JP4537136B2 - 動き推定方法及び動き推定装置、並びにプログラム - Google Patents

Description

本発明は、映像圧縮におけるブロックマッチングによる動き推定技術に関するものであり、特に、動きベクトルによっては捉えにくい映像の動きを感度よく検出することにより、適応的にブロックマッチングを行うことが可能な動き推定技術に関する。

ブロックマッチング動き推定（Block Matching Motion Estimation：ＢＭＭＥ）は、ソフトウェア実装においてもハードウェア実装においても、現在のところ最も有力な動き推定（Motion Estimation：ＭＥ）方法であり、MPEG-1/2/4やH.216/263/263+等の種々の国際標準において採用されている。

ブロックマッチング動き推定において、判定基準（matching criterion）として、通常、（数１）で表される差分絶対値和（Sum of Absolution Difference：ＳＡＤ）が使用される。ここで、Ｍはブロックサイズを表す。また、I_CとI_Rは、それぞれ、対象フレーム（current flame）内におけるブロックマッチングの対象のブロックである対象ブロック（current block）内の画素値、及び参照フレーム（reference frame）内において発見された再一致候補ブロック内の画素値を表す。

しかしながら、ＢＭＭＥには、本質的に、極めて計算量が大きなタスクを内在していることは明らかである。そして、そのタスクは、ビデオエンコーダにおける全計算時間の６０％〜８０％をも占める程度の計算量であるとする試算が報告されている（非特許文献１参照）。特に総当たり法である全域探索ブロックマッチング（Full Search Block Matching：ＦＳＢＭ）の場合には、＋／−Ｎピクセルの探索領域に対して、探索点は(2N+1)²にものぼる。

そこで、従来、ＭＥの改良技術として、二次元対数探索法（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）法を表す。N_simple，N_critical，N_chaosは探索範囲を表す。例えば、N_simpleの場合には、N_simple×N_simpleの領域において探索を行うことを表している。ここで、N_simple，N_critical，N_chaosの間には（数１３）のような関係がある。

‘ＳＩＭＰＬＥ’の場合、小さいウィンドウ内に探索領域を限定することによって、かなりの量の無駄な計算を省くことができる。

‘ＣＲＩＴＩＣＡＬ’の場合、対象フレームの動き複雑性は参照フレームの動き複雑性よりも低くなる。従って、ほとんどの場合、（数１２）によりかなり信頼性の高い探索中心のオフセットを予測することができる。従って、ブロックマッチングにおける探索範囲は小さくてもよい。しかしながら、上述した「トラップ」を考慮して、探索領域はN_simpleよりも大きくあるべきである。

‘ＣＨＡＯＳ’の場合には、それぞれの動きベクトル間の相関が小さいので、ブロックマッチングを行う際の探索範囲は大きめにとる必要がある。しかしながら、探索中心はオフセットによりシフトされる。また、動きベクトルの探索領域の大きさは、探索によって得られる動きベクトルの大きさが実用範囲内となる程度に制限される。従って、探索範囲の大きさは一定サイズの領域に限定されるので、動き複雑性が大きい場合でも計算量は減少すると考えられる。動きベクトルの探索は、螺旋パターン（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）、ユークリッド距離等を使用することができる。

距離の「代表値」とは、変数の分布を要約する統計量のことをいう。「距離の代表値δ_Ｔ」としては、最大値、最小値、中央値、平均値、最頻値、総和、自乗和、平方和等を使用することができる。

本発明に係る動き推定方法の第２の構成は、前記第１の構成において、前記第４ステップにおいて、前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１よりも大きい場合には、ブロック探索方法として、所定の探索領域における多段探索法を選択し、前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１以下の場合には、ブロック探索方法として、前記多段探索法の探索領域よりも狭い探索領域での全域探索法を選択することを特徴とする。

この構成によれば、代表値δ_Ｔの値の閾値判定によって、対象ブロックＣ_０の近傍の局所的な動き複雑性に応じて動きベクトルの探索方法を適応的に切り替えることが可能となる。また、閾値判定であるため、簡単なアルゴリズムにより実現可能であり、また、ハードウェアによって回路的に実現する場合の回路構成も簡易である。

ここで、「所定の閾値Ｔｈ_１」は、実験的に設定する値である。また、「所定の閾値Ｔｈ_１」は、必ずしも固定値とする必要はなく、動き推定の精度の要求に応じて、外部から自由に設定できるようにしてもよい。

本発明に係る動き推定方法の第３の構成は、前記第１又は２の構成において、前記第４ステップにおいて、前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１よりも大きい場合においては、ブロック探索方法として、所定の探索領域Ｓ_０における多段探索法を選択し、前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１以下の場合においては、前記代表値δ_Ｔ−１の値が所定の閾値Ｔｈ_２よりも大きい場合には、ブロック探索方法として、前記多段探索法の探索領域Ｓ_０と同じ又はより狭い探索領域Ｓ_１での全域探索法を選択し、前記代表値δ_Ｔ−１の値が所定の閾値Ｔｈ_２以下の場合には、ブロック探索方法として、前記所定の範囲Ｒ _１ よりも狭い探索領域Ｓ_２での全域探索法を選択することを特徴とする。

