JP6616242B2 - 映像符号化装置、ブロック構造決定方法及びコンピュータプログラム - Google Patents

Description

本発明は、映像符号化装置、ブロック構造決定方法及びコンピュータプログラムに関する。

映像符号化の標準規格としてＨ．２６４／ＡＶＣ（Advanced Video Coding）やＨ．２６５／ＨＥＶＣ（High Efficiency Video Coding）と呼ばれる映像符号化方式が策定されている。ＨＥＶＣは、高い圧縮率を達成する反面、符号化処理の演算量が従来規格と比べて多いことで知られている。その理由の１つとして、画面内の符号化ブロックのバリエーションが増加したことが挙げられる。ＨＥＶＣでは、符号化対象の画像領域をＬＣＵ(Largest Coding Unit：最大符号化単位)と呼ばれる正方形のブロック単位に分割し、更にＬＣＵをＣＵ(Coding Unit)と呼ばれるブロック単位に再帰的に最大３回まで４等分することができる。

ＬＣＵは最大６４×６４画素に設定でき、その場合ＣＵは、６４×６４画素、３２×３２画素、１６×１６画素、８×８画素を設定することができる。ＬＣＵ毎にＣＵ（最大４パターン分）のブロックを組み合わせ、最適なブロック構造を決定することで効率的に圧縮が可能である。しかし、組み合わせ数が膨大となるため全ての組み合わせを行ってしまうと符号化の演算負荷が高くなってしまうという問題がある。よって、少ない演算量で最適なブロック構造を選択する手法が望まれている。

例えば、隣接するブロックの最小ＣＵサイズを用いてブロックサイズの候補を制限する手法が提案されている（例えば、特許文献１参照）。特許文献１に記載の技術（以下、「従来技術１」という）では、隣接するブロックの構造が予め選択されている必要があり、複数のブロックの構造を同時に選択していくような並列処理へは適用し難いという課題がある。この課題を解決する手法として、隣接するブロックを符号化済みフレームから取得する手法が提案されている（例えば、非特許文献１参照）。非特許文献１に記載の技術（以下、「従来技術２」という）では符号化済みフレームの参照ブロックの最大分割深度に基づいて、符号化対象ブロックの最大分割深度を選択する。

特許第５７１９４０１号公報

Guilherme Correa, Pedro Assuncao , Luciano Agostini, Luis A. da Silva Cruz, "Complexity Control of HEVC through Quadtree Depth Estimation", EuroCon 2013, 1-4 July 2013, Zagreb, Croatia, pp. 81-86

ただし、従来技術２では、１箇所でも最大分割のブロックがあると全パターンのブロックを計算することになるため、演算量が削減できないケースが発生する。そのため、従来技術２を、従来技術１などと組み合わせて、図２１に示すような構成とし、ブロックサイズ毎に判定する手法（以下、「従来技術２’」という）も考えられる。しかしながら、時間的参照ブロックは、符号化対象ブロックと相関が必ずしも高いとは限らないため、相関が低い場合に各ブロックサイズを個別に判定すると符号化効率が低下してしまうという問題がある。

本発明は、上記問題を解決すべくなされたもので、その目的は、符号化効率の低下を抑えつつ、ブロック構造決定処理の演算量を削減する映像符号化装置、ブロック構造決定方法及びコンピュータプログラムを提供することにある。

本発明の一態様は、画像を複数の領域に分割し、前記領域を再帰的にブロックに分割することで生成される１つのブロックサイズで構成される若しくは複数のブロックサイズのブロックを組み合わせて構成されるブロック構造を決定するブロック構造決定部と、決定された前記ブロック構造に基づいて符号化を行う符号化部と、を備え、前記ブロック構造決定部は、前記ブロックサイズごとに、前記画像の領域を所定のサイズのブロックに分割するブロック分割部と、分割された前記ブロックのサイズと、前記ブロックが参照する領域の中心が属するブロックのサイズと、が等しい若しくは前記中心が属するブロックのサイズが１段階大きい場合、前記ブロックの各々が、第１の候補ブロックとなると判定する第１候補ブロック判定部と、前記所定のサイズより１段階大きいサイズのブロックを前記所定のサイズに分割して得られたブロック群が前記第１の候補ブロックとして判定されている数が所定の値以上の場合、前記ブロック群に属するすべてのブロックを第２の候補ブロックにすると判定する第２候補ブロック判定部と、前記第２の候補ブロックと判定された前記ブロックについて評価値を算出するブロックサイズ評価値算出部と、前記評価値に基づいて、前記画像の領域を分割する前記ブロックの組み合わせを選択する最終ブロック選択部と、を備える映像符号化装置である。

本発明の一態様は、上記の映像符号化装置であって、前記ブロック分割部は、あらかじめ定められた複数のサイズごとに前記画像を分割し、前記第１候補ブロック判定部と、前記第２候補ブロック判定部は、前記複数のサイズごとに判定を行い、前記画像の所定の領域について、前記第２候補ブロック判定部により重複して前記第２の候補ブロックにすると判定されている場合、前記画像の所定の領域についてのいずれかのブロックを前記第２の候補ブロックから除外する重複領域処理部をさらに備える。

本発明の一態様は、上記の映像符号化装置であって、前記第１候補ブロック判定部は、前記画像に適用される予測モードごとに、分割された前記ブロックと、前記画像の領域に対応する参照ピクチャ内の領域を分割する参照ブロックとに基づいて、前記ブロックの各々が、第１の候補ブロックとなるか否かを判定し、前記第２候補ブロック判定部は、前記所定のサイズより１段階大きいサイズのブロックを前記所定のサイズに分割して得られたブロック群に対して、前記予測モードごとに、前記ブロック群に含まれる前記第１の候補ブロックの割合と、予測モードとブロックサイズとに応じて予め定められる尤度と、に基づいて、前記ブロック群のブロックを全て第２の候補ブロックにするか否かを判定する。

本発明の一態様は、上記の映像符号化装置であって、前記第１候補ブロック判定部は、いずれかの前記予測モードについて、分割された前記ブロックの各々のブロックサイズが、前記参照ブロックのブロックサイズと同一、または、前記参照ブロックのブロックサイズよりも１段階小さいブロックサイズと同一の場合、前記第１の候補ブロックとし、前記予測モード以外の予測モードについて、分割された前記ブロックの各々のブロックサイズが、前記参照ブロックのブロックサイズと同一、または、前記参照ブロックのブロックサイズよりも１段階大きいブロックサイズと同一の場合、前記第１の候補ブロックとして判定する。

本発明の一態様は、上記の映像符号化装置であって、ブロックサイズと前記予測モードの組み合わせごとに異なる尤度が予め定められており、前記第２候補ブロック判定部は、前記ブロック群のブロックサイズと、前記予測モードとに基づいて、前記予測モードごとの前記ブロック群の尤度を算出し、算出した尤度の合計値に基づいて、前記ブロック群のブロックを全て第２の候補ブロックにするか否かを判定する。

本発明の一態様は、上記の映像符号化装置であって、前記第２候補ブロック判定部は、前記ブロック群のブロックを全て第２の候補ブロックにすると判定した場合、前記ブロック群の中で前記第１の候補ブロックでないブロックを前記第２の候補ブロックとして追加する際に、前記ブロックを、複数の予測モードそれぞれにおいて得られる尤度の合計値の中で前記尤度の合計値の大きい前記予測モードに対応する前記第２の候補ブロックとして追加する。

本発明の一態様は、画像の領域をブロックに分割し、前記領域を再帰的にブロックに分割することで生成される１つのブロックサイズで構成される若しくは複数のブロックサイズのブロックを組み合わせて構成されるブロック構造を決定するブロック構造決定ステップと、決定された前記ブロック構造に基づいて符号化を行う符号化ステップと、を有し、前記ブロック構造決定ステップにおいて、前記ブロックサイズごとに、前記画像の領域を所定のサイズのブロックに分割するブロック分割ステップと、分割された前記ブロックのサイズと、前記ブロックが参照する領域の中心が属するブロックのサイズと、が等しい若しくは前記中心が属するブロックのサイズが１段階大きい場合、前記ブロックの各々が、第１の候補ブロックとなると判定する第１候補ブロック判定ステップと、前記所定のサイズより１段階大きいサイズのブロックを前記所定のサイズに分割して得られたブロック群が前記第１の候補ブロックとして判定されている数が所定の値以上の場合、前記ブロック群に属するすべてのブロックを第２の候補ブロックにすると判定する第２候補ブロック判定ステップと、前記第２の候補ブロックと判定された前記ブロックについて評価値を算出するブロックサイズ評価値算出ステップと、前記評価値に基づいて、前記画像の領域を分割する前記ブロックの組み合わせを選択する最終ブロック選択ステップと、を行うブロック構造決定方法である。

