(57)【特許請求の範囲】
【請求項１】
画像を構成する複数の点の分散性を評価する分散評価装置であって、
評価対象となる注目点と、この注目点との距離が所定の限界値以内である他の点との間の距離、及び、他の点の密度に基づいて、注目点の分散性を示す評価値を算出する評価値算出手段
を有し、
前記評価値算出手段は、
注目点を基準とした所定の限界値以内の距離に他の点が複数存在する場合に、２つの点間の距離のみに依存する評価関数を他の点の密度で除算することによって、他の点それぞれについて２点間評価値を算出し、
他の点それぞれについて算出された２点間評価値の合算値を前記評価値とし、
前記評価値に基づいて分散性の良否を判断し、
前記評価関数は、２つの点の間の距離が限界値を超える場合に、関数値が０となり、かつ、この限界値以内の距離については単調減少な凸関数であり、この評価関数の導関数は、２つの点の間の距離の平方根に対して、凹関数となる
分散評価装置。
【請求項２】
前記評価関数は、２つの点の間の距離に対して、２階微分可能であり、かつ、この評価関数の微分係数は、連続である
請求項１に記載の分散評価装置。
【請求項３】
前記評価関数は、下記第１の条件
0004666223.tif 000009
、及び、第２の条件
0004666223.tif 000010
を満たすｆｒである
請求項１または２に記載の分散評価装置。
【請求項４】
評価対象となる注目点と、この注目点との距離が所定の限界値以内である他の点との間の距離、及び、他の点の密度に基づいて、注目点の分散性を示す評価値を算出する評価値算出手段と、
前記評価値算出手段により算出された評価値を用いて、所定の配置空間内における複数の点の配置を決定する配置決定手段と
を有し、
前記評価値算出手段は、
注目点を基準とした所定の限界値以内の距離に他の点が複数存在する場合に、２つの点間の距離のみに依存する評価関数を他の点の密度で除算することによって、他の点それぞれについて２点間評価値を算出し、
他の点それぞれについて算出された２点間評価値の合算値を前記評価値とし、
前記評価値に基づいて分散性の良否を判断し、
前記評価関数は、２つの点の間の距離が限界値を超える場合に、関数値が０となり、かつ、この限界値以内の距離については単調減少な凸関数であり、この評価関数の導関数は、２つの点の間の距離の平方根に対して、凹関数となる
配置決定装置。
【請求項５】
評価対象となる注目点と、この注目点との距離が所定の限界値以内である他の点との間の距離、及び、前記他の点の密度に基づいて、注目点の分散性を示す評価値を算出する評価値算出手段と、
前記複数の点のいずれかの仮配置を更新する配置更新手段と、
前記配置更新手段により仮配置が更新された複数の点について、前記評価値算出手段に評価値を算出させて、算出された評価値に基づいて、適用すべき配置を決定する配置決定手段と
を有し、
前記評価値算出手段は、
注目点を基準とした所定の限界値以内の距離に他の点が複数存在する場合に、２つの点間の距離のみに依存する評価関数を他の点の密度で除算することによって、他の点それぞれについて２点間評価値を算出し、
他の点それぞれについて算出された２点間評価値の合算値を前記評価値とし、
前記評価値に基づいて分散性の良否を判断し、
前記評価関数は、２つの点の間の距離が限界値を超える場合に、関数値が０となり、かつ、この限界値以内の距離については単調減少な凸関数であり、この評価関数の導関数は、２つの点の間の距離の平方根に対して、凹関数となる
配置決定装置。
【請求項６】
評価対象となる注目点と、この注目点との距離が所定の限界値以内である他の点との間の距離、及び、他の点の密度に基づいて、注目点の分散性を示す評価値を算出する評価値算出手段と、
前記評価値算出手段により算出された評価値を用いて、所定の画像内における複数の点の配置を決定する配置決定手段と
を有し、
前記評価値算出手段は、
注目点を基準とした所定の限界値以内の距離に他の点が複数存在する場合に、２つの点間の距離のみに依存する評価関数を他の点の密度で除算することによって、他の点それぞれについて２点間評価値を算出し、
他の点それぞれについて算出された２点間評価値の合算値を前記評価値とし、
前記評価値に基づいて分散性の良否を判断し、
前記評価関数は、２つの点の間の距離が限界値を超える場合に、関数値が０となり、かつ、この限界値以内の距離については単調減少な凸関数であり、この評価関数の導関数は、２つの点の間の距離の平方根に対して、凹関数となる
画像処理装置。
【請求項７】
画像を構成する複数の点の分散を評価する分散評価方法であって、
評価対象となる注目点と、この注目点との距離が所定の限界値以内である他の点との間の距離、及び、他の点の密度に基づいて、注目点の分散性を示す評価値を算出し、
前記評価値を算出することは、
注目点を基準とした所定の限界値以内の距離に他の点が複数存在する場合に、２つの点間の距離のみに依存する評価関数を他の点の密度で除算することによって、他の点それぞれについて２点間評価値を算出し、
他の点それぞれについて算出された２点間評価値の合算値を前記評価値とし、
前記評価値に基づいて分散性の良否を判断し、
前記評価関数は、２つの点の間の距離が限界値を超える場合に、関数値が０となり、かつ、この限界値以内の距離については単調減少な凸関数であり、この評価関数の導関数は、２つの点の間の距離の平方根に対して、凹関数となる
分散評価方法。
【請求項８】
所定の配置空間に配置された複数の点について、いずれかの点の仮配置を変更し、
評価対象となる注目点と、この注目点との距離が所定の限界値以内である他の点との間の距離、及び、他の点の密度に基づいて、少なくとも１つの点の仮配置が更新された配置空間について、評価値を算出し、
算出された評価値に基づいて、適用すべき配置を決定し、
前記評価値を算出することは、
注目点を基準とした所定の限界値以内の距離に他の点が複数存在する場合に、２つの点間の距離のみに依存する評価関数を他の点の密度で除算することによって、他の点それぞれについて２点間評価値を算出し、
他の点それぞれについて算出された２点間評価値の合算値を前記評価値とし、
前記評価値に基づいて分散性の良否を判断し、
前記評価関数は、２つの点の間の距離が限界値を超える場合に、関数値が０となり、かつ、この限界値以内の距離については単調減少な凸関数であり、この評価関数の導関数は、２つの点の間の距離の平方根に対して、凹関数となる
配置決定方法。
【請求項９】
所定の画像を構成する複数の点について、いずれかの点の仮配置を変更し、
評価対象となる注目点と、この注目点との距離が所定の限界値以内である他の点との間の距離、及び、他の点の密度に基づいて、仮配置が更新された点について評価値を算出し、
算出された評価値に基づいて、適用すべき配置を決定し、
前記評価値を算出することは、
注目点を基準とした所定の限界値以内の距離に他の点が複数存在する場合に、２つの点間の距離のみに依存する評価関数を他の点の密度で除算することによって、他の点それぞれについて２点間評価値を算出し、
他の点それぞれについて算出された２点間評価値の合算値を前記評価値とし、
前記評価値に基づいて分散性の良否を判断し、
前記評価関数は、２つの点の間の距離が限界値を超える場合に、関数値が０となり、かつ、この限界値以内の距離については単調減少な凸関数であり、この評価関数の導関数は、２つの点の間の距離の平方根に対して、凹関数となる
画像処理方法。
【請求項１０】
画像を構成する複数の点の分散を評価するコンピュータにおいて、
評価対象となる注目点と、この注目点との距離が所定の限界値以内である他の点との間の距離、及び、他の点の密度に基づいて、注目点の分散性を示す評価値を算出するステップ
を前記コンピュータに実行させ、
前記評価値を算出するステップは、
注目点を基準とした所定の限界値以内の距離に他の点が複数存在する場合に、２つの点間の距離のみに依存する評価関数を他の点の密度で除算することによって、他の点それぞれについて２点間評価値を算出し、
他の点それぞれについて算出された２点間評価値の合算値を前記評価値とし、
前記評価値に基づいて分散性の良否を判断し、
前記評価関数は、２つの点の間の距離が限界値を超える場合に、関数値が０となり、かつ、この限界値以内の距離については単調減少な凸関数であり、この評価関数の導関数は、２つの点の間の距離の平方根に対して、凹関数となる
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、既定の空間に配置された配置物の分散性を評価する分散評価装置、及び分散性の評価を用いて配置物の配置を決定する配置決定装置に関する。より具体的には、領域毎に異なる密度で配置された配置物の分散性を評価する分散評価装置及び既定の密度に応じて配置物の配置を決定する配置決定装置に関する。
【背景技術】
【０００２】
例えば、特許文献１は、エネルギー関数としてユークリッド距離関数を用いる形態を開示する。
また、特許文献２は、物理学のモデルに従った斥力緩和法による点分散の方法を開示する。
【特許文献１】特開２００４−２７２１９５号公報
【特許文献２】特開２００３−０６６２０８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、領域毎に異なる密度で配置された配置物の分散性を適切に評価することができる分散評価装置を提供することを目的とする。
【課題を解決するための手段】
【０００４】
［分散評価装置］
上記目的を達成するために、本発明にかかる分散評価装置は、複数の配置物の分散性を評価する分散評価装置であって、評価対象となる注目配置物と、この注目配置物を基準として既定の範囲内にある他の配置物との間の距離、及び、他の配置物に対応付けられた密度情報に基づいて、注目配置物の分散性を示す評価値を算出する評価値算出手段を有する。
【０００５】
好適には、前記評価値算出手段は、２つの配置物間の距離のみに依存する評価関数と、他の配置物に対応付けられた密度情報の逆数に比例する重み付け関数とを用いて、評価値を算出する。
【０００６】
好適には、前記評価値算出手段は、注目配置物を基準とした既定の範囲内に他の配置物が複数存在する場合に、前記評価関数及び前記重み付け関数を用いて、他の配置物それぞれについて２点間評価値を算出し、他の配置物それぞれについて算出された２点間評価値の合算値を前記評価値とする。
【０００７】
好適には、前記配置物は、画像を構成する点であり、それぞれの点に対応付けられた密度情報は、それぞれの画像領域における濃度値であり、前記評価値算出手段は、前記評価関数及び前記重み付け関数を用いて、画像における点の分散性を示す評価値を算出する。
【０００８】
好適には、前記評価関数は、１次元周期空間に配置された複数の点を評価する場合にこれら複数の点が略均等に配置されたときに全点間の関数値の総和平均が最小となる関数であり、かつ、２次元周期空間に複数の点が略均等に配置されたときの全点間の関数値の総和平均が局所的に最小となる関数である。
【０００９】
好適には、前記評価関数は、２つの配置物の間の距離が限界値を超える場合に、関数値が０となり、かつ、この限界値以内の距離については単調減少な凸関数であり、この部分評価関数の導関数は、２つの配置物の間の距離の平方根に対して、凹関数となる。
【００１０】
好適には、前記評価関数は、２つの配置物の間の距離に対して、２階微分可能であり、かつ、この評価関数の微分係数は、連続である。
【００１１】
好適には、前記評価関数は、下記第１の条件
0004666223.tif 000002
、及び、第２の条件
0004666223.tif 000003
を満たす。
【００１２】
［配置決定装置］
また、本発明にかかる配置決定装置は、注目配置物の分散性を評価する場合に、２つの配置物間の距離のみに依存する評価関数と、他の配置物に対応付けられた密度情報の逆数に比例する重み付け関数とを用いて、注目配置物の分散性を示す評価値を算出する評価値算出手段と、前記評価値算出手段により算出された評価値を用いて、所定の配置空間内における複数の配置物の配置を決定する配置決定手段とを有する。
【００１３】
また、本発明にかかる配置決定装置は、評価対象となる注目配置物と、この注目配置物を基準として既定の範囲内にある他の配置物との間の距離、及び、前記他の配置物に対応付けられた密度情報に基づいて、注目配置物の分散性を示す評価値を算出する評価値算出手段と、前記複数の配置物のいずれかの仮配置を更新する配置更新手段と、前記配置更新手段により仮配置が更新された複数の配置物について、前記評価値算出手段に評価値を算出させて、算出された評価値に基づいて、適用すべき配置を決定する配置決定手段とを有する。
【００１４】
［画像処理装置］
また、本発明にかかる画像処理装置は、注目ドットの分散性を評価する場合に、２つのドット間の距離のみに依存する評価関数と、他のドットに対応付けられた濃度情報の逆数に比例する重み付け関数とを用いて、注目ドットの分散性を示す評価値を算出する評価値算出手段と、前記評価値算出手段により算出された評価値を用いて、所定の画像内における複数のドットの配置を決定する配置決定手段とを有する。
【００１５】
［分散評価方法］
また、本発明にかかる分散評価方法は、複数の配置物の分散を評価する分散評価方法であって、評価対象となる注目配置物と、この注目配置物を基準として既定の範囲内にある他の配置物との間の距離、及び、他の配置物に対応付けられた密度情報に基づいて、注目配置物の分散性を示す評価値を算出する。
【００１６】
［配置決定方法］
また、本発明にかかる配置決定方法は、所定の配置空間に配置された複数の配置物について、いずれかの配置物の仮配置を変更し、注目配置物の分散性を評価する場合に、２つの配置物間の距離のみに依存する評価関数と、他の配置物に対応付けられた密度情報の逆数に比例する重み付け関数とを用いて、少なくとも１つの配置物の仮配置が更新された配置空間について、評価値を算出し、算出された評価値に基づいて、適用すべき配置を決定する。
【００１７】
［画像処理方法］
また、本発明にかかる画像処理方法は、所定の画像を構成する複数のドットについて、いずれかのドットの仮配置を変更し、仮配置が変更されたドットの分散性を評価する場合に、２つのドット間の距離のみに依存する評価関数と、他のドットに対応付けられた濃度情報の逆数に比例する重み付け関数とを用いて、仮配置が更新されたドットについて評価値を算出し、算出された評価値に基づいて、適用すべき配置を決定する。
【００１８】
［プログラム］
また、本発明にかかるプログラムは、複数の配置物の分散を評価するコンピュータにおいて、評価対象となる注目配置物と、この注目配置物を基準として既定の範囲内にある他の配置物との間の距離、及び、他の配置物に対応付けられた密度情報に基づいて、注目配置物の分散性を示す評価値を算出するステップを前記コンピュータに実行させる。
【発明の効果】
【００１９】
本発明の分散評価装置または配置決定装置によれば、領域毎に異なる密度で配置された配置物の分散性を適切に評価する、または配置物の配置を既定の密度に応じて適切に決定することができる。
【発明を実施するための最良の形態】
【００２０】
［背景］
まず、本発明の理解を助けるために、その背景及び概略を説明する。
デジタル画像処理におけるデジタルスクリーニング技術（２値化技術）では、白と黒の画素からなる２値画像によって擬似的に中間調のグレー値を表現し、複数の２値画像を重ねることで、例えばＣＭＹＫなどの擬似カラー画像を作成している。
２値画像には、主に網点と呼ばれる、複数個の点の密集により濃淡を表現するタイプ（網点画像と呼ぶ）と、複数個の分散した点により濃淡を表現するタイプ（分散ドット画像と呼ぶ）に分けられる。網点画像は、解像度は低いが安定した濃度表現が可能であり、分散ドット画像は、網点画像よりも高い解像性を表現できる。分散ドット画像の画質上の問題点として、ドットの分散性の良し悪しに起因するざらつきの発生が挙げられ、高品位な分散ドット画像を得るためには、ドットの分散性を高める必要がある。以下、分散ドット画像に関する問題点を整理する。
【００２１】
分散ドット画像の作成方法としては、誤差拡散法と分散ドットマスク法が知られている。誤差拡散法は、原画像である連続階調画像の各ドットを閾値と比較して「０」「１」の信号を発生させると同時に、比較誤差を周囲の未処理画素に重畳しながら２値化を行う方式であり、解像性の高い画像を得ることができ、ドットの分散性にも優れているが、固有のテクスチュアが発生する場合がある。分散ドットマスク法は、予め作成した固定サイズの分散ドット閾値マトリックスを原画像上に周期的にマスクしながら、閾値比較をして「０」又は「１」の信号を発生させる方式であり、一般にドットの分散性と解像性が高くなく、誤差拡散法の画質には劣るが、網点画像と同等の高速処理が可能である。
なお、誤差拡散法も分散ドットマスク法も、共に画質上の問題点を克服するために、これまで様々な改良が提案されてきているが、理論的に最良と言える方式の獲得までは至っていない。
【００２２】
なお、一例をあげると、誤差拡散法は、「Ｒ．Ｆｌｏｙｄ、Ｌ．Ｓｔｅｉｎｂｅｒｇ、"Ａｎ  ａｄａｐｔｉｖｅ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｓｐａｔｉａｌ  ｇｒｅｙ  ｓｃａｌｅ"、Ｐｒｏｃ．Ｓｏｃ．Ｉｎｆｏ．Ｄｉｓｐｌａｙ、１７、７５−７７（１９７６）．」に述べられており、分散ドットマスク法は、「Ｒ．Ｕｌｉｃｈｎｅｙ、"Ｔｈｅ  ｖｏｉｄ−ａｎｄ−ｃｌｕｓｔｅｒ  ｍｅｔｈｏｄ ｆｏｒ ｄｉｔｈｅｒ ａｒｒａｙ ｇｅｎｅｒａｔｉｏｎ"、 ｉｎ  Ｈｕｍ．Ｖｉｓｉｏｎ， Ｖｉｓｕａｌ Ｐｒｏｃｅｓｓ．， Ｄｉｇｉｔａｌ Ｄｉｓｐ．ＩＶ，Ｐｒｏｃ．ＳＰＩＥ、１９１３，３３２−３４３(１９９３)．」に述べられている。
また、これらを含む２値化技術全般の動向は、「Ｈ．Ｒ．Ｋａｎｇ、"Ｄｉｇｉｔａｌ  ｃｏｌｏｒ  ｈａｌｆｔｏｎｉｎｇ"、ＳＰＩＥ／ＩＥＥＥ  Ｓｅｒｉｅｓ  ｏｎ  Ｉｍａｇｉｎｇ  ｓｃｉｅｎｃｅ  &  ｅｎｇｉｎｅｅｒｉｎｇ（１９９９）．」に詳しい。
【００２３】
分散ドット画像の別の課題として、網点画像から分散ドット画像への変換、作成済みの分散ドット画像の画質改善、解像度変換、濃度変換、画質評価、などが挙げられる。一般に、分散ドット画像を含む２値画像は、データサイズが小さく改竄耐性が高い反面、画像変換を行うことが難しい。実際、改竄を認めない場合は別として、２値画像の画像変換は多くのところで必要になっている。例えば４００ｄｐｉの解像度で読み取った画像を６００ｄｐｉでプリントするような場合には１．５倍の解像度変換が必要となる。分散ドット画像は、一つ一つのドットが意味を持っているため、少しでもドットの点灯数を増減させたり、点灯位置を変えたりしただけでもドットの分散性が悪化し、見た目の画質を大きく低下させることにつながる。そのため、上述した各種の処理は、どれも難しいものとなっている。そして、やはりこれらの処理についても、ドットの分散性を理論的に保証した最良の方式の獲得までは至っていない。
【００２４】
以上をまとめると、分散ドットによる２値画像を理論的に保証しつつ高画質に処理する方式が必要となっている。
【００２５】
なお、誤差拡散法と分散ドットマスク法以外の分散ドット２値化技術に関して、特許文献１では、エネルギー関数としてユークリッド距離関数を利用した方法が開示され、特許文献２では、物理学のモデルに従った斥力緩和法による方法が開示されている。これらの技術における関数は、いずれも何らかのモデルを利用したものである。しかしながら、これらのモデルにおいては、いずれも幾何学的な考察が行われていないため、場合によってはパラメータ設定を行うなどして使用する必要があった。
なお、本願出願人は、幾何学的に保証されたエネルギーを用いて点分散の評価や作成を行う方法を特願２００５−０７９６１４において開示している。この方法では、点分散を幾何学的に保証しつつ点分散を得ることができるものの、いずれも密度が一定（固定濃度の画像、又は、均一な密度で配置された配置物など）である場合を対象としていた。そのため、領域毎に濃度（分散密度）が異なる分散ドット画像に関し、分散性の評価を行うことができなかった。
【００２６】
そこで、本実施形態における配置決定装置２は、ｎ次元ユークリッド空間に含まれる有界な部分空間Ｅ（ｎ）内に分散したｍ個の点からなる集合をＸとしたときに、各点ｘ、ｙ∈Ｘの間で生じる相互エネルギーｆｒ（｜ｘ−ｙ｜）と、各点ｙにおける点密度とに基づいて、集合Ｘのエネルギーを算出し、このＸのエネルギーを低下することによって点分散の分散性を高める。この方法により、２次元の幅ｗ、高さｈの有界な画像空間における分散ドット画像について、各領域の画像濃度を加味しつつ、ドットの分散性を向上させることができる。
なお、関数ｆｒは、本発明にかかる評価関数の一例であり、２階微分可能かつ各微分係数が連続で、少なくとも、ｆｒ（ｘ）＝０（ｘ≧ｒ）、０<ｒ<１／２・ｄｉａｍ（Ｅ（ｎ））を満たし、更に、ｆｒ（ｘ）が凸関数であり、関数ｆｒの導関数ｆｒ'についてｆｒ'（√ｘ）が凹関数であるものとすることができる。
なお、この条件を満たす関数ｆｒは、１次元周期的空間において、複数の点が均等に分散したときに、全てのｘ、ｙ∈Ｘに関する関数値ｆｒ（｜ｘ−ｙ｜）の総和平均が最小になることが数学的に保証された関数である。このとき、任意の点分散に対して、各点のエネルギーを測定し、測定した値が小さいほど、エネルギーが小さく、点分散の分散性が良いとすることができる。
また、上述したように、２次元のｗ×ｈピクセルの画像を扱うため、１／２・ｄｉａｍ（Ｅ（ｎ））は１／２・ｍｉｎ｛ｗ、ｈ｝で置き換えてもよい。
【００２７】
さらに、本実施形態における配置決定装置２は、上述の点分散の評価を利用して分散ドット２値画像を作成するほかに、任意の２値画像から分散ドット２値画像への変換、分散ドット２値画像の画質改善、分散ドット２値画像の解像度変換、分散ドット２値画像の濃度変換、分散ドット画像の画質評価、のそれぞれの処理を実行する。
【００２８】
これにより、本実施形態における配置決定装置２は、幾何学的に適切なエネルギー関数によって点分散の良さを評価しながら分散性を高めつつ、高画質な分散ドット画像処理を行うことができる。
【００２９】
なお、本実施形態では、画像を構成するドットを本発明にかかる配置物の一例として説明するが、配置物は、これに限定されるものではない。
例えば、別の例として、例えば、ある都市内に複数の店舗を配置するような場合、どの地域からもいずれかの店舗に近くなるように、効率的な店舗配置が求められる場合がある。この場合に、商圏人口などに応じた店舗の配置密度を実現することが望まれる。
さらに別の例として、例えば、単位立方体内に電子あるいは分子を均等に分散させた状態を用意し、各種の物理実験のシミュレートを行うような場合がある。この場合にも、電場などの影響として、電子あるいは分子の密度を制御する必要がある。
【００３０】
［ハードウェア構成］
次に、本実施形態における配置決定装置２のハードウェア構成を説明する。
図１は、本発明にかかる分散評価方法、配置決定方法及び画像処理方法が適応される配置決定装置２のハードウェア構成を、制御装置２０を中心に例示する図である。
図１に例示するように、配置決定装置２は、ＣＰＵ２０２及びメモリ２０４などを含む制御装置２０、通信装置２２、ＨＤＤ・ＣＤ装置などの記録装置２４、並びに、ＬＣＤ表示装置あるいはＣＲＴ表示装置及びキーボード・タッチパネルなどを含むユーザインターフェース装置（ＵＩ装置）２６から構成される。
配置決定装置２は、例えば、配置決定プログラム５（後述）がインストールされた汎用コンピュータであり、通信装置２２又は記録装置２４などを介して、空間上に配置すべき配置物に関する情報（例えば、配置物の数など）、及び、これらの配置物が配置される配置空間に関する情報（例えば、配置空間の形状、大きさなど）を取得し、取得された情報に基づいて、配置物の配置を決定する。
また、配置決定装置２は、配置物の位置情報、及び、配置空間に関する情報を取得し、取得されたこれらの情報に基づいて、配置物の分散性を評価する。
【００３１】
［配置決定プログラム］
図２は、制御装置２０（図１）により実行され、本発明にかかる配置決定方法を実現する分散化プログラム５の機能構成を例示する図である。
図２に例示するように、配置決定プログラム５は、データ入力部５００、記憶部５１０、予備処理部５２０、濃度特定部５３０、分散評価部５４０、配置更新部５５０、判定部５６０及びデータ出力部５７０を有する。
なお、配置決定プログラム５の全部又は一部をＡＳＩＣなどのハードウェアで実現してもよい。
【００３２】
配置決定プログラム５において、データ入力部５００は、通信装置２２（図１）又は記憶装置２４（図１）を介して、配置空間上に配置すべき配置物に関する情報（例えば、配置物の数など）、及び、この配置空間に関する情報（例えば、配置空間の形状、大きさなど）を点分散データとして取得し、取得された点分散データを記憶部５１０に出力する。
本例のデータ入力部５００は、入力された２値画像（分散ドット画像データ）を点分散データとして記憶部５１０に出力する。
【００３３】
記憶部５１０は、データ入力部５００から入力された点分散データを記憶する。
また、記憶部５１０は、予備処理部５２０、濃度特定部５３０、分散評価部５４０、配置更新部５５０及び判定部５６０に対して、ワークエリアを提供する。例えば、記憶部５１０は、データ入力部５００から入力された点分散データに加えて、予備処理部５２０により前処理された画像の点分散データ、分散性改善後の点分散データ、並びに、点分散評価に用いられる各種の途中演算結果及び処理パラメータなどを保持する。
【００３４】
予備処理部５２０は、入力された点分散データに対して、必要とされるさまざまな予備処理を行う。
本例では、２値の分散ドット画像の各種の処理を行うことが可能であるが、それぞれの処理に応じて必要な準備や処理工程が異なるため、予備処理部５２０は必要な処理を行う。一例を挙げると、分散ドット画像の解像度変換を行う場合には、予備処理部５２０は、分散評価部５４０及び配置更新部５５０等による分散性の改善処理を行う前に、原画像を所定解像度に解像度変換する。この場合に、解像度変換された画像に対して、分散評価部５４０及び配置更新部５５０等によって分散性の改善処理が施される。
【００３５】
濃度特定部５３０は、入力された点分散データに基づいて、各配置領域における配置物の密度を特定し、特定された密度を示す情報（密度情報）を分散評価部５４０に提供する。密度情報には、例えば、画像の濃度情報などが含まれる。
本例の濃度特定部５３０は、多値の画像データが入力された場合には、入力された画像データの画素値に基づいて、各画像領域における濃度値を特定し、２値の画像データが入力された場合には、２値画像を構成する複数のドットの分布に基づいて、各画像領域における濃度値を特定する。
【００３６】
分散評価部５４０は、記憶部５１０に記憶されている点分散データと、濃度特定部５３０により特定された密度情報とに基づいて、エネルギー値の評価を行う。
より具体的には、分散評価部５４０は、記憶部５１０に保持された点分散データの分散性の良さを、エネルギー関数によって評価する。このエネルギー関数Ｉ（Ｘ，ｆｒ）は、例えば、以下の式で表される。
【００３７】
Ｉ（Ｘ，ｆｒ）＝１／｜Ｘ｜・Σｘ∈ＸＩ（Ｘ，ｘ，ｆｒ）・・・（式１）
【００３８】
ここで、ｎ次元空間内の有界な配置空間をＥ（ｎ）とし、入力されたｎ次元配置空間Ｅ（ｎ）における点分散全体がＸ⊂Ｅ（ｎ）である。
また、関数ｆｒは、配置物の集合Ｘに含まれる各点（ｘ、ｙ∈Ｘ）の間で生じる相互エネルギーｆｒ（｜ｘ−ｙ｜）である。そして、各点エネルギー関数Ｉ（Ｘ，ｘ，ｆｒ）は、この相互エネルギーｆｒと、密度情報の逆数に比例する重み付け関数Ｐ（本例では、１／ｐ（ｙ））とからなる関数である。さらに、ｐ（ｙ）は、配置物が配置される点ｙに対応付けられた密度情報（本例では、点ｙにおける濃度値）である。したがって、各点エネルギー関数値Ｉは、ｆｒ／ｐ（ｙ）の各点平均値である。つまり、本例における各点エネルギー関数Ｉ（Ｘ，ｘ，ｆｒ）は、例えば、以下の式で表すことができる。
【００３９】
Ｉ（Ｘ，ｘ，ｆｒ）＝Σｙ∈Ｘｆｒ（｜ｘ−ｙ｜）／ｐ（ｙ）・・・（式２）
【００４０】
本例における各点エネルギーＩ（Ｘ，ｘ，ｆｒ）の定義式において、本来は空間の総点数｜Ｘ｜で除算するところを、点ｙの密度ｐ（ｙ）で除算していることが大きな特徴である。これは、局所的な点の総数（すなわち、局所的な濃度）で除算することで、異なる濃度で点が分散した状態においても、各点にそれぞれ適当な重みを与えたエネルギーで相互比較を可能にするための重要な工夫である。このようにすることで、注目点ｘの周囲に異なる濃度で点ｙが分散していても、それぞれｘとｙの間で働く相互エネルギーｆｒ（｜ｘ−ｙ｜）に、濃度による重みが掛けられ、点ｘとの間で生じる全ての各点エネルギーを平等にすることができる。この結果、簡単なエネルギー降下によって、分散ドット画像の濃度を保ったまま、ドットの分散性のみを向上させることができる。
【００４１】
相互エネルギーｆｒの関数（評価関数）ｆｒは、２階微分可能かつ各微分係数が連続で、ｆｒ（ｘ）＝０（ｘ≧ｒ）、０<ｒ<１／２・ｄｉａｍ（Ｅ（ｎ））を満たし、更にｆｒ（ｘ）が凸関数であり、ｆｒの導関数ｆｒ'についてｆｒ'（√ｘ）が凹関数であるものとする。
【００４２】
なお、上述における「ｎ次元空間」とは、より高次元のユークリッド空間に埋め込めるｎ次元空間全てを対象とする。
また、｜Ｘ｜は、Ｘの点の総数とする。
また、｜ｘ−ｙ｜は、Ｅ（ｎ）空間における点ｘとｙとの距離を意味する。例えば、Ｅ（ｎ）がｎ次元ユークリッド空間の部分集合の場合には、｜ｘ−ｙ｜は、ユークリッド距離で定義できる。また、ｄｉａｍ（Ｅ（ｎ））はＥ（ｎ）の直径、すなわちｓｕｐ｛｜ｘ−ｙ｜：ｘ、ｙ∈Ｅ（ｎ）｝とする。ここで、ｓｕｐは上限値を意味する。
【００４３】
なお、上記エネルギー関数の一般的な定義自体は、ポテンシャル理論の分野に属している。ポテンシャル理論では、例えば、エネルギーＩ（Ｘ）は、ｓを実数として以下の式で定義される。
【００４４】
Ｉ（Ｘ）＝∫∫｜ｘ−ｙ｜ｓｄμ（ｘ）ｄμ（ｙ）・・・（式３）
【００４５】
なお、本例の相互エネルギーｆｒは、本発明にかかる評価関数の一例である。また、各点エネルギーＩ（Ｘ，ｘ，ｆｒ）は、本発明にかかる評価値を算出する関数である。本例では、点分散性の改善処理を行う場合には、各点エネルギー関数Ｉ（Ｘ，ｘ，ｆｒ）を用い、画像全体の分散性を評価する場合には、全点エネルギーＩ（Ｘ，ｆｒ）を用いる。
【００４６】
配置更新部５５０は、記憶部５１０に記憶されている点分散データに対して、いずれかの配置物の仮配置位置を変更する配置更新処理を行う。
本例の配置更新部５５０は、分散評価値５２０により算出される各点エネルギー値を降下させるように、入力された２値画像のドットを移動させる。
【００４７】
判定部５６０（配置決定手段）は、分散評価部５４０による評価結果に基づいて、適用すべき点分散データを選択する。
また、判定部５６０は、分散性の評価のみを行う場合に、配置更新部５５０による点分散データの更新（ドットの移動）を禁止する。
また、判定部５６０は、分散性のよい配置を決定する場合に、配置更新部５５０に各配置物（ドット）を移動させ、必要に応じて分散評価部５４０に再び各点エネルギー値の算出を実行させる。あるいは、判定部５６０は、エネルギー値が既定の条件を満たすまで、分散評価部５４０による評価、及び、配置更新部５５０による配置更新処理を交互に繰り返させてもよい。
【００４８】
すなわち、分散評価部５４０、配置更新部５５０及び判定部５６０は、互いに協働して、点分散性の改善処理を行う。
【００４９】
データ出力部５７０は、分散評価部５４０による評価結果（算出された全点エネルギー値もしくはエネルギー降下すなわち分散性が改善された点分散データ）を、通信装置２２又は記憶装置２４に出力する。
【００５０】
以下、配置決定プログラム５による分散評価処理及び配置決定処理をそれぞれ説明する。なお、入力される点分散データが離散空間内で定義される場合を具体例として説明するが、これに限定されるものではなく、例えば、本配置決定プログラム５は、連続空間で定義された点分散データに関しても、密なメッシュで離散化することによって擬似的に取り扱うことができる。
【００５１】
［分散評価処理］
まず、分散評価処理を説明する。以下では、離散的な空間２５６×２５６ピクセル内に分散したｍ個の点の点分散の分散性を評価する例について説明する。
図３は、配置決定プログラム５（図２）による分散評価処理（Ｓ１０）のフローチャートである。
図３に示すように、ステップ１００（Ｓ１００）において、データ入力部５００は、通信装置２２（図１）又は記憶装置２４（図１）を介して、入力画像（配置空間）の形状及び大きさ、並びに、この入力画像における各ドットの位置を点分散データとして取得し、取得された点分散データを記憶部５１０に出力する。
分散評価部５４０は、データ入力部５００から入力された点分散データに応じて、ｎ次元配置空間内の有限集合Ｅ（ｎ）に含まれる点分散集合Ｘを準備する。本例では、Ｅ（ｎ）は、図４に例示するように、２５６×２５６のピクセル全体とする。また、ドットの集合Ｘは、このＥ（ｎ）の内部に定義されたｍ個の点の集合とする。
なお、本例では、説明の便宜のために、２５６×２５６の２値画像を具体例として説明するが、画像でなく一般の２５６×２５６の離散空間に置き換えてもよい。
【００５２】
ステップ１１０（Ｓ１１０）において、濃度特定部５３０は、入力されたドットの分布に基づいて、各ドット位置における濃度値を算出する。濃度値は、例えば、既定サイズの画像領域におけるドット点灯比率に基づいて算出される。
【００５３】
ステップ１２０（Ｓ１２０）において、判定部５６０は、分散評価処理を行うか配置決定処理を行うかを判定し、分散評価部５４０及び配置更新部５５０に対して、判定結果に応じた制御を行う。本例では、分散評価処理を行うため、判定部５６０は、分散評価処理を実施させるべく、配置更新部５５０に対して配置更新処理を禁止し、分散評価部５４０に対して分散評価処理を行うよう指示する。
分散評価部５４０は、入力された点分散データ、及び、濃度特定部５３０により算出された濃度値に基づいて、各ドット位置の各点エネルギーＩ（Ｘ，ｘ，ｆｒ）を算出する。
より具体的には、分散評価部５４０は、注目点ｘに関して、他の点ｙ（ｘ、ｙ∈Ｘ）との間で生じる相互エネルギーｆｒ（｜ｘ−ｙ｜）をそれぞれ算出し、算出された相互エネルギーｆｒを点ｙの濃度値ｐ（ｙ）で除算する。そして、分散評価部５４０は、集合Ｘに含まれる他の点ｙ全てについて算出されたｆｒ／ｐ（ｙ）を合算して、各点エネルギーＩ（Ｘ，ｘ，ｆｒ）を算出する。
すなわち、各注目点ｘの各点エネルギーＩ（Ｘ，ｘ，ｆｒ）は、以下の式で表される。
Ｉ（Ｘ，ｘ，ｆｒ）＝Σｙ∈Ｘｆｒ（｜ｘ−ｙ｜）／ｐ（ｙ）
【００５４】
なお、各点エネルギーＩ（Ｘ，ｘ，ｆｒ）は、関数ｆｒの性質によって、図５に示すように、注目点ｘ（ｘ∈Ｘ）を中心とする半径ｒの領域内にある全ての点ｙ（ｙ∈Ｘ）について、ｆｒ（｜ｘ−ｙ｜）／ｐ（ｙ）を計算してその和を取った値である。
半径ｒよりも外側の点（白抜きの丸）は、ｆｒ（ｘ）＝０（ｘ≧ｒ）の条件に基づいて無視される。
【００５５】
ステップ１３０（Ｓ１３０）において、分散評価部５４０は、算出された各点（注目点ｘ）の各点エネルギーＩ（Ｘ，ｘ，ｆｒ）に基づいて、配置空間全体のエネルギーＩ（Ｘ，ｆｒ）（以下、全点エネルギー）を算出する。
より具体的には、分散評価部５４０は、各点エネルギーを合算し、この合算値を、集合Ｘに含まれる点の数（｜Ｘ｜＝ｍ）で除算して、全点エネルギーＩ（Ｘ，ｆｒ）を算出する。
すなわち、対象となる配置空間の全点エネルギーＩ（Ｘ，ｆｒ）は、以下の式で表される。
Ｉ（Ｘ，ｆｒ）＝１／｜Ｘ｜・Σｘ∈ＸＩ（Ｘ，ｘ，ｆｒ）
【００５６】
換言すると、全点エネルギーＩ（Ｘ，ｆｒ）は、全配置物（すなわち、全てのｘ∈Ｘ）に対する各点エネルギーの平均値として算出される。
【００５７】
ステップ１４０（Ｓ１４０）において、データ出力部５７０は、分散評価部５４０により算出された全点エネルギーＩ（Ｘ，ｆｒ）を、点分散性の評価値として出力する。
なお、データ出力部５７０は、全点エネルギーＩ（Ｘ，ｆｒ）に加えて、各点のエネルギーＩ（Ｘ，ｘ，ｆｒ）を、分散性の評価値として出力してもよい。
【００５８】
このように、配置決定プログラム５（図２）は、２値画像を構成するドット間の距離に基づいて、各点エネルギーＩ（Ｘ，ｘ，ｆｒ）及び全点エネルギーＩ（Ｘ，ｆｒ）を算出し、ドットの分散性の評価値として出力する。
【００５９】
［境界条件について］
配置空間に応じた２点間（注目点ｘと対象点ｙ）の距離｜ｘ−ｙ｜の取り方を説明する。
本実施形態で算出される各点エネルギーＩ（Ｘ，ｘ，ｆｒ）は、注目した点ｘとその他の点ｙ全てとの間で生じるエネルギー値の濃度に応じた重み付け合算値として定義されている。
このような場合、考察する配置空間に対称性がない場合、つまり境界領域が存在する場合に、取り扱いに面倒が生じる。
図６は、配置空間における境界領域を例示する図である。
図６に例示するように、配置空間Ｅ（ｎ）は、主走査方向及び副走査方向に２５６ピクセルの２次元空間である。図６中のハッチングで示した領域は、配置空間Ｅ（ｎ）の周縁部から、限界距離ｒまでの領域である。ここで、限界距離ｒとは、相互エネルギーｆｒが有意な値（０以外の値）をとりうる範囲を示す値である。限界距離ｒよりも離れた点間では、相互エネルギーｆｒの値が０となる。換言すると、注目点ｘとの距離が限界距離ｒよりも遠い他の点ｙ（対象点ｙ）は、この注目点ｘのエネルギーに影響を与えない。
図６に示すハッチング領域内にある任意の注目点ｘ（ｘ∈Ｘ）を考えた場合に、注目点ｘを中心として半径ｒの範囲を考察すると、図６に示すように２５６×２５６の外周の外側にはみ出てしまい、正しい計算ができない場合がある。このような場合には、予め２５６×２５６を含むより大きな空間Ｙの一部として２５６×２５６を入力して、注目点ｘとしてはＸの点全体を動かし、対象点ｙとしてはＹの点全てを対象とするようにしてもよい。あるいは、図６に示すように、配置空間からはみ出した領域には点がないものとして処理してもよい。もちろん外周部分の不具合によって評価結果に不都合が生じるような場合もあるが、そのような場合には、対象とする空間をより大きく（例えば１０２４×１０２４など）選択することによって、その不都合が減少し、より分散性の良い点分散を、よりエネルギーが低いと判定することができる。
【００６０】
［相互エネルギーｆｒについて］
分散評価部５４０により適用されるエネルギー関数ｆｒは、ｆｒと同様の性質を持ち、［０，１］閉区間で定義された関数ｈ（ｘ）を用いて、
0004666223.tif 000004
と表すことができる。なお、このようにして［０，１］閉区間で定義された関数ｈ（ｘ）を与えてｆｒ（ｘ）を定義すると、ｒを含まない一般の関数ｈ（ｘ）を使ってｆｒ（ｘ）を構成できるという利点がある。図７に実線で示したグラフは、エネルギー関数ｆｒを構成する関数ｈ（ｘ）の一例であり、ｈ（ｘ）＝（２／３―ｘ＋１／３・ｘ３）２のグラフである。
分散評価部５４０により適用される関数ｆｒ（相互エネルギーを求める関数）の条件として、ｆｒ（ｘ）＝０（ｘ≧ｒ）、０<ｒ<１／２・ｄｉａｍ（Ｅ（ｎ））、ｆｒ（ｘ）が凸関数であり、ｆｒの導関数ｆｒ'についてｆｒ'（√ｘ）が凹関数であり、更にｆｒ（ｘ）は２階微分可能かつ各微分係数が連続としていた。ここで、ｆｒ（ｘ）を上記のようにｈ（ｘ）による合成関数として定義すると、ｆｒ（ｘ）が上記各条件を満たすためには、上記の各条件におけるｆｒをｈに置き換えて条件が満たされれば良いということがわかる。
【００６１】
図７に例示するエネルギー関数ｈ（ｘ）も、上記条件の全てを満たすことを確認することができる。実際に、図７に実線で示すとおり、ｈ（ｘ）は凸形をしている（更にｈ（ｘ）の導関数ｈ'（√ｘ）が凹形となる）。そして、上述したようにこの性質は合成関数であるｆｒ（ｘ）についても成立する。
本実施形態における分散評価部５４０は、上記条件を満たしさえすればどのような関数を使ってもよいことが大きな特徴であるが、本例では、図７に例示するエネルギー関数ｈ（ｘ）を、関数ｆｒを実現する具体例として用いる。なお上記条件を満たす関数はその他にも数多くあるが、一例としては、
ｈ（ｘ）＝（１−ｘ）ｐ（但しｐ≧２）
があげられる。
一方、上述した従来の関数の一例であるｅｘｐ（−ｘ２／（２σ２））は、同じく図７に点線で示したグラフであり、凸性や凹性を持っていない。なお、この従来の関数（点線）は、その形態がｈ（ｘ）に近くなるように、パラメータσの値を調整したもの（σ＝０．２２）であり、σの調整を行っていない場合には、更にｈ（ｘ）と異なる形態を有することになる。なお、従来例では、この関数に限らず関数に数学的な保証がないために、このようなパラメータ調整が必要となる場合が多い。
【００６２】
［画像改善処理］
次に、画像改善処理を説明する。本例では、２５６×２５６ピクセルの２値画像を処理対象とし、この画像内に分散したｍ個の黒ドットについて、各画像領域の濃度を維持しつつ、より分散性の良い２値画像を作成する形態を具体例として説明する。
処理対象となる２値画像は、網点画像でも、分散ドット画像でもよい。また、本例では、入力された２値画像に対して、連続階調画像の原画像が存在する場合と、存在しない場合を共に前提として説明を行う。
【００６３】
図８は、配置決定プログラム５（図２）による画像改善処理（Ｓ２０）のフローチャートである。なお、本例では、「局所振動法」を用いた形態を具体例として説明するが、これに限定されるものではなく、分散評価部５４０により算出されるエネルギー値が降下する方法であれば、どのような方法でもよい。
【００６４】
図８に示すように、ステップ２００（Ｓ２００）において、データ入力部５００（図２）は、通信装置２２（図１）又は記憶装置２４（図１）を介して、入力された２値画像の形状及び大きさ、並びに、この２値画像における各黒ドットの位置を点分散データとして取得し、取得された点分散データ（すなわち、２値画像の画像データ）を記憶部５１０に出力する。
なお、本例では、黒ドットを配置物として分散性を評価し、配置の更新を行うが、白ドットを配置物として処理してもよい。
【００６５】
ステップ２０２（Ｓ２０２）において、予備処理部５２０（図２）は、記憶部５１０に展開された２値画像に対して、要求された処理に対して必要な前処理を実行する。すなわち、予備処理部５２０は、記憶部５１０に展開された２値画像に対して解像度変換などの画像処理を施す。なお、予備処理部５２０による前処理は必須ではなく、前処理が行われない場合には、本画像改善処理により、ドットの分散性が改善される。
【００６６】
例えば、解像度変換が要求された場合には、予備処理部５２０は、例えば、最近傍法などにより２値画像を構成する黒ドット及び白ドットの数を変更する。この場合に、黒ドット及び白ドットの数、並びに、２値画像の大きさなどが変化するため、点分散データが更新されることになる。
また、濃度変換が要求された場合には、予備処理部５２０は、入力された２値画像（及び、連続階調画像）について、濃度変換を行う。すなわち、連続階調画像の濃度変換は、各ピクセルに固定濃度比率を乗算し、２値画像の濃度変換は、該固定比率に基づいて所定数の画素値（黒ドットと白ドット）を反転させればよい。この場合にも、黒ドット及び白ドットの数が変化するため、点分散データが更新されることになる。
【００６７】
ステップ２０４（Ｓ２０４）において、濃度特定部５３０は、記憶部５１０に展開されている２値画像の各黒ドットの位置について、濃度値を特定する。濃度値の特定は、例えば、連続階調画像の原画像が存在する場合には、現画像の画素値そのものとすればよいし、連続階調画像の原画像が存在しない場合には、該２値画像の各黒ドットを中心とした既定サイズの画像領域における黒ドットの割合に基づいてなされる。
【００６８】
ステップ２０６（Ｓ２０６）において、判定部５６０は、ドットの配置改善処理を行うべく、配置更新部５５０に仮配置更新処理を指示する。
配置更新部５５０は、２値画像を構成する黒ドットの集合Ｘの中から、処理対象となる注目ドットｘを設定し、この注目ドットｘを既定の位置に仮変位させる。注目ドットｘを仮変位させる既定位置は、例えば、注目ドットｘを中心とした３×３ピクセルのいずれかである。
【００６９】
ステップ２０８（Ｓ２０８）において、判定部５６０は、この仮変位後の注目ドットｘについて、各点エネルギーＩ（Ｘ，ｘ，ｆｒ）を算出するよう分散評価部５４０に指示する。
分散評価部５４０は、記憶部５１０に展開されている２値画像の点分散データに応じて、ｎ次元配置空間内の有限集合Ｅ（ｎ）に含まれる点分散集合Ｘを準備する。本例では、図４に例示するように、ｎ＝２として、Ｅ（ｎ）を２５６×２５６のピクセル全体とする。また、２値画像を構成する黒ドットの集合Ｘは、このＥ（ｎ）の内部に定義されたｍ個の点の集合であり、初期配置データして設定される。
【００７０】
分散評価部５４０は、仮変位後の注目ドットｘについて、各点エネルギーＩ（Ｘ，ｘ，ｆｒ）を算出する。
なお、本ステップにおける各点エネルギーＩの算出は、図３に示したＳ１２０と実質的に同一である。
また、各点エネルギーＩは、注目した黒ドットと周囲の黒ドットとの間で生じるエネルギーを算出している。したがって、画像の縁部分では例外処理が必要となる。図６に示すように、外枠を２５６×２５６の外周として、同じく図６にハッチングで示した領域内にある任意の黒ドットｘ∈Ｘを考えた場合に、黒ドットｘを中心として半径ｒの範囲を考察すると、図６に示すように２５６×２５６の外周の外側にはみ出てしまう。このような場合には、予め２５６×２５６（画像領域）の外側に仮想的に幅ｒの枠を設けて、２５６×２５６の外周の画素をコピーして加えた（２５６＋２ｒ）×（２５６＋２ｒ）の空間をＸに置き直すようにしてもよいし、注目ドットｘが２５６×２５６の外周に来たときにのみ、仮想的に外周の外側にもコピーされた黒ドットが存在するものとしてエネルギー計算してもよい。
【００７１】
ステップ２１０（Ｓ２１０）において、判定部５６０は、この注目ドットｘを全ての既定位置（注目ドットｘを中心とした９ピクセル）で仮変位させ、それぞれの仮変位後に各点エネルギーを算出したか否かを判定し、全ての仮変位点で各点エネルギーが算出された場合に、Ｓ２１２の処理に移行し、これ以外の場合に、Ｓ２０６の処理に戻って、次の変位位置について各点エネルギーを算出する。
【００７２】
ステップ２１２（Ｓ２１２）において、判定部５６０は、この注目ドットｘを仮変位させて算出された各点エネルギーの中から、各点エネルギーが最も小さい仮変位位置を配置更新部５５０に通知する。
配置更新部５５０は、判定部５６０からの通知に応じて、最も各点エネルギーの小さい仮変位位置に、この注目ドットｘを配置し、Ｘを更新する。
【００７３】
ステップ２１４（Ｓ２１４）において、判定部５６０は、黒ドットの集合Ｘに含まれる全てのドットｘについて、Ｓ２０６〜Ｓ２１２の処理を行ったか否かを判定し、未処理の黒ドットｘが存在する場合に、Ｓ２０６の処理に戻って、未処理の黒ドットｘを注目ドットとしてＳ２０６〜Ｓ２１２の処理を行い、全ての黒ドットｘについて処理が終了した場合に、Ｓ２１６の処理に移行する。
【００７４】
ステップ２１６（Ｓ２１６）において、判定部５６０は、Ｓ２０６〜Ｓ２１４の処理が既定の回数だけ繰り返されたか否かを判断し、繰返し回数が既定回数以上である場合に、Ｓ２２０の処理に移行し、繰返し回数が既定回数未満である場合に、Ｓ２１８の処理に移行する。
すなわち、配置決定プログラム５は、Ｓ２０６〜Ｓ２１４の処理が既定の回数以上繰り返された場合に、各点が収束して最適な地点に移動し終えたと判断する。
【００７５】
ステップ２１８（Ｓ２１８）において、判定部５６０は、Ｓ２０６〜Ｓ２１４の処理が施された黒ドットの集合Ｘ'を、初期配置データに設定して、Ｓ２０６の処理に戻る。
すなわち、配置決定プログラム５は、Ｓ２０６〜Ｓ２１４の処理が既定の回数以上繰り返されていない場合に、各点が収束し終えていないと判断し、この処理後の黒ドットの集合Ｘ'を初期状態として、Ｓ２０６〜Ｓ２１４の処理を繰り返す。
【００７６】
ステップ２２０（Ｓ２２０）において、判定部５６０は、初期配置データ（収束するまで更新が繰り返された集合Ｘの配置）を、最適な配置として出力するようデータ出力部５７０に指示する。
データ出力部５７０は、初期配置データを、分散性が改善された２値画像のデータとして出力する。なお、データ出力部５７０は、分散性が改善された２値画像のデータと共に、算出された各点エネルギーＩ（Ｘ，ｘ，ｆｒ）及び全点エネルギーＩ（Ｘ，ｆｒ）を、この画像データの評価値として出力してもよい。
【００７７】
このように、配置決定プログラム５は、画像領域における濃度値に加味してドットの分散性を評価しながら、エネルギーを降下させることにより、画像処理が施された２値画像のドットの分散性を改善させる。
また、このように改善された２値画像は、濃度情報の精度次第で誤差拡散法と同等の高解像度を実現し、しかも誤差拡散法に特有のテクスチュアを発生させない、高画質な画像となる。
なお、以上の説明においては、連続階調画像の原画像が存在する場合と存在しない場合を共に扱ってきたが、例えば画像の２値化処理は前者に相当し、２値画像の解像度変換や色変換などの処理は一般に後者に相当する。連続画像の２値化処理も、このように一旦仮２値化した画像の分散性を上げるという見方をすることで本例の方法を適用することができる。
【００７８】
図９は、解像度変換された画像に対する画像改善効果を説明する図である。
図８のＳ２０２において、予備処理部５２０が、図９（Ａ）に例示するｗ×ｈピクセルの原画像を、最近傍法でＷ×Ｈピクセルに解像度変換すると、図９（Ｂ）に例示するような画像（解像度変換済み）が生成される。
解像度変換された２値画像に関し、黒ドットに注目して考えると、図９に例示するように、各１×１ピクセルの黒ドットが各２×２の黒ドットに変換される。
これが、図８のＳ２０６〜Ｓ２２０の処理によって、各２×２ピクセル内にある４つの黒ドットが、エネルギー降下によってそれぞれ互いに分散してゆき、図９（Ｃ）に例示する分散性のよい２値画像になる。
つまり、一旦解像度変換することによって外見上ドットがクラスター化しても、エネルギー降下によって再び原画像と同じ大きさの画素サイズで分散してゆく。原画像のドット分散性は、エネルギー降下によってより分散性の良い画像に変換されるので、解像度変換とドット分散性の改善を同時に行っていることになる。
【００７９】
なお、本例のエネルギー関数として、ｆｒ（ｘ）を、２階微分可能かつ各微分係数が連続であるという条件を満たすように選択すると、エネルギー関数自体が、点ｘの局所的な移動に対して微分可能となる。従って、図８に示したような局所振動によるエネルギー降下アルゴリズムを行っても、極小解に陥りにくいという性質を持っている。ｒ値は固定してよく、黒ドット（又は白ドット）の数（濃度）が増減しても、収束に全く問題を生じない。実際には、離散空間の制約上、点の数が増大するにつれて、点の配置に大きな制約が掛かる。この場合、ｒ値を小さく取ると、エネルギー値に及ぼす各点の比率が高くなり、誤差が大きくなる可能性がある。また、逆にｒが大きすぎると、参照する点の数が増大するため処理速度の低下となる。これらの点からｒ値はある程度大きく、例えば１０程度に取るのが好ましい。２０×２０以下の小画像を処理する場合には、ｒ＝１／２・ｍｉｎ｛ｗ、ｈ｝−１（ｗ、ｈはそれぞれ主走査方向、副走査方向のピクセル数）などとすればよい。
【００８０】
ここで、関数ｆｒが、ｆｒ（ｘ）＝０（ｘ≧ｒ）、０<ｒ<１／２・ｍｉｎ｛ｗ、ｈ｝を満たし、少なくともｆｒ（ｘ）が凸関数であり、ｆｒの導関数ｆｒ'についてｆｒ'（√ｘ）が凹関数であり（条件Ａ）、更にｆｒ（ｘ）は２階微分可能かつ各微分係数が連続である（条件Ｂ）場合の理論的な効果をまとめる。条件Ａによって、周期的１次元空間において点が均等に分散した際にエネルギーが最小化することが幾何学的に保証され、条件Ｂによって局所的な極小解に陥ることを防いでいる。ｒの値は予め大きな値を設定しておけばよいだけなので、エネルギー関数ｆｒは、実質上パラメータ設定が一切必要なく、また極小解に陥りにくいという性質から、収束のアルゴリズムにもより依存しないものとなっている。
【００８１】
エネルギー関数の条件として、更に２次元固有のより強い条件を課してもよい。実際、ｆｒが更に以下の２条件満たすことで、２次元における局所的なエネルギー安定性を保証できる。つまり、Ｘを２次元平面内の三角格子配置した点集合とした場合に、
0004666223.tif 000005
及び、
0004666223.tif 000006
の２条件を加えることで、三角格子配置時に局所的なエネルギー安定性を保証できる。ここで、三角格子を考慮しているのは、２次元平面で最も点が均等に配置した状態が三角格子配置だからである。なお、実施例で述べた、ｈ（ｘ）による具体的な関数ｆｒは、実際これらの２条件をも満たしていることが確認できる。なお、より安全を期すならば、これらの条件を満たす関数ｈ（ｘ）に対して、ｈ（ｘ）をｐ乗（ｐ≧１）した関数を新たにｈ（ｘ）と置き直すことによってより強い凸性を与えた関数を使用することができる。この、強い凸性を与えることでより安全になるであろうという推定は、１次元解及び２次元での部分解における考察から導出されるものである。
【００８２】
ｆｒ（ｘ）に対する上述した全ての条件を満たす関数として、
0004666223.tif 000007
と置いた場合に、例えば以下の関数を挙げることができる。
0004666223.tif 000008
このようにして定義されたｆｒは上述した全ての条件を満たすことが確認できる。なお、この関数ｈ（ｘ）の形態は図７に実線で示すとおりであり、ｈが凸形をしている（更にｈ'（√ｘ）が凹形となる）。
【００８３】
次に、上記したように、集合Ｘとして分散ドットのうちの黒ドットでも白ドットでも、どちらを設定してもよい。この場合、上述のエネルギー降下処理において、黒ドット、白ドットを問わず、ドット数が少ない（低濃度）領域においてエネルギー降下の結果、ざらつきが残る場合がある。これは、エネルギー関数を、任意の濃度を同時に扱い得るようにするために、
Ｉ（Ｘ，ｘ，ｆｒ）＝Σｙ∈Ｘｆｒ（｜ｘ−ｙ｜）／ｐ（ｙ）
で定義していることに起因する。ここで、点ｙの濃度ｐ（ｙ）で各点間のエネルギーを除算して、濃度によって各点の重みを変える効果を与えている。ところが、低濃度領域においては、点灯しているドットの数が少ないため、相対的に、一点のドットの点灯がエネルギーＩ（Ｘ，ｘ，ｆｒ）に与える影響が大きくなり、点ｙの濃度ｐ（ｙ）による重み効果で吸収できる以上の誤差を与えやすくなるため、エネルギー降下によってドットの分散性にざらつきが残りやすくなる。
このような点を鑑みて、エネルギー降下を変形させてもよい。例えば、変形例として、黒ドットと白ドットの両方のエネルギーを考慮する、あるいは濃度によって黒ドットと白ドットのエネルギーを切り換える、あるいはブレンドする、などの方法を使用してもよい。黒ドットと白ドットの両方のエネルギーを考慮する場合には、注目ドットを他の点に移動するということを、黒ドットと白ドットを入れ替えるとみなし、それぞれ入れ替えた黒ドットと白ドットで共にエネルギー降下した場合にのみ、入れ替えを成立させる、などの方法を採ることができる。これにより、例えば黒ドットの低濃度側の処理では同時に白ドットの高濃度側が考慮されるので、全体にザラツキを緩和することができる。なお、このように黒ドットと白ドットの両方を処理の対象とする場合、Ｘ１（黒ドット）、Ｘ２（白ドット）という、互いに反転の関係にある二つの分散ドット画像のエネルギーを降下させると考えればよい。
【００８４】
以上説明したように、分散ドット画像の「分散性の良さ」に関わる処理は、エネルギー降下の概念で全て対応することができる。その一方で、分散ドット画像の解像度に関わる部分は、本質的には分散ドットの良さとは無関係であり、本例においては、連続階調の原画像の解像度に大きく依存している。したがって、連続階調の原画像が存在する場合には、高解像度の分散ドット画像を作成できるが、連続階調の原画像が存在しない場合には、分散性は充分に向上できても、解像度自体は低いままとなる。これは、２値の原画像から連続階調の原画像を推定する際に、原画像の解像度を充分に推定できないという理論的な限界に起因している。言い換えれば、本例の方法は、分散ドット画像の画質に関わる「分散性」と「解像度」のうち、解像度を最大限保ちつつ、分散性を理論的な限界近くまで改善する方式であると言える。
【図面の簡単な説明】
【００８５】
【図１】本発明にかかる分散評価方法、配置決定方法及び画像処理方法が適応される配置決定装置２のハードウェア構成を、制御装置２０を中心に例示する図である。
【図２】制御装置２０（図１）により実行され、本発明にかかる配置決定方法を実現する分散化プログラム５の機能構成を例示する図である。
【図３】配置決定プログラム５（図２）による分散評価処理（Ｓ１０）のフローチャートである。
【図４】２５６×２５６ピクセルの２値画像と、この２値画像を構成するｍ個の黒ドットとを例示する図である。
【図５】相互エネルギーｆｒに対して設定された限界距離ｒを説明する図である。
【図６】配置空間における境界領域を例示する図である。
【図７】相互エネルギーｆｒのグラフである。
【図８】配置決定プログラム５（図２）による画像改善処理（Ｓ２０）のフローチャートである。
【図９】解像度変換された画像に対する画像改善効果を説明する図である。
【符号の説明】
【００８６】
２・・・配置決定装置
５・・・配置決定プログラム
５００・・・データ入力部
５１０・・・記憶部
５２０・・・予備処理部
５３０・・・濃度特定部
５４０・・・分散評価部
５５０・・・配置更新部
５６０・・・判定部
５７０・・・データ出力部
【図１】
0004666223.tif 000011
【図２】
0004666223.tif 000012
【図３】
0004666223.tif 000013
【図４】
0004666223.tif 000014
【図５】
0004666223.tif 000015
【図６】
0004666223.tif 000016
【図７】
0004666223.tif 000017
【図８】
0004666223.tif 000018
【図９】
0004666223.tif 000019