(57)【要約】【課題】色シンボルレベルでの単純で計算上高速な画像処理アルゴリズムを可能とする、カラー画像を量子化する方法を提供する。【解決手段】  色シンボルを画像画素に割当てる方法は、量子化された輝度値の離散的セットから輝度値を選択するステップと、量子化されたクロミナンス値の順序付けられた離散的セットからクロミナンス値を選択するステップと、選択された輝度値の指数と選択されたクロミナンス値の順序位置の指数とから色シンボルを構成するステップと、を含む。本発明の特定の実施例では、各離散的クロミナンス値は、ＬａｂまたはＬｕｖ等の知覚的に一様な色空間における一定輝度平面上のフィボナッチ格子から選択される。【選択図】図６
2010211214.tif 000002
【特許請求の範囲】
【請求項１】
色シンボルを画像の少なくとも１つの画素に割当てる方法であって、該方法は、量子化された輝度値の離散的セットから輝度値を選択する段階と、量子化されたクロミナンス値の順序付けられた離散的セットからクロミナンス値を選択する段階と、該選択された輝度値の指数と該選択されたクロミナンス値の順序位置の指数とから色シンボルを構成する段階と、該色シンボルを格納する段階とからなることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２次元カラー画像の処理に関する。特に、本発明は、かかる画像の各画素に、制限された色（ｃｏｌｏｒ）のセットからの選択を表すシンボル（ｓｙｍｂｏｌ）を割当てる方法に関する。
【背景技術】
【０００２】
色知覚の研究から、いかなる色も３原色の組合せとして適切な表示装置に再現することができる、ということは周知である。従って、画像の格納、送信および表示の目的で、各々がそれぞれの原色からの寄与（ｃｏｎｔｒｉｂｕｔｉｏｎ）を表している３つの係数を指定することによって、デジタル化した画像の各画素の色を表現することは、好都合である。人間は連続的な色の範囲を知覚するため、原則として、いかなる特定の色を指定するためにも無限量の情報が必要となる。すなわち、３つの係数の各々は、長さが制限されていない。
【０００３】
かかる再現的システムは、当然のことながら非実用的である。しかしながら、多くの目的で、連続的な色の範囲を離散的な色のセットによって置換えることが十分であることが分かっている。離散的な色のセットの指定は、「色量子化（ｃｏｌｏｒ  ｑｕａｎｔｉｚａｔｉｏｎ）」と呼ばれている。例えば、いわゆるフル色表示システムは、３原色係数の各々に８ビットを割当てる。従って、かかるシステムの各色は、合計２４ビットによって指定され、そのため指定可能な色の合計数は、２２４すなわち約１７００万色である。
【０００４】
実際には、より少ない色の選択で十分なアプリケーションも多くある。従って、例えば、目下入手可能な表示モニタでは、２４ビット未満、一般には８、１２または１６ビットのストリングが各表示可能色を表現する。ここでは、かかるストリング各々を「シンボル（ｓｙｍｂｏｌ）」と呼ぶ。
【０００５】
一般に、利用可能な色のあるサブセットは、「色コードブック（ｃｏｌｏｒ  ｃｏｄｅｂｏｏｋ）」と呼ばれるが、全色セットから選択される。選択は、すべての画像に対して同じであってよく、その場合、色コードブックは「画像独立型（ｉｍａｇｅ  ｉｎｄｅｐｅｎｄｅｎｔ）」であると言われる。代替的に、選択は、個々の画像または画像群に対して専用に適用されてもよい。その場合、色コードブックは「画像依存型（ｉｍａｇｅ  ｄｅｐｅｎｄｅｎｔ）」であると言われる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｇ．ＷｙｓｚｅｃｋｉおよびＷ．Ｓ．Ｓｔｉｌｅｓ、「Ｃｏｌｏｒ  Ｓｃｉｅｎｃｅ」（Ｊｏｈｎ  Ｗｉｌｅｙ，Ｎｅｗ  Ｙｏｒｋ，１９８２）
【発明の概要】
【発明が解決しようとする課題】
【０００７】
各シンボルは、対応する色を検索するための色コードブックへの指標としての役割を果たす。このため、所定のシンボルが、表示装置において対応する色を再現するために使用される３原色係数と、必ずしも直接関係があるものではない。代りに、再現に必要な情報は、格納された情報から検索される。
【０００８】
実際には、従来からの多くの色コードブックにおけるシンボルは、無作為に割当てられており、基本となる色と相関関係がまったく無い。結果として、従来からのシステムにおける色情報のデジタル処理は、シンボルレベルで直接行うことができない。代りに、各シンボルは、処理のために多次元色空間の点に変換されなければならない。
【０００９】
対照的に、グレイスケール画像の「色」値は、１つの軸、すなわち１次元空間に沿う。結果として、かかる画像の各画素は、その画素の量子化されたグレイスケール値に直接関連するシンボルに容易に割当てられる。かかる方法で色量子化されたグレイスケール画像の空間的フィルタリング等の処理を実行するために、単純で計算上高速なアルゴリズムが使用可能である。
【００１０】
しかしながら、今まで、シンボル領域で少なくとも部分的に動作する単純で計算上高速な画像処理アルゴリズムの同様な利点を提供する、カラー画像を量子化する方法は無かった。
【課題を解決するための手段】
【００１１】
本発明者は、色量子化の新規な方法を発明した。本発明の方法によれば、量子化された輝度値（ｌｕｍｉｎａｎｃｅ  ｖａｌｕｅ）の離散的なセットから輝度値が選択され、量子化されたクロミナンス値（ｃｈｒｏｍｉｎａｎｃｅ  ｖａｌｕｅ）の順序付けされた離散的なセットからクロミナンス値が選択される。色シンボルは、選択された輝度値の指数と選択されたクロミナンス値の順序位置の指数とから構成され、その色シンボルは格納される。
【００１２】
本発明の特定の実施例において、量子化された輝度値およびクロミナンス値の離散的なセットは、連続的な３次元の色空間（ｃｏｌｏｒ  ｓｐａｃｅ）を量子化することによって得られる。これは、実際には、色空間を一定の輝度の平面に分割し、結果としての各平面を離散的な点の実質的に均一な空間的分布でサンプリングすることによって、行われる。
【００１３】
重要なことには、各平面のサンプリングされた点に対し順序付けがなされている。サンプリングされた点にはシンボルが割当てられる。各割当てられたシンボルは、色空間における対応する点の輝度レベルと順序性とを識別する。
【００１４】
結果として得られるシンボルのセットは、基礎となる色空間の構造と密接な関係がある。結果として、色情報の処理は、少なくとも部分的にシンボルレベルで実行することができる。これによって、従来はグレイスケール画像の処理においてのみ可能であった単純で計算上高速な処理の利点が提供される。
【００１５】
有利には、サンプリングされた３次元色空間は、２つの点の間のユークリッド距離（Ｅｕｃｌｉｄｅａｎ  ｄｉｓｔａｎｃｅ）がそれら点の間の色の知覚的な差に対応する空間である。各一定の輝度の平面内で、サンプリングされた点は、有利には螺旋状格子（ｓｐｉｒａｌ  ｌａｔｔｉｃｅ）を構成する。かかる格子において、ｎ’番目の点の半径位置は、ｎの実数の累乗であり、ｎ’番目の点の角度位置は２πｎγによって与えられるｎの倍数である。ここで、γは、好ましくはマルコフ無理数（Ｍａｒｋｏｆｆ  ｉｒｒａｔｉｏｎａｌ  ｎｕｍｂｅｒ）に近い実数である。本発明の特定の実施例において、螺旋状格子はフィボナッチ格子（Ｆｉｂｏｎａｃｃｉ  ｌａｔｔｉｃｅ）、すなわち、半径位置がｎの平方根によって与えられγがおおよそ±（√５−１）／２に等しい螺旋状格子である。
【図面の簡単な説明】
【００１６】
【図１】本発明のいくつかの実施例において有用な一例としてのフィボナッチ格子を示す図である。
【図２】図１のフィボナッチ格子の詳細を示す図である。
【図３】いくつかの実施例での本発明による色量子化のステップを示すフローチャートを示す図である。
【図４】図３の手続きに従って探索されるべき一定輝度平面の一部を表す図である。
【図５】いくつかの実施例での本発明による色平均化手続きのフローチャートを示す図である。
【図６】本発明の原理を組込んだ画像符号器の１つの段の略図である。
【図７】図６に示すものを複数段含む色符号器の略図である。
【図８】画像捕捉装置から取得される色データに本発明の色量子化原理を適用するための例示的な手続きのフローチャートを示す図である。
【発明を実施するための形態】
【００１７】
知覚可能な色を３次元空間の点として表現することができるということは、以前から周知である。かかる表現に対する１つの方法では、所定の色を表現する点の座標として３つのいわゆる「三刺激値（ｔｒｉｓｔｉｍｕｌｕｓ  ｖａｌｕｅ）」を利用する。三刺激値は、適当な重みと結合された時に所定の色を生成する３つの加法原色に、単純な方法で関連付けられている。３原色のセットが一意でないため、三刺激値のいかなる特定の体系も原色の特定の選択に関連付けられなければならない。三刺激値に基づく色空間の１つの例は、ＲＧＢ色空間である。
【００１８】
三刺激値に基づく色空間には、いくつかの利点がある。それは、例えば、それらを用いて、スキャナから受取られた画像の色かあるいはプリンタ、モニタまたは他の表示装置に表示される画像の色を、比較的単純な中間的処理で記述することができるためである。しかしながら、かかる色空間は、知覚的に一様でないため、人間の色の知覚を表現するためには不利である。すなわち、２つの色の差に対する人間の判断は、かかる色空間における点の間のユークリッド距離とうまく相関しない。
【００１９】
対照的に、ＬａｂおよびＬｕｖ等の色空間は知覚的に一様である。それは、一対の点の間の所定のユークリッド距離が、空間内の位置に関わらず所定の知覚的距離を表すためである。これら空間の各々は、輝度軸Ｌとクロミナンスを表す一対の軸（それぞれ、ａ、ｂまたはｕ、ｖ）によって特徴付けられる。概略すれば、輝度（ｌｕｍｉｎａｎｎｃｅ）は画像要素の明るさに関連し、クロミナンス（ｃｈｒｏｍｉｎａｎｃｅ）はその色相に関連する。ＬａｂおよびＬｕｖ色空間は、例えば、Ｇ．ＷｙｓｚｅｃｋｉおよびＷ．Ｓ．Ｓｔｉｌｅｓによる「Ｃｏｌｏｒ  Ｓｃｉｅｎｃｅ」（Ｊｏｈｎ  Ｗｉｌｅｙ，Ｎｅｗ  Ｙｏｒｋ，１９８２）に述べられている（特に、１６４〜１６９頁を参照。）。
【００２０】
周知の技術により、周知のＲＧＢ空間等、三刺激値に基づく空間で同じ色を表現する点の座標から、ＬａｂまたはＬｕｖ等の知覚的に一様な空間の点の座標を取得することは、容易に実行可能である。当業者によって認められるように、それぞれの空間は、空間的に依存する線要素または距離に関連して表現することができる非線形変換を通して、関連付けられている。かかる変換は、例えば上に引用したＷｙｓｚｅｃｋｉおよびＳｔｉｌｅｓによる「Ｃｏｌｏｒ  Ｓｃｉｅｎｃｅ」に述べられている。
【００２１】
後述する例示的な実現では、Ｌａｂ色空間を使用する。当業者は、Ｌｕｖ色空間等、他の知覚的に一様な色空間に対し容易に拡張することができる、ということを認めるであろう。
【００２２】
色空間を量子化する第１のステップとして、輝度軸が、ＮＬ個の離散的レベル（ＮＬは整数）にサンプリングされる。各離散的レベルは、それぞれの指数ｌと輝度値Ｌｌとを有している。輝度指数は、例えば、ｌ＝１、２、・・・、ＮＬをカウントすることによって割当てられ、指数１が最低の離散的輝度に割当てられる。このように、各輝度指数は、一定の輝度Ｌｌの各平面を定義する。
【００２３】
一定輝度の各平面において、ＮＰ個の点（ＮＰは整数）が選択される。点の選択は、次の形の螺旋を構成することによって実行される。
【数１】
2010211214.tif 000003
ここで、ｒは半径座標であり、θは角度座標であり、ｓはスケールファクタであり（１であることが多い）、δおよびγは実数であり、φはオフセット角であり（０であることが多い）、ｎは自由パラメータ（ｆｒｅｅ  ｐａｒａｍｅｔｅｒ）である。ｎが例えば０からＮｐ−１までの整数である場合はいつでも、点が選択される。結果としての点のセットは、一定輝度平面における螺旋状格子を構成する。各点のクロミナンス指数は、例えばその点におけるｎの値である。
【００２４】
当業者は、半径座標と角度座標との両方を、
【数２】
2010211214.tif 000004
（ここで、ｊ２＝−１）
によって与えられる複素数値の座標ｚに包含することができる、ということを認めるであろう。
【００２５】
スケールファクタｓが１に設定され、オフセット角φが０に設定された、適当な色パレットを取得することができるが、これらの一方または両方が他の値に設定されることも可能である。スケールファクタは、平面における色の細かいかまたは粗いサンプリングに対して調整することができる。オフセット角は、例えば、螺旋状格子の隙間ではなく点が特定の重要な色になることを確実にするよう、調整することができる。
【００２６】
累乗の指数δが１／２に設定されている場合、結果としての螺旋状格子は、平面を一様に覆う。すなわち、十分に広い領域にわたって平均化され、単位エリア毎に一定数の格子点がある。一定面積の適用範囲が必要でない場合、δは、他の値に設定されることも可能であり、平面上の位置の関数とされてもよい。
【００２７】
係数γは、格子における点の分布を制御するために重要である。γが最少の整数の比として表現される有理数である場合、ｎが、かかる比の分母より大きい値を超えると、螺旋状格子の点は、その原点から放射状に広がるスポーク（ｓｐｏｋｅ）に沿って配列される。これは、比較的微細なレベルで一様である平面の適用範囲を提供しないため、望ましくない。より高い一様性が達成されるのはγが無理数であるとき、特に数学者にはマルコフ無理数として周知の無理数のクラスに属する場合である。後に説明するように、±γの値として特定のマルコフ数、すなわち黄金比である（√５−１）／２を選択することが、特に有利である。（なお、γは正の値でも負の値でもよい。簡単のためであって限定のためではなく、以下の説明においてγは正の値をとるものとする。）
【００２８】
当然ながら、無理数を表現するための計算機において無限の精度は不可能である。よくても、無理数のいかなる計算上の表現も、実際には丸めかまたは切捨てによってそれから得られた無理数の近傍の有理数となる。しかしながら、かかる有理数の比の表現において分母が十分に大きい場合、実質的に、螺旋状格子に対する差異は無視できるものとなる。
【００２９】
上述した手続きによってＮＬ・ＮＰ点の３次元格子がもたらされるが、すべての点が必ずしも知覚可能な色に対応するものではない。すなわち、例えばＲＧＢ空間の限定された領域のみが、有効な色を含む。このため、格子を構成した後、有効な色を表現しない各点を破棄する。これは、例えば、ＲＧＢ空間のｒ、ｇまたはｂ座標が０乃至１の許可された範囲外にある各点を破棄することによって容易に達成される。適切な結果と共に使用した例示的な色パレットには、この破棄するステップの後に１３９の点が残っている。
【００３０】
フィボナッチ格子として、ｓが定数であり、δ＝１／２であり、γ＝±（√５−１）／２である場合の結果となる螺旋状格子について述べる。フィボナッチ格子を、図１に示す。図から、格子の各点を通して、原点（ｎ＝０）に向かって傾斜する右回りと左回りの一対の螺旋を描くことが可能であることが明らかとなろう。連続する点の間の指数差は、右回り螺旋の場合は２１であり左回り螺旋の場合は１３である。例えば、図は、ｎ＝５の点を通過する右回り螺旋１５と左回り螺旋２０とを示している。ここでは、これら螺旋を「主螺旋（ｄｏｍｉｎａｎｔ  ｓｐｉｒａｌ）」と呼ぶ。
【００３１】
また、フィボナッチ格子の各点が、中心点の回りに略六辺形の近傍を形成する６つの最近傍を有していることも、図から明らかとなろう。点ｎ＝２２の回りのかかる近傍が、図１の近傍２５として示されている。近傍２５のより詳細は図２に示されており、それについては後に更に参照する。
【００３２】
また、各点とその最近傍の各々との間の指数差がフィボナッチ数、すなわち多数の周知のフィボナッチ数列１、１、２、３、５、８、１３、２１、３４、・・・であることも、図１から明らかとなろう。図２において、例えば、点ｎ＝２２とその最近傍との間に、指数差が示されている。図２は、近傍２５内において、指数差は５、８、１３または２１であることを示している。
【００３３】
ここで、螺旋状格子の２つのパラメータを採用する。最短距離ｄｍｉｎは、最高指数格子点と、大きい方の主螺旋に沿った、すなわちフィボナッチ数が大きい方の主螺旋に沿ったその最近傍と、の間のユークリッド距離である。従って、例えば、図１の格子の最高指数点は点ｎ＝８９である。点ｎ＝８９を通過する２つの主螺旋１５、３０のうち、螺旋１５のフィボナッチ数は２１であり、螺旋３０のフィボナッチ数は１３であるため、大きい方の螺旋は螺旋１５である。コードブック最短距離Ｄｍｉｎは、３次元格子によってサンプリングされ有効な色に対応する、基本となる色空間、例えばＬａｂ空間の点のすべての対の間のユークリッド距離を考慮することによって定義される。Ｄｍｉｎは、かかる距離の最短である。従って、Ｄｍｉｎは、（ａ）ｄｍｉｎおよび（ｂ）隣接する一定輝度平面間の輝度軸に沿った最短距離のうちの小さい方である。
【００３４】
量子化処理
Ｌａｂ空間の色座標がＬｐ、ａｐ、ｂｐである画素ｐが与えられる場合、それら所定の座標を有するＬａｂ空間の点から最短ユークリッド距離を有する格子点を見つけることにより、画素ｐの色を量子化することは、有利である。かかる量子化は、全２乗誤差（ｔｏｔａｌ  ｓｑｕａｒｅ  ｅｒｒｏｒ：ＴＳＥ）量子化として周知のものの一例である。
【００３５】
ここで、図３を参照して例示的な量子化手続きを説明する。入力点のＬａｂ座標が取得される（ブロック１００）。そして、最も近い離散的輝度レベルＬｐが見つけられる（ブロック１０５）。選択されたレベルに輝度値Ｌと輝度指数ｌを持たせる。そして、最小のＴＳＥを有する選択された一定輝度平面の格子点、すなわち、選択された平面上の点（Ｌｐ，ａｐ，ｂｐ）の射影までの最短ユークリッド距離を有する格子点に対し、探索が実行される（ブロック１１０）。
【００３６】
フィボナッチ格子の特性は、探索を平面の限定された部分に制限するため、故に探索を実行するために必要とされる計算時間を短縮するために使用される。特に、図４に示すように、探索領域１２０を、原点の回りの中間半径がおおよそ、
【数３】
2010211214.tif 000005
であり幅がｄｍｉｎよりわずかに大きいリングに制限することで十分である。従って、αおよびβが適応可能なパラメータ、例えば共に値０．５である場合、リング内側半径はｒｐ−αｄｍｉｎとしてよく、外側リング半径はｒｐ＋βｄｍｉｎとしてよい。螺旋状格子の点が指数付けされる順序により、および半径座標が、ｎ＝（ｒ／ｓ）２のような指数に関連付けられているため、指数が（ｒｐ−αｄｍｉｎ）２／ｓ２以下の最も近い整数から（ｒｐ＋βｄｍｉｎ）２／ｓ２以上の最も近い整数までの範囲である点のみに対し、探索することで十分である。更に、探索は、リングの角度セクタに容易に制限される。例えば、角度座標が点（ａｐ，ｂｐ）の角度座標と同じ象限内にある格子点に探索を制限することは有利である。
【００３７】
量子化された輝度指数およびクロミナンス指数は、決定された後、図３のブロック１１５に示すように、容易に結合されて色シンボルとなる。かかるシンボルの１つの有用な形式は、輝度指数およびクロミナンス指数を備えた、順序付けされた対かまたはマルチプレット（ｍｕｌｔｉｐｌｅｔ）である。しかしながら、多くの場合、よりコンパクトであるためにより有用である形式は、輝度指数およびクロミナンス指数の重み付けされた合計である。例えば、上記のように、Ｎｐが、無効な色を破棄する前の各螺旋状格子における点の数を示すようにする。ｌおよびｎが、それぞれ輝度およびクロミナンスの指数を示すようにする。そして、色シンボルの１つの有用な形式は、Ｎｐｌ＋ｎである。Ｎｐを知っていることから、ｌとｎとは共に、この形の色シンボルから容易に抽出される。
【００３８】
順序付けされたディザリング（Ｏｒｄｅｒｅｄ  Ｄｉｔｈｅｒｉｎｇ）
一定の色を有するように知覚される広い画像領域が量子化される場合、再現された画像は、量子化された色を使用するため、一定色領域に割込む間違った輪郭を示す傾向がある、ということは以前から周知である。この理由は、量子化アルゴリズムが、概して、蓄積された色の変化が閾値を超えるまで小さい（そのため知覚不可能な）色勾配（ｃｏｌｏｒ  ｇｒａｄｉｅｎｔ）を無視するためである。そして、新たな色値が割当てられる。結果として、下位閾値領域と上位閾値領域との間の再現画像に、知覚可能な勾配が現れる。また、原画像の代りに、乱数のまたは擬似乱数の雑音が付加された中間画像を量子化することにより、間違った輪郭形成を抑制することができる、ということも認められている。かかる雑音を付加するプロセスは、順序付けされたディザリング（Ｏｒｄｅｒｅｄ  Ｄｉｔｈｅｒｉｎｇ）と呼ばれる。
【００３９】
順序付けされたディザリングは、本発明による量子化手続きに容易に組込まれる。中間画像を形成するために、原画像に雑音振幅ｖ（ｉ，ｊ）の行列Ｄが付加される。Ｄは、例えばある次元Ｍの正方行列である。原画像の画素ｉ、ｊに付加される雑音振幅は、ｖ（ｉ  ｍｏｄ  Ｍ，ｊ  ｍｏｄ  Ｍ）である。雑音振幅の分布は、望ましくはゼロ平均を有し、そのエネルギースペクトルは、望ましくは最低空間周波数でその最小値を有している。雑音の振幅は、一定色の領域が種々の近傍の色に量子化されるように選択され、それによって間違った輪郭形成の出現が低減される。
【００４０】
色量子化に対する本発明による方法のコンテキストにおいて、単に無作為に選択された画素の量子化された色を置換することによって、雑音が容易に付加される。すなわち、選択された画素各々において、色格子の元の点が、近傍の点によって置換される。一般に、新しい点は、フィボナッチ近傍の１つ、すなわち主螺旋の各々に沿った２つの最近傍（従って、全部で４つ）の１つとなる。すなわち、主螺旋に沿った最近傍の直接上かまたは下にある、隣接する一定輝度平面上の点か、または、元の点の直接上かまたは下にある、隣接する一定輝度平面上の点である。従って、対応する雑音振幅ｖ（ｉ，ｊ）は、共に上に定義した格子パラメータｄｍｉｎかまたは格子パラメータＤｍｉｎから容易に決定される。重大なことに、同じ輝度値での色置換は、単純に主螺旋の１つに対応するフィボナッチ数をクロミナンス指数に加算するかまたはそれから減算することによって、容易に実行される。
【００４１】
２つの色値の差と平均
３次元格子の２点間のユークリッド距離の計算は、半径座標ｒと指数ｎとの関係によって簡略化される。従って、それぞれのクロミナンス指数ｍ、ｎの格子点の対の、共通の一定輝度平面に対する射影は、
【数４】
2010211214.tif 000006
によって得られる距離Δｍｎによって分離される。輝度差Λｍｎは、Λｍｎ＝［Ｌｍ−Ｌｎ］１／２に従ってそれぞれの輝度値Ｌｍ、Ｌｎから容易に得られる。そして、全体の差ｄｉｆｆ（ｍ、ｎ）は  、
【数５】
2010211214.tif 000007
として容易に得られる。種々の代替的な差の公式は容易に定義可能である。しかしながら、多くの場合、輝度の差およびクロミナンスの差の組合せとして全体の差を定義することが有用であり、Ｌｍ−Ｌｎまたはその絶対値の関数として輝度差を定義することがしばしば有用となる。
【００４２】
特に有用な差の公式Ｄｉｆｆ（ｍ、ｎ）は、上に定義した格子パラメータＤｍｉｎにｄｉｆｆ（ｍ，ｎ）を正規化することによって得られる。すなわち、Ｄｉｆｆ（ｍ，ｎ）＝［Ｄｉｆｆ（ｍ、ｎ）］／Ｄｍｉｎである。差の公式Ｄｉｆｆ（ｍ，ｎ）は、ｍ’番目とｎ’番目の点の間の経路に要求される格子に対する最低数のステップとして理解されてよい。
【００４３】
グレイスケール画像が処理される場合、２つのグレイスケール値の平均は、例えばその２つの値の平均をとりその最も近い整数に丸めることによって、容易に得られる。しかしながら、かかる平均化手続きは、３次元の量子化された色空間における色シンボルに直接適用される場合、概して満足がいかない。特に、一対の色度指数の丸めた平均は、平均化される色の両方から比較的離れた色値の指数となる可能性がある。
【００４４】
この問題の１つの解法は、基本となるＬａｂ空間の対応する点の間の平均を計算した後、先に説明したようにその結果を量子化する、というものである。かかる計算に必要なＬａｂ座標の値は、例えばルックアップテーブルに局所的に格納されていてもよく、あるいは、平均化される色の量子化された値から計算されてもよい。
【００４５】
代替的な解法は、フィボナッチ格子の構造を使用する。代替的な解法によれば、それぞれｍ、ｎが指数付けされた色間の新たな平均ａｖ（ｍ，ｎ）を定義する。本発明による新たな平均は、クロミナンスのみに適用される。対応する輝度は、例えば、輝度値を平均化し結果としての平均値に最も近い一定輝度平面に量子化することによって、平均化することができる。
【００４６】
ここで、クロミナンスを平均化する代替的な解法を、図５を参照して説明する。平均ａｖ（ｍ，ｎ）は、ａｖ（ｍ、ｎ）＝（１／２）×（ｍ’＋ｎ’）によって定義される。ここで、ｍ’およびｎ’は、後に説明するように選択されたフィボナッチ格子の点である。
【００４７】
ブロック１２５に示すように、ｍ’、ｎ’の初期設定はそれぞれｍ、ｎである。ｍおよびｎが同じパリティを有するか否かという初期判断（ブロック１３０）がなされる。２つの指数は、両方とも奇数かまたは両方とも偶数である同じパリティを有することとなる。
【００４８】
ｍ、ｎの一方が奇数で他方が偶数である場合、２つの指数のうちの１つは、反対のパリティの近傍によって置換されなければならない。この場合、所定の点の近傍は、フィボナッチ近傍、すなわち、以下のうちの１つである。すなわち、主螺旋の各々に沿った２つの最近傍（従って、全部で４つ）のうちの１つか、主螺旋に沿った最近傍の直接上か下にある隣接する一定輝度平面上の点か、または元の点の直接上か下にある隣接する一定輝度平面上の点である。
【００４９】
元の量子化された色とその置換との間の差を最小化するために、図のブロック１４０、１４５に示すように、まず指数が大きい方の元の格子点を置換するようにすることが有利である。置換されるべき格子点は、格子の外側縁にない限り、それを通過する主螺旋の各々の上の２つの最近傍を有することとなる。これら４つの近傍のうち、最も近い許容可能な近傍が選択されなければならない（ブロック１６０）。（ブロック１５５のテストの否定の結果に対応して）いずれの近傍も許容可能でない場合、ブロック１５０に示すように、指数の小さい方の元の格子点が、同じ方法で置換を考慮される。
【００５０】
置換が無い場合、平均化するための候補の格子点は、元の格子点である。置換が行われる場合、候補点は、１つが元の点であり１つが置換された点であるか、または、後に説明するように２つの置換された点である。
【００５１】
そして、候補格子点の指数を合計し２で割ることによって、平均指数がとられる。ブロック１６５は、置換された点に対するこのステップを示し、ブロック１７５は置換されていない（すなわち、元の）点に対するこのステップを示す。このステップでの候補格子点が必ずしも同じパリティを有していないため、それらの合計は偶数でありそれらの平均は整数であって、従って平均は格子の点の指数である。しかしながら、結果としての平均指数は、許容できる角度範囲内であってもなくてもよい。すなわち、元の格子点の角度座標は、閉じた角度範囲（すなわち、２つの格子点の間の小さいほうの角度範囲であり、１８０°を超えない）を定義し、平均指数は、それがその範囲にある角度座標を有する場合にのみ許容可能である。平均指数の角度座標がその範囲外にある場合、ブロック１７０、１８０においてテストの否定の結果に示すように、平均指数は拒否される。
【００５２】
平均指数が拒否された場合、いくつかのオプションが利用可能である。１つのオプションは、ブロック１７２で示すように現置換を破棄し、元の格子点に戻り、新たな置換を試す、というものである。ブロック１３５におけるテストの肯定的な結果に示すように、１つの点の置換により許容できる平均指数がもたらされなかった場合、ブロック１８５に示すように２つの点の置換が試みられる。
【００５３】
第２のオプションを、ここでは「リワインド（ｒｅｗｉｎｄ）」処理と呼ぶ。リワインド処理によれば、一定輝度平面の探索は、平均指数を有する格子点がある半径を含むリング形状の範囲内で実行される。探索は、２つの元の格子点によって定義される小さい方の角度範囲（すなわち、１８０°を超えない範囲）に制限される。リング形状の領域の内側および外側の半径は、例えば、上述した量子化手続きに対する場合と同様に決定される。探索の目的は、許容できる角度範囲内で、その半径座標が平均指数格子点の半径座標に最も近い格子点を探すことである。
【００５４】
勾配演算子（ｇｒａｄｉｅｎｔ  Ｏｐｅｒａｔｏｒｓ）およびエッジ検出
グレイスケール画像の処理において、所定の近傍における画素値間の勾配（ｇｒａｄｉｅｎｔ）を評価することにより、エッジは容易に検出される。しかしながら、カラー画像に対し許容可能なエッジ検出器を考案することはずっと困難である。その困難性は、色を記述するためには、単に１つのグレイスケールの次元ではなく３次元が必要であるため、および人間の知覚は同じ画像の異なる色成分に対し異なってエッジを配置する傾向にあるため、発生する。しかしながら、本発明者は、上に定義した差演算子ｄｉｆｆ（ｍ，ｎ）を使用することによって、カラー画像の処理に対し従来からのグレイスケール勾配演算子を拡張する簡単な方法を見つけた。重要なことには、本発明による拡張された勾配演算子は、色シンボル、すなわち輝度指数およびクロミナンス指数に対し直接作用し、従って計算資源の使用が比較的経済的である。
【００５５】
従来からの水平勾配演算子Ｈｘおよび垂直勾配演算子Ｈｙの一例は、以下の３×３ウインドウの対の形式を取る。
【数６】
2010211214.tif 000008
これら演算子の各々は、画像にわたって走査される。走査における各位置で、演算子の対応する要素によって画像の９画素が覆われる。走査における各位置で、演算子の第２行第２列の要素の下にある画素における勾配は、重み付けされた合計として評価される。要素によって覆われた各画素のグレイスケール値は、その要素によって重み付けされ、合計に加算される。重みａ、ｂ、ｃは、使用される演算子のクラスによって種々の値をとることができる。例えば、プレウィット（Ｐｒｅｗｉｔｔ）演算子の場合の（ａ，ｂ，ｃ）は（１，１，１）であり、ソーベル（Ｓｏｂｅｌ）演算子の場合は（１，２，１）であり、等方性演算子の場合は（１，√２，１）である。従って、画素位置（ｉ，ｊ）（ｉは画素がある画像の行を示し、ｊは対応する列を示す）において、水平勾配ｇｘ（ｉ，ｊ）は、
【数７】
2010211214.tif 000009
によって与えられ、垂直勾配ｇｙ（ｉ，ｊ）は
【数８】
2010211214.tif 000010
によって与えられる。ここで、Ｉ（ｉ，ｊ）は、画素（ｉ，ｊ）におけるグレイスケール値を示す。
【００５６】
2010211214.tif 000011
【００５７】
対応するベクトル勾配は、大きさ
【数９】
2010211214.tif 000012
と、向き
【数１０】
2010211214.tif 000013
とを有する。
【００５８】
色量子化された画像の圧縮および符号化
図６および図７は、上述した原理を組込んだ例示的な画像符号器を示す。符号器の目的は、色マップされた画像の多重解像度分解を実行することである。符号器の出力は、元の色マップの低解像度近似と、異なるレベルの解像度でおよび異なる方向に沿って細部を表現する画像の集合とである。
【００５９】
例示的な画像符号器は、多重分解レベルＤ１、Ｄ２、・・・、ＤＬを有している。ｉ’番目のレベルＤｉに対する入力は、画像ａｉ−１（ｍ，ｎ）からなる（ｍおよびｎはそれぞれ画素の行および列の座標を表す）。第１分解レベルに対する入力ａ０（ｍ，ｎ）は、生（ｒａｗ）画像を表す。符号器の１つの分解レベルを図６に示す。
【００６０】
図６を参照すると、入力画像の各行または列は、ブロック２００において１次元ローパスフィルタによってフィルタリングされ、その後ブロック２０５において係数２によってサブサンプリングされる。同様に、各行または列は、ブロック２１０において１次元ハイパスフィルタによってフィルタリングされ、その後ブロック２１５において係数２によってサブサンプリングされる。ｉ’番目のレベルのローパス出力は、ｄｉ（ｍ，ｎ）と称され、ハイパス出力はａｉ（ｍ，ｎ）と称される。例示的なフィルタリング動作は、後述するが、色シンボル、すなわち輝度およびクロミナンスの指数に対して実行される。フィルタリング動作には、指数対の合計または差の半分をとることが含まれるため、上述したように、各対が同じパリティのクロミナンス指数を含むことを確実にするよう置換を実行することが望ましい。本発明による画像符号化のコンテキストにおいて、かかる置換を「丸め（ｒｏｕｎｄｉｎｇ）」演算と呼ぶ。図６において、丸め演算は、ブロック２２０において示されている。
【００６１】
各分解レベルで、図６のブロック２２５に示すように、エッジマップｅｉ（ｍ，ｎ）も計算する。エッジマップを計算するために、適切なエッジ検出演算子を使用することができる。１つの例は、上述した勾配演算子である。例示的な実現では、エッジを検出するためにベクトル勾配の大きさを使用する。当業者は、代替的な実現において、１次元勾配を使用してもよい、ということを認めるであろう。図６のブロック２３０に示すように、エッジ検出器２２５の生出力（ｒａｗ  ｏｕｔｐｕｔ）ｅｉ（ｍ，ｎ）は、バイナリ量子化される。例えば、所定の画素（ｍ，ｎ）について、適切な分解レベルに対しｅｉ（ｍ，ｎ）が量子化閾値Ｔｉを超える場合、出力ｓｉ（ｍ，ｎ）は値１をとり、ｅｉ（ｍ，ｎ）が量子化閾値を超えない場合、ｓｉ（ｍ，ｎ）は値０をとる。ここでは、量子化された出力ｓｉ（ｍ，ｎ）を「重要度マップ（ｓｉｇｎｉｆｉｃａｎｃｅ  ｍａｐ）」と呼ぶ。後に説明するように、重要度マップは、画像符号器の後続する段階で詳細信号のセットを量子化するために使用される。
【００６２】
上述したように、ブロック２００でローパスフィルタリングが実行され、ブロック２１０でハイパスフィルタリングが実行される。各フィルタは、例えば、１次元の完全復元フィルタである。このようなフィルタの具体例は、ローパスフィルタの場合は重み（１／２，１／２）を有しハイパスフィルタの場合は（１／２，−１／２）を有するＨａａｒフィルタ（Ｈａａｒ  ｆｉｌｔｅｒ）である。従って、例えば、ｐ１’は、（ｍ，ｎ）画素位置における丸められた色シンボルを表し、ｐ２’は（ｍ，ｎ＋１）画素位置における丸められた色シンボルを表す場合、出力ａｉ（ｍ，ｎ）およびｄｉ（ｍ，ｎ）は、水平方向に沿った平均および差をそれぞれ表すが、次の式から与えられる。
【数１１】
2010211214.tif 000014
【００６３】
出力ａｉ、ｄｉおよびｓｉは各々、画像を表現する。分解の方向に沿ったこれら画像の各々の解像度は、入力画像ａｉ−１の解像度より２倍低い。出力画像ａｉは、ｉ’番目の分解の入力と直交する方向で実行される（ｉ＋１）’番目の分解に対する入力としてとられる。従って、Ｌ個の分解の合計は、図７のブロック２３５に示すように、Ｄ１、Ｄ２、・・・、ＤＬとラベル付けされた交互の方向に実行される。
【００６４】
全体の結果は、元の色マップよりＬ／２低い解像度を有する画像近似ａＬ（ｍ，ｎ）と、Ｌ個の詳細信号の集合｛ｄｉ｝と、Ｌ個の重要度マップの集合｛ｓｉ｝（ｉ＝１、・・・、Ｌ）とからなる。詳細信号および重要度マップは、図７のブロック２４０に示す量子化器Ｑに対する入力としてとられる。
【００６５】
量子化器２４０において、対応する重要度係数ｓｉが０である場合、各詳細信号ｄｉは０に設定される。対応する重要度係数が１である場合、ｄｉは変更されずに通され、後述するルールが適用される。本発明者は、詳細係数の間の空間的冗長性を利用することにより、信号圧縮を向上させることができる、ということが分かった。重要なことには、詳細信号ｄｉ（ｍ，ｎ）が閾値Ｔｉに対してｉ’番目のスケールで重要でない場合、すなわち、対応する重要度係数が０である場合、２つのより細かいスケール、すなわち、（ｉ−１）’番目および（ｉ−２）’番目のスケールにおける詳細係数もまた、（ｍ，ｎ）画素位置において重要でない可能性が高いと仮定する。従って、量子化は、最初に最も粗いスケールで実行される。所定のレベルの詳細信号がゼロに量子化された場合、２つの次の細かいレベルでの対応する詳細信号もまた、自動的にゼロに設定され、対応する重要度係数がゼロに設定される。
【００６６】
量子化器２４０からの出力として、すべてのレベルの重要度マップが、ブロック２４５に示すようにまずランレングス符号化（ｒｕｎ−ｌｅｎｇｔｈ  ｃｏｄｅｄ）され、その後ブロック２５０に示すように、従来からの符号化技術を使用してエントロピ符号化（ｅｎｔｒｏｐｙ  ｃｏｄｅｄ）される。量子化器２４０からの出力として、すべてのレベルの詳細信号が、ブロック２５５に示すように従来からの符号化技術を使用してエントロピ符号化される。画像近似ａＬ（ｍ，ｎ）は、ブロック２６０に示すように、まず予測符号化され、その後ブロック２６５に示すように、従来からの符号化技術を用いてエントロピ符号化される。
【００６７】
復元された画像は元の量子化された色パレットからの色のみを含むため、符号器において追加の量子化を実行する必要はない。結果として、本明細書で述べた符号化方式により、比較的高い画像品質およびビットレートを維持しつつ比較的低い複雑度の復号器を採用することが可能になる。
【００６８】
例示的な実現
一般的な色モニタに対する入力色は、ＲＧＢ表現において原色値ｒ、ｇ、ｂによって表現される。各入力値は、非線形関係を介して対応する表示強度に関連付けられる。例えば、入力赤値ｒは、ｒ＝（Ｉｒ）γ（γは一般的に約２．３）によって表示赤強度Ｉｒに関連付けられる（このパラメータは、上述した格子パラメータγとは関連していない。）。一般的な画像捕捉装置は、予め歪められた（ｐｒｅ−ｄｉｓｔｏｒｔｅｄ）出力を提供することによって各入力原色とその輝度との間の非線形性を補償する。すなわち、かかる装置の出力は、ｒ＝（Ｉｒ）１／γ等の逆変換が施される。かかる事前に歪められた原色は、しばしば「ガンマ補正色（ｇａｍｍａ−ｃｏｒｒｅｃｔｅｄ  ｃｏｌｏｒｓ）」と呼ばれる。
【００６９】
図８に関して、本発明による色量子化手続きの例示的な実現は、ブロック３００において、画像の１つまたは複数の画素の各々に対し、ガンマ補正されたＲＧＢ色のセットを取得するステップで開始する。ブロック３０５において、ガンマ補正は取除かれる。ブロック３１０において、色データは、線形演算子を使用して周知のＸＹＺ色空間に変換される。ＸＹＺ空間において、周知の技術を使用して、照明白色点に関してデータが正規化される（ブロック３１５）。ブロック３２０において、色データは、非線形変換を介してＬａｂ表現に変換される。かかる手続きは、例えば、上で引用したＷｙｓｚｅｃｋｉおよびＳｔｉｌｅｓによる「Ｃｏｌｏｒ  Ｓｃｉｅｎｃｅ」において述べられている。ブロック３２５において、図３および図４に関連して上述したように、生色（ｒａｗ  ｃｏｌｏｒ）は量子化された色の適当なパレットにマップされる。
【００７０】
以下のパラメータから、１０２４の量子化された色の一例としてのパレットが容易に生成される。
【数１２】
2010211214.tif 000015
【００７１】
９１の色を有するより小さい例示的なパレットは、以下のパラメータから容易に生成される。
【数１３】
2010211214.tif 000016
【図１】
2010211214.tif 000017
【図２】
2010211214.tif 000018
【図３】
2010211214.tif 000019
【図４】
2010211214.tif 000020
【図５】
2010211214.tif 000021
【図６】
2010211214.tif 000022
【図７】
2010211214.tif 000023
【図８】
2010211214.tif 000024