(57)【要約】ブロック単位での分割情報を示すフラグを含むビットストリームを取得するステップと、前記階層の深さＮよりも深さが小さい階層に属する上位ブロックに付与された、前記上位ブロックの四分木の分割情報を示す上位フラグを復号し取得するステップと、前記階層の深さＮに属する下位ブロックのうち、第１の下位ブロックに付与された、前記上位ブロックの四分木の分割情報を示す第１の下位フラグを復号し取得するステップと、既に取得している前記上位フラグ及び複数の前記第１の下位フラグが特定の組み合わせである場合に、前記階層の深さＮに属する第２の下位ブロックの四分木の分割情報を示す第２の下位フラグとして予め定めた第１の値を設定し、前記特定の組み合わせではない場合に、前記第２の下位フラグを復号し取得するステップと、前記上位フラグと、第１及び第２の下位フラグに従って、前記ブロックの復号画像信号を生成するステップと、を具備する。
2011121843.tif 000002
【特許請求の範囲】
【請求項１】
入力画像信号を、階層の深さＮに応じたブロックサイズに分割されたブロックを復号する動画像復号化方法において、
ブロック単位での分割情報を示すフラグを含むビットストリームを取得するステップと、
前記階層の深さＮよりも深さが小さい階層に属する上位ブロックに付与された、前記上位ブロックの四分木の分割情報を示す上位フラグを復号し取得するステップと、
前記階層の深さＮに属する下位ブロックのうち、第１の下位ブロックに付与された、前記上位ブロックの四分木の分割情報を示す第１の下位フラグを復号し取得するステップと、
既に取得している前記上位フラグ及び複数の前記第１の下位フラグが特定の組み合わせである場合に、前記階層の深さＮに属する第２の下位ブロックの四分木の分割情報を示す第２の下位フラグとして予め定めた第１の値を設定し、前記特定の組み合わせではない場合に、前記第２の下位フラグを復号し取得するステップと、
前記上位フラグと、第１及び第２の下位フラグに従って、前記ブロックの復号画像信号を生成するステップと、
を具備する動画像復号化方法。
【請求項２】
前記フラグは、予測残差信号の有無を表すコーデットブロックフラグであることを、特徴とする請求項１記載の動画像復号化方法。
【請求項３】
前記フラグは、画面間予測で使われるスキップモードかどうかを表すスキップフラグであることを、特徴とする請求項１記載の動画像復号化方法。
【請求項４】
前記特定の組み合わせは、前記上位フラグが前記第１の値であり、前記上位ブロックに包含される複数の前記下位ブロックのうち、前記第２の下位ブロックを除いた全ての下位ブロックの前記第１のフラグが前記第１の値とは異なる第２の値であることを、特徴とする請求項１記載の動画像復号化方法。
【請求項５】
入力画像信号を、階層の深さＮに応じたブロックサイズに分割されたブロックに符号化処理を行う動画像符号化方法において、
ブロック単位での分割情報を示すフラグを符号化するステップと、
前記階層の深さＮよりも深さが小さい階層に属する上位ブロックに付与された、前記上位ブロックの四分木の分割情報を示す上位フラグを取得するステップと、
前記階層の深さＮに属する下位ブロックのうち、第１の下位ブロックに付与された、前記上位ブロックの四分木の分割情報を示す第１の下位フラグを取得するステップと、
既に取得している前記上位フラグ及び複数の前記第１の下位フラグが特定の組み合わせである場合に、前記階層の深さＮに属する第２の下位ブロックの四分木の分割情報を示す第２の下位フラグとして予め定めた第１の値を設定し、前記特定の組み合わせではない場合に、前記第２の下位フラグを取得するステップと、
前記上位フラグと、第１及び第２の下位フラグに従って、前記ブロックの局部復号画像信号を生成するステップと、
を具備する動画像符号化方法。
【請求項６】
前記フラグは、予測残差信号の有無を表すコーデットブロックフラグであることを、特徴とする請求項５記載の動画像符号化方法。
【請求項７】
前記フラグは、画面間予測で使われるスキップモードかどうかを表すスキップフラグであることを、特徴とする請求項５記載の動画像符号化方法。
【請求項８】
記特定の組み合わせは、前記上位フラグが前記第１の値であり、前記上位ブロックに包含される複数の前記下位ブロックのうち、前記第２の下位ブロックを除いた全ての下位ブロックの前記第１のフラグが前記第１の値とは異なる第２の値であることを特徴とする請求項５記載の動画像符号化方法。
【請求項９】
ブロック単位での予測情報、ブロック単位での予測残差信号の有無を表すコーデットパターンデータ、およびブロック単位での予測残差信号をエントロピー符号化した画像データを含むビットストリームを入力するステップと、
前記ビットストリームに含まれる情報が上位コーデットパターンデータである場合に、前記ビットストリームを復号化し上位コーデットパターンデータを取得するステップと、
前記ビットストリームに含まれる情報が前記上位コーデットパターンデータに属するコーデットパターンデータである下位コーデットパターンデータであり、かつ、すでに取得した前記上位コーデットパターンデータと該下位コーデットパターンデータの組み合わせが特定の組み合わせである場合に下位コーデットパターンデータとして予め定めたデータを設定し、前記特定の組み合わせでない場合に前記ビットストリームを復号化し次の下位コーデットパターンデータを取得するステップと、
前記コーデットパターンデータによりブロック単位での予測残差信号の有無を判別するステップと、
前記ビットストリームに含まれる情報がブロック単位での予測情報である場合には、前記ビットストリームを復号化しブロック単位での予測情報を得るステップと、
前記ビットストリームに含まれる情報がブロック単位での予測残差信号である場合には、前記ビットストリームを復号化しブロック単位での予測残差信号を得るステップと、
前記ブロック単位での予測情報、および前記ブロック単位での予測残差信号を利用して、画像信号を復号化するステップと、を具備することを特徴とする画像復号化方法。
【請求項１０】
ブロック単位での予測情報、およびブロック単位での予測残差信号をエントロピー符号化した画像データを含むビットストリームを入力するステップと、
前記ビットストリームに含まれる予測情報が複数のブロックのスキップ予測を表す上位スキップデータである場合に、前記ビットストリームを復号化し上位スキップデータを取得するステップと、
前記ビットストリームに含まれる予測情報が前記上位スキップデータに属するスキップデータである下位スキップデータであり、かつ、すでに取得した前記上位スキップデータと該下位スキップデータの組み合わせが特定の組み合わせである場合に次の下位スキップデータとして予め定めたデータを設定し、前記特定の組み合わせでない場合に前記ビットストリームを復号化し次の下位スキップデータを取得するステップと、
前記ブロック単位での予測情報、および前記ブロック単位での予測残差信号を利用して、画像信号を復号化するステップと、を具備することを特徴とする画像復号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、符号化及び復号化方法に関する。
【背景技術】
【０００２】
動画像の符号化技術の１つとしてＨ．２６４（例えば非特許文献１）が知られている。Ｈ．２６４は復号化（デコード）の方法を定めた規格である。Ｈ．２６４では、フレーム内およびフレーム間予測の残差（予測誤差）は予め定められた直交変換により変換し、その変換係数を量子化したうえで符号化する。直交変換のサイズは符号化モードにより４ｘ４画素ブロック、８ｘ８画素ブロックの２種類のいずれかが使用される。直交変換の係数は、量子化によりゼロになることが多い。そこでＨ．２６４では、符号量を減らすために、すべての変換係数がゼロであるかを表す１ビットのフラグを符号化し、すべての変換係数がゼロである場合には変換係数の符号化をスキップする。このフラグは、０がすべての係数がゼロであることを表し、１が少なくとも１つの非ゼロの係数があることを表す。【０００３】
Ｈ．２６４では、４ｘ４画素ブロック内の変換数に対するフラグをＣＢＦ（coded block flag）と呼び、８ｘ８画素以上のブロックに対するフラグについてはＣＢＰ（coded block pattern）と呼ぶ。ＣＢＦについては、符号化モードにより、すべての変換係数がゼロであるか否かを表す場合と、変換係数の最初の変換係数（ＤＣ成分）以外の係数がすべてゼロであるか否かを表す場合がある。また、４つの４ｘ４画素ブロックは８ｘ８画素のブロックが分割されたものとして扱われ、４つの４ｘ４画素ブロックの変換係数がすべて０である場合には、８ｘ８画素のブロックに対するフラグ（ＣＢＰ）を０とする。また、１６ｘ１６画素のブロックに対してもＣＢＰは符号化され、このＣＢＰは、４つの８ｘ８画素の輝度信号（Luminance）ブロック、その１６ｘ１６画素のブロックに対応する２つの色差信号（Chrominance）ブロックのすべての変換係数がゼロであるか否かを表す。これらのことからわかるように、変換係数が０であるか否かという情報（ＣＢＰおよびＣＢＦ）は階層的に符号化されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】ITU-T (Telecommunication Standardization Sector of International Telecommunication Union) Recommendation H.264, “Advanced video coding for generic audiovisual services”’, 2003.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
符号化モードによっては、ＣＢＰおよびＣＢＦの符号化において、ＣＢＰが０であるなら必ずＣＢＦが０であるというモードが存在する。Ｈ．２６４では、これらの符号化モードにおいても、ＣＢＰが１、すべてのＣＢＦが０という情報を符号化できる。このようなＣＢＰとＣＢＦの組み合わせに符号を割り当てることは冗長である。この冗長性を排除すれば、圧縮率を向上できる。【０００６】
なお、Ｈ．２６４におけるＣＢＦとＣＢＰの符号化でなくても、ＣＢＰを階層的に符号化する場合には同様の冗長性が生じる。また、Ｈ．２６４のインター予測ではスキップ予測であるか否かをあらわすモード情報を１ビットで符号化する。今後のＨ．２６４の拡張を考えると、このスキップフラグを階層的に符号化する場合についても同様の冗長性が生じると考えられる。階層的なスキップフラグの符号化における冗長性については、Ｈ．２６４におけるＣＢＰおよびＣＢＦの冗長性に対する本発明の解決手段と同じ手段で解決できる。【０００７】
本発明の目的は、階層的なＣＢＰやＣＢＦ、スキップフラグの符号化時の冗長性を排除した圧縮データを得ること、及び圧縮データを復号化することにある。
【課題を解決するための手段】
【０００８】
実施形態の画像復号化方法は、入力画像信号を、階層の深さＮに応じたブロックサイズに分割されたブロックを復号する動画像復号化方法において、ブロック単位での分割情報を示すフラグを含むビットストリームを取得するステップと、前記階層の深さＮよりも深さが小さい階層に属する上位ブロックに付与された、前記上位ブロックの四分木の分割情報を示す上位フラグを復号し取得するステップと、前記階層の深さＮに属する下位ブロックのうち、第１の下位ブロックに付与された、前記上位ブロックの四分木の分割情報を示す第１の下位フラグを復号し取得するステップと、既に取得している前記上位フラグ及び複数の前記第１の下位フラグが特定の組み合わせである場合に、前記階層の深さＮに属する第２の下位ブロックの四分木の分割情報を示す第２の下位フラグとして予め定めた第１の値を設定し、前記特定の組み合わせではない場合に、前記第２の下位フラグを復号し取得するステップと、前記上位フラグと、第１及び第２の下位フラグに従って、前記ブロックの復号画像信号を生成するステップと、を具備する。【０００９】
また、実施形態の画像復号化方法は、入力画像信号を、階層の深さＮに応じたブロックサイズに分割されたブロックに符号化処理を行う動画像符号化方法において、ブロック単位での分割情報を示すフラグを符号化するステップと、前記階層の深さＮよりも深さが小さい階層に属する上位ブロックに付与された、前記上位ブロックの四分木の分割情報を示す上位フラグを取得するステップと、前記階層の深さＮに属する下位ブロックのうち、第１の下位ブロックに付与された、前記上位ブロックの四分木の分割情報を示す第１の下位フラグを取得するステップと、既に取得している前記上位フラグ及び複数の前記第１の下位フラグが特定の組み合わせである場合に、前記階層の深さＮに属する第２の下位ブロックの四分木の分割情報を示す第２の下位フラグとして予め定めた第１の値を設定し、前記特定の組み合わせではない場合に、前記第２の下位フラグを取得するステップと、前記上位フラグと、第１及び第２の下位フラグに従って、前記ブロックの局部復号画像信号を生成するステップと、を具備する。
【発明の効果】
【００１０】
本発明によれば、階層的なＣＢＰやＣＢＦ、スキップフラグの符号化時の冗長性を排除した符号化手段により圧縮されたデータが与えられたときに、復号化する画像復号化方法を提供することができる。
【図面の簡単な説明】
【００１１】
【図１】符号化又は復号化の対象となる画素ブロックと符号化処理方向を表す図。
【図２】本実施の形態の階層的ＣＢＰ（下位が４ビットの場合）を示す図。
【図３】図２に対応する単純な階層的ＣＢＰを示す図。
【図４】本実施の形態の階層的ＣＢＰ（下位が２ビットの場合）を示す図。
【図５】本実施の形態のブロック単位のＣＢＰの符号化の動作の一例を示すフローチャート。
【図６】図５の動作を実行する符号化装置のブロック図。
【図７】本実施の形態のブロック単位のＣＢＰの復号化の動作の一例を示すフローチャート。
【図８】図７の動作を実行する符号化装置のブロック図。
【図９】本実施の形態の階層的ＣＢＰの復号化方法の一例を示す図。
【図１０】図９の別の一例を示す図。
【図１１】図９の条件分岐を反転させた復号化方法の一例を示す図。
【図１２】８ｘ８画素のブロックに対応するＣＢＰが非０の場合に、４ｘ４画素ブロックのＣＢＦを復号化方法の一例を示す図。
【図１３】上位ブロックのサイズが６４ｘ６４画素、下位ブロックのサイズが３２ｘ３２画素であり、かつ、下位が４ビットの階層的ＣＢＰを復号化方法の一例を示す図。
【図１４】図１３の別の一例を示す図。
【図１５】１６ｘ１６の画素ブロックに対する１ビットの輝度ＣＢＰが与えられた場合に、４ｘ４、８ｘ８、１６ｘ８、８ｘ１６、１６ｘ１６の変換についてのｃｂｐを得るシンタックスの一例を示す図。
【図１６】単純な階層的スキップフラグを示す図。
【図１７】図１６に対応する本実施の形態の階層的スキップフラグを示す図。
【図１８】本実施の形態のブロック単位のスキップフラグの復号化の動作の一例を示す図。
【図１９】図１８の動作を実現するシンタックスの一例を示す図。
【図２０Ａ】四分木分割に基づいた再帰的ブロック分割の一例を示す図。
【図２０Ｂ】四分木分割に基づいた再帰的ブロック分割の一例を示す図。
【図２０Ｃ】四分木分割に基づいた再帰的ブロック分割の一例を示す図。
【図２１】四分木分割に基づいた再帰的ブロック分割におけるコーデットブロックフラグのシンタクス構造の一例を示す図。
【図２２】四分木分割に基づいた再帰的ブロック分割におけるコーデットブロックフラグの冗長度を削減するシンタクス構造の一例を示す図。
【図２３Ａ】四分木分割に基づいた再帰的ブロック分割におけるコーデットブロックフラグの冗長度を削減するシンタクス構造の一例を示す図。
【図２３Ｂ】四分木分割に基づいた再帰的ブロック分割におけるコーデットブロックフラグの冗長度を削減するシンタクス構造の一例を示す図。
【図２４Ａ】四分木分割に基づいた再帰的ブロック分割における上位コーデットブロックフラグと下位コーデットブロックフラグの符号長の一例を示す図。
【図２４Ｂ】四分木分割に基づいた再帰的ブロック分割における上位コーデットブロックフラグと下位コーデットブロックフラグの符号長の一例を示す図。
【図２４Ｃ】四分木分割に基づいた再帰的ブロック分割における上位コーデットブロックフラグと下位コーデットブロックフラグの符号長の一例を示す図。
【図２４Ｄ】四分木分割に基づいた再帰的ブロック分割における上位コーデットブロックフラグと下位コーデットブロックフラグの符号長の一例を示す図。
【図２５】四分木分割に基づいた再帰的ブロック分割におけるスキップフラグの冗長度を削減するシンタクス構造の一例を示す図。
【図２６Ａ】四分木分割に基づいた再帰的ブロック分割におけるスキップフラグの冗長度を削減するシンタクス構造の一例を示す図。
【図２６Ｂ】四分木分割に基づいた再帰的ブロック分割におけるスキップフラグの冗長度を削減するシンタクス構造の一例を示す図。
【図２７】コーデットブロックフラグのシンタクス構造とスキップフラグのシンタクス構造とを組み合わせたシンタクス構造の一例を示す図。
【図２８】本実施の形態の階層的なスキップフラグの符号化の動作の一例を示すフローチャート。
【発明を実施するための形態】
【００１２】
以下、図面を参照しながら本発明の実施の形態に係る画像復号化方法、画像符号化方法、および装置について詳細に説明する。なお、以下の実施の形態では、同一の番号を付した部分については同様の動作を行うものとして、重ねての説明を省略する。  
まず、Ｈ．２６４で復号化可能なデータを生成する符号化手段について簡単に説明しておく。この符号化手段は、例えば、図１に示すような、フレーム内予測（Ｉｎｔｒａ予測）またはフレーム間予測（Ｉｎｔｅｒ予測）、離散コサイン変換（ＤＣＴ；Discrete Cosine Transform)の近似である整数精度の直交変換およびその逆変換、係数の量子化および逆量子化、コンテキスト適応２値算術符号（ＣＡＢＡＣ； Context-based Adaptive Binary Arithmetic Code)あるいは可変長符号化(ＣＡＶＬＣ；Context-adaptive Variable Length Coding)と呼ばれるエントロピー符号を組み合わせた手段により、Ｈ．２６４で復号化可能なデータを生成できる。
【００１３】
本実施の形態では、符号化においては上位のＣＢＰが１である場合に、下位のＣＢＰ（４ｘ４画素の場合はＣＢＦ）がすべて０であるという冗長な組み合わせに符号を割り当てないことを考える。本実施の形態の画像復号化方法はそのような圧縮データの復号化を目的とする。また、上位のスキップフラグが０である場合に、下位のスキップフラグがすべて１となるという冗長な組み合わせへの符号の割り当てを避けた符号化を行うものとする。本実施の形態の画像復号化方法はそのような圧縮データの復号化を行う。
【００１４】
（階層的ＣＢＰの冗長性削減、エンコーダ）  
以下、残差信号の有無を表す情報をコーデットパターンデータと呼ぶこととする。Ｈ．２６４の規格書においては、コーデットパターンデータのうち、複数の８ｘ８画素あるいは１６ｘ１６画素ブロックに対するフラグをまとめたデータがＣＢＰ、１つの４ｘ４画素ブロックに対するフラグがＣＢＦに対応する。コーデットパターンデータのうち、上位の１ブロックに対応するコーデットパターンデータをｕｐｐｅｒ＿ｆｌａｇ、その上位の１ブロックに属するｉ番目の下位のコーデットパターンデータをｌｏｗｅｒ＿ｆｌａｇｓ［ｉ］と呼ぶことにする。例えば、上記非特許文献１において、Ｌｕｍｉｎａｎｃｅ信号に対する８ｘ８画素ブロックのＣＢＰおよび４ｘ４画素ブロックのＣＢＦの場合、ｕｐｐｅｒ＿ｆｌａｇおよびｌｏｗｅｒ＿ｆｌａｇｓ［ｉ］は、それぞれＣｏｄｅｄＢｌｏｃｋＰａｔｔｅｒｎＬｕｍａ内の１ビット、およびｉ番目の４ｘ４画素ブロックの残差信号に対するｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇに対応する。
【００１５】
ＭＰＥＧ−１／２／４の圧縮ビデオ復号規格やＨ．２６４など多くの規格に定められた復号化の過程では、画像をブロック単位で区切ったうえで、ブロック単位での復号化処理を行う。そこで、以下の説明では、ブロック単位での符号化（エンコード）の過程の一例、およびブロック単位での復号化（デコード）の過程の一例について説明する。画面全体の処理は、ブロック単位の処理を区切られたブロックの数だけ繰り返すことで行える。
【００１６】
本発明の実施の形態では、コーデットパターンデータを階層的に符号化する際に、特定のパターンに対応する符号量を減らすことで圧縮率を向上させる手段を提供し、およびそのような手段で生成されたビットストリームを復号化する。特定のパターンの具体的な例（下位が４ビットの場合）を図２に示し、図２に対応した単純な階層的コーデットパターンデータの例（下位が４ビットの場合）を図３に示す（なお、図３は上記非特許文献１のＨ．２６４で使われている）。
【００１７】
図３では、下位コーデットパターンデータ（ｌｏｗｅｒ−ｆｌａｇｓ）が０００１の場合に、符号化データは０００１になる。これに対し、図２の本発明の実施の形態では、下位コーデットパターンデータ（ｌｏｗｅｒ−ｆｌａｇｓ）が０００１の場合には最後の１ビットを符号せず、符号化データを０００とする。復号化においては、上位コーデットパターンデータが１であり、かつ、４ビットの下位コーデットパターンのうち、最後の１ビットを除いた３ビットが０００であることがわかれば、最後の１ビットは１であることがわかる。すなわち、符号化において１ビット分符号化する必要、および、符号化されたデータの復号化において１ビット分復号化する必要がなくなる場合がある。
【００１８】
なお、図２では下位のコーデットパターンデータを４ビットとしているが、特に４ビットである必要はなく、例えば図４に示す２ビットであってもよい。２ビットの場合には、上位コーデットパターンデータが１であり、かつ、２ビットの下位コーデットパターンのうち、最初の１ビットが０であることがわかれば、最後の１ビットは１であることがわかる。したがって、この場合も、符号化において１ビット分符号化する必要、および、符号化されたデータの復号化において１ビット分復号化する必要がなくなる場合がある。
【００１９】
次に、ブロック単位のＣＢＰの符号化の過程を示すフローチャートを図５、符号化に利用する装置の一例を図６に示す。コーデットパターンデータの符号化は、例えば、次の方法により行える。なお、以下の説明では、コーデットパターンデータ以外の部分の符号化であるステップ３、ステップ１１も含めて説明する。
【００２０】
ステップ１．（Ｓ５０１）画像入力部６０１が画像ブロックを読み込む。ここで読み込むブロックは、典型的には、ステップ５における上位コーデットパターンデータに対応したブロックと同じか、それより大きなサイズ（例えば、１６ｘ１６画素）を持つものとする。
【００２１】
ステップ２．（Ｓ５０２）演算ユニット６０２がＳ５０１で読みこんだブロックに対して符号化すべき予測モードをプログラム用メモリ６０５から読み込む。なお、この予測モードは予め決めておく場合もあるし、複数の予測モードのそれぞれでステップＳ５０３以降を行い最も良いモードを選択する場合もある。他にも予測モードを設定する変形例はたくさんある。
【００２２】
ステップ３．演算ユニット６０２は予測モードを符号化して、符号化データ出力部６０４はビットストリームに出力する。
【００２３】
ステップ４．（Ｓ５０３）演算ユニット６０２は予測モードとすでに復号可能となったデータを利用してブロック予測を行い、入力画像ブロックと予測画像ブロックの差である予測残差を求める。
【００２４】
ステップ５．（Ｓ５０４）演算ユニット６０２は、予測残差にブロック変換（例えば、あらかじめトレーニングデータにより生成したＫＬＴの基底や、ＤＣＴの基底を利用した直交変換）および量子化を施す。ここで変換を行うブロックは、ステップ１のブロックよりも小さなサイズ（例えば、４ｘ４画素）を持つものとする。次に、演算ユニット６０２は量子化された変換係数の中に非０の係数が存在するか否かをあらわす情報をブロック単位で算出する。典型的には、この情報は、ブロック内に非０の係数が存在する場合には１、ブロック内の係数がすべて０の場合には０という、ブロックごとに１ビットのフラグ情報になる。この情報を下位のコーデットパターンデータ（下位ＣＢＰやＣＢＦ）と呼ぶ。次に、下位のコーデットパターンデータの集合（例えば、４つの下位のコーデットパターンデータ）がすべて０か否かという情報を表す、より大きなブロックに対するコーデットパターンデータである上位のコーデットパターンデータ（上位ＣＢＰ）を求める。典型的には、上位のコーデットパターンデータは、下位のコーデットパターンデータがすべて０であれば０、下位のコーデットパターンデータに１つでも非０の情報があれば１という、ブロックごとに１ビットのフラグ情報になる。ここで、上位コーデットパターンデータに対応するブロックのサイズは、下位コーデットパターンデータよりも大きなサイズ（例えば８ｘ８画素）を持つものとする。
【００２５】
ステップ６．（Ｓ５０５）演算ユニット６０２が上位のコーデットパターンデータを符号化して、符号化データ出力部６０４がビットストリームに出力する。
【００２６】
ステップ７．（Ｓ５０６）演算ユニット６０２は、上位のコーデットパターンデータが０である場合にはステップ８〜１０を飛ばし、そうでないのならステップ８を実行する。
【００２７】
ステップ８．（Ｓ５０７）ステップ８〜１０は下位のコーデットパターンデータを１ビットずつ符号化していく過程である。このステップでは次の条件分岐を実行する。演算ユニット６０２は、すでに符号化された下位のコーデットパターンデータが特定のパターンデータである場合（典型的には、最後の１ビットの下位のコーデットパターンデータを符号化する場合であって、かつ、符号化済みの下位のコーデットパターンデータがすべて０である場合）には、次のビットストリームに出力するステップ９を飛ばし、そうでなければステップ９を実行する。
【００２８】
ステップ９．（Ｓ５０８）次に、演算ユニット６０２は符号化すべき下位のコーデットパターンデータを符号化して、符号化データ出力部６０４はビットストリームに出力する。
【００２９】
ステップ１０．（Ｓ５０９）演算ユニット６０２は、下位のコーデットパターンデータをすべて符号化していればステップ１１に進め、そうでなければステップ８に戻る。Ｓ５０７からＳ５０９のループはビット数に応じて回る回数が決まり、例えば４ビットであれば４回だけ回すことになる。
【００３０】
ステップ１１．符号化データ出力部６０４は、コーデットパターンデータが非０のブロックについて、量子化された変換係数を符号化してビットストリームに出力する。
【００３１】
なお、ステップ３はＳ５０１やＳ５０２より前にあってもよい。エンコーダは、例えば、符号化すべき予測モードを切り替えながらステップ２〜１１を繰り返し試したうえで、符号化効率が良い予測モードを選択することで、圧縮率を向上させることができる。ただし、デコード可能なビットストリームを出力するために、このような繰り返しは必須ではなく、別の基準で予測モードを決めてもよい。
【００３２】
次に、符号化装置について図６を参照して説明する。  
本実施の形態の符号化装置は、画像入力部６０１、演算ユニット６０２、データ用メモリ６０３、符号化データ出力部６０４、プログラム用メモリ６０５を含む。
【００３３】
画像入力部６０１は画像ブロックを読み込む。演算ユニット６０２は、画像入力部６０１が読み込んだ画像ブロックに対し、データ用メモリ６０３およびプログラム用メモリ６０５を参照して符号化を行う。データ用メモリ６０３は、一時記憶装置であり、例えば現在処理しているフレームの前フレームを一時的に記憶する。データ用メモリ６０３は例えばＲＡＭである。プログラム用メモリ６０５は、符号化のためのプログラムを記憶している。プログラム用メモリ６０５は例えばＲＯＭまたはＲＡＭである。符号化データ出力部６０４は、符号化されたデータをビットストリームに出力する。
【００３４】
（階層的ＣＢＰの冗長性削減、デコーダ）  
以上の方法で生成されたビットストリームを復号化（ブロック単位のＣＢＰの復号化）する方法のフローチャートの一例を図７に、復号化を実行するための装置の一例を図８に示す。コーデットパターンデータの復号化は、例えば、次のステップ１〜１０の方法により行える。
【００３５】
ステップ１．（Ｓ７０１）符号化データ入力部８０１が入力データとしてビットストリームを入力する。ビットストリームは、ブロック単位での予測情報、ブロック単位での予測残差信号の有無を表すコーデットパターンデータ、およびブロック単位での予測残差信号をエントロピー符号化した画像データを含む。
【００３６】
ステップ２．（Ｓ７０２）次に演算ユニット８０２が、取得すべきデータが上位のコーデットパターンデータ（例えば、上位のＣＢＰ）であるかどうかを判定し、上位のコーデットパターンデータであると判定された場合にはステップ３へ、そうでなければステップ４へ飛ぶ。
【００３７】
ステップ３．（Ｓ７０３）演算ユニット８０２が上位のコーデットパターンデータをエントロピー復号により取得する。ステップ９へ飛ぶ。
【００３８】
ステップ４．（Ｓ７０４）次に演算ユニット８０２が、取得すべきデータが上位コーデットパターンデータに属するコーデットパターンデータである下位のコーデットパターンデータ（例えば、下位のＣＢＰあるいは下位のＣＢＦ）であるかどうかを判定し、下位のコーデットパターンデータであると判定された場合にはステップ６へ、そうでなければステップ５へ飛ぶ。
【００３９】
ステップ５．（Ｓ７０５）次に演算ユニット８０２が取得すべき（コーデットパターンデータ以外の）データを取得しステップ９へ飛ぶ。
【００４０】
ステップ６．（Ｓ７０６）演算ユニット８０２が、すでに取得された下位のコーデットパターンデータが予め定められたパターンであるかどうかを判定し、予め定められたパターンである場合にはステップ７へ飛び、そうでなければステップ８へ飛ぶ。例えば、図２の例においては、予め定められたパターンとは、下位のコーデットパターンデータが４ビットであり、かつ、すでに下位のコーデットパターンデータが３ビット取得されていて次に取得すべきデータが４ビット目のコーデットパターンデータであり、かつ、すでに取得された３ビットが０００であるパターンを指す。
【００４１】
ステップ７．（Ｓ７０７）次に演算ユニット８０２が、取得すべき下位のコーデットパターンデータとして、予め定められた固定値を設定し、設定後ステップ９へ飛ぶ。例えば、図２の例では、次に取得すべき４ビット目のコーデットパターンデータとして１を設定する。
【００４２】
ステップ８．（Ｓ７０８）次に演算ユニット８０２が、取得すべき下位のコーデットパターンデータをエントロピー復号により取得する。
【００４３】
ステップ９．（Ｓ７０９）演算ユニット８０２がブロック情報の取得が完了しているかどうかを判定し、取得が完了していればステップ１０へ飛び、そうでなければステップ２へ飛ぶ。ブロック情報は、復号された、ブロック単位での予測情報およびブロック単位での予測残差信号を示す。すなわち、このフローでは明示されていないが、ビットストリームに含まれる情報がブロック単位での予測情報である場合にはビットストリームを復号化しブロック単位での予測情報を得るステップがあり、ビットストリームに含まれる情報がブロック単位での予測残差信号である場合にはビットストリームを復号化しブロック単位での予測残差信号を得るステップがある。
【００４４】
ステップ１０．（Ｓ７１０）演算ユニット８０２が取得されたブロック情報に基づきブロック画像信号を復元し、画像出力部８０４が復元された画像を出力する。
【００４５】
次に、復号化装置について図８を参照して説明する。  
本実施の形態の復号化装置は、符号化データ入力部８０１、演算ユニット８０２、データ用メモリ８０３、画像出力部８０４、プログラム用メモリ８０５を含む。
【００４６】
符号化データ入力部８０１は入力データとしてビットストリームを入力する。演算ユニット８０２は、符号化データ入力部８０１が入力したビットストリームに含まれるブロックを、ブロックの切れ目を判断しながら、データ用メモリ６０３およびプログラム用メモリ６０５を参照して復号化を行う。データ用メモリ８０３は、一時記憶装置であり、例えば符号化データ入力部８０１が入力したビットストリームを一時的に記憶する。プログラム用メモリ８０５は、復号化のためのプログラムを記憶していて、例えば下記図９または図１０に示す擬似プログラムに対応するプログラムを格納している。
【００４７】
次に、下位のコーデットパターンデータが４ビットの階層的ＣＢＰの場合の復号化方法のシンタックスの一例を図９に、下位のコーデットパターンデータがｎｕｍ＿ｌｏｗｅｒ＿ｂｌｏｃｋｓビットの階層的ＣＢＰの場合の復号化方法のシンタックスの一例を図１０に示す。図９、図１０において、ａｅ（ｖ）とされた行はエントロピー復号（例えばＣＡＢＡＣ）により１ビットの情報を取得することを表し、そうでない行はその行を実行することを表す。「（ｕｐｐｅｒ＿ｆｌａｇ  ｉｓ  ａｌｒｅａｄｙ  ｄｅｃｏｄｅｄ）」は、上位のコーデットパターンデータがすでにｕｐｐｅｒ＿ｆｌａｇとして取得されていることを表す。「（ｏｔｈｅｒ  ｄｅｃｏｄｉｎｇ  ｐｒｏｃｅｓｓｅｓ，  ｏｐｔｉｏｎａｌ）」は、もし他のシンタックス処理が必要であれば、そのシンタックス処理を実行することを表す。なお、コーデットパターンデータが特定の組み合わせであるかを判定する条件分岐判定は反転させることが可能である。図９の条件分岐判定を反転させた例を図１１に示す。他の図についても同様である。
【００４８】
（ＣＢＰとＣＢＦ）  
Ｈ．２６４では、４ｘ４画素のブロックに対応したコーデットパターンデータであるｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは、第１のｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇ、第１のｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇが非０の場合には第１の変換係数、第２のｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇ、第２のｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇが非０の場合には第２の変換係数、というように、変換係数とあわせて復号化される。この場合、上位のコーデットパターンデータとして８ｘ８画素のブロックに対応するＣＢＰ、下位のコーデットパターンデータとして８ｘ８画素のブロックを構成する各４ｘ４画素のブロックに対応したＣＢＦを考えると、シンタックスは図１２のように表せる。図１２は、８ｘ８画素のブロックに対応するＣＢＰが非０の場合に、４ｘ４画素ブロックのＣＢＦを復号化する方法の一例を示す。
【００４９】
図１２において、引数ｂｌｏｃｋＩｎｄｅｘは、処理中の４ｘ４画素ブロックがそれを含む８ｘ８画素のブロック内で先頭のブロックを０としたときのインデックスを表し、（ｄｅｃｏｄｅ  ｒｅｓｉｄｕａｌ  ｃｏｅｆｆｉｃｉｅｎｔｓ  ｃｏｅｆｆＬｅｖｅｌ［ｉ］）は変換係数を復号化することを表す。また、最初の４ｘ４画素ブロックを復号化する前に、ｎｏｎｚｅｒｏ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇ＿ｆｏｕｎｄには０を設定しておくものとする。８ｘ８画素のブロックを構成する４ｘ４画素ブロックは４つあるから、ｂｌｏｃｋＩｎｄｅｘが３であり、かつ、他のｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇが０である場合には、ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇを復号化せずに１とすることができる。そうでない場合には、ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇを復号化する必要がある。なお、図１２には含まれていないが、予測モードによっては常にｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇを復号化する必要があるため、図１２の関数を呼び出す前に、常にｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇを復号化する必要があるかを、判定しておく必要がある。常にｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇを復号化する必要がある予測モードとしては、例えば、Ｈ．２６４のＩｎｔｒａ１６ｘ１６予測があげられる。このモードでは、輝度ブロックに対応したＣＢＰの表現として、１６ｘ１６画素ブロックを構成する４つの８ｘ８ブロックに対する４ビットのＣＢＰについて、すべてのビットが０であるかすべてのビットが１であるかの２通りしか用意されていない。この場合、上位のＣＢＰが１かつ下位のＣＢＦがすべて０という符号を用意しておかなければ、１６ｘ１６画素内の任意の８ｘ８画素ブロックにおいて、８ｘ８画素ブロック内のＣＢＦがすべて０になるというコーデットパターンデータを表現できない。したがって、Ｈ．２６４のＩｎｔｒａ１６ｘ１６予測では、常にｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇを復号化する必要がある。
【００５０】
（上位ＣＢＰと下位ＣＢＰ）  
Ｈ．２６４では、上位のコーデットパターンデータを持つブロック（マクロブロック）のサイズは１６ｘ１６画素である。しかし、符号化効率を考えると、例えばマクロブロックのサイズを３２ｘ３２画素や６４ｘ６４画素に拡張するという拡張も考えられる。これを拡張マクロブロックと呼ぶことにする。拡張マクロブロックでは、例えば、３２ｘ３２画素の拡張マクロブロックを構成する１６ｘ１６画素のブロックは、輝度ブロックのみを考えれば４個、輝度ブロック４つに加えてＣｂ、Ｃｒの色差ブロックまで考えれば１２個存在することになる。ＣＢＰは０となることが多く、０のフラグを１２個も符号化することは避けたい。そこでマクロブロックの拡張として、３２ｘ３２画素の拡張マクロブロックを構成するＣＢＰがすべて０であるか、１つ以上の非０のビットを持つＣＢＰであるかというコーデットパターンデータを符号化することが考えられる。この実施例では、３２ｘ３２画素の拡張マクロブロックに対するコーデットパターンデータをｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２と呼ぶことにする。ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２は１ビットのフラグ情報である。さらに大きな拡張マクロブロックとして、６４ｘ６４画素のレベル２拡張マクロブロックを考えるなら、レベル２拡張マクロブロックを構成する３２ｘ３２画素のＣＢＰであるｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２がすべて０であるか、１つ以上の非０のビットを持つＣＢＰであるかを符号化することが考えられる。この実施例では、６４ｘ６４画素の拡張マクロブロックに対するコーデットパターンデータをｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿６４と呼ぶこととし、その６４ｘ６４画素ブロックを構成する４つの３２ｘ３２画素ブロックについては、インデックスを付与してｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２［０］〜ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２［３］と呼ぶことにする。
【００５１】
ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿６４およびｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２をデコードする処理の流れの一例を図１３、別の一例を図１４に示す。双方の図は、上位ブロックのサイズが６４ｘ６４画素、下位ブロックのサイズが３２ｘ３２画素であり、かつ、下位が４ビットの階層的ＣＢＰを復号化する方法の一例を示す。
【００５２】
「（ｏｔｈｅｒ  ｄｅｃｏｄｉｎｇ  ｐｒｏｃｅｓｓｅｓ，  ｏｐｔｉｏｎａｌ）」は、もし他のシンタックス処理が必要であれば、そのシンタックス処理を実行することを表す。図１３は、ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿６４とｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２が符号化されたデータを復号化する場合の一例を表している。図１３では、まずｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿６４を復号化し、それが０でない場合にはｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２の各要素を復号化している。この際、ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２［３］については、ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２［０］〜ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２［２］のうち１つ以上が非０であれば復号化するが、ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２［０］〜ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２［２］のすべてが０である場合にはｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２［３］を１とする。図１４は、図１３におけるｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿６４とｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２が別の関数として表現された場合の一例を表している。図１４において、ｍａｃｒｏｂｌｏｃｋ＿ｃｌｕｓｔｅｒ＿ｒｅｓｉｄｕａｌ＿６４ｘ６４（）は６４ｘ６４画素のレベル２拡張マクロブロックの残差を復号化するための関数であり、ｍａｃｒｏｂｌｏｃｋ＿ｃｌｕｓｔｅｒ＿ｒｅｓｉｄｕａｌ＿３２ｘ３２（）は３２ｘ３２画素の拡張マクロブロックの残差を復号化するための関数である。図１３に対し、図１４では、ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿６４の復号化がｍａｃｒｏｂｌｏｃｋ＿ｃｌｕｓｔｅｒ＿ｒｅｓｉｄｕａｌ＿６４ｘ６４（）で行われ、ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２の各要素の復号化はｍａｃｒｏｂｌｏｃｋ＿ｃｌｕｓｔｅｒ＿ｒｅｓｉｄｕａｌ＿３２ｘ３２（）で行われている点が異なる。ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２［０］〜ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２［２］のすべてが０である場合に、ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｐａｔｔｅｒｎ＿３２［３］を復号化せず固定値１とする点は図１３と同じである。
【００５３】
（階層的ＣＢＰの具体例）  
シンタックスの一例として、１６ｘ１６画素のブロックに対して１ビットの輝度ＣＢＰが符号化および復号化され、輝度ＣＢＰが１の場合にのみ、１６ｘ１６画素のブロック内に属する各ブロックについて、変換係数の有無をＣＢＰとして符号化および復号化される例を、図１５のシンタックスにしたがって説明する。図１５は、１６ｘ１６の画素ブロックに対する１ビットの輝度ＣＢＰが与えられた場合に、４ｘ４、８ｘ８、１６ｘ８、８ｘ１６、１６ｘ１６の変換についてのｃｂｐを得るシンタックスの一例を示す。
【００５４】
変換のサイズとして、４ｘ４、８ｘ８、１６ｘ８、８ｘ１６、１６ｘ１６の５通りを考える。変換タイプ「ｃｕｒ＿ｔｒａｎｓｆｏｒｍ＿ｔｙｐｅ」は、４ｘ４に対応する０、８ｘ８に対応する１、１６ｘ８／８ｘ１６／１６ｘ１６のいずれかに対応する２の３値を取るものとする。「ｃｕｒ＿ｔｒａｎｓｆｏｒｍ＿ｔｙｐｅ」が２の場合、変換サイズは、予測ブロックのサイズが１６ｘ８であれば１６ｘ８、８ｘ１６であれば８ｘ１６、それ以外であれば１６ｘ１６とする。変換サイズが４ｘ４および８ｘ８の場合には、４つの８ｘ８ブロックに対する４ビットのＣＢＰが必要である。変換サイズが１６ｘ８および８ｘ１６の場合には、それぞれ、２つの１６ｘ８ブロックおよび２つの８ｘ１６ブロックに対する２ビットのＣＢＰが必要である。変換サイズが１６ｘ１６の場合には、１ビットのＣＢＰが必要である。
【００５５】
この場合、図１５に示すように、ｃｕｒ＿ｔｒａｎｓｆｏｒｍ＿ｔｙｐｅが０または１の場合には図２に対応した読み込みを行い、ｃｕｒ＿ｔｒａｎｓｆｏｒｍ＿ｔｙｐｅが２かつ変換サイズが１６ｘ８／８ｘ１６の場合には図４に対応した読み込みを行い、ｃｕｒ＿ｔｒａｎｓｆｏｒｍ＿ｔｙｐｅが２かつ変換サイズが１６ｘ１６の場合には与えられたＣＢＰをそのまま利用することで、本発明を利用できることになる。なお、図１５において、「ｃｂｐ＿ｌｕｍａ＿１ｂｉｔ」は１ビットの輝度ＣＢＰを表し、「ＭｂＰａｒｔＷｉｄｔｈ（ｍｂ＿ｔｙｐｅ）」および「ＭｂＰａｒｔＨｅｉｇｈｔ（ｍｂ＿ｔｙｐｅ）」は予測ブロックのサイズを表し、ｃｂｐは１６ｘ１６輝度ブロックを４つの８ｘ８ブロックに分割した場合の、各８ｘ８輝度ブロックに対応した４ビットのｃｂｐを表す。図１５のシンタックスでは、１６ｘ８／８ｘ１６／１６ｘ１６の場合について、ｃｂｐを８ｘ８ブロックにあわせて４ビットとしているが、これらの場合にｃｂｐを８ｘ８ブロックにあわせる必要はなく、それぞれ２ビット、２ビット、１ビットのｃｂｐとして読み込んでもよい。
【００５６】
（四分木分割による再帰構造をもった階層ブロックにおけるＣＢＦ符号化）  
本実施形態の変更例として、Ｈ．２６４のブロック構造をＭｘＭサイズ（Ｍは２のべき乗）のブロックに階層的に分割することを考える。この際、上位ブロックサイズを２Ｎｘ２Ｎ、下位ブロックサイズをＮｘＮ（Ｎは２のべき乗）で表現する。図２０Ａ、図２０Ｂに２Ｎｘ２ＮサイズとＮｘＮサイズの符号化ブロックを示す。上位ブロックサイズを分割する際には、分割を示す１ビットのフラグを用いて分割の有無を表現する。ＣＢＦについても同様に、上位ブロックに上位ＣＢＦが存在し、下記ブロックには０から３で示される４つのＮｘＮブロック毎に４つの下位ＣＢＦが存在する。ここで上位ＣＢＦが１で有りかつ下位ＣＢＦが全て０の場合は、上位ＣＢＦが０である場合と同じ表現となるため冗長である。このようなＣＢＦの符号化を考えた場合、上位ＣＢＦは、上位ブロックを分割するかどうかを示す情報と等価となる。
【００５７】
ＮｘＮを更に分割する場合においても、上記関係を用いて再帰的に表現することが可能である。例えば、上位ブロックと下位ブロックを再帰的に組み合わせた時の階層的な四分木分割の一例を図２０Ｃに示す。図２０Ｂでは下位ブロックとなっていたブロック２が、図２０Ｃでは更に四分木分割されている。この場合、図２０Ｃのブロック２には上位ブロックとしてのＣＢＦが存在するとともに、ブロック２を四分木分割しているので下位ブロックの４つのＣＢＦも存在することになる。ここでは、ブロック２の下位ブロックの番号を０’、１’、２’、３’として上位ブロックと区別している。
【００５８】
つまり、上位ブロックと下位ブロックの構成は、階層の深さによって変化する。例えば、階層の深さ（ｌａｙｅｒ）で表現される上位ブロックは、（ｌａｙｅｒ＋１）の階層では４つの下位ブロックを持つことになる。同様に（ｌａｙｅｒ＋１）の階層で表現される上位ブロックは、（ｌａｙｅｒ＋２）の階層では４つの下位ブロックを持つことになる。ＣＢＦについても同様の階層化による四分木分割が可能である。
【００５９】
このような階層的なブロック分割に対応するシンタクスの一例として、階層構造を再帰的に表現したときのＣＢＦの関係を図２１に示す。図中に示されるｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）は、図中太字で表されている、上位ブロックの非０の変換係数の有無を表すｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇと、下位ブロックの非０の変換係数の有無を表すｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇを符号化するシンタクス構造を示している。図中のｃｕｒｒＢｌｏｃｋＰｏｓは、当該ブロックの位置を示す情報であり、ｌａｙｅｒは、階層構造の深さを示す。例えば、ｃｕｒｒＢｌｏｃｋＰｏｓ０は図２０Ｂにおけるブロック０を示し、ｃｕｒｒＢｌｏｃｋＰｏｓ３は図２０Ｂにおけるブロック３を示している。ｌａｙｅｒの一例として、図２０Ａで２Ｎｘ２Ｎサイズが６４ｘ６４の例を示すと、ＮｘＮサイズは３２ｘ３２となり、ｌａｙｅｒは１となる。更にＮｘＮを分割する場合、Ｎ／２ｘＮ／２サイズは１６ｘ１６となり、ｌａｙｅｒは２となる。
【００６０】
ｃｕｒｒＬｏｗｅｒＡｖａｉｌａｂｌｅは、当該ブロックが下位ＣＢＦを保持することができるかどうかを示す内部変数である。言い換えれば、当該ブロックが、分割可能かどうかを示している。例えば、予め定めた最小分割ブロックサイズよりも当該ブロックを分割したときのブロックサイズが小さくなる場合、下位ＣＢＦを持つことができないためｃｕｒｒＬｏｗｅｒＡｖａｉｌａｂｌｅは０となる。一方、当該ブロックを更に分割することが可能である場合ｃｕｒｒＬｏｗｅｒＡｖａｉｌａｂｌｅは１となる。
【００６１】
ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは、上位ブロックの非０の変換係数の有無を示すフラグであり、言い換えれば上位ブロックを分割するかどうかを表している。分割する場合は１、分割しない場合は０となる。ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇが１である場合、上位ブロックに非０の変換係数が存在するため、更に下位ＣＢＦを持つことが可能となる。関数ｃａｌｃｕｌａｔｅＢｌｏｃｋＰｏｓ（）は、当該ブロックを四分木分割した際、ｉ（ｉは０から最大３まで）で示される分割後のブロックの位置を返す関数である。ｃｕｒｒＢｌｏｃｋＰｏｓ０から３は、最大４つまでの分割後のブロックの位置を示す。
【００６２】
ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは、下位ブロックの非０の変換係数の有無を示すシンタクス要素であり、当該下位ブロックに非０の変換係数が存在する場合は１を、存在しない場合は０となる。ｃｏｄｅｄＢｌｏｃｋＦｌａｇは階層構造毎にｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇを保持する内部変数であり、下位ブロックに該当する当該ブロックからｌａｙｅｒが０で示される上位ブロックまでのｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇが保持されている。
【００６３】
ｒｅｓｉｄｕａｌ＿ｂｌｏｃｋ（）は、ＣＢＦ以外の変換係数に関連する情報を符号化する関数である。なお、本関数は非０の変換係数が存在する時だけ（ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇが１のときだけ）呼び出される。更に、本関数はｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）以外の関数で呼び出される構成としてもよい。
【００６４】
図２１で示される再帰構造を持ったシンタクス構造を考えた場合、上位ＣＢＰが１である場合に、下位のＣＢＰ（４ｘ４画素の場合はＣＢＦ）がすべて０であるという冗長な組み合わせが存在する。
【００６５】
（四分木分割による再帰構造をもった階層ブロックにおけるＣＢＦの冗長度削減）  
図２１で説明した再帰構造を持つＣＢＦのシンタクス構造時にも発生する下位ＣＢＦの冗長性を削減したシンタクス構造の一例が図２２に示されている。図２２では、ｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）関数に、ＤｅｃｏｄｅｄＳｋｉｐＦｌａｇが引数として追加されている。ＤｅｃｏｄｅｄＳｋｉｐＦｌａｇは、当該ブロックにおいてｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇを符号化又は復号するかどうかを示す1ビットの内部変数である。上位ＣＢＦが存在した場合（上位ブロックのｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇが１の場合）で且つ、４つの下位ＣＢＦの内の最初の３つのｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇが全て０である場合、ＤｅｃｏｄｅｄＳｋｉｐＦｌａｇが１となる。そうでない場合は、ＤｅｃｏｄｅｄＳｋｉｐＦｌａｇは０に設定される。
【００６６】
逆にいえば、ＤｅｃｏｄｅｄＳｋｉｐＦｌａｇが１の場合、下位ブロックの最初から３番目までのＣＢＦが０であるため、４番目に相当する下位ブロックのＣＢＦ（ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇ）は自動的に１に設定される。ここでは、最初の３つのｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇが全て０である場合を説明したが、符号化及び復号の際に最後に処理されるブロック以外が全て０である場合にＤｅｃｏｄｅｄＳｋｉｐＦｌａｇが１とすることも容易に実現可能である。このようなシンタクス構造をもつことで、四分木分割されたシンタクス構造における下位ＣＢＦの冗長性を削減することが可能となる。
【００６７】
（シンタクス要素の分割）  
なお、本実施の形態に関わるシンタクス要素のｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇとｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇを別々の関数として分けることも可能である。この例が図２３Ａ及び図２３Ｂに記述されている。
【００６８】
図２３Ａでは、ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇのみを再帰的に符号化するシンタクス構造である。図中に示される(・・・)は、ＣＢＦ以外の様々なシンタクス要素、関数が記述されてもよいことを意味している。ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇが０となる場合に、ｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ＿ｔｒｅｅ（）関数が呼ばれる。一方、図２３Ｂにｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ＿ｔｒｅｅ（）関数が示されている。ｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ＿ｔｒｅｅ（）関数は、ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇのみを符号化する関数である。以上のように上位ブロックと下位ブロックを分割しても、分割しない図２２と同一の機能を実現できる。
【００６９】
（ＣＢＦ符号化例１：冗長度有り）  
図２０Ｂの場合で、４つの下位ブロックと上位ブロックのＣＢＦの符号長を図２１のシンタクスに従って算出した場合の符号量は、図３で示されている。下位ＣＢＦの組み合わせ（ｌｏｗｅｒ＿ｃｏｄｅｓ）が０００１の場合に、符号化データは０００１となり、４ビットが必要となる。これに対し、図２２のシンタクスに従って算出した場合の符号量は、図２で示されている。下位ＣＢＦ（ｌｏｗｅｒ＿ｃｏｄｅｓ）が０００１の場合には最後の１ビットを符号せず、符号化データを０００とする。これにより、冗長な最後の1ビットの符号量を削減できる。
【００７０】
次に図２０Ｂの場合に、図２１のシンタクス構造を用いてＣＢＦを符号化・復号化した場合の、各ブロックの符号長を図２４Ａに示す。本図を用いて符号化・復号化の流れを説明する。ここで、図２０Ｂでは、ブロック３のみが非０の変換係数を有し、それ以外のブロックは非０の変換係数を持たない場合を考える。
【００７１】
先ず、図２０Ａの２Ｎｘ２Ｎの上位ブロック０”に対してｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）が呼ばれる。ここで上位ブロックは４つの下位ブロックに分割されているため、ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは１として符号化される。次に図２０Ｂのブロック０に対してｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）が呼び出される。ここでＮｘＮのブロック０は下位ブロックに分割されていないため、ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。更に当該ブロックは非ゼロの変換係数を持たないため、ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。
【００７２】
次にブロック１に対してｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）が呼び出される。ここでＮｘＮのブロック１は下位ブロックに分割されていないため、ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。更に当該ブロックは非ゼロの変換係数を持たないため、ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。ブロック２についても同様の符号化・復号化処理が施される。最後にブロック３に対してｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）が呼び出される。ここでＮｘＮのブロック３は下位ブロックに分割されていないため、ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。当該ブロックは非ゼロの変換係数を持つため、ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは１として符号化・復号化される。
【００７３】
以上の処理を経て、符号化・復号化されたＣＢＦの情報は５ビットのｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇと４ビットのｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇとなり９ビットの符号長となる。
【００７４】
（ＣＢＦ符号化例１：冗長度削減手法）  
次に図２０Ｂの場合に、図２２のシンタクス構造を用いてＣＢＦを符号化・復号化した場合の、各ブロックの符号長を図２４Ｂに示す。本図を用いて符号化・復号化の流れを説明する。ここでは、先ほどと同様に、ブロック３のみが非０の変換係数を有し、それ以外のブロックは非０の変換係数を持たない場合を考える。
【００７５】
ブロック０”及びブロック０からブロック２までは前述と同一の処理が施される。なお、このとき、ＤｅｃｏｄｅＳｋｉｐＦｌａｇは０である。最後にブロック３に対してｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）が呼び出される。ここで、ブロック０、ブロック１、ブロック２の３つの下位ブロックのＣＢＦが全て０となるため、ＤｅｃｏｄｅＳｋｉｐＦｌａｇが１に設定される。ブロック３は下位ブロックに分割されていないため、ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。ＤｅｃｏｄｅＳｋｉｐＦｌａｇが１であるため、ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは符号化・復号化されず、内部的に１が設定される。
【００７６】
以上の処理を経て、符号化・復号化されたＣＢＦの情報は５ビットのｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇと３ビットのｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇとなり８ビットの符号長となる。これにより、１ビットの無駄な符号を削減できる。
【００７７】
（ＣＢＦ符号化例２：冗長度有り）  
次に図２０Ｃの場合に、図２１のシンタクス構造を用いてＣＢＦを符号化・復号化した場合の、各ブロックの符号長を図２４Ｃに示す。本図を用いて符号化・復号化の流れを説明する。ここで、図２０Ｃでは、ブロック３’のみが非０の変換係数を有し、それ以外のブロックは非０の変換係数を持たない場合を考える。
【００７８】
ブロック０”、ブロック０及びブロック１は、図２４Ａの説明と同一の処理が施される。続いてブロック２に対してｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）が呼び出される。ここでブロック２は４つの下位ブロックに分割されているため、ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは１として符号化・復号化される。続いてブロック２の下位ブロックであるブロック０’に対してｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）が呼び出される。ここでＮ／２ｘＮ／２のブロック０’は下位ブロックに分割されていないため、ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。更に当該ブロックは非ゼロの変換係数を持たないため、ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。
【００７９】
次にブロック１’に対してｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）が呼び出される。ここでＮ／２ｘＮ／２のブロック１’は下位ブロックに分割されていないため、ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。更に当該ブロックは非ゼロの変換係数を持たないため、ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。ブロック２’についても同様の符号化・復号化処理が施される。続いてブロック３’に対してｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）が呼び出される。ここでＮ／２ｘＮ／２のブロック３’は下位ブロックに分割されていないため、ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。当該ブロックは非ゼロの変換係数を持つため、ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは１として符号化・復号化される。
【００８０】
引き続き、ブロック３に対してｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）が呼び出される。ここでＮｘＮのブロック３は下位ブロックに分割されていないため、ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。更に当該ブロックは非ゼロの変換係数を持たないため、ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。
【００８１】
以上の処理を経て、符号化・復号化されたＣＢＦの情報は９ビットのｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇと７ビットのｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇとなり１６ビットの符号長となる。
【００８２】
（ＣＢＦ符号化例２：冗長度削減手法）  
次に図２０Ｃの場合に、図２２のシンタクス構造を用いてＣＢＦを符号化・復号化した場合の、各ブロックの符号長を図２４Ｄに示す。本図を用いて符号化・復号化の流れを説明する。ここでは、先ほどと同様に、ブロック３’のみが非０の変換係数を有し、それ以外のブロックは非０の変換係数を持たない場合を考える。
【００８３】
ブロック０”、ブロック０からブロック１、及びブロック０’からブロック２’までは前述と同一の処理が施される。なお、このとき、ＤｅｃｏｄｅＳｋｉｐＦｌａｇは０である。続いてブロック３’に対してｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）が呼び出される。ここで、ブロック０’、ブロック１’、ブロック２’の３つの下位ブロックのＣＢＦが全て０となるため、ＤｅｃｏｄｅＳｋｉｐＦｌａｇが１に設定される。ブロック３’は下位ブロックに分割されていないため、ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。更にＤｅｃｏｄｅＳｋｉｐＦｌａｇが１であるため、ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは符号化・復号化されず、内部的に１が設定される。
【００８４】
引き続き、ブロック３に対してｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）が呼び出される。ここでＮｘＮのブロック３は下位ブロックに分割されていないため、ｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。更に当該ブロックは非ゼロの変換係数を持たないため、ｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇは０として符号化・復号化される。
【００８５】
以上の処理を経て、符号化・復号化されたＣＢＦの情報は９ビットのｕｐｐｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇと６ビットのｌｏｗｅｒ＿ｃｏｄｅｄ＿ｂｌｏｃｋ＿ｆｌａｇとなり１５ビットの符号長となる。これにより、１ビットの無駄な符号を削減できる。
【００８６】
（図２２に準じた符号化フローチャート）  
図２２のシンタクス構造に基づいて、本実施の形態を図５のフローチャート及び図６の符号化装置に沿って説明する。コーデットパターンデータの符号化は、例えば、次の方法により行える。なお、以下の説明では、コーデットパターンデータ以外の部分の符号化であるステップ３、ステップ１１も含めて説明する。
【００８７】
ステップ１．（Ｓ５０１）画像入力部６０１が画像ブロックを読み込む。ここで読み込むブロックは、典型的には、ステップ５における上位コーデットパターンデータに対応したブロックと同じか、それより大きなサイズ（例えば、６４ｘ６４画素）を持つものとする。
【００８８】
ステップ２．（Ｓ５０２）演算ユニット６０２がＳ５０１で読みこんだブロックに対して符号化すべき予測モードをプログラム用メモリ６０５から読み込む。なお、この予測モードは予め決めておく場合もあるし、複数の予測モードのそれぞれでステップＳ５０３以降を行い最も良いモードを選択する場合もある。他にも予測モードを設定する変形例はたくさんある。
【００８９】
ステップ３．演算ユニット６０２は予測モードを符号化して、符号化データ出力部６０４はビットストリームに出力する。
【００９０】
ステップ４．（Ｓ５０３）演算ユニット６０２は予測モードとすでに復号可能となったデータを利用してブロック予測を行い、入力画像ブロックと予測画像ブロックの差である予測残差を求める。
【００９１】
ステップ５．（Ｓ５０４）演算ユニット６０２は、予測残差にブロック変換（例えば、あらかじめトレーニングデータにより生成したＫＬＴの基底や、ＤＣＴの基底を利用した直交変換）および量子化を施す。ここで変換を行うブロックは、ステップ１のブロックよりも小さなサイズ（例えば、４ｘ４画素）を持つものとする。次に、演算ユニット６０２は量子化された変換係数の中に非０の係数が存在するか否かをあらわす情報をブロック単位で算出する。典型的には、この情報は、ブロック内に非０の係数が存在する場合には１、ブロック内の係数がすべて０の場合には０という、ブロックごとに１ビットのフラグ情報になる。この情報を下位のコーデットパターンデータ（下位ＣＢＰやＣＢＦ）と呼ぶ。次に、下位のコーデットパターンデータの集合（例えば、４つの下位のコーデットパターンデータ）がすべて０か否かという情報を表す、より大きなブロックに対するコーデットパターンデータである上位のコーデットパターンデータ（上位ＣＢＰ）を求める。典型的には、上位のコーデットパターンデータは、下位のコーデットパターンデータがすべて０であれば０、下位のコーデットパターンデータに１つでも非０の情報があれば１という、ブロックごとに１ビットのフラグ情報になる。ここで、上位コーデットパターンデータに対応するブロックのサイズは、下位コーデットパターンデータよりも大きなサイズ（例えば８ｘ８画素）を持つものとする。この処理を階層的に行って最下位のＣＢＰから最上位のＣＢＰまでを設定する。例えば最下位のブロックを４ｘ４画素、最上位のブロックを６４ｘ６４画素とした場合、階層の深さが０（６４ｘ６４画素ブロック）から５（４ｘ４画素ブロック）までで表現される。
【００９２】
ステップ６．（Ｓ５０５）演算ユニット６０２が上位のコーデットパターンデータを符号化して、符号化データ出力部６０４がビットストリームに出力する。
【００９３】
ステップ７．（Ｓ５０６）演算ユニット６０２は、上位のコーデットパターンデータが０である場合にはステップ８〜１０を飛ばし、そうでないのならステップ８を実行する。
【００９４】
ステップ８．（Ｓ５０７）ステップ８〜１０は下位のコーデットパターンデータを１ビットずつ符号化していく過程である。このステップでは次の条件分岐を実行する。演算ユニット６０２は、すでに符号化された下位のコーデットパターンデータが特定のパターンデータである場合（典型的には、最後の１ビットの下位のコーデットパターンデータを符号化する場合であって、かつ、符号化済みの下位のコーデットパターンデータがすべて０である場合）には、次のビットストリームに出力するステップ９を飛ばし、そうでなければステップ９を実行する。
【００９５】
ステップ９．（Ｓ５０８）次に、演算ユニット６０２は符号化すべき下位のコーデットパターンデータを符号化して、符号化データ出力部６０４はビットストリームに出力する。
【００９６】
ステップ１０．（Ｓ５０９）演算ユニット６０２は、下位のコーデットパターンデータをすべて符号化していればステップ１１に進め、そうでなければステップ８に戻る。Ｓ５０７からＳ５０９のループはビット数に応じて回る回数が決まり、例えば４ビットであれば４回だけ回すことになる。また、このステップ７〜１０は、上位ブロックが分割されなくなるまで（ステップ１０の判定がＹｅｓになるまで）、階層に応じて再帰的に繰り返される。
【００９７】
ステップ１１．符号化データ出力部６０４は、コーデットパターンデータが非０のブロックについて、量子化された変換係数を符号化してビットストリームに出力する。
【００９８】
なお、ステップ３はＳ５０１やＳ５０２より前にあってもよい。エンコーダは、例えば、符号化すべき予測モードを切り替えながらステップ２〜１１を繰り返し試したうえで、符号化効率が良い予測モードを選択することで、圧縮率を向上させることができる。ただし、デコード可能なビットストリームを出力するために、このような繰り返しは必須ではなく、別の基準で予測モードを決めてもよい。
【００９９】
（図２２に準じた復号フローチャート）  
次に本実施の形態で説明した図２２のシンタクス構造を図７のフローチャート及び図８の復号装置に沿って説明する。
【０１００】
以上の方法で生成されたビットストリームを復号化（ブロック単位のＣＢＰの復号化）する方法のフローチャートの一例を図７に、復号化を実行するための装置の一例を図８に示す。コーデットパターンデータの復号化は、例えば、次のステップ１〜１０の方法により行える。
【０１０１】
ステップ１．（Ｓ７０１）符号化データ入力部８０１が入力データとしてビットストリームを入力する。ビットストリームは、ブロック単位での予測情報、ブロック単位での予測残差信号の有無を表すコーデットパターンデータ、およびブロック単位での予測残差信号をエントロピー符号化した画像データを含む。
【０１０２】
ステップ２．（Ｓ７０２）次に演算ユニット８０２が、取得すべきデータが上位のコーデットパターンデータ（例えば、上位のＣＢＰ）であるかどうかを判定し、上位のコーデットパターンデータであると判定された場合にはステップ３へ、そうでなければステップ４へ飛ぶ。
【０１０３】
ステップ３．（Ｓ７０３）演算ユニット８０２が上位のコーデットパターンデータをエントロピー復号により取得する。ステップ９へ飛ぶ。
【０１０４】
ステップ４．（Ｓ７０４）次に演算ユニット８０２が、取得すべきデータが上位コーデットパターンデータに属するコーデットパターンデータである下位のコーデットパターンデータ（例えば、下位のＣＢＰあるいは下位のＣＢＦ）であるかどうかを判定し、下位のコーデットパターンデータであると判定された場合にはステップ６へ、そうでなければステップ５へ飛ぶ。
【０１０５】
ステップ５．（Ｓ７０５）次に演算ユニット８０２が取得すべき（コーデットパターンデータ以外の）データを取得しステップ９へ飛ぶ。
【０１０６】
ステップ６．（Ｓ７０６）演算ユニット８０２が、すでに取得された下位のコーデットパターンデータが予め定められたパターンであるかどうかを判定し、予め定められたパターンである場合にはステップ７へ飛び、そうでなければステップ８へ飛ぶ。例えば、図２の例においては、予め定められたパターンとは、下位のコーデットパターンデータが４ビットであり、かつ、すでに下位のコーデットパターンデータが３ビット取得されていて次に取得すべきデータが４ビット目のコーデットパターンデータであり、かつ、すでに取得された３ビットが０００であるパターンを指す。
【０１０７】
ステップ７．（Ｓ７０７）次に演算ユニット８０２が、取得すべき下位のコーデットパターンデータとして、予め定められた固定値を設定し、設定後ステップ９へ飛ぶ。例えば、図２の例では、次に取得すべき４ビット目のコーデットパターンデータとして１を設定する。
【０１０８】
ステップ８．（Ｓ７０８）次に演算ユニット８０２が、取得すべき下位のコーデットパターンデータをエントロピー復号により取得する。
【０１０９】
ステップ９．（Ｓ７０９）演算ユニット８０２がブロック情報の取得が完了しているかどうかを判定し、取得が完了していればステップ１０へ飛び、そうでなければステップ２へ飛ぶ。ブロック情報は、復号された、ブロック単位での予測情報およびブロック単位での予測残差信号を示す。すなわち、このフローでは明示されていないが、ビットストリームに含まれる情報がブロック単位での予測情報である場合にはビットストリームを復号化しブロック単位での予測情報を得るステップがあり、ビットストリームに含まれる情報がブロック単位での予測残差信号である場合にはビットストリームを復号化しブロック単位での予測残差信号を得るステップがある。
【０１１０】
ステップ１０．（Ｓ７１０）演算ユニット８０２が取得されたブロック情報に基づきブロック画像信号を復元し、画像出力部８０４が復元された画像を出力する。
【０１１１】
このステップ２〜９は、上位ブロックが分割されなくなるまで（ステップ９の判定がＹｅｓになるまで）、階層に応じて再帰的に繰り返される。
【０１１２】
本実施の形態に関わる復号化装置については図８と同一の構成であるため、説明を省略する。
【０１１３】
（ダイレクトモード）  
Ｈ．２６４の多くのフレーム間符号化モードでは、すでに復号化した情報から求められる動き予測に対する動きの予測誤差、および予測で得られたブロックと画像ブロックとの予測残差の２つの情報を符号化および復号化する。しかし、動きの予測誤差を符号化および復号化せず予測残差のみを符号化および復号化するダイレクトモード、すでに復号化した情報から求められる動き予測のみを利用したスキップモードという２つの特殊なモードが用意されている。なお、Ｈ．２６４ではＢスライスと呼ばれるデータに対してのみダイレクトモードが用意されているが、Ｐスライスと呼ばれるデータについても同じ定義でのダイレクトモードが実現できるため、本実施の形態ではスライスの種類については特に限定しない。
【０１１４】
スキップモードとダイレクトモードという２つのモードを比較すると、スキップモードはダイレクトモードの予測残差が存在しないモードであると考えられる。Ｈ．２６４では予測残差が存在しないダイレクトモードを符号化することも可能であるが、そのような場合にはスキップモードで符号化し、復号化時にダイレクトモードでは常に予測残差が存在すると解釈してもよく、予測残差が存在しないダイレクトモードは冗長なモードであることがわかる。したがって、拡張マクロブロックにおける階層的なコーデットブロックデータをデコードする際には、ダイレクトモードとして符号化されたブロックと同一サイズのコーデットブロックデータに限り、コーデットブロックデータをエントロピー復号化により取得せずに、予測残差の存在を表す固定値（１）を設定できる。換言すれば、ブロック単位での予測情報がダイレクトモードである場合に、上位コーデットパターンデータを前記ビットストリームから復号化せずに予め定めた値を設定する。なお、ダイレクトモードにおける下位のブロック（例えば、６４ｘ６４画素のレベル２拡張マクロブロックでダイレクトモードと記録されている場合にそのブロックを構成する４つの３２ｘ３２画素の拡張マクロブロック）については、予測残差の存在の有無は不明であって、コーデットブロックデータを符号化および復号化する必要がある。
【０１１５】
（スキップフラグ）  
今までの説明ではコーデットブロックデータの無駄を減らす手段について述べてきた。同じ手段で、スキップモードをあらわすスキップフラグについても冗長な情報を減らすことができる。スキップモードは、ブロックがスキップである場合に１、そうでない場合に０となるフラグである。スキップ予測が可能なブロックのサイズとして２種以上のサイズが用意されている場合には、スキップフラグを階層的に符号化する必要がある。この場合、図１６（単純な階層的スキップフラグの一例）のように実装することになるが、これは今まで述べてきたＣＢＰとＣＢＦの例を論理反転させた表になっており、従来のコーデットブロックデータが冗長であった理由と同じ理由で冗長である。したがって、図１７（本実施の形態の階層的スキップフラグの一例）に示すように、下位のスキップフラグとして４つのフラグが符号化および復号化される場合、上位のスキップフラグが０、下位のスキップフラグのうち第１、第２、第３のスキップフラグが１であるなら、第４の下位のスキップフラグを符号化および復号化せずに、０という固定値を利用できる。
【０１１６】
階層的なスキップフラグを符号化する方法の流れを表す図を図２８に示す。符号化は、次の流れで行われる。
【０１１７】
ステップ１．（Ｓ２８０１）画像入力部６０１が画像ブロックを読み込む。
【０１１８】
ステップ２．（Ｓ２８０２）演算ユニット６０２がＳ５０１で読みこんだブロックに対して符号化すべき予測モードをプログラム用メモリ６０５から読み込む。予測モードは、スキップフラグ（Ｓｋｉｐ）の情報を含む。なお、この予測モードは予め決めておく場合もあるし、複数の予測モードのそれぞれでステップＳ５０３以降を行い最も良いモードを選択する場合もある。他にも予測モードを設定する変形例はたくさんある。
【０１１９】
ステップ３．（Ｓ２８０３）演算ユニット６０２は上位のスキップフラグを符号化して、符号化データ出力部６０４はビットストリームに出力する。
【０１２０】
ステップ４．（Ｓ２８０４）このステップは次の条件分岐を実行する。演算ユニット６０２は、上位のスキップフラグが１であれば、ステップ５〜９を飛ばす。そうでなければステップ５を実行する。
【０１２１】
ステップ５．（Ｓ２８０５）演算ユニット６０２は、スキップフラグ以外の、上位の予測モードを符号化して、符号化データ出力部６０４からビットストリームに出力する。
【０１２２】
ステップ６．（Ｓ２８０６）ステップ６〜８は下位のスキップフラグのうち１ビットを符号化する過程である。このステップでは次の条件分岐を実行する。演算ユニット６０２は、すでに符号化された下位のスキップフラグが特定のパターンデータである場合（典型的には、最後の１ビットの下位のスキップフラグを符号化する場合であって、かつ、符号化済みの下位のスキップフラグがすべて１である場合）には、次のビットストリームに出力するステップ７を飛ばし、そうでなければステップ７を実行する。
【０１２３】
ステップ７．（Ｓ２８０７）演算ユニット６０２は符号化すべき下位のスキップフラグを符号化して、符号化データ出力部６０４からビットストリームに出力する。
【０１２４】
ステップ８．（Ｓ２８０８）演算ユニット６０２は、スキップフラグ以外の、下位の予測モードを符号化して、符号化データ出力部６０４からビットストリームに出力する。また、演算ユニット６０２は、残差情報があるなら、残差情報を符号化して、符号化データ出力部６０４からビットストリームに出力する。
【０１２５】
ステップ９．（Ｓ２８０９）演算ユニット６０２は、（下位のスキップフラグを含めた）下位のブロックをすべて符号化していればブロックの符号化を終了する。そうでなければ、次の下位のブロックを符号化するために、ステップ６に戻る。Ｓ２８０６からＳ２８０９のループは上位のブロックに属する下位のブロックの数に応じて回る回数が決まり、例えば下位のブロックが４つに分割されているなら４回だけ回すことになる。
【０１２６】
エンコーダは、例えば、符号化すべき予測モードを切り替えながらステップ２〜９を繰り返し試したうえで、符号化効率が良い予測モードを選択することで、圧縮率を向上させることができる。ただし、デコード可能なビットストリームを出力するために、このような繰り返しは必須ではなく、別の基準で予測モードを決めてもよい。
【０１２７】
階層的なスキップフラグの復号化の流れは図７とほとんど同じである。図７に対応する、ブロック単位のスキップフラグの復号化の流れの一例を図１８に示す。図１８の流れは、Ｓ７０２〜Ｓ７０８におけるＣＢＰが、Ｓ１８０２〜Ｓ１８０８におけるスキップフラグ（図１８ではｓｋｉｐと表記）に置き換わる点が図７と異なる。対応するシンタックスは、例えば、図１９のようになる。図１９は、階層的なスキップフラグに対する本実施の形態を利用したフラグ削減の一例である。
【０１２８】
（四分木分割による再帰構造をもった階層ブロックにおけるスキップフラグ符号化）  
図２０Ａから図２０Ｃまでで説明したような四分木分割による再帰構造においても、前述の通り、スキップフラグ或いはダイレクトモードの冗長度を削減可能である。図２５にこの場合のシンタクス構造の一例を示す。図２５に示されるｃｏｄｉｎｇ＿ｕｎｉｔ（）は、予測モードなどに関連する情報を符号化する関数である。本関数の基本構造は、図２２とほぼ同じである。上位ブロックのスキップフラグをｕｐｐｅｒ＿ｓｋｉｐ＿ｆｌａｇ、４つの下位ブロックのスキップフラグをｌｏｗｅｒ＿ｓｋｉｐ＿ｆｌａｇと表現している。ここで、図２２の説明時と同様、上位スキップフラグは、当該ブロックを分割するかどうかを示す情報と等価である。ｃｕｒｒＬｏｗｅｒＡｖａｉｌａｂｌｅは、当該ブロックを分割することが可能かどうかを示す内部変数である。例えば、予め定めた最小分割ブロックサイズよりも当該ブロックを分割したときのブロックサイズが小さくなる場合、下位ブロックがスキップモードを取ることができないためｃｕｒｒＬｏｗｅｒＡｖａｉｌａｂｌｅは０となる。一方、当該ブロックを更に分割することが可能である場合ｃｕｒｒＬｏｗｅｒＡｖａｉｌａｂｌｅは１となる。
【０１２９】
ｕｐｐｅｒ＿ｓｋｉｐ＿ｆｌａｇは、上位ブロックがスキップモードかどうかを示すフラグであり、言い換えれば上位ブロックを分割するかどうかを表している。分割する場合は１、分割しない場合は０となる。
【０１３０】
ＡｖａｉｌａｂｌｅＳｋｉｐは、当該ブロックがスキップモードを選択できるかどうかを示す1ビットの内部変数である。当該スライスがイントラ予測のみで構成されるＩ−ｓｌｉｃｅである場合に、スキップモードのフラグを符号化することは無駄であり、符号量増に繋がるため、上記場合ＡｖａｉｌａｂｌｅＳｋｉｐは０に設定される。それ以外の場合には１に設定される。つまり、ＤｅｃｏｄｅｄＳｋｉｐＦｌａｇが０且つＡｖａｉｌａｂｌｅＳｋｉｐが１の場合のみｌｏｗｅｒ＿ｓｋｉｐ＿ｆｌａｇが符号化される。
【０１３１】
ＤｅｃｏｄｅｄＳｋｉｐＦｌａｇは、当該ブロックにおいてｌｏｗｅｒ＿ｓｋｉｐ＿ｆｌａｇを符号化又は復号するかどうかを示す1ビットの内部変数である。上位スキップフラグが存在した場合（上位ブロックのｕｐｐｅｒ＿ｓｋｉｐ＿ｆｌａｇが１の場合）で且つ、４つの下位スキップフラグの内の最初の３つのｌｏｗｅｒ＿ｓｋｉｐ＿ｆｌａｇが全て０である場合、ＤｅｃｏｄｅｄＳｋｉｐＦｌａｇが１となる。そうでない場合は、ＤｅｃｏｄｅｄＳｋｉｐＦｌａｇは０に設定される。逆にいえば、ＤｅｃｏｄｅｄＳｋｉｐＦｌａｇが１の場合、下位ブロックの最初から３番目までのスキップフラグが０であるため、４番目に相当する下位ブロックのスキップフラグ（ｌｏｗｅｒ＿ｓｋｉｐ＿ｆｌａｇ）は自動的に１に設定される。
【０１３２】
（シンタクス分割例）  
このようなシンタクス構造をもつことで、四分木分割されたシンタクス構造における下位スキップフラグの冗長性を削減することが可能となる。なお、本実施の形態に関わるシンタクス要素のｕｐｐｅｒ＿ｓｋｉｐ＿ｆｌａｇとｌｏｗｅｒ＿ｓｋｉｐ＿ｆｌａｇを別々の関数として分けることも可能である。この例が図２６Ａ及び図２６Ｂに記述されている。
【０１３３】
図２６Ａでは、ｕｐｐｅｒ＿ｓｋｉｐ＿ｆｌａｇのみを再帰的に符号化するシンタクス構造である。ｕｐｐｅｒ＿ｓｋｉｐ＿ｆｌａｇが０となる場合に、ｐｒｅｄｉｃｔｉｏｎ＿ｕｎｉｔ（）関数が呼ばれる。一方、図２６Ｂにｐｒｅｄｉｃｔｉｏｎ＿ｕｎｉｔ（）関数が示されている。ｐｒｅｄｉｃｔｉｏｎ＿ｕｎｉｔ（）関数は、ｌｏｗｅｒ＿ｓｋｉｐ＿ｆｌａｇのみを符号化する関数である。以上のように上位ブロックと下位ブロックを分割しても、分割しない図２５と同一の機能を実現できる。
【０１３４】
（コーデットブロックフラグとスキップフラグの組み合わせ例）  
実施の形態で説明した、図２２に示されるコーデットブロックフラグのシンタクス構造と図２６に示されるスキップフラグのシンタクス構造を組み合わせることも可能である。図２７にこれら２つを組み合わせた場合のシンタクス構造を示す。ｃｏｄｉｎｇ＿ｕｎｉｔ（）関数内部で、ｐｒｅｄｉｃｔｉｏｎ＿ｕｎｉｔ（）関数とｔｒａｎｓｆｏｒｍ＿ｕｎｉｔ（）関数が呼ばれる構成とすることで、コーデットブロックフラグとスキップフラグの冗長性をそれぞれ削減できる。尚、図中に示されるＤｅｃｏｄｅＳｋｉｐＴｒａｎｓＦｌａｇは、図２２で説明したＤｅｃｏｄｅＳｋｉｐＦｌａｇと同じ機能を有するが、スキップフラグの冗長度削減時のフラグの名称が被るため、異なるインデックスを与えている。
【０１３５】
（発明の効果）  
以上に述べたように、本実施の形態を用いると、階層的なＣＢＰやＣＢＦ、およびスキップフラグについて、その冗長性の排除により、圧縮率の高い符号化手段、およびその符号化手段により圧縮されたデータの復号化手段を提供できる。なお、本実施の形態での手段および方法は従来の冗長性を排除するものであって、新しい符号化モードやフラグの追加は行っていない。したがって、従来の符号化方法に対して本実施の形態に記載の方法でフラグの符号化を行うという変更のみを加えた符号化手段を用いるなら、符号量が減ることはあっても増えることはないと期待できる。
【０１３６】
上述の実施形態の中で示した処理手順に示された指示は、ソフトウェアであるプログラムに基づいて実行されることが可能である。汎用の計算機システムが、このプログラムを予め記憶しておき、このプログラムを読み込むことにより、上述した実施形態の画像復号化方法および画像符号化方法による効果と同様な効果を得ることも可能である。上述の実施形態で記述された指示は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＯＭ、ＤＶＤ±Ｒ、ＤＶＤ±ＲＷなど）、半導体メモリ、又はこれに類する記録媒体に記録される。コンピュータまたは組み込みシステムが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であってもよい。コンピュータは、この記録媒体からプログラムを読み込み、このプログラムに基づいてプログラムに記述されている指示をＣＰＵで実行させれば、上述した実施形態の画像復号化方法および画像符号化方法と同様な動作を実現することができる。もちろん、コンピュータがプログラムを取得する場合又は読み込む場合はネットワークを通じて取得又は読み込んでもよい。  
また、記憶媒体からコンピュータや組み込みシステムにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワーク等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行してもよい。  
さらに、本願発明における記憶媒体は、コンピュータあるいは組み込みシステムと独立した媒体に限らず、ＬＡＮやインターネット等により伝達されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。  
また、記憶媒体は１つに限られず、複数の媒体から本実施形態における処理が実行される場合も、本発明における記憶媒体に含まれ、媒体の構成は何れの構成であってもよい。
【０１３７】
なお、本願発明におけるコンピュータまたは組み込みシステムは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するためのものであって、パソコン、マイコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であってもよい。  
また、本願発明の実施形態におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の実施形態における機能を実現することが可能な機器、装置を総称している。
【０１３８】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【０１３９】
６０１…画像入力部、６０２、８０２…演算ユニット、６０３、８０３…データ用メモリ、６０４…符号化データ出力部、６０５、８０５…プログラム用メモリ、８０１…符号化データ入力部、８０４…画像出力部。
【図１】
2011121843.tif 000003
【図２】
2011121843.tif 000004
【図３】
2011121843.tif 000005
【図４】
2011121843.tif 000006
【図５】
2011121843.tif 000007
【図６】
2011121843.tif 000008
【図７】
2011121843.tif 000009
【図８】
2011121843.tif 000010
【図９】
2011121843.tif 000011
【図１０】
2011121843.tif 000012
【図１１】
2011121843.tif 000013
【図１２】
2011121843.tif 000014
【図１３】
2011121843.tif 000015
【図１４】
2011121843.tif 000016
【図１５】
2011121843.tif 000017
【図１６】
2011121843.tif 000018
【図１７】
2011121843.tif 000019
【図１８】
2011121843.tif 000020
【図１９】
2011121843.tif 000021
【図２０Ａ】
2011121843.tif 000022
【図２０Ｂ】
2011121843.tif 000023
【図２０Ｃ】
2011121843.tif 000024
【図２１】
2011121843.tif 000025
【図２２】
2011121843.tif 000026
【図２３Ａ】
2011121843.tif 000027
【図２３Ｂ】
2011121843.tif 000028
【図２４Ａ】
2011121843.tif 000029
【図２４Ｂ】
2011121843.tif 000030
【図２４Ｃ】
2011121843.tif 000031
【図２４Ｄ】
2011121843.tif 000032
【図２５】
2011121843.tif 000033
【図２６Ａ】
2011121843.tif 000034
【図２６Ｂ】
2011121843.tif 000035
【図２７】
2011121843.tif 000036
【図２８】
2011121843.tif 000037
【国際調査報告】
2011121843.tif 000038
2011121843.tif 000039