JPH02116893A - 色画像量子化方法及び装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は、色画像量子化装置及び方法に関し、特に同時
表示色が限られたカラー表示装置に、同時表示色を超え
る色数を有する画像を画質劣化させることなく表示する
目的で、少ない記憶容量でもって、かつ高速に色画像を
量子化する装置に係る。

Ｂ、従来技術及びその問題点 近年、色ルックアップ・テーブル（ＬＵＴ）方式を採用
したカラー表示装置が一般化してきている。第１２図は
、色ＬＵＴ方式の概要を示す。この図において、もし、
フレーム・バッファに、画像データの赤、緑、青成分の
強度を全て格納することができれば、色ＬＵＴは不必要
となり、フレーム・バッファから読み出したデータをそ
のままカラー表示装置のビデオ信号とすれば良い。しか
し、たとえば赤、緑、青成分の各々を８ビツトで表現し
たと仮定すると、画像データの一画素に対して２４ビツ
トも必要となり、フレーム・バッファの記憶容量が膨大
で費用も割高となる。

そのため、最近では、色ＬＵＴを利用して、フレーム・
バッファの内容を色ＬＵＴの色インデックスとして使用
し、その色インデックスで示された色ＬＵＴの赤、緑、
青成分の各内容を読み出し、カラー表示装置のビデオ信
号としている。したがって、フレーム・バッファの画素
データは、色ＬＵＴのエントリー数だけあれば充分とな
る。たとえば、色ＬＵＴのエントリー数、すなわちカラ
ー表示装置の同時表示色数が２５６の場合、フレーム・
バッファの画素データは、８ビツト（１バイト）で表現
することができる。

現在、色ＬＵＴ方式カラー表示装置では、同時表示色数
が８色、１６色、３２色、２５６色などのものがある。

このようなカラー表示装置に、その表示装置の同時表示
色数よりも充分に多い色数を有する色画像（たとえば、
赤、緑、青成分の強度を各々８ビツトで表現した色画像
では、約１６７０万色を有する）を表示する場合に、極
力画質を劣化させることなく、最適な同時表示色を選定
し、色画像の原始色をこれら選定された同時表示色に適
切にマツピングさせる技術が重要となる。

この技術のことを色画像の量子化という。

Ｐ、Ｈｅｃｋｂｅｒｔ　”Ｃ０ＬＯＲＩＭＡＧＥ　ＱＬ
ＩＡＮＴＬＺＡＴＩＯＮ　ＦＯＲＦＲＡ門Ｅ　　ＢＵＦ
ＦＥＲＤＩＳＰＬＡＹ　　”　　ＡＣＭ　　５ＩＧＧＲ
ＡＰＨ’　　８　２　　。

２９７〜３０７頁、１９８２年、７月に記載されるよう
に、色画像の量子化の手法は、大別すると一様サンプリ
ング法と適応型サンプリング法とに分けられる。−様サ
ンプリング法とは、色空間を等分割し、分割された空間
内にそれぞれ代表色を与えることで量子化するものであ
る。利点はどんな画像に対しても、−度分割された色空
間の各代表色をルックアップテーブルにロードしておけ
ば二度三度とロードしなおす必要がない点にある。

欠点としては、色彩が色空間で等しくばらつかず、部分
的な偏倚のある入力画像では、画質が著しく劣化してし
まう点にある。ここで色空間とは、ＲＣＢ空間（Ｒｅｄ
、　Ｇｒｅｅｎｉ　Ｂｌｕｅ空間）、ＨＬＳ空間（Ｈｕ
ｅ＋Ｌｉｇｈｔｎｅｓｓ、５ａｔｕｒａｔｉｏｎ空間）
、ＣＹＭＢ空間（ｃｙａｎｉＹｅｌｌｏｗ、Ｍａｇｅｎ
ｔａ、Ｂｌａｃｋ空間）、Ｌ＊１１＊Ｖ空間など様々な
ものを含む。

Ｊ、Ｔａｊｉｍａ　”Ｕｎｉｆｏｒｍ　Ｃｏ１ｏｒ　５
ｃａｌｅ　Ａｐｐｌｉｃａｔｉｏｎｓｔｏ　Ｃｏｍｐｕ
ｔｅｒ　Ｇｒａｐｈｉｃｓ、”ＣＯＭＰＵＴＥＲＶＩＳ
ＩＯＮ、ＧＲＡＰ）ＩＩｃｓ、八ＮＯＸＭＡＧＥ　　Ｐ
ＲＯＣＥＳＳＩＮＧ　　ｖｏｌ、２１゜Ｎｏ、３．ｐｐ
、３０５−３２５．１９８３年３月、はＬ＊ｕ＊ｖ空間
の中での一様サンプリングを開示している。Ｌ＊ｕ＊ｖ
空間とは、人間の感じる色差と空間中の距離が対応する
ように作られた色空間で、均等色空間とも呼ばれている
。

一方、適応型サンプリング法とは、入力画像により、ル
ックアップテーブルの内容を変更し、それを最もよく表
現できるように量子化する手法である。われわれの興味
は、この適応型サンプリング法の色画像の量子化法であ
る。これまで多くの適応型サンプリング法が提案されて
きたが、いずれも次の４つのステップで量子化される。

但し、一般性を失うことなく、入力画像はＲＧＢ空間で
定義されているものとする。

しステップ１］：ＲＧＢ各ｎビットで表現された入力画
像を、ＲＯＢ各ｍビット （一般にｍ＜＝ｎ）の空間でサ ンプリングし、ヒストグラムを 作成する。

［ステップ２］　ニルツクアップテーブルにロードすべ
き色（ｋ個）を選択する。

（一般に２３″＞＝ｋ） ［ステップ３］　：サンプリングされたＲＧＢｍピント
の空間から、ルックアップ テーブルへのマツピングを行な う。

［ステップ４］二人力画像の各画素に対応するルックア
ップテーブルの色を割当 てる。

これらのステップのうち、画質を左右するのは、［ステ
ップ２］以降であるが、量子化そのもののキーとなるの
は、しステップ２］と［ステップ３］である。つまり、
［ステップ２］で代表色に個を選び、［ステップ３コで
残る色を、代表色に個の中から“近いパ色を探しだし割
当てるところまでで、量子化のよしあしが決まる。なお
［ステップ４］では多くの場合、量子化の誤差を利用し
た誤差拡散法、あるいはデイザ法（ランダムノイズ法）
を併用することが多い。

［ステップ２コに関し、これまでの手法を列挙すると以
下のようになる。まず、Ｐ、Ｈｅｃｋｂｅｒｔ“Ｃ０Ｌ
ＯＲＩＭＡＧＥ　Ｑ［ＩＡＮＴＩＺＡＴＩＯＮ　ＦＯＲ
ＦＲＡＭＥ　ＢＵＦＦＥＲＤＩＳＰＬＡＹ”ＡＣＭ　５
ＩＧＧＲＡＰＩ（１９８２年７月ではＰｏｐｕｌａｒｉ
ｔｙ　Ａｌｇｏｒｉｔｈｍと、Ｍｅｄｉａｎ　Ｃｕｔ　
Ａｌｇｏｒｉｔｈｍが開示されている。前者はヒストグ
ラムを頻度の多い順にソーティングし、ｋ個の色をその
上位より順に代表色として選ぶ方法である。この手法は
簡単である反面、頻度がほぼ等しいような色が多く分布
する場合に、著しく画質が劣化するという大きな欠点を
有する。

一方、後者はＲ，Ｇ、Ｂ各方向の最小値と最大値を計算
し、この中間値で空間を再帰的にスプリットしていく方
法である。スプリットする際、ＲＣＢ各成分方向で、最
大値、最小値を求める分だけ余分な時間を費やし、また
、中間値を実数で与えると実数計算が入り、処理速度が
低下する。それを整数で与えた場合は、切捨にしても四
捨五入にしても誤差が入りこむ欠点を有する。

Ｙ、　Ｔｏｚａｗａは、米国特許第４６５４７２０号の
明細書にてＰｏｐｕｌａｔｉｏｎ　Ｅｑｕａｌｉｚａｔ
ｉｏｎ　Ａｌｇｏｒｉｔｈｍを開示している。これは、
代表色に個を色空間中での頻度ができるだけ等しくなる
ような近傍空間を求めながら選定する方法である。この
方法によれば、画質は優れるが、入力画像によっては、
近傍空間のマージに多くの時間を費やすと共に、きわめ
て、多くの作業域（ストーレッジ）を必要とする欠点が
ある。

Ｓ、ｒｗａｉ　とＳ、　Ｕｎｏは、米国特許第４７１０
８０６号の明細書にてＦｉｘｅｄ　Ａｒｅａ　＋　Ｃｈ
ｒｏｍａｔｉｃｉｔｙＢａｓｅｄ　Ａｌｇｏｒｉｔｈｍ
を開示している。これは、カラールックアップテーブル
の中に、あらかしめ固定領域を設けておき、まずこれと
同値なものをヒストグラムから除去しておいてから、Ｒ
ＧＢＯ比（色度）に基づくヒストグラムを生成し、そこ
に現れるピーク値によって代表色を求めていく方法であ
る。人間の目が明度に敏感である特性を活かし、色度が
一定で明るさの変化する領域を中心とした色を選ぶ点に
特徴がある。固定領域の有無は入力画像に依存するため
、利点になることも欠点になることもある。しかし、色
度用のヒストグラム作成、ピークの検出といった一連の
プロセスで、実数計算（特にａｒｃ　ｃｏｓｉｎｅなど
の角度計算）が入るため、処理速度がきわめて遅いとい
う欠点がある。

