(57)【特許請求の範囲】
【請求項１】
各々が映像シーケンス上の特徴の動きを示す複数の軌跡から前記映像シーケンス内の固有の動きを識別する映像解析方法であって、
前記映像シーケンスの隣接フレームにおいて像点をあらわす粒子が検出され、フレームにおける粒子間のリンクにより相対的な粒子運動が数値化されるオプティカルフロー推定により前記複数の軌跡を生成すること；
前記複数の軌跡から互いに関連する第１の軌跡および第２の軌跡を判定すること；および
前記固有の動きに対応するものとして前記第１の軌跡および前記第２の軌跡を分類すること；
を含み、前記第１の軌跡と前記第２の軌跡の間に指示的関係が存在し、
前記第１および第２の軌跡は、各々が、軌跡が示す特徴が周囲に対して静止している静的区間、および軌跡が示す特徴が周囲に対して移動している動的区間を持っており、前記指示的関係は、前記第１の軌跡の前記静的区間と前記第２の軌跡の前記動的区間の一致を含む、方法。
【請求項２】
前記複数の軌跡から１組の軌跡を判定することをさらに含み、前記１組の軌跡における各軌跡は、静的区間および動的区間を持っており、前記第１の軌跡および前記第２の軌跡は、前記１組の軌跡から判定される、請求項１に記載の方法。
【請求項３】
軌跡によってその動きが示される特徴は、前記静的区間では周囲に対して静止し、前記特徴は、前記動的区間では周囲に対して移動する、請求項１または２に記載の方法。
【請求項４】
前記指示的関係は、前記第１の軌跡および前記第２の軌跡により示される動きの方向の相関を含む、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記動きの方向の前記相関は、前記第１の軌跡が前記第２の軌跡に対して平行であることを含む、請求項４に記載の方法。
【請求項６】
前記固有の動きは歩行の動きである、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記指示的関係は、ランダム決定森を用いて判定される、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
コンピューター上で実行されたときに、請求項１〜７のいずれか一項に記載の方法を該コンピューターに行なわせる計算機実行可能命令を記録するコンピューター可読記録媒体。
【請求項９】
各々が映像シーケンス上の特徴の動きを示す複数の軌跡のためのストレージ；および
前記映像シーケンスの隣接フレームにおいて像点をあらわす粒子が検出され、フレームにおける粒子間のリンクにより相対的な粒子運動が数値化されるオプティカルフロー推定により前記複数の軌跡を生成し、
前記複数の軌跡から互いに関連する第１の軌跡および第２の軌跡を判定し、
固有の動きに対応するものとして前記第１の軌跡および前記第２の軌跡を分類するプロセッサを具備し、前記第１の軌跡と前記第２の軌跡の間に指示的関係が存在し、
前記第１および第２の軌跡は、各々が、軌跡が示す特徴が周囲に対して静止している静的区間、および軌跡が示す特徴が周囲に対して移動している動的区間を持っており、前記指示的関係は、前記第１の軌跡の前記静的区間と前記第２の軌跡の前記動的区間の一致を含む、映像解析システム。
【請求項１０】
前記プロセッサは、前記複数の軌跡から、静的区間と動的区間を持った１組の軌跡を判定し、該１組の軌跡から前記第１の軌跡および前記第２の軌跡を判定する、請求項９に記載の映像解析システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、映像解析に関し、より具体的には映像内の移動特徴の識別に関する。
【背景技術】
【０００２】
映像内の移動特徴の動きは、映像の複数フレームの各々における特徴の位置を示す軌跡によって表わすことができる。そのような軌跡を分析しその特徴を探すことによって、映像内の移動特徴を識別することができる。移動特徴は、例えば、映像における歩行者に関するものである。映像中の歩行者検出には、空間または建物に立ち入る人々または立ち去る人々の数を判定するといった、いくつかの応用例がある。自動車用途の歩行者検出もある。例えば、車両前方の物体の分析に基づいた自動ブレーキシステムの制御である。
【発明の概要】
【０００３】
歩行者のような注目物体を検出するには、注目物体の軌跡を注目していない他の物体の軌跡から識別しなければならない。映像中の物体の動きは、しばしば複雑な軌跡をえがく。したがって、物体を不正確に識別したり、注目物体を逸する可能性がある。
【０００４】
そこで、本発明は上記問題に対処し、映像中で固有の動きを識別する方法の提供を目的とする。
【０００５】
本発明の態様によれば、映像中で固有の動きを識別する映像解析方法が提供される。それぞれが映像シーケンス上の特徴の動きを示す複数の軌跡から、固有の動き(characteristic motion)が識別される。該方法は、指示的関係(indicative relationship)を持つ軌跡対を決定することを含む。軌跡対がそのような関係を持っていることが判明すると、その軌跡対は、固有の動きに対応するものとして分類される。
【０００６】
本発明の実施形態によれば、軌跡対間に存在しうる相関に基づいて、軌跡は分析され、分類される。
【０００７】
固有の動きは、歩行の動きであってもよい。歩いている歩行者の二本の足の動きには、いくつかの相関がある。
【０００８】
本発明の実施形態によれば、軌跡対を構成する第１および第２の軌跡は、静的区間と動的区間を有する。軌跡対を分類するのに用いられる軌跡対の指示的関係は、第１の軌跡の静的区間が第２の軌跡の動的区間と一致することである。
【０００９】
歩いている歩行者の足の軌跡は静的区間と動的区間を持つことから、この分析は歩行者の検出を可能にする。歩行者の地面に立っている方の足は静止しており、従って静的である。歩行者の別の方の足は地面に対して移動し、従って動的区間にあると考えることができる。歩行者が歩くと、一方の足を静的区間とし、他方の足を動的区間としながら、それぞれの足で静的区間と動的区間が交互に入れ替わる。
【００１０】
本発明の実施形態によれば、静的区間および動的区間を持つ軌跡が識別され、静的区間と動的区間を持つ軌跡の集合についてペアワイズ分析( pair wise analysis)が行なわれる。
【００１１】
これにより、空間的に足にかかわる軌跡を個々に識別して同一歩行者に関する軌跡対を識別することができる。
【００１２】
静的区間では、軌跡が示す特徴はその周囲に対して静止している。動的区間では、軌跡が示す特徴は、その周囲に対して移動している。
【００１３】
本発明の実施形態によれば、第１および第２の軌跡の指示的関係は、軌跡対の動きの方向の相関である。
【００１４】
歩行者の足の動きは、歩行者が歩く方向とほぼ平行であることが見込まれる。これは、空間的に歩行者の両足に関する軌跡対の識別に用いることができる。
【００１５】
本発明の実施形態によれば、第１および第２の軌跡の動き方向の相関は、第１の軌跡が第２の軌跡に対して実質的に平行であることを含む。
【００１６】
本発明の実施形態によれば、方法は複数の軌跡を判定することをさらに含む。
【００１７】
映像シーケンスの各フレームに注目点を置くことにより複数の軌跡が判定される。注目点は映像中の特徴に対応する。第１のフレーム内の特徴について軌跡を構築するために、次フレームの注目点とこれに先行するフレームの注目点の対応が判定される。１つのフレームにおける所与の注目点について、次フレームにおいて対応する２以上の注目点が用いられてもよい。注目点の対応を用いることにより、第１のフレーム内の注目点の軌跡が構築される。フレーム間、注目点間の複数の対応の可能性から、第１のフレーム内の注目点について、起こり得る軌跡が２以上見つかるかもしれない。
【００１８】
本方法は、フレーム間の注目点マッチングの柔軟性を許容する。複数の軌跡のうちのいくつかは、全フレームにわたって同じ物理的特徴を追跡しないかもしれない。しかしながら、他の軌跡と比べて、そのような軌跡が指示的関係を持つ可能性は低い。したがってそのような軌跡は指示的関係が存在するかどうかの判定をする際に破棄される。このような柔軟性は、物体がオクルージョンによって不明瞭になる場合、当該物体が不明瞭となるフレームからでさえも軌跡を常に生成できることから有利に働く。また、フレーム対にまたがり物体の２以上の空間的な一致がある場合、これらはすべて複数の軌跡に含めてもよい。
【００１９】
本発明の実施形態によれば、フレームにおいて注目点を表わすノードと、後続フレームにおいて同じ特徴に対応する注目点をつなぐエッジとを持つ非循環グラフを構築し、該グラフをトラバースすることにより、複数の軌跡が判定される。
【００２０】
本発明の実施形態によれば、非循環グラフをトラバースすることは、増補確率に基づいて、各ノードでエッジの確率的な選択を行なうことを含む。増補確率は、軌跡のトレース可能な深さに依存する係数を含むことができる。この係数は、指示的関係が存在するかどうかをより確実に判定しやすい長い軌跡に対して有利に働くのを可能にする。増補確率は、速度のような物理的特性の保存に基づいた係数を含んでもよい。これは、対象物に見込まれた特性を持っている軌跡に対して有利に働くことを可能にし、非物質的な軌跡を除外することをこのように可能にする。
【００２１】
本発明の実施形態によれば、指示的関係はランダム決定森を用いて判定される。
【００２２】
本発明の態様によれば、本発明に従う方法をコンピューターに実行させる命令を伝えるコンピューター可読媒体が提供される。
【００２３】
本発明の態様によれば、映像中の固有の動きを識別するための映像解析システムが提供される。
【図面の簡単な説明】
【００２４】
発明の実施形態を以下の図面を参照しながら説明する。
【図１】図１はデータ処理システムのブロック図である。
【図２】図２は映像内の移動特徴を認識する方法のフローチャートである。
【図３】図３はフレーム間で起こり得る軌跡のトレース図である。
【図４】図４は映像シーケンスにおいて対象を追跡する方法を示すフローチャートである。
【図５】図５は後のフレームの注目点との空間的な一致として分析されるフレームの注目点を示す図である。
【図６】図６は特徴の確率的な軌跡を生成するのに用いられる非循環グラフを示す図である。
【図７】図７は歩行者が歩く際の動きの固有パターンを複数の軌跡から識別する方法を示す図である。
【図８】図８は軌跡が足に関連するものであるか否かをランダム森分類器を用いて分類する方法を示す図である。
【図８Ａ】図８Ａは速度ベクトル対の例を示す図である。
【図９】図９はランダム決定森を示す図である。
【図１０】図１０はランダム決定森からの決定木を示す図である。
【図１１】図１１は２つの軌跡の動きの方向の相関に基づく関数を計算する方法を示す図である。
【図１１Ａ】図１１Ａは軌跡およびその一次の方向ベクトルの例を示す図である。
【図１２】図１２は、２つの軌跡の動きの位相の時間的な相関に基づく関数を計算する方法を示すである。
【発明を実施するための形態】
【００２５】
図１は、映像内の移動特徴を認識するためのデータ処理システム１００を示している。データ処理システム１００は、プロセッサ１０２、メモリ１０４、入力モジュール１０８および出力モジュール１１０を含む。メモリ１０４は、映像内の移動特徴を認識するためのプログラム１０６を記憶する。プログラム１０６は、プロセッサ１０２上で実行することができる。入力モジュール１０８は、映像シーケンスにおける移動特徴を認識する分析のために該映像シーケンスの入力を受け取ることができ、また、出力モジュール１１０は、その分析の結果を出力することができる。入力モジュール１０８は、ビデオカメラまたはビデオレコーダーからの映像データを受信することができるデータ接続でもよい。入力モジュール１０８は、インターネットのようなネットワーク上の映像データを受信することができるネットワーク接続でもよい。データ処理システム１００は、従来のコンピューターでもよい。以下、プログラム１０６によって行なわれる方法を説明する。
【００２６】
図２は、映像内の移動特徴を認識する方法のフローチャートを示す。映像は、フレームのシーケンスから構成される。各々のフレームは、同時に１組の特徴を表現する。映像が再生される場合、映像内の特徴の動きは、該映像の連続フレーム上でのそれらの位置の変化に反映される。したがって、映像中の特徴の軌跡は、映像シーケンス上の各フレームについての位置と見なすことが可能である。特徴の軌跡を、物体の見込まれる動きと比較することにより、物体に対応するものとして特徴を認識することができる。例えば、映像中に現れる、歩いている人の足は、固有の動きのパターンを持つ。足が地面に接している時、歩行者のその足は固定区間を持ち、足が地面に対して移動している時、その足は移動区間を持つ。また、歩行者の足の歩行の動きには相関性がある。一方の足が静止している時、他方の足は動いている。映像内の特徴の動きを、足の動きのような予期される固有のパターンと比較することによって、足のような特徴を映像において識別することができ、したがって、歩行者を識別することができる。
【００２７】
映像内の移動特徴を認識するには、映像のフレームについての特徴の軌跡が必要である。映像内の物体の軌跡を追跡するには、映像フレームにおいてその物体の位置を識別することが必要である。したがって、対処すべき２つの問題がある。物体の位置を各フレームにおいて識別しなければならない。また、追跡するフレームにおいて同じ物体を識別しなければならない。
【００２８】
方法のステップＳ１００は、映像シーケンスの各フレームに注目点を置くことを含んでいる。シーケンスの２以上のフレームで起こりうる一定の特徴を示す個々のフレームの空間的ピクセルパターンを検出する。例えば、第１ステップが、各フレームのコーナーを発見することを含んでもよい。
【００２９】
映像内の特徴の軌跡を検出するために、ステップＳ１０１において、直接先行するフレームにおける特徴に対応する注目点が判定される。
【００３０】
ステップＳ１０２では、シーケンスの第１のフレーム内の所与の注目点について、１組の起こり得る軌跡を生成する。注目点について起こり得る最も一般的な軌跡の組は、次フレームにおいて識別される注目点のうちのいずれかの次フレームにおける位置を含む。フレームの外部や、フレーム内の別の物体の背後、つまり当該フレームにおいて示されない位置に通じる軌跡とすることも可能である。
【００３１】
起こり得る軌跡の組は、フレーム対を考慮し、該フレーム対における空間的なマッチング(matching)注目点を識別することにより判定する。マッチング注目点の対は、マッチングスコアを計算することにより識別する。マッチングスコアについては、注目点位置の間の空間距離および注目点のアピアランスの類似性のような要因を考慮する。これは、２フレーム以内で似たような位置および／または類似のアピアランスを持つ注目点を識別することにより達成することができる。空間的なフレームのマッチング対から、フレームシーケンスを通して該マッチング対をトレースすることにより、起こり得る軌跡を構築する。
【００３２】
映像シーケンスの第１のフレーム内の物体について起こり得る軌跡の組は、第２の後続するフレーム内の多数の注目点を含んでもよい。起こり得る軌跡の組を、物体の軌跡が従うものと予期されるパターンに基づく制約を実行することによって絞り込む。これは、例えば物体の速度保存のような物理法則とすることができる。
【００３３】
起こり得る軌跡の数を絞り込んだ時点で、軌跡が更なる処理に必要な場合、起こりそうな軌跡の確率的な選択を行う。結果として生ずる軌跡は、例えばジェスチャ認識アルゴリズムにおける更なる処理において用いられる。確率的な選択が繰り返される場合、選択された軌跡は相違しうることに留意されたい。
【００３４】
次にステップＳ１０３内において、軌跡を固有の動きのパターンと比較する。
【００３５】
図３は、フレーム間の起こり得る軌跡のトレース図を示している。図３において一番上のフレームは最近のフレームであり、また、時間的に前のフレームは最近のフレームの下に示される。入力シーケンスの各フレームにおいて、いくつかの注目点が見つかる。隣のフレームの注目点との間であり得る対応はリンクによって示される。
【００３６】
図４は、映像シーケンス内の対象を追跡する方法を示すフローチャートである。例えば、映像シーケンスは、解像度１２８０×７２０ピクセルで６０フレーム／秒の３５０フレームとする。図４に示す方法では、映像シーケンスのフレームにおけるコーナー検出により特徴を追跡する。図１に示されるデータ処理システム１００を参照しながら、この方法について説明する。ステップＳ１において、映像シーケンスの各フレームから注目点を抽出する。各フレームのコーナーを検出するために、ハリス・コーナー検出器が用いられる。各フレームにおける注目点の位置は、メモリ１０４のセクションに記憶される。ハリス・コーナー検出器は、画像の領域を考慮し、これをわずかにシフトし、その領域を当該画像の重複領域と比較することにより、画像内のコーナーの位置を検出する。ハリス・コーナー検出器は、プログラム１０６の一部として実装される。すべての方向で重複領域の変化があるところにコーナーは位置する。ハリス・コーナー検出器については、「C. Harris and M. Stephens, 'A Combined Corner and Edge Detector', Proc. Forth Alvey Vision Conference, pages 147-151, 1988」に記載されている。
【００３７】
時点ｔのフレームにおける注目点をｐｉ（ｔ）と表す。ここで、ｉ＝１，．．．，ｎは、注目点のインデックスである。フレームｔにおける注目点ｐｉ（ｔ）の二次元位置はｘｉ（ｔ）である。
【００３８】
ステップＳ２では、諸フレームの注目点間の一致（match)を判定する。一フレームの各注目点について、空間的な祖先である前フレームの注目点が識別される。この識別は、現フレームで検討しているコーナーの一定範囲内に存在する前フレームの注目点を分析することにより行う。
【００３９】
図５は、時間ｔのフレームにおける注目点ｐｉ（ｔ）の空間的な一致であるとして分析される時間ｔ−１のフレームにおける注目点ｐｊ（ｔ−１）を示す。フレームｔにおける注目点ｐｉ（ｔ）の位置ｘｊ（ｔ）の範囲Ｒ内において位置ｘｊ（ｔ−１）を持つ注目点ｐｊ（ｔ−１）を分析する。範囲Ｒの外側の位置ｘ’ｊ（ｔ−１）を持つ注目点ｐ’ｊ（ｔ−１）は、注目点ｐｉ（ｔ）との空間的な一致とされることはない。
【００４０】
各注目点対について、時間的なマッチングスコアを計算する。時間的なマッチングスコアは、前フレームにおける注目点と現フレームにおける注目点とを一致させる。
【００４１】
時間的なマッチングスコアは２つの注目点のアピアランス類似性およびそれらの空間距離に基づく。
【００４２】
時点ｔのフレームにおける注目点ｐｉ（ｔ）と、時点ｔ−１の前フレームにおける注目点ｐｊ（ｔ−１）の間の時間的なマッチングスコアをＰｉｊ（ｐｉ（ｔ），ｐｊ（ｔ−１））と表す。これは、次式によって計算することができる。
【数１】
0005634517.tif 000002
【００４３】
ここで、Ｓｉｊは、注目点ｐｉ（ｔ）と注目点ｐｊ（ｔ−１）の間のアピアランス類似である。アピアランス類似は、それぞれのフレーム中の注目点周囲の局所画像領域から計算される。
【００４４】
これは、局所画像領域間の絶対差の正規化平均の和として計算される。Ｄｉｊは、注目点間の空間距離であり、次式から計算される。αおよびβは、正の重み付け係数である。
【数２】
0005634517.tif 000003
【００４５】
空間的な一致は、時間的なマッチングスコアＰｉｊに基づいて識別される。２進値Ｅｉｊ（ｔ）は、時点ｔのフレームにおける注目点ｐｉ（ｔ）と時点ｔ−１の前フレームにおける注目点ｐｊ（ｔ−１）の間の空間的な一致の各々に関連付けられる。空間的な一致は、現フレームにおける所与のコーナーの時間的なマッチングスコアの最高値として選択してもよい。あるいは、最大値のしきい値範囲内で時間的なマッチングスコアを持つ一致をすべて空間的な一致として選択してもよい。したがって、
【数３】
0005634517.tif 000004
【００４６】
のいずれかについて、Ｅｉｊ（ｔ）＝１である。ここで、ｅはしきい値である。
【００４７】
処理を逆に考えても空間的な一致は判定される。前フレームの各注目点について、時間的なマッチングスコアが現フレームの注目点について計算される。
【００４８】
ステップＳ３では、２つのフレーム間の一致総数を制限する。これは、一致数を単に一定に維持すればよい。フレーム対間の一致数が一定となるように、しきい値ｅは動的に調整してもよい。フレーム間の一致総数４ｎは、一致の固定数として適切な定数であることが分かった。これらは最も高い時間的なマッチングスコアを持ったものとして選択されている。これにより、コーナーの最大マッチングスコアが低い値である場合に、一致がないコーナーが結果として生じるかも知れない。
【００４９】
ステップＳ３の後に、シーケンスの各フレームにおけるいくつかの注目点と、フレーム間の注目点のアクティブな一致の組を入手することができ、確率的な軌跡抽出のためのグラフを構築することができる。
【００５０】
このグラフをステップＳ４において構築する。各フレームｔに対して、１組の注目点ｐｉ（ｔ）がある。また、時間的に隣接するフレーム間において、時点ｔのフレームと時点ｔ−１のフレームの注目点との間に１組の一致Ｅｉｊ（ｔ）がある。これらはグラフＧｉ（Ｎ，Ｅ）を構築するのに用いられる。グラフＮのノードは、前フレームにおいて一致した注目点を表わし、エッジ（Ｅ）は、注目点間の一致を表わす。このグラフは、映像シーケンスの最終フレームに注目点の各々のルートノードを定めることによって構築される。当該注目点から前フレームにおける注目点へのエッジがアクティブな一致のそれぞれについて加えられる。ノードは、前フレームで一致した注目点について定められる。この処理を、当該シーケンスの最終フレームに先行するフレームからのアクティブな一致について繰り返し、以下の図５に示すような非循環グラフが生成される。これは、確率的な軌跡を生成するのに用いることができる。このグラフは、Ｔ個のフレームについて構築される。各エッジＥｉｊ（ｔ）には、その重み係数としてｐｉ（ｔ）が与えられる。
【００５１】
エッジのトレース可能な深さ、すなわち、グラフにおいて特徴点ｐｉ（ｔ）の空間的な祖先を持つフレームの数をｄ［Ｅｉｊ（ｔ）］と表記する。グラフＧｉ（Ｎ，Ｅ）を表わすデータはメモリ１０４に記憶される。データは、Ｎ個のノードの各々のｘｉ（ｔ）に対する値、各エッジＥｉｊ（ｔ）に対するＰｉｊ（ｔ）およびｄ［Ｅｉｊ（ｔ）］の値として記憶される。
【００５２】
ステップＳ５において、この非周期グラフをトラバースすることにより軌跡を生成する。トラバースはいずれかのルートノードから開始する。また、エッジの確率的な選択を行う。この処理を各ノードで繰り返す。確率的な選択は、増補確率に基づいて行う。この増補確率は、マッチングスコアから計算され、トレース可能な深さおよび速度保存係数を考慮するための係数を含んでいる。
【００５３】
増補確率、あるいはサンプリング確率Ｐ’ｉｊ（ｐｉ（ｔ），ｐｊ（ｔ−１））は、次式から与えられる。
【数４】
0005634517.tif 000005
【００５４】
ここで、γとδは正の重み係数である。また、Ｖｉｊは次式から与えられる速度保存係数である。
【数５】
0005634517.tif 000006
【００５５】
上記速度保存係数の式は、問題のフレームｘｉ（Ｔ）における注目点の位置、前フレームｘｊ（Ｔ−１）内の軌跡における注目点の位置、および軌跡Ｘｈ（Ｔ＋１）内で次の点と見なされている注目点の位置を考慮に入れる。
【００５６】
トレース可能な深さに依存する係数を含んだ増補確率を使用することは、長い軌跡を支持することを意味する。長い軌跡は、短い軌跡より利用価値が高い場合が多い。また速度保存係数は、検討中のフレームに至るまで軌跡内の物体の速度を保存する特徴点間のリンクを支持することを意味する。これにより、非循環グラフをトラバースする場合、物理的特徴の動きに対応する可能性がありそうな滑らかな軌跡を確実にたどることができる。
【００５７】
非循環グラフは、最終フレームの特徴点に対応する物体について複数の確率的な軌跡を生成するために複数回にわたりトラバースすることができる。生成される軌跡は相違するものとなり、このため少なくともいくつかのものは正確ではない。しかしながら、連続するフレームの対応に関して不確実性がある場合であっても可能性のある軌跡を許容することにより、シーケンスの一部においてオクルージョンにより物体が不明瞭になる場合であっても比較的長いフレームシーケンスの軌跡を得ることができる。
【００５８】
一の物体についての複数の軌跡は、例えば、特定の固有の動きを持つ映像シーケンス内の特徴を検出するパターン認識アルゴリズムに有用である。この場合、シーケンスの最終フレームにおける各注目点について、複数の起こり得る軌跡を検査し、特定の固有の動きを持つものについてすべての起こり得る軌跡を検査すると効果的であるかもしれない。非循環グラフを用いて複数の起こり得る軌跡を生成することは、上記の応用に特に適している。
【００５９】
非循環グラフのトラバースの後、確率的な軌跡Ｘｉ（ｔ）＝［ｘ（ｔ），ｘ（ｔ−１），．．．ｘ（ｔ−Ｔ＋１）]をメモリ１０４に記憶する。これは、この軌跡に属する点のフレーム内の位置の集合を表わす。
【００６０】
図６は、上述した方法を用いて特徴の確率的な軌跡を生成するのに用いられる非循環グラフを示している。最近のフレームにおける注目点は、グラフの一番上のノードとして示される。これら注目点は、１組のエッジによって前フレームにおける注目点に連結される。時間的なマッチングスコアが、時間的に隣接するフレームにおいて注目点を表わすノードをつなぐ各エッジに関連付けられる。
【００６１】
注目点のグラフから軌跡を抽出するために、各ノードにおいて、そのノードを前のフレームにおいて注目点を表わすノードに接続しているエッジのうちの１つが選択される。
【００６２】
歩行者の歩行の動きを識別するために、軌跡を固有のパターンと比較するステップは、空間的に歩行者に一方の足に関する特徴を識別すること、および、歩行者の2本の足に対応する動きに相関を持つ特徴の対を検出することを含んでいる。これについて図７を参照して述べる。
【００６３】
図７は、複数の軌跡から、歩行者の歩行の動きの固有のパターンを識別する方法を示している。
【００６４】
上述したように、確率的な軌跡の計算以外の方法によって複数の軌跡を得ることができる。例えば、「Peter Sand, Seth Teller, Particle Video: Long-Range Motion Estimation using Point Trajectories, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.2195-2202, June 17-22, 2006」に記載されるような粒子技術を軌跡の生成に用いることができる。粒子映像技術は、粒子の軌跡を生成する。粒子は、像点を表わす。オプティカルフロー推定は、隣接フレームにおいて粒子の位置を検出するのに用いられ、フレームにおける粒子間をつなぐリンクは、相対的な粒子運動を数量化するのに用いられる。
【００６５】
ステップＳ６０１において、候補軌跡を識別する。軌跡が空間的に足に関係するかどうか判断するために、およそ１つの歩行周期の軌跡の動きが分析される。軌跡が足の位置に対応する注目点に関連している場合、歩行周期内で移動区間および固定区間を持つことが期待される。したがって、ステップＳ６０１において、一の歩行周期内で動的区間および固定区間を持つものが候補軌跡として識別される。
【００６６】
候補軌跡が識別されると、関連する候補軌跡対をステップＳ６０２において検出する。歩いている歩行者については、二本の足の動きは相関することが期待される。この相関は、時間的かつ空間的である。相関の時間的な態様は、歩いている歩行者の一方の足が固定区間にある場合、他方の足は動的区間にあることが期待されるということである。二本の足の空間的な位置もまた相関を持つことが予期される。これらの相関に加えて、歩行者の足の動きの方向についても相関があることが期待される。歩いている人の二本の足の軌跡は、歩行者が歩いている方向においてほぼ平行であることが期待される。上記の相関を持っている候補軌跡対を識別することによって、映像シーケンスにおいて歩行者の足に関係する注目点の動きから歩行者が識別される。
【００６７】
足に関連するものであるか足に関連するものでないかによって軌跡を分類し、ステップＳ６０１において候補軌跡を識別するには、ランダム森分類器を用いることができる。
【００６８】
足に関連するものであるか否か軌跡を分類するのにランダム森分類器を用いる方法を図８に示す。ステップＳ７０１において、軌跡を標準形に変換する。軌跡を標準形に変換することは、軌跡の角度のような係数、軌跡に関係しうる歩行者の速度、歩行者のステップの幅および相を説明することを意味する。標準形への変換は、カメラの動きのような線運動の削減、およびステップ振幅のような軌跡の正規化態様を含んでもよい。
【００６９】
軌跡の標準形は、次のように表記される。
【数６】
0005634517.tif 000007
【００７０】
ステップＳ７０２において、特徴ベクトルｖ０およびｖ１を軌跡の標準形から生成する。これらの特徴ベクトルは、４つの時点ｔ０，ｔ１，ｔ２およびｔ３を任意に選択し、それらの位置で軌跡を５つのセクションにカットすることで生成される。特徴ベクトルは、次式から与えられる。
【数７】
0005634517.tif 000008
【００７１】
図８Ａは、速度ベクトル対の例を示している。特徴を計算するために、多数の速度ベクトル対がサンプリングされる。
【００７２】
ステップＳ７０３において、特徴ｆｓおよびｆｄを特徴ベクトルおよびランダムに選択した変数から計算する。この特徴は、次のように距離および２つのベクトルｖ０およびｖ１の内積として計算される。
【数８】
0005634517.tif 000009
【００７３】
ここで、ａ０、ａ１、ｂ０およびｂ１は０と１の間の値をとる任意の係数である。
【００７４】
カット点ｔ０、ｔ１、ｔ２、ｔ３および係数ａ０、ａ１、ｂ０、ｂ１について異なる値を用いることにより、ｆｓとｆｄの多数のバリエーションを作ることができる。
【００７５】
ステップＳ７０４において、ランダム決定森を用いることにより、足に関連するものであるか足に関連しないものであるかに軌跡を分類する。
【００７６】
図９は、ランダム決定森８００を示している。ランダム決定森８００は、８本の決定木８１０、８２０、８３０、８４０、８５０、８６０、８７０、８８０を持つ。各軌跡は、全部で８本の木を用いて分類される。木の各分岐点においてパラメーターｔ０、ｔ１、ｔ２、ｔ３、ａ０、ａ１、ｂ０およびｂ１を用いてｆｓとｆｄの関数が計算される。この関数の値に基づいて、左の枝と右の枝のどちらをたどるかの判定がなされる。左と右の枝のどちらを選ぶかの選択に用いられるしきい値θの値は、足／非足の分散の情報増加が最大となるように選定される。
【００７７】
図１０は、図９に示した決定森８００から取り出した決定木８１０を示している。決定木９０２の各ノードにおいて、当該木をトラバースする場合、軌跡が当該ノードに達する条件つき確率を２本の縦線の高さで示す。決定木８１０のルートノード９０２において、この点の特徴は足であるか否かの情報がないことから、足の特徴９０４に関する軌跡の縦線と、非足の特徴９０６に関する軌跡の縦線は等しい。この木のトラバースの際に、ｆｓとｆｄの関数値が計算され、問題の軌跡についてのこれら値に基づいて、左の枝のノード９１０または右の枝のノード９０８のいずれかに到達する。トラバースは継続し、各分岐点で異なる関数の値が計算される。葉ノード（例えば９２０）に到達すると、木８１０からの条件つき確率は、決定森における他の木からの条件つき確率と結合され、この確率に基づいて、軌跡は、足あるいは非足のどちらかに分類される。
【００７８】
ランダム森は、各分岐点について、パラメーターｔ０、ｔ１、ｔ２、ｔ３、ａ０、ａ１、ｂ０およびｂ１、関数ｆｓおよびｆｄ、各分岐点のしきい値θに関する一連の値として記憶される。これらの値はメモリ１０４に記憶する。これらは、手動で映像シーケンスの特徴に注釈を付与し、関数ｆｓおよびｆｄの値を計算し、最大の情報利得を与えるしきい値θに対する値を選択することにより、プログラム１０６の実行に先立って計算される。
【００７９】
足の候補軌跡が識別されると、これらを分析し、同一歩行者について相関する足の組を検出する。この分析についても、上述と同様の方法でランダム決定森を用いて行う。ランダム決定森において木をトラバースする場合に判定を下すのに用いられる関数は、検討中の２つの軌跡の動きの方向の相関、および軌跡における動きの移動区間と固定区間の相関に基づいて計算される。
【００８０】
図１１は、２つの軌跡Ｘｉ（ｔ）およびＸｕ（ｔ）の動きの方向の相関に基づく関数を計算する方法を示している。ステップＳ１００１において、各軌跡の動きの方向を検出する。軌跡Ｘｉ（ｔ）の動きの方向は、位置ｘｉ（Ｔ）の集合Ｔ＝ｔ．．．ｔ−Ｔ＋１の分散行列を計算し、分散行列の最大固有値に対応する固有ベクトルξｉを計算することにより検出される。したがって、ξｉは、Ｘｉ（ｔ）の一次の方向を表わす。第２の軌跡Ｘｕ（ｔ）の一次の方向ξｕも同様に計算される。
【００８１】
図１１Ａは、軌跡Ｘｉ（ｔ）および一次の方向ベクトルξｉの例を示している。
【００８２】
ステップＳ１００２において、２つの軌跡に関連している時点ｔのフレームにおける注目点の位置ｘｉ（ｔ）およびＸｕ（ｔ）に基づいて、該２つの軌跡について歩行方向のベクトルｘｉｕ（ｔ）を計算する。
【数９】
0005634517.tif 000010
【００８３】
ステップＳ１００３において、互いの動きの方向の内積および歩行の方向によりコンシステンシーｃを計算する。
【数１０】
0005634517.tif 000011
【００８４】
コンシステンシーは、歩行者の足の移動方向がほぼ平行になること、および、これらの方向は歩行の歩行方向とほぼ平行になることが見込まれるという事実を利用するものである。
【００８５】
ステップＳ１００４において、コンシステンシーに基づいた関数ｆ０およびランダムベクトルΦを計算する。
【数１１】
0005634517.tif 000012
【００８６】
図１２は、検討中の２つの軌跡Ｘｉ（ｔ）およびＸｕ（ｔ）の動きの位相の時間的な相関に基づいて関数を計算する方法を示している。
【００８７】
ステップＳ１１０１において、軌跡の速度ベクトルＹｉ（ｔ）を計算する。
【数１２】
0005634517.tif 000013
【００８８】
ここで、Ｔ＝ｔ，．．．ｔ−Ｔ＋２について、ｙ（Ｔ）＝ｘ（Ｔ）−ｘ（Ｔ−１）である。
【００８９】
ステップＳ１１０２において、修正した速度ベクトルを計算する。次式すなわち
【数１３】
0005634517.tif 000014
【００９０】
を用いることにより、一定のカメラモーションを相殺することができる。修正された速度ベクトルは次式を用いて生成される。
【数１４】
0005634517.tif 000015
【００９１】
ステップＳ１１０３において、修正された速度ベクトルを固定のカット点でｌ個の部分にカットする。そしてステップＳ１１０４において、カットされ修正された速度ベクトルの内積に基づくベクトルを計算する。
【数１５】
0005634517.tif 000016
【００９２】
最後にステップＳ１１０５において、このベクトルおよびランダムベクトルに基づいた関数を計算する。
【図１】
0005634517.tif 000017
【図２】
0005634517.tif 000018
【図３】
0005634517.tif 000019
【図４】
0005634517.tif 000020
【図５】
0005634517.tif 000021
【図６】
0005634517.tif 000022
【図７】
0005634517.tif 000023
【図８】
0005634517.tif 000024
【図８Ａ】
0005634517.tif 000025
【図９】
0005634517.tif 000026
【図１０】
0005634517.tif 000027
【図１１】
0005634517.tif 000028
【図１１Ａ】
0005634517.tif 000029
【図１２】
0005634517.tif 000030