JP4271804B2

JP4271804B2 - 画素に割り当てられる色の選択方法、ならびに画像の符号化及び記憶方法

Info

Publication number: JP4271804B2
Application number: JP35386699A
Authority: JP
Inventors: クラッセンアール．ビクター
Original assignee: Xerox Corp
Current assignee: Xerox Corp
Priority date: 1998-12-21
Filing date: 1999-12-14
Publication date: 2009-06-03
Anticipated expiration: 2019-12-14
Also published as: US6748108B2; JP2000196907A; EP1014699B1; DE69937785D1; EP1014699A1; DE69937785T2; US6385337B1; US6507669B1; US20020039441A1

Description

【０００１】
【発明の属する技術分野】
本発明は概して画像処理に関し、詳細には、ブロック打ち切りコード化画像圧縮技術に使用されるブロック内の画素に対する色の選択に関する。
【０００２】
【従来の技術】
データ整理はデータ処理工程で必要とされ、その場合、データを使用する実際のアプリケーションに対して過度の量のデータが存在する。ディジタル画像−即ち、空間座標と走査によって取得されるような輝度レベルとの両方において離散化された画像−は、多くの場合に非常に多く、このため少なくとも１つのデータ整理の形式に対する望ましい対象になる。正確には、データをより高速で処理可能にすることによってユーザに与える不便さを緩和するのみならず、画像処理時間を大幅に増加させずに一層複雑なデータを処理可能にする。例えば、詳細な中間階調の画像を正確に描画するのに必要なビット数は、印刷されていないページにおける１枚の黒色原稿の場合の多数倍になる。同様に、カラー画像を正確に描画することは、その非常に詳細な中間階調の場合よりもさらに大量のデータを要求することになる。データ整理の形式が何もないと、中間階調画像及びカラー画像を含む文書の処理では許容できないほどに長い時間がかかる可能性がある。
【０００３】
各ブロックにおけるすべての画素は、ブロックに割り当てられた２色のみの一方によって表示されなければならない。各ブロックを表示するために選択されるこの２色が慎重に選択されないと、最終的に復号化された出力画像における色は原画像の色を正確に表示しないことになる。本発明は、２色ブロックに割り当てられる色を選択し、次にブロック内の画素に色を割り当てることによりカラー画像を正確に再生するための方法と装置を開示する。
【０００４】
【発明が解決しようとする課題】
ブロックごとに色を選択する周知の方法では、１つのパスにおいて２つの両極端の色を見つけることが試みられてきた。このパスから得られる両極端の色はブロックに割り当てられる２色である。ブロック内の各画素は、該画素の実際の色に最も近い色に割り当てられる。この方法は最も一般的な場合−即ち、ブロックが２つの色と、それらの間に明確な境界を有する場合−に対して容認できる。中間色はその境界に沿って正確に現われるが、これら中間色がブロックを表示するために選択される色を見いだすために使用されるものでないことは、両極端の色が最も実際的な外観を付与することになるからである。しかしながら、実質的に同色の画素からなる一次クラスタが２つ以上ある場合には問題が生じる。２つ以上のクラスタ内のブロックは高周波テクスチャーデータ又はノイズを含む画像の領域に現れる可能性がある。この場合、該ブロックに対して選択された第２の色として選ばれた色は、領域において重要な色よりはむしろ、ノイズを表わすことになる。ノイズカラーを該ブロックに割り当てることにより、より多くの画素が符号化さらには復号化された画像におけるその色に付着することになり、これによりノイズを増幅させる。
【０００５】
【課題を解決するための手段】
本発明によって提供される、マーキング装置による後続の復号化と印刷のために画像の画素に割り当てられる色を選択する方法は：画像を複数のブロックに分割する工程であって、各ブロックは複数の画素から構成され；ブロックにおいて複数の画素クラスタを識別する工程であって、画素クラスタは実質的に同色の複数の画素を含み；最大数の画素を含む最大画素クラスタを選択し、ブロックに対する第１の割り当てとして該最大画素クラスタの色を指定する工程と；該最大画素クラスタの外側の画素の平均色を計算し、ブロックに対する次の割り当てとして外側画素の平均色を指定する工程と、を有する。
【０００６】
本発明の別の実施の形態によって提供される、画像を第１の解像度で符号化し第２の解像度で画像バッファに記憶させる方法は：画像を複数のブロックに分割する工程であって、各ブロックは複数の画素から構成され；該複数のブロック各々に存在する多数の画素クラスタを識別する工程であって、各画素クラスタは実質的に同色の複数の画素を含み；ブロックにおいて最大数の画素を含む各ブロックごとに最大画素クラスタを選択し、該ブロックに対する第１の割り当てとして最大画素クラスタの色を指定する工程と；最大画素クラスタの外側にあるブロック内の画素に対して平均色を計算し、該ブロックに対する次の割り当てとして外側画素の平均色を指定する工程と；マーキング装置による後続の復号化及び印刷のための低減容量化画像バッファに複数のブロックを記憶する工程と、を有する。
【０００７】
【発明の実施の形態】
本発明の実施の形態を説明するための図面を参照するに、本発明を限定するものではないが、図１にはディジタルフォーマットを用いて原画像を表示するために一般に使用されるタイプの画素マップ１０が示されている。図示のように、画素マップ１０は、複数の画像素子、即ち、「画素」１４を含む。複数の画素１４は本発明での処理のために複数のブロック１２に区分けされている。以下の発明の説明では、画素マップ１０はカラーデータを含むものと仮定する。しかしながら、本発明がグレースケール中間階調データを付与するシステムでの使用に適応され得るとともに、カラー文書の再生に限定されるものでないことは、当業者によって認識されるであろう。同様に、本発明は、グレースケール又は黒白の文書を取得してカラーのものを印刷することにも適応可能であり、その反対の場合も同様である。このような代りの方法をすべて包含するとともに、本発明がここに含まれる説明に限定されないことが意図されている。
【０００８】
図２を参照して、本発明を概略的に説明する。カラー画像における複数の画素は多くの場合、「クラスタ」に区分けされる。複数の画素から成るクラスタはここでは、各々実質的に同一のカラー値（輝度、色差、及び色相）であるディジタル信号によって表示される複数の画素のグループとして定義される。図示のように、ステップ１０２でブロック１２が取得されると、ステップ１０４に示されるように最大数の画素を含むブロックにおけるクラスタ（最大クラスタ、最大数クラスタ、または最大画素クラスタともいう）が識別される。最大クラスタが識別されると、ステップ１０６に示されるように該クラスタの幾何学的中心にある、又はそれに最も近接した画素１４の位置を見つけ、該画素のディジタル値をブロックの色の１つとして選択する。本発明の実施の形態をクラスタの幾何学的中心の値を選択するものとして説明するが、当業者は、例えば、平均又は中央の信号値などの数学的中心を代わりに選ぶこともできることを理解するであろう。実際、そうすることが有利であるならば、クラスタにおける画素の最小又は最大の信号値を選んでもよいことになる。クラスタにおけるすべての画素に対する信号値は選ばれた値に等しく設定される。次に、ステップ１０８で最大クラスタに含まれないブロックにおける複数の画素の平均カラー値を計算して、ブロックの他の色として選択する。このように、最大クラスタの外側にあるすべての画素に対する信号値は、これら信号値の平均に等しく設定される。このようにして、他にクラスタが１つだけある場合、平均値はそのクラスタの平均と等しく、結果として符号化された画像はブロック内への１つのパスの場合と同様になり、ブロック内での設定画素は最も近い値に等しい。しかしながら、２つ以上の追加クラスタがある場合、それらの値は平均化され、これにより画像に含まれる可能性があるノイズ信号の影響を軽減する。
【０００９】
図４を参照すると、最大画素数クラスタを見いだす実施の一形態の詳細には、ステップ３０２に示されるように、各クラスタにおける画素値範囲の位置を見つけるため、ブロック１２における画素上でヒストグラム分析を実行することが含まれる。なお、図３を参照すると、図示のように番号づけされた画素を備えた４×４サイズのブロックが画素信号を有するとともに、該画素信号はそれぞれ（画素１乃至１６の順に）１６６、１５８、１６４、１４、１６２、１６７、１２、８、１７０、２０４、２４８、２５１、２０２、２０９、２４６、及び２４２の値を有するものと仮定する。画素１、２、３、５、６、及び９（それぞれ１６６、１５８、１６４、１６２、１６７、及び１７０の値を有する）は同一範囲にあり、１４、１２、及び８の値をそれぞれ有する画素４、７、及び８は別の範囲にあり、２０４、２０２、及び２０９の値をそれぞれ有する画素１０、１３、及び１４はさらに別の範囲にあり、２４８、２５１、２４６、及び２４２の値をそれぞれ有する画素１１、１２、１５、及び１６はさらに別の、第４の範囲にある。ヒストグラム分析では、４つの画素値範囲、即ち、０乃至８９、９０乃至１８０、１８１乃至２３０、２３１乃至２５５のそれぞれの信号値がこのような場合において容認され得ることが示されている。例として、画素の色は単純なスカラ値（即ち、番号）として示される。実際には、画素値は通常は３又は４次元のベクトル量である。このため、ヒストグラムは３又は４次元となる。
【００１０】
図４を再度参照すると、ヒストグラム分析が終了されると、各画素は、ステップ３０４に示されるように、画素の配置される信号値範囲（画素値範囲）に対応するクラスタに割り当てられることになり、各範囲における画素の数はステップ３０６に示されるようにカウントされることになる。ここに示された例では、９０乃至１８０の値を有する２番目のクラスタが明らかに最大クラスタである。
【００１１】
図５に転じて、本発明による最大クラスタを見いだすことを含む別の実施の形態の詳細を説明する。前記の通り、ブロックのヒストグラム分析はステップ４０２に示されるように実行される。画素値範囲に対応するカウンタｘ及びｙと、処理中の画素は、ステップ４０４に示されるように初期化される。画素ｐ_yの値ｖ_yはステップ４０６で得られ、ステップ４０８に示されるように、第１の範囲の上限しきい値ｋ_xと比較される。ｖ_yがｋ_xより小さいと、ステップ４１０と４１２に示されるように、画素は範囲ｘに割り当てられ、その範囲に対応するカウンタはインクリメントされる。一方、ｖ_yがｋ_xより小さくない場合、画素値範囲カウンタｘはインクリメントされて、ｖ_yはステップ４０８で次の範囲の上限しきい値と比較される。画素値ｖ_yは、適切な範囲が見いだされるまで各範囲の上限しきい値と比較される。画素が範囲に割り当てられると、それに対応付けられるカウンタはインクリメントされる。
【００１２】
次のステップは、ステップ４１６に示されるように、ブロック内の最後の画素が処理されたかどうかを確認することである。否定判断の場合、画素カウンタｙがインクリメントされ、次の画素の適切な範囲の位置が、ステップ４０６乃至４１４における上述された工程を用いて見つけられる。これは、ブロックの最後の画素が処理されるまで継続する。その状態になると（ステップ４１６）、現時点でのブロックに対する処理がステップ４２０に示されるように停止する。すべての範囲に対応付けられるカウンタは再検討されてどの範囲に最も多く画素があるかを決定して、最大クラスタ（最大数クラスタ）が識別される。画像にまだほかにブロックがある場合、それらブロックにも、ここで説明されたように処理がなされて、そのブロックにおける画素の最大クラスタを見いだすことができる。
【００１３】
本発明をここまで、簡潔にするために、従来のヒストグラム分析を用いて説明してきた。好ましい実施の形態では、「ファジィ」ヒストグラムが使用される。従来のヒストグラムでは、値がビンに対応する範囲内の値であるたびに該値は該「ビン」に割り当てられ、該ビンに対するカウンタがインクリメントされる。ビンに対するそれぞれの範囲は互いにオーバーラップすることなく、完全に一組になった範囲はヒストグラム化された値の範囲を構成する。本発明で使用されるようなファジィヒストグラムでは、値は一定の半径内にあるすべてのビンに割り当てられる。一次元では、これは、現時点での色の値を中心とした任意の範囲内のすべてのビンがそれぞれのカウンタを増分させることを意味する。したがって、範囲が＋／−１０で、ビン幅が１６であると、３３の値によって、範囲１６乃至３１と、３２乃至４７に対応するビン２及び３のカウンタがそれぞれ増分される。また、４０の値によって、範囲１６乃至３１、３２乃至４７、４８乃至６３に
対応するビン２、３、及び４のカウンタがそれぞれ増分される。
【００１４】
２次元では、概念的に、値の周囲を所定半径の円で囲み、該円によって部分的にオーバーラップされたすべてのビンはそのカウンタをインクリメントさせることになる。実際には、ヒストグラムに追加される値は有限精度を有し、各座標はビン数（円の中心にあるビンを表わす）と、オフセット（中心内部の小数オフセットを表わす）に分離されることもある。有限数（概して、小数）の独自のオフセットの発生にすぎない。例えば、１７個のビンを使用して、座標ｘでは、ビン番号はフロア［（ｘ＋８）／１７］（ここで、フロア（ｘ）は最大がｘである整数）であり、オフセットはｘ−１７フロア［（ｘ＋８）／１７］である。８−ビット整数では、この場合にオフセットが発生され得る１５個のみの予想値がある。ビンの数が２の累乗であると、ビン番号は「ｘ＋ビン幅／２」の高位ビットで示され、一方、オフセットは前記式の低位ビットである。小さな組の予想オフセットがあるので、オフセットごとに近隣の値のリストを予め計算してもよい。このように、ヒストグラムの構築中の時間での距離を計算することなく、中心ビンと、影響を受けたすべての近隣の値（入力値の半径ｒ以内にある値）を増分することがあり得る。
【００１５】
三次元又はそれよりも大きな次元では、円は球形又は超球形に一般化し、一組の近隣の値を見いだすためのテーブルルックアップの使用がより重要になる。
【００１６】
このように、それぞれが新しい値を含むビンだけでなく、値の任意の半径内にあるすべてのビンに対してもカウンタをそれぞれインクリメントすることによって、ファジィヒストグラムが構築される。この方法の主な利点については図６（Ａ）及び図６（Ｂ）を参照することができる。ここでは、一組の２次元の値がヒストグラムのビン境界とともに描画されている。図６（Ａ）（従来技術）では、ヒストグラムのカウントは個々のビンにおける値のみを示す。図６（Ｂ）（本発明の実施の形態）では、カウントは１ビン幅の半径に対して計算される。各図の左上側よりも右下側の方に最大クラスタが識別される。本発明は最大クラスタを迅速に見いだすことを意図する。この最大クラスタの中心を１つの色の値として用いて、該クラスタ内に存在しない色の複数の画素の平均を他の色として使用する。
【００１７】
最大クラスタを見つけ得る速度は本発明の重要な特徴である。要約すると、発明の好ましい実施の形態では、データ構造は色の低位ビットで指標づけされた３次元又は４次元のヒストグラムである。各画素域は、リストサイズのカウントとともに、マップするすべての画素のリストを含む。量子化誤差を回避するために、各画素は画素の色の任意の半径内の各範囲に入力される。画素がリストに入力されると、対応範囲に対するカウントはインクリメントされて、最大カウントをある程度超えると、そのカウントとレンジは記録される。ブロック内のすべての画素が入力されると、最大カウントのある範囲は最大クラスタの画素を含む。これらの画素についての色の平均は第１の色として使用される。
【００１８】
残りの色は平均をとられて第２のブロックカラーとなる。画素位置のすべての配置を示すビットマップが形成され、平均に含まれている画素は該ビットマップから削除されて、第２のクラスタに属する画素を見つけやすくなる。
【００１９】
本発明の別の実施の形態では、処理が繰り返されて、３つ以上の色が割り当てられるブロックに対して、未分類の色の最大クラスタを見つける。このように、すべての範囲と対応付けられるカウンタを再検討した後で、最大クラスタを識別するためにどのレンジが最大画素を有するかを決定するのみならず、１つ以上の次の最大クラスタも同様に決定する。これらのクラスタの幾何学的中心にある画素の値、もしくは、平均、中央、最大、又は最小の数学値等の値を個々のクラスタ内にある画素に割り当てることもできる。
【００２０】
本発明のさらに別の実施の形態では、２つの色が見いだされると、それらの間のラインに沿って外挿してエッジ強化の形式を付与することによりこれら２つの色を変更することもできる。このように、２つの色がａ及びｂであると、その変更値は、（ａ＋ｂ）／２−ｔ（ｂ−ａ）／２及び（ａ＋ｂ）／２＋ｔ（ｂ−ａ）／２であり、ｔのある値は１よりわずかに大きい。
【００２１】
なお、上記例は、第１の解像度で画像を符号化し、第２の解像度で低減容量化画像バッファに記憶（マーキング装置による後続の復号化と印刷のため）する方法においても用いられる。即ち、上記低減容量化画像バッファには、各ブロックごとに上記のように色が指定された最大画素クラスタが選択された該複数のブロックが記憶される。
【００２２】
【発明の効果】
本発明は上記のように構成されているので、２色ブロックに割り当てられる色を選択し、次にブロック内の画素に色を割り当てることによりカラー画像を正確に再生することができるという効果を有する。
【図面の簡単な説明】
【図１】本発明で使用するための画像を表示するために一般的に使用されるタイプの画素マップを示す図である。
【図２】本発明による、画素の色を選択するための順次工程を示す、一般化されたフローチャートである。
【図３】本発明における画素の最大クラスタを見いだすことを含む本発明の一部の１つの実施の形態を示す、詳細な図である。
【図４】本発明における画素の最大クラスタを見いだすことを含む本発明の一部の別の実施の形態を示す、詳細な流れ図である。
【図５】本発明が適用できる印刷システムの流れ図である。
【図６】（Ａ）及び（Ｂ）はそれぞれ、実施の形態によるファジィヒストグラムの実行方法を示す図である。
【符号の説明】
１０画素マップ
１２ブロック
１４画素

