(57)【要約】【課題】  マルチビューのシーケンスのビデオ符号化を行う動き推定方法及び動き推定装置を提供する。【解決手段】  一実施の形態では、マルチビュービデオシーケンスの第１のフレームの１つ以上の画素を識別し、効率的な符号化と意味的正確さ間の所望の相関の指示に基づいて、マルチビュービデオシーケンスの第２のフレームの探索範囲を制限する。マルチビュービデオシーケンスを捕捉する複数のカメラの幾何学的配置を用いることにより、動き推定は、意味的に正確になる。動き推定方法は、第２のフレームの制限された探索範囲内を探索し、第１のフレーム内で識別された画素に一致する画素を検出する。【選択図】  図２
2007502053.tif 000002
【特許請求の範囲】
【請求項１】
マルチビュービデオシーケンスの第１のフレーム内の１つ以上の画素を識別するステップと、
上記マルチビュービデオシーケンスの第２のフレームに関する探索範囲を、効率的な符号化と、該マルチビュービデオシーケンスを捕捉する複数のカメラの幾何学的配置を用いることにより指定される意味的正確さとの間の所望の相関の指示に基づいて、制限するステップと、
上記第２のフレームに関する上記制限された探索範囲内を探索し、上記第１のフレーム内で識別された上記１つ以上の画素に一致する画素を検出するステップとを
有する動き推定方法。
【請求項２】
上記探索範囲は、上記複数のカメラの幾何学的配置により決定される、上記第１のフレーム内の上記１つ以上の画素に対応する上記第２のフレーム内のエピポーラ線の位置に関連して、制限されることを特徴とする請求項１記載の動き推定方法。
【請求項３】
上記第１のフレーム内の上記１つ以上の画素は、ブロックを示すことを特徴とする請求項１記載の動き推定方法。
【請求項４】
上記第２のフレーム内の上記エピポーラ線を計算するステップを更に有する請求項２記載の動き推定方法。
【請求項５】
上記エピポーラ線は、基本行列を用いて計算されることを特徴とする請求項４記載の動き推定方法。
【請求項６】
上記探索範囲を制限するステップにおいて、
上記エピポーラ線上に開始シード位置を検出し、
上記開始シードをカバーするウインドウ及び上記エピポーラ線のパラメータを、上記効率的な符号化と意味的正確さ間の所望の相関に基づいて指定することを特徴とする請求項２記載の動き推定方法。
【請求項７】
上記開始シード位置を、視差ベクトルを用いて検出することを特徴とする請求項６記載の動き推定方法。
【請求項８】
上記効率的な符号化と意味的正確さ間の所望の相関の指示を、ユーザから受信するステップを更に有する請求項１記載の動き推定方法。
【請求項９】
上記効率的な符号化と意味的正確さ間の所望の相関をユーザが入力し易くするユーザインタフェースを介して、該効率的な符号化と意味的正確さ間の所望の相関の指示をユーザから受信することを特徴とする請求項８記載の動き推定方法。
【請求項１０】
上記ユーザインタフェースは、上記効率的な符号化と意味的正確さ間の所望の相関をユーザが指定することができるように、スライダを含むことを特徴とする請求項９記載の動き推定方法。
【請求項１１】
上記ユーザインタフェースは、ユーザが、効率的な符号化と意味的正確さ間の前に指示された所望の相関を、変更することができることを特徴とする請求項９記載の動き推定方法。
【請求項１２】
プロセッサ上で実行されたときに、該プロセッサに方法を実行させるインストラクションを記憶したコンピュータで読取可能な媒体において、上記方法は、
マルチビュービデオシーケンスの第１のフレーム内の１つ以上の画素を識別するステップと、
上記マルチビュービデオシーケンスの第２のフレームに関する探索範囲を、効率的な符号化と、該マルチビュービデオシーケンスを捕捉する複数のカメラの幾何学的配置を用いることによって決定される意味的正確さ間の所望の相関の指示に基づいて、制限するステップと、
上記第２のフレームに関する上記制限された探索範囲内を探索し、上記第１のフレーム内で識別された上記１つ以上の画素に一致する画素を検出するステップとを、
有するコンピュータで読取可能な媒体。
【請求項１３】
上記探索範囲は、上記複数のカメラの幾何学的配置によって決定される、上記第１のフレーム内の上記１つ以上の画素に対応する上記第２のフレーム内のエピポーラ線の位置に関連して、制限されることを特徴とする請求項１２記載のコンピュータで読取可能な媒体。
【請求項１４】
上記第１のフレーム内の上記１つ以上の画素は、ブロックを示すことを特徴とする請求項１２記載のコンピュータで読取可能な媒体。
【請求項１５】
上記動き推定方法は、
上記第２のフレーム内の上記エピポーラ線を計算するステップを更に有する請求項１３記載のコンピュータで読取可能な媒体。
【請求項１６】
上記エピポーラ線は、基本行列を用いて計算されることを特徴とする請求項１５記載のコンピュータで読取可能な媒体。
【請求項１７】
上記探索範囲を制限するステップにおいて、
上記エピポーラ線上に開始シード位置を検出するステップと、
上記効率的な符号化と意味的正確さ間の所望の相関に基づいて、上記開始シードをカバーするウインドウ及び上記エピポーラ線のパラメータを決定するステップとを有する請求項１３記載のコンピュータで読取可能な媒体。
【請求項１８】
上記開始シード位置を視差ベクトルを用いて検出することを特徴とする請求項１７記載のコンピュータで読取可能な媒体。
【請求項１９】
上記動き推定方法は、
上記効率的な符号化と意味的正確さ間の所望の相関をユーザが入力し易くするユーザインタフェースを介して、該効率的な符号化と意味的正確さ間の所望の相関の指示をユーザから受信するステップとを有することを特徴とする請求項１２記載のコンピュータで読取可能な媒体。
【請求項２０】
メモリと、
上記メモリに接続された少なくとも１つのプロセッサを備え、
上記メモリは、上記少なくとも１つのプロセッサが、マルチビュービデオシーケンスの第１のフレーム内の１つ以上の画素を識別する一連のインストラクションを与え、効率的な符号化と、上記マルチビュービデオシーケンスを捕捉する複数のカメラの幾何学的配置を用いることによって決定される意味的正確さ間の所望の相関の指示に基づいて、該マルチビュービデオシーケンスの第２のフレームに関する探索範囲を制限し、上記第２のフレームに関する上記制限された探索範囲内を探索し、上記第１のフレーム内で識別された上記１つ以上の画素に一致する画素を検出する一連のインストラクションを記憶していることを特徴とする備えるコンピュータシステム。
【請求項２１】
上記探索範囲は、上記複数のカメラの幾何学的配置によって決定される、上記第１のフレーム内の上記１つ以上の画素に対応する上記第２のフレーム内のエピポーラ線の位置に関連して、制限されることを特徴とする請求項２０記載のコンピュータシステム。
【請求項２２】
上記第１のフレーム内の上記１つ以上の画素は、ブロックを示すことを特徴とする請求項２０記載のコンピュータシステム。
【請求項２３】
上記プロセッサは、上記エピポーラ線上に開始シード位置を検出し、上記効率的な符号化と意味的正確さ間の所望の相関に基づいて、該開始シードをカバーするウインドウ及び該エピポーラ線のパラメータを決定することによって、上記探索範囲を制限することを特徴とする請求項２１記載のコンピュータシステム。
【請求項２４】
上記プロセッサは、視差ベクトルを用いて上記開始シード位置を検出することを特徴とする請求項２３記載のコンピュータシステム。
【請求項２５】
更に、上記プロセッサは、上記効率的な符号化と意味的正確さ間の所望の相関をユーザが入力し易くするユーザインタフェースを、該効率的な符号化と意味的正確さ間の所望の相関の指示をユーザから受信することを特徴とする請求項２０記載のコンピュータシステム。
【請求項２６】
マルチビュービデオシーケンスの第１のフレーム内で１つ以上の画素を識別するブロック識別器と、
上記マルチビュービデオシーケンスの第２のフレームに関する探索範囲を、効率的な符号化と、該マルチビュービデオシーケンスを捕捉する複数のカメラの幾何学的配置を用いることによって決定される意味的正確さ間の所望の相関の指示に基づいて、制限する探索範囲決定器と、
上記第２のフレームに関する上記制限された探索範囲内を探索し、上記第１のフレーム内の上記１つ以上の画素に一致する画素を検出する探索器とを備える動き推定装置。
【請求項２７】
上記探索範囲は、上記複数のカメラの幾何学的配置によって決定される、上記第１のフレーム内の上記１つ以上の画素に対応する、上記第２のフレーム内のエピポーラ線の位置に関連して、制限されることを特徴とする請求項２６記載の動き推定装置。
【請求項２８】
上記第１のフレーム内の上記１つ以上の画素は、ブロックを示すことを特徴とする請求項２６記載の動き推定装置。
【請求項２９】
更に、上記探索範囲決定器は、上記第２のフレーム内の上記エピポーラ線を計算することを特徴とする請求項２７記載の動き推定装置。
【請求項３０】
上記探索範囲決定器は、上記エピポーラ線上に開始シード位置を検出し、上記効率的な符号化と意味的正確さ間の所望の相関に基づいて、上記開始シードをカバーするウインドウ及び上記エピポーラ線のパラメータを決定することによって、上記探索範囲を制限することを特徴とする請求項２７記載の動き推定装置。
【請求項３１】
更に、上記探索範囲決定器は、上記効率的な符号化と意味的正確さ間の所望の相関をユーザが入力し易くするユーザインタフェースを、該効率的な符号化と意味的正確さ間の所望の相関の指示をユーザから受信することを特徴とする請求項２６記載の動き推定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には、ビデオ符号化に関する。より詳しくは、本発明は、マルチビュービデオ符号化の動き推定を実行する動き推定方法及び装置に関する。
【関連出願】
【０００２】
本発明は、２００３年８月７日に出願された米国仮出願番号６０／４９３，８８３号の優先権を主張し、その出願の明細書及び図面は、本明細書において援用される。
【著作権注意／許可】
【０００３】
本明細書の一部は、著作権保護の対象となる内容を含んでいる。著作権者は、米国特許商標庁の特許ファイル又は記録のコピーに対しては、異論はないが、それ以外のあらゆる著作権は保有する。明細書及び図面に記載したソフトウェア及びデータの著作権は、ソニーエレクトロニクスインクに帰属する。
【背景技術】
【０００４】
動き推定及び動き補償は、ビデオシーケンス全体のビットレートを低減する効果的な方法である。動き推定は、フレーム間の画像サンプル（例えば、複数の画素）の動きを推定する処理である。符号化器は、動き推定を用いて、１つのフレーム内の画素のブロックを、別のフレームの画素のブロックに一致させることを試みる。所定の探索範囲内で最も類似したブロックが見つかった後、対応する画素間の位置の変化は、近似され、動きデータ、例えば動きベクトルとして表される。動き補償は、予測画像を決定し、予測画像と元の画像間の誤差を計算する処理である。符号化器は、動き補償を用いて、動きデータを画像に適用して、予測画像を算出する。予測画像と入力画像間の差分は、誤差信号と呼ばれる。
【０００５】
従来の動き推定及び動き補償方法は、様々な符号化器（例えば、ＭＥＰＧ−ｘ符号化器、Ｈ．２６ｘ符号化器等）に用いられており、シングルビューのビデオシーケンスを時間に亘って効率的に圧縮することができる。しかしながら、これらの方法によるマッチング（match）は、圧縮の観点からは効率的であるが、ビデオシーケンスの基礎となる「真の」動きを表す必要がないので、多くの場合、意味論的には正しくない。
【発明の開示】
【課題を解決するための手段】
【０００６】
マルチビューのシーケンスのビデオ符号化をする動き推定方法及び装置について説明する。例示的な動き推定方法は、マルチビュービデオシーケンスの第１のフレーム内の１つ以上の画素を識別し、効率的な符号化と意味的正確さ間の所望の相関の指示に基づいて、マルチビュービデオシーケンスの第２のフレームに関する探索範囲を制限する。意味的正確さは、マルチビュービデオシーケンスを捕捉する複数のカメラの幾何学的配置を用いることによって決定される。動き推定方法は、第２のフレームに関する制限された探索範囲内を探索し、第１のフレーム内で識別された画素に一致する画素を検出する。
【発明を実施するための最良の形態】
【０００７】
以下、本発明の実施の形態を図面を参照して、詳細に説明する。なお、図面において、同じ参照番号は、同じ構成要素を示し、本発明を実施することができる特定の実施の形態を例示的に示す。当業者が本発明を実施することができるように、これらの実施の形態を詳細に説明する。また、その他の実施の形態を用いることもでき、本発明の範囲から逸脱することなく論理的、機械的、電気的、機能的及びその他の変更を行うことができることは明らかである。したがって、本発明は、以下の詳細な説明に限定されるものではなく、本発明の範囲は、特許請求の範囲によってのみ定義される。
【０００８】
図１は、本発明を適用した符号化装置の一実施の形態の構成を示すブロック図である。符号化装置１００は、ＭＰＥＧ‐ｘ及びＨ‐２６ｘ等のビデオ符号化規格に準拠してマルチビュー符号化を実行する。符号化装置１００は、ハードウェア、ソフトウェア又は両方の組合せで実現をすることができる。ソフトウェアで実現する場合は、符号化装置１００は、従来のコンピュータで読取可能な様々な媒体に保存して、配信することができる。ハードウェアで実現する場合には、符号化装置１００の各モジュールは、デジタル論理回路（例えば、集積回路）で実現される。また、幾つかの機能をコンピュータ周辺機器内の特殊用途のデジタル論理回路内において最適化し、ホストコンピュータの処理負荷を軽減することができる。
【０００９】
符号化装置１００は、信号受信機１０２と、動き推定器１０４と、動き補償器１０６と、符号化モジュール１０８と、バッファ１１０と、フレーム再構成器１１２とを備える。信号受信機１０２は、マルチビュービデオシーケンスのビデオ信号を受信し、マルチビュービデオシーケンス内に含まれる個々のフレームを動き推定器１０４に供給する。
【００１０】
動き推定器１０４は、マルチビュービデオシーケンスの現フレームと、前フレームから再構成され、バッファ１１０に記憶されているフレームとを比較し、前フレームに対する現フレームの動きを推定する。特に、動き推定器１０４は、現フレームの各画素（又は画素のブロック）に一致する再構成された前フレームの各画素を探索し、各画素又はブロックの動きベクトルを算出する。得られる動きベクトルは、動き推定器１０４の出力である。
【００１１】
動き補償器１０６は、動きベクトル及び再構成された前フレームを読み込み、現フレームに対する予測画像を算出し、現フレームから予測画像を減算し、残差フレームが得られる。
【００１２】
符号化モジュール１０８は、残差フレームに様々な符号化処理を施して信号を圧縮し、圧縮信号をこの符号化装置１００の出力とする。符号化処理の例として、適応量子化と組み合わせた離散コサイン変換（ＤＣＴ）、差分符号化（differential coding）、ランレングス符号化（ＲＬＣ）、可変長符号化（ＶＬＣ）等がある。
【００１３】
フレーム再構成器１１２は、残差フレームを予測画像に加算し、再構成された現フレームを生成して、バッファ１１０に記憶する。この再構成された現フレームは、次の予測画像として、動き推定器１０４及び動き補償器１０６によって用いられる。
【００１４】
一実施の形態において、動き推定器１０４は、ブロック識別器１１４と、探索範囲決定器１１６と、探索器１１８と、動きベクトル算出器１２０とを備える。ブロック識別器１１４は、信号受信機１０２から供給されるマルチビュービデオシーケンスからフレームを分離し、現フレームをブロック（又は各画素）に分割し、各ブロック（又は画素）を探索範囲決定器１１６に供給する。
【００１５】
探索範囲決定器１１６は、マルチビュービデオシーケンスの符号化された前フレーム内で一致するブロック（matching block）を探索するための探索範囲を決定する。探索範囲決定器１１６は、マルチビューのシーケンスを捕捉するために用いられた複数のカメラの幾何学的配置に基づいて、探索範囲を決定する。複数のカメラの幾何学的配置は、探索範囲を決定するために用いるときは、マルチビューの幾何学的形状を制限し、この幾何学的形状の制限により、マッチングの意味的正確さ（semantic accuracy of matching）をより高め、探索の複雑さを軽減することができる。
【００１６】
一実施の形態では、マルチビューの幾何学的形状の制限は、エピポーラ幾何学によって説明される。特に、エピポーラ幾何学に基づく、同じ場面を見る一対の視野では、第１の視野における任意の画素の意味論的な真の一致は、その画素に対応した第２の視野におけるエピポーラ線に沿って存在する。したがって、探索範囲決定器１１６は、前フレーム内のエピポーラ線の位置を用いて、適切なブロックの探索範囲を決定する。より詳しくは、探索範囲決定器１１６は、効率的な符号化とマッチングの意味的正確さ間の所望の相関に基づいて、エピポーラ線の位置に関連した探索範囲をどのように制限するかを決定する。すなわち、意味的正確さをより高くするためには、探索範囲決定器１１６は、探索範囲をエピポーラ線により近い範囲に制限する。一実施の形態では、効率的な符号化とマッチングの意味的正確さ間の所望の相関は、（例えば、符号化装置１００が用いられるアプリケーションの要求に基づいて）、ユーザにより指定され、また、何時でも変更することができる。
【００１７】
探索器１１８は、前フレームの決定された探索範囲内で一致するブロックを探索し、動きベクトル算出器１２０は、このブロックの動きベクトルを算出する。
【００１８】
したがって、符号化装置１００は、ブロックベースのマッチングにマルチビューの幾何学的形状の制限を組み合わせることによって、マッチングの意味的正確さをより高めている。この方法を、本明細書では意味ベースの動き推定（semantics-based motion estimation）と呼ぶ。更に、符号化装置１００は、制限の強さ（hardness of the constraint）を変えることができ、それにより、ユーザは、効率的な圧縮とマッチングの意味的正確さ間の相関を制御することができる。
【００１９】
図２及び図３は、本発明の様々な実施の形態に基づいて、図１に示す動き推定器１０４が実行する動き推定処理を示すフローチャートである。動き推定処理は、ハードウェア（例えば、回路、専用論理回路等）、ソフトウェア（例えば、汎用コンピュータシステム又は専用マシン上で実行されるソフトウェア）、又はそれらの両方の組合せからなる処理ロジックによって実行される。処理をソフトウェアで実行する場合、フローチャートの説明により、当業者は、適切に構成されたコンピュータ（コンピュータで読取可能な媒体（メモリを含む）からのインストラクションを実行するコンピュータのプロセッサ）上において、動き推定処理を実行するインストラクションを含むそのようなプログラムを開発することができる。コンピュータで実行可能なインストラクションは、コンピュータプログラミング言語で書かれており、或いはファームウェア論理回路で実現されている。コンピュータで実行可能なインストラクションが、公認の規格に準拠したプログラミング言語で書かれている場合、そのようなインストラクションは、様々なハードウェアプラットフォーム上で実行され、様々なオペレーティングシステムにインタフェースすることができる。なお、本発明の実施の形態は、いかなる特定のプログラミング言語に関連して説明していない。また、様々なプログラミング言語を用いて、ここに説明する技術を実現できることは明らかである。更に、一形式のソフトウェア又は他の形式のソフトウェア（例えば、プログラム、手続き、処理、アプリケーション、モジュール、ロジック）を、動作を実行し、結果を生ずると技術的に説明することは、普通に行われていることである。このような表現は、コンピュータのプロセッサに動作を実行させ、又は結果を生じさせるコンピュータによるソフトウェアの実行を単に簡単に説明したものである。本発明の範囲から逸脱することなく、図２及び図３に示す動き推定処理に更に処理を追加したり、処理を削除でき、また、ここで説明するブロックの配置の順番は、特定の順番を表していないことは、言うまでもない。
【００２０】
図２は、マルチビュービデオシーケンスの動き推定を実行する処理２００の一実施の形態を表すフローチャートである。
【００２１】
図２に示すように、処理ロジックは、マルチビュービデオシーケンスの第１のフレーム内の１つ以上の画素を識別する（処理ブロック２０２）。第１のフレームは、現在処理されているフレームである。１つ以上の画素は、ブロック又は個々の画素を表すことがある。
【００２２】
処理ブロック２０４において、処理ロジックは、マルチビュービデオシーケンスの第２のフレームにアクセスし、第１のフレームの上述した画素に対応する第２のフレーム内のエピポーラ線を計算する。第２のフレームは、前に処理されたフレーム（例えば、動き推定器１０４によって再構成され、バッファ１１０に記憶されたフレーム）である。一実施の形態では、第１のフレームの個々の画素に対して動き推定が実行され、エピポーラ線は、適切な画素に対応する。他の実施の形態では、第１のフレーム内のブロックに対して動き推定が実行され、エピポーラ線は、適切なブロック内の所定位置の画素に対応する。一実施の形態では、エピポーラ線は、基本行列（Ｆマトリックス）を用いて算出され、エピポーラ幾何学の代数表現である。エピポーラ線の計算は、以下の式によって表すことができる。
【００２３】
ｌ１＝Ｆｘ０
ここで、ｌ１は、第１の画像内の画素ｘ０に対応した第２の画像内のエピポーラ線である。なお、当業者には、エピポーラ線を普遍性を失うことなく、従来の他の方法を用いて算出できることは明らかである。
【００２４】
次に、処理ロジックは、算出されたエピポーラ線を用いて、第２の画像内の一致する画素を検出するための探索範囲を決定する。特に、処理ブロック２０６において、処理ロジックは、効率的な符号化とマッチングの意味的正確さ間の所望の相関の指示に基づいて、エピポーラ線に関連した探索範囲を制限する。所望の相関は、エピポーラ線に対する探索範囲の近さを決定する（例えば、意味的正確さが効率的な符号化よりも重要な場合は、処理ロジックは、探索範囲をエピポーラ線により近い範囲に制限し、又は、その逆）。一実施の形態において、効率的な符号化と意味的正確さ間の相関の指示は、処理ロジックによって提供されるユーザインタフェースを介して、ユーザにより指定される。一実施の形態では、エピポーラ線上の特定の位置に関連した探索範囲を更に制限するために、開始シードが用いられ、この詳細については後述する。他の実施形態では、シードは、用いられない。むしろ、第１のフレーム及び第２のフレームは、フレーム内のあらゆる画素について、他のフレーム内の対応するエピポーラ線が、画素の位置に合わされた水平走査線となるような性質を満たすように、調整される。歪みの調整（Rectification）は、ホモグラフィー（homography）、すなわち２つのフレームのそれぞれの二次元の投影的歪み（2D projective warp）を計算して、これらの歪みを除去する処理である。様々なアルゴリズムを用いて、調整するホモグラフィーを計算し、それに従って、フレームの歪みを修正することができる。
【００２５】
処理ブロック２０８において、処理ブロック２０６で決定された第２のフレームの探索範囲内で、第１のフレームの１つ以上の画素に一致する画素を探索する。
【００２６】
その後、処理ブロック２１０において、処理ロジックは、画素の位置の変化に基づいて、動きベクトルを計算する。
【００２７】
図３は、シーディング法（seeding approach）を用いた動き推定の探索範囲を決定する処理３００の一実施の形態を表すフローチャートである。
【００２８】
図３に示すように、処理ロジックは、ユーザから、効率的な符号化とマッチングの意味的正確さ間の所望の相関の指示を受信する（処理ブロック３０２）。一実施の形態では、これらの２つの要素間の所望の相関のユーザからの指示は、ユーザインタフェースを介して受信される。例えば、ユーザインタフェースは、２つの要素の加重（cumulative weight）又は割合（例えば、１００％）を示し、ユーザは、加重又は割合を分配することができる（例えば、ユーザは、２０％を効率的な符号化に割り当て、８０％を意味的正確さに割り当てることができる）。あるいは、ユーザインタフェースにスライダを設け、ユーザがこれらの２つの要素間の所望の相関を指定できるようにしてもよい。
【００２９】
処理ブロック３０４において、符号化されるブロックのエピポーラ線上の開始シードの位置を検出する。一実施の形態では、開始シードは、視差ベクトルを用いて検出される。異なる視点から同じ場面を同じスナップショットで同時に捕捉した他の視野における最も意味論的に正確に一致する画素を検出するための第１の画像の各画素の視差ベクトルを、ステレオアルゴリズムを用いて計算する。そのような視差ベクトルが利用可能なときは、適切な視差ベクトルを開始シードとして用いる。
【００３０】
処理ブロック３０６において、処理ロジックは、効率的な符号化とマッチングの意味的正確さ間の所望の相関に基づいて、開始シードの周囲のウインドウ及びエピポーラ線のパラメータを決定する。一実施の形態では、符号化されるブロックの最適なマッチングを求めるメトリックは、以下の数１で表すことができる。
【００３１】
【数１】
2007502053.tif 000003
【００３２】
ここで、ｍｖｄｘ、ｍｖｄｙは、それぞれ、視差ベクトルのシード位置からの動きベクトルのエピポーラ線に対する平行な変位、直角な変位に対応する。Ｓｄｉｓｐｗは、視差ベクトルにより得られるシード位置の周囲の探索ウインドウ（大きさｗ×ｗ）内の候補予測値全体の集合に対応する。ＳＡＤは、符号化されるブロックと候補ｍｖによって表される候補ブロックとの絶対差分の画素毎の合計を表す。ｍｖｂｉｔｓ（ｍｖｄ）は、差分動きベクトル（動きベクトルの大きさの増加関数）の符号化に必要なビット数を表す。λは、目標とする品質に対応した適切なラグランジュ乗数である。
【００３３】
λｙに対するλｘの相対値を下げることによって、処理ロジックは、マッチングをエピポーラ線のより近くで行い、意味的正確さをより確実にすることができる。λｙ＝∞の場合、エピポーラ線に沿った探索に対応している。これは、視差ベクトルを計算する必要性をなくして、マルチビュー幾何学を用いてエピポーラ線を算出した特殊な場合である。
【００３４】
動き探索のために視差ベクトルをシードとして用いることにより、シードの周囲のウインドウを比較的小さくし、良好な圧縮効率及び意味的正確さを有するマッチングを行うことができる。更に、より小さな探索ウインドウを用いることにより、探索処理の複雑さを軽減することができる。更に、良好な意味的に正確なマッチングは、通常、エピポーラ線のより近くで行われるので、探索は、（標準的な動き推定における二次元探索よりはむしろ）一次元探索となり、探索処理の複雑さを更に軽減することができる。
【００３５】
図４は、マルチビュービデオシーケンスの具体的な２つのフレームを示す図である。フレーム４０２内の符号化される点に対して、視差シードが前フレーム４０４内で検出される。ウインドウ４０６は、従来の動き推定を示しており、視差シードの周囲に決定された探索範囲は、エピポーラ線の位置に基づいて制限されていない。ウインドウ４０８は、視差シードの周囲及びエピポーラ線の近くに決定された探索範囲に影響を与えるエピポーラ幾何学の制限を組み込んだ動き推定を示している。ウインドウ４１０は、探索範囲をエピポーラ線に沿うように限定することによって最高の意味的正確さを目標とした動き推定を示している。
【００３６】
図５は、マルチビュービデオシーケンスの、異なる動き推定方法を用いた実験により得られるビットレートの比較を示している。第１列は、動き探索のために視差ベクトルをシードとして用いた標準的な動き推定の場合におけるビットレートを示す。この標準的な動き推定では、シードの周囲に小さな探索ウインドウを用いて、良好な圧縮効率を有するマッチングを行っている。これは、水平及び垂直ラグランジュ乗数の相対加重が近い場合に対応しており、最大の圧縮が得られる。
【００３７】
第２列及び第３列は、マッチングをエピポーラ線の近くに保つ方向のバイアスを強くした（水平ラグランジュ乗数をより大きくした）場合を示している。これにより、エピポーラ線の近くにマッチングが制限されるので、良好な意味的正確さが得られるが、その結果、圧縮効率は下がる。
【００３８】
図６は、本発明を実施するのに適したコンピュータハードウェア及び他の構成要素を示すブロック図であるが、本発明を限定するものではない。図６は、図１に示す符号化装置１００又は動き推定器１０４として用いるのに適したコンピュータシステムの一実施の形態を示している。
【００３９】
コンピュータシステム６４０は、プロセッサ６５０と、メモリ６５５と、入力／出力装置６６０とを備え、これらはシステムバス６６５に接続されている。メモリ６５５は、プロセッサ６５０によって実行されたときに、上述した動き推定方法を実行するインストラクションを記憶している。入力／出力装置６６０は、プロセッサ６５０によってアクセス可能なあらゆる種類の記憶装置を含む様々な種類のコンピュータで読取可能な媒体を含む。当業者にとって、「コンピュータで読取可能な媒体」という用語は、データ信号を変調する搬送波を更に含むことは明らかである。更に、コンピュータシステム６４０は、メモリ６５５内に記憶されているオペレーティングシステムソフトウェアを実行するプロセッサ６５０によって制御される。媒体に関連する入力／出力装置６６０は、オペレーティングシステム及び本発明の動き推定方法の、コンピュータが実行可能なインストラクションを保存する。図１に示す動き推定器１０４は、プロセッサ６５０に接続された独立した構成要素とすることもでき、あるいはプロセッサ６５０によって実行されるコンピュータで実行可能なインストラクションとして実現することができる。一実施の形態では、コンピュータシステム６４０は、入力／出力装置６６０を介してＩＳＰ（インターネットサービスプロバイダ）接続されており、インターネット上の画像データを伝送又は受信することができる。本発明は、インターネットアクセス及びインターネットのウェブベースのサイトに限定されず、直接接続及びプライベートネットワークも含まれる。
【００４０】
コンピュータシステム６４０は、様々なアーキテクチャを有する多くの考えられる多くのコンピュータシステムの一具体例である。典型的なコンピュータシステムは、通常、少なくともプロセッサと、メモリと、メモリをプロセッサに接続するバスとを有する。当業者には、本発明は、マルチプロセッサシステム、ミニコンピュータ、メインフレームコンピュータ等を含む他のコンピュータシステム構成で実施することもできることは、明らかである。また、本発明は、通信ネットワークを介して接続された遠隔処理装置によってタスクが実行される分散コンピューティング環境においても実施することができる。
【００４１】
最適なスケールファクターを選択する様々な実施の形態を説明した。特定の実施の形態を説明したが、当業者には、同様の目的を達成するように意図されたいかなる構成を、例示した特定の実施の形態に代わに用いることができることは、明らかである。この出願は、本発明の適用及び変更をカバーすることを意図したものである。
【図面の簡単な説明】
【００４２】
本発明を、本発明の様々な実施の形態の図面を以下参照して詳細に説明する。また、以下の詳細な説明は、本発明を特定の実施の形態に限定するものではなく、本発明を説明するためのものである。
【図１】符号化装置の一実施の形態のブロック図である。
【図２】マルチビュービデオシーケンスの動き推定を実行する処理の一実施の形態を表すフローチャートである。
【図３】シーディング方法を用いた動き推定の探索範囲を決定する処理の一実施の形態である。
【図４】マルチビュービデオシーケンスの２つのフレームを例示的に示す図である。
【図５】マルチビュービデオシーケンスの他の動き推定を実行して算出されたビットレートの比較を例示的に表す列である。
【図６】本発明の実施の形態を実行するコンピュータ環境のブロック図である。
【図１】
2007502053.tif 000004
【図２】
2007502053.tif 000005
【図３】
2007502053.tif 000006
【図４】
2007502053.tif 000007
【図５】
2007502053.tif 000008
【図６】
2007502053.tif 000009
【国際調査報告】
2007502053.tif 000010
2007502053.tif 000011
2007502053.tif 000012