(57)【要約】      （修正有）【課題】動画エンコーディングにおける高速なサブピクセル動き推定用のシステムおよび方法を提供する。【解決手段】複数の非線形構築面を生成することと、複数の構築面と実際のマッチング規準面の複数のサンプルポイントとに基づき、ソースフレームと参照フレームとの間のマッチング規準を表す推定マッチング規準面をリアルタイムで生成することと、推定マッチング規準面上で位置をリアルタイムで選択することとによって、ソースフレームと参照フレームとの間の最良マッチを提供することを含む。【選択図】なし【特許請求の範囲】
【請求項１】
動画エンコーディングにおけるサブピクセル動き推定のための方法であって、
複数の非線形構築面を生成すること、
前記複数の構築面と、実際のマッチング規準面の複数のサンプルポイントとに基づき、第１の画像と第２の画像との間のマッチング規準を表す推定マッチング規準面をリアルタイムで生成すること、
前記推定マッチング規準面上で前記第１の画像と前記第２の画像との間の最良マッチを表す位置をリアルタイムで選択すること、
を備える方法。
【請求項２】
前記複数の非線形構築面の各々が係数の集合によって定義される、請求項１に記載の方法。
【請求項３】
前記複数の構築面が所定のパラメータに関連付けられている、請求項１に記載の方法。
【請求項４】
前記複数の構築面を生成することが、
前記複数のサンプルポイントとして使用される複数の位置ずれポイントを選択すること、
複数の構築面を生成すること、
を含む、請求項１に記載の方法。
【請求項５】
前記複数の構築面を生成することが、前記推定マッチング規準面と前記実際のマッチング規準面との間の誤差を最小化するために、複数の構築面を反復的に更新することを含む、請求項１に記載の方法。
【請求項６】
前記複数の構築面を反復的に更新することが、
受信されたソースフレームと参照フレームとに従って前記実際のマッチング規準面を計算すること、
前記複数の位置ずれポイントにおける前記実際のマッチング規準面の複数のサンプルと、前記複数の構築面とに基づいて推定面を生成すること、
前記推定面と前記実際のマッチング規準面との間の誤差を所定のしきい値と比較すること、
を含む、請求項５に記載の方法。
【請求項７】
前記位置が動きベクトルを表す、請求項１に記載の方法。
【請求項８】
サブピクセル動き推定のための動画エンコードシステムであって、
複数の非線形構築面を生成するための前処理ユニットと、
前記複数の構築面と、実際のマッチング規準面の複数のサンプルポイントとに基づき、第１の画像と第２の画像との間のマッチング規準を表す推定マッチング規準面をリアルタイムで生成するとともに、前記推定マッチング規準面上で前記第１の画像と前記第２の画像との間の最良マッチを表す位置をリアルタイムで選択するサブピクセル動き推定ブロックと、
を備えるシステム。
【請求項９】
前記前処理ユニットは、前記複数の非線形構築面の各々を係数の集合によって定義する、請求項８に記載のシステム。
【請求項１０】
前記前処理ユニットは、所定のパラメータに関連付けて前記複数の構築面を生成する、請求項８に記載のシステム。
【請求項１１】
前記前処理ユニットは、複数の構築面を生成するとともに、前記複数のサンプルポイントとして使用される複数の位置ずれポイントを選択する、請求項８に記載のシステム。
【請求項１２】
前記前処理ユニットは、前記推定マッチング規準面と前記実際のマッチング規準面との間の誤差を最小化するために、複数の構築面を反復的に更新する、請求項８に記載のシステム。
【請求項１３】
前記前処理ユニットは、
ソースフレームと参照フレームとを受信すること、
前記ソースフレームと前記参照フレームとに従って前記実際のマッチング規準面を計算すること、
前記複数の位置ずれポイントにおける前記実際のマッチング規準面の複数のサンプルと、前記複数の構築面とに基づいて推定面を生成すること、および
前記推定面と前記実際のマッチング規準面との間の誤差を所定のしきい値と比較すること、
を反復的に行う、請求項１２に記載のシステム。
【請求項１４】
前記位置が動きベクトルを表す、請求項８に記載のシステム。
【請求項１５】
処理プラットフォームによって実行される命令を格納したコンピュータ記憶媒体を備える製品であって、前記命令は、
複数の非線形構築面を生成すること、
前記複数の構築面と、実際のマッチング規準面の複数のサンプルポイントとに基づき、第１の画像と第２の画像との間のマッチング規準を表す推定マッチング規準面をリアルタイムで生成すること、
前記推定マッチング規準面上で前記第１の画像と前記第２の画像との間の最良マッチを表す位置をリアルタイムで選択すること、
を前記処理プラットフォームに実行させる、製品。
【発明の詳細な説明】
【技術分野】
【０００１】
高速サブピクセル動き推定に関する。
【背景技術】
【０００２】
デジタル動画圧縮は、放送、ストリーミング、記憶など、様々な実施用途で使用され得る。種々の動画圧縮の規格および方法には、ある画像から別の画像への変換（通常は動画シーケンスにおける隣接フレーム間）を表す動きベクトルを決定する動き推定というプロセスが含まれる。
【０００３】
動き推定アルゴリズムは、現在のフレーム内の現在のブロックに関し、目標フレームの検索範囲から、現在のブロックと最も類似している最良マッチングブロックを検索する。比較的良好なマッチが見つかったら、動き推定アルゴリズムは、動きベクトルをそのブロックに割り当て、ブロックがマッチするのに必要な水平方向および垂直方向の移動距離を示す。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
最良マッチを見つける方法として、サブピクセル解像度を用いることができる。理論的には、動き推定アルゴリズムは、検索領域内で検索可能なすべてのサブピクセル位置を計算した後に検索を実行するのがよいが、この方法では、大きなメモリ領域と処理リソースが必要となる。従って、計算の複雑性を低減し得るサブピクセル動き推定アルゴリズムが望まれている。
【図面の簡単な説明】
【０００５】
【図１】本発明の実施形態による例示的な動画エンコーダを表すブロック図である。
【図２】本発明の実施形態によるサブピクセル動き推定のための前処理アルゴリズムを実行する方法を表すフローチャートである。
【図３】本発明の実施形態によるリアルタイムサブピクセル動き推定アルゴリズムを実行する方法を表すフローチャートである。
【図４Ａ】本発明の実施形態によるサブピクセル動き推定アルゴリズムの例示的なリアルタイム実装を表すフローチャートである。
【図４Ｂ】本発明の実施形態による例示的なピクセルマップを表すフローチャートである。
【発明を実施するための形態】
【０００６】
以下の詳細な説明では、本発明を完全に理解するために、種々の具体的な詳細について説明する。しかしながら、これらの具体的な詳細がなくとも本発明を実施できることは、当業者であれば理解し得る。他の実施例では、本発明が不明瞭になることを避けるために、周知の方法、手順、および構成要素は、詳細に説明されていない。また、説明の簡潔化および明瞭化のため、図示されている要素は必ずしも正しい尺度で描かれてはいない。例えば、一部の要素の寸法は、明確化のために他の要素に比して誇張されている。対応する要素または類似する要素を示す場合、参照番号を適宜、図中で繰り返す。
【０００７】
本発明の実施形態は、これに限定されないが、例えば、「処理」、「演算」、「計算」、「決定」、「確立」、「解析」、「確認」等の用語を使用した説明は、コンピュータ、演算プラットフォーム、演算システム、あるいは他の電子演算装置の動作および／またはプロセスに関係する。これらの装置は、コンピュータのレジスタおよび／またはメモリ内に物理量（電子量など）として表されているデータを、コンピュータのレジスタおよび／またはメモリ内、あるいは動作および／またはプロセスを実行する命令を格納可能な他の情報記憶媒体内に同様に物理量として表されている他のデータに処理したり変換したりする。
【０００８】
本発明の実施形態は、これに限定されないが、本明細書で使用する「複数」という用語は、例えば「多数」または「二つ以上」を含み、二つ以上の構成部品、装置、要素、ユニット、パラメータ等に言及する目的で本明細書全体で使用される。
【０００９】
次に図１を参照すると、同図は、本発明の実施形態による例示的な動画エンコーダのブロック図である。動画エンコーダ１００は、動画ストリームを入力として受信し、エンコードされた動画ストリームを出力する。動画エンコーダ１００は、動きベクトルを計算するための高速サブピクセル動き推定を実行可能な動き推定／補償ブロック１１０を含む。動きベクトルは、フレームメモリ１０１に記憶された最初のソース画像すなわちフレームから、参照フレームメモリ１０５に記憶された参照フレームなどの別の画像すなわちフレームへの変換を表す。画像すなわちフレームは、複数のブロック、例えば、複数のマクロブロック（ＭＢ）に分割されていてもよく、各ブロックは、例えば、１６×１６ピクセルのような一群のピクセルを含み得る。
【００１０】
推定／補償ブロック１１０は、メモリ１０５に記憶された参照フレーム内の検索範囲において、メモリ１０１に記憶されたソースフレームすなわち現在フレーム内のブロックに最も類似し、最良マッチングブロックとなるブロックを検索する。マッチするものが見つかると、推定／補償ブロック１１０によって実行される動き推定アルゴリズムは、そのブロックに動きベクトルを割り当てる。動き推定アルゴリズムは、ソースフレームと参照フレームとをマッチさせるためには、そのブロックを水平方向および垂直方向にどのくらいの距離で移動させればよいかを示す。
【００１１】
第１のフレームの選択されたブロックに対する最良マッチを見つけるために、動き推定アルゴリズムは、第２のフレームで最も類似したブロックを検索してもよい。本明細書に記載されている、ソースフレームと参照フレームとの間の「マッチング規準」という用語は、二つのフレーム間の差、またはそれらのフレーム内での二つの領域間の差を表す値を意味する。例えば、参照フレームにおいて区画される検索領域内でソースフレームの選択されたＭＢを検索する場合には、該ソースフレームの選択されたＭＢと検索領域内のＭＢとの差が、絶対差の総和（ＳＡＤ）、二乗差の総和（ＳＳＤ）、ハダマード変換などの、任意の適用可能な方法で測定される。なお、その他の適切な方法、公式、あるいは計算式を使用してもよい。
【００１２】
動き推定／補償ブロック１１０は、サブピクセル解像を行う動き推定アルゴリズムを実行または実施可能なサブピクセル動き推定ブロック１２０を含む。サブピクセル推定ブロック１２０は、取りうるすべてのフルピクセル位置および取りうるすべてのサブピクセル位置に関するマッチング規準を計算することなく、参照フレームの検索領域内で選択された解像度に従って、第１の画像（例えばソースフレーム）と第２の画像（例えば参照フレーム）との間の最良マッチを提供し得る。本発明の実施形態によれば、サブピクセル動き推定ブロック１２０は、複数の構築面と実際のマッチング規準面の複数のサンプルポイントとに基づいて、第１の画像と第２の画像との間のマッチング規準を表す推定マッチング規準面をリアルタイムで生成することができる。
【００１３】
サブピクセル推定ブロック１２０は、前処理ユニット１３０などの処理ユニットで実行された、あるいはそこから受信した演算処理の結果を記憶または保存するメモリ１２５を含み得る。メモリ１２５は、前処理ユニット１３０から受信した演算結果をテーブル形式やリストや他の方法などの任意の形式または方法で保存する。メモリ１２５は、リアルタイムエンコーディングの際に前処理アルゴリズムの結果を使用する命令を記憶するコンピュータ記憶媒体であってよい。
【００１４】
前処理ユニット１３０は、ソースフレームと参照フレームとのマッチング規準の推定に使用する複数の非線形構築面を生成する。前処理ユニット１３０によって生成される構築面や位置ずれポイント等の他のパラメータは、図２に記載されているように、サブピクセル推定ブロック１２０に入力データとして提供される。
【００１５】
前処理ユニット１３０は、エンコーダ１００とは別の演算装置などの、エンコーダ１００に対する外部装置として実装し得る。いくつかの実施形態では、前処理ユニット１３０は、動き推定ブロック１１０に統合したり、エンコーダ１００内でスタンドアロンのユニットとして実装したりしてもよい。前処理ユニット１３０は、本明細書においては「設計フェーズ」とも称される前処理アルゴリズムを実行または実装し得る。このアルゴリズムは、動き推定／補償ブロック１１０のプロセスおよび／またはエンコーダ１００のプロセスよりも前に実施あるいは実行される。
【００１６】
前処理ユニット１３０によって実行される設計フェーズは、動き推定ブロック１１０を初めて有効化する前など、実際の動き推定が始まる前に一回実行される。前処理ブロック１３０によって実装される前処理アルゴリズムをエンコーダ１００の実行時に実行することはできず、前処理アルゴリズムは、エンコーダ１００の演算プラットフォームとは異なる演算装置で前処理ブロック１３０によって実装されることを当業者は理解し得る。
【００１７】
処理ユニット１３０によって実行される設計フェーズは、特定のアプリケーション、特定のエンコーダ１００、および／または特定の動画圧縮規準（ＭＰＥＧ―２、ＭＰＥＧ―４、Ｈ．２６４など）に対して固有であってもよい。また、前処理ユニット１３０による設計フェーズアルゴリズムの実行時に他の任意のパラメータを考慮してもよい。
【００１８】
エンコーダ１００は、エンコーディング機能や動作の実行、またはその実行に関する他のブロック、モジュール、動作ユニットとして、減算器１１１、加算器１１２、画像処理ブロック１１３をさらに含み得る。図１の例示において、画像処理ブロック１１３は、離散コサイン変換（ＤＣＴ）、量子化、エントロピーコーディング、あるいはその他の関数、計算、処理など、エンコーディングプロセスの一部であってよい任意の動作、関数、または方法を含み得るが、本発明はこの点に関して限定されない。本発明の実施形態により、他のブロック、ユニットおよび／またはモジュールの数や種類も、エンコーダ１００に含めることができ、エンコーディングプロセスの一部であってよいことを当業者は理解し得る。
【００１９】
次に図２を参照すると、同図は本発明の実施形態によるサブピクセル動き推定のための前処理アルゴリズムを実行するための方法を表すフローチャートである。この方法の動作は、図１のエンコーダ１００に対して内部的におよび／または外部的に実装可能な前処理ユニット１３０などによって、および／または他の任意の適切なユニット、装置、および／またはシステムによって実行可能である。前処理アルゴリズムの動作は、図１のエンコーダ１００のサブピクセル推定ブロック１２０により実行される動作の前に実行される。前処理アルゴリズムの動作は、「セットアップ」または「設計」フェーズとみなすことができる。つまり、これらの動作は、実行時にエンコーダ１００によってリアルタイムで実行される動作とは、時間的にも場所的にも別々に実行される。これらの設計フェーズ動作は、パラメータを生成し、後で実行時（run-time）に使用され得る計算を実行するために、エンコーダ１００が初期化される前に少なくとも一回実行される。
【００２０】
設計または前処理フェーズにおいて、本方法は、マッチング規準の推定に使用され、本明細書において「構築面（building surface）」とも称される複数の面を構築する。これらの面を使用することにより、複数のサンプルを基に実際のマッチング規準の挙動を予測することができる。
【００２１】
ボックス２０１に示すように、本方法は、一つ以上のマッチング規準を選択することを含む。ソースフレームと参照フレームとのマッチング規準は、その二つのフレーム間、またはそれらフレーム内の二つの領域間の差を表す値である。例えば、参照フレームにおいて区画される検索領域内でソースフレームの選択されたマクロブロック（ＭＢ）を検索する場合には、該ソースフレームの選択されたＭＢと検索領域内のＭＢの差が、例えば、ＳＡＤ、ＳＳＤ、あるいはその他任意の方法で算出される。
【００２２】
ボックス２０２に示すように、本方法は、前処理時にサンプルポイントとして使用する複数の位置ずれポイント、例えば、ｎ箇所の位置ずれポイントを選択することを含む。
ボックス２０３に示すように、本方法は、最適な非線形構築面の集合体となるまで修正され得るｎ個の非線形構築面を生成、作成、または定義することを含む。これらの非線形構築面は、動き推定を実行するべく、前処理時に第１の画像と第２の画像とのマッチング規準を推定するために使用される。面の数「ｎ」は、ボックス２０２で選択された「ｎ」箇所の位置ずれポイントの数によって、および／またはその数に応じて決定することができる。「ｎ」箇所の位置ずれポイントの位置は、「ｎ」個の構築面の構成に影響し得る。例えば、「ｎ」箇所の位置ずれポイントは、特定の検索領域に均一に分散していることがある。
【００２３】
理論的には、構築面を生成するには、ｍ＊（２ｐ＋１）２という式を解く必要がある。式中、ｍは使用する面の数であり、ｐはサブピクセル位置で表した検索領域のサイズ、つまり、それらの面がカバーする最大許容位置ずれポイントである。すべての面と補間位置とは同じなので、この式だと、解の数は無限数になり得る。本発明の実施形態は、各面がその対称性を維持できる基本直交面を使用する。例えば、ｎ個の構築面の構成は、各軸に多項式構造を使用して計算してもよい。構築面を形成し得る例示的な一次多項式は、以下の式１〜３で定義される。
（１）Ｚｘ＝ａｘ１＋ａｘ０
（２）Ｚｙ＝ａｙ１＋ａｙ０
式１および式２より式３が得られる。
（３）Ｚ＝ａｘ１ａｙ１ｘｙ＋ａｘ１ａｙ０ｘ＋ａｘ０ａｙ１ｙ＋ａｘ０ａｙ０＝ａ３ｘｙ＋ａ２ｘ＋ａ１ｙ＋ａ０
式３によって表される例示の面は、四つの自由係数（すなわち、ａ３、ａ２、ａ１、およびａ０）を有する。高次多項式は、（ｎ＋１）２の係数を有し、式中ｎは多項式次元を表す。後述の実画像データに基づいて自由係数を見つけ出してもよい。
【００２４】
ボックス２０４に示すように、本方法は、本明細書において「テスト領域」と称されるソースフレームまたはブロックと、本明細書において「検索領域」と称される参照フレームまたはブロックとを受信することを含む。これらの両フレームまたはブロックは、最適な構築面を見つけるために前処理アルゴリズムによって統計データとして使用されるアプリケーションの典型的なデータを含み得る。本方法は、多数の典型的なソースフレームと参照フレームとの集合を使用して、後述する反復的な方法で最適な非線形構築面の集合を計算してもよい。
【００２５】
ボックス２０５に示すように、本方法は、ソースフレームと参照フレームとの間の実際のマッチング面を計算することを含む。この実際のマッチング面を計算することは、完全検索、つまり、すべてのフルピクセル位置と複数のサブピクセル位置で一つ以上のマッチング規準を計算することを含む。計算された実際のマッチング面は、ソースフレームと参照フレームとのマッチングを表し得る。
【００２６】
ボックス２０６に示すように、本方法は、ボックス２０５で計算された実際のマッチング面上の値をボックス２０２で選択されたｎ箇所の位置ずれポイントで読み込むこと、つまり、ｎ箇所の位置ずれポイントで実際のマッチング面をサンプリングすることを含む。
【００２７】
ボックス２０７に示すように、本方法は、ボックス２０６でサンプリングされ、実際のマッチング面から取得されたサンプルと、ボックス２０３で生成された構築面に基づいて推定マッチング面を生成することを含む。例えば、推定マッチング面は、（ボックス２０２の）ｎ箇所のサンプルポイントの各々を、（ボックス２０３の）ｎ個の構築面の各々で掛け合わせ、その結果を合計することによって生成してもよい。
【００２８】
ボックス２０８に示すように、本方法は、推定マッチング面と実際のマッチング面との間の誤差が最小となるように、基本直交面を有するボックス２０３で生成されたｎ個の構築面を更新することを含み得る。更新された構築面を使用して、実際のマッチング面の挙動を予測してもよい。
【００２９】
例えば、式３の各々の自由係数は、ボックス２０４で受信されるソースフレームおよび参照フレームなどの統計データなどから派生される標準面を有する。例えば、一次多項式の面は、下記の式４に示すように定義される。
【００３０】
式４：
【００３１】
【数１】
2010233208.tif 000002
推定マッチング面と実際のマッチング面との間の誤差を統計データに基づいて最小化すると、式４で表される理論上の基本面が変化し、下記の式５に示すように、実際のマッチング面をより正確に表すことができる。
【００３２】
式５：
【００３３】
【数２】
2010233208.tif 000003
ボックス２０９に示すように、本方法は、更新された基本面を、即ち、多数のデータ集合（例えば、多数の典型的ソース画像および参照用画像や、フレームや、またはフレームのブロックなど）に基づく（ボックス２０８の）構築面をテスト、確認、または調査することを含む。テストすることは、（ボックス２０８の）推定面を使用して、ソース画像および参照画像に関する全動き（full motion ）推定を実行することを含み得る。（ボックス２０８の）推定面と、（ブロック２０５の）計算された実際のマッチング面との間の総誤差を、所望の所定しきい値と比較し、その総誤差が、先に計算された総誤差または或る所定しきい値より小さい場合には、ボックス２１１に示すように、現在の更新された基本（構築）面が、エンコーダによってリアルタイム処理で使用される。
【００３４】
総誤差がしきい値よりも大きいか、先に計算された総誤差以上の場合、本方法はボックス２０４に戻ることを含み得る。それぞれの反復処理において、ボックス２０３で作成された最初の基本面に代わりに、更新された基本面（構築面）を使用することができる。更新された基本面を使用しない場合には、元の基本面が使用される。さらに、誤差がしきい値よりも大きい場合でも、図２に記載されている反復プロセスを中断し、現在の更新面を使用して推定マッチング面［ボックス２１１］を作成してもよい。ただし、面パラメータの変化により、総誤差は大きくなる。
【００３５】
構築面は、図３に記載されているソースフレームと参照フレームとの間の動きベクトルを見つけるために、図１のサブピクセル動き推定１２０によってリアルタイム処理で使用される。
【００３６】
次に図３を参照すると、同図は、本発明の実施形態によるリアルタイムで動的なサブピクセル動き推定アルゴリズムを実行するための方法を表すフローチャートである。本方法の動作は、例えば、図１のサブピクセル動き推定ブロック１２０、および／または他の適切なユニット、装置、および／またはシステムによって実装してよい。実施形態によっては、前処理ユニット１３０によってオフラインで実行される演算結果を用いて、サブピクセル動き推定アルゴリズムの動作をエンコーディングプロセスの実行時にリアルタイムで動的に実行してもよい。他の実施形態においては、基本面を更新するなどの目的で、前処理ユニット１３０の動作をエンコーディングプロセスの実行時にリアルタイムで実行してもよい。
【００３７】
ボックス３０１に示すように、本方法は、ソースフレームおよび参照フレームをリアルタイムで受信することを含む。ソースフレームおよび参照フレームは、図１のエンコーダ１００によってエンコードされる動画ストリームのフレームであってもよい。
【００３８】
ボックス３０２に示すように、本方法は、ソースフレームと参照フレームとの間の差、つまり、一つ以上のマッチング規準を、以前に選択されたマッチング規準（図２のボックス２０１）に従って以前に選択されたｎ箇所のサンプルポイント（図２のボックス２０２）の位置で、リアルタイムで計算することを含む。
【００３９】
ボックス３０３に示すように、本方法は、（ボックス３０２で計算された）サンプルと、前処理フェーズから取得された構築面（図２のボックス２１１）を基に、推定マッチング面を生成することを含む。例えば、推定マッチング面は、ｎ箇所のサンプルポイントの各々に、前処理フェーズで計算された各々の構築面を掛け合わせ、その結果を合計することによって生成することができる。面推定プロセスにより、実際のマッチング面をリアルタイムで計算することなく、前処理フェーズで見つかった構築面を基に、実際のマッチング面を表す式の自由係数を取得してもよい。これらの係数は、計算されたｎ箇所のサンプルポイントなど、既知のサンプル値を用いて取得してもよい。サンプルポイントの数は、実際のマッチング面を表す式の自由係数の数と、少なくとも同じであればよい。例えば、式の集合を解析するために、自由係数ごとに所与の値を使用してもよい。式の解析は、逆行列乗算を用いるなど、線形式の集合の解を求めることによって実行することができる。いくつかの実施形態においては、自由係数の数よりも多くのサンプルポイントを使用してもよい。
【００４０】
ボックス３０４に示すように、本方法は、ボックス３０３で作成された推定マッチング面上の最良マッチ位置、つまり、マッチング規準に対する最良マッチを示す推定面上のポイントを見つけることを含む。最良マッチ位置は、動き推定／補償プロセスを実行するのに必要な動きベクトルを提供し得る。最良マッチ位置は、例えば、動きベクトル自体であってもよい。
【００４１】
次に図４Ａを参照すると、同図は、本発明の実施形態によるサブピクセル動き推定アルゴリズムの例示的なリアルタイム実装を表すフローチャートである。次に図４Ｂを参照すると、同図は、本発明の実施形態を理解する上で役立つ検索領域の例示的なピクセルマップを表す。
【００４２】
例示的なリアルタイム実装では、入力値として、９つの構築面が生成された前処理設計フェーズ（図２に記載）の結果が使用される。例示的な検索領域は、水平線の入った菱形の領域４００と定義される。
【００４３】
図４Ａおよび図４Ｂによって表される例示的な実装は、マッチング規準としてＳＡＤを選ぶこと（ボックス４０１）を含む。面推定に計算および使用される実際のサンプルは、５つのフルピクセル結果および４つのハーフピクセル結果である。このため、フルピクセルの５つのＳＡＤ値（図４Ｂに「Ｆ」で表示）が計算される（ボックス４０２）。加えて、二次元のハーフピクセル（図４Ｂに「Ｊ」で表示）の４つのＳＡＤ値も計算される（ボックス４０３）。
【００４４】
ボックス４０４に示すように、本方法は、行列乗算を用いて９つの式の解を求めるなどして面を推定することを含む。行列乗算は、設計フェーズで先に計算しておいてもよい。
計算の複雑性をさらに低減するために、本方法は、図４Ｂの検索領域４００をさらに減らし、菱形領域４００（ボックス４０５）内に水平線と垂直線との両方が描かれている部分４１０など、最良マッチが得られる見込みが最も高い一部の検索領域４００だけを選択してもよい。このような選択は、図４ＢにＦおよびＪで表されるサンプルなど、検索領域内のサンプルまたはポイントの結果に基づいてもよい。一方、本方法は、検索領域４００全体で実行してもよく、検索領域の他の任意のセクション、領域、部分、またはピクセル数を選択してよいことを当業者は理解し得る。
【００４５】
面が推定されたら、選択領域内で評価可能なすべての位置が評価され得る。たとえば、クォータピクセルがＱで表され、二次元ハーフピクセルがＪで表される領域４００のすべての位置が評価され得る。ボックス４０６に示すように、本明細書において「最良整数値」と称される、全フルピクセル中で最小のＳＡＤを選択してもよい。ボックス４０７に示すように、本明細書において「最良サブピクセル」と称される、全サブピクセル中で最小のＳＡＤを選択してもよい。
【００４６】
最良整数値と最良サブピクセル値とが比較される。最良位置が最良整数値である場合には、フルピクセルが使用される（ボックス４１２）。最良位置が最良サブピクセル値である場合には、サブピクセル補間後に使用される実際の規準を作成するために、最良位置で動き補償（ＭＣ）動作が実行される（ボックス２０９）。その後、ＳＡＤなど実際のマッチング規準が計算され、整数ピクセル結果と比較され得る（ボックス４１０）。計算されたＳＡＤが整数結果よりも良好である場合には、サブピクセル結果が使用される（ボックス４１３）。計算された整数値のＳＡＤの方が良好である場合には、整数結果が使用される（ボックス４１２）。
【００４７】
本発明の実施形態は、取りうる位置を計算するのに使用される構築面を例えば面推定行列を変更することなく変更することによって、あるいは計算された位置を比較する前に重み付けを使用したりすることによって、推定マッチング規準面の異なる位置または場所が出現する頻度を制御し得る。推定および再構成に異なる構築面を使用する場合には、基本直交面の一つなど、すべてのサンプルで同じ値を有する面上の特定位置で一つ以上のサンプル値を減じるなどしてマッチングスコアを人為的に下げることにより、特定の位置を好適化してもよい。例えば、マッチング規準の点でメリットがある場合に特定の場所を使用するために、推定マッチング規準を下げることでこの場所の可能性を下げ得る面を選択してもよい。
【００４８】
本発明の実施形態は、コンピュータまたはプロセッサによる読み取りが可能な媒体などの製品、メモリ、ディスクドライブ、ＵＳＢフラッシュメモリなど、コンピュータ記憶媒体またはプロセッサ記憶媒体、プロセッサまたはコントローラによって実行された場合に、本明細書に開示されている方法を実行するコンピュータ実行可能命令などのエンコード命令、組み込み命令、または記憶命令を含み得る。
【００４９】
本発明の実施形態は、複数の中央処理装置（ＣＰＵ）または他のいかなる適切な汎用または特定プロセッサあるいはコントローラ、複数の入力ユニット、複数の出力ユニット、複数のメモリユニット、および複数の記憶ユニットなどの構成要素などを含み得るが、これらに限定されない。このようなシステムは、他の適切なハードウェア構成要素および／またはソフトウェア構成要素をさらに含み得る。いくつかの実施形態において、このようなシステムは、パーソナルコンピュータ、デスクトップコンピュータ、モバイルコンピュータ、ラップトップコンピュータ、ノート型コンピュータ、端末、ワークステーション、サーバコンピュータ、パーソナル携帯情報（ＰＤＡ）装置、タブレットコンピュータ、ネットワーク装置、またはその他任意の適切な演算装置を備えていてもよく、あるいはこれらの装置であってもよい。
【００５０】
本発明の特定の特徴を本明細書に明示および記載したが、当業者であれば、多くの変形、代用、変更、および等価物を考え得る。特許請求の範囲は、本発明の思想から逸脱しないすべての変形および変更を網羅することを意図する。
【図１】
2010233208.tif 000004
【図２】
2010233208.tif 000005
【図３】
2010233208.tif 000006
【図４Ａ】
2010233208.tif 000007
【図４Ｂ】
2010233208.tif 000008
【外国語明細書】
2010233208000001.pdf