(57)【要約】  方法は、カメラによりシーンに関して取得された映像中の移動物体を追跡する。背景モデルがフレーム毎に保持され、背景モデルにおける変化により移動物体が検出される。物体モデルが移動物体に関して保持され、その移動物体のカーネルが生成される。映像中の移動物体を追跡するために、平均値シフト法が各フレーム中の各カーネルに適用されて、背景モデル、物体モデル、及び平均値シフトカーネルにより各フレーム中の移動物体の推定位置の尤度が求められる。
2008535038.tif 000002
【特許請求の範囲】
【請求項１】
シーンの映像を取得するステップを含み、
前記映像はフレームシーケンスを含み、各フレームは複数の画素を含み、
フレーム毎に、
背景モデルを保持するステップと、
前記背景モデルにより移動物体を検出するステップと、
前記移動物体の物体モデルを保持するステップと、
前記移動物体に対し、前記移動物体の経路の尤度及び前記物体モデルの尤度により複数のカーネルを割り当てるステップと、
各カーネルに平均値シフト法を適用して前記カーネルの位置を推定するステップと、
前記複数のカーネルの推定位置を結合するステップと、
前記複数のシフトカーネルの結合された推定位置により前記移動物体の推定位置を求めて前記映像中の前記移動物体を追跡するステップとをさらに含む、
カメラによりシーンに関して取得された映像中の移動物体を追跡する方法。
【請求項２】
複数のカメラにより複数の映像を取得するステップと、
前記複数の映像中の複数の移動物体を同時に検出するステップと、
前記複数の映像中の前記複数の移動物体を同時に追跡するステップとをさらに含む
請求項１記載の方法。
【請求項３】
前記複数のフレームをサブサンプリングするステップをさらに含む
請求項１記載の方法。
【請求項４】
前記映像は、低フレームレートで取得される
請求項１記載の方法。
【請求項５】
前記フレームは、２フレーム毎秒未満のレートで取得される
請求項１記載の方法。
【請求項６】
非連結画素を除去して前記移動物体を検出するステップをさらに含む
請求項１記載の方法。
【請求項７】
前記複数のカーネルは、前記移動物体に関連する全ての画素を包囲する物体カーネルと、前記移動物体の画素の９０％を含む内部カーネルと、前記物体カーネルの２倍のエリアサイズである外部カーネルとを含む
請求項１記載の方法。
【請求項８】
各カーネルは、矩形である
請求項７記載の方法。
【請求項９】
各カーネルは、円形エリアである
請求項７記載の方法。
【請求項１０】
各カーネルは、前フレームにおける前記移動物体の形状である
請求項７記載の方法。
【請求項１１】
前記複数のカーネルは、画素強度の勾配の方向に移動される
請求項１記載の方法。
【請求項１２】
前記物体モデルは（Ｗ×Ｈ）×Ｄの要素行列であり、各要素は色サンプルを含み、ここで、Ｗ及びＨはそれぞれ前記物体モデルの幅及び高さであり、Ｄは連続フレーム数で測定される奥行きである
請求項１記載の方法。
【請求項１３】
現フレーム中の前記移動物体の前記推定位置はｚ１であり、前記物体カーネル内の画素は（ｘｉ，ｕｉ）Ｎｉ＝１であり、ここで、ｘｉはフレーム座標系の２Ｄ座標であり、ｕｉは、画素の色及び垂直勾配の大きさを含む特徴ベクトルであり、前記物体モデルにおけるサンプル点は（ｙｊ，ｖｊｋ）Ｍｊ＝１として表され、ここで、ｙｊは物体モデル座標系の２Ｄ座標であり、ｖｊｋは２Ｄの色及び勾配の大きさの特徴ベクトル｛ｖｊｋ｝ｋ＝１，．．．，Ｄ＋２である  請求項１２記載の方法。
【請求項１４】
各カーネルは、ガウス関数により重み付けされる
請求項１記載の方法。
【請求項１５】
各カーネルは、カラーヒストグラムにより表される
請求項１記載の方法。
【請求項１６】
前記尤度は、パーゼン窓推定器を用いて求められる
請求項１記載の方法。
【請求項１７】
前記移動物体のサイズをスケーリングするステップをさらに含む
請求項１記載の方法。
【請求項１８】
前記カーネルの以前の位置を集約するステップと、
前記集約した位置を標準化して前記移動物体の前記経路の尤度を得るステップとをさらに含む
請求項１記載の方法。
【請求項１９】
前記背景モデルと前記フレームとの間の距離マップを求めるステップと、
前記フレーム中の各画素に前記距離マップ中の値を、前記画素と前記カーネルの前の位置との間の距離により重み付けするステップと、
前記距離マップ中の複数のピークを求めるステップと、
前記移動物体の前の位置を前記ピークのうちの１つとして割り当てるステップと、
互いに近いピークをマージするステップと、
前記マージされたピークを前記ピークの大きさに関して閾値処理するステップと、
各ピークを中心とする前記複数のカーネルのうちの１つを中心に位置決めするステップとをさらに含む
請求項１記載の方法。
【請求項２０】
前記距離マップに関して前記画素をクラスタリングするステップをさらに含む
請求項１９記載の方法。
【請求項２１】
前記移動物体のサイズを用いて空間平均値シフト分割を適用することをさらに含む
請求項２０記載の方法。
【請求項２２】
考え得るカーネル位置の初期の組を選択するステップと、
物体モデルと、前記初期の組内の前記位置を中心とする前記カーネルとの間の類似度スコアを求めるステップと、
前記初期のカーネル位置からの距離に反比例する重みを各位置に割り当てるステップと、
前記類似度スコアに前記重みを掛けてピーク尤度を求めるステップと、
最大のピーク尤度スコアを有する考え得る位置から開始することによって、最大カーネル数に達するか、又は考え得るカーネル位置が残らなくなるまで、反復毎に前記物体サイズに比例する領域を除去することによって前記複数のカーネル位置を繰り返し選択するステップとをさらに含む
請求項１記載の方法。
【請求項２３】
経路尤度マップに基づいて前記考え得るカーネル位置の初期の組を選択するステップをさらに含む
請求項２２記載の方法。
【請求項２４】
前記映像が取得されたフレームレートに従って前記複数のカーネルの数を求めるステップをさらに含む
請求項１記載の方法。
【請求項２５】
前記映像が取得されたフレームレートに比例する値の範囲内で前記物体カーネルの寸法を変更するステップをさらに含む
請求項７記載の方法。
【請求項２６】
前記背景モデルは、前記画素の勾配の大きさ、向き、及びテクスチャの特徴に基づく
請求項１記載の方法。
【請求項２７】
カーネル毎に、
前記カーネルの推定位置と前記カーネルの前の位置との間の距離を測定することによって距離尤度スコアを求めるステップと、
以前のフレーム中の前記移動物体の以前の速度及び方向に基づいて動き尤度スコアを求めるステップと、
前記物体モデルを前記カーネルの前記推定位置における色、勾配、向き及びテクスチャと比較することによってモデル尤度スコアを求めるステップと、
前記距離尤度、前記動き尤度、及び前記モデル尤度の加重和を集約することによって融合スコアを求めるステップと、
前記融合スコアを用いて前記現フレーム中の前記移動物体の新たな位置を割り当てるステップとをさらに含む
請求項１記載の方法。
【請求項２８】
前記複数のカーネルの最大融合スコアを求めるステップと、
前記最大融合スコアにより前記移動物体の前記新たな位置を割り当てるステップと
をさらに含む
請求項２７記載の方法。
【請求項２９】
カーネル毎に、前記カーネルの前記推定位置と前記移動物体の前記前の位置との間の差ベクトルを構築するステップと、
前記差ベクトルに前記融合スコアを掛けるステップと、
前記掛けられた差ベクトルの和である和ベクトルを求めるステップと、
前記和ベクトルを標準化するステップと、
前記標準化されたベクトルを前記移動物体の前記新たな位置と前記前の位置との間の差として割り当てるステップとをさらに含む
請求項２７記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には映像中の物体の追跡に関し、特に、低フレームレートで取得された映像中の物体の追跡に関する。
【背景技術】
【０００２】
多くのコンピュータビジョンアプリケーション及び映像監視アプリケーションが、様々な環境における移動物体、例えば歩行者又は車両を識別しようとしている。一般に、シーン中の何かは、カメラにより取得された静止シーンの背景モデルと大幅に異なるときに関心の対象となる。最も単純な背景モデルは、背景シーンが経時的に全く静的であり、シーン中の物体はそれに見合った速度で移動するものと仮定する。
【０００３】
経時的に、静的な背景における個々の画素の強度値は通常、正規分布をとる。したがって、シーン中の関心対象でない変動は、単峰性でゼロ平均の「白色」ガウスノイズ法により適切にモデル化することができる。よって、そのような統計分布を表す合理的なモデルは単一ガウスモデルである（C.R. Wren、A. Azarbayejani、T.J. Darrel、及びA.P. Pentland著「Ｐｆｉｎｄｅｒ：人体のリアルタイム追跡（Pfinder: Real-time tracking of the human body）」（PAMI, 19(7), pp. 780-785, July 1997））。
【０００４】
多くの場合、単一ガウスモデルは、照明条件の変化により影が変化する背景のような動的な背景における画素強度値の時間的変化を正確にモデル化するには不適である。したがって、より複雑なシステムは、影により生じる変動のような照明の変化を関心対象でないものとして排除する機構を含む（Ismail Haritaoglu、David Harwood、及びLarry S. Davis著「Ｗ４：誰が？いつ？どこで？何を？（W4: Who? When? Where? What?）」（Proceedings of FG'98, IEEE, April 1998））。
【０００５】
動的な背景を画素レベルで記述するために複数のモデルを使用することは、背景のモデル化における飛躍的な進歩であった。具体的に言えば、ガウス分布の混合を使用する方法が、近年の多数の関連アプリケーションの一般的な基礎となった。
【０００６】
３つのガウス成分の混合を、各画素の視覚的特性をモデル化するために使用することができる（N. Friedman及びS. Russell著「映像シーケンスにおける画像の分割：確率論的アプローチ（Image segmentation in video sequences: A probabilistic approach）」（Thirteenth Conference on Uncertainty in Artificial Intelligence, August 1997））。このモデルは、経時的なガウス混合モデル（ＧＭＭ）を学習するために期待値最大化（ＥＭ）法も用いる。交通監視アプリケーションにおいて、各画素の強度値は３つの仮説、すなわち、道路、影、及び車両に制限される。残念ながら、この単純な仮定は、ＧＭＭが個々の画素の任意の分布をモデル化する能力を大幅に低下させる。さらに、この方法は高い計算コストがかかる。
【０００７】
別の方法はシーンが非静的であることを許容する（Chris Stauffer及びW.E.L. Grimson著「リアルタイム追跡のための適応的な背景混合モデル（Adaptive background mixture models for real-time tracking）」（Computer Vision and Pattern Recognition, volume 2, June 1999））。各画素は、可変数のガウス成分を有するガウス分布の混合としてモデル化される。この方法は背景を、各モードが静的モデルにゼロ平均の白色ガウスノイズ法を加えたものである多峰性の方法として表す。これらのモデルは、近似を用いてリアルタイムで更新することができる。この映像監視システムは、昼夜サイクル及び長期にわたるシーンの変化に対してロバストであることが証明されている。しかし、水面の波紋、海の波、又は動く草木のような非常に速い変化を示す背景の場合、このモデルは、長い映像シーケンスにわたって分散の大きい分布を生じる可能性がある。したがって、前景物体の検出感度は大きく低下する。
【０００８】
同様に競争力のある多峰性の背景の方法がF. Porikli及びO. Tuzel著「適応的な背景モデル及び平均値シフト解析による人体の追跡（Human body tracking by adaptive background models and mean-shift analysis）」（Conference on Computer Vision Systems, Workshop on PETS, IEEE, April 2003）（参照により本明細書中に援用される）に記載されている。
【０００９】
このような困難な状況に対処するために、ノンパラメトリック技法が開発された。これらの技法は、複数の最近取得されたサンプルに基づいて、画素値の統計を用いて各画素の背景特性を推定する。これらの技法は、速い背景変化に適応させることができる（Elgammal、D. Harwood、L. S. Davis著「背景差分のためのノンパラメトリックモデル（Non-parametric model for background subtraction）」（ECCV 2000, June 2000））。この方法は、密度推定にガウス関数を用いる。このモデルは、長い映像シーケンスにわたって最近のサンプル値の履歴を表す。
【００１０】
他の同様の技法は、適応的な密度推定の目的で可変サイズのカーネルを強調する。カーネルはデータ空間の探索領域に対応する。もう１つの特徴として、オプティカルフローを用いることができる（Anurag Mittal、Nikos Paragios著「適応的なカーネル密度推定を用いた動きベースの背景差分（Motion-based background subtraction using adaptive kernel density estimation）」（CVPR 2004, Volume 2, pp. 302-309, June, 2004））。
【００１１】
効果的な背景のモデル化を扱う他の技法は予測法として分類することができる。予測法は、画素強度の変化を時系列として扱い、過去の観測値に基づいて時間モデルを用いて新たな画素値を予測する。予測値と実際の観測値との間の偏差を用いて、予測モデルのパラメータを調節することができる。
【００１２】
他の方法はフィルタを用いる。例えば、カルマンフィルタは、各画素の動的特性をモデル化することができる（Dieter Koller、Joseph Weber、及びJitendra Malik著「遮蔽の理由付けを用いたロバストな複数車両の追跡（Robust multiple car tracking with occlusion reasoning）」（ECCV'94, May 1994））。カルマンフィルタを単純にしたもの、例えばウィーナーフィルタは、画素強度値の最近の履歴に基づいて確率的予測を行うことができる。
【００１３】
自己回帰モデルは、同様のテキスチャをシミュレートするために動的シーンの特性を取り込む（G. Doretto、A. Chiuso、S. Soatto、Y.N. Wu著「動的テクスチャ（Dynamic textures）」（IJCV 51(2), pp. 91-109, 2003））。この方法は、動的背景のモデル化に対処するため、及び映像監視において前景検出を行うために改良された（Antoine Monnet、Anurag Mittal、Nikos Paragios、Visvanathan Ramesh著「動的シーンの背景のモデル化及び差分（Background modeling and subtraction of dynamic scenes）」（ICCV'03, p. 1305, October, 2003）、並びにJing Zhong及びStan Sclaroff著「ロバストなカルマンフィルタによる動的なテクスチャ付き背景からの前景物体の分割（Segmenting foreground objects from a dynamic textured background via a robust Kalman Filter）」（ICCV'03, pp. 44-50, 2003））。或る種の難しいサンプル映像に関して良い結果が得られているが、このような自己回帰モデルを用いる計算コストは高い。
【発明の開示】
【発明が解決しようとする課題】
【００１４】
概して、従来の背景のモデル化には２つの主な欠点がある。これらのモデルの計算量は本質的に多い。これは、多数の映像が同時に取得され、映像中の物体をリアルタイムで追跡することが望ましい大規模な映像監視システムでは特に問題となる。従来のシステムは、費用のかかるネットワーク資源、記憶資源、及び処理資源を必要とする。
【００１５】
したがって、より少ないネットワーク資源、記憶資源、及び処理資源を用いて多数の映像の中の複数の物体を同時に追跡するシステム及び方法を提供することが望ましい。
【００１６】
また、従来の方法は、物体がそれに見合った速度で移動し、追跡すべき物体は連続フレームにおいて大きな重なりを有するものと仮定する。したがって、従来の方法は、１つのフレーム中の物体の位置が次フレーム中の物体と実質的に同じ位置にあるものと期待する。
【００１７】
したがって、それに見合わない速度で移動する物体を追跡することが望ましい。
【課題を解決するための手段】
【００１８】
本発明は、低フレームレート、例えば１フレーム毎秒（１ｆｐｓ）以下で取得された映像中の物体を追跡するシステム及び方法を提供する。映像を低フレームレートで取得することにより、ネットワーク帯域幅及び記憶媒体等の必要な資源が削減される。しかし、低レートの映像では、物体は予想よりも速い速度で移動し、物体の位置が連続フレームにおいて重なることはほとんどない。よって、従来の物体追跡方法は用いることができない。
【００１９】
したがって、本発明は、フレームシーケンスの中の大きな動きのある領域を中心とする複数のカーネルを用いる平均値シフト法を用いる。平均値シフト法の収束は、物体モデルを用いて２つの尤度項を統合することによって改善される。
【発明の効果】
【００２０】
本発明は、低フレームレートで取得された映像中の物体を追跡する方法を提供する。複数の平均値シフト法を、変化検出により得られる高い動きのエリアを中心とする複数のカーネルにわたって反復する。
【００２１】
従来の方法と異なり、本発明による方法は、ロバスト性及び精度を犠牲にすることなく低い時間分解能、例えば１ｆｐｓで移動物体を追跡することができる。
【００２２】
マルチカーネル法はまた、複数の物体を同時に追跡することができる。本方法は、遮蔽が存在していても、例えば物体が一時的に木又は駐車車両の背後に「消える」場合にも良好に機能する。
【００２３】
マルチカーネル法はまた、映像がフルの時間分解能で処理される場合に従来の方法よりも良好な性能を有する。
【発明を実施するための最良の形態】
【００２４】
システム構造
図１に示すように、本発明は、大規模な監視システムにおけるような多数のカメラ１１０のうちの１つによりシーン１０２に関して取得された映像１０１中の物体１７１を追跡するシステム及び方法１００を提供する。従来のカメラは、固定された比較的高いフレームレート、例えば３０又は６０フレーム毎秒（ｆｐｓ）で映像を取得するように設計されている。
【００２５】
必要な資源の数を削減し、処理効率を高めるために、本発明は、映像のフレームをサブサンプリングする（１２０）。したがって、通信、処理及び記憶された映像が低フレームレート（ＬＦＲ）、例えば１フレーム毎秒（１ｆｐｓ）以下で取得される。ＬＦＲ制御ユニット１３０がフレームレートを決定する。ＬＦＲフレーム１２１は多重化されて（１４０）監視プロセッサ１５０へ送られる。
【００２６】
ＬＦＲトラッカ１６０が軌跡１６１を求める。ＬＦＲトラッカはまた、ＬＦＲ制御ユニット１３０へのフィードバックを提供する。軌跡はマルチカメラマネージャ１７０に供給され、物体１７１が検出される。物体は、有意な事象１８１を検出する（１８０）ために用いられ、これらの事象１８１は監視プロセッサ１５０に供給される。
【００２７】
映像はそのような低フレームで取得されるため、物体が予想よりも遥かに速く移動しているように見え、また、通常のフレームレート、例えば３０ｆｐｓ以上で取得された映像のように移動物体が連続フレームにおいて重なることはほとんどないので、従来の物体トラッカは機能しない。
【００２８】
方法の動作
図２に示すように、本発明は、多峰性の背景のモデル化方法２００を用いる。本発明の方法では、サブサンプリングされたフレーム１２１のシーケンスにおける観測される照明の変化に従う背景モデル２１１を保持する（２１０）。
【００２９】
各フレーム中の各画素を評価して、その画素が背景モデルに「適合」するかどうかを判定する。画素が背景モデルから大きく逸脱する場合、その画素は、おそらく移動物体に関連する前景画素に割り当てられる。
【００３０】
移動物体に関連する領域を検出するために、先ず、おそらくはノイズに起因する各フレーム中の非連結画素の小さな領域すなわち「スペックル」を除去する。連結画素の領域は残りの画素から判定する。各連結領域を別個の物体に関連付ける。
【００３１】
スペックルノイズをモルフォロジーにより除去する。フィルタリング工程を加速するために、収縮−膨張（erosion-dilation）フィルタを提供する。本発明では２値の前景−背景マップがあるため、３２個の画素値を４バイトの整数に変換することができる。左右にシフトし、上位及び下位のビット列に論理包含演算を適用することによって、モルフォロジカルな膨張を適用する。２回目のパスでは、同様に包含ではなく論理排他を適用してフレームを「収縮」させる。したがって、本発明のフィルタリングは３２倍速い。
【００３２】
連結成分解析を適用して、フィルタリング後の前景画素の連結領域を求める。グラフベースのシングルパス法を用いる。連結成分解析中に、連結領域、すなわちフレーム中の移動物体に関連する可能性が高い画素を抽出する。連結領域毎に、画素の総数、重心、連結成分の全ての画素を包囲する物体カーネルの座標と、連結成分の画素の９０％を含む内部カーネルの座標とを求める。
【００３３】
これら２つのカーネルを用いて、凸領域を細長い領域と区別することができる。凸領域は物体のエリアと内部カーネルとの比が小さいのに対し、細長い領域は比がより大きい。物体カーネル及び内部カーネルは必ずしも同心でないことに留意すべきである。
【００３４】
ＬＦＲトラッカ１６０は、２組の物体１７１、すなわち潜在的な物体と追跡物体とを物体データベース２２０に保持する。所定数よりも少ないフレームにわたって追跡される連結画素の移動領域は、潜在的な物体としてマーキングされる。これらの画素は、シーン１０２中のノイズ又は追跡すべき潜在的な物体に対応する可能性がある。
【００３５】
潜在的な物体が所定数のフレームにわたって追跡される場合、その物体は潜在的な物体の組から除去され、追跡物体の組へ入れられる。
【００３６】
連結領域の特性を用いて、物体に関連する領域を判定する。これらの特性は、後述のようなカーネル２３１の形態である。カーネルは、物体カーネル、内部カーネル、及び外部カーネルを含む。２つの連結領域の内部カーネルが重なる場合、それらの領域は同一物体に関連する。物体カーネルが重なり、重なるエリアが領域のエリアに合致する場合、外部カーネルもまた同一物体に関連付けられる。
【００３７】
マルチカーネル平均値シフト
サブサンプリングされたフレーム１２１のシーケンスにおいて、マルチカーネル平均値シフト法を用いて物体１７１を追跡する（１６０）。物体毎に、カーネル２３１を最初に初期化する（２３０）。
【００３８】
カーネルは、移動物体に関連する可能性のある画素領域である。カーネルは、フレーム中の２Ｄ空間エリアに対応する。カーネルは、矩形、円形、楕円形、画素組、物体のシルエット、又は任意の他の所望の形状であり得る。本発明では矩形カーネルを選ぶ。空間領域に加えて、カーネルはまた、色空間における３Ｄ容積に関連付けることができる。
【００３９】
従来の平均値シフト法はクラスタリングを用いる。この平均値シフト法は、クラスタ数の事前知識を必要とせず、クラスタの形状を制約しない（D. Comaniciu及びP. Meer著「平均値シフト：特徴量空間解析へのロバストなアプローチ（Mean-shift: A robust approach toward feature space analysis）」（IEEE Trans. Pattern Anal. Machine Intell., vol. 24, pp. 603-619, 2002）（参照により本明細書中に援用される）を参照のこと）。
【００４０】
この平均値シフト法は、或るデータ点から開始し、反復毎に、画素強度の勾配の方向へ移動する。この反復は、その点が分布の局所モードに収束すると終了する。分布の局所モードへの収束は、平均値シフトの反復がそのデータ点において開始されるときに保証される。しかし、従来の平均値シフトによる追跡は、物体のカーネルが連続フレームにおいて大きく重なることを必要とする。
【００４１】
本発明によるＬＦＲ映像１２１では、物体の移動が異常に大きく予測不可能である。したがって、物体の前の位置を中心とする従来の単一の平均値シフトカーネルでは機能しない。この問題を克服するために、物体の前の位置に加えて、各フレームにおけるシーン中の大きな動きに対応するエリアにおいて物体１７１毎に複数のカーネル２３１を初期化する（２３０）。これらの複数のカーネルは、さらに詳細に後述するように、移動物体の経路の推定尤度に基づいて割り当てられる。複数のカーネルの尤度２８１スコアを収束点において求め、最大スコアを獲得した位置を新たな位置として選択する。
【００４２】
前フレームにおける物体領域である単一カーネルに依存する代わりに、本発明では、変化検出モジュール２４０により求められるような大きな動きに対応するエリアを中心とする複数のカーネルにおいて平均値シフトを反復する。
【００４３】
平均値シフト法２８０を各カーネル２３１に適用して、推定経路の位置にあるカーネルが本当に移動物体に関連するものであるという尤度２８１を求める。
【００４４】
各物体の位置を推定した後、連結成分を照合する。この照合は、連結成分の画素とのカーネルの重なりに基づいて行う。
【００４５】
複数のカーネルの割り当て
ガウスモデル又はカルマンフィルタリングといった任意の利用可能な方法を用いて背景モデルを推定すると共に、現フレームを推定した参照背景モデルと比較して、現フレームにおいて異なる領域を見付ける。
【００４６】
画素毎に、現フレームにおける画素と、背景モデルにおける対応画素との間の色の距離を求めて距離マップを得る。次に、この距離マップに空間クラスタリングを適用する。このクラスタリングは、距離マップのピークを求めるための別の空間平均値シフトクラスタリングにより行われる。本発明の方法はまた、他のクラスタリングアルゴリズム、例えばｋ平均クラスタリング及び階層クラスタリングを用いることができる。
【００４７】
画素毎に、距離マップ値の値を、その画素と、前フレームにおける対応する物体カーネルの位置との間の距離に対して重み付けする。この変換は、物体の前の位置に近い位置ほど高い尤度を割り当てる。
【００４８】
次に、距離マップ内のピークを求める。前フレームにおける物体の領域の重心を付加的なピークとして割り当てる。考え得る物体サイズのパラメータを用いて互いに近いピークをマージする。各ピークの大きさが所定の閾値よりも高い場合、そのピークにカーネルを割り当てる。したがって、少なくとも１つのピークが存在し、シーン中で観測される動きの量により、各移動物体につき複数のピークが存在する場合がある。
【００４９】
代替的に、以前に追跡された物体の履歴を保持する経路尤度マップに基づいて考え得るカーネル位置の初期の組を選択する。物体カーネルが経路尤度マップにおける画素に対応する場合に、その画素の値を増大させる。映像のフレーム毎に経路尤度マップを更新し続ける。したがって、多数のフレームにおいて物体を追跡すれば、経路尤度マップは物体の可能性の高い位置を示す。
【００５０】
例えば、交通監視映像の場合、尤度経路マップは、物体（例えば車両）が移動している車線に対応する画素の値が高くなる。
【００５１】
経路尤度マップを用いて、経路尤度スコアに基づいて一組の画素を選択する。この画素組に関して、物体モデルと、これらの画素を中心とするカーネルとの間の類似度スコアを求める。これらの類似度スコアを元のカーネル位置からの距離によりスケーリングし、中心から離れた画素ほど類似度スコアが小さくなるようにする。次に、最大スコアを有する画素から開始することによって、最大カーネル数に達するか、又は考え得るカーネル位置が残らなくなるまで、反復毎に物体サイズに比例する領域を除去することによって画素を繰り返し選択する。これらの画素は、複数カーネルの位置として割り当てられる。
【００５２】
物体モデルの管理
物体管理（２５０）は以下のように行われる。物体モデルが以後のフレームにおけるどの連結成分とも一致しないとき、その物体モデルを物体データベースから削除する。以前に追跡したどの物体とも一致しない連結成分に関して、新たな物体モデルを初期化する。
【００５３】
現在追跡中の物体が別の物体とマージされない場合、後述のように、式（１２）を用いて物体のスケールを適応させる（２６０）。
【００５４】
本発明の物体はノンパラメトリックモデルにより表される。この物体モデルは、（Ｗ×Ｈ）×Ｄの要素行列である。行列の要素は物体の３Ｄの色サンプル、例えばＲＧＢ画素強度であり、ここで、Ｗ及びＨはそれぞれ物体モデルの幅及び高さであり、Ｄは、連続フレーム数で測定される奥行き又は時間サイズである。なお、このモデルは背景画素を含まない。
【００５５】
現フレーム中の移動物体の位置の尤度はｚ１である。本明細書中では推定物体カーネル内の画素を（ｘｉ，ｕｉ）Ｎｉ＝１とし、ここで、ｘｉはフレーム座標系の２Ｄ座標であり、ｕｉは３Ｄの色ベクトルである。
【００５６】
物体モデルにおける対応するサンプル点は（ｙｊ，ｖｊｋ）Ｍｊ＝１として表され、ここで、ｙｊは物体モデル座標系の２Ｄ座標であり、ｖｊｋは３Ｄの色ベクトル｛ｖｊｋ｝ｋ＝１，．．．，Ｄである。
【００５７】
推定物体カーネル内のインデックスｉは物体モデルのインデックスｊにマッピングする。このマッピングは１対１ではない。通常、物体カーネルのサイズは物体モデルのサイズよりも遥かに大きいため、物体モデルの１画素は物体カーネル内の数画素にマッピングする。
【００５８】
追跡中、物体モデルの各画素の「最も古い」サンプルを現フレームからの１つの対応画素で更新することによって各物体モデルを保持する（２７０）。本発明では、ブレを防ぐために、対応画素の平均値は用いない。前景分割を用いて、現フレーム中の背景画素に対応する物体モデルの画素は更新しない。
【００５９】
背景情報を用いる平均値シフト
カラーヒストグラムに基づく平均値シフト法は、非剛性の物体追跡に効率的且つロバストであり得る。しかし、追跡物体の色情報が背景の色に似ている場合、平均値シフト追跡の性能は低下する。
【００６０】
したがって、本発明では、画素の背景モデル２１１も用いて、本発明の平均値シフト物体トラッカ１６０の性能を高める。
【００６１】
物体の重み付きカラーヒストグラムは｛ｑｓ｝ｓ＝１，．．．，ｍである。このヒストグラムは、ノンパラメトリック物体モデル
【００６２】
【数１】
2008535038.tif 000003
【００６３】
を用いて構築され、ここで、サイズｈｔは物体モデルの横及び縦のサイズの半分であり、ｋＮは、ｄ次元空間の多変量ガウス（正規）関数
【００６４】
【数２】
2008535038.tif 000004
【００６５】
に従って重み付けされた物体カーネルである。本発明では、２に等しいｄを空間情報に、３に等しいｄを色情報に用いる。定数項Ｑ１は、Σｍｓ＝１ｑｓ＝１であることを保証する。関数（＾）ｍは色値を、量子化された色空間の対応するヒストグラムビンにマッピングする。なお、（＾）ｍは、ｍの上に＾が有ることを表す。
【００６６】
物体モデルは履歴情報を含む。この履歴情報は、物体が遮蔽されている間、ヒストグラムをより正確にする。
【００６７】
位置ｚを中心とするカーネルのカラーヒストグラムはｐ（ｚ）である。同位置の背景のカラーヒストグラムはｂ（ｚ）である。カーネルの中心から離れた画素ほど小さな重みを割り当てるために２Ｄのガウス形重み関数が用いられる。
【００６８】
Ｂｈａｔｔａｃｈａｒｙａ係数
【００６９】
【数３】
2008535038.tif 000005
【００７０】
は、物体ヒストグラムと、現フレーム中の物体の推定位置ｚにおけるヒストグラムとの間の類似度２２１を測定する。
【００７１】
背景情報を統合し、類似度関数を次のように定義する。
【００７２】
【数４】
2008535038.tif 000006
【００７３】
ここで、αｆ及びαｂは前景成分及び背景成分の混合係数である。
【００７４】
上記の類似度関数を最大化することに加えて、現ヒストグラムと背景ヒストグラムとの間の類似度にペナルティーを科す。物体は背景と異なる外観を有するものと仮定する。
【００７５】
本発明ではαｆ＝１及びαｂ＝１／２を用いる。類似度関数は次のように書き換えることができる。
【００７６】
【数５】
2008535038.tif 000007
【００７７】
本発明において現フレーム中の物体位置の探索を開始する初期位置はｚ０である。カーネルヒストグラムｐｓ（ｚ０）及び背景ヒストグラムｂｓ（ｚ０）の値を中心としてテイラー展開を用いると、
【００７８】
【数６】
2008535038.tif 000008
【００７９】
となる。定数項をＱ２に入れると、次式が得られる。
【００８０】
【数７】
2008535038.tif 000009
【００８１】
カーネルヒストグラムｐ（ｚ）及び背景ヒストグラムｂ（ｚ）の定義を用いて、類似度関数は次のように書き換えられる。
【００８２】
【数８】
2008535038.tif 000010
【００８３】
ここで、（＾）ｍｆ（ｘｉ）及び（＾）ｍｂ（ｘｉ）は現フレーム及び背景モデルの画素を量子化された色空間の対応するカラービンにマッピングする。
【００８４】
サイズｈは各寸法に沿ってカーネルの半分のサイズに等しい。式（７）の第２項は、データがｗｉで重み付けされたカーネル密度推定値に等しい。この重みｗｉは負であってもよい。式（３）の類似度関数によれば、この分布のモードは平均値シフト法により求められる。
【００８５】
位置ｚ０における平均値シフトベクトルは
【００８６】
【数９】
2008535038.tif 000011
【００８７】
となり、ここで、ｇＮ（ｘ＊）＝−ｋ´Ｎ（ｘ＊）である。
【００８８】
物体モデルの尤度
ｚを中心とするカーネル内の単一の画素（ｘｉ，ｕｉ）が物体に属するものであるという尤度２８１は、パーゼン窓推定器
【００８９】
【数１０】
2008535038.tif 000012
【００９０】
を用いて推定することができる。上記において、色情報を表すカーネルのサイズはｈｃ＝１６として選択される。位置ｚにある物体の尤度２８１は次のように測定される。
【００９１】
【数１１】
2008535038.tif 000013
【００９２】
物体カーネルｋＮの重み関数は、中心から離れたサンプルほど小さな重みを割り当てて推定性能を高める。
【００９３】
本発明による平均値シフト追跡法の擬似コードを付録Ａに示す。
【００９４】
スケール適応
物体モデルのスケール適応（２６０）は前景画素のみを用いて行われる。これは、物体がカメラに向かう方向又はカメラから離れる方向へ移動している可能性があり、それによりフレーム中の物体のサイズが変わるために行われる。推定位置ｚｌを中心とする物体の物体カーネルはＢである。物体カーネルは外部カーネルＯの中心でもある。この外部カーネルは物体カーネルＢの２倍のエリアを有する。適合スコア
【００９５】
【数１２】
2008535038.tif 000014
【００９６】
を最大化する。ここで、（＾）ｃ（ｘ）は、ｘが前景画素である場合に１であり、そうでない場合に０である。各フレームにおいて、外部カーネルＯを固定したまま、境界線の位置を変えることによって物体カーネルＢを全ての寸法で或る限界内で変更すると共に、最大の適合スコアを生じるスケールを選択する。
【００９７】
矩形の物体カーネルＢの寸法は（ｘＬ，ｘＲ，ｙＵ，ｙＤ）であり、ここで、ｘＬは左端の境界線のｘ座標であり、ｘＲは右端の境界線であり、ｙＵは上側の境界線であり、ｙＤは下側の境界線である。フレームレートｆｒに比例する或る限界内で
【００９８】
【数１３】
2008535038.tif 000015
【００９９】
のように寸法を変え、その度に適合スコアを求める。
【０１００】
通常、低フレームレートのために、物体カーネルは２つの連続フレームにおいて重ならず、従来の平均値シフト法を用いて物体を追跡することを不可能にする。本発明の物体モデル尤度関数は、シーン中の複数の物体により生じる曖昧さを解消する上で非常に効果的である。さらに、ヒストグラムに基づく平均値シフトトラッカは、背景モデル２１１を含めることによって大幅に改善することができる。
【０１０１】
カーネル推定値の融合
物体の複数のカーネルを初期化して各カーネルに平均値シフト推定を適用した後、推定カーネル位置（ｘ，ｙ）ｋを得る。ここで、ｋ＝１，．．．，Ｋであり、Ｋは複数のカーネルの数である。次に、これらの位置推定値を融合して、物体の新たな位置（ｘ，ｙ）＊を以下のように求める。
【０１０２】
これらの推定位置の各々に割り当てることのできる尤度スコアはいくつかある。本発明では、カーネルの推定位置と物体の前の位置（ｘ，ｙ）ｔ−１との間の距離を測定することによって距離尤度スコアを測定する。この距離尤度スコアは距離が大きいほど小さくなる。この距離は、２Ｄの画像平面距離又はシーンの地表面が利用可能であれば３Ｄの地表面距離を用いることによって測定することができる。
【０１０３】
カルマンフィルタを用いて以前のフレーム中の物体の以前の速度及び方向に基づいて動き尤度スコアを求め割り当てることによって物体の動き履歴を統合する。平均値シフト法によるカーネルの推定位置がカルマンフィルタによる推定位置から離れるほど、動き尤度スコアの値は低くなる。
【０１０４】
本発明では、物体モデルが既にあるので、物体モデルを、現フレームの物体の推定位置を中心とするカーネルと比較することによってモデル尤度スコアも求める。モデル尤度距離は、色、勾配、向き、及びテクスチャの距離を含む。比較のために、物体モデルと、現フレームの色、勾配、及びテクスチャの特徴との間の類似度を求める。物体モデルが高い値を有する場合に高いモデル尤度スコアを割り当てる。上記の尤度は、複数のカーネルの推定位置の各々に関して求められる。
【０１０５】
各カーネルの融合スコアを求めて、これらのスコアを全て結合する。重み付きの距離、動き、及びモデル尤度スコアを合計する。
【０１０６】
物体の新たな位置を求めるためには、２つの方法が可能である。第１の方法は、スコアの最も高い位置を現フレーム中の物体の推定位置として選択する。
【０１０７】
第２の方法はベクトル加算に基づく。本発明では、物体の前の位置（ｘ，ｙ）ｔ−１を原点（０，０）とし、推定カーネル位置（ｘ，ｙ）ｋから前の位置（ｘ，ｙ）ｔ−１を引くことによって、この原点に対して差ベクトルを求める。すなわち、（ｘ，ｙ）ｋｄ＝（ｘｋ−ｘｔ−１，ｙｋ−ｙｔ−１）である。差ベクトルの各々にそれらの融合スコアを掛ける。次に、ベクトル和を求め、このベクトル和を融合重みの合計に対して標準化する。その結果、物体の前の位置と新たな位置との間の差が得られる。
【０１０８】
本発明を好ましい実施形態の例として説明してきたが、本発明の精神及び範囲内で様々な他の適応及び変更を行ってもよいことが理解される。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲に入るそのような変形及び変更をすべて網羅することである。
【０１０９】
付録
アルゴリズム  マルチカーネル平均値シフト
入力：前フレームで位置ｚ０にあるターゲット及び｛ｃｉ｝ｉ＝１．．ｌを中心とする連結成分
【０１１０】
【数１４】
2008535038.tif 000016
【図面の簡単な説明】
【０１１１】
【図１】本発明による、低フレームレートで取得された映像中の物体を追跡するシステムのブロック図である。
【図２】本発明による、低フレームレートで取得された映像中の物体を追跡する方法の流れ図である。
【図１】
2008535038.tif 000017
【図２】
2008535038.tif 000018
【国際調査報告】
2008535038.tif 000019