適応探索範囲を用いた動き推定
第１フレーム内のピクセルブロックの動きを推定する方法および装置であって、前記方法は、第２フレーム内の第１領域を探索して前記ピクセルブロックに対応する第１合致ブロックを識別するステップであって、前記第１合致ブロックは、前記ピクセルブロックと前記第１合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第１誤差値を含むステップと、前記第１合致ブロックに関連する第１動きベクトルを計算するステップと、を有する。前記方法はさらに、前記第２フレーム内の第２領域を探索して前記ピクセルブロックに対応する第２合致ブロックを識別するステップであって、前記第２合致ブロックは、前記ピクセルブロックと前記第２合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第２誤差値を含むステップと、前記第２合致ブロックに関連する第２動きベクトルを計算するステップと、前記第１および第２誤差値に基づき、前記第１および第２動きベクトルの間で最終動きベクトルを選択するステップと、を有する。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本出願は、２００７年１２月２０日に出願された、米国仮出願第６１／０１５，２２６号に基づく優先権を主張し、その内容は、参照によって、その全体が本願に組み込まれる。
【０００２】
本発明は、全体的にはビデオと画像の符号化の分野に関し、より具体的には、動き推定と補償のための方法およびシステムに関する。
【背景技術】
【０００３】
伝送ネットワーク、デジタル記憶媒体、超大規模集積デバイス、および映像音声信号のデジタル処理における技術的進歩により、広範な応用分野において、デジタルビデオが安価に伝送され、蓄積されるようになってきている。デジタルビデオ信号の蓄積と伝送は多くのアプリケーションの中心となっているので、デジタルビデオ符号化技術の使用は一般的になっている。
【０００４】
視覚情報は、生活のほぼ全ての領域において重要な役割を果たしている。画像とビデオに関連する膨大なデータ量に起因して、ビデオ符号化は重要な技術となっている。動き推定および補償は、様々なビデオ符号化手法において重要な役割を果たす。動き補償は、例えば、圧縮、ノイズ除去、走査変換、フレーム／フィールドレート変換のための画像補間のような様々なビデオアプリケーションにおいて用いることができる。
【０００５】
しかし、モバイル通信とインターネットが猛烈なスピードで発展するのにともない、現在の動き推定および補償の手法では、これまで増加してきた、インターネットや携帯テレビ電話を介したビデオストリーミングのようなアプリケーションの需要についていくことができなくなっている。
【０００６】
したがって、ビデオ符号化と補償の手法におけるより効率的な動き推定および補償が必要となっている。
【発明の概要】
【課題を解決するための手段】
【０００７】
本発明の実施形態に対応する、第１フレーム内のピクセルブロックの動きを推定する方法は、第２フレーム内の第１領域を探索して、ピクセルブロックに対応する第１合致ブロックであって、ピクセルブロックと第１合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第１誤差値を含む第１合致ブロックを識別するステップと、第１合致ブロックに関連する第１動きベクトルを計算するステップと、を有する。
【０００８】
本発明に係る方法はさらに、第２フレーム内の第２領域を探索して、ピクセルブロックに対応する第２合致ブロックであって、ピクセルブロックと第２合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第２誤差値を含む第２合致ブロックを識別するステップと、第２合致ブロックに関連する第２動きベクトルを計算するステップと、第１誤差値および第２誤差値に基づき第１動きベクトルと第２動きベクトルの間で最終動きベクトルを選択するステップと、を有する。
【０００９】
本発明のさらなる特徴と利点は、一部は以下の記載において説明され、一部はその記載から明らかであり、または本発明を実施することによって取得されるであろう。本発明の特徴と利点は、特許請求の範囲において特に指摘される要素と組合せの手段によって実現され、達成される。
【００１０】
添付する図面は、本明細書に組み込まれてその一部をなし、本発明の実施形態を示し、明細書の記載とともに本発明の原理を説明するのに役立つ。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態に対応するビデオ符号化システムのブロック図を示す。
【図２ａ】本発明の実施形態に対応するビデオフレーム例を示す。
【図２ｂ】本発明の実施形態に対応するビデオフレーム例を示す。
【図３】本発明の実施形態に対応する動画像例を示す。
【図４ａ】本発明の実施形態に対応するビデオフレームの他例を示す。
【図４ｂ】本発明の実施形態に対応するビデオフレームの他例を示す。
【図５】本発明の実施形態に対応する動き推定方法の概略図である。
【図６】本発明の実施形態に対応する他の動き推定方法の概略図である。
【図７】本発明の実施形態に対応する動き推定装置のハイレベルブロック図である。
【図８】本発明の実施形態に対応する他の動き推定装置のブロック図である。
【図９ａ】本発明の実施形態に対応する他の動き推定装置のブロック図である。
【図９ｂ】本発明の実施形態に対応する格子構造の概略図である。
【図１０】本発明の実施形態に対応する動きベクトルヒストグラムの概略図である。
【図１１】本発明の実施形態に対応する動き推定装置のブロック図である。
【発明を実施するための形態】
【００１２】
本発明の実施形態について、図面を詳細に参照する。実施形態の例は、添付する図面に記載されている。できる限り、同じまたは同様の部分については、図面全体を通して、同じ参照符号を用いる。
【００１３】
以下の説明および特許請求の範囲において、「連結」および「接続」という用語が、その派生語とともに用いられる場合がある。これら用語は、互いの同義語として意図されているのではないことが理解されるであろう。むしろ、特定の実施形態においては、「接続」および／または「連結」は、２以上の要素が互いに直接物理的にまたは電気的に接触していることを示す。しかし、「連結」はまた、２以上の要素が互いに直接接触してはいないが、互いに協調し、通信し、および／または相互作用することも意味する。
【００１４】
図１は、本発明の実施形態に対応するビデオ符号化システム１００のハイレベル機能ブロック図を示す。以下の説明および特許請求の範囲における様々な機能部が、実際には、個別にまたは組み合わせて、ハードウェア内、１以上のハードウェア部品（例えば、１以上のプロセッサ、１以上の特定用途向け集積回路（ＡＳＩＣｓ）、またはその他の同様部品）上で実行されるソフトウェア内、またはこれらの組み合わせにおいて実装し得ることが理解されよう。
【００１５】
図１に示すように、システム１００は、カメラ１０２からビデオ信号（Ｉ）を受け取るように連結され、信号ＩをエンコードしてビットストリームＢを得るように構成されたたエンコーダ部１０４を備えることができる。用途によっては、ビットストリームＢは、メモリ内に蓄積し、および／または通信チャンネルを介して伝送することができる。図１に示すように、システム１００はさらに、ビットストリームＢを受け取るように連結され、信号ＩをビットストリームＢから再構築するように構成されたデコーダ部１０６を備えることができる。システム１００はまた、デコーダ１０６に連結され、再構築された信号Ｉを表示するように構成されたディスプレイ１０８（例えば、モニタ、スクリーン、または同様なディスプレイデバイス）を備えることができる。先に説明したように、動き推定はビデオ符号化において重要な役割を果たし得るので、システム１００は動き推定部（ＭＥＵ）１１０を備えることができる。実施形態によっては、例示するＭＥＵ１１０のような動き推定部は、デコーダ１０６内に設けることができる。実施形態によっては、ＭＥＵ１１０は、例示するデコーダ１０６のようなデコーダ内に設けられた動き補償画像補間部（ＭＣＩＩＵ）１１１の一部として設けることができる。ＭＣＩＩＵ１１１は、ビデオの欠損したフレームを復元（再構築）する画像補間を実施するように構成することができる。本発明の実施形態に対応する動き推定部の詳細は、図７において詳しく説明する。
【００１６】
自然の視覚シーンは、空間的にも時間的にも連続している。典型的には、視覚シーンは、実シーンを空間的（通常は画像平面上の長方形格子）および時間的（定期的な時間間隔でサンプリングした一連の静止画像（フレーム）として）にサンプリングすることにより、デジタル形式で表すことができる。図１に示すように、カメラ１０２からの信号Ｉは、視覚シーンを１以上の静止画像（フレーム）（Ｉ１，Ｉ２，・・・，Ｉｎ−１，Ｉｎ）として表すことができる。
【００１７】
図２ａは、カメラ１０２のようなキャプチャ装置でキャプチャされた例示的な自然シーンからの静止画像２００の例を示す。画像２００は、背景に丘（２１２、２１４、２１６）と木（２０６、２０８、２１０）がある道路２０４上を走行している車２０２を示す。画像２００は、図２ｂに示すように、Ｐ×Ｑの長方形格子Ｒ上にサンプリングすることにより、デジタル形式で表すことができる。長方形格子Ｒ上の各点Ｒ（ｐ，ｑ）（０≦ｐ≦Ｐ−１、０≦ｑ≦Ｑ−１）は、画像要素（ピクセル）に対応させることができる。各ピクセルは、明るさ（輝度）および／または色を表す数値または数値セットによって表すことができる。デジタルアプリケーションにおいて、ピクセルは１以上のバイナリ値として表すことができ、各フレームは対応するピクセル値の配列（または行列）として表すことができる。アプリケーションの種類に基づき、フレーム内のピクセルの数（Ｐ×Ｑ）が異なることが理解されよう。したがって本開示は、本発明に対応するフレーム内に含まれるピクセル数を限定するものではない。
【００１８】
典型的には、例示する画像２００のような静止画は、画像２００の２次元投影をセンサ（例えば電荷結合素子のアレイ（ＣＣＤアレイ））上にフォーカスすることにより、キャプチャ装置（例えばカメラ１０２）を用いて２次元サンプリングされた画像として得られる。ピクセル配列（ピクセル値の配列）は、ＣＣＤアレイの出力から得られる。場合によっては、カラー画像について、ＣＣＤアレイの出力を１以上の色成分にフィルタリングし得る。各色成分は、対応するピクセル配列を有する。例えば、ＲＧＢ（赤、緑、青）色モデルにおけるカラー画像は、各色成分について１以上のピクセル配列を有し得る。
【００１９】
先に説明したように、自然シーンは（Ｉ１，Ｉ２，・・・，Ｉｎ−１，Ｉｎ）のような一連のフレームとして表すことができる。これらフレームは、一連の完全フレームおよび／または一連のインタレースフレームとしてサンプリングすることができる。本開示の実施形態は、上記種類のフレーム（プログレッシブまたはインタレース）を使用することに制約されず、また限定されないことが理解されよう。
【００２０】
図３は、道路２０４を走行する車２０２（図１ａと１ｂに示した）の動画像３００の例を示す。ビデオ３００は、周期的時間間隔における例示フレーム３０２、３０４、３０６、３０８のような一連のフレームによってキャプチャすることができる。一連のフレームを再生することにより、車２０２が動いているように見せることができる。便宜上図３は、ビデオ３００が４フレーム（３０２、３０４、３０６、３０８）を含むものとして示した。しかし実際には、例示するビデオ３００のような所与のビデオ内に含まれる、任意数（ｎ）のフレームが存在し得ることが理解されよう。したがって本開示は、本発明に対応するシステムに含まれ、サポートされるフレーム数に限定されない。
【００２１】
ビデオ３００の各フレームは、図２ａと２ｂについて説明したものと同様の手法によりデジタル形式で表すことができる。したがって、ビデオ３００内の各フレームは、複数のビットによって表すことができる。典型的には、フレームレートが高くなると（１時刻単位毎に取得されるフレーム数）、動きは滑らかになり、ビデオ３００の品質は全体的に良くなる。しかし、フレームレートを増やすと、例示するビデオ３００のようなビデオ画像を表すために必要なビット数も増える。
【００２２】
ほとんどのビデオアプリケーションの記憶容量と帯域は限られているので、様々な符号化手法（および／または圧縮）をエンコーダ部（例えば、例示するエンコーダ部１０４）によって実装し、所与のビデオを表すために必要なビット数とビデオ品質の間のバランスを取ることができる。
【００２３】
典型的には、ほとんどのビデオ符号化手法は、シーン内の冗長情報を時間的にも空間的にも利用し、圧縮を実現する。時間ドメインでは、時間的に隣接するフレーム間、すなわち時間順で連続するフレーム間には、特に高フレームレートにおいて高い相関（類似性）がある。空間ドメインでは、互いに近接するピクセル間、すなわち隣接するピクセル間に高い相関がある。図３に見られるように、フレーム３０２、３０４、３０６、３０８において、丘（２１２、２１４、２１６）、木（２０６、２０８、２１０）、道路２０４に関するピクセルは、全てのフレーム（３０２、３０４、３０６、３０８）内で一定（冗長）である。したがって、各フレーム内の冗長な情報を表す必要性をなくすことにより、ビデオ３００を表すために必要な全体的ビット数を抑えることができる。これは、１以上のフレーム内の共通するピクセルを識別することによってなされる。
【００２４】
しかし、ピクセル毎にフレームを処理することは、計算が複雑である。場合によっては、計算の複雑さを低減し、さらに圧縮率を改善するため、フレームを複数の領域（特にブロック）に再分割し、ブロック毎に処理することもできる。典型的には、領域（ブロック）は複数の隣接ピクセルを含み、サイズがそれぞれ異なっていてもよい。アプリケーションの種類によっては、ブロックは互いに重なり合っていてもよい。
【００２５】
図４ａは、それぞれ１６×１６ピクセルを含む５×５固定サイズブロック（例えば、例示するピクセルブロック４０２）によって分割された例示フレーム３０２を示す。便宜上図４ａは、フレーム３０２が５×５ピクセルブロックを有するものとして示している。しかし実際には、所与のフレームは任意数の（Ｕ＜Ｐ、Ｖ＜Ｑ）の（Ｕ×Ｖ）ピクセルブロックを含み、各ピクセルブロックは任意数のピクセルを含み得ることが理解されよう。したがって本発明は、本発明に対応するフレーム内に含まれるピクセルブロックの数および／またはサイズに限定されるものではない。
【００２６】
場合によっては、ビデオ品質をさらに向上させるため、フレームを可変ブロックサイズに分割することもできる。図４ｂは、可変サイズブロック（例えば、例示するピクセルブロック４０２、４０４、４０６）に分割された例示フレーム３０２を示す。便宜上図４ｂは、フレーム３０２が異なるブロックサイズのピクセルブロック４０２、４０４、４０６を含むものとして示している。しかし実際には、所与のフレームは任意数の（Ｕ×Ｖ）ピクセルブロックを含み、各ピクセルブロックはさらに任意数の（ｕ×ｖ）ピクセルブロック（ｕ＜Ｕ、ｖ＜Ｖ）に分割し得ることが理解されよう。したがって本発明は、本発明に対応するフレーム内に含まれるピクセルブロックの数および／またはサイズに限定されない。
【００２７】
典型的には、ビデオフレーム間の変更は、物体の動き（例えば移動中の車）、カメラの動き（例えばパン、傾斜、ズーム、回転など）、覆いが外された領域（例えば移動中の車によって覆われたシーン背景部分）、光の変更によってもたらされる。光の変更は例外だが、動きは典型的にはフレーム間のピクセル移動に関わる。したがって、連続フレーム間の各ピクセルの軌跡を予測することにより（動き推定）、各ピクセルを参照フレーム（過去のまたは未来のフレーム）内で移動させて（関連する軌跡に基づき）現在のフレームを正確に再構築することができる（動き補償）。１以上のフレームは単一の参照フレームによって表すことができるので、ビデオ画像全体を表すために必要なビット数を削減することができる。
【００２８】
しかし、先に説明したように、ピクセル毎にフレームを処理するのは計算コストが高い。したがって、計算の複雑さを低減するため、実施形態によっては、動き推定部（ＭＥＵ）１１０によって様々なブロック毎の動き推定手法を実装することができる。
【００２９】
図４ａと４ｂについて先に説明したように、例示フレーム３０２のような所与のフレームは、１以上の固定および／または可変サイズピクセルブロックに分割することができる。ブロックベースの動き推定において、現在ブロックは参照フレーム内の同サイズのシフトされた他ブロックと比較される。現在ブロックとシフトされた参照ブロックが最も合致するとき、２つのブロック間の最適変位または動きを表す１以上の動きベクトル（ＭＶ）が得られる。実施形態によっては、動きベクトルは２次元であり、水平成分と垂直成分を有する。したがって現在のフレームは、変位した（移動した）ブロックを識別し、参照フレーム内の全ての対応する変位ブロックをそれぞれの動きベクトルで補償することにより、参照フレームを用いて表すことができる。
【００３０】
例えば例示ビデオ３００において、フレーム３０４は、フレーム３０４内で移動したブロックを識別し、変位したブロックに対応する動きベクトルを計算し、フレーム３０２内の変位したブロックを対応する動きベクトルで補償することによって、例えばフレーム３０２のような参照フレームを用いて表すことができる。したがって、フレーム３０４に関連する全てのピクセル値を保存することに代えて、フレーム３０４内の変位したブロックに関連するＭＶおよびフレーム３０２と３０４の間の任意の差異（例えば車２０２の移動によって覆いが外された領域）のみを保存する必要がある。
【００３１】
実施形態によっては、ＭＥＵ１１０は、参照フレームおよび１以上の現在フレーム内のブロック間の動きを推定するためのブロックマッチング手法を実装することができる。１実施形態において、ＭＥＵ１１０は、誤差判定基準（例えば絶対誤差の合計（ＳＡＤ）、２乗誤差の合計（ＳＳＤ）、絶対変換誤差の合計（ＳＡＴＤ）、または他の同様の誤差判定基準）を、現在のブロックに含まれる全てのピクセルについて用い、参照フレーム内の対応する「最も合致する」ブロックを探索するように構成することができる。典型的には、ＳＡＤ基準の計算の単純さまたはコスト機能により、これが最もよく用いられる。
【００３２】
実施形態によっては、ＭＥＵ１１０はフルサイズの網羅的な探索を実施し、探索領域（または範囲）内の全ての動きベクトルについての大域最小ブロック合致誤差（例えば、最小ＳＡＤ値）を見つけることができる。最小合致誤差を有する動きベクトルは、大多数のピクセルについての最良の動き推定を表し、これに関連するブロックを最良合致ブロックとして選択することができる。
【００３３】
図５は、本発明の実施形態に対応するＭＥＵ１１０によって実装することができるフルサイズ網羅的探索ブロック合致手法の例示図である。図５は、参照フレーム５０２と現在フレーム５０４を示す。フレーム５０２と５０４は、図３で説明したフレームと類似していてもよい。現在フレーム５０４は、図４ａと４ｂで説明したピクセルブロックに類似する例示的な現在ブロック５０６を含むことができる。図５に示すように、ブロック５０６に属する画像詳細部分の位置は、フレーム５０２から５０４へ変化する場合がある。
【００３４】
図５に示すように、全探索領域５０３は、参照フレーム５０２においてブロックマッチング処理を実施して現在ブロック５０６に関連する１以上の最良合致ブロック（および対応する動きベクトル）を識別するために用いることができる。ブロック５０６（フレーム５０４内）の空間的に整列した位置は、参照フレーム５０２内においてゼロ変位ブロック５０７によって示されている。
【００３５】
全探索領域５０３のサイズは、画像解像度（フォーマット）、フレームレート、アプリケーション種別に依拠し得る。実施形態によっては、全探索領域５０３は、水平サイズ［−Ｍ／２〜Ｍ／２］ピクセル、垂直サイズ［−Ｎ／２〜Ｎ／２］ピクセルの（Ｍ＋１×Ｎ＋１）ピクセルを含む長方形の範囲を有する。ここで、ＭとＮは偶数であり、（Ｍ＋１≦Ｐ、Ｎ＋１≦Ｑ）である。実施形態によっては、全探索領域５０３のサイズは、速度が異なる画像フォーマットにおける動きベクトル間で同様に表されることを確実にするため、画像フォーマットに比例してもよい。速度は、フレーム内の物体がフレームを一端から他端に向かって横切るために必要な時間量として定義される。例えば、ＨＤＴＶ１０８０ｐ画像シーケンスで用いられる探索領域は、類似する動きベクトルを取得するため、ＨＤＴＶ７２０ｐ画像シーケンスで用いられる探索領域よりも２２５％大きい。実施形態によっては、フレーム５０２内で、全探索領域５０３の中心をゼロ変位ブロック５０７にすることができる。
【００３６】
実施形態によっては、参照フレーム５０２内のシフト探索ブロック（ブロック５０８、５１０として２度示している）は、現在ブロック５０６と同じサイズを有し、全探索領域５０３内で発生し得る（ブロック５０６の）変位と関連するブロック合致誤差を計算するため、単位ピクセル増加によって変位させることができる。大域最小ブロック合致誤差に対応する変位は、最良合致ブロックとして識別することができる。例えば図５において、参照フレーム５０２内のブロック５０６について、ブロック５０８は「最良合致」候補として示されており、ブロック５１０は代替の「最良合致」候補として示されている。図５に示すように、ブロック５０８と５１０にそれぞれ動きベクトルＭＶ１とＭＶ２を割り当てることができる。便宜上図５では、全探索領域５０３が２つのブロック（５０８と５１０）と対応する動きベクトル（ＭＶ１とＭＶ２）のみを、現在ブロック５０６についての最良合致候補として含むように記載している。しかし実際には、全探索領域内に含まれる任意数の最良合致候補（ＭＶおよび／またはブロック）が存在し得ることが理解されよう。したがって本発明は、本発明に対応する探索領域内に含まれるＭＶの数に限定されるものではない。
【００３７】
図５で説明したように、ＭＥＵ１１０は、フルサイズ網羅的探索を実施することにより、参照フレーム５０２内の最良合致ブロック５０８と５１０を識別することができる。しかし、フルサイズ網羅的探索手法は、所与のフレーム内のブロック数が増加すると、計算コストが高くなる。さらに、フルサイズ網羅的探索手法を用いると、図５に示すように複数の最良合致ブロックが得られる場合がある。動き補償および／または画像補間のときに最良合致ブロックが誤っていると、多大な不具合が生じる。マッチング誤差を起こす画像特徴には、多くの種類がある。例えば、直線形状の場合、当該形状に平行な任意長の動きベクトルが、フルサイズ探索から得られる場合がある。そして、直線形状に関連するその動きベクトルがランダムに選択され、当該形状近傍の他のピクセルを補間するときに誤差を引き起こす場合がある。
【００３８】
例えば図５において、フレーム５０２内のＭＶ２（ブロック５１０に関連付けられている）が、現在ブロック５０６に関連する真の動きベクトルであると仮定する。合致ブロック５０８と５１０はともに同程度の低い合致誤差値を持つので、ＭＥＵ１１０はブロック５０６についての最良合致としてブロック５０８を誤って選択する可能性がある。このような誤ったブロック合致は、ビデオ品質を劣化させる。
【００３９】
動きベクトルは画像補間に用いることができるので、画像シーケンス内の物体の真の動きと詳細部分を正確に表すことにより、画像オブジェクトとその詳細部分が適正に補間された空間上の位置に変位することを確実にし、補間後画像内に不具合が存在することを回避できる。
【００４０】
画像は、格子構造または周期構造とも呼ばれる様々な繰り返し構造を含む場合があるので、これら格子構造を識別すると、真の動きの表現を改善することに役立つ。実施形態によっては、ＭＥＵ１１０は、画像内の様々な格子構造を識別する１以上の格子構造マップ（または格子構造周期マップ）を生成する格子構造検知手法を実装することができる。格子構造周期マップは、水平動きベクトル成分を分類する水平ピッチ周期値と、垂直動きベクトル成分を分類する垂直ピッチ周期値を含む。ピッチ周期は、格子構造の最小繰り返し単位として定義することができる。
【００４１】
ＭＥＵ１１０によって実装することができる格子構造検知手法については、図９ａと９ｂを用いて詳細に説明する。
【００４２】
格子構造は、建物、窓、焼き網、フェンス、テキストなどの物体内に顕著に存在する。網羅的全探索手法（図５で説明した）において、ＭＥＵ１１０は、全探索領域（例えば探索領域５０３）内において、同程度の低ブロック合致誤差を有する複数の最良合致動きベクトル（図５に示した）を識別することができる。例えば、格子構造が１０ピクセルの水平ピッチ周期（格子構造の最小繰り返し単位）を有し、真の水平動作が＋３ピクセルである場合、ＭＥＵ１１０は、最良合致候補として、−７ピクセル（３−１０）または＋１３ピクセル（３＋１０）の水平動作を見つける可能性がある。真の動きベクトルに対応する１つの局所最小合致誤差が存在する可能性があるが、場合によっては、シーンの光の変化、カメラのパン動作、または同様の潜在的な光イフェクトのような影響により、大域最小合致誤差が１以上の識別された最良合致候補に関連付けられる可能性がある。探索領域（例えば全探索領域５０３）のサイズを削減することにより、局所最小値の数を少なくすることができる。これにより、大域最小値が真の動きベクトルに関連付けられる可能性が高まる。しかし、全探索領域５０３が小さいと、限られた範囲の物体変位のみが適正に推定され、総合的な動き推定結果について妥協することになる。したがって、動き推定に関して妥協することなく誤ったブロック合致が生じないようにするため、実施形態によっては、ＭＥＵ１１０は、適応探索手法を実装して最良合致ブロック（および動きベクトル）を見つけることができる。
【００４３】
図６は、本発明の実施形態に対応するＭＥＵ１１０によって実装することができる適応探索手法の概略図である。図６は、参照フレーム５０２と現在フレーム５０４を示す。図５で説明した手法と同様に、ブロック５０６の位置はフレーム５０２から５０４に向かって変化する。
【００４４】
図６に示すように、全探索領域５０３に加えて、参照フレーム５０２内で適応探索領域６０３を用いて、ブロックマッチング処理を実施し、現在ブロック５０６に関連する１以上の最良合致ブロックを識別（および動きベクトルを推定）することができる。実施形態によっては、全探索領域５０３と適応探索領域６０３の中心をゼロ変位ブロック５０７にすることができる。
【００４５】
実施形態によっては、全探索ブロックマッチングを全探索領域５０３内で実施し、ブロック合致誤差のサブセットを、適応探索領域６０３に含まれる（範囲にある）全ての変位について収集することができる。最良合致ブロックの位置に対応する局所最小誤差を見つけるため、ブロック合致誤差（領域５０３内と６０３内で計算される）が比較される。例えば図６は、対応する動きベクトルとしての動きベクトル６０５とともに、最良合致ブロックとしてブロック５１０（適応探索領域６０３内に含まれる）を示す。先に説明したように、全探索領域５０３と適応探索領域６０３は、複数の最良合致ブロックと対応する動きベクトルを含むことができる。便宜上以下の説明は、全探索領域５０３内に含まれる全ての最良合致ＭＶと対応するブロック合致誤差を、それぞれ最良合致ベクトル６０７、ブロック合致誤差６０９として、まとめて参照する。同様に以下の説明は、適応探索領域６０３内に含まれる全ての最良合致ＭＶと対応するブロック合致誤差を、それぞれ最良合致ベクトル６０５、ブロック合致誤差６１１として、まとめて参照する。
【００４６】
実施形態によっては、全探索領域５０３のサイズは固定かつ長方形であってもよく（図５で説明したものと同様に）、一方で適応探索領域６０３は範囲が可変であり、かつ予測動き値によって（ゼロ変位ブロック５０７の中心から）オフセットしてもよい。
【００４７】
実施形態によっては、適応探索領域６０３は、水平サイズ［−Ｍ／２〜Ｍ／２］ピクセル、垂直サイズ［−Ｎ／２〜Ｎ／２］ピクセルの（Ｍ＋１×Ｎ＋１）ピクセルを含む長方形の範囲を有する。ここで、ｍとｎは偶数であり、（ｍ＜Ｍ、ｎ＜Ｎ）である。実施形態によっては、適応探索領域６０３は、動きオフセット値オフセット（Ｏｈ、Ｏｖ）ピクセルを有し、ＯｈとＯｖは、全探索領域５０３中心から見た適応探索領域６０３中心の対応する水平軸オフセットと垂直軸オフセットである。実施形態によっては、ｍ、ｎ、Ｏｖ、Ｏｈは、格子構造マップと動きベクトルヒストグラム（ＭＶＨ）から取得することができる。
【００４８】
ＭＶＨは、水平軸上の全ての水平動き値（ＭＶｈ）［−Ｎ／２〜Ｎ／２］、および垂直軸上の全ての垂直ピッチ周期値（Ｔｈ）［２〜Ｎ］を表す２次元ヒストグラム配列であってもよい。実施形態によっては、ＭＶＨは、各ヒストグラムビンが画像ピクセルに類似しているという意味において、小画像に類似している。実施形態によっては、２つのヒストグラムを各フレームから生成することができる。そのうち１つは水平動きベクトル成分および水平周期について、もう１つは垂直動きベクトル成分および垂直周期についてである。ＭＥＵ１１０が用いることができるＭＶＨを、図１０に詳細に示した。
【００４９】
格子構造内では典型的に、２つの良好な候補ベクトル成分間の距離は、複数のピッチ周期値である。式（１）は、ピッチ周期値（Ｔ）を有する格子構造における、真の動きベクトル（ＭＶＴ）と任意の選択された動きベクトル（ＭＶＳ）の間の関係を示す。
ＭＶＴｈ＝ＭＶＳｈ＋ｋ×Ｔｈ （１）
ここで、（ｈ）は動きベクトルとピッチ周期の水平成分を示し、ｋは選択された動きベクトルが真の動きベクトルからオフセットしている周期数を示す符号付整数変数である。理想的な状況では、ｋ＝０である。
【００５０】
式（１）から導かれるように、適応探索領域６０３内の局所最小値の数を、１に限定することができる。このとき、ｍは垂直ピッチ周期値（Ｔｖ）未満であり、ｎは水平ピッチ周期値（Ｔｈ）未満である。実施形態によっては、適応探索の範囲６０３（例えばｍ、ｎ、Ｏｈ、Ｏｖ）は、式（２）（３）に基づいてセットすることができる。
ｍ＝Ｔｖ−１ （２）
ｎ＝Ｔｈ−１ （３）
式（２）（３）に見られるように、ＴｈとＴｖはともに２以上であると仮定されている。Ｔｖ＝０である場合、垂直格子構造は検出されず、ｍはＭに関連する一定値にセットされ、オフセットＯｖ＝０となる。Ｔｈ＝０である場合、水平格子構造は検出されず、ｎはＮに関連する一定値にセットされ、オフセットＯｈ＝０となる。
【００５１】
実施形態によっては、適応探索領域６０３は、高速動作（変位）が存在するときは省略できる。実施形態によっては、ブロック合致誤差計算がさらに要求されることがないようにするため、適応探索領域６０３は、全探索領域５０３の包括的なサブセットであってもよく、その他の全ての領域におけるブロックマッチングは無視してよい。例えば、オフセット（Ｏｈ＝Ｎ／２）、適応探索領域６０３の中心位置が全探索領域５０３の右境界にあるとき、これにより適応探索領域６０３の左半分のみが考慮される。
【００５２】
実施形態によっては、探索領域５０３および６０３のサイズは、画像解像度に依拠する。例えば、高解像度ＨＤ−１０８０の領域５０３および６０３のサイズは、ＨＤ−７２０についてのサイズよりも大きく、またＨＤ−４８０についてのサイズよりも大きい。実施形態によっては、ＳＤ−７２０についての探索領域５０３および６０３はＳＤ−４８０についてのサイズの２倍であり、ＨＤ−１０８０についてはＳＤ−４８０のサイズの３倍である。
【００５３】
便宜上図６において、フレーム５０２は２つの探索領域（全探索領域５０３と適応探索領域６０３）を含む。しかし実際には、所与のフレームは任意数の探索領域を含み得ることが理解されよう。したがって本発明は、本発明に対応するフレーム内に含まれる探索領域の数に限定されるものではない。
【００５４】
便宜上図６において、全探索領域５０３と適応探索領域６０３は、それぞれ１つの最良合致ブロックを識別することを示している。しかし実際には、探索領域は任意数の最良合致ブロックを識別することができ、または全く識別しなくてもよいことが理解されよう。したがって本発明は、本発明に対応する探索領域内に含まれる最良合致ブロックの数に限定されるものではない。
【００５５】
先に説明したように、「最良合致」ブロックは、例えばＳＡＤ、ＳＳＤ、ＳＡＴＤ、または他の合致誤差のようなブロック合致誤差を最小化するブロックとして選択することができる。実施形態によっては、ＭＥＵ１１０は、１以上の誤差範囲を満たす（範囲内にある）最良合致ブロックを選択するように構成することができる。実施形態によっては、最良合致ブロックを選択する誤差範囲は、ＭＥＵ１１０の外部においてプログラムされており、および／またはＭＥＵ１１０が通信取得するように構成することができる。
【００５６】
図７は、本発明の実施形態に対応するシステム１００のようなビデオ符号化システムに含まれる動き推定部（ＭＥＵ）１１０のブロック図を示す。図６に見られるように、実施形態によっては、ＭＥＵ１１０は、ビデオ信号（例えば信号Ｉ）を受信し、現在フレーム（例えば現在フレーム５０４）と空間的に整列され得る１以上のフレーム（例えば参照フレーム５０２）を抽出するように連結された遅延部（ＤＵ）７０４を備えることができる。ＭＥＵ１１０は、現在フレーム５０４および参照フレーム５０２を（ＤＵ７０４から）受信するように連結された適応動き推定探索部（ＡＭＳＵ）７０２を備えることができる。ＡＭＳＵ７０２はさらに、適応探索手法を実装し、全探索動きベクトルとブロック合致誤差（それぞれ６０７、６０９）、ならびに適応探索動きベクトルとブロック合致誤差（それぞれ６０５、６１１）を識別するように構成することができる。
【００５７】
ＭＥＵ１１０はさらに、信号（Ｉ）を受信するように連結され、信号Ｉに含まれる１以上のフレームについてブロックベースの格子構造マップ（または格子周期マップ）７１２を生成するように構成された格子構造検知部（ＬＳＤＵ）７０６を備えることができる。図７に示すように、ＡＭＳＵ７０２は格子構造マップ７１２をＬＳＤＵ７０６から受け取ることができる。
【００５８】
ＭＥＵ１１０はさらに、格子構造マップ７１２（ＬＳＤＵ７０６から）と全探索動きベクトル６０７（ＡＭＳＵ７０２から）を受け取るように連結された動きヒストグラム生成部（ＭＨＧＵ）７０８を備えることができる。ＭＨＧＵ７０８は、動きオフセットパラメータ７１４（例えば、オフセット値ＯｈとＯｖ）を生成するように構成することができる。
【００５９】
図７に示すように、ＭＥＵ１１０はさらに、動きベクトル（６０７と６０５）、ブロック合致誤差（６０９と６１１）、および格子構造マップ７１２を受け取るように連結された動きベクトル選択部（ＭＶＳＵ）７１０を備えることができる。ＭＶＳＵ７１０は、最良合致ブロックを表す最終動きベクトル７１６を選択するように構成することができる。
【００６０】
初期化またはシーン変更において、ＡＭＳＵ７０２は現在フレーム５０４と参照フレーム５０２を受信し、ＡＭＳＵ７０２は全網羅的探索を実施して、全探索動きベクトル６０７および対応するブロック合致誤差６０９を識別することができる。同時に、ＭＨＧＵ７０８はＬＳＤＵ７０６から格子構造マップ７１２を受け取り、これにより、動きベクトル６０７を表す２次元ＭＶＨ７１１を生成することができる。ＭＨＧＵ７０８によって生成されるＭＶＨ７１１については、図１０で詳しく説明する。
【００６１】
実施形態によっては、現在フレーム５０４の最終ブロックがＡＭＳＵ７０２によって処理されるまでに、ＭＨＧＵ７０８内のＭＶＨ７１１は、現在フレーム５０４全体について動き情報（格子構造マップ７１２によって分類される）を収集する。ＭＨＧＵはさらにＭＶＨ７１１を処理し、格子構造マップ７１２内の各入手可能な周期値について動きオフセットパラメータ７１４を計算する。ＡＭＳＵ７０２はさらに、動きオフセットパラメータ７１４と格子構造マップ７１２を受け取り、これにより、適応探索領域６０３の範囲（例えば、ｍ、ｎ、Ｏｈ、Ｏｖ）を構成することができる。
【００６２】
ブロックがＡＭＳＵ７０２内の動き推定を経ると、全探索領域５０３は、全探索領域６０３に含まれる全ての動き変位について、ブロック合致誤差６０９および対応する動きベクトル６０７を計算することができる。また、適応探索領域６０３は、適応探索領域６０３に含まれる全ての動き変位について、ブロック合致誤差６１１および対応する動きベクトル６０５を計算することができる。動きベクトル（６０７と６０５）およびブロック合致誤差（６０９と６１１）をさらに、動きベクトル選択部（ＭＶＳＵ）７１０に送信することができる。動きベクトル選択部（ＭＶＳＵ）７１０は、格子構造マップ７１２に基づいてブロック合致誤差（６０９と６１１）を比較し、最終動きベクトル７１６間で選択する。本発明の実施形態に対応するＭＶＳＵ７１０については、図１１で詳しく説明する。
【００６３】
実施形態によっては、後向きおよび前向き動きベクトルは、２つのフレーム（５０２と５０４）を交換することによって取得できる。図８は、本発明の実施形態に対応するＡＭＳＵ７０２のブロック図を示す。図８に見られるように、ＡＭＳＵ７０２は、現在フレーム５０４と参照フレーム５０２を受け取るように連結されたブロックマッチング部（ＢＭＵ）８０２を備えることができる。ＢＭＵ８０２は、全探索領域５０３内の全ての変位（ｄｘ，ｄｙ）８１４について１以上のブロック合致誤差判定基準（例えばＳＡＤ）を評価することにより、ブロック合致誤差８２０を生成するように構成することができる。ＡＭＳＵ７０２はさらに、変位８１４を生成する動きベクトル走査部（ＭＳＣＵ）８０４を備えることができる。実施形態によっては、ＭＳＣＵ８０４は、位置（−Ｍ／２，−Ｎ／２）から開始し（Ｍ／２，Ｎ／２）で終了する変位８１４を、ラスター走査手法によって生成することができる。
【００６４】
図８に示すように、ＡＭＳＵ７０２はさらに、変位８１４とブロック合致誤差８２０を受け取るように連結された、全探索評価部（ＦＳＥＵ）８１２および適応探索評価部（ＡＳＥＵ）８１０を備えることができる。実施形態によっては、ブロック合致誤差８２０は、対応する変位とともにＦＳＥＵ８１２およびＡＳＥＵ８１０に順次送信される。ＦＳＥＵ８１２は、全探索領域５０３について大域最小ブロック合致誤差を評価し、対応するブロック合致誤差６０９とともに最良合致動きベクトル６０７を生成するように構成することができる。
【００６５】
ＡＭＳＵ７０２はさらに、格子構造マップ７１２および動きパラメータ７１４を受け取るように連結され、適応探索領域６０３の範囲８１６（例えばｍ、ｎ）を計算するように構成された探索領域計算部（ＳＡＣＵ）８０６を備えることができる。図８に示すように、ＡＭＳＵ７０２はさらに、変位８１４と範囲８１６を受け取るように連結され、現在フレーム５０４の全探索ブロックマッチングの間に８１４内の各（ｄｘ，ｄｙ）変位を比較して変位（ｄｘ，ｄｙ）が適応探索領域６０３内に含まれるか否かを識別するように構成された比較部（ＣＵ）８０８を備えることができる。実施形態によっては、ＣＵ８０８は、（ｄｘ，ｄｙ）変位が適応探索６０３領域内に含まれるか否かを、バイナリ信号８１８によって示すことができる。
【００６６】
図８に示すように、ＡＳＥＵ８１０はさらに、信号８１８を受信し、適応探索領域６０３内に含まれる全ての（ｄｘ，ｄｙ）変位値について、対応する最良合致ベクトル６０５とともに、局所最小ブロック合致誤差６１１を計算することができる。
【００６７】
図９ａは、本発明の実施形態に対応するＬＳＤＵ７０６のブロック図を示す。図９ａに示すように、ＬＳＤＵ７０６は、フレーム５０２のようなフレームを受け取るように連結され、フレーム５０２内のピクセルに対してウインドウベースサンプリングを実装してピクセルサンプル９１２を取得するように構成されたサンプリングウインドウ部（ＳＷＵ）９０２を備えることができる。実施形態によっては、ＳＷＵ９０２は、正規化１次元サンプリングウインドウを備えることができる。サンプリングウインドウのサイズは、検知し得るピッチ周期範囲に依拠する。実施形態によっては、［２〜Ｎ］の周期範囲について、少なくとも２Ｎピクセルのサンプリングウインドウサイズが用いられる。実施形態によっては、ＳＷＵ９０２は、全てのサンプリングされたピクセルの平均値を計算し、その平均値を各ピクセルサンプルから減算することにより、（フレーム５０２の）ピクセルサンプル９１２を、ゼロ値平均に正規化することができる。
【００６８】
図９ａに示すように、ＬＳＤＵ７０６はさらに、ピクセルサンプル９１２を受け取るように連結され、重み付けされたピクセルサンプル９１４を取得するための重み付け機能を実装するように構成された重み付け部（ＷＵ）９０４を備えることができる。ＷＵ９０４によって実装される重み付け機能は、サンプリングウインドウの中心周辺のピクセルサンプルをより強調し、サンプリングウインドウの終端近傍のサンプルを弱めることができる。実施形態によっては、ＷＵ９０４は、ピクセルサンプル９１２にハミング窓変調（または重み付け）を実装し、重み付けされたサンプル９１４を取得することができる。実施形態によっては、ハミング窓を使用することにより、１の隣接ブロックから次のブロックへ向けたより一貫性のある周期検出を提供することができる。
【００６９】
ＬＳＤＵ７０６はさらに、重み付けされたサンプル９１４を受け取るように連結され、フーリエ変換を実施して変換係数９１６を取得するように構成された高速フーリエ変換部（ＦＦＴ）９０６を備えることができる。実施形態によっては、係数９１６は係数の振幅成分のみを含むこともできる。
【００７０】
図９ａに示すように、ＬＳＤＵ７０６はまた、係数９１６を受け取るように連結され、係数９１６の振幅スペクトルに対してピーク検出手法を実装し、最も強い周波数振幅ピークを検出するように構成された、ピークおよび周期計算部（ＰＰＣＵ）９０８を備えることができる。ＰＰＣＵ９０８はさらに、最良ピーク周波数値を選択し、その最良ピーク周波数値をピッチ周期マップ９１８に変換することができる。ＬＳＤＵ７０６はさらに、ピッチ周期マップ９１８を受け取るように連結され、周期マップ９１８をフィルタリングすることによって格子構造マップ７１２（または格子構造周期マップ）７１２を生成するように構成されたフィルタ周期部（ＦＰＵ）９１０を備えることができる。周期マップ９１８をフィルタリングすることにより、ＦＰＵ９１０はさらに一貫性（滑らかさ）を改善し、周期マップ９１８内の検出された周期の隔絶したまたは誤った検出結果を除去することができる。
【００７１】
図９ｂは、フレーム５０２内に含まれる格子構造９３０の例を示す。円で囲った領域９３２は、水平ピッチ周期値（Ｔｈ）を示す、フレーム５０２の水平成分を示す。水平ピッチ周期Ｔｈのようなピッチ周期に関する情報は、格子構造マップ７１２内に含まれている。
【００７２】
実施形態によっては、ウインドウ化信号自動相関のような他手法を、ウインドウ化周波数変換に代えて用い、ブロック毎に格子構造の周期値を検出することができる。実施形態によっては、入力フレームの異なる解像度に対して格子構造を階層的に検出することもできる。階層的検知手法を用いることにより、様々な画像のダウンサンプリング段階を通して、より広い範囲のピッチ周期を検出することができる。例えば、画像が２分の１にダウンサイズされると、周期は２分の１に小さくなり、等価な周期検出範囲は２倍に大きくなる。
【００７３】
図７を用いて先に説明したように、ＭＨＧＵ７０８は、ＡＭＳＵ７０２が使用する動きオフセットパラメータ７１４を計算するために用いる動きベクトルヒストグラム（ＭＶＨ）７１１を生成することができる。図１０は、ＭＨＧＵ７０８が生成するヒストグラムＭＶＨ７１１の例を示す。
【００７４】
図１０に見られるように、ＭＶＨ７１１は、例示するヒストグラムビン１００４のようなヒストグラムビンを備えることができる。水平軸（ＭＶｈ）は、全ての可能な水平動き値［−Ｎ／２〜Ｎ／２］を表し、垂直軸（Ｔｈ）は、全ての可能な被検出水平ピッチ周期値［２〜Ｎ］を表すことができる。図１０におけるヒストグラムＭＶＨの例は、ピクセルブロック内の被検出ピッチ周期４と他のピクセルブロック内の被検出ピッチ周期５を含む格子構造を有するフレームを示す。さらに、図１０に示すように、周期値４および５双方について、ほとんどの発生動きベクトルはＭＶ０（それぞれ７５回、９０回発生している）である。図１０に示すように、ピッチ周期４について、ＭＶ０とＭＶ＋４は、正確に互いから１ピッチ周期離れており、これはＭＶ＋４があるフレームの特定ブロックにおいて誤ってマッチングされる可能性を示す。
【００７５】
先に説明したように、ＭＨＧＵ７０８は、ＭＶＨ７１１を解析して動きオフセット値７１４を生成することができる。実施形態によっては、ＭＨＧＵ７０８はＭＶＨ７１１をフィルタリングし、格子構造マップ７１２内の各周期について最適動作を判定することができる。例えば、図１０に示すＭＶＨ７１１を参照すると、周期４または５の周期格子構造に属するブロックは、水平オフセットＯｈが０にセットされ、幅ｎが式（３）を用いて説明した値にセットされるように構成された適応探索領域６０３を有し得ることが分かる。
【００７６】
実施形態によっては、全てのヒストグラムビン（例えば例示するビン１００４）は、各新フレームが入ってくる毎にリセットすることができる。先に説明したように、実施形態によっては、ＭＨＧＵ７０８は、各フレームについて２つのヒストグラムを生成することができる。その１つは水平動きベクトル成分および水平周期であり、もう１つは垂直動きベクトル成分および垂直周期である。
【００７７】
図１１は、本発明の実施形態に対応する動きベクトル選択部（ＭＶＳＵ）７１０のブロック図を示す。図１１に示すように、ＭＶＳＵ７１０は、全探索動きベクトルおよび適応探索動きベクトル（６０７と６０５）ならびに格子構造マップ７１２を受け取るように連結された動きベクトル比較部（ＭＶＣＵ）１１０２を備えることができる。ＭＶＣＵ１１０２はさらに、各ブロックについて動きベクトル（６０７と６０５）間の絶対差分を比較するように構成することができる。所与のブロックについてのベクトル（６０７と６０５）間の絶対差分が０でなく、複数のピッチ周期値（格子マップ７１２から）である場合、実施形態によっては、ＭＶＣＵ１１０２は、現在ブロック位置における入力フレーム内の格子構造の存在を示す検証信号１１１０を生成することができる。実施形態によっては、検証信号１１１０はバイナリ信号である。
【００７８】
ＭＶＳＵ７１０はさらに、検証信号１１１０を受け取るように連結され、パラメータ（１１１２と１１１４）を選択するように構成されたマルチプレクサ１１０６を備えることができる。検証信号１１１０に基づき、マルチプレクサ１１０６は、係数とオフセット値を含むペナルティーパラメータ１１１６を送信することができる。図１１に示すように、ＭＶＳＵ７１０は、マッチング誤差（６０９と６１１）とペナルティーパラメータ１１１６を受け取るように連結されたマッチング誤差計算部（ＭＥＣＵ）１１０４を備えることができる。ＭＥＣＵ１１０４はさらに、選択信号１１１８を生成するように構成することができる。実施形態によっては、ペナルティーパラメータ１１１６は、ＭＥＣＵ１１０４が対応する全探索マッチング誤差６０９にペナルティーを課し、対応する適応探索動きベクトル６０５をより選択に適するようにするために用いることができる。例えば、格子構造が存在する場合、マルチプレクサ１１０６は、検証信号１１１０を介して、ペナルティーパラメータ１１１６を送信するように構成することができる。このペナルティーパラメータ１１１６により、ＭＥＣＵ１１０４は、適応探索動きベクトル６０５をより選択されやすくする（選択信号１１１８とマルチプレクサ１１０８を介して）ことができる。これは、全探索マッチング誤差６０９に大きなペナルティーが適用されるからである。周期格子構造が存在しない場合、マルチプレクサ１１０６を検証信号１１１０によって構成し、ＭＥＣＵ１１０４がより小さいペナルティーを全探索マッチング誤差６０９に適用してブロックマッチング誤差（６０９と６１１）が類似しているときに適応探索ベクトル６０５が選択され得る（選択信号１１１８とマルチプレクサ１１０８を介して）ように、ペナルティー係数１１１６を生成することができる。実施形態によっては、大域最小値により、ペナルティーを課されない全探索マッチング誤差６０９は、適応探索マッチング誤差６１１以下となり得る。
【００７９】
実施形態によっては、選択信号１１１８は、バイナリ信号であってもよい。選択信号１１１８に基づき、マルチプレクサ１１０８は、最終動きベクトル７１６を、全探索動きベクトルと適応探索動きベクトル（６０７と６０５）の間で選択することができる。
【００８０】
他の実施形態は、当業者にとって、ここに開示する明細書と実施例の検討から明らかである。明細書と実施例は、例示目的のみを意図しており、本発明の真の範囲と趣旨は特許請求の範囲によって示される。
【技術分野】
【０００１】
関連出願
本出願は、２００７年１２月２０日に出願された、米国仮出願第６１／０１５，２２６号に基づく優先権を主張し、その内容は、参照によって、その全体が本願に組み込まれる。
【０００２】
本発明は、全体的にはビデオと画像の符号化の分野に関し、より具体的には、動き推定と補償のための方法およびシステムに関する。
【背景技術】
【０００３】
伝送ネットワーク、デジタル記憶媒体、超大規模集積デバイス、および映像音声信号のデジタル処理における技術的進歩により、広範な応用分野において、デジタルビデオが安価に伝送され、蓄積されるようになってきている。デジタルビデオ信号の蓄積と伝送は多くのアプリケーションの中心となっているので、デジタルビデオ符号化技術の使用は一般的になっている。
【０００４】
視覚情報は、生活のほぼ全ての領域において重要な役割を果たしている。画像とビデオに関連する膨大なデータ量に起因して、ビデオ符号化は重要な技術となっている。動き推定および補償は、様々なビデオ符号化手法において重要な役割を果たす。動き補償は、例えば、圧縮、ノイズ除去、走査変換、フレーム／フィールドレート変換のための画像補間のような様々なビデオアプリケーションにおいて用いることができる。
【０００５】
しかし、モバイル通信とインターネットが猛烈なスピードで発展するのにともない、現在の動き推定および補償の手法では、これまで増加してきた、インターネットや携帯テレビ電話を介したビデオストリーミングのようなアプリケーションの需要についていくことができなくなっている。
【０００６】
したがって、ビデオ符号化と補償の手法におけるより効率的な動き推定および補償が必要となっている。
【発明の概要】
【課題を解決するための手段】
【０００７】
本発明の実施形態に対応する、第１フレーム内のピクセルブロックの動きを推定する方法は、第２フレーム内の第１領域を探索して、ピクセルブロックに対応する第１合致ブロックであって、ピクセルブロックと第１合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第１誤差値を含む第１合致ブロックを識別するステップと、第１合致ブロックに関連する第１動きベクトルを計算するステップと、を有する。
【０００８】
本発明に係る方法はさらに、第２フレーム内の第２領域を探索して、ピクセルブロックに対応する第２合致ブロックであって、ピクセルブロックと第２合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第２誤差値を含む第２合致ブロックを識別するステップと、第２合致ブロックに関連する第２動きベクトルを計算するステップと、第１誤差値および第２誤差値に基づき第１動きベクトルと第２動きベクトルの間で最終動きベクトルを選択するステップと、を有する。
【０００９】
本発明のさらなる特徴と利点は、一部は以下の記載において説明され、一部はその記載から明らかであり、または本発明を実施することによって取得されるであろう。本発明の特徴と利点は、特許請求の範囲において特に指摘される要素と組合せの手段によって実現され、達成される。
【００１０】
添付する図面は、本明細書に組み込まれてその一部をなし、本発明の実施形態を示し、明細書の記載とともに本発明の原理を説明するのに役立つ。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態に対応するビデオ符号化システムのブロック図を示す。
【図２ａ】本発明の実施形態に対応するビデオフレーム例を示す。
【図２ｂ】本発明の実施形態に対応するビデオフレーム例を示す。
【図３】本発明の実施形態に対応する動画像例を示す。
【図４ａ】本発明の実施形態に対応するビデオフレームの他例を示す。
【図４ｂ】本発明の実施形態に対応するビデオフレームの他例を示す。
【図５】本発明の実施形態に対応する動き推定方法の概略図である。
【図６】本発明の実施形態に対応する他の動き推定方法の概略図である。
【図７】本発明の実施形態に対応する動き推定装置のハイレベルブロック図である。
【図８】本発明の実施形態に対応する他の動き推定装置のブロック図である。
【図９ａ】本発明の実施形態に対応する他の動き推定装置のブロック図である。
【図９ｂ】本発明の実施形態に対応する格子構造の概略図である。
【図１０】本発明の実施形態に対応する動きベクトルヒストグラムの概略図である。
【図１１】本発明の実施形態に対応する動き推定装置のブロック図である。
【発明を実施するための形態】
【００１２】
本発明の実施形態について、図面を詳細に参照する。実施形態の例は、添付する図面に記載されている。できる限り、同じまたは同様の部分については、図面全体を通して、同じ参照符号を用いる。
【００１３】
以下の説明および特許請求の範囲において、「連結」および「接続」という用語が、その派生語とともに用いられる場合がある。これら用語は、互いの同義語として意図されているのではないことが理解されるであろう。むしろ、特定の実施形態においては、「接続」および／または「連結」は、２以上の要素が互いに直接物理的にまたは電気的に接触していることを示す。しかし、「連結」はまた、２以上の要素が互いに直接接触してはいないが、互いに協調し、通信し、および／または相互作用することも意味する。
【００１４】
図１は、本発明の実施形態に対応するビデオ符号化システム１００のハイレベル機能ブロック図を示す。以下の説明および特許請求の範囲における様々な機能部が、実際には、個別にまたは組み合わせて、ハードウェア内、１以上のハードウェア部品（例えば、１以上のプロセッサ、１以上の特定用途向け集積回路（ＡＳＩＣｓ）、またはその他の同様部品）上で実行されるソフトウェア内、またはこれらの組み合わせにおいて実装し得ることが理解されよう。
【００１５】
図１に示すように、システム１００は、カメラ１０２からビデオ信号（Ｉ）を受け取るように連結され、信号ＩをエンコードしてビットストリームＢを得るように構成されたたエンコーダ部１０４を備えることができる。用途によっては、ビットストリームＢは、メモリ内に蓄積し、および／または通信チャンネルを介して伝送することができる。図１に示すように、システム１００はさらに、ビットストリームＢを受け取るように連結され、信号ＩをビットストリームＢから再構築するように構成されたデコーダ部１０６を備えることができる。システム１００はまた、デコーダ１０６に連結され、再構築された信号Ｉを表示するように構成されたディスプレイ１０８（例えば、モニタ、スクリーン、または同様なディスプレイデバイス）を備えることができる。先に説明したように、動き推定はビデオ符号化において重要な役割を果たし得るので、システム１００は動き推定部（ＭＥＵ）１１０を備えることができる。実施形態によっては、例示するＭＥＵ１１０のような動き推定部は、デコーダ１０６内に設けることができる。実施形態によっては、ＭＥＵ１１０は、例示するデコーダ１０６のようなデコーダ内に設けられた動き補償画像補間部（ＭＣＩＩＵ）１１１の一部として設けることができる。ＭＣＩＩＵ１１１は、ビデオの欠損したフレームを復元（再構築）する画像補間を実施するように構成することができる。本発明の実施形態に対応する動き推定部の詳細は、図７において詳しく説明する。
【００１６】
自然の視覚シーンは、空間的にも時間的にも連続している。典型的には、視覚シーンは、実シーンを空間的（通常は画像平面上の長方形格子）および時間的（定期的な時間間隔でサンプリングした一連の静止画像（フレーム）として）にサンプリングすることにより、デジタル形式で表すことができる。図１に示すように、カメラ１０２からの信号Ｉは、視覚シーンを１以上の静止画像（フレーム）（Ｉ１，Ｉ２，・・・，Ｉｎ−１，Ｉｎ）として表すことができる。
【００１７】
図２ａは、カメラ１０２のようなキャプチャ装置でキャプチャされた例示的な自然シーンからの静止画像２００の例を示す。画像２００は、背景に丘（２１２、２１４、２１６）と木（２０６、２０８、２１０）がある道路２０４上を走行している車２０２を示す。画像２００は、図２ｂに示すように、Ｐ×Ｑの長方形格子Ｒ上にサンプリングすることにより、デジタル形式で表すことができる。長方形格子Ｒ上の各点Ｒ（ｐ，ｑ）（０≦ｐ≦Ｐ−１、０≦ｑ≦Ｑ−１）は、画像要素（ピクセル）に対応させることができる。各ピクセルは、明るさ（輝度）および／または色を表す数値または数値セットによって表すことができる。デジタルアプリケーションにおいて、ピクセルは１以上のバイナリ値として表すことができ、各フレームは対応するピクセル値の配列（または行列）として表すことができる。アプリケーションの種類に基づき、フレーム内のピクセルの数（Ｐ×Ｑ）が異なることが理解されよう。したがって本開示は、本発明に対応するフレーム内に含まれるピクセル数を限定するものではない。
【００１８】
典型的には、例示する画像２００のような静止画は、画像２００の２次元投影をセンサ（例えば電荷結合素子のアレイ（ＣＣＤアレイ））上にフォーカスすることにより、キャプチャ装置（例えばカメラ１０２）を用いて２次元サンプリングされた画像として得られる。ピクセル配列（ピクセル値の配列）は、ＣＣＤアレイの出力から得られる。場合によっては、カラー画像について、ＣＣＤアレイの出力を１以上の色成分にフィルタリングし得る。各色成分は、対応するピクセル配列を有する。例えば、ＲＧＢ（赤、緑、青）色モデルにおけるカラー画像は、各色成分について１以上のピクセル配列を有し得る。
【００１９】
先に説明したように、自然シーンは（Ｉ１，Ｉ２，・・・，Ｉｎ−１，Ｉｎ）のような一連のフレームとして表すことができる。これらフレームは、一連の完全フレームおよび／または一連のインタレースフレームとしてサンプリングすることができる。本開示の実施形態は、上記種類のフレーム（プログレッシブまたはインタレース）を使用することに制約されず、また限定されないことが理解されよう。
【００２０】
図３は、道路２０４を走行する車２０２（図１ａと１ｂに示した）の動画像３００の例を示す。ビデオ３００は、周期的時間間隔における例示フレーム３０２、３０４、３０６、３０８のような一連のフレームによってキャプチャすることができる。一連のフレームを再生することにより、車２０２が動いているように見せることができる。便宜上図３は、ビデオ３００が４フレーム（３０２、３０４、３０６、３０８）を含むものとして示した。しかし実際には、例示するビデオ３００のような所与のビデオ内に含まれる、任意数（ｎ）のフレームが存在し得ることが理解されよう。したがって本開示は、本発明に対応するシステムに含まれ、サポートされるフレーム数に限定されない。
【００２１】
ビデオ３００の各フレームは、図２ａと２ｂについて説明したものと同様の手法によりデジタル形式で表すことができる。したがって、ビデオ３００内の各フレームは、複数のビットによって表すことができる。典型的には、フレームレートが高くなると（１時刻単位毎に取得されるフレーム数）、動きは滑らかになり、ビデオ３００の品質は全体的に良くなる。しかし、フレームレートを増やすと、例示するビデオ３００のようなビデオ画像を表すために必要なビット数も増える。
【００２２】
ほとんどのビデオアプリケーションの記憶容量と帯域は限られているので、様々な符号化手法（および／または圧縮）をエンコーダ部（例えば、例示するエンコーダ部１０４）によって実装し、所与のビデオを表すために必要なビット数とビデオ品質の間のバランスを取ることができる。
【００２３】
典型的には、ほとんどのビデオ符号化手法は、シーン内の冗長情報を時間的にも空間的にも利用し、圧縮を実現する。時間ドメインでは、時間的に隣接するフレーム間、すなわち時間順で連続するフレーム間には、特に高フレームレートにおいて高い相関（類似性）がある。空間ドメインでは、互いに近接するピクセル間、すなわち隣接するピクセル間に高い相関がある。図３に見られるように、フレーム３０２、３０４、３０６、３０８において、丘（２１２、２１４、２１６）、木（２０６、２０８、２１０）、道路２０４に関するピクセルは、全てのフレーム（３０２、３０４、３０６、３０８）内で一定（冗長）である。したがって、各フレーム内の冗長な情報を表す必要性をなくすことにより、ビデオ３００を表すために必要な全体的ビット数を抑えることができる。これは、１以上のフレーム内の共通するピクセルを識別することによってなされる。
【００２４】
しかし、ピクセル毎にフレームを処理することは、計算が複雑である。場合によっては、計算の複雑さを低減し、さらに圧縮率を改善するため、フレームを複数の領域（特にブロック）に再分割し、ブロック毎に処理することもできる。典型的には、領域（ブロック）は複数の隣接ピクセルを含み、サイズがそれぞれ異なっていてもよい。アプリケーションの種類によっては、ブロックは互いに重なり合っていてもよい。
【００２５】
図４ａは、それぞれ１６×１６ピクセルを含む５×５固定サイズブロック（例えば、例示するピクセルブロック４０２）によって分割された例示フレーム３０２を示す。便宜上図４ａは、フレーム３０２が５×５ピクセルブロックを有するものとして示している。しかし実際には、所与のフレームは任意数の（Ｕ＜Ｐ、Ｖ＜Ｑ）の（Ｕ×Ｖ）ピクセルブロックを含み、各ピクセルブロックは任意数のピクセルを含み得ることが理解されよう。したがって本発明は、本発明に対応するフレーム内に含まれるピクセルブロックの数および／またはサイズに限定されるものではない。
【００２６】
場合によっては、ビデオ品質をさらに向上させるため、フレームを可変ブロックサイズに分割することもできる。図４ｂは、可変サイズブロック（例えば、例示するピクセルブロック４０２、４０４、４０６）に分割された例示フレーム３０２を示す。便宜上図４ｂは、フレーム３０２が異なるブロックサイズのピクセルブロック４０２、４０４、４０６を含むものとして示している。しかし実際には、所与のフレームは任意数の（Ｕ×Ｖ）ピクセルブロックを含み、各ピクセルブロックはさらに任意数の（ｕ×ｖ）ピクセルブロック（ｕ＜Ｕ、ｖ＜Ｖ）に分割し得ることが理解されよう。したがって本発明は、本発明に対応するフレーム内に含まれるピクセルブロックの数および／またはサイズに限定されない。
【００２７】
典型的には、ビデオフレーム間の変更は、物体の動き（例えば移動中の車）、カメラの動き（例えばパン、傾斜、ズーム、回転など）、覆いが外された領域（例えば移動中の車によって覆われたシーン背景部分）、光の変更によってもたらされる。光の変更は例外だが、動きは典型的にはフレーム間のピクセル移動に関わる。したがって、連続フレーム間の各ピクセルの軌跡を予測することにより（動き推定）、各ピクセルを参照フレーム（過去のまたは未来のフレーム）内で移動させて（関連する軌跡に基づき）現在のフレームを正確に再構築することができる（動き補償）。１以上のフレームは単一の参照フレームによって表すことができるので、ビデオ画像全体を表すために必要なビット数を削減することができる。
【００２８】
しかし、先に説明したように、ピクセル毎にフレームを処理するのは計算コストが高い。したがって、計算の複雑さを低減するため、実施形態によっては、動き推定部（ＭＥＵ）１１０によって様々なブロック毎の動き推定手法を実装することができる。
【００２９】
図４ａと４ｂについて先に説明したように、例示フレーム３０２のような所与のフレームは、１以上の固定および／または可変サイズピクセルブロックに分割することができる。ブロックベースの動き推定において、現在ブロックは参照フレーム内の同サイズのシフトされた他ブロックと比較される。現在ブロックとシフトされた参照ブロックが最も合致するとき、２つのブロック間の最適変位または動きを表す１以上の動きベクトル（ＭＶ）が得られる。実施形態によっては、動きベクトルは２次元であり、水平成分と垂直成分を有する。したがって現在のフレームは、変位した（移動した）ブロックを識別し、参照フレーム内の全ての対応する変位ブロックをそれぞれの動きベクトルで補償することにより、参照フレームを用いて表すことができる。
【００３０】
例えば例示ビデオ３００において、フレーム３０４は、フレーム３０４内で移動したブロックを識別し、変位したブロックに対応する動きベクトルを計算し、フレーム３０２内の変位したブロックを対応する動きベクトルで補償することによって、例えばフレーム３０２のような参照フレームを用いて表すことができる。したがって、フレーム３０４に関連する全てのピクセル値を保存することに代えて、フレーム３０４内の変位したブロックに関連するＭＶおよびフレーム３０２と３０４の間の任意の差異（例えば車２０２の移動によって覆いが外された領域）のみを保存する必要がある。
【００３１】
実施形態によっては、ＭＥＵ１１０は、参照フレームおよび１以上の現在フレーム内のブロック間の動きを推定するためのブロックマッチング手法を実装することができる。１実施形態において、ＭＥＵ１１０は、誤差判定基準（例えば絶対誤差の合計（ＳＡＤ）、２乗誤差の合計（ＳＳＤ）、絶対変換誤差の合計（ＳＡＴＤ）、または他の同様の誤差判定基準）を、現在のブロックに含まれる全てのピクセルについて用い、参照フレーム内の対応する「最も合致する」ブロックを探索するように構成することができる。典型的には、ＳＡＤ基準の計算の単純さまたはコスト機能により、これが最もよく用いられる。
【００３２】
実施形態によっては、ＭＥＵ１１０はフルサイズの網羅的な探索を実施し、探索領域（または範囲）内の全ての動きベクトルについての大域最小ブロック合致誤差（例えば、最小ＳＡＤ値）を見つけることができる。最小合致誤差を有する動きベクトルは、大多数のピクセルについての最良の動き推定を表し、これに関連するブロックを最良合致ブロックとして選択することができる。
【００３３】
図５は、本発明の実施形態に対応するＭＥＵ１１０によって実装することができるフルサイズ網羅的探索ブロック合致手法の例示図である。図５は、参照フレーム５０２と現在フレーム５０４を示す。フレーム５０２と５０４は、図３で説明したフレームと類似していてもよい。現在フレーム５０４は、図４ａと４ｂで説明したピクセルブロックに類似する例示的な現在ブロック５０６を含むことができる。図５に示すように、ブロック５０６に属する画像詳細部分の位置は、フレーム５０２から５０４へ変化する場合がある。
【００３４】
図５に示すように、全探索領域５０３は、参照フレーム５０２においてブロックマッチング処理を実施して現在ブロック５０６に関連する１以上の最良合致ブロック（および対応する動きベクトル）を識別するために用いることができる。ブロック５０６（フレーム５０４内）の空間的に整列した位置は、参照フレーム５０２内においてゼロ変位ブロック５０７によって示されている。
【００３５】
全探索領域５０３のサイズは、画像解像度（フォーマット）、フレームレート、アプリケーション種別に依拠し得る。実施形態によっては、全探索領域５０３は、水平サイズ［−Ｍ／２〜Ｍ／２］ピクセル、垂直サイズ［−Ｎ／２〜Ｎ／２］ピクセルの（Ｍ＋１×Ｎ＋１）ピクセルを含む長方形の範囲を有する。ここで、ＭとＮは偶数であり、（Ｍ＋１≦Ｐ、Ｎ＋１≦Ｑ）である。実施形態によっては、全探索領域５０３のサイズは、速度が異なる画像フォーマットにおける動きベクトル間で同様に表されることを確実にするため、画像フォーマットに比例してもよい。速度は、フレーム内の物体がフレームを一端から他端に向かって横切るために必要な時間量として定義される。例えば、ＨＤＴＶ１０８０ｐ画像シーケンスで用いられる探索領域は、類似する動きベクトルを取得するため、ＨＤＴＶ７２０ｐ画像シーケンスで用いられる探索領域よりも２２５％大きい。実施形態によっては、フレーム５０２内で、全探索領域５０３の中心をゼロ変位ブロック５０７にすることができる。
【００３６】
実施形態によっては、参照フレーム５０２内のシフト探索ブロック（ブロック５０８、５１０として２度示している）は、現在ブロック５０６と同じサイズを有し、全探索領域５０３内で発生し得る（ブロック５０６の）変位と関連するブロック合致誤差を計算するため、単位ピクセル増加によって変位させることができる。大域最小ブロック合致誤差に対応する変位は、最良合致ブロックとして識別することができる。例えば図５において、参照フレーム５０２内のブロック５０６について、ブロック５０８は「最良合致」候補として示されており、ブロック５１０は代替の「最良合致」候補として示されている。図５に示すように、ブロック５０８と５１０にそれぞれ動きベクトルＭＶ１とＭＶ２を割り当てることができる。便宜上図５では、全探索領域５０３が２つのブロック（５０８と５１０）と対応する動きベクトル（ＭＶ１とＭＶ２）のみを、現在ブロック５０６についての最良合致候補として含むように記載している。しかし実際には、全探索領域内に含まれる任意数の最良合致候補（ＭＶおよび／またはブロック）が存在し得ることが理解されよう。したがって本発明は、本発明に対応する探索領域内に含まれるＭＶの数に限定されるものではない。
【００３７】
図５で説明したように、ＭＥＵ１１０は、フルサイズ網羅的探索を実施することにより、参照フレーム５０２内の最良合致ブロック５０８と５１０を識別することができる。しかし、フルサイズ網羅的探索手法は、所与のフレーム内のブロック数が増加すると、計算コストが高くなる。さらに、フルサイズ網羅的探索手法を用いると、図５に示すように複数の最良合致ブロックが得られる場合がある。動き補償および／または画像補間のときに最良合致ブロックが誤っていると、多大な不具合が生じる。マッチング誤差を起こす画像特徴には、多くの種類がある。例えば、直線形状の場合、当該形状に平行な任意長の動きベクトルが、フルサイズ探索から得られる場合がある。そして、直線形状に関連するその動きベクトルがランダムに選択され、当該形状近傍の他のピクセルを補間するときに誤差を引き起こす場合がある。
【００３８】
例えば図５において、フレーム５０２内のＭＶ２（ブロック５１０に関連付けられている）が、現在ブロック５０６に関連する真の動きベクトルであると仮定する。合致ブロック５０８と５１０はともに同程度の低い合致誤差値を持つので、ＭＥＵ１１０はブロック５０６についての最良合致としてブロック５０８を誤って選択する可能性がある。このような誤ったブロック合致は、ビデオ品質を劣化させる。
【００３９】
動きベクトルは画像補間に用いることができるので、画像シーケンス内の物体の真の動きと詳細部分を正確に表すことにより、画像オブジェクトとその詳細部分が適正に補間された空間上の位置に変位することを確実にし、補間後画像内に不具合が存在することを回避できる。
【００４０】
画像は、格子構造または周期構造とも呼ばれる様々な繰り返し構造を含む場合があるので、これら格子構造を識別すると、真の動きの表現を改善することに役立つ。実施形態によっては、ＭＥＵ１１０は、画像内の様々な格子構造を識別する１以上の格子構造マップ（または格子構造周期マップ）を生成する格子構造検知手法を実装することができる。格子構造周期マップは、水平動きベクトル成分を分類する水平ピッチ周期値と、垂直動きベクトル成分を分類する垂直ピッチ周期値を含む。ピッチ周期は、格子構造の最小繰り返し単位として定義することができる。
【００４１】
ＭＥＵ１１０によって実装することができる格子構造検知手法については、図９ａと９ｂを用いて詳細に説明する。
【００４２】
格子構造は、建物、窓、焼き網、フェンス、テキストなどの物体内に顕著に存在する。網羅的全探索手法（図５で説明した）において、ＭＥＵ１１０は、全探索領域（例えば探索領域５０３）内において、同程度の低ブロック合致誤差を有する複数の最良合致動きベクトル（図５に示した）を識別することができる。例えば、格子構造が１０ピクセルの水平ピッチ周期（格子構造の最小繰り返し単位）を有し、真の水平動作が＋３ピクセルである場合、ＭＥＵ１１０は、最良合致候補として、−７ピクセル（３−１０）または＋１３ピクセル（３＋１０）の水平動作を見つける可能性がある。真の動きベクトルに対応する１つの局所最小合致誤差が存在する可能性があるが、場合によっては、シーンの光の変化、カメラのパン動作、または同様の潜在的な光イフェクトのような影響により、大域最小合致誤差が１以上の識別された最良合致候補に関連付けられる可能性がある。探索領域（例えば全探索領域５０３）のサイズを削減することにより、局所最小値の数を少なくすることができる。これにより、大域最小値が真の動きベクトルに関連付けられる可能性が高まる。しかし、全探索領域５０３が小さいと、限られた範囲の物体変位のみが適正に推定され、総合的な動き推定結果について妥協することになる。したがって、動き推定に関して妥協することなく誤ったブロック合致が生じないようにするため、実施形態によっては、ＭＥＵ１１０は、適応探索手法を実装して最良合致ブロック（および動きベクトル）を見つけることができる。
【００４３】
図６は、本発明の実施形態に対応するＭＥＵ１１０によって実装することができる適応探索手法の概略図である。図６は、参照フレーム５０２と現在フレーム５０４を示す。図５で説明した手法と同様に、ブロック５０６の位置はフレーム５０２から５０４に向かって変化する。
【００４４】
図６に示すように、全探索領域５０３に加えて、参照フレーム５０２内で適応探索領域６０３を用いて、ブロックマッチング処理を実施し、現在ブロック５０６に関連する１以上の最良合致ブロックを識別（および動きベクトルを推定）することができる。実施形態によっては、全探索領域５０３と適応探索領域６０３の中心をゼロ変位ブロック５０７にすることができる。
【００４５】
実施形態によっては、全探索ブロックマッチングを全探索領域５０３内で実施し、ブロック合致誤差のサブセットを、適応探索領域６０３に含まれる（範囲にある）全ての変位について収集することができる。最良合致ブロックの位置に対応する局所最小誤差を見つけるため、ブロック合致誤差（領域５０３内と６０３内で計算される）が比較される。例えば図６は、対応する動きベクトルとしての動きベクトル６０５とともに、最良合致ブロックとしてブロック５１０（適応探索領域６０３内に含まれる）を示す。先に説明したように、全探索領域５０３と適応探索領域６０３は、複数の最良合致ブロックと対応する動きベクトルを含むことができる。便宜上以下の説明は、全探索領域５０３内に含まれる全ての最良合致ＭＶと対応するブロック合致誤差を、それぞれ最良合致ベクトル６０７、ブロック合致誤差６０９として、まとめて参照する。同様に以下の説明は、適応探索領域６０３内に含まれる全ての最良合致ＭＶと対応するブロック合致誤差を、それぞれ最良合致ベクトル６０５、ブロック合致誤差６１１として、まとめて参照する。
【００４６】
実施形態によっては、全探索領域５０３のサイズは固定かつ長方形であってもよく（図５で説明したものと同様に）、一方で適応探索領域６０３は範囲が可変であり、かつ予測動き値によって（ゼロ変位ブロック５０７の中心から）オフセットしてもよい。
【００４７】
実施形態によっては、適応探索領域６０３は、水平サイズ［−Ｍ／２〜Ｍ／２］ピクセル、垂直サイズ［−Ｎ／２〜Ｎ／２］ピクセルの（Ｍ＋１×Ｎ＋１）ピクセルを含む長方形の範囲を有する。ここで、ｍとｎは偶数であり、（ｍ＜Ｍ、ｎ＜Ｎ）である。実施形態によっては、適応探索領域６０３は、動きオフセット値オフセット（Ｏｈ、Ｏｖ）ピクセルを有し、ＯｈとＯｖは、全探索領域５０３中心から見た適応探索領域６０３中心の対応する水平軸オフセットと垂直軸オフセットである。実施形態によっては、ｍ、ｎ、Ｏｖ、Ｏｈは、格子構造マップと動きベクトルヒストグラム（ＭＶＨ）から取得することができる。
【００４８】
ＭＶＨは、水平軸上の全ての水平動き値（ＭＶｈ）［−Ｎ／２〜Ｎ／２］、および垂直軸上の全ての垂直ピッチ周期値（Ｔｈ）［２〜Ｎ］を表す２次元ヒストグラム配列であってもよい。実施形態によっては、ＭＶＨは、各ヒストグラムビンが画像ピクセルに類似しているという意味において、小画像に類似している。実施形態によっては、２つのヒストグラムを各フレームから生成することができる。そのうち１つは水平動きベクトル成分および水平周期について、もう１つは垂直動きベクトル成分および垂直周期についてである。ＭＥＵ１１０が用いることができるＭＶＨを、図１０に詳細に示した。
【００４９】
格子構造内では典型的に、２つの良好な候補ベクトル成分間の距離は、複数のピッチ周期値である。式（１）は、ピッチ周期値（Ｔ）を有する格子構造における、真の動きベクトル（ＭＶＴ）と任意の選択された動きベクトル（ＭＶＳ）の間の関係を示す。
ＭＶＴｈ＝ＭＶＳｈ＋ｋ×Ｔｈ （１）
ここで、（ｈ）は動きベクトルとピッチ周期の水平成分を示し、ｋは選択された動きベクトルが真の動きベクトルからオフセットしている周期数を示す符号付整数変数である。理想的な状況では、ｋ＝０である。
【００５０】
式（１）から導かれるように、適応探索領域６０３内の局所最小値の数を、１に限定することができる。このとき、ｍは垂直ピッチ周期値（Ｔｖ）未満であり、ｎは水平ピッチ周期値（Ｔｈ）未満である。実施形態によっては、適応探索の範囲６０３（例えばｍ、ｎ、Ｏｈ、Ｏｖ）は、式（２）（３）に基づいてセットすることができる。
ｍ＝Ｔｖ−１ （２）
ｎ＝Ｔｈ−１ （３）
式（２）（３）に見られるように、ＴｈとＴｖはともに２以上であると仮定されている。Ｔｖ＝０である場合、垂直格子構造は検出されず、ｍはＭに関連する一定値にセットされ、オフセットＯｖ＝０となる。Ｔｈ＝０である場合、水平格子構造は検出されず、ｎはＮに関連する一定値にセットされ、オフセットＯｈ＝０となる。
【００５１】
実施形態によっては、適応探索領域６０３は、高速動作（変位）が存在するときは省略できる。実施形態によっては、ブロック合致誤差計算がさらに要求されることがないようにするため、適応探索領域６０３は、全探索領域５０３の包括的なサブセットであってもよく、その他の全ての領域におけるブロックマッチングは無視してよい。例えば、オフセット（Ｏｈ＝Ｎ／２）、適応探索領域６０３の中心位置が全探索領域５０３の右境界にあるとき、これにより適応探索領域６０３の左半分のみが考慮される。
【００５２】
実施形態によっては、探索領域５０３および６０３のサイズは、画像解像度に依拠する。例えば、高解像度ＨＤ−１０８０の領域５０３および６０３のサイズは、ＨＤ−７２０についてのサイズよりも大きく、またＨＤ−４８０についてのサイズよりも大きい。実施形態によっては、ＳＤ−７２０についての探索領域５０３および６０３はＳＤ−４８０についてのサイズの２倍であり、ＨＤ−１０８０についてはＳＤ−４８０のサイズの３倍である。
【００５３】
便宜上図６において、フレーム５０２は２つの探索領域（全探索領域５０３と適応探索領域６０３）を含む。しかし実際には、所与のフレームは任意数の探索領域を含み得ることが理解されよう。したがって本発明は、本発明に対応するフレーム内に含まれる探索領域の数に限定されるものではない。
【００５４】
便宜上図６において、全探索領域５０３と適応探索領域６０３は、それぞれ１つの最良合致ブロックを識別することを示している。しかし実際には、探索領域は任意数の最良合致ブロックを識別することができ、または全く識別しなくてもよいことが理解されよう。したがって本発明は、本発明に対応する探索領域内に含まれる最良合致ブロックの数に限定されるものではない。
【００５５】
先に説明したように、「最良合致」ブロックは、例えばＳＡＤ、ＳＳＤ、ＳＡＴＤ、または他の合致誤差のようなブロック合致誤差を最小化するブロックとして選択することができる。実施形態によっては、ＭＥＵ１１０は、１以上の誤差範囲を満たす（範囲内にある）最良合致ブロックを選択するように構成することができる。実施形態によっては、最良合致ブロックを選択する誤差範囲は、ＭＥＵ１１０の外部においてプログラムされており、および／またはＭＥＵ１１０が通信取得するように構成することができる。
【００５６】
図７は、本発明の実施形態に対応するシステム１００のようなビデオ符号化システムに含まれる動き推定部（ＭＥＵ）１１０のブロック図を示す。図６に見られるように、実施形態によっては、ＭＥＵ１１０は、ビデオ信号（例えば信号Ｉ）を受信し、現在フレーム（例えば現在フレーム５０４）と空間的に整列され得る１以上のフレーム（例えば参照フレーム５０２）を抽出するように連結された遅延部（ＤＵ）７０４を備えることができる。ＭＥＵ１１０は、現在フレーム５０４および参照フレーム５０２を（ＤＵ７０４から）受信するように連結された適応動き推定探索部（ＡＭＳＵ）７０２を備えることができる。ＡＭＳＵ７０２はさらに、適応探索手法を実装し、全探索動きベクトルとブロック合致誤差（それぞれ６０７、６０９）、ならびに適応探索動きベクトルとブロック合致誤差（それぞれ６０５、６１１）を識別するように構成することができる。
【００５７】
ＭＥＵ１１０はさらに、信号（Ｉ）を受信するように連結され、信号Ｉに含まれる１以上のフレームについてブロックベースの格子構造マップ（または格子周期マップ）７１２を生成するように構成された格子構造検知部（ＬＳＤＵ）７０６を備えることができる。図７に示すように、ＡＭＳＵ７０２は格子構造マップ７１２をＬＳＤＵ７０６から受け取ることができる。
【００５８】
ＭＥＵ１１０はさらに、格子構造マップ７１２（ＬＳＤＵ７０６から）と全探索動きベクトル６０７（ＡＭＳＵ７０２から）を受け取るように連結された動きヒストグラム生成部（ＭＨＧＵ）７０８を備えることができる。ＭＨＧＵ７０８は、動きオフセットパラメータ７１４（例えば、オフセット値ＯｈとＯｖ）を生成するように構成することができる。
【００５９】
図７に示すように、ＭＥＵ１１０はさらに、動きベクトル（６０７と６０５）、ブロック合致誤差（６０９と６１１）、および格子構造マップ７１２を受け取るように連結された動きベクトル選択部（ＭＶＳＵ）７１０を備えることができる。ＭＶＳＵ７１０は、最良合致ブロックを表す最終動きベクトル７１６を選択するように構成することができる。
【００６０】
初期化またはシーン変更において、ＡＭＳＵ７０２は現在フレーム５０４と参照フレーム５０２を受信し、ＡＭＳＵ７０２は全網羅的探索を実施して、全探索動きベクトル６０７および対応するブロック合致誤差６０９を識別することができる。同時に、ＭＨＧＵ７０８はＬＳＤＵ７０６から格子構造マップ７１２を受け取り、これにより、動きベクトル６０７を表す２次元ＭＶＨ７１１を生成することができる。ＭＨＧＵ７０８によって生成されるＭＶＨ７１１については、図１０で詳しく説明する。
【００６１】
実施形態によっては、現在フレーム５０４の最終ブロックがＡＭＳＵ７０２によって処理されるまでに、ＭＨＧＵ７０８内のＭＶＨ７１１は、現在フレーム５０４全体について動き情報（格子構造マップ７１２によって分類される）を収集する。ＭＨＧＵはさらにＭＶＨ７１１を処理し、格子構造マップ７１２内の各入手可能な周期値について動きオフセットパラメータ７１４を計算する。ＡＭＳＵ７０２はさらに、動きオフセットパラメータ７１４と格子構造マップ７１２を受け取り、これにより、適応探索領域６０３の範囲（例えば、ｍ、ｎ、Ｏｈ、Ｏｖ）を構成することができる。
【００６２】
ブロックがＡＭＳＵ７０２内の動き推定を経ると、全探索領域５０３は、全探索領域６０３に含まれる全ての動き変位について、ブロック合致誤差６０９および対応する動きベクトル６０７を計算することができる。また、適応探索領域６０３は、適応探索領域６０３に含まれる全ての動き変位について、ブロック合致誤差６１１および対応する動きベクトル６０５を計算することができる。動きベクトル（６０７と６０５）およびブロック合致誤差（６０９と６１１）をさらに、動きベクトル選択部（ＭＶＳＵ）７１０に送信することができる。動きベクトル選択部（ＭＶＳＵ）７１０は、格子構造マップ７１２に基づいてブロック合致誤差（６０９と６１１）を比較し、最終動きベクトル７１６間で選択する。本発明の実施形態に対応するＭＶＳＵ７１０については、図１１で詳しく説明する。
【００６３】
実施形態によっては、後向きおよび前向き動きベクトルは、２つのフレーム（５０２と５０４）を交換することによって取得できる。図８は、本発明の実施形態に対応するＡＭＳＵ７０２のブロック図を示す。図８に見られるように、ＡＭＳＵ７０２は、現在フレーム５０４と参照フレーム５０２を受け取るように連結されたブロックマッチング部（ＢＭＵ）８０２を備えることができる。ＢＭＵ８０２は、全探索領域５０３内の全ての変位（ｄｘ，ｄｙ）８１４について１以上のブロック合致誤差判定基準（例えばＳＡＤ）を評価することにより、ブロック合致誤差８２０を生成するように構成することができる。ＡＭＳＵ７０２はさらに、変位８１４を生成する動きベクトル走査部（ＭＳＣＵ）８０４を備えることができる。実施形態によっては、ＭＳＣＵ８０４は、位置（−Ｍ／２，−Ｎ／２）から開始し（Ｍ／２，Ｎ／２）で終了する変位８１４を、ラスター走査手法によって生成することができる。
【００６４】
図８に示すように、ＡＭＳＵ７０２はさらに、変位８１４とブロック合致誤差８２０を受け取るように連結された、全探索評価部（ＦＳＥＵ）８１２および適応探索評価部（ＡＳＥＵ）８１０を備えることができる。実施形態によっては、ブロック合致誤差８２０は、対応する変位とともにＦＳＥＵ８１２およびＡＳＥＵ８１０に順次送信される。ＦＳＥＵ８１２は、全探索領域５０３について大域最小ブロック合致誤差を評価し、対応するブロック合致誤差６０９とともに最良合致動きベクトル６０７を生成するように構成することができる。
【００６５】
ＡＭＳＵ７０２はさらに、格子構造マップ７１２および動きパラメータ７１４を受け取るように連結され、適応探索領域６０３の範囲８１６（例えばｍ、ｎ）を計算するように構成された探索領域計算部（ＳＡＣＵ）８０６を備えることができる。図８に示すように、ＡＭＳＵ７０２はさらに、変位８１４と範囲８１６を受け取るように連結され、現在フレーム５０４の全探索ブロックマッチングの間に８１４内の各（ｄｘ，ｄｙ）変位を比較して変位（ｄｘ，ｄｙ）が適応探索領域６０３内に含まれるか否かを識別するように構成された比較部（ＣＵ）８０８を備えることができる。実施形態によっては、ＣＵ８０８は、（ｄｘ，ｄｙ）変位が適応探索６０３領域内に含まれるか否かを、バイナリ信号８１８によって示すことができる。
【００６６】
図８に示すように、ＡＳＥＵ８１０はさらに、信号８１８を受信し、適応探索領域６０３内に含まれる全ての（ｄｘ，ｄｙ）変位値について、対応する最良合致ベクトル６０５とともに、局所最小ブロック合致誤差６１１を計算することができる。
【００６７】
図９ａは、本発明の実施形態に対応するＬＳＤＵ７０６のブロック図を示す。図９ａに示すように、ＬＳＤＵ７０６は、フレーム５０２のようなフレームを受け取るように連結され、フレーム５０２内のピクセルに対してウインドウベースサンプリングを実装してピクセルサンプル９１２を取得するように構成されたサンプリングウインドウ部（ＳＷＵ）９０２を備えることができる。実施形態によっては、ＳＷＵ９０２は、正規化１次元サンプリングウインドウを備えることができる。サンプリングウインドウのサイズは、検知し得るピッチ周期範囲に依拠する。実施形態によっては、［２〜Ｎ］の周期範囲について、少なくとも２Ｎピクセルのサンプリングウインドウサイズが用いられる。実施形態によっては、ＳＷＵ９０２は、全てのサンプリングされたピクセルの平均値を計算し、その平均値を各ピクセルサンプルから減算することにより、（フレーム５０２の）ピクセルサンプル９１２を、ゼロ値平均に正規化することができる。
【００６８】
図９ａに示すように、ＬＳＤＵ７０６はさらに、ピクセルサンプル９１２を受け取るように連結され、重み付けされたピクセルサンプル９１４を取得するための重み付け機能を実装するように構成された重み付け部（ＷＵ）９０４を備えることができる。ＷＵ９０４によって実装される重み付け機能は、サンプリングウインドウの中心周辺のピクセルサンプルをより強調し、サンプリングウインドウの終端近傍のサンプルを弱めることができる。実施形態によっては、ＷＵ９０４は、ピクセルサンプル９１２にハミング窓変調（または重み付け）を実装し、重み付けされたサンプル９１４を取得することができる。実施形態によっては、ハミング窓を使用することにより、１の隣接ブロックから次のブロックへ向けたより一貫性のある周期検出を提供することができる。
【００６９】
ＬＳＤＵ７０６はさらに、重み付けされたサンプル９１４を受け取るように連結され、フーリエ変換を実施して変換係数９１６を取得するように構成された高速フーリエ変換部（ＦＦＴ）９０６を備えることができる。実施形態によっては、係数９１６は係数の振幅成分のみを含むこともできる。
【００７０】
図９ａに示すように、ＬＳＤＵ７０６はまた、係数９１６を受け取るように連結され、係数９１６の振幅スペクトルに対してピーク検出手法を実装し、最も強い周波数振幅ピークを検出するように構成された、ピークおよび周期計算部（ＰＰＣＵ）９０８を備えることができる。ＰＰＣＵ９０８はさらに、最良ピーク周波数値を選択し、その最良ピーク周波数値をピッチ周期マップ９１８に変換することができる。ＬＳＤＵ７０６はさらに、ピッチ周期マップ９１８を受け取るように連結され、周期マップ９１８をフィルタリングすることによって格子構造マップ７１２（または格子構造周期マップ）７１２を生成するように構成されたフィルタ周期部（ＦＰＵ）９１０を備えることができる。周期マップ９１８をフィルタリングすることにより、ＦＰＵ９１０はさらに一貫性（滑らかさ）を改善し、周期マップ９１８内の検出された周期の隔絶したまたは誤った検出結果を除去することができる。
【００７１】
図９ｂは、フレーム５０２内に含まれる格子構造９３０の例を示す。円で囲った領域９３２は、水平ピッチ周期値（Ｔｈ）を示す、フレーム５０２の水平成分を示す。水平ピッチ周期Ｔｈのようなピッチ周期に関する情報は、格子構造マップ７１２内に含まれている。
【００７２】
実施形態によっては、ウインドウ化信号自動相関のような他手法を、ウインドウ化周波数変換に代えて用い、ブロック毎に格子構造の周期値を検出することができる。実施形態によっては、入力フレームの異なる解像度に対して格子構造を階層的に検出することもできる。階層的検知手法を用いることにより、様々な画像のダウンサンプリング段階を通して、より広い範囲のピッチ周期を検出することができる。例えば、画像が２分の１にダウンサイズされると、周期は２分の１に小さくなり、等価な周期検出範囲は２倍に大きくなる。
【００７３】
図７を用いて先に説明したように、ＭＨＧＵ７０８は、ＡＭＳＵ７０２が使用する動きオフセットパラメータ７１４を計算するために用いる動きベクトルヒストグラム（ＭＶＨ）７１１を生成することができる。図１０は、ＭＨＧＵ７０８が生成するヒストグラムＭＶＨ７１１の例を示す。
【００７４】
図１０に見られるように、ＭＶＨ７１１は、例示するヒストグラムビン１００４のようなヒストグラムビンを備えることができる。水平軸（ＭＶｈ）は、全ての可能な水平動き値［−Ｎ／２〜Ｎ／２］を表し、垂直軸（Ｔｈ）は、全ての可能な被検出水平ピッチ周期値［２〜Ｎ］を表すことができる。図１０におけるヒストグラムＭＶＨの例は、ピクセルブロック内の被検出ピッチ周期４と他のピクセルブロック内の被検出ピッチ周期５を含む格子構造を有するフレームを示す。さらに、図１０に示すように、周期値４および５双方について、ほとんどの発生動きベクトルはＭＶ０（それぞれ７５回、９０回発生している）である。図１０に示すように、ピッチ周期４について、ＭＶ０とＭＶ＋４は、正確に互いから１ピッチ周期離れており、これはＭＶ＋４があるフレームの特定ブロックにおいて誤ってマッチングされる可能性を示す。
【００７５】
先に説明したように、ＭＨＧＵ７０８は、ＭＶＨ７１１を解析して動きオフセット値７１４を生成することができる。実施形態によっては、ＭＨＧＵ７０８はＭＶＨ７１１をフィルタリングし、格子構造マップ７１２内の各周期について最適動作を判定することができる。例えば、図１０に示すＭＶＨ７１１を参照すると、周期４または５の周期格子構造に属するブロックは、水平オフセットＯｈが０にセットされ、幅ｎが式（３）を用いて説明した値にセットされるように構成された適応探索領域６０３を有し得ることが分かる。
【００７６】
実施形態によっては、全てのヒストグラムビン（例えば例示するビン１００４）は、各新フレームが入ってくる毎にリセットすることができる。先に説明したように、実施形態によっては、ＭＨＧＵ７０８は、各フレームについて２つのヒストグラムを生成することができる。その１つは水平動きベクトル成分および水平周期であり、もう１つは垂直動きベクトル成分および垂直周期である。
【００７７】
図１１は、本発明の実施形態に対応する動きベクトル選択部（ＭＶＳＵ）７１０のブロック図を示す。図１１に示すように、ＭＶＳＵ７１０は、全探索動きベクトルおよび適応探索動きベクトル（６０７と６０５）ならびに格子構造マップ７１２を受け取るように連結された動きベクトル比較部（ＭＶＣＵ）１１０２を備えることができる。ＭＶＣＵ１１０２はさらに、各ブロックについて動きベクトル（６０７と６０５）間の絶対差分を比較するように構成することができる。所与のブロックについてのベクトル（６０７と６０５）間の絶対差分が０でなく、複数のピッチ周期値（格子マップ７１２から）である場合、実施形態によっては、ＭＶＣＵ１１０２は、現在ブロック位置における入力フレーム内の格子構造の存在を示す検証信号１１１０を生成することができる。実施形態によっては、検証信号１１１０はバイナリ信号である。
【００７８】
ＭＶＳＵ７１０はさらに、検証信号１１１０を受け取るように連結され、パラメータ（１１１２と１１１４）を選択するように構成されたマルチプレクサ１１０６を備えることができる。検証信号１１１０に基づき、マルチプレクサ１１０６は、係数とオフセット値を含むペナルティーパラメータ１１１６を送信することができる。図１１に示すように、ＭＶＳＵ７１０は、マッチング誤差（６０９と６１１）とペナルティーパラメータ１１１６を受け取るように連結されたマッチング誤差計算部（ＭＥＣＵ）１１０４を備えることができる。ＭＥＣＵ１１０４はさらに、選択信号１１１８を生成するように構成することができる。実施形態によっては、ペナルティーパラメータ１１１６は、ＭＥＣＵ１１０４が対応する全探索マッチング誤差６０９にペナルティーを課し、対応する適応探索動きベクトル６０５をより選択に適するようにするために用いることができる。例えば、格子構造が存在する場合、マルチプレクサ１１０６は、検証信号１１１０を介して、ペナルティーパラメータ１１１６を送信するように構成することができる。このペナルティーパラメータ１１１６により、ＭＥＣＵ１１０４は、適応探索動きベクトル６０５をより選択されやすくする（選択信号１１１８とマルチプレクサ１１０８を介して）ことができる。これは、全探索マッチング誤差６０９に大きなペナルティーが適用されるからである。周期格子構造が存在しない場合、マルチプレクサ１１０６を検証信号１１１０によって構成し、ＭＥＣＵ１１０４がより小さいペナルティーを全探索マッチング誤差６０９に適用してブロックマッチング誤差（６０９と６１１）が類似しているときに適応探索ベクトル６０５が選択され得る（選択信号１１１８とマルチプレクサ１１０８を介して）ように、ペナルティー係数１１１６を生成することができる。実施形態によっては、大域最小値により、ペナルティーを課されない全探索マッチング誤差６０９は、適応探索マッチング誤差６１１以下となり得る。
【００７９】
実施形態によっては、選択信号１１１８は、バイナリ信号であってもよい。選択信号１１１８に基づき、マルチプレクサ１１０８は、最終動きベクトル７１６を、全探索動きベクトルと適応探索動きベクトル（６０７と６０５）の間で選択することができる。
【００８０】
他の実施形態は、当業者にとって、ここに開示する明細書と実施例の検討から明らかである。明細書と実施例は、例示目的のみを意図しており、本発明の真の範囲と趣旨は特許請求の範囲によって示される。
【特許請求の範囲】
【請求項１】
第１フレーム内のピクセルブロックの動きを推定する方法であって、
第２フレーム内の第１領域を探索して前記ピクセルブロックに対応する第１合致ブロックを識別するステップであって、前記第１合致ブロックは、前記ピクセルブロックと前記第１合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第１誤差値を含むステップと、
前記第１合致ブロックに関連する第１動きベクトルを計算するステップと、
前記第２フレーム内の第２領域を探索して前記ピクセルブロックに対応する第２合致ブロックを識別するステップであって、前記第２合致ブロックは、前記ピクセルブロックと前記第２合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第２誤差値を含むステップと、
前記第２合致ブロックに関連する第２動きベクトルを計算するステップと、
前記第１および第２誤差値に基づき、前記第１および第２動きベクトルの間で最終動きベクトルを選択するステップと、
を有することを特徴とする動き推定方法。
【請求項２】
前記第１領域を探索して前記第１合致ブロックを識別するステップはさらに、
前記第１領域を、第１複数ピクセルブロックによって広げられた領域として提供するステップと、
前記第１複数ピクセルブロックを探索して、前記ピクセルブロックと前記第１合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である前記第１誤差値を含む前記第１合致ブロックを識別するステップと、
前記第１合致ブロックに関連する第１動きベクトルを計算するステップと、
を有することを特徴とする請求項１記載の動き推定方法。
【請求項３】
前記第２領域を探索して前記第２合致ブロックを識別するステップは、
前記第１フレームの第１格子構造マップであって、前記第１フレーム内の少なくとも１つの繰り返し構造に関連する少なくとも１つのピッチ周期値を含む、前記第１格子構造マップを検出するステップと、
前記第１フレームについての第１ヒストグラムであって、前記第１および第２動きベクトルならびに前記第１格子構造マップから導出され、前記第１および第２動きベクトルと前記少なくとも１つのピッチ周期値との間の関係を含む、前記第１ヒストグラムを生成するステップと、
少なくとも１つのパラメータを前記第１格子構造マップと前記第１動きベクトルヒストグラムから導出するステップと、
前記第２領域を、第２複数ピクセルブロックによって広げられた領域として提供するステップであって、前記第２領域は、前記第１領域のサブセットとして含まれており、前記第２領域はさらに、前記少なくとも１つのパラメータから導出された少なくとも１つの領域範囲を含んでいるステップと、
前記第２複数ピクセルブロックを探索して、前記ピクセルブロックと前記第２合致ブロックの間の少なくとも１つの誤差判定基準についての最小値を含む前記第２誤差値を含む前記第２合致ブロックを識別するステップと、
前記第２合致ブロックに関連する前記第２動きベクトルを計算するステップと、
を有することを特徴とする請求項１記載の動き推定方法。
【請求項４】
前記第１および第２動きベクトルの間で最終動きベクトルを選択するステップは、
第１格子構造マップ内に含まれる前記少なくとも１つのピッチ周期値に基づき第１ペナルティー値を計算するステップであって、前記第１ペナルティー値は、前記第１誤差値および／または前記第２誤差値を調整するステップと、
調整された前記第１および第２誤差値に基づき、前記第１および第２動きベクトルの間で前記最終動きベクトルを選択するステップと、
を有することを特徴とする請求項１記載の動き推定方法。
【請求項５】
第１フレーム内のピクセルブロックの動きを推定する装置であって、
第２フレームを探索して、前記ピクセルブロックに対応する第１合致ブロックに関連する第１動きベクトルを計算するように連結された適応動き探索部（ＡＭＳＵ）であって、前記第１合致ブロックは、前記ピクセルブロックと前記第１合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第１誤差値を含み、前記ＡＭＳＵはさらに、前記ピクセルブロックに対応する第２合致ブロックに関連する第２動きベクトルを計算し、前記第２合致ブロックは、前記ピクセルブロックと前記第２合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第２誤差値を含む、適応動き探索部と、
前記第１フレームの第１格子構造マップであって、前記第１フレーム内の少なくとも１つの繰り返し構造に関連する少なくとも１つのピッチ周期値を含む第１格子構造マップを検出するように連結された、格子構造検出部（ＬＳＤＵ）と、
前記第１フレームについての第１ヒストグラムであって、前記第１動きベクトルと前記第１格子構造マップから導出され、前記第１動きベクトルと少なくとも１つの前記ピッチ周期値との間の関係を含む第１ヒストグラムを生成するように連結された、動きヒストグラム生成部（ＭＨＧＵ）と、
前記第１および第２誤差値に基づき、前記第１および第２動きベクトルの間で最終動きベクトルを選択するように連結された動きベクトル選択部（ＭＶＳＵ）と、
を有することを特徴とする動き推定装置。
【請求項１】
第１フレーム内のピクセルブロックの動きを推定する方法であって、
第２フレーム内の第１領域を探索して前記ピクセルブロックに対応する第１合致ブロックを識別するステップであって、前記第１合致ブロックは、前記ピクセルブロックと前記第１合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第１誤差値を含むステップと、
前記第１合致ブロックに関連する第１動きベクトルを計算するステップと、
前記第２フレーム内の第２領域を探索して前記ピクセルブロックに対応する第２合致ブロックを識別するステップであって、前記第２合致ブロックは、前記ピクセルブロックと前記第２合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第２誤差値を含むステップと、
前記第２合致ブロックに関連する第２動きベクトルを計算するステップと、
前記第１および第２誤差値に基づき、前記第１および第２動きベクトルの間で最終動きベクトルを選択するステップと、
を有することを特徴とする動き推定方法。
【請求項２】
前記第１領域を探索して前記第１合致ブロックを識別するステップはさらに、
前記第１領域を、第１複数ピクセルブロックによって広げられた領域として提供するステップと、
前記第１複数ピクセルブロックを探索して、前記ピクセルブロックと前記第１合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である前記第１誤差値を含む前記第１合致ブロックを識別するステップと、
前記第１合致ブロックに関連する第１動きベクトルを計算するステップと、
を有することを特徴とする請求項１記載の動き推定方法。
【請求項３】
前記第２領域を探索して前記第２合致ブロックを識別するステップは、
前記第１フレームの第１格子構造マップであって、前記第１フレーム内の少なくとも１つの繰り返し構造に関連する少なくとも１つのピッチ周期値を含む、前記第１格子構造マップを検出するステップと、
前記第１フレームについての第１ヒストグラムであって、前記第１および第２動きベクトルならびに前記第１格子構造マップから導出され、前記第１および第２動きベクトルと前記少なくとも１つのピッチ周期値との間の関係を含む、前記第１ヒストグラムを生成するステップと、
少なくとも１つのパラメータを前記第１格子構造マップと前記第１動きベクトルヒストグラムから導出するステップと、
前記第２領域を、第２複数ピクセルブロックによって広げられた領域として提供するステップであって、前記第２領域は、前記第１領域のサブセットとして含まれており、前記第２領域はさらに、前記少なくとも１つのパラメータから導出された少なくとも１つの領域範囲を含んでいるステップと、
前記第２複数ピクセルブロックを探索して、前記ピクセルブロックと前記第２合致ブロックの間の少なくとも１つの誤差判定基準についての最小値を含む前記第２誤差値を含む前記第２合致ブロックを識別するステップと、
前記第２合致ブロックに関連する前記第２動きベクトルを計算するステップと、
を有することを特徴とする請求項１記載の動き推定方法。
【請求項４】
前記第１および第２動きベクトルの間で最終動きベクトルを選択するステップは、
第１格子構造マップ内に含まれる前記少なくとも１つのピッチ周期値に基づき第１ペナルティー値を計算するステップであって、前記第１ペナルティー値は、前記第１誤差値および／または前記第２誤差値を調整するステップと、
調整された前記第１および第２誤差値に基づき、前記第１および第２動きベクトルの間で前記最終動きベクトルを選択するステップと、
を有することを特徴とする請求項１記載の動き推定方法。
【請求項５】
第１フレーム内のピクセルブロックの動きを推定する装置であって、
第２フレームを探索して、前記ピクセルブロックに対応する第１合致ブロックに関連する第１動きベクトルを計算するように連結された適応動き探索部（ＡＭＳＵ）であって、前記第１合致ブロックは、前記ピクセルブロックと前記第１合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第１誤差値を含み、前記ＡＭＳＵはさらに、前記ピクセルブロックに対応する第２合致ブロックに関連する第２動きベクトルを計算し、前記第２合致ブロックは、前記ピクセルブロックと前記第２合致ブロックの間の少なくとも１つの誤差判定基準についての最小値である第２誤差値を含む、適応動き探索部と、
前記第１フレームの第１格子構造マップであって、前記第１フレーム内の少なくとも１つの繰り返し構造に関連する少なくとも１つのピッチ周期値を含む第１格子構造マップを検出するように連結された、格子構造検出部（ＬＳＤＵ）と、
前記第１フレームについての第１ヒストグラムであって、前記第１動きベクトルと前記第１格子構造マップから導出され、前記第１動きベクトルと少なくとも１つの前記ピッチ周期値との間の関係を含む第１ヒストグラムを生成するように連結された、動きヒストグラム生成部（ＭＨＧＵ）と、
前記第１および第２誤差値に基づき、前記第１および第２動きベクトルの間で最終動きベクトルを選択するように連結された動きベクトル選択部（ＭＶＳＵ）と、
を有することを特徴とする動き推定装置。
【図１】
【図２ａ】
【図２ｂ】
【図３】
【図４ａ】
【図４ｂ】
【図５】
【図６】
【図７】
【図８】
【図９ａ】
【図９ｂ】
【図１０】
【図１１】
【図２ａ】
【図２ｂ】
【図３】
【図４ａ】
【図４ｂ】
【図５】
【図６】
【図７】
【図８】
【図９ａ】
【図９ｂ】
【図１０】
【図１１】
【公表番号】特表２０１１−５０８５１７（Ｐ２０１１−５０８５１７Ａ）
【公表日】平成２３年３月１０日（２０１１．３．１０）
【国際特許分類】
【出願番号】特願２０１０−５３９５０５（Ｐ２０１０−５３９５０５）
【出願日】平成２０年１２月１８日（２００８．１２．１８）
【国際出願番号】ＰＣＴ／ＵＳ２００８／０１３９４２
【国際公開番号】ＷＯ２００９／０８５２３２
【国際公開日】平成２１年７月９日（２００９．７．９）
【出願人】（５０８２４９６９７）インテグレーテッド・デバイス・テクノロジー・インコーポレーテッド (6)
【Ｆターム（参考）】
【公表日】平成２３年３月１０日（２０１１．３．１０）
【国際特許分類】
【出願日】平成２０年１２月１８日（２００８．１２．１８）
【国際出願番号】ＰＣＴ／ＵＳ２００８／０１３９４２
【国際公開番号】ＷＯ２００９／０８５２３２
【国際公開日】平成２１年７月９日（２００９．７．９）
【出願人】（５０８２４９６９７）インテグレーテッド・デバイス・テクノロジー・インコーポレーテッド (6)
【Ｆターム（参考）】
[ Back to top ]