動き推定方法及び動き推定装置、並びにプログラム
【課題】正確な動きタイプ予測が可能で、映像内容が複雑な動きを示す場合でも高い頑健性を得ることができる動き推定技術の提供。
【解決手段】対象フレームの各ブロックの既に決定された動きベクトルに基づき、ブロックＣ０の動きベクトルの仮推定値ＭＶ０”を決定する。ＭＶ０”とブロックＣ０周囲のブロックの動きベクトルＭＶｊとの距離の代表値δＴ、すなわち動き複雑性を算出する。更に、参照フレームについても動き複雑性δＴ−１を算出する。この代表値δＴ、δＴ−１の値に対応するブロック探索方法を、代表値δＴ、δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から選択する。このブロック探索方法によって、ブロック探索を行い、動きベクトルを決定する。このように、動き複雑性によりブロック探索方法を適応化させることで、映像内容が複雑な動きを示す場合であっても高い頑健性を得ることができる。
【解決手段】対象フレームの各ブロックの既に決定された動きベクトルに基づき、ブロックＣ０の動きベクトルの仮推定値ＭＶ０”を決定する。ＭＶ０”とブロックＣ０周囲のブロックの動きベクトルＭＶｊとの距離の代表値δＴ、すなわち動き複雑性を算出する。更に、参照フレームについても動き複雑性δＴ−１を算出する。この代表値δＴ、δＴ−１の値に対応するブロック探索方法を、代表値δＴ、δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から選択する。このブロック探索方法によって、ブロック探索を行い、動きベクトルを決定する。このように、動き複雑性によりブロック探索方法を適応化させることで、映像内容が複雑な動きを示す場合であっても高い頑健性を得ることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、映像圧縮におけるブロックマッチングによる動き推定技術に関するものであり、特に、動きベクトルによっては捉えにくい映像の動きを感度よく検出することにより、適応的にブロックマッチングを行うことが可能な動き推定技術に関する。
【背景技術】
【０００２】
ブロックマッチング動き推定（Block Matching Motion Estimation：ＢＭＭＥ）は、ソフトウェア実装においてもハードウェア実装においても、現在のところ最も有力な動き推定（Motion Estimation：ＭＥ）方法であり、MPEG-1/2/4やH.216/263/263+等の種々の国際標準において採用されている。
【０００３】
ブロックマッチング動き推定において、判定基準（matching criterion）として、通常、（数１）で表される差分絶対値和（Sum of Absolution Difference：ＳＡＤ）が使用される。ここで、Ｍはブロックサイズを表す。また、ICとIRは、それぞれ、対象フレーム（current flame）内におけるブロックマッチングの対象のブロックである対象ブロック（current block）内の画素値、及び参照フレーム（reference frame）内において発見された再一致候補ブロック内の画素値を表す。
【０００４】
【数１】
【０００５】
しかしながら、ＢＭＭＥには、本質的に、極めて計算量が大きなタスクを内在していることは明らかである。そして、そのタスクは、ビデオエンコーダにおける全計算時間の６０％〜８０％をも占める程度の計算量であるとする試算が報告されている（非特許文献１参照）。特に総当たり法である全域探索ブロックマッチング（Full Search Block Matching：ＦＳＢＭ）の場合には、＋／−Ｎピクセルの探索領域に対して、探索点は(2N+1)2にものぼる。
【０００６】
そこで、従来、ＭＥの改良技術として、二次元対数探索法（2-D Logarithmic Search ：ＬＯＣＳ）（非特許文献２参照）、３段探索法（Three Step Search ：ＴＳＳ）（非特許文献３，１１参照）、４段探索法（Four Step Search ：ＦＳＳ）（非特許文献４参照）、ダイヤモンド探索法（Diamond Search ：ＤＳ）（非特許文献５，６参照）等、多くの高速探索技術が提案されている。ＦＳＢＭとは異なり、これらのアルゴリズムは、探索時間の大幅な短縮を理論的に達成するために、予め定義された探索パターンを用いることによって、探索点数を削減する手法を採用している。しかしながら、それにより、ハードウェア実装が困難となる。また、このような剛的な探索戦略（rigid search strategy）を採用すると、その探索戦略は様々な種類の映像に対して常に最適であるとは限らない。そのため、いくつかの映像に対しては、マッチング品質が低下するというリスクも大きくなる。
【０００７】
その後、映像内容の動き複雑性に従って、ＢＭの探索戦略を動的に適応化させることにより、映像の歪みを抑えコンピュータの処理コストを低減させることを目的として、適応的動き推定アルゴリズム（Adaptive motion estimation algorithm）が考案された。大部分の適応的動き推定アルゴリズムは、予め複数の探索パターンを用意しておき、対象ブロックに対する動きタイプ予測の結果により、最適な探索戦略を選択するものである。動きベクトル場適応探索法（Motion Vector Field Adaptive Search Technique ：ＭＶＦＡＳＴ）では、動きタイプ予測において空間的相関が利用されている（非特許文献７参照）。また、予測動きベクトル場適応探索法（Predictive Motion Vector Field Adaptive Search Technique：ＰＭＶＦＡＳＴ）においては、時間的に配列されたブロックも動きタイプ予測の考慮の対象となる（非特許文献８参照）。そして、予測された動きタイプに従って、大ダイヤモンド探索（Large Diamond Search：ＬＤＳ）又は小ダイヤモンド探索（Small Diamond Search：ＳＤＳ）が選択される。更に、非特許文献９においては、より洗練された動きタイプ予測アルゴリズムが導入されている。
【特許文献１】特開２００３−３２４７４３号公報
【特許文献２】特開２００３−２７４４１６号公報
【特許文献３】特開２００２−１５２７６０号公報
【特許文献４】特開２００２−１３５７８４号公報
【非特許文献１】P.M. Kuhn, G. Diebel, S. Hermann, A. Keil, H. Mooshofer, A. Kaup, et al. "Complexity and PSNR-comparison of several fast motion estimation algorithms for MPEG4," in Proceeding of Applications of Digital Image Processing ;XXI, San Diego. SPIE, vol. 3460, pp. 486-499, July, 1998.
【非特許文献２】J. R. Jain and A. K. Jain, "Displacement measurement and its application in interframe image coding," IEEE Trans. Commun., vol. 29, pp. 1799-1808, Dec. 1981.
【非特許文献３】T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, "Motion-compensated interframe coding for video conferencing," in Proc. Nat. Telecommunications Conf., pp.G 5.3.1-G 5.3.5., Nov./Dec. 1981.
【非特許文献４】L. M. Po, and W. C. Ma " A novel Four-Step Search Algorithm for fast blockmatching," IEEE Trans. Circuits Syst. Video Technol., vol. 6, Jun. 1996.
【非特許文献５】G. Cote, M. Gallant, and F. Kossentini, " Efficient motion vector estimation and coding for H.263-based very low bit rate video compression," ITU-T SG 16, Q15-A-45, June 1997.
【非特許文献６】J.Y. Tham, S. Ranganath, M. Ranganath, and A.A. Kassim, "A novel unrestricted center-biased diamond search algorithm for block motion estimation," IEEE Trans. On Circuits & Systems for Video Technology, vol.8, pp.369-377, Aug. 1998.
【非特許文献７】P. I. Hosur and K.K. Ma, "Motion Vector Field Adaptive Fast Motion Estimation," Second International Conference on Information, Communications and Signal Proeessing (IClCS '99). Singapore, 7-lO, Dec. 1999.
【非特許文献８】A. M. Tourapisl, O. C. Au2, and M. L. Liou "Predictive Motion Vector Field Adaptive Search Technique (PMVFAST) - Enhancing Block Based Motion Estimation," in Proc. SPIE, Visual Commuaications and Image Processing, vol. 431O, pp. 883-892, Dec. 2000.
【非特許文献９】J.H. Lim, and H.W. Choi, "Adaptive motion estimation algorithm using spatial and temporal correlation," Pacific Rim (PACRIM) Conference on Communications, Computers and signal Processing, vol.2, pp.26-28 Aug. 2001.
【非特許文献１０】T. Sappasitwong, and S. Aramvith, " Adaptive asymmetric diamond search algorithm for block-based motion estimation," International Conference on Digital Signal Processing, vol.2, pp.1-3, July . 2002.
【非特許文献１１】酒井善則，吉田俊之共著，「ヒューマンコミュニケーション工学シリーズ 映像情報符号化」，第１版，株式会社オーム社，２００１年１２月２０日，pp.121-141.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上述の適応的動き推定アルゴリズムは、計算速度とマッチング品質において、従前のアルゴリズムに比べて、より優れた性能が得られることが期待される。しかしながら、上述の適応的動き推定アルゴリズムは、ハードウェア実装をする場合には理想的ではないと考えられる複数の高速探索方法を採用している。更に、フレーム間のエラー伝搬の問題も深刻である。
【０００９】
そこで、本発明の目的は、正確な動きタイプの予測が可能であり、映像内容が複雑な動きを示す場合であっても高い頑健性（robustness）を得ることができる動き推定技術を提供することにある。
【課題を解決するための手段】
【００１０】
最初に本発明に係る動き推定方法について基本となる考え方について説明した後、本発明の構成、作用についての説明を行う。
【００１１】
〔１〕観察
映像は多種多様であるが、それらはすべて映像系列を一つのフレームのセットと見なすことができる。一つのフレーム内における動きは一般に複雑である。しかし、一つのフレームを、いくつかの典型的な動きタイプにマッピングすることのできる部分に切り分けることは可能である。これは、動きタイプの予測を行うにあたっての基礎となる。種々の映像を観察した結果、本発明者は以下のように要約される２つの結論を得た。
【００１２】
（ａ）動きタイプの定義は動き複雑性に基づいている。
近年における研究では（非特許文献９，１０参照）、動きタイプ（motion types）は動き複雑性（motion complexity）に基づいて定義される。「動き複雑性」とは、予測変数である各動きベクトル（motion vector）の間の相関のことをいう。
【００１３】
例えば、図１に例示したフレームでは、フレームの上部においては均一な動きが検出される。均一な動きは、動きがどんなに速くても、大域的な動きベクトルのオフセットを差し引くことにより、固定的な領域に変換できるため、困難は生じない。
【００１４】
（ｂ）動きベクトルは往々にして真の動きを正確に表さない場合がある。
動きベクトルは、映像の符号化において予測誤差を最小化するのに役立つものであるが、動きベクトルは必ずしも映像の真の動きを記述するものではないという点に「トラップ」がある。すなわち、ブロックマッチングによって得られる動きベクトルは、実際には「フレーム間の動き」を表すベクトルではなく、むしろ「フレーム間の冗長性を最も除去可能なベクトル」と解釈されるべきものである。例えば、均一なテクスチャは視覚的な識別性に乏しい。従って、図１において、フレームの下の部分（すなわち、グラウンドに相当する部分）において、均一な動きは動きベクトルとしては捉えられない。
【００１５】
〔２〕局所的な動きタイプ予測
上記の観察に基づき、本発明に係る動き推定においては、動きタイプの予測は対象ブロック（ブロックマッチングの対象であるブロック）の周囲の動き複雑性の分析に基づいて行われる。動きベクトルの分布を動き複雑性の分析の基礎として利用することにより、動きベクトルが真の動きを捉えることに失敗したときに、上記「トラップ」に陥るのを避けることができる。
【００１６】
対象ブロックの近傍に位置するいくつかのブロックを、ブロックマッチングを行うためのコンテキストを形成するブロックとして選択する。図２は、ブロックマッチングを行うために使用されるコンテキストの一例である。
【００１７】
コンテキストＴは、対象フレーム内のブロックから構成されるコンテキストであって、対象ブロックＣ０の第１隣接にある３つのブロックＣ１，Ｃ２，Ｃ３により構成されるコンテキストである。ここで、「第１隣接」とは、対象ブロックのいずれかの辺又は頂点に対し、いずれかの辺又は頂点が接しているブロックをいう。
【００１８】
対象フレームのブロックマッチングは、ラスタスキャンの走査方向に沿って、フレームの左上のブロックから右下のブロックにかけて、右向きの水平方向の反復走査に沿って行われる。従って、図２において、コンテキストＴのブロックＣ１，Ｃ２，Ｃ３はすでに動きベクトルが決定されたブロックである。また、参照フレームについては、すでにすべてのブロックについて動きベクトルが決定されている。
【００１９】
また、コンテキストＴ−１は、参照フレーム内のブロックから構成されるコンテキストであって、対象ブロックＣ０の位置に対応する参照フレーム内のブロックＣ０’及びその第１隣接に位置するブロックＣ１’〜Ｃ８’により構成されるコンテキストである。
【００２０】
本発明に係る動き推定においては、従来提案されている動き推定法（非特許文献９，１０参照）とは異なり、ブロックマッチングにおいて空間的な相関を引き出すために、対象フレーム及び参照フレームから数ブロックを抽出し、これを対象ブロックＣ０の動き推定に利用することにある。このように一般化した隣接ブロックは、２つの連続したフレームに含まれる局所的な動きの情報を引き出すためのサンプルとして利用される。動き複雑性の解析は、コンテキストＴ−１とコンテキストＴに対して、以下の２つの評価に基づいて行われる。
【００２１】
【数２】
【００２２】
【数３】
【００２３】
ここで、ＭＶｉ’（ｉ＝０，１，…，８）は、コンテキストＴ−１におけるブロックＣｉ’の動きベクトルを表す。ＭＶｉ（ｉ＝１，２，３）は、コンテキストＴにおけるブロックＣｉ’の動きベクトルを表す。δＴ−１，δＴは、それぞれ参照フレーム、対象フレームにおける局所的な動き複雑性を表す。これらは、予測変数として用いられる動きベクトルの関数として定義される。
【００２４】
本発明においては、局所的な動き複雑性を規定する関数として、対象ブロックＣ０及びそれに対応するブロックＣ０’の動きベクトルＭＶ０，ＭＶ０’と、コンテキストＴ，Ｔ−１内の他のブロックＣｉ，Ｃｉ’の動きベクトルＭＶｉ，ＭＶｉ’との間の距離の代表値を使用する。すなわち、局所的な動き複雑性δＴ−１，δＴを（数４）、（数５）により定義する。特に、コンテキストＴ−１は対称的な構造であり、すべての方向からの動き特性の変化を捉えることができるので、（数４）は敏感な特性値（indicator）となる。
【００２５】
【数４】
【００２６】
【数５】
【００２７】
ここで、ＲｅｐＴ−１，ＲｅｐＴは、それぞれ、代表値関数である。代表値関数としては、最大値、最頻値、中央値、平均値、総和等を使用することができる。‖・‖は、ベクトルのノルムを表す。また、動きベクトルＭＶ０については、現時点では求まっていないので、δＴの演算においては、動きベクトルＭＶ０の代わりにその仮推定値ＭＶ０”＝ＭＶ０”（ＭＶ１，ＭＶ２，ＭＶ３）を使用する。ＭＶ０”の演算式についても、種々の方法が考えられる。
【００２８】
より具体的には、局所的な動き複雑性δＴ−１，δＴとして（数６）、（数７）を使用することができる。
【００２９】
【数６】
【００３０】
【数７】
【００３１】
上記のようなコンテキストＴ−１，Ｔの局所的な動き複雑性δＴ−１，δＴに従って、コンテキストＴ−１，Ｔの動きタイプＴＹＰＥＴ−１，ＴＹＰＥＴの分類を行う。動きタイプの分類の決定は、（数８）、（数９）に示すような閾値判定により行うことができる。
【００３２】
【数８】
【００３３】
【数９】
【００３４】
ここで、Ｔｈ１，Ｔｈ２は動きタイプを分類するための閾値を表す。閾値Ｔｈ１，Ｔｈ２を適当な値に選択することによって、時間的及び空間的な予測変数の影響の度合いを調節することができる。
【００３５】
次のステップでは、時間コヒーレンス（temporal coherence）を考慮して、前記ＴＹＰＥＴ−１，ＴＹＰＥＴに基づき、対象ブロックＣ０について、最も可能性の高い動きタイプを予測する。対象ブロックＣ０の動きタイプの予測は、（表１）に従って行うことができる。
【００３６】
【表１】
【００３７】
対象ブロックＣ０の動きタイプを用いることにより、対象ブロックＣ０の動きベクトルＭＶ０のより確実な予測を行うことが可能となる。例えば、均一なテクスチャ部分が高速に動いている場合において、ＭＶ６’以外の他のすべての動きベクトルが動きを捉えていない場合においても、ＭＶ６’が動きを捉えている限りは、上記動きタイプ予測によって、対称ブロックＣ０は激しい動きにあることを検出することが可能となる。これに対して、従来の他の動き推定方法では、このような動き検出をすることはできない。
【００３８】
〔３〕適応的ブロックマッチング
以上のような推定により得られる動きタイプを用いて、本発明では以下のような適応的ブロックマッチングにより動き推定を行う。
【００３９】
（１）ステップ１
上述の局所的な動きタイプ予測を実行した後、（数１０）により４つの探索中心候補を決定する。各ベクトルＶｉ＝（ｖｘｉ，ｖｙｉ）は、対象ブロックＣ０に対応するブロックＣ０’の中心位置から探索の中心となる点までのオフセットを表すベクトルである。
【００４０】
【数１０】
【００４１】
ベクトルＶ３，Ｖ４は、それぞれ、参照フレーム内のブロックＣ０’の右上半面、左下半面に属するブロックの動きベクトルの代表値を表す。ここでは、ベクトルＶ３，Ｖ４として、（数１１）の値を使用する。
【００４２】
【数１１】
【００４３】
（２）ステップ２
上記４つの探索中心候補の中で最良の探索中心を表すベクトルＶを選択する。この選択は、（数１２）によりＳＡＤを計算することによって行う。
【００４４】
【数１２】
【００４５】
ここで、ＩＴ，ＩＴ−１は、それぞれ、対象ブロック、参照ブロックの画素値を表す。また、演算子argmin（・）の部分は、「（・）を最小にするＶｋ」を表している。
【００４６】
（３）ステップ３
最後に、選択されたベクトルＶをオフセットとして、ブロック探索を行う。このとき、上記予測により得られた対象ブロックＣ０の動きタイプによって、対象ブロックＣ０の動きベクトルを決定するための探索方法の選択を行う。この場合、対象ブロックＣ０の動きタイプが‘ＣＨＡＯＳ’の場合、対象ブロックＣ０の近傍の動きは複雑であることが予測される。従って、動きベクトルの探索方法は広範囲の探索に適した方法を選択する必要がある。対象ブロックＣ０の動きタイプが‘ＣＲＩＴＩＣＡＬ’の場合、対象ブロックＣ０の近傍の動きは複雑な動きから一様な動きに変化する境界付近にあることが予測される。従って、この場合、動きベクトルの探索方法は中程度の範囲の探索に適した方法を選択する必要がある。対象ブロックＣ０の動きタイプが‘ＳＩＭＰＬＥ’の場合、対象ブロックＣ０の近傍の動きは一様であることが予測される。従って、動きベクトルの探索方法は狭範囲の探索に適した方法を選択する必要がある。
【００４７】
そこで、例えば、対象ブロックＣ０の動きタイプによって、（表２）のように探索方法を選択することができる。
【００４８】
【表２】
【００４９】
ここで、ＦＳは全域探索（Full Search）法、ＴＳＳは３段探索（Three Step Search）法を表す。Nsimple，Ncritical，Nchaosは探索範囲を表す。例えば、Nsimpleの場合には、Nsimple×Nsimpleの領域において探索を行うことを表している。ここで、Nsimple，Ncritical，Nchaosの間には（数１３）のような関係がある。
【００５０】
【数１３】
【００５１】
‘ＳＩＭＰＬＥ’の場合、小さいウィンドウ内に探索領域を限定することによって、かなりの量の無駄な計算を省くことができる。
【００５２】
‘ＣＲＩＴＩＣＡＬ’の場合、対象フレームの動き複雑性は参照フレームの動き複雑性よりも低くなる。従って、ほとんどの場合、（数１２）によりかなり信頼性の高い探索中心のオフセットを予測することができる。従って、ブロックマッチングにおける探索範囲は小さくてもよい。しかしながら、上述した「トラップ」を考慮して、探索領域はNsimpleよりも大きくあるべきである。
【００５３】
‘ＣＨＡＯＳ’の場合には、それぞれの動きベクトル間の相関が小さいので、ブロックマッチングを行う際の探索範囲は大きめにとる必要がある。しかしながら、探索中心はオフセットによりシフトされる。また、動きベクトルの探索領域の大きさは、探索によって得られる動きベクトルの大きさが実用範囲内となる程度に制限される。従って、探索範囲の大きさは一定サイズの領域に限定されるので、動き複雑性が大きい場合でも計算量は減少すると考えられる。動きベクトルの探索は、螺旋パターン（spiral pattern）により従って実行し、早期打ち切り法（early break technique）を用いることができる。
【００５４】
また、それぞれの場合において、同じＳＡＤの候補が２つ以上見つかった場合には、対象ブロックＣ０の位置により近い方を採用すればよい。
【００５５】
〔４〕本発明の構成及び作用
本発明に係る動き推定方法の第１の構成は、複数のフレームから構成される映像において、参照フレームに対する対象フレーム内の各ブロックの動きベクトルを推定する動き推定方法であって、前記対象フレーム内における動きベクトル推定の対象となるブロック（以下、「対象ブロック」という。）Ｃ０との相関が最大である前記参照フレーム内のブロックの探索を、以下の各ステップを有する選択手順で選択されたブロック探索方法に従って行うことにより、前記対象ブロックＣ０の動きベクトルＭＶ０を決定することを特徴とする：
（１）前記参照フレーム又は前記対象フレームの各ブロックの動きベクトルであって既に決定されているものに基づき、前記対象ブロックＣ０の動きベクトルＭＶ０の仮推定値ＭＶ０”を決定する第１ステップ；
（２）前記仮推定値ＭＶ０”と、前記対象フレーム内における前記対象ブロックＣ０周囲の所定の範囲Ｒ１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｊ（ｊ∈Ｒ１）の動きベクトルＭＶｊとの間の距離の代表値δＴを算出する第２ステップ；
（３）前記対象ブロックＣ０に対応する前記参照フレーム内のブロックＣ０’の動きベクトルＭＶ０’と、前記ブロックＣ０’の周囲の所定の範囲Ｒ２内にある前記参照フレーム内の各ブロックＣｉ’（ｉ∈Ｒ２）の動きベクトルＭＶｉ’との間の距離の代表値δＴ−１を算出する第３ステップ；
（４）前記代表値δＴ及び前記代表値δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から、前記第２ステップ及び前記第３ステップで算出された前記代表値δＴ及び前記代表値δＴ−１の値に対応するブロック探索方法を選択する第４ステップ。
【００５６】
この構成により、対象ブロックＣ０の動きベクトルの仮推定値に対する対象ブロックＣ０の周囲のブロックの局所的な動きベクトルのばらつきの度合い（以下、「局所的な動き複雑性（local motion complexity）」という。）に応じて、適応的にブロック探索方法を決定することができる。「局所的な動き複雑性」とは、対象ブロックＣ０の動きベクトルに対するその周囲の動きベクトルの変化の度合いをいう。この局所的な動き複雑性は、第２ステップ及び第３ステップで演算される代表値δＴ及びδＴ−１の値により評価される。
【００５７】
すなわち、第２、第３ステップにおいて、対象フレームにおける対象ブロックＣ０を中心とする局所的な動き複雑性と、参照フレーム内におけるブロックＣ０’を中心とする局所的な動き複雑性とが算出される。そして、第４ステップにおいて、それらを参照し、局所的な動き複雑性が大きい場合には、広範囲のブロック探索に適したブロック探索方法を選択し、局所的な動き複雑性が小さい場合には狭範囲のブロック探索に適したブロック探索方法を選択することが可能となる。これにより、ブロック探索に要する演算量を現実的な演算量に抑えつつ、動きが小さい場合において動きベクトルの推定精度を高く維持することができるとともに、動きが大きい場合に動きベクトルの予測が大きく外れることを防止することが可能となる。
【００５８】
特に、対象ブロックＣ０の周囲の「局所的な動き複雑性」と参照フレーム内におけるブロックＣ０’の周囲の「局所的な動き複雑性」との双方を評価することで、一様なテクスチャが高速に移動する部分のように、対象ブロックＣ０の周囲に動きがあるにもかかわらずそれが動きベクトルに動きが反映されにくい状態にある映像に対しても、動きの存在を敏感に捉えることが可能となる。すなわち、正確な動きタイプの予測が可能となり、映像内容が複雑な動きを示す場合であっても高い頑健性を得ることができる。そして、捉えられた動きタイプに応じて、適応的にブロック探索方法が選択されるため、高いマッチング品質を得ることができる。そして、捉えられた動きに応じて、適応的にブロック探索方法が選択されるため、残留予測誤差を更に小さくし、映像の圧縮率を改善することができる。
【００５９】
ここで、「ブロック」とは、動き補償による画像の符号化を行う際に、一つの動きベクトルに対応させる領域の単位をいう。通常は、１６×１６画素のブロックを使用するが、本発明においてはブロックの大きさは特に限定しない。
【００６０】
「ブロック探索方法」とは、対象フレーム内の対象ブロックＣ０との相関が最大である（最も一致する）参照フレーム内のブロックの探索を行う方法をいう。本発明においては、「ブロック探索方法」は、特に限定するものではないが、例えば、全域探索法（Full Search Technique）、二次元対数探索法（2-D Logarithmic Search Technique）（非特許文献２参照）、多段探索法（３段探索法（Three Step Search Technique）、４段探索法（Four Step Search Technique）等）（非特許文献３，４，１１参照）、動きベクトル場適応探索法（Motion Vector Field Adaptive Search Technique）（非特許文献７参照）、ダイヤモンド探索法（Diamond Search Technique）（非特許文献５，６参照）等を使用することが可能である。
【００６１】
第４ステップにおいては、通常、代表値δＴの値が小さい場合には、対象ブロックＣ０近傍の「局所的な動き複雑性」は小さいと考えられるので、「ブロック探索方法」としてはマッチング誤差を最小化することが可能な全域探索法を選択するようにし、代表値δＴの値が大きい場合には、対象ブロックＣ０近傍の局所的な動き複雑性は大きいと考えられるので、「ブロック探索方法」としては、多段探索法、動きベクトル場適応探索法、ダイヤモンド探索法等の広い領域を高速に探索できる方法を選択するように設定しておくことが好ましい。
【００６２】
「動きベクトル」とは、参照フレームと対象フレーム間において、映像が動いた方向と距離を表す動き量のことをいう。
【００６３】
動きベクトルＭＶ０の仮推定値ＭＶ０”の決定方法は、ここでは特に限定はしない。この仮推定値ＭＶ０”の決定方法としては、例えば、対象ブロックＣ０の近傍にある対象フレーム内のブロックのうち動きベクトルが既に決定されているものの集合をＲ３とした場合、集合Ｒ３に属するブロックの動きベクトルの平均値、中央値、最頻値、加重平均値等を仮推定値ＭＶ０”とする方法などを採ることができる。
【００６４】
「所定の範囲Ｒ１」は、対象ブロックＣ０の近傍であって、対象ブロックＣ０の動きベクトルとの相関が大きい動きベクトルを有するブロックの範囲に定められる。本発明では特に「所定の範囲Ｒ１」は特に限定しないが、通常は、対象ブロックＣ０の第１隣接又は第２隣接までを含む範囲に設定される。
【００６５】
「所定の範囲Ｒ２」は、ブロックＣ０’の近傍であって、ブロックＣ０’の動きベクトルとの相関が大きい動きベクトルを有するブロックの範囲に定められる。本発明では特に「所定の範囲Ｒ２」は特に限定しないが、通常は、ブロックＣ０’の第１隣接又は第２隣接までを含む範囲に設定される。
【００６６】
２つの動きベクトルの間の「距離」とは、動きベクトル空間における２つの動きベクトルの間の空間的な隔たりをいう。「距離」としては、差分絶対値和（Sum of Absolute Difference : ＳＡＤ）、平均平方誤差（Mean square error : MSE）、平均絶対誤差（mean absolute error : MAE）、ユークリッド距離等を使用することができる。
【００６７】
距離の「代表値」とは、変数の分布を要約する統計量のことをいう。「距離の代表値δＴ」としては、最大値、最小値、中央値、平均値、最頻値、総和、自乗和、平方和等を使用することができる。
【００６８】
本発明に係る動き推定方法の第２の構成は、前記第１の構成において、前記第４ステップにおいて、前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合には、ブロック探索方法として、所定の探索領域における多段探索法を選択し、前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合には、ブロック探索方法として、前記多段探索法の探索領域よりも狭い探索領域での全域探索法を選択することを特徴とする。
【００６９】
この構成によれば、代表値δＴの値の閾値判定によって、対象ブロックＣ０の近傍の局所的な動き複雑性に応じて動きベクトルの探索方法を適応的に切り替えることが可能となる。また、閾値判定であるため、簡単なアルゴリズムにより実現可能であり、また、ハードウェアによって回路的に実現する場合の回路構成も簡易である。
【００７０】
ここで、「所定の閾値Ｔｈ１」は、実験的に設定する値である。また、「所定の閾値Ｔｈ１」は、必ずしも固定値とする必要はなく、動き推定の精度の要求に応じて、外部から自由に設定できるようにしてもよい。
【００７１】
本発明に係る動き推定方法の第３の構成は、前記第１又は２の構成において、前記第４ステップにおいて、前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合においては、ブロック探索方法として、所定の探索領域Ｓ０における多段探索法を選択し、前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合においては、前記代表値δＴ−１の値が所定の閾値Ｔｈ２よりも大きい場合には、ブロック探索方法として、前記多段探索法の探索領域Ｓ０と同じ又はより狭い探索領域Ｓ１での全域探索法を選択し、前記代表値δＴ−１の値が所定の閾値Ｔｈ２以下の場合には、ブロック探索方法として、前記探索領域Ｒ１よりも狭い探索領域Ｓ２での全域探索法を選択することを特徴とする。
【００７２】
この構成によれば、代表値δＴ及び代表値δＴ−１の値の閾値判定によって、対象ブロックＣ０及びブロックＣ０’の近傍の局所的な動き複雑性に応じて動きベクトルの探索方法を適応的に切り替えることが可能となる。また、閾値判定であるため、簡単なアルゴリズムにより実現可能であり、また、ハードウェアによって回路的に実現する場合の回路構成も簡易である。
【００７３】
ここで、各場合における探索領域Ｓ０，Ｓ１，Ｓ２の大きさは、それぞれ、要求される計算速度、計算精度等に応じて適度な大きさに設定することができる。
【００７４】
また、「所定の閾値Ｔｈ１，Ｔｈ２」は、実験的に設定する値である。また、「所定の閾値Ｔｈ１，Ｔｈ２」は、必ずしも固定値とする必要はなく、動き推定の精度の要求に応じて、外部から自由に設定できるようにしてもよい。
【００７５】
本発明に係る動き推定方法の第４の構成は、前記第１乃至３の何れか一の構成において、前記第１ステップにおいて、前記仮推定値ＭＶ０”は、前記対象フレーム内における前記対象ブロックＣ０周囲の所定の範囲Ｒ３内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｋ（ｋ∈Ｒ３）の動きベクトルＭＶｋに基づいて決定されることを特徴とする。
【００７６】
この構成により、走査に従って、対象ブロックＣ０の前に決定された動きベクトルを用いて対象ブロックＣ０の動きベクトルの仮推定値ＭＶ０”を決定することができる。
【００７７】
ここで、「所定の範囲Ｒ３」は特に限定しないが、通常は、対象ブロックＣ０の第１隣接又は第２隣接までを含む範囲に設定される。
【００７８】
「動きベクトルＭＶｋに基づいて」とは、例えば、動きベクトル｛ＭＶｋ｜∀ｋ∈Ｒ３｝の平均値、中央値、最頻値等を仮推定値ＭＶ０”に決定することをいう。また、ラスタスキャンに従って対象ブロックＣ０の動きベクトルＭＶ０を決定していく場合には、対象ブロックＣ０の上の行のブロックと、対象ブロックＣ０の行における対象ブロックＣ０の左側のブロックについては、既に動きベクトルが決定されている。そこで、対象ブロックＣ０の左の隣接ブロックをＣａ、左上の隣接ブロックをＣｂ、上の隣接ブロックをＣｃとすれば、例えば、ＭＶ０”＝ＭＶａ＋ＭＶｃ−ＭＶｂのようにして、二次元の画素値予測方法と同様な方法により仮推定値ＭＶ０”を決定するようにしてもよい。
【００７９】
本発明に係る動き推定方法の第５の構成は、前記第４の構成において、前記仮推定値ＭＶ０”は、（数１４）により計算されることを特徴とする。
【００８０】
【数１４】
【００８１】
この構成によれば、前記仮推定値ＭＶ０”として、｛ＭＶｋ｜∀ｋ∈Ｒ３｝の中央値を用いることで、簡単なアルゴリズムにより仮推定値ＭＶ０”を決定することができる。
【００８２】
本発明に係る動き推定方法の第６の構成は、前記第１乃至５の何れか一の構成において、第２ステップにおいて、所定の範囲Ｒ１は、前記対象ブロックＣ０に対し第１隣接のブロックであって、かつ既に動きベクトルが決定されている４つのブロックの内の一部又は全部のブロックであることを特徴とする。
【００８３】
このように、対象ブロックＣ０周囲の局所的な動き複雑性の検出に、対象ブロックＣ０に対し第１隣接のブロックを使用することで、対象ブロックＣ０から離れたブロックの動きベクトルの影響を受けずに、対象ブロックＣ０の周囲の局所的な動き複雑性を検出することができる。従って、ブロック探索方法の選択において、無駄に広域探索の方法が選択されることを防止することができる。
【００８４】
本発明に係る動き推定方法の第７の構成は、前記第１乃至５の何れか一の構成において、第２ステップにおいて、代表値δＴは、（数１５）により計算されることを特徴とする。
【００８５】
【数１５】
【００８６】
このように、代表値δＴとして動きベクトルの差分絶対値和（ＳＡＤ）を用いれば、代表値δＴの演算が、局所的な動き複雑性をよく表し、かつ簡単なアルゴリズムにより実現可能となる。
【００８７】
本発明に係る動き推定方法の第８の構成は、前記第１乃至７の何れか一の構成において、前記第３ステップにおいて、前記所定の範囲Ｒ２は、前記ブロックＣ０’に対して隣接する８つのブロックの範囲であることを特徴とする。
【００８８】
このように、ブロックＣ０’に対して隣接する８つのブロックを参照して局所的な動き複雑性を評価することで、すべての方向からの動き特性の変化を捉えることができる。従って、代表値δＴ−１は、動きの特性の変化を捉える敏感な特性値となる。
【００８９】
本発明に係る動き推定方法の第９の構成は、前記第１乃至７の何れか一の構成において、前記第３ステップにおいて、前記代表値δＴ−１は、（数１６）により計算されることを特徴とする。
【００９０】
【数１６】
【００９１】
このように、最大値を利用することで、動き特性の変化に対する敏感性を高め、任意方向に起こる動き特性の変化を正確に捉えることができる。
【００９２】
本発明に係る動き推定装置の第１の構成は、複数のフレームから構成される映像において、参照フレームに対する、対象フレームにおける各ブロックの動きベクトルを推定する動き推定装置であって、前記参照フレーム及び前記対象フレームの各ブロックに対する動きベクトルを記憶する動きベクトル記憶手段と、前記動きベクトル記憶手段に記憶されている動きベクトルに基づき、前記対象フレーム内のブロックであって動きベクトル推定の対象となるブロック（以下、「対象ブロック」という。）Ｃ０の動きベクトルＭＶ０の仮推定値ＭＶ０”を演算する動きベクトル仮推定手段と、前記対象ブロックＣ０周囲の所定の範囲Ｒ１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｊ（ｊ∈Ｒ１）の動きベクトルＭＶｊと、前記仮推定値ＭＶ０”との間の距離の代表値δＴを算出する第１の代表値演算手段と、前記対象ブロックＣ０に対応する前記参照フレーム内のブロックＣ０’の動きベクトルＭＶ０’と、前記ブロックＣ０’の周囲の所定の範囲Ｒ２内にある前記参照フレーム内の各ブロックＣｉ’（ｉ∈Ｒ２）の動きベクトルＭＶｉ’との間の距離の代表値δＴ−１を算出する第２の代表値演算手段と、前記代表値δＴ及び前記代表値δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から、前記第１の代表値演算手段により算出された前記代表値δＴ及び前記代表値δＴ−１の値に対応するブロック探索方法を選択する探索方法選択手段と、前記探索方法選択手段により選択された探索方法に従って、前記対象ブロックＣ０との相関が最大である前記参照フレーム内のブロックの探索を行い、前記動きベクトルＭＶ０を決定し、前記動きベクトル記憶手段に保存する動きベクトル決定手段とを備えていることを特徴とする。
【００９３】
この構成によれば、動きベクトル仮推定手段は、動きベクトル記憶手段に記憶されている動きベクトルに基づき、対象ブロックＣ０の動きベクトルＭＶ０の仮推定値ＭＶ０”を演算する。第１の代表値演算手段は、この仮推定値ＭＶ０”と各動きベクトルＭＶｊとの間の距離の代表値δＴを算出する。第２の代表値演算手段は、動きベクトルＭＶ０’と各動きベクトルＭＶｊ’との間の距離の代表値δＴ−１を算出する。次いで、探索方法選択手段は、代表値δＴ及び代表値δＴ−１の値に対応するブロック探索方法を選択する。そして、動きベクトル決定手段は、選択された探索方法に従って、参照フレーム内のブロックの探索を行い、動きベクトルＭＶ０を決定し、動きベクトル記憶手段に保存する。以上の動作を繰り返すことによって、対象フレーム内の各ブロックの動きベクトルが順次決定される。
【００９４】
このとき、動きベクトルの探索方法は、対象ブロックＣ０を中心とする「局所的な動き複雑性」及び対象ブロックＣ０’を中心とする「局所的な動き複雑性」の両方に適応して選択される。これにより、ブロック探索に要する演算量を現実的な演算量に抑えつつ、動きが小さい場合において動きベクトルの推定精度を高く維持することができるとともに、動きが大きい場合に動きベクトルの予測が大きく外れることを防止することが可能となる。
【００９５】
また、対象ブロックＣ０の動きベクトルの仮推定値が真の動きを捉えていない場合においても、対象ブロックＣ０及び対象ブロックＣ０’の双方の周囲の「局所的な動き複雑性」を評価することで、対象ブロックＣ０のみに着目する場合よりも、動きの存在をより敏感に捉え易くなる。そして、捉えられた動きに応じて、適応的にブロック探索方法が選択されるため、残留予測誤差をより小さくし、映像の圧縮率を改善することができる。
【００９６】
本発明に係る動き推定装置の第２の構成は、前記第１の構成において、前記探索方法選択手段は、前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合には、ブロック探索方法として、所定の探索領域における多段探索法を選択し、前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合には、ブロック探索方法として、前記多段探索法の探索領域よりも狭い探索領域での全域探索法を選択することを特徴とする。
【００９７】
本発明に係る動き推定装置の第３の構成は、前記第１又は２の構成において、前記探索方法選択手段は、前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合においては、ブロック探索方法として、所定の探索領域Ｓ０における多段探索法を選択し、前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合においては、前記代表値δＴ−１の値が所定の閾値Ｔｈ２よりも大きい場合には、ブロック探索方法として、前記多段探索法の探索領域Ｓ０と同じ又はより狭い探索領域Ｓ１での全域探索法を選択し、前記代表値δＴ−１の値が所定の閾値Ｔｈ２以下の場合には、ブロック探索方法として、前記探索領域Ｒ１よりも狭い探索領域Ｓ２での全域探索法を選択することを特徴とする。
【００９８】
本発明に係る動き推定装置の第４の構成は、前記第１乃至３の何れか一の構成において、前記動きベクトル仮推定手段は、前記対象フレーム内における前記対象ブロックＣ０周囲の所定の範囲Ｒ３内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｋ（ｋ∈Ｒ３）の動きベクトルＭＶｋに基づいて前記仮推定値ＭＶ０”を決定することを特徴とする。
【００９９】
本発明に係る動き推定装置の第５の構成は、前記第４の構成において、前記仮推定値ＭＶ０”は、（数１７）により計算されることを特徴とする。
【０１００】
【数１７】
【０１０１】
本発明に係る動き推定装置の第６の構成は、前記第１乃至５の何れか一の構成において、前記所定の範囲Ｒ１は、前記対象ブロックＣ０に上下左右及び斜め方向に隣接し、かつ既に動きベクトルが決定されている４つのブロックの内の一部又は全部のブロックであることを特徴とする。
【０１０２】
本発明に係る動き推定装置の第７の構成は、前記第１乃至５の何れか一の構成において、前記第１の代表値演算手段は、（数１８）により代表値δＴを計算することを特徴とする。
【０１０３】
【数１８】
【０１０４】
本発明に係る動き推定装置の第８の構成は、前記第１乃至７の何れか一の構成において、前記所定の範囲Ｒ２は、前記ブロックＣ０’に対して上下左右及び斜め方向に隣接する８つのブロックの範囲であることを特徴とする。
【０１０５】
本発明に係る動き推定装置の第９の構成は、前記第１乃至７の何れか一の構成において、前記第２の代表値演算手段は、（数１９）により代表値δＴ−１を計算することを特徴とする。
【０１０６】
【数１９】
【０１０７】
本発明に係るプログラムは、コンピュータに上記第１乃至９の何れか一の構成の動きベクトル推定方法を実行させる
【発明の効果】
【０１０８】
以上のように、本発明によれば、局所的な動き複雑性が大きい場合には、広範囲のブロック探索に適したブロック探索方法を選択し、局所的な動き複雑性が小さい場合には狭範囲のブロック探索に適したブロック探索方法を選択することが可能となる。これにより、ブロック探索に要する演算量を現実的な演算量に抑えつつ、動きが小さい場合において動きベクトルの推定精度を高く維持することができるとともに、動きが大きい場合に動きベクトルの予測が大きく外れることを防止することが可能となる。
【０１０９】
また、対象ブロックＣ０の動きベクトルの仮推定値が、真の動きを捉えるのに失敗した場合においても、対象ブロックＣ０の周囲の「局所的な動き複雑性」を評価することで、対象ブロックＣ０のみに着目する場合よりも、動きの存在をより敏感に捉え易くなる。すなわち、正確な動きタイプの予測が可能となり、映像内容が複雑な動きを示す場合であっても高い頑健性が得られる。そして、捉えられた動きに応じて、適応的にブロック探索方法が選択されるため、残留予測誤差をより小さくし、映像の圧縮率を改善することができる。
【発明を実施するための最良の形態】
【０１１０】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【０１１１】
図３は一般の映像符号化装置１の全体構成を表す図である（非特許文献１１参照）。尚、図３の映像符号化装置１は、一般に広く使用されているものであるため、ここでの説明は、その概略説明のみにとどめる。
【０１１２】
映像符号化装置１は、フレームメモリ２、差分器３、離散コサイン変換器（ＤＣＴ）４、量子化器５、エントロピ符号器６、局所復号器７、動き推定装置８、及び動き補償器９から構成されている。
【０１１３】
フレームメモリ２は、撮像素子等から入力される映像フレームを一時的に記憶するメモリである。差分器３は、フレームメモリ２が出力する対象フレームｆＴから、動き補償器９が出力する予測フレームｆＴ’を差し引いた差分画像ΔｆＴを出力する。ＤＣＴ４は、差分画像ΔｆＴに対して離散コサイン変換を施す。量子化器５は、ＤＣＴ４により出力されるＤＣＴ係数を量子化する。エントロピ符号器６は、量子化器５が出力する量子化されたＤＣＴ係数と動き推定装置８が出力する動きベクトルＭＶとをエントロピ符号化して、符号化映像のビット列として出力する。
【０１１４】
局所復号器７は、量子化器５が出力するＤＣＴ係数を再度もとのフレーム画像に復元する。そして、復元したフレーム画像を一時的に記憶し、対象フレームｆＴよりも前の参照フレームｆＴ−１”を出力する。動き推定装置８は、この参照フレームｆＴ−１”と対象フレームｆＴとを用いて、動きベクトルＭＶを推定し出力する。動き補償器９は、参照フレームｆＴ−１”と動きベクトルＭＶを用いて、対象フレームｆＴの予測値である予測フレームｆＴ’を生成し出力する。この予測フレームｆＴ’が、前記差分器３において差分画像ΔｆＴを生成する際に使用される。
【０１１５】
ここで、動き推定装置８において動きベクトルＭＶを生成するとき、及び動き補償器９において参照フレームとして、入力された映像からそのまま得られるフレームｆＴ−１を使用せず、局所復号器７で復元されたフレームｆＴ−１”を使用しているのは、映像復号側において復号画像に量子化誤差が蓄積することによりドリフトが生じることを防止するためである。
【０１１６】
尚、局所復号器７は、逆量子化器１０、逆離散コサイン変換器（逆ＤＣＴ）１１、加算器１２、フレームメモリ１３から構成されている。量子化器５が出力するＤＣＴ係数は、逆量子化器１０に入力され逆量子化が施された後に、逆ＤＣＴ１１において逆離散コサイン返還が施され、差分画像ΔｆＴ”が復元される。加算器１２において、この差分画像ΔｆＴ”と動き補償器９が出力する予測フレームｆＴ’とが加算されて、復元された対象フレームｆＴ”がフレームメモリ１３に格納される。これらの構成は、一般的な映像復号器と同様である。
【０１１７】
次に、本発明に係る動き推定装置８について説明する。図４は、本発明の実施例１に係る動き推定装置８の構成を表すブロック図である。
【０１１８】
動き推定装置８は、動きベクトル記憶手段２０、動きベクトル仮推定手段２１、代表値演算手段２２，２３、探索方法選択手段２４、動きベクトル決定手段２５、及び探索中心決定手段２６を備えている。
【０１１９】
動きベクトル記憶手段２０は、参照フレームｆＴ−１”及び対象フレームｆＴの各ブロックに対する動きベクトルＭＶ’，ＭＶを記憶するメモリである。
【０１２０】
動きベクトル仮推定手段２１は、動きベクトル記憶手段２０に記憶されている動きベクトルＭＶに基づき、対象フレームｆＴ内のブロックであって動きベクトル推定の対象となるブロック（対象ブロック）Ｃ０の動きベクトルＭＶ０の仮推定値ＭＶ０”を演算する。
【０１２１】
代表値演算手段２２は、対象ブロックＣ０の第１隣接の範囲Ｒ１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｊ（ｊ∈Ｒ１）の動きベクトルＭＶｊと、仮推定値ＭＶ０”との間の距離の代表値δＴを算出する。
【０１２２】
代表値演算手段２３は、対象ブロックＣ０に対応する参照フレームｆＴ−１”内のブロックＣ０’の動きベクトルＭＶ０’と、ブロックＣ０’の第１隣接の範囲Ｒ２内にある参照フレームｆＴ−１”内の各ブロックＣｉ’（ｉ∈Ｒ２）の動きベクトルＭＶｉ’との間の距離の代表値δＴ−１を算出する。
【０１２３】
探索方法選択手段２４は、代表値δＴ及び代表値δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から、代表値演算手段２２，２３により算出された代表値δＴ及び代表値δＴ−１の値に対応するブロック探索方法を選択する。
【０１２４】
探索中心決定手段２６は、動きベクトル決定手段２５が探索を行う際の探索中心のオフセットを決定する。
【０１２５】
動きベクトル決定手段２５は、探索方法選択手段２４により選択された探索方法に従って、探索中心決定手段２６により決定された探索中心を中心として、対象ブロックＣ０との相関が最大である参照フレームｆＴ−１”内のブロックの探索を行い、動きベクトルＭＶ０を決定し、動きベクトル記憶手段２０に保存する。
【０１２６】
探索方法選択手段２４は、動きタイプ決定手段３１，３２、及び探索方法選択手段３３を備えている。動きタイプ決定手段３１は、代表値演算手段２２が出力する代表値δＴの値を閾値判定し、対象ブロックＣ０の近傍の局所的な動きタイプＴＹＰＥ１を決定する。動きタイプ決定手段３２は、代表値演算手段２２が出力する代表値δＴ−１の値を閾値判定し、対象ブロックＣ０’の近傍の局所的な動きタイプＴＹＰＥ２を決定する。そして、探索方法選択手段３３は、局所的な動きタイプＴＹＰＥ１，ＴＹＰＥ２によって、探索方法の選択を行う。
【０１２７】
以上のように構成された本実施例に係る動き推定装置８について、以下その動き推定方法について説明する。動きベクトルの推定は、ラスタ走査の走査線に沿って、対象フレームの右上のブロックから左下のブロックに向かって行われるものとする。また、対象フレームの端に位置するブロックについては、全域探索法を用いて動きベクトルの推定が行われるものとする。以下では、対象フレームの端に位置するブロック以外の対象ブロックに対する動き推定動作について説明する。
【０１２８】
図５は本発明の実施例１に係る動き推定方法を表すフローチャートである。まず、動きベクトル仮推定手段２１は、動きベクトル記憶手段２０から図２に示したコンテキストＴの各ブロックの動きベクトルＭＶ１，ＭＶ２，ＭＶ３を読み出す。そして、対象ブロックＣ０の動きベクトルの仮推定値ＭＶ０”を（数２０）により算出する（Ｓ１）。
【０１２９】
【数２０】
【０１３０】
次に、代表値演算手段２２は、動きベクトル記憶手段２０から図２に示したコンテキストＴの各ブロックの動きベクトルＭＶ１，ＭＶ２，ＭＶ３を読み出す。そして、先に算出された動きベクトルの仮推定値ＭＶ０”と動きベクトルＭＶ１，ＭＶ２，ＭＶ３とに基づき、対象フレームｆＴ内における対象ブロックＣ０近傍の局所的な動き複雑性を算出する（Ｓ２）。ここでは、局所的な動き複雑性として、各ブロックＣｊ（ｊ∈Ｒ１）の動きベクトルＭＶｊと、仮推定値ＭＶ０”との間の距離の代表値δＴを用いる。従って、代表値演算手段２２は（数２１）により対象ブロックＣ０近傍の局所的な動き複雑性である代表値δＴを算出する。
【０１３１】
【数２１】
【０１３２】
一方、代表値演算手段２３は、動きベクトル記憶手段２０から図２に示したコンテキストＴ−１の各ブロックの動きベクトルＭＶ０’〜ＭＶ８’を読み出す。そして、これらの動きベクトルＭＶ０’〜ＭＶ８’に基づき、参照フレームｆＴ−１”内におけるブロックＣ０’近傍の局所的な動き複雑性を算出する（Ｓ３）。ここでは、局所的な動き複雑性として、各ブロックＣｉ’（ｉ∈Ｒ２）の動きベクトルＭＶｉ’と、ブロックＣ０’の動きベクトルＭＶ０’との間の距離の代表値δＴ−１を用いる。従って、代表値演算手段２３は（数２２）により対象ブロックＣ０近傍の局所的な動き複雑性である代表値δＴ−１を算出する。
【０１３３】
【数２２】
【０１３４】
次に、探索方法選択手段２４は、代表値δＴ及び代表値δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から、代表値演算手段２２，２３により算出された代表値δＴ及び代表値δＴ−１の値に対応するブロック探索方法を選択する（Ｓ４）。具体的には、まず、動きタイプ決定手段３１が、代表値δＴに基づき、（数９）に従って動きタイプＴＹＰＥＴを決定する。また、動きタイプ決定手段３２が、代表値δＴ−１に基づき、（数８）に従って動きタイプＴＹＰＥＴ−１を決定する。探索方法選択手段３３は、動きタイプＴＹＰＥＴ，ＴＹＰＥＴ−１により、（表１）に従って対象ブロックＣ０の動きタイプを決定する。そして、対象ブロックＣ０の動きタイプに基づき、（表２）に従って探索方法の選択を行う。このようにして、局所的な動き複雑性に従って、ブロックマッチングにおける探索戦略が適応的に決定される。
【０１３５】
次に、探索中心決定手段２６は、動きベクトル決定手段２５が探索を行う際の探索中心のオフセットＶを、（数１０）〜（数１２）に従って決定する（Ｓ５）。
【０１３６】
次に、動きベクトル決定手段２５は、探索方法選択手段２４により選択された探索方法に従って、対象ブロックＣ０との相関が最大である参照フレームｆＴ−１”内のブロックの探索を行う（Ｓ６）。このとき、ブロック探索は、ブロックＣ０”の位置から、ステップＳ５において決定されたオフセットＶだけ平行移動した位置を中心として行われる。これにより、対象ブロックＣ０の動きベクトルＭＶ０が決定される。
【０１３７】
最後に、動きベクトル決定手段２５は、動きベクトルＭＶ０を動きベクトル記憶手段２０に保存して（Ｓ７）、対象ブロックＣ０の動きベクトル推定動作を終了する。
【０１３８】
このような動きベクトル推定動作を、ラスタ走査の走査線に沿って、対象ブロックＣ０を移動させながら順次行うことにより、対象フレームｆＴの動きベクトル推定を行うことができる。
【０１３９】
尚、本実施例の動き推定装置は、映像の性質により適応的に探索戦略を変更できるため、映像内容が複雑な動きを示す場合であっても高い頑健性を得ることができるとともに、ハードウェア実装することもソフトウェア実装することも可能である。また、コンピュータ・プログラムとして構成し、汎用コンピュータによって実現することも可能である。
【図面の簡単な説明】
【０１４０】
【図１】テスト映像（ＣＩＦ）から得られたフレーム内の動きベクトルマップを表す図である。
【図２】ブロックマッチングを行うために使用されるコンテキストの一例である。
【図３】一般の映像符号化装置の全体構成を表す図である。
【図４】本発明の実施例１に係る動き推定装置８の構成を表すブロック図である。
【図５】本発明の実施例１に係る動き推定方法を表すフローチャートである。
【符号の説明】
【０１４１】
１ 映像符号化装置
２ フレームメモリ
３ 差分器
４ 離散コサイン変換器（ＤＣＴ）
５ 量子化器
６ エントロピ符号器
７ 局所復号器
８ 動き推定装置
９ 動き補償器
１０ 逆量子化器
１１ 逆離散コサイン変換器（逆ＤＣＴ）
１２ 加算器
１３ フレームメモリ
２０ 動きベクトル記憶手段
２１ 動きベクトル仮推定手段
２２，２３ 代表値演算手段
２４ 探索方法選択手段
２５ 動きベクトル決定手段
２６ 探索中心決定手段
３１，３２ 動きタイプ決定手段
３３ 探索方法選択手段
【技術分野】
【０００１】
本発明は、映像圧縮におけるブロックマッチングによる動き推定技術に関するものであり、特に、動きベクトルによっては捉えにくい映像の動きを感度よく検出することにより、適応的にブロックマッチングを行うことが可能な動き推定技術に関する。
【背景技術】
【０００２】
ブロックマッチング動き推定（Block Matching Motion Estimation：ＢＭＭＥ）は、ソフトウェア実装においてもハードウェア実装においても、現在のところ最も有力な動き推定（Motion Estimation：ＭＥ）方法であり、MPEG-1/2/4やH.216/263/263+等の種々の国際標準において採用されている。
【０００３】
ブロックマッチング動き推定において、判定基準（matching criterion）として、通常、（数１）で表される差分絶対値和（Sum of Absolution Difference：ＳＡＤ）が使用される。ここで、Ｍはブロックサイズを表す。また、ICとIRは、それぞれ、対象フレーム（current flame）内におけるブロックマッチングの対象のブロックである対象ブロック（current block）内の画素値、及び参照フレーム（reference frame）内において発見された再一致候補ブロック内の画素値を表す。
【０００４】
【数１】
【０００５】
しかしながら、ＢＭＭＥには、本質的に、極めて計算量が大きなタスクを内在していることは明らかである。そして、そのタスクは、ビデオエンコーダにおける全計算時間の６０％〜８０％をも占める程度の計算量であるとする試算が報告されている（非特許文献１参照）。特に総当たり法である全域探索ブロックマッチング（Full Search Block Matching：ＦＳＢＭ）の場合には、＋／−Ｎピクセルの探索領域に対して、探索点は(2N+1)2にものぼる。
【０００６】
そこで、従来、ＭＥの改良技術として、二次元対数探索法（2-D Logarithmic Search ：ＬＯＣＳ）（非特許文献２参照）、３段探索法（Three Step Search ：ＴＳＳ）（非特許文献３，１１参照）、４段探索法（Four Step Search ：ＦＳＳ）（非特許文献４参照）、ダイヤモンド探索法（Diamond Search ：ＤＳ）（非特許文献５，６参照）等、多くの高速探索技術が提案されている。ＦＳＢＭとは異なり、これらのアルゴリズムは、探索時間の大幅な短縮を理論的に達成するために、予め定義された探索パターンを用いることによって、探索点数を削減する手法を採用している。しかしながら、それにより、ハードウェア実装が困難となる。また、このような剛的な探索戦略（rigid search strategy）を採用すると、その探索戦略は様々な種類の映像に対して常に最適であるとは限らない。そのため、いくつかの映像に対しては、マッチング品質が低下するというリスクも大きくなる。
【０００７】
その後、映像内容の動き複雑性に従って、ＢＭの探索戦略を動的に適応化させることにより、映像の歪みを抑えコンピュータの処理コストを低減させることを目的として、適応的動き推定アルゴリズム（Adaptive motion estimation algorithm）が考案された。大部分の適応的動き推定アルゴリズムは、予め複数の探索パターンを用意しておき、対象ブロックに対する動きタイプ予測の結果により、最適な探索戦略を選択するものである。動きベクトル場適応探索法（Motion Vector Field Adaptive Search Technique ：ＭＶＦＡＳＴ）では、動きタイプ予測において空間的相関が利用されている（非特許文献７参照）。また、予測動きベクトル場適応探索法（Predictive Motion Vector Field Adaptive Search Technique：ＰＭＶＦＡＳＴ）においては、時間的に配列されたブロックも動きタイプ予測の考慮の対象となる（非特許文献８参照）。そして、予測された動きタイプに従って、大ダイヤモンド探索（Large Diamond Search：ＬＤＳ）又は小ダイヤモンド探索（Small Diamond Search：ＳＤＳ）が選択される。更に、非特許文献９においては、より洗練された動きタイプ予測アルゴリズムが導入されている。
【特許文献１】特開２００３−３２４７４３号公報
【特許文献２】特開２００３−２７４４１６号公報
【特許文献３】特開２００２−１５２７６０号公報
【特許文献４】特開２００２−１３５７８４号公報
【非特許文献１】P.M. Kuhn, G. Diebel, S. Hermann, A. Keil, H. Mooshofer, A. Kaup, et al. "Complexity and PSNR-comparison of several fast motion estimation algorithms for MPEG4," in Proceeding of Applications of Digital Image Processing ;XXI, San Diego. SPIE, vol. 3460, pp. 486-499, July, 1998.
【非特許文献２】J. R. Jain and A. K. Jain, "Displacement measurement and its application in interframe image coding," IEEE Trans. Commun., vol. 29, pp. 1799-1808, Dec. 1981.
【非特許文献３】T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, "Motion-compensated interframe coding for video conferencing," in Proc. Nat. Telecommunications Conf., pp.G 5.3.1-G 5.3.5., Nov./Dec. 1981.
【非特許文献４】L. M. Po, and W. C. Ma " A novel Four-Step Search Algorithm for fast blockmatching," IEEE Trans. Circuits Syst. Video Technol., vol. 6, Jun. 1996.
【非特許文献５】G. Cote, M. Gallant, and F. Kossentini, " Efficient motion vector estimation and coding for H.263-based very low bit rate video compression," ITU-T SG 16, Q15-A-45, June 1997.
【非特許文献６】J.Y. Tham, S. Ranganath, M. Ranganath, and A.A. Kassim, "A novel unrestricted center-biased diamond search algorithm for block motion estimation," IEEE Trans. On Circuits & Systems for Video Technology, vol.8, pp.369-377, Aug. 1998.
【非特許文献７】P. I. Hosur and K.K. Ma, "Motion Vector Field Adaptive Fast Motion Estimation," Second International Conference on Information, Communications and Signal Proeessing (IClCS '99). Singapore, 7-lO, Dec. 1999.
【非特許文献８】A. M. Tourapisl, O. C. Au2, and M. L. Liou "Predictive Motion Vector Field Adaptive Search Technique (PMVFAST) - Enhancing Block Based Motion Estimation," in Proc. SPIE, Visual Commuaications and Image Processing, vol. 431O, pp. 883-892, Dec. 2000.
【非特許文献９】J.H. Lim, and H.W. Choi, "Adaptive motion estimation algorithm using spatial and temporal correlation," Pacific Rim (PACRIM) Conference on Communications, Computers and signal Processing, vol.2, pp.26-28 Aug. 2001.
【非特許文献１０】T. Sappasitwong, and S. Aramvith, " Adaptive asymmetric diamond search algorithm for block-based motion estimation," International Conference on Digital Signal Processing, vol.2, pp.1-3, July . 2002.
【非特許文献１１】酒井善則，吉田俊之共著，「ヒューマンコミュニケーション工学シリーズ 映像情報符号化」，第１版，株式会社オーム社，２００１年１２月２０日，pp.121-141.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上述の適応的動き推定アルゴリズムは、計算速度とマッチング品質において、従前のアルゴリズムに比べて、より優れた性能が得られることが期待される。しかしながら、上述の適応的動き推定アルゴリズムは、ハードウェア実装をする場合には理想的ではないと考えられる複数の高速探索方法を採用している。更に、フレーム間のエラー伝搬の問題も深刻である。
【０００９】
そこで、本発明の目的は、正確な動きタイプの予測が可能であり、映像内容が複雑な動きを示す場合であっても高い頑健性（robustness）を得ることができる動き推定技術を提供することにある。
【課題を解決するための手段】
【００１０】
最初に本発明に係る動き推定方法について基本となる考え方について説明した後、本発明の構成、作用についての説明を行う。
【００１１】
〔１〕観察
映像は多種多様であるが、それらはすべて映像系列を一つのフレームのセットと見なすことができる。一つのフレーム内における動きは一般に複雑である。しかし、一つのフレームを、いくつかの典型的な動きタイプにマッピングすることのできる部分に切り分けることは可能である。これは、動きタイプの予測を行うにあたっての基礎となる。種々の映像を観察した結果、本発明者は以下のように要約される２つの結論を得た。
【００１２】
（ａ）動きタイプの定義は動き複雑性に基づいている。
近年における研究では（非特許文献９，１０参照）、動きタイプ（motion types）は動き複雑性（motion complexity）に基づいて定義される。「動き複雑性」とは、予測変数である各動きベクトル（motion vector）の間の相関のことをいう。
【００１３】
例えば、図１に例示したフレームでは、フレームの上部においては均一な動きが検出される。均一な動きは、動きがどんなに速くても、大域的な動きベクトルのオフセットを差し引くことにより、固定的な領域に変換できるため、困難は生じない。
【００１４】
（ｂ）動きベクトルは往々にして真の動きを正確に表さない場合がある。
動きベクトルは、映像の符号化において予測誤差を最小化するのに役立つものであるが、動きベクトルは必ずしも映像の真の動きを記述するものではないという点に「トラップ」がある。すなわち、ブロックマッチングによって得られる動きベクトルは、実際には「フレーム間の動き」を表すベクトルではなく、むしろ「フレーム間の冗長性を最も除去可能なベクトル」と解釈されるべきものである。例えば、均一なテクスチャは視覚的な識別性に乏しい。従って、図１において、フレームの下の部分（すなわち、グラウンドに相当する部分）において、均一な動きは動きベクトルとしては捉えられない。
【００１５】
〔２〕局所的な動きタイプ予測
上記の観察に基づき、本発明に係る動き推定においては、動きタイプの予測は対象ブロック（ブロックマッチングの対象であるブロック）の周囲の動き複雑性の分析に基づいて行われる。動きベクトルの分布を動き複雑性の分析の基礎として利用することにより、動きベクトルが真の動きを捉えることに失敗したときに、上記「トラップ」に陥るのを避けることができる。
【００１６】
対象ブロックの近傍に位置するいくつかのブロックを、ブロックマッチングを行うためのコンテキストを形成するブロックとして選択する。図２は、ブロックマッチングを行うために使用されるコンテキストの一例である。
【００１７】
コンテキストＴは、対象フレーム内のブロックから構成されるコンテキストであって、対象ブロックＣ０の第１隣接にある３つのブロックＣ１，Ｃ２，Ｃ３により構成されるコンテキストである。ここで、「第１隣接」とは、対象ブロックのいずれかの辺又は頂点に対し、いずれかの辺又は頂点が接しているブロックをいう。
【００１８】
対象フレームのブロックマッチングは、ラスタスキャンの走査方向に沿って、フレームの左上のブロックから右下のブロックにかけて、右向きの水平方向の反復走査に沿って行われる。従って、図２において、コンテキストＴのブロックＣ１，Ｃ２，Ｃ３はすでに動きベクトルが決定されたブロックである。また、参照フレームについては、すでにすべてのブロックについて動きベクトルが決定されている。
【００１９】
また、コンテキストＴ−１は、参照フレーム内のブロックから構成されるコンテキストであって、対象ブロックＣ０の位置に対応する参照フレーム内のブロックＣ０’及びその第１隣接に位置するブロックＣ１’〜Ｃ８’により構成されるコンテキストである。
【００２０】
本発明に係る動き推定においては、従来提案されている動き推定法（非特許文献９，１０参照）とは異なり、ブロックマッチングにおいて空間的な相関を引き出すために、対象フレーム及び参照フレームから数ブロックを抽出し、これを対象ブロックＣ０の動き推定に利用することにある。このように一般化した隣接ブロックは、２つの連続したフレームに含まれる局所的な動きの情報を引き出すためのサンプルとして利用される。動き複雑性の解析は、コンテキストＴ−１とコンテキストＴに対して、以下の２つの評価に基づいて行われる。
【００２１】
【数２】
【００２２】
【数３】
【００２３】
ここで、ＭＶｉ’（ｉ＝０，１，…，８）は、コンテキストＴ−１におけるブロックＣｉ’の動きベクトルを表す。ＭＶｉ（ｉ＝１，２，３）は、コンテキストＴにおけるブロックＣｉ’の動きベクトルを表す。δＴ−１，δＴは、それぞれ参照フレーム、対象フレームにおける局所的な動き複雑性を表す。これらは、予測変数として用いられる動きベクトルの関数として定義される。
【００２４】
本発明においては、局所的な動き複雑性を規定する関数として、対象ブロックＣ０及びそれに対応するブロックＣ０’の動きベクトルＭＶ０，ＭＶ０’と、コンテキストＴ，Ｔ−１内の他のブロックＣｉ，Ｃｉ’の動きベクトルＭＶｉ，ＭＶｉ’との間の距離の代表値を使用する。すなわち、局所的な動き複雑性δＴ−１，δＴを（数４）、（数５）により定義する。特に、コンテキストＴ−１は対称的な構造であり、すべての方向からの動き特性の変化を捉えることができるので、（数４）は敏感な特性値（indicator）となる。
【００２５】
【数４】
【００２６】
【数５】
【００２７】
ここで、ＲｅｐＴ−１，ＲｅｐＴは、それぞれ、代表値関数である。代表値関数としては、最大値、最頻値、中央値、平均値、総和等を使用することができる。‖・‖は、ベクトルのノルムを表す。また、動きベクトルＭＶ０については、現時点では求まっていないので、δＴの演算においては、動きベクトルＭＶ０の代わりにその仮推定値ＭＶ０”＝ＭＶ０”（ＭＶ１，ＭＶ２，ＭＶ３）を使用する。ＭＶ０”の演算式についても、種々の方法が考えられる。
【００２８】
より具体的には、局所的な動き複雑性δＴ−１，δＴとして（数６）、（数７）を使用することができる。
【００２９】
【数６】
【００３０】
【数７】
【００３１】
上記のようなコンテキストＴ−１，Ｔの局所的な動き複雑性δＴ−１，δＴに従って、コンテキストＴ−１，Ｔの動きタイプＴＹＰＥＴ−１，ＴＹＰＥＴの分類を行う。動きタイプの分類の決定は、（数８）、（数９）に示すような閾値判定により行うことができる。
【００３２】
【数８】
【００３３】
【数９】
【００３４】
ここで、Ｔｈ１，Ｔｈ２は動きタイプを分類するための閾値を表す。閾値Ｔｈ１，Ｔｈ２を適当な値に選択することによって、時間的及び空間的な予測変数の影響の度合いを調節することができる。
【００３５】
次のステップでは、時間コヒーレンス（temporal coherence）を考慮して、前記ＴＹＰＥＴ−１，ＴＹＰＥＴに基づき、対象ブロックＣ０について、最も可能性の高い動きタイプを予測する。対象ブロックＣ０の動きタイプの予測は、（表１）に従って行うことができる。
【００３６】
【表１】
【００３７】
対象ブロックＣ０の動きタイプを用いることにより、対象ブロックＣ０の動きベクトルＭＶ０のより確実な予測を行うことが可能となる。例えば、均一なテクスチャ部分が高速に動いている場合において、ＭＶ６’以外の他のすべての動きベクトルが動きを捉えていない場合においても、ＭＶ６’が動きを捉えている限りは、上記動きタイプ予測によって、対称ブロックＣ０は激しい動きにあることを検出することが可能となる。これに対して、従来の他の動き推定方法では、このような動き検出をすることはできない。
【００３８】
〔３〕適応的ブロックマッチング
以上のような推定により得られる動きタイプを用いて、本発明では以下のような適応的ブロックマッチングにより動き推定を行う。
【００３９】
（１）ステップ１
上述の局所的な動きタイプ予測を実行した後、（数１０）により４つの探索中心候補を決定する。各ベクトルＶｉ＝（ｖｘｉ，ｖｙｉ）は、対象ブロックＣ０に対応するブロックＣ０’の中心位置から探索の中心となる点までのオフセットを表すベクトルである。
【００４０】
【数１０】
【００４１】
ベクトルＶ３，Ｖ４は、それぞれ、参照フレーム内のブロックＣ０’の右上半面、左下半面に属するブロックの動きベクトルの代表値を表す。ここでは、ベクトルＶ３，Ｖ４として、（数１１）の値を使用する。
【００４２】
【数１１】
【００４３】
（２）ステップ２
上記４つの探索中心候補の中で最良の探索中心を表すベクトルＶを選択する。この選択は、（数１２）によりＳＡＤを計算することによって行う。
【００４４】
【数１２】
【００４５】
ここで、ＩＴ，ＩＴ−１は、それぞれ、対象ブロック、参照ブロックの画素値を表す。また、演算子argmin（・）の部分は、「（・）を最小にするＶｋ」を表している。
【００４６】
（３）ステップ３
最後に、選択されたベクトルＶをオフセットとして、ブロック探索を行う。このとき、上記予測により得られた対象ブロックＣ０の動きタイプによって、対象ブロックＣ０の動きベクトルを決定するための探索方法の選択を行う。この場合、対象ブロックＣ０の動きタイプが‘ＣＨＡＯＳ’の場合、対象ブロックＣ０の近傍の動きは複雑であることが予測される。従って、動きベクトルの探索方法は広範囲の探索に適した方法を選択する必要がある。対象ブロックＣ０の動きタイプが‘ＣＲＩＴＩＣＡＬ’の場合、対象ブロックＣ０の近傍の動きは複雑な動きから一様な動きに変化する境界付近にあることが予測される。従って、この場合、動きベクトルの探索方法は中程度の範囲の探索に適した方法を選択する必要がある。対象ブロックＣ０の動きタイプが‘ＳＩＭＰＬＥ’の場合、対象ブロックＣ０の近傍の動きは一様であることが予測される。従って、動きベクトルの探索方法は狭範囲の探索に適した方法を選択する必要がある。
【００４７】
そこで、例えば、対象ブロックＣ０の動きタイプによって、（表２）のように探索方法を選択することができる。
【００４８】
【表２】
【００４９】
ここで、ＦＳは全域探索（Full Search）法、ＴＳＳは３段探索（Three Step Search）法を表す。Nsimple，Ncritical，Nchaosは探索範囲を表す。例えば、Nsimpleの場合には、Nsimple×Nsimpleの領域において探索を行うことを表している。ここで、Nsimple，Ncritical，Nchaosの間には（数１３）のような関係がある。
【００５０】
【数１３】
【００５１】
‘ＳＩＭＰＬＥ’の場合、小さいウィンドウ内に探索領域を限定することによって、かなりの量の無駄な計算を省くことができる。
【００５２】
‘ＣＲＩＴＩＣＡＬ’の場合、対象フレームの動き複雑性は参照フレームの動き複雑性よりも低くなる。従って、ほとんどの場合、（数１２）によりかなり信頼性の高い探索中心のオフセットを予測することができる。従って、ブロックマッチングにおける探索範囲は小さくてもよい。しかしながら、上述した「トラップ」を考慮して、探索領域はNsimpleよりも大きくあるべきである。
【００５３】
‘ＣＨＡＯＳ’の場合には、それぞれの動きベクトル間の相関が小さいので、ブロックマッチングを行う際の探索範囲は大きめにとる必要がある。しかしながら、探索中心はオフセットによりシフトされる。また、動きベクトルの探索領域の大きさは、探索によって得られる動きベクトルの大きさが実用範囲内となる程度に制限される。従って、探索範囲の大きさは一定サイズの領域に限定されるので、動き複雑性が大きい場合でも計算量は減少すると考えられる。動きベクトルの探索は、螺旋パターン（spiral pattern）により従って実行し、早期打ち切り法（early break technique）を用いることができる。
【００５４】
また、それぞれの場合において、同じＳＡＤの候補が２つ以上見つかった場合には、対象ブロックＣ０の位置により近い方を採用すればよい。
【００５５】
〔４〕本発明の構成及び作用
本発明に係る動き推定方法の第１の構成は、複数のフレームから構成される映像において、参照フレームに対する対象フレーム内の各ブロックの動きベクトルを推定する動き推定方法であって、前記対象フレーム内における動きベクトル推定の対象となるブロック（以下、「対象ブロック」という。）Ｃ０との相関が最大である前記参照フレーム内のブロックの探索を、以下の各ステップを有する選択手順で選択されたブロック探索方法に従って行うことにより、前記対象ブロックＣ０の動きベクトルＭＶ０を決定することを特徴とする：
（１）前記参照フレーム又は前記対象フレームの各ブロックの動きベクトルであって既に決定されているものに基づき、前記対象ブロックＣ０の動きベクトルＭＶ０の仮推定値ＭＶ０”を決定する第１ステップ；
（２）前記仮推定値ＭＶ０”と、前記対象フレーム内における前記対象ブロックＣ０周囲の所定の範囲Ｒ１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｊ（ｊ∈Ｒ１）の動きベクトルＭＶｊとの間の距離の代表値δＴを算出する第２ステップ；
（３）前記対象ブロックＣ０に対応する前記参照フレーム内のブロックＣ０’の動きベクトルＭＶ０’と、前記ブロックＣ０’の周囲の所定の範囲Ｒ２内にある前記参照フレーム内の各ブロックＣｉ’（ｉ∈Ｒ２）の動きベクトルＭＶｉ’との間の距離の代表値δＴ−１を算出する第３ステップ；
（４）前記代表値δＴ及び前記代表値δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から、前記第２ステップ及び前記第３ステップで算出された前記代表値δＴ及び前記代表値δＴ−１の値に対応するブロック探索方法を選択する第４ステップ。
【００５６】
この構成により、対象ブロックＣ０の動きベクトルの仮推定値に対する対象ブロックＣ０の周囲のブロックの局所的な動きベクトルのばらつきの度合い（以下、「局所的な動き複雑性（local motion complexity）」という。）に応じて、適応的にブロック探索方法を決定することができる。「局所的な動き複雑性」とは、対象ブロックＣ０の動きベクトルに対するその周囲の動きベクトルの変化の度合いをいう。この局所的な動き複雑性は、第２ステップ及び第３ステップで演算される代表値δＴ及びδＴ−１の値により評価される。
【００５７】
すなわち、第２、第３ステップにおいて、対象フレームにおける対象ブロックＣ０を中心とする局所的な動き複雑性と、参照フレーム内におけるブロックＣ０’を中心とする局所的な動き複雑性とが算出される。そして、第４ステップにおいて、それらを参照し、局所的な動き複雑性が大きい場合には、広範囲のブロック探索に適したブロック探索方法を選択し、局所的な動き複雑性が小さい場合には狭範囲のブロック探索に適したブロック探索方法を選択することが可能となる。これにより、ブロック探索に要する演算量を現実的な演算量に抑えつつ、動きが小さい場合において動きベクトルの推定精度を高く維持することができるとともに、動きが大きい場合に動きベクトルの予測が大きく外れることを防止することが可能となる。
【００５８】
特に、対象ブロックＣ０の周囲の「局所的な動き複雑性」と参照フレーム内におけるブロックＣ０’の周囲の「局所的な動き複雑性」との双方を評価することで、一様なテクスチャが高速に移動する部分のように、対象ブロックＣ０の周囲に動きがあるにもかかわらずそれが動きベクトルに動きが反映されにくい状態にある映像に対しても、動きの存在を敏感に捉えることが可能となる。すなわち、正確な動きタイプの予測が可能となり、映像内容が複雑な動きを示す場合であっても高い頑健性を得ることができる。そして、捉えられた動きタイプに応じて、適応的にブロック探索方法が選択されるため、高いマッチング品質を得ることができる。そして、捉えられた動きに応じて、適応的にブロック探索方法が選択されるため、残留予測誤差を更に小さくし、映像の圧縮率を改善することができる。
【００５９】
ここで、「ブロック」とは、動き補償による画像の符号化を行う際に、一つの動きベクトルに対応させる領域の単位をいう。通常は、１６×１６画素のブロックを使用するが、本発明においてはブロックの大きさは特に限定しない。
【００６０】
「ブロック探索方法」とは、対象フレーム内の対象ブロックＣ０との相関が最大である（最も一致する）参照フレーム内のブロックの探索を行う方法をいう。本発明においては、「ブロック探索方法」は、特に限定するものではないが、例えば、全域探索法（Full Search Technique）、二次元対数探索法（2-D Logarithmic Search Technique）（非特許文献２参照）、多段探索法（３段探索法（Three Step Search Technique）、４段探索法（Four Step Search Technique）等）（非特許文献３，４，１１参照）、動きベクトル場適応探索法（Motion Vector Field Adaptive Search Technique）（非特許文献７参照）、ダイヤモンド探索法（Diamond Search Technique）（非特許文献５，６参照）等を使用することが可能である。
【００６１】
第４ステップにおいては、通常、代表値δＴの値が小さい場合には、対象ブロックＣ０近傍の「局所的な動き複雑性」は小さいと考えられるので、「ブロック探索方法」としてはマッチング誤差を最小化することが可能な全域探索法を選択するようにし、代表値δＴの値が大きい場合には、対象ブロックＣ０近傍の局所的な動き複雑性は大きいと考えられるので、「ブロック探索方法」としては、多段探索法、動きベクトル場適応探索法、ダイヤモンド探索法等の広い領域を高速に探索できる方法を選択するように設定しておくことが好ましい。
【００６２】
「動きベクトル」とは、参照フレームと対象フレーム間において、映像が動いた方向と距離を表す動き量のことをいう。
【００６３】
動きベクトルＭＶ０の仮推定値ＭＶ０”の決定方法は、ここでは特に限定はしない。この仮推定値ＭＶ０”の決定方法としては、例えば、対象ブロックＣ０の近傍にある対象フレーム内のブロックのうち動きベクトルが既に決定されているものの集合をＲ３とした場合、集合Ｒ３に属するブロックの動きベクトルの平均値、中央値、最頻値、加重平均値等を仮推定値ＭＶ０”とする方法などを採ることができる。
【００６４】
「所定の範囲Ｒ１」は、対象ブロックＣ０の近傍であって、対象ブロックＣ０の動きベクトルとの相関が大きい動きベクトルを有するブロックの範囲に定められる。本発明では特に「所定の範囲Ｒ１」は特に限定しないが、通常は、対象ブロックＣ０の第１隣接又は第２隣接までを含む範囲に設定される。
【００６５】
「所定の範囲Ｒ２」は、ブロックＣ０’の近傍であって、ブロックＣ０’の動きベクトルとの相関が大きい動きベクトルを有するブロックの範囲に定められる。本発明では特に「所定の範囲Ｒ２」は特に限定しないが、通常は、ブロックＣ０’の第１隣接又は第２隣接までを含む範囲に設定される。
【００６６】
２つの動きベクトルの間の「距離」とは、動きベクトル空間における２つの動きベクトルの間の空間的な隔たりをいう。「距離」としては、差分絶対値和（Sum of Absolute Difference : ＳＡＤ）、平均平方誤差（Mean square error : MSE）、平均絶対誤差（mean absolute error : MAE）、ユークリッド距離等を使用することができる。
【００６７】
距離の「代表値」とは、変数の分布を要約する統計量のことをいう。「距離の代表値δＴ」としては、最大値、最小値、中央値、平均値、最頻値、総和、自乗和、平方和等を使用することができる。
【００６８】
本発明に係る動き推定方法の第２の構成は、前記第１の構成において、前記第４ステップにおいて、前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合には、ブロック探索方法として、所定の探索領域における多段探索法を選択し、前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合には、ブロック探索方法として、前記多段探索法の探索領域よりも狭い探索領域での全域探索法を選択することを特徴とする。
【００６９】
この構成によれば、代表値δＴの値の閾値判定によって、対象ブロックＣ０の近傍の局所的な動き複雑性に応じて動きベクトルの探索方法を適応的に切り替えることが可能となる。また、閾値判定であるため、簡単なアルゴリズムにより実現可能であり、また、ハードウェアによって回路的に実現する場合の回路構成も簡易である。
【００７０】
ここで、「所定の閾値Ｔｈ１」は、実験的に設定する値である。また、「所定の閾値Ｔｈ１」は、必ずしも固定値とする必要はなく、動き推定の精度の要求に応じて、外部から自由に設定できるようにしてもよい。
【００７１】
本発明に係る動き推定方法の第３の構成は、前記第１又は２の構成において、前記第４ステップにおいて、前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合においては、ブロック探索方法として、所定の探索領域Ｓ０における多段探索法を選択し、前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合においては、前記代表値δＴ−１の値が所定の閾値Ｔｈ２よりも大きい場合には、ブロック探索方法として、前記多段探索法の探索領域Ｓ０と同じ又はより狭い探索領域Ｓ１での全域探索法を選択し、前記代表値δＴ−１の値が所定の閾値Ｔｈ２以下の場合には、ブロック探索方法として、前記探索領域Ｒ１よりも狭い探索領域Ｓ２での全域探索法を選択することを特徴とする。
【００７２】
この構成によれば、代表値δＴ及び代表値δＴ−１の値の閾値判定によって、対象ブロックＣ０及びブロックＣ０’の近傍の局所的な動き複雑性に応じて動きベクトルの探索方法を適応的に切り替えることが可能となる。また、閾値判定であるため、簡単なアルゴリズムにより実現可能であり、また、ハードウェアによって回路的に実現する場合の回路構成も簡易である。
【００７３】
ここで、各場合における探索領域Ｓ０，Ｓ１，Ｓ２の大きさは、それぞれ、要求される計算速度、計算精度等に応じて適度な大きさに設定することができる。
【００７４】
また、「所定の閾値Ｔｈ１，Ｔｈ２」は、実験的に設定する値である。また、「所定の閾値Ｔｈ１，Ｔｈ２」は、必ずしも固定値とする必要はなく、動き推定の精度の要求に応じて、外部から自由に設定できるようにしてもよい。
【００７５】
本発明に係る動き推定方法の第４の構成は、前記第１乃至３の何れか一の構成において、前記第１ステップにおいて、前記仮推定値ＭＶ０”は、前記対象フレーム内における前記対象ブロックＣ０周囲の所定の範囲Ｒ３内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｋ（ｋ∈Ｒ３）の動きベクトルＭＶｋに基づいて決定されることを特徴とする。
【００７６】
この構成により、走査に従って、対象ブロックＣ０の前に決定された動きベクトルを用いて対象ブロックＣ０の動きベクトルの仮推定値ＭＶ０”を決定することができる。
【００７７】
ここで、「所定の範囲Ｒ３」は特に限定しないが、通常は、対象ブロックＣ０の第１隣接又は第２隣接までを含む範囲に設定される。
【００７８】
「動きベクトルＭＶｋに基づいて」とは、例えば、動きベクトル｛ＭＶｋ｜∀ｋ∈Ｒ３｝の平均値、中央値、最頻値等を仮推定値ＭＶ０”に決定することをいう。また、ラスタスキャンに従って対象ブロックＣ０の動きベクトルＭＶ０を決定していく場合には、対象ブロックＣ０の上の行のブロックと、対象ブロックＣ０の行における対象ブロックＣ０の左側のブロックについては、既に動きベクトルが決定されている。そこで、対象ブロックＣ０の左の隣接ブロックをＣａ、左上の隣接ブロックをＣｂ、上の隣接ブロックをＣｃとすれば、例えば、ＭＶ０”＝ＭＶａ＋ＭＶｃ−ＭＶｂのようにして、二次元の画素値予測方法と同様な方法により仮推定値ＭＶ０”を決定するようにしてもよい。
【００７９】
本発明に係る動き推定方法の第５の構成は、前記第４の構成において、前記仮推定値ＭＶ０”は、（数１４）により計算されることを特徴とする。
【００８０】
【数１４】
【００８１】
この構成によれば、前記仮推定値ＭＶ０”として、｛ＭＶｋ｜∀ｋ∈Ｒ３｝の中央値を用いることで、簡単なアルゴリズムにより仮推定値ＭＶ０”を決定することができる。
【００８２】
本発明に係る動き推定方法の第６の構成は、前記第１乃至５の何れか一の構成において、第２ステップにおいて、所定の範囲Ｒ１は、前記対象ブロックＣ０に対し第１隣接のブロックであって、かつ既に動きベクトルが決定されている４つのブロックの内の一部又は全部のブロックであることを特徴とする。
【００８３】
このように、対象ブロックＣ０周囲の局所的な動き複雑性の検出に、対象ブロックＣ０に対し第１隣接のブロックを使用することで、対象ブロックＣ０から離れたブロックの動きベクトルの影響を受けずに、対象ブロックＣ０の周囲の局所的な動き複雑性を検出することができる。従って、ブロック探索方法の選択において、無駄に広域探索の方法が選択されることを防止することができる。
【００８４】
本発明に係る動き推定方法の第７の構成は、前記第１乃至５の何れか一の構成において、第２ステップにおいて、代表値δＴは、（数１５）により計算されることを特徴とする。
【００８５】
【数１５】
【００８６】
このように、代表値δＴとして動きベクトルの差分絶対値和（ＳＡＤ）を用いれば、代表値δＴの演算が、局所的な動き複雑性をよく表し、かつ簡単なアルゴリズムにより実現可能となる。
【００８７】
本発明に係る動き推定方法の第８の構成は、前記第１乃至７の何れか一の構成において、前記第３ステップにおいて、前記所定の範囲Ｒ２は、前記ブロックＣ０’に対して隣接する８つのブロックの範囲であることを特徴とする。
【００８８】
このように、ブロックＣ０’に対して隣接する８つのブロックを参照して局所的な動き複雑性を評価することで、すべての方向からの動き特性の変化を捉えることができる。従って、代表値δＴ−１は、動きの特性の変化を捉える敏感な特性値となる。
【００８９】
本発明に係る動き推定方法の第９の構成は、前記第１乃至７の何れか一の構成において、前記第３ステップにおいて、前記代表値δＴ−１は、（数１６）により計算されることを特徴とする。
【００９０】
【数１６】
【００９１】
このように、最大値を利用することで、動き特性の変化に対する敏感性を高め、任意方向に起こる動き特性の変化を正確に捉えることができる。
【００９２】
本発明に係る動き推定装置の第１の構成は、複数のフレームから構成される映像において、参照フレームに対する、対象フレームにおける各ブロックの動きベクトルを推定する動き推定装置であって、前記参照フレーム及び前記対象フレームの各ブロックに対する動きベクトルを記憶する動きベクトル記憶手段と、前記動きベクトル記憶手段に記憶されている動きベクトルに基づき、前記対象フレーム内のブロックであって動きベクトル推定の対象となるブロック（以下、「対象ブロック」という。）Ｃ０の動きベクトルＭＶ０の仮推定値ＭＶ０”を演算する動きベクトル仮推定手段と、前記対象ブロックＣ０周囲の所定の範囲Ｒ１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｊ（ｊ∈Ｒ１）の動きベクトルＭＶｊと、前記仮推定値ＭＶ０”との間の距離の代表値δＴを算出する第１の代表値演算手段と、前記対象ブロックＣ０に対応する前記参照フレーム内のブロックＣ０’の動きベクトルＭＶ０’と、前記ブロックＣ０’の周囲の所定の範囲Ｒ２内にある前記参照フレーム内の各ブロックＣｉ’（ｉ∈Ｒ２）の動きベクトルＭＶｉ’との間の距離の代表値δＴ−１を算出する第２の代表値演算手段と、前記代表値δＴ及び前記代表値δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から、前記第１の代表値演算手段により算出された前記代表値δＴ及び前記代表値δＴ−１の値に対応するブロック探索方法を選択する探索方法選択手段と、前記探索方法選択手段により選択された探索方法に従って、前記対象ブロックＣ０との相関が最大である前記参照フレーム内のブロックの探索を行い、前記動きベクトルＭＶ０を決定し、前記動きベクトル記憶手段に保存する動きベクトル決定手段とを備えていることを特徴とする。
【００９３】
この構成によれば、動きベクトル仮推定手段は、動きベクトル記憶手段に記憶されている動きベクトルに基づき、対象ブロックＣ０の動きベクトルＭＶ０の仮推定値ＭＶ０”を演算する。第１の代表値演算手段は、この仮推定値ＭＶ０”と各動きベクトルＭＶｊとの間の距離の代表値δＴを算出する。第２の代表値演算手段は、動きベクトルＭＶ０’と各動きベクトルＭＶｊ’との間の距離の代表値δＴ−１を算出する。次いで、探索方法選択手段は、代表値δＴ及び代表値δＴ−１の値に対応するブロック探索方法を選択する。そして、動きベクトル決定手段は、選択された探索方法に従って、参照フレーム内のブロックの探索を行い、動きベクトルＭＶ０を決定し、動きベクトル記憶手段に保存する。以上の動作を繰り返すことによって、対象フレーム内の各ブロックの動きベクトルが順次決定される。
【００９４】
このとき、動きベクトルの探索方法は、対象ブロックＣ０を中心とする「局所的な動き複雑性」及び対象ブロックＣ０’を中心とする「局所的な動き複雑性」の両方に適応して選択される。これにより、ブロック探索に要する演算量を現実的な演算量に抑えつつ、動きが小さい場合において動きベクトルの推定精度を高く維持することができるとともに、動きが大きい場合に動きベクトルの予測が大きく外れることを防止することが可能となる。
【００９５】
また、対象ブロックＣ０の動きベクトルの仮推定値が真の動きを捉えていない場合においても、対象ブロックＣ０及び対象ブロックＣ０’の双方の周囲の「局所的な動き複雑性」を評価することで、対象ブロックＣ０のみに着目する場合よりも、動きの存在をより敏感に捉え易くなる。そして、捉えられた動きに応じて、適応的にブロック探索方法が選択されるため、残留予測誤差をより小さくし、映像の圧縮率を改善することができる。
【００９６】
本発明に係る動き推定装置の第２の構成は、前記第１の構成において、前記探索方法選択手段は、前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合には、ブロック探索方法として、所定の探索領域における多段探索法を選択し、前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合には、ブロック探索方法として、前記多段探索法の探索領域よりも狭い探索領域での全域探索法を選択することを特徴とする。
【００９７】
本発明に係る動き推定装置の第３の構成は、前記第１又は２の構成において、前記探索方法選択手段は、前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合においては、ブロック探索方法として、所定の探索領域Ｓ０における多段探索法を選択し、前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合においては、前記代表値δＴ−１の値が所定の閾値Ｔｈ２よりも大きい場合には、ブロック探索方法として、前記多段探索法の探索領域Ｓ０と同じ又はより狭い探索領域Ｓ１での全域探索法を選択し、前記代表値δＴ−１の値が所定の閾値Ｔｈ２以下の場合には、ブロック探索方法として、前記探索領域Ｒ１よりも狭い探索領域Ｓ２での全域探索法を選択することを特徴とする。
【００９８】
本発明に係る動き推定装置の第４の構成は、前記第１乃至３の何れか一の構成において、前記動きベクトル仮推定手段は、前記対象フレーム内における前記対象ブロックＣ０周囲の所定の範囲Ｒ３内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｋ（ｋ∈Ｒ３）の動きベクトルＭＶｋに基づいて前記仮推定値ＭＶ０”を決定することを特徴とする。
【００９９】
本発明に係る動き推定装置の第５の構成は、前記第４の構成において、前記仮推定値ＭＶ０”は、（数１７）により計算されることを特徴とする。
【０１００】
【数１７】
【０１０１】
本発明に係る動き推定装置の第６の構成は、前記第１乃至５の何れか一の構成において、前記所定の範囲Ｒ１は、前記対象ブロックＣ０に上下左右及び斜め方向に隣接し、かつ既に動きベクトルが決定されている４つのブロックの内の一部又は全部のブロックであることを特徴とする。
【０１０２】
本発明に係る動き推定装置の第７の構成は、前記第１乃至５の何れか一の構成において、前記第１の代表値演算手段は、（数１８）により代表値δＴを計算することを特徴とする。
【０１０３】
【数１８】
【０１０４】
本発明に係る動き推定装置の第８の構成は、前記第１乃至７の何れか一の構成において、前記所定の範囲Ｒ２は、前記ブロックＣ０’に対して上下左右及び斜め方向に隣接する８つのブロックの範囲であることを特徴とする。
【０１０５】
本発明に係る動き推定装置の第９の構成は、前記第１乃至７の何れか一の構成において、前記第２の代表値演算手段は、（数１９）により代表値δＴ−１を計算することを特徴とする。
【０１０６】
【数１９】
【０１０７】
本発明に係るプログラムは、コンピュータに上記第１乃至９の何れか一の構成の動きベクトル推定方法を実行させる
【発明の効果】
【０１０８】
以上のように、本発明によれば、局所的な動き複雑性が大きい場合には、広範囲のブロック探索に適したブロック探索方法を選択し、局所的な動き複雑性が小さい場合には狭範囲のブロック探索に適したブロック探索方法を選択することが可能となる。これにより、ブロック探索に要する演算量を現実的な演算量に抑えつつ、動きが小さい場合において動きベクトルの推定精度を高く維持することができるとともに、動きが大きい場合に動きベクトルの予測が大きく外れることを防止することが可能となる。
【０１０９】
また、対象ブロックＣ０の動きベクトルの仮推定値が、真の動きを捉えるのに失敗した場合においても、対象ブロックＣ０の周囲の「局所的な動き複雑性」を評価することで、対象ブロックＣ０のみに着目する場合よりも、動きの存在をより敏感に捉え易くなる。すなわち、正確な動きタイプの予測が可能となり、映像内容が複雑な動きを示す場合であっても高い頑健性が得られる。そして、捉えられた動きに応じて、適応的にブロック探索方法が選択されるため、残留予測誤差をより小さくし、映像の圧縮率を改善することができる。
【発明を実施するための最良の形態】
【０１１０】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【０１１１】
図３は一般の映像符号化装置１の全体構成を表す図である（非特許文献１１参照）。尚、図３の映像符号化装置１は、一般に広く使用されているものであるため、ここでの説明は、その概略説明のみにとどめる。
【０１１２】
映像符号化装置１は、フレームメモリ２、差分器３、離散コサイン変換器（ＤＣＴ）４、量子化器５、エントロピ符号器６、局所復号器７、動き推定装置８、及び動き補償器９から構成されている。
【０１１３】
フレームメモリ２は、撮像素子等から入力される映像フレームを一時的に記憶するメモリである。差分器３は、フレームメモリ２が出力する対象フレームｆＴから、動き補償器９が出力する予測フレームｆＴ’を差し引いた差分画像ΔｆＴを出力する。ＤＣＴ４は、差分画像ΔｆＴに対して離散コサイン変換を施す。量子化器５は、ＤＣＴ４により出力されるＤＣＴ係数を量子化する。エントロピ符号器６は、量子化器５が出力する量子化されたＤＣＴ係数と動き推定装置８が出力する動きベクトルＭＶとをエントロピ符号化して、符号化映像のビット列として出力する。
【０１１４】
局所復号器７は、量子化器５が出力するＤＣＴ係数を再度もとのフレーム画像に復元する。そして、復元したフレーム画像を一時的に記憶し、対象フレームｆＴよりも前の参照フレームｆＴ−１”を出力する。動き推定装置８は、この参照フレームｆＴ−１”と対象フレームｆＴとを用いて、動きベクトルＭＶを推定し出力する。動き補償器９は、参照フレームｆＴ−１”と動きベクトルＭＶを用いて、対象フレームｆＴの予測値である予測フレームｆＴ’を生成し出力する。この予測フレームｆＴ’が、前記差分器３において差分画像ΔｆＴを生成する際に使用される。
【０１１５】
ここで、動き推定装置８において動きベクトルＭＶを生成するとき、及び動き補償器９において参照フレームとして、入力された映像からそのまま得られるフレームｆＴ−１を使用せず、局所復号器７で復元されたフレームｆＴ−１”を使用しているのは、映像復号側において復号画像に量子化誤差が蓄積することによりドリフトが生じることを防止するためである。
【０１１６】
尚、局所復号器７は、逆量子化器１０、逆離散コサイン変換器（逆ＤＣＴ）１１、加算器１２、フレームメモリ１３から構成されている。量子化器５が出力するＤＣＴ係数は、逆量子化器１０に入力され逆量子化が施された後に、逆ＤＣＴ１１において逆離散コサイン返還が施され、差分画像ΔｆＴ”が復元される。加算器１２において、この差分画像ΔｆＴ”と動き補償器９が出力する予測フレームｆＴ’とが加算されて、復元された対象フレームｆＴ”がフレームメモリ１３に格納される。これらの構成は、一般的な映像復号器と同様である。
【０１１７】
次に、本発明に係る動き推定装置８について説明する。図４は、本発明の実施例１に係る動き推定装置８の構成を表すブロック図である。
【０１１８】
動き推定装置８は、動きベクトル記憶手段２０、動きベクトル仮推定手段２１、代表値演算手段２２，２３、探索方法選択手段２４、動きベクトル決定手段２５、及び探索中心決定手段２６を備えている。
【０１１９】
動きベクトル記憶手段２０は、参照フレームｆＴ−１”及び対象フレームｆＴの各ブロックに対する動きベクトルＭＶ’，ＭＶを記憶するメモリである。
【０１２０】
動きベクトル仮推定手段２１は、動きベクトル記憶手段２０に記憶されている動きベクトルＭＶに基づき、対象フレームｆＴ内のブロックであって動きベクトル推定の対象となるブロック（対象ブロック）Ｃ０の動きベクトルＭＶ０の仮推定値ＭＶ０”を演算する。
【０１２１】
代表値演算手段２２は、対象ブロックＣ０の第１隣接の範囲Ｒ１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｊ（ｊ∈Ｒ１）の動きベクトルＭＶｊと、仮推定値ＭＶ０”との間の距離の代表値δＴを算出する。
【０１２２】
代表値演算手段２３は、対象ブロックＣ０に対応する参照フレームｆＴ−１”内のブロックＣ０’の動きベクトルＭＶ０’と、ブロックＣ０’の第１隣接の範囲Ｒ２内にある参照フレームｆＴ−１”内の各ブロックＣｉ’（ｉ∈Ｒ２）の動きベクトルＭＶｉ’との間の距離の代表値δＴ−１を算出する。
【０１２３】
探索方法選択手段２４は、代表値δＴ及び代表値δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から、代表値演算手段２２，２３により算出された代表値δＴ及び代表値δＴ−１の値に対応するブロック探索方法を選択する。
【０１２４】
探索中心決定手段２６は、動きベクトル決定手段２５が探索を行う際の探索中心のオフセットを決定する。
【０１２５】
動きベクトル決定手段２５は、探索方法選択手段２４により選択された探索方法に従って、探索中心決定手段２６により決定された探索中心を中心として、対象ブロックＣ０との相関が最大である参照フレームｆＴ−１”内のブロックの探索を行い、動きベクトルＭＶ０を決定し、動きベクトル記憶手段２０に保存する。
【０１２６】
探索方法選択手段２４は、動きタイプ決定手段３１，３２、及び探索方法選択手段３３を備えている。動きタイプ決定手段３１は、代表値演算手段２２が出力する代表値δＴの値を閾値判定し、対象ブロックＣ０の近傍の局所的な動きタイプＴＹＰＥ１を決定する。動きタイプ決定手段３２は、代表値演算手段２２が出力する代表値δＴ−１の値を閾値判定し、対象ブロックＣ０’の近傍の局所的な動きタイプＴＹＰＥ２を決定する。そして、探索方法選択手段３３は、局所的な動きタイプＴＹＰＥ１，ＴＹＰＥ２によって、探索方法の選択を行う。
【０１２７】
以上のように構成された本実施例に係る動き推定装置８について、以下その動き推定方法について説明する。動きベクトルの推定は、ラスタ走査の走査線に沿って、対象フレームの右上のブロックから左下のブロックに向かって行われるものとする。また、対象フレームの端に位置するブロックについては、全域探索法を用いて動きベクトルの推定が行われるものとする。以下では、対象フレームの端に位置するブロック以外の対象ブロックに対する動き推定動作について説明する。
【０１２８】
図５は本発明の実施例１に係る動き推定方法を表すフローチャートである。まず、動きベクトル仮推定手段２１は、動きベクトル記憶手段２０から図２に示したコンテキストＴの各ブロックの動きベクトルＭＶ１，ＭＶ２，ＭＶ３を読み出す。そして、対象ブロックＣ０の動きベクトルの仮推定値ＭＶ０”を（数２０）により算出する（Ｓ１）。
【０１２９】
【数２０】
【０１３０】
次に、代表値演算手段２２は、動きベクトル記憶手段２０から図２に示したコンテキストＴの各ブロックの動きベクトルＭＶ１，ＭＶ２，ＭＶ３を読み出す。そして、先に算出された動きベクトルの仮推定値ＭＶ０”と動きベクトルＭＶ１，ＭＶ２，ＭＶ３とに基づき、対象フレームｆＴ内における対象ブロックＣ０近傍の局所的な動き複雑性を算出する（Ｓ２）。ここでは、局所的な動き複雑性として、各ブロックＣｊ（ｊ∈Ｒ１）の動きベクトルＭＶｊと、仮推定値ＭＶ０”との間の距離の代表値δＴを用いる。従って、代表値演算手段２２は（数２１）により対象ブロックＣ０近傍の局所的な動き複雑性である代表値δＴを算出する。
【０１３１】
【数２１】
【０１３２】
一方、代表値演算手段２３は、動きベクトル記憶手段２０から図２に示したコンテキストＴ−１の各ブロックの動きベクトルＭＶ０’〜ＭＶ８’を読み出す。そして、これらの動きベクトルＭＶ０’〜ＭＶ８’に基づき、参照フレームｆＴ−１”内におけるブロックＣ０’近傍の局所的な動き複雑性を算出する（Ｓ３）。ここでは、局所的な動き複雑性として、各ブロックＣｉ’（ｉ∈Ｒ２）の動きベクトルＭＶｉ’と、ブロックＣ０’の動きベクトルＭＶ０’との間の距離の代表値δＴ−１を用いる。従って、代表値演算手段２３は（数２２）により対象ブロックＣ０近傍の局所的な動き複雑性である代表値δＴ−１を算出する。
【０１３３】
【数２２】
【０１３４】
次に、探索方法選択手段２４は、代表値δＴ及び代表値δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から、代表値演算手段２２，２３により算出された代表値δＴ及び代表値δＴ−１の値に対応するブロック探索方法を選択する（Ｓ４）。具体的には、まず、動きタイプ決定手段３１が、代表値δＴに基づき、（数９）に従って動きタイプＴＹＰＥＴを決定する。また、動きタイプ決定手段３２が、代表値δＴ−１に基づき、（数８）に従って動きタイプＴＹＰＥＴ−１を決定する。探索方法選択手段３３は、動きタイプＴＹＰＥＴ，ＴＹＰＥＴ−１により、（表１）に従って対象ブロックＣ０の動きタイプを決定する。そして、対象ブロックＣ０の動きタイプに基づき、（表２）に従って探索方法の選択を行う。このようにして、局所的な動き複雑性に従って、ブロックマッチングにおける探索戦略が適応的に決定される。
【０１３５】
次に、探索中心決定手段２６は、動きベクトル決定手段２５が探索を行う際の探索中心のオフセットＶを、（数１０）〜（数１２）に従って決定する（Ｓ５）。
【０１３６】
次に、動きベクトル決定手段２５は、探索方法選択手段２４により選択された探索方法に従って、対象ブロックＣ０との相関が最大である参照フレームｆＴ−１”内のブロックの探索を行う（Ｓ６）。このとき、ブロック探索は、ブロックＣ０”の位置から、ステップＳ５において決定されたオフセットＶだけ平行移動した位置を中心として行われる。これにより、対象ブロックＣ０の動きベクトルＭＶ０が決定される。
【０１３７】
最後に、動きベクトル決定手段２５は、動きベクトルＭＶ０を動きベクトル記憶手段２０に保存して（Ｓ７）、対象ブロックＣ０の動きベクトル推定動作を終了する。
【０１３８】
このような動きベクトル推定動作を、ラスタ走査の走査線に沿って、対象ブロックＣ０を移動させながら順次行うことにより、対象フレームｆＴの動きベクトル推定を行うことができる。
【０１３９】
尚、本実施例の動き推定装置は、映像の性質により適応的に探索戦略を変更できるため、映像内容が複雑な動きを示す場合であっても高い頑健性を得ることができるとともに、ハードウェア実装することもソフトウェア実装することも可能である。また、コンピュータ・プログラムとして構成し、汎用コンピュータによって実現することも可能である。
【図面の簡単な説明】
【０１４０】
【図１】テスト映像（ＣＩＦ）から得られたフレーム内の動きベクトルマップを表す図である。
【図２】ブロックマッチングを行うために使用されるコンテキストの一例である。
【図３】一般の映像符号化装置の全体構成を表す図である。
【図４】本発明の実施例１に係る動き推定装置８の構成を表すブロック図である。
【図５】本発明の実施例１に係る動き推定方法を表すフローチャートである。
【符号の説明】
【０１４１】
１ 映像符号化装置
２ フレームメモリ
３ 差分器
４ 離散コサイン変換器（ＤＣＴ）
５ 量子化器
６ エントロピ符号器
７ 局所復号器
８ 動き推定装置
９ 動き補償器
１０ 逆量子化器
１１ 逆離散コサイン変換器（逆ＤＣＴ）
１２ 加算器
１３ フレームメモリ
２０ 動きベクトル記憶手段
２１ 動きベクトル仮推定手段
２２，２３ 代表値演算手段
２４ 探索方法選択手段
２５ 動きベクトル決定手段
２６ 探索中心決定手段
３１，３２ 動きタイプ決定手段
３３ 探索方法選択手段
【特許請求の範囲】
【請求項１】
複数のフレームから構成される動画像において、参照フレームに対する対象フレーム内の各ブロックの動きベクトルを推定する動き推定方法であって、前記対象フレーム内における動きベクトル推定の対象となるブロック（以下、「対象ブロック」という。）Ｃ０との相関が最大である前記参照フレーム内のブロックの探索を、以下の各ステップを有する選択手順で選択されたブロック探索方法に従って行うことにより、前記対象ブロックＣ０の動きベクトルＭＶ０を決定することを特徴とする動き推定方法：
前記参照フレーム又は前記対象フレームの各ブロックの動きベクトルであって既に決定されているものに基づき、前記対象ブロックＣ０の動きベクトルＭＶ０の仮推定値ＭＶ０”を決定する第１ステップ；
前記仮推定値ＭＶ０”と、前記対象フレーム内における前記対象ブロックＣ０周囲の所定の範囲Ｒ１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｊ（ｊ∈Ｒ１）の動きベクトルＭＶｊとの間の距離の代表値δＴを算出する第２ステップ；
前記対象ブロックＣ０に対応する前記参照フレーム内のブロックＣ０’の動きベクトルＭＶ０’と、前記ブロックＣ０’の周囲の所定の範囲Ｒ２内にある前記参照フレーム内の各ブロックＣｉ’（ｉ∈Ｒ２）の動きベクトルＭＶｉ’との間の距離の代表値δＴ−１を算出する第３ステップ；
前記代表値δＴ及び前記代表値δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から、前記第２ステップ及び前記第３ステップで算出された前記代表値δＴ及び前記代表値δＴ−１の値に対応するブロック探索方法を選択する第４ステップ。
【請求項２】
前記第４ステップにおいて、
前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合には、ブロック探索方法として、所定の探索領域における多段探索法を選択し、
前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合には、ブロック探索方法として、前記多段探索法の探索領域よりも狭い探索領域での全域探索法を選択すること
を特徴とする請求項１記載の動き推定方法。
【請求項３】
前記第４ステップにおいて、
前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合においては、ブロック探索方法として、所定の探索領域Ｓ０における多段探索法を選択し、
前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合においては、
前記代表値δＴ−１の値が所定の閾値Ｔｈ２よりも大きい場合には、ブロック探索方法として、前記多段探索法の探索領域Ｓ０と同じ又はより狭い探索領域Ｓ１での全域探索法を選択し、
前記代表値δＴ−１の値が所定の閾値Ｔｈ２以下の場合には、ブロック探索方法として、前記探索領域Ｒ１よりも狭い探索領域Ｓ２での全域探索法を選択すること
を特徴とする請求項１又は２記載の動き推定方法。
【請求項４】
前記第１ステップにおいて、前記仮推定値ＭＶ０”は、前記対象フレーム内における前記対象ブロックＣ０周囲の所定の範囲Ｒ３内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｋ（ｋ∈Ｒ３）の動きベクトルＭＶｋに基づいて決定されることを特徴とする請求項１乃至３の何れか一記載の動き推定方法。
【請求項５】
前記仮推定値ＭＶ０”は、（数１）により計算されることを特徴とする請求項４記載の動き推定方法。
【数１】
【請求項６】
第２ステップにおいて、所定の範囲Ｒ１は、前記対象ブロックＣ０に対し第１隣接のブロックであって、かつ既に動きベクトルが決定されている４つのブロックの内の一部又は全部のブロックであること
を特徴とする請求項１乃至５の何れか一記載の動き推定方法。
【請求項７】
第２ステップにおいて、代表値δＴは、（数２）により計算されることを特徴とする請求項１乃至５の何れか一記載の動き推定方法。
【数２】
【請求項８】
前記第３ステップにおいて、前記所定の範囲Ｒ２は、前記ブロックＣ０’に対して隣接する８つのブロックの範囲であることを特徴とする請求項１乃至７の何れか一記載の動き推定方法。
【請求項９】
前記第３ステップにおいて、前記代表値δＴ−１は、（数３）により計算されることを特徴とする請求項１乃至７の何れか一記載の動き推定方法。
【数３】
【請求項１０】
複数のフレームから構成される動画像において、参照フレームに対する、対象フレームにおける各ブロックの動きベクトルを推定する動き推定装置であって、
前記参照フレーム及び前記対象フレームの各ブロックに対する動きベクトルを記憶する動きベクトル記憶手段と、
前記動きベクトル記憶手段に記憶されている動きベクトルに基づき、前記対象フレーム内のブロックであって動きベクトル推定の対象となるブロック（以下、「対象ブロック」という。）Ｃ０の動きベクトルＭＶ０の仮推定値ＭＶ０”を演算する動きベクトル仮推定手段と、
前記対象ブロックＣ０周囲の所定の範囲Ｒ１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｊ（ｊ∈Ｒ１）の動きベクトルＭＶｊと、前記仮推定値ＭＶ０”との間の距離の代表値δＴを算出する第１の代表値演算手段と、
前記対象ブロックＣ０に対応する前記参照フレーム内のブロックＣ０’の動きベクトルＭＶ０’と、前記ブロックＣ０’の周囲の所定の範囲Ｒ２内にある前記参照フレーム内の各ブロックＣｉ’（ｉ∈Ｒ２）の動きベクトルＭＶｉ’との間の距離の代表値δＴ−１を算出する第２の代表値演算手段と、
前記代表値δＴ及び前記代表値δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から、前記第１及び前記第２の代表値演算手段により算出された前記代表値δＴ及び前記代表値δＴ−１の値に対応するブロック探索方法を選択する探索方法選択手段と、
前記探索方法選択手段により選択された探索方法に従って、前記対象ブロックＣ０との相関が最大である前記参照フレーム内のブロックの探索を行い、前記動きベクトルＭＶ０を決定し、前記動きベクトル記憶手段に保存する動きベクトル決定手段と、
を備えていることを特徴とする動き推定装置。
【請求項１１】
前記探索方法選択手段は、
前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合には、ブロック探索方法として、所定の探索領域における多段探索法を選択し、
前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合には、ブロック探索方法として、前記多段探索法の探索領域よりも狭い探索領域での全域探索法を選択すること
を特徴とする請求項１０記載の動き推定装置。
【請求項１２】
前記探索方法選択手段は、
前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合においては、ブロック探索方法として、所定の探索領域Ｓ０における多段探索法を選択し、
前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合においては、
前記代表値δＴ−１の値が所定の閾値Ｔｈ２よりも大きい場合には、ブロック探索方法として、前記多段探索法の探索領域Ｓ０と同じ又はより狭い探索領域Ｓ１での全域探索法を選択し、
前記代表値δＴ−１の値が所定の閾値Ｔｈ２以下の場合には、ブロック探索方法として、前記探索領域Ｒ１よりも狭い探索領域Ｓ２での全域探索法を選択すること
を特徴とする請求項１０又は１１記載の動き推定装置。
【請求項１３】
前記動きベクトル仮推定手段は、前記対象フレーム内における前記対象ブロックＣ０周囲の所定の範囲Ｒ３内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｋ（ｋ∈Ｒ３）の動きベクトルＭＶｋに基づいて前記仮推定値ＭＶ０”を決定することを特徴とする請求項１０乃至１２の何れか一記載の動き推定装置。
【請求項１４】
前記仮推定値ＭＶ０”は、（数４）により計算されることを特徴とする請求項１３記載の動き推定装置。
【数４】
【請求項１５】
前記所定の範囲Ｒ１は、前記対象ブロックＣ０に上下左右及び斜め方向に隣接し、かつ既に動きベクトルが決定されている４つのブロックの内の一部又は全部のブロックであること
を特徴とする請求項１０乃至１４の何れか一記載の動き推定装置。
【請求項１６】
前記第１の代表値演算手段は、（数５）により代表値δＴを計算することを特徴とする請求項１０乃至１４の何れか一記載の動き推定装置。
【数５】
【請求項１７】
前記所定の範囲Ｒ２は、前記ブロックＣ０’に対して上下左右及び斜め方向に隣接する８つのブロックの範囲であることを特徴とする請求項１０乃至１６の何れか一記載の動き推定装置。
【請求項１８】
前記第２の代表値演算手段は、（数６）により代表値δＴ−１を計算することを特徴とする請求項１０乃至１６の何れか一記載の動き推定方法。
【数６】
【請求項１９】
コンピュータに請求項１乃至９の何れか一記載の方法を実行させるためのプログラム。
【請求項１】
複数のフレームから構成される動画像において、参照フレームに対する対象フレーム内の各ブロックの動きベクトルを推定する動き推定方法であって、前記対象フレーム内における動きベクトル推定の対象となるブロック（以下、「対象ブロック」という。）Ｃ０との相関が最大である前記参照フレーム内のブロックの探索を、以下の各ステップを有する選択手順で選択されたブロック探索方法に従って行うことにより、前記対象ブロックＣ０の動きベクトルＭＶ０を決定することを特徴とする動き推定方法：
前記参照フレーム又は前記対象フレームの各ブロックの動きベクトルであって既に決定されているものに基づき、前記対象ブロックＣ０の動きベクトルＭＶ０の仮推定値ＭＶ０”を決定する第１ステップ；
前記仮推定値ＭＶ０”と、前記対象フレーム内における前記対象ブロックＣ０周囲の所定の範囲Ｒ１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｊ（ｊ∈Ｒ１）の動きベクトルＭＶｊとの間の距離の代表値δＴを算出する第２ステップ；
前記対象ブロックＣ０に対応する前記参照フレーム内のブロックＣ０’の動きベクトルＭＶ０’と、前記ブロックＣ０’の周囲の所定の範囲Ｒ２内にある前記参照フレーム内の各ブロックＣｉ’（ｉ∈Ｒ２）の動きベクトルＭＶｉ’との間の距離の代表値δＴ−１を算出する第３ステップ；
前記代表値δＴ及び前記代表値δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から、前記第２ステップ及び前記第３ステップで算出された前記代表値δＴ及び前記代表値δＴ−１の値に対応するブロック探索方法を選択する第４ステップ。
【請求項２】
前記第４ステップにおいて、
前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合には、ブロック探索方法として、所定の探索領域における多段探索法を選択し、
前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合には、ブロック探索方法として、前記多段探索法の探索領域よりも狭い探索領域での全域探索法を選択すること
を特徴とする請求項１記載の動き推定方法。
【請求項３】
前記第４ステップにおいて、
前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合においては、ブロック探索方法として、所定の探索領域Ｓ０における多段探索法を選択し、
前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合においては、
前記代表値δＴ−１の値が所定の閾値Ｔｈ２よりも大きい場合には、ブロック探索方法として、前記多段探索法の探索領域Ｓ０と同じ又はより狭い探索領域Ｓ１での全域探索法を選択し、
前記代表値δＴ−１の値が所定の閾値Ｔｈ２以下の場合には、ブロック探索方法として、前記探索領域Ｒ１よりも狭い探索領域Ｓ２での全域探索法を選択すること
を特徴とする請求項１又は２記載の動き推定方法。
【請求項４】
前記第１ステップにおいて、前記仮推定値ＭＶ０”は、前記対象フレーム内における前記対象ブロックＣ０周囲の所定の範囲Ｒ３内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｋ（ｋ∈Ｒ３）の動きベクトルＭＶｋに基づいて決定されることを特徴とする請求項１乃至３の何れか一記載の動き推定方法。
【請求項５】
前記仮推定値ＭＶ０”は、（数１）により計算されることを特徴とする請求項４記載の動き推定方法。
【数１】
【請求項６】
第２ステップにおいて、所定の範囲Ｒ１は、前記対象ブロックＣ０に対し第１隣接のブロックであって、かつ既に動きベクトルが決定されている４つのブロックの内の一部又は全部のブロックであること
を特徴とする請求項１乃至５の何れか一記載の動き推定方法。
【請求項７】
第２ステップにおいて、代表値δＴは、（数２）により計算されることを特徴とする請求項１乃至５の何れか一記載の動き推定方法。
【数２】
【請求項８】
前記第３ステップにおいて、前記所定の範囲Ｒ２は、前記ブロックＣ０’に対して隣接する８つのブロックの範囲であることを特徴とする請求項１乃至７の何れか一記載の動き推定方法。
【請求項９】
前記第３ステップにおいて、前記代表値δＴ−１は、（数３）により計算されることを特徴とする請求項１乃至７の何れか一記載の動き推定方法。
【数３】
【請求項１０】
複数のフレームから構成される動画像において、参照フレームに対する、対象フレームにおける各ブロックの動きベクトルを推定する動き推定装置であって、
前記参照フレーム及び前記対象フレームの各ブロックに対する動きベクトルを記憶する動きベクトル記憶手段と、
前記動きベクトル記憶手段に記憶されている動きベクトルに基づき、前記対象フレーム内のブロックであって動きベクトル推定の対象となるブロック（以下、「対象ブロック」という。）Ｃ０の動きベクトルＭＶ０の仮推定値ＭＶ０”を演算する動きベクトル仮推定手段と、
前記対象ブロックＣ０周囲の所定の範囲Ｒ１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｊ（ｊ∈Ｒ１）の動きベクトルＭＶｊと、前記仮推定値ＭＶ０”との間の距離の代表値δＴを算出する第１の代表値演算手段と、
前記対象ブロックＣ０に対応する前記参照フレーム内のブロックＣ０’の動きベクトルＭＶ０’と、前記ブロックＣ０’の周囲の所定の範囲Ｒ２内にある前記参照フレーム内の各ブロックＣｉ’（ｉ∈Ｒ２）の動きベクトルＭＶｉ’との間の距離の代表値δＴ−１を算出する第２の代表値演算手段と、
前記代表値δＴ及び前記代表値δＴ−１の各値に対応して予め決められている各種ブロック探索方法の中から、前記第１及び前記第２の代表値演算手段により算出された前記代表値δＴ及び前記代表値δＴ−１の値に対応するブロック探索方法を選択する探索方法選択手段と、
前記探索方法選択手段により選択された探索方法に従って、前記対象ブロックＣ０との相関が最大である前記参照フレーム内のブロックの探索を行い、前記動きベクトルＭＶ０を決定し、前記動きベクトル記憶手段に保存する動きベクトル決定手段と、
を備えていることを特徴とする動き推定装置。
【請求項１１】
前記探索方法選択手段は、
前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合には、ブロック探索方法として、所定の探索領域における多段探索法を選択し、
前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合には、ブロック探索方法として、前記多段探索法の探索領域よりも狭い探索領域での全域探索法を選択すること
を特徴とする請求項１０記載の動き推定装置。
【請求項１２】
前記探索方法選択手段は、
前記代表値δＴの値が所定の閾値Ｔｈ１よりも大きい場合においては、ブロック探索方法として、所定の探索領域Ｓ０における多段探索法を選択し、
前記代表値δＴの値が所定の閾値Ｔｈ１以下の場合においては、
前記代表値δＴ−１の値が所定の閾値Ｔｈ２よりも大きい場合には、ブロック探索方法として、前記多段探索法の探索領域Ｓ０と同じ又はより狭い探索領域Ｓ１での全域探索法を選択し、
前記代表値δＴ−１の値が所定の閾値Ｔｈ２以下の場合には、ブロック探索方法として、前記探索領域Ｒ１よりも狭い探索領域Ｓ２での全域探索法を選択すること
を特徴とする請求項１０又は１１記載の動き推定装置。
【請求項１３】
前記動きベクトル仮推定手段は、前記対象フレーム内における前記対象ブロックＣ０周囲の所定の範囲Ｒ３内にあるブロックであって既に動きベクトルが決定されている各ブロックＣｋ（ｋ∈Ｒ３）の動きベクトルＭＶｋに基づいて前記仮推定値ＭＶ０”を決定することを特徴とする請求項１０乃至１２の何れか一記載の動き推定装置。
【請求項１４】
前記仮推定値ＭＶ０”は、（数４）により計算されることを特徴とする請求項１３記載の動き推定装置。
【数４】
【請求項１５】
前記所定の範囲Ｒ１は、前記対象ブロックＣ０に上下左右及び斜め方向に隣接し、かつ既に動きベクトルが決定されている４つのブロックの内の一部又は全部のブロックであること
を特徴とする請求項１０乃至１４の何れか一記載の動き推定装置。
【請求項１６】
前記第１の代表値演算手段は、（数５）により代表値δＴを計算することを特徴とする請求項１０乃至１４の何れか一記載の動き推定装置。
【数５】
【請求項１７】
前記所定の範囲Ｒ２は、前記ブロックＣ０’に対して上下左右及び斜め方向に隣接する８つのブロックの範囲であることを特徴とする請求項１０乃至１６の何れか一記載の動き推定装置。
【請求項１８】
前記第２の代表値演算手段は、（数６）により代表値δＴ−１を計算することを特徴とする請求項１０乃至１６の何れか一記載の動き推定方法。
【数６】
【請求項１９】
コンピュータに請求項１乃至９の何れか一記載の方法を実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００６−３３４３３（Ｐ２００６−３３４３３Ａ）
【公開日】平成１８年２月２日（２００６．２．２）
【国際特許分類】
【出願番号】特願２００４−２０９６１４（Ｐ２００４−２０９６１４）
【出願日】平成１６年７月１６日（２００４．７．１６）
【出願人】（８０２００００３１）財団法人北九州産業学術推進機構 (187)
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
【公開日】平成１８年２月２日（２００６．２．２）
【国際特許分類】
【出願日】平成１６年７月１６日（２００４．７．１６）
【出願人】（８０２００００３１）財団法人北九州産業学術推進機構 (187)
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
[ Back to top ]