(57)【要約】【課題】ブロック量子化を用いてカラーハーフトーン化を実施する方法及び装置を提供することを目的とする。【解決手段】本発明の一実施形態にしたがった方法は、入力画像を複数のブロックに分割する段階、複数のブロックの各々における画素を複数のカラーグループにクラスター化する段階、複数のブロックの各々についての複数のカラーグループの各々を代表カラー値にブロック量子化する段階、並びに、各々の異なるブロックによりカバーされた空間領域において近似される前記各々の異なるブロックの各々のグループのための代表カラー値を用いて、複数のブロックにおける各々のブロックに関連する異なるブロックを有する出力ハーフトーン画像を生成する段階、から構成される。【選択図】　　　図１
2004056783.tif 000002
【特許請求の範囲】
【請求項１】
入力画像を複数のブロックに分割する段階；
複数のブロックの各々の画素を複数のカラーグループにクラスター化する段階；
複数のブロックの各々のための複数のカラーグループの各々を代表カラー値にブロック量子化する段階；並びに
各々の異なるブロックにおけるグループによりカバーされた空間領域において近似される前記各々の異なるブロックにおける各々のグループのための代表カラー値を用いて、複数のブロックにおける各々のブロックに関連する異なるブロックを有する出力ハーフトーン画像を生成する段階；
から構成される方法。
【請求項２】
請求項１に記載の方法であって、複数のグループは多くとも３つのグループから構成される、方法。
【請求項３】
請求項１に記載の方法であって、複数のグループは多くとも４つのグループから構成される、方法。
【請求項４】
請求項１に記載の方法であって、複数のカラーグループの少なくとも１つのための代表カラー値は１つのカラーグループにおける１つまたはそれ以上のカラーの平均カラー値である、方法。
【請求項５】
請求項１に記載の方法であって、第１の複数のブロックの各々におけるカラーを複数のカラーグループにクラスター化する段階、第１の複数のブロックの各々のための複数のカラーグループの各々を代表カラー値にブロック量子化する段階、並びに、第１の複数のブロックにおける各々のブロックに関連する異なるブロックを有する出力ハーフトーン画像を生成する段階からなる操作が、並列に実行される、方法。
【請求項６】
請求項１に記載の方法であって、入力画像は１２ｘ１２ブロックに分割される、方法。
【請求項７】
請求項１に記載の方法であって、入力画像は１６ｘ１６ブロックに分割される、方法。
【請求項８】
請求項１に記載の方法であって、複数のブロックの各々における画素の複数のカラーグループへのクラスター化は画素のカラー値に基づいている、方法。
【請求項９】
請求項１に記載の方法であって、複数のブロックの各々における画素の複数のカラーグループへのクラスター化は画素の空間位置に基づいている、方法。
【請求項１０】
請求項１に記載の方法であって、複数のブロックの各々における画素の複数のカラーグループへのクラスター化は反対カラー空間の画素のカラー値に基づいている、方法。
【請求項１１】
請求項１に記載の方法であって、複数のブロックの各々における画素の複数のカラーグループへのクラスター化は、前記各々のブロックにおける画素の数に等しいサイズをもつ複数のブロックの各々のためのベクトルを生成し、各々の画素がどのカラーグループに属すかを示すためにベクトルのエントリがマークされる、方法。
【請求項１２】
請求項１に記載の方法であって、複数のブロックの各々における画素を複数のカラーグループにクラスター化する段階は：
ブロックにおける画素において反復する手順であって、各々のブロックにおける各々の画素のカラーを１つまたはそれ以上のグループの代表カラーと比較すること、並びに、所定の距離より小さい１つのカラーグループの代表カラーへのカラーにおける距離に基づいて、複数のカラーグループのうち１つに属するように画素にマーキングすることを含む、反復する手順から構成される；
方法。
【請求項１３】
入力画像を複数のブロックに分割するための手段；
複数のブロックの各々における画素を複数のカラーグループにクラスター化するための手段；
複数のブロックの各々のための複数のカラーグループの各々を代表カラー値にブロック量子化するための手段；並びに
各々の異なるブロックにおけるグループによりカバーされた空間領域において近似される前記各々の異なるブロックにおける各々のグループのための代表カラー値を用いて、複数のブロックにおける各々のブロックに関連する異なるブロックを有する出力ハーフトーン画像を生成するための手段；
から構成される装置。
【請求項１４】
請求項１３に記載の装置であって、複数のグループは多くとも３つのグループから構成される、装置。
【請求項１５】
請求項１３に記載の方法であって、複数のグループは多くとも４つのグループから構成される、装置。
【請求項１６】
請求項１３に記載の装置であって、複数のカラーグループの少なくとも１つのための代表カラー値は１つのカラーグループにおける１つまたはそれ以上のカラーの平均カラー値である、装置。
【請求項１７】
請求項１３に記載の方法であって、第１の複数のブロックの各々におけるカラーを複数のカラーグループにクラスター化するための手段、第１の複数のブロックの各々のための複数のカラーグループの各々を代表カラー値にブロック量子化するための手段、並びに、第１の複数のブロックにおける各々のブロックに関連する異なるブロックを有する出力ハーフトーン画像を生成するための手段が、並列に動作する、装置。
【請求項１８】
請求項１３に記載の装置であって、入力画像は１２ｘ１２ブロックに分割される、装置。
【請求項１９】
請求項１３に記載の装置であって、入力画像は１６ｘ１６ブロックに分割される、装置。
【請求項２０】
請求項１３に記載の装置であって、複数のブロックの各々における画素の複数のカラーグループへのクラスター化は画素のカラー値に基づく、装置。
【請求項２１】
請求項１３に記載の装置であって、複数のブロックの各々における画素の複数のカラーグループへのクラスター化は画素の空間位置に基づいて動作する、装置。
【請求項２２】
請求項１３に記載の装置であって、複数のブロックの各々における画素の複数のカラーグループへのクラスター化は反対カラー空間の画素のカラー値に基づいて動作する、装置。
【請求項２３】
請求項１３に記載の装置であって、複数のブロックの各々における画素の複数のカラーグループへのクラスター化のための手段は、前記各々のブロックにおける画素の数に等しいサイズをもつ複数のブロックの各々のためのベクトルを生成するための手段から構成され、各々の画素がどのカラーグループに属すかを示すためにベクトルのエントリがマークされる、装置。
【請求項２４】
請求項１３に記載の装置であって、複数のブロックの各々における画素を複数のカラーグループにクラスター化するための手段は：
ブロックにおける画素を通して反復するための手段であって、各々のブロックにおける各々の画素のカラーを１つまたはそれ以上のグループのカラー代表と比較する手順、並びに、所定の距離より小さい１つのカラーグループのカラー代表へのカラーにおける距離に基づいて、複数のカラーグループのうち１つに属するように画素にマーキングする手順を含む、反復から構成される；
装置。
【請求項２５】
記憶される実行可能な指令を有する１つまたはそれ以上の媒体から構成される製造物品であって、システムにより実行されるとき、システムが：
入力画像を複数のブロックに分割し；
複数のブロックの各々における画素を複数のカラーグループにクラスター化し；
複数のブロックの各々のための複数のカラーグループの各々を代表カラー値にブロック量子化し；並びに
各々の異なるブロックにおけるグループによりカバーされた空間領域において近似される前記各々の異なるブロックにおける各々のグループのための代表カラー値を用いて、複数のブロックにおける各々のブロックに関連する異なるブロックを有する出力ハーフトーン画像を生成する；
ようにする製造物品。
【請求項２６】
請求項２５に記載の製造物品であって、複数のカラーグループの少なくとも１つのための代表カラーは１つのカラーグループにおける１つまたはそれ以上の平均カラー値である、製造物品。
【請求項２７】
請求項２５に記載の製造物品であって、第１の複数のブロックの各々におけるカラーを複数のカラーグループにクラスター化する段階、第１の複数のブロックの各々のための複数のカラーグループの各々を代表カラー値にブロック量子化する段階、並びに、第１の複数のブロックにおける各々のブロックに関連する異なるブロックを有する出力ハーフトーン画像を生成する段階からなる動作が、並列に実行される、製造物品。
【請求項２８】
請求項２５に記載の製造物品であって、画素のカラー値に基づいて、システムにより実行されるとき、システムが複数のブロックの各々における画素を複数のカラーグループにクラスター化するようにする指令がクラスター化をもたらす、製造物品。
【請求項２９】
請求項２５に記載の製造物品であって、画素の空間位置に基づいて、システムにより実行されるとき、システムが複数のブロックの各々における画素を複数のカラーグループにクラスター化するようする指令がクラスター化をもたらす、製造物品。
【請求項３０】
請求項２５に記載の製造物品であって、反対カラー空間の画素のカラー値に基づいて、システムにより実行されるとき、システムが複数のブロックの各々における画素を複数のカラーグループにクラスター化するようにする指令がクラスター化をもたらす、製造物品。
【請求項３１】
請求項２５に記載の製造物品であって、複数のブロックの各々における画素を複数のカラーグループにクラスター化するための指令は、システムにより実行されるとき、システムが前記各々のブロックにおける画素の数に等しいサイズをもつ複数のブロックの各々のためのベクトルを生成するようにする指令から構成され、各々の画素がどのカラーグループに属すかを示すためにベクトルのエントリがマークされる、製造物品。
【請求項３２】
請求項２５に記載の製造物品であって、システムにより実行されるとき、システムが複数のブロックの各々における画素を複数のカラーグループにクラスター化するようにする指令は：
ブロックにおける画素を通して、各々のブロックにおける各々の画素のカラーを１つまたはそれ以上のグループの代表カラーと比較すること、並びに、所定の距離より小さい１つのカラーグループの代表カラーへのカラーにおける距離に基づいて、複数のカラーグループの１つに属するように画素をマーキングすること、を少なくとも一部として、システムが反復するようにする、指令から構成される；
製造物品。
【請求項３３】
入力画像を複数のブロックに分割する段階；
画像の画素のカラーに基づいて各々のブロックにおける画像の画素を複数のグループにグループ化する段階；
複数のグループの各々のための代表カラーを選択する段階；
複数のグループの各々のための代表カラーを近似するためにカラー空間のインクドットの分布を決定する段階；
各々のグループのための印刷カラーの最終分布を決定する段階；並びに
前記各々のグループをカバーする配置マスクに基づいて各々のグループのためにインクドットを配置する段階；
から構成される方法。
【請求項３４】
請求項３３に記載の方法であって、配置マスクに基づいて各々のグループのために画素を配置する段階は、前記各々のグループをカバーする配置マスクの数にしたがって輝度の順序に画素を配置する手順から構成される、方法。
【請求項３５】
請求項３３に記載の方法であって、複数のグループの各々のための代表カラーは前記各々のグループにおけるカラーのカラー平均から構成される、方法。
【請求項３６】
請求項３３に記載の方法であって、複数のグループの各々のための代表カラーは前記各々のグループにおけるカラーのメジアンカラーから構成される、方法。
【請求項３７】
請求項３３に記載の方法であって、複数のグループの各々のための代表カラーは前記各々のグループにおけるカラーのベクトルメジアンカラーから構成される、方法。
【請求項３８】
請求項３３に記載の方法であって、インクドット数は、シアン（Ｃ）、マゼンタ（Ｍ）、イエロー（Ｙ）及びブラック（Ｋ）のうち０またはそれ以上の組み合わせから構成される、方法。
【請求項３９】
請求項３３に記載の方法であって、各々のグループのためのインクドットの最終分布を決定する段階は、グループのためのドット分布を、グループのための正確なドット数から構成される所定の順序の分布に変換する手順から構成される、方法。
【請求項４０】
請求項３９に記載の方法であって、所定の順序はＣＭＹＫＲＧＢＷから構成される、方法。
【請求項４１】
請求項３９に記載の方法であって、ドット分布におけるインクドットの輝度変化を減少する手順から更に構成される、方法。
【請求項４２】
請求項３３に記載の方法であって、前記各々のグループをカバーする配置マスクに基づいて各々のグループのためにインクドットを配置する段階はＫＢＣＧＲＭＹＷから構成される順序にインクドットを配置する手順から構成される、方法。
【請求項４３】
入力画像を複数のブロックに分割するための手段；
画像の画素のカラーに基づいて各々のグループにおける画像の画素を複数のグループにグループ化するための手段；
複数のグループの各々のために代表カラーを選択するための手段；
複数のグループの各々のための代表カラーを近似するためにカラー空間のインクドットの分布を決定するための手段；
各々のグループのために印刷カラーの最終分布を決定するための手段；並びに前記各々のグループをカバーする配置マスクに基づいて各々のグループのためにインクドットを配置する手段；
から構成される装置。
【請求項４４】
請求項４３に記載の装置であって、配置マスクに基づいて各々のグループのために画素を配置するための手段は、前記各々のグループをカバーする配置マスク数にしたがって輝度の順序に画素を配置するための手段から構成される、装置。
【請求項４５】
請求項４３に記載の装置であって、複数のグループの各々のための代表カラーは前記各々のグループにおけるカラーのカラー平均から構成される、装置。
【請求項４６】
請求項４３に記載の装置であって、複数のグループの各々のための代表カラーは前記各々のグループにおけるカラーのメジアンカラーから構成される、装置。
【請求項４７】
請求項４３に記載の装置であって、複数のグループの各々のための代表カラーは前記各々のグループにおけるカラーのベクトルメジアンカラーから構成される、装置。
【請求項４８】
請求項４３に記載の方法であって、インクドットの数は、シアン（Ｃ）、マゼンタ（Ｍ）、イエロー（Ｙ）及びブラック（Ｋ）のうち１つまたはそれ以上の組み合わせから構成される、方法。
【請求項４９】
請求項４３に記載の装置であって、各々のグループのためのインクドットの最終分布を決定する手段は、グループのためのドット分布を、グループについての正確なドット数から構成される所定の順序の分布に変換するための手段から構成される、装置。
【請求項５０】
請求項４９に記載の装置であって、所定の順序はＣＭＹＫＲＧＢＷから構成される、装置。
【請求項５１】
請求項４９に記載の装置であって、ドット分布におけるインクドットの輝度変化を減少させる手段から更に構成される、装置。
【請求項５２】
請求項４３に記載の装置であって、前記各々のグループをカバーする配置マスクに基づいて各々のグループのためにインクドットを配置するための手段はＫＢＣＧＲＭＹＷから構成される順序にインクドットを配置するための手段から構成される、装置。
【請求項５３】
記憶された実行可能な指令を有する１つまたはそれ以上の保存可能な媒体から構成される製造物品であって、システムにより実行されるとき、システムが：
入力画像を複数のブロックに分割し；
画像の画素のカラーに基づいて各々のブロックにおける画像の画素を複数のグループにグループ化し；
複数のグループの各々のための代表カラーを選択し；
複数のグループの各々のための代表カラーを近似するためにカラー空間のインクドットの分布を決定し；
各々のグループのために印刷カラーの最終分布を決定し；並びに
前記各々のグループをカバーする配置マスクに基づいて各々のグループのためにインクドットを配置する；
ようにする製造物品。
【請求項５４】
請求項５３に記載の製造物品であって、システムが配置マスクに基づいて各々のグループのために画素を配置するようにする指令は、システムにより実行されるとき、システムが前記各々のグループをカバーする配置マスク数にしたがって輝度の順序に画素を配置するようにする、製造物品。
【請求項５５】
請求項５３に記載の製造物品であって、システムが配置マスクに基づいて各々のグループのために画素を配置するようにする指令は、システムにより実行されるとき、システムがグループのためのドット分布をグループのための正確なドット数から構成される所定の順序の分布に変換するようにする、製造物品。
【請求項５６】
請求項５５に記載の製造物品であって、所定の順序はＣＭＹＫＲＧＢＷから構成される、製造物品。
【請求項５７】
請求項５５に記載の製造物品であって、システムにより実行されるとき、システムがドット分布におけるインクドットの輝度変化を減少させるようする指令から更に構成される、製造物品。
【請求項５８】
請求項５３に記載の製造物品であって、システムが前記各々のグループをカバーする配置マスクに基づいて各々のグループのためにインクドットを配置するようする指令は、システムが実行されるとき、システムがＫＢＣＧＲＭＹＷから構成される順序にインクドットを配置するようにする、製造物品。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、カラーハーフトーン化の分野に関し、特に、カラーハーフトーン化にブロック量子化技術の適用に関する。
【０００２】
【従来の技術】
カラーハーフトーン化は、市販の画像化装置についての重要な懸案事項となっている。カラーハーフトーン化は、４種類のインク（そして白）のような数種類のカラーのみと可能な限り増大させた空間分解能とを用いて、画像として多ビット（例えば２４ビット）カラー画像を表すものである。眼がカラーを平均化することにより視覚的に認識されたカラーをオリジナルのカラーと同様に見えるように、限定されたパレットからカラーを交互に配することによりこのカラーハーフトーン化を施すことが可能である。
【０００３】
カラーハーフトーン化アルゴリズムを判断することは、視覚の主観的性質により困難である。ハーフトーン化アルゴリズムの具体的な目標は、カラーマッチング、簡単な演算、小さい粒状性、アーチファクトの最小化及び後工程の影響の低減を含んでいる。これら目標の各々の相対的重要性は、見る人、予測される見える距離及びターゲット画像に依存する。
【０００４】
カラーマッチングには少なくとも２つの対象があり、それらは個々の入力カラー及び出力カラーの近さと辻褄の合うエラーである。計算に関する問題は、実行速度、並行処理性、メモリサイズ及び複雑さを含む。粒状性は、識別可能な出力カラーを認識するための能力と説明することができる。認識される粒状性は、ある程度はｄｐｉの関数である。
【０００５】
詳細な情報は、低い空間分解能または低いカラー解像度（又は、それら両者の組み合わせ）により、失われることがあり得る。アーチファクトは、アルゴリズムの結果である何らかの不所望の現象（ノイズではない）であって、スペックル、ストリーク、ゴースト、グリッディング、テクスチャ及び非常に重要なことには擬似輪郭（また、バンディングとして知られる）を指す一般的な用語である。
【０００６】
ハーフトーン化が施されるとき、ハーフトーン化された画像は必ずしも最終段階ではないので、後処理工程の効果は重要である。圧縮のためのダウンサンプリングからエッジエンハンスメントまで、種々の画像処理操作を施すことが可能である。ハーフトーン化アルゴリズムは、これらの操作の成功と容易さに影響を及ぼす。
【０００７】
ハーフトーン化のために考案されたえきた種々の技術として、ディザリング、エラー拡散及び反復法がある。文献Ｈｅｎｒｙ　Ｋａｎｇによる　”Ｄｉｇｉｔａｌ　Ｃｏｌｏｒ　Ｈａｌｆｔｏｎｉｎｇ”，　ＳＰＩＥ　ａｎｄ　ＩＥＥＥ　Ｐｒｅｓｓ，　１９９９（非特許文献１）、及びＲ．Ｕｌｉｃｈｎｅｙによる　“Ｄｉｇｉｔａｌ　Ｈａｌｆｔｏｎｉｎｇ”，　ＭＩＴ　Ｐｒｅｓｓ，　１９８７（非特許文献２）を参照されたい。殆どのカラーハーフトーン化技術は、３つのカラー平面の各々に対して白黒ハーフトーン化技術を単純に個別に適用拡大したものである。コンピュータを用いて効率化を図る、構成要素に関する拡大適用は、暗黙の内に、インクカラーの数学的線形性を仮定している。しかしながら、印刷における減法混色は非線形であって、それ故、そのような平面毎のハーフトーン化は次善にしかならない。
【０００８】
ディザリングは、偽似乱数の二次元の周期的信号を画像の各々のカラー成分に加え、次いで、最も近い出力カラーに各々の画素を量子化する処理を含むものである。ディザ信号は、眼に対して混合する交互に配置されたカラーのパターンを生成するためにデザインされている。種々の様式のディザリングがあり、その中には、クラスタードットディザリング（ｃｌｕｓｔｅｒｅｄ　ｄｏｔ　ｄｉｔｈｅｒｉｎｇ）、分散ドットディザリング（ｄｉｓｔｒｉｂｕｔｅｄ　ｄｏｔ　ｄｉｔｈｅｒｉｎｇ）及び配置ドットディザリング（ｏｒｄｅｒｅｄ　ｄｏｔ　ｄｉｔｈｅｒｉｎｇ）がある。ホワイトノイズを伴うディザリングは、整列性のよいディザリング程の視覚的に満足のいく結果を得ることはできない。ディザリングは、眼で見て分かる周期的なパターニングの影響を受けることは周知である。ディザリングを改善するために多くの努力がなされてきた。カラーへのディザリングの適用は技術的に要請されている。ディザリングに関する詳しい情報は、文献Ａ．Ｋａｒｕｎ等による　”Ｎｅｗ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｄｉｔｈｅｒｉｎｇ　ｏｆ　Ｃｏｌｏｒ　Ｉｍａｇｅｓ”，　Ｐｒｏｃ．　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｎｏｎｌｉｎｅａｒ　Ｓｉｇｎａｌ／Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，　１９９５（非特許文献３）を参照されたい。
【０００９】
ディザリングは点描プロセスであり（即ち、各々の画素における出力は入力画素とディザ信号のような可能な外部因子のみに依存する）、エラー拡散は、各々の順方向におけるエラーの一部を送る方向性空間フィルタに基づいて、隣接画素に各々の画素の量子化エラーを拡散する。その結果、エラー拡散によるハーフトーン化プロセスは大きな周波数ノイズを付加することとなる。目的は眼で見たときにカラーが混合されることであって、実際のモザイク状のカラーが認識されないことであるから、このエラー拡散のハイパスフィルタ効果は、高周波数ノイズに対する人間の眼の鈍感さを利用している。このようにして、エラー拡散はブルーの空間スペクトルを生成する。このブルーのノイズが視覚的により好まれるという考え方が定着している。
【００１０】
エラー拡散は、実際、うまく機能しており、中程度のインク密度及びそのままのシャープニングエッジ（ｓｈａｒｐｅｎｉｎｇ　ｅｄｇｅ）においてよい画像品質を提供する。文献Ｒ．Ｗ．Ｆｌｏｙｄ、Ｌ．Ｓｔｅｉｎｂｅｒｇによる　”Ａｎ　ａｄａｐｔｉｖｅ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｓｐｅｃｉａｌ　ｇｒａｙｓｃａｌｅ”　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｓｏｃｉｅｔｙ　ｆｏｒ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｄｉｓｐｌａｙ，　Ｖｏｌ．　１７，　Ｎｏ．２，　ｐｐ７５−７７，　１９７６（非特許文献４）を参照されたい。しかしながら、エラー拡散にはいくつかの問題点がある。それは局所的に最適化する欲張りなアルゴリズムであることである。即ち、それは、空間的に各々の画素において最適な役割を果たすようにする。エラーは前方に拡散するので、それは方向性があり、局所領域全体に亘って真の結合の最適化を提供することができない。眼で見てカラーが平均化されるポイントを遥かに超えて、エラーは拡散し得る。エラー拡散のアーチファクトには、スペックル、ストリーク、一時的且つエッジ効果、及び所定強度におけるグリッド効果がある。エラー拡散に必要なフィードバックループは、アルゴリズムを並行して実行することに対する障害となり得る。ブロックに基づくエラー拡散技術には、Ｆａｎによる研究がある。Ｆａｎの研究に関するさらに詳しい情報は、文献Ｈｅｎｒｙ　Ｋａｎｇによる　”Ｄｉｇｉｔａｌ　Ｃｏｌｏｒ　Ｈａｌｆｔｏｎｉｎｇ”　ＳＰＩＥ　ａｎｄ　ＩＥＥＥ　Ｐｒｅｓｓ，　１９９９（非特許文献５）及び最近のＤｅｍｅｒａ−Ｖｅｎｋａｔａによる研究、文献Ｎ．Ｄｅｍｅｒａ−Ｖｅｎｋａｔａ、Ｂ．Ｅｖａｎｓによる　”ＦＭ　Ｈａｌｆｔｏｎｅｉｎｇ　ｖｉａ　ｂｌｏｃｋ　ｅｒｒｏｒ　ｄｉｆｆｕｓｉｏｎ”　Ｐｒｏ．　ＩＥＥＥ　ＩＣＩＰ，　ｐｐ１０８１−１０８４，　２００１（非特許文献６）を参照されたい。
【００１１】
長年に亘って、エラー拡散における改善がなされてきた。構造的アーチファクトを最少化するような方向への努力がなされてきており、適応可能であるフィードバックフィルタが製造され、そしてニューラルネットワークが用いられている。
【００１２】
また、知覚モデル及びプリンタモデルを用いる奏効した白黒のハーフトーン化技術があるが、これらの技術はカラーハーフトーン化に対する複雑な拡大適用を必要とする。
【００１３】
平均マッチングの考え方を取り入れ、追加された白黒アルゴリズムがある。例えば、１つのマルチスケールハーフトーン化アルゴリズムを全体的な画像の解像度において始めて、出力画像の平均グレーレベルを入力画像の平均グレーレベルに等しく設定する。続いて、次に高い解像度レベルにおいて、平均グレーレベルを、４つの４分割された部分に、それらの平均グレーレベルに基づいて、分割する。このプロセスは、各々の画素が黒または白に量子化されるまでの解像度レベルにおいて継続される。例えば、文献Ｂｒｅａｕｘ等による　”Ｗａｖｅｌｅｔ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｃｏｍｐｒｅｓｓｉｏｎ，　Ｒｅｎｄｅｒｉｎｇ，　ａｎｄ　Ｄｅｓｃｒｅｅｎｉｎｇ　ｉｎ　Ｄｉｇｉｔａｌ　Ｈａｌｆｔｏｎｉｎｇ”　ＳＰＩＥ，　Ｖｏｌ．　３０７８，　１９９７（非特許文献７）、Ｎ．Ｂｒｅａｕｘ及びＣ．Ｈ．Ｃｈｕによる　”Ｗａｖｅｌｅｔ　Ｍｅｔｈｏｄｓ　Ｆｏｒ　Ｃｏｍｐｒｅｓｓｉｏｎ，　Ｒｅｎｄｅｒｉｎｇ，　ａｎｄ　Ｄｅｓｃｒｅｅｎｉｎｇ　Ｉｎ　Ｄｉｇｉｔａｌ　Ｈａｌｆｔｏｎｉｎｇ”　Ｐｒｏｃ．　ｏｆ　ｔｈｅ　ＳＰＩＥ，　Ｖｏｌ．　３０７８，　ｐｐ６５６−６６７，　１９９７（非特許文献８）（ウェーブレット平均を演算し、次いでこれらのグレーレベル平均を近似するためにディザリングを用いる）、Ｐ．Ｗ．Ｗｏｎｇによる　”Ｈａｌｆｔｏｎｉｎｇ　ｂｙ　Ｍｕｌｔｉｓｃａｌｅ　Ｄｏｔ　Ｄｉｓｔｒｉｂｕｔｉｏｎ”　Ｐｒｏｃ．　ｏｆ　ＩＥＥＥ　Ｉｎｔ．　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，　Ｖｏｌ．　ＩＩＩ，　１９９５（非特許文献９）、及びＰ．Ｗ．Ｗｏｎｇによる　”Ｍｅａｎ　ｍａｔｃｈｉｎｇ　Ｈａｌｆｔｏｎｉｎｇ　ｏｎ　Ｒｏｔａｔｅｄ　Ｑｕａｄ−ｔｒｅｅ　Ｓｔｒｕｃｔｕｒｅ”　Ｈｕｍａｎ　Ｖｉｓｉｏｎａｎｄ　Ｅｌｅｃｔｒｉｃ　Ｉｍａｇｉｎｇ，　Ｐｒｏｃ．　ｏｆ　ＳＰＩＥ　２６５７，　１９９６（非特許文献１０）（種々の解像度において入力画像と出力画像の平均グレーレベルをマッチングさせる）を参照されたい。また、Ｉ．Ｋａｔｓａｖｏｕｎｄｉｄｉｓ及びＣ．Ｃ．Ｋｕｏによる　”Ａ　Ｒｅｃｕｒｓｉｖｅ　Ｍｕｌｔｉｓｃａｌｅ　Ｅｒｒｏｒ−Ｄｉｆｆｕｓｉｏｎ　Ｔｅｃｈｎｉｑｕｅ　ｆｏｒ　Ｄｉｇｉｔａｌ　Ｈａｌｆｔｏｎｉｎｇ”　ＳＰＩＥ　Ｃｏｎｆｅｒｅｎｃｅ　Ｐｒｏｃｅｅｄｉｎｇｓ，　Ｖｏｌ．　２０９４，　１９９３（非特許文献１１）及びＩ．Ｋａｔｓａｖｏｕｎｄｉｄｉｓ及びＣ．Ｃ．Ｋｕｏによる　”Ａ　Ｍｕｌｔｉｓｃａｌｅ　Ｅｒｒｏｒ　Ｄｉｆｆｕｓｉｏｎ　Ｔｅｃｈｎｉｑｕｅ　ｆｏｒ　Ｄｉｇｉｔａｌ　Ｈａｌｆｔｏｎｉｎｇ”　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎ　ｏｎ　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，　Ｖｏｌ．　６，　Ｎｏ．　３，　　Ｍａｒｃｈ　１９９７（非特許文献１２）（Ｋａｔｓａｖｏｕｎｄｉｄｉｓ及びＫｕｏは異なる解像度において強度をマッチングさせることを目的とし、‘マルチスケールエラー拡散技術を用いている）を参照されたい。
【００１４】
【非特許文献１】
Ｈｅｎｒｙ　Ｋａｎｇ，　”Ｄｉｇｉｔａｌ　Ｃｏｌｏｒ　Ｈａｌｆｔｏｎｉｎｇ”，　ＳＰＩＥ　ａｎｄ　ＩＥＥＥ　Ｐｒｅｓｓ，　１９９９
【非特許文献２】
Ｒ．Ｕｌｉｃｈｎｅｙ，　“Ｄｉｇｉｔａｌ　Ｈａｌｆｔｏｎｉｎｇ”，　ＭＩＴ　Ｐｒｅｓｓ，　１９８７
【非特許文献３】
Ａ．Ｋａｒｕｎ，ｅｔ．ａｌ．，　”Ｎｅｗ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｄｉｔｈｅｒｉｎｇ　ｏｆ　Ｃｏｌｏｒ　Ｉｍａｇｅｓ”，　Ｐｒｏｃ．　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｎｏｎｌｉｎｅａｒ　Ｓｉｇｎａｌ／Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，　１９９５
【非特許文献４】
Ｒ．Ｗ．Ｆｌｏｙｄ、Ｌ．Ｓｔｅｉｎｂｅｒｇ，　”Ａｎ　ａｄａｐｔｉｖｅ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｓｐｅｃｉａｌ　ｇｒａｙｓｃａｌｅ”　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｓｏｃｉｅｔｙ　ｆｏｒ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｄｉｓｐｌａｙ，　Ｖｏｌ．　１７，　Ｎｏ．２，　ｐｐ７５−７７，　１９７６
【非特許文献５】
Ｈｅｎｒｙ　Ｋａｎｇ，　”Ｄｉｇｉｔａｌ　Ｃｏｌｏｒ　Ｈａｌｆｔｏｎｉｎｇ”　ＳＰＩＥ　ａｎｄ　ＩＥＥＥ　Ｐｒｅｓｓ，　１９９９
【非特許文献６】
Ｎ．Ｄｅｍｅｒａ−Ｖｅｎｋａｔａ、Ｂ．Ｅｖａｎｓ，　”ＦＭ　Ｈａｌｆｔｏｎｉｎｇ　ｖｉａｂｌｏｃｋ　ｅｒｒｏｒ　ｄｉｆｆｕｓｉｏｎ”　Ｐｒｏ．　ＩＥＥＥ　ＩＣＩＰ，　ｐｐ１０８１−１０８４，　２００１）
【非特許文献７】
Ｂｒｅａｕｘ，ｅｔ．ａｌ．，　”Ｗａｖｅｌｅｔ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｃｏｍｐｒｅｓｓｉｏｎ，　Ｒｅｎｄｅｒｉｎｇ，　ａｎｄ　Ｄｅｓｃｒｅｅｎｉｎｇ　ｉｎ　Ｄｉｇｉｔａｌ　Ｈａｌｆｔｏｎｉｎｇ”　ＳＰＩＥ，　Ｖｏｌ．　３０７８，　１９９７
【非特許文献８】
Ｎ．Ｂｒｅａｕｘ，Ｃ．Ｈ．Ｃｈｕ，　”Ｗａｖｅｌｅｔ　Ｍｅｔｈｏｄｓ　Ｆｏｒ　Ｃｏｍｐｒｅｓｓｉｏｎ，　Ｒｅｎｄｅｒｉｎｇ，　ａｎｄ　Ｄｅｓｃｒｅｅｎｉｎｇ　Ｉｎ　Ｄｉｇｉｔａｌ　Ｈａｌｆｔｏｎｉｎｇ”　Ｐｒｏｃ．　ｏｆ　ｔｈｅ　ＳＰＩＥ，　Ｖｏｌ．　３０７８，　ｐｐ６５６−６６７，　１９９７
【非特許文献９】
Ｐ．Ｗ．Ｗｏｎｇ，　”Ｈａｌｆｔｏｎｉｎｇ　ｂｙ　Ｍｕｌｔｉｓｃａｌｅ　Ｄｏｔ　Ｄｉｓｔｒｉｂｕｔｉｏｎ”　Ｐｒｏｃ．ｏｆ　ＩＥＥＥ　Ｉｎｔ．　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ，　Ｖｏｌ．　ＩＩＩ，　１９９５
【非特許文献１０】
Ｐ．Ｗ．Ｗｏｎｇ，　”Ｍｅａｎ　ｍａｔｃｈｉｎｇ　Ｈａｌｆｔｏｎｉｎｇ　ｏｎ　Ｒｏｔａｔｅｄ　Ｑｕａｄ−ｔｒｅｅ　Ｓｔｒｕｃｔｕｒｅ”　Ｈｕｍａｎ　Ｖｉｓｉｏｎ　ａｎｄ　Ｅｌｅｃｔｒｉｃ　Ｉｍａｇｉｎｇ，　Ｐｒｏｃ．　ｏｆ　ＳＰＩＥ　２６５７，　１９９６
【非特許文献１１】
Ｉ．Ｋａｔｓａｖｏｕｎｄｉｄｉｓ，Ｃ．Ｃ．Ｋｕｏ，　”Ａ　Ｒｅｃｕｒｓｉｖｅ　Ｍｕｌｔｉｓｃａｌｅ　Ｅｒｒｏｒ−Ｄｉｆｆｕｓｉｏｎ　Ｔｅｃｈｎｉｑｕｅ　ｆｏｒ　Ｄｉｇｉｔａｌ　Ｈａｌｆｔｏｎｉｎｇ”　ＳＰＩＥ　Ｃｏｎｆｅｒｅｎｃｅ
Ｐｒｏｃｅｅｄｉｎｇｓ，　Ｖｏｌ．　２０９４，　１９９３
【非特許文献１２】
Ｉ．Ｋａｔｓａｖｏｕｎｄｉｄｉｓ，Ｃ．Ｃ．Ｋｕｏ，　”Ａ　Ｍｕｌｔｉｓｃａｌｅ　Ｅｒｒｏｒ　Ｄｉｆｆｕｓｉｏｎ　Ｔｅｃｈｎｉｑｕｅ　ｆｏｒ　Ｄｉｇｉｔａｌ　Ｈａｌｆｔｏｎｉｎｇ”　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎ　ｏｎ　ＩｍａｇｅＰｒｏｃｅｓｓｉｎｇ，　Ｖｏｌ．　６，　Ｎｏ．　３，　　Ｍａｒｃｈ　１９９７
【００１５】
【発明が解決しようとする課題】
他の先行技術の解決方法においては、入力画像及び出力画像の平均グレーレベルを種々の解像度において生成している。更に他の先行技術の解決方法においては、ウェーブレット平均が演算され、次いで、これらのグレーレベル平均を近似するためにディザリングが用いられる。更に具体的には、画像は、先ず、ウェーブレットを用いて圧縮され、次いで、ホワイトドットがどのように四分割部分に分割されるかを決定するために、平均グレーレベルとして、ウェーブレット係数が各々のレベルにおいて用いられる。この技術は、画素レベルまでいっておらず、クラスター化されたドットまたは分散されたドットのディザを用いて、選択された数のホワイトドットをモザイク状にする。それらの結果は水平及び垂直アーチファクト、並びに擬似輪郭の影響を受ける。
【００１６】
【課題を解決するための手段】
本発明は、ブロック量子化を用いてカラーハーフトーン化を実施するための方法及び装置について開示している。本発明の１つの実施形態にしたがった方法は、入力信号を複数のブロックに分割する段階、各々の複数のブロックにおいて複数のカラーグループに画素をクラスター化する段階、複数のブロックの各々についての複数のカラーグループの各々を代表カラー値にブロックを量子化する段階、及び複数のブロックにおける各々のブロックに関して異なるブロックを有する出力のハーフトーン画像を生成する段階から構成され、前記各々の異なるブロックによりカバーされた空間領域に亘って近似される各々の異なるブロックにおける各々のグループは代表カラー値をもっている。
【００１７】
【発明の実施の形態】
本発明は、入力画像の小ブロックにおけるカラー平均を出力画像における対応する小ブロックのカラー平均とマッチングさせるハーフトーン化技術を提供する。より具体的には、ここで説明するＢＣＱハーフトーン技術においては、オリジナル画像がどのように認識されているかに関して最小限の歪を伴って認識されるハーフトーンを生成することを目的として、画像をブロックに分割し、代表入力カラーを各々の小ブロックの各々のグループの代表出力カラーにマッチングさせるものである。このＢＣＱを用いる方法においては、エッジにおいてではなく、入力ドメイン及びハーフトーンにおいてアイローパスフィルタを仮定している。それ故、この技術は、一貫したカラーパッチ間の歪を最小になるようにするものである。各々のブロック内において、エッジの情報を保つために、カラーをクラスター化する。本発明の一実施形態において、この技術は、クラスター化によりブロックをカラーグループに分割し、且つ代表カラーを得るためにＣ、Ｍ、Ｙ、Ｋ、Ｗ、Ｒ、Ｇ、Ｂの分配を割り当てる。本発明の一実施形態におけるハーフトーン化の方法は、ディザマスク、即ち分散ドットマスク又はクラスタードットマスクを用いて選択されたインクドットを配置し、それ故、孤立化したドットを用いる印刷の問題、及び先行技術において妨げとなっていた他の物理的な装置上の問題を回避することが可能である。
【００１８】
ブロックカラー量子化によるハーフトーン化技術の考え方は、入力画像及び出力ハーフトーンにおける非常に微小なスムーズなカラー領域の平均カラー値をマッチングさせることにより、速くて高品質のハーフトーンを得ることを可能にするものである。人間の視覚システムは、カラー値に近いカラーを平均化するが、カラー値から遠く離れたカラーをエッジとして認識する。本発明の一実施形態においては、アルゴリズムを並行に実行し、画像の各々の小ブロックを独立して処理する。本発明の一実施形態においては、各々の微小ブロックについて、カラーを最大３つの異なるカラーグループにクラスター化する。次いで、これらカラーグループの各々を、平均値等の、任意の代表値に“ブロック量子化”する。次いで、生成したハーフトーンは、各々のブロックにおけるグループによりカバーされる空間領域において各々のカラーグループのカラーを再生成する。
【００１９】
以下の記述において、本発明の詳細について説明する。それらの具体的な詳細説明がないとしても、本発明が実施可能であることが明白であることは、当業者には容易に理解されるであろう。実施形態に関しては、周知の構造及び装置をブロック図の形式で示し、本発明を不明瞭にすることを回避することとした。
【００２０】
以下の詳細な説明の一部においては、コンピュータのメモリ内のデータビットに関する操作のアルゴリズムと符号表現について説明している。これらのアルゴリズムの説明及び符号表現は、データ処理の技術分野の熟達者が用いる手段であり、彼らの分野の内容を他の分野の者に最も効果的に伝えることが可能である。ここでのアルゴリズムは、一般に、所望の結果に導く首尾一貫した一連の段階として考案したものである。それらの段階は、物理量の物理的操作を必要とするものである。通常、これらの物理量は、記憶、移動、結合、比較及び他の操作を行うことが可能である電気的又は磁気的信号の形態をとるが、必ずしもそうであるとは限らない。主に共通に使用することを目的とし、これらの信号を、ビット、値、要素、符号、特性、用語、数字等と表現することは好都合であると認識されている。
【００２１】
しかしながら、これらすべて及び類似の用語は適切な物理量に結びつけるものであり、これらの量に適用される、単なる好都合なラベルとして用いられることを心に留めておくべきである。以下の説明から明らかなように、他に具体的に述べられていない限り、以下の説明を通して、“処理する”、“演算する”、“計算する”、“決定する”、“表示する”等は、コンピュータシステムのレジスタ及びメモリ内の物理（電子的）量として表されるデータを、コンピュータシステムのメモリ、レジスタ又は他の情報ストレージ、伝送装置または表示装置内の物理量として同様に表される他のデータに処理し且つ変換する、ところのコンピュータシステムまたは類似する電子演算装置の働き及びプロセスを表す。
【００２２】
本発明はまた、ここで操作を実行するための装置に関する。目的を達成するためにこの装置を特別に構成する、即ち、この装置は多目的コンピュータから構成され、このコンピュータに記憶されたコンピュータプログラムにより選択的に動作され、再構成される。フロッピー（登録商標）ディスク、光学ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＡＭ、ＥＥＰＲＡＭ、磁気又は光カード、または電子的指令を記憶するために適切な何れかのタイプの媒体、及びコンピュータシステムに連結した各々のバス等のコンピュータ読み取り可能記憶媒体に、そのようなコンピュータプログラムを記憶することが可能であるが、これらに限定されるものではない。
【００２３】
ここで示すアルゴリズム及び表示装置は、何れかの特定のコンピュータ又は他の装置に固有に関連するものではない。本発明の教示にしたがって、プログラムを備えた種々の多目的システムを用いることが可能であり、または、この方法に必要な段階を実行するために更に専用化した装置を備えることが好適である。以下の説明において、種々のこれらのシステムのために必要な構造について示す。更に、本発明は、何れかの特定なプログラム言語に関して述べるものではない。ここで記述する本発明の教示するところを実行するために、種々のプログラム言語を用いることが可能であることは、評価されるであろう。
【００２４】
機械により読み取り可能な媒体は、機械（例えば、コンピュータ）により読み取り可能な形式で情報を記憶するか、または送るために何れかのメカニズムを含む。例えば、機械により読み取り可能な媒体は、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリ装置、電子信号、光信号、音響信号又は他の伝搬信号（例えば、搬送波、赤外線信号、デジタル信号等）等である。
【００２５】
概観
図１は、ブロックカラー量子化ハーフトーン化を実施するためのプロセスの一実施形態を示すフローチャートである。ハードウェア（例えば、回路、専用ロジック等）、ソフトウェア（多目的コンピュータシステム又は専用機械において実行されるような）またはその両者の組み合わせから構成される処理ロジックにより、このプロセスを実施する。
【００２６】
図１を参照するに、処理ロジックは画像を小ブロックに分割する（処理ブロック１０１）。画像を小ブロックに分割した後、処理ロジックは、画素のカラーに基づいて、最大の所定グループ数（例えば、３、４）以下の１つまたはそれ以上のグループに、各々のブロックにおける画像画素をグループ化する（処理ブロック１０２）。画像の画素をグループ化した後、処理ロジックは各々のグループのために、カラー空間から代表カラー値を選択する（処理ブロック１０３）。カラー空間において得られる可能な値を調べることにより、この処理を行うことが可能である。本発明の一実施形態においては、処理ロジックは、各々のグループについて、ＣＭＹＫ値（例えば、Ｃ、Ｍ、Ｙ及び／又はＫのカラーの組み合わせを表すδビット値）を選択する。各々のグループのための代表カラー値を選択した後、処理ロジックは、各々のグループのために、ブロックのグループについてのターゲットカラーに最も近いカラーを得るために必要な出力カラーのセットのインクドット数を演算する（処理ブロック１０４）。次いで、各々のグループについて、処理ロジックは印刷カラーの最終的な分布を構成し、且つ各々のグループ（例えば、Ｃ、Ｍ、Ｙ、Ｒ、Ｇ、Ｂ、Ｋ及びＷドット）のためにインクドットを配置し（処理ブロック１０５）、そして各々のグループのために、グループをカバーする配置マスク数にしたがって、プリセットの順序（例えば、輝度によりソーティングする）に画素を配置する（処理ブロック１０６）。
【００２７】
図２は、カラーハーフトーン化のためのブロック量子化システムの一実施形態についてのブロック図である。このブロック量子化システムは、入力ドメインにおけるカラーの数が出力ドメインにおける利用可能なカラーの数より多いカラーハーフトーン化を達成するために、システムの入力ドメインとシステムの出力ドメインの間のカラーマッチングを実施する。このシステムは、入力ドメイン及び出力ドメインにおける画像を複数のブロックに分割することによるカラーマッチング、そして入力ドメインの画像における各々のブロックのカラー平均と出力ドメインの画像におけるブロックについてのカラー平均とのマッチングを、実行する。それらブロックは、２つ又はそれ以上の形状の組み合わせによる複雑な形状を含む、如何なる形状をとることが可能である。例えば、ブロックは、正方形（ｄｘｄ）とすることが可能であり、矩形（ｄｘｂ）とすることが可能であり、ここで、ｄとｂは等しくない。
【００２８】
本発明の一実施形態において、入力ドメインは、モニタ及びプリンタを備えた出力ドメインを有するコンピュータシステムから構成される。入力画像の各々の小ブロックのために、ここで説明するブロック量子化技術は、入力ブロックのカラー平均を最もよく表現する（一実施形態における理に適った間隔測定の基で）、それに対応する出力ブロックについての印刷カラーのセットを計算する。本発明の一実施形態において、ここで述べる技術は、カラー空間における３次元（３Ｄ）ベクトルとして各々の入力カラーを処理し、減法印刷プロセスで得られた実際の出力カラーを用いてハーフトーンを生成する。この方法において、ここで説明するハーフトーン化技術は、各々の局所の入力領域に対して、その平均カラーは対応する局所の出力領域の平均カラーに適合し、それらの領域は人間の眼がそれらの領域において平均化することを確実にするように十分小さくなっている。ブロック量子化技術は、より良好なカラー解像度を達成するために印刷プロセスのより高い空間分解能を利用し、条件付で局所カラー最適化の達成することを試みる。一般的にエラー拡散に伴うスペックル、テクスチャ及び他のアーチファクトの共通部分は実質的に回避される。
【００２９】
図２を参照するに、入力画像２０１は、入力画像２０１をブロックに分割するブロック生成ユニット２０２により受け取られる。
【００３０】
グループ化ユニット２０２は各々のブロックにおける画像画素を所定数のグループにグループ化する。それらグループは画素カラーに基づいている。または、グループは画素の空間的位置に基づくことも可能である。本発明の一実施形態においては、所定のグループ数は４であり、それ故、グループ化ユニット２０２は各々のブロックにおける画像の画素を４つのグループにグループ化する。または、グループ化ユニット２０２は、画像の画素を３つの異なるカラーグループにグループ化することが可能である。
【００３１】
カラー選択ユニット２０３は各々のグループのために代表カラーを選択する。例えば、カラー選択ユニット２０３は、グループを代表するカラー値を選択することが可能である。カラー値は、Ｃ、Ｍ、Ｙ及び／またはＫのカラー（例えば、（Ｃ，Ｍ，Ｙ，Ｋ）の値が（３０，０，１５，５０）に等しいとき、Ｃ、Ｍ、Ｙ及び／またはＫの値の平均）の平均を代表する８ビットＣＭＹＫ値とすることが可能である。
【００３２】
目標として入力ブロックカラー平均が与えられる場合、カラーマッチング及びレイアウトユニット２０４は、各々のグループについて必要とされる出力カラー空間のドット数を計算し、それにより、出力カラーのセットは目標値にできるだけ近づくように平均化される。本発明の一実施形態において、カラーマッチング及びレイアウトユニット２０４は、出力画像のカラー空間において達成可能である値を調べること且つ達成可能な目標値に最も近い値を確認することにより、出力カラーのセットを計算する。例えば、カラーマッチング及びレイアウトユニット２０４は、各々のグループに対してＣ、Ｍ、Ｙ及びＫのドットがどれ位必要であるかを計算する。その後、カラーマッチング及びレイアウトユニット２０４は、各々のグループのために出力カラーセットのドットの分布を構築する。例えば、カラーマッチング及びレイアウトユニット２０４は、各々のグループのために、Ｃ、Ｍ、Ｙ、Ｒ、Ｇ、Ｂ、Ｋ及びＷのドット分布を構築する。ここで留意すべきは、何れかの印刷可能なカラーのセットにおける他の分布を用いることが可能であることである。
【００３３】
出力カラーのセットが与えられると、カラーマッチング及びレイアウトユニット２０４は、所望のカラーを得るため、及びアーチファクトと粒状性を減少させて最小化をも可能にするために、それら構築されたカラーを配置する。本発明の一実施形態においては、各々のグループのために、カラーマッチング及びレイアウトユニット２０４は、グループをカバーする配置マスク数にしたがった輝度の順序に画素を配置する。このことについては以下で詳述する。
【００３４】
画像の小ブロックへの分割
ハーフトーン化が効果的であることの１つの理由は、人間の眼が互いに空間的に近いカラーを平均化することである。空間的なカラーの平均化はまた、入力画像において生じ、それ故、ここで述べた本発明の教示するところにより、入力画像と出力画像の間で局所的なカラー平均を適合させる。
【００３５】
ここで述べたブロックに基づく処理は、ブロックカラー量子化は並行して実行することが可能であるため、有利である。
【００３６】
本発明の一実施形態においては、画像は１６ｘ１６ブロックに分割される。または、１２ｘ１２ブロックを用いることが可能であり、または他のブロックサイズも可能である。ブロック数が多くなればなる程、ハーフトーンにおけるカラー分解能はより可能になる。例えば、２ｘ２ブロックを用いる場合、各々のカラーは４つのドットのみにより代表され、例えば、シアンの可能な濃淡は５つのみであり、これにより擬似輪郭がもたらされる。ＣＲＴのスクリーンは、１インチ当たり７５ドットにおいて、何れのカラーディメンジョン（Ｒ，Ｇ，Ｂ）を最大２５６レベルまで用いる。したがって、適切なｄｐｉの解像度において、１６ｘ１６のブロック（何れの印刷可能カラーディメンジョンの２５６レベルに等しい）は、モニタスクリーンと同じカラーの深みを十分に再現する。しかしながら、本発明の他の実施形態において、擬似輪郭を伴うことなく、画像を生成するために、１２ｘ１２のブロック（＝１４４レベル）を用いることが可能である。
【００３７】
ハーフトーンのカラー分解能はブロックが大きい程向上するが、人間の眼がブロックにおいてカラーを実際に平均化するのに十分小さいブロックを形成するという仮定について計算して裏付けるためには、ブロックは小さい程好ましい。最も重要なことには、所定のｄｐｉにおけるブロックのサイズが小さくなればなる程、人間の眼はブロックに気がつかなくなっていく。ブロック内に強調されたエッジがある場合、人間の眼はエッジに対して敏感になり、かなりの空間の拡がりにおいてエッジを調和させることができない。ブロック内のエッジの情報を捕捉するために、以下に述べるように、各々のブロックをカラーグループに分割することが可能である。
【００３８】
各々のブロックにおける画素のグループ化
ブロックにおいてエッジが存在する場合、またはブロックにおいて強い変化が存在する場合、各々のブロックの画素を、カラー値に基づいて４つのグループにグループ化する。ここでは、これらをカラーグループと呼ぶことにする。ブロックサイズが小さく保たれる場合、代表的には３つのグループがすべてにおいて必要とされ、または、多くても４つのグループが必要とされる。１２ｘ１２ブロックについては、代表的には、３つのグループがすべてのエッジを捕捉するが、１６ｘ１６ブロックを用いる場合は、ブロックを最大４つのグループまで分割する必要がある。本発明の一実施形態においては、グループ数を分析的に決定する。この分析的決定は、所定の入力ｄｐｉに対する人間の眼の周波数特性に基づくことが可能である。
【００３９】
本発明の一実施形態において、画素はそのカラー値に基づいてグループ化されるのであって、それらの空間的位置に基づいてグループ化されるのではない。そのような方法においては、ブロック内のエッジのあらゆる変化を捕捉することが可能である。本発明の一実施形態においては、画素を、ＲＧＢカラー値ではなくＹＣｂＣｒカラー値に基づいてグループ化するが、これは必須ではない。関連する技術分野で周知であるように、ＹＣｂＣｒは反対カラー空間であり、それ故、Ｙは輝度チャンネルを、ＣｂとＣｒはクロミナンスチャンネルを表す。
【００４０】
次の式にしたがって、カラー空間を変換することが可能である。
【００４１】
Ｙ＝０．２９９Ｒ＋０．５８７Ｇ＋０．１１４Ｂ
Ｃｂ＝−０．１６９Ｒ−０．３３１Ｇ＋０．５Ｂ
Ｃｒ＝０．５Ｒ−０．４１８Ｇ−０．０８１Ｂ
他のカラー空間として、ＹＵＶ、ＣＩＥＬａｂ及びＣＩＥＬｕｖを用いることが可能である。
【００４２】
図３は、画素のグループ化についての３つの例を示している。図３を参照するに、４ｘ４画像ブロックを、各々色に基づいて、且つ位置に基づかずに４ｘ４画像ブロックを４つのグループに分割する。
【００４３】
図４は、画像ブロック内に画素を取り込み、クラスターを配置するために用いるプロセスについての本発明の一実施形態のフローチャートである。このプロセスは即座に機能し、重要なグループがそのときのマジョリティであることを確認する。この実施形態は３つのカラーグループを用いるが、他のカラーグループ数を用いることも可能である。以下の記述において、各々のグループの平均はＧ１、Ｇ２及びＧ３と表す。このプロセスは、ブロックにおける画素数に等しいサイズを有するベクトルｇｒｐを作り出し、このブロックへの登録は、ブロックにおいて各々の画素が属するグループを特徴付ける。
【００４４】
図４を参照するに、処理ロジックは、異なるカラーとしてカウントされる２つのカラー値がどれくらい離れているべきかを指定する、間隔の閾値ｔｈｒとｔｈｒ２を設定する（処理ブロック４０１）。１０個のＹＣｂＣｒユニットの閾値は経験的に十分機能するが、カラー空間の領域に依存する閾値は更に良好に機能する筈である（閾値数はグループ数に関連している）。
閾値間隔が指定された後、処理ロジックはブロックにおける画素をＹＣｂＣｒ（または、他の前もって選択されたカラー空間）に変換する（処理ブロック４０２）。ブロックにおける画素を異なるカラー空間に変換した後、処理ロジックはＧ１をブロックにおける第１画素に等しく設定する（処理ブロック４０３）。処理ロジックは、ブロックにおけるすべての画素が処理されたかどうかを調べ（処理ブロック４０４）、それにより、ブロックの終端に到達したことを確認する。このように処理された場合、処理は終了する。しかしながら、このように処理されなかった場合、処理ロジックは、ブロックにおけるすべての画素を通して反復する。
【００４５】
各々の画素ｕに対して、処理ロジックは、画素ｕのカラーとカラーグループＧ１のカラー値の間の差が閾値ｔｈｒより小さいかどうかを決定する（間隔（ｕ，Ｇ１）＜ｔｈｒ）（処理ブロック４０５）。上述のように、１０個のＹＣｂＣｒユニットの閾値を用いることが可能である。間隔が（ｕ，Ｇ１）＜ｔｈｒの場合、処理ロジックはグループ１に属するとして画素ｕにマーキングする（ｇｒｐ［ｕ］＝１）（処理ブロック４０６）。間隔が（ｕ，Ｇ１）＜ｔｈｒでない場合、処理ロジックは、グループ１のマークが付けられなかったすべての画素のうちどの画素が原点（０，０，０）から最大及び最小の間隔にあるか追跡し続ける（処理ブロック４０７）。これらの２つの値はｍａｘＰｉｘ及びｍｉｎＰｉｘとして表される。処理ロジックは、ｍａｘＰｉｘ及びｍｉｎＰｉｘ間の間隔が閾値ｔｈｒ２より大きいかどうかを決定する（距離（ｍａｘＰｉｘ，ｍｉｎＰｉｘ）＞ｔｈｒ２）（処理ブロック４０８）。そのような場合、処理ロジックは、Ｇ２をｍａｘＰｉｘに等しく、Ｇ３をｍｉｎＰｉｘに等しいと設定し（処理ブロック４０９）、グループ１のマークが付けられなかったすべての画素を通して反復し、画素がＧ２またはＧ３に近いかに依存してグループ２またはグループ３として各々の画素にマーキングする（処理ブロック４１０）。
【００４６】
処理ロジックが、ｍａｘＰｉｘ及びｍｉｎＰｉｘ間の距離が閾値ｔｈｒ２より大きくないことを決定する場合（距離（ｍａｘＰｉｘ，ｍｉｎＰｉｘ）＜＝ｔｈｒ２）であって、すでにそれらがカラーグループＧ１のマークを付けられなかった場合に、処理ロジックはすべての画素をカラーグループＧ２としてマーキングする（処理ブロック４１１）。本発明の一実施形態において、閾値ｔｈｒ２は１０個のＹＣｂＣｒユニットから構成される。
【００４７】
図４のプロセスの最終的な結果は、ブロックにおけるすべての画素がＧ１、Ｇ２またはＧ３のマークが付けられ、対応するグループに属することである。
【００４８】
グループ化のプロセスにおける処理ブロック４０５及び４０８において、各々の画素ｕそしてＧ１、Ｇ２及びＧ３の間の距離はｌ∞距離により測定されるが、ｌ２（ユークリッド）距離及び他の距離の測定もまた用いることが可能である。ｌ∞距離は、すべての次元における２つのポイント間の最大距離として２つの多次元のポイントの間の距離を測定する。
【００４９】
閾値ｔｈｒ及びｔｈｒ２が大きい場合、画像ブロックは分離したグループに分かれない傾向が強い。閾値ｔｈｒ及びｔｈｒ２が小さい場合、画像ブロックは、ブロック内のカラー変化に敏感であり、２つまたは３つのグループにた易く分割される。上述のように、ｔｈｒ及びｔｈｒ２についての１０個の値はＹＣｂＣｒ空間において十分に機能する（距離はｌ∞距離において測定されると仮定される）。
【００５０】
それに代えて、他の多くのアルゴリズムを用いることが可能であり、例えば、ｋ手段、期待値最大化及び階層クラスター化技術があり、これらは画像ブロックにおける画素を取り、カラーに基づいて画素をクラスターにグループ化する。
【００５１】
画像のアップサンプリングとダウンサンプリング
入力及び出力ｄｐｉが同じ場合、グループを代表する入力画素は、グループがマッピングする出力ドットとなる。しかしながら、出力ｄｐｉが異なる場合、各々のグループはより低い／高いｄｐｉに対して再マッピングされる。
【００５２】
各々のグループについての代表カラーの選択
各々のブロックグループにおいて画素をグループ化した後、各々のグループについての代表カラーを選択する。例えば、３つのブロックに対して、そのグループの代表カラーは（Ｃ１，Ｍ１，Ｙ１，Ｋ１）、（Ｃ２，Ｍ２，Ｙ２，Ｋ２）及びＣ３，Ｍ３，Ｙ３，Ｋ３）と表すことが可能である。
【００５３】
本発明の一実施形態において、処理ロジックはグループをそのカラー平均により表す。画素がグループに加えられるにとき、それらの値を移動平均に加えることが可能であり、且つ実際の画素を保存する必要はない。他の実施形態においては、グループのメジアンまたはベクトルメジアンカラーを代表カラーとして用いることが可能である。
グループの平均カラーを取る１つの不都合は、最初の１つは画素すべてを通して読み取り、且つそれらをグループ化しなければならないことであり、次いで、各々のグループについて平均を求めるために再び全体を通して読み出さなければならないことである。グループの代表カラーとしてＧ１、Ｇ２及びＧ３を用いることにより、これを回避することが可能であるが、結果として得られる画像派過度にくっきりと現れる傾向にある。多くのカラーが存在する込み合った領域であって、そのような有色のテキストを伴う有色のマップにおいては、カラー平均を用いないことにより、支配的なカラーを目立たなくすることが可能である。
【００５４】
出力カラー（例えば、Ｃ、Ｍ、Ｙ、Ｋ）のドット計算
本発明の一実施形態において、出力カラーのドットの演算に先立ち、各々の入力ブロックは最大３つ（または４つ）のグループに関連付けられる。処理ロジックは、空間的に、グループを出力ブロックに再マッピングする。入力ブロックと出力ブロックが同じサイズである場合、これはどうでもよいことである。他の実施形態において、入力ブロックと出力ブロックが同じサイズでない場合、ブロックについて入力画素と出力画素との間のマッピングを行うために、空間マッピングを用いることが可能である。したがって、各々の出力ブロックは、例えば（Ｃ１，Ｍ１，Ｙ１，Ｋ１）、（Ｃ２，Ｍ２，Ｙ２，Ｋ２）及びＣ３，Ｍ３，Ｙ３，Ｋ３）のカラーにより表され、且つ出力ブロックにおいて、それぞれｄ１、ｄ２及びｄ３をカバーする最大３つのグループを有する。
【００５５】
次に、本発明の一実施形態において、グループ１は次の式のようなＣ、Ｍ、Ｙ及びＫのドット総数を得る。
【００５６】
Ｃ１ｄｏｔｓ＝ｄ１＊Ｃ１／２５５
Ｍ１ｄｏｔｓ＝ｄ１＊Ｍ１／２５５
Ｙ１ｄｏｔｓ＝ｄ１＊Ｙ１／２５５
Ｋ１ｄｏｔｓ＝ｄ１＊Ｋ１／２５５
同様のやり方で、他のグループの各々についてのドット総数を演算する。前述の数字２５５は８ビットカラー値についての数字であることに留意されたい。多いまたは少ないカラー値を有する他の実施形態においては、数字２５５をそれらの最大のカラー値で置き換える。
【００５７】
しかしながら、Ｃ１ｄｏｔｓ＋Ｍ１ｄｏｔｓ＋Ｙ１ｄｏｔｓ＋Ｋ１ｄｏｔｓ　のようなグループに寄与するカラードットの総数は、グループが有する空間ドット数、ｄ１の最大４倍とすることが可能である。例えば、Ｃ１＝Ｍ１＝Ｙ１＝Ｋ１＝２５５である場合、Ｃ１ｄｏｔｓ＝Ｍ１ｄｏｔｓ＝Ｙ１ｄｏｔｓ＝Ｋ１ｄｏｔｓ＝ｄ１であって、その総数は４ｄ１である。他方、グループのカラー値がすべて０である場合、グループにはドットが全く割り当てられない。最終的なドット分布を演算することにおいて、この問題はＣ、Ｍ及びＹのドットをＲ、Ｇ、Ｂ、Ｋ及びＷのドットに変換することにより解決し、それ故、その総数は、グループがカバーするドット数に全く等しくなる。
【００５８】
最終的ドット分布の演算
ドット数を演算した後、最終的なドット分布を演算する。本発明の一実施形態において、この変換により、グループについてのＣＭＹＫドットを、グループについての正確なドット数に一致するＣＭＹＫＲＧＢＷにおける分布に変換する。
【００５９】
人間の眼はクロミナンスに比べて輝度において高周波数により敏感であるため、小さい輝度変化のカラーパッチは、大きい輝度変化のパッチに比べて画像粒状性がより小さく現れる。粒状性は、局所的カラー変化の測定として表現され、例えば、ＩＳＯ標準規格ＩＳＯ／ＩＥＣ　１３６６０−２００１を参照されたい。
【００６０】
このため、本発明は、ハーフトーンドットの輝度変化を減少させ、最小化に至らしめることを試みる。図５は、そのようなプロセスについて示している。そのプロセスは、ＣＭＹＫドット分布をＣＭＹＫＲＧＢＷ分布に変換する他の方法に比べて、非常に速く、且つよりスムーズな結果を与えるものである。
【００６１】
図５において、ｍｉｎ（Ａ，Ｂ）はＡまたはＢの最小値に等しく、ｎはグループに割り当てられたドット数であり、そしてｔｏｔは割り当てられた有色ドット数である。
【００６２】
各々のグループについて、処理ロジックは、初期的に、ｔｏｔがＣ、Ｍ及びＹに対するドット総数に等しいと設定し、次式のようになる（処理ブロック５０１）。
【００６３】
ｔｏｔ＝Ｃｄｏｔｓ＋Ｍｄｏｔｓ＋Ｙｄｏｔｓ
したがって、各々のグループについて、処理ロジックは、そのＣＭＹＫドット分布をＣＭＹＫＲＧＢＷ分布のドット数ｎに変換する（処理ブロック５０２）。この変換は多くの処理において起こる。先ず、処理ロジックはｔｏｔ＞ｎであるかどうかを決定する（処理ブロック５０２Ａ）。もしそうであれば、処理ロジックはＲｄｏｔｓ＝ｍｉｎ（Ｍｄｏｔｓ，Ｙｄｏｔｓ）に設定し、Ｍｄｏｔｓ、Ｙｄｏｔｓ及びｔｏｔからＲｄｏｔｓを減じる（処理ブロック５０２Ｂ）。処理ロジックは、次いで、処理ロジックはｔｏｔ＞ｎであるかどうかを決定する（処理ブロック５０２Ｃ）。もしそうである場合、処理ロジックはＧｄｏｔｓ＝ｍｉｎ（Ｃｄｏｔｓ，Ｙｄｏｔｓ）に設定し、Ｃｄｏｔｓ、Ｙｄｏｔｓ及びｔｏｔからＧｄｏｔｓを減じる（処理ブロック５０２Ｄ）。次いで、処理ロジックはｔｏｔ＞ｎであるかどうかを決定する（処理ブロック５０２Ｅ）。もしそうである場合、処理ロジックはＢｄｏｔｓ＝ｍｉｎ（Ｃｄｏｔｓ，Ｍｄｏｔｓ）に設定し、Ｃｄｏｔｓ、Ｍｄｏｔｓ及びｔｏｔからＢｄｏｔｓを減じる（処理ブロック５０２Ｆ）。次いで、処理ロジックはｔｏｔ＞ｎであるかどうかを決定する（処理ブロック５０２Ｇ）。もしそうである場合、処理ロジックはｔｅｍｐ＝ｍｉｎ（Ｒｄｏｔｓ，Ｃｄｏｔｓ）に設定し、Ｃｄｏｔｓ、Ｒｄｏｔｓ及びｔｏｔからｔｅｍｐを減じ、Ｋｄｏｔｓ＝Ｋｄｏｔｓ＋ｔｅｍｐに設定する（処理ブロック５０２Ｈ）。次いで、処理ロジックはｔｏｔ＜ｎであるかどうかを決定する（処理ブロック５０２Ｉ）。もしそうである場合、処理ロジックはＷｄｏｔｓ＝ｎ−ｔｏｔ及びｔｏｔ＝ｔｏｔ＋Ｗｄｏｔｓに設定する（処理ブロック５０２Ｊ）。
【００６４】
各々のブロックのドットの配置
ブロックについてインクドットが設定される（ブロックのグループ間で分割される）場合、用いることが可能である多くのドット配置が存在する。ドットはランダムに配置することが可能であり、また、各々のブロック内のカラー間で空間的に交互に配置することが可能である。しかしながら、これは、人間の眼に対して、分布している全体的な画像における乱雑さをもたらすことが可能である。この乱雑さは生成される空間周波数の広いスペクトルにおいて見られ、ハーフトーンを粒状的に見せることとなる。
【００６５】
また、ハーフトーン化プロセスは、人間の眼が敏感ではない高い空間周波数にハーフトーンの歪みを押し込む、ブルーノイズハーフトーン化のような可視域の外側の空間周波数を加え、または歪めるため、ブルーノイズハーフトーン及び良好な画像品質を達成するための良好な方法は、ブロックドットを配置するためにブルーノイズディザマスク（分散ドットディザマスク）を用いることである。そのマスクの例を図８及び９に示す。用いるマスクは比較的大きいかまたはブロックサイズと同じサイズである。本発明の一実施形態において、処理ロジックは、最適結果をえるために粗く輝度の順番にドットを配置する。その順番は、ブルードット及びブラックドットのような見え方の近いドットがハーフトーンにおいて互いに凝集しないように、且つハーフトーンを粒状的に見せないように、保証することは重要である。本発明の一実施形態において、カラーを分離するための順序を用いるが、それは輝度の順序ではなく、ＫＢＣＧＲＭＹＷの順序である。最後に、処理ロジックは順序付けされたドットを通して反復され、ブロック内のグループの空間ドメイン内の次のマスクの番号にドットを配置する。
【００６６】
本発明の一実施形態において、処理ロジックは、空間的順序ＫＢＣＧＲＭＹＷにブロックの各々のグループについてインクドットを配置し、次いで、ブロックをカバーするマスクの数を通して順番に処理を行う。各々の数は出力画素をカバーし、その出力画素は、画素が属すグループから次のインクカラーを割り当てる。
【００６７】
図６Ａ及び図６Ｂは、ブロックがエッジを有しない、即ち１つのグループのみを有する場合の実施例を示している。図６Ａ及び６Ｂを参照するに、４ｘ４ブロックは１つのグループであって、５Ｋ、３Ｒ、７Ｍ及び１Ｙのインクの組み合わせを有している。この実施例を用いると、図６Ａに示す４ｘ４ブロックについての実施例の配置マスクを用いると、ドットは、そのマスクにしたがった順序にドットを配置することによりドットを配置する。例えば、ドットの最初のセットは５Ｋであり、１つのＫは、マスクにおける最初の５つの番号（１〜５）の位置に配置される。これを図６Ｂに示す。一旦すべてのＫが配置されると、次のカラーのセット、即ち３Ｒが、マスクにおける次の３つの番号（６〜８）に配置される。３Ｒが配置された後、マスクにおいて指定される次の７つの位置（９〜１５）の各々に７Ｍを配置する。最終的に、１つのＹをマスクの最後の位置（１６）に配置する。図６Ｂは、結果として得られるインクの配置を示している。
【００６８】
図７Ａ乃至図７Ｃは、グループ１は７Ｃ（シアン）から構成され、グループ２は４Ｋ及び５Ｒから構成される、ブロックを２つのグループに分割した実施例を示している。同じ実施例の配置マスク（図７Ｂ）を用いて、ドットを配置する。マスクにより数字的に進めて、つぎのカラードットを特定のグループ、この場合グループ１またはグループ２から配置するが、これは、配置マスクの位置及びその位置がグループ１またはグループ２のどちらであるかに依存する。さらに具体的には、配置マスクにおける位置１はグループ１にあり、したがって、７Ｃの１番目はその位置に配置される。しかしながら、その配置マスクにおける位置２及び３はカラーグループ２に属するから、配置されるべき４Ｋのうち初めの２Ｋはそれらの位置に配置される。次に、配置マスクにおける位置４はカラーグループ１に属す。したがって、カラーグループ１からの次のドット（７Ｃの２番目）をその位置に配置する。このようなパターン化は、図６Ｃに示すように結果として得られるインク配置が得られるまで、続けられる。
【００６９】
ハーフトーンにおける個々のドット数を最少化するために、または他のローバスト性の理由により、クラスタードットディザマスクを用いることが可能である。
【００７０】
異なるブルーノイズマスクを異なる装置のためにより良好に機能させる。特定のレーザコピーに対しては、最大限、小さい数を並べることが重要であったため、低いインク密度の領域においては非常にブルーのスペクトルが得られた。中程度のインク密度においては、ブロックサイズが調和するある程度強い空間周波数をもつことが重要である。例えば、１２ｘ１２ブロックサイズを用いると、マスクは強い６ｘ６、４ｘ４、３ｘ３及び２ｘ２の周波数を有する筈である。これは、ブロックから１２ｘ１２空間周波数を埋没させる助けとなる。図８のブルーノイズｂｎ１４４を分散させたディザマスクは、この機能を良好に果たし、且つすべてのインク密度領域において良好に見える。しかしながら、そのように数多くの強い空間周波数はインクのモアレを増加させる。クラスター化されたドットのハーフトーンであるハーフトーン画像に対して、他のマスク、即ち、図９におけるｅ４９分散ディザマスクが用いられる。ｂｎ１４４マスクは再帰モザイクに基づいている。
【００７１】
上述のＢＣＱ方法には多くの優位性がある。これらの優位性の多くはエラー拡散またはディザ技術と比較することで分かる。第１に、標準的なエラー拡散と違って、ここで述べるＢＣＱ技術は各々のブロックを独立してハーフトーン化するため、ＢＣＱ技術を並行して処理することが可能である。また、各々のブロックのために実行する演算は非常に少ないものである。ディザは、並行的に実行されることが可能であるが、エラー拡散及びＢＣＱ技術がよりはっきりしたエッジとよりスムーズなスムーズ領域を有するのと同程度の品質を得ることはできない。即ち、ディザは、オリジナルの信号が各々の画素に加えられたノイズを有し、次いで各々の画素が個別に量子化されることによるプロセスである。ブロックカラー量子化は、同時に画素のブロックを量子化し、ノイズが加えられることはない。ディザにおいて加えられたノイズは、エッジがノイジーであり、したがって、画像エッジが空間的に真実とは異なることを意味している。また、ディザにおいて加えられたノイズは、スムーズな領域がスムーズではないこともあることを意味している。
【００７２】
更に、ＢＣＱによるハーフトーンは、カラーパッチ内の輝度変化がより小さいので、ディザまたはエラー拡散に比べてよりスムーズである。例えば、５０％がＣのドットであり、残りの５０％がＹのドットであるようなパッチを想定する。エラー拡散またはディザはカラー平面を独立してハーフトーン化するため、平均して、パッチ内のドットの２５％はＣ（＝Ｇ）の上にＹをもち、ドットの２５％はＣのないＹであり、ドットの２５％はＹのないＣであり、そしてドットの２５％はブラックまたはＷである。ここで述べるＢＣＱ技術は一度にすべてのカラー平面を想定している。それ故、同じパッチが５０％のＣドットと５０％のＹドットをもち、ＧドットとＷドットはもっていない。したがって、パッチにおけるドットのカラー変化（及び、特に輝度の変化）は、ＢＣＱを用いたハーフトーンについてはより小さくなり、結果として得られる低いカラードットコントラストは人間の視覚に対して容易なカラー平均化をもたらし、それ故、スムーズなハーフトーンがもたらされる。
【００７３】
また特筆すべきこととして、個々で述べるＢＣＱ技術はインクとトナーを節約し、結果的に経費節減、スピード、鮮明さおよび環境について良好に作用する。ブラックドットの上にカラードットを印刷しないことにより、ＢＣＱ技術はトナーまたはインクを節約する。この技術によると、Ｙ＋Ｋのようなカラーを選択することを可能としない。実験的には、通常の画像について平均１９％の節約が得られた。そのインクの節約を直接コスト削減に結びつけることが可能である。
【００７４】
インクまたはトナーの使用に対する利点は数多くある。コスト削減と売り物になること、潜在的に速いプロセスであること、より鮮明なテキストと細い線、及びトナー／インクの使用量が少なくて済むことは環境に対して良好に作用する。
【００７５】
モアレは、近接した空間周波数が互いに干渉し合うとき、問題となり得る。ＢＣＱにおけるハーフトーン化に対して標準的なブロック構造があるが、各々のブロックは、存在する何れかのエッジに沿って分割されるため、殆んどの画像においては、エラー拡散を用いる場合程モアレは存在しなかった。具体的には、高周波数のラインテストであって、直線及び円形の線のテストに対しては、モアレの増加は見られなかった。クラスタードットハーフトーン画像（クラスタードットハーフトーンのパッチであって、ここでは再ハーフトーン化がなされている）については、モアレは少し増加した。各々のブロック内に標準的構造をもたない、ｅ４６マスク（図９に示したｅ４６マスク）に対して、各々の１２ｘ１２ブロック内に標準的構造をもつ、ｂｎ１４４マスク（図８）からの変化により、この少しの増加を取り除くことが可能である。モアレのリスクがないときに、ｅ４６マスク（図９）を用いることにより、より可視的なブロッキネス（ｂｌｏｃｋｉｎｅｓｓ）に導かれる。
【００７６】
１２ｘ１２反復マスクに関連するブロッキネスがある。それはわずかな効果であり、一部の領域のみにおいて認識されるものであるが、１２インチの見える距離においてさえ認識され、肌の領域のような重要な部分においては認識可能である。それは、ＢＣＱによるハーフトーン化に関する最も悪いアーチファクトである。ブロッキネスに関して、ＢＣＱは、トレードオフの関係にあるカラーと空間分解能を適合させるようにして処理するが、それは小さいブロック内のみに限られる。ＢＣＱのハーフトーン化における最も大きな特徴はブロックであるため、ブロックの周波数より低い空間周波数におけるアーチファクト（モアレの可能性意外の）は存在しない。ブロックの周波数において、何らかの可視的‘ブロッキネス’が存在し得る。幸運にも、人間の視覚は高い空間周波数に対して敏感ではない。ブロックのサイズはｄｐｉと共に増加しないため、ｄｐｉが高くなるにつれてブロックの絶対空間周波数は増加する。
【００７７】
ブロッキネスに対する解決方法は２つあり、１つは、上述のより大きいマスクを用いることまたは上述の６角形のマスクを恐らく用いることにより、それを取り除くことである。もう１つの解決方法は、誰もブロックを認識できない程ｄｐｉが十分高くなるまで待つことである。即ち、ｄｐｉが高くなるとき、ブロックのサイズはそのまま同じであるため、ブロックの空間周波数は、人間の可視域を通り過ぎて、高くなる。ハーフトーン化の効果そのもののように、ブロックは、人間の視覚が認識することさえできない画素のようになる。高いｄｐｉにおいて消えてしまうブロッキネスの検討は上述したが、１８００ｄｐｉにおいて生じる筈である。
【００７８】
低密度領域及び明るいカラーは、ＢＣＱのハーフトーン化によりよく調整される。ＢＣＱハーフトーン化は、エラー拡散により生成された黒っぽい虫食い状態よりよりスムーズになる、最小の輝度変化と規則的な間隔をもつこれらの領域を調整する。更に、エラー拡散アーチファクト（例えば、明るいバックグラウンドにおける黒い虫食い）はより低い空間周波数にあり、それ故、消去させるには、ＢＣＱの標準ブロックより、より高いｄｐｉを必要とするであろう。
【００７９】
エラー拡散は、粒状性または虫食いのように見える、ドットの虫のような動きと他の大規模なアーチファクトを生成する。ＢＣＱハーフトーン化は虫のような動きのアーチファクトまたは粒状性を生成しない。
【００８０】
ＢＣＱは、エラー拡散が有するカラーのイズまたは粒状性を有しないが、ときどき、ブロッキングアーチファクトの影響を受ける。ブロッキングが見えないとき、ＢＣＱハーフトーンはよりスムーズに見える。より高いｄｐｉにおいて、ブロッキングが視覚的に見えないとき、ＢＣＱは常にスムーズに見えるようにハーフトーン化すると考えられる。特に、より低い密度において且つイエローに対して、ＢＣＱハーフトーンはよりスムーズに見える。
【００８１】
他の実施形態
理想的には、画素は一旦最後まで読み取られなければならない。本発明の一実施形態において、ここで説明するＢＣＱ技術は、ブロックの画素を最後まで読み取り、それらをグループ分けし、次いで、再び最後まで読み取って各々のグループの平均を求める。グループ化を行う方法を変化させることにより、または平均ではないグループの代表値を変化させることにより、たった一度だけ読み取ることが可能となる筈であり、バッファリングを行う必要はない。
【００８２】
本発明の他の実施形態においては、より黒いブラックを達成するために、Ｋ＋Ｃ＋Ｍ、またはＫ＋Ｃ或いはＫ＋Ｍのような他の重ね印刷したブラックをインクの選択肢として含める。ＢＣＱ技術により印刷する最も黒いドットはＫである。しかしながら、ブラックインクは完全に光を吸収するものではないため、Ｋ＋Ｃ＋Ｍのパッチはブラックのパッチに比べてより黒く見えさえする。このことがまさに問題である場合、インクの選択肢としてＫ＋Ｃ＋Ｍを含むことにより自由度を持たせるべきである。
【００８３】
画像またはビデオ圧縮のためのＢＣＱ
ブロックカラー量子化は画像またはビデオ圧縮に拡張することが可能である。例えば、次のＢＣＱ符号化方法を検討する。
１）画像における各々の小さいブロックのために、ブロックのカラーを２つ（または４つ）のカラーグループにクラスター化し、ブロックが属するグループの各々の画素についてマーキングする。
２）各々のブロックの各々のグループのために、平均カラーを求める。
３）画像における平均カラー全てをクラスター化し、次いで、コードブックまたは平均カラーのパレットを作成する。
４）パレットカラー及び各々のブロックの各々のグループについての違いを符号化する。
【００８４】
ランレングスエンコーディングまたはブロック０／１マップの辞書（またはコードブック）はより多くのビットを保存する。階層型のパレットまたはその違いをパレットカラーに区別して符号化することはより多くのビットを保存する。上述のようなコード化方法は、ブロックのグループレベルにおいて、必然的に損失が多いが、復号化は濃淡のむらがある出力を生成することに比べて洗練されている。
【００８５】
単純な復号器は、正しいパレットカラーと各々のブロックの各々のグループについての違いのみを表示する。より洗練された復号器は類似するブロック間を補間し、それ故、グレーディングとシェーディングを回復させる。
【００８６】
この考え方は、ＪＢＩＧ辞書及びＶＱコードブック、そして可能な他の圧縮スキームを思い出させるものである。類似する対象物またはテクスチャは類似する符号化を有してという意味で、この考え方はモデルベースである。
【００８７】
模範的な実施形態
本発明の一実施形態において、ブロックカラー量子化は、たとえばコピー機またはプリンタのようなシステムに内蔵されたプロセッサによりなされる。そのアルゴリズムは、特定用途向け集積回路（ＡＳＩＣ：ａｐｐｌｉｃａｔｉｏｎ　ｓｐｅｃｉｆｉｃ　ｉｎｔｅｇｒａｔｅｄ　ｃｉｒｃｕｉｔ）にある。図１０は、上述のブロック量子化技術のための処理を含むことが可能である模範的なシステムについてのブロック図である。
【００８８】
図１０を参照するに、システム１０００は、情報を処理するための内蔵プロセッサ１０１２から構成される。更に、システム１０００は、情報及び内蔵プロセッサ１０１２により実行される指令を記憶するために内蔵プロセッサに結合された、ランダムアクセスメモリ（ＲＡＭ）または他の動的メモリデバイス１００４から構成される。
【００８９】
更に、システムのユーザに対して情報を表示するために、内蔵プロセッサ１０１２に結合された陰極線管（ＣＲＴ）または液晶表示装置（ＬＣＤ）等の表示装置１０２１に、コンピュータシステム１０００を接続することができる。内臓プロセッサ１０１２に対して情報とコマンドの選択を伝達するために、アルファベットと数字以外のキーを含むアルファニューメリック入力装置を含むことができる。プロセッサ１０１２に対する情報とコマンドの選択を伝達するために、そして表示装置１０２１のカーソルの動きを制御するために、マウス、トラックボール、スタイラスペンまたはカーソルコントロールキー等の付加的なユーザによる入力装置を備えることができる。
【００９０】
プリントエンジン１０２４は内蔵プロセッサ１０１２に連結されている。本発明の一実施形態においては、プリントエンジン１０２４はコピー機の一部である。コンピュータシステム１０００の構成要素及び関連するハードウェアの何れかを、本発明において用いることができる。しかしながら、システムの他の構成がそれら装置の一部または全てを含むことができる。
【００９１】
当業者には、上述の内容を読むことにより、本発明の代替及び変形が可能であることは疑いもなく明白である一方、例として示し、記述した何れかの本発明の実施形態は、決して、限定を考慮することを意図されたものではない、ことを理解されたい。したがって、詳細に記述して参照した種々の実施形態は、本発明の必須要件としての特徴のみを列挙した請求項に基づく請求範囲を限定することを意図されたものではない。
【図面の簡単な説明】
【図１】本発明の一実施形態にしたがったブロックカラー量子化ハーフトーン化を実行するためのプロセスを示すフロー図である。
【図２】本発明の一実施形態にしたがったカラーハーフトーン化のためのブロック量子化システムのブロック図である。
【図３】画素をグループ化する３つの実施例を示す模式図である。
【図４】本発明の一実施形態にしたがった、画像ブロックに画素を取り、クラスターを位置付けるために用いられるプロセスのフロー図である。
【図５】本発明の一実施形態にしたがった、最終的なドット分布を演算するためのプロセスのフロー図である。
【図６Ａ】１つのカラーグループのみをもつブロックを示す図である。
【図６Ｂ】１つのカラーグループのみをもつブロックを示す図である。
【図７Ａ】２つのグループをもつブロックの実施例を示す図である。
【図７Ｂ】２つのグループをもつブロックの実施例を示す図である。
【図７Ｃ】２つのグループをもつブロックの実施例を示す図である。
【図８】模範的なマスクを示す図である。
【図９】他の模範的なマスクを示す図である。
【図１０】模範的なシステムを示すブロック図である。
【符号の説明】
１０１〜１０６　処理ブロック
２０１　入力画像
２０２　グループ化ユニット　ブロック生成ユニット
２０３　カラー選択ユニット
２０４　カラーマッチング及びレイアウトユニット
４０１〜４１１　処理ブロック
５０２　処理ブロック
５０２Ａ〜５０２Ｊ　処理ブロック
１０００　コンピュータシステム
１００４　メモリ
１０１２　内蔵型プロセッサ
１０２１　表示装置
１０２４　プリントエンジン
【図１】
2004056783.tif 000003
【図２】
2004056783.tif 000004
【図３】
2004056783.tif 000005
【図４】
2004056783.tif 000006
【図５】
2004056783.tif 000007
【図６Ａ】
2004056783.tif 000008
【図６Ｂ】
2004056783.tif 000009
【図７Ａ】
2004056783.tif 000010
【図７Ｂ】
2004056783.tif 000011
【図７Ｃ】
2004056783.tif 000012
【図８】
2004056783.tif 000013
【図９】
2004056783.tif 000014
【図１０】
2004056783.tif 000015