(57)【要約】  本発明は、それぞれのマッチング特徴のスケーリングと分散を考慮に入れる、ビデオフレーム内でオブジェクトを追跡するためのオブジェクトトラッキング方法及びシステムを提供する。これは、オブジェクト間の一致を決定するために可能な限り多くのマッチング特徴を使用することができ、このようにして決定されるマッチングの精度を高めることを確実にする一方で、マッチング特徴の選択でのある程度の自由度に備える。オブジェクト間の閉塞を考慮に入れるために並列マッチング手法が使用され、発見的規則が利用される。【選択図】      図１
2007510994.tif 000002
【特許請求の範囲】
【請求項１】
ビデオ画像のシーケンスの中でオブジェクトを追跡する方法であって、
前記シーケンスの過去のビデオ画像の中で検出されたオブジェクトに関係するオブジェクトモデルを記憶する段階であって、前記オブジェクトモデルが前記検出されたオブジェクトの特性の値とそれらの値の分散とを備える段階と、
処理される前記シーケンスの追加のビデオ画像を受信する段階と、
前記受信されたビデオ画像の中のオブジェクトを検出する段階と、
前記検出されたオブジェクトの特性を決定する段階と、
前記特性の少なくとも前記分散を考慮に入れる距離関数を使用して前記それぞれの特性に基づいて各検出されたオブジェクトと各オブジェクトモデルの間の距離測度を計算する段階と、
前記計算された距離測度に基づいて前記オブジェクトモデルに前記検出されたオブジェクトをマッチングする段階と、
前記オブジェクトモデルを、それにマッチングされた前記それぞれの検出されたオブジェクトの特性を使用して更新する段階と、
を備える、方法。
【請求項２】
前記距離測度はスケーリングされたユークリッド距離である、請求項１に記載の方法。
【請求項３】
前記距離関数はオブジェクトモデルｌと検出されたオブジェクトｋについて
【数１】
2007510994.tif 000019
の形を取り、ここではｘｌｉとｙｋｉがそれぞれ記憶されているオブジェクトモデルと検出されたオブジェクトの特性の値であり、σ２ｌｉが各特徴の前記分散の対応する成分であり、前記指数ｉがオブジェクトモデルのＮ個の特徴を通る、請求項２に記載の方法。
【請求項４】
前記距離測度はマハラノビスの距離である、請求項１に記載の方法。
【請求項５】
前記受信されたフレームのための記憶されているオブジェクトモデルの前記特性の値を予測する段階とをさらに備え、前記計算する段階は前記オブジェクトモジュールからの前記特徴値として前記特性の前記予測値を使用する、請求項１乃至請求項４のいずれか１項に記載の方法。
【請求項６】
オブジェクトモデルが検出されたオブジェクトにマッチングされない場合に、そのオブジェクトの特性値の分散が増加する、請求項１乃至請求項５のいずれか１項に記載の方法。
【請求項７】
オブジェクトモデルが前記受信された画像の中の検出されたオブジェクトにマッチングされない場合、前記更新段階が所定数の過去の画像で同じオブジェクトについて検出されたそれぞれの個別の値の平均で前記特性値を更新することを備える、請求項１乃至請求項６のいずれか１項に記載の方法。
【請求項８】
オブジェクトモデルが前記受信された画像の中の検出されたオブジェクトにマッチングされない場合、前記オブジェクトが別のオブジェクトと重複するかどうかを判断するために試験が実行され、重複が検出されるとオブジェクトが閉塞していると見なされる、請求項１乃至請求項７のいずれか１項に記載の方法。
【請求項９】
各オブジェクトが追跡される連続ビデオ画像の数をカウントする段階と、オブジェクトが所定数の連続フレームの間追跡されると、トラッキングが発生したことを示す追跡信号を出力する段階とをさらに備える、請求項１乃至請求項８のいずれか１項に記載の方法。
【請求項１０】
オブジェクトモデルが前記受信された画像内の検出されたオブジェクトにマッチングされない場合、オブジェクトモデルがマッチングされていない連続フレーム数のカウントが増分され、前記カウントが所定数を上回ると前記オブジェクトモデルを削除する段階をさらに備える、請求項の１乃至請求項９のいずれか１項に記載の方法。
【請求項１１】
検出されたオブジェクトがオブジェクトモデルにマッチングされない場合に、新しいオブジェクトモデルが前記検出されたオブジェクトに対応して記憶される、請求項１乃至請求項１０のいずれか１項に記載の方法。
【請求項１２】
コンピュータで実行時に、それ／それらによって前記コンピュータが請求項１乃至請求項１１のいずれか１項に従って動作するように構成される、コンピュータプログラムまたはコンピュータプログラムのセット。
【請求項１３】
請求項１２に記載のコンピュータプログラムまたはコンピュータプログラムのセットの少なくとも１つを記憶する、コンピュータ読み取り可能記憶媒体。
【請求項１４】
ビデオ画像のシーケンスの中でオブジェクトを追跡するためのシステムであって、
前記シーケンスの過去のビデオ画像で検出されるオブジェクトに関係するオブジェクトモデルを記憶するための記憶手段であって、前記オブジェクトモデルが前記検出されたオブジェクトの特性の値とそれらの値の分散を備える記憶手段と、
処理される前記シーケンスの追加のビデオ画像を受信するための手段と、
使用時に、
前記受信されたビデオ画像の中で１つまたは複数のオブジェクトを検出し、
前記検出されたオブジェクトの特性を決定し、
前記特性の少なくとも前記分散を考慮する距離関数を使用して前記それぞれの特性に基づいて各検出されたオブジェクトと各オブジェクトモデルの間の距離測度を計算し、
前記計算された距離測度に基づいて前記オブジェクトモデルに前記検出されたオブジェクトをマッチングし、
前記記憶されているオブジェクトモデルを、それにマッチングされた前記それぞれの検出されたオブジェクトの特性を使用して更新するように、
構成された処理手段と、
を備える、システム。
【請求項１５】
前記距離測度はスケーリングされたユークリッド距離である、請求項１４に記載のシステム。
【請求項１６】
前記距離関数は、オブジェクトモデルｌ及び検出されたオブジェクトｋについて
【数２】
2007510994.tif 000020
の形を取り、ここではｘｌｉとｙｋｉがそれぞれ記憶されているオブジェクトモデルと検出されたオブジェクトの前記特性の値であり、σ２ｌｉが各特徴の前記分散の対応する成分であり、前記指数ｉがオブジェクトモデルのＮ個の特徴を通る、請求項１５に記載のシステム。
【請求項１７】
前記距離測度はマハラノビスの距離である、請求項１４に記載のシステム。
【請求項１８】
前記受信されたフレームのための前記記憶されているオブジェクトモデルの前記特性の値を予測するための手段をさらに備え、前記処理手段は前記距離測度計算の中で前記オブジェクトモデルからの前記特徴値として前記特性の予測値を使用する、請求項１４乃至請求項１７のいずれか１項に記載のシステム。
【請求項１９】
オブジェクトモデルが検出されたオブジェクトにマッチングされない場合に、そのオブジェクトの前記特性値の前記分散が増加する、請求項１４乃至請求項１８のいずれか１項に記載のシステム。
【請求項２０】
オブジェクトモデルが前記受信された画像の中の検出されたオブジェクトにマッチングされない場合に、前記更新ステップが所定数の過去の画像の間前記同じオブジェクトについて検出されたそれぞれの個別の値の平均で前記特性値を更新することを備える、請求項１４乃至請求項１９のいずれか１項に記載のシステム。
【請求項２１】
オブジェクトモデルが前記受信された画像の中の検出されたオブジェクトにマッチングされない場合に、前記オブジェクトが別のオブジェクトと重複するかどうかを判断するために試験が実行され、重複が検出されると前記オブジェクトが閉塞されていると見なされる、請求項１４乃至請求項２０のいずれか１項に記載のシステム。
【請求項２２】
各オブジェクトが追跡される連続ビデオ画像の数をカウントするための手段と、オブジェクトが所定数の連続フレームの間追跡される場合にトラッキングが発生したことを示す追跡信号を出力するための手段とをさらに備える、請求項１４乃至請求項２１のいずれか１項に記載のシステム。
【請求項２３】
オブジェクトモデルが前記受信された画像の中の検出されたオブジェクトにマッチングされない場合に、前記オブジェクトモデルがマッチングされない連続フレーム数のカウントが増分され、前記システムは、前記カウントが所定数を超える場合に前記オブジェクトモデルを削除するための手段をさらに備える、請求項１４乃至請求項２２のいずれか１項に記載のシステム。
【請求項２４】
検出されたオブジェクトがオブジェクトモデルにマッチングされない場合に、新しいオブジェクトモデルが前記検出されたオブジェクトに対応して記憶される、請求項１４乃至請求項２３のいずれか１項に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はフレームごとにビデオ画像の中で検出されるオブジェクトを追跡する方法及びシステムに関する。
【背景技術】
【０００２】
自動ビデオトラッキングアプリケーションは当技術分野において公知である。一般的にこのようなアプリケーションはビデオフレームを入力として受信し、多くの場合バックグラウンド除去技法を使用して、移動するオブジェクト等の画像内の関心のあるオブジェクトを検出するために動作する。単一の入力フレーム内でオブジェクトを検出すると、このようなアプリケーションは、検出されたオブジェクトの特性を使用してフレームごとに検出されたオブジェクトを追跡するために動作する。将来の入力フレームでオブジェクトを検出し、前記検出されたオブジェクトの特性を決定することにより、前記決定された特性をマッチングして、トラックを生じさせるために過去に検出されたオブジェクトとの将来検出されるオブジェクトのマッチングが可能である。前記を表す例の従来の技術のトラッキングアプリケーションは、Ｚｈｏｕ  Ｑらの「ビデオから移動するオブジェクトを追跡し、分類すること」会議録、ＰＥＴＳに関する第２回ＩＥＥＥ国際ワークショップ、２００１年米国ハワイ、カウアイの中に説明されている。
【０００３】
しかしながら、特性を使用するマッチングは、他の特徴が雑音により影響を受けやすい一方、いくつかの特徴がオブジェクトに対してより永続的であるためにいくつかの問題を提起する。また、異なる特徴は通常異なる分散のある異なる範囲内で値をとる。ユークリッド距離マッチング測度は、距離測度を支配するためにより大きなスケールと分散を有する次元を可能にするであろうため、これらの要因を考慮しない。
【発明の開示】
【０００４】
本発明はそれぞれのマッチング特徴のスケーリングと分散を考慮に入れる、ビデオフレーム内でオブジェクトを追跡するためのオブジェクトトラッキング方法とシステムの提供により前記に対処する。これは、オブジェクト間で一致を決定するために可能な限り多くのマッチング特徴を使用することができ、このようにして決定されるマッチングの精度を高めることを確実にする一方で、マッチング特徴の選択である程度の自由度に備える。
【０００５】
前記を鑑みて、第１の態様から、本発明は、  
シーケンスの過去のビデオ画像で検出されたオブジェクトに関する１つまたは複数のオブジェクトモデルを記憶する段階であって、前記オブジェクトモデルが検出されたオブジェクトの特性の値とそれらの値の分散を備える段階と、  
処理されるシーケンスの追加のビデオ画像を受信する段階と、  
前記受信されたビデオ画像内で１または複数のオブジェクトを検出する段階と、  
前記検出されたオブジェクトの特性を決定する段階と、  
前記特性の少なくとも前記分散を考慮に入れる距離関数を使用して、前記それぞれの特性に基づいて各検出されたオブジェクトと各オブジェクトモデルの間で距離測度を計算する段階と、  
前記計算された距離測度に基づいて前記オブジェクトモデルに前記検出されたオブジェクトをマッチングする段階と、  
前記オブジェクトのトラックを提供するために、前記オブジェクトモデルを、それにマッチングされた前記それぞれの検出されたオブジェクトの特性を使用して更新する段階と、  
を備える、ビデオ画像のシーケンス内でオブジェクトを追跡するための方法を提供する。
【０００６】
特性の分散を考慮に入れる距離関数を使用することにより、他と比較されるときに前記一致する特性のいくつかのより大きなスケールと分散が補償されるため、一致を実行するために使用できるのと同じくらい多くの異なるマッチング特徴を使用する能力だけではなく、特徴の選択における柔軟度も与えられる。
【０００７】
好ましい実施形態では、距離測度はスケーリングされたユークリッド距離である。これは、リアルタイム演算に適したコンピュータ的に安価なプロセスにより高次元データを処理できるという利点を提供する。好ましくは、距離関数は、オブジェクトモデルｌと検出されたオブジェクトｋについて以下の形をとり、  
【数３】
2007510994.tif 000003
【０００８】
この場合指数ｉはオブジェクトモデルのＮ個の特徴すべてを通り、  
【数４】
2007510994.tif 000004
【０００９】
は各特長の分散の対応する成分である。
【００１０】
代替実施形態では、距離測度は、特徴のスケーリングと分散だけではなく、共分散行列に基づいた他の特徴の変分も考慮に入れるマハラノビスの距離である。したがって、相関する特徴がある場合、それらの寄与は適切に加重される。
【００１１】
好ましくは、受信されるフレームについて記憶されているオブジェクトモデルの特性の値を予測する段階がさらに含まれ、前記計算段階は特性の予測値をオブジェクトモデルからの特徴値として使用する。この入信フレームとともに使用するためのオブジェクトモデルごとに特性の値を予測するために予測を使用することにより、オブジェクトモデルの検出されたオブジェクトに対するマッチングの精度を高めることができる。
【００１２】
好ましい実施形態では、オブジェクトモデルが検出されたオブジェクトにマッチングされない場合、そのオブジェクトの特性値の分散が増加する。これは、それが追跡者が突然のまたは予想外の動きを経験する可能性がある失われたオブジェクトを回復するのを支援するという利点を提供する。
【００１３】
好ましくは、オブジェクトモデルが受信された画像の検出されたオブジェクトにマッチングされない場合、更新段階は特性値を所定数の過去の画像で同じオブジェクトについて検出されたそれぞれの個別の値の平均で更新することを備える。これはオブジェクトの再取得（re-acquiring）を容易にするために予測モデルを変更することにより予測誤差(errors)の場合の補償に備える。
【００１４】
さらに、好ましくはオブジェクトモデルが受信された画像の検出されたオブジェクトにマッチングされない場合、オブジェクトが別のオブジェクトと重なっていないかどうかを判断するために試験が実行され、重複が検出されるとオブジェクトは閉塞済みと見なされる。これは、最終的にはオブジェクトが失われたことを確認することにつながるであろうルーチンが開始される代わりに、オブジェクトが閉塞している場合には、追跡技法がこれをそのようなものとして認識し、オブジェクトトラックをただちに除去しないという点でオブジェクトのトラックにある程度の柔軟性を与える。
【００１５】
さらに、該方法は好ましくは、各オブジェクトが追跡される連続ビデオ画像数をカウントすることと、オブジェクトが所定数の連続フレームの間追跡されると追跡が発生したことを示す追跡信号を出力することとをさらに備える。これにより瞬間的なオブジェクトの動きを無視することができる。
【００１６】
さらに、オブジェクトモデルが受信された画像の検出されたオブジェクトにマッチングされない場合、好ましくはオブジェクトモデルがマッチングされない連続フレーム数のカウントが増分され、該方法は、前記カウントが所定数を超えるとオブジェクトモデルを削除することをさらに備える。これにより、背景と融合してしまった静止オブジェクト及び視界を離れてしまったオブジェクトを、このようなオブジェクトに関係する記憶されているオブジェクトモデルを取り除くことによって無視できるようにし、このようにして技法の計算効率を維持し、リアルタイム機能に貢献する。
【００１７】
最後に、検出されたオブジェクトがオブジェクトモデルにマッチングされない場合、好ましくは新しいオブジェクトモデルが検出されたオブジェクトに対応して記憶される。これにより、新しいオブジェクトは画像キャプチャ装置の視界に入り、以後追跡されることが可能になる。
【００１８】
第２の態様から、本発明は、  
シーケンスの過去のビデオ画像で検出されたオブジェクトに関係する、検出されたオブジェクトの特性の値とそれらの値の分散を備える１または複数のオブジェクトモデルを記憶するための記憶手段と、  
処理されるシーケンスの追加のビデオ画像を受信するための手段と、  
使用時に、  
受信されたビデオ画像の中の１または複数のオブジェクトを検出し、  
前記検出されたオブジェクトの特性を決定し、  
該特性の少なくとも分散を考慮に入れる距離関数を使用してそれぞれの特性に基づいて各検出されたオブジェクトと各オブジェクトモデルの間の距離測度を計算し、  
前記計算された距離測度に基づいてオブジェクトモデルに検出されたオブジェクトをマッチングし、  
記憶されたオブジェクトモデルを、それにマッチングされたそれぞれの検出されたオブジェクトの特性を使用して更新するように  
構成された、使用中の処理手段と、  
を備える、ビデオ画像のシーケンス内のオブジェクトを追跡するためのシステムも提供する。
【００１９】
第２の態様の中では、第１の態様に関して前述されたのと同じ利点と同じ追加の特徴と利点が得られる。
【００２０】
第３の態様から、本発明は、コンピュータシステム上での実行時に、プログラムまたはプログラムのセットにより前記コンピュータシステムが第１の態様の方法を実行するように構成されるコンピュータプログラムまたはプログラムのセットも提供する。さらに、追加の態様から、第３の態様に従ってコンピュータプログラムまたはプログラムのセットを記憶するコンピュータ読み取り可能記憶媒体も提供される。コンピュータ読み取り可能記憶媒体は、限定されない例として、磁気ディスク、ＤＶＤ、ソリッドステートメモリ、光ディスク、光磁気ディスク等のどれかのような当技術分野において公知の適切なデータ記憶装置または媒体であってよい。
【００２１】
本発明の追加の特徴及び利点は、例証としてのみ提示されているその実施形態の以下の説明から、及び添付図面を参照することにより明らかになるであろう
【発明を実施するための最良の形態】
【００２２】
本発明の実施形態は、ここで図及び示されている実施形態の動作の例に関して説明される。
【００２３】
図１は、本発明の実施形態を提供する例のシステムアーキテクチャを描く。さらに詳細には、本発明は概して入力された画像の中でオブジェクトを追跡するための画像処理技法に関するため、本発明はおもにコンピュータ上で実行されるソフトウェアとして具現化される。したがって、本発明のシステムアーキテクチャは、当技術分野において周知であるように汎用コンピュータ１６を備える。コンピュータ１６は、コンピュータによって生成される出力画像がユーザに表示されてよいディスプレイ２０を備え、さらにキーボード、マウス等の多様なユーザ入力装置１８を備えている。汎用コンピュータ１６は、プログラム、及び本発明の実施形態により生成されるデータが記憶されるハードディスク、メモリ、光ディスク等のデータ記憶媒体２２も備えている。出力インタフェース４０はさらにコンピュータ１６によって提供され出力インタフェース４０から、コンピュータによって画像内で追跡されるオブジェクトに関係するトラッキングデータが、このようなデータを利用してよい他の装置に出力されてよい。
【００２４】
データ記憶媒体２２上には、記憶されているオブジェクトモデル（テンプレート）に対応するデータ２４、入力画像に対応するデータ２８、及び画像データ、計算結果、及び本発明の動作中に中間記憶装置として使用される他のデータ構造または変数等の作業データに対応するデータ３０が記憶されている。さらに、データ記憶媒体２２には、制御プログラム３１、特徴抽出プログラム３２、マッチング距離計算プログラム３６、オブジェクト検出プログラム２６、オブジェクトモデル更新プログラム３４、及び予測フィルタプログラム３８等のプログラムの形をとる実行可能なプログラムコードが記憶されている。これらのプログラムのそれぞれの動作は後述される。
【００２５】
実施形態の動作を容易にするために、コンピュータ１６は、カメラ等の画像キャプチャ装置１２から画像を受信するように構成されている。画像キャプチャ装置１２はコンピュータ１６に直接的に接続されてよい、あるいは代わりにインターネット等のネットワークを介してコンピュータ１６に論理的に接続されてよい。画像キャプチャ装置１２は、オブジェクトが検出され、追跡されなければならない場面の連続ビデオ画像を提供するように構成され、前記ビデオ画像は、特定の輝度特性とクロミナンス特性を有するために特定の値を取るピクチャエレメント（ピクセル）から構成されている。画像キャプチャ装置１２から出力されるピクセルのために使用されるカラーモデルは、ＲＧＢ、ＹＵＶ等当技術分野において公知のものであってよい。
【００２６】
動作中、汎用コンピュータ１６はネットワークを介して、または直接的に画像キャプチャ装置１２から画像を受信し、受信された画像の中のオブジェクトを追跡するために受信された入力画像を処理するように制御プログラム３１の総合的な制御下でデータ記憶媒体２２に記憶されている多様なプログラムを実行する。本実施形態の動作のさらに詳細な説明は図２と図３に関してここで行われる。
【００２７】
図２に関して、ステップ２．２で新しいビデオ画像が画像キャプチャ装置１２から受信され、該装置から受信されるビデオシーケンスの一部を形成する。この説明のために、過去の画像が受信された、及びオブジェクトがその中で過去に検出され、追跡されたと仮定する。シーケンスの第１の画像が受信されるときの起動動作の簡単な説明が以下に示される。
【００２８】
ステップ２．２に続いて、実行される第１の処理は、関心のあるオブジェクト（おもに移動するオブジェクト）が入力画像内で検出される必要がある、「セグメンテーション」として一般的に知られているプロセスである。「人の集団を追跡すること（Ｔｒａｃｋｉｎｇ  Ｇｒｏｕｐｓ  ｏｆ  Ｐｅｏｐｌｅ）」、コンピュータビジョンと画像の理解、８０、４２−５６、２０００、ＭｃＫｅｎｎａらによって、あるいは「リアルタイムのロバストなバックグランド除去技法及び陰影検出のための統計的な手法（Ａ  Ｓｔａｔｉｓｔｉｃａｌ  Ａｐｐｒｏａｃｈ  ｆｏｒ  Ｒｅａｌ−ｔｉｍｅ  Ｒｏｂｕｓｔ  Ｂａｃｋｇｒｏｕｎｄ  Ｓｕｂｔｒａｃｔｉｏｎ  ａｎｄ  Ｓｈａｄｏｗ  Ｄｅｔｅｃｔｉｏｎ）」、ＩＥＥＥ  ＩＣＣＶ’９９  ＦＲＡＭＥ＿ＲＡＴＥワークショップでＨｏｒｐｒａｓｅｔらによって説明されているもの等のすでに公知のセグメンテーション手順が使用されてよい。しかしながら、代わりに、及び好ましくはこれとともに同時に出願され、英国出願第０３２６３７４．４号からの優先権を主張する本出願人の同時係属国際特許出願に説明されるようなオブジェクト検出技法も使用されてよい。どちらの技法が利用されようとも、ステップ２．４ではオブジェクト検出は、推定上個々のオブジェクトに属しているすべてのピクセルをそれぞれのブロブにリンクするためにオブジェクト検出プログラム２６によって実行される。
【００２９】
次に以下のステップの目的は、オブジェクトを表現するそれぞれのブロブを、検出されたオブジェクトの特徴ベクトルを時間的なテンプレート（オブジェクトモデル）と比較することにより場面内でのそれらの動きを通して時間的に追跡することである。オブジェクトテンプレートの内容は後述される。
【００３０】
本実施形態では、各検出されたオブジェクト（候補ブロブ）の速度、形状、及び色を説明する５つの重要な特徴の集合が使用されている。つまり、  
速度ｖ＝その中心軌跡（ｐｘ、ｐｙ）での（ｖｘ、ｖｙ）  
含まれているサイズ、またはピクセル数（ｓ）  
ブロブに最も適合する楕円（ｒ）の長軸対短軸の比率−楕円のこの比率はその境界ボックスの縦横比よりオブジェクトをよく記述する。  
楕円の主軸の向き（θ）及び  
ブロブの凝集ピクセルの色共分散行列の主要な固有ベクトルを使用する有力な色の表現（ｃｐ）
ステップ２．６では、特徴抽出プログラム３２が、前記に概略されたように、オブジェクトマッチング特性を検出するために動作する。つまり（ｐ’ｋｘ、ｐ’ｋｙ）を中心とするフレームｔ＋１の中の候補ブロブｋについて、特徴ベクトルＢｋ（ｔ＋１）＝（ｖ’ｋ、ｓ’ｋ、ｒ’ｋ、θ’ｋ、ｃ’ｐ）が検出される。それぞれの特徴ベクトルが本入力フレームｔ＋１の中の検出されたオブジェクトごとに求められることに留意せよ。候補ブロブｋの速度は、以下のように計算される。
【００３１】
ｖ’ｋ＝（ｐ’ｋｘ、ｐ’ｋｙ）Ｔ−（ｐ’ｌｘ、ｐ’ｌｙ）Ｔ
ｒとθを求めるための楕円の適合は、Ｆｉｔｚｇｉｂｂｏｎ，Ａ．Ｗ及びＦｉｓｈｅｒ，Ｒ．Ｂ．、「円錐フィッティングのバイヤーガイド（Ａ  ｂｕｙｅｒ’ｓ  ｇｕｉｄｅ  ｔｏ  ｃｏｎｉｃ  ｆｉｔｔｉｎｇ）」、会議録、第５回英国マシンビジョン会議、バーミンガム、５１３−５２２ページ（１９９５年）に説明されるように実行されてよい。ｃを求める方法の説明については、Ｚｈｏｕ  Ｑ．及びＡｇｇａｒｗａｌ，Ｊ．Ｋ．、「ビデオから移動するオブジェクトを追跡し、分類すること（Ｔｒａｃｋｉｎｇ  ａｎｄ  ｃｌａｓｓｉｆｙｉｎｇ  ｍｏｖｉｎｇ  ｏｂｊｅｃｔｓ  ｆｒｏｍ  ｖｉｄｅｏ）」、会議録、追跡と監視の性能評価に関する第２回ＩＥＥＥ国際ワークショップ（ＰＥＴＳ２００１年）、米国、ハワイ、カウアイ（２００１年１２月）を参照されたい。
【００３２】
検出されたオブジェクトの特徴ベクトルを計算すると、記憶されているオブジェクトテンプレートにより表現される追跡されているオブジェクトに検出されたオブジェクトをマッチングすることを開始できる。さらに詳細には、及び図３に図示されているように、入力画像により表現されている場面の中で過去に追跡されたことのある関心のある各オブジェクトは、永続的な特性の時間テンプレートによってモデリングされる。任意の時間ｔで、追跡されたオブジェクト／（ｐｌｘ、ｐｌｙ）を中心とするそれぞれに特徴のテンプレートを有する。
【００３３】
Ｍｌ（ｔ）＝（ｖｌ、ｓｌ、ｖｌ、θｌ、ｃｐ）
それらのオブジェクトモデル（またはテンプレート）は、オブジェクトモデル領域２４の中のデータ記憶媒体２２に記憶されている。
【００３４】
特徴ベクトルＢｋ（ｔ＋１）＝（ｖ’ｋ、ｓ’ｋ、ｒ’ｋ、θ’ｋ、ｃ’ｐ）と、（ｐ’ｋｘ、ｐ’ｋｙ）を中心とするフレームｔ＋１の中の候補ブロブｋを有するテンプレートＭｌをマッチングする前に、カルマンフィルタが、それぞれ  
【数５】
2007510994.tif 000005
【００３５】
のその新しい速度、サイズ、縦横比、向きを予測することによりテンプレートを更新するために使用される。ここでは、  
【数６】
2007510994.tif 000006
【００３６】
がすでに予測され、記憶されていると仮定される。さらに、記憶されているオブジェクトモデルも平均  
【数７】
2007510994.tif 000007
【００３７】
と分散ｖｌ（ｔ）ベクトルを含む。つまりこれらの値は、フレームｔ＋１の中の候補ブロブｋがテンプレートと一致することが判明すると必ず更新される。したがって、ステップ２．８で、入力画像内のあらゆる検出されたオブジェクトに関して記憶されているオブジェクトテンプレートごとにマッチング距離の順序付きリストを生成するＦＯＲ処理ループを開始するマッチング距離計算プログラム３６が起動される。さらに詳細には、ステップ２．８の第１の反復時に、最初に記憶されているオブジェクトテンプレートが選択され、その特徴ベクトルが取り出される。次に、ステップ２．１０では、あらゆる検出されたオブジェクトの特徴ベクトルを通るために動作する第２のネスト化されたＦＯＲ処理ループが開始され、ステップ２．１２に従って各集合を処理する。ステップ２．１２では、それぞれのマッチング特徴を比較することによって本オブジェクトテンプレートと処理されている本検出されたオブジェクトの間でマッチング距離値が計算されてその間のマッチング距離を求める。ステップ２．１２で適用されるマッチング関数の追加の詳細は次に示される。
【００３８】
明らかに、他が雑音の影響をより受けやすい一方、あるオブジェクトについていくつかの特徴はより永続的である。また、異なる特徴は通常異なる分散を有する異なる範囲内で値を取る。ユークリッド距離は、距離測度を支配するためにより大きなスケールと分散を有する次元を可能にするであろうため、これらの要因を考慮しない。
【００３９】
この問題に立ち向かう１つの方法は、特徴のスケーリングと分散だけではなく、共分散行列に基づく他の特徴の変分も考慮に入れるマハラノビスの距離メトリックを使用することである。したがって、相関する特徴がある場合、それらの貢献は適切に加重される。代替実施形態では、このような距離メトリックが利用されてよい。
【００４０】
しかしながら、高次元データでは、共分散行列は不可逆となる場合がある。さらに行列反転はコンピュータ的に高価なプロセスであり、リアルタイム演算に適していない。したがって本実施形態では、テンプレート  
【数８】
2007510994.tif 000008
【００４１】
と候補ブロブｋの間の、方程式（２）に示されているスケーリングされたユークリッド距離が採用される。異種データセットの場合、これが妥当な距離定義であり、  
【数９】
2007510994.tif 000009
【００４２】
ここでは、ｘｌｉとｙｋｉは、それぞれテンプレート  
【数１０】
2007510994.tif 000010
【００４３】
と特徴ベクトルＢｋのスカラー要素であり、  
【数１１】
2007510994.tif 000011
【００４４】
は分散ベクトルｖl（ｔ）の対応する成分であり、指数ｉはテンプレートのすべての特徴を通る。方程式（２）が特徴の間に相関がないケースでマハラノビスの距離によって出されるのと同じ結果であり、そのために共分散行列が対角行列になることに留意せよ。したがって、方程式（２）は、特徴が無相関であると仮定することによって簡略化を表現する。この公式化の１つの例外が色である。これは色距離  
【数１２】
2007510994.tif 000012
【００４５】
を計算し、（ｘｌｉ−ｙｋｉ）の代わりにこれを使用することにより処理される。対応する分散σｌｉは  
【数１３】
2007510994.tif 000013
【００４６】
の分散である。
【００４７】
ステップ２．１２に続いて、ステップ２．１４では、検出されたオブジェクトのすべてが処理されている本オブジェクトテンプレートと対照してマッチングされたかどうか、つまり内側ＦＯＲループが完了したかどうかの判断が実行される。マッチングされていない場合には、次に検出されたオブジェクトが選択され、内側ＦＯＲループが繰り返される。マッチングされた場合には、処理はＳ２．１６に進む。
【００４８】
ステップ２．１６ではこの処理の状態は、あらゆる検出されたオブジェクトを、現在処理中の記憶されているオブジェクトテンプレートにマッチングするマッチング距離のリストが得られたが、このリストが順序付けられておらず、距離測度値が妥当であるかどうかを判断するためにチェックもされていないということである。これに鑑みて、ステップ２．１６では、リスト中の距離値に閾値が適用され、閾値を上回るそれらの値はリストから取り除かれる。１０というＴＨＲ値が実際に機能することが判明したが、他の値も有効でなければならない。閾値化演算に続き、ステップ２．１８では、結果として生じる閾値化されたリストが、標準ソートルーチンを使用して距離値をマッチングすることにより順序付けられる。
【００４９】
次に、ステップ２．２０は記憶されているオブジェクトテンプレートのすべてが処理されたかどうか、つまり外側ＦＯＲループが終了したかどうかをチェックする。処理されていない場合、次のオブジェクトテンプレートが選択され、外側ＦＯＲループと内側ＦＯＲループが繰り返される。処理されている場合、処理はＳ．２．２２に進む。
【００５０】
処理のこの段階で、作業データ領域３０の中に、記憶されているオブジェクトモデルごとに１つマッチング距離のそれぞれの順序付きリストを記憶した。これらの順序付きリストを使用すると、記憶されているオブジェクトモデルに検出されたモデルをマッチングすることは可能であり、これは次に実行される。
【００５１】
さらに詳細には、ステップ２．２２では、順に、それぞれの記憶されているオブジェクトテンプレートに対して処理ステップを実行するために再び動作する第２のＦＯＲ処理ループが開始される。特に、ステップ２．２４で第１に、処理されているオブジェクトモデルが使用可能な一致を有するかどうかを判断するための評価が実行される。一致は、本オブジェクトモデルの順序付きリストの中の最低のマッチング距離値を与えた検出されたオブジェクトとなされる。過去に実行された閾値化ステップのために、本オブジェクトモデルの順序付きリストの中にマッチング距離値がない場合には一致は利用できない。
【００５２】
ステップ２．２４の評価が真で戻ると、つまりテンプレート予測  
【数１４】
2007510994.tif 000014
【００５３】
分散ベクトルｖｌ（ｔ）及びＢｋ（ｔ＋１）を手段として本オブジェクトｌがフレームｔ＋１の中の候補ブロブｋによってマッチングされると、処理はステップ２．２６に進み、本オブジェクトモデルＩのための更新が実行される。特に、本オブジェクトのためのオブジェクトテンプレートは、平均と分散  
【数１５】
2007510994.tif 000015
【００５４】
だけではなくＭ１（ｔ＋１）＝Ｂｋ（ｔ＋１）も得るためにオブジェクトモデル更新プログラム３４によって更新される。これらのベクトルは、オブジェクトがマッチングした最新の対応するＬ個のブロブ、またはＬ個のフレーム（例えばＬ＝５０）の時間ウィンドウを使用して計算される。追跡されているオブジェクトごとのテンプレートはそれぞれ次のフレームの中に（主要な色を除く）各特徴の予想値を予測する関連カルマンフィルタの集合を有する。ステップ２．２８では、オブジェクトモデルのためのカルマンフィルタＫＦｌ（ｔ）も、予測フィルタプログラム３８を使用してマッチングされた検出されたオブジェクトの値を入れることによって更新され、次の入力フレームと使用するためのオブジェクトモデルの特徴の予測値  
【数１６】
2007510994.tif 000016
【００５５】
が求められ、記憶される。さらに、ステップ２．３０では、オブジェクトが追跡されたフレーム数を表す「ＴＫ＿ｃｏｕｎｔｓ」カウンタ値が１で増分され、オブジェクトのトラックが前の数個のフレームで一時的に失われた場合に設定された可能性がある「ＭＳ＿ｃｏｕｎｔｓ」がステップ２．３２でゼロに設定される。次にＦＯＲループは、記憶されたオブジェクトテンプレートのすべてが処理されたかどうかに関する評価で終了し、処理されていた場合には、処理は（後述される）ステップ２．５６に進む。記憶されたオブジェクトテンプレートのすべてが処理されていなかった場合には、ｓ．２．２２のＦＯＲループが処理される次の記憶されたオブジェクトテンプレートで再開される。
【００５６】
ステップ２．２４に戻り、ここで、利用可能な一致があるかどうかの評価がマイナスを返すケースを考える。この場合、前述されたように、オブジェクトテンプレートの距離測度のリストに適用された閾値化のために、リスト内にはマッチング距離はない。つまり検出されたオブジェクトは閾値距離の中でオブジェクトテンプレートに一致しない。この場合、最初に処理はステップ２．３６の評価に進み、本オブジェクトテンプレートのためのＴＫ＿ｃｏｕｎｔｓが、それが、２０等の値を取ることがある所定の値ＭＩＮ＿ＳＥＥＮ未満であるかどうかを判断するために評価される。ＴＫ＿ｃｏｕｎｔｓがＭＩＮ＿ＳＥＥＮ未満である場合には、処理はステップ２．５４に進み、本オブジェクトテンプレートはオブジェクトモデル記憶装置２４から削除される。次に処理は、図上別のステップとして示されているが、現実には前述されたものと同一であるステップ２．３４に進む。ＭＩＮ＿ＳＥＥＮ閾値のこの使用は、瞬間的なオブジェクトの移動と、一時的にセグメント化されてよいが、事実上追跡される適切なオブジェクトに対応していないアーチファクトブロブを無視するためである。
【００５７】
ステップ２．３６の評価が、ＴＫ＿ｃｏｕｎｔｓがＭＩＮ＿ＳＥＥＮ閾値を超えることを示すと、ステップ２．３８で閉塞があるかどうかの試験が次に実行される。本実施形態では、オブジェクトが場面に入る／場面からである領域に関する特別な経験則は使用されない。オブジェクトは画像の真中でただ出現する、あるいは消えるだけであるため、位置の規則は必要ない。したがって閉塞を取り扱うためには、経験則の使用は必須である。結果として、実施形態の中で、オブジェクトが検出されたオブジェクトとの一致を見つけることができないたびに、ステップ２．３８で閉塞に関する試験が実行される。本オブジェクトの境界ボックスが何らかの他のオブジェクトの境界ボックスと重複する場合、ステップ２．４０で評価によって決定されるように、ステップ２．４２で両方のオブジェクトも「閉塞済み」と記される。次に処理は後述されるステップ２．４８に進む。
【００５８】
ステップ２．４０に戻ると、閉塞試験が重複する他のテンプレートがない、つまり本オブジェクトが閉塞していないことを示すと、オブジェクトのトラッキングが失われたという結果が出される。したがって、処理は、ある特定のオブジェクトモデルのトラッキングが成功しなかった入力フレームの数のカウントを保つためにＭＳ＿ｃｏｕｎｔｓカウンタが増分されるｓ．２．４８に進む。ステップ２．５０では、このカウントは、５等の値を取ってよい閾値ＭＡＸ＿ＬＯＳＴに比較される。この評価が、カウンタが閾値以上であると示すと、オブジェクトのトラッキングが回復できないほど失われたという結論が出されるため、処理は、前記に説明されたように本オブジェクトモデルが削除されるステップ２．５４に進む。
【００５９】
しかしながら、ステップ２．５０の評価が、カウンタがＭＡＸ＿ＬＯＳＴ未満であることを示すと、処理はステップ２．５２に進み、オブジェクトモデルの分散値が、方程式（３）に従って調整される。
【数１７】
2007510994.tif 000017
【００６０】
ここではδ＝０．０５が優れた選択である。分散のこの増加は、追跡者が予想外または突然の動きを経験した失われたオブジェクトを回復するのを支援する。
【００６１】
ステップ２．５２に続き、処理はステップ２．４４に進む。このステップ２．４４に、本オブジェクトモデルが閉塞されていると記されるステップ２．４２から到達できることにも留意せよ。マッチングの誤差(error)は単に予測誤差(error)のために発生する可能性があるため、ステップ２．４４では予測モデルは失われた追跡の考えられる回復を容易にするために変更される。したがって、ＭＡＸ＿ＬＯＳＴ期間内では、特徴のテンプレートを更新するためにカルマンフィルタは使用されず、代わりにステップ２．４４で、  
【数１８】
2007510994.tif 000018
【００６２】
のように記載する、特徴ごとに最後の５０の正しい予測の平均が使用される。さらに、オブジェクトが閉塞されていると記されると、同じ更新が実行される。これは、最後の数個のフレーム内の小さな異常な動きが除去されるため、閉塞されたオブジェクトが平均化されたテンプレート予測を使用してさらによく追跡されるためである。位置の予測も閉塞ブロブ内で制約される。
【００６３】
ステップ２．４４に続き、処理はすでに説明されたステップ２．３４の評価に進む。
【００６４】
いったんステップ２．３４の評価が、ｓ．２．２２で開始された処理ループに従ってあらゆるオブジェクトテンプレートが処理されたことを示すと、処理の現在の状態は、あらゆる記憶されてたオブジェクトモデルが、ＭＡＸ＿ＬＯＳＴ期間内以外にマッチングされていない、閉塞済みと記されている検出されたオブジェクトとマッチングされたか、あるいは（ＭＩＮ＿ＳＥＥＮ期間内で検出された一致なしのために、あるいはオブジェクトが再取得されることなく超えられたＭＡＸ＿ＬＯＳＴ期間のためのどちらかで）オブジェクトモデル記憶装置２４から削除されている。しかしながら、通常は現在のフレームの中で始めて画像場面内に表示されたばかりの新しいオブジェクトであるために、記憶されているオブジェクトモデルにマッチングされたことがない検出されたオブジェクトがまだ画像内にある可能性がある（例えば、側部から画像視界に歩いて入ってくる人物）。これらの不一致検出済みオブジェクトを考慮に入れるために、新しいオブジェクトモデルがインスタンス化され、オブジェクトモデル記憶装置に記憶されなければならない。
【００６５】
これを達成するために、（いったんそれが、あらゆるオブジェクトテンプレートがｓ．２．２２で開始した処理ループに従って処理されたことを示すと）ステップ２．３４に続いて、処理はステップ２．５６に進み、追加のＦＯＲ処理ループが開始され、今回は検出されたオブジェクトを処理する。処理ループ内では、実行される第１のステップは、処理中の本検出済みオブジェクトがオブジェクトモデルにマッチングされたかどうかをチェックする評価であるステップ２．５８のものである。これが当てはまると、つまり本オブジェクトがマッチングされた場合には、検出されたオブジェクトに新しいオブジェクトモデルを作成する必要はないため、処理はステップ２．６２に進む。ステップ２．６２はステップ２．５６で開始したＦＯＲループによってすべての検出されたオブジェクトが処理されたかどうかを判断し、処理されなかった場合には次に検出されたオブジェクトを処理するために処理をステップ２．５６に戻す、あるいはすべての検出されたオブジェクトが処理されている場合はＦＯＲを終了する。
【００６６】
しかしながら、本検出されたオブジェクトが記憶されているオブジェクトモデルとマッチングされなかった場合、新しいオブジェクトモデルがステップ２．６０でインスタンス化され、記憶されなければならず、検出されたオブジェクトの特徴値をその初期値として取る。つまり、フレームｔ＋１内の本検出されたオブジェクトｋの場合、新しいオブジェクトテンプレートＭｋ（ｔ＋１）がＢｋ（ｔ＋１）から作成される。新しいオブジェクトのための初期の分散ベクトルｖｋ（ｔ＋１）の選択はある程度の検討を必要とするが、適切な値はすでに場面内にある非常に類似したオブジェクトからコピーできる、あるいは設計のオプションとして正しく追跡されるオブジェクトの従来の統計的な分析によって得られる典型的な値から取ることができるかのどちらかである。新しいオブジェクトモデルはオブジェクトモデル記憶装置２４に記憶されるため、次の入力画像が受信されると、突き合わせるために使用できる。
【００６７】
ステップ２．６０に続き、ステップ２．６２のループ評価が前述されたように実行され、いったん検出されたオブジェクトのすべてがループによって処理されると、処理はステップ２．６４に進むことができる。処理のこの段階で、記憶されているオブジェクトモデルのすべてが、ＭＡＸ＿ＬＯＳＴ期間内に閉塞または失われた、あるいは削除されたと記された検出されたオブジェクトにマッチングされ、検出されたオブジェクトのすべては記憶されているオブジェクトモデルにマッチングされたか、あるいはその点で作成された新しいオブジェクトモデルを有していた。したがって、この時点で、検出されたオブジェクトと記憶されているオブジェクトモデルの間で検出された一致を示す、及び画像内で追跡されたオブジェクトの位置を示すトラッキングデータを出力することが可能である。したがって、ステップ２．６４では、ＴＫ＿ｃｏｕｎｔｓカウンタがＭＩＮ＿ＳＥＥＮ閾値を上回る記憶されているオブジェクトテンプレートごとに検出された一致を示すトラッキング出力が提供される。前述されたように、ＭＩＮ＿ＳＥＥＮ閾値を使用すると、あらゆる短い瞬間的なオブジェクト移動を無視できるようになり、実際のオブジェクトに対応しないアーチファクトの一時的にセグメント化されたブロブも補償される。さらに、確かめたように、ＭＩＮ＿ＳＥＥＮ期間内にそれらが関係するオブジェクトのトラッキングが失われる（つまり、オブジェクトモデルがマッチングされない）と、オブジェクトモデルは削除される。もちろん、起動時には、記憶されているテンプレートはない。したがって、当初、検出されるすべてのオブジェクトは新しいオブジェクトであり、新しいテンプレートを作成するために図２（ｂ）に従って処理される。
【００６８】
実施形態の中では、図４と図５に示されているように、出力トラッキング情報が、画像の中のそれぞれの追跡されるオブジェクトの回りに目に見える境界ボックスを置くために画像を操作するために使用される。図４と図５は、時間的に分離されている約４０フレームであるビデオシーケンスからの２つのフレームである（図５が後のフレームである）。これらの画像内では、オブジェクト参照番号を備えた境界ボックスが追跡されたオブジェクトの回りに置かれたことがわかり、図４を図５に比較することにより、場面の中のオブジェクトが、それらが（各画像内で同じ参照番号を有する各オブジェクトの回りの境界ボックスによってここで示されている）場面全体で移動するにつれて追跡されることが分かる。さらに、図５は、オブジェクト９５６として追跡される人の集団がオブジェクト７８７として追跡されるトラックによって閉塞されるが、各オブジェクトが依然として無事に追跡されているときに閉塞を処理する本発明の実施形態の能力を描いている。
【００６９】
画像上に可視出力を提供することにより、オブジェクトが追跡されていることを単に示すだけではなく、本実施形態によって提供されるトラッキング情報も、オブジェクト分類アプリケーション等の追加のアプリケーションで利用されてよい。さらに、トラッキング情報は、それを利用してよい他のシステムにコンピュータ１６（図１を参照されたい）のトラッキング出力４０で出力されてよい。例えば、トラッキング情報は、オブジェクトが移動するときに装置が画像の中のある特定のオブジェクトに向けられたままであることを確実にするために、カメラや武器等の装置を制御するための装置ポインティングシステムに対する入力として使用されてよい。トラッキング情報の他の使用は当業者に明らかになるであろう。
【００７０】
文脈上明らかに他の意味に解すべきではない場合、説明全体及び請求項では、ワード「備える」「備えている」等は排他的または包括的な意味とは対照的に含めた意味で解釈されなければならない。つまり、「含むが、限定されない」の意味である。
【図面の簡単な説明】
【００７１】
【図１】本発明によるコンピュータシステムを描くシステムブロック図である。
【図２（ａ）】本発明の実施形態のトラッキング方法及びシステムの動作を描く流れ図である。
【図２（ｂ）】本発明の実施形態のトラッキング方法及びシステムの動作を描く流れ図である。
【図３】本発明の実施形態で使用される検出されたオブジェクトブロブにマッチングされているオブジェクトテンプレートの概念を描く図である。
【図４】本発明の実施形態により実行されるトラッキングを示すビデオシーケンスのフレームである。
【図５】本発明により実行されるオブジェクトのトラッキングを再び描く、図４のフレームを含むビデオシーケンスの後のフレームである。
【図１】
2007510994.tif 000021
【図２（ａ）】
2007510994.tif 000022
【図２（ｂ）】
2007510994.tif 000023
【図３】
2007510994.tif 000024
【図４】
2007510994.tif 000025
【図５】
2007510994.tif 000026
【国際調査報告】
2007510994.tif 000027
2007510994.tif 000028