この構成によれば、代表値δ_Ｔ及び代表値δ_Ｔ−１の値の閾値判定によって、対象ブロックＣ_０及びブロックＣ_０’の近傍の局所的な動き複雑性に応じて動きベクトルの探索方法を適応的に切り替えることが可能となる。また、閾値判定であるため、簡単なアルゴリズムにより実現可能であり、また、ハードウェアによって回路的に実現する場合の回路構成も簡易である。

ここで、各場合における探索領域Ｓ_０，Ｓ_１，Ｓ_２の大きさは、それぞれ、要求される計算速度、計算精度等に応じて適度な大きさに設定することができる。

また、「所定の閾値Ｔｈ_１，Ｔｈ_２」は、実験的に設定する値である。また、「所定の閾値Ｔｈ_１，Ｔｈ_２」は、必ずしも固定値とする必要はなく、動き推定の精度の要求に応じて、外部から自由に設定できるようにしてもよい。

本発明に係る動き推定方法の第４の構成は、前記第１乃至３の何れか一の構成において、前記第１ステップにおいて、前記仮推定値ＭＶ_０”は、前記対象フレーム内における前記対象ブロックＣ_０周囲の所定の範囲Ｒ_３内にあるブロックであって既に動きベクトルが決定されている各ブロックＣ_ｋ（ｋ∈Ｒ_３）の動きベクトルＭＶ_ｋに基づいて決定されることを特徴とする。

この構成により、走査に従って、対象ブロックＣ_０の前に決定された動きベクトルを用いて対象ブロックＣ_０の動きベクトルの仮推定値ＭＶ_０”を決定することができる。

ここで、「所定の範囲Ｒ_３」は特に限定しないが、通常は、対象ブロックＣ_０の第１隣接又は第２隣接までを含む範囲に設定される。

「動きベクトルＭＶ_ｋに基づいて」とは、例えば、動きベクトル｛ＭＶ_ｋ｜∀ｋ∈Ｒ_３｝の平均値、中央値、最頻値等を仮推定値ＭＶ_０”に決定することをいう。また、ラスタスキャンに従って対象ブロックＣ_０の動きベクトルＭＶ_０を決定していく場合には、対象ブロックＣ_０の上の行のブロックと、対象ブロックＣ_０の行における対象ブロックＣ_０の左側のブロックについては、既に動きベクトルが決定されている。そこで、対象ブロックＣ_０の左の隣接ブロックをＣ_ａ、左上の隣接ブロックをＣ_ｂ、上の隣接ブロックをＣ_ｃとすれば、例えば、ＭＶ_０”＝ＭＶ_ａ＋ＭＶ_ｃ−ＭＶ_ｂのようにして、二次元の画素値予測方法と同様な方法により仮推定値ＭＶ_０”を決定するようにしてもよい。

本発明に係る動き推定方法の第５の構成は、前記第４の構成において、前記仮推定値ＭＶ_０”は、（数１４）により計算されることを特徴とする。

この構成によれば、前記仮推定値ＭＶ_０”として、｛ＭＶ_ｋ｜∀ｋ∈Ｒ_３｝の中央値を用いることで、簡単なアルゴリズムにより仮推定値ＭＶ_０”を決定することができる。

本発明に係る動き推定方法の第６の構成は、前記第１乃至５の何れか一の構成において、第２ステップにおいて、所定の範囲Ｒ_１は、前記対象ブロックＣ_０に対し第１隣接のブロックであって、かつ既に動きベクトルが決定されている４つのブロックの内の一部又は全部のブロックであることを特徴とする。

このように、対象ブロックＣ_０周囲の局所的な動き複雑性の検出に、対象ブロックＣ_０に対し第１隣接のブロックを使用することで、対象ブロックＣ_０から離れたブロックの動きベクトルの影響を受けずに、対象ブロックＣ_０の周囲の局所的な動き複雑性を検出することができる。従って、ブロック探索方法の選択において、無駄に広域探索の方法が選択されることを防止することができる。

本発明に係る動き推定方法の第７の構成は、前記第１乃至５の何れか一の構成において、第２ステップにおいて、代表値δ_Ｔは、（数１５）により計算されることを特徴とする。

このように、代表値δ_Ｔとして動きベクトルの差分絶対値和（ＳＡＤ）を用いれば、代表値δ_Ｔの演算が、局所的な動き複雑性をよく表し、かつ簡単なアルゴリズムにより実現可能となる。

本発明に係る動き推定方法の第８の構成は、前記第１乃至７の何れか一の構成において、前記第３ステップにおいて、前記所定の範囲Ｒ_２は、前記ブロックＣ_０’に対して隣接する８つのブロックの範囲であることを特徴とする。

このように、ブロックＣ_０’に対して隣接する８つのブロックを参照して局所的な動き複雑性を評価することで、すべての方向からの動き特性の変化を捉えることができる。従って、代表値δ_Ｔ−１は、動きの特性の変化を捉える敏感な特性値となる。