本発明の一態様は、画像の領域をブロックに分割し、前記領域を再帰的にブロックに分割することで生成される１つのブロックサイズで構成される若しくは複数のブロックサイズのブロックを組み合わせて構成されるブロック構造を決定するブロック構造決定ステップと、決定された前記ブロック構造に基づいて符号化を行う符号化ステップと、をコンピュータに実行させ、前記ブロック構造決定ステップにおいて、前記ブロックサイズごとに、前記画像の領域を所定のサイズのブロックに分割するブロック分割ステップと、分割された前記ブロックのサイズと、前記ブロックが参照する領域の中心が属するブロックのサイズと、が等しい若しくは前記中心が属するブロックのサイズが１段階大きい場合、前記ブロックの各々が、第１の候補ブロックとなると判定する第１候補ブロック判定ステップと、前記所定のサイズより１段階大きいサイズのブロックを前記所定のサイズに分割して得られたブロック群が前記第１の候補ブロックとして判定されている数が所定の値以上の場合、前記ブロック群に属するすべてのブロックを第２の候補ブロックにすると判定する第２候補ブロック判定ステップと、前記第２の候補ブロックと判定された前記ブロックについて評価値を算出するブロックサイズ評価値算出ステップと、前記評価値に基づいて、前記画像の領域を分割する前記ブロックの組み合わせを選択する最終ブロック選択ステップと、を実行させるためのコンピュータプログラムである。

この発明によれば、符号化効率の低下を抑えつつ、ブロック構造決定処理の演算量を削減することが可能となる。

本発明の第一実施形態における映像符号化装置の構成を示すブロック図である。 第一実施形態におけるブロック構造決定部の構成を示すブロック図である。 第一実施形態における符号化対象ＬＣＵと参照ピクチャ内の参照ブロックの関係を示す図である。 第一実施形態における符号化対象ブロックと参照ブロックの関係を示す図である。 第一実施形態におけるブロック構造決定処理を示すフローチャートである。 第一実施形態における第１候補ブロック判定部による処理を示す図である。 第一実施形態における第２候補ブロック判定部による処理を示す図である。 第一実施形態におけるブロックサイズ評価値算出部と最終ブロック選択部による処理を示す図である。 本発明の第二実施形態におけるブロック構造決定部の構成を示すブロック図である。 第二実施形態におけるブロック構造決定処理を示すフローチャートである。 第二実施形態における重複領域処理部による処理を示す図である。 第二実施形態における第２候補ブロック判定部による処理を示す図である。 第二実施形態におけるブロックサイズ評価値算出部と最終ブロック選択部による処理を示す図である。 本発明の第三実施形態におけるブロック構造決定部の構成を示すブロック図である。 第三実施形態における尤度テーブルの構成を示す図である。 第三実施形態におけるブロック構造決定処理を示すフローチャートである。 第三実施形態における第１候補ブロック判定部による処理を示す図である。 第三実施形態における第２候補ブロック判定部による処理（その１）を示す図である。 第三実施形態における第２候補ブロック判定部による処理（その２）を示す図である。 第三実施形態におけるブロックサイズ評価値算出部と最終ブロック選択部による処理を示す図である。 従来のブロック構造決定部の一例を示す図である。

（第一実施形態）
以下、第一実施形態から順に本発明の実施形態について図面を参照して説明する。図１は、本発明の第一実施形態における映像符号化装置１の構成を示すブロック図である。映像符号化装置１は、ブロック構造決定部１０、減算器１１、直交変換・量子化部１２、可変長符号化部１３、逆量子化・逆直交変換部１４、加算器１５、イントラ予測部１６、イントラ・インター切替スイッチ１７、ループフィルタ部１８、復号ピクチャメモリ部１９及びインター予測部２０を備える。

映像符号化装置１は、符号化対象の映像を構成する符号化対象ピクチャをＬＣＵごとに外部の装置等から受けて、ＬＣＵのブロックに対応する符号化データを他の外部の装置等に出力する。符号化対象ピクチャは、外部の装置等によって、ＬＣＵのサイズ単位でラスタスキャンされて、映像符号化装置１に入力され、ラスタスキャンされた順に映像符号化装置１が繰り返し処理を行うことで、符号化対象ピクチャの符号化が行われる。映像符号化装置１において、ブロック構造決定部１０は、外部の装置等から入力されるＬＣＵのブロック構造を決定、すなわち適切なブロックの組み合わせを選択する。また、ブロック構造決定部１０は、決定したブロック構造にしたがって、ＬＣＵを再帰的にブロックに分割してＣＵを生成し、予め定められる所定の順序で繰り返し、生成したＣＵを減算器１１に出力する。

減算器１１は、ＣＵの画像データから、イントラ予測部１６またはインター予測部２０のいずれかが出力する予測画像データを減算し、減算した差分を直交変換・量子化部１２に出力する。直交変換・量子化部１２は、減算器１１が出力する差分の画像データに対して直交変換と量子化を行って、可変長符号化部１３と、逆量子化・逆直交変換部１４に出力する。可変長符号化部１３は、直交変換・量子化部１２が出力する量子化係数を可変長符号化し、符号化データとして出力する。逆量子化・逆直交変換部１４は、直交変換・量子化部１２が出力する量子化係数に対して逆量子化と逆直交変換を行い、加算器１５に出力する。加算器１５は、逆量子化・逆直交変換部１４が出力する画像データに、イントラ予測部１６またはインター予測部２０のいずれかが出力する予測画像データを加算してイントラ予測部１６と、ループフィルタ部１８とに出力する。

イントラ予測部１６は、加算器１５が出力する、画像データに予測画像データを加算した後の画像データを参照画像データとして、符号化対象ブロックのイントラ予測画像データを生成する。ループフィルタ部１８は、加算器１５が出力する画像データにループフィルタを適用し、フィルタリング後の画像データを復号ピクチャメモリ部１９に出力する。復号ピクチャメモリ部１９は、ループフィルタが適用された画像データを記憶する。インター予測部２０は、復号ピクチャメモリ部１９に記憶されている画像データを参照画像データとし、符号化対象ブロックのインター予測画像を生成する。イントラ・インター切替スイッチ１７は、符号化対象ブロックの予測モードに応じてイントラ予測部１６と、インター予測部２０とを切り替えて、各々の予測モードに対応する予測画像データを減算器１１と加算器１５とに出力する。

図２は、ブロック構造決定部１０の内部構成を示すブロック図である。ブロック構造決定部１０は、ブロック分割部１０１、第１候補ブロック判定部１０２、第２候補ブロック判定部１０３、ブロックサイズ評価値算出部１０４及び最終ブロック選択部１０５を備える。ブロック分割部１０１は、符号化対象ピクチャのＬＣＵを３２×３２画素、１６×１６画素及び８×８画素のブロックに分割する。また、ブロック分割部１０１は、最大ブロックサイズの６４×６４画素のＬＣＵと、３２×３２画素に分割されたＬＣＵと、１６×１６画素に分割されたＬＣＵと、８×８画素に分割されたＬＣＵとを第１候補ブロック判定部１０２に出力する。

第１候補ブロック判定部１０２は、６４×６４ブロック判定部１０２１、３２×３２ブロック判定部１０２２、１６×１６ブロック判定部１０２３及び８×８ブロック判定部１０２４を備える。第１候補ブロック判定部１０２の各々の判定部（すなわち、６４×６４ブロック判定部１０２１、３２×３２ブロック判定部１０２２、１６×１６ブロック判定部１０２３、８×８ブロック判定部１０２４）は、ブロック分割部１０１が出力する各々のブロックサイズに対応するＬＣＵを受ける。すなわち、６４×６４ブロック判定部１０２１は、６４×６４画素のＬＣＵを受け、３２×３２ブロック判定部１０２２は、３２×３２画素に分割されたＬＣＵを受け、１６×１６ブロック判定部１０２３は、１６×１６画素に分割されたＬＣＵを受け、８×８ブロック判定部１０２４は、８×８画素に分割されたＬＣＵを受ける。６４×６４ブロック判定部１０２１、３２×３２ブロック判定部１０２２、１６×１６ブロック判定部１０２３、８×８ブロック判定部１０２４は、ＬＣＵの各ブロックが第１の候補ブロックに該当するか否かを判定する。

ここで、第１候補ブロック判定部１０２の判定部の各々による第１の候補ブロックに該当するか否かの判定は、以下のようにして行われる。６４×６４ブロック判定部１０２１の場合は、１個の符号化対象ブロック、３２×３２ブロック判定部１０２２の場合は、４個の符号化対象ブロック、１６×１６ブロック判定部１０２３の場合は、１６個の符号化対象ブロック、８×８ブロック判定部１０２４の場合は、６４個の符号化対象ブロックが判定の対象となる。これらの符号化対象ブロックの各々について、まず、下記の条件（１）を満たすか否かを判定する。

