"符号化対象画像がn分木分割されている符号化ブロックと局部復号画像の間で動きを探索して、画像間の動き量を表す動きベクトルを検出する動きベクトル検出手段と、上記動きベクトル検出手段により検出された動きベクトルを用いて、上記符号化ブロックに対する動き補償予測を実施して予測画像を生成し、上記予測画像と上記符号化ブロックの差分である予測誤差を符号化する画像符号化手段とを備えた動画像符号化装置において、上記動きベクトル検出手段は、n分木分割されている符号化ブロック毎に、当該符号化ブロックにおけるテクスチャの平坦度を算出する平坦度算出部と、当該符号化ブロックの予測ベクトルと上記局部復号画像を用いて、当該符号化ブロックの動き補償予測誤差を算出する予測誤差算出部と、上記平坦度算出部により算出された平坦度と上記予測誤差算出部により算出された動き補償予測誤差から、動きベクトルの探索に用いるブロックとしての当該符号化ブロックの適合度を算出する適合度算出部と、上記適合度算出部により算出された適合度を参照して、n分木分割されている複数の符号化ブロックの中から、動きベクトルの探索に用いる符号化ブロックを選択する符号化ブロック選択部と、上記符号化ブロック選択部により選択された符号化ブロックと上記局部復号画像の間で動きを探索して、画像間の動き量を表す動きベクトルを検出する動きベクトル検出部とを備えていることを特徴とする動画像符号化装置。符号化ブロックのサイズと量子化パラメータを用いて、適合度算出部により算出された符号化ブロックの適合度を補正し、補正後の適合度を符号化ブロック選択部に出力する適合度補正部を備えていることを特徴とする請求項1記載の動画像符号化装置。符号化ブロック選択部は、未選択の符号化ブロックの中で、最も適合度が高い符号化ブロックを動きベクトルの探索に用いる符号化ブロックとして選択するとともに、上記符号化ブロックが属する階層より下位の階層に属する符号化ブロックを削除する処理を、全てのリーフが選択されるまで繰り返し実施することを特徴とする請求項1または請求項2記載の動画像符号化装置。適合度算出部により符号化ブロックの適合度が算出される毎に、当該符号化ブロックの適合度と基準の適合度を比較し、当該符号化ブロックの適合度が基準の適合度より高ければ、当該符号化ブロックを動きベクトル検出部に出力するとともに、当該符号化ブロックが属する階層より下位の階層に属する符号化ブロックに対する上記平坦度算出部、上記予測誤差算出部及び上記適合度算出部の算出処理を打ち切らせる閾値判定部を設けたことを特徴とする請求項1または請求項2記載の動画像符号化装置。動きベクトル検出手段により検出された1以上の動きベクトルの中で、1つ上位の階層に属する符号化ブロックが共通する兄弟ノードの符号化ブロックの動きベクトルの相違度を算出し、上記相違度が所定値より小さい場合、兄弟ノードの符号化ブロックの代わりに、1つ上位の階層に属する符号化ブロックの動きベクトルの検出を上記動きベクトル検出手段に指示する符号化ブロック変更手段を設けたことを特徴とする請求項1から請求項4のうちのいずれか1項記載の動画像符号化装置。画像符号化手段により生成された予測画像と符号化ブロックの差分である予測誤差が所定値より大きい場合、当該符号化ブロックの代わりに、当該符号化ブロックが属する階層より1つ上位の階層に属する符号化ブロック又は1つ下位の階層に属する符号化ブロックの動きベクトルの検出を上記動きベクトル検出手段に指示する符号化ブロック変更手段を設けたことを特徴とする請求項1から請求項4のうちのいずれか1項記載の動画像符号化装置。動きベクトル検出手段は、符号化ブロック変更手段から1つ上位の階層に属する符号化ブロック又は1つ下位の階層に属する符号化ブロックの動きベクトルを検出する指示が出力された場合、1つ上位又は1つ下位の階層に属する符号化ブロックの予測ベクトルとして、上記指示が出力される前に符号化ブロック選択部により選択された符号化ブロックの検出済みの動きベクトルを利用して、画像間の動きを探索することを特徴とする請求項5または請求項6記載の動画像符号化装置。平坦度算出部は、符号化ブロックにおけるテクスチャの平坦度として、当該符号化ブロック内の画素値の分散を算出することを特徴とする請求項1から請求項7のうちのいずれか1項記載の動画像符号化装置。適合度算出部は、符号化ブロックのサイズと量子化パラメータから重み係数を算出し、上記重み係数を用いて、平坦度算出部により算出された平坦度と予測誤差算出部により算出された動き補償予測誤差の重み付き和を算出し、その重み付き和を当該符号化ブロックの適合度として出力することを特徴とする請求項1から請求項8のうちのいずれか1項記載の動画像符号化装置。動きベクトル検出手段が、符号化対象画像がn分木分割されている符号化ブロックと局部復号画像の間で動きを探索して、画像間の動き量を表す動きベクトルを検出する動きベクトル検出処理ステップと、画像符号化手段が、上記動きベクトル検出処理ステップで検出された動きベクトルを用いて、上記符号化ブロックに対する動き補償予測を実施して予測画像を生成し、上記予測画像と上記符号化ブロックの差分である予測誤差を符号化する画像符号化処理ステップとを備えた動画像符号化方法において、上記動きベクトル検出処理ステップが、n分木分割されている符号化ブロック毎に、当該符号化ブロックにおけるテクスチャの平坦度を算出する平坦度算出処理ステップと、当該符号化ブロックの予測ベクトルと上記局部復号画像を用いて、当該符号化ブロックの動き補償予測誤差を算出する予測誤差算出処理ステップと、上記平坦度算出処理ステップで算出された平坦度と上記予測誤差算出処理ステップで算出された動き補償予測誤差から、動きベクトルの探索に用いるブロックとしての当該符号化ブロックの適合度を算出する適合度算出処理ステップと、上記適合度算出処理ステップで算出された適合度を参照して、n分木分割されている複数の符号化ブロックの中から、動きベクトルの探索に用いる符号化ブロックを選択する符号化ブロック選択処理ステップと、上記符号化ブロック選択処理ステップで選択された符号化ブロックと上記局部復号画像の間で動きを探索して、画像間の動き量を表す動きベクトルを検出する動きベクトル検出処理ステップとから構成されていることを特徴とする動画像符号化方法。符号化対象画像がn分木分割されている符号化ブロックと局部復号画像の間で動きを探索して、画像間の動き量を表す動きベクトルを検出する動きベクトル検出処理手順と、上記動きベクトル検出処理手順により検出された動きベクトルを用いて、上記符号化ブロックに対する動き補償予測を実施して予測画像を生成し、上記予測画像と上記符号化ブロックの差分である予測誤差を符号化する画像符号化処理手順とをコンピュータに実行させるための動画像符号化プログラムにおいて、上記動きベクトル検出処理手順が、n分木分割されている符号化ブロック毎に、当該符号化ブロックにおけるテクスチャの平坦度を算出する平坦度算出処理手順と、当該符号化ブロックの予測ベクトルと上記局部復号画像を用いて、当該符号化ブロックの動き補償予測誤差を算出する予測誤差算出処理手順と、上記平坦度算出処理手順により算出された平坦度と上記予測誤差算出処理手順により算出された動き補償予測誤差から、動きベクトルの探索に用いるブロックとしての当該符号化ブロックの適合度を算出する適合度算出処理手順と、上記適合度算出処理手順により算出された適合度を参照して、n分木分割されている複数の符号化ブロックの中から、動きベクトルの探索に用いる符号化ブロックを選択する符号化ブロック選択処理手順と、上記符号化ブロック選択処理手順により選択された符号化ブロックと上記局部復号画像の間で動きを探索して、画像間の動き量を表す動きベクトルを検出する動きベクトル検出処理手順とから構成されていることを特徴とする動画像符号化プログラム。従来の動画像符号化装置は以上のように構成されているので、符号化対象画像がn分木分割されている場合、n分木の符号化ブロックノードの中で、どの符号化ブロックが、動き補償予測に最適なブロックであるかを決定するには、全ての符号化ブロックについて動き探索を実施して動きベクトルを検出するとともに、その動きベクトルを用いて予測誤差を算出して、その予測誤差を比較する必要がある。そのため、動き探索の処理等の実施に伴う演算量が膨大になり、符号化処理の高速化を図ることが困難である課題があった。なお、特許文献1に開示されている方法を用いれば、動き探索に要する演算量を削減することができるが、符号化対象のブロックの特徴に関係なく、周辺ブロックを符号化する際に選択されたノードに基づいてノードの選択が行われるものであるため、全ての符号化ブロックについて動き探索等を実施することで、動き補償予測に最適なブロックを選択する場合と比べて、大きく選択結果が異なることがあり、この場合には、符号化性能が低下してしまう課題があった。この発明は上記のような課題を解決するためになされたもので、演算量を削減して符号化処理の高速化を図ることができるとともに、高い符号化性能を得ることができる動画像符号化装置、動画像符号化方法及び動画像符号化プログラムを得ることを目的とする。この発明に係る動画像符号化装置は、画像間の動き量を表す動きベクトルを検出する動きベクトル検出手段が、n分木分割されている符号化ブロック毎に、当該符号化ブロックにおけるテクスチャの平坦度を算出する平坦度算出部と、当該符号化ブロックの予測ベクトルと局部復号画像を用いて、当該符号化ブロックの動き補償予測誤差を算出する予測誤差算出部と、平坦度算出部により算出された平坦度と予測誤差算出部により算出された動き補償予測誤差から、動きベクトルの探索に用いるブロックとしての当該符号化ブロックの適合度を算出する適合度算出部と、適合度算出部により算出された適合度を参照して、n分木分割されている複数の符号化ブロックの中から、動きベクトルの探索に用いる符号化ブロックを選択する符号化ブロック選択部と、符号化ブロック選択部により選択された符号化ブロックと上記局部復号画像の間で動きを探索して、画像間の動き量を表す動きベクトルを検出する動きベクトル検出部とを備えるようにしたものである。この発明によれば、画像間の動き量を表す動きベクトルを検出する動きベクトル検出手段が、n分木分割されている符号化ブロック毎に、当該符号化ブロックにおけるテクスチャの平坦度を算出する平坦度算出部と、当該符号化ブロックの予測ベクトルと局部復号画像を用いて、当該符号化ブロックの動き補償予測誤差を算出する予測誤差算出部と、平坦度算出部により算出された平坦度と予測誤差算出部により算出された動き補償予測誤差から、動きベクトルの探索に用いるブロックとしての当該符号化ブロックの適合度を算出する適合度算出部と、適合度算出部により算出された適合度を参照して、n分木分割されている複数の符号化ブロックの中から、動きベクトルの探索に用いる符号化ブロックを選択する符号化ブロック選択部と、符号化ブロック選択部により選択された符号化ブロックと上記局部復号画像の間で動きを探索して、画像間の動き量を表す動きベクトルを検出する動きベクトル検出部とを備えるように構成したので、演算量を削減して符号化処理の高速化を図ることができるとともに、高い符号化性能を得ることができる効果がある。実施の形態1.図1はこの発明の実施の形態1による動画像符号化装置を示す構成図である。図1の動画像符号化装置には、符号化対象画像がn分木分割されている符号化ブロック例えば、図15に示す画像が符号化対象画像である場合、階層1の符号化ブロック1、階層2の符号化ブロック2,7,12,17、階層3の符号化ブロック3~6,8~11,13~16,18~21が入力される。また、図1の動画像符号化装置には、n分木分割されている各符号化ブロックの予測ベクトルが入力される。即ち、図1の動画像符号化装置の外部装置によって、空間的時間的に近傍にある符号化済みのブロックの動きベクトルから予測ベクトルが算出されて、その予測ベクトルが図1の動画像符号化装置に与えられる。図1において、符号化制御部1はn分木分割されている符号化ブロック毎に、利用可能な1以上の符号化モード1以上のイントラ符号化モード、1以上のインター符号化モードの中から、当該符号化ブロックに適する符号化モードを選択し、その符号化モードに対応する予測パラメータイントラ予測パラメータ、インター予測パラメータや、目標符号量及び量子化ステップ幅を示す量子化パラメータなどの符号化パラメータを出力する処理を実施する。評価値算出部2はn分木分割されている符号化ブロック毎に、動きベクトルの探索に用いるブロックとしての当該符号化ブロックの適合度を示す評価値を算出する処理を実施する。符号化ブロック選択部3は評価値算出部2により算出された評価値を参照して、n分木分割されている複数の符号化ブロックの中から、動きベクトルの探索に用いる符号化ブロックを選択する処理を実施する。動きベクトル検出部4は符号化ブロック選択部3により選択された符号化ブロックとフレームメモリ14に格納されている局部復号画像の間で動きを探索して、画像間の動き量を表す動きベクトルを検出する処理を実施する。なお、評価値算出部2、符号化ブロック選択部3及び動きベクトル検出部4から動きベクトル検出手段が構成されている。動き補償部5は符号化制御部1により選択された符号化モードがインター符号化モードである場合、動きベクトル検出部4により検出された動きベクトル及び符号化制御部1から出力されたインター予測パラメータを用いて、当該符号化ブロックに対する動き補償予測処理を実施して予測画像を生成する処理を実施する。画面内予測部6は符号化制御部1により選択された符号化モードがイントラ符号化モードである場合、符号化制御部1から出力されたイントラ予測パラメータを用いて、その符号化ブロックに対するイントラ予測処理を実施して予測画像を生成する処理を実施する。切替スイッチ7は符号化制御部1により選択された符号化モードがイントラ符号化モードであれば、画面内予測部6により生成された予測画像を選択し、符号化制御部1により選択された符号化モードがインター符号化モードであれば、動き補償部5により生成された予測画像を選択する処理を実施する。減算部8は符号化ブロックと切替スイッチ7により選択された予測画像の差分である予測誤差を算出する処理を実施する。直交変換量子化部9は予測誤差に残存する空間方向の冗長度を除くために、減算部8により算出された予測誤差の変換処理例えば、DCT離散コサイン変換や、予め特定の学習系列に対して基底設計がなされているKL変換等の直交変換処理を実施し、また、符号化制御部1から出力された量子化パラメータを用いて、その予測誤差の変換係数を量子化することで、量子化後の変換係数を圧縮データとして出力する処理を実施する。エントロピー符号化部10は直交変換量子化部9から出力された圧縮データと、符号化制御部1から出力された符号化モード及び符号化パラメータとをエントロピー符号化して、その圧縮データ、符号化モード及び符号化パラメータの符号化データが多重化されているビットストリームを生成する処理を実施する。なお、動き補償部5、減算部8、直交変換量子化部9及びエントロピー符号化部10から画像符号化手段が構成されている。逆量子化逆直交変換部11は符号化制御部1から出力された量子化パラメータを用いて、直交変換量子化部9から出力された圧縮データを逆量子化し、逆量子化の圧縮データの逆変換処理例えば、逆DCT逆離散コサイン変換や、逆KL変換等の逆変換処理を実施することで、逆変換処理後の圧縮データを局所復号予測誤差信号として出力する処理を実施する。加算部12は逆量子化逆直交変換部11から出力された局所復号予測誤差信号と切替スイッチ7により選択された予測画像を示す予測信号を加算することで、局所復号画像を示す局所復号画像信号を生成する処理を実施する。ループフィルタ部13は加算部12により生成された局所復号画像信号に含まれている符号化歪みを補償し、符号化歪み補償後の局所復号画像信号が示す局所復号画像をフレームメモリ14に出力する処理を実施する。フレームメモリ14は動き補償部5により次回の動き補償予測処理で用いられる参照画像として、ループフィルタ部13によるフィルタリング処理後の局所復号画像を格納するRAMなどの記録媒体である。イントラ予測用メモリ15は画面内予測部6により次回のイントラ予測処理で用いられる画像として、加算部12により生成された局所復号画像信号が示す局所復号画像を格納するRAMなどの記録媒体である。図1では、動画像符号化装置の構成要素である符号化制御部1、評価値算出部2、符号化ブロック選択部3、動きベクトル検出部4、動き補償部5、画面内予測部6、切替スイッチ7、減算部8、直交変換量子化部9、エントロピー符号化部10、逆量子化逆直交変換部11、加算部12及びループフィルタ部13のそれぞれが専用のハードウェア例えば、CPUを実装している半導体集積回路、あるいは、ワンチップマイコンなどで構成されているものを想定しているが、動画像符号化装置がコンピュータで構成される場合、符号化制御部1、評価値算出部2、符号化ブロック選択部3、動きベクトル検出部4、動き補償部5、画面内予測部6、切替スイッチ7、減算部8、直交変換量子化部9、エントロピー符号化部10、逆量子化逆直交変換部11、加算部12及びループフィルタ部13の処理内容を記述している動画像符号化プログラムを当該コンピュータのメモリに格納し、当該コンピュータのCPUが当該メモリに格納されている動画像符号化プログラムを実行するようにしてもよい。図2はこの発明の実施の形態1による動画像符号化装置の処理内容動画像符号化方法の要部を示すフローチャートである。図3はこの発明の実施の形態1による動画像符号化装置の評価値算出部2を示す構成図である。図3において、分散算出部21はn分木分割されている符号化ブロック毎に、当該符号化ブロックにおけるテクスチャの平坦度として、当該符号化ブロック内の画素値の分散を算出する処理を実施する。なお、分散算出部21は平坦度算出部を構成している。予測誤差算出部22は当該符号化ブロックの予測ベクトルと局部復号画像を用いて、当該符号化ブロックの動き補償予測誤差を算出する処理を実施する。分散予測誤差合成部23は分散算出部21により算出された分散と予測誤差算出部22により算出された動き補償予測誤差の重み付け和を算出することで、動きベクトルの探索に用いるブロックとしての当該符号化ブロックの適合度を示す評価値を算出する処理を実施する。なお、分散予測誤差合成部23は適合度算出部を構成している。評価値補正部24は符号化ブロックのサイズと量子化パラメータを用いて、分散予測誤差合成部23により算出された評価値を補正し、補正後の評価値を符号化ブロック選択部3に出力する処理を実施する。なお、評価値補正部24は適合度補正部を構成している。次に動作について説明する。ただし、評価値算出部2及び符号化ブロック選択部3以外の処理部は、例えば、非特許文献1などに開示されている動画像符号化装置と同様の構成要素であるため詳細な説明を省略し、ここでは、主に評価値算出部2及び符号化ブロック選択部3の処理内容を説明する。評価値算出部2は、n分木分割されている符号化ブロック、当該符号化ブロックの予測ベクトル及び符号化制御部1から出力された符号化パラメータを入力する。評価値算出部2は、n分木分割されている符号化ブロックを入力すると、符号化ブロック毎に、動きベクトルの探索に用いるブロックとしての当該符号化ブロックの適合度を示す評価値を算出する。以下、評価値算出部2の処理内容を具体的に説明する。図4は動きベクトルの探索に適しているブロックと適していないブロックの一例を示す説明図である。図4において、符号化対象画像から符号化ブロックとして分割されたブロック1の内部には、1つの物体人物しか含まれておらず、ブロック全体の動きを1つの動きベクトルで表現することができるため、ブロック1は動きベクトルの探索に適するブロックである。一方、符号化対象画像から符号化ブロックとして分割されたブロック2の内部には、複数の物体人物、自動車、道路が含まれており、それぞれの物体が異なる動きを持っているため、ブロック2は動きベクトルの探索に適さないブロックである。しかし、ブロック2を更に4つのブロック21~24に分割すると、4つのブロック21~24の内部には、1つの物体しか含まれておらず、動きベクトルの探索に適するブロックとなる。このように、ブロックの内部に複数の物体が含まれているか否かを調べることは、そのブロックが動きベクトルの探索に適しているか否かを評価するために効果的である。動き探索に適しているブロック1、21~24は、平坦なテクスチャを持っているのに対して、動き探索に適していないブロック2は非常に複雑なテクスチャを持っている。このため、その評価を行うための指標として、ブロックが持つテクスチャの平坦度が有効な指標となる。なお、平均値からのばらつきを表す統計量である分散は、テクスチャの平坦度として利用することができる。動き探索に適しているブロック1、21~24の画素値から算出される分散は小さな値になり、動き探索に適していないブロック2の画素値から算出される分散は大きな値になる。つまり、分散が小さな値を示すブロックほど、動き探索に適するブロックであると判断することができる。評価値算出部2の分散算出部21は、n分木分割されている符号化ブロック毎に、当該符号化ブロックにおけるテクスチャの平坦度として、当該符号化ブロック内の画素値の分散を算出する図2のステップST1。ここでは、分散算出部21が、テクスチャの平坦度として、画素値の分散を算出する例を示しているが、テクスチャの平坦度を示す指標であれば画素値の分散に限るものではなく、例えば、画素平面に対して平面当て嵌めを行うことで得られる当て嵌め誤差を算出するようにしてもよいし、当該符号化ブロック内の最大画素値と最小画素値の差分を算出するようにしてもよい。図5は動きベクトルの探索に適しているブロックと適していないブロックの一例を示す説明図である。図5において、符号化対象画像から分割されたブロック3は、図4のブロック1と同様の理由で、動きベクトルの探索に適するブロックである。また、符号化対象画像から分割されたブロック4は、図4のブロック2と同様の理由で、動きベクトルの探索に適さないブロックである。しかし、ブロック3の内部には、1つの物体しか含まれていないが、ブロック1と異なり、テクスチャの平坦度が低く、画素値の分散が大きな値になる。このように、物体が複雑なテクスチャを持つ場合、ブロックが静止領域に属する場合、あるいは、カメラのパンによって画面全体が一様に動いている場合などでは、テクスチャの平坦度と、動きベクトルの探索に対するブロックの適合度との間に関連性がない。したがって、画素値の分散だけでなく、ブロックが持つ動きについても、考慮した方が望ましい。そこで、評価値算出部2の予測誤差算出部22は、当該符号化ブロックの予測ベクトルと局部復号画像を用いて、当該符号化ブロックの動き補償予測誤差を算出するステップST2。即ち、予測誤差算出部22は、フレームメモリ14に格納されている局部復号画像の中から、当該符号化ブロックの予測ベクトルが指し示す位置から当該符号化ブロックと同サイズのブロックを抽出する。そして、予測誤差算出部22は、局部復号画像から抽出したブロックと当該符号化ブロックとの間で、画素毎の差分を計算することにより、動き補償予測誤差を算出する。ここでは、画素毎の差分を計算することで、動き補償予測誤差を算出する例を示しているが、画素毎の差分の総和を動き補償予測誤差として算出するようにしてもよいし、ブロックサイズの変化を正規化するために、画素毎の差分の総和を総画素数で割った平均値を動き補償予測誤差として算出するようにしてもよい。この動き補償予測誤差が小さければ、当該符号化ブロックの実際の動きも1つの動きベクトルで表現することができる可能性が高く、当該符号化ブロックは動きベクトルの探索に適していると判断することができる。評価値算出部2の分散予測誤差合成部23は、n分木分割されている符号化ブロック毎に、分散算出部21が当該符号化ブロック内の画素値の分散を算出し、予測誤差算出部22が当該符号化ブロックの動き補償予測誤差を算出すると、下記の式1に示すように、その分散と動き補償予測誤差の重み付け和を算出することで、動きベクトルの探索に用いるブロックとしての当該符号化ブロックの適合度を示す評価値を算出するステップST3。ここで、viは符号化ブロックiノードiの評価値、σi2は分散算出部21により算出された符号化ブロックiノードiの分散、eiは予測誤差算出部22により算出された符号化ブロックiノードiの動き補償予測誤差、αiは分散σi2に対する重み、βiは動き補償予測誤差eiに対する重みである。なお、動き補償予測誤差eiが小さい場合、分散σi2の大小によらず、動き補償予測誤差eiを重視した評価値viとする必要がある。一方、動き補償予測誤差eiが大きい場合、分散σi2を重視する必要がある。そのため、重みαi,βiは、例えば、下記の式2を用いて、決定することができる。このようにして、分散予測誤差合成部23により算出される評価値viは、値が小さい程、当該符号化ブロックiが動きベクトルの探索に適するブロックであることを表していると言える。ここでは、分散予測誤差合成部23が分散と動き補償予測誤差の重み付け和を計算することで評価値を算出する例を示しているが、評価値は分散と動き補償予測誤差の重み付け和に限るものではなく、例えば、分散と動き補償予測誤差の乗算や除算によって評価値を算出するようにしてもよい。なお、評価値としては、分散と動き補償予測誤差の他に、空間的時間的に当該符号化ブロックの近傍にある符号化済ブロックが属する階層の深さを用いることも考えられる。分散予測誤差合成部23により算出される評価値viは、一般に、当該符号化ブロックiノードiが属する階層が深いほどブロックサイズが小さいほど、値が小さくなる傾向があるため、下層にある符号化ブロックiノードiほど、動きベクトルの探索に適していると判断され易くなる。しかし、符号化性能の観点から考えると、ブロックサイズが小さくなると、その分だけ、多くの分割情報や動きベクトルを符号化しなければならず、符号量の増加につながる。そこで、評価値算出部2の評価値補正部24は、符号化ブロックが属している階層の深さに応じて、分散予測誤差合成部23により算出された評価値viの重み付けを行うことで、階層が深くなる程、評価値が大きくなるように補正を行う。これにより、ブロックサイズが必要以上に小さい符号化ブロックが選択されることを防ぐことができる。ただし、評価値補正部24が分散予測誤差合成部23により算出された評価値viを補正する際、量子化パラメータと符号化ブロックのサイズとの間にある関係性を考慮することが望ましい。量子化パラメータが小さいビットレートが高い場合、ビットレートと符号化歪のうち、符号化歪を抑えることを優先し、符号化ブロックのサイズを小さくして、動き補償予測誤差を小さくする方がよい。一方、量子化パラメータが大きいビットレートが低い場合、ビットレートを抑えることを優先し、符号化ブロックのサイズを大きくして、符号量を減らす方がよい。つまり、評価値に対して重み付けを行う際、重み付けの強度を量子化パラメータに応じて、適応的に変化させることで、符号化性能の向上が可能になる。そこで、評価値補正部24は、分散予測誤差合成部23により算出された評価値viを補正する際、符号化ブロックのサイズと量子化パラメータから重みγiを求め、その重みγiを評価値viに乗算することで、その評価値viを補正するようにするステップST4。評価値に対する重み付け関数としては、例えば、下記の式3に示すような関数を用いることができる。図7は関数γiの一例を示す説明図である。ここでは、評価値補正部24が、重みγiを評価値viに乗算することで、その評価値viを補正するようにしているが、その重みγiは、式3に示すような指数関数を用いて求めるものに限るものではなく、例えば、多項式関数や対数関数などの関数を用いて求めるようにしてもよい。符号化ブロック選択部3は、評価値算出部2がn分木分割されている全ての符号化ブロックiの評価値viを算出すると、各符号化ブロックiの評価値viを参照して、n分木分割されている全ての符号化ブロックの中から、動きベクトルの探索に適している符号化ブロックを選択するステップST5。即ち、符号化ブロック選択部3は、未選択の符号化ブロックの中で、最も適合度が高い符号化ブロックを選択して、その符号化ブロックが属する階層より下位の階層に属する符号化ブロックを削除する処理を全てのリーフ子ノードを持たないノードが選択されるまで繰り返し実施する。以下、符号化ブロック選択部3の処理内容を具体的に説明する。ここでは、符号化対象画像が、図8に示すように、四分木分割3階層の四分木分割されているものとして説明する。図8において、符号化ブロックノードに対応付けられている数値は、評価値算出部2の評価値補正部24から出力された補正後の評価値である。図9は符号化ブロック選択部3により選択される符号化ブロックノードを示す説明図である。図8の例では、最初に、符号化ブロック選択部3は、図9aに示すように、最も評価値が小さい符号化ブロック2を選択し、符号化ブロック2が属する階層より下位の階層に属する符号化ブロック3~6を削除する。次に、符号化ブロック選択部3は、図9bに示すように、未選択の符号化ブロックの中で、最も評価値が小さい符号化ブロック8を選択する。符号化ブロック8は子ノードを持っていないので、子ノードの削除は行われない。以降、全てのリーフ子ノードを持たないノードが選択されるまで、同様の処理が繰り返される図9c~h。なお、符号化ブロック12の評価値は110であり、下位の階層に属する符号化ブロック13~16の評価値より高いため適合度が低いため、符号化ブロック12は選択されず、下位の階層に属する符号化ブロック13~16が選択されている。一方、符号化ブロック7の評価値は88であり、下位の階層に属する符号化ブロック8の評価値68より高いが、同じく下位の階層に属する符号化ブロック9~11の評価値より低いため適合度が高いため、符号化ブロック8~11は選択されず、符号化ブロック7が選択されている。これにより、符号化ブロック選択部3に選択された符号化ブロックは、符号化ブロック2、7、13~17となる。動きベクトル検出部4は、符号化ブロック選択部3が1個以上の符号化ブロックを選択すると、符号化ブロック選択部3により選択された符号化ブロック毎に、フレームメモリ14に格納されている局部復号画像の中から、当該符号化ブロックの予測ベクトルが指し示す位置のブロック当該符号化ブロックと同一サイズのブロックを読み出し、その符号化ブロックと読み出しブロックの間で動きを探索して、画像間の動き量を表す動きベクトルを検出するステップST6。図9に示すように、7個の符号化ブロック符号化ブロック2、7、13~17が選択されている場合、動きベクトル検出部4により7個の符号化ブロックについて動きベクトルの探索処理が行われて、7個の動きベクトルが動き補償部5に出力される。以上で明らかなように、この実施の形態1によれば、n分木分割されている符号化ブロック毎に、当該符号化ブロックにおけるテクスチャの平坦度として、当該符号化ブロック内の画素値の分散を算出する分散算出部21と、当該符号化ブロックの予測ベクトルと局部復号画像を用いて、当該符号化ブロックの動き補償予測誤差を算出する予測誤差算出部22と、分散算出部21により算出された分散と予測誤差算出部22により算出された動き補償予測誤差から、動きベクトルの探索に用いるブロックとしての当該符号化ブロックの適合度を示す評価値を算出する分散予測誤差合成部23と、符号化ブロックのサイズと量子化パラメータを用いて、分散予測誤差合成部23により算出された評価値を補正する評価値補正部24と、評価値補正部24による補正後の評価値を参照して、n分木分割されている複数の符号化ブロックの中から、動きベクトルの探索に用いる符号化ブロックを選択する符号化ブロック選択部3と、符号化ブロック選択部3により選択された符号化ブロックと局部復号画像の間で動きを探索して、画像間の動き量を表す動きベクトルを検出する動きベクトル検出部4とを備えるように構成したので、演算量を削減して符号化処理の高速化を図ることができるとともに、高い符号化性能を得ることができる効果を奏する。即ち、この実施の形態1によれば、n分木分割されている全ての符号化ブロックを対象にして、動きベクトルの探索処理を実施するのではなく、動きベクトルの探索に適している符号化ブロックだけを対象にして、動きベクトルの探索処理を実施するようにしているため、動きベクトルの探索処理に関する演算量を大幅に削減することができる。また、分散、動き補償予測誤差、量子化パラメータ、ノードが属する階層の深さなどの複数のパラメータを複合的に利用して評価値を算出するようにしているため、従来技術例えば、特許文献1よりも信頼性が高いノード選択を行うことができる。さらに、n分木分割されている全ての符号化ブロックの評価値を算出した上で、動きベクトルの探索に適している符号化ブロックを選択しているため、全ての符号化ブロックを動きベクトルの探索候補ブロックとして考慮することができる。実施の形態2.上記実施の形態1では、n分木分割されている全ての符号化ブロックの評価値を算出し、それらの評価値を比較することで、動きベクトルの探索に適している符号化ブロックを選択するものを示したが、全ての符号化ブロックの評価値を算出する前に、ある符号化ブロックの評価値が所定の閾値より小さければ、その符号化ブロックを動きベクトルの探索に用いる符号化ブロックとして選択するとともに、その符号化ブロックが属する階層より下位の階層に属する符号化ブロックの評価値の算出処理を打ち切るようにしてもよい。図10はこの発明の実施の形態2による動画像符号化装置を示す構成図であり、図において、図1と同一符号は同一または相当部分を示すので説明を省略する。符号化ブロック選択部16は符号化ブロックの予測ベクトルや量子化パラメータ等を用いて、n分木分割されている複数の符号化ブロックの中から、動きベクトルの探索に用いる符号化ブロックを選択する処理を実施する。なお、符号化ブロック選択部16及び動きベクトル検出部4から動きベクトル検出手段が構成されている。図10では、動画像符号化装置の構成要素である符号化制御部1、符号化ブロック選択部16、動きベクトル検出部4、動き補償部5、画面内予測部6、切替スイッチ7、減算部8、直交変換量子化部9、エントロピー符号化部10、逆量子化逆直交変換部11、加算部12及びループフィルタ部13のそれぞれが専用のハードウェア例えば、CPUを実装している半導体集積回路、あるいは、ワンチップマイコンなどで構成されているものを想定しているが、動画像符号化装置がコンピュータで構成される場合、符号化制御部1、符号化ブロック選択部16、動きベクトル検出部4、動き補償部5、画面内予測部6、切替スイッチ7、減算部8、直交変換量子化部9、エントロピー符号化部10、逆量子化逆直交変換部11、加算部12及びループフィルタ部13の処理内容を記述している動画像符号化プログラムを当該コンピュータのメモリに格納し、当該コンピュータのCPUが当該メモリに格納されている動画像符号化プログラムを実行するようにしてもよい。図11はこの発明の実施の形態2による動画像符号化装置の符号化ブロック選択部16を示す構成図である。図11において、ノード指示部31は分散算出部32及び予測誤差算出部33における算出処理対象の符号化ブロックノードを指示する処理を実施する。分散算出部32はn分木分割されている符号化ブロックの中で、ノード指示部31により指示された符号化ブロックにおけるテクスチャの平坦度として、当該符号化ブロック内の画素値の分散を算出する処理を実施する。なお、分散算出部32は平坦度算出部を構成している。予測誤差算出部33はノード指示部31により指示された符号化ブロックの予測ベクトルと局部復号画像を用いて、当該符号化ブロックの動き補償予測誤差を算出する処理を実施する。分散予測誤差合成部34は分散算出部32により算出された分散と予測誤差算出部33により算出された動き補償予測誤差の重み付け和を算出することで、動きベクトルの探索に用いるブロックとしての当該符号化ブロックの適合度を示す評価値を算出する処理を実施する。なお、分散予測誤差合成部34は適合度算出部を構成している。評価値補正部35は符号化ブロックのサイズと量子化パラメータを用いて、分散予測誤差合成部34により算出された評価値を補正する処理を実施する。なお、評価値補正部35は適合度補正部を構成している。閾値判定部36は評価値補正部35による補正後の評価値と閾値を比較し、補正後の評価値が閾値より低い場合符号化ブロックの適合度が基準の適合度より高い場合、当該符号化ブロックを選択する処理を実施する。また、閾値判定部36は補正後の評価値が閾値より低い場合、その選択した符号化ブロックが属する階層より下位の階層に属する符号化ブロックに対する分散算出部32、予測誤差算出部33、分散予測誤差合成部34及び評価値補正部35の算出処理を打ち切らせる旨をノード指示部31に指示する処理を実施する。次に動作について説明する。図1の評価値算出部2及び符号化ブロック選択部3の代わりに、符号化ブロック選択部16が設けられている点以外は、上記実施の形態1と同様であるため、ここでは、符号化ブロック選択部16の処理内容を説明する。符号化ブロック選択部16は、符号化ブロックの予測ベクトルや量子化パラメータ等を入力すると、その予測ベクトルや量子化パラメータ等を用いて、n分木分割されている複数の符号化ブロックの中から、動きベクトルの探索に用いる符号化ブロックを選択して、その符号化ブロックを動きベクトル検出部4に出力する。具体的には、以下の通りである。まず、符号化ブロック選択部16のノード指示部31は、条件フラグを0に初期化して、対象ノードをルート図8の例では、符号化ブロック1に設定する。ここでは、条件フラグが0である場合、符号化ブロックの階層構造を表すn分木において、深さ優先で対象ノードの次にあたるノードを出力し、そのノードを新たな対象ノードに設定するものとする。ただし、対象ノードがルートの場合は、ルートをそのまま出力する。条件フラグが1である場合、n分木において、対象ノードの子ノード以下を全て削除した上で、深さ優先で対象ノードの次にあたるノードを出力し、そのノードを新たな対象ノードに設定するものとする。したがって、最初は、評価値を算出する処理対象の符号化ブロックをルートの符号化ブロック図8の例では、符号化ブロック1に設定する。分散算出部32は、ノード指示部31が算出処理対象の符号化ブロックを設定すると、その符号化ブロックにおけるテクスチャの平坦度として、当該符号化ブロック内の画素値の分散を算出する。分散算出部32による分散の算出処理は、図3の分散算出部21と同様であるため詳細な説明を省略する。予測誤差算出部33は、ノード指示部31が算出処理対象の符号化ブロックを設定すると、その符号化ブロックの予測ベクトルと局部復号画像を用いて、当該符号化ブロックの動き補償予測誤差を算出する。予測誤差算出部33による動き補償予測誤差の算出処理は、図3の予測誤差算出部22と同様であるため詳細な説明を省略する。分散予測誤差合成部34は、分散算出部32が分散を算出し、予測誤差算出部33が動き補償予測誤差を算出すると、図3の分散予測誤差合成部23と同様に、その分散と動き補償予測誤差の重み付け和を算出することで、動きベクトルの探索に用いるブロックとしての当該符号化ブロックの適合度を示す評価値を算出する。評価値補正部35は、分散予測誤差合成部34が評価値を算出すると、図3の評価値補正部24と同様に、符号化ブロックのサイズと量子化パラメータを用いて、その評価値を補正する。閾値判定部36は、評価値補正部35が評価値を補正すると、補正後の評価値と所定の閾値を比較する。閾値判定部36は、補正後の評価値が閾値より小さい場合、ノード指示部31により指定された符号化ブロックは動きベクトルの探索に適しているブロックであると判断し、その符号化ブロックを動きベクトル検出部4に出力する。このように、ノード指示部31により指定された符号化ブロックを選択して、その符号化ブロックを動きベクトル検出部4に出力する場合、既に動きベクトルの探索に適している符号化ブロックが見つかっており、もはや、その符号化ブロックが属する階層より下位の階層に属する符号化ブロックの評価値を算出する必要がないため、条件フラグを1に設定して、1の条件フラグをノード指示部31に出力する。一方、補正後の評価値が閾値以上である場合、動きベクトルの探索に適している符号化ブロックを引き続き探索する必要があるため、0の条件フラグをノード指示部31に出力する。ノード指示部31は、閾値判定部36から0の条件フラグを受けると、n分木において、深さ優先で対象ノードの次にあたるノードを出力し、そのノードを新たな対象ノードに設定する。図8の例では、例えば、前回設定している符号化ブロックが符号化ブロック1であれば、符号化ブロック2を評価値の算出処理対象に設定し、前回設定している符号化ブロックが符号化ブロック2であれば、符号化ブロック3を評価値の算出処理対象に設定し、前回設定している符号化ブロックが符号化ブロック3であれば、符号化ブロック4を評価値の算出処理対象に設定する。ノード指示部31は、閾値判定部36から1の条件フラグを受けると、前回設定している符号化ブロックが属する階層より下位の階層に属する符号化ブロックの評価値を算出する必要がないため、下位の階層に属する符号化ブロックを削除する。図8の例では、例えば、符号化ブロック1が選択された場合、符号化ブロック2~21を削除し、符号化ブロック7が選択された場合、符号化ブロック8~11を削除する。ただし、符号化ブロック8や符号化ブロック15などが選択された場合、下位の階層に属する符号化ブロックがないため、削除する符号化ブロックはない。また、ノード指示部31は、未選択の符号化ブロックにおいて、深さ優先で対象ノードの次にあたるノードを出力し、そのノードを新たな対象ノードに設定する。図8の例では、例えば、前回設定している符号化ブロックが符号化ブロック2であり、その符号化ブロック2が選択された場合、符号化ブロック3~6を削除しているので、符号化ブロック7を評価値の算出処理対象に設定する。また、前回設定している符号化ブロックが符号化ブロック3であり、その符号化ブロック3が選択された場合、符号化ブロック4を評価値の算出処理対象に設定し、前回設定している符号化ブロックが符号化ブロック6であり、その符号化ブロック6が選択された場合、符号化ブロック7を評価値の算出処理対象に設定する。以上で明らかなように、この実施の形態2によれば、ノード指示部31により指定された符号化ブロックの評価値を算出し、その評価値が所定の閾値より小さければ、当該符号化ブロックを動きベクトルの探索に用いる符号化ブロックとして選択するとともに、当該符号化ブロックが属する階層より下位の階層に属する符号化ブロックに対する分散算出部32、予測誤差算出部33、分散予測誤差合成部34及び評価値補正部35の算出処理を打ち切るように構成しているので、評価値の算出処理に要する演算量を大幅に削減して、符号化処理の高速化を図ることができる効果を奏する。実施の形態3.上記実施の形態1,2では、符号化ブロック選択部3,16により選択された符号化ブロックの動きベクトルを探索して動き補償予測を行うものを示したが、動きベクトルの探索結果や動き補償予測結果に基づいて、符号化ブロック選択部3,16により選択された符号化ブロックを変更して、再度、動きベクトルの探索や動き補償予測を行うようにしてもよい。図12はこの発明の実施の形態3による動画像符号化装置を示す構成図であり、図において、図1と同一符号は同一または相当部分を示すので説明を省略する。ノード探索範囲変更部17は動きベクトル検出部18により検出された1以上の動きベクトルの中で、1つ上位の階層に属する符号化ブロックが共通する兄弟ノードの符号化ブロックの動きベクトルの相違度を算出し、その相違度が所定値より大きい場合、兄弟ノードの符号化ブロックの代わりに、1つ上位の階層に属する符号化ブロック又は1つ下位の階層に属する符号化ブロックの動きベクトルの検出を動きベクトル検出部18に指示する処理を実施する。また、ノード探索範囲変更部17は減算部8により算出された予測誤差が所定値より大きい場合、その予測誤差の算出に用いられた符号化ブロックの代わりに、1つ上位の階層に属する符号化ブロック又は1つ下位の階層に属する符号化ブロックの動きベクトルの検出を動きベクトル検出部18に指示する処理を実施する。なお、ノード探索範囲変更部17は符号化ブロック変更手段を構成している。動きベクトル検出部18は図1の動きベクトル検出部4と同様に、符号化ブロック選択部3により選択された符号化ブロックとフレームメモリ14に格納されている局部復号画像の間で動きを探索して、画像間の動き量を表す動きベクトルを検出する処理を実施するが、ノード探索範囲変更部17から1つ上位の階層に属する符号化ブロック又は1つ下位の階層に属する符号化ブロックの動きベクトルを検出する指示が出力された場合、1つ上位又は1つ下位の階層に属する符号化ブロックの予測ベクトルとして、その指示が出力される前に符号化ブロック選択部3により選択された符号化ブロックの検出済みの動きベクトルを利用して、画像間の動きを探索する処理を実施する。なお、評価値算出部2、符号化ブロック選択部3及び動きベクトル検出部18から動きベクトル検出手段が構成されている。図12では、動画像符号化装置の構成要素である符号化制御部1、評価値算出部2、符号化ブロック選択部3、動きベクトル検出部18、動き補償部5、画面内予測部6、切替スイッチ7、減算部8、直交変換量子化部9、エントロピー符号化部10、逆量子化逆直交変換部11、加算部12、ループフィルタ部13及びノード探索範囲変更部17のそれぞれが専用のハードウェア例えば、CPUを実装している半導体集積回路、あるいは、ワンチップマイコンなどで構成されているものを想定しているが、動画像符号化装置がコンピュータで構成される場合、符号化制御部1、評価値算出部2、符号化ブロック選択部3、動きベクトル検出部18、動き補償部5、画面内予測部6、切替スイッチ7、減算部8、直交変換量子化部9、エントロピー符号化部10、逆量子化逆直交変換部11、加算部12、ループフィルタ部13及びノード探索範囲変更部17の処理内容を記述している動画像符号化プログラムを当該コンピュータのメモリに格納し、当該コンピュータのCPUが当該メモリに格納されている動画像符号化プログラムを実行するようにしてもよい。図13はこの発明の実施の形態3による動画像符号化装置のノード探索範囲変更部17を示す構成図である。図13において、兄弟ノード動きベクトル相違度算出部41は動きベクトル検出部18により検出された1以上の動きベクトルの中で、1つ上位の階層に属する符号化ブロックが共通する兄弟ノードの符号化ブロックの動きベクトルの相違度を算出する処理を実施する。ノード探索範囲変更判定部42は兄弟ノード動きベクトル相違度算出部41により算出された相違度が所定値より小さい場合、あるいは、減算部8により算出された予測誤差が所定値より大きい場合、ノード探索範囲変更部17から指示が出力される前に符号化ブロック選択部3により選択された符号化ブロックの代わりに、1つ上位の階層に属する符号化ブロック又は1つ下位の階層に属する符号化ブロックの動きベクトルの検出を動きベクトル検出部18に指示する処理を実施する。次に動作について説明する。上記実施の形態1,2と比べて、ノード探索範囲変更部17が実装されている点で相違している。ノード探索範囲変更部17の兄弟ノード動きベクトル相違度算出部41は、符号化ブロック選択部3により選択されたN個の符号化ブロックの中に、1つ上位の階層に属する符号化ブロックが共通する兄弟ノードの符号化ブロックが含まれているか否かを確認する。図8の場合、例えば、符号化ブロック2と符号化ブロック7は、符号化ブロック1が共通の親ノードであるため兄弟ノードである。同様に、符号化ブロック3と符号化ブロック5は、符号化ブロック2が共通の親ノードであるため兄弟ノードである。ここで、図14は兄弟ノードの符号化ブロックの動きベクトルが似通っている例を示す説明図である。図14の例では、階層3に属する4つの符号化ブロックの動きベクトルが似通っている。符号量を削減する観点からすると、兄弟ノードの符号化ブロック毎に、動きベクトルを用いて、動き補償予測を実施するよりも、親ノードの符号化ブロックの1つの動きベクトルを用いて、動き補償予測を実施する方が有利である。そこで、兄弟ノード動きベクトル相違度算出部41は、符号化ブロック選択部3により選択されたN個の符号化ブロックの中に、兄弟ノードの符号化ブロックが含まれている場合、動きベクトル検出部18により検出された兄弟ノードの符号化ブロックの動きベクトルの相違度を算出する。動きベクトルの相違度としては、例えば、動きベクトルの先端間の距離などを用いることができる。ノード探索範囲変更判定部42は、兄弟ノード動きベクトル相違度算出部41が兄弟ノードの符号化ブロックの動きベクトルの相違度を算出すると、その相違度と所定値を比較し、その相違度が所定値より大きい場合、兄弟ノードの符号化ブロックの代わりに、1つ上位の階層に属する符号化ブロックの検出を動きベクトル検出部18に指示する。あるいは、1つ下位の階層に属する符号化ブロックの検出を動きベクトル検出部18に指示する。あるいは、1つ上位の階層に属する符号化ブロックと1つ下位の階層に属する符号化ブロックの双方の検出を動きベクトル検出部18に指示する。また、ノード探索範囲変更判定部42は、減算部8により算出された予測誤差が所定値より大きい場合、その予測誤差の算出に用いられた符号化ブロックの選択の信頼性が低いと考えられるため、その符号化ブロックの代わりに、1つ上位の階層に属する符号化ブロックの検出を動きベクトル検出部18に指示する。あるいは、1つ下位の階層に属する符号化ブロックの検出を動きベクトル検出部18に指示する。あるいは、1つ上位の階層に属する符号化ブロックと1つ下位の階層に属する符号化ブロックの双方の検出を動きベクトル検出部18に指示する。動きベクトル検出部18は、ノード探索範囲変更部17から1つ上位又は1つ下位の階層に属する符号化ブロックの動きベクトルを検出する指示が出力された場合、1つ上位又は1つ下位の階層に属する符号化ブロックの予測ベクトルとして、その指示が出力される前に符号化ブロック選択部3により選択された符号化ブロックの検出済みの動きベクトルを利用して、画像間の動きを探索する。即ち、動きベクトル検出部18は、兄弟ノードの符号化ブロックの代わりに、親ノード又は子ノードの符号化ブロックの動きベクトルを検出する指示が出力された場合、フレームメモリ14に格納されている局部復号画像の中から、兄弟ノードの符号化ブロックの検出済みの動きベクトルが指し示す位置のブロックを読み出し、親ノード又は子ノードの符号化ブロックと読み出しブロックの間で動きを探索して、画像間の動き量を表す動きベクトルを検出する。例えば、兄弟ノードの個数が4個である場合、4個の動きベクトルから求めた代表ベクトル例えば、平均ベクトルなどが指し示す位置のブロックを親ノードの符号化ブロックに対応する読み出しブロックとして用いてもよいし、4個のブロックをすべて含んだブロックを用いてもよい。動き補償部5は、動きベクトル検出部18が、1つ上位又は1つ下位の階層に属する符号化ブロックの動きベクトルを検出すると、その動きベクトルを用いて、当該符号化ブロックに対する動き補償予測処理を実施して予測画像を生成するが、その動き補償予測処理を実施した結果、符号化ブロックを変更する前の方が、符号化効率が高い場合、その予測画像を破棄して、符号化ブロックを変更する前の予測画像を最終的な予測画像に決定する。一方、符号化ブロックを変更した後の方が、符号化効率が高い場合、符号化ブロックを変更する前の予測画像を破棄して、符号化ブロックを変更した後の予測画像を最終的な予測画像に決定する。以上で明らかなように、この実施の形態3によれば、動きベクトル検出部18により検出された1以上の動きベクトルの中で、1つ上位の階層に属する符号化ブロックが共通する兄弟ノードの符号化ブロックの動きベクトルの相違度を算出し、その相違度が所定値より小さい場合、あるいは、減算部8により算出された予測誤差が所定値より大きい場合、兄弟ノードの符号化ブロック等の代わりに、1つ上位の階層に属する符号化ブロック又は1つ下位の階層に属する符号化ブロックの検出を動きベクトル検出部18に指示するように構成したので、符号量を削減効果や、符号化ブロック選択の信頼性などを高めることができる効果を奏する。即ち、符号化ブロック選択部3により選択された符号化ブロックの信頼性が低いと考えられる場合には、別の符号化ブロックを新たに選択して動き探索を実施することが可能になるため、符号化性能の向上を図ることができる。また、新たに動きベクトルの探索処理を実施する際に、検出済みの動きベクトルを予測ベクトルとして利用して、探索範囲を削減することで、動きベクトルの探索精度を落とすことなく、探索回数が増えることによる演算量の増加を最小限に抑えることができる。なお、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。"