(57)【要約】【課題】本発明の方法及びシステムは、モデルを追跡して、ある環境において物体移動を予測する。【解決手段】一組のセンサにより感知された時間的及び空間的に隣接する一連のイベント同士を関連づけて、一組のトラックレットを形成する。各トラックレットは、関連づけられた開始及び終了位置を有する。トラックレットは、エッジにより接続された開始ノード、終了ノード及び中間ノードを含む有向グラフを作成するために使用される。中間ノードは、トラックレットが異なるトラックに分岐するスプリットノードでもよく、また複数のトラックレットが単一の通路に収束するジョインノードでもよい。その環境における物体の移動をモデル化して予測するために、確率がエッジに割り当てられる。【選択図】図８
2008211781.tif 000002
【特許請求の範囲】
【請求項１】
ある環境において移動する物体により引き起こされた離散イベントを、前記環境における既知の位置に配設された一組のセンサで検出する工程と、
時間的及び空間的に隣接する一連の離散イベント同士をリンクさせて一組のトラックレットを形成する工程と、
前記一組のトラックレットから、少なくとも１つの開始ノード、少なくとも１つの終了ノード、及び複数のトラックレットが前記物体の移動において曖昧点を発生させながら接続する一つまたは複数の中間ノードを含む一組の有向グラフを作成する工程と、
前記環境において前記物体の移動をモデル化するために、前記物体が特定の既知の位置にあった尤度を示す確率を前記ノードへ割り当てる工程と、
を備えたことを特徴とするある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項２】
前記センサは、モーションセンサであることを特徴とする請求項１に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項３】
前記センサは、前記イベントを伝送するためにワイヤレス送信機を使用することを特徴とする請求項１に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項４】
前記リンクさせる工程は、時間的及び空間的な制約条件に従って行なわれることを特徴とする請求項１に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項５】
前記時間的及び空間的な制約条件は、時間経過とともに学習されることを特徴とする請求項４に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項６】
特定の確率が特定の物体に関連していることを特徴とする請求項１に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項７】
開始ノードがノードＡであり、終了ノードがノードＺであり、グラフγ０が特定の物体のノードＡからノードＺまでの移動をモデル化する場合に、ノードＡで開始する特定の物体が常に前記グラフγ０のノードＺで終了するならば、前記確率は、次式
【数１】
2008211781.tif 000025
で表されることを特徴とする請求項１に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項８】
前記中間ノードは、複数のトラックレットが分岐するスプリットノードと、複数のトラックレットが収束するジョインノードとを含むことを特徴とする請求項１に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項９】
開始ノードがノードＡであり、終了ノードがノードＺであり、Γが一組のグラフγｉである場合に、前記確率は、次式
【数２】
2008211781.tif 000026
で表されることを特徴とする請求項１に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項１０】
一組の終了ノードを組Θとすると、前記確率は、次式
【数３】
2008211781.tif 000027
で表されることを特徴とする請求項９に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項１１】
一組の開始ノードを組Φとすると、前記確率は、次式
【数４】
2008211781.tif 000028
で表されることを特徴とする請求項１０に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項１２】
前記組Φ及び組Θは、不連続でありうることを特徴とする請求項１１に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項１３】
割り当てられた確率で前記一組のグラフから前記物体の移動を予測する工程を備えたことを特徴とする請求項１に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項１４】
前記終了ノードの確率をランクにより順序付けする工程を備えたことを特徴とする請求項１に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項１５】
前記環境は複雑であることを特徴とする請求項１に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項１６】
特定の物体が特定の既知の位置にないならば、前記確率Ｐは０であり、前記特定の物体が前記既知の位置にあれば、前記確率Ｐは１であり、また、その他の場合には、前記確率Ｐは０＜Ｐ＜１であることを特徴とする請求項１に記載のある環境において物体の移動をモデル化するためのコンピュータにより実施される方法。
【請求項１７】
ある環境における既知の位置に配設され、前記環境において移動する物体により引き起こされた離散イベントを検出するように構成された一組のセンサと、
時間的及び空間的に隣接する一連の離散イベント同士をリンクさせて一組のトラックレットを形成する手段と、
前記一組のトラックレットから、少なくとも１つの開始ノード、少なくとも１つの終了ノード、及び複数のトラックレットが前記物体の移動において曖昧点を発生させながら接続する一つまたは複数の中間ノードを含む一組の有向グラフを作成する手段と、
前記環境において前記物体の移動をモデル化するために、前記物体が特定の既知の位置にあった尤度を示す確率を前記ノードへ割り当てる手段と、
を備えたことを特徴とするある環境において物体の移動をモデル化するためのシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願］
この出願は、２００６年１１月３０日にイワノフ（Ｉｖａｎｏｖ）外によって出願された、米国特許出願第１１／５６５，２６４号、「環境における物体を追跡、識別するための監視システム及び方法」の一部継続出願である。
【０００２】
本発明は、一般に、監視システム及び物体追尾方法に関し、特に監視データから物体の動きをモデリングすることに関する。
【背景技術】
【０００３】
ビデオカメラと比較的簡単なセンサとは、大きな環境に対して混合様式の監視システムを構成することを可能にする。センサは物体を識別できないが、比較的小さな領域では、物体を検出できる。画像が利用可能であるときには、カメラによって入手されたビデオ（映像）の画像から識別を行うことができる。
【０００４】
そのようなシステムによって入手されたビデオを記憶或いは蓄積することは、多テラバイトのデータを超えることがある。明らかに、特定の物体に対して何カ月にも亘って収集された記憶データを、瞬時に検索することは、実際には不可能である。従って、簡易なセンサで検出した動きの離散イベントにより物体を見つけるのが望ましい。その上、動きのイベントから物体の移動をモデル化して、物体の移動を予測するのが望ましい。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来の監視システムでは、通常、人間、動物、車などの物体の追跡は、画像及びビデオ処理によって行われる。そのような監視システムの欠点は、特定の物体を追跡、識別することが必要なときに、物体をカメラによって観測することが必要なことである。しかしながら、多くの監視環境は、正確な操作に必要な完全な監視範囲を提供するために、多くのビデオカメラを必要とする。大量のビデオストリームは、正確に作動するために、監視システムでの演算負荷を増大させる。
【０００６】
本発明の目的は、様々なセンサ、カメラ及び監視データベースの混合されたネットワークを使用することにより、移動する物体（例えば、人々）を追跡して、識別するためのシステム及び方法を提供することである。
【課題を解決するための手段】
【０００７】
少数のＰＴＺカメラは、監視下に置かれるべき環境に配置される。カメラの数が比較的少ないとしても、ビデオ（映像）データの量は、多テラバイトの記憶容量を超えることがあり得る。
【０００８】
ビデオカメラは、その環境の一部のイメージ（画像）を獲得できるだけである。このため、カメラだけで物体の追跡と識別とを行なうのは難しくなる。カメラの監視範囲が完全であっても、映像データを検索する時間は非実用的なものとなる。
【０００９】
従って、その環境は、またセンサの密度の高い配置構成を含み、それらのセンサは、本質的には、全ての公共領域をカバーする。イベントは、関連するセンサ識別と時間とを有する。これは、センサデータの総量をかなり小さくして、処理を簡単にする。個々の人間がカメラによって連続して見られないとしても、センサの起動イベントは、特定の個人を追跡するために、ビデオ画像に空間的及び時間的に相関づけられる。
【００１０】
その環境における物体の動きを表わす有向グラフを作成することが可能である。それらのグラフには、開始ノード、終了ノード、及び中間ノードがある。中間ノードは、曖昧点につながる。物体が特定の位置でそれらの移動を開始して終了する尤度を示すように、それらのノード同士を接続するエッジに確率が割り当てられる。物体の動き（移動）は、その動き及びそれを表わすグラフに曖昧点があったとしても、それらの確率から予測することができる。
【発明の効果】
【００１１】
本発明の実施の形態は、混合様式の監視システムを提供する。本システムは、多くの比較的簡単なセンサ及び比較的小数の可動カメラを含む。このことは、従来の監視システムと対比して、費用、複雑さ、ネットワーク帯域幅、記憶容量、及び処理時間を減少させる。
【００１２】
ある環境における物体は、センサからの利用可能な前後の（文脈）情報を使用してカメラにより追跡される。特定の物体の航跡（トラック）を瞬時に判別するために、何カ月にも亘って収集された前後の（文脈）情報を検索することができる。そして、物体を識別するのに、対応する物体の画像を使用できる。このようなことは、膨大な量の映像データの検索を必要とする従来の監視システムでは、実際には不可能である。
【００１３】
また、本発明の実施の形態は、航跡（トラック）に対する確率を求めることにより、物体の移動をモデル化して、予測するための方法及びシステムを提供する。顕著な特徴として、本発明は、解析の前に完全な航跡（トラック）を必要としない。殆どの従来の監視追尾（トラッキング）システムは、信頼できる前処理工程を必要とする。これは、全ての曖昧点を解消するために、忠実度の高いセンサと計算上複雑な方法とを含意する。
【００１４】
対照的に、本発明は、比較的簡単な（バイナリの）モーションセンサ、及び曖昧点を持っている不完全なトラックでも働くことができる。本発明は、トラックを表すグラフにおけるエッジに確率を割り当てることによって、曖昧点を解決する。
【発明を実施するための最良の形態】
【００１５】
監視システム
図１に示されているように、本発明の実施の形態に従って追跡モジュールが実施される監視システムは、比較的大きなセット（組）のワイヤレス・ネットワークのセンサ（ドット）１０１と、比較的小さなセット（組）のパン‐ティルト‐ズーム（ＰＴＺ）カメラ（三角形）１０２とを含む。センサ対カメラの比率は、非常に大きく、例えば３０：１以上の場合がある。
【００１６】
センサ
センサは、モーション（運動）センサでもよく、またドアセンサ、昇降機センサ、熱センサ、圧力センサ、音響センサでもよい。赤外線センサなどのモーションセンサは、センサの付近での物体の動きを検出できる。ドアセンサは、典型的には戸口を通過する人を示すドア開閉イベントを検出できる。昇降機センサは、同様に、ある環境における人々の到着または出発を示すことができる。また、例えばトランスデューサやマイクロホン等の音響センサは、ある領域の活動を検出できる。センサは、その環境における光スイッチ、またはオフィス機器の電源スイッチに搭載することができる。また、マット（敷物）の圧力センサも、通過するトラフィックを示すことができる。また、環境への入口通路におけるバッジ読取り装置などのセキュリティセンサを組み込むことができる。
【００１７】
各センサは比較的小さく、例えば、モーションセンサについては、３×５×６ｃｍである。好適な実施の形態において、これらのセンサは、約１０メートル以下の間隔で互いに離れて、公共領域に密に配置され、また天井、壁、或いは床に取り付けられる。なお、特定の環境及びその環境におけるトラフィックフロー（交通流）に合うように、センサの空間的配置と密度を適合させることができることに注意すべきである。例えば、高いトラフィック（交通）の地域は、低いトラフィックの地域よりも人口密度が高い。
【００１８】
本発明の一実施の形態では、そのセット（一組）のセンサは、工業規格ＩＥＥＥ８０２．１５．４の無線信号を使用して、プロセッサ１１０（図１を参照）と通信する。これは、ジグビー（Ｚｉｇｂｅｅ）タイプのデバイスによって典型的に使用される物理層である。各電池式センサは、検出モードで約５０μＡ、また通信時に４６ｍＡを消費する。起動による通信間隔は、約１６ミリ秒である。また、センサは、ハードウェアに組み込まれてもよいし、或いは他の通信技術を使用してもよいことに注意すべきである。
【００１９】
イベントがセンサ１０１の何れかによって検出されるとき、そのイベントに対応するセンサ識別記号（ＳＩＤ）とタイムスタンプ（ＴＳ）が一斉送信されるか、或いは別の方法でプロセッサ１１０に送られる。プロセッサは、センサデータを監視データベースとしてメモリに記憶する。識別記号は、本来センサの配置場所、従って起動を引き起こしたイベントの配置場所を示す。イベントの記録を行うのには、僅かなバイト数を要するだけである。従って、映像データと比較すると、長期間に亘って収集されたセンサデータの総量は、本質的には、取るにたらないものである。
【００２０】
そのセット（一組）のカメラは、ビデオ（映像）データ（画像系列）を取得するのに使用される。画像は、カメラの固有カメラ識別記号（ＣＩＤまたは配置場所）とフレーム番号（ＦＮ）を有する。本明細書で使用されるように、フレーム番号は、時間と同義である。すなわち、フレーム番号から時間を直接的に計算することができる。さらに、データベースからの問い合わせの間、どんな時刻におけるセンサ近傍のシーン(場面)の可視部分についても計算できるように、あらゆる時刻が各カメラの一組のパン‐ティルト‐ズーム・パラメータに関連している。
【００２１】
カメラは、最大の監視範囲を提供するために、戦略的な配置場所（位置）、例えばその環境における全てのトラフィックがいつか通過しなければならない配置場所で、典型的には、天井に搭載される。如何なる一般的な方向にも、ＰＴＺカメラ１０２を向けて、焦点を合わせることが可能である。必ずしも必要ではないが、ビデオ画像を取得するために、イベントの検出により、近くの何れのビデオカメラをもセンサ近傍のシーンに向けることができる。少数の一連の画像すなわちイベントに関連するビデオクリップを検索するのに、関連するセンサのＩＤとＴＳを後で使用することができる。また、特定のカメラの近くのセンサの近傍で何らイベントが検出されない場合には、所要の記憶容量を減量させるために、画像収集を中断できることに注意すべきである。
【００２２】
特定のイベントを見つけたり、特定の物体のトラック（航跡）を見つけたりして、それらの物体を識別するために、何カ月もの操作に亘って取得された映像データを調べることは難題である。
【００２３】
トラックレット及びトラックレットグラフ
図２に示されているように、本発明の一実施の形態では、一組のトラックレット（トラック片）２１０が使用される。対応するトラックレットグラフ２００が一組のトラックレット２１０から集められる。トラックレットは、一連の空間的に隣接しているセンサ１０１での一連の時間的に隣接している離散事象（イベント）同士にリンクを張ることによって、形成される。トラックレットは、トラックレットグラフ２１０の基本的構成ブロックである。「離散事象（離散イベント）」という用語は、センサの近くの動き（移動）を単一のタイムスタンプのビットで送信できることを示すために使用される。これは、ビデオの形態の連続信号を流すカメラとは異なっている。
【００２４】
我々は、現在のイベントにリンクした直前の先行または後継イベントを見つける処理をコールする（呼び出す）。システムの性能を向上させるために、周期的にトラックレットのリンクと保存（記憶）とを行うことができる。例えば、１営業日の終わりに、或いは毎時間ごとにリンクと保存とを行うことができる。このように、検索を行うことが必要なとき、予め保存したトラックレットを容易に利用することが可能である。
【００２５】
組み立てられたトラックレットグラフ２００では、トラックレットは、グラフのノードで接続された有向エッジである。そのグラフのノードは、各トラックレットのその直後のトラックレットまたは直前のトラックレットとの関係をコード化する。ノードは、次の４つのタイプの内の１つを持つことができる。すなわち、トラックスタート(開始)２０１、トラックジョイン（結合）２０２、トラックスプリット（分岐）２０３、及びトラックエンド（終了）２０４である。
【００２６】
トラックスタート（開始）
トラックスタートノードは、トラックレットにおける最初（第１）のイベントを表しており、所定時間間隔内で何れの先行イベントもそのセンサに関連させることができない。本明細書で使用されるように、「先行」は、隣接するセンサでの以前のイベントを意味する。「時間間隔」は、歩行者が一つのセンサから隣接する次のセンサまで移動するのにかかる時間にほぼ限定できる。
【００２７】
トラックジョイン（結合）
トラックジョインノードは、所定時間間隔内にそのセンサに関連させることができる複数の先行イベントが存在するような、トラックレットグラフにおけるイベントを表す。すなわち、トラックレットジョインノードは、複数の先行トラックレットが単一の後継トラックレットに収束することを表している。単一の有効な先行トラックレットは、それが現在のトラックレットに既にリンクされているので、存在することができない。
【００２８】
トラックスプリット（分岐）
トラックスプリットノードは、所定時間間隔内にそのセンサに関連させることができる複数の後継トラックレットが存在するような、トラックレットにおけるイベントを表す。すなわち、トラックレットスプリットノードは、単一の先行トラックレットが複数の後継トラックレットへ分岐することを表している。単一の有効な後継トラックレットは、それが現在のトラックレットに既にリンクされているので、存在することができない。
【００２９】
トラックエンド（終了）
トラックエンドノードは、所定時間間隔内に何れの後行イベントにも関連させられないような、トラックレットにおける最後のイベントを表している。全てのトラックレットは、一組のグラフを形成し、それらのグラフの各々は、物体が移動した実際のトラック（航跡）に関する固有の曖昧さを表している。
【００３０】
トラックレットグラフは、ユーザにより課され得るか、または時間経過とともに「学習され得る」、時間的及び空間的な制約条件により集めることができるイベントに関連する一組のトラックレットである。
【００３１】
図２のトラックレットグラフには、２つの開始トラックレットがあり、それらは、その後単一のトラックに収束する。そして、収束されたトラックレットは、２度分岐して、４つのエンドポイント（終点）になる。トラックレットグラフは、我々が物体追跡のために使用するイベントの中心的な表示である。
【００３２】
延長トラックレットグラフ
物体がセンサネットワークの視界から見えなくなる場合における延長された追跡の目的のためにも、２つの空間的に隣接していて時間的にも隣接しているトラックレットグラフを集めることができる。このような状況は、追跡されている人々が廊下などの公共領域を抜け出して、オフィスなどの領域に進入するときの環境で頻繁に起こる。オフィスに入るイベントは、人が感知すなわち観測されなくなったとき、トラックレットエンドノードで先行トラックレットを終了させる。オフィスを出る際、その人を再び後継グラフで追跡できる。人がオフィスに入ると、その人は、例えば何時間もの長い期間の後にでも、退出しなければならないと思われる。この場合、空間的な制約条件は、厳密に実行され得るが、時間的な制約条件は緩和できる。
【００３３】
先行グラフにおけるトラックレットのトラックエンドノードの一つが、後継グラフにおけるトラックレットの少なくとも一つのトラックレットスタートノードのタイムスタンプよりも小さなタイムスタンプを有するという条件の下で、グラフが集められる。
【００３４】
センサの可視性の判別
本発明の一つの目標は、あるセンサの近傍の領域が複数のカメラの何れから見ることが出来るかを判別することである。これにより、ユーザに提示される無関係な画像の量を最小にする。
【００３５】
この目標を実現するために、システムの全てのカメラがセンサの配置場所に較正される。我々のシステムでは、各センサは、そのカメラからセンサの起動を引き起こしたイベントを見えるようにする各カメラのさまざまなパン、ティルト及びズームのパラメータに関連している。各カメラのＰＴＺパラメータが、カメラ方向の変更の度に、監視データベースに保存されるならば、トラックレットがセンサ起動毎にデータベースから検索されるときに、「可視」領域を、対応する時に各カメラのＰＴＺパラメータと比較できる。カメラのＰＴＺパラメータがセンサの可視領域に入ると、次に、センサの起動（イベント）が可視であると考えられ、対応するカメラからの一連の画像がビデオ証拠として検索される。以下に述べるように、この証拠は、続いて、ユーザインタフェースを使用したトラックレット選択プロセスの間、ユーザに表示される。
【００３６】
人間に誘導された追跡
我々が我々のシステムで解決する人間により誘導された追跡及び検索に関するタスクを簡単なシナリオで示すことができる。
【００３７】
ラップトップ型パソコンがオフィスから午後１時００分と午後２時００分との間に盗まれたと報告された。そのオフィスに対して利用可能な直接的カメラ監視範囲は無かった。ユーザは、その時間帯にオフィスを通過できた全ての人々を見つけ出し、そして可能ならば、彼らを識別し、個人をそのイベントに結びつける証拠を集める必要がある。そのような状況では、オペレータ（操作者）は、そのオフィスのドアで開始する全てのトラック（航跡）を識別し、全ての利用可能なビデオ証拠を調べることによって、その個人を識別することを欲するであろう。
【００３８】
混合様式のセンサネットワークでの物体追跡の一般原理
トラックスタートノード及びトラックエンドノードは、完全なトラック（航跡）の明確な始めと終わりである。ところで、トラックスプリット（航跡分岐）とトラックジョイン（航跡結合）の曖昧さの自動的解決は、感知されたイベントのみを使用するだけでは不可能である。スプリット（分岐）とジョイン（結合）との曖昧さは、センサにおける、或いは、センサの近くのイベント以外の如何なる特徴へのセンサネットワークの知覚的限界のためである。
【００３９】
そのような状況では、２人の人間が廊下で通路を横切る（出会う）イベントは、可能な交差点の前後で各人に対するイベントを含む少なくとも４つのトラックレットをシステムに発生させる。更なる情報がなければ、このセット（組）のトラックレットの解釈には、固有の曖昧さがある。例えば、その２人の人間は、互いに行き違うか、或いは出会って彼らが来た道を引き返すことができる。これらのトラック（航跡）に対するアイデンティティ（同一性）をマップ化して、絶対確実にそれらの連続性を維持することは、それらのイベントだけからでは不可能である。
【００４０】
これらの曖昧さの見地から、我々は、以下のように簡素化して観測を行う。
【００４１】
ユーザは、グラフ全体の曖昧さを除く必要がない。ユーザは、前方または後方のグラフ横断に対して、選択されたトラックレットを開始するトラックジョインノードの曖昧さを除いたり、或いは、トラックレットを終了させるトラックスプリットノードの曖昧さを除いたりすることがそれぞれ必要になるだけである。
【００４２】
各候補トラックに関連するビデオクリップを考慮に入れることによって、トラックジョイン及びトラックスプリットの曖昧さを解決することを簡素化できる。
【００４３】
第１の観測は、トラックに集められるべき可能な候補であるとみなされる必要があるトラックレットの量を著しく減量させる。一実施の形態では、ユーザは、一度に一人のみを追跡する。従って、システムは、効果的に他のイベントを無視しつつ、その人の移動を解決（分析）するだけでよい。通路で交差する２人の人間の例に対して、我々は、１つのトラックレットが交差点の前に選択され、４つ全てではなく、２つのトラックレットだけが、可能な連続であるとみなされる必要があると仮定する。トラッキング（追跡）及びトラックの曖昧さの解消への、この繰り返しフォーカスされた手法で、私たちは、問題の複雑さを潜在的に指数型から線形（一次関数）へ減少させることができる。
【００４４】
第２の観測は、スプリット及びジョイン（分岐と結合）の曖昧さが生じるとき、システムがトラックレットの時間と配置場所とを直近のカメラからのビデオと相関させて、集合トラックに対して何れのトラックレットが可能性の高い連続であるかを決定するために、対応するビデオクリップをユーザに表示することができることを含意する。
【００４５】
センサのネットワークだけを使用することにより、物体の動きの力学（動態）を推測するのを試みる自動追跡手順を開発することが可能であるかもしれない。しかし、如何なるそのような処理手順も誤りを犯すのは不可避である。監視アプリケーションでは、若干不正確なだけの追跡処理の結果に対するコミットメント（関与、取り組み、対応）は、かなり高価になる場合がある。
【００４６】
従って、我々の追尾方式は、追跡データを表す基本的な前後の（文脈）情報としてのトラックレットグラフと共に、人間により誘導された技術を使用する。追跡及び検索が基づいているセンサデータが非常に小さく、従って、特に映像データの従来の検索と比較すると、速やかに処理を進めることができることに注意すべきである。
【００４７】
我々のシステムの主眼とすることは、イベントを使用することにより、非常に短時間で効率的に多量の映像データを検索することである。このために、我々は、主としてフォールスネガティブレート（偽陰性率）を小さくすることに関心があるが、フォールスポジティブレート（偽陽性率）を小さくすることが遠い二次的目標である。これらの目標を実現するために、我々は、以下に述べるようなトラック集合用の機構を採用する。
【００４８】
トラックレット集合処理
我々のシステムの人間に誘導された追跡のプロセスは、我々が開始すべきトラックと予想する一つ以上のセンサのサブセット（部分集合）と、任意ではあるが、時間間隔と、を選択することで始まる。例えば、我々のシステムでは、センサがオフィスの外側の公共区域に配置される場合、ユーザは、フロアープラン（床配置図）を使用して、人が特定のオフィスを出るときに恐らく起動されうるそのセンサのサブセット（部分集合）を選択できる。
【００４９】
イベントのデータベースにおける高速検索を行なうことによって、我々は、選択されたセンサの１つで開始するトラックレットのあらゆるインスタンス（例）を識別できる。ここで、ユーザは、さらに詳細に探査を行うために、そのトラックレットの単一のインスタンス（例）を選択できる。トラックが開始するおおよその時点を特定することによって、上記の検索を速めることができる。
【００５０】
第１のトラックレットを選択すると、対応するトラックレットグラフが構成される。集められたトラックのグラフは、時間的及び空間的に隣接する一連のイベントに関連する複数のトラックレットを含む。選択されたトラックレットは、図３に示されているように、エンド（終了）、スプリット（分岐）またはノード（結合）があるところのポイント（地点）まで床配置図上に描かれる。エンドポイント（終点）に到達すると、トラック３００は完成する。床配置図においてトラック３００に沿った人の場所が、トラック３００で太線３０１により、ユーザインタフェースに視覚的に示される。
【００５１】
トラックレットのエンド（終端）がスプリット（分岐）ノード或いはジョイン（結合）ノードを有するならば、トラックは終了されず、候補トラックレットを、一貫性を有するトラックへ集めるために複数のトラックレットグラフを使用してトラックレット集合処理が繰り返して行われる。このプロセスの間、グラフ中の各曖昧（不明瞭）点（スプリットノードまたはジョインノード）で、ユーザは、さらに横断するためのサブグラフを選択する。人々を識別して、正しい後継トラックレットを選択するために、対応するトラックレットに属するセンサ起動の何れかに指向されたカメラからの利用可能なビデオ画像を表示することができる。また、物体や顔の認証などの自動化技術を、上述の識別のために使用できる。
【００５２】
その処理は、選択グラフを使用して図４に示されている。選択グラフでは、ビデオ画像４０１は、対応する複数のトラックレットに含まれている複数のセンサへ指向された複数のカメラからの利用可能な複数のビデオクリップを表している。菱形４１０は、曖昧ポイント（点）、及びその曖昧ポイントに続く可能な競合トラックレットを示す。そのグラフにおけるエッジは、トラックレットが存在することを示す。
【００５３】
なお、図４のトラックレット選択グラフは、図２のトラックレットグラフに関連するが、それと同一ではない。事実、図４のグラフは、一般的な選択グラフを表しており、それは、時間的に前方（図示されるように）或いは後方へのトラックレットグラフの横断のために使用できる。前者の場合には、図４における選択グラフのスタート（開始）及びエンド（終了）ノードは、トラックレットグラフにおけるそれらと同じ意味を持っているが、菱形のみは、スプリット（分岐）を表している。トラックジョインは、前進の選択代替策を提示しないので、前進の選択プロセスとは無関係である。対照的に、選択グラフが後方の横断のために使用される場合には、選択グラフのスタート及びエンドノードは、トラックレットグラフのものと反対の意味を有し、菱形のみがジョイン（結合）を表している。
【００５４】
いずれの場合でも、トラックレット選択グラフは、最初に選択されたトラックレットで始まり、スタートノード２０１で示される利用可能なカメラフレーム４０１を横断可能な、トラックレットグラフによる一組のトラックを表している。曖昧ポイント（点）は、既知であるので、そのような各ポイントでは、システムは、曖昧さの解消のために、曖昧なトラックレットのセットをユーザに提示できる。
【００５５】
例えば、第１ステップでは、曖昧ポイント４１０は、現在のノードからのスリーウェイスプリット（三方向分岐）を表している。最も左側のトラックレットは、２つのカメラ視界４３１につながる。中央のトラックレットは、カメラ視界を持たずに終わる。３番目のトラックレットは、１つのカメラ視界を持っており、次に、ツーウェイスプリット（二方向分岐）につながる。これらのトラックレットの各々を床配置図に描くことができる。選択が行われた後、拒絶されたトラックレットは、床配置図から取り除かれる。エンド（終了）トラック２０４に出会うまで、処理が続けられる。
【００５６】
トラックの終端に遭遇するとき、トラック集合処理のプロセスを終了することができる。しかし、ユーザに実際のトラックが終了ポイントから続くと信じる理由があるならば、前述のようなトラックレットグラフ拡張機構が使用される。システムは、終了されたトラックの位置で始まる新しいトラックレットを見出すために、所定時間間隔内でデータベースの検索を行なう。そのようなトラックレットを見出すなら、以下に述べるように、対応するビデオクリップが識別され、トラックレット選択コントロールパネルにおいてユーザに表示される。ユーザがトラックの延長された線分に対して最初のトラックを選択すると、集められたトラックの終端にトラックレットが追加され、その選択されたトラックレットで始まる新しいトラックレットグラフが作成される。その後、その物体の完全なトラックをさらに延長するために、選択プロセスが、前述と同様に、繰り返して続けられる。完全なトラックでは、全てのジョイン及びスプリットノードが取り除かれ、トラックは、単一の開始トラックレットと単一の終了トラックレットとを含むのみである。
【００５７】
ユーザインタフェース
図５に示されるように、一実施の形態では、ユーザインタフェースは、５つのメインパネル、すなわち、床配置図５０１、タイムライン（時系列）５０２、ビデオクリップビン（記憶装置）５０３、トラックレットセレクタ５０４、及びカメラ視界パネル５０５を含む。
【００５８】
床配置図は、図３に示されている通りである。床配置図のトラック３００に沿った人の位置が、トラック３００における「膨れ」３０１（破線）により示される。各センサに対して、タイムライン５０２は、イベントを示す。タイムラインにおける各列は、一つのセンサに対応しており、時間は、左から右に進む。垂直線５１０は、「現在」の再生時間を示す。現在時刻を設定するために、メニュー及びアイコン５２０を使用できる。再生のスピードを調整するために、「ノブ」５２１を使用できる。マウスで線をドラッグすることによって、タイムラインを前方及び後方に移動できる。短い線分２００は、トラックレット、また、線３００は、解決されたトラックをそれぞれ表す、図３を参照。
【００５９】
ビデオクリップビンは、物体識別のために選択されたクリップ（画像系列）の画像を示している。本質的には、ビデオクリップビンにおけるトラックに関連する収集された一連の画像は、トラックと物体に関連するビデオ証拠である。
【００６０】
トラックレット選択制御は、図４の決定グラフの現状を示している。
【００６１】
現在時刻及び選択された位置に対応する画像がカメラ視界パネル５０５に示されている。画像は、ユーザにより選択されるか、或いはカメラスケジューリング処理手順により自動的に選択されることができる。ビデオクリップビン５０３を形成するために、クリップの再生の間に、スケジューリング処理手順を呼び出すことができる。
【００６２】
追跡方法
本発明の実施の形態では、追跡プロセスは、二つの相を含む。すなわち、物体を追跡するために、監視データを記録する相と、及び検索する相とである。
【００６３】
記録相は、図６に示されている。図６は、監視データベース６１１におけるセンサデータを保存する方法を示している。監視データベースは、一組のセンサ１０１によって取得されたイベント１０３を保存する。センサの選択されたサブセット（部分集合）に対して時間的及び空間的に隣接している一連のイベントは、一組のトラックレット６３１を形成するようにリンク６３０されている（繋がっている）。各トラックレットには、トラックレットスタートノードとトラックレットエンドノードがある。また、トラックレットは、監視データベースに保存される。
【００６４】
センサ起動と同時に、一組のカメラ１０２によって取得された画像１０４の順序がコンピュータ記憶装置６１２に記録される。各イベント及び画像は、１つのカメラ（位置）と時間とに関連付けられている。なお、前述と同様に、カメラのＰＴＺパラメータを判別することもできる。
【００６５】
トラッキングフェーズ（追跡相）が図７に示されている。このフェーズ（相）は、あるトラックが開始すると予想されるセンサのサブセット（部分集合）を選択し６２０、複数のトラックの開始として使用されうる複数のトラックレットを見つけ出し６２５、そのトラックの開始として第１のトラックレットを選択し６４０、そしてトラック集合処理６８０を行うことを含む。
【００６６】
トラック集合処理は、選択されたトラックレットに対してトラックレットグラフ６５１を構成する６５０ことで始まる。トラックレットグラフ６５１は、複数の先行トラックレットが単一の後継トラックレットに合流するところの可能なトラックレットジョインノードと、単一の先行トラックレットが複数のトラックレットに分岐するところの可能なトラックレットスプリットノードとを有する。
【００６７】
トラックレットグラフ６５１は、最初に選択されたトラックレットから始まり、繰り返し横断される。そのグラフに続いて、次の曖昧なノードが識別され、候補トラックレットに含まれるセンサ起動（イベント）に時間的及び空間的に相関づけられた画像がコンピュータ記憶装置６１２から検索され、表示６６０され、そして、集められたトラック６６１に結合されるべき次のトラックレット６７０が選択される６７０。
【００６８】
その処理は、集められたトラック６６１がそのエンドポイントとしてトラックエンドノードを有するトラックレットで終了されるときに終わり、そして、そのグラフから全てのジョイン及びスプリットノードが取り除かれる。
【００６９】
物体トラックのモデル化及び物体の移動の予測
以上で、私たちは、離散的な動き（モーション）イベントに従って、物体（例えば、人間）が何処にあったかを判別する方法を説明した。次に、我々は、ある環境で取得された監視データから、物体が行くかもしれない場所を予測して、物体の曖昧な動き（移動）を識別しようと思う。具体的には、我々は、異常な、或いは不審な挙動を示すかもしれない動きを予測しようと思う。
【００７０】
我々は、高品質の（ビデオ）追跡が可能でないか、または実行不可能であるときでも、その環境における物体の動きをモデル化するための複数の方法について説明する。それらの方法は、複雑な環境で移動する如何なる関心物体（人間、車等）に対しても有効である。「複雑な環境」という言葉により、我々は、恐らく数百や数千個ものセンサ及び同様の数の、ワーカー（労働者）や車等の移動物体を有する大規模オフィスビル、製造工場、または駐車場を意味している。複雑な環境では、互いに関連する物体の尤度は比較的高く、物体のアイデンティティ（同一性）は、未知であるかもしれない。
【００７１】
まず最初に、我々は、トラッキング（追跡）により高品質及び低品質を比較する。高品質のトラッキング（追跡）は、センサ、例えばカメラやモーションセンサ等、の集合からセンサデータの連続ストリームを処理して、特定の個人の動きのモデルを生成する行為である。そのモデルは、その物体（個人）が移動したトラックに沿った当該個人の開始、中間及び終了位置に関する質問に答えるために使用できる。一般に、トラッキング（追跡）は、決定論的なトラックモデル（すなわち、その環境を通るその個人のトラックに関する最良の推測）を生成すると考えられる。
【００７２】
そのモデルの曖昧点は、誤り、追跡の失敗、異常な或いは珍しい運動であると考えられる。高品質のトラッキング（追跡）システムは、全ての曖昧点を解消する試みにおいて非常に複雑になる可能性がある。その環境に複数の個人がいると、曖昧点が不可避的に生じるであろう。
【００７３】
各物体に対して決定論的な動き（移動）モデルを生成するという目標を有する監視システムでは、それらの曖昧点は、物体の真の構成に関する仮説と、将来のイベントに対して、唯一の真の仮説が残るまで、伝播され、テストされ、できれば剪定されねばならない環境との集合として表される。
【００７４】
曖昧点は、物体または個人の相互作用から生じるので、考慮されねばならない仮説の数は、その環境における個体数と比較して、指数関数的に増大する可能性がある。
【００７５】
低品質のトラッキング（追跡）は、曖昧点を解決するのが非現実的であるか、または事実上不可能なので曖昧点が許容される場合である。
【００７６】
高品質のトラッキングシステムは、イベントが曖昧点の解決のために充分な特別な情報を含まなければならないので、一般的に高品質のセンサを必要とする。人々を追跡するシステムは、顔を認識したり、衣服の色のマッチング（照合）を行ったり、キー（鍵）カードやバイオメトリックスキャンに依存したりして、そのような曖昧点を解決するかもしれない。
【００７７】
それらの種類の高品質なセンサが利用できない状況では、離散イベントを送信する（例えば、動きの無いときにセンサがオフになり、動きがあるときにセンサがオンになる）ことしかできない簡易なセンサを備える環境において、物体の動き（移動）のパターンに関する推論を引き出すことが、まだ有用である場合がある。完全なトラッキング（追跡）出力を当てにするよりむしろ、我々は、離散的な動きのイベントを送信することしかできない低品質のモーションセンサによって得られた不完全な追跡モデルの集合からこれらの推論を得る方法を説明する。
【００７８】
トラックレット
我々は、トラックレットの概念を、確率的なフレームワークにおいてその表示を埋め込みつつ使用する。１つのトラックレットの基本概念は、明白に互いに関連する離散イベントをそのトラックレットに集めるということである。トラックレットの概念は、上述のように、トラックレットのグラフ中の不完全な追跡モデルを高品質のトラックモデルへと洗練するために、システムが効率的に当該システムのユーザと対話できるように、監視に適用するための物体追跡における曖昧さを表わす方法として開発された。
【００７９】
今、我々は、一組の確率的なグラフから推論を得るのを可能にするために、トラックレットとトラックレットグラフとを確率的モデルに埋設する。このようにして、本発明は、短い期間に亘っての個々人の単一または小さなグループの特定の動きではなく、長い期間に亘って個々人の集団または他の物体の動き（移動）のパターンを理解するのを可能にする。
【００８０】
図８に極度に単純化して示すように、イベント８０１の集合が空間と時間を通して一列に並べられる。それらのイベントは、上述したように、例えば、簡易な低品質のモーションセンサによって検出された動きイベントであり得る。
【００８１】
以下において、それらのイベントは、その環境における位置と同義である。１つのセンサは、その環境における比較的小さな領域における動き、例えば約５〜１０メートルの領域における物体の動きを検出できるだけである。このため、複数のセンサは、比較的小さな領域における移動物体を検出し、（検出された）複数のイベントは、複数のセンサの位置に直接関連させることができる。それらのセンサが廊下に配置され、そしてオフィスに隣接して特定の個人に割り当てられたならば、比較的高い確率で特定の個人のトラフィック（通行）パターンを予測することが出来る。
【００８２】
複数のイベントが空間的にお互いに近くにあり、時間的に、順番に配列されており、他のイベントから孤立しているならば、その環境における物体の動きの簡易モデルは、それらのイベントを通る実線矢印で示すように、我々が当該イベントを単一のトラック８０２に集めることを可能にする。その矢印は、一連の離散イベントを１つのトラックレットに抽象化したものであり、そのトラックレットは、その集合における全てのイベントが同一の個人、または個人の小さなグループによって生成されたという事実を、非常に高い確率で表すモデルである。
【００８３】
さらに、それらの一連のイベントに、空間及び時間において最終的なイベントの近くにある如何なるイベントも続いていないならば、我々は、トラックレットが終了したと言う。これは、ボックスノード８０３によって表される。同様に、トラックレットが空間及び時間において他のイベントに接続されるように思われるイベントに先行されないならば、トラックレットは、その空間及び時間で始まり、そして、これは三角形ノード８０４により示される。続いて、我々は、開始ノードＡから終了ノードＺまでの高水準のトラックレット抽象化８０５を示すのみで、それらのイベント自体をドロップ（廃棄）することができる。
【００８４】
トラックレットグラフが示される。我々は、図８の単純グラフ８０５をグラフγ０と呼ぶ。グラフγ０は、ノードＺで検出された終了イベントが、開始ノードＡでそのイベントを生成した同じ個人によって生成されるという確率Ｐが高いことを示す。
【００８５】
一般性の喪失がなければ、グラフγ０を考えると、次式
【数１】
2008211781.tif 000003
で表される確率８００は、ノードＺで検出されたイベントが、ノードＡのイベントに続いて起こるという確率が明らかに（曖昧ではなく）１であることを意味する。ここで、
【数２】
2008211781.tif 000004
は、後に続くということを示している。
【００８６】
一般に、物体が既知の位置にないならば、確率Ｐは０であり、物体が既知の位置にあれば、確率Ｐは１であり、また、その他の場合には、確率Ｐは０＜Ｐ＜１である。
【００８７】
トラックレットグラフ
その環境における曖昧点は、より複雑なグラフを生成する。我々のグラフは、有向のエッジまたはトラックレットによって接続されたノードを含む。可能な共通の原因を共有する全てのイベントが、同一の連結されたグラフに結びつけられる。グラフ中のノードは開始ノード、中間ノード及び終了ノードを含むことができる。この説明のために、グラフは、スプリットノードまたはジョインノードのような、少なくとも１つの中間ノードを含む。そうでなければ、どんな曖昧点もないであろうし、また、物体を追跡するという問題が決定論的になり、かつ些細になる。中間ノードはスプリットノードとジョインノードを含むことができる。
【００８８】
確率は、物体が特定のノードで始動して、別のノードで終了するという見込みを示すためにエッジ（トラックレット）に割り当てられる。換言すると、確率とは、終了ノードにおけるイベントが開始ノードのイベントに続き、それらのイベントは同じ物体によって引き起こされるという尤度である。トラックは、開始ノードから終了ノードへ延びており、曖昧点を生じさせるために中間ノードを含む。
【００８９】
図９は、その環境においてトラックを横断する２人以上の個人を表すより複雑なグラフを示している。
【００９０】
山形部９０１及び９０２はジョイン（結合）ｊ及びスプリット（分岐）ｓをそれぞれ表している。すなわち、数回のイベントが、十分に小さな時間的及び空間的な近傍内でスプリットｓに続いて起こり、曖昧点が発生する。スプリットの場合には、１つのトラックレットにおいて共同アクター（人物）であるとみなされるように、一緒に動いている、或いは互いに非常に近い幾人かの個人がいる。スプリットの後では、ｊからｓへトラックレットを横断した各個人のトラックは曖昧である。すなわち、それぞれの個人がトラックレットに沿ってスプリットｓから終了ノードＺへ移動したのか、或いはスプリットｓから終了ノードＹへ移動したのかが曖昧である。
【００９１】
我々がγ１と呼ぶこのグラフを考えると、私たちはノードＡで始まる個人のトラックを知らない。この曖昧点の確率は、次式（１）で表される。
【数３】
2008211781.tif 000005
ここで、我々は、両方の結果が等しく起こりうるように、ｐ＝ｑと決めてもよいし、或いは、我々の予測を一方或いは他方に偏向させるように、移動パターンを学習しても良い。そのパターンは、システムのユーザにより手動的に学習されることもできるし、或いは時間の経過とともに自動的に学習されることもできる。ノードＡの個人または物体は、どこかに行かなければならないので、グラフにおけるその確率は、合計すると１、すなわちｐ＋ｑ＝１にならねばならない。
【００９２】
グラフは、任意に複雑にすることができる。図１０のグラフγ２は、幾つかの開始ノードＡ、Ｂ及びＣ、幾つかのスプリット（分岐）ｓ及びジョイン（結合）ｊ、並びに終了ノードＷ、Ｘ、Ｙ及びＺを有する遙かに複雑なグラフである。
【００９３】
グラフにおいて有向エッジをトレースすることによって、どんな終了ノード｛Ｗ、Ｘ、Ｙ、Ｚ｝にも開始ノードＡを接続することが可能である。例えば、その確率は、次式の通りである。
【数４】
2008211781.tif 000006
【００９４】
ここで、ノードＡで開始する個人が、非零の確率を有するそれらの位置の何れかで終わることができるように、我々は、その確率を以下の次式（２）〜次式（５）に示す。
【数５】
2008211781.tif 000007
我々は、それらの全ての結果が等しく起こりそうであると決めてもよいし、或いはまた、個人の習慣的な動き等のような、以前に学習された情報に基づいて、それらの確率を偏倚させてもよい。
【００９５】
より興味深いケースは、ノードＣで開始する個々人が、彼らの最終目的地において同じくらい多くの曖昧さを持っていないことである。ｓ１からｊ２へエッジが指向されるので、すなわち、次式
【数６】
2008211781.tif 000008
で表される確率が成立するので、ノードＣで開始しノードＷまたはノードＸで終了する個人に対する妥当な説明は無い。そのため、次式（６）〜次式（９）が成立する。
【数７】
2008211781.tif 000009
【００９６】
グラフが完全であることに注意する価値がある。すなわち、ノードＣで始まり、１つの終了ノードで終わる物体に関連する一連の可能なイベントがあれば、その終了ノードがグラフにある。しかしながら、グラフ中でノードＶが終了ノードでないならば、確率は次式で表される。
【数８】
2008211781.tif 000010
【００９７】
同様に、特定のグラフで見出せない開始ノードに対しては、そのグラフに亘る時間の間、その開始ノードと終了ノードとの間には、どんな可能な接続もこのグラフにはない。例えば、その確率は次式で表される。
【数９】
2008211781.tif 000011
【００９８】
グラフのセット
ある瞬間に、外観上連係されていないようにその環境内を動き回わる幾つかの物体または個人がたまたまトラックを横断し、曖昧点を生成して、その結果、特定のトラックレットグラフのインスタンス（例）γを生成した個々人のコーホート（群）になる。上述の解析は、それらの個人のトラックに関して多少の弱いアサート（表明、主張）を行う。
【００９９】
我々は今、より長い期間に亘る物体の集団の動きを説明する１セット（組）のグラフΓについて考える。
【０１００】
我々は、「このセット（組）のグラフが、ビル（建物）内で個々人が一つの場所から他の場所へ移動する確率に関して我々に何を示すか」という形の質問をすることができる。我々は、例えばノードＡを含み且つノードＡで開始する全てのグラフを検索して、可能ならば個々の確率によって重み付けされた、ノードＡとＺとの間の可能な接続を含むグラフの数を数えることにより、この質問に答えることができる。このことは、次式で表される。
【数１０】
2008211781.tif 000012
ここで、Ｎは、そのセットΓにおけるグラフの数である。ノードＡを開始ノードとして含むセットΓにおけるグラフの数はＭであり、それは、正規化因子（係数）として使用できる。１つの接続に対する証拠、すなわち次式
【数１１】
2008211781.tif 000013
で表される確率は、トラックレットグラフを作図して、次にグラフの数Ｍと共に、各センサ対に対する証拠を蓄積することによって、イベントが受信されるにつれて蓄積され得る。
【０１０１】
物体の動きを全体として示している明白な（曖昧さの無い）トラックレットが無いときでも、繰り返す動き（運動）に対する証拠を蓄積することが可能である。ノードＡで開始するトラフィックが常にノードＺで終了するならば、ノードＡを開始ノードとして含むセットΓにおける全てのグラフは、ノードＡからノードＺへの妥当なトラックを含んでいる。これはかなりの量の証拠となる。
【０１０２】
確率
【数１２】
2008211781.tif 000014
は、平均証拠確率
【数１３】
2008211781.tif 000015
である。その確率は、その動きのあらゆる例が完全に明白（曖昧さの無い）であるときよりも小さく、そして、確率
【数１４】
2008211781.tif 000016
は、同様に１である。
【０１０３】
逆に、決して繰り返されない偶然の或いは極めて稀な動き（運動）は、分子に殆ど証拠を集めないが、分母は、偶発的な開始ノードを含むグラフの数であり、そして、その結果として生じる値は、グラフのセット（組）に対して非常に小さい。
【０１０４】
センサの集団に亘って、及びグラフに亘って確率としての証拠をさらに集めることによって、ある環境におけるトラフィックパターンを次式のように定量化することが可能である。
【数１５】
2008211781.tif 000017
ここで、Θは終了ノードのセットであり、また、正規化因子Ｍは、全てのトラフィックが通過しなければならない環境における隘路等の、開始ノードとして対象となる特定のノードＡを含むセットΓにおけるグラフの数である。これは、我々がその環境における異なる領域の間の「接続性」を測定することを可能にする。
【０１０５】
より一般な解は、次式に示すように、開始ノード及び終了ノードに対する確率を複数のグラフに亘って集めることである。
【数１６】
2008211781.tif 000018
ここで、Φは開始ノードのセットである。セットΦ及びΘは、不連続の場合があり、その環境に亘って分散配置させてもよい個人のグループ間の関係を測定する。
【０１０６】
いずれの場合でも、次式
【数１７】
2008211781.tif 000019
で表される確率は、グラフのセットΦにおけるあるノードで開始するトラックが、グラフのセットΘにおけるあるノードで終了する相対的な尤度を表している。
【０１０７】
接続性グラフ
その環境における全ての開始及び終了の対のノードＡ及びＺの間の次式
【数１８】
2008211781.tif 000020
で表される確率は、その環境におけるある場所から他の場所への、繰り返される人々の流れがある確率の推定値を表している。オフィスビル等の環境で、個々の人々は、典型的には、特定のオフィスに関連している。このため、通常、ある個人を特定のオフィスの外で開始するトラックに関連づけることが可能である。同様に、あるトラックがあるオフィスで終了するならば、その個人を比較的高い確率で再び認識できる。また、通常、少数の共用資源が、例えば、トイレ、台所、コピー機、及びプリンタ等の既知の場所にある。そして、ノードがそれらの位置に対応する確率は、個々人と場所との間の潜在的な接続性の間接的な測定を与える。
【０１０８】
これらの確率は、接続の決定論的なグラフと個人の間の接続品質とを生成するために、２つ以上のクラスに群化できる。
【０１０９】
従来技術では、これらの種類の社会的な「ネットワーク」は、例えば、ＲＦＩＤタグやバッジ等の、人体に装着するセンサを使用することにより測定されているが、これらは、容易に失われたり破損し易く、また装着して検出するのに不快であったり、不便であるかもしれない。その環境に配置された間接的で、簡易なセンサからネットワークを推測することは、本発明の重要な利点である。
【０１１０】
予測
トラックレットがセンサ（ノード）Ａで開始するならば、そのノードに対する全ての終了確率のセットまたはサブセットは、次式の確率で与えられる。
【数１９】
2008211781.tif 000021
【０１１１】
ここで、そのトラックレットに対して最も確度の高い終了ノードを次式のように予測することが可能である。
【数２０】
2008211781.tif 000022
【０１１２】
また、確率により全ての終了ノードをランクにより順序付けして、エレベータ、照明、加熱システム、或いはその他の限られた環境資源に対する需要を予測するシステム等の確率的決定システムに対して、ウエイト（重り）として相対的（条件付き）確率を使用することも可能である。
【０１１３】
また、この技術は、より限定されたグラフを作ることによって、「Ａ、Ｒ、Ｓ、Ｚ」等のノードのサブセット（部分集合）を含めるようにその確率を次式のように一般化する。
【数２１】
2008211781.tif 000023
【０１１４】
ノードＡとＲとは、シーケンシャル（順次的、連続的）である必要はない。それらのノードは、グラフの可能性の高い（妥当な）部分の一部であればよい。すなわち、ノードＡとノードＲとの間、またノードＲとノードＺとの間には、中間ノードがあってもよい。これは、例えば、ノードＡとノードＲとの間に多くの同等のトラックがあるときに有用になり、ノードＲは、そのグラフにおいて特に有益なノードを表わす。
【０１１５】
このような形式は、１つ以上の中間ノードを含むサブセット（部分集合）を含むように延長することができる。次に、予測は、次式のように確率的な形式をとる。
【数２２】
2008211781.tif 000024
【０１１６】
図１１は、一般的な方法の各ステップ（工程）を示している。移動物体によって引き起こされたイベント１１１１は、ある環境において既知の位置に配設された一組のセンサ１０１により検出される１１１０。時間的及び空間的に隣接する一連のイベントは、一組のトラックレット１１２１を形成するようにリンクされている（繋がれている）１１２０。一組の有向グラフ１１３１がその一組のトラックレットから組み立てられる１１３０。それらのグラフは、少なくとも１つの開始ノード、少なくとも１つの終了ノード、及び複数のトラックレットが物体の動き（移動）に対して曖昧点を発生させながら接続する一つまたは複数の中間ノードを含む。確率１１４１は、その環境において物体の動きをモデル化するために、物体が特定の位置にあった尤度を示すように、エッジへ割り当てられる１１４０。それらの確率１１４１は、時間経過と共に学習１１４５された、動き（移動）のパターン１１４６等の情報に基づいて洗練されうる。そしてまた、それらの確率で注釈されたグラフは、物体の動きを予測するのに使用できる。
【０１１７】
本発明は、好適な実施の形態を例に挙げて説明したが、本発明の精神及び範囲内で種々の他の改変及び変更を行うことができることを理解すべきである。従って、添付クレームの目的は、本発明の真実の精神及び範囲に含まれるような全ての変形例及び変更例をカバーすることである。
【図面の簡単な説明】
【０１１８】
【図１】本発明の実施の形態に従ってトラッキングシステムが実施される環境を示す説明図である。
【図２】本発明の実施の形態によるトラックレット（小航跡）グラフを示す説明図である。
【図３】本発明の実施の形態による図１の環境における追跡物体の航跡を示すブロック図である。
【図４】本発明の実施の形態による決定グラフを示す説明図である。
【図５】本発明の実施の形態によるユーザインタフェースを示す画像である。
【図６】本発明の実施の形態による監視データを記録するための方法を示すフローチャートである。
【図７】本発明の実施の形態による物体を追跡するために監視データを検索する方法を示すフローチャートである。
【図８】運動（モーション）センサ及びトラックレットによって検出された離散的事象（イベント）を示す説明図である。
【図９】本発明の実施の形態によるトラックレット（小航跡）グラフを示す説明図である。
【図１０】本発明の実施の形態によるトラックレット（小航跡）グラフを示す説明図である。
【図１１】モデリング及び予測を行うための方法を示すフローチャートである。
【図１】
2008211781.tif 000029
【図２】
2008211781.tif 000030
【図３】
2008211781.tif 000031
【図４】
2008211781.tif 000032
【図５】
2008211781.tif 000033
【図６】
2008211781.tif 000034
【図７】
2008211781.tif 000035
【図８】
2008211781.tif 000036
【図９】
2008211781.tif 000037
【図１０】
2008211781.tif 000038
【図１１】
2008211781.tif 000039
【外国語明細書】
2008211781.tif 000040
2008211781.tif 000041
2008211781.tif 000042
2008211781.tif 000043
2008211781.tif 000044
2008211781.tif 000045
2008211781.tif 000046
2008211781.tif 000047
2008211781.tif 000048
2008211781.tif 000049
2008211781.tif 000050
2008211781.tif 000051
2008211781.tif 000052
2008211781.tif 000053
2008211781.tif 000054
2008211781.tif 000055
2008211781.tif 000056
2008211781.tif 000057
2008211781.tif 000058
2008211781.tif 000059
2008211781.tif 000060
2008211781.tif 000061
2008211781.tif 000062
2008211781.tif 000063
2008211781.tif 000064
2008211781.tif 000065
2008211781.tif 000066
2008211781.tif 000067
2008211781.tif 000068
2008211781.tif 000069
2008211781.tif 000070
2008211781.tif 000071
2008211781.tif 000072
2008211781.tif 000073
2008211781.tif 000074
2008211781.tif 000075
2008211781.tif 000076
2008211781.tif 000077
2008211781.tif 000078
2008211781.tif 000079
2008211781.tif 000080
2008211781.tif 000081
2008211781.tif 000082
2008211781.tif 000083
2008211781.tif 000084
2008211781.tif 000085
2008211781.tif 000086
2008211781.tif 000087
2008211781.tif 000088
2008211781.tif 000089
2008211781.tif 000090