JP2007531345A - 高速サーチ・ブロック・マッチングを用いた動き推定 - Google Patents

Abstract

イメージ・ブロックのためのビデオ信号データおよびこのイメージ・ブロックを予測するための特定の参照ピクチャ指標を符号化するビデオ符号器および対応する方法が提供される。符号器（１００）は、少なくとも１つの特定の参照ピクチャに対応する動きベクトルを提供する高速サーチ・ブロック動き推定器（１８０）を含んでいる。動き推定器は、高速サーチ・ブロック・マッチングを実行し、イメージ・ブロック・ピクセルを正規化したものと参照ピクチャ・ピクセルを正規化したものとの比較に従って最適でないサーチ・ポイントを除外する高速サーチ・ブロック・マッチング部を含み、この高速サーチ・ブロック・マッチング部は、少なくとも１つの特定の参照ピクチャに応答する出力を有する。対応する方法（２００）は、実質的に圧縮されていないイメージ・ブロックを受信するステップ（２１２）と、少なくとも１つの特定の参照ピクチャに応答して前記イメージ・ブロックのブロック・マッチングを行い、イメージ・ブロック・ピクセルを正規化したものと参照ピクチャ・ピクセルを正規化したものとの比較に従って最適でないサーチ・ポイントを除外するステップ（２１４）と、イメージ・ブロックと少なくとも１つの特定の参照ピクチャとの差に対応する動きベクトルを計算するステップ（２１６）と、動きベクトルに応答して少なくとも１つの特定の参照ピクチャを動き補償するステップ（２１８）を含んでいる。

Description

（関連出願とのクロスリファレンス）
本出願は、２００３年７月１５日付で出願された米国仮特許出願第６０／４８７,４５８号の優先権を主張するものである。

本発明は、一般には、ビデオ符号器（エンコーダ）およびビデオ復号器（デコーダ）に関し、より具体的には、ビデオ符号器およびビデオ復号器における動き推定アルゴリズムに関する。

一般に、ビデオ・データは、ビットストリームの形式で処理され、転送される。通常、ビデオ圧縮符号器および復号器（「コーデック（ＣＯＤＥＣ）」）は、符号化されるピクチャの参照ピクチャ予測（ｒｅｆｅｒｅｎｃｅ ｐｉｃｔｕｒｅ ｐｒｅｄｉｃｔｉｏｎ）を形成し、現在のピクチャと予測したものとの間の差を符号化することにより大きな圧縮効率が得られる。予測したものが現在のピクチャとより密接に相関するほど、このピクチャを圧縮するために必要となるビットが少なくなり、処理の効率が高められる。従って、できる限り最良のピクチャ予測が形成されることが望ましい。

ＭＰＥＧ（Ｍｏｖｉｎｇ Ｐｉｃｔｕｒｅ Ｅｘｐｅｒｔｓ Ｇｒｏｕｐ）１、ＭＰＥＧ２、およびＭＰＥＧ４を含む多くのビデオ圧縮規格・標準においては、前の参照ピクチャと現在のピクチャとの間の動きが推定され、前の参照ピクチャの動き補償されたバージョンを形成する。前の参照ピクチャの動き補償されたバージョンは、現在のピクチャを予測したものとして使用され、現在のピクチャと予測されたものの差のみが符号化される。

動き推定は、現在のビデオ符号化システムにおいて重要な役割を果たし、一般に、符号器の最も演算が困難な部分である。大抵の現在のビデオ符号化規格には、ブロック・マッチング・アルゴリズムが採用されている。フルサーチ（ＦＳ：Ｆｕｌｌ Ｓｅａｒｃｈ、全探索）手法は、ブロック毎に動きの量を推定する周知の動き推定方法である。残念ながら、フルサーチ手法は、特に、複数の参照ピクチャおよび複数のブロック・タイプを用いるＨ．２６４などの高度なビデオ符号化規格では、演算が複雑となる。スリー・ステップ・サーチ（３段探索）、新スリー・ステップ・サーチ（新３段探索）、ダイヤモンド・サーチ、ゾーン・サーチ、階層または複数解像度（ｍｕｌｔｉ‐ｒｅｓｏｌｕｔｉｏｎ）サーチ、またはこれらを組み合わせたものなど、幾つかの高速サーチ（探索）アルゴリズムが提案されている。このようなアルゴリズムは、サーチ（探索）するポイントの数を減少させることにより、演算量を低減させるものである。残念ながら、これらは、誤差表面（ｅｒｒｏｒ ｓｕｒｆａｃｅ）上でローカル・ミニマム（局所的な極小値）に陥りやすく、その性能は、一般に、フルサーチ手法のものよりも劣っている。

大抵の現在のビデオ符号化規格には、ビットレートを低減するためのブロック動き推定が採用されている。ビデオ符号化のためのブロック動き推定はよく研究されているが、Ｈ．２６３＋＋やＪＶＴ／Ｈ．２６４／ＭＰＥＧ ＡＶＣなどの複数の参照ピクチャおよび複数のブロック・タイプの選択についてはほとんど何も提案されてない。

