(57)【要約】ビデオ・データの現フレームにおけるデータのマクロブロックの座標と、ビデオ・データの基準フレームにおけるデータの関連するマクロブロックの座標との差を表す動きベクトルを用いて、ビデオ・エンコーダ・システムにおいて高速予測動き検索を実行する方法および装置を提供する。複数の動きベクトル予測子（６２０）を取得する。動きベクトル予測子は、現マクロブロックに可能な動きベクトルの近似を表す。検索パターン（６３０）を規定する。複数の動きベクトル予測子の各動きベクトル予測子の周囲において、検索パターンを用いて検索を行う。次いで、最終動きベクトル（６６０）を決定する。
2005535228.tif 000002
【特許請求の範囲】
【請求項１】
ビデオ・データの現フレームにおけるデータのマクロブロックの座標と、ビデオ・データの基準フレームにおけるデータの関連するマクロブロックの座標との差を表す動きベクトルを用いて、ビデオ・エンコーダ・システムにおいて予測動き検索を実行する方法において、
少なくとも３つの動きベクトル予測子を取得するステップであって、前記動きベクトル予測子が、現マクロブロックに対して可能な動きベクトルの近似を表す、ステップと、
検索パターンを規定するステップと、
前記検索パターンを用いて、前記少なくとも３つの動きベクトル予測子の各動きベクトル予測子の周囲において検索を行うステップと、
最終動きベクトルを決定するステップと、
を含む方法。
【請求項２】
請求項１記載の方法であって、更に、マクロブロック一致の品質を表す差分メトリックを計算するステップを含む、方法。
【請求項３】
請求項２記載の方法において、前記差分メトリックは、絶対差分メトリックの和、および差分メトリックの二乗の和の内の少なくとも１つである、方法。
【請求項４】
請求項１記載の方法において、前記少なくとも３つの動きベクトル予測子は、推定グローバル動きベクトルを含む、方法。
【請求項５】
請求項４記載の方法において、前記推定グローバル動きベクトルは、差分メトリックが指定の閾値未満である先行のフレームにおける全ての最終動きベクトルの平均である、方法。
【請求項６】
請求項４記載の方法において、
先行のフレームにおける最終動きベクトルの各々について差分メトリックを計算し、
前記先行のフレームにおける最終動きベクトルの各々についての前記差分メトリックを、所定の閾値と比較し、
閾値未満の差分メトリックを有する先行のフレームにおける最終動きベクトルの各々に基づいて前記グローバル動きベクトルを決定することによって、前記推定グローバル動きベクトルが決定される、方法。
【請求項７】
請求項１記載の方法において、前記検索するステップは、更に、
前記検索パターンを用いて、前記少なくとも３つの動きベクトル予測子の各動きベクトル予測子の周囲において検索を行うステップと、
所定の閾値よりも高い差分メトリックを有する最良動きベクトルを決定するステップと、
新たな動きベクトル予測子集合の周囲において検索パターンを実行するステップと、
を含む方法。
【請求項８】
請求項１記載の方法において、前記検索するステップは、更に、
前記動きベクトル予測子に対して検索パターンを実行するステップと、
現動きベクトルに対する現差分メトリックを決定するステップと、
前記現動きベクトルを、以前の最少差分メトリックと比較するステップと、
前記現差分メトリックが前記以前の最少差分メトリック未満である場合、新たな最少差分メトリックを設定するステップと、
前記差分メトリックが前記以前の最少メトリックを所定量だけ上回る場合、前記検索パ
ターンを終了するステップと、
を含む方法。
【請求項９】
請求項１記載の方法であって、更に、
差分メトリックを計算するステップと、
予測子動きベクトルと候補動きベクトルとに基づいてバイアスを計算するステップと、
前記差分メトリックと前記バイアスとに基づいて、変更された差分メトリックを決定するステップと、
を含む、方法。
【請求項１０】
請求項１記載の方法において、検索パターンを規定する前記ステップは、更に、垂直方向よりも水平方向により広がる検索パターンを定義するステップを含む、方法。
【請求項１１】
請求項１記載の方法において、前記少なくとも３つの動きベクトル予測子は、ゼロ動きベクトルを含む、方法。
【請求項１２】
請求項１記載の方法において、前記少なくとも３つの動きベクトル予測子は、先行のフレームからの、同一位置にあるマクロブロックの動きベクトルを含む、方法。
【請求項１３】
請求項１記載の方法において、前記少なくとも３つの動きベクトル予測子は、現マクロブロックの左側に位置するマクロブロックの動きベクトルを含む、方法。
【請求項１４】
請求項１記載の方法において、前記少なくとも３つの動きベクトル予測子は、現マクロブロックの上方に位置するマクロブロックの動きベクトルを含む、方法。
【請求項１５】
請求項１記載の方法において、前記少なくとも３つの動きベクトル予測子は、現マクロブロックの右上方に位置するマクロブロックの動きベクトルを含む、方法。
【請求項１６】
請求項１記載の方法において、前記少なくとも３つの動きベクトル予測子は、
現マクロブロックの左側に位置するマクロブロックの動きベクトルと、
現マクロブロックの上方に位置するマクロブロックの動きベクトルと、
現マクロブロックの右上方に位置するマクロブロックの動きベクトルとの、
中間水平座標および中間垂直座標から得られる中間動きベクトルを含む、方法。
【請求項１７】
ブロックに基づく動き推定を用いて、ビデオ・エンコーダ・システムにおいて高速予測動き検索を実行する方法であって、
複数の動きベクトル予測子を決定するステップと、
前記複数の動きベクトル予測子の内の少なくとも１つに対して検索パターンを実行するステップと、
所定の閾値よりも高い差分メトリックを有する最良の動きベクトルを決定するステップと、
新たな動きベクトル予測子集合の周囲において新たな検索パターンを実行するステップと、
を含む方法。
【請求項１８】
請求項１７記載の方法において、新たな検索パターンを実行する前記ステップは、更に、最良の動きベクトルに基づいて、新たな動きベクトル予測子集合の周囲において、新たな検索パターンを実行するステップを含む方法。
【請求項１９】
請求項１７記載の方法において、前記新たな検索パターンは、垂直方向よりも水平方向
に多く偏倚されている、方法。
【請求項２０】
ブロックに基づく動き推定を用いて、ビデオ・エンコーダ・システムにおいて高速予測動き検索を実行する方法であって、
動きベクトル予測子の周囲において検索パターンを実行するステップと、
現動きベクトルに対する現差分メトリックを決定するステップと、
前記現差分メトリックを以前の最少差分メトリックと比較するステップと、
前記現差分メトリックが前記以前の最少差分メトリック未満である場合、新たな最少差分メトリックを設定するステップと、
前記差分メトリックが前記以前の最少メトリックを所定量だけ上回る場合、前記検索パターンを終了するステップと、
を含む方法。
【請求項２１】
ビデオ・データの現フレームにおけるデータのマクロブロックの座標と、ビデオ・データの基準フレームにおけるデータの関連するマクロブロックの座標との差を表す動きベクトルを用いて、ビデオ・エンコーダ・システムにおいて高速予測動き検索を実行する方法であって、
垂直方向よりも水平方向により広がる検索パターンを規定するステップと、
前記規定した検索パターンに基づいて候補検索を実行するステップと、
最終動きベクトルを決定するステップと、
を含む方法。
【請求項２２】
ビデオ・データの現フレームにおけるデータのマクロブロックの座標と、ビデオ・データの基準フレームにおけるデータの関連するマクロブロックの座標との差を表す動きベクトルを用いて、ビデオ・エンコーダ・システムにおいて高速予測動き検索を実行する装置であって、
現画像マクロブロック入力と、
前記現画像マクロブロック入力に結合された高速予測動き検索動き推定回路であって、
動きベクトル予測子記憶回路と、
検索パターン規定回路と、
前記動きベクトル予測子記憶回路と前記検索パターン規定回路とに結合され、少なくとも３つの動きベクトル予測子を検索する回路と、
最終動きベクトル決定回路と、
を含む、高速予測動き検索動き推定回路と、
動きベクトル出力と、
を備える装置。
【請求項２３】
請求項２２記載の装置であって、更に、
前記高速予測動き検索動き推定回路に結合された動き補償回路と、
前記現画像マクロブロック入力に結合され、更に前記動き補償回路に結合された加算器と、
を備える、装置。
【請求項２４】
請求項２３記載の装置であって、更に、
前記加算器に結合された離散余弦変換回路と、
前記離散余弦変換回路に結合された量子化器と、
を備える、装置。
【請求項２５】
請求項２２記載の装置において、前記高速予測動き検索動き推定回路は、更に、グローバル動きベクトル決定回路を含む、装置。
【請求項２６】
請求項２２記載の装置において、前記高速予測動き検索動き推定回路は、更に、キャプチャモード回路を含む、装置。
【請求項２７】
請求項２２記載の装置において、前記高速予測動き検索動き推定回路は、更に、差分メトリックが所定量だけ以前の最少メトリックを上回る場合に検索パターン終了させる回路を含む、装置。
【請求項２８】
請求項２２記載の装置において、前記高速予測動き検索動き推定回路は、更に、絶対差分の変更された和を決定する回路を含む、装置。
【請求項２９】
請求項２２記載の装置において、前記動きベクトル予測子記憶回路は、複数の動きベクトル予測子を格納する、回路。
【請求項３０】
請求項２９記載の装置において前記複数の動きベクトル予測子は、ゼロ動きベクトルを含む、装置。
【請求項３１】
請求項３０記載の装置において、前記複数の動きベクトル予測子は、先行のフレームからの、同じ位置にあるマクロブロックの動きベクトルを含む、装置。
【請求項３２】
請求項３０記載の装置において、前記少なくとも３つの動きベクトル予測子は、
現マクロブロックの左側に位置するマクロブロックの動きベクトルと、
現マクロブロックの上方に位置するマクロブロックの動きベクトルと、
現マクロブロックの右上方に位置するマクロブロックの動きベクトルとの、
中間水平座標および中間垂直座標から得られる中間動きベクトルを含む、装置。
【請求項３３】
ビデオ・データの現フレームにおけるデータのマクロブロックの座標と、ビデオ・データの基準フレームにおけるデータの関連するマクロブロックの座標との差を表す動きベクトルを用いて、ビデオ・エンコーダ・システムにおいて高速予測動き検索を実行する装置を含む移動通信デバイスであって、
現画像マクロブロック入力と、
前記現画像マクロブロック入力に結合された高速予測動き検索動き推定回路であって、
動きベクトル予測子記憶回路と、
検索パターン規定回路と、
前記動きベクトル予測子記憶回路と前記検索パターン規定回路とに結合され、少なくとも３つの動きベクトル予測子を検索する回路と、
最終動きベクトル決定回路と、を含む、高速予測動き検索動き推定回路と、
動きベクトル出力と、
を備える、移動通信デバイス。
【請求項３４】
ブロックに基づく動き推定を用いて、ビデオ・エンコーダ・システムにおいて高速予測動き検索を実行する方法であって、
第１段階において複数の動きベクトル予測子を決定するステップと、
前記第１段階において、前記複数の動きベクトル予測子の内少なくとも１つに対して検索パターンを実行するステップと、
最良の動きベクトル予測子を決定するステップと、
第２段階において、前記最良の動きベクトル予測子の周囲において新たな検索パターンを実行するステップと、
を含む方法。
【請求項３５】
請求項３４記載の方法において、前記新たな検索パターンを、近似した螺旋状のパターンで実行する、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動き推定の分野に関し、特に、ビデオ画像の圧縮に適用される、ブロック毎の動き推定に関する。
【背景技術】
【０００２】
現在、動き検出は、多くのビデオ圧縮技術の重要な要素となっている。動き推定の目的は、ビデオ・シーケンスのフレーム間における時間的冗長性を減少させることである。動き推定アルゴリズムは、１つ以上の以前にコード化した画像フレームまたは今後のフレームを用いて、画像フレームの画像データを予測する。元の画素データと対応する予測画素データとの間で計算上の差を求めることによって、差分画像を計算する。変動が大きい差分画像は、画像フレーム間に時間的冗長性が殆どないか、または全くないことを示す。一方、変動が小さい差分画像は、画像フレーム間に高い度合いの時間的冗長性があることを示す。差分画像が表す画像フレームの時間的冗長性が少ない程、コード化効率を高めることができる。
【０００３】
動き推定アルゴリズムの一種に、ブロックに基づく動き推定アルゴリズムがある。ブロックに基づく動き推定アルゴリズムは、画像データのブロックを単位に動作する。現フレームにおける画像データのブロックを、直前の画像フレームからのデータ・ブロックによって予測する。この動き推定アルゴリズムは、直前の画像フレームから最も良く一致するブロックの位置を指定する、画像データのブロックに対する動きベクトルを出力する。ビデオ圧縮方法では、この動きベクトル情報を圧縮し、圧縮した差分データと共に送信または格納する。
【０００４】
Ｈ．２６３、ＭＰＥＧ−２、およびＭＰＥＧ−４のような国際的なビデオ圧縮標準規格では、動きベクトルを指定するためにシンタックスを設けることによって、ブロック毎の動き推定を可能にしている。これらの標準規格では、特定の動き推定アルゴリズムを必要としない。これらの圧縮標準規格においては、動き推定は、マクロブロックと呼ばれる１６×１６画素の基準ブロック・サイズで行われる。もっと小さい画像領域について動きを推定するために、８×８画素のブロック・サイズで動作することも認められている。
【０００５】
動き推定は、ビデオ・エンコード・システムにおいて最もプロセッサ集約的単元の１つである。計算の複雑さと動きベクトルの効率との間の妥協を見出そうとする既存のブロックに基づく動き推定技術は多数ある。
【０００６】
全検索動き推定（ＦＳＭＥ：ｆｕｌｌ  ｓｅａｒｃｈ  ｍｏｔｉｏｎ  ｅｓｔｉｍａｔｉｏｎ）は、現画像フレーム内のブロックを、直前に処理したフレームの検索枠内にある各画素位置と余すところなく比較する。各画素位置におけるブロック一致度を判定するには、その対応する歪みを測定する。ブロック照合メトリック（ｂｌｏｃｋ  ｍａｔｃｈｉｎｇ  ｍｅｔｒｉｃｓ）によって用いられる典型的な歪み測定は、絶対差（ＳＡＤ：ａｂｓｏｌｕｔｅ  ｄｉｆｆｅｒｅｎｃｅ）メトリックの和である。
【０００７】
【数１】
2005535228.tif 000003
【０００８】
ここで、ＢＣは、現画像フレームにおけるブロック、ＢＰは直前の画像フレームにおけるブロックである。インデックスｍおよびｎは、Ｎ行およびＭ列のブロック内における画素を示す。小さいＳＡＤ値は高いブロック一致度に対応し、大きなＳＡＤ値は低いブロック一致度に対応する。生憎、全検索動き推定は、検索枠が大きくなると、使えなくなる。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
現在では、複雑度が低い数種類の動きアルゴリズムがある。これらのアルゴリズムの全ては、得られる質が低い、または計算の複雑度を十分に低減できないという問題がある。また、比較的複雑度を低く抑えてある程度質を高めた動き推定アルゴリズムもいくつか提案されている。
【００１０】
可能な手法の１つは、ゾーン毎手法である。まず、動きベクトル予測子（ＰＭＶ）を最高一致動きベクトルとして計算する。次に、ＰＭＷを中心としたゾーン・パターンに従って、動きベクトル検索を実行する。これに続いて、ゼロ動きベクトルを中心とした同様のゾーン検索を行う。各ステップ毎に、十分に高い基準が得られた場合に検索を終了する判定がある。生憎、この手法は広い範囲のビデオ・シーケンス全域にわたって一貫して良好な結果を得ることができない。
【００１１】
ＰＭＶＦＡＳＴと呼ばれる動き推定アルゴリズムは、前述のゾーン手法に非常に似通っている。しかしながら、ゾーン検索パターンの代わりに、繰り返しダイアモンド検索パターンを用いる。ある種の基準に応じて、大きなまたは小さなダイアモンド検索パターンを用いることができる。生憎、この手法は、ゾーン手法と比較した場合、非常に似通った結果しか得られない。
【課題を解決するための手段】
【００１２】
ブロックに基づく動き推定を用い、ビデオ・エンコーダ・システムにおいて高速予測動き検索を実行する方法および装置を提供する。この方法は、複数の動きベクトル予測子を取得するステップを含み、動きベクトル予測子は、現マクロブロックに対して可能な動きベクトルの近似を表すことができる。また、この方法は、検索パターンを規定するステップと、この検索パターンを用いて、複数の動きベクトル予測子の各動きベクトル予測子の周囲において検索を行うステップと、最終動きベクトルを決定するステップを含む。
【発明を実施するための最良の形態】
【００１３】
本発明は、広い範囲のビデオ・シーケンスにわたって、性能の向上をもたらす。数々の改良および新たなアルゴリズムの革新の結果、品質の向上が得られた。実際、数々のビデオ・シーケンスで平均すると、本発明は、達成したビデオ圧縮効率に関して、従来の全検索アルゴリズムをも凌駕する。
【００１４】
従来技術において用いられていた方法は全て、ブロック照合の最適化に焦点を当てていたのに対し、本発明は、効果の中でもとりわけ、ビデオ・シーケンスをエンコードするのに必要なビット数を明示的に考慮することができる。また、本発明は、実生活におけるビデオキャプチャにおいて見られる、動きの性質を利用することもできる。
【００１５】
現在、ワイヤレスの市場の成長によって、ハンドヘルド・デバイスにビデオ・エンコード技術を利用できるようにすることが一層求められるようになろう。これらのデバイスの殆どは、動き推定の集中的計算を実行する処理能力を有していない。したがって、本発明が提供する高品質で複雑でない動き推定アルゴリズムは、かかるデバイスにおいて非常に有用となることができる。
【００１６】
一実施形態によれば、本発明は２段階で実行することができる。第１段階では、数個の予測動きベクトルを考慮することができ、固定の検索パターンを用いて、候補の各々の周囲において検索を実行することができる。第１段階の間に、高い一致度を達成する可能性がないことがわかった場合、あらたな候補動きベクトル集合を選択することができ、新たな検索を実行することができる。これは、場面に現れるい任意の新しい物体の動きを捕捉するために行うことができる。第２段階では、第１段階の最良の結果を考慮することができ、移動、重み付け、螺旋状検索パターンを用いた新たな検索を実行して、最良のブロック一致に到達することができる。
【００１７】
図１は、一実施形態によるビデオ・エンコーダのためのビデオ圧縮システム１００のブロック図の一例である。ビデオ圧縮システム１００は、高速予測動き検索動き推定回路１１０、動き補償回路１１５、加算器１２０、離散余弦変換回路（ＤＣＴ）１２５、量子化器１３０、可変長コード（ＶＬＣ）エンコーダ１３５、逆量子化器１４０、逆離散余弦変換回路（ＩＤＣＴ）１４５、別の加算器１５０、および先行フレーム回路１５５を含むことができる。
【００１８】
動作において、１つ以上の以前に処理した画像フレームを用いて、現画像フレームからの画像データのブロックに対して動き推定を計算する。動き推定回路１１０は、処理したブロックに対応する動きベクトルを出力する。動き補償回路１１５は、計算した動きベクトルを用いて、先行のフレームから予測ブロックを形成する。加算器１２０によって、現画像フレームから予測画像データを減算することによって、差分画像を計算する。ＤＣＴ回路１２５を用いて、この差分画像を変換する。動き推定回路１１０および動き補償回路１１５は画像フレーム間の時間的冗長性を低減するように作用するのに対して、ＤＣＴ回路１２５は１フレーム内の空間的冗長性を低減するように作用する。その後、ＤＣＴ係数は、量子化器１４０による精度の低下を受ける。量子化器１４０は、数値的損失を招くが、圧縮度を高める。量子化されたＤＣＴ係数は、次に、ＶＬＣエンコーダ１３５によってエンコードされ、動きベクトルと共に、圧縮ビデオ・ビットストリーム内において送信される。ローカル復元ループは、逆量子化器１４０、ＩＤＣＴ１４５、および加算器１５０によって構成される。逆量子化器１４０は、ＤＣＴ係数を復元する。ＩＤＣＴ１４５は、ＤＣＴ係数を空間ドメインに逆変換し、量子化した差分画像を形成する。復元されたフレームは、加算器１５０によって、動き補償データを、量子化した差分画像に加算することによって計算される。次いで、この復元したデータを先行フレーム回路１５５に格納し、後続の画像フレームの処理に用いる。
【００１９】
高速予測動き検索動き推定回路１１０の動作は、２段階で構成することができる。第１段階では、数個の動きベクトル予測子の周囲において小規模な検索を行うことができる。これらの動きベクトル予測子（ＭＶＰ：ｍｏｔｉｏｎ  ｖｅｃｔｏｒ  ｐｒｅｄｉｃｔｏｒ）は、他の動きベクトル（ＭＶ）から得ることができる。初期の定義では、ＭＶは、ビデオ・データの現フレームにおけるデータのブロックと、これと照合する基準フレームにおけるデータとのブロックの座標における差である。ＭＶは２つの成分ＸおよびＹを有する。ＭＶの値は、順序付けた対（Ｘ，Ｙ）として記述される。ＭＶＰは、照合を行うときに、最良のＭＶの優れた「推測」として用いられるＭＶである。マクロブロック（ＭＢ）とは、ビデオ・フレーム内におけるデータの１６×１６ブロックである。ＭＢは、異なるサイズのデータのブロック（例えば、８×８、４×８、４×４、１６×８等）を意味することもでき、汎用性を失うことはない。
【００２０】
１つの動きベクトル予測子は、ゼロ動きベクトルに基づくことができる。特定の動きベクトルに基づく動きベクトル予測子は、特定の動きベクトルに等しいものとして、動きベクトル予測子を定義することができる。ゼロ動きベクトルは、（０、０）の座標を有する
動きベクトルである。第２の動きベクトル予測子は、先行のフレームにおいて同じ位置にあったマクロブロックの動きベクトルに基づき得る。
【００２１】
図２は、付加的な動きベクトルを決定するために用いることができる、現マクロブロックに隣接するマクロブロックの位置を示す一例である。このように、第３の動きベクトル予測子は、現マクロブロックの左側にあるマクロブロックの動きベクトルに基づき得る。第４の動きベクトル予測子は、現マクロブロックの上部すなわち上方にあるマクロブロックの動きベクトルに基づき得る。第５の動きベクトル予測子は、現マクロブロックの右上側のマクロブロックの動きベクトルに基づき得る。第６の動きベクトル予測子は、第３、第４、および第５の動きベクトル予測子を基準にすることができる。この中間動きベクトル予測子は、動きベクトルのＸおよびＹ成分には独立して計算することができる。
【００２２】
第７の動きベクトル予測子は、推定したグローバル動きベクトルに基づき得る。このグローバル動きベクトルは、動き推定回路１１０によって、差分メトリックが所要の閾値ＴＨＲＥＳＨ１未満であった、先行のフレームの最終動きベクトル全ての平均として推定される。差分メトリックは、絶対差分メトリックの和、差分メトリックの二乗の和、絶対差分メトリックの変更された和、またはその他の有用なメトリックであればいずれでも可能である。好適な実施形態では、ＴＨＲＥＳＨ１の値は、次のようにして選択した。
【００２３】
ＴＨＲＥＳＨ１＝ＳＡＤ１＋ＯＦＦＳＥＴ
ここで、ＯＦＦＳＥＴは名目上５００に設定することができ、
ＳＡＤ１は次の式で求められる。
【００２４】
【数２】
2005535228.tif 000004
【００２５】
ここで、ｍおよびｎは、画素のインデックスである。ＭおよびＮはブロックの寸法である。例えば、マクロブロックでは、Ｍ＝Ｎ＝１６である。グローバル動きベクトルは、ビデオ・カメラ上の動きセンサ、他のアルゴリズム、またはグローバル動きベクトルを決定するその他のいずれかの手段のような、別の手段によって決定してもよい。
【００２６】
更に、動きベクトル予測子は、同じマクロブロックについて行った動き推定の結果であるが、別の以前にコード化したフレームに基づいて決定することもできる。
このように、動き推定回路１１０は、差分メトリックが指定の閾値よりも低い、先行のフレームにおける最終動きベクトル全ての平均を用いることによって、グローバル動きベクトルを決定することができる。即ち、動き推定回路１１０は、先行のフレームにおける最終動きベクトルの各々について差分メトリックを計算し、先行のフレームにおける最終動きベクトルの各々についての差分メトリックを所定の閾値と比較し、先行のフレームにおける最終動きベクトルの各々と、閾値よりも小さい差分メトリックとに基づいてグローバル動きベクトルを決定することによって、グローバル動きベクトルを決定することができる。
【００２７】
各ＭＶＰの周囲の小領域内における全てのＭＶが検索され得る。次いで、絶対差分の変更和（ＭＳＡＤ）が最低のメトリックを有するＭＶを、第２段階の候補ＭＶとして選択す
ることができる。ＭＳＡＤメトリックは以下のように定義する。
【００２８】
即ち、動き推定回路１１０は、複数の動きベクトル予測子であって、現マクロブロックに対して可能な動きベクトルの近似を表現する動きベクトル予測子を求め、検索パターンを規定し、この検索パターンを用いて複数の動きベクトル予測子の各動きベクトル予測子の周囲において検索し、最終動きベクトルを決定することによって、予測動き検索を行うことができる。更に、動き予測回路は、マクロブロック一致の質を表す差分メトリックを計算することができ、差分メトリックは、絶対差分メトリックの和、差分メトリックの二乗の和、または動き推定に有用なその他のいずれかのメトリックとすることができる。
【００２９】
各ＭＶＰ周囲における検索パターンの一例を図３に示す。図示のように、検索パターンは、垂直方向よりも水平方向に多く広がることができる。これは、殆どの実生活のビデオ・データでは、水平方向における動きや動きの変動が多いという事実を利用し得る。
【００３０】
最初の６つの動きベクトルを評価した後、最良のＭＶが閾値ＴＨＲＥＳＨ２よりも高いＭＳＡＤメトリックを有する場合、第１段階はキャプチャモードに進むことができる。好適な実施形態では、ＴＨＲＥＳＨ２は、以下の式で求められる。
【００３１】
ＴＨＲＥＳＨ２＝４＊ＭＭＳＡＤＡＶＧ、
ＭＭＳＡＤＡＶＧ＝先行のフレームの全ＭＭＳＡＤＳ（即ち、最良のＭＶのＭＳＡＤＳ）の平均
キャプチャモードでは、図４に示すような、追加のＭＶＰを考慮することができる。例えば、８つの点を次のようにすることができる。
（−１２，０）（１２，０）（０，−８）（０，８）（−６，４）（６，４）（６，−４）（−６，−４）
【００３２】
図３に示したのと同じ検索パターンを用いて、ＭＶＰの各々を中心とした検索を実行する。好適な実施形態では、８つのＭＶＰの内４つのみを、マクロブロックについて考慮することができる。最初のマクロブロックには、最初の４つを考慮する。次のマクロブロックには、別の４つのＭＶＰを考慮する、等となる。これを行うと、計算の数を削減することができる。
【００３３】
キャプチャモードの目的は、画面内に素早く入ってきた任意の新たな物体を検出することである。かかる場面では、近隣の動きベクトルに基づくＭＶＰでは失敗する。８つの新たな点を用いると、高い動きベクトル照合度を得る機会が高まる。８つの点は、水平方向を優先するように選択することができる。これは、この方向における動きがより多い場合が多いためである。
【００３４】
このように、動き推定回路１１０は、検索パターンを用いて、複数の動きベクトル予測子の各動きベクトルの周囲において検索し、所定の閾値よりも高い差分メトリックを有する最良の動きベクトルを判定し、新たな動きベクトル予測子集合の周囲において検索パターンを実行することができる。
【００３５】
第１段階では、ＭＶＰを中心とした検索パターンを評価しているとき、早期終止基準を用いて、当該ＭＶＰの検索を終了することができる。ＭＶについて得られたＭＳＡＤが、現在の最少ＭＳＡＤ（ＭＭＳＡＤ）よりも閾値ＴＨＲＥＳＨ３だけ大きい場合、即ち、（ＭＳＡＤｉ＞（ＭＭＳＡＤ＋ＴＨＲＥＳＨ３））の場合、検索は終了される。ＭＳＡＤｉがＭＶＰｉについて得られたＭＳＡＤである場合、ＭＭＳＡＤは、現行のＭＤに対するこの点までに得られた全てのＭＳＡＤ値の内最小値となる。即ち、これが最良のＭＶのＭＳＡＤとなる。好適な実施形態では、ＴＨＲＥＳＨ３の値は、約７６８に選択することがで
きる。
【００３６】
このように、動き推定回路１１０は、動きベクトル予測子に対して検索パターンを実行し、現動きベクトルに対して現差分メトリックを決定し、現差分メトリックを直前の最少差分メトリックと比較し、現差分メトリックが直前の最少差分メトリック未満の場合新たな最少差分メトリックを設定し、差分メトリックが直前の最少メトリックを所定量だけ超過した場合に、検索パターンを終了することができる。
【００３７】
次いで、第１段階において検索した全てのＭＶの中から、最も低いＭＳＡＤメトリックを与えるＭＶを選択し、これが第２段階の開始点となる。
第２段階では、第１段階からの最良のＭＶ（即ち、最も低いＭＳＡＤを与えるもの）を選択し、このＭＶの周囲において検索を実行する。例えば、検索は、図５に示すようなパターンで実行することができる。検索パターンは、中央から開始することができ、番号の順に螺旋状に外側に向かって、図５に示すような順序で行うことができる。より良いＭＶ（即ち、より低いＭＳＡＤを与えるＭＶ）が見つかると直ちに、再度検索パターンの中心を新たなＭＶに変更し、螺旋状検索パターンを再度開始する。このプロセスは、３つの条件の内１つを満たすまで続く。
【００３８】
条件１：ＭＳＡＤが以下の式で求められる閾値ＴＨＲＥＳＨ４未満である。
ＴＨＲＥＳＨ４＝Ａ＊Ｑ＋Ｂ
ここで、Ｑは、現ＭＢにエンコーダが用いる量子化の刻み幅、ＡおよびＢは定数である。好適な実施形態では、Ａ＝８、およびＢ＝０である。
【００３９】
条件２：候補の最大数Ｎが、第２段階において既に考慮されている。好適な実施形態では、Ｎ＝３０である。
条件３：最後のＭ子の候補ＭＶの間に、最少ＭＳＡＤ（ＭＭＳＡＤ）に改善がない。ここで、Ｍは、螺旋状検索パターンにおける最後のＭＶ候補の位置のインデックスの関数である。例えば、検索はインデックス０から開始する。次いで、これは点１、２、３、．．．の周囲において螺旋状に進む。より良いＭＶが発見されたときにはいつでも、螺旋状検索パターンは、この新たなＭＶを中心に置き直し、インデックスは再度０から開始する。このインデックスは、Ｍの値を決定するために用いられる。好適な実施形態では、Ｍは、インデックスに基づく値の集合｛４、４、４、４、４、４、４、４、４、５、５、５、５、６、６、６、６、７、７、７、７、７、７、８、８、８、８、８、９、９｝から選択される。
【００４０】
第２段階終了時における最良のＭＶを、マクロブロックの最良のＭＶとして選択する。このＭＶは、周知の技法を用いて後続の段階において、半画素、１／４画素、またはそれ以上の精度に更に改良することができる。
【００４１】
前述のように、検索パターンは、垂直方向よりも水平方向に広い有効範囲を与えるように選択することができる。
ＭＳＡＤメトリックは、本発明の有用な部分とすることができる。差分メトリックの変更和が好ましい結果を与える間、いずれの差分メトリックも、絶対差分メトリックの和、差分メトリックの変更和、またはその他のいずれかの差分メトリックを必要とする本発明のあらゆる実施形態において、相互交換可能に用いることができる。ＭＳＡＤメトリックは、前述の絶対差分（ＳＡＤ）の和、評価される候補ＭＶ、および予測子動きベクトル（ＰＭＶ）の関数である。一般に、ＰＭＶは、最終動きベクトルのエンコードの間ビデオ・エンコーダによって用いられる。最終動きベクトルは、ＭＶＰとは異なるＰＭＶに関する差分としてエンコードされる。例えば、これは、動きベクトルをエンコードする目的のためにＨ．２６１、Ｈ．２６３、ＭＰＥＧ−１、ＭＰＥＧ−２およびＭＰＥＧ−４において
規定される一意のＭＶとすることができる。ＳＡＤは、前述のように従来の動き推定アルゴリズムに用いられるメトリックである。
【００４２】
所与のＰＭＶを有するマクロブロック、および候補動きベクトルＭＶについて、ＭＳＡＤは、次の式で求められる。
ＭＳＡＤ＝ＳＡＤ＋Ｂｉａｓ（バイアス）
ここで、バイアスは、ＭＶおよびＰＭＶ間の差分メトリックに基づくいずれかの値である。例えば、
ＭＳＡＤ＝ＳＡＤ＋Ｃ＊（｜ＭＶＸ−ＰＭＶＸ｜＋｜ＭＶＹ−ＰＭＶＹ｜）
ここで、ＳＡＤは、先に定義した一致ブロックに用いられる従来のメトリックであり、ＭＶｘおよびＭＶｙは、候補動きベクトルのＸおよびＹ成分であり、ＰＭＶｘおよびＰＭＶｙは、ＰＭＶのＸおよびＹ成分であり、Ｃは定数である。好適な実施形態では、Ｃは約５である。ＰＭＶは、一般に、ＭＢ内の全候補に対して固定のままであるが、ＭＶは変化する。
【００４３】
ＭＳＡＤメトリックは、動き推定アルゴリズムとは独立しており、実際上全てのアルゴリズムにおいて活用することができる。新たなメトリックの効果は、アルゴリズムをＰＭＶ側に向けてバイアスさせることによって、動きベクトルをエンコードするために必要なビット数を減少させ、こうして全体的な圧縮効率を高めることである。
【００４４】
ゼロ動きベクトル、ＭＶ＝（０，０）に対するＭＳＡＤは、特殊な事例
として扱われる。ゼロＭＶは、潜在的に、圧縮効率の改善をもたらすことができる。しかし、これができるのは、得られたマクロブロックが、Ｈ．２６１、Ｈ．２６３、ＭＰＥＧ−１、ＭＰＥＧ−２およびＭＰＥＧ−４標準規格において「非コード化」モード（ｎｏｔ
ｃｏｄｅｄ  ｍｏｄｅ）でコード化されるときだけである。これは、ＳＡＤがある閾値未満の場合にＳＡＤをバイアスすることによって、考慮に入れることができる。
【００４５】
Ｉｆ  （ＳＡＤ＞ＴＨＲＥＳＨ５）
ＭＳＡＤ＝ＳＡＤ−ＴＨＲＥＳＨ６
Ｅｌｓｅ  
ＭＡＳＤ＝ＳＡＤ＋Ｃ＊（｜ＰＭＶｘ｜＋｜ＰＭＶＹ｜）
Ｅｎｄｉｆ  
Ｃ、ＰＭＶｘおよびＰＭＶｙは、前述の通りである。
ＴＨＲＥＳＨ５＝Ｄ＊Ｑ＋Ｅ
ＴＨＲＥＳＨ６＝Ｆ
【００４６】
ここで、Ｑは量子化刻み幅、Ｄ，ＥおよびＦは定数である。好適な実施形態では、Ｄは約１２８、Ｅ＝０、そしてＦは約１００である。
【００４７】
このように、動き推定回路１１０は、差分メトリックを計算し、予測動きベクトルおよび候補動きベクトルに基づいてバイアスを計算し、差分メトリックおよびバイアスに基づいて、変更差分メトリックを決定することができる。
【００４８】
検索プロセスの間、異なるＭＶＰの検索領域が重複し、候補動きベクトルが繰り返される可能性もあり得る。既に評価した全ての候補のログを維持することができ、これらが既に考慮されていれば、これらを無視する。
【００４９】
図示した検索シーケンスは、好適な実施形態において用いられるものである。これらは、広いビデオ・シーケンスの範囲にわたってできるだけ短時間で、高い一致度が得られるように最適化されている。代わりの検索パターンも用いることができる。
【００５０】
開示した発明は、動きベクトルの範囲については何の想定もしていない。動きベクトル値に対するいかなる制約でも、候補に適用することができ、これらが許容範囲を超える場合、破棄することができる。
【００５１】
好適な実施形態の第２段階では、最良に一致する新たな候補ＭＶを得るために、螺旋状検索パターンの中心を決め直すことできる。このように、評価する必要がある次の点は、先験的には知ることができない。評価する次の候補は、潜在的に、現候補の評価結果に左右される。したがって、数個の候補ＭＳＡＤ計算を並行して実施するのは困難になる場合もある（ハードウェア・アーキテクチャによってはそうする必要がある場合もある）。これを軽減するために、検査パターンの中心の決め直しは、１組の候補を評価した後に行うことができ、これにより、この１組を並列に処理することが可能となる。
【００５２】
図６は、一実施形態による動き推定回路１１０の動作を概略的に示すフローチャート６００の一例である。ステップ６１０において、フローチャートは開始する。ステップ６２０において、動き推定回路１１０は、複数の動きベクトル予測子を取得する。ステップ６３０において、動き推定回路１１０は、検索パターンを規定する。ステップ６４０において、動き推定回路１１０は、各動きベクトル予測子の周囲において検索を行う。ステップ６５０において、動き推定回路は、最終動きベクトルを決定する。ステップ６６０において、動き推定回路１１０は、最終動きベクトルを出力する。
【００５３】
図７は、一実施形態による高速予測動き検索動き推定回路１１０のブロック図の一例である。動き推定回路１１０は、動きベクトル予測子記憶回路７１０、検索パターン規定回路７２０、複数の動きベクトル推定回路７３０、および最終動きベクトル決定回路７４０を含むことができる。また、動き推定回路１１０は、グローバル動きベクトル決定回路７５０、キャプチャモード回路７６０、パターン終了回路７７０、および絶対差変更和回路７８０を含むことができる。これらの回路は、先に述べたその同様の機能にしたがって動作する。
【００５４】
別の関連実施形態によれば、高速予測動き検索方法は、２段階で実行することができる。第１段階では、７つのＭＶＰ候補を前述のように計算することができる。次いで、各ＭＰＶ毎に、図３における検索パターンにしたがって全てのＭＶ候補を評価することができ、終止基準を採用して、ＭＶＰから抜け出し、キャプチャモードに進むことができる。次に、キャプチャモードにおける場合、図３における同じ検索パターンおよび同じ終止基準を用いて、図４に示したＭＶＰおよびその周囲において検索を実行することができる。次いで、第２段階において、第１段階からの最良のＭＶを選択することができ、図５に示した螺旋状で検索を実行することができる。より良い一致が得られたときには常に、螺旋の中心を決め直すことができ、インデックスを０にリセットすることができる。最後に、３つの終止基準の内１つが見出されるまでプロセスを継続することができる。
【００５５】
別の関連実施形態によれば、本発明は、ブロックに基づく動き推定を用いて、ビデオ・エンコーダ・システムにおいて高速予測動き検索を実行する方法を提供する。この方法は、複数の動きベクトル予測子を決定するステップと、複数の動きベクトル予測子の内少なくとも１つについて検索パターンを実行するステップと、所定の閾値よりも高い差分メトリックを有する最良動きベクトルを決定するステップと、新たな動きベクトル予測子集合の周囲において新たな検索パターンを実行するステップとを含むことができる。新たな検索パターンを実行するステップは、更に、最良動きベクトルに基づいて、新たな動きベクトル予測子集合の周囲において新たな検索パターンを実行するステップを含むことができる。新たな検索パターンは、垂直方向よりも水平方向に多く偏倚され得る。
【００５６】
別の関連実施形態によれば、本発明は、ブロックに基づく動き推定を用いて、ビデオ・エンコーダ・システムにおいて高速予測動き検索を実行する方法を提供することができる。この方法は、動きベクトル予測子の周囲において検索パターンを実行するステップと、現動きベクトルに対して現差分メトリックを決定するステップと、現差分メトリックをこれまでの最少差分メトリックと比較するステップと、現差分メトリックがこれまでの最少差分メトリック未満である場合、新たな最少差分メトリックを設定するステップと、差分メトリックがこれまでの最少メトリックよりも所定量だけ上回るときに、検索パターンを終了するステップとを含むことができる。
【００５７】
別の関連実施形態によれば、本発明は、ビデオ・データの現フレームにおけるデータのマクロブロックの座標と、ビデオ・データの基準フレームにおけるデータの関連マクロブロックの座標との差を表す動きベクトルを用いて、ビデオ・エンコーダ・システムにおいて高速予測動き検索を実行する方法を提供することができる。この方法は、垂直方向よりも水平方向に広がる検索パターンを規定するステップと、規定した検索パターンに基づいて候補検索を実行するステップと、最終動きベクトルを決定するステップとを含むことができる。
【００５８】
開示した発明は、複雑度を低く抑えつつ、高度の圧縮効率を達成することができる。複雑度は、ＡＰＤＺＳやＰＭＶＦＡＳＴの複雑度と同様にすることができる。しかしながら、達成される品質は高くなる。本業界において容認されている基準である標準的な全検索アルゴリズムと比較した場合、本発明は、固定のビデオ品質については、約０．６％高い圧縮効率を達成する。この数値は、２４回の異なるＱＣＩＦビデオ・シーケンスを平均した後に得られた。
【００５９】
本発明の用途の１つに、ハンドヘルド・デバイス上でのリアル・タイム・ビデオ・エンコーダがある。かかるエンコード・ビデオの典型的な帯域幅は、３２ｋｂｐｓから５１２ｋｂｐｓの範囲であり、典型的なビデオ・フレーム・サイズはＱＣＩＦおよびＣＩＦである。
【００６０】
本発明の方法は、プログラムされたプロセッサ上で実施することが好ましい。しかしながら、ビデオ圧縮システム１００、高速予測動き検索動き推定回路１１０、およびその他のエレメントは、汎用または特殊目的用コンピュータ、プログラムされたマイクロプロセッサまたはマイクロコントローラおよび周辺集積回路エレメント、ＡＳＩＣまたはその他の集積回路、ディスクリート・エレメント回路のようなハードウェア電子回路または論理回路、ＰＬＤ、ＰＬＡ、ＦＰＧＡまたはＰＡＬのようなプログラム可能な論理デバイス等にも実施することができる。一般に、図に示したフローチャートおよび前述の方法を実施可能な有限状態機械が常駐するいずれのデバイスを用いても、本発明のプロセッサ機能を実施することができる。
【００６１】
以上、特定的な実施形態と共に本発明について説明したが、当業者には多くの代替、変更、および変形が明白であることは明らかである。例えば、実施形態の種々の構成要素は、他の実施形態において相互交換、追加、または置換することができる。したがって、ここに明記した本発明の好適な実施形態は、例示であり、限定ではないことを意図している。本発明の主旨および範囲から逸脱することなく、種々の変更を行うことができる。
【図面の簡単な説明】
【００６２】
【図１】一実施形態によるビデオ圧縮システムの例示的なブロック図。
【図２】一実施形態による現マクロブロックの近隣を示す一例を示す図。
【図３】好適な実施形態の第１段階において用いられる検索パターンの一例を示す図。
【図４】好適な実施形態の第１段階においてキャプチャモードで用いる検索パターンの一例を示す図。
【図５】好適な実施形態の第２段階において用いる検索パターンの一例を示す図。
【図６】好適な実施形態による本発明の動作を概略的に示す例示的なフローチャート。
【図７】一実施形態による高速予測動き検索動き推定回路の例示的なブロック図。
【図１】
2005535228.tif 000005
【図２】
2005535228.tif 000006
【図３】
2005535228.tif 000007
【図４】
2005535228.tif 000008
【図５】
2005535228.tif 000009
【図６】
2005535228.tif 000010
【図７】
2005535228.tif 000011
【国際調査報告】
2005535228.tif 000012