目標が位置する空間エリアを決定する方法、装置およびシステム
【課題】 目標が位置する空間エリアを決定するための方法、装置およびシステムを提案する。
【解決手段】 目標が位置する空間エリアを決定するための方法は、 複数のキーポイント位置点によって特徴付けられる１つ以上の空間エリアを含む空間内の目標の位置パラメータを受信するステップと、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定するステップを含む。空間エリアを特徴付ける方法は、空間エリア内の一連の位置点を取得するステップと、一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出するステップとを含む。
【解決手段】 目標が位置する空間エリアを決定するための方法は、 複数のキーポイント位置点によって特徴付けられる１つ以上の空間エリアを含む空間内の目標の位置パラメータを受信するステップと、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定するステップを含む。空間エリアを特徴付ける方法は、空間エリア内の一連の位置点を取得するステップと、一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出するステップとを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、本発明は位置情報処理の分野に関し、特に空間エリアを特徴付けて目標が位置する空間エリアを決定する方法、装置およびシステムに関する。
【背景技術】
【０００２】
ロケーション情報は、ユーザと環境間の地理的関係を特定する際に利用できる基本的なコンテキスト情報であり、これによりユーザの行動をより深く理解することが可能になる。
近年、位置情報を提供する方法とシステムは、ますます多くの注目を集めてきている。特に、位置情報を提供する方およびシステムは、室内の環境および市街地の環境にとってより一層必要とされている。
【０００３】
現在、多種多様な適用情況、例えば、オフィス、医療機関、鉱山、地下鉄、スマートビルディング、あるいはホテル等のような環境において、リアルタイムで正確な位置追跡に対する要求はますます高まってきている。
多くの位置情報に基づいた用途においては、多くの場合、空間を空間エリアあるいは空間グリッドと呼ばれる複数のエリアに区分けし、目標が空間内のどの空間エリアに位置するかを判定することが必要となる。
例えば、商品棚の情報推薦用途においては、棚上の商品がそれぞれ商品に対応する空間エリアに位置すると仮定することができる。そして、目標がその空間エリアに入る時（例えば、目標が一定の商品に接近する時）、空間エリアのモデルに基づいて、目標がどの空間エリアに入るかを決定することが必要である。その結果として、空間エリアに対応する商品に関する情報を顧客に推薦することが可能となる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】パターン分類（セカンドエディション）、１０章、５１７−５９９ページＲ．Ｏ．デューダ、Ｐ．Ｅ．ハート、Ｄ．Ｇ．ストーク、ＩＳＢＮ：０−４７１−０５６６９−３（Pattern Classification (Second Edition), Chapter 10, pp. 517-599, R.O. Duda, P. E. Hart, and D. G. Stork, ISBN:0-471-05669-3）」
【発明の概要】
【発明が解決しようとする課題】
【０００５】
これまで、空間エリアを特徴付け、目標がある一空間エリア内に位置するかどうかを決定するためのいくつかの方法が提案されている。
しかしながら、関連技術によるこれらの方法には少なからず限界がある。例えば、空間エリアのモデリングあるいは空間エリアを特徴付ける処理は余りに複雑過ぎするし、計算コストもかかり過ぎる。さらに、近隣の空間エリアを効率的にかつ迅速に区別することが難しいため、正確性が非常に低くなる。
【０００６】
このため、便利で、迅速かつ正確に、空間エリアを特徴付けて目標が位置する空間エリアを決定することができる技術的解決方法がこの技術分野において特に必要となっている。
【課題を解決するための手段】
【０００７】
本発明の目的は、空間内の空間エリアを特徴付けるための技術的解決方法を提供することにある。
【０００８】
本発明の他の目的は、目標が空間のどの空間エリアに位置するかを決定するための技術的解決方法を提供することにある。
【０００９】
本発明による第２の方法は、空間エリア内の一連の位置点を取得するステップと、一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出するステップとを含む。
【００１０】
本発明による第２の装置は、空間エリア内の一連の位置点を取得する取得手段と、一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出する抽出手段とを含む。
【００１１】
本発明によるシステムは、複数のキーポイント位置点によって特徴付けられる１つ以上の空間エリアを含む空間内の目標の配置され、測距信号を発信するように構成された信号発信器と、信号発信器から発信された測距信号に基づいて目標の位置パラメータを取得するように構成された測位装置（ＰＯＤ）と、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定するように構成されたサーバとを含む。
【発明の効果】
【００１２】
本発明によれば、簡単な処理で空間内の空間エリアを特徴付けることができる方法を実現する。
また、本発明によれば、効率的にかつ迅速に目標が空間のどの空間エリアに位置するかを決定することが可能になる。
【００１３】
本発明の他の特徴と利点は、添付図面を参照する好適な実施の形態によって明らかとなるであろう。
【図面の簡単な説明】
【００１４】
他の目的および本発明の効果は、添付図面を参照した詳細な説明の記述によって、本発明の好適な実施の形態についてのより総合的な理解をもってより明らとなり、かつ容易に理解できるであろう。
【図１】複数の空間エリアを含む空間の概略図である。
【図２ａ】関連技術に従った空間エリアの特徴付けを示す概略図である。
【図２ｂ】本発明の実施の形態による空間エリアの特徴付けを示す概略図である。
【図３】本発明の実施の形態による空間内の空間エリアを特徴付けるシステムの構成を示すブロック図である。
【図４】本発明の実施の形態による空間内の空間エリアを特徴付ける方法を説明するフローチャートである。
【図５】本発明の実施の形態によるキーポイント位置点を抽出する方法を説明するフローチャートである。
【図６】本発明の他の実施の形態によるキーポイント位置点を抽出する方法を説明するフローチャートである。
【図７】本発明の実施の形態による空間エリアを決定するシステムの構成を示すブロック図である。
【図８】本発明の実施の形態による空間エリアを決定する方法を説明するフローチャートである。
【図９】本発明の実施の形態による目標が位置する空間エリアを決定する方法を説明するフローチャートである。
【図１０】本発明の他の実施の形態による目標が位置する空間エリアを決定する方法を説明するフローチャートである。
【図１１】本発明の他の実施の形態による空間内の空間エリアを特徴付けかつ決定するシステムの構成を示すブロック図である。
【発明を実施するための形態】
【００１５】
まず、本発明の好ましい実施の形態において使用される専門用語について簡単に説明する。
【００１６】
１． 空間および空間エリア
本発明による空間は、目標が移動することができる空間であり、例えば、部屋、オフィス、会議室などである。図１は、複数の空間エリアを含む空間１００を示す概略図である。
【００１７】
本発明による空間エリアは、空間に含まれるエリアの一部を指す。図２ａ及び図２ｂは、空間エリア２１０と空間エリア２２０を示す概略図である。本発明による空間エリアが、図２ａと図２ｂに示されるような立方体に限定されず、例えば、直方体、球、不規則な形状などのあらゆる形状を取りうることを理解すべきである。
さらに、空間が１つ以上の空間エリアを含む場合があること、また、空間エリアが図１に示すように互いにオーバーラップの無い独立した空間部分か、あるいは互いにオーバーラップ部分を有する空間部分でもよいことを理解すべきである。
【００１８】
通常、目標がどの空間エリアに存在しているかを認識するためには、空間エリアのモデルを認識しなければならない。すなわち、空間エリアをどのように特徴付けるかを認識していることが必要である。本発明の実施の形態によって、空間エリアを特徴付けるのための技術的方法を提供する。以下にその詳細を説明する。
【００１９】
２．位置点およびキーポイントとなる位置点
本発明による位置点は、空間エリア２２０（例えば、図２ｂに示す空間エリア２２０）内の点であり、空間エリア２２０は複数の位置点２２１を含んでいる。位置点は、空間内の位置点の三次元の座標である対応する位置パラメータを有していてもよい。
【００２０】
キーポイントとなる位置点２２２は、空間エリアを特徴付けるのための位置点である。キーポイントとなる位置点は、空間エリア内のいかなる位置点あるいは空間エリア上のいかなる位置点でもよい。
例えば、図２ｂに示す空間エリア２２０において、空間エリア２２０は複数の位置点２２１を有するだけでなく、空間エリアを特徴付けるためにそれらの位置点から選択されたキーポイントとなる位置点２２２を有する。
原則的に、それが空間を特徴付けることができる限り、空間内のいかなる点もキーポイントとなる位置点として選択することが可能である。
通常は、空間エリアのモデルを取得するためには、空間エリアを特徴付けるためのキーポイントとなる位置点を認識していることが必要である。
本発明の実施の形態によれば、キーポイントとなる位置点の抽出を通して空間エリアを特徴付けるのための技術的方法が提供され、以下にその詳細を説明する。
【００２１】
３．信号発信器
本発明の好ましい実施の形態における信号発信器は、測距信号を発信することができる装置を指しており、例えば、ＲＦ信号発信器である。
本発明の実施の形態において、信号発信器は空間内の目標に配置することが可能である。例えば、信号発信器は、目標の信号発信器から発信される測距信号を受信する測位装置（ＰＯＤ）によって目標の位置パラメータを取得するために、タグの形で目標に付与される。
測距信号としては様々な形式の信号を利用することが可能である。例えば、超音波、赤外線、レーザ、ＲＦ信号、超広帯域パルス信号、ドップラー信号および音波等を含むが、これらに限定されない。
なお、ＰＯＤと信号発信器によって目標の位置パラメータを決定することは本発明の技術分野においては広く知られているので、その詳細は省略する。
【００２２】
４．測位装置（ＰＯＤ：Positioning on
One Device）
本発明の実施の形態によるＰＯＤは、目標の位置パラメータを取得するための装置である。
好ましい実施の形態において、本発明に採用されるＰＯＤは、複数の葉ノードを有するセンサアレイである。葉ノードの数は少なくとも２である。言いかえれば、ＰＯＤは、少なくとも２つの葉ノードセンサとその間に配列された１つのセンサを含む。通常、より多くの葉ノードがあると、測位精度はより高くなる。
具体的な適用例においては、ＰＯＤは、通常、空間１００の一番上に配置され、空間１００内の目標の信号発信器から発信された測距信号を受信する。
目標の位置パラメータは、測距信号およびＰＯＤそれ自体の位置パラメータに基づいて決定することができる。
【００２３】
以下に、本発明の好適な実施の形態について、添付図面を参照して説明する。これらの実施の形態は例として説明するものであり、本発明の範囲を制限するものではない。
【００２４】
まず、空間エリアを特徴付けて目標が位置する空間エリアを決定するこれまでの関連技術による方法について説明する。
【００２５】
図２ａは、関連技術による空間エリアを特徴付ける方法を示す略図である。図２ａに示すような空間エリアを特徴付ける方法において、ユーザは信号発信器を使用し空間エリアの境界に沿って移動し、その間に信号発信器から発された測距信号をＰＯＤによって受信する。
空間エリアの境界に沿って移動する信号発信器の位置パラメータは測距信号とＰＯＤそれ自体の位置パラメータに基づいて決定され、その結果として、空間エリアの境界の位置パラメータが取得される。
その後、空間エリアの一連の頂点が多角形フィッティングアルゴリズムを使用することによって取得され、また、一連の頂点は空間エリアを特徴付けるために空間エリアのモデルとして利用される。
【００２６】
目標が位置する空間エリアを決定する関連技術の方法では、目標の信号発信器が空間内の異なる空間エリアに移動すると、その間に信号発信器から発信された測距信号をＰＯＤによって受信する。
測距信号とＰＯＤそれ自体の位置パラメータに基づいて、目標の位置パラメータを決定する。そして、目標がどの空間エリアに位置するか決定するために、目標の位置パラメータを全ての空間エリアのモデルと比較する。
【００２７】
しかしながら、関連技術には多くの問題点がある。
第１に、目標が信号発信器と共に空間エリアの境界に沿って厳密に移動することを要求されるため、関連技術は空間エリアを特徴付けるために複雑なプロセスを必要とする。
なおかつ、空間エリアの形が不規則である場合、信号発信器を備えた目標が空間エリアの境界に沿って厳密に移動するのは困難である。
第２に、目標が位置する空間エリアを決定する処理において、２つの空間エリアが緊密に隣接する時に、目標が２つの空間エリア間で移動する時、目標が正確にどの空間エリアを位置するか決定するのは困難であろう。
【００２８】
図２ｂは、本発明の好適な実施の形態による空間エリアを特徴付ける方法を示す略図である。
好適な実施の形態によれば、空間エリアを特徴付ける処理の間、目標が信号発信器と共に空間エリアの境界に沿って厳密に移動することは不要である。
それどころか、空間エリアの任意の一連の位置点を取得するだけで、キーポイントとなる位置点を空間エリアを特徴付けるために抽出することが可能である。
以下、図３から図６に示す実施の形態は、本発明による空間部の空間エリアを特徴付ける方法を詳細に説明する。
【００２９】
図３は、本発明の好適な実施の形態による空間内の空間エリアを特徴付けるためのシステム３００のブロック図を示す。
図３に示されるように、空間内の空間エリアを特徴付けるためのシステム３００は、信号発信器３１０と、測位装置（ＰＯＤ）３２０と、サーバ３００とを含む。
信号発信器３１０は、測距信号を発信するように構成され、一連の位置点内の位置点に配置される。一連の位置点内の位置点の位置パラメータは、信号発信器から測位装置（ＰＯＤ）へ測距信号を発信することにより取得される。
測位装置（ＰＯＤ）３２０は、信号発信器からの測距信号に基づいて信号発信器が位置する位置点の位置パラメータを取得するように構成される。
サーバ３３０は、空間エリア特徴付け装置３４０を含む。
【００３０】
以下に、システム３００の実現例について詳細に説明する。
具体的には、本発明の好適な実施の形態によれば、一連の位置点（図２ｂに示すように一点鎖線でつながる一連の位置点）が、まず空間エリア内で決定される。
本発明の実施の形態においては、一連の位置点は、空間エリア内で信号発信器をランダムに移動させることにより決定され、あるいは、空間エリア内に複数の位置点を予め設定することにより決定される。
本発明における一連の位置点は、関連技術のように空間エリアの境界に沿って厳密に移動することによって取得する必要が無く、空間エリア内の任意の位置点を含むことに留意すべきである。
本発明の実施の形態において、信号発信器は、一連の位置点の各位置点にそれぞれ配置され、これにより、位置点の位置パラメータが取得される。
位置点の位置パラメータを取得するため、一連の位置点内の異なる位置点にも同じ信号発信器が配置される。
一例では、サーバ３３０が、信号発信器３１０から発信された測距信号と測距信号を受信するＰＯＤ３２０自身の位置パラメータに基づいて、一連の位置点内の各位置点の位置パラメータを決定する。
他の例では、ＰＯＤ３２０が、信号発信器３１０から発された測距信号と信号発信器それ自体の位置パラメータに基づいて、一連の位置点内の各位置点の位置パラメータを決定する。
信号発信器３１０自体は、本技術分野において広く知られているので、ここでは詳しく説明しない。
【００３１】
次に、ＰＯＤ３２０は、空間にセットされる。ＰＯＤ３２０は、空間内のどのような箇所にも設置することが可能である。
例えば、ＰＯＤ３２０を空間の上部に配置することができ、その初期の配置箇所は任意である。すなわち、空間の上部のどのような箇所にも配置することが可能である。
一例では、サーバ３３０内の空間エリア特徴付け装置３４０が、信号発信器３１０から発信された測距信号と測距信号を受信するＰＯＤ３２０自身の位置パラメータに基づいて一連の位置点内の各位置点の位置パラメータを決定するために、ＰＯＤ３２０は、信号発信器３１０から測距信号を受信し、その測距信号とＰＯＤ３２０自身の位置パラメータをサーバに対して送信する。
他の例においては、ＰＯＤ３２０が、信号発信器３１０から発された測距信号と信号発信器それ自体の位置パラメータに基づいて一連の位置点内の各位置点の位置パラメータを決定する。
【００３２】
信号発信器３１０の配置とＰＯＤ３２０の配置の間に前後関係がないことを理解すべきである。
それらを両方とも同時に配置することも可能であるし、あるいは、ＰＯＤ３２０を最初に配置し、次に、信号発信器３１０を空間の空間特徴点に配置することも可能である。
【００３３】
その後、本発明の実施の形態によれば、サーバ３３０の空間エリア特徴付け装置３４０は、信号発信器３１０から発信された測距信号と測距信号を受信するＰＯＤ３２０自体の位置パラメータに基づいて、空間全体について空間エリア内の一連の位置点内の位置点の位置パラメータを算出する。
例えば、位置パラメータは、空間内の位置点の座標（ｘ、ｙ、ｚ）である。
その後、空間エリア特徴付け装置３４０は、一連の位置点内の位置点の位置パラメータを使用して、空間エリアを特徴付けるキーポイント位置点を抽出し、それにより、空間エリアのモデルを確立する。
【００３４】
本発明の好適な実施の形態によれば、空間エリア特徴付け装置３４０は、空間エリア内の一連の位置点を取得するように構成される取得手段３４１と、空間エリアを特徴付けるために、一連の位置点に基づいてキーポイント位置点を抽出するように構成される抽出手段３４２とを含む。
図４は、本実施の形態による空間エリアを特徴付ける空間エリア特徴付け装置３４０の動作を説明するフローチャートである。
【００３５】
ステップ４０１で、空間エリア内の一連の位置点を取得する。
【００３６】
上述したように、一連の位置点は、空間エリア内でランダムに移動する信号発信器の移動軌跡に基づいて取得することができ、あるいは、空間エリア内に複数の位置点を予め設定することにより取得することができる。
【００３７】
具体的な例では、ユーザが測距信号を発信する信号発信器を所持して空間内をランダムに移動し、そして、信号発信器の移動軌跡をキーポイントとなる位置点を抽出するための一連の位置点として使用することができる。
【００３８】
ステップ４０２で、空間エリアを特徴付けるキーポイント位置点を抽出する。
【００３９】
このステップでは、ステップ４０１から取得された一連の位置点からキーポイントとなる位置点を抽出するために様々な実施方法が利用可能である。
【００４０】
一例として、ステップ４０２は、k-meansクラスタリングアルゴリズム（K-means
clustering algorithm）や、非特許文献１「パターン分類（セカンドエディション）、１０章、５１７−５９９ページＲ．Ｏ．デューダ、Ｐ．Ｅ．ハート、Ｄ．Ｇ．ストーク、ＩＳＢＮ：０−４７１−０５６６９−３（Pattern
Classification (Second Edition), Chapter 10, pp. 517-599, R. O. Duda, P. E.
Hart, and D. G. Stork, ISBN:0-471-05669-3）」に記載されるアルゴリズムで実現することができる。
図５は、k-meansクラスタリングアルゴリズムでキーポイント位置点を抽出するための方法のフローチャートを示す。これについては以下に詳細に説明する。
【００４１】
他の例では、ステップ４０２は、階層的クラスタリングアルゴリズムで実現することができる。図６は、階層的クラスタリングアルゴリズムでキーポイントとなる位置点を抽出するための方法のフローチャートを示す。これについては以下に詳細に説明する。
【００４２】
図５に示すk-meansクラスタリングアルゴリズムでキーポイント位置点を抽出する方法において、空間エリア特徴付け装置３４０は、取得手段３４１と抽出手段３４２を含んでいる。
抽出手段３４２は、一連の位置点内の位置点と所定のキーポイント位置点の間の距離を計算する計算手段（初期の所定のキーポイント位置点は、一連の位置点から選択された１つ以上の位置点である）と、隣接性原理（adjacency principle）に基づいて、位置点を、所定の各キーポイント位置点にグループ化するグループ化手段と、同一の予め定めたキーポイント位置点に属する位置点の位置パラメータの平均を求める平均化手段と、平均値と所定のキーポイント位置点の位置パラメータを比較して、それらの間の差を取得する比較手段とを含む。
平均値と所定のキーポイント位置点の位置パラメータの間の差が所定の値以下である場合、所定の位置点がキーポイント位置点として決定される。
平均値と所定のキーポイント位置点の位置パラメータの間の差が所定の値より大きい場合、所定のキーポイント位置点が平均値と対応する位置点に置き換えられた後、計算手段、グループ化手段、平均化手段および比較手段が起動され、繰り返し実行される。
【００４３】
以下、本実施の形態における空間エリア特徴付け装置３４０の抽出手段３４２の動作フローとについて、図５の各ステップを参照して詳細に説明する。
【００４４】
ステップ５０１で、一連の位置点内の位置点と所定のキーポイント位置点の間の距離を計算する。
【００４５】
一例において、ステップ４０１から得られた一連の位置点は１つ以上の位置点を含む。
各位置点は、位置パラメータ（例えば、位置点の三次元の座標）によって特徴付けられる。
一連の位置点は、L={(xi,yi,zi),
i=1,2,…,N}として示される。ここで、Ｎは、一連の位置点に含まれる位置点の数を示す。
【００４６】
図５に示すようなキーポイントを抽出する実施の形態において、所定のキーポイント位置点が任意の位置点である可能性がある。
所定のキーポイント位置点は、必ずしも空間エリアを特徴付けることができるキーポイント位置点ではなく、一連の位置点からキーポイント位置点を抽出する処理において使用される中間の位置点というだけである。
【００４７】
一例では、１つ以上の初期の所定のキーポイント位置点が予め決められる。あるいは、一連の位置点から１つ以上の位置点が初期の所定のキーポイント位置点として選択される。
初期の所定のキーポイント位置点は、位置パラメータ、例えば、P={(xjP,yjP,zjP),
j=1,…,M}
によって特徴付けられる。ここで、Ｍは、初期の所定のキーポイント位置点の数である。
【００４８】
一連の位置点内の各位置点からＭ個の各所定のキーポイント位置点までの間の距離は、ユークリッド距離あるいは当該技術分野における当業者にとって既知の他の方法を使用することにより計算することができる。
【００４９】
ユークリッド距離に対する計算式は以下の通りである。
【数１】
ここで、dijは、一連の位置点におけるｉ番目（ｉ＝１、２、・・・、Ｎ）の位置点(xi,yi,zi)からｊ番目（ｊ＝１、・・・、Ｍ）の所定のキーポイント位置点((xjP,yjP,zjP))までの間の距離である。
【００５０】
ステップ５０１の終了後、一連の位置点内の各位置点と各所定のキーポイント位置点の間の距離行列dijが得られる。ここで、i=1,2,…,N 及びj=1,…,Mである。
【数２】
【００５１】
ステップ５０２で、位置点を、隣接性原理（adjacency
principle）に基づいて各所定のキーポイント位置点にグループ化する。
【００５２】
このステップにおける隣接性原理は、その位置が位置点に対して最も接近している所定のキーポイント位置点を決定することを指す。
例えば、一連の位置点内のｉ番目の位置点(xi,yi,zi)に対する所定のキーポイント位置点は、以下の方法で決定することができる。
まず、一連の位置点内のｉ番目の位置点(xi,yi,zi)と予め定められた各キーポイント位置点の間の距離を、ステップ５０１での計算結果に基づいて取得する。
例えば、例えば、距離行列（２）におけるｉ行は、Ｍ個の値(di1，di2，…diM)を含む。
Ｍ個の値をソートすることにより、最小値を取得する。例えば、dik
ここで、ｋは、Ｍ個の予め定めたキーポイント位置点のｋ番目を表わす。
その後、一連の位置点内のｉ番目の位置点(xi,yi,zi)を、ｋ番目の予め定めたキーポイント位置点にグループ化する。
【００５３】
以上の方法によって、一連の位置点内の全ての位置点は、隣接性原理に基づいて対応する予め定めたキーポイント位置点にグループ化される。
これにより、Ｍ個のグループを取得することができる。また、各グループは少なくとも１つの予め定めたキーポイント位置点を含んでいる。
各グループが一連の位置点内の複数の位置点を含む場合があることに注目すべきである。
しかし、いくつかの状況において、一連の位置点内の位置点のどれも特定の予め定めたキーポイントにグループ化されないことがあり、そのとき、特定の予め定めたキーポイントが属するグループは、一連の位置点内の位置点のどれも含まない。
【００５４】
ステップ５０３で、同一の所定のキーポイント位置点に属する位置点の位置パラメータの平均を求める。
【００５５】
ステップ５０２から得られたＭ個のグループについて、各グループ中の所定のキーポイント位置点の位置パラメータと他の位置点の位置パラメータとの平均を求める。この時点で取得した平均値を、平均位置パラメータと称する。
【００５６】
例えば、Ｍ個のグループのｊ番目のグループが、Tj個の位置点（Tj個の位置点は、予め定めたキーポイント位置点だけでなく一連の位置点内の位置点も含む）を含む場合、ｊ番目のグループの平均位置パラメータは、下記のように表される。
【数３】
【００５７】
ステップ５０４で、平均値と所定のキーポイント位置点の位置パラメータを比較してそれらの差を求め、これにより、その差が所定の値以下かどうかを判断する。
【００５８】
平均値（すなわち、平均の位置パラメータ）と所定のキーポイント位置点の位置パラメータとの間の差は、対応する位置パラメータを互いに減じることにより計算する。当業者に既知の他の方式を差を計算するのに利用することが可能である。
【００５９】
差が所定の値以下である場合、処理はステップ５０５へ進む。また、差が所定の値より大きい場合、処理はステップ５０６へ進む。
【００６０】
差と比較する所定の値は、経験に基づいて固定的に設定するか、あるいは異なる適用場面に応じて暫定的に設定することが可能である。
一例として、所定の値が「０」に設定される場合もある。この場合、ステップ５０３で取得された平均値（すなわち、平均位置パラメータ）が、所定の位置点の位置パラメータと完全に同一である場合のみ、繰り返し処理が終了し、処理はステップ５０５へ進む。
そうでなければ、処理はステップ５０６へ続き、次の繰り返し処理が開始する。
【００６１】
ステップ５０５で、現在の所定のキーポイント位置点をキーポイント位置点として決定する。その後、図５の処理が終了する。
【００６２】
ステップ５０６で、所定のキーポイント位置点を、平均値と対応する位置点に置き換える。
その後、処理はステップ５０１へ戻り、平均の位置パラメータと所定のキーポイント位置点の位置パラメータと間の差がステップ５０４で所定の値以下であると判定されるまで、ステップ５０１から５０４を繰り返し実行する。
【００６３】
図６は、階層的クラスタリングアルゴリズムを利用することにより、キーポイント位置点を抽出する実施の形態を示す。
この実施の形態において、空間エリア特徴付け装置３４０の抽出手段３４２は、取得する必要のあるキーポイント位置点の数を設定するための設定手段と、一連の位置点内の２つの位置点毎にその間の距離を計算するための計算手段と、最小の距離を有する２つの位置点をマージして、新たな位置点を取得するためのマージ手段と、現在の位置点の数と設定したキーポイント位置点の数を比較するための比較手段とを含む。
現在の位置点の数が設定したキーポイント位置点の数と等しければ、現在の位置点をキーポイント位置点として決定し、現在の位置点の数が設定したキーポイント位置点の数と等しくなければ、計算手段、マージ手段、比較手段が起動され、繰り返し実行される。
【００６４】
以下、本実施の形態における空間エリア特徴付け装置３４０の抽出手段３４２の動作について、図６の各ステップの説明を通じて詳細に記述する。
【００６５】
ステップ６０１で、取得する必要のあるキーポイント位置点の数を設定する。
【００６６】
キーポイント位置点が一連の位置点から抽出されるので、設定するキーポイント位置点の数は一連の位置点内の位置点の数ほど大きくないものとする。
特定の例において、キーポイント位置点の数が一連の位置点内の位置点の数と同一である場合、一連の位置点内の全ての位置点を空間エリアを特徴付けるためのキーポイント位置点として用いることができる。
キーポイント位置点が多ければ多いほど、空間エリアを正確に特徴付けることが可能となる。
しかしながら、目標がどの空間エリアに位置するかを決定するためのその後の計算の複雑度が増大するという問題をもたらすことになる。
このため、上記のような例では、キーポイント位置点の数と計算び複雑度の間で折衷を行うことが必要となる。
【００６７】
この実施の形態においては、取得する必要のあるキーポイント位置点の数をＨと設定すると仮定する。
【００６８】
ステップ６０２で、一連の位置点内の２つの位置点毎にその間の距離を計算する。
【００６９】
図５に示す実施の形態と同様に、ステップ４０１から取得される一連の位置点はL={(xi,yi,zi),
i=1,2,…,N}と表される。ここで、Ｎは、一連の位置点に含まれる位置点の数を示す。
一連の位置点内の２つの位置点毎の間の距離は、ユークリッド距離あるいは当業者にとって既知の他の方法で計算することができる。
【００７０】
ユークリッド距離に対する計算式は以下の通りである。
【数４】
ここで、dijは、一連の位置点におけるｉ番目（ｉ＝１、２、・・・、Ｎ）の位置点(xi,yi,zi)から一連の位置点におけるｊ番目（ｊ＝１、・・・、Ｍ）の位置点(xj,yj,zj)までの間の距離である。
【００７１】
ステップ６０３で、その間の距離が最小の２つの位置点を新たな位置点としてマージする。
【００７２】
まず、ステップ６０２で計算される一連の位置点内の２つの位置点毎の間の距離をソートし、最小の距離を有する２つの位置点を決定する。
一例として、位置点(x1,y1,z1)と位置点(x2,y2,z2)の間の距離が、最小の距離として決定されたと想定する。
【００７３】
その後、最小の距離を有する２つの位置点を新たな位置点としてマージする。上記の例において、位置点(x1,y1,z1) と位置点(x2,y2,z2)は様々な方法によってマージすることが可能である。
例えば、２つの位置点の位置パラメータを平均化を行い、その平均値を新たな位置点の位置パラメータとすることも可能であるし、当業者にとって既知の他の方法によってそれらをマージすることも可能である。
２つの位置点の位置パラメータを平均化することによってマージされた位置点の位置パラメータは、以下のように示される。
【数５】
【００７４】
このようにして、一連の位置点内の位置点の数は、１つまで減少する。
【００７５】
ステップ６０４で、現在の位置点の数を、設定したキーポイント位置点の数と比較する。
【００７６】
ステップ６０１で設定されたように、取得する必要のあるキーポイント位置の数はＨであるので、ステップ６０４では、現在の位置点の数をＨと比較する。
【００７７】
現在の位置点の数がＨと等しい場合、それは現在の位置点の数が設定したキーポイント位置点の数に達したことを示し、その時点で、処理はステップ６０５へ進む。
等しくない場合、処理はステップ６０２へ戻り、位置点の数が設定したキーポイント位置点の数まで減少するまで、ステップ６０２−６０４を繰り返し実行する。
【００７８】
ステップ６０５で、現在のキーポイント位置点をキーポイント位置点として決定する。その後、図６の処理が終了する。
【００７９】
図７は、本発明の好適な実施の形態による空間エリアを決定するためのシステム７００のブロック図を示す。
図７に示すように、システム７００は、目標に配置された測距信号を発信する信号発信器７１０（信号発信器から測位装置（ＰＯＤ）へ発信された測距信号に基づいて目標の位置パラメータが取得される）と、信号発信器からの測距信号に基づいて位置パラメータを取得するように構成された測位装置（ＰＯＤ）７２０と、空間エリア決定装置７４０を含むサーバ７３０とを含む構成である。
【００８０】
以下に、システム７００の実装例について詳細に説明する。
本発明の好適な実施の形態によれば、信号発信器（あるいはラベル）７１０を付けた目標は空間エリアに位置し、決定する必要があるのは、目標が空間内のどの空間エリアに位置するかである。
【００８１】
ＰＯＤ７２０は、空間内の任意の場所に設置することが可能である。
例えば、ＰＯＤ７２０を空間の上部に配置することができ、その初期の配置箇所は任意である。すなわち、空間の上部のどのような箇所にも配置することが可能である。
一例では、サーバ７３０が、信号発信器７１０から発信された測距信号と測距信号を受信するＰＯＤ７２０自身の位置パラメータに基づいて一連の位置点内の各位置点の位置パラメータを決定するために、ＰＯＤ７２０は、信号発信器７１０から測距信号を受信し、その測距信号とＰＯＤ７２０自身の位置パラメータをサーバに対して送信する。
他の例においては、ＰＯＤ７２０が、信号発信器７１０から発された測距信号と信号発信器それ自体の位置パラメータに基づいて一連の位置点内の各位置点の位置パラメータを決定する。
【００８２】
その後、本発明の実施の形態によれば、サーバ７３０は、目標の信号発信器７１０から発信された測距信号と測距信号を受信するＰＯＤ７２０自体の位置パラメータに基づいて、空間全体について対象の位置パラメータを算出する。
例えば、位置パラメータは、空間内の目標の座標（ｘ、ｙ、ｚ）である。
その後、空間エリア決定装置７４０は、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定する。
【００８３】
本発明の好適な実施の形態によれば、空間エリア決定装置７４０は、空間内の目標の位置パラメータを受信する受信手段７４１と、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定する決定手段７４２とを含む。
図８は、本実施の形態による目標が位置する空間エリアを決定する空間エリア決定装置７４０の動作を説明するフローチャートである。
【００８４】
ステップ８０１で、空間内の目標の位置パラメータは受信する。
【００８５】
上述のように、空間内の目標の位置パラメータは、目標の信号発信器から発された測距信号とＰＯＤ７２０の位置パラメータに基づいて、ＰＯＤ７２０あるいはサーバ７３０によって決定される。
【００８６】
ステップ８０２で、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定する。
【００８７】
空間エリアを特徴付けるキーポイント位置点は、図４〜図６に示すような本発明による空間エリア特徴付け方法によって抽出することも可能であるし、当業者に既知の他の方法によって抽出することも可能である。
その他、空間エリアを特徴付けるキーポイント位置点は、ステップ８０２を実行する処理において抽出してもよいし、あるいは当業者が利用可能な記憶装置内に予め記憶させておいてもよい。
【００８８】
目標が位置する空間エリアは、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて様々な方法で決定することが可能である。
図９および図１０は、それぞれ本発明の好適な実施の形態による目標が位置する空間エリアを決定する方法のフローチャートである。
【００８９】
図９を説明する前に、まず図９の方法を実現する空間エリア決定装置７４０の実施の形態について説明する。
空間エリア決定装置７４０は、受信手段７４０および決定手段７４２を含む。また、決定手段７４２は、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標と各空間エリアの間の距離を計算する手段と、最小の距離を有する空間エリアを、目標が位置する空間エリアとして選択する手段とを含む。
具体的な例では、目標と空間エリアの間の距離は、目標と空間エリア内のキーポイント位置点の間の距離を平均化することにより取得される。
【００９０】
図９は、本発明の好適な実施の形態による目標が位置する空間エリアを決定する方法を示すフローチャートである。
【００９１】
ステップ９０１で、目標と各空間エリアの間の距離を計算する。
本発明の実施の形態においては、空間エリアは、空間エリア内のキーポイント位置点によって特徴付けられている。
目標と空間エリアの間の距離の計算は、目標と空間エリア内の各キーポイント位置点の間の距離を計算することにより実行される。
【００９２】
一例として、図４のステップ４０１で受信した位置パラメータが(x0,y0,z0)である想定し、また、空間がＮ個の空間エリアを含むと想定する。
ここで、ｉ番目の空間エリアを特徴付けるのためのキーポイント位置点(xij,yij,zij)の数は、Miである（i=1,2,…,N
また j=1,…, Mi）。
【００９３】
目標と各キーポイント位置点の間の距離は、ユークリッド距離あるいは当業者に既知の他の方法によって計算することが可能である。
【００９４】
ユークリッド距離に対する計算式は以下の通りである。
【数６】
ここで、dijは、目標とｉ番目の空間エリア内のｊ番目のキーポイント位置点(xij,yij,zij)の間の距離である。
【００９５】
ｉ番目の空間エリアが１つのキーポイント位置点を含む場合、上記のように計算されたdijは、目標とｉ番目の空間エリアの間の距離diとみなすことができる。
ｉ番目の空間エリアに含まれるキーポイント位置点の数が１以上である場合、計算した複数の距離を平均化し、平均値を目標と各空間エリアの間の距離として使用することができる。
【００９６】
上記の例において、ｉ番目の空間エリアを特徴付けるキーポイント位置点の数Miが１以上であると想定すると、目標とｉ番目の空間エリアの間の距離diは、以下の式によってMi個のdijを平均することにより取得することができる。
【数７】
【００９７】
ステップ９０２で、計算した距離をソートし、最小の距離を決定する。
【００９８】
上記の例において、空間は合計Ｎ個の空間エリアを含んでいる。したがって、目標とＮ個の空間エリアの間のＮ個の距離diは、ステップ９０１で取得される（ここで、i=1,2,…,N）。そして、Ｎ個の距離をソートによって、最小の距離を取得することができる。
【００９９】
ステップ９０３で、最小の距離を有する空間エリアを、目標が位置する空間エリアとして選択する。
【０１００】
その後、図９の処理が終了する。
【０１０１】
図１０について説明する前に、図１０の方法を実現する空間エリア決定装置７４０の実施の形態について説明する。
空間エリア決定装置７４０は、受信手段７４０と決定手段７４２を含んでいる。
決定手段７４２は、空間エリアから候補空間エリアを選択する手段と、目標の位置パラメータと候補空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標と各候補空間エリアの間の距離の計算する手段と、最小の距離を有する候補空間エリアを、目標が位置する空間エリアとして選択する手段とを含む。
空間エリアから候補空間エリアを選択する手段は、各空間エリアのキーポイント位置点から１つのキーポイントな位置点を選択する手段と、目標と選択されたキーポイント位置点の間の距離を計算する手段と、しきい値未満の距離を有する空間エリアを、候補空間エリアとして決定する手段とを含む。
具体的な例では、目標と空間エリアの間の距離は、目標と空間エリア内のキーポイント位置点の間の距離を平均化することにより取得される。
【０１０２】
図１０は、本発明の好適な実施の形態による目標が位置する空間エリアを決定する方法を示すフローチャートである。
図９に示す方式と異なり、図１０に示す方法においては、全ての空間エリアから複数の候補空間エリアを決定し、目標と空間エリアの間の距離を計算に必要な計算量を減少させる。これにより、目標が位置する空間エリアを決定する方法の速度を向上させる。
【０１０３】
ステップ１００１で、１つのキーポイント位置点を、各空間エリアのキーポイントな位置点から選択する。
【０１０４】
一例では、キーポイント位置点は、空間エリアからランダムに選択することが可能である。
他の好ましい例では、キーポイント位置点を所定の規則に基づいて選択するようにしてもよい。
例えば、空間エリア内の全てのキーポイント位置点について平均の位置パラメータを計算し、次に、平均の位置パラメータに最も近いキーポイント位置点を選択する。
【０１０５】
ステップ１００２で、目標と選択された各キーポイント位置点の間の距離を計算する。
【０１０６】
目標と各空間エリアから選択されたキーポイント位置点の間の距離は、ユークリッド距離あるいは当業者にとって既知の他の方法によって計算することが可能である。
空間エリアの数がＮであると仮定すると、ステップ１００２で計算された目標とＮ個の空間エリア内の各選択されたキーポイント位置点の間の距離の数もまたＮとなる。
【０１０７】
ステップ１００３で、しきい値未満の距離を有する空間エリアを、候補空間エリアとして決定する。
【０１０８】
好ましい実施例では、候補空間エリアの範囲を限定するためにしきい値を設定する。
例えば、ステップ１００２で計算されるＮ個の距離をしきい値と比較し、しきい値より小さい距離を有する空間エリアを、候補空間エリアとして決定する。
【０１０９】
ステップ１００４で、目標と各候補空間エリアの間の距離を計算する。
【０１１０】
このステップはステップ９０１と類似している。しかし、ステップ１００４では、計算するのが目標と候補空間エリアの間の距離であるのに対して、ステップ９０１では、計算するのが目標と全ての空間エリアの間の距離である点で相違している。
【０１１１】
ステップ１００５の、計算した距離をソートし、最小の距離を決定する。
【０１１２】
このステップの実現はステップ９０２と類似している。
さらに、当業者であれば、このステップを実現するために先行技術における他の実施例を利用することができるであろう。ここで、これについて詳しく説明しない。
【０１１３】
ステップ１００６で、最小の距離を有する候補空間エリアを、目標が位置する空間エリアとして選択する。
【０１１４】
このステップはステップ９０３と類似している、しかし、ステップ１００６では、目標が位置する空間エリアを候補空間エリアから決定するのに対して、ステップ９０３では、目標が位置する空間エリアを全ての空間エリアから決定する点で相違している。
【０１１５】
その後、図１０の処理が終了する。
【０１１６】
図１１は、本発明の他の実施の形態による空間内の空間エリアを特徴付けて決定するシステムの構成を示すブロック図である。
【０１１７】
システム１１００は、空間内の目標の位置で測距信号を発信するように構成された信号発信器１１１０と、信号発信器からの測距信号に基づいて目標の位置パラメータを取得するように構成された測位装置（ＰＯＤ）１１２０と、空間エリア特徴付け装置１１３１および空間エリア決定装置１１３２を含むサーバ１１３０とを備える。
空間エリア特徴付け装置１１３１は、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定するように構成されている。
空間エリア決定装置１１３２は、空間エリア内の一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出するように構成されている。
【０１１８】
本発明の好ましい実施の形態において、システム１１００内のサーバ１１３０は、空間エリア特徴付け装置１１３１だけを含んでいてもよい。
この場合、システム１１００は、空間内の空間エリアを特徴付ける機能を実現することが可能である。
【０１１９】
本発明の他の好ましい実施の形態では、システム１１００内のサーバ１１３０が単に空間エリア決定装置１１３２だけを含む構成でもよい。
この場合、システム１１００は、目標が空間のどの空間エリアに位置するかを決定する機能を実現することが可能である。
【０１２０】
本発明の他の好ましい実施の形態では、システム１１００内のサーバ１１３０が、空間エリア特徴付け装置１１３１だけでなく空間エリア決定装置１１３２を含む構成とすることも可能である。この場合、システム１１００は、空間内の空間エリアを特徴付ける機能、および特徴付けられた空間エリアに基づいて、目標が空間のどの空間エリアを位置するかを決定する機能の両方を実現することが可能である。
【０１２１】
本発明による方法と装置は、ソフトウェア、ハードウェアあるいはソフトウェアとハードウェアの組合せによって実現することが可能である。
ハードウェア一部分は専用のロジックで実現され、ソフトウェア一部分は記憶装置に格納され、適切な命令実行システム（例えばマイクロプロセッサ、パーソナルコンピュータ（ＰＣ）、メインフレーム）によって実行される。
【０１２２】
上記では例示と説明を目的として本発明の明細書を提示したが、これは本発明を網羅的に示すことを意図するものではなく、本発明は開示された形態に限定されない。多数の変更や改変が可能なことは、当該技術に精通した当業者には明らかであろう。
【０１２３】
したがって、上記の実施の形態の選択と説明が、本発明の原理および実際の適用をより明快に説明すること、本発明の精神から逸脱することなくなされた、全ての変更および改変は付記される請求項に定義される本発明の保護範囲に含まれることを、当業者は十分理解するであろう。
【０１２４】
また、上記実施形態の一部又は全部は、以下の付記のようにも記載されうるが、これに限定されない。
【０１２５】
（付記１）
複数のキーポイント位置点によって特徴付けられる１つ以上の空間エリアを含む空間内の目標の位置パラメータを受信するステップと、
目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定するステップを
を有することを特徴とする方法。
【０１２６】
（付記２）
前記目標が位置する空間エリアを決定するステップが、
目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標と各空間エリアの間の距離を計算するステップと、
最小の距離を有する空間エリアを、目標が位置する空間エリアとして選択するステップを含む
ことを特徴とする付記１に記載の方法。
【０１２７】
（付記３）
前記目標が位置する空間エリアを決定するステップが、
空間エリアから候補空間エリアを選択するステップと、
目標の位置パラメータと候補空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標と各候補空間エリアの間の距離を計算するステップと、
最小の距離を有する候補空間エリアを、目標が位置する空間エリアとして選択するステップを含む
ことを特徴とする付記１に記載の方法。
【０１２８】
（付記４）
前記空間エリアから候補空間エリアを選択するステップが、
各空間エリアのキーポイント位置点からキーポイント位置点を選択するステップと、
目標と選択したキーポイント位置点の間の距離を計算するステップと、
しきい値未満の距離を有する空間エリアを、候補空間エリアとして決定するステップを含む
ことを特徴とする付記３に記載の方法。
【０１２９】
（付記５）
距離は、目標と各空間エリアのキーポイント位置点の間の距離を平均することにより取得することを特徴とする付記２又は付記３に記載の方法。
【０１３０】
（付記６）
空間エリア内の一連の位置点に基づいて空間エリアを特徴付けるキーポイント位置点を抽出するステップをさらに有することを特徴とする付記１に記載の方法。
【０１３１】
（付記７）
前記キーポイント位置点を抽出するステップが、
（ａ）一連の位置点と所定のキーポイント位置点の間の距離を計算するステップと、
（ｂ）隣接性原理に基づいて、位置点を、所定の各キーポイント位置点にグループ化するステップと、
（ｃ）同一の所定のキーポイント位置点に属する位置点の位置パラメータの平均を求めるステップと、
（ｄ）平均値と各所定のキーポイント位置点の位置パラメータを比較して、それらの間の差を取得するステップとを含み、
差が所定の値以下ならば、所定の位置点をキーポイント位置点として決定し、
差が所定の値より大きければ、所定のキーポイント位置点を平均値と対応する位置点と置き換えた後、ステップ（ａ）からステップ（ｄ）を繰り返し実行することを特徴とする付記６に記載の方法。
【０１３２】
（付記８）
前記キーポイント位置点を抽出するステップが、
（ａ）取得する必要のあるキーポイント位置点の数を設定するステップと、
（ｂ）一連の位置点内の２つの位置点毎にその間の距離を計算するステップと、
（ｃ）最小の距離を有する２つの位置点をマージして、新たな位置点とするステップと、
（ｄ）現在の位置点の数を、設定したキーポイント位置点の数と比較するステップとを含み、
現在の位置点の数が、設定したキーポイント位置点の数と等しければ、現在の位置点をキーポイント位置点として決定し、
現在の位置点の数が、設定したキーポイント位置点の数と等しくなければ、ステップ（ｂ）からステップ（ｄ）を繰り返し実行することを特徴とする付記６に記載の方法。
【０１３３】
（付記９）
測距信号を発信可能な信号発信器が、一連の位置点内の各位置点に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって位置点の位置パラメータを取得することを特徴とする付記６に記載の方法。
【０１３４】
（付記１０）
測距信号を発信可能な信号発信器が、目標に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって目標の位置パラメータを取得することを特徴とする付記１に記載の方法。
【０１３５】
（付記１１）
空間エリア内の一連の位置点を取得するステップと、
一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出するステップと
を有することを特徴とする方法。
【０１３６】
（付記１２）
キーポイント位置点を抽出するステップが、
（ａ）一連の位置点内の位置点と所定のキーポイント位置点の間の距離を計算するステップと、
（ｂ）隣接性原理に基づいて、位置点を、各所定のキーポイント位置点にグループ化するステップと、
（ｃ）同一の所定のキーポイント位置点に属する位置点の位置パラメータの平均を求めるステップと、
（ｄ）平均値と各所定のキーポイント位置点の位置パラメータを比較して、それらの間の差を取得するステップとを含み、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値以下ならば、所定のキーポイントの位置点をキーポイント位置点として決定し、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値より大きければ、所定のキーポイント位置点を平均値に対応する位置点と置き換えた後、ステップ（ａ）からステップ（ｄ）を繰り返し実行することを特徴とする付記１１に記載の方法。
【０１３７】
（付記１３）
初期の所定のキーポイント位置点として、一連の位置点から１以上の位置点を選択することを特徴とする付記１２に記載の方法。
【０１３８】
（付記１４）
キーポイント位置点を抽出するステップが、
（ａ）取得する必要のあるキーポイント位置点の数を設定するステップと、
（ｂ）一連の位置点内の２つの位置点毎にその間の距離を計算するステップと、
（ｃ）最小の距離を有する２つの位置点をマージして、新たな位置点とするステップと、
（ｄ）現在の位置点の数を、設定したキーポイント位置点の数と比較するステップとを含み、
現在の位置点の数が、設定したキーポイント位置点の数と等しければ、現在の位置点をキーポイント位置点として決定し、
現在の位置点の数が、設定したキーポイント位置点の数と等しくなければ、ステップ（ｂ）からステップ（ｄ）を繰り返し実行することを特徴とする付記１１に記載の方法。
【０１３９】
（付記１５）
測距信号を発信可能な信号発信器が、一連の位置点内の各位置点に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって位置点の位置パラメータを取得することを特徴とする付記１１に記載の方法。
【０１４０】
（付記１６）
複数のキーポイント位置点によって特徴付けられる１つ以上の空間エリアを含む空間内の目標の位置パラメータを受信する受信手段と、
目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定する決定手段と
を備えることを特徴とする装置。
【０１４１】
（付記１７）
前記決定手段が、
目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標と各空間エリアの間の距離を計算する手段と、
最小の距離を有する空間エリアを、目標が位置する空間エリアとして選択する手段を備えることを特徴とする付記１６に記載の装置。
【０１４２】
（付記１８）
前記決定手段が、
空間エリアから候補空間エリアを選択する手段と、
目標の位置パラメータと候補空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標と各候補空間エリアの間の距離を計算する手段と、
最小の距離を有する候補空間エリアを、目標が位置する空間エリアとして選択する手段を備えることを特徴とする付記１６に記載の装置。
【０１４３】
（付記１９）
前記空間エリアから候補空間エリアを選択する手段が、
各空間エリアのキーポイント位置点からキーポイント位置点を選択する手段と、
目標と選択したキーポイント位置点の間の距離を計算する手段と、
しきい値未満の距離を有する空間エリアを、候補空間エリアとして決定する手段を備えることを特徴とする付記１８に記載の装置。
【０１４４】
（付記２０）
距離は、目標と各空間エリアのキーポイント位置点の間の距離を平均することにより取得することを特徴とする付記１７又は付記１８に記載の装置。
【０１４５】
（付記２１）
測距信号を発信可能な信号発信器が、一連の位置点内の各位置点に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって位置点の位置パラメータを取得することを特徴とする付記１６に記載の装置。
【０１４６】
（付記２２）
空間エリア内の一連の位置点を取得する取得手段と、
一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出する抽出手段と
を備えることを特徴とする装置。
【０１４７】
（付記２３）
前記抽出手段が、
一連の位置点内の位置点と所定のキーポイント位置点の間の距離を計算する計算手段と、
隣接性原理に基づいて、位置点を、各所定のキーポイント位置点にグループ化するグループ化手段と、
同一の所定のキーポイント位置点に属する位置点の位置パラメータの平均を求める平均化手段と、
平均値と各所定のキーポイント位置点の位置パラメータを比較して、それらの間の差を取得する比較手段とを備え、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値以下ならば、所定のキーポイントの位置点をキーポイント位置点として決定し、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値より大きければ、所定のキーポイント位置点を平均値に対応する位置点と置き換えた後、前記計算手段、前記グループ化手段、前記平均化手段及び前記比較手段の動作を繰り返し実行することを特徴とする付記２２に記載の装置。
【０１４８】
（付記２４）
一連の位置点から１以上の位置点を、初期の所定のキーポイント位置点として選択することを特徴とする付記２３に記載の装置。
【０１４９】
（付記２５）
前記抽出手段が、
取得する必要のあるキーポイント位置点の数を設定する設定手段と、
一連の位置点内の２つの位置点毎にその間の距離を計算する計算手段と、
最小の距離を有する２つの位置点をマージして、新たな位置点とするマージ手段と、
現在の位置点の数を、設定したキーポイント位置点の数と比較する比較手段とを備え、
現在の位置点の数が、設定したキーポイント位置点の数と等しければ、現在の位置点をキーポイント位置点として決定し、
現在の位置点の数が、設定したキーポイント位置点の数と等しくなければ、前記計手段、前記マージ手段、前記比較手段の動作を繰り返し実行することを特徴とする付記２２に記載の装置。
【０１５０】
（付記２６）
測距信号を発信可能な信号発信器が、一連の位置点内の各位置点に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって位置点の位置パラメータを取得することを特徴とする付記２２に記載の装置。
【０１５１】
（付記２７）
複数のキーポイント位置点によって特徴付けられる１つ以上の空間エリアを含む空間内の目標の配置され、測距信号を発信するように構成された信号発信器と、
信号発信器から発信された測距信号に基づいて目標の位置パラメータを取得するように構成された測位装置（ＰＯＤ）と、
目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定するように構成されたサーバと
を備えることを特徴とするシステム。
【０１５２】
（付記２８）
前記サーバは、空間エリア内の一連の位置点に基づいて、空間エリアを特徴付けるキーポイント位置点を抽出するように構成されることを特徴とする付記２７に記載のシステム。
【符号の説明】
【０１５３】
１００：空間
２２１：位置点
２２２：キーポイント位置点
２２０：空間エリア
３１０：信号発信器
３２０：測位装置（ＰＯＤ）
３３０：サーバ
３４０：空間エリア特徴付け装置
３４１：取得手段
３４２：抽出手段
７１０：信号発信器
７２０：測位装置（ＰＯＤ）
７３０：サーバ
７４０：空間エリア決定装置
７４１：受信手段
７４２：決定手段
１１１０：信号発信器
１１２０：測位装置（ＰＯＤ）
１１３０：サーバ
１１３１：空間エリア特徴付け装置
１１３２：空間エリア決定装置
【技術分野】
【０００１】
本発明は、本発明は位置情報処理の分野に関し、特に空間エリアを特徴付けて目標が位置する空間エリアを決定する方法、装置およびシステムに関する。
【背景技術】
【０００２】
ロケーション情報は、ユーザと環境間の地理的関係を特定する際に利用できる基本的なコンテキスト情報であり、これによりユーザの行動をより深く理解することが可能になる。
近年、位置情報を提供する方法とシステムは、ますます多くの注目を集めてきている。特に、位置情報を提供する方およびシステムは、室内の環境および市街地の環境にとってより一層必要とされている。
【０００３】
現在、多種多様な適用情況、例えば、オフィス、医療機関、鉱山、地下鉄、スマートビルディング、あるいはホテル等のような環境において、リアルタイムで正確な位置追跡に対する要求はますます高まってきている。
多くの位置情報に基づいた用途においては、多くの場合、空間を空間エリアあるいは空間グリッドと呼ばれる複数のエリアに区分けし、目標が空間内のどの空間エリアに位置するかを判定することが必要となる。
例えば、商品棚の情報推薦用途においては、棚上の商品がそれぞれ商品に対応する空間エリアに位置すると仮定することができる。そして、目標がその空間エリアに入る時（例えば、目標が一定の商品に接近する時）、空間エリアのモデルに基づいて、目標がどの空間エリアに入るかを決定することが必要である。その結果として、空間エリアに対応する商品に関する情報を顧客に推薦することが可能となる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】パターン分類（セカンドエディション）、１０章、５１７−５９９ページＲ．Ｏ．デューダ、Ｐ．Ｅ．ハート、Ｄ．Ｇ．ストーク、ＩＳＢＮ：０−４７１−０５６６９−３（Pattern Classification (Second Edition), Chapter 10, pp. 517-599, R.O. Duda, P. E. Hart, and D. G. Stork, ISBN:0-471-05669-3）」
【発明の概要】
【発明が解決しようとする課題】
【０００５】
これまで、空間エリアを特徴付け、目標がある一空間エリア内に位置するかどうかを決定するためのいくつかの方法が提案されている。
しかしながら、関連技術によるこれらの方法には少なからず限界がある。例えば、空間エリアのモデリングあるいは空間エリアを特徴付ける処理は余りに複雑過ぎするし、計算コストもかかり過ぎる。さらに、近隣の空間エリアを効率的にかつ迅速に区別することが難しいため、正確性が非常に低くなる。
【０００６】
このため、便利で、迅速かつ正確に、空間エリアを特徴付けて目標が位置する空間エリアを決定することができる技術的解決方法がこの技術分野において特に必要となっている。
【課題を解決するための手段】
【０００７】
本発明の目的は、空間内の空間エリアを特徴付けるための技術的解決方法を提供することにある。
【０００８】
本発明の他の目的は、目標が空間のどの空間エリアに位置するかを決定するための技術的解決方法を提供することにある。
【０００９】
本発明による第２の方法は、空間エリア内の一連の位置点を取得するステップと、一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出するステップとを含む。
【００１０】
本発明による第２の装置は、空間エリア内の一連の位置点を取得する取得手段と、一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出する抽出手段とを含む。
【００１１】
本発明によるシステムは、複数のキーポイント位置点によって特徴付けられる１つ以上の空間エリアを含む空間内の目標の配置され、測距信号を発信するように構成された信号発信器と、信号発信器から発信された測距信号に基づいて目標の位置パラメータを取得するように構成された測位装置（ＰＯＤ）と、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定するように構成されたサーバとを含む。
【発明の効果】
【００１２】
本発明によれば、簡単な処理で空間内の空間エリアを特徴付けることができる方法を実現する。
また、本発明によれば、効率的にかつ迅速に目標が空間のどの空間エリアに位置するかを決定することが可能になる。
【００１３】
本発明の他の特徴と利点は、添付図面を参照する好適な実施の形態によって明らかとなるであろう。
【図面の簡単な説明】
【００１４】
他の目的および本発明の効果は、添付図面を参照した詳細な説明の記述によって、本発明の好適な実施の形態についてのより総合的な理解をもってより明らとなり、かつ容易に理解できるであろう。
【図１】複数の空間エリアを含む空間の概略図である。
【図２ａ】関連技術に従った空間エリアの特徴付けを示す概略図である。
【図２ｂ】本発明の実施の形態による空間エリアの特徴付けを示す概略図である。
【図３】本発明の実施の形態による空間内の空間エリアを特徴付けるシステムの構成を示すブロック図である。
【図４】本発明の実施の形態による空間内の空間エリアを特徴付ける方法を説明するフローチャートである。
【図５】本発明の実施の形態によるキーポイント位置点を抽出する方法を説明するフローチャートである。
【図６】本発明の他の実施の形態によるキーポイント位置点を抽出する方法を説明するフローチャートである。
【図７】本発明の実施の形態による空間エリアを決定するシステムの構成を示すブロック図である。
【図８】本発明の実施の形態による空間エリアを決定する方法を説明するフローチャートである。
【図９】本発明の実施の形態による目標が位置する空間エリアを決定する方法を説明するフローチャートである。
【図１０】本発明の他の実施の形態による目標が位置する空間エリアを決定する方法を説明するフローチャートである。
【図１１】本発明の他の実施の形態による空間内の空間エリアを特徴付けかつ決定するシステムの構成を示すブロック図である。
【発明を実施するための形態】
【００１５】
まず、本発明の好ましい実施の形態において使用される専門用語について簡単に説明する。
【００１６】
１． 空間および空間エリア
本発明による空間は、目標が移動することができる空間であり、例えば、部屋、オフィス、会議室などである。図１は、複数の空間エリアを含む空間１００を示す概略図である。
【００１７】
本発明による空間エリアは、空間に含まれるエリアの一部を指す。図２ａ及び図２ｂは、空間エリア２１０と空間エリア２２０を示す概略図である。本発明による空間エリアが、図２ａと図２ｂに示されるような立方体に限定されず、例えば、直方体、球、不規則な形状などのあらゆる形状を取りうることを理解すべきである。
さらに、空間が１つ以上の空間エリアを含む場合があること、また、空間エリアが図１に示すように互いにオーバーラップの無い独立した空間部分か、あるいは互いにオーバーラップ部分を有する空間部分でもよいことを理解すべきである。
【００１８】
通常、目標がどの空間エリアに存在しているかを認識するためには、空間エリアのモデルを認識しなければならない。すなわち、空間エリアをどのように特徴付けるかを認識していることが必要である。本発明の実施の形態によって、空間エリアを特徴付けるのための技術的方法を提供する。以下にその詳細を説明する。
【００１９】
２．位置点およびキーポイントとなる位置点
本発明による位置点は、空間エリア２２０（例えば、図２ｂに示す空間エリア２２０）内の点であり、空間エリア２２０は複数の位置点２２１を含んでいる。位置点は、空間内の位置点の三次元の座標である対応する位置パラメータを有していてもよい。
【００２０】
キーポイントとなる位置点２２２は、空間エリアを特徴付けるのための位置点である。キーポイントとなる位置点は、空間エリア内のいかなる位置点あるいは空間エリア上のいかなる位置点でもよい。
例えば、図２ｂに示す空間エリア２２０において、空間エリア２２０は複数の位置点２２１を有するだけでなく、空間エリアを特徴付けるためにそれらの位置点から選択されたキーポイントとなる位置点２２２を有する。
原則的に、それが空間を特徴付けることができる限り、空間内のいかなる点もキーポイントとなる位置点として選択することが可能である。
通常は、空間エリアのモデルを取得するためには、空間エリアを特徴付けるためのキーポイントとなる位置点を認識していることが必要である。
本発明の実施の形態によれば、キーポイントとなる位置点の抽出を通して空間エリアを特徴付けるのための技術的方法が提供され、以下にその詳細を説明する。
【００２１】
３．信号発信器
本発明の好ましい実施の形態における信号発信器は、測距信号を発信することができる装置を指しており、例えば、ＲＦ信号発信器である。
本発明の実施の形態において、信号発信器は空間内の目標に配置することが可能である。例えば、信号発信器は、目標の信号発信器から発信される測距信号を受信する測位装置（ＰＯＤ）によって目標の位置パラメータを取得するために、タグの形で目標に付与される。
測距信号としては様々な形式の信号を利用することが可能である。例えば、超音波、赤外線、レーザ、ＲＦ信号、超広帯域パルス信号、ドップラー信号および音波等を含むが、これらに限定されない。
なお、ＰＯＤと信号発信器によって目標の位置パラメータを決定することは本発明の技術分野においては広く知られているので、その詳細は省略する。
【００２２】
４．測位装置（ＰＯＤ：Positioning on
One Device）
本発明の実施の形態によるＰＯＤは、目標の位置パラメータを取得するための装置である。
好ましい実施の形態において、本発明に採用されるＰＯＤは、複数の葉ノードを有するセンサアレイである。葉ノードの数は少なくとも２である。言いかえれば、ＰＯＤは、少なくとも２つの葉ノードセンサとその間に配列された１つのセンサを含む。通常、より多くの葉ノードがあると、測位精度はより高くなる。
具体的な適用例においては、ＰＯＤは、通常、空間１００の一番上に配置され、空間１００内の目標の信号発信器から発信された測距信号を受信する。
目標の位置パラメータは、測距信号およびＰＯＤそれ自体の位置パラメータに基づいて決定することができる。
【００２３】
以下に、本発明の好適な実施の形態について、添付図面を参照して説明する。これらの実施の形態は例として説明するものであり、本発明の範囲を制限するものではない。
【００２４】
まず、空間エリアを特徴付けて目標が位置する空間エリアを決定するこれまでの関連技術による方法について説明する。
【００２５】
図２ａは、関連技術による空間エリアを特徴付ける方法を示す略図である。図２ａに示すような空間エリアを特徴付ける方法において、ユーザは信号発信器を使用し空間エリアの境界に沿って移動し、その間に信号発信器から発された測距信号をＰＯＤによって受信する。
空間エリアの境界に沿って移動する信号発信器の位置パラメータは測距信号とＰＯＤそれ自体の位置パラメータに基づいて決定され、その結果として、空間エリアの境界の位置パラメータが取得される。
その後、空間エリアの一連の頂点が多角形フィッティングアルゴリズムを使用することによって取得され、また、一連の頂点は空間エリアを特徴付けるために空間エリアのモデルとして利用される。
【００２６】
目標が位置する空間エリアを決定する関連技術の方法では、目標の信号発信器が空間内の異なる空間エリアに移動すると、その間に信号発信器から発信された測距信号をＰＯＤによって受信する。
測距信号とＰＯＤそれ自体の位置パラメータに基づいて、目標の位置パラメータを決定する。そして、目標がどの空間エリアに位置するか決定するために、目標の位置パラメータを全ての空間エリアのモデルと比較する。
【００２７】
しかしながら、関連技術には多くの問題点がある。
第１に、目標が信号発信器と共に空間エリアの境界に沿って厳密に移動することを要求されるため、関連技術は空間エリアを特徴付けるために複雑なプロセスを必要とする。
なおかつ、空間エリアの形が不規則である場合、信号発信器を備えた目標が空間エリアの境界に沿って厳密に移動するのは困難である。
第２に、目標が位置する空間エリアを決定する処理において、２つの空間エリアが緊密に隣接する時に、目標が２つの空間エリア間で移動する時、目標が正確にどの空間エリアを位置するか決定するのは困難であろう。
【００２８】
図２ｂは、本発明の好適な実施の形態による空間エリアを特徴付ける方法を示す略図である。
好適な実施の形態によれば、空間エリアを特徴付ける処理の間、目標が信号発信器と共に空間エリアの境界に沿って厳密に移動することは不要である。
それどころか、空間エリアの任意の一連の位置点を取得するだけで、キーポイントとなる位置点を空間エリアを特徴付けるために抽出することが可能である。
以下、図３から図６に示す実施の形態は、本発明による空間部の空間エリアを特徴付ける方法を詳細に説明する。
【００２９】
図３は、本発明の好適な実施の形態による空間内の空間エリアを特徴付けるためのシステム３００のブロック図を示す。
図３に示されるように、空間内の空間エリアを特徴付けるためのシステム３００は、信号発信器３１０と、測位装置（ＰＯＤ）３２０と、サーバ３００とを含む。
信号発信器３１０は、測距信号を発信するように構成され、一連の位置点内の位置点に配置される。一連の位置点内の位置点の位置パラメータは、信号発信器から測位装置（ＰＯＤ）へ測距信号を発信することにより取得される。
測位装置（ＰＯＤ）３２０は、信号発信器からの測距信号に基づいて信号発信器が位置する位置点の位置パラメータを取得するように構成される。
サーバ３３０は、空間エリア特徴付け装置３４０を含む。
【００３０】
以下に、システム３００の実現例について詳細に説明する。
具体的には、本発明の好適な実施の形態によれば、一連の位置点（図２ｂに示すように一点鎖線でつながる一連の位置点）が、まず空間エリア内で決定される。
本発明の実施の形態においては、一連の位置点は、空間エリア内で信号発信器をランダムに移動させることにより決定され、あるいは、空間エリア内に複数の位置点を予め設定することにより決定される。
本発明における一連の位置点は、関連技術のように空間エリアの境界に沿って厳密に移動することによって取得する必要が無く、空間エリア内の任意の位置点を含むことに留意すべきである。
本発明の実施の形態において、信号発信器は、一連の位置点の各位置点にそれぞれ配置され、これにより、位置点の位置パラメータが取得される。
位置点の位置パラメータを取得するため、一連の位置点内の異なる位置点にも同じ信号発信器が配置される。
一例では、サーバ３３０が、信号発信器３１０から発信された測距信号と測距信号を受信するＰＯＤ３２０自身の位置パラメータに基づいて、一連の位置点内の各位置点の位置パラメータを決定する。
他の例では、ＰＯＤ３２０が、信号発信器３１０から発された測距信号と信号発信器それ自体の位置パラメータに基づいて、一連の位置点内の各位置点の位置パラメータを決定する。
信号発信器３１０自体は、本技術分野において広く知られているので、ここでは詳しく説明しない。
【００３１】
次に、ＰＯＤ３２０は、空間にセットされる。ＰＯＤ３２０は、空間内のどのような箇所にも設置することが可能である。
例えば、ＰＯＤ３２０を空間の上部に配置することができ、その初期の配置箇所は任意である。すなわち、空間の上部のどのような箇所にも配置することが可能である。
一例では、サーバ３３０内の空間エリア特徴付け装置３４０が、信号発信器３１０から発信された測距信号と測距信号を受信するＰＯＤ３２０自身の位置パラメータに基づいて一連の位置点内の各位置点の位置パラメータを決定するために、ＰＯＤ３２０は、信号発信器３１０から測距信号を受信し、その測距信号とＰＯＤ３２０自身の位置パラメータをサーバに対して送信する。
他の例においては、ＰＯＤ３２０が、信号発信器３１０から発された測距信号と信号発信器それ自体の位置パラメータに基づいて一連の位置点内の各位置点の位置パラメータを決定する。
【００３２】
信号発信器３１０の配置とＰＯＤ３２０の配置の間に前後関係がないことを理解すべきである。
それらを両方とも同時に配置することも可能であるし、あるいは、ＰＯＤ３２０を最初に配置し、次に、信号発信器３１０を空間の空間特徴点に配置することも可能である。
【００３３】
その後、本発明の実施の形態によれば、サーバ３３０の空間エリア特徴付け装置３４０は、信号発信器３１０から発信された測距信号と測距信号を受信するＰＯＤ３２０自体の位置パラメータに基づいて、空間全体について空間エリア内の一連の位置点内の位置点の位置パラメータを算出する。
例えば、位置パラメータは、空間内の位置点の座標（ｘ、ｙ、ｚ）である。
その後、空間エリア特徴付け装置３４０は、一連の位置点内の位置点の位置パラメータを使用して、空間エリアを特徴付けるキーポイント位置点を抽出し、それにより、空間エリアのモデルを確立する。
【００３４】
本発明の好適な実施の形態によれば、空間エリア特徴付け装置３４０は、空間エリア内の一連の位置点を取得するように構成される取得手段３４１と、空間エリアを特徴付けるために、一連の位置点に基づいてキーポイント位置点を抽出するように構成される抽出手段３４２とを含む。
図４は、本実施の形態による空間エリアを特徴付ける空間エリア特徴付け装置３４０の動作を説明するフローチャートである。
【００３５】
ステップ４０１で、空間エリア内の一連の位置点を取得する。
【００３６】
上述したように、一連の位置点は、空間エリア内でランダムに移動する信号発信器の移動軌跡に基づいて取得することができ、あるいは、空間エリア内に複数の位置点を予め設定することにより取得することができる。
【００３７】
具体的な例では、ユーザが測距信号を発信する信号発信器を所持して空間内をランダムに移動し、そして、信号発信器の移動軌跡をキーポイントとなる位置点を抽出するための一連の位置点として使用することができる。
【００３８】
ステップ４０２で、空間エリアを特徴付けるキーポイント位置点を抽出する。
【００３９】
このステップでは、ステップ４０１から取得された一連の位置点からキーポイントとなる位置点を抽出するために様々な実施方法が利用可能である。
【００４０】
一例として、ステップ４０２は、k-meansクラスタリングアルゴリズム（K-means
clustering algorithm）や、非特許文献１「パターン分類（セカンドエディション）、１０章、５１７−５９９ページＲ．Ｏ．デューダ、Ｐ．Ｅ．ハート、Ｄ．Ｇ．ストーク、ＩＳＢＮ：０−４７１−０５６６９−３（Pattern
Classification (Second Edition), Chapter 10, pp. 517-599, R. O. Duda, P. E.
Hart, and D. G. Stork, ISBN:0-471-05669-3）」に記載されるアルゴリズムで実現することができる。
図５は、k-meansクラスタリングアルゴリズムでキーポイント位置点を抽出するための方法のフローチャートを示す。これについては以下に詳細に説明する。
【００４１】
他の例では、ステップ４０２は、階層的クラスタリングアルゴリズムで実現することができる。図６は、階層的クラスタリングアルゴリズムでキーポイントとなる位置点を抽出するための方法のフローチャートを示す。これについては以下に詳細に説明する。
【００４２】
図５に示すk-meansクラスタリングアルゴリズムでキーポイント位置点を抽出する方法において、空間エリア特徴付け装置３４０は、取得手段３４１と抽出手段３４２を含んでいる。
抽出手段３４２は、一連の位置点内の位置点と所定のキーポイント位置点の間の距離を計算する計算手段（初期の所定のキーポイント位置点は、一連の位置点から選択された１つ以上の位置点である）と、隣接性原理（adjacency principle）に基づいて、位置点を、所定の各キーポイント位置点にグループ化するグループ化手段と、同一の予め定めたキーポイント位置点に属する位置点の位置パラメータの平均を求める平均化手段と、平均値と所定のキーポイント位置点の位置パラメータを比較して、それらの間の差を取得する比較手段とを含む。
平均値と所定のキーポイント位置点の位置パラメータの間の差が所定の値以下である場合、所定の位置点がキーポイント位置点として決定される。
平均値と所定のキーポイント位置点の位置パラメータの間の差が所定の値より大きい場合、所定のキーポイント位置点が平均値と対応する位置点に置き換えられた後、計算手段、グループ化手段、平均化手段および比較手段が起動され、繰り返し実行される。
【００４３】
以下、本実施の形態における空間エリア特徴付け装置３４０の抽出手段３４２の動作フローとについて、図５の各ステップを参照して詳細に説明する。
【００４４】
ステップ５０１で、一連の位置点内の位置点と所定のキーポイント位置点の間の距離を計算する。
【００４５】
一例において、ステップ４０１から得られた一連の位置点は１つ以上の位置点を含む。
各位置点は、位置パラメータ（例えば、位置点の三次元の座標）によって特徴付けられる。
一連の位置点は、L={(xi,yi,zi),
i=1,2,…,N}として示される。ここで、Ｎは、一連の位置点に含まれる位置点の数を示す。
【００４６】
図５に示すようなキーポイントを抽出する実施の形態において、所定のキーポイント位置点が任意の位置点である可能性がある。
所定のキーポイント位置点は、必ずしも空間エリアを特徴付けることができるキーポイント位置点ではなく、一連の位置点からキーポイント位置点を抽出する処理において使用される中間の位置点というだけである。
【００４７】
一例では、１つ以上の初期の所定のキーポイント位置点が予め決められる。あるいは、一連の位置点から１つ以上の位置点が初期の所定のキーポイント位置点として選択される。
初期の所定のキーポイント位置点は、位置パラメータ、例えば、P={(xjP,yjP,zjP),
j=1,…,M}
によって特徴付けられる。ここで、Ｍは、初期の所定のキーポイント位置点の数である。
【００４８】
一連の位置点内の各位置点からＭ個の各所定のキーポイント位置点までの間の距離は、ユークリッド距離あるいは当該技術分野における当業者にとって既知の他の方法を使用することにより計算することができる。
【００４９】
ユークリッド距離に対する計算式は以下の通りである。
【数１】
ここで、dijは、一連の位置点におけるｉ番目（ｉ＝１、２、・・・、Ｎ）の位置点(xi,yi,zi)からｊ番目（ｊ＝１、・・・、Ｍ）の所定のキーポイント位置点((xjP,yjP,zjP))までの間の距離である。
【００５０】
ステップ５０１の終了後、一連の位置点内の各位置点と各所定のキーポイント位置点の間の距離行列dijが得られる。ここで、i=1,2,…,N 及びj=1,…,Mである。
【数２】
【００５１】
ステップ５０２で、位置点を、隣接性原理（adjacency
principle）に基づいて各所定のキーポイント位置点にグループ化する。
【００５２】
このステップにおける隣接性原理は、その位置が位置点に対して最も接近している所定のキーポイント位置点を決定することを指す。
例えば、一連の位置点内のｉ番目の位置点(xi,yi,zi)に対する所定のキーポイント位置点は、以下の方法で決定することができる。
まず、一連の位置点内のｉ番目の位置点(xi,yi,zi)と予め定められた各キーポイント位置点の間の距離を、ステップ５０１での計算結果に基づいて取得する。
例えば、例えば、距離行列（２）におけるｉ行は、Ｍ個の値(di1，di2，…diM)を含む。
Ｍ個の値をソートすることにより、最小値を取得する。例えば、dik
ここで、ｋは、Ｍ個の予め定めたキーポイント位置点のｋ番目を表わす。
その後、一連の位置点内のｉ番目の位置点(xi,yi,zi)を、ｋ番目の予め定めたキーポイント位置点にグループ化する。
【００５３】
以上の方法によって、一連の位置点内の全ての位置点は、隣接性原理に基づいて対応する予め定めたキーポイント位置点にグループ化される。
これにより、Ｍ個のグループを取得することができる。また、各グループは少なくとも１つの予め定めたキーポイント位置点を含んでいる。
各グループが一連の位置点内の複数の位置点を含む場合があることに注目すべきである。
しかし、いくつかの状況において、一連の位置点内の位置点のどれも特定の予め定めたキーポイントにグループ化されないことがあり、そのとき、特定の予め定めたキーポイントが属するグループは、一連の位置点内の位置点のどれも含まない。
【００５４】
ステップ５０３で、同一の所定のキーポイント位置点に属する位置点の位置パラメータの平均を求める。
【００５５】
ステップ５０２から得られたＭ個のグループについて、各グループ中の所定のキーポイント位置点の位置パラメータと他の位置点の位置パラメータとの平均を求める。この時点で取得した平均値を、平均位置パラメータと称する。
【００５６】
例えば、Ｍ個のグループのｊ番目のグループが、Tj個の位置点（Tj個の位置点は、予め定めたキーポイント位置点だけでなく一連の位置点内の位置点も含む）を含む場合、ｊ番目のグループの平均位置パラメータは、下記のように表される。
【数３】
【００５７】
ステップ５０４で、平均値と所定のキーポイント位置点の位置パラメータを比較してそれらの差を求め、これにより、その差が所定の値以下かどうかを判断する。
【００５８】
平均値（すなわち、平均の位置パラメータ）と所定のキーポイント位置点の位置パラメータとの間の差は、対応する位置パラメータを互いに減じることにより計算する。当業者に既知の他の方式を差を計算するのに利用することが可能である。
【００５９】
差が所定の値以下である場合、処理はステップ５０５へ進む。また、差が所定の値より大きい場合、処理はステップ５０６へ進む。
【００６０】
差と比較する所定の値は、経験に基づいて固定的に設定するか、あるいは異なる適用場面に応じて暫定的に設定することが可能である。
一例として、所定の値が「０」に設定される場合もある。この場合、ステップ５０３で取得された平均値（すなわち、平均位置パラメータ）が、所定の位置点の位置パラメータと完全に同一である場合のみ、繰り返し処理が終了し、処理はステップ５０５へ進む。
そうでなければ、処理はステップ５０６へ続き、次の繰り返し処理が開始する。
【００６１】
ステップ５０５で、現在の所定のキーポイント位置点をキーポイント位置点として決定する。その後、図５の処理が終了する。
【００６２】
ステップ５０６で、所定のキーポイント位置点を、平均値と対応する位置点に置き換える。
その後、処理はステップ５０１へ戻り、平均の位置パラメータと所定のキーポイント位置点の位置パラメータと間の差がステップ５０４で所定の値以下であると判定されるまで、ステップ５０１から５０４を繰り返し実行する。
【００６３】
図６は、階層的クラスタリングアルゴリズムを利用することにより、キーポイント位置点を抽出する実施の形態を示す。
この実施の形態において、空間エリア特徴付け装置３４０の抽出手段３４２は、取得する必要のあるキーポイント位置点の数を設定するための設定手段と、一連の位置点内の２つの位置点毎にその間の距離を計算するための計算手段と、最小の距離を有する２つの位置点をマージして、新たな位置点を取得するためのマージ手段と、現在の位置点の数と設定したキーポイント位置点の数を比較するための比較手段とを含む。
現在の位置点の数が設定したキーポイント位置点の数と等しければ、現在の位置点をキーポイント位置点として決定し、現在の位置点の数が設定したキーポイント位置点の数と等しくなければ、計算手段、マージ手段、比較手段が起動され、繰り返し実行される。
【００６４】
以下、本実施の形態における空間エリア特徴付け装置３４０の抽出手段３４２の動作について、図６の各ステップの説明を通じて詳細に記述する。
【００６５】
ステップ６０１で、取得する必要のあるキーポイント位置点の数を設定する。
【００６６】
キーポイント位置点が一連の位置点から抽出されるので、設定するキーポイント位置点の数は一連の位置点内の位置点の数ほど大きくないものとする。
特定の例において、キーポイント位置点の数が一連の位置点内の位置点の数と同一である場合、一連の位置点内の全ての位置点を空間エリアを特徴付けるためのキーポイント位置点として用いることができる。
キーポイント位置点が多ければ多いほど、空間エリアを正確に特徴付けることが可能となる。
しかしながら、目標がどの空間エリアに位置するかを決定するためのその後の計算の複雑度が増大するという問題をもたらすことになる。
このため、上記のような例では、キーポイント位置点の数と計算び複雑度の間で折衷を行うことが必要となる。
【００６７】
この実施の形態においては、取得する必要のあるキーポイント位置点の数をＨと設定すると仮定する。
【００６８】
ステップ６０２で、一連の位置点内の２つの位置点毎にその間の距離を計算する。
【００６９】
図５に示す実施の形態と同様に、ステップ４０１から取得される一連の位置点はL={(xi,yi,zi),
i=1,2,…,N}と表される。ここで、Ｎは、一連の位置点に含まれる位置点の数を示す。
一連の位置点内の２つの位置点毎の間の距離は、ユークリッド距離あるいは当業者にとって既知の他の方法で計算することができる。
【００７０】
ユークリッド距離に対する計算式は以下の通りである。
【数４】
ここで、dijは、一連の位置点におけるｉ番目（ｉ＝１、２、・・・、Ｎ）の位置点(xi,yi,zi)から一連の位置点におけるｊ番目（ｊ＝１、・・・、Ｍ）の位置点(xj,yj,zj)までの間の距離である。
【００７１】
ステップ６０３で、その間の距離が最小の２つの位置点を新たな位置点としてマージする。
【００７２】
まず、ステップ６０２で計算される一連の位置点内の２つの位置点毎の間の距離をソートし、最小の距離を有する２つの位置点を決定する。
一例として、位置点(x1,y1,z1)と位置点(x2,y2,z2)の間の距離が、最小の距離として決定されたと想定する。
【００７３】
その後、最小の距離を有する２つの位置点を新たな位置点としてマージする。上記の例において、位置点(x1,y1,z1) と位置点(x2,y2,z2)は様々な方法によってマージすることが可能である。
例えば、２つの位置点の位置パラメータを平均化を行い、その平均値を新たな位置点の位置パラメータとすることも可能であるし、当業者にとって既知の他の方法によってそれらをマージすることも可能である。
２つの位置点の位置パラメータを平均化することによってマージされた位置点の位置パラメータは、以下のように示される。
【数５】
【００７４】
このようにして、一連の位置点内の位置点の数は、１つまで減少する。
【００７５】
ステップ６０４で、現在の位置点の数を、設定したキーポイント位置点の数と比較する。
【００７６】
ステップ６０１で設定されたように、取得する必要のあるキーポイント位置の数はＨであるので、ステップ６０４では、現在の位置点の数をＨと比較する。
【００７７】
現在の位置点の数がＨと等しい場合、それは現在の位置点の数が設定したキーポイント位置点の数に達したことを示し、その時点で、処理はステップ６０５へ進む。
等しくない場合、処理はステップ６０２へ戻り、位置点の数が設定したキーポイント位置点の数まで減少するまで、ステップ６０２−６０４を繰り返し実行する。
【００７８】
ステップ６０５で、現在のキーポイント位置点をキーポイント位置点として決定する。その後、図６の処理が終了する。
【００７９】
図７は、本発明の好適な実施の形態による空間エリアを決定するためのシステム７００のブロック図を示す。
図７に示すように、システム７００は、目標に配置された測距信号を発信する信号発信器７１０（信号発信器から測位装置（ＰＯＤ）へ発信された測距信号に基づいて目標の位置パラメータが取得される）と、信号発信器からの測距信号に基づいて位置パラメータを取得するように構成された測位装置（ＰＯＤ）７２０と、空間エリア決定装置７４０を含むサーバ７３０とを含む構成である。
【００８０】
以下に、システム７００の実装例について詳細に説明する。
本発明の好適な実施の形態によれば、信号発信器（あるいはラベル）７１０を付けた目標は空間エリアに位置し、決定する必要があるのは、目標が空間内のどの空間エリアに位置するかである。
【００８１】
ＰＯＤ７２０は、空間内の任意の場所に設置することが可能である。
例えば、ＰＯＤ７２０を空間の上部に配置することができ、その初期の配置箇所は任意である。すなわち、空間の上部のどのような箇所にも配置することが可能である。
一例では、サーバ７３０が、信号発信器７１０から発信された測距信号と測距信号を受信するＰＯＤ７２０自身の位置パラメータに基づいて一連の位置点内の各位置点の位置パラメータを決定するために、ＰＯＤ７２０は、信号発信器７１０から測距信号を受信し、その測距信号とＰＯＤ７２０自身の位置パラメータをサーバに対して送信する。
他の例においては、ＰＯＤ７２０が、信号発信器７１０から発された測距信号と信号発信器それ自体の位置パラメータに基づいて一連の位置点内の各位置点の位置パラメータを決定する。
【００８２】
その後、本発明の実施の形態によれば、サーバ７３０は、目標の信号発信器７１０から発信された測距信号と測距信号を受信するＰＯＤ７２０自体の位置パラメータに基づいて、空間全体について対象の位置パラメータを算出する。
例えば、位置パラメータは、空間内の目標の座標（ｘ、ｙ、ｚ）である。
その後、空間エリア決定装置７４０は、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定する。
【００８３】
本発明の好適な実施の形態によれば、空間エリア決定装置７４０は、空間内の目標の位置パラメータを受信する受信手段７４１と、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定する決定手段７４２とを含む。
図８は、本実施の形態による目標が位置する空間エリアを決定する空間エリア決定装置７４０の動作を説明するフローチャートである。
【００８４】
ステップ８０１で、空間内の目標の位置パラメータは受信する。
【００８５】
上述のように、空間内の目標の位置パラメータは、目標の信号発信器から発された測距信号とＰＯＤ７２０の位置パラメータに基づいて、ＰＯＤ７２０あるいはサーバ７３０によって決定される。
【００８６】
ステップ８０２で、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定する。
【００８７】
空間エリアを特徴付けるキーポイント位置点は、図４〜図６に示すような本発明による空間エリア特徴付け方法によって抽出することも可能であるし、当業者に既知の他の方法によって抽出することも可能である。
その他、空間エリアを特徴付けるキーポイント位置点は、ステップ８０２を実行する処理において抽出してもよいし、あるいは当業者が利用可能な記憶装置内に予め記憶させておいてもよい。
【００８８】
目標が位置する空間エリアは、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて様々な方法で決定することが可能である。
図９および図１０は、それぞれ本発明の好適な実施の形態による目標が位置する空間エリアを決定する方法のフローチャートである。
【００８９】
図９を説明する前に、まず図９の方法を実現する空間エリア決定装置７４０の実施の形態について説明する。
空間エリア決定装置７４０は、受信手段７４０および決定手段７４２を含む。また、決定手段７４２は、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標と各空間エリアの間の距離を計算する手段と、最小の距離を有する空間エリアを、目標が位置する空間エリアとして選択する手段とを含む。
具体的な例では、目標と空間エリアの間の距離は、目標と空間エリア内のキーポイント位置点の間の距離を平均化することにより取得される。
【００９０】
図９は、本発明の好適な実施の形態による目標が位置する空間エリアを決定する方法を示すフローチャートである。
【００９１】
ステップ９０１で、目標と各空間エリアの間の距離を計算する。
本発明の実施の形態においては、空間エリアは、空間エリア内のキーポイント位置点によって特徴付けられている。
目標と空間エリアの間の距離の計算は、目標と空間エリア内の各キーポイント位置点の間の距離を計算することにより実行される。
【００９２】
一例として、図４のステップ４０１で受信した位置パラメータが(x0,y0,z0)である想定し、また、空間がＮ個の空間エリアを含むと想定する。
ここで、ｉ番目の空間エリアを特徴付けるのためのキーポイント位置点(xij,yij,zij)の数は、Miである（i=1,2,…,N
また j=1,…, Mi）。
【００９３】
目標と各キーポイント位置点の間の距離は、ユークリッド距離あるいは当業者に既知の他の方法によって計算することが可能である。
【００９４】
ユークリッド距離に対する計算式は以下の通りである。
【数６】
ここで、dijは、目標とｉ番目の空間エリア内のｊ番目のキーポイント位置点(xij,yij,zij)の間の距離である。
【００９５】
ｉ番目の空間エリアが１つのキーポイント位置点を含む場合、上記のように計算されたdijは、目標とｉ番目の空間エリアの間の距離diとみなすことができる。
ｉ番目の空間エリアに含まれるキーポイント位置点の数が１以上である場合、計算した複数の距離を平均化し、平均値を目標と各空間エリアの間の距離として使用することができる。
【００９６】
上記の例において、ｉ番目の空間エリアを特徴付けるキーポイント位置点の数Miが１以上であると想定すると、目標とｉ番目の空間エリアの間の距離diは、以下の式によってMi個のdijを平均することにより取得することができる。
【数７】
【００９７】
ステップ９０２で、計算した距離をソートし、最小の距離を決定する。
【００９８】
上記の例において、空間は合計Ｎ個の空間エリアを含んでいる。したがって、目標とＮ個の空間エリアの間のＮ個の距離diは、ステップ９０１で取得される（ここで、i=1,2,…,N）。そして、Ｎ個の距離をソートによって、最小の距離を取得することができる。
【００９９】
ステップ９０３で、最小の距離を有する空間エリアを、目標が位置する空間エリアとして選択する。
【０１００】
その後、図９の処理が終了する。
【０１０１】
図１０について説明する前に、図１０の方法を実現する空間エリア決定装置７４０の実施の形態について説明する。
空間エリア決定装置７４０は、受信手段７４０と決定手段７４２を含んでいる。
決定手段７４２は、空間エリアから候補空間エリアを選択する手段と、目標の位置パラメータと候補空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標と各候補空間エリアの間の距離の計算する手段と、最小の距離を有する候補空間エリアを、目標が位置する空間エリアとして選択する手段とを含む。
空間エリアから候補空間エリアを選択する手段は、各空間エリアのキーポイント位置点から１つのキーポイントな位置点を選択する手段と、目標と選択されたキーポイント位置点の間の距離を計算する手段と、しきい値未満の距離を有する空間エリアを、候補空間エリアとして決定する手段とを含む。
具体的な例では、目標と空間エリアの間の距離は、目標と空間エリア内のキーポイント位置点の間の距離を平均化することにより取得される。
【０１０２】
図１０は、本発明の好適な実施の形態による目標が位置する空間エリアを決定する方法を示すフローチャートである。
図９に示す方式と異なり、図１０に示す方法においては、全ての空間エリアから複数の候補空間エリアを決定し、目標と空間エリアの間の距離を計算に必要な計算量を減少させる。これにより、目標が位置する空間エリアを決定する方法の速度を向上させる。
【０１０３】
ステップ１００１で、１つのキーポイント位置点を、各空間エリアのキーポイントな位置点から選択する。
【０１０４】
一例では、キーポイント位置点は、空間エリアからランダムに選択することが可能である。
他の好ましい例では、キーポイント位置点を所定の規則に基づいて選択するようにしてもよい。
例えば、空間エリア内の全てのキーポイント位置点について平均の位置パラメータを計算し、次に、平均の位置パラメータに最も近いキーポイント位置点を選択する。
【０１０５】
ステップ１００２で、目標と選択された各キーポイント位置点の間の距離を計算する。
【０１０６】
目標と各空間エリアから選択されたキーポイント位置点の間の距離は、ユークリッド距離あるいは当業者にとって既知の他の方法によって計算することが可能である。
空間エリアの数がＮであると仮定すると、ステップ１００２で計算された目標とＮ個の空間エリア内の各選択されたキーポイント位置点の間の距離の数もまたＮとなる。
【０１０７】
ステップ１００３で、しきい値未満の距離を有する空間エリアを、候補空間エリアとして決定する。
【０１０８】
好ましい実施例では、候補空間エリアの範囲を限定するためにしきい値を設定する。
例えば、ステップ１００２で計算されるＮ個の距離をしきい値と比較し、しきい値より小さい距離を有する空間エリアを、候補空間エリアとして決定する。
【０１０９】
ステップ１００４で、目標と各候補空間エリアの間の距離を計算する。
【０１１０】
このステップはステップ９０１と類似している。しかし、ステップ１００４では、計算するのが目標と候補空間エリアの間の距離であるのに対して、ステップ９０１では、計算するのが目標と全ての空間エリアの間の距離である点で相違している。
【０１１１】
ステップ１００５の、計算した距離をソートし、最小の距離を決定する。
【０１１２】
このステップの実現はステップ９０２と類似している。
さらに、当業者であれば、このステップを実現するために先行技術における他の実施例を利用することができるであろう。ここで、これについて詳しく説明しない。
【０１１３】
ステップ１００６で、最小の距離を有する候補空間エリアを、目標が位置する空間エリアとして選択する。
【０１１４】
このステップはステップ９０３と類似している、しかし、ステップ１００６では、目標が位置する空間エリアを候補空間エリアから決定するのに対して、ステップ９０３では、目標が位置する空間エリアを全ての空間エリアから決定する点で相違している。
【０１１５】
その後、図１０の処理が終了する。
【０１１６】
図１１は、本発明の他の実施の形態による空間内の空間エリアを特徴付けて決定するシステムの構成を示すブロック図である。
【０１１７】
システム１１００は、空間内の目標の位置で測距信号を発信するように構成された信号発信器１１１０と、信号発信器からの測距信号に基づいて目標の位置パラメータを取得するように構成された測位装置（ＰＯＤ）１１２０と、空間エリア特徴付け装置１１３１および空間エリア決定装置１１３２を含むサーバ１１３０とを備える。
空間エリア特徴付け装置１１３１は、目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定するように構成されている。
空間エリア決定装置１１３２は、空間エリア内の一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出するように構成されている。
【０１１８】
本発明の好ましい実施の形態において、システム１１００内のサーバ１１３０は、空間エリア特徴付け装置１１３１だけを含んでいてもよい。
この場合、システム１１００は、空間内の空間エリアを特徴付ける機能を実現することが可能である。
【０１１９】
本発明の他の好ましい実施の形態では、システム１１００内のサーバ１１３０が単に空間エリア決定装置１１３２だけを含む構成でもよい。
この場合、システム１１００は、目標が空間のどの空間エリアに位置するかを決定する機能を実現することが可能である。
【０１２０】
本発明の他の好ましい実施の形態では、システム１１００内のサーバ１１３０が、空間エリア特徴付け装置１１３１だけでなく空間エリア決定装置１１３２を含む構成とすることも可能である。この場合、システム１１００は、空間内の空間エリアを特徴付ける機能、および特徴付けられた空間エリアに基づいて、目標が空間のどの空間エリアを位置するかを決定する機能の両方を実現することが可能である。
【０１２１】
本発明による方法と装置は、ソフトウェア、ハードウェアあるいはソフトウェアとハードウェアの組合せによって実現することが可能である。
ハードウェア一部分は専用のロジックで実現され、ソフトウェア一部分は記憶装置に格納され、適切な命令実行システム（例えばマイクロプロセッサ、パーソナルコンピュータ（ＰＣ）、メインフレーム）によって実行される。
【０１２２】
上記では例示と説明を目的として本発明の明細書を提示したが、これは本発明を網羅的に示すことを意図するものではなく、本発明は開示された形態に限定されない。多数の変更や改変が可能なことは、当該技術に精通した当業者には明らかであろう。
【０１２３】
したがって、上記の実施の形態の選択と説明が、本発明の原理および実際の適用をより明快に説明すること、本発明の精神から逸脱することなくなされた、全ての変更および改変は付記される請求項に定義される本発明の保護範囲に含まれることを、当業者は十分理解するであろう。
【０１２４】
また、上記実施形態の一部又は全部は、以下の付記のようにも記載されうるが、これに限定されない。
【０１２５】
（付記１）
複数のキーポイント位置点によって特徴付けられる１つ以上の空間エリアを含む空間内の目標の位置パラメータを受信するステップと、
目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定するステップを
を有することを特徴とする方法。
【０１２６】
（付記２）
前記目標が位置する空間エリアを決定するステップが、
目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標と各空間エリアの間の距離を計算するステップと、
最小の距離を有する空間エリアを、目標が位置する空間エリアとして選択するステップを含む
ことを特徴とする付記１に記載の方法。
【０１２７】
（付記３）
前記目標が位置する空間エリアを決定するステップが、
空間エリアから候補空間エリアを選択するステップと、
目標の位置パラメータと候補空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標と各候補空間エリアの間の距離を計算するステップと、
最小の距離を有する候補空間エリアを、目標が位置する空間エリアとして選択するステップを含む
ことを特徴とする付記１に記載の方法。
【０１２８】
（付記４）
前記空間エリアから候補空間エリアを選択するステップが、
各空間エリアのキーポイント位置点からキーポイント位置点を選択するステップと、
目標と選択したキーポイント位置点の間の距離を計算するステップと、
しきい値未満の距離を有する空間エリアを、候補空間エリアとして決定するステップを含む
ことを特徴とする付記３に記載の方法。
【０１２９】
（付記５）
距離は、目標と各空間エリアのキーポイント位置点の間の距離を平均することにより取得することを特徴とする付記２又は付記３に記載の方法。
【０１３０】
（付記６）
空間エリア内の一連の位置点に基づいて空間エリアを特徴付けるキーポイント位置点を抽出するステップをさらに有することを特徴とする付記１に記載の方法。
【０１３１】
（付記７）
前記キーポイント位置点を抽出するステップが、
（ａ）一連の位置点と所定のキーポイント位置点の間の距離を計算するステップと、
（ｂ）隣接性原理に基づいて、位置点を、所定の各キーポイント位置点にグループ化するステップと、
（ｃ）同一の所定のキーポイント位置点に属する位置点の位置パラメータの平均を求めるステップと、
（ｄ）平均値と各所定のキーポイント位置点の位置パラメータを比較して、それらの間の差を取得するステップとを含み、
差が所定の値以下ならば、所定の位置点をキーポイント位置点として決定し、
差が所定の値より大きければ、所定のキーポイント位置点を平均値と対応する位置点と置き換えた後、ステップ（ａ）からステップ（ｄ）を繰り返し実行することを特徴とする付記６に記載の方法。
【０１３２】
（付記８）
前記キーポイント位置点を抽出するステップが、
（ａ）取得する必要のあるキーポイント位置点の数を設定するステップと、
（ｂ）一連の位置点内の２つの位置点毎にその間の距離を計算するステップと、
（ｃ）最小の距離を有する２つの位置点をマージして、新たな位置点とするステップと、
（ｄ）現在の位置点の数を、設定したキーポイント位置点の数と比較するステップとを含み、
現在の位置点の数が、設定したキーポイント位置点の数と等しければ、現在の位置点をキーポイント位置点として決定し、
現在の位置点の数が、設定したキーポイント位置点の数と等しくなければ、ステップ（ｂ）からステップ（ｄ）を繰り返し実行することを特徴とする付記６に記載の方法。
【０１３３】
（付記９）
測距信号を発信可能な信号発信器が、一連の位置点内の各位置点に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって位置点の位置パラメータを取得することを特徴とする付記６に記載の方法。
【０１３４】
（付記１０）
測距信号を発信可能な信号発信器が、目標に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって目標の位置パラメータを取得することを特徴とする付記１に記載の方法。
【０１３５】
（付記１１）
空間エリア内の一連の位置点を取得するステップと、
一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出するステップと
を有することを特徴とする方法。
【０１３６】
（付記１２）
キーポイント位置点を抽出するステップが、
（ａ）一連の位置点内の位置点と所定のキーポイント位置点の間の距離を計算するステップと、
（ｂ）隣接性原理に基づいて、位置点を、各所定のキーポイント位置点にグループ化するステップと、
（ｃ）同一の所定のキーポイント位置点に属する位置点の位置パラメータの平均を求めるステップと、
（ｄ）平均値と各所定のキーポイント位置点の位置パラメータを比較して、それらの間の差を取得するステップとを含み、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値以下ならば、所定のキーポイントの位置点をキーポイント位置点として決定し、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値より大きければ、所定のキーポイント位置点を平均値に対応する位置点と置き換えた後、ステップ（ａ）からステップ（ｄ）を繰り返し実行することを特徴とする付記１１に記載の方法。
【０１３７】
（付記１３）
初期の所定のキーポイント位置点として、一連の位置点から１以上の位置点を選択することを特徴とする付記１２に記載の方法。
【０１３８】
（付記１４）
キーポイント位置点を抽出するステップが、
（ａ）取得する必要のあるキーポイント位置点の数を設定するステップと、
（ｂ）一連の位置点内の２つの位置点毎にその間の距離を計算するステップと、
（ｃ）最小の距離を有する２つの位置点をマージして、新たな位置点とするステップと、
（ｄ）現在の位置点の数を、設定したキーポイント位置点の数と比較するステップとを含み、
現在の位置点の数が、設定したキーポイント位置点の数と等しければ、現在の位置点をキーポイント位置点として決定し、
現在の位置点の数が、設定したキーポイント位置点の数と等しくなければ、ステップ（ｂ）からステップ（ｄ）を繰り返し実行することを特徴とする付記１１に記載の方法。
【０１３９】
（付記１５）
測距信号を発信可能な信号発信器が、一連の位置点内の各位置点に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって位置点の位置パラメータを取得することを特徴とする付記１１に記載の方法。
【０１４０】
（付記１６）
複数のキーポイント位置点によって特徴付けられる１つ以上の空間エリアを含む空間内の目標の位置パラメータを受信する受信手段と、
目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定する決定手段と
を備えることを特徴とする装置。
【０１４１】
（付記１７）
前記決定手段が、
目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標と各空間エリアの間の距離を計算する手段と、
最小の距離を有する空間エリアを、目標が位置する空間エリアとして選択する手段を備えることを特徴とする付記１６に記載の装置。
【０１４２】
（付記１８）
前記決定手段が、
空間エリアから候補空間エリアを選択する手段と、
目標の位置パラメータと候補空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標と各候補空間エリアの間の距離を計算する手段と、
最小の距離を有する候補空間エリアを、目標が位置する空間エリアとして選択する手段を備えることを特徴とする付記１６に記載の装置。
【０１４３】
（付記１９）
前記空間エリアから候補空間エリアを選択する手段が、
各空間エリアのキーポイント位置点からキーポイント位置点を選択する手段と、
目標と選択したキーポイント位置点の間の距離を計算する手段と、
しきい値未満の距離を有する空間エリアを、候補空間エリアとして決定する手段を備えることを特徴とする付記１８に記載の装置。
【０１４４】
（付記２０）
距離は、目標と各空間エリアのキーポイント位置点の間の距離を平均することにより取得することを特徴とする付記１７又は付記１８に記載の装置。
【０１４５】
（付記２１）
測距信号を発信可能な信号発信器が、一連の位置点内の各位置点に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって位置点の位置パラメータを取得することを特徴とする付記１６に記載の装置。
【０１４６】
（付記２２）
空間エリア内の一連の位置点を取得する取得手段と、
一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出する抽出手段と
を備えることを特徴とする装置。
【０１４７】
（付記２３）
前記抽出手段が、
一連の位置点内の位置点と所定のキーポイント位置点の間の距離を計算する計算手段と、
隣接性原理に基づいて、位置点を、各所定のキーポイント位置点にグループ化するグループ化手段と、
同一の所定のキーポイント位置点に属する位置点の位置パラメータの平均を求める平均化手段と、
平均値と各所定のキーポイント位置点の位置パラメータを比較して、それらの間の差を取得する比較手段とを備え、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値以下ならば、所定のキーポイントの位置点をキーポイント位置点として決定し、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値より大きければ、所定のキーポイント位置点を平均値に対応する位置点と置き換えた後、前記計算手段、前記グループ化手段、前記平均化手段及び前記比較手段の動作を繰り返し実行することを特徴とする付記２２に記載の装置。
【０１４８】
（付記２４）
一連の位置点から１以上の位置点を、初期の所定のキーポイント位置点として選択することを特徴とする付記２３に記載の装置。
【０１４９】
（付記２５）
前記抽出手段が、
取得する必要のあるキーポイント位置点の数を設定する設定手段と、
一連の位置点内の２つの位置点毎にその間の距離を計算する計算手段と、
最小の距離を有する２つの位置点をマージして、新たな位置点とするマージ手段と、
現在の位置点の数を、設定したキーポイント位置点の数と比較する比較手段とを備え、
現在の位置点の数が、設定したキーポイント位置点の数と等しければ、現在の位置点をキーポイント位置点として決定し、
現在の位置点の数が、設定したキーポイント位置点の数と等しくなければ、前記計手段、前記マージ手段、前記比較手段の動作を繰り返し実行することを特徴とする付記２２に記載の装置。
【０１５０】
（付記２６）
測距信号を発信可能な信号発信器が、一連の位置点内の各位置点に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって位置点の位置パラメータを取得することを特徴とする付記２２に記載の装置。
【０１５１】
（付記２７）
複数のキーポイント位置点によって特徴付けられる１つ以上の空間エリアを含む空間内の目標の配置され、測距信号を発信するように構成された信号発信器と、
信号発信器から発信された測距信号に基づいて目標の位置パラメータを取得するように構成された測位装置（ＰＯＤ）と、
目標の位置パラメータと空間エリアを特徴付けるキーポイント位置点の位置パラメータに基づいて、目標が位置する空間エリアを決定するように構成されたサーバと
を備えることを特徴とするシステム。
【０１５２】
（付記２８）
前記サーバは、空間エリア内の一連の位置点に基づいて、空間エリアを特徴付けるキーポイント位置点を抽出するように構成されることを特徴とする付記２７に記載のシステム。
【符号の説明】
【０１５３】
１００：空間
２２１：位置点
２２２：キーポイント位置点
２２０：空間エリア
３１０：信号発信器
３２０：測位装置（ＰＯＤ）
３３０：サーバ
３４０：空間エリア特徴付け装置
３４１：取得手段
３４２：抽出手段
７１０：信号発信器
７２０：測位装置（ＰＯＤ）
７３０：サーバ
７４０：空間エリア決定装置
７４１：受信手段
７４２：決定手段
１１１０：信号発信器
１１２０：測位装置（ＰＯＤ）
１１３０：サーバ
１１３１：空間エリア特徴付け装置
１１３２：空間エリア決定装置
【特許請求の範囲】
【請求項１】
空間エリア内の一連の位置点を取得するステップと、
一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出するステップと
を有することを特徴とする方法。
【請求項２】
キーポイント位置点を抽出するステップが、
（ａ）一連の位置点内の位置点と所定のキーポイント位置点の間の距離を計算するステップと、
（ｂ）隣接性原理に基づいて、位置点を、各所定のキーポイント位置点にグループ化するステップと、
（ｃ）同一の所定のキーポイント位置点に属する位置点の位置パラメータの平均を求めるステップと、
（ｄ）平均値と各所定のキーポイント位置点の位置パラメータを比較して、それらの間の差を取得するステップとを含み、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値以下ならば、所定のキーポイントの位置点をキーポイント位置点として決定し、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値より大きければ、所定のキーポイント位置点を平均値に対応する位置点と置き換えた後、ステップ（ａ）からステップ（ｄ）を繰り返し実行することを特徴とする請求項１に記載の方法。
【請求項３】
初期の所定のキーポイント位置点として、一連の位置点から１以上の位置点を選択することを特徴とする請求項２に記載の方法。
【請求項４】
キーポイント位置点を抽出するステップが、
（ａ）取得する必要のあるキーポイント位置点の数を設定するステップと、
（ｂ）一連の位置点内の２つの位置点毎にその間の距離を計算するステップと、
（ｃ）最小の距離を有する２つの位置点をマージして、新たな位置点とするステップと、
（ｄ）現在の位置点の数を、設定したキーポイント位置点の数と比較するステップとを含み、
現在の位置点の数が、設定したキーポイント位置点の数と等しければ、現在の位置点をキーポイント位置点として決定し、
現在の位置点の数が、設定したキーポイント位置点の数と等しくなければ、ステップ（ｂ）からステップ（ｄ）を繰り返し実行することを特徴とする請求項１に記載の方法。
【請求項５】
測距信号を発信可能な信号発信器が、一連の位置点内の各位置点に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって位置点の位置パラメータを取得することを特徴とする請求項１から請求項４の何れか１項に記載の方法。
【請求項６】
空間エリア内の一連の位置点を取得する取得手段と、
一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出する抽出手段と
を備えることを特徴とする装置。
【請求項７】
前記抽出手段が、
一連の位置点内の位置点と所定のキーポイント位置点の間の距離を計算する計算手段と、
隣接性原理に基づいて、位置点を、各所定のキーポイント位置点にグループ化するグループ化手段と、
同一の所定のキーポイント位置点に属する位置点の位置パラメータの平均を求める平均化手段と、
平均値と各所定のキーポイント位置点の位置パラメータを比較して、それらの間の差を取得する比較手段とを備え、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値以下ならば、所定のキーポイントの位置点をキーポイント位置点として決定し、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値より大きければ、所定のキーポイント位置点を平均値に対応する位置点と置き換えた後、前記計算手段、前記グループ化手段、前記平均化手段及び前記比較手段の動作を繰り返し実行することを特徴とする請求項６に記載の装置。
【請求項８】
一連の位置点から１以上の位置点を、初期の所定のキーポイント位置点として選択することを特徴とする請求項７に記載の装置。
【請求項９】
前記抽出手段が、
取得する必要のあるキーポイント位置点の数を設定する設定手段と、
一連の位置点内の２つの位置点毎にその間の距離を計算する計算手段と、
最小の距離を有する２つの位置点をマージして、新たな位置点とするマージ手段と、
現在の位置点の数を、設定したキーポイント位置点の数と比較する比較手段とを備え、
現在の位置点の数が、設定したキーポイント位置点の数と等しければ、現在の位置点をキーポイント位置点として決定し、
現在の位置点の数が、設定したキーポイント位置点の数と等しくなければ、前記計手段、前記マージ手段、前記比較手段の動作を繰り返し実行することを特徴とする請求項６に記載の装置。
【請求項１０】
測距信号を発信可能な信号発信器が、一連の位置点内の各位置点に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって位置点の位置パラメータを取得することを特徴とする請求項６から請求項９の何れか１項に記載の装置。
【請求項１】
空間エリア内の一連の位置点を取得するステップと、
一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出するステップと
を有することを特徴とする方法。
【請求項２】
キーポイント位置点を抽出するステップが、
（ａ）一連の位置点内の位置点と所定のキーポイント位置点の間の距離を計算するステップと、
（ｂ）隣接性原理に基づいて、位置点を、各所定のキーポイント位置点にグループ化するステップと、
（ｃ）同一の所定のキーポイント位置点に属する位置点の位置パラメータの平均を求めるステップと、
（ｄ）平均値と各所定のキーポイント位置点の位置パラメータを比較して、それらの間の差を取得するステップとを含み、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値以下ならば、所定のキーポイントの位置点をキーポイント位置点として決定し、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値より大きければ、所定のキーポイント位置点を平均値に対応する位置点と置き換えた後、ステップ（ａ）からステップ（ｄ）を繰り返し実行することを特徴とする請求項１に記載の方法。
【請求項３】
初期の所定のキーポイント位置点として、一連の位置点から１以上の位置点を選択することを特徴とする請求項２に記載の方法。
【請求項４】
キーポイント位置点を抽出するステップが、
（ａ）取得する必要のあるキーポイント位置点の数を設定するステップと、
（ｂ）一連の位置点内の２つの位置点毎にその間の距離を計算するステップと、
（ｃ）最小の距離を有する２つの位置点をマージして、新たな位置点とするステップと、
（ｄ）現在の位置点の数を、設定したキーポイント位置点の数と比較するステップとを含み、
現在の位置点の数が、設定したキーポイント位置点の数と等しければ、現在の位置点をキーポイント位置点として決定し、
現在の位置点の数が、設定したキーポイント位置点の数と等しくなければ、ステップ（ｂ）からステップ（ｄ）を繰り返し実行することを特徴とする請求項１に記載の方法。
【請求項５】
測距信号を発信可能な信号発信器が、一連の位置点内の各位置点に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって位置点の位置パラメータを取得することを特徴とする請求項１から請求項４の何れか１項に記載の方法。
【請求項６】
空間エリア内の一連の位置点を取得する取得手段と、
一連の位置点から空間エリアを特徴付けるキーポイント位置点を抽出する抽出手段と
を備えることを特徴とする装置。
【請求項７】
前記抽出手段が、
一連の位置点内の位置点と所定のキーポイント位置点の間の距離を計算する計算手段と、
隣接性原理に基づいて、位置点を、各所定のキーポイント位置点にグループ化するグループ化手段と、
同一の所定のキーポイント位置点に属する位置点の位置パラメータの平均を求める平均化手段と、
平均値と各所定のキーポイント位置点の位置パラメータを比較して、それらの間の差を取得する比較手段とを備え、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値以下ならば、所定のキーポイントの位置点をキーポイント位置点として決定し、
平均値と所定のキーポイント位置点の位置パラメータの間の差が、所定の値より大きければ、所定のキーポイント位置点を平均値に対応する位置点と置き換えた後、前記計算手段、前記グループ化手段、前記平均化手段及び前記比較手段の動作を繰り返し実行することを特徴とする請求項６に記載の装置。
【請求項８】
一連の位置点から１以上の位置点を、初期の所定のキーポイント位置点として選択することを特徴とする請求項７に記載の装置。
【請求項９】
前記抽出手段が、
取得する必要のあるキーポイント位置点の数を設定する設定手段と、
一連の位置点内の２つの位置点毎にその間の距離を計算する計算手段と、
最小の距離を有する２つの位置点をマージして、新たな位置点とするマージ手段と、
現在の位置点の数を、設定したキーポイント位置点の数と比較する比較手段とを備え、
現在の位置点の数が、設定したキーポイント位置点の数と等しければ、現在の位置点をキーポイント位置点として決定し、
現在の位置点の数が、設定したキーポイント位置点の数と等しくなければ、前記計手段、前記マージ手段、前記比較手段の動作を繰り返し実行することを特徴とする請求項６に記載の装置。
【請求項１０】
測距信号を発信可能な信号発信器が、一連の位置点内の各位置点に配置され、
信号発信器から測位装置（ＰＯＤ）に対して発信された測距信号によって位置点の位置パラメータを取得することを特徴とする請求項６から請求項９の何れか１項に記載の装置。
【図１】
【図２ａ】
【図２ｂ】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２ａ】
【図２ｂ】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１２−１６０１９６（Ｐ２０１２−１６０１９６Ａ）
【公開日】平成２４年８月２３日（２０１２．８．２３）
【国際特許分類】
【出願番号】特願２０１２−６８８２５（Ｐ２０１２−６８８２５）
【出願日】平成２４年３月２６日（２０１２．３．２６）
【分割の表示】特願２０１０−８５６７６（Ｐ２０１０−８５６７６）の分割
【原出願日】平成２２年４月２日（２０１０．４．２）
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
【公開日】平成２４年８月２３日（２０１２．８．２３）
【国際特許分類】
【出願日】平成２４年３月２６日（２０１２．３．２６）
【分割の表示】特願２０１０−８５６７６（Ｐ２０１０−８５６７６）の分割
【原出願日】平成２２年４月２日（２０１０．４．２）
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
[ Back to top ]