Ｈ．２６４においては、動き補償のために様々なモードが提供されている。各動き補償されたマクロブロックのモードは、固定サイズのブロックに対応する。ブロックは、１６×１６、１６×８、８×１６、更に、８×８のパーティションに分割される。また、８×８のブロックは、８×４、４×８、または、４×４のブロック・サイズのサブパーティションに分割される。従って、合計７個のブロック・タイプがサポートされている。各予測符号化されたｍ×ｎのブロックのための予測信号は、対応する参照ピクチャの領域を変位させることにより得ることができ、これは、動きベクトル予測値（ｐｒｅｄｉｃｔｏｒ）とは異なって符号化される並進動きベクトルにより特定される。更に、Ｈ．２６４は、複数ピクチャの動き補償された予測をサポートする。即ち、１つ以上の前に符号化されたピクチャが参照として使用され、予測符号化されたブロックの予測信号を構成する。従って、動き推定のために、符号器は、どのブロック・タイプを選択するべきか、どの参照ピクチャを選択するべきかを決定しなければならない。この複数参照ピクチャおよび複数ブロック・タイプの選択により、動きサーチがより複雑になる。

現在、フルサーチ（ＦＳ）と、更に、例えば、スリー・ステップ・サーチ、新スリー・ステップ・サーチ、ダイヤモンド・サーチ、ゾーン・サーチ、および階層サーチなどの幾つかの高速サーチ・アルゴリズムが提案されている。この中で、フルサーチのみが最適な解決策を生み出すものである。従って、必要とされているものは、フルサーチ・アルゴリズムよりも演算量を低減した上、最適な解決策を生み出す方法である。

（発明の概要）
従来技術のこれらのおよび他の欠点、不都合は、ビデオ符号器およびビデオ復号器において高速サーチ・ブロック・マッチングを行うための装置および方法により解決される。

イメージ・ブロックのためのビデオ信号データおよびこのイメージ・ブロックを予測するための特定の参照ピクチャ指標を符号化するビデオ符号器が提供される。符号器は、少なくとも１つの特定の参照ピクチャに対応する動きベクトルを提供する高速サーチ・ブロック動き推定器を含んでいる。動き推定器は、高速サーチ・ブロック・マッチングを実行し、イメージ・ブロック・ピクセル（画素）を正規化したものと参照ピクチャ・ピクセルを正規化したものとの比較に従って最適でないサーチ・ポイントを除外する高速サーチ・ブロック・マッチング部を含み、この高速サーチ・ブロック・マッチング部は、少なくとも１つの特定の参照ピクチャに応答する出力を有する。

イメージ・ブロックのためのビデオ信号データを符号化するための対応する方法は、実質的に圧縮されていないイメージ・ブロックを受信するステップと、少なくとも１つの特定の参照ピクチャに応答してイメージ・ブロックのブロック・マッチングを行い、イメージ・ブロック・ピクセルを正規化したものと参照ピクチャ・ピクセルを正規化したものとの比較に従って最適でないサーチ・ポイントを除外するステップと、イメージ・ブロックと少なくとも１つの特定の参照ピクチャとの差に対応する動きベクトルを計算するステップと、動きベクトルに応答して少なくとも１つの特定の参照ピクチャを動き補償するステップとを含んでいる。本発明のこれらの態様、特徴および利点、また、その他の態様、特徴および利点は、添付図面を参照して以下の本発明の例示的な実施の形態の説明を読むことにより明らかになるであろう。

本発明の上述した特徴が実現され、詳細な理解が可能になるように、上に要約した本発明のより具体的な説明が実施の形態を参照して行われる。各実施の形態は、付随する図面に示されている。

しかしながら、添付図面は、代表的な本発明の実施の形態を示すものに過ぎず、本発明の範囲を限定するものと解釈されてはならず、本発明を他の同様の効果を生み出す実施の形態にも適用することができることを理解すべきである。

本発明は、高速サーチ・ブロック・マッチングを用いて動き推定を実行するものである。本発明の各実施の形態は、最適でないサーチ・ポイントを捨てるために、連続削除（ｓｕｃｃｅｓｓｉｖｅ ｅｌｉｍｉｎａｔｉｏｎ）を使用し、予め計算されたデータを使用することにより、フルサーチ方法の最適性を犠牲にすることなく計算を節約する。

動き推定（ｍｏｔｉｏｎ ｅｓｔｉｍａｔｉｏｎ）の技術は、広く研究されている。符号化しようとしているピクチャの各動きブロックに対し、参照ピクチャからの動きブロックの変位を表す動きベクトルが選択される。包括的サーチ方法においては、サーチ領域内で、動きブロックの位置に対して所定のオフセット範囲内にある各変位がテストされる。このテストには、現在のピクチャ内の動きブロックと参照ピクチャ内で変位した動きブロックとの各ピクセルの差の絶対値の和（ＳＡＤ：Ｓｕｍ ｏｆ ｔｈｅ Ａｂｓｏｌｕｔｅ Ｄｉｆｆｅｒｅｎｃｅ）や平均二乗誤差（ＭＳＥ：Ｍｅａｎ Ｓｑｕａｒｅ Ｅｒｒｏｒ）を計算することが含まれる。最小の絶対値の和（ＳＡＤ）または平均二乗誤差（ＭＳＥ）を有するオフセットが動きベクトルとして選択される。例えば、スリー・ステップ・サーチ（３段探索）やレート歪み最適化動き推定（ｒａｔｅ‐ｄｉｓｔｏｒｔｉｏｎ ｏｐｔｉｍｉｚｅｄ ｍｏｔｉｏｎ ｅｓｔｉｍａｔｉｏｎ）など、この技術には多くの変形例が提案されている。

