(57)【要約】      （修正有）【課題】より効率的なブロック間符号化方法を提供する。【解決手段】ビデオ・シーケンス内の第２の画像を参照して第１の画像内の第１のピクセル・セットを符号化するための方法であり、第２の画像内の第１の検索ウィンドウ内で、第１の画像内の第１のピクセル・セットに最もよく一致する第２の画像内の第１の特定の部分を検索して識別する。第２の画像内の第１の検索ウィンドウ内で、第１の特定の部分に対応する第１のロケーションを識別する。次に、第１のロケーションの近くに画定された第２の画像内の第２の検索ウィンドウ内で、第１の画像内の第１のピクセル・セットに最もよく一致する第２の画像内の第２の特定の部分を検索して識別する。【選択図】図１
2014150568.tif 000002
【特許請求の範囲】
【請求項１】
ビデオ・シーケンス内の第２の画像を参照して第１の画像内の第１のピクセル・セットを符号化するための方法であって、
ａ）第２の画像内の第１の検索ウィンドウ内で、
前記第１の画像内の前記第１のピクセル・セットに最もよく一致する前記第２の画像内の第１の特定の部分を識別するための検索を行うステップと、
前記第２の画像内の前記第１の検索ウィンドウ内で、
前記第１の特定の部分に対応する第１のロケーションを識別するステップと、
ｂ）前記第１のロケーションの近くに画定された前記第２の画像内の第２の検索ウィンドウ内で、前記第１の画像内の前記第１のピクセル・セットに最もよく一致する前記第２の画像内の第２の特定の部分を識別するための検索を行うステップとを含む方法。
【請求項２】
前記第２の画像内の前記第２の検索ウィンドウが前記第２の画像内の前記第１の検索ウィンドウよりも小さい請求項１に記載の方法。
【請求項３】
前記第１の特定の部分を識別するための検索を行う前記ステップが、複数の開始ロケーションから検索するステップを含む請求項１に記載の方法。
【請求項４】
前記第１の検索ウィンドウ内で検索を行う前記ステップが粗検索を含み、前記第２の検索ウィンドウ内で検索を行う前記ステップが微細検索を含む請求項１に記載の方法。
【請求項５】
前記第２の検索ウィンドウ内で検索を行う前記ステップが、
ａ）前記第２の検索ウィンドウ内の複数の検索ポイントを識別するステップと、
ｂ）各々の特定の検索ポイントについて、繰り返し、
ｉ．複数の第２のピクセル・グループを識別するステップと、
ｉｉ．各々の識別された第２のピクセル・グループについての動きベクトル・メトリックを計算するステップと、
ｉｉｉ．各々の第１のピクセル・グループについて最良の第２のピクセル・グループを指定するステップと、
ｉｖ．判定基準が満たされたら残りの前記検索ポイントを見送るステップとをさらに含む請求項１に記載の方法。
【請求項６】
ａ）特定のピクセル・グループに関連する前記指定された第２のピクセル・グループが閾値を超える計算された動きベクトル・メトリックを有するか否かを判定するステップと、
ｂ）前記特定の第１のピクセル・グループに関連する前記指定された第２のピクセル・グループが前記閾値を超えると判定した後で、前記特定の第１のピクセル・グループを以降の検索から除外するステップとをさらに含む請求項５に記載の方法。
【請求項７】
前記第２の検索ウィンドウ内で検索を行う前記ステップの間に前記閾値が動的に定義される請求項６に記載の方法。
【請求項８】
前記第２の検索ウィンドウ内で検索を行う前記ステップが第１のピクセル・レベルで検索を行うステップを含む請求項５に記載の方法。
【請求項９】
前記第２の検索ウィンドウ内で検索を行う前記ステップが第２のピクセル・レベルで検索を行うステップを更に含み、
前記第１のピクセル・レベルが整数ピクセル・レベルであり、前記第２のピクセル・レベルがハーフ・ピクセル・レベルである請求項８に記載の方法。
【請求項１０】
ビデオ・シーケンス内の画像のブロック間符号化方法であって、ビデオ・シーケンス内の
各画像が複数の整数ピクセル・ロケーションを有し、各整数ピクセル・ロケーションが少
なくとも１つの画像値を有し、
ａ）第２の画像を参照して符号化するための第１の画像を選択するステップと、
ｂ）前記第１の画像内のピクセル・セットに一致する前記第２の画像内の非整数ピクセ
ル・ロケーションの第１のセットを識別するステップであって、この識別が、前記第２の
画像内の複数の整数ピクセル・ロケーションの画像値から前記第２の画像内の非整数ピク
セル・ロケーションに関連する画像値を補間するステップを含むステップと、
ｃ）前記第２の画像を参照して第３の画像を符号化する際に使用するために非整数ピク
セル・ロケーションの補間された画像値を記憶するステップとを含む方法。
【請求項１１】
前記第２の画像内の非整数ピクセル・ロケーションのセットを識別した後で、前記第２の
画像内の他の非整数ピクセル・ロケーションのグループの画像値を補間するステップをさ
らに含む請求項１０に記載の方法。
【請求項１２】
非整数ピクセル・ロケーションのグループが非整数ピクセル・ロケーションの前記第１の
セットの近くにある請求項１１に記載の方法。
【請求項１３】
ビデオ・シーケンス内の画像のブロック間復号化方法であって、前記ビデオ・シーケンス
内の各画像が複数の整数ピクセル・ロケーションを有し、各整数ピクセル・ロケーション
が少なくとも１つの画像値を有し、
ａ）第２の画像を参照して復号化するための第１の画像を選択するステップと、
ｂ）前記第１の画像内のピクセル・セットに対応する前記第２の画像内の非整数ピクセ
ル・ロケーションのセットを識別するステップと、
ｃ）前記第２の画像内の複数の整数ピクセル・ロケーションの画像値から前記第２の画
像内の非整数ピクセル・ロケーションに関連する画像値を補間するステップと、
ｄ）前記第２の画像を参照して第３の画像を復号化する際に使用するために前記非整数
ピクセル・ロケーションの補間された画像値を記憶するステップとを含む方法。
【請求項１４】
前記非整数ピクセル・ロケーションに関連する画像値を補間した後で、前記第２の画像内
の他の非整数ピクセル・ロケーションのグループの画像値を補間するステップをさらに含
む請求項１３に記載の方法。
【請求項１５】
非整数ピクセル・ロケーションのグループが前記第１の非整数ピクセル・ロケーションの
近くにある請求項１４に記載の方法。
【請求項１６】
ビデオ画像のシーケンス内の第２の画像を参照して第１の画像内の第１の部分をブロック
間処理する方法であって、
ａ）前記第２の画像をタイルのセットに分割するステップと、
ｂ）前記タイルを第１の非キャッシュ・メモリ記憶域に記憶するステップと、
ｃ）タイルのサブセットが必要な時はいつでも、前記第１の非キャッシュ・メモリ記憶
域から前記タイルのサブセットを取り出すステップと、
ｄ）前記第１の部分と前記取り出されたタイルのサブセットの一部である前記第２の画
像の部分との間で、前記取り出されたタイルのサブセットを第２のキャッシュ・メモリ記
憶域に記憶するステップであって、前記取り出されたタイルのサブセットがタイルのセッ
ト全体よりも小さいステップとを含む方法。
【請求項１７】
前記第１の部分に一致する前記第２の画像内の一部を識別するために検索する前記タイル
のサブセットに対応する前記第２の画像内のロケーションを識別する時に、タイルのサブ
セットを取り出して前記第２のキャッシュ・メモリ記憶域に記憶する必要があると判断す
る請求項１６に記載の方法。
【請求項１８】
前記キャッシュ・メモリ記憶域がコンピュータのランダム・アクセス・メモリである請求
項１６に記載の方法。
【請求項１９】
前記キャッシュ・メモリ記憶域がコンピュータの不揮発性記憶装置である請求項１６に記
載の方法。
【請求項２０】
ブロック間処理方法がブロック間符号化方法である請求項１６に記載の方法。
【請求項２１】
ブロック間処理方法がブロック間復号化方法である請求項１６に記載の方法。
【請求項２２】
前記タイルのセットが少なくとも２つの水平方向に隣接したタイルと少なくとも２つの垂
直方向に隣接したタイルとを含む請求項１６に記載の方法。
【請求項２３】
前記タイルが前記キャッシュ・メモリ記憶域に順次記憶される請求項１６に記載の方法。
【請求項２４】
第１のビデオ画像内の第１のピクセル・セットを符号化するブロック間符号化方法であって、
ａ）前記第１のピクセル・セットに一致する可能性がある第２の画像の複数の部分を検査するパターンを各々が定義する検索パターン・セットから第１の検索パターンを選択するステップと、
ｂ）判定基準セットに基づいて前記検索パターン・セット内の前記第１の検索パターンを適応的に選択するステップとを含む方法。
【請求項２５】
前記判定基準セットが媒体内の画像のシーケンスの解像度符号化を含む請求項２４に記載の方法。
【請求項２６】
前記判定基準セットが隣接する複数の動きベクトルに関する複数の動きベクトルを含む請求項２４に記載の方法。
【請求項２７】
前記判定基準セットがビデオ画像セット内の動きフィールドを含む請求項２４に記載の方法。
【請求項２８】
画像シーケンス内の第２の画像を参照して第１の画像内の第１のピクセル・セットを符号
化するための方法であって、
ａ）第２の画像内の複数の第２のピクセル・セットを識別するステップと、
ｂ）前記第２のピクセル・セットの各々について第１の測定基準評価を計算するステッ
プと、
ｃ）前記第１の測定基準評価に基づいて第２のピクセル・セットのサブセットを識別す
るステップと、
ｄ）識別された第２のピクセル・セットのサブセットから、
ｉ．前記識別された第２のピクセル・セットの各々について第２の測定基準評価を計算
するステップと、
ｉｉ．最良の第２の測定基準評価を有する前記識別された第２のピクセル・セットを選
択するステップであって、選択済みの識別された第２のピクセル・セットが前記第１のピ
クセル・セットと最もよく一致するステップとを含む方法。
【請求項２９】
各々の第２のピクセル・セットが複数の第２のピクセル・グルーピングを含み、各々の第
２のピクセル・グルーピングが複数の第２のピクセル・グループを含む請求項２８に記載
の方法。
【請求項３０】
第１の測定基準評価を計算するステップが、
ａ）各々の第２のピクセル・グルーピングについて第１の測定基準評価を計算するステ
ップと、
ｂ）各々の第２のピクセル・グループについて第１の測定基準評価を計算するステップ
とを含む請求項２９に記載の方法。
【請求項３１】
第２のピクセル・セットのサブセットを識別するステップが、第２のピクセル・グルーピ
ングのサブセットと第２のピクセル・グループのサブセットを識別するステップを含む請
求項３０に記載の方法。
【請求項３２】
前記第２の測定基準評価を計算するステップが、各々の第２のピクセル・グルーピングと
各々の第２のピクセル・グループについて第２の測定基準評価を計算するステップを含む
請求項３１に記載の方法。
【請求項３３】
前記第１の測定基準評価が絶対差の総和（「ＳＡＤ」）測定基準評価である請求項３２に
記載の方法。
【請求項３４】
第２のピクセル・セットのサブセットを識別するステップが最小の第１の測定基準評価を
有する上位Ｎ個の第２のピクセル・セットを選択するステップを含む請求項２８に記載の
方法。
【請求項３５】
第２のレート測定基準評価が、送信するデータの量と送信データに関連する歪の量を定量
化するレート・ディストーション・コストである請求項３４に記載の方法。
【請求項３６】
ａ）最小の第２の測定基準評価を有する上位Ｎ個の第２のピクセル・セットについて第３
の測定基準評価を計算するステップと、
ｂ）最良の第３の測定基準評価を有する識別された第２のピクセル・セットを選択する
ステップであって、選択済みの識別された第２のピクセル・セットが第１のピクセル・セ
ットに最もよく一致するステップとをさらに含む請求項２８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像を符号化および復号化するための方法に関する。
【背景技術】
【０００２】
ビデオ・コーデックは、ビデオ・データ・ストリームを符号化（すなわち、圧縮）およ
び復号化（すなわち、解凍）してストリームのサイズを低減して高速な伝送速度とより小
さい記憶空間を確保するように設計された圧縮アルゴリズムである。損失が大きい現在の
ビデオ・コーデックはビデオ・ストリームのバイナリ・データを圧縮してビデオ品質を維
持しようと努めている。
【０００３】
ビデオ・ストリームは、通常、ビデオ・フレームのシーケンスによって形成される。ビ
デオ・エンコーダは、各フレームを各々が１６×１６ピクセル・セットであるいくつかの
マクロブロックに分割することが多い。ビデオ・エンコーダは、通常、フレーム内符号化
またはフレーム間符号化を用いてビデオ・フレームまたはビデオ・フレーム内のマクロブ
ロックを符号化する。フレーム内符号化されたフレームまたはマクロブロックは、他のフ
レーム内の他のフレームまたはマクロブロックとは独立して符号化されたフレームまたは
マクロブロックである。
【０００４】
フレーム間符号化されたフレームまたはマクロブロックは、他のフレーム内の１つまた
は複数の他のフレームまたはマクロブロックを参照して符号化されたフレームまたはマク
ロブロックである。ブロック間符号化は、通常、時間がかかる。これは符号化が特定のフ
レームのマクロブロックまたはマクロブロック内のパーティションを別の基準フレームの
マクロブロックまたはマクロブロック内のパーティションと比較しなければならないため
である。
【０００５】
したがって、当技術分野で、より効率的なブロック間符号化方法が必要である。理想的
には、そのような符号化方法によって符号化および復号化の演算が高速になる。
【発明の概要】
【０００６】
いくつかの実施形態では、ビデオ・シーケンス内の第２の画像を参照して第１の画像内
の第１のピクセル・セットを符号化するための方法が提供される。この方法は、第２の画
像内の第１の検索ウィンドウ内で、第１の画像内の第１のピクセル・セットに最もよく一
致する第２の画像内の第１の特定の部分を検索して識別する。第２の画像内の第１の検索
ウィンドウ内で、この方法は、第１の特定の部分に対応する第１のロケーションを識別す
る。次に、この方法は、第１のロケーションの近くに画定された第２の画像内の第２の検
索ウィンドウ内で、第１の画像内の第１のピクセル・セットに最もよく一致する第２の画
像内の第２の特定の部分を検索して識別する。
【０００７】
いくつかの実施形態では、ビデオ・シーケンス内の画像をブロック間符号化するための
方法が提供される。ビデオ・シーケンス内の各画像は、各々が少なくとも１つの画像値（
例えば、輝度値）を有するいくつかの整数ピクセル・ロケーションを有する。この方法は
、第２の画像を参照して符号化する第１の画像を選択する。次にこの方法は、第１の画像
内のピクセル・セットに一致する第２の画像内の非整数ピクセル・ロケーションのセット
を識別する。この識別は、第２の画像内のいくつかの整数ピクセル・ロケーションの画像
値から第２の画像内の非整数ピクセル・ロケーションに関連する画像値を補間する処理を
必然的に伴う。この方法は、第２の画像を参照して第３の画像を符号化する際に使用する
ために非整数ピクセル・ロケーションの補間された画像値を記憶する。
【０００８】
いくつかの実施形態では、ビデオ・シーケンス内の画像をブロック間復号化するための
方法が提供される。ビデオ・シーケンス内の各画像は、各々が少なくとも１つの画像値（
例えば、輝度値）を有するいくつかの整数ピクセル・ロケーションを有する。この方法は
、第２の画像を参照して復号化する第１の画像を選択する。次にこの方法は、第１の画像
内のピクセル・セットに対応する第２の画像内の非整数ピクセル・ロケーションのセット
を識別する。この方法は、次に、第２の画像内のいくつかの整数ピクセル・ロケーション
の画像値から第２の画像内の非整数ピクセル・ロケーションに関連する画像値を補間する
。この方法は、第２の画像を参照して第３の画像を復号化する際に使用するために非整数
ピクセル・ロケーションの補間された画像値を記憶する。
【０００９】
いくつかの実施形態では、ビデオ画像のシーケンス内の第２の画像を参照して第１の画
像内の第１の部分をブロック間処理するための方法が提供される。この方法は、第２の画
像をタイルのセットに分割し、タイルを第１の非キャッシュ・メモリ記憶域に記憶する。
第１の画像内の第１の部分を第２の画像内の一部に一致させるためにタイルのサブセット
が必要な時はいつでも、この方法は、第１の非キャッシュ・メモリ記憶域からタイルのサ
ブセットを取り出してこの取り出されたタイルのサブセットを第２のキャッシュ・メモリ
記憶域に記憶して、第１の部分と取り出されたタイルのサブセットの一部である第２の画
像の部分とを高速で比較する。取り出されたタイルのサブセットはタイルのセット全体よ
りも小さい。
【００１０】
いくつかの実施形態で、この方法は、第１の部分に一致する第２の画像内の一部を識別
するために検索する、タイルのサブセットに対応する第２の画像内のロケーションを識別
する時に、タイルのサブセットを取り出して第２のキャッシュ・メモリ記憶域に記憶する
必要があると判断する。いくつかの実施形態では、キャッシュ・メモリ記憶域はコンピュ
ータのランダム・アクセス・メモリであるが、非キャッシュ・メモリ記憶域はコンピュー
タの不揮発性記憶装置である。また、ブロック間処理方法は、いくつかの実施形態ではブ
ロック間符号化方法であるが、別の実施形態では、ブロック間復号化方法である。さらに
、いくつかの実施形態では、タイルのセットは少なくとも２つの水平方向に隣接したタイ
ルと少なくとも２つの垂直方向に隣接したタイルとを含む。
【００１１】
いくつかの実施形態では、第１のピクセル・セットに一致する可能性がある第２の画像
の一部を検査するパターンを各々定義する検索パターンのセットから第１の検索パターン
を選択して第１のビデオ画像内の第１のピクセル・セットを符号化するブロック間符号化
方法が提供される。この符号化方法は、判定基準のセットに基づいて検索パターンのセッ
ト内の第１の検索パターンを適応的に選択する。いくつかの実施形態の判定基準のセット
はビデオ画像の媒体のタイプを含む。
【図面の簡単な説明】
【００１２】
本発明の新規な特徴を添付の特許請求の範囲に記載する。しかし、説明のために、本発
明のいくつかの実施形態を以下の図面で示している。
【図１】符号化プロセスを簡単化するために種々の新規な刈り込み技法を使用するエンコーダの処理のフローを示す概念図である。
【図２】２段階動作の動き推定演算を実行して、１つまたは２つの基準フレームとカレント・フレームとの間のマクロブロックの動作を指定する動きベクトルを識別するプロセスを示す図である。
【図３】いくつかの実施形態が、第１の検索ウィンドウをカレント・フレーム内のマクロブロックのロケーションに対応する基準フレームのロケーションの近くに配置する方法を示す図である。
【図４】カレント・フレーム・マクロブロックに関連する予測動きベクトルに基づいて第１の検索ウィンドウのロケーションを識別する１つの方法を示す図である。
【図５】第１の検索ウィンドウ内の複数の開始ポイントの一例を示す図である。
【図６】第２段階の検索ウィンドウの一例を示す図である。
【図７】カレント・フレーム・マクロブロックのピクセルのパーティション・セットに最もよく一致する基準フレーム内のピクセルのパーティション・セットを識別するために実行される微細動き推定プロセスを示す図である。
【図８】いくつかのロケーション・ポイントを有する検索ウィンドウを示す概念図である。
【図９】多重ピクセル・レベルの基準フレーム・マクロブロックのピクセルのパーティションを検索するプロセスを示す概念図である。
【図１０】いくつかの可能なパーティション（すなわち、ブロック）サイズを示す概念図である。
【図１１】異なるピクセル・レベルのいくつかの検索ロケーションを示す概念図である。
【図１２】基準フレーム内のサブピクセル・ロケーションと位置合わせされたカレント・フレーム・マクロブロックの概念図である。
【図１３】同じフレームをポイントする動きベクトルを含むいくつかのフレームの概念図である。
【図１４】ピクセル・セットに関するデータ（例えば、整数、非整数）をキャッシュに記憶する方法の概念図である。
【図１５】検索ウィンドウ内の低密度検索パターンを示す図である。
【図１６】検索ウィンドウ内の高密度検索パターンを示す図である。
【図１７】垂直方向に偏った検索パターンの一例を示す図である。
【図１８】水平方向に偏った検索パターンの一例を示す図である。
【図１９】動き推定方法のサブセットを選択的に検査してＲＤコストを計算するために必要なサブセットを識別するプロセスを示す図である。
【図２０】本発明のいくつかの実施形態が実施されるコンピュータ・システムを示す図である。
【発明を実施するための形態】
【００１３】
以下の本発明の詳細な説明で、本発明のさまざまな詳細、例、および実施形態を提示し
、説明する。しかし、本発明は提示された実施形態に限定されず、また本発明は説明した
特定の詳細および例示なしで実施することができることは当業者には明らかであろう。
【００１４】
Ｉ．概要
本発明のいくつかの実施形態では、新規なブロック間符号化および復号化プロセスが提
供される。これらの新規なプロセスは、（１）多段動き推定プロセスと、（２）基準フレ
ームの非整数ピクセル・ロケーション値をキャッシュする補間キャッシング・プロセスと
、（３）基準フレームのタイルのサブセットをキャッシュするタイル・キャッシング・プ
ロセスと、（４）基準フレーム内の検索に用いる検索パターンを適応的に選択する動き推
定プロセスとを含む。
【００１５】
Ａ．多段動き推定
いくつかの実施形態の多段動き推定プロセスは、ビデオ・シーケンス内の第２の画像を
参照して第１の画像内の第１のピクセル・セットを符号化する。動き推定プロセスは、第
２の画像内の第１の検索ウィンドウ内で、第１の画像内の第１のピクセル・セットに最も
よく一致する第２の画像内の第１の特定の部分を検索して識別する。第２の画像内の第１
の検索ウィンドウ内で、動き推定プロセスは、第１の特定の部分に対応する第１のロケー
ションを識別する。次に、動き推定プロセスは、第１のロケーションの近くに画定された
第２の画像内の第２の検索ウィンドウ内で、第１の画像内の第１のピクセル・セットに最
もよく一致する第２の画像内の第２の特定の部分を検索して識別する。いくつかの実施形
態では、第１の検索は粗動き推定プロセスで、第２の検索は微細動き推定プロセスである
。さらに、いくつかの実施形態では、微細動き推定プロセスは可変ブロック・サイズを検
索する。
【００１６】
Ｂ．補間キャッシュ
本発明のいくつかの実施形態のエンコーダはビデオ・シーケンス内の画像をブロック間
符号化する。ビデオ・シーケンス内の各画像はいくつかの整数ピクセル・ロケーションを
有し、各整数ピクセル・ロケーションは少なくとも１つの画像値（例えば、輝度値）を有
する。エンコーダは、第２の画像を参照して符号化する第１の画像を選択する。次いでエ
ンコーダは、第１の画像内のピクセル・セットに一致する第２の画像内の非整数ピクセル
・ロケーションのセットを識別する。この識別は、第２の画像内のいくつかの整数ピクセ
ル・ロケーションの画像値から第２の画像内の非整数ピクセル・ロケーションに関連する
画像値を補間する処理を必然的に伴う。エンコーダは、第２の画像を参照して第３の画像
を符号化する際に使用するために非整数ピクセル・ロケーションの補間された画像値を補
間キャッシュ内に記憶する。
【００１７】
本発明のいくつかの実施形態のデコーダも同様の補間キャッシュを使用する。特に、デ
コーダは、第２の画像を参照して復号化する第１の画像を選択する。次いでデコーダは、
第１の画像内のピクセル・セットに対応する第２の画像内の非整数ピクセル・ロケーショ
ンのセットを識別する。デコーダは、次に、第２の画像内のいくつかの整数ピクセル・ロ
ケーションの画像値から第２の画像内の非整数ピクセル・ロケーションに関連する画像値
を補間する。デコーダは、第２の画像を参照して第３の画像を復号化する際に使用するた
めに非整数ピクセル・ロケーションの補間された画像値を記憶する。
【００１８】
Ｃ．タイル・キャッシング・プロセス
いくつかの実施形態は、ビデオ画像のシーケンス内の第２の画像を参照して第１の画像内の第１の部分を処理するブロック間プロセスにタイル・キャッシング・プロセスを使用する。キャッシング・プロセスは、第２の画像をタイルのセットに分割し、タイルを第１の非キャッシュ・メモリ記憶域に記憶する。第１の画像内の第１の部分を第２の画像内の部分に一致させるためにタイルのサブセットが必要な時はいつでも、キャッシング・プロセスは、第１の非キャッシュ・メモリ記憶域からタイルのサブセットを取り出して、この取り出されたタイルのサブセットを第２のキャッシュ・メモリ記憶域に記憶して、第１の部分と取り出されたタイルのサブセットの一部である第２の画像の複数の部分とを高速で比較する。取り出されたタイルのサブセットはタイルのセット全体よりも小さい。
【００１９】
いくつかの実施形態で、キャッシング・プロセスは、第１の部分に一致する第２の画像内の部分を識別するために検索すべき、タイルのサブセットに対応する第２の画像内のロケーションを識別した時に、タイルのサブセットを取り出して第２のキャッシュ・メモリ記憶域に記憶する必要があると判断する。いくつかの実施形態では、キャッシュ・メモリ記憶域はコンピュータのランダム・アクセス・メモリであるが、非キャッシュ・メモリ記憶域はコンピュータの不揮発性記憶装置である。また、ブロック間プロセスは、いくつかの実施形態ではブロック間符号化プロセスであるが、別の実施形態では、ブロック間復号化プロセスである。さらに、いくつかの実施形態では、タイルのセットは少なくとも２つの水平方向に隣接したタイルと少なくとも２つの垂直方向に隣接したタイルとを含む。
【００２０】
Ｄ．適応検索パターン
本発明のいくつかの実施形態の動き推定プロセスは、第１のピクセル・セットに一致す
る可能性がある第２の画像の一部を検査するパターンを各々定義する検索パターンのセッ
トから第１の検索パターンを選択して第１のビデオ画像内の第１のピクセル・セットを符
号化する。動き推定プロセスは、判定基準のセットに基づいて検索パターンのセット内の
第１の検索パターンを適応的に選択する。いくつかの実施形態の判定基準のセットはビデ
オ画像の媒体のタイプを含む。
【００２１】
上記の新規なブロック間符号化および復号化プロセスについて説明する前に、本発明の
ブロック間符号化プロセスを含む符号化プロセスの全体のフローについて以下に説明する
。
【００２２】
ＩＩ．全体フロー
図１は符号化プロセスを簡単化するために種々の新規な刈り込み技法を使用するエンコ
ーダの処理の流れを概念図で示すプロセス１００を示す。いくつかの実施形態では、本章
の刈り込み技法のすべてを使用するわけではない。また、いくつかの実施形態は、ＩＩ章
で後述するこれらの刈り込み技法を多段動き推定演算と併用する。
【００２３】
図１に示すように、プロセス１００はインタブロックとしてのマクロブロックの符号化
を見送るか否かを決定するステップ（１０５）から開始する。いくつかの実施形態では、
ある状況の下でプロセスはブロック間符号化を見送る。これらの状況は、各フレームをイ
ントラブロックとして符号化する処理を必要とするデバッグ・モードにエンコーダを設定
する処理、いくつかのマクロブロックをイントラブロックとして符号化する処理を必要と
するイントラブロック・リフレッシュの指定、ブロック内符号化が最終的に選択されると
いう認識、ブロック内符号化されているマクロブロックの数が少なすぎるという認識、ま
たはマクロブロックをイントラブロックとして符号化することが必要な何か別の指定を含
む。
【００２４】
プロセス１００が、マクロブロックをインタブロックとして符号化する必要がないと判
断すると、プロセスは１１０に進む。１１０で、プロセスはマクロブロックをイントラブ
ロックとして符号化する。ブロック内符号化を実行する種々の新規な方法は、弁理士整理
番号ＡＰＬＥ．Ｐ００７８（「Ｉｎｔｒａｂｌｏｃｋ  Ｅｎｃｏｄｉｎｇ  Ａｐｐｌｉｃ
ａｔｉｏｎ」）を有する「ビデオ・データを符号化するための符号化タイプおよび予測モ
ードの選択」（Ｓｅｌｅｃｔｉｎｇ  Ｅｎｃｏｄｉｎｇ  Ｔｙｐｅｓ  ａｎｄ  Ｐｒｅｄ
ｉｃｔｉｖｅ  Ｍｏｄｅｓ  ｆｏｒ  Ｅｎｃｏｄｉｎｇ  Ｖｉｄｅｏ  Ｄａｔａ）という
名称の米国特許出願に記載されている。この米国特許出願は参照により本明細書に組み込
むものとする。
【００２５】
プロセスがマクロブロックをイントラブロックとして（１１０で）符号化すると、プロ
セスは１５０に進み、符号化方法を指定する。この場合、プロセスは１１０でそのイント
ラコーディングの結果を指定する。これはフローのこのパス内でプロセス１００が探索し
た唯一の符号化方法であるからである。１５０の後で、プロセス１００は終了する。
【００２６】
別の方法としては、プロセス１００がブロック間符号化を見送るべき（すなわち、切り
詰める）でないと（１０５で）決定した場合、プロセスはマクロブロックのスキップ・モ
ード符号化を（１１５で）実行し、必要に応じて、マクロブロックの直接モード符号化を
実行する。スキップ・モード符号化で、マクロブロックはスキップされたマクロブロック
として符号化される。デコーダ側では、このマクロブロックは周囲のマクロブロックおよ
び／または周囲のマクロブロック内のパーティションの動きベクトルを参照して復号化さ
れる。スキップ・モード符号化は、さらに、弁理士整理番号ＡＰＬＥ．Ｐ００７３（「Ｐ
ｒｕｎｉｎｇ  Ａｐｐｌｉｃａｔｉｏｎ」）を有する「ビデオ符号化時の刈り込み」（Ｐ
ｒｕｎｉｎｇ  Ｄｕｒｉｎｇ  Ｖｉｄｅｏ  Ｅｎｃｏｄｉｎｇ）という名称の共願の米国
特許出願に記載されている。この米国特許出願は参照により本明細書に組み込むものとす
る。直接モード符号化は、直接モード符号化では、マクロブロックのテクスチャ・データ
の一部が量子化され、符号化ビット・ストリーム内で送信されるという点を除き、スキッ
プ・モード符号化と同様である。いくつかの実施形態では、直接モード符号化はマクロブ
ロックのＢモード符号化として実行される。また、いくつかの実施形態は、Ｐモード符号
化の際に直接モード符号化を実行する。
【００２７】
１１５の後で、プロセス１００は、スキップ・モード符号化が１１５で最良の符号化方
法であったか否かを（１２０で）判定する。これは明らかに、１１５で直接モード符号化
が実行されなかった時には最良の符号化方法である。他方、１１５で直接モード符号化が
実行され、この符号化が結果的にスキップ・モード符号化より優れた方法の時には、プロ
セスは１３５に進んでインターコーディングを実行する。これについては後述する。
【００２８】
ただし、プロセスが、スキップ・モード符号化が１１５で最良の結果であったと（１２
０で）判定した時には、プロセスはスキップ・モード符号化が符号化を終了するのに十分
優れていたか否かを（１２５で）判定する。そのような判定の１つの方法が上記組み込ま
れた「Ｐｒｕｎｉｎｇ  Ａｐｐｌｉｃａｔｉｏｎ」に記載されている。
【００２９】
スキップ・モード符号化が十分に優れているとプロセスが（１２５で）判定した場合、
プロセス１００は１３０に進み、スキップ・モード符号化方法を廃棄するか否かを決定す
る。いくつかの実施形態は、レート・ディストーション・コスト（ＲＤコスト）と呼ばれ
る符号化コストに基づいて方法を判定する。ＩＩ章で詳述するように、符号化方法のＲＤ
コストは、多くの場合、符号化されたマクロブロックの歪を表し、その符号化方法で生成
される実際のビット数をカウントする。スキップ・モード方法はＲＤコストが大きいこと
があるがそれでも魅力的な方法である。これは、そのような方法がきわめて小さいレート
・コストを有し、そのような小さいレート・コストは全ＲＤコストを大幅にゆがめて、劣
った方法を最良の方法と思わせるためである。
【００３０】
したがって、１２５でスキップ・モード符号化方法を選択した後でも、プロセス１００
はスキップ・モード方法を除去するか否かを（１２５で）判定する。いくつかの実施形態
では、この判定の基準は、現在のマクロブロックのスキップ・モード符号化の歪が現在の
マクロブロックの隣接マクロブロックの最大歪の２倍より大きいか否かである。
【００３１】
プロセスが、スキップ・モード方法を除去しないと（１３０で）決定した場合、プロセ
スは符号化方法を指定する。この場合、プロセスはスキップ・モード符号化方法の結果を
指定する。１５０の後で、プロセス１００は終了する。他方、プロセス１００が、スキッ
プ・モード符号化方法を除去すると（１３０で）決定した場合、１３５に進む。スキップ
・モード方法が符号化を終了させるのに十分優れてはいないと（１２５で）判定した場合
も、プロセスは１３５に進む。
【００３２】
１３５で、プロセスは種々のブロック間符号化を検査する。いくつかの実施形態では、
プロセス１００は種々のマクロブロックとサブマクロブロック符号化（例えば、１６×１
６、８×１６、１６×８、８×８、８×４、４×８、および４×４ＢモードおよびＰモー
ド符号化）を探索することがある。これについてはＩＩ章で詳述する。ただし、上記組み
込まれた「Ｐｒｕｎｉｎｇ  Ａｐｐｌｉｃａｔｉｏｎ」に記載されているように、いくつ
かの実施形態は、マクロブロックまたはサブマクロブロック符号化モードのいくつかの探
索および／または分析を切り詰め（すなわち、見送り）、ブロック間符号化プロセスを高
速化する。
【００３３】
１３５でブロック間符号化を実行した後、プロセスはマクロブロックのブロック間符号
化がマクロブロックのブロック内符号化を見送るほど優れているか否かを（１４０で）判
定する。別の実施形態ではこの判定方法が異なる。これらの手法のいくつかについてＩＩ
章で詳述する。
【００３４】
プロセス１００が、ブロック内符号化を実行すると（１４０で）決定すると、１４５に
進み、この符号化を実行する。上記のように、このプロセスのブロック内符号化のいくつ
かの新規な特徴は上記組み込まれた「Ｉｎｔｒａｂｌｏｃｋ  Ｅｎｃｏｄｉｎｇ  Ａｐｐ
ｌｉｃａｔｉｏｎ」に記載されている。１４５の後で、プロセスは１５０に進む。プロセ
スはブロック内符号化を見送ると（１４０で）決定した場合も、１５０に進む。
【００３５】
上記のように、プロセスはマクロブロックの符号化方法を（１５０で）指定する。プロ
セス１００が１５０の前にその動作中に複数の符号化方法を識別すると、プロセスはこれ
らの方法の１つを（１５０で）選択する。いくつかの実施形態では、プロセス１００は最
良のＲＤコストを有する方法を選択する。ＲＤコストのいくつかの例を以下に示す。１５
０の後で、プロセスは終了する。
【００３６】
ＩＩＩ．ブロック間符号化
Ａ．多段動き推定
上記のように、いくつかの実施形態は、多段動き推定演算を図１に示すプロセス１００
と併用する。いくつかの実施形態では、多段動き推定演算はマクロブロックをブロック間
符号化する時に実行される。以下に述べるように、いくつかの多段動き推定演算は粗動き
推定と微細動き推定とを含む。いくつかの実施形態では、プロセス１００は初期の粗動き
推定演算の後に実行される。しかし、初期の粗動き推定演算は、また、プロセス１００中
に（例えば、ステップ１０５とステップ１１５との間のステップ１４０で）実行できるこ
とは当業者には明らかであろう。
【００３７】
１．全体フロー
図２は、１つまたは２つの基準フレームとカレント・フレームとの間のマクロブロック
の動きを指定する動きベクトルを識別する多段動き推定演算を実行するプロセスを示す図
である。本発明の多段動き推定演算の説明を分かりにくくしないために、単一の基準フレ
ーム内のカレント・フレーム・マクロブロックの位置を発見する処理に関してプロセス２
００を以下に説明する。しかし、このプロセスはしばしば２つの基準フレームを探索して
マクロブロックの最良の動き推定符号化を識別することは当業者には明らかであろう。
【００３８】
このプロセスの第１段階は、基準フレーム内のカレント・フレーム・マクロブロックの
位置の粗近似を識別する粗検索（例えば、粗動き推定）である。第２段階は、基準フレー
ム内のカレント・フレーム・マクロブロックの位置のより高精度の近似を識別するより微
細検索（例えば、微細動き推定）である。
【００３９】
プロセスは最初、カレント・フレーム・マクロブロックに最もよく一致するマクロブロ
ックの基準フレームの第１の検索を（２１０で）実行する。第１の検索は基準フレーム内
の第１の検索ウィンドウ内で実行される。別の実施形態は第１の検索ウィンドウの位置を
異なって識別する。例えば、図３に示すように、いくつかの実施形態は、第１の検索ウィ
ンドウ３００をカレント・フレーム内のマクロブロック３３０のロケーション３２０に対
応する基準フレームのロケーション３１０の近くに配置する。
【００４０】
別の実施形態は、第１の検索ウィンドウを基準フレーム内のカレント・フレーム・マク
ロブロックの指定のロケーションに配置する。図４は、カレント・フレーム・マクロブロ
ックに関連する予測動きベクトルに基づいて第１の検索ウィンドウのロケーションを識別
する１つの方法を示す図である。図４はカレント・フレーム４００内のカレント・フレー
ム・マクロブロック４１０を示す。この図はまた、カレント・フレーム・マクロブロック
４１０に関連する予測動きベクトル４２０を示す。この予測動きベクトル４２０は、カレ
ント・フレーム内のカレント・フレーム・マクロブロック４１０に隣接するマクロブロッ
クの動きベクトルに基づいて計算できる。図４に示すように、予測動きベクトル４２０は
基準フレーム４３０内のロケーション４４０に対応するカレント・フレーム４００内のロ
ケーション・ポイント４６０をポイントする。したがって、図４にさらに示すように、い
くつかの実施形態は、基準フレーム４３０内の第１の検索ウィンドウ４５０をロケーショ
ン・ポイント４４０の近くに配置する。
【００４１】
プロセス２００は、カレント・フレーム・マクロブロックが基準フレーム内に出現して
から動いた量を指定する動きベクトルを識別しようとして第１の検索ウィンドウ内で粗検
索を（２１０で）実行する。プロセスは、カレント・フレーム・マクロブロックに最もよ
く一致する第１の検索ウィンドウ内で基準フレーム・マクロブロックを検索することでこ
の動きベクトルを識別できる。プロセスは、検索ウィンドウ内のすべての基準フレーム・
マクロブロックを参照するわけではなく、ある種の所定のパラメータの範囲にあるマクロ
ブロックを決定するのに十分なだけ参照する。
【００４２】
プロセスが十分な基準フレーム・マクロブロックを識別すると、この粗検索で遭遇する
最良の基準フレーム・マクロブロックを（２１０で）識別する。次いで、プロセスは識別
された最良の基準フレーム・マクロブロックを（２１０で）用いて基準フレーム内のカレ
ント・フレーム・マクロブロックのロケーションの粗近似を示す動きベクトルを指定する
。
【００４３】
２１０の後で、プロセスは第１の検索ウィンドウ内で粗検索を十分に繰り返したか否か
を（２２０で）判定する。いくつかの実施形態は、このウィンドウ内で１回の検索しか実
行しない。そのような実施形態では、プロセス２００は２２０で判定する必要がなく、そ
の代わりに、２１０から直接２３０に進む。あるいは、他の実施形態は、このウィンドウ
内で、複数の異なるポイントで開始する複数の検索を実行する。
【００４４】
プロセス２００が、第１の検索ウィンドウ内で、別の粗検索を実行すると（２２０で）
決定した場合、プロセスは２１０に戻って、マクロブロックに関して２１０で実行された
他の以前の粗検索とは異なるロケーションで開始する別の検索（このウィンドウ内の）を
実行する。
【００４５】
図５は、第１の検索ウィンドウ内の複数の開始ポイントの一例を示す図である。特に、
この図は第１の検索ウィンドウ５００内の４つの開始ポイント５１０〜５４０を示す。各
開始ポイント５１０〜５４０は異なる基準フレーム・マクロブロックを識別する検索を実
行する。いくつかの実施形態では、異なる開始ポイントが同じ基準フレーム・マクロブロ
ックを識別してもよい。
【００４６】
プロセスが第１の検索ウィンドウ内で粗検索を十分に繰り返したと（２２０で）判定し
た場合、２１０までの１つまたは複数の繰り返しで識別した最良の可能な粗い段階の方法
を（２３０で）識別する。図６に示すように、この方法は、基準フレーム内のロケーショ
ン６３０に対応するカレント・フレーム内のマクロブロック４１０のロケーション６１０
を識別する動きベクトル６２０を識別する。
【００４７】
次に、プロセスはカレント・フレーム・マクロブロックに一致する基準フレーム・マク
ロブロックの第２の微細動き推定検索を（２４０で）実行する。第２の検索は基準フレー
ムの第２の検索ウィンドウ内で実行される。いくつかの実施形態では、この第２の検索ウ
ィンドウは２１０の粗い第１段階の検索で使用した第１の検索ウィンドウよりも小さい。
また、いくつかの実施形態では、第２の検索ウィンドウは、第１段階の検索によって（す
なわち、２３０で選択された動きベクトルによって）生成された動きベクトルによって識
別された基準フレーム内の位置の近くに画定される。図６はそのような第２段階の検索ウ
ィンドウの一例を示す図である。特に、この図は、第１の検索で指定されたロケーション
・ポイント６３０の近くの第２の検索ウィンドウ６４０を示している。
【００４８】
いくつかの実施形態では、第２の検索段階で（２４０で）使用した検索プロセスは第１
の検索段階で使用した検索プロセスよりもはるかに徹底している。例えば、いくつかの実
施形態は、第２段階ではレート・ディストーション最適化を利用する詳細なサブマクロブ
ロック検索を使用するが、第１の検索段階ではより簡単な３ステップの検索を使用する。
【００４９】
２４０の第２の検索段階の最後に、プロセス２００は、カレント・フレーム・マクロブ
ロックが基準フレーム内に出現してから動いた量を指定する動きベクトルを提供する。２
４０の後で、プロセスは終了する。
【００５０】
２．微細動き推定
図７は、カレント・フレーム・マクロブロックのピクセルのパーティション・セットに
最もよく一致する基準フレーム内のピクセルのパーティション・セットを識別するために
実行される微細動き推定プロセス７００を示す図である。いくつかの実施形態では、プロ
セス７００はプロセス２００の第２の検索（２４０）中に実施される。
【００５１】
この図に示すように、プロセス７００は検索ウィンドウ内でロケーション・ポイントを
（７０５で）選択する。いくつかの実施形態では、検索ウィンドウは最初はプロセス２０
０の２３０で識別された微細基準フレーム・マクロブロックの近くに画定される。
【００５２】
図８は、いくつかのロケーション・ポイントを有する検索ウィンドウ８００を示す概念
図である。この図に示すように、検索ウィンドウ８００は、９つのロケーション・ポイン
ト８０５〜８４５を含む。いくつかの実施形態では、これらのロケーション・ポイント８
０５〜８４５はランダムに生成できる。別の実施形態では、これらのロケーション・ポイ
ント８０５〜８４５は判定基準のセットによって事前に規定されている。これらのロケー
ション・ポイント８０５〜８４５の各々は整数ピクセル・レベルの基準フレーム・マクロ
ブロックに対応する。さらに、図８は、ハーフおよびクォータ・ピクセル・レベルのロケ
ーション・ポイントなどの非整数ピクセル・レベル（すなわち、サブピクセル・レベル）
のロケーション・ポイントを示す。これらのサブピクセル・レベルのロケーション・ポイ
ントの使用法について図９を参照しながら詳述する。
【００５３】
次に、カレント・フレーム・マクロブロック内のピクセルの各々の可能なパーティショ
ンについて、プロセス７００は選択されたロケーション・ポイントの特定のピクセルのパ
ーティションがカレント・フレーム・マクロブロックのピクセルのパーティションにどの
程度一致するか（７１０で）検査する。図１０は、いくつかの可能なパーティション（す
なわち、ブロック）サイズを示す概念図である。特に、この図は、各ブロック・サイズが
特定のピクセル・ブロックを表す９つの可能なブロック・サイズを示す。例えば、ブロッ
ク・サイズ１は１６×１６のピクセル・アレイを含むピクセル・ブロックを表す。ブロッ
ク・サイズ２は１６×８のピクセル・アレイを含むピクセル・ブロックを表す。この図は
９つのブロック・サイズしか示していないが、プロセス７００は他のピクセル構成のブロ
ック・サイズを検索することができる。いくつかの実施形態は、これらのブロック・サイ
ズをすべて検索するが、別の実施形態は、これらのブロック・サイズの一部しか検索しな
い。
【００５４】
検査が（７１０で）実行されると、プロセス７００は各ブロック・サイズの基準フレー
ム・マクロブロックの最良のロケーションを（７１５で）更新する。プロセス７００は、
別のロケーション・ポイントがあるか否かを（７２０で）判定する。ある場合、プロセス
７００は７０５に進んで別のロケーション・ポイントを選択し、ステップ７１０〜７２０
をもう１回繰り返す。
【００５５】
プロセス７００がもうロケーション・ポイントはないと（７２０で）判定すると、プロ
セス７００はあるブロック・サイズの検索結果が良好であるか否かを（７２５で）判定す
る。いくつかの実施形態では、更新されたロケーションを有するブロック・サイズが一定
の判定基準（例えば、一定のしきい値より下のＳＡＤ）を満たしていれば、検索結果は良
好である。いくつかの実施形態では、特定のブロック・サイズに関連するコストと最小の
コストを有するブロック・サイズに関連するコストとの差がしきい値を超えている場合、
検索結果は良好ではない。いくつかの実施形態では、しきい値は検索中に動的に定義され
る。プロセス７００があるブロック・サイズの検索結果が良好ではないと（７２５で）判
定すると、プロセス７００は以降のどの検索でもこれらのブロック・サイズを（７３０で
）除外する。
【００５６】
これらのブロック・サイズを（７３０で）除外した後、またはすべての検索結果が良好
であると（７２５で）判定した後で、プロセス７００は別の検索を（７３５で）実行する
。この検索中、各ブロック・サイズについて、プロセス７００はカレント・フレーム・マ
クロブロックのパーティションに最もよく一致する基準フレーム内のピクセルのパーティ
ションを検索する。この検索は、サブピクセル・レベルでのピクセルのパーティションの
検索を含む。このサブピクセル・レベル検索について以下に詳述する。（７３５の）検索
の後で、プロセス７００は終了する。
【００５７】
３．サブピクセル・レベルでの検索
図９は、多重ピクセル・レベルの基準フレーム・マクロブロックのピクセルのパーティ
ションを検索するプロセス９００を示す概念図である。いくつかの実施形態では、プロセ
ス９００はプロセス７００の検索７３５中に実行される。この図に示すように、プロセス
９００は、カレント・フレーム・マクロブロックのピクセルのパーティションを（９０５
で）選択する（すなわち、ブロック・サイズを選択する）。プロセス９００は９０５まで
を数回繰り返す。９０５までの繰り返しで、いくつかの実施形態のプロセスは、図１０に
示す数字指定に基づいて７３０で順次廃棄されなかったパーティション（すなわち、ブロ
ック）を繰り返し選択する。例えば、７３０でどのパーティションも廃棄されなかった場
合、プロセス９００はブロック１〜９を順次選択する。
【００５８】
９０５の後、プロセス９００は検索の初期ピクセル解像度（例えば、ピクセル・レベル
）を（９１０で）定義する（すなわち、検索の粒度を定義する）。例えば、プロセス９０
０は最初、ピクセル解像度を整数ピクセルで１ロケーションおき（すなわち、整数のピク
セル・レベル解像度の半分の解像度）と定義できる。次に、プロセス９００は、検索ロケ
ーションを、カレント・フレーム・マクロブロックの選択されたパーティションのこれま
でに識別されたうち最良のロケーションと（９１５で）定義する。この最良と識別された
ロケーションは、図７のプロセス７００のピクセル・レベル検索中に識別でき、または、
以下に詳述するように、図９のプロセス９００のピクセル解像度検索のいずれかの実行中
に識別できる。
【００５９】
７３０で廃棄されなかった特定のカレント・フレーム・パーティションの各々について
、プロセス９００は、（９２０で）（１）定義されたピクセル・レベル解像度（すなわち
、検索の粒度）で９１５で識別された検索ロケーション近くの基準フレーム・パーティシ
ョンを検査し、（２）カレント・フレーム・パーティションに最もよく一致する特定の検
査済の基準フレーム・パーティションを識別する。
【００６０】
次いで、７３０で廃棄されなかった特定のカレント・フレーム・パーティションの各々
について、プロセス９００は、（９２５で）特定のカレント・フレーム・パーティション
の９２０で識別された特定のカレント・フレーム・パーティションが特定のカレント・フ
レーム・パーティションの以前に識別された最高の一致よりもよい一致であるか否かを判
定する。そうである場合、プロセスは９２０で識別された特定の基準フレーム・パーティ
ションのロケーションを特定のカレント・フレーム・パーティションの最良のロケーショ
ンとして（９２５で）定義する。
【００６１】
次に、プロセス９００は、選択されたパーティションの最大ピクセル・レベル解像度で
基準フレームを検査したか否かを（９３０で）判定する。そうでない場合、プロセス９０
０はピクセル・レベル解像度を次のピクセル・レベル解像度（例えば、半分、４分の１）
に（９３５で）増やし、９１５に戻る。これについては前述の通りである。したがって、
ステップ９１５〜９３５の以降の繰り返しで、プロセス９００はサブピクセル・レベル（
例えば、半分、４分の１）でカレント・フレーム・マクロブロックのパーティションを検
査する。
【００６２】
プロセス９００が、選択されたパーティションの最大ピクセル・レベル解像度で基準フ
レームを検査したと（９３０で）判定した場合、プロセス９００は、７３０で廃棄されな
かったすべてのカレント・フレーム・パーティションを検査したか否かを（９４０で）判
定する。そうでない場合、プロセス９００は９０５に戻って次のカレント・フレーム・パ
ーティションを選択し、このパーティションについてステップ９１０〜９３５を繰り返す
。プロセス９００は、７３０で廃棄されなかったすべてのピクセルのパーティションを検
査したと（９４０で）判定すると、終了する。
【００６３】
図１１は、異なるピクセル・レベルのいくつかの検索ロケーションを示す概念図である
。特に、この図は、４つの整数ピクセル・レベルロケーション８２５〜８３０と８４０〜
８４５とによって区切られた検索領域８６０を示す。いくつかの実施形態では、この区切
られた検索領域８６０は、図８に示すように、検索ウィンドウ８００内にある。
【００６４】
区切られた検索領域８６０内には５つのハーフ・ピクセル・レベル・ロケーションがあ
る。さらに、この区切られた検索領域８６０内には、１６のクォータ・ピクセル・レベル
・ロケーションがある。別の実施形態では、これより多い、または少ない整数および非整
数のロケーションを含む別の区切られた検索領域を指定できる。いくつかの実施形態は、
プロセス９００が検索ロケーションをロケーション８５０と（９１５で）定義している時
には、９２０での検索時にこの区切られた検索領域８６０の内部および周囲を検索できる
。
【００６５】
いくつかの実施形態では、上記のステップのいくつかの繰り返しが実行される。上記の
ように、いくつかの実施形態は、ピクセル・レベルごとに別途検索を行う。ただし、いく
つかの実施形態では、異なるピクセル・レベルでいくつかのブロック・サイズを検索ロケ
ーションごとに同時に検索できる（すなわち、すべてのブロック・サイズについて整数、
ハーフおよびクォータ・ピクセル・レベルで同時に各ロケーションについて検索できる）
ことは当業者には明らかであろう。サブピクセル・レベルはハーフおよびクォータ・ピク
セル・レベルとして説明しているが、サブピクセル・レベルは任意の非整数ピクセル・レ
ベルでよいことは当業者には明らかであろう。
【００６６】
さらに、プロセス７００は、あるブロック・サイズの検索結果が良好か否かを（７２５
で）判定すると記述している。いくつかの実施形態では、この判定７２５は、プロセス９
００中に行ってもよい。さらに、この判定７２５はプロセス７００および９００の異なる
ステップ中に実行してもよいことは当業者には明らかであろう。例えば、各ブロック・サ
イズの最良のロケーションを見つけた後でそのような判定プロセス７２５を実行してもよ
い。
【００６７】
さらに、いくつかの実施形態は、プロセス７００中に７３５で検索を実行しない。また
、上記プロセス７００および９００は基準フレーム・マクロブロックの検索を実行すると
記述してあるが、プロセス７００および９００を用いて他のタイプのピクセル・アレイ（
例えば、１６×８のサブマクロブロック）を検索できることは当業者には明らかであろう
。
【００６８】
Ｂ．キャッシュ補間値
図１２は、基準フレーム内のいくつかのピクセルおよびサブピクセル・ロケーションを
示す概念図である。これらのサブピクセル・ロケーションはハーフおよびクォータ・ピク
セル・ロケーションを含む。この図に詳細に示すように、カレント・フレーム・マクロブ
ロック１２００はクォータ・サブピクセル・ロケーション１２０５と位置合わせされてい
る（すなわち、カレント・フレーム・マクロブロック内のピクセル・ロケーションは基準
フレーム内のクォータ・サブピクセル・ロケーションと揃っている）。
【００６９】
上記のように、エンコーダは、いくつかの実施形態の動き推定演算中に、基準フレーム
内のサブピクセル・ロケーションと位置合わせされた（すなわち、ピクセル・ロケーショ
ンと位置合わせされていない）マクロブロックまたはマクロブロック・パーティションを
検査する。いくつかの実施形態のデコーダは、また、場合によっては、基準フレームから
サブピクセル・ロケーションと位置合わせされた（すなわち、ピクセル・ロケーションと
位置合わせされていない）マクロブロックまたはマクロブロック・パーティションを取り
出す必要がある。
【００７０】
サブピクセル・ロケーションと位置合わせされたマクロブロックまたはマクロブロック
・パーティションの検査および取り出しを行うには、エンコーダまたはデコーダが、復号
化演算時のカレント・フレーム内のピクセル・ロケーションに対応し、符号化演算時にカ
レント・フレーム内のピクセル・ロケーションと比較する必要があるサブピクセル・ロケ
ーションの基準フレームの画像値（例えば、輝度値）を生成することが必要である。
【００７１】
いくつかの実施形態では、サブピクセル・ロケーションに対応する画像値の生成は、隣
接するピクセル・ロケーションの画像値から画像値を補間する（すなわち、ピクセル・ロ
ケーションの画像値からサブピクセル・ロケーションの画像値を抽出する）処理を必然的
に伴う。多くの場合、サブピクセル・ロケーションの画像値の補間は２つの最も近い隣接
したピクセル・ロケーションの画像値を単に計算する以上の処理を必然的に伴う困難な演
算（例えば、計算が高価な演算）である。したがって、いくつかの実施形態は、サブピク
セル・ロケーションの補間された画像値をキャッシュに記憶する。この画像値は、別のカ
レント・フレーム・パーティションの以降の検索がサブピクセル・ロケーションの上記の
補間された画像値を検査しようとする時には容易に取り出すことができる。いくつかの実
施形態はすべての補間された値をキャッシュに記憶するが、別の実施形態は補間された値
の一部しかキャッシュに記憶しない。
【００７２】
符号化および／または復号化演算中、カレント・フレーム・マクロブロックのセットの
多くの動きベクトルが同じ基準フレームをポイントする。例えば、図１３に示すように、
フレーム１３１０はフレーム１３０５および１３２５を参照して定義された動きベクトル
を有する。さらに、両方のフレーム１３１５および１３２０はフレーム１３０５を参照し
て定義された動きベクトルを有する。したがって、ある実施形態の場合には、他の複数の
フレームを符号化、または復号化するために基準フレームを使用できる。この結果、基準
フレームについて補間されたすべての、またはいくつかのサブピクセル値をキャッシュに
入れることが必要である。これは、サブピクセル値が他のフレームの符号化に使用できる
ためである。
【００７３】
Ｃ．キャッシュ・タイリング
図１４は、基準フレームをキャッシュに記憶するための方法を示す概念図である。いく
つかの実施形態では、この方法は上記の補間演算と併用される。この図に示すように、基
準フレーム１３０５はいくつかのタイル１４３０に分割される。いくつかの実施形態では
、フレーム１３０５は複数のタイルの列と複数のタイルの行とを含むように分割される。
【００７４】
図１４はさらに基準フレーム内のピクセル・ロケーションと位置合わせされたまたはさ
れていないピクセル・ブロック１４５０を示す。ピクセル・ブロック１４５０は符号化演
算時に（すなわち、動き推定時に）検査されるかまたは復号化演算時に取り出される基準
フレームの一部を表す。
【００７５】
図１４に示すように、タイル１４３０ａ〜１４３０ｄの一部はピクセル・ブロック１４
５０を検査または取り出すために必要である。したがって、符号化または復号化演算時に
ピクセル・ブロック（ピクセル・ブロック１４５０など）の検査を容易にするために、い
くつかの実施形態では、基準フレーム１３０５をそのタイルに関してキャッシュに入れる
。言い換えれば、基準フレーム１３０５全体にわたるピクセルの行（例えば、ピクセル・
ブロック１４５０を含むピクセル行１４０１〜１４２５）をキャッシュに入れる代わりに
、いくつかの実施形態では、基準フレーム内のタイルをキャッシュに入れるだけである。
【００７６】
特定のピクセル・ブロックの分析のためにタイルのセットが必要な時には、これらの実
施形態のエンコーダまたはデコーダは特定のピクセル・ブロックが重なっているすべての
タイルがキャッシュに入っているか否かを判定する。そうである場合、エンコーダまたは
デコーダはキャッシュに入っているタイルを用いて特定のピクセル・ブロックを処理する
。そうでない場合、エンコーダまたはデコーダは、（１）非キャッシュ記憶域から所望の
タイル（すなわち特定のピクセル・ブロックと重なるが現在キャッシュに入っていないタ
イル）を取り出し、（２）これらのタイルをキャッシュに記憶し、次に、（３）これらの
タイルを用いて特定のピクセル・ブロックを処理する。例えば、ピクセル・ブロック１４
５０を処理しようとする場合、エンコーダまたはデコーダはこのブロックがタイル１４３
０ａ〜１４３０ｄに重なっていると判定する。したがって、エンコーダまたはデコーダは
これらのタイル１４３０ａ〜１４３０ｄをキャッシュに入れ（まだ入っていない場合）、
次に、これらのタイルを用いてブロック１４５０を処理する。
【００７７】
いくつかの実施形態では、キャッシュ記憶域は符号化または復号化演算を実行するため
のコンピュータ・システムのプロセッサのキャッシュである。別の実施形態では、キャッ
シュ記憶域は符号化または復号化演算を実行するためのコンピュータ・システムの揮発性
メモリ（例えば、ランダム・アクセス・メモリ）の専用の領域である。また、図１４はキ
ャッシュ処理のための正方形のタイルを示しているが、いくつかの実施形態では、そのタ
イルに長方形などの他の形状を用いてもよい。
【００７８】
Ｄ．動き推定のための適応検索パターン
いくつかの実施形態は、上記の多段動き推定演算中に異なる検索判定基準を用いて検索
を実行する。いくつかの実施形態は、検索を実行する際に固定検索パターンを使用する。
別の実施形態では、異なる検索パターンを使用してもよい。例えば、いくつかの実施形態
は、ある種の判定基準に基づいて検索パターンを適応的に選択する。
【００７９】
１つの例は、低密度および高密度検索パターンの間の選択である。図１５は、検索ウィ
ンドウ１５００内の低密度検索パターンを示す。この図は、パターンが検索のために指定
するロケーションを表す黒い円で検索パターンを示している。図１５に示すように、検索
パターンは、検査できる４９個の潜在的なマクロブロック・ロケーション（黒と白の円で
識別される）から検索のために１６個のロケーションだけを指定する。図１６は、検索ウ
ィンドウ１５００内の高密度検索パターンを示す。この図の検索パターンは、検査できる
４９個の潜在的なマクロブロック・ロケーション（黒と白の円で識別される）から検索の
ために２５個のロケーションを指定する。
【００８０】
いくつかの実施形態は、所望の符号化結果に基づいて図１５および図１６に示す検索パ
ターンから適応的に選択を行う。例えば、いくつかの実施形態は、高解像度符号化（例え
ば、ＨＤテレビジョン符号化）には図１６に示す高密度パターンを使用し、別の実施形態
は、ネットを通じて搬送されるストリーミング・リアルタイム・ビデオのために図１５に
示す低密度パターンを使用する。
【００８１】
あるいは、いくつかの実施形態は、垂直検索の動きを強調する検索パターンを使用し、
別の実施形態は、水平検索の動きを強調する検索パターンを使用する。図１７は、予測さ
れたマクロブロック・ロケーション付近に中心がある検索ウィンドウ内の検索パターンの
一例を示す。この検索パターンは垂直方向に偏っている。探索できるロケーションの数が
限られているので、図１７に示すパターンは、エンコーダの限られた検索予算を使って検
索ウィンドウ１５００の中心にある予測されたマクロブロック・ロケーションの近くの垂
直列にあるロケーションを検査する。
【００８２】
図１８は、予測されたマクロブロック・ロケーション付近に中心がある検索ウィンドウ
内の検索パターンの一例を示す。この検索パターンは水平方向に偏っている。探索できる
ロケーションの数が限られているので、図１８に示すパターンは、エンコーダの限られた
検索予算を使って検索ウィンドウ１５００の中心にある予測されたマクロブロック・ロケ
ーションの近くの水平行にあるロケーションを検査する。
【００８３】
いくつかの実施形態は、隣接マクロブロックのベクトルに基づいて、図１７および図１
８に示す２つのパターンのうちから適応的に選択を行う。それらの大半またはすべてが特
定の方向（例えば、垂直または水平方向）を指す場合、これらの実施形態は図１７または
図１８に示すパターンを選択する。いくつかの実施形態は一方の方向（例えば、ｙ軸）の
動きベクトルの絶対値が他方の方向（例えば、ｘ軸）の動きベクトルの絶対値より大きい
か否かを判定することで、隣接するマクロブロックの動きベクトルが特定の方向を指すか
否かを判定する。いくつかの実施形態は、隣接するマクロブロックの動きベクトルの方向
だけでなく、これらのベクタの大きさも考慮する。いくつかの実施形態は、検索パターン
を適応的に選択する際に、画像のセットの動きフィールド（例えば、画像のセットが特定
の方向の動きを示すか否か）も考慮する。
【００８４】
Ｅ．ＲＤコスト計算
上記のように、本発明のいくつかの実施形態は、動き推定演算中にレート・ディストー
ション（「ＲＤ」）コストなどの特定のマクロブロックのコストを計算する。動き推定中
にすべての可能なモードについてレート・ディストーション・コストを生成することは計
算処理の負荷が高い。このコストが、多くの場合、生成される実際のビットの歪と数の測
定を必然的に伴うとするとこれは正しい。したがって、いくつかの実施形態では、すべて
の可能なモードについてＲＤコストを計算することはない。その代わりに、これらの実施
形態は、動き推定方法をランク付けし、上位Ｎ個の動き推定方法を選択し、次いで選択し
た方法のＲＤコストを計算することで可能なモードの数を減らす。
【００８５】
図１９は、本発明のいくつかの実施形態のプロセス１９００を示す。このプロセスはＲ
Ｄコストを計算する必要がある動き推定方法を識別するために、動き推定方法のサブセッ
トを選択的に検査する。いくつかの実施形態では、このプロセスが開始する前にいくつか
の符号化方法が計算されている。別の実施形態は、このプロセスを符号化方法と併用する
。
【００８６】
最初、プロセス１９００は、最小から最大推定誤差に基づいて符号化方法を（１９１０
で）ランク付けする。いくつかの実施形態では、各符号化方法は動きベクトルだけでなく
推定誤差も生成する。別の実施形態は別のメトリック計算を用いて誤差を量子化する。例
えば、いくつかの実施形態は、平均絶対差（「ＭＡＤ」）測定基準評価（ｍｅｔｒｉｃ  
ｓｃｏｒｅ）を使用するが、絶対差の総和（「ＳＡＤ」）測定基準評価を使用する実施形
態もある。後者の方法は上記組み込まれた「Ｐｒｕｎｉｎｇ  Ａｐｐｌｉｃａｔｉｏｎ」
に記載されている。さらに別の実施形態では、複数の測定基準評価の組み合わせを使用す
る。
【００８７】
次に、プロセスはランク付けされたリストの上位Ｎ個の符号化方法を（１９２０で）選
択する。いくつかの実施形態では、Ｎの値は事前定義された数で、別の実施形態では、動
的に生成される数である。次いで、プロセスは選択した上位Ｎ個の結果のＲＤコストを（
１９３０で）計算し、最も低いＲＤコストを備えた符号化方法を（１９４０で）選択し、
終了する。
【００８８】
いくつかの実施形態は、符号化方法のＲＤコストを下式で表す。
ＲｄＣｏｓｔ＝歪コスト＋（λ×ＮＢ）
ただし、λは重み付け係数、ＮＢは符号化のために生成されたビット数である。ＲｄＣｏ
ｓｔは送信するデータの量とそのデータに関連する歪の量を定量化する。
【００８９】
単一のＲＤコストを計算する代わりに、いくつかの実施形態では、ＲＤコストを因子に
分解するだけでなく符号化方法が生成された所与のモードを復号化する複雑さも因子に分
解するコストを（２３３０で）計算する。このコストは下式で表される。
複合ＲＤ＝ＲｄＣｏｓｔ＋α（ｃｆ）
ただし、ＲｄＣｏｓｔは上記の指定された等式で計算され、αは復号化の複雑さに関連す
る重要な因子で、ｃｆはデータ上で実行される復号化の量を定量化する複雑さの因子であ
る。
【００９０】
１９３０の後で、プロセスは１９３０で計算された最小コストに至った動き推定方法を
（１９４０で）選択し、終了する。最初に初期測定基準評価で動き推定演算をランク付け
し、最小初期測定基準評価でこれらの符号化方法のコスト・メトリックに対して定量化の
みを実行することで、プロセス１９００は可能な限り高速に受け入れられる結果を確実に
見つけるようにする。
【００９１】
ＩＶ．コンピュータ・システム
図２０は、本発明のいくつかの実施形態が実施されるコンピュータ・システムを示す概
念図である。コンピュータ・システム２０００は、バス２００５と、プロセッサ２０１０
と、システム・メモリ２０１５と、読み出し専用メモリ２０２０と、永久記憶装置２０２
５と、入力装置２０３０と、出力装置２０３５とを含む。
【００９２】
バス２００５は、コンピュータ・システム２０００の内部装置間の通信をサポートする
すべてのシステム、周辺装置、およびチップセット・バスを集合的に表す。例えば、バス
２００５は、プロセッサ２０１０を通信可能に読み出し専用メモリ２０２０と、システム
・メモリ２０１５と、永久記憶装置２０２５とに接続する。
【００９３】
これらの種々のメモリ・ユニットから、プロセッサ２０１０は本発明のプロセスを実行
するために、実行する命令と、処理するデータとを取り出す。読み出し専用メモリ（ＲＯ
Ｍ）２０２０は、プロセッサ２０１０とコンピュータ・システムの他のモジュールが必要
とする静的データと命令とを記憶する。他方、永久記憶装置２０２５は、読み出し／書き
込みメモリ素子である。この素子はコンピュータ・システム２０００がオフになっても命
令およびデータを記憶する不揮発性記憶装置である。本発明のいくつかの実施形態は、永
久記憶装置２０２５として、大容量記憶装置（磁気または光ディスクとそれに対応するデ
ィスク・ドライブなど）を使用する。別の実施形態は、永久記憶装置として、着脱式記憶
装置（フロッピー・ディスクまたはｚｉｐ（登録商標）ディスクとそれに対応するディス
ク・ドライブなど）を使用する。
【００９４】
永久記憶装置２０２５のように、システム・メモリ２０１５は読み出し／書き込みメモ
リ素子である。ただし、記憶装置２０２５とは違って、システム・メモリはランダム・ア
クセス・メモリのような揮発性読み出し／書き込みメモリである。システム・メモリはプ
ロセッサが実行時に必要とする命令とデータの一部を記憶する。いくつかの実施形態では
、本発明のプロセスは、システム・メモリ２０１５、永久記憶装置２０２５、および／ま
たは読み出し専用メモリ２０２０に記憶される。
【００９５】
バス２００５はまた入力および出力装置２０３０および２０３５に接続する。ユーザは
入力装置を用いてコンピュータ・システムに情報を伝え、コマンドを選択する。入力装置
２０３０は英数字キーボードおよびカーソル制御装置を含む。出力装置２０３５はコンピ
ュータ・システムによって生成される画像を表示する。出力装置はプリンタと陰極線管（
ＣＲＴ）または液晶ディスプレイ（ＬＣＤ）などの表示装置を含む。
【００９６】
最後に、図２０に示すように、バス２００５はまたネットワーク・アダプタ（図示せず
）を介してコンピュータ２０００をネットワーク２０６５に結合する。こうして、コンピ
ュータはコンピュータのネットワーク（ローカル・エリア・ネットワーク（「ＬＡＮ」）
、ワイド・エリア・ネットワーク（「ＷＡＮ」）、もしくはイントラネットなど）または
ネットワークのネットワーク（インターネットなど）の一部になる。コンピュータ・シス
テム２０００のいずれかまたはすべての構成要素を本発明と併用することができる。ただ
し、任意のその他のシステム構成も本発明と併用できることは当業者には明らかであろう
。
【００９７】
多数の特定の詳細を参照しながら本発明を説明してきたが、通常の当業者であれば、本
発明の精神から逸脱することなしに、本発明を他の特定の形態で実施することができるこ
とを理解することができるだろう。例えば、本発明の多くの実施形態をマクロブロックを
参照しながら説明してきたが、通常の当業者であれば、これらの実施形態は、ピクセル値
の任意の他のアレイと一緒に使用することができることを理解することができるだろう。
【符号の説明】
【００９８】
１００  プロセス
１０５、１１０、１１５，１２０，１２５，１３０，１３５，１４０，１４５，１５０  
２００，２１０，２２０，２３０、２４０，３００、３１０，３２０，３３０、４１０，
４２０，４４０，４５０，４６０、５００，５１０，５２０，５３０，５４０、６１０，
６２０，６３０，６４０，７００，７０５、７１０、７１５，７２０，７２５，７３０，
７３５  ステップ
【図１】
2014150568.tif 000003
【図２】
2014150568.tif 000004
【図３】
2014150568.tif 000005
【図４】
2014150568.tif 000006
【図５】
2014150568.tif 000007
【図６】
2014150568.tif 000008
【図７】
2014150568.tif 000009
【図８】
2014150568.tif 000010
【図９】
2014150568.tif 000011
【図１０】
2014150568.tif 000012
【図１１】
2014150568.tif 000013
【図１２】
2014150568.tif 000014
【図１３】
2014150568.tif 000015
【図１４】
2014150568.tif 000016
【図１５】
2014150568.tif 000017
【図１６】
2014150568.tif 000018
【図１７】
2014150568.tif 000019
【図１８】
2014150568.tif 000020
【図１９】
2014150568.tif 000021
【図２０】
2014150568.tif 000022
【手続補正書】
【提出日】平成26年4月15日(2014.4.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第２の画像を参照して第１の画像内のピクセル・セットを符号化するブロック間符号化方法であって、前記第２の画像は、前記第２の画像内のピクセル・セットを前記第１の画像内の前記ピクセル・セットと照合するための検索ロケーション・セットを含み、前記ブロック間符号化方法は、
判定基準セットに基づいて、前記第１の画像内の前記ピクセル・セットに一致する可能性がある前記第２の画像の複数の部分を検査するための異なる検索ロケーション・サブセットを各々が定義する検索パターン・セットから第１の検索パターンを選択するステップと、
前記選択された第１の検索パターンを使用して、前記第１の画像内の前記ピクセル・セットに最もよく一致する前記第２の画像内のピクセル・セットを識別するステップとを含む方法。
【請求項２】
前記判定基準セットが前記第１の画像及び前記第２の画像を含む画像のシーケンスの符号化解像度を含み、前記判定基準セットがより高い符号化解像度を特定する場合はより高い密度の検索パターンが選択され、前記判定基準セットがより低い符号化解像度を特定する場合はより低い密度の検索パターンが選択される請求項１に記載の方法。
【請求項３】
前記判定基準セットが隣接するピクセル・セットに関する動きベクトル・セットの方向を含み、前記動きベクトル・セットが垂直方向である場合は垂直方向に偏った検索パターンが選択され、前記動きベクトル・セットが水平方向である場合は水平方向に偏った検索パターンが選択される請求項１に記載の方法。
【請求項４】
前記判定基準セットが前記第１の画像及び前記第２の画像を含むビデオ画像セット内の動きフィールドを含み、前記ビデオ画像セットが垂直方向の動きを示す場合は垂直方向に偏った検索パターンが選択され、前記ビデオ画像セットが水平方向の動きを示す場合は水平方向に偏った検索パターンが選択される請求項１に記載の方法。
【外国語明細書】
2014150568000001.pdf