本発明に係る動き推定方法の第９の構成は、前記第１乃至７の何れか一の構成において、前記第３ステップにおいて、前記代表値δ_Ｔ−１は、（数１６）により計算されることを特徴とする。

このように、最大値を利用することで、動き特性の変化に対する敏感性を高め、任意方向に起こる動き特性の変化を正確に捉えることができる。

本発明に係る動き推定装置の第１の構成は、複数のフレームから構成される映像において、参照フレームに対する、対象フレームにおける各ブロックの動きベクトルを推定する動き推定装置であって、前記参照フレーム及び前記対象フレームの各ブロックに対する動きベクトルを記憶する動きベクトル記憶手段と、前記動きベクトル記憶手段に記憶されている動きベクトルに基づき、前記対象フレーム内のブロックであって動きベクトル推定の対象となるブロック（以下、「対象ブロック」という。）Ｃ_０の動きベクトルＭＶ_０の仮推定値ＭＶ_０”を演算する動きベクトル仮推定手段と、前記対象ブロックＣ_０周囲の所定の範囲Ｒ_１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣ_ｊ（ｊ∈Ｒ_１）の動きベクトルＭＶ_ｊと、前記仮推定値ＭＶ_０”との差のノルムである距離の代表値δ_Ｔを算出する第１の代表値演算手段と、前記対象ブロックＣ_０に対応する前記参照フレーム内のブロックＣ_０’の動きベクトルＭＶ_０’と、前記ブロックＣ_０’の周囲の所定の範囲Ｒ_２内にある前記参照フレーム内の各ブロックＣ_ｉ’（ｉ∈Ｒ_２）の動きベクトルＭＶ_ｉ’との差のノルムである距離の代表値δ_Ｔ−１を算出する第２の代表値演算手段と、前記代表値δ_Ｔ及び前記代表値δ_Ｔ−１の各値に対応して予め決められている各種ブロック探索方法の中から、前記第１の代表値演算手段により算出された前記代表値δ_Ｔ及び前記代表値δ_Ｔ−１の値に対応するブロック探索方法を選択する探索方法選択手段と、前記探索方法選択手段により選択された探索方法に従って、前記対象ブロックＣ_０との相関が最大である前記参照フレーム内のブロックの探索を行い、前記動きベクトルＭＶ_０を決定し、前記動きベクトル記憶手段に保存する動きベクトル決定手段とを備えていることを特徴とする。

この構成によれば、動きベクトル仮推定手段は、動きベクトル記憶手段に記憶されている動きベクトルに基づき、対象ブロックＣ_０の動きベクトルＭＶ_０の仮推定値ＭＶ_０”を演算する。第１の代表値演算手段は、この仮推定値ＭＶ_０”と各動きベクトルＭＶ_ｊとの間の距離の代表値δ_Ｔを算出する。第２の代表値演算手段は、動きベクトルＭＶ_０’と各動きベクトルＭＶ_ｊ’との間の距離の代表値δ_Ｔ−１を算出する。次いで、探索方法選択手段は、代表値δ_Ｔ及び代表値δ_Ｔ−１の値に対応するブロック探索方法を選択する。そして、動きベクトル決定手段は、選択された探索方法に従って、参照フレーム内のブロックの探索を行い、動きベクトルＭＶ_０を決定し、動きベクトル記憶手段に保存する。以上の動作を繰り返すことによって、対象フレーム内の各ブロックの動きベクトルが順次決定される。

このとき、動きベクトルの探索方法は、対象ブロックＣ_０を中心とする「局所的な動き複雑性」及び対象ブロックＣ_０’を中心とする「局所的な動き複雑性」の両方に適応して選択される。これにより、ブロック探索に要する演算量を現実的な演算量に抑えつつ、動きが小さい場合において動きベクトルの推定精度を高く維持することができるとともに、動きが大きい場合に動きベクトルの予測が大きく外れることを防止することが可能となる。

また、対象ブロックＣ_０の動きベクトルの仮推定値が真の動きを捉えていない場合においても、対象ブロックＣ_０及び対象ブロックＣ_０’の双方の周囲の「局所的な動き複雑性」を評価することで、対象ブロックＣ_０のみに着目する場合よりも、動きの存在をより敏感に捉え易くなる。そして、捉えられた動きに応じて、適応的にブロック探索方法が選択されるため、残留予測誤差をより小さくし、映像の圧縮率を改善することができる。

本発明に係る動き推定装置の第２の構成は、前記第１の構成において、前記探索方法選択手段は、前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１よりも大きい場合には、ブロック探索方法として、所定の探索領域における多段探索法を選択し、前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１以下の場合には、ブロック探索方法として、前記多段探索法の探索領域よりも狭い探索領域での全域探索法を選択することを特徴とする。