条件（１）：符号化対象ブロックのブロックサイズが、参照ブロックのブロックサイズと同一または１段階小さいブロックサイズと同一の場合、条件（１）を満たすと判定する。ここで、参照ブロックとは、図３に示すように、ＬＣＵの動きベクトルが指す参照ピクチャにおいて、符号化対象ブロックの中心座標を含むＣＵのことである。例えば、図４において、符号化対象ブロックが６４×６４画素のサイズの場合、中心座標が存在する参照ピクチャにおけるＣＵは、右上の６４×６４画素の参照ブロックとなる。

また、第１候補ブロック判定部１０２の各々の判定部は、判定結果を第２候補ブロック判定部１０３に出力する。第２候補ブロック判定部１０３は、第１候補ブロック判定部１０２が出力する判定結果を受けて、以下の条件（２）を満たすか否かを判定する。

条件（２）：符号化対象ブロックが最大ブロックサイズ（本実施形態では、６４×６４画素）の場合、条件（１）を満たしたブロックは、条件（２）を満たすと判定して第２の候補ブロックとする。最大ブロックサイズではない場合、当該ブロックサイズより１段階大きいブロックサイズのブロックを４分割した領域、例えば、当該ブロックサイズが１６×１６画素の場合、１段階大きい３２×３２画素のいずれかを４分割した４個の１６×１６画素の領域に属するブロック群を選択する。当該ブロック群において、条件（１）を満たすブロックが予め定められる所定個数以上である場合、条件（２）を満たすと判定し、当該ブロック群全てを第２の候補ブロックとする。条件（１）を満たすブロックが所定個数未満である場合、条件（２）を満たさないと判定し、当該ブロック群全てを第２の候補ブロックとしない。ただし、符号化対象ＬＣＵにおいて一度も第２の候補ブロックとなっていない領域は、少なくとも一度は第２の候補ブロックとなるように小さいブロックサイズから優先的に第２の候補ブロックとする。なお、予め定められる所定個数は、ブロックサイズごとに変更してもよく、本実施形態では、３２×３２画素以上のブロックサイズについては「２個」、１６×１６画素以下のブロックサイズについては「３個」とする。

ブロックサイズ評価値算出部１０４は、第２の候補ブロックとなったブロックの評価値（以下、評価コストという）、すなわち、以下の式（１）に基づいて算出するＲＤコストを算出する。

ＲＤコスト＝Ｄ＋λＲ・・・（１）

式（１）において、Ｄは符号化対象ブロックを符号化した場合の誤差を表し、Ｒは符号量を表し、λはラグラジアン定数を表す。また、ブロックサイズ評価値算出部１０４は、予測モードごと、すなわちイントラ予測部１６によるイントラ予測モード、及びインター予測部２０によるインター予測モードの各予測モードに対してＲＤコストを算出し、最小のＲＤコストをブロックの評価コストとする。

最終ブロック選択部１０５は、ブロックサイズ評価値算出部１０４が、算出した評価コストが最小となるブロックの組み合わせをブロック構造として選択する。例えば、最終ブロック選択部１０５は、同一のブロック領域で小さいブロックサイズと大きいブロックサイズを比較する場合、小さいブロックサイズの評価コストの合計と、大きいブロックサイズの評価コストを比較し、評価コストの小さいブロックサイズのブロックをブロック構造を構成するブロックとして選択する。

次に、図５から図８を参照しつつ、第一実施形態の映像符号化装置１のブロック構造決定部１０によるブロック構造決定処理について説明する。図５は、ブロック構造決定処理の流れを示すフローチャートである。映像符号化装置１のブロック構造決定部１０のブロック分割部１０１は、外部の装置等から受けた符号化対象ピクチャのＬＣＵを３２×３２画素、１６×１６画素、８×８画素のブロックサイズに分割する。ブロック分割部１０１は、最大ブロックサイズの６４×６４画素のＬＣＵと、３２×３２画素に分割されたＬＣＵと、１６×１６画素に分割されたＬＣＵと、８×８画素に分割されたＬＣＵとを第１候補ブロック判定部１０２の対応する判定部に出力する（ステップＳａ１）。

第１候補ブロック判定部１０２は、符号化対象ブロックが条件（１）を満たす第１の候補ブロックになるか否かを判定し、第１の候補ブロックを選択する処理を行う（ステップＳａ２）。ステップＳａ２の処理は、例えば、６４×６４ブロック判定部１０２１、３２×３２ブロック判定部１０２２、１６×１６ブロック判定部１０２３、８×８ブロック判定部１０２４の順に、各々の判定部によって、各々に対応するブロックサイズのＬＣＵに対して行われる（ループＬａ１）。また、第１候補ブロック判定部１０２の各々の判定部は、符号化対象ブロックに含まれるブロックの各々について繰り返しステップＳａ２の処理を行う（ループＬａ２）。例えば、８×８ブロック判定部１０２４の場合、６４個のブロックの各々に対してステップＳａ２を６４回繰り返して行う。第１候補ブロック判定部１０２の各々の判定部によって、符号化対象ブロックに含まれるブロックの各々についてステップＳａ２の処理が行なわれると、ループＬａ２が終了する（ループＬａ３）。また、第１候補ブロック判定部１０２の各々の判定部によって、各々に対応するブロックサイズのＬＣＵに対してステップＳａ２の処理が行われると、ループＬａ１が終了する（ループＬａ４）。

図６は、第１候補ブロック判定部１０２によるステップＳａ２の処理の例を示す図である。図６において「○」が条件（１）を満たすブロックであり、「×」が条件（１）を満たさないブロックであることを示す。例えば、符号化対象ＬＣＵの各ブロックと、参照ブロックとの関係が図４に示す関係である場合、６４×６４ブロック判定部１０２１は、ブロック分割部１０１が出力する６４×６４画素のＬＣＵを受けて、６４×６４画素のブロックの中心座標が、参照ピクチャのどの参照ブロックに存在しているかを判定する。６４×６４画素の中心座標は、参照ピクチャの右上の６４×６４画素の参照ブロックに存在し、当該参照ブロックと同一のブロックサイズとなるため、条件（１）を満たすことになる。したがって、６４×６４ブロック判定部１０２１は、図６（ａ）に示すように「○」、すなわち第１の候補ブロックという判定結果を出力する。

３２×３２ブロック判定部１０２２は、ブロック分割部１０１から、３２×３２画素に分割されたＬＣＵを受けて、３２×３２画素の４個のブロックの各々の中心座標が、参照ピクチャのどの参照ブロックに存在しているかを判定する。右上のブロックは、参照ピクチャの６４×６４画素の参照ブロックに存在し、当該参照ブロックのブロックサイズよりも１段階低いブロックサイズのブロックに該当する。そのため、右上のブロックは、条件（１）を満たすことになる。同様に、左上のブロックは、参照ピクチャの３２×３２画素のブロックに存在するため、参照ブロックのブロックサイズと同一のブロックサイズのブロックに該当するため条件（１）を満たすことになる。これに対して、右下と、左下のブロックは、参照ピクチャの１６×１６画素のブロックに存在するため、条件（１）を満たさないことになる。したがって、３２×３２ブロック判定部１０２２は、図６（ｂ）に示すように右上と左上のブロックが「○」、すなわち第１の候補ブロックに該当し、右下と左下のブロックが「×」、すなわち第１の候補ブロックに該当しない判定結果を出力する。

同様にして１６×１６ブロック判定部１０２３は、ブロック分割部１０１から、１６×１６画素に分割されたＬＣＵを受けて、１６×１６画素の１６個のブロックの中心座標が、参照ピクチャのどの参照ブロックに存在しているかを判定する。中心座標が１６×１６画素のブロック、または３２×３２画素の参照ブロックに存在する場合、条件（１）を満たし、６４×６４画素の参照ブロックに存在する場合、条件（１）を満たさないため、１６×１６ブロック判定部１０２３は、図６（ｃ）に示すような判定結果を出力する。８×８ブロック判定部１０２４は、８×８画素については、全て条件（１）を満たさないため、図６（ｄ）に示す「×」、すなわち全てが、第１の候補ブロックに該当しない判定結果を出力する。

図５に戻り、第２候補ブロック判定部１０３は、第１候補ブロック判定部１０２の各々の判定部による判定結果を受けて、符号化対象ブロックが条件（２）を満たすか否かを判定する（ステップＳａ３）。図７は、第２候補ブロック判定部１０３による判定の結果を示す図であり、図７において「☆」は、第２の候補ブロックとして判定されたブロックを示している。図７において、「†」の意味は、図６において、第１の候補ブロックとなっていなかったブロックが第２の候補ブロックにした場合、または、第１の候補ブロックとなっていたブロックが第２の候補ブロックにしなかった場合を示す記号である。

図６の第１の候補ブロックの判定結果を受けて、６４×６４画素のＬＣＵについては、第２候補ブロック判定部１０３は、最大ブロックサイズに該当し、更に、６４×６４画素のＬＣＵは、第１の候補ブロックにも該当しているため、条件（２）を満たすと判定する。したがって、第２候補ブロック判定部１０３は、図７（ａ）に示すように「☆」、すなわち第２の候補ブロックに該当する判定結果を出力する。