以下の説明は、発明の原理を例示するものに過ぎない。従って、当業者であれば、本明細書に明確に記載、図示されていなくとも、本発明の原理を実施する様々な構成を考案することが可能であり、このような構成の各々が本発明の精神および範囲に包含されることが理解できるであろう。更に、本明細書に記載された全ての例および条件付の文言は、本発明の原理を読者が理解するのを助けるための開示目的のものであり、発明者により寄与された概念は、技術を発展させるものであり、このような具体的に記載された例や条件に限定されるように解釈されるべきではない。また、本明細書における本発明の原理、態様、および、実施の形態についての全ての記載、更に、その特定の例は、構造的、機能的な均等物の双方を包含するように意図したものである。更に、このような均等物は、現在公知の均等物だけでなく、将来において開発される均等物、即ち、構造に係らず、同一の機能を実行するように開発された全ての要素を包含するように意図されている。

従って、例えば、当業者であれば、本明細書において示されたブロック図は、本発明の原理を実施する回路を例示する概念図であることが理解できよう。同様に、フローチャート、フロー図、状態遷移図、擬似コードなどは、何れも様々な処理を表す。これらの処理は、実質的にコンピュータにより読み取り可能なメディアにおいて表すことができ、コンピュータまたはプロセッサにより実行され、このようなコンピュータまたはプロセッサがはっきりと図示されているかどうかに係るものではない。

各図面において示される様々な要素の機能は、専用のハードウェアの使用により提供されてもよく、適切なソフトウェアと関連付けてソフトウェアを実行することが可能なハードウェアの使用により提供されてもよい。機能が、プロセッサにより提供される場合にも、単一の専用プロセッサにより提供されてもよく、単一の共有プロセッサにより提供されてもよく、複数の別個のプロセッサにより提供されてもよく、幾つかのプロセッサが共有されていてもよい。更に、用語「プロセッサ（ｐｒｏｃｅｓｓｏｒ）」または「コントローラ（ｃｏｎｔｒｏｌｌｅｒ）」を明示的に使用した場合であっても、ソフトウェアを実行することが可能なハードウェアのみを意味するように解釈されるべきではなく、限定するものではないが、ディジタル信号プロセッサ（ＤＳＰ：Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｏｒ）ハードウェア、ソフトウェアを記憶する読み出し専用メモリ（ＲＯＭ：Ｒｅａｄ‐Ｏｎｌｙ Ｍｅｍｏｒｙ）、ランダム・アクセス・メモリ（ＲＡＭ：Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、および不揮発性の記憶装置を暗示的に含むことがある。また、従来のおよび／または慣習的な他のハードウェアを含むこともある。同様に、図面に示されたどのスイッチも概念的なものに過ぎない。これらの機能はプログラム論理回路の動作を介して、専用の論理回路を介して、プログラム制御と専用の論理回路との相互採用を介して、または、手動でも実行されることがある。文脈からより具体的に理解できるように、実施者により、特定の技術を選択可能である。

請求の範囲において、特定の機能を実施するための手段として表現された何れの要素も、この機能をどのような方法で実行するものも包含するように意図している。例えば、ａ）機能を実行する回路要素を組み合わせたもの、または、ｂ）いかなる形態のソフトウェア、つまり、ファームウェア、マイクロコード等を含むもの、機能を実施するためにソフトウェアを実行する適当な回路と組み合わせたものも包含する。このような請求の範囲により定義される発明は、請求の範囲により要求されているように、様々な記載された手段により提供される機能性が組み合わされ、まとめられるという事実に基づいたものである。従って、出願人は、このような機能性を提供することが可能な手段はどのようなものであっても、本願において示されているものと均等であるとみなす。

高速サーチ・ブロック・マッチング動き推定アルゴリズムは、フルサーチ・ブロック・マッチングと匹敵する品質を達成すると共に、演算量を低減する。ここに開示する連続消去アルゴリズムの実施の形態は、三角不等式に基づく測定基準を用いて早期に最適でないサーチ・ポイントを除去し、予め計算されたデータを採用することにより、計算の数を減少させる。このアルゴリズムは、ソフトウェアおよびハードウェア双方の実施の形態に適用することができ、また、他の発見的な高速サーチ・アルゴリズムに適用することも可能である。

