(57)【要約】  適応動き検索範囲を用いて動き推定を実施するための技術は、ターゲット画像内の画素ブロックにおける動きベクトルを算出する段階と、算出された動きベクトルを用いて、ターゲット画像内の画素のターゲットブロックに関係付けられた検索範囲を生成する段階と、生成した検索範囲を用いて画素のターゲットブロックの動きを推定する段階とを含む。【選択図】図２
2009509408.tif 000002
【特許請求の範囲】
【請求項１】
電子データプロセッサによって実施される方法であって、
ターゲット画像内の画素ブロックにおける動きベクトルを算出する段階と、
前記ターゲット画像内のターゲットブロックに対して近隣した前記ターゲット画像内のブロックの前記算出された動きベクトルを用いて、前記画素のターゲットブロックに関連付けられた検索範囲を生成する段階と、
前記生成した検索範囲を用いて、前記画素のターゲットブロックの動きを推定する段階と、
を含む方法。
【請求項２】
前記検索範囲を生成する段階が、前記算出された動きベクトルを用いて推定動き範囲を決定する段階を含む、
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記推定動き範囲を決定する段階が、低域通過フィルタを前記算出された動きベクトルに適用する段階を含む、
ことを特徴とする請求項２に記載の方法。
【請求項４】
前記フィルタを前記算出された動きベクトルに適用する段階が次式を含むことを特徴とする請求項３に記載の方法。
【数１】
2009509408.tif 000010
式中Ｌは、Ｌ＝［ｌ1，ｌ2，．．．，ｌn］、ｌiがタップｌのフィルタ係数、ｍｘ＾i,jが、前記ターゲットブロックの推定動き範囲のｘ軸の値、Ｍxが、前記算出された動きベクトルのｘ軸の値を含むベクトル、（Ｍx）Tが、ベクトルＭxの転置ベクトル、ｍｙ＾i,jが、該ターゲットブロックの推定動き範囲のｙ軸の値、Ｍyが、算出された動きベクトルのｙ軸の値を含むベクトル、（Ｍy）Tが、ベクトルＭyの転置ベクトルであるような、ｎ個のタップを有するフィルタである。
【請求項５】
前記動き検索範囲を生成する段階が、前記算出された動きベクトルの分散を決定する段階を含む、
ことを特徴とする請求項１に記載の方法。
【請求項６】
前記分散を決定する段階が、高域通過フィルタを前記算出された動きベクトルに適用する段階を含む、
ことを特徴とする請求項５に記載の方法。
【請求項７】
ラスター走査順序及びサブサンプリング順序からなるグループから選択される前記ターゲット画像内の前記ブロックにおけるブロック走査順序を決定する段階を更に含む、
請求項１に記載の方法。
【請求項８】
前記ターゲット画像内の画素ブロックにおける動きベクトルを算出する段階が、複数の参照画像を用いて前記動きベクトルを算出する段階を含む、
ことを特徴とする請求項１に記載の方法。
【請求項９】
ターゲット画像内の画素ブロックにおける動きベクトルを算出する動きベクトル算出器と、
前記ターゲット画像内のターゲットブロックに対して近隣した前記ターゲット画像内のブロックの前記算出された動きベクトルを用いて、前記画素のターゲットブロックに関連付けられた検索範囲を生成する検索範囲算出器と、
前記生成した検索範囲を用いて、前記画素のターゲットブロックの動きを推定する動き推定器と、
を備える装置。
【請求項１０】
前記検索範囲算出器が、前記算出された動きベクトルを用いて推定動き範囲を決定する、
ことを特徴とする請求項９に記載の装置。
【請求項１１】
前記検索範囲算出器が前記算出された動きベクトルに対して低域通過フィルタを適用する、
ことを特徴とする請求項１０に記載の装置。
【請求項１２】
前記検索範囲算出器が次式を適用することを特徴とする請求項１１に記載の装置。
【数２】
2009509408.tif 000011
式中Ｌは、Ｌ＝［ｌ1，ｌ2，．．．，ｌn］、ｌiがタップｌのフィルタ係数、ｍｘ＾i,jが、前記ターゲットブロックの推定動き範囲のｘ軸の値、Ｍxが、前記算出された動きベクトルのｘ軸の値を含むベクトル、（Ｍx）Tが、ベクトルＭxの転置ベクトル、ｍｙ＾i,jが、該ターゲットブロックの推定動き範囲のｙ軸の値、Ｍyが、算出された動きベクトルのｙ軸の値を含むベクトル、（Ｍy）Tが、ベクトルＭyの転置ベクトルであるような、ｎ個のタップを有するフィルタである。
【請求項１３】
前記検索範囲算出器が、前記算出された動きベクトルの分散を決定する、
ことを特徴とする請求項９に記載の装置。
【請求項１４】
前記検索範囲算出器が、高域通過フィルタを前記算出された動きベクトルに適用することによって前記分散を決定する、
ことを特徴とする請求項１３に記載の装置。
【請求項１５】
前記ターゲット画像内のブロックが、ラスター走査順序又はサブサンプリング順序で走査される、
ことを特徴とする請求項９に記載の装置。
【請求項１６】
前記動きベクトル算出器が、複数の参照画像を用いて前記動きベクトルを算出する、
ことを特徴とする請求項９に記載の装置。
【請求項１７】
処理システムによって実行されたときに、該システムに対して、
ターゲット画像内の画素ブロックにおける動きベクトルを算出する段階と、
前記ターゲット画像内のターゲットブロックに対して近隣した前記ターゲット画像内のブロックの前記算出された動きベクトルを用いて、前記画素のターゲットブロックに関連付けられた検索範囲を生成する段階と、
前記生成した検索範囲を用いて、前記画素のターゲットブロックの動きを推定する段階と、
を含む方法を実施させる命令のプログラムを記憶するコンピュータ可読媒体。
【請求項１８】
前記検索範囲を生成する段階が、前記算出された動きベクトルを用いて推定動き範囲を決定する段階を含む、
ことを特徴とする請求項１７に記載のコンピュータ可読媒体。
【請求項１９】
前記推定動き範囲を決定する段階が、低域通過フィルタを前記算出された動きベクトルに適用する段階を含む、
ことを特徴とする請求項１８に記載のコンピュータ可読媒体。
【請求項２０】
前記フィルタを前記算出された動きベクトルに適用する段階が次式を含むことを特徴とする請求項１９に記載のコンピュータ可読媒体。
【数３】
2009509408.tif 000012
式中Ｌは、Ｌ＝［ｌ1，ｌ2，．．．，ｌn］、ｌiがタップｌのフィルタ係数、ｍｘ＾i,jが、前記ターゲットブロックの推定動き範囲のｘ軸の値、Ｍxが、前記算出された動きベクトルのｘ軸の値を含むベクトル、（Ｍx）Tが、ベクトルＭxの転置ベクトル、ｍｙ＾i,jが、該ターゲットブロックの推定動き範囲のｙ軸の値、Ｍyが、算出された動きベクトルのｙ軸の値を含むベクトル、（Ｍy）Tが、ベクトルＭyの転置ベクトルであるような、ｎ個のタップを有するフィルタである。
【請求項２１】
前記動き検索範囲を生成する段階が、前記算出された動きベクトルの分散を決定する段階を含む、
ことを特徴とする請求項１７に記載のコンピュータ可読媒体。
【請求項２２】
前記分散を決定する段階が、高域通過フィルタを前記算出された動きベクトルに適用する段階を含む、
ことを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項２３】
ラスター走査順序及びサブサンプリング順序からなるグループから選択される前記ターゲット画像内の前記ブロックにおけるブロック走査順序を決定する段階を更に含む、請求項１７に記載のコンピュータ可読媒体。
【請求項２４】
前記ターゲット画像内の画素ブロックにおける動きベクトルを算出する段階が、複数の参照画像を用いて前記動きベクトルを算出する段階を含む、
ことを特徴とする請求項１７に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はビデオ圧縮分野に関する。
【背景技術】
【０００２】
ビデオシーケンスにおける高圧縮利得は、画像（フレーム）間の時間冗長性を除去することによって得ることができる。例えば、画像を符号化するために、符号化される画像の時間予測が前の符号化した画像に基づいて生成される。時間予測は、実際の画像と比較されて予測誤差を求め、この予測誤差は符号化される。予測は、広く用いられているブロックベースの動き推定及び補償法（例えばＭＰＥＧ規格）を用いて行うことができる。
【０００３】
動き補償及び推定法を用いて１つ又はそれ以上の参照画像内で参照ブロックを見つけ、ターゲット画像内の対応するターゲットブロックのロケーションを予測し、その結果、通常は予測誤差と動きベクトルである、ターゲットブロックの予測残差だけをコード化すればよいようにする。これらの方法は、ブロックマッチングを実施して、ターゲット画像内の対応するターゲットブロックに最も類似した、参照画像内の画素の参照ブロックを識別する。
【０００４】
参照ブロックと対応するターゲットブロックとの間の画素距離がターゲットブロックの動きベクトルである。例えば、ｍｘi,j、ｍｙi,jをｘ軸（横）及びｙ軸（縦）それぞれにおけるブロックＢijの動きベクトルとする。ビデオ圧縮においては、参照ブロックと共に動きベクトルの値を用いて、ターゲットブロックについての予測値を生成する。
【０００５】
図１は、例示的な動きベクトルの図である。ターゲット画像１２０は、参照画像１１０からの情報を用いて符号化されることになる。参照ブロック１１５は、ターゲット画像１２０内のターゲットブロック１２５に最も密接に整合する、参照画像１１０内のブロックとして識別される。参照ブロックが識別された後、動きベクトル１３０（単に例証の目的で矢印で示している）が生成され，参照ブロック１１５の位置に対するターゲットブロック１２５の位置を識別する。動きベクトル１３０は、参照ブロック１１５とターゲットブロック１２５との間の関係を表す２つの要素、水平変位と垂直変位とを有する。例えば、例示的な３×３の画素群である参照ブロック１１５は、ロケーション（ｉ’，ｊ’）に位置し、ターゲットブロック１２５はロケーション（ｉ，ｊ）に位置する。２つのブロック間の距離が動きベクトル（ｉ’−ｉ，ｊ−’ｊ）である。
【０００６】
参照画像内で参照ブロックを識別するために、参照画像内の候補ブロックをターゲットブロックと比較する。各候補ブロックは、ターゲットブロックと同じサイズを有し、参照画像内の特定の検索範囲内に位置付けられている。ターゲットブロックに最も密接に整合する候補ブロックが参照ブロックとして識別される。参照ブロックを検索する段階は、動き推定の重要な部分であり、通常は多大な算術計算を必要とする。
【０００７】
１つのターゲットブロックについて動き推定を実施する複雑さは、検索範囲内での利用可能な参照ブロックの数に比例し、動き検索範囲すなわち距離ｄの二乗に比例する（例えば、複雑さ＝ａｘｄ2、ここでａは定数）。動き検索範囲は、参照画像における区域を定義し、参照ブロックを見つけるのに用いられる。言い換えれば、検索範囲は、動き推定中に調査される参照画像におけるブロック数を指定する。
【０００８】
動き検索範囲は、画像内の物体の移動速度に関連付けられるはずである。例えば、高速に移動する物体では、ターゲットブロックを予測するための良好な対応ブロックを見つけるには大きな検索範囲が適切である。しかしながら、画像（又はフレーム）のどの部分が動きの量が少なく、どの部分が動きの量が多いかを予測することは、動き推定法を実施する前に行う場合には困難である。従って、典型的なビデオ圧縮法は、同じターゲット画像内の全てのブロックについて固定の動き検索範囲を用いている。
【０００９】
固定の動き検索範囲の欠点は、この範囲が画像内で最も高速に移動する物体を捉えるのに十分な程大きい場合、移動が少ない領域に対して検索計算が不必要に増加することである。逆に、検索範囲が小さ過ぎる場合、参照ブロックが検索範囲の外にある可能性があるので、動き推定法は、移動量の大きい参照ブロックを見つけることができない可能性がある。
【発明の開示】
【課題を解決するための手段】
【００１０】
適応動き検索範囲を用いて動き推定を実施するための技術は、ターゲット画像内の画素ブロックにおける動きベクトルを算出する段階と、算出された動きベクトルを用いて、ターゲット画像内の画素のターゲットブロックに関係付けられた検索範囲を生成する段階と、生成した検索範囲を用いて画素のターゲットブロックの動きを推定する段階とを含む。
【発明を実施するための最良の形態】
【００１１】
本発明は例証により説明され、添付図面と共に以下の説明を参照することにより十分に理解することができる。
【００１２】
以下の説明では、本明細書の一部を形成し、本発明を実施することができる特定の実施形態を例証として示している添付図面を参照する。他の実施形態を利用することも可能であり、本発明の範囲から逸脱することなく構造的変更を加えることができる点を理解されたい。例えば、様々な実施形態を説明するのに用いるフィールド、フレーム、画像、又は映像といった用語は、一般的にビデオデータに関して用いられるものと同義であることは当業者には理解されるであろう。
【００１３】
動き検索範囲を適応させる方法は、動き推定において用いられ、ターゲット画像内の動きについての既存の情報に基づいて、ターゲットブロックの動き検索範囲を自動的に調節する。本方法は、動きが低速の物体に対して検索範囲を縮小すること、及び高速に移動する物体に対して動き検索範囲を自動的に拡大することによって高速に移動する物体の予測品質を維持することの両方を行うことができる。例えば、本方法は、近隣ブロックについて前に算出した動き推定結果に従って、ターゲットブロックに対する動き検索範囲を適応的に調節する。従って、本方法の実施形態は、動き検索範囲を周囲領域における動きの量に適応させることによって、各ターゲットブロックについて動きベクトルを見つける複雑さを低減する。この適応的方法は、他の技術と組み合わせて、ビデオ圧縮法において時間予測を実施することができる。またこの適応的方法は、動き推定が必要な他のビデオ応用においても用いることができる。
【００１４】
図２は、適応的方法を用いて決定される動き検索範囲の実施例を示している。Ｂi,jを、ターゲット画像２２０における画素位置ｉ，ｊにあるターゲットブロック２２５とする。ここでｄｘi,j及びｄｙi,jは、それぞれ水平及び垂直方向の動き検索範囲である。この実施例では、参照画像２１０内の候補参照ブロックは、参照ブロック２１５を見つけるためにターゲットブロックと比較すべき数の候補ブロックを含む、［２ｄｘi,j＋１］×［２ｄｙi,j＋１］の矩形区域２３０内にある。この検索範囲は、動き推定を実施する計算の複雑さに対して直接的な影響を与える。近隣ブロックにおける動きの予測量に基づいてターゲットブロックに対するｄｘi,j及びｄｙi,jの値を適応的に調節することによって、近隣ブロックの動きの量が小さいことが予測される場合には、検索範囲のサイズを縮小することができる。結果として得られるより小さな検索範囲では、ターゲットブロックにおける動き推定を実施する計算上の複雑さが低減される。同様に幾つかの実施形態では、近隣ブロックの動きの量が大きいことが予測される場合には、検索範囲を相対的に大きくなるように適応させることができる。
【００１５】
一般に、Ｎx、Ｎyは、ターゲットブロックの最大水平及び垂直検索範囲である。検索範囲ｄｘi,j及びｄｙi,Jは、所与のターゲットブロックＢi,jに対する調節可能な検索範囲であり、前に算出された近隣ブロックからの動きベクトルを用いて算出される。動き推定が前に算出されていた近隣ブロックは、これらのブロックの動き推定がターゲットブロックの動き推定の前に決定されているので、先行近隣ブロックと呼ばれる。この処理は、検索範囲に対して固定値（例えばＮx、Ｎy）を用いるのではなく、前に算出された近隣ブロックからの動き推定を用いて、特定のターゲットブロックに対する検索範囲のサイズを自動的に適応させる。
【００１６】
図２に例示的に示す動き検索範囲を定義するｄｘi,j及びｄｙi,Jの値は、図３に示す例示的方法を用いてターゲット画像内の各ブロックに自動的に適応される。３１０で、ターゲット画像をブロックに分割する。３１５で、ブロックに対して動き推定を順次的に実施するための走査順序を定義する。３２０において、動き推定処理用にターゲットブロックを選択する。３２５では、本処理は、ターゲットブロックが、検索範囲を適応させるための十分な先行近隣ブロック（求められた動きベクトルを有する近隣ブロックである）を有するか否かを判定する。否である場合、３３０で、本処理はデフォルトの検索範囲を用いてターゲットブロックについて動き推定を実施する。例えば、図２のターゲット画像の左上のコーナーにあるブロックＢ0,0のような、走査順序シーケンスにおける初期ブロックは、符号化処理において先行近隣ブロックを持たない。この場合には、動き推定法の検索範囲パラメータを、シーケンス内のこの初期ブロックに対してデフォルト値：ｄｘi,j＝Ｎxdyi,j=Ny及びｄｙi,j＝Ｎyに設定することができる。次いで３４０で、ターゲットブロックについて動き推定を実施する。
【００１７】
幾つかの実施形態では、決定済み動きベクトルを有する単一の先行ターゲットブロック（例えば左上のブロック）は、適応検索範囲法を開始するのに十分である。他の実施形態では、決定済み動きベクトルを有する複数の先行ターゲットブロック（例えば、ラスター走査順序を用いる場合には、上及び左側の近隣ブロック）を必要とする。３３５で、十分な先行近隣ブロックを有するターゲットブロックについて、本処理は、先行近隣ブロックから調節係数を計算する。ターゲットブロックに対する検索範囲は、調節係数を用いて先行近隣ブロックにおける動きの量に自動的に適応され、３４０において、この適応済み範囲を用いてターゲットブロックについて動き推定を実施する。３４５では、本処理は、動き推定を他のブロックについて実施すべきかどうかを判定する。そうである場合には、本方法は３２０に戻る。さもなければ、３５０で処理は終了する。
【００１８】
以下は、図３に関係する例示的な実施形態の説明である。１つの事例では、図３に示す動き推定法の３３５において、先行近隣ブロックから算出される係数に基づいてターゲットブロックに対する検索範囲を調節する。これらの係数は次式となる。
【数１】
2009509408.tif 000003
ここで、ｍｘ＾i,j、ｍｙ＾i,jは、ターゲットブロックＢi,jに対する推定水平び垂直動き範囲であり、δx、δyは、先行近隣ブロックにおける動きの量とターゲットブロックにおける動きの量との間の推定相関量を表す。式１の背後にある概念は、ターゲットブロック内の画素の動きは、近隣ブロック内の画素の動きに類似している可能性が高いことである。従って、特定のターゲットブロックに対する動き検索範囲は、近隣動きベクトルによって示される、近隣ブロック内で既に判明している動きの量から自動的に決定される。
【００１９】
ターゲットブロックに対する動き範囲の推定
ターゲットブロックに対する動き検索範囲ｍｘ＾i,j、ｍｙ＾i,jにおける値は、先行近隣ブロックの動きベクトルから計算される。集合Ｐi,jをターゲットブロックＢi,jの先行近隣ブロックの集合と定義すると、ｍｘ＾i,j及びｍｙ＾i,jは、集合Ｐi,jにおける先行近隣ブロックの動きベクトルの関数として表わされる。１つの実施形態では、この関数は、集合Ｐi,jに属するブロックの動きベクトルの平均値であり、次式となる。
【数２】
2009509408.tif 000004
ここでＢk,l∈Ｐi,jは、集合Ｐi,jにおけるブロックを表し、ｎはＰi,j内のブロックの合計数である。この実施例では、上のブロック及び左のブロックのような２つのブロックが先行近隣ブロックである場合には、ｍｘ＾i,j及びｍｙ＾i,jは、２つの動きベクトルの平均として表わされる。
【数３】
2009509408.tif 000005
【００２０】
従って、ｍｘ＾i,j及びｍｙ＾i,jを発生させる関数は、集合Ｐi,jにおけるブロックの動きベクトルから決定される。この関数によって、適応動き検索範囲法は、ターゲット画像内の各ブロックに対して動き検索範囲を動的に決定する。１つの実施形態では、本方法は、近隣ブロックにおける動きの量についての情報を用いてターゲットブロック内の物体の動きの量を推定することによって、式３を用いてターゲットブロックに対して検索範囲を適応させる。
【００２１】
例えば、ターゲットブロックが、動きベクトルが小さい先行近隣ブロックを有する場合には、一般に、ターゲットブロックの動きの量が小さい。１つの実施形態における適応動き検索範囲法は、式（３）を用いてターゲットブロックに対して小さな検索範囲を発生させ、この動作は動き検索の複雑さを低減する。
【００２２】
他方、ターゲットブロックが、動きベクトルが大きい先行近隣ブロックを有する場合には、恐らくはターゲットブロックの動きの量は大きい。従って、１つの実施形態では、適応動き検索範囲法は、式３を用いてターゲットブロックに対する検索範囲を自動的に拡大する。次いで、動き推定は、高速に移動する物体に対する参照ブロックを識別するのに十分に大きい拡大検索範囲を用いてターゲットブロックについて実施される。
【００２３】
式（２）及び式（３）は、集合Ｐi,jにおける動きベクトルの平均値を算出するのに用いることができる関数の実施例である。先行近隣ブロック集合Ｐi,jにおける動きベクトルにフィルタを適用し、推定動き範囲ｍｘ＾i,j及びｍｙ＾i,jを生成することによって、より一般的な関数を得ることができる。一般性を失うことなく、項目ｍｘ＾i,jを導出するための実施例が示され、更に同じ手法で項目ｍｙ＾i,jを導出することができる。Ｌを、ｎ個のタップを含むフィルタ、Ｌ＝［ｌ1，ｌ2，．．．，ｌn］とし、ここでｌiは、Ｌにおけるｉ番目の要素であり、ｌｉはまた、タップｉのフィルタ係数である。Ｍxを、先行近隣ブロック内のブロック（Ｐi,j）の全ての動きベクトル（ｘ軸の値のみ）を含むベクトル、Ｍx＝［ｘ1，ｘ2，．．．，ｘn］とする。ここで次式が成り立つ。
【数４】
2009509408.tif 000006
ここで（Ｍx）Tは、ベクトルＭｘの転置ベクトルである。
【００２４】
式（２）及び式（３）に示す平均化法は、式４のフィルタリング法の特別な場合である。例えば、Ｌ＝［０．５，０．５］、Ｍx＝［ｍｘi-1,j，ｍｘi,j-1］、及びＭy＝［ｍｙi-1,j，ｍｙi,j-1］とすると、式（４）は式（３）に簡約される。
【００２５】
一般に、集合Ｐi,jにおけるブロック数がフィルタＬにおけるタップ数と等しいので、フィルタＬにおけるタップ数は、集合Ｐi,jにおけるブロック数を増やすことによって増加させることができる。
【００２６】
通常Ｌは、先行近隣ブロックの動きベクトルの統計平均値を得るのに用いられる低域通過フィルタ（平滑フィルタ）とすることができる。かかるフィルタを設計するために、多くの法を用いることができる（例えばフィルタＬにおける各フィルタ係数（ｌi）について値を選択する）。従って、適応動き検索範囲法は、低域通過フィルタを用いて、推定検索範囲ｍｘ＾i,j及びｍｙ＾i,jを得ることができる。
【００２７】
調節検索範囲の安全マージンの推定
式（１）における調節項目δx及びδyの値を動き検索範囲を調節するための安全マージンとして用いることができ、先行近隣ブロックの動きベクトルがターゲットブロックにおける動きの量を予想することができない可能性を考慮するようにする。例えば、先行近隣ブロックの動きベクトル分布が、大きな標準偏差を生じる場合には、調節値δx及びδyにより、ターゲットブロックの動き検索範囲が、先行近隣ブロックの動き検索範囲と有意に異なるようにすることができる。
【００２８】
δx及びδyに対する値の選択により、動き検索範囲がターゲットブロックの動き特性に適応することが可能になる。大きなδx及びδy値は、動き検索範囲内の高速に移動する物体を見つけることを可能にする。しかしながら、この値が大きくなるほど、検索範囲は拡大するので、動き検索の複雑さも増大する可能性がある。δx及びδyが小さいほど、適応速度を制限すると同時に、動き検索の複雑さを低減する。項目δx及びδyは、固定値又は調節可能な値のいずれかを有することができる。固定値を用いることによって平易性が得られる。δx及びδyに適応値を用いることによって、動き推定の精度を改善することができる。
【００２９】
δx及びδyをターゲットブロックの動き特性に適応させることができる様々な方法が存在する。一般的に、ターゲットブロックが、先行近隣ブロックの動きベクトルとは異なる動きベクトルを有する可能性が高い場合には、δx及びδyの値は大きくなるはずである。一般性を損ねることなく、項δxを導出する実施例を示す（項δyは同じ手法によって導出することができる）。
【００３０】
第１の実施例は、先行近隣ブロックの動きベクトルの標準偏差を用いてδxを導出する。例えば、ターゲットブロックＢi,jに対して次式が成り立つ。
【数５】
2009509408.tif 000007
ここで、Ｂk,l∈Ｐi,jは、集合Ｐi,jにおけるブロック全てを表し、ｎは、Ｐi,jにおけるブロックの合計数、ｍｘ＾i,jは、ターゲットブロックＢi,jの推定動き範囲（これは式（４）から導出することができる）、ｋはスカラー定数である。
【００３１】
第２の実施例は、先行近隣ブロックの動きベクトルにフィルタ処理を行い、δxを決定する。式（４）を用いて動き検索範囲を算出する方法と類似して、δx及びδyを得る一般的な方法は、ターゲットブロックＢi,jの先行動きベクトルにフィルタを適用する。通常このフィルタは、Ｈで表される高域通過フィルタを用いる。
【００３２】
Ｈを、ｎ個のタップを含むフィルタＨ＝［ｈ１，ｈ２，．．．ｈｎ］とすると、次式が成り立つ。
【数６】
2009509408.tif 000008
ここで、│ａ│は、ａの絶対値を表す。ベクトルＭｘ及びＭｙは、式（４）で与えられるものと同じ定義を有する。高域通過フィルタＨは、Ｍｘの分散（先行近隣ブロックの動きベクトル値）に関連付けられる。従って、δxが大きい時には、先行動きベクトルは大きな分散を有し、その逆もまた同様である。
【００３３】
例えば、先行近隣ブロック集合が、２つのブロック（例えば上及び左）を有し、高域通過フィルタが、Ｈ＝［０．５，−０．５］、Ｍx＝［ｍｘi-1,j，ｍｘi,j-1］、及びＭy＝［ｍｙi-1,j，ｍｙi,j-1］である場合には、次式が成り立つ。
【数７】
2009509408.tif 000009
幾つかの実施形態では、先行近隣ブロックの数を増やすことによって、より多くのタップを用いることができる。
【００３４】
複数の参照画像への拡張
上記に説明した例示的な実施例は、単一の参照画像に基づいている。幾つかの実施形態では、処理は、動き推定において複数の参照画像を用いる場合に拡張され、例えば、ターゲットブロックを異なる画像から予測することができる。これらの場合、動きベクトルは３つの要素、例えば［ｍｘi,j，ｍｙi,j，ｍｔi,j］を有し、ここでｍｔi,jは、特定の参照画像の時間インデックスである。
【００３５】
単一の参照画像の場合、先行近隣ブロックは同じ参照画像内に存在し、例えばこれらのブロックは、２次元表面にある。複数の参照画像を用いると、先行近隣ブロックの範囲は、その動き推定がターゲットブロックの動きが推定される前に決定される限り、例えば異なる画像において３次元に拡張される。従って、フィルタ（Ｌ及びＨ）が先行近隣ブロックの分布に従って構築される限り、ｍｘ＾i,j、ｍｙ＾i,j、及びδx、δyを取得するフィルタリング法を３次元の複数の参照の場合に即座に適用することができる。
【００３６】
ブロックのスキャナ順序の選択
各ブロックについて動き推定を実施するシーケンスを設定するブロックのスキャナ順序は、特定のターゲットブロックに対する先行ブロックとすることができるブロックの集合を決定し、すなわち、ターゲットブロックよりも早期に動き推定を算出できるブロックだけを該ターゲットブロックの先行ブロックとすることができる。従って、適応動き検索範囲法によって用いられるブロック走査順序のタイプは、特定のターゲットブロックに対する推定動き検索範囲に影響を及ぼす。
【００３７】
ブロック走査順序の１つの実施例は、図４に示すラスター走査順序である。この実施例では、ブロックを左から右、上から下に走査する。動き推定は、最初に、左上のコーナーにあるブロックについて実施され、１行目の各ブロックについて左から右に続く。次いで、２行目のブロックについて動き推定を実施し、ここでは左側の１番目のブロックから開始する。推定は、ターゲット画像内のブロックの全てを処理し終わるまで、この左から右、上から下への処理手順で続く。この処理手順は、左右上下走査順序（又はラスター走査順序）と呼ばれる。
【００３８】
図４に示す実施例では、陰付きブロックは、動き推定法によって処理が完了しており、従って、動きベクトルを有する。陰なしブロックでは、動き推定は未だ実施されていない。すなわち、動き推定法によって処理すべき次のブロックである特定のブロックＢij＝Ｘでは、そのブロックの先行近隣ブロック集合は、陰付きブロックの全てを含む。しかしながら、先行近隣ブロック集合は、先行ブロックの全てのうちのサブセットとして定義することができる。例えば、ブロックａからｅまでは、ターゲットブロックＸにおける動き検索範囲を調節するのに用いられる先行近隣ブロックＢij＝Ｘの集合、すなわちＰij＝［ａ，ｂ，ｃ，ｄ］として選択することができる。
【００３９】
この例では左から右の走査順序を用いているが、ブロックの走査順序は任意とすることができる。用いられる走査順序のタイプは、どの近隣ブロックがターゲットブロックよりも早期に動き推定結果を受け取るかを左右する。適応的方法は、少なくとも一部が先行近隣ブロックとして機能するブロックを用いて、ターゲットブロックに対する動き検索範囲を調節する。
【００４０】
ブロック走査順序の別の実施例は、図５に示すサブサンプリング走査順序である。例示的なターゲット画像５１０内の陰付きブロックで示すように、１回目では、一つおきのブロックを左から右及び上から下に走査する。この回で走査したブロックを、ターゲット画像内のブロックの全てからサブサンプリングする。次いで、例示的なターゲット画像５２０で示すように、２回目の走査の間に残りのブロックを走査する。
【００４１】
このサブサンプリングスキームの１つの利点は、２回目に走査したブロックを、図４に示すように上及び左方向のみではなく、全ての方向で先行近隣ブロックとすることができる点である。例えば、５２０におけるブロックＸは、ブロックｆ、ｇ、ｈ、ｉ、ｊ、及びｋを先行近隣ブロックとして有することができる。このように、ブロックａ及びｆは、サブサンプリング走査順序を用いるとターゲットブロックＸに対する先行近隣ブロックであるが、ラスター走査順序を用いると先行近隣ブロックではない。このサブサンプリング走査順序は、推定動き範囲（ｍｘ＾i,j.ｍｙ＾i,j）及び調節値（δx，δy）の取得の改善をもたらすことができる。
【００４２】
図６は、適応動き検索範囲法を用いるシステムの実施例を示している。デジタルビデオカメラ６１０は、電子的形式で画像を取り込み、圧縮及び符号化処理中に適応動き検索範囲法を実施する圧縮デバイス６２０を用いて画像を処理する。符号化された画像は、電子伝送媒体６３０を介してデジタル再生デバイス６４０に送信される。画像は、復号処理中にこの方法を用いる復号デバイス６５０によって復号される。カメラ６１０は、本発明の実施形態を含む様々な画像処理装置（例えば、他の画像取り込みデバイス、画像エディタ、画像プロセッサ、個人及び商用のコンピューティングプラットフォーム、その他）を例証するものである。同様に復号デバイス６５０は、画像データを復号する様々なデバイスを例示するものである。
【００４３】
本発明を特定のシステム環境における例示的な実施形態に関して説明したが、本発明は、添付の請求項の精神及び範囲内で他の異なるハードウェア及びソフトウェア環境において様々な方式で実施することができる点は当業者であれば理解されるであろう。
【図面の簡単な説明】
【００４４】
【図１】参照ブロックに基づいて生成されたターゲットブロックに対する動きベクトルの実施例を示す図である。
【図２】ビデオシーケンスにおいて動き推定を実施するための適応可能動き検索範囲の実施例を示す図である。
【図３】動き推定を実施する上で用いられるブロック対して動き検索範囲を適応させる方法の実施例を示す図である。
【図４】図３に示す方法において用いられるブロック走査順序の実施例を示す図である。
【図５】図３に示す方法において用いられるブロック走査順序の実施例を示す図である。
【図６】適応動き検索範囲法を用いるシステムの実施例を示す図である。
【符号の説明】
【００４５】
２１０  ターゲット画像
２１５  参照ブロック
２２０  ターゲット画像
２２５  ターゲットブロック
２３０  検索範囲の矩形区域
【図１】
2009509408.tif 000013
【図２】
2009509408.tif 000014
【図３】
2009509408.tif 000015
【図４】
2009509408.tif 000016
【図５】
2009509408.tif 000017
【図６】
2009509408.tif 000018
【国際調査報告】
2009509408.tif 000019