(57)【要約】【課題】適切なディザマトリクスを生成する。【解決手段】第２ドットプロファイル生成部３３では、一の濃度レベルのドットプロファイルに次の対象濃度レベルに合わせてドットを追加して次の濃度レベルのドットプロファイルを生成する際に、ドットプロファイルに追加されるドットの位置を変更しつつ、ドットプロファイルから導かれるエネルギー値の変化が取得され、追加されるドットの位置がエネルギー値を極小とする位置として決定される。ここで、エネルギー値としては、ドットプロファイルに含まれる２つのドットの各組合せについて、２つのドット間の相対的な位置により決定される相互作用エネルギーを求めた上で、相互作用エネルギーの総和として求められるものが利用される。これにより、適切なディザマトリクスを生成することができる。【選択図】図５
2006165930.tif 000002
【特許請求の範囲】
【請求項１】
多階調の元画像のハーフトーン化において前記元画像と比較されるディザマトリクスを生成するディザマトリクス生成方法であって、
ディザマトリクスに対応する２次元領域に、最初の一の濃度レベルにおけるドットの配置を示す２値のドットプロファイルを取得する工程と、
前記一の濃度レベルの次の濃度レベルに合わせて前記ドットプロファイル中に追加されるドットの個数を取得する工程と、
前記ドットプロファイル中に追加されるドットの位置を決定し、前記次の濃度レベルのドットプロファイルを取得する工程と、
前記一の濃度レベルを前記次の濃度レベルへと更新して前記追加されるドットの個数を取得する工程へと戻る工程と、
を備え、
前記最初の一の濃度レベルのドットプロファイル、および、各濃度レベルのドットプロファイルに対して決定された前記追加されるドットの位置の組合せが、ディザマトリクスとされ、
前記次の濃度レベルのドットプロファイルを取得する工程が、
前記ドットプロファイルにドットを追加して変更後のドットプロファイルを生成する工程と、
前記変更後のドットプロファイルに含まれる２つのドットの各組合せについて、前記２つのドット間の相対的な位置により決定される相互作用エネルギーを求め、相互作用エネルギーの総和をエネルギー値として実質的に求める工程と、
を備え、
前記次の濃度レベルのドットプロファイルを取得する工程において、前記ドットプロファイルに追加されるドットの位置を変更しつつ、前記変更後のドットプロファイルを生成する工程と前記エネルギー値を実質的に求める工程とが繰り返され、前記追加されるドットの位置が前記エネルギー値を極小とする位置として決定されることを特徴とするディザマトリクス生成方法。
【請求項２】
請求項１に記載のディザマトリクス生成方法であって、
ドットプロファイルの行方向および列方向の大きさをそれぞれＬｘ，Ｌｙ、前記変更後のドットプロファイルにおける前記２つのドットの前記行方向および前記列方向にて規定される位置の座標をそれぞれ（ｘｍ，ｙｍ），（ｘｎ，ｙｎ）として、
（ｘｎ−ｘｍ）のＬｘによる剰余、および、（ｙｎ−ｙｍ）のＬｙによる剰余をパラメータとして前記２つのドットの間の前記相互作用エネルギーが求められることを特徴とするディザマトリクス生成方法。
【請求項３】
請求項１または２に記載のディザマトリクス生成方法であって、
前記２つのドット間の距離をｒとして前記相互作用エネルギーＪ（ｒ）が、
【数１】
2006165930.tif 000007
により求められることを特徴とするディザマトリクス生成方法。
【請求項４】
請求項１ないし３のいずれかに記載のディザマトリクス生成方法であって、
前記エネルギー値を実質的に求める工程において、変更前のドットプロファイルのエネルギー値と前記変更後のドットプロファイルのエネルギー値との差が前記追加されるドットの位置の変更に基づいて求められることを特徴とするディザマトリクス生成方法。
【請求項５】
請求項１ないし４のいずれかに記載のディザマトリクス生成方法であって、
前記次の濃度レベルのドットプロファイルを取得する工程が、焼きなまし法を利用して前記エネルギー値を極小とする前記追加されるドットの位置を決定することを特徴とするディザマトリクス生成方法。
【請求項６】
多階調の元画像のハーフトーン化において前記元画像と比較されるディザマトリクスを生成するディザマトリクス生成方法であって、
ディザマトリクスに対応する２次元領域に、低濃度範囲の最初の濃度レベルにおけるドットの配置を示す２値のドットプロファイルを生成する初期ドットプロファイル生成工程と、
前記低濃度範囲の前記最初の濃度レベル以降の各濃度レベルにおけるドットプロファイルを、前記２次元領域において全てのドットから最も離れた位置にドットを順次追加することにより生成する第１ドットプロファイル生成工程と、
少なくとも中濃度範囲の各濃度レベルにおけるドットの配置を示すドットプロファイルを前記第１ドットプロファイル生成工程とは異なる手法を利用して生成する第２ドットプロファイル生成工程と、
を備えることを特徴とするディザマトリクス生成方法。
【請求項７】
請求項６に記載のディザマトリクス生成方法であって、
前記初期ドットプロファイル生成工程において、前記最初の濃度レベルに合わせた個数だけドットを前記２次元領域に配置し、配置されたドットの分布の均一性をボロノイ領域分割を利用して高めることにより、前記最初の濃度レベルのドットプロファイルが生成されることを特徴とするディザマトリクス生成方法。
【請求項８】
請求項６または７に記載のディザマトリクス生成方法であって、
前記第２ドットプロファイル生成工程において、ドットの配置状態を数値化する所定のエネルギー関数を用いて一の濃度レベルのドットプロファイルから次の濃度レベルのドットプロファイルを生成する際に追加されるドットの位置が決定されることを特徴とするディザマトリクス生成方法。
【請求項９】
請求項８に記載のディザマトリクス生成方法であって、
前記第２ドットプロファイル生成工程が、
前記次の濃度レベルに合わせて前記一の濃度レベルのドットプロファイル中に追加されるドットの個数を取得する工程と、
前記一の濃度レベルのドットプロファイル中に追加されるドットの位置を決定し、前記次の濃度レベルのドットプロファイルを取得する工程と、
前記一の濃度レベルを前記次の濃度レベルへと更新して前記追加されるドットの個数を取得する工程へと戻る工程と、
を備え、
前記次の濃度レベルのドットプロファイルを取得する工程が、
前記一の濃度レベルのドットプロファイルにドットを追加して変更後のドットプロファイルを生成する工程と、
前記変更後のドットプロファイルに含まれる２つのドットの各組合せについて、前記２つのドット間の相対的な位置により決定される相互作用エネルギーを求め、相互作用エネルギーの総和をエネルギー値として実質的に求める工程と、
を備え、
前記次の濃度レベルのドットプロファイルを取得する工程において、前記一の濃度レベルのドットプロファイルに追加されるドットの位置を変更しつつ、前記変更後のドットプロファイルを生成する工程と前記エネルギー値を実質的に求める工程とが繰り返され、前記追加されるドットの位置が前記エネルギー値を極小とする位置として決定されることを特徴とするディザマトリクス生成方法。
【請求項１０】
請求項１ないし９のいずれかに記載のディザマトリクス生成方法にて生成されたことを特徴とするディザマトリクス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多階調の元画像のハーフトーン化において元画像と比較されるディザマトリクスを生成する技術、および、ディザマトリクスに関する。
【背景技術】
【０００２】
従来より、ディザマトリクスを利用して多階調の元画像（入力画像とも呼ばれる。）をハーフトーン化（ディザ処理）することが行われている。ディザマトリクスを利用するこの手法では、元画像の各画素の濃度レベル（画素値）とディザマトリクスの対応する要素値とを比較することにより、この画素の位置にドットを形成するか否かが決定されて２値の出力画像が生成され、これにより、誤差拡散法等の近傍アルゴリズムに比べて高速なディザ処理が実現される。また、近年では、ディザマトリクスの要素値の配列にランダム性を取り入れることにより、出力画像において要素値の配列の規則性に起因する周期的模様が発生することを防止する技術も利用されている。さらに、青色雑音（ブルーノイズ）と呼ばれる特性を有するディザマトリクスでは、誤差拡散法により生成される出力画像と同等の高品質な出力画像の生成が可能になるとともに、誤差拡散法において問題となる出力画像中のドットが線状に連なる現象（いわゆる、ワーム）が発生することもない。
【０００３】
ディザマトリクスを生成する手法として、例えば、特許文献１では、一の濃度レベルのドットの配置から次の濃度レベルにおけるドットの配置を示す２値のドットプロファイルを生成する際に、ドットプロファイルに対して定義される人間の視覚特性に基づいたコスト関数（エネルギー関数）の値が小さくなるように、焼きなまし法を用いて一の濃度レベルのドットプロファイルに追加されるドットの位置を決定することにより、全ての濃度レベルにそれぞれ対応する複数のドットプロファイルを取得してディザマトリクスを生成する手法が開示されている。
【０００４】
なお、特許文献２では、一の濃度レベルの２値のドットプロファイルにブルーノイズ特性フィルタを作用させた画像を生成し、この画像と元のドットプロファイルとの差分画像において濃度レベルが最大となる画素に対応するドットプロファイル中の位置にドットを追加して一の濃度レベルの次の濃度レベルのドットプロファイルを生成することにより、各濃度レベルのドットプロファイルを取得してディザマトリクスを生成する手法が提案されている。また、特許文献３では、一の濃度レベルのドットプロファイルに低域通過フィルタを作用させた画像において、濃度レベルが最小となる画素に対応するドットプロファイル中の位置にドットを追加して次の濃度レベルのドットプロファイルを生成することにより、各濃度レベルのドットプロファイルを取得してディザマトリクスを生成する手法が開示されている。
【特許文献１】特開平１０−７５３７６号公報
【特許文献２】特表平６−５０８００７号公報
【特許文献３】米国特許第５，５３５，０２０号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、特許文献１の手法にて生成されたディザマトリクスを利用してハーフトーン化された出力画像では、空間周波数特性において単に低周波成分がカットされるだけとなり、ブルーノイズの特徴とされる周波数スペクトルのピークが顕著に現れない。また、この手法ではコスト関数の計算に長時間を要するため、最適化されたドットプロファイルを短時間に生成することができないという問題もある。なお、特許文献２および３の手法においても、演算量の削減が必要とされる場合がある。
【０００６】
本発明は上記課題に鑑みなされたものであり、適切なディザマトリクスを生成することを目的とし、ディザマトリクスを短時間に生成することも目的としている。
【課題を解決するための手段】
【０００７】
請求項１に記載の発明は、多階調の元画像のハーフトーン化において前記元画像と比較されるディザマトリクスを生成するディザマトリクス生成方法であって、ディザマトリクスに対応する２次元領域に、最初の一の濃度レベルにおけるドットの配置を示す２値のドットプロファイルを取得する工程と、前記一の濃度レベルの次の濃度レベルに合わせて前記ドットプロファイル中に追加されるドットの個数を取得する工程と、前記ドットプロファイル中に追加されるドットの位置を決定し、前記次の濃度レベルのドットプロファイルを取得する工程と、前記一の濃度レベルを前記次の濃度レベルへと更新して前記追加されるドットの個数を取得する工程へと戻る工程とを備え、前記最初の一の濃度レベルのドットプロファイル、および、各濃度レベルのドットプロファイルに対して決定された前記追加されるドットの位置の組合せが、ディザマトリクスとされ、前記次の濃度レベルのドットプロファイルを取得する工程が、前記ドットプロファイルにドットを追加して変更後のドットプロファイルを生成する工程と、前記変更後のドットプロファイルに含まれる２つのドットの各組合せについて、前記２つのドット間の相対的な位置により決定される相互作用エネルギーを求め、相互作用エネルギーの総和をエネルギー値として実質的に求める工程とを備え、前記次の濃度レベルのドットプロファイルを取得する工程において、前記ドットプロファイルに追加されるドットの位置を変更しつつ、前記変更後のドットプロファイルを生成する工程と前記エネルギー値を実質的に求める工程とが繰り返され、前記追加されるドットの位置が前記エネルギー値を極小とする位置として決定される。
【０００８】
請求項２に記載の発明は、請求項１に記載のディザマトリクス生成方法であって、ドットプロファイルの行方向および列方向の大きさをそれぞれＬｘ，Ｌｙ、前記変更後のドットプロファイルにおける前記２つのドットの前記行方向および前記列方向にて規定される位置の座標をそれぞれ（ｘｍ，ｙｍ），（ｘｎ，ｙｎ）として、（ｘｎ−ｘｍ）のＬｘによる剰余、および、（ｙｎ−ｙｍ）のＬｙによる剰余をパラメータとして前記２つのドットの間の前記相互作用エネルギーが求められる。
【０００９】
請求項３に記載の発明は、請求項１または２に記載のディザマトリクス生成方法であっ
て、前記２つのドット間の距離をｒとして前記相互作用エネルギーＪ（ｒ）が、
【００１０】
【数１】
2006165930.tif 000003
【００１１】
により求められる。
【００１２】
請求項４に記載の発明は、請求項１ないし３のいずれかに記載のディザマトリクス生成方法であって、前記エネルギー値を実質的に求める工程において、変更前のドットプロファイルのエネルギー値と前記変更後のドットプロファイルのエネルギー値との差が前記追加されるドットの位置の変更に基づいて求められる。
【００１３】
請求項５に記載の発明は、請求項１ないし４のいずれかに記載のディザマトリクス生成方法であって、前記次の濃度レベルのドットプロファイルを取得する工程が、焼きなまし法を利用して前記エネルギー値を極小とする前記追加されるドットの位置を決定する。
【００１４】
請求項６に記載の発明は、多階調の元画像のハーフトーン化において前記元画像と比較されるディザマトリクスを生成するディザマトリクス生成方法であって、ディザマトリクスに対応する２次元領域に、低濃度範囲の最初の濃度レベルにおけるドットの配置を示す２値のドットプロファイルを生成する初期ドットプロファイル生成工程と、前記低濃度範囲の前記最初の濃度レベル以降の各濃度レベルにおけるドットプロファイルを、前記２次元領域において全てのドットから最も離れた位置にドットを順次追加することにより生成する第１ドットプロファイル生成工程と、少なくとも中濃度範囲の各濃度レベルにおけるドットの配置を示すドットプロファイルを前記第１ドットプロファイル生成工程とは異なる手法を利用して生成する第２ドットプロファイル生成工程とを備える。
【００１５】
請求項７に記載の発明は、請求項６に記載のディザマトリクス生成方法であって、前記初期ドットプロファイル生成工程において、前記最初の濃度レベルに合わせた個数だけドットを前記２次元領域に配置し、配置されたドットの分布の均一性をボロノイ領域分割を利用して高めることにより、前記最初の濃度レベルのドットプロファイルが生成される。
【００１６】
請求項８に記載の発明は、請求項６または７に記載のディザマトリクス生成方法であって、前記第２ドットプロファイル生成工程において、ドットの配置状態を数値化する所定のエネルギー関数を用いて一の濃度レベルのドットプロファイルから次の濃度レベルのドットプロファイルを生成する際に追加されるドットの位置が決定される。
【００１７】
請求項９に記載の発明は、請求項８に記載のディザマトリクス生成方法であって、前記第２ドットプロファイル生成工程が、前記次の濃度レベルに合わせて前記一の濃度レベルのドットプロファイル中に追加されるドットの個数を取得する工程と、前記一の濃度レベルのドットプロファイル中に追加されるドットの位置を決定し、前記次の濃度レベルのドットプロファイルを取得する工程と、前記一の濃度レベルを前記次の濃度レベルへと更新して前記追加されるドットの個数を取得する工程へと戻る工程とを備え、前記次の濃度レベルのドットプロファイルを取得する工程が、前記一の濃度レベルのドットプロファイルにドットを追加して変更後のドットプロファイルを生成する工程と、前記変更後のドットプロファイルに含まれる２つのドットの各組合せについて、前記２つのドット間の相対的な位置により決定される相互作用エネルギーを求め、相互作用エネルギーの総和をエネルギー値として実質的に求める工程とを備え、前記次の濃度レベルのドットプロファイルを取得する工程において、前記一の濃度レベルのドットプロファイルに追加されるドットの位置を変更しつつ、前記変更後のドットプロファイルを生成する工程と前記エネルギー値を実質的に求める工程とが繰り返され、前記追加されるドットの位置が前記エネルギー値を極小とする位置として決定される。
【００１８】
請求項１０に記載の発明は、請求項１ないし９のいずれかに記載のディザマトリクス生成方法にて生成されたものである。
【発明の効果】
【００１９】
請求項１ないし５、並びに、請求項９および１０の発明では、相互作用エネルギーを利用して適切なディザマトリクスを生成することができる。
【００２０】
また、請求項３の発明では、より適切なディザマトリクスを生成することができ、請求項４の発明では、ディザマトリクスを容易に生成することができる。
【００２１】
請求項６ないし１０の発明では、低濃度範囲において既存のドットから離れた位置にドットを追加することにより適切なディザマトリクスを短時間に生成することができる。
【００２２】
また、請求項７の発明では、低濃度範囲の最初の濃度レベルのドットプロファイルをドットの分布の均一性を確保しつつ生成することができ、請求項８の発明では、少なくとも中濃度範囲において所定のエネルギー関数を利用して、ディザマトリクスを容易に生成することができる。
【発明を実施するための最良の形態】
【００２３】
図１はディザマトリクスを利用して元画像のハーフトーン化を行うディザ処理システム１の機能構成を示す図である。ディザ処理システム１は、行方向および列方向に画素が配列される多階調の元画像（入力画像とも呼ばれ、図１中において行列Ｉ（Ｘ，Ｙ）として表される。）のデータを記憶する元画像メモリ１１、元画像メモリ１１から濃度レベル（画素値）が読み出される各画素の行方向の座標Ｘおよび列方向の座標Ｙがそれぞれ入力されるモジュロ演算部１２ａ，１２ｂ、後述するディザマトリクス生成処理により生成されるディザマトリクスを記憶するディザマトリクスメモリ１３、元画像メモリ１１からの濃度レベルとディザマトリクスの対応する要素値（閾値）とを比較する比較部１４、並びに、比較部１４からの出力を記憶する出力画像メモリ１５を備える。
【００２４】
図２は元画像７０をハーフトーン化する様子を説明するための図である。図２に示すように元画像７０には、同一の大きさの多数の領域に分割してハーフトーン化の単位となる繰り返し領域７１が設定される。ディザマトリクス８１は１つの繰り返し領域７１（図２中において太線にて示す領域）に含まれる複数の画素にそれぞれ対応する複数の閾値を要素値として有するものであり、本実施の形態では、ディザマトリクス８１の行方向および列方向の大きさがそれぞれＬｘ，Ｌｙ（ただし、Ｌｘ，Ｌｙは整数）とされる。
【００２５】
元画像のハーフトーン化の際には、概念的には元画像７０の各繰り返し領域７１にディザマトリクス８１をタイル張りするように重ね合わせ、繰り返し領域７１の各画素の濃度レベルとディザマトリクス８１の対応する要素値とが比較されることにより、２値の出力画像９０（図１中において行列Ｏ（Ｘ，Ｙ）として表される。）におけるその画素の位置（アドレス）の濃度レベルが決定される。したがって、仮に元画像７０の画素の濃度レベルが一様である場合は、ディザマトリクス８１においてその濃度レベルよりも小さな要素値が設定されている位置の画素には、例えば、濃度レベル「１」が付与され（すなわち、ドットが置かれ）、残りの画素には濃度レベル「０」が付与され（すなわち、ドットは置かれず）、ハーフトーン化後の２値の出力画像９０が生成される。
【００２６】
ハーフトーン化の処理を図１を参照してさらに具体的に説明すると、元画像メモリ１１から元画像の１つの画素の濃度レベルが読み出されると、この画素の位置の座標（Ｘ，Ｙ）に対応する繰り返し領域中のｘ座標が、モジュロ演算部１２ａが（Ｘ  ｍｏｄ  Ｌｘ）（ただし、（Ａ  ｍｏｄ  Ｂ）はＡをＢで除したときの剰余を示し、Ｂより小さい０以上の整数となる。）を演算することにより求められ、繰り返し領域中のｙ座標が、モジュロ演算部１２ｂが（Ｙ  ｍｏｄ  Ｌｙ）を演算することにより求められる。そして、ディザマトリクス８１における１つの要素値が特定されてディザマトリクスメモリ１３から読み出される。比較部１４では、元画像メモリ１１からの濃度レベルとディザマトリクスメモリ１３からの要素値とが比較され、濃度レベルが要素値よりも大きい場合にはその画素の位置の濃度レベルが「１」とされ、濃度レベルが要素値以下の場合にはその画素の位置の濃度レベルが「０」とされ、図３に示すように、ドット（平行斜線を付して示す。）の有無により表現される２値の出力画像９０が生成される。なお、実際にはＬｘ，Ｌｙの値は図３に示すものよりも十分に大きい。
【００２７】
次に、多階調の元画像のハーフトーン化において元画像と比較されるディザマトリクスを生成する処理について説明を行う。図４は、本発明の第１の実施の形態に係るディザマトリクスを生成するコンピュータ２の構成を示す図である。コンピュータ２は、図４に示すように、各種演算処理を行うＣＰＵ２１、基本プログラムを記憶するＲＯＭ２２および各種情報を記憶するＲＡＭ２３をバスラインに接続した一般的なコンピュータシステムの構成となっている。バスラインにはさらに、情報記憶を行う固定ディスク２４、画像等の各種情報の表示を行うディスプレイ２５、操作者からの入力を受け付けるキーボード２６ａおよびマウス２６ｂ（以下、「入力部２６」と総称する。）、光ディスク、磁気ディスク、光磁気ディスク等のコンピュータ読み取り可能な記録媒体８から情報の読み取りを行う読取装置２７、並びに、他の装置との間で信号を送受信する通信部２８が、適宜、インターフェイス（Ｉ／Ｆ）を介する等して接続される。
【００２８】
コンピュータ２には、事前に読取装置２７を介して記録媒体８からプログラム８０が読み出され、固定ディスク２４に記憶される。そして、プログラム８０がＲＡＭ２３にコピーされるとともにＣＰＵ２１がＲＡＭ２３内のプログラムに従って演算処理を実行することにより（すなわち、コンピュータがプログラムを実行することにより）、コンピュータ２がディザマトリクスを生成するディザマトリクス生成部としての役割を果たす。
【００２９】
図５は、ＣＰＵ２１がプログラム８０に従って動作することにより、ＣＰＵ２１、ＲＯＭ２２、ＲＡＭ２３、固定ディスク２４等が実現する機能構成を他の構成とともに示す図であり、図５において、ディザマトリクス生成部３０の各構成（ボロノイ領域分割部３１、第１ドットプロファイル生成部３２および第２ドットプロファイル生成部３３）および記憶部３４がＣＰＵ２１等により実現される機能を示す。なお、ディザマトリクス生成部３０の機能は専用の電気的回路により実現されてもよく、部分的に電気的回路が用いられてもよい。
【００３０】
図６はディザマトリクスを生成する処理の概要を説明するための図であり、ディザマトリクス８１と各濃度レベルにおけるドットの配置を示す２値のドットプロファイルとの関係を示す図である。ディザマトリクス８１を生成する際には、元画像の濃度範囲に含まれる複数の濃度レベルのそれぞれに対応するとともに、生成されるディザマトリクスと同じ大きさのドットプロファイルが取得され、これらのドットプロファイルから１つのディザマトリクスが生成される。例えば、元画像の濃度レベルが０ないし３である場合には、図６に示すように、これらの濃度レベルにそれぞれ対応する４個のドットプロファイル８１１〜８１４が取得される。
【００３１】
ここで、ディザマトリクス８１と同じ大きさの一定の濃度レベルの画像をディザマトリクス８１を用いてハーフトーン化すると、その濃度レベルのドットプロファイルとなるため、ディザマトリクス８１においてドットプロファイル中のドットの位置と同じ位置は、その濃度レベルよりも低い値とされる。また、ドットプロファイルは濃度レベルが高いほどドット（図６中において平行斜線を付して示す画素）の数が増加し、濃度レベルが異なる２つのドットプロファイルの間では、濃度レベルが低いドットプロファイルにおいて存在するドットは、濃度レベルが高いドットプロファイルにおいても必ず存在するという特徴を有する。したがって、ディザマトリクスに対応する２次元領域において、一の濃度レベルのドットプロファイルと次の濃度レベルのドットプロファイルとの間でドットが追加（または、削除）される位置と同じ位置に一の濃度レベル（または、次の濃度レベル）の値を付与し、一の濃度レベルを次の濃度レベルへと更新しつつ上記処理を繰り返すことによりディザマトリクス８１が生成される。以下、元画像の複数の濃度レベルにそれぞれ対応する複数のドットプロファイルを取得して、ディザマトリクスを生成する処理について詳述する。
【００３２】
図７．Ａはコンピュータ２がディザマトリクスを生成する処理の流れを示す図であり、図７．Ｂは、図７．Ａ中の各工程に関係する濃度範囲（または、濃度レベル）を説明するための図である。図７．Ａおよび図７．Ｂに示すように、コンピュータ２では、初期ドットプロファイル生成処理により濃度レベル１のドットプロファイルが取得され（ステップＳ１１）、第１ドットプロファイル生成処理により濃度レベル２からｇ１までの低濃度範囲の各濃度レベルのドットプロファイルが取得され（ステップＳ１２）、第２ドットプロファイル生成処理により濃度レベルｇ１より大きい中濃度範囲および高濃度範囲（ただし、最も高い濃度レベルを除く。）の各濃度レベルのドットプロファイルが取得される（ステップＳ１３）。
【００３３】
本実施の形態では、低濃度レベルから高濃度レベルに向かって順にドットプロファイルが生成されるため、一の濃度レベルのドットプロファイルにドットを追加して、より高い次の濃度レベルのドットプロファイルが取得される。また、元画像の濃度レベルが０ないし２５５の２５６段階であるものとし、濃度レベルｇのドットプロファイルに含まれるドット数を累積分布関数ｎ（ｇ）にて表すものとする。累積分布関数ｎ（ｇ）は（広義の）単調増加関数とされ、通常、（ｎ（ｇ＋１）＞ｎ（ｇ））、かつ、（ｎ（０）＝０）、および、（ｎ（２５５）＝Ｌｘ×Ｌｙ）（上述のように、ドットプロファイルの行方向および列方向の大きさは、ディザマトリクスと同様に、それぞれＬｘ，Ｌｙとなる。）とされる。なお、累積分布関数の一例としては、濃度レベルとドット数とが線形に増加する線形関数が考えられるが、他の単調増加関数を用いることも可能である。以下、図７．Ａ中のステップＳ１１〜Ｓ１３の各処理の詳細について説明する。
【００３４】
図８は初期ドットプロファイル生成処理の流れを示す図であり、図７．ＡのステップＳ１１にて行われる処理を示している。初期ドットプロファイル生成処理ではボロノイ領域分割が利用される。ここで、ボロノイ領域分割とは距離が定義された空間を、空間に散らばった複数の母点をそれぞれ核とする複数の細胞領域に分割することをいい、各細胞領域に含まれる点において、全ての母点のうち当該細胞領域の核である母点が最寄りのものとなる。
【００３５】
図５のボロノイ領域分割部３１では、まず、ディザマトリクスに対応する離散的な２次元領域（すなわち、行方向および列方向の大きさがそれぞれＬｘ，Ｌｙとされる２次元領域であり、以下、「マトリクス領域」という。）において、初期の濃度レベル１に合わせたドットの個数分だけ位置（すなわち、行方向および列方向にて規定される整数値座標）がランダムに選択され、選択された複数の位置のそれぞれに母点が配置されて異なるラベルが付与される（ステップＳ２１）。ここで、濃度レベル１に合わせたドットの個数は、累積分布関数ｎ（１）として求められる。
【００３６】
続いて、マトリクス領域中の各位置（座標（ｘ，ｙ）にて特定される位置）に対して最寄りの母点が特定され、特定された母点のラベルをこの位置に対応する要素値とする行列Ｖ（ｘ，ｙ）が求められることにより、ラベルが等しい（すなわち、最寄りの母点が同じとなる）位置の集合が細胞領域として取得される（すなわち、離散ボロノイ領域分割が行われる）（ステップＳ２２）。このとき、マトリクス領域が、図２に示す繰り返し領域７１に対応することから、ｎ（１）個だけ配置された複数の母点も上下左右に繰り返し存在するものとして扱われる。したがって、ボロノイ領域分割が行われる際には、マトリクス領域の繰り返しを想定した場合の複数の母点のうち、距離算出基準となる各位置に最も近いものが特定される。
【００３７】
図９は、ボロノイ領域分割が行われたマトリクス領域を示す図である。図９に示すように、複数の母点６１の位置に基づいてボロノイ領域分割が行われ、複数の細胞領域６２（図９中にて太線にて囲む領域）がマトリクス領域中にて取得される。複数の細胞領域６２が取得されると、各細胞領域６２において重心６３が求められ、母点６１から重心６３までのベクトルが求められる（ステップＳ２３）。なお、この段階では、母点６１の位置と細胞領域６２の重心６３の位置とは通常一致せず、母点６１は細胞領域６２内のある方向に偏っており、ステップＳ２３では細胞領域６２内における母点６１の偏りが実質的に求められる。そして、母点６１から重心６３までのベクトルがＣ倍（定数倍）され、Ｃ倍後の移動ベクトルに従って母点６１を移動して細胞領域６２内における母点６１の偏りが改善される（ステップＳ２４）。
【００３８】
ボロノイ領域分割部３１では、細胞領域内における母点の偏りを計算し、偏りを改善する上記ステップＳ２２〜Ｓ２４の処理が繰り返し行われ（ステップＳ２５）、母点がほぼ移動しなくなると（すなわち、母点の位置が収束して、母点から細胞領域の重心までのベクトルの大きさがほぼ０となると）、各母点の位置の値が「１」とされてドットが付与される（ステップＳ２６）。これにより、ｎ（１）個のドットがマトリクス領域におよそ均一に分布された濃度レベル１のドットプロファイルＰ（ｘ，ｙ；１）が取得される。なお、ステップＳ２４において用いられる定数Ｃは、母点の位置の収束を加速させるためのパラメータであり、操作者により図５の入力部２６を介して予め設定される。経験的には、定数Ｃを２とした場合に定数Ｃが１の場合よりも母点の位置の収束が速くなり、母点の分布も好ましいものとなる。
【００３９】
このように、ボロノイ領域分割部３１では、低濃度範囲の最初の濃度レベルに合わせた個数だけドットがマトリクス領域に配置され、ドットの分布の均一性がボロノイ領域分割を利用して高められることにより、低濃度範囲の最初の濃度レベルのドットプロファイルがドットの分布の均一性を確保しつつ適切かつ容易に生成される。
【００４０】
次に、図５の第１ドットプロファイル生成部３２では、低濃度範囲に含まれる複数の濃度レベルｇ（ただし、２≦ｇ≦ｇ１）のそれぞれに対してドットプロファイルが取得される。図１０は、第１ドットプロファイル生成部３２が行う第１ドットプロファイル生成処理の流れを示す図であり、図７．ＡのステップＳ１２にて行われる処理を示している。
【００４１】
第１ドットプロファイル生成部３２では、まず、マトリクス領域に濃度レベル（ｇ−１）のドットプロファイルＰ（ｘ，ｙ；ｇ−１）がコピーされ、ドットプロファイルＱ（ｘ，ｙ）が生成される（ステップＳ３１）。ここで、ドットプロファイルＰ（ｘ，ｙ；ｇ−１）は求められるドットプロファイルの濃度レベルｇ（以下、「対象濃度レベルｇ」という。）の前の濃度レベルのものであり、第１ドットプロファイル生成部３２における最初の処理では、通常、上述の処理により生成された濃度レベル１のドットプロファイルＰ（ｘ，ｙ；１）とされる。そして、対象濃度レベルｇのドットプロファイルにおけるドット数ｎ（ｇ）と濃度レベル（ｇ−１）のドットプロファイルにおけるドット数ｎ（ｇ−１）との差ｄｎ（ｄｎ＝ｎ（ｇ）−ｎ（ｇ−１））を求めることにより追加されるドットの個数が取得される（ステップＳ３２）。また、所定のパラメータＫが０に初期化される（ステップＳ３３）。
【００４２】
続いて、ドットプロファイルＱ（ｘ，ｙ）において、繰り返し領域を考慮しつつ各位置と最寄りのドットとの間の距離が算出され、算出された距離をこの位置に対応する要素値とする最短距離行列Ｗ（ｘ，ｙ）が求められ（ステップＳ３４，Ｓ３５）、距離が最大となる位置の座標（ｘａ，ｙａ）が求められる（ステップＳ３６）。なお、最寄りの母点との距離が等しい複数の位置が存在する場合には、１つの位置がランダムに選択される。そして、ドットプロファイルＱ（ｘ，ｙ）中の座標（ｘａ，ｙａ）の位置の値が「１」とされてドットが追加される（ステップＳ３７）。このとき、距離が最大となる位置は、上述のボロノイ領域分割により生成される細胞領域の境界を示すいずれかの多角形の頂点の位置と同じであり、この位置では隣接する全てのドットとの間の距離が等しくなる。したがって、このような位置に新たなドットを追加することにより、ドットの分布の均一性がおよそ保たれる。その後、パラメータＫに１が加算される（ステップＳ３８）。なお、最短距離行列Ｗ（ｘ，ｙ）と同時に離散ボロノイ領域分割を示す行列Ｖ（ｘ，ｙ）を保持し、ステップＳ３７で追加されたドットに新しいラベルを与え、追加されたドットの近傍の必要最低限の範囲にある座標について離散ボロノイ領域分割を示す行列Ｖ（ｘ，ｙ）および最短距離行列Ｗ（ｘ，ｙ）を修正すれば、ステップＳ３５は高速化が可能である。さらに、ステップＳ３６で最短距離行列Ｗ（ｘ，ｙ）をスキャンして選択される座標の候補は複数存在することが多いので、Ｗ（ｘ，ｙ）の一度のスキャンで座標の候補をリストアップしておけば、毎回スキャンする必要はなくなり、高速化につながる。
【００４３】
上記ステップＳ３４〜Ｓ３８はＫの値を更新しつつ繰り返され、マトリクス領域において全てのドットから最も離れた位置にドットが順次追加される。更新後のＫの値が対象濃度レベルｇと濃度レベル（ｇ−１）とのドット数の差ｄｎとなると（すなわち、ｄｎ個のドットが追加されると）（ステップＳ３４）、ドットプロファイルＱ（ｘ，ｙ）はドットプロファイルＰ（ｘ，ｙ；ｇ）とされ（ステップＳ３９）、ｎ（ｇ）個のドットを含む対象濃度レベルｇのドットプロファイルが生成される。
【００４４】
第１ドットプロファイル生成部３２では、生成されたドットプロファイルの濃度レベルｇがｇ１となるまで、濃度レベルｇのドットプロファイルＰ（ｘ，ｙ；ｇ）をマトリクス領域への次のコピー対象として濃度レベルを更新しつつ、上記ステップＳ３１〜Ｓ３９が繰り返される（ステップＳ４０，Ｓ４１）。これにより、低濃度範囲（２≦ｇ≦ｇ１）に含まれる複数の濃度レベルのそれぞれのドットプロファイルが生成される。実際には、低濃度範囲の各濃度レベルｇに対するステップＳ３５〜Ｓ３８の繰り返し処理において、ステップＳ３７にて追加されるドットの位置の組合せがディザマトリクスにおいて値（ｇ−１）が付与される位置とされる。
【００４５】
以上のように、コンピュータ２では、低濃度範囲の最初の濃度レベル以降の各濃度レベルにおけるドットの配置を示す２値のドットプロファイルが、マトリクス領域において既存のドットから最も離れた位置にドットを順次追加することにより生成され、中濃度範囲および高濃度範囲の各濃度レベルのドットプロファイルが、第１ドットプロファイル生成部３２とは異なる後述の手法を利用して生成される。これにより、低濃度範囲において複雑な演算を行うことなく均一性の高いドットプロファイルが生成され、適切なディザマトリクスを容易かつ短時間に生成することが実現される。なお、第１ドットプロファイル生成部３２による上記処理では、ドット数が（Ｌｘ×Ｌｙ）の半数に近づくとドット同士が接続して既存のドットから最も離れた位置を求める技術的意義が失われるため、第１ドットプロファイル生成処理はドット数ｎ（ｇ）が（Ｌｘ×Ｌｙ）の半数より少なく、ドット同士が接続しない程度の濃度レベルｇの範囲内にて利用されることが好ましい。
【００４６】
次に、中濃度範囲（ｇ１＜ｇ≦ｇ２）および高濃度範囲（ｇ２＜ｇ≦２５４）に含まれる複数の濃度レベルｇのそれぞれに対して、図５の第２ドットプロファイル生成部３３が、ドットの配置状態を数値化する所定のエネルギー関数を用いてドットプロファイルを生成する手法について述べる。
【００４７】
まず、第２ドットプロファイル生成部３３において利用されるエネルギー関数について説明する。本実施の形態では、２値画像を統計物理学の分野で用いられる２次元のスピンモデルと対応させるものとし、スピンとは１または０の値をとる物理変数である。エネルギー値Ｅは、マトリクス領域においてディザマトリクスと同じ大きさの２値画像を表現するスピン行列をＳ（ｘ，ｙ）、スピン行列に含まれる２つのスピンの位置の座標をそれぞれ（ｘｍ，ｙｍ），（ｘｎ，ｙｎ）、２つのスピンの相対位置により決定される相互作用エネルギーを示す関数をＪとして数２により示される。
【００４８】
【数２】
2006165930.tif 000004
【００４９】
数２では、スピン行列Ｓ（ｘ，ｙ）に含まれる２つのスピンの各組合せについて相互作用エネルギーを求め、２つのスピンの値の積と相互作用エネルギーとを乗じた値の総和がエネルギー値とされる。ここで、２つのスピン間の相互作用エネルギーは、ａ）スピン行列Ｓ（ｘ，ｙ）の繰り返し領域を考慮して求められるとともに相互作用エネルギーの大きさは２つのスピン間の相対位置にのみ依存し、ｂ）相互作用エネルギーの大きさは両スピンに対して対称性を有し、ｃ）同一のスピン同士の組合せには相互作用エネルギーは生じない、という条件を満たす。条件ａ）は、数２において（（ｘｎ−ｘｍ）  ｍｏｄ  Ｌｘ）、および、（（ｙｎ−ｙｍ）  ｍｏｄ  Ｌｙ）をパラメータとして２つのスピン間の相互作用エネルギーＪが求められることを意味する。また、条件ｂ）は、（−ａ  ｍｏｄ  Ｌｘ）、および、（−ｂ  ｍｏｄ  Ｌｙ）により求められる相互作用エネルギーＪと、（ａ  ｍｏｄ  Ｌｘ）、および、（ｂ  ｍｏｄ  Ｌｙ）により求められる相互作用エネルギーＪとが等しくなることを意味し、条件ｃ）は２つのパラメータの値が共に０である場合の相互作用エネルギーＪが０となることを意味する。第２ドットプロファイル生成部３３では、数２により求められるエネルギー値Ｅを最小化するようにしてスピン行列Ｓ（ｘ，ｙ）が求められ、ドットプロファイルが生成される（いわゆる、最適化アルゴリズムが利用される。）。
【００５０】
本実施の形態では、相互作用エネルギーＪは繰り返し領域を考慮した２つのスピンが近接している場合に、大きな値をとるものとされる。具体的には、相互作用エネルギーＪ（ｒ）は繰り返し領域を考慮した２つのスピン間の最短距離をｒとして数３により求められる。ただし、数３において、ｗ１、ｗ２、σ１、σ２は０以上の実数の定数であり、σ１＞σ２かつｗ１＞ｗ２とされ、距離ｒが０の場合を除く。
【００５１】
【数３】
2006165930.tif 000005
【００５２】
数３は、分散パラメータが互いに異なる２つの２次元正規分布をそれぞれ示す２つの関数を組み合わせたものであり、数３により求められる相互作用エネルギーＪは、２つのスピン間の距離ｒが０となる近傍において大きな値をとり、σ１、σ２に比べて距離ｒが十分に大きい場合には相互作用エネルギーＪは０と近似できる。また、数３をフーリエ変換した場合、右辺の第１項は低周波成分において値が大きくなるため、エネルギー値Ｅにおいて低周波成分に対するペナルティとして機能し、右辺の第２項は高周波成分にて値が大きくなるため、高周波成分に対するペナルティとして機能するといえ、ｗ１、ｗ２はそれぞれ第１項および第２項の重み付けを与える。以下、スピンモデルおよび相互作用エネルギーを利用した第２ドットプロファイル生成部３３における処理について詳述する。
【００５３】
図１１および図１２は、第２ドットプロファイル生成部３３が行う第２ドットプロファイル生成処理の流れを示す図であり、図７．ＡのステップＳ１３にて行われる処理を示している。第２ドットプロファイル生成処理についても、中濃度および高濃度範囲内において低濃度レベルから高濃度レベルに向かって順にドットプロファイルが生成される。
【００５４】
第２ドットプロファイル生成部３３のスピン行列変更部３３１では、まず、一の濃度レベル（ｇ−１）のドットプロファイルＰ（ｘ，ｙ；ｇ−１）がスピン行列Ｓ（ｘ，ｙ）にコピーされる（ステップＳ５１）。ここで、ドットプロファイルＰ（ｘ，ｙ；ｇ−１）は求められるドットプロファイルの濃度レベルｇ（対象濃度レベルｇ）の前の濃度レベルのものであり、第２ドットプロファイル生成部３３における最初の処理では、通常、図１０の処理により最後に取得された濃度レベルｇ１のドットプロファイルＰ（ｘ，ｙ；ｇ１）とされる。
【００５５】
続いて、スピン行列Ｓ（ｘ，ｙ）において、値が０であるスピンの座標の集合Ｈ（すなわち、ドットプロファイルＰ（ｘ，ｙ；ｇ−１）においてドットが追加可能である位置の集合であり、（Ｈ＝｛（ｘｊ，ｙｊ）；Ｓ（ｘｊ，ｙｊ）＝０｝）で表される。）が求められる（ステップＳ５２）。また、対象濃度レベルｇのドットプロファイルにおけるドット数ｎ（ｇ）と濃度レベル（ｇ−１）のドットプロファイルにおけるドット数ｎ（ｇ−１）との差ｄｎ（ｄｎ＝ｎ（ｇ）−ｎ（ｇ−１））が求められ、対象濃度レベルｇに合わせてドットプロファイルＰ（ｘ，ｙ；ｇ−１）に追加されるドットの個数が取得される（ステップＳ５３）。
【００５６】
スピン行列変更部３３１では座標集合Ｈからｄｎ個の座標がランダムに選択され、選択された座標の集合がＵ、残りの座標の集合がＤとされる（ステップＳ５４）。そして、スピン行列Ｓ（ｘ，ｙ）において、座標集合Ｕに含まれる全ての座標（ｘ，ｙ）のスピンの値が１とされる（ステップＳ５５）。なお、座標集合Ｕおよび座標集合Ｄ（すなわち、座標集合Ｈ）に含まれる座標は、以下の処理において操作対象となるスピン（以下、「対象スピン」という。）の位置を示すものであり、座標集合Ｕは対象スピンのうち値が１とされたものの座標の集合を示し、座標集合Ｄは対象スピンのうち値が０のままであるものの座標の集合を示す。
【００５７】
エネルギー値算出部３３２では、対象濃度レベルｇに対応する所定のパラメータ（すなわち、ｗ１、ｗ２、σ１、σ２）が数３に示す相互作用エネルギーＪを求める式に設定される（ステップＳ５６）。このとき、数３に設定されるパラメータは、例えば、対象濃度レベルｇが中濃度範囲に含まれる場合（ｇ１＜ｇ≦ｇ２）と、高濃度範囲に含まれる場合（ｇ２＜ｇ≦２５４）とで異なる値とされ、これらのパラメータは操作者により入力部２６を介して予め入力される。なお、対象濃度レベルｇに対応するパラメータが既に設定されている場合には、ステップＳ５６の処理はスキップされる。
【００５８】
ここで、第２ドットプロファイル生成部３３ではエネルギー値Ｅが小さいスピン行列Ｓ（ｘ，ｙ）を求めるために焼きなまし法が利用される。焼きなまし法はエネルギーの定義された統計物理的なモデルをシミュレーションし、その平衡状態を高温から低温へと徐々にシフトさせることにより、エネルギーをより小さくする状態を見つけだす手法である。スピン行列変更部３３１では、まず、焼きなまし法にて利用される温度パラメータＴ（ただし、Ｔ＞０）が初期値Ｔ０にセットされる（ステップＳ５７）。
【００５９】
続いて、座標集合Ｄから１つの座標（ｘ１，ｙ１）（（ｘ１，ｙ１）∈Ｄ））がランダムに選択され、座標集合Ｕからも１つの座標（ｘ２，ｙ２）（（ｘ２，ｙ２）∈Ｕ）がランダムに選択され、スピン行列Ｓにおいて座標（ｘ１，ｙ１）の対象スピンの値０と座標（ｘ２，ｙ２）の対象スピンの値１とが交換される（ステップＳ５８）。そして、エネルギー値算出部３３２において値を交換する前後におけるスピン行列Ｓのエネルギー値Ｅの変化量ｄＥが求められる（ステップＳ５９）。
【００６０】
ここで、数２において、ある１つの座標（ｘｂ，ｙｂ）のスピンの値のみを反転する場合におけるエネルギー値Ｅの変化量ｄＥ１は、当該スピンの値の変化量（（＋１）または（−１）となる。）をｄＳとして数４により求められる。
【００６１】
【数４】
2006165930.tif 000006
【００６２】
したがって、ステップＳ５９では数４を用いて、座標（ｘ１，ｙ１）の対象スピンの値のみを反転させた場合のエネルギー値Ｅの変化量と、座標（ｘ１，ｙ１）の対象スピンの値を反転した後に、座標（ｘ２，ｙ２）の対象スピンの値を反転させた場合のエネルギー値Ｅの変化量とを求め、これらの値の和がエネルギー値の変化量ｄＥとされる。このように、エネルギー値算出部３３２では、値が交換される前のスピン行列Ｓ（ｘ，ｙ）のエネルギー値と、値が交換された後のスピン行列Ｓ（ｘ，ｙ）のエネルギー値との差が、値を１とする対象スピンの位置の変更に基づいて求められる。これにより、位置の変更前後において数２を計算してエネルギー値の差を求めるよりも、演算量を大幅に減少させることができる。また、上述のように、数３においてσ１、σ２に比べて距離ｒが十分に大きい場合には相互作用エネルギーＪが０と近似できるため、繰り返し領域を考慮しつつ値を反転するスピンの近傍のスピンに対してのみ数４の演算を行えばよく、エネルギー値Ｅの変化量ｄＥを容易に求めることができる。
【００６３】
ここで、数３中の最短距離ｒを取得する際に、行方向の距離は、例えば（（ｘ２−ｘ１）  ｍｏｄ  Ｌｘ）の結果がＬｘ／２以下である場合にはその値を用いて、また、Ｌｘ／２より大きい場合にはこの剰余演算の結果とＬｘとの差に基づいて求めることができ、列方向の距離についても同様である。すなわち、最短距離ｒは（（ｘ２−ｘ１）  ｍｏｄ  Ｌｘ）および（（ｙ２−ｙ１）  ｍｏｄ  Ｌｙ）の結果から取得することが可能であるため、数３により求められる相互作用エネルギーＪ（ｒ）についても実質的に（ｘ２−ｘ１）のＬｘによる剰余、および、（ｙ２−ｙ１）のＬｙによる剰余をパラメータとするものといえる。なお、相互作用エネルギーＪは（（ｘ２−ｘ１）  ｍｏｄ  Ｌｘ）および（（ｙ２−ｙ１）  ｍｏｄ  Ｌｙ）の演算結果により、対応する要素である相互作用エネルギーＪの行方向および列方向の位置が特定される行列として予め準備されてもよく、この場合、相互作用エネルギー行列は行方向および列方向の大きさがそれぞれＬｘ，Ｌｙとなる。
【００６４】
続いて、スピン行列変更部３３１において擬似一様乱数ｐ（ただし、０≦ｐ＜１）が取得され（ステップＳ６０）、擬似一様乱数ｐがｍｉｎ｛１，ｅｘｐ（−ｄＥ／Ｔ）｝（ただし、ｍｉｎ｛Ａ，Ｂ｝はＡおよびＢのうち小さい方を示す。）よりも小さい場合に、ステップＳ５８における交換が許可され（ステップＳ６１）、座標（ｘ１，ｙ１）が座標集合Ｄから座標集合Ｕへと移動し、座標（ｘ２，ｙ２）が座標集合Ｕから座標集合Ｄへと移動する（ステップＳ６２）。一方、擬似一様乱数ｐがｍｉｎ｛１，ｅｘｐ（−ｄＥ／Ｔ）｝以上である場合には（ステップＳ６１）、ステップＳ５８における対象スピンの値の交換が元に戻される（ステップＳ６３）。このように、エネルギー値の変化量ｄＥが０より大きい場合には交換が確率的に許可され、変化量ｄＥが０以下である場合には交換が必ず許可される。
【００６５】
そして、温度パラメータＴを小さくするか確認した上で、小さくする場合には（ステップＳ６４）、温度パラメータＴがβ倍（ただし、０＜β＜１）されて小さくされ（ステップＳ６５）、変更後の温度パラメータＴを用いてステップＳ５８〜Ｓ６５の処理が繰り返される（ステップＳ６６）。このとき、ステップＳ６１において、エネルギー値が増加する場合にも確率的に交換を許可することにより、エネルギー値が局所最適解にとどまることが抑制される。なお、ステップＳ６５の処理は所定の繰り返し回数毎に行われる。
【００６６】
ここで、温度パラメータＴは、どの程度エネルギー値が増加する交換を許可するかを決定するためのものである。仮に、温度パラメータＴがおよそ０である場合には、エネルギー値の変化量ｄＥが０より大きくなる交換は全て拒絶され、エネルギー値が増加しない交換のみが許可される。一方、Ｔが無限大である場合には、変化量ｄＥが０より大きくなる交換も全て許可され、スピン行列Ｓをランダムに状態変化させることと同じになる。したがって、ステップＳ６５においてＴをβ倍して小さくしていくことにより、繰り返し回数が少ない間は広く探索を行ってスピン行列Ｓがおよそ適切な解の近傍に到達し、繰り返し回数が多くなるにしたがって探索の範囲を狭めて、エネルギー値が極小となる解（スピン行列Ｓ）を求めることが可能となる。なお、温度パラメータＴは、不適切な局所最適解に陥った場合等、必要に応じて大きくされてもよく、一定の値としてステップＳ６４，Ｓ６５の処理を省略することも可能である。
【００６７】
第２ドットプロファイル生成部３３では、例えば、エネルギー値の変化量ｄＥがしきい値以下となることが所定回数だけ連続して繰り返され、エネルギー値の著しい変化がほとんどなくなると、ステップＳ５８〜Ｓ６５の処理の繰り返しが終了され（ステップＳ６６）、エネルギー値が極小となるスピン行列Ｓ（ｘ，ｙ）が取得される。このとき、第２ドットプロファイル生成部３３ではスピン行列Ｓ（ｘ，ｙ）について、数２に示す演算によるエネルギー値Ｅは実際には求められないが、ステップＳ５９において、値を交換する前後のスピン行列Ｓにおけるエネルギー値Ｅの変化量ｄＥを求めつつ、変化量ｄＥの変化がモニターされるため、実質的には、上記処理は、値を交換する前後のスピン行列Ｓのエネルギー値Ｅを求めて、エネルギー値Ｅが極小となるスピン行列Ｓ（ｘ，ｙ）を特定することと等価の処理となる。なお、ステップＳ６５における処理が所定回数だけ行われることにより、ステップＳ５８〜Ｓ６５の処理の繰り返しが終了されてもよく（以下、同様。）（ステップＳ６６）、この場合でも、エネルギー値がおよそ極小となるスピン行列Ｓ（ｘ，ｙ）が取得される。
【００６８】
ステップＳ５８〜Ｓ６５の処理の繰り返しが終了すると、スピン行列Ｓ（ｘ，ｙ）が対象濃度レベルｇのドットプロファイルＰ（ｘ，ｙ；ｇ）として取得される（ステップＳ６７）。このとき、ドットプロファイルＰ（ｘ，ｙ；ｇ）において、濃度レベル（ｇ−１）のドットプロファイルＰ（ｘ，ｙ；ｇ−１）から追加されたドットの位置の組合せがディザマトリクスにおいて値（ｇ−１）が付与される位置とされる。
【００６９】
第２ドットプロファイル生成部３３では、取得されたドットプロファイルＰ（ｘ，ｙ；ｇ）をスピン行列Ｓ（ｘ，ｙ）への次のコピー対象として濃度レベルを更新しつつ、ステップＳ５１〜Ｓ６７が繰り返される（ステップＳ６８，Ｓ６９）。そして、取得されたドットプロファイルの濃度レベルｇが濃度レベル２５４となると第２ドットプロファイル生成処理が終了する（ステップＳ６８）。これにより、中濃度範囲および高濃度範囲の各濃度レベルに対してドットプロファイルが求められつつディザマトリクス８１が生成される。
【００７０】
生成後のディザマトリクス８１は記憶部３４に記憶され、記憶部３４からさらに図１のディザマトリクスメモリ１３にコピーされる。そして、ディザ処理システム１では、ディザマトリクス８１を利用して元画像をハーフトーン化することにより、ブルーノイズの特徴とされる周波数スペクトルのピークを有する高品質な出力画像を取得することができる。
【００７１】
以上のように、コンピュータ２では、一の濃度レベルのドットプロファイルに対応するスピン行列Ｓ（ｘ，ｙ）から、次の濃度レベルに合わせた個数だけ対象スピンの値が１に変更される。そして、スピン行列Ｓ（ｘ，ｙ）に含まれる２つのスピンの各組合せについて、２つのスピン間の距離が０となる近傍で値が大きくなる相互作用エネルギーと２つのスピンの値の積とを乗じた値を実質的に求め、これらの値の総和であるエネルギー値が小さくなるように、値が１に変更された対象スピンと値が０の他の対象スピンとの値をさらに交換して、中濃度範囲および高濃度範囲の各濃度レベルのドットプロファイルが取得される（スピンモデルのエネルギー最小化法）。これにより、中濃度範囲および高濃度範囲において相互作用エネルギーを利用してドットが均一に分布したドットプロファイルを取得し、適切なディザマトリクスを生成することができる。
【００７２】
また、所定のパラメータ（ｗ１、ｗ２、σ１、σ２）を用いて数３に示す相互作用エネルギーが求められることにより、低周波成分および高周波成分にペナルティを与えて周波数特性の制御を行い、生成される出力画像にドットの大きな塊や、いわゆるチェッカーボード模様が発生することを抑制しつつ、ブルーノイズ特性を有するより適切なディザマトリクスを生成することが実現される。さらに、値が交換される前後のスピン行列Ｓ（ｘ，ｙ）のエネルギー値の差が、数４を用いて値を１とする対象スピンの位置の変更に基づいて求められることにより、交換前後において数２を計算してエネルギー値の差を求めるよりも演算量を減少させることができ、ディザマトリクスを容易に生成することができる。
【００７３】
上記の説明では、低濃度レベルから高濃度レベルに向かって順にドットプロファイルが生成されるが、高濃度レベルから低濃度レベルに向かって順にドットプロファイルが生成されてもよい。この場合、初期ドットプロファイル生成処理、第１ドットプロファイル生成処理および第２ドットプロファイル生成処理のそれぞれでは、ある濃度レベルのドットプロファイルからドットを削除する（すなわち、ドットプロファイルのある画素の値を１から０とする）ことにより次の濃度レベルのドットプロファイルを生成することとなるが、値が０の画素をドットと捉えて、ある濃度レベルのドットプロファイルに値が０のドットを追加していくものと考えれば、上記の説明と同じ処理により（値が０のドットの濃度レベルがより高い）次の濃度レベルのドットプロファイルが生成される。値が１の画素をドットと捉えるか、値が０の画素をドットと捉えるかは便宜的なものである。
【００７４】
例えば、図１１および図１２の第２ドットプロファイル生成処理では、一の濃度レベル（ｇ＋１）のドットプロファイルＰ（ｘ，ｙ；ｇ＋１）がスピン行列Ｓ（ｘ，ｙ）にコピーされ（ステップＳ５１）、スピン行列Ｓ（ｘ，ｙ）において、値が１であるスピンの座標の集合Ｈ（すなわち、ドットプロファイルＰ（ｘ，ｙ；ｇ＋１）において値が０のドットが追加可能である座標の集合）が求められる（ステップＳ５２）。また、濃度レベル（ｇ＋１）のドットプロファイルにおけるドット数ｎ（ｇ＋１）と対象濃度レベルｇのドットプロファイルにおけるドット数ｎ（ｇ）との差ｄｎが求められ、対象濃度レベルｇに合わせてドットプロファイルＰ（ｘ，ｙ；ｇ＋１）から削除されるドットの個数（すなわち、追加される値が０のドットの個数）が取得される（ステップＳ５３）。
【００７５】
スピン行列変更部３３１では座標集合Ｈからｄｎ個の座標が選択され、選択された座標の集合がＤ、残りの座標の集合がＵとされる（ステップＳ５４）。そして、スピン行列Ｓ（ｘ，ｙ）において、座標集合Ｄに含まれる全ての座標（ｘ，ｙ）の値が０とされ（ステップＳ５５）、エネルギー値算出部３３２により対象濃度レベルｇに対応するパラメータが数３に設定されるとともに（ステップＳ５６）、温度パラメータＴが初期値Ｔ０にセットされる（ステップＳ５７）。
【００７６】
続いて、座標集合Ｕから１つの座標（ｘ１，ｙ１）がランダムに選択され、座標集合Ｄからも１つの座標（ｘ２，ｙ２）がランダムに選択され、スピン行列Ｓにおいて座標（ｘ１，ｙ１）の対象スピンの値１と座標（ｘ２，ｙ２）の対象スピンの値０とが交換される（ステップＳ５８）。そして、エネルギー値算出部３３２において値を交換する前後のスピン行列Ｓにおけるエネルギー値の変化量ｄＥが求められる（ステップＳ５９）。
【００７７】
変化量ｄＥが求められると、擬似一様乱数ｐが取得され（ステップＳ６０）、擬似一様乱数ｐがｍｉｎ｛１，ｅｘｐ（−ｄＥ／Ｔ）｝よりも小さい場合に、ステップＳ５８における交換が許可され（ステップＳ６１）、座標（ｘ１，ｙ１）が座標集合Ｕから座標集合Ｄへと移動し、座標（ｘ１，ｙ１）が座標集合Ｄから座標集合Ｕへと移動する（ステップＳ６２）。一方、擬似一様乱数ｐがｍｉｎ｛１，ｅｘｐ（−ｄＥ／Ｙ）｝以上である場合には（ステップＳ６１）、ステップＳ５９における交換が元に戻される（ステップＳ６３）。そして、温度パラメータＴを小さくする場合には（ステップＳ６４）、温度パラメータＴがβ倍されて小さくされ（ステップＳ６５）、変更後の温度パラメータＴを用いてステップＳ５８〜Ｓ６５の処理が繰り返される（ステップＳ６６）。
【００７８】
エネルギー値の著しい変化がほとんどなくなると、ステップＳ５８〜Ｓ６５の処理の繰り返しが終了されて（ステップＳ６６）、エネルギー値が極小となるスピン行列Ｓ（ｘ，ｙ）が取得され、スピン行列Ｓ（ｘ，ｙ）が対象濃度レベルｇのドットプロファイルＰ（ｘ，ｙ；ｇ）として取得される（ステップＳ６７）。このとき、ドットプロファイルＰ（ｘ，ｙ；ｇ）において、濃度レベル（ｇ＋１）のドットプロファイルＰ（ｘ，ｙ；ｇ＋１）から削除されたドットの位置の組合せがディザマトリクスにおいて値ｇが付与される位置とされる。そして、取得されたドットプロファイルＰ（ｘ，ｙ；ｇ）をスピン行列Ｓ（ｘ，ｙ）への次のコピー対象として濃度レベルを更新しつつ、ステップＳ５１〜Ｓ６７が繰り返される（ステップＳ６８，Ｓ６９）。これにより、高濃度レベルから低濃度レベルに向かって順にドットプロファイルを生成することが実現される。
【００７９】
以上、スピンモデルを利用して中濃度範囲および高濃度範囲の各濃度レベルのドットプロファイルを生成する処理について説明を行ったが、上記処理において、スピン行列Ｓ（ｘ，ｙ）に対する処理がドットプロファイルに対して直接的に行われてもよい。
【００８０】
具体的には、マトリクス領域に最初の一の濃度レベルにおけるドットの配列を示す２値のドットプロファイルが取得され（ここでは、図７．ＡのステップＳ１２の処理に相当し、濃度レベルｇ１のドットプロファイルが取得されている。）、ドットが追加可能な位置が求められる（ステップＳ５２）。続いて、一の濃度レベルの次の対象濃度レベルに合わせてドットプロファイルに追加されるドットの個数が取得され（ステップＳ５３）、ドットプロファイルにドットを追加して変更後のドットプロファイルが生成される（ステップＳ５４，Ｓ５５）。また、数３に対象濃度レベルに対応するパラメータが設定され（ステップＳ５６）、温度パラメータＴが初期値Ｔ０とされる（ステップＳ５７）。
【００８１】
そして、追加されたドットのうち１つのドットをランダムに選択して位置が変更され（ステップＳ５８）、変更前のドットプロファイルのエネルギー値と変更後のドットプロファイルのエネルギー値との差が求められる（ステップＳ５９）。ここで、エネルギー値は変更後のドットプロファイルに含まれる２つのドットの各組合せについての相互作用エネルギーの総和であり、相互作用エネルギーは、２つのドット間の相対的な位置により決定されるとともに２つのドットが近接している場合に値が大きくなるものとされる。実際には、位置の変更前後でのエネルギー値の差は数４により追加されたドットの位置の変更に基づいて求められるが、本手法によりエネルギー値が適切な極小値をとるドットプロファイルが求められることを鑑みれば、ステップＳ５９の処理は実質的にエネルギー値を取得することと等価であるといえる。
【００８２】
続いて、擬似一様乱数ｐが取得されて追加されたドットの位置の変更を許可するか否かが判定され（ステップＳ６０〜Ｓ６１）、ドットの位置の変更を許可する場合にはドットの配置がそのままとされ（ステップＳ６２）、許可しない場合には位置が変更されたドットが元の位置へと戻される（ステップＳ６３）。そして、温度パラメータＴが適宜小さくされる（ステップＳ６４，Ｓ６５）。
【００８３】
上記ステップＳ５８〜Ｓ６５は、エネルギー値の著しい変化がほとんどなくなるまで繰り返される（ステップＳ６６）。すなわち、温度パラメータＴを適宜小さくしながらドットプロファイルに追加されるドットの位置を変更しつつ、変更後のドットプロファイルの生成とエネルギー値の実質的な取得とが繰り返され、焼きなまし法を利用して、追加されるドットの位置がエネルギー値を極小とする位置として決定される。このようにして、エネルギー関数を用いて一の濃度レベルのドットプロファイルから対象濃度レベルのドットプロファイルを生成する際に追加されるドットの位置が決定され、対象濃度レベルのドットプロファイルが取得される。
【００８４】
対象濃度レベルのドットプロファイルが取得されると、濃度レベルを更新しつつステップＳ５２へと戻り（ステップＳ６８，Ｓ６９）、さらに次の濃度レベルのドットプロファイルが取得される。これにより、中濃度範囲および高濃度範囲の各濃度レベルにおけるドットの配置を示すドットプロファイルが生成され、適切なディザマトリクスが生成される。
【００８５】
次に、本発明の第２の実施の形態に係るディザマトリクス生成処理について説明を行う。図１３は第２の実施の形態におけるディザマトリクス生成処理の概要を説明するための図である。本実施の形態では、全ての濃度範囲（ただし、最も低い濃度レベルおよび最も高い濃度レベルを除く。）に含まれる各濃度レベルのドットプロファイルが図７．Ａ中のステップＳ１２の第２ドットプロファイル生成処理にて生成される。実際には、０ないし２５５の２５６段階の濃度レベルのうち１ないし２５４の濃度レベルが図１３中に符号Ａ１〜Ａ５を付す矢印にてそれぞれ示す（濃度レベルおよび）複数の濃度範囲に大別され、濃度範囲Ａ１〜Ａ５毎にパラメータやドットプロファイルの取得順序を変更しつつ、濃度範囲Ａ１から濃度範囲Ａ５の順に第２ドットプロファイル生成処理が行われる。以下、各濃度範囲Ａ１〜Ａ５に対する処理を図１１および図１２に準じて説明を行う。なお、本実施の形態では、累積分布関数ｎ（ｇ）は、（ｎ（０）＝０）、および、（ｎ（２５５）＝Ｌｘ×Ｌｙ）となる線形関数であるものとする。
【００８６】
まず、濃度レベルＡ１（例えば、濃度レベル１２８）のドットプロファイルを生成する際には、マトリクス領域にドットが全く配置されていないドットプロファイル（例えば、濃度レベルが０のドットプロファイル）が準備され、全ての位置がドットが追加可能な位置とされる（ステップＳ５２）。続いて、濃度レベルＡ１に合わせてドットが全く配置されていないドットプロファイルに追加されるドットの個数ｎ（Ａ１）が取得され（ステップＳ５３）、ドットプロファイルにｎ（Ａ１）個のドットがランダムに追加されて変更後のドットプロファイルが生成される（ステップＳ５４，Ｓ５５）。また、数３に濃度レベルＡ１に対応するパラメータ（例えば、ｗ１が１．０、ｗ２が０．４、σ１が１．０、σ２が０．７５とされる。）が設定され（ステップＳ５６）、温度パラメータＴが初期値Ｔ０とされる（ステップＳ５７）。
【００８７】
そして、追加されたドットのうち１つのドットをランダムに選択して位置を変更し（ステップＳ５８）、変更前のドットプロファイルのエネルギー値と変更後のドットプロファイルのエネルギー値との差が、数４の演算を行うことにより求められる（ステップＳ５９）。また、擬似一様乱数ｐが取得されて選択されたドットの位置の変更を許可するか否かが判定され（ステップＳ６０〜Ｓ６１）、ドットの位置の変更を許可する場合にはドットの配置がそのままとされ、許可しない場合には位置が変更されたドットが元の位置へと戻される（ステップＳ６２，Ｓ６３）。そして、温度パラメータＴが適宜小さくされる（ステップＳ６４，Ｓ６５）。
【００８８】
上記ステップＳ５８〜Ｓ６５は、エネルギー値の著しい変化がほとんどなくなるまで繰り返されて（ステップＳ６６）、エネルギー値が極小となるドットプロファイルが濃度レベルＡ１のドットプロファイルとして取得される。
【００８９】
濃度レベルＡ１のドットプロファイルが生成されると、次に、濃度範囲Ａ２（例えば、濃度レベル１２９〜２２２）に含まれる各濃度レベルのドットプロファイルが生成される。濃度範囲Ａ２に含まれる各濃度レベルのドットプロファイルを生成する際には、濃度範囲Ａ２内において低濃度レベルから高濃度レベルに向かって順にドットプロファイルが生成される。
【００９０】
まず、上記濃度レベルＡ１に対する処理にて取得された濃度レベルＡ１のドットプロファイルにおいてドットが追加可能な位置が求められる（ステップＳ５２）。続いて、濃度レベルＡ１の次の対象濃度レベル（例えば、濃度レベル１２９）に合わせてドットプロファイルに追加されるドットの個数が取得され（ステップＳ５３）、ドットプロファイルにドットを追加して変更後のドットプロファイルが生成される（ステップＳ５４，Ｓ５５）。また、数３に濃度範囲Ａ２に対応するパラメータが設定され（パラメータは、例えば、ｗ１が１．０、ｗ２が０．４、σ１が１．０、σ２が０．７５とされ、既に設定されている場合にはこの処理はスキップされる。）（ステップＳ５６）、温度パラメータＴが初期値Ｔ０とされる（ステップＳ５７）。
【００９１】
上記と同様にして、エネルギー値の著しい変化がほとんどなくなるまでステップＳ５８〜Ｓ６５が繰り返され（ステップＳ６６）、エネルギー値が極小となるドットプロファイルが対象濃度レベルのドットプロファイルとして取得される。対象濃度レベルのドットプロファイルが取得されると、濃度レベルを更新しつつステップＳ５２へと戻り（ステップＳ６８，Ｓ６９）、さらに次の濃度レベルのドットプロファイルが取得される。これにより、濃度範囲Ａ２の各濃度レベルにおけるドットの配置を示すドットプロファイルが生成される。このとき、中濃度範囲（濃度レベル３３〜２２２）に含まれる濃度範囲Ａ１，Ａ２および後述する濃度範囲Ａ４では、同じパラメータを用いて低周波成分および高周波成分にペナルティを与え、ブルーノイズの特徴とされる周波数スペクトルのピークを有するドットプロファイルが生成される。
【００９２】
濃度範囲Ａ２の各濃度レベルのドットプロファイルが生成されると、次に、濃度範囲Ａ３（例えば、濃度レベル２２３〜２５４）に含まれる各濃度レベルのドットプロファイルが生成される。濃度範囲Ａ３に含まれる各濃度レベルのドットプロファイルを生成する際にも、濃度範囲Ａ２の場合と同様にして、濃度範囲Ａ３内において低濃度レベルから高濃度レベルに向かって順にドットプロファイルが生成される。ただし、濃度範囲Ａ３の場合には、数３に設定されるパラメータが、例えば、ｗ１が１．０、ｗ２が０、σ１が（α／ｓｑｒｔ（２５５−ｇ））（ただし、ｓｑｒｔ（２５５−ｇ）は（２５５−ｇ）の平方根を表し、ｇは対象濃度レベル、αは１０．０である。）とされ、この場合、数３の右辺の第１項のみが用いられることとなり、高濃度範囲である濃度範囲Ａ３では、２つのドット間の距離が近いほど値が大きくなる正規分布型の相互作用エネルギーの影響により値が０の空ドットが全体に均一に分布したドットプロファイルが生成される。
【００９３】
このようにして、濃度レベルＡ１より高い濃度範囲Ａ２，Ａ３に含まれる各濃度レベルのドットプロファイルが生成されると、次に、濃度レベルＡ１より低い濃度範囲Ａ４（例えば、濃度レベル３３〜１２７）に含まれる各濃度レベルのドットプロファイルが生成される。濃度範囲Ａ４に含まれる各濃度レベルのドットプロファイルを生成する際には、濃度範囲Ａ４内において高濃度レベルから低濃度レベルに向かって順にドットプロファイルが生成される。
【００９４】
まず、上記濃度レベルＡ１に対する処理にて取得された濃度レベルＡ１のドットプロファイルにおいてドットが削除可能な位置（すなわち、値が０のドットが追加可能な位置）が求められる（ステップＳ５２）。続いて、濃度レベルＡ１の次の対象濃度レベル（ここでは、より低い濃度レベルであり、例えば、濃度レベル１２７）に合わせてドットプロファイルから削除されるドットの個数が取得され（ステップＳ５３）、ドットプロファイルからドットを削除して変更後のドットプロファイルが生成される（ステップＳ５４，Ｓ５５）。また、数３に濃度範囲Ａ４に対応するパラメータ（例えば、ｗ１が１．０、ｗ２が０．４、σ１が１．０、σ２が０．７５）が設定され（ステップＳ５６）、温度パラメータＴが初期値Ｔ０とされる（ステップＳ５７）。
【００９５】
上記と同様にして、エネルギー値の著しい変化がほとんどなくなるまでステップＳ５８〜Ｓ６５が繰り返され（ステップＳ６６）、エネルギー値が極小となるドットプロファイルが対象濃度レベルのドットプロファイルとして取得される。対象濃度レベルのドットプロファイルが取得されると、濃度レベルを更新しつつステップＳ５２へと戻り（ステップＳ６８，Ｓ６９）、さらに次の濃度レベル（より低い濃度レベル）のドットプロファイルが取得される。これにより、濃度範囲Ａ４の各濃度レベルにおけるドットの配置を示すドットプロファイルが生成される。
【００９６】
濃度範囲Ａ４の各濃度レベルのドットプロファイルが生成されると、次に、濃度範囲Ａ５（例えば、濃度レベル１〜３２）に含まれる各濃度レベルのドットプロファイルが生成される。濃度範囲Ａ５に含まれる各濃度レベルのドットプロファイルを生成する際にも、濃度範囲Ａ４の場合と同様にして、濃度範囲Ａ５内において高濃度レベルから低濃度レベルに向かって順にドットプロファイルが生成される。ただし、濃度範囲Ａ５の場合には、数３に設定されるパラメータが、例えば、ｗ１が１．０、ｗ２が０、σ１が（α／ｓｑｒｔ（ｇ））（ただし、ｓｑｒｔ（ｇ）はｇの平方根を表し、ｇは対象濃度レベル、αは１０．０である。）とされ、この場合、数３の右辺の第１項のみが用いられることとなり、低濃度範囲である濃度範囲Ａ５では濃度範囲Ａ４と同様に、２つのドット間の距離が近いほど値が大きくなる正規分布型の相互作用エネルギーの影響によりドットが全体に均一に分布したドットプロファイルが生成される。
【００９７】
以上のように、第２の実施の形態に係るディザマトリクス生成処理では、最初の一の濃度レベルのドットプロファイルが取得されて準備され、続いて、最初の一の濃度レベルを除く全ての濃度レベルのそれぞれのドットプロファイルが相互作用エネルギーを利用してドットが均一に分布するようにして順次取得される。そして、最初の一の濃度レベルのドットプロファイル、および、各濃度レベルのドットプロファイルに対して決定された追加（または、削除）されるドットの位置の組合せがディザマトリクスとされ、これにより、第２の実施の形態に係るディザマトリクス生成処理では、適切なディザマトリクスを生成することができる。また、低濃度範囲、中濃度範囲および高濃度範囲でそれぞれパラメータを切り替えつつ数３により相互作用エネルギーを求めることにより、低濃度範囲および高濃度範囲においてドットが均一に分布するとともに、中濃度範囲においてブルーノイズの特徴とされる周波数スペクトルのピークを有する出力画像が生成可能なディザマトリクスを取得することができる。
【００９８】
なお、濃度レベルＡ１のドットプロファイルは、マトリクス領域の全ての位置にドットが配置されたドットプロファイル（例えば、濃度レベル２５５のドットプロファイル）から、ドットを削除することにより生成されてもよい。また、本実施の形態において数３に設定されるパラメータおよび大別される濃度範囲は、経験的に好ましいとされる一例であり、他のものとされてもよい。
【００９９】
以上、本発明の実施の形態について説明してきたが、本発明は上記実施の形態に限定されるものではなく、様々な変形が可能である。
【０１００】
上記第１の実施の形態において、低濃度範囲に含まれる各濃度レベルのドットプロファイル（例えば、ドット同士が接続しない程度の密度となるドットプロファイル）が第１ドットプロファイル生成処理により生成され、中濃度範囲および高濃度範囲の各濃度レベルのドットプロファイルが上述のものとは異なる方法による第２ドットプロファイル生成処理により生成されてもよい。
【０１０１】
他の第２ドットプロファイル生成処理としては、例えば、上述の特許文献１の手法を用いることができる。具体的には、中濃度範囲および高濃度範囲に含まれる対象濃度レベルのドットプロファイルを生成する際に、直前の一のドットプロファイルから追加されるドットの位置を、ドットプロファイルに対して人間の視覚特性に基づいて定義されたコスト関数（エネルギー関数）の値が小さくなるように焼きなまし法を用いて決定することにより、中濃度範囲および高濃度範囲の各濃度レベルのドットプロファイルが順次生成される。これにより、上記第１の実施の形態と同様に、低濃度範囲においては、第１ドットプロファイル生成処理により既存のドットから離れた位置にドットを追加して均一性の高いドットプロファイルを短時間に生成し、中濃度範囲および高濃度範囲においては、ドットの配置状態を数値化する所定のエネルギー関数を用いて一の濃度レベルのドットプロファイルから次の濃度レベルのドットプロファイルを生成する際に追加されるドットの位置が決定され、適切なディザマトリクスを容易に生成することができる。
【０１０２】
また、さらに他の第２ドットプロファイル生成処理として、上述の特許文献２の手法が用いられてもよく、この処理では、一の濃度レベルのドットプロファイルに、一の濃度レベルの次の対象濃度レベルに応じたブルーノイズ特性フィルタを作用させた画像が生成され、この画像と元のドットプロファイルとの差分画像（誤差画像）において濃度レベルが最大となる位置であって、元のドットプロファイル中において値が０の位置にドットを追加する（元のドットプロファイルを誤差画像に近づけることに相当する。）ことにより、中濃度範囲および高濃度範囲に含まれる各濃度レベルのドットプロファイルが順次生成される。さらに、中濃度範囲および高濃度範囲において、上述の特許文献３の手法が利用されてもよく、この手法では、一の濃度レベルのドットプロファイルに低域通過フィルタを作用させた画像（ぼかし画像）において濃度レベルが最小となる位置であって、元のドットプロファイル中において値が０の位置にドットを追加する（最も疎な部分にドットを追加することに相当する。）ことにより、中濃度範囲および高濃度範囲に含まれる対象濃度レベルのドットプロファイルが生成される。
【０１０３】
ここで、高濃度範囲におけるドットプロファイルの生成手法の違いが出力画像に与える影響は、一般的には、低濃度範囲および中濃度範囲に比べて小さいため、低濃度範囲および中濃度範囲の各濃度レベルのドットプロファイルの質がディザマトリクスの生成に際して重要となる。このような観点から、適切なディザマトリクスを短時間に生成するには低濃度範囲の各濃度レベルのドットプロファイルが第１ドットプロファイル生成処理により生成され、少なくとも中濃度範囲の各濃度レベルのドットプロファイルが第１ドットプロファイル生成処理とは異なる手法を利用して生成されることが重要となる。
【０１０４】
上記実施の形態において、相互作用エネルギーは、２つのドット間の相対的な位置により決定されるものであれば様々なものとすることができる。例えば、行方向と列方向とで単位距離当たりのドット数が異なる印刷装置にて印刷される出力画像や、行方向と列方向とで単位距離当たりの画素数が異なる表示装置にて表示される出力画像の生成に利用されるディザマトリクスの生成においては、２つのドット間の距離ｒを実際に印刷または表示される画像上での距離（または、この距離に比例する値）として数３に与えることにより、当該印刷装置または表示装置に合わせた適切なディザマトリクスを生成することができる。また、相互作用エネルギーは、行方向および列方向とこれらの方向に傾斜した方向とで異なる特性を示すものであってもよい。
【図面の簡単な説明】
【０１０５】
【図１】ディザ処理システムの機能構成を示す図である。
【図２】元画像をハーフトーン化する様子を説明するための図である。
【図３】元画像のハーフトーン化により生成された出力画像を示す図である。
【図４】コンピュータの構成を示す図である。
【図５】コンピュータが実現する機能構成を示す図である。
【図６】ディザマトリクスを生成する処理の概要を説明するための図である。
【図７．Ａ】ディザマトリクスを生成する処理の流れを示す図である。
【図７．Ｂ】ディザマトリクス生成処理の各工程に関係する濃度範囲を説明するための図である。
【図８】初期ドットプロファイル生成処理の流れを示す図である。
【図９】ボロノイ領域分割が行われたマトリクス領域を示す図である。
【図１０】第１ドットプロファイル生成処理の流れを示す図である。
【図１１】第２ドットプロファイル生成処理の流れを示す図である。
【図１２】第２ドットプロファイル生成処理の流れを示す図である。
【図１３】第２の実施の形態におけるディザマトリクス生成処理の概要を説明するための図である。
【符号の説明】
【０１０６】
７０    元画像
８１    ディザマトリクス
８１１〜８１４    ドットプロファイル
Ｓ１１〜Ｓ１３，Ｓ５３〜Ｓ５５，Ｓ５８，Ｓ５９，Ｓ６６，Ｓ６８，Ｓ６９    ステップ
【図１】
2006165930.tif 000008
【図２】
2006165930.tif 000009
【図３】
2006165930.tif 000010
【図４】
2006165930.tif 000011
【図５】
2006165930.tif 000012
【図６】
2006165930.tif 000013
【図７．Ａ】
2006165930.tif 000014
【図７．Ｂ】
2006165930.tif 000015
【図８】
2006165930.tif 000016
【図９】
2006165930.tif 000017
【図１０】
2006165930.tif 000018
【図１１】
2006165930.tif 000019
【図１２】
2006165930.tif 000020
【図１３】
2006165930.tif 000021