本発明に係る動き推定装置の第３の構成は、前記第１又は２の構成において、前記探索方法選択手段は、前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１よりも大きい場合においては、ブロック探索方法として、所定の探索領域Ｓ_０における多段探索法を選択し、前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１以下の場合においては、前記代表値δ_Ｔ−１の値が所定の閾値Ｔｈ_２よりも大きい場合には、ブロック探索方法として、前記多段探索法の探索領域Ｓ_０と同じ又はより狭い探索領域Ｓ_１での全域探索法を選択し、前記代表値δ_Ｔ−１の値が所定の閾値Ｔｈ_２以下の場合には、ブロック探索方法として、前記所定の範囲Ｒ _１ よりも狭い探索領域Ｓ_２での全域探索法を選択することを特徴とする。

本発明に係る動き推定装置の第４の構成は、前記第１乃至３の何れか一の構成において、前記動きベクトル仮推定手段は、前記対象フレーム内における前記対象ブロックＣ_０周囲の所定の範囲Ｒ_３内にあるブロックであって既に動きベクトルが決定されている各ブロックＣ_ｋ（ｋ∈Ｒ_３）の動きベクトルＭＶ_ｋに基づいて前記仮推定値ＭＶ_０”を決定することを特徴とする。

本発明に係る動き推定装置の第５の構成は、前記第４の構成において、前記仮推定値ＭＶ_０”は、（数１７）により計算されることを特徴とする。

本発明に係る動き推定装置の第６の構成は、前記第１乃至５の何れか一の構成において、前記所定の範囲Ｒ_１は、前記対象ブロックＣ_０に上下左右及び斜め方向に隣接し、かつ既に動きベクトルが決定されている４つのブロックの内の一部又は全部のブロックであることを特徴とする。

本発明に係る動き推定装置の第７の構成は、前記第１乃至５の何れか一の構成において、前記第１の代表値演算手段は、（数１８）により代表値δ_Ｔを計算することを特徴とする。

本発明に係る動き推定装置の第８の構成は、前記第１乃至７の何れか一の構成において、前記所定の範囲Ｒ_２は、前記ブロックＣ_０’に対して上下左右及び斜め方向に隣接する８つのブロックの範囲であることを特徴とする。

本発明に係る動き推定装置の第９の構成は、前記第１乃至７の何れか一の構成において、前記第２の代表値演算手段は、（数１９）により代表値δ_Ｔ−１を計算することを特徴とする。

本発明に係るプログラムは、コンピュータに上記第１乃至９の何れか一の構成の動きベクトル推定方法を実行させる

以上のように、本発明によれば、局所的な動き複雑性が大きい場合には、広範囲のブロック探索に適したブロック探索方法を選択し、局所的な動き複雑性が小さい場合には狭範囲のブロック探索に適したブロック探索方法を選択することが可能となる。これにより、ブロック探索に要する演算量を現実的な演算量に抑えつつ、動きが小さい場合において動きベクトルの推定精度を高く維持することができるとともに、動きが大きい場合に動きベクトルの予測が大きく外れることを防止することが可能となる。

また、対象ブロックＣ_０の動きベクトルの仮推定値が、真の動きを捉えるのに失敗した場合においても、対象ブロックＣ_０の周囲の「局所的な動き複雑性」を評価することで、対象ブロックＣ_０のみに着目する場合よりも、動きの存在をより敏感に捉え易くなる。すなわち、正確な動きタイプの予測が可能となり、映像内容が複雑な動きを示す場合であっても高い頑健性が得られる。そして、捉えられた動きに応じて、適応的にブロック探索方法が選択されるため、残留予測誤差をより小さくし、映像の圧縮率を改善することができる。

以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。

図３は一般の映像符号化装置１の全体構成を表す図である（非特許文献１１参照）。尚、図３の映像符号化装置１は、一般に広く使用されているものであるため、ここでの説明は、その概略説明のみにとどめる。

映像符号化装置１は、フレームメモリ２、差分器３、離散コサイン変換器（ＤＣＴ）４、量子化器５、エントロピ符号器６、局所復号器７、動き推定装置８、及び動き補償器９から構成されている。

フレームメモリ２は、撮像素子等から入力される映像フレームを一時的に記憶するメモリである。差分器３は、フレームメモリ２が出力する対象フレームｆ_Ｔから、動き補償器９が出力する予測フレームｆ_Ｔ’を差し引いた差分画像Δｆ_Ｔを出力する。ＤＣＴ４は、差分画像Δｆ_Ｔに対して離散コサイン変換を施す。量子化器５は、ＤＣＴ４により出力されるＤＣＴ係数を量子化する。エントロピ符号器６は、量子化器５が出力する量子化されたＤＣＴ係数と動き推定装置８が出力する動きベクトルＭＶとをエントロピ符号化して、符号化映像のビット列として出力する。

局所復号器７は、量子化器５が出力するＤＣＴ係数を再度もとのフレーム画像に復元する。そして、復元したフレーム画像を一時的に記憶し、対象フレームｆ_Ｔよりも前の参照フレームｆ_Ｔ−１”を出力する。動き推定装置８は、この参照フレームｆ_Ｔ−１”と対象フレームｆ_Ｔとを用いて、動きベクトルＭＶを推定し出力する。動き補償器９は、参照フレームｆ_Ｔ−１”と動きベクトルＭＶを用いて、対象フレームｆ_Ｔの予測値である予測フレームｆ_Ｔ’を生成し出力する。この予測フレームｆ_Ｔ’が、前記差分器３において差分画像Δｆ_Ｔを生成する際に使用される。

