(57)【要約】【課題】  トータルの演算量を減らしつつ最適なブロックサイズの選択を可能とする。【解決手段】  推定動きベクトル演算部２１は第一ブロックと第一ブロックを複数に分割した第二ブロックのいずれか一方を動き補償予測ブロックとして選択する際に探索アルゴリズムの第一反復又は最大反復数以下の少ない反復で複数の第二ブロックの各々の動きベクトルを演算する。第一判定部２２はそれらの動きベクトルが等価である場合に第一ブロックを選択する。一方、それらの動きベクトルが等価でない場合にＳＢ探索部２５は、探索アルゴリズムの最大反復数で複数の第二ブロックの各々の動きベクトルを演算する。第二判定部２６はその動きベクトルの等価を判定して等価の場合に第一ブロックを選択し、等価でない場合に第二ブロックを選択する。【選択図】  図４
2006180014.tif 000002
【特許請求の範囲】
【請求項１】
第一ブロックと該第一ブロックを複数に分割した第二ブロックのいずれか一方を動き補償予測ブロックとして選択するブロック選択手段を備えた動き補償予測符号化装置において、
前記ブロック選択手段は、
前記複数の第二ブロックの各々の動きベクトルを予め定められた反復数以下の少ない反復で所定の探索アルゴリズムにより演算する第一動きベクトル演算手段と、
前記第一動きベクトル演算手段で演算された第二ブロックの各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第一判定手段とを含み、
前記第一判定手段の判定結果が肯定の場合に前記第一ブロックを動き補償予測ブロックとして選択する一方、前記第一判定手段の判定結果が否定の場合に前記第二ブロックを動き補償予測ブロックとして選択することを特徴とする動き補償予測符号化装置。
【請求項２】
第一ブロックと該第一ブロックを複数に分割した第二ブロックのいずれか一方を動き補償予測ブロックとして選択するブロック選択手段を備えた動き補償予測符号化装置において、
前記ブロック選択手段は、
前記複数の第二ブロックの各々の動きベクトルを予め定められた第１の反復数以下の少ない反復で所定の探索アルゴリズムにより演算する第一動きベクトル演算手段と、
前記第一動きベクトル演算手段で演算された第二ブロックの各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第一判定手段と、
前記第一判定手段の判定結果が肯定の場合に前記第一ブロックを動き補償予測ブロックとして選択する第一選択手段と、
前記第一判定手段の判定結果が肯定の場合に前記第一ブロックの動きベクトルを予め定められた第２の反復数を上限にして所定の探索アルゴリズムにより演算する第二動きベクトル演算手段と、
前記第一判定手段の判定結果が否定の場合に前記複数の第二ブロックの各々の動きベクトルを予め定められた第３の反復数を上限にして所定の探索アルゴリズムにより演算する第三動きベクトル演算手段と、
前記第三動きベクトル演算手段で演算された第二ブロックの各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第二判定手段と、
前記第二判定手段の判定結果が肯定の場合に前記第一ブロックを動き補償予測ブロックとして選択する一方、前記第二判定手段の判定結果が否定の場合に前記第二ブロックを動き補償予測ブロックとして選択する第二選択手段と
を備えたことを特徴とする動き補償予測符号化装置。
【請求項３】
前記所定の探索アルゴリズムは、最近傍探索法又はＮステップ探索法若しくは対数探索法であることを特徴とする請求項１又は請求項２記載の動き補償予測符号化装置。
【請求項４】
前記第二動きベクトル演算手段及び前記第三動きベクトル演算手段は、前記第一動きベクトル演算手段の反復がｎ′回のとき、ｎ′＋１回から反復を開始するとともに、その反復の初期値として、前記第一動きベクトル演算手段のｎ′反復で得られた中間値を使用することを特徴とする請求項２記載の動き補償予測符号化装置。
【請求項５】
第一ブロックと該第一ブロックを複数に分割した第二ブロックのいずれか一方を動き補償予測ブロックとして選択する際に、
前記複数の第二ブロックの各々の動きベクトルを予め定められた反復数以下の少ない反復で所定の探索アルゴリズムにより演算する第一動きベクトル演算工程と、
前記第一動きベクトル演算工程で演算された第二ブロックの各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第一判定工程と、
前記第一判定工程の判定結果が肯定の場合に前記第一ブロックを動き補償予測ブロックとして選択する一方、前記第一判定工程の判定結果が否定の場合に前記第二ブロックを動き補償予測ブロックとして選択する選択工程と
を実行することを特徴とする動き補償予測符号化方法。
【請求項６】
第一ブロックと該第一ブロックを複数に分割した第二ブロックのいずれか一方を動き補償予測ブロックとして選択する際に、
前記複数の第二ブロックの各々の動きベクトルを予め定められた第１の反復数以下の少ない反復で所定の探索アルゴリズムにより演算する第一動きベクトル演算工程と、
前記第一動きベクトル演算工程で演算された第二ブロックの各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第一判定工程と、
前記第一判定工程の判定結果が肯定の場合に前記第一ブロックを動き補償予測ブロックとして選択する第一選択工程と、
前記第一判定工程の判定結果が肯定の場合に前記第一ブロックの動きベクトルを予め定められた第２の反復数を上限にして所定の探索アルゴリズムにより演算する第二動きベクトル演算工程と、
前記第一判定工程の判定結果が否定の場合に前記複数の第二ブロックの各々の動きベクトルを予め定められた第３の反復数を上限にして所定の探索アルゴリズムにより演算する第三動きベクトル演算工程と、
前記第三動きベクトル演算工程で演算された第二ブロックの各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第二判定工程と、
前記第二判定工程の判定結果が肯定の場合に前記第一ブロックを動き補償予測ブロックとして選択する一方、前記第二判定工程の判定結果が否定の場合に前記第二ブロックを動き補償予測ブロックとして選択する第二選択工程と
を実行することを特徴とする動き補償予測符号化方法。
【請求項７】
前記所定の探索アルゴリズムは、最近傍探索法又はＮステップ探索法若しくは対数探索法であることを特徴とする請求項５又は請求項６記載の動き補償予測符号化方法。
【請求項８】
前記第二動きベクトル演算工程及び前記第三動きベクトル演算工程は、前記第一動きベクトル演算工程の反復がｎ′回のとき、ｎ′＋１回から反復を開始するとともに、その反復の初期値として、前記第一動きベクトル演算工程のｎ′反復で得られた中間値を使用することを特徴とする請求項６記載の動き補償予測符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動き補償予測符号化装置及び動き補償予測符号化方法に関し、詳しくは、動き補償予測ブロックのサイズを選択して使用できる動き補償予測符号化装置及び動き補償予測符号化方法に関する。
【背景技術】
【０００２】
我々が目にする動画は、時間軸上に連続する多数のフレーム画像（静止画）の残像に過ぎない。ギクシャク感のないスムーズな動きにするには、残像効果が失われる前に次のフレーム画像を表示しなければならず、それには、たとえば、毎秒３０フレームないしはそれ以上のフレーム画像を必要とするが、こうした多数のフレーム画像からなる動画は、その情報量が膨大なものとなり、蓄積媒体の容量や伝送経路の帯域を圧迫する。
【０００３】
そこで、動画の情報量を削減（圧縮）するための技術として、「動き補償予測符号化」が用いられる。
【０００４】
図１６は、動き補償予測符号化の簡略化した概念図である。左列に符号化前（情報量削減前）の画像（以下、元画像）Ｐ１、Ｐ２、Ｐ３、・・・・、Ｐ７が並んでいる。並び順は時間軸に沿って上から下である。動き補償予測符号化では、少なくとも１枚の元画像Ｐ１（イントラ画像ともいう）はそのまま（無圧縮又は静止画の符号化技術で圧縮し）伝送路（又は蓄積媒体）を介して復号側に送出しなければならないが、残りの元画像Ｐ２、Ｐ３、・・・・、Ｐ７については、時間軸を過去に遡った一つ前の元画像（参照画像）との間の「動き情報」を取り出し、その動き情報からなる被符号化画像Ｐ２′、Ｐ３′、・・・・、Ｐ７′を伝送路を介して復号側に送出する。被符号化画像Ｐ２′、Ｐ３′、・・・・、Ｐ７′の情報量は、元画像Ｐ２、Ｐ３、・・・・、Ｐ７のそれよりも少ない。このため、伝送路上（または蓄積媒体）における情報量は、すべての元画像を送出する場合に比べて遙かに削減される。
【０００５】
復号側では、イントラ画像（元画像Ｐ１）はそのまま復元画像Ｐ１″として用いるが、それ以外の復元画像Ｐ２′、Ｐ３′、・・・・、Ｐ７′については、時間軸を過去に遡った一つ前の復元画像と「動き情報」とにより画像を再生するという手順を繰り返すことにより、元画像Ｐ１、Ｐ２、Ｐ３、・・・・、Ｐ７と同じ並びの復元画像Ｐ１″、Ｐ２″、Ｐ３″、・・・・、Ｐ７″を得る。なお、図の説明では、時間軸を過去に遡った一つ“前”の元画像を「参照画像」としているが、これは伝送系メディアの場合である。蓄積系では時間軸上の未来の画像（一つ“後”の元画像）を「参照画像」とすることもある。
【０００６】
図１７は、動き補償予測符号化における被符号化画像生成の概念図である（たとえば、特許文献１参照。）。この図において、動き補償予測符号化では、動画像を構成する元画像を１６×１６画素などの小さな動き補償予測ブロック（以下、単に「ブロック」という）に分割し、このブロック単位に、時間的に前（蓄積系では後の場合もある）に位置する参照画像から被符号化画像を作成する。
【０００７】
具体的には、たとえば、被符号化画像１がＢ１〜Ｂ２５（Ｂはブロックの略）までの２５個のブロックに分割されていると仮定した場合、まず、Ｂ１と同じ大きさのブロック（Ｂ１′）を参照画像２から取り出し、そのＢ１′とＢ１との画素毎の差分（残差信号）を取る。そして、参照画像２の上のＢ１′の位置を数画素ないしは１／ｍ画素単位にずらしながら、逐次に残差信号を収集していき、残差信号が最小となったときのＢ１′（図ではＢ１″）とＢ１との相対的なズレの大きさ及びズレの方向をベクトル量３（動きベクトル）で検出する。これを、他のブロック（Ｂ２〜Ｂ２５）についても同様に繰り返すことにより、最終的に、すべてのブロック（Ｂ１〜Ｂ２５）の動きベクトルと残差信号とを得ることができる。復号側には、それらの動きベクトルと残差信号を各ブロック（Ｂ１〜Ｂ２５）に格納した被符号化画像４を送出する。
【０００８】
復号側では、送られてきた被符号化画像４のＢ１〜Ｂ２５の各動きベクトルを用いて、対象となる参照画像に相当する復元画像のブロックを選択し、そのブロックとＢ１〜Ｂ２５の各残差信号を画素毎に加算して、Ｂ１〜Ｂ２５を再現し、元画像と同じ復元画像を再構成する。
【０００９】
ここで、ブロックサイズを小さくすると、よりきめ細かな動き予測を行うことができることから、初期の動画像符号化方式（ＭＰＥＧ−２：Moving Picture Experts Group ）では「１６×１６」の一種類しかなかったブロックサイズが、その上位バージョン（ＭＰＥＧ−４）では「１６×１６」と「８×８」の二種類となり、さらに、最新バージョン（ＭＰＥＧ−４／ＡＶＣ又はＨ．２６４／ＡＶＣ）では「１６×１６」、「１６×８」、「８×１６」、「８×８」、「８×４」、「４×８」、「４×４」の７種類になった。
【００１０】
これにより、小さなブロックを選択して動き予測の精度を高めることができるようになった。反面、小さなブロックは、符号化処理量の増加を招き、伝送情報量や処理のオーバヘッド及び電力消費を大きくすることから、とりわけ動きの少ない画像に用いて不適切であり、動きの量に対応した適切な大きさのブロックを選択できる技術が求められている。
【００１１】
動きの量に対応した適切な大きさのブロックを選択できる従来技術としては、たとえば、１６×１６動きベクトル検出部と、８×８動きベクトル検出部と、それらの二つの動き検出部で得られた動き補償予測結果のうちのどちらか一方を選択するベクトル選択部とを備えたものが知られている（たとえば、特許文献２参照）。
【００１２】
これによれば、１６×１６ブロックと、そのブロックを４分割した８×８ブロックのそれぞれで得られた動き補償予測結果のうち適切な方を選択できる。このため、動きが少ない場合には大きなサイズの「１６×１６ブロック」を選択して伝送情報量の削減と電力消費の抑制及び処理のオーバヘッドの軽減を図り、一方、動きが大きい場合には小さなサイズの「８×８ブロック」を選択してよりきめ細かな動き予測を図ることができる。
【００１３】
【特許文献１】特表２００３−５３３１４２号公報
【特許文献２】特開２０００−１０２０１６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、上記の従来技術にあっては、「１６×１６ブロック」と、そのブロックを４分割した「８×８ブロック」のそれぞれで動き補償予測を行っているため、たとえば、「全探索法」で予測を行った場合、トータルの演算量は、１６×１６ブロック１個分の演算量のほぼ２倍にも達する。これは、ブロックの面積に比例して演算量が増えるため、８×８ブロック４個分の演算量は、１６×１６ブロック１個分の演算量にほぼ匹敵するからである。
【００１５】
なお、このこと（演算量が２倍に増える）は「全探索法」よりも演算量が少ない他の探索法（最近傍探索法など）を用いた場合でも同じである。たとえば、最近傍探索法を行ったときの１６×１６ブロック１個分の演算量をＡとするとき（このＡは全探索法よりも少ないが）、同様に最近傍探索を行った８×８ブロック４個分の演算量もほぼＡと同等になるため、トータルの演算量が、やはり２倍（≒２Ａ）になるからである。
【００１６】
そこで、本発明の目的は、トータルの演算量を減らしつつ、最適なブロックサイズの選択を可能とする動き補償予測符号化装置及び動き補償予測符号化方法を提供することにある。
【課題を解決するための手段】
【００１７】
請求項１記載の発明は、第一ブロックと該第一ブロックを複数に分割した第二ブロックのいずれか一方を動き補償予測ブロックとして選択するブロック選択手段を備えた動き補償予測符号化装置において、前記ブロック選択手段は、前記複数の第二ブロックの各々の動きベクトルを予め定められた反復数以下の少ない反復で所定の探索アルゴリズムにより演算する第一動きベクトル演算手段と、前記第一動きベクトル演算手段で演算された第二ブロックの各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第一判定手段とを含み、前記第一判定手段の判定結果が肯定の場合に前記第一ブロックを動き補償予測ブロックとして選択する一方、前記第一判定手段の判定結果が否定の場合に前記第二ブロックを動き補償予測ブロックとして選択することを特徴とする動き補償予測符号化装置である。
この発明では、予め定められた反復数以下の少ない反復で所定の探索アルゴリズムを用いて複数の第二ブロックの各々の動きベクトルを演算し、それらの動きベクトルが完全等価又は近似等価である場合に、第一ブロックを動き補償予測ブロックとして選択する一方、それらの動きベクトルが完全等価又は近似等価でない場合に第二ブロックを動き補償予測ブロックとして選択する。ここで、第一ブロックを複数に分割したものが第二ブロックであるから、第一ブロックは「大きい動き補償予測ブロック」であり、第二ブロックは「小さい動き補償予測ブロック」である。
そして、複数の第二ブロック（小さい動き補償予測ブロック）の各々の動きベクトルが揃っている（完全等価又は近似等価している）ということは、各々の画像が同一方向且つ同一量に動いているということであり、これは、第一ブロック（大きい動き補償予測ブロック）の画像の動きを表すから、この場合は、演算量削減を意図として大きい動き補償予測ブロック、つまり、第一ブロックを選択する。
これに対して、複数の第二ブロック（小さい動き補償予測ブロック）の各々の動きベクトルが揃っていない（完全等価又は近似等価していない）場合は、各々の画像がバラバラに動いているということであり、この場合には、きめ細かな動きベクトルを検出するために、小さな動き補償予測ブロック、つまり、第二ブロックを選択する。
この発明の“ブロック選択”に要する時間は、もっぱら、複数の第二ブロックの各々の動きベクトルの演算時間で与えられるが、この演算は、探索アルゴリズムの“予め定められた反復数以下の少ない反復”で行われるため、探索アルゴリズムを予め定められた反復数で行った場合に比べて明らかに短い時間で済む。
したがって、トータルの演算量を減らしつつ、最適なブロックサイズの選択を可能とする動き補償予測符号化装置を提供できる。
請求項２記載の発明は、第一ブロックと該第一ブロックを複数に分割した第二ブロックのいずれか一方を動き補償予測ブロックとして選択するブロック選択手段を備えた動き補償予測符号化装置において、前記ブロック選択手段は、前記複数の第二ブロックの各々の動きベクトルを予め定められた第１の反復数以下の少ない反復で所定の探索アルゴリズムにより演算する第一動きベクトル演算手段と、前記第一動きベクトル演算手段で演算された第二ブロックの各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第一判定手段と、前記第一判定手段の判定結果が肯定の場合に前記第一ブロックを動き補償予測ブロックとして選択する第一選択手段と、前記第一判定手段の判定結果が肯定の場合に前記第一ブロックの動きベクトルを予め定められた第２の反復数を上限にして所定の探索アルゴリズムにより演算する第二動きベクトル演算手段と、前記第一判定手段の判定結果が否定の場合に前記複数の第二ブロックの各々の動きベクトルを予め定められた第３の反復数を上限にして所定の探索アルゴリズムにより演算する第三動きベクトル演算手段と、前記第三動きベクトル演算手段で演算された第二ブロックの各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第二判定手段と、前記第二判定手段の判定結果が肯定の場合に前記第一ブロックを動き補償予測ブロックとして選択する一方、前記第二判定手段の判定結果が否定の場合に前記第二ブロックを動き補償予測ブロックとして選択する第二選択手段とを備えたことを特徴とする動き補償予測符号化装置である。
この発明では、請求項１の発明に加えて、複数の第二ブロックの各々の動きベクトルが揃っていない（完全等価又は近似等価していない）場合には、第二ブロックの各々の動きベクトルを再探索する。この再探索は、予め定められた第３の反復数を上限にした所定の探索アルゴリズムの正確な演算で行われるので、第一動きベクトル演算手段の演算結果に比べて精度が高い。
このため、仮に、第二判定手段で逆の判定結果（等価）が得られた場合には、第一判定手段の判定結果が間違っていると判断して、大きい動き補償予測ブロック、つまり、第一ブロックを選択し、また、第二判定手段で同じ判定結果（等価でない）が得られた場合には、第一判定手段の判定結果が正しかったと判断して、小さい動き補償予測ブロック、つまり、第二ブロックを選択する。
したがって、仮に、第一判定手段の判定結果に誤りがあった場合でも、正しいブロック選択を行うことができ、実用上好ましいものとすることができる。
請求項３記載の発明は、前記所定の探索アルゴリズムは、最近傍探索法又はＮステップ探索法若しくは対数探索法であることを特徴とする請求項１又は請求項２記載の動き補償予測符号化装置である。
請求項４記載の発明は、前記第二動きベクトル演算手段及び前記第三動きベクトル演算手段は、前記第一動きベクトル演算手段の反復がｎ′回のとき、ｎ′＋１回から反復を開始するとともに、その反復の初期値として、前記第一動きベクトル演算手段のｎ′反復で得られた中間値を使用することを特徴とする請求項２記載の動き補償予測符号化装置である。
この発明では、前記第一動きベクトル演算手段の演算で得られた中間値を、前記第二動きベクトル演算手段及び前記第三動きベクトル演算手段で流用するため、それらの第二動きベクトル演算手段及び第三動きベクトル演算手段の反復を少なくして、処理量の削減が図られる。
請求項５記載の発明は、第一ブロックと該第一ブロックを複数に分割した第二ブロックのいずれか一方を動き補償予測ブロックとして選択する際に、前記複数の第二ブロックの各々の動きベクトルを予め定められた反復数以下の少ない反復で所定の探索アルゴリズムにより演算する第一動きベクトル演算工程と、前記第一動きベクトル演算工程で演算された第二ブロックの各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第一判定工程と、前記第一判定工程の判定結果が肯定の場合に前記第一ブロックを動き補償予測ブロックとして選択する一方、前記第一判定工程の判定結果が否定の場合に前記第二ブロックを動き補償予測ブロックとして選択する選択工程とを実行することを特徴とする動き補償予測符号化方法である。
請求項６記載の発明は、第一ブロックと該第一ブロックを複数に分割した第二ブロックのいずれか一方を動き補償予測ブロックとして選択する際に、前記複数の第二ブロックの各々の動きベクトルを予め定められた第１の反復数以下の少ない反復で所定の探索アルゴリズムにより演算する第一動きベクトル演算工程と、前記第一動きベクトル演算工程で演算された第二ブロックの各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第一判定工程と、前記第一判定工程の判定結果が肯定の場合に前記第一ブロックを動き補償予測ブロックとして選択する第一選択工程と、前記第一判定工程の判定結果が肯定の場合に前記第一ブロックの動きベクトルを予め定められた第２の反復数を上限にして所定の探索アルゴリズムにより演算する第二動きベクトル演算工程と、前記第一判定工程の判定結果が否定の場合に前記複数の第二ブロックの各々の動きベクトルを予め定められた第３の反復数を上限にして所定の探索アルゴリズムにより演算する第三動きベクトル演算工程と、前記第三動きベクトル演算工程で演算された第二ブロックの各々の動きベクトルが完全等価又は近似等価であるか否かを判定する第二判定工程と、前記第二判定工程の判定結果が肯定の場合に前記第一ブロックを動き補償予測ブロックとして選択する一方、前記第二判定工程の判定結果が否定の場合に前記第二ブロックを動き補償予測ブロックとして選択する第二選択工程とを実行することを特徴とする動き補償予測符号化方法である。
請求項７記載の発明は、前記所定の探索アルゴリズムは、最近傍探索法又はＮステップ探索法若しくは対数探索法であることを特徴とする請求項４又は請求項５記載の動き補償予測符号化方法である。
請求項８記載の発明は、前記第二動きベクトル演算工程及び前記第三動きベクトル演算工程は、前記第一動きベクトル演算工程の反復がｎ′回のとき、ｎ′＋１回から反復を開始するとともに、その反復の初期値として、前記第一動きベクトル演算工程のｎ′反復で得られた中間値を使用することを特徴とする請求項６記載の動き補償予測符号化方法である。
【発明の効果】
【００１８】
本発明によれば、“ブロック選択”に要する時間が、もっぱら、複数の第二ブロックの各々の動きベクトルの演算時間で与えられる。この演算は、「予め定められた反復数以下の少ない反復」で行われるため、探索アルゴリズムを予め定められた反復数で行った場合に比べて明らかに短い時間で済む。
したがって、トータルの演算量を減らしつつ、最適なブロックサイズの選択を可能とする動き補償予測符号化装置を提供できる。
また、他の発明によれば、第一判定手段の誤判定をバックアップして、正しいブロック選択を行うことができ、実用上好ましいものとすることができる。
また、他の発明によれば、前記第一動きベクトル演算手段の演算で得られた中間値を、前記第二動きベクトル演算手段及び前記第三動きベクトル演算手段で流用するので、それらの第二動きベクトル演算手段及び第三動きベクトル演算手段の反復を少なくすることができ、処理量の削減を図ることができる。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の実施形態を、図面を参照しながら説明する。なお、以下の説明における様々な細部の特定ないし実例および数値や文字列その他の記号の例示は、本発明の思想を明瞭にするための、あくまでも参考であって、それらのすべてまたは一部によって本発明の思想が限定されないことは明らかである。また、周知の手法、周知の手順、周知のアーキテクチャおよび周知の回路構成等（以下「周知事項」）についてはその細部にわたる説明を避けるが、これも説明を簡潔にするためであって、これら周知事項のすべてまたは一部を意図的に排除するものではない。かかる周知事項は本発明の出願時点で当業者の知り得るところであるので、以下の説明に当然含まれている。
【００２０】
＜動き補償予測ブロック＞
まず、動き補償予測ブロックについて説明する。
図１は、動き補償予測ブロックの種類を示す図である。（ａ）〜（ｈ）は、それぞれＭＰＥＧ−４／ＡＶＣ（又はＨ．２６４／ＡＶＣ）で使用が認められている７種類の動き補償予測ブロックである。詳しくは、（ａ）は「１６×１６」のサイズの動き補償予測ブロック、（ｂ）は「１６×１６」の動き補償予測ブロックを上下に２分割したそれぞれ「１６×８」のサイズの動き補償予測ブロック、（ｃ）は同じく「１６×１６」の動き補償予測ブロックを左右に２分割したそれぞれ「８×１６」のサイズの動き補償予測ブロック、（ｄ）は同じく「１６×１６」の動き補償予測ブロックを上下左右に４分割したそれぞれ「８×８」のサイズの動き補償予測ブロックである。
【００２１】
また、（ｅ）は「８×８」の動き補償予測ブロック、（ｆ）は「８×８」の動き補償予測ブロックを上下に２分割したそれぞれ「８×４」のサイズの動き補償予測ブロック、（ｇ）は同じく「８×８」の動き補償予測ブロックを左右に２分割したそれぞれ「４×８」のサイズの動き補償予測ブロック、（ｈ）は同じく「８×８」の動き補償予測ブロックを上下左右に４分割したそれぞれ「４×４」のサイズの動き補償予測ブロックである。
【００２２】
動き補償予測ブロックの選択は、（ａ）〜（ｄ）のグループの中で行われる。すなわち、最大サイズの「１６×１６」、最大サイズを上下に２分割した「１６×８」、最大サイズを左右に２分割した「８×１６」、及び、最大サイズを上下左右に４分割した「８×８」の中から選ばれる。また、選択された動き補償予測ブロックが（ｄ）（「１６×１６」を上下左右に４分割した「８×８」）である場合は、それぞれの「８×８」ブロック毎に、さらに（ｅ）〜（ｈ）のグループの中から選択できるように階層化されている。
【００２３】
なお、一般的に（ａ）の動き補償予測ブロック（「１６×１６」）は「マクロブロック」、（ｂ）〜（ｈ）の分割された動き補償予測ブロックは「サブブロック」と呼ばれる。
【００２４】
このように、動き補償予測ブロックの種類は多く、ブロック選択の組み合わせも多岐にわたるため、本実施形態では説明の簡単化のために、「１６×１６」の動き補償予測ブロック（ａ）と、それを四分割した大きさの「８×８」の動き補償予測ブロック（ｄ）を選択するものとする。
【００２５】
図２は、本実施形態の便宜的な選択対象となる二つの動き補償予測ブロックを示す図である。この図においては、「１６×１６」の動き補償予測ブロックと、それを四分割した大きさの「８×８」の動き補償予測ブロックが例示されている。以下、上記の一般呼称に倣って、「１６×１６」の動き補償予測ブロックを「マクロブロック（略号：ＭＢ）」といい、それを四分割した大きさの「８×８」の動き補償予測ブロックを「サブブロック（略号：ＳＢ）」ということにする。但し、これは、両者のブロックを区別するための、あくまでも説明上の便宜であって、これらの呼び名（マクロ・・・・、サブ・・・・）から発明の外縁を把握してはならない。また、４個のＳＢの各々に左上から順に添え字０、１，２，３を付けて識別することにする。すなわち、左上のＳＢをＳＢ0 、右上のＳＢをＳＢ1 、左下のＳＢをＳＢ2 、右下のＳＢをＳＢ3 として識別することにする。
【００２６】
＜動き補償予測符号化装置の構成＞
次に、動き補償予測符号化装置の構成を説明する。
【００２７】
図３は、動き補償予測符号化装置のブロック図である。動き補償予測符号化装置１０は、入力されたビットストリーム中の現フレーム（元画像）と予測画像との差分をとる減算部１１と、その差分を何らかの２次元関数の有限級数変換式（たとえば、２次元離散コサイン変換：ＤＣＴ）として表示することにより圧縮する変換部１２と、変換式の係数を量子化する量子化部１３と、この量子化データと後述の動き情報及び分割モードとを符号化（たとえば、エントロピー符号化）して、その符号化ビットストリームを伝送媒体や蓄積媒体に出力する符号化部１４と、量子化データを逆量子化する逆量子化部１５と、逆量子化されたデータを逆変換して元の差分に戻す逆変換部１６と、この差分と予測画像とを加算して復元画像を再生する加算部１７と、復元画像を保持する復元画像メモリ１８と、現在の元画像と復元画像メモリ１８に保持されている一つ前の復元画像（参照画像）とに基づいて動き情報（動きベクトル等）やブロックの分割モードを推定する動き推定部１９（ブロック選択手段）と、この動き情報に基づいて予測画像を生成する動き補償部２０とを備える。
【００２８】
＜動き推定部の構成と動作＞
図４は、動き推定部１９の概念的なブロック図である。動き推定部１９は、推定動きベクトル演算部２１（第一動きベクトル演算手段）、第一判定部２２（第一判定手段）、ＭＢ（マクロブロック）探索部２３（第二動きベクトル演算手段）、第一ＭＢ動きベクトル出力部２４（第一選択手段）、ＳＢ（サブブロック）探索部２５（第三動きベクトル演算手段）、第二判定部２６（第二判定手段）、第二ＭＢ動きベクトル出力部２７（第二選択手段）、ＳＢ動きベクトル出力部２８（第二選択手段）を備える。
【００２９】
推定動きベクトル演算部２１は、ＳＢ0 〜ＳＢ3 （図２参照）の各々について、探索アルゴリズム（たとえば、最近傍探索法などの高速探索アルゴリズム）の第１反復（発明の要旨に記載の「予め定められた反復数又は予め定められた第１の反復数以下の少ない反復」に相当）だけを行って、ＳＢ0 〜ＳＢ3 の大まかな推定動きベクトルｆｖ0 〜ｆｖ3 を演算出力する。この演算に関する詳細は、後述の推定動きベクトル演算処理（図１０及び図１１参照）で説明する。
【００３０】
第一判定部２２は、推定動きベクトルｆｖ0 〜ｆｖ3 の等価（ｆｖ0 ＝ｆｖ1 ＝ｆｖ2 ＝ｆｖ3 ）を判定し、等価であれば、ＭＢ探索部２３を起動し、等価でなければ、ＳＢ探索部２５を起動する。
【００３１】
ＭＢ探索部２３は、推定動きベクトルｆｖ0 〜ｆｖ3 が等価（ｆｖ0 ＝ｆｖ1 ＝ｆｖ2 ＝ｆｖ3 ）の場合に、１６×１６分割モードを出力するとともに、たとえば、最近傍探索法などによりＭＢの動きベクトルｍｖを求め、その動きベクトルｍｖを、第一ＭＢ動きベクトル出力部２４を介して出力する。
【００３２】
ＳＢ探索部２５は、推定動きベクトルｆｖ0 〜ｆｖ3 が等価（ｆｖ0 ＝ｆｖ1 ＝ｆｖ2 ＝ｆｖ3 ）でない場合に、たとえば、最近傍探索法などによりＳＢ0 、ＳＢ1 、ＳＢ2 及びＳＢ3 のそれぞれの動きベクトルｍｖ0 、ｍｖ1 、ｍｖ2 、ｍｖ3 を求める。
【００３３】
第二判定部２６は、ＳＢ0 、ＳＢ1 、ＳＢ2 及びＳＢ3 のそれぞれの動きベクトルｍｖ0 、ｍｖ1 、ｍｖ2 、ｍｖ3 の等価（ｍｖ0 ＝ｍｖ1 ＝ｍｖ2 ＝ｍｖ3 ）を判定し、等価であれば、第二ＭＢ動きベクトル出力部２７を介して１６×１６分割モードと一つの動きベクトル（ｍｖ0 ）を出力する一方、等価でなければ、ＳＢ動きベクトル出力部２８を介して、８×８分割モードと四つの動きベクトル（ｍｖ0 、ｍｖ1 、ｍｖ2 、ｍｖ3 ）を出力する。
【００３４】
図５及び図６は、動き推定部１９の動作を説明するための概念図である。まず、図５に示すように、推定動きベクトル演算部２１で計算された４つのサブブロック（ＳＢ0 、ＳＢ1 、ＳＢ2 、ＳＢ3 ）の推定動きベクトル（ｆｖ0 、ｆｖ1 、ｆｖ2 、ｆｖ3 ）が等価である場合は、それらの４つのサブブロックに対応するマクロブロック（ＭＢ）の動きベクトル（ｍｖ）も高い蓋然性でほぼ同じになる。つまり、４つのサブブロックの推定動きベクトル（ｆｖ0 、ｆｖ1 、ｆｖ2 、ｆｖ3 ）が等価である（揃っている）ということは、それらの４つのサブブロック内の各画像が同一方向に且つ同一量だけ動いているということであり、これは、すなわち、それらの４つのサブブロックに対応するマクロブロック（ＭＢ）の画像の動きを表しているからである。ゆえに、この場合は、演算量の削減及び消費電力の抑制並びに処理のオーバヘッドを減らす観点から、大きい分割モード（たとえば、「１６×１６」）を選択（第一ＭＢ動きベクトル出力部２４）する。
【００３５】
一方、図６に示すように、推定動きベクトル演算部２１で計算された４つのサブブロック（ＳＢ0 、ＳＢ1 、ＳＢ2 、ＳＢ3 ）の推定動きベクトル（ｆｖ0 、ｆｖ1 、ｆｖ2 、ｆｖ3 ）が等価でない場合（不揃いの場合）は、それらの４つのサブブロック内の各画像がバラバラに動いていることを示唆する。但し、この示唆は正しくないかも知れない。推定動きベクトル（ｆｖ0 、ｆｖ1 、ｆｖ2 、ｆｖ3 ）は１反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）だけのあくまでも“推定値”であって、完全なものではないからである。最終判断は、ＳＢ探索部２５で４つのサブブロック（ＳＢ0 、ＳＢ1 、ＳＢ2 、ＳＢ3 ）の正確な動きベクトル（ｍｖ0 、ｍｖ1 、ｍｖ2 、ｍｖ3 ）を求め、第二判定部２６でそれらの等価（ｍｖ0 ＝ｍｖ1 ＝ｍｖ2 ＝ｍｖ3 ）を判定して行う。そして、その最終判断でも、やはり等価でなければ、上記の“示唆”は正しかったから、サブブロック毎の正確な動きを検出するために、小さな分割モード（たとえば、４つの「８×８」）を選択（ＳＢ動きベクトル出力部２８）する。一方、第二判定部２６の判定結果が“等価でない”場合は、上記の“示唆”は誤りであると判断し、演算量の削減等を意図して大きい分割モード（たとえば、「１６×１６」）を選択（第二ＭＢ動きベクトル出力部２７）する。
【００３６】
＜動き推定部の詳細動作＞
次に、上記の動き推定部１９の動作をより詳しく説明する。なお、ここではフローチャートの形で説明するが、これには二つの意味合いがある。第一の意味は、フローに沿って順番に動作説明を行うことにより理解を助ける点にあり、第二の意味は、上記の動き推定部１９のそれぞれの機能をハードロジックで構成する実施態様だけでなく、このようなフローチャートの流れに沿って設計されたソフトウェアとコンピュータとの有機的結合によって実現される実施態様も排除しない点にある。
【００３７】
まず、フローチャートで用いられる用語等について説明する。
図７は、元画像のブロック位置（座標）とブロックサイズを説明する図である。この図において、元画像２９の升目３０のそれぞれはブロック（ＭＢ又はＳＢ）であり、それらのブロック位置は、たとえば、その升目３０の左上隅の画素座標（ｘ，ｙ）で表されるものとする。また、ブロックサイズは横方向（行方向）をｓｘ、縦方向（列方向）をｓｙとして表されるものとする。
【００３８】
図８は、参照画像に与えるオフセットを示す図である。この図において、参照画像３１の上のブロック３２のオフセットは（ｏｘ，ｏｙ）で表されるものとする。
【００３９】
＜動き推定部の動作フロー＞
図９は、動き推定部１９の動作フローチャートを示す図である。このフローチャートを開始すると、まず、ＳＢ0 〜ＳＢ3 （図２参照）の各々について、探索アルゴリズム（たとえば、最近傍探索法などの高速探索アルゴリズム）の第１反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）だけを行って、ＳＢ0 〜ＳＢ3 の大まかな推定動きベクトルｆｖ0 〜ｆｖ3 を演算出力する推定動きベクトル演算処理（ステップＳ１０：第一動きベクトル演算工程）を実行する。次いで、式「ｆｖ0 ＝ｆｖ1 ＝ｆｖ2 ＝ｆｖ3 」を評価（ステップＳ１１：第一判定工程）して、その評価結果が“Ｔｒｕｅ”であるか否かを判定する（ステップＳ１２）。そして、その判定結果が“Ｔｒｕｅ”であれば、次に、ＭＢ探索処理（ステップＳ１３：第二動きベクトル演算工程）を実行し、そのＭＢ探索処理で得られたＭＢ動きベクトル（ｍｖ）と大きい分割モード（たとえば、「１６×１６」）とを出力（ステップＳ１４：選択工程、第一選択工程）した後、フローチャートを終了する。
【００４０】
一方、ステップＳ１２の判定結果が“Ｔｒｕｅ”でなければ、ＳＢ探索処理（ステップＳ１５：第三動きベクトル演算工程）を実行し、式「ｍｖ0 ＝ｍｖ1 ＝ｍｖ2 ＝ｍｖ3 」を評価（ステップＳ１６：第二判定工程）して、その評価結果が“Ｔｒｕｅ”であるか否かを判定する（ステップＳ１７）。そして、その判定結果が“Ｔｒｕｅ”であれば、次に、ＭＢ動きベクトル（ｍｖ0 ）と大きい分割モード（たとえば、「１６×１６」）とを出力（ステップＳ１８：選択工程、第二選択工程）してフローチャートを終了し、その判定結果が“Ｔｒｕｅ”でなければ、ＳＢ動きベクトル（ｍｖ0 〜ｍｖ3 ）と小さい分割モード（たとえば、「８×８」）とを出力（ステップＳ１９：選択工程、第二選択工程）してフローチャートを終了する。
【００４１】
＜推定動きベクトル演算処理＞
図１０及び図１１は、推定動きベクトル演算処理の動作フローチャートを示す図である。このフローチャートを開始すると、まず、ブロックサイズ変数ｓｘ、ｓｙとループ変数ｉにそれぞれ初期値をセットする（ステップＳ２０）。ｉの初期値は“０”、ｓｘとｓｙの初期値はＳＢの横サイズと縦サイズに相当する“８”である。
【００４２】
初回（ｉ＝０）：
まず、ｉ＝０を判定し（ステップＳ２１）、ｘ＝Ｘ、ｙ＝Ｙをセットする（ステップＳ２２）。Ｘ及びＹはＳＢ0 の位置座標を表している。したがって、この回（ｉ＝０）では、図２の左上のサブブロック（ＳＢ0 ）を対象にした処理が行われる。
【００４３】
次に、ＳＡＤ関数を用いて、探索中心（ｘ0 ，ｙ0 ）の残差評価値Ａ、探索中心（ｘ0 ，ｙ0 ）の１画素右（ｘ0 ＋１、ｙ0 ）の残差評価値Ｂ、探索中心（ｘ0 ，ｙ0 ）の１画素左（ｘ0 −１、ｙ0 ）の残差評価値Ｃ、探索中心（ｘ0 ，ｙ0 ）の１画素上（ｘ0 、ｙ0 ＋１）の残差評価値Ｄ、及び、探索中心（ｘ0 ，ｙ0 ）の１画素下（ｘ0 、ｙ0 −１）の残差評価値Ｅを演算する（ステップＳ２３〜ステップＳ２７）。ＳＡＤ関数とは、差分絶対値和（sum of absolute difference）を計算するための関数である。
【００４４】
なお、探索中心のオフセット（ｘ0 ，ｙ0 ）は、ゼロベクトルとしてもよいし、何らかの方法（たとえば、Ｈ．２６４に定められているメディアン予測）によって与えられた予測ベクトルとしてもよい。
【００４５】
ＳＡＤ関数は、残差評価値Ａ〜Ｅごとに計算される。すなわち、
Ａ＝ＳＡＤ（ｘ，ｙ，ｘ0 、ｙ0 ，ｓｘ，ｓｙ）
Ｂ＝ＳＡＤ（ｘ，ｙ，ｘ0 ＋１、ｙ0 ，ｓｘ，ｓｙ）
Ｃ＝ＳＡＤ（ｘ，ｙ，ｘ0 −１、ｙ0 ，ｓｘ，ｓｙ）
Ｄ＝ＳＡＤ（ｘ，ｙ，ｘ0 、ｙ0 ＋１，ｓｘ，ｓｙ）
Ｅ＝ＳＡＤ（ｘ，ｙ，ｘ0 、ｙ0 −１，ｓｘ，ｓｙ）
の５回計算される。
【００４６】
今、ｘ＝Ｘ、ｙ＝Ｙ、ｓｘ＝８、ｓｙ＝８であるから、
Ａ＝ＳＡＤ（Ｘ，Ｙ，ｘ0 、ｙ0 ，８，８）
Ｂ＝ＳＡＤ（Ｘ，Ｙ，ｘ0 ＋１、ｙ0 ，８，８）
Ｃ＝ＳＡＤ（Ｘ，Ｙ，ｘ0 −１、ｙ0 ，８，８）
Ｄ＝ＳＡＤ（Ｘ，Ｙ，ｘ0 、ｙ0 ＋１，８，８）
Ｅ＝ＳＡＤ（Ｘ，Ｙ，ｘ0 、ｙ0 −１，８，８）
となる。これらの式は、たとえば、最近傍探索法などの高速探索アルゴリズムの１反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）分に相当する。
【００４７】
次に、Ｍｉｎ関数を用いて、Ａ、Ｂ、Ｃ、Ｄ、Ｅの最小値を取り出し（ステップＳ２８）、その最小値を変数ＳＡＤｍｉｎに格納する。
【００４８】
次に、ＳＡＤｍｉｎに格納されている最小値がＡ〜Ｅのいずれであるかを判定する（ステップＳ２９〜ステップＳ３２）。そして、ＳＡＤｍｉｎ＝Ａであれば、ｆｖ（ｉ）に（０，０）をセットし（ステップＳ３３）、ＳＡＤｍｉｎ＝Ｂであれば、ｆｖ（ｉ）に（１，０）をセットし（ステップＳ３４）、ＳＡＤｍｉｎ＝Ｃであれば、ｆｖ（ｉ）に（−１，０）をセットし（ステップＳ３５）、ＳＡＤｍｉｎ＝Ｄであれば、ｆｖ（ｉ）に（０，１）をセットし（ステップＳ３６）、ＳＡＤｍｉｎ＝Ｅであれば、ｆｖ（ｉ）に（０，−０）をセットする（ステップＳ３７）。
【００４９】
今、ｉ＝０であるから、このｆｖ（ｉ）はｆｖ0 である。したがって、この段階で、図２の左上のサブブロック（ＳＢ0 ）の推定動きベクトルｆｖ0 が得られる。この推定動きベクトルｆｖ0 は、最近傍探索法などの高速探索アルゴリズムの１反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）分に相当する演算を行って得られたものであり、同アルゴリズムを最大反復（予め定められた反復数又は予め定められた第１の反復数）回行って得られた値と比べて精度は劣るが、大凡の動きベクトルの傾向を把握する（推定する）値として差し支えないものである。
【００５０】
第一回目のループ（ｉ＝１）：
次に、ループ変数ｉを＋１し（ステップＳ３８）、ｉ＞３であるか否かを判定する（ステップＳ２９）。今、ｉ＝１であるからループし、ｉ＝１を判定して（ステップＳ４０）、ｘ＝Ｘ＋８、ｙ＝Ｙをセットする（ステップＳ４１）。Ｘ＋８及びＹはＳＢ1 の位置座標を表している。したがって、この回（ｉ＝１）では、図２の右上のサブブロック（ＳＢ1 ）を対象にした処理が行われる。
【００５１】
次に、ＳＡＤ関数を用いて、探索中心（ｘ0 ，ｙ0 ）の残差評価値Ａ、探索中心（ｘ0 ，ｙ0 ）の１画素右（ｘ0 ＋１、ｙ0 ）の残差評価値Ｂ、探索中心（ｘ0 ，ｙ0 ）の１画素左（ｘ0 −１、ｙ0 ）の残差評価値Ｃ、探索中心（ｘ0 ，ｙ0 ）の１画素上（ｘ0 、ｙ0 ＋１）の残差評価値Ｄ、及び、探索中心（ｘ0 ，ｙ0 ）の１画素下（ｘ0 、ｙ0 −１）の残差評価値Ｅを演算する（ステップＳ２３〜ステップＳ２７）。
【００５２】
初回と同様に、ＳＡＤ関数は、残差評価値Ａ〜Ｅごとに計算される。すなわち、
Ａ＝ＳＡＤ（ｘ，ｙ，ｘ0 、ｙ0 ，ｓｘ，ｓｙ）
Ｂ＝ＳＡＤ（ｘ，ｙ，ｘ0 ＋１、ｙ0 ，ｓｘ，ｓｙ）
Ｃ＝ＳＡＤ（ｘ，ｙ，ｘ0 −１、ｙ0 ，ｓｘ，ｓｙ）
Ｄ＝ＳＡＤ（ｘ，ｙ，ｘ0 、ｙ0 ＋１，ｓｘ，ｓｙ）
Ｅ＝ＳＡＤ（ｘ，ｙ，ｘ0 、ｙ0 −１，ｓｘ，ｓｙ）
の５回計算される。
【００５３】
今、ｘ＝Ｘ＋８、ｙ＝Ｙ、ｓｘ＝８、ｓｙ＝８であるから、
Ａ＝ＳＡＤ（Ｘ＋８，Ｙ，ｘ0 、ｙ0 ，８，８）
Ｂ＝ＳＡＤ（Ｘ＋８，Ｙ，ｘ0 ＋１、ｙ0 ，８，８）
Ｃ＝ＳＡＤ（Ｘ＋８，Ｙ，ｘ0 −１、ｙ0 ，８，８）
Ｄ＝ＳＡＤ（Ｘ＋８，Ｙ，ｘ0 、ｙ0 ＋１，８，８）
Ｅ＝ＳＡＤ（Ｘ＋８，Ｙ，ｘ0 、ｙ0 −１，８，８）
となる。これらの式は、たとえば、最近傍探索法などの高速探索アルゴリズムの１反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）分に相当する。
【００５４】
次に、Ｍｉｎ関数を用いて、Ａ、Ｂ、Ｃ、Ｄ、Ｅの最小値を取り出し（ステップＳ２８）、その最小値を変数ＳＡＤｍｉｎに格納する。
【００５５】
次に、ＳＡＤｍｉｎに格納されている最小値がＡ〜Ｅのいずれであるかを判定する（ステップＳ２９〜ステップＳ３２）。そして、ＳＡＤｍｉｎ＝Ａであれば、ｆｖ（ｉ）に（０，０）をセットし（ステップＳ３３）、ＳＡＤｍｉｎ＝Ｂであれば、ｆｖ（ｉ）に（１，０）をセットし（ステップＳ３４）、ＳＡＤｍｉｎ＝Ｃであれば、ｆｖ（ｉ）に（−１，０）をセットし（ステップＳ３５）、ＳＡＤｍｉｎ＝Ｄであれば、ｆｖ（ｉ）に（０，１）をセットし（ステップＳ３６）、ＳＡＤｍｉｎ＝Ｅであれば、ｆｖ（ｉ）に（０，−０）をセットする（ステップＳ３７）。
【００５６】
今、ｉ＝１であるから、このｆｖ（ｉ）はｆｖ1 である。したがって、この段階で、図２の右上のサブブロック（ＳＢ1 ）の推定動きベクトルｆｖ1 が得られる。この推定動きベクトルｆｖ1 も、上記の推定動きベクトルｆｖ0 と同様に、最近傍探索法などの高速探索アルゴリズムの１反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）分に相当する演算を行って得られたものであり、同アルゴリズムを最大反復（予め定められた反復数又は予め定められた第１の反復数）回行って得られた値と比べて精度は劣るが、大凡の動きベクトルの傾向を把握する（推定する）値として差し支えないものである。
【００５７】
第二回目のループ（ｉ＝２）：
次に、ループ変数ｉを＋１し（ステップＳ３８）、ｉ＞３であるか否かを判定する（ステップＳ２９）。今、ｉ＝２であるからループし、ｉ＝２を判定して（ステップＳ４２）、ｘ＝Ｘ、ｙ＝Ｙ＋８をセットする（ステップＳ４３）。Ｘ及びＹ＋８はＳＢ2 の位置座標を表している。したがって、この回（ｉ＝２）では、図２の左下のサブブロック（ＳＢ2 ）を対象にした処理が行われる。
【００５８】
次に、ＳＡＤ関数を用いて、探索中心（ｘ0 ，ｙ0 ）の残差評価値Ａ、探索中心（ｘ0 ，ｙ0 ）の１画素右（ｘ0 ＋１、ｙ0 ）の残差評価値Ｂ、探索中心（ｘ0 ，ｙ0 ）の１画素左（ｘ0 −１、ｙ0 ）の残差評価値Ｃ、探索中心（ｘ0 ，ｙ0 ）の１画素上（ｘ0 、ｙ0 ＋１）の残差評価値Ｄ、及び、探索中心（ｘ0 ，ｙ0 ）の１画素下（ｘ0 、ｙ0 −１）の残差評価値Ｅを演算する（ステップＳ２３〜ステップＳ２７）。
【００５９】
初回及び第一回のループと同様に、ＳＡＤ関数は、残差評価値Ａ〜Ｅごとに計算される。すなわち、
Ａ＝ＳＡＤ（ｘ，ｙ，ｘ0 、ｙ0 ，ｓｘ，ｓｙ）
Ｂ＝ＳＡＤ（ｘ，ｙ，ｘ0 ＋１、ｙ0 ，ｓｘ，ｓｙ）
Ｃ＝ＳＡＤ（ｘ，ｙ，ｘ0 −１、ｙ0 ，ｓｘ，ｓｙ）
Ｄ＝ＳＡＤ（ｘ，ｙ，ｘ0 、ｙ0 ＋１，ｓｘ，ｓｙ）
Ｅ＝ＳＡＤ（ｘ，ｙ，ｘ0 、ｙ0 −１，ｓｘ，ｓｙ）
の５回計算される。
【００６０】
今、ｘ＝Ｘ、ｙ＝Ｙ＋８、ｓｘ＝８、ｓｙ＝８であるから、
Ａ＝ＳＡＤ（Ｘ，Ｙ＋８，ｘ0 、ｙ0 ，８，８）
Ｂ＝ＳＡＤ（Ｘ，Ｙ＋８，ｘ0 ＋１、ｙ0 ，８，８）
Ｃ＝ＳＡＤ（Ｘ，Ｙ＋８，ｘ0 −１、ｙ0 ，８，８）
Ｄ＝ＳＡＤ（Ｘ，Ｙ＋８，ｘ0 、ｙ0 ＋１，８，８）
Ｅ＝ＳＡＤ（Ｘ，Ｙ＋８，ｘ0 、ｙ0 −１，８，８）
となる。これらの式は、たとえば、最近傍探索法などの高速探索アルゴリズムの１反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）分に相当する。
【００６１】
次に、Ｍｉｎ関数を用いて、Ａ、Ｂ、Ｃ、Ｄ、Ｅの最小値を取り出し（ステップＳ２８）、その最小値を変数ＳＡＤｍｉｎに格納する。
【００６２】
次に、ＳＡＤｍｉｎに格納されている最小値がＡ〜Ｅのいずれであるかを判定する（ステップＳ２９〜ステップＳ３２）。そして、ＳＡＤｍｉｎ＝Ａであれば、ｆｖ（ｉ）に（０，０）をセットし（ステップＳ３３）、ＳＡＤｍｉｎ＝Ｂであれば、ｆｖ（ｉ）に（１，０）をセットし（ステップＳ３４）、ＳＡＤｍｉｎ＝Ｃであれば、ｆｖ（ｉ）に（−１，０）をセットし（ステップＳ３５）、ＳＡＤｍｉｎ＝Ｄであれば、ｆｖ（ｉ）に（０，１）をセットし（ステップＳ３６）、ＳＡＤｍｉｎ＝Ｅであれば、ｆｖ（ｉ）に（０，−０）をセットする（ステップＳ３７）。
【００６３】
今、ｉ＝２であるから、このｆｖ（ｉ）はｆｖ2 である。したがって、この段階で、図２の左下のサブブロック（ＳＢ2 ）の推定動きベクトルｆｖ2 が得られる。この推定動きベクトルｆｖ2 も、上記の推定動きベクトルｆｖ0 、ｆｖ1 と同様に、最近傍探索法などの高速探索アルゴリズムの１反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）分に相当する演算を行って得られたものであり、同アルゴリズムを最大反復（予め定められた反復数又は予め定められた第１の反復数）回行って得られた値と比べて精度は劣るが、大凡の動きベクトルの傾向を把握する（推定する）値として差し支えないものである。
【００６４】
第三回目のループ（ｉ＝３）：
次に、ループ変数ｉを＋１し（ステップＳ３８）、ｉ＞３であるか否かを判定する（ステップＳ２９）。今、ｉ＝３であるからループし、ｉ＝３を判定して（ステップＳ４２の“ＮＯ”）、ｘ＝Ｘ＋８、ｙ＝Ｙ＋８をセットする（ステップＳ４４）。Ｘ＋８及びＹ＋８はＳＢ3 の座標を表す。したがって、この回（ｉ＝３）では、図２の左下のサブブロック（ＳＢ3 ）を対象にした処理が行われる。
【００６５】
次に、ＳＡＤ関数を用いて、探索中心（ｘ0 ，ｙ0 ）の残差評価値Ａ、探索中心（ｘ0 ，ｙ0 ）の１画素右（ｘ0 ＋１、ｙ0 ）の残差評価値Ｂ、探索中心（ｘ0 ，ｙ0 ）の１画素左（ｘ0 −１、ｙ0 ）の残差評価値Ｃ、探索中心（ｘ0 ，ｙ0 ）の１画素上（ｘ0 、ｙ0 ＋１）の残差評価値Ｄ、及び、探索中心（ｘ0 ，ｙ0 ）の１画素下（ｘ0 、ｙ0 −１）の残差評価値Ｅを演算する（ステップＳ２３〜ステップＳ２７）。
【００６６】
初回〜第二回のループと同様に、ＳＡＤ関数は、残差評価値Ａ〜Ｅごとに計算される。すなわち、
Ａ＝ＳＡＤ（ｘ，ｙ，ｘ0 、ｙ0 ，ｓｘ，ｓｙ）
Ｂ＝ＳＡＤ（ｘ，ｙ，ｘ0 ＋１、ｙ0 ，ｓｘ，ｓｙ）
Ｃ＝ＳＡＤ（ｘ，ｙ，ｘ0 −１、ｙ0 ，ｓｘ，ｓｙ）
Ｄ＝ＳＡＤ（ｘ，ｙ，ｘ0 、ｙ0 ＋１，ｓｘ，ｓｙ）
Ｅ＝ＳＡＤ（ｘ，ｙ，ｘ0 、ｙ0 −１，ｓｘ，ｓｙ）
の５回計算される。
【００６７】
今、ｘ＝Ｘ＋８、ｙ＝Ｙ＋８、ｓｘ＝８、ｓｙ＝８であるから、
Ａ＝ＳＡＤ（Ｘ＋８，Ｙ＋８，ｘ0 、ｙ0 ，８，８）
Ｂ＝ＳＡＤ（Ｘ＋８，Ｙ＋８，ｘ0 ＋１、ｙ0 ，８，８）
Ｃ＝ＳＡＤ（Ｘ＋８，Ｙ＋８，ｘ0 −１、ｙ0 ，８，８）
Ｄ＝ＳＡＤ（Ｘ＋８，Ｙ＋８，ｘ0 、ｙ0 ＋１，８，８）
Ｅ＝ＳＡＤ（Ｘ＋８，Ｙ＋８，ｘ0 、ｙ0 −１，８，８）
となる。これらの式は、たとえば、最近傍探索法などの高速探索アルゴリズムの１反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）分に相当する。
【００６８】
次に、Ｍｉｎ関数を用いて、Ａ、Ｂ、Ｃ、Ｄ、Ｅの最小値を取り出し（ステップＳ２８）、その最小値を変数ＳＡＤｍｉｎに格納する。
【００６９】
次に、ＳＡＤｍｉｎに格納されている最小値がＡ〜Ｅのいずれであるかを判定する（ステップＳ２９〜ステップＳ３２）。そして、ＳＡＤｍｉｎ＝Ａであれば、ｆｖ（ｉ）に（０，０）をセットし（ステップＳ３３）、ＳＡＤｍｉｎ＝Ｂであれば、ｆｖ（ｉ）に（１，０）をセットし（ステップＳ３４）、ＳＡＤｍｉｎ＝Ｃであれば、ｆｖ（ｉ）に（−１，０）をセットし（ステップＳ３５）、ＳＡＤｍｉｎ＝Ｄであれば、ｆｖ（ｉ）に（０，１）をセットし（ステップＳ３６）、ＳＡＤｍｉｎ＝Ｅであれば、ｆｖ（ｉ）に（０，−０）をセットする（ステップＳ３７）。
【００７０】
今、ｉ＝３であるから、このｆｖ（ｉ）はｆｖ3 である。したがって、この段階で、図２の右下のサブブロック（ＳＢ3 ）の推定動きベクトルｆｖ3 が得られる。この推定動きベクトルｆｖ3 も、上記の推定動きベクトルｆｖ0 、ｆｖ1 、ｆｖ2 と同様に、最近傍探索法などの高速探索アルゴリズムの１反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）分に相当する演算を行って得られたものであり、同アルゴリズムを最大反復（予め定められた反復数又は予め定められた第１の反復数）回行って得られた値と比べて精度は劣るが、大凡の動きベクトルの傾向を把握する（推定する）値として差し支えないものである。
【００７１】
次に、ループ変数ｉを＋１し（ステップＳ３８）、ｉ＞３であるか否かを判定するが（ステップＳ２９）、ｉ＝４であるので、ループを抜けてフローチャートを終了する。
【００７２】
この推定動きベクトル演算処理によれば、図２の４つのサブブロック（ＳＢ0 〜ＳＢ3 ）の各々の大まかな推定動きベクトルｆｖ0 〜ｆｖ3 が得られる。
【００７３】
すなわち、ＳＢ0 の探索中心（ｘ0 ，ｙ0 ）の残差評価値Ａ、探索中心（ｘ0 ，ｙ0 ）の１画素右（ｘ0 ＋１、ｙ0 ）の残差評価値Ｂ、探索中心（ｘ0 ，ｙ0 ）の１画素左（ｘ0 −１、ｙ0 ）の残差評価値Ｃ、探索中心（ｘ0 ，ｙ0 ）の１画素上（ｘ0 、ｙ0 ＋１）の残差評価値Ｄ、及び、探索中心（ｘ0 ，ｙ0 ）の１画素下（ｘ0 、ｙ0 −１）の残差評価値Ｅのうち最小のものを「ｆｖ0 」として、
また、ＳＢ1 の探索中心（ｘ0 ，ｙ0 ）の残差評価値Ａ、探索中心（ｘ0 ，ｙ0 ）の１画素右（ｘ0 ＋１、ｙ0 ）の残差評価値Ｂ、探索中心（ｘ0 ，ｙ0 ）の１画素左（ｘ0 −１、ｙ0 ）の残差評価値Ｃ、探索中心（ｘ0 ，ｙ0 ）の１画素上（ｘ0 、ｙ0 ＋１）の残差評価値Ｄ、及び、探索中心（ｘ0 ，ｙ0 ）の１画素下（ｘ0 、ｙ0 −１）の残差評価値Ｅのうち最小のものを「ｆｖ1 」として、
また、ＳＢ2 の探索中心（ｘ0 ，ｙ0 ）の残差評価値Ａ、探索中心（ｘ0 ，ｙ0 ）の１画素右（ｘ0 ＋１、ｙ0 ）の残差評価値Ｂ、探索中心（ｘ0 ，ｙ0 ）の１画素左（ｘ0 −１、ｙ0 ）の残差評価値Ｃ、探索中心（ｘ0 ，ｙ0 ）の１画素上（ｘ0 、ｙ0 ＋１）の残差評価値Ｄ、及び、探索中心（ｘ0 ，ｙ0 ）の１画素下（ｘ0 、ｙ0 −１）の残差評価値Ｅのうち最小のものを「ｆｖ2 」として、
また、ＳＢ3 の探索中心（ｘ0 ，ｙ0 ）の残差評価値Ａ、探索中心（ｘ0 ，ｙ0 ）の１画素右（ｘ0 ＋１、ｙ0 ）の残差評価値Ｂ、探索中心（ｘ0 ，ｙ0 ）の１画素左（ｘ0 −１、ｙ0 ）の残差評価値Ｃ、探索中心（ｘ0 ，ｙ0 ）の１画素上（ｘ0 、ｙ0 ＋１）の残差評価値Ｄ、及び、探索中心（ｘ0 ，ｙ0 ）の１画素下（ｘ0 、ｙ0 −１）の残差評価値Ｅのうち最小のものを「ｆｖ3 」として、それぞれ得られる。
【００７４】
これらの推定動きベクトルｆｖ0 〜ｆｖ3 は、ＳＢ0 〜ＳＢ3 のそれぞれで５回のＳＡＤ演算を行うことによって得られたものであり、この演算は、最近傍探索法などの高速探索アルゴリズムの１反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）分に相当するから、当該高速探索アルゴリズムの全反復（予め定められた反復数又は予め定められた第１の反復数）演算に比べて短時間で結果が得られ、しかも、演算の処理量も少ない。
【００７５】
＜ＭＢ探索処理＞
図１２は、ＭＢ探索処理の動作フローチャートを示す図である。このフローチャートを開始すると、まず、ｆｖ0 が初期値（ｘ0 ，ｙ0 ）であるか否かを判定し（ステップＳ５０）、初期値である場合はｍｖに（ｘ0 ，ｙ0 ）をセット（ステップＳ５１）した後、フローチャートを終了する。
【００７６】
一方、ｆｖ0 が初期値（ｘ0 ，ｙ0 ）でなかった場合は、まず、ｘ＝Ｘ，ｙ＝Ｙ、ｏｘ＝ｆｖ0 、ｏｙ＝ｆｖ0 、ｓｘ＝１６、ｓｙ＝１６、ｎ＝１４をセット（ステップＳ５２）する。次いで、それらを引数にしてＮＮＳ関数処理（図１４又は図１５）を実行し、その関数の戻り値をｍｖにセットして（ステップＳ５３）、フローチャートを終了する。ここで、ｘ＝Ｘ，ｙ＝Ｙ、ｏｘ＝ｆｖ0 、ｏｙ＝ｆｖ0 、ｓｘ＝１６、ｓｙ＝１６、ｎ＝１４であるから、ＮＮＳ（Ｘ，Ｙ，ｆｖ0 ，ｆｖ0 ，１６，１６，１４）となる。ＮＮＳ関数は、与えられた引数を条件にして最近傍探索（Nearest Neighbours Search）を行い、その結果（動きベクトル）を返す関数である。ＮＮＳ関数の処理内容については後述する（図１３及び図１４）。
【００７７】
このように、このＭＢ探索処理では、高速探索アルゴリズム、たとえば、最近傍探索法のＮＮＳ関数を用い、その最大反復回数（ｎ）を、たとえば、１４回（この回数は、発明の要旨に記載の「予め定められた第２の反復数」に相当する）にして、一つのマクロブロック（ＭＢ）の正確な動きベクトル（ｍｖ）を演算する。
【００７８】
＜ＳＢ探索処理＞
図１３は、ＳＢ探索処理の動作フローチャートを示す図である。このフローチャートを開始すると、まず、ｓｘ＝８、ｓｙ＝８、ｎ＝１４をセットする（ステップＳ６０）。次いで、ｘ＝Ｘ、ｙ＝Ｙ、ｏｘ＝ｆｖ0 、ｏｙ＝ｆｖ0 をセットし（ステップＳ６１）、それらを引数にしてＮＮＳ関数処理（図１４又は図１５）を実行し、その関数の戻り値をｍｖ0 にセットする（ステップＳ６２）。ここで、ｘ＝Ｘ、ｙ＝Ｙ、ｏｘ＝ｆｖ0 、ｏｙ＝ｆｖ0 、ｓｘ＝８、ｓｙ＝８、ｎ＝１４であるから、ＮＮＳ（Ｘ，Ｙ，ｆｖ0 ，ｆｖ0 ，８，８，１４）となる。
【００７９】
次いで、ｘ＝Ｘ＋８、ｙ＝Ｙ、ｏｘ＝ｆｖ1 、ｏｙ＝ｆｖ1 をセットし（ステップＳ６３）、それらを引数にしてＮＮＳ関数処理（図１４又は図１５）を実行し、その関数の戻り値をｍｖ1 にセットする（ステップＳ６４）。ここで、ｘ＝Ｘ＋８、ｙ＝Ｙ、ｏｘ＝ｆｖ1 、ｏｙ＝ｆｖ1 、ｓｘ＝８、ｓｙ＝８、ｎ＝１４であるから、ＮＮＳ（Ｘ＋８，Ｙ，ｆｖ1 ，ｆｖ1 ，８，８，１４）となる。
【００８０】
次いで、ｘ＝Ｘ、ｙ＝Ｙ＋８、ｏｘ＝ｆｖ2 、ｏｙ＝ｆｖ2 をセットし（ステップＳ６５）、それらを引数にしてＮＮＳ関数処理（図１４又は図１５）を実行し、その関数の戻り値をｍｖ2 にセットする（ステップＳ６６）。ここで、ｘ＝Ｘ、ｙ＝Ｙ＋８、ｏｘ＝ｆｖ2 、ｏｙ＝ｆｖ2 、ｓｘ＝８、ｓｙ＝８、ｎ＝１４であるから、ＮＮＳ（Ｘ，Ｙ＋８，ｆｖ2 ，ｆｖ2 ，８，８，１４）となる。
【００８１】
次いで、ｘ＝Ｘ＋８、ｙ＝Ｙ＋８、ｏｘ＝ｆｖ3 、ｏｙ＝ｆｖ3 をセットし（ステップＳ６７）、それらを引数にしてＮＮＳ関数処理（図１４又は図１５）を実行して、その関数の戻り値をｍｖ3 にセットする（ステップＳ６８）。ここで、ｘ＝Ｘ＋８、ｙ＝Ｙ＋８、ｏｘ＝ｆｖ3 、ｏｙ＝ｆｖ3 、ｓｘ＝８、ｓｙ＝８、ｎ＝１４であるから、ＮＮＳ（Ｘ＋８，Ｙ＋８，ｆｖ3 ，ｆｖ3 ，８，８，１４）となる。
【００８２】
このように、このＳＢ探索処理では、高速探索アルゴリズム、たとえば、最近傍探索法のＮＮＳ関数を用い、その最大反復回数（ｎ）を、たとえば、１４回（この回数は、発明の要旨に記載の「予め定められた第３の反復数」に相当する）にして、各サブブロック（ＳＢ0 、ＳＢ1 、ＳＢ2 、ＳＢ3）毎の正確な動きベクトル（ｍｖ0 、ｍｖ1 、ｍｖ2 、ｍｖ3 ）を演算する。
【００８３】
なお、以上の例では、ＭＢ探索処理の最大反復数ｎ（予め定められた第２の反復数）とＳＢ探索処理の最大反復数ｎ（予め定められた第３の反復数）とを同一の値（“１４”）にしているが、これに限定されない。異なる値であってもよい。
【００８４】
＜ＮＮＳ関数処理＞
図１４は、ＮＮＳ関数処理のフローチャートを示す図である。この関数は与えられた引数（ｘ：ブロックＸ座標，ｙ：ブロックＹ座標，ｏｘ：オフセットＸ座標，ｏｙ：オフセットＹ座標，ｓｘ：ブロックサイズＸ，ｓｙ：ブロックサイズＹ，ｎ：最大反復数）に従って高速探索アルゴリズムの一つである最近傍探索法を実行し、その結果を戻り値として返す。
【００８５】
ＮＮＳ関数は、まず、反復のためのループ変数ｉに初期値０をセットし（ステップＳ７０）、次いで、探索中心の残差評価値Ａ、探索中心の１画素右の残差評価値Ｂ、探索中心の１画素左の残差評価値Ｃ、探索中心の１画素上の残差評価値Ｄ、及び、探索中心の１画素下の残差評価値Ｅを演算する（ステップＳ７１）。これらの残差評価値Ａ〜Ｅは、前記の推定動きベクトル演算処理（図１０及び図１１参照）と同様に、ＳＡＤ関数を用いて求めることができる。
【００８６】
次に、Ａ〜Ｅのうちの最小値を求める（ステップＳ７２）。この最小値も、前記の推定動きベクトル演算処理（図１０及び図１１参照）と同様に、Ｍｉｎ関数を用いて求めることができる。
【００８７】
次に、最小値が探索中心で得られたものであるか否かを判定する（ステップＳ７３）。そして、最小値が探索中心で得られたものであれば、その探索中心の座標を戻り値にして（ステップＳ７４）、フローを終了（反復を終了）する。
【００８８】
一方、最小値が探索中心で得られたものでなければ、最小値が得られた画素を新たな探索中心にセットする（ステップＳ７５）。すなわち、最小値＝Ｂであれば探索中心の１画素右を新たな探索中心にセットし、最小値＝Ｃであれば探索中心の１画素左を新たな探索中心にセットし、最小値＝Ｄであれば探索中心の１画素上を新たな探索中心にセットし、又は、最小値＝Ｅであれば探索中心の１画素下を新たな探索中心にセットする。
次いで、ループ変数ｉを＋１して（ステップＳ７６）、そのｉが最大反復数ｎを超えているか否かを判定し（ステップＳ７７）、超えていなければ、ステップＳ７１に戻って以上の処理を繰り返し（反復し）、超えていれば、そのときの探索中心の座標を戻り値にして（ステップＳ７４）、フローを終了（反復を終了）する。
【００８９】
このように、ＮＮＳ関数処理では、与えられた引数の最大反復数ｎを上限にして反復を繰り返しながら逐次に探索を行い、正確な動きベクトルを返すことができる。
【００９０】
ところで、このＮＮＳ関数処理では、第一反復（ｉ＝０）から処理を開始しているが、先の推定動きベクトル演算処理（図１０及び図１１参照）においても、この第一反復に相当する処理（ステップＳ２３〜ステップＳ２７）を行っているため、二重の演算であり無駄であるから、次のように改良することが望ましい。
【００９１】
図１５は、改良されたＮＮＳ関数処理の要部フローチャートを示す図である。改良前との違いは、探索中心及びその探索中心近傍４点の計５個の残差評価値Ａ〜Ｅを演算する（ステップＳ７１）前に、新たな処理（ステップＳ７８）を行う点にある。
【００９２】
この処理（ステップＳ７８）では、ｉ＝０であるか否かを判定（つまり、第一反復であるか否か）し（ステップＳ７８ａ）、第一反復でなければ（第二反復、第三反復、・・・・であれば）、改良前と同様に探索中心及びその探索中心近傍４点の計５個の残差評価値Ａ〜Ｅを演算する（ステップＳ７１）が、第一反復である場合には、「推定動きベクトル演算処理の中間値（図１０のステップＳ２３〜ステップＳ２７で求められたＡ〜Ｅ）を取り込み、それらを探索中心及びその探索中心近傍４点の計５個の残差評価値Ａ〜Ｅとして流用する」（ステップＳ７８ｂ）。
【００９３】
したがって、この改良されたＮＮＳ関数処理によれば、推定動きベクトル演算処理の中間値を、ＭＢ探索処理（図１２）やＳＢ探索処理（図１３）の反復の初期値として再利用するので、それらのＭＢ探索処理やＳＢ探索処理の反復数を少なくして、処理時間を短縮できる。この処理時間の短縮効果は、たとえ、推定動きベクトル演算処理の反復数が最小（第一反復だけ）であったとしても絶大である。
【００９４】
ＭＢ探索処理やＳＢ探索処理は、ブロックの数だけ実行する必要があり、且つ、一つのビデオストリームあたり「ブロック数×フレーム数」の膨大な量の探索処理が行われるからであり、それゆえ、たとえ、推定動きベクトル演算処理の反復数が最小（第一反復だけ）であったとしても、トータルで見た場合、「ブロック数×フレーム数」に相当する大量の反復処理を省略できるからである。
【００９５】
＜実施形態のまとめ＞
このように、本実施形態によれば、最近傍探索法の第１反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）に相当する演算だけを行って得られた各サブブロック（ＳＢ0 〜ＳＢ3 ）の各々の推定動きベクトル（ｆｖ0 〜ｆｖ3 ）に基づいてマクロブロック（ＭＢ）内の動きが一様に近いか否かを早い段階で判断し、その判断結果に従って探索ブロックの分割方法（大きい分割モードにするか、小さい分割モードにするか）を決定するので、従来技術に比べて、その決定に要する時間を短くすることができ、しかも、次に述べる理由より、計算量をほぼ半減することもできる。
【００９６】
計算量をほぼ半減できる理由は、次のとおりである。従来技術では一つのマクロブロック（１６×１６ブロック）と、そのマクロブロックを分割した４つのサブブロック（８×８ブロック）のそれぞれで動き補償予測を行ってから探索ブロックの分割方法を決めていたため、一つのマクロブロックの計算量をＡとすると、４つのサブブロックの計算量もほぼＡ相当となり、結局、トータルの計算量が略２倍（≒２Ａ）になっていた。
【００９７】
これに対して、本実施形態では、ＭＢ探索（図４のＭＢ探索部２３／図９のステップＳ１３のＭＢ探索処理）とＳＢ探索（図４のＳＢ探索部２５／図９のステップＳ１５のＳＢ探索処理）のいずれか一方しか行わないため、それらの計算量をＡとすると、トータルの計算量は、このＡに、図４の推定動きベクトル演算部２１（又は図９のステップＳ１０の推定動きベクトル演算処理）の計算量αを加えた程度（Ａ＋α）で済む。しかも、推定動きベクトル演算部２１（又は図９のステップＳ１０の推定動きベクトル演算処理）の計算量αは、最近傍探索法などの高速探索アルゴリズムの１反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）分に相当（したがって、Ａ＞＞α）するから、結局、本実施形態のトータルの計算量（Ａ＋α）を、従来技術のそれ（≒２Ａ）に比べてほぼ半減することができるのである。
【００９８】
また、上記の改良されたＮＮＳ関数処理（図１５）を用いると、推定動きベクトル演算処理（図１０及び図１１）の途中で得られる中間値（ステップＳ２３〜ステップＳ２７で得られるＡ〜Ｅ）、つまり、探索アルゴリズムの予め定められた反復数又は予め定められた第１の反復数以下の少ない反復（ｎ′）で演算された複数の第二ブロックの各々の動きベクトルを、ＭＢ探索処理（図１２）やＳＢ探索処理（図１３）の反復の初期値として再利用できる。これにより、ＭＢ探索処理やＳＢ探索処理の反復数を少なく（−ｎ′）して、処理時間を短縮できる。
【００９９】
本発明は上記の実施形態に限定されない。その技術思想の範囲内において、様々な変形例を含むことはもちろんであり、たとえば、以下のようにしてもよい。
（１）サブブロックのサイズ、個数、形状は任意である。また、分割方法に階層関係があれば同様に適用できる。例えば、Ｈ．２６４では「１６×１６」を分割した「８×８」をさらに「４×８」、「８×４」、「４×４」に分割することができ、階層構造が二重になっているが、このいずれかの階層間で、または両方の階層間で行うことができる。
（２）残差評価値はＳＡＤの代わりにＳＳＤ（sum of squared difference：差分二乗和）等であってもよい。サブブロック評価値の集まりからブロック評価値を計算可能であれば、全く同様に適用できる。また、動きベクトルの符号割り当てコストを評価値に加えてもよい。
（３）推定動きベクトル（ｆｖ0 〜ｆｖ3 ）を求めるための反復（予め定められた反復数又は予め定められた第１の反復数以下の少ない反復）は１回だけとしたが、２回ないしはそれ以上の反復を行ってもよい。少なくとも最大反復数（予め定められた反復数又は予め定められた第１の反復数）以下であればよい。反復回数を増やすほど、推定の確実さが高まる。
（４）推定動きベクトル（ｆｖ0 〜ｆｖ3 ）の等価判別は、完全等価のみならず、各成分の差分絶対値が所定値以内などの近似等価によって行ってもよい。
（５）動き推定のための探索アルゴリズムは、最近傍探索法だけでなく、たとえば、Ｎステップ探索法や対数探索法など他のアルゴリズムを用いてもよい。
【図面の簡単な説明】
【０１００】
【図１】動き補償予測ブロックの種類を示す図である。
【図２】本実施形態の便宜的な選択対象となる二つの動き補償予測ブロックを示す図である。
【図３】動き補償予測符号化装置のブロック図である。
【図４】動き推定部１９の概念的なブロック図である。
【図５】動き推定部１９の動作を説明するための概念図（１／２）である。
【図６】動き推定部１９の動作を説明するための概念図（２／２）である。
【図７】図元画像のブロック位置（座標）とブロックサイズを説明するである。
【図８】参照画像に与えるオフセットを示す図である。
【図９】動き推定部１９の動作フローチャートを示す図である。
【図１０】推定動きベクトル演算処理の動作フローチャートを示す図（１／２）である。
【図１１】推定動きベクトル演算処理の動作フローチャートを示す図（２／２）である。
【図１２】ＭＢ探索処理の動作フローチャートを示す図である。
【図１３】ＳＢ探索処理の動作フローチャートを示す図である。
【図１４】ＮＮＳ関数処理のフローチャートを示す図である。
【図１５】改良されたＮＮＳ関数処理のフローチャートを示す図である。
【図１６】動き補償予測符号化の簡略化した概念図である。
【図１７】動き補償予測符号化における被符号化画像生成の概念図である。
【符号の説明】
【０１０１】
Ｓ１０  推定動きベクトル演算処理（第一動きベクトル演算工程）
Ｓ１１  第一判定処理（第一判定工程）
Ｓ１３  ＭＢ探索処理（第二動きベクトル演算工程）
Ｓ１４  ＭＢ動きベクトル出力（選択工程、第一選択工程）
Ｓ１５  ＳＢ探索処理（第三動きベクトル演算工程）
Ｓ１６  第二判定処理（第二判定工程）
Ｓ１８  ＭＢ動きベクトル出力（選択工程、第二選択工程）
Ｓ１９  ＳＢ動きベクトル出力（選択工程、第二選択工程）
１０  動き補償予測符号化装置
１９  動き推定部（ブロック選択手段）
２１  推定動きベクトル演算部（第一動きベクトル演算手段）
２２  第一判定部（第一判定手段）
２３  ＭＢ探索部（第二動きベクトル演算手段）
２４  第一ＭＢ動きベクトル出力部（第一選択手段）
２５  ＳＢ探索部（第三動きベクトル演算手段）
２６  第二判定部（第二判定手段）
２７  第二ＭＢ動きベクトル出力部（第二選択手段）
２８  ＳＢ動きベクトル出力部（第二選択手段）
【図１】
2006180014.tif 000003
【図２】
2006180014.tif 000004
【図３】
2006180014.tif 000005
【図４】
2006180014.tif 000006
【図５】
2006180014.tif 000007
【図６】
2006180014.tif 000008
【図７】
2006180014.tif 000009
【図８】
2006180014.tif 000010
【図９】
2006180014.tif 000011
【図１０】
2006180014.tif 000012
【図１１】
2006180014.tif 000013
【図１２】
2006180014.tif 000014
【図１３】
2006180014.tif 000015
【図１４】
2006180014.tif 000016
【図１５】
2006180014.tif 000017
【図１６】
2006180014.tif 000018
【図１７】
2006180014.tif 000019