(57)【要約】  ビデオ映像に撮像されている目標を追跡するための方法及びシステムが開示されている。目標は、例えば群集を通って移動する人物であってもよい。前記方法は、第１のフレーム内で目標を特定するステップと、前記目標の位置の周辺に画定されているテンプレート領域からサンプリングすることによってサブテンプレートの集団を生成するステップと、第２のフレーム内で前記目標の位置を突き止めるために前記第２のフレーム内のサブテンプレートのインスタンスを検索するステップとを備える。インスタンスが新しい目標位置に一致していないサブテンプレートは集団から削除され、新規にサンプリングされたサブテンプレートで置換される。そして、該方法は追加フレーム内で目標を検出するために反復できる。該方法はＣＣＴＶカメラ等のビデオ撮像手段と、該方法を実施するよう動作可能な処理手段とを備えるシステムで実施され得る。【選択図】      図１
2009512908.tif 000002
【特許請求の範囲】
【請求項１】
ビデオ映像の中に撮像されている目標を追跡する方法であって、
（ｉ）第１の画像フレーム内で追跡されるべき、第１の位置に位置している目標を特定するステップと、
（ｉｉ）前記第１の位置の周辺に画定される第１のテンプレート領域からサンプリングすることによってサブテンプレートの第１の集団を生成するステップと、
（ｉｉｉ）第２の画像フレーム内でサブテンプレートの前記第１の集団のそれぞれのインスタンスを検索し、前記第２の画像フレーム内の各インスタンスの位置を決定するステップと、
（ｉｖ）前記インスタンスの前記位置に応じて前記第２の画像フレーム内の目標の第２の位置を特定するステップと、
（ｖ）サブテンプレートの第１の集団の選択及び新しいサブテンプレートの集合を備えるサブテンプレートの第２の集団を生成するステップであって、該選択は、前記第２のフレーム内のサブテンプレートのそれぞれのインスタンスの位置に応じて選ばれ、該新しいサブテンプレート集合は、第２の位置の周辺に画定される第２のテンプレート領域からサンプリングすることによって生成されるものと、
（ｖｉ）サブテンプレートの前記第１の集団及び前記第１の位置の代りに、サブテンプレートの前記第２の集団、及び先行する反復から得られる前記第２の位置を使用して追加の画像フレームに関して前記ステップ（ｉｉｉ）から（ｖ）を反復し、それによって一連の目標位置を決定し、前記一連の目標位置から前記目標追跡を推測するステップと、を備える方法。
【請求項２】
前記ステップ（ｉｉｉ）は、前記第２の画像フレーム内のサブテンプレートの第１の集団のそれぞれに対する最適一致の位置を決定することを備える、請求項１に記載の方法。
【請求項３】
サブテンプレートの前記第２の集団を生成する前記ステップは、サブテンプレートの前記第１の集団のそれぞれに、重みを関連付けることを含み、該重みは前記第２の位置を基準にした前記第２のフレーム内の前記各サブテンプレートのインスタンスの位置に関連する、請求項１または２に記載の方法。
【請求項４】
各重みには、該重みに関連付けられたサブテンプレートの前記インスタンスが前記第２のテンプレート領域内に位置するのか、あるいは前記第２のテンプレート領域外に位置するのかに応じて、２つの値の内の１つが与えられる、請求項３に記載の方法。
【請求項５】
サブテンプレートの第１の集団の前記選択は、前記第２のテンプレート領域内にインスタンスを有するサブテンプレートを備える、請求項４に記載の方法。
【請求項６】
上限が、新しいサブテンプレートの前記集合の中のサブテンプレートの数に対して設定される、請求項１乃至請求項５のいずれか一項に記載の方法。
【請求項７】
前記上限は、サブテンプレートの前記第１の集団の中のサブテンプレートの数の５％と５０％の間の範囲内にある、請求項６に記載の方法。
【請求項８】
前記上限は、サブテンプレートの前記第１の集団の中のサブテンプレートの数の１５％と２５％の間の範囲内にある、請求項６または請求項７に記載の方法。
【請求項９】
前記上限は、サブテンプレートの前記第１の集団の中のサブテンプレートの数の２０％である、請求項６乃至請求項８のいずれか一項に記載の方法。
【請求項１０】
前記目標の第２の位置を特定する前記ステップは、許可されている領域を決定するステップと、該許可されている領域内にあるように前記第２の位置を制約するステップを備える、請求項１乃至請求項９のいずれか一項に記載の方法。
【請求項１１】
許可されている領域を決定する前記ステップは、最大目標速度を提供することと、該最大目標速度、前記第１の位置、及び前記第１の画像フレームと第２の画像フレームの間に経過した時間に応じて前記許可されている領域を決定することとを備える、請求項１０に記載の方法。
【請求項１２】
前記第１の画像フレームと第２の画像フレームの面積は、前記第１のテンプレート領域と第２のテンプレート領域の面積よりはるかに大きい、請求項１０または１１に記載の方法。
【請求項１３】
第２の位置を特定する前記ステップは、前記第２の画像フレーム内のサブテンプレートの前記第１の集団のインスタンスの前記位置に、クラスタ化プロセスを適用することを備える、請求項１乃至請求項１２のいずれか一項に記載の方法。
【請求項１４】
前記クラスタ化プロセスは、クラスタ関数をサブテンプレートの前記第１の集団のインスタンスの前記集団と畳み込むステップを備え、前記第２の位置は結果として生じる畳み込みが最高の値を有する位置である、請求項１３に記載の方法。
【請求項１５】
前記クラスタ関数は前記目標テンプレートにほぼ等しい形状を有する、請求項１４に記載の方法。
【請求項１６】
ビデオ映像の中に撮像されている目標を、添付図に関して実質的に本明細書に説明されるように追跡する方法。
【請求項１７】
ビデオ映像を生成するように動作可能な撮像手段と、請求項１乃至請求項１６のいずれか一項に記載の方法を実施するように動作可能な処理手段とを備える追跡システム。
【請求項１８】
コンピュータに差し込まれると、請求項１乃至請求項１７のいずれか一項に記載の方法を実施するよう動作可能なコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオ映像（例えばＣＣＴＶ映像）に撮像されている人間等の目標を追跡するための方法に関する。さらに詳細には、本方法は一連の画像フレームを通してゆっくり移動する目標の追跡を改善するためにシードされた（seeded）管理されていない（unsupervised）学習方法を使用することを備える。
【背景技術】
【０００２】
例えばニューラルネットワークの分野で、及び分類子の組み合わせの分野では、管理された（supervised）学習方法と管理されていない（unsupervised）学習方法の両方ともが公知である。管理された学習方法は、該学習方法の性能を高めるために、正解情報（ground truth）を使用して分類子を適応させる。管理されていない学習方法はトレーニングデータ組（training data set）の中の相関関係を検索する。管理されていない学習アルゴリズムの設計者は、アルゴリズムが学習しようとする構造の種類を決定することはできるが、何が学習されるのかを決定することはできない。何が学習されるのかは該データ組が決定する。例えば、遺伝的アルゴリズムは管理されていない学習方法であると考えられる。
【発明の開示】
【０００３】
学習方法は、ビデオ映像において撮像されている人間のような目標追跡の問題に適用されてきた。従来の公知の人追跡方法はテンプレート照合技法を含み、事前に学習でき、または目標が初めて検出される際、もしくは、目標が指定される際に取り込むことのできる初期のテンプレートが目標の位置を突き止めるために使用される。このような追跡システムは残念なことに信頼性が低く、目標が隠されるとき、（例えば、大通りに沿って歩いている人物が、手足が体に近い立位から、手足が体からはるかに遠く離れ得る歩行位置に形状を変化させるときのように）目標が形状を変えるとき、目標の外観が変わるとき、あるいは光の状態が変化するときにさえも失敗しやすい。さらに、このように現在公知の追跡システムは、特に群集を通って移動する目標を追跡しようとするときに、目標検出に失敗しやすい。
【０００４】
前述された問題のいくつかを克服する、あるいは少なくとも部分的に軽減することが本発明の目的である。繰り返し隠される場合があり、あるいは形状または概観を変えることがある目標をより良く追跡できる、ビデオ映像に撮像されている目標を追跡するための改善された方法を提供することが本発明の追加の目的である。
【０００５】
広義では、本発明は、弱い分類子の集団の維持、及び一貫性に基づいた重み付け関数に従って該集団の選択を反復して置換するという概念にある。分類子集団は、例えばビデオ映像から得られる各画像フレーム内で目標の位置を突き止めるために使用できる。重み付け関数は現在の目標位置と一致しない分類子の使用に対抗するように重みを付け、分類子を、現在の最適の解と一貫性がある可能性がより高い新しい分類子で置換しようとする。分類子はサブテンプレートとも呼ばれる場合がある。
【０００６】
本発明の第1の態様によると、ビデオ映像で撮像されている目標を追跡する方法が提供され、該方法は、  
（ｉ）第1の画像フレームで追跡されるべき、第1の位置に位置している目標を特定するステップと、  
（ｉｉ）前記第1の位置の周辺に画定される第1のテンプレート領域からサンプリングすることによってサブテンプレートの第1の集団を生成するステップと、  
（ｉｉｉ）第２の画像フレーム内でサブテンプレートの第1の集団のそれぞれのインスタンスを検索し、前記第２の画像フレーム内の各インスタンスの位置を決定するステップと、  
（ｉｖ）前記インスタンスの位置に応じて該第２の画像フレーム内の目標の第２の位置を特定するステップと、  
（ｖ）サブテンプレートの前記第１の集団の選択及び新しいサブテンプレートの集合を備えるサブテンプレートの第２の集団を生成するステップであって、該選択は、前記第２のフレーム内のサブテンプレートのそれぞれのインスタンスの位置に応じて選ばれ、新しいサブテンプレートの前記集合は、該第２の位置の周辺に画定されている第２のテンプレート領域からサンプリングすることにより生成されるものと、  
（ｖｉ）サブテンプレートの前記第１の集団及び前記第１の位置の代りに、サブテンプレートの前記第２の集団、及び先行する反復から得られる前記第２の位置を使用して、追加の画像フレームに関してステップ（ｉｉｉ）から（ｖ）を反復し、それによって一連の目標位置を決定し、前記一連の目標位置から目標追跡を推測するステップと、を備える。
【０００７】
有利なことに、上記の目標を追跡する方法は、該目標が繰り返し隠されることがある環境を通って移動する目標を追跡するように、及び移動の際に形状または外観を変えることがある目標を追跡するように動作可能である。したがって、該方法はＣＣＴＶ映像によって取り込まれ得るような、群集を通って移動する人間等の目標の追跡において適用例が見つけられることが期待できる。このような追跡は従来の公知の追跡システムで可能な追跡よりもさらに信頼性があり、リアルタイムで達成できる。該方法は、航空機によって取り込まれるビデオ映像で撮像され得るような車両等の目標の追跡にも適用例が見つけられることも期待できる。
【０００８】
第２の画像フレーム内でサブテンプレートの第１の集団のそれぞれのインスタンスを検索し、第２の画像フレーム内の各インスタンスの位置を決定するステップは、前記第２の画像フレーム内のこのようなテンプレートの前記第１の集団のそれぞれに対する最適の一致の位置を決定することを備えてもよい。該最適の一致は、例えば相関関係のようなプロセスを使用して決定してもよい。
【０００９】
サブテンプレートの第２の集団を生成するステップは、サブテンプレートの前記第１の集団のそれぞれに、重みを関連付けることを含んでもよく、該重みは前記第２の位置を基準にした前記第２のフレーム内の前記各サブテンプレートのインスタンスの位置に関連するものである。該重みには、該重みに関連付けられたサブテンプレートの前記インスタンスが前記第２のテンプレート領域内にあるのか、あるいは前前記第２のテンプレート領域の外にあるのかに応じて、２つの値の内の１つが与えられてもよい。他の重みつけの割り当ても考えられるが、有利なことにこのようなバイナリシステムは実現するのが簡略であり、該方法を実現するために必要とされる計算能力のレベルを引き下げる。
【００１０】
サブテンプレートの前記第１の集団の選択は、前記第２のテンプレート領域内にインスタンスを有するサブテンプレートを備えてもよい。したがって、第２の集団内に保持されているサブテンプレートの第１の集団の選択は、インスタンスが第２の位置と一致するようなサブテンプレートを備え、第２の位置と一致しないサブテンプレートの少なくともいくつかは廃棄される。
【００１１】
上限が、新しいサブテンプレートの集合の中のサブテンプレートの数に対して設定されてもよい。上限は、該方法が適用され得る所定の問題に対する実験によって決定できる。上限は、特に、システムが変化することが予想される速度、したがって解が変化することが予想される速度に依存する。つまり、解の高速進化が予想されるシステムの場合、大きな上限が設定される。前記上限はサブテンプレートの該前記第１の集団の中のサブテンプレートの前記数の５％と５０％の間の範囲内にあってもよい。さらに好ましくは、前記上限はサブテンプレートの前記第１の集団のサブテンプレートの数の１５％と２５％の間の範囲内にあってもよい。以下に詳しく説明されている一実施形態では、前記上限はサブテンプレートの前記第１の集団の中のサブテンプレートの数の２０％である。
【００１２】
前記目標の第２の位置を特定する前記ステップは、許可されている領域を決定するステップと、該許可されている領域内にあるように前記第２の位置を制約するステップを備えてもよい。許可されている領域を決定するステップは、最大目標速度を提供することと、該最大目標速度、該第１の位置、及び該第１の画像フレームと該第２の画像フレームの間に経過した時間に応じて前記許可されている領域を決定することとを備えてもよい。
【００１３】
前記第１の画像フレームと第２の画像フレームの面積は、前記第１のテンプレート領域と第２のテンプレート領域の面積よりはるかに大きくてもよい。この場合、有利なことに、サブテンプレートの検索は、目標があるように制約されている領域よりはるかに広い領域で実行できる。サブテンプレートのインスタンスに対する検索の範囲に、大きな背景領域を含むことによって、目標があることができない領域内に、最適の一致の位置があるような有効でないサブテンプレートを、サブテンプレートの集団から削除できることを保証することができる。
【００１４】
第２の位置を特定する前記ステップは、前記第２の画像フレーム内のサブテンプレートの前記第１の集団のインスタンスの位置に、クラスタ化プロセスを適用することを備えてもよい。前記クラスタ化プロセスはクラスタ関数をサブテンプレートの前記第１の集団のインスタンスの集団と畳み込むステップを備えてもよく、前記第２の位置は結果として生じる畳み込みが最高の値を有する位置である。前記クラスタ関数は前記目標テンプレートにほぼ等しい形状を有してもよい。
【００１５】
本発明の第２の態様によると、ビデオ映像を生成するように動作可能な撮像手段と、前述されたように目標を追跡する方法を実施するように動作可能な処理手段とを備える追跡システムが提供される。該撮像手段は、目標を追跡できるビデオ映像を提供するためにＣＣＴＶカメラを備えてもよい。
【００１６】
本発明の第３の態様によると、問題に対する解を決定する方法が提供され、該方法は、  
（ｉ）問題の初期のインスタンスに初期の解を提供するステップと、  
（ｉｉ）ディスクリミネータ（discriminator）のそれぞれが、該初期の解が与えられると、前記問題のインスタンスに対する解を計算するように動作可能なディスクリミネータの第１の集団を生成するステップと、  
（ｉｉｉ）該問題の第１のインスタンスに対する解の第１の集団を計算するよう、ディスクリミネータの第１の集団を動作するステップと、  
（ｉｖ）第１の集団解から最適の解を決定するステップと、  
（ｖ）ディスクリミネータの前記第１の集団の選択と、新規に生成されたディスクリミネータの集合とを備える、ディスクリミネータの第２の集団を生成するステップであって、該選択は、解の第１の集団と最適の解との間の差異に応じて選ばれるものと、  
（ｖｉ）前記初期の解とディスクリミネータの前記第１の集団の代わりに、最適の解と、先行する反復からのディスクリミネータの第２の集団を用いる、問題の追加のインスタンスに関して前記ステップ（ｉｉｉ）から（ｖ）を反復し、それにより該問題の追加のインスタンスに対する一連の最適の解を生成するステップと、を備える。
【００１７】
この方法は広範囲の問題に適用できる。該方法は、現在の最適の解を正解情報として使用できる任意の問題に適用でき、したがって正解情報の実際の測定が利用できない問題を解決するために特に有用である。該方法は、公知の、管理された学習方法及び管理されていない学習方法の両方ともと、根本的に異なっている。公知の管理された学習方法と対照的に、該方法の反復毎に正解情報が提供される必要はない。つまり便利なことに、正解情報は初期化のためにだけ提供される必要がある。公知の管理されていない学習方法と対照的に、該方法は、所定の基準に対してではなく推定された正解情報に対して適応する。有利なことに、該方法は自己適応し、問題のそれぞれの新しいインスタンスを解決することを目標としたディスクリミネータの適応集団を維持できる。
【００１８】
ディスクリミネータの第２の集団を生成する前記ステップは、ディスクリミネータの第１の集団のそれぞれに、重みを関連付けるステップを含み、ディスクリミネータの第１の集団のそれぞれの重みは、前記各ディスクリミネータによって計算される解と最適の解との差異に応じて決定されるものを備えてもよい。すると、前記選択はディスクリミネータの第１の集団のそれぞれと関連付けられる重みに応じて選ばれることができる。例えば、該重みは、バイナリ重みであってもよい。
【００１９】
最適の解を決定する前記ステップは、許可されている解空間を特定するステップを備えてもよい。最適の改を決定する前記ステップは、以後の解の集団にクラスタ化プロセスを適用することをさらに備えてもよい。
【００２０】
上限が、新規に生成されるディスクリミネータの集合の中のディスクリミネータの数に対して設定されてもよい。上限は、該方法が適用され得る所定の問題に対する実験によって決定できる。上限は、特に、システムが変化することが予想される速度、したがって解が変化することが予想される速度に依存する。つまり、解の高速進化が予想されるシステムの場合、大きな上限が設定される。本明細書に説明されているある特定の実施形態では、上限は該第１の集団の中のディスクリミネータの総数の２０％である。
【００２１】
有利なことに、解の第１の集団は、許可されている解空間より広い解空間で計算されてもよい。これはディスクリミネータの集団から質が悪いディスクリミネータを削除する明快な手段を提供する。つまり、ディスクリミネータが、不可能であると分かっている解を生成する場合に、該ディスクリミネータは、明らかにディスクリミネータの集団から削除されなければならないような質が悪いディスクリミネータである。これは、ディスクリミネータがさらに効率的に最良の解に達することができることを保証するためにも役立つ。
【００２２】
本発明は、コンピュータに差し込まれると、前述されたような方法を実施するよう動作可能なコンピュータプログラム製品に及ぶ。
【００２３】
本発明の前述の及び追加の特長は、特に添付請求項に詳細に述べられ、添付図面に図解されている多様な例示的な実施形態に関して、以下の記述において詳しく説明される。
【発明を実施するための最良の形態】
【００２４】
本発明は、本発明者によって開発された、問題を解決するための一般的なフレームワークを利用する。該フレームワーク方法は、問題の初期のインスタンスに初期の解を提供することにより開始され、その後、追加の入力無しに、該問題の以後のインスタンスに対する以後の解を決定することができる。該フレームワーク方法は、問題の現在のインスタンスに対する最良の解が正解情報(ground truth)の近似として扱える、あらゆる問題に適用でき、したがって正解情報の計測が不可能な場合に特に有用である。本発明者は、この一般的なフレームワークを自己適応判別（self-adapting discriminant, SAD）フィルタと名付けた。
【００２５】
ＳＡＤフィルタは、管理された学習方法と管理されていない学習方法との間のハイブリッドである。初期のシード（seed）の解に基づいて管理されていない学習が実施されるが、問題の将来のインスタンスに対する将来の解を生成するためには管理された教師あり学習手法が使用される。つまり、従前の反復により生成された解が、事実上、正解情報であると仮定される。したがって、ＳＡＤフィルタは管理された学習方法と管理されていない学習方法の両方と根本的に異なっている。本発明の追跡方法を説明する前に、追跡方法をさらに容易に理解できるように、特定されない問題に関してＳＡＤフィルタを説明する。
【００２６】
ＳＡＤフィルタ方法の一部として実行されるステップを描くフローチャート１００が図１に描かれている。フィルタは解決されるべき問題のインスタンス、及び該問題の該インスタンスに対する解を提供することによってステップ１１０で初期化される。この解が基点解(seed solution)として機能する。基点解、及び後に連続して続く将来の解が問題の後のインスタンスに対する解に制約を課し、その結果、許可される解空間が問題の将来のインスタンスごとに画定される。いったんこのようにして初期化されると、フィルタは操作者からの追加の入力なく同じ問題の将来のインスタンスに対する解を生成できることに留意すべきである。
【００２７】
問題の初期のインスタンスに対する初期の解が与えられると、問題の将来のインスタンスに解を提供できる、ディスクリミネータと呼ばれるアルゴリズムを生成することができる。これらのディスクリミネータは、該ディスクリミネータが、初期の問題に対する初期の解と一致する解を生じさせるように選ばれる。ディスクリミネータの第１の集団は、問題の初期のインスタンスに対する初期の解に基づいてステップ１２０で生成される。ディスクリミネータのこの第１の集団は、問題の第２のインスタンスに対する解の第１の集団を提供するためにステップ１３０で実行される。ディスクリミネータは、初期の解により課される制約によって規定される、許可されている解空間よりはるかに大きい問題空間上で実行される。このような大きい問題空間上でディスクリミネータを実行すると、（後述される）ステップ１４０で決定される最良の解と一致する適切なディスクリミネータを、より適切ではないディスクリミネータに優先して選択できることが確実になる。
【００２８】
ステップ１４０では、問題の第２のインスタンスに対する最良の解が、解の第１の集団から生成される。解の集団に対するクラスタ化が実効され、これにより最良の解が生成される。最良の解は、許可されている解空間内の最大のクラスタからの、平均として取得できる。クラスタ化方法は当業者には周知である。例えば、Ｋ−平均クラスタ化（K-means clustering）は、カリフォルニア大学出版、バークレーによって１９６７年に発行された、算数統計及び確率に関する第５回バークレーシンポジウムの会議記録（Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability）の第１巻の２８１ページから２９７ページに、論文「多変量観測の分類及び分析のための方法（Some Methods for Classification and Analysis of Multivariate Observations）」がＪ．Ｂ．ＭａｃＱｕｅｅｎによって開示されている。ステップ１４０で生成される最良の解は、問題の次のインスタンスのための正解情報となるように選ばれる。最良の解はステップ１５０で操作者に伝達される。
【００２９】
ステップ１７０では、多くのディスクリミネータの第１の集団が再生成される。ディスクリミネータの第１の集団のそれぞれには、ステップ１４０で決定された最良の解に対する、ディスクリミネータに関連付けられた解の近接性に応じて重みが与えられる。解空間において、最良の解に近い解を有するディスクリミネータに高い重みが与えられる。最良の解から遠く離れた解を有するディスクリミネータには低い重みが与えられる。保持されるべきものとして選択されるディスクリミネータは、最も高い重みが与えられたものであり、一方再生成されるべきものとして選択されるディスクリミネータは、最も低い重みが与えられたものである。したがって、最良の解から解が最も遠いディスクリミネータは廃棄され、新しいディスクリミネータの集合が該ディスクリミネータの代りに生成される。しかしながら、該方法のそれぞれの１回の反復で再生成できるディスクリミネータの第１の集団に対する割合の上限が適用される。
【００３０】
新しいディスクリミネータの該集合は、ステップ１２０で使用されるのと該同じ方法を使用して生成され、その結果ディスクリミネータの第２の集団が生成される。第２の集団は、ステップ１７０で再生成されるディスクリミネータを除き、第１の集団と同じであることが理解されなければならない。演算力が十分であれば、問題の第２のインスタンスに対してディスクリミネータの安定した集団が得られるまで、ステップ１３０、１４０、１６０及び１７０によって形成されるループを備えるディスクリミネータ再生成のプロセスを反復することが好ましい。しかしながら、問題のインスタンス同士の間で使用できる時間内にディスクリミネータの安定した集団に達するほど十分な演算力がない場合には、問題の、連続したインスタンスごとに単に一度該ループを実行してもよい。したがって、この方法は、初期化の後に操作者からの入力なしで問題の連続するインスタンスに対する連続する解を計算するために使用され得る。
【００３１】
前述されたＳＡＤフィルタを適用できる１つの特定の問題は、ＣＣＴＶ（クローズドサーキットテレビ）映像に取り込まれている目標を追跡するという問題である。典型的には、目標は大通りにいる人物、あるいは店舗にいる人物であってもよい。いったん特定の人物が目標として指定されると、解決されるべき問題は、本質的には該目標を再検出するという問題である。これは、高いフレームレート及び相対的に低い目標速度が、実際の目標追跡を行うという問題を、各フレームの検出インスタンスを結合するという問題にまで削減するためである。問題は当初簡単に見える可能性があるが、該問題は、実際には当初予想されたよりさらに複雑であることが判明することがある。目標が他の潜在的な目標によって繰り返し隠されたり、指定された目標に非常に類似して見える他の物体または人物が存在したりする可能性があるような、群集の中で移動する目標を再度検出する際には、特に困難である。
【００３２】
ＣＣＴＶ映像によって目標を追跡するための本発明の第１の実施形態の一部として実施されるステップは、図２に示されているフローチャート２００に示されている。フローチャート２００に描かれているステップは、図１に描かれているＳＡＤフィルタに関して説明され、これによりＳＡＤフィルタと目標追跡方法の関係性を明確に理解できる。明確にするために、図１に描かれているステップには数字「１」で始まる参照番号が与えられ、図２に描かれているステップには数字「２」で始まる参照番号が与えられていることに留意せよ。説明される方法は、固定カメラから取得されるビデオ映像に適用できる。目標は、例えば群集を通って移動する人物であってもよい。
【００３３】
図１に描かれているフローチャート１００に描かれている一般的な方法では、第１のステップは初期化のステップである。該初期化ステップでは、初期の解が問題の初期のインスタンスに与えられる。目標追跡問題の場合、ＳＡＤフィルタ初期化はステップ２１０と２２０で発生する。ステップ２１０は、初期フレーム内で、人物のような目標を識別することと、目標の位置を突き止めることとを備える。この初期のステップは人間の操作者によって実施できる。その結果、問題は以後の第２のフレーム内で該目標を再度検出し、該目標の位置を再度突き止めることである。ステップ２２０は、該目標のサイズを決定することと、テンプレート領域を画定することとを備える。テンプレート領域は目標にほぼ等しいサイズを有するように選ばれ、目標の中心に中心が置かれる。テンプレート領域の形状は便宜上選ばれる。本実施形態では、テンプレート領域は矩形となるように選ばれる。
【００３４】
一般的なＳＡＤフィルタ方法における第２のステップは、フローチャート１００のステップ１２０として描かれているディスクリミネータの第１の集団を生成するステップである。図２に示されているフローチャート２００内で描かれている追跡実施形態では、このステップはテンプレート領域内からサンプリングすることによってサブテンプレートの第１の集団を生成することを備える。サブテンプレートは、テンプレート領域内から無作為で選ばれる領域である。各サブテンプレートの面積はテンプレート領域の面積に比較して狭い。
【００３５】
本発明の第１の実施形態の性能は、生成されるサブテンプレートの数が増えるに従って高くなるが、大きな追加の計算負荷が犠牲となる。この改善は、目標のあらゆる有用な特長が少なくとも１つのテンプレートに含まれることがほぼ確実になるほど十分なサブテンプレートがあるまで続けられる。有用な特長とは、目標を局所的な背景から区別する特長であることは、当業者によって容易に理解されるだろう。したがって、サブテンプレートの第１の集団におけるサブテンプレートの最適数は、目標の大きさとサブテンプレートの大きさとの比率の問題だけではなく、画像の内容の関数でもある。十分な計算資源が与えられれば、範囲サイズ（range size）のあるサブテンプレートの非常に大きな集団が使用され得る。より大きな集団は、より大きな多様性を示すことが期待できるため、有用な特長を含む可能性がより高い。しかしながら、サブテンプレートを生成するランダム法を考慮すると、同一であるか、あるいは非常に類似している複数のサブテンプレートを生成する可能性がある。残念なことに、サブテンプレートの集団で高いレベルの多様性を維持しようとする人工的な試みは、現時点では性能の低下につながっている。したがって、サブテンプレートを生成するランダム法は、サブテンプレート集団の多様性の減少だけではなく増加にもつながることがあるため、このような人工的な多様性強化処置は使用されていない。目標が、ＣＣＴＶ映像で撮像されている群集を通って移動する人間である本実施形態では、テンプレート領域は１３０×１５ピクセルであり、それぞれの領域が４×４ピクセルである２０個のサブテンプレートは該テンプレート領域内からランダムにサンプリングされる。これらの量は約１５０，０００ピクセルという全体的な画像領域に比較されてもよい。明らかに、多様な領域のための実際の値は利用できる画像に強く依存し、所定のビデオ映像のための最適の値は試行錯誤のプロセスを使用して当業者によって容易に決めることができる。
【００３６】
一般的なＳＡＤ方法でのステップ１３０は、解の第１の集団を生成するためにディスクリミネータを実行するステップである。このステップは、ＳＡＤフィルタの追跡実現例において、第２のフレーム内のサブテンプレートのそれぞれに対する最適の一致を検索することと、該最適の一致の位置を突き止めることとを備えるステップ２４０に対応する。各サブテンプレートに対する該最適の一致の検索は、目標領域Ｓｔａｒｇｅｔよりはるかに大きい領域Ｓｗｉｄｅ上で実行される。例えば、領域Ｓｗｉｄｅは該第２のフレームの領域全体となるように選ばれてもよい。Ｓｔａｒｇｅｔよりはるかに広くなるようにＳｗｉｄｅを選ぶと、目標と背景を効果的に判別しないサブテンプレートを、効果的に判別するサブテンプレートから区別できることが保証される。つまり、効果的に判別しないサブテンプレートは、許可されている、狭い領域の外に最適の一致を有する可能性が高い。その結果、後述される適応更新ステップ２７０、２８０の間にサブテンプレートの第１の集団からこれらのサブテンプレートを容易に削除することができる。
【００３７】
相関関係のようなプロセスが、最適の一致の位置を決定するために使用される。サブテンプレートが第２のフレーム全体の候補位置を通して動かされ、候補位置ごとにスコアが計算される。本実施形態では、スコアは、候補位置での画像ピクセルに対するテンプレートピクセルの差異が閾値を超えているテンプレートピクセル数をカウントすることによって計算される。そして、スコアが最低となる候補位置が、サブテンプレートにとって最適の一致の位置であると解釈される。
【００３８】
一般的なＳＡＤ方法のステップ１４０は、最良の解を生成するために解の集団をクラスタ化するステップである。このステップは、ＳＡＤフィルタの追跡実現例におけるステップ２５０に対応し、第２のフレームで検出されるサブテンプレートの第１の集団のインスタンスをクラスタ化することと、許可されている領域Ｓｎａｒｒｏｗ内のテンプレート位置の最適のクラスタを選択し、新しい目標位置にすることとを備える。初期のフレームと第２のフレームの間で経過した時間量の知識と、考えられる最大の目標速度の推定値とを使用してＳｎａｒｒｏｗを決定することができる。
【００３９】
本実施形態で使用されているクラスタ化手順は、重み付けテンプレートを、ステップ２４０で計算されるテンプレート最適一致の位置の点分布と畳み込むことと、結果として得られる表面上で最高の値の点を取って新しい目標値とすることとを備える。重み付けテンプレートはほぼ目標の形状となり、目標中心に向かって最高になる。本実施形態では矩形の重み付けテンプレートが使用される。しかしながら、重み付けテンプレートの正確な詳細が追跡器（tracker）の性能に大きく影響を及ぼすものではないことと、所定の目標のための最適な重み付けテンプレートが実験によって容易に決定できることとに留意すべきである。最適なクラスタがＳｎａｒｒｏｗの範囲内にあるための要件が、初期のフレームと第２のフレームにおける目標位置の間の何らかの一貫性を保証することに、さらに留意すべきである。
【００４０】
新しい目標の位置は、次に正解情報として受け入れられ、一般的なＳＡＤフィルタリング方法のステップ１５０に対応するステップ２６０でユーザに伝達できる。そして、次のフレーム内で目標の位置を突き止めようと試みる前に、ステップ２７０と２８０で適応更新が実行される。適応更新は、新たに仮定される正解情報と一致していないサブテンプレートの少なくともいくつかを廃棄し、従前のテンプレート領域と同じ大きさであるが、新しい目標位置に中心が置かれる新しいテンプレート領域から再度サンプリングすることによって、サブテンプレートの新しい第２の集団を生成するために使用される。これは、ステップ２７０でサブテンプレートのそれぞれに重みを割り当て、次にステップ２８０で、選択されたサブテンプレートを再生成することによって、ＳＡＤフィルタの追跡実現例において達成される。サブテンプレートの第２の集団は、再生成されるサブテンプレートを除いて、サブテンプレートの第１の集団と同じであることに留意すべきである。
【００４１】
本実施形態では、ステップ２７０において、バイナリ重み付けが新しい目標位置を基準にして第２のフレーム内の各サブテンプレートの最適の一致インスタンスの位置に応じてサブテンプレートの第１の集団のそれぞれに割り当てられる。新しい目標位置に中心をおいたテンプレート領域に一致する領域Ｓｔａｒｇｅｔが画定される。重み付けは、第２のフレーム内のサブテンプレートのための最適の一致インスタンスが領域Ｓｔａｒｇｅｔの外にある場合にはゼロという値を、第２のフレーム内のサブテンプレートのための最適の一致インスタンスが領域Ｓｔａｒｇｅｔ内にある場合には単位値を有する。どの１回の反復でも再生成される最大割合はサブテンプレートの２０％である。ステップ２８０において、重み付けがゼロであるすべてのサブテンプレートは、サブテンプレート集団の２０％まで再生成される。重み付けがゼロであるサブテンプレートの割合が２０％を超える場合には、最大割合に対応する数のサブテンプレートが、重み付けがゼロであるサブテンプレートからランダムに選ばれる。新しいサブテンプレートは、新しい目標位置を中心にするテンプレート領域からランダムにサンプリングすることによって再生成されるが、画像ピクセルが初期のフレームを基準にして変化した第２のフレームの領域から、よりサンプリングするように小さな追加の重み付けがなされる。追加の重み付けは、生成されるサブテンプレートが目標上にあることの可能性を高める。
【００４２】
そして、方法は、追加のフレーム内でステップ２３０でのサブテンプレートの第２の集団を使用して反復される。この反復によって、ＣＣＴＶ映像全体で目標を追跡できる。ＳＡＤフィルタは、目標が移動するにつれて、サブテンプレートの集団が変化して、目標に適応するため、特に前述された人間追跡の適用例に特に適している。このようにしてサブテンプレートの集団は、目標と、考えられる偽の検出とを区別するのに理想的に適した集団に向かって連続的に適応する。
【００４３】
人間追跡のためにＳＡＤフィルタを使用することの利点及び優位点は、単純な例に関して容易に理解できる。第１のフレームで、赤いズボンと黒のトップを着用し、緑の草木を通って移動している人間が目標として選択されると、ステップ２３０で生成されるサブテンプレートの集団は主に赤の領域と黒の領域から構成される可能性が高い。赤いコートを着用した新しい人物が後のフレームに入ってくると、該赤のサブテンプレートの多くは該新しい人物の方を好み、Ｓｔａｒｇｅｔの外部でサブテンプレートの最適の一致を検出し、再生成される。この再生成プロセスは黒のサブテンプレートを好む。該新しい人物が目標の人物に接近し、最終的に領域Ｓｎａｒｒｏｗに入る可能性がある。しかしながら、新しい人物がＳｎａｒｒｏｗ内に存在するまでに、サブテンプレート集団は、赤のサブテンプレートよりもさらに多くの黒のサブテンプレートを含む。したがって、該新しい人物が追跡システムによって真の目標とする人間に間違えられる可能性は低くなる。平均−シフト色ヒストグラムアルゴリズム等の従来の公知の人間追跡アルゴリズムは、このシナリオでは失敗する可能性が非常に高い。赤のズボンと黒のトップを着用した追加の新しい人間が該目標の人間に接近すると、サブテンプレート集団のすべては再生成にオープンであろう。この場合、本発明の実施形態は失敗することも考えられるが、目標の人間の局所的な構造のいくつかの詳細は、このように検出の誤りと成り得るものを防げるほど十分なディスクリミネータであることが判明する可能性が高い。例えば、多くのサブテンプレートが目標のズボンとトップの間の赤−黒の境界の領域内にある場合には、該サブテンプレートは境界の形状の詳細を取り込んでいる場合があり、境界の形状の詳細は、目標の誤りとなり得るものから、実際の目標を区別するのに十分であると判明するであろう。
【００４４】
本発明の本実施形態は、駐車場、混雑した店舗及び混雑した通りを通ることを含む種々の状況でうまくいくことが示されてきた。すべてのこれらの状況では、従来の公知の人間追跡方法は急に失敗しがちである。対照的に、ＳＡＤフィルタ人間追跡器は、低解像度の像、及び繰り返され、ときどきは完全に目標が隠されるにも関わらず、所定の目標を追跡できる。さらに、これらの状況では追跡器が、目標が、追跡の最後には最初に指定された目標の外観と極めて異なって見える場合のように、外観を繰り返し変える場合にも無事に対処することが示されている。今までに実行されてきた試験のために、目標指定は、初期のフレームで目標中心点を手作業で選択することによって達成される。
【００４５】
前述された特定の実施形態はすべての点で例示的であることが理解されるべきである。変形及び改良が想定され、当業者にただちに自明になるであろう。例えば、前述では、人間が目標を指定することによって追跡を初期化することが説明されてきたが、自動的な目標指定がある状況では適切であることを当業者はただちに認識するであろう。このような自動指定は、目標を指定するために、ほぼ「人間の大きさの」ピクセル領域の変化を探す変更検出によって達成できるであろう。このような技法は、比較的整頓されている状況で目標を捉えることが可能である場合に適切であろう。他の状況では他の技法がさらに適切となり得る。さらに、２０％であると前述されたＳＡＤフィルタの該追跡実現例の、どの１回の反復でも再生成されるサブテンプレートの最大割合は、目標の環境、目標が隠される予想レベル、あるいは変化する照明条件に対する目標の予想される安定性に応じて変えられてもよい。サブテンプレート一致のための候補位置のスコアを計算するために使用される方法、及び新しい目標位置を計算するためにサブテンプレートの最適一致の位置をクラスタ化するために使用される方法の最適の選択肢は、本発明の特定の適用例に依存し、ケースバイケースで実験的に決定できる。候補位置に対するスコアは、例えば、前述されるように所定の閾値より大きな差異を有するセルの数のカウントではなく、対応するテンプレートと画像セルの間の総合的な差を決定するものであってもよい。同様に、サブテンプレート領域と、テンプレート領域と目標領域との相対的なサイズ、および各反復後に再生成されることが許されるサブテンプレート集団の最大の割合は、本発明の適用例に応じて変化する。これらのパラメータを、目標タイプ、背景、フレームレート、及び計算能力等の個々の項目に適するように調整することもできる。前述された追跡方法は、固定されていないカメラによって記録されるビデオ映像を通して目標が追跡されるように容易に修正することもできる。サブテンプレート再生成ステップ２８０において、変化したピクセルに与えられる追加の重み付けが削除できるか、あるいは、半固定（semi-static）カメラに適切であり得るように、使用された追加の重み付けを削減できるかのどちらかである。
【００４６】
最後に、任意の一実施形態に関して前述された任意の特長は、単独で、または説明された他の特長と組み合わせて使用されてもよく、任意の他の実施形態、もしくは任意の他の実施形態の任意の組み合わせの、１つまたは複数の特長と組み合わされて使用されてもよいことが明確に理解されなければならないことに留意すべきである。
【図面の簡単な説明】
【００４７】
【図１】本発明の第１の実施形態による方法の一部として実行されるステップを概略して描くフローチャートである。
【図２】本発明の第２の実施形態による方法の一部として実行されるステップを概略して描くフローチャートである。
【図１】
2009512908.tif 000003
【図２】
2009512908.tif 000004
【国際調査報告】
2009512908.tif 000005
2009512908.tif 000006
2009512908.tif 000007