(57)【要約】  映像圧縮の分野、特に、デジタル映像符号器における改善された動き推定に関する技術を提供する。動き推定反復検索のための次位置セレクタは、次の検索区域の中心点を容易かつ迅速に判断することによって整数ピクセル動き推定反復検索の効率及び品質を改善する。現在の検索区域のＳＡＤ値を取り、その位置を次の検索区域の中心点にマップすることにより、次の検索区域を判断する処理は、非常に効率的である。極小値回避機構は、極小値に捕捉されることの回避を改善する。以前の位置／方向を覚えておくことにより、検索は、正しい方向に継続され、極小値に捕捉される前後する検索なしに継続されることを保証することができる。この改善された動き推定検索の用途は、画像の安定化、並びに動きベクトルが使用される多くの他の用途を含む。【選択図】図１
2011528534.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータデバイスを用いる動き推定反復検索を改善する方法であって、
ａ．最小距離位置に関して反復的に検索する段階、
ｂ．次の検索区域の中心点を判断する段階、及び
ｃ．極小値を回避する段階、
を含むことを特徴とする方法。
【請求項２】
前記最小距離位置は、最小「絶対差の和」位置であることを特徴とする請求項１に記載の方法。
【請求項３】
前記次の検索区域の前記中心点を判断する段階は、
ａ．最小距離値を有する検索区域の位置を判断する段階、
ｂ．前記最小距離値を有する前記位置に基づいて次の検索区域の中心点に対するオフセットを判断する段階、及び
ｃ．前記オフセットに基づいて前記次の検索区域の前記中心点を選択する段階、
を更に含む、
ことを特徴とする請求項１に記載の方法。
【請求項４】
極小値を回避する段階は、
ａ．以前の位置を判断する段階、
ｂ．新しい位置を判断する段階、
ｃ．前記以前の位置と前記新しい位置を比較する段階、及び
ｄ．前記以前の位置と前記新しい位置の比較に基づいて、該新しい位置が該以前の位置と反対の方向にある場合は該以前の位置に基づき、かつ該新しい位置が該以前の位置と反対の方向にない場合は該新しい位置に基づく新しい検索中心を選択する段階、
を更に含む、
ことを特徴とする請求項１に記載の方法。
【請求項５】
反復的に検索する段階は、
ａ．部分領域の部分領域距離値を計算する段階、
ｂ．前記部分領域の最小距離値を判断する段階、
ｃ．前記最小距離値を閾値と比較する段階、
ｄ．前記最小距離値が前記閾値よりも小さい場合に早期に終了する段階、及び
ｅ．前記最小距離値が前記閾値よりも大きいか又はそれに等しい場合に、計数値がゼロになるまでａ〜ｄを繰り返す段階、
を更に含む、
ことを特徴とする請求項１に記載の方法。
【請求項６】
コンピュータデバイスを用いる動き推定反復検索を改善するためのシステムであって、
ａ．ｉ．最小距離位置に関して反復的に検索する段階、
ｉｉ．次の検索区域の中心点を判断する段階、及び
ｉｉｉ．極小値を回避する段階、
を行うように構成されたアプリケーションを記憶するためのメモリ、及び
ｂ．前記アプリケーションを処理するためのプロセッサ、
を含むことを特徴とするシステム。
【請求項７】
前記最小距離位置は、最小「絶対差の和」位置であることを特徴とする請求項６に記載のシステム。
【請求項８】
前記次の検索区域の前記中心点を判断する段階は、
ａ．最小距離値を有する検索区域の位置を判断する段階、
ｂ．前記最小距離値を有する前記位置に基づいて次の検索区域の中心点に対するオフセットを判断する段階、及び
ｃ．前記オフセットに基づいて前記次の検索区域の前記中心点を選択する段階、
を更に含む、
ことを特徴とする請求項６に記載のシステム。
【請求項９】
極小値を回避する段階は、
ａ．以前の位置を判断する段階、
ｂ．新しい位置を判断する段階、
ｃ．前記以前の位置及び新しい位置を比較する段階、及び
ｄ．前記以前の位置と前記新しい位置の比較に基づいて、該新しい位置が該以前の位置と反対の方向にある場合は該以前の位置に基づき、かつ該新しい位置が該以前の位置と反対の方向にない場合は該新しい位置に基づく新しい検索中心を選択する段階、
を更に含む、
ことを特徴とする請求項６に記載のシステム。
【請求項１０】
反復的に検索する段階は、
ａ．部分領域の部分領域距離値を計算する段階、
ｂ．前記部分領域の最小距離値を判断する段階、
ｃ．前記最小距離値を閾値と比較する段階、
ｄ．前記最小距離値が前記閾値よりも小さい場合に早期に終了する段階、及び
ｅ．前記最小距離値が前記閾値よりも大きいか又はそれに等しい場合に、計数値がゼロになるまでａ〜ｄを繰り返す段階、
を更に含む、
ことを特徴とする請求項６に記載のシステム。
【請求項１１】
コンピュータデバイスを用いて次の検索区域の中心点を判断する方法であって、
ａ．最小距離値を有する検索区域の位置を判断する段階、
ｂ．前記最小距離値を有する前記位置に基づいて次の検索区域の中心点に対するオフセットを判断する段階、及び
ｃ．前記オフセットに基づいて前記次の検索区域の前記中心点を選択する段階、
を含むことを特徴とする方法。
【請求項１２】
前記最小距離値は、最小「絶対差の和」値であることを特徴とする請求項１１に記載の方法。
【請求項１３】
次の検索区域の前記中心点を判断する段階は、動きを推定する効率を改善し、それによって画像を安定させることを特徴とする請求項１１に記載の方法。
【請求項１４】
前記オフセットを判断する段階は、ルックアップテーブルを用いることによって実施されることを特徴とする請求項１１に記載の方法。
【請求項１５】
前記ルックアップテーブルは、前記検索区域の各位置に対する対応するオフセットを含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記検索区域は、３×３ピクセルであることを特徴とする請求項１１に記載の方法。
【請求項１７】
ハードウエアにのみ実施されることを特徴とする請求項１１に記載の方法。
【請求項１８】
部分的にハードウエアに実施されることを特徴とする請求項１１に記載の方法。
【請求項１９】
部分的にハードウエアに実施され、かつ部分的に１つ又はそれよりも多くのアプリケーションを用いて実施されることを特徴とする請求項１１に記載の方法。
【請求項２０】
前記コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択されることを特徴とする請求項１１に記載の方法。
【請求項２１】
コンピュータデバイスを用いて次の検索区域の中心点を判断するためのシステムであって、
ａ．ｉ．最小距離値を有する検索区域の位置を判断する段階、
ｉｉ．前記最小距離値を有する前記位置に基づいて次の検索区域の中心点に対するオフセットを判断する段階、及び
ｉｉｉ．前記オフセットに基づいて前記次の検索区域の前記中心点を選択する段階、
を行うように構成されたアプリケーションを記憶するためのメモリ、及び
ｂ．前記アプリケーションを処理するためのプロセッサ、
を含むことを特徴とするシステム。
【請求項２２】
前記最小距離値は、最小「絶対差の和」値であることを特徴とする請求項２１に記載のシステム。
【請求項２３】
次の検索区域の前記中心点を判断する段階は、動きを推定する効率を改善し、それによって画像を安定させることを特徴とする請求項２１に記載のシステム。
【請求項２４】
前記オフセットを判断する段階は、ルックアップテーブルを用いることによって実施されることを特徴とする請求項２１に記載のシステム。
【請求項２５】
前記ルックアップテーブルは、前記検索区域の各位置に対する対応するオフセットを含むことを特徴とする請求項２４に記載のシステム。
【請求項２６】
前記検索区域は、３×３ピクセルであることを特徴とする請求項２１に記載のシステム。
【請求項２７】
ハードウエアにのみ実施されることを特徴とする請求項２１に記載のシステム。
【請求項２８】
部分的にハードウエアに実施されることを特徴とする請求項２１に記載のシステム。
【請求項２９】
部分的にハードウエアに実施され、かつ部分的に１つ又はそれよりも多くのアプリケーションを用いて実施されることを特徴とする請求項２１に記載のシステム。
【請求項３０】
前記コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択されることを特徴とする請求項２１に記載のシステム。
【請求項３１】
コンピュータデバイスを用いて次の検索区域の中心点を判断するためのシステムであって、
ａ．検索区域の最小距離位置を受け取るための入力コンポーネント、
ｂ．前記最小距離位置をオフセットにマップするマッピングコンポーネント、及び
ｃ．前記オフセットを出力するための出力コンポーネント、
を含むことを特徴とするシステム。
【請求項３２】
前記最小距離位置は、最小「絶対差の和」位置であることを特徴とする請求項３１に記載のシステム。
【請求項３３】
次の検索区域の前記中心点の判断は、動きを推定する効率を改善し、それによって画像を安定させることを特徴とする請求項３１に記載のシステム。
【請求項３４】
前記マッピングコンポーネントは、ルックアップテーブルを利用することを特徴とする請求項３１に記載のシステム。
【請求項３５】
前記ルックアップテーブルは、前記検索区域の各位置に対する対応するオフセットを含むことを特徴とする請求項３４に記載のシステム。
【請求項３６】
前記検索区域は、３×３ピクセルであることを特徴とする請求項３１に記載のシステム。
【請求項３７】
ハードウエアにのみ実施されることを特徴とする請求項３１に記載のシステム。
【請求項３８】
部分的にハードウエアに実施されることを特徴とする請求項３１に記載のシステム。
【請求項３９】
部分的にハードウエアに実施され、かつ部分的に１つ又はそれよりも多くのアプリケーションを用いて実施されることを特徴とする請求項３１に記載のシステム。
【請求項４０】
前記コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択されることを特徴とする請求項３１に記載のシステム。
【請求項４１】
コンピュータデバイスを用いて動きを推定する時に極小値を回避する方法であって、
ａ．以前の位置を判断する段階、
ｂ．新しい位置を判断する段階、
ｃ．前記以前の位置及び新しい位置を比較する段階、及び
ｄ．前記以前の位置と前記新しい位置の比較に基づいて、該新しい位置が該以前の位置と反対の方向にある場合は該以前の位置に基づき、かつ該新しい位置が該以前の位置と反対の方向にない場合は該新しい位置に基づく新しい検索中心を選択する段階、
を含むことを特徴とする方法。
【請求項４２】
前記反対の方向は、前記新しい位置、前記以前の位置、及び中心点に基づいて判断されることを特徴とする請求項４１に記載の方法。
【請求項４３】
前記新しい位置及び前記以前の位置は、テーブル及び中心点を用いて比較されることを特徴とする請求項４１に記載の方法。
【請求項４４】
極小値の回避は、動きを推定する効率を改善し、それによって画像を安定させることを特徴とする請求項４１に記載の方法。
【請求項４５】
前記コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択されることを特徴とする請求項４１に記載の方法。
【請求項４６】
コンピュータデバイスを用いて動きを推定する時に極小値を回避する方法であって、
ａ．以前の方向を判断する段階、
ｂ．新しい方向を判断する段階、
ｃ．前記以前の方向と前記新しい方向を比較する段階、及び
ｄ．前記以前の方向と前記新しい方向の比較に基づいて、該新しい方向が該以前の方向と反対の方向にある場合は該以前の方向に基づき、かつ該新しい方向が該以前の方向と反対の方向ではない場合は該新しい方向に基づく新しい検索中心を選択する段階、
を含むことを特徴とする方法。
【請求項４７】
極小値の回避は、動きを推定する効率を改善し、それによって画像を安定させることを特徴とする請求項４６に記載の方法。
【請求項４８】
ハードウエアにのみ実施されることを特徴とする請求項４６に記載の方法。
【請求項４９】
部分的にハードウエアに実施されることを特徴とする請求項４６に記載の方法。
【請求項５０】
部分的にハードウエアに実施され、かつ部分的に１つ又はそれよりも多くのアプリケーションを用いて実施されることを特徴とする請求項４６に記載の方法。
【請求項５１】
前記コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択されることを特徴とする請求項４６に記載の方法。
【請求項５２】
コンピュータデバイスを用いて動きを推定する時に極小値を回避する方法であって、
ａ．検索区域の各点に対する距離値を計算する段階、
ｂ．前記検索区域の各点に対する前記距離値から最小距離位置を選択する段階、
ｃ．前記最小距離位置に基づいて新しい方向を判断する段階、
ｄ．前記新しい方向を以前の方向と比較する段階、
ｅ．前記新しい方向と前記以前の方向が反対の方向である場合に、以前の位置を保持する段階、
ｆ．前記新しい方向と前記以前の方向が反対の方向ではない場合に、新しい位置を選択する段階、
ｇ．前記以前の位置及び前記新しい位置のうちの一方に基づいて新しい検索中心を選択する段階、及び
ｈ．限界に達するまでａ〜ｇを繰り返す段階、
を含むことを特徴とする方法。
【請求項５３】
前記距離値は、「絶対差の和」値であることを特徴とする請求項５２に記載の方法。
【請求項５４】
前記限界は、ｎ回の反復であることを特徴とする請求項５２に記載の方法。
【請求項５５】
前記限界は、閾値であることを特徴とする請求項５２に記載の方法。
【請求項５６】
前記新しい方向は、前記新しい位置と中心点の間の第１の関係に基づいて判断され、前記以前の方向は、前記以前の位置と該中心点の間の第２の関係に基づいて判断されることを特徴とする請求項５２に記載の方法。
【請求項５７】
前記新しい方向及び前記以前の方向は、テーブルを使用し、前記新しい位置を中心点と比較し、かつ前記以前の位置を該中心点と比較して判断されることを特徴とする請求項５２に記載の方法。
【請求項５８】
前記検索区域は、５×５ピクセルであることを特徴とする請求項５２に記載の方法。
【請求項５９】
極小値の回避は、動きを推定する効率を改善し、それによって画像を安定させることを特徴とする請求項５２に記載の方法。
【請求項６０】
ハードウエアにのみ実施されることを特徴とする請求項５２に記載の方法。
【請求項６１】
部分的にハードウエアに実施されることを特徴とする請求項５２に記載の方法。
【請求項６２】
部分的にハードウエアに実施され、かつ部分的に１つ又はそれよりも多くのアプリケーションを用いて実施されることを特徴とする請求項５２に記載の方法。
【請求項６３】
前記コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択されることを特徴とする請求項５２に記載の方法。
【請求項６４】
コンピュータデバイスを用いて極小値を回避するためのシステムであって、
ａ．ｉ．検索区域の各点に対する距離値を計算する段階、
ｉｉ．前記検索区域の各点に対する前記距離値から最小距離位置を選択する段階、
ｉｉｉ．前記最小距離位置に基づいて新しい方向を判断する段階、
ｉｖ．前記新しい方向を以前の方向と比較する段階、
ｖ．前記新しい方向と前記以前の方向が反対の方向である場合に、以前の位置を保持する段階、
ｖｉ．前記新しい方向と前記以前の方向が反対の方向ではない場合に、新しい位置を選択する段階、
ｖｉｉ．前記以前の位置及び前記新しい位置のうちの一方に基づいて新しい検索中心を選択する段階、及び
ｖｉｉｉ．限界に達するまでｉ〜ｖｉｉを繰り返す段階、
を行うように構成されたアプリケーションを記憶するためのメモリ、及び
ｂ．前記アプリケーションを処理するためのプロセッサ、
を含むことを特徴とするシステム。
【請求項６５】
前記距離値は、「絶対差の和」値であることを特徴とする請求項６４に記載のシステム。
【請求項６６】
前記検索区域は、５×５ピクセルであることを特徴とする請求項６４に記載のシステム。
【請求項６７】
前記コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択されることを特徴とする請求項６４に記載のシステム。
【請求項６８】
極小値の回避は、動きを推定する効率を改善し、それによって画像を安定させることを特徴とする請求項６４に記載のシステム。
【請求項６９】
極小値を回避するためのシステムであって、
ａ．第１の組の計算を実行するためのハードウエアコンポーネント、及び
ｂ．第２の組の計算を実行するためのアプリケーションコンポーネント、
を含み、
前記第１の組の計算及び前記第２の組の計算は、以前の方向を判断する段階、新しい方向を判断する段階、及び該以前の方向と該新しい方向を比較して新しい検索中心を判断する段階を含む、
ことを特徴とするシステム。
【請求項７０】
前記極小値の回避は、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択されたデバイス上に実施されることを特徴とする請求項６９に記載のシステム。
【請求項７１】
極小値の回避は、動きを推定する効率を改善し、それによって画像を安定させることを特徴とする請求項６９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、映像圧縮の分野に関する。より具体的には、本発明は、デジタル映像符号器における改善された動き推定に関する。
【背景技術】
【０００２】
映像シーケンスは、通常、フレームと呼ばれる多くの画像から成る。連続するフレームは非常に類似しており、従って、１つのフレームから次のフレームへと大量の冗長性を含む。映像データは、チャンネルを通じて効率的に送信されるか又はメモリに記憶される前に、帯域幅及びメモリの両方を節約するために圧縮される。目標は、冗長性を排除してより良好な圧縮比を得ることである。第１の映像圧縮手法は、所定のフレームから基準フレームを減算して相対的差異を発生させることである。圧縮されたフレームは、基準フレームよりも少ない情報を含む。相対的差異は、同じ品質を有しながらより低いビットレートで符号化することができる。復号器は、基準フレームに相対的差異を加算することによって元のフレームを復元する。
【０００３】
更に高度な手法は、シーン全体の動き及び映像シーケンスのオブジェクトを近似することである。動きは、ビットストリーム内に符号化されたパラメータによって記述される。予測フレームのピクセルは、基準フレームの適切に変換されたピクセルによって近似される。この手法は、単純な減算よりも改善された予測機能を提供する。しかし、動きモデルのパラメータによって占有されるビットレートは、過度に大きくなってはならない。
【０００４】
一般的に、映像圧縮は、ＭＰＥＧ−１、ＭＰＥＧ−２、及びＭＰＥＧ−４のような「エムペグ（ＭＰＥＧ）」からの音声及び映像に対する１つ又はそれよりも多くの規格を含む多くの規格に従って実施される。Ｈ．２６４又はＡＶＣ（高度映像符号化）とも呼ばれるＭＰＥＧ−４パート１０規格の一部として、付加的な拡張が行われた。ＭＰＥＧ規格の下では、映像データは、最初に符号化され（例えば、圧縮され）、次に、映像システムの符号器側の符号器バッファに記憶される。後に、符号化されたデータは、映像システムの復号器側に送信され、そこで復号器バッファに記憶され、その後、対応する画像を見ることができるように復号される。
【０００５】
Ｈ．２６４／ＡＶＣ計画の意図は、以前の規格が必要とすると考えられるもの（例えば、ＭＰＥＧ−２、Ｈ．２６３、又はＭＰＥＧ−４パート２）よりも実質的に低いビットレートで良好な映像品質をもたらすことができる規格を開発することであった。更に、その設計を実施不能にするような大幅な複雑性の増大を伴わずにこれらの改善を加えることが望まれた。付加的な目標は、規格を低ビットレートと高ビットレートの両方、及び低解像度映像と高解像度映像の両方に対して用いることができるように、様々な用途にこの規格を適用することを可能にすると考えられる柔軟な方法でこれらの変更を加えることであった。別の目的は、それが、非常に広範なネットワーク及びシステム上で十分に機能することであった。
【０００６】
Ｈ．２６４／ＡＶＣ／ＭＰＥＧ−４パート１０は、古い規格よりも非常に効率的に映像を圧縮し、様々なネットワーク環境に対する適用に向けてより高い柔軟性をもたらすことを可能にする多くの新しい特徴を含む。一部の主要な特徴は、以前に符号化された画像を基準として用いた多画像動き補償、最大で１６×１６及び最小で４×４のブロックサイズでの可変ブロックサイズ動き補償（ＶＢＳＭＣ）、半ピクセル輝度サンプル予測の導出のための６タップフィルタリング、マクロブロック対構造、動き補償における４分の１ピクセル精度、重み付き予測、ループ内ブロック解除フィルタ、完全符合整数４×４空間ブロック変換、１次空間変換の「ＤＣ」係数に対して実行される、高速フーリエ変換に類似の２次アダマール変換、「内部」符号化のための隣接ブロックのエッジからの空間予測、状況適応２進演算符号化（ＣＡＢＡＣ）、状況適応可変長符号化（ＣＡＶＬＣ）、「指数−ゴロム」符号化と呼ばれるＣＡＢＡＣ又はＣＡＶＬＣによっては符号化されない構文要素の多くに対する単純で高度に構造化された可変長符号化（ＶＬＣ）技術、ネットワーク抽象化層（ＮＡＬ）定義、スイッチングスライス、柔軟なマクロブロック順序付け、冗長スライス（ＲＳ）、補足的拡張情報（ＳＥＩ）、及び映像使用可能性情報（ＶＵＩ）、補助画像、フレーム付番、並びに画像順序計数を含む。これらの技術及びいくつかの他のものは、Ｈ．２６４を以前の規格よりも有意に良好に、かつより多くの状況下及びより多くの環境において実施することを可能にする。通常、Ｈ．２６４は、半分のビットレート又は更にそれ以下で同じ品質を得ることでＭＰＥＧ−２映像よりも良好に機能する。
【０００７】
ＭＰＥＧは、動画及び関連の音声の汎用符号化に用いられ、一連の３種類の符号化されたデータフレームで構成された圧縮映像ビットストリームを発生させる。３種類のデータフレームは、イントラフレーム（Ｉフレーム又はＩ画像と呼ばれる）、双方向予測フレーム（Ｂ−フレーム又はＢ画像と呼ばれる）、及び順方向予測フレーム（Ｐフレーム又はＰ画像と呼ばれる）である。これらの３種類のフレームは、ＧＯＰ（画像の群）構造と呼ばれる指定順序で配置することができる。Ｉフレームは、画像を復元するのに必要な全ての情報を含む。Ｉフレームは、動き補償のない通常映像として符号化される。一方、Ｐフレームは、以前のフレームからの情報を用い、Ｂ−フレームは、以前のフレーム、次のフレーム、又はこれらの両方からの情報を用いて画像を復元する。特に、Ｐフレームは、先行するＩフレーム又は直前のＰフレームから予測される。
【０００８】
フレームはまた、直後のフレームから予測することができる。この手法で次のフレームを利用するためには、次のフレームを予測フレームの前に符号化すべきである。従って、符号化の順序は、実際のフレームの順序と必ずしも一致しない。そのようなフレームは、通常は、例えば、予測フレームの直前のＩフレーム又はＰフレーム、又は直後のＰフレームという２方向から予測される。これらの双方向予測フレームはＢフレームと呼ばれる。
【０００９】
多くの可能なＧＯＰ構造が存在する。一般的なＧＯＰ構造は、１５フレーム長であり、Ｉ＿ＢＢ＿Ｐ＿ＢＢ＿Ｐ＿ＢＢ＿Ｐ＿ＢＢ＿Ｐ＿ＢＢ＿というシーケンスを有する。類似の１２フレームシーケンスも一般的である。Ｉフレームは、空間冗長性に対して符号化し、Ｐフレーム及びＢ−フレームは、時間冗長性と空間冗長性の両方に対して符号化する。映像ストリーム内で隣接するフレームは、多くの場合に非常に相関しているので、Ｐフレーム及びＢ−フレームは、Ｉフレームのサイズの僅かな割合でしかない。しかし、フレームを圧縮することができる圧縮後サイズと、そのような圧縮フレームを符号化するのに必要とされる処理時間及びリソースの間には背反関係が存在する。ＧＯＰ構造におけるＩフレームとＰフレームとＢ−フレームとの比は、映像ストリームの性質及び出力ストリームに対する帯域幅によって判断されるが、同じく符号化時間も問題である可能性がある。多くのＢフレームを含むストリームは、Ｉフレームのみのファイルよりも符号化するのに大幅な時間を消費する場合があるから、上述のことは、限られたコンピュータリソースしか持たないライブ送信及び実時間環境では特に当て嵌まる。
【００１０】
Ｂフレーム及びＰフレームは、一般的に、現在のフレームと、以前のフレーム、次のフレーム、又はこれらの両方のフレームの間の差異に関する差異ビットを含み、画像データを記憶するのにより少ないビットしか必要としない。従って、Ｂフレーム及びＰフレームは、フレームにわたって含まれる冗長性情報を低減するのに用いられる。作動時には、復号器は、符号化されたＢフレーム又は符号化されたＰフレームを受け取り、以前又は次のフレームを用いて元のフレームを復元する。連続フレームが実質的に類似する場合はフレームにおける差異が小さいので、この処理は極めて容易であり、滑らかなシーン移行を引き起こす。
【００１１】
各映像画像は、輝度（Ｙ）チャンネル及び２つの色度チャンネル（色差信号Ｃｂ及びＣｒとも呼ばれる）に分離される。輝度及び色度の配列のブロックは、イントラフレームの符号化の基本ユニットである「マクロブロック」へと編成される。
Ｉフレームの場合には、実際の映像データが符号化処理に渡される。しかし、Ｐフレーム及びＢフレームは、最初に、「動き補償」処理を受ける。動き補償は、先行フレームの各マクロブロックが移動した位置に関する連続するフレーム間の差異を説明する手法である。そのような技術は、映像圧縮の映像シーケンスの時間冗長性を低減するのに多くの場合に用いられる。Ｐフレーム又はＢフレーム内の各マクロブロックは、「動きベクトル」を用いて符号器によって選択される以前又は次の映像内で非常に相関している区域に関連付けられる。マクロブロックをその相関する区域にマップする動きベクトルは符号化され、次に、２つの区域の間の差異が符号化処理に渡される。
【００１２】
従来の映像コーデックは、動き補償予測を用いて生の入力映像ストリームを効率的に符号化する。現在のフレーム内のマクロブロックは、以前のフレーム内の移行したマクロブロックから予測される。元のマクロブロックとその予測マクロブロックの間の差異は圧縮され、変位（動き）ベクトルと共に送信される。この技術は、フレーム間符号化と呼ばれ、ＭＰＥＧ規格に用いられる手法である。
【００１３】
符号化処理において最も時間を消費するコンポーネントのうちの１つが動き推定である。動き推定は、動き補償予測を予測誤差の変換符号化との組合せで実施することによって映像信号のビットレートを低減するのに利用される。動き推定に関連するエイリアシングは、フレーム間ピクセル動き推定を用いることによっては回避することができず、エイリアシングは予測効率を劣化させる。劣化問題を解決するために、エイリアシングの影響を低減するように半ピクセル内挿及び４分の１ピクセル内挿が適用される。４分の１ピクセル精度で動きベクトルを推定するには、一般的に、３段階検索が用いられる。第１の段階では、指定検索範囲の各整数ピクセルに対して動き推定が適用され、最良の適合が見出される。次に、第２の段階では、選択された整数ピクセル動きベクトルの周囲の８つの半ピクセル点が調べられ、最良の半ピクセル適合点が見出される。最後に第３の段階で、選択された半ピクセル動きベクトルの周囲の８つの４分の１ピクセル点が調べられ、最良の適合点が最終動きベクトルとして選択される。動き推定の複雑性を考慮すると、整数ピクセル動き推定において全検索が用いられた場合には、整数ピクセル動き推定は、動き推定のうちで主な部分を占める。しかし、高速整数動き推定アルゴリズムが利用される場合には、整数ピクセル動きベクトルは、１０個よりも少ない検索点を調べることによって得ることができる。その結果、半ピクセル動きベクトル及び４分の１ピクセル動きベクトルを検索する計算複雑性が大半になる。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】Ｙａｍａｕｃｈｉ，Ｈ．他著「８１ＭＨｚ、１２８０ｘ７２０ピクセル×３０フレーム／ｓ、ＭＰＥＧ−４映像／音声ＣＯＤＥＣプロセッサ」
【発明の概要】
【発明が解決しようとする課題】
【００１５】
動き推定反復検索のための次位置セレクタは、次の検索区域の中心点を容易かつ迅速に判断することによって整数ピクセル動き推定反復検索の効率及び品質を改善する。現在の検索区域のＳＡＤ値を取り、その位置を次の検索区域の中心点にマップすることにより、次の検索区域を判断する処理は、非常に効率的である。極小値回避機構は、極小値に捕捉されることの回避を改善する。以前の位置／方向を覚えておくことにより、検索は、正しい方向に継続され、極小値に捕捉される前後する検索なしに継続されることを保証することができる。この改善された動き推定検索の用途は、画像の安定化、並びに動きベクトルが使用される多くの他の用途を含む。
【課題を解決するための手段】
【００１６】
一態様では、コンピュータデバイスを用いた動き推定反復検索を改善する方法は、最小距離位置に関して反復的に検索する段階、次の検索区域の中心点を判断する段階、及び極小値を回避する段階を含む。一部の実施形態では、最小距離位置は、最小「絶対差の和」位置である。次の検索区域の中心点を判断する段階は、最小距離値を有する検索区域の位置を判断する段階、最小距離値を有する位置に基づいて次の検索区域の中心点に対するオフセットを判断する段階、及びオフセットに基づいて次の検索区域の中心点を選択する段階を更に含む。極小値を回避する段階は、以前の位置を判断する段階、新しい位置を判断する段階、以前の位置と新しい位置を比較する段階、及び以前の位置と新しい位置の比較に基づいて、新しい位置が以前の位置と反対の方向にある場合は以前の位置に基づき、かつ新しい位置が以前の位置と反対の方向にない場合は新しい位置に基づく新しい検索中心を選択する段階を更に含む。反復的に検索する段階は、部分領域の部分領域距離値を計算する段階、部分領域の最小距離値を判断する段階、最小距離値を閾値と比較する段階、最小距離値が閾値よりも小さい場合に、早期に終了する段階、及び最小距離値が閾値よりも大きいか又はそれに等しい場合に、計数値がゼロになるまでこれらの段階を繰り返す段階を更に含む。
【００１７】
別の態様では、コンピュータデバイスを用いた動き推定反復検索を改善するためのシステムは、最小距離位置に関して反復的に検索する段階、次の検索区域の中心点を判断する段階、及び極小値を回避する段階を行うように構成されたアプリケーションを記憶するためのメモリと、アプリケーションを処理するためのプロセッサとを含む。一部の実施形態では、最小距離位置は、最小「絶対差の和」位置である。次の検索区域の中心点を判断する段階は、最小距離値を有する検索区域の位置を判断する段階、最小距離値を有する位置に基づいて次の検索区域の中心点に対するオフセットを判断する段階、及びオフセットに基づいて次の検索区域の中心点を選択する段階を更に含む。極小値を回避する段階は、以前の位置を判断する段階、新しい位置を判断する段階、以前の位置と新しい位置を比較する段階、及び以前の位置と新しい位置の比較に基づいて、新しい位置が以前の位置と反対の方向にある場合は以前の位置に基づき、新しい位置が以前の位置と反対の方向にない場合は新しい位置に基づく新しい検索中心を選択する段階を更に含む。反復的に検索する段階は、部分領域の部分領域距離値を計算する段階、部分領域の最小距離値を判断する段階、最小距離値を閾値と比較する段階、最小距離値が閾値よりも小さい場合に早期に終了する段階、及び最小距離値が閾値よりも大きいか又はそれに等しい場合に、計数値がゼロになるまでこれらの段階を繰り返す段階を更に含む。
【００１８】
更に別の態様では、コンピュータデバイスを用いて次の検索区域の中心点を判断する方法は、最小距離値を有する検索区域の位置を判断する段階、最小距離値を有する位置に基づいて次の検索区域の中心点に対するオフセットを判断する段階、及びオフセットに基づいて次の検索区域の中心点を選択する段階を含む。一部の実施形態では、最小距離値は、最小「絶対差の和」値である。次の検索区域の中心点を判断する段階は、動きを推定する効率を改善し、それによって画像を安定させる。オフセットを判断する段階は、ルックアップテーブルを用いることによって実施される。ルックアップテーブルは、検索区域の各位置に対する対応するオフセットを含む。代替的に、検索区域は、３×３ピクセルである。一部の実施形態では、本方法は、ハードウエアにのみ実施される。代替的に、本方法は、部分的にハードウエアに実施される。代替的に、本方法は、部分的にハードウエアに実施され、かつ部分的に１つ又はそれよりも多くのアプリケーションを用いて実施される。コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択される。
【００１９】
別の態様では、コンピュータデバイスを用いて次の検索区域の中心点を判断するためのシステムは、最小距離値を有する検索区域の位置を判断する段階、最小距離値を有する位置に基づいて次の検索区域の中心点に対するオフセットを判断する段階、及びオフセットに基づいて次の検索区域の中心点を選択する段階を行うように構成されたアプリケーションを記憶するためのメモリと、アプリケーションを処理するためのプロセッサとを含む。一部の実施形態では、最小距離値は、最小「絶対差の和」値である。次の検索区域の中心点を判断する段階は、動きを推定する効率を改善し、それによって画像を安定させる。オフセットを判断する段階は、ルックアップテーブルを用いることによって実施される。ルックアップテーブルは、検索区域の各位置に対する対応するオフセットを含む。代替的に、検索区域は、３×３ピクセルである。一部の実施形態では、システムは、ハードウエアにのみ実施される。代替的に、システムは、部分的にハードウエアに実施される。代替的に、システムは、部分的にハードウエアに実施され、かつ部分的に１つ又はそれよりも多くのアプリケーションを用いて実施される。コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択される。
【００２０】
別の態様では、コンピュータデバイスを用いて次の検索区域の中心点を判断するためのシステムは、検索区域の最小距離位置を受け取るための入力コンポーネント、最小距離位置をオフセットにマップするマッピングコンポーネント、及びオフセットを出力するための出力コンポーネントを含む。一部の実施形態では、最小距離位置は、最小「絶対差の和」位置である。次の検索区域の前記中心点を判断する段階は、動きを推定する効率を改善し、それによって画像を安定させる。マッピングコンポーネントは、ルックアップテーブルを利用する。ルックアップテーブルは、検索区域の各位置に対する対応するオフセットを含む。代替的に、検索区域は、３×３ピクセルである。一部の実施形態では、システムは、ハードウエアにのみ実施される。代替的に、システムは、部分的にハードウエアに実施される。代替的に、システムは、部分的にハードウエアに実施され、かつ部分的に１つ又はそれよりも多くのアプリケーションを用いて実施される。コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択される。
【００２１】
更に別の態様では、コンピュータデバイスを用いて動きを推定する時に極小値を回避する方法は、以前の位置を判断する段階、新しい位置を判断する段階、以前の位置と新しい位置を比較する段階、以前の位置と新しい位置の比較に基づいて、新しい位置が以前の位置と反対の方向にある場合は以前の位置に基づき、かつ新しい位置が以前の位置と反対の方向にない場合は新しい位置に基づいて新しい検索中心を選択する段階を含む。反対の方向は、新しい位置、以前の位置、及び中心点に基づいて判断される。新しい位置と以前の位置は、テーブル及び中心点を用いて比較される。極小値の回避は、動きを推定する効率を改善し、それによって画像を安定させる。コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択される。
【００２２】
別の態様では、コンピュータデバイスを用いて動きを推定する時に極小値を回避する方法は、以前の方向を判断する段階、新しい方向を判断する段階、以前の方向と新しい方向を比較する段階、及び以前の方向と新しい方向の比較に基づいて、新しい方向が以前の方向と反対の方向にある場合は以前の方向に基づき、かつ新しい方向が以前の方向と反対の方向ではない場合は新しい方向に基づく新しい検索中心を選択する段階を含む。極小値の回避は、動きを推定する効率を改善し、それによって画像を安定させる。一部の実施形態では、本方法は、ハードウエアにのみ実施される。代替的に、本方法は、部分的にハードウエアに実施される。代替的に、本方法は、部分的にハードウエアに実施され、かつ部分的に１つ又はそれよりも多くのアプリケーションを用いて実施される。コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択される。
【００２３】
別の態様では、コンピュータデバイスを用いて動きを推定する時に極小値を回避する方法は、検索区域の各点に対する距離値を計算する段階、検索区域の各点に対する距離値から最小距離位置を選択する段階、最小距離位置に基づいて新しい方向を判断する段階、新しい方向を以前の方向と比較する段階、新しい方向と以前の方向が反対の方向である場合に、以前の位置を保持する段階、新しい方向と以前の方向が反対の方向ではない場合に、新しい位置を選択する段階、以前の位置及び新しい位置のうちの一方に基づいて新しい検索中心を選択する段階、及び限界に達するまでこれらの段階を繰り返す段階を含む。一部の実施形態では、最小距離位置は、最小「絶対差の和」位置である。限界は、ｎ回の反復である。代替的に、限界は、閾値である。新しい方向は、新しい位置と中心点の間の第１の関係に基づいて判断され、以前の方向は、以前の位置と中心点の間の第２の関係に基づいて判断される。新しい方向及び以前の方向は、テーブルを使用し、新しい位置を中心点と比較し、かつ以前の位置を中心点と比較して判断される。検索区域は、５×５ピクセルである。極小値の回避は、動きを推定する効率を改善し、それによって画像を安定させる。一部の実施形態では、本方法は、ハードウエアにのみ実施される。代替的に、本方法は、部分的にハードウエアに実施される。代替的に、本方法は、部分的にハードウエアに実施され、かつ部分的に１つ又はそれよりも多くのアプリケーションを用いて実施される。コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択される。
【００２４】
更に別の態様では、コンピュータデバイスを用いて極小値を回避するためのシステムは、検索区域の各点に対する距離値を計算する段階、検索区域の各点に対する距離値から最小距離位置を選択する段階、最小距離位置に基づいて新しい方向を判断する段階、新しい方向を以前の方向と比較する段階、新しい方向と以前の方向が反対の方向である場合に、以前の位置を保持する段階、新しい方向と以前の方向が反対の方向ではない場合に、新しい位置を選択する段階、以前の位置及び新しい位置のうちの一方に基づいて新しい検索中心を選択する段階、及び限界に達するまでこれらの段階を繰り返す段階を行うように構成されたアプリケーションを記憶するためのメモリと、アプリケーションを処理するためのプロセッサとを含む。一部の実施形態では、距離値は、「絶対差の和」値である。検索区域は、５×５ピクセルである。コンピュータデバイスは、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択される。極小値の回避は、動きを推定する効率を改善し、それによって画像を安定させる。
【００２５】
別の態様では、極小値を回避するためのシステムは、第１の組の計算を実行するためのハードウエアコンポーネント、及び第２の組の計算を実行するためのアプリケーションコンポーネントを含み、第１の組の計算及び第２の組の計算は、以前の方向を判断する段階、新しい方向を判断する段階、及び以前の方向と新しい方向を比較して新しい検索中心を判断する段階を含む。極小値の回避は、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、及びホームエンタテインメントシステムから成る群から選択されたデバイス上に実施される。極小値の回避は、動きを推定する効率を改善し、それによって画像を安定させる。
【図面の簡単な説明】
【００２６】
【図１】本発明による映像符号化層のブロック図である。
【図２】本発明による動き推定フローの図である。
【図３】本発明による例示的な検索の図である。
【図４】本発明による反復検索の流れ図である。
【図５】本発明による「絶対差の和（ＳＡＤ）」を計算するのに用いられる例示的な検索位置及びピクセルの図である。
【図６】本発明による動きを推定するのに推測的開始点選択を実施する流れ図である。
【図７】本発明による例示的なコンピュータデバイスのブロック図である。
【図８】本発明によるナイーブな次段階選択の図である。
【図９】本発明による極小値における検索滞留の図である。
【図１０】本発明による反対方向へのナイーブな次段階選択の逆戻りの図である。
【図１１】本発明による極小値から抜け出す検索の図である。
【図１２】本発明による位置行列の図である。
【図１３】本発明による反対の位置が陰付き表示された位置行列の図である。
【図１４】本発明による新しい位置及び禁則反対位置の図である。
【図１５】本発明によるナイーブな検索の流れ図である。
【図１６】本発明による極小値回避検索の流れ図である。
【図１７】本発明による次位置セレクタの流れ図である。
【図１８】本発明による現在の検索区域の最小ＳＡＤを有する位置に基づく次の検索区域を３×３検索区域において例示する図である。
【図１９】本発明による現在の検索区域の最小ＳＡＤを有する位置に基づく次の検索区域を３×３検索区域において例示する図である。
【図２０】本発明による現在の検索区域の最小ＳＡＤを有する位置に基づく次の検索区域を３×３検索区域において例示する図である。
【図２１】本発明による次の位置を選択する方法の流れ図である。
【図２２】本発明による最小ＳＡＤを有する位置に基づいて次の検索区域の中心点を判断するための例示的なルックアップテーブルの図である。
【図２３】本発明による動きベクトルコストと予測動きベクトルのＳＡＤとに基づく精緻化を用いた反復検索の流れ図である。
【図２４】本発明による現在のマクロブロックを隣接マクロブロック及びそれらの動きベクトルと共に例示する図である。
【図２５】本発明による動きベクトルコストと予測動きベクトルのＳＡＤとに基づく精緻化を用いた反復検索の流れ図である。
【図２６】本発明による早期終了機構を有する反復検索の流れ図である。
【発明を実施するための形態】
【００２７】
図１は、マクロブロックの映像符号化層１００のブロック図を示している。映像符号化層１００（例えば、符号器）は、変換符号化と共に時間予測と空間予測との組合せを含む。入力映像１０２が受け取られ、複数のブロックに分割される。シーケンスの先頭の画像は、通常はそれ自体に含まれる情報のみを用いて「イントラ」符号化される。次に、イントラフレーム内のブロックの各部分は、以前に符号化されたブロックの空間的に隣接するサンプルを用いてイントラ予測モジュール１１０で予測される。符号化処理は、どの隣接サンプルがイントラ予測において利用され、これらのサンプルがどのように用いられるかを選択する。この処理は、ローカル復号器１１８、並びに符号器１００において実施される。シーケンスのうちの残りの画像に対しては、通常は「インター」符号化が用いられる。インター符号化は、他の以前に復号された画像からの動き補償１１２を実施する。動き推定モジュール１１４におけるインター予測／動き推定のための符号化処理は、動きデータを選択する段階と、基準画像及びブロックの全てのサンプルに適用される空間移行を判断する段階とを含む。動きデータは、符号器１００及びローカル復号器１１８によって用いられる付帯情報として送信される。
【００２８】
元のブロックと予測ブロックの間の差異を予測残差と呼ぶ。変換及びスケーリング量子化モジュール１０４においてこの残差は変換され、変換係数がスケーリング及び量子化される。変換係数の量子化では、スカラー量子化が利用される。各ブロックは、整数変換を用いて変換され、変換係数は量子化され、エントロピー符号化法を用いて送信される。エントロピー符号器１１６は、量子化された変換係数を除く全ての要素に対してコードワードセットを用いる。量子化された変換係数に対しては、「状況適応可変長符号化（ＣＡＶＬＣ）」又は「状況適応２進演算符号化（ＣＡＢＡＣ）」が利用される。フィルタリングの強度を制御して映像のブロックノイズを低減するために、ブロック解除フィルタ１０８が実施される。
【００２９】
また、符号器１００は、次のブロックに対する予測基準を発生させるローカル復号器１１８を含む。量子化された変換係数は、符号器側と同じ手法で逆スケーリング及び逆変換され１０６、それによって復号された予測残差が与えられる。復号された予測残差は、予測に加算され、この組合せは、ブロック解除フィルタ１０８に誘導され、ブロック解除フィルタ１０８は、復号された映像を出力として供給する。最終的にエントロピー符号器１１６が、最初に入力された映像１０２の圧縮映像ビット１２０を生成する。
【００３０】
映像符号器の「動き推定（ＭＥ）」において最も高価な計算は、予測画像と元の画像の間の「絶対差の和（ＳＡＤ）」の計算である。特に、整数ピクセル検索のＳＡＤ計算がその大半を占める。従って、整数ピクセル検索においてＳＡＤ計算の回数を低減することは、ハードウエアサイズ、及び従ってコストを低減するのに重要な役割を有する。図２は、画像を取得し、整数ピクセル検索、半ピクセル輝度検索、及び４分の１ピクセル輝度検索を実行し、動きベクトルを判断する動き推定フロー２００を示している。
【００３１】
ＳＡＤ計算を低減するための一般的な手法は、ＭＥハードウエアが、より少ない回数のＳＡＤ計算で同じ検索範囲を検索することができるように、ＳＡＤ計算の前に基準画像と元の画像とを部分サンプリングすることである。部分サンプリングされた検索範囲内でも、検索は依然として消耗的である。検索は、大雑把な部分サンプリング済み領域内で行われるので、より精密な動きベクトルを得るには精緻化が必要である。
【００３２】
引用によって本明細書に組み込まれているＹａｍａｕｃｈｉ，Ｈ．他著「８１ＭＨｚ、１２８０ｘ７２０ピクセル×３０フレーム／ｓ、ＭＰＥＧ−４映像／音声ＣＯＤＥＣプロセッサ」に説明されている反復動き推定検索法は、検索範囲の一部のみのＳＡＤを計算することによってＳＡＤ計算の回数を更に低減する。この方法を用いると、システムは、一度に小さい領域のＳＡＤしか計算しない。次に、システムは、この領域のＳＡＤを比較し、最小ＳＡＤの位置を選出する。次に、システムは、以前の検索結果に基づいて別の小領域を選択する。システムは、この処理をある一定回数繰り返す。全ての反復の間に最小ＳＡＤ値を有する検索位置が、最良の適合位置として選択される。反復回数は、ハードウエア性能に依存する。図３は、開始位置３００及び判断された最小ＳＡＤ３０２を示している例示的な検索であり、各段階が、一度に９個の検索点（３×３）を検索し、５回繰り返すものを示している。
【００３３】
図４は、反復検索の流れ図を示している。段階４００において、処理は、Ｎに等しい計数値で始まり、ここでＮは検索を行う回数である。段階４０２では、ある領域のＳＡＤが計算される（例えば、３×３領域）。段階４０４では、段階４０２の計算に基づいてこの領域内での最小ＳＡＤ位置が選択される。段階４０６では、最小ＳＡＤ位置が、以前の最良の（例えば、最小）ＳＡＤと比較され、２つのうちの小さい方が保持される。段階４０８では、反復を計数するために計数値が１だけ減分される。段階４１０では、計数値が０であるか否かが判断される。計数値が０であった場合には、処理は終了する。計数値が０ではなかった場合には、段階４１２において次の検索位置が選択される。その後、段階４０２で始まり、処理は繰り返す。一部の実施形態では、異なる計数実施又は異なる計数順を用いることができる。
【００３４】
検索範囲の一部しか検索されないので、ＳＡＤ計算回数は、消耗的な検索と比較して劇的に低減する。部分サンプリング検索では、少数の検索点（３×３グリッド内で９つ等）が一度に検索され、検索は、Ｎ回（５回等）繰り返される。「３×３検索」は、「９つの位置」のＳＡＤ計算を意味し、「９回のＳＡＤ」を意味するのではない。従って、マクロブロック（１６×１６ピクセル）が１／４サイズ（例えば、８×８ピクセル））で部分サンプリングされる場合には、「１つの位置」に対するＳＡＤ回数は８×８＝６４である。ハードウエアでは、６４回のＳＡＤ計算は、同時に計算することができる。図５は、例示的な３×３の検索位置５００及び８×８ピクセルのマクロブロックの部分サンプル５０２を示している。３×３の部分サンプル検索を説明したが、検索のサイズは、このサイズに限定されない。
しかし、部分サンプリング反復検索は、検索範囲の位置の全てを調べるわけではないので、この検索には問題がある。つまりこの検索は、可能な最良の解が見出されることになることを保証しない。特に、検索は間違った方向に進む場合があり、及び／又は最良の検索位置が、開始位置から遠過ぎる場合がある。
【００３５】
推測的開始点
上述の問題を解決するために、推測的開始点反復検索が用いられる。推測的検索機構を用いると、反復が始まる前に、システムは、いくつかの「有望な」位置のＳＡＤを比較する。次に、「有望な」位置のうちの最良のものが、反復検索の開始位置として用いられる。Ｈ．２６４符号器における実施では、検索は２段階で実行されるが、代替的に、いかなる段階数においても実行することができる。
【００３６】
図６は、動きを推定するのに推測的開始点選択を実施する流れ図を示している。段階６００では、「グローバル動きベクトル（ＧＭＶ）」、「ゼロ（０）動きベクトル（０ＭＶ）」、及び「予測動きベクトル（ＰＭＶ）」という３つの位置のＳＡＤが計算される。ＧＭＶは、以前に符号化されたフレームの統計からフレーム毎に一度計算され、ＰＭＶは、現在のフレーム内の隣接マクロブロックからの各マクロブロックに対して推定される。最小ＳＡＤを有する位置が、以降の反復検索の開始位置として用いられる。「符号器／復号器（ＣＯＤＥＣ）」によっては、様々な位置を上述したものに限定されない「有望な」位置として選択することができる。上記では３つの位置を説明したが、選択するのに利用可能な位置の個数は、３つに限定されず、それよりも多いか又は少ない位置から選択することができる。
【００３７】
段階６０２では、システムは、図４で説明した反復検索を実行する。しかし、反復の開始位置は、段階６００からの最良の開始位置である。一部の実施形態では、段階６００の後に、選択されたＳＡＤが、反復検索の他の実施における開始位置として用いられる。段階６０４では、動きベクトルが精緻化される。段階６０６では、部分ピクセル検索が実施される。結果は、より短い時間量で処理された滑らかな画像／映像である。
【００３８】
図７は、本発明による例示的なコンピュータデバイス７００のブロック図である。コンピュータデバイス７００は、映像及び映像のような情報を取得、記憶、計算、通信、及び／又は表示するのに用いることができる。例えば、コンピュータデバイス７００は映像を取得し、映像が得られる間に、この改善された動き推定処理が行われる。一般的に、コンピュータデバイス７００を実施するのに適切なハードウエア構造は、ネットワークインタフェース７０２、メモリ７０４、プロセッサ７０６、Ｉ／Ｏデバイス７０８、バス７１０、及び記憶デバイス７１２を含む。プロセッサの選択は、十分な速度を有する適切なプロセッサが選択される限り重要ではない。メモリ７０４は、当業技術で公知のあらゆる従来のコンピュータメモリとすることができる。記憶デバイス７１２は、ハードドライブ、ＣＤＲＯＭ、ＣＤＲＷ、ＤＶＤ、ＤＶＤＲＷ、フラッシュメモリカード、又はあらゆる他の記憶デバイスを含むことができる。コンピュータデバイス７００は、１つ又はそれよりも多くのネットワークインタフェース７０２を含むことができる。ネットワークインタフェースの例は、イーサネット（登録商標）又は他の種類のＬＡＮに接続したネットワークカードを含む。Ｉ／Ｏデバイス７０８は、キーボード、マウス、モニタ、ディスプレイ、プリンタ、モデム、タッチスクリーン、ボタンインタフェース、及び他のデバイスのうちの１つ又はそれよりも多くを含むことができる。本発明の方法を実施するのに用いられるアプリケーション７３０は、記憶デバイス７１２及びメモリ７０４に記憶され、アプリケーションが典型的に処理されるように処理される可能性が大きい。アプリケーション７３０は、開始点を判断するための開始点コンポーネント７３０’、及び反復検索を実行するための反復検索コンポーネント７３０’’、並びに他の望ましい又は必要なコンポーネントを含む。コンピュータデバイス７００内には、図７に示しているものよりも多いか又は少ないコンポーネントを含めることができる。一部の実施形態では、動き推定情報を処理するために、動き推定ハードウエア７２０が含まれる。図７のコンピュータデバイス７００は、動き推定処理のためのアプリケーション７３０及びハードウエア７２０を含むが、改善された動き推定処理は、コンピュータデバイスにおいて、ハードウエア、ファームウエア、ソフトウエア、又はこれらのあらゆる組合せに実施することができる。
【００３９】
適切なコンピュータデバイスの例は、パーソナルコンピュータ、ラップトップコンピュータ、コンピュータワークステーション、サーバ、メインフレームコンピュータ、手持ち式コンピュータ、携帯情報端末、セルラー／モバイル電話、スマート家電、ゲーム専用機、デジタルカメラ、デジタルカムコーダー、カメラ電話、ｉＰｏｄ（登録商標）、ホームエンタテインメントシステム、又はあらゆる他の適切なコンピュータデバイスを含む。
【００４０】
推測的開始点反復検索機構を利用するのに、コンピュータデバイスは通常通りに作動するが、動き推定処理は、処理がより効率的かつより正確であるという点で改善される。ユーザから見たコンピュータデバイスの利用は、標準の動き推定を用いるものと同様又は同じである。例えば、ユーザは、変わらずにデジタルカムコーダーを単純に始動し、カムコーダーを用いて映像を記録する。改善された動き推定処理は、映像品質を自動的に改善することができる。例えば、推測的開始点反復検索機構は、映像安定化装置のような動き推定を必要とするあらゆる場合に用いることができる。多くの他のアプリケーションが、この改善された動き推定処理を利用することができる。
【００４１】
作動時には、推測的開始点反復検索機構を用いることにより、反復検索は、いくつかの点で改善される。改善された反復検索は、可能な最良の開始点から始まるので、完全に間違った位置に進むことを回避する。反復検索は、「静的な位置」（０ＭＶ）、カメラパンのような「グローバル移動」（ＧＭＶ）、及び「オブジェクトの動き」（ＰＭＶ）の中から選択された開始ＭＶを用いて、検索範囲の可能な最良の位置の近くの位置から始めることができる可能性が高いので、合計反復回数を低減することができる。最良の位置（例えば、ＭＶ）が大きい場合であっても、反復がグローバルの動きから始まる場合には検索位置に到達することができる。Ｍ．２６４符号器における推測的開始点反復検索機構は、ＳＡＤ計算時間を劇的に短縮する。
【００４２】
極小値回避
反復検索の重要な態様は、次の中心点を如何にして選択するかである。システムが、最小ＳＡＤを有する方向を単純に選択した場合には、システムは、極小値において往来する状況に陥る可能性がある。例えば、ナイーブなシステムは、最小ＳＡＤ点の方向を選択する可能性がある。図８に示している例では、位置８０２が５×５区域８００の最小ＳＡＤ値を有する時には右に進むのが妥当である。次の反復は、右にある５×５区域に対する検索である。しかし、検索は、実際の最小値９０２ではなく、図９に示しているように極小値９００に収まる可能性がある。この場合、次の反復の最小ＳＡＤは、図１０に示している５×５区域内の左の中心１００２である。次に、ナイーブな選択アルゴリズムは、次の検索が、既に検索済みである左の５×５区域に進むように判断する。以降の検索では、最小ＳＡＤは、ここでもまた右の中心であり、検索は往来を続け、極小値に留まる。
【００４３】
極小値に留まることを回避するために、極小値回避検索は、解析される次の方向が、前に解析した方向と反対であるか否かを判断する。検索が次の検索中心に進む前に、検索は、現在の検索の最小ＳＡＤ位置を保持する。図８の場合には、システムは、東に進んでいることを記憶する。
【００４４】
次の検索位置のＳＡＤ計算が完了し、最良のＳＡＤが選出された後に、システムは、以前の反復との「反対方向」に進もうとするか否かを調べる。図１０の場合には、新しい方向は西であり、これは以前の方向と正反対である。これが発生すると、システムは、前に選択した向き（例えば、東）に進むように判断する。反対方向を何回か回避した後に、検索は、極小値１１００を脱出することができ、図１１に示しているように実際の最小値１１０２に向けて移動する。
【００４５】
図１２から図１４は、極小値回避検索の例示的な実施を示している。Ｈ．２６４映像符号器における実施では、システムは、以前の検索の最小ＳＡＤ位置しか記憶しない。５×５検索１２００では、０から２４までの番号が保持される。図１２は、最小ＳＡＤが、東の中位位置にある位置１４であると判断されていることを示している。
【００４６】
反復における次の段階では、新しい最小ＳＡＤ位置が計算された後に、新しい位置が以前の最良の位置と比較される。ルックアップテーブル又は他のマッピング機構に基づいて、方法／システムは、どの位置が反対方向にあると見なされるかを把握することができる。例えば、図１２では以前の段階における最良の位置は１４であり、従って、図１３の陰付き表示位置１３００は、「以前の最良のものと反対である」と見なされる。
【００４７】
新しい位置が、これらの陰付き表示位置１３００のうちのいずれかであった場合には、システムは、この反復を過去の検索位置への「後退」と見なす。この後システムは、基本的な反復規則を無効にして、次の方向として東を選択する。
【００４８】
５×５検索の場合には、一部の適用可能な規則は、図１４に示しているパターンに低減されたものである。他の位置は、図を回転させることによって当て嵌めることができる。以前の検索位置に対して陰付き表示位置１４００が示されており、対応する禁則位置１４０２が、陰付き位置１４００に対向して示されている。一般的に、コーナ位置は、場合によっては延長が反対であると見なされた場合に反対コーナ位置を生じ、側部／上部／底部の位置は、反対位置としてそれぞれの反対側部／底部／上部を有する。
【００４９】
図１５は、単純化された反復検索の流れ図を示している。段階１５００では、５×５検索のＳＡＤが計算される。段階１５０２では、最小ＳＡＤ位置が選択される。次に、段階１５０４では、新しい検索中心が、現在の検索結果に基づいて選択される。処理は、閾値に達するか又は別の基準が満たされるまで指定回数繰り返される。
【００５０】
極小値回避検索のフローを図１６に例示している。新しい検索中心が選択される前に、方向が後退しているか否かを判断するために新しい方向が調べられる。後退している場合には、方向は、以前の方向で置換される。方向は、最小ＳＡＤの位置によって判断される。例えば、最小ＳＡＤが東の中位位置である場合には、方向は東である。方向が東の上位位置であった場合には、方向は北東であり、以下同様である。
【００５１】
具体的には、段階１６００では、５×５区域の各検索位置のＳＡＤが計算される。段階１６０２では、最小ＳＡＤを有する位置が選択される。段階１６０４では、新しい位置の方向が判断される。段階１６０６では、この方向が以前の方向と反対であるか否かが判断される。この方向が反対ではなかった場合には、段階１６０８において新しい位置が保持され、段階１６１０はとばされる。方向が反対であった場合には、段階１６１０において、新しい位置が以前の位置に設定される。次に、段階１６１２では、段階１６０８又は段階１６１０において判断された位置に基づいて新しい検索中心が選択される。処理は、段階１６１４において閾値に達するか又は別の基準が満たされるまで指定回数繰り返される。
【００５２】
一部の実施形態では、「後退」が検出された場合に、同じ方向（例えば、以前の向き）が辿られる。一部の実施形態では、「後退」が検出された場合には、以前の方向と新しい方向の間のどこかである調節された方向が取られる。
例証目的で５×５検索を用いたが、あらゆる適切にサイズの検索が可能である。
【００５３】
上述のように、図７は、コンピュータデバイス７００を示している。コンピュータデバイスは、推測的開始点法を実行することができることに加えて、他のアプリケーションに加えて、又はその代わりに極小値回避を実行することができる。一部の実施形態では、コンピュータデバイス７００は、極小値を回避するための付加的なアプリケーション７３２を含む。一部の実施形態では、極小値回避法は、推測的開始点選択アプリケーション７３０と同じアプリケーション内に実施される。一部の実施形態では、コンピュータデバイス「ＭＥ  ＨＷ」７２０が、極小値を回避するように構成される。極小値回避は、ハードウエア、ファームウエア、ソフトウエア、又はこれらのあらゆる組合せに実施することができる。
【００５４】
極小値回避検索を利用するのに、コンピュータデバイスは通常通りに作動するが、極小値が回避されることになるので、動き推定処理は、処理が、より効率的かつより正確であるという点で改善される。ユーザから見たコンピュータデバイスの利用は、標準の動き推定を用いるものと同様又は同じである。例えば、ユーザは、変わらずにデジタルカムコーダーを単純に始動し、カムコーダーを用いて映像を記録する。極小値回避検索は、映像品質を自動的に改善することができる。例えば、極小値回避検索は、映像安定化装置のような動き推定を必要とするあらゆる場合に用いることができる。多くの他のアプリケーションが、極小値回避処理を利用することができる。
作動時には、極小値回避検索は、反復検索が、連続的に往来して同じ位置を検索することを阻止することによって極小値を回避する。
【００５５】
次検索位置機構
反復検索は、検索範囲の限られた点しか検索することができないので、検索点が効率的に選択されない場合には、画像品質は大きく劣化する。更に、検索点選択は、反復における全ての段階に実施される。従って、意志判断アルゴリズムは好ましくは、高速である。
次検索位置機構は、最小ＳＡＤの位置にのみ基づいて次の検索中心を迅速に判断することができる。
【００５６】
図１７は、作動時の次位置セレクタ１７０２の流れ図を示している。次位置セレクタ１７０２の入力１７００は、現在の検索における最小ＳＡＤの位置である。３×３の場合には、位置は、図１８に示しているように０から８までの番号である。出力１７０４は、現在の検索中心から新しい検索中心までのオフセットである。次に、反復検索は、出力に基づいて移動する。
【００５７】
例えば、最小ＳＡＤの位置が、図１８の位置のうちで「１」とラベル付けされたものである時には、次の検索中心は、現在の検索中心の３ピクセル北になる。従って、現在の検索の検索中心が、位置（１０，１０）にあり、３×３検索区域内の最良／最小のＳＡＤ位置が位置１にある場合には、次の検索中心は、位置（１０，７）に存在することになる。しかし、最小ＳＡＤが位置５にある場合には、次の検索中心は、３ピクセル東になる。従って、現在の検索中心が位置（１０，１０）にある場合には、新しい検索中心は、位置（１３，１０）に存在することになる。
【００５８】
図１８〜図２０は、現在の検索区域の最小ＳＡＤを有する位置に基づく次の検索区域を３×３検索区域において例示している。図１８は、各位置が番号で示された３×３検索を示している。このパターンは、水平、垂直、及び対角位置のみを含む。図１９は、位置１：北（０，−３）、位置３：西（−３，０）、位置７：南（０，３）、及び位置５：東（３，０）という対応する次の検索区域オフセットを有する水平位置（３、５）及び垂直位置（１、７）を示している。図２０は、位置０：北西（−２，−２）、位置６：南西（−２，２）、位置８：南東（２，２）、及び位置２：北東（２，−２）という対応する検索区域オフセットを有する対角位置（０、２、６、８）を示している。
３×３検索区域を説明したが、あらゆる適切な検索区域が可能である。
【００５９】
図２１は、次の位置を選択する方法の流れ図を示している。段階３１００では、検索区域内で最小ＳＡＤを有する位置が判断される。一部の実施形態では、検索区域は３×３ピクセルであり、一部の実施形態では、検索区域は異なるサイズのものである。段階３１０２では、次の検索に向けて、次の検索区域中心点に対するオフセットが、最小ＳＡＤ位置に基づいて自動的に計算／参照される。一部の実施形態では、次の中心点の実際の位置は、現在の中心点に基づいて計算される。段階３１０４では、次の検索区域に向けて中心点が選択される。
【００６０】
次位置セレクタによって用いられる規則は、ルックアップテーブルによって実施することができる。一部の実施形態では、規則は、別の手段によって実施される。一部の実施形態では、ＳＡＤの値自体さえも必要とされない。規則は、最小ＳＡＤの位置を単純に用いて次の検索区域の中心点を判断する。更に、規則は、ルックアップテーブルに実施されるので、これらの規則は、必要に応じて容易に変更することができる。
【００６１】
図２２は、最小ＳＡＤを有する位置に基づいて次の検索区域の中心点を判断するための例示的なルックアップテーブル３２００を示している。上述のように、次の検索区域の中心点に対するオフセットは、最小ＳＡＤ位置に基づいて判断される。図２２に示しているように、最小ＳＡＤが位置０にある場合に、次の検索区域の中心点は、オフセット（−２，−２）の位置に存在する。他の参照値も同様に示されている。図２２は、３×３ピクセルの検索区域を仮定している。他の検索区域では、これらの値は相応に変化することになる。
Ｈ．２６４符号器では、次検索区域選択機構は、簡単な極小値回避検索機構との組合せにおいて、小さいプロセッササイクルで高品質の符号化を提供することができる。
【００６２】
上述のように、図７は、コンピュータデバイス７００を示している。コンピュータデバイス７００は、推測的開始点反復検索機構及び極小値回避法を実行することができることに加えて、他のアプリケーションの代わりに又はそれに加えて次検索位置選択法を実行することができる。一部の実施形態では、コンピュータデバイス７００は、次の検索位置を選択するための付加的なアプリケーション７３４を含む。一部の実施形態では、次検索位置選択法は、アプリケーション７３２又は推測的開始点選択アプリケーション７３０のような同じアプリケーション内に実施される。一部の実施形態では、次の検索位置を選択するためのアプリケーション７３４又はハードウエア７２０は、検索区域の最小ＳＡＤ位置を受け取るための入力コンポーネント７３４’、最小ＳＡＤ位置に基づくオフセットを参照するためのルックアップテーブルのようなマッピングコンポーネント７３４’’、次の検索区域の中心点のオフセットを出力するための出力コンポーネント７３４’’’を含む。一部の実施形態では、オフセットが出力される代わりに又はそれに加えて、次の検索区域の中心点の実際の位置が判断される。一部の実施形態では、コンピュータデバイス「ＭＥ  ＨＷ」７２０は、次の検索位置を選択するように構成される。次検索位置選択は、ハードウエア、ファームウエア、ソフトウエア、又はこれらのあらゆる組合せに実施することができる。
【００６３】
次位置セレクタを利用するのに、コンピュータデバイスは通常通りに作動するが、より良好な検索される次の位置が選択されることになるので、動き推定処理は、処理が、より効率的及びより正確であるという点で改善される。ユーザから見たコンピュータデバイスの利用は、標準の動き推定を用いるものと同様又は同じである。例えば、ユーザは、変わらずにデジタルカムコーダーを単純に始動し、カムコーダーを用いて映像を記録する。次位置セレクタは、映像品質を自動的に改善することができる。例えば、次位置セレクタは、映像安定化装置のような動き推定を必要とするあらゆる場合に用いることができる。多くの他のアプリケーションが、次位置セレクタを利用することができる。
作動時には、次位置セレクタは、次の検索区域の中心点を判断して動き推定の効率を改善する。更に、次位置セレクタは、簡単な機構を用いるので、それは容易に実施される。
【００６４】
精緻化機構
滑らかで平坦な区域では、殆どの位置は、類似のＳＡＤ値を有する。従って、あらゆる動きベクトルが良好な候補であるように見えるので、検索アルゴリズムは容易に欺かれる。しかし、ＭＥが任意の動きベクトルを選択した場合には、係数ではなく動きベクトルヘッダに対してより多くのビットが消費され、本質的な画像品質を低下させる。更に、この場合、ＳＮ比は、それ程影響を受けないが、滑らかな面における矛盾する動きは、不自然な画像を発生させ、本質的な品質を劣化させる。
元の画像が多くのノイズを有する場合には、ＳＡＤの計算は、ノイズによって容易に欺かれる。時としてこれらの不正確な動きベクトルは、ノイズの理由からより小さいＳＡＤ値を有する。しかし、これらの不正確な動きは、人間の目によって容易に見分けられる。
【００６５】
「予測動きベクトル（ＰＭＶ）」を用いて反復検索を精緻化する機構を説明する。ＰＭＶは、隣接マクロブロックから予測される、現在のマクロブロックの最も可能性の高い動きベクトルである。
【００６６】
周辺のマクロブロックの動きベクトルを用いた反復検索のフローを図２３に示している。ＰＭＶ精緻化は、ＰＭＶ位置に２つの可能性を与える。段階３３００では、「グローバル動きベクトル（ＧＭＶ）」、「ゼロ（０）動きベクトル（０ＭＶ）」、及び「予測動きベクトル（ＰＭＶ）」という３つの位置のＳＡＤが計算される。ＧＭＶは、以前に符号化されたフレームの統計からフレーム毎に一度計算され、ＰＭＶは、現在のフレーム内の隣接マクロブロックからの各マクロブロックに対して推定される。最小ＳＡＤを有する位置が、以降の反復検索の開始位置として用いられる。「符号器／復号器（ＣＯＤＥＣ）」によっては、様々な位置を上述したものに限定されない「有望な」位置として選択することができる。上記では３つの位置を説明したが、選択するのに利用可能な位置の個数は、３つに限定されず、それよりも多いか又は少ない位置から選択することができる。
【００６７】
段階３３０２では、システムは、図４で説明した反復検索を実行する。しかし、反復の開始位置は、段階３３００からの最良の開始位置である。ＰＭＶ位置のＳＡＤ値が計算され、０ＭＶ及びグローバルＭＶのような他の位置と比較され、上述のように反復の開始位置が判断される。一部の実施形態では、段階３３００の後に、選択されたＳＡＤが、反復検索の他の実施における開始位置として用いられる。反復検索は、最小ＳＡＤ位置を生じる。段階３３０４では、動きベクトルコストが反復検索の検索結果のＳＡＤに加算され、それに対してＭＶコストはＰＭＶのＳＡＤには加算されない。次に、段階３３０６では、動きベクトルコストが加算された反復検索の検索結果（例えば、最小ＳＡＤ位置）が、ＰＭＶ位置のＳＡＤと再度比較される。動きベクトルコストを有する反復検索結果とＰＭＶのＳＡＤとのうちの小さい方が選択される。段階３３０８では、動きベクトルが精緻化される。その結果は、より短い時間量で処理された滑らかな画像／映像処理である。
ＭＶコストを計算するには様々な手法がある。一般的に、動きベクトルコストは、ＰＭＶからの距離に基づいて計算される。従って、ＭＶコストは、ｐＭＶ位置に加算されない。
【００６８】
図２４は、現在のマクロブロック３４００を隣接マクロブロック３４０２及びそれらの動きベクトルと共に例示している。ＰＭＶは、隣接マクロブロック３４０２から計算される。
【００６９】
精緻化機構は、反復検索が勝手な動きベクトルを選択するのを阻止する。この機構は、滑らかな面においても動きベクトルが適合することになるのに役立ち、動きベクトルヘッダに費やされるビットを節約する。それによって本質的な画像品質が改善される。更に、このシステムは、ノイズの多い映像シーケンスにおいてさえも、欺かれる可能性が低い。
精緻化機構は、ＰＭＶを計算する手法を限定しない。更に、この精緻化機構は、いかなる種類のＭＥアプリケーションにも適用することができる。
【００７０】
上述のように、図７は、コンピュータデバイス７００を示している。コンピュータデバイス７００は、精緻化機構を実行することができる。一部の実施形態では、コンピュータデバイス７００は、精緻化機構を実行するための付加的なアプリケーション７３６を含む。一部の実施形態では、アプリケーション７３６は、開始位置コンポーネント７３６’、反復検索コンポーネント７３６’’、及び付加的な比較コンポーネント７３６’’’を有する。一部の実施形態では、精緻化機構は、前に解説したアプリケーションのうちの１つと同じアプリケーション内に実施される。一部の実施形態では、コンピュータデバイス「ＭＥ  ＨＷ」７２０が、精緻化機構を実施するように構成される。精緻化機構は、ハードウエア、ファームウエア、ソフトウエア、又はこれらのあらゆる組合せに実施することができる。
【００７１】
精緻化機構を利用するのに、コンピュータデバイスは通常通りに作動するが、適正な動きベクトルが選択されることになるので、動き推定処理は、特に、滑らかで平坦な区域において、処理が、より効率的で正確であるという点で改善される。ユーザから見たコンピュータデバイスの利用は、標準の動き推定を用いるものと同様又は同じである。例えば、ユーザは、変わらずにデジタルカムコーダーを単純に始動し、カムコーダーを用いて映像を記録する。精緻化機構は、映像品質を自動的に改善することができる。例えば、精緻化機構は、映像安定化装置のような動き推定を必要とするあらゆる場合に用いることができる。多くの他のアプリケーションが、精緻化機構を利用することができる。
【００７２】
作動時には、精緻化機構は、動きベクトルコストを動きベクトルのＳＡＤに加算し、この値をＰＭＶのＳＡＤと比較することによって適切な動きベクトルを判断する。次に、動きベクトルの精緻化に向けてこれらの２つのうちの低い方が用いられる。この付加的な比較は、映像内の滑らかな平坦区域又はノイズの多い映像から発生する問題を回避するのに役立つ。
【００７３】
閾値を用いた精緻化機構
画像の動きが非常に大きい場合には、上述の精緻化機構は、一部の悪影響を有する。具体的には、システムは、反復検索の検索結果をＰＭＶ位置と比較する。しかし、合計コストがＰＭＶ位置と比較され、この場合、合計コストは「ＳＡＤ＋ＭＶコスト」であり、それに対してＰＭＶの合計コストはＳＡＤのみである。従って、画像内の動きが大きい場合には、ＭＶコストも比較的大きいものである傾向を有する。それによって精緻化機構は、動き推定システムが大きい動きベクトルを生成するのを強く妨害する。
【００７４】
閾値が追加された周辺のマクロブロックの動きベクトルを用いる反復検索のフローを図２５に示している。ＰＭＶ精緻化は、ＰＭＶ位置に２つの可能性を与えるが、閾値は、第２の可能性が有利であるか否かを判断する。段階３５００では、「グローバル動きベクトル（ＧＭＶ）」、「ゼロ（０）動きベクトル（０ＭＶ）」、及び「予測動きベクトル（ＰＭＶ）」という３つの位置のＳＡＤが計算される。ＧＭＶは、以前に符号化されたフレームの統計からフレーム毎に一度計算され、ＰＭＶは、現在のフレーム内の隣接マクロブロックからの各マクロブロックに対して推定される。最小ＳＡＤを有する位置が、以降の反復検索の開始位置として用いられる。「符号器／復号器（ＣＯＤＥＣ）」によっては、様々な位置を上述したものに限定されない「有望な」位置として選択することができる。上記では３つの位置を説明したが、選択するのに利用可能な位置の個数は、３つに限定されず、それよりも多いか又は少ない位置から選択することができる。
【００７５】
段階３５０２では、システムは、図４に説明した反復検索を実行する。しかし、反復の開始位置は、段階３５００からの最良の開始位置である。ＰＭＶ位置のＳＡＤ値が計算され、０ＭＶ及びグローバルＭＶ（ＧＭＶ）のような他の位置と比較され、上述のように反復の開始位置が判断される。一部の実施形態では、段階３５００の後に、選択されたＳＡＤが、反復検索の他の実施における開始位置として用いられる。反復検索は、最小ＳＡＤ位置を生じる。段階３５０４では、動きベクトルコストが反復検索の検索結果のＳＡＤに加算される。一部の実施形態では、段階３５０４の順序と段階３５０６の順序とが入れ替えられる。段階３５０６では、ＧＭＶが閾値と比較される。ＧＭＶが閾値よりも低い場合には、段階３５０８において動きベクトルコストが加算された反復検索の検索結果（例えば、最小ＳＡＤ位置）が、ＰＭＶ位置のＳＡＤと比較される。反復検索結果とＰＭＶのＳＡＤとのうちの小さい方が選択される。段階３５１０では、選択された動きベクトルが精緻化される。段階３５０６でＧＭＶが閾値よりも大きいか又はそれに等しい場合には、段階３５０８における比較は省略され、反復検索の結果は、段階３５１０で精緻化された動きベクトルである。この結果は、より短い時間量で処理された滑らかな画像／映像である。
【００７６】
閾値を用いた精緻化機構は、反復検索が任意の動きベクトルを選択することを阻止し、また、先行ＰＭＶがより大きい動きベクトルを妨害することを阻止する。これは、滑らかな面においてさえも動きベクトルが適合することになることにも役立ち、動きベクトルヘッダに費やされるビットが節約される。それによって画像内の動きが大きい場合に、本質的な画像品質が改善される。
閾値を用いた精緻化機構は、ＰＭＶを計算する手法を限定しない。更に、精緻化機構は、いかなる種類のＭＥアプリケーションにも適用することができる。
【００７７】
上述のように、図７は、コンピュータデバイス７００を示している。コンピュータデバイス７００は、閾値を用いた精緻化機構を実行することができる。一部の実施形態では、コンピュータデバイス７００は、閾値を用いた精緻化機構を実行するための付加的なアプリケーション７３８を含む。一部の実施形態では、アプリケーション７３８は、開始位置コンポーネント７３８’、反復検索コンポーネント７３８’’、閾値コンポーネント７３８’’’、及び付加的な比較コンポーネント７３８’’’’を有する。一部の実施形態では、閾値を用いた精緻化機構は、前に解説したアプリケーションのうちの１つと同じアプリケーション内に実施される。一部の実施形態では、コンピュータデバイス「ＭＥ  ＨＷ」７２０が、閾値を用いた精緻化機構を実施するように構成される。閾値を用いた精緻化機構は、ハードウエア、ファームウエア、ソフトウエア、又はこれらのあらゆる組合せに実施することができる。
【００７８】
閾値を用いた精緻化機構を利用するのに、コンピュータデバイスは通常通りに作動するが、適正な動きベクトルが選択されることになるので、動き推定処理は、特に、滑らかで平坦な区域において、処理が、より効率的かつより正確であるという点で改善される。ユーザから見たコンピュータデバイスの利用は、標準の動き推定を用いるものと同様又は同じである。例えば、ユーザは、変わらずにデジタルカムコーダーを単純に始動し、カムコーダーを用いて映像を記録する。閾値を用いた精緻化機構は、映像品質を自動的に改善することができる。例えば、閾値を用いた精緻化機構は、映像安定化装置のような動き推定を必要とするあらゆる場合に用いることができる。多くの他のアプリケーションが、閾値を用いた精緻化機構を利用することができる。
【００７９】
作動時には、閾値を用いた精緻化機構は、最初に、ＧＭＶと閾値との比較に基づいて反復検索結果とＰＭＶとの比較が適切であるか否かを判断する。適切な場合には、次に、閾値を用いた精緻化機構は、動きベクトルコストを動きベクトルのＳＡＤに加算し、この値をＰＭＶのＳＡＤと比較することによって適切な動きベクトルを判断する。次に、これらの２つのうちで低い方が、動きベクトルの精緻化に用いられる。適切ではない場合には、反復検索結果からの動きベクトルが、精緻化に用いられる。
【００８０】
早期終了機構
反復検索アルゴリズムは、ＳＡＤ計算の回数を低減するが、システム内ではＳＡＤによる電力消費は依然として大きい。従って、反復回数を低減する方法が、次に、電力消費を低減することになる。
反復検索の電力消費を低減するために、反復検索は、「良好な」検索候補が見つかった時に終了される。システムは、１つの段階の最良のＳＡＤを閾値と比較する。最良のＳＡＤ値が閾値よりも小さい場合には、この値は「良好な」検索候補と見なされ、反復は終了される。そうでなければ、検索は通常通りに続行される。
【００８１】
図２６は、閾値を用いた反復検索の流れ図を示している。段階３６００では、処理は、Ｎに等しい計数値で始まり、ここでＮは検索回数である。段階３６０２では、ある一定の領域のＳＡＤが計算される（例えば、３×３領域）。段階３６０４では、段階３６０２の計算に基づいて最小ＳＡＤ位置が選択される。段階３６０６では、最小ＳＡＤが、以前の最良の（例えば、最小の）ＳＡＤと比較され、２つのうちで低い方が保持される。段階３６０８では、段階３６０６における比較を計数するために計数値が１だけ減分される。段階３６１０では、計数値が０であるか否かが判断される。計数値が０である場合には、処理は終了する。計数値が０でない場合には、段階３６１２において、保持されたＳＡＤが、閾値よりも小さいか否かが判断される。ＳＡＤが閾値よりも小さかった場合には、処理は終了する。ＳＡＤが閾値よりも小さくなかった場合には、段階３６１４において次の検索位置が選択される。その後、段階３６０２において始まり、処理は繰り返される。一部の実施形態では、計数の別の実施又は計数の別の順序を用いることができる。
【００８２】
上述のように、図７は、コンピュータデバイス７００を示している。コンピュータデバイス７００は、早期終了機構を実行することができる。一部の実施形態では、コンピュータデバイス７００は、早期終了機構を実行するための付加的なアプリケーション７４０を含む。一部の実施形態では、早期終了機構は、前に解説したアプリケーションのうちの１つと同じアプリケーション内に実施される。一部の実施形態では、アプリケーション７４０は、反復検索のための反復検索コンポーネント７４０’、及び閾値条件が満たされた場合の早期終了のための閾値コンポーネント７４０’’を含む。一部の実施形態では、コンピュータデバイス「ＭＥ  ＨＷ」７２０が、早期終了機構を実施するように構成される。早期終了機構は、ハードウエア、ファームウエア、ソフトウエア、又はこれらのあらゆる組合せに実施することができる。
【００８３】
早期終了機構を利用するのに、コンピュータデバイスは通常通りに作動するが、動き推定処理は、処理がより効率的である点で改善される。ユーザから見たコンピュータデバイスの利用は、標準の動き推定を用いるものと同様又は同じである。例えば、ユーザは、変わらずにデジタルカムコーダーを単純に始動し、カムコーダーを用いて映像を記録する。早期終了機構は、映像品質を自動的に改善することができる。例えば、早期終了機構は、映像安定化装置のような動き推定を必要とするあらゆる場合に用いることができる。多くの他のアプリケーションが、早期終了機構を利用することができる。
【００８４】
作動時には、早期終了機構は、最良のＳＡＤが閾値よりも小さいかを判断する。最良のＳＡＤが閾値よりも小さかった場合には、機構は、残りの計数を完了することなく終了する。早期終了機構は、動き推定がハードウエアに実施される時に反復検索の電力消費を低減する。ソフトウエアに実施される場合には、早期終了機構は、プロセッササイクルを低減し、より高速な符号化速度を生じる。
【００８５】
上述の方法のうちのいずれか及び／又は全てを必要に応じて別々のデバイス又は単一のデバイス上に実施することができる。例えば、デジタルカムコーダーは、推測的開始点法、極小値回避、次検索位置機構、精緻化機構、閾値を用いた精緻化機構、及び早期終了機構を含むことができる。
【００８６】
本明細書では、パターン適合度を計算するために反復検索において実施される距離測定基準としてＳＡＤを説明したが、「絶対移動距離の和」及び「平均二乗誤差」を含むがこれらに限定されない誤差値又は他の距離のような用いることができる多くの他の距離測定基準又は誤差測定基準が存在する。
【００８７】
本発明の構成の原理及び作動の理解を容易にするために、詳細内容が組み込まれた特定的な実施形態を用いて本発明を説明した。本明細書における特定的な実施形態及びその詳細内容への参照は、特許請求の範囲を限定することを意図したものではない。当業者には、特許請求によって定められる本発明の精神及び範囲から逸脱せずに、例示的に選択された実施形態に他の様々な修正を加えることができることが容易に明らかであろう。
【符号の説明】
【００８８】
１００  マクロブロックの映像符号化層、符号器
１０２  入力映像
１１０  イントラ予測モジュール
１１２  動き補償
１１８  ローカル復号器
【図１】
2011528534.tif 000003
【図２】
2011528534.tif 000004
【図３】
2011528534.tif 000005
【図４】
2011528534.tif 000006
【図５】
2011528534.tif 000007
【図６】
2011528534.tif 000008
【図７】
2011528534.tif 000009
【図８】
2011528534.tif 000010
【図９】
2011528534.tif 000011
【図１０】
2011528534.tif 000012
【図１１】
2011528534.tif 000013
【図１２】
2011528534.tif 000014
【図１３】
2011528534.tif 000015
【図１４】
2011528534.tif 000016
【図１５】
2011528534.tif 000017
【図１６】
2011528534.tif 000018
【図１７】
2011528534.tif 000019
【図１８】
2011528534.tif 000020
【図１９】
2011528534.tif 000021
【図２０】
2011528534.tif 000022
【図２１】
2011528534.tif 000023
【図２２】
2011528534.tif 000024
【図２３】
2011528534.tif 000025
【図２４】
2011528534.tif 000026
【図２５】
2011528534.tif 000027
【図２６】
2011528534.tif 000028
【国際調査報告】
2011528534.tif 000029