３２×３２画素に分割されたＬＣＵについては、第２候補ブロック判定部１０３は、最大ブロッサイズではないため、再帰的に４分割された領域に属する各々ブロックの中で第１の候補ブロックとなっているブロックの数を検出する。図６（ｂ）に示すように、３２×３２画素のＬＣＵについては、第１の候補ブロックは、２個存在するため、第２候補ブロック判定部１０３は、個数を「２」として検出する。３２×３２画素については、予め定められる所定個数が「２」となっているため、第２候補ブロック判定部１０３は、３２×３２画素に分割されたＬＣＵについては、条件（２）を満たすと判定し、当該４分割の領域に存在するブロックを全て第２の候補ブロックとする判定結果を出力する。したがって、第２候補ブロック判定部１０３は、図７（ｂ）に示すように、３２×３２画素のＬＣＵの全てのブロックが「☆」、すなわち第２の候補ブロックに該当する判定結果を出力する。

１６×１６画素に分割されたＬＣＵについては、第２候補ブロック判定部１０３は、最大ブロッサイズではないため、３２×３２画素のブロックから更に再帰的に４分割された領域に属する各々ブロックについて、第１の候補ブロックとなっているブロックの数を検出する。図６（ｃ）に示すように、１６×１６画素のＬＣＵにおいて、左下の４分割されたブロックには、第１の候補ブロックが３個存在するため、第２候補ブロック判定部１０３は、個数を「３」として検出する。また、右下の４分割されたブロックには、第１の候補ブロックが２個存在するため、第２候補ブロック判定部１０３は、個数を「２」として検出する。また、左上の４分割されたブロックには、第１の候補ブロックが２個存在するため、第２候補ブロック判定部１０３は、個数を「２」として検出する。右上の４分割されたブロックには、第１の候補ブロックは存在しないため、第２候補ブロック判定部１０３は、個数を「０」として検出する。１６×１６画素のブロックについては、予め定められる所定数が「３」となっているため、第２候補ブロック判定部１０３は、左下の４分割された領域については、条件（２）を満たし、それ以外については、条件（２）を満たさないと判定する。したがって、第２候補ブロック判定部１０３は、条件（２）を満たす左下の４分割された領域に属するブロックについては、「☆」、すなわち第２の候補ブロックに該当し、それ以外のブロックについては、「×」、すなわち第２の候補ブロックに該当しない判定結果を出力する。

第２候補ブロック判定部１０３は、８×８の画素に分割されたＬＣＵについては、第１の候補ブロックとなっているブロックが存在しないため、全てが条件（２）を満たさないと判定する。

次に、ブロックサイズ評価値算出部１０４は、第２の候補ブロックとなった各ブロックについて、予測モードごとに、評価コスト、すなわちＲＤコストを上記の式（１）に基づいて算出する（ステップＳａ４）。図８（ａ）に示す各ブロック内の数値が、ブロックサイズ評価値算出部１０４が算出した評価コストの値である。最終ブロック選択部１０５は、ブロックサイズ評価値算出部１０４が算出した評価コストが最小となる組み合わせをブロック構造を構成するブロックとして選択する（ステップＳａ５）。図８（ａ）に示すように、まず、最終ブロック選択部１０５は、３２×３２画素の左下のブロックの評価コストである「３０」と、１６×１６画素の左下の４分割の領域の評価コストの合計である「２５＝１０＋５＋５＋５」とを比較する。１６×１６画素の４分割の領域の評価コストの合計の方が小さいので、最終ブロック選択部１０５は、１６×１６画素に分割されたブロックを選択する。

次に、最終ブロック選択部１０５は、６４×６４画素の評価コストである「１００」と、３２×３２画素の４分割の領域の各ブロックの評価コストの合計とを比較する。この際、３２×３２画素の左下のブロックの評価コストは、１６×１６画素の左下の４分割の領域の評価コストの合計である「２５＝１０＋５＋５＋５」が用いられる。すなわち、最終ブロック選択部１０５は、６４×６４画素の評価コストである「１００」と、３２×３２画素の４分割の領域の各ブロックの評価コストの合計である「８５＝２５＋２５＋２０＋１５」とを比較する。３２×３２画素の４分割の領域の評価コストの合計の方が小さいので、最終ブロック選択部１０５は、３２×３２画素に分割されたブロックを選択する。この際、最終ブロック選択部１０５は、３２×３２画素に分割されたブロックの左下のブロックにおいては１６×１６画素に分割されたブロックを選択する。選択したブロックに基づいて、最終ブロック選択部１０５は、図８（ｂ）に示すブロック構造を出力する。

上記の第一実施形態の構成により、第１候補ブロック判定部１０２は、６４×６４画素のＬＣＵ、３２×３２画素に分割されたＬＣＵ、１６×１６画素に分割されたＬＣＵ、８×８画素に分割されたＬＣＵの各ブロックのブロックサイズと、対応する参照ブロックのブロックサイズとに基づいて、第１の候補ブロックに該当するか否かを判定する。第２候補ブロック判定部１０３は、１段階ブロックサイズが大きいブロックから４分割された４個のブロックに占める第１の候補ブロックの個数に基づいて、各ブロックが、第２の候補ブロックに該当するか否かを判定する。ブロックサイズ評価値算出部１０４は、第２の候補ブロックの評価コストを算出し、最終ブロック選択部１０５は、評価コストが最小となるブロックの組み合わせをブロック構造を構成するブロックとして選択する。これにより、符号化効率の低下を抑えつつ、ブロック構造決定処理の演算量を削減することが可能となる。

上述した従来技術２を図４の例に適用した場合、６４×６４画素のＬＣＵ、３２×３２画素に分割されたＬＣＵ、１６×１６画素に分割されたＬＣＵの全てのブロックが候補となるため、演算量の削減効果がほとんど得られない。これに対して、本発明の第一実施形態の構成では１６×１６画素に分割されたＬＣＵについては左下のブロック群のみを候補とするので、演算量を削減することができる。

また、上述した従来技術２’を同様に図４の例に適用した場合、仮に３２×３２画素に分割されたＬＣＵの左右下の２個のブロックにおいて参照ブロックとの相関が低い場合、従来技術２’では左右下の２個のブロックは候補とならない。そのため、従来技術２’では、この２個のブロックを候補から除外してしまうことで符号化効率を低下させてしまうことになる。これに対し、本発明の第一実施形態の構成では、図２１に示す従来技術２’のブロック構造決定部１０００には備えられていない第２候補ブロック判定部１０３を備えている。そのため、第１候補ブロック判定部１０２により各ブロックで判定した後、更に、第２候補ブロック判定部１０３により再度周囲のブロック（図６（ｂ）に示す左右の上２個のブロック）を考慮して左右の下２個のブロックを候補に加えるため、符号化効率の低下を抑えることができる。

＜変形例＞
なお、上記の第一実施形態において、条件（１）に示した条件は、符号化対象ブロックのブロックサイズが、参照ブロックのブロックサイズと同一のサイズになる確率が高いという特徴を利用した条件である。しかしながら、本発明の構成は当該実施の形態に限られず、条件（１）は、上記した条件には限られず、従来技術１に示されている条件や、その他の条件を用いてもよい。
また、条件（２）は、１段階大きいブロックサイズから４分割された４個のブロック群間にブロックサイズの相関があるという特徴を利用した条件である。しかしながら、本発明の構成は当該実施の形態に限られない。条件（２）は、上記した条件に限られず、符号化対象ブロックの周囲の複数のブロックを判定に用いるようにしてもよいし、最大ブロックサイズである６４×６４画素のＬＣＵにおいても当該ＬＣＵの周囲のブロックを判定に用いるようにしてもよい。

（第二実施形態）
図９は、本発明の第二実施形態におけるブロック構造決定部１０ａの構成を示すブロック図である。第一実施形態における映像符号化装置１は、ブロック構造決定部１０を備えている。これに対して、第二実施形態では、当該ブロック構造決定部１０がブロック構造決定部１０ａに置き換えられる構成となる。図９において、第一実施形態と同一の構成については、同一の符号を付し、以下、異なる構成について説明する。ブロック構造決定部１０ａは、第２候補ブロック判定部１０３と、ブロックサイズ評価値算出部１０４との間に、重複領域処理部１０６を備える。

重複領域処理部１０６は、第２候補ブロック判定部１０３によって、第２の候補ブロックであると判定されたブロックの重複領域を検出し、予め定められている所定回数以上重複しているブロックについては、以下の条件（３）を満たすように第２の候補ブロックから除外する。除外された第２の候補ブロックについては、ブロックサイズ評価値算出部１０４の評価コストの算出対象に含まれない。

条件（３）：重複回数が所定回数以上の領域について、条件（１）を満たすブロックの占める割合が最大となるように、第２の候補ブロックから除外する。ただし、占める割合が同じになった場合、小さいブロックサイズを優先的に除外する。なお、本実施形態では、予め定められる所定回数を「２」とする。