ここで、動き推定装置８において動きベクトルＭＶを生成するとき、及び動き補償器９において参照フレームとして、入力された映像からそのまま得られるフレームｆ_Ｔ−１を使用せず、局所復号器７で復元されたフレームｆ_Ｔ−１”を使用しているのは、映像復号側において復号画像に量子化誤差が蓄積することによりドリフトが生じることを防止するためである。

尚、局所復号器７は、逆量子化器１０、逆離散コサイン変換器（逆ＤＣＴ）１１、加算器１２、フレームメモリ１３から構成されている。量子化器５が出力するＤＣＴ係数は、逆量子化器１０に入力され逆量子化が施された後に、逆ＤＣＴ１１において逆離散コサイン返還が施され、差分画像Δｆ_Ｔ”が復元される。加算器１２において、この差分画像Δｆ_Ｔ”と動き補償器９が出力する予測フレームｆ_Ｔ’とが加算されて、復元された対象フレームｆ_Ｔ”がフレームメモリ１３に格納される。これらの構成は、一般的な映像復号器と同様である。

次に、本発明に係る動き推定装置８について説明する。図４は、本発明の実施例１に係る動き推定装置８の構成を表すブロック図である。

動き推定装置８は、動きベクトル記憶手段２０、動きベクトル仮推定手段２１、代表値演算手段２２，２３、探索方法選択手段２４、動きベクトル決定手段２５、及び探索中心決定手段２６を備えている。

動きベクトル記憶手段２０は、参照フレームｆ_Ｔ−１”及び対象フレームｆ_Ｔの各ブロックに対する動きベクトルＭＶ’，ＭＶを記憶するメモリである。

動きベクトル仮推定手段２１は、動きベクトル記憶手段２０に記憶されている動きベクトルＭＶに基づき、対象フレームｆ_Ｔ内のブロックであって動きベクトル推定の対象となるブロック（対象ブロック）Ｃ_０の動きベクトルＭＶ_０の仮推定値ＭＶ_０”を演算する。

代表値演算手段２２は、対象ブロックＣ_０の第１隣接の範囲Ｒ_１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣ_ｊ（ｊ∈Ｒ_１）の動きベクトルＭＶ_ｊと、仮推定値ＭＶ_０”との間の距離の代表値δ_Ｔを算出する。

代表値演算手段２３は、対象ブロックＣ_０に対応する参照フレームｆ_Ｔ−１”内のブロックＣ_０’の動きベクトルＭＶ_０’と、ブロックＣ_０’の第１隣接の範囲Ｒ_２内にある参照フレームｆ_Ｔ−１”内の各ブロックＣ_ｉ’（ｉ∈Ｒ_２）の動きベクトルＭＶ_ｉ’との間の距離の代表値δ_Ｔ−１を算出する。

探索方法選択手段２４は、代表値δ_Ｔ及び代表値δ_Ｔ−１の各値に対応して予め決められている各種ブロック探索方法の中から、代表値演算手段２２，２３により算出された代表値δ_Ｔ及び代表値δ_Ｔ−１の値に対応するブロック探索方法を選択する。

探索中心決定手段２６は、動きベクトル決定手段２５が探索を行う際の探索中心のオフセットを決定する。

動きベクトル決定手段２５は、探索方法選択手段２４により選択された探索方法に従って、探索中心決定手段２６により決定された探索中心を中心として、対象ブロックＣ_０との相関が最大である参照フレームｆ_Ｔ−１”内のブロックの探索を行い、動きベクトルＭＶ_０を決定し、動きベクトル記憶手段２０に保存する。

探索方法選択手段２４は、動きタイプ決定手段３１，３２、及び探索方法選択手段３３を備えている。動きタイプ決定手段３１は、代表値演算手段２２が出力する代表値δ_Ｔの値を閾値判定し、対象ブロックＣ_０の近傍の局所的な動きタイプＴＹＰＥ_１を決定する。動きタイプ決定手段３２は、代表値演算手段２２が出力する代表値δ_Ｔ−１の値を閾値判定し、対象ブロックＣ_０’の近傍の局所的な動きタイプＴＹＰＥ_２を決定する。そして、探索方法選択手段３３は、局所的な動きタイプＴＹＰＥ_１，ＴＹＰＥ_２によって、探索方法の選択を行う。

以上のように構成された本実施例に係る動き推定装置８について、以下その動き推定方法について説明する。動きベクトルの推定は、ラスタ走査の走査線に沿って、対象フレームの右上のブロックから左下のブロックに向かって行われるものとする。また、対象フレームの端に位置するブロックについては、全域探索法を用いて動きベクトルの推定が行われるものとする。以下では、対象フレームの端に位置するブロック以外の対象ブロックに対する動き推定動作について説明する。