図１を参照すると、高速サーチ・ブロック・マッチング動き推定を行うビデオ符号器が概ね参照符号１００により示されている。符号器１００に対する入力は、加算接合部（ｓｕｍｍｉｎｇ ｊｕｎｃｔｉｏｎ）１１０の非反転入力と信号通信するように結合されている。加算結合部１１０の出力は、ブロック変換器１２０と信号通信するように結合されている。変換器１２０は、量子化器１３０と信号通信するように結合されている。量子化器１３０の出力は、可変長符号器（ＶＬＣ：ｖａｒｉａｂｌｅ ｌｅｎｇｔｈ ｃｏｄｅｒ）１４０と信号通信するように結合され、可変長符号器（ＶＬＣ）１４０の出力は、符号器１００の外部的に利用可能な出力である。

更に、量子化器１３０の出力は、逆量子化器１５０と信号通信するように結合される。逆量子化器１５０は、逆ブロック変換器１６０と信号通信するように結合される。また、逆ブロック変換器１６０は、参照ピクチャ記憶装置１７０と信号通信するように結合される。参照ピクチャ記憶装置１７０の第１の出力は、高速サーチ・ブロック・マッチング動き推定器１８０の第１の入力と信号通信するように結合される。更に、符号器１００への入力は、高速サーチ・ブロック・マッチング動き推定器１８０の第２の入力と信号通信するように結合される。

本明細書において本発明は、動き推定ブロックの概念的な部分が説明されるが、代替的な実施の形態においては、別個の高速ブロック・サーチ部により動き推定部にどのオペレーティング・ポイントをテストするか、テストしないかを示す部分間の信号を供給するようにしてもよいことが理解できよう。高速サーチ・ブロック・マッチング動き推定器１８０の出力は、動き補償器１９０の第１の入力と信号通信するように結合される。参照ピクチャ記憶装置１７０の第２の出力は、動き補償器１９０の第２の入力と信号通信するように結合される。動き補償器１９０の出力は、加算結合部１１０の反転入力と信号通信するように結合される。

図２を参照すると、高速サーチ・ブロック・マッチング動き推定に従ってイメージ・ブロックのためのビデオ信号データを符号化する例示的な処理が概ね参照符号２００により示されている。この処理は、制御を入力ブロック２１２に受け渡す開始ブロック２１０を含んでいる。入力ブロック２１２は、実質的に圧縮されていないイメージ・ブロック・データを受信し、制御を機能ブロック２１４に受け渡す。機能ブロック２１４は、高速サーチ・ブロック・マッチングを実行し、現在のピクチャ・ピクセルを正規化（例えば、絶対値の和（ＳＡＤ）、平均二乗誤差（ＭＳＥ））したものと、参照ピクチャ・ピクセルを同じく正規化したものとの比較に従って、最適でないサーチ・ポイントを除外する。機能ブロック２１４は、制御を機能ブロック２１６に受け渡し、機能ブロック２１６は、イメージ・ブロック・データと特定の参照ピクチャとの間の差に対応する動きベクトルを計算し、制御を機能ブロック２１８に受け渡す。機能ブロック２１８は、動きベクトルに応答して特定の参照ピクチャを動き補償し、制御を機能ブロック２２２に受け渡す。

機能ブロック２２２は、実質的に圧縮されていないイメージ・ブロック・データから動き補償された参照ピクチャを差し引き、制御を機能ブロック２２４に受け渡す。次に、機能ブロック２２４は、実質的に圧縮されていないイメージ・ブロック・データと動き補償された参照ピクチャとの差の信号を特定の参照ピクチャの対応する指標と共に符号化し、制御を終了ブロック２２６に受け渡す。

次に図３を参照すると、イメージ・ブロックのためのビデオ信号データを復号化する例示的な処理が概ね参照符号３００により示されている。この処理は、制御を入力ブロック３１２に受け渡す開始ブロック３１０を含んでいる。入力ブロック３１２は、イメージ・ブロックの圧縮されたデータを受信し、制御を入力ブロック３１４に受け渡す。入力ブロック３１４は、少なくとも１つの参照ピクチャ指標をイメージ・ブロックのためのデータと共に受信する。各参照ピクチャ指標は、特定の参照ピクチャに対応する。入力ブロック３１４は、制御を機能ブロック３１８に受け渡す。機能ブロック３１８は、受信した参照ピクチャ指標の各々に対応する参照ピクチャを取得し、制御を機能ブロック３２０に受け渡す。次に、機能ブロック３２０は、取得した参照ピクチャを動き補償し、制御を終了ブロック３２６に受け渡す。

図４に高速サーチ・ブロック・マッチング動き推定を行う際に使用されるビデオ・デコーダが概ね参照符号４００を用いて示されている。ビデオ復号器４００は、可変長復号器（ＶＬＤ：Ｖａｒｉａｂｌｅ Ｌｅｎｇｔｈ Ｄｅｃｏｄｅｒ）４１０を備え、ＶＬＤ４１０は、逆量子化器４２０と信号通信するように結合されている。逆量子化器４２０は、逆変換器４３０と信号通信するように結合される。逆変換器４３０は、加算器または加算結合部４４０の第１の入力端子と信号通信するように結合され、加算結合部４４０の出力は、ビデオ復号器４００の出力を提供する。加算結合部４４０の出力は、参照ピクチャ記憶装置４５０と信号通信するように結合される。参照ピクチャ記憶装置４５０は、動き補償器４６０と信号通信するように結合され、動き補償器４６０は、加算結合部４４０の第２の入力端子と信号通信するように結合される。

