統計的テンプレートマッチングによる高速な物体検出方法
画像中の物体の検出方法は、テンプレートを画像の領域と比較すること、及び、類似度を求めることを含み、類似度は統計測度を用いて求められる。テンプレートは、物体の各部分及びそれらの空間的関係に対応するいくつかの領域を含む。テンプレート全体のピクセルの分散は、全ての個々の領域におけるピクセルの分散との関係により設定され、類似度が得られる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テンプレートマッチングを用いて画像中の物体を検出又は位置特定する方法及び装置に関する。
【０００２】
物体検出は、コンピュータビジョンにおいて、ビデオ監視、視覚に基づく制御、人間コンピュータインタフェース、医用画像、拡張現実(augmented reality)及びロボット工学等の広範な用途を有する。また、物体検出は、３Ｄ再構成及び３Ｄ表現のようなより高レベルの視覚タスクへの入力となる。物体検出はまた、コンテンツベースのインデックス付け及び検索等のビデオデータベース用途に関して重要な役割を果たす。
【０００３】
ロバストで正確で高性能な手法が今日においても大きな課題である。この問題の難易度は、関心物体(object of interest)がどう定義されるかに大きく依存する。特定の物体を記述するテンプレートがあれば、物体検出は、テンプレートと解析中の画像との間で特徴を照合するプロセスとなる。完全一致による物体検出は一般に計算量が多く、照合の品質及び速度は物体テンプレートにより提供される細部及び正確さに依存する。
【０００４】
テンプレートマッチングにはいくつかの主要な技法が用いられてきた。
１）画像減算(image subtraction)。この技法では、テンプレートと画像中の様々な位置との間の距離関数を最小化することによってテンプレートの位置が求められる［Nicu Sebe、Michael S. Lew、及びDionysius P. Hujismans, H.著（2000）「Toward Improved Ranking Metrics」（IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1132-1142, 22(10), 2000）］。画像減算法に必要な計算時間は、後述する相関に基づく技法よりも短いが、画像減算法は、テンプレートとこのテンプレートを含む画像との間で画像強度及び視角等の撮影条件が同じという制限された環境において良好に機能する。
２）相関。相関によるマッチングは、テンプレートと画像との間の正規化された相互相関ピークの位置を利用して最良一致を位置特定する［Chung, KL.著（2002）「Fast Stereo Matching Using Rectangular Subregioning and 3D Maximum-Surface Techniques」（International Journal of Computer Vision. vol. 47, no. 1/2/3, pp. 99-117, May 2002）］。この技法は一般に、画像中の雑音及び照明効果に強いが、テンプレート全体にわたる加算により生じる計算量が多いという欠点がある。点相関により計算量を、加算のために注意深く選択された点の小さな集合に低減することができる。
３）可変テンプレートマッチング。可変テンプレートマッチング手法は、剛性変形及び非剛性変形により物体が変化する場合により適している［A.K. Jain、Y. Zhong、S. Lakshmanan著「Object Matching Using Deformable Templates」（IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 18, Issue 3 (March 1996), 267-278）］。これらの変化は、物体自体の変形又は単にカメラに対する異なる物体姿勢により生じる場合がある。ほとんどのビデオ中の物体は可変性であるため、可変モデルは追跡タスクにおいてより魅力的である。この手法では、テンプレートは、物体形状の特徴的な輪郭／エッジを記述するビットマップとして表される。原型となる輪郭の確率的変形が適用されて、入力画像中の顕著なエッジに合わせてテンプレートが変形される。テンプレートの形状を変化させる変形パラメータを有する目的関数(objective function)が、このような変換のコストを反映して定式化される。この目的関数は、変形パラメータを物体に最も良く一致するように繰り返し更新することによって最小化される。
４）フーリエ法。計算速度の加速が必要であるか、画像が様々な条件下で取得されたか、又は画像が周波数依存性雑音により破損している場合、相関のような方法よりもフーリエ法［Y. Keller、A. Averbuch著「Unified Approach To FFT-Based Image Registration」（IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2002, Orlando, USA, May 2002）］が好ましい。フーリエ法は、周波数領域における画像のフーリエ表現を利用する。位相相関法はフーリエシフトの定理に基づき、当初は平行移動画像の位置合わせのために提案された。位相相関法は、テンプレート及び画像の相互電力スペクトルを計算し、その逆スペクトルのピークの位置を探す。
【０００５】
本発明が取り組む課題は、低品質画像及び雑然とした背景のような複雑な環境におけるロバストな物体検出である。
【０００６】
本発明が取り組む別の課題は、物体検出に用いられるテンプレートマッチング方法のリアルタイムでの実施である。よく知られたテンプレートマッチング方法は、以下のようないくつかの欠点を有する。
（ａ）相互相関法はロバストであるが計算量が多い。Ｍ×Ｎサイズのテンプレートの場合、画像ピクセル毎にＯ（ＭＮ）回の演算、通常は乗算を必要とし、リアルタイムでの実行には適さない場合がある。
（ｂ）高速フーリエ変換に基づく位相相関は高速であるが、画像サイズに匹敵するテンプレートサイズのみで安定して機能する。通常の用途では、関心物体が占めるのは画像サイズの１％未満である可能性があり、位相相関法の出力ははっきりしないものとなる。物体の大まかな位置がアプリオリに分かっている場合、例えば、画像シーケンスにおいて物体が追跡される場合、関心領域のサイズを縮小することができる。この場合、位相相関が適用可能であるが、２つの新たな問題が生じる：（１）領域追跡を初期化するために最初のフレーム中の物体を検出する別の方法が必要になる。（２）このアプリケーションは、物体の位置に関するアプリオリ情報がない静止画では機能しない。
【０００７】
既存の方法に伴う問題を克服するために、新たなテンプレートマッチング方法が提案される。本方法は、統計的仮説試験に基づき、その性能はテンプレートサイズに依存せず、テンプレートの複雑さのみに依存する。
【０００８】
リアルタイム実施の要件はロバスト性の要件と矛盾することが多い。本方法の実施は以下に対してロバストである：
１）スケール変更；本方法は、画像が（０．５，２）の範囲の倍率でスケーリングされても同様の結果を与える。
２）局所的な画像ワーピング；本方法は小さな幾何学的障害の影響を受けない。
３）非線形の強度変化；本方法は高圧縮画像に対して機能することができる。１００分の１又は２という低い圧縮品質のＪＰＥＧ画像で行った試験は成功した。
【０００９】
本明細書では、画像がＮ個の座標変数の関数Ｉ（ｘ１，ｘ２，．．．，ｘＮ）であると仮定する。このような定義画像には以下のような様々な場合がある。
Ｎ＝１；これは、例えばあらゆる実信号、２Ｄ画像から抽出されるピクセルプロファイル又は画像から導出されるあらゆる整関数（ヒストグラム、側方向投影）であり得る１Ｄ画像又は１Ｄ信号である。
Ｎ＝２；これは、未処理形態又は前処理済み形態の通常の２Ｄ画像Ｉ（ｘ，ｙ）である。前処理は、フィルタリング、分割、エッジ又は特徴抽出等の任意の画像処理操作を含み得る。
Ｎ＝３；これは、未処理形態又は前処理済み形態の体積画像(volumetric image)（ボクセル画像、画像スタックとして編成された画像シーケンス又はビデオ）である。
任意のＮ；応用形態はデータ表現により高い次元を用いることができ、例えば、時間的に変化する体積画像の場合にＮ＝４を用いることができる。
【００１０】
本発明の態様は、添付の特許請求の範囲に記載される。提案する物体検出方法のいくつかの態様を以下に記載する。
【００１１】
関心物体又はその一部の記述は、領域の集合Ｔ０＝Ｔ１∪．．．∪ＴＭにより行う。この記述をこの提案ではトポロジカルテンプレート又は単にテンプレートと呼ぶ。このテンプレートは、物体のトポロジー（その各部分の空間的関係）のみを記述し、その放射分析的（色、強度等の放射線に関連する）特性は記述しない。各領域Ｔｉはいくつかの非連結領域から成る可能性がある。
【００１２】
提案するテンプレートマッチング方法は、ピクセル群の統計的特徴（平均及び分散）のみを解析に用いるため、統計的テンプレートマッチングと呼ばれる。マッチングプロセスにおいて、テンプレートと画像領域との間の類似度は統計的仮説試験に基づく。各ピクセルｘ及びその近傍Ｒ（ｘ）に関して、２つの仮説を検討する：
Ｈ０：Ｒ（ｘ）はランダムである。
Ｈ１：Ｒ（ｘ）はテンプレートに類似している。
【００１３】
Ｈ０又はＨ１を受け入れる決定規則は、（テンプレート領域により画定される）ピクセル群の特徴が互いに統計的に異なるか、及び、導出される類似度が信号対雑音比に近いかという試験に基づく。これは次のように計算される：
【００１４】
【数１】
【００１５】
ここで、σ２（Ｑ）は領域Ｑにおける画像値の分散であり、｜Ｑ｜は領域Ｑ内のピクセル数を示す。
【００１６】
統計的テンプレートマッチングは、積分画像と呼ばれるよく知られた技法を用いることによって、リアルタイム性能を達成するように容易に適用させることができる。この修正では、各テンプレート領域Ｔｉは矩形の集合から成る。この場合、２Ｄ画像に関して、（１）の各分散値は８ｋ回のメモリ参照により計算することができ、ここで、ｋは矩形の数である。従来のやり方でσ２（Ｑ）を計算すると｜Ｑ｜回のメモリ参照が必要となる。
【００１７】
統計的テンプレートマッチング出力の以下の解釈は、物体検出に用いることができる。ピクセル毎に、マッチングは類似度Ｓ及び一組の統計的特徴σ２（Ｔ０），．．．，σ２（ＴＮ）、ｍ（Ｔ０），．．．，ｍ（ＴＮ）を生成する。ここで、ｍ（Ｔｉ）は、σ２（Ｔｉ）の計算に用いられる領域平均である。類似度値は類似度マップを形成し、高い値は物体の有望な位置に対応する。したがって、類似度と閾値との比較は物体／非物体位置分類器として適用される。物体検出アルゴリズムを完成させるために、以下の手順を適用することができる：
１）非最大値の抑制により、類似度マップの極大値(local maxima)及び物体中心の整数座標を得る。
２）多項式曲面を類似度マップの極大値の近傍に当てはめて、物体のサブピクセル位置を得る。
３）統計値σ２（Ｔ０），．．．，σ２（ＴＮ）、ｍ（Ｔ０），．．．，ｍ（ＴＮ）の用途依存解析は、誤報数の削減に役立つ。物体領域の放射分析的特性が事前に分かっている（例えば、領域の一部が他の領域よりも暗いことが分かっている）場合、ｍ（Ｔｉ）＜ｍ（Ｔｊ）のような追加条件により不要な構成を拒絶する。
【００１８】
提案する方法のいくつかの拡張を以下に記載する。
１）多解像度手法。本方法は、画像のいくつかの解像度を作成する場合（いわゆる画像ピラミッド）に、粗密の枠組みで適用することができ、処理は最も粗いレベルから始まり、検出結果はより細かい解像度で精緻化される。この場合、テンプレートを多解像度にしたもの（テンプレートピラミッド）を作成する。この処理は、最も粗い画像解像度における最も粗いテンプレートのマッチングから始まる。全ての考えられる物体位置を粗い類似度マップから抽出した後、処理は、関心領域（ＲＯＩ）内でのみより細かい解像度で行われる。
２）物体追跡。このような用途では、方法は、シーケンスの最初の画像においてＲＯＩを初期化し、次の画像におけるその位置を予測しようとすることによって、統計的テンプレートマッチングの探索エリアを縮小する。いくつかの連続フレームから得られた結果の統計的フィルタリングを用いて、物体の存在に関する決定を行うことができる。
３）テンプレートの修正。多解像度の枠組み又は物体追跡の枠組みでは、次のステップにおける物体検出を改善するために、テンプレートを現在の検出結果の解析に基づいて調整することができる。例えば、いくつかのテンプレート領域の統合又は除外が類似度を高める場合、そのように統合又は除外することができる。また、テンプレートの全体のサイズを類似度マップのピークの幅に従って調整することができる。
４）複数のテンプレート。この状況は、いくつかのテンプレートが或る物体を表し得る場合に可能である。統計的テンプレートマッチングを適用した結果として複数の類似度マップが得られ、これらが単一の類似度マップに結合されてから、物体位置が抽出され得る。最も単純な結合方法はピクセル毎の乗算である。
【００１９】
本発明の実施形態を添付図面に関して説明する。
【００２０】
２Ｄの場合の提案する方法の実施を以下に記載する。
【００２１】
本方法のブロック図を図１に示す。まず、以下でより詳細に説明するように、関心物体を含む可能性のある入力画像を用いて積分画像を計算する（ブロック１．１）。次に、画像をピクセル毎にスキャンして取り込み（１．２）、テンプレートの中心を現ピクセルに置く（１．３）。テンプレートによって覆われた画像領域に関して一組の統計値及び類似度を計算する（１．４）。次に、計算された統計値を用いてアプリオリ情報を調べる。特定の条件を満たさない場合、現ピクセルは物体の中心ではあり得ないため、最低値の類似度を割り当てる（１．５）。テンプレートを移動させてその中心を画像中の各ピクセルに順番に置くことによって全ての類似度値を計算して類似度マップが得られたら、物体の考えられる位置を抽出するためにこのマップを後処理する（１．６）。そして最後に、検出された物体の類似度値を統計的有意水準又は用途により定義される閾値と比較する（１．７）。
【００２２】
提案する方法では、関心物体又はその一部を、領域の集合Ｔ０＝Ｔ１∪．．．∪ＴＭから成るテンプレートにより記述する。このテンプレートは、物体のトポロジー（その各部分の空間的関係）のみを記述し、その放射分析的特性は記述しない。６つの領域を有するトポロジカルテンプレートの一例を図２ａに示す。このテンプレートは、いずれかのピクセルに位置するテンプレートによって覆われる局所画像領域をどのように解釈するかを決める。図２ｂに示すようにテンプレートの中心をピクセル（ｘ０，ｙ０）に置くと、Ｍ＋１個の画像領域（図２のＴ０．．．Ｔ６の領域）において局所統計値が計算される。これらの統計値は、画像とテンプレートとの間の類似度の計算に用いられる。
【００２３】
物体のテンプレートを作成する際の一般的な指針は以下の通りである。
ａ）領域数Ｍは弁別的な物体の部分の数に対応していなければならない。
ｂ）いくつかの物体部分の放射分析的特性が類似している場合、それらはテンプレートの１つの領域に含まれなければならない。
ｃ）物体が非常に変わりやすい領域（高周波のテクスチャ、エッジ）を含む場合、それらの領域は、方法の性能をより良くするためにテンプレートから除外することができる。
ｄ）領域のサイズ又は形状の仮定は行わない。各領域Ｔｉはいくつかの非連結領域から成る可能性がある。各領域は穴（使用されない領域）を含み得る。
ｅ）本方法のより良い性能は、領域の形状を単純化することによって達成することができる。したがって、各領域Ｔｉが矩形の集合として表される場合、処理時間は最短となる。
ｆ）最良性能（リアルタイム用途に適している）は、以下の場合に達成することができる。すなわち、テンプレート形状（領域Ｔ０）が矩形であり、全ての他の領域Ｔｉが矩形の集合から成り、テンプレートに穴（使用されない領域）がない場合である。
【００２４】
顔検出タスク用のテンプレートの例を図３に示す。これらのテンプレートは、目領域が通常は周囲の肌領域よりも暗いという観察（図３ａ）に基づいて作成された。各テンプレートは、黒のエリア及び白のエリアにより画定される２つの領域から成る。なお、１つのテンプレート領域（黒で示す）は２つの非連結領域から成る。図３ｃのテンプレートは、暗い値から明るい値への強度遷移エリアを除外するための穴（灰色で示す）も含む。図３ｄのテンプレートは図３ｂを簡略化したもので、リアルタイムでの実施に適している。
【００２５】
テンプレートが異なるサイズの矩形の集合として表される場合、これらの矩形内の統計的特徴（平均及び分散）の高速な計算のために特別な画像前処理を適用することができる（図１、ブロック１．１）。画像を積分表現に変換することにより、このような特徴は、後述のように矩形の角の座標の４回のピクセル参照のみで高速に計算できるようになる。
【００２６】
本発明では積分画像Ｓｕｍ（ｘ，ｙ）及びＳｕｍＱ（ｘ，ｙ）を以下のように定義する。
【００２７】
【数２】
【００２８】
ここで、Ｉ（ｘ，ｙ）は原画像であり、ｘ，ｙ＜０の場合にＩ（ｘ，ｙ）＝０である。
【００２９】
テンプレートと画像領域との間の類似度は統計的仮説試験に基づく。ピクセル（ｘ０，ｙ０）及びその近傍Ｒ（ｘ０，ｙ０）毎に、２つの仮説を検討する：
Ｈ０：Ｒ（ｘ０，ｙ０）はランダムである。
Ｈ１：Ｒ（ｘ０，ｙ０）はテンプレートに類似している。
【００３０】
Ｈ０又はＨ１を受け入れる決定規則は、Ｍ個のピクセル群の平均が互いに統計的に異なるかどうかという試験に基づく。これらのＭ個の群はテンプレートにより画定され、その中心はピクセル（ｘ０，ｙ０）に位置する。
【００３１】
まず、２つの領域の場合：Ｔ０＝Ｔ１∪Ｔ２を検討する。よく知られた統計的ｔ検定(t-test)を２つのピクセル群に適用すると以下の類似度が得られる（いくつかの等価変換は省く）。
【００３２】
【数３】
【００３３】
この式から定数を除去すると、（１）の形の類似度が得られる。
【００３４】
テンプレートが３つ以上の領域から成る場合、別の統計的技法を用いて類似度を得る。この技法は分散分析(Analysis of Variances)（ＡＮＯＶＡ）と呼ばれ、数学的にはｔ検定と等価であるが、群数が２つよりも多い場合にのみ用いられる。
【００３５】
群間分散及び群内分散をＱ１（Ｔ１，．．．，ＴＭ）及びＱ２（Ｔ１，．．．，ＴＭ）とする。これらの分散は以下のように計算される。
【００３６】
【数４】
【００３７】
これらの分散は以下のように連結される。
【００３８】
【数５】
【００３９】
本発明では、フィッシャー基準を類似度として用いる（（５）、（６）、（７）に続く等価変換は省く）。
【００４０】
【数６】
【００４１】
この式から定数を除去すると、（１）の形の類似度が得られる。
【００４２】
したがって、点（ｘ０，ｙ０）における統計的テンプレートマッチングの結果は次のように表すことができる。
【００４３】
【数７】
【００４４】
類似度値が計算されたら、画像領域が関心物体に類似していると言えるほどこの値が大きいかどうかという検定を、統計的閾値処理を用いて行うことができる。このような検定には統計的な有意性の表を用いることができる。有意性の検定には、リスク水準を設定しなければならない。通常、０．０５のリスク水準を用いる。リスク水準及び自由度数が与えられると、ｔ値（（４）から）又はＦ値（（８）から）を標準的な有意性の表から得られる閾値と比較して、類似度値が有意であるほど十分に大きいかどうかを判定することができる。
【００４５】
上記のように、積分画像の使用により構成の速度を高めることができる。積分画像を用いると、任意の矩形領域Ｒの｜Ｒ｜σ２（Ｒ）の計算に必要なピクセル参照は２＊｜Ｒ｜回ではなく２＊４回となる。
【００４６】
【数８】
【００４７】
ここで、最後の等式は定義であり、（ｘ１，ｙ１）、（ｘ２，ｙ２）は矩形Ｒの左上及び右下の点の座標である。
【００４８】
矩形の集合から成る領域：Ｔｉ＝Ｒ１∪Ｒ２∪．．．ＲＫｉの場合、｜Ｔｉ｜σ２（Ｔｉ）の計算は同様である。
【００４９】
【数９】
【００５０】
上記の式を用いて、テンプレートと画像との間の類似度の計算は、テンプレートサイズに依存せず、テンプレートの複雑度（その中の矩形の数）に依存する。
【００５１】
（５）〜（７）を用いてさらなる最適化を行う。ここから、ｍ（ＴＭ）、σ２（ＴＭ）を計算する必要がないことは明らかである。これは、これらの値がｍ（Ｔ０），．．，ｍ（ＴＭ−１）、σ２（Ｔ０），．．．，σ２（ＴＭ−１）から導出できるためである。この最適化により、（ａ）少数の領域のみを用いる（Ｍ＝２，３）場合、又は（ｂ）領域ＴＭが非常に多数の矩形から成る場合に性能を大幅に高めることができる。
【００５２】
図４は、提案する方法による顔検出の例を示す。図４ｄに示すテンプレートを統計的テンプレートマッチングに用いた。図４の上の行は顔画像を類似度の最大値の位置と共に示す。下の行は、（９）を用いて計算した類似度マップの対応するフラグメントを示す。この例示には、ＡＴ＆Ｔ顔データベースからの画像を用いた。これらの画像は、AT&T Laboratories, Cambridgeのウェブサイトhttp://www.uk.research.att.com/facedatabase.htmlから入手可能である。
【００５３】
本提案によるテンプレートマッチング方法は、本方法を例示するために用いた顔検出タスクに特定的なものではない。本方法は、物体モデルを事前に定義及び簡略化することができる物体検出を扱うあらゆる用途に用いることができる。この方法は特に、バイモーダルの場合（明るい背景の中の暗い物体又は暗い背景の中の明るい物体）、又は物体モデルを一組の矩形から成るように簡略化することができる場合によく機能する。モデルを矩形から構成することができる場合、本方法のリアルタイム性能が達成されるが、これは相関に基づく技法には必ずしも当てはまらない。
【００５４】
図５は、顔特徴の検出への本方法の適用を示す。上の行は水平方向特徴（目、鼻腔、口）の検出を示す。下の行は垂直方向特徴（鼻）の検出を示す。左の列は検出結果を示す。中央の列はテンプレートを示し、右の列は類似度マップを示す。
【００５５】
基準マーク検出の典型的な例は、衛星画像の自動的な内部オリエンテーションであり、この場合、画像の歪みを補正するために、カメラにより作成された基準マークを検出しなければならない（図６）。図６において、（ａ）は衛星画像中の基準マーク（十字）を示し、（ｂ）はテンプレート（ｃ）〜（ｇ）を用いた統計的テンプレートマッチングにより得られる結合された類似度マップを示す。
【００５６】
提案するテンプレートマッチング方法の別の用途としては、路面標示の検出が考えられる。道路画像を直交ビューに変換すると、標示ははっきりした物体となり、テンプレートマッチングにより検出することができる。図７は、（ａ）道路画像−車内からのビュー、（ｂ）直交変換後の道路の「航空」ビュー、（ｃ）標示部分の始まり、終わり及び中央部を検出するテンプレートの例を示す。
【００５７】
図８は、画像透かし問題への提案する方法の適用を示す。ここでは、均一な領域から成る透かしを用いる。この例の透かしは画像の最下位ビットに埋め込まれるが（図８ａ）、他の埋め込み法も用いることができる。透かし画像の抽出（図８ｂ）後、透かしに符号化された情報を読み取る方法が必要となる。このような読み取りに、提案する統計的テンプレートマッチングを用いることができる。全ての考えられる透かし（その一部を図８ｅに示す）に対してマッチングを行い、考えられる位置及び類似度値を検出する（図８ｃ、図８ｄに２つの例を示す）。最も高い類似度値を生じるテンプレートを透かしと見なす。図８は、（ａ）透かし入り画像、（ｂ）透かし入り画像の最下位ビット、（ｃ）透かしに対応するテンプレート（図（ｅ）の左のテンプレート）を用いる統計的テンプレートマッチングの結果（類似度マップ）、（ｄ）なんらかの任意のテンプレートを用いる統計的テンプレートマッチングの結果（類似度マップ）、（ｅ）透かしを読み取るために用いられるテンプレートの例を示す。
【００５８】
上記の説明では、類似度は値が高いほど類似度が高いことを示すようになっており、極大値が検出される。しかし、使用する類似度に応じて、他の値（より低い値、等）でより近い類似度を示し、極小値を検出するようにしてもよい。高い値、極大値等への言及はそれに応じて解釈すべきである。
【００５９】
本明細書において、統計的という用語は、色、強度等の何らかの品質の分布に関連することを意味する。
【００６０】
本明細書において、「画像」という用語は、画像単位を記述するために用いられる。この画像単位は、解像度の変更、アップサンプリング、ダウンサンプリング等の処理の後のものを含み、又は積分画像と関連するものを含む。また、この用語は、フレーム、フィールド、ピクチャ等の他の同様の用語、又は画像、フレーム等のサブユニット若しくは領域にも適用される。ピクセル及びブロック又はピクセル群という用語は、適宜互換可能に用いられ得る。本明細書において、画像という用語は、文脈から明らかな場合を除いて、画像全体又は画像の一領域を意味する。同様に、画像の一領域は画像全体を意味し得る。画像は、フレーム又はフィールドを含み、静止画、フィルム若しくはビデオ等の画像シーケンス中の１つの画像、若しくは関連画像群中の１つの画像に関連する。
【００６１】
画像はグレースケール画像又はカラー画像であってもよく、又は別のタイプのマルチスペクトル画像、例えば、ＩＲ、ＵＶ若しくは他の電磁画像、若しくは音響画像等であってもよい。
【００６２】
本発明は、例えばコンピュータシステムにおいて適切なソフトウェア及び／又はハードウェアの変更を行って実施することができる。例えば、本発明は、プロセッサ又は制御装置等の制御手段又は処理手段、メモリ、磁気記憶装置、ＣＤ、ＤＶＤ等といった画像記憶手段を含むデータ記憶手段、ディスプレイ若しくはモニタ又はプリンタ等のデータ出力手段、キーボード等のデータ入力手段、及びスキャナ等の画像入力手段、又はこのような構成要素の任意の組み合わせを追加構成要素と共に有する、コンピュータ等を用いて実施することができる。本発明の態様は、ソフトウェア形態及び／又はハードウェア形態で、又は特定用途向け装置において提供するか、又はマイクロチップ等の特定用途向けモジュールを提供することができる。本発明の一実施形態による装置内のシステムの構成要素は、例えばインターネットを通じて他の構成要素と離れた場所に設けてもよい。
【図面の簡単な説明】
【００６３】
【図１】本発明の一実施形態の方法のフロー図である。
【図２】図２ａはテンプレートの一例である。図２ｂは本発明の一実施形態の方法のための、画像内に位置する図２ａのテンプレートを示す。
【図３】図３ａは関心物体としての画像領域である。図３ｂ〜図３ｄは図３ａの関心物体に対応するテンプレートの例である。
【図４】顔の画像の例と、対応する統計的テンプレートマッチングを示すグラフとを含む。
【図５】検出結果を含む顔の画像、顔特徴検出テンプレート、及び類似度マップを示す。
【図６】図６ａは基準マークを有する衛星画像を示す。図６ｂは図６ａに対応する類似度マップを示す。図６ｃは図６ａに用いるテンプレートを示す。
【図７】図７ａは道路画像を示す。図７ｂは直交変換後の図７ａの画像を示す。図７ｃは路面標示を検出するテンプレートを示す。
【図８】図８ａは透かし画像を示す。図８ｂは図８ａの画像の最下位ビットを示す。図８ｃおよび図８ｄは統計的テンプレートマッチングの結果を示すグラフである。図８ｅは図８ａの画像用のテンプレートを示す。
【技術分野】
【０００１】
本発明は、テンプレートマッチングを用いて画像中の物体を検出又は位置特定する方法及び装置に関する。
【０００２】
物体検出は、コンピュータビジョンにおいて、ビデオ監視、視覚に基づく制御、人間コンピュータインタフェース、医用画像、拡張現実(augmented reality)及びロボット工学等の広範な用途を有する。また、物体検出は、３Ｄ再構成及び３Ｄ表現のようなより高レベルの視覚タスクへの入力となる。物体検出はまた、コンテンツベースのインデックス付け及び検索等のビデオデータベース用途に関して重要な役割を果たす。
【０００３】
ロバストで正確で高性能な手法が今日においても大きな課題である。この問題の難易度は、関心物体(object of interest)がどう定義されるかに大きく依存する。特定の物体を記述するテンプレートがあれば、物体検出は、テンプレートと解析中の画像との間で特徴を照合するプロセスとなる。完全一致による物体検出は一般に計算量が多く、照合の品質及び速度は物体テンプレートにより提供される細部及び正確さに依存する。
【０００４】
テンプレートマッチングにはいくつかの主要な技法が用いられてきた。
１）画像減算(image subtraction)。この技法では、テンプレートと画像中の様々な位置との間の距離関数を最小化することによってテンプレートの位置が求められる［Nicu Sebe、Michael S. Lew、及びDionysius P. Hujismans, H.著（2000）「Toward Improved Ranking Metrics」（IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1132-1142, 22(10), 2000）］。画像減算法に必要な計算時間は、後述する相関に基づく技法よりも短いが、画像減算法は、テンプレートとこのテンプレートを含む画像との間で画像強度及び視角等の撮影条件が同じという制限された環境において良好に機能する。
２）相関。相関によるマッチングは、テンプレートと画像との間の正規化された相互相関ピークの位置を利用して最良一致を位置特定する［Chung, KL.著（2002）「Fast Stereo Matching Using Rectangular Subregioning and 3D Maximum-Surface Techniques」（International Journal of Computer Vision. vol. 47, no. 1/2/3, pp. 99-117, May 2002）］。この技法は一般に、画像中の雑音及び照明効果に強いが、テンプレート全体にわたる加算により生じる計算量が多いという欠点がある。点相関により計算量を、加算のために注意深く選択された点の小さな集合に低減することができる。
３）可変テンプレートマッチング。可変テンプレートマッチング手法は、剛性変形及び非剛性変形により物体が変化する場合により適している［A.K. Jain、Y. Zhong、S. Lakshmanan著「Object Matching Using Deformable Templates」（IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 18, Issue 3 (March 1996), 267-278）］。これらの変化は、物体自体の変形又は単にカメラに対する異なる物体姿勢により生じる場合がある。ほとんどのビデオ中の物体は可変性であるため、可変モデルは追跡タスクにおいてより魅力的である。この手法では、テンプレートは、物体形状の特徴的な輪郭／エッジを記述するビットマップとして表される。原型となる輪郭の確率的変形が適用されて、入力画像中の顕著なエッジに合わせてテンプレートが変形される。テンプレートの形状を変化させる変形パラメータを有する目的関数(objective function)が、このような変換のコストを反映して定式化される。この目的関数は、変形パラメータを物体に最も良く一致するように繰り返し更新することによって最小化される。
４）フーリエ法。計算速度の加速が必要であるか、画像が様々な条件下で取得されたか、又は画像が周波数依存性雑音により破損している場合、相関のような方法よりもフーリエ法［Y. Keller、A. Averbuch著「Unified Approach To FFT-Based Image Registration」（IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2002, Orlando, USA, May 2002）］が好ましい。フーリエ法は、周波数領域における画像のフーリエ表現を利用する。位相相関法はフーリエシフトの定理に基づき、当初は平行移動画像の位置合わせのために提案された。位相相関法は、テンプレート及び画像の相互電力スペクトルを計算し、その逆スペクトルのピークの位置を探す。
【０００５】
本発明が取り組む課題は、低品質画像及び雑然とした背景のような複雑な環境におけるロバストな物体検出である。
【０００６】
本発明が取り組む別の課題は、物体検出に用いられるテンプレートマッチング方法のリアルタイムでの実施である。よく知られたテンプレートマッチング方法は、以下のようないくつかの欠点を有する。
（ａ）相互相関法はロバストであるが計算量が多い。Ｍ×Ｎサイズのテンプレートの場合、画像ピクセル毎にＯ（ＭＮ）回の演算、通常は乗算を必要とし、リアルタイムでの実行には適さない場合がある。
（ｂ）高速フーリエ変換に基づく位相相関は高速であるが、画像サイズに匹敵するテンプレートサイズのみで安定して機能する。通常の用途では、関心物体が占めるのは画像サイズの１％未満である可能性があり、位相相関法の出力ははっきりしないものとなる。物体の大まかな位置がアプリオリに分かっている場合、例えば、画像シーケンスにおいて物体が追跡される場合、関心領域のサイズを縮小することができる。この場合、位相相関が適用可能であるが、２つの新たな問題が生じる：（１）領域追跡を初期化するために最初のフレーム中の物体を検出する別の方法が必要になる。（２）このアプリケーションは、物体の位置に関するアプリオリ情報がない静止画では機能しない。
【０００７】
既存の方法に伴う問題を克服するために、新たなテンプレートマッチング方法が提案される。本方法は、統計的仮説試験に基づき、その性能はテンプレートサイズに依存せず、テンプレートの複雑さのみに依存する。
【０００８】
リアルタイム実施の要件はロバスト性の要件と矛盾することが多い。本方法の実施は以下に対してロバストである：
１）スケール変更；本方法は、画像が（０．５，２）の範囲の倍率でスケーリングされても同様の結果を与える。
２）局所的な画像ワーピング；本方法は小さな幾何学的障害の影響を受けない。
３）非線形の強度変化；本方法は高圧縮画像に対して機能することができる。１００分の１又は２という低い圧縮品質のＪＰＥＧ画像で行った試験は成功した。
【０００９】
本明細書では、画像がＮ個の座標変数の関数Ｉ（ｘ１，ｘ２，．．．，ｘＮ）であると仮定する。このような定義画像には以下のような様々な場合がある。
Ｎ＝１；これは、例えばあらゆる実信号、２Ｄ画像から抽出されるピクセルプロファイル又は画像から導出されるあらゆる整関数（ヒストグラム、側方向投影）であり得る１Ｄ画像又は１Ｄ信号である。
Ｎ＝２；これは、未処理形態又は前処理済み形態の通常の２Ｄ画像Ｉ（ｘ，ｙ）である。前処理は、フィルタリング、分割、エッジ又は特徴抽出等の任意の画像処理操作を含み得る。
Ｎ＝３；これは、未処理形態又は前処理済み形態の体積画像(volumetric image)（ボクセル画像、画像スタックとして編成された画像シーケンス又はビデオ）である。
任意のＮ；応用形態はデータ表現により高い次元を用いることができ、例えば、時間的に変化する体積画像の場合にＮ＝４を用いることができる。
【００１０】
本発明の態様は、添付の特許請求の範囲に記載される。提案する物体検出方法のいくつかの態様を以下に記載する。
【００１１】
関心物体又はその一部の記述は、領域の集合Ｔ０＝Ｔ１∪．．．∪ＴＭにより行う。この記述をこの提案ではトポロジカルテンプレート又は単にテンプレートと呼ぶ。このテンプレートは、物体のトポロジー（その各部分の空間的関係）のみを記述し、その放射分析的（色、強度等の放射線に関連する）特性は記述しない。各領域Ｔｉはいくつかの非連結領域から成る可能性がある。
【００１２】
提案するテンプレートマッチング方法は、ピクセル群の統計的特徴（平均及び分散）のみを解析に用いるため、統計的テンプレートマッチングと呼ばれる。マッチングプロセスにおいて、テンプレートと画像領域との間の類似度は統計的仮説試験に基づく。各ピクセルｘ及びその近傍Ｒ（ｘ）に関して、２つの仮説を検討する：
Ｈ０：Ｒ（ｘ）はランダムである。
Ｈ１：Ｒ（ｘ）はテンプレートに類似している。
【００１３】
Ｈ０又はＨ１を受け入れる決定規則は、（テンプレート領域により画定される）ピクセル群の特徴が互いに統計的に異なるか、及び、導出される類似度が信号対雑音比に近いかという試験に基づく。これは次のように計算される：
【００１４】
【数１】
【００１５】
ここで、σ２（Ｑ）は領域Ｑにおける画像値の分散であり、｜Ｑ｜は領域Ｑ内のピクセル数を示す。
【００１６】
統計的テンプレートマッチングは、積分画像と呼ばれるよく知られた技法を用いることによって、リアルタイム性能を達成するように容易に適用させることができる。この修正では、各テンプレート領域Ｔｉは矩形の集合から成る。この場合、２Ｄ画像に関して、（１）の各分散値は８ｋ回のメモリ参照により計算することができ、ここで、ｋは矩形の数である。従来のやり方でσ２（Ｑ）を計算すると｜Ｑ｜回のメモリ参照が必要となる。
【００１７】
統計的テンプレートマッチング出力の以下の解釈は、物体検出に用いることができる。ピクセル毎に、マッチングは類似度Ｓ及び一組の統計的特徴σ２（Ｔ０），．．．，σ２（ＴＮ）、ｍ（Ｔ０），．．．，ｍ（ＴＮ）を生成する。ここで、ｍ（Ｔｉ）は、σ２（Ｔｉ）の計算に用いられる領域平均である。類似度値は類似度マップを形成し、高い値は物体の有望な位置に対応する。したがって、類似度と閾値との比較は物体／非物体位置分類器として適用される。物体検出アルゴリズムを完成させるために、以下の手順を適用することができる：
１）非最大値の抑制により、類似度マップの極大値(local maxima)及び物体中心の整数座標を得る。
２）多項式曲面を類似度マップの極大値の近傍に当てはめて、物体のサブピクセル位置を得る。
３）統計値σ２（Ｔ０），．．．，σ２（ＴＮ）、ｍ（Ｔ０），．．．，ｍ（ＴＮ）の用途依存解析は、誤報数の削減に役立つ。物体領域の放射分析的特性が事前に分かっている（例えば、領域の一部が他の領域よりも暗いことが分かっている）場合、ｍ（Ｔｉ）＜ｍ（Ｔｊ）のような追加条件により不要な構成を拒絶する。
【００１８】
提案する方法のいくつかの拡張を以下に記載する。
１）多解像度手法。本方法は、画像のいくつかの解像度を作成する場合（いわゆる画像ピラミッド）に、粗密の枠組みで適用することができ、処理は最も粗いレベルから始まり、検出結果はより細かい解像度で精緻化される。この場合、テンプレートを多解像度にしたもの（テンプレートピラミッド）を作成する。この処理は、最も粗い画像解像度における最も粗いテンプレートのマッチングから始まる。全ての考えられる物体位置を粗い類似度マップから抽出した後、処理は、関心領域（ＲＯＩ）内でのみより細かい解像度で行われる。
２）物体追跡。このような用途では、方法は、シーケンスの最初の画像においてＲＯＩを初期化し、次の画像におけるその位置を予測しようとすることによって、統計的テンプレートマッチングの探索エリアを縮小する。いくつかの連続フレームから得られた結果の統計的フィルタリングを用いて、物体の存在に関する決定を行うことができる。
３）テンプレートの修正。多解像度の枠組み又は物体追跡の枠組みでは、次のステップにおける物体検出を改善するために、テンプレートを現在の検出結果の解析に基づいて調整することができる。例えば、いくつかのテンプレート領域の統合又は除外が類似度を高める場合、そのように統合又は除外することができる。また、テンプレートの全体のサイズを類似度マップのピークの幅に従って調整することができる。
４）複数のテンプレート。この状況は、いくつかのテンプレートが或る物体を表し得る場合に可能である。統計的テンプレートマッチングを適用した結果として複数の類似度マップが得られ、これらが単一の類似度マップに結合されてから、物体位置が抽出され得る。最も単純な結合方法はピクセル毎の乗算である。
【００１９】
本発明の実施形態を添付図面に関して説明する。
【００２０】
２Ｄの場合の提案する方法の実施を以下に記載する。
【００２１】
本方法のブロック図を図１に示す。まず、以下でより詳細に説明するように、関心物体を含む可能性のある入力画像を用いて積分画像を計算する（ブロック１．１）。次に、画像をピクセル毎にスキャンして取り込み（１．２）、テンプレートの中心を現ピクセルに置く（１．３）。テンプレートによって覆われた画像領域に関して一組の統計値及び類似度を計算する（１．４）。次に、計算された統計値を用いてアプリオリ情報を調べる。特定の条件を満たさない場合、現ピクセルは物体の中心ではあり得ないため、最低値の類似度を割り当てる（１．５）。テンプレートを移動させてその中心を画像中の各ピクセルに順番に置くことによって全ての類似度値を計算して類似度マップが得られたら、物体の考えられる位置を抽出するためにこのマップを後処理する（１．６）。そして最後に、検出された物体の類似度値を統計的有意水準又は用途により定義される閾値と比較する（１．７）。
【００２２】
提案する方法では、関心物体又はその一部を、領域の集合Ｔ０＝Ｔ１∪．．．∪ＴＭから成るテンプレートにより記述する。このテンプレートは、物体のトポロジー（その各部分の空間的関係）のみを記述し、その放射分析的特性は記述しない。６つの領域を有するトポロジカルテンプレートの一例を図２ａに示す。このテンプレートは、いずれかのピクセルに位置するテンプレートによって覆われる局所画像領域をどのように解釈するかを決める。図２ｂに示すようにテンプレートの中心をピクセル（ｘ０，ｙ０）に置くと、Ｍ＋１個の画像領域（図２のＴ０．．．Ｔ６の領域）において局所統計値が計算される。これらの統計値は、画像とテンプレートとの間の類似度の計算に用いられる。
【００２３】
物体のテンプレートを作成する際の一般的な指針は以下の通りである。
ａ）領域数Ｍは弁別的な物体の部分の数に対応していなければならない。
ｂ）いくつかの物体部分の放射分析的特性が類似している場合、それらはテンプレートの１つの領域に含まれなければならない。
ｃ）物体が非常に変わりやすい領域（高周波のテクスチャ、エッジ）を含む場合、それらの領域は、方法の性能をより良くするためにテンプレートから除外することができる。
ｄ）領域のサイズ又は形状の仮定は行わない。各領域Ｔｉはいくつかの非連結領域から成る可能性がある。各領域は穴（使用されない領域）を含み得る。
ｅ）本方法のより良い性能は、領域の形状を単純化することによって達成することができる。したがって、各領域Ｔｉが矩形の集合として表される場合、処理時間は最短となる。
ｆ）最良性能（リアルタイム用途に適している）は、以下の場合に達成することができる。すなわち、テンプレート形状（領域Ｔ０）が矩形であり、全ての他の領域Ｔｉが矩形の集合から成り、テンプレートに穴（使用されない領域）がない場合である。
【００２４】
顔検出タスク用のテンプレートの例を図３に示す。これらのテンプレートは、目領域が通常は周囲の肌領域よりも暗いという観察（図３ａ）に基づいて作成された。各テンプレートは、黒のエリア及び白のエリアにより画定される２つの領域から成る。なお、１つのテンプレート領域（黒で示す）は２つの非連結領域から成る。図３ｃのテンプレートは、暗い値から明るい値への強度遷移エリアを除外するための穴（灰色で示す）も含む。図３ｄのテンプレートは図３ｂを簡略化したもので、リアルタイムでの実施に適している。
【００２５】
テンプレートが異なるサイズの矩形の集合として表される場合、これらの矩形内の統計的特徴（平均及び分散）の高速な計算のために特別な画像前処理を適用することができる（図１、ブロック１．１）。画像を積分表現に変換することにより、このような特徴は、後述のように矩形の角の座標の４回のピクセル参照のみで高速に計算できるようになる。
【００２６】
本発明では積分画像Ｓｕｍ（ｘ，ｙ）及びＳｕｍＱ（ｘ，ｙ）を以下のように定義する。
【００２７】
【数２】
【００２８】
ここで、Ｉ（ｘ，ｙ）は原画像であり、ｘ，ｙ＜０の場合にＩ（ｘ，ｙ）＝０である。
【００２９】
テンプレートと画像領域との間の類似度は統計的仮説試験に基づく。ピクセル（ｘ０，ｙ０）及びその近傍Ｒ（ｘ０，ｙ０）毎に、２つの仮説を検討する：
Ｈ０：Ｒ（ｘ０，ｙ０）はランダムである。
Ｈ１：Ｒ（ｘ０，ｙ０）はテンプレートに類似している。
【００３０】
Ｈ０又はＨ１を受け入れる決定規則は、Ｍ個のピクセル群の平均が互いに統計的に異なるかどうかという試験に基づく。これらのＭ個の群はテンプレートにより画定され、その中心はピクセル（ｘ０，ｙ０）に位置する。
【００３１】
まず、２つの領域の場合：Ｔ０＝Ｔ１∪Ｔ２を検討する。よく知られた統計的ｔ検定(t-test)を２つのピクセル群に適用すると以下の類似度が得られる（いくつかの等価変換は省く）。
【００３２】
【数３】
【００３３】
この式から定数を除去すると、（１）の形の類似度が得られる。
【００３４】
テンプレートが３つ以上の領域から成る場合、別の統計的技法を用いて類似度を得る。この技法は分散分析(Analysis of Variances)（ＡＮＯＶＡ）と呼ばれ、数学的にはｔ検定と等価であるが、群数が２つよりも多い場合にのみ用いられる。
【００３５】
群間分散及び群内分散をＱ１（Ｔ１，．．．，ＴＭ）及びＱ２（Ｔ１，．．．，ＴＭ）とする。これらの分散は以下のように計算される。
【００３６】
【数４】
【００３７】
これらの分散は以下のように連結される。
【００３８】
【数５】
【００３９】
本発明では、フィッシャー基準を類似度として用いる（（５）、（６）、（７）に続く等価変換は省く）。
【００４０】
【数６】
【００４１】
この式から定数を除去すると、（１）の形の類似度が得られる。
【００４２】
したがって、点（ｘ０，ｙ０）における統計的テンプレートマッチングの結果は次のように表すことができる。
【００４３】
【数７】
【００４４】
類似度値が計算されたら、画像領域が関心物体に類似していると言えるほどこの値が大きいかどうかという検定を、統計的閾値処理を用いて行うことができる。このような検定には統計的な有意性の表を用いることができる。有意性の検定には、リスク水準を設定しなければならない。通常、０．０５のリスク水準を用いる。リスク水準及び自由度数が与えられると、ｔ値（（４）から）又はＦ値（（８）から）を標準的な有意性の表から得られる閾値と比較して、類似度値が有意であるほど十分に大きいかどうかを判定することができる。
【００４５】
上記のように、積分画像の使用により構成の速度を高めることができる。積分画像を用いると、任意の矩形領域Ｒの｜Ｒ｜σ２（Ｒ）の計算に必要なピクセル参照は２＊｜Ｒ｜回ではなく２＊４回となる。
【００４６】
【数８】
【００４７】
ここで、最後の等式は定義であり、（ｘ１，ｙ１）、（ｘ２，ｙ２）は矩形Ｒの左上及び右下の点の座標である。
【００４８】
矩形の集合から成る領域：Ｔｉ＝Ｒ１∪Ｒ２∪．．．ＲＫｉの場合、｜Ｔｉ｜σ２（Ｔｉ）の計算は同様である。
【００４９】
【数９】
【００５０】
上記の式を用いて、テンプレートと画像との間の類似度の計算は、テンプレートサイズに依存せず、テンプレートの複雑度（その中の矩形の数）に依存する。
【００５１】
（５）〜（７）を用いてさらなる最適化を行う。ここから、ｍ（ＴＭ）、σ２（ＴＭ）を計算する必要がないことは明らかである。これは、これらの値がｍ（Ｔ０），．．，ｍ（ＴＭ−１）、σ２（Ｔ０），．．．，σ２（ＴＭ−１）から導出できるためである。この最適化により、（ａ）少数の領域のみを用いる（Ｍ＝２，３）場合、又は（ｂ）領域ＴＭが非常に多数の矩形から成る場合に性能を大幅に高めることができる。
【００５２】
図４は、提案する方法による顔検出の例を示す。図４ｄに示すテンプレートを統計的テンプレートマッチングに用いた。図４の上の行は顔画像を類似度の最大値の位置と共に示す。下の行は、（９）を用いて計算した類似度マップの対応するフラグメントを示す。この例示には、ＡＴ＆Ｔ顔データベースからの画像を用いた。これらの画像は、AT&T Laboratories, Cambridgeのウェブサイトhttp://www.uk.research.att.com/facedatabase.htmlから入手可能である。
【００５３】
本提案によるテンプレートマッチング方法は、本方法を例示するために用いた顔検出タスクに特定的なものではない。本方法は、物体モデルを事前に定義及び簡略化することができる物体検出を扱うあらゆる用途に用いることができる。この方法は特に、バイモーダルの場合（明るい背景の中の暗い物体又は暗い背景の中の明るい物体）、又は物体モデルを一組の矩形から成るように簡略化することができる場合によく機能する。モデルを矩形から構成することができる場合、本方法のリアルタイム性能が達成されるが、これは相関に基づく技法には必ずしも当てはまらない。
【００５４】
図５は、顔特徴の検出への本方法の適用を示す。上の行は水平方向特徴（目、鼻腔、口）の検出を示す。下の行は垂直方向特徴（鼻）の検出を示す。左の列は検出結果を示す。中央の列はテンプレートを示し、右の列は類似度マップを示す。
【００５５】
基準マーク検出の典型的な例は、衛星画像の自動的な内部オリエンテーションであり、この場合、画像の歪みを補正するために、カメラにより作成された基準マークを検出しなければならない（図６）。図６において、（ａ）は衛星画像中の基準マーク（十字）を示し、（ｂ）はテンプレート（ｃ）〜（ｇ）を用いた統計的テンプレートマッチングにより得られる結合された類似度マップを示す。
【００５６】
提案するテンプレートマッチング方法の別の用途としては、路面標示の検出が考えられる。道路画像を直交ビューに変換すると、標示ははっきりした物体となり、テンプレートマッチングにより検出することができる。図７は、（ａ）道路画像−車内からのビュー、（ｂ）直交変換後の道路の「航空」ビュー、（ｃ）標示部分の始まり、終わり及び中央部を検出するテンプレートの例を示す。
【００５７】
図８は、画像透かし問題への提案する方法の適用を示す。ここでは、均一な領域から成る透かしを用いる。この例の透かしは画像の最下位ビットに埋め込まれるが（図８ａ）、他の埋め込み法も用いることができる。透かし画像の抽出（図８ｂ）後、透かしに符号化された情報を読み取る方法が必要となる。このような読み取りに、提案する統計的テンプレートマッチングを用いることができる。全ての考えられる透かし（その一部を図８ｅに示す）に対してマッチングを行い、考えられる位置及び類似度値を検出する（図８ｃ、図８ｄに２つの例を示す）。最も高い類似度値を生じるテンプレートを透かしと見なす。図８は、（ａ）透かし入り画像、（ｂ）透かし入り画像の最下位ビット、（ｃ）透かしに対応するテンプレート（図（ｅ）の左のテンプレート）を用いる統計的テンプレートマッチングの結果（類似度マップ）、（ｄ）なんらかの任意のテンプレートを用いる統計的テンプレートマッチングの結果（類似度マップ）、（ｅ）透かしを読み取るために用いられるテンプレートの例を示す。
【００５８】
上記の説明では、類似度は値が高いほど類似度が高いことを示すようになっており、極大値が検出される。しかし、使用する類似度に応じて、他の値（より低い値、等）でより近い類似度を示し、極小値を検出するようにしてもよい。高い値、極大値等への言及はそれに応じて解釈すべきである。
【００５９】
本明細書において、統計的という用語は、色、強度等の何らかの品質の分布に関連することを意味する。
【００６０】
本明細書において、「画像」という用語は、画像単位を記述するために用いられる。この画像単位は、解像度の変更、アップサンプリング、ダウンサンプリング等の処理の後のものを含み、又は積分画像と関連するものを含む。また、この用語は、フレーム、フィールド、ピクチャ等の他の同様の用語、又は画像、フレーム等のサブユニット若しくは領域にも適用される。ピクセル及びブロック又はピクセル群という用語は、適宜互換可能に用いられ得る。本明細書において、画像という用語は、文脈から明らかな場合を除いて、画像全体又は画像の一領域を意味する。同様に、画像の一領域は画像全体を意味し得る。画像は、フレーム又はフィールドを含み、静止画、フィルム若しくはビデオ等の画像シーケンス中の１つの画像、若しくは関連画像群中の１つの画像に関連する。
【００６１】
画像はグレースケール画像又はカラー画像であってもよく、又は別のタイプのマルチスペクトル画像、例えば、ＩＲ、ＵＶ若しくは他の電磁画像、若しくは音響画像等であってもよい。
【００６２】
本発明は、例えばコンピュータシステムにおいて適切なソフトウェア及び／又はハードウェアの変更を行って実施することができる。例えば、本発明は、プロセッサ又は制御装置等の制御手段又は処理手段、メモリ、磁気記憶装置、ＣＤ、ＤＶＤ等といった画像記憶手段を含むデータ記憶手段、ディスプレイ若しくはモニタ又はプリンタ等のデータ出力手段、キーボード等のデータ入力手段、及びスキャナ等の画像入力手段、又はこのような構成要素の任意の組み合わせを追加構成要素と共に有する、コンピュータ等を用いて実施することができる。本発明の態様は、ソフトウェア形態及び／又はハードウェア形態で、又は特定用途向け装置において提供するか、又はマイクロチップ等の特定用途向けモジュールを提供することができる。本発明の一実施形態による装置内のシステムの構成要素は、例えばインターネットを通じて他の構成要素と離れた場所に設けてもよい。
【図面の簡単な説明】
【００６３】
【図１】本発明の一実施形態の方法のフロー図である。
【図２】図２ａはテンプレートの一例である。図２ｂは本発明の一実施形態の方法のための、画像内に位置する図２ａのテンプレートを示す。
【図３】図３ａは関心物体としての画像領域である。図３ｂ〜図３ｄは図３ａの関心物体に対応するテンプレートの例である。
【図４】顔の画像の例と、対応する統計的テンプレートマッチングを示すグラフとを含む。
【図５】検出結果を含む顔の画像、顔特徴検出テンプレート、及び類似度マップを示す。
【図６】図６ａは基準マークを有する衛星画像を示す。図６ｂは図６ａに対応する類似度マップを示す。図６ｃは図６ａに用いるテンプレートを示す。
【図７】図７ａは道路画像を示す。図７ｂは直交変換後の図７ａの画像を示す。図７ｃは路面標示を検出するテンプレートを示す。
【図８】図８ａは透かし画像を示す。図８ｂは図８ａの画像の最下位ビットを示す。図８ｃおよび図８ｄは統計的テンプレートマッチングの結果を示すグラフである。図８ｅは図８ａの画像用のテンプレートを示す。
【特許請求の範囲】
【請求項１】
画像中の物体の検出方法であって、
テンプレートを画像の領域と比較することと、
類似度を求めることと
を含み、
前記類似度は統計測度を用いて求められる、画像中の物体の検出方法。
【請求項２】
前記統計測度は、前記テンプレートに対応する前記画像の前記領域の統計値を用いて求められる、請求項１に記載の方法。
【請求項３】
前記領域の前記統計値は、前記テンプレートに対応する前記画像の前記領域内のピクセル値の平均及び分散を含む、請求項２に記載の方法。
【請求項４】
前記統計測度は統計的仮説試験に関係する、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
Ｍ個の領域を含むテンプレートを用い、ここで、Ｍは２以上であり、前記テンプレートの前記Ｍ個の領域は前記物体の各部分及び前記各部分の空間的関係に対応する、請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記テンプレートは前記Ｍ個の領域の集合である、請求項５に記載の方法。
【請求項７】
物体の、類似する放射分析的特性（色、強度等）を有する複数の領域が、前記テンプレートの１つの領域に結合される、請求項５又は６に記載の方法。
【請求項８】
１つ又は複数の領域が、テンプレートマッチングに使用されない１つ又は複数のエリアを含む、請求項５〜７のいずれか一項に記載の方法。
【請求項９】
少なくとも１つの領域が非連結のサブ領域を含む、請求項５〜８のいずれか一項に記載の方法。
【請求項１０】
前記領域は単純な形状に対応する、請求項５〜９のいずれか一項に記載の方法。
【請求項１１】
前記形状は直線エッジを有する、請求項５〜１０のいずれか一項に記載の方法。
【請求項１２】
前記形状は矩形である、請求項１１に記載の方法。
【請求項１３】
前記類似度は前記テンプレートの前記Ｍ個の領域の各々に関係する、請求項５〜１２のいずれか一項に記載の方法。
【請求項１４】
前記類似度は、前記テンプレートの前記Ｍ個の領域の各々と、前記テンプレート全体に対応する１つの領域とに関係する、請求項１３に記載の方法。
【請求項１５】
前記テンプレートの前記Ｍ個又はＭ＋１個の領域に対応する前記画像の前記領域の各々に統計値が用いられる、請求項５〜１４のいずれか一項に記載の方法。
【請求項１６】
前記統計値は平均及び分散を含む、請求項１５に記載の方法。
【請求項１７】
前記統計測度の使用は、統計的ｔ検定をピクセル群に適用することを含む、請求項１６に記載の方法。
【請求項１８】
前記類似度は式（１）若しくは（４）の形であるか、又はそれに近い、請求項１７に記載の方法。
【請求項１９】
前記類似度の使用は、分散分析（ＡＮＯＶＡ）検定を適用することを含む、請求項１６に記載の方法。
【請求項２０】
前記類似度は式（８）若しくは（９）の形であるか、又はそれに近い、請求項１９に記載の方法。
【請求項２１】
前記類似度を閾値と比較することを含む、請求項１〜２０のいずれか一項に記載の方法。
【請求項２２】
統計的閾値処理又は統計的有意水準を用いることを含む、請求項２１に記載の方法。
【請求項２３】
リスク水準を設定することと、
前記リスク水準、自由度、及び有意性の表を用いることと
を含む、請求項２２に記載の方法。
【請求項２４】
前記画像から積分画像を導出することと、
前記類似度の計算において前記積分画像を用いることと
を含む、請求項１〜２３のいずれか一項に記載の方法。
【請求項２５】
前記類似度の計算において、前記積分画像と、（１０）又は（１１）の関係とを用いることを含む、請求項２４に記載の方法。
【請求項２６】
前記画像中の複数の領域の各々に関して類似度を導出することであって、それによって、類似度マップを導出することと、
前記類似度に従って極大値又は極小値を特定することと
を含む、請求項１〜２５のいずれか一項に記載の方法。
【請求項２７】
極大値又は極小値を閾値と比較することを含む、請求項２６に記載の方法。
【請求項２８】
物体検出において前記関心物体に関する追加の条件を用いることを含む、請求項１〜２７のいずれか一項に記載の方法。
【請求項２９】
前記追加条件は、前記統計的仮説試験において導出される統計値を含む、請求項２８に記載の方法。
【請求項３０】
１つの物体を表す複数のテンプレートを用いることと、
前記複数のテンプレートの各々を用いて類似度を導出することと、
前記複数の類似度を結合等により用いることであって、それによって、前記物体を位置特定することと
を含む、請求項１〜２９のいずれか一項に記載の方法。
【請求項３１】
前記画像の複数のバージョンを、異なる解像度で生成することと、
前記テンプレートの複数のバージョンを、異なる解像度で生成することと、
第１の解像度でのテンプレートマッチング及び第２のより高い解像度でのテンプレートマッチングを行うことと
を含む、請求項１〜３０のいずれか一項に記載の方法。
【請求項３２】
第１の解像度での前記マッチングは、前記物体を含む関心領域を検出するために行われ、
第２の解像度での前記テンプレートマッチングは、前記関心領域内で行われる、請求項３１に記載の方法。
【請求項３３】
前記テンプレートを１つの解像度用に調整することであって、異なる解像度での検出結果に応じて、例えばテンプレート領域を統合若しくは除外すること、又は前記テンプレート若しくはテンプレート領域のサイズ若しくは形状を変更することによって、或る解像度用に調整することを含む、請求項３１又は３２に記載の方法。
【請求項３４】
画像シーケンス中の物体の追跡方法であって、
請求項１〜３３のいずれか一項に記載の方法を用いて物体を検出することと、
次の画像中の前記物体のおおよその位置を予測することと、
前記予測を用いて、前記次の画像中の関心領域を求めることと、
請求項１〜３３のいずれか一項に記載の方法を前記関心領域において用いて、前記物体を検出することと
を含む、画像シーケンス中の物体の追跡方法。
【請求項３５】
前記テンプレートを、前記画像シーケンス中の１つの画像用に調整することであって、前記画像シーケンス中の異なる画像における検出結果に応じて、例えばテンプレート領域を統合若しくは除外すること、又は前記テンプレート又は前記テンプレート領域のサイズ若しくは形状を変更することによって、前記画像シーケンス中の１つの画像用に調整することを含む、請求項３４に記載の方法。
【請求項３６】
顔特徴及び／又は顔を検出するための、請求項１〜３５のいずれか一項に記載の方法。
【請求項３７】
衛星画像、地理画像等の中の特徴を検出するための、請求項１〜３６のいずれか一項に記載の方法。
【請求項３８】
基準マーク、路面標示、透かし等を検出するための、請求項１〜３７のいずれか一項に記載の方法。
【請求項３９】
請求項１〜３８のいずれか一項に記載の方法を実行する装置。
【請求項４０】
請求項１〜３８のいずれか一項に記載の方法を実行するようにプログラムされる制御装置。
【請求項４１】
請求項４０に記載の制御装置と、画像を記憶する記憶手段とを備える装置。
【請求項４２】
請求項１〜３８のいずれか一項に記載の方法を実行するコンピュータプログラム、システム又はコンピュータ読み取り可能な記憶媒体。
【請求項１】
画像中の物体の検出方法であって、
テンプレートを画像の領域と比較することと、
類似度を求めることと
を含み、
前記類似度は統計測度を用いて求められる、画像中の物体の検出方法。
【請求項２】
前記統計測度は、前記テンプレートに対応する前記画像の前記領域の統計値を用いて求められる、請求項１に記載の方法。
【請求項３】
前記領域の前記統計値は、前記テンプレートに対応する前記画像の前記領域内のピクセル値の平均及び分散を含む、請求項２に記載の方法。
【請求項４】
前記統計測度は統計的仮説試験に関係する、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
Ｍ個の領域を含むテンプレートを用い、ここで、Ｍは２以上であり、前記テンプレートの前記Ｍ個の領域は前記物体の各部分及び前記各部分の空間的関係に対応する、請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記テンプレートは前記Ｍ個の領域の集合である、請求項５に記載の方法。
【請求項７】
物体の、類似する放射分析的特性（色、強度等）を有する複数の領域が、前記テンプレートの１つの領域に結合される、請求項５又は６に記載の方法。
【請求項８】
１つ又は複数の領域が、テンプレートマッチングに使用されない１つ又は複数のエリアを含む、請求項５〜７のいずれか一項に記載の方法。
【請求項９】
少なくとも１つの領域が非連結のサブ領域を含む、請求項５〜８のいずれか一項に記載の方法。
【請求項１０】
前記領域は単純な形状に対応する、請求項５〜９のいずれか一項に記載の方法。
【請求項１１】
前記形状は直線エッジを有する、請求項５〜１０のいずれか一項に記載の方法。
【請求項１２】
前記形状は矩形である、請求項１１に記載の方法。
【請求項１３】
前記類似度は前記テンプレートの前記Ｍ個の領域の各々に関係する、請求項５〜１２のいずれか一項に記載の方法。
【請求項１４】
前記類似度は、前記テンプレートの前記Ｍ個の領域の各々と、前記テンプレート全体に対応する１つの領域とに関係する、請求項１３に記載の方法。
【請求項１５】
前記テンプレートの前記Ｍ個又はＭ＋１個の領域に対応する前記画像の前記領域の各々に統計値が用いられる、請求項５〜１４のいずれか一項に記載の方法。
【請求項１６】
前記統計値は平均及び分散を含む、請求項１５に記載の方法。
【請求項１７】
前記統計測度の使用は、統計的ｔ検定をピクセル群に適用することを含む、請求項１６に記載の方法。
【請求項１８】
前記類似度は式（１）若しくは（４）の形であるか、又はそれに近い、請求項１７に記載の方法。
【請求項１９】
前記類似度の使用は、分散分析（ＡＮＯＶＡ）検定を適用することを含む、請求項１６に記載の方法。
【請求項２０】
前記類似度は式（８）若しくは（９）の形であるか、又はそれに近い、請求項１９に記載の方法。
【請求項２１】
前記類似度を閾値と比較することを含む、請求項１〜２０のいずれか一項に記載の方法。
【請求項２２】
統計的閾値処理又は統計的有意水準を用いることを含む、請求項２１に記載の方法。
【請求項２３】
リスク水準を設定することと、
前記リスク水準、自由度、及び有意性の表を用いることと
を含む、請求項２２に記載の方法。
【請求項２４】
前記画像から積分画像を導出することと、
前記類似度の計算において前記積分画像を用いることと
を含む、請求項１〜２３のいずれか一項に記載の方法。
【請求項２５】
前記類似度の計算において、前記積分画像と、（１０）又は（１１）の関係とを用いることを含む、請求項２４に記載の方法。
【請求項２６】
前記画像中の複数の領域の各々に関して類似度を導出することであって、それによって、類似度マップを導出することと、
前記類似度に従って極大値又は極小値を特定することと
を含む、請求項１〜２５のいずれか一項に記載の方法。
【請求項２７】
極大値又は極小値を閾値と比較することを含む、請求項２６に記載の方法。
【請求項２８】
物体検出において前記関心物体に関する追加の条件を用いることを含む、請求項１〜２７のいずれか一項に記載の方法。
【請求項２９】
前記追加条件は、前記統計的仮説試験において導出される統計値を含む、請求項２８に記載の方法。
【請求項３０】
１つの物体を表す複数のテンプレートを用いることと、
前記複数のテンプレートの各々を用いて類似度を導出することと、
前記複数の類似度を結合等により用いることであって、それによって、前記物体を位置特定することと
を含む、請求項１〜２９のいずれか一項に記載の方法。
【請求項３１】
前記画像の複数のバージョンを、異なる解像度で生成することと、
前記テンプレートの複数のバージョンを、異なる解像度で生成することと、
第１の解像度でのテンプレートマッチング及び第２のより高い解像度でのテンプレートマッチングを行うことと
を含む、請求項１〜３０のいずれか一項に記載の方法。
【請求項３２】
第１の解像度での前記マッチングは、前記物体を含む関心領域を検出するために行われ、
第２の解像度での前記テンプレートマッチングは、前記関心領域内で行われる、請求項３１に記載の方法。
【請求項３３】
前記テンプレートを１つの解像度用に調整することであって、異なる解像度での検出結果に応じて、例えばテンプレート領域を統合若しくは除外すること、又は前記テンプレート若しくはテンプレート領域のサイズ若しくは形状を変更することによって、或る解像度用に調整することを含む、請求項３１又は３２に記載の方法。
【請求項３４】
画像シーケンス中の物体の追跡方法であって、
請求項１〜３３のいずれか一項に記載の方法を用いて物体を検出することと、
次の画像中の前記物体のおおよその位置を予測することと、
前記予測を用いて、前記次の画像中の関心領域を求めることと、
請求項１〜３３のいずれか一項に記載の方法を前記関心領域において用いて、前記物体を検出することと
を含む、画像シーケンス中の物体の追跡方法。
【請求項３５】
前記テンプレートを、前記画像シーケンス中の１つの画像用に調整することであって、前記画像シーケンス中の異なる画像における検出結果に応じて、例えばテンプレート領域を統合若しくは除外すること、又は前記テンプレート又は前記テンプレート領域のサイズ若しくは形状を変更することによって、前記画像シーケンス中の１つの画像用に調整することを含む、請求項３４に記載の方法。
【請求項３６】
顔特徴及び／又は顔を検出するための、請求項１〜３５のいずれか一項に記載の方法。
【請求項３７】
衛星画像、地理画像等の中の特徴を検出するための、請求項１〜３６のいずれか一項に記載の方法。
【請求項３８】
基準マーク、路面標示、透かし等を検出するための、請求項１〜３７のいずれか一項に記載の方法。
【請求項３９】
請求項１〜３８のいずれか一項に記載の方法を実行する装置。
【請求項４０】
請求項１〜３８のいずれか一項に記載の方法を実行するようにプログラムされる制御装置。
【請求項４１】
請求項４０に記載の制御装置と、画像を記憶する記憶手段とを備える装置。
【請求項４２】
請求項１〜３８のいずれか一項に記載の方法を実行するコンピュータプログラム、システム又はコンピュータ読み取り可能な記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公表番号】特表２００８−５３０７００（Ｐ２００８−５３０７００Ａ）
【公表日】平成２０年８月７日（２００８．８．７）
【国際特許分類】
【出願番号】特願２００７−５５５７０６（Ｐ２００７−５５５７０６）
【出願日】平成１８年２月２０日（２００６．２．２０）
【国際出願番号】ＰＣＴ／ＧＢ２００６／０００５９０
【国際公開番号】ＷＯ２００６／０８７５８０
【国際公開日】平成１８年８月２４日（２００６．８．２４）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・インフォメイション・テクノロジー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＲＩＣ ＩＮＦＯＲＭＡＴＩＯＮ ＴＥＣＨＮＯＬＯＧＹ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公表日】平成２０年８月７日（２００８．８．７）
【国際特許分類】
【出願日】平成１８年２月２０日（２００６．２．２０）
【国際出願番号】ＰＣＴ／ＧＢ２００６／０００５９０
【国際公開番号】ＷＯ２００６／０８７５８０
【国際公開日】平成１８年８月２４日（２００６．８．２４）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・インフォメイション・テクノロジー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＲＩＣ ＩＮＦＯＲＭＡＴＩＯＮ ＴＥＣＨＮＯＬＯＧＹ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]