図５は本発明の実施例１に係る動き推定方法を表すフローチャートである。まず、動きベクトル仮推定手段２１は、動きベクトル記憶手段２０から図２に示したコンテキストＴの各ブロックの動きベクトルＭＶ_１，ＭＶ_２，ＭＶ_３を読み出す。そして、対象ブロックＣ_０の動きベクトルの仮推定値ＭＶ_０”を（数２０）により算出する（Ｓ１）。

次に、代表値演算手段２２は、動きベクトル記憶手段２０から図２に示したコンテキストＴの各ブロックの動きベクトルＭＶ_１，ＭＶ_２，ＭＶ_３を読み出す。そして、先に算出された動きベクトルの仮推定値ＭＶ_０”と動きベクトルＭＶ_１，ＭＶ_２，ＭＶ_３とに基づき、対象フレームｆ_Ｔ内における対象ブロックＣ_０近傍の局所的な動き複雑性を算出する（Ｓ２）。ここでは、局所的な動き複雑性として、各ブロックＣ_ｊ（ｊ∈Ｒ_１）の動きベクトルＭＶ_ｊと、仮推定値ＭＶ_０”との間の距離の代表値δ_Ｔを用いる。従って、代表値演算手段２２は（数２１）により対象ブロックＣ_０近傍の局所的な動き複雑性である代表値δ_Ｔを算出する。

一方、代表値演算手段２３は、動きベクトル記憶手段２０から図２に示したコンテキストＴ−１の各ブロックの動きベクトルＭＶ_０’〜ＭＶ_８’を読み出す。そして、これらの動きベクトルＭＶ_０’〜ＭＶ_８’に基づき、参照フレームｆ_Ｔ−１”内におけるブロックＣ_０’近傍の局所的な動き複雑性を算出する（Ｓ３）。ここでは、局所的な動き複雑性として、各ブロックＣ_ｉ’（ｉ∈Ｒ_２）の動きベクトルＭＶ_ｉ’と、ブロックＣ_０’の動きベクトルＭＶ_０’との間の距離の代表値δ_Ｔ−１を用いる。従って、代表値演算手段２３は（数２２）により対象ブロックＣ_０近傍の局所的な動き複雑性である代表値δ_Ｔ−１を算出する。

次に、探索方法選択手段２４は、代表値δ_Ｔ及び代表値δ_Ｔ−１の各値に対応して予め決められている各種ブロック探索方法の中から、代表値演算手段２２，２３により算出された代表値δ_Ｔ及び代表値δ_Ｔ−１の値に対応するブロック探索方法を選択する（Ｓ４）。具体的には、まず、動きタイプ決定手段３１が、代表値δ_Ｔに基づき、（数９）に従って動きタイプＴＹＰＥ_Ｔを決定する。また、動きタイプ決定手段３２が、代表値δ_Ｔ−１に基づき、（数８）に従って動きタイプＴＹＰＥ_Ｔ−１を決定する。探索方法選択手段３３は、動きタイプＴＹＰＥ_Ｔ，ＴＹＰＥ_Ｔ−１により、（表１）に従って対象ブロックＣ_０の動きタイプを決定する。そして、対象ブロックＣ_０の動きタイプに基づき、（表２）に従って探索方法の選択を行う。このようにして、局所的な動き複雑性に従って、ブロックマッチングにおける探索戦略が適応的に決定される。

次に、探索中心決定手段２６は、動きベクトル決定手段２５が探索を行う際の探索中心のオフセットＶを、（数１０）〜（数１２）に従って決定する（Ｓ５）。

次に、動きベクトル決定手段２５は、探索方法選択手段２４により選択された探索方法に従って、対象ブロックＣ_０との相関が最大である参照フレームｆ_Ｔ−１”内のブロックの探索を行う（Ｓ６）。このとき、ブロック探索は、ブロックＣ_０”の位置から、ステップＳ５において決定されたオフセットＶだけ平行移動した位置を中心として行われる。これにより、対象ブロックＣ_０の動きベクトルＭＶ_０が決定される。

最後に、動きベクトル決定手段２５は、動きベクトルＭＶ_０を動きベクトル記憶手段２０に保存して（Ｓ７）、対象ブロックＣ_０の動きベクトル推定動作を終了する。

このような動きベクトル推定動作を、ラスタ走査の走査線に沿って、対象ブロックＣ_０を移動させながら順次行うことにより、対象フレームｆ_Ｔの動きベクトル推定を行うことができる。

尚、本実施例の動き推定装置は、映像の性質により適応的に探索戦略を変更できるため、映像内容が複雑な動きを示す場合であっても高い頑健性を得ることができるとともに、ハードウェア実装することもソフトウェア実装することも可能である。また、コンピュータ・プログラムとして構成し、汎用コンピュータによって実現することも可能である。

テスト映像（ＣＩＦ）から得られたフレーム内の動きベクトルマップを表す図である。 ブロックマッチングを行うために使用されるコンテキストの一例である。 一般の映像符号化装置の全体構成を表す図である。 本発明の実施例１に係る動き推定装置８の構成を表すブロック図である。 本発明の実施例１に係る動き推定方法を表すフローチャートである。

符号の説明

