(57)【要約】      （修正有）【課題】十分に大きく動いている物体を追跡することを可能にする方法を提供する。【解決手段】トレーニング画像から目標画像まで物体を追跡する方法及びシステムを提供する。トレーニング画像及び目標画像は画像シーケンスの要素である。トレーニング画像内の物体は物体状態によって表される。最初に、パーティクルのセットが取得され、該パーティクルのセット内の各パーティクルは重みに関連付けられ、それによって、該パーティクルが該重みに等しい確率で物体状態を表す。次に、目標画像に基づいてパーティクルのセット内の各パーティクルに回帰関数が適用されて、動いたパーティクルのセットが求められ、該動いたパーティクルのセットに従って物体状態が更新され、それによって、物体状態が目標画像内の物体を表す。【選択図】図１
2010238226.tif 000002
【特許請求の範囲】
【請求項１】
トレーニング画像から目標画像まで物体を追跡するための方法であって、前記トレーニング画像及び前記目標画像は画像シーケンスの要素であり、前記トレーニング画像内の前記物体は物体状態によって表され、該方法のステップを実施するためのプロセッサを備え、該方法は、
パーティクルのセットを取得するステップであって、各該パーティクルは重みに関連付けられ、それによって、該パーティクルが該重みに等しい確率で前記物体状態を表す、取得するステップと、
前記プロセッサを使用して、目標画像に基づいて前記パーティクルのセット内の各該パーティクルに回帰関数を適用するステップであって、動いたパーティクルのセットを求める、適用するステップと、
前記動いたパーティクルのセットに従って前記物体状態を更新するステップであって、それによって、前記物体状態が前記目標画像内の前記物体を表す、更新するステップと、
を含む、方法。
【請求項２】
前記適用の前に、前記物体状態に基づいて前記回帰関数をトレーニングすることをさらに含む、請求項１に記載の方法。
【請求項３】
前記更新に応答して、前記物体状態に基づいて前記回帰関数をトレーニングすることをさらに含む、請求項１に記載の方法。
【請求項４】
前記重みは重みのセット内の要素であり、それによって、前記パーティクルのセット内の各該パーティクルが対応する重みに関連付けられ、
前記方法は、
前記動いたパーティクルのセットに従って前記重みのセットを更新することをさらに含む、請求項１に記載の方法。
【請求項５】
前記適用することは、
前記パーティクルのセット内の各該パーティクルに対する運動変換を求めることをさらに含む、請求項１に記載の方法。
【請求項６】
前記回帰関数はｆであり、パーティクルの記述子は、
【数１】
2010238226.tif 000038
であり、ここでｍは前記物体記述子の次元であり、
前記運動変換は、
【数２】
2010238226.tif 000039
である、請求項５に記載の方法。
【請求項７】
時刻ｔにおける前記パーティクルの状態はロケーション変換行列Ｍｔによって記述され、前記パーティクルの運動は運動変換ΔＭｔによって記述され、それによって、
【数３】
2010238226.tif 000040
となる、請求項６に記載の方法。
【請求項８】
前記更新することは、
前記動いたパーティクルのセットに基づいて平均重みを計算すること、及び
前記平均重み及び前記動いたパーティクルのセットに基づいて前記物体状態を求めること、
をさらに含む、請求項１に記載の方法。
【請求項９】
前記取得することは、
前記物体状態に基づくガウス確率密度に従って前記パーティクルのセットを求めることをさらに含む、請求項１に記載の方法。
【請求項１０】
前記取得することは、
前記動いたパーティクルのセットに基づいて前記パーティクルのセットを求めることをさらに含む、請求項１に記載の方法。
【請求項１１】
前記取得することは、
前記目標画像を用いて前記トレーニング画像を更新すること、及び
前記画像シーケンス内の次の画像を用いて前記目標画像を更新すること、
をさらに含む、請求項１に記載の方法。
【請求項１２】
トレーニング画像から目標画像まで物体を追跡するためのシステムであって、前記トレーニング画像及び前記目標画像は画像シーケンスの要素であり、前記トレーニング画像内の前記物体は物体状態によって表され、該システムはプロセッサを備え、該システムは、
パーティクルのセットを取得する手段であって、各該パーティクルは重みに関連付けられ、それによって、該パーティクルが該重みに等しい確率で前記物体状態を表す、取得する手段と、
前記プロセッサを使用して、目標画像に基づいて各前記パーティクルに回帰関数を適用する手段であって、動いたパーティクルのセットを求める、適用する手段と、
前記動いたパーティクルのセットに従って前記物体状態を更新する手段であって、それによって、前記物体状態が前記目標画像内の前記物体を表す、更新する手段と、
を備える、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には画像処理及びコンピュータビジョンのための方法に関し、より詳細には、物体を追跡する方法に関する。
【背景技術】
【０００２】
追跡は、画像シーケンス内の物体の運動を推定するプロセスである。物体を追跡する方法は一般に、物体が或る初期画像内で検出されることを必要とする。その結果、後続の画像内で物体を追跡することができる。追跡方法は一般に、状態空間推定器、モデル整合、及び局所的カーネル検索の方法として分類することができる。
【０００３】
状態空間推定器の方法
状態空間推定器の方法は通常、マルコフプロセスを使用し、運動パラメータの確率密度関数（ｐｄｆ：probability density function）を構築する。たとえば、カルマンフィルタリングは正規分布を使用する。しかしながら、カルマンフィルタリング法は多モード分布を記述することができない。
【０００４】
モンテカルロ積分法、たとえばパーティクルフィルタは、物体の姿勢を含むいかなるパラメトリック変動も追跡することができる。しかしながら、これらの方法はランダムサンプリングに依存し、特により高い次元の表現に関して推定尤度を劣化させる傾向にある。その上、これらの方法の計算要件は状態変数の数と共に指数関数的に増大し、それによって、これらの方法は複雑な姿勢変化を追跡するには不適切なものとなる。
【０００５】
モデル整合の方法
モデル整合の方法は、物体モデルと、画像内に見える通りの物体との間の差分に基づいてコスト関数を定義する。コスト関数は、運動パラメータを最小化することによって解かれる。１つの例はオプティカルフロー推定であり、該オプティカルフロー推定では、物体モデルと画像強度との間の距離の２乗の合計が反復最小２乗問題として最小化される。この方法の主要な問題は、各反復に対する画像勾配、ヤコビ行列及びへッシアン行列の計算であり、このためこの方法は時間がかかってしまう。
【０００６】
他のモデル整合の方法は、運動とコスト関数との関係の代替的な定式化によってこの問題を克服する。いくつかの方法では、オフラインプロセスにおいて学習される画像勾配の線形関数を使用して運動が推定される。この着想は、関連ベクタマシンを使用して画像から運動への非線形マッピングを学習することに拡張される。
【０００７】
しかし、これらの方法は線形化を介して運動パラメータに対する加法的な更新を推定する。したがって、これらの方法は非線形運動を追跡することができない。
【０００８】
局所的カーネル検索
対照的に、カーネルに基づく方法は、物体を画像領域として表し、前回のロケーションを先行する確率として使用して同じ領域を検索する。この検索は、網羅的マッチングプロセス又は反復密度勾配推定として課される。カーネル法は多くの場合に、物体が連続するフレーム間で重なり合っている領域を有することを必要とする。ヒストグラム及びテンプレートのような初期の物体表現に起因して、カーネルに基づく方法は姿勢の変動を判別することができず、並進運動に限定される。
【０００９】
運動推定に関するリー群理論
リー代数を使用して、平均シフト演算を使用する剛体運動推定に関して、ユークリッド運動群構造を有する分布のモードを求めることができる。運動が大きい場合、平均シフト演算は失敗する可能性があることが知られている。ベクトル加法演算はリー代数において、アフィン「スネーク」（affine 'snake'）の追跡のために一連のアフィン運動を積分するように規定される。
【００１０】
テンプレート追跡のために加法的な更新がリー代数において実施される。しかしながら、この手法は行列乗算の非交換性を考慮しておらず、この推定は物体の初期変換付近でしか有効でない。
【００１１】
リー代数に基づく１つの追跡方法は、一次近似を測地誤差まで最小化し、特に物体の運動が大きくない場合に、非常に満足のいく姿勢追跡結果を報告する。参照により本明細書に援用される、Prikli他によって出願された「Method and System for Detecting and Tracking Objects in Images」と題する米国特許出願第１１／８６２，５５４号を参照されたい。
【００１２】
姿勢が複雑に変化する場合であっても、パーティクルフィルタを使用して画像シーケンス内で物体を追跡することが望ましい。
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本発明の目的は、物体追跡のための方法を提供することである。
【００１４】
本発明のさらなる目的は、十分に大きく動いている物体を追跡することを可能にする方法を提供することである。
【課題を解決するための手段】
【００１５】
十分に大きく動いている物体を追跡するという課題は、パーティクルフィルタを使用すると共に、各パーティクルを変換空間上に回帰させることによって解決され、ここで、マッピング関数はリー代数における回帰によって学習される。本発明の実施の形態は、回帰追跡器及びパーティクルフィルタと比較してより優れた追跡性能を実証している。
【００１６】
本発明の実施の形態は、パーティクルフィルタリング及びリー代数における回帰追跡の双方の利点を受け継ぐ方法を開示する。
【００１７】
回帰追跡とは異なり、本方法はパーティクルフィルタに起因して、物体のパラメータ変動が著しく大きい場合であっても、該変動を推定する。加えて、回帰に起因して、本方法の計算要件は最小限に留まり（リアルタイム）、それによって、アフィン変換のような複雑な姿勢変化を追跡することが可能となる。加えて、採用される低レベルの特徴（方向ヒストグラム）によって、単眼シーケンスにおける姿勢追跡が可能となる。
【発明の効果】
【００１８】
本発明の実施の形態は、リー代数における回帰姿勢推定を逐次重点サンプリングパーティクルフィルタ内に組み込む、物体追跡のための新規の方法を提供する。本発明の方法は、１０倍のパーティクルを用いる従来のパーティクルフィルタよりも正確な結果を提供し、リー代数における従来の回帰追跡器とは異なり大きな並進運動を回復する。
【図面の簡単な説明】
【００１９】
【図１】本発明の一実施形態による画像シーケンス内で物体を追跡する方法の流れ図である。
【図２】本発明の一実施形態による、物体座標における物体と、画像座標における物体との間の双方向変換の概略図である。
【図３】本発明の一実施形態による、方向ヒストグラムを用いる追跡領域の表現のブロック図である。
【図４】本発明の実施形態による、回帰関数をトレーニングするための方法のブロック図である。
【図５】本発明の一実施形態によるトレーニングセットのうちの複数の画像を含む図である。
【図６】本発明の一実施形態による、追跡方法に対する疑似コードのブロック図である。
【発明を実施するための形態】
【００２０】
図１は、本発明の実施形態による、画像Ｉｉのシーケンス１１０内で動いている物体１１５を追跡するための方法及びシステム１００を示す。画像シーケンス１１０をカメラによって取得することができる。代替的に、シーケンス１１０を持続性メモリ又は通信インタフェースから方法１００に提供することができる。一般性を損なうことなく、方法１００は物体１１５の非線形運動に関して記載される。しかしながら、本方法は任意のタイプの運動を有する物体を追跡することができる。
【００２１】
方法１００は、当該技術分野において既知のテレビ、プロジェクタ、再生装置、カメラ、又はコンピュータのような表示装置（図示せず）に接続されるプロセッサ又はマイクロプロセッサ１０３において機能することができる。表示装置を使用して、システムのユーザが物体の運動を見ることができる。
【００２２】
コンピュータは通常、バスによって接続される、１つ又は複数の処理装置及び／又はマイクロコントローラ、メモリ、並びに入出力インタフェースを備える。メモリは、後述するような現在の画像を記憶する揮発性メモリ、たとえばＲＡＭを含むことができる。プロセッサは、画像シーケンス１１０を記憶する持続性メモリ、たとえばビデオテープ及びＤＶＤのような取り外し可能記憶媒体、並びに、セットトップボックス、ネットワークインタフェース等のような通信インタフェースにアクセスすることもできる。本方法は、画像シーケンス１１０がリアルタイムで取得される場合にも物体を追跡することができることを理解されたい。
【００２３】
本発明の方法に対する入力は、画像シーケンス１１０である。該画像は、動いている物体１１５を含む。通常、画像シーケンスはビデオの複数のフレームである。シーケンス１１０の最初の画像はトレーニング画像と呼ばれる。トレーニング画像１１７に関して、物体状態１２０、たとえば物体ロケーション、方向、及びスケールが分かっている。画像シーケンスからの画像Ｉｉは、方法１００の現在の反復の間に物体を検出又は追跡する必要がある場合、目標画像と呼ばれる。
【００２４】
１つの実施形態において、目標画像は、方法１００の後続の反復に対するトレーニング画像となることに留意されたい。しかしながら、別の実施形態では、トレーニング画像１１７は方法１００の実行全体の間に変更されない。
【００２５】
トレーニング画像１１７及び物体状態１２０から回帰関数１３５をトレーニングする（１３０）。回帰関数トレーニングは、下記に、及び、参照により本明細書に援用される、Prikli他によって２００７年９月２７日付けで出願された「Method and System for Detecting and Tracking Objects in Images」と題する米国特許出願第１１／８６２，５５４号に記載されている。
【００２６】
上述のように、目標画像がトレーニング画像に置き換わるとき、目標画像のすべて又は一部に関して回帰関数１３５を再トレーニングすることができる。代替的に、方法１００の実行全体にわたって回帰関数を維持することができる。
【００２７】
シーケンス１１０の各目標画像Ｉｉをパーティクルのセット１４０として表す。セット１４０の各パーティクルの運動１５５を求める（１５０）。パーティクル１４０の運動１５５は、より詳細に後述するように、回帰関数１３５及び各パーティクルの特徴表現、たとえば、目標画像Ｉｉと比較して重み付けされた方向ヒストグラムを使用して求められる。
【００２８】
パーティクル１４０は、重みに関連付けられる物体１１５のランダムパーティクルのセットによって、物体１１５の事後密度関数によって表され、該重みはパーティクルが物体１１５と一致する確率を記述する。１つの実施形態では、物体状態１２０のガウス確率密度からサンプルを取り出す。代替的に、動いたパーティクル１５５を、方法１００の後続の反復に対するパーティクル１４０として使用することができる。
【００２９】
本発明の背景として、回帰関数１３５に基づく動いたパーティクル１５５は物体１１５の運動をより良好に表すことが理解されている。したがって、動いたパーティクルに関連付けられる重みを計算して組み合わせる（１６０）ことによって、物体１１５の物体状態１２０の新たな値がより高い精度で求められる。
【００３０】
より詳細に後述されるように、ステップ１６０は、トレーニング画像１１７及び物体状態１２０の現在の値に基づいて求められる（１７０）物体記述子１７５を利用する。
【００３１】
追跡メカニズムとしての回帰
本発明の実施形態を、物体１１５のパラメトリック運動変換Ａ（２）に関して説明する。パラメトリック変換は、所与の変数に適用されるパラメータの関数である。該変数は、画素特徴と、領域特徴と、画素座標と、領域座標とを含む。該パラメータは、たとえば、アフィン変換と、透視運動変換と、有限数のパラメータによって表すことができる他の線形変換、非線形変換、剛体運動変換、及び非剛体運動変換とを含む。本発明は、他の運動変換、たとえば相似変換Ｓ（２）、及びユークリッド運動ＳＥ（２）と共に使用することができる。
【００３２】
２次元パラメトリック変換Ａ（２）は３×３行列
【００３３】
【数１】
2010238226.tif 000003
【００３４】
によって与えられ、ここで、Ａは、回転、スケール及びスキューを表すための正則２×２行列であり、
【００３５】
【数２】
2010238226.tif 000004
【００３６】
である。すべてのパラメトリック変換から成るセットが行列リー群構造を形成する。リー群は微分可能多様体である。該群に対する演算は平滑構造に対応する。リー群は多様体であるため、リー群に対し微分学によって演算を行うことができる。大域的なリー群を、そのリー代数として知られる局所的なもの又は線形化したものに置き換えることができる。リー代数は、リー群及び微分可能多様体のような幾何学的対象に対して演算を行うのに使用することができる代数構造である。
【００３７】
図２は、物体座標及び画像座標における物体１１５のロケーションの双方向ロケーション変換行列Ｍ及びＭ−１を示す。物体座標における物体１１５のロケーションは単位正方形２０１である。画像座標における物体１１５のロケーションは画像２０２の追跡領域１６０である。アフィン行列Ｍは、以下の式に従って、座標２０３の原点における単位正方形２０１を、画像内の物体を囲む追跡領域１６０に変換する。
【００３８】
【数３】
2010238226.tif 000005
【００３９】
ここで、下付き文字はそれぞれ物体座標（ｏｂｊ）及び画像座標（ｉｍｇ）を示す。逆変換Ｍ−１もアフィン行列であり、画像座標１６０内の物体を物体座標２０１内の物体に変換する。
【００４０】
Ｉを入力画像１１０を示すものとし、ｔは時刻（フレーム）インデックスである。追跡は、時刻ｔまでの画像、すなわちＩ０．．．ｔ及び初期ロケーション変換Ｍ０を所与としてロケーション変換行列Ｍｔを推定する。初期画像内で物体を検出する方法については後述する。
【００４１】
ロケーション変換行列Ｍｔは、時刻ｔにおける物体座標における物体１１５のロケーションを規定する。ロケーション変換行列を以下のようにモデル化し、
【００４２】
【数４】
2010238226.tif 000006
【００４３】
各時刻（フレーム）ｔにおける運動変換ΔＭを推定する。運動変換ΔＭは、時刻ｔ−１からｔまでの物体座標２０３内の物体の運動に対応する。
【００４４】
物体座標における画像はＩ（Ｍ−１）である。画素値を物体１１５の追跡領域１６０とみなし、画素を記述子１７５、たとえば勾配方向ヒストグラムを用いて表す。記述子（観測値）はｏ（Ｍ−１）∈Ｒｍであり、ここでｍは記述子１７５の次元である。
【００４５】
追跡を、行列値回帰問題として定義する。前回処理した画像Ｍｔ−１の、ロケーション変換行列によって指示される物体の前回のロケーション、すなわち追跡領域、及び現在の画像Ｉｔを所与として、回帰関数１３５を使用して運動変換ΔＭｔを推定する。
【００４６】
【数５】
2010238226.tif 000007
【００４７】
物体記述子
図３は、物体１１５を囲む単位正方形２０１の表現を示す。単位正方形は、物体座標における単位正方形２０１の内部の規則的な格子において求められるいくつかの勾配方向ヒストグラムを含む。スケール不変特徴変換（ＳＩＦＴ）記述子と同様に、各画素のヒストグラムに対する寄与は画素の勾配の大きさに比例する。単位正方形３０１は６×６＝３６個のブロック３０２に分割され、ヒストグラムはブロックごとに求められる。
【００４８】
各ヒストグラム内の方向は０度と２π度との間でπ／６度刻みで量子化される。したがって、各ヒストグラムは１２次元であり、物体記述子ｏは４３２次元である。追跡中に、追跡領域内の周縁画素は頻繁にバックグラウンドの影響を受ける。したがって、本発明の１つの実施形態では、追跡領域の外周付近に１０％の境界を残し、単位正方形３０１の内部の物体の記述子を求める。
【００４９】
回帰関数
図４は、本発明の実施形態による、回帰関数ｆ１３５をトレーニングする（１３０）ための方法を示す。トレーニングの結果は、回帰係数Ωの推定値である。回帰係数は、物体記述子ｏを、運動変換ΔＭと相関させる。回帰関数がトレーニングされて画像に適用される方法は、物体追跡及び物体検出の場合と同じである。
【００５０】
トレーニングセット
トレーニング中に、物体１１５の初期ロケーションが、シーケンス１１０の初期（トレーニング）画像Ｉ０４２０内の初期追跡領域１６０によって近似される。追跡領域１６０は一般に、画像座標に従って物体１１５のロケーションを指示する。したがって、物体座標における物体１１５のロケーションのロケーション変換行列Ｍ０４６０も分かる。物体検出に関して、物体を含むトレーニング画像がトレーニングに供給される。図４を参照されたい。
【００５１】
物体の初期ロケーションＭ０４６０に基づいてｎ個のランダムパラメトリック運動変換行列から成る集合｛ΔＭ｝ｉ＝１．．．ｎを生成する（４３０）。各行列は、物体１１５の初期ロケーションＭ０４６０からの可能な運動、たとえば、シフト、回転、スケール、スキュー及びそれらの組み合わせを記述する。ロケーションＭ０４６０における物体１１５は、運動変換ΔＭ−１ｉを乗算することによって変換される。新たな記述子はｏｉ０＝ｏ０（ΔＭ−１ｉ．Ｍ−１０）である。運動変換ΔＭｉは、物体を単位正方形２０１に動かす。各運動変換ΔＭは、ロケーションＭ０４６０における物体１１５の記述子ｏに関連付けられる。運動変換はトレーニングセット４１０を決定する。トレーニングセット４１０は｛ｏｉ０，ΔＭｉ｝のｎ個のサンプルを含む。
【００５２】
図５は、初期トレーニングセット４１０の例５０１〜５０４を示す。トレーニング中の運動及び追跡中の推定される運動に対して記号ΔＭを使用する。下付き文字ｉはトレーニングセット内のサンプルを指し、一方で時刻インデックスｔは追跡中の推定される運動を指す。いくつかの実施形態では、シーケンス１１０の各目標画像Ｉｉは、追跡中にトレーニングセットを更新するのに使用される。これによって、回帰関数が、外観及び照明の変化に適応するようになる。
【００５３】
回帰関数
【００５４】
【数６】
2010238226.tif 000008
【００５５】
はアフィン行列である。したがって、アフィン行列の構造が考慮される。
【００５６】
線形運動推定のための従来の方法は、運動ΔＭ（ｐ）のパラメータ化、及び初期値を中心とする線形化を使用する。
【００５７】
【数７】
2010238226.tif 000009
【００５８】
従来の変換は恒等行列を中心とするため、線形化はΔＭ（ｐ０）＝Ｉにおいて実施される。従来の方法は、増分Δｐを推定することによって進行する。
【００５９】
リー群代数を使用してトレーニングセット４１０から回帰関数ｆ１３５をトレーニングする。運動変換ΔＭ１５０は記述子ｏ１７５の線形関数としてリー代数においてモデル化される。
【００６０】
リー群
ｄ次元多様体は、ユークリッド空間に局所的に類似している位相空間である。多様体上のすべての点は、
【００６１】
【数８】
2010238226.tif 000010
【００６２】
の近傍をマッピングする同相写像が存在する近傍を有する。
【００６３】
微分可能多様体は平滑性制約を満足する。したがって、多様体上の曲線の導関数を規定することが可能である。多様体上の点Ｍにおける導関数は、その点における接空間であるベクトル空間内に存在する。リー群は、群の演算、乗算及び逆元（inverse）が微分可能マップであるような微分可能多様体の構造を有する群Ｇである。群の単位元Ｉに対する接空間がリー代数ｇを形成する。
【００６４】
多様体上の距離は点を接続する曲線の長さによって測定され、長さが最小の曲線を「測地線」と呼ぶ。単位元Ｉから、ベクトルｍ∈ｇで開始する一意の測地線が存在する。指数写像ｅｘｐ：ｇ→Ｇが、ベクトルｍをこの測地線が到達する点にマッピングする。ｅｘｐ（ｍ）＝Ｍである場合、測地線の長さはρ（Ｉ，Ｍ）＝||ｍ||である。一般に、指数写像は全射（onto）ではあるが１対１ではない。したがって、逆写像対数：Ｇ→ｇは単位元Ｉの近傍付近でのみ一意に規定される。任意のＭ∈Ｇに関して、Ｍ＝ｅｘｐ（ｍ）であるようないくつかのｍ∈ｇが存在する場合、ｌｏｇ（Ｍ）は最小ノルムを有するベクトルとして選択される。群要素の逆元Ｍ−１による左演算：Ｇ→Ｇは点ＭをＩにマッピングし、Ｍにおける接空間をリー代数にマッピングし、これは同型写像である。マッピング及び測地線の定義を使用して２つの群要素間の距離は以下の式によって測定される。
【００６５】
【数９】
2010238226.tif 000011
【００６６】
アフィン運動Ａ（２）、相似変換Ｓ（２）、及びユークリッド運動ＳＥ（２）のような本発明の実施形態において使用する変換は、３×３正則正方行列の群である一般線形群ＧＬ（３，Ｒ）の閉部分群である。行列及びその逆元の指数写像、対数写像は以下のように定義される。
【００６７】
【数１０】
2010238226.tif 000012
【００６８】
一般に、指数写像は以下の恒等式を満足しない。
【００６９】
【数１１】
2010238226.tif 000013
【００７０】
マッピングは、ベイカー・キャンベル・ハウスドルフの公式
【００７１】
【数１２】
2010238226.tif 000014
【００７２】
を通じて以下の式によって定義される。
【００７３】
【数１３】
2010238226.tif 000015
【００７４】
ここで、［ｍ１，ｍ２］＝ｍ１ｍ２−ｍ２ｍ１はリー括弧演算である。アフィン行列の構造については上述の通りである。空間は６次元多様体である。
【００７５】
アフィン群のリー代数は行列
【００７６】
【数１４】
2010238226.tif 000016
【００７７】
の集合であり、ここで、Ｕは２×２行列であり、ｖ∈Ｒ２である。行列ｍは、行列Ｕの要素のそれぞれ及びベクトルｖを正規直交基底として選択することによって、６次元ベクトルとして参照されることがある。
【００７８】
回帰関数トレーニング
トレーニングセット４１０に基づくトレーニング４８０中、回帰係数Ω４７０が推定される。回帰係数４７０は、物体記述子ｏを、運動変換ΔＭと相関させる。この記載のために、回帰係数Ω４７０は回帰関数１４０と均等である。
【００７９】
トレーニングセット４１０は、上述のような記述子及び運動変換｛ｏｉ０，ΔＭｉ｝を含む。アフィン運動行列はベクトル空間上には存在せず、２つの運動の間の従来のユークリッド距離は有効な測定基準ではない。
【００８０】
しかしながら、アフィン運動行列は微分可能多様体上に存在する。この場合、重要な誤差関数は、回帰推定値ｆ（ｏｉ０）と運動変換ΔＭｉとの間の測地的距離の２乗の総和である。
【００８１】
【数１５】
2010238226.tif 000017
【００８２】
Ｍ１及びＭ２を２つの運動行列とし、ｍ１＝ｌｏｇ（Ｍ１）且つｍ２＝ｌｏｇ（Ｍ２）とする。式（８）のＢＣＨ公式を使用して、２つの運動行列の間の測地的距離に対する一次近似は以下の通りである。
【００８３】
【数１６】
2010238226.tif 000018
【００８４】
リー代数におけるｄ個の正規直交基底を選択すると、２つのベクトルの間のユークリッド距離として行列ノルムを求めることができる。式（８）のＢＣＨ公式、及びリー括弧演算の定義から、該近似は変換が小さいほどより良好であり、それによって、ｍ１及びｍ２がゼロに近づくか、又は均等にＭ１及びＭ２が恒等行列Ｉに近づく。式（１１）を使用して、式（１０）の誤差関数は、
【００８５】
【数１７】
2010238226.tif 000019
【００８６】
を一次項まで最小化することと均等である。変換は恒等行列の小さな近傍内であるため、該近似は十分に正確である。
【００８７】
回帰関数を以下のように定義し、
【００８８】
【数１８】
2010238226.tif 000020
【００８９】
リー代数における接線ベクトルｌｏｇ（ΔＭ）を推定する関数
【００９０】
【数１９】
2010238226.tif 000021
【００９１】
を求める。関数ｇを以下のような記述子の線形関数としてモデル化する。
【００９２】
【数２０】
2010238226.tif 000022
【００９３】
ここで、Ωは回帰係数のｍ×ｄ行列である。Ｘを初期記述子のｎ×ｍ行列とし、Ｙを運動のリー代数に対するマッピングのｎ×ｄ行列とする。
【００９４】
【数２１】
2010238226.tif 000023
【００９５】
ｌｏｇ（ΔＭ１）は、ここではｄ次元ベクトルの形態で参照される。
【００９６】
式（１３）及び（１４）を式（１２）に代入することによって、以下の式を得る。
【００９７】
【数２２】
2010238226.tif 000024
【００９８】
ここで、トレース（ｔｒ）が式（１２）内の総和に置き換わっている。トレースは、主対角線上の要素の合計である。誤差関数ＪａをΩに関して微分すると、最小値はΩ＝（ＸＴＸ）−１ＸＴＹとなる。
【００９９】
リアルタイムの追跡の場合、記述子の数は相対的に小さく、たとえばｎ＝２００である。記述子の数は特徴空間の次元ｍ＝４３２よりも小さい（ｎ＜ｍ）ため、この系は劣決定であり、ＸＴＸが階級不足となる。この場合、推定値はトレーニング誤差をゼロにする。しかしながら、該誤差は将来の予測に一般化されず、これは過剰適合と呼ばれる。
【０１００】
過剰適合を回避するために、回帰係数のサイズに対して、リッジ回帰である以下の追加の制約を設ける。
【０１０１】
【数２３】
2010238226.tif 000025
【０１０２】
ここで、Ｔは変換演算子である。リッジ回帰は、条件が悪い線形回帰問題を解くのに有用である。
【０１０３】
誤差関数Ｊｒの最小値は以下の通りである。
【０１０４】
【数２４】
2010238226.tif 000026
【０１０５】
ここで、Ｉはｍ×ｍ恒等行列である。正規化係数λが回帰係数に対する収縮の度合いを決定する。係数λの値が大きくなるほど運動が安定化し、一方で値が小さくなるほどフレーム間のより大きな運動が可能となる。係数λの最適値は、追跡全体を通じての、トレーニングシーケンスに対するλの残りの定数との相互検証によって選択される。
【０１０６】
第１のフレーム内の運動パラメータをランダムに生成することによってモデルをトレーニングした後、更新プロセスは単純な行列乗算しか必要としないため、連続するフレームにおいて非常に高速である。
【０１０７】
逐次重点サンプリング
回帰追跡は、隣接する画像間で物体ウィンドウ、すなわち状態が重なり合うことを必要とする。したがって、回帰追跡は運動の変化が大きく、このような重なり合いが満足され得ない場合には失敗する。
【０１０８】
この問題を克服するために、本発明の実施形態は、パーティクル、すなわちサンプルのセットが大きな探索空間にわたって取り出される逐次重点サンプリング（ＳＩＳ）を使用する。ＳＩＳは、過去１０年間にわたって開発されたほとんどの逐次的ＭＣフィルタの基礎を成すモンテカルロ（ＭＣ）法であり、ブートストラップフィルタリング、凝縮アルゴリズム、適者生存、また最も一般的にはパーティクルフィルタとしても知られている。
【０１０９】
主要な着想は、（たとえば静止している物体の）事後密度関数を、重みが関連付けられているランダムパーティクルのセットによって表すと共に、これらのサンプル及び重みに基づいて推定値を計算することである。しかしながら、ベイズ理論によれば、サンプルの数が大きいときにパーティクルの加重平均は物体の真の状態に集束するが、これは計算的に実行不可能である。
【０１１０】
回帰パーティクル
本発明の実施形態による回帰パーティクルフィルタでは、各パーティクルの状態はベクトルとして表される運動パラメータに対応する。パーティクルの状態の他の表現が可能である。運動パラメータを以下のようにベクトル化する。
【０１１１】
【数２５】
2010238226.tif 000027
【０１１２】
ここで、ａ、ｂ、ｃ、ｄ、ｘ、及びｙは運動パラメータである。時刻ｔにおけるｉ番目のパーティクルをｖｉｔとして示し、パーティクルｖｉｔの重みをｗｉｔとして示す。観測値Ｉｔは時刻ｔにおける目標画像である。パーティクル１４０｛ｖｉｔ，ｉ＝１，２，．．．，ｎ｝が提案密度ｑ（・）から生成される。代替的に、上述のように、パーティクル１４０を、方法１００の前回の反復の動いた物体１５５から取得することができる。
【０１１３】
時刻ｔにおける重みが以下の式によって更新される。
【０１１４】
【数２６】
2010238226.tif 000028
【０１１５】
ここで、ｑ（ｖｉｔ｜ｖｉｔ−１，Ｉｔ）は、パーティクルｖｉｔが生成された提案密度である。正規化重みπｉが以下の式によって与えられる。
【０１１６】
【数２７】
2010238226.tif 000029
【０１１７】
サンプル平均によって、物体状態
【０１１８】
【数２８】
2010238226.tif 000030
【０１１９】
１２０が求められる。
【０１２０】
【数２９】
2010238226.tif 000031
【０１２１】
式（２０）において、ｐ（Ｉｔ｜ｖｉｔ）は、以下の式によって与えられるｉ番目のパーティクルの尤度である。
【０１２２】
【数３０】
2010238226.tif 000032
【０１２３】
ここで、Ｄは、ｖｉｔに対応する２Ｄ画像領域と目標画像との間の勾配加重方向ヒストグラムの相違点、たとえばバタチャリヤ距離である。ｐ（ｖｉｔ｜ｖｉｔ−１）は推移確率であり、物体の運動の動態（履歴）によって求められる。これはデータを通じて学習される。ｑ（ｖｉｔ｜ｖｉｔ−１，Ｉｔ）は、サンプルを生成する提案密度である。本発明の場合、最初にガウス確率密度からサンプルを取り出す。
【０１２４】
【数３１】
2010238226.tif 000033
【０１２５】
ここで、ｖｉｔ，ｍはｖｉｔの中間サンプルを表し、Ｎ（０，Ｃ）はゼロ平均及び共分散行列Ｃを有するガウス分布である。
【０１２６】
基礎を成す領域が物体モデルにより良好に適合するように空間内のパーティクルの位置を改善するために、回帰追跡器を適用する。ベクトルを再び行列形式にマッピングし（ｖ→Ｍ）、以下のように計算する。
【０１２７】
【数３２】
2010238226.tif 000034
【０１２８】
パーティクルのベクトル表現に回帰を直接適用することができる。通常、サンプルを生成する方法、すなわち式（２３）及び（２４）に基づいて提案密度の閉形式表現ｑ（Ｍｉｔ｜Ｍｉｔ−１，Ｉｔ）を使用する。
【０１２９】
しかしながら、回帰追跡は特徴密度から変換空間へのマッピングである。本発明で使用した低レベル特徴である、式（２４）における勾配ヒストグラムｏｔ（Ｍ−１ｔ，ｍ）は、閉形式表現が導出されるのを回避する。
【０１３０】
したがって、パーティクルを、物体の変換動態に適合するようにサンプリングする。すなわち、ｐ（ｖｉｔ｜ｖｉｔ−１）＝ｑ（ｖｉｔ｜ｖｉｔ−１，Ｉｔ）。次いで、式（２０）を以下のように通分する。
【０１３１】
【数３３】
2010238226.tif 000035
【０１３２】
物体追跡
ステップ１：パーティクルを取得する
図１を参照すると、方法１００は、シーケンス１１０内の目標画像ごとに反復して実行される。パーティクルのセット１４０を取得する。１つの実施形態では、式（２３）に従ってパーティクルのセットを取得する。代替的に、方法１００の前回の反復において求めた、動いたパーティクルのセット１５５からパーティクルのセット１４０を更新することができる。
【０１３３】
ステップ２：パーティクルごとの回帰
パーティクルのセット内のパーティクルごとに、回帰関数１３５を使用して運動１５５を求める（１５０）。
【０１３４】
図６は、運動確定１５０のための疑似コードを示す。回帰関数ｆ１３５をトレーニングする。式（４）を使用して各パーティクルの運動を求める。回帰関数ｆを用いて運動推定を繰り返すことによって運動確定を改善することができる。推定される運動ΔＭｔが単位元（identity）と等しくなるか、又は現在の推定されるロケーションにおけるパーティクルの尤度が前回のロケーションにおけるパーティクルの尤度未満になると、反復は終了する。時刻ｔにおいてロケーションＭにあるパーティクルの尤度は以下の通りである。
【０１３５】
【数３４】
2010238226.tif 000036
【０１３６】
ここで、前回のロケーションにおけるパーティクルの記述子が現在のロケーションにおけるパーティクルの記述子と比較される。通常、パーティクルの追跡には１つの画像あたり１回又は２回の反復で十分である。
【０１３７】
ステップ３：物体状態を推定する
セット１５５内の各動いたパーティクルを再び運動状態にマッピングし、式（２５）に従って動いたパーティクルの平均重みを計算する。次に、式（２１）に従って物体状態１２０の新たな値を求める。
【実施例】
【０１３８】
本発明において提案密度関数からパーティクルを取り出す方法と、回帰関数トレーニングのためにランダムな運動を生成する方法との間には相関関係がある。本発明の実施形態では、パーティクルフィルタは、回転及びスケールよりも、むしろ大きな平行移動を補償するように設計される。
【０１３９】
合成シーケンス及び実世界のビデオの双方に対して広範囲にわたるテストを実施した。各テストにおいて、本発明の方法を、回帰追跡器及びパーティクルフィルタと比較した。
【０１４０】
すべてのテストサンプルに関して、勾配方向ヒストグラム（ＨＯＧ）記述子に２８８個の係数を適用した。ＳＩＦＴ記述子と同様に、各画素のヒストグラムに対する寄与はその勾配の大きさに比例する。単位正方形は６×６＝３６個の領域に分割され、それらのそれぞれにおいてヒストグラムが計算される。各ヒストグラムは０と２πとの間でπ／４度刻みで量子化される。各ヒストグラムのサイズは８次元であり、記述子ｏはｍ＝２８８次元である。追跡中に、周縁画素は頻繁にバックグラウンドによって汚染される。したがって、本発明では、単位正方形の外側に１０％の境界を残し、内側の矩形の内部に記述子を構築する。
【０１４１】
物体の姿勢として２Ｄアフィン変換モデルの６つのパラメータを推定した。ここで、各係数が同一の重要性を有している。回帰モデルは第１のフレームにおいてのみトレーニングされ、追跡プロセス中は一定に維持される。単一の物体のランダムアフィン変換によって、２００個のサンプルから成るトレーニングセットを生成した。−０．１〜０．１のランダムな値を６つの状態パラメータのそれぞれに与えることによってリー代数における運動が生成され、累乗法を介してアフィン行列にマッピングされる。
【０１４２】
小さなランダム摂動（−０．０５〜０．０５）を回転及びスケールパラメータＡに与え、より大きな値（−０．３〜０．３）を平行移動Ｔに与えることによって運動の最初の半分を割り当てると共に、大きいランダムな値をＡに与え、小さい値をＴに与えることによって他方の半分を割り当てることも分析した。後者の方が、著しく不規則な姿勢変化を描写しているシーケンスに対して物体を追跡する可能性が高いことが観測されている。
【０１４３】
グランドトゥルースアフィンパラメータが利用可能な合成シーケンスに関して、各方法によって一回の追跡反復を実施し、推定値と真の値との間の測地的距離の代わりに、単純に、以下のように６つすべてのパラメータに関する平均２乗誤差（ＭＳＥ）を測定した。
【０１４４】
【数３５】
2010238226.tif 000037
【０１４５】
アフィンモデルを用いて目標を追跡するが、目標によっては平面的でないものもあることに留意されたい。したがって、アフィンモデルは目標に完全に適合することはできないが、依然として最良のアフィン近似を生成する。
【０１４６】
比較を実施するために、従来のパーティクルフィルタと本発明の方法との双方において、提案密度関数を同じままにした。加えて、従来のパーティクルフィルタにおけるパーティクルの数は、双方の方法のＣＰＵ時間がほぼ等しくなるように経験的に選択されている。勾配情報は、パーティクルフィルタにおける尤度及び回帰追跡における領域記述子を計算するための唯一のキューとして使用されている。回帰追跡器をパーティクルフィルタ内に組み込むことによって、追跡の性能が著しく改善されることが実証されている。
【０１４７】
なお、本発明の方法はアフィン運動には限定されず、より複雑なパラメータ運動に容易に拡張することができる。
【０１４８】
本発明を好ましい実施形態の例として説明してきたが、本発明の精神及び範囲内で様々な他の適合及び変更を行うことができることは理解されたい。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内に入るすべての変形及び変更を包含することである。
【図１】
2010238226.tif 000041
【図２】
2010238226.tif 000042
【図３】
2010238226.tif 000043
【図４】
2010238226.tif 000044
【図５】
2010238226.tif 000045
【図６】
2010238226.tif 000046
【外国語明細書】
2010238226.tif 000047
2010238226.tif 000048
2010238226.tif 000049
2010238226.tif 000050
2010238226.tif 000051
2010238226.tif 000052
2010238226.tif 000053
2010238226.tif 000054
2010238226.tif 000055
2010238226.tif 000056
2010238226.tif 000057
2010238226.tif 000058
2010238226.tif 000059
2010238226.tif 000060
2010238226.tif 000061
2010238226.tif 000062
2010238226.tif 000063
2010238226.tif 000064
2010238226.tif 000065
2010238226.tif 000066
2010238226.tif 000067
2010238226.tif 000068
2010238226.tif 000069
2010238226.tif 000070
2010238226.tif 000071
2010238226.tif 000072
2010238226.tif 000073