(57)【特許請求の範囲】
【請求項１】
画像データに応じて網点の重心と黒化数を決定する画像処理装置であって、
処理対象の網点が含む画素の画像データから、前記処理対象の網点の重心を計算する重心の計算手段と、
前記処理対象の網点が含む画素の画像データから、前記処理対象の網点が含む、黒画素にすべき画素の数を示す黒化数を計算する黒化数の計算手段と、
前記処理対象の網点に隣接する画素を前記処理対象の網点に追加する網点の拡大手段と、
前記黒化数が所定数に達するまで、前記重心の計算手段、前記黒化数の計算手段および前記網点の拡大手段に処理を繰り返させて、前記処理対象の網点の重心と黒化数を決定する決定手段とを有することを特徴とする画像処理装置。
【請求項２】
前記網点の拡大手段は、前記網点のサイズが予め設定された第一のサイズよりも小さい場合、または、前記黒化数が前記所定数よりも小さく、かつ、前記網点のサイズが予め設定された、前記第一のサイズよりも大きい第二のサイズよりも小さい場合、前記網点に含まれず前記網点の重心に最も近い画素を前記網点に追加することを特徴とする請求項1に記載された画像処理装置。
【請求項３】
前記網点の拡大手段は、画像データのシャドウ域において前記網点のサイズを前記第一のサイズまで拡大し、画像データのハイライト域において前記網点のサイズを前記第二のサイズまで拡大し、前記シャドウ域と前記ハイライト域の中間の濃度域において前記網点のサイズを前記第一のサイズよりも大きく前記第二のサイズよりも小さいサイズに拡大することを特徴とする請求項2に記載された画像処理装置。
【請求項４】
さらに、前記第一のサイズ、前記第二のサイズ、および、前記所定数を取得する取得手段を有することを特徴とする請求項2または請求項3に記載された画像処理装置。
【請求項５】
さらに、前記第一のサイズに揺らぎを与える変動手段を有することを特徴とする請求項2から請求項4の何れか一項に記載された画像処理装置。
【請求項６】
さらに、前記重心を母点として、ハーフトーンスクリーンを多角形にボロノイ分割する分割手段と、
前記多角形の重心を成長中心として、前記黒化数に応じて前記多角形が含む画素を黒化して、前記多角形に関連する形状で網点を成長させる成長手段とを有することを特徴とする請求項1から請求項5の何れか一項に記載された画像処理装置。
【請求項７】
前記網点の拡大手段は、前記追加する画素の探索順が記載されたテーブルを参照して、前記網点を円状または矩形状に拡大することを特徴とする請求項1から請求項6の何れか一項に記載された画像処理装置。
【請求項８】
前記黒化数の計算手段は、前記網点が含む画素の数と、前記網点が含む画素の画像データの合計値を用いて、前記黒化数を計算することを特徴とする請求項1から請求項7の何れか一項に記載された画像処理装置。
【請求項９】
前記成長手段は、前記多角形の中点多角形に略相似な形状で網点を成長させることを特徴とする請求項6に記載された画像処理装置。
【請求項１０】
前記成長手段は、前記多角形の辺の長さと、前記辺の中点と前記多角形の重心の距離が所定の比率に達しない辺の中点は、前記中点多角形の頂点に採用しないことを特徴とする請求項9に記載された画像処理装置。
【請求項１１】
重心および黒化数の計算手段、網点の拡大手段、決定手段を有し、画像データに応じて網点の重心と黒化数を決定する画像処理装置の画像処理方法であって、
前記重心の計算手段が、処理対象の網点が含む画素の画像データから、前記処理対象の網点の重心を計算し、
前記黒化数の計算手段が、前記処理対象の網点が含む、黒画素にすべき画素の数を示す黒化数を計算し、
前記網点の拡大手段が、前記処理対象の網点に隣接する画素を前記処理対象の網点に追加し、
前記決定手段が、前記黒化数が所定数に達するまで、前記重心の計算手段、前記黒化数の計算手段および前記網点の拡大手段に処理を繰り返させて、前記処理対象の網点の重心と黒化数を決定することを特徴とする画像処理方法。
【請求項１２】
コンピュータを請求項1から請求項10の何れか一項に記載された画像処理装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハーフトーン処理に関する。
【背景技術】
【０００２】
光ビームを走査して、有機光導電体(OPC)やアモルファスシリコンなどの感光ドラムの一様に帯電された表層から電荷を除去する露光過程をもつ電子写真方式の印刷装置は非線形特性を有する。また、現像、転写、定着などの電子写真プロセスの複雑さも非線形特性の要因になる。
【０００３】
この非線形特性により、印刷ドットの間で干渉が生じる。例えば、独立した1ドットを印刷しようとしてもドットは記録され難く、数ドットのクラスタ状態になると確実にドットが記録される。また、ドット間の距離が小さいとトナーが移動してドットがつながることがある。言い換えれば、空間周波数の高周波特性が低下する。なお、インクジェット方式のように、インク滴をメディアに付着させてドットを記録するプロセスは、インクとメディアの間のミクロ現象はあるが、印刷ドットの間の干渉は生じ難く、確実にドットを記録することができる。
【０００４】
電子写真方式の印刷装置による印刷画像は、上記の電子写真プロセスの非線形特性により、空間周波数の変動に大きく影響される。電子写真プロセスにより中間調画像を形成する場合、非線形性を考慮して、網点方式を利用する。網点方式を利用すれば基本空間周波数が固定され、空間周波数の変動を受けずに、ドットを安定に記録することができる。例えば、網点の線数をN線/インチとすると、網点のピッチPは25.4/N[mm]になる。つまり、空間周波数は1/(2P)=N/(2×25.4)であり、基本空間周波数が固定されたことになる。従って、基本空間周波数において、常に、電子写真プロセスが安定化するように印刷装置を設計すれば、印刷画像を安定に形成することができる。例えば、1200dpiの印刷装置において200線/インチの網点スクリーンの基本空間周波数は4サイクル/mmである。つまり、4サイクル/mmの空間周波数において電子写真プロセスを安定化させれば、印刷装置の画像再現特性が向上する。
【０００５】
網点方式によるAM変調方式は、安定な画像再現特性が得られる。その反面、カラー印刷においてはCMYK各色のトナーを重ねることでモアレが発生し易い。モアレを抑えるには、色成分ごとにスクリーン角を変えて、色成分の間で生じるモアレビートを高周波側に追いやり、モアレが視覚的に目立たないようにする。例えば、Yのスクリーン角を30度、C、M、Kのスクリーン角を0または60度にして、色トナーの重なりによるモアレを抑制する。
【０００６】
また、ディジタルハーフトーン処理においては、ディジタル画像の解像度が離散的であるためスクリーン角を任意に取ることはできない。しかし、色成分ごとに最適かつ離散的なスクリーン角を選択すれば、モアレを抑制することができる。
【０００７】
ただし、スクリーン角を導入し最適化しても、モアレビートを高周波側に追いやるだけで、色成分の重なりによって生じる独特のパターンが残る。これが所謂ロゼッタパターンであり、高画質な画像を出力する場合の障害になる。とくに、高画質の写真画像を出力する場合、銀塩プロセスの写真のように滑らかな画質再現が求められ、ロゼッタパターンは大きな障害である。
【０００８】
別のアプローチとして、誤差拡散やブルーノイズマスクによるFM変調方式によって階調を再現する方法がある。FM変調方式は、印刷ドットの配置がランダムになり、階調性も良好で、色成分の重なりによるモアレもないため、インクジェット方式や熱転写方式などで広く採用される。しかし、FM変調方式は、ドット間隔が変化し、ドット間隔を自由にコントロールすることができない。例えば、濃度値が高くなるに連れてドットの間隔が徐々に縮まる。このため空間周波数特性が高周波数に及び、印刷装置の周波数特性の影響をもろに受ける。従って、空間周波数変動の影響を受け易い電子写真方式の印刷装置にFM変調方式は向かない。
【０００９】
【特許文献１】特開2004-338366公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は、良好な階調再現が得られるハーフトーン処理を実現することを目的とする。
【課題を解決するための手段】
【００１２】
本発明は、前記の目的を達成する一手段として、以下の構成を備える。
【００１３】
本発明にかかる画像処理は、処理対象の網点が含む画素の画像データから、前記処理対象の網点の重心を計算し、前記処理対象の網点が含む、黒画素にすべき画素の数を示す黒化数を計算し、前記処理対象の網点に隣接する画素を前記処理対象の網点に追加し、前記黒化数が所定数に達するまで、前記重心の計算、前記黒化数の計算および前記網点の拡大を繰り返して、前記処理対象の網点の重心と黒化数を決定することを特徴とする。
【発明の効果】
【００１５】
本発明によれば、良好な階調再現が得られるハーフトーン処理を実現することができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明にかかる実施例の画像処理を図面を参照して詳細に説明する。
【実施例１】
【００１７】
［装置の構成］
図1は実施例の画像処理装置の構成例を示すブロック図である。
【００１８】
スキャナ11と、電子写真方式のプリンタ12を有する複合機(MFP)10は、内蔵するコントローラ13によって、その機能が制御される。
【００１９】
コントローラ13のCPU17は、RAM15をワークメモリとして、ROM14やハードディスクドライブ(HDD)16に格納されたオペレーティングシステム(OS)や各種プログラムを実行する。HDD16は、制御プログラム、画像処理プログラムなどのプログラムや画像データを記憶する。また、画像メモリ21は、レンダリング用のページメモリである。なお、画像メモリ21は、RAM15に割り当ててもよいし、RAM15とは別個に設けてもよい。
【００２０】
CPU17は、表示部18にユーザインタフェイスを表示して、表示部18のソフトウェアキーや、操作パネル19のキーボードからユーザの指示を入力する。例えば、ユーザ指示がコピーを示す場合、スキャナ11によって読み取った原稿画像をプリンタ12によって印刷する（コピー機能）。
【００２１】
通信部20は、図には示さないが、公衆回線やネットワークに接続する通信インタフェイスである。CPU17は、ユーザ指示がファクシミリ送信を示す場合、スキャナ11によって読み取った原稿画像を、通信部20を制御してユーザが指定する相手先にファクシミリ送信する（ファクシミリ機能）。また、ユーザ指示がプッシュスキャンを示す場合、スキャナ11によって読み取った原稿画像を、通信部20を制御して指定のサーバ装置に送信する（プッシュスキャン機能）。また、通信部20がファクシミリ画像を受信した場合、CPU17は、受信画像をプリンタ12で印刷する（ファクシミリ機能）。また、通信部20が印刷ジョブを受信した場合、CPU17は、印刷ジョブに従いプリンタ12で画像を印刷する（プリンタ機能）。また、通信部20がプルスキャンジョブを受信した場合、CPU17は、スキャンジョブに従いスキャナ11によって読み取った原稿画像を指定のサーバ装置やクライアント装置に送信する（プルスキャン機能）。
【００２２】
●光学系の構成
図2はプリンタ12の光学系の構成例を示す図である。
【００２３】
半導体レーザ素子などのビーム光源27から出力された光ビーム26は、球面系あるいはアナモフィック光学系によるコリメータレンズ28を介して回転多面鏡25の反射面に入射する。回転多面鏡25の回転により偏向された光ビーム26は、f-θレンズなどの結像レンズ29を介して、回転する感光ドラム30上に結像し、感光ドラム30上を光走査する。
【００２４】
●ドットジェネレータ
図3はハーフトーンスクリーンを生成するドットジェネレータの構成例を示すブロック図である。なお、ドットジェネレータは、コントローラ13の一部として構成される。なお、以下では、本実施例のハーフトーンスクリーンをクラスタハーフトーンスクリーン(cluster halftone screen: CHS)と呼ぶことにする。
【００２５】
同期信号入力部35は、同期信号として、プリンタ12から1ラインの走査タイミングを示す水平同期信号Hsync、一頁の走査タイミングを示す垂直同期信号Vsync、および、画素クロックVclockを入力する。これら同期信号は、画像メモリ21、画像処理部22、レーザドライバ34、光源27に供給され、画像形成タイミングを制御する。
【００２６】
画像処理部22は、画像メモリ21から画像を入力し、後述するVDSを用いるハーフトーン処理を行う。レーザドライバ34は、画像処理部22が出力する二値信号に従いビーム光源27を駆動して、ビーム光源27の発光を制御する。
【００２７】
［CHSの作成］
CHSの生成処理を概略分割すると次のようになる。
第一のステップ：網点の重心と黒化する画素の数（以下、黒化数）を求める（重心と黒化数の決定）、
第二のステップ：網点の重心を母点として、スクリーンをボロノイ(Voronoi)分割し、ボロノイ多角形を求める（ボロノイ分割）、
第三のステップ：ボロノイ多角形の重心を網点の成長中心として、黒化数分の画素を黒化する（網点の成長）。
【００２８】
●重心と黒化数の決定
図4はCHSの生成処理における重心と黒化数の決定を説明するフローチャートで、画像処理部22が実行する処理である。
【００２９】
画像処理部22は、図5に示すユーザインタフェイス(UI)を表示部18に表示して、CHSを作成するための作成パラメータを取得する(S30)。本実施例では、画像データの濃度に合わせて網点の面積を成長する（黒化する）ことで階調を表現する。網点のサイズを網点サイズ、網点内の最小ドット（例えばプリンタ12が形成可能な最小ドットサイズ）をセルと呼ぶことにする。ユーザは、図5のUIを操作して、最小網点サイズCmin、最小網点サイズの変動幅N、最大網点サイズCmax、クラスタサイズの各テキストボックス50〜53に数値を設定し、OKボタンを押す。
【００３０】
最小網点サイズCminと最大網点サイズCmaxは、網点サイズを規制し、網点の黒化の一次元方向のサイズを表すことにする。最小網点サイズの変動幅Nは、網点サイズに与える揺らぎの大きさを決定する数値である。また、クラスタサイズMは、階調再現における中間濃度を表現する場合に、クラスタ化する黒化セルの数を表す。画像処理部22は、これら四つのパラメータを取得し、CHSの生成を開始する。
【００３１】
次に、画像処理部22は、画像の左上の画素データを入力する(S31)。画素データを下式で表すと、image(1, 1)を入力することになる。
image(x, y)            …(1)
ここで、1≦x≦Xsize、1≦y≦Ysize、
Xsizeは画像の主走査方向（X方向）の画素数、
Ysizeは画像の副走査方向（Y方向）の画素数
【００３２】
画素データがRGB値の場合、画像処理部22は、式(2)または(2')を用いて、画素データImage(x, y)を濃度値YMCに変換する。なお、何れかの色成分の濃度値を表す場合はDとする。なお、後述するステップS41の処理も同様に輝度値から濃度値への変換を行う。
Y = 1 - B
M = 1 - G      …(2)
C = 1 - R
Y = log10(1/B)
M = log10(1/G)      …(2')
C = log10(1/R)
【００３３】
次に、画像処理部22は、処理の開始アドレスを検出する(S32)。つまり、印刷すべき画像のサイズに対応するビットマップ（深さ1ビット）テーブルをラスタ順に参照して、最初に値が‘0’の画素位置を開始アドレスにする。ビットマップテーブルは、下式の値を有し、処理の開始時点で各画素値が‘0’に初期化されている。従って、image(1, 1)を入力した直後は、PixData(1, 1)が開始アドレスになる。また、検出した開始アドレスに対応するPixData(x, y)には‘1’を設定する。
処理済画素の場合、PixData(x, y) = ‘1’
未処理画素の場合、PixData(x, y) = ‘0’      …(3)
ここで、1≦x≦Xsize、1≦y≦Ysize
【００３４】
次に、画像処理部22は、最小網点サイズCminに揺ぎを与える(S33)。図6は最小網点サイズCminに揺らぎを与える処理を示すフローチャートである。まず、下式により、乱数を発生し、最小網点サイズの変動幅Nに応じた、最小網点サイズに加算する変動値vを計算する(S45)。
v ＝ int{N・rand() + 0.5}      …(4)
ここで、Nは自然数、
rand()は0＜r＜1の乱数を発生する関数、
int()は小数点以下を切り捨てる関数
【００３５】
式(4)によれば、変動値vとして0, 1, 2, …, Nの何れかが得られるが、最小網点サイズの変動幅N=1の場合、v=0またはv=1である。画像処理部22は、下式により、最小網点サイズCminに揺らぎを与える(S46)。
Cmin' = Cmin + v      …(5)
【００３６】
次に、画像処理部22は、網点の重心を計算する(S34)。なお、image(1, 1)を入力した直後は(1, 1)が重心である。そして、網点サイズCが最小網点サイズCmin'未満か否かを判定し(S35)、C＜Cmin'であれば網点を拡大する。つまり、網点の重心に最も近い画素（近傍画素）で、PixData(x, y)=‘0’の画素を網点に加え(S40)、網点に加えた画素の画素データを読み込み(S41)、処理を重心の計算(S34)に戻す。なお、網点に加えた画素に対応するPixData(x, y)には‘1’を設定する。
【００３７】
そして、画像処理部22は、C=Cmin'になるまで、ステップS34〜S41の処理を繰り返す。なお、画像処理部22は、X方向、Y方向それぞれについてC=Cmin'になるまで網点の拡大を行う。
【００３８】
拡大処理による網点の累積濃度値SumD（濃度値の合計）は下式で表される。
SumD = ΣDi      …(6)
ここで、Diはi番目に網点に加えられた画素の濃度値D
【００３９】
また、拡大後の網点の重心は下式で計算する(S34)。なお、重心は、網点に含まれる高濃度の画素に近い位置になる。
Gx' = (xa - Gx)・Da/(SumD0 + Da) + Gx
Gy' = (ya - Gx)・Da/(SumD0 + Da) + Gy      …(7)
ここで、(Gx', Gy')は拡大後の網点の重心位置、
(Gx, Gy)は拡大前の網点の重心位置、
SumD0は拡大前の網点の累積濃度値、
(xa, ya)は追加画素の位置、
Daは追加画素の濃度値
【００４０】
網点サイズCが最小網点サイズCmin'に達すると、画像処理部22は、下式により、黒化する画素数（以下、黒化数）NBを計算する(S36)。
NB = SumD/(Dmax×P)×P = SumD/Dmax      …(8)
ここで、Pは網点に加えた画素数
Dmaxは一画素当りの最大濃度値（例えば255）
【００４１】
画素サイズとセルサイズが等しい場合、一つの網点で表現可能な階調数は、網点に加えた画素数Pに比例する。一方、網点の累積濃度値SumDの最大値は、一画素の最大濃度値Dmaxから、Dmax×Pである。従って、ある網点における黒化数NBは、累積濃度値と累積濃度値の最大値の比SumD/(Dmax×P)に画素数Pを乗算した値になる。
【００４２】
次に、画像処理部22は、黒化数NBとクラスタサイズMを比較して(S37)、黒化数がクラスタサイズ以上（NB≧M）ならば、その網点の重心と黒化数を決定する(S39)。一方、NB＜Mならば、網点サイズCと最大網点サイズCmaxを比較して(S38)、C=Cmaxならば網点を決定する(S39)。また、C＜Cmaxの場合は、さらに網点を拡大するために処理をステップS40に戻す。なお、ステップS38の判定は、X方向、Y方向それぞれについてC=Cmaxになるまで処理をステップS40に戻す。
【００４３】
処理がステップS40に戻った場合、網点の重心に最も近い画素で、PixData(x, y)=‘0’の画素を網点に加え(S40)、網点に加えた画素の画素データを読み込み(S41)、処理を網点の重心計算(S34)に戻す。その後、既にC＞Cmin'であるから、処理は黒化数NBの計算(S36)、黒化数NBとクラスタサイズMの比較(S37)に進む。
【００４４】
NB≧MまたはC=Cmaxになると、重心と黒化数の決定(S39)の後、全画素の処理が終了したか否かを判定し(S42)、未了の場合は処理をステップS31に戻す。なお、ビットマップテーブルに値‘0’の画素がなければ、全画素の処理が終了したと判定すればよい。
【００４５】
図7はCHSの作成によって得られる網点41と、網点の重心40を示す図である。重心に最も近い画素を網点に加えるように網点を拡大すると、拡大結果の網点は円に近い形状になる。
【００４６】
重心に近い画素を選択してセルを拡大すると、重心と網点の距離sは下式で示される。
s = √{(Gx - x)2 + (Gy - y)2}      …(9)
ここで、(Gx, Gy)は重心、
(x, y)は画素の座標
【００４７】
つまり、画像処理部22は、ステップS40で距離sが最小の画素（ただし、PixData=‘0’の画素、以下、追加画素）を選択する。
【００４８】
図8は追加画素を検索するためのテーブルを示す図である。
【００４９】
図8に示すテーブルには、上段に探索順を示す数値が、下段に網点の重心からの変位量を表す二桁の数値が記録されている。つまり、探索順が「1」の画素（変位量00）を網点の重心(Xg, Yg)とすると、追加画素の候補は探索順が「2」の画素（変位量10）である。従って、次画素のアドレスは(Xg+1, Yg+0)である。探索順が「2」の画素のPixData、つまり、PixData(Xg+1, Yg+0)=‘0’ならば、探索順が「2」の画素を追加画素にする。もし、PixData(Xg+1, Yg+0)=‘1’ならば、探索順が「2」の画素をパスして、探索順が「3」の画素を調べる。
【００５０】
このようなテーブルを使用すれば、網点の重心に最も近い追加画素の候補を短時間に探索することができる。
【００５１】
図9はCHSの作成によって得られる網点サイズを概念的に示す図である。実際の網点形状は、図7に示すような円の一部が欠けた形状になるが、図9には網点サイズを模式的に示す。
【００５２】
画像データのシャドウ域においては、濃度が小さくなる（ハイライトに向かう)と、最小網点サイズCmin'の網点内で黒化数NB（黒化面積）が減少する。画像データの中間濃度域においては、濃度が小さくなるに従い、黒化面積は一定（クラスタサイズM）で網点サイズCが拡大する。画像データのハイライト域においては、濃度が小さくなるに従い、最大網点サイズCmaxの網点内で黒化面積が減少する。
【００５３】
図10は画像データの濃度と網点の重心の関係を説明する図である。図10(a)に示すグラデーションの画像データに対して、シャドウ域では網点サイズがCmin'に固定されるため、揺らぎ分を除けば重心はほぼ等間隔に並ぶ。中間濃度域において、網点サイズが拡大するため、重心の間隔が徐々に広くなる。ハイライト域では網点サイズがCmaxに固定されるため、重心はほぼ等間隔に並ぶ。
【００５４】
図11は図10に示す矩形領域54の網点形状と重心を示す図である。中間濃度域おいて、ハイライト域に向かって網点サイズが大きくなることが分かる。
【００５５】
図12は最小網点サイズCminに揺らぎを与えない場合の画像データの濃度と網点の重心の関係を説明する図である。図12(a)に示す、図10(a)と同じグラデーションの画像データに対して、網点の間隔の変化はほぼ図10(b)と同じだが、図12(b)に示すように、重心の位置に周期的なパターンが発生し、網点の配置は充分にランダムとは言えない。上記の揺らぎを与えることで、図10に示すように、網点の周期的な配置が消失し、モアレを生じない網点パターンを生成することが可能になる。
【００５６】
●ボロノイ分割
図13はCHSの生成処理におけるボロノイ分割を説明するフローチャートで、画像処理部22が実行する処理である。
【００５７】
画像処理部22は、決定した重心の位置を入力し(S60)、重心を母点としてスクリーンをボロノイ分割し、ボロノイ多角形を生成する(S61)。
【００５８】
図14はボロノイ多角形の生成を説明する図である。図14(a)は母点となる重心を示し、図14(b)は母点を結んだドロネ(Delaunay)三角形71を示し、図14(c)は母点とボロノイ多角形を示している。
【００５９】
母点Piに対するボロノイ多角形は次式に示す点V(Pi)の集合であり、ボロノイ多角形は母点Piの勢力圏を現す。
V(Pi) = {P|d(P, Pi) ＜ d(P, Pj), ∀j≠i}      …(10)
ここで、PjはPiに隣接する母点、
d(P, Pi)は母点Pと母点Piの距離、
d(P, Pj)は母点Pと母点Pjの距離
【００６０】
ボロノイ多角形の辺（ボロノイ境界）は、ドロネ三角形の外心点を結ぶ線分である。また、ドロネ三角形は、隣接する母点間を結ぶ線分を辺としてもち、母点に対して一義的に決まる。従って、ボロノイ多角形も一義的に決まる。ドロネ三角形の外心点(Gx, Gy)は次式で表される。
Gx = {X02(Y1-Y2) + X12(Y2-Y0) + X22(Y0-Y1) - (Y0-Y1)(Y1-Y2)(Y2-Y0)}/L
Gy = -Gx(X2-X1)/(Y2-Y1) + (X2-X1)(X1+X2)/2/(Y2-Y1) + (Y1+Y2)/2  …(11)
ここで、L = 2{X0(Y1-Y2) + X1(Y2-Y0) + X2(Y0-Y1)}、
(X0, Y0)、(X1, Y1)、(X2, Y2)はドロネ三角形の頂点座標
【００６１】
このように、一つの母点を内部にもつボロノイ多角形を形成し、ボロノイ多角形を対応する網点の形状にする。図14(c)はボロノイ多角形（網点形状）を示す図で、これらボロノイ多角形が網点の成長領域である。ボロノイ多角形は、ランダム配置の格子点に対して視覚的に滑らかな網点形状を決定する。もし、正方網点格子点列を使用し、網点面積を可変にして画像の濃度に応じた網点密度の設定（密度変調）を行えば、網点内部をうまく充填する（黒ドットを成長させる）ことができない。ボロノイ多角形を使用すれば、視覚的にも違和感なく、網点内部を充填することができる。
【００６２】
図15と図16はボロノイ分割によって得られるボロノイ多角形の重心を示す図である。図15に示す重心の配置は、比較的分散性がよい状態にある。一方、図16に示す重心の配置は、分散性がよいとは言えない状態にある。図16に示す分散性が充分ではない重心の配置が得られた場合、重心ボロノイ図により、重心の配置を分散させることが望ましい。
【００６３】
重心ボロノイ図は、母点をボロノイ多角形の重心に移動して、再び、ボロノイ分割を行うCVT(centroidal Voronoi tessellation)と呼ばれる処理によって得られる。この処理の繰り返しは、Lloydアルゴリズムと呼ばれ、S.Lloyd「Least Square Quantization in PCM」IEEE Trans. Inform. Theory, Vol. 28, pp.129-137, 1982に詳細が記載されている。
【００６４】
図16に示す重心を母点としてCVTを行えば、CVT後の重心は図15に示すような分散性のよい状態になる。つまり、図13のステップS61において、CVTを実行してもよい。ただし、図7に示すような、重心に最も近い画素を網点拡大の画素候補として網点を拡大する方法の場合、重心の移動は少なく、CVTを行わなくても充分分散性のよい重心が得られる。
【００６５】
●網点の成長
図17はCHSの生成処理における網点の成長を説明するフローチャートで、画像処理部22が実行する処理である。
【００６６】
画像処理部22は、ボロノイ多角形の重心の位置と黒化数NBを入力し(S73)、重心を網点の成長中心として黒化数NBの画素を含む、ボロノイ多角形に関連する（この場合は略相似の）ハーフトーン多角形を形成する(S74)。そして、ハーフトーン多角形内の画素を黒化する（黒で塗り潰す）(S75)。
【００６７】
図18と図19は網点を拡大した様子を示す図で、図18は網点面積率が30%の網点を、図19は網点面積率が75％の網点を示している。
【００６８】
黒化数NBとボロノイ多角形の面積Sを画素数で表すと、黒化する画素の面積率ηは下式で表される。
η = NB/S      …(12)
【００６９】
つまり、√ηの比率でボロノイ多角形を相似形に縮小したハーフトーン多角形を設定し、ハーフトーン多角形に含まれる画素を黒化すればよい。
【００７０】
図20は図10に示したグラデーション画像に対する重心から得られるボロノイ多角形と重心を示す図である。図21はCHSによって最終的に形成される網点画像例を示す図である。図21(a)は8ビットの輝度データで128〜255のグラデーション画像に対する網点画像を、図21(b)は8ビットの輝度データで0〜255のグラデーション画像に対する網点画像を示している。
【００７１】
また、図22は入力画像（建物の写真）を、図23は図22の画像に対して重心と黒化数の決定（第一のステップ）で得られる重心を、図24は網点の成長（第三のステップ）で得られるCHSを用いた網点画像をそれぞれ示す図である。
【００７２】
●パラメータによる網点の変化
図25はステップS30で取得するCHSの作成パラメータを変化させた場合の網点の変化を示す図である。
【００７３】
図25(a)は8ビットの輝度データで128〜255のグラデーション画像（原画）を示す。図25(b)は最小網点サイズCminを4×4画素、最大網点サイズCmaxを12×12画素、クラスタサイズM=4、最小網点サイズの変動幅N=1とした場合の網点画像を示す。図25(c)は最小網点サイズCminだけを6×6画素とした場合の網点画像を示す。図25(d)は、さらに、クラスタサイズM=8とし場合の網点画像を示す。
【００７４】
図25から分かるように、最小網点サイズCminを大きくすると線数が低くなり、クラスタサイズMを大きくすると中間濃度の網点サイズが大きくなり線数が低下する。このように、プリンタ12のMTF特性に合わせた線数になるようにパラメータを設定することで、最も安定し、かつ、高画質に画像を印刷することができる。
【００７５】
クラスタハーフトーンスクリーン(CHS)による疑似中間調再現は、網点をベースにするAM変調方式と、誤差拡散やブルーノイズを利用するFM変調方式の中間に位置する。前述したように、AM変調方式は、固定線数の網点で中間調を再現するため、電子写真方式において最も安定に階調を再現することができるが、網点の周期性により、画像の周期性をもつパターンや色の間でモアレが生じる。また、FM変調方式は、電子写真方式の非線形的な特性により、安定して中間調を再現することができない。上述した実施例によれば、CHSを利用することで、AM・FM変調方式の問題を解決し、電子写真方式の複写機、MFP、オフィス用プリンタなどにおいて、モアレのない高画質な印刷が可能になる。
【実施例２】
【００７６】
以下、本発明にかかる実施例2の画像処理を説明する。なお、実施例2において、実施例1と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【００７７】
［網点の拡大］
図26は実施例2における網点の拡大を説明する図で、網点を矩形状に拡大する例を示している。図27は追加画素を検索するためのテーブルを示す図である。
【００７８】
図27に示すテーブルには、上段に探索順を示す数値が、下段に網点の重心からの変位量を表す二桁の数値が記録されている。つまり、探索順が「1」の画素（変位量00）を網点の重心(Xg, Yg)とすると、追加画素の候補は探索順が「2」の画素（変位量10）である。従って、次画素のアドレスは(Xg+1, Yg+0)である。探索順が「2」の画素のPixData、つまり、PixData(Xg+1, Yg+0)=‘0’ならば、探索順が「2」の画素を追加画素にする。もし、PixData(Xg+1, Yg+0)=‘1’ならば、探索順が「2」の画素をパスして、探索順が「3」の画素を調べる。
【００７９】
探索順が「3」の画素は、図8に示したテーブルでは重心の画素の真下にあるが、図27に示すテーブルでは重心の右下にくる。また、探索順が「4」の画素は、図8に示したテーブルでは重心の画素の右下にあるが、図27に示すテーブルでは重心の真下にくる。さらに、探索順が「5」の画素は、図8に示したテーブルでは重心の画素の左下にあるが、図27に示すテーブルでは重心の二つ右（探索順が「2」の画素の右）にくる。つまり、探索順の設定により、網点の形状を円状にするか、矩形状にするかを制御することができる。
【００８１】
このような矩形状に網点を拡大する場合、図27に示すテーブルの作成が容易になり、システムのデバッグが容易である。網点形状は、初期は矩形状になるが、最終的にはボロノイ分割によって得られるボロノイ多角形になるため、初期の矩形状の影響は少ない。ただし、網点形状の変化により、初期の重心とボロノイ多角形の重心には多少の差異があり、重心の配置に充分な分散性が得られない場合がある。その場合、前述したCVTを行うことにより、分散性を得ればよい。
【００８２】
［ハーフトーン多角形の形状］
図28はハーフトーン多角形の形成を説明する図である。実施例1では、ボロノイ多角形に関連するハーフトーン多角形として、ボロノイ多角形に略相似なハーフトーン多角形を形成する例を説明した。実施例2では、図28に示すように、ボロノイ多角形に関連する多角形として、ボロノイ多角形の各辺の中点を結ぶ多角形（中点多角形）に略相似なハーフトーン多角形を形成する。なお、ボロノイ多角形と中点多角形の重心は一致する。
【００８３】
図28に示す多角形ABCDEがボロノイ多角形とすると、辺AB、BC、CD、DE、EAの各中点を結ぶ中点多角形H1H2H3H4H5に略相似なハーフトーン多角形を決定する。ハーフトーン多角形は、ボロノイ多角形ABCDEからはみ出さないように決定されるから、中点多角形よりも大きくなると、例えば、多角形M1M2M3M4M5M6M7M8M9M10のように成長する。
【００８４】
実施例1のボロノイ多角形に略相似なハーフトーン多角形を利用する場合、網点面積率が大きいシャドウ域では、図19に示すように、ボロノイ多角形の辺に沿った細い領域として白ドットが形成される。このため、網点面積率が100%に近いシャドウ域で、階調再現が不安定になり易い。これに対して、実施例2の中点多角形に略相似なハーフトーン多角形は、ボロノイ多角形の頂点A、B、C、D、Eを核とする多角形状の白ドットを形成し、網点面積率が100%に近いシャドウ域の安定性を増すことができる。
【００８５】
図29はボロノイ多角形に短い辺がある場合のハーフトーン多角形の形成を示す図である。ボロノイ多角形ABCDEFGの七角形からなるとし、辺BCとGAが他辺に比べて極端に短いとする。例えば、ある辺の長さLと、当該辺の中点と重心Gを結ぶ線分Vが次の関係を満たす場合、辺BCの中点を、前記中点多角形の頂点に使用しないことにする。
L/V ＜ α      …(13)
ここで、所定の比率αは1/4くらいの値が好ましい
【００８６】
図29において、辺BC、GAの長さLと、辺BC、GAの中点と重心Gを結ぶ線分Vを比較すると、L≪Vであり、辺BC、GAの中点を使用しない。
【００８７】
図30は中点多角形に略相似なハーフトーン多角形の形状を示す図で、図30(a)は網点面積率が40%、図30(b)は網点面積率80%の状態を表している。図30から分かるように、シャドウ域においても多角形状（少なくとも三角形状）の白ドットが生成され、安定に階調を再現することができる。
【００８８】
［他の実施例］
なお、本発明は、複数の機器（例えばコンピュータ、インタフェイス機器、リーダ、プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、ファクシミリ装置、制御装置など）に適用してもよい。
【００８９】
また、本発明の目的は、上記実施例の機能を実現するコンピュータプログラムを記録した記憶媒体をシステムまたは装置に供給し、そのシステムまたは装置のコンピュータ（CPUやMPU）が前記コンピュータプログラムを実行することでも達成される。この場合、記憶媒体から読み出されたソフトウェア自体が上記実施例の機能を実現することになり、そのコンピュータプログラムと、そのコンピュータプログラムを記憶する、コンピュータが読み取り可能な記憶媒体は本発明を構成する。
【００９０】
また、前記コンピュータプログラムの実行により上記機能が実現されるだけではない。つまり、そのコンピュータプログラムの指示により、コンピュータ上で稼働するオペレーティングシステム(OS)および/または第一の、第二の、第三の、…プログラムなどが実際の処理の一部または全部を行い、それによって上記機能が実現される場合も含む。
【００９１】
また、前記コンピュータプログラムがコンピュータに接続された機能拡張カードやユニットなどのデバイスのメモリに書き込まれていてもよい。つまり、そのコンピュータプログラムの指示により、第一の、第二の、第三の、…デバイスのCPUなどが実際の処理の一部または全部を行い、それによって上記機能が実現される場合も含む。
【００９２】
本発明を前記記憶媒体に適用する場合、その記憶媒体には、先に説明したフローチャートに対応または関連するコンピュータプログラムが格納される。
【図面の簡単な説明】
【００９３】
【図１】実施例の画像処理装置の構成例を示すブロック図、
【図２】プリンタの光学系の構成例を示す図、
【図３】ハーフトーンスクリーンを生成するドットジェネレータの構成例を示すブロック図、
【図４】CHSの生成処理における重心と黒化数の決定を説明するフローチャート、
【図５】CHSの作成パラメータを入力するUI例を示す図、
【図６】最小網点サイズに揺らぎを与える処理を示すフローチャート、
【図７】CHSの作成によって得られる網点と、網点の重心を示す図、
【図８】追加画素を検索するためのテーブルを示す図、
【図９】CHSの作成によって得られる網点サイズを概念的に示す図、
【図１０】画像データの濃度と網点の重心の関係を説明する図、
【図１１】図10に示す矩形領域の網点形状と重心を示す図、
【図１２】最小網点サイズに揺らぎを与えない場合の画像データの濃度と網点の重心の関係を説明する図、
【図１３】CHSの生成処理におけるボロノイ分割を説明するフローチャート、
【図１４】ボロノイ多角形の生成を説明する図、
【図１５】ボロノイ分割によって得られるボロノイ多角形の重心を示す図、
【図１６】ボロノイ分割によって得られるボロノイ多角形の重心を示す図、
【図１７】CHSの生成処理における網点の成長を説明するフローチャート、
【図１８】網点を拡大した様子を示す図、
【図１９】網点を拡大した様子を示す図、
【図２０】図10に示したグラデーション画像に対する重心から得られるボロノイ多角形と重心を示す図、
【図２１】CHSによって最終的に形成される網点画像例を示す図、
【図２２】入力画像（建物の写真）を示す図、
【図２３】図22の画像に対して重心と黒化数の決定で得られる重心を示す図、
【図２４】網点の成長で得られるCHSを用いた網点画像を示す図、
【図２５】CHSの作成パラメータを変化させた場合の網点の変化を示す図、
【図２６】実施例2における網点の拡大を説明する図、
【図２７】追加画素を検索するためのテーブルを示す図、
【図２８】ハーフトーン多角形を形成を説明する図、
【図２９】ボロノイ多角形に短い辺がある場合のハーフトーン多角形の形成を示す図、
【図３０】中点多角形に略相似なハーフトーン多角形の形状を示す図である。
【図１】
0004929122.tif 000002
【図２】
0004929122.tif 000003
【図３】
0004929122.tif 000004
【図４】
0004929122.tif 000005
【図５】
0004929122.tif 000006
【図６】
0004929122.tif 000007
【図７】
0004929122.tif 000008
【図８】
0004929122.tif 000009
【図９】
0004929122.tif 000010
【図１３】
0004929122.tif 000011
【図１４】
0004929122.tif 000012
【図１５】
0004929122.tif 000013
【図１６】
0004929122.tif 000014
【図１７】
0004929122.tif 000015
【図１８】
0004929122.tif 000016
【図１９】
0004929122.tif 000017
【図２０】
0004929122.tif 000018
【図２１】
0004929122.tif 000019
【図２３】
0004929122.tif 000020
【図２４】
0004929122.tif 000021
【図２６】
0004929122.tif 000022
【図２７】
0004929122.tif 000023
【図２８】
0004929122.tif 000024
【図２９】
0004929122.tif 000025
【図３０】
0004929122.tif 000026
【図１０】
0004929122.tif 000027
【図１１】
0004929122.tif 000028
【図１２】
0004929122.tif 000029
【図２２】
0004929122.tif 000030
【図２５】
0004929122.tif 000031