カラー中間調処理方法及び装置、記録媒体
【課題】 誤差拡散と同様の空間解像度及び色解像度を達成し、かつ誤差拡散につきもののアーティファクトの発生を防止するカラー中間調処理を実現する。
【解決手段】 カラー中間調処理にブロック量子化を利用する。ブロック生成・色平均ユニット１０２は入力画像及び出力画像をブロック分割する。出力ブロックは１つの入力ブロックに対応する。ユニット１０２は各入力ブロックの色平均を計算する。色合わせ・配置ユニット１０４は、各出力ブロックのための出力色セットを対応入力ロックの色平均に一致するように計算し、その出力色を出力ブロック内にモザイク状配置をする。
【解決手段】 カラー中間調処理にブロック量子化を利用する。ブロック生成・色平均ユニット１０２は入力画像及び出力画像をブロック分割する。出力ブロックは１つの入力ブロックに対応する。ユニット１０２は各入力ブロックの色平均を計算する。色合わせ・配置ユニット１０４は、各出力ブロックのための出力色セットを対応入力ロックの色平均に一致するように計算し、その出力色を出力ブロック内にモザイク状配置をする。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、カラー中間調処理(halftoning)の分野に係り、特に、カラー中間調処理へのブロック量子化技術の応用に関する。
【０００２】
【従来の技術】カラー中間調処理は、多ビット（例えば２４ビット）の画像を、少数の色だけを用いた、場合によって空間解像度を上げた画像として表現しようとするものである。これは多くのカラープリンタで直面する課題である。一般にカラープリンタは、例えば、シアン、マゼンタ、イエロー、黒、白と、それらの組み合わせであるシアン＋マゼンタ、シアン＋イエロー、マゼンタ＋イエローのような、５色又は８色だけしか使用できない。
【０００３】カラー中間調処理アルゴリズムの評価は、視覚の主観性のせいで困難な場合がある。中間調処理アルゴリズムにおける特有の目標として、色が一致すること、計算が単純であること、粒状性が低いこと、アーティファクト(artifact)をできるだけ少なくすること、後処理による影響を低減することがある。これら各目標の相対的な重要性は、観察者、予定観察距離、対象画像により左右される。
【０００４】色の一致には少なくとも２つの目標、すなわち、個々の入力色と出力色が近いこと、及び、誤差のばらつきがないことがある。計算の課題には、実行速度、並列処理の容易性、メモリ容量、複雑さがある。粒状性は、別々の出力色を（それらの色が完全に混じり合わずに）知覚できる能力として説明することができる。知覚される粒状性はｄｐｉといくぶん相関がある。
【０００５】空間解像度が悪いか色解像度が悪いと（又はその両方が悪いと）、ディテール情報が失われるであろう。アーティファクトは、スペックル(speckle)、縞模様(steak)、ゴースト、グリッディング(gridding)、テクスチャ、それと非常に重要な擬似輪郭（バンディングとしても知られている）など、アルゴリズムの結果で好ましくない現象を表す一般用語である。
【０００６】中間調処理画像は、中間調処理された時点で”完成した”とは限らないので、後処理の影響は重要な問題である。その画像に対し、圧縮のためのダウンサンプリングからエッジ強調まで様々な画像処理操作がさらに行われることがある。中間調処理アルゴリズムは、これら操作の成否、容易さを左右することがある。
【０００７】中間調処理のための技術は、ディザ法、誤差拡散法、反復法など様々なものが考案されている。殆どのカラー中間調処理技術は、白黒中間調処理技術を単純に３つの色プレーンの各々に対し別個に拡張して適用する。このようなコンポーネント別に拡張する方法は、計算の面では効率的ではあるが、インク色の数学的線形性を前提としている。しかし、印刷における減法混色は非線形であるため、プレーン別の中間調処理方法は最善の方法ではない。
【０００８】ディザは、擬似乱数の２次元周期信号を画像の各色成分に加算してから、各画素を最も近い出力色に量子化する構成である。ディザの信号は、見た目には混じり合って見える、交互に色が変化するパターンを生成するように作られる。異なるタイプのディザとして、ドット集中型ディザ、ドット分散型ディザ、ドット順序型ディザがある。白色ノイズを用いるディザは、組織的ディザほどには視覚的に良好な結果を得られない。ディザは、周期的パターンが目立つという欠点を有することが知られている。ディザを改良するために様々な取り組みがなされている。カラーへのディザの応用は当該技術分野で知られている。これ以上の情報を知るには「A.Karun, et al., "New Methods for Dithering of Color lmages,"Proc. of the IEEE Workshop on Nonlinear Signal/lmage Processing, 1995」を参照されたい。
【０００９】ディザは局所的処理（すなわち、各画素の出力は、その入力画素と、おそらくはディザ信号のような外的要因にのみに依存する）であるのに対し、誤差拡散は、各画素位置での量子化誤差を、誤差の一部を各前進方向へ送る方向性空間フィルタに基づいて、近傍画素へ拡散させる。結果として、誤差拡散による中間調処理は高周波ノイズを加える。目で色が混じり合って実際の色モザイクに気付かないようにすることが目標であるので、この誤差拡散のハイパスフィルタ効果は目が高周波ノイズを知覚しにくいことを利用する。すなわち、誤差拡散は青色空間スペクトルを生じる。青色ノイズのほうが視覚的に好ましいという考えは十分確立したものである。
【００１０】誤差拡散は有効に作用するが、いくつか欠点がある。誤差拡散は、局所的に最適化する、つまり、各画素の位置で最善を尽くすという点で欲張りなアルゴリズムである。誤差は前方へ拡散されるので、誤差拡散は方向性があり、局所領域全体にわたって真の同時最適化はできない。目が色を平均化している局所の外へ誤差が拡散されることがある。誤差拡散のアーティファクトとして、ある程度のスペックル、縞模様、過渡的なエッジ効果及びグリッディング効果がある。誤差拡散のために必要なフィードバックループが、アルゴリズムの並列実行の障害になることがある。
【００１１】誤差拡散の改良が長年にわたって行われてきた。構造的アーティファクトの低減、フィードバック・フィルタの適応化、ニューラルネットワークの利用というような方向で努力がなされてきた。
【００１２】また、知覚モデルとプリンタ・モデルを用いる優れた白黒中間調処理技法があるが、これらはカラー中間調処理のためには複雑な拡張が必要である。
【００１３】平均マッチングの考え方を考慮した別の白黒アルゴリズムもある。例えば、ある多重解像度中間調処理アルゴリズムは、元の画像の解像度よりスタートし、出力画像の平均グレーレベルを入力画像の平均グレーレベルと等しくする。次に、１つ上のレベルの解像度では、平均グレーレベルを４象限間で各象限の平均グレーレベルに基づいて比例的に分配する。この過程は、各画素が黒又は白に量子化される解像度レベルまで繰り返される。例えば、「Breaux, et al., "WaveletMethods for Compression, Rendering, and Descreening in DigitalHalftoning," SPIE vol. 3078,1997」、「P.W.Wong, "Halftoning byMultiscale Dot Distribution,"Proc. IEEE Int. Conference on lmageProcessing, Vol. III, 1995」、「P.W. Wong,"Mean matching Halftoning ona Rotated Quad-tree Structure," Human Vision and Electronic lmaging," Proc. SPIE 2657, 1996」を参照されたい。
【００１４】もう１つの従来技術の方法では、入力画像と出力画像の平均グレーレベルがいくつかの解像度で生成される。さらに別の従来技術では、ウェーブレット平均を計算し、次に、ディザを利用して、これらの平均グレーレベルを近似する。より具体的には、まず画像をウェーブレットを用いて圧縮し、次いで、各レベルごとに、ウェーブレット係数を平均グレーレベルとして用いることにより白ドットを４象限内でどのように分配すべきか決定する。この手法は、画素レベルまでは達しないため、選択した数の白ドットを、ドット集中型ディザ又はドット分散型ディザを利用して配列する。それらの結果には、水平方向及び垂直方向のアーティファクトと擬似輪郭が生じる欠点がある。
【００１５】
【発明が解決しようとする課題】本発明は、以上に述べた従来技術の問題点に鑑み、ブロック量子化を応用する新規なカラー中間調処理方法及び装置を提供することを目的とする。
【００１６】
【課題を解決するための手段】請求項１記載のカラー中間調処理方法の特徴は、入力画像及び出力画像をブロックに分割するステップ、ここにおいて出力画像の各ブロックは入力画像の１つのブロックに対応する；各入力ブロックの色平均を計算するステップ；出力画像の各ブロックのための出力色セットを入力画像の対応ブロックの色平均に一致するように計算するステップ；及び、出力画像の各ブロックにおける出力色セットの配置を制御するための指示を生成するステップを有することである。
【００１７】請求項２記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、特定の条件が満たされるときに、それぞれの入力ブロック及び出力ブロックをサブブロックに分割するステップをさらに有することである。
【００１８】請求項３記載のカラー中間調処理方法の特徴は、請求項２記載の構成において、ブロックをサブブロックに分割するための特定の条件とは、そのブロックがエッジを含んでいるかどうかであることである。
【００１９】請求項４記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、ブロックの特性はブロックに関連した色を人間の目が平均化するようなものであることである。
【００２０】請求項５記載のカラー中間調処理方法の特徴は、請求項４記載の構成において、ブロックの特性はサイズ、形状及び想定観察距離の中の１つ以上を含むことである。
【００２１】請求項６記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットの計算は、色空間上で表現可能な値を調べ、対応した入力ブロックの色平均に最も近い表現可能値を見つけることにより行われることである。
【００２２】請求項７記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットの計算に、同セット中の出力色を決定するために平均色に関するルックアップテーブルを利用することである。
【００２３】請求項８記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットの計算に整数計画法を利用することである。
【００２４】請求項９記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットの計算に動的計画法を利用することである。
【００２５】請求項１０記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットの計算に近似線形計画法を利用することである。
【００２６】請求項１１記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットの計算に近似最大エントロピー法を利用することである。
【００２７】請求項１２記載のカラー中間調処理方法の特徴は、請求項２記載の構成において、ブロックをサブブロックへ分割するステップは、各ブロックごとに、及び、そのブロックの複数のサブブロックの各々ごとに色値の関数を計算するステップ、ブロックとサブブロックの色値の関数間の距離が閾値より大きいか判定するステップ、及び、その距離が閾値より大きいときにブロックをサブブロックに分割するステップからなることである。
【００２８】請求項１３記載のカラー中間調処理方法の特徴は、請求項１２記載の構成において、各サブブロックについての色値の関数を、そのブロックの他のサブブロックについての関数値と比較することによりエッジの存在を判定するステップをさらに有することである。
【００２９】請求項１４記載のカラー中間調処理方法の特徴は、請求項１２記載の構成において、複数のサブブロックは４個のサブブロックからなることである。
【００３０】請求項１５記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットが与えられたならば、ターゲット色に一致するように、かつ空間的アーティファクトを減らすように各ブロック内に色を配置するステップをさらに有することである。
【００３１】請求項１６記載のカラー中間調処理方法の特徴は、請求項１５記載の構成において、各ブロック内の色配置で規則的グリッディングを行うことである。
【００３２】請求項１７記載のカラー中間調処理方法の特徴は、請求項１５記載の構成において、各ブロック内の色配置で、選択された出力色をディザマトリクスに従って配置することである。
【００３３】請求項１８記載のコンピュータ読み取り可能な記録媒体の特徴は、請求項１乃至１７のいずれか１項記載のステップをコンピュータに実行させるための実行可能命令が記録されたことである。
【００３４】請求項１９記載のカラー中間調処理装置の特徴は、入力画像及び出力画像をブロックに分割するディバイダ、ここにおいて出力画像の各ブロックは入力画像の１つのブロックに対応する；各入力ブロックの色平均を計算する第１のロジック；出力画像の各ブロックのための出力色セットを入力画像の対応ブロックの色平均に一致させるように計算する第２のロジック；及び、出力画像の各ブロックにおける出力色セットの配置を制御するための指示を生成する指示生成ロジックを有することである。
【００３５】請求項２０記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、前記ディバイダは、特定の条件が満たされるときに、それぞれの入力ブロック及び出力ブロックをサブブロックに分割することである。
【００３６】請求項２１記載のカラー中間調処理装置の特徴は、請求項２０記載の構成において、ブロックをサブブロックに分割するための特定の条件とは、そのブロックがエッジを含んでいるかどうかであることである。
【００３７】請求項２２記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、ブロックの特性はブロックに関連した色を人間の目が平均化するようなものであることである。
【００３８】請求項２３記載のカラー中間調処理装置の特徴は、請求項２２記載の構成において、ブロックの特性はサイズ、形状及び想定観察距離の中の１つ以上を含むことである。
【００３９】請求項２４記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットを計算する第２のロジックは、色空間上で表現可能な値を調べ、対応した入力ブロックの色平均に最も近い表現可能値を見つけることである。
【００４０】請求項２５記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットを計算する第２のロジックは、同セット中の出力色を決定するために平均色に関するルックアップテーブルを利用することである。
【００４１】請求項２６記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットを計算する第２のロジックは整数計画法を利用することである。
【００４２】請求項２７記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットを計算する第２のロジックは動的計画法を利用することである。
【００４３】請求項２８記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットを計算する第２のロジックは近似線形計画法を利用することである。
【００４４】請求項２９記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットを計算する第２のロジックは近似最大エントロピー法を利用することである。
【００４５】請求項３０記載のカラー中間調処理装置の特徴は、請求項２０記載の構成において、各ブロックごとに、及びそのブロックの複数のサブブロックの各々ごとに色値の関数を生成する計算ロジック、ブロックとサブブロックの色値の関数間の距離が閾値より大きいか判定する判定ロジック、及び、その距離が閾値より大きいときにブロックをサブブロックに分割するディバイダをさらに有することである。
【００４６】請求項３１記載のカラー中間調処理装置の特徴は、請求項３０記載の構成において、各サブブロックについての色値の関数を、そのブロックの他のサブブロックについての関数値と比較することによりエッジの存在を判定する判定ロジックをさらに有することである。
【００４７】請求項３２記載のカラー中間調処理装置の特徴は、請求項３０記載の構成において、複数のサブブロックは４個のサブブロックからなることである。
【００４８】請求項３３記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットが与えられたときに、ターゲット色に一致するように、かつ空間的アーティファクトを減らすように各ブロック内に色を配置する制御ロジックをさらに有することである。
【００４９】請求項３４記載のカラー中間調処理装置の特徴は、請求項３３記載の構成において、制御ロジックは各ブロック内において規則的グリッディングを行うことである。
【００５０】請求項３５記載のカラー中間調処理装置の特徴は、請求項３３記載の構成において、制御ロジックは各ブロック内に選択された出力色をディザマトリクスに従って配置することである。
【００５１】請求項３６記載のカラー中間調処理装置の特徴は、入力画像及び出力画像をブロックに分割する手段、ここにおいて出力画像の各ブロックは入力画像の１つのブロックに対応する；各入力ブロックの色平均を計算する手段；出力画像の各ブロックのための出力色セットを入力画像の対応ブロックの色平均に一致するように計算する手段；及び、出力画像の各ブロックにおける出力色セットの配置を制御するための指示を生成する手段を有することである。
【００５２】請求項３７記載のカラー中間調処理方法の特徴は、入力画像及び出力画像をブロックに分割するステップであって、エッジを含むブロックのサイズを適応的に変更してエッジを含まない複数のブロックを生成するステップを含むステップ、及び、入力画像の対応ブロックの色平均を最もよく表現する出力色セットを計算するステップを有することである。
【００５３】請求項３８記載のカラー中間調処理方法の特徴は、請求項３７記載の構成において、入力画像の色域は出力画像の色域に合わせるため予め調整されることである。
【００５４】請求項３９記載のカラー中間調処理装置の特徴は、入力画像及び出力画像をブロックに分割する手段であって、エッジを含むブロックのサイズを適応的に変更してエッジを含まない複数のブロックを生成する手段を含む手段、及び、入力画像の対応ブロックの色平均を最もよく表現する出力色セットを計算する手段を有することである。
【００５５】請求項４０記載のカラー中間調処理装置の特徴は、請求項３９記載の構成において、入力画像の色域は出力画像の色域に合わせるため予め調整されることである。
【００５６】請求項４１記載のカラー中間調処理装置の特徴は、エッジを含むブロックのサイズを適応的に変更してエッジを含まない複数のブロックを生成することにより入力画像及び出力画像をブロックに分割するディバイダ、及び、入力画像の対応ブロックの色平均を最も良く表現する出力色セットを計算する計算ロジックを有することである。
【００５７】
【発明の実施の形態】ブロック量子化方法及び装置について説明する。以下の説明において、多くの詳細事項が提示される。ただし、これら特定の詳細事項によらずに本発明を実施し得ることは当業者には明らかであろう。他方、本発明を難解にしないため、周知の構造及び素子はブロック図により示し詳細は示さない。
【００５８】以下の詳細な説明中に、コンピュータのメモリ内のデータビットに対する操作のアルゴリズム及び記号表現によって表された部分がある。このようなアルゴリズム記述及び表現は、データ処理技術の当業者が研究内容を他の当業者に最も効率的に伝えるために用いる手段である。あるアルゴリズムがあり、それが概して期待した結果に至る筋の通ったステップの系列だと理解されるとする。それらのステップは、物理量の物理的処理を要するステップである。必ずという訳ではないが、これらの物理量は記憶、転送、結合、比較、その他処理が可能な電気的または磁気的信号の形をとるのが普通である。これらの信号をビット、値、要素、記号、文字、術語、番号などで表わすのが、主に慣用上の理由から便利な場合があることが分かっている。
【００５９】ただし、このような術語や同様の用語はすべて適切な物理量と関連付けられるべきであり、また、それら物理量に付けた便宜上のラベルに過ぎないということに留意すべきである。以下の説明より明らかなように、特に断わらない限り、”処理”、”演算”、”計算”、”判定”、”表示”などの用語によって論じられることは、コンピュータシステムのレジスタ及びメモリの内部の物理的（電子的）な量として表現されたデータを処理して、コンピュータシステムのメモリやレジスタ、その他同様の情報記憶装置、情報伝送装置又は情報表示装置の内部の同様に物理量として表現された他のデータへ変換する、コンピュータシステムや同様の電子的演算装置の作用及びプロセスを意味する。
【００６０】本発明は、本明細書に述べる処理を実行するための装置にも関係するものである。このような装置は、所要目的のために専用に作られてもよいし、汎用コンピュータを内蔵のコンピュータ・プログラムによって選択駆動もしくは再構成したものでもよい。そのようなコンピュータ・プログラムは、コンピュータが読み取り可能な記憶媒体、限定するわけではないが例えば、フロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスクなどの任意種類のディスク、リードオンリーメモリ（ＲＯＭ）やランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード又は光カードなど、コンピュータのシステムバスに接続された電子的命令の記憶に適した任意種類の媒体に格納することができる。
【００６１】本明細書に提示されるアルゴリズム及び表示は、本質的に、いかなる特定のコンピュータ、その他の装置とも関わりがない。様々な汎用マシンを、本明細書に述べた内容に従ったプログラムで利用し得るが、所要の手順のステップの実行のために、より特化した装置を作るほうが好都合であるかもしれない。そのような多様なシステムに必要な構造は以下の説明から明らかになろう。また、いかなる特定のプログラミング言語とも関連付けることなく本発明を説明する。本明細書に述べる本発明の内容を実現するために様々なプログラミング言語を使用し得ることは明らであろう。
【００６２】機械読み取り可能媒体は、機械（例えばコンピュータ）が読み取ることができる形式で情報を記録するための任意の機構を包含する。例えば、機械読み取り可能媒体には、リードオンリーメモリ（ＲＯＭ）；ランダムアクセスメモリ（ＲＡＭ）；磁気ディスク記憶媒体；光記憶媒体；フラッシュメモリ素子などが含まれる。
【００６３】《ブロックカラー量子化を利用したカラー中間調処理の概要》本発明は、入力ブロックのサイズが適応的に調整されるブロック量子化を利用してカラー中間調処理を行う。図１は、カラー中間調処理のためのブロック量子化システムの一実施例のブロック図である。本ブロック量子化システムは、その入力ドメインと出力ドメインの間で色合わせを行って、入力ドメインの色数が出力ドメインの使用可能色数より多い場合のカラー中間調処理を実現する。本ブロック量子化システムは、入力ドメイン及び出力ドメインの画像を複数ブロックに分割し、入力ドメインの画像の各ブロックの色平均を出力ドメインの画像の１つのブロックの色平均に一致させることによって色合わせを行う。ブロックは任意の形状でよく、２つ以上の形状を組み合わせた複雑な形状でもよい。例えば、ブロックは正方形（ｄ×ｄ）でもよいが、長方形（ｄ×ｂ）（ただし、ｄ≠ｂ）でもよい。
【００６４】一実施例では、入力ドメインはモニタを有するコンピュータシステムからなり、出力ドメインはプリンタからなる。ここで説明するブロック量子化技術は、入力画像の各小ブロックごとに、その色平均を最適に（一実施例では適切な距離基準による）表現する対応出力ブロックの印刷色セットを計算する。このようにして、ここに説明する中間調処理技術によれば、局所的入力領域毎に、その平均色を対応した局所的出力領域の平均色と確実に一致させるが、それら領域は目で確実に平均化されるような十分小さな領域である。本ブロック量子化技術は、印刷プロセスの高い空間解像度を利用して色解像度を向上させ、制限条件付きの局所的色最適化を達成する。誤差拡散法につきもののスペックル、テクスチャ、その他のアーティファクトの発生はほぼ防止される。
【００６５】本技術は、各入力色を色空間上の３次元（３Ｄ）ベクトルとして扱い、そして一実施例では、減法混色印刷プロセスで得られる実際の出力色を使用して中間調を生成する。
【００６６】図１において、入力画像１０１はブロック生成・色平均ユニット１０２に受け取られ、同ユニットは入力画像１０１をブロックに分割し、各ブロックの平均色値を生成する。一実施例では、ブロックは固定サイズである。
【００６７】ブロック生成・色平均ユニット１０２は、各ブロックを、それにエッジが含まれるときにサブブロックに再分割するブロックサイズ適応調整ユニット１０３を有する。一実施例では、そのサブブロック数は４であるが、任意の数のサブブロックを用いてもよい。ブロックサイズ適応調整ユニット１０３は、すべてのブロックについて、どのブロックにもエッジが含まれなくなるまで、あるいは何らかの他の特定の条件が満たされるまで、個々のブロック（固定サイズでよい）のサブブロックへの再分割を繰り返して行うであろう。別の実施例では、１つ、２つ以上、あるいは全てのブロックにエッジが含まれていたとしてもサブブロックへは分割されないであろう。一実施例では、エッジを含むブロックは、例えば、それを分割すると色解像度の低下を招く場合にはサブブロックに分割されないであろう。なお、このような実施例はフィードバックが必要となるが、このフィードバックは本発明を難解にしないため図１には示されていない。
【００６８】一実施例では、各ブロックにエッジが含まれているか判定するため、ブロックの平均ベクトル色値が計算され、そのブロックの複数の（例えば４個の）サブブロックの平均と比較される。ブロックとサブブロックの平均との差がある閾値を越えるときに、そのブロックはエッジを含むと判定されてサブブロックに再分割される。これはブロックが所定サイズになるまで繰り返されるであろう。例えば、最初に４×４画素ブロックを用いる場合には、ブロックサイズ適応調整はブロックが１×１画素ブロックになるまで繰り返されるであろう。
【００６９】目標値としての入力ブロックの色平均が与えられると、色合わせ・配置ユニット１０４は、平均するとその目標値に可能な限り近い値となる出力色セットを計算する。一実施例では、色合わせ・配置ユニット１０４は、出力画像の色空間上で実現可能な値を調べ、目標に可能な限り近い値を割り出すことによって、出力色セットを計算する。
【００７０】出力色セットが求まると、色合わせ・配置ユニット１０４は、所望の色を得るとともにアーティファクト及び粒状性を減少させ、できれば最小にするように色を配置する。
【００７１】図２は、ここに説明するブロック量子化技術の処理手順の一例を示す流れ図である。このプロセスを実行する処理ロジックは、ハードウェア、ソフトウェア、両者の組み合わせのいずれで構成してもよい。
【００７２】図２を参照すると、プロセスの最初に、処理ロジックは、入力ドメインにおいて目で全体を平均化できるようなブロック・サイズを選択する（処理ブロック２０１）。一実施例では、ブロックのサイズは正方形（ｄ×ｄ）である。別の実施例では、ブロックのサイズは正方形ではない（例えば、長方形、菱形など）。
【００７３】次に、処理ロジックは入力画像及び出力画像を対応したブロックに分割する（処理ブロック２０２）。各入力ブロックに対し、対応する１つのｎ画素の出力ブロックがある（ここで、ｎは出力空間解像度と入力ブロックのサイズによって決まる）。
【００７４】次に、処理ロジックは各ブロックの内部にエッジが存在するか判定する（処理ブロック２０３）。ブロック内のエッジの存在を判定する方法はいろいろある。前述のように、一実施例では、ブロックの色平均とそのサブブロックの色平均の差がある閾値を越える場合にエッジが存在している。エッジがある場合には、処理ロジックは、そのブロックをエッジを含まないサブブロックに分割する（処理ブロック２０４）。これを、ここでは４分木分割(quadtreeing)と言う。
【００７５】一実施例では、閾値処理の一環として、入力画像中に空間エッジが存在するか否かを判定するため、まず４×４画素ブロックを考え、４×４ブロック全体の入力平均を２×２サブブロックの平均と比較する。エッジが存在すると思われる場合には、各２×２ブロックごとに別々に一致する色を見つける。この閾値処理で認識可能なエッジがないと判定された場合には、その４×４ブロックは一括してカラー量子化される。一実施例では、このプロセスは１×１のブロックサイズが検討されるまで繰り返される。
【００７６】一実施例では、この閾値処理は、４×４ブロックの平均と各２×２ブロックの平均との間のユークリッド距離を用いて行われる。そのユークリッド距離が、４サブブロックのいずれかで閾値を越えるときに、その４×４ブロックは分割される。一般に、閾値処理はなんらかの色空間（例えば、ＲＧＢやその他の色空間）上の色値の関数を用いて行われる。閾値処理で、サブブロックの値を相互に比較してもブロック全体の値と比較してもよい。
【００７７】ブロックをそれ以上サブブロックに分割する必要がなくなり、かつ、そのような操作が以前行われなかったならば、処理ロジックは各入力ブロックの色平均Ａi を計算する（処理ブロック２０５）。一実施例では、各ブロックの色を示す値を生成するために、ブロック全体の算術平均（２Ｄハール(Haar)ウェーブレットと等価である）が用いられる。入力ドメインにおけるブロックの色平均を定義するために、他のウェーブレットや目のフィルタモデルを用いてもよく、また、別種の平均、例えば、幾何平均やＬ２平均を用いてもよい。さらに、直交座標上又は極座標などの他の空間座標上で平均を求めてもよい。
【００７８】次に、処理ロジックは、入力画像中のブロックの色平均と数学的に最もよく一致する出力ドメインの色セットを割り出す（処理ブロック２０６）。一実施例では、処理ロジックは、以下の距離尺度の式により表される出力色基本セットＢに関する整数係数βi を計算する。
【００７９】
【数１】
【００８０】この演算は、ｎ個の出力画素中の各画素に１つの色が割り当てられるよう制約条件がつけられる。すなわち、
【００８１】
【数２】
【００８２】ここで、”ｎ”は出力ブロック中の画素数であり、”ｂ”は出力色数である。入力画像中のブロックの平均を求めるために使用された同じ色平均方法を同様に用いることができる。このプロセスにより、入力ドメインの使用可能色と出力ドメインの使用可能色との間の距離が減少し、さらには最小化されるであろう。なお、様々な距離尺度、例えばユークリッド距離、マンハッタン距離、Ｌ１ノルム、Ｌ２ノルム、Ｌ∞ノルムなどを用いてもよい。
【００８３】最後に、所定の出力ブロックに対する出力色セットβi・Ｂが与えられると、処理ロジックは、その選択された色セットをブロック内に”モザイク状配置”することにより出力ドメインの画像を生成する（処理ブロック２０７）。一実施例では、処理ロジックは入力画像中の対応ブロックの色に最もよく一致し、かつ、空間的アーティファクトが減少し、できれは最少になるように試みる。所定の出力ブロックに対する出力色セットβi・Ｂが与えられた場合、そのブロック内の色配置が空間的アーティファクト及び知覚される色に大きく影響を及ぼす。一実施例では、視覚的に良好な結果を得るため、ランダムサンプリング、規則的グリッディング（gridding）、及び、青色ノイズ・ディザマトリクスによる色配置が、単独で使用されるか、適応的に切り替えて使用される。なお、処理ロジックによって、出力デバイス（例えばプリントエンジン）に対し選択された色セットを用紙上にどのように配置すべきか命令するために送られる指示が生成されるであろう。
【００８４】本プロセスは、例えばＲＧＢやＣＩＥＬＡＢなどの様々な色空間に適用可能である。
【００８５】本ブロック量子化技術は拘束条件付きの局所的色最適化を達成し、誤差拡散型のアーティファクトを生じない。色の一致、空間解像度及び色解像度については誤差拡散に劣らない。最小化問題の解を得ることが、本アルゴリズムの計算量の多い部分であるが、整数計画法、動的計画法、あるいはルックアップテーブルを利用することでスピードアップできる。例えば、単純ではあるがメモリ使用量の多いルックアップテーブルは、ブロックの色値を入力として受け取って、そのブロックのために使用すべき各出力色の画素数を返すであろう。例えば、モニタから４色プリンタまでの量子化の場合、入力ブロックが平均ＲＧＢ値（122, 33, 250）を有するものとする。この平均ＲＧＢ値が１６出力画素サイズのブロックのためのルックアップテーブルに入力される。ルックアップテーブルは、１３シアン、３マゼンタ、０イエロー、０ブラック及び０ホワイトを出力するであろう。また、近似解を見つけることによって本アルゴリズムをスピードアップすることができる。そのために、例えば、問題を逆行列で表して最大エントロピー法もしくは線形計画法で解いたり、近似ルックアップテーブルを利用することができる。あるいは、動的計画法で近似解を得ることができる。
【００８６】《空間フィルタ》ここに説明するブロック量子化技術のある実施例の目的は、局所的入力領域（例えばブロック）の平均色を対応した局所的出力領域の平均色に一致させることである。局所的領域の平均は、その局所的領域に対し空間フィルタを適用し、値に重み付けすることによって求めることができる。重み付けの一例を図６に示す。例えば、直交フィルタを用いることができる。この場合、領域内の画素は領域内の他の全ての画素と均等にカウントされる。
【００８７】入力ドメインの平均の計算及び／又は出力色セットの計算のために、非直交フィルタを用いることもできる。
【００８８】平均を求めるためにウェーブレットフィルタを用いることもできる。一実施例では、ハイパス・ウェーブレット成分がエッジの有無判定に利用されるであろう。このように、ハイパス・ウェーブレットフィルタが４分木閾値処理に利用される。
【００８９】算出される平均は使用色空間に依存する。様々な色空間を使用できる。色空間としては、RGB、CIELAB、CIELUV、Ohta、Opponent、log Opponent、HSV、 HUV、YCbCr があるが、これに限らない。
【００９０】入力領域及び出力領域の形状は、円形領域が好ましいであろう。略円形の形状から離れた形状は、一般に結果が好ましくない。
【００９１】領域のサイズは、目による平均化を前提とすることが妥当でなくなるほど大きくならないように選ばれる。領域が小さすぎると色解像度が制限される。領域が大きすぎると、空間的ディテールの解像能力の低下を招く。すなわち、目の平均化サイズの範囲内で色解像度と空間解像度の間にトレードオフの関係があり、どちらを無視してもディテール情報が損なわれる可能性がある。
【００９２】《出力色セットの選択》ｎ個の出力色の最適なセットをＢ個の可能色から見出す方法について以下に説明する。まず、Ｂ＝３個の可能色Ｊ，Ｋ，Ｌによって範囲が定められる２Ｄ色空間よりｎ＝３個の出力色を選ぶという簡単な問題について検討する。図３を参照すれば、ｘ記号は、ｎ個の選択出力色からなるセットとして可能な色JJJ，JJK，JKK．．．を示す。”アンカー”Ｊ，Ｋ，Ｌ間の距離の１／ｎの長さの２つのベクトルJK,JLを定義することができる。これらベクトルJk，JLは２Ｄ色空間を張るベクトル基底をなす。
【００９３】ベクトル基底のグラム-シュミット(Gram-Schmidt)直交化法を用いて、直交ベクトル基底を求めることができる。任意の入力ターゲット色点を、原点Ｊより同ターゲット色点へ向かうベクトルと考えることができる。このＪターゲットベクトルを直交基底上へ分解し、元のJX，JLベクトルの係数として再構成することができる。これら２つの係数は、何個の出力色をＫとし、何個の出力色をＬとするか指定する（故に出力色セット中の残余の色はＪとする）。グラム-シュミット手順の結果、ｎ色はターゲットに到達するＪ，Ｋ，Ｌに正確に分解される。ただし、整数解のみ用いればよい。よって、一実施例では、最も近い整数解が出力色セットとして選ばれる。
【００９４】３Ｄ色空間の場合、Ｂを４色以上とし、同じベクトル手法によりｎ個の出力色を求めることができる。しかし、３Ｄで５色以上又は２Ｄで４色以上の場合、ベクトル基底は冗長である（例えば、ターゲットを元のベクトル上へ正確に分解するという問題は劣決定であるので多くの解があるが、正確な整数解があるとは限らない）。
【００９５】５色以上の場合、１つの解法は、とり得る各々の整数個の第５色０〜ｎを考え、（ターゲット平均−第５色寄与分）を残りの４色へ分解することである。したがって、５色の場合には、その４色の解が見つかる。ターゲット色が出力インクにより形成される凸包から外れていない限り、近い整数解が一般に見つかる。
【００９６】入力ターゲット色と一致する適切な出力色セットを見つけるために線形計画法を利用できる。線形計画法はターゲット色と出力色平均との差を減少させ、さらには最小化させる解を探索するが、その減少（最小化）後の差がユークリッド距離（Ｌ２ノルムの２乗に等しい）となることはない。むしろ、線形計画法はＬ１もしくは上限ノルムを減らすのである。ユークリッド距離を減少させ、さらには最小化させるために二次計画法を利用できる。
【００９７】出力色セットの選択プロセスのスピードアップのためにテーブル検索を利用できる。テーブル検索は、例えばプリンタの場合のように、出力色が予め分かっている場合の選択に特に有利である。一実施例では、そのＬＵＴは可能性のあるすべての入力色に対応したメモリセルを有する。別の実施例では、そのＬＵＴは、異なる複数の出力色セットを持つようにプログラムされ、かつ／又は、１つの入力色によって、その最も近い出力色が求まる。このようにすると、メモリは少なくて済むが必要処理量は増加し、また、不正確な答を出すことがある。
【００９８】一実施例では、色空間は予め定量化可能なセルに分割される。所定のセルに含まれる全ての入力平均は、そのセルの中心点に定量化される。
【００９９】前述のように、一実施例では、入力ベクトル色平均が与えられると、その入力平均と選択される出力色セットとのユークリッド距離を減少もしくは最少化するように出力色セットが選択される。別の実施例では、マンハッタン距離もしくは成分毎の最大値を減少させ、さらには最小化するであろう。
【０１００】前述のように、入力色セット及び選択された出力色セットの平均が求められ、そのユークリッド距離が減少させられる（また最少化されるかもしれない）。各ブロックごとに平均を算出するのではなく、ある距離尺度（例えばＥＭＤ（Earth Mover's Distance））を使用して入力ブロック、予定出力色間の距離を測定してもよい。一実施例では、ＥＭＤを使用して、いくつかの可能性のあるものの中から、やや高速の出力セット・ジェネレータで迅速に生成できるものが選択される。ＥＭＤに関するこれ以上の情報を知るには、「Rubnex, Tomasi,Goibas,ICCV 1998」を参照されたい。
【０１０１】《出力色のモザイク状配置》出力色セットが選択されたとしても、それら出力色を出力空間にどのように配置するか決定する課題が残っている。例えば、Ｒ３画素とＧ３画素をRRRGGGのように配置するのとRGRGRGのように配置するのとでは、知覚される色、粒状性、及び、擬似輪郭に違いが生じるであろう。モザイク状配置の方法は、例えば、規則的グリッディング(gridding)、（置換有りと置換無しの）ランダムサンプリング、青色ディザマトリクスの値を用いて選択出力画素を並べるなど、多くの異なる方法を使用できる。規則的グリッディングは、２つのやり方で行うことができる。１つのやり方は、ある特定の出力色の画素全部を一斉にブロック内に配置し、次いで２つ目の出力色の画素全部を一斉にブロック内に配置し、以下同様に行う方法である。例えば、Ｒの８画素とＧの８画素はRRRRRRRRGGGGGGGGのようになろう。この方法は孤立色が発生しない。もう１つの実施例では、できるだけ互い違いにする規則的グリッディングが用いられる。この方法は、よく混合した画像を得られる。この場合、Ｒの８画素とＧの８画素はRGRGGRGRRGRGGRGRとなる。
【０１０２】ブロックのモザイク状配置のもう１つの方法はランダムサンプリングである。Ｒ８画素、Ｇ８画素をブロックに配置するとして、出力ブロックの各画素ごとに分布がランダムにサンプリングされるが、置き換えは行われるか又は行われない。しかし、この方法はざらついた感じの画像になりやすい。
【０１０３】モザイク状配置のための視覚的に好ましい方法は、選択された出力色を青色空間周波パターンに配置する方法である。そのための１つの方法は、当該目的用に作成したディザマトリクスを選択することである。出力色は、何らかの順に、例えば輝度順に配列される。例えば、出力色をＷＹＣＭＫとする。Ｋは黒である。この場合、選択された出力色をディザの順に配置する。図５に一例を示す。４×４ディザマトリクスが図５（ａ）のようだとすると、選択された出力色セットは図５（ｂ）のマトリクスのようになる。
【０１０４】所定のブロックより大きなディザマトリクスを用いてもよく、その場合には、ブロックはそれがカバーする値の順序たけを利用する。
【０１０５】（閾値処理に関連して前述したようにブロックが分割されていない時に）ブロックのサブブロックの平均により良く一致させようと試みる決定論的方法又は確率的方法によって、全ての解像度で一層良く平均を表現すことができる。４×４ブロックの場合、１６の出力色が選ばれた後に、各２×２サブブロックの平均に基づいて、それら出力色を４つの４色グループに分ければよい。
【０１０６】《応用例》一実施例では、複写機やプリンタなどのシステム内の組み込みプロセッサによって本ブロックカラー量子化が実行される。そのアルゴリズムは特定用途向け集積回路（ＡＳＩＣ）に実装されるであろう。図４は、前述したブロック量子化技術のための処理を組み込むことができるシステムの一例を示すブロック図である。
【０１０７】図４を参照すれば、システム４００は情報処理のための組み込みプロセッサ４１２を有する。システム４００は、さらに、情報と組み込みプロセッサ４１２により実行される命令を格納するための、組み込みプロセッサ４１２に接続されたランダムアクセスメモリ（ＲＡＭ）又は他の動的記憶装置４０４を有する。
【０１０８】コンピュータシステム４００は、システムのユーザに情報を表示するための陰極線菅（ＣＲＴ）や液晶ディスプレイ（ＬＣＤ）などの、組み込みディスプレイ４１２に接続されたディスプレイ装置４２１も有するであろう。組み込みプロセッサ４１２に情報及びコマンド選択を伝えるために、英数字キー及び他のキーを有する英数字入力装置も装備されるであろう。
【０１０９】これ以外のユーザ入力装置は、マウス、トラックボール、トラックパッド、スタイラス、カーソル方向キーなどのカーソル制御装置であり、方向情報及びコマンド選択をプロセッサ４１２に伝えたりディスプレイ４２１上のカーソルの動きを制御するためにシステムに組み込まれるであろう。
【０１１０】プリントエンジン４２４が組み込みプロセッサ４１２に接続されている。一実施例では、このプリントエンジン４２４は複写機の一部である。システム４００の前記要素の任意の要素又は全要素と関連ハードウェアを本発明に利用し得ることに注意されたい。ただし、システムの他の構成でも以上の装置の一部又は全部を含んでもよいことは明らかであろう。
【０１１１】以上の説明を読めば本発明の多くの変更及び修正が当業者には明白となろうから、以上に図示及び記述したどの実施例も説明を目的としたものであって、限定を意図したものと解すべきでない。
【０１１２】
【発明の効果】以上、詳細に説明したように、本発明によれば、拘束条件付きの局所的色最適化を行って、誤差拡散と同様の色の一致、空間解像度及び色解像度を達成するとともに誤差拡散につきもののアーティファクトの発生を防止することができ、また、整数計画法、動的計画法又はルックアップテーブルを利用することで処理のスピードアップを達成できる、等々の効果を得られるものである。
【図面の簡単な説明】
【図１】中間調処理のためのブロック量子化システムの一実施例のブロック図である。
【図２】ブロック量子化を中間調処理と同時に実施するプロセスの一実施例の流れ図である。
【図３】可能な色セットの説明図である。
【図４】ブロック量子化処理機能を有するシステムの一実施例のブロック図である。
【図５】ディザマトリクスによる出力色セットの配置例の説明図である。
【図６】重み付けの一例を示す図である。
【符号の説明】
１０２ ブロック生成・色平均ユニット
１０３ ブロックサイズ適応調整ユニット
１０４ 色合わせ・配置ユニット
【０００１】
【発明の属する技術分野】本発明は、カラー中間調処理(halftoning)の分野に係り、特に、カラー中間調処理へのブロック量子化技術の応用に関する。
【０００２】
【従来の技術】カラー中間調処理は、多ビット（例えば２４ビット）の画像を、少数の色だけを用いた、場合によって空間解像度を上げた画像として表現しようとするものである。これは多くのカラープリンタで直面する課題である。一般にカラープリンタは、例えば、シアン、マゼンタ、イエロー、黒、白と、それらの組み合わせであるシアン＋マゼンタ、シアン＋イエロー、マゼンタ＋イエローのような、５色又は８色だけしか使用できない。
【０００３】カラー中間調処理アルゴリズムの評価は、視覚の主観性のせいで困難な場合がある。中間調処理アルゴリズムにおける特有の目標として、色が一致すること、計算が単純であること、粒状性が低いこと、アーティファクト(artifact)をできるだけ少なくすること、後処理による影響を低減することがある。これら各目標の相対的な重要性は、観察者、予定観察距離、対象画像により左右される。
【０００４】色の一致には少なくとも２つの目標、すなわち、個々の入力色と出力色が近いこと、及び、誤差のばらつきがないことがある。計算の課題には、実行速度、並列処理の容易性、メモリ容量、複雑さがある。粒状性は、別々の出力色を（それらの色が完全に混じり合わずに）知覚できる能力として説明することができる。知覚される粒状性はｄｐｉといくぶん相関がある。
【０００５】空間解像度が悪いか色解像度が悪いと（又はその両方が悪いと）、ディテール情報が失われるであろう。アーティファクトは、スペックル(speckle)、縞模様(steak)、ゴースト、グリッディング(gridding)、テクスチャ、それと非常に重要な擬似輪郭（バンディングとしても知られている）など、アルゴリズムの結果で好ましくない現象を表す一般用語である。
【０００６】中間調処理画像は、中間調処理された時点で”完成した”とは限らないので、後処理の影響は重要な問題である。その画像に対し、圧縮のためのダウンサンプリングからエッジ強調まで様々な画像処理操作がさらに行われることがある。中間調処理アルゴリズムは、これら操作の成否、容易さを左右することがある。
【０００７】中間調処理のための技術は、ディザ法、誤差拡散法、反復法など様々なものが考案されている。殆どのカラー中間調処理技術は、白黒中間調処理技術を単純に３つの色プレーンの各々に対し別個に拡張して適用する。このようなコンポーネント別に拡張する方法は、計算の面では効率的ではあるが、インク色の数学的線形性を前提としている。しかし、印刷における減法混色は非線形であるため、プレーン別の中間調処理方法は最善の方法ではない。
【０００８】ディザは、擬似乱数の２次元周期信号を画像の各色成分に加算してから、各画素を最も近い出力色に量子化する構成である。ディザの信号は、見た目には混じり合って見える、交互に色が変化するパターンを生成するように作られる。異なるタイプのディザとして、ドット集中型ディザ、ドット分散型ディザ、ドット順序型ディザがある。白色ノイズを用いるディザは、組織的ディザほどには視覚的に良好な結果を得られない。ディザは、周期的パターンが目立つという欠点を有することが知られている。ディザを改良するために様々な取り組みがなされている。カラーへのディザの応用は当該技術分野で知られている。これ以上の情報を知るには「A.Karun, et al., "New Methods for Dithering of Color lmages,"Proc. of the IEEE Workshop on Nonlinear Signal/lmage Processing, 1995」を参照されたい。
【０００９】ディザは局所的処理（すなわち、各画素の出力は、その入力画素と、おそらくはディザ信号のような外的要因にのみに依存する）であるのに対し、誤差拡散は、各画素位置での量子化誤差を、誤差の一部を各前進方向へ送る方向性空間フィルタに基づいて、近傍画素へ拡散させる。結果として、誤差拡散による中間調処理は高周波ノイズを加える。目で色が混じり合って実際の色モザイクに気付かないようにすることが目標であるので、この誤差拡散のハイパスフィルタ効果は目が高周波ノイズを知覚しにくいことを利用する。すなわち、誤差拡散は青色空間スペクトルを生じる。青色ノイズのほうが視覚的に好ましいという考えは十分確立したものである。
【００１０】誤差拡散は有効に作用するが、いくつか欠点がある。誤差拡散は、局所的に最適化する、つまり、各画素の位置で最善を尽くすという点で欲張りなアルゴリズムである。誤差は前方へ拡散されるので、誤差拡散は方向性があり、局所領域全体にわたって真の同時最適化はできない。目が色を平均化している局所の外へ誤差が拡散されることがある。誤差拡散のアーティファクトとして、ある程度のスペックル、縞模様、過渡的なエッジ効果及びグリッディング効果がある。誤差拡散のために必要なフィードバックループが、アルゴリズムの並列実行の障害になることがある。
【００１１】誤差拡散の改良が長年にわたって行われてきた。構造的アーティファクトの低減、フィードバック・フィルタの適応化、ニューラルネットワークの利用というような方向で努力がなされてきた。
【００１２】また、知覚モデルとプリンタ・モデルを用いる優れた白黒中間調処理技法があるが、これらはカラー中間調処理のためには複雑な拡張が必要である。
【００１３】平均マッチングの考え方を考慮した別の白黒アルゴリズムもある。例えば、ある多重解像度中間調処理アルゴリズムは、元の画像の解像度よりスタートし、出力画像の平均グレーレベルを入力画像の平均グレーレベルと等しくする。次に、１つ上のレベルの解像度では、平均グレーレベルを４象限間で各象限の平均グレーレベルに基づいて比例的に分配する。この過程は、各画素が黒又は白に量子化される解像度レベルまで繰り返される。例えば、「Breaux, et al., "WaveletMethods for Compression, Rendering, and Descreening in DigitalHalftoning," SPIE vol. 3078,1997」、「P.W.Wong, "Halftoning byMultiscale Dot Distribution,"Proc. IEEE Int. Conference on lmageProcessing, Vol. III, 1995」、「P.W. Wong,"Mean matching Halftoning ona Rotated Quad-tree Structure," Human Vision and Electronic lmaging," Proc. SPIE 2657, 1996」を参照されたい。
【００１４】もう１つの従来技術の方法では、入力画像と出力画像の平均グレーレベルがいくつかの解像度で生成される。さらに別の従来技術では、ウェーブレット平均を計算し、次に、ディザを利用して、これらの平均グレーレベルを近似する。より具体的には、まず画像をウェーブレットを用いて圧縮し、次いで、各レベルごとに、ウェーブレット係数を平均グレーレベルとして用いることにより白ドットを４象限内でどのように分配すべきか決定する。この手法は、画素レベルまでは達しないため、選択した数の白ドットを、ドット集中型ディザ又はドット分散型ディザを利用して配列する。それらの結果には、水平方向及び垂直方向のアーティファクトと擬似輪郭が生じる欠点がある。
【００１５】
【発明が解決しようとする課題】本発明は、以上に述べた従来技術の問題点に鑑み、ブロック量子化を応用する新規なカラー中間調処理方法及び装置を提供することを目的とする。
【００１６】
【課題を解決するための手段】請求項１記載のカラー中間調処理方法の特徴は、入力画像及び出力画像をブロックに分割するステップ、ここにおいて出力画像の各ブロックは入力画像の１つのブロックに対応する；各入力ブロックの色平均を計算するステップ；出力画像の各ブロックのための出力色セットを入力画像の対応ブロックの色平均に一致するように計算するステップ；及び、出力画像の各ブロックにおける出力色セットの配置を制御するための指示を生成するステップを有することである。
【００１７】請求項２記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、特定の条件が満たされるときに、それぞれの入力ブロック及び出力ブロックをサブブロックに分割するステップをさらに有することである。
【００１８】請求項３記載のカラー中間調処理方法の特徴は、請求項２記載の構成において、ブロックをサブブロックに分割するための特定の条件とは、そのブロックがエッジを含んでいるかどうかであることである。
【００１９】請求項４記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、ブロックの特性はブロックに関連した色を人間の目が平均化するようなものであることである。
【００２０】請求項５記載のカラー中間調処理方法の特徴は、請求項４記載の構成において、ブロックの特性はサイズ、形状及び想定観察距離の中の１つ以上を含むことである。
【００２１】請求項６記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットの計算は、色空間上で表現可能な値を調べ、対応した入力ブロックの色平均に最も近い表現可能値を見つけることにより行われることである。
【００２２】請求項７記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットの計算に、同セット中の出力色を決定するために平均色に関するルックアップテーブルを利用することである。
【００２３】請求項８記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットの計算に整数計画法を利用することである。
【００２４】請求項９記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットの計算に動的計画法を利用することである。
【００２５】請求項１０記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットの計算に近似線形計画法を利用することである。
【００２６】請求項１１記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットの計算に近似最大エントロピー法を利用することである。
【００２７】請求項１２記載のカラー中間調処理方法の特徴は、請求項２記載の構成において、ブロックをサブブロックへ分割するステップは、各ブロックごとに、及び、そのブロックの複数のサブブロックの各々ごとに色値の関数を計算するステップ、ブロックとサブブロックの色値の関数間の距離が閾値より大きいか判定するステップ、及び、その距離が閾値より大きいときにブロックをサブブロックに分割するステップからなることである。
【００２８】請求項１３記載のカラー中間調処理方法の特徴は、請求項１２記載の構成において、各サブブロックについての色値の関数を、そのブロックの他のサブブロックについての関数値と比較することによりエッジの存在を判定するステップをさらに有することである。
【００２９】請求項１４記載のカラー中間調処理方法の特徴は、請求項１２記載の構成において、複数のサブブロックは４個のサブブロックからなることである。
【００３０】請求項１５記載のカラー中間調処理方法の特徴は、請求項１記載の構成において、出力色セットが与えられたならば、ターゲット色に一致するように、かつ空間的アーティファクトを減らすように各ブロック内に色を配置するステップをさらに有することである。
【００３１】請求項１６記載のカラー中間調処理方法の特徴は、請求項１５記載の構成において、各ブロック内の色配置で規則的グリッディングを行うことである。
【００３２】請求項１７記載のカラー中間調処理方法の特徴は、請求項１５記載の構成において、各ブロック内の色配置で、選択された出力色をディザマトリクスに従って配置することである。
【００３３】請求項１８記載のコンピュータ読み取り可能な記録媒体の特徴は、請求項１乃至１７のいずれか１項記載のステップをコンピュータに実行させるための実行可能命令が記録されたことである。
【００３４】請求項１９記載のカラー中間調処理装置の特徴は、入力画像及び出力画像をブロックに分割するディバイダ、ここにおいて出力画像の各ブロックは入力画像の１つのブロックに対応する；各入力ブロックの色平均を計算する第１のロジック；出力画像の各ブロックのための出力色セットを入力画像の対応ブロックの色平均に一致させるように計算する第２のロジック；及び、出力画像の各ブロックにおける出力色セットの配置を制御するための指示を生成する指示生成ロジックを有することである。
【００３５】請求項２０記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、前記ディバイダは、特定の条件が満たされるときに、それぞれの入力ブロック及び出力ブロックをサブブロックに分割することである。
【００３６】請求項２１記載のカラー中間調処理装置の特徴は、請求項２０記載の構成において、ブロックをサブブロックに分割するための特定の条件とは、そのブロックがエッジを含んでいるかどうかであることである。
【００３７】請求項２２記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、ブロックの特性はブロックに関連した色を人間の目が平均化するようなものであることである。
【００３８】請求項２３記載のカラー中間調処理装置の特徴は、請求項２２記載の構成において、ブロックの特性はサイズ、形状及び想定観察距離の中の１つ以上を含むことである。
【００３９】請求項２４記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットを計算する第２のロジックは、色空間上で表現可能な値を調べ、対応した入力ブロックの色平均に最も近い表現可能値を見つけることである。
【００４０】請求項２５記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットを計算する第２のロジックは、同セット中の出力色を決定するために平均色に関するルックアップテーブルを利用することである。
【００４１】請求項２６記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットを計算する第２のロジックは整数計画法を利用することである。
【００４２】請求項２７記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットを計算する第２のロジックは動的計画法を利用することである。
【００４３】請求項２８記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットを計算する第２のロジックは近似線形計画法を利用することである。
【００４４】請求項２９記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットを計算する第２のロジックは近似最大エントロピー法を利用することである。
【００４５】請求項３０記載のカラー中間調処理装置の特徴は、請求項２０記載の構成において、各ブロックごとに、及びそのブロックの複数のサブブロックの各々ごとに色値の関数を生成する計算ロジック、ブロックとサブブロックの色値の関数間の距離が閾値より大きいか判定する判定ロジック、及び、その距離が閾値より大きいときにブロックをサブブロックに分割するディバイダをさらに有することである。
【００４６】請求項３１記載のカラー中間調処理装置の特徴は、請求項３０記載の構成において、各サブブロックについての色値の関数を、そのブロックの他のサブブロックについての関数値と比較することによりエッジの存在を判定する判定ロジックをさらに有することである。
【００４７】請求項３２記載のカラー中間調処理装置の特徴は、請求項３０記載の構成において、複数のサブブロックは４個のサブブロックからなることである。
【００４８】請求項３３記載のカラー中間調処理装置の特徴は、請求項１９記載の構成において、出力色セットが与えられたときに、ターゲット色に一致するように、かつ空間的アーティファクトを減らすように各ブロック内に色を配置する制御ロジックをさらに有することである。
【００４９】請求項３４記載のカラー中間調処理装置の特徴は、請求項３３記載の構成において、制御ロジックは各ブロック内において規則的グリッディングを行うことである。
【００５０】請求項３５記載のカラー中間調処理装置の特徴は、請求項３３記載の構成において、制御ロジックは各ブロック内に選択された出力色をディザマトリクスに従って配置することである。
【００５１】請求項３６記載のカラー中間調処理装置の特徴は、入力画像及び出力画像をブロックに分割する手段、ここにおいて出力画像の各ブロックは入力画像の１つのブロックに対応する；各入力ブロックの色平均を計算する手段；出力画像の各ブロックのための出力色セットを入力画像の対応ブロックの色平均に一致するように計算する手段；及び、出力画像の各ブロックにおける出力色セットの配置を制御するための指示を生成する手段を有することである。
【００５２】請求項３７記載のカラー中間調処理方法の特徴は、入力画像及び出力画像をブロックに分割するステップであって、エッジを含むブロックのサイズを適応的に変更してエッジを含まない複数のブロックを生成するステップを含むステップ、及び、入力画像の対応ブロックの色平均を最もよく表現する出力色セットを計算するステップを有することである。
【００５３】請求項３８記載のカラー中間調処理方法の特徴は、請求項３７記載の構成において、入力画像の色域は出力画像の色域に合わせるため予め調整されることである。
【００５４】請求項３９記載のカラー中間調処理装置の特徴は、入力画像及び出力画像をブロックに分割する手段であって、エッジを含むブロックのサイズを適応的に変更してエッジを含まない複数のブロックを生成する手段を含む手段、及び、入力画像の対応ブロックの色平均を最もよく表現する出力色セットを計算する手段を有することである。
【００５５】請求項４０記載のカラー中間調処理装置の特徴は、請求項３９記載の構成において、入力画像の色域は出力画像の色域に合わせるため予め調整されることである。
【００５６】請求項４１記載のカラー中間調処理装置の特徴は、エッジを含むブロックのサイズを適応的に変更してエッジを含まない複数のブロックを生成することにより入力画像及び出力画像をブロックに分割するディバイダ、及び、入力画像の対応ブロックの色平均を最も良く表現する出力色セットを計算する計算ロジックを有することである。
【００５７】
【発明の実施の形態】ブロック量子化方法及び装置について説明する。以下の説明において、多くの詳細事項が提示される。ただし、これら特定の詳細事項によらずに本発明を実施し得ることは当業者には明らかであろう。他方、本発明を難解にしないため、周知の構造及び素子はブロック図により示し詳細は示さない。
【００５８】以下の詳細な説明中に、コンピュータのメモリ内のデータビットに対する操作のアルゴリズム及び記号表現によって表された部分がある。このようなアルゴリズム記述及び表現は、データ処理技術の当業者が研究内容を他の当業者に最も効率的に伝えるために用いる手段である。あるアルゴリズムがあり、それが概して期待した結果に至る筋の通ったステップの系列だと理解されるとする。それらのステップは、物理量の物理的処理を要するステップである。必ずという訳ではないが、これらの物理量は記憶、転送、結合、比較、その他処理が可能な電気的または磁気的信号の形をとるのが普通である。これらの信号をビット、値、要素、記号、文字、術語、番号などで表わすのが、主に慣用上の理由から便利な場合があることが分かっている。
【００５９】ただし、このような術語や同様の用語はすべて適切な物理量と関連付けられるべきであり、また、それら物理量に付けた便宜上のラベルに過ぎないということに留意すべきである。以下の説明より明らかなように、特に断わらない限り、”処理”、”演算”、”計算”、”判定”、”表示”などの用語によって論じられることは、コンピュータシステムのレジスタ及びメモリの内部の物理的（電子的）な量として表現されたデータを処理して、コンピュータシステムのメモリやレジスタ、その他同様の情報記憶装置、情報伝送装置又は情報表示装置の内部の同様に物理量として表現された他のデータへ変換する、コンピュータシステムや同様の電子的演算装置の作用及びプロセスを意味する。
【００６０】本発明は、本明細書に述べる処理を実行するための装置にも関係するものである。このような装置は、所要目的のために専用に作られてもよいし、汎用コンピュータを内蔵のコンピュータ・プログラムによって選択駆動もしくは再構成したものでもよい。そのようなコンピュータ・プログラムは、コンピュータが読み取り可能な記憶媒体、限定するわけではないが例えば、フロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスクなどの任意種類のディスク、リードオンリーメモリ（ＲＯＭ）やランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード又は光カードなど、コンピュータのシステムバスに接続された電子的命令の記憶に適した任意種類の媒体に格納することができる。
【００６１】本明細書に提示されるアルゴリズム及び表示は、本質的に、いかなる特定のコンピュータ、その他の装置とも関わりがない。様々な汎用マシンを、本明細書に述べた内容に従ったプログラムで利用し得るが、所要の手順のステップの実行のために、より特化した装置を作るほうが好都合であるかもしれない。そのような多様なシステムに必要な構造は以下の説明から明らかになろう。また、いかなる特定のプログラミング言語とも関連付けることなく本発明を説明する。本明細書に述べる本発明の内容を実現するために様々なプログラミング言語を使用し得ることは明らであろう。
【００６２】機械読み取り可能媒体は、機械（例えばコンピュータ）が読み取ることができる形式で情報を記録するための任意の機構を包含する。例えば、機械読み取り可能媒体には、リードオンリーメモリ（ＲＯＭ）；ランダムアクセスメモリ（ＲＡＭ）；磁気ディスク記憶媒体；光記憶媒体；フラッシュメモリ素子などが含まれる。
【００６３】《ブロックカラー量子化を利用したカラー中間調処理の概要》本発明は、入力ブロックのサイズが適応的に調整されるブロック量子化を利用してカラー中間調処理を行う。図１は、カラー中間調処理のためのブロック量子化システムの一実施例のブロック図である。本ブロック量子化システムは、その入力ドメインと出力ドメインの間で色合わせを行って、入力ドメインの色数が出力ドメインの使用可能色数より多い場合のカラー中間調処理を実現する。本ブロック量子化システムは、入力ドメイン及び出力ドメインの画像を複数ブロックに分割し、入力ドメインの画像の各ブロックの色平均を出力ドメインの画像の１つのブロックの色平均に一致させることによって色合わせを行う。ブロックは任意の形状でよく、２つ以上の形状を組み合わせた複雑な形状でもよい。例えば、ブロックは正方形（ｄ×ｄ）でもよいが、長方形（ｄ×ｂ）（ただし、ｄ≠ｂ）でもよい。
【００６４】一実施例では、入力ドメインはモニタを有するコンピュータシステムからなり、出力ドメインはプリンタからなる。ここで説明するブロック量子化技術は、入力画像の各小ブロックごとに、その色平均を最適に（一実施例では適切な距離基準による）表現する対応出力ブロックの印刷色セットを計算する。このようにして、ここに説明する中間調処理技術によれば、局所的入力領域毎に、その平均色を対応した局所的出力領域の平均色と確実に一致させるが、それら領域は目で確実に平均化されるような十分小さな領域である。本ブロック量子化技術は、印刷プロセスの高い空間解像度を利用して色解像度を向上させ、制限条件付きの局所的色最適化を達成する。誤差拡散法につきもののスペックル、テクスチャ、その他のアーティファクトの発生はほぼ防止される。
【００６５】本技術は、各入力色を色空間上の３次元（３Ｄ）ベクトルとして扱い、そして一実施例では、減法混色印刷プロセスで得られる実際の出力色を使用して中間調を生成する。
【００６６】図１において、入力画像１０１はブロック生成・色平均ユニット１０２に受け取られ、同ユニットは入力画像１０１をブロックに分割し、各ブロックの平均色値を生成する。一実施例では、ブロックは固定サイズである。
【００６７】ブロック生成・色平均ユニット１０２は、各ブロックを、それにエッジが含まれるときにサブブロックに再分割するブロックサイズ適応調整ユニット１０３を有する。一実施例では、そのサブブロック数は４であるが、任意の数のサブブロックを用いてもよい。ブロックサイズ適応調整ユニット１０３は、すべてのブロックについて、どのブロックにもエッジが含まれなくなるまで、あるいは何らかの他の特定の条件が満たされるまで、個々のブロック（固定サイズでよい）のサブブロックへの再分割を繰り返して行うであろう。別の実施例では、１つ、２つ以上、あるいは全てのブロックにエッジが含まれていたとしてもサブブロックへは分割されないであろう。一実施例では、エッジを含むブロックは、例えば、それを分割すると色解像度の低下を招く場合にはサブブロックに分割されないであろう。なお、このような実施例はフィードバックが必要となるが、このフィードバックは本発明を難解にしないため図１には示されていない。
【００６８】一実施例では、各ブロックにエッジが含まれているか判定するため、ブロックの平均ベクトル色値が計算され、そのブロックの複数の（例えば４個の）サブブロックの平均と比較される。ブロックとサブブロックの平均との差がある閾値を越えるときに、そのブロックはエッジを含むと判定されてサブブロックに再分割される。これはブロックが所定サイズになるまで繰り返されるであろう。例えば、最初に４×４画素ブロックを用いる場合には、ブロックサイズ適応調整はブロックが１×１画素ブロックになるまで繰り返されるであろう。
【００６９】目標値としての入力ブロックの色平均が与えられると、色合わせ・配置ユニット１０４は、平均するとその目標値に可能な限り近い値となる出力色セットを計算する。一実施例では、色合わせ・配置ユニット１０４は、出力画像の色空間上で実現可能な値を調べ、目標に可能な限り近い値を割り出すことによって、出力色セットを計算する。
【００７０】出力色セットが求まると、色合わせ・配置ユニット１０４は、所望の色を得るとともにアーティファクト及び粒状性を減少させ、できれば最小にするように色を配置する。
【００７１】図２は、ここに説明するブロック量子化技術の処理手順の一例を示す流れ図である。このプロセスを実行する処理ロジックは、ハードウェア、ソフトウェア、両者の組み合わせのいずれで構成してもよい。
【００７２】図２を参照すると、プロセスの最初に、処理ロジックは、入力ドメインにおいて目で全体を平均化できるようなブロック・サイズを選択する（処理ブロック２０１）。一実施例では、ブロックのサイズは正方形（ｄ×ｄ）である。別の実施例では、ブロックのサイズは正方形ではない（例えば、長方形、菱形など）。
【００７３】次に、処理ロジックは入力画像及び出力画像を対応したブロックに分割する（処理ブロック２０２）。各入力ブロックに対し、対応する１つのｎ画素の出力ブロックがある（ここで、ｎは出力空間解像度と入力ブロックのサイズによって決まる）。
【００７４】次に、処理ロジックは各ブロックの内部にエッジが存在するか判定する（処理ブロック２０３）。ブロック内のエッジの存在を判定する方法はいろいろある。前述のように、一実施例では、ブロックの色平均とそのサブブロックの色平均の差がある閾値を越える場合にエッジが存在している。エッジがある場合には、処理ロジックは、そのブロックをエッジを含まないサブブロックに分割する（処理ブロック２０４）。これを、ここでは４分木分割(quadtreeing)と言う。
【００７５】一実施例では、閾値処理の一環として、入力画像中に空間エッジが存在するか否かを判定するため、まず４×４画素ブロックを考え、４×４ブロック全体の入力平均を２×２サブブロックの平均と比較する。エッジが存在すると思われる場合には、各２×２ブロックごとに別々に一致する色を見つける。この閾値処理で認識可能なエッジがないと判定された場合には、その４×４ブロックは一括してカラー量子化される。一実施例では、このプロセスは１×１のブロックサイズが検討されるまで繰り返される。
【００７６】一実施例では、この閾値処理は、４×４ブロックの平均と各２×２ブロックの平均との間のユークリッド距離を用いて行われる。そのユークリッド距離が、４サブブロックのいずれかで閾値を越えるときに、その４×４ブロックは分割される。一般に、閾値処理はなんらかの色空間（例えば、ＲＧＢやその他の色空間）上の色値の関数を用いて行われる。閾値処理で、サブブロックの値を相互に比較してもブロック全体の値と比較してもよい。
【００７７】ブロックをそれ以上サブブロックに分割する必要がなくなり、かつ、そのような操作が以前行われなかったならば、処理ロジックは各入力ブロックの色平均Ａi を計算する（処理ブロック２０５）。一実施例では、各ブロックの色を示す値を生成するために、ブロック全体の算術平均（２Ｄハール(Haar)ウェーブレットと等価である）が用いられる。入力ドメインにおけるブロックの色平均を定義するために、他のウェーブレットや目のフィルタモデルを用いてもよく、また、別種の平均、例えば、幾何平均やＬ２平均を用いてもよい。さらに、直交座標上又は極座標などの他の空間座標上で平均を求めてもよい。
【００７８】次に、処理ロジックは、入力画像中のブロックの色平均と数学的に最もよく一致する出力ドメインの色セットを割り出す（処理ブロック２０６）。一実施例では、処理ロジックは、以下の距離尺度の式により表される出力色基本セットＢに関する整数係数βi を計算する。
【００７９】
【数１】
【００８０】この演算は、ｎ個の出力画素中の各画素に１つの色が割り当てられるよう制約条件がつけられる。すなわち、
【００８１】
【数２】
【００８２】ここで、”ｎ”は出力ブロック中の画素数であり、”ｂ”は出力色数である。入力画像中のブロックの平均を求めるために使用された同じ色平均方法を同様に用いることができる。このプロセスにより、入力ドメインの使用可能色と出力ドメインの使用可能色との間の距離が減少し、さらには最小化されるであろう。なお、様々な距離尺度、例えばユークリッド距離、マンハッタン距離、Ｌ１ノルム、Ｌ２ノルム、Ｌ∞ノルムなどを用いてもよい。
【００８３】最後に、所定の出力ブロックに対する出力色セットβi・Ｂが与えられると、処理ロジックは、その選択された色セットをブロック内に”モザイク状配置”することにより出力ドメインの画像を生成する（処理ブロック２０７）。一実施例では、処理ロジックは入力画像中の対応ブロックの色に最もよく一致し、かつ、空間的アーティファクトが減少し、できれは最少になるように試みる。所定の出力ブロックに対する出力色セットβi・Ｂが与えられた場合、そのブロック内の色配置が空間的アーティファクト及び知覚される色に大きく影響を及ぼす。一実施例では、視覚的に良好な結果を得るため、ランダムサンプリング、規則的グリッディング（gridding）、及び、青色ノイズ・ディザマトリクスによる色配置が、単独で使用されるか、適応的に切り替えて使用される。なお、処理ロジックによって、出力デバイス（例えばプリントエンジン）に対し選択された色セットを用紙上にどのように配置すべきか命令するために送られる指示が生成されるであろう。
【００８４】本プロセスは、例えばＲＧＢやＣＩＥＬＡＢなどの様々な色空間に適用可能である。
【００８５】本ブロック量子化技術は拘束条件付きの局所的色最適化を達成し、誤差拡散型のアーティファクトを生じない。色の一致、空間解像度及び色解像度については誤差拡散に劣らない。最小化問題の解を得ることが、本アルゴリズムの計算量の多い部分であるが、整数計画法、動的計画法、あるいはルックアップテーブルを利用することでスピードアップできる。例えば、単純ではあるがメモリ使用量の多いルックアップテーブルは、ブロックの色値を入力として受け取って、そのブロックのために使用すべき各出力色の画素数を返すであろう。例えば、モニタから４色プリンタまでの量子化の場合、入力ブロックが平均ＲＧＢ値（122, 33, 250）を有するものとする。この平均ＲＧＢ値が１６出力画素サイズのブロックのためのルックアップテーブルに入力される。ルックアップテーブルは、１３シアン、３マゼンタ、０イエロー、０ブラック及び０ホワイトを出力するであろう。また、近似解を見つけることによって本アルゴリズムをスピードアップすることができる。そのために、例えば、問題を逆行列で表して最大エントロピー法もしくは線形計画法で解いたり、近似ルックアップテーブルを利用することができる。あるいは、動的計画法で近似解を得ることができる。
【００８６】《空間フィルタ》ここに説明するブロック量子化技術のある実施例の目的は、局所的入力領域（例えばブロック）の平均色を対応した局所的出力領域の平均色に一致させることである。局所的領域の平均は、その局所的領域に対し空間フィルタを適用し、値に重み付けすることによって求めることができる。重み付けの一例を図６に示す。例えば、直交フィルタを用いることができる。この場合、領域内の画素は領域内の他の全ての画素と均等にカウントされる。
【００８７】入力ドメインの平均の計算及び／又は出力色セットの計算のために、非直交フィルタを用いることもできる。
【００８８】平均を求めるためにウェーブレットフィルタを用いることもできる。一実施例では、ハイパス・ウェーブレット成分がエッジの有無判定に利用されるであろう。このように、ハイパス・ウェーブレットフィルタが４分木閾値処理に利用される。
【００８９】算出される平均は使用色空間に依存する。様々な色空間を使用できる。色空間としては、RGB、CIELAB、CIELUV、Ohta、Opponent、log Opponent、HSV、 HUV、YCbCr があるが、これに限らない。
【００９０】入力領域及び出力領域の形状は、円形領域が好ましいであろう。略円形の形状から離れた形状は、一般に結果が好ましくない。
【００９１】領域のサイズは、目による平均化を前提とすることが妥当でなくなるほど大きくならないように選ばれる。領域が小さすぎると色解像度が制限される。領域が大きすぎると、空間的ディテールの解像能力の低下を招く。すなわち、目の平均化サイズの範囲内で色解像度と空間解像度の間にトレードオフの関係があり、どちらを無視してもディテール情報が損なわれる可能性がある。
【００９２】《出力色セットの選択》ｎ個の出力色の最適なセットをＢ個の可能色から見出す方法について以下に説明する。まず、Ｂ＝３個の可能色Ｊ，Ｋ，Ｌによって範囲が定められる２Ｄ色空間よりｎ＝３個の出力色を選ぶという簡単な問題について検討する。図３を参照すれば、ｘ記号は、ｎ個の選択出力色からなるセットとして可能な色JJJ，JJK，JKK．．．を示す。”アンカー”Ｊ，Ｋ，Ｌ間の距離の１／ｎの長さの２つのベクトルJK,JLを定義することができる。これらベクトルJk，JLは２Ｄ色空間を張るベクトル基底をなす。
【００９３】ベクトル基底のグラム-シュミット(Gram-Schmidt)直交化法を用いて、直交ベクトル基底を求めることができる。任意の入力ターゲット色点を、原点Ｊより同ターゲット色点へ向かうベクトルと考えることができる。このＪターゲットベクトルを直交基底上へ分解し、元のJX，JLベクトルの係数として再構成することができる。これら２つの係数は、何個の出力色をＫとし、何個の出力色をＬとするか指定する（故に出力色セット中の残余の色はＪとする）。グラム-シュミット手順の結果、ｎ色はターゲットに到達するＪ，Ｋ，Ｌに正確に分解される。ただし、整数解のみ用いればよい。よって、一実施例では、最も近い整数解が出力色セットとして選ばれる。
【００９４】３Ｄ色空間の場合、Ｂを４色以上とし、同じベクトル手法によりｎ個の出力色を求めることができる。しかし、３Ｄで５色以上又は２Ｄで４色以上の場合、ベクトル基底は冗長である（例えば、ターゲットを元のベクトル上へ正確に分解するという問題は劣決定であるので多くの解があるが、正確な整数解があるとは限らない）。
【００９５】５色以上の場合、１つの解法は、とり得る各々の整数個の第５色０〜ｎを考え、（ターゲット平均−第５色寄与分）を残りの４色へ分解することである。したがって、５色の場合には、その４色の解が見つかる。ターゲット色が出力インクにより形成される凸包から外れていない限り、近い整数解が一般に見つかる。
【００９６】入力ターゲット色と一致する適切な出力色セットを見つけるために線形計画法を利用できる。線形計画法はターゲット色と出力色平均との差を減少させ、さらには最小化させる解を探索するが、その減少（最小化）後の差がユークリッド距離（Ｌ２ノルムの２乗に等しい）となることはない。むしろ、線形計画法はＬ１もしくは上限ノルムを減らすのである。ユークリッド距離を減少させ、さらには最小化させるために二次計画法を利用できる。
【００９７】出力色セットの選択プロセスのスピードアップのためにテーブル検索を利用できる。テーブル検索は、例えばプリンタの場合のように、出力色が予め分かっている場合の選択に特に有利である。一実施例では、そのＬＵＴは可能性のあるすべての入力色に対応したメモリセルを有する。別の実施例では、そのＬＵＴは、異なる複数の出力色セットを持つようにプログラムされ、かつ／又は、１つの入力色によって、その最も近い出力色が求まる。このようにすると、メモリは少なくて済むが必要処理量は増加し、また、不正確な答を出すことがある。
【００９８】一実施例では、色空間は予め定量化可能なセルに分割される。所定のセルに含まれる全ての入力平均は、そのセルの中心点に定量化される。
【００９９】前述のように、一実施例では、入力ベクトル色平均が与えられると、その入力平均と選択される出力色セットとのユークリッド距離を減少もしくは最少化するように出力色セットが選択される。別の実施例では、マンハッタン距離もしくは成分毎の最大値を減少させ、さらには最小化するであろう。
【０１００】前述のように、入力色セット及び選択された出力色セットの平均が求められ、そのユークリッド距離が減少させられる（また最少化されるかもしれない）。各ブロックごとに平均を算出するのではなく、ある距離尺度（例えばＥＭＤ（Earth Mover's Distance））を使用して入力ブロック、予定出力色間の距離を測定してもよい。一実施例では、ＥＭＤを使用して、いくつかの可能性のあるものの中から、やや高速の出力セット・ジェネレータで迅速に生成できるものが選択される。ＥＭＤに関するこれ以上の情報を知るには、「Rubnex, Tomasi,Goibas,ICCV 1998」を参照されたい。
【０１０１】《出力色のモザイク状配置》出力色セットが選択されたとしても、それら出力色を出力空間にどのように配置するか決定する課題が残っている。例えば、Ｒ３画素とＧ３画素をRRRGGGのように配置するのとRGRGRGのように配置するのとでは、知覚される色、粒状性、及び、擬似輪郭に違いが生じるであろう。モザイク状配置の方法は、例えば、規則的グリッディング(gridding)、（置換有りと置換無しの）ランダムサンプリング、青色ディザマトリクスの値を用いて選択出力画素を並べるなど、多くの異なる方法を使用できる。規則的グリッディングは、２つのやり方で行うことができる。１つのやり方は、ある特定の出力色の画素全部を一斉にブロック内に配置し、次いで２つ目の出力色の画素全部を一斉にブロック内に配置し、以下同様に行う方法である。例えば、Ｒの８画素とＧの８画素はRRRRRRRRGGGGGGGGのようになろう。この方法は孤立色が発生しない。もう１つの実施例では、できるだけ互い違いにする規則的グリッディングが用いられる。この方法は、よく混合した画像を得られる。この場合、Ｒの８画素とＧの８画素はRGRGGRGRRGRGGRGRとなる。
【０１０２】ブロックのモザイク状配置のもう１つの方法はランダムサンプリングである。Ｒ８画素、Ｇ８画素をブロックに配置するとして、出力ブロックの各画素ごとに分布がランダムにサンプリングされるが、置き換えは行われるか又は行われない。しかし、この方法はざらついた感じの画像になりやすい。
【０１０３】モザイク状配置のための視覚的に好ましい方法は、選択された出力色を青色空間周波パターンに配置する方法である。そのための１つの方法は、当該目的用に作成したディザマトリクスを選択することである。出力色は、何らかの順に、例えば輝度順に配列される。例えば、出力色をＷＹＣＭＫとする。Ｋは黒である。この場合、選択された出力色をディザの順に配置する。図５に一例を示す。４×４ディザマトリクスが図５（ａ）のようだとすると、選択された出力色セットは図５（ｂ）のマトリクスのようになる。
【０１０４】所定のブロックより大きなディザマトリクスを用いてもよく、その場合には、ブロックはそれがカバーする値の順序たけを利用する。
【０１０５】（閾値処理に関連して前述したようにブロックが分割されていない時に）ブロックのサブブロックの平均により良く一致させようと試みる決定論的方法又は確率的方法によって、全ての解像度で一層良く平均を表現すことができる。４×４ブロックの場合、１６の出力色が選ばれた後に、各２×２サブブロックの平均に基づいて、それら出力色を４つの４色グループに分ければよい。
【０１０６】《応用例》一実施例では、複写機やプリンタなどのシステム内の組み込みプロセッサによって本ブロックカラー量子化が実行される。そのアルゴリズムは特定用途向け集積回路（ＡＳＩＣ）に実装されるであろう。図４は、前述したブロック量子化技術のための処理を組み込むことができるシステムの一例を示すブロック図である。
【０１０７】図４を参照すれば、システム４００は情報処理のための組み込みプロセッサ４１２を有する。システム４００は、さらに、情報と組み込みプロセッサ４１２により実行される命令を格納するための、組み込みプロセッサ４１２に接続されたランダムアクセスメモリ（ＲＡＭ）又は他の動的記憶装置４０４を有する。
【０１０８】コンピュータシステム４００は、システムのユーザに情報を表示するための陰極線菅（ＣＲＴ）や液晶ディスプレイ（ＬＣＤ）などの、組み込みディスプレイ４１２に接続されたディスプレイ装置４２１も有するであろう。組み込みプロセッサ４１２に情報及びコマンド選択を伝えるために、英数字キー及び他のキーを有する英数字入力装置も装備されるであろう。
【０１０９】これ以外のユーザ入力装置は、マウス、トラックボール、トラックパッド、スタイラス、カーソル方向キーなどのカーソル制御装置であり、方向情報及びコマンド選択をプロセッサ４１２に伝えたりディスプレイ４２１上のカーソルの動きを制御するためにシステムに組み込まれるであろう。
【０１１０】プリントエンジン４２４が組み込みプロセッサ４１２に接続されている。一実施例では、このプリントエンジン４２４は複写機の一部である。システム４００の前記要素の任意の要素又は全要素と関連ハードウェアを本発明に利用し得ることに注意されたい。ただし、システムの他の構成でも以上の装置の一部又は全部を含んでもよいことは明らかであろう。
【０１１１】以上の説明を読めば本発明の多くの変更及び修正が当業者には明白となろうから、以上に図示及び記述したどの実施例も説明を目的としたものであって、限定を意図したものと解すべきでない。
【０１１２】
【発明の効果】以上、詳細に説明したように、本発明によれば、拘束条件付きの局所的色最適化を行って、誤差拡散と同様の色の一致、空間解像度及び色解像度を達成するとともに誤差拡散につきもののアーティファクトの発生を防止することができ、また、整数計画法、動的計画法又はルックアップテーブルを利用することで処理のスピードアップを達成できる、等々の効果を得られるものである。
【図面の簡単な説明】
【図１】中間調処理のためのブロック量子化システムの一実施例のブロック図である。
【図２】ブロック量子化を中間調処理と同時に実施するプロセスの一実施例の流れ図である。
【図３】可能な色セットの説明図である。
【図４】ブロック量子化処理機能を有するシステムの一実施例のブロック図である。
【図５】ディザマトリクスによる出力色セットの配置例の説明図である。
【図６】重み付けの一例を示す図である。
【符号の説明】
１０２ ブロック生成・色平均ユニット
１０３ ブロックサイズ適応調整ユニット
１０４ 色合わせ・配置ユニット
【特許請求の範囲】
【請求項１】入力画像及び出力画像をブロックに分割するステップ、ここにおいて出力画像の各ブロックは入力画像の１つのブロックに対応する、各入力ブロックの色平均を計算するステップ、出力画像の各ブロックのための出力色セットを入力画像の対応ブロックの色平均に一致するように計算するステップ、及び出力画像の各ブロックにおける出力色セットの配置を制御するための指示を生成するステップを有することを特徴とするカラー中間調処理方法。
【請求項２】特定の条件が満たされるときに、それぞれの入力ブロック及び出力ブロックをサブブロックに分割するステップをさらに有することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項３】ブロックをサブブロックに分割するための特定の条件とは、そのブロックがエッジを含んでいるかどうかであることを特徴とする請求項２記載のカラー中間調処理方法。
【請求項４】ブロックの特性はブロックに関連した色を人間の目が平均化するようなものであることを特徴とする請求項１記載のカラー中間調処理方法。
【請求項５】ブロックの特性はサイズ、形状及び想定観察距離の中の１つ以上を含むことを特徴とする請求項４記載のカラー中間調処理方法。
【請求項６】出力色セットの計算は、色空間上で表現可能な値を調べ、対応した入力ブロックの色平均に最も近い表現可能値を見つけることにより行われることを特徴とする請求項１記載のカラー中間調処理方法。
【請求項７】出力色セットの計算に、同セット中の出力色を決定するために平均色に関するルックアップテーブルを利用することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項８】出力色セットの計算に整数計画法を利用することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項９】出力色セットの計算に動的計画法を利用することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項１０】出力色セットの計算に近似線形計画法を利用することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項１１】出力色セットの計算に近似最大エントロピー法を利用することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項１２】ブロックをサブブロックへ分割するステップは、各ブロックごとに、及び、そのブロックの複数のサブブロックの各々ごとに色値の関数を計算するステップ、ブロックとサブブロックの色値の関数間の距離が閾値より大きいか判定するステップ、及びその距離が閾値より大きいときにブロックをサブブロックに分割するステップからなることを特徴とする請求項２記載のカラー中間調処理方法。
【請求項１３】各サブブロックについての色値の関数を、そのブロックの他のサブブロックについての関数値と比較することによりエッジの存在を判定するステップをさらに有することを特徴とする請求項１２記載のカラー中間調処理方法。
【請求項１４】複数のサブブロックは４個のサブブロックからなることを特徴とする請求項１２記載のカラー中間調処理方法。
【請求項１５】出力色セットが与えられたならば、ターゲット色に一致するように、かつ空間的アーティファクトを減らすように各ブロック内に色を配置するステップをさらに有することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項１６】各ブロック内の色配置で規則的グリッディングを行うことを特徴とする請求項１５記載のカラー中間調処理方法。
【請求項１７】各ブロック内の色配置で、選択された出力色をディザマトリクスに従って配置することを特徴とする請求項１５記載のカラー中間調処理方法。
【請求項１８】コンピュータが読み取り可能な記録媒体であって、請求項１乃至１７のいずれか１項記載のステップをコンピュータに実行させるための実行可能命令が記録されたことを特徴とする記録媒体。
【請求項１９】入力画像及び出力画像をブロックに分割するディバイダ、ここにおいて出力画像の各ブロックは入力画像の１つのブロックに対応する、各入力ブロックの色平均を計算する第１のロジック、出力画像の各ブロックのための出力色セットを入力画像の対応ブロックの色平均に一致させるように計算する第２のロジック、及び出力画像の各ブロックにおける出力色セットの配置を制御するための指示を生成する指示生成ロジックを有することを特徴とするカラー中間調処理装置。
【請求項２０】前記ディバイダは、特定の条件が満たされるときに、それぞれの入力ブロック及び出力ブロックをサブブロックに分割することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２１】ブロックをサブブロックに分割するための特定の条件とは、そのブロックがエッジを含んでいるかどうかであることを特徴とする請求項２０記載のカラー中間調処理装置。
【請求項２２】ブロックの特性はブロックに関連した色を人間の目が平均化するようなものであることを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２３】ブロックの特性はサイズ、形状及び想定観察距離の中の１つ以上を含むことを特徴とする請求項２２記載のカラー中間調処理装置。
【請求項２４】出力色セットを計算する第２のロジックは、色空間上で表現可能な値を調べ、対応した入力ブロックの色平均に最も近い表現可能値を見つけることを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２５】出力色セットを計算する第２のロジックは、同セット中の出力色を決定するために平均色に関するルックアップテーブルを利用することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２６】出力色セットを計算する第２のロジックは整数計画法を利用することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２７】出力色セットを計算する第２のロジックは動的計画法を利用することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２８】出力色セットを計算する第２のロジックは近似線形計画法を利用することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２９】出力色セットを計算する第２のロジックは近似最大エントロピー法を利用することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項３０】各ブロックごとに、及びそのブロックの複数のサブブロックの各々ごとに色値の関数を生成する計算ロジック、ブロックとサブブロックの色値の関数間の距離が閾値より大きいか判定する判定ロジック、及びその距離が閾値より大きいときにブロックをサブブロックに分割するディバイダをさらに有することを特徴とする請求項２０記載のカラー中間調処理装置。
【請求項３１】各サブブロックについての色値の関数を、そのブロックの他のサブブロックについての関数値と比較することによりエッジの存在を判定する判定ロジックをさらに有することを特徴とする請求項３０記載のカラー中間調処理装置。
【請求項３２】複数のサブブロックは４個のサブブロックからなることを特徴とする請求項３０記載のカラー中間調処理装置。
【請求項３３】出力色セットが与えられたときに、ターゲット色に一致するように、かつ空間的アーティファクトを減らすように各ブロック内に色を配置する制御ロジックをさらに有することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項３４】制御ロジックは各ブロック内において規則的グリッディングを行うことを特徴とする請求項３３記載のカラー中間調処理装置。
【請求項３５】制御ロジックは各ブロック内に選択された出力色をディザマトリクスに従って配置することを特徴とする請求項３３記載のカラー中間調処理装置。
【請求項３６】入力画像及び出力画像をブロックに分割する手段、ここにおいて出力画像の各ブロックは入力画像の１つのブロックに対応する、各入力ブロックの色平均を計算する手段、出力画像の各ブロックのための出力色セットを入力画像の対応ブロックの色平均に一致するように計算する手段、及び出力画像の各ブロックにおける出力色セットの配置を制御するための指示を生成する手段を有することを特徴とするカラー中間調処理装置。
【請求項３７】入力画像及び出力画像をブロックに分割するステップであって、エッジを含むブロックのサイズを適応的に変更してエッジを含まない複数のブロックを生成するステップを含むステップ、及び入力画像の対応ブロックの色平均を最もよく表現する出力色セットを計算するステップを有することを特徴とするカラー中間調処理方法。
【請求項３８】入力画像の色域は出力画像の色域に合わせるため予め調整されることを特徴とする請求項３７記載のカラー中間調処理方法。
【請求項３９】入力画像及び出力画像をブロックに分割する手段であって、エッジを含むブロックのサイズを適応的に変更してエッジを含まない複数のブロックを生成する手段を含む手段、及び入力画像の対応ブロックの色平均を最もよく表現する出力色セットを計算する手段を有することを特徴とするカラー中間調処理装置。
【請求項４０】入力画像の色域は出力画像の色域に合わせるため予め調整されることを特徴とする請求項３９記載のカラー中間調処理装置。
【請求項４１】エッジを含むブロックのサイズを適応的に変更してエッジを含まない複数のブロックを生成することにより入力画像及び出力画像をブロックに分割するディバイダ、及び入力画像の対応ブロックの色平均を最も良く表現する出力色セットを計算する計算ロジックを有すること特徴とするカラー中間調処理装置。
【請求項１】入力画像及び出力画像をブロックに分割するステップ、ここにおいて出力画像の各ブロックは入力画像の１つのブロックに対応する、各入力ブロックの色平均を計算するステップ、出力画像の各ブロックのための出力色セットを入力画像の対応ブロックの色平均に一致するように計算するステップ、及び出力画像の各ブロックにおける出力色セットの配置を制御するための指示を生成するステップを有することを特徴とするカラー中間調処理方法。
【請求項２】特定の条件が満たされるときに、それぞれの入力ブロック及び出力ブロックをサブブロックに分割するステップをさらに有することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項３】ブロックをサブブロックに分割するための特定の条件とは、そのブロックがエッジを含んでいるかどうかであることを特徴とする請求項２記載のカラー中間調処理方法。
【請求項４】ブロックの特性はブロックに関連した色を人間の目が平均化するようなものであることを特徴とする請求項１記載のカラー中間調処理方法。
【請求項５】ブロックの特性はサイズ、形状及び想定観察距離の中の１つ以上を含むことを特徴とする請求項４記載のカラー中間調処理方法。
【請求項６】出力色セットの計算は、色空間上で表現可能な値を調べ、対応した入力ブロックの色平均に最も近い表現可能値を見つけることにより行われることを特徴とする請求項１記載のカラー中間調処理方法。
【請求項７】出力色セットの計算に、同セット中の出力色を決定するために平均色に関するルックアップテーブルを利用することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項８】出力色セットの計算に整数計画法を利用することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項９】出力色セットの計算に動的計画法を利用することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項１０】出力色セットの計算に近似線形計画法を利用することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項１１】出力色セットの計算に近似最大エントロピー法を利用することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項１２】ブロックをサブブロックへ分割するステップは、各ブロックごとに、及び、そのブロックの複数のサブブロックの各々ごとに色値の関数を計算するステップ、ブロックとサブブロックの色値の関数間の距離が閾値より大きいか判定するステップ、及びその距離が閾値より大きいときにブロックをサブブロックに分割するステップからなることを特徴とする請求項２記載のカラー中間調処理方法。
【請求項１３】各サブブロックについての色値の関数を、そのブロックの他のサブブロックについての関数値と比較することによりエッジの存在を判定するステップをさらに有することを特徴とする請求項１２記載のカラー中間調処理方法。
【請求項１４】複数のサブブロックは４個のサブブロックからなることを特徴とする請求項１２記載のカラー中間調処理方法。
【請求項１５】出力色セットが与えられたならば、ターゲット色に一致するように、かつ空間的アーティファクトを減らすように各ブロック内に色を配置するステップをさらに有することを特徴とする請求項１記載のカラー中間調処理方法。
【請求項１６】各ブロック内の色配置で規則的グリッディングを行うことを特徴とする請求項１５記載のカラー中間調処理方法。
【請求項１７】各ブロック内の色配置で、選択された出力色をディザマトリクスに従って配置することを特徴とする請求項１５記載のカラー中間調処理方法。
【請求項１８】コンピュータが読み取り可能な記録媒体であって、請求項１乃至１７のいずれか１項記載のステップをコンピュータに実行させるための実行可能命令が記録されたことを特徴とする記録媒体。
【請求項１９】入力画像及び出力画像をブロックに分割するディバイダ、ここにおいて出力画像の各ブロックは入力画像の１つのブロックに対応する、各入力ブロックの色平均を計算する第１のロジック、出力画像の各ブロックのための出力色セットを入力画像の対応ブロックの色平均に一致させるように計算する第２のロジック、及び出力画像の各ブロックにおける出力色セットの配置を制御するための指示を生成する指示生成ロジックを有することを特徴とするカラー中間調処理装置。
【請求項２０】前記ディバイダは、特定の条件が満たされるときに、それぞれの入力ブロック及び出力ブロックをサブブロックに分割することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２１】ブロックをサブブロックに分割するための特定の条件とは、そのブロックがエッジを含んでいるかどうかであることを特徴とする請求項２０記載のカラー中間調処理装置。
【請求項２２】ブロックの特性はブロックに関連した色を人間の目が平均化するようなものであることを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２３】ブロックの特性はサイズ、形状及び想定観察距離の中の１つ以上を含むことを特徴とする請求項２２記載のカラー中間調処理装置。
【請求項２４】出力色セットを計算する第２のロジックは、色空間上で表現可能な値を調べ、対応した入力ブロックの色平均に最も近い表現可能値を見つけることを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２５】出力色セットを計算する第２のロジックは、同セット中の出力色を決定するために平均色に関するルックアップテーブルを利用することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２６】出力色セットを計算する第２のロジックは整数計画法を利用することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２７】出力色セットを計算する第２のロジックは動的計画法を利用することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２８】出力色セットを計算する第２のロジックは近似線形計画法を利用することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項２９】出力色セットを計算する第２のロジックは近似最大エントロピー法を利用することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項３０】各ブロックごとに、及びそのブロックの複数のサブブロックの各々ごとに色値の関数を生成する計算ロジック、ブロックとサブブロックの色値の関数間の距離が閾値より大きいか判定する判定ロジック、及びその距離が閾値より大きいときにブロックをサブブロックに分割するディバイダをさらに有することを特徴とする請求項２０記載のカラー中間調処理装置。
【請求項３１】各サブブロックについての色値の関数を、そのブロックの他のサブブロックについての関数値と比較することによりエッジの存在を判定する判定ロジックをさらに有することを特徴とする請求項３０記載のカラー中間調処理装置。
【請求項３２】複数のサブブロックは４個のサブブロックからなることを特徴とする請求項３０記載のカラー中間調処理装置。
【請求項３３】出力色セットが与えられたときに、ターゲット色に一致するように、かつ空間的アーティファクトを減らすように各ブロック内に色を配置する制御ロジックをさらに有することを特徴とする請求項１９記載のカラー中間調処理装置。
【請求項３４】制御ロジックは各ブロック内において規則的グリッディングを行うことを特徴とする請求項３３記載のカラー中間調処理装置。
【請求項３５】制御ロジックは各ブロック内に選択された出力色をディザマトリクスに従って配置することを特徴とする請求項３３記載のカラー中間調処理装置。
【請求項３６】入力画像及び出力画像をブロックに分割する手段、ここにおいて出力画像の各ブロックは入力画像の１つのブロックに対応する、各入力ブロックの色平均を計算する手段、出力画像の各ブロックのための出力色セットを入力画像の対応ブロックの色平均に一致するように計算する手段、及び出力画像の各ブロックにおける出力色セットの配置を制御するための指示を生成する手段を有することを特徴とするカラー中間調処理装置。
【請求項３７】入力画像及び出力画像をブロックに分割するステップであって、エッジを含むブロックのサイズを適応的に変更してエッジを含まない複数のブロックを生成するステップを含むステップ、及び入力画像の対応ブロックの色平均を最もよく表現する出力色セットを計算するステップを有することを特徴とするカラー中間調処理方法。
【請求項３８】入力画像の色域は出力画像の色域に合わせるため予め調整されることを特徴とする請求項３７記載のカラー中間調処理方法。
【請求項３９】入力画像及び出力画像をブロックに分割する手段であって、エッジを含むブロックのサイズを適応的に変更してエッジを含まない複数のブロックを生成する手段を含む手段、及び入力画像の対応ブロックの色平均を最もよく表現する出力色セットを計算する手段を有することを特徴とするカラー中間調処理装置。
【請求項４０】入力画像の色域は出力画像の色域に合わせるため予め調整されることを特徴とする請求項３９記載のカラー中間調処理装置。
【請求項４１】エッジを含むブロックのサイズを適応的に変更してエッジを含まない複数のブロックを生成することにより入力画像及び出力画像をブロックに分割するディバイダ、及び入力画像の対応ブロックの色平均を最も良く表現する出力色セットを計算する計算ロジックを有すること特徴とするカラー中間調処理装置。
【図１】
【図２】
【図３】
【図４】
【図６】
【図５】
【図２】
【図３】
【図４】
【図６】
【図５】
【公開番号】特開２００２−５７９０９（Ｐ２００２−５７９０９Ａ）
【公開日】平成１４年２月２２日（２００２．２．２２）
【国際特許分類】
【出願番号】特願２００１−１８０９７４（Ｐ２００１−１８０９７４）
【出願日】平成１３年６月１５日（２００１．６．１５）
【出願人】（０００００６７４７）株式会社リコー (37,907)
【Ｆターム（参考）】
【公開日】平成１４年２月２２日（２００２．２．２２）
【国際特許分類】
【出願日】平成１３年６月１５日（２００１．６．１５）
【出願人】（０００００６７４７）株式会社リコー (37,907)
【Ｆターム（参考）】
[ Back to top ]