【手続補正書】
【提出日】平成18年11月15日(2006.11.15)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】  ビデオ符号化アプリケーションで動き推定を行う方法であって、該方法は、
ａ）  ソース・フレーム内の選択されたソース・ブロックのロケーションに対して、ターゲット・フレーム内のターゲット・ブロックの中でマッチング・ブロックの探索（サーチ）を開始する開始ロケーションを見つけるステップと、
ｂ）  前記ソース・フレームからの前記ソース・ブロック内のピクセル・ロケーションにあるピクセル値と、前記開始ロケーションに置かれている前記ターゲット・フレーム内のターゲット・ブロック中の対応するピクセル・ロケーションにあるピクセル値との差分を計算するステップと、
ｃ）  前記開始ロケーションに置かれている前記ターゲット・ブロックに対する結合された動きと誤差信号データの測定量を計算するステップと、
ｄ）  前記探索における後続ターゲット・ブロックについてステップｂとｃを、前記ターゲット・フレーム内でスパイラル・パスに沿って繰り返し、前記結合された動きと誤差信号データについて最小測定量を保つように動作するステップと、
ｅ）  前記探索における前記後続ターゲット・ブロックの各々について、前記ターゲット・ブロックに関連付けられた動きデータの前記符号化オーバー・ヘッドの測定量を計算し、前記符号化オーバー・ヘッドの前記測定量と前記結合された動きと誤差信号データの前記最小測定量と比較して、前記マッチング・ブロックの前記探索を終了するかどうかを決定するステップ
を含むことを特徴とする方法。
【請求項２】  請求項１に記載の方法において、前記ステップｅ）は、
前記符号化オーバー・ヘッドが、結合された動きと誤差信号データの最小測定量より大であるとき、前記最小測定量に関連付けられた前記ターゲット・ブロックの動きベクトルを、前記ソース・ブロックの符号化に使用される動きベクトルとして選択するステップを含むことを特徴とする方法。
【請求項３】  請求項１に記載の方法において、前記結合された動きと誤差信号データの前記測定量は、ターゲット・ブロックに関連付けられた動きベクトルの符号化に必要なビット数の測定量を算入することを特徴とする方法。
【請求項４】  請求項３に記載の方法において、前記結合された動きと誤差信号データの前記測定量は、
Ｋは符号化されるビデオ・シーケンスについて選択された定数、
Ｑｓは量子化ステップ、
Ｂｉｔｓは動きベクトルの符号化に必要なビット数の測定量、および
ＳＡＤは、ソース・ブロック内のピクセル値と、ターゲット・フレーム内で前記スパイラル探索パスに沿ったロケーションに置かれているターゲット・ブロック内の対応するピクセル値との差分の絶対値の総和として表された誤差信号、とした際に、
Ｋ＊Ｑｓ＊Ｂｉｔｓ（動きベクトル）＋ＳＡＤ
で表されることを特徴とする方法。
【請求項５】  請求項１に記載の方法において、前記開始ロケーションは、前記ソース・フレームに含まれる前記ソース・ブロックの近隣ブロックについて以前に計算された動きベクトルから計算されることを特徴とする方法。
【請求項６】  請求項１に記載の方法において、前記スパイラル探索パスは、前記ターゲット・フレーム内のブロック・ロケーションの順序付けられたシーケンスを含み、前記開始ロケーションの後の後続するブロック・ロケーションそれぞれは、開始ロケーションからの距離が増加する位置に置かれていることを特徴とする方法。
【請求項７】  請求項１に記載の方法において、さらに、
前記ソース・フレーム内の前記ソース・ブロックに隣接するブロックの少なくとも１つの動きベクトルから前記開始ロケーションを予測するステップと、
前記予測開始ロケーションが最大動きベクトル・サイズによって制限されていないときは、第１のスパイラル探索パスを使用し、
前記予測開始ロケーションが最大動きベクトル・サイズによって制限されているときは、前記第１のスパイラル探索パスのシフトされた探索順序を使用するステップ、
を含むことを特徴とする方法。
【請求項８】  請求項１に記載の方法において、さらに、
前記ソース・フレームからセグメント化された任意形状のオブジェクトにオーバーラップするソース・オブジェクトについて、前記ステップａ〜ｅを繰り返すステップを含むことを特徴とする方法。
【請求項９】  請求項１に記載の方法において、さらに、
前記ソース・フレーム内のソース・ブロックについて、前記ステップａ〜ｅを繰り返すステップを含むことを特徴とする方法。
【請求項１０】  ビデオ符号化アプリケーションで動き推定を行う方法において、該方法は、
ソース・フレーム内のソース・ブロックについて、ターゲット・フレーム内のターゲット・ブロックの中からマッチング・ブロックを探し出す探索を行うステップであって、
前記ソース・フレームからの前記ソース・ブロック内のピクセル・ロケーションにあるピクセル値と、前記ターゲット・フレームに含まれる前記ターゲット・ブロック内の対応するピクセル・ロケーションにあるピクセル値との差分を計算するステップと、
前記ターゲット・ブロックに対する動きデータであって、量子化係数によって重み付けされている動きデータと、前記ターゲット・ブロックに対する誤差信号データの結合された測定量を計算するステップと
を含む探索ステップと、
前記ターゲット・ブロックに対する結合された動きと誤差信号データの測定量の最小値を有するターゲット・ブロックを前記ターゲット・ブロックの中から選択するステップと、
前記ソース・ブロックと前記選択されたターゲット・ブロックのピクセル間の動きに近似する動きデータを使用して前記ソース・ブロックを符号化するステップと
を含むことを特徴とする方法。
【請求項１１】  請求項１０に記載の方法において、前記ターゲット・ブロックそれぞれは、開始探索ポイントから距離が増加する位置に置かれ、
各ターゲット・ブロックの動きベクトルの符号化オーバー・ヘッドの測定量を計算するステップと、
前記動きベクトルの符号化オーバー・ヘッドの前記測定量を使用して、前記マッチング・ブロックの前記探索を終了するか否かを決定するステップと
を含むことを特徴とする方法。
【請求項１２】  請求項１０に記載の方法において、さらに、
前記ソース・ブロックに対する動きベクトルを予測するステップと、
前記動きベクトルを使用して、前記ターゲット・フレーム内の前記探索の開始ロケーションを予測するステップと、
前記開始ロケーションに近いターゲット・ブロックが、前記開始ロケーションから遠く離れた距離に置かれているターゲット・ブロックよりも先に査定されるように、前記ターゲット・フレーム内のターゲット・ブロックの探索パスを選択するステップと
を含むことを特徴とする方法。
【請求項１３】  ビデオ・シーケンスにおける動き推定のためのブロック・マッチングの方法を実行する命令が格納されているコンピュータ読取可能媒体であって、前記方法は、
ソース・フレームのソース・ブロックについて、ターゲット・フレームの複数のターゲット・ブロックの中からマッチングするターゲット・ブロックを探索するステップであって、探索される各々のターゲット・ブロックについて、
前記探索されるターゲット・ブロックを符号化するための動きベクトル・コストを計算するステップ、
前記動きベクトル・コストを量子化係数で重み付けするステップ、および
前記探索されるターゲット・ブロックのマッチング基準を、前記重み付けされた動きベクトル・コストに少なくとも部分的に基づいて計算するステップ
を含む探索ステップと、
前記探索されるターゲット・ブロックそれぞれに対するそれぞれのマッチング基準に基づいて前記マッチングするターゲット・ブロックを選択するステップと
を含むことを特徴とするコンピュータ読取可能媒体。
【請求項１４】  請求項１３に記載のコンピュータ読取可能媒体において、探索される各々のターゲット・ブロックの前記マッチング基準は、前記探索されるターゲット・ブロックと前記ソース・ブロックとの間の誤差測定量にも、少なくとも部分的に基づいていることを特徴とするコンピュータ読取可能媒体。
【請求項１５】  請求項１３に記載のコンピュータ読取可能媒体において、探索される各々のターゲット・ブロックについて、前記探索ステップは、さらに、
定数により動きベクトル・コストを重み付けするステップを含み、前記定数は、ビデオ・シーケンス全体にわたって符号化コストを低減するように最適化されていることを特徴とするコンピュータ読取可能媒体。
【請求項１６】  請求項１３に記載のコンピュータ読取可能媒体において、前記複数のターゲット・ブロックが探索される際の順序をスパイラル探索パターンが制御することを特徴とするコンピュータ読取可能媒体。
【請求項１７】  請求項１６に記載のコンピュータ読取可能媒体において、前記方法は、さらに、
前記スパイラル探索パターンをシャッフルして、動きベクトル・サイズの制約に対して調整するステップを含むことを特徴とするコンピュータ読取可能媒体。
【請求項１８】  請求項１６に記載のコンピュータ読取可能媒体において、探索される各々のターゲット・ブロックのマッチング基準は、前記探索されるターゲット・ブロックと前記ソース・ブロック間の誤差測定量にも少なくとも部分的に基づき、探索される各々のターゲット・ブロックについて、前記探索ステップは、さらに、
前記探索されるターゲット・ブロックの前記重み付けされた動きベクトル・コストが、以前に探索されたターゲット・ブロックの最良マッチング基準を超えていれば、前記探索を終了させるステップを含むことを特徴とするコンピュータ読取可能媒体。
【請求項１９】  ビデオ符号化アプリケーションで動き推定を行う方法であって、該方法は、
ソース・フレーム内の選択されたソース・ブロックのロケーションに対して、ターゲット・フレーム内のターゲット・ブロックの中でマッチング・ブロックの探索（サーチ）を開始する開始ロケーションを見つけること、
前記開始ロケーションでのターゲット・ブロックの、結合された動きデータと誤差信号データの符号化オーバー・ヘッド測定量を計算すること、
前記探索における１つまたは２つ以上の後続ターゲット・ブロックの各々について、前記後続するターゲット・ブロックに対する動きデータに基づいて最小符号化オーバー・ヘッド測定量を計算し、現在の最良の符号化オーバー・ヘッドの測定量を保持し、前記後続のターゲット・ブロックの前記最小化符号化オーバー・ヘッドの測定量が前記現在の最良符号化オーバー・ヘッドの測定量を越える場合に、前記探索を終了すること
を含むことを特徴とする方法。
【請求項２０】  ビデオ・フレームのシーケンスのソース・フレーム内のソース・ブロックに対する動き推定であって、前記シーケンス内のターゲット・フレーム内のターゲット・ブロックの中でマッチング・ブロックの探索を、前記ターゲット・フレーム内の開始ロケーションから開始することを含む動き推定を行う方法であって、該方法は、
前記開始ロケーションのターゲット・ブロックに対する結合された符号化オーバー・ヘッド測定量を、前記ターゲット・ブロックの動きデータと誤差信号を含む、複数の要素に基づいて計算すること、
前記開始ロケーションの前記ターゲット・ブロックに対する前記結合された符号化オーバー・ヘッド測定量に基づいて、前記ターゲット・フレーム前記ターゲット・ブロックの中で、現在の最良にマッチングするターゲット・ブロック用の、現在の最良の符号化オーバー・ヘッド測定量を初期化すること、
前記ターゲット・フレーム内の、一つまたは複数の後続するターゲット・ブロックのそれぞれに対して、
前記オーバー・ヘッド測定量の前記計算を単純化するように、全ての複数の要素よりも少ない要素に基づいて、前記後続するターゲット・ブロックに対する単純化されたオーバー・ヘッド測定量を、計算すること、および
前記現在の最良の符号化オーバー・ヘッド測定量と、前記後続するターゲット・ブロックを表す前記後続するターゲット・ブロックに対する前記単純化されたオーバー・ヘッド測定量との比較が、現在の最良の符号化オーバー・ヘッド測定量よりも必ず悪いマッチングである場合に、前記探索を終了すること
を含むことを特徴とする方法。
【請求項２１】  前記ターゲット・フレーム内の、一つまたは複数の後続するターゲット・ブロックのそれぞれに対して、
前記比較が、前記現在の最良の符号化オーバー・ヘッド測定量よりも、必ず悪いマッチングであることを示さない場合、前記後続するターゲット・ブロックの前記結合された符号化オーバー・ヘッド測定量を計算すること
をさらに備えることを特徴とする請求項２０に記載の方法。
【請求項２２】  前記後続するターゲット・ブロックに対して前記結合された符号化オーバー・ヘッド測定量を計算することは、前記後続するターゲット・ブロックに対して前記単純化された符号化オーバー・ヘッド測定量から開始すること
を特徴とする請求項２１に記載の方法。
【請求項２３】  前記ターゲット・フレーム内の、一つまたは複数の後続するターゲット・ブロックのそれぞれに対して、
前記後続するターゲット・ブロックに対する前記結合された符号化オーバー・ヘッド測定量を、現在の最良符号化オーバー・ヘッド測定量と比較し、必要に応じて、前記現在の最良符号化オーバー・ヘッド測定量を更新すること
をさらに含むことを特徴とする請求項２１に記載の方法。
【請求項２４】  全ての前記複数の要因よりも少ない要素は、前記後続するブロックに対する動きデータを含み、前記後続ブロックに対する誤差信号は含まないことを特徴とする請求項２０に記載の方法。
【請求項２５】  ビデオ・エンコーダであって、
ソース・フレーム内のソース・ブロックに対するターゲット・フレーム内のターゲット・ブロックの中のマッチング・ブロックを探索する手段であって、前記ターゲット・フレーム内の前記複数のターゲット・ブロックのうちの一つまたは複数のターゲット・ブロックに対する動きデータと誤差データの結合されたコストの測定値を計算する手段を含み、現在のターゲット・ブロックに対する動きデータのコストの測定量が、前記ターゲット・ブロック内の以前のターゲット・ブロックの中の動きデータと誤差信号の結合されたコストの最良の測定値を超えた場合に探索を停止し、探索の停止後に、前記最良の測定量に基づいて、前記ターゲット・フレーム内の前記複数のターゲット・ブロックの中から前記マッチング・ブロックを選択する、探索手段、および
前記ソース・ブロックを、マッチング・ブロックの動きデータに少なくとも部分的に基づいて、符号化する手段
を備えることを特徴とするビデオ・エンコーダ。