(57)【要約】【課題】複数の階層で規定されたブロックサイズを用いる動画像符号化において、イントラ予測モードにおけるブロック分割を決定するための演算量を削減する。【解決手段】選択部４１１は、動画像の画像内の符号化対象領域を複数の階層それぞれにおいて再帰的に分割して得られる、異なるブロックサイズの複数のブロックそれぞれについて、ブロックの原画像と所定の予測画像との差分に基づく符号化コストを再帰的に計算する。そして、選択部４１１は、それぞれのブロックの符号化コストを比較して、複数の階層のうち１つの階層のブロックサイズを選択する。決定部４１２は、選択されたブロックサイズを有する符号化対象ブロックに対するイントラ予測モードを決定する。イントラ予測部４１３は、決定されたイントラ予測モードに基づいて、符号化対象ブロックに対する予測画像を生成する。符号化部４１４は、生成された予測画像を用いて、符号化対象ブロックを符号化する。【選択図】図４
2019062339.tif 000002
【特許請求の範囲】
【請求項１】
動画像に含まれる符号化対象画像内の符号化対象領域を複数の階層それぞれにおいて再帰的に分割して得られる、異なるブロックサイズの複数のブロックそれぞれについて、ブロックの原画像と所定の予測画像との差分に基づく符号化コストを再帰的に計算し、前記複数のブロックそれぞれの符号化コストを比較して、前記複数の階層のうち１つの階層のブロックサイズを選択する選択部と、
前記選択部が選択したブロックサイズを有する符号化対象ブロックに対するイントラ予測モードを決定する決定部と、
前記決定部が決定したイントラ予測モードに基づいて、前記符号化対象ブロックに対する予測画像を生成するイントラ予測部と、
前記イントラ予測部が生成した予測画像を用いて、前記符号化対象ブロックを符号化する符号化部と、
を備えることを特徴とする動画像符号化装置。
【請求項２】
前記所定の予測画像の画素値は、前記複数のブロックのうち処理対象ブロックに隣接する複数の画素の画素値の平均値であり、前記処理対象ブロックの符号化コストは、前記処理対象ブロックの原画像と前記所定の予測画像との差分をアダマール変換によって変換した変換結果の絶対値和を含むことを特徴とする請求項１記載の動画像符号化装置。
【請求項３】
前記選択部は、前記処理対象ブロック内の前記処理対象ブロックよりも小さなブロックサイズを有するブロックの原画像をアダマール変換によって変換した変換結果を用いて、前記処理対象ブロックの原画像をアダマール変換によって変換した変換結果を計算し、前記処理対象ブロックよりも小さなブロックサイズを有するブロックに隣接する複数の画素の画素値を用いて、前記処理対象ブロックに隣接する複数の画素の画素値の平均値を計算し、前記処理対象ブロックの原画像をアダマール変換によって変換した変換結果と、前記処理対象ブロックに隣接する複数の画素の画素値の平均値とを用いて、前記処理対象ブロックの符号化コストを計算し、前記処理対象ブロックの符号化コストが前記処理対象ブロックよりも小さなブロックサイズを有するブロックの符号化コストよりも小さい場合、前記処理対象ブロックのブロックサイズを選択することを特徴とする請求項２記載の動画像符号化装置。
【請求項４】
動画像符号化装置によって実行される動画像符号化方法であって、
前記動画像符号化装置が、
動画像に含まれる符号化対象画像内の符号化対象領域を複数の階層それぞれにおいて再帰的に分割して得られる、異なるブロックサイズの複数のブロックそれぞれについて、ブロックの原画像と所定の予測画像との差分に基づく符号化コストを再帰的に計算し、
前記複数のブロックそれぞれの符号化コストを比較して、前記複数の階層のうち１つの階層のブロックサイズを選択し、
選択したブロックサイズを有する符号化対象ブロックに対するイントラ予測モードを決定し、
決定したイントラ予測モードに基づいて、前記符号化対象ブロックに対する予測画像を生成し、
生成した予測画像を用いて、前記符号化対象ブロックを符号化する、
ことを特徴とする動画像符号化方法。
【請求項５】
動画像に含まれる符号化対象画像内の符号化対象領域を複数の階層それぞれにおいて再帰的に分割して得られる、異なるブロックサイズの複数のブロックそれぞれについて、ブロックの原画像と所定の予測画像との差分に基づく符号化コストを再帰的に計算し、
前記複数のブロックそれぞれの符号化コストを比較して、前記複数の階層のうち１つの階層のブロックサイズを選択し、
選択したブロックサイズを有する符号化対象ブロックに対するイントラ予測モードを決定し、
決定したイントラ予測モードに基づいて、前記符号化対象ブロックに対する予測画像を生成し、
生成した予測画像を用いて、前記符号化対象ブロックを符号化する、
処理をコンピュータに実行させるための動画像符号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動画像符号化装置、動画像符号化方法、及び動画像符号化プログラムに関する。
【背景技術】
【０００２】
動画像符号化の１つの標準であるHigh Efficiency Video Coding（ＨＥＶＣ）では、Prediction Unit（ＰＵ）と呼ばれるブロック毎に予測方法が決定される。ＰＵのブロックサイズは、四分木分割の木構造における複数の階層によって規定されている。動画像符号化装置は、四分木分割の各階層で最適なイントラ予測モードを決定し、それぞれの階層における最適なイントラ予測モードを階層間で比較することで、最適なＰＵ分割を決定する。
【０００３】
サブブロックの差分絶対値和に基づく第１の評価値と、原画像を直交変換した後のサブブロックの直交変換係数の絶対値和に基づく第２の評価値とに基づいて、ブロックサイズを選択する動画像符号化装置も知られている（例えば、特許文献１を参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１０−２８３４９５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ＨＥＶＣにおける四分木分割の複数の階層それぞれについて、３５種類のイントラ予測モードそれぞれの符号化コストを計算し、計算した符号化コストを比較して最適な階層を決定する場合、符号化コストの計算回数が増加する。演算量が多い符号化コストの計算回数が増加すると、最適な階層を決定するための処理時間が長くなる。
【０００６】
なお、かかる問題は、ＨＥＶＣにおける四分木分割を採用した動画像符号化に限らず、複数の階層で規定されたブロックサイズに基づくブロック分割を採用した他の動画像符号化においても生ずるものである。
【０００７】
１つの側面において、本発明は、複数の階層で規定されたブロックサイズを用いる動画像符号化において、イントラ予測モードにおけるブロック分割を決定するための演算量を削減することを目的とする。
【課題を解決するための手段】
【０００８】
１つの案では、動画像符号化装置は、選択部、決定部、イントラ予測部、及び符号化部を含む。
【０００９】
選択部は、動画像に含まれる符号化対象画像内の符号化対象領域を複数の階層それぞれにおいて再帰的に分割して得られる、異なるブロックサイズの複数のブロックそれぞれについて、符号化コストを再帰的に計算する。計算される符号化コストは、ブロックの原画像と所定の予測画像との差分に基づく符号化コストである。そして、選択部は、複数のブロックそれぞれの符号化コストを比較して、複数の階層のうち１つの階層のブロックサイズを選択する。
【００１０】
決定部は、選択部が選択したブロックサイズを有する符号化対象ブロックに対するイントラ予測モードを決定する。イントラ予測部は、決定部が決定したイントラ予測モードに基づいて、符号化対象ブロックに対する予測画像を生成する。符号化部は、イントラ予測部が生成した予測画像を用いて、符号化対象ブロックを符号化する。
【発明の効果】
【００１１】
実施形態によれば、複数の階層で規定されたブロックサイズを用いる動画像符号化において、イントラ予測モードにおけるブロック分割を決定するための演算量を削減することができる。
【図面の簡単な説明】
【００１２】
【図１】四分木分割を示す図である。
【図２】イントラ予測符号化におけるＰＵを示す図である。
【図３】ＲＤコストの評価方法を示す図である。
【図４】動画像符号化装置の機能的構成図である。
【図５】動画像符号化処理のフローチャートである。
【図６】動画像符号化装置の具体例を示す機能的構成図である。
【図７】動画像符号化処理の具体例を示すフローチャートである。
【図８】判定部の機能的構成図である。
【図９】イントラ予測モード判定処理のフローチャートである。
【図１０】選択部の機能的構成図である。
【図１１】４×４のブロックを示す図である。
【図１２】上周辺領域及び左周辺領域を示す図である。
【図１３】処理対象ブロックを示す図である。
【図１４】加算値の個数を示す図である。
【図１５】上加算値を示す図である。
【図１６】左加算値を示す図である。
【図１７】データにアクセスする順序を示す図である。
【図１８】ブロックサイズ決定処理のフローチャートである。
【図１９】積み上げ処理のフローチャートである。
【図２０】比較処理のフローチャートである。
【図２１】第１のシミュレーション結果を示す図である。
【図２２】第２のシミュレーション結果を示す図である。
【図２３】第３のシミュレーション結果を示す図である。
【図２４】第４のシミュレーション結果を示す図である。
【図２５】再構成画像を利用する動画像符号化装置の具体例を示す機能的構成図である。
【図２６】情報処理装置の構成図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照しながら、実施形態を詳細に説明する。
図１は、ＨＥＶＣにおける四分木分割の例を示している。ＨＥＶＣでは、動画像に含まれる符号化対象画像が、Coding Tree Unit（ＣＴＵ）と呼ばれるブロックに分割され、各ＣＴＵが、再帰的な四分木分割によって、Coding Unit（ＣＵ）と呼ばれるブロックに分割される。インター予測、イントラ予測、直交変換、量子化、エントロピー符号化等の一連の符号化処理は、ＣＵ単位で行われる。以下では、ｎ画素×ｎ画素（ｎは１以上の整数）のブロックサイズを、単にｎ×ｎと記すことがある。
【００１４】
例えば、６４×６４のＣＴＵは、四分木分割によって、４個の３２×３２のＣＵに分割され、３２×３２のＣＵは、４個の１６×１６のＣＵにさらに分割される。３２×３２のＣＵは、４個の１６×１６のＣＵにさらに分割され、１６×１６のＣＵは、４個の８×８のＣＵにさらに分割される。ＣＵのブロックサイズの最小値は、８×８〜ＣＴＵのブロックサイズの範囲で指定することが可能である。
【００１５】
各ＣＵは、インター予測符号化又はイントラ予測符号化のいずれかの符号化方式によって符号化される。インター予測符号化は、符号化対象画像を符号化済み画像の情報を用いて符号化する符号化方式であり、イントラ予測符号化は、符号化対象画像が持つ情報のみを用いて符号化対象画像を符号化する符号化方式である。
【００１６】
各ＣＵは、ＰＵと呼ばれるブロックに分割されるとともに、再帰的な四分木分割によって、Transform Unit（ＴＵ）と呼ばれるブロックにも分割される。インター予測及びイントラ予測はＰＵ単位で行われ、直交変換及び量子化はＴＵ単位で行われる。
【００１７】
図２は、イントラ予測符号化におけるＰＵの例を示している。イントラ予測符号化の場合、２Ｎ×２Ｎ（Ｎ＝３２，１６，８，４）のＣＵに対して、ＣＵと同じ２Ｎ×２ＮのＰＵ、又はＣＵよりも小さなＮ×ＮのＰＵを選択することが可能である。ただし、Ｎ×ＮのＰＵは、最小のＣＵに対してのみ選択することができる。したがって、イントラ予測符号化におけるＰＵのブロックサイズは、６４×６４、３２×３２、１６×１６、８×８、又は４×４のいずれかである。
【００１８】
一方、ＴＵのブロックサイズは、３２×３２、１６×１６、８×８、又は４×４のいずれかである。
【００１９】
動画像符号化では、符号化処理によって発生する符号量（ビット量）を最小化するために、原画像と予測画像との差分（符号化歪み）によって発生するビット量の多さを示すRate-Distortion（ＲＤ）コストと呼ばれる符号化コストが用いられることがある。この場合、ＰＵ毎に複数の予測方法に対するＲＤコストが計算され、ＲＤコストが最小となる予測方法が選択される。ＲＤコストＣは、例えば、次式によって計算される。
【００２０】
Ｃ＝Ｄ＋λ×Ｒ      （１）
【００２１】
式（１）のＤは、原画像と予測画像との差分を表し、Ｒは、シンタックスを符号化する際に発生するビット量を表す。λは、量子化パラメータ（Quantization Parameter，ＱＰ）に基づいて決定される変換係数である。Ｄとしては、例えば、差分絶対値和（Sum of Absolute Differences，ＳＡＤ）、Sum of Absolute Transformed Differences（ＳＡＴＤ）等が用いられる。
【００２２】
図３は、イントラ予測符号化におけるＲＤコストの評価方法の例を示している。この例では、ＣＴＵのブロックサイズは６４×６４であり、動画像符号化装置は、四分木分割の階層０〜階層４それぞれにおいて、ＰＵ及びＴＵのブロックサイズの組み合わせ毎にＲＤコストを計算する。そして、動画像符号化装置は、それぞれの階層における最小のＲＤコストを比較することで、四分木分割の最適な階層を決定する。
【００２３】
階層０〜階層３それぞれにおけるＣＵのブロックサイズは、以下の通りである。
階層０  ６４×６４
階層１  ３２×３２
階層２  １６×１６
階層３  ８×８
【００２４】
この場合、階層０におけるＰＵのブロックサイズは６４×６４であり、ＴＵのブロックサイズは３２×３２、１６×１６、８×８、又は４×４である。階層１におけるＰＵのブロックサイズは３２×３２であり、ＴＵのブロックサイズは３２×３２、１６×１６、８×８、又は４×４である。階層２におけるＰＵのブロックサイズは１６×１６であり、ＴＵのブロックサイズは１６×１６、８×８、又は４×４である。階層３におけるＰＵのブロックサイズは８×８であり、ＴＵのブロックサイズは８×８又は４×４である。
【００２５】
階層４は、階層３におけるＣＵに対して４×４のＰＵが選択された場合を示している。この場合、ＴＵのブロックサイズとして４×４が選択される。
【００２６】
まず、動画像符号化装置は、階層４における４×４のＰＵと４×４のＴＵの組み合わせに対して、３５種類のイントラ予測モードそれぞれのＲＤコストを計算し、その組み合わせに対する最小のＲＤコストを求める。そして、動画像符号化装置は、４×４のＰＵと４×４のＴＵの組み合わせを、最適な組み合わせ３０１として採用する。
【００２７】
次に、動画像符号化装置は、階層３におけるＰＵとＴＵの各組み合わせに対して、３５種類のイントラ予測モードそれぞれのＲＤコストを計算し、その組み合わせに対する最小のＲＤコストを求める。そして、動画像符号化装置は、最適な組み合わせ３０１と、階層３における最小のＲＤコストが得られた組み合わせのうち、ＲＤコストが小さい方の組み合わせを、最適な組み合わせ３０２として用いる。
【００２８】
このような評価を階層４から階層０まで順番に繰り返すことで、最適な組み合わせ３０１〜最適な組み合わせ３０４に基づいて、最適な階層、ＰＵとＴＵの最適な組み合わせ、及び最適なイントラ予測モードが決定される。この場合、各階層におけるＰＵとＴＵの各組み合わせに対して、イントラ予測モードの個数（３５個）と同じ回数だけＲＤコストの計算が繰り返される。このように、演算量が多いＲＤコストの計算回数が増加すると、最適な階層を決定するための処理時間が長くなる。
【００２９】
図４は、実施形態の動画像符号化装置の機能的構成例を示している。図４の動画像符号化装置４０１は、選択部４１１、決定部４１２、イントラ予測部４１３、及び符号化部４１４を含む。
【００３０】
図５は、図４の動画像符号化装置４０１が行う動画像符号化処理の例を示すフローチャートである。まず、選択部４１１は、動画像に含まれる符号化対象画像内の符号化対象領域を複数の階層それぞれにおいて再帰的に分割して得られる、異なるブロックサイズの複数のブロックそれぞれについて、符号化コストを再帰的に計算する（ステップ５０１）。計算される符号化コストは、ブロックの原画像と所定の予測画像との差分に基づく符号化コストである。そして、選択部４１１は、複数のブロックそれぞれの符号化コストを比較して、複数の階層のうち１つの階層のブロックサイズを選択する（ステップ５０２）。
【００３１】
次に、決定部４１２は、選択部４１１が選択したブロックサイズを有する符号化対象ブロックに対するイントラ予測モードを決定する（ステップ５０３）。次に、イントラ予測部４１３は、決定部４１２が決定したイントラ予測モードに基づいて、符号化対象ブロックに対する予測画像を生成する（ステップ５０４）。そして、符号化部４１４は、イントラ予測部４１３が生成した予測画像を用いて、符号化対象ブロックを符号化する（ステップ５０５）。
【００３２】
図４の動画像符号化装置４０１によれば、複数の階層で規定されたブロックサイズを用いる動画像符号化において、イントラ予測モードにおけるブロック分割を決定するための演算量を削減することができる。
【００３３】
図６は、図４の動画像符号化装置４０１の具体例を示している。図６の動画像符号化装置６０１は、分割部６１１、レート制御部６１２、差分生成部６１３、変換部６１４、エントロピー符号化部６１５、判定部６１６、判定部６１７、スイッチ６１８、動き補償部６１９、動き予測部６２０、及びイントラ予測部６２１を含む。さらに、動画像符号化装置６０１は、逆変換部６２２、再構成部６２３、ループ内フィルタ６２４、及びフレームメモリ６２５を含む。
【００３４】
判定部６１６は、図４の選択部４１１及び決定部４１２に対応し、イントラ予測部６２１は、イントラ予測部４１３に対応し、差分生成部６１３、変換部６１４、エントロピー符号化部６１５、及びスイッチ６１８は、符号化部４１４に対応する。
【００３５】
動画像符号化装置６０１は、例えば、ハードウェア回路として実装することができる。この場合、動画像符号化装置６０１の各構成要素を個別の回路として実装してもよく、１つの集積回路として実装してもよい。
【００３６】
動画像符号化装置６０１は、入力される符号化対象動画像を符号化し、符号化動画像をビットストリームとして出力する。符号化対象動画像は、時系列の複数のピクチャを含む。各ピクチャは、符号化対象画像に対応し、フレームと呼ばれることもある。各ピクチャは、カラー画像であってもよく、モノクロ画像であってもよい。ピクチャがカラー画像の場合、画素値はＲＧＢ形式であってもよく、ＹＵＶ形式であってもよい。
【００３７】
分割部６１１は、各ピクチャ内における符号化対象領域である符号化対象ＣＴＵの位置を決定し、ＣＴＵのブロックサイズ（ＣＴＵサイズ）に従ってピクチャを分割することで、符号化対象ＣＴＵの原画像（ＣＴＵ原画像）を抽出する。そして、分割部６１１は、抽出したＣＴＵ原画像とＣＴＵサイズとを、差分生成部６１３、判定部６１６、及び動き予測部６２０へ出力する。
【００３８】
判定部６１６は、分割部６１１が出力するＣＴＵ原画像及びＣＴＵサイズと、レート制御部６１２が出力する量子化パラメータＱＰとを用いて、ＣＴＵ内の各ＰＵのブロックサイズを決定する。そして、判定部６１６は、各ＰＵに対する最適なイントラ予測モードとＴＵのブロックサイズとを決定し、決定したイントラ予測モードをイントラ予測部６２１へ出力し、そのイントラ予測モードに対応する符号化コストを判定部６１７へ出力する。
【００３９】
イントラ予測部６２１は、再構成部６２３が出力する再構成画像をＰＵの周辺画素として用い、判定部６１６が出力するイントラ予測モードに従って、イントラ予測画像を生成する。そして、イントラ予測部６２１は、生成したイントラ予測画像をスイッチ６１８へ出力する。
【００４０】
動き予測部６２０は、フレームメモリ６２５が記憶する復号画像と、分割部６１１が出力するＣＴＵ原画像と、レート制御部６１２が出力する量子化パラメータＱＰとを用いて、ＣＴＵ内の各ＰＵのブロックサイズを決定する。次に、動き予測部６２０は、各ＰＵに対する最適な動きベクトルと、最適な復号画像の参照インデックスと、ＴＵのブロックサイズとを決定する。そして、動き予測部６２０は、決定した動きベクトル及び参照インデックスを動き補償部６１９へ出力し、その動きベクトル及び参照インデックスに対応する符号化コストを判定部６１７へ出力する。
【００４１】
動き補償部６１９は、動き予測部６２０が出力する参照インデックスが示す復号画像をフレームメモリ６２５から取得し、取得した復号画像と動き予測部６２０が出力する動きベクトルとを用いて、インター予測画像を生成する。そして、動き補償部６１９は、生成したインター予測画像をスイッチ６１８へ出力する。
【００４２】
判定部６１７は、判定部６１６が出力するイントラ予測モードの各ＰＵの符号化コストと、動き予測部６２０が出力するインター予測モードの各ＰＵの符号化コストとを比較する。そして、判定部６１７は、各ＰＵに対してイントラ予測モード又はインター予測モードのいずれを適用するかを決定し、決定した予測モードを示す制御信号をスイッチ６１８へ出力する。
【００４３】
イントラ予測モードのＰＵとインター予測モードのＰＵのブロックサイズが異なる場合、判定部６１７は、大きい方のＰＵのブロックサイズに合わせて、小さい方のＰＵの符号化コストを合算する。そして、判定部６１７は、合算した符号化コストと、大きい方のＰＵの符号化コストとを比較する。
【００４４】
エントロピー符号化部６１５は、変換部６１４が出力する変換係数と符号化処理の各シンタックスとをエントロピー符号化によって符号化し、符号化動画像のビットストリームを出力する。そして、エントロピー符号化部６１５は、エントロピー符号化によって発生するビット量（発生情報量）をレート制御部６１２へ出力する。
【００４５】
レート制御部６１２は、エントロピー符号化部６１５が出力する発生情報量が目標情報量になるように、量子化パラメータＱＰを指定し、指定した量子化パラメータＱＰを、変換部６１４、判定部６１６、及び動き予測部６２０へ出力する。レート制御部６１２は、量子化パラメータＱＰをＣＵ単位で指定することができる。
【００４６】
スイッチ６１８は、判定部６１７が出力する制御信号に従って、イントラ予測部６２１が出力するイントラ予測画像、又は動き予測部６２０が出力するインター予測画像のいずれかを選択し、選択した予測画像を差分生成部６１３へ出力する。
【００４７】
差分生成部６１３は、スイッチ６１８が出力する予測画像と、分割部６１１が出力するＣＴＵ原画像に含まれる部分画像との差分を、予測誤差として変換部６１４へ出力する。変換部６１４は、差分生成部６１３が出力する差分に対して直交変換及び量子化を行い、量子化係数をエントロピー符号化部６１５及び逆変換部６２２へ出力する。
【００４８】
逆変換部６２２は、変換部６１４が出力する量子化係数に対して逆量子化及び逆直交変換及を行って、逆変換差分を生成し、生成した逆変換差分を再構成部６２３へ出力する。再構成部６２３は、スイッチ６１８が出力する予測画像と、逆変換部６２２が出力する逆変換差分とを加算して、再構成画像を生成し、生成した再構成画像をループ内フィルタ６２４へ出力する。
【００４９】
ループ内フィルタ６２４は、再構成部６２３が出力する再構成画像にフィルタを適用して復号画像を生成し、生成した復号画像をフレームメモリ６２５へ出力する。フレームメモリ６２５は、ループ内フィルタ６２４が出力する復号画像を記憶する。
【００５０】
動画像符号化装置６０１は、通信ネットワークを介して、ビットストリームを不図示の動画像復号装置へ送信することができる。この場合、動画像復号装置は、ビットストリームを復号して符号化対象動画像を復元する。
【００５１】
動画像符号化装置６０１は、様々な用途に利用される。例えば、動画像符号化装置６０１を、ビデオカメラ、映像送信装置、映像受信装置、テレビ電話システム、コンピュータ、又は携帯電話機に組み込むことも可能である。
【００５２】
図７は、図６の動画像符号化装置６０１が行う動画像符号化処理の具体例を示すフローチャートである。図７の動画像符号化処理は、符号化対象動画像に含まれる各ピクチャに対して適用される。
【００５３】
まず、分割部６１１は、ピクチャから１つのＣＴＵ原画像を抽出し（ステップ７０１）、判定部６１６は、イントラ予測モード判定を行って、ＣＴＵ内の各ＰＵのブロックサイズを決定し、各ＰＵに対するイントラ予測モードを決定する（ステップ７０２）。
【００５４】
次に、イントラ予測部６２１は、イントラ予測を行ってイントラ予測画像を生成する（ステップ７０３）。また、動き予測部６２０は、動き予測を行って、各ＰＵに対する動きベクトル及び復号画像の参照インデックスを決定し（ステップ７０４）、動き補償部６１９は、動き補償を行ってインター予測画像を生成する（ステップ７０５）。
【００５５】
次に、判定部６１７は、各ＰＵに対してイントラ予測モード又はインター予測モードのいずれを適用するかを決定し（ステップ７０６）、差分生成部６１３は、予測画像と原画像との差分を生成する（ステップ７０７）。そして、変換部６１４は、差分に対して直交変換及び量子化を行い（ステップ７０８）、エントロピー符号化部６１５は、量子化係数に対してエントロピー符号化を行う（ステップ７０９）。
【００５６】
次に、逆変換部６２２は、量子化係数に対して逆量子化及び逆直交変換及を行い（ステップ７１０）、再構成部６２３は、予測画像及び逆変換差分から再構成画像を生成する（ステップ７１１）。そして、ループ内フィルタ６２４は、再構成画像にフィルタを適用して復号画像を生成し（ステップ７１２）、生成した復号画像をフレームメモリ６２５に格納する（ステップ７１３）。
【００５７】
次に、分割部６１１は、ピクチャ内のすべてのＣＴＵを処理したか否かをチェックする（ステップ７１４）。未処理のＣＴＵが残っている場合（ステップ７１４，ＮＯ）、分割部６１１は、次のＣＴＵを選択して（ステップ７１５）、ステップ７０１以降の処理を繰り返す。そして、すべてのＣＴＵを処理した場合（ステップ７１４，ＹＥＳ）、動画像符号化装置６０１は、処理を終了する。
【００５８】
図８は、図６の判定部６１６の機能的構成例を示している。図８の判定部６１６は、選択部８０１、輝度モード決定部８０２、色差モード決定部８０３、輝度サイズ決定部８０４、及び色差サイズ決定部８０５を含む。選択部８０１は、図４の選択部４１１に対応し、輝度モード決定部８０２及び色差モード決定部８０３は、決定部４１２に対応する。
【００５９】
選択部８０１は、ＣＴＵ原画像、ＣＴＵサイズ、及び量子化パラメータＱＰを用いて、四分木分割の複数の階層それぞれにおいて再帰的に分割して得られる、異なるブロックサイズの複数のＰＵそれぞれについて、符号化コストを再帰的に計算する。
【００６０】
この場合、各階層におけるＰＵが処理対象ブロックとなり、選択部８０１は、各ＰＵの原画像とDirect Current（ＤＣ）予測モードのイントラ予測画像との差分に基づく符号化コストを計算する。ＤＣ予測モードのイントラ予測画像の画素値は、ＰＵの上及び左に隣接する所定領域に含まれる複数の画素の画素値の平均値である。例えば、符号化コストとしては、式（１）のＲＤコストＣが用いられ、式（１）の差分Ｄとしては、ＳＡＴＤが用いられる。
【００６１】
次に、選択部８０１は、複数のＰＵそれぞれの符号化コストを比較して、最適なＰＵのブロックサイズを決定し、決定したブロックサイズを輝度モード決定部８０２及び色差モード決定部８０３へ出力する。この場合、最小の符号化コストを有するＰＵが、最適なＰＵに決定される。
【００６２】
輝度モード決定部８０２は、ＣＴＵ原画像、ＣＴＵサイズ、量子化パラメータＱＰ、及び決定されたＰＵのブロックサイズを用いて、３５種類のイントラ予測モードそれぞれについて、符号化コストを計算する。３５種類のイントラ予測モードには、ＤＣ予測モード、Planar予測モード、及び３３方向のAngular予測モードが含まれる。
【００６３】
次に、輝度モード決定部８０２は、３５種類のイントラ予測モードそれぞれの符号化コストを比較して、ＰＵに対する最適なイントラ予測モードを決定し、決定したイントラ予測モードを輝度サイズ決定部８０４へ出力する。この場合、最小の符号化コストを有するイントラ予測モードが、最適なイントラ予測モードに決定される。
【００６４】
輝度サイズ決定部８０４は、ＣＴＵ原画像、ＣＴＵサイズ、及び決定されたイントラ予測モードを用いて、ＰＵに対するＴＵのブロックサイズを決定し、ＴＵのブロックサイズと、決定されたイントラ予測モードの符号化コストとを出力する。
【００６５】
色差モード決定部８０３は、ＣＴＵ原画像、ＣＴＵサイズ、量子化パラメータＱＰ、及び決定されたＰＵのブロックサイズを用いて、色差ＰＵに対する５種類の色差イントラ予測モードそれぞれについて、符号化コストを計算する。５種類の色差イントラ予測モードには、ＤＣ予測モード、Planar予測モード、垂直予測モード、水平予測モード、及び斜め予測モードが含まれる。
【００６６】
次に、色差モード決定部８０３は、５種類の色差イントラ予測モードそれぞれの符号化コストを比較して、最適な色差イントラ予測モードを決定し、決定した色差イントラ予測モードを色差サイズ決定部８０５へ出力する。この場合、最小の符号化コストを有する色差イントラ予測モードが、最適な色差イントラ予測モードに決定される。
【００６７】
色差サイズ決定部８０５は、ＣＴＵ原画像、ＣＴＵサイズ、及び決定された色差イントラ予測モードを用いて、色差ＰＵに対する色差ＴＵのブロックサイズを決定し、色差ＴＵのブロックサイズと、決定された色差イントラ予測モードの符号化コストとを出力する。
【００６８】
図９は、図８の判定部６１６が行うイントラ予測モード判定処理の例を示すフローチャートである。まず、選択部８０１は、四分木分割の複数の階層それぞれにおけるＰＵのブロックサイズの中から、最適なＰＵのブロックサイズを決定する（ステップ９０１）。
【００６９】
次に、輝度モード決定部８０２は、ＰＵに対する最適なイントラ予測モードを決定し（ステップ９０２）、輝度サイズ決定部８０４は、ＰＵに対するＴＵのブロックサイズを決定する（ステップ９０３）。
【００７０】
次に、色差モード決定部８０３は、色差ＰＵに対する最適な色差イントラ予測モードを決定し（ステップ９０４）、色差サイズ決定部８０５は、色差ＰＵに対する色差ＴＵのブロックサイズを決定する（ステップ９０５）。
【００７１】
図８の判定部６１６によれば、選択部８０１は、複数の階層それぞれにおいて、３５種類のイントラ予測モードの符号化コストを計算するのではなく、ＤＣ予測モードの符号化コストのみを計算する。また、輝度モード決定部８０２は、複数の階層それぞれにおいて３５種類のイントラ予測モードの符号化コストを計算するのではなく、選択部８０１が決定した単一の階層のみにおいて３５種類のイントラ予測モードの符号化コストを計算する。
【００７２】
したがって、複数の階層それぞれにおいて３５種類のイントラ予測モードの符号化コストを計算する場合と比較して、演算量が多い符号化コストの計算回数が削減され、最適な階層及びイントラ予測モードを決定するための処理時間が短くなる。
【００７３】
選択部８０１は、複数の階層それぞれにおいてＤＣ予測モードの符号化コストを計算する際、処理を簡略化するために、ＤＣ予測画像に近似する疑似ＤＣ予測画像を用いることができる。この場合、選択部８０１は、ＤＣ予測モードにおける処理対象ブロックに隣接する周辺領域の画素値として、再構成画像の代わりに符号化前の原画像の画素値を用いることで、疑似ＤＣ予測画像を生成する。これにより、周辺ブロックの再構成画像が確定する前に予測画像を生成することが可能になり、処理が簡略化される。
【００７４】
また、選択部８０１は、ＳＡＴＤを含む符号化コストを用いることで、アダマール変換の積み上げを利用して、複数の階層それぞれにおけるＰＵに対する符号化コストを再帰的に計算することができる。アダマール変換の変換行列Ｈｍ（ｍは１以上の整数）は、２ｍ×２ｍの行列であり、次式によって再帰的に定義される。
【００７５】
【数１】
2019062339.tif 000003
【００７６】
ただし、１×１の変換行列Ｈ０は、Ｈ０＝１によって定義される。また、式（１１）のＨｍに含まれる正規化係数を省略すると、アダマール変換は、次式の変換行列Ｔｍによって記述することができる。
【００７７】
【数２】
2019062339.tif 000004
【００７８】
ただし、Ｔ０＝Ｈ０＝１である。例えば、ｍ＝２の場合、式（１２）より、４×４の変換行列Ｔ２は、次式のようになる。
【００７９】
【数３】
2019062339.tif 000005
【００８０】
２ｍ×２ｍの行列Ｍを変換行列Ｔ＝Ｔｍによって変換した変換結果Ｔ（Ｍ）は、次式により記述される。
【００８１】
Ｔ（Ｍ）＝ＴＭＴＴ      （１４）
【００８２】
式（１４）のＴＴは、変換行列Ｔを転置して得られる転置行列を表す。２ｍ×２ｍのブロックの水平方向の座標をｘ座標とし、垂直方向の座標をｙ座標とすると、座標（ｘ，ｙ）に対応する画素の画素値を行列Ｍの要素Ｍ［ｘ］［ｙ］として用いることで、そのブロックの画像を表す行列Ｍが生成される。この場合、ｘ座標は行列Ｍの列を表し、ｙ座標は行列Ｍの行を表す。
【００８３】
例えば、ｍ＝２の場合、式（１３）及び式（１４）より、４×４の行列Ｍの変換結果Ｔ（Ｍ）は、次式のようになる。
【００８４】
【数４】
2019062339.tif 000006
【００８５】
【数５】
2019062339.tif 000007
【００８６】
ＤＣ予測モードにおけるＳＡＴＤは、処理対象ブロックの原画像とＤＣ予測画像との差分をアダマール変換によって変換した変換結果の絶対値和である。ｎ×ｎ（ｎ＝２ｍ）のブロックのＤＣ予測モードにおけるＳＡＴＤは、原画像の画素値を要素とするｎ×ｎの行列Ｍと、ＤＣ予測画像の画素値を要素とするｎ×ｎの行列Ｐとを用いて、次式により記述される。
【００８７】
Ｓ＝Σ（ｘ＝０〜ｎ−１，ｙ＝０〜ｎ−１）｜Ｔ（Ｍ−Ｐ）ＴＴ［ｘ］［ｙ］｜
＝Σ（ｘ＝０〜ｎ−１，ｙ＝０〜ｎ−１）｜Ｑ［ｘ］［ｙ］｜            （１７）
Ｑ［ｘ］［ｙ］＝ＴＭＴＴ［ｘ］［ｙ］−ＴＰＴＴ［ｘ］［ｙ］      （１８）
【００８８】
式（１７）において、ＳはＤＣ予測モードにおけるＳＡＴＤを表す。Σ（ｘ＝０〜ｎ−１，ｙ＝０〜ｎ−１）は、ｘ＝０〜ｎ−１及びｙ＝０〜ｎ−１の範囲のすべての要素の総和を表す。
【００８９】
行列Ｐの要素Ｐ［ｘ］［ｙ］は、行列Ｐに対応するブロックの上及び左に隣接する所定領域に含まれる複数の画素の画素値の平均値である。Ｐ［ｘ］［ｙ］はすべて同じ値であるため、ＴＭＴＴ［０］［０］≧（ｎ×ｎ）Ｐ［０］［０］である場合、式（１７）を次式のように変形することができる。
【００９０】
Ｓ＝Σ（ｘ＝０〜ｎ−１，ｙ＝０〜ｎ−１）｜ＴＭＴＴ［ｘ］［ｙ］｜
−（ｎ×ｎ）Ｐ［０］［０］                                        （１９）
【００９１】
一方、ＴＭＴＴ［０］［０］＜（ｎ×ｎ）Ｐ［０］［０］である場合、式（１７）を次式のように変形することができる。
【００９２】
Ｓ＝Σ（ｘ＝０〜ｎ−１，ｙ＝０〜ｎ−１）｜ＴＭＴＴ［ｘ］［ｙ］｜
＋（ｎ×ｎ）Ｐ［０］［０］−２ＴＭＴＴ［０］［０］                （２０）
【００９３】
ここで、式（１９）及び式（２０）の導出方法について説明する。例えば、ｎ＝４（ｍ＝２）の場合、式（１８）のＱ［ｘ］［ｙ］は、次式により記述される。
【００９４】
Ｑ［ｘ］［ｙ］＝Ｔ２ＭＴ２Ｔ［ｘ］［ｙ］−Ｔ２ＰＴ２Ｔ［ｘ］［ｙ］      （２１）
【００９５】
式（２１）のＴ２ＭＴ２Ｔ［ｘ］［ｙ］は、式（１５）から求められる。また、Ｐ［ｘ］［ｙ］＝Ｐ［０］［０］であるから、Ｔ２ＰＴ２Ｔ［ｘ］［ｙ］は、次式のように変形できる。
【００９６】
【数６】
2019062339.tif 000008
【００９７】
式（２２）より、式（２１）のＱ［ｘ］［ｙ］は、次式のように変形できる。
【００９８】
【数７】
2019062339.tif 000009
【００９９】
式（２３）より、Ｔ２ＭＴ２Ｔ［０］［０］≧（４×４）Ｐ［０］［０］である場合、式（１７）を次式のように変形することができる。
【０１００】
Ｓ＝（Ｔ２ＭＴ２Ｔ［０］［０］−（４×４）Ｐ［０］［０］）
＋Σ（ｘ＝０〜ｎ−１，ｙ＝０〜ｎ−１）｜Ｔ２ＭＴ２Ｔ［ｘ］［ｙ］｜
−Ｔ２ＭＴ２Ｔ［０］［０］
＝Σ（ｘ＝０〜ｎ−１，ｙ＝０〜ｎ−１）｜Ｔ２ＭＴ２Ｔ［ｘ］［ｙ］｜
−（４×４）Ｐ［０］［０］                                          （２４）
【０１０１】
式（２４）は、ｎ＝４の場合の式（１９）と一致している。一方、Ｔ２ＭＴ２Ｔ［０］［０］＜（４×４）Ｐ［０］［０］である場合、式（１７）を次式のように変形することができる。
【０１０２】
Ｓ＝−（Ｔ２ＭＴ２Ｔ［０］［０］−（４×４）Ｐ［０］［０］）
＋Σ（ｘ＝０〜ｎ−１，ｙ＝０〜ｎ−１）｜Ｔ２ＭＴ２Ｔ［ｘ］［ｙ］｜
−Ｔ２ＭＴ２Ｔ［０］［０］
＝Σ（ｘ＝０〜ｎ−１，ｙ＝０〜ｎ−１）｜Ｔ２ＭＴ２Ｔ［ｘ］［ｙ］｜
＋（４×４）Ｐ［０］［０］−２Ｔ２ＭＴ２Ｔ［０］［０］              （２５）
【０１０３】
式（２５）は、ｎ＝４の場合の式（２０）と一致している。さらに、ｎ＞４（ｍ＞２）の場合も同様にして、式（１７）から式（１９）及び式（２０）を導出することができる。
【０１０４】
式（１９）及び式（２０）のＴＭＴＴ［ｘ］［ｙ］と式（２０）のＴＭＴＴ［０］［０］は、Ｍの部分行列Ｍ［０］〜Ｍ［３］を変換行列Ｔｍ−１によって変換した変換結果から、次式により再帰的に計算することが可能である。
【０１０５】
【数８】
2019062339.tif 000010
【０１０６】
【数９】
2019062339.tif 000011
Ｈ［０］＝Ｔｍ−１Ｍ［０］Ｔｍ−１Ｔ＋Ｔｍ−１Ｍ［２］Ｔｍ−１Ｔ
＋Ｔｍ−１Ｍ［１］Ｔｍ−１Ｔ＋Ｔｍ−１Ｍ［３］Ｔｍ−１Ｔ      （２８）
Ｈ［１］＝Ｔｍ−１Ｍ［０］Ｔｍ−１Ｔ＋Ｔｍ−１Ｍ［２］Ｔｍ−１Ｔ
−Ｔｍ−１Ｍ［１］Ｔｍ−１Ｔ−Ｔｍ−１Ｍ［３］Ｔｍ−１Ｔ      （２９）
Ｈ［２］＝Ｔｍ−１Ｍ［０］Ｔｍ−１Ｔ−Ｔｍ−１Ｍ［２］Ｔｍ−１Ｔ
＋Ｔｍ−１Ｍ［１］Ｔｍ−１Ｔ−Ｔｍ−１Ｍ［３］Ｔｍ−１Ｔ      （３０）
Ｈ［３］＝Ｔｍ−１Ｍ［０］Ｔｍ−１Ｔ−Ｔｍ−１Ｍ［２］Ｔｍ−１Ｔ
−Ｔｍ−１Ｍ［１］Ｔｍ−１Ｔ＋Ｔｍ−１Ｍ［３］Ｔｍ−１Ｔ      （３１）
【０１０７】
また、式（１９）及び式（２０）のＰ［０］［０］は、Ｐの部分行列に対応するサブブロックの上及び左に隣接する所定領域に含まれる、複数の画素の画素値から、再帰的に計算することができる。
【０１０８】
そこで、選択部８０１は、処理対象のＰＵよりも小さなブロックサイズを有するＰＵの原画像に対するアダマール変換の変換結果を用いて、処理対象のＰＵの原画像に対するアダマール変換の変換結果を計算する。また、選択部８０１は、処理対象のＰＵよりも小さなブロックサイズを有するＰＵの上及び左に隣接する所定領域に含まれる、複数の画素の画素値を用いて、処理対象のＰＵに対するＰ［０］［０］を計算する。
【０１０９】
次に、選択部８０１は、処理対象のＰＵの原画像に対するアダマール変換の変換結果と、処理対象のＰＵに対するＰ［０］［０］とを用いて、式（１９）又は式（２０）によりＳＡＴＤを計算する。そして、選択部８０１は、計算したＳＡＴＤを用いて、処理対象のＰＵに対する符号化コストを計算する。
【０１１０】
したがって、最小のブロックのみに対してアダマール変換を実施しておけば、より大きなブロックに対するアダマール変換の変換結果を、より小さなブロックの変換結果から再帰的に求めることができる。このとき、原画像に対するアダマール変換の再帰的計算とＰ［０］［０］の再帰的計算とを、それぞれ独立に行うことが可能である。
【０１１１】
例えば、ＳＡＴＤを含む符号化コストとしてＲＤコストを用いる場合、式（１）に準じて、ＲＤコストＣを次式により計算することができる。
【０１１２】
Ｃ＝Ｓ＋λ×Ｒ＋Ｖ      （３２）
【０１１３】
式（３２）の変換係数λは、ＲＤコストＣに含まれるコストＳ（ＳＡＴＤ）に対するビット量Ｒの比率を表し、量子化パラメータＱＰに基づいて決定される。ビット量Ｒは、イントラ予測符号化で用いられるシンタックスを符号化する際に発生するビット量である。イントラ予測符号化で用いられるシンタックスとしては、例えば、次のようなものが用いられる。
【０１１４】
Coding quadtree syntax:
split_cu_flag
Coding unit syntax:
cu_transquant_bypass_flag
part_mode
prev_intra_luma_pred_flag
mpm_idx
rem_intra_luma_pred_mode
intra_chroma_pred_mode
【０１１５】
このうち、split_cu_flag及び part_modeについては、処理対象のＰＵのＣＵ  Ｄｅｐｔｈ及び最大のＣＵ  Ｄｅｐｔｈから、ビット量が決定される。それ以外のシンタックスについては、符号化対象動画像の統計値からビット量を決定してもよく、あらかじめ典型的な動画像で取得した統計値からビット量を決定してもよい。また、実装条件によってシンタックスのビット量が制限されている場合は、指定されたビット量を用いてもよい。エントロピー符号化において算術符号が用いられる場合は、統計又は推定によってシンタックスのビット量を決定してもよい。
【０１１６】
式（３２）のＶは、オフセット値を表す。ＲＤコストＣにオフセット値Ｖを付加することで、再構成画像を用いて生成した予測画像から計算されるＲＤコストと、符号化前の原画像を用いて生成した予測画像から計算されるＲＤコストとの差分を、補正することが可能になる。オフセット値Ｖとしては、サンプル動画像を用いたシミュレーション等により得られた統計値を用いることができる。
【０１１７】
図１０は、図８の選択部８０１の機能的構成例を示している。図１０の選択部８０１は、位置決定部１００１、アダマール変換部１００２、変換結果記憶部１００３、ＳＡＴＤ計算部１００４、ＳＡＴＤ記憶部１００５、加算部１００６、左加算値記憶部１００７、及び上加算値記憶部１００８を含む。
【０１１８】
さらに、選択部８０１は、ＤＣ計算部１００９、位置計算部１０１０、管理部１０１１、変換結果積み上げ部１０１２、ＤＣ積み上げ部１０１３、ＳＡＴＤ計算部１０１４、及び比較部１０１５を含む。さらに、選択部８０１は、オフセット記憶部１０１６、ＲＤコスト記憶部１０１７、及びＰＵサイズ記憶部１０１８を含む。
【０１１９】
位置決定部１００１は、ＣＴＵサイズに基づいて、ＣＴＵ内における最小のＰＵである４×４のブロックの位置（ｂｘ，ｂｙ）を決定し、位置（ｂｘ，ｂｙ）をアダマール変換部１００２及び加算部１００６へ出力する。
【０１２０】
図１１は、ＣＴＵ内における４×４のブロックの位置（ｂｘ，ｂｙ）の例を示している。図１１のＣＴＵのＣＴＵサイズは６４×６４であり、ＣＴＵ内の４×４のブロックの個数は１６×１６個である。したがって、ｂｘ＝０〜１５及びｂｙ＝０〜１５の範囲の（ｂｘ，ｂｙ）を用いて、各ブロックの位置を記述することができる。例えば、ブロック１１０１の位置は（ｂｘ，ｂｙ）＝（２，２）である。
【０１２１】
アダマール変換部１００２は、ＣＴＵ原画像内の位置（ｂｘ，ｂｙ）に対応する４×４のブロックの画素値を用いて、式（１５）によりアダマール変換結果Ｈ（ｂｘ，ｂｙ）を計算する。そして、アダマール変換部１００２は、Ｈ（ｂｘ，ｂｙ）を変換結果記憶部１００３及びＳＡＴＤ計算部１００４へ出力する。変換結果記憶部１００３は、位置（ｂｘ，ｂｙ）と対応付けて、アダマール変換結果Ｈ（ｂｘ，ｂｙ）を記憶する。
【０１２２】
加算部１００６は、ＣＴＵ原画像内の位置（ｂｘ，ｂｙ）に対応する４×４のブロックの上に隣接する周辺領域（上周辺領域）の画素値を用いて、上加算値Ｕ（ｂｘ，ｂｙ）を計算し、上加算値Ｕ（ｂｘ，ｂｙ）を上加算値記憶部１００８へ出力する。また、加算部１００６は、そのブロックの左に隣接する周辺領域（左周辺領域）の画素値を用いて、左加算値Ｌ（ｂｘ，ｂｙ）を計算し、左加算値Ｌ（ｂｘ，ｂｙ）を左加算値記憶部１００７へ出力する。
【０１２３】
図１２は、４×４のブロックの上周辺領域及び左周辺領域の例を示している。上加算値Ｕ（ｂｘ，ｂｙ）は、４×４のブロック１２０１の上周辺領域１２０２に含まれている４個の画素の画素値の和であり、左加算値Ｌ（ｂｘ，ｂｙ）は、４×４のブロック１２０１の左周辺領域１２０３に含まれている４個の画素の画素値の和である。
【０１２４】
上加算値記憶部１００８は、位置（ｂｘ，ｂｙ）と対応付けて上加算値Ｕ（ｂｘ，ｂｙ）を記憶し、左加算値記憶部１００７は、位置（ｂｘ，ｂｙ）と対応付けて左加算値Ｌ（ｂｘ，ｂｙ）を記憶する。
【０１２５】
ＤＣ計算部１００９は、位置（ｂｘ，ｂｙ）に対応する４×４のブロックの疑似ＤＣ予測画像の画素値ＤＣ（ｂｘ，ｂｙ）を、次式により計算し、ＤＣ（ｂｘ，ｂｙ）をＳＡＴＤ計算部１００４へ出力する。
【０１２６】
ＤＣ（ｂｘ，ｂｙ）＝（Ｕ（ｂｘ，ｂｙ）＋Ｌ（ｂｘ，ｂｙ））／８      （４１）
【０１２７】
式（４１）のＤＣ（ｂｘ，ｂｙ）は、左周辺領域及び上周辺領域に含まれる８個の画素の画素値の平均値を表しており、式（１９）及び式（２０）のＰ［０］［０］に対応する。４×４のブロックの左周辺領域及び上周辺領域の画素値が参照不可能である場合、例えば、ＤＣ計算部１００９は、ＤＣ（ｂｘ，ｂｙ）として１２８を出力する。
【０１２８】
ＳＡＴＤ計算部１００４は、アダマール変換結果Ｈ（ｂｘ，ｂｙ）及び画素値ＤＣ（ｂｘ，ｂｙ）から、式（１９）又は式（２０）により、位置（ｂｘ，ｂｙ）に対応する４×４のブロックのＳＡＴＤであるＳ（ｂｘ，ｂｙ）を計算する。そして、ＳＡＴＤ計算部１００４は、Ｓ（ｂｘ，ｂｙ）をＳＡＴＤ記憶部１００５へ出力し、ＳＡＴＤ記憶部１００５は、位置（ｂｘ，ｂｙ）と対応付けてＳ（ｂｘ，ｂｙ）を記憶する。
【０１２９】
位置計算部１０１０は、処理対象ブロックのブロックサイズを２Ａ×２Ａ（Ａ＝４，８，１６，３２）として、処理対象ブロックの位置（Ｘ，Ｙ）を計算し、ブロックサイズを示すパラメータＡ及び位置（Ｘ，Ｙ）を、管理部１０１１へ出力する。
【０１３０】
図１３は、図１１のＣＴＵ内における処理対象ブロックの位置（Ｘ，Ｙ）の例を示している。２Ａ×２Ａの処理対象ブロックの位置（Ｘ，Ｙ）は、その処理対象ブロック内において左上に位置するＡ×Ａのブロックの位置（ｂｘ，ｂｙ）によって表される。例えば、Ａ＝４の場合、８×８の処理対象ブロック内には４個の４×４のブロックが存在し、そのうち左上に位置するブロックの位置（ｂｘ，ｂｙ）が、処理対象ブロックの位置（Ｘ，Ｙ）として用いられる。
【０１３１】
図１３に示す１６×１６の処理対象ブロック１３０１の場合、処理対象ブロック１３０１内には４個の８×８のブロックが存在し、４個の８×８のブロックそれぞれの中には４個の４×４のブロックが存在する。ブロックＢ１〜ブロックＢ４は、４個の８×８のブロックそれぞれの中で左上に位置している４×４のブロックである。この場合、ブロックＢ１〜ブロックＢ４のうち、左上に位置するブロックＢ１の位置（８，８）が、処理対象ブロック１３０１の位置（Ｘ，Ｙ）として用いられる。
【０１３２】
位置計算部１０１０は、２Ａ×２Ａの処理対象ブロックの位置（Ｘ，Ｙ）の初期値を（０，０）に設定し、（Ｘ，Ｙ）＝（Ｘ＋（２Ａ／４），Ｙ）により位置（Ｘ，Ｙ）を２Ａ／４だけ右へ移動させる操作を繰り返す。そして、処理対象ブロックの右端がＣＴＵの右端に達した場合、（Ｘ，Ｙ）＝（０，Ｙ＋（２Ａ／４））により位置（Ｘ，Ｙ）を２Ａ／４だけ下の左端の位置へ移動させる操作を繰り返す。位置計算部１０１０は、このような操作を、処理対象ブロックの下端がＣＴＵの下端に達し、かつ、処理対象ブロックの右端がＣＴＵの右端に達するまで繰り返す。
【０１３３】
さらに、位置計算部１０１０は、Ａ＝Ａ＊２によりパラメータＡを更新して、２Ａ×２ＡがＣＴＵサイズ又は指定された最大のＰＵのブロックサイズに達するまで、同様の操作を繰り返す。
【０１３４】
管理部１０１１は、位置計算部１０１０が出力する位置（Ｘ，Ｙ）に基づいて、変換結果記憶部１００３、ＳＡＴＤ記憶部１００５、左加算値記憶部１００７、及び上加算値記憶部１００８からデータを読み出す。
【０１３５】
変換結果記憶部１００３からは、位置（Ｘ，Ｙ）が示す処理対象ブロック内の４個のＡ×Ａのブロックのアダマール変換結果である、Ｈ（Ｘ，Ｙ）、Ｈ（Ｘ＋Ａ／４，Ｙ）、Ｈ（Ｘ，Ｙ＋Ａ／４）、及びＨ（Ｘ＋Ａ／４，Ｙ＋Ａ／４）が読み出される。例えば、Ａ＝４の場合、処理対象ブロック内の４個の４×４のブロックのアダマール変換結果Ｈ（Ｘ，Ｙ）、Ｈ（Ｘ＋１，Ｙ）、Ｈ（Ｘ，Ｙ＋１）、及びＨ（Ｘ＋１，Ｙ＋１）が読み出される。管理部１０１１は、読み出した４個のＡ×Ａのブロックのアダマール変換結果を、変換結果積み上げ部１０１２へ出力する。
【０１３６】
変換結果積み上げ部１０１２は、４個のＡ×Ａのブロックのアダマール変換結果を用いて、式（２６）〜式（３１）により、処理対象ブロックのアダマール変換結果Ｈ（Ｘ，Ｙ）を計算し、Ｈ（Ｘ，Ｙ）を管理部１０１１及びＳＡＴＤ計算部１０１４へ出力する。管理部１０１１は、そのアダマール変換結果Ｈ（Ｘ，Ｙ）を変換結果記憶部１００３へ出力し、変換結果記憶部１００３は、位置（Ｘ，Ｙ）と対応付けて、アダマール変換結果Ｈ（Ｘ，Ｙ）を記憶する。
【０１３７】
例えば、図１３に示す１６×１６の処理対象ブロック１３０１の場合、処理対象ブロック１３０１内には４個の８×８のブロックが存在する。そのうち左上に位置する８×８のブロックのアダマール変換結果は、ブロックＢ１の位置（８，８）に対応付けて格納され、右上に位置する８×８のブロックのアダマール変換結果は、ブロックＢ２の位置（１０，８）に対応付けて格納される。
【０１３８】
また、左下に位置する８×８のブロックのアダマール変換結果は、ブロックＢ３の位置（８，１０）に対応付けて格納され、右下に位置する８×８のブロックのアダマール変換結果は、ブロックＢ４の位置（１０，１０）に対応付けて格納される。
【０１３９】
そして、ブロックＢ１〜ブロックＢ４の位置に対応付けて格納されている４個のアダマール変換結果が読み出され、読み出されたアダマール変換結果を用いて、処理対象ブロック１３０１のアダマール変換結果が計算される。そして、計算された処理対象ブロック１３０１のアダマール変換結果は、ブロックＢ１の位置（８，８）に対応付けて格納される。
【０１４０】
処理対象ブロック１３０１を含む３２×３２のブロックが新たな処理対象ブロックとして選択されたとき、ブロックＢ１の位置に対応付けて格納されたアダマール変換結果が、１６×１６のブロックのアダマール変換結果として読み出される。
【０１４１】
なお、変換結果記憶部１００３の記憶領域は、図１３のＣＴＵのような２次元領域である必要はなく、位置（ｂｘ，ｂｙ）に対応付けられた１次元の連続領域であってもよい。
【０１４２】
上加算値記憶部１００８からは、位置（Ｘ，Ｙ）が示す処理対象ブロックの上周辺領域に対応するｋ個の上加算値Ｕ（Ｘ，Ｙ）〜Ｕ（Ｘ＋ｋ−１，Ｙ）が読み出される。また、左加算値記憶部１００７からは、処理対象ブロックの左周辺領域に対応するｋ個の左加算値Ｌ（Ｘ，Ｙ）〜Ｌ（Ｘ，Ｙ＋ｋ−１）が読み出される。上加算値記憶部１００８及び左加算値記憶部１００７から読み出される加算値の個数ｋは、パラメータＡを用いて次式により決定される。
【０１４３】
ｋ＝（１＜＜ｌｏｇ２（２Ａ））＞＞２      （４２）
【０１４４】
式（４２）の“１＜＜ｌｏｇ２（２Ａ）”は、２進数で表した“１”を左へｌｏｇ２（２Ａ）ビットだけシフトする操作を表し、“（１＜＜ｌｏｇ２（２Ａ））＞＞２”は、（１＜＜ｌｏｇ２（２Ａ））を右へ２ビットだけシフトする操作を表す。
【０１４５】
図１４は、読み出される加算値の個数ｋの例を示している。Ａ＝４，８，１６，３２のそれぞれに対してｋ＝２，４，８，１６となる。
【０１４６】
例えば、Ａ＝４の場合、８×８の処理対象ブロックの上周辺領域（８画素）に対応する２個の４×４のブロックの上加算値Ｕ（ｂｘ，ｂｙ）が読み出される。また、８×８の処理対象ブロックの左周辺領域（８画素）に対応する２個の４×４のブロックの左加算値Ｌ（ｂｘ，ｂｙ）が読み出される。
【０１４７】
Ａ＝８の場合、１６×１６の処理対象ブロックの上周辺領域（１６画素）に対応する４個の４×４のブロックの上加算値Ｕ（ｂｘ，ｂｙ）が読み出される。また、１６×１６の処理対象ブロックの左周辺領域（１６画素）に対応する４個の４×４のブロックの左加算値Ｌ（ｂｘ，ｂｙ）が読み出される。
【０１４８】
Ａ＝１６の場合、３２×３２の処理対象ブロックの上周辺領域（３２画素）に対応する８個の４×４のブロックの上加算値Ｕ（ｂｘ，ｂｙ）が読み出される。また、３２×３２の処理対象ブロックの左周辺領域（３２画素）に対応する８個の４×４のブロックの左加算値Ｌ（ｂｘ，ｂｙ）が読み出される。
【０１４９】
Ａ＝３２の場合、６４×６４の処理対象ブロックの上周辺領域（６４画素）に対応する１６個の４×４のブロックの上加算値Ｕ（ｂｘ，ｂｙ）が読み出される。また、６４×６４の処理対象ブロックの左周辺領域（６４画素）に対応する１６個の４×４のブロックの左加算値Ｌ（ｂｘ，ｂｙ）が読み出される。
【０１５０】
なお、処理対象ブロックの上加算値Ｕ及び左加算値Ｌは、４×４のブロック毎の上加算値Ｕ及び左加算値Ｌを用いて計算する代わりに、パラメータＡが示すブロックサイズに応じて上加算値Ｕ及び左加算値Ｌを順次積み上げる方法により、計算することも可能である。この場合、例えば、４×４のブロックの上加算値Ｕ又は左加算値Ｌから、８×８のブロックの上加算値Ｕ又は左加算値Ｌが計算され、８×８のブロックの上加算値Ｕ又は左加算値Ｌから、１６×１６のブロックの上加算値Ｕ又は左加算値Ｌが計算される。
【０１５１】
図１５は、上加算値記憶部１００８から読み出される上加算値Ｕ（ｂｘ，ｂｙ）の例を示している。１６×１６の処理対象ブロック１３０１の上周辺領域に対応する加算値は、領域１５０１内の（８，８）、（９，８）、（１０，８）、及び（１１，８）の４個のブロックの位置に対応付けて格納されている。そこで、これらの４個の位置から、Ｕ（８，８）、Ｕ（９，８）、Ｕ（１０，８）、及びＵ（１１，８）が読み出される。
【０１５２】
図１６は、左加算値記憶部１００７から読み出される左加算値Ｌ（ｂｘ，ｂｙ）の例を示している。１６×１６の処理対象ブロック１３０１の左周辺領域に対応する加算値は、領域１６０１内の（８，８）、（８，９）、（８，１０）、及び（８，１１）の４個のブロックの位置に対応付けて格納されている。そこで、これらの４個の位置から、Ｌ（８，８）、Ｌ（８，９）、Ｌ（８，１０）、及びＬ（８，１１）が読み出される。
【０１５３】
管理部１０１１は、読み出したｋ個の上加算値Ｕ（ｂｘ，ｂｙ）及びｋ個の左加算値Ｌ（ｂｘ，ｂｙ）を、ＤＣ積み上げ部１０１３へ出力する。
【０１５４】
ＤＣ積み上げ部１０１３は、ｋ個の上加算値Ｕ（ｂｘ，ｂｙ）及びｋ個の左加算値Ｌ（ｂｘ，ｂｙ）を用いて、処理対象ブロックの疑似ＤＣ予測画像の画素値ＤＣ（Ｘ，Ｙ）を、次式により計算し、ＤＣ（Ｘ，Ｙ）をＳＡＴＤ計算部１０１４へ出力する。
【０１５５】
ＤＣ（Ｘ，Ｙ）＝（Σ（ｉ＝０〜ｋ−１）Ｕ（Ｘ＋ｉ，Ｙ）
＋Σ（ｉ＝０〜ｋ−１）Ｌ（Ｘ，Ｙ＋ｉ））
／（２Ａ＋２Ａ）                              （４３）
【０１５６】
式（４３）のΣ（ｉ＝０〜ｋ−１）は、ｉ＝０〜ｋ−１の範囲についての総和を表す。式（４３）のＤＣ（Ｘ，Ｙ）は、式（１９）及び式（２０）のＰ［０］［０］に対応する。例えば、Ａ＝４の場合、ＤＣ積み上げ部１０１３は、ＤＣ（Ｘ，Ｙ）を次式により計算することができる。
【０１５７】
ＤＣ（Ｘ，Ｙ）＝（Ｕ（Ｘ，Ｙ）＋Ｕ（Ｘ＋１，Ｙ）
＋Ｌ（Ｘ，Ｙ）＋Ｌ（Ｘ，Ｙ＋１）
＋（８＋８−１））／（８＋８）      （４４）
【０１５８】
式（４４）の右辺の（８＋８−１）は、８＋８で除算した結果を小数点以下切り上げの整数にするために付加されている。
【０１５９】
ＳＡＴＤ記憶部１００５からは、位置（Ｘ，Ｙ）が示す処理対象ブロック内の４個の４×４のブロックのＳＡＴＤである、Ｓ（Ｘ，Ｙ）、Ｓ（Ｘ＋１，Ｙ）、Ｓ（Ｘ，Ｙ＋１）、及びＳ（Ｘ＋１，Ｙ＋１）が読み出される。管理部１０１１は、読み出した４個の４×４のブロックのＳＡＴＤを、比較部１０１５へ出力する。
【０１６０】
ＳＡＴＤ計算部１０１４は、処理対象ブロックのアダマール変換結果Ｈ（Ｘ，Ｙ）及び画素値ＤＣ（Ｘ，Ｙ）から、式（１９）又は式（２０）により、処理対象ブロックのＳＡＴＤであるＳ（Ｘ，Ｙ）を計算する。そして、ＳＡＴＤ計算部１０１４は、Ｓ（Ｘ，Ｙ）を比較部１０１５へ出力する。
【０１６１】
オフセット記憶部１０１６は、式（３２）のオフセット値Ｖを記憶する。比較部１０１５は、量子化パラメータＱＰに基づいて式（３２）の変換係数λを決定し、オフセット記憶部１０１６からオフセット値Ｖを読み出す。そして、比較部１０１５は、ＳＡＴＤ計算部１０１４が出力する処理対象ブロックのＳＡＴＤ、変換係数λ、ビット量Ｒ、及びオフセット値Ｖを用いて、式（３２）により処理対象ブロックのＲＤコストＲＤｎを計算する。
【０１６２】
Ａ＝４の場合、比較部１０１５は、管理部１０１１が出力する４個の４×４のブロックのＳＡＴＤ、変換係数λ、ビット量Ｒ、及びオフセット値Ｖを用いて、式（３２）により各ブロックのＲＤコストＣを計算する。そして、比較部１０１５は、４個の４×４のブロックのＲＤコストＣの和である、ＲＤコストＲＤｄを計算する。
【０１６３】
次に、比較部１０１５は、ＲＤコストＲＤｄとＲＤコストＲＤｎとを比較し、小さい方のＲＤコストに対応するブロックサイズを、最適なＰＵのブロックサイズとして選択する。そして、比較部１０１５は、選択したブロックサイズをＰＵサイズ記憶部１０１８に格納し、選択したブロックサイズに対応するＲＤコストＣをＲＤコスト記憶部１０１７に格納する。
【０１６４】
一方、Ａ＞４の場合、処理対象ブロック内の複数のブロックのＲＤコストＣが、既にＲＤコスト記憶部１０１７に格納されている。そこで、比較部１０１５は、ＲＤコスト記憶部１０１７からそれらのブロックのＲＤコストＣを読み出し、読み出したＲＤコストＣの和であるＲＤコストＲＤｄを計算する。
【０１６５】
この場合、処理対象ブロック内のすべてのＰＵのブロックサイズがＡ×Ａに設定されているとは限らず、一部の領域ではＡ×Ａよりも小さなＰＵが選択されていることもある。したがって、ＲＤコストＲＤｄは、処理対象ブロック内の４個以上のブロックのＲＤコストＣの和になる。
【０１６６】
次に、比較部１０１５は、ＲＤコストＲＤｄとＲＤコストＲＤｎとを比較し、小さい方のＲＤコストに対応するブロックサイズを、最適なＰＵのブロックサイズとして選択する。ＲＤコストＲＤｎがＲＤコストＲＤｄよりも小さい場合、比較部１０１５は、ブロックサイズ２Ａ×２Ａを選択し、ブロックサイズ２Ａ×２ＡをＰＵサイズ記憶部１０１８に格納する。そして、比較部１０１５は、ブロックサイズ２Ａ×２Ａに対応するＲＤコストＲＤｎをＲＤコスト記憶部１０１７に格納する。
【０１６７】
一方、ＲＤコストＲＤｄがＲＤコストＲＤｎよりも小さい場合、比較部１０１５は、Ａ×Ａ以下の１つ又は複数のブロックサイズを選択する。この場合、選択したブロックサイズは、既にＰＵサイズ記憶部１０１８に格納されており、選択したブロックサイズに対応するＲＤコストＣは、既にＲＤコスト記憶部１０１７に格納されている。したがって、比較部１０１５は、ＲＤコスト記憶部１０１７及びＰＵサイズ記憶部１０１８のデータを更新しない。
【０１６８】
処理対象ブロックのブロックサイズ２Ａ×２Ａが最大値に達した場合、比較部１０１５は、ＰＵサイズ記憶部１０１８の各要素が記憶するブロックサイズを、最適なＰＵのブロックサイズとして出力する。また、比較部１０１５は、ＲＤコスト記憶部１０１７の各要素が記憶するＲＤコストＣを、最適なＰＵのブロックサイズに対応する符号化コストとして出力する。
【０１６９】
図１７は、比較部１０１５がＲＤコスト記憶部１０１７及びＰＵサイズ記憶部１０１８のデータにアクセスする順序の例を示している。この例では、ＣＴＵのＣＴＵサイズは３２×３２であり、ＣＴＵ内の４×４のブロックの個数は８×８個である。
【０１７０】
ＲＤコスト記憶部１０１７及びＰＵサイズ記憶部１０１８の記憶領域は、例えば、複数の要素からなる１次元領域であり、これらの要素は、Ｚスキャン順のインデックスＩ（Ｉ＝０〜６３）によって識別される。各要素は、４×４のブロックのデータを記憶する。
【０１７１】
図１７（ａ）は、Ａ＝４の場合に、６４個のデータを８×８のブロックの単位でＺスキャン順にアクセスする順序の例を示している。例えば、８×８の処理対象ブロックがＩ＝２４に対応する場合（（Ｘ，Ｙ）＝（４，２））、Ｉ＝２４〜２７に対応する４個の４×４のブロックのＲＤコストＲＤｄと、８×８の処理対象ブロックのＲＤコストＲＤｎとが比較される。
【０１７２】
ここで、処理対象ブロックのブロックサイズ８×８が選択された場合、比較部１０１５は、ＲＤコスト記憶部１０１７のＩ＝２４〜２７に対応する４個の要素に、ＲＤコストＲＤｎを格納する。そして、比較部１０１５は、ＰＵサイズ記憶部１０１８のＩ＝２４〜２７に対応する４個の要素に、ブロックサイズ８×８を格納する。
【０１７３】
一方、ブロックサイズ４×４が選択された場合、比較部１０１５は、ＲＤコスト記憶部１０１７のＩ＝２４〜２７に対応する４個の要素に、４個の４×４のブロックそれぞれのＲＤコストＣを格納する。そして、比較部１０１５は、ＰＵサイズ記憶部１０１８のＩ＝２４〜２７に対応する４個の要素に、ブロックサイズ４×４を格納する。
【０１７４】
このように、比較部１０１５が選択したブロックサイズに対応するＲＤコストＣは、２Ａ×２Ａの処理対象ブロックに対応する、ＲＤコスト記憶部１０１７の複数の要素すべてに格納される。同様に、比較部１０１５が選択したブロックサイズは、２Ａ×２Ａの処理対象ブロックに対応する、ＰＵサイズ記憶部１０１８の複数の要素すべてに格納される。
【０１７５】
比較部１０１５は、Ａ＝４，８，１６，３２の順に処理を進めるため、Ａ＞４の場合、２Ａ×２Ａの処理対象ブロック内の４個のＡ×Ａのブロックに対応する領域のデータは、既にＲＤコスト記憶部１０１７及びＰＵサイズ記憶部１０１８に格納されている。
【０１７６】
そこで、比較部１０１５は、４個のＡ×Ａのブロックに対応する領域のＲＤコストＣをＲＤコスト記憶部１０１７から読み出す際、処理対象ブロックの位置（Ｘ，Ｙ）からＺスキャン順のインデックスＩに従って、ＲＤコスト記憶部１０１７の各要素にアクセスする。このとき、比較部１０１５は、インデックスＩを導出する計算式又はアクセス用の変換テーブルを用いてもよい。
【０１７７】
図１７（ｂ）は、Ａ＝８の場合に、６４個のデータを１６×１６のブロックの単位でＺスキャン順にアクセスする順序の例を示している。
【０１７８】
変換結果記憶部１００３、ＳＡＴＤ記憶部１００５、左加算値記憶部１００７、上加算値記憶部１００８、ＲＤコスト記憶部１０１７、及びＰＵサイズ記憶部１０１８の記憶領域の形式は、実施形態に限定されるものではない。例えば、メモリ使用量、処理量、アクセス容易性等の観点から、別の形式の記憶領域を用いることも可能である。
【０１７９】
ところで、図２に示したように、イントラ予測符号化の場合、最小のＣＵを除いて、ＰＵのブロックサイズはＣＵのブロックサイズと一致する。一方、最小のＣＵについては、ＰＵのブロックサイズとして、ＣＵのブロックサイズ又はＣＵを４分割したブロックサイズを選択することができる。また、ＣＴＵサイズ、最大のＣＵのブロックサイズ、及び最小のＣＵのブロックサイズは、シンタックスによって指定することができる。
【０１８０】
そこで、ＣＴＵサイズが最大のＣＵのブロックサイズよりも大きい場合、ＣＴＵサイズ以下、かつ、最大のＣＵのブロックサイズよりも大きいＰＵについては、最適なＰＵの候補から除外することができる。あるいは、そのようなＰＵについては、選択部８０１の処理対象から除外しても構わない。
【０１８１】
また、最大のＣＵのブロックサイズによって決められる最小のＰＵのブロックサイズが４×４よりも大きい場合、最小のＰＵのブロックサイズよりも小さいＰＵについては、最適なＰＵの候補から除外することができる。あるいは、そのようなＰＵについては、選択部８０１の処理対象から除外しても構わない。この場合、Ａ×Ａの最小値として、４×４の代わりに最小のＰＵのブロックサイズが用いられる。
【０１８２】
図１８は、図９のステップ９０１において図１０の選択部８０１が行うブロックサイズ決定処理の例を示すフローチャートである。まず、位置決定部１００１は、ＣＴＵ内における４×４のブロックの位置（ｂｘ，ｂｙ）を決定する（ステップ１８０１）。
【０１８３】
次に、アダマール変換部１００２は、位置（ｂｘ，ｂｙ）に対応する４×４のブロックのアダマール変換を行い（ステップ１８０２）、アダマール変換結果Ｈ（ｂｘ，ｂｙ）を変換結果記憶部１００３に格納する（ステップ１８０３）。
【０１８４】
次に、加算部１００６は、位置（ｂｘ，ｂｙ）に対応する４×４のブロックの上周辺領域における上加算値Ｕ（ｂｘ，ｂｙ）を計算し（ステップ１８０４）、上加算値Ｕ（ｂｘ，ｂｙ）を上加算値記憶部１００８に格納する（ステップ１８０５）。
【０１８５】
次に、加算部１００６は、位置（ｂｘ，ｂｙ）に対応する４×４のブロックの左周辺領域における左加算値Ｌ（ｂｘ，ｂｙ）を計算し（ステップ１８０６）、左加算値Ｌ（ｂｘ，ｂｙ）を左加算値記憶部１００７に格納する（ステップ１８０７）。
【０１８６】
次に、ＤＣ計算部１００９は、上加算値Ｕ（ｂｘ，ｂｙ）及び左加算値Ｌ（ｂｘ，ｂｙ）を用いて、位置（ｂｘ，ｂｙ）に対応する４×４のブロックの疑似ＤＣ予測画像の画素値ＤＣ（ｂｘ，ｂｙ）を計算する（ステップ１８０８）。
【０１８７】
次に、ＳＡＴＤ計算部１００４は、アダマール変換結果Ｈ（ｂｘ，ｂｙ）及び画素値ＤＣ（ｂｘ，ｂｙ）を用いて、位置（ｂｘ，ｂｙ）に対応する４×４のブロックのＳＡＴＤであるＳ（ｂｘ，ｂｙ）を計算する（ステップ１８０９）。そして、ＳＡＴＤ計算部１００４は、Ｓ（ｂｘ，ｂｙ）をＳＡＴＤ記憶部１００５に格納する（ステップ１８１０）。
【０１８８】
次に、位置決定部１００１は、ＣＴＵ内のすべての４×４のブロックを処理したか否かをチェックする（ステップ１８１１）。未処理のブロックが残っている場合（ステップ１８１１，ＮＯ）、選択部８０１は、次の４×４のブロックについてステップ１８０１以降の処理を繰り返す。すべての４×４のブロックを処理した場合（ステップ１８１１，ＹＥＳ）、選択部８０１は、積み上げ処理を行う（ステップ１８１２）。
【０１８９】
図１９は、図１８のステップ１８１２における積み上げ処理の例を示すフローチャートである。まず、位置計算部１０１０は、パラメータＡを４に設定し（ステップ１９０１）、２Ａ×２Ａの処理対象ブロックの位置を示す座標Ｙを０に設定し（ステップ１９０２）、その位置を示す座標Ｘを０に設定する（ステップ１９０３）。
【０１９０】
次に、管理部１０１１は、処理対象ブロック内の４個のＡ×Ａのブロックのアダマール変換結果を、変換結果記憶部１００３から読み出す（ステップ１９０４）。次に、変換結果積み上げ部１０１２は、４個のＡ×Ａのブロックのアダマール変換結果を用いて、式（２６）〜式（３１）により、処理対象ブロックのアダマール変換結果Ｈ（Ｘ，Ｙ）を計算する（ステップ１９０５）。そして、管理部１０１１は、アダマール変換結果Ｈ（Ｘ，Ｙ）を変換結果記憶部１００３に格納する（ステップ１９０６）。
【０１９１】
次に、管理部１０１１は、処理対象ブロックの上周辺領域に対応するｋ個の上加算値を、上加算値記憶部１００８から読み出す（ステップ１９０７）。次に、管理部１０１１は、処理対象ブロックの左周辺領域に対応するｋ個の左加算値を、左加算値記憶部１００７から読み出す（ステップ１９０８）。そして、ＤＣ積み上げ部１０１３は、ｋ個の上加算値及びｋ個の左加算値を用いて、式（４３）により、処理対象ブロックの疑似ＤＣ予測画像の画素値ＤＣ（Ｘ，Ｙ）を計算する（ステップ１９０９）。
【０１９２】
次に、ＳＡＴＤ計算部１０１４は、処理対象ブロックのアダマール変換結果Ｈ（Ｘ，Ｙ）及び画素値ＤＣ（Ｘ，Ｙ）から、式（１９）又は式（２０）により、処理対象ブロックのＳＡＴＤであるＳ（Ｘ，Ｙ）を計算する（ステップ１９１０）。そして、比較部１０１５は、Ｓ（Ｘ，Ｙ）を用いて比較処理を行う（ステップ１９１１）。
【０１９３】
次に、位置計算部１０１０は、Ｘ＝Ｘ＋（２Ａ／４）によりＸを更新し（ステップ１９１２）、ＸがＣＴＵの右端を超えたか否かをチェックする（ステップ１９１３）。ＸがＣＴＵの右端を超えていない場合（ステップ１９１３，ＮＯ）、選択部８０１は、更新されたＸに基づいて、ステップ１９０４以降の処理を繰り返す。
【０１９４】
ＸがＣＴＵの右端を超えた場合（ステップ１９１３，ＹＥＳ）、位置計算部１０１０は、Ｙ＝Ｙ＋（２Ａ／４）によりＹを更新し（ステップ１９１４）、ＹがＣＴＵの下端を超えたか否かをチェックする（ステップ１９１５）。ＹがＣＴＵの下端を超えていない場合（ステップ１９１５，ＮＯ）、選択部８０１は、更新されたＹに基づいて、ステップ１９０３以降の処理を繰り返す。
【０１９５】
ＹがＣＴＵの下端を超えた場合（ステップ１９１５，ＹＥＳ）、位置計算部１０１０は、Ａ＝Ａ＊２によりパラメータＡを更新し（ステップ１９１６）、Ａ×ＡをＣＴＵサイズと比較する（ステップ１９１７）。Ａ×ＡがＣＴＵサイズよりも小さい場合（ステップ１９１７，ＮＯ）、選択部８０１は、更新されたパラメータＡに基づいて、ステップ１９０２以降の処理を繰り返す。
【０１９６】
Ａ×ＡがＣＴＵサイズである場合（ステップ１９１７，ＹＥＳ）、比較部１０１５は、ＰＵサイズ記憶部１０１８の各要素が記憶するブロックサイズを、最適なＰＵのブロックサイズとして出力する（ステップ１９１８）。
【０１９７】
図２０は、図１９のステップ１９１１における比較処理の例を示すフローチャートである。まず、比較部１０１５は、ＳＡＴＤ計算部１０１４が出力する処理対象ブロックのＳＡＴＤを用いて、式（３２）により、処理対象ブロックのＲＤコストＲＤｎを計算する（ステップ２００１）。
【０１９８】
次に、比較部１０１５は、４個のＡ×ＡのブロックのＲＤコストＲＤｄを計算する（ステップ２００２）。Ａ＝４の場合、比較部１０１５は、４個の４×４のブロックのＳＡＴＤを用いて、式（３２）により、各ブロックのＲＤコストＣを計算し、それらのＲＤコストＣを加算することで、ＲＤコストＲＤｄを計算する。
【０１９９】
一方、Ａ＞４の場合、比較部１０１５は、処理対象ブロック内の４個以上のブロックのＲＤコストＣを、ＲＤコスト記憶部１０１７から読み出し、それらのＲＤコストＣを加算することで、ＲＤコストＲＤｄを計算する。
【０２００】
次に、比較部１０１５は、ＲＤコストＲＤｄとＲＤコストＲＤｎとを比較する（ステップ２００３）。ＲＤコストＲＤｄがＲＤコストＲＤｎよりも小さい場合（ステップ２００３，ＹＥＳ）、比較部１０１５は、４個のＡ×Ａのブロックに対応する１つ又は複数のブロックサイズを選択する（ステップ２００４）。
【０２０１】
例えば、Ａ＝４の場合、比較部１０１５は、ブロックサイズ４×４を選択し、そのブロックサイズを、ＰＵサイズ記憶部１０１８の４個の４×４のブロックの要素に格納する。そして、比較部１０１５は、４×４の各ブロックのＲＤコストＣを、ＲＤコスト記憶部１０１７の各ブロックの要素に格納する。
【０２０２】
一方、Ａ＞４の場合、比較部１０１５は、４個のＡ×Ａのブロックに対応する領域において既に設定されている１つ又は複数のブロックサイズを選択する。この場合、比較部１０１５は、ＲＤコスト記憶部１０１７及びＰＵサイズ記憶部１０１８のデータを更新しない。
【０２０３】
ＲＤコストＲＤｄがＲＤコストＲＤｎ以上である場合（ステップ２００３，ＮＯ）、比較部１０１５は、ブロックサイズ２Ａ×２Ａを選択する（ステップ２００５）。次に、比較部１０１５は、ＲＤコスト記憶部１０１７の２Ａ×２Ａの処理対象ブロックに対応する複数の要素にＲＤコストＲＤｎを格納することで、ＲＤコスト記憶部１０１７のデータを更新する（ステップ２００６）。そして、比較部１０１５は、ＰＵサイズ記憶部１０１８の２Ａ×２Ａの処理対象ブロックに対応する複数の要素にブロックサイズ２Ａ×２Ａを格納することで、ＰＵサイズ記憶部１０１８のデータを更新する（ステップ２００７）。
【０２０４】
なお、Ａ＞４の場合、ステップ２００２において、比較部１０１５は、処理対象ブロック内に既に設定されているブロックサイズのブロック毎に１つのＲＤコストＣを読み出す。そして、比較部１０１５は、複数のブロックのＲＤコストＣを加算することで、ＲＤコストＲＤｄを計算する。
【０２０５】
図２１〜図２４は、HEVC Test Model（ＨＭ）によりＰＵのブロックサイズを決定した場合と、図１０の選択部８０１によりＰＵのブロックサイズを決定した場合とを比較した第１〜第４のシミュレーション結果の例を示している。ＨＭは、標準化団体の参照ソフトウェアである。
【０２０６】
図２１（ａ）は、サンプル動画像＃１に含まれる１枚の画像に対して、ＨＭがＰＵのブロックサイズを８×８に決定した場合に、選択部８０１が計算したＲＤコストの例を示している。縦軸は、８×８のブロックのＲＤコストＣ８を表し、横軸は、８×８のブロック内の４個の４×４のブロックのＲＤコストＣ４を表す。ＲＤコストＣ４とＲＤコストＣ８の組み合わせを表す各点は、ＨＭによってブロックサイズが８×８に決定されたＰＵ毎にプロットされている。直線２１０１は、これらの点を近似する近似直線を表す。
【０２０７】
ＲＤコストＣ８の方がＲＤコストＣ４よりも小さい場合、選択部８０１は、ＨＭと同様に、ブロックサイズを８×８に決定する。一方、ＲＤコストＣ４の方がＲＤコストＣ８よりも小さい場合、選択部８０１は、ブロックサイズを４×４以下に決定する。
【０２０８】
図２１（ｂ）は、サンプル動画像＃２に含まれる１枚の画像に対して、ＨＭがＰＵのブロックサイズを８×８に決定した場合に、選択部８０１が計算したＲＤコストの例を示している。図２１（ａ）と同様に、ＲＤコストＣ４とＲＤコストＣ８の組み合わせを表す各点は、ＨＭによってブロックサイズが８×８に決定されたＰＵ毎にプロットされている。直線２１０２は、これらの点を近似する近似直線を表す。
【０２０９】
図２２（ａ）は、サンプル動画像＃１に含まれる１枚の画像に対して、ＨＭがＰＵのブロックサイズを１６×１６に決定した場合に、選択部８０１が計算したＲＤコストの例を示している。縦軸は、１６×１６のブロックのＲＤコストＣ１６を表し、横軸は、１６×１６のブロック内の４個の８×８のブロックのＲＤコストＣ８を表す。ＲＤコストＣ８とＲＤコストＣ１６の組み合わせを表す各点は、ＨＭによってブロックサイズが１６×１６に決定されたＰＵ毎にプロットされている。直線２２０１は、これらの点を近似する近似直線を表す。
【０２１０】
図２２（ｂ）は、サンプル動画像＃２に含まれる１枚の画像に対して、ＨＭがＰＵのブロックサイズを１６×１６に決定した場合に、選択部８０１が計算したＲＤコストの例を示している。図２２（ａ）と同様に、ＲＤコストＣ８とＲＤコストＣ１６の組み合わせを表す各点は、ＨＭによってブロックサイズが１６×１６に決定されたＰＵ毎にプロットされている。直線２２０２は、これらの点を近似する近似直線を表す。
【０２１１】
図２３（ａ）は、サンプル動画像＃１に含まれる１枚の画像に対して、ＨＭがＰＵのブロックサイズを３２×３２に決定した場合に、選択部８０１が計算したＲＤコストの例を示している。縦軸は、３２×３２のブロックのＲＤコストＣ３２を表し、横軸は、３２×３２のブロック内の４個の１６×１６のブロックのＲＤコストＣ１６を表す。ＲＤコストＣ１６とＲＤコストＣ３２の組み合わせを表す各点は、ＨＭによってブロックサイズが３２×３２に決定されたＰＵ毎にプロットされている。直線２３０１は、これらの点を近似する近似直線を表す。
【０２１２】
図２３（ｂ）は、サンプル動画像＃２に含まれる１枚の画像に対して、ＨＭがＰＵのブロックサイズを３２×３２に決定した場合に、選択部８０１が計算したＲＤコストの例を示している。図２３（ａ）と同様に、ＲＤコストＣ１６とＲＤコストＣ３２の組み合わせを表す各点は、ＨＭによってブロックサイズが３２×３２に決定されたＰＵ毎にプロットされている。直線２３０２は、これらの点を近似する近似直線を表す。
【０２１３】
図２４（ａ）は、サンプル動画像＃１に含まれる１枚の画像に対して、ＨＭがＰＵのブロックサイズを６４×６４に決定した場合に、選択部８０１が計算したＲＤコストの例を示している。縦軸は、６４×６４のブロックのＲＤコストＣ６４を表し、横軸は、６４×６４のブロック内の４個の３２×３２のブロックのＲＤコストＣ３２を表す。ＲＤコストＣ３２とＲＤコストＣ６４の組み合わせを表す各点は、ＨＭによってブロックサイズが６４×６４に決定されたＰＵ毎にプロットされている。直線２４０１は、これらの点を近似する近似直線を表す。
【０２１４】
図２４（ｂ）は、サンプル動画像＃２に含まれる１枚の画像に対して、ＨＭがＰＵのブロックサイズを６４×６４に決定した場合に、選択部８０１が計算したＲＤコストの例を示している。図２４（ａ）と同様に、ＲＤコストＣ３２とＲＤコストＣ６４の組み合わせを表す各点は、ＨＭによってブロックサイズが６４×６４に決定されたＰＵ毎にプロットされている。直線２４０２は、これらの点を近似する近似直線を表す。
【０２１５】
図２１〜図２４のシミュレーション結果から、ＨＭによって決定されるＰＵのブロックサイズと、選択部８０１によって決定されるＰＵのブロックサイズとの間に強い相関があることが分かる。したがって、図１０の選択部８０１によれば、ＨＭと近似するＰＵ分割を実現することが可能である。
【０２１６】
図６の動画像符号化装置６０１では、符号化前の原画像のみを用いて疑似ＤＣ予測画像を生成しているが、符号化済みＣＴＵの再構成画像を利用して疑似ＤＣ予測画像を生成することも可能である。
【０２１７】
図２５は、再構成画像を利用する動画像符号化装置４０１の具体例を示している。図２５の動画像符号化装置２５０１は、図６の動画像符号化装置６０１と同様の構成を有し、再構成部６２３は、フィルタが適用される前の再構成画像を判定部６１６へ出力する。
【０２１８】
この場合、再構成画像が図１０の加算部１００６に入力される。加算部１００６は、ＣＴＵ原画像内の位置（ｂｘ，ｂｙ）がＣＴＵの上の境界に対応する場合、上に隣接する符号化済みＣＴＵの再構成画像の画素値を、４×４のブロックの上周辺領域の画素値として用いて、上加算値Ｕ（ｂｘ，ｂｙ）を計算する。また、加算部１００６は、位置（ｂｘ，ｂｙ）がＣＴＵの左の境界に対応する場合、左に隣接する符号化済みＣＴＵの再構成画像の画素値を、４×４のブロックの左周辺領域の画素値として用いて、左加算値Ｌ（ｂｘ，ｂｙ）を計算する。
【０２１９】
したがって、ＤＣ計算部１００９及びＤＣ積み上げ部１０１３は、符号化済みＣＴＵの再構成画像を利用して、疑似ＤＣ予測画像の画素値を計算することができる。
【０２２０】
図４、図６、及び図２５の動画像符号化装置の構成は一例に過ぎず、動画像符号化装置の用途又は条件に応じて一部の構成要素を省略又は変更してもよい。図８の判定部６１６の構成は一例に過ぎず、動画像符号化装置の用途又は条件に応じて一部の構成要素を省略又は変更してもよい。図１０の選択部８０１の構成は一例に過ぎず、動画像符号化装置の用途又は条件に応じて一部の構成要素を省略又は変更してもよい。
【０２２１】
図５、図７、図９、及び図１８〜図２０に示したフローチャートは一例に過ぎず、動画像符号化装置の構成又は条件に応じて一部の処理を省略又は変更してもよい。動画像符号化装置は、ＨＥＶＣの代わりに別の動画像符号化の標準を採用して、動画像符号化処理を行ってもよく、ＤＣ予測画像の代わりに別の予測画像を用いて、符号化コストを計算してもよい。動画像符号化装置は、ＳＡＴＤに基づくＲＤコストの代わりに別の符号化コストを用いて、イントラ予測符号化におけるＰＵのブロックサイズを決定してもよい。
【０２２２】
図１の四分木分割、図２のＰＵ、及び図３のＲＤコストの評価方法は一例に過ぎず、採用される動画像符号化の標準に応じて、別のブロック分割等を用いてもよい。図１１の４×４のブロックの位置、図１２の上周辺領域及び左周辺領域、図１３の処理対象ブロックの位置、図１４の加算値の個数、図１５の上加算値、図１６の左加算値、及び図１７のアクセス順序は一例に過ぎない。採用される動画像符号化の標準に応じて、別の変数、領域等を用いてもよい。
【０２２３】
図２１〜図２４のシミュレーション結果は一例に過ぎず、シミュレーション結果は、符号化対象動画像に応じて変化する。
【０２２４】
式（１）〜式（４４）は一例に過ぎず、動画像符号化装置の構成又は条件に応じて別の計算式を用いてもよい。
【０２２５】
図４、図６、及び図２５の動画像符号化装置は、ハードウェア回路として実装することもでき、図２６に示すような情報処理装置（コンピュータ）を用いて実装することもできる。
【０２２６】
図２６の情報処理装置は、Central Processing Unit（ＣＰＵ）２６０１、メモリ２６０２、入力装置２６０３、出力装置２６０４、補助記憶装置２６０５、媒体駆動装置２６０６、及びネットワーク接続装置２６０７を含む。これらの構成要素はバス２６０８により互いに接続されている。
【０２２７】
メモリ２６０２は、例えば、Read Only Memory（ＲＯＭ）、Random Access Memory（ＲＡＭ）、フラッシュメモリ等の半導体メモリであり、動画像符号化処理に用いられるプログラム及びデータを記憶する。メモリ２６０２は、図６及び図２５のフレームメモリ６２５として用いることができる。メモリ２６０２は、図１０の変換結果記憶部１００３、ＳＡＴＤ記憶部１００５、左加算値記憶部１００７、上加算値記憶部１００８、オフセット記憶部１０１６、ＲＤコスト記憶部１０１７、及びＰＵサイズ記憶部１０１８として用いることもできる。
【０２２８】
ＣＰＵ２６０１（プロセッサ）は、例えば、メモリ２６０２を利用してプログラムを実行することにより、図４の選択部４１１、決定部４１２、イントラ予測部４１３、及び符号化部４１４として動作する。
【０２２９】
ＣＰＵ２６０１は、メモリ２６０２を利用してプログラムを実行することにより、図６の分割部６１１、レート制御部６１２、差分生成部６１３、変換部６１４、エントロピー符号化部６１５、判定部６１６、及び判定部６１７としても動作する。ＣＰＵ２６０１は、メモリ２６０２を利用してプログラムを実行することにより、スイッチ６１８、動き補償部６１９、動き予測部６２０、イントラ予測部６２１、逆変換部６２２、再構成部６２３、及びループ内フィルタ６２４としても動作する。
【０２３０】
ＣＰＵ２６０１は、メモリ２６０２を利用してプログラムを実行することにより、図８の選択部８０１、輝度モード決定部８０２、色差モード決定部８０３、輝度サイズ決定部８０４、及び色差サイズ決定部８０５としても動作する。
【０２３１】
ＣＰＵ２６０１は、メモリ２６０２を利用してプログラムを実行することにより、図１０の位置決定部１００１、アダマール変換部１００２、ＳＡＴＤ計算部１００４、加算部１００６、及びＤＣ計算部１００９としても動作する。ＣＰＵ２６０１は、メモリ２６０２を利用してプログラムを実行することにより、位置計算部１０１０、管理部１０１１、変換結果積み上げ部１０１２、ＤＣ積み上げ部１０１３、ＳＡＴＤ計算部１０１４、及び比較部１０１５としても動作する。
【０２３２】
入力装置２６０３は、例えば、キーボード、ポインティングデバイス等であり、ユーザ又はオペレータからの指示や情報の入力に用いられる。出力装置２６０４は、例えば、表示装置、プリンタ、スピーカ等であり、ユーザ又はオペレータへの問い合わせ及び処理結果の出力に用いられる。
【０２３３】
補助記憶装置２６０５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク装置、テープ装置等である。補助記憶装置２６０５は、ハードディスクドライブ又はフラッシュメモリであってもよい。情報処理装置は、補助記憶装置２６０５にプログラム及びデータを格納しておき、それらをメモリ２６０２にロードして使用することができる。
【０２３４】
媒体駆動装置２６０６は、可搬型記録媒体２６０９を駆動し、その記録内容にアクセスする。可搬型記録媒体２６０９は、メモリデバイス、フレキシブルディスク、光ディスク、光磁気ディスク等である。可搬型記録媒体２６０９は、Compact Disk Read Only Memory（ＣＤ−ＲＯＭ）、Digital Versatile Disk（ＤＶＤ）、又はUniversal Serial Bus（ＵＳＢ）メモリであってもよい。ユーザ又はオペレータは、この可搬型記録媒体２６０９にプログラム及びデータを格納しておき、それらをメモリ２６０２にロードして使用することができる。
【０２３５】
このように、処理に用いられるプログラム及びデータを格納するコンピュータ読み取り可能な記録媒体には、メモリ２６０２、補助記憶装置２６０５、及び可搬型記録媒体２６０９のような、物理的な（非一時的な）記録媒体が含まれる。
【０２３６】
ネットワーク接続装置２６０７は、Local Area Network（ＬＡＮ）、インターネット等の通信ネットワークに接続され、通信に伴うデータ変換を行う通信インタフェース回路である。ネットワーク接続装置２６０７は、ビットストリームを動画像復号装置へ送信することができる。情報処理装置は、プログラム及びデータを外部の装置からネットワーク接続装置２６０７を介して受け取り、それらをメモリ２６０２にロードして使用することもできる。
【０２３７】
なお、情報処理装置が図２６のすべての構成要素を含む必要はなく、用途又は条件に応じて一部の構成要素を省略することも可能である。例えば、ユーザ又はオペレータとのインタフェースが不要である場合は、入力装置２６０３及び出力装置２６０４を省略してもよい。また、情報処理装置が可搬型記録媒体２６０９にアクセスしない場合は、媒体駆動装置２６０６を省略してもよい。
【０２３８】
開示の実施形態とその利点について詳しく説明したが、当業者は、特許請求の範囲に明確に記載した本発明の範囲から逸脱することなく、様々な変更、追加、省略をすることができるであろう。
【０２３９】
図１乃至図２６を参照しながら説明した実施形態に関し、さらに以下の付記を開示する。
（付記１）
動画像に含まれる符号化対象画像内の符号化対象領域を複数の階層それぞれにおいて再帰的に分割して得られる、異なるブロックサイズの複数のブロックそれぞれについて、ブロックの原画像と所定の予測画像との差分に基づく符号化コストを再帰的に計算し、前記複数のブロックそれぞれの符号化コストを比較して、前記複数の階層のうち１つの階層のブロックサイズを選択する選択部と、
前記選択部が選択したブロックサイズを有する符号化対象ブロックに対するイントラ予測モードを決定する決定部と、
前記決定部が決定したイントラ予測モードに基づいて、前記符号化対象ブロックに対する予測画像を生成するイントラ予測部と、
前記イントラ予測部が生成した予測画像を用いて、前記符号化対象ブロックを符号化する符号化部と、
を備えることを特徴とする動画像符号化装置。
（付記２）
前記所定の予測画像の画素値は、前記複数のブロックのうち処理対象ブロックに隣接する複数の画素の画素値の平均値であり、前記処理対象ブロックの符号化コストは、前記処理対象ブロックの原画像と前記所定の予測画像との差分をアダマール変換によって変換した変換結果の絶対値和を含むことを特徴とする付記１記載の動画像符号化装置。
（付記３）
前記選択部は、前記処理対象ブロック内の前記処理対象ブロックよりも小さなブロックサイズを有するブロックの原画像をアダマール変換によって変換した変換結果を用いて、前記処理対象ブロックの原画像をアダマール変換によって変換した変換結果を計算し、前記処理対象ブロックよりも小さなブロックサイズを有するブロックに隣接する複数の画素の画素値を用いて、前記処理対象ブロックに隣接する複数の画素の画素値の平均値を計算し、前記処理対象ブロックの原画像をアダマール変換によって変換した変換結果と、前記処理対象ブロックに隣接する複数の画素の画素値の平均値とを用いて、前記処理対象ブロックの符号化コストを計算し、前記処理対象ブロックの符号化コストが前記処理対象ブロックよりも小さなブロックサイズを有するブロックの符号化コストよりも小さい場合、前記処理対象ブロックのブロックサイズを選択することを特徴とする付記２記載の動画像符号化装置。
（付記４）
前記処理対象ブロックに隣接する複数の画素は、前記処理対象ブロックの上に隣接する複数の画素と、前記処理対象ブロックの左に隣接する複数の画素とを含むことを特徴とする付記２又は３記載の動画像符号化装置。
（付記５）
動画像符号化装置によって実行される動画像符号化方法であって、
前記動画像符号化装置が、
動画像に含まれる符号化対象画像内の符号化対象領域を複数の階層それぞれにおいて再帰的に分割して得られる、異なるブロックサイズの複数のブロックそれぞれについて、ブロックの原画像と所定の予測画像との差分に基づく符号化コストを再帰的に計算し、
前記複数のブロックそれぞれの符号化コストを比較して、前記複数の階層のうち１つの階層のブロックサイズを選択し、
選択したブロックサイズを有する符号化対象ブロックに対するイントラ予測モードを決定し、
決定したイントラ予測モードに基づいて、前記符号化対象ブロックに対する予測画像を生成し、
生成した予測画像を用いて、前記符号化対象ブロックを符号化する、
ことを特徴とする動画像符号化方法。
（付記６）
前記所定の予測画像の画素値は、前記複数のブロックのうち処理対象ブロックに隣接する複数の画素の画素値の平均値であり、前記処理対象ブロックの符号化コストは、前記処理対象ブロックの原画像と前記所定の予測画像との差分をアダマール変換によって変換した変換結果の絶対値和を含むことを特徴とする付記５記載の動画像符号化方法。
（付記７）
前記動画像符号化装置は、前記処理対象ブロック内の前記処理対象ブロックよりも小さなブロックサイズを有するブロックの原画像をアダマール変換によって変換した変換結果を用いて、前記処理対象ブロックの原画像をアダマール変換によって変換した変換結果を計算し、前記処理対象ブロックよりも小さなブロックサイズを有するブロックに隣接する複数の画素の画素値を用いて、前記処理対象ブロックに隣接する複数の画素の画素値の平均値を計算し、前記処理対象ブロックの原画像をアダマール変換によって変換した変換結果と、前記処理対象ブロックに隣接する複数の画素の画素値の平均値とを用いて、前記処理対象ブロックの符号化コストを計算し、前記処理対象ブロックの符号化コストが前記処理対象ブロックよりも小さなブロックサイズを有するブロックの符号化コストよりも小さい場合、前記処理対象ブロックのブロックサイズを選択することを特徴とする付記６記載の動画像符号化方法。
（付記８）
前記処理対象ブロックに隣接する複数の画素は、前記処理対象ブロックの上に隣接する複数の画素と、前記処理対象ブロックの左に隣接する複数の画素とを含むことを特徴とする付記６又は７記載の動画像符号化方法。
（付記９）
動画像に含まれる符号化対象画像内の符号化対象領域を複数の階層それぞれにおいて再帰的に分割して得られる、異なるブロックサイズの複数のブロックそれぞれについて、ブロックの原画像と所定の予測画像との差分に基づく符号化コストを再帰的に計算し、
前記複数のブロックそれぞれの符号化コストを比較して、前記複数の階層のうち１つの階層のブロックサイズを選択し、
選択したブロックサイズを有する符号化対象ブロックに対するイントラ予測モードを決定し、
決定したイントラ予測モードに基づいて、前記符号化対象ブロックに対する予測画像を生成し、
生成した予測画像を用いて、前記符号化対象ブロックを符号化する、
処理をコンピュータに実行させるための動画像符号化プログラム。
（付記１０）
前記所定の予測画像の画素値は、前記複数のブロックのうち処理対象ブロックに隣接する複数の画素の画素値の平均値であり、前記処理対象ブロックの符号化コストは、前記処理対象ブロックの原画像と前記所定の予測画像との差分をアダマール変換によって変換した変換結果の絶対値和を含むことを特徴とする付記９記載の動画像符号化プログラム。
（付記１１）
前記コンピュータは、前記処理対象ブロック内の前記処理対象ブロックよりも小さなブロックサイズを有するブロックの原画像をアダマール変換によって変換した変換結果を用いて、前記処理対象ブロックの原画像をアダマール変換によって変換した変換結果を計算し、前記処理対象ブロックよりも小さなブロックサイズを有するブロックに隣接する複数の画素の画素値を用いて、前記処理対象ブロックに隣接する複数の画素の画素値の平均値を計算し、前記処理対象ブロックの原画像をアダマール変換によって変換した変換結果と、前記処理対象ブロックに隣接する複数の画素の画素値の平均値とを用いて、前記処理対象ブロックの符号化コストを計算し、前記処理対象ブロックの符号化コストが前記処理対象ブロックよりも小さなブロックサイズを有するブロックの符号化コストよりも小さい場合、前記処理対象ブロックのブロックサイズを選択することを特徴とする付記１０記載の動画像符号化プログラム。
（付記１２）
前記処理対象ブロックに隣接する複数の画素は、前記処理対象ブロックの上に隣接する複数の画素と、前記処理対象ブロックの左に隣接する複数の画素とを含むことを特徴とする付記１０又は１１記載の動画像符号化プログラム。
【符号の説明】
【０２４０】
４０１、６０１、２５０１  動画像符号化装置
４１１、８０１  選択部
４１２  決定部
４１３  イントラ予測部
４１４  符号化部
６１１  分割部
６１２  レート制御部
６１３  差分生成部
６１４  変換部
６１５  エントロピー符号化部
６１６、６１７  判定部
６１８  スイッチ
６１９  動き補償部
６２０  動き予測部
６２１  イントラ予測部
６２２  逆変換部
６２３  再構成部
６２４  ループ内フィルタ
６２５  フレームメモリ
８０２  輝度モード決定部
８０３  色差モード決定部
８０４  輝度サイズ決定部
８０５  色差サイズ決定部
１００１  位置決定部
１００２  アダマール変換部
１００３  変換結果記憶部
１００４、１０１４  ＳＡＴＤ計算部
１００５  ＳＡＴＤ記憶部
１００６  加算部
１００７  左加算値記憶部
１００８  上加算値記憶部
１００９  ＤＣ計算部
１０１０  位置計算部
１０１１  管理部
１０１２  変換結果積み上げ部
１０１３  ＤＣ積み上げ部
１０１５  比較部
１０１６  オフセット記憶部
１０１７  ＲＤコスト記憶部
１０１８  ＰＵサイズ記憶部
１１０１、１２０１  ブロック
１２０２  上周辺領域
１２０３  左周辺領域
１３０１  処理対象ブロック
１５０１、１６０１  領域
２１０１、２１０２、２２０１、２２０２、２３０１、２３０２、２４０１、２４０２  直線
２６０１  ＣＰＵ
２６０２  メモリ
２６０３  入力装置
２６０４  出力装置
２６０５  補助記憶装置
２６０６  媒体駆動装置
２６０７  ネットワーク接続装置
２６０８  バス
２６０９  可搬型記録媒体
【図１】
2019062339.tif 000012
【図２】
2019062339.tif 000013
【図３】
2019062339.tif 000014
【図４】
2019062339.tif 000015
【図５】
2019062339.tif 000016
【図６】
2019062339.tif 000017
【図７】
2019062339.tif 000018
【図８】
2019062339.tif 000019
【図９】
2019062339.tif 000020
【図１０】
2019062339.tif 000021
【図１１】
2019062339.tif 000022
【図１２】
2019062339.tif 000023
【図１３】
2019062339.tif 000024
【図１４】
2019062339.tif 000025
【図１５】
2019062339.tif 000026
【図１６】
2019062339.tif 000027
【図１７】
2019062339.tif 000028
【図１８】
2019062339.tif 000029
【図１９】
2019062339.tif 000030
【図２０】
2019062339.tif 000031
【図２１】
2019062339.tif 000032
【図２２】
2019062339.tif 000033
【図２３】
2019062339.tif 000034
【図２４】
2019062339.tif 000035
【図２５】
2019062339.tif 000036
【図２６】
2019062339.tif 000037