一方、［ステップ３］に関しては、残る色のうち、ヒス
トグラムに１個以上のエントリのあるものは、近傍の代
表色を探す必要がある。Ｙ、Ｔｏｚａｗａ手法では、こ
れを距離的に１近傍、２近傍、・・・と増やしながらマ
ージしつつ処理していく。その他の手法では、何らかの
距離（たとえばＲＧＢ空間でのユークリッド距離）のメ
ジャーを導入することで、近傍の代表色を探すようにな
っている。通常、この近傍を発見するための距離計算は
、時間を費やすプロセスである。

Ｃ０発明が解決しようとする問題点 この発明は、従来の適応型サンプリング法におけるステ
ップ２およびステップ３を共に高速に処理する手段を提
供する。その手段による量子化の処理時間および処理に
必要な記憶容量は、カラー表示装置の同時表示色の数に
のみ比例し、原画像に固有の色数および色の分布には影
古されない。

また、その手段の実現に必要な記憶容量は小さくて良い
ため、パーソナル・コンピュータ上でも動作する。

Ｄ１問題点を解決するための手段 本発明による色画像量子化方法及び装置は、基本となる
ａ種類の成分の各強度の諸段階を表現するために、ｎｉ
（１≦ｉ≦ａ）ビットを割り当て任意の色が割り当てら
れた多数の画素からなる原始画素を上記に個の表示色を
用いて表示するべく色画像を量子化するために、次のよ
うなステップを実行する。

（ａ）上記原始画像を入力して、上記８種類の成分の各
強度の諸段階を表現するためにｍｉ　　（ｍｉ≦ｎｉ）
ビットを割り当てることにより規定される色空間で、上
記原始画像をサンプリングし、ａ次元のヒストグラムを
作成する。

（ｂ）色空間をＸ個の色空間に分割することを繰り返し
、 その際、分割により生成された子空間の各々について、
核子空間に含まれる色に割り当てられた画素の個数を、
上記ヒストグラムを参照して計算し、該計算結果に分割
レベルに応じた重みづけ係数を乗じて、子空間の空間支
配数を計算する。

（ｃ）色空間同士の親子関係を記述する木構造のリスト
を用意し、色空間の分割が行われる度に、新たに生成さ
れた色空間を登録して該リストを更新する。

（ｄ）木構造リストの終端に位置する色空間を空間支配
数の大きさの順にに個選択して代表色空間とする。

（ｅ）上記に個の代表色空間の各々について、該色空間
を代表する色を選択し、かつ該代表色にインデックスを
付与する。

Ｃｆ）上記に個の代表色空間内の代表色以外の色につい
ては、該空間の代表色に付されたインデックスを付与し
、 上記木構造リスト中の、上記代表色空間以外の色空間中
の色については、該色空間の近傍に位置する代表色空間
を発見し、該発見された代表色空間に付されたインデッ
クスを付与する。

（ｇ）上記原始画像の各画素について、該画素に割り当
てられた色に付与されたインデックスを求め、求まった
インデックスを記憶装置に格納する。

上記基本となる８種類の成分は、典型的には赤、緑、青
といった基本色である。しかしながら、本発明の適用範
囲は、色成分のみからなる画像に限られるわけではない
。例えば、リモートセンシングの分野では、地表温度等
の成分を基本成分の中に含めてよい。そういう意味で、
本発明による量子化の対象となる画像は、正確には多次
元多値画像と呼ぶことができよう。しかし、以下では、
便宜上色画像と呼ぶことにする。

Ｅ、実施例 １、概要 本発明は、多次元多値画像に対しても適用できるが、こ
こでは赤、緑、青成分からなる色空間を例にとり、単純
色画像量子化装置として説明する。

本発明による色画像量子化装置の概要を第１図に示す。

本装置は、ヒストグラム生成装置、代表色選択装置、近
傍代表色マツピング装置、インデックス画像生成装置の
大きく４種類の装置からなる。ここでは、表示しようと
する原画像の赤、緑、青成分が各ｎビットであり、色Ｌ
ＵＴ方式の表示装置が、赤、緑、青成分各ｍビットの色
空間からに個の色（以後、代表色と呼ぶ）を選択し、同
時表示できるものとする。本装置では、大きく４つのス
テップにより色画像の量子化を行う。以下にその処理手
順を上記の各装置に関連させて説明する。

１）ステップ１：ヒストグラムの生成 ヒストグラムの生成装置では、表示しようとする原画像
を受けとり、その画像で使われている色の使用頻度を求
め、ヒストグラムを出力する。受けとる原画像は、赤（
Ｒ）、緑（Ｇ）、青（Ｂ）成分各ｎビットで表現されて
おり、出力するヒストグラムは、ＲＧＢ各ｍビット（ｎ
２ｍ）である。

第２図に出力するヒストグラム例を示し第３図にヒスト
グラム生成装置の処理手順を示す。第３図において、Ｎ
は原画像の画素数、Ｒ（ｉ）、Ｇ（ｉ）、Ｂ　（ｉ）は
原画像のｉ番目の画素データＣＲＧＢ各ｎビット）、ｒ
、ｇ、ｂはＲ（ｉ）、Ｇ　（ｉ）、Ｂ　（ｉ）の各デー
タの上位ｍビットだけをとり出したデータ、Ｈ（ｒ、ｇ
、ｂ）は赤、緑、青成分各ｍビットで表現された色空間
における要素（ｒ、ｇ、ｂ）についての使用頻度（カウ
ント数）を示す。ステップ１が終了するとステップ２が
起動される。

２）ステップ２：代表色の選択 ステップ２では、代表色選択装置により赤、緑、青成分
各ｍビットで表現された色空間を再帰的に８分割してい
きながら、最終的にに個の分割された色空間を得て、代
表色を選択する。この時、分割された色空間内に割り当
てられている画素数（使用頻度）ができるだけ等しくな
るように再帰的に８分割する。

これを実現する手法として、分割色空間管理リストと分
割順位管理リストを導入している。代表色の選択手順に
ついて述べる前に、分割色空間管理リストと分割順位管
理リストについて簡単に説明する。なお、いずれのリス
トも記憶装置中に生成される。

２−１）分割色空間管理リスト ここでの実施例では赤、緑、青成分を有する３次元の空
間を扱うので、空間は８分割され、分割色空間管理リス
トは、８分岐（オクト・トリー）構造となる。なお２次
元の場合は、このリストは４分岐（フォード・トリー）
構造、４次元の場合はこのリストは１６分岐構造となる
。

第４図に色空間と８分割され空間との対応関係を示す。

色画像量子化の処理が開始される時点では、赤、緑、青
成分のそれぞれ下限が０、上限が２ｆｆｉ−１の範囲の
値をとる。最初にこの全体の色空間に対して８分割を行
う。簡便のため、この８つの分割された空間に、第４図
に示すような番号付けの慣例に従い、■から■までの番
号を与える。

これらは、それぞれ元の色空間に対して子色空間（子オ
クタント）と呼ぶ。逆にこれらの■から■までの子色空
間に対して元の空間を親色空間（親オクタント）と呼ぶ
。

ここで、ある親色空間の赤、緑、青成分のそれぞれ下限
と上限を（Ｒｍｉｎｉ　Ｒｍａｘ）、（ＧｍｉｎｉＧｍ
ａｘ）、（Ｂｍ　ｉｎ　、　Ｂｍａｘ）で表現するとき
、その子色空間の上限と下限は、下記の規則に従い自動
的に決められる。

■−子オクタント： （Ｒｍｉｎｉ　（Ｒｍｉｎ＋Ｒｍａｘ）／２）　＋　（
Ｇｍｉｎｉ　（Ｇｍｉｎ＋Ｇｍａｘ）／２）（Ｂｍｉｎ
ｉ　（Ｂｍｉｎ＋Ｂｍａｘ）／２）■−子オクタント： （（Ｒｍｉｎ＋Ｒｍａｘ）／２．　Ｒｍａｘ）　、　（
Ｇｍｉｎｉ　（Ｇｍｉｎ＋Ｇｍａｘ）／２）　ｌ（Ｂｍ
ｉｎｉ　（Ｂｍｉｎ＋Ｂｍａｘ）／２）■−子オクタン
ト： （Ｒｍｉｎｉ　（Ｒｍｉｎ＋Ｒｍａｘ）／２）　＋　（
Ｇｍｉｎ＋Ｇｍａｘ）／２．　Ｇｍａｘ）　＋（Ｂｍｉ
ｎｉ（Ｂｍｉｎ十Ｂｍａｘ）／２）■−子オクタント： （（Ｒｍｉｎ＋Ｒｍａｘ）／２＋　Ｒｍａｘ）＋　（（
Ｇｍｉｎ＋Ｇｍａｘ）／２．Ｇｍａｘ）。

