(57)【要約】  動画像の局所的特性に適合したパーティションサイズや変換サイズを選択できる可能性を高く維持しつつ、付加情報の符号量を低減する。動画像符号化装置１０は、入力動画像を所定の大きさのブロックに分割して、ブロック単位に符号化処理を行うもので、ブロックのパーティション構造を決定する予測パラメータ決定部１０２と、パーティション構造で規定されるパーティションを単位として予測画像を生成する予測画像生成部１０３と、予測画像と入力動画像の差分である予測残差に対して所定の変換プリセットに含まれる周波数変換のいずれかを適用する変換係数生成部１０７と、パーティション形状情報に基づいてパーティション毎に適用可能な周波数変換のリストである変換候補リストを生成する変換制約導出部１０４と、変換候補リストと変換プリセットに基づいて変換選択フラグを可変長符号化する可変長符号化部１０８とを備える。
2010116869.tif 000002
【特許請求の範囲】
【請求項１】
入力動画像を所定の大きさのブロックに分割して、ブロック単位に符号化処理を行う動画像符号化装置において、
ブロックのパーティション構造を決定する予測パラメータ決定部と、
前記パーティション構造で規定されるパーティションを単位として予測画像を生成する予測画像生成部と、
前記予測画像と入力動画像の差分である予測残差に対して所定の変換プリセットに含まれる変換のいずれかを適用する変換係数生成部と、
パーティション形状情報に基づいて適用可能な変換のリストである変換候補リストを生成する変換候補導出部と、
前記変換候補リストに基づいてパーティション毎に適用する変換を示す変換選択フラグを決定する周波数変換決定部と、
前記変換候補リストと前記変換プリセットに基づいて前記変換選択フラグを可変長符号化する可変長符号化部を備えることを特徴とする動画像符号化装置。
【請求項２】
パーティション形状情報に基づいてパーティション毎に適用不可能な変換のリストである禁止変換リストを生成する変換制約導出部を備え、
前記変換候補リストは、前記禁止変換リストと前記変換プリセットに基づいて導出されることを特徴とする請求項１記載の動画像符号化装置。
【請求項３】
前記パーティション形状情報とは、パーティションの縦の長さと横の長さの比、または、パーティションの縦の長さと横の長さの大小関係であることを特徴とする請求項１または２記載の動画像符号化装置。
【請求項４】
前記パーティション形状情報とは、パーティションの縦の長さと横の長さの最小値であることを特徴とする請求項１または２記載の動画像符号化装置。
【請求項５】
前記パーティション構造は、階層構造によって表現されて各パーティションはその形状に応じていずれかの階層に含まれることが規定され、
前記パーティション形状情報とは、パーティションが属する階層であることを特徴とする請求項１または２記載の動画像符号化装置。
【請求項６】
前記所定の変換プリセットは、変換サイズが縦１画素の横長矩形である変換を少なくとも一個以上含み、
前記変換候補リスト生成部は、パーティションの横の長さが縦の長さよりも長い場合に縦１画素の横長矩形の変換サイズの変換を前記変換候補リストに含めることを特徴とする請求項１記載の動画像符号化装置。
【請求項７】
前記所定の変換プリセットは、変換サイズが正方形の変換を少なくとも一個、変換サイズが横長矩形または縦長矩形である変換を少なくとも一個含み、
前記変換制約導出部は、パーティションの縦の長さと横の長さが一致しない場合に、正方形の変換を少なくとも一個、前記禁止変換リストへ含めることを特徴とする請求項２記載の動画像符号化装置。
【請求項８】
前記所定の変換プリセットは、変換サイズが横長矩形の変換および変換サイズが縦長矩形の変換を少なくとも各一個以上含み、
前記変換制約導出部は、パーティションの横の長さが縦の長さよりも長い場合に、縦長矩形の変換サイズの変換を前記禁止変換リストへ含めることを特徴とする請求項２記載の動画像符号化装置。
【請求項９】
前記所定の変換プリセットは、互いに類似関係にある変換サイズの変換を少なくとも二個以上含み、
前記変換制約導出部は、パーティションの縦の長さと横の長さの最小値が所定の閾値以上の場合に、前記類似関係にある変換サイズを有する変換の中で最小の変換サイズの変換を前記禁止変換リストへ含めることを特徴とする請求項２記載の動画像符号化装置。
【請求項１０】
前記所定の変換プリセットは、第一の変換と、前記第一の変換と相似関係にありかつ前記第一の変換よりも変換サイズが小さい第二の変換を含み、
前記パーティション構造は、階層構造によって表現されて各パーティションはその形状に応じていずれかの階層に含まれることが規定され、
前記変換制約導出部は、パーティションが最下位ではない所定の階層に属する場合には前記第一の変換を変換候補リストに含めるとともに前記第二の変換は変換候補リストに含めず、パーティションが前記最下位ではない所定の階層よりも下位の階層に属する場合には前記第二の変換を変換候補リストに含めることを特徴とする請求項１記載の動画像符号化装置。
【請求項１１】
入力符号化データをブロック単位に復号処理を行う動画像復号装置において、
前記入力符号化データから、処理対象のブロックのパーティション構造を復号する可変長符号復号部と、
前記パーティション構造で規定されるパーティションを単位として予測画像を生成する予測画像生成部と、
パーティション形状情報に基づいて適用可能な変換の変換制約および／または変換候補を導出する変換制御導出部とを有し、
前記可変長復号部は、前記入力符号化データと前記変換制約および／または前記変換候補に基づいて変換選択フラグを復号するとともに、前記変換選択フラグに基づいて前記処理対象のブロックの変換係数を復号し、
さらに前記変換選択フラグにより規定される変換に対応する逆変換を前記変換係数に適用して予測残差を再構築する予測残差再構築部と、
前記予測画像と前記予測残差とに基づいて前記処理対象のブロックに対応する復号画像データを出力する局所復号画像生成部と、を備えることを特徴とする動画像復号装置。
【請求項１２】
入力符号化データを処理してブロック単位で画像を復号する動画像復号装置において、
処理対象のブロックのパーティション構造を決定する予測パラメータ、および、パーティションおよびパーティションの集合に対して適用可能な変換を規定または更新するためのルールを復号する可変長符号復号部と、
前記パーティション構造で規定されるパーティションを単位として予測画像を生成する予測画像生成部と、
前記可変長復号部は、前記入力符号化データと前記ルールに基づいて変換選択フラグを復号するとともに、前記変換選択フラグに基づいて前記処理対象のブロックの変換係数を復号し、
さらに前記変換選択フラグにより規定される変換に対応する逆変換を前記変換係数に適用して予測残差を再構築する予測残差再構築部と、
前記予測画像と前記予測残差とに基づいて前記処理対象のブロックに対応する復号画像データを出力する局所復号画像生成部と、を備えることを特徴とする動画像復号装置。
【請求項１３】
前記ルールは、特定の形状のパーティションに対して、特定の種類の変換を前記変換候補リストに含めることを規定するルールを含むことを特徴とする請求項１２記載の動画像復号装置。
【請求項１４】
前記ルールは、特定の形状のパーティションに対して、特定の種類の変換を前記変換候補リストに含めることを禁止することを規定するルールを含むことを特徴とする請求項１２記載の動画像復号装置。
【請求項１５】
前記ルールは、特定の形状のパーティションに対して、特定の種類の変換が前記変換候補リストに含まれている場合に、当該変換を別の変換に置換することを規定するルールを含むことを特徴とする請求項１２記載の動画像復号装置。
【請求項１６】
前記ルールは、特定の形状のパーティションに対して特定の種類の変換を許可または禁止または置換する基礎ルールの組み合わせとして表現される複合ルールを含むことを特徴とする請求項１２記載の動画像復号装置。
【請求項１７】
前記ルールは、特定の階層よりも上位の階層に属するパーティションに対して、類似関係にある変換の中で小さいサイズの変換を前記変換候補リストに含めることを禁止することを規定するルールを前記複合ルールとして含むことを特徴とする請求項１６記載の動画像復号装置。
【請求項１８】
前記可変長符号化部は、前記ルールとして、前記複合ルールを適用するか否かのフラグを符号化することを特徴とする請求項１６または１７に記載の動画像復号装置。
【請求項１９】
入力動画像を所定の大きさのブロックに分割して、ブロック単位に符号化処理を行う動画像符号化装置において、
ブロックのパーティション構造を決定する予測パラメータ決定部と、
前記パーティション構造で規定されるパーティションを単位として予測画像を生成する予測画像生成部と、
前記予測画像と入力動画像の差分である予測残差に対して所定の変換プリセットに含まれる周波数変換のいずれかを適用する変換係数生成部と、
パーティション形状情報に基づいてパーティション毎に適用可能な変換の変換制約および／または変換候補を導出する変換制御導出部と、
前記変換制約および／または変換候補に基づいて適用する変換を示す変換選択フラグを決定する周波数変換決定部と、
前記変換制御導出部における変換制約および／または変換候補の導出方法を規定または更新するルールを決定する変換候補導出ルール決定部と、
前記変換制約および／または変換候補リストと前記変換プリセットに基づいて前記変換選択フラグを可変長符号化し、加えて前記変換候補導出ルールをブロックより大きい所定の単位毎に可変長符号化する可変長符号化部を備えることを特徴とする動画像符号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像を符号化して符号化データを生成する動画像符号化装置と、伝送・蓄積された動画像の符号化データから動画像を再生する動画像復号装置に関する。
【背景技術】
【０００２】
＜導入と基本的な用語の定義＞
ブロックベースの動画像符号化方式においては、符号化対象である入力動画像が、マクロブロック（以下、ＭＢ）と呼ばれる所定の処理単位に分割され、ＭＢ毎に符号化処理が行われて、符号化データが生成される。動画像の再生時には、復号対象である符号化データをＭＢ単位で処理して復号することで、復号画像が生成される。【０００３】
現在広く普及しているブロックベースの動画像符号化方式として、非特許文献１により規定される方式（Ｈ．２６４／ＡＶＣ（Advanced Video Coding））がある。Ｈ．２６４／ＡＶＣでは、ＭＢ単位に分割された入力動画像を推定する予測画像が生成されて、入力動画像と予測画像の差分である予測残差が計算される。得られた予測残差には、離散コサイン変換（ＤＣＴ）に代表される周波数変換が適用されて、変換係数が導出される。導出された変換係数は、ＣＡＢＡＣ（Context-based Adaptive Binary Arithmetic Coding）やＣＡＶＬＣ（Context-based Adaptive Variable Length Coding）と呼ばれる方法で可変長符号化される。なお、予測画像は、動画像の空間的な相関を利用するイントラ予測や、動画像の時間的な相関を利用するインター予測（動き補償予測）により生成される。【０００４】
＜パーティションの概念とその効果＞
インター予測では、符号化対象ＭＢの入力動画像を近似する画像が、パーティションと呼ばれる単位で生成される。各パーティションには、１個または２個の動きベクトルが対応付けられる。前記動きベクトルに基づいて、フレームメモリに記録されている局所復号画像上において符号化対象ＭＢに対応する領域を参照することで、予測画像が生成される。なお、その際に参照される局所復号画像は参照画像と呼ばれる。Ｈ．２６４／ＡＶＣでは、画素単位で、１６×１６、１６×８、８×１６、８×８、８×４、４×８、４×４のパーティションサイズが利用できる。小さいパーティションサイズを利用すれば、細かい単位で動きベクトルを指定して予測画像を生成できるため、動きの空間的な相関が小さい場合であっても、入力動画像に近い予測画像を生成できる。一方、大きいパーティションサイズを利用すれば、動きの空間的な相関が大きい場合に、動きベクトルの符号化に要する符号量を低減できる。【０００５】
＜変換サイズの概念とその効果＞
予測画像を用いて生成された予測残差では、入力動画像の画素値の空間的または時間的冗長性が削減されている。さらに、予測残差に対してＤＣＴを適用することで、変換係数の低周波成分にエネルギーを集中させられる。従って、そのエネルギーの偏りを利用して可変長符号化を実行することで、予測画像やＤＣＴを利用しない場合に較べて、符号化データの符号量を削減できる。【０００６】
Ｈ．２６４／ＡＶＣでは、ＤＣＴによる低周波成分へのエネルギー集中性を増加させる目的で、複数種の変換サイズのＤＣＴから動画像の局所的性質に適合したＤＣＴを選択する方式（ブロック適応変換選択）が採用されている。例えば、予測画像がインター予測により生成される場合には、８×８ＤＣＴと４×４ＤＣＴの二種類のＤＣＴから、予測残差の変換に適用するＤＣＴを選択できる。８×８ＤＣＴは、広い範囲で画素値の空間相関を利用できるため、高周波成分が比較的少ない平坦な領域に対して有効である。一方、４×４ＤＣＴは、物体の輪郭を含むような高周波成分の多い領域で有効である。Ｈ．２６４／ＡＶＣにおいては、８×８ＤＣＴは大きい変換サイズのＤＣＴであり、４×４ＤＣＴは小さい変換サイズのＤＣＴといえる。
なお、Ｈ．２６４／ＡＶＣでは、パーティションの面積が８×８画素以上の場合に８×８ＤＣＴと４×４ＤＣＴを選択できる。また、パーティションの面積が８×８画素未満の場合に４×４ＤＣＴを選択できる。【０００７】
上記説明の通り、Ｈ．２６４／ＡＶＣは、動画像の局所的性質である画素値の空間相関や動きベクトルの空間相関の高低に応じて好適なパーティションサイズや変換サイズを選択できるため、符号化データの符号量を削減できる。【０００８】
＜適応変換サイズ拡張とパーティションサイズ拡張の説明＞
近年、ＨＤ（１９２０画素×１０８０画素）以上の解像度を有する高精細動画像が増加している。高精細動画像では従来の低解像度の動画像の場合に較べて、動画像内の局所領域において動画像上の画素値の空間相関や動きベクトルの空間相関の取り得る範囲が広い。とりわけ、画素値と動きベクトルの双方に関して、局所領域における空間相関が高い場合が多いという性質を高精細動画像は有している。【０００９】
非特許文献２には、Ｈ．２６４／ＡＶＣのパーティションサイズや変換サイズを拡張することで、上記のような高精細動画像の空間相関の性質を利用して、符号化データの符号量を削減する動画像符号化方式が記載されている。【００１０】
具体的には、パーティションサイズとして、Ｈ．２６４／ＡＶＣで規定されているものに加え、６４×６４、６４×３２、３２×６４、３２×３２、３２×１６、１６×３２のパーティションサイズが追加されている。さらに、ＤＣＴとして、Ｈ．２６４／ＡＶＣで規定されているものに加え、１６×１６ＤＣＴ、１６×８ＤＣＴ、８×１６ＤＣＴの３種の新しい変換サイズを有するＤＣＴが追加されている。【００１１】
パーティションの面積が１６×１６画素以上の場合には１６×１６ＤＣＴ、８×８ＤＣＴ、４×４ＤＣＴが選択できる。また、パーティションサイズが１６×８の場合は１６×８ＤＣＴ、８×８ＤＣＴ、４×４ＤＣＴが選択できる。パーティションサイズが８×１６の場合は８×１６ＤＣＴ、８×８ＤＣＴ、４×４ＤＣＴが選択できる。パーティションサイズが８×８の場合は８×８ＤＣＴ、４×４ＤＣＴが選択できる。パーティションの面積が８×８画素未満の場合には４×４ＤＣＴが選択できる。【００１２】
非特許文献２記載の方式では、上記のような多様なパーティションサイズや変換サイズを切り替えることで、画素や動きベクトルの空間相関のダイナミックレンジが比較的広い高精細動画像に対しても動画像の局所的性質に適合したパーティションサイズや変換サイズを選択できるため、符号化データの符号量を削減できる。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】ＩＴＵ−Ｔ  Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  Ｈ．２６４（１１／０７）
【非特許文献２】ＩＴＵ−Ｔ  Ｔ０９−ＳＧ１６−Ｃ−０１２３
【発明の概要】
【発明が解決しようとする課題】
【００１４】
上記説明の通り、動画像符号化方式において、選択可能なパーティションサイズや変換サイズの種類を増加させることは、符号化データの符号量削減に有効である。しかしながら、動画像上の各局所領域において、復号時に適用するパーティションサイズや変換サイズを選択するために必要な付加情報の符号量が増加するという新たな問題が生じる。【００１５】
非特許文献１および非特許文献２では、パーティションサイズが大きい場合においても小さい変換サイズの周波数変換（４×４ＤＣＴ）を利用できる。しかしながら、大きいパーティションは画素値や動きベクトルの空間相関の高い領域で選択されやすいため、そのようなパーティションに対して小さい変換サイズの周波数変換を適用する場合に、大きい変換サイズの周波数変換を適用する場合に較べて予測残差のエネルギーをより少数の変換係数に集中することが難しい。そのため、小さい変換サイズの周波数変換が選択されることは殆ど無く、変換サイズの選択に必要な付加情報が無駄になっている。特に、最大パーティションサイズが拡大されることで、大きいパーティションサイズと小さい変換サイズの大きさの差が拡大した場合には、小さい変換サイズはより選択され難くなる。【００１６】
また、非特許文献２では、長方形のパーティションに対して同じ大きさの変換サイズの周波数変換を選択できたが、変換サイズの種類をさらに追加した場合に、選択可能な変換サイズをどのような基準で決定するかについては言及されていない。【００１７】
本発明は、このような状況に鑑みてなされたもので、多様なパーティションサイズや変換サイズが動画像符号化装置において利用可能である場合に、動画像の局所的特性に適合したパーティションサイズや変換サイズを選択できる可能性を維持しつつ、付加情報の符号量を低減することを可能とする動画像符号化装置を提供するものである。また、前記動画像符号化装置で符号化された符号化データを復号可能な動画像復号装置を提供するものである。
【課題を解決するための手段】
【００１８】
上述のごとき課題を解決するために、本発明の第１の技術手段は、入力動画像を所定の大きさのブロックに分割して、ブロック単位に符号化処理を行う動画像符号化装置において、ブロックのパーティション構造を決定する予測パラメータ決定部と、パーティション構造で規定されるパーティションを単位として予測画像を生成する予測画像生成部と、予測画像と入力動画像の差分である予測残差に対して所定の変換プリセットに含まれる変換のいずれかを適用する変換係数生成部と、パーティション形状情報に基づいて適用可能な変換のリストである変換候補リストを生成する変換候補導出部と、変換候補リストに基づいてパーティション毎に適用する変換を示す変換選択フラグを決定する周波数変換決定部と、変換候補リストと変換プリセットに基づいて変換選択フラグを可変長符号化する可変長符号化部を備えることを特徴としたものである。【００１９】
第２の技術手段は、第１の技術手段において、パーティション形状情報に基づいてパーティション毎に適用不可能な変換のリストである禁止変換リストを生成する変換制約導出部を備え、変換候補リストは、禁止変換リストと変換プリセットに基づいて導出されることを特徴としたものである。【００２０】
第３の技術手段は、第１または２の技術手段において、パーティション形状情報とは、パーティションの縦の長さと横の長さの比、または、パーティションの縦の長さと横の長さの大小関係であることを特徴としたものである。【００２１】
第４の技術手段は、第１または２の技術手段において、パーティション形状情報とは、パーティションの縦の長さと横の長さの最小値であることを特徴としたものである。【００２２】
第５の技術手段は、第１または２の技術手段において、パーティション構造は、階層構造によって表現されて各パーティションはその形状に応じていずれかの階層に含まれることが規定され、パーティション形状情報とは、パーティションが属する階層であることを特徴としたものである。【００２３】
第６の技術手段は、第１の技術手段において、所定の変換プリセットは、変換サイズが縦１画素の横長矩形である変換を少なくとも一個以上含み、変換候補リスト生成部は、パーティションの横の長さが縦の長さよりも長い場合に縦１画素の横長矩形の変換サイズの変換を変換候補リストに含めることを特徴としたものである。【００２４】
第７の技術手段は、第２の技術手段において、所定の変換プリセットは、変換サイズが正方形の変換を少なくとも一個、変換サイズが横長矩形または縦長矩形である変換を少なくとも一個含み、変換制約導出部は、パーティションの縦の長さと横の長さが一致しない場合に、正方形の変換を少なくとも一個、禁止変換リストへ含めることを特徴としたものである。【００２５】
第８の技術手段は、第２の技術手段において、所定の変換プリセットは、変換サイズが横長矩形の変換および変換サイズが縦長矩形の変換を少なくとも各一個以上含み、変換制約導出部は、パーティションの横の長さが縦の長さよりも長い場合に、縦長矩形の変換サイズの変換を禁止変換リストへ含めることを特徴としたものである。【００２６】
第９の技術手段は、第２の技術手段において、所定の変換プリセットは、互いに類似関係にある変換サイズの変換を少なくとも二個以上含み、変換制約導出部は、パーティションの縦の長さと横の長さの最小値が所定の閾値以上の場合に、類似関係にある変換サイズを有する変換の中で最小の変換サイズの変換を禁止変換リストへ含めることを特徴としたものである。【００２７】
第１０の技術手段は、第１の技術手段において、所定の変換プリセットは、第一の変換と、第一の変換と相似関係にありかつ第一の変換よりも変換サイズが小さい第二の変換を含み、パーティション構造は、階層構造によって表現されて各パーティションはその形状に応じていずれかの階層に含まれることが規定され、変換制約導出部は、パーティションが最下位ではない所定の階層に属する場合には第一の変換を変換候補リストに含めるとともに第二の変換は変換候補リストに含めず、パーティションが最下位ではない所定の階層よりも下位の階層に属する場合には第二の変換を変換候補リストに含めることを特徴としたものである。【００２８】
第１１の技術手段は、入力符号化データをブロック単位に復号処理を行う動画像復号装置において、入力符号化データから、処理対象のブロックのパーティション構造を復号する可変長符号復号部と、パーティション構造で規定されるパーティションを単位として予測画像を生成する予測画像生成部と、パーティション形状情報に基づいて適用可能な変換の変換制約および／または変換候補を導出する変換制御導出部とを有し、可変長復号部は、入力符号化データと変換制約および／または変更に基づいて変換選択フラグを復号するとともに、変換選択フラグに基づいて処理対象のブロックの変換係数を復号し、さらに変換選択フラグにより規定される変換に対応する逆変換を変換係数に適用して予測残差を再構築する予測残差再構築部と、予測画像と予測残差とに基づいて処理対象のブロックに対応する復号画像データを出力する局所復号画像生成部と、を備えることを特徴としたものである。【００２９】
第１２の技術手段は、第の技術手段において、入力符号化データを処理してブロック単位で画像を復号する動画像復号装置において、処理対象のブロックのパーティション構造を決定する予測パラメータ、および、パーティションおよびパーティションの集合に対して適用可能な変換を規定または更新するためのルールを復号する可変長符号復号部と、パーティション構造で規定されるパーティションを単位として予測画像を生成する予測画像生成部と、可変長復号部は、入力符号化データとルールに基づいて変換選択フラグを復号するとともに、変換選択フラグに基づいて処理対象のブロックの変換係数を復号し、さらに変換選択フラグにより規定される変換に対応する逆変換を変換係数に適用して予測残差を再構築する予測残差再構築部と、予測画像と予測残差とに基づいて処理対象のブロックに対応する復号画像データを出力する局所復号画像生成部と、を備えることを特徴としたものである。【００３０】
第１３の技術手段は、第１２の技術手段において、ルールは、特定の形状のパーティションに対して、特定の種類の変換を変換候補リストに含めることを規定するルールを含むことを特徴としたものである。【００３１】
第１４の技術手段は、第１２の技術手段において、ルールは、特定の形状のパーティションに対して、特定の種類の変換を変換候補リストに含めることを禁止することを規定するルールを含むことを特徴としたものである。【００３２】
第１５の技術手段は、第１２の技術手段において、ルールは、特定の形状のパーティションに対して、特定の種類の変換が変換候補リストに含まれている場合に、当該変換を別の変換に置換することを規定するルールを含むことを特徴としたものである。【００３３】
第１６の技術手段は、第１２の技術手段において、ルールは、特定の形状のパーティションに対して特定の種類の変換を許可または禁止または置換する基礎ルールの組み合わせとして表現される複合ルールを含むことを特徴としたものである。【００３４】
第１７の技術手段は、第１６の技術手段において、ルールは、特定の階層よりも上位の階層に属するパーティションに対して、類似関係にある変換の中で小さいサイズの変換を変換候補リストに含めることを禁止することを規定するルールを複合ルールとして含むことを特徴としたものである。【００３５】
第１８の技術手段は、第１６または１７の技術手段において、可変長符号化部は、ルールとして、複合ルールを適用するか否かのフラグを符号化することを特徴とする特徴としたものである。【００３６】
第１９の技術手段は、入力動画像を所定の大きさのブロックに分割して、ブロック単位に符号化処理を行う動画像符号化装置において、ブロックのパーティション構造を決定する予測パラメータ決定部と、パーティション構造で規定されるパーティションを単位として予測画像を生成する予測画像生成部と、予測画像と入力動画像の差分である予測残差に対して所定の変換プリセットに含まれる周波数変換のいずれかを適用する変換係数生成部と、パーティション形状情報に基づいてパーティション毎に適用可能な変換の変換制約および／または変換候補を導出する変換制御導出部と、変換制約および／または変換候補に基づいて適用する変換を示す変換選択フラグを決定する周波数変換決定部と、変換制御導出部における変換制約および／または変換候補の導出方法を規定または更新するルールを決定する変換候補導出ルール決定部と、変換制約および／または変換候補リストと変換プリセットに基づいて変換選択フラグを可変長符号化し、加えて変換候補導出ルールをブロックより大きい所定の単位毎に可変長符号化する可変長符号化部を備えることを特徴としたものである。
【発明の効果】
【００３７】
本発明の動画像符号化装置では、特定のパーティションサイズが選択される場合に、選択可能な変換サイズを有効性の高いものに制限することで、動画像の局所的特性に適合した変換サイズを選択できる可能性を高く維持しつつ、付加情報の符号量を低減でき、さらに、符号化処理の処理量を削減できる。また、本発明の動画像復号装置では、前記動画像符号化装置で符号化された符号化データを復号できる。
【図面の簡単な説明】
【００３８】
【図１】拡張マクロブロック（ＭＢ）と処理順序の定義を説明するための図である。
【図２】本発明の動画像符号化装置の一実施例を示すブロック図である。
【図３】パーティション階層構造と処理順序の定義を説明するための図である。
【図４】禁止変換リストの生成処理の一例を説明するためのフローチャートである。
【図５】禁止変換リストの生成処理の他の例を説明するためのフローチャートである。
【図６】禁止変換リストの生成時のパーティション分割について説明するための図である。
【図７】禁止変換リストの生成時のパーティション分割について説明するための他の図である。
【図８】禁止変換リストの生成処理の更に他の例を説明するためのフローチャートである。
【図９】禁止変換リストの生成手順の具体例を説明するための図である。
【図１０】変換選択フラグの符号化データ生成処理例を説明するためのフローチャートである。
【図１１】本発明の動画像復号装置の一実施例を示すブロック図である。
【図１２】本発明の動画像符号化装置の他の実施例を示すブロック図である。
【図１３】変換候補リストの生成処理の一例を説明するためのフローチャートである。
【図１４】本発明の動画像復号装置の他の実施例を示すブロック図である。
【図１５】本発明の動画像符号化装置の更に他の実施例を示すブロック図である。
【図１６】本発明の動画像復号装置の更に他の実施例を示すブロック図である。
【発明を実施するための形態】
【００３９】
（実施形態１）
以下、本発明による動画像符号化装置および動画像復号装置の一実施形態である動画像符号化装置１０および動画像復号装置２０について図１〜図１１を参照しながら説明する。なお、図面の説明においては、同一要素には同一符号を付与して説明を省略する。
【００４０】
以下の説明において、動画像符号化装置には６４×６４画素から構成される拡張ＭＢ単位で入力動画像が順次入力されて処理が実行されるものとする。また、拡張ＭＢの入力順序は、図１に示すようなラスタスキャン順を仮定する。ただし、本発明は拡張ＭＢのサイズが上記以外の場合にも適用可能である。特に、現在広く利用されている処理単位である１６×１６画素よりも大きなサイズの拡張ＭＢに対して有効である。
【００４１】
以下の説明における動画像符号化装置および動画像復号装置における処理は、Ｈ．２６４／ＡＶＣを元に実現されるものとし、動作について特に触れていない部分については、Ｈ．２６４／ＡＶＣの動作に準じるものとする。ただし、本発明はＨ．２６４／ＡＶＣに限定されるものではなく、類似のＶＣ−１、ＭＰＥＧ−２、ＡＶＳ等の方式や、ブロック単位の処理や周波数変換を採用する他の動画像符号化方式に対しても適用可能である。
【００４２】
＜動画像符号化装置１０の構成＞
図２は動画像符号化装置１０の構成を示すブロック図である。動画像符号化装置１０は、フレームメモリ１０１、予測パラメータ決定部１０２、予測画像生成部１０３、変換制約導出部１０４、周波数変換決定部１０５、予測残差生成部１０６、変換係数生成部１０７、可変長符号化部１０８、予測残差再構築部１０９、局所復号画像生成部１１０より構成される。
【００４３】
＜フレームメモリ１０１＞
フレームメモリ１０１には、局所復号画像を記録する。ここで、局所復号画像とは、変換係数に対して逆周波数変換を適用することで再構築された予測残差に対し、予測画像を足し合わせることで生成される画像である。入力動画像の特定フレームの特定拡張ＭＢを処理する時点では、処理対象フレームより先に符号化されたフレームに対する局所復号画像、および、処理対象拡張ＭＢより先に符号化された拡張ＭＢに対応する局所復号画像がフレームメモリ１０１に記録されている。なお、フレームメモリ１０１に記録された局所復号画像は、装置内の各構成要素によって適宜読み出すことが可能とする。
【００４４】
＜予測パラメータ決定部１０２（パーティション構造定義、モード判定説明）＞
予測パラメータ決定部１０２は、入力動画像の局所的性質に基づいて、予測パラメータを決定して出力する。ここで、予測パラメータには、少なくとも、拡張ＭＢ内各部で適用するパーティションの構造を表すパーティション構造と、インター予測のための動き情報（動きベクトルおよび参照する局所復号画像のインデックス（参照画像インデックス））が含まれる。また、イントラ予測の際の予測画像生成方法を示すイントラ予測モードを含んでもよい。
【００４５】
パーティション構造の詳細について、図３を参照しながら説明する。パーティション構造は階層構造により表現され、６４×６４画素を処理単位とする階層を階層Ｌ０、３２×３２画素を処理単位とする階層を階層Ｌ１、１６×１６画素を処理単位とする階層を階層Ｌ２、８×８画素を処理単位とする階層を階層Ｌ３と定義する。各階層では、分割方法として、分割を行わない一分割、水平方向の直線により領域を等分する水平二分割、垂直方向の直線により領域を等分する垂直二分割、水平方向と垂直方向の２本の直線により領域を四等分する四分割のいずれかを選択できる。なお、処理単位が大きい階層を上位階層、処理単位が小さい階層を下位階層と呼ぶ。本実施形態においては、階層Ｌ０が最上位階層であり、階層Ｌ３が最下位階層である。パーティション構造は最上位階層である階層Ｌ０から順に各階層における分割方法を特定することで表現される。具体的には、次の手順によってパーティション構造を一意に表現できる。
【００４６】
（手順Ｓ１０）階層Ｌ０における分割方法が一分割、水平二分割、垂直二分割のいずれかであれば、その分割方法で表現される領域を、階層Ｌ０における処理単位のパーティションとする。分割方法が四分割の場合には、各分割領域に対し手順Ｓ１１によりパーティションを決定する。
（手順Ｓ１１）階層Ｌ１における分割方法が一分割、水平二分割、垂直二分割のいずれかであれば、その分割方法で表現される領域を、階層Ｌ１における処理単位のパーティションとする。分割方法が四分割の場合には、各分割領域に対し手順Ｓ１２によりパーティションを決定する。
【００４７】
（手順Ｓ１２）階層Ｌ２における分割方法が一分割、水平二分割、垂直二分割のいずれかであれば、その分割方法で表現される領域を、階層Ｌ２における処理単位のパーティションとする。分割方法が四分割の場合には、各分割領域に対し手順Ｓ１３によりパーティションを決定する。
（手順Ｓ１３）階層Ｌ３における分割方法で表現される領域を、階層Ｌ３における処理単位のパーティションとする。
【００４８】
ここで、拡張ＭＢ内の各パーティションの処理順序について説明しておく。図３に示したように各階層において、分割方法に関わらずラスタスキャン順で処理が実行される。ただし、最下位の階層（階層Ｌ３）以外で、分割方法として四分割が選択されている場合には、各四分割領域に対して下位階層で表現されるパーティションがラスタスキャン順に処理される。以降説明する各部において、拡張ＭＢ内のパーティションを処理する場合には、上記の処理順序が適用されるものとする。
【００４９】
パーティションｐが属する階層Ｌｘは次の手順により導出する。
（手順Ｓ２０）パーティションｐのサイズが、特定の階層Ｌｙの一分割または水平二分割または垂直二分割により生成されるパーティションのサイズと等しい場合、Ｌｘの値をＬｙに設定する。
（手順Ｓ２１）上記以外の場合、Ｌｘの値をＬ３に設定する（Ｌｘを最下位階層に設定する）。
【００５０】
＜パーティション形状の説明＞
パーティション構造に属する各パーティションを特徴付ける情報、すなわち、パーティションサイズ、もしくは、パーティションサイズの特徴を示す情報、もしくは、パーティション構造における階層を、パーティション形状情報と呼ぶ。例えば、３２×３２などのパーティションサイズそのもの、所定のパーティションサイズよりも大きいかどうかを示す情報、パーティションの縦の長さと横の長さの比、パーティションの縦の長さと横の長さの大小関係、パーティションの縦の長さと横の長さの最小値や最大値、パーティションが属する階層などは、全てパーティション形状情報である。
【００５１】
予測パラメータは、レート歪判定により決定される。レート歪判定では、各予測パラメータ候補に対し、該予測パラメータを用いて処理対象拡張ＭＢを符号化した際の符号化データの符号量と、局所復号画像と入力動画像の歪からレート歪コストと呼ばれるコストを計算して、当該コストを最小とする予測パラメータを選択する。すなわち、予測パラメータであるパーティション構造や動き情報の可能なあらゆる組み合わせに対してレート歪コストを計算して、最良の組み合わせを予測パラメータとする。レート歪コストＣは、拡張ＭＢの符号化データの符号量をＲ、拡張ＭＢに対応する入力動画像と局所復号画像の平均二乗誤差をＤ、符号量Ｒと誤差Ｄの関係を表すパラメータλを用いて、Ｃ＝Ｄ＋λＲの式により計算できる。
【００５２】
レート歪判定により、処理対象拡張ＭＢを符号化するのに好適な予測パラメータ、すなわち、好適なパーティション構造と、各パーティションに対応する動き情報が決定されて、出力される。
なお、特定の予測パラメータに対してレート歪コストを計算する際に処理対象拡張ＭＢに対して適用する周波数変換が一意に定まっていない可能性がある。その場合には、特定の周波数変換を適用して得られるレート歪コストとして利用することもできるし、複数の周波数変換全てを適用した場合に得られる最小のレート歪コストを利用することもできる。
【００５３】
＜予測画像生成部１０３＞
予測画像生成部１０３は、入力される予測パラメータに基づいて処理対象拡張ＭＢの予測画像を生成して出力する。予測画像生成は次の手順で実行される。
（手順Ｓ３０）予測パラメータに含まれるパーティション構造に基づいて、拡張ＭＢをパーティションに分割して、各パーティションにおける予測画像を手順Ｓ３１により生成する。
（手順Ｓ３１）処理対象のパーティションに対応する動き情報、すなわち、動きベクトルと参照画像インデックスを予測パラメータより読み出す。参照画像インデックスの示す局所復号画像上で、動きベクトルが示す領域の画素値に基づいて動き補償予測によって予測画像を生成する。
【００５４】
＜予測残差生成部１０６＞
予測残差生成部１０６は、入力される入力動画像と予測画像に基づいて、拡張ＭＢの予測残差を生成して出力する。予測残差は拡張ＭＢと同サイズの２次元データであり、各要素は、入力動画像と予測画像の対応する画素間の差分値となる。
【００５５】
＜変換係数生成部１０７＞
変換係数生成部１０７は、入力される予測残差と変換選択フラグに基づいて、予測残差を周波数変換することで変換係数を生成して出力する。変換選択フラグは拡張ＭＢの各パーティションに対して適用する周波数変換を示し、変換係数生成部１０７は拡張ＭＢ内の各パーティションに変換選択フラグの示す周波数変換を選択して、選択した周波数変換を予測残差に適用する。変換選択フラグによって示される周波数変換は、変換係数生成部１０７で適用され得る全ての周波数変換の集合（変換プリセット）の含む周波数変換のいずれかである。
【００５６】
本実施形態における変換プリセットには、４×４ＤＣＴ、８×８ＤＣＴ、１６×１６ＤＣＴ、１６×８ＤＣＴ、８×１６ＤＣＴ、１６×１ＤＣＴ、１×１６ＤＣＴ、８×１ＤＣＴ、および１×８ＤＣＴの９種類の周波数変換が含まれる。ここで規定した各周波数変換は、それぞれ特定の変換サイズのＤＣＴ（離散コサイン変換）に対応する（例えば、４×４ＤＣＴは４×４画素を変換サイズとする離散コサイン変換に対応する。）なお、本発明は上記周波数変換の組に対してのみ制限されるものではなく、上記変換プリセットのサブセットに対しても適応できる。また、別の変換サイズの離散コサイン変換、例えば３２×３２ＤＣＴや６４×６４ＤＣＴを含む周波数変換を変換プリセットに含めても良いし、離散コサイン変換以外の周波数変換、例えばアダマール変換やサイン変換やウェーブレット変換、またはそれらの変換を近似する変換を含む周波数変換を変換プリセットに含めても構わない。
【００５７】
Ｍ×Ｎ画素のパーティションに対して、Ｗ×Ｈの変換サイズを有する周波数変換を適用する処理は、次の疑似コードで示す処理である。なお、領域Ｒ（ｘ，ｙ，ｗ，ｈ）は、パーティション内左上を起点として右方向にｘ画素、下方向にｙ画素変位した位置に存在する幅ｗ画素、高さｈ画素の領域を意味する。
【００５８】
ｆｏｒ（ｊ＝０，ｊ＜Ｎ，ｊ＋＝Ｈ）｛
ｆｏｒ（ｉ＝０，ｉ＜Ｍ，ｉ＋＝Ｗ）｛
領域Ｒ（ｉ，ｊ，Ｗ，Ｈ）に周波数変換を適用
｝
｝
【００５９】
＜変換制約導出部１０４＞
変換制約導出部１０４は、入力される予測パラメータに基づいて、拡張ＭＢ内の各パーティションにおいて選択可能な周波数変換に関する制約を変換制約として導出して出力する。すなわち、予測パラメータにより決定される各パーティションのパーティション形状情報に基づいて、そのパーティションの変換制約を導出する。
【００６０】
変換制約は、拡張ＭＢ内の各パーティションにそれぞれ対応付けられた禁止変換リストの集合として定義する。ここで、禁止変換リストには、変換プリセットに含まれる周波数変換のうち、対応付けられたパーティションにおいて選択することができない周波数変換（禁止周波数変換）が要素に含まれる。言い換えると、変換プリセットの要素から、禁止変換リストの要素を取り除いたものが、対応付けられたパーティションで選択可能な周波数変換の集合（変換候補リスト）となる。
【００６１】
なお、禁止変換リスト、変換候補リストは各変換を集合に含めるか否かの情報を含む変換集合情報によって表現できる。変換プリセットに含まれる変換の数をＮｔ個のとすると、変換の組み合わせは２のＮｔ乗であるため、０〜（２のＮｔ乗―１）の値域を持つ変換集合情報で集合に含まれる変換を表現きる。なお、変換集合情報により必ずしも全ての変換の組合せを表現できる必要はなく、特定の組み合わせに対応する値を表現してもよい。端的な例として、変換プリセットが４ｘ４ＤＣＴ及び８ｘ８ＤＣＴのみを含む場合に、４ｘ４ＤＣＴ（または８ｘ８ＤＣＴ）を禁止するか否かを示す１ｂｉｔのフラグにより禁止リストを表現できる。また４ｘ４ＤＣＴを０、４ｘ４ＤＣＴと８ｘ８ＤＣＴの組を１、８ｘ８ＤＣＴを２という値に各々対応付けて、０〜２の値により変換候補リストを表現することもできる。
また、変換集合情報の意味は、階層、パーティション、ブロックの組などの単位で変更しても構わない。すなわち、同じ変換集合情報の値０が、階層Ｌ０では１６ｘ１６ＤＣＴ、階層Ｌ１では８ｘ８ＤＣＴ、階層Ｌ２では４ｘ４ＤＣＴを意味しても良い。変換集合情報の値の意味を変更することにより、少ない値の範囲で禁止変換リスト及び変換候補リストの表現が可能になる。
従って、本発明における、変換制約、変換候補リストは、リストという言葉に捉われることなく、変換制約、変換候補を示す変換集合情報と同値と考えることとする。
【００６２】
特定のパーティションｐに対する禁止変換リストＬｐは次の手順で生成される。なお、パーティションｐの大きさをＭ×Ｎ画素（横Ｍ画素、縦Ｎ画素）とする。また、パーティションｐは階層Ｌｘに属するとする。
【００６３】
（手順Ｓ４０）Ｌｐを空に設定する。
（手順Ｓ４１）Ｍ×Ｎ画素より大きい変換サイズの周波数変換をＬｐに追加する。
（手順Ｓ４２）Ｍｉｎ（Ｍ，Ｎ）の値に応じて決定した周波数変換をＬｐに追加する。
（手順Ｓ４３）Ｍ÷Ｎの値に応じて決定した周波数変換をＬｐに追加する。
（手順Ｓ４４）階層Ｌｘの値に応じて決定した周波数変換をＬｐに追加する。
なお、Ｍ×Ｎ画素より大きいかどうかを示す情報、Ｍｉｎ（Ｍ，Ｎ）の値、Ｍ÷Ｎの値、階層Ｌｘの値はパーティション形状情報である。
【００６４】
＜Ｍｉｎ（Ｍ，Ｎ）による変換サイズの制限＞
上記手順Ｓ４２のさらに詳細な手順を図４のフロー図を参照して説明する。
（手順Ｓ５０）Ｍｉｎ（Ｍ，Ｎ）が所定の閾値Ｔｈ１（例えばＴｈ１＝１６画素）以上であれば手順Ｓ５１へ進み、それ以外であれば手順Ｓ５２へ進む。
（手順Ｓ５１）周波数変換リスト内で類似関係の変換サイズを有する周波数変換が２個以上存在する場合、それぞれの類似関係の変換サイズを有する周波数変換の組の中で変換サイズが最小である周波数変換（４×４ＤＣＴ、８×１ＤＣＴ、１×８ＤＣＴ）をＬｐに追加して手順Ｓ５２へ進む。ここでの類似関係には相似関係が含まれる。例えば、本実施形態の変換プリセットにおける１６×１６と８×８と４×４の変換サイズが類似関係となる。また、類似関係には近似的な相似関係も含まれる。たとえば、本実施形態の変換プリセットにおける１６×１と８×１の変換サイズや、１×１６と１×８の変換サイズが類似関係となる。なお、以下の説明においては適用しないが、周波数変換をそのサイズに基づいて正方形、縦長矩形、横長矩形の３カテゴリに分類し、各カテゴリに属する周波数変換を類似関係と見なすこともできる。
【００６５】
（手順Ｓ５２）Ｍｉｎ（Ｍ，Ｎ）が所定の閾値Ｔｈ２（例えばＴｈ２＝３２画素）以上であれば手順Ｓ５３へ進み、それ以外であれば処理を終了する。
（手順Ｓ５３）変換プリセット内で類似関係の変換サイズを有する周波数変換が３個以上存在する場合、それぞれの類似関係の変換サイズを有する周波数変換の組の中で２番目に小さい変換サイズの周波数変換（８×８ＤＣＴ）をＬｐに追加して処理を終了する。ただし、Ｔｈ２＞Ｔｈ１とする。
【００６６】
パーティションは動き補償の単位であり、動きベクトルを用いてパーティション単位で生成される予測画像を入力画像に近づけるために、パーティション内の画像のフレーム間の動きが一様となるようパーティション構成が決定される。すなわち、入力動画像上の大きい物体（またはその一部）には大きいパーティションが、小さい物体には小さいパーティションが割り当てられる。一般に、入力動画像上において、大きい物体に対応する領域の画素値の空間相関は、小さい物体に対応する領域の画素値の空間相関に比べて高い。そのため、大きいパーティションに対しては大きい変換サイズの周波数変換が小さい変換サイズの周波数変換に比べて有効である。したがって、大きいパーティションに対して、ある程度小さい変換サイズの周波数変換を禁止変換とした場合でも、符号化データの符号量はほとんど増加しない。
【００６７】
＜Ｍ÷Ｎの値による変換サイズの制限＞
次に、上記手順Ｓ４３のさらに詳細な手順を図５のフロー図を参照して説明する。
（手順Ｓ６０）Ｍ÷Ｎの値が２以上（パーティションｐの横の長さが縦の長さの２倍以上）ならば手順Ｓ６１へ進み、それ以外であれば手順Ｓ６３へ進む。
（手順Ｓ６１）全ての正方形の変換サイズを持つ周波数変換（４×４ＤＣＴ、８×８ＤＣＴ、１６×１６ＤＣＴ）をＬｐに追加して手順Ｓ６２へ進む。
（手順Ｓ６２）変換サイズの縦の長さが横の長さより長い周波数変換（８×１６ＤＣＴ、１×１６ＤＣＴ）をＬｐに追加して処理を終了する。
【００６８】
（手順Ｓ６３）Ｍ÷Ｎの値が０．５以下（パーティションｐの縦の長さが横の長さの２倍以上）ならば手順Ｓ６４へ進み、それ以外であれば手順Ｓ６６へ進む。
（手順Ｓ６４）全ての正方形の変換サイズを持つ周波数変換（４×４ＤＣＴ、８×８ＤＣＴ、１６×１６ＤＣＴ）をＬｐに追加して手順Ｓ６５へ進む。
（手順Ｓ６５）変換サイズの横の長さが縦の長さより長い周波数変換（１６×８ＤＣＴ、１６×１ＤＣＴ）をＬｐに追加して処理を終了する。
【００６９】
（手順Ｓ６６）Ｍ÷Ｎの値が１に等しい（パーティションｐの横と縦の長さが等しい）ならば手順Ｓ６７へ進み、それ以外であれば処理を終了する。
（手順Ｓ６７）変換サイズの横の長さと縦の長さが異なる周波数変換（１６×８ＤＣＴ、１６×１ＤＣＴ、８×１６ＤＣＴ、１×１６ＤＣＴ）をＬｐに追加する。
【００７０】
上記手順Ｓ６１及び手順Ｓ６２の意図について、図６を参照しながら説明する。図６（ａ）に示したように、ある階層の処理単位Ｕの中に２つの物体（前景物体Ｏと背景Ｂ）が存在し、前景物体Ｏと背景Ｂの境界が処理単位Ｕの下部に存在するとする。この場合、図６（ｂ）に示すような、Ｍ÷Ｎの値が２以上となるような横長矩形のパーティションが選択される。逆に、図６（ｃ）に示すような、縦長矩形のパーティションは選択されない。
【００７１】
次に、横長矩形パーティションが選択された場合の、背景Ｂと前景物体Ｏの両方を含む方のパーティションにおける変換サイズと符号化データの符号量の関係について、図６（ｄ）〜（ｆ）を参照して説明する。図６の（ｄ）、（ｅ）、（ｆ）は、前記パーティションにおいて、それぞれ正方形、横長矩形、縦長矩形の変換サイズが適用される場合におけるパーティションと変換サイズの関係を図示したものである。正方形の変換サイズの周波数変換（図６（ｄ））や、縦長矩形の変換サイズの周波数変換（図６（ｆ））を用いると、周波数変換を適用する領域内に境界が存在する場合が多い。
【００７２】
一方、横長矩形の変換サイズの周波数変換（図６（ｅ））を用いると、周波数変換を適用する領域内に境界が存在する場合が少ない。周波数変換を適用する領域内に境界が存在する場合、周波数変換によって変換係数の低周波成分にエネルギーを集中できないため、変換係数の符号化に要する符号量が多くなる。一方、周波数変換を適用する領域内に境界が存在しない場合、周波数変換によって変換係数の低周波成分にエネルギーを集中できるため、変換係数の符号化に要する符号量が少なくなる。ゆえに、横長矩形のパーティションに対しては、横長矩形の変換サイズの周波数変換を適用する方が、正方形や縦長矩形の変換サイズの周波数変換を適用する場合に較べて有効である。したがって、横長矩形パーティションに対して、正方形または縦長矩形の変換サイズの周波数変換を禁止変換に設定した場合でも、符号化データの符号量はほとんど増加しない。
【００７３】
上記手順Ｓ６４及び手順Ｓ６５の意図も上記と同様である。すなわち、縦長矩形パーティションに対して、正方形または横長矩形の変換サイズの周波数変換を禁止変換に設定した場合でも、符号化データの符号量はほとんど増加しない。
【００７４】
上記手順Ｓ６６の意図について、図７を参照しながら説明する。図７（ａ）に示したように、ある階層の処理単位Ｕの中に２つの物体（前景物体Ｏと背景Ｂ）が存在し、前景物体Ｏと背景Ｂの境界が処理単位Ｕの右下部に存在するとする。この場合、図７（ｂ）に示すような、Ｍ÷Ｎの値が１となるような正方形のパーティションが選択される。
【００７５】
次に、正方形のパーティションが選択された場合の、背景Ｂと前景物体Ｏの両方を含むパーティション（右下パーティション）における変換サイズと符号化データの符号量の関係を、図７（ｄ）〜（ｆ）を参照して説明する。図７の（ｄ）、（ｅ）、（ｆ）は、右下パーティションにおいて、それぞれ正方形、横長矩形、縦長矩形の変換サイズが適用される場合におけるパーティションと変換サイズの関係を図示したものである。この場合、正方形、縦長矩形、横長矩形のいずれ変換サイズを用いる場合でも、周波数変換を適用する領域内に境界が存在する割合はそれほど変わらない。したがって、右下パーティションに関しては、正方形、縦長矩形、横長矩形のいずれの変換サイズの周波数変換を用いても、符号化データの符号量の違いは少ない。
【００７６】
一方、処理単位Ｕ内の右下パーティション以外のパーティションにおいては、背景Ｂのみが含まれ境界が存在しないため、いずれの変換サイズを用いても、周波数変換を適用する領域内に境界が存在しない。そこで、予測残差の画素値の空間相関を水平方向（横方向）と垂直方向（縦方向）の両方向にバランス良く活用できる正方形の変換サイズの周波数変換を用いる方が、縦長矩形や横長矩形の変換サイズの周波数変換を用いるのに較べて、より変換係数においてエネルギーを集中できる。ゆえに、正方形のパーティションには、正方形の変換サイズの周波数変換の方が、横長矩形や縦長矩形の変換サイズの周波数変換より有効である。したがって、正方形のパーティションに対して、横長矩形または縦長矩形の変換サイズの周波数変換を禁止変換に設定した場合でも、符号化データの符号量はほとんど増加しない。
【００７７】
＜パーティションの属する階層による変換サイズの制限＞
次に、上記手順Ｓ４４のさらに詳細な手順を図８のフロー図を参照して説明する。
（手順Ｓ７０）階層Ｌｘが最上位階層ならば手順Ｓ７１へ進み、それ以外であれば手順Ｓ７２へ進む。
（手順Ｓ７１）相似形状の変換サイズを有する複数の周波数変換候補（１６×１６ＤＣＴ、８×８ＤＣＴ、４×４ＤＣＴ）のうち、最大の変換サイズを有する周波数変換以外の周波数変換（８×８ＤＣＴ、４×４ＤＣＴ）をＬｐに追加して処理を終了する。
（手順Ｓ７２）階層Ｌｘが最下位階層ならば手順Ｓ７３へ進み、それ以外であれば処理を終了する。
（手順Ｓ７３）相似形状の変換サイズを有する複数の周波数変換候補（１６×１６ＤＣＴ、８×８ＤＣＴ、４×４ＤＣＴ）のうち、最小の変換サイズを有する周波数変換以外の周波数変換（１６×１６ＤＣＴ、８×８ＤＣＴ）をＬｐに追加して処理を終了する。
【００７８】
パーティションが階層構造で表現される場合、最上位階層に属するパーティションで、比較的変換サイズの小さい一部の周波数変換を制限したとしても、符号化データの符号量はほとんど増加しない。それは、最上位階層で特定の変換（例えば８×８ＤＣＴや４×４ＤＣＴ）が選択できなくても、下位階層において選択可能なためである。つまり、小さい変換サイズの周波数変換が有効な領域では、最上位階層に属するパーティションを選択せず、小さい変換サイズの周波数変換が選択可能な下位階層のパーティションを選択することで、符号化データの符号量増加を抑制できる。特に、大きいパーティションに対しては、大きい変換サイズの周波数変換が有効であるという事実を踏まえると、周波数変換候補の中に複数の相似形状の変換サイズの周波数変換が存在する場合に、それらの周波数変換の中で小さい変換サイズの周波数変換を最上位階層で制限するのが好ましい。
【００７９】
同様に、パーティションが階層構造で表現される場合、最下位階層に属するパーティションで、比較的変換サイズの大きい一部の変換サイズの周波数変換を制限したとしても、符号化データの符号量はほとんど増加しない。特に、小さいパーティションに対しては、小さい変換サイズの周波数変換が有効であるという事実を踏まえて、周波数変換候補の中に複数の相似形状の変換サイズの周波数変換が存在する場合に、それらの周波数変換の中で大きい変換サイズの周波数変換を最下位階層で制限するのが好ましい。
【００８０】
＜禁止変換リスト生成処理の具体例＞
上で説明した、変換制約導出部１０４において、特定のパーティション構造に対して変換制約、すなわちパーティション毎の禁止変換リストを生成する手順の具体例について図９を参照して紹介しておく。図９に示したように、拡張ＭＢは、階層Ｌ０で四分割された後、左上部は階層Ｌ１で一分割（パーティションａ）、右上部は階層Ｌ１で水平二分割（パーティションｂ、ｃ）、左下部は階層Ｌ１で垂直二分割（パーティションｄ、ｅ）、右下部は階層Ｌ１で四分割されている。
【００８１】
階層Ｌ１で四分割された領域は、左上部は階層Ｌ２で一分割（パーティションｆ）、右上部は階層Ｌ２で水平二分割（パーティションｇ、ｈ）、左下部は階層Ｌ２で垂直二分割（パーティションｉ、ｊ）、右下部は階層Ｌ２で四分割されている。階層Ｌ２で四分割された各部は、階層Ｌ３で一分割（パーティションｋ、ｌ、ｍ、ｎ）されている。選択可能な周波数変換の変換サイズは、前記の通り、４×４、８×８、１６×１６、１６×１、１×１６、８×１、１×８、１６×８、８×１６の９種類である。
【００８２】
パーティションａは、大きさが３２×３２画素であり階層Ｌ１に属している。上記の禁止変換リストの生成手順を適用すると、手順Ｓ５１で４×４、８×１、１×８、手順Ｓ５２で８×８、手順Ｓ６７で１×１６、１６×１、１６×８、８×１６の各変換サイズの周波数変換が禁止変換リストに追加される。
【００８３】
パーティションｂ、ｃは、大きさは３２×１６画素であり階層Ｌ１に属している。上記の禁止変換リストの生成手順を適用すると、手順Ｓ５１で４×４、８×１、１×８、手順Ｓ６１で４×４、８×８、１６×１６、手順Ｓ６２で１×１６、８×１６の各変換サイズの周波数変換が禁止変換リストに追加される。
【００８４】
パーティションｄ、ｅは、大きさは１６×３２画素であり階層Ｌ１に属している。上記の禁止変換リストの生成手順を適用すると、手順Ｓ５１で４×４、８×１、１×８、手順Ｓ６４で４×４、８×８、１６×１６、手順Ｓ６５で１６×１、１６×８の各変換サイズの周波数変換が禁止変換リストに追加される。
【００８５】
パーティションｆの大きさは１６×１６画素であり階層Ｌ２に属している。上記の禁止変換リストの生成手順を適用すると、手順Ｓ５１で４×４、８×１、１×８、手順Ｓ６７で１６×１、１×１６、１６×８、８×１６の各変換サイズの周波数変換が禁止変換リストに追加される。
【００８６】
パーティションｇ，ｈの大きさは１６×８画素であり階層Ｌ２に属している。上記の禁止変換リストの生成手順を適用すると、手順Ｓ４１で１６×１６、１×１６、８×１６、手順Ｓ６１で４×４、８×８、１６×１６、手順Ｓ６２で１×１６、８×１６の各変換サイズの周波数変換が禁止変換リストに追加される。
【００８７】
パーティションｉ，ｊの大きさは８×１６画素であり階層Ｌ２に属している。上記の禁止変換リストの生成手順を適用すると、手順Ｓ４１で１６×１６、１６×１、１６×８、手順Ｓ６４で４×４、８×８、１６×１６、手順Ｓ６５で１６×１、１６×８の各変換サイズの周波数変換が禁止変換リストに追加される。
【００８８】
パーティションｋ、ｌ、ｍ、ｎの大きさは８×８画素であり階層Ｌ３に属している。上記の禁止変換リストの生成手順を適用すると、手順Ｓ４１で１６×１６、１６×１、１６×８、１×１６、８×１６、手順Ｓ６７で１６×１、１６×８、１×１６、８×１６、手順５ｂで８×８、１６×１６の各変換サイズの周波数変換が禁止変換リストに追加される。
【００８９】
上記の例のように、他のパーティション構造を有する拡張ＭＢに対しても、拡張ＭＢ内の各パーティションに対して禁止変換リストを生成して、変換制約として出力できる。
なお、上記説明では、禁止変換リスト生成手順において、手順Ｓ４２、手順Ｓ４３、手順Ｓ４４の全てを実行するものとしたが、それらの一部のみを用いても良い。また、手順Ｓ４２の詳細手順では、手順Ｓ５０の判定と手順Ｓ５１の判定のいずれか一方のみを実行しても良い。また、手順Ｓ４３の詳細手順では、判定に関して、手順Ｓ６０、手順６３、手順６６の各判定の一部のみを実行しても良いし、判定後の処理に関して、手順Ｓ６１と手順Ｓ６２のいずれか一方、手順Ｓ６４と手順Ｓ６５のいずれか一方のみを実行しても良い。また、手順Ｓ４４の詳細手順では、手順Ｓ７０と手順７２の判定のいずれか一方のみを実行しても良い。そのような手順省力を行った場合、禁止変換リスト生成に要する計算処理が軽減できる。
【００９０】
＜周波数変換決定部１０５＞
周波数変換決定部１０５は、入力される変換制約を利用して、拡張ＭＢ内の各パーティションにおいて適用する周波数変換を決定し、その情報を変換選択フラグとして出力する。特定のパーティションｐにおいて適用する周波数変換を決定する手順は次の通りである。
（手順Ｓ１２０）パーティションｐに対応する禁止変換リストＬｐを変換制約から抽出する。
（手順Ｓ１２１）変換プリセットと、禁止変換リストＬｐの差集合をとって、変換候補リストＣｐとする。
【００９１】
（手順Ｓ１２２）変換候補リストＣｐが空集合であった場合は、変換プリセットに含まれる正方形の変換サイズの周波数変換のうち最小の変換サイズの周波数変換を変換候補リストＣｐに追加する。この手順は、禁止変換リストが変換プリセットと一致した場合に適用すべき周波数変換が存在しない状況を避けるために必要である。変換プリセットと一致しない禁止変換リストが常に生成される場合には、この手順は無くても良い。
（手順Ｓ１２３）変換候補リストＣｐに含まれる各周波数変換を適用した場合のレート歪コストを計算して、レート歪コストを最小とする周波数変換を、パーティションｐにおいて適用する周波数変換とする。
【００９２】
＜可変長符号化部１０８＞
可変長符号化部１０８は、入力される変換係数と予測パラメータと変換制約と変換選択フラグに基づいて、拡張ＭＢにおける変換係数と予測パラメータと変換選択フラグに対応する符号化データを生成して出力する。
変換係数と予測パラメータは従来通りの方法で可変長符号化されて出力される。変換選択フラグは変換制約を利用して可変長符号化されて出力される。以下、変換選択フラグの可変長符号化手順について図１０のフロー図を参照して説明する。
【００９３】
（手順Ｓ８０）拡張ＭＢにおける階層Ｌ０の分割方法が四分割以外であれば、手順Ｓ８１の処理を実行し、それ以外であれば手順Ｓ８２〜手順Ｓ９２の処理を実行する。
（手順Ｓ８１）階層Ｌ０の処理単位（６４×６４画素）内の各パーティションに適用する周波数変換を示す情報を可変長符号化して、処理を終了する。
（手順Ｓ８２）階層Ｌ０の処理単位を四分割して得られる階層Ｌ１の各処理単位（３２×３２画素）それぞれに対して、以下の手順Ｓ８３〜手順Ｓ９２の処理を実行する。
【００９４】
（手順Ｓ８３）現在の処理単位（３２×３２画素）における階層Ｌ１の分割方法が四分割以外であれば、手順Ｓ８４へ進み、それ以外であれば手順Ｓ８５へ進む。
（手順Ｓ８４）現在の処理単位（３２×３２画素）内の各パーティションに適用する周波数変換を示す情報を可変長符号化して、手順Ｓ９２に進む。
（手順Ｓ８５）階層Ｌ１の処理単位（３２×３２画素）を四分割して得られる階層Ｌ２の各処理単位（１６×１６画素）それぞれに対して、以下の手順Ｓ８６〜手順Ｓ９１の処理を適用する。
【００９５】
（手順Ｓ８６）現在の処理単位（１６×１６画素）における階層Ｌ２の分割方法が四分割以外であれば、手順Ｓ８７へ進み、それ以外であれば手順Ｓ８８へ進む。
（手順Ｓ８７）現在の処理単位（１６×１６画素）内の各パーティションに適用する周波数変換を示す情報を可変長符号化して、手順Ｓ９１に進む。
（手順Ｓ８８）階層Ｌ２の処理単位を四分割して得られる階層Ｌ３の各処理単位（８×８画素）それぞれに対して、以下の手順Ｓ８９〜手順Ｓ９０の処理を実行する。
（手順Ｓ８９）現在の処理単位（８×８画素）内の各パーティションに適用する周波数変換を示す情報を可変長符号化して、手順Ｓ９０に進む。
【００９６】
（手順Ｓ９０）全ての処理単位（８×８画素）の処理が終了していれば手順Ｓ９１に進む。そうでなければ、次の処理単位（８×８画素）を設定して、手順Ｓ８９に進む
（手順Ｓ９１）全ての処理単位（１６×１６画素）の処理が終了していれば手順Ｓ９２に進む。そうでなければ、次の処理単位（１６×１６画素）を設定して、手順Ｓ８６に進む
（手順Ｓ９２）全ての処理単位（３２×３２画素）の処理が終了していれば処理を終了する。そうでなければ次の処理単位（３２×３２画素）を設定して、手順Ｓ８３に進む
【００９７】
特定のパーティションｐに対応する変換選択フラグの可変長符号化は、以下の手順で実行される。
（手順Ｓ１３０）パーティションｐに対応する禁止変換リストＬｐを変換制約から抽出する。
（手順Ｓ１３１）変換プリセットと、禁止変換リストＬｐの差集合をとって、変換候補リストＣｐとする。
【００９８】
（手順Ｓ１３２）変換候補リストＣｐが空集合であった場合は、変換プリセットに含まれる正方形の変換サイズの周波数変換のうち最小の変換サイズの周波数変換を数変換候補リストＣｐに追加する。この手順で追加する周波数変換は上記の周波数変換に限らず、変換プリセットに含まれる他のパーティションｐより小さい変換サイズの周波数変換であっても良い。ただし、周波数変換決定部の手順Ｓ１２２で用いたのと同一の周波数変換である必要がある。
（手順Ｓ１３３）変換候補リストＣｐに含まれる周波数変換の数が１個のみの場合は、可変長符号化処理を終了する。この場合、パーティションｐに適用する周波数変換を示す情報を符号化データに含まなくても、データの復号時にはいずれの周波数変換を適用すべきかが一意に特定できるため、問題は生じない。
（手順Ｓ１３４）変換候補リストＣｐに含まれる周波数変換を所定の順序で並べ換えて０から始まり１ずつ増加するインデックスを対応付ける。
【００９９】
（手順Ｓ１３５）パーティションｐに適用する周波数変換に関連付けられたインデックスを可変長符号化する。インデックスの可変長符号化方法として、例えば、周波数変換候補リストの要素数ｓとした場合に２のｔ乗がｓ以上となる最小のｔを用いて、インデックス値のｔビットで２進化して得られるビット列を符号化データとする方法が適用できる。
【０１００】
周波数変換候補リストの要素数が少なければインデックスの符号化に要する符号量は小さくなる。すなわち、禁止変換を各パーティションに設定することで、変換選択フラグの符号化に要する符号量を削減できる。また、周波数変換候補リストの要素数が少なければ、適用する周波数変換を選択するための符号化処理の演算量を削減することができる。
【０１０１】
なお、上記手順Ｓ１３４における所定の順序とは、例えば大きい変換サイズの周波数変換に対して小さい変換サイズの周波数変換よりも小さいインデックス、変換サイズが正方形である場合に横長矩形である場合よりも小さいインデックス、変換サイズが横長矩形である場合に縦長矩形である場合よりも小さいインデックスが付加されるような順序を用いることができる。この場合、１６×１６ＤＣＴ、１６×８ＤＣＴ、８×１６ＤＣＴ、８×８ＤＣＴ、４×４ＤＣＴ、１６×１ＤＣＴ、１×１６ＤＣＴ、８×１ＤＣＴ、１×８ＤＣＴの順に小さいインデックスが対応付けられ易くなる。
【０１０２】
別の例として、上記手順Ｓ１３４における所定の順序を、各周波数変換の選択頻度の高い順とすることもできる。具体的には、入力動画像の符号化処理を始めた後にパーティションの変換として変換プリセット中の各変換が何回選択されたかを計数しておき、選択回数が多い周波数変換に対してより小さいインデックスが割り当てられるような順序を作る。この場合、インデックスの発生頻度にも偏りが生じるため、手順Ｓ１３５でインデックスを可変長符号化した際の符号量が減少する。なお、新しいフレームの符号化開始時や、所定の個数の拡張ＭＢの集合であるスライスの符号化開始時等の適当なタイミングで、上記選択回数の係数値をゼロ等の規定値に初期化しても良い。また、条件付きの周波数変換選択回数、例えば、パーティションサイズ毎の各周波数変換の選択回数を計数しておき利用しても良い。
【０１０３】
また、上記手順Ｓ１３５におけるインデックスの可変長符号化に別の方法を用いても良い。例えばＨ．２６４／ＡＶＣで規定されている各種ＶＬＣや、ＣＡＢＡＣ等を用いることもできる。
【０１０４】
なお、インデックスはそのまま可変長符号化するのではなく、インデックス予測値と一致するか否かのフラグを符号化し、該フラグが一致しないことを示す場合のみインデックスを可変長符号化してもよい。符号化済の拡張ＭＢの情報（局所復号画像、パーティション構造、動きベクトル等）を用いて処理対象パーティションで利用される周波数変換を推定し、その周波数変換に対応するインデックスをインデックス予測値とできる。特に、周波数変換の空間相関を考慮して、処理対象パーティション近傍のパーティションで適用される周波数変換に基づいて、インデックス予測値を導出することが好ましい。具体的には、処理対象パーティションの左、上、右上に位置する各パーティションで適用される周波数変換のインデックスをそれぞれ導出する。そして、それらのインデックスの２個以上が一致すればその値をインデックス予測値とし、それ以外ならば、それらのインデックスの中で最小の値をインデックス予測値とする方式が好ましい。
【０１０５】
また、上記の変換選択フラグの可変長符号化手順では、全てのパーティションに対する変換選択フラグを可変長符号化すると説明したが、特定の階層Ｌｘの同一処理単位に属する各パーティションに対して適用する周波数変換は共通とする制約を課した上で、処理単位内パーティション共通の変換選択フラグを階層Ｌｘの処理単位毎に１個可変長符号化しても良い。その場合、周波数変換の選択の自由度は低下するが、パーティション毎に変換選択フラグを符号化する必要がなく、階層Ｌｘの処理単位毎に変換選択フラグを符号化すれば良いため、変換選択フラグの符号化に要する符号量を低減できる。逆に、変換候補リストに含まれる最大の変換サイズの周波数変換よりも小さくならない単位にパーティションをさらに分割し、その単位で変換選択フラグを符号化してもよい。
【０１０６】
＜予測残差再構築部１０９＞
予測残差再構築部１０９は、入力される変換係数と変換選択フラグに基づいて、変換係数を逆周波数変換することで予測残差を再構築して出力する。なお、変換係数が量子化されている場合には、周波数変換の適用に先立って逆量子化を適用する。
【０１０７】
＜局所復号画像生成部１１０＞
局所復号画像生成部１１０は、入力される予測画像と予測残差に基づいて局所復号画像を生成して出力する。局所復号画像の各画素値は、予測画像と予測残差の対応する画素間の画素値の和となる。なお、局所復号画像に対して、ブロック境界に発生するブロック歪低減や、量子化誤差低減を目的としてフィルタを適用してもよい。
【０１０８】
＜動画像符号化装置１０の動作＞
続いて、動画像符号化装置１０の動作について説明する。
（手順Ｓ１００）外部から動画像符号化装置１０に入力された入力動画像は、拡張ＭＢを単位として予測パラメータ決定部１０２および予測残差生成部１０６に順次入力されて、各拡張ＭＢについて、以降のＳ１０１〜Ｓ１０９の処理が順に実行される。
（手順Ｓ１０１）予測パラメータ決定部１０２では、処理対象拡張ＭＢについて、入力された入力動画像に基づいて予測パラメータが決定されて、予測画像生成部１０３および可変長符号化部１０８に出力される。
【０１０９】
（手順Ｓ１０２）予測画像生成部１０３では、入力された予測パラメータおよびフレームメモリ１０１に記録されている局所復号画像に基づいて、入力動画像における処理対象拡張ＭＢの領域を近似する予測画像が生成されて予測残差生成部１０６および局所復号画像生成部１１０に出力される。
【０１１０】
（手順Ｓ１０３）予測残差生成部１０６では、入力された入力動画像と予測画像に基づいて、処理対象拡張ＭＢに対応する予測残差が生成されて、周波数変換決定部１０５および変換係数生成部１０７に出力される。
（手順Ｓ１０４）変換制約導出部１０４では、入力された予測パラメータに基づいて、処理対象拡張ＭＢの各パーティションにおける周波数変換に関する制約が変換制約として導出されて、周波数変換決定部１０５および可変長符号化部１０８に出力される。
【０１１１】
（手順Ｓ１０５）周波数変換決定部１０５では、入力された変換制約と予測残差に基づいて、処理対象拡張ＭＢの各パーティションに適用する周波数変換が決定されて、変換選択フラグとして変換係数生成部１０７および可変長符号化部１０８および予測残差再構築部１０９に出力される。
（手順Ｓ１０６）変換係数生成部１０７では、入力された変換選択フラグにより規定される周波数変換が、入力された予測残差に適用されて、処理対象拡張ＭＢに対応する変換係数が生成されて、可変長符号化部１０８および予測残差再構築部１０９に出力される。
【０１１２】
（手順Ｓ１０７）予測残差再構築部１０９では、入力された変換選択フラグにより規定される周波数変換に対応する逆周波数変換が、入力された変換係数に適用されて、処理対象拡張ＭＢに対応する予測残差が再構築されて、局所復号画像生成部１１０に出力される。
（手順Ｓ１０８）局所復号画像生成部１１０では、入力された予測残差と予測画像に基づいて局所復号画像が生成されてフレームメモリ１０１に出力されて記録される。
【０１１３】
（手順Ｓ１０９）可変長符号化部１０８では、入力された変換制約を利用して、入力された変換係数および予測パラメータおよび変換選択フラグが可変長符号化されて、符号化データとして外部に出力される。
上記の手順により、動画像符号化装置１０では、入力された入力動画像を符号化して符号化データを生成し、外部に出力できる。
【０１１４】
＜動画像復号装置２０の構成＞
次に、動画像符号化装置１０で符号化された符号化データを復号して復号動画像を生成する動画像復号装置２０について説明する。
図１１は画像復号装置２０の構成を表すブロック図である。動画像復号装置２０はフレームメモリ１０１、予測画像生成部１０３、変換制約導出部１０４、予測残差再構築部１０９、局所復号画像生成部１１０および可変長符号復号部２０１より構成される。
可変長符号復号部２０１は、入力される符号化データと変換制約に基づいて、予測パラメータおよび変換選択フラグおよび変換係数を復号して出力する。具体的には、まず、符号化データから予測パラメータを復号して出力する。次に、変換制約を利用して、符号化データから変換選択フラグを復号して出力する。最後に、変換選択フラグを利用して、符号化データから変換係数を復号して出力する。
【０１１５】
＜動画像復号装置２０の動作＞
続いて、動画像復号装置２０の動作について説明する。
（手順Ｓ１１０）外部から動画像復号装置２０に入力された符号化データは、拡張ＭＢを単位として可変長符号復号部２０１に順次入力されて、各拡張ＭＢに対応する符号化データに対して、以降のＳ１１１〜Ｓ１１７の処理が順に実行される。
（手順Ｓ１１１）可変長符号復号部２０１では、入力された符号化データから、処理対象拡張ＭＢに対応する予測パラメータが復号されて、予測画像生成部１０３および変換制約導出部１０４へ出力される。
【０１１６】
（手順Ｓ１１２）変換制約導出部１０４では、入力された予測パラメータに基づいて、処理対象拡張ＭＢの各パーティションにおける周波数変換に関する制約が変換制約として導出されて、可変長符号復号部２０１に出力される。
（手順Ｓ１１３）可変長符号復号部２０１では、入力された符号化データと変換制約に基づいて、処理対象ＭＢに対応する変換選択フラグが復号されて、予測残差再構築部１０９へ出力される。
【０１１７】
（手順Ｓ１１４）可変長符号復号部２０１では、入力された符号化データと（手順Ｓ１１３）で導出した変換選択フラグに基づいて、処理対象拡張ＭＢに対応する変換係数が復号されて、予測残差再構築部１０９へ出力される。
（手順Ｓ１１５）予測画像生成部１０３では、入力された予測パラメータおよびフレームメモリ１０１に記録されている局所復号画像に基づいて、処理対象拡張ＭＢに対応する予測画像が生成されて局所復号画像生成部１１０に出力される。
【０１１８】
（手順Ｓ１１６）予測残差再構築部１０９では、入力された変換選択フラグにより規定される周波数変換に対応する逆周波数変換が、入力された変換係数に適用されて、処理対象拡張ＭＢに対応する予測残差が再構築されて、局所復号画像生成部１１０に出力される。
（手順Ｓ１１７）局所復号画像生成部１１０では、入力された予測残差と予測画像に基づいて局所復号画像が生成されてフレームメモリ１０１に出力されて記録されるとともに、処理対象ブロックに対応する復号動画像上の領域として外部に出力される。
【０１１９】
以上説明したように、動画像復号装置２０によれば、動画像符号化装置１０で生成された符号化データから復号動画像を生成することができる。
【０１２０】
＜付記事項１：パーティションサイズや属する階層以外の情報の利用について＞
なお、上記動画像符号化装置１０や動画像復号装置２０の説明において、拡張ＭＢ内のパーティション毎の禁止変換リストは、パーティションサイズやパーティションの属する階層にのみ基づいて生成されるものとして説明を行ったが、符号化データに含まれた情報に基づいて復号時に再現可能な別の情報を用いても良い。例えば、予測パラメータに含まれる動きベクトルや参照画像インデックスを禁止変換リストの導出に用いることもできる。
【０１２１】
特定のパーティションｐにおいて動きベクトルと参照画像インデックスを用いて禁止変換リストへ周波数変換を追加する手順を以下に示す。なお、パーティションｐの動きベクトルをｍｖｐ、参照画像インデックスをｒｅｆｐとする。また、パーティションｐの上辺に隣接するパーティションの中で左端に位置するパーティション（パーティションｕ）の動きベクトルをｍｖｕ、参照画像インデックスをｒｅｆｕとする。また、パーティションｐの左辺に隣接するパーティションの中で上端に位置するパーティション（パーティションｌ）の動きベクトルをｍｖｌ、参照画像インデックスをｒｅｆｌと定義する。
【０１２２】
（手順Ｓ１４０）ｍｖｐとｍｖｕとｍｖｌが全て一致し、かつ、ｒｅｆｐとｒｅｆｕとｒｅｆｌが全て一致する場合は手順Ｓ１４１へ進む。それ以外の場合は処理を終了する。
（手順Ｓ１４１）周波数変換リスト内で類似関係の変換サイズを有する周波数変換が２個以上存在する場合、それぞれの類似関係の変換サイズを有する周波数変換の組の中で変換サイズが最小である周波数変換をＬｐに追加して処理を終了する．
【０１２３】
隣接ブロック間で動きベクトルが一致することは、符号化対象の拡張ＭＢ近傍の局所領域において動きベクトルの空間相関が高いことを意味する。動きベクトルの空間相関が高い場合には画素値の空間相関も高い傾向があるため、類似の変換サイズを有する周波数変換の中で小さい変換サイズの周波数変換の適用を禁止しても符号化データの符号量増加はわずかである。
【０１２４】
なお、上記説明では禁止変換リスト導出に用いる動きベクトルや参照画像インデックスをパーティションｐの隣接パーティションの動きベクトルや参照画像インデックスであるとしたが、別の動きベクトルを用いることもできる。例えば、パーティションｐが属する拡張ＭＢ（処理対象拡張ＭＢ）に隣接する拡張ＭＢ内の動きベクトルを用いてもよい。具体的には、処理対象拡張ＭＢの左側に隣接する拡張ＭＢ内で右上に位置するパーティションの動きベクトルをｍｖｌ、処理対象拡張ＭＢの上側に隣接する拡張ＭＢ内で左下に位置するパーティションの動きベクトルをｍｖｕとして用いる。この場合、拡張ＭＢ内の全パーティションで同一のｍｖｌ、ｍｖｕが利用されるため、手順Ｓ１４０、Ｓ１４１の処理がパーティションを単位として並列実行可能となる。  
【０１２５】
＜付記事項２：禁止変換リストの生成タイミングについて＞
なお、上記動画像符号化装置１０や動画像復号装置２０の説明において、変換制約導出部１０４は拡張ＭＢのパーティション毎に随時禁止変換リストの生成処理を実行するものと説明したが、禁止変換リストへの周波数変換の追加がパーティションサイズやパーティションの属する階層のみに基づいて実行される場合には、所定のタイミングで事前に禁止周波数変換リストを生成しておいても良い。その場合、パーティションの種類毎に事前に生成された禁止変換リストを変換制約導出部１０４において拡張ＭＢ内の各パーティションに関連付ける必要がある。前記所定のタイミングとは、入力動画像の符号化開始または符号化データの復号開始直後であっても良いし、シーケンス、フレーム、スライス等の所定の符号化単位の符号化または復号処理の開始直後であっても良い。禁止変換リストの生成処理の実行回数を減らせるため、符号化および復号処理の処理量を低減できる。
【０１２６】
逆に、禁止変換リストへの周波数変換の追加の際に動きベクトルや参照画像インデックスを用いる場合には、上記動画像符号化装置１０や動画像復号装置２０で説明したように拡張ＭＢ毎に随時禁止変換リストの生成処理を実行する必要がある。この場合、禁止変換リストの生成処理回数の増加により符号化および復号処理の処理量は増加するが、ＭＢ毎に生成処理を実行しない場合に較べて、符号化データより導出できるより多くの情報を用いることにより、より動画像の局所的性質に適合した禁止変換リストを生成できる。
【０１２７】
（実施形態２）
次に、本発明による動画像符号化装置および動画像復号装置の別の一実施形態である動画像符号化装置１１および動画像復号装置２１について図１２〜図１４を参照しながら説明する。なお、図面の説明においては、同一要素には同一符号を付与して説明を省略する。
本実施形態における動画像符号化装置１１および動画像復号装置２１では、動画像符号化装置１０や動画像復号装置２０における変換制約導出部１０４を変換候補導出部１１１により置き換えることで、禁止変換リストを生成せずに、変換候補リストを直接導出することを特徴としている。
【０１２８】
なお、変換制約導出部１０４と変換候補導出部１１１を合わせて、変換制御導出部と呼ぶ。
【０１２９】
図１２は動画像符号化装置１１の構成を示すブロック図である。動画像符号化装置１１は、フレームメモリ１０１、予測パラメータ決定部１０２、予測画像生成部１０３、予測残差生成部１０６、変換係数生成部１０７、予測残差再構築部１０９、局所復号画像生成部１１０、変換候補導出部１１１、周波数変換決定部１１２、可変長符号化部１１３より構成される。
【０１３０】
変換候補導出部１１１は、入力される予測パラメータに基づいて、拡張ＭＢ内の各パーティションにおいて選択可能な周波数変換に関する情報を変換候補リストとして出力する。すなわち、予測パラメータにより決定される各パーティションのパーティション形状情報に基づいて、そのパーティションの変換候補リストを生成する。
変換候補リストは、拡張ＭＢ内の各パーティションにそれぞれ対応付けられており、変換プリセットに含まれる周波数変換の中で、各パーティションで選択可能な周波数変換の集合を規定する。
【０１３１】
特定のパーティションｐに対する変換候補リストＣｐは次の手順で生成される。なお、パーティションｐの大きさをＭ×Ｎ画素（横Ｍ画素、縦Ｎ画素）とする。また、パーティションｐは階層Ｌｘに属するとする。
（手順Ｓ１５０）ＭとＮの大小関係に応じて決定した周波数変換をＣｐに追加する。
（手順Ｓ１５１）Ｃｐが空である場合に全てのパーティションサイズよりも小さい変換サイズを持つ周波数変換の中で、最も大きい変換サイズの周波数変換をＣｐに追加する。
【０１３２】
上記手順Ｓ１５０のさらに詳細な手順を図１３のフロー図を参照して説明する。
（手順Ｓ１６０）所定の値Ｔｈ３（例えば以下ではＴｈ３＝１６）を用いて、Ｍ１にＭｉｎ（Ｍ、Ｔｈ３）の値、Ｎ１にＭｉｎ（Ｎ，Ｔｈ３）の値を設定する。なお、Ｔｈ３の値は、変換プリセットに含まれる最大の正方形の変換サイズの周波数変換における変換サイズの一辺の長さに設定することが好ましい。変換サイズＭ１×Ｎ１の変換サイズを持つ周波数変換が変換プリセットに存在すれば、その周波数変換を変換候補リストＣｐに追加して、手順Ｓ１６１へ進む。
【０１３３】
（手順Ｓ１６１）ＭがＮより大きい場合（パーティションｐが横長矩形の場合）手順Ｓ１６２へ進み、それ以外であれば手順Ｓ１６３へ進む。
（手順Ｓ１６２）変換サイズＭ１×１の変換サイズを持つ周波数変換が変換プリセットに存在すれば、その周波数変換を変換候補リストＣｐに追加して処理を終了する。
（手順Ｓ１６３）ＭがＮより小さい場合（パーティションｐが縦長矩形の場合）手順Ｓ１６４へ進み、それ以外であれば手順Ｓ１６５へ進む。
【０１３４】
（手順Ｓ１６４）変換サイズ１×Ｎ１の変換サイズを持つ周波数変換が変換プリセットに存在すれば、その周波数変換を変換候補リストＣｐに追加して処理を終了する。
（手順Ｓ１６５）Ｍ２にＭ１÷２の値、Ｎ２にＮ１÷２の値を設定する。変換サイズＭ２×Ｎ２の変換サイズを持つ周波数変換が変換プリセットに存在すれば、その周波数変換を変換候補リストＣｐに追加して処理を終了する。なお、この手順はＭとＮが等しい場合（パーティションｐが正方形の場合）に実行される。
上記、ＭとＮの大小関係、パーティションサイズＭｘＮはパーティション形状情報である。
【０１３５】
上記の手順においては、横長矩形（縦長矩形）のパーティションに対し、変換プリセットに存在すれば、パーティションの高さ（幅）より縦（横）の長さが短い変換サイズの周波数変換が変換候補リストＣｐに追加される。動画像符号化装置１０の変換制約導出部１０４における禁止変換リストの導出手順の説明において図６を参照して言及した通り、横長矩形（縦長矩形）のパーティションに対しては、横長矩形（縦長矩形）の変換サイズの周波数変換が有効である。特に、短い辺の長さが長い辺に較べて極端に短い変換サイズの周波数変換を用いることで、変換サイズ内に物体の境界が存在する場合を少なくすることができ、周波数変換による変換係数の低周波数成分へのエネルギー集中効果を高めることができる。
【０１３６】
周波数変換決定部１１２は、入力される変換候補リストを利用して、拡張ＭＢ内の各パーティションにおいて適用する周波数変換を決定し、その情報を変換選択フラグとして出力する。具体的には、変換候補リストＣｐに含まれる各周波数変換を適用した場合のレート歪コストを計算して、レート歪コストを最小とする周波数変換を、パーティションｐにおいて適用する周波数変換とする。
【０１３７】
可変長符号化部１１３は、入力される変換係数と予測パラメータに可変長符号化と変換候補リストと変換選択フラグに基づいて、拡張ＭＢにおける変換係数と予測パラメータと変換選択フラグに対応する符号化データを生成して出力する。
【０１３８】
拡張ＭＢ内の各パーティションにおける変換選択フラグの可変長符号化手順は、動画像符号化装置１０の可変長符号化部１０８における手順Ｓ８０〜手順Ｓ９２（図１０）で示した通りである。特定のパーティションｐにおける詳細な変換選択フラグの可変長符号化手順としては、可変長符号化部１０８における手順Ｓ１３３〜手順Ｓ１３５を適用する。
【０１３９】
続いて、動画像符号化装置１１の動作について説明する。
（手順Ｓ１７０）外部から動画像符号化装置１１に入力された入力動画像は、拡張ＭＢを単位として予測パラメータ決定部１０２および予測残差生成部１０６に順次入力されて、各拡張ＭＢについて、以降のＳ１７１〜Ｓ１７９の処理が順に実行される。
（手順Ｓ１７１）予測パラメータ決定部１０２では、処理対象拡張ＭＢについて、入力された入力動画像に基づいて予測パラメータが決定されて、予測画像生成部１０３および可変長符号化部１１３に出力される。
【０１４０】
（手順Ｓ１７２）予測画像生成部１０３では、入力された予測パラメータおよびフレームメモリ１０１に記録されている局所復号画像に基づいて、入力動画像における処理対象拡張ＭＢの領域を近似する予測画像が生成されて予測残差生成部１０６および局所復号画像生成部１１０に出力される。
（手順Ｓ１７３）予測残差生成部１０６では、入力された入力動画像と予測画像に基づいて、処理対象拡張ＭＢに対応する予測残差が生成されて、周波数変換決定部１１２および変換係数生成部１０７に出力される。
【０１４１】
（手順Ｓ１７４）変換候補導出部１１１では、入力された予測パラメータに基づいて、処理対象拡張ＭＢの各パーティションにおける周波数変換に関する制約が導出されて、周波数変換決定部１１２および可変長符号化部１１３に出力される。
（手順Ｓ１７５）周波数変換決定部１１２では、入力された変換制約と予測残差に基づいて、処理対象拡張ＭＢの各パーティションに適用する周波数変換が決定されて、変換選択フラグとして変換係数生成部１０７および可変長符号化部１１３および予測残差再構築部１０９に出力される。
【０１４２】
（手順Ｓ１７６）変換係数生成部１０７では、入力された変換選択フラグにより規定される周波数変換が、入力された予測残差に適用されて、処理対象拡張ＭＢに対応する変換係数が生成されて、可変長符号化部１０８および予測残差再構築部１０９に出力される。
（手順Ｓ１７７）予測残差再構築部１０９では、入力された変換選択フラグにより規定される周波数変換に対応する逆周波数変換が、入力された変換係数に適用されて、処理対象拡張ＭＢに対応する予測残差が再構築されて、局所復号画像生成部１１０に出力される。
【０１４３】
（手順Ｓ１７８）局所復号画像生成部１１０では、入力された予測残差と予測画像に基づいて局所復号画像が生成されてフレームメモリ１０１に出力されて記録される。
（手順Ｓ１７９）可変長符号化部１１３では、入力された変換制約を利用して、入力された変換係数および予測パラメータおよび変換選択フラグが可変長符号化されて、符号化データとして外部に出力される。
上記の手順により、動画像符号化装置１１では、入力された入力動画像を符号化して符号化データを生成し、外部に出力できる。
【０１４４】
＜変換候補リスト生成方法の他の例＞
なお、上記の変換候補導出部１１１に関する説明で、変換候補リスト生成方法の一例を示したが、別の方法で変換候補リストを生成してもよい。例えば、変換プリセットに相似関係にある２個の周波数変換ＤＣＴａ、ＤＣＴｂ（ただしＤＣＴａの変換サイズはＤＣＴｂの変換サイズより大きい）が含まれる場合に、上位階層に含まれるパーティションに対する変換候補リストにはＤＣＴａを追加してＤＣＴｂを追加せず、下位階層に含まれるパーティションに対する変換候補リストにはＤＣＴｂを追加する、という変換候補リスト生成方法も有効である。より具体的には、変換プリセットに１６×１６ＤＣＴと８×８ＤＣＴが含まれる場合に、６４×６４画素を処理単位とする階層Ｌ０に含まれるパーティションに対する変換候補リストには少なくとも１６×１６ＤＣＴを追加して８×８ＤＣＴは追加せず、３２×３２画素を処理単位とする階層Ｌ１に含まれるパーティションに対する変換候補リストには少なくとも８×８ＤＣＴを追加する。
【０１４５】
特定の階層Ｌｘに属するパーティションで特定の周波数変換ＤＣＴｂ（例えば８×８ＤＣＴ）が選択できなくても、階層Ｌｘよりも下位の階層Ｌｙに属するパーティションにおいてＤＣＴｂが選択可能であれば、ＤＣＴｂが有効な領域では、上位階層Ｌｘに属するパーティションを選択せず、ＤＣＴｂが選択可能な下位階層Ｌｙに属するパーティションを選択することで、符号化データの符号量増加を抑制できる。特に、大きいパーティションに対しては、大きい変換サイズの周波数変換が有効であるという事実を踏まえて、上位階層Ｌｘに属するパーティションに対してはＤＣＴｂの選択を禁止する代わりに、より大きな変換サイズを有するＤＣＴａ（例えば１６×１６ＤＣＴ）を選択可能とし、一方で下位階層Ｌｙに属するパーティションに対してはＤＣＴｂを選択可能とすることが有効である。
【０１４６】
＜動画像復号装置２１の構成＞
次に、動画像符号化装置１１で符号化された符号化データを復号して復号動画像を生成する動画像復号装置２１について説明する。
図１４は画像復号装置２１の構成を表すブロック図である。動画像復号装置２０はフレームメモリ１０１、予測画像生成部１０３、予測残差再構築部１０９、局所復号画像生成部１１０、変換候補導出部１１１および可変長符号復号部２０２より構成される。
【０１４７】
可変長符号復号部２０２は、入力される符号化データと変換候補リストに基づいて、予測パラメータ、変換選択フラグおよび変換係数を復号して出力する。具体的には、まず、符号化データから予測パラメータを復号して出力する。次に、変換候補リストを利用して、符号化データから変換選択フラグを復号して出力する。最後に、変換選択フラグを利用して、符号化データから変換係数を復号して出力する。なお、変換選択フラグの復号時に、変換選択フラグが何ビットで符号化されているかを知る必要があるが、そのためには変換候補リストに含まれる要素の情報は必ずしも必要ではなく、変換候補リストに含まれる要素数のみが分かれば十分である。この場合、可変長符号復号部２０２に入力される信号および変換選択フラグの復号に用いられる信号は、変換候補リストのうち、変換候補リストに含まれる要素数に関する信号のみでも構わない。
【０１４８】
＜動画像復号装置２１の動作＞
続いて、動画像復号装置２１の動作について説明する。
（手順Ｓ１８０）外部から動画像復号装置２０に入力された符号化データは、拡張ＭＢを単位として可変長符号復号部２０１に順次入力されて、各拡張ＭＢに対応する符号化データに対して、以降のＳ１８１〜Ｓ１８７の処理が順に実行される。
（手順Ｓ１８１）可変長符号復号部２０２では、入力された符号化データから、処理対象拡張ＭＢに対応する予測パラメータが復号されて、予測画像生成部１０３および変換候補導出部１１１へ出力される。
【０１４９】
（手順Ｓ１８２）変換候補導出部１１１では、入力された予測パラメータに基づいて、処理対象拡張ＭＢの各パーティションにおける変換候補リストが導出されて、可変長符号復号部２０２に出力される。
（手順Ｓ１８３）可変長符号復号部２０２では、入力された符号化データと変換制約に基づいて、処理対象ＭＢに対応する変換選択フラグが復号されて、予測残差再構築部１０９へ出力される。
【０１５０】
（手順Ｓ１８４）可変長符号復号部２０２では、入力された符号化データと（手順Ｓ１８３）で導出した変換選択フラグに基づいて、処理対象拡張ＭＢに対応する変換係数が復号されて、予測残差再構築部１０９へ出力される。
（手順Ｓ１８５）予測画像生成部１０３では、入力された予測パラメータおよびフレームメモリ１０１に記録されている局所復号画像に基づいて、処理対象拡張ＭＢに対応する予測画像が生成されて局所復号画像生成部１１０に出力される。
【０１５１】
（手順Ｓ１８６）予測残差再構築部１０９では、入力された変換選択フラグにより規定される周波数変換に対応する逆周波数変換が、入力された変換係数に適用されて、処理対象拡張ＭＢに対応する予測残差が再構築されて、局所復号画像生成部１１０に出力される。
（手順Ｓ１８７）局所復号画像生成部１１０では、入力された予測残差と予測画像に基づいて局所復号画像が生成されてフレームメモリ１０１に出力されて記録されるとともに、処理対象ブロックに対応する復号動画像上の領域として外部に出力される。
【０１５２】
＜デコーダまとめ＞
以上説明したように、動画像復号装置２１によれば、動画像符号化装置１１で生成された符号化データから復号動画像を生成することができる。
【０１５３】
（実施形態３）
次に、本発明による動画像符号化装置および動画像復号装置の別の一実施形態である動画像符号化装置３０および動画像復号装置４０について図１５〜図１６を参照しながら説明する。なお、図面の説明においては、同一要素には同一符号を付与して説明を省略する。また、動画像符号化装置３０および動画像復号装置４０において利用可能なパーティション構造や変換プリセットは、動画像符号化装置１１および動画像復号装置２１で用いたものと同じとする。
本実施形態における動画像符号化装置３０や動画像復号装置４０では、動画像のシーン、フレーム、スライスといったＭＢより大きい所定の単位で変換候補導出部による変換候補リストの導出方法を動画像の性質に合わせて適応的に変更する機能を備える点が、動画像符号化装置１１や動画像復号装置２１と異なる。
【０１５４】
図１５は動画像符号化装置３０の構成を示すブロック図である。動画像符号化装置３０は、フレームメモリ１０１、予測パラメータ決定部１０２、予測画像生成部１０３、予測残差生成部１０６、変換係数生成部１０７、予測残差再構築部１０９、局所復号画像生成部１１０、周波数変換決定部１１２、変換候補リスト導出ルール決定部３０１、変換候補導出部３０２、可変長符号化部３０３より構成される。
【０１５５】
変換候補リスト導出ルール決定部３０１は、シーン、フレーム、スライス等のＭＢより大きい所定の単位で入力される入力動画像に基づいて、変換候補導出部における変換候補リスト導出方法を規定または更新する変換候補リスト導出ルールを生成する。なお、以下では説明の簡単のため、変換候補リスト導出ルールはフレーム毎に生成されるものとして説明する。
【０１５６】
（変換候補リスト導出ルールの定義）
変換候補リスト導出ルールは、以下に示す基礎ルールの組み合わせとして定義する。
・基礎ルール１：所定のパーティションＡに対して変換プリセット内の所定の周波数変換Ｂを変換候補リストへ追加することを規定する。なお、以下では基礎ルール１を、［許可、パーティションＡ、周波数変換Ｂ］という形式で記載する。例えば、［許可、６４×６４、Ｔ１６×１６］は、６４×６４のパーティションに対してＴ１６×１６の周波数変換を変換候補リストへ追加することを示す。
【０１５７】
・基礎ルール２：所定のパーティションＡに対して変換プリセット内の所定の周波数変換Ｂを変換候補リストへ含めることを禁止することを規定する。なお、以下では基礎ルール２を、［禁止、パーティションＡ、周波数変換Ｂ］という形式で記載する。例えば、［禁止、６４×６４、Ｔ４×４］は、６４×６４の大きさパーティションに対してＴ４×４を禁止して、変換候補リストに含めないことを示す。
【０１５８】
・基礎ルール３：所定のパーティションＡに対して変換プリセット内の所定の周波数変換Ｂが変換候補リストへ含まれている場合に、変換候補リスト中の周波数変換Ｂを別の周波数変換Ｃで置き換えることを規定する。なお、以下では基礎ルール３を、［置換、パーティションＡ、周波数変換Ｂ、周波数変換Ｃ］という形式で記載する。例えば、［置換、６４×３２、Ｔ４×４、Ｔ１６×１］は、６４×３２の大きさのパーティションに対してＴ４×４が変換候補リストに含まれる場合に、Ｔ４×４を変換候補リストから除外して、代わりにＴ１６×１を変換候補リストに加えることを示す。
【０１５９】
すなわち、変換候補リスト導出ルールには複数の基礎ルールが含まれており、各基礎ルールは、上記基礎ルール１〜３のいずれかに分類される。
なお、変換候補リスト導出ルールにおいて、基礎ルールに加えて、もしくは、基礎ルールの代替として、基礎ルールの組み合わせにより表現される複合ルールを含めてもよい。以下、いくつかの複合ルールの例を挙げる。
【０１６０】
・複合ルール１：特定の階層に属するパーティションで特定の変換を禁止する。例えば、Ｌ０階層でＴ８×８以下の大きさの変換を禁止するというルールがこの複合ルール１に相当する。上記複合ルール（Ｒ１）は、次のような基礎ルールの集合として表現できる。
Ｒ１＝｛［禁止、Ｐ、Ｔ］：（ＰはＬ０階層に属するパーティション）∧（ＴはＴ８×８以下の周波数変換）｝
また、所定の階層より上位の階層で類似関係にある周波数変換の中でサイズの小さい周波数変換を禁止するというルール、より具体的には、階層Ｌ１よりも上位の階層で類似関係にあるＴ１６×１６、Ｔ８×８、Ｔ４×４の各変換のうち、Ｔ８×８およびＴ４×４を禁止するというルール、もこの複合ルール１に相当する。
【０１６１】
・複合ルール２：特定の形状のパーティションでは、特定の変換Ａを特定の変換Ｂに置き換える。例えば、正方形のパーティションでは長方形の周波数変換を所定の正方形の周波数変換（例えばＴ４×４）に置き換えるというルールがこの複合ルール２に相当する。上記複合ルール（Ｒ２）は、次のような基礎ルールの集合として表現できる。
Ｒ２＝｛［置換、Ｐ、Ｔ、Ｔ４×４］：（Ｐ∈正方形のパーティション）∧（Ｔ∈長方形の周波数変換）｝
また、横長矩形のパーティションでは正方形の周波数変換を横長矩形の周波数変換に置き換えるというルールもこの複合ルール２に相当する。
【０１６２】
（変換候補リスト導出ルールの決定手順）
まず、基礎ルールおよび複合ルールを構成要素とするルール候補を符号化処理開始前にあらかじめ規定しておき、変換候補リスト導出ルールを空に設定する。次に、入力される各フレームに対し、ルール候補に含まれる各基礎ルールまたは複合ルールをそれぞれ適用して符号化処理を行った場合のレート歪コストを計算する。また、全てのルール候補を適用しない場合のレート歪コストＣ１も計算しておく。続いて、各基礎ルールまたは複合ルールを適用した場合のレート歪コストＣ２とコストＣ１を比較して、コストＣ２がコストＣ１より小さければ、当該基礎ルールまたは複合ルールを適用することを決定して、変換候補リスト導出ルールに含める。
上記の手順により、所定のルール候補のうち、フレームの符号化時に適用することでレート歪コストが低減され得る基礎ルールまたは複合ルールのみが、変換候補リスト導出ルールに追加される。
【０１６３】
変換候補導出部３０２は、入力される予測パラメータと変換候補リスト導出ルールに基づいて、拡張ＭＢ内の各パーティションにおいて選択可能な周波数変換に関する情報を変換候補リストとして出力する。変換候補リストは、拡張ＭＢ内の各パーティションにそれぞれ対応付けられており、変換プリセットに含まれる周波数変換の中で、各パーティションで選択可能な周波数変換の集合を規定する。なお、その際には、入力される変換候補リスト導出ルールも変換候補リスト導出処理に用いられる。
【０１６４】
入力された変換候補リスト導出ルールに基づいて、特定のパーティションｐに対する変換候補リストＣｐを生成する手順は次の通りである。なお、パーティションｐの大きさをＭ×Ｎ画素（横Ｍ画素、縦Ｎ画素）とする。
【０１６５】
（手順Ｓ２００）変換候補リスト導出ルールに複合ルールが含まれる場合、各複合ルールを基礎ルールに分解して変換候補リスト導出ルールに追加する。
（手順Ｓ２０１）変換候補リストに含まれる全ての基礎ルール１に属する基礎ルールに対して、手順Ｓ２０２の処理を実行する。
（手順Ｓ２０２）処理対象の基礎ルール１を［許可、Ｐ１、Ｔ１］と表わす。パーティションｐの形状とＰ１が一致する場合、変換候補リストに周波数変換Ｔ１を追加する。
（手順Ｓ２０３）変換候補リストに含まれる全ての基礎ルール２に属する基礎ルールに対して、手順Ｓ２０４の処理を実行する。
【０１６６】
（手順Ｓ２０４）処理対象の基礎ルール２を［禁止、Ｐ２、Ｔ２］と表わす。パーティションｐの形状とＰ２が一致し、かつ変換候補リストに周波数変換Ｔ２が存在している場合、周波数変換Ｔ２を変換候補リストから除去する。
（手順Ｓ２０５）変換候補リストに含まれる全ての基礎ルール３に属する基礎ルールに対して、手順Ｓ２０６の処理を実行する。
（手順Ｓ２０６）処理対象の基礎ルール２を［置換、Ｐ３、Ｔ３、Ｔ４］と表わす。パーティションｐの形状とＰ３が一致し、かつ変換候補リストに周波数変換Ｔ３が存在している場合、周波数変換Ｔ３を周波数変換Ｔ４に置き換える。
以上の手順により、変換候補導出部３０２において、入力される変換候補リスト導出ルールに従って変換候補リストを導出できる。
【０１６７】
可変長符号化部３０３は、入力される変換係数と予測パラメータと変換候補リストと変換選択フラグと変換候補リスト導出ルールそれぞれに対応する符号化データを生成して出力する。
変換候補リスト導出ルールに対応する符号化データの生成処理の詳細を説明する。符号化データは、変換候補リスト導出ルールに含まれる各基礎ルールまたは複合ルールを可変長符号化することで生成される。基礎ルールの可変長符号化では、まず対象の基礎ルールが基礎ルール１〜３のいずれに分類されるかを示す情報を符号化し、次に基礎ルールの適応対象であるパーティションを示す情報符号化する。最後に、基礎ルール１の場合は許可する周波数変換、基礎ルール２の場合は禁止する周波数変換、基礎ルール３の場合は置換前後の各周波数変換の種類を示す情報が符号化される。なお、どのような基礎ルールが変換候補リスト導出リストに含まれ得るかがあらかじめ決めっている場合には、上記の方法で基礎ルールを可変長符号化する代わりに、基礎ルールを適用するか否かの情報を符号化データとすることで符号量を削減できる。なお、特定の基礎ルールを常に適用することがあらかじめ決められている場合には、その基礎ルールを可変長符号化する必要はない。
【０１６８】
複合ルールは、基礎ルールに分解して符号化される。また、どのような複合ルールが変換候補リスト導出リストに含まれ得るかがあらかじめ決めっている場合には、複合ルールを適用するか否かの情報を符号化データとすることで符号量を削減できる。例えば、３２×３２より大きいパーティションにおいてＴ４×４およびＴ８×８を禁止するという複合ルールの適用有無を１ｂｉｔのフラグとして符号化できる。
【０１６９】
また、特定の基礎ルールまたは複合ルールをひとまとめにしてルールグループを規定し、当該ルールグループに含まれる基礎ルール各々について適用有無を示す情報を符号化するか、または当該ルールグループに含まれる全ての基礎ルールの適用有無を既定の方法で推定するかを示すフラグを符号化してもよい。具体的には、階層Ｌ３においてＴ１６×１６、Ｔ８×８、Ｔ４×４各々の適用有無を示す複合ルールをｅｎａｂｌｅ＿ｔ１６×１６＿Ｌ３、ｅｎａｂｌｅ＿ｔ１６×１６＿Ｌ３、ｅｎａｂｌｅ＿ｔ１６×１６＿Ｌ３とする場合、前記３つの復号ルールをまとめてルールグループｅｎａｂｌｅ＿Ｌ３を作成する。符号化時には、まずｅｎａｂｌｅ＿Ｌ３の適用有無を１ビットで符号化し、ｅｎａｂｌｅ＿Ｌ３を適用する場合には、当該ルールグループに含まれる各複合ルールの適用有無を各々１ビットで符号化する。ｅｎａｂｌｅ＿Ｌ３を適用しない場合には、各複合ルールの適用有無は既定の方法で推定される。
【０１７０】
なお、基礎ルールおよび複合ルールを１個ずつ可変長符号化するのではなく、まとめて符号化してもよい。例えば、全ての基礎ルールを適用しないか、少なくとも１個の基礎ルールを適用するかを示すフラグを符号化して、当該フラグが少なくとも１個の基礎ルールを適用することを示すときに限り、基礎ルール毎に適用するか否かの情報を符号化してもよい。また、前フレームで適用した変換候補リスト導出ルールを引き継ぐか否かのフラグを符号化し、引き継がない場合にのみ変換候補リスト導出ルールを符号化することもできる。
【０１７１】
続いて、動画像符号化装置３０の動作について説明する。
（手順Ｓ２１０）外部から動画像符号化装置３０に入力された入力動画像はフレームを単位として変換候補リスト導出ルール決定部３０１に入力されると共に、拡張ＭＢを単位として予測パラメータ決定部１０２および予測残差生成部１０６に順次入力される。各フレームに対して手順Ｓ２１１〜Ｓ２１２の処理、各拡張ＭＢに対して手順Ｓ２１３〜Ｓ２２１の処理が実行される。
（手順Ｓ２１１）変換候補リスト導出ルール決定部３０１では、入力フレームに基づいて、変換候補リスト導出ルールが生成されて、変換候補導出部３０２および可変長符号化部３０３に出力される。
【０１７２】
（手順Ｓ２１２）可変長符号化部３０３では、入力された変換候補リスト導出ルールに基づいて対応する符号化データが生成されて外部に出力される。
（手順Ｓ２１３）予測パラメータ決定部１０２では、処理対象拡張ＭＢについて、入力された入力動画像に基づいて予測パラメータが決定されて、予測画像生成部１０３、変換候補導出部３０２、および可変長符号化部３０３に出力される。
（手順Ｓ２１４）予測画像生成部１０３では、入力された予測パラメータおよびフレームメモリ１０１に記録されている局所復号画像に基づいて、入力動画像における処理対象拡張ＭＢの領域を近似する予測画像が生成されて予測残差生成部１０６および局所復号画像生成部１１０に出力される。
【０１７３】
（手順Ｓ２１５）予測残差生成部１０６では、入力された入力動画像と予測画像に基づいて、処理対象拡張ＭＢに対応する予測残差が生成されて、周波数変換決定部１１２および変換係数生成部１０７に出力される。
（手順Ｓ２１６）変換候補導出部３０２では、入力された予測パラメータおよび変換候補リスト導出ルールに基づいて、処理対象拡張ＭＢの各パーティションにおける周波数変換に関する制約が導出されて、周波数変換決定部１１２および可変長符号化部３０３に出力される。
【０１７４】
（手順Ｓ２１７）周波数変換決定部１１２では、入力された変換制約と予測残差に基づいて、処理対象拡張ＭＢの各パーティションに適用する周波数変換が決定されて、変換選択フラグとして変換係数生成部１０７および可変長符号化部３０３および予測残差再構築部１０９に出力される。
（手順Ｓ２１８）変換係数生成部１０７では、入力された変換選択フラグにより規定される周波数変換が、入力された予測残差に適用されて、処理対象拡張ＭＢに対応する変換係数が生成されて、可変長符号化部１０８および予測残差再構築部１０９に出力される。
（手順Ｓ２１９）予測残差再構築部１０９では、入力された変換選択フラグにより規定される周波数変換に対応する逆周波数変換が、入力された変換係数に適用されて、処理対象拡張ＭＢに対応する予測残差が再構築されて、局所復号画像生成部１１０に出力される。
【０１７５】
（手順Ｓ２２０）局所復号画像生成部１１０では、入力された予測残差と予測画像に基づいて局所復号画像が生成されてフレームメモリ１０１に出力されて記録される。
（手順Ｓ２２１）可変長符号化部３０３では、入力された変換制約を利用して、入力された変換係数および予測パラメータおよび変換選択フラグが可変長符号化されて、符号化データとして外部に出力される。
上記の手順により、動画像符号化装置３０では、入力された入力動画像を符号化して符号化データを生成し、外部に出力できる。
【０１７６】
＜動画像復号装置４０の構成＞
次に、動画像符号化装置３０で符号化された符号化データを復号して復号動画像を生成する動画像復号装置４０について説明する。
図１６は画像復号装置４０の構成を表すブロック図である。動画像復号装置４０はフレームメモリ１０１、予測画像生成部１０３、予測残差再構築部１０９、局所復号画像生成部１１０、変換候補導出部３０２および可変長符号復号部４０１より構成される。
【０１７７】
可変長符号復号部４０１は、入力される符号化データと変換候補リストに基づいて、予測パラメータ、変換選択フラグ、変換係数、および変換候補リスト導出ルールを復号して出力する。具体的には、まず、変換候補リスト導出ルールを復号して出力する。次に、符号化データから予測パラメータを復号して出力する。次に、変換候補リストを利用して、符号化データから変換選択フラグを復号して出力する。最後に、変換選択フラグを利用して、符号化データから変換係数を復号して出力する。
【０１７８】
＜動画像復号装置４０の動作＞
続いて、動画像復号装置４０の動作について説明する。
（手順Ｓ２３０）外部から動画像復号装置４０に入力された符号化データは、フレームを単位として可変長符号復号部４０１に順次入力されて、各フレームに対応する符号化データに対して、以降のＳ２３１〜Ｓ２３９の処理が順に実行される。
（手順Ｓ２３１）可変長符号復号部４０１では、入力された符号化データから、処理対象フレームに対応する変換候補リスト導出ルールが復号されて、変換候補導出部３０２へ出力される。
【０１７９】
（手順Ｓ２３２）可変長符号復号部４０１では、入力されたフレーム単位の符号化データが拡張ＭＢ単位の符号化データに分割され、各拡張ＭＢに対応する符号化データに対して以降のＳ２３３〜Ｓ２３９の処理が順に実行される。
（手順Ｓ２３３）可変長符号復号部４０１では、処理対象である拡張ＭＢ単位の符号化データから予測パラメータが復号されて、変換候補導出部３０２へ出力される。
（手順Ｓ２３４）変換候補導出部３０２では、入力された変換候補リスト導出ルールおよび予測パラメータに基づいて、処理対象拡張ＭＢの各パーティションにおける変換候補リストが導出されて、可変長符号復号部４０１に出力される。
【０１８０】
（手順Ｓ２３５）可変長符号復号部４０１では、入力された符号化データと変換制約に基づいて、処理対象ＭＢに対応する変換選択フラグが復号されて、予測残差再構築部１０９へ出力される。
（手順Ｓ２３６）可変長符号復号部２０２では、入力された符号化データと（手順Ｓ２３５）で導出した変換選択フラグに基づいて、処理対象拡張ＭＢに対応する変換係数が復号されて、予測残差再構築部１０９へ出力される。
（手順Ｓ２３７）予測画像生成部１０３では、入力された予測パラメータおよびフレームメモリ１０１に記録されている局所復号画像に基づいて、処理対象拡張ＭＢに対応する予測画像が生成されて局所復号画像生成部１１０に出力される。
【０１８１】
（手順Ｓ２３８）予測残差再構築部１０９では、入力された変換選択フラグにより規定される周波数変換に対応する逆周波数変換が、入力された変換係数に適用されて、処理対象拡張ＭＢに対応する予測残差が再構築されて、局所復号画像生成部１１０に出力される。
（手順Ｓ２３９）局所復号画像生成部１１０では、入力された予測残差と予測画像に基づいて局所復号画像が生成されてフレームメモリ１０１に出力されて記録されるとともに、処理対象ブロックに対応する復号動画像上の領域として外部に出力される。
【０１８２】
以上説明したように、動画像復号装置４０によれば、動画像符号化装置１１で生成された符号化データから復号動画像を生成することができる。
【０１８３】
また、上述した実施形態における動画像符号化装置および動画像復号装置の一部、または全部を典型的には集積回路であるＬＳＩ（Large Scale Integration）として実施してもよい。動画像符号化装置及び動画像復号装置の各機能ブロックは個別にチップ化してもよいし、一部、または全部を集積してチップ化してもよい。また、集積回路化の手法はＬＳＩに限らず専用回路、または汎用プロセッサで実現しても良い。また、半導体技術の進歩によりＬＳＩに代替する集積回路化の技術が出現した場合、当該技術による集積回路を用いることも可能である。
【符号の説明】
【０１８４】
１０…動画像符号化装置、１１…動画像符号化装置、２０…動画像復号装置、２１…動画像復号装置、３０…動画像符号化装置、４０…動画像復号装置、１０１…フレームメモリ、１０２…予測パラメータ決定部、１０３…予測画像生成部、１０４…変換制約導出部、１０５…周波数変換決定部、１０６…予測残差生成部、１０７…変換係数生成部、１０８…可変長符号化部、１０９…予測残差再構築部、１１０…局所復号画像生成部、１１１…変換候補導出部、１１２…周波数変換決定部、１１３…可変長符号化部、２０１…可変長符号復号部、２０２…可変長符号復号部、３０１…候補リスト導出ルール決定部、３０２…変換候補導出部、３０２…可変長符号化部、４０１…可変長符号復号部。
【図１】
2010116869.tif 000003
【図２】
2010116869.tif 000004
【図３】
2010116869.tif 000005
【図４】
2010116869.tif 000006
【図５】
2010116869.tif 000007
【図６】
2010116869.tif 000008
【図７】
2010116869.tif 000009
【図８】
2010116869.tif 000010
【図９】
2010116869.tif 000011
【図１０】
2010116869.tif 000012
【図１１】
2010116869.tif 000013
【図１２】
2010116869.tif 000014
【図１３】
2010116869.tif 000015
【図１４】
2010116869.tif 000016
【図１５】
2010116869.tif 000017
【図１６】
2010116869.tif 000018
【国際調査報告】
2010116869.tif 000019
2010116869.tif 000020
2010116869.tif 000021
2010116869.tif 000022