１ 映像符号化装置
２ フレームメモリ
３ 差分器
４ 離散コサイン変換器（ＤＣＴ）
５ 量子化器
６ エントロピ符号器
７ 局所復号器
８ 動き推定装置
９ 動き補償器
１０ 逆量子化器
１１ 逆離散コサイン変換器（逆ＤＣＴ）
１２ 加算器
１３ フレームメモリ
２０ 動きベクトル記憶手段
２１ 動きベクトル仮推定手段
２２，２３ 代表値演算手段
２４ 探索方法選択手段
２５ 動きベクトル決定手段
２６ 探索中心決定手段
３１，３２ 動きタイプ決定手段
３３ 探索方法選択手段

Claims (19)

1. 複数のフレームから構成される動画像において、参照フレームに対する対象フレーム内の各ブロックの動きベクトルを推定する動き推定方法であって、前記対象フレーム内における動きベクトル推定の対象となるブロック（以下、「対象ブロック」という。）Ｃ_０との相関が最大である前記参照フレーム内のブロックの探索を、以下の各ステップを有する選択手順で選択されたブロック探索方法に従って行うことにより、前記対象ブロックＣ_０の動きベクトルＭＶ_０を決定することを特徴とする動き推定方法：
   前記参照フレーム又は前記対象フレームの各ブロックの動きベクトルであって既に決定されているものに基づき、前記対象ブロックＣ_０の動きベクトルＭＶ_０の仮推定値ＭＶ_０”を決定する第１ステップ；
   前記仮推定値ＭＶ_０”と、前記対象フレーム内における前記対象ブロックＣ_０周囲の所定の範囲Ｒ_１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣ_ｊ（ｊ∈Ｒ_１）の動きベクトルＭＶ_ｊとの差のノルムである距離の代表値δ_Ｔを算出する第２ステップ；
   前記対象ブロックＣ_０に対応する前記参照フレーム内のブロックＣ_０’の動きベクトルＭＶ_０’と、前記ブロックＣ_０’の周囲の所定の範囲Ｒ_２内にある前記参照フレーム内の各ブロックＣ_ｉ’（ｉ∈Ｒ_２）の動きベクトルＭＶ_ｉ’との差のノルムである距離の代表値δ_Ｔ−１を算出する第３ステップ；
   前記代表値δ_Ｔ及び前記代表値δ_Ｔ−１の各値に対応して予め決められている各種ブロック探索方法の中から、前記第２ステップ及び前記第３ステップで算出された前記代表値δ_Ｔ及び前記代表値δ_Ｔ−１の値に対応するブロック探索方法を選択する第４ステップ。
2. 前記第４ステップにおいて、
   前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１よりも大きい場合には、ブロック探索方法として、所定の探索領域における多段探索法を選択し、
   前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１以下の場合には、ブロック探索方法として、前記多段探索法の探索領域よりも狭い探索領域での全域探索法を選択すること
   を特徴とする請求項１記載の動き推定方法。
3. 前記第４ステップにおいて、
   前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１よりも大きい場合においては、ブロック探索方法として、所定の探索領域Ｓ_０における多段探索法を選択し、
   前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１以下の場合においては、
   前記代表値δ_Ｔ−１の値が所定の閾値Ｔｈ_２よりも大きい場合には、ブロック探索方法として、前記多段探索法の探索領域Ｓ_０と同じ又はより狭い探索領域Ｓ_１での全域探索法を選択し、
   前記代表値δ_Ｔ−１の値が所定の閾値Ｔｈ_２以下の場合には、ブロック探索方法として、前記所定の範囲Ｒ _１ よりも狭い探索領域Ｓ_２での全域探索法を選択すること
   を特徴とする請求項１又は２記載の動き推定方法。
4. 前記第１ステップにおいて、前記仮推定値ＭＶ_０”は、前記対象フレーム内における前記対象ブロックＣ_０周囲の所定の範囲Ｒ_３内にあるブロックであって既に動きベクトルが決定されている各ブロックＣ_ｋ（ｋ∈Ｒ_３）の動きベクトルＭＶ_ｋに基づいて決定されることを特徴とする請求項１乃至３の何れか一記載の動き推定方法。
5. 前記仮推定値ＭＶ_０”は、（数１）により計算されることを特徴とする請求項４記載の動き推定方法。
   

   
6. 第２ステップにおいて、所定の範囲Ｒ_１は、前記対象ブロックＣ_０に対し第１隣接のブロックであって、かつ既に動きベクトルが決定されている４つのブロックの内の一部又は全部のブロックであること
   を特徴とする請求項１乃至５の何れか一記載の動き推定方法。