Claims

画像において画素に割り当てられる色を選択する方法であって、
ａ）画像を複数のブロックに分割する工程であって、各ブロックは複数の画素から構成され、各画素は、画像における分離した位置での輝度、色差、及び色相を表わす値を有し、
ｂ）ブロックにおいて少なくとも１つの画素クラスタを識別する工程であって、該画素クラスタは略同一の輝度、色差、及び色相の値を有する複数の画素を含み、
ｃ）最大数の画素を含む画素クラスタを選択し、前記ブロックに割り当てるために該最大画素クラスタに対応付けられた信号値を指定する工程と、
を有し、
前記工程ｃ）において、
各ブロックの各画素の値から、画素の値の複数の画素値範囲の各々の度数を計数して、最大度数の画素値範囲を前記最大画素クラスタとして選択するとともに、各画素値範囲の度数を計数する際に、各画素の値を中心とした所定範囲内の画素に対応する複数の画素値範囲の度数を増分する
ことを特徴とする画素に割り当てられる色の選択方法。
第１の解像度で画像を符号化し、第２の解像度で画像バッファに記憶する方法であって、
ａ）画像を複数のブロックに分割する工程であって、各ブロックは複数の画素から構成され、
ｂ）該複数のブロック各々に存在する多数の画素クラスタを識別する工程であって、画素クラスタは略同一色の複数の画素を含み、
ｃ）該ブロックに最大数の画素を含む各ブロックごとに最大画素クラスタを選択して、該ブロックへの割り当てのために該最大画素クラスタの色を指定する工程と、
ｄ）マーキング装置による後続の復号化と印刷のために低減容量化画像バッファに該複数のブロックを記憶する工程と、
を有し、
前記工程ｃ）において、
各ブロックの各画素の値から、画素の値の複数の画素値範囲の各々の度数を計数して、最大度数の画素値範囲を前記最大画素クラスタとして選択するとともに、各画素値範囲の度数を計数する際に、各画素の値を中心とした所定範囲内の画素に対応する複数の画素値範囲の度数を増分する
ことを特徴とする、画像の符号化及び記憶方法。