図１０は、第二実施形態におけるブロック構造決定処理の流れを示すフローチャートである。ステップＳｂ１からＳｂ３までの処理は、第一実施形態におけるブロック構造決定処理のステップＳａ１からＳａ３までの処理と同じ処理が行われる。ステップＳｂ３までの処理により、第２候補ブロック判定部１０３によって、図７に示す判定結果が得られる。重複領域処理部１０６は、第２候補ブロック判定部１０３からの判定結果の出力を受けて、各ブロックでの重複回数を検出する。図１１（ａ）は、例えば、３２×３２画素に分割された領域の各ブロックにおける重複回数を重複領域処理部１０６が検出した例であり、左右の上のブロックと、右下のブロックについては、６４×６４画素のブロックの領域のみが重複するため重複回数として「１」を検出する。左下のブロックについては、６４×６４画素のブロックの領域に加えて、１６×１６画素に分割されたブロックの領域も重複するため重複回数として「２」を検出する。

２回以上重複している左下の領域は、条件（３）の重複回数が所定回数以上の領域に該当するため、図７（ｂ）に示すように除外対象領域となる。重複領域処理部１０６は、当該左下の領域について、第１の候補ブロックの占める割合を検出する。６４×６４画素のブロックにおいて、当該領域における第１の候補ブロックの占める割合は、１００％である。１６×１６画素のブロックにおいて、当該領域における第１の候補ブロックの占める割合は、７５％である。これに対して、３２×３２画素のブロックにおいて、当該領域における第１の候補ブロックの占める割合は、０％である。したがって、割合が低い３２×３２画素の左下のブロックを除外する。図１２は、重複領域処理部１０６による処理が行われた後の各ブロックの判定結果を示す図であり、図１２において「☆」は第２の候補ブロックとして選択されたブロックを示し、「△」は、除外されたブロックを示す。

ブロックサイズ評価値算出部１０４は、第２の候補ブロックから除外されたブロックを除く、第２の候補ブロックとなった各ブロックについて、予測モードごとに、評価コスト、すなわちＲＤコストを上記の式（１）に基づいて算出する（ステップＳｂ４）。図１３（ａ）に示す各ブロック内の数値が、ブロックサイズ評価値算出部１０４が算出した評価コストの値である。最終ブロック選択部１０５は、ブロックサイズ評価値算出部１０４が算出した評価コストが最小となる組み合わせをブロック構造を構成するブロックとして選択する（ステップＳｂ５）。

３２×３２画素に分割されたブロックの左下の領域については、重複領域処理部１０６によって除外されている。そのため、最終ブロック選択部１０５は、当該領域に、１６×１６画素に分割されたブロックの左下の４つの領域の評価コストを適用し、評価コストの合計値を「８５＝２５＋２０＋１５＋１０＋５＋５＋５」として算出する。これに対して、６４×６４画素のブロックの評価コストは「１００」である。したがって、最終ブロック選択部１０５は、図１３（ｂ）に示すような組み合わせ、すなわち左右の上と右下は、３２×３２画素に分割されたブロックであり、左下は、３２×３２画素に分割されたブロックを再帰的に分割した４つの１６×１６画素のブロックである組み合わせを選択する。この組み合わせが、評価コストが最小となるブロック構造を構成するブロックの組み合わせとなる。

上記の第二実施形態の構成では、第一実施形態の構成に加えて、第２候補ブロック判定部１０３と、ブロックサイズ評価値算出部１０４の間に重複領域処理部１０６を備えたことにより、重複領域処理部１０６が、第２の候補ブロックとして判定されたブロックが符号化対象ＬＣＵの同一の領域で予め定められる回数以上重複している場合、重複しているいずれかのブロックを除外する構成とした。これにより、符号化効率の低下を抑え、ブロック構造決定処理の演算量を削減しつつ、ブロックサイズ評価値算出部１０４による、評価コストの演算量が削減され、演算速度を高めることが可能となる。
上記の第二実施形態の例では、最終ブロック選択部１０５が出力するブロック構造は第一実施形態と同じであるが、３２×３２画素に分割されたＬＣＵの１ブロック分の評価コストの演算量が削減されており、当該演算量の削減により演算速度も速くなっている。
また、重複領域処理部１０６は、第１の候補ブロックの占める割合が最大となるようにすることで、候補として尤もらしいブロックを候補として残すことを可能としている。

なお、上記の第二実施形態では、条件（３）として、重複回数を判定の基準としているが、重複の回数ではなく、符号化対象ＬＣＵにおける、重複領域面積や重複領域の占める割合などを用いてもよい。
また、第二実施形態の構成では、重複回数の判定に用いられる予め定められる所定回数の値によって演算量を変えることができており、図４の例では、所定回数を「２」に設定した場合、面積比で２／４＝５０％の演算量削減効果を得ることができる。例えば、６４×６４から８×８までの全ブロックが第２の候補ブロックとなった場合について考える。この場合、所定回数を２に設定すると、２ＬＣＵ分の面積のブロックが除外される。すなわち、４ＬＣＵから２ＬＣＵになっているため、評価コストを計算する必要のあるブロックが５０％削減されていることになる。その結果、最大でも全体の５０％（２ＬＣＵ分）だけしか計算しなくても良くなる。また、重複の回数ではなく、符号化対象ＬＣＵにおける、重複領域面積や重複領域の占める割合などを用いれば、より精度の高い演算量の変更を行うことが可能となる。

（第三実施形態）
次に、本発明の第三実施形態について説明する。図１４は、本発明の第三実施形態におけるブロック構造決定部１０ｂの構成を示すブロック図である。第一実施形態における映像符号化装置１は、ブロック構造決定部１０を備えている。これに対して、第三実施形態では、当該ブロック構造決定部１０がブロック構造決定部１０ｂに置き換えられる構成となる。図１４において、第一実施形態と同一の構成については、同一の符号を付し、以下、異なる構成について説明する。ブロック構造決定部１０ｂは、第１候補ブロック判定部１０２ｂ、第２候補ブロック判定部１０３ｂを備える。第１候補ブロック判定部１０２ｂは、６４×６４ブロック判定部１０２１ｂ、３２×３２ブロック判定部１０２２ｂ、１６×１６ブロック判定部１０２３ｂ、８×８ブロック判定部１０２４ｂを備える。第１候補ブロック判定部１０２ｂは、ブロック分割部１０１が出力する各々のブロックサイズに対応するＬＣＵに基づいて、予測モードごとに、各ブロックが第１の候補ブロックに該当するか否かを判定する。本実施形態では、予測モードとして、イントラ予測モードとインター予測モードとが適用される。

第１候補ブロック判定部１０２の判定部の各々（すなわち、６４×６４ブロック判定部１０２１ｂ、３２×３２ブロック判定部１０２２ｂ、１６×１６ブロック判定部１０２３ｂ、８×８ブロック判定部１０２４ｂ）による第１の候補ブロックに該当するか否かの判定は、以下のようにして行われる。６４×６４ブロック判定部１０２１ｂの場合は、１個の符号化対象ブロック、３２×３２ブロック判定部１０２２ｂの場合は、４個の符号化対象ブロック、１６×１６ブロック判定部１０２３ｂの場合は、１６個の符号化対象ブロック、８×８ブロック判定部１０２４ｂの場合は、６４個の符号化対象ブロックが判定の対象となる。これらの符号化対象ブロックの各々について、予測モードごとに、下記の条件（４）を満たすか否かを判定する。

条件（４）：予測モードが、イントラ予測モードである場合、符号化対象ブロックのブロックサイズが、参照ブロックのブロックサイズと同一、または参照ブロックのブロックサイズよりも１段階小さいサイズと同一の場合、当該符号化対象ブロックをイントラ予測モードにおける第１の候補ブロックとする。予測モードが、インター予測モードである場合、符号化対象ブロックのブロックサイズが参照ブロックのブロックサイズと同一、または参照ブロックのブロックサイズよりも１段階大きいサイズと同一の場合、当該符号化対象ブロックをインター予測モードにおける第１の候補ブロックとする。

また、第１候補ブロック判定部１０２ｂの各々の判定部は、判定結果を第２候補ブロック判定部１０３ｂに出力する。第２候補ブロック判定部１０３ｂは、第１候補ブロック判定部１０２ｂが出力する判定結果を受けて、以下の条件（５）を満たすか否かを判定する。