7. 第２ステップにおいて、代表値δ_Ｔは、（数２）により計算されることを特徴とする請求項１乃至５の何れか一記載の動き推定方法。
   

   
8. 前記第３ステップにおいて、前記所定の範囲Ｒ_２は、前記ブロックＣ_０’に対して隣接する８つのブロックの範囲であることを特徴とする請求項１乃至７の何れか一記載の動き推定方法。
9. 前記第３ステップにおいて、前記代表値δ_Ｔ−１は、（数３）により計算されることを特徴とする請求項１乃至７の何れか一記載の動き推定方法。
   

   
10. 複数のフレームから構成される動画像において、参照フレームに対する、対象フレームにおける各ブロックの動きベクトルを推定する動き推定装置であって、
    前記参照フレーム及び前記対象フレームの各ブロックに対する動きベクトルを記憶する動きベクトル記憶手段と、
    前記動きベクトル記憶手段に記憶されている動きベクトルに基づき、前記対象フレーム内のブロックであって動きベクトル推定の対象となるブロック（以下、「対象ブロック」という。）Ｃ_０の動きベクトルＭＶ_０の仮推定値ＭＶ_０”を演算する動きベクトル仮推定手段と、
    前記対象ブロックＣ_０周囲の所定の範囲Ｒ_１内にあるブロックであって既に動きベクトルが決定されている各ブロックＣ_ｊ（ｊ∈Ｒ_１）の動きベクトルＭＶ_ｊと、前記仮推定値ＭＶ_０”との差のノルムである距離の代表値δ_Ｔを算出する第１の代表値演算手段と、
    前記対象ブロックＣ_０に対応する前記参照フレーム内のブロックＣ_０’の動きベクトルＭＶ_０’と、前記ブロックＣ_０’の周囲の所定の範囲Ｒ_２内にある前記参照フレーム内の各ブロックＣ_ｉ’（ｉ∈Ｒ_２）の動きベクトルＭＶ_ｉ’との差のノルムである距離の代表値δ_Ｔ−１を算出する第２の代表値演算手段と、
    前記代表値δ_Ｔ及び前記代表値δ_Ｔ−１の各値に対応して予め決められている各種ブロック探索方法の中から、前記第１及び前記第２の代表値演算手段により算出された前記代表値δ_Ｔ及び前記代表値δ_Ｔ−１の値に対応するブロック探索方法を選択する探索方法選択手段と、
    前記探索方法選択手段により選択された探索方法に従って、前記対象ブロックＣ_０との相関が最大である前記参照フレーム内のブロックの探索を行い、前記動きベクトルＭＶ_０を決定し、前記動きベクトル記憶手段に保存する動きベクトル決定手段と、
    を備えていることを特徴とする動き推定装置。
11. 前記探索方法選択手段は、
    前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１よりも大きい場合には、ブロック探索方法として、所定の探索領域における多段探索法を選択し、
    前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１以下の場合には、ブロック探索方法として、前記多段探索法の探索領域よりも狭い探索領域での全域探索法を選択すること
    を特徴とする請求項１０記載の動き推定装置。
12. 前記探索方法選択手段は、
    前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１よりも大きい場合においては、ブロック探索方法として、所定の探索領域Ｓ_０における多段探索法を選択し、
    前記代表値δ_Ｔの値が所定の閾値Ｔｈ_１以下の場合においては、
    前記代表値δ_Ｔ−１の値が所定の閾値Ｔｈ_２よりも大きい場合には、ブロック探索方法として、前記多段探索法の探索領域Ｓ_０と同じ又はより狭い探索領域Ｓ_１での全域探索法を選択し、
    前記代表値δ_Ｔ−１の値が所定の閾値Ｔｈ_２以下の場合には、ブロック探索方法として、前記所定の範囲Ｒ _１ よりも狭い探索領域Ｓ_２での全域探索法を選択すること
    を特徴とする請求項１０又は１１記載の動き推定装置。
13. 前記動きベクトル仮推定手段は、前記対象フレーム内における前記対象ブロックＣ_０周囲の所定の範囲Ｒ_３内にあるブロックであって既に動きベクトルが決定されている各ブロックＣ_ｋ（ｋ∈Ｒ_３）の動きベクトルＭＶ_ｋに基づいて前記仮推定値ＭＶ_０”を決定することを特徴とする請求項１０乃至１２の何れか一記載の動き推定装置。
14. 前記仮推定値ＭＶ_０”は、（数４）により計算されることを特徴とする請求項１３記載の動き推定装置。
    

    
15. 前記所定の範囲Ｒ_１は、前記対象ブロックＣ_０に上下左右及び斜め方向に隣接し、かつ既に動きベクトルが決定されている４つのブロックの内の一部又は全部のブロックであること
    を特徴とする請求項１０乃至１４の何れか一記載の動き推定装置。
16. 前記第１の代表値演算手段は、（数５）により代表値δ_Ｔを計算することを特徴とする請求項１０乃至１４の何れか一記載の動き推定装置。
    

    
17. 前記所定の範囲Ｒ_２は、前記ブロックＣ_０’に対して上下左右及び斜め方向に隣接する８つのブロックの範囲であることを特徴とする請求項１０乃至１６の何れか一記載の動き推定装置。
18. 前記第２の代表値演算手段は、（数６）により代表値δ_Ｔ−１を計算することを特徴とする請求項１０乃至１６の何れか一記載の動き推定装置。
    

    
19. コンピュータに請求項１乃至９の何れか一記載の方法を実行させるためのプログラム。
    

Images