位置推定方法および装置
【構成】センサの位置を示すセンサ頂点ＶＳ、空間領域の位置を示す領域頂点ＶＲ、および領域頂点ＶＲとセンサ頂点ＶＳとを結ぶエッジＥからなるグラフ構造Ｇ上に粒子の分布が制限された１または２以上の粒子フィルタを用いて、空間領域内の対象の位置を推定する位置推定方法であって、
センサにおいて対象が検出されたとき、グラフ構造Ｇ上において当該センサを示すセンサ頂点ＶＳと最も距離が近い粒子フィルタを伝播モードとし（Ｓ２９）、それ以外の粒子フィルタを固定モードとし（Ｓ３１）、センサにおいて対象が検出されないとき、すべての粒子フィルタを固定モードとする（Ｓ２５）。
【効果】対象が一定の空間領域に長期間存在して検出されない場合や任意の粒子フィルタが観測を勝ち取らなかった場合でも粒子がグラフ構造Ｇ上の方々に分散することを防止できる。
センサにおいて対象が検出されたとき、グラフ構造Ｇ上において当該センサを示すセンサ頂点ＶＳと最も距離が近い粒子フィルタを伝播モードとし（Ｓ２９）、それ以外の粒子フィルタを固定モードとし（Ｓ３１）、センサにおいて対象が検出されないとき、すべての粒子フィルタを固定モードとする（Ｓ２５）。
【効果】対象が一定の空間領域に長期間存在して検出されない場合や任意の粒子フィルタが観測を勝ち取らなかった場合でも粒子がグラフ構造Ｇ上の方々に分散することを防止できる。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、位置推定方法および装置に関し、特に、１または２以上の粒子フィルタを用いて、空間領域を移動する対象の現在の位置を推定する位置推定方法および装置に関する。
【背景技術】
【０００２】
現在、人が活動する空間領域のいたるところにコンピュータが存在する状況となり、人とコンピュータとの間のインターフェースをどのように発展させるかが大きな課題となっている。現状では、人々の間にコンピュータを扱う能力の格差が存在するため、すべての人々がコンピュータによって提供される各種のサービスによる恩恵を等しく享受しているとはいい難い。
【０００３】
そこで、この恩恵をすべての人々が等しく享受することができる環境の実現が強く望まれている。この環境の実現への鍵となる技術として、コンピュータが周囲の人やオブジェクトの状態を認識し、その状態による環境に応じたサービスを能動的に提供する“コンテクストアウェアネス”がある。
【０００４】
このような技術の実現に向けて、人の姿勢推定、視線推定、音声認識などの数多くの状態推定に関する研究が行われている。そして、これらの状態推定の中でも、人の位置の推定は、人が存在する場所とその場所で起こしうる行動との相関が非常に高いことから、人の行動を認識する上で最も重要な推定の１つであると考えられている。
【０００５】
そのため、人の位置を推定する方法としてさまざまな方法が提案されているが、その１つとして、非特許文献１に記載されているように、粒子フィルタ（モンテカルロ・フィルタ）を用いるものがある。この従来の方法では、単一の粒子フィルタを用いて、移動するロボットの位置を推定しており、粒子フィルタの粒子の分散はロボットが移動する複数の空間領域の互いの繋がりの構造を示すボロノイ・グラフ上に制限されている。そして、この粒子フィルタで、ロボットの位置の予測と複数の空間領域からなる場所にまばらに設けられたセンサによるロボットの検出結果に基づく当該予測の修正とを繰り返すことによってロボットが存在する位置を推定（追跡）している。
【非特許文献１】Liao, L., Fox, D., Hightower, J., Kautz, H., Schulz, D.: Voronoi tracking: Location estimation using sparse and noisy sensor data. In: Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems. (2003)
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところが、このような粒子フィルタを用いて複数の空間領域からなる建物内を移動する人の現在の位置を推定する場合、人が所定の空間領域内のセンサに検出されない位置で長期間存在する状況が発生すると、人の検出による予測の修正が行われず、予測のみが行われるため、時間の経過に伴い粒子が方々に分散して人の存在位置の確率を示す正しい粒子の分布を維持できなくなるという問題がある。
【０００７】
また、このような粒子フィルタを用いて複数の空間領域からなる建物内を移動する人の現在の位置を推定する場合、センサの検出範囲が複数の空間領域にまたがっていてセンサが位置する空間領域と異なる空間領域に存在する人を誤検出したり、一連のセンサによる連続した人の検出の間に所定のセンサが正常に人を検出しなかったりして、ボロノイ・グラフ上において連続しない空間領域において突発的に人が検出された場合には、正しく人の現在の位置を推定（追跡）することができないという問題がある。
【０００８】
なお、センサの検出範囲の複数の空間領域へのまたがりは、たとえば、人が移動する場所がショッピングモールやコンビニエンスストアなどで、空間領域の区切りが陳列棚などの高さの低いものであり、所定の空間領域の天井に設けられた赤外線センサが、当該空間領域以外の空間領域に存在する人が携帯する赤外線発信機から発信された赤外線を受信する場合に起こりうる。空間領域を区切る陳列棚が、赤外線発信機が発信する赤外線を遮断しないためである。
【０００９】
それゆえに、この発明の主たる目的は、新規な、位置推定方法および装置を提供することである。
【００１０】
また、この発明の他の目的は、対象が一定の空間領域に長期間存在するなどしてセンサで検出されない場合がある環境であっても高い精度で対象の現在の位置を推定できる、位置推定方法および装置を提供することである。
【００１１】
さらに、この発明の他の目的は、対象が空間領域の移動可能経路上において連続しない空間領域で突発的に検出される環境であっても高い精度で対象の現在の位置を推定できる位置推定方法および装置を提供することである。
【課題を解決するための手段】
【００１２】
本発明は、上記の課題を解決するために、以下の構成を採用した。なお、括弧内の参照符号および補足説明などは、本発明の理解を助けるために後述する実施の形態との対応関係を示したものであって、本発明を何ら限定するものではない。
【００１３】
第１の発明は、空間領域の境界に設けられ当該境界を通過する対象を検出するセンサの位置を示すセンサ頂点、空間領域の位置を示す領域頂点、および領域頂点と当該領域頂点が示す空間領域の境界に設けられたセンサを示すセンサ頂点とを結ぶエッジからなるグラフ構造上に粒子の分布が制限され、粒子の確率分布に基づく対象の位置の予測とセンサによる対象の検出に基づく予測の修正とを繰り返す１または２以上の粒子フィルタを用いて、空間領域を移動する対象の位置を推定する位置推定方法であって、センサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタに属する粒子の確立分布に基づく対象の位置の予測を検出に基づいて修正し、当該粒子フィルタに属する粒子をグラフ構造上に伝搬させる伝搬ステップ（Ａ）、およびセンサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタ以外の粒子フィルタに属する粒子をグラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第１固定ステップ（Ｂ）を含む、位置推定方法である。
【００１４】
第１の発明では、位置推定方法は、空間領域の境界に設けられ当該境界を通過する対象を検出するセンサ（１０、１２）の位置を示すセンサ頂点（ＶＳ）、空間領域の位置を示す領域頂点（ＶＲ）、および領域頂点と当該領域頂点が示す空間領域の境界に設けられたセンサを示すセンサ頂点とを結ぶエッジ（Ｅ）からなるグラフ構造（Ｇ）上に粒子の分布が制限され、粒子の確率分布に基づく対象の位置の予測とセンサによる対象の検出に基づく予測の修正とを繰り返す１または２以上の粒子フィルタを用いて、空間領域を移動する対象の位置を推定する。
【００１５】
そして、この位置推定方法において、伝搬ステップ（Ａ）（Ｓ２９）では、センサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタに属する粒子の確立分布に基づく対象の位置の予測を検出に基づいて修正し、当該粒子フィルタに属する粒子をグラフ構造上に伝搬させ、第１固定ステップ（Ｂ）（Ｓ３１）では、センサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタ以外の粒子フィルタに属する粒子をグラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる。
【００１６】
第１の発明によれば、粒子フィルタは、伝搬ステップ（Ａ）が実行される伝播モードの他に、第１固定ステップ（Ｂ）が実行される固定モードを備えるので、センサによる対象の検出により予測が修正されない粒子フィルタの粒子がグラフ構造上の方々に分散することを防止し、高い精度で位置の推定を行うことができる。
【００１７】
第２の発明は、第１の発明に従属する発明であって、いずれのセンサにおいても対象が検出されないとき、すべての粒子フィルタについて各粒子フィルタに属する粒子をグラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第２固定ステップ（Ｃ）をさらに含む。
【００１８】
第２の発明では、第２固定ステップ（Ｃ）（Ｓ２５）において、いずれのセンサにおいても対象が検出されないとき、すべての粒子フィルタについて各粒子フィルタに属する粒子をグラフ構造（Ｇ）上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる。
【００１９】
第２の発明によれば、粒子フィルタの固定モードではさらに第２固定ステップが実行されるので、対象が一定の空間領域に長期間存在するなどしてセンサで検出されない場合に粒子がグラフ構造上の方々に分散することを防止し、高い精度で位置の推定を行うことができる。
【００２０】
第３の発明は、第１の発明または第２の発明に従属する発明であって、グラフ構造上において、粒子フィルタの位置から他のセンサによって検出されることなく対象が移動不可能な位置に存在するセンサ頂点が示すセンサが対象を検出した場合に、粒子の確率分布が当該センサ頂点を中心とする新規の粒子フィルタを生成する生成ステップ（Ｄ）、異なるセンサによる連続した所定回数の対象の検出のうちのいずれの検出によっても粒子の確立分布に基づく対象の位置の予測の修正が行われないとき、当該粒子フィルタを消滅させる消滅ステップ（Ｅ）、２以上の粒子フィルタがそれぞれ予測する対象の位置が同じであるとみなせるとき、当該２以上の粒子フィルタを結合する結合ステップ（Ｆ）、および１または２以上の粒子フィルタから対象の位置の推定に利用する粒子フィルタを選択する選択ステップをさらに含む位置推定方法である。
【００２１】
第３の発明では、生成ステップ（Ｄ）（Ｓ３３）で、グラフ構造（Ｇ）上において、粒子フィルタの位置から他のセンサによって検出されることなく対象が移動不可能な位置に存在するセンサ頂点（ＶＳ）が示すセンサが対象を検出した場合に、粒子の確率分布が当該センサ頂点を中心とする新規の粒子フィルタを生成し、消滅ステップ（Ｅ）（Ｓ４３）において、異なるセンサによる連続した所定回数の対象の検出のうちのいずれの検出によっても粒子の確立分布に基づく対象の位置の予測の修正が行われないとき、当該粒子フィルタを消滅させ、結合ステップ（Ｆ）（Ｓ３９）において、２以上の粒子フィルタがそれぞれ予測する対象の位置が同じであるとみなせるとき、当該２以上の粒子フィルタを結合し、選択ステップ（Ｇ）（Ｓ４５）において、１または２以上の粒子フィルタから対象の位置の推定に利用する粒子フィルタを選択する。
【００２２】
第３の発明によれば、人を検出したセンサと粒子フィルタの位置関係、異なるセンサによる連続した所定回数の対象の検出のうちのいずれかの検出によって予測の修正が行われたか否か、および複数の粒子フィルタの位置関係に基づいて、粒子フィルタの生成、消滅、結合を行うので、対象が空間領域の移動可能経路上において連続しない空間領域で突発的に検出された場合でも高い精度で対象の現在の位置を推定することができる。
【００２３】
第４の発明は、第３の発明に従属する発明であって、選択ステップ（Ｇ）では、属する粒子の確立分布に基づく予測の修正に寄与した検出の数がより多く、属する粒子の確立分布に基づく予測の修正に寄与した検出が行われたセンサを示すセンサ頂点の位置の変化の履歴が、検出を行ったすべてのセンサのそれぞれを示すセンサ頂点の位置の変化の履歴とよりよく一致する粒子フィルタを選択する。
【００２４】
第４の発明では、選択ステップ（Ｇ）（Ｓ４５）において、属する粒子の確立分布に基づく予測の修正に寄与した検出の数がより多く、属する粒子の確立分布に基づく予測の修正に寄与した検出が行われたセンサを示すセンサ頂点（ＶＳ）の位置の変化の履歴が、検出を行ったすべてのセンサのそれぞれを示すセンサ頂点の位置の変化の履歴とよりよく一致する粒子フィルタを選択する。
【００２５】
第４の発明によれば、複数存在する粒子フィルタの中から最も確かに対象の位置を予測したであろう粒子フィルタを選択するので、複数存在する粒子フィルタを用いて精度よく対象の現在の位置を推定することができる。
【００２６】
第５の発明は、空間領域の境界に設けられ当該境界を通過する対象を検出するセンサの位置を示すセンサ頂点、空間領域の位置を示す領域頂点、および領域頂点と当該領域頂点が示す空間領域の境界に設けられたセンサを示すセンサ頂点とを結ぶエッジからなるグラフ構造上に粒子の分布が制限され、粒子の確率分布に基づく対象の位置の予測とセンサによる対象の検出に基づく予測の修正とを繰り返す１または２以上の粒子フィルタを用いて、空間領域を移動する対象の位置を推定する位置推定装置であって、センサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタに属する粒子の確立分布に基づく対象の位置の予測を検出に基づいて修正し、当該粒子フィルタに属する粒子をグラフ構造上に伝搬させる伝搬手段、およびセンサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタ以外の粒子フィルタに属する粒子をグラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第１固定手段を備える、位置推定装置である。
【００２７】
第５の発明では、位置推定装置は、空間領域の境界に設けられ当該境界を通過する対象を検出するセンサ（１０、１２）の位置を示すセンサ頂点（ＶＳ）、空間領域の位置を示す領域頂点（ＶＲ）、および領域頂点と当該領域頂点が示す空間領域の境界に設けられたセンサを示すセンサ頂点とを結ぶエッジ（Ｅ）からなるグラフ構造（Ｇ）上に粒子の分布が制限され、粒子の確率分布に基づく対象の位置の予測とセンサによる対象の検出に基づく予測の修正とを繰り返す１または２以上の粒子フィルタを用いて、空間領域を移動する対象の位置を推定する。
【００２８】
そして、この位置推定装置では、伝搬手段（Ａ）（Ｓ２９）が、センサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタに属する粒子の確立分布に基づく対象の位置の予測を検出に基づいて修正し、当該粒子フィルタに属する粒子をグラフ構造上に伝搬させ、第１固定手段（Ｂ）（Ｓ３１）が、センサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタ以外の粒子フィルタに属する粒子をグラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる。
【００２９】
第５の発明によれば、粒子フィルタは、粒子の伝搬が実行される伝播モードの他に、粒子の収束が実行される固定モードを備えるので、センサによる対象の検出により予測が修正されない粒子フィルタの粒子がグラフ構造上の方々に分散することを防止し、高い精度で位置の推定を行うことができる。
【００３０】
第６の発明は、第５の発明に従属する発明であって、いずれのセンサにおいても対象が検出されないとき、すべての粒子フィルタについて各粒子フィルタに属する粒子をグラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第２固定手段をさらに備える。
【００３１】
第６の発明では、第２固定手段（Ｓ２５）が、いずれのセンサにおいても対象が検出されないとき、すべての粒子フィルタについて各粒子フィルタに属する粒子をグラフ構造（Ｇ）上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる。
【００３２】
第６の発明によれば、粒子フィルタの固定モードではさらに第２固定手段により粒子の収束が実行されるので、対象が一定の空間領域に長期間存在するなどしてセンサで検出されない場合に粒子がグラフ構造上の方々に分散することを防止し、高い精度で位置の推定を行うことができる。
【００３３】
第７の発明は、第５の発明または第６の発明に従属する発明であって、グラフ構造上において、粒子フィルタの位置から他のセンサによって検出されることなく対象が移動不可能な位置に存在するセンサ頂点が示すセンサが対象を検出した場合に、粒子の確率分布が当該センサ頂点を中心とする新規の粒子フィルタを生成する生成手段、異なるセンサによる連続した所定回数の対象の検出のうちのいずれの検出によっても粒子の確立分布に基づく対象の位置の予測の修正が行われないとき、当該粒子フィルタを消滅させる消滅手段、２以上の粒子フィルタがそれぞれ予測する対象の位置が同じであるとみなせるとき、当該２以上の粒子フィルタを結合する結合手段、および１または２以上の粒子フィルタから対象の位置の推定に利用する粒子フィルタを選択する選択手段をさらに備える位置推定装置である。
【００３４】
第７の発明では、生成手段（Ｓ３３）が、グラフ構造（Ｇ）上において、粒子フィルタの位置から他のセンサによって検出されることなく対象が移動不可能な位置に存在するセンサ頂点（ＶＳ）が示すセンサが対象を検出した場合に、粒子の確率分布が当該センサ頂点を中心とする新規の粒子フィルタを生成し、消滅手段（Ｓ４３）が、異なるセンサによる連続した所定回数の対象の検出のうちのいずれの検出によっても粒子の確立分布に基づく対象の位置の予測の修正が行われないとき、当該粒子フィルタを消滅させ、結合手段（Ｓ３９）が、２以上の粒子フィルタがそれぞれ予測する対象の位置が同じであるとみなせるとき、当該２以上の粒子フィルタを結合し、選択手段（Ｓ４５）が、１または２以上の粒子フィルタから対象の位置の推定に利用する粒子フィルタを選択する。
【００３５】
第７の発明によれば、人を検出したセンサと粒子フィルタの位置関係、異なるセンサによる連続した所定回数の対象の検出のうちのいずれかの検出によって予測の修正が行われたか否か、および複数の粒子フィルタの位置関係に基づいて、粒子フィルタの生成、消滅、結合を行うので、対象が空間領域の移動可能経路上において連続しない空間領域で突発的に検出された場合でも高い精度で対象の現在の位置を推定することができる。
【００３６】
第８の発明は、第７の発明に従属する発明であって、選択手段は、属する粒子の確立分布に基づく予測の修正に寄与した検出の数がより多く、属する粒子の確立分布に基づく予測の修正に寄与した検出が行われたセンサを示すセンサ頂点の位置の変化の履歴が、検出を行ったすべてのセンサのそれぞれを示すセンサ頂点の位置の変化の履歴とよりよく一致する粒子フィルタを選択する。
【００３７】
第８の発明では、選択手段（Ｓ４５）は、属する粒子の確立分布に基づく予測の修正に寄与した検出の数がより多く、属する粒子の確立分布に基づく予測の修正に寄与した検出が行われたセンサを示すセンサ頂点（ＶＳ）の位置の変化の履歴が、検出を行ったすべてのセンサのそれぞれを示すセンサ頂点の位置の変化の履歴とよりよく一致する粒子フィルタを選択する。
【００３８】
第８の発明によれば、複数存在する粒子フィルタの中から最も確かに対象の位置を予測したであろう粒子フィルタを選択するので、複数存在する粒子フィルタを用いて精度よく対象の現在の位置を推定することができる。
【発明の効果】
【００３９】
この発明によれば、センサによる対象の検出により予測が修正されない粒子フィルタの粒子がグラフ構造上の方々に分散することを防止し、高い精度で位置の推定を行うことができる。
【００４０】
また、この発明によれば、対象が一定の空間領域に長期間存在するなどしてセンサで検出されない場合がある環境でも高い精度で対象の現在の位置を推定できる。
【００４１】
さらに、この発明によれば、対象が空間領域の移動可能経路上において連続しない空間領域で突発的に検出される環境であっても高い精度で対象の現在の位置を推定できる。
【００４２】
この発明の上述の目的、その他の目的、特徴および利点は、図面を参照して行う以下の実施例の詳細な説明から一層明らかとなろう。
【発明を実施するための最良の形態】
【００４３】
本発明の位置推定方法の一例として以下に説明する位置推定方法は、たとえば、図１に示すように、ショッピングモールなどにおいて、商品の陳列棚１００によって区切られた複数の空間領域（たとえば空間領域α、β、γ）内を移動する買い物客の現在の位置の推定を行う。このショッピングモールでは、空間領域Ａを成す（空間領域αに面している）陳列棚１００には、たとえば、ネコ用の缶詰のキャットフードが陳列され、空間領域βを成す陳列棚１００には、たとえば、ネコ用の袋詰めのキャットフードが陳列され、空間領域γを成す陳列棚１００には、たとえば、イヌ用の袋詰めのドックフードが陳列されるというように、各空間領域を成す陳列棚１００ごとに陳列されている商品が異なっている。
【００４４】
このような空間領域の各出入り口（境界）のたとえば天井に、一対の赤外線センサ１０からなるゲートセンサ１２を配置する。ゲートセンサ１２は、一方の赤外線センサ１０が隣接する空間領域の一方側に位置し、他方の赤外線センサ１０が隣接する空間領域の他方側に位置するように配置される。そして、陳列棚１００によって形成されたこれらの空間領域内を移動する買い物客に赤外線発信機（不図示）を携帯させる。たとえば、買い物カゴ（不図示）に赤外線発信機を取り付けるようにしてもよい。
【００４５】
このようにして、買い物客が携帯する赤外線発信機から発信された赤外線を、赤外線センサ１０で受信することによって、買い物客の位置を検出し、買い物客が存在する空間領域を特定することによって、たとえば、買い物客が現在どの商品の購入を検討しているかを知ることができる。また、１つの空間領域内に存在し続ける時間を計測することによって、買い物客がどの程度の時間、所定の商品の購入を検討していたかを知ることができる。なお、買い物客が携帯する赤外線発信機から発信される赤外線には買い物客を識別するＩＤ情報（以下、“識別ＩＤ”と呼ぶ。）が含まれ、複数存在する買い物客のぞれぞれの位置を推定することができる。
【００４６】
このようなシステムにおいて、買い物客を検出した赤外線センサ１０の位置をそのまま、買い物客が現在に存在する位置であると判断できれば問題はない。しかし、ショッピングモールなどでは、空間領域を区切る陳列棚１００は天井まで届いておらず、また、赤外線発信機から発信される赤外線を遮断するような構造ではないので、天井に設置された赤外線センサ１０の赤外線の検出範囲Ｒ（図１の斜線を施した楕円の部分）は、赤外線センサ１０が設置されている空間領域の範囲をはみ出して他の空間領域にまたがっている。（このように、赤外線が空間領域を区切る陳列棚１００や壁によって遮断されない環境を“半開放型環境”と呼ぶ。）そのため、たとえば、買い物客が空間領域αから赤外線センサ（５）１０および赤外線センサ（６）１０を通過して空間領域γに入り、空間領域γの図面上部を移動した場合、空間領域γの内部で、赤外線センサ（３）１０および赤外線センサ（４）１０によって赤外線が検出され、買い物客が空間領域γに存在するにもかかわらず、買い物客が空間領域γから直接的に空間領域βに移動したと誤判断する可能性がある。
【００４７】
また、買い物客の移動を追跡している場合において、買い物客がゲートセンサ１２を通過する際に、買い物カゴなどに取り付けられた赤外線発信機から赤外線が下方向や横方向に発射されたときには、通過するゲートセンサ１２の赤外線センサ１０によって赤外線が受信されない事態が発生する。このような場合には、受信漏れを起こしたのとは別の赤外線センサ１０で次に買い物客が検出されると、買い物客が連続しない空間領域を移動したこととなり、正常に買い物客の移動を追跡することができない。
【００４８】
このような誤判断を防止し、また、正常に対象としての買い物客を追跡するために、いわゆる粒子フィルタを用いる。粒子フィルタは高次元の一般状態空間モデルに対するフィルタと平滑化のために提案されたものであり、条件付分布をその分布からの多数の実現値で近時表現するものであり、モンテカルロ・フィルタとも呼ばれる。
【００４９】
より具体的には、粒子フィルタは、追跡対象（ここでは、買い物客）の状態を、Ｎ個の離散的な状態ベクトルｘ(i)tとこれに対応する重みw(i)tを持つ多数の粒子{ｘ(i)t, w(i)t }(i = １，…，N)を用いて離散変数の集合に近似して逐次的に推定する方法である。
【００５０】
状態ベクトルｘtを非線形関数Ft、システムノイズｖtを用いて表した式（１）をシステムモデルと呼び、観測ベクトルｙtを非線形関数Ht、観測ノイズｗtを用いて表した式（２）を観測モデルと呼ぶ。そして、状態ベクトルｘtと観測ベクトルｙtとの関係を示すシステムモデルと観測モデルとの組を一般状態空間モデルと呼ぶ。なお、システムモデルは状態予測モデルとも呼ばれる。
【００５１】
［システムモデル］ ｘt ＝Ft(Xt-1,ｖt) (1)
［観測モデル］ ｙt ＝Ht(ｘt,ｗt) (2)
これらのシステムモデルおよび観測モデルは、状態ｘt-1，ｘtが与えられたときの条件付分布Qt，Ｒtを用いて以下の式（３）および式（４）のように一般化される。
【００５２】
［システムモデル］ ｘt 〜Qt(・|ｘt-1) (3)
［観測モデル］ ｙt 〜 Ｒt(・|ｘt) (4)
粒子フィルタは、これらの式（３）および式（４）に示す、システムモデルと観測モデルを用いて、観測対象（ここでは買い物客）の状態の予測と、実際の観測結果に基づいた状態の予測の修正を繰り返す。状態の予測と予測の修正は、図２に示すフロー図の手順に従って実行される。
【００５３】
このフロー図に示すように、手順では、まず、ステップＳ１では、ｉ＝１，…，ＮのＮ個の粒子からなる粒子の集団の初期状態Ｘ0＝{ｘ(1)0,…,ｘ(N)0}を生成する。
【００５４】
そして、ステップＳ３では、変数“ｔ”を“１”だけインクリメントする。この変数“ｔ”は“１”〜“Ｔ”までの値をとり、時間をカウントするための変数である。ステップＳ３からステップＳ１１までの手順が、変数“ｔ”が“Ｔ”に等しくなるまで繰り返される。なお、変数“ｔ”の初期値は“０”である。
【００５５】
次に、ステップＳ５では、すべての“ｉ”（粒子）について、式（５）のシステムモデルに基づいて、状態ｘ^(i)tを予測し、
【００５６】
【数１】
【００５７】
また、観測によって得たｙtを用いて、すべての“ｉ”（粒子）について、式（６）の観測モデルに基づいて、粒子の重みｗ(i)tを計算する。
【００５８】
【数２】
【００５９】
ここで、粒子フィルタを用いて買い物客の位置を推定する場合には、“観測”とは、赤外線センサ１０によって買い物客が検出されることであり、“ｙt”は買い物客が検出された空間領域の位置などの情報である。
【００６０】
次に、ステップＳ７では、式（７）に基づいて、各粒子の重みの合計を計算する。
【００６１】
【数３】
【００６２】
そして、ステップＳ９では、すべての“ｉ”（粒子）について、式（８）に基づいて、ステップＳ７で求めた重みの合計に対する、状態（粒子）ｘ^(i)tの重みｗ(i)tの割合ｗ~(i)tを計算する。つまり、重みｗ(i)t（ｗ~(i)t）の合計が“１”となるように正規化する。なお、“ｗ~(i)t”は、“ｉ”番目の粒子の“importance weight”と呼ばれる。
【００６３】
【数４】
【００６４】
さらに、時刻“ｔ”における粒子の集団Ｘ^t＝{ｘ^(1)t,…,ｘ^(N)t}の中からｘ^(i)tをｗ~(i)tの確率で復元抽出する。この復元抽出をリサンプリングと呼ぶ。そして、リサンプリングされたN個の粒子からなる時刻“ｔ”における新たな粒子の集団Xt＝{ｘ(1)t,…,ｘ(N)t}を生成する。このようにして、状態ｘ^(i)tの予測が観測（検出）された“ｙt”によって修正される。
【００６５】
こうして生成された時刻“Ｔ”における粒子の集団XＴ＝{ｘ(1)Ｔ,…,ｘ(N)Ｔ}において、最も大きい重みを持つ（最も尤度が高い）粒子の状態ｘ(i)Ｔが示す位置が時刻“Ｔ”における対象（買い物客）の現在の位置として推定される。
【００６６】
本発明の位置推定方法で用いられる粒子フィルタは、属する粒子の分布が、空間領域の位置を示す領域頂点ＶＲと、赤外線センサ１０の位置を示すセンサ頂点ＶＳと、領域頂点ＶＲおよびセンサ頂点ＶＳ並びにセンサ頂点ＶＳおよびセンサ頂点ＶＳを結ぶエッジＥによって決定されるグラグ構造Ｇ上に制限される。
【００６７】
図１においては、領域頂点ＶＲを“□”で、センサ頂点ＶＳを“○”で、エッジＥを太線でそれぞれ示している。図１からもわかるように、領域頂点ＶＲは、各空間領域に１つ設定され、その空間領域に隣接するセンサ頂点ＶＳに対するハブ（ｈｕｂ）の役目を果たす。また、センサ頂点ＶＳは、赤外線センサ１０の受信部の位置を示し、グラフ構造Ｇ上で唯一、対象としての買い物客が検出される場所である。赤外線センサ１０で買い物客が検出されることを、センサ頂点ＶＳで“観測”が得られると表現する。
【００６８】
本発明の位置推定方法では、得られた“観測”や粒子フィルタの状況などに応じて複数の粒子フィルタを生成し、また、複数の粒子フィルタの結合や粒子フィルタの消滅を行う。より具体的には、時刻ｔにおいて“観測”が得られたセンサ頂点ＶＳの位置が、グラフ構造Ｇ上において、時刻ｔ−１における既存の粒子フィルタの位置から他の１つ以上のセンサ頂点ＶＳにおいて“観測”されることなく買い物客が移動することができない位置である場合に、時刻ｔにおいて“観測”が得られたセンサ頂点ＶＳを粒子の確率分布の中心として新規の粒子フィルタを生成する。このような位置のセンサ頂点ＶＳにおいて得られる“観測”を“突発的な観測”と呼ぶ。
【００６９】
そして、複数の粒子フィルタのそれぞれが予測する買い物客の位置が同じ空間領域内であるとみなせる場合に、これらの粒子フィルタを結合して１つの粒子フィルタとする。
【００７０】
また、複数の粒子フィルタが存在する場合には、センサ頂点ＶＳにおける“観測”は、“観測”が得られたセンサ頂点ＶＳの位置から最も近い粒子フィルタに対してのみ“観測”として影響を与える。つまり、予測を修正する。このように“観測”によって粒子フィルタが影響を受けて予測を修正することを、粒子フィルタが“観測を勝ち取る”と表現する。
【００７１】
さらに、異なるセンサ頂点ＶＳで所定の回数だけ連続して発生する“観測”について、“観測”を一度も勝ち取らなかった粒子フィルタは消滅させる。
【００７２】
詳細については後述するが、このように、粒子フィルタの生成、結合、消滅を行うことによって、赤外線センサ１０による誤検出が発生しても買い物客の現在の位置を高い精度で推定することができる。
【００７３】
また、“観測”を勝ち取った粒子フィルタは“観測”による影響に基づいて予測を修正して粒子をグラフ構造Ｇ上に伝搬させるが、“観測”を勝ち取らなかった粒子フィルタは、粒子を最も近い領域頂点ＶＲの周辺に収束させる。なお、いずれのセンサ頂点ＶＳにおいても観測が得られない場合は、すべての粒子フィルタの粒子を最も近い領域頂点ＶＲの周辺に収束させる。この粒子フィルタの粒子をグラフ構造Ｇ上を伝搬させる状態を粒子フィルタの“伝搬モード”と呼び、粒子を領域頂点ＶＲの周辺に収束させる状態を粒子フィルタの“固定モード”と呼ぶ。
【００７４】
このように、粒子フィルタに伝搬モードの他に固定モードを与えることによって、“観測”を勝ち取らなかった粒子フィルタの粒子が時間経過とともにグラフ構造Ｇ上の方々に分散することを防止することができる。
【００７５】
本発明の位置推定方法で用いられる粒子フィルタは、伝搬モードのシステムモデルを式（９）ないし式（１１）で定めることによって、粒子の分布をグラフ構造Ｇ上に制限する。なお、本発明の位置推定方法で用いられる粒子フィルタのシステムモデルには、上述のように伝搬モードと固定モードとがあるが固定モードについては後述する。
【００７６】
【数５】
【００７７】
Ｐ^(ｘt｜ｘt-1)は、粒子が時刻“ｔ−１”においてある状態ｘt-1にあった場合に、時刻ｔで状態ｘtに変化する確率を示している。Ｄ(ｘt,ｘt-1)は、グラフ構造Ｇ上における２つの粒子（状態）の距離を示しており、式（１１）からわかるように、Ｐ^(ｘt｜ｘt-1)は、２つの粒子の状態ｘt，ｘt-1の間のグラフ構造Ｇ上における距離に基づいて決定される。なお、２つの粒子（状態）間の距離Ｄ(ｘt,ｘt-1)は、経験的に平均“０”、分散“σd=０．３”の正規分布に従うとしている。
【００７８】
ところで、本発明の位置推定方法で用いられる粒子フィルタの粒子は、式（１２）に示すようなパラメータを持つ。
【００７９】
粒子状態空間 ｘ＝＜ｅ，ｄ，ｍ＞ (12)
式（１２）において、“ｅ”は粒子が現在存在するエッジＥであり、“ｄ”は粒子が現在存在するエッジＥの端点からの距離であり、“ｍ”は粒子フィルタの現在の動作モード（伝搬モード／固定モード）である。
【００８０】
そして、グラフ構造Ｇ上における２つの粒子（状態）間の距離Ｄ(ｘt,ｘt-1)は、式（１３）によって決定される。
【００８１】
【数６】
【００８２】
式（１３）によると、異なる２つの粒子（状態）が同一エッジＥ上にある場合（ｅi ＝ ｅj）は、単純に、そのエッジＥ上において距離を計算する。一方、異なる２つの粒子（状態）が同一エッジＥ上に存在しない場合（otherwise）は、２つの粒子（状態）を結ぶ経路をどのように選択するかによって距離が異なってくるので、経路の距離が最短となるエッジＥを選択する。式（１３）における、“Σk|ｅk|”は、点“ｄi”と点“ｄj”との間に存在する１つの経路に含まれるエッジＥの距離の和を示している。なお、領域頂点ＶＲとセンサ頂点ＶＳをつなぐエッジＥの距離を一様に“０．５”とし、センサ頂点ＶＳとセンサ頂点ＶＳをつなぐエッジＥの距離を一様に“１．０”とする。
【００８３】
式（１０）におけるＰ(ｅt|ｅt-1)は、図３に示すように、粒子がエッジＥ（ｅi）の分岐点である領域頂点ＶＲに到達したときに、次に所定のエッジＥ（ｅi、ｅj、ｅkのいずれか）に遷移する確率（以下、“遷移確率”と呼ぶ。）を表しており、式（１４）で決定される。
【００８４】
【数７】
【００８５】
ここで、“時刻ｔにおいてセンサ頂点v(j)Ｓで“観測”されたＩＤ受信頻度（freq(v(j)Ｓ,t)）”とは、ある固定の時間間隔（ウィンドウ幅）“ｔw”を設定したとき、［ｔ−ｔw，ｔ］の時間内に、センサ頂点v(j)Ｓに位置する赤外線センサ１０によって、その買い物客の識別ＩＤが“観測”（検出）された回数を示している。
【００８６】
また、式（１４）における“α”は、買い物客の識別ＩＤがまったく観測されない赤外線センサ１０のセンサ頂点ＶＳが接続されたエッジＥへの遷移確率が完全に“０”になることを防止するための値である。つまり、現実には、買い物客が赤外線センサ１０の近くに移動したにもかかわらず、赤外線センサ１０の誤った“観測”によって、“観測”が得られない場合が考えられることに対応して“α”という一定値のゲタをはかせている。
【００８７】
なお、式（１４）における右辺は、確率ではないので、実際にコンピュータなどで、Ｐ(ｅt,ｅt-1)を計算する場合には、すべてのエッジＥ（１，…，Ne）について、式（１４）の右辺を計算し、計算された各エッジＥについての右辺を、右辺の各右辺の合計に対する割合と置き換えて、置き換えられた各右辺の合計が“１”となるように正規化したものを用いる。
【００８８】
このように、エッジＥの遷移確率Ｐ(ｅt,ｅt-1)は、センサ頂点ＶＳ（赤外線センサ１０）における買い物客の識別ＩＤの受信頻度（観測回数）に基づいて動的に変更される。
【００８９】
伝搬モードのシステムモデルは以上に説明した通りであるが、観測モデルは、式（１５）によって決定される。
【００９０】
【数８】
【００９１】
この式からわかるように、粒子の尤度は、“ＩＤ受信頻度／粒子から観測されたセンサ頂点ＶＳまでのホップ数”によって決定される。そして、式（１５）は、同時刻において、複数のセンサ頂点ＶＳ上で“観測”が得られた場合、状態ｘtの粒子の尤度は、複数の“観測”で得られた尤度の和によって計算されることを示している。
【００９２】
そして、先述の“importance weight”は、式（１５）を利用して、式（１６）によって決定される。
【００９３】
【数９】
【００９４】
この“importance weight”は、先述の通り、次の時刻における粒子フィルタに属する粒子の分布を決定するリサンプリングに利用される。
【００９５】
以上が、伝搬モードにおけるシステムモデルと観測モデルであるが、固定モードにおけるシステムモデルは式（１７）によって決定される。
【００９６】
【数１０】
【００９７】
式（１７）からわかるように、粒子フィルタの固定モードでは、すなわち、粒子フィルタが“観測”を勝ち取らない状態においては、その粒子フィルタに属する粒子をすべて、当該粒子フィルタに最も近い領域頂点ＶＲの周辺に収束させる。つまり、粒子フィルタに属する粒子は、当該粒子フィルタが“観測”を勝ち取らない期間、最近傍の領域頂点ＶＲを中心とした正規分布に従って分散される。なお、この場合の正規分布の分散は伝搬モードと同様に経験上“σd＝０．３”とする。
【００９８】
本発明の位置推定方法では、以上に説明したような伝搬モードおよび固定モードのシステムモデルと観測モデルとに基づく粒子フィルタを用いて、上述したように、たとえば、ショッピングモール内を移動する買い物客の現在の位置を推定する。
【００９９】
しかし、この例のように、空間領域の出入り口に設けられた赤外線センサ１０によるまばらな“観測”しか得られない環境では、得られる“観測”が少ないことや誤った“観測”が原因となり、現在の時刻までの“観測”に基づいて一意に買い物客の位置を決定することができない場合が発生する。このような場合、粒子の尤度が示す買い物客の位置の事後分布は、多峰性を有すると考えられる。
【０１００】
そこで、本発明の位置推定方法では、新たな粒子フィルタの生成、粒子フィルタの結合、および粒子フィルタの消滅を繰り返すことによって、多峰性を有する事後分布に対応する。
【０１０１】
そして、複数の粒子フィルタが存在する場合には、詳しくは後述するが、尤もらしい買い物客の移動軌跡に対応する粒子フィルタを選択することによって、高精度に買い物客の位置の推定を行う。
【０１０２】
先述したが、図４に示すように、グラグ構造Ｇ上において、領域頂点ＶＲとセンサ頂点ＶＳを接続するエッジＥの距離を一様に“０．５”とし、隣接するセンサ頂点ＶＳ同士を接続するエッジＥの距離を一様に“１．０”とする。
【０１０３】
そして、図４に示すように、新たに“観測”が得られたセンサ頂点ＶＳと既存の粒子フィルタとの距離が“２．０”以上である場合には、粒子が、新たに観測が得られたセンサ頂点ＶＳを中心とした正規分布に従う新たな粒子フィルタを生成する。なお、このように、粒子フィルタとの距離が“２．０”以上であるセンサ頂点ＶＳにおいて得られる“観測”が、上述した“突発的な観測”である。
【０１０４】
ここで、図５に示すような、センサ頂点ＶＳと粒子フィルタｋとの距離を式（１８）で決定する。
【０１０５】
【数１１】
【０１０６】
式（１８）からわかるように、あるセンサ頂点ＶＳとある粒子フィルタｋとの距離は、粒子フィルタｋに属するすべての粒子とあるセンサ頂点ＶＳとの間の距離の合計を、粒子フィルタｋに属する粒子の総数で割って得られる平均の距離によって表現する。
【０１０７】
したがって、式（１８）によって得られる値が“２．０”以上である場合に、新たな粒子フィルタを生成する。なお、粒子とあるセンサ頂点ＶＳとの間の距離は、粒子が存在するエッジＥの端点からの距離ｄ（式（１２）参照）と、粒子が存在するエッジＥに接続されている頂点Ｖ（センサ頂点ＶＳ／領域頂点ＶＲ）およびあるセンサ頂点ＶＳの距離に基づいて求めることができる。
【０１０８】
また、２つの粒子フィルタのグラフ構造Ｇ上における距離が“２．０”未満である場合には、２つの粒子フィルタが予測する買い物客の現在の位置は同一であるとみなし、これらの２つの粒子フィルタを結合して新たな１つの粒子フィルタを生成する。
【０１０９】
ここで、図６に示すような、２つの粒子フィルタｋ1と粒子フィルタｋ2との間の距離を、式（１８）を用いた式（１９）で決定する。
【０１１０】
【数１２】
【０１１１】
式（１９）からわかるように、２つの粒子フィルタｋ1と粒子フィルタｋ2との間の距離は、基準となる頂点Ｖ（センサ頂点ＶＳ／領域頂点ＶＲ）および粒子フィルタｋ1の距離と、基準となる頂点Ｖ（センサ頂点ＶＳ／領域頂点ＶＲ）および粒子フィルタｋ2の距離との和から計算される。ここで、粒子フィルタｋ1と粒子フィルタｋ2とを結ぶグラフ構造Ｇ上の経路が複数ある場合は、最短の経路上の頂点Ｖ（センサ頂点ＶＳ／領域頂点ＶＲ）を基準とする。
【０１１２】
なお、２つの粒子フィルタｋ1と粒子フィルタｋ2とを結合して新たな粒子フィルタｋnewを生成する際には、粒子フィルタｋ1の粒子の集団X(k1)tと粒子フィルタｋ2の粒子の集団X(k2)tとから尤度が高い順に粒子を選び出して粒子フィルタｋnewの粒子の集団X(new)tとする。
【０１１３】
これらのようにして生成された粒子フィルタは、ある一定の回数、たとえば３回以上だけ連続して異なるセンサ頂点ＶＳで得られる“観測”について、一度も“観測”を勝ち取らなかった場合には消滅させる。このように粒子フィルタを消滅させることによって、赤外線センサ１０による誤った“観測”を排除することができる。
【０１１４】
以上に説明したように、本発明の位置推定方法では、複数の粒子フィルタが存在する可能性があるが、複数の粒子フィルタが存在する場合には、先述のように、尤も確からしい買い物客の移動軌跡に対応する粒子フィルタに基づいて買い物客の現在の位置を推定する。
【０１１５】
つまり、各粒子フィルタが勝ち取った“観測”の履歴、具体的には“観測”に基づく買い物客の空間領域の通過方向の履歴、および“観測”の数が、各粒子フィルタ毎に記録される。そして、“観測”の数がより多く、より一貫性のある通過方向の履歴が記録されている粒子フィルタを尤も確からしい買い物客の移動軌跡に対応する粒子フィルタであるとする。ここで、通過方向の履歴とは、粒子フィルタが勝ち取った“観測”を得たセンサ頂点ＶＳの位置とその“観測”の順序からなる“観測”の位置の変化の記録である。また、より一貫性のある通過方向の履歴とは、“観測”の位置の変化が、グラフ構造Ｇ上において“観測”を得たすべてのセンサ頂点ＶＳの位置とその“観測”の順序からなる“観測”の位置の変化とよりよく一致する履歴である。
【０１１６】
また、２つの粒子フィルタを結合して１つの新たな粒子フィルタを生成する場合には、それぞれの粒子フィルタに対応つけて記録されている買い物客の空間領域の通過方向の履歴と“観測”の数とを１つにまとめる必要がある。この際には、“観測”の数については、より数の多い“観測”の数を、通過方向の履歴については、より一貫性のある通過方向の履歴を、新たな粒子フィルタの“観測”の数、よび通過方向の履歴とする。
【０１１７】
なお、買い物客の通過方向は、ゲートセンサ１２に含まれる一対の赤外線センサ１０による買い物客が携帯する赤外線発信機から発せられる赤外線の受信の順序によって知ることができる。
【０１１８】
このように、より多くの“観測”を勝ち取り、かつ、より一貫性のある通過方向の履歴を有し、尤も確からしい買い物客の移動軌跡に対応する粒子フィルタを“尤も確からしい粒子フィルタ”と呼ぶ。
【０１１９】
図７は以上に説明した、本発明の位置測定方法を、コンピュータを用いて実現する場合に、当該コンピュータによって実行される処理手順を逐次的に示したフロー図である。このフロー図にしたがって、コンピュータで実行される処理を説明する。図７のフロー図に示す処理を実行するコンピュータは一般的で周知のパーソナルコンピュータなどである。赤外線センサ１０で買い物客を検出した旨を示す情報をパーソナルコンピュータに与える方法（図１０参照）やパーソナルコンピュータの構成（図１１参照）などについては後述する。なお、以下のフロー図に示す処理は適宜に並列に実行してもかまわない。また、このコンピュータの記憶装置には、先述の各粒子フィルタが勝ち取った“観測”の数と、各粒子フィルタが勝ち取った“観測”に基づく通過方向の履歴が記録される。
【０１２０】
まず、コンピュータのＣＰＵは、ステップＳ２１で、変数“ｔ”を“１”だけインクリメントする。この変数“ｔ”は、コンピュータで本発明の位置測定方法を実行する際の処理単位となる時間をカウントするものであり、コンピュータのＣＰＵは、ステップＳ２１からステップＳ４５の処理を変数“ｔ”が“１”だけカウントされる度に実行する。なお、この変数“ｔ”は、図２のフロー図において示した変数“ｔ”と同じとみなせる。
【０１２１】
ステップＳ２３では、いずれかの赤外線センサ１０（センサ頂点ＶＳ）において、“観測”が得られたか否か、つまり、赤外線センサ１０が、買い物客が携帯する赤外線発信機から発信された赤外線を検出したか否かを判断する。
【０１２２】
“観測”が得られなかったと判断すると（ステップＳ２３：ＮＯ）、ＣＰＵはステップＳ２５で、存在するすべての粒子フィルタを固定モードとし、各粒子フィルタの粒子を最も近くの領域頂点ＶＲの周辺に収束させる。そして、ステップＳ４５に進む。
【０１２３】
一方、ステップＳ２３で“観測”が得られたと判断すると（ステップＳ２３：ＹＥＳ）、ＣＰＵは、次に、ステップＳ２７において、式（１８）による演算に基づいて“観測”が得られた赤外線センサ１０の位置を示すセンサ頂点ＶＳからの距離が“２．０”より短い粒子フィルタが存在するか否かを判断する。
【０１２４】
距離が“２．０”より短い粒子フィルタが存在すると判断する（ステップＳ２７：ＹＥＳ）と、ステップＳ２９において、“観測”が得られたセンサ頂点ＶＳからの距離が最も近い粒子フィルタ、つまりステップＳ２３において得られたと判断された“観測”を勝ち取った粒子フィルタを伝搬モードにする。そして、ステップＳ３１において、“観測”を勝ち取らなかったすべての粒子フィルタを固定モードにする。なお、“観測”を勝ち取り、伝搬モードとなった粒子フィルタについては、式（９）ないし式（１１）のシステムモデルおよび式（１５）の観測モデルを用いて、図２に示したステップＳ５ないしステップＳ９の処理の手順が実行される。
【０１２５】
一方、ステップＳ２７において、“観測”が得られたセンサ頂点ＶＳからの距離が“２．０”より短い粒子フィルタが存在しないと判断すると（ステップＳ２７：ＮＯ）、ステップＳ３３において、“観測”が得られたセンサ頂点ＶＳを中心とする新たな粒子フィルタを生成し、ステップＳ３５において、新たに生成した粒子フィルタを伝搬モードにする。
【０１２６】
ステップＳ３７では、式（１９）による演算に基づいて、互いの距離が“２．０”よりも短い粒子フィルタが存在するか否かを判断する。そして、互いの距離が“２．０”よりも短い粒子フィルタが存在すると判断すると（ステップＳ３７：ＹＥＳ）、距離が“２．０”よりも短い複数の粒子フィルタを結合して新たな粒子フィルタを生成する。
【０１２７】
一方、互いの距離が“２．０”よりも短い粒子フィルタが存在しないと判断すると（ステップＳ３７：ＮＯ）、ステップＳ３９をスキップする。
【０１２８】
次に、ステップＳ４１では、異なるセンサ頂点ＶＳで３回連続して得られる“観測”について、１つの“観測”も勝ち取らなかった、つまり３回連続して“観測”を勝ち取らなかった粒子フィルタが存在するか否かを判断する。
【０１２９】
３回連続して“観測”を勝ち取らなかった粒子フィルタが存在すると判断すると（ステップＳ４１：ＹＥＳ）、ステップＳ４３において、３回連続して“観測”を勝ち取らなかった粒子フィルタを消滅させる。
【０１３０】
一方、３回連続して“観測”を勝ち取らなかった粒子フィルタが存在しないと判断すると（ステップＳ４１：ＮＯ）、ステップＳ４３をスキップしてステップＳ４５に進む。
【０１３１】
そして、ステップＳ４５では、“尤も確からしい粒子フィルタ”の粒子の尤度に基づいて、買い物客の現在の位置を推定する。粒子フィルタが１つしか存在しない場合には、その粒子フィルタに基づいて買い物客の現在の位置を推定する。
＜実施例＞
本発明の位置推定方法の有効性を証明するために以下のような実験を行った。この実験では、後述するような“半開放型環境”を構築し、この“半開放型環境”に２つの赤外線センサ１０からなるゲートセンサ１２を設置し、“半開放型環境”内に形成された空間領域を移動する赤外線発信機を携帯した人物（この人物が実験の対象ではないが、以下、“被験者”と呼ぶ。）の現在の位置を推定（追跡）する。
【０１３２】
実験のための“半開放型環境”（以下、“実験環境”と呼ぶ。）は、壁などの遮蔽物がない横７．５ｍ、縦８．８ｍの空間を、ポールと、そのポール間に張られたビニールテープによって、図８に示すように、空間領域Ａないし空間領域Ｉの９つの部屋や通路に区切ることによって作成した。
【０１３３】
この実験環境は、観測の単位となる空間領域間ＡないしＩに、赤外線を遮断する壁などによる明確な区切りは存在しないが、ポール間に張られたビニールテープにより、被験者の移動が制限される。
【０１３４】
そして、被験者が各空間領域ＡないしＩ内を移動する際に、必ず通過する空間領域の境界に、合計９台のゲートセンサ（通過方向検知センサ）１２を配置した。また、被験者の正しい位置データを得るために、被験者を撮影するビデオカメラ（不図示）をこの実験環境に合計８台だけ配置した。
【０１３５】
ゲートセンサ１２は、図９に示すように構成した。つまり、ゲートセンサ１２は、所定のボードを組み立てて作成したアーチ状のゲート枠１４、ゲート枠１４の天井部分に設けられた一対の赤外線センサ１０、および赤外線センサ１０から得られた情報を処理するセンサモジュール１６からなる。
【０１３６】
このようなゲートセンサ１２は、空間領域の境界に、一方の赤外線センサ１０が当該境界に面する一方の空間領域側に位置し、他方の赤外線センサ１０が当該境界に面する他方の空間領域側に位置するように配置される。
【０１３７】
実験環境に設けられた９台のゲートセンサ１２のそれぞれを、図１０に示すように（図１０には紙面の都合上、４つのゲートセンサ１２を示している。）、無線通信中継ポイント３０を介したＩＥＥＥ８０２． １１ｂ規格の無線ＬＡＮによって、パーソナルコンピュータ４０と接続する。
【０１３８】
実験環境内を移動する被験者は、頭部に小型の赤外線タグ（赤外線発信機）２０を装着する。
【０１３９】
ゲートセンサ１２の一方の赤外線センサ１０が赤外線タグ２０から赤外線を受信することによりタグＩＤを受け取ると、センサモジュール１６は赤外線センサ１０からタグＩＤを受け取り、当該ＩＤタグに、当該ＩＤタグを受信した赤外線センサ１０の識別ＩＤとタイムスタンプとを付加し、このタグＩＤを無線通信中継ポイント３０に送信する。無線通信中継ポイント３０は、センサモジュール１６から送信されたタグＩＤを中継してパーソナルコンピュータ（位置推定装置）４０に送信する。
【０１４０】
タグＩＤを受信したパーソナルコンピュータ４０は、図２および図７に示した処理手順を実行して、本発明の位置推定方法により、被験者の現在の位置を推定する。パーソナルコンピュータ４０はタグＩＤに付加された、赤外線センサ１０の識別ＩＤによって被験者を検出した位置（赤外線センサ１０の位置）を特定し、タイムスタンプによって被験者を検出した順序を判断する。
【０１４１】
パーソナルコンピュータ４０は、図１１に示すように構成されている。つまり、パーソナルコンピュータ４０は、ＣＰＵ４２、メモリ４４、ＨＤＤ（Hard Disc Drive）４６、液晶モニタなどの表示装置４８、キーボードやマウスなどの入力装置５０、およびＩＥＥＥ ８０２． １１ｂ規格に対応した無線通信装置５２から構成される。
【０１４２】
パーソナルコンピュータ４０のＨＤＤ４６には、図２および図７に示した処理手順を実行するための位置推定プログラム４６ａ、当該位置推定プログラム４６ａによって利用されるグラグ構造Ｇのデータ（グラフ構造データ）４６ｂ、および同様に位置推定プログラム４６ａによって利用される粒子フィルタのシステムモデルや観測モデルを示すデータ（粒子フィルタデータ）４６ｃが記憶されている。そして、位置推定プログラム４６ａの実行時には、ＨＤＤ４６には、生成された各粒子フィルタに対応した履歴データ（“観測”の回数や通過方向の履歴を示すデータ）４６ｄが記録される。なお、被験者を検出した赤外線センサ１０の位置は、当該赤外線センサ１０の識別ＩＤとグラフ構造データ４６ｂとに基づいて特定される。つまり、ＨＤＤ４６には、グラフ構造Ｇ上のセンサ頂点ＶＳの位置と赤外線センサ１０の識別ＩＤとが対応つけて記憶されている。
【０１４３】
この実験では、実験環境のいたるところ（ビニールテープ、机の上、床など）に、“１”から“２７”までの番号が記載された番号札を配置し、被験者に、実験環境に配置された番号札を番号順に探し出し、探し出した番号札を手で触れさせるというタスクを与えた。なお、被験者には番号札の大まかな位置が記載された地図を手がかりとして与えた。本実験の被験者は１５人であり、各被験者は、このタスクを２回ずつ実行した。
【０１４４】
このようなタスクは、ショッピングモール、コンビニエンスストア、図書館などのような“半開放型環境”において、目的の品物を探し出すことを想定している。
【０１４５】
本発明の位置推定方法の有効性を示すための比較対象として、実験環境において、他の３つの位置推定方法も施行した。他の位置推定方法とは、“最頻反応センサ選択法（距離制約なし）”、“最頻反応センサ選択法（距離制約あり）”、および“単一粒子フィルタ法”である。
【０１４６】
“最頻反応センサ選択法（距離制約なし）”とは、単位時間内の反応回数が最大である赤外線センサの近傍に人物が存在しているとみなす手法である。
【０１４７】
“最頻反応センサ選択法（距離制約あり）”とは、“最頻反応センサ選択法”で得られた結果に対して、赤外線センサ１０の間を人物が移動するために必要な時間を考慮し、突発的に他の空間領域で誤って生じた“観測”（突発的な観測）を後処理で取り除く手法である。なお、本実験では、人物の歩行速度を１．４ｍ／ｓとした。
【０１４８】
“単一粒子フィルタ法”とは、図８に示したセンサ頂点ＶＳ、領域頂点ＶＲ、およびエッジＥからなるグラフ構造Ｇ上に、単体の粒子フィルタを適用して被験者の位置推定を行う手法である。
【０１４９】
図１２の表に実験の結果を示す。図９の表において、“正解時間率”とは、図７のフロー図におけるステップＳ４５において時間“ｔ”ごとに行われる、被験者（買い物客）の現在の位置の推定結果の正解率を、全実験時間に占める正解した時間“ｔ”の割合（率）で表したものである。また、“遷移数”とは、各手法において、被験者の位置がある空間領域から別の空間領域に移動したと判断された回数である。
【０１５０】
図１２の表の実験結果によれば、“最頻反応センサ選択法（距離制約なし）”を用いた場合の位置推定制度は、正解時間率が約２０％、正解遷移率が約３０％、本発明の位置推定方法と比較して低い値となっている。このことから、異なる空間領域に配置された赤外線センサの検出範囲Ｒが複数の空間領域にまたがっていない従来の環境（遮蔽型環境）を前提とした“最頻反応センサ選択法”では、その前提が成り立たない“半開放型環境”では、正確に被験者の位置の推定を行うことが困難であるといえる。
【０１５１】
“最頻反応センサ選択法”に、赤外線センサ１０間の物理的距離による制約を設けて誤った“観測”を除去する方法を適用した“最頻反応センサ選択法（距離制約あり）”の場合、“最頻反応センサ選択法（距離制約なし）”と比較して、精度が１０％ほど向上している。この精度の向上の原因を検討すると、本実験では、横７．５ｍ、縦８．８ｍという狭い空間に９つの空間領域を設けたため、頻繁に被験者の空間領域の移動が発生したことが原因であると考えられる。
【０１５２】
つまり、空間領域の境界に設置された赤外線センサ１０において、比較的高頻度に“観測”が得られ（空間領域の平均滞留時間は３秒程度）、時間的に連続な“観測”が得られる環境において有用な、センサ間の距離の制約を用いた“最頻反応センサ選択法（距離制約あり）”がより精度を向上することが可能となったと考えられる。
【０１５３】
しかし、本発明の位置推定方法と比較すると、正解時間率が約１０％、正解遷移率は約１４％、低い値となっている。したがって、“最頻反応センサ選択法（距離制約あり）”のようにセンサ間の距離の制約により誤った“観測”除去する方法よりも、本発明の位置推定方法のように、センサによる“観測”の順序に基づいて誤った“観測”を除去する方法が有効であることがわかる。
【０１５４】
“単一粒子フィルタ法”による位置推定の精度は、正解時間率が約２４％、正解遷移率にいたっては約４３％も本発明の位置推定方法より低い値となっている。その原因として、“半開放型環境”では、空間領域の境界付近において、異なる空間領域に位置する赤外線センサ１０上で、長期にわたり誤った“観測”が発生する状況が頻繁に起き、徐々に粒子が誤った“観測”の発生している赤外線センサ１０（センサ頂点ＶＳ）の方向へ移動してしまうことがあげられる。
【０１５５】
さらに、粒子フィルタの粒子は誤った“観測”が生じた赤外線センサ１０が取り付けられた空間領域には即座に移動できず、その間にある空間領域やエッジＥ上を移動する。そのため、粒子フィルタの粒子が推定した被験者の移動の軌跡（通過方向の履歴）と、実際の被験者の移動の軌跡とでは大きく異なってしまうことが、正解遷移率を低下させていると考えられる。
【０１５６】
また、一度、誤った“観測”が得られた赤外線センサ１０（センサ頂点ＶＳ）に粒子が集中すると、その後に正しい“観測”が得られたときに、その正しい“観測”が得られたセンサ頂点ＶＳに粒子が戻るまでに時間がかかるため、さらに位置推定の精度を下げていると考えられる。
【０１５７】
以上の原因により、“単一粒子フィルタ法”では、“半開放型環境”において、正確に被験者の位置の推定を行うことは困難であり、実験を行った手法の中で、一番精度が低い結果となっていると考えられる。
【０１５８】
一方、本発明の位置推定方法では、正解時間率、正解遷移率ともに、８５％以上の精度が得られており、“半開放型環境”において高い精度で被験者の位置の推定を行えることが証明された。
【０１５９】
本発明の位置推定方法は、“最頻反応センサ選択法（距離制約あり）”のように、時間情報に基づいて誤った“観測”の除去を行うのではなく、複数の粒子フィルタを用いて、赤外線センサ１０の“観測”の順序に基づいて、誤った“観測”を検出し、修正する。
【０１６０】
そのため、被験者の空間領域内における滞留により誤った“観測”の前後で長期にわたり正しい“観測”が得られなかった場合においても頑健にその誤った“観測”を除去することが可能となり、このように高い精度が得られたと考えられる。
【０１６１】
また、赤外線センサ１０の検出もれが生じた場合においても、離れた空間領域で得られた赤外線センサ１０による正しい“観測”に対して、即座にそのセンサ頂点ＶＳを中心として粒子フィルタを生成する。そのため、その“観測”以降の被験者の位置の推定（追跡）が正確に行えることが本発明の位置推定方法の精度をさらに向上させていると考えられる。
【０１６２】
なお、本発明の位置推定方法は、上述の“半開放型環境”だけでなく、空間領域が赤外線を遮断する壁などで区切られた一般的な建物の内部などの“遮蔽型空間”にも適用できることは言うまでもない。そして、たとえば、本発明の位置推定方法の適用の舞台を病院内などに設定し、病院内で働く看護師の位置を推定するようにすれば、看護師の現在の位置に基づいて、看護師が現在に従事している看護業務などを予測することが可能となる。
【０１６３】
また、以上のテキストによる記述においては、使用しているエディタなどの都合上、図１３に示す表のように、文字の置き換えを行った。
【図面の簡単な説明】
【０１６４】
【図１】この発明の位置推定方法により位置が推定される買い物客が移動する空間領域が存在する環境の一例を示す図解図である。
【図２】本発明の位置推定方法に用いられる粒子フィルタのアルゴリズムを示すフロー図である。
【図３】エッジ遷移率を説明する図解図である。
【図４】新規な粒子フィルタの生成を説明する図解図である。
【図５】頂点（センサ頂点／領域頂点）と粒子フィルタとの距離について説明する図解図である。
【図６】２つの粒子フィルタの間の距離について説明する図解図である。
【図７】本発明の位置推定方法を実現するコンピュータによって実行される処理の手順の一例を示すフロー図である。
【図８】本発明の位置推定方法の有効性を証明する実験における半開放型環境を説明する図解図である。
【図９】本発明の位置推定方法の有効性を証明する実験に用いられるゲートセンサの構成の一例を示す図解図である。
【図１０】本発明の位置推定方法の有効性を証明する実験におけるネットワーク環境の一例を示す図解図である。
【図１１】本発明の位置推定方法を実現する位置推定装置としてのパーソナルコンピュータの構成の一例を示すブロック図である。
【図１２】本発明の位置推定方法の有効性を証明する実験の結果の表を示す図解図である。
【図１３】文字の置き換えを説明する図解図である。
【符号の説明】
【０１６５】
１０ …赤外線センサ
１２ …ゲートセンサ
２０ …赤外線タグ（赤外線発信機）
３０ …無線中継ポイント
４０ …パーソナルコンピュータ（位置推定装置）
１００ …陳列棚
Ｖ …頂点（センサ頂点／領域頂点）
ＶＳ …センサ頂点
ＶＲ …領域頂点
ｋ …粒子フィルタ
ｋ1 …粒子フィルタ
ｋ2 …粒子フィルタ
ｋnew …粒子フィルタ
Ｒ …検出範囲
【技術分野】
【０００１】
この発明は、位置推定方法および装置に関し、特に、１または２以上の粒子フィルタを用いて、空間領域を移動する対象の現在の位置を推定する位置推定方法および装置に関する。
【背景技術】
【０００２】
現在、人が活動する空間領域のいたるところにコンピュータが存在する状況となり、人とコンピュータとの間のインターフェースをどのように発展させるかが大きな課題となっている。現状では、人々の間にコンピュータを扱う能力の格差が存在するため、すべての人々がコンピュータによって提供される各種のサービスによる恩恵を等しく享受しているとはいい難い。
【０００３】
そこで、この恩恵をすべての人々が等しく享受することができる環境の実現が強く望まれている。この環境の実現への鍵となる技術として、コンピュータが周囲の人やオブジェクトの状態を認識し、その状態による環境に応じたサービスを能動的に提供する“コンテクストアウェアネス”がある。
【０００４】
このような技術の実現に向けて、人の姿勢推定、視線推定、音声認識などの数多くの状態推定に関する研究が行われている。そして、これらの状態推定の中でも、人の位置の推定は、人が存在する場所とその場所で起こしうる行動との相関が非常に高いことから、人の行動を認識する上で最も重要な推定の１つであると考えられている。
【０００５】
そのため、人の位置を推定する方法としてさまざまな方法が提案されているが、その１つとして、非特許文献１に記載されているように、粒子フィルタ（モンテカルロ・フィルタ）を用いるものがある。この従来の方法では、単一の粒子フィルタを用いて、移動するロボットの位置を推定しており、粒子フィルタの粒子の分散はロボットが移動する複数の空間領域の互いの繋がりの構造を示すボロノイ・グラフ上に制限されている。そして、この粒子フィルタで、ロボットの位置の予測と複数の空間領域からなる場所にまばらに設けられたセンサによるロボットの検出結果に基づく当該予測の修正とを繰り返すことによってロボットが存在する位置を推定（追跡）している。
【非特許文献１】Liao, L., Fox, D., Hightower, J., Kautz, H., Schulz, D.: Voronoi tracking: Location estimation using sparse and noisy sensor data. In: Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems. (2003)
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところが、このような粒子フィルタを用いて複数の空間領域からなる建物内を移動する人の現在の位置を推定する場合、人が所定の空間領域内のセンサに検出されない位置で長期間存在する状況が発生すると、人の検出による予測の修正が行われず、予測のみが行われるため、時間の経過に伴い粒子が方々に分散して人の存在位置の確率を示す正しい粒子の分布を維持できなくなるという問題がある。
【０００７】
また、このような粒子フィルタを用いて複数の空間領域からなる建物内を移動する人の現在の位置を推定する場合、センサの検出範囲が複数の空間領域にまたがっていてセンサが位置する空間領域と異なる空間領域に存在する人を誤検出したり、一連のセンサによる連続した人の検出の間に所定のセンサが正常に人を検出しなかったりして、ボロノイ・グラフ上において連続しない空間領域において突発的に人が検出された場合には、正しく人の現在の位置を推定（追跡）することができないという問題がある。
【０００８】
なお、センサの検出範囲の複数の空間領域へのまたがりは、たとえば、人が移動する場所がショッピングモールやコンビニエンスストアなどで、空間領域の区切りが陳列棚などの高さの低いものであり、所定の空間領域の天井に設けられた赤外線センサが、当該空間領域以外の空間領域に存在する人が携帯する赤外線発信機から発信された赤外線を受信する場合に起こりうる。空間領域を区切る陳列棚が、赤外線発信機が発信する赤外線を遮断しないためである。
【０００９】
それゆえに、この発明の主たる目的は、新規な、位置推定方法および装置を提供することである。
【００１０】
また、この発明の他の目的は、対象が一定の空間領域に長期間存在するなどしてセンサで検出されない場合がある環境であっても高い精度で対象の現在の位置を推定できる、位置推定方法および装置を提供することである。
【００１１】
さらに、この発明の他の目的は、対象が空間領域の移動可能経路上において連続しない空間領域で突発的に検出される環境であっても高い精度で対象の現在の位置を推定できる位置推定方法および装置を提供することである。
【課題を解決するための手段】
【００１２】
本発明は、上記の課題を解決するために、以下の構成を採用した。なお、括弧内の参照符号および補足説明などは、本発明の理解を助けるために後述する実施の形態との対応関係を示したものであって、本発明を何ら限定するものではない。
【００１３】
第１の発明は、空間領域の境界に設けられ当該境界を通過する対象を検出するセンサの位置を示すセンサ頂点、空間領域の位置を示す領域頂点、および領域頂点と当該領域頂点が示す空間領域の境界に設けられたセンサを示すセンサ頂点とを結ぶエッジからなるグラフ構造上に粒子の分布が制限され、粒子の確率分布に基づく対象の位置の予測とセンサによる対象の検出に基づく予測の修正とを繰り返す１または２以上の粒子フィルタを用いて、空間領域を移動する対象の位置を推定する位置推定方法であって、センサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタに属する粒子の確立分布に基づく対象の位置の予測を検出に基づいて修正し、当該粒子フィルタに属する粒子をグラフ構造上に伝搬させる伝搬ステップ（Ａ）、およびセンサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタ以外の粒子フィルタに属する粒子をグラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第１固定ステップ（Ｂ）を含む、位置推定方法である。
【００１４】
第１の発明では、位置推定方法は、空間領域の境界に設けられ当該境界を通過する対象を検出するセンサ（１０、１２）の位置を示すセンサ頂点（ＶＳ）、空間領域の位置を示す領域頂点（ＶＲ）、および領域頂点と当該領域頂点が示す空間領域の境界に設けられたセンサを示すセンサ頂点とを結ぶエッジ（Ｅ）からなるグラフ構造（Ｇ）上に粒子の分布が制限され、粒子の確率分布に基づく対象の位置の予測とセンサによる対象の検出に基づく予測の修正とを繰り返す１または２以上の粒子フィルタを用いて、空間領域を移動する対象の位置を推定する。
【００１５】
そして、この位置推定方法において、伝搬ステップ（Ａ）（Ｓ２９）では、センサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタに属する粒子の確立分布に基づく対象の位置の予測を検出に基づいて修正し、当該粒子フィルタに属する粒子をグラフ構造上に伝搬させ、第１固定ステップ（Ｂ）（Ｓ３１）では、センサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタ以外の粒子フィルタに属する粒子をグラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる。
【００１６】
第１の発明によれば、粒子フィルタは、伝搬ステップ（Ａ）が実行される伝播モードの他に、第１固定ステップ（Ｂ）が実行される固定モードを備えるので、センサによる対象の検出により予測が修正されない粒子フィルタの粒子がグラフ構造上の方々に分散することを防止し、高い精度で位置の推定を行うことができる。
【００１７】
第２の発明は、第１の発明に従属する発明であって、いずれのセンサにおいても対象が検出されないとき、すべての粒子フィルタについて各粒子フィルタに属する粒子をグラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第２固定ステップ（Ｃ）をさらに含む。
【００１８】
第２の発明では、第２固定ステップ（Ｃ）（Ｓ２５）において、いずれのセンサにおいても対象が検出されないとき、すべての粒子フィルタについて各粒子フィルタに属する粒子をグラフ構造（Ｇ）上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる。
【００１９】
第２の発明によれば、粒子フィルタの固定モードではさらに第２固定ステップが実行されるので、対象が一定の空間領域に長期間存在するなどしてセンサで検出されない場合に粒子がグラフ構造上の方々に分散することを防止し、高い精度で位置の推定を行うことができる。
【００２０】
第３の発明は、第１の発明または第２の発明に従属する発明であって、グラフ構造上において、粒子フィルタの位置から他のセンサによって検出されることなく対象が移動不可能な位置に存在するセンサ頂点が示すセンサが対象を検出した場合に、粒子の確率分布が当該センサ頂点を中心とする新規の粒子フィルタを生成する生成ステップ（Ｄ）、異なるセンサによる連続した所定回数の対象の検出のうちのいずれの検出によっても粒子の確立分布に基づく対象の位置の予測の修正が行われないとき、当該粒子フィルタを消滅させる消滅ステップ（Ｅ）、２以上の粒子フィルタがそれぞれ予測する対象の位置が同じであるとみなせるとき、当該２以上の粒子フィルタを結合する結合ステップ（Ｆ）、および１または２以上の粒子フィルタから対象の位置の推定に利用する粒子フィルタを選択する選択ステップをさらに含む位置推定方法である。
【００２１】
第３の発明では、生成ステップ（Ｄ）（Ｓ３３）で、グラフ構造（Ｇ）上において、粒子フィルタの位置から他のセンサによって検出されることなく対象が移動不可能な位置に存在するセンサ頂点（ＶＳ）が示すセンサが対象を検出した場合に、粒子の確率分布が当該センサ頂点を中心とする新規の粒子フィルタを生成し、消滅ステップ（Ｅ）（Ｓ４３）において、異なるセンサによる連続した所定回数の対象の検出のうちのいずれの検出によっても粒子の確立分布に基づく対象の位置の予測の修正が行われないとき、当該粒子フィルタを消滅させ、結合ステップ（Ｆ）（Ｓ３９）において、２以上の粒子フィルタがそれぞれ予測する対象の位置が同じであるとみなせるとき、当該２以上の粒子フィルタを結合し、選択ステップ（Ｇ）（Ｓ４５）において、１または２以上の粒子フィルタから対象の位置の推定に利用する粒子フィルタを選択する。
【００２２】
第３の発明によれば、人を検出したセンサと粒子フィルタの位置関係、異なるセンサによる連続した所定回数の対象の検出のうちのいずれかの検出によって予測の修正が行われたか否か、および複数の粒子フィルタの位置関係に基づいて、粒子フィルタの生成、消滅、結合を行うので、対象が空間領域の移動可能経路上において連続しない空間領域で突発的に検出された場合でも高い精度で対象の現在の位置を推定することができる。
【００２３】
第４の発明は、第３の発明に従属する発明であって、選択ステップ（Ｇ）では、属する粒子の確立分布に基づく予測の修正に寄与した検出の数がより多く、属する粒子の確立分布に基づく予測の修正に寄与した検出が行われたセンサを示すセンサ頂点の位置の変化の履歴が、検出を行ったすべてのセンサのそれぞれを示すセンサ頂点の位置の変化の履歴とよりよく一致する粒子フィルタを選択する。
【００２４】
第４の発明では、選択ステップ（Ｇ）（Ｓ４５）において、属する粒子の確立分布に基づく予測の修正に寄与した検出の数がより多く、属する粒子の確立分布に基づく予測の修正に寄与した検出が行われたセンサを示すセンサ頂点（ＶＳ）の位置の変化の履歴が、検出を行ったすべてのセンサのそれぞれを示すセンサ頂点の位置の変化の履歴とよりよく一致する粒子フィルタを選択する。
【００２５】
第４の発明によれば、複数存在する粒子フィルタの中から最も確かに対象の位置を予測したであろう粒子フィルタを選択するので、複数存在する粒子フィルタを用いて精度よく対象の現在の位置を推定することができる。
【００２６】
第５の発明は、空間領域の境界に設けられ当該境界を通過する対象を検出するセンサの位置を示すセンサ頂点、空間領域の位置を示す領域頂点、および領域頂点と当該領域頂点が示す空間領域の境界に設けられたセンサを示すセンサ頂点とを結ぶエッジからなるグラフ構造上に粒子の分布が制限され、粒子の確率分布に基づく対象の位置の予測とセンサによる対象の検出に基づく予測の修正とを繰り返す１または２以上の粒子フィルタを用いて、空間領域を移動する対象の位置を推定する位置推定装置であって、センサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタに属する粒子の確立分布に基づく対象の位置の予測を検出に基づいて修正し、当該粒子フィルタに属する粒子をグラフ構造上に伝搬させる伝搬手段、およびセンサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタ以外の粒子フィルタに属する粒子をグラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第１固定手段を備える、位置推定装置である。
【００２７】
第５の発明では、位置推定装置は、空間領域の境界に設けられ当該境界を通過する対象を検出するセンサ（１０、１２）の位置を示すセンサ頂点（ＶＳ）、空間領域の位置を示す領域頂点（ＶＲ）、および領域頂点と当該領域頂点が示す空間領域の境界に設けられたセンサを示すセンサ頂点とを結ぶエッジ（Ｅ）からなるグラフ構造（Ｇ）上に粒子の分布が制限され、粒子の確率分布に基づく対象の位置の予測とセンサによる対象の検出に基づく予測の修正とを繰り返す１または２以上の粒子フィルタを用いて、空間領域を移動する対象の位置を推定する。
【００２８】
そして、この位置推定装置では、伝搬手段（Ａ）（Ｓ２９）が、センサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタに属する粒子の確立分布に基づく対象の位置の予測を検出に基づいて修正し、当該粒子フィルタに属する粒子をグラフ構造上に伝搬させ、第１固定手段（Ｂ）（Ｓ３１）が、センサにおいて対象が検出されたとき、当該センサを示すセンサ頂点とグラフ構造上において最も距離が近い粒子フィルタ以外の粒子フィルタに属する粒子をグラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる。
【００２９】
第５の発明によれば、粒子フィルタは、粒子の伝搬が実行される伝播モードの他に、粒子の収束が実行される固定モードを備えるので、センサによる対象の検出により予測が修正されない粒子フィルタの粒子がグラフ構造上の方々に分散することを防止し、高い精度で位置の推定を行うことができる。
【００３０】
第６の発明は、第５の発明に従属する発明であって、いずれのセンサにおいても対象が検出されないとき、すべての粒子フィルタについて各粒子フィルタに属する粒子をグラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第２固定手段をさらに備える。
【００３１】
第６の発明では、第２固定手段（Ｓ２５）が、いずれのセンサにおいても対象が検出されないとき、すべての粒子フィルタについて各粒子フィルタに属する粒子をグラフ構造（Ｇ）上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる。
【００３２】
第６の発明によれば、粒子フィルタの固定モードではさらに第２固定手段により粒子の収束が実行されるので、対象が一定の空間領域に長期間存在するなどしてセンサで検出されない場合に粒子がグラフ構造上の方々に分散することを防止し、高い精度で位置の推定を行うことができる。
【００３３】
第７の発明は、第５の発明または第６の発明に従属する発明であって、グラフ構造上において、粒子フィルタの位置から他のセンサによって検出されることなく対象が移動不可能な位置に存在するセンサ頂点が示すセンサが対象を検出した場合に、粒子の確率分布が当該センサ頂点を中心とする新規の粒子フィルタを生成する生成手段、異なるセンサによる連続した所定回数の対象の検出のうちのいずれの検出によっても粒子の確立分布に基づく対象の位置の予測の修正が行われないとき、当該粒子フィルタを消滅させる消滅手段、２以上の粒子フィルタがそれぞれ予測する対象の位置が同じであるとみなせるとき、当該２以上の粒子フィルタを結合する結合手段、および１または２以上の粒子フィルタから対象の位置の推定に利用する粒子フィルタを選択する選択手段をさらに備える位置推定装置である。
【００３４】
第７の発明では、生成手段（Ｓ３３）が、グラフ構造（Ｇ）上において、粒子フィルタの位置から他のセンサによって検出されることなく対象が移動不可能な位置に存在するセンサ頂点（ＶＳ）が示すセンサが対象を検出した場合に、粒子の確率分布が当該センサ頂点を中心とする新規の粒子フィルタを生成し、消滅手段（Ｓ４３）が、異なるセンサによる連続した所定回数の対象の検出のうちのいずれの検出によっても粒子の確立分布に基づく対象の位置の予測の修正が行われないとき、当該粒子フィルタを消滅させ、結合手段（Ｓ３９）が、２以上の粒子フィルタがそれぞれ予測する対象の位置が同じであるとみなせるとき、当該２以上の粒子フィルタを結合し、選択手段（Ｓ４５）が、１または２以上の粒子フィルタから対象の位置の推定に利用する粒子フィルタを選択する。
【００３５】
第７の発明によれば、人を検出したセンサと粒子フィルタの位置関係、異なるセンサによる連続した所定回数の対象の検出のうちのいずれかの検出によって予測の修正が行われたか否か、および複数の粒子フィルタの位置関係に基づいて、粒子フィルタの生成、消滅、結合を行うので、対象が空間領域の移動可能経路上において連続しない空間領域で突発的に検出された場合でも高い精度で対象の現在の位置を推定することができる。
【００３６】
第８の発明は、第７の発明に従属する発明であって、選択手段は、属する粒子の確立分布に基づく予測の修正に寄与した検出の数がより多く、属する粒子の確立分布に基づく予測の修正に寄与した検出が行われたセンサを示すセンサ頂点の位置の変化の履歴が、検出を行ったすべてのセンサのそれぞれを示すセンサ頂点の位置の変化の履歴とよりよく一致する粒子フィルタを選択する。
【００３７】
第８の発明では、選択手段（Ｓ４５）は、属する粒子の確立分布に基づく予測の修正に寄与した検出の数がより多く、属する粒子の確立分布に基づく予測の修正に寄与した検出が行われたセンサを示すセンサ頂点（ＶＳ）の位置の変化の履歴が、検出を行ったすべてのセンサのそれぞれを示すセンサ頂点の位置の変化の履歴とよりよく一致する粒子フィルタを選択する。
【００３８】
第８の発明によれば、複数存在する粒子フィルタの中から最も確かに対象の位置を予測したであろう粒子フィルタを選択するので、複数存在する粒子フィルタを用いて精度よく対象の現在の位置を推定することができる。
【発明の効果】
【００３９】
この発明によれば、センサによる対象の検出により予測が修正されない粒子フィルタの粒子がグラフ構造上の方々に分散することを防止し、高い精度で位置の推定を行うことができる。
【００４０】
また、この発明によれば、対象が一定の空間領域に長期間存在するなどしてセンサで検出されない場合がある環境でも高い精度で対象の現在の位置を推定できる。
【００４１】
さらに、この発明によれば、対象が空間領域の移動可能経路上において連続しない空間領域で突発的に検出される環境であっても高い精度で対象の現在の位置を推定できる。
【００４２】
この発明の上述の目的、その他の目的、特徴および利点は、図面を参照して行う以下の実施例の詳細な説明から一層明らかとなろう。
【発明を実施するための最良の形態】
【００４３】
本発明の位置推定方法の一例として以下に説明する位置推定方法は、たとえば、図１に示すように、ショッピングモールなどにおいて、商品の陳列棚１００によって区切られた複数の空間領域（たとえば空間領域α、β、γ）内を移動する買い物客の現在の位置の推定を行う。このショッピングモールでは、空間領域Ａを成す（空間領域αに面している）陳列棚１００には、たとえば、ネコ用の缶詰のキャットフードが陳列され、空間領域βを成す陳列棚１００には、たとえば、ネコ用の袋詰めのキャットフードが陳列され、空間領域γを成す陳列棚１００には、たとえば、イヌ用の袋詰めのドックフードが陳列されるというように、各空間領域を成す陳列棚１００ごとに陳列されている商品が異なっている。
【００４４】
このような空間領域の各出入り口（境界）のたとえば天井に、一対の赤外線センサ１０からなるゲートセンサ１２を配置する。ゲートセンサ１２は、一方の赤外線センサ１０が隣接する空間領域の一方側に位置し、他方の赤外線センサ１０が隣接する空間領域の他方側に位置するように配置される。そして、陳列棚１００によって形成されたこれらの空間領域内を移動する買い物客に赤外線発信機（不図示）を携帯させる。たとえば、買い物カゴ（不図示）に赤外線発信機を取り付けるようにしてもよい。
【００４５】
このようにして、買い物客が携帯する赤外線発信機から発信された赤外線を、赤外線センサ１０で受信することによって、買い物客の位置を検出し、買い物客が存在する空間領域を特定することによって、たとえば、買い物客が現在どの商品の購入を検討しているかを知ることができる。また、１つの空間領域内に存在し続ける時間を計測することによって、買い物客がどの程度の時間、所定の商品の購入を検討していたかを知ることができる。なお、買い物客が携帯する赤外線発信機から発信される赤外線には買い物客を識別するＩＤ情報（以下、“識別ＩＤ”と呼ぶ。）が含まれ、複数存在する買い物客のぞれぞれの位置を推定することができる。
【００４６】
このようなシステムにおいて、買い物客を検出した赤外線センサ１０の位置をそのまま、買い物客が現在に存在する位置であると判断できれば問題はない。しかし、ショッピングモールなどでは、空間領域を区切る陳列棚１００は天井まで届いておらず、また、赤外線発信機から発信される赤外線を遮断するような構造ではないので、天井に設置された赤外線センサ１０の赤外線の検出範囲Ｒ（図１の斜線を施した楕円の部分）は、赤外線センサ１０が設置されている空間領域の範囲をはみ出して他の空間領域にまたがっている。（このように、赤外線が空間領域を区切る陳列棚１００や壁によって遮断されない環境を“半開放型環境”と呼ぶ。）そのため、たとえば、買い物客が空間領域αから赤外線センサ（５）１０および赤外線センサ（６）１０を通過して空間領域γに入り、空間領域γの図面上部を移動した場合、空間領域γの内部で、赤外線センサ（３）１０および赤外線センサ（４）１０によって赤外線が検出され、買い物客が空間領域γに存在するにもかかわらず、買い物客が空間領域γから直接的に空間領域βに移動したと誤判断する可能性がある。
【００４７】
また、買い物客の移動を追跡している場合において、買い物客がゲートセンサ１２を通過する際に、買い物カゴなどに取り付けられた赤外線発信機から赤外線が下方向や横方向に発射されたときには、通過するゲートセンサ１２の赤外線センサ１０によって赤外線が受信されない事態が発生する。このような場合には、受信漏れを起こしたのとは別の赤外線センサ１０で次に買い物客が検出されると、買い物客が連続しない空間領域を移動したこととなり、正常に買い物客の移動を追跡することができない。
【００４８】
このような誤判断を防止し、また、正常に対象としての買い物客を追跡するために、いわゆる粒子フィルタを用いる。粒子フィルタは高次元の一般状態空間モデルに対するフィルタと平滑化のために提案されたものであり、条件付分布をその分布からの多数の実現値で近時表現するものであり、モンテカルロ・フィルタとも呼ばれる。
【００４９】
より具体的には、粒子フィルタは、追跡対象（ここでは、買い物客）の状態を、Ｎ個の離散的な状態ベクトルｘ(i)tとこれに対応する重みw(i)tを持つ多数の粒子{ｘ(i)t, w(i)t }(i = １，…，N)を用いて離散変数の集合に近似して逐次的に推定する方法である。
【００５０】
状態ベクトルｘtを非線形関数Ft、システムノイズｖtを用いて表した式（１）をシステムモデルと呼び、観測ベクトルｙtを非線形関数Ht、観測ノイズｗtを用いて表した式（２）を観測モデルと呼ぶ。そして、状態ベクトルｘtと観測ベクトルｙtとの関係を示すシステムモデルと観測モデルとの組を一般状態空間モデルと呼ぶ。なお、システムモデルは状態予測モデルとも呼ばれる。
【００５１】
［システムモデル］ ｘt ＝Ft(Xt-1,ｖt) (1)
［観測モデル］ ｙt ＝Ht(ｘt,ｗt) (2)
これらのシステムモデルおよび観測モデルは、状態ｘt-1，ｘtが与えられたときの条件付分布Qt，Ｒtを用いて以下の式（３）および式（４）のように一般化される。
【００５２】
［システムモデル］ ｘt 〜Qt(・|ｘt-1) (3)
［観測モデル］ ｙt 〜 Ｒt(・|ｘt) (4)
粒子フィルタは、これらの式（３）および式（４）に示す、システムモデルと観測モデルを用いて、観測対象（ここでは買い物客）の状態の予測と、実際の観測結果に基づいた状態の予測の修正を繰り返す。状態の予測と予測の修正は、図２に示すフロー図の手順に従って実行される。
【００５３】
このフロー図に示すように、手順では、まず、ステップＳ１では、ｉ＝１，…，ＮのＮ個の粒子からなる粒子の集団の初期状態Ｘ0＝{ｘ(1)0,…,ｘ(N)0}を生成する。
【００５４】
そして、ステップＳ３では、変数“ｔ”を“１”だけインクリメントする。この変数“ｔ”は“１”〜“Ｔ”までの値をとり、時間をカウントするための変数である。ステップＳ３からステップＳ１１までの手順が、変数“ｔ”が“Ｔ”に等しくなるまで繰り返される。なお、変数“ｔ”の初期値は“０”である。
【００５５】
次に、ステップＳ５では、すべての“ｉ”（粒子）について、式（５）のシステムモデルに基づいて、状態ｘ^(i)tを予測し、
【００５６】
【数１】
【００５７】
また、観測によって得たｙtを用いて、すべての“ｉ”（粒子）について、式（６）の観測モデルに基づいて、粒子の重みｗ(i)tを計算する。
【００５８】
【数２】
【００５９】
ここで、粒子フィルタを用いて買い物客の位置を推定する場合には、“観測”とは、赤外線センサ１０によって買い物客が検出されることであり、“ｙt”は買い物客が検出された空間領域の位置などの情報である。
【００６０】
次に、ステップＳ７では、式（７）に基づいて、各粒子の重みの合計を計算する。
【００６１】
【数３】
【００６２】
そして、ステップＳ９では、すべての“ｉ”（粒子）について、式（８）に基づいて、ステップＳ７で求めた重みの合計に対する、状態（粒子）ｘ^(i)tの重みｗ(i)tの割合ｗ~(i)tを計算する。つまり、重みｗ(i)t（ｗ~(i)t）の合計が“１”となるように正規化する。なお、“ｗ~(i)t”は、“ｉ”番目の粒子の“importance weight”と呼ばれる。
【００６３】
【数４】
【００６４】
さらに、時刻“ｔ”における粒子の集団Ｘ^t＝{ｘ^(1)t,…,ｘ^(N)t}の中からｘ^(i)tをｗ~(i)tの確率で復元抽出する。この復元抽出をリサンプリングと呼ぶ。そして、リサンプリングされたN個の粒子からなる時刻“ｔ”における新たな粒子の集団Xt＝{ｘ(1)t,…,ｘ(N)t}を生成する。このようにして、状態ｘ^(i)tの予測が観測（検出）された“ｙt”によって修正される。
【００６５】
こうして生成された時刻“Ｔ”における粒子の集団XＴ＝{ｘ(1)Ｔ,…,ｘ(N)Ｔ}において、最も大きい重みを持つ（最も尤度が高い）粒子の状態ｘ(i)Ｔが示す位置が時刻“Ｔ”における対象（買い物客）の現在の位置として推定される。
【００６６】
本発明の位置推定方法で用いられる粒子フィルタは、属する粒子の分布が、空間領域の位置を示す領域頂点ＶＲと、赤外線センサ１０の位置を示すセンサ頂点ＶＳと、領域頂点ＶＲおよびセンサ頂点ＶＳ並びにセンサ頂点ＶＳおよびセンサ頂点ＶＳを結ぶエッジＥによって決定されるグラグ構造Ｇ上に制限される。
【００６７】
図１においては、領域頂点ＶＲを“□”で、センサ頂点ＶＳを“○”で、エッジＥを太線でそれぞれ示している。図１からもわかるように、領域頂点ＶＲは、各空間領域に１つ設定され、その空間領域に隣接するセンサ頂点ＶＳに対するハブ（ｈｕｂ）の役目を果たす。また、センサ頂点ＶＳは、赤外線センサ１０の受信部の位置を示し、グラフ構造Ｇ上で唯一、対象としての買い物客が検出される場所である。赤外線センサ１０で買い物客が検出されることを、センサ頂点ＶＳで“観測”が得られると表現する。
【００６８】
本発明の位置推定方法では、得られた“観測”や粒子フィルタの状況などに応じて複数の粒子フィルタを生成し、また、複数の粒子フィルタの結合や粒子フィルタの消滅を行う。より具体的には、時刻ｔにおいて“観測”が得られたセンサ頂点ＶＳの位置が、グラフ構造Ｇ上において、時刻ｔ−１における既存の粒子フィルタの位置から他の１つ以上のセンサ頂点ＶＳにおいて“観測”されることなく買い物客が移動することができない位置である場合に、時刻ｔにおいて“観測”が得られたセンサ頂点ＶＳを粒子の確率分布の中心として新規の粒子フィルタを生成する。このような位置のセンサ頂点ＶＳにおいて得られる“観測”を“突発的な観測”と呼ぶ。
【００６９】
そして、複数の粒子フィルタのそれぞれが予測する買い物客の位置が同じ空間領域内であるとみなせる場合に、これらの粒子フィルタを結合して１つの粒子フィルタとする。
【００７０】
また、複数の粒子フィルタが存在する場合には、センサ頂点ＶＳにおける“観測”は、“観測”が得られたセンサ頂点ＶＳの位置から最も近い粒子フィルタに対してのみ“観測”として影響を与える。つまり、予測を修正する。このように“観測”によって粒子フィルタが影響を受けて予測を修正することを、粒子フィルタが“観測を勝ち取る”と表現する。
【００７１】
さらに、異なるセンサ頂点ＶＳで所定の回数だけ連続して発生する“観測”について、“観測”を一度も勝ち取らなかった粒子フィルタは消滅させる。
【００７２】
詳細については後述するが、このように、粒子フィルタの生成、結合、消滅を行うことによって、赤外線センサ１０による誤検出が発生しても買い物客の現在の位置を高い精度で推定することができる。
【００７３】
また、“観測”を勝ち取った粒子フィルタは“観測”による影響に基づいて予測を修正して粒子をグラフ構造Ｇ上に伝搬させるが、“観測”を勝ち取らなかった粒子フィルタは、粒子を最も近い領域頂点ＶＲの周辺に収束させる。なお、いずれのセンサ頂点ＶＳにおいても観測が得られない場合は、すべての粒子フィルタの粒子を最も近い領域頂点ＶＲの周辺に収束させる。この粒子フィルタの粒子をグラフ構造Ｇ上を伝搬させる状態を粒子フィルタの“伝搬モード”と呼び、粒子を領域頂点ＶＲの周辺に収束させる状態を粒子フィルタの“固定モード”と呼ぶ。
【００７４】
このように、粒子フィルタに伝搬モードの他に固定モードを与えることによって、“観測”を勝ち取らなかった粒子フィルタの粒子が時間経過とともにグラフ構造Ｇ上の方々に分散することを防止することができる。
【００７５】
本発明の位置推定方法で用いられる粒子フィルタは、伝搬モードのシステムモデルを式（９）ないし式（１１）で定めることによって、粒子の分布をグラフ構造Ｇ上に制限する。なお、本発明の位置推定方法で用いられる粒子フィルタのシステムモデルには、上述のように伝搬モードと固定モードとがあるが固定モードについては後述する。
【００７６】
【数５】
【００７７】
Ｐ^(ｘt｜ｘt-1)は、粒子が時刻“ｔ−１”においてある状態ｘt-1にあった場合に、時刻ｔで状態ｘtに変化する確率を示している。Ｄ(ｘt,ｘt-1)は、グラフ構造Ｇ上における２つの粒子（状態）の距離を示しており、式（１１）からわかるように、Ｐ^(ｘt｜ｘt-1)は、２つの粒子の状態ｘt，ｘt-1の間のグラフ構造Ｇ上における距離に基づいて決定される。なお、２つの粒子（状態）間の距離Ｄ(ｘt,ｘt-1)は、経験的に平均“０”、分散“σd=０．３”の正規分布に従うとしている。
【００７８】
ところで、本発明の位置推定方法で用いられる粒子フィルタの粒子は、式（１２）に示すようなパラメータを持つ。
【００７９】
粒子状態空間 ｘ＝＜ｅ，ｄ，ｍ＞ (12)
式（１２）において、“ｅ”は粒子が現在存在するエッジＥであり、“ｄ”は粒子が現在存在するエッジＥの端点からの距離であり、“ｍ”は粒子フィルタの現在の動作モード（伝搬モード／固定モード）である。
【００８０】
そして、グラフ構造Ｇ上における２つの粒子（状態）間の距離Ｄ(ｘt,ｘt-1)は、式（１３）によって決定される。
【００８１】
【数６】
【００８２】
式（１３）によると、異なる２つの粒子（状態）が同一エッジＥ上にある場合（ｅi ＝ ｅj）は、単純に、そのエッジＥ上において距離を計算する。一方、異なる２つの粒子（状態）が同一エッジＥ上に存在しない場合（otherwise）は、２つの粒子（状態）を結ぶ経路をどのように選択するかによって距離が異なってくるので、経路の距離が最短となるエッジＥを選択する。式（１３）における、“Σk|ｅk|”は、点“ｄi”と点“ｄj”との間に存在する１つの経路に含まれるエッジＥの距離の和を示している。なお、領域頂点ＶＲとセンサ頂点ＶＳをつなぐエッジＥの距離を一様に“０．５”とし、センサ頂点ＶＳとセンサ頂点ＶＳをつなぐエッジＥの距離を一様に“１．０”とする。
【００８３】
式（１０）におけるＰ(ｅt|ｅt-1)は、図３に示すように、粒子がエッジＥ（ｅi）の分岐点である領域頂点ＶＲに到達したときに、次に所定のエッジＥ（ｅi、ｅj、ｅkのいずれか）に遷移する確率（以下、“遷移確率”と呼ぶ。）を表しており、式（１４）で決定される。
【００８４】
【数７】
【００８５】
ここで、“時刻ｔにおいてセンサ頂点v(j)Ｓで“観測”されたＩＤ受信頻度（freq(v(j)Ｓ,t)）”とは、ある固定の時間間隔（ウィンドウ幅）“ｔw”を設定したとき、［ｔ−ｔw，ｔ］の時間内に、センサ頂点v(j)Ｓに位置する赤外線センサ１０によって、その買い物客の識別ＩＤが“観測”（検出）された回数を示している。
【００８６】
また、式（１４）における“α”は、買い物客の識別ＩＤがまったく観測されない赤外線センサ１０のセンサ頂点ＶＳが接続されたエッジＥへの遷移確率が完全に“０”になることを防止するための値である。つまり、現実には、買い物客が赤外線センサ１０の近くに移動したにもかかわらず、赤外線センサ１０の誤った“観測”によって、“観測”が得られない場合が考えられることに対応して“α”という一定値のゲタをはかせている。
【００８７】
なお、式（１４）における右辺は、確率ではないので、実際にコンピュータなどで、Ｐ(ｅt,ｅt-1)を計算する場合には、すべてのエッジＥ（１，…，Ne）について、式（１４）の右辺を計算し、計算された各エッジＥについての右辺を、右辺の各右辺の合計に対する割合と置き換えて、置き換えられた各右辺の合計が“１”となるように正規化したものを用いる。
【００８８】
このように、エッジＥの遷移確率Ｐ(ｅt,ｅt-1)は、センサ頂点ＶＳ（赤外線センサ１０）における買い物客の識別ＩＤの受信頻度（観測回数）に基づいて動的に変更される。
【００８９】
伝搬モードのシステムモデルは以上に説明した通りであるが、観測モデルは、式（１５）によって決定される。
【００９０】
【数８】
【００９１】
この式からわかるように、粒子の尤度は、“ＩＤ受信頻度／粒子から観測されたセンサ頂点ＶＳまでのホップ数”によって決定される。そして、式（１５）は、同時刻において、複数のセンサ頂点ＶＳ上で“観測”が得られた場合、状態ｘtの粒子の尤度は、複数の“観測”で得られた尤度の和によって計算されることを示している。
【００９２】
そして、先述の“importance weight”は、式（１５）を利用して、式（１６）によって決定される。
【００９３】
【数９】
【００９４】
この“importance weight”は、先述の通り、次の時刻における粒子フィルタに属する粒子の分布を決定するリサンプリングに利用される。
【００９５】
以上が、伝搬モードにおけるシステムモデルと観測モデルであるが、固定モードにおけるシステムモデルは式（１７）によって決定される。
【００９６】
【数１０】
【００９７】
式（１７）からわかるように、粒子フィルタの固定モードでは、すなわち、粒子フィルタが“観測”を勝ち取らない状態においては、その粒子フィルタに属する粒子をすべて、当該粒子フィルタに最も近い領域頂点ＶＲの周辺に収束させる。つまり、粒子フィルタに属する粒子は、当該粒子フィルタが“観測”を勝ち取らない期間、最近傍の領域頂点ＶＲを中心とした正規分布に従って分散される。なお、この場合の正規分布の分散は伝搬モードと同様に経験上“σd＝０．３”とする。
【００９８】
本発明の位置推定方法では、以上に説明したような伝搬モードおよび固定モードのシステムモデルと観測モデルとに基づく粒子フィルタを用いて、上述したように、たとえば、ショッピングモール内を移動する買い物客の現在の位置を推定する。
【００９９】
しかし、この例のように、空間領域の出入り口に設けられた赤外線センサ１０によるまばらな“観測”しか得られない環境では、得られる“観測”が少ないことや誤った“観測”が原因となり、現在の時刻までの“観測”に基づいて一意に買い物客の位置を決定することができない場合が発生する。このような場合、粒子の尤度が示す買い物客の位置の事後分布は、多峰性を有すると考えられる。
【０１００】
そこで、本発明の位置推定方法では、新たな粒子フィルタの生成、粒子フィルタの結合、および粒子フィルタの消滅を繰り返すことによって、多峰性を有する事後分布に対応する。
【０１０１】
そして、複数の粒子フィルタが存在する場合には、詳しくは後述するが、尤もらしい買い物客の移動軌跡に対応する粒子フィルタを選択することによって、高精度に買い物客の位置の推定を行う。
【０１０２】
先述したが、図４に示すように、グラグ構造Ｇ上において、領域頂点ＶＲとセンサ頂点ＶＳを接続するエッジＥの距離を一様に“０．５”とし、隣接するセンサ頂点ＶＳ同士を接続するエッジＥの距離を一様に“１．０”とする。
【０１０３】
そして、図４に示すように、新たに“観測”が得られたセンサ頂点ＶＳと既存の粒子フィルタとの距離が“２．０”以上である場合には、粒子が、新たに観測が得られたセンサ頂点ＶＳを中心とした正規分布に従う新たな粒子フィルタを生成する。なお、このように、粒子フィルタとの距離が“２．０”以上であるセンサ頂点ＶＳにおいて得られる“観測”が、上述した“突発的な観測”である。
【０１０４】
ここで、図５に示すような、センサ頂点ＶＳと粒子フィルタｋとの距離を式（１８）で決定する。
【０１０５】
【数１１】
【０１０６】
式（１８）からわかるように、あるセンサ頂点ＶＳとある粒子フィルタｋとの距離は、粒子フィルタｋに属するすべての粒子とあるセンサ頂点ＶＳとの間の距離の合計を、粒子フィルタｋに属する粒子の総数で割って得られる平均の距離によって表現する。
【０１０７】
したがって、式（１８）によって得られる値が“２．０”以上である場合に、新たな粒子フィルタを生成する。なお、粒子とあるセンサ頂点ＶＳとの間の距離は、粒子が存在するエッジＥの端点からの距離ｄ（式（１２）参照）と、粒子が存在するエッジＥに接続されている頂点Ｖ（センサ頂点ＶＳ／領域頂点ＶＲ）およびあるセンサ頂点ＶＳの距離に基づいて求めることができる。
【０１０８】
また、２つの粒子フィルタのグラフ構造Ｇ上における距離が“２．０”未満である場合には、２つの粒子フィルタが予測する買い物客の現在の位置は同一であるとみなし、これらの２つの粒子フィルタを結合して新たな１つの粒子フィルタを生成する。
【０１０９】
ここで、図６に示すような、２つの粒子フィルタｋ1と粒子フィルタｋ2との間の距離を、式（１８）を用いた式（１９）で決定する。
【０１１０】
【数１２】
【０１１１】
式（１９）からわかるように、２つの粒子フィルタｋ1と粒子フィルタｋ2との間の距離は、基準となる頂点Ｖ（センサ頂点ＶＳ／領域頂点ＶＲ）および粒子フィルタｋ1の距離と、基準となる頂点Ｖ（センサ頂点ＶＳ／領域頂点ＶＲ）および粒子フィルタｋ2の距離との和から計算される。ここで、粒子フィルタｋ1と粒子フィルタｋ2とを結ぶグラフ構造Ｇ上の経路が複数ある場合は、最短の経路上の頂点Ｖ（センサ頂点ＶＳ／領域頂点ＶＲ）を基準とする。
【０１１２】
なお、２つの粒子フィルタｋ1と粒子フィルタｋ2とを結合して新たな粒子フィルタｋnewを生成する際には、粒子フィルタｋ1の粒子の集団X(k1)tと粒子フィルタｋ2の粒子の集団X(k2)tとから尤度が高い順に粒子を選び出して粒子フィルタｋnewの粒子の集団X(new)tとする。
【０１１３】
これらのようにして生成された粒子フィルタは、ある一定の回数、たとえば３回以上だけ連続して異なるセンサ頂点ＶＳで得られる“観測”について、一度も“観測”を勝ち取らなかった場合には消滅させる。このように粒子フィルタを消滅させることによって、赤外線センサ１０による誤った“観測”を排除することができる。
【０１１４】
以上に説明したように、本発明の位置推定方法では、複数の粒子フィルタが存在する可能性があるが、複数の粒子フィルタが存在する場合には、先述のように、尤も確からしい買い物客の移動軌跡に対応する粒子フィルタに基づいて買い物客の現在の位置を推定する。
【０１１５】
つまり、各粒子フィルタが勝ち取った“観測”の履歴、具体的には“観測”に基づく買い物客の空間領域の通過方向の履歴、および“観測”の数が、各粒子フィルタ毎に記録される。そして、“観測”の数がより多く、より一貫性のある通過方向の履歴が記録されている粒子フィルタを尤も確からしい買い物客の移動軌跡に対応する粒子フィルタであるとする。ここで、通過方向の履歴とは、粒子フィルタが勝ち取った“観測”を得たセンサ頂点ＶＳの位置とその“観測”の順序からなる“観測”の位置の変化の記録である。また、より一貫性のある通過方向の履歴とは、“観測”の位置の変化が、グラフ構造Ｇ上において“観測”を得たすべてのセンサ頂点ＶＳの位置とその“観測”の順序からなる“観測”の位置の変化とよりよく一致する履歴である。
【０１１６】
また、２つの粒子フィルタを結合して１つの新たな粒子フィルタを生成する場合には、それぞれの粒子フィルタに対応つけて記録されている買い物客の空間領域の通過方向の履歴と“観測”の数とを１つにまとめる必要がある。この際には、“観測”の数については、より数の多い“観測”の数を、通過方向の履歴については、より一貫性のある通過方向の履歴を、新たな粒子フィルタの“観測”の数、よび通過方向の履歴とする。
【０１１７】
なお、買い物客の通過方向は、ゲートセンサ１２に含まれる一対の赤外線センサ１０による買い物客が携帯する赤外線発信機から発せられる赤外線の受信の順序によって知ることができる。
【０１１８】
このように、より多くの“観測”を勝ち取り、かつ、より一貫性のある通過方向の履歴を有し、尤も確からしい買い物客の移動軌跡に対応する粒子フィルタを“尤も確からしい粒子フィルタ”と呼ぶ。
【０１１９】
図７は以上に説明した、本発明の位置測定方法を、コンピュータを用いて実現する場合に、当該コンピュータによって実行される処理手順を逐次的に示したフロー図である。このフロー図にしたがって、コンピュータで実行される処理を説明する。図７のフロー図に示す処理を実行するコンピュータは一般的で周知のパーソナルコンピュータなどである。赤外線センサ１０で買い物客を検出した旨を示す情報をパーソナルコンピュータに与える方法（図１０参照）やパーソナルコンピュータの構成（図１１参照）などについては後述する。なお、以下のフロー図に示す処理は適宜に並列に実行してもかまわない。また、このコンピュータの記憶装置には、先述の各粒子フィルタが勝ち取った“観測”の数と、各粒子フィルタが勝ち取った“観測”に基づく通過方向の履歴が記録される。
【０１２０】
まず、コンピュータのＣＰＵは、ステップＳ２１で、変数“ｔ”を“１”だけインクリメントする。この変数“ｔ”は、コンピュータで本発明の位置測定方法を実行する際の処理単位となる時間をカウントするものであり、コンピュータのＣＰＵは、ステップＳ２１からステップＳ４５の処理を変数“ｔ”が“１”だけカウントされる度に実行する。なお、この変数“ｔ”は、図２のフロー図において示した変数“ｔ”と同じとみなせる。
【０１２１】
ステップＳ２３では、いずれかの赤外線センサ１０（センサ頂点ＶＳ）において、“観測”が得られたか否か、つまり、赤外線センサ１０が、買い物客が携帯する赤外線発信機から発信された赤外線を検出したか否かを判断する。
【０１２２】
“観測”が得られなかったと判断すると（ステップＳ２３：ＮＯ）、ＣＰＵはステップＳ２５で、存在するすべての粒子フィルタを固定モードとし、各粒子フィルタの粒子を最も近くの領域頂点ＶＲの周辺に収束させる。そして、ステップＳ４５に進む。
【０１２３】
一方、ステップＳ２３で“観測”が得られたと判断すると（ステップＳ２３：ＹＥＳ）、ＣＰＵは、次に、ステップＳ２７において、式（１８）による演算に基づいて“観測”が得られた赤外線センサ１０の位置を示すセンサ頂点ＶＳからの距離が“２．０”より短い粒子フィルタが存在するか否かを判断する。
【０１２４】
距離が“２．０”より短い粒子フィルタが存在すると判断する（ステップＳ２７：ＹＥＳ）と、ステップＳ２９において、“観測”が得られたセンサ頂点ＶＳからの距離が最も近い粒子フィルタ、つまりステップＳ２３において得られたと判断された“観測”を勝ち取った粒子フィルタを伝搬モードにする。そして、ステップＳ３１において、“観測”を勝ち取らなかったすべての粒子フィルタを固定モードにする。なお、“観測”を勝ち取り、伝搬モードとなった粒子フィルタについては、式（９）ないし式（１１）のシステムモデルおよび式（１５）の観測モデルを用いて、図２に示したステップＳ５ないしステップＳ９の処理の手順が実行される。
【０１２５】
一方、ステップＳ２７において、“観測”が得られたセンサ頂点ＶＳからの距離が“２．０”より短い粒子フィルタが存在しないと判断すると（ステップＳ２７：ＮＯ）、ステップＳ３３において、“観測”が得られたセンサ頂点ＶＳを中心とする新たな粒子フィルタを生成し、ステップＳ３５において、新たに生成した粒子フィルタを伝搬モードにする。
【０１２６】
ステップＳ３７では、式（１９）による演算に基づいて、互いの距離が“２．０”よりも短い粒子フィルタが存在するか否かを判断する。そして、互いの距離が“２．０”よりも短い粒子フィルタが存在すると判断すると（ステップＳ３７：ＹＥＳ）、距離が“２．０”よりも短い複数の粒子フィルタを結合して新たな粒子フィルタを生成する。
【０１２７】
一方、互いの距離が“２．０”よりも短い粒子フィルタが存在しないと判断すると（ステップＳ３７：ＮＯ）、ステップＳ３９をスキップする。
【０１２８】
次に、ステップＳ４１では、異なるセンサ頂点ＶＳで３回連続して得られる“観測”について、１つの“観測”も勝ち取らなかった、つまり３回連続して“観測”を勝ち取らなかった粒子フィルタが存在するか否かを判断する。
【０１２９】
３回連続して“観測”を勝ち取らなかった粒子フィルタが存在すると判断すると（ステップＳ４１：ＹＥＳ）、ステップＳ４３において、３回連続して“観測”を勝ち取らなかった粒子フィルタを消滅させる。
【０１３０】
一方、３回連続して“観測”を勝ち取らなかった粒子フィルタが存在しないと判断すると（ステップＳ４１：ＮＯ）、ステップＳ４３をスキップしてステップＳ４５に進む。
【０１３１】
そして、ステップＳ４５では、“尤も確からしい粒子フィルタ”の粒子の尤度に基づいて、買い物客の現在の位置を推定する。粒子フィルタが１つしか存在しない場合には、その粒子フィルタに基づいて買い物客の現在の位置を推定する。
＜実施例＞
本発明の位置推定方法の有効性を証明するために以下のような実験を行った。この実験では、後述するような“半開放型環境”を構築し、この“半開放型環境”に２つの赤外線センサ１０からなるゲートセンサ１２を設置し、“半開放型環境”内に形成された空間領域を移動する赤外線発信機を携帯した人物（この人物が実験の対象ではないが、以下、“被験者”と呼ぶ。）の現在の位置を推定（追跡）する。
【０１３２】
実験のための“半開放型環境”（以下、“実験環境”と呼ぶ。）は、壁などの遮蔽物がない横７．５ｍ、縦８．８ｍの空間を、ポールと、そのポール間に張られたビニールテープによって、図８に示すように、空間領域Ａないし空間領域Ｉの９つの部屋や通路に区切ることによって作成した。
【０１３３】
この実験環境は、観測の単位となる空間領域間ＡないしＩに、赤外線を遮断する壁などによる明確な区切りは存在しないが、ポール間に張られたビニールテープにより、被験者の移動が制限される。
【０１３４】
そして、被験者が各空間領域ＡないしＩ内を移動する際に、必ず通過する空間領域の境界に、合計９台のゲートセンサ（通過方向検知センサ）１２を配置した。また、被験者の正しい位置データを得るために、被験者を撮影するビデオカメラ（不図示）をこの実験環境に合計８台だけ配置した。
【０１３５】
ゲートセンサ１２は、図９に示すように構成した。つまり、ゲートセンサ１２は、所定のボードを組み立てて作成したアーチ状のゲート枠１４、ゲート枠１４の天井部分に設けられた一対の赤外線センサ１０、および赤外線センサ１０から得られた情報を処理するセンサモジュール１６からなる。
【０１３６】
このようなゲートセンサ１２は、空間領域の境界に、一方の赤外線センサ１０が当該境界に面する一方の空間領域側に位置し、他方の赤外線センサ１０が当該境界に面する他方の空間領域側に位置するように配置される。
【０１３７】
実験環境に設けられた９台のゲートセンサ１２のそれぞれを、図１０に示すように（図１０には紙面の都合上、４つのゲートセンサ１２を示している。）、無線通信中継ポイント３０を介したＩＥＥＥ８０２． １１ｂ規格の無線ＬＡＮによって、パーソナルコンピュータ４０と接続する。
【０１３８】
実験環境内を移動する被験者は、頭部に小型の赤外線タグ（赤外線発信機）２０を装着する。
【０１３９】
ゲートセンサ１２の一方の赤外線センサ１０が赤外線タグ２０から赤外線を受信することによりタグＩＤを受け取ると、センサモジュール１６は赤外線センサ１０からタグＩＤを受け取り、当該ＩＤタグに、当該ＩＤタグを受信した赤外線センサ１０の識別ＩＤとタイムスタンプとを付加し、このタグＩＤを無線通信中継ポイント３０に送信する。無線通信中継ポイント３０は、センサモジュール１６から送信されたタグＩＤを中継してパーソナルコンピュータ（位置推定装置）４０に送信する。
【０１４０】
タグＩＤを受信したパーソナルコンピュータ４０は、図２および図７に示した処理手順を実行して、本発明の位置推定方法により、被験者の現在の位置を推定する。パーソナルコンピュータ４０はタグＩＤに付加された、赤外線センサ１０の識別ＩＤによって被験者を検出した位置（赤外線センサ１０の位置）を特定し、タイムスタンプによって被験者を検出した順序を判断する。
【０１４１】
パーソナルコンピュータ４０は、図１１に示すように構成されている。つまり、パーソナルコンピュータ４０は、ＣＰＵ４２、メモリ４４、ＨＤＤ（Hard Disc Drive）４６、液晶モニタなどの表示装置４８、キーボードやマウスなどの入力装置５０、およびＩＥＥＥ ８０２． １１ｂ規格に対応した無線通信装置５２から構成される。
【０１４２】
パーソナルコンピュータ４０のＨＤＤ４６には、図２および図７に示した処理手順を実行するための位置推定プログラム４６ａ、当該位置推定プログラム４６ａによって利用されるグラグ構造Ｇのデータ（グラフ構造データ）４６ｂ、および同様に位置推定プログラム４６ａによって利用される粒子フィルタのシステムモデルや観測モデルを示すデータ（粒子フィルタデータ）４６ｃが記憶されている。そして、位置推定プログラム４６ａの実行時には、ＨＤＤ４６には、生成された各粒子フィルタに対応した履歴データ（“観測”の回数や通過方向の履歴を示すデータ）４６ｄが記録される。なお、被験者を検出した赤外線センサ１０の位置は、当該赤外線センサ１０の識別ＩＤとグラフ構造データ４６ｂとに基づいて特定される。つまり、ＨＤＤ４６には、グラフ構造Ｇ上のセンサ頂点ＶＳの位置と赤外線センサ１０の識別ＩＤとが対応つけて記憶されている。
【０１４３】
この実験では、実験環境のいたるところ（ビニールテープ、机の上、床など）に、“１”から“２７”までの番号が記載された番号札を配置し、被験者に、実験環境に配置された番号札を番号順に探し出し、探し出した番号札を手で触れさせるというタスクを与えた。なお、被験者には番号札の大まかな位置が記載された地図を手がかりとして与えた。本実験の被験者は１５人であり、各被験者は、このタスクを２回ずつ実行した。
【０１４４】
このようなタスクは、ショッピングモール、コンビニエンスストア、図書館などのような“半開放型環境”において、目的の品物を探し出すことを想定している。
【０１４５】
本発明の位置推定方法の有効性を示すための比較対象として、実験環境において、他の３つの位置推定方法も施行した。他の位置推定方法とは、“最頻反応センサ選択法（距離制約なし）”、“最頻反応センサ選択法（距離制約あり）”、および“単一粒子フィルタ法”である。
【０１４６】
“最頻反応センサ選択法（距離制約なし）”とは、単位時間内の反応回数が最大である赤外線センサの近傍に人物が存在しているとみなす手法である。
【０１４７】
“最頻反応センサ選択法（距離制約あり）”とは、“最頻反応センサ選択法”で得られた結果に対して、赤外線センサ１０の間を人物が移動するために必要な時間を考慮し、突発的に他の空間領域で誤って生じた“観測”（突発的な観測）を後処理で取り除く手法である。なお、本実験では、人物の歩行速度を１．４ｍ／ｓとした。
【０１４８】
“単一粒子フィルタ法”とは、図８に示したセンサ頂点ＶＳ、領域頂点ＶＲ、およびエッジＥからなるグラフ構造Ｇ上に、単体の粒子フィルタを適用して被験者の位置推定を行う手法である。
【０１４９】
図１２の表に実験の結果を示す。図９の表において、“正解時間率”とは、図７のフロー図におけるステップＳ４５において時間“ｔ”ごとに行われる、被験者（買い物客）の現在の位置の推定結果の正解率を、全実験時間に占める正解した時間“ｔ”の割合（率）で表したものである。また、“遷移数”とは、各手法において、被験者の位置がある空間領域から別の空間領域に移動したと判断された回数である。
【０１５０】
図１２の表の実験結果によれば、“最頻反応センサ選択法（距離制約なし）”を用いた場合の位置推定制度は、正解時間率が約２０％、正解遷移率が約３０％、本発明の位置推定方法と比較して低い値となっている。このことから、異なる空間領域に配置された赤外線センサの検出範囲Ｒが複数の空間領域にまたがっていない従来の環境（遮蔽型環境）を前提とした“最頻反応センサ選択法”では、その前提が成り立たない“半開放型環境”では、正確に被験者の位置の推定を行うことが困難であるといえる。
【０１５１】
“最頻反応センサ選択法”に、赤外線センサ１０間の物理的距離による制約を設けて誤った“観測”を除去する方法を適用した“最頻反応センサ選択法（距離制約あり）”の場合、“最頻反応センサ選択法（距離制約なし）”と比較して、精度が１０％ほど向上している。この精度の向上の原因を検討すると、本実験では、横７．５ｍ、縦８．８ｍという狭い空間に９つの空間領域を設けたため、頻繁に被験者の空間領域の移動が発生したことが原因であると考えられる。
【０１５２】
つまり、空間領域の境界に設置された赤外線センサ１０において、比較的高頻度に“観測”が得られ（空間領域の平均滞留時間は３秒程度）、時間的に連続な“観測”が得られる環境において有用な、センサ間の距離の制約を用いた“最頻反応センサ選択法（距離制約あり）”がより精度を向上することが可能となったと考えられる。
【０１５３】
しかし、本発明の位置推定方法と比較すると、正解時間率が約１０％、正解遷移率は約１４％、低い値となっている。したがって、“最頻反応センサ選択法（距離制約あり）”のようにセンサ間の距離の制約により誤った“観測”除去する方法よりも、本発明の位置推定方法のように、センサによる“観測”の順序に基づいて誤った“観測”を除去する方法が有効であることがわかる。
【０１５４】
“単一粒子フィルタ法”による位置推定の精度は、正解時間率が約２４％、正解遷移率にいたっては約４３％も本発明の位置推定方法より低い値となっている。その原因として、“半開放型環境”では、空間領域の境界付近において、異なる空間領域に位置する赤外線センサ１０上で、長期にわたり誤った“観測”が発生する状況が頻繁に起き、徐々に粒子が誤った“観測”の発生している赤外線センサ１０（センサ頂点ＶＳ）の方向へ移動してしまうことがあげられる。
【０１５５】
さらに、粒子フィルタの粒子は誤った“観測”が生じた赤外線センサ１０が取り付けられた空間領域には即座に移動できず、その間にある空間領域やエッジＥ上を移動する。そのため、粒子フィルタの粒子が推定した被験者の移動の軌跡（通過方向の履歴）と、実際の被験者の移動の軌跡とでは大きく異なってしまうことが、正解遷移率を低下させていると考えられる。
【０１５６】
また、一度、誤った“観測”が得られた赤外線センサ１０（センサ頂点ＶＳ）に粒子が集中すると、その後に正しい“観測”が得られたときに、その正しい“観測”が得られたセンサ頂点ＶＳに粒子が戻るまでに時間がかかるため、さらに位置推定の精度を下げていると考えられる。
【０１５７】
以上の原因により、“単一粒子フィルタ法”では、“半開放型環境”において、正確に被験者の位置の推定を行うことは困難であり、実験を行った手法の中で、一番精度が低い結果となっていると考えられる。
【０１５８】
一方、本発明の位置推定方法では、正解時間率、正解遷移率ともに、８５％以上の精度が得られており、“半開放型環境”において高い精度で被験者の位置の推定を行えることが証明された。
【０１５９】
本発明の位置推定方法は、“最頻反応センサ選択法（距離制約あり）”のように、時間情報に基づいて誤った“観測”の除去を行うのではなく、複数の粒子フィルタを用いて、赤外線センサ１０の“観測”の順序に基づいて、誤った“観測”を検出し、修正する。
【０１６０】
そのため、被験者の空間領域内における滞留により誤った“観測”の前後で長期にわたり正しい“観測”が得られなかった場合においても頑健にその誤った“観測”を除去することが可能となり、このように高い精度が得られたと考えられる。
【０１６１】
また、赤外線センサ１０の検出もれが生じた場合においても、離れた空間領域で得られた赤外線センサ１０による正しい“観測”に対して、即座にそのセンサ頂点ＶＳを中心として粒子フィルタを生成する。そのため、その“観測”以降の被験者の位置の推定（追跡）が正確に行えることが本発明の位置推定方法の精度をさらに向上させていると考えられる。
【０１６２】
なお、本発明の位置推定方法は、上述の“半開放型環境”だけでなく、空間領域が赤外線を遮断する壁などで区切られた一般的な建物の内部などの“遮蔽型空間”にも適用できることは言うまでもない。そして、たとえば、本発明の位置推定方法の適用の舞台を病院内などに設定し、病院内で働く看護師の位置を推定するようにすれば、看護師の現在の位置に基づいて、看護師が現在に従事している看護業務などを予測することが可能となる。
【０１６３】
また、以上のテキストによる記述においては、使用しているエディタなどの都合上、図１３に示す表のように、文字の置き換えを行った。
【図面の簡単な説明】
【０１６４】
【図１】この発明の位置推定方法により位置が推定される買い物客が移動する空間領域が存在する環境の一例を示す図解図である。
【図２】本発明の位置推定方法に用いられる粒子フィルタのアルゴリズムを示すフロー図である。
【図３】エッジ遷移率を説明する図解図である。
【図４】新規な粒子フィルタの生成を説明する図解図である。
【図５】頂点（センサ頂点／領域頂点）と粒子フィルタとの距離について説明する図解図である。
【図６】２つの粒子フィルタの間の距離について説明する図解図である。
【図７】本発明の位置推定方法を実現するコンピュータによって実行される処理の手順の一例を示すフロー図である。
【図８】本発明の位置推定方法の有効性を証明する実験における半開放型環境を説明する図解図である。
【図９】本発明の位置推定方法の有効性を証明する実験に用いられるゲートセンサの構成の一例を示す図解図である。
【図１０】本発明の位置推定方法の有効性を証明する実験におけるネットワーク環境の一例を示す図解図である。
【図１１】本発明の位置推定方法を実現する位置推定装置としてのパーソナルコンピュータの構成の一例を示すブロック図である。
【図１２】本発明の位置推定方法の有効性を証明する実験の結果の表を示す図解図である。
【図１３】文字の置き換えを説明する図解図である。
【符号の説明】
【０１６５】
１０ …赤外線センサ
１２ …ゲートセンサ
２０ …赤外線タグ（赤外線発信機）
３０ …無線中継ポイント
４０ …パーソナルコンピュータ（位置推定装置）
１００ …陳列棚
Ｖ …頂点（センサ頂点／領域頂点）
ＶＳ …センサ頂点
ＶＲ …領域頂点
ｋ …粒子フィルタ
ｋ1 …粒子フィルタ
ｋ2 …粒子フィルタ
ｋnew …粒子フィルタ
Ｒ …検出範囲
【特許請求の範囲】
【請求項１】
空間領域の境界に設けられ当該境界を通過する対象を検出するセンサの位置を示すセンサ頂点、前記空間領域の位置を示す領域頂点、および前記領域頂点と当該領域頂点が示す前記空間領域の境界に設けられたセンサを示す前記センサ頂点とを結ぶエッジからなるグラフ構造上に粒子の分布が制限され、前記粒子の確率分布に基づく前記対象の位置の予測と前記センサによる前記対象の検出に基づく前記予測の修正とを繰り返す１または２以上の粒子フィルタを用いて、前記空間領域を移動する前記対象の位置を推定する位置推定方法であって、
前記センサにおいて前記対象が検出されたとき、当該センサを示す前記センサ頂点と前記グラフ構造上において最も距離が近い前記粒子フィルタに属する粒子の確立分布に基づく前記対象の位置の予測を前記検出に基づいて修正し、当該粒子フィルタに属する前記粒子を前記グラフ構造上に伝搬させる伝搬ステップ（Ａ）、および
前記センサにおいて前記対象が検出されたとき、当該センサを示す前記センサ頂点と前記グラフ構造上において最も距離が近い前記粒子フィルタ以外の粒子フィルタに属する粒子を前記グラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第１固定ステップ（Ｂ）を含む、位置推定方法。
【請求項２】
いずれの前記センサにおいても前記対象が検出されないとき、すべての前記粒子フィルタについて各粒子フィルタに属する粒子を前記グラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第２固定ステップ（Ｃ）をさらに含む、請求項１記載の位置推定方法。
【請求項３】
前記グラフ構造上において、前記粒子フィルタの位置から他のセンサによって検出されることなく前記対象が移動不可能な位置に存在する前記センサ頂点が示す前記センサが前記対象を検出した場合に、前記粒子の確率分布が当該センサ頂点を中心とする新規の前記粒子フィルタを生成する生成ステップ（Ｄ）、
異なる前記センサによる連続した所定回数の前記対象の検出のうちのいずれの前記検出によっても前記粒子の確立分布に基づく前記対象の位置の予測の修正が行われないとき、当該粒子フィルタを消滅させる消滅ステップ（Ｅ）、
２以上の前記粒子フィルタがそれぞれ予測する前記対象の位置が同じであるとみなせるとき、当該２以上の前記粒子フィルタを結合する結合ステップ（Ｆ）、および
１または２以上の前記粒子フィルタから前記対象の位置の推定に利用する前記粒子フィルタを選択する選択ステップ（Ｇ）をさらに含む、請求項１または２記載の位置推定方法。
【請求項４】
前記選択ステップ（Ｇ）では、属する粒子の確立分布に基づく前記予測の修正に寄与した前記検出の数がより多く、属する粒子の確立分布に基づく前記予測の修正に寄与した前記検出が行われた前記センサを示すセンサ頂点の位置の変化の履歴が、前記検出を行ったすべての前記センサのそれぞれを示すセンサ頂点の位置の変化の履歴とよりよく一致する粒子フィルタを選択する、請求項３記載の位置推定方法。
【請求項５】
空間領域の境界に設けられ当該境界を通過する対象を検出するセンサの位置を示すセンサ頂点、前記空間領域の位置を示す領域頂点、および前記領域頂点と当該領域頂点が示す前記空間領域の境界に設けられたセンサを示す前記センサ頂点とを結ぶエッジからなるグラフ構造上に粒子の分布が制限され、前記粒子の確率分布に基づく前記対象の位置の予測と前記センサによる前記対象の検出に基づく前記予測の修正とを繰り返す１または２以上の粒子フィルタを用いて、前記空間領域を移動する前記対象の位置を推定する位置推定装置であって、
前記センサにおいて前記対象が検出されたとき、当該センサを示す前記センサ頂点と前記グラフ構造上において最も距離が近い前記粒子フィルタに属する粒子の確立分布に基づく前記対象の位置の予測を前記検出に基づいて修正し、当該粒子フィルタに属する前記粒子を前記グラフ構造上に伝搬させる伝搬手段、および
前記センサにおいて前記対象が検出されたとき、当該センサを示す前記センサ頂点と前記グラフ構造上において最も距離が近い前記粒子フィルタ以外の粒子フィルタに属する粒子を前記グラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第１固定手段を備える、位置推定装置。
【請求項６】
いずれの前記センサにおいても前記対象が検出されないとき、すべての前記粒子フィルタについて各粒子フィルタに属する粒子を前記グラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第２固定手段をさらに備える、請求項５記載の位置推定装置。
【請求項７】
前記グラフ構造上において、前記粒子フィルタの位置から他のセンサによって検出されることなく前記対象が移動不可能な位置に存在する前記センサ頂点が示す前記センサが前記対象を検出した場合に、前記粒子の確率分布が当該センサ頂点を中心とする新規の前記粒子フィルタを生成する生成手段、
異なる前記センサによる連続した所定回数の前記対象の検出のうちのいずれの前記検出によっても前記粒子の確立分布に基づく前記対象の位置の予測の修正が行われないとき、当該粒子フィルタを消滅させる消滅手段、
２以上の前記粒子フィルタがそれぞれ予測する前記対象の位置が同じであるとみなせるとき、当該２以上の前記粒子フィルタを結合する結合手段、および
１または２以上の前記粒子フィルタから前記対象の位置の推定に利用する前記粒子フィルタを選択する選択手段をさらに備える、請求項５または６記載の位置推定装置。
【請求項８】
前記選択手段は、属する粒子の確立分布に基づく前記予測の修正に寄与した前記検出の数がより多く、属する粒子の確立分布に基づく前記予測の修正に寄与した前記検出が行われた前記センサを示すセンサ頂点の位置の変化の履歴が、前記検出を行ったすべての前記センサのそれぞれを示すセンサ頂点の位置の変化の履歴とよりよく一致する粒子フィルタを選択する、請求項７記載の位置推定装置。
【請求項１】
空間領域の境界に設けられ当該境界を通過する対象を検出するセンサの位置を示すセンサ頂点、前記空間領域の位置を示す領域頂点、および前記領域頂点と当該領域頂点が示す前記空間領域の境界に設けられたセンサを示す前記センサ頂点とを結ぶエッジからなるグラフ構造上に粒子の分布が制限され、前記粒子の確率分布に基づく前記対象の位置の予測と前記センサによる前記対象の検出に基づく前記予測の修正とを繰り返す１または２以上の粒子フィルタを用いて、前記空間領域を移動する前記対象の位置を推定する位置推定方法であって、
前記センサにおいて前記対象が検出されたとき、当該センサを示す前記センサ頂点と前記グラフ構造上において最も距離が近い前記粒子フィルタに属する粒子の確立分布に基づく前記対象の位置の予測を前記検出に基づいて修正し、当該粒子フィルタに属する前記粒子を前記グラフ構造上に伝搬させる伝搬ステップ（Ａ）、および
前記センサにおいて前記対象が検出されたとき、当該センサを示す前記センサ頂点と前記グラフ構造上において最も距離が近い前記粒子フィルタ以外の粒子フィルタに属する粒子を前記グラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第１固定ステップ（Ｂ）を含む、位置推定方法。
【請求項２】
いずれの前記センサにおいても前記対象が検出されないとき、すべての前記粒子フィルタについて各粒子フィルタに属する粒子を前記グラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第２固定ステップ（Ｃ）をさらに含む、請求項１記載の位置推定方法。
【請求項３】
前記グラフ構造上において、前記粒子フィルタの位置から他のセンサによって検出されることなく前記対象が移動不可能な位置に存在する前記センサ頂点が示す前記センサが前記対象を検出した場合に、前記粒子の確率分布が当該センサ頂点を中心とする新規の前記粒子フィルタを生成する生成ステップ（Ｄ）、
異なる前記センサによる連続した所定回数の前記対象の検出のうちのいずれの前記検出によっても前記粒子の確立分布に基づく前記対象の位置の予測の修正が行われないとき、当該粒子フィルタを消滅させる消滅ステップ（Ｅ）、
２以上の前記粒子フィルタがそれぞれ予測する前記対象の位置が同じであるとみなせるとき、当該２以上の前記粒子フィルタを結合する結合ステップ（Ｆ）、および
１または２以上の前記粒子フィルタから前記対象の位置の推定に利用する前記粒子フィルタを選択する選択ステップ（Ｇ）をさらに含む、請求項１または２記載の位置推定方法。
【請求項４】
前記選択ステップ（Ｇ）では、属する粒子の確立分布に基づく前記予測の修正に寄与した前記検出の数がより多く、属する粒子の確立分布に基づく前記予測の修正に寄与した前記検出が行われた前記センサを示すセンサ頂点の位置の変化の履歴が、前記検出を行ったすべての前記センサのそれぞれを示すセンサ頂点の位置の変化の履歴とよりよく一致する粒子フィルタを選択する、請求項３記載の位置推定方法。
【請求項５】
空間領域の境界に設けられ当該境界を通過する対象を検出するセンサの位置を示すセンサ頂点、前記空間領域の位置を示す領域頂点、および前記領域頂点と当該領域頂点が示す前記空間領域の境界に設けられたセンサを示す前記センサ頂点とを結ぶエッジからなるグラフ構造上に粒子の分布が制限され、前記粒子の確率分布に基づく前記対象の位置の予測と前記センサによる前記対象の検出に基づく前記予測の修正とを繰り返す１または２以上の粒子フィルタを用いて、前記空間領域を移動する前記対象の位置を推定する位置推定装置であって、
前記センサにおいて前記対象が検出されたとき、当該センサを示す前記センサ頂点と前記グラフ構造上において最も距離が近い前記粒子フィルタに属する粒子の確立分布に基づく前記対象の位置の予測を前記検出に基づいて修正し、当該粒子フィルタに属する前記粒子を前記グラフ構造上に伝搬させる伝搬手段、および
前記センサにおいて前記対象が検出されたとき、当該センサを示す前記センサ頂点と前記グラフ構造上において最も距離が近い前記粒子フィルタ以外の粒子フィルタに属する粒子を前記グラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第１固定手段を備える、位置推定装置。
【請求項６】
いずれの前記センサにおいても前記対象が検出されないとき、すべての前記粒子フィルタについて各粒子フィルタに属する粒子を前記グラフ構造上において当該粒子フィルタに最も近い領域頂点の周辺に収束させる第２固定手段をさらに備える、請求項５記載の位置推定装置。
【請求項７】
前記グラフ構造上において、前記粒子フィルタの位置から他のセンサによって検出されることなく前記対象が移動不可能な位置に存在する前記センサ頂点が示す前記センサが前記対象を検出した場合に、前記粒子の確率分布が当該センサ頂点を中心とする新規の前記粒子フィルタを生成する生成手段、
異なる前記センサによる連続した所定回数の前記対象の検出のうちのいずれの前記検出によっても前記粒子の確立分布に基づく前記対象の位置の予測の修正が行われないとき、当該粒子フィルタを消滅させる消滅手段、
２以上の前記粒子フィルタがそれぞれ予測する前記対象の位置が同じであるとみなせるとき、当該２以上の前記粒子フィルタを結合する結合手段、および
１または２以上の前記粒子フィルタから前記対象の位置の推定に利用する前記粒子フィルタを選択する選択手段をさらに備える、請求項５または６記載の位置推定装置。
【請求項８】
前記選択手段は、属する粒子の確立分布に基づく前記予測の修正に寄与した前記検出の数がより多く、属する粒子の確立分布に基づく前記予測の修正に寄与した前記検出が行われた前記センサを示すセンサ頂点の位置の変化の履歴が、前記検出を行ったすべての前記センサのそれぞれを示すセンサ頂点の位置の変化の履歴とよりよく一致する粒子フィルタを選択する、請求項７記載の位置推定装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１０−１９６６９（Ｐ２０１０−１９６６９Ａ）
【公開日】平成２２年１月２８日（２０１０．１．２８）
【国際特許分類】
【出願番号】特願２００８−１７９９４９（Ｐ２００８−１７９９４９）
【出願日】平成２０年７月１０日（２００８．７．１０）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 社団法人電子情報通信学会「電子情報通信学会技術研究報告 信学技報 Ｖｏｌ．１０８ Ｎｏ．４５」２００８年５月１５日発行 刊行物等 「大阪工業大学情報科学部２００７年度修士学位論文公聴会」大阪工業大学主催 ２００８年２月１２日開催
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度独立行政法人情報通信研究機構「民間基盤技術研究促進制度／日常行動・状況理解に基づく知識共有システムの研究開発」、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（３９３０３１５８６）株式会社国際電気通信基礎技術研究所 (905)
【公開日】平成２２年１月２８日（２０１０．１．２８）
【国際特許分類】
【出願日】平成２０年７月１０日（２００８．７．１０）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 社団法人電子情報通信学会「電子情報通信学会技術研究報告 信学技報 Ｖｏｌ．１０８ Ｎｏ．４５」２００８年５月１５日発行 刊行物等 「大阪工業大学情報科学部２００７年度修士学位論文公聴会」大阪工業大学主催 ２００８年２月１２日開催
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度独立行政法人情報通信研究機構「民間基盤技術研究促進制度／日常行動・状況理解に基づく知識共有システムの研究開発」、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（３９３０３１５８６）株式会社国際電気通信基礎技術研究所 (905)
[ Back to top ]