条件（５）：符号化対象ブロックが、最大ブロックサイズ（本実施形態では、６４×６４画素）の場合、条件（４）を満たした、予測モードとブロックの組を、条件（５）を満たすと判定して第２の候補ブロックとする。最大ブロックサイズではない場合、１段階大きいブロックサイズのブロックを４分割した領域に属するブロック群について、第２候補ブロック判定部１０３ｂが内部の記憶領域に予め記憶する図１５に示す尤度テーブルに基づいて、尤度の合計を算出する。算出した尤度の合計値が、予め定められる所定の尤度閾値以上の場合、該当する予測モードとブロック群の組み合わせを、条件（５）を満たすと判定し、当該ブロック群に含まれるブロックの全てを当該予測モードにおける第２の候補ブロックとする。このとき、複数の予測モードにおいて、算出した尤度の合計値が、予め定められる所定の尤度閾値以上となった場合、予測モードごとの尤度の合計値において、最も大きい合計値の予測モードに対応するブロック群を第２の候補ブロックとする。算出した尤度の合計値が、予め定められる所定の尤度閾値以上でない場合、条件（５）を満たさないと判定し、ブロック群全てを第２の候補ブロックとしない。ただし、符号化対象ＬＣＵ内で一度も第２の候補ブロックとなっていない領域は少なくとも一度は第２の候補ブロックとなるように小さいブロックサイズで、かつ尤度合計が最も大きい予測モードを優先的に第２の候補ブロックとする。本実施形態では、予め定められる所定の尤度閾値の値を「６」としている。

次に、図１６から図２０を参照しつつ、第三実施形態におけるブロック構造決定処理について説明する。図１６は、ブロック構造決定処理の流れを示すフローチャートである。映像符号化装置１のブロック構造決定部１０のブロック分割部１０１は、外部の装置等から受けた符号化対象ピクチャのＬＣＵを３２×３２画素、１６×１６画素、８×８画素のブロックサイズに分割する。ブロック分割部１０１は、最大ブロックサイズの６４×６４画素のＬＣＵと、３２×３２画素に分割されたＬＣＵと、１６×１６画素に分割されたＬＣＵと、８×８画素に分割されたＬＣＵとを第１候補ブロック判定部１０２ｂの対応する判定部に出力する（ステップＳｃ１）。

第１候補ブロック判定部１０２ｂは、符号化対象ブロックが条件（４）を満たす第１の候補ブロックになるか否かを判定し、第１の候補ブロックを選択する処理を行う（ステップＳｃ２）。ステップＳｃ２の処理は、例えば、６４×６４ブロック判定部１０２１ｂ、３２×３２ブロック判定部１０２２ｂ、１６×１６ブロック判定部１０２３ｂ、８×８ブロック判定部１０２４ｂの順に、各々の判定部によって、各々に対応するブロックサイズのＬＣＵに対して行われる（ループＬｃ１）。また、第１候補ブロック判定部１０２の各々の判定部は、符号化対象ＬＣＵに含まれるブロックの各々について繰り返しステップＳｃ２の処理を行う（ループＬｃ２）。例えば、８×８ブロック判定部１０２４ｂの場合、６４個のブロックの各々に対してステップＳａ２を６４回繰り返して行う。また、第１候補ブロック判定部１０２ｂの各々の判定部は、予測モードごと、すなわち本実施形態ではイントラ予測モードとインター予測モードについて、ステップＳｃ２の処理を行う（ループＬｃ３）。第１候補ブロック判定部１０２ｂの各々の判定部によって、予測モードごとについてステップＳｃ２の処理が行なわれると、ループＬｃ３が終了する（ループＬｃ４）。また、第１候補ブロック判定部１０２ｂの各々の判定部によって、符号化対象ＬＣＵに含まれるブロックの各々についてステップＳｃ２の処理が行なわれると、ループＬｃ２が終了する（ループＬｃ５）。また、第１候補ブロック判定部１０２ｂの各々の判定部によって、各々に対応するブロックサイズのＬＣＵに対してステップＳｃ２の処理が行われると、ループＬｃ１が終了する（ループＬｃ６）。

図１７は、第１候補ブロック判定部１０２ｂによる判定結果を示す図である。図１７において、「○」は、条件（４）を満たしていることを示しており、「×」は、条件（４）を満たしていないことを示す。６４×６４画素のブロックについては、最大ブロックサイズであるため、予測モードに関わらず、条件（４）を満たすことになるため、図１７（ａ）に示すように、第１の候補ブロックとなる。３２×３２画素に分割されたＬＣＵについては、イントラ予測モードについては、第一実施形態と同じ結果となり、左右上のブロックが、第１の候補ブロックとなり、左右下のブロックは、第１の候補ブロックとはならない。これに対して、インター予測モードについては、右上のブロックに重なる参照ブロックのサイズが６４×６４画素であるため、条件（４）を満たさない。左上のブロックは、参照ブロックと同じブロックサイズであり、左右の下のブロックは、参照ブロックが１６×１６画素であるため、条件（４）を満たすことから、第１の候補ブロックとなる。したがって、第１候補ブロック判定部１０２ｂによる３２×３２画素に分割されたＬＣＵの判定結果は、図１７（ｂ）のようになる。

１６×１６画素に分割されたＬＣＵについても、イントラ予測モードについては、第一実施形態と同じブロックが、第１の候補ブロックとなる。これに対して、インター予測モードについては、ＬＣＵの４行目の４個のブロックの中心座標が、いずれも１６×１６画素のブロック、または３２×３２画素のブロックに存在するため、条件（４）を満たし、第１の候補ブロックとなる。したがって、第１候補ブロック判定部１０２ｂによる１６×１６画素に分割されたＬＣＵの判定結果は、図１７（ｃ）のようになる。８×８画素については、全て条件（４）を満たさないと判定される。

次に、第２候補ブロック判定部１０３ｂは、第１候補ブロック判定部１０２ｂが出力する判定結果を受けて、条件（５）に基づいて第２の候補ブロックの判定を行う（ステップＳｃ３）。第２候補ブロック判定部１０３ｂは、３２×３２画素に４分割されたＬＣＵの４個の領域の尤度の合計値と、３２×３２画素の各ブロックが更に４分割された１６×１６画素の４個の領域の尤度の合計値とを、予測モードごとに、図１５に示す尤度テーブルを用いて算出する。図１８は、第２候補ブロック判定部１０３ｂによる尤度の合計値の算出結果である。３２×３２画素のＬＣＵについては、尤度の合計値が「１１」となる。１６×１６画素の左上の４個の領域の尤度の合計値は、「６」となり、１６×１６画素の左下の４個の領域の尤度の合計値は、「１３」となり、１６×１６画素の右下の４個の領域の尤度の合計値は、「１０」となる。

第２候補ブロック判定部１０３ｂは、尤度の合計値が、予め定められる尤度閾値、すなわち「７」以上であるか否かに基づいて、第２の候補ブロックに該当するか否かを判定する。図１９（ｂ）に示すように、３２×３２画素に分割されたＬＣＵは、尤度の合計値が、「１１」であるため、第２候補ブロック判定部１０３ｂは、条件（５）を満たすと判定する。図１９（ｂ）に示すように第２候補ブロック判定部１０３ｂは、イントラ予測モードについては、尤度の合計値が「２」であり、インター予測モードについては、尤度の合計値が「９」である。尤度の合計値の大きいのは、インター予測モードであるため、第２候補ブロック判定部１０３ｂは、インター予測モードにおいて「×」となっている右上のブロックを第２の候補ブロックとする。

図１９（ｃ）に示すように、１６×１６画素に分割されたＬＣＵの左上の４個のブロックについては、尤度の合計値が「６」であるため、第２候補ブロック判定部１０３ｂは、４個のブロック全てを第２の候補ブロックにはしない。

左下の４個のブロックについては、イントラ予測モードの尤度の合計値が「９」であり、インター予測モードの尤度の合計値が「４」であるため、全体としての尤度の合計値は「１３」であり、尤度閾値以上となっている。尤度の合計値が大きいのは、イントラ予測モードの方であるため、第２候補ブロック判定部１０３ｂは、イントラ予測モードのブロックについて、「×」となっている右上のブロックを第２の候補ブロックとする。

右下の４個のブロックについては、イントラ予測モードの尤度の合計値が「６」であり、インター予測モードの尤度の合計値が「４」であり、全体としての尤度の合計値は「１０」であり、尤度閾値以上となっている。尤度の合計値が大きいのは、イントラ予測モードの方であるため、第２候補ブロック判定部１０３ｂは、イントラ予測モードのブロックについて、「×」となっている左右上のブロックを第２の候補ブロックとする。最終的に、第２候補ブロック判定部１０３ｂによって、図１９（ｃ）に同一、示すように、第２の候補ブロックが選択される。

ブロックサイズ評価値算出部１０４は、第２の候補ブロックとなった各ブロックについて、予測モードごとに、評価コスト、すなわちＲＤコストを上記の式（１）に基づいて算出する（ステップＳｃ４）。図２０（ａ）に示す各ブロック内の数値が、ブロックサイズ評価値算出部１０４が算出した評価コストの値である。最終ブロック選択部１０５は、ブロックサイズ評価値算出部１０４が算出した評価コストが最小となる組み合わせをブロック構造を構成するブロックとして選択する（ステップＳｃ５）。

