(57)【特許請求の範囲】
【請求項１】
ハーフトーンイメージを生成する方法において、
受容可能な品質の画像を生成するために互いに相関した２次元２値パターンの組を発生するステップであって、各２次元２値パターンはその平均濃度レベルがデジタル入力信号の濃度レベルにそれぞれ対応し、各２次元２値パターンの組は、当該パターンの人間視覚系変調伝達関数によって重み付けされたフーリエ変換係数で示されるコスト関数の重み付け加算としての集合コスト関数が最小となるように推定的アニーリングにより同時に発生されるステップと、
イメージデータ内のピクセルを前記２次元２値パターンの組を用いて変調アドレスすることで前記イメージデータ内のピクセル値を２値に変換しハーフトーンイメージを形成するステップと、
を含み、
各パターンの組は、２次元アレイＭ（ｉ，ｊ）により発生されるものであり、前記２次元アレイＭ（ｉ，ｊ）の位置（ｉ，ｊ）における各素子には入力信号の濃度レベルを示す整数が割り当てられ、濃度レベルｑに対するパターンであるＰｑ（ｉ，ｊ）は、下式によって定められることを特徴とするハーフトーンイメージ生成方法。
0003630699.tif 000008
【請求項２】
請求項１記載の方法において、
前記２次元アレイＭは３２×３２であることを特徴とするハーフトーンイメージ生成方法。
【請求項３】
請求項１記載の方法において、
前記集合コスト関数は、各パターンのコスト関数をＣｑ、コスト関数Ｃｑの重みをＷｑとした場合、２５６グレースケールレベルにおいては下式によって定められることを特徴とするハーフトーンイメージ生成方法。
0003630699.tif 000009
【請求項４】
入力イメージ内のピクセルの濃度レベル（グレーレベル）を表すデジタル信号を前記入力イメージから発生するデジタルスキャナと、
スキャナからのデジタル信号に対して作用して受容可能な品質の画像を生成するために互いに相関した２次元２値パターンの組を発生するようにプログラムされたコンピュータであって、各２次元２値パターンはその平均濃度レベルがデジタル入力信号の濃度レベルにそれぞれ対応し、各２次元２値パターンの組は、当該パターンの人間視覚系変調伝達関数によって重み付けされたフーリエ変換係数で示される個別コスト関数の重み付け加算としての集合コスト関数が最小となるように推定的アニーリングにより同時に発生されるコンピュータであって、更に、イメージデータ内のピクセルを前記２次元２値パターンの組を用いて変調アドレスすることで前記イメージデータ内のピクセル値を２値に変換しハーフトーンイメージを形成するようプログラムされるコンピュータと、
コンピュータにより駆動されハーフトーンイメージを印刷するマーキングエンジンと、  を含み、
各パターンの組は、２次元アレイＭ（ｉ，ｊ）により発生されるものであり、前記２次元アレイＭ（ｉ，ｊ）の位置（ｉ，ｊ）における各素子には入力信号の濃度レベルを示す整数が割り当てられ、濃度レベルｑに対するパターンであるＰｑ（ｉ，ｊ）は、下式によって定められることを特徴とするハーフトーンイメージ生成装置。
0003630699.tif 000010
【請求項５】
請求項４記載の装置において、
前記マーキングエンジンは、レーザプリンタであることを特徴とするハーフトーンイメージ生成装置。
【請求項６】
請求項５記載の装置において、
前記レーザプリンタは３００−５００ドット／インチの範囲の解像度を有することを特徴とするハーフトーンイメージ生成装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明はデジタルイメージ処理分野、特に、全体が最小視覚変調用に最適化された変調ビットマップパターンの相関データベースを用いた連続トーンイメージのデジタルハーフトーニング方法に関する。
【０００２】
【従来の技術】
デジタルハーフトーニングは、眼がグレースケールレベルの表現として感受するドットとノードットとのパターンにより、連続トーンイメージをシミュレートする技術である。ハーフトーニングは、例えばドットの印刷かオープンスペースを空けることのみが可能なレーザプリンタ等の印刷装置により、連続トーン写真を表すために用いられる。平均所望濃度またはグレースケールレベルを表し得るドットとノードットとのパターンには、ほぼ無制限といえる数のものが存在することが想像できよう。しかし、そのようなパターンは、画質を著しく劣化させるモワレパターン等の視覚ノイズを含んだイメージを生成することがある。従って、本発明の目的は、特定信号グレーレベルを平均的に表すドットとノードットとのパターンに対して視覚的に感受される変調ノイズを最小限に抑制することにある。
【０００３】
連続トーンイメージを発生するためのハーフトーニングは、１９６０年代中期から実用化されている（Ｃｏｍｍ．ｏｆ  ｔｈｅ  ＡＣＭ，Ｖｏｌ．７，Ｎｏ．５  ｐｐ３１１−３１３にＰｅｒｒｙ  ａｎｄ  Ｍｅｎｄｅｌｓｏｈｎにより記述された「Ｐｉｃｔｕｒｅ  Ｇｅｎｅｒａｔｉｏｎ  ｗｉｔｈ  Ｓｔａｎｄａｒｄ  Ｌｉｎｅ  Ｐｒｉｎｔｅｒ」参照）。現在使用されている主な２つの技術は、デイザリング及びエラー拡散である。ＭＩＴ  Ｐｒｅｓｓ，Ｃａｍｂｒｉｄｇｅ，Ｍａｓｓａｃｈｕｓｅｔｔｓ，ｐｐ７７−７９，１２７，２３９−２４０にＵｌｉｃｈｎｅｙにより記載されたＤｉｇｉｔａｌ  Ｈａｌｆｔｏｎｉｎｇを参照。最も注目すべきデイザリング技術は、ランダムデイザー、クラスタードットデイザー、散乱ドットデイザー、及びデイザーパターン索引表である。ランダムデイザーが最初に開発されたのであるが、生成される画質が低いためにほとんど使用されていない。
【０００４】
クラスタードットデイザー及び散乱ドットデイザーは、圧倒的に最も広く普及しているクラスタードットデイザーと共に用いられる。これらの技術は、しきい値スクリーンパターンに基づいている。該パターンは、通常は固定サイズ例えば８ｘ８のイメージピクセルであり、これが入力デジタルイメージ値と比較される。もし入力値がスクリーンパターン数よりも大きければ出力は「ｏｎ」に設定され、それ以外の場合には「ｏｆｆ」へセットされる。しきい値マップは、通常シーケンシャルに構成され、その出力パターンは前ハーフトーン濃度レベルに対して為された決定に対して条件が定められる。クラスタードットパターン技術の場合には各パターンは中心成長ドットから展開するが、この方法はドットサイズが変化可能なリソグラフィー等のグラッフィクアート装置で生成されるハーフトーンと同様である。
【０００５】
大きなパターンを用いるほど得られるレベルも大きくなるが、同時にレベル間移行のピッチがそれに応じて粗くなるので、有効解像度が低減してしまう。例えば３００−５００ドット／インチのコピー機及びプリンターの中間ピクセルレートでは、４ｘ４より大きなスクリーンパターンでパターンアーテイファクトが視認可能になってしまう。結果として得られる有効レベル数例えば１６は、通常の連続トーンイメージには不適である。
【０００６】
デイザーパターン索引表は、エラー拡散等の方法に対する実行の簡易性を維持しつつ、しきい値法に通常生じる解像度が低減するという問題を回避しようというものである。これらのパターンは、変調形態でアクセスされるこの技術におけるデータベースとして使用される。この技術におけるデータベース内の各ハーフトーンパターンは、選択されたグレースケールに対して視覚歪が最小となるよう独立的に定められる（ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｓｙｓｔｅｍｓ，Ｍａｎ  ａｎｄ  Ｃｙｂｅｒｎｅｔｉｃｓ，Ｖｏｌ．２２１，Ｎｏ．１，１９９１，ｐｐ．３３−３８にＪ．Ｓｕｌｌｉｖａｎ，Ｌ．Ｒａｙ  ａｎｄ  Ｒ．Ｍｉｌｌｅｒによって記載された「Ｄｅｓｉｇｎ  ｏｆ  Ｍｉｎｉｍｕｍ  Ｖｉｓｕａｌ  Ｍｏｄｕｌａｔｉｏｎ  Ｈａｌｆｔｏｎｅ  Ｐａｔｔｅｒｎｓ」参照）。これらのパターンは、ｔｉｎｔ−ｆｉｌｌ装置に対しては優れているが、一般的な撮像装置に適用した時の結果は期待できない。
【０００７】
エラー拡散は、固定パターンが存在しないデイザーパターンハーフトーニングアプローチとは基本的に異なるものであるが、それに代えて帰納的アルゴリズムが用いられる。該アルゴリズムは、２値で連続入力信号を表すことにより生じたエラー原因を補正する。エラー拡散の２個の主成分は、フラクションのマトリックスである。フラクションマトリックスは、重み付けされた過去のエラー及び該重み付けされたエラーの総和に基づくしきい値演算子と、「ｏｎ」または「ｏｆｆ」のいずれを出力するかを定める現ピクセルと、である。エラー拡散技術は、２次元型即ちエラーが前ライン及び前ピクセルからフィードバックされるものが最も優れている。エラーフィードバックメカニズムは通常線形であり総和エラーは過去のエラーの線形組み合わせであるが、しきい値設定は非線形であり、これによって複合処理も非線形となる。しきい値設定を信号依存ゲインとして近似させると、正エラー重み付けに対して出力２値信号が、イメージへの「青ノイズ」を導入する均一イメージ領域における高域通過性（ハイパス）となる（上記引用したＵｌｉｎｃｈｎｅｙ参照）。Ｕｌｉｎｃｈｎｅｙにより言及されているように、この「青ノイズ」は、その感知が人視覚系により低域通過ろ過されると更に高次な信号−ノイズ比感受性が得られるので低減され、極めて好ましい特徴である。
【０００８】
【発明が解決しようとする課題】
残念ながら、エラー重み付けは、この好適なノイズ特性には間接的に関わるものである故に、最適状態には及ばない次善的制御にとどまる。また或信号レベルに対しては、カジュアルフィードバックは視覚的に受け付けない「虫様」または相関パターンを発生する視覚的に不安定なものとなる可能性がある。最も一般的な解決法は重み付けを無作為に変調することであるが、これは、「虫様」を低減するがノイズをも増大してしまう。
【０００９】
個々のハーフトーンパターンは、受容可能品質の画像をそれぞれ生成するために相関させなければならない。パターンを相関させないアプローチでは、画像ノイズが激しくなり、これはランダムドットデイザーパターンを用いた時の結果とほぼ同様となる。一般的なアプローチは、パターンの巣状組を定めることである（Ｐｒｏｃ．ＩＥＥＥ  Ｉｎｔ．Ｃｏｍｍ．Ｃｏｎｆｅｒｅｎｃｅ  Ｒｅｃｏｒｄ，ｐｐ．（２６−１１）−（２６−１５）にＢ．Ｅ．Ｂａｙｅｒによって記載された「Ｏｐｔｉｍａｌ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｔｗｏ−Ｌｅｖｅｌ  Ｒｅｎｄｉｔｉｏｎ    ｏｆ  Ｃｏｎｔｉｎｕｏｕｓ−Ｔｏｎｅ  Ｐｉｃｔｕｒｅｓ」参照）。
【００１０】
他のハーフトーニング法では、視覚モデルを用いてハーフトーンパターンが設計される。これらのパターンは通常「青ノイズ」パターンと呼ばれるものである。上述のように、「青ノイズ」は望ましい特徴ではある。しかし、従来技術では、各パターンの選択は格子またはシーケンシャル決定プロセスのいずれかによってシーケンシャルに行われる（米国特許出願第４７６０９０号（発明の名称：「相関最小可視変調パターンを用いたデジタルハーフトーニング」；  出願日：１９９０年２月７日；  発明者：  Ｌａｗｒｅｎｃｅ  Ａ．Ｒａｙ及びＪａｍｅｓＲ．Ｓｕｌｌｉｖａｎ）及び「ブルーノイズマスクを用いたデジタルハーフトーニング」（著者：  Ｔｈｅｏｐｈａｎｏ  Ｍｉｔｓａ及びＫｅｖｉｎ  Ｊ．Ｐａｒｋｅｒ，ｉｎ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ  Ａｌｇｏｒｉｔｈｍｓａｎｄ  Ｔｅｃｈｎｉｑｕｅｓ  ＩＩ，ＳＰＩＥ  Ｖｏｌ．１４５２，１９９１，ｐｐ．４７−５６）参照）。これらの方法は、シーケンシャル決定プロセスに依存するものであるため、制限される。このようなシーケンシャル決定プロセスは、各段階での結果を最適化しようとするものであるが、後段のパターン選択プロセスの結果は次善的なもので終わっている。
【００１１】
本発明は上記従来技術の有する課題に鑑みなされたものであり、確実に、各パターンが連続したグレースケールレベルに対して巣状とされると共に各パターン間の相関が維持でき、相関パターン全体として最適なものを得ることができるハーフトーンイメージ生成方法及び装置を提供することにある。
【００１２】
【課題を解決するための手段及び作用】
ハーフトーンイメージを生成するための本発明に係る方法は、相関最小視覚変調２次元２値パターンの集合体を発生するステップを含む。各パターンは、デジタル入力信号の一の濃度レベルに対応している。複数のパターンから成る組は、各パターンの人間視覚系変調伝達関数によって重み付けされたフーリエ変換係数で示される個別コスト関数の重み付け加算としての集合コスト関数が最小となるように同時に発生する。各パターンは、その後変調アドレスされ、ハーフトーンパターンを形成するためのビットを選択する。一実施例では、各パターンの組は合成最小化技術である推計学的アニーリングにより生成される。
【００１３】
ハーフトーンパターンは、２次元ピクセルアレイによって定められる。該アレイの各素子は、ハーフトーンパターンが正しい平均濃度を持つように選択された入力信号のピクセル濃度レベルを表す整数である。２次元アレイはＮｘＮ、特に３２ｘ３２であることが望ましい。適切な集合体コスト関数は、視覚変調移行関数によって乗算された個別フーリエ変換の係数から派生した個別ビットパターンに対するコストの和である。ＮｘＮピクセル（例：３２ｘ３２）アレイは、イメージ中の各濃度レベルに対してビットマップパターンを明確に定める。各パターンは、相関され、イメージ中の各ピクセル値及び各ピクセル位置を用いたパターンの相関及び係数アドレシングにより加えられた制約範囲内で全体として最小の視覚ノイズとなる。各グレーレベルにおいて、アレイは個別に正しい平均濃度をもつハーフトーンパターンを定める。
【００１４】
本発明のポイントは、従来技術で周知のシーケンシャルプロセスと異なり、各パターンが同時に展開されることである。本発明の技術は、構成の複雑性を最小限としつつ最適画質を発生することができる。この品質は、局部的に最適化されるか或いは最適化が前の決定または前の最適化に対して条件付けられるシステムとは異なり、全体的に最適化されることによって達成される。従来技術において、各パターンは、相関されているにもかかわらず前の結果に対して高度に条件化されたレベルで望ましくない空間周波数を示し始めるが、前パターン選択のためにこれらの空間周波数を除去できないのである。本発明によれば、集合体を全体として最適化することにより、各パターン相互のバランスを確立できるので、例えば奇数であるというような不適切な数値的特性によって特定のパターンに不都合が生じることはなくなる。
【００１５】
本発明で使用されるコスト関数は、ハーフトーンパターンに伴うノイズを、完全ランダム構造として現れそして視覚的に訴えるような方法で拡大する。このようにして、本発明では、従来技術で視認者の目がとらえていた分離空間周波数を除去する。
【００１６】
【実施例】
以下において、２５６グレースケールレベルに対する各パターンは、３２ｘ３２アレイＭを用いて設計されるものとする。本発明の方法は汎用的なものであり、任意のレベル数及びアレイサイズへ適用可能であることを強調しておく。２５６グレースケールレベルに対しては、アレイＭの各素子は、０と２５５との間の整数値である。各グレーレベルにおいて、アレイＭは正しい平均濃度をもつハーフトーンパターンを個別に定める。グレースケールレベルｑに対しては、ハーフトーンパターンＰｑ  は次式（１）によって定められる
0003630699.tif 000002
各ハーフトーンパターンは、受容可能な品質の画像を生成するために相関される必要がある。上述したように、各パターンを相関させない方法では、ランダムドットデイザーパターンを用いた場合とほぼ同様に深刻な画像ノイズ発生を招く。上記式（１）で表された方法により、各パターンは確実に連続グレーレベルに対して巣状化されると共にその相関が維持される。
【００１７】
本発明に係るハーフトーン画像発生方法は、全入力ピクセルレベルに対して同時に相関最小視覚変調パターンを設定するステップと、各パターンを変調アドレスしてハーフトーン画像中で使用されるビットを選択するステップと、を含む。ここでは、ビットマップパターンの設定をまず説明し、次いでアドレシング及びパターン選択プロセスに言及する。
【００１８】
本発明の目的は、平均的に特定信号レベルを表示するドットと非ドットとのパターンに対する視覚変調を最小限に抑制することである。更に、各パターンは、各パターン間における入力信号差または組織差に起因する変位により発生するあらゆるアーチファクトを低減するため、十分に相関されなければならない。パターン発生基準の第１アスペクトとしては、与えられたパターンに対する視覚的変調またはコストの定義、及びコスト最小化の方法が必要となる。パターン発生の第２アスペクトは、各パターンを相関させること及び同時に全体を設定するために使用される全体コストを定めることである。
【００１９】
通常の視覚距離すなわち１０インチに対する人間の視覚系の有効２次元変調伝達機能ＭＴＦが図２に示されている。この伝達機能には、人間視覚系の低コントラスト明所ＭＴＦの機能モデルにおける第１オーダーに設定された視覚変調の定義が必要となる（ＳＰＩＥ    Ｐｒｏｃ．，Ｖｏｌ．１０７７，１９８９，ｐｐ．２１７−２２７にＳ．Ｄａｌｙ，ＳＰＩＥ    Ｐｒｏｃ．，によって記載された「Ａｐｐｌｉｃａｔｉｏｎ    ｏｆ    ａ    ｎｏｉｓｅ    ａｄａｐｔｉｖｅ    ｃｏｎｓｔｒａｓｔ    ｓｅｎｓｉｔｉｖｉｔｙ    ｆｕｎｃｔｉｏｎ    ｔｏ    ｉｍａｇｅ    ｄａｔａ    ｃｏｍｐｒｅｓｓｉｏｎ」参照）。ＭＴＦ機能は、次式により与えられる。
【００２０】
0003630699.tif 000003
ここで、定数ａ，ｂ，ｃ及びｄは経験的にそれぞれ２．２，０．１９２，０．１１４及び１．１と演算され、ｆｉｊ´は視覚距離に対してスケールされた視覚対辺のサイクル／度で表されるラジアル空間周波数であり、ｆｍａｘ  は機能的ＭＴＦ関数がピークとなる周波数である。この機能を実行するためには、離散水平及び垂直ドキュメント周波数｛ｆｉ  ，ｆｊ  ｝をラジアル視覚周波数へ変換することが必要である。
【００２１】
対称的印刷グリッドに対しては、水平及び垂直離散周波数は周期的であり、ドットピッチΔ及び周波数の数Ｎに関する次式で与えられる。
【００２２】
ｆｉ  ＝（ｉ−１）／ΔＮ
ｆｊ  ＝（ｊ−１）／ΔＮ                                                      （３）
これらをラジアル周波数へ変換し、そしてその結果を視認距離ｄｉｓ（ｍｍ）に対するサイクル／視覚度へスケーリングすることによって、次式が得られる。
【００２３】
【数１】
0003630699.tif 000004
視覚ＭＴＦの変動を視角θの関数として説明するには、これらの周波数を角度依存関数Ｓｉｊ（θ）によって標準化し、式（４）を用いることが好適である。これは、
ｆｉｊ´＝ｆｉｊ／Ｓｉｊ（θ）                            （５）
ここで、角標準化関数Ｓｉｊ（θ）はＤａｌｙによって次のように与えられている。
【００２４】
【数２】
0003630699.tif 000005
ここで、ｗは対称パラメータであり、そしてθは次式で表される。
【００２５】
θ＝ａｒｃｔａｎ（ｆｊ  ／ｆｉ  ）                                  （７）
式（６）を検討すると、ｗが減少するに従って、Ｓｉｊ（θ）がほぼ４５度へ減少する。これによってｆ´が増大してＶｉｊが減少し、この結果、視覚ＭＴＦがこれらの角度において更に低域通過性が増す。Δ＝０．０６２５（すなわち４００ドット／インチ）、Ｎ＝３２、及びｗ＝０．７における通常視距離での視覚ＭＴＦが図１に示され、同図には視覚系の低域通過特性及び低減された４５度の感度が明かにされている。
【００２６】
用いることが可能な多くのコスト関数が存在しており、ここで開示したアプローチは特定のコスト関数へ限定されるものではない。一の明白なコスト関数は、次式で与えられる。
【００２７】
0003630699.tif 000006
ここで、Ｒｉｊ２  は、ハーフトーンパターンのフーリエ変換の平方の大きさである。もし人間の視覚系が真に線形であれば、式（２）のＭＴＦはハーフトーンノイズの感受性を完全に特徴化するのに十分となる。しかしながら、人間の視覚系が線形でなく周期的ノイズ及び複製パターンに極めて感受性が強いので、式（８）により表されたものよりも更に洗練されたコスト関数が望ましい。
【００２８】
パターンＭ（ｉ，ｊ）  から派生した特定ＮｘＮビットパターンＰｑ  に対するコストをＣｑ  とする。全体の総コスト、すなわち集合コスト関数は、ｑ＝１，．．．，２５４に対する全Ｃｑ  の重み付けされた和により与えられる。象徴的に、
0003630699.tif 000007
ここで、Ｗｑ  ，ｑ＝１，２５４は、重み付けの組であり、本発明では全てのＷｑは等しい。重み付けＷｑ  の選択は、設計パラメータである。もし中間グレースケールレベルがより重要なのであれば、相対重み付けが増大する。
【００２９】
拡散ドットパターンの有効グレースケールは、単純に期待されるように線形に変化するように示されている。Ｉ．Ｃｈｅｎにより記載された「Ｓｔｏｃｈａｓｔｉｃ  Ｍｏｄｅｌ  ｏｆ  Ｈａｌｆｔｏｎｅ  Ｉｍａｇｅｓ  ｉｎ  Ｄｉｇｉｔａｌ  Ｅｌｅｃｔｒｏｇｒａｐｈｙ」、Ｊｏｕｒｎａｌ  ｏｆ  Ｉｍａｇｉｎｇ  Ｓｃｉｅｎｃｅ，Ｖｏｌ．３５，Ｎｏ．１，Ｊａｎｕａｒｙ／Ｆｅｂｒｕａｒｙ  １９９１，ｐｐ．４４−４８参照。しかしながら、非線形性はテーブルエントリーを唯一となるように選択し、最良相関パターンを定めるために推定学的アニーリング処理を適用することによってしきい値マップを変更することによって容易に処置可能である。Ｃｈｅｎ  ｒｅｆｅｒｅｎｃｅからモデルを適用することにより、感受されたグレースケールは評価可能であり、そして１０２４の２５６値が線形応答性を維持するように選択可能である。
【００３０】
パターン集合体の大きな数が決定可能であるから、最適集合体の選択は有効（重要）な組み合わせの問題となる。集合体を最適化するための一の方法は、遺伝的アルゴリズムである（「Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍｓ  ｉｎ  Ｓｅａｒｃｈ  Ｏｐｔｉｍｉｚａｔｉｏｎ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ」  ｂｙ  Ｄａｖｉｄ  Ｅ．  Ｇｏｌｄｂｅｒｇ，Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ，Ｒｅａｄｉｎｇ，Ｍａｓｓ．１９８９  参照）。集合体を最適化する他の方法は、推定学的アニーリングまたはシミュレートされたアニーリングとして知られる方法を適用することである（「Ｄｅｓｉｇｎ  ｏｆ  Ｍｉｎｉｍｕｍ  Ｖｉｓｕａｌ  Ｍｏｄｕｌａｔｉｏｎ  Ｈａｌｆｔｏｎｅ  Ｐａｔｔｅｒｎｓ」、ｂｙ  Ｊ．Ｓｕｌｌｉｖａｎ，Ｌ．Ｒａｙ  ａｎｄ  Ｒ．Ｍｉｌｌｅｒ，ＩＥＥＥ  Ｔｒａｎｓ．ｏｎ  Ｓｙｓｔｅｍｓ，Ｍａｎ  ａｎｄ  Ｃｙｂｅｒｎｅｔｉｃｓ，Ｖｏｌ．２１，Ｎｏ．１，Ｊａｎｕａｒｙ１９９１，ｐｐ．３３−３８を参照。この方法のキーとなる特徴は、それが個別サーチスペースに極めて適していること及び局部最小は各反復におけるコスト増大受容可能性によってエスケープされ得ることである。
【００３１】
推定的アニーリングは、現在の形態及びその視覚コストを演算することによって実行される。アレイＭ中における２個のエントリーはランダムに選択され、すなわち、もしＭ（（ｉ，ｊ）０  ）  ≠Ｍ（（ｉ，ｊ）１  ）  であれば（ｉ，ｊ）  ０  及び（ｉ，ｊ）  １  であり、２つのエントリーは交換される。また、Ｍ（（ｉ，ｊ）０  ）  ＝ｑ０  及びＭ（（ｉ，ｊ）１  ）  ＝ｑ１  であるならば、ｑ０  ≦ｑ≦ｑ１  に対する全てのパターンＰｑ  が乱され新たな視覚コストが新たなＭアレイのコストを設定するために演算されなければならない。
【００３２】
以下に、パターンサイズが３２ｘ３２であるが、明かな変更によってこれらのパターンを他のアレイサイズへ拡大することが可能である。
【００３３】
推定的アニーリングの詳細は次の各ステップに含まれる。
【００３４】
１．パターンＰｑ  が正しい平均グレースケール値を持つようにランダム選択されたエントリーでアレイＭを開始する。３２ｘ３２アレイＭを用いた２５６グレースケールレベルの場合には、開始されたアレイＭは５１、１０２、１５３及び２０４等の４個の値が正確に５回選択されるようにランダム選択されたエントリーを有し、そして１と２５４との間の全ての他の値は正確に４回選択された。
【００３５】
２．アレイＭの視覚コストを上述のように定め、Ｃ０  とする。
【００３６】
３．Ｍにおける２個のエントリーを交換してアレイＭ１  を形成し、コストＣ１  を演算する。
【００３７】
４．Ｃ０  とＣ１  との絶対差を演算し、その結果をテーブル内に記憶する。
【００３８】
５．各ステップ１−４を多数回例えば１０００回実行し、テーブルを順次分類し、テーブルエントリー８００に対して初期に受け入れられるコスト増大例えば８０％の比率を表す値を選択する。
【００３９】
６．次式で与えられるテスト統計τを演算する。
【００４０】
τ＝ｅｘｐ（−Ｔａｂｌｅ（８００））
この統計は一般にシステムの温度として知られ、初期温度として使用される。
【００４１】
７．新たなアレイＭを構成する。
【００４２】
８．このアレイの視覚コストを演算し、Ｃｏｌｄ  とする。
【００４３】
９．アレイＭの２個のエントリーを交換し、その結果得られる視覚コストＣｎｅｗ  及び視覚コストの変化ΔＣｏｓｔ  ＝Ｃｏｌｄ  −Ｃｎｅｗ  を演算する。
【００４４】
１０．もしΔＣｏｓｔ  ≦０．０であるならば、変化及びＣｏｌｄ  ＝Ｃｎｅｗ  を受容する。
【００４５】
１１．もしΔＣｏｓｔ  ＞０．０であるならば、統計ρ＝ｅｘｐ（−ΔＣｏｓｔ  ／τ）及びランダム数ζ、０＜ζ＜１を演算する。もしρ＜ζであるならば、新たな構成及びＣｏｌｄ  ＝Ｃｎｅｗ  を受容する。それ以外の場合には、アレイＭはそのままになる。
【００４６】
１２．各ステップ８−１１を多数回例えば１０００回繰り返し、その後温度τをκ＜１である或ファクタκ分だけ低減し、新たな温度κτを形成する。
【００４７】
１３．各ステップ８−１２を多数回例えば１００回或いは視覚コストがそれ以上減少しなくなるまで繰り返す。
【００４８】
図１は、本発明の技術を示したブロック図である。デジタルスキャナ１０は、連続トーン写真等の入力画像を走査し、各ピクセルに対してピクセルのグレースケールレベルの２値表示を発生する。デジタルスキャナ１０の出力は、スーパーコンピュータ等の汎用コンピュータ１２によって処理される。コンピュータ１２は上述の処理によって個々のハーフトーンパターンを発展させ、各グレースケールレベルに対するパターンを生成する。上述した実施例において、コンピュータ１２はコンピュータ１２内のメモリ内に記憶された２５６のパターンを発生する。ピクセルのグレースケールレベルに対応するパターンは、３００−５００ドット／インチの解像度をもつレーザプリンタ等のプリンタであるマーキングエンジン１４によって印刷される。処理は、入力物質の各ピクセルに対して繰り返される。このようにして、視覚ノイズを最小限に低減するハーフトーンイメージが生成される。
【００４９】
【発明の効果】
以上説明したように、本発明のハーフトーンイメージ生成方法及び装置によれば、確実に、各パターンが連続したグレースケールレベルに対して巣状とされると共に各パターン間の相関が維持でき、相関パターン全体として最適なものを得ることができる。
【図面の簡単な説明】
【図１】本発明の実施例におけるデジタルハーフトーンイメージ生成装置の構成ブロック図である。
【図２】本発明の実施例における人間の視覚変調伝達機能のグラフである。
【符号の説明】
１０  デジタルスキャナ
１２  コンピュータ
１４  マーキングエンジン
【図１】
0003630699.tif 000011
【図２】
0003630699.tif 000012