Ｖｉｓｕａｌｈｕｌｌを用いて群衆の人数を決定するシステムおよび方法
Visual hull情報を用いて群集の人数を決定するシステム、装置および方法が提示される。一つの実施形態において、画像センサは群集の従来型の画像を生成する。従来型の画像に基づいてシルエット画像が次に決定される。シルエット画像コーンと動作容積との交差領域が決定される。交差領域の平面上への投影が決定される。いくつかの画像センサからの平面投影が、画像センサを交差させることによって集められ、細分化パターンが形成される。多角形で実際には空のものが識別され、除外される。個々の多角形内の人数の上下限が決定されて、ツリーデータ構造に保存される。このツリーは、時間の経過とともに画像センサから新しい情報を受信し、更新される。群集の人数はツリーのルートノードの下限に等しい。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は計算装置を用いて群集の人数を決定することに関する。より具体的には、本発明は群集の人数を決定するためにvisual hull情報を利用することに関する。
【背景技術】
【０００２】
群集の人数を決定するいくつかの技術が現存する。しかしながら、これらの技術はそれぞれに欠点を有している。一つの技術は群集の空間像を生成した後、画像中の人数を数える。例えば、戸外の場所の群集は航空機または衛星から写真を撮ることができる。この画像は群集の人数を数えるために使用される。この技術の欠点は、このような画像を得るためには群集が戸外に居なければならないことである。もう一つの欠点は、画像の分解能が低い場合があるので、人数を数えることが難しいことである。さらに別の欠点は、この技術は一つの特定の時刻（即ち、画像が生成されたとき）の群集の人数を提供することに有る。それより後の時刻において、群集の人数を決定するためには、全てのプロセスを繰り返さなければならない。この理由は、第一回の実行で取得された情報を第二回の実行で利用できないからである。
【０００３】
群集の動的特徴を考慮に入れる別の技術では、群集内の且つ／又は群集周囲の物理的なチェックポイントを選定する。その後、群集の人数はチェックポイントを通過した人数に基づいて予想される。必要なチェックポイントの数は群集の規模に依存し、多くの場合いくつかのチェックポイントが必要である。チェックポイントで人数を決定する一つの方法は、手入力（即ち、人が実際に人を数える）による。この技術は非常に労働集約的である。もう一つのより労働集約的でない方法は、人数を数える装置を使用する。例えば、カメラはチェックポイントで群集を監視することができ、コンピュータはその画像を処理することができる。しかしながら、人は互いに重なり合い、何人の人が現存するかの決定が難しくなるので、これらの二つの技術は両者ともにチェックポイントが混雑している場合は誤差を引起しやすい。
【０００４】
チェックポイント技術のもう一つの問題点は二重カウントの問題である。１人の人が複数のチェックポイントから視認され得る。これは、その人がチェックポイント間を移動すること、またはチェックポイントの視認領域が重なることにより発生する。第一の状況は、概略同時に個々のチェックポイントに何人の人が居るか決定することによって処理できる。必要な同時性の程度は、群衆中の人の移動性とチェックポイント間の距離に依存する。第二の状況は、しかしながら、依然として残ったままである。代替的な手法の一つは、特定の個人を識別（追跡）し、その後それぞれの個人が一回だけしかカウントされていないことを確認する。チェックポイントで人をカウントするために画像装置が使用される場合、個人を追跡することは難しい。まず、個人個人は非常に似通って見える。さらに、いくつかの異なる装置から情報が集められ処理されなければならない。このために、多くの帯域幅と計算が必要である。
【０００５】
群集の規模と密度にかかわらず、限られた量の帯域幅と計算により、実時間で群集の人数を決定する方法が必要である。
【発明の開示】
【０００６】
発明の要約
Visual hull情報を用いて群集の人数を決定するシステム、装置および方法が提示される。一つの実施形態において、システムは画像センサと中央コンピュータのネットワークからなる。他の実施形態では、システムはさらに１台以上のローカルコンピュータを含む。一つの実施形態において、画像センサは群集に対してどのような高さおよびどのような角度で配置されても良い。
【０００７】
一つの実施形態において、群集のvisual hullの平面投影は次のように決定される：画像センサが画像センサから見た従来の群集画像を生成する。次に、シルエット画像が従来の画像に基づいて決定される。シルエット画像コーンと動作容積の交差領域が決定される。交差領域の平面上への投影が決定される。最後に、いくつかの画像センサから平面投影が集められる。
【０００８】
一つの実施形態において、中央コンピュータはいくつかの画像センサからの平面投影を、それらを交差させ細分化パターンを形成することによって、集積する。一つの実施形態において、中央コンピュータは一つの多角形が対象物を包含すると決定する場合には厳密な一致を要求する。別の一つの実施形態において、中央コンピュータは投票スキームを使用する。一つの実施形態において、中央コンピュータは次にどの多角形が実際に空であるか決定し、それらを除外する。
【０００９】
一つの実施形態において、中央コンピュータは次に個々の多角形における人数の上下限を決定する。一つの実施形態において、これらの境界はツリーデータ構造に保存される。一つの実施形態において、このツリーは時間の経過にしたがって画像センサから新しい情報が受信され更新される。一つの実施形態において、群集の人数はツリーのルートノードの下限に等しい。
【発明を実施するための最良の形態】
【００１０】
実施形態の詳細な説明
類似の番号が類似の要素を示す添付図面の図において、発明は限定するためではなく、例示を目的として示されている。
以下の説明において、説明の目的から、多くの具体的な詳細が発明の完全な理解を目的として提示される。しかしながら、これらの具体的な詳細が無くても、本発明が実施可能であることは、当業者にとって明らかである。他の場合において、本発明を不明確にすることが無いように、構造および装置がブロック図の形で示されている。
【００１１】
明細書中の「一つの実施形態」又は「実施形態」の使用は、その実施形態に関連して説明された特定の特徴、構造又は特性が本発明の少なくとも一つの実施形態に含まれることを意図している。明細書中のいくつかの個所で出現する「一つの実施形態において」は必ずしも全てが同じ実施形態を言及するものではない。
【００１２】
以下に述べられる詳細な記述のある部分は、コンピュータメモリ内のデータビット上の動作についてアルゴリズムの形および記号表現の形で示されている。これらのアルゴリズムの説明および表現は、データ処理技術に携わる当業者が自分の成果の中身を最も効果的に他の当業者に対して伝達するために使用する手段である。ここでは、また一般にも、一つのアルゴリズムは所望の結果に導く自己矛盾の無い一連のステップと考えられる。ステップは物理量の物理的な操作を要求するものである。必ずというわけではないが、通常、これらの量は、保存、移動、結合、比較およびその他の操作が可能な電気または磁気信号の形を取る。主に通常の使用にかかわる理由として、これらの信号を、ビット、数値、要素、記号、文字、項、番号等と呼ぶと便利な場合があることが分かっている。
【００１３】
しかしながら、これらおよび類似の項の全てが、適切な物理量と関連付けられ、これらの量に適用される便宜的な表示に過ぎないことを覚えておくべきである。具体的に宣言されない限り、以下の議論で明らかなように、説明を通して、「処理する」、「演算する」、「計算する」、「決定する」「表示する」等を使用した議論は、コンピュータシステムのレジスタおよびメモリ内に物理（電子）量として表されているデータを、コンピュータシステムのメモリ、レジスタ、あるいは他のそのような情報保存、伝送またはディスプレイ装置内で、同じように物理量として表わされる他のデータに、操作して変換するコンピュータシステムまたは類似の電子計算装置の実行および処理、に言及している。
【００１４】
本発明はここで動作を実行する装置にも関係している。この装置は要求された目的に合わせて構成されている専用機か、あるいはコンピュータ内に保存されたコンピュータプログラムによって、選択的に作動または再設定される汎用のコンピュータからなる。このようなコンピュータプログラムはコンピュータが読み出し可能な次のようなストレージ媒体、以下に限定されないが例えば、フロッピーディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスクを含む任意のタイプのディスク、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気または光カード、または電子命令を保存可能な全てのタイプの媒体に保存され、以上の媒体のそれぞれはコンピュータシステムバスに接続される。
【００１５】
ここで示されるアルゴリズムとディスプレイは特定のコンピュータまたは他の装置に固有に関連するものではない。多種の汎用目的のシステムが、ここでの教示事項に従ったプログラムと共に使用され、あるいは要求される方法のステップを実行するためにより特殊化された装置が構築される。これらのさまざまなシステムに要求される構成は以下の説明によって明らかになる。さらに、本発明はいずれの特定のプログラミング言語も参照することなく説明される。ここで説明される本発明の教示事項を実施するためにさまざまなプログラミング言語が使用可能であると認識される。
【００１６】
１．群衆の人数を決定するためのシステムの構成
以下の説明は、群衆の人数を決定するためのシステムの構成を扱うものであるが、該システムはある特定のエリアにある対象物の数を決定するために使用することも可能である。対象物は同一のタイプからなるもの（例えば、人々）、または異なるタイプからなるもの（例えば人々と動物）のいずれの場合もありうる。
【００１７】
図１は本発明の一つの実施形態による、群集の人数を決定するためのシステムの俯瞰図（ブロック図の形式で）を示す。群集の存在が想定される長方形の領域１１０をいくつかの画像センサ１００が取り囲む。領域１１０は物理的な境界によって境界が定められても定められなくても良い。実施形態では８台の画像センサが示されているが、１台より多ければいかなる数の画像センサの使用も可能である。一般に、使用される画像センサ１００の数が増えれば、システムが取り扱い可能な領域１１０のサイズも増加する。
【００１８】
一つの実施形態においては、図１に示されたシステムは領域１１０に存在する人の数の上下限を演算する。他の実施形態においては、下限が存在する人の数に等しい。一般に、使用センサ１００の数が増加するにつれて、システムが正しく数えることができる人数が増加する。さらに他の実施形態においては、システムは常に領域１００に存在する人数の上下限を計算する。
【００１９】
一つの実施形態においては、画像センサ１００はネットワーク１９０を使用する中央コンピュータ１２０に接続されている。ネットワーク１９０との双方向の通信リンクは有線または無線（例えば地上波または衛星を利用したトランシーバ）のいずれの形も可能である。一つの実施形態においては、ネットワーク１９０は個人のネットワークである。他の一つの実施形態においては、ネットワーク１９０は、ＩＰに基づいた構内通信網（ＬＡＮ）または広域通信網（ＷＡＮ）である。
【００２０】
データは画像センサ１００から中央コンピュータ１２０へ送られる。中央コンピュータ１２０はこのデータを用いて群集のvisual hullの平面投影を決定する。対象物のvisual hullは、対象物がその中に存在することができて、対象物の外部の全てのビューに対して、対象物自身と同一のシルエットを生み出す最大の体積である。換言すれば、visual hullは対象物のいくつかのシルエットコーンの交差領域である。シルエットコーンは異なる場所から見たときの対象物の異なるビューを示す。Visual hullを生成する技術には、ボリューム・インターセクション（volume intersection） およびシェイプ・フロム・シルエット（shape-from-silhouette）が含まれる。対象物のvisual hullはその定義から対象物を完全に包含することが保証されている。Visual hullとその生成方法については当業者に知られ、詳細については「ザ・ビジュアル・ハル・コンセプト・フォー・シルエット−ベイスト・イメージ・アンダースタンディング」Ａ．ロオレンティニ、ＩＥＥＥトランザクションズ・オン・パターン・アナリシス・アンド・マシーン・インテリジェンス、１６：２、１９９４年２月（”The Visual Hull Concept for Silhouette-Based Image Understanding” by A. Laurentini, IEEE Transactions on Pattern Analysis and Machine Intelligence, 16:2, February 1994.）に記載されている。Visual hullの平面投影はvisual hullの平面上への投影である。一つの実施形態においては、中央コンピュータ１２０が長方形領域１１０の床上への群集のvisual hullの投影を決定する。この実施形態においては、群集のvisual hullの平面投影は、群集の上部位置から見たときの群衆のシルエットに類似している。
【００２１】
一旦群集のvisual hullの平面投影が決定されると、中央コンピュータ１２０が群集の人数を決定する。群集の人数を決定するために中央コンピュータ１２０が使用する方法を、図８を参照して以下に説明する。
【００２２】
上述のように、中央コンピュータ１２０は画像センサ１００からのデータを用いて群衆のvisual hullの平面投影を決定する。一つの実施形態においては、画像センサ１００は中央コンピュータ１２０から問い合わせを受信した後、データを中央コンピュータ１２０へ送る。他の一つの実施形態においては、画像センサ１００は問い合わせを受信することなく中央コンピュータ１２０へデータを送る。さらに他の一つの実施形態においては、画像センサ１００は定期的に中央コンピュータ１２０へデータを送る。二つの画像センサ１００が定期的に中央コンピュータにデータを送信する場合、それらの送信は同期してもしなくても良い。
【００２３】
ａ．群集のvisual hullの平面投影を決定するシステムの使用
一つの実施形態において、群集のvisual hullの投影は、群集のvisual hullを決定し（異なるセンサからの群集のビューに基づく）、その後visual hullを平面上に投影することによって決定される。少ない演算リソースが要求される他の一つの実施形態では、群集のvisual hullの平面投影は、それぞれのシルエットコーンを平面上に投影し、その結果得られる２次元マップを集積することによって決められる。この実施形態はvisual hullの平面投影の近似を与えるに過ぎないが、群集の人数を決定するには充分な近似である。さらに他の一つの実施形態においては、前記の実施形態によって必要とされる演算リソース量は、群集のvisual hull を動作容積（working volume）で交差させることによって（前者の実施形態）、または個々のシルエットコーンを動作容積で交差させることによって（後者の実施形態）さらに減少される。
【００２４】
図１１は、本発明の一つの実施形態による、群集のvisual hullの平面投影を決定するために、群集の従来の画像を利用する方法を示す。最初のステップで、複数の従来の群集の画像が生成される（１１００）。複数のシルエット画像が従来の画像に基づいて決定される（１１１０）。個々のシルエット画像コーンと動作容積の交差領域が決定される（１１２０）。個々の交差領域の平面上への投影が決定される（１１３０）。最後に、群集のvisual hullの平面投影を形成するためにそれらの投影が集められる（１１４０）。
【００２５】
ステップ１１００、１１１０、１１２０、１１３０、および１１４０は、例えば、画像センサ１００、中央コンピュータ１２０、あるいは追加のローカルコンピュータ（図示せず）によって実行される。一つの実施形態においては、画像センサ１００の間の通信構成は比較的集中化されていない。一つの実施形態においては、１台以上の近傍のセンサ１００からのデータを処理するために１台以上のローカルコンピュータが使用される。その後、このローカルコンピュータは得られたデータをさらに処理するために中央コンピュータ１２０へ送る。
【００２６】
一つの実施形態において、例えば、画像センサ１００は、このセンサ１００の視点から見た群集の従来の画像を生成する（１１００）。この実施形態においては、画像センサ１００は、従来の画像を生成できるカメラのような、どのようなタイプの装置をも含む。
【００２７】
この従来のイメージに基づいてシルエット画像が決定される（１１１０）。一つの実施形態においては、シルエット画像には２色のみが使用される：１色は前景（群衆中の人々）、もう１色は背景（人が居ない場所）。別の一つの実施形態では、シルエット画像は白黒のビットマップである。
【００２８】
シルエット画像を決定するために（１１１０）、いくつかの方法のいずれもが使用できる。一つの実施形態においては、背景減算を用いてシルエット画像が決定される（１１１０）。シルエット画像を生成するために従来の画像イメージから背景が減算される。一つの実施形態においては、人が全く存在しない場合は、画像センサ１００の出力が、画像センサ１００から見た時の背景画像に対して較正される。一つの実施形態においては、コンピュータが背景減算を実行する。他の一つの実施形態では、ＣＭＯＳセンサの集合体が背景減算を実行する。例えば、内蔵のＣＭＯＳロジックが、同一または前の画像内の近傍のピクセルの値に基づいて、従来画像のピクセルの値を比較する。背景減算は当業者に知られた技術であり、「ア・ローバスト・バックグラウンド・サブトラクション・アンド・シャドウ・ディテクション」Ｔ．ホープラサート他、プロシーディングズ・オブ・エイジャン・コンファランス・オン・コンピュータ・ビジョン、２０００年１月（”A Robust Background Subtraction and Shadow Detection” by T. Horprasert et al., Proceedings of Asian Conference on Computer Vision, January 2000）に詳細が記載されている。
【００２９】
他の実施形態では、動作検出を用いてシルエット画像が決定される（１１１０）。この実施形態では、動的対象物は従来の画像として検出され、シルエットとして取り出される。静的対象物は背景の一部と見なされ、シルエット画像には含まれない。動的検出は、例えば、コンピュータまたはＣＭＯＳセンサの集合体を用いて実行することができる。内蔵されたＣＭＯＳロジックが、画像内のピクセルの値を、同一のまたは前の画像内の近傍のピクセルの値と比較して動的検出を実行する。動作検出は当業者に知られている。
【００３０】
さらに別の一つの実施形態においては、シルエット画像は画像内の対象物の距離に関する情報を用いて決定される（１１１０）。この実施形態においては、前景の対象物はセンサ１００の近接した位置にあり、一方、背景対象物はセンサ１００から離れている。シルエット画像は、対象物の距離を閾値と比較し、前景の対象物を背景の対象物から分離して生成される。３次元の深さセンサが当業者に知られていて、例えば、カネスタ社および３ＤＶ・システムズ社（Canesta, Inc. and 3DV Systems, Ltd.）から入手可能である。
【００３１】
ステップ１１１０は、例えば、画像センサ１００によって実行される。この実施形態においては、センサ１００は上で説明した方法のいずれかを用いて従来のイメージからシルエット画像を決定できる（１１１０）システムからなる。例えば、該システムはコンピュータのこともある。他の例として、該システムはＣＭＯＳセンサの集合体のこともある。代替案として、ステップ１１１０は、例えば、中央コンピュータ１２０またはローカルコンピュータによっても実行可能である。この実施形態においては、中央コンピュータ１２０（またはローカルコンピュータ）がセンサ１００から従来のイメージを受信する。中央コンピュータ１２０（またはローカルコンピュータ）は次に、上で説明した方法のいずれかを用いて従来のイメージからシルエット画像を決定する（１１１０）。
【００３２】
シルエット画像コーンと動作容積の交差領域が次に決定される（１１２０）。動作容積は人々の存在を検出する空間容積である。シルエットコーンと動作容積の交差領域は、特定のセンサ１００から見た対象物のビューに基づいて、対象物がどこに存在する可能性があるかを表す３次元形状である。一つの実施形態においては、動作容積は床（長方形領域１１０）と平行に位置する四角柱である。動作容積の高さは可変である。一般に、動作容積の高さを限定すれば、群集のvisual hullの平面投影を計算するために必要なリソース量は減少する。一つの実施形態においては、動作容積の高さは最も背の高い人の身長以上で、動作容積は床面を起点とする。他の一つの実施形態においては、動作容積の高さは３フィートで、動作容積は腰の位置（例えば、床から３フィート）を重点的にカバーする。３次元形状の交差領域を決定する方法は当業者に知られており、ハンドブック・オブ・ディスクリート・アンド・コンピュテーショナル・ジオメトリ、グッドマンおよびオールーケ編、ＣＲＣ・プレス、１９９７、５９９−６３０頁（Handbook of Discrete and Computational Geometry, Goodman and O’Rourke, Eds., CRS Press, 1977, pp. 599-630）に詳細が記載されている。
【００３３】
ステップ１１２０は、例えば、画像センサ１００によって実行される。この実施形態においては、センサ１００は３次元対象物（シルエット画像コーンと動作容積）の交差領域を決定できる（１１２０）システムからなる。例えば、該システムはコンピュータのこともある。代替案として、ステップ１１２０は、例えば、中央コンピュータ１２０またはローカルコンピュータによって実行することも可能である。この実施形態においては、中央コンピュータ１２０（またはローカルコンピュータ）がセンサ１００からシルエット画像を受信する。中央コンピュータ１２０（またはローカルコンピュータ）が次にシルエット画像コーンと動作容積との交差領域を決定する（１１２０）。
【００３４】
個々の交差領域の平面への投影が決定される（１１３０）。上述のように、交差領域は対象物がどこに存在する可能性のあるかを表す３次元形状である。この形状の平面投影は、どこに対象物が存在するかを２次元マップで示す。一つの実施形態においては、この平面は床（長方形領域１１０）である。この実施形態においては、交差領域の平面投影は対象物が存在する可能性のある床スペースの領域に相似である。３次元形状の平面投影を決定する方法は当業者に知られている。
【００３５】
ステップ１１３０は、例えば、画像センサ１００によって実行される。この実施形態においては、センサ１００は３次元対象物（シルエット画像コーンと動作容積の交差領域）の平面上への投影を決定できる（１１３０）システムからなる。例えば、該システムはコンピュータのこともある。代替案として、ステップ１１２０は、例えば、中央コンピュータ１２０またはローカルコンピュータによって実行することも可能である。この実施形態においては、中央コンピュータ１２０（またはローカルコンピュータ）がセンサ１００から３次元対象物の表示（シルエット画像コーンと動作容積の交差領域）を受信する。中央コンピュータ１２０（またはローカルコンピュータ）が次に３次元対象物の平面への投影を決定する（１１３０）。
【００３６】
最後に、平面投影は、群集のvisual hullの平面投影を形成するために集められる。このステップについて以下に図８を参照して説明する。
【００３７】
ｂ．システム内へのセンサの配置
画像センサ１００は対象物に対して任意の高さおよび角度で据付が可能である。しかしながら、画像センサ１００の位置および向きによって画像センサ１００からの対象物の見え方が影響される。画像センサの対象物の見え方は、３次元空間のコーンを掃引するシルエットであることを思い出そう。このように、対象物の正確な位置は、１台だけの画像センサ１００からの対象物のシルエットに基づいて決定することはできない。特に、対象物と画像センサ１００との距離は決定できない。
【００３８】
図２は、画像センサ、人および投影シルエットコーンの側面図である。図２Ａにおいて、画像センサ１００は人２００の真上（例えば天井）に位置し、床を向いている。図２Ｂは図２Ａの人および投影シルエットコーンの上面図である。図２Ｂに示された投影シルエットコーン２１０の上面図も、画像センサ１００から見た時の人２００のシルエット画像である。さらに、このシルエットはこの人のvisual hullの平面投影である。
【００３９】
画像センサ１００からのシルエット画像を用いて人２００のvisual hullの平面投影を決定することが最終目的の場合は、シルエット画像が既に所要の平面投影に等しいことが望ましい。このように、画像センサ１００の好ましい配置は、人２００の真上になろう。この配置では、シルエット画像は、人２００のvisual hullの平面投影を決定するために、これ以上の処理を必要としない。しかしながら、上述のように、群集の上に画像センサ１００を設置することは、例えば屋外の集まりにおいて、実際的でない。この配置では、人２００と画像センサ１００との距離が決定されないことに注意して欲しい。しかしながら、人２００と画像センサ１００との距離は人のvisual hullの平面投影とは無関係であるので、距離が決定されないことは問題にならない。
【００４０】
図３Ａは画像センサ、人および投影シルエットコーンの側面図である。図３Ａでは画像センサ１００が人２００の横に斜めになるように配置されている。図３Ｂは図３Ａの画像センサ、人および投影シルエットコーンの上面図である。図３Ｂに示された人２００の上面からの見え方は、画像センサ１００から見たときのシルエットコーンの投影と同じでないことに注意を喚起する。また、画像センサ１００から見た人２００のシルエット画像は、人のvisual hullの平面投影ではない。この配置では、人２００と画像センサ１００との距離は決定できない。しかしながら、図２Ａおよび２Ｂの配置とは異なり、人２００と画像センサ１００との距離は人のvisual hullの平面投影に関係するので、距離を決定できないことが問題になる。
【００４１】
図４Ａは画像センサ、人および投影シルエットコーンの側面図である。図４Ａにおいて、画像センサ１００は床に平行に配置され、人２００はセンサ視野範囲内に在る。図４Ｂは、図４Ａの画像センサ、人および投影シルエットコーンの上面図である。図４Ｂに示された人２００の上面からの見え方は、画像センサ１００から見たときのシルエットコーンの投影と同じでないことに注意を喚起する。また、画像センサ１００から見た人２００のシルエット画像は、人のvisual hullの平面投影ではない。この配置では、人２００と画像センサ１００との距離は決定できない。しかしながら、図２Ａおよび２Ｂの配置とは異なり、人２００と画像センサ１００との距離は人のvisual hullの平面投影に関係するので、距離を決定できないことが問題になる。
【００４２】
上述のように、画像センサ１００は対象物に対して任意の高さおよび角度で配置することが可能である。しかしながら、群集のvisual hullの平面投影を計算するためには、動作容積内のポイントは少なくとも２台のセンサ１００から可視状態になければならない。多数のセンサ１００からビューを取得すれば、システムのオクルージョンの処理の助けになる。説明を明確にするために、本発明は今後、画像センサ１００が、図４Ａおよび４Ｂと同様に、床に平行に配置されている実施形態によって説明する。
【００４３】
一般に、画像センサ１００は、シルエットが不完全であっても、センサの視野内の人が唯一のシルエットを作るように配置されるべきである。例えば、画像センサ１００が地上から１０フィート上に配置されるとした場合、５フィートの身長の人は、センサ１００の近くに位置しようが離れていようが、センサの視野から外れる可能性がある。図５は画像センサ、画像センサの視野および異なる二箇所に位置している人の側面図である。図５では、画像センサ１００は床と平行に配置され、人２００は第１の位置２００Aと第２の位置２００Bのいずれの位置においても、視野５００の外部にある。当然のことながら、人２００は第２の画像センサ１００（図示せず）の視野内に入ることはあり得る。一般に、領域１１０は画像センサ１００によって充分にカバーされるべきであるが、全ての画像センサが領域１１０内の全ての場所をカバーする必要は無い。同様に、画像センサ１００は一人の人を表している二つの対象物を見るべきでない。画像センサが地上に配置された場合、視野２００内を歩行する人２００は二つの対象物（左足と右足）として現れるかもしれない。従って、一つの実施形態においては、画像センサ１００は地上から約３フィート離して設置される。この高さに置かれると画像センサ１００は人の胴を見ることができる。
【００４４】
２．群集の人数を決定するための装置の構成
図６は本発明の一つの実施形態による群衆のvisual hullの平面投影に基づいた群集の人数を決定するための装置のブロック図である。装置６００は好ましくはプロセッサ６１０、主メモリ６２０、データ保存装置６３０および入出力制御器６８０からなり、これらの全てはシステムバス６４０に通信可能な状態で接続されている。装置６００に、例えば、汎用のコンピュータを使用することも可能である。
【００４５】
プロセッサ６１０はデータ信号を処理し、複号命令セットコンピュータ（ＣＩＳＣ）、縮小命令セットコンピュータ（ＲＩＳＣ）または命令セットの組み合わせを実施する構成を含むさまざまな計算構成からなる。図６では一つのプロセッサだけが示されているが、多数のプロセッサが含まれる場合もある。
【００４６】
主メモリ６２０はプロセッサ６１０によって実行される命令および／またはデータを保存する。命令および／またはデータは、ここで説明される技術のいずれかおよび／または全てを実行するためのコードからなる。主メモリ６２０はダイナミックランダムアクセスメモリ（ＤＲＡＭ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）またはその他の周知のメモリデバイスであることが望ましい。
【００４７】
データ保存装置６３０はプロセッサ６１０のためのデータおよび命令を保存し、ハードディスクドライブ、フロッピディスクドライブ、ＣＤ−ＲＯＭデバイス、ＤＶＤ−ＲＯＭデバイス、ＤＶＤ−ＲＡＭデバイス、ＤＶＤ−ＲＷデバイス、フラッシュメモリデバイスまたはその他の既知の大容量ストレージデバイスを含む一つ以上のデバイスからなる。
【００４８】
ネットワーク制御器６８０は装置６００が通信できるように装置６００を他の機器にリンクさせる。
【００４９】
システムバス６４０は装置６００の至る所で情報およびデータを通信するための共有バスである。システムバス６４０は、工業標準アーキテクチャ（ＩＳＡ）バス、周辺機器相互接続（ＰＣＩ）バス、ユニバーサルシリアルバス（ＵＳＢ）またはその他の類似の機能を実現できる周知のバスを含むバスの一つ以上のバスである。
【００５０】
システムバス６４０経由で装置６００に接続される可能性のある追加のコンポーネントとしては、ディスプレイ装置６５０、キーボード６６０およびカーソル制御装置６７０がある。ディスプレイ装置６５０は電子イメージおよびデータをローカルユーザまたは保守担当者に表示できる装置であればどのようなものでも構わない。ディスプレイ装置６５０は陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）またはその他の類似の機能を有するディスプレイ装置、スクリーンまたはモニタである。キーボード６６０は情報および命令選択をプロセッサ６１０へ通信するために装置６００に接続されたアルファベットと数字を組み合わせた入力装置である。カーソル制御装置６７０は命令選択および位置データをプロセッサ６１０へ通信するために備えられたユーザ入力装置である。カーソル制御装置６７０は、マウス、トラックボール、スタイラス、ペン、カーソル方向キーあるいはカーソルに動作を与える他の機構からなる。
【００５１】
当業者にとって、本発明の範囲を逸脱することなく、装置６００が図６に示された例より多くのまたは少ないコンポーネントから構成されることは自明である。例えば、装置６００は追加のメモリ、例えば、プライマリまたはセカンダリレベルのキャッシュ、あるいは一つ以上の特定用途向け集積回路（ＡＳＩＣ）を含む。上述のように、装置６００はＡＳＩＣだけから構成することも可能である。さらに、装置６００に連結される可能性のあるコンポーネントとしては、例えば、画像走査装置、デジタルスチルまたはビデオカメラ、あるいは装置６００へ／又は装置６００から電子データを取得および／またはダウンロードするために装備されてもされなくても良い他の装置が挙げられる。
【００５２】
図７は図６に示されたメモリユニットの内容を示すより詳細なブロック図である。一般に、メモリユニット６２０は、群集のvisual hullの平面投影に基づいて群集の人数を決定するためのいくつかのコードモジュールからなる。一つの実施形態において、メモリユニット６２０は、シルエットコーンと動作容積との交差領域の平面投影に基づいて群集のvisual hullの平面投影を近似する。特に、メモリユニット６２０のコードモジュールは、メインプログラムモジュール７００、集積モジュール７１０、除去モジュール７２０、ツリー決定モジュール７３０、ツリー更新モジュール７４０および合計モジュール７５０からなる。
【００５３】
全てのコードモジュール７１０、７２０、７３０、７４０、７５０はメインプログラムモジュール７００に連結されて通信が可能である。メインプログラムモジュール７００が中央から装置６００の動作および処理フローを制御し、個々のコードモジュール７１０、７２０、７３０、７４０、７５０からデータを受信するとともに、これらのモジュールへ命令とデータを送信する。メインプログラムモジュール７００の動作の詳細については図８を参照して以下に説明する。
【００５４】
集積モジュール７１０は、シルエットコーンと動作容積との交差領域の平面投影を含む複数の二次元マップを集積する。個々の二次元マップは１台のセンサ１００からのビューに基づいた、人が存在する可能性のある領域を包含する。この領域はシルエットコーンと動作容積との交差領域の平面投影である。集積によってマップが交差し、それはマップを互いに重ね合わせ、どこでシルエットコーンが重なり合うかを見ることに類似している。
【００５５】
図９は２台の画像センサ、一つの対象物およびその対象物のシルエットコーンの上面図である。図示の実施形態では、シルエットコーンは楔形をしている。多数のセンサ１００が領域１１０を囲む場合、楔形のシルエットコーン９１０Ａと９１０Ｂは交差し（重なり）細分化パターンを形成して、領域１１０をいくつかの多角形９００Ａ，９００Ｂ，９００Ｃ，９００Ｄおよび９００Ｅに分割する。図示の実施形態では、シルエットコーン９１０Ａは多角形９００Ｂ，９００Ｃおよび９００Ｄからなる一方、シルエットコーン９１０Ｂは多角形９００Ａ，９００Ｃおよび９００Ｅからなる。このようにしてセンサ１００Ａは対象物が多角形９００Ｂ，９００Ｃおよび９００Ｄ内に位置すると決定でき、一方、センサ１００Ｂは対象物が多角形９００Ａ，９００Ｃおよび９００Ｅ内に位置すると決定できる。これとともに、センサ１００Ａおよび１００Ｂからの情報は集積されて、対象物が多角形９００Ｃ内に位置していると決定することが可能である。
【００５６】
一つの実施形態において、上述の細分化は厳密に決定される。この実施形態ではシルエットコーンの境界は線で表される。これらの線は交差すると多角形の境界線を形成する。他の一つの実施形態においては、細分化に近似が用いられる。この実施形態では、二次元マップは、シルエットコーンがピクセルのパッチになるように画素化される。画素化はまたラスタ処理またはスキャン変換と呼ばれ、当業者に知られている。その詳細はグラフィクス・ジェムズ、Ａ．グラスナー編、モーガン・カオフマン、１９９８年、７５−９７頁（Graphics Gems, A. Glassner, Ed., Morgan Kaufmann, 1988, pp. 75-97）に記載されている。
【００５７】
一般に、厳密な細分化はアルゴリズムの観点から実施するのは困難で、必要な演算リソースは少なく、誤差の扱いにおいては能力が低い。対照的に、画素化は実施し易いが、演算リソースをより多く必要とし、誤差を扱う能力はより高い。一つの実施形態においては、特別のグラフィックハードウェアがマップをピクセル化し交差させるために用いられる。特別のグラフィックハードウェアがピクセル化に用いられる場合は、必要な演算リソース量は大幅に減少する。
【００５８】
集積モジュール７１０はマップを交差させることによっていくつかのセンサからの情報を集積する。結果として得られる交差領域は群集のvisual hullの近似である。一つの実施形態において、集積モジュール７１０は対象物が存在するかもしれないと決定するときに厳密な一致を必要とする。この実施形態では、ある特定の多角形領域をカバーする全てのマップ（センサビュー）は対象物がその領域にあると一致しなければならない。１台のセンサでもその領域に対象物が無いと出力した場合には、集積モジュール７１０は対象物が存在しないと決定する。他の実施形態においては、集積モジュール７１０は投票スキームを用いる。この実施形態においては、対象物が存在する可能性があるとするマップの数と対象物が存在しないとするマップの数を比較する。「対象物有り」のマップの数またはパーセントが閾値より高い場合、集積モジュール７１０は対象物がその領域に存在すると決定する。
【００５９】
一つの実施形態においては、ローカルコンピュータが二次元マップの全数の一部である部分集合を集積するために使用される。この実施形態では、センサ１００からのビューの集積を分散して実施することが可能になる。ローカルコンピュータで集めた結果が中央コンピュータ１２０で集められる。
【００６０】
図１０Ａは対象物無しの２台の画像センサおよび投影シルエットコーンの上面図である。多角形領域１０００Ａ，１０００Ｂ，１０００Ｃおよび１０００Ｄは対象物が存在する可能性のある場所を示している。換言すれば、多角形領域１０００Ａ，１０００Ｂ，１０００Ｃおよび１０００Ｄは投影された対象物のvisual hullである。一人より多い対象物が多角形領域１０００Ａ，１０００Ｂ，１０００Ｃおよび１０００Ｄに存在する可能性のあることを喚起されたい。対象物のいくつかの配置が一つの所与のvisual hullに一致することができるので、投影されたvisual hullはあいまい性を持つ。図１０Ｂは図１０Ａの投影されたシルエットコーンと第一のコンフィギュレーションにおける多数の対象物の上面図である。図１０Ｃは図１０Ａの投影されたシルエットコーンと第二のコンフィギュレーションにおける多数の対象物の上面図である。図１０Ｄは図１０Ａの投影されたシルエットコーンと第三のコンフィギュレーションにおける多数の対象物の上面図である。図１０Ｅは図１０Ａの投影されたシルエットコーンと第四のコンフィギュレーションにおける多数の対象物の上面図である。図１０Ｂ，１０Ｃ，１０Ｄおよび１０Ｅのいずれの対象物のコンフィギュレーションも図１０Ａの投影されたvisual hullと一致している。
【００６１】
除去モジュール７２０はどの投影visual hullの多角形領域が空かを決定し、それらを投影から除外する。これらの多角形領域は幻影（phantoms）として知られている。幻影の一つのタイプはサイズに基づいて識別される。例えば、最低の対象物サイズより小さい多角形は除外される。他の幻影のタイプは時間的コヒーレンスに基づいて識別される。例えば、対象物が無いのに現出する多角形(次の多角形にはなり得ないもの)は除外される。このタイプの幻影は３台以上のセンサ１００によるものである。図１２Ａは３台のセンサ、それらの投影シルエットコーンおよび多数の対象物の上面図である。図１２Ｂは３台のセンサ、それらの投影シルエットコーン、多数の対象物および幻影多角形の上面図である。二つの対象物１２００Ａと１２００Ｂが二つの連続の時間ステップ（最初に図１２Ａ次に図１２Ｂ）で観測され、幻影１２１０が図１２Ｂに現出している。一つの実施形態においては、多角形の時間コヒーレンスは、その多角形が前の時間ビュー（例えば図１２Ａ）において多角形を交差したかテストすることによってチェックされる。このテストでは対象物が一つの時間ステップでそのvisual hullによって作られた領域を去ることは無いと仮定している。一つの実施形態においては、この最大スピードの仮定は、交差領域を計算する前に、前の時間ステップにおける多角形を拡張することによって調整される。
【００６２】
センサイメージがオクルージョン（ある人が他の人のセンサ１００による視認を妨害）を含む場合、群集の正しい人数を決定することはできない。その代わりに、一つの実施形態では、群集の人数は個々の多角形内に存在する人数を限定することによって決定される。ツリー決定モジュール７３０は個々の多角形内の人数の上下限を決定する。
【００６３】
上限制約（ＵＢＣ）−一つの実施形態において、最低の対象物サイズで割った多角形の面積が多角形の上限である。対象物がクラスタ化し一体となって単一の標的のように動くとして、考えられる最悪シナリオを仮定しているので、この境界は厳密性を非常に欠いている。この境界には、対象物の幾何学的形状によらず（変わった形状の入れ物を液体が満たすやり方に類似）、対象物が多角形の全領域を満たすとの仮定が用いられている。
【００６４】
下限制約（ＬＢＣ）−一つだけの多角形と交差する画像センサ１００からの光線があれば、その多角形は少なくとも一つの対象物を含む。これは画像センサ１００からの光線は、対応する視線が対象物によってブロックされた場合にだけ、多角形に交差するからである。一つだけの多角形が光線と交差する場合、対象物は多角形内に含まれるはずである。この制約は、対象物を直接数えるのでＵＢＣとは異なる。（真の対象物は光線に沿って観測されカウントされる。）対照的に、ＵＢＣは多角形を満たす対象物の最大数を仮定する。
【００６５】
一つの実施形態において、決定モジュール７３０はデータ構造に上下限を保存する。特定のＬＢＣの値は多角形が少なくとも一つの対象物を含むかを示すが、時系列のＬＢＣの振る舞いによって追加情報が伝達される。他の一つの実施形態では、データ構造はツリー（τ）になっている。ツリーに沿って下限を伝播することにより、領域１１０内の対象物の数がさらに制約される（例えば、下限が狭くなる）。
【００６６】
一つの実施形態においては、ツリーの個々の葉は、時刻ｔで、新たに観測された多角形とそれに関連する対象物の境界を保存する。ツリーのノードはその子孫の全ての多角形からなる暗黙の和集合を表している。このノードはこの和集合内の対象物の数に対する境界を含む。これにより、ツリー中の対象物の境界上で四つの特性が導入される：
【００６７】
【００６８】
【００６９】
【００７０】
【００７１】
【００７２】
【００７３】
【００７４】
【００７５】
境界の更新−方程式（１）−（４）が全てのノードに確実に成り立つようにするために、対象物の境界はツリー全体で更新される。これには次の二つの操作が含まれる：まず、葉からの新しい情報はτのルーツまで伝播される。その後、ルーツに対する更新された境界は葉まで伝播されて戻る。
【００７６】
合計モジュール７５０はツリーτのルートノードへ下限を返す。この数字が群集の人数である。
【００７７】
３．群集の人数を決定する方法
図８は本発明の一つの実施形態による群衆の人数を決定する方法を示す。方法が開始すると、ステップ１１３０に示すように、シルエットコーンと動作容積の交差領域の平面投影が既に決定されている。
【００７８】
最初のステップで、メインプログラムモジュール７００が開始する（８００）。メインプログラムモジュール７００は集積モジュール７１０に、シルエットコーンと動作容積の交差領域の平面投影である複数の２次元マップの集積を命令する（８１０）。そして、メインプログラムモジュール７００は除去モジュール７２０に、投影されたvisual hullのどの多角形が実際に空か決定し、それらを投影から除外することによって、多角形を除去するように命令する（８２０）。
【００７９】
メインプログラムモジュール７００は決定モジュール７３０に、上下限を保存することによって、ツリーデータ構造を決定するように命令する（８３０）。メインプログラムモジュール７００は、その後、合計モジュール７５０を用いて群集の人数を決定する（８４０）。
【００８０】
要望があれば、シルエットコーンと動作容積の交差領域の平面投影は、時間的に後に再決定される。方法はステップ８１０へ戻り（８６０）、ステップ８１０および８２０を繰り返す。その後、メインプログラムモジュール７００はツリー更新モジュール７４０にツリーデータ構造を更新するように命令する（８３０）。タイムステップがそれ以上ない場合は、メインプログラムモジュール７００は終了する（８５０）。
【００８１】
本発明はその実施形態を参照して相当な詳細にわたって説明されたが、当業者の理解が得られるように、他の実施形態も可能である。例えば、他の一つの実施形態が、「カウンティング・ピープル・イン・クラウズ・ウイズ・ア・リアル−タイム・ネットワーク・オブ・シンプル・イメージ・センサーズ」、Ｄ．ヤング、Ｈ．ゴンザレツ−バノス、およびＬ．ギバス共著、プロシーディングズ・オブ・ザ・ナインス・ＩＥＥＥ・インターナショナル・コンファランス・オン・コンピュータ・ビジョン（ＩＣＣＶ）、ニース、フランス、１０月１３−１６日、２００３年、１２２−１２９頁およびＣＤ−ＲＯＭ（Counting People in Crowds with a Real-Time Network of Simple Image Sensors” by D. Yang, H. Gonzalez-Banos, and L. Guibas, Proceedings of the Ninth IEEE International Conference on Computer Vision (ICCV), Nice, France, October 13-16, 2003, pp. 122-129 and CD-ROM）、に掲載されている。
【図面の簡単な説明】
【００８２】
【図１】図１は本発明の一つの実施形態による、群集の人数を決定するためのシステムの俯瞰図（ブロック図の形式で）を示す。
【図２Ａ】図２Ａは、画像センサ、人および投影シルエットコーンの側面図を示す。
【図２Ｂ】図２Ｂは、図２Ａの人および投影シルエットコーンの上面図を示す。
【図３Ａ】図３Ａは画像センサ、人および投影シルエットコーンの側面図を示す。
【図３Ｂ】図３Ｂは図３Ａの画像センサ、人および投影シルエットコーンの上面図を示す。
【図４Ａ】図４Ａは画像センサ、人および投影シルエットコーンの側面図を示す。
【図４Ｂ】図４Ｂは、図４Ａの画像センサ、人および投影シルエットコーンの上面図を示す。
【図５】図５は画像センサ、画像センサの視野および異なる二箇所に位置している人の側面図を示す。
【図６】図６は本発明の一つの実施形態による、群衆のvisual hullの平面投影に基づいた群集の人数を決定するための装置のブロック図を示す。
【図７】図７は図６に示されたメモリユニットの内容を示すより詳細なブロック図である。
【図８】図８は本発明の一つの実施形態による群衆の人数を決定する方法を示す。
【図９】図９は２台の画像センサ、一つの対象物およびその対象物のシルエットコーンを示す上面図である。
【図１０Ａ】図１０Ａは対象物無しの２台の画像センサおよび投影シルエットコーンの上面図を示す。
【図１０Ｂ】図１０Ｂは図１０Ａの投影されたシルエットコーンと、第一のコンフィギュレーションにおける多数の対象物を示す上面図である。
【図１０Ｃ】図１０Ｃは図１０Ａの投影されたシルエットコーンと、第二のコンフィギュレーションにおける多数の対象物を示す上面図である。
【図１０Ｄ】図１０Ｄは図１０Ａの投影されたシルエットコーンと、第三のコンフィギュレーションにおける多数の対象物を示す上面図である。
【図１０Ｅ】図１０Ｅは図１０Ａの投影されたシルエットコーンと、第四のコンフィギュレーションにおける多数の対象物を示す上面図である。
【図１１】図１１は、本発明の一つの実施形態による、群集のvisual hullの平面投影を決定するために、従来の群集の画像を利用する方法を示す。
【図１２Ａ】図１２Ａは３台のセンサ、それらの投影シルエットコーンおよび多数の対象物を示す上面図である。
【図１２Ｂ】図１２Ｂは３台のセンサ、それらの投影シルエットコーン、多数の対象物および幻影の多角形を示す上面図である。
【図１３】図１３は本発明の一つの実施形態によるツリーデータ構造のダイアグラムを示す。
【技術分野】
【０００１】
本発明は計算装置を用いて群集の人数を決定することに関する。より具体的には、本発明は群集の人数を決定するためにvisual hull情報を利用することに関する。
【背景技術】
【０００２】
群集の人数を決定するいくつかの技術が現存する。しかしながら、これらの技術はそれぞれに欠点を有している。一つの技術は群集の空間像を生成した後、画像中の人数を数える。例えば、戸外の場所の群集は航空機または衛星から写真を撮ることができる。この画像は群集の人数を数えるために使用される。この技術の欠点は、このような画像を得るためには群集が戸外に居なければならないことである。もう一つの欠点は、画像の分解能が低い場合があるので、人数を数えることが難しいことである。さらに別の欠点は、この技術は一つの特定の時刻（即ち、画像が生成されたとき）の群集の人数を提供することに有る。それより後の時刻において、群集の人数を決定するためには、全てのプロセスを繰り返さなければならない。この理由は、第一回の実行で取得された情報を第二回の実行で利用できないからである。
【０００３】
群集の動的特徴を考慮に入れる別の技術では、群集内の且つ／又は群集周囲の物理的なチェックポイントを選定する。その後、群集の人数はチェックポイントを通過した人数に基づいて予想される。必要なチェックポイントの数は群集の規模に依存し、多くの場合いくつかのチェックポイントが必要である。チェックポイントで人数を決定する一つの方法は、手入力（即ち、人が実際に人を数える）による。この技術は非常に労働集約的である。もう一つのより労働集約的でない方法は、人数を数える装置を使用する。例えば、カメラはチェックポイントで群集を監視することができ、コンピュータはその画像を処理することができる。しかしながら、人は互いに重なり合い、何人の人が現存するかの決定が難しくなるので、これらの二つの技術は両者ともにチェックポイントが混雑している場合は誤差を引起しやすい。
【０００４】
チェックポイント技術のもう一つの問題点は二重カウントの問題である。１人の人が複数のチェックポイントから視認され得る。これは、その人がチェックポイント間を移動すること、またはチェックポイントの視認領域が重なることにより発生する。第一の状況は、概略同時に個々のチェックポイントに何人の人が居るか決定することによって処理できる。必要な同時性の程度は、群衆中の人の移動性とチェックポイント間の距離に依存する。第二の状況は、しかしながら、依然として残ったままである。代替的な手法の一つは、特定の個人を識別（追跡）し、その後それぞれの個人が一回だけしかカウントされていないことを確認する。チェックポイントで人をカウントするために画像装置が使用される場合、個人を追跡することは難しい。まず、個人個人は非常に似通って見える。さらに、いくつかの異なる装置から情報が集められ処理されなければならない。このために、多くの帯域幅と計算が必要である。
【０００５】
群集の規模と密度にかかわらず、限られた量の帯域幅と計算により、実時間で群集の人数を決定する方法が必要である。
【発明の開示】
【０００６】
発明の要約
Visual hull情報を用いて群集の人数を決定するシステム、装置および方法が提示される。一つの実施形態において、システムは画像センサと中央コンピュータのネットワークからなる。他の実施形態では、システムはさらに１台以上のローカルコンピュータを含む。一つの実施形態において、画像センサは群集に対してどのような高さおよびどのような角度で配置されても良い。
【０００７】
一つの実施形態において、群集のvisual hullの平面投影は次のように決定される：画像センサが画像センサから見た従来の群集画像を生成する。次に、シルエット画像が従来の画像に基づいて決定される。シルエット画像コーンと動作容積の交差領域が決定される。交差領域の平面上への投影が決定される。最後に、いくつかの画像センサから平面投影が集められる。
【０００８】
一つの実施形態において、中央コンピュータはいくつかの画像センサからの平面投影を、それらを交差させ細分化パターンを形成することによって、集積する。一つの実施形態において、中央コンピュータは一つの多角形が対象物を包含すると決定する場合には厳密な一致を要求する。別の一つの実施形態において、中央コンピュータは投票スキームを使用する。一つの実施形態において、中央コンピュータは次にどの多角形が実際に空であるか決定し、それらを除外する。
【０００９】
一つの実施形態において、中央コンピュータは次に個々の多角形における人数の上下限を決定する。一つの実施形態において、これらの境界はツリーデータ構造に保存される。一つの実施形態において、このツリーは時間の経過にしたがって画像センサから新しい情報が受信され更新される。一つの実施形態において、群集の人数はツリーのルートノードの下限に等しい。
【発明を実施するための最良の形態】
【００１０】
実施形態の詳細な説明
類似の番号が類似の要素を示す添付図面の図において、発明は限定するためではなく、例示を目的として示されている。
以下の説明において、説明の目的から、多くの具体的な詳細が発明の完全な理解を目的として提示される。しかしながら、これらの具体的な詳細が無くても、本発明が実施可能であることは、当業者にとって明らかである。他の場合において、本発明を不明確にすることが無いように、構造および装置がブロック図の形で示されている。
【００１１】
明細書中の「一つの実施形態」又は「実施形態」の使用は、その実施形態に関連して説明された特定の特徴、構造又は特性が本発明の少なくとも一つの実施形態に含まれることを意図している。明細書中のいくつかの個所で出現する「一つの実施形態において」は必ずしも全てが同じ実施形態を言及するものではない。
【００１２】
以下に述べられる詳細な記述のある部分は、コンピュータメモリ内のデータビット上の動作についてアルゴリズムの形および記号表現の形で示されている。これらのアルゴリズムの説明および表現は、データ処理技術に携わる当業者が自分の成果の中身を最も効果的に他の当業者に対して伝達するために使用する手段である。ここでは、また一般にも、一つのアルゴリズムは所望の結果に導く自己矛盾の無い一連のステップと考えられる。ステップは物理量の物理的な操作を要求するものである。必ずというわけではないが、通常、これらの量は、保存、移動、結合、比較およびその他の操作が可能な電気または磁気信号の形を取る。主に通常の使用にかかわる理由として、これらの信号を、ビット、数値、要素、記号、文字、項、番号等と呼ぶと便利な場合があることが分かっている。
【００１３】
しかしながら、これらおよび類似の項の全てが、適切な物理量と関連付けられ、これらの量に適用される便宜的な表示に過ぎないことを覚えておくべきである。具体的に宣言されない限り、以下の議論で明らかなように、説明を通して、「処理する」、「演算する」、「計算する」、「決定する」「表示する」等を使用した議論は、コンピュータシステムのレジスタおよびメモリ内に物理（電子）量として表されているデータを、コンピュータシステムのメモリ、レジスタ、あるいは他のそのような情報保存、伝送またはディスプレイ装置内で、同じように物理量として表わされる他のデータに、操作して変換するコンピュータシステムまたは類似の電子計算装置の実行および処理、に言及している。
【００１４】
本発明はここで動作を実行する装置にも関係している。この装置は要求された目的に合わせて構成されている専用機か、あるいはコンピュータ内に保存されたコンピュータプログラムによって、選択的に作動または再設定される汎用のコンピュータからなる。このようなコンピュータプログラムはコンピュータが読み出し可能な次のようなストレージ媒体、以下に限定されないが例えば、フロッピーディスク、光ディスク、ＣＤ−ＲＯＭ、光磁気ディスクを含む任意のタイプのディスク、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気または光カード、または電子命令を保存可能な全てのタイプの媒体に保存され、以上の媒体のそれぞれはコンピュータシステムバスに接続される。
【００１５】
ここで示されるアルゴリズムとディスプレイは特定のコンピュータまたは他の装置に固有に関連するものではない。多種の汎用目的のシステムが、ここでの教示事項に従ったプログラムと共に使用され、あるいは要求される方法のステップを実行するためにより特殊化された装置が構築される。これらのさまざまなシステムに要求される構成は以下の説明によって明らかになる。さらに、本発明はいずれの特定のプログラミング言語も参照することなく説明される。ここで説明される本発明の教示事項を実施するためにさまざまなプログラミング言語が使用可能であると認識される。
【００１６】
１．群衆の人数を決定するためのシステムの構成
以下の説明は、群衆の人数を決定するためのシステムの構成を扱うものであるが、該システムはある特定のエリアにある対象物の数を決定するために使用することも可能である。対象物は同一のタイプからなるもの（例えば、人々）、または異なるタイプからなるもの（例えば人々と動物）のいずれの場合もありうる。
【００１７】
図１は本発明の一つの実施形態による、群集の人数を決定するためのシステムの俯瞰図（ブロック図の形式で）を示す。群集の存在が想定される長方形の領域１１０をいくつかの画像センサ１００が取り囲む。領域１１０は物理的な境界によって境界が定められても定められなくても良い。実施形態では８台の画像センサが示されているが、１台より多ければいかなる数の画像センサの使用も可能である。一般に、使用される画像センサ１００の数が増えれば、システムが取り扱い可能な領域１１０のサイズも増加する。
【００１８】
一つの実施形態においては、図１に示されたシステムは領域１１０に存在する人の数の上下限を演算する。他の実施形態においては、下限が存在する人の数に等しい。一般に、使用センサ１００の数が増加するにつれて、システムが正しく数えることができる人数が増加する。さらに他の実施形態においては、システムは常に領域１００に存在する人数の上下限を計算する。
【００１９】
一つの実施形態においては、画像センサ１００はネットワーク１９０を使用する中央コンピュータ１２０に接続されている。ネットワーク１９０との双方向の通信リンクは有線または無線（例えば地上波または衛星を利用したトランシーバ）のいずれの形も可能である。一つの実施形態においては、ネットワーク１９０は個人のネットワークである。他の一つの実施形態においては、ネットワーク１９０は、ＩＰに基づいた構内通信網（ＬＡＮ）または広域通信網（ＷＡＮ）である。
【００２０】
データは画像センサ１００から中央コンピュータ１２０へ送られる。中央コンピュータ１２０はこのデータを用いて群集のvisual hullの平面投影を決定する。対象物のvisual hullは、対象物がその中に存在することができて、対象物の外部の全てのビューに対して、対象物自身と同一のシルエットを生み出す最大の体積である。換言すれば、visual hullは対象物のいくつかのシルエットコーンの交差領域である。シルエットコーンは異なる場所から見たときの対象物の異なるビューを示す。Visual hullを生成する技術には、ボリューム・インターセクション（volume intersection） およびシェイプ・フロム・シルエット（shape-from-silhouette）が含まれる。対象物のvisual hullはその定義から対象物を完全に包含することが保証されている。Visual hullとその生成方法については当業者に知られ、詳細については「ザ・ビジュアル・ハル・コンセプト・フォー・シルエット−ベイスト・イメージ・アンダースタンディング」Ａ．ロオレンティニ、ＩＥＥＥトランザクションズ・オン・パターン・アナリシス・アンド・マシーン・インテリジェンス、１６：２、１９９４年２月（”The Visual Hull Concept for Silhouette-Based Image Understanding” by A. Laurentini, IEEE Transactions on Pattern Analysis and Machine Intelligence, 16:2, February 1994.）に記載されている。Visual hullの平面投影はvisual hullの平面上への投影である。一つの実施形態においては、中央コンピュータ１２０が長方形領域１１０の床上への群集のvisual hullの投影を決定する。この実施形態においては、群集のvisual hullの平面投影は、群集の上部位置から見たときの群衆のシルエットに類似している。
【００２１】
一旦群集のvisual hullの平面投影が決定されると、中央コンピュータ１２０が群集の人数を決定する。群集の人数を決定するために中央コンピュータ１２０が使用する方法を、図８を参照して以下に説明する。
【００２２】
上述のように、中央コンピュータ１２０は画像センサ１００からのデータを用いて群衆のvisual hullの平面投影を決定する。一つの実施形態においては、画像センサ１００は中央コンピュータ１２０から問い合わせを受信した後、データを中央コンピュータ１２０へ送る。他の一つの実施形態においては、画像センサ１００は問い合わせを受信することなく中央コンピュータ１２０へデータを送る。さらに他の一つの実施形態においては、画像センサ１００は定期的に中央コンピュータ１２０へデータを送る。二つの画像センサ１００が定期的に中央コンピュータにデータを送信する場合、それらの送信は同期してもしなくても良い。
【００２３】
ａ．群集のvisual hullの平面投影を決定するシステムの使用
一つの実施形態において、群集のvisual hullの投影は、群集のvisual hullを決定し（異なるセンサからの群集のビューに基づく）、その後visual hullを平面上に投影することによって決定される。少ない演算リソースが要求される他の一つの実施形態では、群集のvisual hullの平面投影は、それぞれのシルエットコーンを平面上に投影し、その結果得られる２次元マップを集積することによって決められる。この実施形態はvisual hullの平面投影の近似を与えるに過ぎないが、群集の人数を決定するには充分な近似である。さらに他の一つの実施形態においては、前記の実施形態によって必要とされる演算リソース量は、群集のvisual hull を動作容積（working volume）で交差させることによって（前者の実施形態）、または個々のシルエットコーンを動作容積で交差させることによって（後者の実施形態）さらに減少される。
【００２４】
図１１は、本発明の一つの実施形態による、群集のvisual hullの平面投影を決定するために、群集の従来の画像を利用する方法を示す。最初のステップで、複数の従来の群集の画像が生成される（１１００）。複数のシルエット画像が従来の画像に基づいて決定される（１１１０）。個々のシルエット画像コーンと動作容積の交差領域が決定される（１１２０）。個々の交差領域の平面上への投影が決定される（１１３０）。最後に、群集のvisual hullの平面投影を形成するためにそれらの投影が集められる（１１４０）。
【００２５】
ステップ１１００、１１１０、１１２０、１１３０、および１１４０は、例えば、画像センサ１００、中央コンピュータ１２０、あるいは追加のローカルコンピュータ（図示せず）によって実行される。一つの実施形態においては、画像センサ１００の間の通信構成は比較的集中化されていない。一つの実施形態においては、１台以上の近傍のセンサ１００からのデータを処理するために１台以上のローカルコンピュータが使用される。その後、このローカルコンピュータは得られたデータをさらに処理するために中央コンピュータ１２０へ送る。
【００２６】
一つの実施形態において、例えば、画像センサ１００は、このセンサ１００の視点から見た群集の従来の画像を生成する（１１００）。この実施形態においては、画像センサ１００は、従来の画像を生成できるカメラのような、どのようなタイプの装置をも含む。
【００２７】
この従来のイメージに基づいてシルエット画像が決定される（１１１０）。一つの実施形態においては、シルエット画像には２色のみが使用される：１色は前景（群衆中の人々）、もう１色は背景（人が居ない場所）。別の一つの実施形態では、シルエット画像は白黒のビットマップである。
【００２８】
シルエット画像を決定するために（１１１０）、いくつかの方法のいずれもが使用できる。一つの実施形態においては、背景減算を用いてシルエット画像が決定される（１１１０）。シルエット画像を生成するために従来の画像イメージから背景が減算される。一つの実施形態においては、人が全く存在しない場合は、画像センサ１００の出力が、画像センサ１００から見た時の背景画像に対して較正される。一つの実施形態においては、コンピュータが背景減算を実行する。他の一つの実施形態では、ＣＭＯＳセンサの集合体が背景減算を実行する。例えば、内蔵のＣＭＯＳロジックが、同一または前の画像内の近傍のピクセルの値に基づいて、従来画像のピクセルの値を比較する。背景減算は当業者に知られた技術であり、「ア・ローバスト・バックグラウンド・サブトラクション・アンド・シャドウ・ディテクション」Ｔ．ホープラサート他、プロシーディングズ・オブ・エイジャン・コンファランス・オン・コンピュータ・ビジョン、２０００年１月（”A Robust Background Subtraction and Shadow Detection” by T. Horprasert et al., Proceedings of Asian Conference on Computer Vision, January 2000）に詳細が記載されている。
【００２９】
他の実施形態では、動作検出を用いてシルエット画像が決定される（１１１０）。この実施形態では、動的対象物は従来の画像として検出され、シルエットとして取り出される。静的対象物は背景の一部と見なされ、シルエット画像には含まれない。動的検出は、例えば、コンピュータまたはＣＭＯＳセンサの集合体を用いて実行することができる。内蔵されたＣＭＯＳロジックが、画像内のピクセルの値を、同一のまたは前の画像内の近傍のピクセルの値と比較して動的検出を実行する。動作検出は当業者に知られている。
【００３０】
さらに別の一つの実施形態においては、シルエット画像は画像内の対象物の距離に関する情報を用いて決定される（１１１０）。この実施形態においては、前景の対象物はセンサ１００の近接した位置にあり、一方、背景対象物はセンサ１００から離れている。シルエット画像は、対象物の距離を閾値と比較し、前景の対象物を背景の対象物から分離して生成される。３次元の深さセンサが当業者に知られていて、例えば、カネスタ社および３ＤＶ・システムズ社（Canesta, Inc. and 3DV Systems, Ltd.）から入手可能である。
【００３１】
ステップ１１１０は、例えば、画像センサ１００によって実行される。この実施形態においては、センサ１００は上で説明した方法のいずれかを用いて従来のイメージからシルエット画像を決定できる（１１１０）システムからなる。例えば、該システムはコンピュータのこともある。他の例として、該システムはＣＭＯＳセンサの集合体のこともある。代替案として、ステップ１１１０は、例えば、中央コンピュータ１２０またはローカルコンピュータによっても実行可能である。この実施形態においては、中央コンピュータ１２０（またはローカルコンピュータ）がセンサ１００から従来のイメージを受信する。中央コンピュータ１２０（またはローカルコンピュータ）は次に、上で説明した方法のいずれかを用いて従来のイメージからシルエット画像を決定する（１１１０）。
【００３２】
シルエット画像コーンと動作容積の交差領域が次に決定される（１１２０）。動作容積は人々の存在を検出する空間容積である。シルエットコーンと動作容積の交差領域は、特定のセンサ１００から見た対象物のビューに基づいて、対象物がどこに存在する可能性があるかを表す３次元形状である。一つの実施形態においては、動作容積は床（長方形領域１１０）と平行に位置する四角柱である。動作容積の高さは可変である。一般に、動作容積の高さを限定すれば、群集のvisual hullの平面投影を計算するために必要なリソース量は減少する。一つの実施形態においては、動作容積の高さは最も背の高い人の身長以上で、動作容積は床面を起点とする。他の一つの実施形態においては、動作容積の高さは３フィートで、動作容積は腰の位置（例えば、床から３フィート）を重点的にカバーする。３次元形状の交差領域を決定する方法は当業者に知られており、ハンドブック・オブ・ディスクリート・アンド・コンピュテーショナル・ジオメトリ、グッドマンおよびオールーケ編、ＣＲＣ・プレス、１９９７、５９９−６３０頁（Handbook of Discrete and Computational Geometry, Goodman and O’Rourke, Eds., CRS Press, 1977, pp. 599-630）に詳細が記載されている。
【００３３】
ステップ１１２０は、例えば、画像センサ１００によって実行される。この実施形態においては、センサ１００は３次元対象物（シルエット画像コーンと動作容積）の交差領域を決定できる（１１２０）システムからなる。例えば、該システムはコンピュータのこともある。代替案として、ステップ１１２０は、例えば、中央コンピュータ１２０またはローカルコンピュータによって実行することも可能である。この実施形態においては、中央コンピュータ１２０（またはローカルコンピュータ）がセンサ１００からシルエット画像を受信する。中央コンピュータ１２０（またはローカルコンピュータ）が次にシルエット画像コーンと動作容積との交差領域を決定する（１１２０）。
【００３４】
個々の交差領域の平面への投影が決定される（１１３０）。上述のように、交差領域は対象物がどこに存在する可能性のあるかを表す３次元形状である。この形状の平面投影は、どこに対象物が存在するかを２次元マップで示す。一つの実施形態においては、この平面は床（長方形領域１１０）である。この実施形態においては、交差領域の平面投影は対象物が存在する可能性のある床スペースの領域に相似である。３次元形状の平面投影を決定する方法は当業者に知られている。
【００３５】
ステップ１１３０は、例えば、画像センサ１００によって実行される。この実施形態においては、センサ１００は３次元対象物（シルエット画像コーンと動作容積の交差領域）の平面上への投影を決定できる（１１３０）システムからなる。例えば、該システムはコンピュータのこともある。代替案として、ステップ１１２０は、例えば、中央コンピュータ１２０またはローカルコンピュータによって実行することも可能である。この実施形態においては、中央コンピュータ１２０（またはローカルコンピュータ）がセンサ１００から３次元対象物の表示（シルエット画像コーンと動作容積の交差領域）を受信する。中央コンピュータ１２０（またはローカルコンピュータ）が次に３次元対象物の平面への投影を決定する（１１３０）。
【００３６】
最後に、平面投影は、群集のvisual hullの平面投影を形成するために集められる。このステップについて以下に図８を参照して説明する。
【００３７】
ｂ．システム内へのセンサの配置
画像センサ１００は対象物に対して任意の高さおよび角度で据付が可能である。しかしながら、画像センサ１００の位置および向きによって画像センサ１００からの対象物の見え方が影響される。画像センサの対象物の見え方は、３次元空間のコーンを掃引するシルエットであることを思い出そう。このように、対象物の正確な位置は、１台だけの画像センサ１００からの対象物のシルエットに基づいて決定することはできない。特に、対象物と画像センサ１００との距離は決定できない。
【００３８】
図２は、画像センサ、人および投影シルエットコーンの側面図である。図２Ａにおいて、画像センサ１００は人２００の真上（例えば天井）に位置し、床を向いている。図２Ｂは図２Ａの人および投影シルエットコーンの上面図である。図２Ｂに示された投影シルエットコーン２１０の上面図も、画像センサ１００から見た時の人２００のシルエット画像である。さらに、このシルエットはこの人のvisual hullの平面投影である。
【００３９】
画像センサ１００からのシルエット画像を用いて人２００のvisual hullの平面投影を決定することが最終目的の場合は、シルエット画像が既に所要の平面投影に等しいことが望ましい。このように、画像センサ１００の好ましい配置は、人２００の真上になろう。この配置では、シルエット画像は、人２００のvisual hullの平面投影を決定するために、これ以上の処理を必要としない。しかしながら、上述のように、群集の上に画像センサ１００を設置することは、例えば屋外の集まりにおいて、実際的でない。この配置では、人２００と画像センサ１００との距離が決定されないことに注意して欲しい。しかしながら、人２００と画像センサ１００との距離は人のvisual hullの平面投影とは無関係であるので、距離が決定されないことは問題にならない。
【００４０】
図３Ａは画像センサ、人および投影シルエットコーンの側面図である。図３Ａでは画像センサ１００が人２００の横に斜めになるように配置されている。図３Ｂは図３Ａの画像センサ、人および投影シルエットコーンの上面図である。図３Ｂに示された人２００の上面からの見え方は、画像センサ１００から見たときのシルエットコーンの投影と同じでないことに注意を喚起する。また、画像センサ１００から見た人２００のシルエット画像は、人のvisual hullの平面投影ではない。この配置では、人２００と画像センサ１００との距離は決定できない。しかしながら、図２Ａおよび２Ｂの配置とは異なり、人２００と画像センサ１００との距離は人のvisual hullの平面投影に関係するので、距離を決定できないことが問題になる。
【００４１】
図４Ａは画像センサ、人および投影シルエットコーンの側面図である。図４Ａにおいて、画像センサ１００は床に平行に配置され、人２００はセンサ視野範囲内に在る。図４Ｂは、図４Ａの画像センサ、人および投影シルエットコーンの上面図である。図４Ｂに示された人２００の上面からの見え方は、画像センサ１００から見たときのシルエットコーンの投影と同じでないことに注意を喚起する。また、画像センサ１００から見た人２００のシルエット画像は、人のvisual hullの平面投影ではない。この配置では、人２００と画像センサ１００との距離は決定できない。しかしながら、図２Ａおよび２Ｂの配置とは異なり、人２００と画像センサ１００との距離は人のvisual hullの平面投影に関係するので、距離を決定できないことが問題になる。
【００４２】
上述のように、画像センサ１００は対象物に対して任意の高さおよび角度で配置することが可能である。しかしながら、群集のvisual hullの平面投影を計算するためには、動作容積内のポイントは少なくとも２台のセンサ１００から可視状態になければならない。多数のセンサ１００からビューを取得すれば、システムのオクルージョンの処理の助けになる。説明を明確にするために、本発明は今後、画像センサ１００が、図４Ａおよび４Ｂと同様に、床に平行に配置されている実施形態によって説明する。
【００４３】
一般に、画像センサ１００は、シルエットが不完全であっても、センサの視野内の人が唯一のシルエットを作るように配置されるべきである。例えば、画像センサ１００が地上から１０フィート上に配置されるとした場合、５フィートの身長の人は、センサ１００の近くに位置しようが離れていようが、センサの視野から外れる可能性がある。図５は画像センサ、画像センサの視野および異なる二箇所に位置している人の側面図である。図５では、画像センサ１００は床と平行に配置され、人２００は第１の位置２００Aと第２の位置２００Bのいずれの位置においても、視野５００の外部にある。当然のことながら、人２００は第２の画像センサ１００（図示せず）の視野内に入ることはあり得る。一般に、領域１１０は画像センサ１００によって充分にカバーされるべきであるが、全ての画像センサが領域１１０内の全ての場所をカバーする必要は無い。同様に、画像センサ１００は一人の人を表している二つの対象物を見るべきでない。画像センサが地上に配置された場合、視野２００内を歩行する人２００は二つの対象物（左足と右足）として現れるかもしれない。従って、一つの実施形態においては、画像センサ１００は地上から約３フィート離して設置される。この高さに置かれると画像センサ１００は人の胴を見ることができる。
【００４４】
２．群集の人数を決定するための装置の構成
図６は本発明の一つの実施形態による群衆のvisual hullの平面投影に基づいた群集の人数を決定するための装置のブロック図である。装置６００は好ましくはプロセッサ６１０、主メモリ６２０、データ保存装置６３０および入出力制御器６８０からなり、これらの全てはシステムバス６４０に通信可能な状態で接続されている。装置６００に、例えば、汎用のコンピュータを使用することも可能である。
【００４５】
プロセッサ６１０はデータ信号を処理し、複号命令セットコンピュータ（ＣＩＳＣ）、縮小命令セットコンピュータ（ＲＩＳＣ）または命令セットの組み合わせを実施する構成を含むさまざまな計算構成からなる。図６では一つのプロセッサだけが示されているが、多数のプロセッサが含まれる場合もある。
【００４６】
主メモリ６２０はプロセッサ６１０によって実行される命令および／またはデータを保存する。命令および／またはデータは、ここで説明される技術のいずれかおよび／または全てを実行するためのコードからなる。主メモリ６２０はダイナミックランダムアクセスメモリ（ＤＲＡＭ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）またはその他の周知のメモリデバイスであることが望ましい。
【００４７】
データ保存装置６３０はプロセッサ６１０のためのデータおよび命令を保存し、ハードディスクドライブ、フロッピディスクドライブ、ＣＤ−ＲＯＭデバイス、ＤＶＤ−ＲＯＭデバイス、ＤＶＤ−ＲＡＭデバイス、ＤＶＤ−ＲＷデバイス、フラッシュメモリデバイスまたはその他の既知の大容量ストレージデバイスを含む一つ以上のデバイスからなる。
【００４８】
ネットワーク制御器６８０は装置６００が通信できるように装置６００を他の機器にリンクさせる。
【００４９】
システムバス６４０は装置６００の至る所で情報およびデータを通信するための共有バスである。システムバス６４０は、工業標準アーキテクチャ（ＩＳＡ）バス、周辺機器相互接続（ＰＣＩ）バス、ユニバーサルシリアルバス（ＵＳＢ）またはその他の類似の機能を実現できる周知のバスを含むバスの一つ以上のバスである。
【００５０】
システムバス６４０経由で装置６００に接続される可能性のある追加のコンポーネントとしては、ディスプレイ装置６５０、キーボード６６０およびカーソル制御装置６７０がある。ディスプレイ装置６５０は電子イメージおよびデータをローカルユーザまたは保守担当者に表示できる装置であればどのようなものでも構わない。ディスプレイ装置６５０は陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）またはその他の類似の機能を有するディスプレイ装置、スクリーンまたはモニタである。キーボード６６０は情報および命令選択をプロセッサ６１０へ通信するために装置６００に接続されたアルファベットと数字を組み合わせた入力装置である。カーソル制御装置６７０は命令選択および位置データをプロセッサ６１０へ通信するために備えられたユーザ入力装置である。カーソル制御装置６７０は、マウス、トラックボール、スタイラス、ペン、カーソル方向キーあるいはカーソルに動作を与える他の機構からなる。
【００５１】
当業者にとって、本発明の範囲を逸脱することなく、装置６００が図６に示された例より多くのまたは少ないコンポーネントから構成されることは自明である。例えば、装置６００は追加のメモリ、例えば、プライマリまたはセカンダリレベルのキャッシュ、あるいは一つ以上の特定用途向け集積回路（ＡＳＩＣ）を含む。上述のように、装置６００はＡＳＩＣだけから構成することも可能である。さらに、装置６００に連結される可能性のあるコンポーネントとしては、例えば、画像走査装置、デジタルスチルまたはビデオカメラ、あるいは装置６００へ／又は装置６００から電子データを取得および／またはダウンロードするために装備されてもされなくても良い他の装置が挙げられる。
【００５２】
図７は図６に示されたメモリユニットの内容を示すより詳細なブロック図である。一般に、メモリユニット６２０は、群集のvisual hullの平面投影に基づいて群集の人数を決定するためのいくつかのコードモジュールからなる。一つの実施形態において、メモリユニット６２０は、シルエットコーンと動作容積との交差領域の平面投影に基づいて群集のvisual hullの平面投影を近似する。特に、メモリユニット６２０のコードモジュールは、メインプログラムモジュール７００、集積モジュール７１０、除去モジュール７２０、ツリー決定モジュール７３０、ツリー更新モジュール７４０および合計モジュール７５０からなる。
【００５３】
全てのコードモジュール７１０、７２０、７３０、７４０、７５０はメインプログラムモジュール７００に連結されて通信が可能である。メインプログラムモジュール７００が中央から装置６００の動作および処理フローを制御し、個々のコードモジュール７１０、７２０、７３０、７４０、７５０からデータを受信するとともに、これらのモジュールへ命令とデータを送信する。メインプログラムモジュール７００の動作の詳細については図８を参照して以下に説明する。
【００５４】
集積モジュール７１０は、シルエットコーンと動作容積との交差領域の平面投影を含む複数の二次元マップを集積する。個々の二次元マップは１台のセンサ１００からのビューに基づいた、人が存在する可能性のある領域を包含する。この領域はシルエットコーンと動作容積との交差領域の平面投影である。集積によってマップが交差し、それはマップを互いに重ね合わせ、どこでシルエットコーンが重なり合うかを見ることに類似している。
【００５５】
図９は２台の画像センサ、一つの対象物およびその対象物のシルエットコーンの上面図である。図示の実施形態では、シルエットコーンは楔形をしている。多数のセンサ１００が領域１１０を囲む場合、楔形のシルエットコーン９１０Ａと９１０Ｂは交差し（重なり）細分化パターンを形成して、領域１１０をいくつかの多角形９００Ａ，９００Ｂ，９００Ｃ，９００Ｄおよび９００Ｅに分割する。図示の実施形態では、シルエットコーン９１０Ａは多角形９００Ｂ，９００Ｃおよび９００Ｄからなる一方、シルエットコーン９１０Ｂは多角形９００Ａ，９００Ｃおよび９００Ｅからなる。このようにしてセンサ１００Ａは対象物が多角形９００Ｂ，９００Ｃおよび９００Ｄ内に位置すると決定でき、一方、センサ１００Ｂは対象物が多角形９００Ａ，９００Ｃおよび９００Ｅ内に位置すると決定できる。これとともに、センサ１００Ａおよび１００Ｂからの情報は集積されて、対象物が多角形９００Ｃ内に位置していると決定することが可能である。
【００５６】
一つの実施形態において、上述の細分化は厳密に決定される。この実施形態ではシルエットコーンの境界は線で表される。これらの線は交差すると多角形の境界線を形成する。他の一つの実施形態においては、細分化に近似が用いられる。この実施形態では、二次元マップは、シルエットコーンがピクセルのパッチになるように画素化される。画素化はまたラスタ処理またはスキャン変換と呼ばれ、当業者に知られている。その詳細はグラフィクス・ジェムズ、Ａ．グラスナー編、モーガン・カオフマン、１９９８年、７５−９７頁（Graphics Gems, A. Glassner, Ed., Morgan Kaufmann, 1988, pp. 75-97）に記載されている。
【００５７】
一般に、厳密な細分化はアルゴリズムの観点から実施するのは困難で、必要な演算リソースは少なく、誤差の扱いにおいては能力が低い。対照的に、画素化は実施し易いが、演算リソースをより多く必要とし、誤差を扱う能力はより高い。一つの実施形態においては、特別のグラフィックハードウェアがマップをピクセル化し交差させるために用いられる。特別のグラフィックハードウェアがピクセル化に用いられる場合は、必要な演算リソース量は大幅に減少する。
【００５８】
集積モジュール７１０はマップを交差させることによっていくつかのセンサからの情報を集積する。結果として得られる交差領域は群集のvisual hullの近似である。一つの実施形態において、集積モジュール７１０は対象物が存在するかもしれないと決定するときに厳密な一致を必要とする。この実施形態では、ある特定の多角形領域をカバーする全てのマップ（センサビュー）は対象物がその領域にあると一致しなければならない。１台のセンサでもその領域に対象物が無いと出力した場合には、集積モジュール７１０は対象物が存在しないと決定する。他の実施形態においては、集積モジュール７１０は投票スキームを用いる。この実施形態においては、対象物が存在する可能性があるとするマップの数と対象物が存在しないとするマップの数を比較する。「対象物有り」のマップの数またはパーセントが閾値より高い場合、集積モジュール７１０は対象物がその領域に存在すると決定する。
【００５９】
一つの実施形態においては、ローカルコンピュータが二次元マップの全数の一部である部分集合を集積するために使用される。この実施形態では、センサ１００からのビューの集積を分散して実施することが可能になる。ローカルコンピュータで集めた結果が中央コンピュータ１２０で集められる。
【００６０】
図１０Ａは対象物無しの２台の画像センサおよび投影シルエットコーンの上面図である。多角形領域１０００Ａ，１０００Ｂ，１０００Ｃおよび１０００Ｄは対象物が存在する可能性のある場所を示している。換言すれば、多角形領域１０００Ａ，１０００Ｂ，１０００Ｃおよび１０００Ｄは投影された対象物のvisual hullである。一人より多い対象物が多角形領域１０００Ａ，１０００Ｂ，１０００Ｃおよび１０００Ｄに存在する可能性のあることを喚起されたい。対象物のいくつかの配置が一つの所与のvisual hullに一致することができるので、投影されたvisual hullはあいまい性を持つ。図１０Ｂは図１０Ａの投影されたシルエットコーンと第一のコンフィギュレーションにおける多数の対象物の上面図である。図１０Ｃは図１０Ａの投影されたシルエットコーンと第二のコンフィギュレーションにおける多数の対象物の上面図である。図１０Ｄは図１０Ａの投影されたシルエットコーンと第三のコンフィギュレーションにおける多数の対象物の上面図である。図１０Ｅは図１０Ａの投影されたシルエットコーンと第四のコンフィギュレーションにおける多数の対象物の上面図である。図１０Ｂ，１０Ｃ，１０Ｄおよび１０Ｅのいずれの対象物のコンフィギュレーションも図１０Ａの投影されたvisual hullと一致している。
【００６１】
除去モジュール７２０はどの投影visual hullの多角形領域が空かを決定し、それらを投影から除外する。これらの多角形領域は幻影（phantoms）として知られている。幻影の一つのタイプはサイズに基づいて識別される。例えば、最低の対象物サイズより小さい多角形は除外される。他の幻影のタイプは時間的コヒーレンスに基づいて識別される。例えば、対象物が無いのに現出する多角形(次の多角形にはなり得ないもの)は除外される。このタイプの幻影は３台以上のセンサ１００によるものである。図１２Ａは３台のセンサ、それらの投影シルエットコーンおよび多数の対象物の上面図である。図１２Ｂは３台のセンサ、それらの投影シルエットコーン、多数の対象物および幻影多角形の上面図である。二つの対象物１２００Ａと１２００Ｂが二つの連続の時間ステップ（最初に図１２Ａ次に図１２Ｂ）で観測され、幻影１２１０が図１２Ｂに現出している。一つの実施形態においては、多角形の時間コヒーレンスは、その多角形が前の時間ビュー（例えば図１２Ａ）において多角形を交差したかテストすることによってチェックされる。このテストでは対象物が一つの時間ステップでそのvisual hullによって作られた領域を去ることは無いと仮定している。一つの実施形態においては、この最大スピードの仮定は、交差領域を計算する前に、前の時間ステップにおける多角形を拡張することによって調整される。
【００６２】
センサイメージがオクルージョン（ある人が他の人のセンサ１００による視認を妨害）を含む場合、群集の正しい人数を決定することはできない。その代わりに、一つの実施形態では、群集の人数は個々の多角形内に存在する人数を限定することによって決定される。ツリー決定モジュール７３０は個々の多角形内の人数の上下限を決定する。
【００６３】
上限制約（ＵＢＣ）−一つの実施形態において、最低の対象物サイズで割った多角形の面積が多角形の上限である。対象物がクラスタ化し一体となって単一の標的のように動くとして、考えられる最悪シナリオを仮定しているので、この境界は厳密性を非常に欠いている。この境界には、対象物の幾何学的形状によらず（変わった形状の入れ物を液体が満たすやり方に類似）、対象物が多角形の全領域を満たすとの仮定が用いられている。
【００６４】
下限制約（ＬＢＣ）−一つだけの多角形と交差する画像センサ１００からの光線があれば、その多角形は少なくとも一つの対象物を含む。これは画像センサ１００からの光線は、対応する視線が対象物によってブロックされた場合にだけ、多角形に交差するからである。一つだけの多角形が光線と交差する場合、対象物は多角形内に含まれるはずである。この制約は、対象物を直接数えるのでＵＢＣとは異なる。（真の対象物は光線に沿って観測されカウントされる。）対照的に、ＵＢＣは多角形を満たす対象物の最大数を仮定する。
【００６５】
一つの実施形態において、決定モジュール７３０はデータ構造に上下限を保存する。特定のＬＢＣの値は多角形が少なくとも一つの対象物を含むかを示すが、時系列のＬＢＣの振る舞いによって追加情報が伝達される。他の一つの実施形態では、データ構造はツリー（τ）になっている。ツリーに沿って下限を伝播することにより、領域１１０内の対象物の数がさらに制約される（例えば、下限が狭くなる）。
【００６６】
一つの実施形態においては、ツリーの個々の葉は、時刻ｔで、新たに観測された多角形とそれに関連する対象物の境界を保存する。ツリーのノードはその子孫の全ての多角形からなる暗黙の和集合を表している。このノードはこの和集合内の対象物の数に対する境界を含む。これにより、ツリー中の対象物の境界上で四つの特性が導入される：
【００６７】
【００６８】
【００６９】
【００７０】
【００７１】
【００７２】
【００７３】
【００７４】
【００７５】
境界の更新−方程式（１）−（４）が全てのノードに確実に成り立つようにするために、対象物の境界はツリー全体で更新される。これには次の二つの操作が含まれる：まず、葉からの新しい情報はτのルーツまで伝播される。その後、ルーツに対する更新された境界は葉まで伝播されて戻る。
【００７６】
合計モジュール７５０はツリーτのルートノードへ下限を返す。この数字が群集の人数である。
【００７７】
３．群集の人数を決定する方法
図８は本発明の一つの実施形態による群衆の人数を決定する方法を示す。方法が開始すると、ステップ１１３０に示すように、シルエットコーンと動作容積の交差領域の平面投影が既に決定されている。
【００７８】
最初のステップで、メインプログラムモジュール７００が開始する（８００）。メインプログラムモジュール７００は集積モジュール７１０に、シルエットコーンと動作容積の交差領域の平面投影である複数の２次元マップの集積を命令する（８１０）。そして、メインプログラムモジュール７００は除去モジュール７２０に、投影されたvisual hullのどの多角形が実際に空か決定し、それらを投影から除外することによって、多角形を除去するように命令する（８２０）。
【００７９】
メインプログラムモジュール７００は決定モジュール７３０に、上下限を保存することによって、ツリーデータ構造を決定するように命令する（８３０）。メインプログラムモジュール７００は、その後、合計モジュール７５０を用いて群集の人数を決定する（８４０）。
【００８０】
要望があれば、シルエットコーンと動作容積の交差領域の平面投影は、時間的に後に再決定される。方法はステップ８１０へ戻り（８６０）、ステップ８１０および８２０を繰り返す。その後、メインプログラムモジュール７００はツリー更新モジュール７４０にツリーデータ構造を更新するように命令する（８３０）。タイムステップがそれ以上ない場合は、メインプログラムモジュール７００は終了する（８５０）。
【００８１】
本発明はその実施形態を参照して相当な詳細にわたって説明されたが、当業者の理解が得られるように、他の実施形態も可能である。例えば、他の一つの実施形態が、「カウンティング・ピープル・イン・クラウズ・ウイズ・ア・リアル−タイム・ネットワーク・オブ・シンプル・イメージ・センサーズ」、Ｄ．ヤング、Ｈ．ゴンザレツ−バノス、およびＬ．ギバス共著、プロシーディングズ・オブ・ザ・ナインス・ＩＥＥＥ・インターナショナル・コンファランス・オン・コンピュータ・ビジョン（ＩＣＣＶ）、ニース、フランス、１０月１３−１６日、２００３年、１２２−１２９頁およびＣＤ−ＲＯＭ（Counting People in Crowds with a Real-Time Network of Simple Image Sensors” by D. Yang, H. Gonzalez-Banos, and L. Guibas, Proceedings of the Ninth IEEE International Conference on Computer Vision (ICCV), Nice, France, October 13-16, 2003, pp. 122-129 and CD-ROM）、に掲載されている。
【図面の簡単な説明】
【００８２】
【図１】図１は本発明の一つの実施形態による、群集の人数を決定するためのシステムの俯瞰図（ブロック図の形式で）を示す。
【図２Ａ】図２Ａは、画像センサ、人および投影シルエットコーンの側面図を示す。
【図２Ｂ】図２Ｂは、図２Ａの人および投影シルエットコーンの上面図を示す。
【図３Ａ】図３Ａは画像センサ、人および投影シルエットコーンの側面図を示す。
【図３Ｂ】図３Ｂは図３Ａの画像センサ、人および投影シルエットコーンの上面図を示す。
【図４Ａ】図４Ａは画像センサ、人および投影シルエットコーンの側面図を示す。
【図４Ｂ】図４Ｂは、図４Ａの画像センサ、人および投影シルエットコーンの上面図を示す。
【図５】図５は画像センサ、画像センサの視野および異なる二箇所に位置している人の側面図を示す。
【図６】図６は本発明の一つの実施形態による、群衆のvisual hullの平面投影に基づいた群集の人数を決定するための装置のブロック図を示す。
【図７】図７は図６に示されたメモリユニットの内容を示すより詳細なブロック図である。
【図８】図８は本発明の一つの実施形態による群衆の人数を決定する方法を示す。
【図９】図９は２台の画像センサ、一つの対象物およびその対象物のシルエットコーンを示す上面図である。
【図１０Ａ】図１０Ａは対象物無しの２台の画像センサおよび投影シルエットコーンの上面図を示す。
【図１０Ｂ】図１０Ｂは図１０Ａの投影されたシルエットコーンと、第一のコンフィギュレーションにおける多数の対象物を示す上面図である。
【図１０Ｃ】図１０Ｃは図１０Ａの投影されたシルエットコーンと、第二のコンフィギュレーションにおける多数の対象物を示す上面図である。
【図１０Ｄ】図１０Ｄは図１０Ａの投影されたシルエットコーンと、第三のコンフィギュレーションにおける多数の対象物を示す上面図である。
【図１０Ｅ】図１０Ｅは図１０Ａの投影されたシルエットコーンと、第四のコンフィギュレーションにおける多数の対象物を示す上面図である。
【図１１】図１１は、本発明の一つの実施形態による、群集のvisual hullの平面投影を決定するために、従来の群集の画像を利用する方法を示す。
【図１２Ａ】図１２Ａは３台のセンサ、それらの投影シルエットコーンおよび多数の対象物を示す上面図である。
【図１２Ｂ】図１２Ｂは３台のセンサ、それらの投影シルエットコーン、多数の対象物および幻影の多角形を示す上面図である。
【図１３】図１３は本発明の一つの実施形態によるツリーデータ構造のダイアグラムを示す。
【特許請求の範囲】
【請求項１】
動作容積内の対象物の数を決定する方法であって、
シルエットコーンと前記動作容積との交差領域である三次元形状の第一の複数の平面投影を交差させることにより、一つ以上の多角形からなる第一の集合を決定するステップと、
一つ以上の多角形からなる前記第一の集合の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最低の数である一つ以上の下限からなる第一の集合を決定するステップとからなる方法。
【請求項２】
前記動作容積のシルエットコーンの前記第一の複数の平面投影を交差させることは、前記動作容積のシルエットコーンの平面投影の画素化からなることを特徴とする請求項１の方法。
【請求項３】
前記動作容積のシルエットコーンの平面投影の画素化は、前記動作容積のシルエットコーンの平面投影を画素化するためのハードウェアを使用することからなることを特徴とする請求項２の方法。
【請求項４】
前記動作容積は全ての対象物を完全には含まないことを特徴とする請求項１の方法。
【請求項５】
一つ以上の下限からなる前記第一の集合を決定するステップは、シルエットコーンに沿って伸び、一つの多角形とだけ交差する光線が存在するかの決定からなることを特徴とする請求項１の方法。
【請求項６】
一つ以上の多角形が対象物を含まないと決定したことに対応して、一つ以上の多角形からなる前記第一の集合から一つ以上の多角形を除外するステップをさらに含む請求項１の方法。
【請求項７】
一つ以上の多角形からなる前記第一の集合内の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最高の数である上限を一つ以上含む第一の集合を決定するステップをさらに含む請求項１の方法。
【請求項８】
一つ以上の上限からなる前記第一の集合を決定するステップは、多角形の面積を最小の対象物の寸法で分割することからなることを特徴とする請求項７の方法。
【請求項９】
一つ以上の下限からなる前記第一の集合をデータ構造に保存するステップと、
シルエットコーンと前記動作容積との交差領域である三次元形状の第二の複数の平面投影を交差させることにより、一つ以上の多角形からなる第二の集合を決定するステップと、
一つ以上の多角形からなる前記第二の集合内の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最低の数である下限を一つ以上含む第二の集合を決定するステップとをさらに含む請求項１の方法。
【請求項１０】
前記動作容積のシルエットコーンの前記第二の複数の平面投影を交差させることは、前記動作容積のシルエットコーンの平面投影の画素化からなることを特徴とする請求項０の方法。
【請求項１１】
前記動作容積のシルエットコーンの平面投影の画素化は、前記動作容積のシルエットコーンの平面投影を画素化するためのハードウェアを使用することからなることを特徴とする請求項０の方法。
【請求項１２】
前記動作容積は全ての対象物を完全には含まないことを特徴とする請求項０の方法。
【請求項１３】
一つ以上の下限からなる前記第二の集合を決定するステップは、シルエットコーンに沿って伸び、一つの多角形とだけ交差する光線が存在するかの決定からなることを特徴とする請求項０の方法。
【請求項１４】
一つ以上の多角形が対象物を含まないと決定したことに対応して、一つ以上の多角形からなる前記第二の集合から一つ以上の多角形を除外するステップをさらに含む請求項０の方法。
【請求項１５】
一つ以上の多角形からなる前記第二の集合内の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最高の数である上限を一つ以上含む第二の集合を決定するステップをさらに含む請求項０の方法。
【請求項１６】
一つ以上の上限からなる前記第二の集合を決定するステップは、多角形の面積を最小の対象物の寸法で分割することからなることを特徴とする請求項０の方法。
【請求項１７】
前記データ構造を更新するステップをさらに含む請求項０の方法。
【請求項１８】
前記データ構造はツリーデータ構造からなり、該ツリーデータ構造のノードは一つ以上の多角形からなる前記第一の集合に含まれる一つの多角形に関連付けられることを特徴とする請求項０の方法。
【請求項１９】
前記ツリーデータ構造のノードは前記関連付けられた多角形の下限からなることを特徴とする請求項０の方法。
【請求項２０】
前記ツリーデータ構造のノードは前記関連付けられた多角形の上限からなることを特徴とする請求項０の方法。
【請求項２１】
前記データ構造の更新は、前記データ構造にノードを加えるステップと、
前記データ構造から重複するノードを除去するステップと、
前記データ構造のノードを更新するステップとからなることを特徴とする請求項０の方法。
【請求項２２】
動作容積内の対象物の数を決定するシステムであって、
シルエットコーンと前記動作容積との交差領域である三次元形状の第一の複数の平面投影を交差させることにより、一つ以上の多角形からなる第一の集合を決定する手段と、
一つ以上の多角形からなる前記第一の集合の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最低の数である一つ以上の下限からなる第一の集合を決定する手段とからなるシステム。
【請求項２３】
前記動作容積のシルエットコーンの前記第一の複数の平面投影を交差させることは、前記動作容積のシルエットコーンの平面投影の画素化からなること特徴とする請求項２２のシステム。
【請求項２４】
前記動作容積のシルエットコーンの平面投影の画素化は、前記動作容積のシルエットコーンの平面投影を画素化するためのハードウェアを使用することからなることを特徴とする請求項２３のシステム。
【請求項２５】
前記動作容積は全ての対象物を完全には含まないことを特徴とする請求項２２のシステム。
【請求項２６】
一つ以上の下限からなる前記第一の集合を決定する手段は、シルエットコーンに沿って伸び、一つの多角形とだけ交差する光線が存在するか決定する手段からなることを特徴とする請求項２２のシステム。
【請求項２７】
一つ以上の多角形が対象物を含まないと決定したことに対応して、一つ以上の多角形からなる前記第一の集合から一つ以上の多角形を除外する手段をさらに含む請求項２２のシステム。
【請求項２８】
一つ以上の多角形からなる前記第一の集合内の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最高の数である上限を一つ以上含む第一の集合を決定する手段をさらに含む請求項２２のシステム。
【請求項２９】
一つ以上の上限からなる前記第一の集合を決定する手段は、多角形の面積を最小の対象物の寸法で分割する手段からなることを特徴とする請求項２８のシステム。
【請求項３０】
一つ以上の下限からなる前記第一の集合をデータ構造に保存する手段と、
シルエットコーンと前記動作容積との交差領域である三次元形状の第二の複数の平面投影を交差させることにより、一つ以上の多角形からなる第二の集合を決定する手段と、
一つ以上の多角形からなる前記第二の集合内の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最低の数である下限を一つ以上含む第二の集合を決定する手段とをさらに含む請求項２２のシステム。
【請求項３１】
前記動作容積のシルエットコーンの前記第二の複数の平面投影を交差させることは、前記動作容積のシルエットコーンの平面投影の画素化からなることを特徴とする請求項３０のシステム。
【請求項３２】
前記動作容積のシルエットコーンの平面投影の画素化は、前記動作容積のシルエットコーンの平面投影を画素化するためのハードウェアを使用することからなることを特徴とする請求項３１のシステム。
【請求項３３】
前記動作容積は全ての対象物を完全には含まないことを特徴とする請求項３０のシステム。
【請求項３４】
一つ以上の下限からなる前記第二の集合を決定する手段は、シルエットコーンに沿って伸び、一つの多角形とだけ交差する光線が存在するかを決定する手段からなることを特徴とする請求項３０のシステム。
【請求項３５】
一つ以上の多角形が対象物を含まないと決定したことに対応して、一つ以上の多角形からなる前記第二の集合から一つ以上の多角形を除外する手段をさらに含む請求項３０のシステム。
【請求項３６】
一つ以上の多角形からなる前記第二の集合内の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最高の数である上限を一つ以上含む第二の集合を決定する手段をさらに含む請求項３０のシステム。
【請求項３７】
一つ以上の上限からなる前記第二の集合を決定する手段は、多角形の面積を最小の対象物の寸法で分割する手段からなることを特徴とする請求項３６のシステム。
【請求項３８】
前記データ構造を更新する手段をさらに含む請求項３０のシステム。
【請求項３９】
前記データ構造はツリーデータ構造からなり、該ツリーデータ構造のノードは一つ以上の多角形からなる前記第一の集合に含まれる一つの多角形に関連付けられることを特徴とする請求項３８のシステム。
【請求項４０】
前記ツリーデータ構造のノードは前記関連付けられた多角形の下限からなることを特徴とする請求項３９のシステム。
【請求項４１】
前記ツリーデータ構造のノードは前記関連付けられた多角形の上限からなることを特徴とする請求項３９のシステム。
【請求項４２】
前記データ構造を更新する手段は、前記データ構造にノードを加える手段と、
前記データ構造から重複するノードを除去する手段と、
前記データ構造のノードを更新する手段とからなることを特徴とする請求項３９のシステム。
【請求項１】
動作容積内の対象物の数を決定する方法であって、
シルエットコーンと前記動作容積との交差領域である三次元形状の第一の複数の平面投影を交差させることにより、一つ以上の多角形からなる第一の集合を決定するステップと、
一つ以上の多角形からなる前記第一の集合の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最低の数である一つ以上の下限からなる第一の集合を決定するステップとからなる方法。
【請求項２】
前記動作容積のシルエットコーンの前記第一の複数の平面投影を交差させることは、前記動作容積のシルエットコーンの平面投影の画素化からなることを特徴とする請求項１の方法。
【請求項３】
前記動作容積のシルエットコーンの平面投影の画素化は、前記動作容積のシルエットコーンの平面投影を画素化するためのハードウェアを使用することからなることを特徴とする請求項２の方法。
【請求項４】
前記動作容積は全ての対象物を完全には含まないことを特徴とする請求項１の方法。
【請求項５】
一つ以上の下限からなる前記第一の集合を決定するステップは、シルエットコーンに沿って伸び、一つの多角形とだけ交差する光線が存在するかの決定からなることを特徴とする請求項１の方法。
【請求項６】
一つ以上の多角形が対象物を含まないと決定したことに対応して、一つ以上の多角形からなる前記第一の集合から一つ以上の多角形を除外するステップをさらに含む請求項１の方法。
【請求項７】
一つ以上の多角形からなる前記第一の集合内の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最高の数である上限を一つ以上含む第一の集合を決定するステップをさらに含む請求項１の方法。
【請求項８】
一つ以上の上限からなる前記第一の集合を決定するステップは、多角形の面積を最小の対象物の寸法で分割することからなることを特徴とする請求項７の方法。
【請求項９】
一つ以上の下限からなる前記第一の集合をデータ構造に保存するステップと、
シルエットコーンと前記動作容積との交差領域である三次元形状の第二の複数の平面投影を交差させることにより、一つ以上の多角形からなる第二の集合を決定するステップと、
一つ以上の多角形からなる前記第二の集合内の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最低の数である下限を一つ以上含む第二の集合を決定するステップとをさらに含む請求項１の方法。
【請求項１０】
前記動作容積のシルエットコーンの前記第二の複数の平面投影を交差させることは、前記動作容積のシルエットコーンの平面投影の画素化からなることを特徴とする請求項０の方法。
【請求項１１】
前記動作容積のシルエットコーンの平面投影の画素化は、前記動作容積のシルエットコーンの平面投影を画素化するためのハードウェアを使用することからなることを特徴とする請求項０の方法。
【請求項１２】
前記動作容積は全ての対象物を完全には含まないことを特徴とする請求項０の方法。
【請求項１３】
一つ以上の下限からなる前記第二の集合を決定するステップは、シルエットコーンに沿って伸び、一つの多角形とだけ交差する光線が存在するかの決定からなることを特徴とする請求項０の方法。
【請求項１４】
一つ以上の多角形が対象物を含まないと決定したことに対応して、一つ以上の多角形からなる前記第二の集合から一つ以上の多角形を除外するステップをさらに含む請求項０の方法。
【請求項１５】
一つ以上の多角形からなる前記第二の集合内の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最高の数である上限を一つ以上含む第二の集合を決定するステップをさらに含む請求項０の方法。
【請求項１６】
一つ以上の上限からなる前記第二の集合を決定するステップは、多角形の面積を最小の対象物の寸法で分割することからなることを特徴とする請求項０の方法。
【請求項１７】
前記データ構造を更新するステップをさらに含む請求項０の方法。
【請求項１８】
前記データ構造はツリーデータ構造からなり、該ツリーデータ構造のノードは一つ以上の多角形からなる前記第一の集合に含まれる一つの多角形に関連付けられることを特徴とする請求項０の方法。
【請求項１９】
前記ツリーデータ構造のノードは前記関連付けられた多角形の下限からなることを特徴とする請求項０の方法。
【請求項２０】
前記ツリーデータ構造のノードは前記関連付けられた多角形の上限からなることを特徴とする請求項０の方法。
【請求項２１】
前記データ構造の更新は、前記データ構造にノードを加えるステップと、
前記データ構造から重複するノードを除去するステップと、
前記データ構造のノードを更新するステップとからなることを特徴とする請求項０の方法。
【請求項２２】
動作容積内の対象物の数を決定するシステムであって、
シルエットコーンと前記動作容積との交差領域である三次元形状の第一の複数の平面投影を交差させることにより、一つ以上の多角形からなる第一の集合を決定する手段と、
一つ以上の多角形からなる前記第一の集合の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最低の数である一つ以上の下限からなる第一の集合を決定する手段とからなるシステム。
【請求項２３】
前記動作容積のシルエットコーンの前記第一の複数の平面投影を交差させることは、前記動作容積のシルエットコーンの平面投影の画素化からなること特徴とする請求項２２のシステム。
【請求項２４】
前記動作容積のシルエットコーンの平面投影の画素化は、前記動作容積のシルエットコーンの平面投影を画素化するためのハードウェアを使用することからなることを特徴とする請求項２３のシステム。
【請求項２５】
前記動作容積は全ての対象物を完全には含まないことを特徴とする請求項２２のシステム。
【請求項２６】
一つ以上の下限からなる前記第一の集合を決定する手段は、シルエットコーンに沿って伸び、一つの多角形とだけ交差する光線が存在するか決定する手段からなることを特徴とする請求項２２のシステム。
【請求項２７】
一つ以上の多角形が対象物を含まないと決定したことに対応して、一つ以上の多角形からなる前記第一の集合から一つ以上の多角形を除外する手段をさらに含む請求項２２のシステム。
【請求項２８】
一つ以上の多角形からなる前記第一の集合内の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最高の数である上限を一つ以上含む第一の集合を決定する手段をさらに含む請求項２２のシステム。
【請求項２９】
一つ以上の上限からなる前記第一の集合を決定する手段は、多角形の面積を最小の対象物の寸法で分割する手段からなることを特徴とする請求項２８のシステム。
【請求項３０】
一つ以上の下限からなる前記第一の集合をデータ構造に保存する手段と、
シルエットコーンと前記動作容積との交差領域である三次元形状の第二の複数の平面投影を交差させることにより、一つ以上の多角形からなる第二の集合を決定する手段と、
一つ以上の多角形からなる前記第二の集合内の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最低の数である下限を一つ以上含む第二の集合を決定する手段とをさらに含む請求項２２のシステム。
【請求項３１】
前記動作容積のシルエットコーンの前記第二の複数の平面投影を交差させることは、前記動作容積のシルエットコーンの平面投影の画素化からなることを特徴とする請求項３０のシステム。
【請求項３２】
前記動作容積のシルエットコーンの平面投影の画素化は、前記動作容積のシルエットコーンの平面投影を画素化するためのハードウェアを使用することからなることを特徴とする請求項３１のシステム。
【請求項３３】
前記動作容積は全ての対象物を完全には含まないことを特徴とする請求項３０のシステム。
【請求項３４】
一つ以上の下限からなる前記第二の集合を決定する手段は、シルエットコーンに沿って伸び、一つの多角形とだけ交差する光線が存在するかを決定する手段からなることを特徴とする請求項３０のシステム。
【請求項３５】
一つ以上の多角形が対象物を含まないと決定したことに対応して、一つ以上の多角形からなる前記第二の集合から一つ以上の多角形を除外する手段をさらに含む請求項３０のシステム。
【請求項３６】
一つ以上の多角形からなる前記第二の集合内の一つの多角形と関連付けられ、関連付けられた多角形に包含され得る対象物の最高の数である上限を一つ以上含む第二の集合を決定する手段をさらに含む請求項３０のシステム。
【請求項３７】
一つ以上の上限からなる前記第二の集合を決定する手段は、多角形の面積を最小の対象物の寸法で分割する手段からなることを特徴とする請求項３６のシステム。
【請求項３８】
前記データ構造を更新する手段をさらに含む請求項３０のシステム。
【請求項３９】
前記データ構造はツリーデータ構造からなり、該ツリーデータ構造のノードは一つ以上の多角形からなる前記第一の集合に含まれる一つの多角形に関連付けられることを特徴とする請求項３８のシステム。
【請求項４０】
前記ツリーデータ構造のノードは前記関連付けられた多角形の下限からなることを特徴とする請求項３９のシステム。
【請求項４１】
前記ツリーデータ構造のノードは前記関連付けられた多角形の上限からなることを特徴とする請求項３９のシステム。
【請求項４２】
前記データ構造を更新する手段は、前記データ構造にノードを加える手段と、
前記データ構造から重複するノードを除去する手段と、
前記データ構造のノードを更新する手段とからなることを特徴とする請求項３９のシステム。
【図１】
【図２Ａ】
【図２Ｂ】
【図３Ａ】
【図３Ｂ】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１０Ｃ】
【図１０Ｄ】
【図１０Ｅ】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１３】
【図２Ａ】
【図２Ｂ】
【図３Ａ】
【図３Ｂ】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１０Ｃ】
【図１０Ｄ】
【図１０Ｅ】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１３】
【公表番号】特表２００７−５１７２７３（Ｐ２００７−５１７２７３Ａ）
【公表日】平成１９年６月２８日（２００７．６．２８）
【国際特許分類】
【出願番号】特願２００６−５３３７８０（Ｐ２００６−５３３７８０）
【出願日】平成１６年６月１４日（２００４．６．１４）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０１８８４２
【国際公開番号】ＷＯ２００４／１１１７９９
【国際公開日】平成１６年１２月２３日（２００４．１２．２３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（０００００５３２６）本田技研工業株式会社 (23,863)
【Ｆターム（参考）】
【公表日】平成１９年６月２８日（２００７．６．２８）
【国際特許分類】
【出願日】平成１６年６月１４日（２００４．６．１４）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０１８８４２
【国際公開番号】ＷＯ２００４／１１１７９９
【国際公開日】平成１６年１２月２３日（２００４．１２．２３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（０００００５３２６）本田技研工業株式会社 (23,863)
【Ｆターム（参考）】
[ Back to top ]