（Ｂｍｉｎｉ　（Ｂｍｉｎ＋Ｂｍａｘ）／２）■−子オ
クタント： （Ｒｍｉｎｉ　（Ｒｍｉｎ＋Ｒｍａｘ／２）　＋　（Ｇ
ｍｉｎｉ　（Ｇｍｉｎ＋Ｇｍａｘ）／２）　＋（（Ｂｍ
ｉｎ＋Ｂｍａｘ）　／２＋　Ｂｍａｘ）■−子オクタン
ト： （（Ｒｍｉｎ十Ｒｍａｘ）／２．Ｒｍａｘ）＋　（Ｇｍ
ｉｎｉ（Ｇｍｉｎ＋Ｇｍａｘ）／２）　ｌ（（Ｂｍｉｎ
＋Ｂｍａｘ）　／２．　Ｂｍａｘ）■−子オクタント： （Ｒｍｉｎｉ　（Ｒｍｉｎ＋Ｒｍａｘ／２）　＋　（（
Ｇｍｉｎ＋Ｇｍａｘ）／２．　Ｇｍａｘ）（（Ｂｍｉｎ
＋Ｂｍａｘ）／２．　Ｂｍａｘ）■−子オクタント： （（Ｒｍｉｎ＋Ｒｍａｘ）／２．Ｒｍａｘ）、　（（Ｇ
ｍｉｎ＋Ｇｍａｘ）／２．Ｇｍａｘ）（（Ｂｍｉｎ＋Ｂ
ｍａｘ）　／２＋　Ｂｍａｘ）それぞれの子色空間は、
更に８分割の対象となる。分割に伴い子色空間の下限と
上限の差は、どんどん狭まっていく。こうして、全体と
して第５図に示す階層構造ができあがる。この階層構造
を管理するリストが分割色空間管理リストである。

分割色空間リストの各要素（ノード）は、各子色空間を
管理する情報として、 ■階層構造の深さ（レベル）、 ■子色空間の赤、緑、青成分の上限及び下限、■空間支
配数、 ■カラー・ルックアップ・テーブル（ＬＵＴ）の色イン
デックス、 ■代表色の色（赤、緑、青）、 ■親色空間へのポインター ■８つの子色空間へのポインター を持っている。

■の階層構造レベルは、一番深い所でｍまでの値をとる
。レベルｍでは■における上限と下限の値は、一致する
。これは、レベルｍではそれ以上空間が分割されないこ
とを意味する。■の空間支配数はステップ１で求めたヒ
ストグラムの使用頻度に■の階層構造の深さ（レベル）
に応じて決められた重みづけ係数を乗じて求めることが
できる。

第６図に、ｍ＝４の場合の重みづけ係数の規則の１例を
示す。■のカラーＬＵＴの色インデックスおよび■の代
表色の色は、ステップ２あるいはステップ３で設定され
る。■と■のポインターは、親色空間が８つの子色空間
に分割される時、第４図に示した番号付けの規則に従い
、親色空間と子色空間を接続するためのポインターと、
逆に分割によって生成された子色空間から親色空間がす
ぐに参照できるようにするための逆ポインターである。

なお、子色空間をもたない場合、■のポインターは全て
空（ＮＵＬＬ）である。また、■の空間支配数が０とな
る場合は、その色空間を管理するためにメモリを割当て
ず、空（ＮＵＬＬ）扱いとする。したがって、■の子色
空間へのポインターの中には、空（ＮＵＬＬ）のものが
ありうる。

２−２）分割順位管理リスト 分割順位管理リストは、色空間を再帰的に８分割してい
く時にどの空間を次に８分割するかを決定するために用
いられる。

第７図に分割順位管理リストを示す。本リストの各要素
は、色空間を８分割した時に常に空間支配数が多い順に
並べかえられる。そのため、本リストの各要素（ノード
）には、 ■分割色空間管理リスト中の対応する色空間要素（ノー
ド）へのポインター ■分割支配数が自分よりも少なく、かつ自分に最も近い
要素（ノード）へのポインター■分割支配数が自分より
も大きく、かつ自分に最も近い要素（ノード）へのポイ
ンターの３種のポインターを持っている。

２−３）代表色の選択手順 第８図は色空間が分割されていく過程をわかりやすいよ
うに２次元的に示したものである。第８図の分割色空間
内の数字は、空間支配数の例を示す。

まず最初に、色空間が４分割され、４つの子色空間が生
成される。この時、前述の分割色空間管理リストが生成
されると同時に、第９図に示す分割順位管理リストが生
成され、要素が空間支配数の大きい順番で並べられる（
第８図および第９図のｐｒｏｃ−１）。

次に、分割順位制御ポインター（ｃＰＴＲ）が示す、分
割順位管理リストの先頭にある、すなわち空間支配数の
最大の子色空間（Ａ）が分割対象として選択され、４分
割される。上記と同様に、分割色空間管理リストが更新
されると同時に、分割順位管理リストもその要素が空間
支配数の大きい順番に並べかえられて更新される（第８
図および第９図のｐｒｏｃ−２）。このような４分割処
理が、分割色空間の数かに個（代表色の数）になるまで
再帰的に続けられる。

ｋが非常に大きな数であるときには、分割順位管理リス
トに登録された色空間の数がｋに達した時点で色空間の
分割を停止し、続いてステップ３、ステップ４に移行し
ても差し支えない。

しかし、画質のより一層の向上を目指すため、以下では
、色空間の分割及び分割色空間管理リストと分割順位管
理リストの更新をさらに繰り返す。

分割色空間の数かに個より多くなった時、第１０図に示
すように、順位が（ｋ＋１）以後の分割色空間は、分割
順位管理リストから削除される。

また、分割色空間の数かに個より多くなった後は、分割
すべき子色空間は次のように選択される。

まずＣＰＴＲが示す分割順位管理リストの先頭にある子
色空間（第１０図中のＰ）を４分罰したと仮定した時、
その４個の子色空間の空間支配数の最大値が、現在の分
割順位管理リストの末尾の子色空間（Ｒ）の空間支配数
よりも大きい場合、その分割順位管理リストの先頭にあ
る色空間（Ｐ）が４分割される。しかし、そうでない場
合は、ＣＰＴＲが２番目の子色空間（Ｑ）に移動し、２
番目の子色空間（Ｑ）が分割対象として選択され４分割
される。同様な処理を繰り返し、ＣＰＴＲかに番目の子
色空間Ｒを指すようになった時点で、ステップ２の処理
は完了する。

代表色選択装置は、このステップ２において生成された
最終の分割順位管理リストのに個の子色空間の各々に含
まれる色のなかから、代表色を求めると同時に、分割色
空間管理リストの中の対応するに個の子色空間（ノード
）に代表色の色インデックスを設定する。また、代表色
とインデックスの対応表である色ルックアップ・テーブ
ル（ＬＵＴ）を生成する（第１１Ａ図参照）。ヒストグ
ラムの対応するエントリにも、色インデックスが設定さ
れる。

３）ステップ３：近傍の代表色へのマツピング近傍代表
色マツピング装置により、原画像の色にもつとも近い代
表色を決定し、ステップ１で生成したヒストグラムに代
表色のインデックスを設定する（第１１Ｂ図参照）。ス
テップ３は、次の大きな２つのプロセスから成る。

３−１）−プロセス１ 生成された分割色空間管理リストの中の子供のボ０ンタ
を持つ非終端の親色空間に対して、その子供の色空間で
あって代表色を持つもののうち、空間支配数が最大のも
のの代表色の色インデックスをその親色空間の色インデ
ックスとして設定することを再帰的に行う。

３−２）プロセス２ ステップ１で生成したヒストグラムのエントリのうち、
使用頻度数が非零で、かつ代表色とじて選ばれなかった
ものについて、マツプすベキ近傍の代表色を次のように
求める。

ａ）まず、兄弟色空間（親色空間が同じ子色空間同志）
の中で代表色として選ばれたものがあれば、その代表色
の色インデックスを与える。

ｂ）もし、それがない場合、プロセス１で設定した親色
空間の代表色の色インデックスを与える。

Ｃ）このようにして、分割色空間管理リストの各ノード
、つまり各色空間に１つの色インデックスが付与された
。後は、ヒストグラム中の使用頻度が非零の各エントリ
について、分割色空間管理リストをトラバースすること
により、該エントリの色が属する終端ノードを発見し、
該ノードに付与されているインデックスを当該エントリ
にセットすればよい。

４）ステップ４：インデックス画像生成インデックス画
像生成装置により、ステップ３で生成した代表色のイン
デックスをともなうヒストグラムを参照して原画像の各
画素の色を代表色のインデックスに置換し、インデック
ス画像（画素シーケンスをインデックス・シーケンスと
して表わしたもの）を生成する。

■、より具体的な実施例 ここでは、前述の実施例のステップ２の代表色選択装置
およびステップ３の近傍代表色マツピング装置をより詳
細に説明する。なお、以下で述べるプロセッサは、専用
のハードウェアで構成されてもよいし、ソフトウェアの
ルーチンとして構成されてもよい。

１）ステップ２：代表色の選択 第１３図に代表色選択装置のより詳細な手順を示す。代
表色選択装置には６個のプロセッサがある。それぞれの
プロセッサの入力信号、出力信号、処理手順を示す。

■プロセッサ２−１（分割子色空間の生成プロセッサ） プロセッサ２−１は、入力信号として、分割対象の分割
色空間データとヒストグラムを受は取り、出力信号とし
て子色空間データを出力するプロセッサである。入力信
号及び出力信号の中身は、それぞれ下記のように与えら
れる。

（入力信号）二分割対象の分割色空間をθ、７で表わす
。

