(57)【要約】【課題】与えられた密度関数に忠実に従った分散密度で配置物を配置させる。【解決手段】配置決定装置は、２次元の幅ｗ、高さｈの有界な空間Ｅ内に分散したｎ個の点からなる集合をＸとしたときに、各点ｘ、ｙ∈Ｘの距離を変数とする評価関数値ｆｒにより定められる相互エネルギー（相互影響力、相互斥力）ｆｒ（｜ｘ−ｙ｜）に、密度関数ψによって定められる重み関数値μψ（ｙ）、νψ（ｘ）を重み付け係数として乗算して加重相互エネルギーを定義し、集合Ｘの任意の２点間の加重相互エネルギーの総和を集合Ｘのエネルギーとして算出して分散性を評価し、この集合Ｘのエネルギーを低下させることによって点分散の分散性を高めつつ、密度関数ψを忠実に再現する点分散を得る。【選択図】図６
2012039216.tif 000002
【特許請求の範囲】
【請求項１】
異なる２つの配置物ｘ、ｙの間の距離を変数とする評価関数ｆｒにより定められる相互エネルギーに対して、前記配置物ｘ、ｙの各位置における重み関数値μ（ｘ）、ν（ｙ）を重み付け係数として乗じた値を加重相互エネルギーとして定め、配置された全配置物間の前記加重相互エネルギーの総和を、配置物の分散性を示す評価値として算出する評価値算出手段と、
前記評価値算出手段により算出された評価値に基づいて、配置物の分散性を評価する評価手段と、
を有する分散評価装置。
【請求項２】
前記重み関数μ、νは、各配置物の配置位置における分散密度を現す密度関数ψに基づいて定められる重み関数μψ、νψとして算出される請求項１記載の分散評価装置。
【請求項３】
前記重み関数μψ、νψは、
配置物が配置された平面をメッシュ分割し、分割された各メッシュにそれぞれ独立の周期境界条件を設定した場合の理想的重み関数μψ０、νψ０に基づいて定められる前記加重相互エネルギーの総和を最小化したときの配置物の配置構造を理想配置構造とみなし、
周期境界時の重み関数μψ０、νψ０により定められる加重相互エネルギーの総和と非周期境界時の重み関数μψ、νψにより定められる加重相互エネルギーの総和が近似されるように定められる請求項１または２記載の分散評価装置。
【請求項４】
前記評価関数は、１次元周期空間に配置された複数の配置物を評価する場合にこれら複数の配置物が正三角格子状に配置されたときに全配置物間の評価関数値ｆｒの総和平均が最小となる関数であり、かつ、２次元周期空間に複数の配置物が正三角格子状に配置されたときの全配置物間の評価関数値ｆｒの総和平均が局所的に最小となる関数である請求項１から３のいずれか１項に記載の分散評価装置。
【請求項５】
前記評価関数は、２つの配置物ｘ、ｙの間の距離が規定の限界値を超える場合に値が０となり、かつ、この限界値以内の場合には、距離値を変数として単調減少かつ２階微分可能な凸関数である請求項４に記載の分散評価装置。
【請求項６】
前記評価値算出手段は、２つの配置物ｘ、ｙの間の距離が規定の限界値を超える場合、この２つの配置物ｘ、ｙに対する相互エネルギーの計算を省略する請求項５に記載の分散評価装置。
【請求項７】
異なる２つの配置物ｘ、ｙの間の距離を変数とする評価関数により定められる相互エネルギーに対して、前記配置物ｘ、ｙの各位置における重み関数値μ（ｘ）、ν（ｙ）を重み付け係数として乗じた値を加重相互エネルギーとして定め、配置された全配置物間の前記加重相互エネルギーの総和を、配置物の分散性を示す評価値として算出する評価値算出手段と、
前記評価値算出手段により算出された評価値を用いて、前記加重相互エネルギーの総和が小さくなるように所定の配置空間内における複数の配置物の配置を決定する配置決定手段と、
を有する配置決定装置。
【請求項８】
前記配置決定手段は、該加重相互エネルギーの総和の低下量が最大となる位置に前記各配置物の移動を行うか、または前記加重相互エネルギーの総和の低下量が所定値以上となる位置に前記各配置物を移動させ、全配置物の移動を所定回数反復することにより前記加重相互エネルギーの総和の降下を行う請求項７記載の配置決定装置。
【請求項９】
前記加重相互エネルギーの総和の低下量は、任意の１つの配置物を移動した際に、該配置物の移動に応じて加重相互エネルギーの総和に変動を及ぼす項である各点エネルギー係数として定義される請求項８記載の配置決定装置。
【請求項１０】
画像を構成する複数の点のうち異なる２つの点ｘ、ｙの間の距離を変数とする評価関数ｆｒにより定められる相互エネルギーに対して、前記点ｘ、ｙの各位置における重み関数値μ（ｘ）、ν（ｙ）を重み付け係数として乗じた値を加重相互エネルギーとして定め、配置された全点間の前記加重相互エネルギーの総和を、点の分散性を示す評価値として算出する評価値算出手段と、
前記評価値算出手段により算出された評価値を用いて、前記加重相互エネルギーの総和が小さくなるように所定の配置空間内における複数の点の配置を決定する配置決定手段と、
を有する画像処理装置。
【請求項１１】
異なる２つの配置物ｘ、ｙの間の距離を変数とする評価関数ｆｒにより定められる相互エネルギーに対して、前記配置物ｘ、ｙの各位置における重み関数値μ（ｘ）、ν（ｙ）を重み付け係数として乗じた値を加重相互エネルギーとして定め、配置された全配置物間の前記加重相互エネルギーの総和を、配置物の分散性を示す評価値として算出するステップと、
算出された評価値に基づいて、配置物の分散性を評価するステップとをコンピュータに実行させるためのプログラム。
【請求項１２】
異なる２つの配置物ｘ、ｙの間の距離を変数とする評価関数ｆｒにより定められる相互エネルギーに対して、前記配置物ｘ、ｙの各位置における重み関数値μ（ｘ）、ν（ｙ）を重み付け係数として乗じた値を加重相互エネルギーとして定め、配置された全配置物間の前記加重相互エネルギーの総和を、配置物の分散性を示す評価値として算出するステップと、
算出された評価値を用いて、前記加重相互エネルギーの総和が小さくなるように所定の配置空間内における複数の配置物の配置を決定するステップとをコンピュータに実行させるためのプログラム。
【請求項１３】
画像を構成する複数の点のうち異なる２つの点ｘ、ｙの間の距離を変数とする評価関数ｆｒにより定められる相互エネルギーに対して、前記点ｘ、ｙの各位置における重み関数値μ（ｘ）、ν（ｙ）を重み付け係数として乗じた値を加重相互エネルギーとして定め、配置された全点間の前記加重相互エネルギーの総和を、点の分散性を示す評価値として算出するステップと、
算出された評価値を用いて、前記加重相互エネルギーの総和が小さくなるように所定の配置空間内における複数の点の配置を決定するステップとをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散評価装置、配置決定装置、画像処理装置およびプログラムに関する。
【背景技術】
【０００２】
特許文献１には、有界な空間内に分散した各配置物間の相互エネルギーの総和を算出して分散性を評価する際に、注目配置物と他の配置物との間のエネルギーに対して、他の配置物の配置位置における密度情報の逆数に比例する重み付けを行うようにする方法が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００７−１８９４２７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の目的は、与えられた密度関数に忠実に従った分散密度で配置物を配置させることができる分散評価装置、配置決定装置、画像処理装置およびプログラムを提供することである。
【課題を解決するための手段】
【０００５】
［分散評価装置］
請求項１に係る本発明は、異なる２つの配置物ｘ、ｙの間の距離を変数とする評価関数ｆｒにより定められる相互エネルギーに対して、前記配置物ｘ、ｙの各位置における重み関数値μ（ｘ）、ν（ｙ）を重み付け係数として乗じた値を加重相互エネルギーとして定め、配置された全配置物間の前記加重相互エネルギーの総和を、配置物の分散性を示す評価値として算出する評価値算出手段と、
前記評価値算出手段により算出された評価値に基づいて、配置物の分散性を評価する評価手段とを有する分散評価装置である。
【０００６】
請求項２に係る本発明は、前記重み関数μ、νが、各配置物の配置位置における分散密度を現す密度関数ψに基づいて定められる重み関数μψ、νψとして算出される請求項１記載の分散評価装置である。
【０００７】
請求項３に係る本発明は、前記重み関数μψ、νψが、配置物が配置された平面をメッシュ分割し、分割された各メッシュにそれぞれ独立の周期境界条件を設定した場合の理想的重み関数μψ０、νψ０に基づいて定められる前記加重相互エネルギーの総和を最小化したときの配置物の配置構造を理想配置構造とみなし、
周期境界時の重み関数μψ０、νψ０により定められる加重相互エネルギーの総和と非周期境界時の重み関数μψ、νψにより定められる加重相互エネルギーの総和が近似されるように定められる請求項１または２記載の分散評価装置である。
【０００８】
請求項４に係る本発明は、前記評価関数が、１次元周期空間に配置された複数の配置物を評価する場合にこれら複数の配置物が正三角格子状に配置されたときに全配置物間の評価関数値ｆｒの総和平均が最小となる関数であり、かつ、２次元周期空間に複数の配置物が正三角格子状に配置されたときの全配置物間の評価関数値ｆｒの総和平均が局所的に最小となる関数である請求項１から３のいずれか１項に記載の分散評価装置である。
【０００９】
請求項５に係る本発明は、前記評価関数が、２つの配置物ｘ、ｙの間の距離が規定の限界値を超える場合に値が０となり、かつ、この限界値以内の場合には、距離値を変数として単調減少かつ２階微分可能な凸関数である請求項４に記載の分散評価装置である。
【００１０】
請求項６に係る本発明は、前記評価値算出手段が、２つの配置物ｘ、ｙの間の距離が規定の限界値を超える場合、この２つの配置物ｘ、ｙに対する相互エネルギーの計算を省略する請求項５に記載の分散評価装置である。
【００１１】
[配置決定装置]
請求項７に係る本発明は、異なる２つの配置物ｘ、ｙの間の距離を変数とする評価関数ｆｒにより定められる相互エネルギーに対して、前記配置物ｘ、ｙの各位置における重み関数値μ（ｘ）、ν（ｙ）を重み付け係数として乗じた値を加重相互エネルギーとして定め、配置された全配置物間の前記加重相互エネルギーの総和を、配置物の分散性を示す評価値として算出する評価値算出手段と、
前記評価値算出手段により算出された評価値を用いて、前記加重相互エネルギーの総和が小さくなるように所定の配置空間内における複数の配置物の配置を決定する配置決定手段とを有する配置決定装置である。
【００１２】
請求項８に係る本発明は、前記配置決定手段が、該加重相互エネルギーの総和の低下量が最大となる位置に前記各配置物の移動を行うか、または前記加重相互エネルギーの総和の低下量が所定値以上となる位置に前記各配置物を移動させ、全配置物の移動を所定回数反復することにより前記加重相互エネルギーの総和の降下を行う請求項７記載の配置決定装置である。
【００１３】
請求項９に係る本発明は、前記加重相互エネルギーの総和の低下量が、任意の１つの配置物を移動した際に、該配置物の移動に応じて加重相互エネルギーの総和に変動を及ぼす項である各点エネルギー係数として定義される請求項８記載の配置決定装置である。
【００１４】
[画像処理装置]
請求項１０に係る本発明は、画像を構成する複数の点のうち異なる２つの点ｘ、ｙの間の距離を変数とする評価関数ｆｒにより定められる相互エネルギーに対して、前記点ｘ、ｙの各位置における重み関数値μ（ｘ）、ν（ｙ）を重み付け係数として乗じた値を加重相互エネルギーとして定め、配置された全点間の前記加重相互エネルギーの総和を、点の分散性を示す評価値として算出する評価値算出手段と、
前記評価値算出手段により算出された評価値を用いて、前記加重相互エネルギーの総和が小さくなるように所定の配置空間内における複数の点の配置を決定する配置決定手段とを有する画像処理装置である。
【００１５】
[プログラム]
請求項１１に係る本発明は、異なる２つの配置物ｘ、ｙの間の距離を変数とする評価関数ｆｒにより定められる相互エネルギーに対して、前記配置物ｘ、ｙの各位置における重み関数値μ（ｘ）、ν（ｙ）を重み付け係数として乗じた値を加重相互エネルギーとして定め、配置された全配置物間の前記加重相互エネルギーの総和を、配置物の分散性を示す評価値として算出するステップと、
算出された評価値に基づいて、配置物の分散性を評価するステップとをコンピュータに実行させるためのプログラムである。
【００１６】
請求項１２に係る本発明は、異なる２つの配置物ｘ、ｙの間の距離を変数とする評価関数ｆｒにより定められる相互エネルギーに対して、前記配置物ｘ、ｙの各位置における重み関数値μ（ｘ）、ν（ｙ）を重み付け係数として乗じた値を加重相互エネルギーとして定め、配置された全配置物間の前記加重相互エネルギーの総和を、配置物の分散性を示す評価値として算出するステップと、
算出された評価値を用いて、前記加重相互エネルギーの総和が小さくなるように所定の配置空間内における複数の配置物の配置を決定するステップとをコンピュータに実行させるためのプログラムである。
【００１７】
請求項１３に係る本発明は、画像を構成する複数の点のうち異なる２つの点ｘ、ｙの間の距離を変数とする評価関数ｆｒにより定められる相互エネルギーに対して、前記点ｘ、ｙの各位置における重み関数値μ（ｘ）、ν（ｙ）を重み付け係数として乗じた値を加重相互エネルギーとして定め、配置された全点間の前記加重相互エネルギーの総和を、点の分散性を示す評価値として算出するステップと、
算出された評価値を用いて、前記加重相互エネルギーの総和が小さくなるように所定の配置空間内における複数の点の配置を決定するステップとをコンピュータに実行させるためのプログラムである。
【発明の効果】
【００１８】
請求項１に係る本発明によれば、与えられた密度関数に忠実に従った分散密度で配置物を配置させることができる分散評価装置を提供することができる。
【００１９】
請求項２に係る本発明によれば、請求項１に係る本発明により得られる効果に加えて、配置物の配置状態が、任意に与えられた密度関数ψに忠実に従った分散密度で配置されているか否かを評価することが可能な分散評価装置を提供することができる。
【００２０】
請求項３に係る本発明によれば、請求項１または２に係る本発明により得られる効果に加えて、重み関数μψ、νψを理想的重み関数μψ０、νψ０に近似させることにより、密度関数ψを忠実に再現している場合に良い評価結果であると評価することができる分散評価装置を提供することができる。
【００２１】
請求項４に係る本発明によれば、請求項１から３のいずれか１項に係る本発明により得られる効果に加えて、配置物や点が分散密度に関係なく均等に分散しているかどうかを評価できる分散評価装置を提供することができる。
【００２２】
請求項５に係る本発明は、請求項４に係る本発明において規定された評価関数の要件を容易に実現することができる分散評価装置を提供することができる。
【００２３】
請求項６に係る本発明は、請求項５に係る本発明により得られる効果に加えて、全ての配置物間の相互エネルギーを計算する場合と比較して、相互エネルギーの計算を簡略化することが可能な分散評価装置を提供することができる。
【００２４】
請求項７に係る本発明によれば、与えられた密度関数に忠実に従った分散密度で配置物を配置させることができる配置決定装置を提供することができる。
【００２５】
請求項８に係る本発明によれば、請求項７により得られる効果に加えて、加重相互エネルギーの総和を暫時低下させて最小化近似を行うことが可能な配置決定装置を提供することができる。
【００２６】
請求項９に係る本発明によれば、請求項８により得られる効果に加えて、任意の１つの配置物を移動した場合でも、加重相互エネルギーの総和を再計算することなく各点エネルギー係数のみを計算すればよいため、計算処理を簡略化することが可能な配置決定装置を提供することができる。
【００２７】
請求項１０に係る本発明によれば、与えられた密度関数に忠実に従った分散密度で複数の点を配置させることができる画像処理装置を提供することができる。
【００２８】
請求項１１に係る本発明によれば、与えられた密度関数に忠実に従った分散密度で配置物を配置させることができるプログラムを提供することができる。
【００２９】
請求項１２に係る本発明によれば、与えられた密度関数に忠実に従った分散密度で配置物を配置させることができるプログラムを提供することができる。
【００３０】
請求項１３に係る本発明によれば、異なる密度が混在して配置された複数の点の分散性を、本構成を有しない場合と比較して、画素の濃度分布が大きく変化する境界付近においても適切に評価して複数点の配置を決定することができるプログラムを提供することができる。
【図面の簡単な説明】
【００３１】
【図１】相互エネルギーを定義する評価関数ｆｒに対して設定された限界距離ｒを説明する図である。
【図２】本発明の一実施形態の配置決定装置１０のハードウェア構成を示す図である。
【図３】本発明の一実施形態の配置決定装置１０の機能構成を示す図である。
【図４】本発明の一実施形態の配置決定装置１０における分散評価処理（Ｓ１０）を説明するためのフローチャートである。
【図５】２５６×２５６ピクセルの２値画像と、この２値画像を構成するｍ個の黒ドットとを例示する図である。
【図６】本発明の一実施形態の配置決定装置１０における配置決定処理（Ｓ２０）を説明するためのフローチャートである。
【図７】相互エネルギーを定義する評価関数ｆｒのグラフの例である。
【図８】方法４による重み関数μψ（ｘ）、νψ（ｘ）を用いて作成した分散ドット画像の一例を示す図（図８（Ａ））、および方法１による重み関数μψ（ｘ）、νψ（ｘ）を用いて作成した分散ドット画像の一例を示す図（図８（Ｂ））である。
【図９】密度関数ψ（ｘ）により表現された原画像の一例を示す図である。
【図１０】図９に示す原画像に基づいて上記の方法１により重み関数μψ（ｘ）、νψ（ｘ）を求めμψ（ｘ）＝νψ（ｘ）＝η（ｘ）として、１／η（ｘ）2のプロットを示す図である。
【図１１】全点エネルギーを降下させることによりドットの配置を決定して生成した分散ドット画像を示す図である。
【発明を実施するための形態】
【００３２】
[背景]
まず、本発明の理解を助けるために、その背景及び概略を説明する。
デジタル画像処理におけるデジタルスクリーニング技術（２値化技術）では、白と黒の画素からなる２値画像によって擬似的に中間調のグレー値を表現し、複数の２値画像を重ねることで、例えばＣＭＹＫなどの擬似カラー画像を作成している。
【００３３】
２値画像には、主に網点と呼ばれる、複数個の点の密集により濃淡を表現するタイプ（網点画像と呼ぶ）と、複数個の分散した点により濃淡を表現するタイプ（分散ドット画像と呼ぶ）に分けられる。網点画像は、解像度は低いが安定した濃度表現が可能であり、分散ドット画像は、網点画像よりも高い解像性を表現できる。分散ドット画像の画質上の問題点として、ドットの分散性の良し悪しに起因するざらつきの発生が挙げられ、高品位な分散ドット画像を得るためには、ドットの分散性を高める必要がある。以下、分散ドット画像に関する問題点を整理する。
【００３４】
分散ドット画像の作成方法は、主に閾値一対比較方式と適応計算方式とに分けられる。
閾値一対比較方式は、予め作成した固定サイズの分散ドット閾値マトリックスを原画像上に周期的にマスクしながら、閾値比較をして「０」又は「１」の信号を発生させる方式であり、網点画像生成と同等の高速性を有するが、一般にドットの分散性と解像性が高くなく、以下に説明する適応計算方式と比較して画質が劣る。
【００３５】
適応計算方式の代表的なものに誤差拡散法が知られている。誤差拡散法は、原画像である連続階調画像の各ドットを閾値と比較して「０」「１」の信号を発生させると同時に、比較誤差を周囲の未処理画素に重畳しながら２値化を行う方式であり、解像性の高い画像を得ることができ、ドットの分散性にも優れているが、固有のテクスチュア（ワーム）や階調段差が発生する場合がある。
【００３６】
適応計算方式の別の代表的なものにｄｉｒｅｃｔ  ｂｉｎａｒｙ  ｓｅａｒｃｈ方式がある。ｄｉｒｅｃｔ  ｂｉｎａｒｙ  ｓｅａｒｃｈ方式は、連続階調画像である原画像と、その画像の分散ドットハーフトーン画像とに、人間の視覚特性に基づいたｐｏｉｎｔ  ｓｐｒｅａｄ関数（ボケ特性関数）を施し、これらの画像間の２乗距離が小さくなるようにハーフトーン画像内のドットを移動させながら収束させる方式である。ｄｉｒｅｃｔ  ｂｉｎａｒｙ  ｓｅａｒｃｈ方式は誤差拡散法のようなテクスチュアや階調段差がなく、全濃度に渡って均一なドット分散を得ることができるが、ボケ特性関数を使用することにより全体にハーフトーン画像にボケが目立ち、また２乗距離計算を行うため処理負荷が高く、ＶＧＡサイズの画像をハーフトーン化するにも数時間を要するという問題がある。
【００３７】
また、適応計算方式の別の方式としてｄｉｓｃｒｅｐａｎｃｙ方式がある。ｄｉｓｃｒｅｐａｎｃｙ方式は、ｄｉｒｅｃｔ  ｂｉｎａｒｙ  ｓｅａｒｃｈ方式と同様に連続階調画像である原画像とその画像の分散ドットハーフトーン画像との距離を尺度とする方式であり、ｌｏｗ−ｄｉｓｃｒｅｐａｎｃｙ列の理論に基づいている。ｄｉｒｅｃｔ  ｂｉｎａｒｙ  ｓｅａｒｃｈ方式のようなｐｏｉｎｔ  ｓｐｒｅａｄ関数によるボケ特性を使わず、代わりに平面内の任意の領域内で原画像濃度と分散したドットの総数とに基づいて距離（Ｌ２距離やＬ∞距離）を定義し、ドット分散の均一性を保証するようにしている。数学的な保証・解析が可能な点で、ｄｉｒｅｃｔ  ｂｉｎａｒｙ  ｓｅａｒｃｈ方式よりも素性が良い。しかしながら根本的な問題として、ハーフトーンで要求される幾何的なドット分散性とｌｏｗ−ｄｉｓｃｒｅｐａｎｃｙ列の理論で保証される点分散性との整合性が不明であり、実際に前記の誤差拡散やｄｉｒｅｃｔ  ｂｉｎａｒｙ  ｓｅａｒｃｈ方式よりも分散性は悪い結果となる。
【００３８】
なお、誤差拡散法は、一例をあげると、
R. Floyd and L. Steinberg, "An adaptive algorithm for spatial grey scale," Proc. Soc. Info. Display, vol 17, no. 2, pp. 75-77, 1976.
に述べられておいる。
【００３９】
また、ｄｉｒｅｃｔ  ｂｉｎａｒｙ  ｓｅａｒｃｈ方式は、一例をあげると、
M. Analoui and J. Allebach, "Model-based halftoning using direct binary search," in Proc. 1992 SPIE/IS&T Symp. Elec. Imag. Sci. Tech., vol. 1666, San Jose, CA, Feb. 1992, pp. 96-108.
に述べられている。
【００４０】
そして、ｄｉｓｃｒｅｐａｎｃｙ方式は、一例をあげると、特開２００３−６６２０８号公報に述べられている。
【００４１】
[実施形態]
以下、本発明の一実施形態の配置決定装置について説明を行なうが、本実施形態の配置決定装置における分散評価処理、配置決定処理の方法を説明する前に、これらの処理を行う上で必要となる概念である、周期境界（条件）・周期空間、エネルギーの定義及びエネルギー降下に関して説明する。
【００４２】
[周期境界（条件）・周期空間]
本発明において、周期境界条件とは、１次元空間（線分）の場合は線分の右端点と左端点とを同一視することを意味し、２次元空間（長方形）の場合は長方形の右辺と左辺とを同一視し、更に上辺と下辺とを同一視することを意味する。なおここで、点ｘと点ｙとを同一視するとは、点ｘと点ｙとの距離が０であるとみなすことを意味し、同一視によって、空間の境界部分は反対側の境界部分と連続的に繋げられる。直感的には、例えば２次元空間の場合には点ｐが連続的に長方形内を移動して行って右辺に達したら高さ方向の座標はそのまま変わらずに横方向の座標だけ０に戻って左辺から点ｐが再び出てくることであるとも理解できる。これらの周期境界条件を課した空間を周期空間と呼ぶこととする。なお、非周期境界と言った場合は、このような周期境界条件を外した状態を意味する。以下、周期境界・周期空間の語は、断りのない限りこの定義に基づくものとする。
【００４３】
[エネルギーの定義]
本発明においては、分散性の評価尺度として、エネルギーの概念を使用する。以下、エネルギーの定義を行う。
２次元の幅ｗ、高さｈの有界な空間Ｅ内に分散したｎ個の点からなる集合をＸとしたときに、各点ｘ、ｙ∈Ｘの距離を変数とする評価関数ｆｒにより定められる値ｆｒ（｜ｘ−ｙ｜）を相互エネルギーと定義し、これに各点ｘ、ｙにおける重み関数値μ（ｙ）、ν（ｘ）を重み付け係数として乗算した値を加重相互エネルギーとして下記のように定義する。
ｆｒ（｜ｘ−ｙ｜）・μ（ｙ）・ν（ｘ）
【００４４】
そして、集合Ｘの任意の２点間の加重相互エネルギーの総和を求めることにより、下記の式（１）で示される全点エネルギーＩ（Ｘ，ｆｒ）を定義する。つまり、全点エネルギーＩ（Ｘ，ｆｒ）は、集合Ｘに属する任意の２点ｘ、ｙ間の加重相互エネルギーの総和を求める関数である。
【数１】
2012039216.tif 000003
【００４５】
後述するように、この集合Ｘの全点エネルギーにより点分散の分散性の評価尺度が定められ、Ｘの全点エネルギーを低下させることによって点分散の分散性を高めることができる。
【００４６】
全点エネルギーは、各点エネルギーの概念を経由して説明することもできる。つまり、集合Ｘの点ｘとその他の点ｙとの相互エネルギーに各点ｙにおける重み関数値μ（ｙ）を乗じて総和をとって、Ｘの各点エネルギーを下記のように定義する。
Ｉ（Ｘ，ｘ,ｆｒ）＝Σy∈Xｆｒ（｜ｘ−ｙ｜）・μ（ｙ）
【００４７】
更に、各点ｘでの各点エネルギーに点ｘにおける重み関数値ν（ｘ）を重み付け係数として乗じて総和をとって、Ｘの全点エネルギーが下記の式により導かれ、上記の式（１）と一致する。
Ｉ（Ｘ，ｆｒ）＝Σx∈XＩ（Ｘ，ｘ，ｆｒ）・ν（ｘ）
【００４８】
上記エネルギーの一般的な定義自体は、ポテンシャル理論の分野に属している。ポテンシャル理論では、例えば、エネルギーＩ（Ｘ、ｆ）は、ｓを実数として以下の式で定義される。
【００４９】
【数２】
2012039216.tif 000004
【００５０】
また、重み関数μ、νは、予め与えられた空間内に配置されるべき点の密度を与える密度関数ψによって定められ、これを明示する場合にはμψ、νψと記述する。
【００５１】
重み関数μψ、νψは密度関数ψと同じ定義域上で定義された関数であり、定義域上の各点においてエネルギー値に掛け合わせるべき重みを定義するものである。与えられた密度関数ψに応じて正しく重み関数を定めることで、密度関数ψを正確に再現する点分散を得ることができる。そのためには、予め、密度関数ψを正確に再現する点分散を理想的に規定し、そのときの各点で取るべきエネルギー値の逆数を重み関数μψ、νψとして定義する必要がある。実際にはこのエネルギー値の逆数には、理論的なエネルギー最小性を保証するための微分項などが付加されて複雑になっている。しかし、重み関数の意味としては、密度分布（密度関数）ψを正確に反映した理想点分散を仮想的に規定し、そのような点分散における各点での理想エネルギー値のおおよそ逆数値を重み関数値として表現するための関数となる。
【００５２】
なお、本発明において重要な概念である重み関数μψ、νψの具体的な算出方法は複雑なため、別途後述する。
【００５３】
相互エネルギーを算出するための評価関数ｆｒは、本発明にかかる評価関数の一例であり、区間［０、１］上で定義された関数ｈ（ｘ）により、
ｆｒ（ｘ）＝ｈ（ｘ／ｒ）  （ｘ＜ｒのとき）、
ｆｒ（ｘ）＝０            （ｘ≧ｒのとき）
と表記したときに、
Ｈ１：ｈはＣ２級で単調減少凸関数
Ｈ２：ｈ（１）＝ｈ’（１）＝ｈ’’（１）＝０
Ｈ３：（ｈ’’（ｘ1/2）／（ｘ1/2））1/2が凸関数
であるものとすることができる。Ｈ１〜Ｈ３を満たす関数ｈと満たさない関数ｈの実例、及びそれらが本発明に与える効果に関しては、後述の[関数ｈにより定義される評価関数ｆｒの具体例]における説明の中で詳述する。
【００５４】
なお、Ｈ１〜Ｈ３の条件を満たす関数ｈにより定義された評価関数ｆｒは、１次元周期空間に配置された複数の点が均等に分散したときに、全ての点ｘ、ｙ∈Ｘに関する評価関数値（相互エネルギー）ｆｒ（｜ｘ−ｙ｜）の総和平均が最小になることが数学的に保証された関数である。また、この評価関数ｆｒは、２次元周期空間に複数の点が正三角格子状に配置されたときに、全ての点ｘ、ｙ∈Ｘに関する評価関数値（相互エネルギー）ｆｒ（｜ｘ−ｙ｜）の総和平均が局所的に最小になる関数である。局所的に最小であるとは、任意の１点を移動するとエネルギー値が上昇するということを意味し、三角格子状構造が局所的に安定であるということを意味している。このとき、任意の点分散に対して、各点のエネルギーを測定し、測定した値が小さいほど、エネルギーが小さく、点分散の分散性が良いとすることができる。
【００５５】
また、評価関数ｆｒの定義の仕方から、２点ｘ、ｙが距離ｒ以上離れた場合に相互エネルギーは０となる。従って、上記の式（１）で定義される全点エネルギーはＸの各点ｘに対して、ｘから距離ｒ以内にあるＸの点ｙのみに関して加重相互エネルギーを計算して総和をとれば良い。つまり、図１に示すように、注目点ｘ∈Ｘを中心とする半径ｒの領域内にある全ての点ｙ∈Ｘのみを（加重）相互エネルギー計算の対象点とすれば良く、半径ｒよりも外側の点（白抜きの丸）は、ｆｒ（ｘ）＝０（ｘ≧ｒ）の条件に基づいて無視できる。
【００５６】
[エネルギーの降下]
有界な空間Ｅ内の点集合Ｘについて、上記の式（１）により算出された全点エネルギー（Ｉ（Ｘ，ｆｒ））を低下するように各点ｘ∈Ｘを局所的に近傍点に移動してゆくことにより、与えられた密度関数ψに従った分散性の良い点配置を得ることができる。なお、以下の説明においては、点集合Ｘが属している有界な空間Ｅは、２次元ユークリッド平面の部分集合であるとする。一例として分散ドットハーフトーン画像を例にすると、２次元の幅ｗ、高さｈの有界な画像空間Ｅ上の原画像を密度関数ψとし、分散ドットハーフトーン画像ドット全体（黒ドット）の集合をＸと置けば良い。画像（長方形）の周囲は周期境界としておく。
【００５７】
各点を近傍の点に動かして全点エネルギーを低下させる際には、上記の全点エネルギー値自体を逐次測定する必要はなく、全点エネルギーのうち、点ｘの移動により変化する値
【数３】
2012039216.tif 000005
が低下するように移動すれば良く、上記全点エネルギーの近似的な最小を得ることができる。以後、このＤ（Ｘ、ｘ、ｆｒ）を、「各点エネルギー係数」と呼ぶ。なお、このような各点の移動によるｃｏｓｔ関数の最小化の方法として、ここで説明したような単に近傍中の最小値を取る点に移動するという「山登り法」の他に、「焼き鈍し法」などの方法（閾値を設け、ある程度値が悪化する点を許容しながら移動しつつ、徐々に閾値を小さくする方式）を使用することもできる。
【００５８】
なお、「山登り法」の場合は上記の各点エネルギー係数Ｄの低下量が最大となる位置に各点の移動を行い、「焼き鈍し法」の場合は上記各点エネルギー係数Ｄの低下量が許容された値以上となる位置に各点を移動させる。一般には、焼き鈍し法の方がより低いエネルギー値に収束することが知られている。そして、全ての点を各点エネルギー係数Ｄが低減する位置に移動するという工程をＮ回（所定回数）反復することによりエネルギーの降下を行うことができる。
【００５９】
［分散評価装置、配置決定装置、画像処理装置］
次に、本実施形態における分散評価装置、配置決定装置、画像処理装置のハードウェア構成を説明する。ここで、本実施形態における分散評価装置は配置決定装置の一部であり、また画像処理装置は実質的に分散評価装置そのものと理解してよい。従って、画像処理装置としての動作を前提として例示しながら、一般的な機能を網羅する配置決定装置に関して、ハードウェア構成を説明する。但し、上記のように分散評価装置は配置決定装置の一機能ではあるが、与えられた２つの配置状態のどちらがより密度関数ψに従った良い配置（分散）状態かを評価するという別の目的のために、単独で使用できるという点に注意する。
【００６０】
本実施形態における配置決定装置１０は、上述の点分散の評価を利用して配置物の分散性を評価したり、配置物を分散させる。対象とする配置物を分散ドット２値画像のドットとすれば、分散ドット２値画像を作成するほかに、任意の２値画像から分散ドット２値画像への変換、分散ドット２値画像の画質改善、分散ドット２値画像の解像度変換、分散ドット２値画像の濃度変換、分散ドット画像の画質評価、のそれぞれの処理を実行することができる。本実施形態では、与えられた確率密度分布（密度関数ψ）にしたがった密度分布で配置物（２値画像の場合はドット）を分散させる。
【００６１】
図２は、分散評価方法、配置決定方法及び画像処理方法を実行する配置決定装置１０のハードウェア構成を示す図である。
本実施形態の配置決定装置１０は、図２に示されるように、ＣＰＵ１１、メモリ１２、ハードディスクドライブ（ＨＤＤ）等の記憶装置１３、ネットワークを介して外部の装置等との間でデータの送信及び受信を行う通信インタフェース（ＩＦ）１４、タッチパネル又は液晶ディスプレイ並びにキーボードを含むユーザインタフェース（ＵＩ）装置１５を有する。これらの構成要素は、制御バス１６を介して互いに接続されている。
【００６２】
ＣＰＵ１１は、メモリ１２または記憶装置１３に格納された配置決定プログラムに基づいて所定の処理を実行して、配置決定装置１０の動作を制御する。なお、本実施形態では、ＣＰＵ１１は、メモリ１２または記憶装置１３内に格納された配置決定プログラムを読み出して実行するものとして説明したが、当該プログラムをＣＤ−ＲＯＭ等の記憶媒体に格納してＣＰＵ１１に提供することも可能である。
【００６３】
配置決定装置１０は、例えば、配置決定プログラムがインストールされた汎用コンピュータであり、通信ＩＦ１４又は記憶装置１３などを介して、空間上に配置すべき配置物に関する情報（例えば、配置物の数など）、及び、これらの配置物が配置される配置空間に関する情報（例えば、配置空間の形状、大きさなど）を取得し、取得された情報に基づいて、配置物の配置を決定する。
また、配置決定装置１０は、配置物の位置情報、及び、配置空間に関する情報を取得し、取得されたこれらの情報に基づいて、配置物の分散性を評価する。
【００６４】
図３は、上記の配置決定プログラムが実行されることにより実現される配置決定装置１０の機能構成を示すブロック図である。
【００６５】
本実施形態の配置決定装置１０は、図３に示されるように、データ入力部５００と、記憶部５１０と、予備処理部５２０と、濃度特定部５３０と、分散評価部５４０と、配置更新部５５０と、判定部５６０と、データ出力部５７０とを備えている。なお、配置決定装置１０の各構成要素の全部又は一部をＡＳＩＣなどのハードウェアで実現してもよい。
【００６６】
データ入力部５００は、配置空間上に配置すべき配置物に関する情報（例えば、配置物の数など）、及び、この配置空間に関する情報（例えば、配置空間の形状、大きさなど）を点分散データとして取得し、取得された点分散データを記憶部５１０に出力する。本実施形態におけるデータ入力部５００は、入力された２値画像（分散ドット画像データ）を点分散データとして記憶部５１０に出力する。
【００６７】
記憶部５１０は、データ入力部５００から入力された点分散データを記憶する。また、記憶部５１０は、予備処理部５２０、濃度特定部５３０、分散評価部５４０、配置更新部５５０及び判定部５６０に対して、ワークエリアを提供する。例えば、記憶部５１０は、データ入力部５００から入力された点分散データに加えて、予備処理部５２０により前処理された画像の点分散データ、分散性改善後の点分散データ、並びに、点分散評価に用いられる各種の途中演算結果及び処理パラメータなどを保持する。
【００６８】
予備処理部５２０は、入力された点分散データに対して、必要とされるさまざまな予備処理を行う。本実施形態では、２値の分散ドット画像の各種の処理を行うことが可能であるが、それぞれの処理に応じて必要な準備や処理工程が異なるため、予備処理部５２０は必要な処理を行う。一例を挙げると、分散ドット画像の解像度変換を行う場合には、予備処理部５２０は、分散評価部５４０及び配置更新部５５０等による分散性の改善処理を行う前に、原画像を所定解像度に解像度変換する。この場合に、解像度変換された画像に対して、分散評価部５４０及び配置更新部５５０等によって分散性の改善処理が施される。
【００６９】
濃度特定部５３０は、入力された点分散データに基づいて、各配置領域における配置物の密度を特定し、特定された密度を示す情報（密度関数ψ）を分散評価部５４０に提供する。密度関数ψはドットをどのような密度で配置すべきかを指定する密度情報であり、画像の濃度情報（輝度情報）などが含まれる。なお、本実施形態における濃度特定部５３０は、多値の画像データが入力された場合には、入力された画像データの画素値に基づいて、各画像領域における濃度値を特定し、２値の画像データが入力された場合には、２値画像を構成する複数のドットの分布に基づいて、各画像領域における濃度値を特定する。入力された画像データがグレーの２５６階調画像の場合は、この２５６階調そのものを密度関数ψとすれば良い。
【００７０】
分散評価部５４０は、記憶部５１０に記憶されている点分散データと、濃度特定部５３０により特定された密度関数ψに基づいて算出される重み関数μψ、νψを用いて、エネルギー値の評価を行う。より具体的には、分散評価部５４０は、記憶部５１０に保持された点分散データの分散性の良さを、上記で示した式（１）で定義される全点エネルギーによって評価する。
【００７１】
配置更新部５５０は、記憶部５１０に記憶されている点分散データに対して、いずれかの配置物の仮配置位置を変更する配置更新処理を行う。具体的には、配置更新部５５０は、分散評価値５２０により算出される全点エネルギー値を降下させるべく、入力された２値画像の各点ドット（点ｘとみなす）を、上記の式（２）で定義した点ｘでの各点エネルギー係数Ｄを低下させるように移動させる。
【００７２】
判定部５６０（配置決定手段）は、分散評価部５４０による評価結果に基づいて、適用すべき点分散データを選択する。また、判定部５６０は、分散性の評価のみを行う場合に、配置更新部５５０による点分散データの更新（ドットの移動）を禁止する。
【００７３】
さらに、判定部５６０は、分散性のよい配置を決定する場合に、配置更新部５５０に各配置物（ドット）を移動させ、必要に応じて分散評価部５４０に再び各点エネルギー値の算出を実行させる。あるいは、判定部５６０は、エネルギー値が既定の条件を満たすまで、分散評価部５４０による評価、及び、配置更新部５５０による配置更新処理を交互に繰り返させてもよい。
【００７４】
すなわち、分散評価部５４０、配置更新部５５０及び判定部５６０は、互いに協働して、点分散性の改善処理を行う。
【００７５】
データ出力部５７０は、分散評価部５４０による評価結果（算出された全点エネルギー値もしくはエネルギー降下すなわち分散性が改善された点分散データ）を、通信装置２２又は記憶装置２４に出力する。
【００７６】
[配置決定装置１０の動作説明]
次に、本実施形態の配置決定装置１０における分散評価処理及び配置決定処理をそれぞれ説明する。なお、入力される点分散データが離散空間内で定義される場合を具体例として説明するが、これに限定されるものではなく、例えば、本配置決定プログラムは、連続空間で定義された点分散データに関しても、密なメッシュで離散化することによって擬似的に取り扱うことができる。また、長方形以外の形状を持った空間Ｆに関しても、その空間を含む大きな長方形の空間Ｅを対象として点分散を扱えば良い。ここで、ＥであってＦでない点ｘの密度関数値ψ（ｘ）をψ（ｘ）＝０と定義しておけば良いだけである。
【００７７】
［分散評価処理］
まず、分散評価処理を説明する。以下では、離散的な空間２５６×２５６ピクセル内に分散したｍ個の点分散の分散性を評価する例について説明する。
【００７８】
図４は、本実施形態の配置決定装置１０により実行される分散評価処理（Ｓ１０）の処理の流れを示すフローチャートである。
先ず、ステップ１００（Ｓ１００）において、データ入力部５００は、通信ＩＦ１４（図２）又は記憶装置１３（図２）を介して、入力画像（配置空間）の形状及び大きさ、並びに、この入力画像における各ドットの位置を点分散データとして取得し、取得された点分散データを記憶部５１０に出力する。
【００７９】
分散評価部５４０は、データ入力部５００から入力された点分散データに応じて、有限集合Ｅに含まれる点分散集合Ｘを準備する。本実施形態では、Ｅは、図５に例示するように、２５６×２５６のピクセル全体とする。また、ドットの集合Ｘは、このＥの内部に定義されたｍ個の点の集合とする。
【００８０】
ステップ１１０（Ｓ１１０）において、濃度特定部５３０は、入力されたドットの分布に基づいて、各ドット位置における濃度値を算出して密度関数ψとして定義し、合わせて重み関数μψ、νψを定義する。なお、密度関数ψから重み関数μψ、νψを定義する方法はまとめて後述する。濃度値は、例えば、既定サイズの画像領域におけるドット点灯比率に基づいて算出される。
【００８１】
ステップ１２０（Ｓ１２０）において、判定部５６０は、分散評価処理を行うか配置決定処理を行うかを判定し、分散評価部５４０及び配置更新部５５０に対して、判定結果に応じた制御を行う。本実施形態では、分散評価処理を行うため、判定部５６０は、分散評価処理を実施させるべく、配置更新部５５０に対して配置更新処理を禁止し、分散評価部５４０に対して分散評価処理を行うよう指示する。
【００８２】
分散評価部５４０は、入力された点分散データ、及び、濃度特定部５３０により算出された密度関数値ψに基づいて、各ドット位置ｘの各点エネルギーＩ（Ｘ，ｘ，ｆｒ）に点ｘの密度関数値νψ（ｘ）を乗じた、Ｉ（Ｘ，ｘ，ｆｒ）・νψを算出する。なお、各点エネルギーの計算方法は前述した。
【００８３】
ステップ１３０（Ｓ１３０）において、分散評価部５４０は、算出された各点（注目点ｘ）の各点エネルギーＩ（Ｘ，ｘ，ｆｒ）に基づいて、配置空間全体のエネルギーＩ（Ｘ，ｆｒ）（以下、全点エネルギー）を算出する。なお、全点エネルギーの計算方法は前述した。
【００８４】
ステップ１４０（Ｓ１４０）において、データ出力部５７０は、分散評価部５４０により算出された全点エネルギーＩ（Ｘ，ｆｒ）を、点分散性の評価値として出力する。
【００８５】
なお、データ出力部５７０は、全点エネルギーＩ（Ｘ，ｆｒ）に加えて、各点のエネルギーＩ（Ｘ，ｘ，ｆｒ）に点ｘの密度関数値νψ（ｘ）を乗じたＩ（Ｘ，ｘ，ｆｒ）・νψを、分散性の評価値として出力してもよい。
【００８６】
このように、本実施形態の配置決定装置１０は、２値画像を構成するドット間の距離に基づいて、全点エネルギーＩ（Ｘ，ｆｒ）あるいは各点エネルギーＩ（Ｘ，ｘ，ｆｒ）に点ｘの密度関数値νψ（ｘ）を乗じた、Ｉ（Ｘ，ｘ，ｆｒ）・νψを算出し、ドットの分散性の評価値として出力する。
【００８７】
［配置決定処理］
次に、本実施形態の配置決定装置１０における配置決定処理を説明する。本実施形態では、例として２５６×２５６ピクセルの２値画像を処理対象とし、この画像内に分散したｍ個の黒ドットについて、各画像領域の濃度を維持しつつ、全点エネルギーを降下させることで黒ドットの配置を決定し、より分散性の良い２値画像を作成する形態を具体例として説明する。
【００８８】
処理対象となる２値画像は、網点画像でも、分散ドット画像でもよい。また、本実施形態では、入力された２値画像に対して、連続階調画像の原画像ψが存在する場合と、存在しない場合を共に前提として説明を行う。
【００８９】
図６は、本実施形態の配置決定装置１０における配置決定処理（Ｓ２０）の処理の流れを示すフローチャートである。なお、本実施形態では、上記の「エネルギー降下」で説明した形態を具体例として説明するが、これに限定されるものではなく、分散評価部５４０により算出される全点エネルギー値が降下する方法であれば、どのような方法でもよい。
【００９０】
図６に示すように、ステップ２００（Ｓ２００）において、データ入力部５００（図３）は、通信ＩＦ１４（図２）又は記憶装置１３（図２）を介して、入力された２値画像の形状及び大きさ、並びに、この２値画像における各黒ドットの位置を点分散データとして取得し、取得された点分散データ（すなわち、２値画像の画像データ）を記憶部５１０に出力する。
なお、本実施形態では、黒ドットを配置物として分散性を評価し、配置の更新を行うが、白ドットを配置物として処理してもよい。
【００９１】
ステップ２０２（Ｓ２０２）において、予備処理部５２０（図３）は、記憶部５１０に展開された２値画像に対して、要求された処理に対して必要な前処理を実行する。すなわち、予備処理部５２０は、記憶部５１０に展開された２値画像に対して解像度変換などの画像処理を施す。なお、予備処理部５２０による前処理は必須ではなく、前処理が行われない場合には、本配置決定処理により、ドットの分散性が改善される。
【００９２】
例えば、解像度変換が要求された場合には、予備処理部５２０は、例えば、最近傍法などにより２値画像を構成する黒ドット及び白ドットの数を変更する。この場合に、黒ドット及び白ドットの数、並びに、２値画像の大きさなどが変化するため、点分散データが更新されることになる。
【００９３】
また、濃度変換が要求された場合には、予備処理部５２０は、入力された２値画像（及び、連続階調画像）について、濃度変換を行う。すなわち、連続階調画像の濃度変換は、各ピクセルに固定濃度比率を乗算し、２値画像の濃度変換は、この固定比率に基づいて所定数の画素値（黒ドットと白ドット）を反転させればよい。この場合にも、黒ドット及び白ドットの数が変化するため、点分散データが更新されることになる。
【００９４】
ステップ２０４（Ｓ２０４）において、濃度特定部５３０は、記憶部５１０に展開されている２値画像の各黒ドットの位置について、密度関数ψ及び重み関数μψ、νψを特定する。密度関数ψは、例えば、連続階調画像の原画像が存在する場合には、現画像の輝度値そのものとすればよいし、連続階調画像の原画像が存在しない場合には、該２値画像の各黒ドットを中心とした既定サイズの画像領域における黒ドットの割合に基づいてなされる。重み関数μψ、νψの特定はまとめて後述する。
【００９５】
ステップ２０６（Ｓ２０６）において、判定部５６０は、ドットの配置改善処理を行うべく、配置更新部５５０に仮配置更新処理を指示する。
【００９６】
配置更新部５５０は、２値画像を構成する黒ドットの集合Ｘの中から、処理対象となる注目ドットｘを設定し、この注目ドットｘを既定の位置に仮変位させる。注目ドットｘを仮変位させる既定位置は、例えば、注目ドットｘを中心とした３×３ピクセルのいずれかである。場合によっては移動範囲を広げても良い。
【００９７】
ステップ２０８（Ｓ２０８）において、判定部５６０は、この仮変位後の注目ドットｘについて、上記の式（２）に示した各点エネルギー係数Ｄ（Ｘ，ｘ，ｆｒ）を算出するよう分散評価部５４０に指示する。なお、全点エネルギーＩ（Ｘ,ｆｒ）を降下させるためには、各点ｘで各点エネルギー係数Ｄを降下させれば良いということは前述した。
【００９８】
分散評価部５４０は、記憶部５１０に展開されている２値画像の点分散データに応じて、有限集合Ｅに含まれる点分散集合Ｘを準備する。本実施形態では、図５に例示するように、Ｅを２５６×２５６のピクセル全体とする。また、２値画像を構成する黒ドットの集合Ｘは、このＥの内部に定義されたｍ個の点の集合であり、初期配置データして設定される。
【００９９】
分散評価部５４０は、仮変位後の注目ドットｘについて、各点エネルギー係数Ｄ（Ｘ，ｘ，ｆｒ）を算出する。なお、本ステップにおける各点エネルギー係数Ｄの算出は、図４に示したＳ１２０と実質的に同一である。
【０１００】
ステップ２１０（Ｓ２１０）において、判定部５６０は、この注目ドットｘを全ての既定位置（注目ドットｘを中心とした９ピクセル）で仮変位させ、それぞれの仮変位後に各点エネルギー係数を算出したか否かを判定し、全ての仮変位点で各点エネルギー係数が算出された場合に、Ｓ２１２の処理に移行し、これ以外の場合に、Ｓ２０６の処理に戻って、次の変位位置について各点エネルギー係数を算出する。
【０１０１】
ステップ２１２（Ｓ２１２）において、判定部５６０は、この注目ドットｘを仮変位させて算出された各点エネルギー係数の中から、山登り法を適用する場合には各点エネルギー係数が最も小さい仮変位位置を、焼き鈍し法を適用する場合には各点エネルギー係数が許容された値以上となる位置を、配置更新部５５０に通知する。
【０１０２】
配置更新部５５０は、判定部５６０からの通知に応じて、指定された仮変位位置に、この注目ドットｘを配置し、Ｘを更新する。
【０１０３】
ステップ２１４（Ｓ２１４）において、判定部５６０は、黒ドットの集合Ｘに含まれる全てのドットｘについて、Ｓ２０６〜Ｓ２１２の処理を行ったか否かを判定し、未処理の黒ドットｘが存在する場合に、Ｓ２０６の処理に戻って、未処理の黒ドットｘを注目ドットとしてＳ２０６〜Ｓ２１２の処理を行い、全ての黒ドットｘについて処理が終了した場合に、Ｓ２１６の処理に移行する。
【０１０４】
ステップ２１６（Ｓ２１６）において、判定部５６０は、Ｓ２０６〜Ｓ２１４の処理が既定の回数だけ繰り返されたか否かを判断し、繰返し回数が既定回数以上である場合に、Ｓ２２０の処理に移行し、繰返し回数が既定回数未満である場合に、Ｓ２１８の処理に移行する。
【０１０５】
すなわち、配置決定プログラムは、Ｓ２０６〜Ｓ２１４の処理が既定の回数以上繰り返された場合に、各点が収束して最適な地点に移動し終えたと判断する。
【０１０６】
ステップ２１８（Ｓ２１８）において、判定部５６０は、Ｓ２０６〜Ｓ２１４の処理が施された黒ドットの集合Ｘ'を、初期配置データに設定して、Ｓ２０６の処理に戻る。
【０１０７】
すなわち、配置決定装置１０は、Ｓ２０６〜Ｓ２１４の処理が既定の回数以上繰り返されていない場合に、各点が収束し終えていないと判断し、この処理後の黒ドットの集合Ｘ'を初期状態として、Ｓ２０６〜Ｓ２１４の処理を繰り返す。
【０１０８】
ステップ２２０（Ｓ２２０）において、判定部５６０は、初期配置データ（収束するまで更新が繰り返された集合Ｘの配置）を、最適な配置として出力するようデータ出力部５７０に指示する。
【０１０９】
データ出力部５７０は、初期配置データを、分散性が改善された２値画像のデータとして出力する。なお、データ出力部５７０は、分散性が改善された２値画像のデータと共に、算出された各点エネルギーに点ｘの重み関数値νψ（ｘ）を乗じたＩ（Ｘ，ｘ，ｆｒ）・νψ及び全点エネルギーＩ（Ｘ，ｆｒ）を、この画像データの評価値として出力してもよい。
【０１１０】
このように、配置決定装置１０は、密度関数である画像の濃度値に基づいてドットの分散性を評価しながら、エネルギーを降下させることにより、画像処理が施された２値画像のドットの分散性を改善させる。
【０１１１】
なお、以上の説明においては、連続階調画像の原画像が存在する場合と存在しない場合を共に扱ってきたが、例えば画像の２値化処理は前者に相当し、２値画像の解像度変換や色変換などの処理は一般に後者に相当する。連続画像の２値化処理も、このように一旦仮２値化した画像の分散性を上げるという見方をすることで本実施形態の方法を適用することができる。
【０１１２】
[重み関数μψ、νψの具体的算出方法]
次に、上記で説明した、本発明において重要な概念である、重み関数μψ、νψの具体的な算出方法について説明する。
【０１１３】
前述の通り、重み関数μ、νは、好適には与えられた密度関数ψに従って重み関数μψ、νψとして定義することで実用上の意味を持つ。そこで、密度関数ψからどのように重み関数μψ、νψを定めるかを以下に説明する。
【０１１４】
先ず、下記の式に示すように、初めに与えられた密度関数ψを正規化した値を密度関数として置きなおす。
【数４】
2012039216.tif 000006
【０１１５】
正規化により、密度関数ψのＥ上の総密度（積分値）が１となる。以下、重み関数μψ、νψの定義方法を５種類（方法１〜方法５）述べる。初めに理論的に最も正確な形式を方法１として説明し、その結果をより簡単に近似する方法として、方法２から方法４までを説明する。また、方法１をより一般化したものを方法５として説明する。
【０１１６】
[方法１]
初めに重み関数μψ、νψの定義式を述べる。重み関数μψ、νψは、下記の積分方程式の解ηを求めて、μψ（ｘ）＝νψ（ｘ）＝η（ｘ）と定義することができる。
【数５】
2012039216.tif 000007
【０１１７】
ここで、式中のＷｆを以下で定義する。まず、密度関数値ψ（ｘ）に対応する理想点分散間隔ｄｒ（ψ（ｘ））を下記の式により定める。
【数６】
2012039216.tif 000008
【０１１８】
更に、
Λｘ＝｛格子点間隔ｄｒ（ψ（ｘ））の正三角格子（原点を含む）｝
と定義する。
【０１１９】
【数７】
2012039216.tif 000009
【０１２０】
以上で定義される重み関数の定義式（３）の意味を説明する。領域Ｅが有限個のメッシュ（同サイズ）に分割されており、各メッシュ内で密度関数ψが均一の値を取る場合を考える。このとき、Ｘがこの密度関数ψに従った理想的な点分散である場合の各点ａでの点エネルギー値
【数８】
2012039216.tif 000010
の平均値が式（３）の左辺で与えられる。
【０１２１】
また、各メッシュが周期境界条件を持っているとみなし、各メッシュ内の点ｘ、ａのメッシュ内周期境界距離を
【数９】
2012039216.tif 000011
で表現した場合の、各点ａでの点エネルギー値
【数１０】
2012039216.tif 000012
の平均が式（３）の右辺で与えられる。
【０１２２】
なお、このようにメッシュに周期境界を導入した場合の理想点分散は三角格子であり、相似写像に関してただ一つ定まる。また、この周期境界条件付きのメッシュ上で密度関数ψが定義されている場合（各メッシュ内ではそれぞれ定数値）は、Ｘがこの密度関数ψに従った理想的な点分散であるためには、
ζ（ｘ）＝Ｗｆ（ψ（ｘ））
と定義することが必要である。
【０１２３】
このとき、重み関数を、
μψ０（ｘ）＝νψ０（ｘ）＝１／√Ｗｆ（ψ（ｘ））
と定義することにより、エネルギー最小時の正確な分散密度が保証される。このようにして、まず各メッシュに周期境界がある場合の重み関数を定義した上で、次に、周期境界を外して、しかもエネルギー値は周期境界の場合と同じになるように重み関数を定めると、上述した定義式（３）が得られる。
【０１２４】
つまり、周期境界のある場合（エネルギー値が唯一つ定まる場合）を、周期境界がない場合（エネルギー値が唯一つに定まらないが近似値が定まる場合）で近似する式
【数１１】
2012039216.tif 000013
と同値な式が式（３）であるということである。
【０１２５】
まとめると、重み関数μψ、νψは、複数の点が配置された平面をメッシュ分割し、分割された各メッシュにそれぞれ独立の周期境界条件を設定した場合の理想的重み関数μψ０、νψ０に基づいてエネルギーの総和を最小化したときの点の配置構造を理想配置構造とみなし、周期境界時の重み関数μψ０、νψ０によるエネルギーの総和と非周期境界時の重み関数μψ、νψによるエネルギーの総和が近似されるように定められる。
【０１２６】
上記の式（３）に示した積分方程式の解は、逐次代入法などの方法で近似することができ、例えば、下記の式において初期値η（ａ）＝１を複数回写像することにより近似できる。典型的には数回Ｔで写像すれば充分な収束が得られる。
【数１２】
2012039216.tif 000014
【０１２７】
[方法２]
更に、上記で説明した方法１の解を近似する方法２として、重み関数μψ、νψを下記の式にように定義することができる。
【数１３】
2012039216.tif 000015
【０１２８】
この方法２を使うと、積分方程式を近似計算する過程が不要になるため、処理が簡便であり、処理時間・要メモリ量を削減することができる。
【０１２９】
[方法３]
更に、上記の方法２を近似する方法３として、
μψ（ｘ）＝νψ（ｘ）＝１／√Ｗｆ（ψ（ｘ））
あるいは
μψ（ｘ）＝１／Ｗｆ（ψ（ｘ））、νψ（ｘ）＝１
とすることができる。
【０１３０】
ここで前者は、周期境界時の重み関数μψ０、νψ０をそのままμψ（ｘ）＝μψ０（ｘ）、νψ（ｘ）＝νψ０（ｘ）として採用したものである。なお、この定義を使う場合、μψ、νψは定義域Ｅの全域で定義せずに、ψの値域全体で定義することができる。従って、例えば、ψが｛０，１，．．．，２５５｝の値しか取らないような場合には、μψ、νψはそれぞれ２５６テーブル化して良い。
【０１３１】
[方法４]
更に、上記の方法３を近似する方法４として、
μψ（ｘ）＝νψ（ｘ）＝１／√ψ（ｘ）
あるいは、
μψ（ｘ）＝１／ψ（ｘ）、νψ（ｘ）＝１
とすることもできる。
【０１３２】
この場合も方法３の場合と同様に、μψ、νψはそれぞれ２５６テーブル化が可能となる。なお、この方法４による重み関数の定義方法のうち後者は、実質上、上記の特許文献１（特開２００７−０１８９４２７号公報）に開示された点分散密度を考慮したエネルギーの定義方法に他ならない。つまり、本実施形態は、重み関数を導入したことにより、特許文献１に開示されている方法を一般化・理論的正確化したものであり、より正しい分散密度・均等分散性を得ることができる。
【０１３３】
[方法５]
この他、方法１自体をより一般化することも可能である。例えば、関数ｈを導入し、式（２）の両辺に作用させて、下記の式の解ηを重み関数として採用することができる。
【数１４】
2012039216.tif 000016
【０１３４】
この関数ｈは、例えば、０≦ｐ≦１として、下記の式とすることができる
【数１５】
2012039216.tif 000017
【０１３５】
この方法５は、上記で説明した方法２〜４と比べると分散性を損なわずに、密度関数ψの濃度変化が急峻な部分の再現度合いをより微細にコントロールでき、本発明の配置決定処理による分散ドット画像の生成に応用する場合にエッジ部のシャープネス再現性を変える事ができる。ｐ＝０の場合が方法１に相当し、ｐの値を増大させてゆくとよりシャープな結果が得られる。
【０１３６】
以上、密度関数ψから重み関数μψ、νψを定める方法の例を５通り説明してきた。これらの５つの方法１〜５では、方法１、５が理論的に最も正確な形であり、以下方法２〜４に進むにつれて近似が悪くなる。また、逆に計算時間・要メモリの点では方法１、５が最も時間・メモリを必要とし、以下方法２〜４に進むにつれて計算時間・メモリも少なくて済む。従って分散密度の再現性に要求されるレベル・計算負荷・利用可能メモリなどに応じて適当な重み関数の定義方法を選択しても良い。また、特に方法２に類する重み関数の近似式は、数値積分の近似理論を利用してこの他にも類似の近似を使うことができる。
【０１３７】
[関数ｈにより定義される評価関数ｆｒの具体例]
相互エネルギーを算出するための関数ｆｒは、前述のＨ１〜Ｈ３の条件を満たす区間［０、１］上で定義された関数ｈ（ｘ）により定めることができる。Ｈ１〜Ｈ３の条件を満たすｈ（ｘ）の具体例としては、例えば
【数１６】
2012039216.tif 000018
あるいは
ｈ（ｘ）＝（１−ｘ）5
が挙げられる。
【０１３８】
上記の条件Ｈ１〜Ｈ３を満たすｈ（ｘ）により評価関数ｆｒを定めると、ｆｒは、２点間の距離ｘが限界値ｒを超える場合に値が０となり、かつこの限界値以内の距離については単調減少で滑らかな強い凸性を持った凸関数となる。評価関数ｆｒを構成する関数ｈ（ｘ）の一例として、上記式（４）に示した関数ｈのグラフを図７に実線で示す。
【０１３９】
本発明においては、Ｈ１〜Ｈ３条件を満たしさえすればどのような関数ｈを使ってもよいが、本発明の実施形態では、図７に例示する式（４）による関数ｈ（ｘ）を、評価関数ｆｒを実現する具体例として用いている。なお、Ｈ１〜Ｈ３の条件を満たす場合、各点エネルギー自体が、点ｘの局所的な移動に対して微分可能となる。従って、図６に示したような局所振動によるエネルギー降下アルゴリズムを行っても、極小解に陥りにくいという性質を持っている。ｈからｆｒを定義する際の限界距離ｒ値は固定してよく、配置物の数（濃度）が増減しても、収束に全く問題を生じない。ｒ値は離散空間の制約から、点の数が増大するにつれて点の配置に大きな制約が掛かるため、ある程度大きく取る必要があるが、ｒ値が大きすぎると参照範囲が増大するため処理速度の低下となる。従って、例えば２値分散ドット画像への適用の際には、ｒ値は１０〜２０程度が妥当となる。
【０１４０】
一方、Ｈ１〜Ｈ３を満たさないような関数として、ハーフトーン分野で使用されることが多い関数の一例であるｅｘｐ（−ｘ2／（２σ2））のグラフを、図７に点線で示す。この関数は凸性や各点エネルギー適用時の微分可能性を持っていない。なお、この従来の関数（点線）は、その形態がｈ（ｘ）に近くなるように、パラメータσの値を調整したもの（σ＝０．２２）であり、σの調整を行っていない場合には、更にｈ（ｘ）と異なる形態を有することになる。この関数に限らず関数に数学的な保証がない場合は、このようなパラメータ調整が必要となる場合が多く、かつ一般にパラメータ調整を行っても本発明のＨ１〜Ｈ３を満たす関数で得られるような均一な点分散結果が得られない。
【０１４１】
[特許文献１における方法との差異]
上述したように、方法４による重み関数μψ、νψの定め方は、理論的に正確である方法１の方式の近似に過ぎない。上記で説明した特許文献１に開示されたエネルギーは、この方法４を用いて分散性の評価、配置決定を行うものである。方法４の点ｘにおける重み関数値μψ（ｘ）、νψ（ｘ）の定義は純粋に点ｘの密度関数ψ（ｘ）のみによっている。つまり、ｘの周囲の点には依存しておらず、同じ密度関数値ψ（画像で言えば輝度値）を持つ点には全て同じ重み関数値が割り与えられる。言い換えると、注目点の密度関数値の値のみに依存して各点の重み関数値が決められている。しかし、同じ密度関数値を持つ点であっても、周囲の密度関数値によって相互に働き合うエネルギーも変えらなければならない。つまり、注目点ｘの密度関数値の値のだけでなく、注目点の周囲の密度関数値に依存して各点の重み関数値が決められる必要がある。
【０１４２】
以下に、具体例をあげてこのことを詳しく説明する。図８（Ａ）はパッチ画像の分散ドット画像の分散性を方法４による注目点の密度関数の逆数を重み関数として定めて、本発明の配置決定方法によりエネルギー降下した画像であり、上述のように同じ密度関数値（画像の輝度）を持つ点には同じ重み関数値が与えられている。これにより、同じ輝度値を持つパッチ上の周囲の部分でオーバーシュートの現象が起こっている（パッチのフチに白いドットが集中している）。これは、同じ輝度値を持つパッチ内の重み関数値が等しいために、パッチの外側のより重み関数値の高い領域（黒ベタ部）にある点からのエネルギーが大きいために、境界領域から内側に逃げるようにドットが移動していってしまうからである。正しくは、パッチ内部の境界領域に近い部分での重み関数値がより内部の重み関数値よりも軽く設定されることによって、パッチ内部には逆に点が外側に逃げていく力が働いて、この力と上記の内側に逃げる力とが相殺されて釣り合っていなくてはならない。
【０１４３】
このことを保証するのが方法１による周期境界条件時を近似する重み関数μψ（ｘ）、νψ（ｘ）の定義である。図８（Ａ）に示した画像の元となった同じパッチ画像に基づいて、方法１による重み関数を用いて作成した分散ドット画像を図８（Ｂ）に示す。図８（Ｂ）を参照すると、境界領域でもエネルギー値が「釣り合った」状態を実現できているのが分かる。
【０１４４】
以上の説明は簡単のためにパッチ画像で行ったが、任意の画像で同じ性質があり、特に輝度変化が急峻な領域で方法４の不具合が生じやすい。以上説明したように、重み関数は注目点ｘの密度関数値の値のだけでなく、注目点ｘの周囲の密度関数値にも依存して決められることが理想的である。上記で説明した方法１により算出された重み関数μψ（ｘ）、νψ（ｘ）は、この点で理論的に正しい結果を得ることができることが説明される。
【０１４５】
[配置決定処理の実例]
次に、上記で説明した重み関数μψ（ｘ）、νψ（ｘ）を用いて、実際の原画像ψに基づいて、本発明の配置決定方法により分散ドット画像（２値点分散画像）を生成した具体例を図９〜図１１を参照して説明する。
【０１４６】
図９は、密度関数ψ（ｘ）により表現された原画像の一例である。この図９に示す原画像データは、密度関数ψ（ｘ）により、４８０×３６０の各ピクセルにおいて０〜２５５のいずれかの値が定義されている。
【０１４７】
そして、この図９に示す原画像に基づいて上記の方法１により重み関数をμψ（ｘ）、νψ（ｘ）として求めμψ（ｘ）＝νψ（ｘ）＝η（ｘ）として、１／η（ｘ）2をプロットした結果を図１０に示す。
【０１４８】
この場合、上記で説明した全点エネルギーを定義した式（１）は下記のようになる。
【数１７】
2012039216.tif 000019
【０１４９】
そのため、図１０では、η（ｘ）2の逆数である１／η（ｘ）2をプロットしている。この図１０を参照すると、図９に示した原画像と比較して、画素値が変化する境界部分が、グラデーションがかかったようにぼやけていることがわかる。
【０１５０】
そして、この重み関数μψ（ｘ）、νψ（ｘ）を用いて画像の全点エネルギーを定義し、本発明の配置決定方法により、エネルギーを降下させることによりドットの配置を決定して生成した分散ドット画像を図１１に示す。この図１１を参照すると、画素値が変化する領域においても、各ドットが原画像ψを再現するように適切に配置されていることが分かる。
【０１５１】
[その他]
以下、本実施形態の配置決定装置１０に関するその他の注意点について言及する。
【０１５２】
以上の説明は、与えられた密度関数ψに従った好適な点配置を得る方法として、ハーフトーン画像を例に説明してきた。しかし、上記の特許文献１においても詳述されているように、エネルギーは配置の良さの尺度を定めるものであり、より一般的には配置の良さを評価することが上位の概念である。この概念を用いた一つの処理が点配置を得るということと言える。また以上の説明では、理解を簡単にするためにＥは２次元平面にあることを前程に説明してきた。しかし、連続空間・離散空間を問わず、一般のｎ次元において（ｎが３以上の場合には細かい計算上の係数は自明ではないが）同様の理論に基づいて密度関数に基づいた重み関数を定め、従ってエネルギーを定めることができる。
【０１５３】
また、上記の説明では、離散空間であるハーフトーン画像上において、黒ドット全体を点集合Ｘと置いたが、白ドット全体をＸと置いても良い。また従って自明なことだが、黒ドット全体を点集合Ｘ、白ドット全体を点集合Ｙとおいて、ＸあるいはＹの点を動かしながらＸのエネルギーとＹのエネルギーを両方降下させるようにすることもできる。点ｘ（黒ドット）を点ｙ（白ドット）に移動するということは、逆に点ｙ（白ドット）は点ｘ（黒ドット）に移動するということであり、点ｘでのエネルギー降下（黒ドット）と点ｙでのエネルギー降下（白ドット）の両方を対象とすることができる。従って、点ｘの移動先としては、例えば両者のエネルギー和を低下する位置を選択しても良いし、両者が同時に低下する位置を選択しても良いし、あるいは画像のハイライト域ではＹのエネルギーが低下し画像のシャドー域ではＸのエネルギーが低下する位置を選択しても良い。
【０１５４】
また、上記の[配置決定処理]において説明したように、与えられた原画像ψ及びハーフトーン画像Ｘについて、エネルギー降下によりＸの分散性を向上する際には、任意のハーフトーン画像Ｘを初期値として利用可能である。例えば、分散ドットハーフトーンマスク、誤差拡散、網点画像、ランダムノイズなどを利用することができる。分散ドットハーフトーンマスクや誤差拡散画像など、予めある程度分散性が良い画像を初期値とすることで、収束に必要な反復回数Ｎを小さくすることができる。ランダムノイズなど分散性の悪い点配置を初期値に利用する場合、分散密度の再現が充分でないような局所最小解に陥ってしまうことを防止するために、エネルギー降下時に点ｘを近傍に移動する際には、より広い近傍を許容するようにする方が良い。但し、入力画像が全面固定濃度であるような場合にはそのような必要はない。
【０１５５】
このように任意の分散ドット画像を初期値として利用可能だが、注意すべきなのは、ｄｉｒｅｃｔ  ｂｉｎａｒｙ  ｓｅａｒｃｈ方式のように原画像とハーフトーン画像との距離を降下するわけではなく、原画像を密度関数として見た場合に、この密度関数に従うようにハーフトーン画像Ｘをエネルギー降下させてゆくだけであるという点である。つまり、エネルギーの概念においては、Ｘ内の黒ドットの数はエネルギー降下前後で変わりはなく、平均濃度が原画像と一致するというのではなく、平均濃度の比率が原画像と一致するという、より一般的な性質を持つ。そのため、原画像とハーフトーン画像の平均濃度を合わせるためには、予め初期値Ｘ内の「点の総数ｎ／総画素数」が原画像の全平均濃度と一致するようにしておかなくてはならない。初期値として原画像を直接ハーフトーン化した分散ドットハーフトーンマスク画像や、誤差拡散画像はこの性質を持っているが、例えばランダムノイズなどを利用する場合には、
【数１８】
2012039216.tif 000020
個の黒ドットを配置すれば上記の濃度一致を保証することができる。ここで、ｌ＋１が画像の総階調数であり、典型的にはｌ＝２５５を使用すると考えて良い。
【０１５６】
エネルギー降下により得られる分散ドットハーフトーン画像は、ドット分散性が均一かつ等方的でありワームなどのテクスチュアの心配がなく、ボケもなく濃度再現も正しい。従って、本実施形態により得られる分散ドットハーフトーン画像は、前述した分散ドットハーフトーン技術の先行方式である分散ドットハーフトーンマスク法、誤差拡散法、ｄｉｒｅｃｔ  ｂｉｎａｒｙ  ｓｅａｒｃｈ方式、ｄｉｓｃｒｅｐａｎｃｙ方式などと比較して画質の点で優位である。本実施形態による方法は、処理負荷に関しては、エネルギー降下という処理によって、分散ドットハーフトーンマスク法、誤差拡散法のような高速処理はできないが、ｄｉｒｅｃｔ  ｂｉｎａｒｙ  ｓｅａｒｃｈ方式、ｄｉｓｃｒｅｐａｎｃｙ方式と比較するとずっと高速である。実用上は、エネルギー有効範囲ｒを（濃度に依存して）小さく取る、初期値を分散ドットハーフトーンマスク画像とする、反復回数Ｎを小さくする、などの工夫により更に高速化が可能である。
【０１５７】
本実施形態で詳述したエネルギーの概念は、ハーフトーン画像における要求項目を的確に分離保証している点に注目できる。すなわち、分散性の正しさ（ザラツキの少なさ）に関しては、エネルギーＩ（Ｘ，ｆｒ）の構成要素のうちＨ１〜Ｈ３の条件が保証しており、画像濃度（密度関数ψ）の再現性の正しさに関しては、エネルギーＩ（Ｘ，ｆｒ）の構成要素のうち重み関数μψ、νψが保証している。つまり、分散性の良さと濃度再現性の良さは別の要素としてそれぞれコントロール・評価が可能であるということがいえる。このような見通しの良さは、従来の適応計算方式のハーフトーン技術である誤差拡散法、ｄｉｒｅｃｔ  ｂｉｎａｒｙ  ｓｅａｒｃｈ方式、ｄｉｓｃｒｅｐａｎｃｙ方式には見られないものである。
【符号の説明】
【０１５８】
１０    配置決定装置
１１    ＣＰＵ
１２    メモリ
１３    記憶装置
１４    通信インタフェース（ＩＦ）
１５    ユーザインタフェース（ＵＩ）装置
１６    制御バス
５００  データ入力部
５１０    記憶部
５２０    予備処理部
５３０    濃度特定部
５４０    分散評価部
５５０    配置更新部
５６０    判定部
５７０    データ出力部
【図１】
2012039216.tif 000021
【図２】
2012039216.tif 000022
【図３】
2012039216.tif 000023
【図４】
2012039216.tif 000024
【図５】
2012039216.tif 000025
【図６】
2012039216.tif 000026
【図７】
2012039216.tif 000027
【図８】
2012039216.tif 000028
【図９】
2012039216.tif 000029
【図１０】
2012039216.tif 000030
【図１１】
2012039216.tif 000031