(57)【要約】【課題】画像を分割した各小領域に少ない演算量で適切な代表値を割り当てて符号化できる画像符号化方法を提供する。【解決手段】小領域毎の代表値を決定する手順として、小領域内の１つの画素４１を初期選択する第１ステップと、未選択の画素について選択済みの画素それぞれとの色空間上の距離を評価し、最小距離が最大の未選択画素を選択することを、選択済みの画素が必要数になるまで繰り返す第２ステップと、各選択画素の色空間上の位置を夫々クラスタ中心として、当該小領域に属する各画素を最近接のクラスタ中心が同一の画素同士のクラスタに分類する第３ステップと、クラスタ毎に、そのクラスタに属する画素の画像データからそのクラスタの代表値を算出する第４ステップとを有し、代表値が決定済み隣接小領域が存在する場合は、第１ステップにおいて、隣接小領域の決定済み代表値に基づいて初期の画素を選択する。【選択図】図４
2011166450.tif 000002
【特許請求の範囲】
【請求項１】
画像を小領域に分割し、小領域毎に、その小領域に属する画素を所定数のクラスタに分類してクラスタ毎に画素の画像データの代表値を決定し、各画素をその画素が属するクラスタの代表値に対応付けて符号化する画像符号化方法であって、
前記代表値を決定する手順として、
小領域内の１つの画素を選択する第１ステップと、
選択されていない画素について選択済みの画素それぞれとの色空間上での距離を評価して、最小距離が最大の選択されていない画素を選択することを、選択済みの画素が前記所定数になるまで繰り返す第２ステップと、
選択された各画素の前記色空間上での位置をそれぞれクラスタ中心として、当該小領域に属する画素を、前記色空間上で最近接のクラスタ中心が同一の画素同士のクラスタに分類する第３ステップと、
前記クラスタ毎に、そのクラスタに属する画素の画像データからそのクラスタの代表値を算出する第４ステップと、
を有し、
代表値が決定済みの隣接する小領域が存在することを条件に、前記第１ステップにおいて、前記隣接する小領域の決定済み代表値に基づいて前記１つの画素を選択する
ことを特徴とする画像符号化方法。
【請求項２】
前記隣接する小領域の決定済み代表値の中で最大クラスタの代表値に基づいて、前記１つの画素を選択する
ことを特徴とする請求項１に記載の画像符号化方法。
【請求項３】
前記最大クラスタに属する画素の画素数が基準値以上の場合にのみ、前記１つの画素の選択を前記最大クラスタの代表値に基づいて行う
ことを特徴とする請求項２に記載の画像符号化方法。
【請求項４】
前記第２ステップにおける前記繰り返しを、選択済みの画素が前記所定数＋１個になるまで行い、
前記第３ステップにおいて、前記第２ステップで最後に選択した画素を除く所定数の選択された画素の前記色空間上での位置をそれぞれクラスタ中心として前記分類を行い、その結果、前記第１ステップで選択した画素の前記色空間上での位置を最近接のクラスタ中心とするクラスタに属する画素の画素数が所定の下限値以下となった場合は、前記第２ステップで最後に選択した画素の前記色空間上での位置を前記第１ステップで選択した画素に係るクラスタ中心の代替クラスタ中心として前記分類をやり直す
ことを特徴とする請求項１乃至３のいずれか一項に記載の画像符号化方法。
【請求項５】
画像を複数の第１種小領域に分割し、
前記第１種小領域毎に、画像データの符号化を、
該第１種小領域を複数の第２種小領域に分割し、
前記第２種小領域毎に、その第２種小領域に属する画素の画像データを代表する第２種規定数の仮代表値を決定し、
前記複数の第２種小領域に対して決定した前記仮代表値のすべてから、非階層的クラスタ分析によって、前記仮代表値の総数より少なく前記第２種規定数より多い第１種規定数の第１種小領域帰属代表値を決定し、
前記第２種小領域毎に、前記第１種小領域帰属代表値の中から前記第２種規定数の第１種小領域帰属代表値を第２種小領域帰属代表値として選択し、その選択した第１種小領域帰属代表値を指し示す参照情報を求め、
該第１種小領域に属する画素毎に、その画素が属する第２種小領域に係る前記第２種小領域帰属代表値のいずれか１つを選択し、その選択した第２種小領域帰属代表値に対応する参照情報を指し示すラベル情報を求め、
前記第１種規定数の第１種小領域帰属代表値と、前記第２種小領域毎に求めた参照情報と、該第１種小領域に属する画素毎に求めたラベル情報と、を含む符号情報を生成する、
ことによって行い、
前記非階層的クラスタ分析の手順は、
同一の第１種小領域から分割された複数の第２種小領域に対して決定した前記仮代表値のすべてから１つの仮代表値を選択する第１ステップと、
選択されていない各仮代表値について選択済みの仮代表値それぞれとの色空間上での距離を評価して、最小距離が最大の選択されていない仮代表値を選択することを、選択済みの仮代表値が前記第１種規定数になるまで繰り返す第２ステップと、
選択された各仮代表値の前記色空間上での位置をそれぞれクラスタ中心として、各仮代表値を、前記色空間上で最近接のクラスタ中心が同一の仮代表値同士のクラスタに分類する第３ステップと、
前記クラスタ毎に、そのクラスタに属する仮代表値からそのクラスタの代表値を算出し、これを第１種小領域帰属代表値とする第４ステップと、
を有し、
第１種小領域帰属代表値が決定済みの隣接する第１種小領域が存在することを条件に、前記第１ステップにおいて、前記隣接する第１種小領域の決定済み第１種小領域帰属代表値に基づいて前記１つの仮代表値を選択する
ことを特徴とする画像符号化方法。
【請求項６】
画像を多階層に分割して符号化する画像符号化方法であって、
第ｎ種小領域（ｎは１以上の整数）を複数に分割した各小領域を第ｎ＋１種小領域と呼ぶものとして、
画像を複数の第１種小領域に分割し、
前記第１種小領域毎に、画像データの符号化を、
該第１種小領域を、第ｋ種小領域（ｋは３以上の整数）まで分割し、
前記第ｋ種小領域毎に、その第ｋ種小領域に属する画素の画像データを代表する第ｋ種規定数の仮代表値を決定し、
１つの第ｎ種小領域から分割された複数の第ｎ＋１種小領域に対して決定したすべての仮代表値の中から第ｎ種規定数の仮代表値を、非階層的クラスタ分析によって決定することを、ｎ＝ｋ−１からｎ＝１まで繰り返し行い（ただし、第ｎ種規定数＞第ｎ＋１種規定数、かつ、第ｎ種規定数＜１つの第ｎ種小領域から分割された第ｎ＋１種小領域の数×第ｎ＋１種規定数、かつ、第ｎ種規定数＜第ｎ種小領域の画素数、の関係を持つ）、
第１種小領域に対して決定した仮代表値を第１種小領域帰属代表値とし、
第ｎ種小領域に対して、その第ｎ種小領域の分割元の第ｎ−１種小領域に係る第ｎ−１種小領域帰属代表値の中から第ｎ種規定数の第ｎ−１種小領域帰属代表値を第ｎ種小領域帰属代表値として選択し、その選択した第ｎ−１種小領域帰属代表値に対応する第ｎ−１種参照情報を指し示す第ｎ種参照情報を求めることを、ｎ＝２からｋまで行い、
該第１種小領域に属する画素毎に、その画素が属する第ｋ種小領域に係る第ｋ種小領域帰属代表値の中のいずれか１つを選択し、その選択した第ｋ種小領域帰属代表値に対応する第ｋ種参照情報を指し示すラベル情報を求め、
第１種規定数の第１種小領域帰属代表値と、第ｎ種小領域毎に求めた第ｎ種参照情報（ｎ＝２からｋ）と、該第１種小領域に属する画素毎に求めたラベル情報と、を含む符号情報を生成する、
ことによって行い、
前記非階層的クラスタ分析の手順は、
同一の第ｎ種小領域から分割された複数の第ｎ＋１種小領域に対して決定した仮代表値のすべてから１つの仮代表値を選択する第１ステップと、
選択されていない各仮代表値について選択済みの仮代表値それぞれとの色空間上での距離を評価して、最小距離が最大の選択されていない仮代表値を選択することを、選択済みの仮代表値が前記第ｎ種規定数になるまで繰り返す第２ステップと、
選択された各仮代表値の前記色空間上での位置をそれぞれクラスタ中心として、各仮代表値を、前記色空間上で最近接のクラスタ中心が同一の仮代表値同士のクラスタに分類する第３ステップと、
前記クラスタ毎に、そのクラスタに属する仮代表値からそのクラスタの代表値を算出し、これを第ｎ種小領域の仮代表値とする第４ステップと、
を有し、
第１種小領域帰属代表値が決定済みの隣接する第１種小領域が存在することを条件に、前記第１ステップにおいて、前記隣接する第１種小領域の決定済み第１種小領域帰属代表値に基づいて前記１つの仮代表値を選択する
ことを特徴とする画像符号化方法。
【請求項７】
前記隣接する第１種小領域の決定済み第１種小領域帰属代表値の中で最大クラスタの第１種小領域帰属代表値に基づいて、前記１つの仮代表値を選択する
ことを特徴とする請求項５または６に記載の画像符号化方法。
【請求項８】
前記最大クラスタに属する画素の画素数が基準値以上の場合にのみ、前記１つの画素の選択を前記最大クラスタの第１種小領域帰属代表値に基づいて行う
ことを特徴とする請求項７に記載の画像符号化方法。
【請求項９】
前記第２ステップにおける前記繰り返しを、選択済みの仮代表値が前記第１種規定数＋１個になるまで行い、
前記第３ステップにおいて、前記第２ステップで最後に選択した仮代表値を除く第１種規定数の選択された仮代表値の前記色空間上での位置をそれぞれクラスタ中心として前記分類を行い、その結果、前記第１ステップで選択した仮代表値の前記色空間上での位置を最近接のクラスタ中心とするクラスタに属する仮代表値の数が下限値以下の場合は、前記第２ステップで最後に選択した仮代表値の前記色空間上での位置を前記第１ステップで選択した仮代表値に係るクラスタ中心の代替クラスタ中心として前記分類をやり直す
ことを特徴とする請求項５乃至８のいずれか一項に記載の画像符号化方法。
【請求項１０】
前記非階層的クラスタ分析は、画素の色成分を座標変換した座標値に基づいて行う
ことを特徴とする請求項１乃至９のいずれか一項に記載の画像符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像を複数に分割した各小領域を、所定個数の代表値（代表色）で符号化する画像符号化方法に関する。
【背景技術】
【０００２】
画像を符号化して圧縮する方法として、符号化対象の画像を複数のブロック（小領域）に分割し、ブロック毎に符号化するＢＴＣ（Block Truncation Coding）がある。ＢＴＣでは、画像情報を、たとえば、４×４画素の矩形のブロックに分割し、各ブロックに対して少数（たとえば、２個）の代表値（代表色）を割り当てて符号化する。
【０００３】
また、多数の色データからなるカラー画像データを符号化（圧縮）する際、近い色同士をグルーピングし、所定数の代表値（代表色）を定め、それらの代表値で近似することによって減色することが行われる。
【０００４】
上記のようなグルーピングおよび代表値の決定にあたり、従来より以下のような方法が提案されている。
（Ａ）パレットに含まれる色と色との距離を評価し、最も距離が近いもの同士を併合することを繰り返して、所望の色数まで減色する方法（たとえば、特許文献１参照。）。
（Ｂ）色空間分布で、ある部分領域を、その部分領域の代表色とその部分領域に属する画素の色値との距離の累積が小さくなるように分割（距離の分散の大きい部分領域を２分割）する方法（たとえば、特許文献２参照。）。
（Ｃ）ヒストグラム分析よりピークを検出して代表色とし、白黒軸とピーク色の最短距離を結ぶ方向、明度差などを特徴量として、順次ピーク色の併合を行う方法（たとえば、特許文献３参照。）。
【０００５】
ところで、グルーピングに応用可能な統計処理であるクラスタ分析を比較的簡易に実現する方法として、分割数などを与えて全体を一気に分割する非階層的クラスタ分析がある。非階層的クラスタ分析は、一般に、次のようにして行われる。まず、分割数に対応する初期値を選択し、これらの初期値をクラスタ中心として各要素を分類する。次に、各クラスタに属する要素から新たなクラスタ中心を決定し、この新たなクラスタ中心によって分類し直して再度クラスタ中心を求めることを繰り返し行い、クラスタ中心が移動しなくなったとき分類完了とする。
【０００６】
また、非階層的クラスタ分析の変形法として、多色多階調の画像データから少数の代表色を選択する代表色選択方法が特許文献４に提案されている。この方法は、カラー画像の多様な表示色の中から比較的少数の代表色を選択するに当たって、各画素色の色成分によって張られる多次元カラー空間を考え、
（１）画像内の任意の画素色を選び、まず第１の代表色とする、
（２）カラー空間上で、前記第１の代表色から最も遠い距離にある画素色を第２の代表色とする、
（３）これまで選ばれたどの代表色からも最も遠い距離にある画素色を次の代表色とする、
（４）上記（３）の手順を代表色の総数がＲ個となるまで繰り返す、
（５）画像内の全画素を、上記（１）〜（４）の方法で選択されたＲ個の代表色のうち最も距離の近い代表色にそれぞれ割当て、Ｒ個のクラスタに分類する、
（６）代表色の精度を上げるために、（５）によって同じクラスタに分類された画素群のカラー空間内における重心を求め、これを新たな代表色とする、
（７）必要とされる精度に応じて、さらに（５）と（６）の手順を繰り返す、
という手順によってＲ個の代表色を選定し、画像内の全画素をその代表色のいずれかに割り当てる、というものである。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平７−３７０５９号公報
【特許文献２】特開平８−１１５４０５号公報
【特許文献３】特開平２００８−６５８０３号公報
【特許文献４】特開平５−１５９０５０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
代表値（代表色）を選定する上記（Ａ）の方法では、１色ずつ減色してそれを繰り返すため、所謂、階層的クラスタ分析と同様に、最終的な色数が少ないほど演算量が多くなる。上記（Ｂ）の方法では、１つずつ部分領域を増やしながら、全部分領域について分散を評価し、分割する部分領域については最も距離の離れた２色を探索し新たな代表色とするという複雑な手法のため、演算量が多くなる。
【０００９】
上記（Ｃ）の方法では、３次元によるヒストグラム分析を構成要件としており、処理が煩雑になる。また、グルーピング対象となるデータ量がある程度多くないと、適切なピーク検出が困難になる。
【００１０】
このように上記（Ａ）〜（Ｃ）の方法では、ヒストグラム分析を多数繰り返すなど演算が複雑である等のため、ハードウエアで実現する場合には、
・論理的に複雑化で回路規模が大きくなる、
・事前の結果を参照する順次処理のために所要クロック数が多くなる、
といった問題があり、実現が困難なものがほとんどであった。
【００１１】
ところで、予め定めた比較的少ない数に分類する場合は、非階層的クラスタ分析が演算量の観点から好適であるが、非階層的クラスタ分析では、特にデータ数が少ない場合に、初期値の割り振り方によって局所的最適解に陥ってしまう可能性がある。たとえば、図２８（ａ）の４要素を２つのクラスタに分類する場合、初期値として要素ｅ１、ｅ２を選択すると、要素ｅ１とｅ３の第１クラスタと、要素ｅ２とｅ４の第２クラスタに分類され、それらのクラスタ中心はｓ１、ｓ２となり、これらｓ１、ｓ２を新たなクラスタ中心として再分類すると、やはり要素ｅ１とｅ３のクラスタと、要素ｅ２とｅ４のクラスタに分類され、そのクラスタ中心がｓ１、ｓ２となって安定して分類完了となり、同図（ｂ）に示すような最適解を得ることはできない。
【００１２】
図２９（ａ）は、画像データが、非階層的クラスタ分析によって適切に分類された例を示し、図２９（ｂ）は適切に分類ができなかった場合を例示している。図２９（ｂ）では、データ（１，９）（矢印Ａが指し示す画素）は青のクラスタに属するほうが好ましいが、緑のクラスタの中心がデータ（１，９）を含むことでデータ（１，９）に近づいてしまい、微妙に最近接クラスタ中心となってしまっている。データ数が少ないと、１クラスタ当たりのデータ数が少なくなり、このようなことが生じやすくなる。たとえば、画像を複数に分割した小領域単位に代表色を決定する場合、１つの小領域に含まれる画素（画像データ）数が比較的少ないので、上記の問題が生じやすい。
【００１３】
特許文献４に開示された方法においても、第１代表色の選択如何では分類が不適切となる場合がある。また、小領域毎に符号化する場合に、小領域毎に任意の第１代表色を選定すると、第１代表色の選択次第で、同じクラスタに分類されるべき地色部分の画素群に対して、隣接する複数の小領域で異なる代表色が割り当てられてしまい、繰り返し収束処理が不十分の場合には、小領域毎に地色部分の色が微妙に変化してしまうといった問題が生じてしまう。
【００１４】
本発明は、上記の問題を解決しようとするものであり、画像を分割した各小領域を、少ない演算量で適切な代表値を割り当てて符号化することのできる画像符号化方法を提供することを目的としている。
【課題を解決するための手段】
【００１５】
かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
【００１６】
［１］画像を小領域に分割し、小領域毎に、その小領域に属する画素を所定数のクラスタに分類してクラスタ毎に画素の画像データの代表値を決定し、各画素をその画素が属するクラスタの代表値に対応付けて符号化する画像符号化方法であって、
前記代表値を決定する手順として、
小領域内の１つの画素を選択する第１ステップと、
選択されていない画素について選択済みの画素それぞれとの色空間上での距離を評価して、最小距離が最大の選択されていない画素を選択することを、選択済みの画素が前記所定数になるまで繰り返す第２ステップと、
選択された各画素の前記色空間上での位置をそれぞれクラスタ中心として、当該小領域に属する画素を、前記色空間上で最近接のクラスタ中心が同一の画素同士のクラスタに分類する第３ステップと、
前記クラスタ毎に、そのクラスタに属する画素の画像データからそのクラスタの代表値を算出する第４ステップと、
を有し、
代表値が決定済みの隣接する小領域が存在することを条件に、前記第１ステップにおいて、前記隣接する小領域の決定済み代表値に基づいて前記１つの画素を選択する
ことを特徴とする画像符号化方法。
【００１７】
上記発明では、小領域の画素をグループ分けする場合に、初期のクラスタ中心となる１つの画素を選択し、その後は、選択済みすべての画素に対し最も近くない画素をつぎのクラスタ中心に選択することを順次繰り返して必要数のクラスタ中心を求めるので、少ない演算量で必要数の代表値を算出することができる。特に、隣接する代表値決定済みの小領域が存在する場合に、その隣接する小領域の決定済み代表値に基づいて、初期のクラスタ中心を選択するので、代表値の選択において近隣の小領域との関連性を考慮することができ、たとえば、地色が連続するような領域において、隣接する小領域間で色が微妙に変化してしまうといったことが防止される。
【００１８】
［２］前記隣接する小領域の決定済み代表値の中で最大クラスタの代表値に基づいて、前記１つの画素を選択する
ことを特徴とする［１］に記載の画像符号化方法。
【００１９】
上記発明では、隣接する小領域の決定済み代表値の中で最大クラスタの代表値（この代表値を使用する画素数が最大の代表値）に基づいて、初期のクラスタ中心が選択される。すなわち、隣接小領域において最大面積を占める代表値に基づいて初期のクラスタ中心が選択される。
【００２０】
［３］前記最大クラスタに属する画素の画素数が基準値以上の場合にのみ、前記１つの画素の選択を前記最大クラスタの代表値に基づいて行う
ことを特徴とする［２］に記載の画像符号化方法。
【００２１】
上記発明では、各代表値に対応するクラスタサイズが類似し、大きなクラスタサイズの代表値が存在しないような場合には、初期のクラスタ中心は隣接する小領域との関係を考慮しないで定める。たとえば、当該小領域において任意に決定される。
【００２２】
［４］前記第２ステップにおける前記繰り返しを、選択済みの画素が前記所定数＋１個になるまで行い、
前記第３ステップにおいて、前記第２ステップで最後に選択した画素を除く所定数の選択された画素の前記色空間上での位置をそれぞれクラスタ中心として前記分類を行い、その結果、前記第１ステップで選択した画素の前記色空間上での位置を最近接のクラスタ中心とするクラスタに属する画素の画素数が所定の下限値以下となった場合は、前記第２ステップで最後に選択した画素の前記色空間上での位置を前記第１ステップで選択した画素に係るクラスタ中心の代替クラスタ中心として前記分類をやり直す
ことを特徴とする［１］乃至［３］のいずれか一項に記載の画像符号化方法。
【００２３】
上記発明では、クラスタ中心とする画素を予め所定数より１個多く選択しておき、最後に選択したものを除く所定数のクラスタ中心によって分類する。その結果、隣接小領域の決定済み代表値に基づく初期のクラスタ中心を最近接とする画素の数が少ない場合には、初期のクラスタ中心は不適切と判断し、初期のクラスタ中心の代わりに最後に選択したクラスタ中心を採用して再度分類する。
【００２４】
［５］画像を複数の第１種小領域に分割し、
前記第１種小領域毎に、画像データの符号化を、
該第１種小領域を複数の第２種小領域に分割し、
前記第２種小領域毎に、その第２種小領域に属する画素の画像データを代表する第２種規定数の仮代表値を決定し、
前記複数の第２種小領域に対して決定した前記仮代表値のすべてから、非階層的クラスタ分析によって、前記仮代表値の総数より少なく前記第２種規定数より多い第１種規定数の第１種小領域帰属代表値を決定し、
前記第２種小領域毎に、前記第１種小領域帰属代表値の中から前記第２種規定数の第１種小領域帰属代表値を第２種小領域帰属代表値として選択し、
該第１種小領域に属する画素毎に、その画素が属する第２種小領域に係る前記第２種小領域帰属代表値のいずれか１つを選択し、
第１種規定数の第１種小領域帰属代表値と、前記第２種小領域毎に付与する、その第２種小領域に係る第２種小領域帰属代表値に対応する第１種小領域帰属代表値を指し示す参照情報と、該第１種小領域に属する画素毎に付与する、その画素が属する第２種小領域に付与された参照情報のうち該画素について選択した第２種小領域帰属代表値に対応する参照情報を指し示すラベル情報と、を含む符号情報を生成する、
ことによって行い、
前記非階層的クラスタ分析の手順は、
同一の第１種小領域から分割された複数の第２種小領域に対して決定した前記仮代表値のすべてから１つの仮代表値を選択する第１ステップと、
選択されていない各仮代表値について選択済みの仮代表値それぞれとの色空間上での距離を評価して、最小距離が最大の選択されていない仮代表値を選択することを、選択済みの仮代表値が前記第１種規定数になるまで繰り返す第２ステップと、
選択された各仮代表値の前記色空間上での位置をそれぞれクラスタ中心として、各仮代表値を、前記色空間上で最近接のクラスタ中心が同一の仮代表値同士のクラスタに分類する第３ステップと、
前記クラスタ毎に、そのクラスタに属する仮代表値からそのクラスタの代表値を算出し、これを第１種小領域帰属代表値とする第４ステップと、
を有し、
第１種小領域帰属代表値が決定済みの隣接する第１種小領域が存在することを条件に、前記第１ステップにおいて、前記隣接する第１種小領域の決定済み第１種小領域帰属代表値に基づいて前記１つの仮代表値を選択する
ことを特徴とする画像符号化方法。
【００２５】
上記発明では、第１種小領域毎に符号化する際に、第１種小領域をさらに複数の第２種小領域に分割して階層的に符号化する。一般的に、画像データは、より近傍の画素であればあるほど相関性が高い性質がある。そこで、より小さい領域に分割すれば、その範囲での代表値数を少なくしても圧縮歪はそれほど増大することはない。一方、小さい領域毎に代表値を保持すれば、画像全体としては代表値の保持数が増えて、符号量が増大する。
【００２６】
そこで、本発明では、代表値は第１種小領域単位で、たとえば４色の代表値を保持し、この第１種小領域から分割された各第２種小領域は、それぞれ上記４色の代表値の中の２色を選択可能とし、かつその選択した代表値を特定するための情報として第１種小領域単位で保持している代表値を指し示す参照情報を保持する。また、第２種小領域に属する各画素は、その第２種小領域の参照情報（この例では２つ）のいずれかを指し示すラベル情報を保持する。これにより、各第２種小領域において２色を使用可能にしつつ、第１小領域単位での符号量を低減することができる。
【００２７】
［６］画像を多階層に分割して符号化する画像符号化方法であって、
第ｎ種小領域（ｎは１以上の整数）を複数に分割した各小領域を第ｎ＋１種小領域と呼ぶものとして、
画像を複数の第１種小領域に分割し、
前記第１種小領域毎に、画像データの符号化を、
該第１種小領域を、第ｋ種小領域（ｋは３以上の整数）まで分割し、
前記第ｋ種小領域毎に、その第ｋ種小領域に属する画素の画像データを代表する第ｋ種規定数の仮代表値を決定し、
１つの第ｎ種小領域から分割された複数の第ｎ＋１種小領域に対して決定したすべての仮代表値の中から第ｎ種規定数の仮代表値を、非階層的クラスタ分析によって決定することを、ｎ＝ｋ−１からｎ＝１まで繰り返し行い（ただし、第ｎ種規定数＞第ｎ＋１種規定数、かつ、第ｎ種規定数＜１つの第ｎ種小領域から分割された第ｎ＋１種小領域の数×第ｎ＋１種規定数、かつ、第ｎ種規定数＜第ｎ種小領域の画素数、の関係を持つ）、
第１種小領域に対して決定した仮代表値を第１種小領域帰属代表値とし、
第ｎ種小領域に対して、その第ｎ種小領域の分割元の第ｎ−１種小領域に係る第ｎ−１種小領域帰属代表値の中から第ｎ種規定数の第ｎ−１種小領域帰属代表値を第ｎ種小領域帰属代表値として選択し、その選択した第ｎ−１種小領域帰属代表値に対応する第ｎ−１種参照情報を指し示す第ｎ種参照情報を求めることを、ｎ＝２からｋまで行い、
該第１種小領域に属する画素毎に、その画素が属する第ｋ種小領域に係る第ｋ種小領域帰属代表値の中のいずれか１つを選択し、その選択した第ｋ種小領域帰属代表値に対応する第ｋ種参照情報を指し示すラベル情報を求め、
第１種規定数の第１種小領域帰属代表値と、第ｎ種小領域毎に求めた第ｎ種参照情報（ｎ＝２からｋ）と、該第１種小領域に属する画素毎に求めたラベル情報と、を含む符号情報を生成する、
ことによって行い、
前記非階層的クラスタ分析の手順は、
同一の第ｎ種小領域から分割された複数の第ｎ＋１種小領域に対して決定した仮代表値のすべてから１つの仮代表値を選択する第１ステップと、
選択されていない各仮代表値について選択済みの仮代表値それぞれとの色空間上での距離を評価して、最小距離が最大の選択されていない仮代表値を選択することを、選択済みの仮代表値が前記第ｎ種規定数になるまで繰り返す第２ステップと、
選択された各仮代表値の前記色空間上での位置をそれぞれクラスタ中心として、各仮代表値を、前記色空間上で最近接のクラスタ中心が同一の仮代表値同士のクラスタに分類する第３ステップと、
前記クラスタ毎に、そのクラスタに属する仮代表値からそのクラスタの代表値を算出し、これを第ｎ種小領域の仮代表値とする第４ステップと、
を有し、
第１種小領域帰属代表値が決定済みの隣接する第１種小領域が存在することを条件に、前記第１ステップにおいて、前記隣接する第１種小領域の決定済み第１種小領域帰属代表値に基づいて前記１つの仮代表値を選択する
ことを特徴とする画像符号化方法。
【００２８】
上記発明では、分割をより多階層化することで、圧縮歪を低減しつつ符号量の増加をより抑えることができる。
【００２９】
［７］前記隣接する第１種小領域の決定済み第１種小領域帰属代表値の中で最大クラスタの第１種小領域帰属代表値に基づいて、前記１つの仮代表値を選択する
ことを特徴とする［５］または［６］に記載の画像符号化方法。
【００３０】
上記発明では、隣接する第１種小領域の決定済み第１種小領域帰属代表値の中で最大クラスタの第１種小領域帰属代表値（この第１種小領域帰属代表値を使用する画素数が最大の第１種小領域帰属代表値）に基づいて、初期のクラスタ中心が選択される。すなわち、隣接する第１種小領域において最大面積を占める第１種小領域帰属代表値に基づいて初期のクラスタ中心が選択される。
【００３１】
［８］前記最大クラスタに属する画素の画素数が基準値以上の場合にのみ、前記１つの画素の選択を前記最大クラスタの第１種小領域帰属代表値に基づいて行う
ことを特徴とする［７］に記載の画像符号化方法。
【００３２】
上記発明では、各第１種小領域帰属代表値に対応するクラスタサイズが類似し、大きなクラスタサイズの第１種小領域帰属代表値が存在しないような場合には、初期のクラスタ中心は、隣接する第１種小領域との関係を考慮しないで決定される。たとえば、当該第１種小領域において任意に決定される。
【００３３】
［９］前記第２ステップにおける前記繰り返しを、選択済みの仮代表値が前記第１種規定数＋１個になるまで行い、
前記第３ステップにおいて、前記第２ステップで最後に選択した仮代表値を除く第１種規定数の選択された仮代表値の前記色空間上での位置をそれぞれクラスタ中心として前記分類を行い、その結果、前記第１ステップで選択した仮代表値の前記色空間上での位置を最近接のクラスタ中心とするクラスタに属する仮代表値の数が下限値以下の場合は、前記第２ステップで最後に選択した仮代表値の前記色空間上での位置を前記第１ステップで選択した仮代表値に係るクラスタ中心の代替クラスタ中心として前記分類をやり直す
ことを特徴とする［５］乃至［８］のいずれか一項に記載の画像符号化方法。
【００３４】
上記発明では、クラスタ中心とする仮代表値を予め第１種規定数より１個多く選択しておき、最後に選択したものを除く第１種規定数のクラスタ中心によって分類する。その結果、隣接する第１種小領域の決定済み代表値に基づく初期のクラスタ中心を最近接とする仮代表値の数が少ない場合には、初期のクラスタ中心は不適切と判断し、初期のクラスタ中心の代わりに最後に選択したクラスタ中心を採用して再度分類する。
【００３５】
［１０］前記非階層的クラスタ分析は、画素の色成分を座標変換した座標値に基づいて行う
ことを特徴とする［１］乃至［９］のいずれか一項に記載の画像符号化方法。
【００３６】
上記発明では、均等色空間をモデルとした輝度・色成分などを成分とする座標空間、主成分分析結果の主要主成分スコアによる座標空間などにおいて、最近接の判断等が行われる。
【発明の効果】
【００３７】
本発明に係る画像符号化方法によれば、画像を分割した各小領域を、少ない演算量で適切な代表値を割り当てて符号化することができる。
【図面の簡単な説明】
【００３８】
【図１】本発明の実施の形態に係る画像符号化装置としての機能を含む画像処理装置の概略構成を示すブロック図である。
【図２】本発明に係る画像符号化方法の手順の概要を示す流れ図である。
【図３】本発明に係る画像符号化方法による符号化の様子を模式的に示す説明図である。
【図４】代表値選択処理（図２のステップＳ１０３）の詳細を示す流れ図である。
【図５】代表値選択処理により、４つの仮クラスタ中心が順次選択され、各画素が４つのクラスタ(グループ)に分類されて代表値が決定される様子を模擬的に示す説明図である。
【図６】既に符号化済みの小領域の決定済み代表色を参照して、注目する小領域の初期仮クラスタを決定する様子を模式的に示す説明図である。
【図７】手法１による初期仮クラスタ選択処理を示す流れ図である。
【図８】手法２による初期仮クラスタ選択処理を示す流れ図である。
【図９】ＣＭＹＫ形式の画像データを色座標変換によってＹＣ分離する場合の演算式等を示す説明図である。
【図１０】ＹＣｂＣｒ空間における各クラスタ中心をＣＭＹＫ形式の代表値に変換する場合の演算式等を示す説明図である。
【図１１】主成分分析の概念を示す説明図である。
【図１２】元画像と、第１種小領域と、第２種小領域との関係を例示した説明図である。
【図１３】分割符号化によって生成される符号情報を構成する符号データの関連性を示す説明図である。
【図１４】分割符号化によって生成される符号情報の構成を模式的に示す説明図である。
【図１５】分割符号化処理（１）の流れ図である。
【図１６】分割符号化処理（２）の流れ図である。
【図１７】座標変換および主成分分析を適用した分割符号化処理の手順を例示した説明図である。
【図１８】座標変換および主成分分析を適用した分割符号化処理の手順の他の例を示す説明図である。
【図１９】座標変換および主成分分析を適用した分割符号化処理の手順のさらに他の例を示す説明図である。
【図２０】タイプ別の符号情報の内訳を示す一覧表である。
【図２１】判定テーブルを例示した図である。
【図２２】タイプ１の符号情報の一例を示す説明図である。
【図２３】タイプ２の符号情報の一例を示す説明図である。
【図２４】タイプ３の符号情報の一例を示す説明図である。
【図２５】第１種小領域を１６画素毎の４つの第２種小領域に分割する場合の各種の分割パターンを例示した説明図である。
【図２６】８画素×８画素の第１種小領域を、４画素×４画素の第２種小領域に分割し、さらに各第２種小領域を２画素×２画素の第３種小領域に分割した様子を示す説明図である。
【図２７】第３種小領域まで分割して生成した符号情報の構成例を示す説明図である。
【図２８】初期値の選択によって最適解を得られない場合のクラスタ分けと、最適解のクラスタ分けとを対比して示す説明図である。
【図２９】画像データが非階層的クラスタ分析によって適切に分類された例、および適切な分類がされなかった場合の例を示す説明図である。
【発明を実施するための形態】
【００３９】
以下、図面に基づき本発明の実施の形態を説明する。
【００４０】
図１は、本発明に係る画像符号化方法で画像を符号化する機能を含む画像処理装置の概略構成を示している。画像処理装置１０は、画像を符号化する符号化処理部１１と、符号化処理部１１で符号化して得たデータ（符号情報と呼ぶ。）を記憶する画像メモリ１２と、画像メモリ１２もしくは外部から符号情報を入力してこれを復号化する復号化処理部１３とから構成される。
【００４１】
符号化処理部１１は、符号化対象の元画像の画像情報を入力する画像入力部１４と、画像入力部１４によって入力した画像情報を、複数の小領域（ブロック）に分割する画像分割部１５と、画像分割部１５によって分割された小領域毎に画像情報を符号化する符号化部１６とを備えて構成される。
【００４２】
復号化処理部１３は、画像メモリ１２もしくは外部から符号情報を入力する符号入力部１７と、符号入力部１７によって入力した符号情報を復号化する復号化部１８と、復号化部１８が出力する復号化された画像情報を出力する画像出力部１９とを備えて構成される。
【００４３】
図１の画像処理装置１０には各々の処理部の起動や終了等の動作を制御する制御部、オペレータによる画像処理の実行指示等を受け付ける指示入力部、現在の処理状況等を表示する状態表示部、等、図示しない装備が適宜具備されても良い。また、図１の画像処理装置１０は符号化処理部１１、復号化処理部１３、画像メモリ１２を一つの装置としたが、これらは画像符号化装置や画像復号化装置など別体の装置として構成されてもよい。また、ＣＰＵ(Central Processing Unit）とＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）などを備えたコンピュータ装置において所定のプログラムを実行することにより画像符号化の機能等が実現されてもよい。
【００４４】
＜符号化処理の概要＞
図２は、本発明に係る画像符号化方法の手順の概要を示し、図３は符号化の様子を模式的に示している。まず、符号化対象の画像（元画像３０）を複数の小領域（ブロック）３２に分割する（ステップＳ１０１、図３（ａ））。ここでは、元画像３０を複数の矩形の小領域３２に分割する。１つの小領域３２のサイズは画像の解像度や利用目的に応じて適宜決められる。たとえば、縦８画素×横８画素（以下、８画素×８画素の様に表記する）や４画素×４画素の矩形の小領域に分割される。
【００４５】
分割した中の１つの小領域３２を抽出し（ステップＳ１０２、図３：Ｑ１）、その小領域３２に属する画素を、類似する色を有する画素同士の所定数のクラスタ（グループ）に分類し、クラスタ毎にそのクラスタに属する画素の画像データの代表値（代表色）を決定する（ステップＳ１０３）。図３（ｃ）の例では、小領域３２に属する６４画素は４つのクラスタ(グループ)に分類され、クラスタ毎の代表値（代表値１〜代表値４）が割り当てられている。
【００４６】
次に、その小領域３２に属する各画素に、その画素が属するクラスタの代表値を指し示すラベル情報を与えて符号化する(ステップＳ１０４)。１つの小領域は、ステップＳ１０３で求めた代表値と、ステップＳ１０４で与えた画素数分のラベル情報に符号化される。図３（ｄ）の例では、１つの小領域３２の符号情報３４は、４つの代表値（代表値１〜代表値４）と、６４画素分のラベル情報（この例では、１〜４のいずれかの数値）とから構成される。
【００４７】
ステップＳ１０２〜Ｓ１０４の処理を、全小領域について終了するまで繰り返し行い（ステップＳ１０５；Ｎｏ）、全小領域について終了すると（ステップＳ１０５；Ｙｅｓ）、符号化処理が終了する。該符号化処理によって得た符号情報は、たとえば、画像メモリ１２に記憶される。
【００４８】
本実施の形態では、元画像の各画素は、Ｙ（イエロ）、Ｍ（マゼンタ）、Ｃ（シアン）、Ｋ（ブラック）の色成分を有し、各色８ｂｉｔ（０〜２５５）のデータで構成されるものとする。元画像における１つの小領域の符号量は、３２ｂｉｔ×６４画素＝２０４８ｂｉｔである。符号情報３４における１つの代表値はＣＭＹＫ各８ビットで表されて３２ビットであり、ラベル情報は４つの代表値を選択し得るために２ｂｉｔである。したがって、１つの小領域３２に係わる符号情報３４の符号量は、３２ｂｉｔ×４代表値＋２ｂｉｔ×６４画素＝２５６ｂｉｔになる。符号化により８倍の圧縮率が得られている。
【００４９】
元画像から分割された各小領域（ブロック）の符号化は、たとえば、図３（ａ）の矢印Ｆで示すような順序、すなわち、元画像の上部左端から開始し、右側へ１ブロックずつ順次移動し、右端まで終了すると１ブロック下方へ移動して左端に戻り、再び右側へ１ブロックずつ移動する、といった順序で行われる。この順序に限らないが、後述する初期仮クラスタ中心の選択を適切に行うためには、とびとびの順序ではなく、隣接するブロックが順次処理されるように符号化するとよい。
【００５０】
図４は、注目している小領域を所定数のクラスタに分類し、クラスタ毎の代表値（代表色）を決定する代表値選択処理（図２のステップＳ１０３）の詳細を示している。この処理は大まかに、以下の（Ｐ１）〜（Ｐ６）の工程で構成される。
【００５１】
（Ｐ１）小領域（たとえば、８画素×８画素）に含まれる各画素の画像データ（ＣＭＹＫ形式のデータ）を色変換して、CIE L*a*b*空間に変換する（ステップＳ２０１）。
【００５２】
（Ｐ２）当該小領域に係る変換後の画像データの中から1つの画素の画像データを仮クラスタ中心（初期仮クラスタ中心）として選択する（ステップＳ２０２）。
【００５３】
（Ｐ３）選択されていない画素の画像データにつき、仮クラスタ中心として選択済みの各画素の画像データとのCIE L*a*b*空間における距離をそれぞれ評価し、最小距離が最大となるものを新たに仮クラスタ中心として選択することを、仮クラスタ中心（選択済みの画素）が所定数（必要な代表値の数、たとえば４個）になるまで繰り返す（ステップＳ２０３；Ｎｏの間、Ｓ２０４〜Ｓ２０９を繰り返す）。
【００５４】
（Ｐ４）当該小領域に属する各画素の画像データにつき、上記（２）（３）で選択した仮クラスタ中心の中から仮クラスタ中心までの距離が最近となる仮クラスタ中心を選択する(ステップＳ２１０〜Ｓ２１２)。
【００５５】
（Ｐ５）同一クラスタ中心を最近接とする画素の画像データ同士をグルーピングする（ステップＳ２１３）。すなわち、当該小領域に属する各画素を、色空間上で最近接のクラスタ中心が同一の画素同士のクラスタ（グループ）に分類する。
【００５６】
（Ｐ６）全クラスタ（グループ）の各々について、そのクラスタに属する画素の画像データのCIE L*a*b*空間における重心（クラスタ中心）を求め、これをそのクラスタの代表値とし(ステップＳ２１４)、CIE L*a*b*空間にあるこの代表値をＣＭＹＫ形式の座標値に変換する(ステップＳ２１５)。
【００５７】
図５は、代表値選択処理により、４つの仮クラスタ中心が順次選択され、各画素が４つのクラスタ(グループ)に分類されて代表値が決定される様子を模擬的に示したものである。同図（ａ）は、初期仮クラスタ中心として画素４１を選択した状態を示している。同図（ｂ）では、選択されていない画素の中で、画素４１との距離が最長である画素４２が、次の仮クラスタ中心に選択される。さらに、未選択の画素毎に、既に仮クラスタ中心に選択されている、画素４１までの距離Ｌ１と画素４２までの距離Ｌ２とを算出し、その最小距離を求める。この画素毎に求めた最小距離が最長の画素４３を次の仮クラスタ中心に選択する（同図（ｃ））。
【００５８】
同図（ｄ）では、未選択の画素毎に、既に選択された各仮クラスタ中心（画素４１、画素４２、画素４３）までの距離を算出してその最小距離を求め、この画素毎に求めた最小距離が最長の画素４４が４つ目の仮クラスタ中心に選択されている。次に、各画素を、これら４つの仮クラスタ中心４１〜４４の中で最近接の仮クラスタ中心に帰属するように分類する(同図（ｅ）)。そして、分類されたクラスタ（グループ）毎に、そのクラスタに属する画素の重心を新たなクラスタ中心とし、これをそのクラスタの代表値４１ｂ〜４４ｂにしている(同図（ｆ）)。
【００５９】
次に、図４のステップＳ２０２における、初期仮クラスタ中心の選択手法について説明する。
【００６０】
一般的に、画像は広い面積を占有する均一な地色部分を有することが多く、地色部分には、隣接小領域にて同じ代表値（代表色）を対応させることが好ましい。そこで、所定の条件下で、各小領域の初期仮クラスタ中心を、すでに決定された隣接小領域の代表値との関連から決定する。たとえば、図３（ａ）の矢印Ｆに従う順序で各小領域を符号化する場合には、図６に示すように、次に符号化する小領域５１に隣接する既に符号化済みの小領域（図中、グレーの小領域は符号化済みとする）が存在するので、隣接する符号化済みの小領域の代表色を参照して、注目する小領域５１の初期仮クラスタ中心を決定する。
【００６１】
初期仮クラスタ中心の決定手法としては、
（手法１）隣接する小領域の決定済み代表値の中で最大クラスタの代表値に基づいて、初期仮クラスタ中心（もしくは初期仮クラスタ中心とする画素）を選択する
（手法２）隣接する小領域の決定済み代表値の中で最大クラスタに属する画素の画素数が基準値以上の場合にのみ、その最大クラスタの代表値に基づいて、初期仮クラスタ中心（もしくは初期仮クラスタ中心とする画素）を選択する、
がある。
【００６２】
＜手法１＞
図７は、手法１による初期仮クラスタ中心選択処理の流れを示している。代表値決定済みの隣接小領域が存在するか否かを調べ（ステップＳ３０１）、無ければ（ステップＳ３０１；Ｎｏ）、当該小領域の任意の画素の画像データを初期仮クラスタ中心に選択する（ステップＳ３０４）。
【００６３】
代表値決定済みの隣接小領域が存在する場合は（ステップＳ３０１；Ｙｅｓ）、隣接小領域の決定済み代表値のうち、最大クラスタ（その代表値を復号時の画素値に使用する画素数が最大のクラスタ）の代表値を求める(ステップＳ３０２)。この最大クラスタの代表値（CIE L*a*b*空間での値）を、初期仮クラスタ中心にする(ステップＳ３０３)。
【００６４】
なお、ステップＳ３０３において、当該小領域に属する画素のうち、最大クラスタの代表値（CIE L*a*b*空間に変換した値）との色空間での距離が最小の画素の画像データを初期仮クラスタ中心としてもよい。また、最大クラスタの代表値（CIE L*a*b*空間に変換した値）との距離が所定距離以下の画素の画像データ（CIE L*a*b*空間に変換した値）が当該小領域に存在するか否かを調べる。そして、存在しない場合は当該小領域の任意の画素の画像データを初期仮クラスタ中心に選択し（ステップＳ３０４）、存在する場合は最大クラスタの代表値（CIE L*a*b*空間に変換した値）を初期仮クラスタ中心とする（ステップＳ３０３）あるいは最大クラスタの代表値（CIE L*a*b*空間に変換した値）との色空間での距離が最小の画素の画像データを初期仮クラスタ中心とする、としてもよい。
【００６５】
＜手法２＞
図８は、手法２による初期仮クラスタ中心選択処理の流れを示している。代表値決定済みの隣接小領域が存在するか否かを調べ（ステップＳ３１１）、無ければ（ステップＳ３１１；Ｎｏ）、任意の画素の画像データを初期仮クラスタ中心に選択する（ステップＳ３１５）。
【００６６】
代表値決定済みの隣接小領域が存在する場合は（ステップＳ３１１；Ｙｅｓ）、隣接小領域の決定済み代表値のうち、最大クラスタのクラスタサイズ(帰属する画素数)を求める(ステップＳ３１２)。この最大クラスタのクラスタサイズが所定の基準値未満の場合は（ステップＳ３１３；Ｎｏ）、任意の画素の画像データを初期仮クラスタ中心に選択する（ステップＳ３１５）。最大クラスタのクラスタサイズが所定の基準値以上の場合は(ステップＳ３１３；Ｙｅｓ)、その最大クラスタの代表値（CIE L*a*b*空間に変換した値）を、初期仮クラスタ中心にする(ステップＳ３１４)。
【００６７】
なお、ステップＳ３１４において、当該小領域に属する画素のうち、最大クラスタの代表値（CIE L*a*b*空間に変換した値）との色空間での距離が最小の画素の画像データを初期仮クラスタ中心としてもよい。また、最大クラスタの代表値（CIE L*a*b*空間に変換した値）との距離が所定距離以下の画素の画像データ（（CIE L*a*b*空間に変換した値）が当該小領域に存在するか否かを調べる。そして、存在しない場合は当該小領域の任意の画素の画像データを初期仮クラスタ中心に選択し（ステップＳ３１５）、存在する場合は最大クラスタの代表値（CIE L*a*b*空間に変換した値）を初期仮クラスタ中心とする（ステップＳ３１４）あるいは最大クラスタの代表値（CIE L*a*b*空間に変換した値）との色空間での距離が最小の画素の画像データを初期仮クラスタ中心とする、としてもよい。
【００６８】
手法１または手法２によって初期仮クラスタ中心を選択することで、地色部分等において、隣接小領域と微妙に色が変化してしまうこと等が防止される。また手法２では、隣接小領域が地色部分を含まないような場合は最大クラスタサイズが基準値未満となり、当該小領域独自で初期仮クラスタ中心が選択されるようになる。
【００６９】
また初期仮クラスタ中心を手法１または手法２で選択した場合には、その初期仮クラスタ中心が不適切な場合に対応するために、前述したＰ１〜Ｐ６の工程を以下のように変更して行うとさらによい。
【００７０】
（Ｐ３）の処理を、仮クラスタ中心（選択済みの画素）が所定数（必要な代表値の数、たとえば４個）＋１個となるまで、繰り返す、ように変更する。
【００７１】
（Ｐ４）の処理において、選択済み仮クラスタ中心のうち（Ｐ３）の処理で最後に選択した仮クラスタ中心を除くものを有効な仮クラスタ中心とし、該小領域に属する各画素の画像データを、色空間上で最近接の有効なクラスタ中心が同一となるもの同士のクラスタに分類する。その結果、初期仮クラスタ中心のクラスタ（初期仮クラスタ中心を最近接とする画素のグループ）の画素数が基準値以下（たとえば、ゼロ）となった場合は、（Ｐ３）の処理で最後に選択した仮クラスタ中心を初期仮クラスタ中心の代替の仮クラスタ中心として、先の分類をやり直す。
【００７２】
これにより、代表値決定済みの隣接小領域と画像の連続性・関連性がある場合は、隣接小領域の決定済み代表値に基づいた初期仮クラスタ中心が使用されてクラスタ分け（分類）が行われ、代表値決定済みの隣接小領域と画像の連続性・関連性が無いあるいは乏しい場合（初期仮クラスタ中心のクラスタに属する画素数が基準値以下の場合）は、当該小領域の画素の中から選択した仮クラスタ中心のみを使用して分類が行われるので、周囲との連続性・関連性がある場合にのみその画像の連続性・関連性がクラスタ分けに反映されて、より適切な代表値が算出される。
【００７３】
なお、代表値選択処理（図２のステップＳ１０３）は、画像データを主成分分析した結果の主要主成分スコアに基づいて行ったり、画像データを均等色空間などに基づく輝度・色成分などを成分とする座標値に変換して行ったりしてもよい。以下に座標変換して行う代表値選択処理の手順を例示する。
【００７４】
＜座標変換して行う代表値選択処理の例１＞
１）図９に示す手順および演算式により、ＣＭＹＫ形式の画像データを、色座標変換によりＹＣ分離する。
２）ＹＣｂＣｒ空間にて分類(グルーピング)してクラスタ中心を決定する
３）図１０に示す手順および演算式により、ＹＣｂＣｒ空間における各クラスタ中心をＣＭＹＫ形式の代表値に変換する
なお上記１）は図４のステップＳ２０１に対応した処理であり、２）はステップＳ２０２〜Ｓ２１４に対応し、３）はステップＳ２１５に対応する。
【００７５】
＜座標変換して行う代表値選択処理の例２＞
例２では、例１に加えて、主成分分析の結果に基づいてグルーピングするようになっている。
１）図９に示すように、ＣＭＹＫ形式の画像データを、色座標変換によりＹＣ分離する
２）ＹＣｂＣｒ空間にて小領域の画像データを主成分分析する
３）第１主成分と第２主成分のスコアを座標値とする空間にて分類(グルーピング)する
４）グルーピング情報に基づきＹＣｂＣｒ空間にてクラスタ中心を算出する
５）図１０に示すように、クラスタ中心をＣＭＹＫ形式の代表値に変換する
なお上記１）は図４のステップＳ２０１に対応した処理であり、２）は追加の処理であり、３）、４）は図４のステップＳ２０２〜Ｓ２１４に対応し、５）はステップＳ２１５に対応する。
【００７６】
図１１は、主成分分析の概念を示したものである。主成分分析は多変量の分布をより少ない変量の分布で表現するためのものである。たとえば、最も分布範囲の大きい方向を第１主成分、第１主成分に直交する方向のうち最も分布範囲の大きい方向を第２主成分、第１主成分と第２主成分に直交する方向のうち最も分布範囲の大きい方向を第３主成分とすると、一般的には上位２つの主成分の寄与率が圧倒的に大きく、第１主成分と第２主成分のスコアの２次元平面で多次元の分布状態を近似できることが多い。
【００７７】
図１１ではＹＣｂＣｒ空間（３変量）における各画素の分布（同図（ａ））に対して主成分分析を行って、第１主成分スコアと第２主成分スコアによる２変量の分布（同図（ｂ））に変換している。このように主成分分析を用いると、次元数が制限（削減）されるので、‘色空間距離’の評価の演算処理（たとえば、図４のステップＳ２０４、Ｓ２１０）が軽減される。
【００７８】
次に、小領域毎の符号化を、各小領域をさらに複数の小領域に分割して行う符号化方法（以後、分割符号化と呼ぶ）について説明する。
【００７９】
符号化の単位となる小領域を第１種小領域、これをさらに分割したものを第２種小領域と呼ぶこととする。ここでは、図１２に示すように、元画像３０を分割した８画素×８画素単位の領域を第１種小領域６１とし、第１種小領域６１をさらに４つに分割した４画素×４画素単位の領域を第２種小領域６２とする。
【００８０】
図１３は、分割符号化によって生成される符号情報を構成する符号データの関連性を示している。同図（ａ）に示すように、分割符号化では、第１種小領域は所定数（第１種小領域に含まれる画素数より少ない数、たとえば、４個））の代表値を有し、その第１種小領域から分割された第２種小領域はそれぞれ、第１種小領域が有する代表値の中のいずれか１つを指し示す代表値インデックス（参照情報）を規定数（第２種小領域の画素数より少ない数、たとえば、２個）有し、各画素はその画素が含まれる第２種小領域が有する代表値インデックスのいずれか１つを指し示すラベル情報を持つ。
【００８１】
代表値にはそれぞれを特定するための代表値番号（第１種識別情報）が割り当てられ、代表値インデックスは代表値番号によって代表値を指し示す（特定する）。また各代表値インデックスクスにもインデックス番号（第２種識別情報）が割り当てられ、ラベル情報はインデックス番号によって代表値インデックスを指し示す（特定する）。
【００８２】
ただし、同一の第１種小領域から分割された複数の第２種小領域の中の１つの第２種小領域については、同図（ｂ）に示すように代表値インデックスを省略し、画素毎のラベル情報が直接、代表値を指し示すようにすることができる。たとえば、所定の１つの第２種小領域で参照する２つの代表値を、代表値１、代表値２に割り当てるように取り決めれば、画素毎のラベル情報で直接に代表値１、２を指し示すことができ、代表値インデックスを省略することができる。
【００８３】
また、同図（ｃ）に示すように、同一の第２種小領域に属する画素の中の１つの特定画素については、その画素の画素値に対応する代表値インデックスを予め定めたインデックス番号に割り当てることで、該特定画素のラベル情報を省略することができる。たとえば、画素１の画素値に対応する代表値を指し示す代表値インデックスをインデックス番号１（代表値インデックス１）に割り当て、画素１についてのラベル情報は符号化しない。
【００８４】
図１４は、分割符号化によって１つの第１種小領域を符号化した場合に得られる符号情報を模式的に示したものである。この例では、８画素×８画素の第１種小領域６１に対して４つの代表値１〜４を与えている。４画素×４画素の第２種小領域６２のうちの１つ（この例では第２種小領域６２ａ）を除くそれぞれに２つの代表値インデックスを与えている。第２種小領域６２ａを除く各第２種小領域６２については、その第２種小領域に属する各画素に対してその第２種小領域６２が有する２つの代表値インデックスのうちのいずれか１つを指し示すラベル情報を与えている。また、代表値インデックスを省略した第２種小領域６２ａについては、代表値１、２のいずれかを直接指し示すラベル情報を与えてある。
【００８５】
分割符号化では、第１種小領域単位ではＮ個（たとえば、４つ）の代表値（代表色）を有するが、各画素はその画素が属する第２種小領域が有するＭ個（たとえば、２個、Ｍ＜Ｎ）の代表値インデックスを指し示すことができればよいので、ラベル情報のｂｉｔ数を少なく抑えて符号化することができる。また、代表値インデックスは、代表値１〜４のいずれかを指し示すことができる符号で良いので、各２ｂｉｔで済む。
【００８６】
たとえば、図１４の例において、代表値をＣＭＹＫの各色８ビットで表すとすると、１つの代表値は３２ｂｉｔで構成され、代表値インデックスは２ｂｉｔで構成され、各画素は２つの代表値インデックスのいずれかを指し示すので１ｂｉｔで構成される。よって、第１種小領域単位で保持する代表値の符号量は３２ｂｉｔ×４＝１２８ｂｉｔ、第２種小領域単位で保持する代表値インデックスの符号量は、１つの第２種小領域では代表値インデックスを省略するので、２ｂｉｔ×２×３＝１２ｂｉｔ、画素単位で保持するラベル情報の符号量は１ｂｉｔ×１６×４＝６４ｂｉｔ、になり、１つの第１種小領域の符号情報の符号量は２０４ｂｉｔになる。
【００８７】
従来のように、各画素のラベル情報が直接、４つの代表色のいずれかを指し示す場合には、ラベル情報として２ｂｉｔを要するので、画素単位で保持するラベル情報の符号量は２ｂｉｔ×６４＝１２８ｂｉｔになり、代表値４個分の符号量は３２ｂｉｔ×４＝１２８ｂｉｔなので、１つの第１種小領域の符号情報の符号量は２５６ｂｉｔになる。図４に示すような分割符号化を行うことで、２５６−２０４＝４２ｂｉｔが削減される。
【００８８】
一方、４×４画素の第２種小領域単位に２つの代表値を与えて独立に符号化する場合には、１つの第２種小領域について、３２ｂｉｔ×２＋１６ｂｉｔ＝８０ｂｉｔを要するので、第１種小領域の符号化に要する符号量は、３２０ｂｉｔになる。
【００８９】
一般的に、画像データは、より近傍の画素であればあるほど相関性が高い性質がある。そこで、より小さい領域に分割すれば、その範囲での代表値数を少なくしても圧縮歪はそれほど増大することはない。したがって、図１４に示す分割符号化では、第１種小領域をさらに複数に分割した第２種小領域のそれぞれで２つの代表色を使用できるので、画質の劣化を少なく抑えることができ、かつまた、第１種小領域単位では４色使用可能でありながら各画素のラベル情報は１ｂｉｔで済むので、符号量を少なくすることができる。すなわち、分割符号化では、画質の劣化を抑えて圧縮率を向上させることができる、あるいは見方を変えれば、符号量を増加させずに実質的な代表値の数を増やして画質の向上を図ることができる。
【００９０】
図１５は、分割符号化の処理の流れを示している。まず、元画像を第１種小領域に分割する（ステップＳ４０１）。そのうちの１つを符号化対象の第１種小領域として抽出し（ステップＳ４０２）、この第１種小領域を複数の第２種小領域に分割する（ステップＳ４０３）。分割後の各第２種小領域に対して、その第２種小領域に属する画素の画像データを代表する第２種規定数（たとえば、２個）の仮代表値を決定する（ステップＳ４０４）。符号化対象の１つの第１種小領域から分割された複数の第２種小領域に対して決定した仮代表値のすべての中から、非階層的クラスタ分析（図４に示す代表値選択処理と同様の手法）によって、仮代表値の総数より少なく第２種規定数より多い第１種規定数（たとえば、４個）の代表値を第１種小領域帰属代表値に選択する(ステップＳ４０５)。
【００９１】
第２種小領域毎に、ステップＳ４０５で選択した第１種小領域帰属代表値の中から第２種規定数の第１種小領域帰属代表値を第２種小領域帰属代表値として選択し、それら選択した第１種小領域帰属代表値を指し示す代表値インデックス（参照情報）を作成する（ステップＳ４０６）。ここでは、その第２種小領域に対してステップＳ４０４で決定した仮代表値毎に、それに最近接（色空間において）の第１種小領域帰属代表値を選択する。
【００９２】
続いて該第１種小領域に属する画素毎に、その画素が属する第２種小領域に係る第２種小領域帰属代表値のいずれか１つを選択し、その選択した第２種小領域帰属代表値に対応する代表値インデックスを指し示すラベル情報を作成する(ステップＳ４０７)。上記選択では、その画素が属する第２種小領域に係る第２種小領域帰属代表値の中でその画素の画素値に最近接（色空間において）の第２種小領域帰属代表値を選択する。
【００９３】
そして、ステップＳ４０５で選択した第１種規定数の第１種小領域帰属代表値と、ステップＳ４０６で作成した第２種小領域毎の第２種規定数の代表値インデックス（参照情報）と、ステップＳ４０７で作成した画素毎のラベル情報とを含む符号情報を生成する（ステップＳ４０８）。
【００９４】
符号化未処理の第１種小領域がある場合は（ステップＳ４０９；Ｎｏ）、ステップＳ４０２に移行して処理を継続する。すべての第１種小領域の符号化が完了したら（ステップＳ４０９；Ｙｅｓ））本処理を終了する。
【００９５】
なお、図１５の分割符号化処理（１）では、すべての第２種小領域に代表値インデックスを付与するようにしたが、１つの第２種小領域について代表値インデックスを省略する場合には、図１６に示す分割符号化処理（２）となる。図１５と同一処理には同一のステップ番号を付してある。
【００９６】
図１６の処理では、ステップＳ４０５で決定した第１種小領域帰属代表値の中から、代表値インデックスを省略する第２種小領域で使用（参照）する第２種規定数の第１種小領域帰属代表値を選択し（ステップＳ４１１）、それらを予め定めた番号の代表値（たとえば、代表値１、２）に割り当てる（ステップＳ４１２）。上記の選択は、その第２種小領域に対してステップＳ４０４で決定した仮代表値毎に、それに最近接の第１種小領域帰属代表値を選択することによって行う。
【００９７】
次に、代表値インデックスを省略しない第２種小領域毎に、第２種規定数の第１種小領域帰属代表値を先と同様に最近接を基準に選択し、選択した各第１種小領域帰属代表値を指し示す代表値インデックス（参照情報）を付与する（ステップＳ４１３）。そして、代表値インデックスを省略していない第２種小領域の各画素に、その画素が属する第２種小領域が有するいずれかの代表値インデックスを指し示すラベル情報を付与する（ステップＳ４１４）。代表値インデックスを省略した第２種小領域については、ステップＳ４１１で選択した第１種小領域帰属代表値（代表値１、２）のいずれかを指し示すラベル情報を付与する（ステップＳ４１５）。なお、上記ラベル情報の作成における代表値インデックスの選択では、その画素が属する第２種小領域に係る第２種小領域帰属代表値の中でその画素の画素値に最近接の第２種小領域帰属代表値を選択する。
【００９８】
符号化未処理の第１種小領域がある場合は（ステップＳ４１６；Ｎｏ）、ステップＳ４０２に移行して処理を継続する。すべての第１種小領域の符号化が完了したら（ステップＳ４１６；Ｙｅｓ））本処理を終了する。
【００９９】
なお、仮代表値を決定し、それらの中から第１種小領域帰属代表値を選択する処理（図１５、図１６のステップＳ４０４、Ｓ４０５）は、画像データを所望の空間に座標変換したり主成分分析を適用したりして行うようにしてもよい。
【０１００】
図１７〜図１９は、座標変換および主成分分析を適用した分割符号化処理の手順を例示している。たとえば、図１７の手順では、各画素の画像データは、L*a*b*空間に変換された値となっており、第２種小領域毎に、その第２種小領域に含まれる１６画素について主成分分析を行い（ステップＳ４３１）、この１６画素を第１主成分スコアに基づいて２つのグループに分割し、それぞれのグループに属する画素の平均スコア（第１主成分スコアの平均値と第２主成分スコアの平均値）を求め（ステップＳ４３２）、このスコアが示す値をL*a*b*空間に戻して２つの仮代表値とする（ステップＳ４３３）。以上の処理を４つの第２種小領域のそれぞれに対して行うことで、合計８個の仮代表値が算出される。
【０１０１】
これら８つの仮代表値に対して非階層的クラスタ分析（図４に示す代表値選択処理と同様の手法）を行って４つの代表値（第１種小領域帰属代表値）を決定する（ステップＳ４３４）。そして、第２種小領域毎に、これら４つの代表値の中からその第２種小領域の仮代表値に近似する２つの代表値（第２種小領域帰属代表値）を選択し、これらを指し示す代表値インデックスを求める（ステップＳ４３５）。その後、画素毎に、その画素が属する第２種小領域が有する２つの代表値インデックスが指し示す代表値のうち、当該画素との距離（L*a*b*空間での距離）が近い方を選択し、その選択した代表値に対応する代表値インデックスを指し示すラベル情報をその画素に付与する（ステップＳ４３６）。
【０１０２】
図１８の手順では、画素単位の処理が主成分スコアに基づいて行われる。図１９の手順では、主成分スコアのまま非階層的クラスタ分析が行われる。
【０１０３】
次に、帰属する代表値数を第２種小領域毎に変化させる場合について説明する。
【０１０４】
第１種小領域の中にも局所的な色の分布があり、第１種小領域を分割した複数の第２種小領域の中に、代表値１つで表すことが可能な平坦な画像部分もあれば、エッジ部分のように多くの色が含まれる場合もある。そこで、各第２種小領域に対して与えるべき代表値の数を評価し、第２種小領域別に帰属させる代表値の数を変化させることで、第１種小領域単位での符号量を増やすことなく、より少ない歪で画像を符号化することが可能になる。以後、第２種小領域に帰属させる代表値の数を変化させる符号化を、色数適用型符号化と呼ぶものとする。
【０１０５】
ここでは、以下のような条件で色数適用型符号化の例に説明する。第１種小領域を８画素×８画素の領域とし、第１種小領域に対して４つの代表値を与えるものとする。また、第２種小領域は第１種小領域を４つに分割した４画素×４画素の領域とし、第１種小領域内の色の分布に応じて、次の３つの符号化タイプのいずれかを選択可能とする。
【０１０６】
タイプ１：２色、２色、２色、２色
タイプ２：４色、２色、２色、１色
タイプ３：４色、４色、１色、１色
なお、４色の代表値が帰属する第２種小領域については、代表値以外の予め定めた特定色（たとえば、黒、白など）を想定しない。その他の第２種小領域については、代表値以外の特定色に対応付け可能とする。特定色は、色情報を第１種小領域単位の符号情報として保持しない代表色であり、代表色の番号に対応する色が予め定められている。たとえば、代表色１〜４は、色情報を有し、特定色として、代表色５＝白、代表色６=黒、というように定められる。特定色を使用することで、代表値を持つための符号量を増やすことなく、より多くの色が使用可能となる。特定色は、固定されてもよいし、１ページの画像毎に特定色を選択可能にしてページ単位の符号情報としてその特定色の情報を保持するようにしてもよい。また、１ページ内に任意の画像領域を設定可能とし、その画像領域毎に特定色を選択可能にしてその設定した画像領域に特定色の情報を保持するようにしてもよい。
【０１０７】
色数適用型符号化の符号化形式は以下の通りとする。
＜符号量＞
第１種小領域単位での符号量は２０５ｂｉｔ（特定色を適用する場合は２０９ｂｉｔ）固定とする。
【０１０８】
＜符号構成＞
・タイプ識別コード（１〜２ｂｉｔ）
０・・・タイプ１
１０・・・タイプ２
１１・・・タイプ３
・第１種小領域代表値（４×３２ｂｉｔ）
代表値１（Ｃ，Ｍ，Ｙ，Ｋ）、
代表値２（Ｃ，Ｍ，Ｙ，Ｋ）、
代表値３（Ｃ，Ｍ，Ｙ，Ｋ）、
代表値４（Ｃ，Ｍ，Ｙ，Ｋ）
・第２種小領域色数識別コード
タイプ１・・・なし
タイプ２・・・４ｂｉｔ  下記１２通りを識別
（４２２１，４２１２，４１２２，２４２１，２４１２，２２４１，２２１４，２１４２，２１２４，１４２２，１２４２，１２２４）
タイプ３・・・３ｂｉｔ  下記６通りを識別
（４４１１，４１４１，４１１４，１４４１，１４１４，１１４４）
・第２種小領域インデックス
タイプ１・・・３×４ｂｉｔ（または４×４ｂｉｔ）
第２種小領域１の２色は代表値１・代表値２に固定（０ｂｉｔ）
第２種小領域２〜４はそれぞれ２つの代表値を選択（２×２ｂｉｔ）
タイプ２・・・４ｂｉｔ＋２ｂｉｔ（または、２×４ｂｉｔ＋２ｂｉｔ）
４色の第２種小領域は選択不要（０ｂｉｔ）
２色の第２種小領域のうち１つは、代表値１・代表値２に固定（０ｂｉｔ）
他の２色の第２種小領域につき、２つの代表値を選択（２×２ｂｉｔ）
１色の第２種小領域は１つの代表値を選択（２ｂｉｔ）
タイプ３・・・２ｂｉｔ（または２×２ｂｉｔ）
４色の第２種小領域は選択不要（２×０ｂｉｔ）
１色の第２種小領域のうち１つは代表値１に固定（０ｂｉｔ）
他の１色のサブブロックは１つの代表値を選択（２ｂｉｔ）
・ラベル（６４ｂｉｔ）
４色の第２種小領域は、１６×２ｂｉｔ
２色の第２種小領域は、１６×１ｂｉｔ
１色の第２種小領域は、１６×０ｂｉｔ
タイプ１、タイプ２、タイプ３とも計６４ｂｉｔとなる。
【０１０９】
図２０は、タイプ別の符号情報の内訳を一覧で示したものである。２０５ｂｉｔあるいは２０９ｂｉｔの固定長にする（最大のタイプ１にあわせる）ために、タイプ２、タイプ３には、余ったｂｉｔ数分だけ無意味な符号で埋めてパディングされる。
【０１１０】
次に、色数適用型符号化の手順（アルゴリズム）を、第１方式と、簡易な第２方式について説明する。
【０１１１】
＜第１方式＞
各第１種小領域について、
１）第１種小領域の６４画素について、主成分分析により、第１主成分と第２主成分を求める。
２）６４画素の第１主成分スコアと第２主成分スコアに基づき、代表値４色を決定する（図４と同様の手法による非階層的クラスタ分析にて行う）。
３）各第２種小領域につき、１６画素の主成分スコアに関して、
ａ）最近接代表値への平方距離の和の平均
ｂ）代表値４色から２色を選択した場合の最近接代表値への平方距離の和の平均が最も小さくなる場合の値
ｃ）代表値１色から１色を選択した場合の最近接代表値への平方距離の和の平均が最も小さくなる場合の値
をそれぞれ計算し、さらにタイプ１、タイプ２、タイプ３を適用し、４つの第２種小領域の最大の平方距離の和の平均が最も小さくなるように、符号化タイプおよび各第２種小領域の色数（第２種小領域色数識別コード・・・色数の組み合わせ）を決定する。
（なお上記計算において画素数は常に一定なので、平均ではなく積算値を使用してもかまわない。）
４）決められた符号化タイプに基づいて、各第２種小領域のインデックス（代表値インデックス）、各画素のラベルを求めて符号化する。
【０１１２】
＜第２方式＞
各第１種小領域について、
１）第１種小領域の６４画素について、主成分分析により、第１主成分と第２主成分を求める。
２）６４画素の第１主成分スコアと第２主成分スコアに基づき、代表値４色を決定する（図４と同様の手法による非階層的クラスタ分析にて行う）。
３）各第２種小領域につき、１６画素の主成分スコアに関して、
ａ）最近接の代表値に基づいてクラスタ分割
ｂ）第２種小領域のクラスタ数を評価
４）第２種小領域のクラスタ数に基づき、第２種小領域毎の代表値インデックス数、符号化タイプを決定する。たとえば、図２１に示すような判定テーブルを予め用意しておき、該判定テーブルを参照して符号化タイプおよび各第２種小領域のインデックス数(使用する色数)を決定する。
５）各第２種小領域のインデックス数に基づき、最適なインデックス（平方距離和を最小化する条件）を選択し、それに基づいて画素毎のラベルを求めて、符号化する。
【０１１３】
図２２は、タイプ１の符号情報の一例である。なお、第１種小領域をブロック、第２種小領域をサブブロックとも呼ぶこととする。サブブロック１ではインデックスは省略されており、サブブロック１のラベル情報「０」が代表色１を直接指し示し、サブブロック１のラベル情報「１」が代表色２を直接指し示している。
【０１１４】
また、サブブロック１の画素１−１に対するラベル情報は省略されており、画素１−１に対応させるべき代表色を、ブロックの代表色１に割り当ててある。サブブロック２では、画素２−１に対応させるべき代表色を、当該サブブロック２が有する２つのインデックスのうちの予め定めたもの（たとえば、インデックス０、１のうちの０）が指し示すようにすることで、画素２−１のラベル情報を省略してある。サブブロック３、４でも同様にして、画素３−１、画素４−１のラベル情報を省略してある。このような省略を行うことで、ブロックの符号量は２０１ｂｉｔに削減されている。
【０１１５】
図２３は、タイプ２の符号情報の一例である。この例では、サブブロック１の色数は４、サブブロック２、３の色数は２、サブブロック４の色数は１となっている。サブブロック１のインデックスは省略されており、たとえば、サブブロック１のラベル情報「０」が代表色１を直接指し示し、サブブロック１のラベル情報「１」が代表色２を直接指し示し、サブブロック１のラベル情報「２」が代表色３を直接指し示し、サブブロック１のラベル情報「３」が代表色４を直接指し示すようになっている。
【０１１６】
また、サブブロック２のインデックスも省略されており、サブブロック２のラベル情報「０」が代表色１を直接指し示し、サブブロック２のラベル情報「１」が代表色２を直接指し示すようになっている。
【０１１７】
また、サブブロック２の画素２−１に対するラベル情報は省略されており、画素２−１に対応させるべき代表色を、ブロックの代表色１に割り当ててある。サブブロック３では、画素３−１に対応させるべき代表色を、当該サブブロック３が有する２つのインデックスのうちの予め定めたもの（たとえば、インデックス０、１のうちの０）が指し示すようにすることで、画素３−１のラベル情報を省略してある。
【０１１８】
さらにサブブロック４では色数が１なのでインデックスが１つのみであり、各画素のラベル情報はすべて省略されている。
【０１１９】
このような省略を行うことで、ブロックの符号量は２０２ｂｉｔに削減されている。なお、この例のタイプ２の場合、最初に、サブブロック２の画素２−１に対応させるべき代表色を代表色１に、サブブロック２で使用する他の１つの代表色を代表色２に設定すればよい。
【０１２０】
図２４は、タイプ３の符号情報の一例である。この例では、サブブロック１、２の色数は４、サブブロック３、４の色数は１となっている。サブブロック１、２のインデックスは省略されており、たとえば、サブブロック１、２のラベル情報「０」が代表色１を直接指し示し、ラベル情報「１」が代表色２を直接指し示し、ラベル情報「２」が代表色３を直接指し示し、ラベル情報「３」が代表色４を直接指し示すようになっている。
【０１２１】
サブブロック３ではインデックスおよびラベル情報がそれぞれ省略されている。たとえば、サブブロック３で使用する１つの代表色を代表色１に割り当てるようになっている。サブブロック４のラベル情報は省略されており、サブブロック４が持つ１つのインデックスにより、サブブロック４で使用する１つの代表色を指し示すようになっている。このような省略を行うことで、ブロックの符号量は１９９ｂｉｔに削減されている。
【０１２２】
図２２〜図２４に示す形式の符号情報を使用すれば、１ブロックあたりの符号量を２０２ｂｉｔの固定長（タイプ１、タイプ３ではパディングを行う）に削減することができる。
【０１２３】
このように色数適用型符号化を採用すれば、エッジ部分などを含む第１種小領域において、符号量をほとんど増やすことなく圧縮歪の格段の低減を図ることが可能になる。特に文字画像などでは、平坦部に対してエッジが局在化し、色数の分布が局所的に偏るケースが多いので、色数適用型符号化による画質向上の効果がよく現れる。
【０１２４】
次に、第２種小領域の分割方法を画像に応じて変化させる場合について説明する。
【０１２５】
第１種小領域を、個々の第２種小領域に含まれる色数が少なくなるように分割すれば、インデックス（代表値インデックス）やラベル情報の符号量を少なくすることができる。
【０１２６】
図２５は、第１種小領域を１６画素毎の４つの第２種小領域に分割する場合の各種の分割パターン（ａ〜ｊ）を例示している。同図では、同一色もしくは模様の画素が同一の第２種小領域に属している。
【０１２７】
第２種小領域の分割パターンを変化させる符号化方法（分割パターン適用型符号化と呼ぶものとする）の手順を以下に例示する。
１）第１種小領域毎に、図２５に示すような予め定めた分割パターンのうちの幾つかを適用させ、第２種小領域内の色成分の分散の和が最小となる分割パターンを選択する。
２）各第２種小領域に含まれる画素データに基づき、第２種小領域毎に仮代表値を２色決定する。
３）第１種小領域に含まれる４つの第２種小領域の仮代表値の計８色に基づいて第１種小領域の代表値４色を決定し（図４と同様の手法による非階層的クラスタ分析にて行う）、これらを符号化する。
４）第２種小領域毎に、上記２）で決定した当該第２種小領域の仮代表値につき、３）で決定した第１種小領域の代表値の中から最近接のものを選択し、選択した代表値を指し示す代表値インデックスを符号化する。
５）各画素につき、４）で決定した代表値（当該画素が含まれる第２種小領域が有する代表値インデックスが指し示す代表値）の中から最近接のものを選択し、その代表値に対応する代表値インデックスを指し示すラベル情報を符号化する。
【０１２８】
このように分割パターン適用型符号化では、図形パターンなどに対し、個々の第２種小領域の色数が少なくなるように適応的にパターンが選択されるので、圧縮歪を小さくできる可能性が高くなる。また、色数適用型符号化と分割パターン適用型符号化とを併用すれば、より圧縮率を高めて符号化することも可能になる。
【０１２９】
次に、多階層化による符号化について説明する。
【０１３０】
多層化による符号化では画像を多階層に分割して符号化する。第ｎ種小領域（ｎは１以上の整数）を複数に分割した各小領域を第ｎ＋１種小領域と呼ぶものとして、画像を第ｋ種小領域（ｋ≧３）までに分割して、第１種小領域単位に符号化する。たとえば、図２６は、Ｋ＝３とする場合であり、８画素×８画素の第１種小領域７１を、４画素×４画素の４つの第２種小領域７２に分割し、さらに第２種小領域７２をそれぞれ２画素×２画素の４つの第３種小領域７３に分割している。
【０１３１】
図２６の例の場合の符号化手順は以下のようになる。
１）各第３種小領域７３について、その第３種小領域に含まれる４画素に基づいて第３種小領域の仮代表値（第３種仮代表値）２色を決定する。
２）各第２種小領域７２について、その第２種小領域に含まれる４つの第３種小領域の仮代表値の計８色に基づいて当該第２種小領域の仮代表値（第２種仮代表値）３色を決定する（図４と同様の手法による非階層的クラスタ分析にて行う）。
３）第１種小領域７１に含まれる４つの第２種小領域の仮代表値の計１２色に基づいて第１種小領域の代表値（第１種小領域帰属代表値）４色を決定し（図４と同様の手法による非階層的クラスタ分析にて行う）、これらを符号化する。
４）第２種小領域毎に、上記２）で決定した当該第２種小領域の仮代表値につき、３）で決定した第１種小領域の代表値の中から最近接のものを第２種小領域帰属代表値として選択し、選択した代表値を指し示す代表値インデックスを符号化する。
５）第３種小領域毎に、上記１）で決定した当該第３種小領域の仮代表値につき、４）で決定した、当該第３種小領域が含まれる第２種小領域の代表値インデックスが指し示す代表値（第２種小領域帰属代表値）の中から最近接のものを第３種小領域帰属代表値として選択し、これを指し示す第２種小領域の代表値インデックスを指し示す代表値インデックスを符号化する。
６）各画素につき、５）で決定した、当該画素が含まれる第３種小領域の代表値インデックスが間接に指し示す代表値（第３種小領域帰属代表値）の中から最近接のものを選択し、その選択した代表値に対応する当該第３種小領域の代表値インデックスを指し示すラベル情報を符号化する。
【０１３２】
上記２）、３）で行う各非階層的クラスタ分析において、代表値決定済みの隣接する第１種小領域が存在する場合は、図７または図８と同様の基準で、初期の仮クラスタ中心を選択する。第２種小領域毎の非階層的クラスタ分析にて上記条件での初期の仮クラスタ中心（仮代表値）の選択を行う。
【０１３３】
図２７は、上記手順により、第３種小領域まで分割して生成した符号情報の構成例を示している。なお、第３種小領域をサブサブブロックとも呼ぶものとする。
【０１３４】
サブブロック１〜４では、代表値１〜４のうちの３色を指定する代わりに、除外する１色を指定するようになっている。また、サブブロック１においては除外する代表色を代表色４に固定することで、インデックスを省略している。サブブロック２〜４のインデックスは、４つの代表色の中から除外する１色を指定するので、各２ｂｉｔになっている。
【０１３５】
サブサブブロックのインデックスは、そのサブサブブロックが属するサブブロックのインデックスが示す３つの代表色の中の２色を指定する代わりに除外する１色を指定する。よって、サブサブブロックのインデックスは２ｂｉｔになっている。なお、サブサブブロック１−１においては、除外する１色を、上位のサブブロックのインデックスが示す３つの代表色の中の３色目に固定することで、インデックスを省略している。
【０１３６】
各画素のラベル情報は、サブサブブロックのインデックスが示す２色の中のいずれか一方を指し示すので、１ｂｉｔになっている。なお、各サブブロックの１画素目（画素１−１−１、画素２−１−１、画素３−１−１、画素４−１−１）については、その画素が属するサブサブブロックのインデックスが示す２色のうちの１色目に固定することで、ラベル情報を省略している。
【０１３７】
第３種小領域までの多階層による符号化および上記のような省略を行うことで、１ブロックの符号量は２２４ｂｉｔに削減されている。
【０１３８】
なお、サブブロックのインデックスを使用せずに、各サブサブブロックのインデックスが、ブロックが有する４つの代表値１〜４の中のいずれか２つを直接指定するように構成されてもよい。図２６に示すように、４色の中の２色を指定する場合、その組み合わせは、｛代表値１，代表値２｝、｛代表値１，代表値３｝、｛代表値１，代表値４｝、｛代表値２，代表値３｝、｛代表値２，代表値４｝、｛代表値３，代表値４｝  の６通りある。このなかのいずれの組み合わせであるかを示す情報によって２色を指定すれば、３ｂｉｔで２色を指定することができる。この場合、符号情報は、ブロック（第１種小領域）に係る４つの代表値（３２ｂｉｔ×４＝１２８ｂｉｔ）と、１６個のサブサブブロック（第３種小領域）のインデックス（３ｂｉｔ×１６＝４８ｂｉｔ）、画素毎のラベル情報（１ｂｉｔ×６４画素＝６４ｂｉｔ）で構成され、符号量は２４０ｂｉｔになる。
【０１３９】
なお、多階層の符号化は第３種小領域をさらに複数に分割した第４種小領域や、さらに分割を進めた第５種小領域など多階層に分割してもかまわない。
【０１４０】
第ｋ種小領域まで分割する場合の多階層符号化の手順は以下のようになる。
１）画像を複数の第１種小領域に分割するステップと、
２）第１種小領域毎に、画像データの符号化を、
２−１）該第１種小領域を、第ｋ種小領域（ｋは３以上の整数）まで分割し、
２−２）第ｋ種小領域毎に、その第ｋ種小領域に属する画素の画像データを代表する第ｋ種規定数の仮代表値を決定し、
２−３）１つの第ｎ種小領域から分割された複数の第ｎ＋１種小領域に対して決定したすべての仮代表値の中から第ｎ種規定数の仮代表値を、非階層的クラスタ分析によって決定することを、ｎ＝ｋ−１からｎ＝１まで繰り返し行い（ただし、第ｎ種規定数＞第ｎ＋１種規定数、かつ、第ｎ種規定数＜１つの第ｎ種小領域から分割された第ｎ＋１種小領域の数×第ｎ＋１種規定数、かつ、第ｎ種規定数＜第ｎ種小領域の画素数、の関係を持つ）、
２−４）第１種小領域に対して決定した仮代表値を第１種小領域帰属代表値とし、
２−５）第ｎ種小領域に対して、その第ｎ種小領域の分割元の第ｎ−１種小領域に係る第ｎ−１種小領域帰属代表値の中から第ｎ種規定数の第ｎ−１種小領域帰属代表値を第ｎ種小領域帰属代表値として選択し、その選択した第ｎ−１種小領域帰属代表値に対応する第ｎ−１種参照情報を指し示す第ｎ種参照情報を求めることを、ｎ＝２からｋまで行い、
２−６）該第１種小領域に属する画素毎に、その画素が属する第ｋ種小領域に係る第ｋ種小領域帰属代表値のいずれか１つ（最近接のもの）を選択し、その選択した第ｋ種小領域帰属代表値に対応する第ｋ種参照情報を指し示すラベル情報を求め、
２−７）第１種規定数の第１種小領域帰属代表値と、第ｎ種小領域毎に求めた第ｎ種参照情報（ｎ＝２からｋ）と、該第１種小領域に属する画素毎に求めたラベル情報とを含む符号情報を生成する。
【０１４１】
上記２−３）で行う各非階層的クラスタ分析において、代表値決定済みの隣接する第１種小領域が存在する場合は、図７または図８と同様の基準で、初期の仮クラスタ中心を選択する。第２種小領域毎の非階層的クラスタ分析にて上記条件での初期の仮クラスタ中心（仮代表値）の選択を行う。
【０１４２】
以上、本発明の実施の形態を図面によって説明してきたが、具体的な構成は実施の形態に示したものに限られるものではなく、本発明の要旨を逸脱しない範囲における変更や追加があっても本発明に含まれる。
【符号の説明】
【０１４３】
１０…画像処理装置
１１…符号化処理部
１２…画像メモリ
１３…復号化処理部
１４…画像入力部
１５…画像分割部
１６…符号化部
１７…符号入力部
１８…復号化部
１９…画像出力部
３０…元画像
３２…小領域
３４…符号情報
４１〜４４…仮クラスタ中心（選択された画素）
４１ｂ〜４４ｂ…クラスタ中心
５１…次に符号化する小領域
６１…第１種小領域
６２…第２種小領域
６２ａ…代表値インデックスを省略した第２種小領域
７１…第１種小領域
７２…第２種小領域
７３…第３種小領域
Ｆ…符号化順序
【図１】
2011166450.tif 000003
【図２】
2011166450.tif 000004
【図４】
2011166450.tif 000005
【図５】
2011166450.tif 000006
【図７】
2011166450.tif 000007
【図８】
2011166450.tif 000008
【図９】
2011166450.tif 000009
【図１０】
2011166450.tif 000010
【図１１】
2011166450.tif 000011
【図１２】
2011166450.tif 000012
【図１３】
2011166450.tif 000013
【図１４】
2011166450.tif 000014
【図１５】
2011166450.tif 000015
【図１６】
2011166450.tif 000016
【図１７】
2011166450.tif 000017
【図１８】
2011166450.tif 000018
【図１９】
2011166450.tif 000019
【図２０】
2011166450.tif 000020
【図２１】
2011166450.tif 000021
【図２２】
2011166450.tif 000022
【図２３】
2011166450.tif 000023
【図２４】
2011166450.tif 000024
【図２６】
2011166450.tif 000025
【図２７】
2011166450.tif 000026
【図２８】
2011166450.tif 000027
【図３】
2011166450.tif 000028
【図６】
2011166450.tif 000029
【図２５】
2011166450.tif 000030
【図２９】
2011166450.tif 000031