実施の際には、フルサーチ（全探索）では、まず、現在のピクチャを重なりのないブロックに分割し、参照ピクチャ内で各々をサーチする。フルサーチは、サーチ・センター（探索中心）の周囲のサーチ領域内の全てのポイントをテストすることにより行われ、最後のポジションが見つけられ、最小のコスト関数を有する。フルサーチ方法は、最適な解決策を得ることができるが、多大な演算コストが必要となる。ビデオ符号化方法においては、サーチ範囲がＳであり、参照ピクチャの数がＲＮ（Ｈ．２６Ｌでは、ＲＮは１５までである）であり、マクロブロック（通常は１６×１６）のブロック・タイプの数がＢＮ（Ｈ．２６Ｌでは、ＢＮは７までである）である場合には、各マクロブロックついて、サーチ・ポイントの合計数は（２Ｓ＋１）＊（２Ｓ＋１）＊ＢＮ＊ＲＮとなるか、または、４Ｓ^２＊ＢＮ＊ＲＮを超えるサーチ・ポイントが存在する。

フルサーチ方法よりも演算スピードを高めるために、本発明の実施の形態と併せて２つの技術が利用される。一方は、データの再利用の技術であり、他方は連続削除の技術である。データの再利用のために、最小サイズのブロック・タイプ（４×４）の差の絶対値の和（ＳＡＤ）の結果が記憶され、この結果は、より大きいサイズのブロック・タイプにより再利用される。従って、各マクロブロックについて、サーチ・ポイントに相当する必要となる計算の数は、４Ｓ^２＊ＲＮとなる。

連続削除アルゴリズム（ＳＥＡ：Ｓｕｃｃｅｓｓｉｖｅ Ｅｌｉｍｉｎａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ）におけるフルサーチを高速化するために、三角不等式として知られる数学的な不等式が使用される。ブロック・マッチングにおいては、例えば、差の絶対値の和（ＳＡＤ）または差の二乗和（ＳＳＤ）をサーチ基準として使用することにより、参照ピクチャからの動き補償された予測値ｃ［ｘ，ｙ］と現在のピクチャ内のオリジナル信号値ｓ［ｘ，ｙ］との間の歪みを測定する。セット（集合）Ｂは、考慮されるブロックの全てのサンプル位置を含んでいる。

ＢがＢ_ｎ個のサブ領域に分割されると仮定する。

とすると、

三角等式は、全てのＢ_ｎに適用され、以下の式が得られる。

上記式において、ＳＡＤでは、ｐ＝１であり、ＳＳＤでは、ｐ＝２である。

ＳＡＤまたはＳＳＤは、ビデオ・コーデックにおける歪み尺度として採用することができる。汎用性を損なうことなく、ＳＡＤは、以下の例示的な説明に使用することができ、等式（２）は、等式（３）において明確に記述される。等式（３）は、絶対値演算子の幾つかを除去することにより簡略化することができる。何故ならば、ビデオ・ピクセル・データ値は、常に正であると想定されるからである。

ＳＥＡは、以下のように記述される。
Ｄｍｉｎが、前にブロック動きサーチにおいて計算された最小の歪み値であると仮定する。

であるならばブロックｃを捨て、そうでないならば、フルサーチを実行する。

（等式（３）の右辺）を計算するオーバーヘッドは、２つの部分に分割することができる。第１の部分は、和ノルム（ｓｕｍ ｎｏｒｍ）

および

を計算することに関する。第２の部分は、等式（３）にあるような和ノルムの差の絶対値の和を計算することに関し、サブ領域のサイズに依存する。複数ブロック・タイプの動き推定については、対称分割が望ましい。サブ領域が４×４であれば、オーバーヘッドは、１つのマクロブロックにつき、約Ｓ^２／４＊ＢＮ＊ＲＮ個のサーチ・ポイントに相当する。サブ領域が２×２であれば、オーバーヘッドは、約Ｓ^２＊ＢＮ＊ＲＮとなる。和ノルムを記憶するのに必要なメモリは約（ＲＮ＋１）＊ピクチャ・サイズとなる。ＳＥＡの効率は、下側の境界がどのぐらいタイトであるかに依存する。オーバーヘッドの影響を補償し、フルサーチのポイントを減少させるために、初期Ｄｍｉｎの決定およびサーチ順が重要となる。

好ましい実施の形態においては、ＳＥＡのための

（等式（３）の右辺）を計算するオーバーヘッドを低減するためにデータの再利用が適用される。

の計算は２つの部分に分割することができる。第１の部分は、和ノルム（ｓｕｍ ｎｏｒｍ）

および

を計算することに関する。第２の部分は、等式（３）にあるような和ノルムの差の絶対値の和を計算することに関する。

より詳細には、

を計算するために、動き補償された参照ピクチャについての和ノルムの

および現在のピクチャについての和ノルム

が計算される。

