(57)【要約】  検索される部分ピクセル点が互いに近接しているので、各点の２分の１ピクセル及び４分の１ピクセル補間は、既に計算された補間を計算することを含むという事実が利用されうる。これは、第１点の補間値を記憶して他の点に対する補間を計算する時にそれを再使用することによって達成される。これは、水平及び垂直補間の両方に対して実行されうる。水平及び垂直方向の両方における補間に関して、水平補間値が再使用され、垂直補間がその後に実行され、又はその逆でもよい。４分の１ピクセル補間値の計算に関して、予め計算及び記憶された２分の１ピクセル補間値が使用されうる。【特許請求の範囲】
【請求項１】
ビデオストリームにおける画像の第１点の周りで動き推定を実行するための方法であって：
第１点からピクセルの部分だけ離間している第２点の推定値に到達するように補間を実行する過程であって、前記実行過程は、第１組の結果を生成する、過程と；
メモリに前記第１組の結果を保存する過程と；
第３点の推定値に到達するように補間を実行する時、前記第１組の結果を利用する過程と；
を具備することを特徴とする方法。
【請求項２】
第２点は、第１点から２分の１ピクセルだけ離間し、第３点は、第１点から２分の１ピクセルだけ離間していることを特徴とする請求項１に記載の方法。
【請求項３】
第２点は、負の水平方向のみにおける第１点とは異なり、第３点は、正の水平方向のみにおける第１点とは異なることを特徴とする請求項２に記載の方法。
【請求項４】
第２点は、負の垂直方向のみにおける第１点とは異なり、第３点は、正の垂直方向のみにおける第１点とは異なることを特徴とする請求項２に記載の方法。
【請求項５】
第２点は、第１点から２分の１ピクセル離間し、第３点は、第１点から２分の１ピクセル離間している点から４分の１ピクセル離間していることを特徴とする請求項１に記載の方法。
【請求項６】
ビデオストリームにおける画像の第１整数点の周りで動き推定を実行するための方法であって：
第１整数点から２分の１ピクセル離間している２分の１ピクセル点に対して補間を実行すること、及びサンプルに最も近接している補間を有する２分の１ピクセル点を選択することによって第１整数点に対する最善の２分の１ピクセル推定点を検出する過程と；
一つ以上の前記補間を保存する過程と；
最善の２分の１ピクセル推定点から４分の１ピクセル離間している４分の１ピクセル点に対する補間を実行すること、及びサンプルに最も近接している補間を有する４分の１ピクセル点を選択することによって最善の２分の１ピクセル推定点の周りで最善の４分の１ピクセル推定点を検出する過程と；を具備し、
前記最善の４分の１ピクセル推定を検出する過程は、一つ以上の保存された補間を利用する過程を含むことを特徴とする方法。
【請求項７】
前記検出する過程は、第１整数点から２分の１ピクセル左の位置における２分の１ピクセル点を補間し、第１補間を生成する過程と；
第１補間を保存する過程と；
保存された第１補間を使用して第１整数点から２分の１ピクセル右の位置における２分の１ピクセル点を補間し、第２補間を生成する過程と；
第２補間を保存する過程と；
第１整数点から２分の１ピクセル下の位置における２分の１ピクセル点を補間し、第３補間を生成する過程と；
第３補間を保存する過程と；
保存された第３補間を使用して第１整数点から２分の１ピクセル上の位置における２分の１ピクセル点を補間し、第４補間を生成する過程と；
第４補間を保存する過程と；
保存された第１補間と保存された第３補間とを使用して第１整数点から２分の１ピクセル下及び２分の１ピクセル左の位置における２分の１ピクセル点を補間し、第５補間を生成する過程と；
第５補間を保存する過程と；
保存された第２補間と、保存された第３補間と、保存された第５補間とを使用して第１整数点から２分の１ピクセル下及び２分の１ピクセル右の位置における２分の１ピクセル点を補間し、第６補間を生成する過程と；
第６補間を保存する過程と；
保存された第１補間と、保存された第４補間と、保存された第５補間とを使用して第１整数点から２分の１ピクセル上及び２分の１ピクセル左の位置における２分の１ピクセル点を補間し、第７補間を生成する過程と；
第７補間を保存する過程と；
保存された第２補間と、保存された第４補間と、保存された第６補間と、保存された第７補間とを使用して第１整数点から２分の１ピクセル上及び２分の１ピクセル右の位置における２分の１ピクセル点を補間し、第８補間を生成する過程と；
第８補間を保存する過程と；
を具備することを特徴とする請求項６に記載の方法。
【請求項８】
ビデオストリームにおける画像の第１点の周りで動き推定を実行するための装置であって：
第２点補間実行器と；
前記第２点補間実行器に接続された第２点補間保存器と；
前記第２点補間保存器に接続された第３点補間実行器と；
を具備することを特徴とする装置。
【請求項９】
ビデオストリームにおける画像の第１整数点の周りで動き推定を実行するための装置であって：
補間実行器と補間保存器とを含む最善の２分の１ピクセル推定点検出器であって、補間保存器は、メモリに接続される、最善の２分の１ピクセル推定点検出器と；
前記補間保存器に接続された最善の４分の１ピクセル推定点検出器と；
を具備することを特徴とする装置。
【請求項１０】
最善の２分の１ピクセル推定点検出器補間実行器は、
補間保存器に接続された２分の１ピクセル左の補間実行器と；
メモリと補間保存器とに接続された２分の１ピクセル右の補間実行器と；
補間保存器に接続された２分の１ピクセル下の補間実行器と；
メモリと補間保存器とに接続された２分の１ピクセル上の補間実行器と；
メモリと補間保存器とに接続された２分の１ピクセル下及び左の補間実行器と；
メモリと補間保存器とに接続された２分の１ピクセル下及び右の補間実行器と；
メモリと補間保存器とに接続された２分の１ピクセル上及び左の補間実行器と；
メモリと補間保存器とに接続された２分の１ピクセル上及び右の補間実行器と；
を具備することを特徴とする請求項９に記載の装置。
【請求項１１】
ビデオストリームにおける画像の第１点の周りで動き推定を実行するための装置であって：
第１点からピクセルの部分だけ離間している第２点の推定値に到達するように補間を実行するための手段であって、前記実行手段は、第１組の結果を生成する、手段と；
メモリに前記第１組の結果を保存するための手段と；
第３点の推定値に到達するように補間を実行する時、前記第１組の結果を利用するための手段と；
を具備することを特徴とする装置。
【請求項１２】
第２点は、第１点から２分の１ピクセル離間し、第３点は、第１点から２分の１ピクセル離間していることを特徴とする請求項１１に記載の装置。
【請求項１３】
第２点は、負の水平方向のみにおける第１点とは異なり、第３点は、正の水平方向のみにおける第１点とは異なることを特徴とする請求項１２に記載の装置。
【請求項１４】
第２点は、負の垂直方向のみにおける第１点とは異なり、第３点は、正の垂直方向のみにおける第１点とは異なることを特徴とする請求項１２に記載の装置。
【請求項１５】
第２点は、第１点から２分の１ピクセル離間し、第３点は、第１点から２分の１ピクセル離間している点から４分の１ピクセル離間していることを特徴とする請求項１１に記載の装置。
【請求項１６】
ビデオストリームにおける画像の第１整数点の周りで動き推定を実行するための装置であって：
第１整数点から２分の１ピクセル離間している２分の１ピクセル点に対する補間を実行すること、及びサンプルに最も近接している補間を有する２分の１ピクセル点を選択することによって第１整数点に対する最善の２分の１ピクセル推定点を検出するための手段と；
一つ以上の前記補間を保存するための手段と；
最善の２分の１ピクセル推定点から４分の１ピクセル離間している４分の１ピクセル点に対する補間を実行すること、及びサンプルに最も近接している補間を有する４分の１ピクセル点を選択することによって最善の２分の１ピクセル推定点に対する最善の４分の１ピクセル推定点を検出するための手段と；を具備し、
前記最善の４分の１ピクセル推定を検出する手段は、一つ以上の保存された補間を利用する手段を含むことを特徴とする装置。
【請求項１７】
前記検出手段は：
第１整数点から２分の１ピクセル左の位置における２分の１ピクセル点を補間し、第１補間を生成するための手段と；
第１補間を保存するための手段と；
保存された第１補間を使用して第１整数点から２分の１ピクセル右の位置における２分の１ピクセル点を補間し、第２補間を生成するための手段と；
第２補間を保存するための手段と；
第１整数点から２分の１ピクセル下の位置における２分の１ピクセル点を補間し、第３補間を生成するための手段と；
第３補間を保存するための手段と；
保存された第３補間を使用して第１整数点から２分の１ピクセル上の位置における２分の１ピクセル点を補間し、第４補間を生成するための手段と；
第４補間を保存するための手段と；
保存された第１補間と保存された第３補間とを使用して第１整数点から２分の１ピクセル下及び２分の１ピクセル左の位置における２分の１ピクセル点を補間し、第５補間を生成するための手段と；
第５補間を保存するための手段と；
保存された第２補間と、保存された第３補間と、保存された第５補間とを使用して第１整数点から２分の１ピクセル下及び２分の１ピクセル右の位置における２分の１ピクセル点を補間し、第６補間を生成するための手段と；
第６補間を保存するための手段と；
保存された第１補間と、保存された第４補間と、保存された第５補間とを使用して第１整数点から２分の１ピクセル上及び２分の１ピクセル左の位置における２分の１ピクセル点を補間し、第７補間を生成するための手段と；
第７補間を保存するための手段と；
保存された第２補間と、保存された第４補間と、保存された第６補間と、保存された第７補間とを使用して第１整数点から２分の１ピクセル上及び２分の１ピクセル右の位置における２分の１ピクセル点を補間し、第８補間を生成するための手段と；
第８補間を保存するための手段と；
を具備することを特徴とする請求項１６に記載の装置。
【請求項１８】
ビデオストリームにおける画像の第１点の周りで動き推定を実行するための方法を実行するように機械によって実行可能な命令のプログラムを明白に具体化する、機械によって読取可能なプログラム記憶装置であって：
第１点からピクセルの部分だけ離間している第２点の推定値に到達するように補間を実行する過程であって、前記実行過程は、第１組の結果を生成する、過程と；
メモリに前記第１組の結果を保存する過程と；
第３点の推定値に到達するように補間を実行する時、前記第１組の結果を利用する過程と；
を具備することを特徴とする方法。
【請求項１９】
ビデオストリームにおける画像の第１推定点の周りで動き推定を実行するための方法を実行するように機械によって実行可能な命令のプログラムを明白に具体化する、機械によって読取可能なプログラム記憶装置であって：
第１整数点から２分の１ピクセル離間している２分の１ピクセル点に対する補間を実行すること、及びサンプルに最も近接している補間を有する２分の１ピクセル点を選択することによって第１整数点に対する最善の２分の１ピクセル推定点を検出する過程と；
一つ以上の前記補間を保存する過程と；
最善の２分の１ピクセル推定点から４分の１ピクセル離間している４分の１ピクセル点に対する補間を実行すること、及びサンプルに最も近接している補間を有する４分の１ピクセル点を選択することによって最善の２分の１ピクセル推定点に対する最善の４分の１ピクセル推定点を検出する過程と；を具備し、
前記最善の４分の１ピクセル推定を検出する過程は、一つ以上の保存された補間を利用する過程を含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオ圧縮に関する。具体的に、本発明は、高度なビデオエンコーダにおける補間値の再使用に関する。
【背景技術】
【０００２】
ビデオ圧縮は、デジタル送信のサイズを低減するために多数のコンピュータ及び電子コンピュータによって利用されている。ビデオストリームにおいて余分又は不必要な情報を圧縮することによって、ストリームによって利用される帯域幅は、顕著に低減されうる。
【０００３】
通常使用されるビデオ圧縮規格は、ＭＰＥＧ−４規格である。ＭＰＥＧ−４規格は、多数の異なるツールセット及びコーデックを含み、２つの代表的なものとして、Ａｄｖａｎｃｅｄ  Ｓｉｍｐｌｅ  Ｐｒｏｆｉｌｅ及びＭＰＥＧ−４パート１０がある。これら及び他のＭＰＥＧツールは、動き推定の使用を含むことができる。動き推定は、同一の一般画像の短いシーケンス内で、殆どのオブジェクトが同一の位置にとどまり、他のオブジェクトが短い距離だけ移動するという事実を利用する。動きは、現在のマクロブロックのサンプル値を予測するために、予めデコードされたフレームからマクロブロックを取り出す場所を特定する２次元の動きベクトルとして説明されうる。マクロブロックは、全体画像内のピクセルをグループ化したものである（通常１６×１６のグループ化）。動き推定は、マクロブロック又はサブマクロブロックレベルで実行される。
【０００４】
従来バージョンのＭＰＥＧにおいて、整数ピクセル動き推定が利用された。ここで、推定の精度は、整数に限定されたので、オブジェクトが移動すると推定されうる最小量は、一つの全体ピクセルである。しかし実際、オブジェクトのサブピクセル移動が画像で発生しうる。例えば、スクリーン上のオブジェクトは、右へ２分の１さらには４分の１ピクセル移動しうる。整数ピクセル動き推定は、そのような小さな動きを補うのに十分正確ではない。
【０００５】
この不正確性を踏まえて、２分の１ピクセル推定が導入された。２分の１ピクセル推定において、２分の１ピクセル又はそれ以上の移動は、補間の使用を介して推定される。また、これは、２分の１ピクセル補間として知られている。所定の整数座標から垂直又は水平（又は両方）に正確に２分の１ピクセル離間している８つの位置があるので、これら８つの位置に対する値は、推定され、その後これらの推定は、後続フレームから取られたサンプルと比較されうる。サンプルに最も近接する位置は、オブジェクトに対する適当な新たな位置として選択されうる。これは、推定の精度を改善するのでより効果的な動き補償を提供するが、プロセスに複雑なレイヤーを追加するので処理を減速させうる。プロセスがより強力になっているものの、そのような欠点は、比較的安易に見落とされることがあり、実際に２分の１ピクセル補間は、かなり普及しており、（プロセッサオーバヘッドも追加する）高次フィルタの使用を介してさらに正確になってきている。
【０００６】
ＭＰＥＧ−４は、これをさらに一歩進めて、４分の１ピクセル推定を導入した。４分の１ピクセル推定において、４分の１又はそれ以上の移動は、補間の使用を介して推定される。これも、４分の１ピクセル補間として知られている。しかし、この全ては、膨大な量の計算を生み、ビデオコーデックのパフォーマンスに関して４分の１ピクセル動きベクトル検索を障害にしてしまう。
【０００７】
従来において、この問題は、４分の１ピクセル検索が実行されるマクロブロック数を低減すること、又は早期に無くなった状態を利用する概略的な４分の１ピクセル検索を実行することによって対処されてきた。通常、所定の整数ピクセル動きベクトルの周りで、評価されるべき８個の２分の１ピクセル点と４０個の４分の１ピクセル点とがある。これら点の各々に対する２分の１ピクセル及び４分の１ピクセル補間を実行することは、任意のリアルタイムビデオコーデックにとって実現不可能なので、これら点のサブセットが抽出され、それらの点のみが評価される。一般に、検索は、まず２分の１ピクセル点が評価されてから“最善の”２分の１ピクセル点の周りに点在するそれら４分の１ピクセル点のみが検索されるという、階層的方法を使用して実行される。これは、６〜８個の２分の１ピクセル点の周りと、６〜８個の４分の１ピクセル点の周りとを検索することを含む。ここで、規格に固有な４分の１ピクセルフィルタリングは、２分の１ピクセル補間値を使用するか又は使用しない場合があることに留意すべきである。しかし、規格は、検索メカニズム上で直接的な限定を課さないので、一つの規格は常に、従来の発明を利用するために４分の１ピクセル検索を実行する一方で、４分の１ピクセル補間値を計算するために２分の１ピクセル補間値を使用しうる。
【０００８】
もう一つの従来技術は、データサンプル間の類似度を認識することによって２分の１ピクセル推定を速めることであり、補間は結果的に、常に計算される必要があるので、全体的な計算数は、２つの段階が計算を共有するように組み合わせできる場合に低減されうる。例えば、整数位置が（０，０）である場合、その後この位置から２分の１ピクセル右の補間は、（０，０）に対する推定値と（０，１）に対する推定値とを計算してから、それらの間を補間する（それらを加算し、２で割る）必要がある。その後、この補間値がデータサンプルから減算される第２段階が計算される。しかし、これら２つの段階を組合せる技術により、（０，０）ピクセルから生ずる推定２分の１ピクセル値の一部をデータサンプルからマイナスする初期の計算を可能にする。その計算はその後、（０，０）位置から２分の１ピクセル左、上、及び下について反復されるので、４回の計算になるはずが１回に低減することができる。
【０００９】
これら従来技術の解決策は、２分の１ピクセル及び／又は４分の１ピクセル検索アルゴリズムのパフォーマンスオーバヘッドを低減するが、４分の１ピクセル検索アルゴリズムは未だに、速度に関して障害を呈しているので、あまり採用が普及していない。必要な解決策は、４分の１ピクセル検索アルゴリズムのパフォーマンスオーバヘッドを、その効率性を低減することなく、さらに低減できるようにすることである。
【発明の開示】
【課題を解決するための手段】
【００１０】
検索される部分ピクセル点が互いに近接しているので、各点の２分の１ピクセル及び４分の１ピクセル補間は、既に計算された補間を計算することを含むという事実が利用されうる。これは、第１点の補間値を記憶して他の点に対する補間を計算する時にそれを再使用することによって達成される。これは、水平及び垂直補間の両方に対して実行されうる。水平及び垂直方向の両方における補間に関して、水平補間値が再使用され、垂直補間がその後に実行され、又はその逆でもよい。４分の１ピクセル補間値の計算に関して、予め計算及び記憶された２分の１ピクセル補間値が使用されうる。
【発明を実施するための最良の形態】
【００１１】
本発明の実施形態は、ビデオエンコーディングのために補間値を再使用することに関連して本明細書中で説明される。当業者であれば、本発明の以下の詳細な説明が例示的であって限定的ではないことが分かる。本発明の他の実施形態は、本開示の恩恵に浴するそのような当業者にとって直ちに提案される。本発明の実施形態については、添付図面を参照して詳細に示される。同一又は類似の部分に言及する時、図面及び以下の詳細な説明全体にわたって同一の参照番号が使用される。
【００１２】
明確性の目的で、本明細書中で説明される実施形態における通常の特徴については全く開示及び説明しない。勿論、任意のそのような実際の実施形態に関する開発において、実施形態に固有な多数の決定は、特定用途の制約及び特定事業の制約へ準拠するように、開発者の特定の目的を達成するために行われる必要があり、これら特定の目的は、実施形態ごとに及び開発者ごとに異なることが分かる。また、そのような開発努力は複合的であり多大な時間を要するが、それでもなお本開示の恩恵に浴する当業者の技術における通常の行為である。
【００１３】
本発明によると、要素、処理段階、及び／又はデータ構造は、様々な種類のオペレーティングシステム、計算プラットフォーム、コンピュータプログラム、及び／又は汎用目的機械を使用して実行されうる。また、当業者であれば、ハードワイヤード装置、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途集積回路（ＡＳＩＣ）等のような、比較的汎用目的でない機械は、本明細書中で開示されている本発明の概念の範囲及び精神から逸脱することなく使用されうることが分かる。
【００１４】
本発明は、検索される部分ピクセル点が互いに近接しているという事実を利用するので、各点のブロックに対する２分の１ピクセル及び４分の１ピクセル補間は、既に計算されている補間を計算することを含む。これは、第１点に対応するブロックの補間値を記憶すること、及び他の点に対応するブロックへの補間を計算する時にそれを再使用することによって達成される。これは、水平及び垂直補間の両方に対して実行されうる。水平及び垂直方向の両方における補間に関して、水平補間値が再使用され、垂直補間がその後に実行されうる。４分の１ピクセル補間値の計算に関して、予め計算及び記憶された２分の１補間値が使用されうる。読み易くするために、以下において用語“点を評価する”又は“点の補間値を計算する”は、値のブロックがその点から開始して計算されることを示すために使用される。
【００１５】
本発明は、評価される全ての部分ピクセル点が、最善の整数ピクセル点から整数ピクセル距離内にあるという事実に基づく。故に、部分ピクセル検索に必要な２分の１ピクセル補間の数は、顕著に多い必要がない。一度水平及び垂直補間値が任意の点で計算されると、それらが記憶され、全ての他の点に対して再使用されうる。故に、新たな検索点ごとの補間に必要な追加の計算の数は、顕著に低減されうる。
【００１６】
本発明の一つの実施形態において、階層的方法が４分の１ピクセル検索に使用される。即ち、最善の２分の１ピクセル位置が最初に計算され、次に最善の４分の１ピクセル位置が検出される。当業者であれば、本発明は、階層的態様で実行される必要がなく、階層的方法は、本発明の一つの実施形態に過ぎないのを認識することに留意すべきである。検索は、整数ピクセル点の左へ２分の１ピクセル点から開始しうる。そこで計算された補間値は、記憶されうる。その後、整数ピクセル点の右へ２分の１ピクセル点に対する補間値が計算されうる。その後下、その後上へと続く。図１は、本発明の一つの実施形態による部分ピクセル動き推定の順番を示す図である。ここで、参照番号は、点が補完されうる順番を示すので、点１が最初に、次に点２、点３等が計算されうる。当業者であれば、この順番を任意の所望の順番に変更でき、本発明は、いくつかの補間値が再使用されても役立つことが分かる。
【００１７】
これに鑑みて、先に計算された補間値を再使用する可能性が最も高い点は、水平及び垂直方向の両方における補間を必要とする点である。故に、水平のみ及び／又は垂直のみの方向における補間を必要とする点を計算した後にこれらを計算することは有益である。故に、点１、２、３及び４を計算した後、その記憶された補間値は、点５、６、７及び８に対する補間値を計算する時に再使用されうる。記憶された補間値を再使用しうる点は、太字で示される。
【００１８】
以上のように、第２の水平のみの方向及び垂直のみの方向に関する点も、記憶された補間値を再使用することができる。故に、点２及び４も太字である。
【００１９】
これらの点が計算された後、最善の２分の１ピクセル位置が決定されうる。その後、この２分の１ピクセル位置の周りの４分の１ピクセル位置が計算されうる。これら４分の１ピクセル位置の順番は、２分の１ピクセル位置の順番と同一でもよいが、それに限定されない。再度、補間が再使用されるように、水平のみ及び垂直のみの方向における補間を必要とする点の後に水平及び垂直方向の両方における補間を必要とする点に対して補間値を計算することは実に、さらに有益である。
【００２０】
一方で、より端的に言えば、２分の１ピクセル補間値は、保存されることにより、４分の１ピクセル補間の間に再使用されうる。これは、再使用のために４分の１ピクセル補間値の保存と同時に、又はそれに代えても実行されうる。
【００２１】
また、当業者であれば、補間値の再使用は、使用者が実行したい任意の計算深度に発生しうることが分かる。故に、本発明は、１／８ピクセル動き推定、１／１６ピクセル動き推定等に対して将来適用されうる。
【００２２】
本発明の一つの実施形態において、２分の１ピクセル動きベクトル計算において、８つの２分の１ピクセル点が評価される。勿論、そのうち４つは、一方向のみにおいて２分の１ピクセル変位を有し、他の４つは、両方向において２分の１ピクセル変位を有する。第１の４つの点（一方向２分の１ピクセル）に関して、本発明が利用されない場合、４倍のブロックサイズのフィルタ計算が必要となる。一方で、本発明が利用される場合、略全ての計算が再使用のおかげで第２の水平及び垂直点に関して保存されうるので、単に２倍のブロックサイズのフィルタ計算へ低減されうる。
【００２３】
残りの４つの点（両方向２分の１ピクセル）に関して、本発明が利用されない場合、８倍のブロックサイズのフィルタ計算が必要となる。一方で、本発明が利用される場合、それは、単に１倍のブロックサイズのフィルタ計算へ低減されうる。なぜなら、水平の補間値が全て利用可能であり、１つの点に対して実行された両方向の２分の１ピクセル補間が他の３つの点に対して再使用されうるからである。
【００２４】
最善の２分の１ピクセル点の周りにおける４分の１ピクセル検索に必要な２分の１ピクセル計算に関して、必要な計算の数の推定は、最善として選択された２分の１ピクセル位置に基づき変化しうる。４つの異なるケースがある。以下の全ての４つのケースにおいて、４分の１ピクセル補間値を獲得するのに必要な２分の１ピクセル補間動作のみが推定されることに留意すべきである。しかし、４分の１ピクセル補間それ自体も、４分の１ピクセルフィルタリングを実行するのに必要な動作中に保存するために再使用されうる。
【００２５】
第１のケースにおいて、整数ピクセル位置は、最善である。全ての９つの点に対して等しい可能性を過程すると、これが発生する可能性は、１／９である。この場合において、検索されるべき８つの４分の１ピクセル点のうち、４つは、一方向において４分の１ピクセル変位を有し、他方向において整数ピクセル値を有する。他の４つは、両方向において４分の１ピクセル変位を有する。第１の４つのうち、２つは、ｘ方向のみにおいて４分の１ピクセル変位を有し、２つは、ｙ方向のみにおいて４分の１ピクセル変位を有する。２分の１ピクセル補間が再使用されない場合、その後１２倍のブロックサイズの２分の１ピクセルフィルタ動作を実行する必要がある（第１組に対して４倍のブロックサイズ動作及び第２組に対して８倍のブロックサイズ動作）。しかし、２分の１ピクセル補間が再使用される場合、必要な全ての２分の１ピクセル補間値が既に計算され２分の１ピクセル検索の間にメモリに記憶されるので、追加の２分の１ピクセル補間を実行する必要がない。
【００２６】
第２のケースにおいて、ｘ方向のみにおける２分の１ピクセル点は、最善である。これが発生する可能性は、２／９である。このケースにおいて、検索されるべき８つの４分の１ピクセル点のうち、２つは、ｘ方向において４分の１ピクセル変位と、ｙ方向において整数ピクセル値とを有し、２つは、ｙ方向において４分の１ピクセル変位と、ｘ方向において２分の１ピクセル値とを有し、他の４つは、両方向において４分の１ピクセル変位を有する。２分の１ピクセル補間が再使用されない場合、その後２倍のブロックサイズの２分の１ピクセル計算は、ｘ方向においてのみ４分の１ピクセル変位を有する２つの点に必要とされ、４倍のブロックサイズの２分の１ピクセル計算は、ｙ方向において４分の１ピクセル変位とｘ方向において２分の１ピクセル変位とを有する２つの点に必要とされ、８倍のブロックサイズの２分の１ピクセル計算は、両方向において４分の１ピクセル変位を有する４つの点に必要とされ、全部で１４倍のブロックサイズの２分の１ピクセル計算となる。補間値が再使用される時、全てのこれら計算は、補間値が２分の１ピクセル検索の反復から既に利用可能であるので、保存されうる。
【００２７】
第３のケースにおいて、ｙ方向のみにおける２分の１ピクセル点は、最善である。これが発生する可能性は、２／９である。このケースにおいて、検索されるべき８つの４分の１ピクセル点のうち、２つは、ｙ方向において４分の１ピクセル変位とｘ方向において整数ピクセル値とを有し、２つは、ｘ方向において４分の１ピクセル変位とｙ方向において２分の１ピクセル変位とを有し、他の４つは、両方向において４分の１ピクセル変位を有する。補間値が再使用されない時、２倍のブロックサイズの２分の１ピクセル計算は、ｙ方向においてのみ４分の１ピクセル変位を有する２点に必要とされ、４倍のブロックサイズの２分の１ピクセル計算は、ｘ方向のみにおいて４分の１ピクセル変位とｙ方向において２分の１ピクセル変位とを有する２点に必要とされ、８倍のブロックサイズの計算は、両方向において４分の１ピクセル変位を有する４点に必要とされ、全部で１４倍のブロックサイズの２分の１ピクセル計算となる。補間値がまた再使用される時、追加の２分の１ピクセル計算は、実行されない。
【００２８】
第４のケースにおいて、ｘ及びｙ方向の両方で置き換えられた２分の１ピクセル点は、最善である。これが発生する可能性は、４／９である。ここで、全ての点に関して、２分の１ピクセル補間は、両方向において行われる必要がある。なので、２分の１ピクセル値が再使用されない場合、１６倍のブロックサイズの計算が必要となる。２分の１ピクセル値が再使用される場合、全てのこれら計算は、保存されうる。
【００２９】
その結果、全体として、補間値の再使用がない場合、動作の平均数は、（１２＋（１２＊１／９）＋（１４＊２／９）＋（１４＊２／９）＋（１６＊４／９））＊ブロックサイズ、即ち２４０／９倍のブロックサイズの動作である。２分の１ピクセルを再使用する場合、それは、３＊ブロックサイズ動作である。故に、ブロック毎の４分の１ピクセル検索に対する平均保存率は、８８．７５％である。
【００３０】
本明細書全体を介して、一つの点が、もう一方の点から“離間している”ピクセルの部分であるという記述が利用されることに留意すべきである。用語“離間している”は、ピクセルの部分が推定される時、２つの点が、ピクセルの部分に丸められている値によって示されるという事実に照らして解釈されるべきである。故に、点は、そのｘ座標、ｙ座標、又は両方が、他の点からピクセルの部分だけ離間している場合、もう一方の点からピクセルの部分だけ離間しているとして表示されうる。これは、直線が２つの点間に引かれる場合、２つの点間の正確な距離に直接的に一致又は一致しないことがある。例えば、座標（０．５，０．５）は、幾何学的に言って距離が実際に０．５の平方根であっても、本明細書の目的で点（０，０）から２分の１ピクセル離間していると考えられる。出願人がその独自の辞書編集者として許可されているので、用語“離間している”は、点が、他の点のｘ座標及びｙ座標からその距離だけ離間しているｘ座標、ｙ座標、又は両方を有することを意味するように請求項において解釈されるべきである。
【００３１】
図２は、本発明の一つの実施形態によるビデオストリームにおける画像の第１点の周りで動き推定を実行するための方法を示すフロー図である。この方法は、画像における任意の点の周りで実行されうることに留意すべきである。この方法における各行為は、ソフトウェア、ハードウェア、又はその任意の組合せによって実行されうる。２００において、補間は、第１点からピクセルの部分だけ離間している第２点の推定値に到達するように実行されることができ、第１組の結果を生成する。ピクセルの部分は、任意の部分であり、上記の通り、点からピクセルの部分だけ離間していることは、水平座標、垂直座標、又は両方の何れか一方が当該部分によって点とは異なることを意味する。
【００３２】
２０２において、第１組の結果は、メモリに保存されうる。２０４において、第１組の結果は、第３点の推定値に到達するように補間を実行する時、利用されうる。この利用は、多数の異なる段階で発生しうる。例えば、第３点は、第２点と同じ部分によって第１点とは異なることがある。代わりに、第３点は、第２点と同じ部分によって異なる点を変化させることができる。もう一つの可能性として、第３点は、第１点とは異なる第２点と比較して異なる部分によって第１点又はもう一つの点の何れか一方とは異なることがある。
【００３３】
図３は、本発明のもう一つの実施形態によるビデオストリームにおける画像の第１整数点の周りで動き推定を実行するための方法を示すフロー図である。この方法の各行為は、ソフトウェア、ハードウェア、又はその任意の組合せによって実行されうる。この実施形態において、第１の２分の１ピクセル推定が実行され、最善の２分の１ピクセル推定点上で４分の１ピクセル推定が次に実行される。故に３００において、第１整数点の周りにおける最善の２分の１ピクセル推定点は、第１整数点から２分の１ピクセル離間している２分の１ピクセル点に対する補間を実行すること、及びサンプルに最も近接している補間を有する２分の１ピクセル点を選択することによって検出されることができる。３０２において、一つ以上の補間が保存されうる。この保存は、図４及び付随文章から分かる通り、最善の２分の１ピクセル推定点を検出する間に実際に実行されうることに留意すべきである。検出する間に一つ以上の補間を保存することにより、最善の２分の１ピクセル推定点を他の部分が検出する間に補間を再使用することができる。しかし、実施形態は、２分の１ピクセル推定点を検出することによる補間が、２分の１ピクセル推定点を検出する間に再使用されず、最善の４分の１ピクセル推定点を検出する間に再使用されるだけの実施形態が可能である。
【００３４】
３０４において、最善の４分の１ピクセル推定点は、最善の２分の１ピクセル推定点から４分の１ピクセル離間している４分の１ピクセル点に対する補間を実行すること、及びサンプルに最も近接している補間を有する４分の１ピクセル点を選択することによって最善の２分の１ピクセル推定点に関して検出されることができる。これは、２分の１ピクセル推定からの一つ以上の保存された補間、及び／又は最善の４分の１ピクセル推定点を検出する間の一つ以上の保存された補間を利用することを含む。
【００３５】
図４は、本発明の一つの実施形態による第１整数点に対する最善の２分の１ピクセル推定点を検出することを示すフロー図である。図４は、図３の３００をより詳細に示す。方法の各行為は、ハードウェア、ソフトウェア、又はその任意の組合せで実行されうる。また、行為の順番は、実施形態に依存して変更可能である。また、システムが全ての補間を再使用する必要又は希望のない場合があるので、各補間を保存する厳密な必要性はない。最後に、この方法の間に保存された一つ以上の補間は、後続の方法で再使用可能であることに追加して、方法における他の行為の間に再使用可能である。
【００３６】
４００において、第１整数点から２分の１ピクセル左の位置における２分の１ピクセル点が補間され、第１補間を生成することができる。４０２において、第１補間が保存されうる。４０４において、第１整数点から２分の１ピクセル右の位置における２分の１ピクセル点が補間され、第２補間を生成することができる。４０６において、第２補間が保存されうる。４０８において、第１整数点から２分の１ピクセル下の位置における２分の１ピクセル点が補間され、第３補間を生成することができる。４１０において、第３補間が保存されうる。４１２において、第１整数点から２分の１ピクセル上の位置における２分の１ピクセル点が補間され、第４補間を生成することができる。４１４において、第４補間が保存されうる。
【００３７】
４１６において、第１整数点から２分の１ピクセル下及び２分の１ピクセル左の位置における２分の１ピクセル点が補間され、第５補間を生成することができる。４１８において、第５補間が保存されうる。４２０において、第１整数点から２分の１ピクセル下及び２分の１ピクセル右の位置における２分の１ピクセル点が補間され、第６補間を生成することができる。４２２において、第６補間が保存されうる。４２４において、第１整数点から２分の１ピクセル上及び２分の１ピクセル左の位置における２分の１ピクセル点が補間され、第７補間を生成することができる。４２６において、第７補間が保存されうる。４２８において、第１整数点から２分の１ピクセル上及び２分の１ピクセル右の位置における２分の１ピクセル点が補間され、第８補間を生成することができる。４３０において、第８補間が保存されうる。
【００３８】
図５は、本発明の一つの実施形態による２分の１ピクセル推定点に対する最善の４分の１ピクセル推定点を検出することを示すフロー図である。図５は、図３の３０４をより詳細に示す。方法の各行為は、ハードウェア、ソフトウェア、又はその任意の組合せで実行されうる。また、行為の順番は、実施形態に依存して変更可能である。また、システムが全ての補間を再使用する必要又は希望のない場合があるので、各補間を保存する厳密な必要性はない。最後に、この方法の間に保存された一つ以上の補間は、後続の方法で再使用可能であることに追加して、方法における他の行為の間に再使用可能である。
【００３９】
５００において、最善の２分の１ピクセル推定点から４分の１ピクセル左の位置における４分の１ピクセル点が補間され、第９補間を生成することができる。５０２において、第９補間が保存されうる。５０４において、最善の２分の１ピクセル推定点から４分の１ピクセル右の位置における４分の１ピクセル点が補間され、第１０補間を生成することができる。５０６において、第１０補間が保存されうる。５０８において、最善の２分の１ピクセル推定点から４分の１ピクセル下の位置における４分の１ピクセル点が補間され、第１１補間を生成することができる。５０８において、第１１補間が保存されうる。５１２において、最善の２分の１ピクセル推定点から４分の１ピクセル上の位置における４分の１ピクセル点が補間され、第１２補間を生成することができる。５１４において、第１２補間が保存されうる。
【００４０】
５１６において、最善の２分の１ピクセル推定点から４分の１ピクセル下及び４分の１ピクセル左の位置における４分の１ピクセル点が補間され、第１３補間を生成することができる。５１８において、第１３補間が保存されうる。５２０において、最善の２分の１ピクセル推定点から４分の１ピクセル下及び４分の１ピクセル右の位置における４分の１ピクセル点が補間され、第１４補間を生成することができる。５２２において、第１４補間が保存されうる。５２４において、最善の２分の１ピクセル推定点から４分の１ピクセル上及び４分の１ピクセル左の位置における４分の１ピクセル点が補間され、第１５補間を生成することができる。５２６において、第１５補間が保存されうる。５２８において、最善の２分の１ピクセル推定点から４分の１ピクセル上及び４分の１ピクセル右の位置における４分の１ピクセル点が補間され、第１６補間を生成することができる。５２０において、第１６補間が保存されうる。
【００４１】
図６は、本発明の一つの実施形態によるビデオストリームにおける画像の第１点の周りで動き推定を実行するための装置を示すブロック図である。この装置は、画像における任意の点の周りで使用されうることに留意すべきである。この装置の各要素は、ソフトウェア、ハードウェア、又はその任意の組合せで具体化されうる。第２点補間実行器６００は、第１点からピクセルの部分だけ離間している第２点の推定値に到達するように補間を実行することができ、第１組の結果を生成する。ピクセルの部分は、任意の部分にすることができ、上記検討の通り、点からピクセルの部分だけ離間していることは、水平座標、垂直座標、又は両方が部分によって点とは異なることを意味する。
【００４２】
第２点補間実行器６００に接続された第２点補間保存器６０２は、メモリに第１組の結果を保存することができる。第２点補間保存器６０２に接続された第３点補間実行器６０４は、第３点の推定値に到達するように補間を実行する時、第１組の結果を利用することができる。この利用は、多数の異なる段階で発生しうる。例えば、第３点は、第２点と同じ部分によって第１点とは異なることがある。代わりに、第３点は、第２点と同じ部分によって異なる点を変更することができる。もう一つの可能性として、第３点は、第１点とは異なる第２点と比較して異なる部分によって第１点又はもう一つの点の何れか一方とは異なることがある。
【００４３】
図７は、本発明のもう一つの実施形態によるビデオストリームにおける画像の第１整数点の周りで動き推定を実行するための装置を示すブロック図である。この装置の各要素は、ソフトウェア、ハードウェア、又はその任意の組合せによって具体化されうる。この実施形態において、第１の２分の１ピクセル推定が実行され、最善の２分の１ピクセル推定点上の４分の１ピクセル推定が次に実行される。故に、最善の２分の１ピクセル推定点検出器７００は、第１整数点から２分の１ピクセル離間している２分の１ピクセル点に対する補間を実行すること、及びサンプルに最も近接している補間を有する２分の１ピクセル点を選択することによって第１整数点に対する最善の２分の１ピクセル推定点を検出することができる。最善の２分の１ピクセル推定点検出器７００は、補間実行器７０２及び補間保存器７０４を含むことができる。補間保存器７０４は、補間実行器によって実行された一つ以上の補間を保存することができる。この保存は、図８及び付随文章に示す通り、最善の２分の１ピクセル推定点を検出する間に実際に実行されうる点に留意すべきである。検出する間に一つ以上の補間を保存することにより、最善の２分の１ピクセル推定点を他の部分が検出する間に補間を再使用することができる。しかし、２分の１推定点を検出することによる補間が、２分の１ピクセル推定点を検出する間に再使用されず、最善の４分の１ピクセル推定点を検出する間に再使用されるのみである実施形態が可能である。
【００４４】
補間保存器７０４に接続された最善の４分の１ピクセル推定点検出器７０６は、最善の２分の１ピクセル推定点から４分の１ピクセル離間している４分の１ピクセル点に対する補間を実行すること、及びサンプルに最も近接している補間を有する４分の１ピクセル点を選択することによって最善の２分の１ピクセル推定点に対する最善の４分の１ピクセル推定点を検出することができる。これは、２分の１ピクセル推定による一つ以上の保存された補間、及び／又は最善の４分の１ピクセル推定点を検出する間に一つ以上の保存された補間を利用することを含みうる。
【００４５】
図８は、本発明の一つの実施形態による最善の２分の１ピクセル推定点検出器を示すブロック図である。図８は、図７の７００をより詳細に示す。最善の２分の１ピクセル推定点検出器の各要素は、ハードウェア、ソフトウェア、又はその任意の組合せで実行されうる。また、行為の順番は、実施形態に依存して変更されうる。また、システムが全ての補間を再使用する必要又は希望のない場合があるので、各補間を保存する厳密な必要性はない。最後に、最善の２分の１ピクセル推定点検出器の使用中に保存された一つ以上の補間は、後続の方法で再使用可能なことに加えて、方法における他の行為の間に再使用されうる。
【００４６】
補間保存器８０２に接続された２分の１ピクセル左の補間実行器８００は、第１整数点から２分の１ピクセル左の位置における２分の１ピクセル点を補間し、第１補間を生成することができる。第１補間は、メモリ８０４で補間保存器８０２によって保存されうる。補間保存器８０２とメモリ８０４とへ接続された２分の１ピクセル右の補間実行器８０６は、第１整数点から２分の１ピクセル右の位置における２分の１ピクセル点を補間し、第２補間を生成することができる。第２補間は、メモリ８０４で補間保存器８０２によって保存されうる。補間保存器８０２とメモリ８０４とへ接続された２分の１ピクセル下の補間実行器８０８は、第１整数点から２分の１ピクセル下の位置における２分の１ピクセル点を補間し、第３補間を生成することができる。第３補間は、メモリ８０４で補間保存器８０２によって保存されうる。補間保存器８０２とメモリ８０４とへ接続された２分の１ピクセル上の補間実行器８１０は、第１整数点から２分の１ピクセル上の位置における２分の１ピクセル点を補間し、第４補間を生成することができる。第４補間は、メモリ８０４で補間保存器８０２によって保存されうる。
【００４７】
補間保存器８０２とメモリ８０４とへ接続された２分の１ピクセル下及び左の補間実行器８１２は、第１整数点から２分の１ピクセル下及び２分の１ピクセル左の位置における２分の１ピクセル点を補間し、第５補間を生成することができる。第５補間は、メモリ８０４で補間保存器８０２によって保存されうる。補間保存器８０２とメモリ８０４とへ接続された２分の１ピクセル下及び右の補間実行器８１４は、第１整数点から２分の１ピクセル下及び２分の１ピクセル右の位置における２分の１ピクセル点を補間し、第６補間を生成することができる。第６補間は、メモリ８０４で補間保存器８０２によって保存されうる。補間保存器８０２とメモリ８０４とへ接続された２分の１ピクセル上及び左の補間実行器８１６は、第１整数点から２分の１ピクセル上及び２分の１ピクセル左の位置における２分の１ピクセル点を補間し、第７補間を生成することができる。第７補間は、メモリ８０４で補間保存器８０２によって保存されうる。補間保存器８０２とメモリ８０４とへ接続された２分の１ピクセル上及び右の補間実行器８１８は、第１整数点から２分の１ピクセル上及び２分の１ピクセル右の位置における２分の１ピクセル点を補間し、第８補間を生成することができる。第８補間は、メモリ８０４で補間保存器８０２によって保存されうる。
【００４８】
図９は、本発明の一つの実施形態による最善の４分の１ピクセル推定点検出器を示すブロック図である。図９は、図７の７０６をより詳細に示す。最善の４分の１ピクセル推定点検出器の各要素は、ハードウェア、ソフトウェア、又はその任意の組合せで具体化することができる。また、行為の順番は、実施形態に依存して変更可能である。また、システムが全ての補間を必要又は希望のない場合があるので、各補間を保存する厳密な必要性はない。最後に、最善の４分の１ピクセル推定点検出器の使用中に保存された一つ以上の補間は、それらが存在する場合に、他の要素で再使用可能であることに追加して、最善の４分の１ピクセル推定点検出器によって再使用されうる。
【００４９】
補間保存器９０２とメモリ９０４とへ接続された４分の１ピクセル左の補間実行器９００は、最善の２分の１ピクセル推定点から４分の１ピクセル左の位置における４分の１ピクセル点を補間し、第９補間を生成することができる。第９補間は、メモリ９０４で補間保存器９０２によって保存されうる。補間保存器９０２とメモリ９０４とへ接続された４分の１ピクセル右の補間実行器９０６は、最善の２分の１ピクセル推定点から４分の１ピクセル右の位置における４分の１ピクセル点を補間し、第１０補間を生成することができる。第１０補間は、メモリ９０４で補間保存器９０２によって保存されうる。補間保存器９０２とメモリ９０４とへ接続された４分の１ピクセル下の補間実行器９０６は、最善の２分の１ピクセル推定点から４分の１ピクセル下の位置における４分の１ピクセル点を補間し、第１１補間を生成することができる。第１１補間は、メモリ９０４で補間保存器９０２によって保存されうる。補間保存器９０２とメモリ９０４とへ接続された４分の１ピクセル上の補間実行器９０８は、最善の２分の１ピクセル推定点から４分の１ピクセル上の位置における４分の１ピクセル点を補間し、第１２補間を生成することができる。第１２補間は、メモリ９０４で補間保存器９０２によって保存されうる。
【００５０】
補間保存器９０２とメモリ９０４とへ接続された４分の１ピクセル下及び左の補間実行器９１０は、最善の２分の１ピクセル推定点から４分の１ピクセル下及び４分の１ピクセル左の位置における４分の１ピクセル点を補間し、第１３補間を生成することができる。第１３補間は、メモリ９０４で補間保存器９０２によって保存されうる。補間保存器９０２とメモリ９０４とへ接続された４分の１ピクセル下及び右の補間実行器９１２は、最善の２分の１ピクセル推定点から４分の１ピクセル下及び４分の１ピクセル右の位置における４分の１ピクセル点を補間し、第１４補間を生成することができる。第１４補間は、メモリ９０４で補間保存器９０２によって保存されうる。補間保存器９０２とメモリ９０４とへ接続された４分の１ピクセル上及び左の補間実行器９１４は、最善の２分の１ピクセル推定点から４分の１ピクセル上及び４分の１ピクセル左の位置における４分の１ピクセル点を補間し、第１５補間を生成することができる。第１５補間は、メモリ９０４で補間保存器９０２によって保存されうる。補間保存器９０２とメモリ９０４とへ接続された４分の１ピクセル上及び右の補間実行器は、最善の２分の１ピクセル推定点から４分の１ピクセル上及び４分の１ピクセル右の位置における４分の１ピクセル点を補間し、第１６補間を生成することができる。第１６補間は、メモリ９０４で補間保存器９０２によって保存されうる。
【００５１】
本発明の実施形態及び用途が図示及び説明されたが、本開示の恩恵に浴する当業者であれば、本明細書の発明概念から逸脱することなく、上記言及された変更よりさらに多くの変更をすることができる。故に、本発明は、添付の特許請求の範囲の精神を除いて限定されるべきでない。
【図面の簡単な説明】
【００５２】
【図１】図１は、本発明の一つの実施形態による部分ピクセル動き推定の順番を示す図である。
【図２】図２は、本発明の一つの実施形態によるビデオストリームにおける画像の第１点の周りで動き推定を実行するための方法を示すフロー図である。
【図３】図３は、本発明のもう一つの実施形態によるビデオストリームにおける画像の第１整数点の周りで動き推定を実行するための方法を示すフロー図である。
【図４】図４は、本発明の一つの実施形態による第１整数点に対する最善の２分の１ピクセル推定点を検出する過程を示すフロー図である。
【図５】図５は、本発明の一つの実施形態による２分の１ピクセル推定点に対する最善の４分の１ピクセル推定点を検出する過程を示すフロー図である。
【図６】図６は、本発明の一つの実施形態によるビデオストリームにおける画像の第１点の周りで動き推定を実行するための装置を示すブロック図である。
【図７】図７は、本発明のもう一つの実施形態によるビデオストリームにおける画像の第１整数点の周りで動き推定を実行するための装置を示すブロック図である。
【図８】図８は、本発明の一つの実施形態による最善の２分の１ピクセル推定点検出器を示すブロック図である。
【図９】図９は、本発明の一つの実施形態による最善の４分の１ピクセル推定点検出器を示すブロック図である。
【符号の説明】
【００５３】
６００  第２点補間実行器
６０２  第２点補間保存器
６０４  第３点補間実行器
【図１】
2008547323.tif 000002
【図２】
2008547323.tif 000003
【図３】
2008547323.tif 000004
【図４】
2008547323.tif 000005
【図５】
2008547323.tif 000006
【図６】
2008547323.tif 000007
【図７】
2008547323.tif 000008
【図８】
2008547323.tif 000009
【図９】
2008547323.tif 000010