（１）θ８．．のレベル（整数値データ）（２）θ、０
のＲ＋ａｔｎ　、ＲＭｍｘ　　（整数値データ）（３）
θ、ｎのＧ　１ｊｉｌ’ｌ　、ＣＩＩＩＩＩＸ　　（整
数値データ）（４）θ８ｎのＢ　＠ｉｌ’ｌ　、Ｂ１１
１ａＫ　　（整数値データ）（５）３次元ヒストグラム
Ｈ（ｒ、ｇ、ｂ）（整数値データ） （出力信号）：１番目（１≦ｊ≦８）の子色空間をθ。

ｕｔ　（Ｊ）で表わす。

ｊ＝１から８について以下のものが出力される。

（１）θ。ｕｔ　（Ｊ）のレベル （２）θｏｕｔ　（ｊ）のＲ１ｌｉｌｌ　、ＲＩＩＩＩ
ＩＸ（３）θｏｕｔ　（Ｊ）のＧ　ｍｉｎ　、Ｇｍ１ａ
Ｋ（４）θ。ｕｔ（ｊ）のＢｍ（ｎｉＢｍｍ、（５）θ
ｏｕｔ　（Ｊ）のヒストグラムのカウント数、つまり、
色の使用頻度総数（整数値データ）プロセッサ２−１の
ＣＰＵでは、次の演算が実行される。

（ｉ）θ。ｕｔ　（ｊ）のレベルの計算（ｉｉ）θｏｕ
ｔ　（ｊ）のＲｆｆ１ｉｌｌ　、ＲｌｊａＸ　％　Ｇ１
１ｌｉｌｌ、Ｇ　Ｍｌ８、Ｂ１８０、Ｂ１１１ｌｌＸの
計算（ｉｉｉ）θ。ｕｔ（ｊ）の色の使用頻度総数計算
（ｉ）の演算の手順を第１４図に示す。

（ｉｉ）の演算の手順に使用する回路を第１５図に示す
。

筒便に入力信号列を順番に（ｉ、ｊ、に、ＳＷ）の４つ
組で示し、出力信号列を２つ組（（ｋ。

（ｉ＋ｊ）／２）または（（ｉ＋ｊ）／２．ｋ）で表わ
す。これらを用いると、（ｉｉ）の全体的な演算プロセ
スは次のように与えられる。（矢印の左側が出力列、右
側が入力列を表わす。）θｏｕｔ　（１）の（Ｒｍｉｎ
ｉＲｍａｘ）　＝　（θ、のＲｍｉｎ。

θｉ、ｌのＲｍａｘ、　　θｉ７のＲｍｉｎｉ　ＯＮ　
）（ＧｍｉｎｉＧｍａｘ）　＝　（θ、のＧ　ｍ　ｔ　
ｎ　＋θ□７のＧｍａｘ、　　θ、０のＧｍ１ｎｉ　Ｏ
Ｎ　）（ＢｍｉｎｉＢｍａｘ）　＝　（θ１ｏのＢｍｉ
ｎ。

θ、７のＢｍａｘ、　　θｉｎのＢｍｉｎｉ　ＯＮ　）
θｏｕｔ　（２）の（ＲｍｉｎｉＲｍａｘ）　−（θ、
７のＲｍｉｎ。

θｉｎのＲｍａｘ、　　θｉ、ｌのＲｍａｘ、　ＯＦＦ
）（ＧｍｉｎｉＧｍａｘ）　←（θ、のＧｍ１ｎ＋θ、
のＧｍａｘ、　　θ□７のＧｍｔｎ＋　ＯＮ　）（Ｂｍ
ｉｎｉＢｍａｘ）　”−（θ、、のＢｍｉｎ。

θｉ、ｌのＢｍａｘ、　　θ、のＢｍｉｎｉ　ＯＮ　）
θ。ｕＬ（３）の（ＲｍｉｎｉＲｍａｘ）　←（θｉｎ
のＲｍｉｎ。

θｉｎのＲｍａｘ、　　θｉｒ＋のＲｍｉｎｉ　ＯＮ　
）（ＧｍｉｎｉＧｍａｘ）　←（θ、ｌｌのＧｍ１ｎθ
、ｆｉのＧｍａｘ、　　θ、のＧｍａｘ、　ＯＦＦ）（
ＢｍｉｎｉＢｍａｘ）　−（θＩ７のＢｍｉｎθｉｎの
Ｂｍａｘ、　　θ、。のＢｍｉｎｉ　ＯＮ　）θｏｕｔ
　（４）の（ＲｍｉｎｉＲｍａｘ）　＝（θｉのＲｍｉ
ｎ。

θｉｎのＲｍａｘ、　　θｉのＲｍａｘ、　ＯＦＦ）（
ＧｍｉｎｉＧｍａｘ）　←（θ８．ｌのＧｍ１ｎ。

θ０，１のＧｍａｘ、　　θ、７のＧｍａｘ、　ＯＦＦ
）（ＢｍｉｎｉＢｍａｘ）　’−（θｉのＢｍｉｎ。

θ、１．のＢｍａｘ、　　θｉｎのＢｍｉｎｉ　ＯＮ　
）θ、、Ｌ（５）の（ＲｍｉｎｉＲｍａｘ）　−（θｉ
、ｌのＲｍｉｎ。

θ、７のＲｍａｘ、　　θ、７のＲｍｉｎｉ　ＯＮ　）
（ＧｍｉｎｉＧｍａｘ）　←（θ□７のＧｍ１ｎ。

θ８ｎのＧｍａｘ、θ、のＧｍ１ｎｉ　ＯＮ　）（Ｂｍ
ｉｎｉＢｍａｘ）　＝　（θｒｎのＢｍｉｎ。

θｉｎのＢｍａｘ、　　θｉｎのＢｍａｘ、　０ＦＦ）
θｏｕｔ　（６）の（ＲｍｉｎｉＲｍａｘ）　←（θ、
のＲｍｉｎθ１１のＲｍａｘ、　　θ、Ｉ、のＲｍａｘ
、　ＯＦＦ）（ＧｍｉｎｉＧｍａｘ）　＝　（θ、のＧ
ｍ１ｎ。

θｉ７のＧｍａｘ、　　θｉ、、のＧｍ１ｎｉ　ＯＮ　
）（ＢｍｉｎｉＢｍａｘ）　−（θｉｎのＢｍｉｎθｉ
ｎのＢｍａｘ、　　θ、０のＢｍａｘ、　０ＦＦ）θｏ
ｕｔ　（７）の（ＲｍｉｎｉＲｍａｘ）　←（θ、７の
Ｒｍｉｎ＋θ、７のＲｍａｘ、　　θ、のＲｍｉｎｉ　
ＯＮ）（ＧｍｉｎｉＧｍａｘ）　←（θ□７のＧｍ１ｎ
。

θ、ｎのＧｍａｘ、　　Ｇ１゜のＧｍａｘ、　ＯＦＦ）
（ＢｍｉｎｉＢｍａｘ）　←（θｉｎのＢｍｉｎ。

θｉ、ｌのＢｍａｘ、　　θ、のＢｍａｘ、　０ＦＦ）
θ、、Ｌ（８）の（ＲｍｉｎｉＲｍａｘ）　４−　（Ｇ
８、のＲｍｉｎθ１のＲｍａｘ、　　θ、のＲｍａｘ、
　ＯＦＦ）（Ｇｍｉｒ＋、Ｇｍａｘ）　←（Ｇ８、のＧ
ｍ１ｎθ□７のＧｍａｘ、　　θ、７のＧｍａｘ、　Ｏ
ＦＦ）（ＢｍｉｎｉＢｍａｘ）　←（θｒ、ｌのＢｍｉ
ｎθｉｎのＢｍａｘ、　　θｉ＋ｓのＢｍａｘ、　０Ｆ
Ｆ）（ｉｉｉ）の演算は（ｉｉ）の出力信号を用いて第
１６図に示す手順で処理する。

■プロセッサ２−２（分割順位管理リスト挿入ソートプ
ロセッサ） プロセッサ２−２は、入力信号として、挿入の対象とな
る分割色空間を受けとり、出力信号として分割色空間を
挿入した分割順位管理リストを生成する。

（入力信号）：挿入対象分割色空間をθｉで表わす。

（１）θ、、、のレベル（整数値データ）・・・・・・
（］ｅｖｅｌ＝ｎで表す） （２）θ、７の色の使用頻度総数（整数値データ）（３
）θｉ、のＩＤ（整数値データ） （４）ｍ（ヒストグラムのビット数値のデータ）（５）
　Ｎ１ｆｉ（分割順位管理リストのエントリ数：挿入前
） （出力信号）： （１）　Ｎ、ｕＬ　　（分割順位管理リストのエントリ
数：挿入後） （２）　　ＩＤ　　（ｉ）　　　（リストのｉ番目（１
≦ｉ≦Ｎ、、ｔ）の子色空間のＩＤ ：整数値データ） （３）ＶＡＬ　（ｉ）（リストのｉ番目の子色空間の空
間支配数） 但し、ＶＡＬ　（ｉ）は、その値が大きい順にソートさ
れた整数値データである。“空間支配数′”とは次式で
与えられるものである。

空間支配数＝（その分割色空間に含まれる色の使用頻度
の総数）×（その分割 色空間のレベルに応じた重みづ け係数） 重みづけ係数は、ＲＧＢ空間の各軸方向について、ｍビ
ットの空間分割に対応するように、その分割色空間のレ
ベルに応じて（ｍ　＋　１−１ｅｖｅｌ）倍の重みづけ
を与える。つまり、その軸方向に完全にｍ等分された状
態（ｍ＝　１ｅｖｅｌ）より何倍広い範囲を保有してい
るかを表わす。実際はＲＧＢ空間が３次元なので、重み
づけ係数は、（ｍ＋　１−］ｅｖｅｌ）　’で定義され
る。