の計算が記憶され、参照ピクチャ内の異なる候補となる動きベクトルのオフセットのために再利用される。ビデオ・シーケンスにおける後のピクチャが符号化されるとき、現在のピクチャを後のピクチャのための参照ピクチャとして使用する。ここで、現在のピクチャの和ノルムの計算結果を記憶して、別の依存的ピクチャ（ｄｅｐｅｎｄｅｎｔ ｐｉｃｔｕｒｅ）を符号化する際に現在のピクチャを使用するときに、

として再利用する。従って、本発明のこの実施の形態における和ノルムを計算するオーバーヘッドが、ＲＮ分の１に低減される。

更に、動き推定のために、

のための和ノルムの差の絶対値の和が、異なるブロック・タイプについて、等式（３）にあるように計算される。最小のブロック・サイズのための和ノルムの差の絶対値の計算結果が記憶され、より大きなブロック・タイプのために再利用される。従って、和ノルムの差の絶対値を計算するオーバーヘッドが、ＢＮ分の一に低減される。

ここで、（４）の場合とは別の、最適でないポイントを捨てるためにＳＥＡで使用されるニュー（新）ＳＥＡ（ＮＳＥＡ：Ｎｅｗ ＳＥＡ）と呼ばれる新たな基準が提供される。ＳＥＡにおいては、三角不等式のため、捨てられるポイントは、最小のＳＡＤをとることが数学的に不可能なポイントであり、フルサーチ方法が使用されるときのように同じ動きベクトルが常に選択される。ＮＳＥＡにおいては、もはやこの保証は存在せず、結果として得られる動きベクトルは、フルサーチ方法とは異なり、圧縮されたシーケンスのビットレートが増加する場合がある。

とＤ（ｓ，ｃ）の相関性が高いため、ビットレートの増加は軽微なものになりやすい。しかしながら、ＮＳＥＡでは、サーチの際に捨てられるポイントの数が大いに増加するため、ビデオ符号器の演算量が大幅に低減される。

ＮＳＥＡは以下のように記述される。
Ｄｍｉｎが前にブロック動きサーチにおいて計算された最小の歪み値であると仮定する。

であるならばブロックｃを捨て、そうでないならば、フルサーチを実行する。

（５）において、因数αおよび因数βは、動的に調整され、よりタイトな下側の境界を選定することができ、フルサーチを実行することなく、最適でないサーチ・ポイントを更に除外する。符号化効率を更に改良するために、レート制限付き歪み（ｒａｔｅ‐ｃｏｎｓｔｒａｉｎｅｄ ｄｉｓｔｏｒｔｉｏｎ）が使用される場合もある。即ち、

ＲｍｏｔｉｏｎおよびＲｒｅｆは、それぞれ、符号化動きベクトルおよび参照ピクチャのためのビットである、λｍｏｔｉｏｎおよびλｒｅｆは、それぞれ、グローバル最適化が得られるように、レートおよび歪みのバランスを取るために使用される。（６）におけるレート制限付き歪みは、符号化効率を大幅に改善することを可能とするレート歪み最適化の１つの方法である。

従って、（５）におけるＳＥＡアルゴリズムは、変更可能である。
Ｊｍｉｎが前にブロック動きサーチにおいて計算された最小のレート制限付き歪み値であると仮定する。

であるならばブロックｃを捨て、そうでないならば、フルサーチを実行する。

このアルゴリズムは、良好な初期Ｄｍｉｎ／Ｊｍｉｎおよびサーチ順を使用することにより更に改良する。このような実施の形態の処理を以下に示す。

各予測ピクチャに対し、
等式（３）にあるように現在のピクチャについての和ノルム

を計算し、
予測値（ｐｒｅｄｉｃｔｏｒｓ）の集合Ｐを定義し、
集合Ｐ内のＤ（ｓ，ｃ）／Ｊ（ｓ，ｃ）を調べ、最小値を初期Ｄｍｉｎ／Ｊｍｉｎとし、
サーチ・センターおよびサーチ範囲がステップ３のような初期Ｄｍｉｎ／Ｊｍｉｎを得ることのできる最適予測値を含むように調整し、
動き補償された符号化のための再利用のデータを用いて（５）／（７）に記述されたＮＳＥＡアルゴリズムを適用し、
再構成されたピクチャのための新たな和ノルムを

として計算、記憶する。

本発明は、例示的な高速サーチ・アルゴリズムの実施の形態に制限されない。代替的な実施の形態を当技術分野において公知な他の発見的な高速サーチ・アルゴリズムに直接適用する。何故ならば、和ノルムの計算コストが小さく、結果を再利用することができるため、

を他のアプリケーションにも使用することができるからである。例えば、Ｈ．２６４における動き推定においては、過度に品質を損なうことなく動き補償のための参照ピクチャを選択する高速な方法が望ましい。

とＤ（ｓ，ｃ）との相関性が高いため、ここで、

をどの参照ピクチャが動き補償のために使用されるかを選択するための測定基準として使用することもできる。更に、動きサーチのスピードもサーチ順に依存している。

の増加量に基づいて新たなサーチ順を定義してもよい。従って、特定のポイントで

であれば、後続のサーチ・ポイントを考慮する必要がない。

