(57)【要約】【課題】画素ブロック単位で各画素にそれぞれ色を割当てて順次に画像を符号化する場合に、画像データを効率的に符号化する。【解決手段】実施形態の画像符号化装置は、生成部と、更新部と、割当部と、符号化部と、を有する。生成部は、符号化済みの画素に割り当てられた色に基づいて、対象画素に１色以上の仮の代表色、及び仮の代表色を特定するための仮のインデックスを生成する。更新部は、対象画素及び仮の代表色に基づいて、画素ブロック内の各画素の表現に用いる１色以上の決定された代表色、及び決定された代表色を個別に特定するインデックスを生成して、仮の代表色及び仮のインデックスを、決定された代表色及びインデックスに更新する更新情報を生成する。割当部は、符号化対象となる画素ブロック内の各画素それぞれにインデックスのいずれかを割当てた割当て情報を生成する。符号化部は、更新情報及び割当て情報を符号化する。【選択図】図１
2015023506.tif 000002
【特許請求の範囲】
【請求項１】
画素ブロックに含まれる各画素に色を割当てて画像を符号化する画像符号化装置であって、
符号化済みの画素に割り当てられた色に基づいて、対象画素に１色以上の仮の代表色、及び前記仮の代表色を特定するための仮のインデックスを生成する生成部と、
前記対象画素及び前記仮の代表色に基づいて、画素ブロック内の各画素の表現に用いる１色以上の決定された代表色、及び前記決定された代表色を個別に特定するインデックスを生成して、前記仮の代表色及び前記仮のインデックスを、前記決定された代表色及び前記インデックスに更新する更新情報を生成する更新部と、
符号化対象となる画素ブロック内の各画素それぞれに前記インデックスのいずれかを割当てた割当て情報を生成する割当部と、
前記更新情報及び前記割当て情報を符号化する符号化部と、
を有する画像符号化装置。
【請求項２】
前記更新部は、
符号化対象となる画素ブロック内の画素の画素値と前記仮の代表色との距離に基づいて、符号化対象となる画素ブロック内の各画素に割当てられない前記仮の代表色を特定し、前記決定された代表色及び前記インデックスを生成する
請求項１に記載の画像符号化装置。
【請求項３】
前記割当部は、
前記決定された代表色が重複する場合、重複する前記決定された代表色を特定する複数の前記インデックスのうち、いずれか１つを割当てた割当て情報を生成する
請求項１または２に記載の画像符号化装置。
【請求項４】
前記符号化部は、
符号化対象画素位置と、前記仮の代表色の決定に用いる前記符号化済みの画素との相対的な位置関係に基づいて、前記インデックスの符号長を切り替える
請求項２または３に記載の画像符号化装置。
【請求項５】
前記更新部は、
前記仮の代表色の重複の有無、及び前記仮の代表色間の類似度の少なくともいずれかに基づいて前記更新情報を生成する
請求項１に記載の画像符号化装置。
【請求項６】
画素ブロックに含まれる各画素に色を割当てられた画像の符号化データを復号する画像復号化装置であって、
復号済みの画素の色に基づいて、復号対象となる画素ブロック内の各画素の表現に用いる１色以上の仮の代表色、及び前記仮の代表色を個別に特定する仮のインデックスを生成する生成部と、
前記符号化データを復号することにより、前記仮の代表色及び前記仮のインデックスを、前記決定された代表色及び前記インデックスに更新するための更新情報、及び復号対象となる画素ブロック内の各画素それぞれに前記インデックスのいずれかを割当てられた割当て情報を復号する復号化部と、
前記更新情報に基づいて、前記仮の代表色及び前記仮のインデックスを、前記決定された代表色及び前記インデックスに更新する更新部と、
前記決定された代表色、前記インデックス及び前記割当て情報に基づいて、復号対象となる画素ブロック内の各画素を復号して再構成する再構成部と、
を有する画像復号化装置。
【請求項７】
前記復号化部は、
前記符号化データを復号することにより、前記決定された代表色及び前記インデックスが、前記仮の代表色及び前記仮のインデックスとは異なることを示す情報の有無を判定し、
前記更新部は、
前記決定された代表色及び前記インデックスが、前記仮の代表色及び前記仮のインデックスとは異なることを示す情報が無い場合、前記更新情報に基づく更新を行わない
請求項６に記載の画像復号化装置。
【請求項８】
前記更新情報は、
前記決定された代表色及び前記インデックスが、前記仮の代表色及び前記仮のインデックスとは異なるか否かを示す情報を、色コンポーネントごとに示す
請求項６又は７に記載の画像復号化装置。
【請求項９】
前記インデックスは、
前記生成部が前記仮の代表色及び前記仮のインデックスを生成するために用いた前記復号済みの画素と、復号対象となる画素ブロック内の画素との相対的な位置関係に応じて符号長が異なる
請求項６〜８のいずれか一項に記載の画像復号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、画像符号化装置及び画像復号化装置に関する。
【背景技術】
【０００２】
自然画像データを圧縮する場合、静止画であればＪＰＥＧ、動画像であればＭＰＥＧを用いることにより効率的なデータ圧縮が可能である。一方で、ＰＣの画面のようなＣＧ画像データに対しては、上記手法よりも複数の代表色（パレット）で各画素を表現するカラーパレット画像符号化の方が効率的なデータ圧縮が可能である。
【０００３】
カラーパレットを利用した画像符号化では、符号化対象となる画素ブロック毎に、対象となる画素ブロックをどのような代表色で表現するかを示す代表色情報、及び画素ブロック中の各画素をどの代表色によって表現するかを示すインデックス情報を符号化データとして出力する。従来代表色情報を符号化する際、符号化済みの画素ブロックの代表色情報と符号化対象の画素ブロックの代表色情報とがすべて同じ場合に、特殊モードとしてその連続性を考慮した符号化を行う技術があった。しかしながら、画素ブロック単位で各画素にそれぞれ色を割当てて順次に画像を符号化する場合、画素ブロック中の代表色数が多いと、符号化済みの画素ブロックの代表色と、符号化対象画素ブロックの代表色とが全て同じである可能性が低く、情報量（データ量）の削減効果が得られないという問題があった。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−１４１７０２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明が解決しようとする課題は、画素ブロック単位で各画素にそれぞれ色を割当てて順次に画像を符号化又は復号化する場合に、画像データを効率的に符号化又は復号化することができる画像符号化装置及び画像復号化装置を提供することである。
【課題を解決するための手段】
【０００６】
実施形態の画像符号化装置は、画素ブロックに含まれる各画素に色を割当てて画像を符号化する。この実施形態の画像符号化装置は、生成部と、更新部と、割当部と、符号化部と、を有する。生成部は、符号化済みの画素に割り当てられた色に基づいて、対象画素に１色以上の仮の代表色、及び仮の代表色を特定するための仮のインデックスを生成する。更新部は、対象画素及び仮の代表色に基づいて、画素ブロック内の各画素の表現に用いる１色以上の決定された代表色、及び決定された代表色を個別に特定するインデックスを生成して、仮の代表色及び仮のインデックスを、決定された代表色及びインデックスに更新する更新情報を生成する。割当部は、符号化対象となる画素ブロック内の各画素それぞれにインデックスのいずれかを割当てた割当て情報を生成する。符号化部は、更新情報及び割当て情報を符号化する。
【図面の簡単な説明】
【０００７】
【図１】実施形態にかかる画像符号化装置の構成を例示するブロック図。
【図２】画像符号化装置が行う処理を示すフローチャート。
【図３】符号化対象の画素ブロックと、参照画素ブロックとを示す図。
【図４】仮の代表色を生成した結果を示す図。
【図５】更新部が仮の代表色を代表色に更新する更新処理を示すフローチャート。
【図６】仮の代表色の更新結果を例示する図。
【図７】重複する仮の代表色を削除して最終的な代表色を生成する場合の更新結果を例示する図。
【図８】重複する仮の代表色を削除して最終的な代表色を生成する場合の更新結果の変形例を示す図。
【図９】図６に例示した更新結果を示す更新情報を例示する図。
【図１０】更新情報の変形例を示す図。
【図１１】符号化済みの画素ブロックの代表色と、次に符号化する符号化対象画素ブロックの代表色とを示す図。
【図１２】図１１に示した符号化済み画素ブロックを利用して更新情報を符号化した場合の符号化データを例示する図。
【図１３】符号化対象の画素ブロック内の各画素に対し、インデックスを割り当てた結果を例示する図。
【図１４】インデックスの符号化例を示す図。
【図１５】符号化部が符号化して出力する符号化データの例を示す図。
【図１６】図１５に示した符号化データの変形例を示す図。
【図１７】実施形態にかかる画像復号化装置の構成を例示するブロック図。
【図１８】画像復号化装置が行う処理を示すフローチャート。
【発明を実施するための形態】
【０００８】
以下に添付図面を参照して、実施形態について説明する。
【０００９】
（画像符号化装置）
図１は、実施形態にかかる画像符号化装置の構成を例示するブロック図である。画像符号化装置は、例えばＣＰＵ、記憶装置及び通信インターフェイスなどを備えたコンピュータとしての機能を有する。又は、画像符号化装置は、例えば、ＰＣの画面など、主にＣＧ画像データを扱う装置やシステムに組み込まれる。そして、画像符号化装置は、ＣＧ画像データを圧縮することにより、伝送速度の向上やＣＧ画像データを保存するＤＲＡＭなどの容量の削減が可能である。
【００１０】
図１に示すように、画像符号化装置は、取得部１０１、生成部１０２、更新部１０３、割当部１０４及び符号化部１０５を有する。なお、取得部１０１、生成部１０２、更新部１０３、割当部１０４及び符号化部１０５は、ハードウェア回路、又はＣＰＵで実行するソフトウェアのいずれであってもよい。
【００１１】
取得部１０１は、符号化対象の画像から処理単位となる画素ブロックと、符号化済みの画素からなる参照画素ブロックを取得する。
【００１２】
生成部１０２は、符号化済みの画素の色（例えば参照画素ブロック）に基づいて、符号化対象となる画素ブロック内の各画素の表現に用いる１色以上の仮の代表色、及び仮の代表色を個別に特定する仮のインデックスを生成する。
【００１３】
更新部１０３は、符号化対象となる画素ブロック内の画素データ及び仮の代表色に基づいて、画素ブロック内の各画素の表現に用いる１色以上の代表色、及び代表色を個別に特定するインデックスを生成して、仮の代表色及び仮のインデックスを、代表色及びインデックスに更新する更新情報を生成する。ここで、更新部１０３は、仮の代表色の中で不要な仮の代表色（画素に割当てられない色）、及び新たに追加が必要な代表色を決定し、最終的に決定された代表色を生成する。
【００１４】
割当部１０４は、符号化対象となる画素ブロック内の各画素それぞれにインデックスのいずれかを割当てた割当て情報を生成することにより、符号化対象となる画素ブロック内の各画素それぞれに代表色のいずれかを割当てる。
【００１５】
符号化部１０５は、更新情報及び割当て情報を符号化し、符号化データとして出力する。
【００１６】
次に、画像符号化装置が行う処理について説明する。図２は、画像符号化装置が行う処理を示すフローチャートである。取得部１０１は、符号化対象の画像から処理単位となる画素ブロックと、符号化済みの画素からなる参照画素ブロックを取得する。つまり、取得部１０１は、画像データを取得する（Ｓ１０１）。
【００１７】
生成部１０２は、符号化済みの画素の色（例えば参照画素ブロック）に基づいて、符号化対象となる画素ブロック内の各画素の表現に用いる１色以上の仮の代表色（仮代表色）、及び仮の代表色を個別に特定する仮のインデックスを生成する（Ｓ１０２）。
【００１８】
更新部１０３は、符号化対象となる画素ブロック内の画素データ及び仮の代表色に基づいて、画素ブロック内の各画素の表現に用いる１色以上の代表色、及び代表色を個別に特定するインデックスを生成して、仮の代表色及び仮のインデックスを、決定された代表色及びインデックスに更新する更新情報を生成する。ここで、更新部１０３は、仮の代表色の中で不要な仮の代表色、及び新たに追加が必要な代表色を決定し、最終的な代表色を生成する。つまり、更新部１０３は、Ｓ１０２の処理で決定した仮の代表色及び仮のインデックスを更新し、仮の代表色を決定された代表色に更新する更新情報を生成する（Ｓ１０３）。
【００１９】
割当部１０４は、符号化対象となる画素ブロック内の各画素それぞれにインデックスのいずれかを割当てた割当て情報を生成することにより、符号化対象となる画素ブロック内の各画素それぞれに代表色のいずれかを割当てる（Ｓ１０４）。
【００２０】
符号化部１０５は、Ｓ１０３の処理で生成した更新情報、及びＳ１０４の処理で生成した割当て情報を符号化する（Ｓ１０５）。画像符号化装置は、処理対象となる画素ブロックが残っていれば、画素ブロックを取得するステップ（Ｓ１０１）に戻り、すべての画素ブロックの処理が終了すれば、符号化処理を終了するものとする。
【００２１】
次に、図２に示した各処理ステップについて、それぞれ詳細に説明する。
【００２２】
（Ｓ１０１）
取得部１０１は、例えば、図３に示したＰｉｘ０〜Ｐｉｘ１５（４×４）の画素を一つの画素ブロックとして取得する。この画素ブロック形状は、Ｎ×Ｎの正方形、Ｍ×Ｎの長方形、及びＭ×１、１×Ｍのラインなどのいずれでもよい（Ｎ，Ｍは１以上の整数。Ｎ≠Ｍ）。また、取得部１０１は、符号化済みの画素から、Ｒｅｆ０〜Ｒｅｆ７の８画素を参照画素ブロックとして取得する。この参照画素ブロックについては、画素ブロックに隣接する上４画素及び左４画素を参照画素とする場合を例に説明するが、これに限定されない。例えば、参照画素は、上４画素のみ、上１ライン分の画素、及び符号化対象画素と所定の位置関係にあるＮｘＭの画素などであってもよい。
【００２３】
画素ブロック内を処理（スキャン）する順は、例えばラスタースキャンとする。また、図３において、各画素の色情報は、ＲＧＢ空間（色情報のダイナミックレンジは８ビット［０：２５５］）で表現されているが、例えば、ＹＵＶ、ＹＣｂＣｒ、ＨＳＶなど他の表色系で表現されてもよく、ダイナミックレンジについても８ビットに制限されることはない。
【００２４】
（Ｓ１０２）
生成部１０２は、参照画素ブロックに基づいて仮の代表色を決定する。例えば、生成部１０２は、図４に示すように、Ｒｅｆ０〜Ｒｅｆ７の画素値（画素データ）をそのままＰａｌｅｔｔｅ０〜Ｐａｌｅｔｔｅ７に割り当てて仮の代表色を生成する。また、生成部１０２は、Ｐａｌｅｔｔｅ０〜Ｐａｌｅｔｔｅ７に対し、それぞれ仮のインデックス（Ｉｎｄｅｘ０〜Ｉｎｄｅｘ７）を生成する。
【００２５】
なお、仮の代表色の生成方法は、図４に示した例に限定されない。例えば、Ｐａｌｅｔｔｅ０をＲｅｆ０の画素値から生成し、Ｐａｌｅｔｔｅ１をＲｅｆ４の画素値から生成し、Ｐａｌｅｔｔｅ２をＲｅｆ１の画素値から生成するというように、上及び左の参照画素を交互に仮の代表色として割り当ててもよい。また、生成部１０２は、参照画素の画素値をそのまま仮の代表色として採用するのではなく、例えば下位Ｎビットを量子化して仮の代表色としてもよく、Ｒｅｆ０とＲｅｆ１の平均といったように複数の参照画素から仮の代表色の画素値を生成してもよい。
【００２６】
（Ｓ１０３）
更新部１０３は、生成部１０２が生成した仮の代表色を画素ブロック内の画素と比較し、更新する必要がある場合（後述）に更新を行って決定された代表色を生成するとともに、仮の代表色を決定された代表色へ更新する更新情報を生成する。
【００２７】
図５は、更新部１０３が仮の代表色を決定された代表色に更新する更新処理を示すフローチャートである。更新部１０３は、処理対象となる画素の画素値を取得する（Ｓ２０１）。なお、更新部１０３は、処理対象画素をラスタースキャン順で走査しながら仮の代表色を更新するが、更新方法はこれに限定されない。
【００２８】
更新部１０３は、処理対象画素の画素値と仮の代表色の画素値との距離を算出する（Ｓ２０２）。例えば、更新部１０３は、下式１によって画素ブロック内の符号化対象画素の画素値と、代表色の画素値との距離を算出する。
【００２９】
距離  ＝  α×｜符号化対象画素のＲ−代表色のＲ｜
＋β×｜符号化対象画素のＧ−代表色のＧ｜
＋γ×｜符号化対象画素のＢ−代表色のＢ｜        ・・・（１）
【００３０】
αはＲに対する重み係数、βはＧに対する重み係数、γはＢに対する重み係数とする。ここではα＝β＝γ＝１とするが、ベイヤー配列などを考慮して、Ｇを優先するのであれば、α＝γ＝１、β＝２としてもよい。また、ＹＵＶ表色系であれば、Ｙに対する重み係数をα、Ｕに対する重み係数をβ、Ｖに対する重み係数をγとした場合、Ｙを優先して、α＝２、β＝γ＝１としてもよい。さらに、８ビット精度での差分を取らずに、例えば、下位ビットを落として（すなわち、算術右シフトのようビット幅を減らす）もよい。８ビットを７ビットにしてから差分を取れば、正負の情報として増える１ビットの情報を加味しても、元の８ビットで処理するビット幅を増やさずに済む。
【００３１】
次に、更新部１０３は、対象画素と全ての代表色との間で距離算出が終了したか否かを判定する（Ｓ２０３）。更新部１０３は、対象画素と全ての代表色との間で距離算出が終了していないと判定した場合（Ｓ２０３：Ｎｏ）にはＳ２０２の処理に進む。また、更新部１０３は、対象画素と全ての代表色との間で距離算出が終了したと判定した場合（Ｓ２０３：Ｙｅｓ）にはＳ２０４の処理に進む。
【００３２】
例えば、図３及び図４に示した例においては、Ｐｉｘ０を処理対象画素とすると、Ｐｉｘ０はＰａｌｅｔｔｅ０と画素値が同じであるため、距離は０となる。つまり、最小の距離となる。
【００３３】
次に、更新部１０３は、最小距離の値が予め定められた閾値よりも大きいか否かを判定する（Ｓ２０４）。更新部１０３は、最小距離の値が予め定められた閾値以下である場合（Ｓ２０４：Ｎｏ）にはＳ２０７の処理に進む。また、更新部１０３は、最小距離の値が予め定められた閾値よりも大きい場合（Ｓ２０４：Ｙｅｓ）にはＳ２０５の処理に進む。
【００３４】
更新部１０３は、仮の各代表色に対して、不要な代表色（削除する代表色）を決定する（Ｓ２０５）。更新部１０３が不要な仮の代表色を決定する方法として、例えば重複する仮の代表色を１つの代表色にまとめたり、色の類似度が高い仮の代表色が複数ある場合にはいずれかの仮の代表色を不要な代表色としたりする方法などがある。また、更新部１０３は、Ｓ２０４の処理において最小距離となる仮の代表色として選択された回数が最小の仮の代表色を不要であると判定してもよい。
【００３５】
更新部１０３は、Ｓ２０５の処理で不要と判定した仮の代表色を削除するとともに、処理対象画素の画素値で仮の代表色を決定された代表色に更新する（Ｓ２０６）。なお、代表色の値の更新については、処理対象画素の画素値をそのまま用いてもよく、例えば、下位Ｎビットを量子化して代表色の値を更新してもよい。
【００３６】
そして、更新部１０３は、画素ブロック内の全ての画素に対して処理が完了したか否かを判定する（Ｓ２０７）。更新部１０３は、画素ブロック内の全ての画素に対して処理が完了していない場合（Ｓ２０７：Ｎｏ）にはＳ２０１の処理に進む。また、更新部１０３は、画素ブロック内の全ての画素に対して処理が完了した場合（Ｓ２０７：Ｙｅｓ）には処理を終了する。
【００３７】
例えば、図３に示した画素に対してラスタースキャン順に処理を進めると、Ｐｉｘ４の処理において、最小距離が３２となり、閾値を上回る。この場合は、更新部１０３は、削除する仮の代表色を決定することとなる。また、更新部１０３は、他の方法で更新を行ってもよい。例えば、更新部１０３は、画素ブロック内の色のヒストグラムを生成し、その分布に基づいて代表色を決定しておき、その後に仮の代表色と代表色を比較し、相違点を更新するような方法を用いてもよい。
【００３８】
図６は、仮の代表色の更新結果を例示する図である。図６においては、更新部１０３の更新処理により、仮の代表色のＰａｌｅｔｔｅ２及びＰａｌｅｔｔｅ３が更新された例が示されている。そして、更新部１０３は、仮の代表色から決定された代表色へ更新する更新情報を生成して出力する。
【００３９】
次に、更新部１０３が生成する更新情報について説明する。図９は、図６に例示した更新結果を示す更新情報を例示する図である。例えば、更新部１０３は、更新情報の先頭にパレット更新の有無を示すフラグ情報（パレット更新Ｆｌａｇ）を出力する。図６に示した例では、Ｐａｌｅｔｔｅ２及びＰａｌｅｔｔｅ３が更新されているため、パレット更新フラグをＴｒｕｅとして符号化部１０５が後に符号化する。
【００４０】
ここでは、８個の仮の代表色に対し、各代表色を更新するか否かを８ｂｉｔの０（更新無）、１（更新有）で示す例をあげて説明する。図６に示した例では、Ｐａｌｅｔｔｅ０〜Ｐａｌｅｔｔｅ７の中で、Ｐａｌｅｔｔｅ２及びＰａｌｅｔｔｅ３が更新されているため、更新部１０３は、更新するパレットを指定する更新パレット指定情報を‘００１１００００’として出力する。そして、更新部１０３は、更新パレット指定情報を出力後、Ｐａｌｅｔｔｅ２の更新後の画素値であるＲ＝１２８，Ｇ＝９６，Ｂ＝１２８を示す情報を２４ｂｉｔ、Ｐａｌｅｔｔｅ３の更新後の画素値であるＲ＝０，Ｇ＝０，Ｂ＝０を示す情報を２４ｂｉｔで出力する。
【００４１】
画素値の情報については、図１０に示すように、更新する色成分をさらに指定する情報を付加してもよい。例えば、Ｐａｌｅｔｔｅ２の更新においては、仮の代表色の画素値Ｒ＝１２８，Ｇ＝６４，Ｂ＝６４から、決定された代表色の画素値Ｒ＝１２８，Ｇ＝９６，Ｂ＝１２８への更新が行われる。このときＲの成分については画素値の変更がないため、値を更新する必要がない。つまり、更新部１０３が更新する色成分を指定する情報を出力することにより、更新する必要のある色成分の画素値のみを符号化部１０５が符号化すればよくなるため、画素値を表現するために必要な情報量を削減することができる。
【００４２】
この例では、更新部１０３は、Ｒ，Ｇ，Ｂの更新の有無をそれぞれ１ｂｉｔの０（更新無），１（更新有）で表現し、更新する色コンポーネントを示すＵｐｄａｔｅ  Ｃｏｍｐを‘０１１’として出力し、その後、更新が必要なＧとＢ成分の画素値を出力している。また、更新部１０３は、Ｐａｌｅｔｔｅ３の更新については、すべての色成分で更新が必要なため、更新する色コンポーネントを示すＵｐｄａｔｅ  Ｃｏｍｐを‘１１１’として出力し、その後、Ｒ，Ｇ，Ｂすべての成分の画素値を出力している。
【００４３】
なお、更新部１０３は、更新される仮の代表色がひとつもない場合には、パレット更新フラグをＦａｌｓｅとして出力する。この場合には、更新パレット指定情報を出力する必要がないため、８ｂｉｔ分の符号量を削減することができる。
【００４４】
ここでは、パレット更新Ｆｌａｇを符号化する場合を例に挙げて説明したが、Ｆｌａｇ情報を用いずに、常にパレット指定情報を符号化するような方式を採用してもよい。なお、図９に例示した更新情報の構成については上述の方法に制限されることはない。例えば、更新パレット指定情報については、更新するパレット数及びそれらのパレットを指定するインデックスを符号化するような形式であってもよい。
【００４５】
また、更新後の画素値についても、画素値の値を固定長で符号化するのではなく、例えば出現しやすい画素値の情報が既知である場合には、ハフマン符号化等により、出現しやすい画素値に対して短い符号長を割り当てて可変長符号化することにより、符号量を削減してもよい。さらに、仮の代表色の画素値から更新後の画素値の差分情報を可変長符号化するようにしてもよい。
【００４６】
また、符号化済みの画素ブロックＢｉ−１の代表色を利用して、次に符号化する符号化対象画素ブロックＢｉの代表色を符号化してもよい。図１１は、符号化済みの画素ブロックＢｉ−１の代表色と、次に符号化する符号化対象画素ブロックＢｉの代表色とを示す図である。
【００４７】
図１１において、符号化対象画素ブロックＢｉでは、Ｐａｌｅｔｔｅ２及びＰａｌｅｔｔｅ３の仮の代表色が更新されたことを示している。ここで、Ｐａｌｅｔｔｅ２における代表色の画素値はＲ＝１２８，Ｇ＝９６，Ｂ＝１２８であり、符号化済み画素ブロックＢｉ−１の代表色のＰａｌｅｔｔｅ４と同じ画素値である。従って、２４ｂｉｔの画素値の情報を出力する代わりに、例えば符号化済み画素ブロックＢｉ−１の代表色の中に同じ画素値の代表色があることを示すフラグ１ｂｉｔと、同じ画素値を持つ代表色を指定する情報３ｂｉｔを出力すれば、符号化対象画素ブロックＢｉの代表色の画素値を表現するために必要な情報量を削減することができる。
【００４８】
また、符号化対象画素ブロックＢｉのＰａｌｅｔｔｅ３に関する画素値の情報については、符号化済み画素ブロックＢｉ−１の代表色の中に同じ画素値のものが存在しない示すフラグを１ｂｉｔ出力し、画素値の情報を２４ｂｉｔで符号化する。
【００４９】
なお、図１１に示した例においては、符号化済み画素ブロックＢｉ−１の代表色の中に、符号化対象画素ブロックＢｉの代表色と完全に一致する画素値が存在するか否かを判定していたが、例えばある閾値を設け、画素値の差が閾値以下である場合に画素値が一致すると判定するようにしてもよい。
【００５０】
図１２は、図１１に示した符号化済み画素ブロックＢｉ−１を利用して更新情報を符号化した場合の符号化データを例示する図である。図１２に示した符号化データ例には、更新情報と、符号化対象の画素ブロックの各画素（Ｐｉｘ０〜Ｐｉｘ１５）に対して割当てられた代表色をそれぞれ特定するインデックス（Ｉｎｄｅｘ１，Ｉｎｄｅｘ１，Ｉｎｄｅｘ１，・・・）とが配列されている。
【００５１】
なお、上述した仮の代表色の更新処理及び更新情報については、不要な代表色を削除し、新たな代表色で置き換えるという例をあげて説明したが、例えば、不要な仮の代表色の削除のみを行うような更新処理や、仮の代表色の削除を行わずに新たな代表色を追加のみ行うような更新処理であってもよい。また、更新部１０３は、追加・削除による更新処理を組み合わせたような更新処理を行ってもよい。これらの場合には、仮の代表色を削除する更新であるか、新たに代表色を追加する更新であるか、それとも仮の代表色を新たな代表色に置き換える更新であるかを示す情報を符号化データに加えればよい。又は、符号化及び復号化側で所定の処理手順に従って、更新方法の切り替えを行うような方法が採用されてもよい。
【００５２】
図７は、重複する仮の代表色を削除して最終的な代表色を生成する場合の更新結果を例示する図である。図７に示すように、重複する仮の代表色を削除する前に、Ｐａｌｅｔｔｅ０，Ｐａｌｅｔｔｅ２，Ｐａｌｅｔｔｅ４，Ｐａｌｅｔｔｅ６，Ｐａｌｅｔｔｅ７のように同じ画素値を持つ仮の代表色が複数存在した場合を例に挙げて説明する。この場合、Ｐａｌｅｔｔｅ２，Ｐａｌｅｔｔｅ４，Ｐａｌｅｔｔｅ６，Ｐａｌｅｔｔｅ７のように、Ｐａｌｅｔｔｅ０と同じ画素値を持つ代表色を削除することにより、図中右側のＰａｌｅｔｔｅ０〜Ｐａｌｅｔｔｅ３までの４つに代表色（決定された代表色）を削減することができるため、インデックスを表現するための情報を０００〜１１１（２）の３ｂｉｔから、００〜１１（２）の２ｂｉｔに削減することができる。
【００５３】
なお、重複した代表色の削除方法については、符号化側及び復号化側で所定の方法に従って削除を行えばよく、その方法によって本発明が制限されることはない。例えば、図７に示した例では、仮の代表色を削除後、残った代表色をＰａｌｅｔｔｅ０〜３に再配置する場合を例に挙げて説明したが、図８に示すように、単純に重複した代表色の削除のみを行うような方法であってもよい。
【００５４】
この場合においても、符号化／復号化側で同一の方法により削除を行うことを規定しておけば、復号側においても同様に代表色情報を生成することができるため、００〜１１（２）の２ｂｉｔの表現により、インデックスからその画素に割り当てられた代表色を算出することができる。
【００５５】
例えば、削除によってＮＵＬＬとなった代表色をスキップして、００〜１１（２）のインデックスを割り当てることを符号化／復号化側であらかじめ規定しておけば、Ｐａｌｅｔｔｅ０に００（２）、Ｐａｌｅｔｔｅ１に０１（２）、Ｐａｌｅｔｔｅ３に１０（２）、Ｐａｌｅｔｔｅ５に１１（２）がそれぞれ割り当てられることがわかる。従って、重複した代表色を削除した後の代表色とインデックスから各画素に割り当てられた代表色の値を算出することができるため、各画素を復号することが可能となる。
【００５６】
なお、上述した例においては、画素値が一致する代表色を重複した代表色として削除する場合について説明したが、例えば差分絶対値和のような代表色間の類似度を評価する評価尺度を設けておき、その類似度が所定の閾値を上回る場合に重複する代表色と判定するような方法であってもよい。
【００５７】
また、重複のない代表色についても、処理対象画素ブロックの符号化に不要である場合には削除するような方法をとってもよい。例えば、処理対象画素ブロックの各画素に対して、代表色へのインデックスの割り当てを行った場合に、一度もインデックスの割り当てが発生しなかった代表色については不要であると判断できるため、代表色から削除することができる。なお、不要な代表色の決定方法については、この方法に限定されることはない。例えば、重複のない代表色について削除を行う場合、削除する代表色を復号側で特定できるように、削除した代表色を指定する情報を符号化データに付加すればよい。
【００５８】
（Ｓ１０４）
割当部１０４は、画素ブロック内の各画素に対して、Ｓ１０３の処理で生成した代表色との距離を算出し、その距離が最小となる代表色のインデックスを割り当てる。画素ブロック内の符号化対象画素の色と、代表色との距離の算出式は、図５に示したＳ２０２の処理における式１を適用する。ただし、距離の算出式についてはこれに制限されることはなく、他の算出式を用いてもよい。また、Ｓ２０２における距離の算出と、ここでの距離の算出とにおいて異なる方法により距離を算出してもよい。
【００５９】
なお、インデックスの割り当て方法については、上述の方法に制限されない。例えば、インデックスの符号化が容易になるように、隣接する画素に同じインデックスが割り当てられ易くするような方法でインデックスを割り当ててもよい。
【００６０】
図１３は、符号化対象の画素ブロック内の各画素に対し、インデックスを割り当てた結果を例示する図である。図１３に示すように、符号化対象の画素ブロック内の各画素には、それぞれ代表色を個別に特定するインデックスが割り当てられることにより、代表色のいずれかが割り当てられる。
【００６１】
（Ｓ１０５）
符号化部１０５は、更新部１０３が生成した更新情報と、割当部１０４が生成した割当て情報とを符号化する。例えば、符号化部１０５は、仮の代表色の生成に用いた参照画素と、符号化対象画素との相対的な位置関係に基づいて、インデックスの符号長を切り替えて、インデックスの符号量を削減する。
【００６２】
図１４は、インデックスの符号化例を示す図である。図１４（ａ）は、参照画素と符号化対象の画素との位置関係を示す図である。仮の代表色は、例えばＲｅｆ０〜Ｒｅｆ７の画素値を用いて生成される。代表色は、仮の代表色に基づいて更新される。従って、画素値の類似度に基づいてインデックスの割り当てを行う場合、隣接画素間の画素値の相関により、符号化対象画素と距離が近い参照画素から生成された仮の代表色のインデックスが割り当てられる確率が高い。
【００６３】
例えば、図１４に示した例では、Ｐｉｘ０の画素には相対的な距離が近いＲｅｆ０やＲｅｆ４から生成された仮代表色のインデックスであるインデックス０、又はインデックス４が割り当てられる確率が高い。Ｐｉｘ３のインデックスでは、Ｒｅｆ３あるいはＲｅｆ２の参照画素から生成された仮の代表色のインデックスであるインデックス３又はインデックス２が割り当てられる確率が高い。従って、符号化対象画素と仮の代表色の生成に用いた参照画素との相対的な位置関係に基づいて、割り当てられる確率の高いインデックスに短い符号長を割り当てることにより、インデックスの符号量を削減することができる。
【００６４】
図１４（ｂ）は、図１４（ａ）に示したＰｉｘ０の位置における符号長テーブルを例示する図である。図１４（ｃ）は、図１４（ａ）に示したＰｉｘ３の位置における符号長テーブルを例示する図である。つまり、符号化部１０５は、参照画素と符号化対象の画素との位置関係に基づいて、符号化対象の画素それぞれに対するインデックスの符号長を切替える。
【００６５】
なお、インデックスと符号の関係については図１４に示した符号に限定されるものではなくその他の符号テーブルを用いてもよい。さらに、符号化部１０５は、隣接画素間では同じインデックスが割り当てられる可能性が高いことを考慮し、参照画素と符号化対象画素の位置関係だけではなく、隣接する符号化済みの画素に割り当てられたインデックスに応じてさらにインデックスの符号長テーブルを切り替えてもよい。
【００６６】
例えば、Ｐｉｘ５のインデックスを符号化する場合、符号化部１０５は、Ｐｉｘ５と参照画素との相対的な位置関係に加え、符号化済みの隣接画素Ｐｉｘ０〜Ｐｉｘ２及びＰｉｘ４に割り当てられたインデックスに応じて、Ｐｉｘ５に割り当てられる可能性の高いインデックスに短い符号長を割り当ててもよい。
【００６７】
また、インデックスの符号化においては、上述の方法に制限されることはない。例えば、符号化部１０５は、各画素に割り当てられたインデックスを０００（２）〜１１１（２）の固定長３ｂｉｔによりインデックスの０〜７を表現することにより符号化してもよい。また、符号化部１０５は、ランレングス符号化等により、隣接画素間でのインデックスの類似度を利用して可変長符号化するような方法や、ハフマン符号化のように、出現頻度に基づいて符号長を切り替える方法を用いてもよい。
【００６８】
図１５は、符号化部１０５が符号化して出力する符号化データの例を示す図である。図１５に示した符号化データ例には、更新情報と、符号化対象の画素ブロックの各画素（Ｐｉｘ０〜Ｐｉｘ１５）に対して割当てられた代表色をそれぞれ特定するインデックス（Ｉｎｄｅｘ０，Ｉｎｄｅｘ１，Ｉｎｄｅｘ１，Ｉｎｄｅｘ１，・・・）とが配列されている。
【００６９】
なお、符号化データの出力順序については、図１５に示した例に制限されない。図１６は、図１５に示した符号化データの変形例を示す図である。符号化部１０５は、更新情報と各画素に対するインデックスとを混在させ、代表色が初めて参照された時点でその代表色の更新情報を出力するような構成であってもよい。
【００７０】
このように、実施形態にかかる画像符号化装置によれば、代表色を更新する更新情報と、符号化対象となる画素ブロック内の各画素それぞれに代表色を個別に特定するインデックスのいずれかを割当てた割当て情報とを符号化するので、画素ブロック単位で各画素にそれぞれ色を割当てて順次に画像を符号化する場合に、画像データを効率的に符号化することができる。
【００７１】
（画像復号化装置）
図１７は、実施形態にかかる画像復号化装置の構成を例示するブロック図である。画像復号化装置は、例えばＣＰＵ、記憶装置及び通信インターフェイスなどを備えたコンピュータとしての機能を有する。又は、画像復号化装置は、例えば、ＰＣの画面など、主にＣＧ画像データを扱う装置やシステムに組み込まれる。そして、画像復号化装置は、図１に示した画像符号化装置から出力された符号化データを復号化する。なお、画像復号化装置
は、図１に示した画像符号化装置から出力された符号化データを復号化するものであればよく、図１７に示した構成に限定されない。
【００７２】
図１７に示すように、画像復号化装置は、取得部２０１、生成部２０２、復号化部２０３、更新部２０４及び再構成部２０５を有する。なお、取得部２０１、生成部２０２、復号化部２０３、更新部２０４及び再構成部２０５は、ハードウェア回路、又はＣＰＵで実行するソフトウェアのいずれであってもよい。
【００７３】
取得部２０１は、復号化対象となる符号化データ、及び復号化済みの参照画素ブロックを取得する。生成部２０２は、例えば、復号済みの画素の色（例えば参照画素ブロック）に基づいて、復号対象となる画素ブロック内の各画素の表現に用いる１色以上の仮の代表色、及び仮の代表色を個別に特定する仮のインデックスを生成する。
【００７４】
復号化部２０３は、符号化データを復号することにより、仮の代表色及び仮のインデックスを、代表色及びインデックスに更新するための更新情報、及び復号対象となる画素ブロック内の各画素それぞれにインデックスのいずれかを割当てられた割当て情報を復号する。
【００７５】
更新部２０４は、更新情報に基づいて、仮の代表色及び仮のインデックスを、決定された代表色及びインデックスに更新する。再構成部２０５は、代表色、インデックス及び割当て情報に基づいて、復号対象となる画素ブロック内の各画素を復号して再構成する。
【００７６】
次に、画像復号化装置が行う処理について説明する。図１８は、画像復号化装置が行う処理を示すフローチャートである。
【００７７】
取得部２０１は、復号化対象となる符号化データ、及び復号化済みの参照画素ブロックを取得する（Ｓ３０１）。
【００７８】
生成部２０２は、例えば、復号済みの画素の色（例えば参照画素ブロック）に基づいて、復号対象となる画素ブロック内の各画素の表現に用いる１色以上の仮の代表色、及び仮の代表色を個別に特定する仮のインデックスを生成する（Ｓ３０２）。
【００７９】
復号化部２０３は、符号化データを復号することにより、仮の代表色及び仮のインデックスを、決定された代表色及びインデックスに更新するための更新情報、及び復号対象となる画素ブロック内の各画素それぞれにインデックスのいずれかを割当てられた割当て情報を復号する（Ｓ３０３）。
【００８０】
更新部２０４は、更新情報に基づいて、仮の代表色及び仮のインデックスを、決定された代表色及びインデックスに更新する（Ｓ３０４）。
【００８１】
再構成部２０５は、代表色、インデックス及び割当て情報に基づいて、復号対象となる画素ブロック内の各画素を復号して再構成する（Ｓ３０５）。画像復号化装置は、処理対象となる符号化データが残っていれば、Ｓ３０１の処理に戻り、すべての符号化データの処理が終了すれば、復号化処理を終了する。
【００８２】
このように、実施形態にかかる画像復号化装置によれば、代表色を更新する更新情報と、復号化対象となる画素ブロック内の各画素それぞれに割当てられた代表色を個別に特定するインデックスを示す割当て情報とを復号化するので、画素ブロック単位で各画素にそれぞれ色を割当てて順次に符号化された符号化データを効率的に復号化することができる。
【００８３】
また、本発明のいくつかの実施形態を複数の組み合わせによって説明したが、これらの実施形態は例として提示したものであり、発明の範囲を限定することは意図していない。これら新規の実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００８４】
１０１  取得部
１０２  生成部
１０３  更新部
１０４  割当部
１０５  符号化部
２０１  取得部
２０２  生成部
２０３  復号化部
２０４  更新部
２０５  再構成部
【図１】
2015023506.tif 000003
【図２】
2015023506.tif 000004
【図３】
2015023506.tif 000005
【図４】
2015023506.tif 000006
【図５】
2015023506.tif 000007
【図６】
2015023506.tif 000008
【図７】
2015023506.tif 000009
【図８】
2015023506.tif 000010
【図９】
2015023506.tif 000011
【図１０】
2015023506.tif 000012
【図１１】
2015023506.tif 000013
【図１２】
2015023506.tif 000014
【図１３】
2015023506.tif 000015
【図１４】
2015023506.tif 000016
【図１５】
2015023506.tif 000017
【図１６】
2015023506.tif 000018
【図１７】
2015023506.tif 000019
【図１８】
2015023506.tif 000020