(57)【要約】【課題】画質の劣化を抑えて圧縮率を向上できる画像符号化方法を提供する。【解決手段】元画像を複数の第１種小領域（例えば８×８画素）に分割し、第１種小領域毎に所定数の代表値（例えば４色）を決定し、該第１種小領域を複数の第２種小領域（例えば４×４画素）に分割し、第２種小領域毎に、分割元の第１種小領域の代表値の中から例えば２色の代表値を選択してその選択した代表値を指し示す代表値インデックスを求め、画素毎に、その画素が属する第２種小領域が有する代表値インデックスの中でその画素の色に最近接の代表値を指し示す代表値インデックスを指し示すラベル情報を求め、第１種小領域毎に、代表値と、第２種小領域毎に求めた代表値インデックスと、画素毎のラベル情報と、を含む符号情報を生成する。【選択図】図２
2011166454.tif 000002
【特許請求の範囲】
【請求項１】
画像を複数の第１種小領域に分割し、
前記第１種小領域毎に、画像データの符号化を、
該第１種小領域を複数の第２種小領域に分割し、
該第１種小領域に対して、該第１種小領域に含まれる画素の画像データを代表する、該第１種小領域に含まれる画素数より少ない所定数の代表値を決定し、
前記第２種小領域毎に、前記所定数の代表値の中から前記第２種小領域の画素数より少ない規定数の代表値を第２種小領域帰属代表値として選択し、その選択した代表値を指し示す参照情報を求め、
該第１種小領域に属する画素毎に、その画素が属する第２種小領域に係る前記第２種小領域帰属代表値の中のいずれか１つを選択し、その選択した第２種小領域帰属代表値に対応する参照情報を指し示すラベル情報を求め、
前記所定数の代表値と、前記第２種小領域毎に求めた参照情報と、該第１種小領域に属する画素毎に求めたラベル情報と、を含む符号情報を生成する、
ことによって行う
ことを特徴とする画像符号化方法。
【請求項２】
予め所定の数の特定色を設定し、
第１種小領域に付与した代表値と前記特定色との中から前記第２種小領域帰属代表値を選択し、参照情報が、その選択した、第２種小領域帰属代表値に対応する代表値または特定色を指し示す
ことを特徴とする請求項１に記載の画像符号化方法。
【請求項３】
予め特定色を設定し、
第１種小領域に属する画素に対して、その画素が属する第２種小領域に係る第２種小領域帰属代表値と前記特定色との中のいずれか１つを選択し、前記ラベル情報が、その選択した、第２小領域帰属代表値に対応する参照情報または特定色を指し示す
ことを特徴とする請求項１または２に記載の画像符号化方法。
【請求項４】
前記代表値に第１種識別番号を付与し、参照情報は前記第１種識別番号によって代表値を指し示すようにすると共に、
分割元が同じ複数の第２種小領域のうちの１つの第２種小領域において第２種小領域帰属代表値に選択された代表値を予め定めた第１種識別番号に割り当てることで、前記１つの第２種小領域に係る参照情報を符号化しない
ことを特徴とする請求項１乃至３のいずれか一項に記載の画像符号化方法。
【請求項５】
前記参照情報に第２種識別番号を付与し、ラベル情報は前記第２種識別番号によって参照情報を指し示すようにすると共に、
第２種小領域に属する１つの特定画素で選択された第２種小領域帰属代表値を予め定めた第２種識別番号に割り当てることで、前記１つの特定画素に係るラベル情報を符号化しない
ことを特徴とする請求項１乃至４のいずれか一項に記載の画像符号化方法。
【請求項６】
画像を多階層に分割して符号化する画像符号化方法であって、
第ｎ種小領域（ｎは１以上の整数）を複数に分割した各小領域を第ｎ＋１種小領域と呼ぶものとして、
画像を複数の第１種小領域に分割し、
前記第１種小領域毎に、画像データの符号化を、
該第１種小領域を、第ｋ種小領域（ｋは３以上の整数）まで分割し、
前記第１種小領域に対して、該第１種小領域に含まれる画素の画像データを代表する第１種規定数の第１種小領域帰属代表値を決定し（ただし、第ｎ種規定数＞第ｎ＋１種規定数、かつ、第ｎ種規定数＜１つの第ｎ種小領域から分割された第ｎ＋１種小領域の数×第ｎ＋１種規定数、かつ、第ｎ種規定数＜第ｎ種小領域の画素数、の関係を持つ）、
第ｎ種小領域に対して、その第ｎ種小領域の分割元の第ｎ−１種小領域に係る第ｎ−１種小領域帰属代表値の中から第ｎ種規定数の第ｎ−１種小領域帰属代表値を第ｎ種小領域帰属代表値として選択し、その選択した第ｎ−１種小領域帰属代表値に対応する第ｎ−１種参照情報を指し示す第ｎ種参照情報を求めることを、ｎ＝２からｋまで行い、
該第１種小領域に属する画素毎に、その画素が属する第ｋ種小領域に係る第ｋ種小領域帰属代表値の中のいずれか１つを選択し、その選択した第ｋ種小領域帰属代表値に対応する第ｋ種参照情報を指し示すラベル情報を求め、
第１種規定数の第１種小領域帰属代表値と、第ｎ種小領域毎に求めた第ｎ種参照情報（ｎ＝２からｋ）と、該第１種小領域に属する画素毎に求めたラベル情報と、を含む符号情報を生成する、
ことによって行う
ことを特徴とする画像符号化方法。
【請求項７】
予め所定の数の特定色を設定し、
第ｎ−１種小領域帰属代表値（ｎは２以上とする）と前記特定色との中から前記第ｎ種小領域帰属代表値を選択し、ｎ＝２の場合には、第ｎ種参照情報がその選択した第ｎ−１種小領域帰属代表値または特定色を指し示し、ｎ≧３の場合には、第ｎ種参照情報がその選択した第ｎ−１種小領域帰属代表値に対応する第ｎ−１種参照情報または特定色を指し示す
ことを特徴とする請求項６に記載の画像符号化方法。
【請求項８】
予め特定色を設定し、
第１種小領域に属する画素に対して、その画素が属する第ｋ種小領域に係る第ｋ種参照情報と前記特定色との中のいずれか１つを選択し、前記ラベル情報が、その選択した、第ｋ種参照情報または特定色を指し示す
ことを特徴とする請求項６または７に記載の画像符号化方法。
【請求項９】
前記第１種小領域帰属代表値に第１種識別番号を付与し、第２種参照情報は前記第１種識別番号によって第１種小領域帰属代表値を指し示すようにすると共に、
分割元が同じ複数の第２種小領域のうちの１つの第２種小領域において第２種小領域帰属代表値に選択された第１種小領域帰属代表値を予め定めた第１種識別番号に割り当てることで、前記１つの第２種小領域に係る第２種参照情報を符号化しない
ことを特徴とする請求項６乃至８のいずれか一項に記載の画像符号化方法。
【請求項１０】
前記第ｎ−１種参照情報（ｎは３以上とする）に第ｎ−１種識別番号を付与し、第ｎ種参照情報は前記第ｎ−１種識別番号によって第ｎ−１種参照情報を指し示すようにすると共に、
分割元が同じ複数の第ｎ種小領域のうちの１つの第ｎ種小領域において第ｎ種小領域帰属代表値に選択された第ｎ−１種小領域帰属代表値を、前記分割元の第ｎ−１種小領域において予め定めた第ｎ−１種識別番号に割り当てることで、前記１つの第ｎ種小領域に係る第ｎ種参照情報を符号化しない
ことを特徴とする請求項６乃至９のいずれか一項に記載の画像符号化方法。
【請求項１１】
前記第ｋ種参照情報に第ｋ種識別番号を付与し、ラベル情報は前記第ｋ種識別番号によって第ｋ種参照情報を指し示すようにすると共に、
第ｋ種小領域に属する１つの特定画素で選択された第ｋ種小領域帰属代表値に対応する第ｋ種参照情報を予め定めた第ｋ種識別番号に割り当てることで、前記１つの特定画素に係るラベル情報を符号化しない
ことを特徴とする請求項６乃至１０のいずれか一項に記載の画像符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像を複数に分割した各小領域を、所定個数の代表値（代表色）で符号化する画像符号化方法に関する。
【背景技術】
【０００２】
画像情報を符号化して圧縮する方法として、符号化対象の画像を複数のブロックに分割し、ブロック毎に符号化するＢＴＣ（Block Truncation Coding）がある。たとえば、８×８画素の矩形のブロックに分割し、各ブロックをそのブロックの画素数より少ない所定数（たとえば、４個）の類似する色の画素同士のグループに分け、それぞれのグループにそのグループに属する画素の色を代表する代表値（代表色）を割り当てて減色し、符号化するようになっている（特許文献１参照）。
【０００３】
このような符号化方法で生成される符号情報は、一般に、各代表値を表す情報と、各画素がどの代表値に近似されるかを表す画素毎のラベル情報とから構成される。たとえば、１つの代表値がＣ（シアン）、Ｍ(マゼンタ)、Ｙ（イエロ）、Ｋ（ブラック）の４成分で構成され、それぞれの成分が８ビットで表される場合、１つの代表値の符号量は３２ｂｉｔになり、１つのブロックに対して４つの代表色を与えるとすると、代表値の符号量は３２×４＝１２８ｂｉｔになる。また、各画素のラベル情報は４つの代表値のいずれかを特定するために２ｂｉｔを要し、１ブロックが８×８画素の６４画素で構成されるならば、ラベル情報の符号量は２×６４＝１２８ｂｉｔになる。よって、この場合の１ブロック分の符号情報の符号量は、代表値とラベル情報とを合わせた、２５６ｂｉｔになる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００９−１０６５１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記のような符号化方法においては、代表値の数が多いと圧縮による画質劣化（圧縮歪）は少なくなるが、代表値の符号量が増えると共に、各画素について代表値を特定するためのラベル情報の符号量も増えて、圧縮効率が低下してしまう。一方、代表値の数が少ないと圧縮効率は高まるが、圧縮歪が大きくなってしまう。
【０００６】
本発明は、上記の問題を解決しようとするものであり、画質の劣化を抑えて圧縮率を向上させる、あるいは符号量を増加させずに実質的な代表値の数を増やして画質の向上を図ることのできる画像符号化方法を提供することを目的としている。
【課題を解決するための手段】
【０００７】
かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
【０００８】
［１］画像を複数の第１種小領域に分割し、
前記第１種小領域毎に、画像データの符号化を、
該第１種小領域を複数の第２種小領域に分割し、
該第１種小領域に対して、該第１種小領域に含まれる画素の画像データを代表する、該第１種小領域に含まれる画素数より少ない所定数の代表値を決定し、
前記第２種小領域毎に、前記所定数の代表値の中から前記第２種小領域の画素数より少ない規定数の代表値を第２種小領域帰属代表値として選択し、その選択した代表値を指し示す参照情報を求め、
該第１種小領域に属する画素毎に、その画素が属する第２種小領域に係る前記第２種小領域帰属代表値の中のいずれか１つを選択し、その選択した第２種小領域帰属代表値に対応する参照情報を指し示すラベル情報を求め、
前記所定数の代表値と、前記第２種小領域毎に求めた参照情報と、該第１種小領域に属する画素毎に求めたラベル情報と、を含む符号情報を生成する、
ことによって行う
ことを特徴とする画像符号化方法。
【０００９】
上記発明では、第１種小領域毎に符号化する際に、第１種小領域をさらに複数の第２種小領域に分割して階層的に符号化する。一般的に、画像データは、より近傍の画素であればあるほど相関性が高い性質がある。そこで、より小さい領域に分割すれば、その範囲での代表値数を少なくしても圧縮歪はそれほど増大することはない。一方、小さい領域毎に代表値を保持すれば、画像全体としては代表値の保持数が増えて、符号量が増大する。
【００１０】
そこで、本発明では、代表値は第１種小領域単位で、たとえば４色の代表値を保持し、この第１種小領域から分割された各第２種小領域は、それぞれ上記４色の代表値の中の２色を選択可能とし、かつその選択した代表値を特定するための情報として第１種小領域単位で保持している代表値を指し示す参照情報を保持する。また、第２種小領域に属する各画素は、その第２種小領域の参照情報（この例では２つ）のいずれかを指し示すラベル情報を保持する。これにより、各第２種小領域において２色を使用可能にしつつ、第１種小領域単位での符号量を低減することができる。
【００１１】
［２］予め所定の数の特定色を設定し、
第１種小領域に付与した代表値と前記特定色との中から前記第２種小領域帰属代表値を選択し、参照情報が、その選択した、第２種小領域帰属代表値に対応する代表値または特定色を指し示す
ことを特徴とする［１］に記載の画像符号化方法。
【００１２】
上記発明では、特定色は、その色情報を第１種小領域毎の符号情報として保持しない色であり、特定色が如何なる色であるかは、予め固定的に取り決めておく、ページ単位に設定しておく、などにより別途定められる。かかる特定色を設定することで、符号量の増加を抑えつつ、使用可能な色数を増やすことができる。
【００１３】
［３］予め特定色を設定し、
第１種小領域に属する画素に対して、その画素が属する第２種小領域に係る第２種小領域帰属代表値と前記特定色との中のいずれか１つを選択し、前記ラベル情報が、その選択した、第２小領域帰属代表値に対応する参照情報または特定色を指し示す
ことを特徴とする［１］または［２］に記載の画像符号化方法。
【００１４】
上記発明では、特定色を、ラベル情報で直接指し示す。
【００１５】
［４］前記代表値に第１種識別番号を付与し、参照情報は前記第１種識別番号によって代表値を指し示すようにすると共に、
分割元が同じ複数の第２種小領域のうちの１つの第２種小領域において第２種小領域帰属代表値に選択された代表値を予め定めた第１種識別番号に割り当てることで、前記１つの第２種小領域に係る参照情報を符号化しない
ことを特徴とする［１］乃至［３］のいずれか一項に記載の画像符号化方法。
【００１６】
上記発明では、各代表値に代表値番号などの識別情報(第１種識別情報)を与え、参照情報は代表値番号で代表色を特定するので、分割元が同じ複数の第２種小領域のうちの１つの第２種小領域については、第２種小領域帰属代表値に選択した代表値を予め定めた第１種識別番号に割り当てるようにすれば、該第２種小領域に係る参照情報を省略することができるので符号化しない。これにより、符号情報の符号量を削減することができる。
【００１７】
［５］前記参照情報に第２種識別番号を付与し、ラベル情報は前記第２種識別番号によって参照情報を指し示すようにすると共に、
第２種小領域に属する１つの特定画素で選択された第２種小領域帰属代表値を予め定めた第２種識別番号に割り当てることで、前記１つの特定画素に係るラベル情報を符号化しない
ことを特徴とする［１］乃至［４］のいずれか一項に記載の画像符号化方法。
【００１８】
上記発明では、参照情報に第２種識別番号を付与し、ラベル情報は第２種識別番号によって参照情報を特定するので、第２種小領域に属する１つの特定画素については、その特定画素の画素値に対応する第２種小領域帰属代表値を予め定めた第２種識別番号に割り当てることで、該特定画素に係るラベル情報を省略することができるので符号化しない。これにより、符号情報の符号量を削減することができる。
【００１９】
［６］画像を多階層に分割して符号化する画像符号化方法であって、
第ｎ種小領域（ｎは１以上の整数）を複数に分割した各小領域を第ｎ＋１種小領域と呼ぶものとして、
画像を複数の第１種小領域に分割し、
前記第１種小領域毎に、画像データの符号化を、
該第１種小領域を、第ｋ種小領域（ｋは３以上の整数）まで分割し、
前記第１種小領域に対して、該第１種小領域に含まれる画素の画像データを代表する第１種規定数の第１種小領域帰属代表値を決定し（ただし、第ｎ種規定数＞第ｎ＋１種規定数、かつ、第ｎ種規定数＜１つの第ｎ種小領域から分割された第ｎ＋１種小領域の数×第ｎ＋１種規定数、かつ、第ｎ種規定数＜第ｎ種小領域の画素数、の関係を持つ）、
第ｎ種小領域に対して、その第ｎ種小領域の分割元の第ｎ−１種小領域に係る第ｎ−１種小領域帰属代表値の中から第ｎ種規定数の第ｎ−１種小領域帰属代表値を第ｎ種小領域帰属代表値として選択し、その選択した第ｎ−１種小領域帰属代表値に対応する第ｎ−１種参照情報を指し示す第ｎ種参照情報を求めることを、ｎ＝２からｋまで行い、
該第１種小領域に属する画素毎に、その画素が属する第ｋ種小領域に係る第ｋ種小領域帰属代表値の中のいずれか１つを選択し、その選択した第ｋ種小領域帰属代表値に対応する第ｋ種参照情報を指し示すラベル情報を求め、
第１種規定数の第１種小領域帰属代表値と、第ｎ種小領域毎に求めた第ｎ種参照情報（ｎ＝２からｋ）と、該第１種小領域に属する画素毎に求めたラベル情報と、を含む符号情報を生成する、
ことによって行う
ことを特徴とする画像符号化方法。
【００２０】
上記発明では、分割をより多階層化することで、圧縮歪を低減しつつ符号量の増加をより抑えることができる。
【００２１】
［７］予め所定の数の特定色を設定し、
第ｎ−１種小領域帰属代表値（ｎは２以上とする）と前記特定色との中から前記第ｎ種小領域帰属代表値を選択し、ｎ＝２の場合には、第ｎ種参照情報がその選択した第ｎ−１種小領域帰属代表値または特定色を指し示し、ｎ≧３の場合には、第ｎ種参照情報がその選択した第ｎ−１種小領域帰属代表値に対応する第ｎ−１種参照情報または特定色を指し示す
ことを特徴とする［６］に記載の画像符号化方法。
【００２２】
［８］予め特定色を設定し、
第１種小領域に属する画素に対して、その画素が属する第ｋ種小領域に係る第ｋ種参照情報と前記特定色との中のいずれか１つを選択し、前記ラベル情報が、その選択した、第ｋ種参照情報または特定色を指し示す
ことを特徴とする［６］または［７］に記載の画像符号化方法。
【００２３】
上記［７］［８］に係る発明では、符号量の増加を抑えて、使用可能な色数を増やすことができる。
【００２４】
［９］前記第１種小領域帰属代表値に第１種識別番号を付与し、第２種参照情報は前記第１種識別番号によって第１種小領域帰属代表値を指し示すようにすると共に、
分割元が同じ複数の第２種小領域のうちの１つの第２種小領域において第２種小領域帰属代表値に選択された第１種小領域帰属代表値を予め定めた第１種識別番号に割り当てることで、前記１つの第２種小領域に係る第２種参照情報を符号化しない
ことを特徴とする［６］乃至［８］のいずれか一項に記載の画像符号化方法。
【００２５】
［１０］前記第ｎ−１種参照情報（ｎは３以上とする）に第ｎ−１種識別番号を付与し、第ｎ種参照情報は前記第ｎ−１種識別番号によって第ｎ−１種参照情報を指し示すようにすると共に、
分割元が同じ複数の第ｎ種小領域のうちの１つの第ｎ種小領域において第ｎ種小領域帰属代表値に選択された第ｎ−１種小領域帰属代表値を、前記分割元の第ｎ−１種小領域において予め定めた第ｎ−１種識別番号に割り当てることで、前記１つの第ｎ種小領域に係る第ｎ種参照情報を符号化しない
ことを特徴とする［６］乃至［９］のいずれか一項に記載の画像符号化方法。
【００２６】
［１１］前記第ｋ種参照情報に第ｋ種識別番号を付与し、ラベル情報は前記第ｋ種識別番号によって第ｋ種参照情報を指し示すようにすると共に、
第ｋ種小領域に属する１つの特定画素で選択された第ｋ種小領域帰属代表値に対応する第ｋ種参照情報を予め定めた第ｋ種識別番号に割り当てることで、前記１つの特定画素に係るラベル情報を符号化しない
ことを特徴とする［６］乃至［１０］のいずれか一項に記載の画像符号化方法。
【００２７】
上記［９］［１０］［１１］に係る発明では、［４］［５］と同様の手法により、符号量を削減することができる。
【発明の効果】
【００２８】
本発明に係る画像符号化方法によれば、画質の劣化を抑えて圧縮率を向上させる、あるいは符号量を増加させずに実質的な代表値の数を増やして画質の向上を図ることができる。
【図面の簡単な説明】
【００２９】
【図１】本発明の実施の形態に係る画像符号化装置としての機能を含む画像処理装置の概略構成を示すブロック図である。
【図２】元画像と、第１種小領域と、第２種小領域との関係を例示した説明図である。
【図３】分割符号化によって生成される符号情報を構成する符号データの関連性を示す説明図である。
【図４】特定色を設定した場合における符号データの関連性を示す説明図である。
【図５】分割符号化によって生成される符号情報の構成を模式的に示す説明図である。
【図６】分割符号化処理（１）の流れ図である。
【図７】分割符号化処理（２）の流れ図である。
【図８】タイプ別の符号情報の内訳を示す一覧表である。
【図９】判定テーブルを例示した図である。
【図１０】タイプ１の符号情報の一例を示す説明図である。
【図１１】タイプ２の符号情報の一例を示す説明図である。
【図１２】タイプ３の符号情報の一例を示す説明図である。
【図１３】第１種小領域を１６画素毎の４つの第２種小領域に分割する場合の各種の分割パターンを例示した説明図である。
【図１４】８画素×８画素の第１種小領域を、４画素×４画素の第２種小領域に分割し、さらに各第２種小領域を２画素×２画素の第３種小領域に分割した様子を示す説明図である。
【図１５】第３種小領域まで分割して生成した符号情報の構成例を示す説明図である。
【発明を実施するための形態】
【００３０】
以下、図面に基づき本発明の各種実施の形態を説明する。
【００３１】
図１は、本発明に係る画像符号化方法で画像を符号化する機能を含む画像処理装置の概略構成を示している。画像処理装置１０は、画像を符号化する符号化処理部１１と、符号化処理部１１で符号化して得たデータ（符号情報と呼ぶ。）を記憶する画像メモリ１２と、画像メモリ１２もしくは外部から符号情報を入力してこれを復号化する復号化処理部１３とから構成される。
【００３２】
符号化処理部１１は、符号化対象の元画像の画像情報を入力する画像入力部１４と、画像入力部１４によって入力した画像情報を、複数の小領域（ブロック）に分割する画像分割部１５と、画像分割部１５によって分割された小領域毎に画像情報を符号化する符号化部１６とを備えて構成される。
【００３３】
復号化処理部１３は、画像メモリ１２もしくは外部から符号情報を入力する符号入力部１７と、符号入力部１７によって入力した符号情報を復号化する復号化部１８と、復号化部１８が出力する復号化された画像情報を出力する画像出力部１９とを備えて構成される。
【００３４】
図１の画像処理装置１０には各々の処理部の起動や終了等の動作を制御する制御部、オペレータによる画像処理の実行指示等を受け付ける指示入力部、現在の処理状況等を表示する状態表示部、等、図示しない装備が適宜具備されても良い。また、図１の画像処理装置１０は符号化処理部１１、復号化処理部１３、画像メモリ１２を一つの装置としたが、これらは画像符号化装置や画像復号化装置など別体の装置として構成されてもよい。また、ＣＰＵ(Central Processing Unit）とＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）などを備えたコンピュータ装置において所定のプログラムを実行することにより画像符号化の機能等が実現されてもよい。
【００３５】
＜符号化処理の概要＞
本発明に係る画像符号化方法では、元画像を複数の小領域（第１種小領域）に分割し、各第１種小領域をさらに複数の第２種小領域に分割した上で、第１種小領域単位の符号情報を生成する（この符号化を分割符号化と呼ぶこととする。）。ここでは、図２に示すように、元画像３０を分割した８画素×８画素単位の領域を第１種小領域３１とし、第１種小領域３１をさらに４つに分割した４画素×４画素単位の領域を第２種小領域３２とする。
【００３６】
図３は、分割符号化によって生成される符号情報を構成する符号データの関連性を示している。同図（ａ）に示すように、分割符号化では、第１種小領域は第１種規定数（第１種小領域に含まれる画素数より少ない数、たとえば、４個）の代表値を有し、その第１種小領域から分割された第２種小領域はそれぞれ、第１種小領域が有する代表値の中のいずれか１つを指し示す代表値インデックス（参照情報）を第２種規定数（第２種小領域の画素数より少ない数、たとえば、２個）有し、各画素はその画素が含まれる第２種小領域が有する代表値インデックスのいずれか１つを指し示すラベル情報を持つ。
【００３７】
代表値にはそれぞれを特定するための代表値番号（第１種識別情報）が割り当てられ、代表値インデックスは代表値番号によって代表値を指し示す（特定する）。また各代表値インデックスにもインデックス番号（第２種識別情報）が割り当てられ、ラベル情報はインデックス番号によって代表値インデックスを指し示す（特定する）。
【００３８】
ただし、同一の第１種小領域から分割された複数の第２種小領域の中の１つの第２種小領域については、同図（ｂ）に示すように代表値インデックスを省略し、画素毎のラベル情報が直接、代表値を指し示すようにしてもよい。たとえば、所定の１つの第２種小領域で参照する２つの代表値を、代表値１、代表値２（代表値番号１，２）に割り当てるように取り決めれば、画素毎のラベル情報で直接に代表値１、２を指し示すことができ、代表値インデックスを省略することができる。
【００３９】
また、同図（ｃ）に示すように、同一の第２種小領域に属する画素の中の１つの特定画素については、その画素の画素値に対応する代表値インデックスを予め定めたインデックス番号に割り当てることで、該特定画素のラベル情報を省略することができる。たとえば、画素１の画素値に対応する代表値を指し示す代表値インデックスをインデックス番号１（代表値インデックス１）に割り当て、画素１についてのラベル情報は符号化しない。
【００４０】
さらに図４（ａ）に示すように、予め定めた特定色（色数任意）については、代表値データ（色情報）を第１種小領域単位の符号情報として保持せずに別途取り決めておき、第２種小領域の代表値インデックスによって特定色を指定できるようにする。たとえば、代表値インデックスの値「１」〜「４」により色情報を有する代表値１〜４を指し示し、代表値インデックスの値「５」は予め定めた特定色１を指し示し、代表値インデックスの値「６」は特定色２を指し示すようにする。
【００４１】
このような特定色を設定することで、代表値を持つための符号量を増やすことなく、より多くの色が使用可能となる。特定色は、固定されてもよいし、１ページの画像毎に特定色を選択可能にし、ページ単位の符号情報としてその特定色の情報を保持するようにしてもよい。また、１ページ内に任意の画像領域を設定可能とし、その画像領域毎に特定色を選択可能にしてその設定した画像領域に特定色の情報を保持するようにしてもよい。
【００４２】
また、同図（ｂ）に示すように、ラベル情報のある値によって特定色を、直接指し示すようにしてもよい。たとえば、ラベル情報の値「１」、「２」は代表値インデックス１、２を指し示し、ラベル情報の値「３」は特定色１を直接指し示すようにする。
【００４３】
図５は、分割符号化によって１つの第１種小領域を符号化した場合に得られる符号情報を模式的に示したものである。この例では、８画素×８画素の第１種小領域３１に対して４つの代表値１〜４を与えている。４画素×４画素の第２種小領域３２のうちの１つ（この例では第２種小領域３２ａ）を除くそれぞれに２つの代表値インデックスを与えている。第２種小領域３２ａを除く各第２種小領域３２については、その第２種小領域に属する各画素に対してその第２種小領域３２が有する２つの代表値インデックスのうちのいずれか１つを指し示すラベル情報を与えている。また、代表値インデックスを省略した第２種小領域３２ａについては、代表値１、２のいずれかを直接指し示すラベル情報を与えてある。
【００４４】
分割符号化では、第１種小領域単位ではＮ個（たとえば、４つ）の代表値（代表色）を有するが、各画素はその画素が属する第２種小領域が有するＭ個（たとえば、２個、Ｍ＜Ｎ）の代表値インデックスを指し示すことができればよいので、ラベル情報のｂｉｔ数を少なく抑えて符号化することができる。また、代表値インデックスは、代表値１〜４のいずれかを指し示すことができる符号で良いので、各２ｂｉｔで済む。
【００４５】
たとえば、図５の例において、代表値をＣＭＹＫの各色８ビットで表すとすると、１つの代表値は３２ｂｉｔで構成され、代表値インデックスは２ｂｉｔで構成され、各画素は２つの代表値インデックスのいずれかを指し示すので１ｂｉｔで構成される。よって、第１種小領域単位で保持する代表値の符号量は３２ｂｉｔ×４＝１２８ｂｉｔ、第２種小領域単位で保持する代表値インデックスの符号量は、１つの第２種小領域では代表値インデックスを省略するので、２ｂｉｔ×２×３＝１２ｂｉｔ、画素単位で保持するラベル情報の符号量は１ｂｉｔ×１６×４＝６４ｂｉｔ、になり、１つの第１種小領域の符号情報の符号量は２０４ｂｉｔになる。
【００４６】
従来のように、各画素のラベル情報が直接、４つの代表色のいずれかを指し示す場合には、ラベル情報として２ｂｉｔを要するので、画素単位で保持するラベル情報の符号量は２ｂｉｔ×６４＝１２８ｂｉｔになり、代表値４個分の符号量は３２ｂｉｔ×４＝１２８ｂｉｔなので、１つの第１種小領域の符号情報の符号量は２５６ｂｉｔになる。図５に示すような分割符号化を行うことで、２５６−２０４＝４２ｂｉｔが削減される。
【００４７】
一方、４×４画素の第２種小領域単位に２つの代表値を与えて独立に符号化する場合には、１つの第２種小領域について、３２ｂｉｔ×２＋１６ｂｉｔ＝８０ｂｉｔを要するので、第１種小領域の符号化に要する符号量は、３２０ｂｉｔになる。
【００４８】
一般的に、画像データは、より近傍の画素であればあるほど相関性が高い性質がある。そこで、より小さい領域に分割すれば、その範囲での代表値数を少なくしても圧縮歪はそれほど増大することはない。したがって、図５に示す分割符号化では、第１種小領域をさらに複数に分割した第２種小領域のそれぞれで２つの代表色を使用できるので、画質の劣化を少なく抑えることができ、かつまた、第１種小領域単位では４色使用可能でありながら各画素のラベル情報は１ｂｉｔで済むので、符号量を少なくすることができる。すなわち、分割符号化では、画質の劣化を抑えて圧縮率を向上させることができる、あるいは見方を変えれば、符号量を増加させずに実質的な代表値の数を増やして画質の向上を図ることができる。
【００４９】
図６は、分割符号化の処理の流れを示している。まず、元画像を第１種小領域に分割する（ステップＳ１０１）。そのうちの１つを符号化対象の第１種小領域として抽出し（ステップＳ１０２）、この第１種小領域を複数の第２種小領域に分割する（ステップＳ１０３）。符号化対象の第１種小領域に対して、第１種小領域に含まれる画素数より少ない第１種規定数（たとえば、４個）の代表値を決定する(ステップＳ１０４)。
【００５０】
なお、第１種規定数の代表値を決定する手法は任意でよいが、たとえば、第１種小領域に属する画素を色が近似する画素同士の第１種規定数のグループ（クラスタ）に分類し、グループ毎の代表値を決定すればよい。グループへの分類に際して、主成分分析や非階層的クラスタ分析等の手法を利用するとよい。
【００５１】
次に、第２種小領域毎に、ステップＳ１０４で決定した代表値の中から第２種規定数の代表値を第２種小領域帰属代表値として選択し、それら選択した代表値を指し示す代表値インデックス（参照情報）を作成する（ステップＳ１０５）。ここでは、第２種小領域に属する画素を色が近似する画素同士の第２種規定数のグループに分類し、グループ毎の仮代表値を決定し、各仮代表値に最近接（色空間において）の代表値を第２種小領域帰属代表値として選択する。グループへの分類に際して、主成分分析や非階層的クラスタ分析等の手法を利用するとよい。なお、特定色が設定されている場合は、代表値と特定色との中から第２種小領域帰属代表値を選択することができる。
【００５２】
続いて該第１種小領域に属する画素毎に、その画素が属する第２種小領域に係る第２種小領域帰属代表値のいずれか１つを選択し、その選択した第２種小領域帰属代表値に対応する代表値インデックスを指し示すラベル情報を作成する(ステップＳ１０６)。上記選択では、その画素が属する第２種小領域に係る第２種小領域帰属代表値の中でその画素の画素値に最近接（色空間において）の第２種小領域帰属代表値を選択する。なお、ラベル情報によって特定色を直接指し示すことを可能としている場合は、各画素の代表色として特定色を選択してもよい。
【００５３】
続いてステップＳ１０４で選択した第１種規定数の代表値と、ステップＳ１０５で各第２種小領域に対して第２種規定数ずつ作成した代表値インデックス（参照情報）と、ステップＳ１０６で作成した画素毎のラベル情報とを含む符号情報を生成する（ステップＳ１０７）。
【００５４】
符号化未処理の第１種小領域がある場合は（ステップＳ１０８；Ｎｏ）、ステップＳ１０２に移行して処理を継続する。すべての第１種小領域の符号化が完了したら（ステップＳ１０８；Ｙｅｓ））本処理を終了する。
【００５５】
なお、図６の分割符号化処理（１）では、すべての第２種小領域に代表値インデックスを付与するようにしたが、１つの第２種小領域について代表値インデックスを省略する場合には、図７に示す分割符号化処理（２）となる。図６と同一処理には同一のステップ番号を付してある。
【００５６】
図７の処理では、ステップＳ１０４で決定した代表値の中から、代表値インデックスを省略する第２種小領域で使用（参照）する第２種規定数の代表値を選択し（ステップＳ１１１）、それらを予め定めた番号の代表値（たとえば、代表値１、２）に割り当てる（ステップＳ１１２）。ここでは、第２種小領域に属する画素を色が近似する画素同士の第２種規定数のグループに分類し、グループ毎の仮代表値を決定し、各仮代表値に最近接（色空間において）の代表値を選択する。グループへの分類に際して、主成分分析や非階層的クラスタ分析等の手法を利用するとよい。なお、代表値インデックスを省略する第２種小領域では第２種小領域帰属代表色として特定色を選択しないものとする。
【００５７】
次に、代表値インデックスを省略しない第２種小領域毎に、第２種規定数の代表値を先と同様に最近接を基準に選択し、選択した各代表値を指し示す代表値インデックス（参照情報）を作成する（ステップＳ１１３）。なお、特定色が設定されている場合には、代表値インデックスを省略しない第２種小領域については代表値と特定色との中から第２種小領域帰属代表値を選択することができる。
【００５８】
次に、代表値インデックスを省略していない第２種小領域の各画素について、その画素が属する第２種小領域が有するいずれかの代表値インデックスを指し示すラベル情報を付与する（ステップＳ１１４）。上記選択および付与は、その画素が属する第２種小領域に係る第２種小領域帰属代表値の中でその画素の画素値に最近接（色空間において）の第２種小領域帰属代表値を選択し、その第２種小領域帰属代表値に対応する代表値インデックスを指し示すラベル情報を付与するようにすればよい。なお、ラベル情報によって特定色を直接指し示すことを可能としている場合は、各画素の代表色として特定色を選択してもよい。
【００５９】
代表値インデックスを省略した第２種小領域の各画素には、ステップＳ１１１で選択した代表値（代表値１、２）のうちその画素の画素値に最近接の代表値を指し示すラベル情報を付与する（ステップＳ１１５）。
【００６０】
そして、ステップＳ１０４で選択した第１種規定数の代表値と、ステップＳ１１３で作成した代表値インデックス（参照情報）と、ステップＳ１１４およびＳ１１５で作成した画素毎のラベル情報とを含む符号情報を生成する（ステップＳ１１６）。
【００６１】
符号化未処理の第１種小領域がある場合は（ステップＳ１１７；Ｎｏ）、ステップＳ１０２に移行して処理を継続する。すべての第１種小領域の符号化が完了したら（ステップＳ１１７；Ｙｅｓ））本処理を終了する。
【００６２】
次に、帰属する代表値数を第２種小領域毎に変化させる場合について説明する。
【００６３】
第１種小領域の中にも局所的な色の分布があり、第１種小領域を分割した複数の第２種小領域の中に、代表値１つで表すことが可能な平坦な画像部分もあれば、エッジ部分のように多くの色が含まれる場合もある。そこで、各第２種小領域に対して与えるべき代表値の数を評価し、第２種小領域別に帰属させる代表値の数を変化させることで、第１種小領域単位での符号量を増やすことなく、より少ない歪で画像を符号化することが可能になる。以後、第２種小領域に帰属させる代表値の数を変化させる符号化を、色数適用型符号化と呼ぶものとする。
【００６４】
ここでは、以下のような条件で色数適用型符号化の例に説明する。第１種小領域を８画素×８画素の領域とし、第１種小領域に対して４つの代表値を与えるものとする。また、第２種小領域は第１種小領域を４つに分割した４画素×４画素の領域とし、第１種小領域内の色の分布に応じて、次の３つの符号化タイプのいずれかを選択可能とする。
【００６５】
タイプ１：２色、２色、２色、２色
タイプ２：４色、２色、２色、１色
タイプ３：４色、４色、１色、１色
なお、４色の代表値が帰属する第２種小領域については、代表値以外の予め定めた特定色を想定しない。その他の第２種小領域については、代表値以外の特定色に対応付け可能とする。
【００６６】
色数適用型符号化の符号化形式は以下の通りとする。
＜符号量＞
第１種小領域単位での符号量は２０５ｂｉｔ（特定色を適用する場合は２０９ｂｉｔ）固定とする。
【００６７】
＜符号構成＞
・タイプ識別コード（１〜２ｂｉｔ）
０・・・タイプ１
１０・・・タイプ２
１１・・・タイプ３
・第１種小領域代表値（４×３２ｂｉｔ）
代表値１（Ｃ，Ｍ，Ｙ，Ｋ）、
代表値２（Ｃ，Ｍ，Ｙ，Ｋ）、
代表値３（Ｃ，Ｍ，Ｙ，Ｋ）、
代表値４（Ｃ，Ｍ，Ｙ，Ｋ）
・第２種小領域色数識別コード
タイプ１・・・なし
タイプ２・・・４ｂｉｔ  下記１２通りを識別
（４２２１，４２１２，４１２２，２４２１，２４１２，２２４１，２２１４，２１４２，２１２４，１４２２，１２４２，１２２４）
タイプ３・・・３ｂｉｔ  下記６通りを識別
（４４１１，４１４１，４１１４，１４４１，１４１４，１１４４）
・第２種小領域インデックス
タイプ１・・・３×４ｂｉｔ（または４×４ｂｉｔ）
第２種小領域１の２色は代表値１・代表値２に固定（０ｂｉｔ）
第２種小領域２〜４はそれぞれ２つの代表値を選択（２×２ｂｉｔ）
タイプ２・・・４ｂｉｔ＋２ｂｉｔ（または、２×４ｂｉｔ＋２ｂｉｔ）
４色の第２種小領域は選択不要（０ｂｉｔ）
２色の第２種小領域のうち１つは、代表値１・代表値２に固定（０ｂｉｔ）
他の２色の第２種小領域につき、２つの代表値を選択（２×２ｂｉｔ）
１色の第２種小領域は１つの代表値を選択（２ｂｉｔ）
タイプ３・・・２ｂｉｔ（または２×２ｂｉｔ）
４色の第２種小領域は選択不要（２×０ｂｉｔ）
１色の第２種小領域のうち１つは代表値１に固定（０ｂｉｔ）
他の１色のサブブロックは１つの代表値を選択（２ｂｉｔ）
・ラベル（６４ｂｉｔ）
４色の第２種小領域は、１６×２ｂｉｔ
２色の第２種小領域は、１６×１ｂｉｔ
１色の第２種小領域は、１６×０ｂｉｔ
タイプ１、タイプ２、タイプ３とも計６４ｂｉｔとなる。
【００６８】
図８は、タイプ別の符号情報の内訳を一覧で示したものである。２０５ｂｉｔあるいは２０９ｂｉｔの固定長にする（最大のタイプ１にあわせる）ために、タイプ２、タイプ３には、余ったｂｉｔ数分だけ無意味な符号で埋めてパディングされる。
【００６９】
次に、色数適用型符号化の手順（アルゴリズム）を、第１方式と、簡易な第２方式について説明する。
【００７０】
＜第１方式＞
各第１種小領域について、
１）第１種小領域の６４画素について、主成分分析により、第１主成分と第２主成分を求める。
【００７１】
２）６４画素の第１主成分スコアと第２主成分スコアに基づき、代表値４色を非階層的クラスタ分析等によって決定する。
３）各第２種小領域につき、１６画素の主成分スコアに関して、
ａ）最近接代表値への平方距離の和の平均
ｂ）代表値４色から２色を選択した場合の最近接代表値への平方距離の和の平均が最も小さくなる場合の値
ｃ）代表値１色から１色を選択した場合の最近接代表値への平方距離の和の平均が最も小さくなる場合の値
をそれぞれ計算し、さらにタイプ１、タイプ２、タイプ３を適用し、４つの第２種小領域の最大の平方距離の和の平均が最も小さくなるように、符号化タイプおよび各第２種小領域の色数（第２種小領域色数識別コード・・・色数の組み合わせ）を決定する。
（なお上記計算において画素数は常に一定なので、平均ではなく積算値を使用してもかまわない。）
４）決められた符号化タイプに基づいて、各第２種小領域のインデックス（代表値インデックス）、各画素のラベルを求めて符号化する。
【００７２】
＜第２方式＞
各第１種小領域について、
１）第１種小領域の６４画素について、主成分分析により、第１主成分と第２主成分を求める。
２）６４画素の第１主成分スコアと第２主成分スコアに基づき、代表値４色を非階層的クラスタ分析等によって決定する。
３）各第２種小領域につき、１６画素の主成分スコアに関して、
ａ）最近接の代表値に基づいてクラスタ分割
ｂ）第２種小領域のクラスタ数を評価
４）第２種小領域のクラスタ数に基づき、第２種小領域毎の代表値インデックス数、符号化タイプを決定する。たとえば、図９に示すような判定テーブルを予め用意しておき、該判定テーブルを参照して符号化タイプおよび各第２種小領域のインデックス数(使用する色数)を決定する。
５）各第２種小領域のインデックス数に基づき、最適なインデックス（平方距離和を最小化する条件）を選択し、それに基づいて画素毎のラベルを求めて、符号化する。
【００７３】
図１０は、タイプ１の符号情報の一例である。なお、第１種小領域をブロック、第２種小領域をサブブロックとも呼ぶこととする。サブブロック１ではインデックスは省略されており、サブブロック１のラベル情報「０」が代表色１を直接指し示し、サブブロック１のラベル情報「１」が代表色２を直接指し示している。
【００７４】
また、サブブロック１の画素１−１に対するラベル情報は省略されており、画素１−１に対応させるべき代表色を、ブロックの代表色１に割り当ててある。サブブロック２では、画素２−１に対応させるべき代表色を、当該サブブロック２が有する２つのインデックスのうちの予め定めたもの（たとえば、インデックス０、１のうちの０）が指し示すようにすることで、画素２−１のラベル情報を省略してある。サブブロック３、４でも同様にして、画素３−１、画素４−１のラベル情報を省略してある。このような省略を行うことで、ブロックの符号量は２０１ｂｉｔに削減されている。
【００７５】
図１１は、タイプ２の符号情報の一例である。この例では、サブブロック１の色数は４、サブブロック２、３の色数は２、サブブロック４の色数は１となっている。サブブロック１のインデックスは省略されており、たとえば、サブブロック１のラベル情報「０」が代表色１を直接指し示し、サブブロック１のラベル情報「１」が代表色２を直接指し示し、サブブロック１のラベル情報「２」が代表色３を直接指し示し、サブブロック１のラベル情報「３」が代表色４を直接指し示すようになっている。
【００７６】
また、サブブロック２のインデックスも省略されており、サブブロック２のラベル情報「０」が代表色１を直接指し示し、サブブロック２のラベル情報「１」が代表色２を直接指し示すようになっている。
【００７７】
また、サブブロック２の画素２−１に対するラベル情報は省略されており、画素２−１に対応させるべき代表色を、ブロックの代表色１に割り当ててある。サブブロック３では、画素３−１に対応させるべき代表色を、当該サブブロック３が有する２つのインデックスのうちの予め定めたもの（たとえば、インデックス０、１のうちの０）が指し示すようにすることで、画素３−１のラベル情報を省略してある。
【００７８】
さらにサブブロック４では色数が１なのでインデックスが１つのみであり、各画素のラベル情報はすべて省略されている。
【００７９】
このような省略を行うことで、ブロックの符号量は２０２ｂｉｔに削減されている。なお、この例のタイプ２の場合、最初に、サブブロック２の画素２−１に対応させるべき代表色を代表色１に、サブブロック２で使用する他の１つの代表色を代表色２に設定すればよい。
【００８０】
図１２は、タイプ３の符号情報の一例である。この例では、サブブロック１、２の色数は４、サブブロック３、４の色数は１となっている。サブブロック１、２のインデックスは省略されており、たとえば、サブブロック１、２のラベル情報「０」が代表色１を直接指し示し、ラベル情報「１」が代表色２を直接指し示し、ラベル情報「２」が代表色３を直接指し示し、ラベル情報「３」が代表色４を直接指し示すようになっている。
【００８１】
サブブロック３ではインデックスおよびラベル情報がそれぞれ省略されている。たとえば、サブブロック３で使用する１つの代表色を代表色１に割り当てるようになっている。サブブロック４のラベル情報は省略されており、サブブロック４が持つ１つのインデックスにより、サブブロック４で使用する１つの代表色を指し示すようになっている。このような省略を行うことで、ブロックの符号量は１９９ｂｉｔに削減されている。
【００８２】
図１０〜図１２に示す形式の符号情報を使用すれば、１ブロックあたりの符号量を２０２ｂｉｔの固定長（タイプ１、タイプ３ではパディングを行う）に削減することができる。
【００８３】
このように色数適用型符号化を採用すれば、エッジ部分などを含む第１種小領域において、符号量をほとんど増やすことなく圧縮歪の格段の低減を図ることが可能になる。特に文字画像などでは、平坦部に対してエッジが局在化し、色数の分布が局所的に偏るケースが多いので、色数適用型符号化による画質向上の効果がよく現れる。
【００８４】
次に、第２種小領域の分割方法を画像に応じて変化させる場合について説明する。
【００８５】
第１種小領域を、個々の第２種小領域に含まれる色数が少なくなるように分割すれば、インデックス（代表値インデックス）やラベル情報の符号量を少なくすることができる。
【００８６】
図１３は、第１種小領域を１６画素毎の４つの第２種小領域に分割する場合の各種の分割パターン（ａ〜ｊ）を例示している。同図では、同一色もしくは模様の画素が同一の第２種小領域に属している。
【００８７】
第２種小領域の分割パターンを変化させる符号化方法（分割パターン適用型符号化と呼ぶものとする）の手順を以下に例示する。
１）第１種小領域毎に、図１３に示すような予め定めた分割パターンのうちの幾つかを適用させ、第２種小領域内の色成分の分散の和が最小となる分割パターンを選択する。
２）各第２種小領域に含まれる画素データに基づき、第２種小領域毎に仮代表値を２色決定する。
３）第１種小領域に含まれる４つの第２種小領域の仮代表値の計８色に基づいて第１種小領域の代表値４色を非階層的クラスタ分析等の手法によって決定し、これらを符号化する。
４）第２種小領域毎に、上記２）で決定した当該第２種小領域の仮代表値につき、３）で決定した第１種小領域の代表値の中から最近接のものを選択し、選択した代表値を指し示す代表値インデックスを符号化する。
５）各画素につき、４）で決定した代表値（当該画素が含まれる第２種小領域が有する代表値インデックスが指し示す代表値）の中から最近接のものを選択し、その代表値に対応する代表値インデックスを指し示すラベル情報を符号化する。
【００８８】
このように分割パターン適用型符号化では、図形パターンなどに対し、個々の第２種小領域の色数が少なくなるように適応的にパターンが選択されるので、圧縮歪を小さくできる可能性が高くなる。また、色数適用型符号化と分割パターン適用型符号化とを併用すれば、より圧縮率を高めて符号化することも可能になる。
【００８９】
次に、多階層化による符号化について説明する。
【００９０】
多層化による符号化では画像を多階層に分割して符号化する。第ｎ種小領域（ｎは１以上の整数）を複数に分割した各小領域を第ｎ＋１種小領域と呼ぶものとして、画像を第ｋ種小領域（ｋ≧３）までに分割して、第１種小領域単位に符号化する。たとえば、図１４は、Ｋ＝３とする場合であり、８画素×８画素の第１種小領域４１を、４画素×４画素の４つの第２種小領域４２に分割し、さらに第２種小領域４２をそれぞれ２画素×２画素の４つの第３種小領域４３に分割している。
【００９１】
図１３の例の場合の符号化手順は以下のようになる。
１）各第３種小領域４３について、その第３種小領域に含まれる４画素に基づいて第３種小領域の仮代表値（第３種仮代表値）２色を決定する。  
２）各第２種小領域４２について、その第２種小領域に含まれる４つの第３種小領域の仮代表値の計８色に基づいて当該第２種小領域の仮代表値（第２種仮代表値）３色を非階層的クラスタ分析等の手法によって決定する。
３）第１種小領域４１に含まれる４つの第２種小領域の仮代表値の計１２色に基づいて第１種小領域の代表値（第１種小領域帰属代表値）４色を非階層的クラスタ分析等の手法によって決定し、これらを符号化する。
４）第２種小領域毎に、上記２）で決定した当該第２種小領域の仮代表値につき、３）で決定した第１種小領域の代表値の中から最近接のものを第２種小領域帰属代表値として選択し、選択した代表値を指し示す代表値インデックスを符号化する。
５）第３種小領域毎に、上記１）で決定した当該第３種小領域の仮代表値につき、４）で決定した、当該第３種小領域が含まれる第２種小領域の代表値インデックスが指し示す代表値（第２種小領域帰属代表値）の中から最近接のものを第３種小領域帰属代表値として選択し、これを指し示す第２種小領域の代表値インデックスを指し示す代表値インデックスを符号化する。
６）各画素につき、５）で決定した、当該画素が含まれる第３種小領域の代表値インデックスが間接に指し示す代表値（第３種小領域帰属代表値）の中から最近接のものを選択し、その選択した代表値に対応する当該第３種小領域の代表値インデックスを指し示すラベル情報を符号化する。
【００９２】
図１５は、上記手順により、第３種小領域まで分割して生成した符号情報の構成例を示している。なお、第３種小領域をサブサブブロックとも呼ぶものとする。
【００９３】
サブブロック１〜４では、代表値１〜４のうちの３色を指定する代わりに、除外する１色を指定するようになっている。また、サブブロック１においては除外する代表色を代表色４に固定することで、インデックスを省略している。サブブロック２〜４のインデックスは、４つの代表色の中から除外する１色を指定するので、各２ｂｉｔになっている。
【００９４】
サブサブブロックのインデックスは、そのサブサブブロックが属するサブブロックのインデックスが示す３つの代表色の中の２色を指定する代わりに除外する１色を指定する。よって、サブサブブロックのインデックスは２ｂｉｔになっている。なお、サブサブブロック１−１においては、除外する１色を、上位のサブブロックのインデックスが示す３つの代表色の中の３色目に固定することで、インデックスを省略している。
【００９５】
各画素のラベル情報は、サブサブブロックのインデックスが示す２色の中のいずれか一方を指し示すので、１ｂｉｔになっている。なお、各サブブロックの１画素目（画素１−１−１、画素２−１−１、画素３−１−１、画素４−１−１）については、その画素が属するサブサブブロックのインデックスが示す２色のうちの１色目に固定することで、ラベル情報を省略している。
【００９６】
第３種小領域までの多階層による符号化および上記のような省略を行うことで、１ブロックの符号量は２２４ｂｉｔに削減されている。
【００９７】
なお、サブブロックのインデックスを使用せずに、各サブサブブロックのインデックスが、ブロックが有する４つの代表値１〜４の中のいずれか２つを直接指定するように構成されてもよい。図１４に示すように、４色の中の２色を指定する場合、その組み合わせは、｛代表値１，代表値２｝、｛代表値１，代表値３｝、｛代表値１，代表値４｝、｛代表値２，代表値３｝、｛代表値２，代表値４｝、｛代表値３，代表値４｝  の６通りある。このなかのいずれの組み合わせであるかを示す情報によって２色を指定すれば、３ｂｉｔで２色を指定することができる。この場合、符号情報は、ブロック（第１種小領域）に係る４つの代表値（３２ｂｉｔ×４＝１２８ｂｉｔ）と、１６個のサブサブブロック（第３種小領域）のインデックス（３ｂｉｔ×１６＝４８ｂｉｔ）、画素毎のラベル情報（１ｂｉｔ×６４画素＝６４ｂｉｔ）で構成され、符号量は２４０ｂｉｔになる。
【００９８】
なお、多階層の符号化は第３種小領域をさらに複数に分割した第４種小領域や、さらに分割を進めた第５種小領域など多階層に分割してもかまわない。
【００９９】
第ｋ種小領域まで分割する場合の多階層符号化の手順は以下のようになる。
１）画像を複数の第１種小領域に分割するステップと、
２）第１種小領域毎に、画像データの符号化を、
２−１）第１種小領域に対して、該第１種小領域に含まれる画素の画像データを代表する第１種規定数の第１種小領域帰属代表値を決定し（ただし、第ｎ種規定数＞第ｎ＋１種規定数、かつ、第ｎ種規定数＜１つの第ｎ種小領域から分割された第ｎ＋１種小領域の数×第ｎ＋１種規定数、かつ、第ｎ種規定数＜第ｎ種小領域の画素数、の関係を持つ）、
２−２）第ｎ種小領域に対して、その第ｎ種小領域の分割元の第ｎ−１種小領域に係る第ｎ−１種小領域帰属代表値の中から第ｎ種規定数の第ｎ−１種小領域帰属代表値を第ｎ種小領域帰属代表値として選択し、その選択した第ｎ−１種小領域帰属代表値に対応する第ｎ−１種参照情報（第ｎ−１種代表値インデックス）を指し示す第ｎ種参照情報（第ｎ種代表値インデックス）を求めることを、ｎ＝２からｋまで行い、
２−３）該第１種小領域に属する画素毎に、その画素が属する第ｋ種小領域に係る第ｋ種小領域帰属代表値の中のいずれか１つを選択し、その選択した第ｋ種小領域帰属代表値に対応する第ｋ種参照情報を指し示すラベル情報を求め、
２−４）第１種規定数の第１種小領域帰属代表値と、第ｎ種小領域毎に求めた第ｎ種参照情報（ｎ＝２からｋ）と、該第１種小領域に属する画素毎に求めたラベル情報と、を含む符号情報を生成する。
【０１００】
また、第ｋ種小領域まで分割する場合の多階層符号化における、第ｎ種参照情報の省略は、次のようになる。
分割元が同じ複数の第ｎ種小領域のうちの１つの第ｎ種小領域において第ｎ種小領域帰属代表値に選択された第ｎ−１種小領域帰属代表値を、分割元の第ｎ−１種小領域において予め定めた第ｎ−１種識別番号に割り当てることで、１つの第ｎ種小領域に係る第ｎ種参照情報を符号化しない。
【０１０１】
また、第ｋ種小領域まで分割する場合の多階層符号化における、ラベル情報の省略は、次のようになる。
第ｋ種小領域に属する１つの特定画素で選択された第ｋ種小領域帰属代表値に対応する第ｋ種参照情報を予め定めた第ｋ種識別番号に割り当てることで、１つの特定画素に係るラベル情報を符号化しない。
【０１０２】
第ｋ種小領域まで分割する場合の多階層符号化する場合における、特定色の設定については、
第ｎ−１種小領域帰属代表値（ｎは２以上とする）と特定色との中から第ｎ種小領域帰属代表値を選択し、ｎ＝２の場合には、第ｎ種参照情報がその選択した第ｎ−１種小領域帰属代表値または特定色を指し示し、ｎ≧３の場合には、第ｎ種参照情報がその選択した第ｎ−１種小領域帰属代表値に対応する第ｎ−１種参照情報または特定色を指し示す、ようにすることとなる。
【０１０３】
また、第１種小領域に属する画素に対して、その画素が属する第ｋ種小領域に係る第ｋ種参照情報と特定色との中のいずれか１つを選択し、ラベル情報が、その選択した、第ｋ種参照情報または特定色を指し示す、ようにしてもよい。
【０１０４】
以上、本発明の実施の形態を図面によって説明してきたが、具体的な構成は実施の形態に示したものに限られるものではなく、本発明の要旨を逸脱しない範囲における変更や追加があっても本発明に含まれる。
【符号の説明】
【０１０５】
１０…画像処理装置
１１…符号化処理部
１２…画像メモリ
１３…復号化処理部
１４…画像入力部
１５…画像分割部
１６…符号化部
１７…符号入力部
１８…復号化部
１９…画像出力部
３０…元画像
３１…第１種小領域
３２…第２種小領域
３２ａ…代表値インデックスを省略した第２種小領域
４１…第１種小領域
４２…第２種小領域
４３…第３種小領域
【図１】
2011166454.tif 000003
【図２】
2011166454.tif 000004
【図３】
2011166454.tif 000005
【図４】
2011166454.tif 000006
【図５】
2011166454.tif 000007
【図６】
2011166454.tif 000008
【図７】
2011166454.tif 000009
【図８】
2011166454.tif 000010
【図９】
2011166454.tif 000011
【図１０】
2011166454.tif 000012
【図１１】
2011166454.tif 000013
【図１２】
2011166454.tif 000014
【図１４】
2011166454.tif 000015
【図１５】
2011166454.tif 000016
【図１３】
2011166454.tif 000017