図２０（ａ）に示すように、まず、最終ブロック選択部１０５は、３２×３２画素の左下のブロックの評価コストである「３０」と、１６×１６画素の左下の４分割の領域の評価コストの合計である「２５＝１０＋５＋５＋５」とを比較する。１６×１６画素の左下の４分割の領域の評価コストの合計の方が小さいので、最終ブロック選択部１０５は、１６×１６画素に分割されたブロックを選択する。また、最終ブロック選択部１０５は、３２×３２画素の右下のブロックの評価コストである「１５」と、１６×１６画素の右下の４分割の領域の評価コストの合計である「１４＝５＋３＋３＋３」とを比較する。１６×１６画素の左下の４分割の領域の評価コストの合計の方が小さいので、最終ブロック選択部１０５は、１６×１６画素に分割されたブロックを選択する。

次に、最終ブロック選択部１０５は、６４×６４画素の評価コストである「１００」と、３２×３２画素の４分割の領域の各ブロックの評価コストの合計とを比較する。この際、３２×３２画素の左下のブロックの評価コストは、１６×１６画素の左下の４分割の領域の評価コストの合計である「２５＝１０＋５＋５＋５」が用いられる。また、３２×３２画素の右下のブロックの評価コストは、１６×１６画素の右下の４分割の領域の評価コストの合計である「１４＝５＋３＋３＋３」が用いられる。すなわち、最終ブロック選択部１０５は、６４×６４画素の評価コストである「１００」と、３２×３２画素の４分割の領域の各ブロックの評価コストの合計である「８４＝２５＋２０＋２５＋１４」とを比較する。

３２×３２画素の４分割の領域の評価コストの合計の方が小さいので、最終ブロック選択部１０５は、３２×３２画素に分割されたブロックを選択する。この際、最終ブロック選択部１０５は、３２×３２画素に分割されたブロックの左下のブロックにおいては１６×１６画素に分割されたブロックを選択する。また、最終ブロック選択部１０５は、３２×３２画素に分割されたブロックの右下のブロックにおいては１６×１６画素に分割されたブロックを選択する。選択したブロックに基づいて、最終ブロック選択部１０５は、図２０（ｂ）に示すブロック構造を出力する。

上記の第三実施形態の構成により、第１候補ブロック判定部１０２ｂは、６４×６４画素のＬＣＵ、３２×３２画素に分割されたＬＣＵ、１６×１６画素に分割されたＬＣＵ、８×８画素に分割されたＬＣＵの各ブロックのブロックサイズと、対応する参照ブロックのブロックサイズとに基づいて、予測モードの種類に応じて、第１の候補ブロックに該当するか否かを判定する。第２候補ブロック判定部１０３は、予測モードとブロックサイズとに応じて予め定められる尤度、及び１段階ブロックサイズが大きいブロックから４分割された４個のブロックに占める第１の候補ブロックの割合に基づいて、４個のブロックの尤度の合計値を算出する。そして、尤度の合計値が、予め定められる尤度閾値以上の場合、当該ブロック群を第２の候補ブロックとする。これにより、符号化効率の低下を抑えつつ、ブロック構造決定処理の演算量を削減することが可能となる。

第一実施形態の構成では、各ブロックについて第１の候補ブロック及び第２の候補ブロックとするか否かを判定していた。そのため、第２候補ブロック判定部１０３の判定処理により、第１の候補ブロックでないブロックを第２の候補ブロックとして追加した場合、適用される全ての予測モードについて演算を行う必要があった。これに対して、第三実施形態の構成では、予測モードを考慮に加えて判定しているため、判定精度が向上し、更に、第２の候補ブロックを追加する際に、尤度の値が大きい予測モードに対応するブロックのみを第２の候補ブロックとしている。そのため、追加したブロックについては、当該予測モードについて演算するだけでよく、演算量の増加を抑えた上で第２の候補ブロックを追加することができる。例えば、図４の例において、第三実施形態では、第一実施形態では第２の候補ブロックとされていない、１６×１６画素に分割されたＬＣＵの右下ブロック群を新たに第２の候補ブロックとして追加しているが、４個のブロックの内２つは評価コストをインター予測モードのみで計算しているため、演算量の増加が抑えられた上で第一実施形態とは異なる精度の高いブロック構造を出力することを可能としている。

なお、上記の第三実施形態において、条件（４）は、候補となるブロックサイズにおいて、予測モードによって尤度が異なるという特徴を利用した条件である。しかしながら、本発明の構成は当該実施の形態に限られず、上記した以外の条件を適用するようにしてもよい。
また、条件（５）についても、上記した以外の条件を適用してもよく、例えば、図１５に示す尤度テーブルや尤度閾値を符号化結果に応じて適応的に変えるなどしてもよい。また、ブロックの位置関係を考慮し、例えば、新たに第２の候補ブロックとするブロックの予測モードを隣接ブロックの予測モードの候補の中で数が多い予測モードにしてもよい。また、隣接ブロックにおいて同じ予測モードが候補になっている場合、図１５に示す尤度テーブルにおいて、尤度の値を大きく設定するようにしてもよい。

上記の第一実施形態から第三実施形態では、ＨＥＶＣに準拠した構成を対象としているが、ＨＥＶＣに準拠した構成に限られるものではない。

また、上記の第一実施形態から第三実施形態では、ＬＣＵのサイズを６４×６４画素とし、ＣＵのサイズを６４×６４画素、３２×３２画素、１６×１６画素、８×８画素の４パターンの中からブロック構造を構成するブロックを選択している。しかしながら、本発明の構成は当該実施の形態に限られず、２つ以上のパターンの中からブロック構造を構成するブロックを選択する実施形態等にも適用することが可能である。

また、上記の第一実施形態から第三実施形態では、図３において説明した符号化対象ＬＣＵと、参照ブロックとの関係を示す動きベクトルとして、１つの動きベクトルを示しているが、動きベクトルを用いずに、符号化対象ＬＣＵと空間的に同位置のブロックを参照ブロックとしてもよいし、符号化対象ＬＣＵごとの動きベクトルではなく、符号化対象ＬＣＵの各ブロックそれぞれの動きベクトルを用いるようにしてもよい。

また、上記の第一実施形態から第三実施形態において、ブロックサイズ評価値算出部１０４が算出するＲＤコストは、評価コストの一例であり、ブロックを評価することのできる指標であればどのようなものでもよく、例えば、評価コストとして、誤差のみ、符号量のみ、輝度値の分散値等の統計値を適用してもよい。

また、上記の第一実施形態から第三実施形態において、予測モードとして、イントラ予測モードとインター予測モードを適用するようにしているが、本発明の実施の形態は、当該実施の形態に限られない。イントラ予測モードやインター予測モードに加えて、Merge予測モードやSkip予測モードを適用してもよく、また、これらの中の任意の２つ以上の予測モードを選択して適用するようにしてもよい。

例えば、Skip予測モードとMerge予測モードを適用する場合、参照ブロックがSkip予測モードの場合、参照ブロックのブロックサイズと同一、または、参照ブロックのブロックサイズより１段階大きいブロックサイズと同一であれば第１の候補ブロックとする。参照ブロックがSkip予測モード以外の場合、参照ブロックのブロックサイズと同一、または、参照ブロックのブロックサイズより１段階小さいブロックサイズと同一であれば第１の候補ブロックとする。
第２の候補ブロックを選択する手法としては、例えば、４分割された４個のブロックにおいて、第１の候補ブロックの割合が５０％以上であれば、第１の候補ブロックでない残りのブロックも含めて全てを第２の候補ブロックとする手法がある。また、他の手法として、点数によって第２の候補ブロックを選択する手法もある。例えば、参照ブロックのブロックサイズが３２×３２画素で、Skipモードである場合、符号化対象ブロックも３２×３２画素になる確率が高いとして２点、参照ブロックの予測モードがインター予測モードの場合、符号化対象ブロックが３２×３２画素になる確率は普通であるとして１点、参照ブロックの予測モードがイントラ予測モードの場合、符号化対象ブロックが３２×３２画素になる確率は低いとして０点というように点数を決めておく。４分割された４個のブロックにおける点数が４点を超えた場合、４個のブロック全てを第２の候補ブロックとして選択する手法もある。

また、上記の第一実施形態から第三実施形態において、第２候補ブロック判定部１０３、１０３ｂは、分割されたブロック群をまとめて第２の候補ブロックとするか否かを判定しており、このように複数のブロックを一度に判定することで、ＧＰＵ（Graphics Processing Unit）などの並列処理に特化したデバイスなどにおいて、大量のデータをまとめて処理することによる高速化の効果が得られるという利点がある。

また、上記の第一実施形態から第三実施形態において、図５、図１０、図１６のフローチャートにおけるＬａ１、Ｌａ２、Ｌｂ１、Ｌｂ２、Ｌｃ１、Ｌｃ２、Ｌｃ３のループ処理は、上述したように順番に行われてもよいし、並列に処理を行うようにしてもよい。