プロセッサ２−２の処理手順を第１７図に示す。

■プロセッサ２−３（分割順位管理リスト末尾エントリ
削除プロセッサ） フロセッサ２−３は、入力信号として、現在の分割順位
管理リストを受けとり、出力信号として、末尾のエント
リの削除された分割順位管理リストを生成する。

（入力信号）： （１）　Ｎｉ、、（分割順位管理リストのエントリ数：
削除前） （２）　　ＩＤ　　（ｉ）　　　（リストのｉ番目（１
≦ｉ≦Ｎ、、）の分割色空間■Ｄ： 整数値データ） （３）ＶＡＬ　（ｉ）（リストのｉ番目の分割色空間の
空間支配数） （出力信号）： （１）　Ｎｏｕｔ （２）　　ＩＤ　　（ｉ） （分割順位管理リストのエン トリ数：削除後） （リストのｉ番目（１≦ｉ≦ Ｎｏｕｔ）の分割色空間ＩＤ ：整数値データ） （３）　ＶＡＬ　（ｉ）　　（リストのｉ番目の分割色
空間の空間支配数） ■プロセッサ２−４（分割順位指示プロセッサ） プロセッサ２−４は、入力信号として、分割順位制御ポ
インタＣＰＴＲと分割順位管理リストを受けとり、出力
信号として分割色空間（オクタント）を生成する。

（入力信号）： （１）ＣＰＴＲ（分割順位制御ポインタ：整数値データ
） （２）Ｎ　　　　　　（分割順位管理リストのエントリ
数：整数値データ） （３）ＩＤ　（ｉ）　　　（リストのｉ番目（１≦ｉ≦
Ｎ）の分割色空間■Ｄ：整 数値データ） （出力信号）：θ。、をＩＤ　（ｃＰＴＲ）の分割色空
間とする。

（１）θ。、のレベル　　　　（整数値データ）（２）
θ。、のＲＩＩ、、　、Ｒ□Ｘ　（整数値データ）（３
）θ。、のＣｒ　ｓｉｎ　、ｃ、、Ｘ（整数値データ）
（４）θ。、のＢａ１ｎｉＢｖａ□　（整数値データ）
（５）θ。、の色の使用頻度総数（整数値データ）■プ
ロセッサ２−５（分割可能性判定プロセッサ） プロセッサ２−５は、入力信号として、分割対象候補と
なる分割色空間、分割順位管理リスト及びヒストグラム
を受は取り、出力信号として、分割可能かどうかの判定
値を生成する。

（入力信号）二分割対象色空間をθｉｎで表わす。

（１）θ、、、のレベル　　（整数値データ）・・・・
・・（ｌｅｖｅｌ　＝ｎで表す） （２）θ、７の色の使用頻度総数（整数値データ）（３
）ｍ　　　　　　（ヒストグラムのビット数値のデータ
） （４）Ｎ　　　　　　（分割順位管理リストのエントリ
数：整数値データ） （５）　　ＩＤ　　（ｉ）　　　（リストのｉ番目（１
≦ｉ≦Ｎ）の分割色空間ＩＤ：整 数値データ） （５）　ＶＡＬ　（ｉ）　　（リストのｉ番目の分割色
空間の空間支配数） （７）　Ｈ（ｒ、ｇ、ｂ）　　（３ｍビットのヒストグ
ラム値データ） （出力信号）：（１）判定値（ＯＮまたは０ＦＦ）処理
の手順は第１８図に示す。第１８図に示すようにプロセ
ッサ２−５はプロセッサ２−１を含む。

■プロセッサ２−６（カラーＬＵＴ生成プロセッサ） プロセッサ２−６は、人力信号として分割順位管理リス
ト、分割色空間管理リスト及びヒストグラムを受けとり
、出力信号として色ルックアップ・テーブルと更新され
た分割色空間管理リストを生成する。

（入力信号）：θ＝　ｎ　（ｊ）をｊ番目の分割色空間
とする。（１≦ｊ≦Ｍ） （１）Ｋ　　　　　　（分割順位管理リストのエントリ
数：整数値データ） （２）ＩＤ（ｉ）　　　（分割順位管理リストのｉ番目
（１≦ｉ≦Ｋ）の分割色 空間ＩＤ：整数値データ） （３）Ｍ　　　　　　（分割色空間管理リストの分割色
空間総数：整数値デー タ） （４）θｔｎ（ｊ）のＩＤ　　　　　（整数値データ）
（５）　Ｈ（ｒ、ｇ、ｂ）　　（ヒストグラム：整数値
データ） （６）θｔ、ｔ（ｊ）のＲ，、、、Ｒイ□＋　Ｇｍ１ｎ
＋　ＧＩＩｍＸ＋ＢＩｌｌｉｌ’ｌ＋　Ｂ１１１ａウ　
　　　　　（整数値データ）（出力信号）：θ。ｕｔ　
（Ｊ）をｊ番目の分割色空間とする。（１≦ｊ≦Ｍ） （１）　Ｒ（ｉ）　　　　（ｉ番目のインデックス（１
≦ｉ≦Ｋ）の赤の値：整数 値データ） （２）Ｇ（ｉ）　　　　Ｃｉｉ番目インデックスの緑の
値：整数値データ） （３）Ｂ（ｉ）　　　　（ｉ番目のインデックスの青の
値：整数値データ） （４）θ。ａｔ　（Ｊ）のインデックス値（整数値デー
タ） ここで、分割色空間管理リストの分割色空間の総数をＭ
で表わしたが、この数は、ヒストグラムＨ（ｒ、ｇ、ｂ
）の非零なエントリ数をＮｅとしたとき、Ｋ≦Ｍ≦Ｎｅ
の関係が常に成立する。

また、出力信号のθ。ｕｔ（ｊ）（１≦ｊ≦Ｍ）のＭ個
の信号のうち、実際に値がセットされるのは、このプロ
セッサでは、Ｋ個だけである。

プロッサ２−６の処理は、次の２つに大別できる。

（ｉ）分割順位管理リストをスキャンし、対応する分割
色空間の色インデックス値をテーブルにセットする。

（１１）分割順位管理リストをスキャンし、対応する色
インデックス値の色データ（ｒ、ｇ、ｂ）をテーブルに
セットする。

実１（ｉ）、（ｉｉ　）は、同時に計算でき、その処理
手順フローを第１９図および第２０図に示す。

第２０図の処理フローによれば、代表色空間の中に含ま
れる色の色データに、その色の使用頻度で重みづけをし
て得た平均値が代表色として求まる。もちろん、代表色
空間の中で使用頻度が最大の色を代表色として選んでも
よいが、画質を考慮すれば、第２０図のような処理の方
が好ましい。

代表色が決まった後、ヒストグラム中の対応するエント
リに色インデックスがセットされる。

２）ステップ３：近傍の代表色へのマツピング第２１図
に近傍代表色マツピング装置の処理手順を示す。本装置
には、２個のプロセッサがある。

以下、それぞれのプロセッサの入力信号、出力信号、処
理手順を示す。

■プロセッサ３−１（親色空間に色インデックスを付与
するプロセッサ） プロセッサ３−１は、入力信号として、分割色空間管理
リストを受けとり、その中の親色空間に対し、子色空間
のうち、空間支配数が最大のものの色インデックスを設
定し、出力信号として更新された分割色空間管理リスト
を生成するプロセッサである。

（入力信号）：θ、０により分割色空間管理リストのル
ートの分割色空間を表わすも のとする。

（１）θ８．．のインデックス値　（整数値データ）（
２）θ８．のＩＤ　　　　　　　（整数値データ）（３
）θｉｎの親色空間フラッグ（整数値データ）（４）θ
、ｎの子色空間ＩＤ　　　（整数値データ）（５）Ｍ（
分割色空間の総数：整数値データ）（人力信号）：θ。

ｕｔ（ｊ）によりｊ番目の分割色空間を表わすものとす
る。（１≦ １５Ｍ） （１）θ。ｕＬ（ｊ）のインデックス値このプロセッサ
は、再帰的な処理により、きわめてシンプルに記述でき
る。人力信号としては、初期値と分割色空間管理リスト
のルートの分割色空間を与えるだけである。以後は、第
２２図のような手順で処理される。ただし、分割色空間
管理リストでは、プロセッサ２−６でセットされたイン
デックス値（１〜にの値）をもつ分割色空間以外のイン
デックス値は、大きな整数がセットされているものとす
る。なお、子供のうちの空間支配数最大のものは、分割
順位管理リストでは先頭に現われるため、インデックス
値が最小のものに対応する。

■プロセッサ３−２（ヒストグラムの色インデックス部
分生成） プロセッサ３−２は、入力信号としてＮｅ個の非零エン
トリを有する色インデックス付ヒストグラム（第１１Ｂ
図）、ｋ＋ｌＵの色インデックスを持つ色ルックアップ
・テーブル及び分割色空間管理リストを受けとり、出力
信号として更新された色インデックス付ヒストグラムを
生成するプロセッサである。

（入力信号）：θ１、により、分割色空間管理リストの
ルートの分割色空間を表わす ものとする。