本発明の各実施の形態における計算の節約は、例えば、サーチ範囲を拡大することや他の使用法のためにより良好なアルゴリズムに適合させることなど、他のアプリケーションにも適用することができる。本発明の各実施の形態は、例えば、Ｈ．２６１、Ｈ．２６３、Ｈ．２６４、ＭＰＥＧ１、ＭＰＥＧ２、およびＭＰＥＧ４など、動き推定を用いる多くの異なるビデオ圧縮規格と共に直接使用することができる。

本発明のこれらの特徴および利点、また、その他の特徴および利点は、本明細書の開示内容に基づいて関連する技術分野における当業者であれば容易に確認することができるであろう。本発明の原理が、ハードウェア、ソフトウェア、ファームウェア、特定用途プロセッサ、またはこれらを組み合わせた様々な形態で実施可能であることが理解できよう。

一実施の形態においては、本発明は、ハードウェアとソフトウェアとを組み合わせることにより実施される。更に、ソフトウェアは、プログラム記憶装置に具体的な形態に実現されたアプリケーション・プログラムとして実施されることが好ましい。アプリケーション・プログラムは、好ましいアーキテクチャーを有するコンピュータに対してアップロードされ、このコンピュータにより実行可能なものであってもよい。好ましくは、コンピュータは、１つ以上の中央処理装置（ＣＰＵ）、ランダム・アクセス・メモリ（ＲＡＭ）、入出力（Ｉ／Ｏ）インターフェースを備えるコンピュータ・プラットフォーム上で実施される。このコンピュータ・プラットフォームは、オペレーション・システム（ＯＳ）とマイクロ命令コードを更に備えるものであってもよい。本明細書において記載された様々な処理および機能は、マイクロ命令コードの一部であってもよいし、アプリケーション・プログラムの一部であってもよいし、これらを組み合わせたものであってもよく、ＣＰＵにより実行されるものでもよい。更に、コンピュータ・プラットフォームには、追加のデータ記憶装置や、印刷機等、周辺機器を接続するようにしてもよい。

更に、添付図面に描かれた構成要素としてのシステム構成要素および方法の幾つかは、好ましくはソフトウェアの形態で実施されるため、システム構成要素または処理機能ブロック間の実際の接続は、本発明の実施の形態のプログラムの仕方により異なるものであることが理解できよう。本明細書の開示内容に基づいて、関連する技術分野の当業者であれば、これらの本発明の実施例、構成例、また、同様の構成例、実施例を考案することも可能であろう。

添付図面を参照して例示的な実施の形態を説明したが、本発明はこのような具体的な実施の形態に限定されるものではなく、関連する技術分野の当業者であれば、このような実施の形態に対し、本発明の範囲または精神を逸脱することなく、様々な変形、改変が可能であることが理解できるであろう。このような変形、改変は全て、付随する請求の範囲に記載された本発明の範囲に含まれるように意図されたものである。

図１は、本発明の原理に従った高速サーチ・ブロック・マッチング動き推定を行うビデオ符号器のブロック図を示す。 図２は、本発明の原理に従った符号化処理のフローチャートを示す。 図３は、本発明の原理に従った復号化処理のフローチャートを示す 図４は、本発明の原理に従った高速サーチ・ブロック・マッチング動き推定を行う際に使用されるビデオ復号器のブロック図を示す。

Claims (20)

1. イメージ・ブロックのためのビデオ信号データを符号化する方法（２００）であって、
   実質的に圧縮されていないイメージ・ブロックを受信するステップ（２１２）と、
   少なくとも１つの特定の参照ピクチャに応答して前記イメージ・ブロックのブロック・マッチングを行い、イメージ・ブロック・ピクセルを正規化したものと参照ピクチャ・ピクセルを正規化したものとの比較に従って最適でないサーチ・ポイントを除外するステップ（２１４）と、
   前記イメージ・ブロックと前記少なくとも１つの特定の参照ピクチャとの差に対応する動きベクトルを計算するステップ（２１６）と、
   前記動きベクトルに応答して前記少なくとも１つの特定の参照ピクチャを動き補償するステップ（２１８）と、
   を含む、前記方法。
2. 前記動きベクトルを計算するステップが、
   サーチ領域内で、前記動きブロックに対する所定のオフセット範囲内の各変位をテストし、イメージ・ブロック・ピクセルを正規化したものと参照ピクチャ・ピクセルを正規化したものとの比較に従って最適でないサーチ・ポイントを除外するステップと、
   動き補償された参照ピクチャとの、前記イメージ・ブロックにおける各ピクセルの、差の絶対値の和、差の二乗和、および平均二乗誤差の少なくとも１つを計算するステップと、
   最小に計算された差の絶対値の和、差の二乗和、または、平均二乗誤差を有するオフセットを前記動きベクトルとして選択するステップと、
   を含む、請求項１に記載の方法（２００）。
3. 前記ブロック・マッチングのステップが、
   現在のピクチャを正規化したものを記憶するステップと、
   前記現在のピクチャが別のピクチャを符号化するための参照ピクチャとして使用されるときに、前記記憶された正規化したものを再利用するステップと、
   を含む、請求項１に記載の方法（２００）。
