(57)【要約】      （修正有）【課題】画素間の類似尺度を高い信頼性で計算する。【解決手段】類似尺度計算装置は、第１の画素２５０と第２の画素２７０との間の類似尺度を計算する。この装置は、それぞれ第１及び第２の画素を中心とする第１及び第２の円形ウィンドウ２５２及び２７２の各々の半径の各々上の画素の画素値を平均化する平均化計算部と、平均化された画素値の第１及び第２の列のフーリエ係数の第１及び第２のシーケンスを出力するＦＦＴ変換部と、第１及び第２のシーケンスの各々を正規化するための正規化ブロックと、ＦＦＴ係数の第１及び第２の正規化されたシーケンス間の距離を計算する距離計算部と、を含む。【選択図】図４
2009217496.tif 000002
【特許請求の範囲】
【請求項１】
画像の第１の画素と画像の第２の画素との類似尺度を計算するための類似尺度計算装置であって、
前記第１の画素と前記第２の画素とをそれぞれ中心とする第１及び第２の円形テンプレートの各々の複数の半径の各々の上にある複数個の画素の画素値をそれぞれ平均化して、前記第１及び第２の円形テンプレートの複数の半径の各々の平均画素値の第１及び第２の列をそれぞれ出力するための平均化手段と、
前記平均画素値の第１及び第２の列をフーリエ変換することによって、フーリエ係数の第１及び第２のシーケンスを出力するための高速フーリエ変換手段と、
前記第１及び第２のシーケンスを前記第１及び第２のシーケンス中のそれぞれの最大要素によって除算することで、前記第１及び第２のシーケンスの各々を正規化するための正規化手段と、
前記フーリエ変換係数の第１及び第２の正規化シーケンス間の距離を計算するための距離計算手段と、を含み、
前記距離が前記第１及び第２の画素の前記類似尺度を示す、装置。
【請求項２】
前記平均化手段は、
前記第１及び第２の円形テンプレートの各々の前記複数個の半径の各々の上にある複数個の画素の画素値をサンプリングするためのサンプリング手段と、
前記第１及び第２の円形テンプレートの各々の前記複数個の半径の各々の上にある前記複数個の画素において前記サンプリング手段によってサンプリングされた前記画素値を平均化するための手段と、を含む、請求項１に記載の装置。
【請求項３】
前記平均化手段は、前記第１及び第２の円形テンプレートの各々において、予め定められた基準半径から、ある角度ｎｄθ、ｎ＝１，．．．Ｎ、ただしｄθは予め定められた定数、だけ回転させた複数個Ｎの半径上の画素値を平均化して、結果として得られる２組の平均化された画素値を前記第１及び第２の列として出力するための手段を含む、請求項１に記載の装置。
【請求項４】
前記整数Ｎは２・（２πｒ）の整数部分、ただしｒは前記円形テンプレートの半径長である、請求項３に記載の装置。
【請求項５】
前記距離計算手段は前記第１及び第２の正規化シーケンスの対応する要素の二乗誤差の和を計算するための手段を含む、請求項１〜請求項４のいずれかに記載の装置。
【請求項６】
コンピュータプログラムであって、コンピュータ上で実行されると、コンピュータを、
画像の第１の画素と画像の第２の画素との類似尺度を計算するための類似尺度計算装置であって、
前記第１の画素と前記第２の画素とをそれぞれ中心とする第１及び第２の円形テンプレートの各々の複数の半径の各々の上にある複数個の画素の画素値をそれぞれ平均化して、前記第１及び第２の円形テンプレートの複数の半径の各々の平均画素値の第１及び第２の列を出力するための平均化手段と、
前記平均画素値の第１及び第２の列をフーリエ変換することによって、フーリエ係数の第１及び第２のシーケンスを出力するための高速フーリエ変換手段と、
前記第１及び第２のシーケンスを前記第１のシーケンス中の最大要素と、前記第２のシーケンス中の同じインデックスの要素とによってそれぞれ除算することで、前記第１及び第２のシーケンスの各々を正規化するための正規化手段と、
前記フーリエ変換係数の第１及び第２の正規化シーケンス間の距離を計算するための距離計算手段と、を含み、
前記距離が前記第１及び第２の画素の前記類似尺度を示す、装置として動作させる、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は画像中の画素間の類似尺度をリアルタイムで計算するための装置及びコンピュータプログラムに関し、特に、ステレオ画像、または動きベクトル検出、３Ｄゲーム開発、アニメーション、動画のエンコード、放送及び通信においてディスパリティを検出するための、画素間のリアルタイムかつフレームごとの類似尺度計算のための装置及びプログラムに関する。
【背景技術】
【０００２】
メディア放送コンテンツにおいて、本物らしい感じを達成するために、送信及び音声―映像マルチメディア技術が速いペースで進展している。視聴者に本物らしさを感じさせるためには、視聴者に対し、超現実的な音声及び映像コンテンツを高速で配信しなければならない。例えば、３Ｄ視覚的コンテンツの獲得がこの分野で有望と思われる。
【０００３】
長年にわたって、周知の赤／緑立体視眼鏡に基づく表示、容積表示、自動立体視表示等の様々な種類の３Ｄ表示技術が開発されてきた。赤／緑立体視眼鏡に基づく表示は２つのカメラからの入力を必要とするが、処理はほとんど不要である。ただし視聴者は特別な眼鏡をかけなければならない。自動立体視３Ｄ表示では特別な眼鏡は必要ないが、コンテンツは３Ｄでキャプチャし３Ｄで配信しなければならない。自然なシーンの３Ｄによるコンテンツの獲得で、既存のテレビジョン放送の品質に達するには、依然としてかなりの困難がある。
【０００４】
従来の２Ｄテレビジョンと対照的に、自動立体視３Ｄテレビジョンはあるシーンの視覚的外観だけでなく、そのシーンの密度の濃い深度マップ情報を必要とする。このため、主に２つの科学的課題がある。すなわち、シーンの視覚的外観と深度マップとをリアルタイムで獲得することと、結果として得られる３Ｄテレビジョン上の３Ｄ外観が、そのシーンの元の視覚的外観とマッチしていなければならない（本物らしさ）ということと、である。
【０００５】
これまで、３Ｄのシーンキャプチャに多くの技術が提案されてきた。極端なものの一つでは、従来の較正済立体視カメラを用いた画像ベースのアプローチによって、深度マップを推定している。別の極端な例では、赤外光の飛行時間（Ｔｉｍｅ−ｏｆ−ｆｌｉｇｈｔ：ＴＯＦ）を用いた光学ベースのカメラを用いて深度を獲得している。
【０００６】
ＴＯＦ３Ｄカメラは正弦波変調された赤外光信号を射出する。光が測定システムを出て対象物に至り、システムに戻るまでの移動に必要な時間が測定され、画像中の各画素の深度が計算される。達成可能な最良の距離精度は、深度距離によるが数センチメートルのオーダであって、動作範囲の制限があり、範囲外の測定値は信頼性が低い。このため、ＴＤＦカメラによる獲得アプローチは３Ｄテレビジョン放送には向いていない。
【０００７】
従来の、較正済立体視に基づくアプローチ（非特許文献１、２）は、画像処理アルゴリズム、すなわちテンプレートマッチングを用いて、左右のカメラ画像からのシーンの深度マップを計算する。これはカメラを較正して、内部及び外部のカメラパラメータを推定することを必要とする。深度マップ推定処理は、同期キャプチャ、較正パラメータを用いた補正、及び左右のカメラ画像の画素間の変位推定のためのテンプレートマッチングを含む。
【０００８】
テンプレートマッチングはまた、動画のエンコードにも用いられる。動画のエンコードにおいて、エンコーダは現フレームに対する先行するフレームの画素の各々の動きベクトルを計算する。この目的のために、エンコーダは先行するフレームの各画素について、テンプレートマッチングによって現フレーム中で最もよくマッチする画素を見出さなければならない。画素の運動は、平行移動、回転、又はその両者を含む。従って、テンプレートマッチングは比較的高い計算力を必要とする。
【非特許文献１】Ｋ．コーノリヒ、「スモールビジョンシステム：ハードウェア及び実現」ロボティクス研究に関する第８回国際シンポジウム、ハヤマ、日本、１９９７年（K.  Konolige,  "Small  vision  systems:  Hardware  and  implementation,"  in  Eighth  International  Symposium  on  Robotics  Research,  Hayama,  Japan,  1997.）
【非特許文献２】Ｃ．サン、「矩形サブ領域化及び３ｄ最大面積技術を用いた高速ステレオマッチング」コンピュータビジョン国際ジャーナル、第４７巻、第１／２／３巻、９９−１１７ページ、２００２年（C.  Sun,  "Fast  stereo  matching  using  rectangular  sub-regioning  and  3d  maximum-surface  techniques,"  International  Journal  of  Computer  Vision,  vol.  47,  no.  1/2/3,  pp.  99-117,  2002.）
【発明の開示】
【発明が解決しようとする課題】
【０００９】
テンプレートマッチングアルゴリズムは通常、正規化相互相関ベースの類似尺度を用いる。
【００１０】
しかし、従来のテンプレートマッチングによるアプローチでは、多くの場合、正確に３Ｄ情報又は動きベクトルを計算することができない。なぜなら、ステレオ画像中の、又は先行するフレームと現フレームとの中の画素の場所によっては、特に、ステレオディスパリティ又は動きベクトル探索アルゴリズムのための探索範囲が未知である場合には、対応のマッチングのための固有の情報を提供しないことがあるからである。さらに、テンプレートマッチングアルゴリズムは画像にノイズがある場合、動きベクトル又は動きベクトル情報を正確に計算することができないことがしばしばである。
【００１１】
従って、この発明の目的の１つは、画素間の類似尺度を高い信頼性をもって計算する装置を提供することである。
【００１２】
この発明の別の目的は、画素間の類似尺度を高い信頼性をもって頑健に計算する装置を提供することである。
【００１３】
この発明のさらに別の目的は、画素の一方が他方に対して平行移動又は回転していても、画素間の類似尺度を頑健に計算する装置を提供することである。
【課題を解決するための手段】
【００１４】
この発明の第１の局面に従った類似尺度計算装置は、画像の第１の画素と画像の第２の画素との類似尺度を計算するための類似尺度計算装置であって、前記第１の画素と前記第２の画素とをそれぞれ中心とする第１及び第２の円形テンプレートの各々の複数の半径の各々の上にある複数個の画素の画素値をそれぞれ平均化して、前記第１及び第２の円形テンプレートの複数の半径の各々の平均画素値の第１及び第２の列をそれぞれ出力するための平均化手段と、前記平均画素値の第１及び第２の列をフーリエ変換することによって、フーリエ係数の第１及び第２のシーケンスを出力するための高速フーリエ変換手段と、前記第１及び第２のシーケンスを前記第１のシーケンス中の最大要素と、前記第２のシーケンス中の同じインデックスの要素とによってそれぞれ除算することで、前記第１及び第２のシーケンスの各々を正規化するための正規化手段と、フーリエ変換係数の第１及び第２の正規化シーケンス間の距離を計算するための距離計算手段と、を含む。前記距離が前記第１及び第２の画素の前記類似尺度を示す。
【００１５】
平均化手段は第１の画素と第２の画素とをそれぞれ中心とする第１及び第２の円形テンプレートの各々の複数の半径の各々の上にある複数個の画素の画素値を平均化する。出力される平均化された画素値の第１及び第２の列は、高速フーリエ変換手段によってフーリエ変換され、フーリエ係数の第１及び第２のシーケンスが得られる。正規化手段は、第１及び第２のシーケンスを第１のシーケンス中の最大要素と、第２のシーケンス中の同じインデックスの要素とによってそれぞれ除算することで、第１及び第２のシーケンスの各々を正規化する。距離計算手段はフーリエ変換係数の第１及び第２の正規化シーケンス間の距離を計算する。この距離が第１及び第２の画素間の類似尺度を示す。
【００１６】
画素値が平均化されるので、画素値のノイズ成分が相殺されるか、又は、大数の法則により、少なくとも削減される。正規化により、第１及び第２のシーケンスからスケーリングファクタが除去される。さらに、フーリエ変換により回転ファクタが除去される。こうして、この装置によって計算される類似尺度は、回転とスケーリングを考慮して、高い信頼性をもって２つの画素間の類似性を示す。
【００１７】
好ましくは、前記平均化手段は、前記第１及び第２の円形テンプレートの各々の前記複数個の半径の各々の上にある複数個の画素の画素値をサンプリングするためのサンプリング手段と、前記第１及び第２の円形テンプレートの各々の前記複数個の半径の各々の上にある前記複数個の画素において前記サンプリング手段によってサンプリングされた前記画素値を平均化するための手段と、を含む。
【００１８】
さらに好ましくは、前記平均化手段は、前記第１及び第２の円形テンプレートの各々において、予め定められた基準半径から、ある角度ｎｄθ、ｎ＝１からＮ、ただしｄθは予め定められた定数、だけ回転させた複数個Ｎの半径上の画素値を平均化して、結果として得られる２組の平均化された画素値を前記第１及び第２の列として出力するための手段を含む。
【００１９】
さらに好ましくは、前記整数Ｎは２・（２πｒ）の整数部分、ただしｒは前記円形テンプレートの半径長である。
【００２０】
距離計算手段は、前記第１及び第２の正規化シーケンスの対応する要素の二乗誤差の和を計算するための手段を含んでもよい。
【００２１】
この発明の第２の局面に従うコンピュータプログラムは、コンピュータ上で実行されると、コンピュータを、画像の第１の画素と画像の第２の画素との類似尺度を計算するための類似尺度計算装置として動作させる。装置は、前記第１の画素と前記第２の画素とをそれぞれ中心とする第１及び第２の円形テンプレートの各々の複数の半径の各々の上にある複数個の画素の画素値をそれぞれ平均化して、前記第１及び第２の円形テンプレートの複数の半径の各々の平均画素値の第１及び第２の列をそれぞれ出力するための平均化手段と、前記平均画素値の第１及び第２の列をフーリエ変換することによって、フーリエ係数の第１及び第２のシーケンスを出力するための高速フーリエ変換手段と、前記第１及び第２のシーケンスを前記第１及び第２のシーケンス中のそれぞれの最大要素によって除算することで、前記第１及び第２のシーケンスの各々を正規化するための正規化手段と、フーリエ変換係数の第１及び第２の正規化シーケンス間の距離を計算するための距離計算手段と、を含み、前記距離が前記第１及び第２の画素の前記類似尺度を示す。
【発明を実施するための最良の形態】
【００２２】
以下で、この発明の実施の形態を図面を参照して説明する。図面及び以下の説明において、同じ構成要素は同じ参照番号を付す。従って、その詳細な説明は繰返さない。
【００２３】
＜動きベクトル推定アルゴリズム＞
動きベクトル推定アルゴリズムはしばしば、パターンマッチングメカニズムに依存する。図４はこの実施の形態における動きベクトル推定のためのテンプレートマッチング処理を示す。図４を参照して、Ｎ番目のフレーム２４０の対象画素２５０（ｘ，ｙ）を含む円形テンプレート（「ブロック」とも呼ぶ）２５２が、二乗誤差、ゼロ平均正規化相互相関法等のさまざまな類似尺度を用いて、（Ｎ＋1）番目のフレーム２６０の同じサイズの円形テンプレート２７２と比較される。最も高い類似尺度を有する円形テンプレートが、（Ｎ＋1）番目のフレーム２６０の画素２７０（ｘ＋ｕ，ｙ＋ｕ）を規定する。このような画素２５０及び２７０は、同じ対象点の画像であると考えられる。以下、Ｎ番目及びＮ＋１番目のフレームを、「フレームＮ」、「先行するフレーム」及び「フレームＮ＋１」「現フレーム」とそれぞれ称する。
【００２４】
動きベクトルの推定において、画素２５０を含む物体２５４の回転も考慮しなければならない。例えば、フレームＮ内の物体２５４を、フレームＮ＋１において平行移動させ、角度θだけ回転させると、物体２７４が得られるが、画素２５０と最もよくマッチする画素２７０を見出すためには、テンプレート２７２をθだけ回転させなければならない。
【００２５】
マッチングアルゴリズムは、先行するフレーム２４０内の２Ｄ円形テンプレートＡ２５２の、現フレーム２６０内の２ＤテンプレートＢ２７２に対する類似尺度を計算する必要がある。一般に、回転とガウスノイズの存在下で、テンプレートＡ及びＢ（２５２及び２７２）を以下のように表すことができる。
【００２６】
【数１】
2009217496.tif 000003
ここで、θは、テンプレート２７２に対するテンプレート２５２の相対的回転である。γ及びΓはそれぞれフレームＮ及びＮ＋１の任意のスケール値（利得要素）を表す。Ｘ―（ここで―は式中文字の上に付されるものである）は平均値を表し、Ｘ〜（ここで〜は式中文字の上に付されるものである）はテンプレートデータの固有の形状又はテクスチャ特性を表すものである。Ｎ（μ,σ２）は、平均μ及び分散σ２≧０の任意のガウスノイズを表すが、ここで画像とノイズデータとは独立である。すなわち、一般に、理想的な条件下では、テンプレートデータの両方が同じオブジェクト部分に属するとき、Ａ〜＝Ｂ〜（θ）であり、フレームＮ及びＮ＋１の画像間の差が回転を全く含まない場合のみ、θはゼロである。
【００２７】
しかし、一般に、我々がアクセスできるのは式１及び式２のＡ及びＢの観測のみであり、画像は、映像ノイズにより、又はＡ〜及びＢ〜が固有の情報を有さず、固有の内的形状特性がないことにより、画像を完璧にマッチングすることはできないであろう。映像ノイズは、レンズ焦点の違い、視野角の違い、及びフレームＮ及びフレームＮ＋１での照明効果のむら等のために生ずる。
【００２８】
＜テンプレートマッチングのための正規化相互相関類似尺度＞
動きベクトル推定アルゴリズム等の様々なパターンマッチングアルゴリズムにおいて、２個の画像テンプレート間の類似度を測定するのに、相互相関値が利用される。これは、（Ｎ＋１）番目の画像フレーム中の１組のテンプレートを、フレームＮから既知のものと１つずつ比較することによって、その１組のテンプレートからマッチするものを見出すのに慣用される。テンプレートの直流値は形状情報を示していないので、式１及び式２から各テンプレートの平均を除去する。これによって以下が得られる。
【００２９】
【数２】
2009217496.tif 000004
式３及び式４の個々の分散はテンプレートデータ及びノイズデータの分散の和に等しい。なぜなら、画像データ（あるシーンの視覚的外観）と画像ノイズとは独立だからである。したがって、分散は以下のように表すことができる。
【００３０】
【数３】
2009217496.tif 000005
さもなければ、Ａ〜とＢ〜とは何ら独自の形状情報を示さない。式３と式４との正規化相互相関式は次のように書くことができる。
【００３１】
【数４】
2009217496.tif 000006
ここでｕはフレームＮ＋１の画像と同じ高さにある線上の場所（ｘ＋ｕ）に対応するテンプレートＡの前もって仮定された変位値であり、θは一般に、画像が回転運動を含まない場合は０であると仮定される。従って、以下の式ではパラメータθを無視することができる。
【００３２】
式７をよりよく分析するために、式３〜式４及び式５〜式６を式７に代入し、これを展開すると、以下のようになる。
【００３３】
【数５】
2009217496.tif 000007
ここでＮ（０，σ２）（ｘ,ｙ）は、Ｎ（０，σ２）分布からくる画素の場所（ｘ,ｙ）でのノイズデータを表す。
【００３４】
明らかに、画像中にノイズがあるときには式８が与える類似尺度の信頼性は低くなる。実世界の条件下では、画像ノイズは電子熱効果、レンズ焦点のずれ、視角の違い、フレームＮ及びフレームＮ＋１での照明効果のむら等のために生ずる。従って、間違ったマッチングを減じるために、パターンマッチングの課題においては類似尺度からノイズ効果を除去しなければならない。
【００３５】
＜テンプレートマッチングのための、ノイズに対し頑健な新しい類似尺度＞
以下では、パターンマッチングの課題に対するこの発明の頑健な類似尺度（Ｒｏｂｕｓｔ  ｓｉｍｉｌａｒｉｔｙ  ｍｅａｓｕｒｅ：ＲＳＭ）の数学的導出を説明する。理想的な場合、パターンＡとパターンＢとは以下のような数学的関係を有し、これが図４に示される。
【００３６】
【数６】
2009217496.tif 000008
ここで、ｕ及びｖはｘ及びｙ方向での変位を示し、θはスケールパラメータ及び回転角度をそれぞれ表わす。しかし、実際には、画像ノイズ、カメラ利得要素のずれ、カメラ６０で反射される照明条件などが、理想的な場合とはかなり異なるであろう。従って、たとえもととなるパターン形状が同じであっても、式（９）の関係はもはや有効でない。そこで、観察されたパターンＡと観察されたパターンＢとを、以下のように表す。簡潔さのため、以下の式では指数と変位パラメータとを省略し、これらを「パターンＡ」及び「パターンＢ」として考える。
【００３７】
【数７】
2009217496.tif 000009
γ、Γ及びθと、ノイズパラメータ（μ，ρ２）とは観察できないので、類似尺度処理ではこれらの影響を消去する必要がある。
【００３８】
図５を参照して、パターンＡ及びＢのサンプリングを以下のように行う。フレーム２８０内の画素において、中心が点Ｑ（ｘc,ｙｃ）にあり、半径２８４の長さがｒである円形テンプレート２８２についてサンプリングを行ったと仮定する。信頼性の高いサンプリングを保証するために、円上のサンプリング点Ｐｎ（ｘｎ，ｙｎ）（ｎ＝１，２からＮ，Ｎ＝２・（２πｒ））の数を選択した。半径ＱＰ１（線２８４）と平行なｘ軸方向に対する半径ＱＰｎ（線２８６）の角度は、θｎで示される。
【００３９】
パターンＡ及びパターンＢを放射状にサンプリングすることとしたのは、ＡとＢとが同一のパターンであって互いに対し回転したものである場合、こうすることによって結果として得られるデータアレイが単に互いに円状にずれるだけで済むからである。放射状データサンプリングのための疑似コードは以下によって与えられる。
【００４０】
//rは画素中のテンプレート半径長
//<xc,yc>はテンプレートの中心座標
dq=(2p)/N;//Nは考慮すべき半径の数
n=1;//第１の半径の初期指数
q1=0;//半径の角度
while(n<=N){
//qnにおける、円上の座標
xn=xc+r×cos(qn);
yn=yc+r×sin(qn);
//半径ｙを示す式ｙ＝ｍｘ＋ｂのｍ、ｂを
//(xc,yc)及び(xn,yn)から計算
//その後半径に沿った画像データをサンプリング
x=xc;
dx=(xn×xc)/r;//(xn-xc)=0の場合は特に注意
k=1
while(k<=r){
y=(int)(m×x+b+0.5);//整数に丸める
ray(k,n)=img(y,(int)(x+0.5));
//画素値を整数に丸める
x=x+dx;
k=K+1;
｝
qn+1=qn+dq;
N=n+1;
}
パターンＡ及びＢのデータセットＤＡ及びＤＢを以下のように編成できる。
【００４１】
【数８】
2009217496.tif 000010
ＤＡ及びＤＢは以下のように表わされる。
【００４２】
【数９】
2009217496.tif 000011
ここでグローバルデータ平均Ｄｘ−にノイズ平均が加算され、
【００４３】
【数１０】
2009217496.tif 000012
と計算される。ただしi＝１，２，…ｒであり、ｊ＝１，２，…，Ｎである。
【００４４】
両方のデータセットからそれらの平均を除去することで、結果として得られるセットを以下のように光強度のずれに対して不変とすることができる。
【００４５】
【数１１】
2009217496.tif 000013
式１６及び１７において、ノイズの項、Ｎ（０,ρ２）は同一分布に従う互いに独立（ｉｎｄｅｐｅｎｄｅｎｔ  ａｎｄ  ｉｄｅｎｔｉｃａｌｌｙ  ｄｉｓｔｒｉｂｕｔｅｄ：ｉｉｄ）でランダム変数からくるものであって、その観測量の分布は性質上ガウス形状となる。他方で、画像の項Ｄｘ＾（＾は式中文字の上に付されるものである）はシーンのパターンからくるものであり、データは既知のパターンについて独立でありかつ決定性である。
【００４６】
大数の法則では、ｉｉｄランダム変数の観測は最終的には母平均に近づきそこにとどまると記載される。さらに、大数の法則の記載によれば、観測数ｎが無限大に近づくと（ｎ→∞）、サンプルの平均はほぼ確実に期待値に収束する。もちろん、実際にはサンプル数はｎ＝１６等の有限数であって、１６≠∞である。しかし、たとえサンプルサイズが有限であっても、上記第１の記載は、類似尺度処理においてノイズの効果を大いに抑制できると考えるに足る手がかりである。そこで、式１６及び１７の行列の各列の平均を以下のようにとる。
【００４７】
【数１２】
2009217496.tif 000014
ここでノイズ項の平均はその真の平均（式１６及び１７ではゼロ）に近づく。画像項の平均は、その形状特性に依存して、必ずしもゼロには近付かない。しかしながら、マッチングの課題では、少なくとも２本の半径が非ゼロの平均を生じさせる必要がある。そうでなければ、これらは形状情報を担持しない。
【００４８】
結果として得られるａｋ係数はノイズが抑制されている（最良の場合、ノイズが全くない）。式１８を用いて得られたすべてのａｋ係数をアレイの形に配列することで、以下が得られる。
【００４９】
＿ａ＝［ａ１ａ２ａ３．．．ａＮ］      （１９）
＿ｂ＝［ｂ１ｂ２ｂ３．．．ｂＮ］      （２０）
結果として得られる＿ａ及び＿ｂ（＿はベクトルを表す）の係数の組は、スケール及び回転情報と、形状情報と、を含む。従って、＿ａと＿ｂとの類似尺度処理に先立って、スケール及び回転情報を削除しなければならない。このため、上述のアレイに別個に高速フーリエ変換（ｆａｓｔ  Ｆｏｕｒｉｅｒ  ｔｒａｎｓｆｏｒｍ：ＦＦＴ）を行って、以下を得る。
【００５０】
【数１３】
2009217496.tif 000015
ここでφはＦＦＴ係数の位相シフトを表す。Ａ０及びＢ０はＦＦＴ処理のゼロ番目の係数であり、グローバルな直流値が式１６及び式１７のデータセットから削除されているため、ゼロである（従って、破棄される）。
【００５１】
ベクトル＿ａのＦＦＴ変換のｋ番目の計数Ａ［ｋ］は、以下の式で計算される。
【００５２】
【数１４】
2009217496.tif 000016
ベクトル＿ｂのＦＦＴ係数Ｂ［ｋ］も同様に計算され得る。
【００５３】
最大（優勢）係数
【００５４】
【数１５】
2009217496.tif 000017
を計算することで、２つのパターンの間の位相シフトφを推定することができる（または、平均演算を利用してもよい。）もしφが予想より大きければ、マッチ候補としてパターンＢを完全に破棄することができる。そうでなければ、ＦＦＴ係数から位相項を削除し、これらを好ましくは最大係数Ａｋで正規化することによって、（残っていたとしても）ノイズの効果を以下のようにさらに抑制して、スケーリングファクタを相殺する。
Ｉia＝Ai/Ak  及び  Ｉib＝Bi/Bk
この結果、以下が得られ、ここで、結果として得られる係数の組Ｉａ及びＩｂはそれぞれ、パターンＡ及びパターンＢの固有の不変パラメータである。
【００５５】
【数１６】
2009217496.tif 000018
さて、２つのパターン間の類似尺度は、以下の二乗誤差の和を用いて、信頼性をもって計算することができる。
【００５６】
【数１７】
2009217496.tif 000019
動きベクトルの推定について、最良のマッチ（一致）は最小値
【００５７】
【数１８】
2009217496.tif 000020
を生じるパターンの対の中から、大域的最小点として見出される。又は、不変量の対間の最大絶対値差（または何らかの他の）方法を用いてもよい。
【００５８】
正規化相互相関ベースの類似尺度アルゴリズムは、画像ノイズがあるときにはあまり信頼性の高い結果が得られず、任意の回転にうまく対処できないことを、数学的に示した。他方で、提案されたＲＳＭアルゴリズムは、回転に対し不変の画像特徴を抽出し、画像ノイズ効果を抑制または除去する。
【００５９】
＜システムセットアップ＞
[構造]
上述のとおり、この実施の形態では円形テンプレートの頑健な類似尺度によって高められたマッチングパターン探索アルゴリズムを利用する。
【００６０】
図１は、この実施の形態に従ったビデオエンコーディングシステム４０の全体構造を示す。図１を参照して、ビデオエンコーディングシステム４０は、ビデオカメラ６０と、モニタ７４と、カメラ６０からの画像ストリームをエンコードされた映像データにエンコードするための映像処理システム５０とを含む。見られるとおり、映像処理システム５０はキーボード８０、マウス８２、ＤＶＤメディア１０８を駆動するためのＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ：ディジタル多用途ディスク）ドライブ７６、及び外部メモリを接続可能な外部メモリポート７８を備えたコンピュータ７０を含む。カメラ６０はコンピュータ７０のビデオ入力ポートに接続される。モニタ７４はコンピュータ７０のビデオ出力ポートに接続される。
【００６１】
図２はコンピュータ７０で実現されたこの実施の形態の映像処理システム５０のハードウェアブロック図である。図２を参照して、ＤＶＤドライブ７６及びメモリポート７８に加えて、コンピュータ７０は、中央処理装置（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ：ＣＰＵ）９０と、ＣＰＵ９０に接続された双方向データアドレスバス９２と、バス９２に接続された読出し専用メモリ（ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ：ＲＯＭ）９４と、バス９２に接続されたランダムアクセスメモリ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）９６と、バス９２に接続されたハードディスクドライブ（Ｈａｒd  Ｄｉｓｋ  Ｄｒｉｖｅ：ＨＤＤ）９８と、バス９２に接続され、カメラ６０からのビデオ画像ストリームを受取るためのビデオキャプチャボード１０２と、バス９２とモニタ７４とに接続され、入来するフレームシーケンスをエンコードし、ＨＤＤ９８に記憶されるエンコードされたビデオストリームをデコードし、デコードされたビデオストリームをモニタ７４に供給するためのグラフィック処理ユニット（Ｇｒａｐｈｉｃ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ：ＧＰＵ）１０４とを含む。コンピュータ７０内の構成要素はすべてバス９２に接続され、互いにアクセス可能である。
【００６２】
別の局面では、リアルタイム映像処理システム５０の機能はコンピュータ７０で実行されるソフトウェアで実現される。図３はリアルタイム映像処理システム５０の機能的ブロック図である。
【００６３】
図３を参照して、機能的には、リアルタイム映像処理システム５０は、カメラ６０からの少なくとも２つの連続したフレームを記憶するフレームメモリ１３６と、フレームメモリ１３６に接続され、フレームメモリ１３６に記憶された連続した２個の画像の各画素の変位を計算するための動きベクトル探索モジュール１４８と、動きベクトル探索モジュール１４８によって推定された動きベクトルを利用して、フレームメモリ１３６に記憶されたカメラ６０からの画像フレームシーケンスをエンコードし、要求に応じて、エンコードされた画像フレームシーケンスをデコードし、デコードされた画像フレームシーケンスをモニタ７４に供給するためのエンコーダ／デコーダ１５２と、エンコーダ／デコーダ１５２によってエンコードされたビデオデータを記憶する記憶部１５０と、フレームメモリ１３６、動きベクトル探索モジュール１４８、エンコーダ／デコーダ１５２及び記憶部１５０の協調した動作を制御するコントローラ１２２と、を含む。記憶部１５０はＨＤＤ９８又はＲＡＭ９６で実現され、エンコーダ／デコーダ１５２はＧＰＵ１０４で実現される。
【００６４】
動きベクトル探索モジュール１４８とコントローラ１２２との機能は、コンピュータ７０で実行されるソフトウェアで実現される。エンコーダ／デコーダ１５２の機能はＣＰＵ９０で実行されるソフトウェアとＧＰＵ１０４との組合わせで実行される。
【００６５】
［動きベクトル探索アルゴリズム］
図６はカメラ６０からの連続した２つのフレームのための動きベクトル探索モジュール１４８を実現する動きベクトル探索アルゴリズムの制御構造を示す。
【００６６】
図６を参照して、動きベクトル探索アルゴリズムは一般に、フレームＮ内の全ての画素について変位推定処理３０２を繰返すステップを含む。さらに、パターンＡのデータの組ＤＡがフレームＮから計算され、パターンＢのデータの組ＤＢがフレームＮ＋１から計算される、と仮定される。
【００６７】
処理３０２は、フレームＮ内の画素についてデータＤＡをサンプリングするステップ３０４と、データの組ＤＡに基づいて画素のベクトルＩａ（式（２３）を参照）を計算するステップ３０６と、フレームＮ＋１の画素の各々について、画素の類似尺度
【００６８】
【数１９】
2009217496.tif 000021
を計算する処理３１０を繰返すステップ３０８と、類似尺度の大域的最小点を探索することによって、フレームＮ＋１内の画素（ｘ＋μ，ｙ＋ν）を選択するステップと、を含む。フレームＮ＋１で選択された画素（ｘ＋μ，ｙ＋ν）はフレームＮ内の画素（ｘ，ｙ）の動きベクトルの終点を与える。
【００６９】
処理３１０は、フレームＮ＋１内の画素についてデータの組ＤＢをサンプリングするステップと、その画素のベクトルＩｂ（式（２４）を参照）を計算するステップと、フレームＮ内の対象となる画素に対する、その画素の上記類似尺度を計算するステップと、対象画素（ｘ，ｙ）の座標に関連づけて、ＲＡＭ９６に上記類似尺度を記憶するステップと、を含む。
【００７０】
［データの組ＤＸを編成するためのアルゴリズム］
図７は、図６のステップ３０４及び３１２で呼出される、フレーム（フレームＮ又はフレームＮ＋１）内の画素についてデータの組ＤＸ（Ｘ＝Ａ及びＢ）を編成するためのコンピュータプログラムの制御構造を示す。図７を参照して、このプログラムは、[１，１]から[ｒ，Ｎ]までのインデックスを付された、ＲＡＭ９６内の２次元のアレイｒａｙ［ｒ，Ｎ］を初期化するステップ４００を含み、ここでｒは円２５２又は２７２内の画素の半径長であり（図４を参照）、Ｎは円形テンプレート２５２又は２７２内で考慮すべき半径の数である。プログラムはさらに、ｄθ、ｎ及びθをそれぞれ２π／Ｎ、１、及び０に設定するステップ４０２を含み、ここでθはｘ軸からの半径の角度をラジアンで表したものであり（図４を参照）、ｎは反復制御変数であり、ｄθは隣接する半径間の角度の差を示す。プログラムはさらに、ｎがＮより大きいか否かにより、ＹＥＳ又はＮＯに分岐するステップ４０４を含む。
【００７１】
プログラムはさらに、ステップ４０４でＮＯに分岐したときに行われ、以下の式
【００７２】
【数２０】
2009217496.tif 000022
に従ってｘｎ及びｙｎを計算するステップ４０６を含み、ここでｘｃ及びｙｃはテンプレートの中心（対象画素）座標である。プログラムはさらに、変数ｘの値をｘｃに設定するステップ４０８と、ｄｘ＝（ｘｎ−ｘｃ）／ｒを計算するステップ４１２と、変数ｋの値を１に設定するステップ４１４と、変数ｋが定数ｒより大きいか否かによってＹＥＳ又はＮＯに分岐するステップとを含む。
【００７３】
プログラムはさらに、ステップ４１６でＹＥＳに分岐したときに行われる、θｎ＋１＝θｎ＋ｄθを計算し、ｎを１だけ増分しさらに制御をステップ４０４に戻すステップ４２６と、ステップ４１６でＮＯに分岐したときに行われる、半径の式ｙ＝ｍｘ＋ｂのｍ及びｂを計算するステップ４１８と、ステップ４１８に続いて、ｙ＝（ｉｎｔ）（ｍｘ＋ｂ＋０．５）によってｙを計算するステップとを含み、ここで“（ｉｎｔ）（Ｘ）”は「Ｘの整数部分」を表す。プログラムはさらに、ステップ４２０に続いて、ｒａｙ（ｋ，ｎ）＝ｉｍｇ（ｙ，（ｉｎｔ）（ｘ＋０．５））によって半径要素ｒａｙ（ｋ，ｎ）を計算するステップ４２２を含み、ここでｉｍｇ（ｙ，ｚ）は「（ｘ，ｙ）での画素値」を意味する。プログラムはさらに、ステップ４２２に続いて、変数ｘ及びｋをそれぞれｄｘ及び１だけ増分し、制御をステップ４１６に戻すステップ４２４を含む。ステップ４１８で行われる計算は、半径の２点の座標が既知であるため、ごく簡単な代数である。
【００７４】
プログラムはさらに、ステップ４０４でＹＥＳに分岐したときに行われる、Ｄｘを式（１２）又は式（１３）で示されたように編成するステップ４２８を含む。
【００７５】
［動作］
図１から図７を参照して、上述の、ビデオエンコーディング４０のための頑健な類似尺度ベースのパターンマッチングシステムは、以下のように動作する。特に図１及び図２を参照して、カメラ６０はビデオ画像フレームのストリームをコンピュータ７０に出力する。ビデオキャプチャボード１０２はストリームを獲得し、フレームを、図３に示されたフレームメモリ１３６として働くＲＡＭ９６に、フレームごとに記憶する。フレームメモリ１３６は、少なくとも２つの、最新のフレームを記憶する。
【００７６】
ＣＰＵ９０は図６及び図７に示されたプログラムを実行し、先行するフレーム中の画素の各々の動きベクトル（変位）を、後続のフレームを参照して推定し、それによって図３に示された動きベクトル探索モジュール１４８の機能を実現する。
【００７７】
先行するフレームの画素の各々について、動きベクトル探索モジュール１４８は現フレーム内に対応の画素を見出す。これら画素の変位が、先行するフレームの画素の推定された動きベクトルである。動きベクトル推定機能は、図６及び図７に示すプログラムを実行するＣＰＵ９０によって実現される。
【００７８】
先行するフレーム（フレームＮ）の画素（ｘ,ｙ）の各々について、ＣＰＵ９０は式（１２）で示されるようにデータの組ＤＡを計算する（ステップ３０４）。その後、ＣＰＵ９０は式（２３）で示されるようにベクトルＩａを計算する（ステップ３０６）。
【００７９】
次に、現フレーム（フレームＮ＋１）内の画素の各々について、ＣＰＵ９０は式（１３）で示されるようにデータの組ＤＢを計算し（ステップ３１２）、式（２４）で示されるようにベクトルＩｂを計算する（ステップ３１４）。
【００８０】
ベクトルＩｂが計算されると、ＣＰＵ９０は式（２５）で示されるように類似尺度
【００８１】
【数２１】
2009217496.tif 000023
を計算し、その類似尺度を、現フレームの現画素のｘ−ｙ座標値と関連づけてＲＡＭ９６に記憶する。
【００８２】
現フレーム（フレームＮ＋１）内の全ての画素について類似尺度が計算されると、ＣＰＵ９０はステップ３１８で記憶された類似尺度の中から大域的最小点を探索する（ステップ３２０）。大域的最小点に関連するｘ−ｙ座標値が、先行するフレーム（フレームＮ）の対象の画素の動きベクトルの終点を与える。
【００８３】
先行するフレーム（フレームＮ）内の全ての画素について動きベクトルが推定されると、ＣＰＵ９０は動きベクトルデータの組をエンコーダ／デコーダ１５２に出力し、これは動きベクトルデータを利用して現画像をエンコードする。
【００８４】
現フレームのエンコードが完了すると、ＣＰＵ９０は先行するフレーム（フレームＮ）を廃棄する。こうして現フレーム（フレームＮ＋１）が先行するフレームとなり、カメラ６０から受取られる新たなフレームが、新たな現フレームとしてＲＡＭ９６に記憶される。
【００８５】
上述の動作が、カメラ６０からのフレームシーケンスの全てのフレームについて繰返され、フレームシーケンスはエンコーダ／デコーダ１５２によってエンコードされる。
【００８６】
上述の実施の形態では、大域的最小点を探索するステップは上記の全ての類似尺度が計算された後でステップ３２０で独立して行われる。この発明は、この実現の形態に限定されない。例えば、大域的最小点は、当業者には明らかであるように、繰返し処理３１０の間に見出すこともできる。
【００８７】
上述の実施の形態では、動きベクトルは先行するフレームの画素の全てについて推定されていた。しかしながら、この発明はそのような実施の形態に限定されない。推定速度が重要である場合は、選択した画素についてのみ動きベクトルを推定してもよい。
【００８８】
上述の実施の形態は動きベクトルの推定に関するものである。しかしながら、この発明はこれに限定されない。この発明は２以上の画像間のいかなるパターンマッチングにも適用可能である。例えば、この発明は、左画像の各画素が右画像の全ての画素と比較される、ステレオ画像のディスパリティ推定に直接適用することができる。
【００８９】
今回開示された実施の形態は単に例示であって、本発明が上記した実施の形態のみに制限されるわけではない。本発明の範囲は、発明の詳細な説明の記載を参酌した上で、特許請求の範囲の各請求項によって示され、そこに記載された文言と均等の意味および範囲内でのすべての変更を含む。
【図面の簡単な説明】
【００９０】
【図１】この発明の一実施の形態に従ったビデオエンコーディングシステム４０のシステム構成要素を示す図である。
【図２】この発明の実施の形態の、コンピュータによって実現された映像処理システム５０のハードウェアブロック図である。
【図３】映像処理システム５０の全体の機能ブロック図である。
【図４】共に半径長ｒの例示パターンＡ及びパターンＢと、これらの間の回転角の例を示す図である。
【図５】半径データサンプリング処理の詳細を示す図である。
【図６】実施の形態で用いられる動きベクトル推定プログラムのフロー図である。
【図７】パターン行列ＤＸを編成するための詳細なフロー図である。
【符号の説明】
【００９１】
４０  ビデオエンコーディングシステム
５０  映像処理システム
６０  カメラ
７０  コンピュータ
７４  モニタ
９０  ＣＰＵ
９６  ＲＡＭ
１０２  ビデオキャプチャボード
１０４  ＧＰＵ
１２２  コントローラ
１３６  フレームメモリ
１４８  動きベクトル探索モジュール
１５０  記憶部
１５２  エンコーダ／デコーダ
【図１】
2009217496.tif 000024
【図２】
2009217496.tif 000025
【図３】
2009217496.tif 000026
【図４】
2009217496.tif 000027
【図５】
2009217496.tif 000028
【図６】
2009217496.tif 000029
【図７】
2009217496.tif 000030
【外国語明細書】
2009217496000001.pdf
2009217496000002.pdf
2009217496000003.pdf
2009217496000004.pdf