（１）　Ｈ（ｒ、ｇ、ｂ）　　　　（ヒストグラムの使
用頻度部分：整数値データ） （２）　　Ｉ　（ｒ、ｇ、ｂ）　　　　（ヒストグラム
の色インデンクス部分：整数値デー タ） （３θ、。のインデックス値　（整数値データ）（４θ
、のＩＤ　　　　　　　　（整数値データ）（５θ、７
の親色空間フラッグ（整数値データ）（６θ、１の子色
空間ＩＤ　　　（整数値データ）（７Ｍ　　　　　　（
分割色空間の総数：整数値データ） （８）　Ｒ（ｉ）、Ｇ（ｉ）、Ｂ（ｉ）　　（色ルック
アップ・テーブル：整数値データ） （９）■ぐ　　　　　　（与える色数：整数値データ） （出力信号）： （１）　　Ｉ　（ｒ、ｇ、ｂ）　　　　（色インデック
ス付ヒストグラム（色インデックス 部分）：整数値データ） プロセッサ３−２の処理手順を第２３図に示す。

同図における近傍代表色の色インデックス付与処理は、
前述のように、色インデックスの付与された分割色空間
管理リストをトラバースすることにより行われる。

■、実行例 原画像の画素数２５６、代表色数に＝１０、ヒストグラ
ムをとる色空間の赤、緑、青成分各ビット数ｍ＝４を仮
定した場合のそれぞれのステップの出力結果例を示す。

Ｉ［［−１，ステップ１ 原画像よりヒストグラム（Ｒ，Ｇ、Ｂ各４ビット）を作
成する（第２４図）。

ｍ−ｎｉステップ２ （１）ヒストグラムの非零のもののエントリ数（１５）
が、ｋ（１０）より大きいので、プロセッサ２−１によ
り８つの分割色空間に分割する。

結果を第２５図に示す。このときの分割順位管理リスト
および分割色空間管理リストを第２６図および第２７図
にそれぞれ示す。

（２）Ｎを分割順位管理リストの要素数とする。

Ｎａｋ　（Ｎ＝４、ｋ＝１０）なので、分割処理対象の
色空間として、■の色空間を選択する。そしてこれを８
分割する。但し■−■の記法は親が■の分割色空間であ
り、かつ子が■の分割色空間であることを表すものとす
る。分割した結果を第２８図に示す。

これらの子空間を、プロセッサ２−２により、挿入ソー
トする。分割色空間は、レベルによる重みづけを色の使
用頻度総数に乗じた空間支配数の大きい順に並べる。重
みづけ係数は、第６図に示すルールで与える。

その結果、第２９図に示す分割順位管理リストが得られ
る。（）内は、重みづけ係数を使用頻度合計に乗じた値
（空間支配数）である。

（３）Ｎ＜ｋ　（Ｎ＝８、ｋ＝１０）なので、分割処理
の対象分割色空間として、■の分割色空間を選択し、８
分割する。その結果の分割順位管理リストを第３０図に
示す。

（４）まだＮａｋ　（Ｎ＝９、ｋ＝１０）なので、分割
処理の対象分割色空間として、■−■の分割色空間を選
択し、８分割する。その結果の分割順位管理リストを第
３１図に示す。

（５）Ｎ＝ｋになったので、以降は分割処理においてプ
ロセッサ２−５による分割可能性のチエツクが行われる
。

ＣＰＴＲ≠になので、分割処理の対象分割色空間として
、■−■の分割色空間を選択する。

分割可能性チエツク：■−■を分割したと仮定したとき
、子色空間のうちの 使用頻度が最大のものは、 ■−■−■である。これに 重みづけ係数を乗じた値は、 ８＊５０＝４００で、これ は分割順位管理リストの末 尾のエントリの空間支配数 （８）より大きい。よって 実際に分割する。その時の 分割順位管理リストを第３ ２図に示す。

この時点でＮａｋとなるので、Ｍ＝Ｎ−に個だけ、分割
色空間を分割順位管理リストの末尾よりプロセッサ２−
３によって削除する。つまり■−■−〇のエントリを削
除する。

（６）ＣＰＴＲ≠になので、分割処理の対象分割色空間
として、■−■の分割色空間を選択する。

分割可能性チエツク：■−■を分割したと仮定したとき
、子色空間のうち使 用頻度最大のものは、■ ■−■である。これに重み づけ係数を乗じた値は、８ ＊３０＝２４０で、これは 分割順位管理リストの末尾 のエントリ値（８）より大 きい。よって実際に分割す る。その時の分割順位管理 リストを第３３図に示す。

この時点で、再びＮａｋとなるので、Ｍ＝Ｎｋ（＝２）
個だけ分割色空間を分割順位管理リストの末尾より、プ
ロセッサ２−３により削除する。

（７）全く同様の手順で、■−■、■、■−■■、及び
■−■の分割色空間までを順次分割処理していくと、分
割順位管理リストは第３４図のようになる。

ここまではＣＰＴＲは、常に先頭要素を指している。し
かし、次に■−■−■の分割色空間を選択し、これの分
割可能性チエツクを行うと、仮想子色空間のうち、使用
頻度が最大のものは、■■−■−■であるが、重みづけ
係数を乗じた値は５０にしかならない。これは、分割順
位管理リストの末尾の値（５４）より小さい。よって分
割しない。かくしてＣＰＴＲ−ＣＰＴＲ＋１となり、■
−■−■分割色空間は、最初の出力対象として選定され
たことを意味する。

（８）ＣＰＴＲ（２）≠になので、同様の分割処理を分
割可能性のチエツク付きで行おうとする。

分割可能性チエツクにより、■−■−■及び■−■−■
の各分割色空間は、それ以上分割されないと判断され、
ＣＰＴＲは２回増分され、４となる。

分割色空間■−■は、その仮想子色空間のうち、■−〇
−■の空間支配数が最大（１６０）なので、実際に分割
され、子色空間が分割順位管理リストに挿入ソートされ
る。同じことが分割色空間■−■にもあてはまる。仮想
子色空間■−■−■の空間支配数が１６０なので、空間
■−■は実際に分割されて分割順位管理リストに挿入ソ
ートされる。

この時点で、ＣＰＴＲ以降のリストは、第３５図に示す
ようになる。

（９）以後、ＣＰＴＲの指す分割色空間は、いずれも分
割可能チエツクにてリジェクトされるため、ＣＰＴＲだ
けがどんどん増分され、分割順位管理リスト末尾の分割
色空間■−■まで進む。その結果、ＣＰＴＲ＝にとなる
。最後に、プロセッサ２−６により、分割順位管理リス
トの先頭から順に、対応する分割色空間の代表色（ｒ、
ｇ、ｂ）に対し、色インデックスを与える。

ｍ−ｍ、ステップ３ この時点で第３６図のような分割色空間管理リストが得
られている。

但し一重の円は、各分割色空間を表わし、上段が含まれ
る色の使用頻度総数、下段が色ＬＵＴの色インデックス
を表わす。分割色空間管理リストに納められるのは、実
際には空間支配数であるが、ここでは便宜上、各空間に
含まれる色の使用頻度の総数を記すことにする。二重の
円で示されたのが、ステップ２で求まった分割順位管理
リストに残って事前に色インデックスを割りふられた分
割色空間である。

（１）ステップ３の第１のプロセスは、第３６図の分割
色空間管理リストの各非終端ノードに、その子分別色空
間の中の使用頻度、したがって空間支配数が最大のもの
を再帰的に設定していくプロセスである。第３７図は設
定結果を示す。

（２）ステップ３の第２のプロセスは、第３６図の分割
色空間管理リストのｖ！：端ノードで色インデックスが
まだ設定されてないものに対して、近傍を探しつつ色イ
ンデックスを設定するプロセスである。（距離計算はし
ない。）そのルールは、＜ａ＞兄弟分割色空間をまず探
す。（近い順）＜ｂ＞兄第が全くないか、あるいは兄第
があっても色インデックスの設定されていないものであ
る場合は、上記第１のプロセスで設定された親色空間の
色インデックスを探す。

この例では、＜ａ＞により、設定結果は第３８図のよう
になる。

この時点ですべて色インデックスが求まりくｂ〉に該当
する場合はない。

なお、＜ｂ＞のルールは、エラ一対策用のルールである
。実際は、■−■−■の分割色空間のように、はじめは
兄第（■−■−■）にインデックスが設定されていない
場合でも、第１のプロセスで色インデックスが設定され
るため、＜ｂ＞のルールを適用して親色空間（■−■）
を参照する必要はない。

この後、前述のように、ヒストグラムの非零エントリの
うち、まだ色インデックスが付与されていないものにつ
いて、第３６図ないし第３８図のように決定された分割
色空間管理リストをトラバースすることにより色インデ
ックスを付与し、その色インデックスをヒストグラムに
セットする操作が行われる。

Ｉｆｆ−ＩＶ、ステップ４ 原画像をスキャンしながらそのｒ、ｇ、ｂ値（ステップ
１でヒストグラムのエントリとした４ｂｉｔＯ値）より
、色インデックス付ヒストグラムを参照し、該当するイ
ンデックス値でインデックス画像を作成する。

■、その他 以上、本発明を特定の実施例について説明した。

しかし、本発明に関してはいくつも変形例を考えること
ができる。

例えば、前記実施例では、分割順位管理リストが更新さ
れる度に、その要素を空間支配数の順に並べかえ、分割
順位制御ポインタ（ｃＰＴＲ）はリスト中のできるだけ
先頭の要素、つまり空間支配数が大きいものを指してい
る。しかしながら、必ずしも分割順位管理リストはソー
トされていなければならないわけではない。もっとも、
その場合には、ＣＰＴＲの指す要素を決定する処理が複
雑になる。