4. 前記ブロック・マッチングを行うステップが、
   最小のブロック・サイズを正規化したものを記憶するステップと、
   前記記憶された正規化したものを再利用するステップと、
   を含む、請求項１に記載の方法（２００）。
5. イメージ・ブロックのためのビデオ信号データを処理するための方法であって、
   前記方法が請求項１に記載の符号化するステップ（２００）と、
   復号化するステップ（３００）と、
   を含み、
   前記復号化するステップが、
   前記イメージ・ブロックのためのデータと共に、各々が特定の参照ピクチャに対応する少なくとも１つの参照ピクチャ指標を受信するステップ（３１２、３１４）と、
   前記受信した少なくとも１つの参照ピクチャ指標の各々に対応する参照ピクチャを取得するステップ（３１８）と、
   前記取得した参照ピクチャを動き補償して動き補償された参照ピクチャを形成するステップ（３２０）と、
   を含む、前記方法。
6. 前記動き補償された参照ピクチャを前記イメージ・ブロックのためのデータに追加して前記イメージ・ブロックを予測するステップを含む、請求項５に記載の方法（２００、３００）。
7. 前記予測したイメージ・ブロックを将来に取得される参照ピクチャとして記憶するステップを含む、請求項６に記載の方法（２００、３００）。
8. 前記ビデオ信号データがブロック変換係数を含むストリーミング・ビデオ信号データである、請求項５に記載の方法（２００、３００）。
9. 請求項１に記載のビデオ符号器（１００）およびイメージ・ブロックのためのビデオ信号データと前記イメージ・ブロックを予測するための少なくとも１つの特定の参照ピクチャ指標を復号化するビデオ復号器（４００）からなるビデオ・コーデックであって、
   前記復号器は、前記特定の参照ピクチャ指標に対応するブロックを決定するための出力を有する動き補償器（４６０）を含む、ビデオ・コーデック。
10. 前記動き補償器（４６０）と信号通信して前記動き補償器に対して前記特定の参照ピクチャを提供する可変長復号器（４１０）を含む、請求項９に記載のビデオ・コーデック。
11. 前記動き補償器（４６０）が、前記高速サーチ・ブロック動き推定器（１８０）に応答して動き補償された参照ピクチャを提供する、請求項９に記載のビデオ・コーデック（１００、４００）。
12. 前記ビデオ信号データが、ブロック変換係数を含むストリーミング・ビデオ信号データである、請求項９に記載のビデオ・コーデック（１００、４００）。
13. 少なくとも１つの特定の参照ピクチャに対するイメージ・ブロックのためのビデオ信号データを符号化するためのビデオ符号器（１００）であって、
    前記符号器は、前記少なくとも１つの特定の参照ピクチャに対応する動きベクトルを提供する高速サーチ・ブロック動き推定器（１８０）を含み、
    前記動き推定器は、高速サーチ・ブロック・マッチングを実行し、イメージ・ブロック・ピクセルを正規化したものと参照ピクチャ・ピクセルを正規化したものとの比較に従って最適でないサーチ・ポイントを除外する高速サーチ・ブロック・マッチング部を含み、
    前記高速サーチ・ブロック・マッチング部は、前記少なくとも１つの特定の参照ピクチャに応答する出力を有する、前記ビデオ符号器（１００）。
14. 前記高速サーチ・ブロック・マッチング部が、データ再利用部と連続削除部の少なくとも１つを含む、請求項１３に記載のビデオ符号器（１００）。
15. 前記高速サーチ・ブロック・マッチング部が、現在のピクチャを正規化したものを記憶し、現在のピクチャが別のピクチャを符号化するための参照ピクチャとして使用されるときに、前記記憶された正規化したものを再利用するのに適当なデータ再利用部を含む、請求項１３に記載のビデオ符号器（１００）。
16. 前記高速サーチ・ブロック・マッチング部が、最小のブロック・サイズの正規化したものを記憶し、より大きなブロック・サイズのために、前記記憶された正規化したものを再利用するのに適当なデータ再利用部を含む、請求項１３に記載のビデオ符号器（１００）。
17. 前記高速サーチ・ブロック・マッチング部が、正規化を実行するための、差の絶対値の和の計算機、差の二乗和の計算機、および平均二乗誤差の計算機の少なくとも１つを含む、請求項１３のビデオ符号器（１００）。
18. 前記高速サーチ・ブロック動き推定器（１８０）と信号通信して前記少なくとも１つの特定の参照ピクチャおよび対応する特定の参照ピクチャ指標を提供する参照ピクチャ記憶装置（１７０）を含む、請求項１３に記載のビデオ符号器（１００）。
19. 前記参照ピクチャ記憶装置（１７０）と信号通信して前記少なくとも１つの特定の参照ピクチャに対応する前記特定の参照ピクチャ指標を符号化する可変長符号器（１４０）を含む、請求項１８に記載のビデオ符号器（１００）。
20. 前記高速サーチ・ブロック動き推定器（１８０）と信号通信して前記高速サーチ・ブロック動き推定器に応答して動き補償された参照ピクチャを提供する動き補償器（１９０）を含む、請求項１３に記載のビデオ符号器（１００）。

Images