(57)【要約】      （修正有）【課題】ビデオエンコードのための全二値表現によるピラミッド構造に基づくモーション推定手段を提供する。【解決手段】ビデオエンコードのためのモーション推定の方法は、３つの二値層を有する二値ピラミッド構造を構築する。状態更新モジュールが、最後のモーションベクタのリピートの発生を登録および更新し、静止状態チェッキングモジュールが、リピートの発生に基づき方法が静止モードかノーマルモードかを決定する。ノーマルモードでは、最初の二値層は、最初のレベルのモーションベクタを決定するために±３のピクセルリファインウィンドウ内をサーチする。サーチ範囲内のあらゆる点をチェックすることにより第二の二値層サーチは第二のレベルのモーションベクタを生成する。±２ピクセルのリファインウィンドウ内の第三の二値層サーチは、第二のレベルのモーションベクタに従って最後のモーションベクタを生成する。【選択図】図１
2004173224.tif 000002
【特許請求の範囲】
【請求項１】
ビデオエンコードにおけるモーション推定のための装置であって、
ビデオ画像を、第一、第二および第三の二値層に変換するための二値ピラミッド構築モジュールと、
最終モーションベクタのリピート発生に基づいて前記装置が静止モードかノーマルモードかを決定する静止状態チェッキングモジュールと、
前記第一の二値層を受け取り、第一のレベルの±３ピクセルのリファインウィンドウで並列ＸＯＲブロックマッチングを実施し、前記ノーマルモードのための第一レベルモーションベクタを生成する、第一レベルサーチモジュールと、
前記第二の二値層を受け取り、６つのモーションベクタ候補を用いて前記ノーマルモードのための第二レベルモーションベクタを決定する、第二レベルサーチモジュールと、
前記第二レベルモーションベクタを受け取り、前記第三のレベルの±２ピクセルのリファインウィンドウで並列ＸＯＲブロックマッチングを実施し、前記ノーマルモードのための最終モーションベクタを生成する、第三レベルサーチモジュールと、
±１ピクセルのリファインウィンドウで並列ＸＯＲブロックマッチングを実施し、前記ノーマルモードのための最終モーションベクタを生成する、ファインチューニングモジュールと、
最終モーションベクタの前記リピート発生を登録および更新する状態更新モジュールと、を含む、モーション推定のための装置。
【請求項２】
前記二値ピラミッド構築モジュールが、フィルタリングモジュール、二値化モジュールおよびデシメーションモジュールを有する、請求項１に記載のモーション推定のための装置。
【請求項３】
前記第一レベルサーチモジュールが、
前記第一の二値層を受け取るデータローディングモジュールと、
前記第一のレベルにおいて±３ピクセルのリファインウィンドウで現在のブロックと参照ブロックとをアラインメントするための、前記データローディングモジュールに結合されたビットアラインメントモジュールと、
差分の最小ビット合計に基づく基準により第一レベルモーションベクタを生成するための並列ＸＯＲブロックマッチングモジュールと、
を備える、請求項１に記載のモーション推定のための装置。
【請求項４】
前記並列ＸＯＲブロックマッチングモジュールが、さらに、テーブルルックアップサブモジュールおよび差分ビット合計サブモジュールを含む、請求項３に記載のモーション推定のための装置。
【請求項５】
前記６つのモーションベクタ候補が、それぞれ、右上ブロック、真上ブロック、左ブロック、前記第一レベルからの現在ブロックの最初のモーションベクタ、時間的に前のブロックのモーションベクタ、およびゼロモーションベクタに対応するモーションベクタである、請求項１に記載のモーション推定のための装置。
【請求項６】
前記第二レベルサーチモジュールが、
前記６つのモーションベクタ候補に基づきモーションベクタオフセットのサーチ範囲を決定するモーションオフセットモジュールと、
前記第二の二値層を受け取り、前記モーションオフセットモジュールから前記サーチ範囲を受け取るデータローディングモジュールと、
現在ブロックと参照ブロックとをアラインメントするビットアラインメントモジュールと、
並列ＸＯＲブロックマッチングモジュールとを含み、
前記ビットアラインメントモジュールおよび前記並列ＸＯＲブロックマッチングが、前記モーションオフセットモジュールによって決定された前記サーチ範囲に対応するモーションベクタをチェックすることにより前記第二レベルモーションベクタを決定する、請求項３に記載のモーション推定のための装置。
【請求項７】
前記第二レベルサーチモジュール内の前記並列ＸＯＲブロックマッチングモジュールが、さらに、テーブルルックアップサブモジュールおよび差分ビット合計（ＳｏＤ）サブモジュールを含む、請求項６に記載のモーション推定のための装置。
【請求項８】
前記第三レベルサーチモジュールが、
前記第三の二値層および前記第二レベルモーションベクタを受け取るデータローディングモジュールと、
前記第三のレベルにおいて±２ピクセルのリファインウィンドウで現在ブロックと参照ブロックとをアラインメントするための、前記データローディングモジュールに結合されたビットアラインメントモジュールと、
差分の最小ビット合計に基づく基準により最終モーションベクタを生成する並列ＸＯＲブロックマッチングモジュールと、
を含む、請求項６に記載のモーション推定のための装置。
【請求項９】
前記第三レベルサーチモジュール内の前記並列ＸＯＲブロックマッチングモジュールが、さらに、テーブルルックアップサブモジュールおよび差分のビット合計（ＳｏＤ）サブモジュールを含む、請求項８に記載のモーション推定のための装置。
【請求項１０】
前記状態更新モジュールが、さらに、先のフレーム内の前記最終モーションベクタのリピート発生を登録するためのカウンタを含み、前記前のフレーム内で同一最終モーションベクタがリピートしたならばカウンタが１だけ増加され、前記カウンタが所定の定数より大きいかまたは別の最終モーションベクタが発見された場合にゼロにリセットされる、請求項１に記載のモーション推定のための装置。
【請求項１１】
前記静止状態チェッキングモジュールは、前記前のフレーム内の前記最終モーションベクタのリピート発生を登録するための前記カウンタが、所定の定数より大きい場合に、前記装置を前記静止モードに設定する、請求項１０に記載のモーション推定のための装置。
【請求項１２】
前記二値ピラミッド構築モジュール、前記第一レベルサーチモジュール、前記第二レベルサーチモジュールおよび前記第三レベルサーチモジュールが、パイプラインアーキテクチャで実現される、請求項１に記載のモーション推定のための装置。
【請求項１３】
前記二値ピラミッド構築モジュール、前記第一レベルサーチモジュール、前記第二レベルサーチモジュールおよび前記第三レベルサーチモジュールが、シストリックアレイによって実現される、請求項１に記載のモーション推定のための装置。
【請求項１４】
前記第一レベルサーチモジュール、前記第二レベルサーチモジュールもしくは前記第三レベルサーチモジュールが、
現在ブロックの二値データを格納する第一の格納ユニット、
前記第一の格納ユニットに結合された遅延回路、
参照ブロックの二値データを格納する第二の格納ユニット、
前記第二の格納ユニットからデータを受け取るオンチップメモリモジュール、および
前記オンチップメモリモジュールに結合されかつ複数の出力を提供するマルチプレクサとを有するサーチ回路と、
各シストリックセルが前記遅延回路からのデータを受け取るための第一の入力を有しかつ第一のシストリックセルを除く１つの行の各シストリックセルが同一行における前のシストリックセルの出力に結合された第二の入力を有する、シストリックセルの複数の行を有する二次元シストリックアレイとを含み、
シストリックセルの各行の第一のシストリックセルが前記マルチプレクサの出力に結合された第二の入力を有する、請求項１に記載のモーション推定のための装置。
【請求項１５】
各シストリックセルが、
デコーダと、
前記デコーダの入力に結合された出力、前記シストリックセルの第一の入力に接続された第一の入力、および前記シストリックセルの出力に接続された第二の入力を有するＸＯＲユニットと、
前記第二の入力と前記シストリックセルの出力の間に接続された第一の遅延ユニットと、
第二の遅延ユニットと、
前記デコーダの出力に結合された第一の入力および前記第二の遅延ユニットに接続された出力とを有する合計ユニットと、
前記第二遅延ユニットと、前記合計ユニットへの第二の入力の間の接続を制御するスイッチユニットとを含む、請求項１４に記載のモーション推定のための装置。
【請求項１６】
ビデオエンコードのためのモーション推定の方法であって、
ビデオ画像を第一、第二および第三の二値層に変換することによって二値ピラミッドを構築するステップ（ａ）と、
最終モーションベクタのリピート発生に基づいて前記方法が静止モードかノーマルモードか決定するステップ（ｂ）と、
±１ピクセルのリファインウィンドウで並列ブロックマッチングを実施しかつ前記方法が前記静止モードの場合には最終モーションベクタを生成するステップ（ｃ）と、
前記第一のレベルにおいて±３ピクセルのリファインウィンドウで前記第一の二値層で並列ＸＯＲブロックマッチングを実施しかつ前記方法が前記ノーマルモードの場合には第一レベルモーションベクタを生成することによって第一レベルを実行するステップ（ｄ）と、
６つのモーションベクタ候補に従って第二の二値層で第二レベルサーチを行い、前期方法がノーマルモードの場合には第二レベルモーションベクタを決定するステップ（ｅ）と、
前記第二レベルモーションベクタに従って前記第三の二値層で第三レベルサーチを実行し、第三レベルにおいて±２ピクセルのリファインウィンドウで並列ＸＯＲブロックマッチングを実施し、前記方法がノーマルモードの場合に最終モーションベクタを生成するステップ（ｆ）と、
最終モーションベクタの前記リピート発生を登録および更新するステップ（ｇ）と、
を含むモーション推定のための方法。
【請求項１７】
前記ステップ（ａ）がフィルタリング、二値化およびデシメーションを含む、請求項１６に記載のモーション推定の方法。
【請求項１８】
前記ステップ（ｄ）が、最小ビット差分に基づく基準により並列ＸＯＲブロックマッチングを用いて前記第一のレベルにおいて±３ピクセルのリファインウィンドウで現在ブロックと参照ブロックとをアラインメントすることによって達成される、請求項１６に記載のモーション推定の方法。
【請求項１９】
前記６つのモーションベクタ候補が、それぞれ、右上ブロック、真上ブロック、左ブロック、前記第一レベルからの現在ブロックの最初のモーションベクタ、時間的に前のブロックのモーションベクタ、およびゼロモーションベクタに対応するモーションベクタである、請求項１６に記載のモーション推定の方法。
【請求項２０】
前記ステップ（ｅ）が、
前記６つのモーションベクタ候補に基づいてモーションベクタオフセットのサーチ範囲を決定するステップ（ｅ１）と、
差分の最小ビット合計に基づく基準でＸＯＲブロックマッチングを用いて前記サーチ範囲内のチェックポイントに対応するモーションベクタをチェックすることによって前記第二レベルモーションベクタを決定するステップ（ｅ２）と、
を含む、請求項１６に記載のモーション推定の方法。
【請求項２１】
前記ステップ（ｆ）が、差分の最小ビット合計に基づく基準で前記最終モーションベクタを生成するために並列ＸＯＲブロックマッチングを用いて前記第三レベルにおいて±２ピクセルのリファインウィンドウで現在ブロックと参照ブロックをアラインメントすることによって達成される、請求項１６に記載のモーション推定の方法。
【請求項２２】
前記ステップ（ｇ）が、先のフレーム内の前記最終モーションベクタのリピート発生を登録するためのカウンタを用い、前記前のフレーム内で同一最終モーションベクタがリピートしたならばカウンタが１だけ増加され、前記カウンタが所定の定数より大きいかまたは別の最終モーションベクタが発見された場合にゼロにリセットされる、請求項１６に記載のモーション推定の方法。
【請求項２３】
前記先のフレーム内の前記最終モーションベクタのリピート発生を登録するための前記カウンタが、所定の定数より大きい場合に、前記方法が前記静止モードである、請求項２２に記載のモーション推定の方法
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、広くはビデオエンコードのためのモーション推定（ｍｏｔｉｏｎ  ｅｓｔｉｍａｔｉｏｎ）に関し、より詳細には、ビデオエンコードのための全二値表現によるピラミッド構造に基づくモーション推定に関する。
（発明の背景）
【０００２】
マルチメディア組み込みシステムでは、ビデオエンコードモジュールは、いくつかの主要なコンポーネント、例えば、ＤＣＴ（離散コサイン変換）／ＩＤＣＴ（逆ＤＣＴ）、ＭＥ（モーション推定）、モーション補償、量子化、逆量子化、ビットレート管理およびＶＬＣ（可変長符号化）エンコードを含んでいる。その中で、計算量的に最も高価な部分はモーション推定である。一般に、モーション推定は、最適化されたシステムについては、およそ全体の計算能力の５０％をとる。従って、モーション推定のいっそうの最適化は、埋め込みマルチメディアシステム中の実時間ビデオエンコードについてのコストの削減が重要である。
【０００３】
スリーステップサーチ、２−Ｄ対数サーチ、共役ディレクショナルサーチ、遺伝的アルゴリズムサーチ、ダイヤモンドサーチ、またインテグラルプロジェクション（Ｉｎｔｅｇｒａｌ  Ｐｒｏｊｅｃｔｉｏｎ）を特徴ベースのブロックモーション推定や、交互ピクセルデシメーションパターンを用いたサブサンプルモーションフィールド推定を含む多くの高速サーチアルゴリズムが開発されてきた。
これらの様々なサーチアプローチは、モーションベクタの精度を犠牲にして複雑さを削減し、これにより、伝統的な全サーチアルゴリズムのグローバルミニマムと比べて、平均絶対差分（ＭＡＤ）のローカルミニマムの選択だけをもたらす。
【０００４】
伝統的なマルチ解像度のモーション推定の技術は、より低い解像度からより高い解像度層まで極めて狭いウインドウを用いてサーチを実施する。モーションベクタは各々の層で次第にリファインされるが、サーチエリアは、非常に低い複雑さをもつフルサーチのそれと同等であった。複雑さをさらに削減するため、伝統的な二値モーション推定のアルゴリズムは、ビットの深さを削減することにより、計算の複雑さおよびバス帯域幅の両方を減らす。二値のピラミッド構造を基に、Ｓｏｎｇ等は次の文献で示されているように、ＦＢＰＭＥと略する高速二値モーション推定のアルゴリズムを開示した。
【非特許文献１】
Ｓｏｎｇ他、「Ｎｅｗ  ｆａｓｔ  ｂｉｎａｒｙ  ｐｙｒａｍｉｄ  ｍｏｔｉｏｎ  ｅｓｔｉｍａｔｉｏｎ  ｆｏｒ  ＭＰＥＧ２  ａｎｄ  ＨＤＴＶ（Ｈｉｇｈ  Ｄｅｆｉｎｉｔｉｏｎ  Ｔｅｌｅｖｉｓｉｏｎ）  ｅｎｃｏｄｉｎｇ」、“ＩＥＥＥ  Ｔｒａｎｓ．ｏｎ  Ｃｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ  ｆｏｒ  Ｖｉｄｅｏ  Ｔｅｃｈｎｏｌｏｇｙ”第１０巻、第７号の１０１５頁〜１０２８頁、２０００年１０月
【０００５】
ＦＢＰＭＥのピラミッド構造は、一番小さい解像度（最小画像）の１つの整数層および詳細情報を含んだ３つの二値層を含んでいる。ＦＢＰＭＥは、二値層に排他的論理和（ＸＯＲ）ブーリアンブロックマッチングを伴うタイル化されたモーションサーチを行い、かつ整数層にはＭＡＤを行う。ブロックマッチングは、ＭＡＤオペレーションより実施が大いに簡単かつ高速であるＸＯＲオペレーションを用いる。
【０００６】
しかし、ＦＢＰＭＥ構造は整数層を用い、これによりＭＡＤおよびＸＯＲオペレーションの両方を実施するため２つの歪み計算モジュールをもたらすことになる。それには、より大きいコードサイズおよびより複雑なハードウェアが必要である。ＦＢＰＭＥ構造は、フィルター、デシメーション、二値化および補完を含んだより複雑な事前処理も必要である。ＭＡＤおよびＸＯＲの両オペレーションのためのハードウエアの複雑さおよびマルチ層アプローチにおけるより複雑な事前処理は、ハードウエア実施のためのより多くのパワー消費をもたらす。
【０００７】
Ｎａｔａｒａｊａｎ，ＢｈａｓｋａｒａｎおよびＫｏｎｓｌａｎｔｉｎｉｄｅｓにより提唱されたもう１つの伝統的な高速二値モーション推定のアルゴリズムは、伝統的サーチ方式を用いた簡単な一ビット変換に基づく。それは、現在および参照ブロックを導出する単一層動き推定を提供する。しかしながら、その二値表現はいかなる階層構造も用いない。階層構造を採用するときは、より低い解像度の正確な二値表現を得ることがより魅力的なことである。
（発明の概要）
【０００８】
本発明は、伝統的なモーション推定の上述の欠点を克服するためになされた。
主な目的は、ビデオ符号化のための全二値表現によるモーション推定の方法を提供することである。それに応じて、ビデオ画像の３つの二値層を有する二値ピラミッドが構築される。第一の二値層は、第一レベルのモーションベクタを見付けるため、ビット差分の合計に基づいた基準を用いてまずサーチされる。６つのモーションベクタ候補は、第二の二値層のモーションベクタ決定のため使われる。
最後に、第二の層のモーションベクタに応じた第三の二値層でのサーチが、最終的なモーションベクタを生成する。
【０００９】
本発明において、二値ピラミッドの構築は、フィルタ、二値化およびデシメーションを含んでいる。何ら整数層を用いる必要なく全二値エッジ情報を提供すべく、画像の小さなローカルエリア内の空間的変化に基づいて正確なエッジ情報が抽出される。第一レベルのサーチにおいては、このサーチは±３ピクセルのリファインウィンドウ内で実行される。第二レベルのサーチにおいては、本発明はブロック間に存在する空間的−時間的な依存関係に応じて、現在および以前のフレームから６つのモーションベクタ候補を通じて２次元の８×８モーションオフセット（［Ｒｘｍｉｎ，Ｒｘｍａｘ］、［Ｒｙｍｉｎ，Ｒｙｍａｘ］の範囲を計算する。
第二のレベルのリファインウィンドウは、６つのモーションベクタの平均ベクタを中心に寸法（Ｒｘｍａｘ−Ｒｘｍｉｎ＋１）×（Ｒｙｍａｘ−Ｒｙｍｉｎ＋１）のサーチエリアのドミナントレンジをカバーしている。本発明は、第二のレベルのリファインメントのため、（ＲＸｍａｘ−ＲＸｍｉｎ＋１）×（Ｒｙｍａｘ−Ｒｙｍｉｎ＋１）ピクセルを用いてフルサーチＸＯＲブーリアンブロックマッチングを行う。同様に、結果としてのモーションベクタ候補は、次の二値レベルへと渡される。第三のレベルにおいては、このサーチは、±２ピクセルのリファインウィンドウ内で実施される。各々のレベルにおいて、最良のモーションベクタのサーチおよび決定は、ＸＯＲブロックマッチングを使う最小ビット差分合計の基準に基づく。
【００１０】
本発明の他の目的は、ビデオエンコードのためのモーション推定のための装置を提供することである。従って、この装置は、二値ピラミッド構築モジュール、第一レベルサーチモジュール、第二レベルサーチモジュール、第三レベルサーチモジュールを含んでいる。各レベルサーチモジュールは、データローディングモジュール、ビットアラインメントモジュールおよびＸＯＲブロックマッチングモジュールを含んでいる。二値ピラミッド構造は、更に、フィルタリングモジュール、二値化モジュールおよびデシメーションモジュールを含んでいる。各ＸＯＲブロックマッチングモジュールは、更に、テーブルルックアップのサブモジュールおよびビット差分合計（ＳｏＤ）サブモジュールを含んでいる。
【００１１】
本発明のモーション推定は、パイプライン方式で実行できる。このモーション推定の方法は、ｘ８６、インテル社のＭＭＸ技術を使った単一命令複数データ（ＳＩＭＤ）アーキテクチャ、およびシストリックアレーのような汎用アーキテクチャを含んだ様々なアーキテクチャにおいて実施することができる。本発明のパイプライン方式は、３つの主要な共通のモジュールを含み、それらは、組み込まれた構造、コンパクトなストレージ、および並列ブロックマッチングである。
【００１２】
本発明は、ＭＰＥＧ−４基準のビデオエンコーダーを使う。また、性能を示すようブロックマッチングのため１６×１６サイズのマクロブロックを採用する。
実験の結果によれば、低い計算の複雑さおよび低いメモリ帯域幅消費という利益のみならず、サーチ範囲の増大に影響を受けないという利点を有する。システムの設計者は、さらに視覚品質を改善するため、よりよい二値化方法を選定することができる。それに加えて様々な最適化方法を、異なるレジスタサイズを有する特定のプラットフォームのために開発することができる。従って、本発明は、ほかのモーション推定の方法より柔軟性がある。このオペレーションの統計から、本発明のモーション推定は、汎用処理装置システムでのソフトウェアによる実施にとって望ましい。本発明は、ＡＳＩＣ設計についての並列パイプライン実施により実現することができる。また、ハードウェアの設計段階中、シリコン領域、電力消耗および視覚品質の間のトレードオフを可能にする。
【００１３】
本発明の前に述べたおよび他の目的、特徴、態様および長所は、添付図面への適当な参照を伴う以下に提供する詳細な説明を注意深く読むことによりよりよく理解される。
（好ましい実施形態の詳細な説明）
【００１４】
基本的に本発明の全二値モーション推定は、複数のレベルの二値ピラミッド構造および複数のサーチモジュールを含んでいる。推定されるモーションベクタの精度と計算の複雑さの間のトレードオフを達成するため、本発明の好ましい実施形態は、モーション推定のための３レベルピラミッドを含んでいる。以下の説明では、そのレベルを、それぞれ、レベル１、２、３として記載した。
【００１５】
図１は、本発明によるモーション推定のための３レベルの二値ピラミッド構造のブロック図である。図１のモーション推定のための装置は、二値ピラミッド構造１０１、第一レベルサーチモジュール１０３、第二レベルサーチモジュール１０５、第三レベルサーチモジュール１０７、ファインチューニングモジュール１０９、静止状態チェッキングモジュール１１７、および状態更新モジュール１１９を含んでいる。各レベルサーチモジュールは、データローディングモジュール、ビットアラインメントモジュールおよびＸＯＲブロックマッチングモジュールを含んでいる。二値ピラミッド構造１０１は、更に、フィルタリングモジュール１１１、二値化モジュール１１３およびデシメーションモジュール１１５を含んでいる。簡単なデシメーション（間引き）を使うことにより、ＸＯＲブロックマッチングについて３つのレベルで使われるブロックサイズは、それぞれ、４×４、８×８、１６×１６である。ファインチューニングモジュールにおいては、モーションサーチがスキップされ、ＸＯＲブロックマッチングに使われるブロックサイズは１６×１６である。図４から図６は、それぞれの第一、第二、第三のレベルサーチモジュールを図示している。
【００１６】
図２および図３を参照すると、静止状態チェッキングモジュールおよび状態更新モジュールにおいては、１つのカウンタ１２１および３つの比較器１２２、１２３、１２４がある。最初にソースビデオの一番目のフレームを操作するとき、全ブロックについてのカウンタはゼロにセットされる。２つの定数Ｓ１とＳ２（Ｓ２＞Ｓ１＞２）が、静止モードの発生を制御するためおよびビデオの品質を維持するために使われる。各ブロックｉを実行するため、カウンタｉの内容がＳ１より大きいかどうかを静止状態チェッキングモジュールの比較器１２２がチェックする。大きい場合、モーションサーチは静止状態に入り、かつ、ファインチューニングモジュールにおいて±１の範囲内でモーションベクタを微調整する。そうでない（Ｓ１以下の）場合、モーションサ−チはノーマル状態を経て３レベル二値サ−チに移る。モ−ション推定後、状態更新モジュールにおいて現在のフレームｊの各ブロックｉの最終モーションベクタと、現在ブロックと座標が同じである前のフレームｊ−１のブロックｉの格納されたモーションベクタとが一致するかどうを、比較器１２３がチェックする。２つのモーションベクタが同じ場合、比較器１２４はカウンタｉの内容がＳ２より小さいかどうかチェックする。Ｓ２より小さい場合、カウンタｉ１２１は１だけ増加される。そうでない場合、カウンタｉ１２１はゼロにリセットされる。同じステップが、現在のフレームのあらゆるブロックに対して適用される。同じカウンタ１２１が図２と図３で使われることに留意されたい。
【００１７】
計算の複雑さをさらに削減するため、各マクロブロックについてモーションベクタのリピート発生を登録するためにオプションのカウンタを用いることができる。モーションベクタが直前の４つのフレームについて同一であり続ける場合、本発明は現在のマクロブロックが静止であるとみなし、モーションサーチをスキップし、図１のファインチューニングモジュール１０９により±１のより小さなサーチ範囲内でのリファインメントのみを行う。全二値表現、ＸＯＲオペレーション、およびより小さいサーチウィンドウにより、モーション推定のスピードは、再構築した画像の品質のわずかな損失のみで改善することができる。
【００１８】
図４を参照すると、第一レベルサーチモジュールは、データローディングモジュール２０１、ビットアラインメントモジュール２０３、並列ＸＯＲブロックマッチングモジュール２０５を含んでいる。ビットアラインメントモジュール２０３は、±３のピクセルのリファインウィンドウを有する。図５を参照すると、第二レベルサーチモジュールも、データローディングモジュール３０１、ビットアラインメントモジュール３０３、並列ＸＯＲブロックマッチングモジュール３０５およびモーションオフセットモジュール３０７を含んでいる。
【００１９】
図５のモーションオフセットモジュール３０７を参照すると、レベル２の微調整サーチに入る前、第一レベルサーチおよび前のフレームから推定される６つのモーションベクタ候補を用いて、モーションオフセットモジュールは、あらゆる８×８ブロックについて二次元モーションオフセットの（［Ｒｘｍｉｎ，  Ｒｘｍａｘ］，［Ｒｙｍｉｎ，Ｒｙｍａｘ］）の範囲を計算する。導出されたオフセットに基づき、ビットアラインメントモジュール３０３は、（［Ｒｘｍｉｎ，  Ｒｘｍａｘ］，［Ｒｙｍｉｎ，Ｒｙｍａｘ］）のピクセルリファインウィンドウを有する。
【００２０】
図６を参照すると、第三のレベルサーチモジュールは、データローディングモジュール４０１、ビットアラインメントモジュール４０３、並列ＸＯＲブロックマッチングモジュール４０５を含んでいる。図４から図６の各並列ＸＯＲブロックマッチングモジュール２０５、３０５および４０５は、更に、図７に示すように、テーブルルックアップのサブモジュールおよびビット差分合計（ＳｏＤ）のサブモジュールを含む。図１に示す装置で実現するモーション推定の方法は、主な４つのステップを含む。第１のステップは、複数レベル二値ピラミッド構造を構築することである。第２のステップは、±３ピクセルのリファインウィンドウを用いた全サーチＸＯＲブールブロックマッチングを実行することである。第３のステップは、前および現在のフレームからの６つのモーションベクタ候補によりあらゆる８×８ブロックについて範囲（［Ｒｘｍｉｎ，Ｒｘｍａｘ］，［Ｒｙｍｉｎ，Ｒｙｍａｘ］）の二次元モーションオフセットを計算し、かつ、第二のレベルでのりファインメントのため指定エリア内でＸＯＲブールブロックマッチングを実行することである。第４のステップは、最後のレベルで±２ピクセルのリファインウィンドウを用いた全サーチＸＯＲブールブロックマッチングを実行することである。
【００２１】
第１のステップにおいてフィルタ、二値化およびデシメーションを含んでいる３つのサブステップは、３レベルピラミッド構造を作るため、それぞれ、フィルタリングモジュール１１１、二値化モジュール１１３およびデシメーションモジュール１１５により実行される。各元のピクセルは、二値表現を導出するため、隣接輝度ピクセルの平均値から計算されるしきい値と比較される。デシメーション段では、フィルタされた画像が、反復的に次の層を得るため、画像の各寸法において２でサブサンプルされる。
【００２２】
二値ピラミッド構造を構築する間、正確なエッジ情報が、画像の小さいローカル領域の範囲内の空間的変化に基づいて抽出される。本発明では、フィルタリングモジュールの設計が、ＦＢＰＭＥに必要とされる整数層を一切使わず全二値エッジ情報が提供する。空間的変化は、さまざまなフィルタを用いて抽出される。
現在のフレームＦの８ビット表現が新しいフレーム／Ｆｌを作成するために低周波数通過フィルタにかけられるものとする。すなわち、
ＦＬ＝Ｆ、／Ｆｌ＝Ｈ（Ｆ１）  （※ここで「／」は文字の上棒を表す）
ここでｌ＝１．．Ｌ、またＬは使用するピラミッドレベルの総数である。本発明ではＬは３に設定される。／Ｆｌフレームは、ｌ番目のレベルの、同じサイズを有する、元のフレームＦｌのブラー（ｂｌｕｒｒｅｄ：不鮮明な）バージョンである。二値フォーマットの各ピラミッドレベルの構成を図８に示す。
【００２３】
フィルタされた／Ｆｌフレームは、ついで、現在のフレームの二値表現を生成するため使われる。二値表現の構築は、しきい値Ｔｂに基づく。しきい値は、二値フォーマットにおいて正確なエッジ情報を表現するために定義される。エッジ情報は、元の画像およびそのローパス版を微分することにより得ることができる。二値表現を計算するため、本発明は、／Ｆｌフレームから計算された特定のしきい値を使った新しい微分操作を採用し、その／Ｆｌは、近傍領域についての平均空間変異を提供する。従って、ｌ番目のレベルの二値表現は、以下の１ビット変換により計算される。
【００２４】
【数１】
2004173224.tif 000003
【００２５】
デシメーションの最後の手順において、現在のレベルの元の画像からの空間的情報のほとんどを含むローパスフレーム／Ｆｌは、次のピラミッドレベルで入力フレームを作るため使われる。次のレベルを計算するため、フレーム／Ｆｌは互い違いのピクセルごとに間引きされ、以下の式に示すような新しいフレーム／Ｆ１−１を生成する。
【００２６】
【数２】
2004173224.tif 000004
【００２７】
第２のステップにおいて、±３ピクセルのリファインウィンドウを用いた全サーチＸＯＲブールブロックマッチングが、４×４のブロックサイズをもったひとつの最初のモーションベクタ候補を位置決めするために、第一レベルサーチモジュール１０３で実行される。最初のモーションベクタ候補は、８×８のブロックサイズをもっている次の二値レベルに投影される。
本発明のマッチング基準は、ビット差分合計（ＳｏＤ）である。
【００２８】
【数３】
2004173224.tif 000005
【００２９】
ここで、Ｓｌ，ｔ（ｘ，ｙ）はｌ番目のレベルの現在の二値ブロックを示し、Ｓｉ，ｊ−１（ｘ＋ｕ，ｙ＋ｖ）は、現在のブロックの左側トップコーナーから、オフセットを用いた参照二値ブロックを示す。フレームデータが全二値フォーマットされるので、差の計算が簡単なＸＯＲオペレーションを使う。
【００３０】
本発明は、±１６のサーチ範囲のかわりに±３のサーチ範囲により第一のレベルのフルサーチを実施する（ＲＬｖｌ＝Ｒ／４−１、ただし、Ｒは対象サーチ範囲）。より小さいウィンドウで、実際のサーチ範囲の１６倍（ｔｉｍｅｓ）をカバーするモーションベクタが得られる。
【００３１】
第３のステップでは、ブロック間に存在する空間的−時間的依存関係に基づいて、本発明は、上述のＸＯＲマッチング基準を用いて、現在および前のフレームにおいて、６つの候補から最良の８×８モーションベクタを選択する。６つのモーションベクタ候補は、上右（ＵＲ）、上（Ｕ）、および左（Ｌ）、レベル１の最初のモーションベクタ候補、時間的に前（Ｐ）およびセンター（Ｃ）のモーションベクタに対応するモーションベクタである。センターの候補は、ゼロのモーションベクタを意味する。
【００３２】
本発明によれば、各ディメンジョンについての６つの候補の最小および最大オフセットが、図５に示したモーションオフセットモジュール３０７によって第二のレベルのリファインメントウィンドウの境界として選択される。このようにして、モーションオフセットモジュール３０７が、各８×８ブロックごとに２次元モーションオフセットの範囲（［Ｒｘｍｉｎ，Ｒｘｍａｘ］，［Ｒｙｍｉｎ，Ｒｙｍａｘ］）を規定する。第二レベルのリファインメントウィンドウは、６つのモーションベクタの平均ベクタを中心にサイズ（Ｒｘｍａｘ−Ｒｘｍｉｎ＋１）×（Ｒｙｍａｘ−Ｒｙｍｉｎ＋１）のサーチエリアのドミナント範囲をカバーしている。ついで、第二レベルでのリファインメントのために（Ｒｘｍａｘ−Ｒｘｍｉｎ＋１）×（Ｒｙｍａｘ−Ｒｙｍｉｎ＋１）ピクセルウィンドウとのフルサーチＸＯＲブーリアンブロックマッチングを行う。同様に、得られたモーションベクタ候補が、±２のサーチ範囲内でのリファインメントのために第三のレベルに送られる。
【００３３】
第４のステップにおいて、±２のサーチウィンドウによるリファインされたサーチを用い１６×１６ブロックサイズのための最終的なモーションベクタを導出する。本発明において、その最終的なモーションベクタの精度は、第一のステップの二値化プロセスの効率によって影響される。二値化プロセスにおける閾値Ｔｂの使用は、平均の空間的特性およびフィルタリングプロセス後に維持されるエッジ情報に依存する。より高いカットオフ周波数を有するローパスフィルタは、より少ない量の平均空間バリエーションを除去し、上述の二値表現Ｓｉｊ（ｘ，ｙ）におけるより高い周波数成分を保持する。保持された付加的な高周波情報は、すべての二値エッジ情報の精度を増大させうる。実装のためには、符号化効率とフィルタの複雑さとの間でトレードオフを行う必要がある。
【００３４】
本発明のモーション推定がパイプラインアーキテクチャに適していることを示すために、ｘ８６、インテルのＭＭＸ技術を用いたＳＩＭＤアーキテクチャ、およびシストリックアレイなどの汎用アーキテクチャを含むさまざまなアーキテクチャのためのパイプライン処理を達成するために具体的な実施について調査した。単純化するため、すべての実施において、フィルタリングモジュール１１１で用いるフィルタは以下のとおりである。
【００３５】
【数４】
2004173224.tif 000006
【００３６】
本発明のアプローチのフルサーチアプローチを超える効果を検証するために、本発明はシミュレーションのためにｘ８６システムおよびＣ言語を用いる。各レベルの最初の位置および格納ユニットは別個なので、ブロックマッチングのスピードアップは、本発明で開示する方法ではレベルごとに達成される。レベルごとの実施により、ブロックマッチングのために頻繁なデータアクセスを伴う低いメモリ帯域消費が可能となる。
【００３７】
本発明のパイプラインアーキテクチャは、組み込みの構成、コンパクトなストレージ、および並列ブロックマッチングを含む３つの主要な共通モジュールを含む。各モジュールについて、ストレージのサイズと種類は、様々な異なるサイズのデータストレージ／レジスタを提供する、個々のア−キテクチャで規定されるデータビン／レジスタによって制限される。ｘ８６システムの各汎用モジュールを実現するために、Ｃ言語の使用が、ＩＮＴ（Ｉｎｔｅｇｅｒ）（３２ビット）、ＳＩＮＴ（１６ビット）、およびＵＣＨＡＲ（Ｕｎｓｉｇｎｅｄ  Ｃｈａｒａｃｔｅｒ）（８ビット）を含む３つの基本的なデータビンを提供する。ＭＭＸテクノロジを用いたインテルＳＩＭＤアーキテクチャにおいて、最大のデータビンは、各モジュールについての６４ビットＭＭＸのレジスタである。より大きなデータビンが利用可能でないなら、この種のアーキテクチャについての最適化プロセスはｘ８６アーキテクチャのそれと類似する。処理ユニット間のメモリ帯域幅のさらなる削減および両アーキテクチャの動作カウントの削減のためには、最大のデータビンの使用が、いくつかの連続ブロックの二値表現をパックした方法で格納するには好ましい。
【００３８】
第一のモジュール、すなわち３レベル二値ピラミッドの組み込み構成は、フィルタリング、二値化およびデシメーションを含む３つのプロセスからなる。このモジュールを、境界分離および並列処理を含む２つのサブモジュールにおいて高度化することができる。境界分離は、現在のデータがフレーム境界に位置するかどうかの分岐決定をスキップするために用いることができる。第一のサブモジュール、すなわち境界分離は、フレームを９つのリージョン：４つの角、２つの境界行（ｂｏｕｎｄａｒｙ  ｒｏｗｓ）と２つの境界列（ｂｏｕｎｄａｒｙ  ｃｏｌｕｍｎｓ）および、内部（ｉｎｔｅｒｉｏｒ）に分類することによって達成することができる。第二のサブモジュール、すなわち並列処理は、より大きなレジスタにシーケンシャルに格納されたピクセルの複数の組をロードすることによって達成される。図９は、ローパスフレーム／Ｆｌを構成するためにフィルタＨＡを用いる例を示す。ピクセルＦｌ（ｘ，ｙ）は、ｌ番目のピラミッドレベルの処理フレーム内での座標（ｘ，ｙ）のピクセルを示す。シャドーした円は二値化される現行ピクセルをあらわす。フィルタＨＡを用いたローパスフレームの導出は、１の距離を有するチェックポイントを囲む隣接ピクセルの平均値を計算することに等しい。
【００３９】
フレームデータが、ｘ８６システムのＣ／Ｃ＋＋環境下で、ＳＩＮＴ（Ｓｉｇｎｅｄ  Ｉｎｔｅｇｅｒ）と名づけられたデータビンに格納されるものとする。図９は、ペア（［Ｆｌ（０，１），Ｆｌ（１，１）］）３２を処理する例を示す。本発明は、まず、４つの隣接ペア（［Ｆｌ（１，０）Ｆｌ（０，０）］）３２，（Ｆｌ（１，２）Ｆｌ（０，２）３２，（Ｆｌ（０，１）０）３２および（Ｆｌ（２，１）Ｆｌ（１，１）））３２を参照フレームから４つの３２ビットＩＮＴレジスタ、（Ｒ１）３２、（Ｒ２）３２、（Ｒ３）３２、および（Ｒ４）３２にロードする。ロード後、合計および丸めオペレーションを直接実施することができる。これはフレームについてはオーバーフローもアンダーフローもまったく起こらないからであり、また、１６ビットデータビン中に８ビットの幅のデータのみを格納しているからである。合計およびロードの後、結果が３２ビットＩＮＴレジスタ（Ｒ）３２に戻される。
【００４０】
【数５】
2004173224.tif 000007
【００４１】
ここで、値０ｘ０００４０００４は平行に処理されるピクセルを丸める目的で使用される。もし、各ピクセルの閾値を、レジスタ（Ｒ）３２内の値の対を抽出することによって導き出すことができる。
【００４２】
【数６】
2004173224.tif 000008
【００４３】
ここで、「＞＞」は論理右シフトオペレーションを意味する。導出された閾値は二値化のために使用される。この最適化により、構成ステージは、スピードにおいて約３０％改善される。
【００４４】
より大きなビンが利用可能な場合、単一のビンに同時にロードできるピクセルの数に等しい係数だけ、スピードを増やすことができる。ＭＭＸテクノロジを用いたインテルＳＩＭＤアーキテクチャにおいて、ｘ８６アーキテクチャについて上述した境界分離および並列処理により二値ピラミッドを同様に構成することができる。しかしながら、ＭＭＸテクノロジに基づく到達可能な並列性は、６４ビットアーキテクチャによりほぼ倍になる。直前に示した２つの式に基づけば、スピードにおいて６３％改善される。
【００４５】
フレームデータの二値表現は、ピラミッド層のための望ましいコンパクトな格納をもたらす。レベル１では、４×４ブロックの各行は４ビットを占めるのみである。したがって、４αビットの１つのデータビンは、いくつかの続きのα個のブロックの同一行を格納することができる。レベル２では、サイズ（Ｒｘｍａｘ−Ｒｘｍｉｎ＋１）×（Ｒｙｍａｘ−Ｒｙｍｉｎ＋１）の連続したサーチ範囲を６つの候補に基づいて規定する。複数のブロックの、レベル１のブロックとしての単一ビンへのパッキングを第二レベルサーチでは採用する。したがって、両コンピュータアーキテクチャについて、本発明は、レベル２の連続するα個の８×８ブロックの各行をサイズ８αの単一データビンに格納する。レベル１の同じコンセプトを用いて、本発明は、レベル３の連続するα個の１６×１６ブロックの各行をサイズ１６αの単一データビンにパックする。両アーキテクチャのもっとも広いデータビンはブロックマッチングのスピードアップのために使用されるのみであることに留意されたい。
【００４６】
全二値エッジ情報を用いた高速ブロックマッチングのためのブロック図を、ロード、ビットアラインメント、および並列ＸＯＲブロックマッチングを含む図４から図６で示す。ローディングモジュールは、続きのデータの各グループを、メモリアクセスを削減するためより大きいサイズの対応するビンに置く。二値フォーマットのフレームデータがコンパクトにかつ続きで格納されているため、メモリアクセスがシンプルなフェッチ命令となる。したがって、ローディングモジュールは、現在のデータおよびサーチウィンドウの参照データを、それぞれオンチップメモリにロードする。
【００４７】
図４に示すように、レベル１の４つの続きの４×４ブロックの各グループについて、本発明は、現在の４つのブロックの同じ行を特定のＳＩＮＴレジスタに一つ一つロードし、参照ブロックの対応する行をｘ８６アーキテクチャのＩＮＴレジスタに一つ一つ置く。したがって、４つのＳＩＮＴレジスタを後続の並列ブロックマッチングのために用いることができ、スピードをブロック毎マッチング方式に比べて約４倍増やすようにする。同じプロセスを、レベル１で８つの続きの４×４ブロックの各グループを処理するために６４ビットのデータビンを用いることを除き、インテルＳＩＭＤアーキテクチャに採用することができる。したがって、４つのＭＭＸレジスタを、ブロック毎マッチング方法に比べて約８倍の並列性のために用いることができる。
【００４８】
ビットアラインメントモジュールは、サーチウィンドウの参照データと現在のデータを同期する。ビットアラインメント後、（並列の）ＸＯＲブロックマッチング、テーブルルックアップ、およびＳｏＤ比較サブモジュールを、極小のＳｏＤを有するモーションベクタを見つけるために採用する。ＸＯＲオペレーションを、ひづみの計算のために適用する。そのＸＯＲモジュール後にブロックＳｏＤを導出するため、この一時的レジスタにおける１の数を計数することによりテーブルルックアップサブモジュールにおいて、テーブルルックアップオペレーションが適用される。最後に、すべてのＳｏＤを比較することにより、本発明は、ＳｏＤ比較サブモジュールにおいて、４つのブロックのおのおのにつきどのモーションベクタが最良かを別個に決定できる。現在のフレームのすべてのブロックをやりとおす間に、極小ＳｏＤを有する結果モーションベクタが選択される。
【００４９】
それらのアーキテクチャのモーションベクタサーチの最適化プロセスは、いずれも類似しており、６４ビットレジスタがより多くの連続ブロックを同時に処理できることと、ＳＩＭＤアーキテクチャのレジスタで動作するために特殊な命令が用いられること以外は同じである。したがって、各サーチレベルでｘ８６システムの関連するステップのみを、どのようにそのような並列性を達成するかを示すために、詳細に説明する。並列ＸＯＲブロックマッチングモジュールの最適化はレベル１で詳細に説明する。残りのレベルについては、関連する説明は、その類似性のために割愛する。
【００５０】
レベル１では、各ブロックが続きで割り当てられた最初の位置を有するため、本発明は、ｘ８６アーキテクチャで４つのブロックについてのＳｏＤを同時に計算することができ、行ごとの方法（ｒｏｗ−ｂｙ−ｒｏｗ  ｍａｎｎｅｒ）でＭＭＸテクノロジにより８つのブロックについてのＳｏＤを導出することができる。以降の５つのステップは、並列性を達成するための最適化を示す概要である。
【００５１】
ステップ１（ロード）：本発明は、現在のフレームについての４×４サイズの４つの隣接ブロックを同時に処理するので、各行についてのＳｏＤを計算するために１６ビットのデータが必要である。サーチ範囲が±３であることにより、データビンにロードする必要がある参照フレームのデータは、パラレルブロックマッチングについて２２ビット以上であるべきである。
【００５２】
ステップ２（ビットアラインメント）：最初にロードされたデータにつき、本発明は、図４に示したようにレベル１の現在ブロックに対して＋３の水平オフセットと参照ブロックをそろえる。次のチェックポイントに動くため、オーバーラップしたエリアのビットは、１だけレジスタでビットを右シフトすることによって再利用される。
【００５３】
ステップ３（ＸＯＲ）：各正方形が単一ビットを示す行方向マッチングを図４に示す。ＳＩＮＴが１６ビットを含むので、参照レジスタの下位１６ビットのみが、ＸＯＲを用いて現在のデータと比較される。このＸＯＲの結果は、一時的にほかのＳＩＮＴレジスタに格納されて、３つの４ビットシフトと３つの（マスクとしての）ＡＮＤオペレーションが、４つのブロックについてそれぞれＳｏＤを獲得するために必要である。
ステップ４（テーブルルックアップ）：Ｄｉｆｆは、以下で計算されるようにｎ番目のブロックの現在の行の対応するＳｏＤを格納するＳＩＮＴレジスタである。
【００５４】
【数７】
2004173224.tif 000009
【００５５】
各ブロックについての全体的なＳｏＤは、各行についてのＳｏＤの合計と等しい。
ステップ５（ＳｏＤ比較）：すべてのＳｏＤを比較することにより、本発明は、４つのブロックのそれぞれについてどのモーションベクタが最良かを決定することができる。
【００５６】
レベル２では、本発明は、両アーキテクチャにつき、レベル１で用いた類似のパックアプローチにより２つの連続するブロックを３２ビットデータビンに格納する。図５のモーションオフセットモジュール３０７によって見だされる各所定のチェックポイントにつき、レベル２のモーション推定は行毎の方法でブロックの差異を計算する。現在の行につき、本発明は、所定のサーチ範囲内で必要なビットをレジスタにロードするのみならず、現在のモーションベクタによって示される水平オフセットと等しいβビットだけレジスタをシフトすることにより参照データをアラインメントする必要もある。連続するチェックポイントについては、参照データをアラインメントすべく余分のシフト動作が必要となる。レベル２サーチのためのビットアラインメントプロセスを図５に示す。
【００５７】
レベル３では、ｘ８６アーキテクチャのロードおよびビットアラインメントを含むモジュールが以下のように最適化される。ローディングモジュールでは、１つの３２ビットレジスタＡが、ブロックＸおよび先のブロック（Ｘ−１）で、参照データの同一行を格納する。その他の３２ビットレジスタＢは、ブロック（Ｘ＋１）の同一行を格納する。両レジスタは、図１０に示したように指定のサーチウィンドウ内の参照データの部分ビットを含む。参照データをアラインメントするため、水平予測的モーションベクタが最初はたとえば−１０となるよう設定される。レジスタＡが１０だけ左シフトされる一方、レジスタＢは最初のサーチ位置に達するべく６だけ右シフトされる。本発明は、単純なＸＯＲ／ＯＲオペレーションによって２つのレジスタの内容を組み合わせる。最後のステップで、参照ビットは最初のサーチ位置＋２とマッチするようアラインメントされる。本発明が同一行の次の位置に動くと、追加のシフトオペレーションが、マッチングのためのデータペアを同期させるために必要となる。
【００５８】
以下では、シストリックアレイを用いた本発明の実施例を説明する。各ピラミッドレベルについての全二値表現は、Ｎ２バイトからＮ２ビットへと格納を削減し、列もしくは行のベクタのグループとして格納することができる。ベクタは連続的に格納されるので、本発明は、二値情報のパイプライン化および各マッチングプロセスについての処理時間のオーバラップを通じて、情報に効率的にアクセスする。現在のブロックは、サーチプロセスにおいて固定されているので、参照データは、ＡＳＩＣの実現のためにパイプラインの形式でアクセスしかつ伝播することができる。結局、本発明のモーション推定のためのハードウエア実現を設計するためにシストリックアレイを採用することが有利である。
【００５９】
図４、図５、図６において、並列ＸＯＲブロックマッチングモジュールは、レベル１、レベル２、およびレベル３のサーチについて、シストリックアレイで最適化される。図１１は、シストリックアレイを用いてチェックポイントの各行についての並列ブロックマッチングの空間的−時間的表現を示し、ここでは、各太字のドットはプロセッサ素子を表し、ＸＯＲブロックマッチングの空間的−時間的表現が、
【００６０】
【数８】
2004173224.tif 000010
【００６１】
として定義される。図１１に示したＳｌ，ｔ（．，．）は、時間ｔにおける現在のフレームのｌ番目のレベルの二値表現を示す。Ｓｌ，ｔ−１（．，．）は時間的に前のフレームの同一ピラミッドレベルの参照データを表す。ブロックマッチングのため、ブロック次元がＮ×Ｎとして設定され、サーチ範囲は±Ｒである。
現在のブロックから対応する参照ブロックへのモーションベクタは（ｕ，ｖ）によって示される。
【００６２】
現在のブロックおよび参照ブロックの二値データを、行毎の方法でＸＯＲブロックマッチング基準を合計することにより結果としてのＳｏＤを計算できるようプロセッサに転送することができる。現在もしくは参照フレームの各ブロックにつき、各行の二値データがＩ−Ｄベクタとして格納される。現在および参照ブロックからのベクタの各組が、ＳｏＤの計算のために処理要素（ＰＥ）に送達される。現在のブロックはさらに、シストリックアレイを通じて次のＰＥに渡される。結局、チェックポイントの各行につき、本発明は、図１１に示すように（２Ｒ＋１）個の最終的なＳｏＤを得る。
【００６３】
サイズ（２Ｒ＋１）２のすべてのチェックポイントをカバーすべく、本発明は、パイプラインアプローチによりＳｏＤを計算し比較するが、そこでは、各ＰＥが、サーチウインドウ内の同一行の参照ブロックの特定の行を処理する。パイプラインアプローチに基づき本発明はサーチウィンドウ内の各行を時間的に続けて処理することができる。すなわち、本発明は、サーチウィンドウの第一の行に位置するあらゆるチェックポイントをチェックし、かつ、これらのチェックポイントから選択して極小のＳｏＤを有する最良の候補を見つける。パイプラインはアレイ中のすべてのＰＥを用いて後続の２Ｒ個の行を通じてスキャンし、本発明は、すべてのサーチポイントの間で極小のＳｏＤを有する最終的なＳｏＤを得、これにより現在のブロックのための結果としてのモーションベクタがもたらされる。
【００６４】
パイプラインアーキテクチャは、Ｎ２ビットの各ブロックの（２Ｒ＋１）２のＳｏＤを計算するために、（２Ｒ＋１）のＰＥ（Ｐｒｏｃｅｓｓｉｎｇ  Ｅｌｅｍｅｎｔ）、（２Ｒ＋Ｎ）×（２Ｒ＋１）のサイクル、参照データを得るための（２Ｒ＋Ｎ）×（２Ｒ＋１）のメモリアクセス、およびの現在のデータをオンチップメモリからロードするためのＮ×（２Ｒ＋１）のメモリアクセスを必要とし、ここで、追加の２Ｒサイクルはパイプラインの初期化に用いられ、各メモリアクセスは、Ｎビットの参照ブロックとＮビットの現在ブロックをとる。（２Ｒ＋１）のＰＥを構成するためのゲートカウントは、メモリアクセス効率がチャレンジをポーズする間は小さい。
【００６５】
さらにメモリアクセスの遅延を削減するために、本発明は、シストリックアレイを用いた２−Ｄパラレルブロックマッチングアーキテクチャを開示する。２−Ｄアーキテクチャは、同時に参照ウィンドウ内のすべての（２Ｒ＋Ｎ）２ビットをフェッチしてオンチップメモリに入れることにより連続する参照ブロック内でのオーバーラップビットのロードのオーバーヘッドを除去する。（２Ｒ＋Ｎ）ビットの各行について、本発明は、ついでＮ個のシリアルビットの各グループを対応するパイプラインへと多重化する。ブロックの各ペアＲについての全体ＳｏＤがＰＥで計算され、これは図１２に示される詳細な回路により実現される。
【００６６】
図１２は並列２−Ｄブロックマッチングの詳細な実現を示す。図１２の２−Ｄ並列ブロックマッチングのための装置は、ストレージ１モジュール９０１、遅延モジュール９０３、（２Ｒ＋Ｎ）２のＰＥ、マルチプレクサモジュール９０５、オンチップメモリモジュール９０７、およびストレージ２モジュール９０９を含む。ストレージ１；９０１は、現在のブロックの二値データを格納する。遅延モジュール９０３は、現在ブロックの二値データの行を受け取り、１クロックサイクル遅延後にその行を送出する。図１２に示すように（２Ｒ＋Ｎ）の列と（２Ｒ＋Ｎ）の行を有する２−Ｄアレイとして配置された（２Ｒ＋Ｎ）２のＰＥが、現在ブロックから二値データの行（ｒｏｗ）を受信し、並列に複数ビットのＸＯＲオペレーションを実施し、デコーダ９１３を用いて１の数を計算し、最後にＳｏＤとして１の総数を蓄積する。マルチプレクサ９０５は、二値データの（２Ｒ＋Ｎ）ビットを参照ブロックから受け取り各ＮビットをＰＥの各行に配布する。マルチプレクサ９０５によって受け取った（２Ｒ＋Ｎ）ビットはストレージ２；９０９からオンチップメモリ９０７にフェッチされる。
【００６７】
図１２に示したとおり（２Ｒ＋Ｎ）列および（２Ｒ＋Ｎ）行の２−Ｄアレイとして配置された（２Ｒ＋Ｎ）２のＰＥは、さらに、ＸＯＲモジュール９１１、デコーダモジュール９１３、加算モジュール９１５、２つの遅延モジュール９１７，９１８、およびスイッチモジュール９１９を備える。
【００６８】
デコーダ９１３は、各入力データ内の１の数を計算するために用いられる。ラベルＤを有するブロックは、遅延素子である。内側ループの遅延素子に格納されるＳｏＤは、デコーダ９１３からのすべての出力とともに蓄積される。平行にマッチングされたブロックの全体のＳｏＤは、示さない比較器によって比較される。極小のＳｏＤを有するモーションベクタは、サーチエリア内のすべての位置を経た後に発見される。図１２に示すＳｌ，ｔ（．，．）は、時間ｔにおける現在のフレームのｌ番目のレベルの二値表現を表す。Ｓｌ，ｔ−１（．，．）は、時間的に前のフレームｔ−１の同一ピラミッドレベル内の参照データを表す。ブロックマッチングのため、サーチ範囲は、±Ｒである。現在のブロックから対応する参照ブロックへのモーションベクタは（ｕ，ｖ）で示される。デコーダ９１３の隣の遅延素子「Ｄ」は、サーチエリア内の対応する位置の蓄積されるＳｏＤを格納する。
【００６９】
ＰＥは、複数ビットのＸＯＲオペレーションを並列に行い、デコーダを用いて１の数を計算し、そして最後にＳｏＤとして１の総数を蓄積する。ＰＥ、現在のブロック、および参照ブロックの間の関係を図１２のブロック図として表すことができる。各ＰＥへの入力ブロックの寸法は、現在のピラミッドレベルのブロック寸法に関連する。例えば、レベル１ではブロックの寸法は４であるが、レベル３では１６に増加する。２−Ｄの並列アーキテクチャにより、本発明は、値Ｒのサーチ範囲とＮ２ビットの各ブロックのＳｏＤを導出するために、（２Ｒ＋１）２のＰＥ、（２Ｒ＋Ｎ）のサイクル、参照データを得るための（２Ｒ＋Ｎ）のメモリアクセス、およびオンチップメモリから現在のデータをロードするためのＮのメモリアクセスを必要とする。各メモリアクセスは、オンチップメモリから、（２Ｒ＋Ｎ）ビットの参照ブロックおよびＮビットの現在ブロックをフェッチする。１Ｄのパイプラインアーキテクチャと比較すると、スピードはＳｏＤの計算で（２Ｒ＋１）倍で、各参照データはオンチップメモリから一度だけフェッチされ、これはそのビットをシステムにロードするための極小メモリアクセスである。本発明のモーション推定は、各レベルにつき小さなサーチ範囲しか必要としないため、２−Ｄパイプラインアーキテクチャを実現する上でのゲートカウントの増加は、合理的な範囲のままである。本発明は実施例を提供するが、モーション推定のブロック図をＡＳＩＣやＦＰＧＡチップのような物理的ハードウエアにマッピングする際にはより効率的であることが可能である。
【００７０】
図１３，図１４は、伝統的なフルサーチ（「ＦＳ」）およびハードウエアによる加速を伴うおよび伴わない本発明のモーション推定のための、計算の複雑さおよびバス帯域幅を示す。フレームサイズは３５２×２８８で、フレームレートは３０ｆｐｓ（ｆｒａｍｅｓ  ｐｅｒ  ｓｅｃｏｎｄ）である。以降ではまず、２−Ｄシストリックアレイを用いた図４から図６の並列ＸＯＲブロックマッチングモジュールの他の実施形態を伴うか、または伴わないｘ８６アーキテクチャ上の本発明のモーション推定の計算の複雑さの分析を述べる。分析は、単一ブロックがモーションベクタをどのように計算するかと、特定のフレームレートごとの毎秒メモリアクセスとに基づく。Ｗ、Ｈ、±Ｒ、およびＦｒ（ｆｐｓ）の記載は、フレーム幅、フレーム高さ、サーチ範囲、および毎秒フレーム数をそれぞれ表す。ブロックサイズは、１６×１６とするが、これはビデオ圧縮標準で最も普通に用いられるものである。
【００７１】
レベル２での範囲（［Ｒｘｍｉｎ，Ｒｘｍａｘ］，［Ｒｙｍｉｎ，Ｒｙｍａｘ］）のモーション探索による複雑さの簡単な分析のため、最大モーションサーチ範囲を最悪の場合のシナリオとして用いる。全てのフレームの最大モーションサーチ範囲は、各寸法について以下のように求める。現在のシーケンスの各フレームｉの中の各ブロックｊについて、レベル２のサーチのための最大モーションサーチ範囲の限界は、次の通りである。
【００７２】
【数９】
2004173224.tif 000011
【００７３】
各ブロックについて、絶対差分の合計を用いた伝統的なフルサーチ（ＳＡＤ）は、サーチウィンドウ内の全ての４Ｒ２のサーチポイントを処理する必要がある。各位置は１６２×３オペレーションをとり、ここで３つのオペレーションは、各データ対についての１つの減算、１つの絶対値演算、および１つの加算からなる。したがって、「ＦＳ」としてラベルづけされた単一のモーションベクタを得るためのフルサーチの計算の複雑さは、マクロブロックあたりδＦＳ＝３０７２×Ｒ２オペレーションとして近似される。ｘ８６システムにおいて３２ビットレジスタを用いたフルサーチのための理論的な最良ケースのシナリオに基づくと、単一のモーションベクタを得ることは、マクロブロックあたり／δＦＳ＝（１／４）δＦＳ＝７６８×Ｒ２オペレーションとして近似できる。
【００７４】
同一のサーチエリアにつき、「ＡＢＭＥ＿ＨＡ」としてラベルづけされた、２−Ｄシストリックアレイを用いない開示されたアーキテクチャにつきモーションベクタを計算するために必要な全体オペレーションは、マクロブロックあたりδＡＢＭＥ＿ＨＡ＝δｃ＋δＬｖ１＋δＬｖ２＋δＬｖ３となり、ここで、δｃ、δＬｖ１、δＬｖ２およびδＬｖ３は、それぞれ、ピラミッド構成のためのオペレーションカウントおよび二値ピラミッドの各レベルにおけるモーションサーチのためのオペレーションを表す。サイズ４Ｒ２のサーチウィンドウおよびサイズ１６×１６のマクロブロックをマッチングするためのＸＯＲオペレーションにより、レベル１のサーチ範囲は、（Ｒ／２−１）２に削減され、レベル１からレベル３までのブロックサイズは、それぞれ４２、８２、および１６２となる。二値化プロセスは、平均でピクセル当たり４．５オペレーションを必要とする。したがって、二値ピラミッドを構築することは、ブロックあたりδｃ＝（４２＋８２＋１６２）×４．５＝１５１２オペレーションを必要とする。
【００７５】
ブロックマッチングプロセスについては、データ格納テクニックがレベルによって異なるので、各レベルのために必要とされるオペレーションは独立に分析される。レベル１では、４つのＳＩＮＴビンに格納される４つのブロックの各パックが１つのマッチングユニットを形成し、これは４つのブロックが続いて格納される現在の行のデータを含む。４つのＳｏＤの導出を完了するため、サーチウインドウ内のブロックの各行につき１５のオペレーションをとる。１５のオペレーションは、ＸＯＲのための１つのレジスタシフトと、４つのビット的ＳｏＤを抽出するための３つのＡＮＤオペレーションおよび３つのシフトオペレーションと、４つのテーブルルックアップオペレーションと、４つの同時に処理されたマクロブロックのＳｏＤを蓄積するための４つの加算オペレーションとを含む。したがって、各マクロブロックのためのレベル１の全体のオペレーションは、次の通りである。
【００７６】
【数１０】
2004173224.tif 000012
【００７７】
レベル２の計算量的な分析は、レベル１と類似するが、より大きなブロックサイズおよび動的サーチ範囲を有し、現在のフレームおよび前のフレームからの６つのモーションベクタ候補により計算される。レベル２では、２つのＳＩＮＴビンに格納された２つのブロックの各パックがマッチングユニットを形成し、これは、現在の行のデータを含み、２つのブロックは続いて格納される。２つのＳｏＤの導出を完了するため、サーチウインドウ内のブロックの各行について７つのオペレーションがかかる。その７つのオペレーションは、ＸＯＲのための１つのレジスタシフト、２つのビット的ＳｏＤを抽出するための１つのＡＮＤオペレーションおよび１つのシフト動作、２つのテーブルルックアップオペレーション、および同時に処理される４つのマクロブロックのＳｏＤを蓄積するための２つの加算オペレーションを含む。サーチ位置の数は、（ｒｘｍａｘ−ｒｘｍｉｎ＋１）×（ｒｙｍａｘ−ｒｙｍｉｎ＋１）であり８つのＳＩＮＴビンがサイズ８×８の２つのレベル２ブロックのすべての行をカバーする。したがって、レベル２サーチは、ブロック毎に、δＬｖ２＝８×７×（ｒｘｍａｘ−ｒｘｍｉｎ＋１）×（ｒｙｍａｘ−ｒｙｍｉｎ＋１）／２オペレーションを要する。
【００７８】
レベル３の計算量分析は、レベル２と類似するが、より大きなブロックサイズおよび固定したサーチ範囲を有する。サーチ位置の数は２５であり１６個のＳＩＮＴビンが、サイズ１６×１６のレベル３ブロックのすべての行をカバーする。
したがって、レベル３サーチは、ブロック毎にδＬｖ３＝１６×３×２５＝１２００オペレーションを要する。
【００７９】
二値ピラミッドを構築することは、ブロック毎にδＣ＝（４２＋８２＋１６２）×４．５＝１５１２オペレーションを要する。各ブロックについてのレベル１の全体オペレーションの数δＬｖ１は１５×（Ｒ／２−１）２である。レベル２およびレベル３のブロック毎のオペレーションの数δＬｖ２およびδＬｖ３は、それぞれ、２８×（ｒｘｍａｘ−ｒｘｍｉｎ＋１）×（ｒｙｍａｘ−ｒｙｍｉｎ＋１）および１２００となる。したがって、ＡＢＭＥ＿ＨＡにつき必要なオペレーションの総数は、δＡＢＭＥ＿ＨＡ＝δＣ＋δＬｖ１＋δＬｖ２＋δＬｖ３＝２７１２＋１５×（Ｒ／２−１）２＋２８×（ｒｘｍａｘ−ｒｘｍｉｎ＋１）×（ｒｙｍａｘ−ｒｙｍｉｎ＋１）である。
【００８０】
「ＡＢＭＥ＿ＨＡ＿ＨＷ」と呼ばれる、レベル１、レベル２、レベル３での並列ＸＯＲブロックマッチングモジュールのための２−Ｄシストリックアレイの使用は、マクロブロック毎の全体オペレーションを、次のように削減する。
【００８１】
【数１１】
2004173224.tif 000013
【００８２】
δＡＢＭＥ＿ＨＡ、δＡＢＭＥ＿ＨＡ＿ＨＷおよび／δＦＳの値を比較することにより、本発明はフルサーチを凌駕しており、このことは様々なサーチ範囲について図１３，図１４に示した計算の複雑さと整合する。
【００８３】
以下は、現在および参照フレームからデータをロードするための全体メモリ帯域幅を分析する。フルサーチについては、バイト単位の毎秒全体帯域幅消費はζＦＳ＝（ζＦＳ＿Ｃｕｒ＋ζＦＳ＿Ｒｅｆ）×Ｆｒであり、ここでζＦＳ＿ｃｕｒおよびζＦＳ＿Ｒｅｆは、それぞれ現在フレームおよび参照フレームのためのデータにアクセスするためのメモリ帯域幅である。現在のブロックが１６×１６のＵＣＨＡＲビンによりオンチップメモリに同時にロードされるものとする。したがって、サイズＷ×Ｈの現在のフレームのためのデータにアクセスすることは、ζＦＳ＿Ｃｕｒ＝Ｗ×Ｈバイトを要する。
【００８４】
参照ブロックが、（１６＋２Ｒ）２のＵＣＨＡＲビンによりオンチップメモリに同時にロードされるものとする。次のブロックの動くとき、オーバーラップしたエリアのデータは再利用され、必要な帯域幅は、１６×（１６＋２Ｒ）である。したがって、参照フレームからデータを完全にロードすることは、さらなるζＦＳ＿Ｒｅｆ＝Ｈ／１６×［（１６＋２Ｒ）２＋（Ｗ／１６−１）×（１６＋２Ｒ）×１６）］バイトを必要とする。最初の項は、最初のサーチウィンドウを示し、パイプラインの初期化ステージではメモリストールによりより多くのオペレーションがかかる。残りのサーチウィンドウはその前のものとオーバーラップするのでより少ないオペレーションが必要である。
【００８５】
本発明のモーション推定のために、２−Ｄシストリックアレイを用いた、ハードウエア加速を伴なうおよび伴わないｘ８６システムで用いられるバイト単位の全体メモリ帯域幅消費は、それぞれ、ζＡＢＭＥ＿ＨＡ＝（ζＣｕｒ＋ζＬｖ１＋ζＬｖ２＋ζＬｖ３）×ＦｒおよびζＡＢＭＥ＿ＨＡ＿ＨＷ＝（ζＣｕｒ＋ζ’Ｌｖ１＋ζＬｖ２＋ζ’Ｌｖ３）×Ｆｒとなる。項ζＣｕｒは、現在のフレームをロードするための帯域幅消費を示す。残りの項ζＬｖ１、ζ’Ｌｖ１、ζＬｖ２、ζＬｖ３およびζ’Ｌｖ３は参照フレームにアクセスするために必要な帯域幅を示す。
【００８６】
２−Ｄシストリックアレイを用いたハードウエア加速を伴わないｘ８６システムでは、現在のフレームの各ブロックをロードするためのメモリ帯域幅（バイト）は、ζＣｕｒ＝（１／１６＋１／４＋１）×ＨＷ／８〜０．１６４×Ｗ×Ｈである。すでにレジスタにあるデータの再利用性に基づいて、フレーム毎のサーチウィンドウ内の参照データをロードするため各ピラミッドレベルに必要とされるメモリ帯域幅は次の式のようになる。、
【００８７】
【数１２】
2004173224.tif 000014
【００８８】
ここで、レベル２で各フレームに必要とされるメモリ帯域幅の簡単な計算のために、ｘおよびｙの両寸法について、最悪の場合のサーチ範囲が［−３，３］としてセットされる。
【００８９】
レベル１、２および３のＸＯＲマッチングモジュールが２−Ｄシストリックアレイアーキテクチャで実現されると、フレーム毎のサーチウインドウ内の参照データをロードするための必要とされるメモリ帯域幅は、それぞれ、次のようになる。
【００９０】
【数１３】
2004173224.tif 000015
【００９１】
本発明はフルサ−チと比較してバス帯域幅を顕著に削減する。サーチ範囲が増えると、フルサーチのためのメモリ帯域幅が劇的に増えるが、本発明のモーション推定のためのメモリ帯域幅は増加したζＬｖ１およびζ’Ｌｖ１によりわずかだけ増える。さまざまなＲによるフルサーチのメモリ帯域幅の高い感度とは反対に、本発明のモーション推定はサーチ範囲の変化に影響を受けない、というのも、レベル１のフレームサイズが最も小さく、連続するブロックからのデータをより大きなビンに格納できるからである。そのような卓越したパフォーマンスは図１３，図１４に示した観測と整合するものである。
【００９２】
フルサーチを超える本発明のパフォーマンスを示すため、本発明は、ＭＰＥＧ−４基準ビデオエンコーダを用い、ブロックマッチングのためにサイズ１６×１６のマクロブロックを採用する。図１５に示すパフォーマンス比較は、ビデオシーケンス、エンコード条件、さまざまなデシメーションフィルタ、モーション推定アプローチ、およびＰＳＮＲ値単位の再構築されたビデオの視覚品質を含むファクターにもとづいて分析される。
【００９３】
Ｃｏａｓｔｇｕａｒｄ、Ｆｏｒｅｍａｎ、およびＡｋｉｙｏを含むＣＩＦフォーマットによるビデオシーケンスおよびＣｏｎｔａｉｎｅｒおよびＭｏｔｈｅｒ−ＤａｕｇｈｔｅｒをカバーするＱＣＩＦフォーマットによるシーケンスをテストのために用いる。６つのシーケンスは、様々な空間的およびモーションの活量を特徴づける。本発明は、さらに、早い動作対象からなる卓球およびステファン（Ｓｔｅｆａｎ）を含む２つのＣＣＩＲ６０１シーケンスをテストする。より大きいサイズの画像内の早く動いている対象は、本発明のモーション推定のパフォーマンスおよび計算負荷を試験するために採用する。各ソースシーケンスは３００フレームからなる。
【００９４】
エンコード条件に関しては、各シーケンスは、ＭＰＥＧ委員会により推奨された条件下でエンコードされる。目標フレームレートは１０ｆｐｓとして設定され、ビットレートは、様々なシーケンスにつき１０ｋｂｐｓから２Ｍｂｐｓにわたる。正確なモーションベクタを見つけるために、サーチ範囲は各シーケンスにつき±１６であり、サーチ範囲はＣＣＩＲ−６０１シーケンスについては±３２に増やされる。
【００９５】
レベル２サーチのモーションサーチ範囲については、サイズ（［ｒｘｍｉｎ，ｒｘｍａｘ］，［ｒｙｍｉｎ，ｒｙｍａｘ］）＝（［−３，３］，［−３，３］）の範囲が、経験的にはレベル２の十分なモーションベクタを提供し、したがって図１５の複雑さの評価に用いられる。
【００９６】
デシメーションフィルタについては、本発明は、モーション推定の二値化およびコーディング効率に様々なフィルタがどのように影響するかを分析するため３つの２次元（２−Ｄ）フィルタと３つの１Ｄ可分フィルタを用いる。ＨＡ、ＨＢ、およびＨＣとして記載される３つの２−Ｄフィルタは、以下のようになる。
【００９７】
【数１４】
2004173224.tif 000016
【００９８】
フィルタＨＢもしくはＨＣによって抽出されるフレームＳｔ（ｘ，ｙ）はフィルタＨＡによって抽出されるフレームより高い周波数の情報を保持する。
【００９９】
３つの１Ｄフィルタは、２０％、２５％および３０％のナイキスト周波数の別個のカットオフ周波数を有する３つの分離可能な１３タップのハミングフィルタである。フィルタの複雑さをさらに減らすため、その１Ｄフィルタのあらゆるものが、ｋ・２−ｍの形式の係数を有するフェーズリニアＦＩＲフィルタ（Ｆｉｎｉｔｅ  Ｉｍｐｕｌｓｅ  Ｒｅｓｐｏｎｓｅ  Ｆｉｌｔｅｒ）である。Ｍ個のタップを有する１Ｄフィルタ、すなわちＨ＝［ｈ１，ｈ２，．．．，ｈＭ］について、ローパスフレームは、以下のように計算される。
【０１００】
【数１５】
2004173224.tif 000017
【０１０１】
ここで、
【０１０２】
【数１６】
2004173224.tif 000018
【０１０３】
例えば、Ｈ＝［１，４，６，４，１］・２−４の係数を有する５タップフィルタを、シフトおよび加算オペレーションのみにより実現することができる。様々な現代のコンピュータアーキテクチャ上のかかるオペレーションの通常のコストは、１サイクルである。したがって、このタイプのフィルタは、元のフィルタを上回る有意なスピードアップを達成することができるが、ただし、特定のフィルタ設計方法論では設計されない。３つの１Ｄフィルタは、次の通りである。
【０１０４】
【数１７】
2004173224.tif 000019
【０１０５】
図１３，図１４からの複雑さの分析および図１５からのパフォーマンス比較に基づき、フルサーチと比較して、本発明は、低い計算の複雑さおよび低いメモリ帯域幅消費の利益を受けるのみならずサーチ範囲増加の影響を受けないことが分かる。本発明はまた、よりより二値化方法があれば、視覚的品質をさらに改善することができる。この特徴により、柔軟な構成を提供できる。システム設計者は、それらのシステムによって提供される、利用可能なメモリ、計算能力、表示解像度、もしくはデータバス帯域幅によって二値化方法を選ぶことができる。たとえば、無線移動電話の特性は、より少ない計算能力、より低い表示解像度、およびより少ない利用可能メモリを有する。したがって、最も小さいフィルタが、その視覚的品質が低解像度表示にとっていまだ許容可能である間の最良の実行スピードのために用いられるべきである。また一方で、今日のパーソナルコンピュータやハイエンドのＤＳＰシステム（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｙｓｔｅｍ）など、より速いマシンについては、よりよい周波数応答を有するフィルタを適用すべきである。なぜならその計算能力がより大きな複雑性を許容するからである。加えて、様々な最適化方法を、異なるレジスタサイズを有する特定のプラットフォームのために開発することができる。したがって、本発明のモーション推定は、他のモーションサーチアルゴリズムより柔軟である。
【０１０６】
本発明はまた、ＭＭＸおよびシストリックアレイをもちいたｘ８６、ＳＩＭＤを含むいくつかのハードウエアアーキテクチャについての、プラットフォーム特定の最適化について示す。そのオペレーションカウントからは、本発明のモーション推定は、汎用プロセッサシステム上でのソフトウエアによる実現にとっては大変望ましい。本発明は、ＡＳＩＣ設計のための並列パイプラインの実施により実現することができ、シリコン領域、パワー消費、および視覚品質の間のトレードオフをハードウエア設計フェーズ中に可能にする。したがって本発明のモーション推定は、ソフトウエアおよびハードウエアの両プラットフォームのマルチメディアシステムについて、いろんな目的に使用できかつ効果的である。
【０１０７】
本発明は、好ましい実施形態を参照して説明してきたが、本発明はその詳細な記述に限定されないことを理解されたい。様々な置換および修正形態が前述の説明で示唆されており、他のものを当業者は思いつくであろう。したがって、すべてのかかる置換および修正形態は、請求の範囲に規定された本発明の範囲内に含めることを意図するものである。
【図面の簡単な説明】
【図１】本発明によるモーション推定のための３レベル二値ピラミッド構造のブロック図である。
【図２】本発明によるモーション推定のための静状態チェッキングモジュールを示す図である。
【図３】本発明によるモーション推定のための状態更新モジュールを示す図である。
【図４】図１に示したモーション推定のための第一レベルサーチモジュールを示す図である。
【図５】図１に示したモーション推定のための第二レベルサーチモジュールを示す図である。
【図６】図１に示したモーション推定のための第三レベルサーチモジュールを示す図である。
【図７】テーブルルックアップのサブモジュールおよびビット差分合計のサブモジュールを含んだ本発明のＸＯＲブロックマッチングモジュールを示す図である。
【図８】本発明の各二値層の構造を示す図である。
【図９】二値化処理の並列処理を示す図である。
【図１０】３レベルサーチについて最初のサーチ位置へのビットアラインメントを示す図である。
【図１１】シストリックアレーを使ったチェックポイントの各行について並列ブロックマッチングの空間−時間表現を示す図である。
【図１２】並列２−Ｄブロックマッチングの詳細実施図である。
【図１３】ハードウェア加速を使ったおよび使ってない本発明によるフルサーチモーション推定について、計算の複雑さおよびバス帯域幅を示す図である。
【図１４】図１３の続きの図である。
【図１５】様々なエンコード条件、フィルタおよびＰＳＮＲ単位の視覚品質に基づいたフルサーチと本発明によるモーション推定の性能を比較した図である。
【図１】
2004173224.tif 000020
【図２】
2004173224.tif 000021
【図３】
2004173224.tif 000022
【図４】
2004173224.tif 000023
【図５】
2004173224.tif 000024
【図６】
2004173224.tif 000025
【図７】
2004173224.tif 000026
【図８】
2004173224.tif 000027
【図９】
2004173224.tif 000028
【図１０】
2004173224.tif 000029
【図１１】
2004173224.tif 000030
【図１２】
2004173224.tif 000031
【図１３】
2004173224.tif 000032
【図１４】
2004173224.tif 000033
【図１５】
2004173224.tif 000034