また、前記実施例では、ヒストグラムのエントリに対応
する色インデックスのデータを納めるようにしたが、色
と色インデックスの対応表はヒストグラムと別個に作成
してもよい。

また、前記実施例の手順に従って本発明を実施するにし
ても、いくつかのステップはその処理順序を前後させ得
ることは言うまでもない。例えば、ヒストグラムへの色
インデックスのセットは、すべてのエントリーについて
、上記ステップ３で行ってもよい。

分割対象となる色空間が３次元に限らないことは既に述
べた。前記実施例では各基本成分に等しいビット数を割
り当てたけれども、ある基本成分の割当ビット数が他の
基本成分の割当ビット数と異なる色空間を分割対象とし
てもよい。その場合は、当該基本成分の軸方向に関して
は、１回の分割数を２と異なる数にセットしてもよい。

もちろん、前記実施例のような３次元立方体状の色空間
において、１回の分割数を意識的に８と異なる数にセッ
トしてもよい。

Ｆ、効果 本発明によれば、適応型サンプリング法を用いた色画像
量子化方法及び装置であって、処理時間が選択すべき同
時表示色の数によってほぼ決まり、原画像の色数及び色
分布に影響されることのない。

高速の方法及び装置を提供することができる。

代表色選択のために必要な計算はすべて整数演算で行え
ること、及び近傍の代表色にマツピングするために距離
計算が不要であることは、色画像量子化の高速化に寄与
する。

データとして必要とされるものは、ヒストグラム、分割
色空間管理リスト、及び分割順位管理リストだけなので
、記憶容量は小さくてよい。したがって、本発明はパー
ソナル・コンピュータ上でも実現することができる。

また、分割レベルに応じた重みづけ係数を導入して色空
間の分割可能性を判定するようにしたので、原始画像の
色彩が色空間で等しくばらついておらず、局所的なピー
クを多数持つ画像である場合に、色空間中で密度は低い
が広域的に分布する色群を代表する色（アクセントをつ
ける色であることが多い）の脱落を防止することができ
る。したがって、量子化された画像の画質の劣化を防止
することができる。

【図面の簡単な説明】

第１図は、本発明の実施例を絡路的に示す全体構成図、 第２図は、ステップ１により生成したヒストグラムの説
明図、 第３図は、ステップ１のヒストグラム生成手順のフロー
チャート、 第４図は、ＲＧＢ空間と分割色空間の関係の説明図、 第５図は、分割色空間管理リストの概念図、第６図は、
空間支配数を求めるための重みづけ係数の説明図、 第７図は、分割順位管理リストの概念図、第８図は、色
空間の分割過程を２次元的に表わした説明図、 第９図及び第１０図は、分割順位管理リストの生成過程
の説明図、 第１１図は、色インデックス付ヒストグラムと色ルック
アップ・テーブルの説明図、 第１２図は、カラーＬＵＴ方弐のカラー表示装置の概略
図、 第１３図は、ステップ２の処理手順の詳細図、第１４図
は、子色空間の階層構造レベル計算手順（プロセッサ２
−１）の説明図、 第１５図は、子色空間の占める色空間の範囲計算手順（
プロセッサ２−１）の説明図、第１６図は、子色空間内
の色の使用頻度（カウント数）の計算手順（プロセッサ
２−１）の説明図、 第１７図は、分割順位管理リスト挿入ソート手順（プロ
セッサ２−２）の説明図、 第１８図は、分割可能性判定手順（プロセッサ２−５）
の説明図、 第１９図は、色ルックアップ・テーブルの色インデック
スの設定手順（プロセッサ２−６）の説明図、 第２０図は、色ルックアップ・テーブルの色データ設定
手順（プロセッサ２−６）の説明図、第２１図は、ステ
ップ３の処理手順の詳細図、第２２図は、親色空間に色
インデックスを付与する手順（プロセッサ３−１）の説
明図、第２３図は、色インデックス付ヒストグラムの色
インデックス設定手順（プロセッサ３−２）の説明図、 第２４図は、ヒストグラムの１例を示す図、第２５図及
び第２８図は、８分割後の分割色空間データ例の説明図
、 第２６図及び第２９図ないし第３５図は、分割順位管理
リストの生成過程の説明図、 第２７図は、分割色空間管理リスト例の説明図、第３６
図ないし第３８図は、最終的な分割色空間管理リスト例
の説明図である。 出願人　　　　日本アイ・ビ町エム株式会社代理人　　
弁理士　　頓　　宮　　孝 （外　１４５ン （ｍ＝４の堵伺 第７ｆｆｌ 第３ＷＪ 第５図 ＰＴＲ 第１０ｆｆｌ 第１１Ｂ図 孕素ｔＮ、４ 第１３Ｂ図 第１５図 七す′２士カイ１％、に 第１６図 （使用６１覧堕イ非零のものＩミ１ｉなテ、−ｆ）第２
４図 第２５図 第２８図

Claims (4)

【特許請求の範囲】
1. （１）基本となるａ種類の成分の各強度の諸段階を表現
   するために、ｎ＿ｉ（１≦ｉ≦ａ）ビットを割り当てる
   ことにより得られた２＾Σ＾ｎ＾ｉ個の色のうちからｋ
   個の表示色を選択し、上記２＾Σ＾ｎ＾ｉ個の色のうち
   の任意の色が割り当てられた多数の画素からなる原始画
   像を、上記に個の表示色を用いて表示するべく色画像を
   量子化する方法において、 （ａ）上記原始画像を入力して、上記ａ種類の成分の各
   強度の諸段階を表現するためにｍ＿ｉ（ｍ＿ｉ≦ｎ＿ｉ
   ）ビットを割り当てることにより規定される色空間で、
   上記原始画像をサンプリングし、ａ次元のヒストグラム
   を作成し、 （ｂ）色空間をＸ個の子色空間に分割することを繰り返
   し、 その際、分割により生成された子空間の各々について、
   該子空間に含まれる色に割り当てられた画素の個数を、
   上記ヒストグラムを参照して計算し、該計算結果に分割
   レベルに応じた重みづけ係数を乗じて、子空間の空間支
   配数を計算し、 （ｃ）色空間同士の親子関係を記述する木構造のリスト
   を用意し、色空間の分割が行われる度に、新たに生成さ
   れた色空間を登録して該リストを更新し、 （ｄ）木構造リストの終端に位置する色空間を空間支配
   数の大きさの順にｋ個選択して代表色空間とし、 （ｅ）上記ｋ個の代表色空間の各々について、該色空間
   を代表する色を選択し、かつ該代表色にインデックスを
   付与し、 （ｆ）上記ｋ個の代表色空間内の代表色以外の色につい
   ては、該空間の代表色に付されたインデックスを付与し
   、 上記木構造リスト中の、上記代表色空間以外の色空間中
   の色については、該色空間の近傍に位置する代表色空間
   を発見し、該発見された代表色空間に付されたインデッ
   クスを付与し、 （ｇ）上記原始画像の各画素について、該画素に割り当
   てられた色に付与されたインデックスを求め、求まつた
   インデックスを記憶装置に格納することを特徴とする色
   画像量子化方法。
2. （２）基本となるａ種類の成分の各強度の諸段階を表現
   するために、ｎ＿ｉ（１≦ｉ≦ａ）ビットを割り当てる
   ことにより得られた２＾Σ＾ｎ＾ｉ個の色のうちからｋ
   個の表示色を選択し、上記２＾Σ＾ｎ＾ｉ個の色のうち
   の任意の色が割り当てられた多数の画素からなる原始画
   像を、上記ｋ個の表示色を用いて表示するべく色画像を
   量子化する方法において、 （ａ）上記原始画像を入力して、上記ａ種類の成分の各
   強度の諸段階を表現するためにｍ＿ｉ（ｍ＿ｉ≦ｎ＿ｉ
   ）ビットを割り当てることにより規定される色空間で、
   上記原始画像をサンプリングし、ａ次元のヒストグラム
   を作成し、 （ｂ）色空間をＸ個の子色空間に分割することを繰り返
   し、 その際、分割により生成された子空間の各々について、
   該子空間に含まれる色に割り当てられた画素の個数を、
   上記ヒストグラムを参照して計算し、該計算結果に分割
   レベルに応じた重みづけ係数を乗じて、子空間の空間支
   配数を計算し、 （ｃ）色空間同士の親子関係を記述する木構造のリスト
   を用意し、色空間の分割が行われる度に、新たに生成さ
   れた色空間を登録して該リストを更新し、 （ｄ）上記リストが更新される度に、更新された木構造
   リストの終端に位置する色空間を空間支配数の大きさの
   順にに個まで選択し、 （ｅ）空間支配数の大きさの順に、上記選択された色空
   間の各々の分割可能性を、該色空間の空間支配数に基づ
   いて判断し、 分割不可能ならば該色空間をもつて代表色空間に選定し
   、 分割可能ならば該色空間を分割対象として選択し、 （ｆ）代表色空間の個数がｋ個に達した時点で色空間の
   分割を停止し、 （ｇ）上記ｋ個の代表色空間の各々について、該色空間
   を代表する色を選択し、かつ該代表色にインデックスを
   付与し、 （ｈ）上記に個の代表色空間内の代表色以外の色につい
   ては、該空間の代表色に付されたインデックスを付与し
   、 上記木構造リスト中の、上記代表色空間以外の色空間中
   の色については、該色空間の近傍に位置する代表色空間
   を発見し、該発見された代表色空間に付されたインデッ
   クスを付与し、 （ｉ）上記原始画像の各画素について、該画素に割り当
   てられた色に付与されたインデックスを求め、求まつた
   インデックスを記憶装置に格納することを特徴とする色
   画像量子化方法。
