(57)【要約】【課題】複数のターゲット（１０２）の分散型追跡のための方法およびシステム（２００）を提供する。【解決手段】複数のトラッカ（５０２）によって追跡されるべき複数のターゲット（１０２）が、あるフレーム（２０４）内で検知される。その複数のトラッカ（５０２）の各トラッカの動き状態変数が、変分期待値最大化アルゴリズムのＥステップで計算される。さらに、その複数のトラッカ（５０２）の各トラッカのデータ関連付け変数（３０２）が、そのアルゴリズムのＭステップで計算される。その動き状態変数、およびそのデータ関連付け変数（３０２）に応じて、その複数のターゲット（１０２）が、追跡される。【選択図】図２
2009003919.tif 000002
【特許請求の範囲】
【請求項１】
監視システムにおける変分ＥＭ（期待値最大化）アルゴリズムを使用した複数のターゲット（１０２）の分散型追跡のための方法であって、前記監視システムは、前記複数のターゲット（１０２）を追跡する複数のトラッカ（５０２）を含み、前記方法は、
前記変分ＥＭアルゴリズムのＥステップで実行される、前記複数のトラッカ（５０２）の各トラッカの動き状態変数を推定するステップ（６０４）と、
前記変分ＥＭアルゴリズムのＭステップで実行される、前記複数のトラッカ（５０２）の各トラッカのデータ関連付け変数（３０２）を、グラフベースの離散最適化アルゴリズムに基づいて推定するステップ（６０６）と、
前記複数のトラッカ（５０２）の各トラッカの前記動き状態変数および前記データ関連付け変数（３０２）に基づいて、前記複数のターゲット（１０２）を追跡するステップ（６０８）とを含む方法。
【請求項２】
前記複数のターゲット（１０２）を追跡するように前記複数のトラッカ（５０２）を初期設定するステップ（７０８）をさらに含み、前記複数のトラッカ（５０２）と前記複数のターゲット（１０２）の間の関連付けは、１対１マッピングに基づく請求項１記載の方法。
【請求項３】
前記複数のトラッカ（５０２）の各トラッカの前記動き状態変数は、前記変分ＥＭアルゴリズムの前記Ｅステップで、確率分散関数として推定される請求項１記載の方法。
【請求項４】
前記複数のトラッカ（５０２）の各トラッカの前記データ関連付け変数（３０２）は、前記変分ＥＭアルゴリズムの前記Ｍステップで、ＭＡＰ（最大事後）推定値として推定される請求項１記載の方法。
【請求項５】
前記変分ＥＭアルゴリズムの前記Ｅステップおよび前記Ｍステップは、所定の回数繰り返されて、前記動き状態変数および前記データ関連付け変数（３０２）の値を事前定義された範囲内に収束させる請求項１記載の方法。
【請求項６】
監視システムにおける変分ＥＭ（期待値最大化）アルゴリズムを使用した複数のターゲット（１０２）の分散型追跡のための分散型追跡システム（２００）であって、
動き状態変数およびデータ関連付け変数（３０２）にそれぞれが関連付けられる、前記複数のターゲット（１０２）を追跡するための複数のトラッカ（５０２）を含む追跡モジュール（２１２）を含み、
前記複数のトラッカ（５０２）の各トラッカは、前記変分ＥＭアルゴリズムのＥステップで、前記動き状態変数を推定し、
前記複数のトラッカ（５０２）の各トラッカは、グラフベースの離散最適化定式に基づいてデータ関連付け変数（３０２）を推定し、前記推定は、前記変分ＥＭアルゴリズムのＭステップで実行されるシステム（２００）。
【請求項７】
前記追跡モジュール（２１２）は、前記複数のターゲット（１０２）を追跡するように前記複数のトラッカ（５０２）を初期設定し、前記複数のトラッカ（５０２）と前記複数のターゲット（１０２）の間の関連付けは、１対１マッピングに基づく請求項６記載の分散型追跡システム（２００）。
【請求項８】
前記複数のトラッカ（５０２）の各トラッカの前記動き状態変数は、前記変分ＥＭアルゴリズムの前記Ｅステップで、確率分散関数として推定される請求項６記載の分散型追跡システム（２００）。
【請求項９】
前記複数のトラッカ（５０２）の各トラッカの前記データ関連付け変数（３０２）は、前記変分ＥＭアルゴリズムの前記Ｍステップで、ＭＡＰ（最大事後）推定値として推定される請求項６記載の分散型追跡システム（２００）。
【請求項１０】
前記変分ＥＭアルゴリズムの前記Ｅステップおよび前記Ｍステップは、所定の回数繰り返されて、前記動き状態変数および前記データ関連付け変数（３０２）の値を事前定義された範囲内に収束させる請求項６記載の分散型追跡システム（２００）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して複数ターゲット追跡に関し、より詳細には、監視システムにおいて複数のターゲットを追跡するための方法およびシステムに関する。
【背景技術】
【０００２】
本出願は、参照によって全体が本明細書に組み込まれている、２００７年４月２０日に出願した米国仮出願第６０／９１２９４５号の利益を主張する。
【０００３】
複数のターゲットを追跡することは、例えば、ビデオ監視、交通モニタリング、人間活動分析、スポーツビデオ分析などの、多くのアプリケーションにおいて重要である。ターゲットの位置を追跡することに加え、ターゲットの速度、スケールなどの、ターゲットの他の特性が、追跡されることも可能である。ターゲットの追跡の分析は、ターゲットの将来の経路の予測を可能にして、適切な措置がとられることが可能であるようにする。例えば、空港などの混雑した区域における人間活動を追跡することは、普通でない活動が、検知されることが可能であるとともに、可能な損害が防止されることが可能であるようにするのに、重要である。
【０００４】
外見が異なるターゲットを追跡するのは、複数の独立した単独ターゲットトラッカを使用して、それらのターゲットを追跡することができるので、より容易である。そのような状況において、ある特定のターゲット以外のすべてのターゲットは、それらのターゲットの異なる外見のため、背景として見られることが可能である。しかし、混雑した空間における人々などの、外見が似通っている複数のターゲットを追跡することは、困難である。複数ターゲット追跡は、単独ターゲット追跡とは根本的に異なり、検知された測定値を個別の各データ源に分け、保持されるトラッカとの、それらのデータ源の対応を確立する複雑なデータ関連付け論理を要求する。このことは、複数ターゲット追跡アルゴリズムの成功を決定する２つの重要なプロセス、すなわち、基本的に２つのインタリーブされた特性であるトラッカ測定値関連付けと、トラッカフィルタリングとを含意する。さらに、そのような複数ターゲット追跡は、単独ターゲット追跡に関連する他の問題に加え、ターゲット遮蔽に対処しなければならない。つまり、ターゲットは、他の物体によって遮蔽されている、または遮断されていても、認識され、追跡されなければならない。
【０００５】
この問題に対処する一般的なアプローチは、結合関連付けベクトルという一元化された表現をとり、この表現が、次に、ＪＰＤＡ（結合確率的データ関連付け）フィルタなどの網羅的列挙によって、または確率的モンテカルロ最適化によって推定される。しかし、これらの方法では、関与する計算の複雑さが、特に、大量の追跡および測定データが扱われる必要がある場合、途方もなく大きい。また、結合尤度関数をモデル化して、これにより、すべてのターゲットの複合状態を直接的に推定するサンプリングベースのアプローチも、提案されている。データ関連付けを明示的に計算することに頼ることなしに、これらのサンプリングベースのアプローチは、複雑な動きが存在する場合に、複数のターゲットを追跡する能力を示す。しかし、結合状態表現の一元化された性質のため、これらのアプローチの複雑さは、追跡されるターゲットの数が増えるにつれ、指数関数的に増加する。
【非特許文献１】TING YU, YING WU, NILS O. KRAHNSTOEVER, PETER H. TU, “Distributed Data Association and Filtering for Multiple Target Tracking”, TO APPEAR IN IEEE CONF. ON COMPUTER VISION AND PATTERN RECOGNITION, 2008, 9 Pages
【発明の開示】
【発明が解決しようとする課題】
【０００６】
以上の説明に鑑みて、複数のターゲットを追跡することに関して、計算上の複雑さをより小さくする方法の必要性が、存在する。
【課題を解決するための手段】
【０００７】
本発明の例示的な実施形態は、変分ＥＭ（期待値最大化）アルゴリズムを使用する、監視システムにおける複数のターゲットの分散型追跡のための方法およびシステムを提供する。受信される、それぞれの連続するフレームに関して、検知モジュールが、受信されたフレームの中の複数のターゲットを検知し、それらの検知を追跡モジュールに供給する。追跡モジュールは、複数のトラッカを含む。各トラッカは、変分ＥＭアルゴリズムのＥステップで、そのトラッカ独自の動き状態変数を計算する。さらに、各トラッカは、変分ＥＭアルゴリズムのＭステップで、複数のターゲット検知の１つで、そのトラッカのデータ関連付け変数を計算する。分散型追跡システムは、複数のトラッカのデータ関連付け変数の値に制約を課して、不合理なデータ関連付けを防止する。計算された動き状態変数およびデータ関連付け変数に基づき、各トラッカは、そのトラッカに対応するターゲットを追跡する。
【０００８】
本発明の別の例示的な実施形態は、独自の動き状態変数およびデータ関連付け変数を計算することができるトラッカを提供する。各トラッカは、変分ＥＭアルゴリズムのＥステップで、そのトラッカ独自の動き状態変数を計算する。さらに、各トラッカは、変分ＥＭアルゴリズムのＭステップで、そのトラッカを、複数のターゲットの１つに関連付けるデータ関連付け変数を計算し、そのトラッカの計算されたデータ関連付け変数と関係する情報を、分散型追跡システムにおける他のトラッカに提供する。計算された動き状態変数およびデータ関連付け変数に基づき、各トラッカは、そのトラッカに対応するターゲットを追跡する。さらに、各トラッカは、その他のトラッカから受信された情報に基づき、そのトラッカ独自のデータ関連付け変数を更新し、あるターゲットが、物体によって、または別のターゲットによって部分的に遮蔽されている場合でも、そのターゲットを追跡することができる。
【０００９】
これら、およびその他の利点および特徴は、添付の図面に関連して提供される本発明の好ましい実施形態の以下の詳細な説明から、より容易に理解されよう。
【発明を実施するための最良の形態】
【００１０】
本発明の様々な実施形態は、複数のターゲットの分散型追跡のための方法およびシステムを提供する。変分ＥＭ（期待値最大化）アルゴリズムを使用して、複数のトラッカの動き状態変数およびデータ関連付け変数が計算される。複数のトラッカは、計算された動き状態変数およびデータ関連付け変数に基づき、それらのトラッカに対応するターゲットを追跡する。
【００１１】
図１は、本発明の実施形態が実施されることが可能な環境１００を示す。環境１００は、３つのターゲット１０２ａ、１０２ｂ、および１０２ｃ、ならびにディスプレイ１０４を含む。ディスプレイ１０４は、ディスプレイ１０４のスクリーン上で、継続的に追跡されているターゲットを表示する。ディスプレイ１０４は、空港などの混雑した区域において使用されることが可能であり、したがって、空港における人間活動が、追跡されることが可能であり、普通でない活動が、検知されることが可能である。ディスプレイ１０４上で表示されるビデオイメージは、人間のオペレータによって監視されることが可能であり、かつ／または人間のオペレータによって後に精査されることが可能である。また、そのようなビデオイメージは、自動化されたシステムによって監視されて、これにより、人間の労力を節約し、検知率を向上させることも可能である。図１は、３つだけのターゲットが、追跡され、ディスプレイ上に表示されているのを示しているが、任意の適切な数のターゲットが、追跡され、ディスプレイ上で表示されることが可能である。さらに、いくつかのディスプレイが使用されて、複数ターゲット追跡を円滑にすることも可能である。
【００１２】
図２は、本発明の実施形態による複数ターゲット追跡のためのシステム２００を示すブロック図である。システム２００は、入力モジュール２０２、フレーム２０４、検知−追跡モジュール２０６、およびディスプレイ２０８を含む。検知−追跡モジュール２０６は、検知モジュール２１０および追跡モジュール２１２を含む。入力モジュール２０２は、検知−追跡モジュール２０６にフレーム２０４を供給する。検知−追跡モジュール２０６は、変分期待値最大化アルゴリズムを使用することにより、フレーム２０４の中に存在する複数のターゲットを検知し、追跡する。検知−追跡モジュール２０６は、追跡されている複数のターゲットを表示するディスプレイ２０８に検知−追跡モジュール２０６の出力を供給する。
【００１３】
本発明の様々な実施形態によれば、入力モジュール２０２は、通常のＣＣＴＶビデオ源、または他の任意のビデオ源であることが可能である。フレーム２０４は、追跡される必要がある複数のターゲットを含む。このため、追跡されているターゲットは、フレーム２０４のシーケンスとして受信される。フレーム２０４は、ピクセルを含み、各ピクセルは、明るさ、コントラスト、色などの様々な特性を有することが可能である。ディスプレイ２０８は、追跡されているターゲットを表示することができる任意のスクリーンであることが可能である。
【００１４】
検知モジュール２１０が、フレーム２０４内のターゲットを検知する。検知モジュール２１０は、当技術分野でよく知られている技術によって、それらのターゲットを検知することができる。追跡モジュール２１２が、複数のターゲットが検知された後に初期設定される複数のトラッカを使用することにより、複数のターゲットを追跡する。複数のターゲットは、変分ＥＭアルゴリズムを反復的に使用することにより、複数のトラッカによって追跡される。特に、受信されるフレームごとに、その複数のターゲットが検知され、各トラッカが、変分ＥＭアルゴリズムを使用して、次のフレームに関して、そのトラッカに対応するターゲットの位置を予測し、そのトラッカに対応するターゲットを追跡する。その複数のターゲットのそれぞれが、ディスプレイ２０８上で長方形の領域内に示されることが可能である。その複数のターゲットを追跡する正確なプロセスは、後段で詳細に説明される。
【００１５】
入力モジュール２０２から受信された現在のフレームｔにおいて、測定値が、検知モジュール２１０によって検知され、これらの測定値が、Ｚｔによって表され、ただし、Ｚｔ＝｛ｚ１，ｔ，ｚ２，ｔ，．．．，ｚｍｔ，ｔ｝であるものと考慮されたい。各測定値は、現在のフレームｔにおいて検知されている異なるターゲットを参照する。全フレームセットにわたって収集された測定データは、Ｚｔによって示され、ただし、Ｚｔ＝｛Ｚ１，Ｚ２，．．．，Ｚｔ｝である。
【００１６】
本発明の様々な実施形態によれば、Ｍ個のトラッカが、分散された仕方で表され、ｉが、トラッカ識別子を表し、ｉ＝｛１，２，．．．，Ｍ｝である各トラッカｉが、推定されるべき未知の２つの変数｛ａｉ，ｔ，ｘｉ，ｔ｝を有する。つまり、すべてのトラッカｉが、ターゲットを正しく追跡するために算出される必要があるデータ関連付け変数ａｉ，ｔおよび動き状態変数ｘｉ，ｔに関連するものと考えられる。ａｉ，ｔは、トラッカｉのデータ関連付け変数を表し、離散セット｛０，１，．．．，ｍｔ｝からの値をとることができる。このため、トラッカｉは、トラッカｉを、Ｚｔからの可能なすべての測定値
【００１７】
【数１】
2009003919.tif 000003
に関連付けること、またはトラッカｉを、何にも関連付けない、つまり、ａｉ，ｔ＝０であることが可能である。特に、ａｉ，ｔ＝０は、あるターゲットの検知が欠落していること、またはそのターゲットが、視界から消えていることを示す。同様に、ｘｉ，ｔは、トラッカｉの動き状態変数を表す。それぞれの特定のアプリケーションシナリオに応じて、ｘｉ，ｔは、ターゲットの位置、速度、スケールなどの、ターゲットの特性を記述することが可能である。Ｍ個のトラッカのデータ関連付け変数および動き状態変数は、ａｔ＝｛ａ１，ｔ，ａ２，ｔ，．．．，ａＭ，ｔ｝、ｘｔ＝｛ｘ１，ｔ，ｘ２，ｔ，．．．，ｘＭ，ｔ｝と表される。Ｍ個のトラッカのそれぞれには、ＩＤ（一意識別子）が割り当てられる。
【００１８】
基本的に、複数ターゲット追跡アルゴリズムは、｛ａｔ，ｘｔ｝の相当にインタリーブされている性質のため、複雑な計算能力を要求する事後確率ｐ（ｘｔ，ａｔ｜Ｚｔ）を推定するという問題を扱う。本発明の様々な実施形態によれば、周辺事後が、一方の変数にわたって推定され、他方の変数は、欠落したデータの定式化の下で隠れたものとして扱われる。さらに、複数ターゲット追跡問題は、変分ＥＭアルゴリズムを反復的に繰り返すことによって解かれる。
【００１９】
本発明の様々な実施形態によれば、トラッカの動き状態変数、つまり、ｘｔは、欠落した変数と見なされる。このことは、ＥＭ反復のＥステップにおいて、ｘｔにわたる確率分布の絶えず高まる推定値をもたらす。次に、Ｍステップにおいて、多分岐グラフカットアルゴリズムやｍａｘ−ｐｒｏｄｕｃｔ信念伝搬アルゴリズムなどのグラフベースの最適化技術によって最適化されることが可能な、データ関連付け変数ａｔのポイント推定値（最大事後）が、計算される。本発明は、Ｅステップの後に続くＭステップに関連して説明されてきたが、Ｍステップが、Ｅステップを実行するのに先立って実行されてもよいことは、明白である。この２つのステップが実行される順序は、ＥＭアルゴリズムの出力に影響しない。
【００２０】
したがって、複数ターゲット追跡問題は、以下のとおり、データ関連付け変数ａｔのＭＡＰ（最大事後）推定問題として定式化される。すなわち、
【００２１】
【数２】
2009003919.tif 000004
ただし、Ｅ（ａｔ）は、最大化される必要がある元の目的関数を表す。式（１）は、以下の形態で表されることも可能である。すなわち、
【００２２】
【数３】
2009003919.tif 000005
ジェンセンの不等式から、関数Ｑ（ｘｔ）が、以下のとおり、式（２）に導入され、
【００２３】
【数４】
2009003919.tif 000006
ただし、この等式は、最適な関連付けａｔ＊が、算出され、Ｑ（ｘｔ）＝ｐ（ａｔ＊，ｘｔ｜Ｚｔ）である場合に限り、成立する。元の目的関数Ｅ（ａｔ）を最大化することは、未知の２つの特性、ａｔおよびＱ（ｘｔ）にわたって下限関数
【００２４】
【数５】
2009003919.tif 000007
を反復的に最大化することによって達せられることが可能である。
【００２５】
原則として、Ｑ（ｘｔ）は、ｘｔにわたる任意の有効な確率分布として定義されることが可能であるものの、この事例において、Ｑ（ｘｔ）は、以下のとおり定義される。すなわち、
【００２６】
【数６】
2009003919.tif 000008
ただし、各部分Ｑｉ（ｘｉ，ｔ）により、未知の周辺確率ｐ（ｘｉ，ｔ｜Ｚｔ）が近似される。
【００２７】
式（３）から、下限関数
【００２８】
【数７】
2009003919.tif 000009
の最大化が、以下のとおり表現されることが可能である。すなわち、
【００２９】
【数８】
2009003919.tif 000010
ただし、Ｈ（Ｑ（ｘｔ））は、Ｑ（ｘｔ）のエントロピーであり、ｐ（Ｚｔ｜Ｚｔ−１）は、加算される定数である。連鎖法則をｐ（ａｔ，ｘｔ，Ｚｔ｜Ｚｔ−１）に適用して、
【００３０】
【数９】
2009003919.tif 000011
である。
【００３１】
マルコフ仮定を使用して、データ関連付け変数の事前確率ｐ（ａｔ｜ｘｔ，Ｚｔ−１）は、ｐ（ａｔ｜ｘｔ，Ｚｔ−１）＝ｐ（ａｔ｜ｘｔ）と単純化されることが可能であり、尤度モデルは、ｐ（Ｚｔ｜ａｔ，ｘｔ，Ｚｔ−１）＝ｐ（Ｚｔ｜ａｔ，ｘｔ）と単純化されることが可能である。次に、式（５）における下限関数の最大化が、以下のとおり表現されることが可能である。すなわち、
【００３２】
【数１０】
2009003919.tif 000012
このため、複数ターゲット追跡問題を解くのに、これら３つの分布、すなわち、予測確率ｐ（ｘｔ｜Ｚｔ−１）、データ関連付け変数の事前確率ｐ（ａｔ｜ｘｔ，Ｚｔ−１）、および尤度モデルｐ（Ｚｔ｜ａｔ，ｘｔ，Ｚｔ−１）のそれぞれが、モデル化される必要がある。
【００３３】
動き予測ｐ（ｘｔ｜Ｚｔ−１）：式（６）における項ｐ（ｘｔ｜Ｚｔ−１）は、トラッカの動き予測モデルであり、以下のとおり表現されることが可能であることを見て取ることができる。すなわち、
【００３４】
【数１１】
2009003919.tif 000013
この結合動き事後ｐ（ｘｔ−１｜Ｚｔ−１）は、周辺成分ｐ（ｘｉ，ｔ−１｜Ｚｔ−１）の積を介して、適切に近似されることが可能である。すなわち、
【００３５】
【数１２】
2009003919.tif 000014
フレームｔ−１からのトラッカｉに関する最適Ｑ関数、Ｑｉ＊（ｘｉ，ｔ−１）が、そのトラッカの動き事後ｐ（ｘｉ，ｔ−１｜Ｚｔ−１）の良好な近似であり、独立した力学モデルも使用し、ただし、
【００３６】
【数１３】
2009003919.tif 000015
であるものと想定して、結合動き予測モデルｐ（ｘｔ｜Ｚｔ−１）は、以下のとおり単純化されることが可能である。すなわち、
【００３７】
【数１４】
2009003919.tif 000016
関連付け事前ｐ（ａｔ｜ｘｔ）：関連付け事前ｐ（ａｔ｜ｘｔ）は、関連付け変数ａｔ＝｛ａ１，ｔ，ａ２，ｔ，．．．，ａＭ，ｔ｝の事前確率であり、図３に関連して説明される。
【００３８】
尤度モデルｐ（Ｚｔ｜ａｔ，ｘｔ）：尤度モデルｐ（Ｚｔ｜ａｔ，ｘｔ）は、（ａｔ，ｘｔ）を条件とする、測定データＺｔの結合尤度モデルである。さらに、
【００３９】
【数１５】
2009003919.tif 000017
である。ａｔが提供された場合、この結合尤度モデルは、いずれの測定データ
【００４０】
【数１６】
2009003919.tif 000018
が、各トラッカｘｉ，ｔから生成されるかが知られているので、因数分解されることが可能であり、つまり、
【００４１】
【数１７】
2009003919.tif 000019
である。
【００４２】
図３は、本発明の実施形態による複数のトラッカのペアワイズデータ関連付け制約を示す。図３は、すべて互いに論理的に結び付けられた関連付け変数３０２ａ、３０２ｂ、３０２ｃ、３０２ｄ、および３０２ｅを含む。動き状態変数ｘｔを条件として、ｐ（ａｔ｜ｘｔ）は、関連付け変数ａｔ＝｛ａ１，ｔ，ａ２，ｔ，．．．，ａＭ，ｔ｝の事前確率であり、この図に示されるとおり、完全に結合されているが、分散型のペアワイズグラフとして定式化されることが可能である。対応する確率モデルは、以下のとおり表現されることが可能である。すなわち、
【００４３】
【数１８】
2009003919.tif 000020
ただし、Ｅは、関連付け制約が導入された近隣トラッカのセットを表し、ψ（ａｉ，ｔ，ａｊ，ｔ｜ｘｔ）は、ａｉ，ｔとａｊ，ｔの間のペアワイズ制約である。Ｚｘｔは、ｐ（ａｔ｜ｘｔ）を適切な確率分布にするように導入される分配関数である。図３において、各円は、トラッカの関連付け変数を表し、それらの円を結び付ける辺は、ペアワイズ関連付け制約の存在を表す。｛ａ１（ｋ），ａ２（ｋ）｝間、および｛ａ３（ｋ），ａ４（ｋ），ａ５（ｋ）｝間のリンク辺は、これら２つのグループのそれぞれの中のトラッカが、互いに空間的により近いことを示すように太くされている。
【００４４】
本発明の実施形態によれば、ｐ（ａｔ｜ｘｔ）は、トラッカの動きｘｔとは独立であるものと想定される。このため、
【００４５】
【数１９】
2009003919.tif 000021
であり、ただし、
【００４６】
【数２０】
2009003919.tif 000022
である。
【００４７】
ａｉ，ｔとａｊ，ｔはともに、離散測定値セット｛０，１，．．．ｍｔ｝から値を選択することができる。
【００４８】
以上の説明から、動き予測ｐ（ｘｔ｜ｚｔ−１）、関連付け事前ｐ（ａｔ｜ｘｔ）、および尤度モデルｐ（Ｚｔ｜ａｔ，ｘｔ）はすべて、因数分解された形態、つまり、分散された形態をとることを見て取ることができる。さらに、式（７）は、以下のとおり書かれることが可能である。すなわち、
【００４９】
【数２１】
2009003919.tif 000023
このため、式（１５）によって示される問題のＥＭ解には、２つの反復ステップ、つまり、より良好なＱ’（ｘｔ）を計算する一方のステップと、より良好な関連付けａｔ’を見出す他方のステップとがかかわる。これら２つのステップ、つまり、ＥステップおよびＭステップは、対応するターゲットを追跡する各トラッカによって解かれ、図４に関連してさらに詳細に説明される。
【００５０】
図４は、本発明の様々な実施形態によるトラッカ４００のブロック図を示す。トラッカ４００は、Ｅステップ実行モジュール４０２、およびＭステップ実行モジュール４０４を含む。Ｅステップ実行モジュール４０２およびＭステップ実行モジュール４０４は、トラッカ４００の動き状態変数およびデータ関連付け変数をそれぞれ計算する。Ｅステップ実行モジュール４０２の出力が、Ｍステップ実行モジュール４０４の入力として与えられ、Ｍステップ実行モジュール４０４の出力が、Ｅステップ実行モジュール４０２の入力として与えられる。このため、これら２つのモジュールは、トラッカ４００において変分ＥＭアルゴリズムを実施する。
【００５１】
特に、Ｅステップ実行モジュール４０２は、トラッカの動きｘｔにわたる、より良好な
【００５２】
【数２２】
2009003919.tif 000024
を計算して、Ｅ（ａｔ，Ｑ（ｘｔ））を最大化する。さらに、Ｍステップ実行モジュール４０４は、より良好な関連付けａ’ｔ＝｛ａ’１，ｔ，ａ’２，ｔ，．．．，ａ’Ｍ，ｔ｝を見出して、Ｅ（ａｔ，Ｑ’（ｘｔ））を最大化する。
【００５３】
Ｅステップにおいて、Ｑｉ（ｘｉ，ｔ）にわたって式（１５）における目的の偏導関数がとられる。さらに、各Ｑｉ（ｘｉ，ｔ）が、有効な確率分布でなければならないという制約が、適用され、つまり、
【００５４】
【数２３】
2009003919.tif 000025
である。
【００５５】
この制約が、実施されることが可能であり、これにより、以下のとおり、各トラッカｉに関するＥステップ更新の式が与えられる。すなわち、
【００５６】
【数２４】
2009003919.tif 000026
この事例において、ｘｉ，ｔを選別するのに使用される測定データ
【００５７】
【数２５】
2009003919.tif 000027
は、後に続くＭステップから推定される関連付け変数ａｉ，ｔを条件とする。前述のＥステップ更新は、独立したＭ個の更新の式で構成され、ただし、各式は、個別のトラッカに関することを見て取ることができる。式（１０）における結合動き予測モデルｐ（ｘｔ｜Ｚｔ−１）、および式（１１）における尤度モデルｐ（Ｚｔ｜ａｔ、ｘｔ）が、ガウス性であるものと想定される場合、カルマンフィルタが直接に適用されて、式（１６）におけるＥステップが計算されることが可能である。
【００５８】
Ｍステップにおいて、Ｅステップからの既に更新済みのＱ’（ｘｔ）を所与として、関連付け変数ａｔ＝｛ａ１，ｔ，ａ２，ｔ，．．．，ａＭ，ｔ｝の更新されたセットが算出されて、目的が増加される。
【００５９】
【数２６】
2009003919.tif 000028
以下の２つの項が、定義される。すなわち、
【００６０】
【数２７】
2009003919.tif 000029
これらの式は、それぞれ、（ａｉ，ｔ，ａｊ，ｔ）およびａｉ，ｔの関数である。すると、式（１７）は、以下のとおり書かれることが可能である。すなわち、
【００６１】
【数２８】
2009003919.tif 000030
値｛ａ１，ｔ，ａ２，ｔ，．．．，ａＭ，ｔ｝は、離散値セットからであり、このため、ｆｉ，ｊ（ａｉ，ｔ，ａｊ，ｔ）とｇｉ（ａｉ，ｔ）はともに、Ｍステップ最適化より前に計算されることが可能である。式（１８）にかかわる積分計算は、Ｑｉ（ｘｉ，ｔ）がガウス性であるものと想定することにより、解析的に計算されることが可能である。さらに、式（１９）は、多分岐グラフカットアルゴリズム、ｍａｘ−ｐｒｏｄｕｃｔ信念伝搬などのアルゴリズムによって解かれることが可能である。ｍａｘ−ｐｒｏｄｕｃｔ  ＢＰ（信念伝搬）アルゴリズム、およびその変種は、これらのアルゴリズムの分散型で、並列の計算パラダイムを特徴とし、分散型計算をＭステップに分け与える。
【００６２】
本発明の実施形態によれば、あるターゲットが、部分的に遮蔽されている場合でも、そのターゲットを追跡するために、そのターゲットのＫ部分分解を考慮する。Ｋ部分検知器が、対応する部分の訓練データを収集することによってＫ個の部分を検知するように訓練される。ターゲットが、３つの部分、すなわち、頭−肩、胴、および足に分割される場合（Ｋ＝３）を考慮する。すると、トラッカのデータ関連付け変数は、Ｋ個の部分、すなわち、ａｉ，ｔ＝（ａｉ，１，ｔ，ａｉ，２，ｔ，．．．，ａｉ，Ｋ，ｔ）によって形成され、ただし、ｋ∈Ｋである各ａｉ，ｋ，ｔは、対応する部分検知器からの部分検知をトラッカｉに割り当てる関連付けを記述する。トラッカの動き状態変数は、ｘｉ，ｔである。ｘｉ，ｔおよびデータ関連付け変数ａｉ，ｔを条件として、尤度関数ｐ（ｚａｉ，ｔ，ｔ｜ｘｉ，ｔ）は、以下のとおり表現されることが可能である。すなわち、
【００６３】
【数２９】
2009003919.tif 000031
さらに、関連付け事前ｐ（ａｔ）は、以下のとおり表されることが可能である。すなわち、
【００６４】
【数３０】
2009003919.tif 000032
このため、Ｋ部分分解の事例では、Ｋグラフ最適化が実行されて、最適な部分関連付けａ’ｉ，ｔ＝（ａ’ｉ，１，ｔ，ａ’ｉ，２，ｔ，．．．，ａ’ｉ，Ｋ，ｔ）が同時に得られることが可能である。
【００６５】
本発明の別の実施形態によれば、トラッカｉは、３Ｄ（３次元）空間で使用されることが可能であり、各３Ｄトラッカの動き状態変数は、深度情報を含む。例えば、ｘｉ，ｔ＜ｘｊ，ｔは、トラッカｉの方が、トラッカｊよりもカメラに近いという動き仮説を表すものとし、戻される４つの検知、Ｚｔ＝｛ｚ１，ｔ，．．．，ｚ４，ｔ｝が存在するものとする。ｘｉ，ｔ＜ｘｊ，ｔを条件として、検知が、前部のトラッカｉの投影によって覆われているかどうかに応じて、この４つの検知が、Ｚｔ１＝｛ｚ１，ｔ，ｚ２，ｔ，ｚ３，ｔ｝とＺｔ２＝｛ｚ４，ｔ｝に分割される。この事例では、一般的な制約｛ａｉ，ｔ＝ａｊ，ｔ≠０｝に加えて、ａｊ，ｔ＝４を有するすべての構成は、動き仮説が、ｘｉ，ｔ＜ｘｊ，ｔであるので、許容できない。関与する非線形性のため、粒子フィルタが、トラッカを実行するのに使用されることが可能である。このため、変分確率Ｑｉ（ｘｉ，ｔ）が、重み付き粒子セットによって表されることが可能であり、前述したすべての積分計算は、代わりに合計によって表される。
【００６６】
すると、Ｅステップは、以下のとおり書かれることが可能である。すなわち、
【００６７】
【数３１】
2009003919.tif 000033
ただし、Ｑｉ（ｘｉ，ｔ）の更新は、近隣の各トラッカのＱｊ（ｘｊ，ｔ）を考慮に入れる。
【００６８】
しかし、Ｍステップ目的は、そのまま変わらず、ｆｉ，ｊ（ａｉ，ｔ，ａｊ，ｔ）を事前計算する仕方は、以下のとおり変更される。すなわち、
【００６９】
【数３２】
2009003919.tif 000034
ただし、ペアワイズトラッカの動き（ｘｉ，ｔ，ｘｊ，ｔ）にわたって評価される積分が、ｆｉ，ｊ（ａｉ，ｔ，ａｊ，ｔ）を事前計算するのに要求される。
【００７０】
図５Ａ、図５Ｂ、および図５Ｃは、本発明の様々な実施形態によるトラッカと、連続するフレームにおけるターゲットとの間の関連付けを示す図である。図５Ａは、あるフレームに適用された変分ＥＭアルゴリズムの出力であり、トラッカ５０２ａ、５０２ｂ、５０２ｃ、および５０２ｄを、フレーム内の、それらのトラッカに対応するターゲットとともに含む。トラッカは、正方形によって表されるのに対して、各ターゲットは、十字を中に有する円によって表される。図５Ａに示されるとおり、各トラッカは、ターゲットの後を追う。このため、トラッカ５０２ａ、５０２ｂ、５０２ｃ、および５０２ｄはそれぞれ、そのフレーム内に存在する異なるターゲットに関連付けられる。図５Ｂは、ビデオ監視カメラから受信された次のフレームを示す。図５Ｂから、ターゲットのそれぞれが、そのターゲットの以前の位置から移動していることを見て取ることができる。しかし、トラッカのそれぞれが、依然として、そのトラッカに対応するターゲットとの関連付けを維持している。図５Ｃは、図５Ｂに示されるフレームに変分ＥＭアルゴリズムを適用することの出力を示す。図示されるとおり、トラッカも、トラッカの以前の位置を離れており、トラッカに対応するターゲットの後を追っている。このプロセスは、ビデオ監視カメラから受信されるフレームごとに続けられる。
【００７１】
図６は、本発明の様々な実施形態による複数ターゲット追跡のための方法を示す流れ図である。ステップ６０２で、追跡されるべき複数のターゲットが、あるビデオフレーム内で検知される。その複数のターゲットの検知は、検知モジュールによって実行され、追跡モジュールに供給される。追跡モジュールは、複数のトラッカを含む。
【００７２】
ステップ６０４で、その複数のトラッカのそれぞれが、そのトラッカの動き状態変数を計算する。動き状態とは、ターゲットの位置、速度、スケールなどのターゲット特性のいずれかを指すことが可能である。動き状態変数は、変分ＥＭ（期待値最大化）アルゴリズムのＥステップで計算される。
【００７３】
ステップ６０６で、その複数のトラッカのそれぞれが、変分ＥＭアルゴリズムのＭステップで、そのトラッカのデータ関連付け変数を計算する。データ関連付け変数を計算する際、その複数のトラッカのそれぞれは、そのデータ関連付け変数の現在の推定値について、その他のトラッカにも知らせる。その他のトラッカは、受け取った情報に基づき、それらのトラッカのデータ関連付け変数を更新する。
【００７４】
ステップ６０８で、その複数のトラッカのそれぞれが、変分ＥＭアルゴリズムの助けを借りて、その所与のフレーム内の、そのトラッカに対応するターゲットを追跡する。
【００７５】
図７Ａおよび図７Ｂは、本発明の別の実施形態による複数ターゲット追跡のための方法を示す流れ図である。ステップ７０２で、トラッカのセットが、あるフレーム内で検知された複数のターゲットを追跡するように割り当てられる。ステップ７０４で、次のフレームが、受信される。
【００７６】
ステップ７０６で、その受信されたフレーム内に、関連付けられていない測定値が存在するかどうかが判定される。つまり、トラッカに関連付けられていないターゲットが、存在するかどうかが確認される。
【００７７】
ステップ７０８で、受信されたフレーム内に、関連付けられていない測定値が存在する場合、新たなトラッカが、一時的トラッカとして初期設定される。しかし、関連付けられていない測定値が、まったく検知されない場合、新たなトラッカは、初期設定されず、プロセスは、ステップ７１４に進む。
【００７８】
ステップ７１０で、一時的トラッカのデータ関連付けが、ある事前定義された数のフレームに関して有効であるかどうかが判定される。ステップ７１２で、データ関連付けが、有効であると判定された場合、一時的トラッカには、確立されたトラッカとしてマークが付けられる。しかし、データ関連付けが、有効ではない場合、ステップ７１８で、その一時的トラッカは、終了される。
【００７９】
ステップ７１４で、すべての確立されたトラッカに関して、選択された数のフレームに関して、そのトラッカに対応するターゲットとの有効なデータ関連付けが存在するかどうかが判定される。有効なデータ関連付けが存在する場合、プロセスは、ステップ７１６に進み、ターゲットは、継続的に追跡される。しかし、有効なデータ関連付けが、存在しない場合、ステップ７１８で、その確立されたトラッカは、終了される。
【００８０】
このように、本発明は、複数ターゲット追跡のための方法およびシステムを提供する。変分ＥＭ（期待値最大化）アルゴリズムを使用して、複数のトラッカの動き状態変数およびデータ関連付け変数が計算される。この複数のトラッカは、計算された動き状態変数およびデータ関連付け変数に基づき、これらのトラッカに対応するターゲットを追跡する。動き状態変数とデータ関連付け変数はともに、分散された仕方で計算され、そのため、計算の複雑さを小さくする。
【００８１】
コンピュータサイエンスの業者は、説明されるとおりに作成されたソフトウェアを、マイクロプロセッサなどの、適切な汎用または専用のコンピュータハードウェアと組み合わせて、本発明の実施形態を実施するコンピュータシステムまたはコンピュータサブシステムを作成することが、容易にできよう。本発明の実施形態による装置は、本発明の実施形態を含む、ソフトウェア、ファームウェア、ハードウェア、または以上の任意の組合せもしくはサブセットを含む、ＣＰＵ（中央処理装置）、メモリ、記憶デバイス、通信リンクおよび通信デバイス、サーバ、Ｉ／Ｏデバイスを含むが、以上には限定されない１つまたは複数の処理システム、あるいは１つまたは複数の処理システムの任意の部分構成要素であることが可能である。
【００８２】
本発明の実施形態のコンピュータプログラム製品は、コンピュータシステムに、本発明のイメージ選別方法を含むイメージを選別するための方法を実行させるために、コンピュータシステム上で実行可能である。コンピュータシステムは、マイクロプロセッサ、入力デバイス、ディスプレイ装置、ならびに、インターネット、またはイーサネット（商標）やイントラネットなどのネットワークに対するインターフェースを含む。マイクロプロセッサは、通信バスに接続される。また、コンピュータは、メモリも含む。メモリには、ＲＡＭ（ランダムアクセスメモリ）およびＲＯＭ（読み取り専用メモリ）が含まれることが可能である。コンピュータシステムは、記憶デバイスをさらに含む。記憶デバイスは、ハードディスクドライブ、またはフレキシブルディスクドライブ、光ディスクドライブなどの取り外し可能な記憶ドライブであることが可能である。記憶デバイスは、コンピュータプログラム、または他の命令をコンピュータシステムに読み込むための、他の類似した手段を含むことも可能である。コンピュータシステムは、通信装置も含む。通信装置は、コンピュータが、Ｉ／Ｏインターフェースを介して、他のデータベースおよびインターネットに接続することを可能にする。通信装置は、他のデータベースからのデータの転送および受信を可能にする。通信装置には、コンピュータシステムが、データベース、ならびにＬＡＮ、ＭＡＮ、ＷＡＮ、およびインターネットなどのネットワークに接続することを可能にするモデム、イーサネットカード（「イーサネット」は商標）、または任意の類似したデバイスが含まれることが可能である。コンピュータシステムは、Ｉ／Ｏインターフェースを介してシステムがアクセスすることができる、入力デバイスを介したユーザからの入力を円滑にする。また、様々なモジュールは、ハードウェア装置の形態であることも可能である。
【００８３】
コンピュータシステムは、１つまたは複数の記憶要素の中に格納されている命令セットを実行して、入力データを処理する。命令セットは、プログラム命令手段であることが可能である。また、記憶要素は、所望に応じて、データ、または他の情報を保持することもできる。記憶要素は、情報源、または処理装置内部に存在する物理的メモリ要素の形態であることが可能である。
【００８４】
命令セットは、本発明の方法の実施形態を構成するステップなどの特定のタスクを実行するよう、処理マシンに命令する様々なコマンドを含むことが可能である。命令セットは、ソフトウェアプログラムの形態であることが可能である。さらに、ソフトウェアは、別々のプログラムの集合、より大きいプログラムを有するプログラムモジュール、またはプログラムモジュールの一部分の形態であることが可能である。ソフトウェアは、オブジェクト指向プログラミングの形態のモジュラープログラミングを含むことも可能である。処理マシンによる入力データの処理は、ユーザコマンド、前の処理の結果、または別の処理マシンによって行われた要求に応答することが可能である。
【００８５】
本発明のいくつかの特徴だけが、本明細書で示され、説明されてきたが、多くの変形および変更が、当業者には思い浮かべられよう。したがって、添付の特許請求の範囲は、すべてのそのような変形および変更を、本発明の真の趣旨に含まれるものとして範囲に含むことを意図することを理解されたい。
【００８６】
本発明は、限られた数の実施形態だけに関連して詳細に説明されてきたが、本発明は、そのような開示された実施形態に限定されないことが、容易に理解されるはずである。むしろ、本発明は、以上に説明されていないが、本発明の趣旨および範囲に相応する任意の数の変種、代替、代用、または均等の構成を組み込むように変更されることが可能である。さらに、本発明の様々な実施形態が説明されてきたが、本発明の態様は、説明された実施形態のいくつかだけを含むことが可能であることを理解されたい。したがって、本発明は、以上の説明によって限定されると見なされるべきではなく、添付の特許請求の範囲だけによって限定される。
【図面の簡単な説明】
【００８７】
【図１】本発明の実施形態が実施されることが可能な環境を示す図である。
【図２】本発明の実施形態による複数ターゲット追跡のためのシステムを示すブロック図である。
【図３】本発明の実施形態による複数のトラッカのペアワイズデータ関連付け制約を示す図である。
【図４】本発明の様々な実施形態によるトラッカを示すブロック図である。
【図５Ａ】本発明の実施形態によるトラッカと、連続するフレームにおけるターゲットとの間の関連付けを示す図である。
【図５Ｂ】本発明の実施形態によるトラッカと、連続するフレームにおけるターゲットとの間の関連付けを示す図である。
【図５Ｃ】本発明の実施形態によるトラッカと、連続するフレームにおけるターゲットとの間の関連付けを示す図である。
【図６】本発明の実施形態による複数ターゲット追跡のための方法を示す流れ図である。
【図７Ａ】本発明の別の実施形態による複数ターゲット追跡のための方法を示す流れ図である。
【図７Ｂ】本発明の別の実施形態による複数ターゲット追跡のための方法を示す流れ図である。
【符号の説明】
【００８８】
１００  環境
１０２  ターゲット
１０４  ディスプレイ
２００  分散型追跡システム
２０２  入力モジュール
２０４  フレーム
２０６  検知−追跡モジュール
２０８  ディスプレイ
２１０  検知モジュール
２１２  追跡モジュール
３０２  関連付け変数
４００  トラッカ
４０２  Ｅステップ実行モジュール
４０４  Ｍステップ実行モジュール
５０２  トラッカ
６０２  ターゲットが、検知される
６０４  トラッカの動き状態が、計算される
６０６  トラッカのデータ関連付けが、計算される
６０８  検知されたターゲットが、追跡される
７０２  トラッカのセットが、割り当てられる
７０４  次のフレームが、受信される
７０６  関連付けられていない測定値が、特定される
７０８  新たなトラッカが、初期設定される
７１０  Ｍ個の連続するフレームに関する有効なデータ関連付けが、確認される
７１２  トラッカに、確立されたトラッカとしてマークが付けられる
７１４  Ｎ個の連続するフレームに関する有効なデータ関連付けが、確認される
７１６  検知されたターゲットが、追跡される
７１８  トラッカが、終了される
【図１】
2009003919.tif 000035
【図２】
2009003919.tif 000036
【図３】
2009003919.tif 000037
【図４】
2009003919.tif 000038
【図５Ａ】
2009003919.tif 000039
【図５Ｂ】
2009003919.tif 000040
【図５Ｃ】
2009003919.tif 000041
【図６】
2009003919.tif 000042
【図７Ａ】
2009003919.tif 000043
【図７Ｂ】
2009003919.tif 000044
【外国語明細書】
2009003919000001.pdf