また、上記の第一実施形態から第三実施形態において、例えば、第一実施形態における条件（２）の所定個数以上とする判定、第二実施形態における重複回数の判定における所定回数以上とする判定、第三実施形態における尤度閾値以上とする判定の処理は、一例であり、ある値以上、ある値未満とする判定ではなく、ある値を超過、ある値以下とする判定であってもよい。
また、上記の第一実施形態から第三実施形態において、８×８画素についてはすべて条件（１）を満たさないため、８×８画素全てが第１の候補ブロックに該当しないという判定がなされる一例を示したが、以下のような場合には８×８画素の一部が第１の候補ブロックになるケースも想定される。それは、８×８の場合、その中心座標が参照ブロックの１６×１６画素のブロックに存在している場合である。この場合には、参照ブロックのサイズよりも１段階小さいサイズとなるため、８×８画素の一部が第１の候補ブロックになる。

上述した実施形態におけるブロック構造決定部１０、１０ａ、１０ｂをコンピュータで実現するようにしてもよい。その場合、この機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによって実現してもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでもよい。また上記プログラムは、前述した機能の一部を実現するためのものであってもよく、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであってもよく、ＦＰＧＡ（Field Programmable Gate Array）等のプログラマブルロジックデバイスを用いて実現されるものであってもよい。

以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。

１…映像符号化装置，１０…ブロック構造決定部，１１…減算器，１２…直交変換・量子化部，１３…可変長符号化部，１４…逆量子化・逆直交変換部，１５…加算器，１６…イントラ予測部，１７…イントラ・インター切替スイッチ，１８…ループフィルタ部，１９…復号ピクチャメモリ部，２０…インター予測部，１０１…ブロック分割部，１０２…第１候補ブロック判定部，１０３…第２候補ブロック判定部，１０４…ブロックサイズ評価値算出部，１０５…最終ブロック選択部，１０２１…６４×６４ブロック判定部，１０２２…３２×３２ブロック判定部，１０２３…１６×１６ブロック判定部，１０２４…８×８ブロック判定部

Claims (8)

1. 画像を複数の領域に分割し、前記領域を再帰的にブロックに分割することで生成される１つのブロックサイズで構成される若しくは複数のブロックサイズのブロックを組み合わせて構成されるブロック構造を決定するブロック構造決定部と、
   決定された前記ブロック構造に基づいて符号化を行う符号化部と、
   を備え、
   前記ブロック構造決定部は、
   前記ブロックサイズごとに、前記画像の領域を所定のサイズのブロックに分割するブロック分割部と、
   分割された前記ブロックのサイズと、前記ブロックが参照する領域の中心が属するブロックのサイズと、が等しい若しくは前記中心が属するブロックのサイズが１段階大きい場合、前記ブロックの各々が、第１の候補ブロックとなると判定する第１候補ブロック判定部と、
   前記所定のサイズより１段階大きいサイズのブロックを前記所定のサイズに分割して得られたブロック群が前記第１の候補ブロックとして判定されている数が所定の値以上の場合、前記ブロック群に属するすべてのブロックを第２の候補ブロックにすると判定する第２候補ブロック判定部と、
   前記第２の候補ブロックと判定された前記ブロックについて評価値を算出するブロックサイズ評価値算出部と、
   前記評価値に基づいて、前記画像の領域を分割する前記ブロックの組み合わせを選択する最終ブロック選択部と、
   を備える映像符号化装置。
2. 前記ブロック分割部は、あらかじめ定められた複数のサイズごとに前記画像を分割し、
   前記第１候補ブロック判定部と、前記第２候補ブロック判定部は、前記複数のサイズごとに判定を行い、
   前記画像の所定の領域について、前記第２候補ブロック判定部により重複して前記第２の候補ブロックにすると判定されている場合、前記画像の所定の領域についてのいずれかのブロックを前記第２の候補ブロックから除外する
   重複領域処理部をさらに備える、請求項１に記載の映像符号化装置。
3. 前記第１候補ブロック判定部は、前記画像に適用される予測モードごとに、分割された前記ブロックと、前記画像の領域に対応する参照ピクチャ内の領域を分割する参照ブロックとに基づいて、前記ブロックの各々が、第１の候補ブロックとなるか否かを判定し、
   前記第２候補ブロック判定部は、前記所定のサイズより１段階大きいサイズのブロックを前記所定のサイズに分割して得られたブロック群に対して、前記予測モードごとに、前記ブロック群に含まれる前記第１の候補ブロックの割合と、予測モードとブロックサイズとに応じて予め定められる尤度と、に基づいて、前記ブロック群のブロックを全て第２の候補ブロックにするか否かを判定する、請求項１又は２に記載の映像符号化装置。
4. 前記第１候補ブロック判定部は、いずれかの前記予測モードについて、分割された前記ブロックの各々のブロックサイズが、前記参照ブロックのブロックサイズと同一、または、前記参照ブロックのブロックサイズよりも１段階小さいブロックサイズと同一の場合、前記第１の候補ブロックとし、前記予測モード以外の予測モードについて、分割された前記ブロックの各々のブロックサイズが、前記参照ブロックのブロックサイズと同一、または、前記参照ブロックのブロックサイズよりも１段階大きいブロックサイズと同一の場合、前記第１の候補ブロックとして判定する、請求項３に記載の映像符号化装置。
5. ブロックサイズと前記予測モードの組み合わせごとに異なる尤度が予め定められており、
   前記第２候補ブロック判定部は、前記ブロック群のブロックサイズと、前記予測モードとに基づいて、前記予測モードごとの前記ブロック群の尤度を算出し、算出した尤度の合計値に基づいて、前記ブロック群のブロックを全て第２の候補ブロックにするか否かを判定する、請求項３又は４に記載の映像符号化装置。
6. 前記第２候補ブロック判定部は、前記ブロック群のブロックを全て第２の候補ブロックにすると判定した場合、前記ブロック群の中で前記第１の候補ブロックでないブロックを前記第２の候補ブロックとして追加する際に、前記ブロックを、複数の予測モードそれぞれにおいて得られる尤度の合計値の中で前記尤度の合計値の大きい前記予測モードに対応する前記第２の候補ブロックとして追加する、請求項５に記載の映像符号化装置。
7. 画像の領域をブロックに分割し、前記領域を再帰的にブロックに分割することで生成される１つのブロックサイズで構成される若しくは複数のブロックサイズのブロックを組み合わせて構成されるブロック構造を決定するブロック構造決定ステップと、
   決定された前記ブロック構造に基づいて符号化を行う符号化ステップと、
   を有し、
   前記ブロック構造決定ステップにおいて、
   前記ブロックサイズごとに、前記画像の領域を所定のサイズのブロックに分割するブロック分割ステップと、
   分割された前記ブロックのサイズと、前記ブロックが参照する領域の中心が属するブロックのサイズと、が等しい若しくは前記中心が属するブロックのサイズが１段階大きい場合、前記ブロックの各々が、第１の候補ブロックとなると判定する第１候補ブロック判定ステップと、
   前記所定のサイズより１段階大きいサイズのブロックを前記所定のサイズに分割して得られたブロック群が前記第１の候補ブロックとして判定されている数が所定の値以上の場合、前記ブロック群に属するすべてのブロックを第２の候補ブロックにすると判定する第２候補ブロック判定ステップと、
   前記第２の候補ブロックと判定された前記ブロックについて評価値を算出するブロックサイズ評価値算出ステップと、
   前記評価値に基づいて、前記画像の領域を分割する前記ブロックの組み合わせを選択する最終ブロック選択ステップと、
   を行うブロック構造決定方法。
8. 画像の領域をブロックに分割し、前記領域を再帰的にブロックに分割することで生成される１つのブロックサイズで構成される若しくは複数のブロックサイズのブロックを組み合わせて構成されるブロック構造を決定するブロック構造決定ステップと、
   決定された前記ブロック構造に基づいて符号化を行う符号化ステップと、
   をコンピュータに実行させ、
   前記ブロック構造決定ステップにおいて、
   前記ブロックサイズごとに、前記画像の領域を所定のサイズのブロックに分割するブロック分割ステップと、
   分割された前記ブロックのサイズと、前記ブロックが参照する領域の中心が属するブロックのサイズと、が等しい若しくは前記中心が属するブロックのサイズが１段階大きい場合、前記ブロックの各々が、第１の候補ブロックとなると判定する第１候補ブロック判定ステップと、
   前記所定のサイズより１段階大きいサイズのブロックを前記所定のサイズに分割して得られたブロック群が前記第１の候補ブロックとして判定されている数が所定の値以上の場合、前記ブロック群に属するすべてのブロックを第２の候補ブロックにすると判定する第２候補ブロック判定ステップと、
   前記第２の候補ブロックと判定された前記ブロックについて評価値を算出するブロックサイズ評価値算出ステップと、
   前記評価値に基づいて、前記画像の領域を分割する前記ブロックの組み合わせを選択する最終ブロック選択ステップと、
   を実行させるためのコンピュータプログラム。

Images