追跡方法
本発明は、フレーム・シーケンス内の少なくとも１つの物体を追跡する方法であって、各フレームが画素アレイを有し、深さ値が各画素に関連付けられている方法に関する。この方法は、各フレームの前記画素の少なくともいくつかを複数の領域にグループ分けするステップと、前記領域を、相互接続された領域のクラスタＢ１，…，Ｂ５にグループ分けするステップと、２次元投影で別のクラスタＢ１に隣接する少なくとも１つのクラスタＢ２，…，Ｂ５が前記別のクラスタＢ１の深さ値よりも高い深さ値を有する場合に、少なくとも１つのクラスタＢ２，…，Ｂ５が前記別のクラスタＢ１によって部分的に遮蔽されている物体に属すると判断するステップを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フレーム・シーケンス内の少なくとも１つの物体を追跡する方法であって、各フレームが画素アレイ（ピクセル配列）を有し、深さ値が各画素に関連付けられている方法に関する。
【背景技術】
【０００２】
実世界物体を追跡するために、撮像デバイスに接続され、撮像デバイスによって生成されるビデオ・シーケンスで物体を追跡するようにプログラムされたデータ処理デバイスであって、ビデオ・シーケンスが連続するフレーム・シーケンスを有し、各シーケンスが画素アレイを有するデータ処理デバイスを使用することが、長きにわたり提案されている。
【０００３】
例えば、Ｗｅｉ Ｄｕ及びＪｕｓｔｕｓ Ｐｉａｔｅｒによる論文「Ｔｒａｃｋｉｎｇ ｂｙ Ｃｌｕｓｔｅｒ Ａｎａｌｙｓｉｓ ｏｆ Ｆｅａｔｕｒｅ Ｐｏｉｎｔｓ ｕｓｉｎｇ ａ Ｍｉｘｔｕｒｅ Ｐａｒｔｉｃｌｅ Ｆｉｌｔｅｒ」において、Ｈａｒｒｉｓコーナー検出器及びＬｕｃａｓ−Ｋａｎａｄｅトラッカを使用して、ビデオ・シーケンス内の物体を追跡するための方法が開示されている。しかしこの方法は、画素の深さ情報なしで２次元ビデオ・シーケンスに適用されるので、かなりのデータ処理要件にも関わらずその性能は限られる。
【０００４】
２次元画素アレイを有するビデオ・シーケンスで１つ又は複数の物体を追跡するための方法を開示するいくつかの他の関連の論文は以下のものである。
【０００５】
Ｓ． ＭｃＫｅｎｎａ、Ｓ． Ｊａｂｒｉ、Ｚ． Ｄｕｒｉｃ、及びＨ． Ｗｅｃｈｓｌｅｒ， “Ｔｒａｃｋｉｎｇ Ｇｒｏｕｐｓ ｏｆ Ｐｅｏｐｌｅ”， Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｉｍａｇｅ Ｕｎｄｅｒｓｔａｎｄｉｎｇ， ２０００
【０００６】
Ｆ． Ｂｒｅｍｏｎｄ及びＭ． Ｔｈｏｎｎａｔ， “Ｔｒａｃｋｉｎｇ ｍｕｌｔｉｐｌｅ ｎｏｎｒｉｇｉｄ ｏｂｊｅｃｔｓ ｉｎ ｖｉｄｅｏ ｓｅｑｕｅｎｃｅｓ”， ＩＥＥＥ Ｔｒａｎｓ． Ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ ｆｏｒ Ｖｉｄｅｏ Ｔｅｃｈｎｉｑｕｅｓ， １９９８
【０００７】
Ｉ Ｈａｒｉｔａｏｇｌｕ， “Ａ Ｒｅａｌ Ｔｉｍｅ Ｓｙｓｔｅｍ ｆｏｒ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｔｒａｃｋｉｎｇ ｏｆ Ｐｅｏｐｌｅ ａｎｄ Ｒｅｃｏｇｎｉｚｉｎｇ Ｔｈｅｉｒ Ａｃｔｉｖｉｔｉｅｓ”， Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｍａｒｙｌａｎｄ， １９９８
【０００８】
Ｇ． Ｐｉｎｇａｌｉ、Ｙ． Ｊｅａｎ、及びＡ． Ｏｐａｌａｃｈ， “Ｂａｌｌ Ｔｒａｃｋｉｎｇ ａｎｄ Ｖｉｒｔｕａｌ Ｒｅｐｌａｙｓ ｆｏｒ Ｉｎｎｏｖａｔｉｖｅ Ｔｅｎｎｉｓ Ｂｒｏａｄｃａｓｔｓ”， １５ｔｈ Ｉｎｔ． Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ
【０００９】
しかし、これらの追跡方法は、直接の画素深さ情報なしで２Ｄビデオ・シーケンスで実施されるので、色、形状、又はテクスチャなど他の物体属性に基づいてしか画像セグメント化を行うことができないため、それらの性能は必然的に限られる。
【００１０】
例えば国際公開第２００８／１２８５６８号で、各フレームの各画素に深さ値が関連付けられたビデオ・シーケンスを提供する３Ｄ撮像システムを使用することが既に提案されている。そのような追跡方法は、純粋に２次元の画像に基づくものよりも、追跡される物体に関する有用な位置情報をはるかに多く生成する。特に、３Ｄ撮像システムの使用は、前景と背景の区別を容易にする。しかし、開示された方法は、複数の物体を追跡するという問題には対処しておらず、特に、３Ｄ撮像システムの視野内で別の物体によって少なくとも部分的に遮蔽された物体を追跡するという問題には対処していない。国際公開第２００８／１２８５６８号では、３次元空間内のボリュームを認識するための方法であって、３次元画像データが３次元空間内に複数の点を有する方法が開示されている。これらの点はクラスタ化され、クラスタが、対象の点として選択される。選択されたクラスタ内部の点は、サブクラスタにさらにグループ分けされ、サブクラスタはそれぞれ、重心と、重心に関連付けられるボリュームとを有する。重心は、物体を示すネットワークを形成するために接続することができ、末端の重心は、ただ１つの他の重心に接続された重心として識別される。
【００１１】
３Ｄビデオ・シーケンスを使用しており、しかし遮蔽の問題に対処できていない他の追跡方法は、Ａ． Ａｚｅｒｂａｙｅｒｊａｎｉ及びＣ． Ｗｒｅｎによって“Ｒｅａｌ−Ｔｉｍｅ ３Ｄ Ｔｒａｃｋｉｎｇ ｏｆ ｔｈｅ Ｈｕｍａｎ Ｂｏｄｙ”， Ｐｒｏｃ． ｏｆ Ｉｍａｇｅ’ｃｏｍ， １９９６において開示されており、また、Ｔ． Ｏｌｓｏｎ及びＦ． Ｂｒｉｌｌによって“Ｍｏｖｉｎｇ Ｏｂｊｅｃｔ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｅｖｅｎｔ Ｒｅｃｏｇｎｉｔｉｏｎ Ａｌｇｏｒｉｔｈｍｓ Ｆｏｒ Ｓｍａｒｔ Ｃａｍｅｒａｓ”， Ｐｒｏｃ． Ｉｍａｇｅ Ｕｎｄｅｒｓｔａｎｄｉｎｇ Ｗｏｒｋｓｈｏｐ， １９９７においても開示されている。
【００１２】
いくつかの他の開示は、この遮蔽の問題に対処している。いくつかの様々な方法が、リエージュ大学（Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｌｉｅｇｅ）の電子工学及びコンピュータ・サイエンス科（ｔｈｅ Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｅｌｅｃｔｒｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ）のＰｉｅｒｒｅ Ｆ． Ｇａｂｒｉｅｌ、Ｊａｃｑｕｅｓ Ｇ． Ｖｅｒｌｙ、Ｊｕｓｔｕｓ Ｈ． Ｐｉａｔｅｒ、及びＡｎｄｒｅ Ｇｅｎｏｎによって、“Ｔｈｅ Ｓｔａｔｅ ｏｆ ｔｈｅ Ａｒｔ ｉｎ Ｍｕｌｔｉｐｌｅ Ｏｂｊｅｃｔ Ｔｒａｃｋｉｎｇ Ｕｎｄｅｒ Ｏｃｃｌｕｓｉｏｎ ｉｎ Ｖｉｄｅｏ Ｓｅｑｕｅｎｃｅｓ”という論文で提示されている。
【００１３】
この遮蔽の問題に対処する追跡方法は、Ａ． Ｅｌｇａｍｍａｌ及びＬ．Ｓ． Ｄａｖｉｓが“Ｐｒｏｂａｂｉｌｉｓｔｉｃ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｓｅｇｍｅｎｔｉｎｇ ｐｅｏｐｌｅ ｕｎｄｅｒ ｏｃｃｌｕｓｉｏｎ”， Ｐｒｏｃ． ｏｆ ＩＥＥＥ ８ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ， ２００１において開示しており、またＩ． Ｈａｒｉｔａｏｇｌｕ、Ｄ． Ｈａｒｗｏｏｄ、及びＬ． Ｄａｖｉｓが“Ｈｙｄｒａ： Ｍｕｌｔｉｐｌｅ Ｐｅｏｐｌｅ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｔｒａｃｋｉｎｇ”， Ｗｏｒｋｓｈｏｐ ｏｆ Ｖｉｄｅｏ Ｓｕｒｖｅｉｌｌａｎｃｅ， １９９９において開示しており、またＳ． Ｋｈａｎ及びＭ． Ｓｈａｈが“Ｔｒａｃｋｉｎｇ Ｐｅｏｐｌｅ ｉｎ Ｐｒｅｓｅｎｃｅ ｏｆ Ｏｃｃｌｕｓｉｏｎ”， Ａｓｉａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ”， ２０００において開示しており、またＨ．Ｋ． Ｒｏｈ及びＳ．Ｗ． Ｌｅｅが“Ｍｕｌｔｉｐｌｅ Ｐｅｏｐｌｅ Ｔｒａｃｋｉｎｇ Ｕｓｉｎｇ ａｎ Ａｐｐｅａｒａｎｃｅ Ｍｏｄｅｌ Ｂａｓｅｄ ｏｎ Ｔｅｍｐｏｒａｌ Ｃｏｌｏｒ”， Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， ２０００において開示しており、またＡ．Ｗ． Ｓｅｎｉｏｒ、Ａ． Ｈａｍｐａｐｕｒ、Ｌ．Ｍ． Ｂｒｏｗｎ、Ｙ． Ｔｉａｎ、Ｓ． Ｐａｎｋａｎｔｉ、及びＲ． Ｍ． Ｂｏｌｌｅが“Ａｐｐｅａｒａｎｃｅ Ｍｏｄｅｌｓ ｆｏｒ Ｏｃｃｌｕｓｉｏｎ Ｈａｎｄｌｉｎｇ”， ２ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｐｒｅｆｏｒｍａｎｃｅ Ｅｖａｌｕａｔｉｏｎ ｏｆ Ｔｒａｃｋｉｎｇ ａｎｄ Ｓｕｒｖｅｉｌｌａｎｃｅ Ｓｙｓｔｅｍｓ”， ２００１において開示している。しかし、これらの方法は全て、深さデータはなんら有さずに、２次元画素アレイのみを有する２Ｄ又はステレオビデオ・シーケンスに基づいているので、それらの性能は限られる。
【００１４】
トップダウン・シーン・ビューに基づく物体追跡方法を、Ａ． Ｆ． Ｂｏｂｉｃｋ他が“Ｔｈｅ ＫｉｄｓＲｏｏｍ： Ａ ｐｅｒｃｅｐｔｕａｌｌｙ ｂａｓｅｄ ｉｎｔｅｒａｃｔｉｖｅ ａｎｄ ｉｍｍｅｒｓｉｖｅ ｓｔｏｒｙ ｅｎｖｉｒｏｎｍｅｎｔ”， Ｔｅｌｅｏｐｅｒａｔｏｒｓ ａｎｄ Ｖｉｒｔｕａｌ Ｅｎｖｉｒｏｎｒｍｅｎｔ， １９９９において開示しており、またＲ．Ｔ． Ｃｏｌｌｉｎｓ、Ａ．Ｊ． Ｌｉｐｔｏｎ、及びＴ． Ｋａｎａｄｅが“Ａ Ｓｙｓｔｅｍ ｆｏｒ Ｖｉｄｅｏ Ｓｕｒｖｅｉｌｌａｎｃｅ ａｎｄ Ｍｏｎｉｔｏｒｉｎｇ”， Ｐｒｏｃ． ８ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｔｏｐｉｃａｌ Ｍｅｅｔｉｎｇ ｏｎ Ｒｏｂｏｔｉｃｓ ａｎｄ Ｒｅｍｏｔｅ Ｓｙｓｔｅｍｓ， １９９９において開示しており、またＷ．Ｅ．Ｌ． Ｇｒｉｍｓｏｎ、Ｃ． Ｓｔａｕｆｆｅｒ、Ｒ． Ｒｏｍａｎｏ、及びＬ． Ｌｅｅが“Ｕｓｉｎｇ ａｄａｐｔｉｖｅ ｔｒａｃｋｉｎｇ ｔｏ ｃｌａｓｓｉｆｙ ａｎｄ ｍｏｎｉｔｏｒ ａｃｔｉｖｉｔｉｅｓ ｉｎ ａ ｓｉｔｅ”， Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎにおいて開示しており、またＡ． Ｂｅｖｉｌａｃｑｕａ、Ｌ． Ｄｉ Ｓｔｅｆａｎｏ、及びＰ． Ｔａｚｚａｒｉが“Ｐｅｏｐｌｅ ｔｒａｃｋｉｎｇ ｕｓｉｎｇ ａ ｔｉｍｅ−ｏｆ−ｆｌｉｇｈｔ ｄｅｐｔｈ ｓｅｎｓｏｒ”， ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｖｉｄｅｏ ａｎｄ Ｓｉｇｎａｌ Ｂａｓｅｄ Ｓｕｒｖｅｉｌｌａｎｃｅ， ２００６において開示している。しかし、その結果、追跡される物体に関して入手できる情報は、特にその物体が人間ユーザであるときには制限される。
【００１５】
Ｄａｎ Ｗｉｔｚｎｅｒ Ｈａｎｓｅｎ、Ｍａｄｓ Ｓｙｓｋａ Ｈａｎｓｅｎ、Ｍａｒｔｉｎ Ｋｉｒｓｃｈｍｅｙｅｒ、Ｒａｓｍｕｓ Ｌａｒｓｅｎ、及びＤａｖｉｄｅ Ｓｉｌｖｅｓｔｒｅが“Ｃｌｕｓｔｅｒ ｔｒａｃｋｉｎｇ ｗｉｔｈ ｔｉｍｅ−ｏｆ−ｆｌｉｇｈｔ ｃａｍｅｒａｓ”， ２００８ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ Ｗｏｒｋｓｈｏｐｓにおいて、やはりホモグラフィ平面内で、すなわち「トップダウン」ビューで物体が追跡される物体追跡方法を開示している。この方法は、期待値最大化アルゴリズムを使用する。しかし、この方法もまた、追跡された物体が人間ユーザである場合には、ジェスチャの認識に十分には適合しない。
【００１６】
また、Ｌｅｉｌａ Ｓａｂｅｔｉ、Ｅｈｓａｎ Ｐａｒｖｉｚｉ、及びＱ．Ｍ． Ｊｏｎａｔｈａｎ Ｗｕが、“Ｖｉｓｕａｌ Ｔｒａｃｋｉｎｇ Ｕｓｉｎｇ Ｃｏｌｏｕｒ Ｃａｍｅｒａｓ ａｎｄ Ｔｉｍｅ−ｏｆ−Ｆｌｉｇｈｔ Ｒａｎｇｅ Ｉｍａｇｉｎｇ Ｓｅｎｓｏｒｓ”， Ｊｏｕｒｎａｌ ｏｆ Ｍｕｌｔｉｍｅｄｉａ， Ｖｏｌ． ３， Ｎｏ． ２， Ｊｕｎｅ ２００８において、画素深さデータを有する３Ｄビデオ・シーケンスを使用する物体追跡方法を提示している。しかし、モンテカルロベースの「パーティクル・フィルタ」追跡方法を使用するこの方法はまた、かなりのデータ処理リソースを必要とする。
【００１７】
米国特許出願公開第２００６／２３９５５８号は、シーンの画像を生成する３次元撮像システムを開示する。シーンの画像内の画素は、その画素がシーン内のどの物体に関係付けられているかに応じてラベル付けされて、値を割り当てられる。同じラベルを有する画素のグループは、「ブロブ」を生成するようにグループ分けされ、各ブロブが異なる物体に対応している。ブロブが定義されると、それらは、円や長方形など様々な形状の基本形、或いは人、動物、又は車など他の事前定義された物体にモデル化又は量子化される。シーン内の画素のクラスタ化及びそれらの関連付けられた深さ値を使用して、画素の深さ値に従って、その画素が特定のクラスタに属するかどうか判断する。したがって画素は、隣接する画素と同じ深さである場合には、隣接する画素が属するクラスタと同じラベルを割り当てられる。
【００１８】
米国特許第６７１８１８号は、シーン内の別個の３次元領域又は「ブロブ」を選択的にクラスタ化して、「ブロブ」クラスタを物体認識に関するモデルと比較することによって、シーン内で対象の人及び物体を識別及び位置特定するための方法を開示する。対象のシーンの初期３次元深さ画像が生成される。３次元ボリューム内での３次元画像画素の空間座標が画像によって表される。人又は物体の識別及び位置特定は、作業画像を処理することによって決定され、作業画像は、初期３次元深さ画像とライブ深さ画像を使用した背景差分プロセスから得られ、その際、初期３次元深さ画像とは大きく異なるライブ深さ画像内の任意の画素が作業画像の一部となり、作業画像は、いくつかの別個の３次元領域又は「ブロブ」を含む。「ブロブ」を処理して、各ブロブがどの人又は物体に属するかが識別される。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】国際公開第２００８／１２８５６８号
【特許文献２】米国特許出願公開第２００６／２３９５５８号
【特許文献３】米国特許第６７１８１８号
【非特許文献】
【００２０】
【非特許文献１】Ｗｅｉ Ｄｕ及びＪｕｓｔｕｓ Ｐｉａｔｅｒによる論文「Ｔｒａｃｋｉｎｇ ｂｙ Ｃｌｕｓｔｅｒ Ａｎａｌｙｓｉｓ ｏｆ Ｆｅａｔｕｒｅ Ｐｏｉｎｔｓ ｕｓｉｎｇ ａ Ｍｉｘｔｕｒｅ Ｐａｒｔｉｃｌｅ Ｆｉｌｔｅｒ」
【非特許文献２】Ｓ． ＭｃＫｅｎｎａ、Ｓ． Ｊａｂｒｉ、Ｚ． Ｄｕｒｉｃ、及びＨ． Ｗｅｃｈｓｌｅｒ， “Ｔｒａｃｋｉｎｇ Ｇｒｏｕｐｓ ｏｆ Ｐｅｏｐｌｅ”， Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｉｍａｇｅ Ｕｎｄｅｒｓｔａｎｄｉｎｇ， ２０００
【非特許文献３】Ｆ． Ｂｒｅｍｏｎｄ及びＭ． Ｔｈｏｎｎａｔ， “Ｔｒａｃｋｉｎｇ ｍｕｌｔｉｐｌｅ ｎｏｎｒｉｇｉｄ ｏｂｊｅｃｔｓ ｉｎ ｖｉｄｅｏ ｓｅｑｕｅｎｃｅｓ”， ＩＥＥＥ Ｔｒａｎｓ． Ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ ｆｏｒ Ｖｉｄｅｏ Ｔｅｃｈｎｉｑｕｅｓ， １９９８
【非特許文献４】Ｉ Ｈａｒｉｔａｏｇｌｕ， “Ａ Ｒｅａｌ Ｔｉｍｅ Ｓｙｓｔｅｍ ｆｏｒ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｔｒａｃｋｉｎｇ ｏｆ Ｐｅｏｐｌｅ ａｎｄ Ｒｅｃｏｇｎｉｚｉｎｇ Ｔｈｅｉｒ Ａｃｔｉｖｉｔｉｅｓ”， Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｍａｒｙｌａｎｄ， １９９８
【非特許文献５】Ｇ． Ｐｉｎｇａｌｉ、Ｙ． Ｊｅａｎ、及びＡ． Ｏｐａｌａｃｈ， “Ｂａｌｌ Ｔｒａｃｋｉｎｇ ａｎｄ Ｖｉｒｔｕａｌ Ｒｅｐｌａｙｓ ｆｏｒ Ｉｎｎｏｖａｔｉｖｅ Ｔｅｎｎｉｓ Ｂｒｏａｄｃａｓｔｓ”， １５ｔｈ Ｉｎｔ． Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ
【非特許文献６】Ａ． Ａｚｅｒｂａｙｅｒｊａｎｉ及びＣ． Ｗｒｅｎ“Ｒｅａｌ−Ｔｉｍｅ ３Ｄ Ｔｒａｃｋｉｎｇ ｏｆ ｔｈｅ Ｈｕｍａｎ Ｂｏｄｙ”， Ｐｒｏｃ． ｏｆ Ｉｍａｇｅ’ｃｏｍ， １９９６
【非特許文献７】Ｔ． Ｏｌｓｏｎ及びＦ． Ｂｒｉｌｌ“Ｍｏｖｉｎｇ Ｏｂｊｅｃｔ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｅｖｅｎｔ Ｒｅｃｏｇｎｉｔｉｏｎ Ａｌｇｏｒｉｔｈｍｓ Ｆｏｒ Ｓｍａｒｔ Ｃａｍｅｒａｓ”， Ｐｒｏｃ． Ｉｍａｇｅ Ｕｎｄｅｒｓｔａｎｄｉｎｇ Ｗｏｒｋｓｈｏｐ， １９９７
【非特許文献８】リエージュ大学（Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｌｉｅｇｅ）の電子工学及びコンピュータ・サイエンス科（ｔｈｅ Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｅｌｅｃｔｒｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ）のＰｉｅｒｒｅ Ｆ． Ｇａｂｒｉｅｌ、Ｊａｃｑｕｅｓ Ｇ． Ｖｅｒｌｙ、Ｊｕｓｔｕｓ Ｈ． Ｐｉａｔｅｒ、及びＡｎｄｒｅ Ｇｅｎｏｎによる論文“Ｔｈｅ Ｓｔａｔｅ ｏｆ ｔｈｅ Ａｒｔ ｉｎ Ｍｕｌｔｉｐｌｅ Ｏｂｊｅｃｔ Ｔｒａｃｋｉｎｇ Ｕｎｄｅｒ Ｏｃｃｌｕｓｉｏｎ ｉｎ Ｖｉｄｅｏ Ｓｅｑｕｅｎｃｅｓ”
【非特許文献９】Ａ． Ｅｌｇａｍｍａｌ及びＬ．Ｓ． Ｄａｖｉｓ“Ｐｒｏｂａｂｉｌｉｓｔｉｃ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｓｅｇｍｅｎｔｉｎｇ ｐｅｏｐｌｅ ｕｎｄｅｒ ｏｃｃｌｕｓｉｏｎ”， Ｐｒｏｃ． ｏｆ ＩＥＥＥ ８ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ， ２００１
【非特許文献１０】Ｉ． Ｈａｒｉｔａｏｇｌｕ、Ｄ． Ｈａｒｗｏｏｄ、及びＬ． Ｄａｖｉｓ“Ｈｙｄｒａ： Ｍｕｌｔｉｐｌｅ Ｐｅｏｐｌｅ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｔｒａｃｋｉｎｇ”， Ｗｏｒｋｓｈｏｐ ｏｆ Ｖｉｄｅｏ Ｓｕｒｖｅｉｌｌａｎｃｅ， １９９９
【非特許文献１１】Ｓ． Ｋｈａｎ及びＭ． Ｓｈａｈ“Ｔｒａｃｋｉｎｇ Ｐｅｏｐｌｅ ｉｎ Ｐｒｅｓｅｎｃｅ ｏｆ Ｏｃｃｌｕｓｉｏｎ”， Ａｓｉａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ”， ２０００
【非特許文献１２】Ｈ．Ｋ． Ｒｏｈ及びＳ．Ｗ． Ｌｅｅ“Ｍｕｌｔｉｐｌｅ Ｐｅｏｐｌｅ Ｔｒａｃｋｉｎｇ Ｕｓｉｎｇ ａｎ Ａｐｐｅａｒａｎｃｅ Ｍｏｄｅｌ Ｂａｓｅｄ ｏｎ Ｔｅｍｐｏｒａｌ Ｃｏｌｏｒ”， Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， ２０００
【非特許文献１３】Ａ．Ｗ． Ｓｅｎｉｏｒ、Ａ． Ｈａｍｐａｐｕｒ、Ｌ．Ｍ． Ｂｒｏｗｎ、Ｙ． Ｔｉａｎ、Ｓ． Ｐａｎｋａｎｔｉ、及びＲ． Ｍ． Ｂｏｌｌｅ“Ａｐｐｅａｒａｎｃｅ Ｍｏｄｅｌｓ ｆｏｒ Ｏｃｃｌｕｓｉｏｎ Ｈａｎｄｌｉｎｇ”， ２ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｐｒｅｆｏｒｍａｎｃｅ Ｅｖａｌｕａｔｉｏｎ ｏｆ Ｔｒａｃｋｉｎｇ ａｎｄ Ｓｕｒｖｅｉｌｌａｎｃｅ Ｓｙｓｔｅｍｓ”， ２００１
【非特許文献１４】Ａ． Ｆ． Ｂｏｂｉｃｋ他“Ｔｈｅ ＫｉｄｓＲｏｏｍ： Ａ ｐｅｒｃｅｐｔｕａｌｌｙ ｂａｓｅｄ ｉｎｔｅｒａｃｔｉｖｅ ａｎｄ ｉｍｍｅｒｓｉｖｅ ｓｔｏｒｙ ｅｎｖｉｒｏｎｍｅｎｔ”， Ｔｅｌｅｏｐｅｒａｔｏｒｓ ａｎｄ Ｖｉｒｔｕａｌ Ｅｎｖｉｒｏｎｒｍｅｎｔ， １９９９
【非特許文献１５】Ｒ．Ｔ． Ｃｏｌｌｉｎｓ、Ａ．Ｊ． Ｌｉｐｔｏｎ、及びＴ． Ｋａｎａｄｅ“Ａ Ｓｙｓｔｅｍ ｆｏｒ Ｖｉｄｅｏ Ｓｕｒｖｅｉｌｌａｎｃｅ ａｎｄ Ｍｏｎｉｔｏｒｉｎｇ”， Ｐｒｏｃ． ８ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｔｏｐｉｃａｌ Ｍｅｅｔｉｎｇ ｏｎ Ｒｏｂｏｔｉｃｓ ａｎｄ Ｒｅｍｏｔｅ Ｓｙｓｔｅｍｓ， １９９９
【非特許文献１６】Ｗ．Ｅ．Ｌ． Ｇｒｉｍｓｏｎ、Ｃ． Ｓｔａｕｆｆｅｒ、Ｒ． Ｒｏｍａｎｏ、及びＬ． Ｌｅｅ“Ｕｓｉｎｇ ａｄａｐｔｉｖｅ ｔｒａｃｋｉｎｇ ｔｏ ｃｌａｓｓｉｆｙ ａｎｄ ｍｏｎｉｔｏｒ ａｃｔｉｖｉｔｉｅｓ ｉｎ ａ ｓｉｔｅ”， Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ
【非特許文献１７】Ａ． Ｂｅｖｉｌａｃｑｕａ、Ｌ． Ｄｉ Ｓｔｅｆａｎｏ、及びＰ． Ｔａｚｚａｒｉ“Ｐｅｏｐｌｅ ｔｒａｃｋｉｎｇ ｕｓｉｎｇ ａ ｔｉｍｅ−ｏｆ−ｆｌｉｇｈｔ ｄｅｐｔｈ ｓｅｎｓｏｒ”， ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｖｉｄｅｏ ａｎｄ Ｓｉｇｎａｌ Ｂａｓｅｄ Ｓｕｒｖｅｉｌｌａｎｃｅ， ２００６
【非特許文献１８】Ｄａｎ Ｗｉｔｚｎｅｒ Ｈａｎｓｅｎ、Ｍａｄｓ Ｓｙｓｋａ Ｈａｎｓｅｎ、Ｍａｒｔｉｎ Ｋｉｒｓｃｈｍｅｙｅｒ、Ｒａｓｍｕｓ Ｌａｒｓｅｎ、及びＤａｖｉｄｅ Ｓｉｌｖｅｓｔｒｅ“Ｃｌｕｓｔｅｒ ｔｒａｃｋｉｎｇ ｗｉｔｈ ｔｉｍｅ−ｏｆ−ｆｌｉｇｈｔ ｃａｍｅｒａｓ”， ２００８ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ Ｗｏｒｋｓｈｏｐｓ
【非特許文献１９】Ｌｅｉｌａ Ｓａｂｅｔｉ、Ｅｈｓａｎ Ｐａｒｖｉｚｉ、及びＱ．Ｍ． Ｊｏｎａｔｈａｎ Ｗｕ“Ｖｉｓｕａｌ Ｔｒａｃｋｉｎｇ Ｕｓｉｎｇ Ｃｏｌｏｕｒ Ｃａｍｅｒａｓ ａｎｄ Ｔｉｍｅ−ｏｆ−Ｆｌｉｇｈｔ Ｒａｎｇｅ Ｉｍａｇｉｎｇ Ｓｅｎｓｏｒｓ”， Ｊｏｕｒｎａｌ ｏｆ Ｍｕｌｔｉｍｅｄｉａ， Ｖｏｌ． ３， Ｎｏ． ２， Ｊｕｎｅ ２００８
【発明の概要】
【発明が解決しようとする課題】
【００２１】
本発明の目的は、画素深さ情報を用いてフレーム・シーケンス内の物体を追跡するための方法であって、部分的に遮蔽されている物体でさえ確実に追跡し、それと同時に、３次元空間内での追跡された物体の形状に関する情報を提供し、それをジェスチャ認識のために適用することができる方法を提供することである。
【課題を解決するための手段】
【００２２】
一実施例では、本発明によるコンピュータ実装方法は、
−画素深さ情報を備えるフレーム・シーケンスの各フレームの画素の少なくともいくつかを複数の領域にグループ分けするステップと、
−前記領域を、相互接続された領域のクラスタにグループ分けするステップと、
−２次元投影で別のクラスタに隣接する少なくとも１つのクラスタが前記別のクラスタの深さ値よりも高い深さ値を有する場合に、前記少なくとも１つのクラスタが前記別のクラスタによって部分的に遮蔽されている物体に属すると判断するステップと
を含む。
【００２３】
「深さ値」という用語は、前記ビデオ・シーケンスを捕捉する撮像デバイスの位置とは無関係に、前記２次元投影の平面に垂直な深さの値を意味するものとする。深さ値は、撮像デバイスからの画素の距離である。したがって、１つのクラスタ（又はそのクラスタ内の画素）の深さ値は、撮像デバイスからより遠くに離れていることにより、別のクラスタ（又は別のクラスタ内の画素）の深さ値よりも高い値を有することができる。
【００２４】
本発明のさらなる目的は、単一の部分的に遮蔽されている物体に属するクラスタをつなぎ合わせることである。
【００２５】
このために、前記２次元投影で前記別のクラスタへの隣接性を共に有し且つ前記別のクラスタよりも高い深さ値を有する２つのクラスタが、前記別のクラスタによって部分的に遮蔽されている単一の物体に属するかどうかを、前記より高い深さ値が互いに所定の範囲Δｄ１内にあるかどうかに応じて判断することができる。
【００２６】
また、前記２次元投影で前記別のクラスタへの隣接性を共に有し且つ前記別のクラスタよりも高い深さ値を有する２つのクラスタが、前記別のクラスタによって部分的に遮蔽されている単一の物体に属するかどうかを、前記２次元投影の少なくとも１つの軸において前記２つのクラスタのそれぞれが前記２つのクラスタの他方と少なくとも最小長さにわたって重畳しているかどうかに応じて判断することができる。
【００２７】
これら２つの条件は、個別に、又は同時に適用することができる。これら２つの条件のそれぞれを包含的条件として適用することができ、したがって条件が満たされる場合に、２つのクラスタが単一の物体に属するものとみなされる。しかしこれは、条件が満たされない場合も依然として除外されてはいない。しかし、それぞれの条件を排他的条件として適用することもでき、これは、クラスタがその条件を満たさない場合には、それらのクラスタが単一の物体に属することが除外されることを意味する。特定の実施例では、各条件はさらに、包含及び排他のための様々なしきい値を使用して、包含的及び排他的に個別に適用することができる。
【００２８】
したがってこの追跡方法により、別の物体によって部分的に遮蔽されているときでさえ、物体の追跡を続けることができる。遮っているクラスタからはみ出した領域であって、それらの相対位置により、確実に互いにリンクさせることができる領域は、部分的に遮蔽された物体に属するものとして識別される。さらにこれは、限られた計算リソース消費で実現され、それと同時に、相互接続された領域のクラスタによって、追跡される物体の３次元形状に関する有用な情報を提供する。
【００２９】
対照的に、米国特許出願公開第２００６／２３９５５８号は、画素の深さ値に従って、シーン内の画素に同じラベルを割り振る。これは、シーン内の異なる別個の物体に属する画素が、同一の物体として誤って識別される可能性があることを意味する。
【００３０】
米国特許第６７７１８１８号では、識別されたクラスタをモデルと比較して、遮蔽されている可能性がある物体に画素が属するかどうかを判断する。
【００３１】
有利には、画素は、ベクトル量子化アルゴリズムを使用していくつかの領域にグループ分けすることができる。特に、前記ベクトル量子化アルゴリズムにおいて、
−第１のフレームにおいて、ｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムを使用して画素をＫ個の領域にグループ分けすることができ、
−後続のフレームにおいて、
・制約付きＫ−ｍｅａｎｓアルゴリズムを使用して、画素を前のフレームの領域にグループ分けし、距離制約を使用して、これらの領域のうちの任意の領域の重心から所定の距離Ｑよりも離れている画素を排除し、
・ｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムを使用して、残っている画素があればそれを新たな領域にグループ分けし、
・最後に、この後続のフレームにおいて、前のフレームの領域にいかなる画素も割り当てられていない場合には、その領域を削除することができ、数値Ｋを１だけ減分する。
【００３２】
特に、前記ｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムにおいて、
・画素が領域重心から前記距離Ｑよりも離れている場合には、新たな領域が生成され、数値Ｋが１だけ増分され、また
・画素が領域重心から前記距離Ｑ以内にある場合には、その画素は対応する領域に割り当てられ、それに従って重心の位置が更新される。
【００３３】
そのようなｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムは、いくつかの領域への画素の均一な分散を可能にし、それと同時に、領域の粒度を実質的に一定に保ち、領域の連続的なリフレッシュを保証し、計算リソース消費を制限する。
【００３４】
有利には、
−それら２つの領域の一方での少なくとも１つの画素とそれら２つの領域の他方での別の画素が２次元投影で隣接する場合、及び
−これら２つの領域の隣接する画素の各対における深さの平均差が、前記所定の距離Δｄ１未満である場合
に、２つの領域が３次元空間内で接続されていると判断することができる。
【００３５】
２つの画素は、それらが前記２次元投影で少なくとも１方向で所定の距離以内にある場合に、２次元投影で隣接しているとみなすことができる。
【００３６】
これらの基準により、空間内の単一の物体又は接続された複数の物体の点を表現する画素をグループ分けする複数の領域を、単一のクラスタにグループ分けすることができる。
【００３７】
さらに有利には、後続のフレームにおいて、前のフレームには存在しなかった新たな領域が前記３次元空間内で直接又は少なくとも１つの別の領域を介して前記既存のクラスタの領域に接続されている場合に、前記新たな領域が、前記前のフレームに既に存在していた相互接続された領域の既存のクラスタに属すると判断することができる。したがって、各クラスタの内容は、各後続のフレームにおいて新たに存在する候補領域があればそれを考慮に入れて、連続的に更新することができる。
【００３８】
有利には、本発明による方法の好ましい一実施例は、前記画素を領域にグループ分けする前に、基準フレーム内の対応する画素の深さ値と所定量Δｄ２未満しか異ならない各画素を前記シーケンス内の各フレームから削除する別のステップを含むことができる。したがって、基準フレーム内に既に存在していた背景から前景物体が切り離され、コンピュータ実装追跡方法の計算要件をさらに低減させる。
【００３９】
有利には、前記フレーム・シーケンスは、実世界シーンを捕捉する３Ｄ撮像デバイスからのビデオ・シーケンスでよい。したがって、本発明のこの実施例によるコンピュータ実装追跡方法は、例えばビデオ・ゲーム、シミュレーション、仮想環境、遠隔操作などの用途で、コンピュータ・システムとのリアルタイム対話、例えば命令又はデータの入力のために使用することができる。
【００４０】
さらに有利には、本発明のこの実施例において、画素を領域にグループ分けするステップの前に、撮像デバイスにリンクされた座標系から、前記実世界シーンでの点にリンクされた別の座標系に座標変換を行うことができる。このステップにより、画素座標を、本発明による追跡方法の後続のステップを単純化する別の座標系に変換することができる。
【００４１】
本発明のさらなる目的は、連続するフレーム・シーケンスを含む３次元ビデオ・シーケンスで少なくとも１つの物体を追跡する方法であって、各フレームが画素アレイを備え、深さ値が各画素に関連付けられる方法を使用する用途で、物体のアクティブ化及び／又は非アクティブ化を管理することである。
【００４２】
したがって、本発明の有利な実施例による方法は、さらに、前記シーケンスの少なくとも１つのフレームに関して、物体が第１の組のアクティブ化基準を満たす場合には、前記フレーム内で物体を予備アクティブ化するステップと、所定のアクティブ化規則の下で物体が第２の組のアクティブ化基準を満たす場合には、予備アクティブ状態の物体をアクティブ化するステップとを含むことができる。したがって、第１の組のアクティブ化基準は、第１の絶対フィルタとして働く。予備アクティブ状態の物体のその後のアクティブ化は、各予備アクティブ状態の物体が第２の組のアクティブ化基準を満たすかどうかに依存するだけでなく、アクティブ化規則にも依存する。
【００４３】
有利には、前記第１の組のアクティブ化基準及び／又は前記第２の組のアクティブ化基準が、
−アクティブ化又は非アクティブ化することができる物体の最大数、
−物体の位置、
−物体のサイズ、
−物体の動き、
−物体の形状、
−物体の色、
−物体が非アクティブ状態を保っている、連続する前のフレームの最大数、又は
−ユーザ選択
のうちの少なくとも１つの基準を含むことができる。
【００４４】
有利には、前記アクティブ化規則は、
−第２の組のアクティブ化基準を満たす全ての予備アクティブ状態の物体をアクティブ化する強制アクティブ化規則、
−アクティブ状態の物体が非アクティブ化される場合にのみ、前記第２の組のアクティブ化基準を満たす物体をアクティブ化するランク付きアクティブ化規則、
−前記第２の組のアクティブ化基準を最も良く満たす物体をアクティブ化する単純アクティブ化規則、
−関連し合う別のアクティブ状態の物体が非アクティブ化された場合に物体をアクティブ化する単純交換アクティブ化規則、
−別の物体によって遮蔽される又は遮蔽されている場合に物体をアクティブ化する遮蔽アクティブ化規則、又は
−別のアクティブ状態の物体に接触する場合に物体をアクティブ化する接触交換アクティブ化規則
からなる１組のアクティブ化規則のうちの１つでよい。
【００４５】
これらのアクティブ化基準及び規則は、本発明の物体追跡方法に基づいて、広い範囲の対話の可能性を開く。
【００４６】
さらに有利には、本発明による方法の一実施例はまた、前記シーケンスの少なくとも１つの後続のフレームに関して、所定の非アクティブ化規則の下で物体が１組の非アクティブ化基準を満たす場合に、事前にアクティブ化されている物体を非アクティブ化するステップを含むこともできる。
【００４７】
非アクティブ化基準の前記組は、
−アクティブ化又は非アクティブ化することができる物体の最大数、
−物体の位置、
−物体の形状、
−物体の色、
−物体ランキング、
−物体がアクティブ状態を保っている、連続する前のフレームの最大数及び／又は最小数、或いは
−ユーザ選択
のうちの少なくとも１つの基準を備えることができる。
【００４８】
前記非アクティブ化規則は、
−前記非アクティブ化基準の組を満たす全てのアクティブ状態の物体を非アクティブ化する強制非アクティブ化規則、
−非アクティブ状態の物体がアクティブ化される場合にのみ、前記非アクティブ化基準の組を満たす物体を非アクティブ化するランク付き非アクティブ化規則、
−前記非アクティブ化基準の組を最も良く満たす物体を非アクティブ化する単純非アクティブ化規則、
−関連し合う別の非アクティブ状態の物体がアクティブ化された場合に物体を非アクティブ化する単純交換非アクティブ化規則、又は
−別の非アクティブ状態であるが予備アクティブ化されている物体に接触する場合に物体を非アクティブ化する接触交換非アクティブ化規則
の中から選択することができる。
【００４９】
また本発明は、本発明の実施例の任意のものによる方法を実施するためのコンピュータ実行可能命令を有するコンピュータ可読データ記憶媒体に関し、さらにまた、３次元ビデオ・シーケンス用の入力を備え、本発明の実施例の任意のものによるコンピュータ実装方法を実施するようにプログラムされたコンピュータ・システムであって、３次元ビデオ・シーケンスが、連続するフレーム・シーケンスを有し、各フレームが画素アレイを有し、各画素に深さ値が関連付けられるコンピュータ・システムに関する。
【００５０】
「コンピュータ可読データ記憶媒体」という用語は、限定はしないが、ランダム・アクセス・メモリ、フラッシュ・メモリ、又は読み出し専用メモリなどのソリッドステート・メモリ、さらには、ハードディスク・ドライブ又は磁気テープなどの磁気データ記憶媒体、及び光ディスクなどの光データ記憶媒体を含めた、デジタル・データを含む任意のコンピュータ可読サポートを意味する。
【００５１】
本発明のこれら及び他の目的は、以下の詳細な説明を読み、添付図面を参照すれば、より容易に明らかになろう。
【図面の簡単な説明】
【００５２】
【図１】３Ｄ撮像デバイスの前に立つ人間ユーザのいる部屋を示す図である。
【図２】３Ｄ撮像システムによって捕捉されたときの、３次元空間内に分散された画素の形態での、同じ部屋の３次元画像データを示す図である。
【図３】前記画像データ内部のクリップされたボリュームであって、背景除去後の人間ユーザに対応する画素をグループ分けする相互接続された領域のクラスタを含むボリュームの２次元投影を示す図である。
【図４Ａ】３Ｄビデオ・シーケンスの連続フレームで、相互接続された領域のクラスタが更新される状況を示す図である。
【図４Ｂ】３Ｄビデオ・シーケンスの連続フレームで、相互接続された領域のクラスタが更新される状況を示す図である。
【図４Ｃ】３Ｄビデオ・シーケンスの連続フレームで、相互接続された領域のクラスタが更新される状況を示す図である。
【図５】１人の人間ユーザと、そのユーザを部分的に遮る別の人間ユーザとを表す相互接続された領域のクラスタを示す図である。
【図６Ａ】位置基準と単純アクティブ及び非アクティブ化規則を使用して、物体をアクティブ化及び非アクティブ化することができる状況を示す図である。
【図６Ｂ】位置基準と単純アクティブ及び非アクティブ化規則を使用して、物体をアクティブ化及び非アクティブ化することができる状況を示す図である。
【図６Ｃ】位置基準と単純アクティブ及び非アクティブ化規則を使用して、物体をアクティブ化及び非アクティブ化することができる状況を示す図である。
【図７Ａ】位置基準と接触交換規則を使用して、第１の物体をアクティブ化することができ、第２の物体を非アクティブ化することができる状況を示す図である。
【図７Ｂ】位置基準と接触交換規則を使用して、第１の物体をアクティブ化することができ、第２の物体を非アクティブ化することができる状況を示す図である。
【図８Ａ】位置基準と単純アクティブ化及び非アクティブ化規則を使用して、第１の物体がアクティブ化及び非アクティブ化される状況、及び位置基準とランク付きアクティブ化規則を使用して第２の物体がアクティブ化される状況を示す図である。
【図８Ｂ】位置基準と単純アクティブ化及び非アクティブ化規則を使用して、第１の物体がアクティブ化及び非アクティブ化される状況、及び位置基準とランク付きアクティブ化規則を使用して第２の物体がアクティブ化される状況を示す図である。
【図８Ｃ】位置基準と単純アクティブ化及び非アクティブ化規則を使用して、第１の物体がアクティブ化及び非アクティブ化される状況、及び位置基準とランク付きアクティブ化規則を使用して第２の物体がアクティブ化される状況を示す図である。
【発明を実施するための形態】
【００５３】
本発明は様々な修正形態及び代替形態が可能であるが、本発明の具体的な実施例を図面に例として示してあり、本明細書で詳細に述べる。しかし、開示する特定の形態に本発明を限定する意図はなく、逆に、本発明は、添付の特許請求の範囲で表される本発明の範囲に入る全ての修正形態、均等形態、及び代替形態を網羅するものであることを理解すべきである。
【００５４】
本発明の一実施例によるコンピュータ実装物体追跡方法及びコンピュータ・システムの一実施例の可能な使用例の１つを図１に示す。本出願では、対象物、この場合には人間ユーザ１のジェスチャを認識するためのこのシステム及び方法を、人間ユーザ１に表示される仮想環境を生成するコンピュータ・システム２と対話するために使用する。
【００５５】
ボリューム認識システムは、３Ｄ撮像システム、この特定の実施例では飛行時間（ＴＯＦ）３Ｄカメラ３を有する。このＴＯＦ３Ｄカメラ３はコンピュータ・システム２に接続され、人間ユーザ１は、そのコンピュータ・システム２と対話することができる。この実施例では、このコンピュータ・システム２は、それ自体、ＴＯＦ３Ｄカメラ３と協働して本発明のボリューム認識法を実施するようにプログラムされる。或いは、人間ユーザが前記コンピュータ・システム２と対話できるようにするために、前記方法を実施するようにプログラムされた別個のデータ処理デバイスをＴＯＦ３Ｄカメラとコンピュータ・システム２の間に接続することができる。
【００５６】
ＴＯＦ３Ｄカメラ３は、人間ユーザ１がいる部屋４の３Ｄ画像データを含む連続フレームを捕捉する。３Ｄ画像データは、２Ｄ画素アレイと、各画素に関する深さ値とを含み、深さ値は、その画素によって表された点からＴＯＦ３Ｄカメラ３までの距離に対応する。２Ｄ画素アレイ内の画素の垂直位置と水平位置は、それら自体、それらが表現する点のＴＯＦ３Ｄカメラ３に対する天頂角と方位角に対応するので、図２におけるように、各フレームは、ＴＯＦ３Ｄカメラ３の視程内の物体の可視点に対応する画素５の３次元クラウドによって示すことができる。
【００５７】
これらの連続フレームは、３次元ビデオ・シーケンスを生成し、これがコンピュータ・システム２に伝送される。第１のステップで、前記コンピュータ・システム３の内部にあるデータ処理装置は、ビデオ・シーケンス内の各フレームの画素５の３次元クラウドのカメラに対する画素位置を、シーンに固定された座標系６での座標に変換する。この座標系６は、３つの直交軸、すなわち横軸Ｘ、深さ軸Ｙ、及び高さ軸Ｚを有する。その後、不十分な画素情報しか入手できない画素、又はセンサ雑音によるものである可能性がある画素を、フィルタを使用してフレームから除去することができる。
【００５８】
また、後続のステップにおいて、フレームを、背景のみを含む事前に捕捉された基準フレームと比較することによって、シーン背景に対応する各フレーム内の画素５を除去することもできる。前記深さ軸Ｙで、基準フレーム内の対応する画素からしきい値距離Δｄ２を超えていない全ての画素５を、画像から差し引く。しかし或いは、代わりにリアルタイムで基準背景を更新することによって、この背景除去を動的に行うこともできる。
【００５９】
その後、データ処理要件を低減するために、得られた画像をクリップして、残っている画素５を含むより小さなボリューム７にすることができる。
【００６０】
次いで、データ処理装置によって、コンピュータ・メモリにおいて、それらの残っている画素５を複数の領域Ｒｉ（ここでｉ＝１，…，Ｋ）にグループ分けする。有利には、以下のようにベクトル量子化アルゴリズムを使用して画素をグループ分けする。
【００６１】
ビデオ・シーケンスの第１のフレームにおいて、ｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムを使用して画素をＫ個の領域にグループ分けする。このアルゴリズムでは、画素が領域重心から前記距離Ｑよりも離れている場合には、新たな領域が生成され、数値Ｋが１だけ増分される。画素が領域重心から前記距離Ｑ以内にある場合には、その画素は対応する領域に割り当てられ、それに従って重心の位置が更新される。したがって、前記第１のフレームでの第１の画素から始めると、領域がまだ１つも生成されていないので（Ｋ＝０）、第１の領域が生成され、Ｋが１に設定され、この第１の領域の重心の位置は第１の画素の位置となる。次の画素に関して、その画素が第１の画素から前記距離Ｑ以内にある場合には、その画素は第１の領域に組み込まれ、第１の領域の重心の位置が変わる。しかし、その画素が前記距離Ｑよりも離れている場合には、新たな領域が生成され、Ｋが２に設定される。
【００６２】
各後続のフレームにおいて、まず制約付きＫ−ｍｅａｎｓアルゴリズムを使用して、画素の少なくともいくつかをグループ分けする。Ｋ−ｍｅａｎｓアルゴリズムは反復アルゴリズムであり、時間的コヒーレンスの度合いを導入するために、Ｋ個の領域の重心の初期位置Ｃｉ（この場合には、前のフレームに関して決定されている位置）を定義した後、まず、１組のＮ個の画素の各画素ｊが、以下の式によって表される前記Ｋ個の領域のうちの１つの領域Ｒｓに関連付けられる。
【００６３】
【数１】
ここで、Ｐｊは、上述した座標系６での画素ｊの位置である。この特定の制約付きＫ−ｍｅａｎｓアルゴリズムでは、重心から前記所定の距離Ｑよりも離れている画素は、割り当てられていないままである。
【００６４】
各画素ｊ＝１，…，Ｎを前記Ｋ個の領域の１つに割り振った後、各領域に割り振られた画素の質量中心の位置を計算することによって、それらのＫ個の領域の重心の位置Ｃｉが更新される。
【００６５】
【数２】
ここで、ｎは、領域Ｒｉに割り振られた画素の数である。
【００６６】
次いで、Ｋ個の領域への画素の安定した割振りに落ち着くまで、これら２つのステップを繰り返し行うことができる。
【００６７】
次いで、割り当てられていないままの画素を、上述したのと同じｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムを使用して新たな領域にグループ分けすることができる。このアルゴリズムでは、画素が領域重心から前記距離Ｑよりも離れている場合に、新たな領域が生成され、数値Ｋが１だけ増分される。画素が領域重心から前記距離Ｑ以内にある場合には、その画素は対応する領域に割り当てられ、それに従って重心の位置が更新される。
【００６８】
最後に、Ｋ個の領域のうちの１つの領域が、このフレームにおいてその領域に割り当てられる画素がなく空のままである場合、この領域Ｒｉは削除され、数値Ｋが１だけ減分される。
【００６９】
フレームにおいて得られた１組の領域Ｒｉが図３に示される。
【００７０】
各フレームに関する次のステップは、領域隣接グラフ（ＲＡＧ）を生成し、コンピュータ・メモリにおいて、領域Ｒｉを相互接続された領域のクラスタＢにグループ分けすることを含む。データ処理装置は、
−領域Ｒａ内の少なくとも１つの画素と領域Ｒｂ内の別の画素とが、Ｘ−Ｚ平面上への２次元投影で隣接する場合、及び
−これら２つの領域Ｒａ、Ｒｂの隣接する画素の各対におけるＹ軸での深さの平均差が、所定の距離Δｄ１未満である場合に、
２つの領域Ｒａ、Ｒｂ（ここでａとｂは、０〜Ｋの間の２つの異なる数）が３次元空間内で接続されていると判断する。
【００７１】
２つの画素は、これら２つの画素の一方が、少なくともＸ軸又はＺ軸で他方の画素の次、次の次、又はそのまた次の画素である場合に、２次元投影で隣接しているとみなされる。
【００７２】
２つの領域Ｒａ、Ｒｂが、Ｘ−Ｚ平面上への投影で隣接する画素を有するが、隣接する画素のこれらの各対における深さの平均差が前記所定の距離Δｄ１を超えている場合、領域ＲａとＲｂは、ほぼ間違いなく接続されているものとしてフラグを立てることができる。この場合、それらの領域を相互接続された領域として単一のクラスタＢ０にグループ分けするかどうかは、１組の追加の基準に応じて決まることがある。
【００７３】
いくつかのクラスタＢ０が第１のフレームにおいて生成され、各クラスタが、１組の相互接続された領域を組み込む。後続のフレームに関して、新たな領域Ｒｃが直接又は少なくとも別の領域Ｒｄを介して既存のクラスタＢ０の領域に接続されている場合には、その領域Ｒｃは既存のクラスタＢ０に組み込まれる。これは、以下のアルゴリズムを実行するデータ処理装置によって決定される。
【００７４】
各領域Ｒｉに関して、
−領域Ｒｉが前のフレームで存在していた場合、したがって既存のクラスタＢ０に関連付けられる場合には、時間コヒーレンスを考慮して、Ｒｉが属するクラスタに対するＲｉの距離のインジケータ「ｄｉｓｔａｎｃｅ（Ｒｉ）」はゼロに設定され、インジケータ「ｏｂｊｅｃｔ（Ｒｉ）」は「Ｂ０」に設定され、「ｄｉｓｔａｎｃｅ（Ｒｉ）」の値に関して昇順でソートされたリストＨ内にＲｉが記憶される。
−そうでない場合には、「ｄｉｓｔａｎｃｅ（Ｒｉ）」が「ＩＮＦＩＮＩＴＥ（無限）」に設定され、「ｏｂｊｅｃｔ（Ｒｉ）」が「ＮＵＬＬ（ゼロ）」に設定される。
【００７５】
次いで、リストＨが空でない限り、以下のことが繰り返される。
−リストＨから、最小のインジケータ「ｄｉｓｔａｎｃｅ（Ｒｈ）」の値を有する領域Ｒｈを抽出する。
−領域Ｒｈに隣接する各領域Ｒｖに関して、
・ｄ＝ｄｉｓｔａｎｃｅ（Ｒｈ）＋ｄｉｓｔａｎｃｅＲＡＧ（Ｒｈ，Ｒｖ）を計算する。ここで、ＲｈとＲｖが接続されている場合、ｄｉｓｔａｎｃｅＲＡＧ（Ｒｈ，Ｒｖ）＝０であり、ＲｈとＲｖが接続されていない場合、ｄｉｓｔａｎｃｅＲＡＧ（Ｒｈ，Ｒｖ）＝ＩＮＦＩＮＩＴＥであり、並びに
・ｄ＜ｄｉｓｔａｎｃｅ（Ｒｖ）である場合、
・「ｄｉｓｔａｎｃｅ（Ｒｖ）」の値を値ｄに設定し、
・「ｏｂｊｅｃｔ（Ｒｖ）」の値を「ｏｂｊｅｃｔ（Ｒｈ）」の値に設定し、及び
・領域ＲｖがリストＨ内にない場合には、それをリストＨに挿入し、
・領域Ｒｖが既にリストＨ内にある場合には、それをＨから抽出する。
【００７６】
それにより、既存のクラスタに接続させることができる全ての領域を既存のクラスタに組み込んだ後、残っている領域があればそれを接続に関してチェックして、必要であれば、そのような領域を組み込む追加のクラスタを生成する。図４Ａ、図４Ｂ、及び図４Ｃは、２つの連続フレーム間のこの遷移を示す。
【００７７】
図４Ａに示される第１のフレームには、２つのクラスタＢ１とＢ２が存在する。Ｂ１は、相互接続された領域Ｒ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５、及びＲ６を有し、Ｂ２は、相互接続された領域Ｒ７、Ｒ８、Ｒ９、Ｒ１０、及びＲ１１を有する。図４Ｂに示される次のフレームでは、Ｂ２は依然として存在するが、Ｒ７が消えている。他方、新たな領域Ｒ１２、Ｒ１３、Ｒ１４、Ｒ１５、Ｒ１６、及びＲ１７が現れている。Ｒ１２は、クラスタＢ１の領域Ｒ６に接続され、Ｒ１３は、クラスタＢ２の領域Ｒ１１に接続され、Ｒ１４は、Ｒ１３に接続されている。Ｒ１５と、Ｒ１６と、Ｒ１７は、相互接続されるが、いかなる他の領域又はクラスタにも接続していない。したがって、図４Ｃで見ることができるように、Ｒ１２は、クラスタＢ１に組み込まれ、Ｒ１３及びＲ１４は、クラスタＢ２に組み込まれる。Ｒ１５、Ｒ１６、及びＲ１７は、新たなクラスタＢ３を形成する。
【００７８】
次のステップでは、クラスタ関係グラフ（ＣＲＧ）が確立される。このＣＲＧにおいて、Ｘ−Ｚ平面上への２次元投影で隣接するクラスタの対（すなわち、各クラスタが、Ｘ−Ｚ平面上への２次元投影で、他方のクラスタの領域内の少なくとも１つの画素に隣接する少なくとも１つの画素を有する領域を備える）が、「２Ｄ接続」とタグ付けされた第１のタイプのリンクでリンクされる。次いで、両方のクラスタが共通の隣接するクラスタへの「２Ｄ接続」リンクを有するが、共通の隣接するクラスタよりも高い深さ値を有し、深さ軸で互いから所定の距離Δｄ１以内にあるようなクラスタの対が、「３Ｄ接続可能」とタグ付けされた第２のタイプのリンクでリンクされる。
【００７９】
「３Ｄ接続可能」リンクによってリンクされたクラスタは、それらの共通の隣接するクラスタによって表される別の物体によって部分的に遮蔽された物体に属する可能性がある。それらのクラスタを実際に単一の物体に属するものとして互いに相互接続すべきかどうか判断するために、次いで、それらのクラスタが、前記２次元投影内で「スタック可能」であるかどうか、すなわち前記２次元投影の少なくとも１つの軸で少なくとも最小の正規化長さｏｍｉｎだけ互いに重畳しているかどうか検査される。正規化された重畳長さの値ｏ＝Ｏ／Ｌであり、ここで、Ｏは、その軸での絶対重畳長さであり、Ｌは、その軸での２つの「３Ｄ接続可能」クラスタの短い方の長さである。
【００８０】
図５は、フレームが１組のクラスタＢ１、Ｂ２、Ｂ３、Ｂ４、及びＢ５を示し、これらのクラスタが２つの物体、すなわち第１の人間ユーザＵ１と、第１の人間ユーザＵ１によって部分的に遮蔽されている第２の人間ユーザＵ２とを表す一例である。第２の人間ユーザＵ２の前に第１の人間ユーザＵ１がいることで、第２の人間ユーザＵ２がクラスタＢ２、Ｂ３、Ｂ４、及びＢ５に実質的に分割されることを容易に理解されよう。クラスタＢ２、Ｂ３、Ｂ４、及びＢ５は全て、Ｘ−Ｚ平面への２次元投影でクラスタＢ１に隣接しており、Ｙ軸でのそれらの平均の深さは、最小距離よりも大きくＢ１の深さを上回っているので、それらは、「２Ｄ接続」リンク７によってＢ１とリンクさせることができる。それらはまた、深さ軸Ｙで互いに所定の範囲内にあるので、「３Ｄ接続可能」リンク８で互いにリンクさせることができる。
【００８１】
したがって、次のステップでは、「３Ｄ接続可能」タイプのリンク８によってリンクされたそれらのクラスタＢ２、Ｂ３、Ｂ４、及びＢ５が、さらに、前記２次元投影の少なくとも１つの軸で、少なくとも最小の正規化長さｏｍｉｎだけ互いに重畳しているかどうかチェックされる。図示される実例では、Ｂ３は、Ｂ２と、Ｘ軸において十分な正規化長さｏＸ（３，２）＞ｏｍｉｎだけ重畳しており、また、Ｂ４及びＢ５は、それぞれＢ２及びＢ３と、Ｚ軸において十分な正規化長さｏＺ（４，２）＞ｏｍｉｎ及びｏＺ（５，３）＞ｏｍｉｎだけ重畳している。
【００８２】
正規化された重畳長さｏＸ（３，２）＝ＯＸ（３，２）／ＬＸ３であり、ここで、ＯＸ（３，２）は、Ｘ軸でのＢ３とＢ２の重畳であり、ＬＸ３は、Ｘ軸でのＢ３の長さである。正規化された重畳長さｏＺ（４，２）＝ＯＺ（４，２）／ＬＺ４であり、ここで、ＯＺ（４，２）は、Ｚ軸でのＢ４とＢ２の重畳であり、ＬＺ４は、Ｚ軸でのＢ４の長さである。最後に、正規化された重畳長さｏＺ（５，３）＝ＯＺ（５，３）／ＬＺ５であり、ここで、ＯＺ（５，３）は、Ｚ軸でのＢ５とＢ３の重畳であり、ＬＺ５は、Ｚ軸でのＢ５の長さである。
【００８３】
したがって、クラスタＢ２、Ｂ３、Ｂ４、及びＢ５は、コンピュータ・メモリにおいて、クラスタＢ１を備える別の物体Ｕ１によって部分的に遮蔽されている単一の物体Ｕ２に割り当てることができる。
【００８４】
この図示した実施例では、これらの「３Ｄ接続可能」試験と「スタック可能」試験が組み合わせて使用され、クラスタが両方の条件を満たさない場合には、クラスタが単一の物体に属することが除外されるが、代替実施例では、それらの試験は、互いに別個に、又は互いに並列して使用することもできる。これら２つの条件のそれぞれを包含的条件として適用することができ、したがって、条件が満たされる場合に、２つのクラスタが単一の物体に属するものとみなされる。しかしこれは、条件が満たされない場合も依然として排除されてはいない。各条件は、さらに、包含及び排他のための様々なしきい値を使用して、包含的及び排他的に個別に適用することができる。
【００８５】
後続のフレームに関して、データ処理装置は、新たなＣＲＧを生成し、まず上述した試験を使用して、新たなクラスタを既存の物体に割り当てることができるかどうかチェックする。次いで、同じ試験を使用して、残っている新たなクラスタがあればそれを新たな物体にグループ分けすることができるかどうかチェックする。
【００８６】
したがって、複数の物体を、それらの物体の１つが別の物体に遮蔽されているときでさえ、フレーム・シーケンス全体にわたって追跡することができる。そのような物体は、静止していても、移動可能でもよい。この物体追跡方法が、ビデオ・ゲーム、シミュレーション、又は仮想現実アプリケーションなどのコンピュータ・アプリケーションと対話するために使用されるとき、追跡される物体はそれぞれ、様々なアクティブ化／非アクティブ化基準とアクティブ化／非アクティブ化規則の組に従ってアクティブ化及び／又は非アクティブ化することができる。
【００８７】
本発明の特定の一実施例では、フレーム・シーケンス内の少なくとも１つの物体を追跡する方法であって、各フレームが画素アレイを有し、深さ値が各画素に関連付けられている方法が、さらに、少なくとも１つのフレームに関して、物体が第１の組のアクティブ化基準を満たす場合には、前記フレーム内で物体を予備アクティブ化するステップと、所定のアクティブ化規則の下で物体が第２の組のアクティブ化基準を満たす場合には、予備アクティブ状態の物体をアクティブ化するステップとを含む。
【００８８】
好ましくは、この方法はまた、前記シーケンスの少なくとも１つの後続のフレームに関して、所定の非アクティブ化規則の下で物体が１組の非アクティブ化基準を満たす場合に、事前にアクティブ化されている物体を非アクティブ化するステップを含むこともできる。
【００８９】
第１の組のアクティブ化基準は、以下の基準の少なくとも１つを含むことができる。
【００９０】
物体の位置：すなわち、この要件により、追跡される物体は、別の追跡される物体など移動基準及び／又は静止基準に対してある相対位置範囲内にある（さらには接触している）場合に予備アクティブ化される。
【００９１】
物体のサイズ：すなわち、この要件により、追跡される物体は、１次元、２次元、又は３次元での少なくとも所定の最小サイズ及び／又は多くとも所定の最大サイズを有する場合に予備アクティブ化される。
【００９２】
物体の動き：すなわち、この要件により、追跡される物体は、シーケンス内の少なくとも１つの前のフレームに対する少なくとも所定の最小の動き及び／又は多くとも所定の最大の動きを示す場合に予備アクティブ化される。
【００９３】
物体の形状：すなわち、この要件により、追跡される物体は、例えば人体を表すパターンなど所定のパターンにその物体の形状を合致させることができる場合に予備アクティブ化される。
【００９４】
物体の色：すなわち、この要件により、追跡される物体は、所定の色範囲内の色値を有する１つ又は複数の画素を含む場合に予備アクティブ化される。
【００９５】
物体の持続性：すなわち、この要件により、追跡される物体は、連続する前のフレームの少なくとも最小数及び／又は多くとも最大数にわたってアクティブ状態又は非アクティブ状態として追跡されている場合に予備アクティブ化される。
【００９６】
ユーザ選択：すなわち、この要件により、追跡される物体は、例えば「物体を見えるようにする」といったコマンドなど明示的なユーザ選択によって事前にフラグを立てられている場合に予備アクティブ化される。
【００９７】
アクティブ状態の物体の最大数：すなわち、この要件により、追跡される物体は、アクティブ状態の物体の数が所定の最大数を超えない場合にアクティブ化される。
【００９８】
この第２の組のアクティブ化基準は、アクティブ化規則に関連付けて使用される。このアクティブ化規則は、例えば、第２の組のアクティブ化基準を満たす全ての予備アクティブ状態の物体をアクティブ化する強制アクティブ化規則、アクティブ状態の物体が非アクティブ化される場合にのみ、前記第２の組のアクティブ化基準を満たす物体をアクティブ化するランク付きアクティブ化規則、前記第２の組のアクティブ化基準を最も良く満たす１つ又は複数の物体をアクティブ化する単純アクティブ化規則、関連し合う別のアクティブ状態の物体が非アクティブ化された場合に物体をアクティブ化する単純交換アクティブ化規則、別の物体によって遮蔽される又は遮蔽されている場合に物体をアクティブ化する遮蔽アクティブ化規則、又は別のアクティブ状態の物体に接触する場合に物体をアクティブ化する接触交換アクティブ化規則でよい。
【００９９】
非アクティブ化基準の組は、第２の組のアクティブ化基準のものと同様の基準を含むことがある。また、物体ランキング基準も備えることがあり、これは、物体のランキングが最小値未満である場合に、アクティブ状態の物体を非アクティブ化できるようにする。物体ランキングは、例えば、アクティブ状態の物体の組がアクティブ化された順序によって決定することができる。
【０１００】
非アクティブ化規則は、例えば、前記非アクティブ化基準の組を満たす全てのアクティブ状態の物体を非アクティブ化する強制非アクティブ化規則、非アクティブ状態の物体がアクティブ化される場合にのみ、前記非アクティブ化基準の組を満たす物体を非アクティブ化するランク付き非アクティブ化規則、前記非アクティブ化基準の組を最も良く満たす物体を非アクティブ化する単純非アクティブ化規則、関連し合う別の非アクティブ状態の物体がアクティブ化された場合に物体を非アクティブ化する単純交換非アクティブ化規則、又は別の非アクティブ状態であるが予備アクティブ化されている物体に接触する場合に物体を非アクティブ化する接触交換非アクティブ化規則でよい。
【０１０１】
したがって、アクティブ化基準及び規則、並びに非アクティブ化基準及び規則の組合せに応じて、様々なシナリオが利用可能である。
【０１０２】
例えば、図６Ａにおいて、物体Ｕ１が示されており、この物体Ｕ１は、予備アクティブ状態で、静止基準１１を中心とする円１０に入っており、アクティブ化のための位置基準を満たす。その結果、物体Ｕ１は、単純アクティブ化規則に従ってアクティブ化される。図６Ｂでは、物体Ｕ１は、円１０から出ているが、非アクティブ化のための位置基準はより大きな円１２よりも外にあるので、アクティブ状態のままである。図６Ｃに示されるように、物体Ｕ１がより大きな円１２から出たときにのみ、別の単純非アクティブ化規則の下で非アクティブ化することができる。
【０１０３】
図７Ａにおいて、２つの物体Ｕ１とＵ２は、接触していないものとして示されている。この場合には、２つの物体Ｕ１及びＵ２は、それぞれのユーザＵｓｅｒ１及びＵｓｅｒ２に対応する。第１の物体Ｕ１はアクティブ状態であり、第２の物体Ｕ２は予備アクティブ状態である。第１の物体Ｕ１は、非アクティブ状態であるが予備アクティブ化されている物体と接触するという非アクティブ化のための位置基準を満たすので、接触交換非アクティブ化規則の下で非アクティブ化することができる。他方、第２の物体Ｕ２は、アクティブ状態の物体と接触するというアクティブ化のための位置基準を満たすので、接触交換アクティブ化規則の下でアクティブ化される。その結果生じた状態交換が、図７Ｂに示される。
【０１０４】
図７Ｂでは、接触交換アクティブ化規則の下で、物体Ｕ２が物体Ｕ１と接触するとき、物体Ｕ２は、（非アクティブ状態であるが予備アクティブ化されていたので）アクティブ状態になり、物体Ｕ１は、ここでアクティブ化された物体Ｕ２と接触するので、非アクティブ化される。
【０１０５】
図８Ａにおいて、第１の物体Ｕ１が示されており、この物体Ｕ１は、予備アクティブ状態で、静止基準１１を中心とする円１０に入っており、アクティブ化のための位置基準を満たしている。その結果、この第１の物体Ｕ１は、単純アクティブ化規則に従ってアクティブ化される。円１０の内部にない第２の物体Ｕ２は、非アクティブ状態のままである。図８Ｂでは、第１の物体Ｕ１は、ここでは円１０の外である。しかし、非アクティブ化のための位置基準はより大きな円１２よりも外にあるので、第１の物体Ｕ１は非アクティブ状態のままである。第２の物体Ｕ２は、ここでは予備アクティブ状態であり円１０内にあるが、ランク付きアクティブ化規則の下では、第１の物体Ｕ１がアクティブ状態のままであるときには第２の物体Ｕ２をアクティブ化することはできない。図８Ｃに示されるように、第１の物体Ｕ１が、より大きな円１２から出た後に非アクティブ化されるときにのみ、このランク付きアクティブ化規則の下で第２の物体Ｕ２をアクティブ化することができる。
【０１０６】
アクティブ／非アクティブ化規則が許す場合には、複数の物体をアクティブ化することができることを理解されよう。これは、本発明による３次元撮像システムの視野内の同じ３次元空間内で２人以上のユーザが対話できるようにする。
【０１０７】
具体的な例示的実施例を参照しながら本発明を説明してきたが、特許請求の範囲に記載する本発明のより広範な範囲から逸脱することなく、これらの実施例に様々な修正及び変更を加えることができることは明らかであろう。例えば、物体を予備アクティブ化、アクティブ化、及び／又は非アクティブ化するステップは、部分的に遮蔽された単一の物体に複数のクラスタが属すると判断される方法又はその判断の結果とは無関係に行うことができる。したがって、本明細書及び図面は、限定的な意味合いではなく例示的な意味合いとみなすべきである。
【技術分野】
【０００１】
本発明は、フレーム・シーケンス内の少なくとも１つの物体を追跡する方法であって、各フレームが画素アレイ（ピクセル配列）を有し、深さ値が各画素に関連付けられている方法に関する。
【背景技術】
【０００２】
実世界物体を追跡するために、撮像デバイスに接続され、撮像デバイスによって生成されるビデオ・シーケンスで物体を追跡するようにプログラムされたデータ処理デバイスであって、ビデオ・シーケンスが連続するフレーム・シーケンスを有し、各シーケンスが画素アレイを有するデータ処理デバイスを使用することが、長きにわたり提案されている。
【０００３】
例えば、Ｗｅｉ Ｄｕ及びＪｕｓｔｕｓ Ｐｉａｔｅｒによる論文「Ｔｒａｃｋｉｎｇ ｂｙ Ｃｌｕｓｔｅｒ Ａｎａｌｙｓｉｓ ｏｆ Ｆｅａｔｕｒｅ Ｐｏｉｎｔｓ ｕｓｉｎｇ ａ Ｍｉｘｔｕｒｅ Ｐａｒｔｉｃｌｅ Ｆｉｌｔｅｒ」において、Ｈａｒｒｉｓコーナー検出器及びＬｕｃａｓ−Ｋａｎａｄｅトラッカを使用して、ビデオ・シーケンス内の物体を追跡するための方法が開示されている。しかしこの方法は、画素の深さ情報なしで２次元ビデオ・シーケンスに適用されるので、かなりのデータ処理要件にも関わらずその性能は限られる。
【０００４】
２次元画素アレイを有するビデオ・シーケンスで１つ又は複数の物体を追跡するための方法を開示するいくつかの他の関連の論文は以下のものである。
【０００５】
Ｓ． ＭｃＫｅｎｎａ、Ｓ． Ｊａｂｒｉ、Ｚ． Ｄｕｒｉｃ、及びＨ． Ｗｅｃｈｓｌｅｒ， “Ｔｒａｃｋｉｎｇ Ｇｒｏｕｐｓ ｏｆ Ｐｅｏｐｌｅ”， Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｉｍａｇｅ Ｕｎｄｅｒｓｔａｎｄｉｎｇ， ２０００
【０００６】
Ｆ． Ｂｒｅｍｏｎｄ及びＭ． Ｔｈｏｎｎａｔ， “Ｔｒａｃｋｉｎｇ ｍｕｌｔｉｐｌｅ ｎｏｎｒｉｇｉｄ ｏｂｊｅｃｔｓ ｉｎ ｖｉｄｅｏ ｓｅｑｕｅｎｃｅｓ”， ＩＥＥＥ Ｔｒａｎｓ． Ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ ｆｏｒ Ｖｉｄｅｏ Ｔｅｃｈｎｉｑｕｅｓ， １９９８
【０００７】
Ｉ Ｈａｒｉｔａｏｇｌｕ， “Ａ Ｒｅａｌ Ｔｉｍｅ Ｓｙｓｔｅｍ ｆｏｒ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｔｒａｃｋｉｎｇ ｏｆ Ｐｅｏｐｌｅ ａｎｄ Ｒｅｃｏｇｎｉｚｉｎｇ Ｔｈｅｉｒ Ａｃｔｉｖｉｔｉｅｓ”， Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｍａｒｙｌａｎｄ， １９９８
【０００８】
Ｇ． Ｐｉｎｇａｌｉ、Ｙ． Ｊｅａｎ、及びＡ． Ｏｐａｌａｃｈ， “Ｂａｌｌ Ｔｒａｃｋｉｎｇ ａｎｄ Ｖｉｒｔｕａｌ Ｒｅｐｌａｙｓ ｆｏｒ Ｉｎｎｏｖａｔｉｖｅ Ｔｅｎｎｉｓ Ｂｒｏａｄｃａｓｔｓ”， １５ｔｈ Ｉｎｔ． Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ
【０００９】
しかし、これらの追跡方法は、直接の画素深さ情報なしで２Ｄビデオ・シーケンスで実施されるので、色、形状、又はテクスチャなど他の物体属性に基づいてしか画像セグメント化を行うことができないため、それらの性能は必然的に限られる。
【００１０】
例えば国際公開第２００８／１２８５６８号で、各フレームの各画素に深さ値が関連付けられたビデオ・シーケンスを提供する３Ｄ撮像システムを使用することが既に提案されている。そのような追跡方法は、純粋に２次元の画像に基づくものよりも、追跡される物体に関する有用な位置情報をはるかに多く生成する。特に、３Ｄ撮像システムの使用は、前景と背景の区別を容易にする。しかし、開示された方法は、複数の物体を追跡するという問題には対処しておらず、特に、３Ｄ撮像システムの視野内で別の物体によって少なくとも部分的に遮蔽された物体を追跡するという問題には対処していない。国際公開第２００８／１２８５６８号では、３次元空間内のボリュームを認識するための方法であって、３次元画像データが３次元空間内に複数の点を有する方法が開示されている。これらの点はクラスタ化され、クラスタが、対象の点として選択される。選択されたクラスタ内部の点は、サブクラスタにさらにグループ分けされ、サブクラスタはそれぞれ、重心と、重心に関連付けられるボリュームとを有する。重心は、物体を示すネットワークを形成するために接続することができ、末端の重心は、ただ１つの他の重心に接続された重心として識別される。
【００１１】
３Ｄビデオ・シーケンスを使用しており、しかし遮蔽の問題に対処できていない他の追跡方法は、Ａ． Ａｚｅｒｂａｙｅｒｊａｎｉ及びＣ． Ｗｒｅｎによって“Ｒｅａｌ−Ｔｉｍｅ ３Ｄ Ｔｒａｃｋｉｎｇ ｏｆ ｔｈｅ Ｈｕｍａｎ Ｂｏｄｙ”， Ｐｒｏｃ． ｏｆ Ｉｍａｇｅ’ｃｏｍ， １９９６において開示されており、また、Ｔ． Ｏｌｓｏｎ及びＦ． Ｂｒｉｌｌによって“Ｍｏｖｉｎｇ Ｏｂｊｅｃｔ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｅｖｅｎｔ Ｒｅｃｏｇｎｉｔｉｏｎ Ａｌｇｏｒｉｔｈｍｓ Ｆｏｒ Ｓｍａｒｔ Ｃａｍｅｒａｓ”， Ｐｒｏｃ． Ｉｍａｇｅ Ｕｎｄｅｒｓｔａｎｄｉｎｇ Ｗｏｒｋｓｈｏｐ， １９９７においても開示されている。
【００１２】
いくつかの他の開示は、この遮蔽の問題に対処している。いくつかの様々な方法が、リエージュ大学（Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｌｉｅｇｅ）の電子工学及びコンピュータ・サイエンス科（ｔｈｅ Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｅｌｅｃｔｒｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ）のＰｉｅｒｒｅ Ｆ． Ｇａｂｒｉｅｌ、Ｊａｃｑｕｅｓ Ｇ． Ｖｅｒｌｙ、Ｊｕｓｔｕｓ Ｈ． Ｐｉａｔｅｒ、及びＡｎｄｒｅ Ｇｅｎｏｎによって、“Ｔｈｅ Ｓｔａｔｅ ｏｆ ｔｈｅ Ａｒｔ ｉｎ Ｍｕｌｔｉｐｌｅ Ｏｂｊｅｃｔ Ｔｒａｃｋｉｎｇ Ｕｎｄｅｒ Ｏｃｃｌｕｓｉｏｎ ｉｎ Ｖｉｄｅｏ Ｓｅｑｕｅｎｃｅｓ”という論文で提示されている。
【００１３】
この遮蔽の問題に対処する追跡方法は、Ａ． Ｅｌｇａｍｍａｌ及びＬ．Ｓ． Ｄａｖｉｓが“Ｐｒｏｂａｂｉｌｉｓｔｉｃ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｓｅｇｍｅｎｔｉｎｇ ｐｅｏｐｌｅ ｕｎｄｅｒ ｏｃｃｌｕｓｉｏｎ”， Ｐｒｏｃ． ｏｆ ＩＥＥＥ ８ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ， ２００１において開示しており、またＩ． Ｈａｒｉｔａｏｇｌｕ、Ｄ． Ｈａｒｗｏｏｄ、及びＬ． Ｄａｖｉｓが“Ｈｙｄｒａ： Ｍｕｌｔｉｐｌｅ Ｐｅｏｐｌｅ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｔｒａｃｋｉｎｇ”， Ｗｏｒｋｓｈｏｐ ｏｆ Ｖｉｄｅｏ Ｓｕｒｖｅｉｌｌａｎｃｅ， １９９９において開示しており、またＳ． Ｋｈａｎ及びＭ． Ｓｈａｈが“Ｔｒａｃｋｉｎｇ Ｐｅｏｐｌｅ ｉｎ Ｐｒｅｓｅｎｃｅ ｏｆ Ｏｃｃｌｕｓｉｏｎ”， Ａｓｉａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ”， ２０００において開示しており、またＨ．Ｋ． Ｒｏｈ及びＳ．Ｗ． Ｌｅｅが“Ｍｕｌｔｉｐｌｅ Ｐｅｏｐｌｅ Ｔｒａｃｋｉｎｇ Ｕｓｉｎｇ ａｎ Ａｐｐｅａｒａｎｃｅ Ｍｏｄｅｌ Ｂａｓｅｄ ｏｎ Ｔｅｍｐｏｒａｌ Ｃｏｌｏｒ”， Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， ２０００において開示しており、またＡ．Ｗ． Ｓｅｎｉｏｒ、Ａ． Ｈａｍｐａｐｕｒ、Ｌ．Ｍ． Ｂｒｏｗｎ、Ｙ． Ｔｉａｎ、Ｓ． Ｐａｎｋａｎｔｉ、及びＲ． Ｍ． Ｂｏｌｌｅが“Ａｐｐｅａｒａｎｃｅ Ｍｏｄｅｌｓ ｆｏｒ Ｏｃｃｌｕｓｉｏｎ Ｈａｎｄｌｉｎｇ”， ２ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｐｒｅｆｏｒｍａｎｃｅ Ｅｖａｌｕａｔｉｏｎ ｏｆ Ｔｒａｃｋｉｎｇ ａｎｄ Ｓｕｒｖｅｉｌｌａｎｃｅ Ｓｙｓｔｅｍｓ”， ２００１において開示している。しかし、これらの方法は全て、深さデータはなんら有さずに、２次元画素アレイのみを有する２Ｄ又はステレオビデオ・シーケンスに基づいているので、それらの性能は限られる。
【００１４】
トップダウン・シーン・ビューに基づく物体追跡方法を、Ａ． Ｆ． Ｂｏｂｉｃｋ他が“Ｔｈｅ ＫｉｄｓＲｏｏｍ： Ａ ｐｅｒｃｅｐｔｕａｌｌｙ ｂａｓｅｄ ｉｎｔｅｒａｃｔｉｖｅ ａｎｄ ｉｍｍｅｒｓｉｖｅ ｓｔｏｒｙ ｅｎｖｉｒｏｎｍｅｎｔ”， Ｔｅｌｅｏｐｅｒａｔｏｒｓ ａｎｄ Ｖｉｒｔｕａｌ Ｅｎｖｉｒｏｎｒｍｅｎｔ， １９９９において開示しており、またＲ．Ｔ． Ｃｏｌｌｉｎｓ、Ａ．Ｊ． Ｌｉｐｔｏｎ、及びＴ． Ｋａｎａｄｅが“Ａ Ｓｙｓｔｅｍ ｆｏｒ Ｖｉｄｅｏ Ｓｕｒｖｅｉｌｌａｎｃｅ ａｎｄ Ｍｏｎｉｔｏｒｉｎｇ”， Ｐｒｏｃ． ８ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｔｏｐｉｃａｌ Ｍｅｅｔｉｎｇ ｏｎ Ｒｏｂｏｔｉｃｓ ａｎｄ Ｒｅｍｏｔｅ Ｓｙｓｔｅｍｓ， １９９９において開示しており、またＷ．Ｅ．Ｌ． Ｇｒｉｍｓｏｎ、Ｃ． Ｓｔａｕｆｆｅｒ、Ｒ． Ｒｏｍａｎｏ、及びＬ． Ｌｅｅが“Ｕｓｉｎｇ ａｄａｐｔｉｖｅ ｔｒａｃｋｉｎｇ ｔｏ ｃｌａｓｓｉｆｙ ａｎｄ ｍｏｎｉｔｏｒ ａｃｔｉｖｉｔｉｅｓ ｉｎ ａ ｓｉｔｅ”， Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎにおいて開示しており、またＡ． Ｂｅｖｉｌａｃｑｕａ、Ｌ． Ｄｉ Ｓｔｅｆａｎｏ、及びＰ． Ｔａｚｚａｒｉが“Ｐｅｏｐｌｅ ｔｒａｃｋｉｎｇ ｕｓｉｎｇ ａ ｔｉｍｅ−ｏｆ−ｆｌｉｇｈｔ ｄｅｐｔｈ ｓｅｎｓｏｒ”， ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｖｉｄｅｏ ａｎｄ Ｓｉｇｎａｌ Ｂａｓｅｄ Ｓｕｒｖｅｉｌｌａｎｃｅ， ２００６において開示している。しかし、その結果、追跡される物体に関して入手できる情報は、特にその物体が人間ユーザであるときには制限される。
【００１５】
Ｄａｎ Ｗｉｔｚｎｅｒ Ｈａｎｓｅｎ、Ｍａｄｓ Ｓｙｓｋａ Ｈａｎｓｅｎ、Ｍａｒｔｉｎ Ｋｉｒｓｃｈｍｅｙｅｒ、Ｒａｓｍｕｓ Ｌａｒｓｅｎ、及びＤａｖｉｄｅ Ｓｉｌｖｅｓｔｒｅが“Ｃｌｕｓｔｅｒ ｔｒａｃｋｉｎｇ ｗｉｔｈ ｔｉｍｅ−ｏｆ−ｆｌｉｇｈｔ ｃａｍｅｒａｓ”， ２００８ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ Ｗｏｒｋｓｈｏｐｓにおいて、やはりホモグラフィ平面内で、すなわち「トップダウン」ビューで物体が追跡される物体追跡方法を開示している。この方法は、期待値最大化アルゴリズムを使用する。しかし、この方法もまた、追跡された物体が人間ユーザである場合には、ジェスチャの認識に十分には適合しない。
【００１６】
また、Ｌｅｉｌａ Ｓａｂｅｔｉ、Ｅｈｓａｎ Ｐａｒｖｉｚｉ、及びＱ．Ｍ． Ｊｏｎａｔｈａｎ Ｗｕが、“Ｖｉｓｕａｌ Ｔｒａｃｋｉｎｇ Ｕｓｉｎｇ Ｃｏｌｏｕｒ Ｃａｍｅｒａｓ ａｎｄ Ｔｉｍｅ−ｏｆ−Ｆｌｉｇｈｔ Ｒａｎｇｅ Ｉｍａｇｉｎｇ Ｓｅｎｓｏｒｓ”， Ｊｏｕｒｎａｌ ｏｆ Ｍｕｌｔｉｍｅｄｉａ， Ｖｏｌ． ３， Ｎｏ． ２， Ｊｕｎｅ ２００８において、画素深さデータを有する３Ｄビデオ・シーケンスを使用する物体追跡方法を提示している。しかし、モンテカルロベースの「パーティクル・フィルタ」追跡方法を使用するこの方法はまた、かなりのデータ処理リソースを必要とする。
【００１７】
米国特許出願公開第２００６／２３９５５８号は、シーンの画像を生成する３次元撮像システムを開示する。シーンの画像内の画素は、その画素がシーン内のどの物体に関係付けられているかに応じてラベル付けされて、値を割り当てられる。同じラベルを有する画素のグループは、「ブロブ」を生成するようにグループ分けされ、各ブロブが異なる物体に対応している。ブロブが定義されると、それらは、円や長方形など様々な形状の基本形、或いは人、動物、又は車など他の事前定義された物体にモデル化又は量子化される。シーン内の画素のクラスタ化及びそれらの関連付けられた深さ値を使用して、画素の深さ値に従って、その画素が特定のクラスタに属するかどうか判断する。したがって画素は、隣接する画素と同じ深さである場合には、隣接する画素が属するクラスタと同じラベルを割り当てられる。
【００１８】
米国特許第６７１８１８号は、シーン内の別個の３次元領域又は「ブロブ」を選択的にクラスタ化して、「ブロブ」クラスタを物体認識に関するモデルと比較することによって、シーン内で対象の人及び物体を識別及び位置特定するための方法を開示する。対象のシーンの初期３次元深さ画像が生成される。３次元ボリューム内での３次元画像画素の空間座標が画像によって表される。人又は物体の識別及び位置特定は、作業画像を処理することによって決定され、作業画像は、初期３次元深さ画像とライブ深さ画像を使用した背景差分プロセスから得られ、その際、初期３次元深さ画像とは大きく異なるライブ深さ画像内の任意の画素が作業画像の一部となり、作業画像は、いくつかの別個の３次元領域又は「ブロブ」を含む。「ブロブ」を処理して、各ブロブがどの人又は物体に属するかが識別される。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】国際公開第２００８／１２８５６８号
【特許文献２】米国特許出願公開第２００６／２３９５５８号
【特許文献３】米国特許第６７１８１８号
【非特許文献】
【００２０】
【非特許文献１】Ｗｅｉ Ｄｕ及びＪｕｓｔｕｓ Ｐｉａｔｅｒによる論文「Ｔｒａｃｋｉｎｇ ｂｙ Ｃｌｕｓｔｅｒ Ａｎａｌｙｓｉｓ ｏｆ Ｆｅａｔｕｒｅ Ｐｏｉｎｔｓ ｕｓｉｎｇ ａ Ｍｉｘｔｕｒｅ Ｐａｒｔｉｃｌｅ Ｆｉｌｔｅｒ」
【非特許文献２】Ｓ． ＭｃＫｅｎｎａ、Ｓ． Ｊａｂｒｉ、Ｚ． Ｄｕｒｉｃ、及びＨ． Ｗｅｃｈｓｌｅｒ， “Ｔｒａｃｋｉｎｇ Ｇｒｏｕｐｓ ｏｆ Ｐｅｏｐｌｅ”， Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｉｍａｇｅ Ｕｎｄｅｒｓｔａｎｄｉｎｇ， ２０００
【非特許文献３】Ｆ． Ｂｒｅｍｏｎｄ及びＭ． Ｔｈｏｎｎａｔ， “Ｔｒａｃｋｉｎｇ ｍｕｌｔｉｐｌｅ ｎｏｎｒｉｇｉｄ ｏｂｊｅｃｔｓ ｉｎ ｖｉｄｅｏ ｓｅｑｕｅｎｃｅｓ”， ＩＥＥＥ Ｔｒａｎｓ． Ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ ｆｏｒ Ｖｉｄｅｏ Ｔｅｃｈｎｉｑｕｅｓ， １９９８
【非特許文献４】Ｉ Ｈａｒｉｔａｏｇｌｕ， “Ａ Ｒｅａｌ Ｔｉｍｅ Ｓｙｓｔｅｍ ｆｏｒ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｔｒａｃｋｉｎｇ ｏｆ Ｐｅｏｐｌｅ ａｎｄ Ｒｅｃｏｇｎｉｚｉｎｇ Ｔｈｅｉｒ Ａｃｔｉｖｉｔｉｅｓ”， Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｍａｒｙｌａｎｄ， １９９８
【非特許文献５】Ｇ． Ｐｉｎｇａｌｉ、Ｙ． Ｊｅａｎ、及びＡ． Ｏｐａｌａｃｈ， “Ｂａｌｌ Ｔｒａｃｋｉｎｇ ａｎｄ Ｖｉｒｔｕａｌ Ｒｅｐｌａｙｓ ｆｏｒ Ｉｎｎｏｖａｔｉｖｅ Ｔｅｎｎｉｓ Ｂｒｏａｄｃａｓｔｓ”， １５ｔｈ Ｉｎｔ． Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ
【非特許文献６】Ａ． Ａｚｅｒｂａｙｅｒｊａｎｉ及びＣ． Ｗｒｅｎ“Ｒｅａｌ−Ｔｉｍｅ ３Ｄ Ｔｒａｃｋｉｎｇ ｏｆ ｔｈｅ Ｈｕｍａｎ Ｂｏｄｙ”， Ｐｒｏｃ． ｏｆ Ｉｍａｇｅ’ｃｏｍ， １９９６
【非特許文献７】Ｔ． Ｏｌｓｏｎ及びＦ． Ｂｒｉｌｌ“Ｍｏｖｉｎｇ Ｏｂｊｅｃｔ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｅｖｅｎｔ Ｒｅｃｏｇｎｉｔｉｏｎ Ａｌｇｏｒｉｔｈｍｓ Ｆｏｒ Ｓｍａｒｔ Ｃａｍｅｒａｓ”， Ｐｒｏｃ． Ｉｍａｇｅ Ｕｎｄｅｒｓｔａｎｄｉｎｇ Ｗｏｒｋｓｈｏｐ， １９９７
【非特許文献８】リエージュ大学（Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｌｉｅｇｅ）の電子工学及びコンピュータ・サイエンス科（ｔｈｅ Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｅｌｅｃｔｒｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ）のＰｉｅｒｒｅ Ｆ． Ｇａｂｒｉｅｌ、Ｊａｃｑｕｅｓ Ｇ． Ｖｅｒｌｙ、Ｊｕｓｔｕｓ Ｈ． Ｐｉａｔｅｒ、及びＡｎｄｒｅ Ｇｅｎｏｎによる論文“Ｔｈｅ Ｓｔａｔｅ ｏｆ ｔｈｅ Ａｒｔ ｉｎ Ｍｕｌｔｉｐｌｅ Ｏｂｊｅｃｔ Ｔｒａｃｋｉｎｇ Ｕｎｄｅｒ Ｏｃｃｌｕｓｉｏｎ ｉｎ Ｖｉｄｅｏ Ｓｅｑｕｅｎｃｅｓ”
【非特許文献９】Ａ． Ｅｌｇａｍｍａｌ及びＬ．Ｓ． Ｄａｖｉｓ“Ｐｒｏｂａｂｉｌｉｓｔｉｃ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｓｅｇｍｅｎｔｉｎｇ ｐｅｏｐｌｅ ｕｎｄｅｒ ｏｃｃｌｕｓｉｏｎ”， Ｐｒｏｃ． ｏｆ ＩＥＥＥ ８ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ， ２００１
【非特許文献１０】Ｉ． Ｈａｒｉｔａｏｇｌｕ、Ｄ． Ｈａｒｗｏｏｄ、及びＬ． Ｄａｖｉｓ“Ｈｙｄｒａ： Ｍｕｌｔｉｐｌｅ Ｐｅｏｐｌｅ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｔｒａｃｋｉｎｇ”， Ｗｏｒｋｓｈｏｐ ｏｆ Ｖｉｄｅｏ Ｓｕｒｖｅｉｌｌａｎｃｅ， １９９９
【非特許文献１１】Ｓ． Ｋｈａｎ及びＭ． Ｓｈａｈ“Ｔｒａｃｋｉｎｇ Ｐｅｏｐｌｅ ｉｎ Ｐｒｅｓｅｎｃｅ ｏｆ Ｏｃｃｌｕｓｉｏｎ”， Ａｓｉａｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ”， ２０００
【非特許文献１２】Ｈ．Ｋ． Ｒｏｈ及びＳ．Ｗ． Ｌｅｅ“Ｍｕｌｔｉｐｌｅ Ｐｅｏｐｌｅ Ｔｒａｃｋｉｎｇ Ｕｓｉｎｇ ａｎ Ａｐｐｅａｒａｎｃｅ Ｍｏｄｅｌ Ｂａｓｅｄ ｏｎ Ｔｅｍｐｏｒａｌ Ｃｏｌｏｒ”， Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， ２０００
【非特許文献１３】Ａ．Ｗ． Ｓｅｎｉｏｒ、Ａ． Ｈａｍｐａｐｕｒ、Ｌ．Ｍ． Ｂｒｏｗｎ、Ｙ． Ｔｉａｎ、Ｓ． Ｐａｎｋａｎｔｉ、及びＲ． Ｍ． Ｂｏｌｌｅ“Ａｐｐｅａｒａｎｃｅ Ｍｏｄｅｌｓ ｆｏｒ Ｏｃｃｌｕｓｉｏｎ Ｈａｎｄｌｉｎｇ”， ２ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｐｒｅｆｏｒｍａｎｃｅ Ｅｖａｌｕａｔｉｏｎ ｏｆ Ｔｒａｃｋｉｎｇ ａｎｄ Ｓｕｒｖｅｉｌｌａｎｃｅ Ｓｙｓｔｅｍｓ”， ２００１
【非特許文献１４】Ａ． Ｆ． Ｂｏｂｉｃｋ他“Ｔｈｅ ＫｉｄｓＲｏｏｍ： Ａ ｐｅｒｃｅｐｔｕａｌｌｙ ｂａｓｅｄ ｉｎｔｅｒａｃｔｉｖｅ ａｎｄ ｉｍｍｅｒｓｉｖｅ ｓｔｏｒｙ ｅｎｖｉｒｏｎｍｅｎｔ”， Ｔｅｌｅｏｐｅｒａｔｏｒｓ ａｎｄ Ｖｉｒｔｕａｌ Ｅｎｖｉｒｏｎｒｍｅｎｔ， １９９９
【非特許文献１５】Ｒ．Ｔ． Ｃｏｌｌｉｎｓ、Ａ．Ｊ． Ｌｉｐｔｏｎ、及びＴ． Ｋａｎａｄｅ“Ａ Ｓｙｓｔｅｍ ｆｏｒ Ｖｉｄｅｏ Ｓｕｒｖｅｉｌｌａｎｃｅ ａｎｄ Ｍｏｎｉｔｏｒｉｎｇ”， Ｐｒｏｃ． ８ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｔｏｐｉｃａｌ Ｍｅｅｔｉｎｇ ｏｎ Ｒｏｂｏｔｉｃｓ ａｎｄ Ｒｅｍｏｔｅ Ｓｙｓｔｅｍｓ， １９９９
【非特許文献１６】Ｗ．Ｅ．Ｌ． Ｇｒｉｍｓｏｎ、Ｃ． Ｓｔａｕｆｆｅｒ、Ｒ． Ｒｏｍａｎｏ、及びＬ． Ｌｅｅ“Ｕｓｉｎｇ ａｄａｐｔｉｖｅ ｔｒａｃｋｉｎｇ ｔｏ ｃｌａｓｓｉｆｙ ａｎｄ ｍｏｎｉｔｏｒ ａｃｔｉｖｉｔｉｅｓ ｉｎ ａ ｓｉｔｅ”， Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ
【非特許文献１７】Ａ． Ｂｅｖｉｌａｃｑｕａ、Ｌ． Ｄｉ Ｓｔｅｆａｎｏ、及びＰ． Ｔａｚｚａｒｉ“Ｐｅｏｐｌｅ ｔｒａｃｋｉｎｇ ｕｓｉｎｇ ａ ｔｉｍｅ−ｏｆ−ｆｌｉｇｈｔ ｄｅｐｔｈ ｓｅｎｓｏｒ”， ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｖｉｄｅｏ ａｎｄ Ｓｉｇｎａｌ Ｂａｓｅｄ Ｓｕｒｖｅｉｌｌａｎｃｅ， ２００６
【非特許文献１８】Ｄａｎ Ｗｉｔｚｎｅｒ Ｈａｎｓｅｎ、Ｍａｄｓ Ｓｙｓｋａ Ｈａｎｓｅｎ、Ｍａｒｔｉｎ Ｋｉｒｓｃｈｍｅｙｅｒ、Ｒａｓｍｕｓ Ｌａｒｓｅｎ、及びＤａｖｉｄｅ Ｓｉｌｖｅｓｔｒｅ“Ｃｌｕｓｔｅｒ ｔｒａｃｋｉｎｇ ｗｉｔｈ ｔｉｍｅ−ｏｆ−ｆｌｉｇｈｔ ｃａｍｅｒａｓ”， ２００８ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ Ｗｏｒｋｓｈｏｐｓ
【非特許文献１９】Ｌｅｉｌａ Ｓａｂｅｔｉ、Ｅｈｓａｎ Ｐａｒｖｉｚｉ、及びＱ．Ｍ． Ｊｏｎａｔｈａｎ Ｗｕ“Ｖｉｓｕａｌ Ｔｒａｃｋｉｎｇ Ｕｓｉｎｇ Ｃｏｌｏｕｒ Ｃａｍｅｒａｓ ａｎｄ Ｔｉｍｅ−ｏｆ−Ｆｌｉｇｈｔ Ｒａｎｇｅ Ｉｍａｇｉｎｇ Ｓｅｎｓｏｒｓ”， Ｊｏｕｒｎａｌ ｏｆ Ｍｕｌｔｉｍｅｄｉａ， Ｖｏｌ． ３， Ｎｏ． ２， Ｊｕｎｅ ２００８
【発明の概要】
【発明が解決しようとする課題】
【００２１】
本発明の目的は、画素深さ情報を用いてフレーム・シーケンス内の物体を追跡するための方法であって、部分的に遮蔽されている物体でさえ確実に追跡し、それと同時に、３次元空間内での追跡された物体の形状に関する情報を提供し、それをジェスチャ認識のために適用することができる方法を提供することである。
【課題を解決するための手段】
【００２２】
一実施例では、本発明によるコンピュータ実装方法は、
−画素深さ情報を備えるフレーム・シーケンスの各フレームの画素の少なくともいくつかを複数の領域にグループ分けするステップと、
−前記領域を、相互接続された領域のクラスタにグループ分けするステップと、
−２次元投影で別のクラスタに隣接する少なくとも１つのクラスタが前記別のクラスタの深さ値よりも高い深さ値を有する場合に、前記少なくとも１つのクラスタが前記別のクラスタによって部分的に遮蔽されている物体に属すると判断するステップと
を含む。
【００２３】
「深さ値」という用語は、前記ビデオ・シーケンスを捕捉する撮像デバイスの位置とは無関係に、前記２次元投影の平面に垂直な深さの値を意味するものとする。深さ値は、撮像デバイスからの画素の距離である。したがって、１つのクラスタ（又はそのクラスタ内の画素）の深さ値は、撮像デバイスからより遠くに離れていることにより、別のクラスタ（又は別のクラスタ内の画素）の深さ値よりも高い値を有することができる。
【００２４】
本発明のさらなる目的は、単一の部分的に遮蔽されている物体に属するクラスタをつなぎ合わせることである。
【００２５】
このために、前記２次元投影で前記別のクラスタへの隣接性を共に有し且つ前記別のクラスタよりも高い深さ値を有する２つのクラスタが、前記別のクラスタによって部分的に遮蔽されている単一の物体に属するかどうかを、前記より高い深さ値が互いに所定の範囲Δｄ１内にあるかどうかに応じて判断することができる。
【００２６】
また、前記２次元投影で前記別のクラスタへの隣接性を共に有し且つ前記別のクラスタよりも高い深さ値を有する２つのクラスタが、前記別のクラスタによって部分的に遮蔽されている単一の物体に属するかどうかを、前記２次元投影の少なくとも１つの軸において前記２つのクラスタのそれぞれが前記２つのクラスタの他方と少なくとも最小長さにわたって重畳しているかどうかに応じて判断することができる。
【００２７】
これら２つの条件は、個別に、又は同時に適用することができる。これら２つの条件のそれぞれを包含的条件として適用することができ、したがって条件が満たされる場合に、２つのクラスタが単一の物体に属するものとみなされる。しかしこれは、条件が満たされない場合も依然として除外されてはいない。しかし、それぞれの条件を排他的条件として適用することもでき、これは、クラスタがその条件を満たさない場合には、それらのクラスタが単一の物体に属することが除外されることを意味する。特定の実施例では、各条件はさらに、包含及び排他のための様々なしきい値を使用して、包含的及び排他的に個別に適用することができる。
【００２８】
したがってこの追跡方法により、別の物体によって部分的に遮蔽されているときでさえ、物体の追跡を続けることができる。遮っているクラスタからはみ出した領域であって、それらの相対位置により、確実に互いにリンクさせることができる領域は、部分的に遮蔽された物体に属するものとして識別される。さらにこれは、限られた計算リソース消費で実現され、それと同時に、相互接続された領域のクラスタによって、追跡される物体の３次元形状に関する有用な情報を提供する。
【００２９】
対照的に、米国特許出願公開第２００６／２３９５５８号は、画素の深さ値に従って、シーン内の画素に同じラベルを割り振る。これは、シーン内の異なる別個の物体に属する画素が、同一の物体として誤って識別される可能性があることを意味する。
【００３０】
米国特許第６７７１８１８号では、識別されたクラスタをモデルと比較して、遮蔽されている可能性がある物体に画素が属するかどうかを判断する。
【００３１】
有利には、画素は、ベクトル量子化アルゴリズムを使用していくつかの領域にグループ分けすることができる。特に、前記ベクトル量子化アルゴリズムにおいて、
−第１のフレームにおいて、ｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムを使用して画素をＫ個の領域にグループ分けすることができ、
−後続のフレームにおいて、
・制約付きＫ−ｍｅａｎｓアルゴリズムを使用して、画素を前のフレームの領域にグループ分けし、距離制約を使用して、これらの領域のうちの任意の領域の重心から所定の距離Ｑよりも離れている画素を排除し、
・ｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムを使用して、残っている画素があればそれを新たな領域にグループ分けし、
・最後に、この後続のフレームにおいて、前のフレームの領域にいかなる画素も割り当てられていない場合には、その領域を削除することができ、数値Ｋを１だけ減分する。
【００３２】
特に、前記ｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムにおいて、
・画素が領域重心から前記距離Ｑよりも離れている場合には、新たな領域が生成され、数値Ｋが１だけ増分され、また
・画素が領域重心から前記距離Ｑ以内にある場合には、その画素は対応する領域に割り当てられ、それに従って重心の位置が更新される。
【００３３】
そのようなｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムは、いくつかの領域への画素の均一な分散を可能にし、それと同時に、領域の粒度を実質的に一定に保ち、領域の連続的なリフレッシュを保証し、計算リソース消費を制限する。
【００３４】
有利には、
−それら２つの領域の一方での少なくとも１つの画素とそれら２つの領域の他方での別の画素が２次元投影で隣接する場合、及び
−これら２つの領域の隣接する画素の各対における深さの平均差が、前記所定の距離Δｄ１未満である場合
に、２つの領域が３次元空間内で接続されていると判断することができる。
【００３５】
２つの画素は、それらが前記２次元投影で少なくとも１方向で所定の距離以内にある場合に、２次元投影で隣接しているとみなすことができる。
【００３６】
これらの基準により、空間内の単一の物体又は接続された複数の物体の点を表現する画素をグループ分けする複数の領域を、単一のクラスタにグループ分けすることができる。
【００３７】
さらに有利には、後続のフレームにおいて、前のフレームには存在しなかった新たな領域が前記３次元空間内で直接又は少なくとも１つの別の領域を介して前記既存のクラスタの領域に接続されている場合に、前記新たな領域が、前記前のフレームに既に存在していた相互接続された領域の既存のクラスタに属すると判断することができる。したがって、各クラスタの内容は、各後続のフレームにおいて新たに存在する候補領域があればそれを考慮に入れて、連続的に更新することができる。
【００３８】
有利には、本発明による方法の好ましい一実施例は、前記画素を領域にグループ分けする前に、基準フレーム内の対応する画素の深さ値と所定量Δｄ２未満しか異ならない各画素を前記シーケンス内の各フレームから削除する別のステップを含むことができる。したがって、基準フレーム内に既に存在していた背景から前景物体が切り離され、コンピュータ実装追跡方法の計算要件をさらに低減させる。
【００３９】
有利には、前記フレーム・シーケンスは、実世界シーンを捕捉する３Ｄ撮像デバイスからのビデオ・シーケンスでよい。したがって、本発明のこの実施例によるコンピュータ実装追跡方法は、例えばビデオ・ゲーム、シミュレーション、仮想環境、遠隔操作などの用途で、コンピュータ・システムとのリアルタイム対話、例えば命令又はデータの入力のために使用することができる。
【００４０】
さらに有利には、本発明のこの実施例において、画素を領域にグループ分けするステップの前に、撮像デバイスにリンクされた座標系から、前記実世界シーンでの点にリンクされた別の座標系に座標変換を行うことができる。このステップにより、画素座標を、本発明による追跡方法の後続のステップを単純化する別の座標系に変換することができる。
【００４１】
本発明のさらなる目的は、連続するフレーム・シーケンスを含む３次元ビデオ・シーケンスで少なくとも１つの物体を追跡する方法であって、各フレームが画素アレイを備え、深さ値が各画素に関連付けられる方法を使用する用途で、物体のアクティブ化及び／又は非アクティブ化を管理することである。
【００４２】
したがって、本発明の有利な実施例による方法は、さらに、前記シーケンスの少なくとも１つのフレームに関して、物体が第１の組のアクティブ化基準を満たす場合には、前記フレーム内で物体を予備アクティブ化するステップと、所定のアクティブ化規則の下で物体が第２の組のアクティブ化基準を満たす場合には、予備アクティブ状態の物体をアクティブ化するステップとを含むことができる。したがって、第１の組のアクティブ化基準は、第１の絶対フィルタとして働く。予備アクティブ状態の物体のその後のアクティブ化は、各予備アクティブ状態の物体が第２の組のアクティブ化基準を満たすかどうかに依存するだけでなく、アクティブ化規則にも依存する。
【００４３】
有利には、前記第１の組のアクティブ化基準及び／又は前記第２の組のアクティブ化基準が、
−アクティブ化又は非アクティブ化することができる物体の最大数、
−物体の位置、
−物体のサイズ、
−物体の動き、
−物体の形状、
−物体の色、
−物体が非アクティブ状態を保っている、連続する前のフレームの最大数、又は
−ユーザ選択
のうちの少なくとも１つの基準を含むことができる。
【００４４】
有利には、前記アクティブ化規則は、
−第２の組のアクティブ化基準を満たす全ての予備アクティブ状態の物体をアクティブ化する強制アクティブ化規則、
−アクティブ状態の物体が非アクティブ化される場合にのみ、前記第２の組のアクティブ化基準を満たす物体をアクティブ化するランク付きアクティブ化規則、
−前記第２の組のアクティブ化基準を最も良く満たす物体をアクティブ化する単純アクティブ化規則、
−関連し合う別のアクティブ状態の物体が非アクティブ化された場合に物体をアクティブ化する単純交換アクティブ化規則、
−別の物体によって遮蔽される又は遮蔽されている場合に物体をアクティブ化する遮蔽アクティブ化規則、又は
−別のアクティブ状態の物体に接触する場合に物体をアクティブ化する接触交換アクティブ化規則
からなる１組のアクティブ化規則のうちの１つでよい。
【００４５】
これらのアクティブ化基準及び規則は、本発明の物体追跡方法に基づいて、広い範囲の対話の可能性を開く。
【００４６】
さらに有利には、本発明による方法の一実施例はまた、前記シーケンスの少なくとも１つの後続のフレームに関して、所定の非アクティブ化規則の下で物体が１組の非アクティブ化基準を満たす場合に、事前にアクティブ化されている物体を非アクティブ化するステップを含むこともできる。
【００４７】
非アクティブ化基準の前記組は、
−アクティブ化又は非アクティブ化することができる物体の最大数、
−物体の位置、
−物体の形状、
−物体の色、
−物体ランキング、
−物体がアクティブ状態を保っている、連続する前のフレームの最大数及び／又は最小数、或いは
−ユーザ選択
のうちの少なくとも１つの基準を備えることができる。
【００４８】
前記非アクティブ化規則は、
−前記非アクティブ化基準の組を満たす全てのアクティブ状態の物体を非アクティブ化する強制非アクティブ化規則、
−非アクティブ状態の物体がアクティブ化される場合にのみ、前記非アクティブ化基準の組を満たす物体を非アクティブ化するランク付き非アクティブ化規則、
−前記非アクティブ化基準の組を最も良く満たす物体を非アクティブ化する単純非アクティブ化規則、
−関連し合う別の非アクティブ状態の物体がアクティブ化された場合に物体を非アクティブ化する単純交換非アクティブ化規則、又は
−別の非アクティブ状態であるが予備アクティブ化されている物体に接触する場合に物体を非アクティブ化する接触交換非アクティブ化規則
の中から選択することができる。
【００４９】
また本発明は、本発明の実施例の任意のものによる方法を実施するためのコンピュータ実行可能命令を有するコンピュータ可読データ記憶媒体に関し、さらにまた、３次元ビデオ・シーケンス用の入力を備え、本発明の実施例の任意のものによるコンピュータ実装方法を実施するようにプログラムされたコンピュータ・システムであって、３次元ビデオ・シーケンスが、連続するフレーム・シーケンスを有し、各フレームが画素アレイを有し、各画素に深さ値が関連付けられるコンピュータ・システムに関する。
【００５０】
「コンピュータ可読データ記憶媒体」という用語は、限定はしないが、ランダム・アクセス・メモリ、フラッシュ・メモリ、又は読み出し専用メモリなどのソリッドステート・メモリ、さらには、ハードディスク・ドライブ又は磁気テープなどの磁気データ記憶媒体、及び光ディスクなどの光データ記憶媒体を含めた、デジタル・データを含む任意のコンピュータ可読サポートを意味する。
【００５１】
本発明のこれら及び他の目的は、以下の詳細な説明を読み、添付図面を参照すれば、より容易に明らかになろう。
【図面の簡単な説明】
【００５２】
【図１】３Ｄ撮像デバイスの前に立つ人間ユーザのいる部屋を示す図である。
【図２】３Ｄ撮像システムによって捕捉されたときの、３次元空間内に分散された画素の形態での、同じ部屋の３次元画像データを示す図である。
【図３】前記画像データ内部のクリップされたボリュームであって、背景除去後の人間ユーザに対応する画素をグループ分けする相互接続された領域のクラスタを含むボリュームの２次元投影を示す図である。
【図４Ａ】３Ｄビデオ・シーケンスの連続フレームで、相互接続された領域のクラスタが更新される状況を示す図である。
【図４Ｂ】３Ｄビデオ・シーケンスの連続フレームで、相互接続された領域のクラスタが更新される状況を示す図である。
【図４Ｃ】３Ｄビデオ・シーケンスの連続フレームで、相互接続された領域のクラスタが更新される状況を示す図である。
【図５】１人の人間ユーザと、そのユーザを部分的に遮る別の人間ユーザとを表す相互接続された領域のクラスタを示す図である。
【図６Ａ】位置基準と単純アクティブ及び非アクティブ化規則を使用して、物体をアクティブ化及び非アクティブ化することができる状況を示す図である。
【図６Ｂ】位置基準と単純アクティブ及び非アクティブ化規則を使用して、物体をアクティブ化及び非アクティブ化することができる状況を示す図である。
【図６Ｃ】位置基準と単純アクティブ及び非アクティブ化規則を使用して、物体をアクティブ化及び非アクティブ化することができる状況を示す図である。
【図７Ａ】位置基準と接触交換規則を使用して、第１の物体をアクティブ化することができ、第２の物体を非アクティブ化することができる状況を示す図である。
【図７Ｂ】位置基準と接触交換規則を使用して、第１の物体をアクティブ化することができ、第２の物体を非アクティブ化することができる状況を示す図である。
【図８Ａ】位置基準と単純アクティブ化及び非アクティブ化規則を使用して、第１の物体がアクティブ化及び非アクティブ化される状況、及び位置基準とランク付きアクティブ化規則を使用して第２の物体がアクティブ化される状況を示す図である。
【図８Ｂ】位置基準と単純アクティブ化及び非アクティブ化規則を使用して、第１の物体がアクティブ化及び非アクティブ化される状況、及び位置基準とランク付きアクティブ化規則を使用して第２の物体がアクティブ化される状況を示す図である。
【図８Ｃ】位置基準と単純アクティブ化及び非アクティブ化規則を使用して、第１の物体がアクティブ化及び非アクティブ化される状況、及び位置基準とランク付きアクティブ化規則を使用して第２の物体がアクティブ化される状況を示す図である。
【発明を実施するための形態】
【００５３】
本発明は様々な修正形態及び代替形態が可能であるが、本発明の具体的な実施例を図面に例として示してあり、本明細書で詳細に述べる。しかし、開示する特定の形態に本発明を限定する意図はなく、逆に、本発明は、添付の特許請求の範囲で表される本発明の範囲に入る全ての修正形態、均等形態、及び代替形態を網羅するものであることを理解すべきである。
【００５４】
本発明の一実施例によるコンピュータ実装物体追跡方法及びコンピュータ・システムの一実施例の可能な使用例の１つを図１に示す。本出願では、対象物、この場合には人間ユーザ１のジェスチャを認識するためのこのシステム及び方法を、人間ユーザ１に表示される仮想環境を生成するコンピュータ・システム２と対話するために使用する。
【００５５】
ボリューム認識システムは、３Ｄ撮像システム、この特定の実施例では飛行時間（ＴＯＦ）３Ｄカメラ３を有する。このＴＯＦ３Ｄカメラ３はコンピュータ・システム２に接続され、人間ユーザ１は、そのコンピュータ・システム２と対話することができる。この実施例では、このコンピュータ・システム２は、それ自体、ＴＯＦ３Ｄカメラ３と協働して本発明のボリューム認識法を実施するようにプログラムされる。或いは、人間ユーザが前記コンピュータ・システム２と対話できるようにするために、前記方法を実施するようにプログラムされた別個のデータ処理デバイスをＴＯＦ３Ｄカメラとコンピュータ・システム２の間に接続することができる。
【００５６】
ＴＯＦ３Ｄカメラ３は、人間ユーザ１がいる部屋４の３Ｄ画像データを含む連続フレームを捕捉する。３Ｄ画像データは、２Ｄ画素アレイと、各画素に関する深さ値とを含み、深さ値は、その画素によって表された点からＴＯＦ３Ｄカメラ３までの距離に対応する。２Ｄ画素アレイ内の画素の垂直位置と水平位置は、それら自体、それらが表現する点のＴＯＦ３Ｄカメラ３に対する天頂角と方位角に対応するので、図２におけるように、各フレームは、ＴＯＦ３Ｄカメラ３の視程内の物体の可視点に対応する画素５の３次元クラウドによって示すことができる。
【００５７】
これらの連続フレームは、３次元ビデオ・シーケンスを生成し、これがコンピュータ・システム２に伝送される。第１のステップで、前記コンピュータ・システム３の内部にあるデータ処理装置は、ビデオ・シーケンス内の各フレームの画素５の３次元クラウドのカメラに対する画素位置を、シーンに固定された座標系６での座標に変換する。この座標系６は、３つの直交軸、すなわち横軸Ｘ、深さ軸Ｙ、及び高さ軸Ｚを有する。その後、不十分な画素情報しか入手できない画素、又はセンサ雑音によるものである可能性がある画素を、フィルタを使用してフレームから除去することができる。
【００５８】
また、後続のステップにおいて、フレームを、背景のみを含む事前に捕捉された基準フレームと比較することによって、シーン背景に対応する各フレーム内の画素５を除去することもできる。前記深さ軸Ｙで、基準フレーム内の対応する画素からしきい値距離Δｄ２を超えていない全ての画素５を、画像から差し引く。しかし或いは、代わりにリアルタイムで基準背景を更新することによって、この背景除去を動的に行うこともできる。
【００５９】
その後、データ処理要件を低減するために、得られた画像をクリップして、残っている画素５を含むより小さなボリューム７にすることができる。
【００６０】
次いで、データ処理装置によって、コンピュータ・メモリにおいて、それらの残っている画素５を複数の領域Ｒｉ（ここでｉ＝１，…，Ｋ）にグループ分けする。有利には、以下のようにベクトル量子化アルゴリズムを使用して画素をグループ分けする。
【００６１】
ビデオ・シーケンスの第１のフレームにおいて、ｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムを使用して画素をＫ個の領域にグループ分けする。このアルゴリズムでは、画素が領域重心から前記距離Ｑよりも離れている場合には、新たな領域が生成され、数値Ｋが１だけ増分される。画素が領域重心から前記距離Ｑ以内にある場合には、その画素は対応する領域に割り当てられ、それに従って重心の位置が更新される。したがって、前記第１のフレームでの第１の画素から始めると、領域がまだ１つも生成されていないので（Ｋ＝０）、第１の領域が生成され、Ｋが１に設定され、この第１の領域の重心の位置は第１の画素の位置となる。次の画素に関して、その画素が第１の画素から前記距離Ｑ以内にある場合には、その画素は第１の領域に組み込まれ、第１の領域の重心の位置が変わる。しかし、その画素が前記距離Ｑよりも離れている場合には、新たな領域が生成され、Ｋが２に設定される。
【００６２】
各後続のフレームにおいて、まず制約付きＫ−ｍｅａｎｓアルゴリズムを使用して、画素の少なくともいくつかをグループ分けする。Ｋ−ｍｅａｎｓアルゴリズムは反復アルゴリズムであり、時間的コヒーレンスの度合いを導入するために、Ｋ個の領域の重心の初期位置Ｃｉ（この場合には、前のフレームに関して決定されている位置）を定義した後、まず、１組のＮ個の画素の各画素ｊが、以下の式によって表される前記Ｋ個の領域のうちの１つの領域Ｒｓに関連付けられる。
【００６３】
【数１】
ここで、Ｐｊは、上述した座標系６での画素ｊの位置である。この特定の制約付きＫ−ｍｅａｎｓアルゴリズムでは、重心から前記所定の距離Ｑよりも離れている画素は、割り当てられていないままである。
【００６４】
各画素ｊ＝１，…，Ｎを前記Ｋ個の領域の１つに割り振った後、各領域に割り振られた画素の質量中心の位置を計算することによって、それらのＫ個の領域の重心の位置Ｃｉが更新される。
【００６５】
【数２】
ここで、ｎは、領域Ｒｉに割り振られた画素の数である。
【００６６】
次いで、Ｋ個の領域への画素の安定した割振りに落ち着くまで、これら２つのステップを繰り返し行うことができる。
【００６７】
次いで、割り当てられていないままの画素を、上述したのと同じｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムを使用して新たな領域にグループ分けすることができる。このアルゴリズムでは、画素が領域重心から前記距離Ｑよりも離れている場合に、新たな領域が生成され、数値Ｋが１だけ増分される。画素が領域重心から前記距離Ｑ以内にある場合には、その画素は対応する領域に割り当てられ、それに従って重心の位置が更新される。
【００６８】
最後に、Ｋ個の領域のうちの１つの領域が、このフレームにおいてその領域に割り当てられる画素がなく空のままである場合、この領域Ｒｉは削除され、数値Ｋが１だけ減分される。
【００６９】
フレームにおいて得られた１組の領域Ｒｉが図３に示される。
【００７０】
各フレームに関する次のステップは、領域隣接グラフ（ＲＡＧ）を生成し、コンピュータ・メモリにおいて、領域Ｒｉを相互接続された領域のクラスタＢにグループ分けすることを含む。データ処理装置は、
−領域Ｒａ内の少なくとも１つの画素と領域Ｒｂ内の別の画素とが、Ｘ−Ｚ平面上への２次元投影で隣接する場合、及び
−これら２つの領域Ｒａ、Ｒｂの隣接する画素の各対におけるＹ軸での深さの平均差が、所定の距離Δｄ１未満である場合に、
２つの領域Ｒａ、Ｒｂ（ここでａとｂは、０〜Ｋの間の２つの異なる数）が３次元空間内で接続されていると判断する。
【００７１】
２つの画素は、これら２つの画素の一方が、少なくともＸ軸又はＺ軸で他方の画素の次、次の次、又はそのまた次の画素である場合に、２次元投影で隣接しているとみなされる。
【００７２】
２つの領域Ｒａ、Ｒｂが、Ｘ−Ｚ平面上への投影で隣接する画素を有するが、隣接する画素のこれらの各対における深さの平均差が前記所定の距離Δｄ１を超えている場合、領域ＲａとＲｂは、ほぼ間違いなく接続されているものとしてフラグを立てることができる。この場合、それらの領域を相互接続された領域として単一のクラスタＢ０にグループ分けするかどうかは、１組の追加の基準に応じて決まることがある。
【００７３】
いくつかのクラスタＢ０が第１のフレームにおいて生成され、各クラスタが、１組の相互接続された領域を組み込む。後続のフレームに関して、新たな領域Ｒｃが直接又は少なくとも別の領域Ｒｄを介して既存のクラスタＢ０の領域に接続されている場合には、その領域Ｒｃは既存のクラスタＢ０に組み込まれる。これは、以下のアルゴリズムを実行するデータ処理装置によって決定される。
【００７４】
各領域Ｒｉに関して、
−領域Ｒｉが前のフレームで存在していた場合、したがって既存のクラスタＢ０に関連付けられる場合には、時間コヒーレンスを考慮して、Ｒｉが属するクラスタに対するＲｉの距離のインジケータ「ｄｉｓｔａｎｃｅ（Ｒｉ）」はゼロに設定され、インジケータ「ｏｂｊｅｃｔ（Ｒｉ）」は「Ｂ０」に設定され、「ｄｉｓｔａｎｃｅ（Ｒｉ）」の値に関して昇順でソートされたリストＨ内にＲｉが記憶される。
−そうでない場合には、「ｄｉｓｔａｎｃｅ（Ｒｉ）」が「ＩＮＦＩＮＩＴＥ（無限）」に設定され、「ｏｂｊｅｃｔ（Ｒｉ）」が「ＮＵＬＬ（ゼロ）」に設定される。
【００７５】
次いで、リストＨが空でない限り、以下のことが繰り返される。
−リストＨから、最小のインジケータ「ｄｉｓｔａｎｃｅ（Ｒｈ）」の値を有する領域Ｒｈを抽出する。
−領域Ｒｈに隣接する各領域Ｒｖに関して、
・ｄ＝ｄｉｓｔａｎｃｅ（Ｒｈ）＋ｄｉｓｔａｎｃｅＲＡＧ（Ｒｈ，Ｒｖ）を計算する。ここで、ＲｈとＲｖが接続されている場合、ｄｉｓｔａｎｃｅＲＡＧ（Ｒｈ，Ｒｖ）＝０であり、ＲｈとＲｖが接続されていない場合、ｄｉｓｔａｎｃｅＲＡＧ（Ｒｈ，Ｒｖ）＝ＩＮＦＩＮＩＴＥであり、並びに
・ｄ＜ｄｉｓｔａｎｃｅ（Ｒｖ）である場合、
・「ｄｉｓｔａｎｃｅ（Ｒｖ）」の値を値ｄに設定し、
・「ｏｂｊｅｃｔ（Ｒｖ）」の値を「ｏｂｊｅｃｔ（Ｒｈ）」の値に設定し、及び
・領域ＲｖがリストＨ内にない場合には、それをリストＨに挿入し、
・領域Ｒｖが既にリストＨ内にある場合には、それをＨから抽出する。
【００７６】
それにより、既存のクラスタに接続させることができる全ての領域を既存のクラスタに組み込んだ後、残っている領域があればそれを接続に関してチェックして、必要であれば、そのような領域を組み込む追加のクラスタを生成する。図４Ａ、図４Ｂ、及び図４Ｃは、２つの連続フレーム間のこの遷移を示す。
【００７７】
図４Ａに示される第１のフレームには、２つのクラスタＢ１とＢ２が存在する。Ｂ１は、相互接続された領域Ｒ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５、及びＲ６を有し、Ｂ２は、相互接続された領域Ｒ７、Ｒ８、Ｒ９、Ｒ１０、及びＲ１１を有する。図４Ｂに示される次のフレームでは、Ｂ２は依然として存在するが、Ｒ７が消えている。他方、新たな領域Ｒ１２、Ｒ１３、Ｒ１４、Ｒ１５、Ｒ１６、及びＲ１７が現れている。Ｒ１２は、クラスタＢ１の領域Ｒ６に接続され、Ｒ１３は、クラスタＢ２の領域Ｒ１１に接続され、Ｒ１４は、Ｒ１３に接続されている。Ｒ１５と、Ｒ１６と、Ｒ１７は、相互接続されるが、いかなる他の領域又はクラスタにも接続していない。したがって、図４Ｃで見ることができるように、Ｒ１２は、クラスタＢ１に組み込まれ、Ｒ１３及びＲ１４は、クラスタＢ２に組み込まれる。Ｒ１５、Ｒ１６、及びＲ１７は、新たなクラスタＢ３を形成する。
【００７８】
次のステップでは、クラスタ関係グラフ（ＣＲＧ）が確立される。このＣＲＧにおいて、Ｘ−Ｚ平面上への２次元投影で隣接するクラスタの対（すなわち、各クラスタが、Ｘ−Ｚ平面上への２次元投影で、他方のクラスタの領域内の少なくとも１つの画素に隣接する少なくとも１つの画素を有する領域を備える）が、「２Ｄ接続」とタグ付けされた第１のタイプのリンクでリンクされる。次いで、両方のクラスタが共通の隣接するクラスタへの「２Ｄ接続」リンクを有するが、共通の隣接するクラスタよりも高い深さ値を有し、深さ軸で互いから所定の距離Δｄ１以内にあるようなクラスタの対が、「３Ｄ接続可能」とタグ付けされた第２のタイプのリンクでリンクされる。
【００７９】
「３Ｄ接続可能」リンクによってリンクされたクラスタは、それらの共通の隣接するクラスタによって表される別の物体によって部分的に遮蔽された物体に属する可能性がある。それらのクラスタを実際に単一の物体に属するものとして互いに相互接続すべきかどうか判断するために、次いで、それらのクラスタが、前記２次元投影内で「スタック可能」であるかどうか、すなわち前記２次元投影の少なくとも１つの軸で少なくとも最小の正規化長さｏｍｉｎだけ互いに重畳しているかどうか検査される。正規化された重畳長さの値ｏ＝Ｏ／Ｌであり、ここで、Ｏは、その軸での絶対重畳長さであり、Ｌは、その軸での２つの「３Ｄ接続可能」クラスタの短い方の長さである。
【００８０】
図５は、フレームが１組のクラスタＢ１、Ｂ２、Ｂ３、Ｂ４、及びＢ５を示し、これらのクラスタが２つの物体、すなわち第１の人間ユーザＵ１と、第１の人間ユーザＵ１によって部分的に遮蔽されている第２の人間ユーザＵ２とを表す一例である。第２の人間ユーザＵ２の前に第１の人間ユーザＵ１がいることで、第２の人間ユーザＵ２がクラスタＢ２、Ｂ３、Ｂ４、及びＢ５に実質的に分割されることを容易に理解されよう。クラスタＢ２、Ｂ３、Ｂ４、及びＢ５は全て、Ｘ−Ｚ平面への２次元投影でクラスタＢ１に隣接しており、Ｙ軸でのそれらの平均の深さは、最小距離よりも大きくＢ１の深さを上回っているので、それらは、「２Ｄ接続」リンク７によってＢ１とリンクさせることができる。それらはまた、深さ軸Ｙで互いに所定の範囲内にあるので、「３Ｄ接続可能」リンク８で互いにリンクさせることができる。
【００８１】
したがって、次のステップでは、「３Ｄ接続可能」タイプのリンク８によってリンクされたそれらのクラスタＢ２、Ｂ３、Ｂ４、及びＢ５が、さらに、前記２次元投影の少なくとも１つの軸で、少なくとも最小の正規化長さｏｍｉｎだけ互いに重畳しているかどうかチェックされる。図示される実例では、Ｂ３は、Ｂ２と、Ｘ軸において十分な正規化長さｏＸ（３，２）＞ｏｍｉｎだけ重畳しており、また、Ｂ４及びＢ５は、それぞれＢ２及びＢ３と、Ｚ軸において十分な正規化長さｏＺ（４，２）＞ｏｍｉｎ及びｏＺ（５，３）＞ｏｍｉｎだけ重畳している。
【００８２】
正規化された重畳長さｏＸ（３，２）＝ＯＸ（３，２）／ＬＸ３であり、ここで、ＯＸ（３，２）は、Ｘ軸でのＢ３とＢ２の重畳であり、ＬＸ３は、Ｘ軸でのＢ３の長さである。正規化された重畳長さｏＺ（４，２）＝ＯＺ（４，２）／ＬＺ４であり、ここで、ＯＺ（４，２）は、Ｚ軸でのＢ４とＢ２の重畳であり、ＬＺ４は、Ｚ軸でのＢ４の長さである。最後に、正規化された重畳長さｏＺ（５，３）＝ＯＺ（５，３）／ＬＺ５であり、ここで、ＯＺ（５，３）は、Ｚ軸でのＢ５とＢ３の重畳であり、ＬＺ５は、Ｚ軸でのＢ５の長さである。
【００８３】
したがって、クラスタＢ２、Ｂ３、Ｂ４、及びＢ５は、コンピュータ・メモリにおいて、クラスタＢ１を備える別の物体Ｕ１によって部分的に遮蔽されている単一の物体Ｕ２に割り当てることができる。
【００８４】
この図示した実施例では、これらの「３Ｄ接続可能」試験と「スタック可能」試験が組み合わせて使用され、クラスタが両方の条件を満たさない場合には、クラスタが単一の物体に属することが除外されるが、代替実施例では、それらの試験は、互いに別個に、又は互いに並列して使用することもできる。これら２つの条件のそれぞれを包含的条件として適用することができ、したがって、条件が満たされる場合に、２つのクラスタが単一の物体に属するものとみなされる。しかしこれは、条件が満たされない場合も依然として排除されてはいない。各条件は、さらに、包含及び排他のための様々なしきい値を使用して、包含的及び排他的に個別に適用することができる。
【００８５】
後続のフレームに関して、データ処理装置は、新たなＣＲＧを生成し、まず上述した試験を使用して、新たなクラスタを既存の物体に割り当てることができるかどうかチェックする。次いで、同じ試験を使用して、残っている新たなクラスタがあればそれを新たな物体にグループ分けすることができるかどうかチェックする。
【００８６】
したがって、複数の物体を、それらの物体の１つが別の物体に遮蔽されているときでさえ、フレーム・シーケンス全体にわたって追跡することができる。そのような物体は、静止していても、移動可能でもよい。この物体追跡方法が、ビデオ・ゲーム、シミュレーション、又は仮想現実アプリケーションなどのコンピュータ・アプリケーションと対話するために使用されるとき、追跡される物体はそれぞれ、様々なアクティブ化／非アクティブ化基準とアクティブ化／非アクティブ化規則の組に従ってアクティブ化及び／又は非アクティブ化することができる。
【００８７】
本発明の特定の一実施例では、フレーム・シーケンス内の少なくとも１つの物体を追跡する方法であって、各フレームが画素アレイを有し、深さ値が各画素に関連付けられている方法が、さらに、少なくとも１つのフレームに関して、物体が第１の組のアクティブ化基準を満たす場合には、前記フレーム内で物体を予備アクティブ化するステップと、所定のアクティブ化規則の下で物体が第２の組のアクティブ化基準を満たす場合には、予備アクティブ状態の物体をアクティブ化するステップとを含む。
【００８８】
好ましくは、この方法はまた、前記シーケンスの少なくとも１つの後続のフレームに関して、所定の非アクティブ化規則の下で物体が１組の非アクティブ化基準を満たす場合に、事前にアクティブ化されている物体を非アクティブ化するステップを含むこともできる。
【００８９】
第１の組のアクティブ化基準は、以下の基準の少なくとも１つを含むことができる。
【００９０】
物体の位置：すなわち、この要件により、追跡される物体は、別の追跡される物体など移動基準及び／又は静止基準に対してある相対位置範囲内にある（さらには接触している）場合に予備アクティブ化される。
【００９１】
物体のサイズ：すなわち、この要件により、追跡される物体は、１次元、２次元、又は３次元での少なくとも所定の最小サイズ及び／又は多くとも所定の最大サイズを有する場合に予備アクティブ化される。
【００９２】
物体の動き：すなわち、この要件により、追跡される物体は、シーケンス内の少なくとも１つの前のフレームに対する少なくとも所定の最小の動き及び／又は多くとも所定の最大の動きを示す場合に予備アクティブ化される。
【００９３】
物体の形状：すなわち、この要件により、追跡される物体は、例えば人体を表すパターンなど所定のパターンにその物体の形状を合致させることができる場合に予備アクティブ化される。
【００９４】
物体の色：すなわち、この要件により、追跡される物体は、所定の色範囲内の色値を有する１つ又は複数の画素を含む場合に予備アクティブ化される。
【００９５】
物体の持続性：すなわち、この要件により、追跡される物体は、連続する前のフレームの少なくとも最小数及び／又は多くとも最大数にわたってアクティブ状態又は非アクティブ状態として追跡されている場合に予備アクティブ化される。
【００９６】
ユーザ選択：すなわち、この要件により、追跡される物体は、例えば「物体を見えるようにする」といったコマンドなど明示的なユーザ選択によって事前にフラグを立てられている場合に予備アクティブ化される。
【００９７】
アクティブ状態の物体の最大数：すなわち、この要件により、追跡される物体は、アクティブ状態の物体の数が所定の最大数を超えない場合にアクティブ化される。
【００９８】
この第２の組のアクティブ化基準は、アクティブ化規則に関連付けて使用される。このアクティブ化規則は、例えば、第２の組のアクティブ化基準を満たす全ての予備アクティブ状態の物体をアクティブ化する強制アクティブ化規則、アクティブ状態の物体が非アクティブ化される場合にのみ、前記第２の組のアクティブ化基準を満たす物体をアクティブ化するランク付きアクティブ化規則、前記第２の組のアクティブ化基準を最も良く満たす１つ又は複数の物体をアクティブ化する単純アクティブ化規則、関連し合う別のアクティブ状態の物体が非アクティブ化された場合に物体をアクティブ化する単純交換アクティブ化規則、別の物体によって遮蔽される又は遮蔽されている場合に物体をアクティブ化する遮蔽アクティブ化規則、又は別のアクティブ状態の物体に接触する場合に物体をアクティブ化する接触交換アクティブ化規則でよい。
【００９９】
非アクティブ化基準の組は、第２の組のアクティブ化基準のものと同様の基準を含むことがある。また、物体ランキング基準も備えることがあり、これは、物体のランキングが最小値未満である場合に、アクティブ状態の物体を非アクティブ化できるようにする。物体ランキングは、例えば、アクティブ状態の物体の組がアクティブ化された順序によって決定することができる。
【０１００】
非アクティブ化規則は、例えば、前記非アクティブ化基準の組を満たす全てのアクティブ状態の物体を非アクティブ化する強制非アクティブ化規則、非アクティブ状態の物体がアクティブ化される場合にのみ、前記非アクティブ化基準の組を満たす物体を非アクティブ化するランク付き非アクティブ化規則、前記非アクティブ化基準の組を最も良く満たす物体を非アクティブ化する単純非アクティブ化規則、関連し合う別の非アクティブ状態の物体がアクティブ化された場合に物体を非アクティブ化する単純交換非アクティブ化規則、又は別の非アクティブ状態であるが予備アクティブ化されている物体に接触する場合に物体を非アクティブ化する接触交換非アクティブ化規則でよい。
【０１０１】
したがって、アクティブ化基準及び規則、並びに非アクティブ化基準及び規則の組合せに応じて、様々なシナリオが利用可能である。
【０１０２】
例えば、図６Ａにおいて、物体Ｕ１が示されており、この物体Ｕ１は、予備アクティブ状態で、静止基準１１を中心とする円１０に入っており、アクティブ化のための位置基準を満たす。その結果、物体Ｕ１は、単純アクティブ化規則に従ってアクティブ化される。図６Ｂでは、物体Ｕ１は、円１０から出ているが、非アクティブ化のための位置基準はより大きな円１２よりも外にあるので、アクティブ状態のままである。図６Ｃに示されるように、物体Ｕ１がより大きな円１２から出たときにのみ、別の単純非アクティブ化規則の下で非アクティブ化することができる。
【０１０３】
図７Ａにおいて、２つの物体Ｕ１とＵ２は、接触していないものとして示されている。この場合には、２つの物体Ｕ１及びＵ２は、それぞれのユーザＵｓｅｒ１及びＵｓｅｒ２に対応する。第１の物体Ｕ１はアクティブ状態であり、第２の物体Ｕ２は予備アクティブ状態である。第１の物体Ｕ１は、非アクティブ状態であるが予備アクティブ化されている物体と接触するという非アクティブ化のための位置基準を満たすので、接触交換非アクティブ化規則の下で非アクティブ化することができる。他方、第２の物体Ｕ２は、アクティブ状態の物体と接触するというアクティブ化のための位置基準を満たすので、接触交換アクティブ化規則の下でアクティブ化される。その結果生じた状態交換が、図７Ｂに示される。
【０１０４】
図７Ｂでは、接触交換アクティブ化規則の下で、物体Ｕ２が物体Ｕ１と接触するとき、物体Ｕ２は、（非アクティブ状態であるが予備アクティブ化されていたので）アクティブ状態になり、物体Ｕ１は、ここでアクティブ化された物体Ｕ２と接触するので、非アクティブ化される。
【０１０５】
図８Ａにおいて、第１の物体Ｕ１が示されており、この物体Ｕ１は、予備アクティブ状態で、静止基準１１を中心とする円１０に入っており、アクティブ化のための位置基準を満たしている。その結果、この第１の物体Ｕ１は、単純アクティブ化規則に従ってアクティブ化される。円１０の内部にない第２の物体Ｕ２は、非アクティブ状態のままである。図８Ｂでは、第１の物体Ｕ１は、ここでは円１０の外である。しかし、非アクティブ化のための位置基準はより大きな円１２よりも外にあるので、第１の物体Ｕ１は非アクティブ状態のままである。第２の物体Ｕ２は、ここでは予備アクティブ状態であり円１０内にあるが、ランク付きアクティブ化規則の下では、第１の物体Ｕ１がアクティブ状態のままであるときには第２の物体Ｕ２をアクティブ化することはできない。図８Ｃに示されるように、第１の物体Ｕ１が、より大きな円１２から出た後に非アクティブ化されるときにのみ、このランク付きアクティブ化規則の下で第２の物体Ｕ２をアクティブ化することができる。
【０１０６】
アクティブ／非アクティブ化規則が許す場合には、複数の物体をアクティブ化することができることを理解されよう。これは、本発明による３次元撮像システムの視野内の同じ３次元空間内で２人以上のユーザが対話できるようにする。
【０１０７】
具体的な例示的実施例を参照しながら本発明を説明してきたが、特許請求の範囲に記載する本発明のより広範な範囲から逸脱することなく、これらの実施例に様々な修正及び変更を加えることができることは明らかであろう。例えば、物体を予備アクティブ化、アクティブ化、及び／又は非アクティブ化するステップは、部分的に遮蔽された単一の物体に複数のクラスタが属すると判断される方法又はその判断の結果とは無関係に行うことができる。したがって、本明細書及び図面は、限定的な意味合いではなく例示的な意味合いとみなすべきである。
【特許請求の範囲】
【請求項１】
フレーム・シーケンス内の少なくとも１つの物体を追跡する方法であって、各フレームが画素アレイを有し、深さ値が各画素（５）に関連付けられ、また前記方法が、
ａ）各フレームの前記画素（５）の少なくともいくつかを複数の領域（Ｒ１，…，Ｒ１７）にグループ分けするステップと、
ｂ）前記領域（Ｒ１，…，Ｒ１７）を、相互接続された領域のクラスタ（Ｂ１，…，Ｂ５）にグループ分けするステップと
を含む方法において、
ｃ）２次元投影で別のクラスタ（Ｂ１）に隣接する少なくとも１つのクラスタ（Ｂ２，…，Ｂ５）が前記別のクラスタ（Ｂ１）の深さ値よりも高い深さ値を有する場合に、前記少なくとも１つのクラスタ（Ｂ２，…，Ｂ５）が前記別のクラスタ（Ｂ１）によって部分的に遮蔽されている物体（Ｕ２）に属すると判断するステップ
をさらに含むことを特徴とする方法。
【請求項２】
ステップｃ）は、前記２次元投影で前記別のクラスタ（Ｂ１）への隣接性を共に有し且つ前記別のクラスタ（Ｂ１）よりも高い深さ値を有する２つのクラスタ（Ｂ２，…，Ｂ５）が、前記別のクラスタ（Ｂ１）によって部分的に遮蔽されている単一の物体（Ｕ２）に属するかどうかを、前記より高い深さ値が互いに所定の範囲Δｄ１内にあるかどうかに応じて判断するステップを含む請求項１に記載の方法。
【請求項３】
前記２次元投影で前記別のクラスタ（Ｂ１）への隣接性を共に有し且つ前記別のクラスタ（Ｂ１）よりも高い深さ値を有する２つのクラスタ（Ｂ２，…，Ｂ５）が、前記別のクラスタ（Ｂ１）によって部分的に遮蔽されている単一の物体に属するかどうかが、前記２次元投影の少なくとも１つの軸線において前記２つのクラスタ（Ｂ２，…，Ｂ５）のそれぞれが前記２つのクラスタ（Ｂ２，…，Ｂ５）の他方と重畳しているかどうかに応じて判断される請求項１又は２に記載の方法。
【請求項４】
前記画素（５）の少なくともいくつかが、データ処理装置によって、ベクトル量子化アルゴリズムを使用して領域（Ｒ１，…，Ｒ１７）にグループ分けされる請求項１から３までのいずれか一項に記載のコンピュータ方法。
【請求項５】
前記ベクトル量子化アルゴリズムにおいて、
−第１のフレームにおいて、ｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムを使用して、前記画素（５）がＫ個の領域（Ｒ１，…，Ｒ１１）にグループ分けされ、
−後続のフレームにおいて、
・画素（５）を前のフレームの領域（Ｒ１，…，Ｒ１１）にグループ分けするように制約付きＫ−ｍｅａｎｓアルゴリズムが使用され、領域重心（Ｃ１，…，Ｃ６）から所定の距離Ｑよりも離れている画素（５）を排除するように距離制約が使用され、
・残っている画素（５）があればそれを新たな領域（Ｒ１２，…，Ｒ１７）にグループ分けするようにｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムが使用され、また
・最後に、この後続のフレームにおいて、前のフレームの領域（Ｒ７）にいかなる画素（５）も割り当てられていない場合には、その領域（Ｒ７）が削除され、数値Ｋが１だけ減分される
請求項４に記載の方法。
【請求項６】
前記ｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムにおいて、
・画素（５）が領域重心（Ｃ１，…，Ｃ６）から前記距離Ｑよりも離れている場合には、新たな領域（Ｒ１２，…，Ｒ１７）が生成され、数値Ｋが１だけ増分され、また
・画素（５）が領域重心（Ｃ１，…，Ｃ６）から前記距離Ｑ以内にある場合には、前記画素（５）が対応する領域（Ｒ１，…，Ｒ１１）に割り当てられ、それに従って重心の位置が更新される
請求項５に記載の方法。
【請求項７】
−前記２つの領域（Ｒ１，…，Ｒ１７）の一方での少なくとも１つの画素（５）と前記２つの領域（Ｒ１，…，Ｒ１７）の他方での別の画素（５）が２次元投影で隣接する場合、及び
−前記２つの領域（Ｒ１，…，Ｒ１７）の隣接する画素（５）の各対における深さの平均差が前記所定の距離Δｄ１未満である場合に、
２つの領域（Ｒ１，…，Ｒ１７）が３次元空間内で接続されていると判断する請求項１から６までのいずれか一項に記載の方法。
【請求項８】
後続のフレームにおいて、前のフレームには存在しなかった新たな領域（Ｒ１２、Ｒ１３、Ｒ１４）が前記３次元空間内で直接又は少なくとも１つの別の領域（Ｒ１３）を介して既存のクラスタの領域（Ｒ６、Ｒ１１）に接続されている場合に、前記新たな領域（Ｒ１２、Ｒ１３、Ｒ１４）が、前記前のフレームに既に存在していた相互接続された領域の前記既存のクラスタに属すると判断される請求項４から７までのいずれか一項に記載の方法。
【請求項９】
前記画素（５）を領域（Ｒ１，…，Ｒ１７）にグループ分けする前に、基準フレーム内の対応する画素（５）の深さ値と所定量Δｄ２未満しか異ならない各画素（５）を前記シリーズ内の各フレームから削除する別のステップを含む請求項１から８までのいずれか一項に記載の方法。
【請求項１０】
前記フレーム・シーケンスが、実世界シーンを捕捉する３Ｄ撮像デバイスからのビデオ・シーケンスである請求項１から９までのいずれか一項に記載の方法。
【請求項１１】
前記画素を領域（Ｒ１，…，Ｒ１７）にグループ分けするステップの前に、撮像デバイスにリンクされた座標系から、前記実世界シーンでの点にリンクされた別の座標系に座標変換が行われる請求項１０に記載の方法。
【請求項１２】
前記シーケンスの少なくとも１つのフレームに関して、
−前記フレーム内の物体（Ｕ１、Ｕ２）が第１の組のアクティブ化基準を満たす場合に、前記物体（Ｕ１、Ｕ２）を予備アクティブ化するステップと、
−予備アクティブ状態の物体（Ｕ１、Ｕ２）が所定のアクティブ化規則の下で第２の組のアクティブ化基準を満たす場合に、前記予備アクティブ状態の物体（Ｕ１、Ｕ２）をアクティブ化するステップと
をさらに含む請求項１から１１までのいずれか一項に記載の方法。
【請求項１３】
前記第１の組のアクティブ化基準及び／又は前記第２の組のアクティブ化基準が、
−アクティブ化することができる物体の最大数、
−物体の位置、
−物体のサイズ、
−物体の動き、
−物体の形状、
−物体の色、
−物体がアクティブ状態又は非アクティブ状態を保っている、連続する前のフレームの最小数及び／又は最大数、或いは
−ユーザ選択
のうちの少なくとも１つの基準を含む請求項１２に記載の方法。
【請求項１４】
前記アクティブ化規則が、
−第２の組のアクティブ化基準を満たす全ての予備アクティブ状態の物体をアクティブ化する強制アクティブ化規則、
−アクティブ状態の物体が非アクティブ化される場合にのみ、前記第２の組のアクティブ化基準を満たす物体をアクティブ化するランク付きアクティブ化規則、
−前記第２の組のアクティブ化基準を最も良く満たす１つ又は複数の物体をアクティブ化する単純アクティブ化規則、
−関連し合う別のアクティブ状態の物体が非アクティブ化された場合に物体をアクティブ化する単純交換アクティブ化規則、
−別の物体によって遮蔽される又は遮蔽されている場合に物体をアクティブ化する遮蔽アクティブ化規則、又は
−別のアクティブ状態の物体に接触する場合に物体をアクティブ化する接触交換アクティブ化規則
からなる１組のアクティブ化規則のうちの１つである請求項１２又は１３に記載の方法。
【請求項１５】
前記シーケンスの少なくとも１つの後続のフレームに関して、所定の非アクティブ化規則の下で物体が１組の非アクティブ化基準を満たす場合に、事前にアクティブ化されている物体を非アクティブ化するステップをさらに含む請求項１２から１４までのいずれか一項に記載の方法。
【請求項１６】
非アクティブ化基準の前記組が、
−アクティブ化又は非アクティブ化することができる物体の最大数、
−物体の位置、
−物体のサイズ、
−物体の形状、
−物体の色、
−物体ランキング、
−物体がアクティブ状態を保っている、連続する前のフレームの最大数及び／又は最小数、又は
−ユーザ選択
のうちの少なくとも１つの基準を含む請求項１５に記載の方法。
【請求項１７】
前記非アクティブ化規則が、
−前記非アクティブ化基準の組を満たす全てのアクティブ状態の物体を非アクティブ化する強制非アクティブ化規則、
−非アクティブ状態の物体がアクティブ化される場合にのみ、前記非アクティブ化基準の組を満たす物体を非アクティブ化するランク付き非アクティブ化規則、
−前記非アクティブ化基準の組を最も良く満たす物体を非アクティブ化する単純非アクティブ化規則、
−関連し合う別の非アクティブ状態の物体がアクティブ化された場合に物体を非アクティブ化する単純交換非アクティブ化規則、又は
−別の非アクティブ状態であるが予備アクティブ化されている物体に接触する場合に物体を非アクティブ化する接触交換非アクティブ化規則
からなる１組の非アクティブ化規則のうちの１つである請求項１６に記載の方法。
【請求項１８】
請求項１から１７までのいずれか一項に記載の方法を実施するためのコンピュータ実行可能命令を有するコンピュータ可読データ記憶媒体。
【請求項１９】
請求項１から１７までのいずれか一項に記載の方法を実施するようにプログラムされたコンピュータ・システム。
【請求項１】
フレーム・シーケンス内の少なくとも１つの物体を追跡する方法であって、各フレームが画素アレイを有し、深さ値が各画素（５）に関連付けられ、また前記方法が、
ａ）各フレームの前記画素（５）の少なくともいくつかを複数の領域（Ｒ１，…，Ｒ１７）にグループ分けするステップと、
ｂ）前記領域（Ｒ１，…，Ｒ１７）を、相互接続された領域のクラスタ（Ｂ１，…，Ｂ５）にグループ分けするステップと
を含む方法において、
ｃ）２次元投影で別のクラスタ（Ｂ１）に隣接する少なくとも１つのクラスタ（Ｂ２，…，Ｂ５）が前記別のクラスタ（Ｂ１）の深さ値よりも高い深さ値を有する場合に、前記少なくとも１つのクラスタ（Ｂ２，…，Ｂ５）が前記別のクラスタ（Ｂ１）によって部分的に遮蔽されている物体（Ｕ２）に属すると判断するステップ
をさらに含むことを特徴とする方法。
【請求項２】
ステップｃ）は、前記２次元投影で前記別のクラスタ（Ｂ１）への隣接性を共に有し且つ前記別のクラスタ（Ｂ１）よりも高い深さ値を有する２つのクラスタ（Ｂ２，…，Ｂ５）が、前記別のクラスタ（Ｂ１）によって部分的に遮蔽されている単一の物体（Ｕ２）に属するかどうかを、前記より高い深さ値が互いに所定の範囲Δｄ１内にあるかどうかに応じて判断するステップを含む請求項１に記載の方法。
【請求項３】
前記２次元投影で前記別のクラスタ（Ｂ１）への隣接性を共に有し且つ前記別のクラスタ（Ｂ１）よりも高い深さ値を有する２つのクラスタ（Ｂ２，…，Ｂ５）が、前記別のクラスタ（Ｂ１）によって部分的に遮蔽されている単一の物体に属するかどうかが、前記２次元投影の少なくとも１つの軸線において前記２つのクラスタ（Ｂ２，…，Ｂ５）のそれぞれが前記２つのクラスタ（Ｂ２，…，Ｂ５）の他方と重畳しているかどうかに応じて判断される請求項１又は２に記載の方法。
【請求項４】
前記画素（５）の少なくともいくつかが、データ処理装置によって、ベクトル量子化アルゴリズムを使用して領域（Ｒ１，…，Ｒ１７）にグループ分けされる請求項１から３までのいずれか一項に記載のコンピュータ方法。
【請求項５】
前記ベクトル量子化アルゴリズムにおいて、
−第１のフレームにおいて、ｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムを使用して、前記画素（５）がＫ個の領域（Ｒ１，…，Ｒ１１）にグループ分けされ、
−後続のフレームにおいて、
・画素（５）を前のフレームの領域（Ｒ１，…，Ｒ１１）にグループ分けするように制約付きＫ−ｍｅａｎｓアルゴリズムが使用され、領域重心（Ｃ１，…，Ｃ６）から所定の距離Ｑよりも離れている画素（５）を排除するように距離制約が使用され、
・残っている画素（５）があればそれを新たな領域（Ｒ１２，…，Ｒ１７）にグループ分けするようにｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムが使用され、また
・最後に、この後続のフレームにおいて、前のフレームの領域（Ｒ７）にいかなる画素（５）も割り当てられていない場合には、その領域（Ｒ７）が削除され、数値Ｋが１だけ減分される
請求項４に記載の方法。
【請求項６】
前記ｌｅａｄｅｒ−ｆｏｌｌｏｗｅｒアルゴリズムにおいて、
・画素（５）が領域重心（Ｃ１，…，Ｃ６）から前記距離Ｑよりも離れている場合には、新たな領域（Ｒ１２，…，Ｒ１７）が生成され、数値Ｋが１だけ増分され、また
・画素（５）が領域重心（Ｃ１，…，Ｃ６）から前記距離Ｑ以内にある場合には、前記画素（５）が対応する領域（Ｒ１，…，Ｒ１１）に割り当てられ、それに従って重心の位置が更新される
請求項５に記載の方法。
【請求項７】
−前記２つの領域（Ｒ１，…，Ｒ１７）の一方での少なくとも１つの画素（５）と前記２つの領域（Ｒ１，…，Ｒ１７）の他方での別の画素（５）が２次元投影で隣接する場合、及び
−前記２つの領域（Ｒ１，…，Ｒ１７）の隣接する画素（５）の各対における深さの平均差が前記所定の距離Δｄ１未満である場合に、
２つの領域（Ｒ１，…，Ｒ１７）が３次元空間内で接続されていると判断する請求項１から６までのいずれか一項に記載の方法。
【請求項８】
後続のフレームにおいて、前のフレームには存在しなかった新たな領域（Ｒ１２、Ｒ１３、Ｒ１４）が前記３次元空間内で直接又は少なくとも１つの別の領域（Ｒ１３）を介して既存のクラスタの領域（Ｒ６、Ｒ１１）に接続されている場合に、前記新たな領域（Ｒ１２、Ｒ１３、Ｒ１４）が、前記前のフレームに既に存在していた相互接続された領域の前記既存のクラスタに属すると判断される請求項４から７までのいずれか一項に記載の方法。
【請求項９】
前記画素（５）を領域（Ｒ１，…，Ｒ１７）にグループ分けする前に、基準フレーム内の対応する画素（５）の深さ値と所定量Δｄ２未満しか異ならない各画素（５）を前記シリーズ内の各フレームから削除する別のステップを含む請求項１から８までのいずれか一項に記載の方法。
【請求項１０】
前記フレーム・シーケンスが、実世界シーンを捕捉する３Ｄ撮像デバイスからのビデオ・シーケンスである請求項１から９までのいずれか一項に記載の方法。
【請求項１１】
前記画素を領域（Ｒ１，…，Ｒ１７）にグループ分けするステップの前に、撮像デバイスにリンクされた座標系から、前記実世界シーンでの点にリンクされた別の座標系に座標変換が行われる請求項１０に記載の方法。
【請求項１２】
前記シーケンスの少なくとも１つのフレームに関して、
−前記フレーム内の物体（Ｕ１、Ｕ２）が第１の組のアクティブ化基準を満たす場合に、前記物体（Ｕ１、Ｕ２）を予備アクティブ化するステップと、
−予備アクティブ状態の物体（Ｕ１、Ｕ２）が所定のアクティブ化規則の下で第２の組のアクティブ化基準を満たす場合に、前記予備アクティブ状態の物体（Ｕ１、Ｕ２）をアクティブ化するステップと
をさらに含む請求項１から１１までのいずれか一項に記載の方法。
【請求項１３】
前記第１の組のアクティブ化基準及び／又は前記第２の組のアクティブ化基準が、
−アクティブ化することができる物体の最大数、
−物体の位置、
−物体のサイズ、
−物体の動き、
−物体の形状、
−物体の色、
−物体がアクティブ状態又は非アクティブ状態を保っている、連続する前のフレームの最小数及び／又は最大数、或いは
−ユーザ選択
のうちの少なくとも１つの基準を含む請求項１２に記載の方法。
【請求項１４】
前記アクティブ化規則が、
−第２の組のアクティブ化基準を満たす全ての予備アクティブ状態の物体をアクティブ化する強制アクティブ化規則、
−アクティブ状態の物体が非アクティブ化される場合にのみ、前記第２の組のアクティブ化基準を満たす物体をアクティブ化するランク付きアクティブ化規則、
−前記第２の組のアクティブ化基準を最も良く満たす１つ又は複数の物体をアクティブ化する単純アクティブ化規則、
−関連し合う別のアクティブ状態の物体が非アクティブ化された場合に物体をアクティブ化する単純交換アクティブ化規則、
−別の物体によって遮蔽される又は遮蔽されている場合に物体をアクティブ化する遮蔽アクティブ化規則、又は
−別のアクティブ状態の物体に接触する場合に物体をアクティブ化する接触交換アクティブ化規則
からなる１組のアクティブ化規則のうちの１つである請求項１２又は１３に記載の方法。
【請求項１５】
前記シーケンスの少なくとも１つの後続のフレームに関して、所定の非アクティブ化規則の下で物体が１組の非アクティブ化基準を満たす場合に、事前にアクティブ化されている物体を非アクティブ化するステップをさらに含む請求項１２から１４までのいずれか一項に記載の方法。
【請求項１６】
非アクティブ化基準の前記組が、
−アクティブ化又は非アクティブ化することができる物体の最大数、
−物体の位置、
−物体のサイズ、
−物体の形状、
−物体の色、
−物体ランキング、
−物体がアクティブ状態を保っている、連続する前のフレームの最大数及び／又は最小数、又は
−ユーザ選択
のうちの少なくとも１つの基準を含む請求項１５に記載の方法。
【請求項１７】
前記非アクティブ化規則が、
−前記非アクティブ化基準の組を満たす全てのアクティブ状態の物体を非アクティブ化する強制非アクティブ化規則、
−非アクティブ状態の物体がアクティブ化される場合にのみ、前記非アクティブ化基準の組を満たす物体を非アクティブ化するランク付き非アクティブ化規則、
−前記非アクティブ化基準の組を最も良く満たす物体を非アクティブ化する単純非アクティブ化規則、
−関連し合う別の非アクティブ状態の物体がアクティブ化された場合に物体を非アクティブ化する単純交換非アクティブ化規則、又は
−別の非アクティブ状態であるが予備アクティブ化されている物体に接触する場合に物体を非アクティブ化する接触交換非アクティブ化規則
からなる１組の非アクティブ化規則のうちの１つである請求項１６に記載の方法。
【請求項１８】
請求項１から１７までのいずれか一項に記載の方法を実施するためのコンピュータ実行可能命令を有するコンピュータ可読データ記憶媒体。
【請求項１９】
請求項１から１７までのいずれか一項に記載の方法を実施するようにプログラムされたコンピュータ・システム。
【図１】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図５】
【図６Ａ】
【図６Ｂ】
【図６Ｃ】
【図７Ａ】
【図７Ｂ】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図５】
【図６Ａ】
【図６Ｂ】
【図６Ｃ】
【図７Ａ】
【図７Ｂ】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【公表番号】特表２０１３−５１６０１４（Ｐ２０１３−５１６０１４Ａ）
【公表日】平成２５年５月９日（２０１３．５．９）
【国際特許分類】
【出願番号】特願２０１２−５４６４４０（Ｐ２０１２−５４６４４０）
【出願日】平成２２年１２月２８日（２０１０．１２．２８）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／０７０８２１
【国際公開番号】ＷＯ２０１１／０８０２８２
【国際公開日】平成２３年７月７日（２０１１．７．７）
【出願人】（５１２１６８６３０）ソフトキネティック ソフトウェア (3)
【Ｆターム（参考）】
【公表日】平成２５年５月９日（２０１３．５．９）
【国際特許分類】
【出願日】平成２２年１２月２８日（２０１０．１２．２８）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／０７０８２１
【国際公開番号】ＷＯ２０１１／０８０２８２
【国際公開日】平成２３年７月７日（２０１１．７．７）
【出願人】（５１２１６８６３０）ソフトキネティック ソフトウェア (3)
【Ｆターム（参考）】
[ Back to top ]