(57)【特許請求の範囲】
【請求項１】
画像データのエッジ画像データを生成する生成手段と、
前記エッジ画像データに平滑化処理を施して平滑化画像データを生成する平滑化手段と、
前記平滑化画像データの濃度分布に応じた密度分布の格子点を設定する設定手段と、
スクリーンを前記格子点を囲む多角形にボロノイ分割する分割手段と、
前記多角形の形状に基づく閾値マトリクスを作成する作成手段と、
前記閾値マトリクスを用いて前記画像データをハーフトーン処理するハーフトーン処理手段とを有することを特徴とする画像処理装置。
【請求項２】
さらに、前記平滑化画像データの濃度を調整する調整手段を有することを特徴とする請求項1に記載された画像処理装置。
【請求項３】
前記設定手段は、前記平滑化画像データの濃度が高い領域に対して、前記格子点の密度を高く設定することを特徴とする請求項1または請求項2に記載された画像処理装置。
【請求項４】
前記分割手段は、前記ボロノイ分割によって形成した多角形の重心を母点とするボロノイ分割を繰り返すことを特徴とする請求項1から請求項3の何れか一項に記載された画像処理装置。
【請求項５】
前記作成手段は、前記多角形を画像形成装置のドットサイズに応じて分割した前記閾値マトリクスを作成し、前記閾値マトリクスの各セルに画像データと比較する閾値を設定することを特徴とする請求項1から請求項3の何れか一項に記載された画像処理装置。
【請求項６】
さらに、前記画像データを空間分割したバンド画像の画像データを順次入力する入力手段を有し、前記生成手段、前記平滑化手段、前記設定手段、前記分割手段および前記作成手段は二つのバンド画像単位に処理を実行することを特徴とする請求項1に記載された画像処理装置。
【請求項７】
生成手段、平滑化手段、設定手段、分割手段、作成手段、ハーフトーン処理手段を有する画像処理装置の画像処理方法であって、
前記生成手段が画像データのエッジ画像データを生成し、
前記平滑化手段が前記エッジ画像データに平滑化処理を施して平滑化画像データを生成し、
前記設定手段が前記平滑化画像データの濃度分布に応じた密度分布の格子点を設定し、
前記分割手段がスクリーンを前記格子点を囲む多角形にボロノイ分割し、
前記作成手段が前記多角形の形状に基づく閾値マトリクスを作成し、
前記ハーフトーン処理手段が前記閾値マトリクスを用いて前記画像データをハーフトーン処理することを特徴とする画像処理方法。
【請求項８】
コンピュータを請求項1から請求項6の何れか一項に記載された画像処理装置の各手段として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハーフトーン処理に関する。
【背景技術】
【０００２】
電子写真方式の印刷装置は、複写機、MFP(multi-functional peripheral equipment)、オフィス用プリンタとして広く実用化されている。これら印刷装置は、連続階調の写真画像、文字やラインアートなどの文字線画、グラフやCGなどのグラフィックスなど、様々な種類の画像が混在した所謂文書画像を扱うことが多い。
【０００３】
中でも写真画像と文字線画は、その特徴量が大幅に異なり、写真画像は階調性を重視し、文字線画は解像度を重視して印刷する必要がある。そのため、写真画像を高画質に印刷するための画像処理と、文字線画を高画質に出力するための画像処理は異なる。つまり、写真画像には、網点スクリーンや線スクリーンによるハーフトーンスクリーン処理を施す。このハーフトーンスクリーン処理を文字線画にそのまま適用すれば、文字線画のエッジが網点化し印刷品質が著しく低下する。
【０００４】
上記の問題を回避するため、文書画像の写真画像の領域（以下、写真領域）と文字線画の領域（以下、文字領域）を分離する領域分割を行う。そして、写真領域には写真画像用のハーフトーンスクリーン（以下、写真用スクリーン）を、文字領域には文字線画用のスクリーン（以下、文字用スクリーン）を用いてディザ法や濃度パターン法によって印刷を行う。写真用スクリーンには充分な階調数を得るために、比較的大きなサイズの閾値マトリクスを使い、文字用スクリーンには小さなサイズの閾値マトリクスか、固定の閾値を使用する。このような処理により、特徴が異なる画像が混在する文書画像を高画質に印刷することができる。
【０００５】
しかし、文書画像の領域分割には以下の問題があり、領域分割は複雑なアルゴリズムを必要とし、高価な印刷装置にしか用いられていない。
(1)領域分割には、画像を記憶する入力用のメモリと、領域分割の結果を記憶する出力用のメモリを必要とし、ハードウェアの規模が大きくなり、装置のコストアップの要因になる。
(2)分割精度の向上を図ると分割アルゴリズムが複雑になり、さらにコストアップと処理パフォーマンスの低下が生じる。
(3)写真画像と文字線画が複雑に重なっている場合や、中間調の文字など、領域分割が困難な場合がある。このような領域が存在すると、画質劣化（アーティファクト）が生じ、画質が著しく低下する。
【０００６】
領域分割せずに、文書画像を高画質に印刷する方法が望まれる。一方法として、高線数のハーフトーンスクリーンを用いる方法が考えられる。例えば300線以上のハーフトーンスクリーンを用いてディザ処理を行えば、文字線画のエッジの先鋭性は視覚的に向上する。しかし、写真画像の階調性は著しく劣化する。とくに、電子写真方式の印刷装置は、高線数になるほど階調の再現が難しく、写真画像の印刷を重視する場合、この手法は使えない。
【０００７】
【特許文献１】特開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の一部として構成される。なお、以下では密度が可変のハーフトーンスクリーンを「variable density halftone screen」(VDS)と呼ぶことにする。
【００２３】
同期信号入力部35は、同期信号として、プリンタ12から1ラインの走査タイミングを示す水平同期信号Hsync、一頁の走査タイミングを示す垂直同期信号Vsync、および、画素クロックVclockを入力する。これら同期信号は、RAM15、画像処理部22、レーザドライバ34、光源27に供給され、画像形成タイミングを制御する。
【００２４】
画像処理部22は、バンドメモリ21を使用して、RAM15に割り当てられた画像メモリからバンド単位の画像（バンド画像）を順次入力し、バンド画像単位に、後述するVDSを用いるハーフトーン処理を含むレンダリングを行う。レーザドライバ34は、画像処理部22が出力する二値信号に従いビーム光源27を駆動して、ビーム光源27の発光を制御する。
【００２５】
［VDSによるハーフトーン処理］
図4はVDSによるハーフトーン処理を説明するフローチャートで、画像処理部22が実行する処理である。
【００２６】
画像処理部22は、バンドメモリ21から画像データを入力し(S30)、画像のエッジ部を抽出して、エッジ画像を生成する(S31)。そして、エッジ画像を平滑化処理して平滑化画像を生成し(S32)、必要に応じて、ガンマ調整により画像の濃度を補正する(S33)。
【００２７】
次に、画像処理部22は、平滑化画像の濃度分布（エッジ強度の分布）に応じた密度分布の格子点を導入し(S34)、格子点を母点としてボロノイ(Voronoi)分割を行ってボロノイ多角形を作成する(S35)。そして、ボロノイ多角形を網点形状として網点を成長させるハーフトーン処理を実行する(S36)。
【００２８】
●エッジ画像の生成(S31)
図5はエッジ画像の生成を説明するための入力画像例を示す図である。
【００２９】
画像処理部22は、エッジ抽出フィルタを用いて、入力画像のエッジ部を抽出する。エッジ抽出フィルタにはラプラシアン(Laplacian)フィルタやキャニー(Canny)フィルタなど多くのフィルタがあるが、方向依存性がなくノイズを拾わないフィルタが望ましい。ここでは、図6に示す二次微分フィルタのラプラシアンフィルタを用いて、フィルタ処理結果の絶対値をエッジ成分として、入力画像のエッジ画像を生成する。
【００３０】
●平滑化画像の生成(S32)
図7は入力画像から生成したエッジ画像の一例を示す図である。
【００３１】
画像処理部22は、図7に示すエッジ画像を平滑化して、平滑化画像を生成する。平滑化の目的は、エッジ強度に比例して網点格子の密度を変調する場合、密度の急激な変化よりも密度の緩やかな変化が画質によい影響を与えるためである。
【００３２】
平滑化フィルタとして、例えば、図8に示す7×7の平滑化フィルタを用いればよい。さらに、大きな平滑化効果を得るには、より大きなサイズの平滑化フィルタを使用するか、小サイズの平滑化フィルタにより、複数回平滑化を行う。ここでは、2m-1のガウス(Gaussian)正方フィルタとして下式のフィルタを用いる。平滑効果を強くするには、例えばm=8、a=6とし、15×15の平滑化フィルタにする。
Filter[i, j] = exp{[-(i - m)2 - (j - m)2]/a2}      …(1)
【００３３】
図9はエッジ画像を平滑化した平滑化画像の一例を示す図である。
【００３４】
平滑化後の画像には輝度の上昇（濃度の低下）が生じるため、ガンマ特性を適宜調整して、平滑化画像の濃度の最大値がある範囲に入るように調整して、濃度の低下を抑制する(S33)。上記の範囲の下限は、所定のドット密度を与えるために所定の値になるが、この下限値を制御することで画質を制御することもでき、画質調整パラメータとしても利用することができる。
【００３５】
●格子点の導入(S34)
画像処理部22は、平滑化画像の濃度分布に比例した密度分布の格子点を導入する。つまり、平滑化画像の濃度が高い部分（画像のエッジ部）により多くの格子点を与え、網点密度を高める。また、濃度が低い部分（画像の平坦部）は、網点密度が所定密度（ある程度決まった網点線数）になるように格子点を与える。以下では、画像の濃度に応じた網点密度の設定を「密度変調」と呼ぶ場合がある。網点の中心は網点格子点列の格子点であり、格子点の密度を高く設定することで、網点密度を高め（言い換えれば、高い線数の網点列になる）、細かい描写を可能にする。
【００３６】
図10は格子点の設定例を示す図である。
【００３７】
格子点の導入方法の詳細は後述するが、図10に示すように、この段階で導入した格子点は、密度が高い部分の格子点が接近し過ぎる問題がある。この問題は、後述するCVT(centroidal Voronoi tessellation)によって解決する。図11はCVTを三回の繰り返すことによって得られるボロノイ多角形の母点を示す図で、これら母点を格子点とすることで、図10における密度が高い部分の格子点が接近し過ぎる問題は解消する。
【００３８】
●ボロノイ分割
画像処理部22は、図11に示す格子点を母点とするボロノイ多角形を形成する。格子点Piに対するボロノイ多角形は次式に示す点V(Pi)の集合であり、ボロノイ多角形は網点格子点Piの勢力圏を現す。
V(Pi) = {P|d(P, Pi) ＜ d(P, Pj), ∀j≠i}      …(2)
ここで、PjはPiに隣接する網点格子点、
d(P, Pi)は点Pと網点格子点Piの距離、
d(P, Pj)は点Pと網点格子点Pjの距離
【００３９】
ボロノイ多角形の辺（ボロノイ境界）は、ドロネ(Delaunay)三角形の外心点を結ぶ線分である。また、ドロネ三角形は、隣接する網点格子点間を結ぶ線分を辺としてもち、網点格子点に対して一義的に決まる。従って、ボロノイ多角形も一義的に決まる。ドロネ三角形の外心点(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  …(3)
ここで、L = 2{X0(Y1-Y2) + X1(Y2-Y0) + X2(Y0-Y1)}、
(X0, Y0)、(X1, Y1)、(X2, Y2)はドロネ三角形の頂点座標
【００４０】
このように、一つの格子点を内部にもつボロノイ多角形を形成し、ボロノイ多角形を対応する網点の形状にする。図12はボロノイ多角形（網点形状）を示す図で、これらボロノイ多角形が網点の成長領域である。ボロノイ多角形は、ランダム配置の格子点に対して視覚的に滑らかな網点形状を決定する。もし、正方網点格子点列を使用し、網点面積を可変にして密度変調しようとすれば、網点内部をうまく充填する（黒ドットを成長させる）ことができない。ボロノイ多角形を使用すれば、視覚的にも違和感なく、網点内部を充填することができる。
【００４１】
●ハーフトーン処理(S36)
図13はボロノイ多角形を網点形状として網点を成長させるハーフトーン処理を示すフローチャートである。
【００４２】
画像処理部22は、図12に示すボロノイ多角形の重心位置を求める(S41)。なお、詳細は後述するが、ここまでに数回、詳細は後述する重心ボロノイ処理を繰り返しているため、重心と格子点はほぼ同じ位置になっている。従って、ボロノイ多角形が含む格子点（母点）をそのまま重心として用いても差し支えない。
【００４３】
次に、画像処理部22は、各ボロノイ多角形の画像濃度を決定する(S42)。図14は各ボロノイ多角形の重心位置（点で示す）と、画像を重ねた様子を示す図である。ボロノイ多角形の濃度は、重心位置の画像濃度で代表するか、ボロノイ多角形内の画像の平均濃度に決定する。
【００４４】
次に、画像処理部22は、重心を網点の中心点として、各ボロノイ多角形の画像濃度に応じて網点を成長させる(S43)。つまり、例えば濃度パターン法を用いて、ボロノイ多角形の画像濃度に応じて、重心を中心に、ボロノイ多角形の内部を塗り潰すことでハーフトーン画像を生成する。
【００４５】
網点を成長させる方法は色々あるが、例えば、濃度に比例した面積のボロノイ多角形に略相似の領域を塗り潰せばよい。つまり、濃度が100%（8ビットデータの場合は255）であればボロノイ多角形内をすべて塗り潰し、濃度が0%の場合は塗り潰しを行わない。中間濃度A%であれば面積がA%の、ボロノイ多角形に略相似の領域を塗り潰す。塗り潰しはプリンタ12が記録可能なドット（例えば最小ドット）単位に行う。
【００４６】
図16は閾値マトリクスの一例を示す図である。つまり、ボロノイ多角形の形状（網点形状）をもち、各セルがプリンタ12が記録可能なドットサイズに対応する閾値マトリクスを設定する。そして、濃度値未満の閾値をもつセルを塗り潰す（黒化）ことで、濃度を表現する。
【００４７】
画像処理部22は、ステップS44の判定により、全ボロノイ多角形の処理が終了するまで、ステップS41〜S43の処理を繰り返す。図15はハーフトーン画像の一例を示す図である。図15では、分かり易く網点を拡大して表示するが、実際は、少なくとも150線はあるため、網点は肉眼では認識することができない程度に細かい。
【００４８】
［格子点の導入］
図17は平滑化画像の濃度分布比例した密度分布の格子点の導入を説明するフローチャートである。
【００４９】
画像処理部22は、画像を例えばL×L画素のブロックに分割し、ブロック単位に以下の処理を行う。画素数Lは、画像の平坦部（エッジのない部分）の網点線数を規定する値で、例えば1200dpiのプリンタにおいて150線/インチのスクリーン線数を得たい場合、L=8にすればよい。また、画像のバンド幅をBとすると、B=n・L（nは自然数）の関係にする。
【００５０】
画像処理部22は、平滑化画像から一つのブロックを読み込み(S51)、そのブロック内のエッジ強度Eを求める(S52)。エッジ強度Eは、ブロックの平均濃度値でもよいし、代表点の濃度値でもよいが、どちらを採用しても平滑化後であるから大きな差はない。そして、ブロックに最大Q点の格子点を設定する場合はエッジ強度EをQ段階に量子化する(S53)。例えば濃度値の範囲が0〜255、四段階に量子化する(Q=4)とすると、量子化後のエッジ強度Eqは下式で表される。
Eq = round(E/K ＋ 1)      …(4)
ここで、K=256/Q、
round()は整数化関数
【００５１】
図18はエッジ強度Eqに応じてブロックに導入する格子点の数と位置を示す図で、ブロックの画素数Lが8の場合を示している。
【００５２】
図18に示すように、Eq=1の場合はブロックの左上に一つの格子点を設定し、微小な揺らぎを与えて格子点の位置を一、二画素の範囲でランダムに変位する(S54)。これは、ボロノイ多角形を求める際の0による除算やオーバフローなどを避けるためと、ボロノイ多角形をできるだけ正方形とは異なる形状にするためである。
【００５３】
また、Eq=2の場合はブロックの左上と右下に二点、Eq=3の場合はブロックの左上、左下、右下に三点、Eq=4の場合はブロックの左上、左下、右下、右上に四点の格子点を設定し、微小な揺らぎを与える。
【００５４】
なお、格子点の座標を整数値（画素単位）で演算すると、格子点の座標値の何れかが他の格子点の座標値と同じになり、演算の途中でエラーが発生する場合がある。これを考慮して、変位を与える演算（乱数値の加算）は、浮動小数点の乱数値を発生して、小数桁まで含めた演算を行う。そして、最後に整数化を行って格子点の座標を画素単位にする。
【００５５】
画像処理部22は、ステップS55の判定により、バンド画像の全ブロックの処理が終了するまで、ステップS51〜S54の処理を繰り返す。
【００５６】
［重心ボロノイ図］
重心ボロノイ図は、母点をボロノイ多角形の重心に移動して、再び、ボロノイ分割を行うCVT(centroidal Voronoi tessellation)と呼ばれる処理によって得られる。図19から図21は格子点を母点としてボロノイ分割を行い、CVTを繰り返した様子を示す図である。
【００５７】
図19はステップS34で導入した格子点（図19(a)、・印）を母点としてボロノイ分割した結果のボロノイ多角形（図19(b)）と、ボロノイ多角形の重心点（図19(c)、×印）を示す図である。図19(a)に示すように、初期の格子点の配置は密度が高い領域において局所的に不均一である。図19(c)に示すように、ボロノイ多角形の重心点は、初期の格子点に比べて局所的な不均一が緩和されている。従って、格子点をボロノイ多角形の重心点に移動すれば局所的な不均一が緩和される。
【００５８】
図20はCVTの結果を示す図で、図20(a)は移動後の格子点、図20(b)は重心ボロノイ図、図20(c)は重心ボロノイ図におけるボロノイ多角形の重心点を示す。図21は二回目のCVTの結果を示す図で、図21(a)は移動後の格子点、図21(b)は重心ボロノイ図を示す。
【００５９】
図19(a)、図20(a)、図21(a)を比べると、格子点の局所的な不均一が緩和されていることがわかる。また、図19(c)と図20(c)を参照すると、CVT後の母点（格子点）と重心点のずれが少ないことがわかる。CVTの繰り返し回数は任意であるが、母点と重心点のずれが所定の閾値以下になった場合にCVTの繰り返しを終了すればよい。
【００６０】
［文字画像の処理］
図22はグレイの背景上に描かれた小さな文字画像の一例を示す図である。図23は図22に示す文字画像のエッジ画像を示す図で、ラプラシアンフィルタをエッジ抽出フィルタに用いている。図24は図23に示すエッジ画像の平滑化画像を示す図である。図25は平滑化画像の濃度に応じて格子点を導入した様子を示す図である。図26は図25から格子点を取り出した様子を示す図である。このように、文字のエッジ部に対応する格子点の密度が高くなる。
【００６１】
図27は、図26の一部を拡大して、図26の格子点を母点とするボロノイ分割を示す図で、図27(a)は図26の格子点の一部、図27(b)はボロノイ多角形、図27(c)はボロノイ多角形の重心点を示す。図28は二回目のCVTの結果を示す図で、図28(a)は移動後の格子点、図28(b)は重心ボロノイ図を示す。
【００６２】
図29は、図22の文字画像の一部を拡大して、最終的な格子点とボロノイ多角形を重ねて表示した図である。図30は図29のボロノイ多角形の領域を濃度に応じて塗り潰して得られるハーフトーン画像を示す図である。これらの図から、文字画像のエッジ部には、高い密度で格子点が配置され、その結果、小面積のボロノイ多角形が網点領域として構成されることがわかる。つまり、文字線画のエッジのように空間周波数が高い画像領域には細かい網点が配置される。また、濃度変化が滑らかな階調が連続する画像領域にはほぼ所定間隔に比較的大きい網点が配置される。従って、文字線画と写真画像などが混在する文書画像について、領域分割を行わずに、文字領域のエッジをシャープに、写真領域の階調性を滑らかに再現する、高画質な印刷が可能になる。
【００６３】
［バンドメモリの利用］
図31はバンド単位のレンダリングを説明する図で、VDSによるハーフトーン処理に必要なメモリ量を削減するにはバンド60を単位とするレンダリングが有効である。
【００６４】
画像処理部22は、バンド60を矢印61の方向に走査して、バンド単位のレンダリングを繰り返し、一頁分の画像データを処理する。このようにすれば、レンダリングに必要なメモリ量をバンド幅分に抑えることができ、一頁分のメモリ量を必要としない。
【００６５】
しかし、バンド単位のレンダリングにVDSによるハーフトーン処理を含めると次の問題がある。
【００６６】
図32は辺62Aと62Bで挟まれたバンド画像を示す図で、格子点P1からP6が設定されているとする。図33はドロネ三角形の形成方法を説明する図で、ドロネ三角形は、その外接円（図33に示す円63、64、65など）の内部に母点を含まないというルールで形成される。また、ボロノイ多角形は、そのボロノイ辺がドロネ辺の垂直二等分線であるというルールで形成される。
【００６７】
図34は次のバンド画像において格子点Pxが設定された場合のドロネ三角形の変化を示す図である。図34(a)はP1〜P6とPxが比較的離れた位置関係にある場合を示し、この場合、P1からP6を相互に結ぶドロネ辺は変化せず、ドロネ三角形も変化しない。そして、新たにドロネ三角形△P3P4Pxが形成される。
【００６８】
しかし、点Pxが辺62Bに近付き図34(b)に示す位置にくると、△P1P3P4は、△P1P3Pxと△P1P4Pxの二つのドロネ三角形に変化する。ドロネ三角形が変化すれば、当然、ボロノイ多角形が変化する。さらに、点Pxが辺62Bに近付き図34(c)に示す位置にくると、△P1P2P3と△P1P3Pxは、△P2P3Pxと△P1P2Pxに変化する。そして、点Pxが辺62Bぎりぎりまで近付き図34(d)の位置にくると、△P2P6P3と△P2P3Pxは、△P6P3Pxと△P2P6Pxに変化する。
【００６９】
このように新たなバンドの格子点を設定すると、前のバンドのボロノイ多角形が変化するので、前のバンドのボロノイ多角形を決定し直す必要がある。言い換えると、空間分割した画像それぞれで、独立に、ボロノイ多角形を形成することはできず、前の画像（バンド画像）のボロノイ多角形の変更を許容する必要がある。
【００７０】
図35はボロノイ多角形の変更を許容するバンド単位のハーフトーン処理を説明する図である。まず、二つのバンド画像71と72のボロノイ多角形を設定し、次に、二つのバンド画像72と73のボロノイ多角形を設定する処理を繰り返す。こうすれば、バンド画像72の格子点の影響をバンド画像71のボロノイ多角形に反映し、バンド画像73の格子点の影響をバンド画像72のボロノイ多角形に反映することができる。
【００７１】
バンドメモリ21には、少なくとも三つのメモリ領域を設定する必要がある。これは、レーザビームプリンタなどの高速プリンタにおいては、ハーフトーン処理を含むレンダリング処理とプリンタエンジンの潜像形成速度の関係から、バッファメモリを必要とするためである。従って、図35の符号71〜73がバンドメモリ21の領域を表すとすれば、領域72と73に格納したバンド画像を処理した後、領域72のバンド画像を領域（バッファメモリ）71に移動する。そして、領域73のバンド画像を領域72に移動し、新たなバンド画像を領域73に読み込むことになる。なお、インクジェットプリンタのように比較的低速か、インクジェットプリンタの印刷ヘッドのように印刷を一時停止することができるプリンタであれば、バッファメモリはなくてもよい。
【００７２】
図36はバンド画像の処理を示すフローチャートである。
【００７３】
画像処理部22は、領域72の処理済みのバンド画像を領域71に移動してレーザドライバ34に出力する(S81)。そして、領域73の処理途中のバンド画像を領域72に移動し(S82)、新たなバンド画像を領域73に読み込む(S83)。続いて、領域72と73のバンド画像に上記のハーフトーン処理を実行する(S84)。そして、全バンド画像を処理したか否かを判定し(S85)、未処理のバンド画像がなくなまでステップS81からS84を繰り返す。また、未処理のバンド画像がなくなると、領域72と73の処理済みのバンド画像を順次領域71に移動してレーザドライバ34に出力する(S86)。
【００７４】
このように、VDSを用いるハーフトーン処理を、ページメモリを用いずに、メモリ量が少ないバンドメモリで実行することが可能になる。通常、バンドメモリ21として数10ライン相当分のラインメモリが用いられる。画像データがJPEG圧縮されている場合、復号してバンドメモリ21に書き込まれるため、8の自然数倍のライン数のバンドメモリにすると効率的である。仮に32ラインのバンドメモリとすると、三つの領域を合わせて96ライン分のメモリ量になる。例えば、A4サイズの短手方向(210mm)を600dpiで処理すると、必要なライン数は4960ラインであり、それに比べて、メモリコストを低く抑えることができる。
【００７５】
このように、写真画像と文字線画などが混在する文書画像に、領域分割を行うことなく、各領域に適切なハーフトーン処理を施して高画質の印刷出力を得ることができる。また、領域分割が困難な写真画像と文字線画が複雑に重なっている画像、中間調の文字線画などの各領域に適切なハーフトーン処理を施して高画質の印刷出力を得ることができる。
【００７６】
［他の実施例］
なお、本発明は、複数の機器（例えばコンピュータ、インタフェイス機器、リーダ、プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、ファクシミリ装置、制御装置など）に適用してもよい。
【００７７】
また、本発明の目的は、上記実施例の機能を実現するコンピュータプログラムを記録した記憶媒体をシステムまたは装置に供給し、そのシステムまたは装置のコンピュータ（CPUやMPU）が前記コンピュータプログラムを実行することでも達成される。この場合、記憶媒体から読み出されたソフトウェア自体が上記実施例の機能を実現することになり、そのコンピュータプログラムと、そのコンピュータプログラムを記憶する、コンピュータが読み取り可能な記憶媒体は本発明を構成する。
【００７８】
また、前記コンピュータプログラムの実行により上記機能が実現されるだけではない。つまり、そのコンピュータプログラムの指示により、コンピュータ上で稼働するオペレーティングシステム(OS)および/または第一の、第二の、第三の、…プログラムなどが実際の処理の一部または全部を行い、それによって上記機能が実現される場合も含む。
【００７９】
また、前記コンピュータプログラムがコンピュータに接続された機能拡張カードやユニットなどのデバイスのメモリに書き込まれていてもよい。つまり、そのコンピュータプログラムの指示により、第一の、第二の、第三の、…デバイスのCPUなどが実際の処理の一部または全部を行い、それによって上記機能が実現される場合も含む。
【００８０】
本発明を前記記憶媒体に適用する場合、その記憶媒体には、先に説明したフローチャートに対応または関連するコンピュータプログラムが格納される。
【図面の簡単な説明】
【００８１】
【図１】実施例の画像処理装置の構成例を示すブロック図、
【図２】プリンタの光学系の構成例を示す図、
【図３】密度が可変のハーフトーンスクリーンを生成するドットジェネレータの構成例を示すブロック図、
【図４】VDSによるハーフトーン処理を説明するフローチャート、
【図５】エッジ画像の生成を説明するための入力画像例を示す図、
【図６】ラプラシアンフィルタを示す図、
【図７】エッジ画像の一例を示す図、
【図８】平滑化フィルタを示す図、
【図９】平滑化画像の一例を示す図、
【図１０】平滑化画像の濃度分布に比例した密度分布の格子点の設定例を示す図、
【図１１】CVTを三回の繰り返すことによって得られるボロノイ多角形の母点を示す図、
【図１２】ボロノイ多角形を示す図、
【図１３】ボロノイ多角形を網点形状として網点を成長させるハーフトーン処理を示すフローチャート、
【図１４】各ボロノイ多角形の重心位置と、画像を重ねた様子を示す図、
【図１５】ハーフトーン画像の一例を示す図、
【図１６】閾値マトリクスの一例を示す図、
【図１７】平滑化画像の濃度に比例した密度の格子点の導入を説明するフローチャート、
【図１８】エッジ強度Eqに応じてブロックに導入する格子点の数と位置を示す図、
【図１９】格子点を母点としてボロノイ分割を行い、CVTを繰り返した様子を示す図、
【図２０】格子点を母点としてボロノイ分割を行い、CVTを繰り返した様子を示す図、
【図２１】格子点を母点としてボロノイ分割を行い、CVTを繰り返した様子を示す図、
【図２２】グレイの背景上に描かれた小さな文字画像の一例を示す図、
【図２３】図22に示す文字画像のエッジ画像を示す図、
【図２４】図23に示すエッジ画像の平滑化画像を示す図、
【図２５】平滑化画像の濃度に応じて格子点の導入した様子を示す図、
【図２６】図25から格子点を取り出した様子を示す図、
【図２７】図26の格子点を母点とするボロノイ分割を示す図、
【図２８】二回目のCVTの結果を示す図、
【図２９】最終的な格子点とボロノイ多角形を重ねて表示した図、
【図３０】図29のボロノイ多角形の領域を濃度に応じて塗り潰して得られるハーフトーン画像を示す図、
【図３１】バンド単位のレンダリングを説明する図、
【図３２】バンド画像を示す図、
【図３３】ドロネ三角形の形成方法を説明する図、
【図３４】次のバンド画像において格子点Pxが設定された場合のドロネ三角形の変化を示す図、
【図３５】ボロノイ多角形の変更を許容するバンド単位のハーフトーン処理を説明する図、
【図３６】バンド画像の処理を示すフローチャートである。
【図１】
0004881274.tif 000002
【図２】
0004881274.tif 000003
【図３】
0004881274.tif 000004
【図４】
0004881274.tif 000005
【図６】
0004881274.tif 000006
【図８】
0004881274.tif 000007
【図１１】
0004881274.tif 000008
【図１２】
0004881274.tif 000009
【図１３】
0004881274.tif 000010
【図１５】
0004881274.tif 000011
【図１６】
0004881274.tif 000012
【図１７】
0004881274.tif 000013
【図１８】
0004881274.tif 000014
【図１９】
0004881274.tif 000015
【図２０】
0004881274.tif 000016
【図２１】
0004881274.tif 000017
【図２６】
0004881274.tif 000018
【図２７】
0004881274.tif 000019
【図２８】
0004881274.tif 000020
【図３０】
0004881274.tif 000021
【図３２】
0004881274.tif 000022
【図３３】
0004881274.tif 000023
【図３４】
0004881274.tif 000024
【図３６】
0004881274.tif 000025
【図５】
0004881274.tif 000026
【図７】
0004881274.tif 000027
【図９】
0004881274.tif 000028
【図１０】
0004881274.tif 000029
【図１４】
0004881274.tif 000030
【図２２】
0004881274.tif 000031
【図２３】
0004881274.tif 000032
【図２４】
0004881274.tif 000033
【図２５】
0004881274.tif 000034
【図２９】
0004881274.tif 000035
【図３１】
0004881274.tif 000036
【図３５】
0004881274.tif 000037