3. （３）基本となるａ種類の成分の各強度の諸段階を表現
   するために、ｎ＿ｉ（１≦ｉ≦ａ）ビットを割り当てる
   ことにより得られた２＾Σ＾ｎ＾ｉ個の色のうちからｋ
   個の表示色を選択し、上記２＾Σ＾ｎ＾ｉ個の色のうち
   の任意の色が割り当てられた多数の画素からなる原始画
   像を、上記ｋ個の表示色を用いて表示するべく色画像を
   量子化する装置において、 （ａ）上記原始画像を入力して、上記ａ種類の成分の各
   強度の諸段階を表現するためにｍ＿ｉ（ｍ＿ｉ≦ｎ＿ｉ
   ）ビットを割り当てることにより規定される色空間で、
   上記原始画像をサンプリングし、ａ次元のヒストグラム
   を作成する手段、 （ｂ）（ｂ１）分割対象の色空間が選択される度に選択
   された色空間をＸ個の子色空間に分割し、 （ｂ２）分割により生成された子空間に識別子を付し、 （ｂ３）上記子空間と親空間を対応づけるポインタ・デ
   ータを生成し、 （ｂ４）上記子空間に含まれる色に割り当てられた画素
   の個数を、上記ヒストグラムを参照して計算し、計算結
   果に分割レベルに応じた重みづけ係数を乗じて、子空間
   の空間支配数を計算する手段、 （ｃ）上記（ｂ３）の動作により得られたポインタ・デ
   ータに基づいて上記（ｂ２）、（ｂ４）の動作により得
   られたデータを管理する木構造の第１のリスト、（ｄ）
   色空間の分割が行われる度に、少なくとも空間支配数が
   非零の子空間を上記第１のリストに登録する手段、 （ｅ）生成された色空間の識別子および空間支配数を登
   録する色空間の第２のリスト、 （ｆ）色空間の分割が行われる度に、分割された色空間
   の第２リストへの登録を抹消するとともに、新たに生成
   された色空間を上記第２のリストに登録する手段、 （ｇ）第２のリストに登録された色空間の個数Ｎをカウ
   ントし、Ｎがｋを越えた場合に、空間支配数が最小のも
   のから順に（Ｎ−ｋ）個の色空間の登録を第２リストか
   ら抹消する手段、 （ｈ）上記第２のリストの更新が行われる度に、（ｈ１
   ）更新後の色空間リストに含まれる色空間のうち、分割
   可能であつて、かつ空間支配数が最大のものを分割対象
   として選択し、 （ｈ２）上記カウントＮがｋに達している場合は、選択
   された色空間を分割したならば得られるであろう子空間
   の空間支配数の最大値を計算し、該最大値を現在の第２
   リスト中の色空間の空間支配数の最小値と比較し、該比
   較に基づいて選択された色空間の分割可能性を判断し、 （ｈ３）上記比較の結果該選択された色空間が分割不可
   能と判断された場合、該色空間を分割対象として選択し
   たことを取り消し、その後、上記第２リスト中の残りの
   分割可能な色空間について上記（ｈ１）、（ｈ２）の動
   作を繰り返す手段、 （ｉ）上記第２リスト中の色空間すべてが分割不可能で
   あると判断された場合に、色空間の分割を停止する手段
   、 （ｊ）色空間の分割停止後に、上記第２のリストに登録
   されている色空間の各々について、該色空間を代表する
   色を選択し、かつ該代表色にインデックスを付与する手
   段、 （ｋ）上記第２のリストに登録されている色空間中の色
   については該空間の代表色に付されたインデックスを付
   与し、 上記第２のリストに登録されていない色空間中の色につ
   いては上記第１のリストを走査して該色空間の近傍に位
   置する上記第２リスト中の色空間を発見し、該発見され
   た色空間の代表色に付されたインデックスを付与する手
   段、 （ｌ）上記原始画像の各画素について、該画素に割り当
   てられた色に付与されたインデックスを求め、求まつた
   インデックスを記憶装置に格納する手段、 を有することを特徴とする色画像量子化装置。
4. （４）基本となるａ種類の成分の各強度の諸段階を表現
   するために、ｎビットを割り当てることにより得られた
   ２＾ａ＾ｎ個の色のうちの任意個の色が割り当てられた
   多数の画素からなる原始画像を、上記２＾ａ＾ｎ個の色
   のうちからに個の表示色を選択し、選択された表示色で
   もって表示するための色画像量子化装置において、 （ａ）上記原始画像を入力して、上記ａ種類の成分の各
   強度の諸段階を表現するためにｍ（ｍ≦ｎ）ビットを割
   り当てることにより規定される色空間で、上記原始画像
   をサンプリングし、ａ次元のヒストグラムを作成する手
   段、 （ｂ）（ｂ１）ａ次元の色空間を規則的にＸ等分し、 （ｂ２）分割により生成された子色空間に識別子を付し
   、 （ｂ３）親色空間と子色空間を対応づけるポインタ・デ
   ータを生成し、 （ｂ４）上記分割された子色空間に含まれる色に割り当
   てられた原始画像の画素の個数を、上記ヒストグラムを
   参照して計算し、該計算結果に分割レベルに応じた重み
   づけ係数を乗じて、子色空間の空間支配数を計算する手
   段、 （ｃ）子色空間の空間支配数が平均化するように、空間
   支配数の大きい子色空間をさらにＸ等分し、続けて（ｂ
   ２）、（ｂ３）、（ｂ４）の動作を実行することを繰り
   返す手段、（ｄ）上記（ｂ３）の動作により得られたポ
   インタ・データに基づいて、上記（ｂ２）、（ｂ４）の
   動作により得られたデータを木構造により管理する分割
   色空間管理リスト、 （ｅ）上記手段（ｂ）または（ｃ）による分割が行れる
   度に、少なくとも空間支配数が非零の子色空間を色空間
   要素として上記分割色空間管理リストに登録する手段、 （ｆ）上記手段（ｂ）または手段（ｃ）により分割され
   た色空間の識別子および空間支配数を登録する色空間の
   分割順位管理リスト、 （ｇ）上記手段（ｂ）または手段（ｃ）により色空間が
   分割される度に、新たに生成された色空間を分割順位管
   理リストへ登録するとともに、該リスト中の色空間要素
   を空間支配数が大きい順番にならびかえる手段、 （ｈ）分割順位管理リストに登録された色空間要素数Ｎ
   が上記ｋ個を越えた場合に、空間支配数が最小の色空間
   から順に（Ｎ−ｋ）個の色空間の登録を分割順位管理リ
   ストから抹消する手段、 （ｉ）上記分割順位管理リストの更新が行れる度に、 （ｉ１）更新後の分割順位管理リスト中、ｍ回より少な
   い数の分割回数により生成された色空間であつてかつ空
   間支配数が最大であるものを、上記手段（ｃ）の分割動
   作の対象となる色空間として選択し、あるいは、 （ｉ２）上記分割順位管理リストに登録された色空間要
   素数Ｎがｋに達している場合は、空間支配数が大きい順
   番に、分割対象候補の色空間を選択し、該分割対象候補
   の色空間を仮想的にＸ等分して得られる子色空間の空間
   支配数の最大値を計算し、該最大値を分割順位管理リス
   ト中の色空間の空間支配数の最小値と比較し、前者が後
   者より大きければ該分割対象候補の色空間を上記手段（
   ｃ）の分割動作の対象となる色空間として選択し、 （ｉ３）上記比較の結果前者が後者以下ならば、該分割
   対象候補の色空間は分割不可能であると判断し、その後
   、まだ分割対象候補に選択されていない上記分割順位管
   理リスト中の色空間を対象として上記（ｉ２）の動作を
   繰り返す手段、 （ｊ）上記分割順位管理リスト中のすべての色空間が上
   記手段（ｉ）により分割不可能であると判断された場合
   に色空間の分割を停止する手段、 （ｋ）色空間の分割停止後に、上記分割順位管理リスト
   に登録されている色空間の各々について、該色空間を代
   表する色を選択し、かつ該代表色に色インデックスを付
   与し、色ルックアップ・テーブルを生成する手段、 （ｌ）上記手段（ｊ）により決定された色空間の代表色
   の色インデックスを、分割色空間管理リスト上の対応す
   る色空間にも付与し、分割色空間管理リスト中の子色空
   間を有する親色空間には、その子色空間のうちで空間支
   配数が最大のものの色インデックスを付与することを再
   帰的に行う手段、 （ｍ）上記分割色空間管理リスト中の、まだ色インデッ
   クスを付与されていない色空間について、木構造上該色
   空間の近傍に位置する色インデックス付与済色空間を求
   め、その求まつた近傍色空間に付与されている色インデ
   ックスを、該色インデックス未付与色空間に付与する手
   段、 （ｎ）上記原始画像の各画素について、該画素に割り当
   てられた色が、分割色空間管理リストのどの色空間に属
   するかを求め、その求まつた色空間に付与されている色
   インデックスを表示用メモリに格納する手段、 を有することを特徴とする色画像量子化装置。