画像処理装置およびその方法
【課題】入力装置からの入力画像に対して、ブルーノイズ特性を示す母点配列を行い、且つ、画像のエッジを考慮し、ボロノイ図におけるボロノイ多角形の一辺が画像のエッジと重なるようにする。
【解決手段】入力画像に対して、主要エッジを抽出し、主要エッジに沿った点列を配置しそのセル領域を決定する。しかる後、画像のエッジ情報（多値情報）に基づいてセルのサイズとその重心位置を求め、主要エッジに沿った点列と重心点列の両者の点列からボロノイ図を作成する。
【解決手段】入力画像に対して、主要エッジを抽出し、主要エッジに沿った点列を配置しそのセル領域を決定する。しかる後、画像のエッジ情報（多値情報）に基づいてセルのサイズとその重心位置を求め、主要エッジに沿った点列と重心点列の両者の点列からボロノイ図を作成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力画像データを変形加工し、NPR（Non-Photo Realistic）な画像を生成し、プリント出力する画像処理装置に関するものである。
【背景技術】
【０００２】
従来、プリンタやコピー機等の記録装置は、情報の伝達手段として原稿となるオリジナルに忠実にプリントアウトすることが主流であった。しかし近年、付加価値を高めるために、単に美しく綺麗に出力する事以外に、デジタルカメラなどで撮影した自然画像を、絵画調やイラスト調等のアート風に変形加工して観賞用として出力することが要求されてきている。特に絵画調は、油絵風や水彩画風、貼り絵風など様々な様式があり、一つのオリジナルから種々の加工が可能で観賞用として楽しめる作品製作が可能である。このためプリントサービスやフォトアルバム製作サービスなどにおいて、付加価値を高める技術として注目されている。
【０００３】
その代表的な手法として、入力画像を点列で構成しその点列からなるボロノイ多角形から各多角形をその領域に匹敵する代表色で塗りつぶす、いわゆるボロノイ図形を求める方法がある。かかる方法の利点は、ボロノイ多角形の塗りつぶし方法を細工することや後処理を変えることにより、油絵調や水彩画調などの様々な出力に対応できることである。このボロノイ多角形からNPR画像を得る方法として、ヘンリージョハン他、「領域ベース・ストロークベースのアート風画像生成法」で、詳述されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】ヘンリージョハン、松井、芳賀、土橋、西田；「領域ベース・ストロークベースのアート風画像生成法」、電子情報通信学会論文誌 D-２、 Vol.J88-D-２, No.2, pp.358-367 (2005)
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来の方法では母点である点列の生成において、
（１）入力画像の空間周波数に応じた分散性の良い、すなわちブルーノイズ特性となる母点配置が容易でないこと、
（２）画像のエッジを考慮した配置をとると処理が複雑になる
等の問題があった。特に（２）の問題解決のために、従来法では母点配置の工程において最適化手法を用い、初期設定の母点の移動を繰り返し計算にて行うなど、非常に処理時間がかかっていた。
【課題を解決するための手段】
【０００６】
本発明は上記問題を解決し、画質に応じた分散性がよくブルーノイズ特性を満たす母点の配列と、エッジを考慮した母点の点列配置を容易に構成でき、処理時間が極めて短くできたものである。
【０００７】
上記課題を解決するため、本発明は以下の３工程からなる手段を備える。
１．エッジ情報抽出工程
２．点列作成工程
３．ボロノイ・ダイアグラム作成工程
【発明の効果】
【０００８】
本発明によれば、かかる手段/構成により入力画像をブルーノイズ特性を呈す母点からなる点列配置が得られ、且つ、エッジを考慮した母点配列となるため、より高画質なNPR画形態像を得ることが出来るものである。
【図面の簡単な説明】
【０００９】
【図１】本発明における処理のフローを示す図、
【図２】実施例の画像処理装置の構成例を示すブロック図、
【図３】処理されたデータを出力するための図
【図４】実施例の画像処理装置の構成例を示す図
【図５】エッジ情報抽出を示すブロック図
【図６】エッジ情報抽出結果のエッジ画像を示す図で、（Ａ）入力原画像（Ｂ）エッジ画像（多値）（Ｃ）主要エッジ画像（二値）を示す図
【図７】点列生成を示すブロック図
【図８】点列作成のフローチャートを示す図、
【図９】図8に示すスタートアドレス検出のフローチャートを示す図
【図１０】点列作成の概念を示す図
【図１１】画素探索の手法を示す図
【図１２】画素探索時のルックアップテーブルを示す図、
【図１３】ルックアップテーブルを用いて次画素を検出するフローチャートを示す図、
【図１４】セルの重心と累積濃度を求めるフローチャートを示す図
【図１５】点列作成による出力画像で、（Ａ）作成された点列、（Ｂ）作成されたセルの形状を示す図
【図１６】（Ａ）一様画像データを与えた時の出力点列を示す図、（Ｂ）図（Ａ）のフーリエスペクトルを示す図
【図１７】ボロノイ図の作図を説明する図
【図１８】ボロノイ図作図のフローチャートを示す図
【図１９】ボロノイ図作画のアルゴリズムを示す図、
【図２０】作画されたボロノイ図を示す図
【図２１】ＣＧ画像の処理を示す図で、（Ａ）入力原画像を示す図、（Ｂ）エッジ抽出画像（多値）を示す図、（Ｃ）点列分布を示す図（Ｄ）（Ｃ）の点列に基づくボロノイ図を示す図、（Ｅ）ボロノイ多角形に塗りつぶしを行った時の図、
【図２２】エッジを考慮するアルゴリズムを示す図
【図２３】主要エッジラインに沿って点列とセル領域を求める方法の説明図
【図２４】主要エッジラインに沿って点列を配置する方法のフローチャートを表す図
【図２５】主要エッジラインに沿って点列を配置する処理を表す図で、（Ａ）主要エッジを表す図（Ｂ）主要エッジの周りに配置された点列を表す図（Ｃ）点列の領域であるセルを表す図、
【図２６】セルの領域の中抜けを補正する方法の説明図
【図２７】セルの中抜け対策を行った後のセルの領域を示す図
【図２８】主要エッジを考慮した時の点列配置のフローチャートを示す図
【図２９】主要エッジを考慮した時の処理結果を示す図で、（Ａ）点列配置を示す図（Ｂ）ボロノイ図で多角形の内部を塗りつぶした図
【図３０】別の画像での処理結果を示す図で、（Ａ）主要エッジの周りの点列を示す図、（Ｂ）主要エッジの周りの点列に対するセルを示す図、（Ｃ）主要エッジの周りの点列と、エッジ画像（多値）に基づく点列とを合成した図、（Ｄ）（Ｃ）の点列に対するボロノイ図（Ｅ）ボロノイ図の多角形の内部を塗りつぶした時の図
【図３１】作成されたセルとその重心を示す図
【図３２】ボロノイ多角形の重心処理を表すフローチャートを示す図
【図３３】ボロノイ多角形の重心処理を示す図で、（Ａ）重心移動を行う前、（Ｂ）重心移動を行った後の点列とボロノイ図
【実施例】
【００１０】
以下、本発明を図面を参照しながら説明する。図２は本発明の装置構成を示したものである。スキャナー１、電子写真をベースとしたプリンタ２からなる複写機やMFP（Multi-Functional Printer）は、内蔵されたコントローラ３によりその機能が制御される。コントローラ３はROM 4、RAM 5、プログラムメモリや画像データを記憶するHDD ６、ディスプレイ 8、キーボード９、通信機能１０、CPU 7等からなり、ＣＰＵ 7が全体のコントロールおよび画像処理の演算処理を司る。また、演算処理負荷の高い場合は専用ＬＳＩにて演算処理を行うこともある。
【００１１】
図３は本発明による処理結果のNPR出力画像をプリントする構成図で、プリンタ2からの水平・垂直の同期信号１５は出力ラスター画像のH-Sync, V-Sync信号と画素クロックにより構成され、画像メモリ１３に記憶された画像データをレーザドライバー1４を経てビーム変調された出力信号１６を得る。かかる変調光ビームは図示はされていないが、電子写真ベースの記録装置に導かれ、光露光→現像→転写→定着の電子写真プロセスを経て画像出力される。
【００１２】
図４は本発明を搭載している画像記録装置の光学系の構成図を示す。半導体レーザ等による光源１７からの出射光ビームは、球面系あるいはアナモフィック光学系によるコリメータレンズ18により回転多面鏡２１の反射面に入射する。回転多面鏡の回転により反射ビームは光偏向を受けｆθレンズ等の結像レンズ19へ入射する。結像レンズ１９により結像した光スポットは感光ドラム２０上を光ビーム走査を行う。
【００１３】
図１は本発明におけるNPR画像を生成するための処理フローを示す。本発明は、大きく分けて以下の３つの工程から構成される。
１．エッジ情報抽出工程（２３）
２．点列作成工程（２４）
３．ボロノイ・ダイアグラム作成工程（２５）
以下、順次説明する。
【００１４】
図５はエッジ情報抽出工程を示したもので、画像読み取りデータ２７は、エッジ抽出フィルタ２８によりエッジ画像２９が得られる。エッジ抽出フィルタ２８は通常の一次微分、二次微分フィルタであれば何でもよい。ここでは一次微分のPrewittフィルタで説明する。Prewittフィルタは数式１に示すように一次微分フィルタであるので、2次元画像に適用するには水平・垂直成分をそれぞれ抽出する。また負値があるためそれぞれ絶対値をとって加算する。図６の（A）は入力画像を示し、同（B）はかかるPrewittフィルタでの出力結果を示す。エッジ量は、画像濃度の変化の急激な部分（つまりエッジの強い部分）は濃い黒で与えられ、濃度変化の緩やかな部分（つまりエッジの弱い部分）は白に近い色となるように設定され、多値データとして表される。
【数１】
【００１５】
更に、かかるエッジ画像２９は二値化３０により０，１（８ビットの画像データであれば、０．２５５）に二値化される。しかる後、細線化され主要エッジ抽出３１により主要エッジのみ抽出される。二値化３０は、閾値を設定する事により二値化される。二値化の結果、エッジの強度により抽出されたエッジの線幅は場所によって異なるし、場合によってはエッジ数が多くなりすぎる。このため細線化と、主要エッジ抽出を行う。
【００１６】
細線化手法は様々な手法があるが、本発明では、Hilditchによるアルゴリズムを用いる。かかる細線化により、エッジ画像は1画素幅のエッジライン画像に変換される。主要エッジ抽出は、かかるエッジラインを、各エッジラインに沿って線長をカウントし、線長の長いもののみを抽出する事により選ばれる。
図６（C）は細線化と主要エッジ抽出結果による出力画像を示す。図中、白い線が主要なエッジを示す。
【００１７】
次に点列作成工程について説明する。この工程においては、入力画像に対応した分散性の良い点列を求める必要がある。求める点列は、入力画像の空間周波数が高い領域、すなわちエッジ領域、には点列密度を高くし、空間周波数が低い領域、すなわち平滑領域、には点列密度を低くする。また分散性が良いということは、点列からなる網点画像の空間周波数分布がブルーノイズ特性を示すことである。
【００１８】
さらに、点列に基づくボロノイ図形を構成した時、ボロノイ多角形の一つの辺が、入力画像のエッジラインと重なるように配置することである。このため、点列作成は図7に示される以下の2工程から構成される。
（１）エッジに沿った母点配置と領域を決定する工程２３a
（２）エッジ情報に応じたセルサイズと母点を決定する工程２３b
【００１９】
まず、（２）のエッジ情報に応じたセルサイズと母点を決定する工程２３bについて説明する。ここでは、入力画像の空間周波数に対応した、分散性の良い点列を求める。即ち、入力画像の空間周波数が高い領域、すなわちエッジ領域、には点列密度を高くし、空間周波数が低い領域、すなわち平滑領域、には点列密度を低くする。
【００２０】
図１０は、エッジ量に対応したセル領域の決定と母点の求め方を示したものである。セル領域４６は後述の画素探索でその領域が求められ、母点はかかるセル領域の重心４７を示す。即ちエッジ画像（多値）において、始点を中心にセルを成長させ、画素の累積データがある閾値を超えるまで画素探索を行い、セルの拡張を行う。ある閾値に達した段階で、それまで探索した画素領域を最終セルサイズとし、かかるセルの重心位置を母点とする。
【００２１】
次にこの処理を図８のフローチャートに沿って説明する。まず、エッジ画像（多値）のある一点をスタートアドレスとして検出し（ＳＴＥＰ３０）、探索のためのパラメータのイニシャライズを行う（ＳＴＥＰ３１）。具体的には初期の重心位置の（x0,y0）座標をスタートアドレス値とし、累積濃度NBを０とする。
【００２２】
しかる後、スタートアドレス近傍の1画素を読み込み（３２）、その画素の濃度値（画像データ）を累積濃度NBに加算し、新たな重心位置（Gx,Gy）を求める（３３）。即ち、図14に示されるように、読み込んだ画素の座標を（x1,y1）、（x1,y1）における画像データをD１、これまでの累積濃度値をＮＢとすると、新たな累積濃度値NB‘ および新たな重心座標（Gx’,Gy’）は
NB’＝NB＋D１
Gｘ’＝(ｘ１・D１＋Gx・NB)/（D１＋NB）
Gｙ’＝(ｙ１・D１＋Gｙ・NB)/（D１＋NB） （２）
で与えられる。（ＳＴＥＰ５４）
【００２３】
セルサイズの決定は、かかる操作を繰り返すことによって行われる。セルサイズは、最小セルサイズＣminと最大セルサイズＣmaxがあらかじめ与えられており、この中に入るようにする。また累積濃度も閾値があらかじめ決められているものとする。ＣminとＣmaxの値は、求められる点列の分散性を高めるために、セル単位で乱数α，βを与え変動させる。即ち、
Ｃmin’＝Ｃmin＋α
Ｃmax’＝Ｃmax＋β （３）
かかる変動を与えることにより周期性を除去し分散性を向上させている。
【００２４】
図８においてセルの拡張は、セルサイズＣが最小値Ｃminを超えるまで行われ、累積濃度と重心位置が計算される。最小セルサイズを超えた段階で（ＳＴＥＰ３４）、累積濃度値ＮＢが閾値（これをＮＢ０とする）以下か（ＳＴＥＰ３５）、セルサイズＣが最大セルサイズＣmax以下か（ＳＴＥＰ３６）の判断を行う。即ち、
ＮＢ＜ＮＢ０
Ｃ＜Ｃmax （４）
の条件を満たせば、次画素検出（３９）を行い、同様の操作を繰り返す。そして、これらの条件のいずれかが満たされなければ、画素探索を終了し、セルの固定を行い、セルサイズと重心位置を決定する（ＳＴＥＰ３７）。その後、次のセルの探索を行う。この操作を全画素に対して行い、全画素がすべて読み込まれた段階（ＳＴＥＰ３８）で終了する。
【００２５】
図９はセルのスタートアドレスの検出のフローを示したものである。初めに画像サイズと同サイズのビットマップデータP（x,y）を用意し、P(x,y)=0にイニシャライズしておく。スタートアドレスの検出は、P(x,y) をラスター状にスキャンし（４０）、座標（x0、y0）点における画素データを読み込む（ＳＴＥＰ４１）。もしP(x0,y0)=0であれば（ＳＴＥＰ４２）、スタートアドレスとなり（ＳＴＥＰ４３）、そうでなければ次の画素を探索する。P(x,y)は図8の画素探索において、1画素データを読み込む毎にP(x,y)=1となる。
【００２６】
図11はセルの次画素の探索の探索ルートを示したものである。探索ルートは、スタート画素X（ｘ0,ｙ0）を中心に円弧上に行われる。スタート画素よりも上方はすでに探索された画素になるため、探索ルートはスタート画素に対して下方の領域のみとなる。探索ルートの画素を表すアドレス情報は、スタートアドレスを原点とした変位量をルックアップテーブルとして記憶される。
【００２７】
図１２はこのルックアップテーブルに記憶される情報を示している。また、図１３はその演算処理を示す。画素探索を行う次画素の検出は、スタートアドレス（ｘ0、ｙ0）を起点として、
ｘ＝ｘ０＋ＬＵＴ_Ｘ（ｉ）
ｙ＝ｙ０＋ＬＵＴ_Ｙ（ｉ） （５）
ここで、ＬＵＴ_Ｘ（ｉ）はルックアップテーブルのi番目のｘアドレスを、ＬＵＴ_Ｙ（ｉ）はルックアップテーブルのi番目のｙアドレスを示す。iを０から順次増加させることにより次画素を順次求めることが出来る。
【００２８】
ルックアップテーブルの作成は、以下のようにして求められる。まず、原点を起点にし画素（ｐ、ｑ） ; p＝−pmax〜pmax, q=0〜qmax に対する距離の2乗Ｌを次式で求める。
Ｌ(p,q)＝p^2+q^2 （^は2乗を表す）
しかる後、ＳＯＲＴによりＬを小さい順に並び変える、即ち、i順に並び変えられたものをＬ（ｐ，ｑ，i)とすると、i順に並んだ(p,q)値から、
ＬＵＴ_X(i)=p
ＬＵＴ_Y（i)=q
がルックアップテーブル値として得られる。
【００２９】
以上の操作を繰り返し行い、入力画像データの全領域を処理する。Ｐ（ｘ，ｙ）がすべて1となった段階で終了する。以上のようにして、セルとセルの重心を母点とする点列が求まる。図１５は図６（Ｂ）の画像から以上のようにして求めた点列を示す。エッジの強い領域は密度が高い点列から構成されている事が分かる。同図（Ｂ）は、セル領域を示す。セルはスタートアドレスを中心に下向きの扇型となっている。
【００３０】
図１６はエッジ画像が一様な画像を入力画像とした時のもので、エッジの無い一様データ１２０/２５５を入力画像値としたものである。（Ａ）は本処理により出力された点列を、（Ｂ）はそのフーリエスペクトルを示す。フーリエスペクトル分布は低周波数におけるスペクトル強度が低く、高周波数におけるスペクトル強度が高い、いわゆるブルーノイズ特性を示す。このため分散性の良い点列配列となっている事が分かる。分散の程度は式３におけるα、およびβの値を大きくするほど大きくなるが、逆にノイズの影響で画質が劣化する。ＣＧ画像では一様なデータが続くことが多いため、点列に周期性が現れやすい。従って、自然画像の場合はα、およびβの値は小さくとり、ＣＧ画像などでは大きくとるのがよい。
【００３１】
図１７はボロノイ図の作成を示すもので、点列データを入力し（２４a）、かかる点列に対するボロノイ図形を作成する（２４b）。ここでボロノイ図とは、点Pi、Pj に対して
V(Pi)=｛P|d(P,Pi)＜d(P,Pj), ∀j≠i ｝ （６）
但しd(P,Pi) は点P とPi の距離を表す。
なる点の集合であり、点Pi の勢力圏を現す。
【００３２】
図１８はボロノイ図の作図方法を示したものである。点列データを配置した画像をラスター・スキャンを開始し（ＳＴＥＰ６０）、任意の画素位置（ｘ０、ｙ０）を与え（ＳＴＥＰ６１）、その点に最も近い点列Ｐｎを求める（ＳＴＥＰ６２）。その結果、画素位置（ｘ０、ｙ０）はＰｎの領域に属することになる。そこで画素位置（ｘ０、ｙ０）におけるデータをＰｎとする（ＳＴＥＰ６３）。これを全画素において行う（ＳＴＥＰ６４）。その結果、各画素がどの点列に属するか決まる。
【００３３】
図１９はこの説明図で、点列７１、７２a、７２b、７２c、７２dから構成されるとき、任意の画素位置Ｘとの距離を計算する。その結果、点列７１が最も距離が短いことが分かると、画素位置Ｘは点７１の勢力圏となる。点Ｘを全画素スキャンすることにより、各画素の勢力圏が求まる。ボロノイ多角形は、この勢力圏の境界線から構成される多角形群を表す。このようにしてボロノイ図が作製される。図２０は図１５（Ａ）の点列からボロノイ多角形を作画したものである。空間周波数の高い領域に小面積のボロノイ多角形が配置されていることが分かる。
【００３４】
図２１は以上のアルゴリズムを同図（Ａ）に示す図形を入力画像として処理したものである。同図（Ｂ）はエッジ画像（多値）、（Ｃ）は点列、（Ｄ）はボロノイ図形を示す。（Ｅ）はボロノイ多角形の内部を母点位置の画像データで塗りつぶしたものである。図からわかるように画像のエッジ部では点列の密度が高くなりボロノイ多角形の面積が小さくなっているが、エッジが考慮されていないため、輪郭がギザギザしたものになっている事が分かる。
【００３５】
この対策として、エッジを考慮した点列配置を行う。図５において、エッジ抽出工程は、前述のエッジ画像（多値）と、主要エッジ画像（二値）の2つの手段から構成されているが、対策にあたり主要エッジ情報を用いてエッジ近傍の点列配置を別途行う。図２２はかかる点列配置の方法をブロック図に示したもので、先ず、エッジラインに沿って点列を配置し（８１）、配置された点列の各々の周りに領域を設定する（８２）。
【００３６】
図２３はかかる点列配置の様子を具体的に説明するもので、エッジライン８３に沿って、エッジラインを挟んで距離dの位置に2つの点列Ａ（８４a），Ｂ（８４b）を相対するように配置する。線分ＡＢと接点におけるエッジラインが直交する。そして、それぞれの点に対する円形の領域８５a,８５bを設定し、点Ａ，Ｂに対する占有領域としてセルの領域を決定する。円の半径はｄとし、2つの円形領域がエッジライン状で互いに接するようになる。
【００３７】
次に、エッジラインに沿って次の点列を配置していく。この時、円形領域が互いに重ならないようにするため、円が重ならないか判定し（ＳＴEP88),重なる場合はエッジに沿って画素を円が重ならなくなるまで移動する。このようにして主要エッジラインすべてにわたって点列と点列を包含する領域を設定する。
【００３８】
図２４はこの処理のフローを示す。エッジ画像（二値）をＰ２（ｘ，ｙ）とする。エッジ部分は白（１）、エッジでない部分は黒（０）であるとする。エッジ画像の画素をラスター状にスキャンすることにより、最初に見つかった主要エッジラインから順次処理を行う。エッジラインの先頭からエッジラインに沿って画素を移動していき、エッジラインに直交しエッジラインからｄ＋Δ離れた位置に点Ａ，Ｂを設定する（ＳＴＥＰ８６）。ここでΔは微小量を表し、多少ランダム性を持たせるものである。しかる後、点Ａ，Ｂを中心として半径ｄ＋Δの円を描き点Ａ，Ｂの領域とする（ＳＴＥＰ８７）。
【００３９】
この時、前の円と重なるか否かをチェックし（ＳＴＥＰ８８）、重なる場合はエッジラインに沿った画素移動を行い、円が重ならない位置まで移動する。重ならなくなった状態で点Ａ，Ｂと円をFixし（ＳＴＥＰ８９）、すべての主要ラインをスキャンして終了する。エッジラインに沿って探索した画素はＰ２（ｘ，ｙ）＝０（黒）として、順次消去されていくものとする。
【００４０】
図２５はこの処理を画像で示すもので、図２１（Ａ）の画像に対する主要エッジラインを図２５（Ａ）に示す。同図（Ｂ）は主要エッジラインに沿って配置された点列を、同図（Ｃ）は各点列の周りに円領域を配置したものである。
【００４１】
この点と円領域は、母点およびセル領域に対応する。同図（Ｃ）から分かるように、セル領域に囲まれた内部に非セル領域が存在する。これは後述のエッジ画像（多値）による点列配置に悪影響を与えるため、図２６に示すように点Ａ，Ｂの中点（すなわちエッジライン状の点）を中心とした半径ｄ＋Δの円を描き、これをセル領域に含ませるものとする。
即ち，初めに求めたセル領域Ｕ１と、Ａ，Ｂの中点における円領域をＵ２とした時、
新たなセル領域Ｕ＝Ｕ１＋Ｕ２ （７）
であらわされる。図２７はそのようにして得られセル領域を示す。図２５（Ｃ）と比べるセル領域の中抜けが消滅していることが分かる。
【００４２】
以上のようにして求められた点列とセル領域をベースに、エッジ画像（多値）を用いて点列作成を行う。処理のフローは図８に示したものと同じであるが、異なるところは主要エッジラインに沿って強制的に配置したセル領域を考慮することである。即ち、図２８に示すように、主要エッジラインに沿って得られた領域を既に決まったセル領域とし（ＳＴＥＰ９０）、セル領域以外のところに点列を配置する（ＳＴＥＰ９１）。具体的には、図８におけるイニシャライズ（ＳＴＥＰ３１）で、P（x,y）をエッジラインに沿ったセル領域にイニシャライズしておく。
Ｐ（ｘ，ｙ）＝１ ｘ、ｙがＵに含まれる時
＝０ それ以外 （８）
【００４３】
図２９はこのようにして得られた点列を示す。主要エッジラインの周りに配置された点列と、図８のフローにより求められた点列を合成したものである。両者を合わせて最終的な点列が構成され、かかる点列に基づくボロノイ図が描かれる。同図（Ｂ）はかかる点列をベースにボロノイ多角形を求め、その母点位置の画像データで多角形の内部を塗りつぶしたものである。図２１（Ｅ）と比較すると、画像のエッジがボロノイ多角形の一辺と重なっており、エッジにおけるギザギザ模様が無くなり、エッジを考慮した処理となっていることが分かる。
【００４４】
図３０は、図６（Ａ）の画像に対して処理したもので、エッジ画像（多値）は図６（Ｂ）、主要エッジラインは図６（Ｃ）を用いてしょりされたものである。図３０（Ａ）は、主要エッジラインの周りに配置した点列を、同図（Ｂ）はそれらの点列に対するセル領域を示す。同図（Ｃ）は、合成された最終的な点列を、同図（Ｄ）にかかる点列に基づくボロノイ図を示す。同図（Ｅ）はこのボロノイ多角形の母点位置の画像データで多角形の内部を塗りつぶした画像を示す。画像のエッジがボロノイ多角形の一辺と重なっており、エッジを考慮した処理となっていることが分かる。
【００４５】
以上のように、点列作成工程を、主要エッジラインに沿って母点を配置する手段と、多値エッジ情報に応じてセルサイズと母点を決定する手段とから構成することにより、分散性のよう点列を得ることが出来、作成されるボロノイ多角形の一辺を画像のエッジと重ねることが出来、画像の輪郭情報が考慮された高画質な出力画像を得ることが出来たものである。
【００４６】
一方、主要エッジラインに沿って母点を配置する手段と、多値エッジ情報に応じてセルサイズと母点を決定する手段とを別々に行うため、点列の分散性が損なわれることがある。図３１はその説明図で、主要エッジラインに沿って配列された点８４とセル８５に対して、新たにエッジ画像（多値）に基づき作成されたセル４６（斜線部分）が、セル８４を避けて形成されるため歪な形状を示す。その結果セル４６の重心位置がセル８５の領域内に入り込み点８４に接近し、点列の分散性が悪くなるということが生じる。この現象はまれに起こりその近傍の最終画質が劣化する。
【００４７】
この問題を回避するため、図３２に示すように、先ず全点列からボロノイ図を作成し（ＳＴＥＰ９２）、ボロノイ多角形の重心位置を求め（ＳＴＥＰ９３）、主要エッジの周りの点列以外の点列をこの重心位置で置き換える（ＳＴＥＰ９４）。通常、ボロノイ多角形の重心位置は、点列の分散性が良ければ母点の位置からあまり移動しない。しかしながら極端に接近した母点は、それぞれの重心位置と大きくずれる。
【００４８】
図３３（Ａ）は主要エッジライン近傍の点列配置とボロノイ多角形を示したものである。主要エッジラインの周りの点列を△で示し、それ以外の点列を●で示す。点列の移動は●の点列のみに行う。○はボロノイ多角形の重心位置を示す。点列の変換は●の点列に対しておこなわれ、重心移動後の点列は○となる。移動の結果、新たな点列が出来上がり、かかる点列によるボロノイ図形を同図（Ｂ）に示す。移動により接近しすぎていた点列は多少離れ、点列の分散の一様性が向上する事が分かる。
【００４９】
以上説明したように、本発明は入力画像データの空間周波数特性に応じた点列配置を行い、ブルーノイズ特性を示す分散性の良い点列を構成することが出来，更に、画像のエッジとボロノイ多角形の辺が重なるようにし、高品質なボロノイ画像を生成することが出来たものある。これをベースにNPR（Non-Photo Realistic）な様々な画像を生成し出力する事が出来る。本発明では、演算負荷の多い部分は専用ハードウェアやＬＳＩ、ＧＰＵ（Ｇｒａｐｈｉｃ Ｐｒｏｃｅｓｓｏｒ Ｕｎｉｔ）で処理することにより処理の高速化が図れ、画像読み取り後速やかに画像出力が出来る。なお、本発明は、複数の機器（例えばコンピュータ、インタフェイス機器、リーダ、プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、ファクシミリ装置、制御装置など）に適用してもよい。
【００５０】
また、本発明の目的は、上記実施例の機能を実現するコンピュータプログラムを記録した記憶媒体をシステムまたは装置に供給し、そのシステムまたは装置のコンピュータ（CPUやMPU）が前記コンピュータプログラムを実行することでも達成される。この場合、記憶媒体から読み出されたソフトウェア自体が上記実施例の機能を実現することになり、そのコンピュータプログラムと、そのコンピュータプログラムを記憶する、コンピュータが読み取り可能な記憶媒体は本発明を構成する。
【００５１】
また、前記コンピュータプログラムの実行により上記機能が実現されるだけではない。つまり、そのコンピュータプログラムの指示により、コンピュータ上で稼働するオペレーティングシステム(OS)および/または第一の、第二の、第三の、…プログラムなどが実際の処理の一部または全部を行い、それによって上記機能が実現される場合も含む。
【００５２】
また、前記コンピュータプログラムがコンピュータに接続された機能拡張カードやユニットなどのデバイスのメモリに書き込まれていてもよい。つまり、そのコンピュータプログラムの指示により、第一の、第二の、第三の、…デバイスのCPUなどが実際の処理の一部または全部を行い、それによって上記機能が実現される場合も含む。
【００５３】
本発明を前記記憶媒体に適用する場合、その記憶媒体には、先に説明したフローチャートに対応または関連するコンピュータプログラムが格納される。
【産業上の利用可能性】
【００５４】
本発明は、入力画像データを変形加工し、NPR（Non-Photo Realistic）な画像を生成し出力する装置において、出力画像に付加価値を与え、プリントサービスやフォトサービス、フォトアルバム等に利用可能である。
【符号の説明】
【００５５】
１ スキャナー、 ２ プリンタ、 ３ コントローラ、 ４ ＲＯＭ、 ５ ＲＡＭ、 6 ハードディスク、 ７ ＣＰＵ， ８ ディスプレイ、 ９ キーボード、 １０ 通信機能、 １８ コリメータレンズ、 １９ 結像レンズ、 ２０ 感光ドラム
【技術分野】
【０００１】
本発明は、入力画像データを変形加工し、NPR（Non-Photo Realistic）な画像を生成し、プリント出力する画像処理装置に関するものである。
【背景技術】
【０００２】
従来、プリンタやコピー機等の記録装置は、情報の伝達手段として原稿となるオリジナルに忠実にプリントアウトすることが主流であった。しかし近年、付加価値を高めるために、単に美しく綺麗に出力する事以外に、デジタルカメラなどで撮影した自然画像を、絵画調やイラスト調等のアート風に変形加工して観賞用として出力することが要求されてきている。特に絵画調は、油絵風や水彩画風、貼り絵風など様々な様式があり、一つのオリジナルから種々の加工が可能で観賞用として楽しめる作品製作が可能である。このためプリントサービスやフォトアルバム製作サービスなどにおいて、付加価値を高める技術として注目されている。
【０００３】
その代表的な手法として、入力画像を点列で構成しその点列からなるボロノイ多角形から各多角形をその領域に匹敵する代表色で塗りつぶす、いわゆるボロノイ図形を求める方法がある。かかる方法の利点は、ボロノイ多角形の塗りつぶし方法を細工することや後処理を変えることにより、油絵調や水彩画調などの様々な出力に対応できることである。このボロノイ多角形からNPR画像を得る方法として、ヘンリージョハン他、「領域ベース・ストロークベースのアート風画像生成法」で、詳述されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】ヘンリージョハン、松井、芳賀、土橋、西田；「領域ベース・ストロークベースのアート風画像生成法」、電子情報通信学会論文誌 D-２、 Vol.J88-D-２, No.2, pp.358-367 (2005)
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来の方法では母点である点列の生成において、
（１）入力画像の空間周波数に応じた分散性の良い、すなわちブルーノイズ特性となる母点配置が容易でないこと、
（２）画像のエッジを考慮した配置をとると処理が複雑になる
等の問題があった。特に（２）の問題解決のために、従来法では母点配置の工程において最適化手法を用い、初期設定の母点の移動を繰り返し計算にて行うなど、非常に処理時間がかかっていた。
【課題を解決するための手段】
【０００６】
本発明は上記問題を解決し、画質に応じた分散性がよくブルーノイズ特性を満たす母点の配列と、エッジを考慮した母点の点列配置を容易に構成でき、処理時間が極めて短くできたものである。
【０００７】
上記課題を解決するため、本発明は以下の３工程からなる手段を備える。
１．エッジ情報抽出工程
２．点列作成工程
３．ボロノイ・ダイアグラム作成工程
【発明の効果】
【０００８】
本発明によれば、かかる手段/構成により入力画像をブルーノイズ特性を呈す母点からなる点列配置が得られ、且つ、エッジを考慮した母点配列となるため、より高画質なNPR画形態像を得ることが出来るものである。
【図面の簡単な説明】
【０００９】
【図１】本発明における処理のフローを示す図、
【図２】実施例の画像処理装置の構成例を示すブロック図、
【図３】処理されたデータを出力するための図
【図４】実施例の画像処理装置の構成例を示す図
【図５】エッジ情報抽出を示すブロック図
【図６】エッジ情報抽出結果のエッジ画像を示す図で、（Ａ）入力原画像（Ｂ）エッジ画像（多値）（Ｃ）主要エッジ画像（二値）を示す図
【図７】点列生成を示すブロック図
【図８】点列作成のフローチャートを示す図、
【図９】図8に示すスタートアドレス検出のフローチャートを示す図
【図１０】点列作成の概念を示す図
【図１１】画素探索の手法を示す図
【図１２】画素探索時のルックアップテーブルを示す図、
【図１３】ルックアップテーブルを用いて次画素を検出するフローチャートを示す図、
【図１４】セルの重心と累積濃度を求めるフローチャートを示す図
【図１５】点列作成による出力画像で、（Ａ）作成された点列、（Ｂ）作成されたセルの形状を示す図
【図１６】（Ａ）一様画像データを与えた時の出力点列を示す図、（Ｂ）図（Ａ）のフーリエスペクトルを示す図
【図１７】ボロノイ図の作図を説明する図
【図１８】ボロノイ図作図のフローチャートを示す図
【図１９】ボロノイ図作画のアルゴリズムを示す図、
【図２０】作画されたボロノイ図を示す図
【図２１】ＣＧ画像の処理を示す図で、（Ａ）入力原画像を示す図、（Ｂ）エッジ抽出画像（多値）を示す図、（Ｃ）点列分布を示す図（Ｄ）（Ｃ）の点列に基づくボロノイ図を示す図、（Ｅ）ボロノイ多角形に塗りつぶしを行った時の図、
【図２２】エッジを考慮するアルゴリズムを示す図
【図２３】主要エッジラインに沿って点列とセル領域を求める方法の説明図
【図２４】主要エッジラインに沿って点列を配置する方法のフローチャートを表す図
【図２５】主要エッジラインに沿って点列を配置する処理を表す図で、（Ａ）主要エッジを表す図（Ｂ）主要エッジの周りに配置された点列を表す図（Ｃ）点列の領域であるセルを表す図、
【図２６】セルの領域の中抜けを補正する方法の説明図
【図２７】セルの中抜け対策を行った後のセルの領域を示す図
【図２８】主要エッジを考慮した時の点列配置のフローチャートを示す図
【図２９】主要エッジを考慮した時の処理結果を示す図で、（Ａ）点列配置を示す図（Ｂ）ボロノイ図で多角形の内部を塗りつぶした図
【図３０】別の画像での処理結果を示す図で、（Ａ）主要エッジの周りの点列を示す図、（Ｂ）主要エッジの周りの点列に対するセルを示す図、（Ｃ）主要エッジの周りの点列と、エッジ画像（多値）に基づく点列とを合成した図、（Ｄ）（Ｃ）の点列に対するボロノイ図（Ｅ）ボロノイ図の多角形の内部を塗りつぶした時の図
【図３１】作成されたセルとその重心を示す図
【図３２】ボロノイ多角形の重心処理を表すフローチャートを示す図
【図３３】ボロノイ多角形の重心処理を示す図で、（Ａ）重心移動を行う前、（Ｂ）重心移動を行った後の点列とボロノイ図
【実施例】
【００１０】
以下、本発明を図面を参照しながら説明する。図２は本発明の装置構成を示したものである。スキャナー１、電子写真をベースとしたプリンタ２からなる複写機やMFP（Multi-Functional Printer）は、内蔵されたコントローラ３によりその機能が制御される。コントローラ３はROM 4、RAM 5、プログラムメモリや画像データを記憶するHDD ６、ディスプレイ 8、キーボード９、通信機能１０、CPU 7等からなり、ＣＰＵ 7が全体のコントロールおよび画像処理の演算処理を司る。また、演算処理負荷の高い場合は専用ＬＳＩにて演算処理を行うこともある。
【００１１】
図３は本発明による処理結果のNPR出力画像をプリントする構成図で、プリンタ2からの水平・垂直の同期信号１５は出力ラスター画像のH-Sync, V-Sync信号と画素クロックにより構成され、画像メモリ１３に記憶された画像データをレーザドライバー1４を経てビーム変調された出力信号１６を得る。かかる変調光ビームは図示はされていないが、電子写真ベースの記録装置に導かれ、光露光→現像→転写→定着の電子写真プロセスを経て画像出力される。
【００１２】
図４は本発明を搭載している画像記録装置の光学系の構成図を示す。半導体レーザ等による光源１７からの出射光ビームは、球面系あるいはアナモフィック光学系によるコリメータレンズ18により回転多面鏡２１の反射面に入射する。回転多面鏡の回転により反射ビームは光偏向を受けｆθレンズ等の結像レンズ19へ入射する。結像レンズ１９により結像した光スポットは感光ドラム２０上を光ビーム走査を行う。
【００１３】
図１は本発明におけるNPR画像を生成するための処理フローを示す。本発明は、大きく分けて以下の３つの工程から構成される。
１．エッジ情報抽出工程（２３）
２．点列作成工程（２４）
３．ボロノイ・ダイアグラム作成工程（２５）
以下、順次説明する。
【００１４】
図５はエッジ情報抽出工程を示したもので、画像読み取りデータ２７は、エッジ抽出フィルタ２８によりエッジ画像２９が得られる。エッジ抽出フィルタ２８は通常の一次微分、二次微分フィルタであれば何でもよい。ここでは一次微分のPrewittフィルタで説明する。Prewittフィルタは数式１に示すように一次微分フィルタであるので、2次元画像に適用するには水平・垂直成分をそれぞれ抽出する。また負値があるためそれぞれ絶対値をとって加算する。図６の（A）は入力画像を示し、同（B）はかかるPrewittフィルタでの出力結果を示す。エッジ量は、画像濃度の変化の急激な部分（つまりエッジの強い部分）は濃い黒で与えられ、濃度変化の緩やかな部分（つまりエッジの弱い部分）は白に近い色となるように設定され、多値データとして表される。
【数１】
【００１５】
更に、かかるエッジ画像２９は二値化３０により０，１（８ビットの画像データであれば、０．２５５）に二値化される。しかる後、細線化され主要エッジ抽出３１により主要エッジのみ抽出される。二値化３０は、閾値を設定する事により二値化される。二値化の結果、エッジの強度により抽出されたエッジの線幅は場所によって異なるし、場合によってはエッジ数が多くなりすぎる。このため細線化と、主要エッジ抽出を行う。
【００１６】
細線化手法は様々な手法があるが、本発明では、Hilditchによるアルゴリズムを用いる。かかる細線化により、エッジ画像は1画素幅のエッジライン画像に変換される。主要エッジ抽出は、かかるエッジラインを、各エッジラインに沿って線長をカウントし、線長の長いもののみを抽出する事により選ばれる。
図６（C）は細線化と主要エッジ抽出結果による出力画像を示す。図中、白い線が主要なエッジを示す。
【００１７】
次に点列作成工程について説明する。この工程においては、入力画像に対応した分散性の良い点列を求める必要がある。求める点列は、入力画像の空間周波数が高い領域、すなわちエッジ領域、には点列密度を高くし、空間周波数が低い領域、すなわち平滑領域、には点列密度を低くする。また分散性が良いということは、点列からなる網点画像の空間周波数分布がブルーノイズ特性を示すことである。
【００１８】
さらに、点列に基づくボロノイ図形を構成した時、ボロノイ多角形の一つの辺が、入力画像のエッジラインと重なるように配置することである。このため、点列作成は図7に示される以下の2工程から構成される。
（１）エッジに沿った母点配置と領域を決定する工程２３a
（２）エッジ情報に応じたセルサイズと母点を決定する工程２３b
【００１９】
まず、（２）のエッジ情報に応じたセルサイズと母点を決定する工程２３bについて説明する。ここでは、入力画像の空間周波数に対応した、分散性の良い点列を求める。即ち、入力画像の空間周波数が高い領域、すなわちエッジ領域、には点列密度を高くし、空間周波数が低い領域、すなわち平滑領域、には点列密度を低くする。
【００２０】
図１０は、エッジ量に対応したセル領域の決定と母点の求め方を示したものである。セル領域４６は後述の画素探索でその領域が求められ、母点はかかるセル領域の重心４７を示す。即ちエッジ画像（多値）において、始点を中心にセルを成長させ、画素の累積データがある閾値を超えるまで画素探索を行い、セルの拡張を行う。ある閾値に達した段階で、それまで探索した画素領域を最終セルサイズとし、かかるセルの重心位置を母点とする。
【００２１】
次にこの処理を図８のフローチャートに沿って説明する。まず、エッジ画像（多値）のある一点をスタートアドレスとして検出し（ＳＴＥＰ３０）、探索のためのパラメータのイニシャライズを行う（ＳＴＥＰ３１）。具体的には初期の重心位置の（x0,y0）座標をスタートアドレス値とし、累積濃度NBを０とする。
【００２２】
しかる後、スタートアドレス近傍の1画素を読み込み（３２）、その画素の濃度値（画像データ）を累積濃度NBに加算し、新たな重心位置（Gx,Gy）を求める（３３）。即ち、図14に示されるように、読み込んだ画素の座標を（x1,y1）、（x1,y1）における画像データをD１、これまでの累積濃度値をＮＢとすると、新たな累積濃度値NB‘ および新たな重心座標（Gx’,Gy’）は
NB’＝NB＋D１
Gｘ’＝(ｘ１・D１＋Gx・NB)/（D１＋NB）
Gｙ’＝(ｙ１・D１＋Gｙ・NB)/（D１＋NB） （２）
で与えられる。（ＳＴＥＰ５４）
【００２３】
セルサイズの決定は、かかる操作を繰り返すことによって行われる。セルサイズは、最小セルサイズＣminと最大セルサイズＣmaxがあらかじめ与えられており、この中に入るようにする。また累積濃度も閾値があらかじめ決められているものとする。ＣminとＣmaxの値は、求められる点列の分散性を高めるために、セル単位で乱数α，βを与え変動させる。即ち、
Ｃmin’＝Ｃmin＋α
Ｃmax’＝Ｃmax＋β （３）
かかる変動を与えることにより周期性を除去し分散性を向上させている。
【００２４】
図８においてセルの拡張は、セルサイズＣが最小値Ｃminを超えるまで行われ、累積濃度と重心位置が計算される。最小セルサイズを超えた段階で（ＳＴＥＰ３４）、累積濃度値ＮＢが閾値（これをＮＢ０とする）以下か（ＳＴＥＰ３５）、セルサイズＣが最大セルサイズＣmax以下か（ＳＴＥＰ３６）の判断を行う。即ち、
ＮＢ＜ＮＢ０
Ｃ＜Ｃmax （４）
の条件を満たせば、次画素検出（３９）を行い、同様の操作を繰り返す。そして、これらの条件のいずれかが満たされなければ、画素探索を終了し、セルの固定を行い、セルサイズと重心位置を決定する（ＳＴＥＰ３７）。その後、次のセルの探索を行う。この操作を全画素に対して行い、全画素がすべて読み込まれた段階（ＳＴＥＰ３８）で終了する。
【００２５】
図９はセルのスタートアドレスの検出のフローを示したものである。初めに画像サイズと同サイズのビットマップデータP（x,y）を用意し、P(x,y)=0にイニシャライズしておく。スタートアドレスの検出は、P(x,y) をラスター状にスキャンし（４０）、座標（x0、y0）点における画素データを読み込む（ＳＴＥＰ４１）。もしP(x0,y0)=0であれば（ＳＴＥＰ４２）、スタートアドレスとなり（ＳＴＥＰ４３）、そうでなければ次の画素を探索する。P(x,y)は図8の画素探索において、1画素データを読み込む毎にP(x,y)=1となる。
【００２６】
図11はセルの次画素の探索の探索ルートを示したものである。探索ルートは、スタート画素X（ｘ0,ｙ0）を中心に円弧上に行われる。スタート画素よりも上方はすでに探索された画素になるため、探索ルートはスタート画素に対して下方の領域のみとなる。探索ルートの画素を表すアドレス情報は、スタートアドレスを原点とした変位量をルックアップテーブルとして記憶される。
【００２７】
図１２はこのルックアップテーブルに記憶される情報を示している。また、図１３はその演算処理を示す。画素探索を行う次画素の検出は、スタートアドレス（ｘ0、ｙ0）を起点として、
ｘ＝ｘ０＋ＬＵＴ_Ｘ（ｉ）
ｙ＝ｙ０＋ＬＵＴ_Ｙ（ｉ） （５）
ここで、ＬＵＴ_Ｘ（ｉ）はルックアップテーブルのi番目のｘアドレスを、ＬＵＴ_Ｙ（ｉ）はルックアップテーブルのi番目のｙアドレスを示す。iを０から順次増加させることにより次画素を順次求めることが出来る。
【００２８】
ルックアップテーブルの作成は、以下のようにして求められる。まず、原点を起点にし画素（ｐ、ｑ） ; p＝−pmax〜pmax, q=0〜qmax に対する距離の2乗Ｌを次式で求める。
Ｌ(p,q)＝p^2+q^2 （^は2乗を表す）
しかる後、ＳＯＲＴによりＬを小さい順に並び変える、即ち、i順に並び変えられたものをＬ（ｐ，ｑ，i)とすると、i順に並んだ(p,q)値から、
ＬＵＴ_X(i)=p
ＬＵＴ_Y（i)=q
がルックアップテーブル値として得られる。
【００２９】
以上の操作を繰り返し行い、入力画像データの全領域を処理する。Ｐ（ｘ，ｙ）がすべて1となった段階で終了する。以上のようにして、セルとセルの重心を母点とする点列が求まる。図１５は図６（Ｂ）の画像から以上のようにして求めた点列を示す。エッジの強い領域は密度が高い点列から構成されている事が分かる。同図（Ｂ）は、セル領域を示す。セルはスタートアドレスを中心に下向きの扇型となっている。
【００３０】
図１６はエッジ画像が一様な画像を入力画像とした時のもので、エッジの無い一様データ１２０/２５５を入力画像値としたものである。（Ａ）は本処理により出力された点列を、（Ｂ）はそのフーリエスペクトルを示す。フーリエスペクトル分布は低周波数におけるスペクトル強度が低く、高周波数におけるスペクトル強度が高い、いわゆるブルーノイズ特性を示す。このため分散性の良い点列配列となっている事が分かる。分散の程度は式３におけるα、およびβの値を大きくするほど大きくなるが、逆にノイズの影響で画質が劣化する。ＣＧ画像では一様なデータが続くことが多いため、点列に周期性が現れやすい。従って、自然画像の場合はα、およびβの値は小さくとり、ＣＧ画像などでは大きくとるのがよい。
【００３１】
図１７はボロノイ図の作成を示すもので、点列データを入力し（２４a）、かかる点列に対するボロノイ図形を作成する（２４b）。ここでボロノイ図とは、点Pi、Pj に対して
V(Pi)=｛P|d(P,Pi)＜d(P,Pj), ∀j≠i ｝ （６）
但しd(P,Pi) は点P とPi の距離を表す。
なる点の集合であり、点Pi の勢力圏を現す。
【００３２】
図１８はボロノイ図の作図方法を示したものである。点列データを配置した画像をラスター・スキャンを開始し（ＳＴＥＰ６０）、任意の画素位置（ｘ０、ｙ０）を与え（ＳＴＥＰ６１）、その点に最も近い点列Ｐｎを求める（ＳＴＥＰ６２）。その結果、画素位置（ｘ０、ｙ０）はＰｎの領域に属することになる。そこで画素位置（ｘ０、ｙ０）におけるデータをＰｎとする（ＳＴＥＰ６３）。これを全画素において行う（ＳＴＥＰ６４）。その結果、各画素がどの点列に属するか決まる。
【００３３】
図１９はこの説明図で、点列７１、７２a、７２b、７２c、７２dから構成されるとき、任意の画素位置Ｘとの距離を計算する。その結果、点列７１が最も距離が短いことが分かると、画素位置Ｘは点７１の勢力圏となる。点Ｘを全画素スキャンすることにより、各画素の勢力圏が求まる。ボロノイ多角形は、この勢力圏の境界線から構成される多角形群を表す。このようにしてボロノイ図が作製される。図２０は図１５（Ａ）の点列からボロノイ多角形を作画したものである。空間周波数の高い領域に小面積のボロノイ多角形が配置されていることが分かる。
【００３４】
図２１は以上のアルゴリズムを同図（Ａ）に示す図形を入力画像として処理したものである。同図（Ｂ）はエッジ画像（多値）、（Ｃ）は点列、（Ｄ）はボロノイ図形を示す。（Ｅ）はボロノイ多角形の内部を母点位置の画像データで塗りつぶしたものである。図からわかるように画像のエッジ部では点列の密度が高くなりボロノイ多角形の面積が小さくなっているが、エッジが考慮されていないため、輪郭がギザギザしたものになっている事が分かる。
【００３５】
この対策として、エッジを考慮した点列配置を行う。図５において、エッジ抽出工程は、前述のエッジ画像（多値）と、主要エッジ画像（二値）の2つの手段から構成されているが、対策にあたり主要エッジ情報を用いてエッジ近傍の点列配置を別途行う。図２２はかかる点列配置の方法をブロック図に示したもので、先ず、エッジラインに沿って点列を配置し（８１）、配置された点列の各々の周りに領域を設定する（８２）。
【００３６】
図２３はかかる点列配置の様子を具体的に説明するもので、エッジライン８３に沿って、エッジラインを挟んで距離dの位置に2つの点列Ａ（８４a），Ｂ（８４b）を相対するように配置する。線分ＡＢと接点におけるエッジラインが直交する。そして、それぞれの点に対する円形の領域８５a,８５bを設定し、点Ａ，Ｂに対する占有領域としてセルの領域を決定する。円の半径はｄとし、2つの円形領域がエッジライン状で互いに接するようになる。
【００３７】
次に、エッジラインに沿って次の点列を配置していく。この時、円形領域が互いに重ならないようにするため、円が重ならないか判定し（ＳＴEP88),重なる場合はエッジに沿って画素を円が重ならなくなるまで移動する。このようにして主要エッジラインすべてにわたって点列と点列を包含する領域を設定する。
【００３８】
図２４はこの処理のフローを示す。エッジ画像（二値）をＰ２（ｘ，ｙ）とする。エッジ部分は白（１）、エッジでない部分は黒（０）であるとする。エッジ画像の画素をラスター状にスキャンすることにより、最初に見つかった主要エッジラインから順次処理を行う。エッジラインの先頭からエッジラインに沿って画素を移動していき、エッジラインに直交しエッジラインからｄ＋Δ離れた位置に点Ａ，Ｂを設定する（ＳＴＥＰ８６）。ここでΔは微小量を表し、多少ランダム性を持たせるものである。しかる後、点Ａ，Ｂを中心として半径ｄ＋Δの円を描き点Ａ，Ｂの領域とする（ＳＴＥＰ８７）。
【００３９】
この時、前の円と重なるか否かをチェックし（ＳＴＥＰ８８）、重なる場合はエッジラインに沿った画素移動を行い、円が重ならない位置まで移動する。重ならなくなった状態で点Ａ，Ｂと円をFixし（ＳＴＥＰ８９）、すべての主要ラインをスキャンして終了する。エッジラインに沿って探索した画素はＰ２（ｘ，ｙ）＝０（黒）として、順次消去されていくものとする。
【００４０】
図２５はこの処理を画像で示すもので、図２１（Ａ）の画像に対する主要エッジラインを図２５（Ａ）に示す。同図（Ｂ）は主要エッジラインに沿って配置された点列を、同図（Ｃ）は各点列の周りに円領域を配置したものである。
【００４１】
この点と円領域は、母点およびセル領域に対応する。同図（Ｃ）から分かるように、セル領域に囲まれた内部に非セル領域が存在する。これは後述のエッジ画像（多値）による点列配置に悪影響を与えるため、図２６に示すように点Ａ，Ｂの中点（すなわちエッジライン状の点）を中心とした半径ｄ＋Δの円を描き、これをセル領域に含ませるものとする。
即ち，初めに求めたセル領域Ｕ１と、Ａ，Ｂの中点における円領域をＵ２とした時、
新たなセル領域Ｕ＝Ｕ１＋Ｕ２ （７）
であらわされる。図２７はそのようにして得られセル領域を示す。図２５（Ｃ）と比べるセル領域の中抜けが消滅していることが分かる。
【００４２】
以上のようにして求められた点列とセル領域をベースに、エッジ画像（多値）を用いて点列作成を行う。処理のフローは図８に示したものと同じであるが、異なるところは主要エッジラインに沿って強制的に配置したセル領域を考慮することである。即ち、図２８に示すように、主要エッジラインに沿って得られた領域を既に決まったセル領域とし（ＳＴＥＰ９０）、セル領域以外のところに点列を配置する（ＳＴＥＰ９１）。具体的には、図８におけるイニシャライズ（ＳＴＥＰ３１）で、P（x,y）をエッジラインに沿ったセル領域にイニシャライズしておく。
Ｐ（ｘ，ｙ）＝１ ｘ、ｙがＵに含まれる時
＝０ それ以外 （８）
【００４３】
図２９はこのようにして得られた点列を示す。主要エッジラインの周りに配置された点列と、図８のフローにより求められた点列を合成したものである。両者を合わせて最終的な点列が構成され、かかる点列に基づくボロノイ図が描かれる。同図（Ｂ）はかかる点列をベースにボロノイ多角形を求め、その母点位置の画像データで多角形の内部を塗りつぶしたものである。図２１（Ｅ）と比較すると、画像のエッジがボロノイ多角形の一辺と重なっており、エッジにおけるギザギザ模様が無くなり、エッジを考慮した処理となっていることが分かる。
【００４４】
図３０は、図６（Ａ）の画像に対して処理したもので、エッジ画像（多値）は図６（Ｂ）、主要エッジラインは図６（Ｃ）を用いてしょりされたものである。図３０（Ａ）は、主要エッジラインの周りに配置した点列を、同図（Ｂ）はそれらの点列に対するセル領域を示す。同図（Ｃ）は、合成された最終的な点列を、同図（Ｄ）にかかる点列に基づくボロノイ図を示す。同図（Ｅ）はこのボロノイ多角形の母点位置の画像データで多角形の内部を塗りつぶした画像を示す。画像のエッジがボロノイ多角形の一辺と重なっており、エッジを考慮した処理となっていることが分かる。
【００４５】
以上のように、点列作成工程を、主要エッジラインに沿って母点を配置する手段と、多値エッジ情報に応じてセルサイズと母点を決定する手段とから構成することにより、分散性のよう点列を得ることが出来、作成されるボロノイ多角形の一辺を画像のエッジと重ねることが出来、画像の輪郭情報が考慮された高画質な出力画像を得ることが出来たものである。
【００４６】
一方、主要エッジラインに沿って母点を配置する手段と、多値エッジ情報に応じてセルサイズと母点を決定する手段とを別々に行うため、点列の分散性が損なわれることがある。図３１はその説明図で、主要エッジラインに沿って配列された点８４とセル８５に対して、新たにエッジ画像（多値）に基づき作成されたセル４６（斜線部分）が、セル８４を避けて形成されるため歪な形状を示す。その結果セル４６の重心位置がセル８５の領域内に入り込み点８４に接近し、点列の分散性が悪くなるということが生じる。この現象はまれに起こりその近傍の最終画質が劣化する。
【００４７】
この問題を回避するため、図３２に示すように、先ず全点列からボロノイ図を作成し（ＳＴＥＰ９２）、ボロノイ多角形の重心位置を求め（ＳＴＥＰ９３）、主要エッジの周りの点列以外の点列をこの重心位置で置き換える（ＳＴＥＰ９４）。通常、ボロノイ多角形の重心位置は、点列の分散性が良ければ母点の位置からあまり移動しない。しかしながら極端に接近した母点は、それぞれの重心位置と大きくずれる。
【００４８】
図３３（Ａ）は主要エッジライン近傍の点列配置とボロノイ多角形を示したものである。主要エッジラインの周りの点列を△で示し、それ以外の点列を●で示す。点列の移動は●の点列のみに行う。○はボロノイ多角形の重心位置を示す。点列の変換は●の点列に対しておこなわれ、重心移動後の点列は○となる。移動の結果、新たな点列が出来上がり、かかる点列によるボロノイ図形を同図（Ｂ）に示す。移動により接近しすぎていた点列は多少離れ、点列の分散の一様性が向上する事が分かる。
【００４９】
以上説明したように、本発明は入力画像データの空間周波数特性に応じた点列配置を行い、ブルーノイズ特性を示す分散性の良い点列を構成することが出来，更に、画像のエッジとボロノイ多角形の辺が重なるようにし、高品質なボロノイ画像を生成することが出来たものある。これをベースにNPR（Non-Photo Realistic）な様々な画像を生成し出力する事が出来る。本発明では、演算負荷の多い部分は専用ハードウェアやＬＳＩ、ＧＰＵ（Ｇｒａｐｈｉｃ Ｐｒｏｃｅｓｓｏｒ Ｕｎｉｔ）で処理することにより処理の高速化が図れ、画像読み取り後速やかに画像出力が出来る。なお、本発明は、複数の機器（例えばコンピュータ、インタフェイス機器、リーダ、プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、ファクシミリ装置、制御装置など）に適用してもよい。
【００５０】
また、本発明の目的は、上記実施例の機能を実現するコンピュータプログラムを記録した記憶媒体をシステムまたは装置に供給し、そのシステムまたは装置のコンピュータ（CPUやMPU）が前記コンピュータプログラムを実行することでも達成される。この場合、記憶媒体から読み出されたソフトウェア自体が上記実施例の機能を実現することになり、そのコンピュータプログラムと、そのコンピュータプログラムを記憶する、コンピュータが読み取り可能な記憶媒体は本発明を構成する。
【００５１】
また、前記コンピュータプログラムの実行により上記機能が実現されるだけではない。つまり、そのコンピュータプログラムの指示により、コンピュータ上で稼働するオペレーティングシステム(OS)および/または第一の、第二の、第三の、…プログラムなどが実際の処理の一部または全部を行い、それによって上記機能が実現される場合も含む。
【００５２】
また、前記コンピュータプログラムがコンピュータに接続された機能拡張カードやユニットなどのデバイスのメモリに書き込まれていてもよい。つまり、そのコンピュータプログラムの指示により、第一の、第二の、第三の、…デバイスのCPUなどが実際の処理の一部または全部を行い、それによって上記機能が実現される場合も含む。
【００５３】
本発明を前記記憶媒体に適用する場合、その記憶媒体には、先に説明したフローチャートに対応または関連するコンピュータプログラムが格納される。
【産業上の利用可能性】
【００５４】
本発明は、入力画像データを変形加工し、NPR（Non-Photo Realistic）な画像を生成し出力する装置において、出力画像に付加価値を与え、プリントサービスやフォトサービス、フォトアルバム等に利用可能である。
【符号の説明】
【００５５】
１ スキャナー、 ２ プリンタ、 ３ コントローラ、 ４ ＲＯＭ、 ５ ＲＡＭ、 6 ハードディスク、 ７ ＣＰＵ， ８ ディスプレイ、 ９ キーボード、 １０ 通信機能、 １８ コリメータレンズ、 １９ 結像レンズ、 ２０ 感光ドラム
【特許請求の範囲】
【請求項１】
入力画像データを変形加工し、NPR（Non-Photo Realistic）な画像を生成し出力する画像処理装置において、該画像処理装置は、
１．エッジ情報抽出工程
２．点列作成工程
３．ボロノイ・ダイアグラム作成工程
から構成され、
前記エッジ情報抽出工程はエッジ抽出フィルタによりエッジ画像を取得する手段からなり、
前記点列作成工程は、画像のエッジ情報に基づき母点を配置する手段からなり、
前記ボロノイ・ダイアグラム作成工程は、該母点点列を入力点としたボロノイ・ダイアグラムを作成する手段からなることを特徴とする画像処理装置。
【請求項２】
前記エッジ情報抽出工程はエッジ抽出フィルタによりエッジ情報を取得する手段と、主要エッジラインを取得する手段とからなり、
前記点列作成工程は、該主要エッジラインに沿って母点を配置する手段と、該エッジ情報に応じたセルサイズと母点を決定する手段とからなる事を特徴とする特許請求項１に記載された画像処理装置。
【請求項３】
前記主要エッジラインに沿って母点を配置する手段は、エッジラインからほぼ等距離の位置に母点を配置し、且つその母点を取り囲む領域を決定する手段からなり、前記エッジ情報に応じたセルサイズと母点を決定する手段は、既に決定された母点の周りの領域を除く画像領域を画素のデータの累積値が一定の値になるまで探索することでセルの領域を求め、かかるセルの領域の重心点を母点とする点列を決定する手段、
とからなる事を特徴とする特許請求項２に記載された画像処理装置。
【請求項４】
前記ボロノイ・ダイアグラム作成工程は、前記エッジラインからほぼ等距離の位置に置かれた母点と、前記セルの領域の重心からなる母点の両者を点列とするボロノイ多角形を作成する工程と、前記セル領域の母点を該母点を内包するボロノイ多角形の重心の位置に移動する工程、
とからなる事を特徴とする特許請求項３に記載された画像処理装置。
【請求項１】
入力画像データを変形加工し、NPR（Non-Photo Realistic）な画像を生成し出力する画像処理装置において、該画像処理装置は、
１．エッジ情報抽出工程
２．点列作成工程
３．ボロノイ・ダイアグラム作成工程
から構成され、
前記エッジ情報抽出工程はエッジ抽出フィルタによりエッジ画像を取得する手段からなり、
前記点列作成工程は、画像のエッジ情報に基づき母点を配置する手段からなり、
前記ボロノイ・ダイアグラム作成工程は、該母点点列を入力点としたボロノイ・ダイアグラムを作成する手段からなることを特徴とする画像処理装置。
【請求項２】
前記エッジ情報抽出工程はエッジ抽出フィルタによりエッジ情報を取得する手段と、主要エッジラインを取得する手段とからなり、
前記点列作成工程は、該主要エッジラインに沿って母点を配置する手段と、該エッジ情報に応じたセルサイズと母点を決定する手段とからなる事を特徴とする特許請求項１に記載された画像処理装置。
【請求項３】
前記主要エッジラインに沿って母点を配置する手段は、エッジラインからほぼ等距離の位置に母点を配置し、且つその母点を取り囲む領域を決定する手段からなり、前記エッジ情報に応じたセルサイズと母点を決定する手段は、既に決定された母点の周りの領域を除く画像領域を画素のデータの累積値が一定の値になるまで探索することでセルの領域を求め、かかるセルの領域の重心点を母点とする点列を決定する手段、
とからなる事を特徴とする特許請求項２に記載された画像処理装置。
【請求項４】
前記ボロノイ・ダイアグラム作成工程は、前記エッジラインからほぼ等距離の位置に置かれた母点と、前記セルの領域の重心からなる母点の両者を点列とするボロノイ多角形を作成する工程と、前記セル領域の母点を該母点を内包するボロノイ多角形の重心の位置に移動する工程、
とからなる事を特徴とする特許請求項３に記載された画像処理装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１７】
【図１８】
【図１９】
【図２０】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図３２】
【図３３】
【図６】
【図１６】
【図２１】
【図２９】
【図３０】
【図３１】
【図２】
【図３】
【図４】
【図５】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１７】
【図１８】
【図１９】
【図２０】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図３２】
【図３３】
【図６】
【図１６】
【図２１】
【図２９】
【図３０】
【図３１】
【公開番号】特開２０１２−１７４１５９（Ｐ２０１２−１７４１５９Ａ）
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願番号】特願２０１１−３７９２３（Ｐ２０１１−３７９２３）
【出願日】平成２３年２月２４日（２０１１．２．２４）
【出願人】（７１１００１８９３）
【Ｆターム（参考）】
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願日】平成２３年２月２４日（２０１１．２．２４）
【出願人】（７１１００１８９３）
【Ｆターム（参考）】
[ Back to top ]