(57)【要約】　　　（修正有）【課題】画質と圧縮率を保持した状態で付加情報の付与が可能な画像フォーマットと符号化システムを提供する。【解決手段】与えられた画像に対し特定ピクセルサイズのブロック画像に分割するブロック分割手段１０１と、ブロックを代表する代表色を少なくとも１つ以上算出する代表色算出手段１０２と、代表色の中で符号化フォーマットに基づき少なくとも２つ以上の代表色の補間で表現できるものを決定すると同時に代表色間の補間係数を決定する補間代表色決定手段１０３と、代表色及び補間係数に従い代表色間の補間で求められた補間代表色の中から、ブロックを構成する各ピクセルの色を代表させるものを決定し、そのインデックス情報に符号化するピクセル情報符号化手段１０４と、代表色、補間係数及び符号化ピクセル情報とを符号化フォーマットに従って構成する符号化ブロック生成手段１０５と、符号化ブロックを連結するブロック連結手段１０６とで構成される。【選択図】　　図１
2004104621.tif 000002
【特許請求の範囲】
【請求項１】
画像情報を特定の画像ブロックに分割するブロック分割部と、
前記分割した各画像ブロック単位において少なくとも２つ以上の代表色を求める代表色算出部と、
前記求めた代表色から他の２つ以上の代表色の補間で表現できる代表色を補間代表色として決定すると共に、その補間を行うための補間係数を計算する補間代表色決定部と、
前記各画像ブロックを構成する各ピクセルを、前記求めた代表色、または、前記求めた補間代表色で表現するかを決定して符号化して符号化画像を求めるピクセル情報符号化部と、
前記求めた代表色、前記求めた補間係数及び前記求めた符号化画像とを組み合わせ、ブロック単位の符号化画像である符号化ブロックを生成する符号化ブロック生成部と、
前記生成した符号化ブロックを連結して最終的な符号化画像を構成するブロック連結部と、
を有する
ことを特徴とする画像符号化装置。
【請求項２】
画像情報を特定の画像ブロックに分割するブロック分割部と、
前記分割した各画像ブロック単位において少なくとも２つ以上の代表色を求める代表色算出部と、
前記求めた代表色から他の２つ以上の代表色の補間で表現できる代表色を補間代表色として決定し、この補間代表色の数に応じた符号化フォーマットを決定すると共に、その補間を行うための補間係数を計算する補間代表色決定部と、
前記各画像ブロックを構成する各ピクセルを、前記求めた代表色、または、前記求めた補間代表色のいずれで表現するかを決定して符号化して符号化画像を求めるピクセル情報符号化部と、
前記求めた代表色、前記求めた補間係数及び前記求めた符号化画像とを、前記決定した符号化フォーマットに応じて配置することでブロック単位の符号化画像を生成する符号化ブロック生成部と、
前記決定した各ブロック毎の符号化フォーマット情報を格納したヘッダ情報を生成するヘッダ情報生成部と、
前記生成した符号化ブロック及び前記生成したヘッダ情報を連結して最終的な符号化画像を構成するブロック連結部と、
を有する
ことを特徴とする画像符号化装置。
【請求項３】
画像情報を特定の符号化された画像ブロックに分割するブロック分割部と、
前記分割された各符号化された画像ブロック単位に少なくとも２つ以上の代表色、補間代表色を算出する補間係数及びピクセル情報を符号化した符号化画像を取り出す符号化ブロック分解部と、
前記求めた代表色及び補間係数から補間代表色を算出する補間代表色算出部と、
前記求めた補間代表色、前記代表色及び前記符号化画像とから、ピクセル単位にカラー情報を復号してブロック毎の復号化画像を求めるピクセル情報復号化部と、
前記求めたブロック単位の復号化画像を連結して最終的な復号化画像を構成するブロック連結部と、
を有する
ことを特徴とする画像復号化装置。
【請求項４】
画像情報をヘッダ情報と符号化された画像ブロックに分割するブロック分割部と、
前記ヘッダ情報から前記分割された各画像ブロック単位に符号化フォーマットを判定するフォーマット判定部と、
前記分割された各画像ブロック単位に少なくとも２つ以上の代表色、補間代表色を算出するための補間係数及びピクセル情報を符号化した符号化画像を取り出す符号化ブロック分解部と、
前記求めた代表色及び補間係数から補間代表色を前記判定した符号化フォーマットに従った数だけ算出する補間代表色算出部と、
前記求めた補間代表色、前記代表色及び前記符号化画像とから、ピクセル単位にカラー情報を復号してブロック毎の復号化画像を求めるピクセル情報復号化部と、
前記求めたブロック単位の復号化画像を連結して最終的な復号化画像を構成するブロック連結部と、
を有する
ことを特徴とする画像復号化装置。
【請求項５】
画像情報を特定の画像ブロックに分割するブロック分割ステップと、
前記分割した各画像ブロック単位において少なくとも２つ以上の代表色を求める代表色算出ステップと、
前記求めた代表色から他の２つ以上の代表色の補間で表現できる代表色を補間代表色として決定すると共に、その補間を行うための補間係数を計算する補間代表色決定ステップと、
前記各画像ブロックを構成する各ピクセルを、前記求めた代表色、または、前記求めた補間代表色で表現するかを決定して符号化して符号化画像を求めるピクセル情報符号化ステップと、
前記求めた代表色、前記求めた補間係数及び前記求めた符号化画像とを組み合わせ、ブロック単位の符号化画像である符号化ブロックを生成する符号化ブロック生成ステップと、
前記生成した符号化ブロックを連結して最終的な符号化画像を構成するブロック連結ステップと、
を有する
ことを特徴とする画像符号化方法。
【請求項６】
画像情報を特定の画像ブロックに分割するブロック分割ステップと、
前記分割した各画像ブロック単位において少なくとも２つ以上の代表色を求める代表色算出ステップと、
前記求めた代表色から他の２つ以上の代表色の補間で表現できる代表色を補間代表色として決定し、この補間代表色の数に応じた符号化フォーマットを決定すると共に、その補間を行うための補間係数を計算する補間代表色決定ステップと、
前記各画像ブロックを構成する各ピクセルを、前記求めた代表色、または、前記求めた補間代表色のいずれで表現するかを決定して符号化して符号化画像を求めるピクセル情報符号化ステップと、
前記求めた代表色、前記求めた補間係数及び前記求めた符号化画像とを、前記決定した符号化フォーマットに応じて配置することでブロック単位の符号化画像を生成する符号化ブロック生成ステップと、
前記決定した各ブロック毎の符号化フォーマット情報を格納したヘッダ情報を生成するヘッダ情報生成ステップと、
前記生成した符号化ブロック及び前記生成したヘッダ情報を連結して最終的な符号化画像を構成するブロック連結ステップと、
を有する
ことを特徴とする画像符号化方法。
【請求項７】
画像情報を特定の符号化された画像ブロックに分割するブロック分割ステップと、
前記分割された各符号化された画像ブロック単位に少なくとも２つ以上の代表色、補間代表色を算出する補間係数及びピクセル情報を符号化した符号化画像を取り出す符号化ブロック分解ステップと、
前記求めた代表色及び補間係数から補間代表色を算出する補間代表色算出ステップと、
前記求めた補間代表色、前記代表色及び前記符号化画像とから、ピクセル単位にカラー情報を復号してブロック毎の復号化画像を求めるピクセル情報復号化ステップと、
前記求めたブロック単位の復号化画像を連結して最終的な復号化画像を構成するブロック連結ステップと、
を有する
ことを特徴とする画像復号化方法。
【請求項８】
画像情報をヘッダ情報と符号化された画像ブロックに分割するブロック分割ステップと、
前記ヘッダ情報から前記分割された各画像ブロック単位に符号化フォーマットを判定するフォーマット判定ステップと、
前記分割された各画像ブロック単位に少なくとも２つ以上の代表色、補間代表色を算出するための補間係数及びピクセル情報を符号化した符号化画像を取り出す符号化ブロック分解ステップと、
前記求めた代表色及び補間係数から補間代表色を前記判定した符号化フォーマットに従った数だけ算出する補間代表色算出ステップと、
前記求めた補間代表色、前記代表色及び前記符号化画像とから、ピクセル単位にカラー情報を復号してブロック毎の復号化画像を求めるピクセル情報復号化ステップと、
前記求めたブロック単位の復号化画像を連結して最終的な復号化画像を構成するブロック連結ステップと、
を有する
ことを特徴とする画像復号化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ブロック単位の画像符号化法に関するものであり、特に、３次元コンピュータグラフィックス分野における圧縮率固定のテクスチャ画像圧縮に関わる。
【０００２】
【従来の技術】
３次元コンピュータグラフィクス分野では、３次元を構成するモデル（一般には三角形パッチで構成されるポリゴンモデルが用いられる）表面に実世界から取得した撮影画像（テクスチャ画像）を貼り付けるテクスチャマッピングを行うことで高品位な画像を生成する。
【０００３】
よりリアルな物体を表現するためには、より高精細で大量のテクスチャ画像が必要であり、グラフィックス・システムはこれら大量の画像データを保持、転送、処理するためのメモリやバス・バンド幅、プロセッシングパワーが必要となってきた。いままで、必要なメモリ量やバス・バンド幅を減少させるために、さまざまな画像圧縮方法が試みられてきた。エントロピー符号化／ロスレス符号化、ＤＣＴ、ＪＰＥＧ、ＢＴＣ、ＣＣＣ、Ｓ３ＴＣなどが存在する。これらの方法にはそれぞれ下記のような短所が存在する。
【０００４】
（１）　エントロピー符号化は、予測可能性に基づくもので符号化する場合には最も出現頻度の高いシンボルに短い符号長を割り当てることでデータ量の符号化を実現している。ところが、特定の個所へのランダムアクセスに向かないという欠点が存在する。
【０００５】
１シンボルの解釈に一連の系列解釈が必要で、非効率な演算が必要であったりスループットが低減するといった問題が存在する。
【０００６】
また、圧縮率が固定でない点も問題で、リアルタイム・グラフィックスシステムなどでメモリ量に制約のある場合など圧縮率が不定なこれらの手法は扱うことができなかった。
【０００７】
（２）　離散コサイン変換Ｄｉｓｃｒｅｔｅ　Ｃｏｓｉｎｅ　Ｔｒａｎｓｆｏｒｍ（ＤＣＴ）やＪＰＥＧ等の符号化方法は画質を制御して符号化することが可能である。
【０００８】
これらの方法は画像情報を直交した周波数成分に分解するため、視覚的に影響の少ない部分、例えば低周波数成分のみを個別にカットすることで、画質を保持しながら圧縮率をあげることが可能である。
【０００９】
しかし、圧縮率をかせぐ必要性から扱える処理単位が８×８ピクセルや１６×１６ピクセルといった大きな画像ブロックに限定されてしまう。
【００１０】
非常に小さな画像エリアや１ピクセル単位のランダムアクセスであっても、１ブロック分のピクセル情報を扱う必要があるため、バス幅、計算負荷ともに高くなる。さらに、符号化データ量が不定なためのメモリ配置の問題や、高速な処理演算器か専用ハードウェアが必要なうえバッファ用メモリも必要といった問題もある。また、圧縮率をあげることでエッジが揺らいだり色調が変わる等、単純なポストフィルタリング処理では修復できない画像劣化が発生する問題があった。
【００１１】
（３）　Ｂｌｏｃｋ　ｔｒｕｎｃａｔｉｏｎ　ｃｏｄｉｎｇ（ＢＴＣ）やＣｏｌｏｒ　Ｃｅｌｌ　ｃｏｍｐｒｅｓｓｉｏｎ（ＣＣＣ）と呼ばれる手法では、４×４ピクセル画像ブロックを代表色２色と１ビットに量子化した１６ｂｉｔピクセル情報（どちらの代表色で表現するかで２パターン）で符号化したものである。復号化は、前記２代表色を符号化された１６ｂｉｔ情報の各ビットから２代表色をルックアップテーブルで選択することによって行う。
【００１２】
これらＢＴＣ／ＣＣＣは２段階の色再現性しかないため、画質が落ちる原因にもなっている。特に２代表色を８ｂｉｔのカラーインデックスで表現するため、カラールックアップテーブルを別途転送する必要があり、情報転送量が増加する問題があった。ピクセル毎に３ｂｉｔ情報を割り当てるＣＣＣ方法も存在するが、メモリの配置にオーバーヘッドが発生する問題があった。さらに、代表色を透過キーに割り当てて表示させた場合、画質に大きな劣化が発生する問題があった。
【００１３】
（４）　ピクセル毎の量子化ビットを２ビットにすることで画質を向上する方法もある。Ｓ３ＴＣ（米国特許５９５６４３１）方法は、代表色２色とその代表色間に定義される２色の計４代表色を設定し、ピクセル毎に２ｂｉｔでこれらの代表色を割当ることで、画像諧調表現の向上をおこなっている。
【００１４】
（５）　ＢＴＣ方法では、ピクセル毎に２ビットを４代表色（”Ｊ．Ｄ．Ｋｉｍ，ｅｔ．ａｌ，”Ｐｒｏｇｒｅｓｓｉｖｅ　Ｉｍａｇｉｎｇ　ｏｎ　ｔｈｅ　Ｉｎｔｅｒｎｅｔ　ｖｉａ　ＷＷＷ　Ｂｒｏｗｓｅｒ　ｕｓｉｎｇ　Ａｄａｐｔｉｖｅ　Ｂｌｏｃｋ　Ｔｒｕｎｃａｔｉｏｎ　Ｃｏｄｉｎｇ”，Ｍｕｌｔｉｍｅｄｉａ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｎｅｔｗｏｒｋｉｎｇ　１９９６，　１９９６）や、３代表色（”Ｙ．Ａ．Ａｌａｓｋａ　ａｎｄ　Ｄ．Ａ．Ｌｅｅ，”Ｔｈｒｅｅ　Ｌｅｖｅｌ　Ｂｌｏｃｋ　Ｔｒｕｎｃａｔｉｏｎ　Ｃｏｄｉｎｇ”，　Ｐｒｏｃ．　１９９０　ＩＥＥＥ　Ｓｏｕｔｈｅａｓｔｃｏｎ，　Ｖｏｌ．２，　ＩＥＥＥ　Ｐｒｅｓｓ，　Ｐｉｓｃａｔａｗａｙ，　Ｎ．Ｊ．，　ｐｐ．　４２０−４２３，　１９９０）にして画質を向上させる手法もある。
【００１５】
代表色を増やすことで符号化画像のデータ量が増える一方で、さらに透過情報といった付加的情報を埋め込もうとすると符号化時のデータ量が増加する問題がある。
【００１６】
以上述べたように、ブロック単位の画像符号化法の中には、画質の向上と付加情報の付与を両立させるような画像符号化フォーマット及び符号化手法は存在しない。
【００１７】
【特許文献１】
米国特許　５，９５６，４３１　”ＳＹＳＴＥＭ　ＡＮＤ　ＭＥＴＨＯＤ　ＦＯＲ　ＦＩＸＥＤ−ＲＡＴＥ　ＢＬＯＣＫ−ＢＡＳＥＤ　ＩＭＡＧＥＣＯＭＰＲＥＳＳＩＯＮ　ＷＩＴＨ　ＩＮＦＥＲＲＥＤ　ＰＩＸＥＬ　ＶＡＬＵＥＳ”
【００１８】
【非特許文献１】
Ｇ．Ｃａｍｐｂｅｌｌ　ｅｔ．ａｌ，　”Ｔｗｏ　ｂｉｔ／ｐｉｘｅｌ　ｆｕｌｌ　Ｃｏｌｏｒ　Ｅｎｃｏｄｉｎｇ”，　Ｓｉｇｇｒａｐｈ８６’　ｐｐ．２１５−２２３
【００１９】
【非特許文献１】
Ｊ．Ｄ．Ｋｉｍ，ｅｔ．ａｌ，　”Ｐｒｏｇｒｅｓｓｉｖｅ　Ｉｍａｇｉｎｇ　ｏｎ　ｔｈｅ　Ｉｎｔｅｒｎｅｔ　ｖｉａ　ＷＷＷ　Ｂｒｏｗｓｅｒ　ｕｓｉｎｇ　Ａｄａｐｔｉｖｅ　Ｂｌｏｃｋ　Ｔｒｕｎｃａｔｉｏｎ　Ｃｏｄｉｎｇ”，Ｍｕｌｔｉｍｅｄｉａ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｎｅｔｗｏｒｋｉｎｇ　１９９６，　１９９６
【００２０】
【非特許文献２】
Ｙ．Ａ．Ａｌａｓｋａ　ａｎｄ　Ｄ．Ａ．Ｌｅｅ，　”Ｔｈｒｅｅ　Ｌｅｖｅｌ　Ｂｌｏｃｋ　Ｔｒｕｎｃａｔｉｏｎ　Ｃｏｄｉｎｇ”，　Ｐｒｏｃ．　１９９０　ＩＥＥＥ　Ｓｏｕｔｈｅａｓｔｃｏｎ，　Ｖｏｌ．２，　ＩＥＥＥ　Ｐｒｅｓｓ，　Ｐｉｓｃａｔａｗａｙ，　Ｎ．Ｊ．，　ｐｐ．　４２０−４２３，
１９９０
【００２１】
【発明が解決しようとする課題】
上述したように従来のブロック単位の画像符号化手法は、圧縮率の向上が目的でピクセル毎の属性情報を含めた符号化は考慮されていない。そのため、画質と圧縮率を保持した状態で付加情報の付与が可能な効率的画像フォーマットと符号化法が求められている。
【００２２】
そこで、上記目的を達成するために、本発明を提供する。
【００２３】
【課題を解決するための手段】
請求項１の発明は、画像情報を特定の画像ブロックに分割するブロック分割部と、前記分割した各画像ブロック単位において少なくとも２つ以上の代表色を求める代表色算出部と、前記求めた代表色から他の２つ以上の代表色の補間で表現できる代表色を補間代表色として決定すると共に、その補間を行うための補間係数を計算する補間代表色決定部と、前記各画像ブロックを構成する各ピクセルを、前記求めた代表色、または、前記求めた補間代表色で表現するかを決定して符号化して符号化画像を求めるピクセル情報符号化部と、前記求めた代表色、前記求めた補間係数及び前記求めた符号化画像とを組み合わせ、ブロック単位の符号化画像である符号化ブロックを生成する符号化ブロック生成部と、前記生成した符号化ブロックを連結して最終的な符号化画像を構成するブロック連結部と、を有することを特徴とする画像符号化装置である。
【００２４】
請求項２の発明は、画像情報を特定の画像ブロックに分割するブロック分割部と、前記分割した各画像ブロック単位において少なくとも２つ以上の代表色を求める代表色算出部と、前記求めた代表色から他の２つ以上の代表色の補間で表現できる代表色を補間代表色として決定し、この補間代表色の数に応じた符号化フォーマットを決定すると共に、その補間を行うための補間係数を計算する補間代表色決定部と、前記各画像ブロックを構成する各ピクセルを、前記求めた代表色、または、前記求めた補間代表色のいずれで表現するかを決定して符号化して符号化画像を求めるピクセル情報符号化部と、前記求めた代表色、前記求めた補間係数及び前記求めた符号化画像とを、前記決定した符号化フォーマットに応じて配置することでブロック単位の符号化画像を生成する符号化ブロック生成部と、前記決定した各ブロック毎の符号化フォーマット情報を格納したヘッダ情報を生成するヘッダ情報生成部と、前記生成した符号化ブロック及び前記生成したヘッダ情報を連結して最終的な符号化画像を構成するブロック連結部と、を有することを特徴とする画像符号化装置である。
【００２５】
請求項３の発明は、画像情報を特定の符号化された画像ブロックに分割するブロック分割部と、前記分割された各符号化された画像ブロック単位に少なくとも２つ以上の代表色、補間代表色を算出する補間係数及びピクセル情報を符号化した符号化画像を取り出す符号化ブロック分解部と、前記求めた代表色及び補間係数から補間代表色を算出する補間代表色算出部と、前記求めた補間代表色、前記代表色及び前記符号化画像とから、ピクセル単位にカラー情報を復号してブロック毎の復号化画像を求めるピクセル情報復号化部と、前記求めたブロック単位の復号化画像を連結して最終的な復号化画像を構成するブロック連結部と、を有することを特徴とする画像復号化装置である。
【００２６】
請求項４の発明は、画像情報をヘッダ情報と符号化された画像ブロックに分割するブロック分割部と、前記ヘッダ情報から前記分割された各画像ブロック単位に符号化フォーマットを判定するフォーマット判定部と、前記分割された各画像ブロック単位に少なくとも２つ以上の代表色、補間代表色を算出するための補間係数及びピクセル情報を符号化した符号化画像を取り出す符号化ブロック分解部と、前記求めた代表色及び補間係数から補間代表色を前記判定した符号化フォーマットに従った数だけ算出する補間代表色算出部と、前記求めた補間代表色、前記代表色及び前記符号化画像とから、ピクセル単位にカラー情報を復号してブロック毎の復号化画像を求めるピクセル情報復号化部と、前記求めたブロック単位の復号化画像を連結して最終的な復号化画像を構成するブロック連結部と、を有することを特徴とする画像復号化装置である。
【００２７】
請求項５の発明は、画像情報を特定の画像ブロックに分割するブロック分割ステップと、前記分割した各画像ブロック単位において少なくとも２つ以上の代表色を求める代表色算出ステップと、前記求めた代表色から他の２つ以上の代表色の補間で表現できる代表色を補間代表色として決定すると共に、その補間を行うための補間係数を計算する補間代表色決定ステップと、前記各画像ブロックを構成する各ピクセルを、前記求めた代表色、または、前記求めた補間代表色で表現するかを決定して符号化して符号化画像を求めるピクセル情報符号化ステップと、前記求めた代表色、前記求めた補間係数及び前記求めた符号化画像とを組み合わせ、ブロック単位の符号化画像である符号化ブロックを生成する符号化ブロック生成ステップと、前記生成した符号化ブロックを連結して最終的な符号化画像を構成するブロック連結ステップと、を有することを特徴とする画像符号化方法である。
【００２８】
請求項６の発明は、画像情報を特定の画像ブロックに分割するブロック分割ステップと、前記分割した各画像ブロック単位において少なくとも２つ以上の代表色を求める代表色算出ステップと、前記求めた代表色から他の２つ以上の代表色の補間で表現できる代表色を補間代表色として決定し、この補間代表色の数に応じた符号化フォーマットを決定すると共に、その補間を行うための補間係数を計算する補間代表色決定ステップと、前記各画像ブロックを構成する各ピクセルを、前記求めた代表色、または、前記求めた補間代表色のいずれで表現するかを決定して符号化して符号化画像を求めるピクセル情報符号化ステップと、前記求めた代表色、前記求めた補間係数及び前記求めた符号化画像とを、前記決定した符号化フォーマットに応じて配置することでブロック単位の符号化画像を生成する符号化ブロック生成ステップと、前記決定した各ブロック毎の符号化フォーマット情報を格納したヘッダ情報を生成するヘッダ情報生成ステップと、前記生成した符号化ブロック及び前記生成したヘッダ情報を連結して最終的な符号化画像を構成するブロック連結ステップと、を有することを特徴とする画像符号化方法である。
【００２９】
請求項７の発明は、画像情報を特定の符号化された画像ブロックに分割するブロック分割ステップと、前記分割された各符号化された画像ブロック単位に少なくとも２つ以上の代表色、補間代表色を算出する補間係数及びピクセル情報を符号化した符号化画像を取り出す符号化ブロック分解ステップと、前記求めた代表色及び補間係数から補間代表色を算出する補間代表色算出ステップと、前記求めた補間代表色、前記代表色及び前記符号化画像とから、ピクセル単位にカラー情報を復号してブロック毎の復号化画像を求めるピクセル情報復号化ステップと、前記求めたブロック単位の復号化画像を連結して最終的な復号化画像を構成するブロック連結ステップと、を有することを特徴とする画像復号化方法である。
【００３０】
請求項８の発明は、画像情報をヘッダ情報と符号化された画像ブロックに分割するブロック分割ステップと、前記ヘッダ情報から前記分割された各画像ブロック単位に符号化フォーマットを判定するフォーマット判定ステップと、前記分割された各画像ブロック単位に少なくとも２つ以上の代表色、補間代表色を算出するための補間係数及びピクセル情報を符号化した符号化画像を取り出す符号化ブロック分解ステップと、前記求めた代表色及び補間係数から補間代表色を前記判定した符号化フォーマットに従った数だけ算出する補間代表色算出ステップと、前記求めた補間代表色、前記代表色及び前記符号化画像とから、ピクセル単位にカラー情報を復号してブロック毎の復号化画像を求めるピクセル情報復号化ステップと、前記求めたブロック単位の復号化画像を連結して最終的な復号化画像を構成するブロック連結ステップと、を有することを特徴とする画像復号化方法である。
【００３１】
【発明の実施の形態】
（実施形態１）
実施形態１は、下記の通りである。
【００３２】
少なくとも２つ以上の代表色、前記代表色を補間することで新たな代表色を定義するための少なくとも１つ以上の補間係数及び前記代表色、あるいは前記補間係数に基づき求めた補間代表色のいずれかを各ピクセルのカラー情報として選択するためのインデックス情報で画像ブロックが構成される
ことを特徴とするブロック単位の画像符号化方法である。
【００３３】
（実施形態２）
実施形態２は、下記の通りである。
【００３４】
画像情報を特定ブロックに分割するブロック分割手段と、
前記ブロック分割手段で分割された各画像ブロック単位に少なくとも２つ以上の代表色を求めるための代表色算出手段と、
前記代表色算出手段で求めた代表色から他の２つ以上の代表色の補間で表現できるものを決定し、補間係数を計算するための補間代表色決定手段と、
ブロックを構成する各ピクセルを前記代表色算出手段で求めた代表色、あるいは前記補間代表色決定手段で求めた補間代表色で表現するかを決定し符号化するためのピクセル情報符号化手段と、
前記代表色算出手段で求めた代表色と前記補間代表色決定手段で求めた補間係数及び前記ピクセル情報符号化手段で求めた符号化画像とを組み合わせ、ブロック単位の符号化画像を生成するための符号化ブロック生成手段と、
前記符号化ブロック生成手段で生成した符号化ブロックを連結し、最終的に符号化した画像を構成するためのブロック連結手段と、
を有する
ことを特徴とするブロック単位の画像符号化装置及び方法である。
【００３５】
（実施形態３）
実施形態３は、下記の通りである。
【００３６】
画像情報を特定ブロックに分割するブロック分割手段と、
前記ブロック分割手段で分割された各画像ブロック単位に少なくとも２つ以上の代表色を求めるための代表色算出手段と、
前記代表色算出手段で求めた代表色から他の２つ以上の代表色の補間で表現できるものを決定し、補間できる代表色の数に応じた符号化フォーマットを決定し、補間係数を計算するための補間代表色決定手段と、
ブロックを構成する各ピクセルを前記代表色算出手段で求めた代表色、あるいは前記補間代表色決定手段で求めた補間代表色のいずれで表現するかを決定し符号化するためのピクセル情報符号化手段と、
前記代表色算出手段で求めた代表色と前記補間代表色決定手段で求めた補間係数及び前記ピクセル情報符号化手段で求めた符号化画像とを前記補間代表色決定手段で決定した符号化フォーマットに応じて配置することでブロック単位の符号化画像を生成するための符号化ブロック生成手段と、
前記補間代表色決定手段で決定された各ブロック毎の符号化フォーマット情報を格納したヘッダ情報を生成するためのヘッダ情報生成手段と、
前記符号化ブロック生成手段で生成した符号化ブロック及び前記ヘッダ情報生成手段で生成したヘッダ情報を連結し、最終的に符号化した画像を構成するためのブロック連結手段と、
を有する
ことを特徴とするブロック単位の画像符号化装置及び方法である。
【００３７】
（実施形態４）
実施形態４は、下記の通りである。
【００３８】
前記ヘッダ情報生成手段は、
前記補間代表色決定手段で決定した各ブロック毎の符号化フォーマットの識別情報を保存しておくためのテーブル情報をヘッダ情報として生成する
ことを特徴とする実施形態３に記載のブロック単位の画像符号化装置及び方法である。
【００３９】
（実施形態５）
実施形態５は、下記の通りである。
【００４０】
前記補間代表色決定手段は、
前記ブロック分割手段で分割したブロックを構成するピクセル・カラーの分布特性に応じて符号化符号フォーマットを決定する
ことを特徴とする実施形態３及び４に記載のブロック単位の画像符号化装置及び方法である。
【００４１】
（実施形態６）
実施形態６は、下記の通りである。
【００４２】
前記代表色算出手段は、
画像全体で支配的なカラー情報を代表色に含めて生成する
ことを特徴とする、前記実施形態２から５に記載のブロック単位の画像符号化装置及び方法である。
【００４３】
（実施形態７）
実施形態７は、下記の通りである。すなわち、２代表色を結ぶ線分から他の代表色までの距離で補間代表色、補間係数を決定である。
【００４４】
前記補間代表色算出手段は、
前記代表色算出手段で求めた代表色の中で、特定の代表色と前記代表色を含まない異なる２つの代表色を結ぶ直線までの色空間上の距離に基づき、補間代表色を決定し、前記２代表色間の補間係数をそれぞれ算出する
ことを特徴とする実施形態２から６に記載のブロック単位の画像符号化装置及び方法である。
【００４５】
（実施形態８）
実施形態８は、下記の通りである。すなわち、３代表色で構成される平面までの距離で補間代表色、補間係数を決定である。
【００４６】
前記補間代表色算出手段は、
前記代表色算出手段で求めた代表色の中で、特定の代表色と前記代表色を含まない異なる３つの代表色で定義される色空間内平面までの距離に基づき、補間代表色を決定し、前記３代表色間の補間係数をそれぞれ算出する
ことを特徴とする実施形態２から６に記載のブロック単位の画像符号化装置及び方法である。
【００４７】
（実施形態９）
実施形態９は、下記の通りである。
【００４８】
画像情報を特定符号化ブロック画像に分割するブロック分割手段と、
前記ブロック分割手段で分割された各画像ブロック単位に少なくとも２つ以上の代表色、補間代表色を算出するための補間係数及びピクセル情報を符号化した符号化画像を取り出すための符号化ブロック分解手段と、
前記ブロック分解手段で求めた代表色及び補間係数から補間代表色を算出するための補間代表色算出手段と、
前記補間代表色算出手段で求めた補間代表色と、前記代表色及び符号化画像とから、ピクセル単位にカラー情報を復号するためのピクセル情報復号化手段と、
前記ピクセル情報復号化手段で求めたブロック単位の復号化画像を連結し、最終的に復号化した画像を構成するためのブロック連結手段と、
を有する
ことを特徴とするブロック単位の画像復号化装置及び方法である。
【００４９】
（実施形態１０）
実施形態１０は、下記の通りである。
【００５０】
画像情報をヘッダ情報と符号化ブロック画像に分割するブロック分割手段と、
前記ヘッダ情報から前記ブロック分割手段で分割された各画像ブロック単位に符号化符号化フォーマットを判定するためのフォーマット判定手段と、
前記ブロック分割手段で分割された各画像ブロック単位に少なくとも２つ以上の代表色、補間代表色を算出するための補間係数及びピクセル情報を符号化した符号化画像を取り出すための符号化ブロック分解手段と、
前記ブロック分解手段で求めた代表色及び補間係数から補間代表色を前記フォーマット判定手段でも判定したフォーマットに従った数だけ算出するための補間代表色算出手段と、
前記補間代表色算出手段で求めた補間代表色と、前記代表色及び符号化画像とから、ピクセル単位にカラー情報を復号するためのピクセル情報復号化手段と、
前記ピクセル情報復号化手段で求めたブロック単位の復号化画像を連結し、最終的に復号化した画像を構成するためのブロック連結手段と、
を有する
ことを特徴とするブロック単位の画像復号化装置及び方法である。
【００５１】
【実施例】
以下、本発明の実施例の構成を、図面を参照しながら説明する。
【００５２】
（第１の実施例）
（１）ブロック単位の画像符号化システムの構成
図１は、本発明のブロック単位の画像符号化システム（以下、本符号化システムという）の第１の実施例に関わる構成図である。
【００５３】
本符号化システムは、与えられた画像に対し特定ピクセルサイズのブロック画像に分割するためのブロック分割手段１０１と、ブロックを代表する代表色を少なくとも１つ以上算出するための代表色算出手段１０２と、前記代表色算出手段１０２で算出した代表色の中で、符号化フォーマットに基づき少なくとも２つ以上の代表色の補間で表現できるものを決定すると同時に前記代表色間の補間係数を決定するための補間代表色決定手段１０３と、前記代表色算出手段１０２で求めた代表色及び前記補間代表色決定手段で求めた補間係数に従い代表色間の補間で求められた補間代表色の中から、ブロックを構成する各ピクセルの色を代表させるものを決定し、そのインデックス情報に符号化するためのピクセル情報符号化手段１０４と、前記代表色算出手段１０２で求めた代表色、前記補間代表色決定手段１０３で求めた補間係数及び前記ピクセル情報符号化手段１０４で求めた符号化ピクセル情報とを符号化フォーマットに従って構成するための符号化ブロック生成手段１０５と、前記符号化ブロック生成手段１０５で生成した符号化ブロックを連結し最終的な符号化画像を生成するためのブロック連結手段１０６、とで構成される。
【００５４】
（２）本符号化システム全体の処理の流れ
本符号化システム全体の処理の流れを図２に示す。この図を参考に符号化処理の手順を説明する。
【００５５】
（２−１）ブロックの分割
ブロックの分割２０２では、与えられた符号化画像を特定ブロックサイズの画像ブロックに分割を行う。ここでは４×４ピクセル毎に画像をブロック分解することを考える。画像のピクセル・サイズが２５６×２５６である場合、６４×６４個の画像ブロックが生成されることになる。
【００５６】
代表色の算出２０３では、ブロックを構成する１６ピクセルのカラー情報を４色のカラー情報で代表化させることを考える。代表化カラー情報を算出するにはクラスタリング法を用いる。ここでは４代表色へのクラスタリング手順について説明を行う。
【００５７】
（２−２）代表色の算出
代表色を算出するための処理フローを図３に示す。
【００５８】
この処理の役割は、ブロック内の全ピクセルの色分布を調べて、４つの代表色（Ｃ０，Ｃ１，Ｃ２，Ｃ３）を求めることである。支配色優先３０２では、支配色（ここでは符号化対象の画像内にもっとも多く使用されている色とする）を優先的に代表色とするかどうかを決める。１色で塗りつぶされた背景の上に絵や文字が描かれているような画像の場合、支配色を優先させることによってエッジ部分の再現性を高めることができる。支配色を優先させる場合には、その背景色そのものを代表色Ｃ３とする（３０３）。初期設定（ｎ＝１，δ）３０７以降の処理では、３つまたは４つの代表色を算出するために、クラスタリング処理を実行する。クラスタを順次２分割していく際には、各クラスタの分散σ２を算出し、分散の大きいクラスタを優先的に２分割する（３０８）。分散σ２は、以下のように算出する。
【００５９】
【数１】
2004104621.tif 000003
初期セントロイドの決定３０９では、あるクラスタを２分割するために、２つの初期セントロイド（クラスタの中心）を決定する。セントロイドの決定は以下の手順で行なう（図４）。
【００６０】
１．クラスタの重心ｇを求める。
【００６１】
２．ｇから最も遠い要素をｄ０とする。
【００６２】
３．ｄ０から最も遠い要素をｄ１とする。
【００６３】
４．ｇとｄ０及びｇとｄ１のそれぞれの１：２の内分点をＣ０，Ｃ１とする。
【００６４】
但し、２要素間の距離には、ＲＧＢの３次元空間でユークリッド距離を用いる。３１２、３１３のループは、一般によく知られたクラスタリングアルゴリズムである　Ｋ−Ｍｅａｎｓ　法と同様の処理を行なっている。
【００６５】
以上の手順により、４つの代表色（Ｃ０，Ｃ１，Ｃ２，Ｃ３）を求めることができる。
【００６６】
（２−３）補間代表色の決定
補間代表色の決定２０４では、前記代表色の算出２０３で求めた４つの代表色の中から、ほかの代表色の補間によって表現できるものがあるかどうかを判定し、補間することが可能な場合、その代表色の選択と補間係数の決定を行う。
【００６７】
「補間」とは、色空間上の分布に基づいて、一の代表色（以下、補間代表色という）が他の代表色（以下、保存代表色という）によって表現することをいい、その補間をするための係数を補間係数という。
【００６８】
ここで、補間代表色の数に応じて４つの符号化フォーマットを定義する。補間で表現できる代表色が多いほど代表色として保持しておく保存代表色のデータサイズが少なくて済むため、その空いたデータ領域を透過率情報等のほかの属性情報に割り当てられることができるようになる。一方、補間で表現できる代表色を増やすほど画質自体は劣化するわけで、確保しておく画質と他の付加しておきた画像情報との関係で符号化フォーマットを選択するといった使い方が考えられる。以下に定義する各符号化フォーマットにおけるブロックに保存代表色の数、補間代表色の数、補間係数の数を示す。
【００６９】
符号化フォーマット０：
保存代表色数　４色、　補間代表色数　０色、　補間係数の数　０
符号化フォーマット１：
保存代表色数　３色、　補間代表色数　１色、　補間係数の数　１
符号化フォーマット２：
保存代表色数　３色、　補間代表色数　１色、　補間係数の数　１
符号化フォーマット３：
保存代表色数　２色、　補間代表色数　２色、　補間係数の数　２
符号化フォーマット１、２、３で符号化をする際、４色の代表色のうち１色または２色を補間する必要がある。
【００７０】
補間代表色を決定するための処理フローを図５から図７に示す。
【００７１】
まず、４つの代表色のうち、どのピクセルにも割り当てられていない、つまり復号の際に決して参照されることがない代表色を除去する（５０２，６０２，７０２）。除去した結果、残った代表色の数で補間が必要かどうかが判定される。
【００７２】
符号化フォーマット１あるいは２の場合、残された代表色が３色以下であった場合（５０２，５０４，５０５，６０３，６０４，６０５）、それぞれを代表色として登録する（５０６，５０７，５０８，６０６，６０７，６０８）ことで補間するべき代表色を決定する必要はないが、残された代表色が４色であった場合、補間するべき代表色を１つ決定する必要がある。また、符号化フォーマット３の場合、残された代表色が２色以下であった場合（７０３，７０４）、それぞれを代表色として登録し（７０６，７０７）、補間するべき代表色は決定する必要がない。但し、残された代表色が３色または４色であった場合（７０５）には、それぞれ１色あるいは２色を補間するべき代表色として決定する必要がある。
【００７３】
補間の対象（補間される代表色）を決定する際には、残された代表色の中に支配色が含まれているかどうかを判定する（５０９，６０９，７０８，７０９）。支配色が含まれている場合には、支配色のピクセルをそのままの色で再現した方がよいため、補間の対象には含めず、代表色として登録する（５１０，６１０，７１０，７１１）。支配色の代表色登録が終了し、残された代表色の中から補間するべき代表色を決定することになる。符号化フォーマット１の場合、残された代表色４つの中から１つの補間代表色を決定すればよい（５１１，５１２）、符号化フォーマット２の場合、残された代表色３つの中から１つの補間代表色を決定すればよい（６１１，６１２）、符号化フォーマット３の場合、残された代表色３つの中ら１つの補間代表色を決定する場合（７１２，７１３）と、残された代表色４つの中から２つの補間代表色を決定する場合（７１４，７１５）が存在する。
【００７４】
上記の代表色の組み合わせの中から、もっとも補間することで誤差の少ないものを選び、それを補間代表色として決定することになる。
【００７５】
補間の方法としては、代表色３つから１つの代表色を補間する場合、図８（ａ）に示すように２つの代表色Ｃ０，Ｃ１（ＲＧＢカラーを３次元座標にプロットしたもの）を結んだ直線に対して、もう１つの代表色から垂線を下ろして補間色を決定する。垂線の足が線分Ｃ０−Ｃ１上に存在すれば、”補間が可能である”と判断する、また、直線におろした垂線の長さから補間した場合の誤差（補間誤差ε）を求めることができる（６１３，７１６）。この誤差を最小とする補間代表色の組み合わせを決定し、そのときの直線上に降ろした垂線の足Ｃ２’　の線分Ｃ０−Ｃ１における内分比率を補間係数Ｒａｔｉｏとして求める（６１４，７１７）。
【００７６】
代表色４つから１つの代表色を補間する場合、図８（ｂ）に示すように３つの代表色Ｃ０，Ｃ１，Ｃ２（ＲＧＢカラーを３次元座標にプロットしたもの）で定義される平面に、もう１つの代表色から垂線を下ろして補間色を決定する。垂線の足がＣ０，Ｃ１，Ｃ２で囲まれる三角形内に存在すれば、”補間が可能である”と判断する、また、平面におろした垂線の長さから補間した場合の誤差（補間誤差ε）を求めることができる（５１３）。この誤差を最小とする補間代表色の組み合わせを決定し、そのときの垂線の足Ｃ３’を表現するベクトルＣ０−Ｃ１の内分比率を補間係数Ｒａｔｉｏ１、ベクトルＣ０−Ｃ２の内分比率を補間係数Ｒａｔｉｏ２として求める（５１４）。
【００７７】
代表色４つから２つの代表色を補間する場合、図８（ｃ）に示すように２つの代表色Ｃ０，Ｃ１（ＲＧＢカラーを３次元座標にプロットしたもの）を結んだ直線に対して、それぞれ２つの代表色から垂線を下ろして補間色を決定する。両者の垂線の足が線分Ｃ０Ｃ１上に存在すれば、”補間が可能である”と判断する、また、直線におろした垂線の長さを合計することで補間した場合の誤差（補間誤差ε）を求めることができる（７１６）。
【００７８】
この誤差が最小とする補間代表色の組み合わせを決定し、そのときの直線上に降ろした垂線の足Ｃ２’，Ｃ３’の線分Ｃ０−Ｃ１における内分比率を補間係数Ｒａｔｉｏ１，Ｒａｔｉｏ２として求める（７１７）。
【００７９】
（２−４）ピクセル情報の符号化
ピクセル情報の符号化２０５では、前記代表色の算出２０３で求めた代表色及び前記補間代表色の決定２０４で求めた補間係数から求められる補間代表色の中から、各ピクセルの色を代表させるものを決定し、そのインデックス情報から符号化を行うものである。
【００８０】
ここでは、代表色及び補間代表色あわせて４色のいずれかを選択すればよいのでインデックス情報としては２ｂｉｔあればよいことになる。このピクセル色の代表化では各ピクセル色と代表色、あるいは補間代表色との色空間上の距離を判定尺度にもっとも近い代表色を選ぶことにする。
【００８１】
（２−５）符号化ブロックの生成
符号化ブロックの生成２０６では、前記代表色の算出２０３で求めた代表色、前記補間代表色の決定２０４で求めた補間係数及び前記ピクセル情報の符号化２０５で求めた符号化されたピクセル情報とを前記符号化フォーマットに従ってレイアウトし、符号化ブロックを生成する。
【００８２】
代表色カラ−を１６ｂｉｔ、補間係数を４ｂｉｔ、つまり１６ステップの補間割合、各ピクセルの符号化ビットとして２ｂｉｔ（代表色、あるいは補間代表色のうちいずれかをあらわすインデックス情報）とし、符号化ブロック全体のデータサイズは９６ｂｉｔとすると、属性情報として付与できる空きデータサイズは以下のようになる。
【００８３】
符号化フォーマット０：　空きデータサイズ　０ｂｉｔ
符号化フォーマット１：　空きデータサイズ　８ｂｉｔ
符号化フォーマット２：　空きデータサイズ　１２ｂｉｔ
符号化フォーマット３：　空きデータサイズ　２４ｂｉｔ
各符号化フォーマットにおける代表色、補間係数及び符号化ピクセル情報のレイアウトを図９に示す。
【００８４】
これらの余ったデータ領域には各代表色毎の透過率情報を入れることができる。代表色あたりの透過率情報は、符号化フォーマット１の場合２ｂｉｔ，符号化フォーマット２の場合４ｂｉｔ、符号化フォーマット３の場合１２ｂｉｔ埋め込むことができる。また、符号化ブロックを２×２ピクセルで構成されるサブブロックに分けサブブロック単位に透過率を指定することもできる（１つの符号化ブロックに対し４つのサブブロックが定義されることになる）。この場合、サブブロックあたりの透過率情報は、符号化フォーマット１の場合２ｂｉｔ、符号化フォーマット２の場合３ｂｉｔ、符号化フォーマット３の場合６ｂｉｔ埋め込むことができる。
【００８５】
また、このフォーマットは固定したものである必要はなく、画質を優先したい場合代表色の色解像度を１６ｂｉｔから２４ｂｉｔに変更しても構わない。
【００８６】
（２−６）全ブロックの終了
全ブロックの終了２０７では、前記代表色の算出２０３から前記符号化ブロックの生成２０６までの一連の符号化処理が全ブロックにわたって終了したかどうかを判定する。
【００８７】
（２−７）ブロックの連結
ブロックの連結２０８では、前記符号化ブロックの生成２０６で生成した符号化されたブロック画像を連結し、符号化された画像の生成を行う。今回の場合、６４×６４ブロックが存在し、各符号化ブロックのデータサイズが９６ｂｉｔであることから、符号化画像全体で６４×６４×９６ｂｉｔ＝５０ＫＢｙｔｅのデータ量となる。
【００８８】
（２−８）まとめ
以上の処理の流れから画像をブロック単位に符号化することができる。
【００８９】
符号化フォーマットが異なっても符号化後のブロックデータサイズは一定なため、圧縮率等は固定である。元の画像が２５６×２５６ｐｉｘｅｌ　２４ｂｉｔＲＧＢカラー画像の場合、データ量は２５６×２５６×４＝２６２ＫＢｙｔｅであることから、圧縮率は５０／２６２＝０．１９程度となり、２５６×２５６ｐｉｘｅｌ　２４ｂｉｔ　ＲＧＢカラ−画像の場合、５０／１９７＝０．２５程度となる。
【００９０】
（３）ブロック単位の画像復号化システムの構成
図１０は、本発明のブロック単位の画像復号化システム（以下、本復号化システムという）の第１の実施例に関わる構成図である。
【００９１】
本復号化システムは、画像情報を特定符号化ブロック画像に分割するブロック分割手段１００１と、前記ブロック分割手段１００１で分割された各画像ブロック単位に少なくとも２つ以上の代表色、補間代表色を算出するための補間係数及びピクセル情報を符号化した符号化画像を取り出すための符号化ブロック分解手段１００２と、前記ブロック分解手段１００２で求めた代表色及び補間係数から補間代表色を算出するための補間代表色算出手段１００３と、前記補間代表色算出手段１００３で求めた補間代表色と、前記代表色及び符号化画像とから、ピクセル単位にカラ−情報を復号するためのピクセル情報復号化手段１００４と、前記ピクセル情報復号化手段１００４で求めたブロック単位の復号化画像を連結し、最終的に復号化した画像を構成するためのブロック連結手段１００５、とで構成される。
【００９２】
（４）本復号化システムにおける全体の処理の流れ
本復号化システムにおける全体の処理の流れは図１１のようになる。この図を参考に復号処理の説明を行う。
【００９３】
（４−１）ブロックの分割
ブロックの分割１１０２では、与えられた符号化画像を特定ブロックサイズの画像ブロックに分割を行う。ここでは符号化されたブロックサイズは９６ｂｉｔと固定であるため、９６ｂｉｔを単位として符号化画像をブロック分割することになる。
【００９４】
（４−２）符号化ブロックの分解
符号化ブロックの分解１１０３では、前記ブロックの分割１１０２で分割して求めたブロック単位に復号化に必要な構成要素への分解及び取り出しを行う。前記復号化に必要な構成要素は符号化時に設定した符号化フォーマットに基づいて代表色及び補間代表色を算出するための補間係数及びピクセル情報を符号化した符号化画像を取り出す。
【００９５】
（４−３）補間代表色の算出
補間代表色の算出１１０４では、前記符号化ブロックの分解１１０３で取り出した代表色及び補間係数から復号用代表色を求める。符号化時の符号化フォーマットに応じて以下のような計算で４つの復号用代表色Ｃｄ０〜Ｃｄ３を求める。各方法に応じて他の代表色の補間で求める復号用代表色の数が異なる。
【００９６】
符号化フォーマット０の場合：
Ｃｄ０＝Ｃ０，Ｃｄ１＝Ｃ１，Ｃｄ２　＝Ｃ２，Ｃｄ３＝Ｃ３
符号化フォーマット１の場合：
Ｃｄ０＝Ｃ０，
Ｃｄ１＝Ｃ１，
Ｃｄ２＝Ｃ２，
Ｃｄ３＝（Ｒａｔｉｏ１／１５）＊（Ｃ１−Ｃ０）＋（Ｒａｔｉｏ２／１５）＊（Ｃ２−Ｃ０）
符号化フォーマット２の場合：
Ｃｄ０＝Ｃ０，
Ｃｄ１＝Ｃ１，
Ｃｄ２＝Ｃ２，
Ｃｄ３＝Ｒａｔｉｏ／１５）＊Ｃ０＋（１−Ｒａｔｉｏ／１５）＊Ｃ１
符号化フォーマット３の場合：
Ｃｄ０＝Ｃ０，
Ｃｄ１＝Ｃ１，
Ｃｄ２＝（Ｒａｔｉｏ１／１５）＊Ｃ０＋（１−Ｒａｔｉｏ１／１５）＊Ｃ１，
Ｃｄ３＝（Ｒａｔｉｏ２／１５）＊Ｃ０＋（１−Ｒａｔｉｏ２／１５）＊Ｃ１
（４−４）ピクセル情報の復号化
ピクセル情報の復号化１１０５では、前記符号化ブロックの分解１１０３で取り出した符号化画像に含まれる各ピクセル毎のインデックス情報から、インデックスで指定される代表色、あるいは補間代表色をピクセルカラ−情報として復号する。２ｂｉｔのインデックス情報と復号用代表色との関連づけは以下のように行うことができる。
【００９７】
インデックス０　”００”は、復号用代表色Ｃｄ０になる
インデックス１　”０１”は、復号用代表色Ｃｄ１になる
インデックス２　”１０”は、復号用代表色Ｃｄ２になる
インデックス３　”１１”は、復号用代表色Ｃｄ３になる
（４−５）全ブロック終了
全ブロック終了１１０６では、上記符号化ブロックの分解１１０３からピクセル情報の復号化１１０５、にいたる処理が全ブロックに渡って処理を施したかを判定する。
【００９８】
（４−６）ブロックの連結
ブロックの連結１１０７では、前記ピクセル情報の復号化１１０５でピクセルカラ−情報を復号したブロック画像を元の連結状態を保持したまま結合することで最終的に復号画像を生成する。６４×６４ブロックの連結を行えば、２５６×２５６ピクセルの画像が生成されることになる。
【００９９】
（第２の実施例）
図１２は、本発明のブロック単位の画像符号化システム（以下、本符号化システムという）の第２の実施例に関わる構成図である。
【０１００】
（１）本符号化システムの構成
本符号化システムは、画像情報を特定ブロックに分割するブロック分割手段１２０１と、前記ブロック分割手段１２０１で分割された各画像ブロック単位に少なくとも２つ以上の代表色を求めるための代表色算出手段１２０２と、前記代表色算出手段１２０２で求めた代表色から他の２つ以上の代表色の補間で表現できるものを決定し、補間できる代表色の数に応じた符号化フォーマットを決定し、補間係数を計算するための補間代表色決定手段１２０３と、ブロックを構成する各ピクセルを前記代表色算出手段１２０２で求めた代表色、あるいは前記補間代表色決定手段１２０３で求めた補間代表色のいずれで表現するかを決定し符号化するためのピクセル情報符号化手段１２０４と、前記代表色算出手段１２０２で求めた代表色と前記補間代表色決定手段１２０３で求めた補間係数及び前記ピクセル情報符号化手段１２０４で求めた符号化画像とを前記補間代表色決定手段１２０３で決定した符号化フォーマットに応じて配置することでブロック単位の符号化画像を生成するための符号化ブロック生成手段１２０５と、前記補間代表色決定手段１２０３で決定された各ブロック毎の符号化フォーマット情報を格納したヘッダ情報を生成するためのヘッダ情報生成手段１２０７と、前記符号化ブロック生成手段１２０５で生成した符号化ブロック及び前記ヘッダ情報生成手段１２０７で生成したヘッダ情報を連結し、最終的に符号化した画像を構成するためのブロック連結手段１２０６、とで構成される。
【０１０１】
（２）本符号化システム全体の処理の流れ
本符号化システム全体の処理の流れを図１３に示す。
【０１０２】
ブロックの分割１３０２及び代表色の算出１３０３は、第１の実施例におけるブロックの分割２０２及び代表色の算出２０３と同様であるため説明を省略する。
【０１０３】
第１の実施例における符号化システムの処理フロ−との違いは、ブロック毎に補間代表色の決定１３０４で符号化フォーマットの決定、補間するべき代表色数の決定及びその符号化フォーマットに対応した補間係数等の情報を算出している点である。図１４は、補間代表色決定手段における符号化フォーマット決定の様子を説明するための図である。
【０１０４】
符号化フォーマットを選択する際のパラメ−タとして、画質の重要度（補間誤差の許容範囲）や透過度αの重要度等を用いる。例えば、テクスチャの端に近いブロックは画質よりも透過度を優先したいという要求があれば、符号化フォーマット０よりも符号化フォーマット３を選んだ方がよいということになる。
【０１０５】
補間の際に生じる誤差（補間誤差）は、第１の実施例の図５から図７で示した処理と同様にして算出する。符号化フォーマット３から順に補間誤差を算出し（１４０３）、あるしきい値以下でなければ、符号化フォーマット２，１，０へと状態を遷移させる（１４０６，１４１１，１４１６）。
【０１０６】
符号化フォーマット０以外のものは、画質優先かα値優先かを選択し、最終的なフォーマットを決定する（１４０５，１４１０，１４１５）。
【０１０７】
決定した符号化フォーマットに対応した補間代表色決定の処理フロ−は、第１の実施例における補間代表色の決定２０４で記述した処理フロ−と同じであるため、ここでは省略する。
【０１０８】
ピクセル情報の符号化１３０５は、第１の実施例におけるピクセル情報の符号化２０５と同様に、ピクセル毎に代表色へのインデックス情報を生成する。
【０１０９】
符号化ブロックの生成１３０６では、前記補間代表色の決定１３０４で決定した符号化フォーマットに従って代表色、補間係数、符号化ピクセル情報等をレイアウトして符号化ブロックを生成する。
【０１１０】
ヘッダ情報の追加１３０７は、各ブロック毎の符号化フォーマット種別をヘッダ情報に追加、登録するための手段である。ヘッダ情報におけるブロック単位のフォーマット識別テ−ブル情報の例を図１５に示す。
【０１１１】
ここでは、符号化方法を識別するファイル形式と、ブロックサイズとブロックの数等画像サイズ情報、そして、ブロック毎の符号化フォーマット及び画質優先フォーマットかα優先フォーマットかの区別が可能な識別子が埋め込まれている。
【０１１２】
全ブロック終了１３０８では、前記代表色の算出１３０３から前記ヘッダ情報の追加１３０７までの一連の符号化処理が全ブロックにわたって終了したかどうかの判定を行う。
【０１１３】
ブロックの連結１３０９では、前記符号化ブロックの生成１３０６で生成した符号化されたブロック画像を連結すると同時に、前記ヘッダ情報の追加１３０７で生成したヘッダ情報を追加して最終的に符号化された画像の生成を行う。第１の実施例での符号化システムと同様、符号化後のデータサイズは変わらず、６４×６４ブロックにおいて各ブロックのデータサイズが９６ｂｉｔであることから、符号化画像全体で６４×６４×９６ｂｉｔ　＝　５０ＫＢｙｔｅのデータ量となる。
【０１１４】
第１の実施例との大きな違いは、ブロック毎に符号化フォーマットを変えることができる点である。
【０１１５】
ブロック単位に画質優先、あるいは透過率等の属性情報優先、等の切替が可能になったり、画質を一定水準に保持した状態で最適な属性情報の付与が可能となる。
【０１１６】
（３）ブロック単位の画像復号化システムの構成
図１６は、本発明のブロック単位の画像復号化システム（以下、本復号化システムという）の第２の実施例に関わる構成図である。
【０１１７】
本復号化システムは、画像情報をヘッダ情報と符号化ブロック画像に分割するブロック分割手段１６０１と、前記ヘッダ情報から前記ブロック分割手段１６０１で分割された各画像ブロック単位に符号化符号化フォーマットを判定するためのフォーマット判定手段１６０２と、前記ブロック分割手段１６０１で分割された各画像ブロック単位に少なくとも２つ以上の代表色、補間代表色を算出するための補間係数及びピクセル情報を符号化した符号化画像を取り出すための符号化ブロック分解手段１６０３と、、前記符号化ブロック分解手段１６０３で求めた代表色及び補間係数から補間代表色を前記フォーマット判定手段１６０３で判定したフォーマットに従った数だけ算出するための補間代表色算出手段１６０４と、前記補間代表色算出手段１６０４で求めた補間代表色と、前記代表色及び符号化画像とから、ピクセル単位にカラ−情報を復号するためのピクセル情報復号化手段１６０５と、前記ピクセル情報復号化手段１６０５で求めたブロック単位の復号化画像を連結し、最終的に復号化した画像を構成するためのブロック連結手段１６０６、とで構成される。
【０１１８】
（４）本復号化システム全体の処理の流れ
本復号化システム全体の処理の流れを図１７に示す。この図を参考に説明を行う。
【０１１９】
ブロックの分割１７０２では、ヘッダ情報と符号化画像を分割すると同時に符号化画像をブロックサイズである９６ｂｉｔ単位にブロック分割を行う。
【０１２０】
第１の実施例における復号化システムとの違いは、フォーマットの判定１７０３で各ブロックの符号化フォーマット判定を行っている点である。ここでは、前記ブロックの分割で取得したヘッダ情報に保存されたブロック毎の符号化フォーマット識別テ−ブル（図１５）を参照して、該当するブロックのフォーマットを判定する。
【０１２１】
符号化ブロックの分解１７０４は、前記フォーマットの判定１７０３で判定した符号化フォーマットに従って代表色、補間係数及び符号化ピクセル情報の分解、取り出しを行う。
【０１２２】
補間代表色の算出１７０５は、前記フォーマットの判定１７０３で求めた符号化フォーマットに応じて復号代表色を算出する。各符号化フォーマットに応じた復号代表色の算出方法は第１の実施例における補間代表色の算出１１０４に記載の方法と同様である。
【０１２３】
ピクセル情報の復号化１７０６は、第１の実施例におけるピクセル情報の復号化１１０５と同様であるため、ここでは省略する。
【０１２４】
全ブロック終了１７０７では、前記フォーマットの判定１７０３から前記ピクセル情報の復号化１７０６までの一連の復号化処理が全ブロックにわたって終了したかを判定する。
【０１２５】
ブロックの連結１７０９では、前記ピクセル情報の復号化１７０６でピクセルカラ−情報を復号したブロック画像を元の連結状態を保持したまま結合することで最終的に復号画像を生成する。６４×６４ブロックの連結を行えば、２５６×２５６ピクセルの画像が生成されることになる。
【０１２６】
第１の実施例との違いは、ブロック毎に異なる符号化フォーマットで符号化された画像であってもヘッダ情報を参照することで、復号することが可能な点である。
【０１２７】
【発明の効果】
以上説明した様に本発明によれば、画質と圧縮率を保持した状態で付加情報の付与が可能な効率的画像フォーマットで画像の符号化復号化が可能となる。また、ブロック領域単位に異なる符号化フォーマットが適用できるため用途に応じた柔軟で効率的な画像圧縮が可能となる。
【図面の簡単な説明】
【図１】本発明の画像符号化システムの第１の実施例の構成図である。
【図２】画像符号化システムの第１の実施例の処理フロ−を説明するための図である。
【図３】代表色の算出における具体的な処理フロ−を説明するための図である。
【図４】代表色の算出におけるクラスタリング処理の様子を説明するための図である。
【図５】補間代表色の決定において符号化フォーマット１における処理フロ−図である。
【図６】補間代表色の決定において符号化フォーマット２における処理フロ−図である。
【図７】補間代表色の決定において符号化フォーマット３における処理フロ−図である。
【図８】代表色の数に応じた補間代表色と補間係数決定の様子を説明するための図である。
【図９】各符号化フォーマットのレイアウトを説明するための図である。
【図１０】本発明の画像復号化システムの第１の実施例の構成図である。
【図１１】画像復号化システムの第１の実施例の処理フロ−を説明するための図である。
【図１２】本発明の画像符号化システムの第２の実施例の構成図である。
【図１３】画像符号化システムの第２の実施例の処理フロ−を説明するための図である。
【図１４】補間代表色決定手段における符号化フォーマット決定の様子を説明するための図である。
【図１５】ヘッダ情報に登録されるデータを説明するための図である。
【図１６】本発明の画像復号化システムの第２の実施例の構成図である。
【図１７】画像復号化システムの第２の実施例の処理フロ−を説明するための図である。
【符号の説明】
１０１　　ブロック分割手段
１０２　　代表色算出手段
１０３　　補間代表色決定手段
１０４　　ピクセル情報符号化手段
１０５　　符号化ブロック生成手段
１０６　　ブロック連結手段
【図１】
2004104621.tif 000004
【図２】
2004104621.tif 000005
【図３】
2004104621.tif 000006
【図４】
2004104621.tif 000007
【図５】
2004104621.tif 000008
【図６】
2004104621.tif 000009
【図７】
2004104621.tif 000010
【図８】
2004104621.tif 000011
【図９】
2004104621.tif 000012
【図１０】
2004104621.tif 000013
【図１１】
2004104621.tif 000014
【図１２】
2004104621.tif 000015
【図１３】
2004104621.tif 000016
【図１４】
2004104621.tif 000017
【図１５】
2004104621.tif 000018
【図１６】
2004104621.tif 000019
【図１７】
2004104621.tif 000020