(57)【特許請求の範囲】
【請求項１】
入力データに対して任意の演算処理を行う演算処理部と、前記演算処理部で用いるデータを記憶する記憶部とを有し、前記演算処理部により、移動オブジェクトの各時刻における位置情報を含む軌跡データに基づき当該移動オブジェクトの移動予測範囲を算出する移動予測装置であって、
前記演算処理部に、
外部から移動オブジェクトの軌跡データを取得して前記記憶部へ保存するデータ取得手段と、
前記記憶部の軌跡データに含まれる、時刻ｔ−ｍ（ただしｔ，ｍは正整数）から時刻ｔにおける前記移動オブジェクトの位置ベクトルｐ（ｔ−ｍ）からｐ（ｔ）に基づいて各時刻ｉ（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）における移動速度ベクトルｖ（ｉ）＝ｐ（ｉ）−ｐ（ｉ−１）を算出して前記記憶部へ保存する移動速度算出手段と、
前記記憶部の軌跡データが前記移動オブジェクトの停滞、直進、および乱歩の各移動状態を示す条件のいずれを満たすか判定することにより前記移動オブジェクトの移動状態を特定する移動状態特定手段と、
特定された前記移動オブジェクトの移動状態に応じて当該移動オブジェクトの移動予測範囲を算出する移動予測範囲算出手段と
を備え、
前記移動状態特定手段は、
前記軌跡データに含まれる、時刻ｔ−ｍ（ただしｔ，ｍは正整数）から時刻ｔにおける前記移動オブジェクトの位置ベクトルｐ（ｔ−ｍ）からｐ（ｔ）と、前記軌跡データを測定したセンサの測定誤差または前記移動オブジェクトの直径のうちいずれか大きい値からなる前記移動オブジェクトの位置揺らぎの幅θpとが、｜ｐ（ｉ）−ｐ（ｔ）｜＜θp（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）の条件を満たす場合、当該移動オブジェクトは停滞状態にあると判定し、
前記記憶部の移動速度ベクトルｖ（ｔ−ｍ）からｖ（ｔ）と前記移動オブジェクトの前記位置揺らぎの幅θpとが、｜ｖ（ｉ）−ｖ（ｔ）｜＜θp（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）の条件を満たす場合、当該移動オブジェクトは直進状態にあると判定し、
前記記憶部の移動速度ベクトルｖ（ｔ−ｍ）からｖ（ｔ）、これら移動速度ベクトルの最大移動速度ｖmax、および前記移動オブジェクトの前記位置揺らぎの幅θpが、｜ｖ（ｉ）｜＜ｖmax＋θp（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）の条件を満たす場合、当該移動オブジェクトは乱歩状態にあると判定し、
前記移動予測範囲算出手段は、
前記移動状態特定手段が前記移動オブジェクトが前記停滞状態にあると判定した場合、時刻ｊ（ただしｔ＜ｊ≦ｔ＋ｎ：ｊ，ｎは正整数）における当該移動オブジェクトの移動予測範囲は、少なくともｐ（ｔ）を中心とする半径θpの円内の領域とし、
前記移動状態特定手段が前記移動オブジェクトが前記直進状態にあると判定した場合、時刻ｊ（ただしｔ＜ｊ≦ｔ＋ｎ：ｊ，ｎは正整数）における当該移動オブジェクトの移動予測範囲は、少なくともｐ（ｔ）＋（ｊ−ｔ）ｖ（ｔ）を中心とする半径θpの円内の領域とし、
前記移動状態特定手段が前記移動オブジェクトが前記乱歩状態にあると判定した場合、時刻ｊ（ただしｔ＜ｊ≦ｔ＋ｎ：ｊ，ｎは正整数）における当該移動オブジェクトの移動予測範囲は、少なくともｐ（ｔ）を中心とする半径（ｊ−ｔ）ｖmax＋θpの円内の領域とする
ことを特徴とする移動予測装置。
【請求項２】
請求項１に記載の移動予測装置において、
前記移動予測範囲算出手段は、時刻ｊにｐ（ｔ）から半径ｒの位置に存在する確率は、（ｒ／（ｊ−ｔ）ｖmax）（ｊ−ｔ）とすることを特徴とする移動予測装置。
【請求項３】
入力データに対して任意の演算処理を行う演算処理部と、前記演算処理部で用いるデータを記憶する記憶部とを有する移動予測装置により、移動オブジェクトの各時刻における位置情報を含む軌跡データに基づき当該移動オブジェクトの移動予測範囲を算出する移動予測方法であって、
前記演算処理部が、外部から移動オブジェクトの軌跡データを取得して前記記憶部へ保存するデータ取得ステップと、
前記演算処理部が、前記記憶部の軌跡データに含まれる、時刻ｔ−ｍ（ただしｔ，ｍは正整数）から時刻ｔにおける前記移動オブジェクトの位置ベクトルｐ（ｔ−ｍ）からｐ（ｔ）に基づいて各時刻ｉ（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）における移動速度ベクトルｖ（ｉ）＝ｐ（ｉ）−ｐ（ｉ−１）を算出して前記記憶部へ保存する移動速度算出ステップと、
前記演算処理部が、前記記憶部の軌跡データが前記移動オブジェクトの停滞、直進、および乱歩の各移動状態を示す条件のいずれを満たすか判定することにより前記移動オブジェクトの移動状態を特定する移動状態特定ステップと、
前記演算処理部が、特定された前記移動オブジェクトの移動状態に応じて当該移動オブジェクトの移動予測範囲を算出する移動予測範囲算出ステップと
を備え、
前記移動状態特定ステップは、
前記軌跡データに含まれる、時刻ｔ−ｍ（ただしｔ，ｍは正整数）から時刻ｔにおける前記移動オブジェクトの位置ベクトルｐ（ｔ−ｍ）からｐ（ｔ）と、前記軌跡データを測定したセンサの測定誤差または前記移動オブジェクトの直径のうちいずれか大きい値からなる前記移動オブジェクトの位置揺らぎの幅θpとが、｜ｐ（ｉ）−ｐ（ｔ）｜＜θp（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）の条件を満たす場合、当該移動オブジェクトは停滞状態にあると判定し、
前記記憶部の移動速度ベクトルｖ（ｔ−ｍ）からｖ（ｔ）と前記移動オブジェクトの前記位置揺らぎの幅θpとが、｜ｖ（ｉ）−ｖ（ｔ）｜＜θp（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）の条件を満たす場合、当該移動オブジェクトは直進状態にあると判定し、
前記記憶部の移動速度ベクトルｖ（ｔ−ｍ）からｖ（ｔ）、これら移動速度ベクトルの最大移動速度ｖmax、および前記移動オブジェクトの前記位置揺らぎの幅θpが、｜ｖ（ｉ）｜＜ｖmax＋θp（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）の条件を満たす場合、当該移動オブジェクトは乱歩状態にあると判定し、
前記移動予測範囲算出ステップは、
前記移動状態特定ステップが前記移動オブジェクトが前記停滞状態にあると判定した場合、時刻ｊ（ただしｔ＜ｊ≦ｔ＋ｎ：ｊ，ｎは正整数）における当該移動オブジェクトの移動予測範囲は、少なくともｐ（ｔ）を中心とする半径θpの円内の領域とし、
前記移動状態特定ステップが前記移動オブジェクトが前記直進状態にあると判定した場合、時刻ｊ（ただしｔ＜ｊ≦ｔ＋ｎ：ｊ，ｎは正整数）における当該移動オブジェクトの移動予測範囲は、少なくともｐ（ｔ）＋（ｊ−ｔ）ｖ（ｔ）を中心とする半径θpの円内の領域とし、
前記移動状態特定ステップが前記移動オブジェクトが前記乱歩状態にあると判定した場合、時刻ｊ（ただしｔ＜ｊ≦ｔ＋ｎ：ｊ，ｎは正整数）における当該移動オブジェクトの移動予測範囲は、少なくともｐ（ｔ）を中心とする半径（ｊ−ｔ）ｖmax＋θpの円内の領域とする
ことを特徴とする移動予測方法。
【請求項４】
コンピュータを、請求項１または請求項２に記載の移動予測装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動予測技術に関し、特に移動する人間、車輌、および物体（オブジェクト）の位置を予測する移動予測技術に関する。
【背景技術】
【０００２】
近年、位置を測定するデバイスの普及により、現実世界内を移動する、人、車両、物体などのさまざまな移動オブジェクトを追跡できるようになった。こうした移動オブジェクトのデータを蓄積するＭＯＤＢ（Moving Object DataBase：移動オブジェクトデータベース）の開発が進んでいる（例えば、非特許文献１など参照）。
【０００３】
このような位置情報データベースの研究課題の１つに、インデクスをいかに効率よく作るかという課題がある（例えば、非特許文献２−４など参照）。
移動オブジェクトのデータは、（ｔ,ｘ,ｙ）のような時刻ｔと座標値ｘ，ｙの組み合わせを時系列に並べたものである。以下、このデータを軌跡データと呼ぶ。軌跡データは空間データの一種であるので、ＭＢＲ（Minimum Bounding Rectangle：最小被覆図形）を使ったＲ−Ｔｒｅｅなどの空間インデクス手法を適用することが可能である（例えば、非特許文献５など参照）。しかし、軌跡データは時間経過に従ってデータが継続的に追加されるため、通常のＲ−ＴｒｅｅではＭＢＲを再計算する頻度が高くなるという問題がある。
【０００４】
従来、この問題を解決する方法として、オブジェクトの移動先を予測して、未来の位置も含むようにＭＢＲを作る方法として、ＳＴＰ−Ｔｒｅｅ（例えば、非特許文献６など参照）、ＴＰＲ−Ｔｒｅｅ（例えば、非特許文献７など参照）、ＴＰＲ＊−Ｔｒｅｅ（例えば、非特許文献１など参照）などの方法が提案されている。未来に追加されるであろうデータを含むようにＭＢＲを作れば、時間が経過して新しいデータが追加されてもインデクスを再構築する必要がなくなる。つまり、この方法でインデクスの再構築頻度を減らすためには、未来のオブジェクトの位置を正確に予測することが重要なポイントになる。
【０００５】
次に、図７を参照して、ＴＲＰ−Ｔｒｅｅによる位置予測方法について説明する。図７は、ＴＲＰ−Ｔｒｅｅによる位置予測方法を示す説明図である。
ＴＰＲ−ＴｒｅｅおよびＴＰＲ＊−Ｔｒｅｅでは、各オブジェクトについてある時刻ｔから過去ｔ−ｍまでの間の最大速度および最小速度をｘ軸、ｙ軸ごとに求めておく。これをＶx＋，Ｖy＋，Ｖx−，Ｖy−とする。ＴＰＲ−Ｔｒｅｅでは、Ｖx＋，Ｖy＋，Ｖx−，Ｖy−の四つ組のことをＶＢＶ（Velocity Bounding Vector）と呼んでいる。
【０００６】
この際、最大速度しか予測に用いないため、オブジェクト単体の位置を予測する精度は低くなるため、実際のインデクス作成に使用するときは、ＭＢＲが含む複数のオブジェクトについて、ｘ軸、ｙ軸の正方向、負方向それぞれについて最大速度を求めておく。同様にＶx−，Ｖy＋，Ｖy−も得られる。
【０００７】
オブジェクトがｘ軸の負方向に進まなかった場合、Ｖx−は正方向へ進んだ場合の最小速度になり、ｙ軸についても同様である。このため、図７の例では、Ｖy＋はマイナスの値になっている。
これらの値を用いて、時刻ｔ＋ｉ（ただしｔ，ｉは正整数）におけるＭＢＲの四隅の点のｘ、ｙ座標Ｐx＋（ｔ＋ｉ），Ｐy＋（ｔ＋ｉ），Ｐx−（ｔ＋ｉ），Ｐy−（ｔ＋ｉ）は、次のようにして求められる。なお、Ｐx（ｔ），Ｐy（ｔ）は時刻ｔにおけるオブジェクトの座標を示す。
Ｐx＋（ｔ＋ｉ）＝Ｖx＋×ｉ＋Ｐx（ｔ）
Ｐy＋（ｔ＋ｉ）＝Ｖy＋×ｉ＋Ｐy（ｔ）
Ｐx−（ｔ＋ｉ）＝Ｖx−×ｉ＋Ｐx（ｔ）
Ｐy−（ｔ＋ｉ）＝Ｖy−×ｉ＋Ｐy（ｔ）
【０００８】
次に、ＳＴＰ−Ｔｒｅｅによる位置予測方法について説明する。
ＳＴＲ−Ｔｒｅｅでは各オブジェクトについてある時刻ｔから過去ｔ−ｍ（ただしｍは正整数）までの位置をそれぞれｘ（ｔ−ｍ），ｙ（ｔ−ｍ），ｘ（ｔ−ｍ＋１），ｙ（ｔ−ｍ＋１），...,ｘ（ｔ），ｙ（ｔ）のように取り出す。時刻ｔ−ｍからｔまで取り出したベクトルをｋ（ｔ）mと表記し、時刻ｔ−ｍ−１からｔ−１まで取り出したベクトルはｋ（ｔ−１）mと表記する。この要素数は、常に２ｍ個になる。ｋ（ｔ）mを最上行とし、以下、ｋ（ｔ−１）mからｋ（ｔ−ｎ）m（ｎ＜ｍ）（ただしｎは正整数）の行を順に並べて作った２ｍ×ｎ行列をｋ（ｔ）m，nとする。また、これとは別に時刻ｔからｔ−ｎまでのｘ座標の値を並べたベクトルをｘ（ｔ）n＝｛ｘ（ｔ−ｎ），....,ｘ（ｔ）｝とする。ｙ（ｔ）nも同様である。
【０００９】
このとき、次の連立方程式を満たすような近似解のベクトルｗx＝｛ｗｘ1，ｗｘ2，...., ｗｘ2m｝，ｗy＝｛ｗｙ1，ｗｙ2，....,ｗｙ2m｝を求める。
ｘ（ｔ）T＝Ｋ（ｔ−１）m，n・ｗxT
ｙ（ｔ）T＝Ｋ（ｔ−１）m，n・ｗyT
【００１０】
ここで得られた行列ｗx，ｗyとベクトルｋm（ｔ）＝｛ｘ（ｔ−ｍ），ｙ（ｔ−ｍ），ｘ（ｔ−ｍ＋１），ｙ（ｔ−ｍ＋１），....,ｘ（ｔ），ｙ（ｔ）｝を用いると時刻ｔ＋１のオブジェクトの位置ｐ（ｔ＋１）＝｛ｘ（ｔ＋１）、ｙ（ｔ＋１）｝は次の式で得られる。
ｘ（ｔ＋１）＝ｗx・ｋ（ｔ）mT
ｙ（ｔ＋１）＝ｗy・ｋ（ｔ）mT
時刻ｔ＋２以降の位置ｐ（ｔ＋２），....についても、再帰的にこの式を適用することで求めることができる。
【００１１】
【非特許文献１】Ouri Wolfson, Prasad Sistla, Bo Xu, Jutai Zhou, and Sam Chamberlain. DOMINO:Databases for Moving Objects tracking. In SIGMOD'99 Conference Proceedings, pp.547-549, 1999.
【非特許文献２】Hoda Mokhtar, Jianwen Su, and Oscar H.Ibarra. On moving object queries. In POPS2002 Symposium Proceedings, PP.188-198, 2002.
【非特許文献３】George Kollios, Dimitrios Gunopulos, and Vassilis J.Tsotras. On indexing mobile oblects. In PODS'99 Symposium Proceedings, pp.261-272, 1999.
【非特許文献４】G.Kollios, V.J.Tsotras, D.Gunopulos, A.Delis ,and M.Hadjieleftheriou. Indexing animated objects using spatiotemporal access methods. IEEE Transactions on Knowledge and Data Engineering, Vol.13, No.5, pp.758-777, 2001.
【非特許文献５】O.Guttman. R-trees:a dynamic index structure for spatial searching. In SIGMOD'84 Conference Proceedings, pp.47-57, 1984.
【非特許文献６】Yufei Tao, Christos Faloutsos, Dimitris Papadias, and Bin Liu. Prediction and indexing of moving objects with unknown motion pattens. In SINGMOD'04: Proceedings of then 2004 ACM SIGMOD international conference om Management of data, pp.611-622, New York, NY, USA, 2004. ACM Press.
【非特許文献７】Simonas Saltenis, Christian S.Jensen, Scott T.Leutenegger, and Mario A.Lopez. Indexing the positions of continuously moving objects. In SIGMOD'00 :Proceeding of the 2000 ACM SIGMOD international conference on Management of data, pp.331-342, New York, NY, USA, 2000. ACM Press.
【非特許文献８】Yufei Tao, Jimeng Sun, and Dimitris Papadias. Analysis of predictive spatio-temporal queries. ACM Trans. Database Syst., Vol28, No.4, pp.295-336, 2003.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、このような従来技術では、移動しているオブジェクトの移動予測について良好な正解率が得られないという問題点があった。
例えば、ＴＰＲ−Ｔｒｅｅは、オブジェクトが直進している場合や完全に停止している状態では、比較的よい予測正解率を示す。ランダムウォークのような移動方向が不定である状態についても、結果的に予測範囲が大きく取られるために予測の正解率はさほど下がらない。一方で、位置の揺らぎ（測定誤差）の影響が考慮されていないため、停滞状態であっても位置の揺らぎが大きい場合は予測の正解率が低下したり、面積が過大なＭＢＲを作成してしまうことが多いという問題があった。
【００１３】
また、ＳＰＲ−Ｔｒｅｅでは、予測されるオブジェクトの位置がａｆｉｎ変換で与えられる。このため、停止や直進以外にも、円運動やサインカーブのような運動をするオブジェクトに対しても、高い予測正解率を示す。その反面、反転や転進などがあると近似解が適切な値とならず、予測正解率が大きく落ちることがある。また、ＴＰＲ−Ｔｒｅｅと同様に位置の揺らぎの影響が考慮されていないため、揺らぎを含む停滞があると予測の正解率が低下する。また、この手法では解のベクトルを求める（連立方程式を解く）ために、特異値分解を行う必要があるが、そのアルゴリズムは一般に複雑であり、計算量が多いという問題があった。
【００１４】
本発明はこのような課題を解決するためのものであり、位置揺らぎ（測定誤差）を含むデータを用いてオブジェクトの移動先を予測する場合でも、比較的少ない計算量で、高い予測精度が得られる移動予測装置、移動予測方法、およびプログラムを提供することを目的としている。
【課題を解決するための手段】
【００１５】
このような目的を達成するために、本発明にかかる移動予測装置は、入力データに対して任意の演算処理を行う演算処理部と、演算処理部で用いるデータを記憶する記憶部とを有し、演算処理部により、移動オブジェクトの各時刻における位置情報を含む軌跡データに基づき当該移動オブジェクトの移動予測範囲を算出する移動予測装置であって、演算処理部に、外部から移動オブジェクトの軌跡データを取得して記憶部へ保存するデータ取得手段と、記憶部の軌跡データに含まれる、時刻ｔ−ｍ（ただしｔ，ｍは正整数）から時刻ｔにおける移動オブジェクトの位置ベクトルｐ（ｔ−ｍ）からｐ（ｔ）に基づいて各時刻ｉ（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）における移動速度ベクトルｖ（ｉ）＝ｐ（ｉ）−ｐ（ｉ−１）を算出して記憶部へ保存する移動速度算出手段と、記憶部の軌跡データが移動オブジェクトの停滞、直進、および乱歩の各移動状態を示す条件のいずれを満たすか判定することにより移動オブジェクトの移動状態を特定する移動状態特定手段と、特定された移動オブジェクトの移動状態に応じて当該移動オブジェクトの移動予測範囲を算出する移動予測範囲算出手段とを備えている。
【００１６】
これに加えて、移動状態特定手段で、軌跡データに含まれる、時刻ｔ−ｍ（ただしｔ，ｍは正整数）から時刻ｔにおける移動オブジェクトの位置ベクトルｐ（ｔ−ｍ）からｐ（ｔ）と、軌跡データを測定したセンサの測定誤差または移動オブジェクトの直径のうちいずれか大きい値からなる移動オブジェクトの位置揺らぎの幅θpとが、｜ｐ（ｉ）−ｐ（ｔ）｜＜θp（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）の条件を満たす場合、当該移動オブジェクトは停滞状態にあると判定し、移動予測範囲算出手段で、移動オブジェクトが停滞状態にある場合、時刻ｊ（ただしｔ＜ｊ≦ｔ＋ｎ：ｊ，ｎは正整数）における当該移動オブジェクトの移動予測範囲は、少なくともｐ（ｔ）を中心とする半径θpの円内の領域とするようにしたものである。
【００１７】
これに加えて、移動状態特定手段で、記憶部の移動速度ベクトルｖ（ｔ−ｍ）からｖ（ｔ）と移動オブジェクトの位置揺らぎの幅θpとが、｜ｖ（ｉ）−ｖ（ｔ）｜＜θp（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）の条件を満たす場合、当該移動オブジェクトは直進状態にあると判定し、移動予測範囲算出手段で、移動オブジェクトが直進状態にある場合、時刻ｊ（ただしｔ＜ｊ≦ｔ＋ｎ：ｊ，ｎは正整数）における当該移動オブジェクトの移動予測範囲は、少なくともｐ（ｔ）＋（ｊ−ｔ）ｖ（ｔ）を中心とする半径θpの円内の領域とするようにしたものである。
【００１８】
これに加えて、移動状態特定手段で、記憶部の移動速度ベクトルｖ（ｔ−ｍ）からｖ（ｔ）、これら移動速度ベクトルの最大移動速度ｖmax、および移動オブジェクトの位置揺らぎの幅θpが、｜ｖ（ｉ）｜＜ｖmax＋θp（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）の条件を満たす場合、当該移動オブジェクトは乱歩状態にあると判定し、移動予測範囲算出手段で、移動オブジェクトが乱歩状態にある場合、時刻ｊ（ただしｔ＜ｊ≦ｔ＋ｎ：ｊ，ｎは正整数）における当該移動オブジェクトの移動予測範囲は、少なくともｐ（ｔ）を中心とする半径（ｊ−ｔ）ｖmax＋θpの円内の領域とするようにしたものである。
【００１９】
この際、移動予測範囲算出手段で、時刻ｊにｐ（ｔ）から半径ｒの位置に存在する確率は、（ｒ／（ｊ−ｔ）ｖmax）（ｊ−ｔ）とするようにしてもよい。
【００２０】
また、本発明にかかる移動予測方法は、入力データに対して任意の演算処理を行う演算処理部と、演算処理部で用いるデータを記憶する記憶部とを有する移動予測装置により、移動オブジェクトの各時刻における位置情報を含む軌跡データに基づき当該移動オブジェクトの移動予測範囲を算出する移動予測方法であって、演算処理部が、外部から移動オブジェクトの軌跡データを取得して記憶部へ保存するデータ取得ステップと、演算処理部が、記憶部の軌跡データに含まれる、時刻ｔ−ｍ（ただしｔ，ｍは正整数）から時刻ｔにおける移動オブジェクトの位置ベクトルｐ（ｔ−ｍ）からｐ（ｔ）に基づいて各時刻ｉ（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）における移動速度ベクトルｖ（ｉ）＝ｐ（ｉ）−ｐ（ｉ−１）を算出して記憶部へ保存する移動速度算出ステップと、演算処理部が、記憶部の軌跡データが移動オブジェクトの停滞、直進、および乱歩の各移動状態を示す条件のいずれを満たすか判定することにより移動オブジェクトの移動状態を特定する移動状態特定ステップと、演算処理部が、特定された移動オブジェクトの移動状態に応じて当該移動オブジェクトの移動予測範囲を算出する移動予測範囲算出ステップとを備え、移動状態特定ステップで、軌跡データに含まれる、時刻ｔ−ｍ（ただしｔ，ｍは正整数）から時刻ｔにおける移動オブジェクトの位置ベクトルｐ（ｔ−ｍ）からｐ（ｔ）と、軌跡データを測定したセンサの測定誤差または移動オブジェクトの直径のうちいずれか大きい値からなる移動オブジェクトの位置揺らぎの幅θpとが、｜ｐ（ｉ）−ｐ（ｔ）｜＜θp（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）の条件を満たす場合、当該移動オブジェクトは停滞状態にあると判定し、記憶部の移動速度ベクトルｖ（ｔ−ｍ）からｖ（ｔ）と移動オブジェクトの位置揺らぎの幅θpとが、｜ｖ（ｉ）−ｖ（ｔ）｜＜θp（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）の条件を満たす場合、当該移動オブジェクトは直進状態にあると判定し、記憶部の移動速度ベクトルｖ（ｔ−ｍ）からｖ（ｔ）、これら移動速度ベクトルの最大移動速度ｖmax、および移動オブジェクトの位置揺らぎの幅θpが、｜ｖ（ｉ）｜＜ｖmax＋θp（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）の条件を満たす場合、当該移動オブジェクトは乱歩状態にあると判定し、移動予測範囲算出ステップで、移動状態特定ステップが移動オブジェクトが停滞状態にあると判定した場合、時刻ｊ（ただしｔ＜ｊ≦ｔ＋ｎ：ｊ，ｎは正整数）における当該移動オブジェクトの移動予測範囲は、少なくともｐ（ｔ）を中心とする半径θpの円内の領域とし、移動状態特定ステップが移動オブジェクトが直進状態にあると判定した場合、時刻ｊ（ただしｔ＜ｊ≦ｔ＋ｎ：ｊ，ｎは正整数）における当該移動オブジェクトの移動予測範囲は、少なくともｐ（ｔ）＋（ｊ−ｔ）ｖ（ｔ）を中心とする半径θpの円内の領域とし、移動状態特定ステップが移動オブジェクトが乱歩状態にあると判定した場合、時刻ｊ（ただしｔ＜ｊ≦ｔ＋ｎ：ｊ，ｎは正整数）における当該移動オブジェクトの移動予測範囲は、少なくともｐ（ｔ）を中心とする半径（ｊ−ｔ）ｖmax＋θpの円内の領域とするようにしたものである。
【００２１】
また、本発明にかかるプログラムは、前述したいずれかの移動予測装置構成する各部として機能させるためのプログラムである。
【発明の効果】
【００２２】
本発明によれば、移動予測装置により、軌跡データが移動オブジェクトの停滞、直進、および乱歩の各移動状態を示す条件のいずれを満たすか判定することにより移動オブジェクトの移動状態が特定され、この移動状態に応じて当該移動オブジェクトの移動予測範囲を算出されるため、移動オブジェクトの移動状態に応じて適切に位置揺らぎを考慮して移動予測範囲を算出でき、位置揺らぎ（測定誤差）を含むデータを用いてオブジェクトの移動先を予測する場合でも、比較的少ない計算量で、高い予測精度が得られる。
【発明を実施するための最良の形態】
【００２３】
次に、本発明の実施の形態について図面を参照して説明する。
［第１の実施の形態］
まず、図１を参照して、本発明の第１の実施の形態にかかる移動予測装置が用いられる移動オブジェクトデータベースシステムについて説明する。図１は、本発明の第１の実施の形態にかかる移動予測装置が用いられる移動オブジェクトデータベースシステムの構成を示すブロック図である。
【００２４】
移動オブジェクトデータベースシステム（以下、移動オブジェクトＤＢシステムという）は、入力された任意の移動オブジェクトに関する軌跡データを蓄積し、外部からの検索要求に応じて類似する軌跡を持つ移動オブジェクトを検索し、その検索結果を出力するシステムである。
この移動オブジェクトＤＢシステムは、軌跡データ入力装置１、オブジェクトデータ管理装置２、移動予測装置３、およびデータ検索装置４から構成されている。
【００２５】
軌跡データ入力装置１は、主な機能部としてデータ取得部１１を備えている。
データ取得部１１は、センサで測定された移動オブジェクトの軌跡データ５を受け取る機能と、各時刻における各オブジェクトの位置を示す位置データ１Ａをまとめてオブジェクトデータ管理装置２へ出力する機能とを有している。軌跡データ５については、通信ネットワークを介して受け取る方法や、電子ファイルとして外部装置や記録媒体から取得する方法がある。
【００２６】
オブジェクトデータ管理装置２は、主な機能部としてデータ生成部２１、データ検索部２２、およびデータ蓄積部２３を備えている。
データ生成部２１は、軌跡データ入力装置１から受け取った位置データ１Ａに対するインデクスを作成する機能と、位置データ１Ａとそのインデクスを含むオブジェクトデータをオブジェクトデータ蓄積部２３へ保存する機能と、インデクス作成時に任意のオブジェクトの移動予測が必要になった場合は、予測に必要な過去の位置データを含む予測要求２Ａを移動予測装置３へ出力し、得られた予測結果２Ｂに含まれる予測領域リストに基づきインデクスを作成する機能とを有している。
【００２７】
データ検索部２２は、データ検索装置４からの検索要求４Ａに応じて、オブジェクトデータ蓄積部２３から各オブジェクトのインデクスを参照して所望のオブジェクトデータを検索する機能と、得られたオブジェクトデータを含む検索結果４Ｂをデータ検索装置４へ返送する機能とを有している。
データ蓄積部２３は、ハードディスクなどの記憶装置を用いて、データ生成部２１で生成されたオブジェクトデータをそのインデクスで検索可能に蓄積する機能と、データ検索部２２からの要求に応じて任意のオブジェクトデータを読み出して出力する機能とを有している。
【００２８】
移動予測装置３は、主な機能部として移動予測部３１を備えている。
移動予測部３１は、オブジェクトデータ管理装置２からの予測要求２Ａに基づき任意のオブジェクトの移動状態を特定する機能と、この移動状態に応じた予測関数を用いて当該オブジェクトの移動先を示す予測領域を算出する機能と、得られた予測領域からなる予測領域リストを予測結果２Ｂとしてオブジェクトデータ管理装置２へ返送する機能とを有している。
【００２９】
データ検索装置４は、主な機能部として検索制御部４１を備えている。
検索制御部４１は、検索要求６Ｂで指示された時刻、位置または範囲、オブジェクト名に該当するオブジェクトデータの検索を指示する検索要求４Ａをオブジェクトデータ管理装置２へ出力する機能と、オブジェクトデータ管理装置２から受け取った検索結果を画面表示し、または電子データとして外部装置や記録媒体へ出力し、あるいは通信ネットワークへ送信する機能を有している。
【００３０】
本実施の形態にかかる移動オブジェクトＤＢシステムを構成する軌跡データ入力装置１、オブジェクトデータ管理装置２、移動予測装置３、およびデータ検索装置４は、コンピュータなどの情報処理装置により実現され、これら装置の各機能部は、ＣＰＵなどのマイクロプロセッサとその周辺回路を有する演算処理部が、当該装置の記憶部に格納されているプログラムを読み込んで実行することにより、上記ハードウェアとプログラムとが協働して実現される。なお、本実施の形態では、これら装置を別個の装置で実現した場合を例として説明したが、これに限定されるものではなく、複数の装置を１つの装置で実現してもよい。
【００３１】
［第１の実施の形態の動作］
次に、図１を参照して、本発明の第１の実施の形態にかかる移動オブジェクトＤＢシステムの動作について説明する。
移動オブジェクトＤＢシステムの主な動作としては、各移動オブジェクトに関するオブジェクトデータを格納するオブジェクトデータ格納動作と、任意のオブジェクトデータを検索するオブジェクトデータ検索動作がある。
【００３２】
［オブジェクトデータ格納動作］
まず、移動オブジェクトＤＢシステムに対して各移動オブジェクトに関するオブジェクトデータを格納するオブジェクトデータ格納動について説明する。
軌跡データ入力装置１は、データ取得部１１により、センサで測定された各移動オブジェクトの軌跡データ５を順次受け取り、各時刻における各オブジェクトの位置を示す位置データ１Ａをまとめてオブジェクトデータ管理装置２へ出力する。
【００３３】
オブジェクトデータ管理装置２は、データ生成部２１により、軌跡データ入力装置１から受け取った位置データ１Ａに対するインデクスを作成し、位置データ１Ａとそのインデクスを含むオブジェクトデータをオブジェクトデータ蓄積部２３へ保存する。
この際、データ生成部２１は、インデクス作成時に任意のオブジェクトの移動予測が必要になった場合、予測に必要な過去の位置データを含む予測要求２Ａを移動予測装置３へ出力し、得られた予測結果２Ｂに含まれる予測領域リストに基づきインデクスを作成する。
【００３４】
移動予測装置３は、オブジェクトデータ管理装置２からの予測要求２Ａに応じて、移動予測部３１により、後述する図２の移動予測処理を実行して、任意のオブジェクトの移動状態を特定し、この移動状態に応じた予測関数を用いて当該オブジェクトの移動先を示す予測領域を算出する。そして、得られた予測領域からなる予測領域リストを予測結果２Ｂとしてオブジェクトデータ管理装置２へ返送する。
これにより、時刻ごとに入力された軌跡データに基づき、各移動オブジェクトの位置とインデクスとが生成され、データ蓄積部２３の格納されている各移動オブジェクトのオブジェクトデータがそれぞれ更新される。
【００３５】
［オブジェクトデータ検索動作］
次に、移動オブジェクトＤＢシステムから任意のオブジェクトデータを検索するオブジェクトデータ検索動作について説明する。
データ検索装置４は、オペレータ操作や外部装置から入力された検索要求６Ａに応じて、検索制御部４１により、検索要求６Ｂで指示された時刻、位置または範囲、オブジェクト名に該当するオブジェクトデータの検索を指示する検索要求４Ａをオブジェクトデータ管理装置２へ出力する。
【００３６】
オブジェクトデータ管理装置２は、データ検索装置４からの検索要求４Ａに応じて、データ検索部２２により、データ検索装置４からの検索要求４Ａに応じて、オブジェクトデータ蓄積部２３から各オブジェクトのインデクスを参照して所望のオブジェクトデータを検索する。そして、得られたオブジェクトデータを含む検索結果４Ｂをデータ検索装置４へ返送する。
【００３７】
データ検索装置４の検索制御部４１は、オブジェクトデータ管理装置２から受け取った検索結果を画面表示し、または電子データとして外部装置や記録媒体へ出力し、あるいは通信ネットワークへ送信する。
これにより、所望のオブジェクトデータが移動オブジェクトＤＢシステムから提供される。
【００３８】
［移動予測動作］
次に、図２を参照して、本発明の第１の実施の形態にかかる移動予測装置における移動予測動作について説明する。図２は、本発明の第１の実施の形態にかかる移動予測装置における移動予測処理を示すフローチャートである。
【００３９】
［移動の状態］
まず、移動状態移動の予測に用いることが可能な特徴的な移動の状態について説明する。ここで言う状態とは「オブジェクトがある特定の動きをした場合、その後も同様の動きをする」という事象のことである。この状態を利用すれば、オブジェクトの動きを分析して状態を特定することで、その後のオブジェクトの移動先を予測できる。
【００４０】
状態としては、オブジェクトがほとんど移動しない状態（停滞）と、一定方向に等速で進む状態（直進）の２つの状態がある。以下、これらについて説明する。
停滞：ほぼ移動しない状態のことである。ただし、後述する位置の揺らぎの影響があるため、完全に停止することは稀である。
直進：ほぼ等速度で一定方向へ移動している状態のことである。
【００４１】
これら「停滞」や「直進」のいずれの状態にもあたらない状態を、本発明では「乱歩」状態と呼ぶ。
乱歩：速度、移動方向ともに不定な、いわゆるランダムウォークのことである。ただし、実際のデータを観測すると、完全なランダムウォークではなく、速度がある一定の範囲に収まった状態で、移動方向のみが変わるケースが多く見られる。
【００４２】
［位置揺らぎ］
次に、位置揺らぎについて説明する。測定したいずれの軌跡データにも、オブジェクトが停止中や移動中に移動方向とは無関係な方向にわずかに位置がずれる現象が見られた。本発明では、これを「位置揺らぎ」と呼ぶ。測定するセンサによる誤差と、オブジェクト自体に大きさがあること（センサによって測定される中心位置が変動すること）の両方が原因になり発生していると考えられる。どちらの原因によるものかは、データ上では区別することがほとんど不可能である。
【００４３】
データの揺らぎ幅はその性質上、センサの測定誤差とオブジェクトの大きさ（直径）のうち、より大きい値とほぼ等しくなる。例えばセンサの測定誤差が１εでオブジェクトの大きさが２εなら、揺らぎ幅は２εである。位置の予測を行う上では、この揺らぎの影響も考慮する必要がある。揺らぎはθpで表す。この値は、実測で求める。
【００４４】
［状態の定式化］
次に、状態の定式化について説明する。まず、「移動の状態」という用語を形式的に定義する。「軌跡データλt，−mが移動の状態Ｃにある」とは、時刻ｔ−ｍ（ただしｔ，ｍは正整数）からｔまでの軌跡データλt，−mが条件Ｃを満たしている状態にあることをいう。つまり、条件Ｃによって、それぞれの状態は特定される。前述した「停滞」、「直進」、および「乱歩」の３つの移動の状態を、それぞれ対応する条件Ｃst、Ｃsw、Ｃrwで定義する。
【００４５】
停滞状態（ｓｔ）の条件Ｃstは、軌跡データλt，−mにおける時刻ｉ（ただしｔ−ｍ≦ｉ≦ｔ：ｉは正整数）の位置ベクトルをｐ（ｉ）とした場合、｜ｐ（ｉ）−ｐ（ｔ）｜＝０と定義できる。つまりλt，−mの最大速度が０であるような、完全に停止している状態である。
ただし、前述したように実際のデータには揺らぎがあるため、完全に速度が０として測定されることは稀である。そのため、揺らぎθpの影響を加味し、停滞状態を次のように定義する。
Ｃst：｜ｐ（ｉ）−ｐ（ｔ）｜＜θp
ｐ（ｉ）∈λt，−m
つまり、停滞状態にあるオブジェクトは、時刻ｔ−ｍからｔの間にｐ（ｔ）から距離θp以上離れなていないという条件を満たす。これにより、位置揺らぎを考慮して移動オブジェクトが停滞状態にあることを的確に判定できる。
【００４６】
直進状態（ｓｗ）の条件Ｃswは、軌跡データλt，−mの時刻ｉ（０≦ｉ≦ｍ）における移動速度（ベクトル値）をｖ（ｉ）＝ｐ（ｉ）−ｐ（ｉ−１）とすれば、ｖ（ｉ）−ｖ（ｔ）と定義できる。つまりλt，−mのどの移動ベクトルも、時刻ｔの速度ベクトルｖ（ｔ）＝ｐ（ｔ）−ｐ（ｔ−１）との差が０であるような状態である。
ただし、停滞状態と同様に揺らぎの影響がある。このため、揺らぎを含めた直進状態を次のように定義する。
Ｃsw：｜ｖ（ｉ）−ｖ（ｔ）｜＜θp
ｖ（ｉ）＝ｐ（ｉ）−ｐ（ｉ−１）
これにより、位置揺らぎを考慮して移動オブジェクトが直進状態にあることを的確に判定できる。
【００４７】
乱歩状態（ｒｗ）は、停滞、直進のいずれにも分類されなかった場合は、乱歩状態と判定できる。このため、乱歩状態を特定する条件は不要とも考えられる。しかし、状態の条件が設定されていないと、予測関数を一意に決められなくなる。そこで、いかなる動きをするオブジェクトでも満足するように条件を、乱歩状態の条件として定義しておく。
【００４８】
ｐ（ｔ）を終点とし、最高速度がｖmaxであるようなオブジェクトの軌跡データλt，−mの各点は、必ずｐ（ｔ）を中心とする半径ｉｖmaxの円に含まれる。乱歩状態の条件Ｃrwは、λt，−mの最高速度（スカラー値）をｖmaxとするとき、Ｃrw：｜ｖ（ｉ）｜≦ｉｖmax（ｔ−ｍ≦ｉ≦ｔ）と定義でき、揺らぎを含めた乱歩状態を次のように定義する。
Ｃrw：｜ｖ（ｉ）｜≦ｖmax＋θp
これにより、位置揺らぎを考慮して移動オブジェクトが乱歩状態にあることを的確に判定できる。
【００４９】
［予測関数］
時刻ｔから未来の時刻ｊ＝ｔ＋ｎ（ただしｔ＜ｊ≦ｔ＋ｎ：ｊ，ｎは正整数）までの軌跡データλt，＋nで示される移動オブジェクトの移動予想範囲をＲ（ｊ）とする。λt，−mがある状態Ｃにあるとき、Ｃに含まれる条件式を利用して、λt，−mからＲ（ｊ）を求めることができる。範囲Ｒ（ｊ）は面積を持つ閉じた図形であり、例えば矩形や円、またはこれらの集合で表される。Ｒ（ｊ）はｆ（λt，−m，ｊ）＝Ｒ（ｊ）のように、λt，−mと時刻ｊを引数とする関数で表せる。このｆを予測関数と呼ぶ。
【００５０】
なお、従来手法では、ｆは点座標を返す関数として定義されているものもある。しかし、未来のオブジェクトの移動する位置を、点座標という極めて高い精度の位置情報として予測することは現実的でない。このため、本発明ではｆは範囲を返す関数として定義する。
【００５１】
停滞状態の場合、条件Ｃst：｜ｐ（ｉ）−ｐ（ｔ）｜＜θpであるから、未来にオブジェクトが移動する範囲Ｒst（ｊ）＝ｆst（λt，−m，ｊ）もｐ（ｔ）を中心とする半径θpの円とする。ただし、ＭＢＲ（Minimum Bounding Rectangle：最小被覆図形）を作成する場合には予測範囲が矩形であるほうが都合がよいため、実際にはこの円を含む最小の矩形を予測範囲とする。
これにより、位置揺らぎを考慮して移動オブジェクトが停滞状態にある場合の移動予測範囲を精度よく算出できる。
【００５２】
直進状態の場合、条件Ｃsw：｜ｖ（ｉ）−ｖ（ｔ）｜＜θpから、Ｒsw（ｊ）＝ｆsw（λt，−m，ｊ）は、図３に示すように、ｐ（ｔ）＋（ｊ−ｔ）ｖ（ｔ）を中心とした半径θpの円形の領域とする。図３は、直進状態での移動予測範囲を示す説明図である。予測される領域は円形になるが、停滞の場合と同じようにＭＢＲの作成に供するため、この円を含む最小の矩形を実際の予測範囲とする。
これにより、位置揺らぎを考慮して移動オブジェクトが直進状態にある場合の移動予測範囲を精度よく算出できる。
【００５３】
乱歩状態の場合、条件Ｃrw：｜ｖ（ｉ）｜≦ｖmax＋θpから、Ｒrw（ｊ）＝ｆrw（ｔ＋ｎ）は、図４に示すようにｐ（ｔ）を中心とする半径ｎｖmax＋θpの円になる。図４は、乱歩状態での移動予測範囲を示す説明図である。しかし、この予測関数をそのまま用いると、予測関数で得られる予測範囲が非常に広くなり、冗長性が高くなる。そこで、移動オブジェクトがランダムウォークすると仮定し、移動オブジェクトが到達しにくい、円の外周付近の領域を予測範囲から削る方法を導入する。
【００５４】
ランダムウォークの場合、オブジェクトが移動速度ｖmax以下でｊ−ｔ回移動するとき、出発点ｐ（ｔ）から半径ｒ（０≦ｒ≦ｎｖmax）の円内に存在する確率ρは、次の式で与えられる。
ρ＝（ｒ／（ｊ−ｔ）ｖmax）（j−t）
【００５５】
つまり、時刻ｔ＋ｎにおける移動オブジェクトの位置を確率ρ以内で予測するには、予測円の半径をθp＋ｎｖmax×ｎ√ｐとすればよい。例えばρ＝０．７、π＝５であれば、円の半径は０．９３×５ｖmaxとなる。ただし、実際の軌跡データではｖmaxは過大な値をとりやすく、ρ＝０．６〜０．８程度に設定しても予測率はほとんど低下しない。このρは装置の管理者が、適正な値に予め設定する。
これにより、位置揺らぎを考慮して移動オブジェクトが乱歩状態にある場合の移動予測範囲を精度よく算出できる。
【００５６】
［移動予測処理］
時刻ｔ＋ｎにおける移動先を示す移動予測範囲は、移動オブジェクトの軌跡データλt，−mについて、前述した、停滞、直進、乱歩の各状態の条件Ｃst，Ｃsw，Ｃrwを満たすかどうかを調べ、条件を満たす状態に対応する予測関数を、軌跡データに適用することで行う。前述の通り、いかなる移動オブジェクトも少なくとも条件Ｃrwは満たす。このため、移動オブジェクトは必ずどれかの状態として特定される。オブジェクトが停滞および直進の両方の条件を満たしている場合は、停滞状態にあるものとして予測を行う。これはＲst（ｊ）のほうがＲsw（ｊ）より小さい予測範囲になるためである。
【００５７】
図２を参照して、移動予測処理の具体例について説明する。移動予測装置３の移動予測部３１は、オブジェクトデータ管理装置２からの予測要求２Ａに応じて、図２の移動予測処理を実行する。
まず、移動予測部３１は、予測要求２Ａから軌跡データλt，−m＝｛ｐ（ｔ−ｍ），....，ｐ（ｔ）｝を取得し（ステップ１００：データ取得手段）、この軌跡データから各移動速度ベクトルｖ（ｉ）＝ｐ（ｉ）−ｐ（ｉ−１）を算出する（ステップ１０１：移動速度算出手段）。
【００５８】
次に、軌跡データが停滞条件Ｃst：｜ｐ（ｉ）−ｐ（ｔ）｜＜θpを満足するか検査し（ステップ１０２：移動状態特定手段）、Ｃstを満足する場合は（ステップ１０２：ＹＥＳ）、時刻ｊにおける当該移動オブジェクトの移動予測範囲はｐ（ｔ）を中心とする半径θpの円内の領域とする（ステップ１０３：移動予測範囲算出手段）。
【００５９】
一方、Ｃstを満足しない場合（ステップ１０２：ＮＯ）、軌跡データが直進条件Ｃsw：｜ｖ（ｉ）−ｖ（ｔ）｜＜θpを満足するか検査し（ステップ１０４：移動状態特定手段）、Ｃswを満足する場合は（ステップ１０４：ＹＥＳ）、時刻ｊにおける当該移動オブジェクトの移動予測範囲はｐ（ｔ）＋（ｊ−ｔ）ｖ（ｔ）を中心とする半径θpの円内の領域とする（ステップ１０５：移動予測範囲算出手段）。
【００６０】
また、Ｃrwを満足しない場合（ステップ１０４：ＮＯ）、軌跡データが乱歩条件Ｃrw：｜ｖ（ｉ）｜≦ｖmax＋θpを満足するか検査し（ステップ１０６：移動状態特定手段）、Ｃrwを満足する場合は（ステップ１０６：ＹＥＳ）、時刻ｊにおける当該移動オブジェクトの移動予測範囲はｐ（ｔ）を中心とする半径（ｊ−ｔ）ｖmax＋θpの円内の領域とする（ステップ１０７：移動予測範囲算出手段）。
【００６１】
このように、本実施の形態は、移動予測装置により、軌跡データが移動オブジェクトの停滞、直進、および乱歩の各移動状態を示す条件のいずれを満たすか判定することにより移動オブジェクトの移動状態を特定し、この特定された移動オブジェクトの移動状態に応じて当該移動オブジェクトの移動予測範囲を算出するようにしたので、移動オブジェクトの移動状態に応じて適切に位置揺らぎを考慮して移動予測範囲を算出でき、位置揺らぎ（測定誤差）を含むデータを用いてオブジェクトの移動先を予測する場合でも、比較的少ない計算量で、高い予測精度が得られる。
【００６２】
［第２の実施の形態］
次に、移動オブジェクトＤＢシステムのオブジェクトデータ管理装置２におけるインデクス作成動作について説明する。
各移動オブジェクトに対するインデクス構造としては、ＴＰＲ−ＴｒｅｅやＳＴＰ−Ｔｒｅｅなどと同様に、ｄ次元空間に時間軸を加えたｄ＋１次元上の、Ｒ−Ｔｒｅｅをベースとした木構造を用いる。移動オブジェクトＤＢシステムでは、センサで追跡されている移動オブジェクトの位置データを時刻ごとに一斉に集め、それらをまとめてデータベースに追加する形態が多い。
【００６３】
このため、本実施の形態では、一般のＲ−Ｔｒｅｅとは異なり、オブジェクトデータは常に現在時刻の位置データのみが一斉に追加されるものとする。すなわち、過去の時刻のデータが追加されるケースは扱わない。このように仮定すると、移動オブジェクト間の距離や速度差などを予め算出してからＭＢＲを作成できるため、一般のＲ−Ｔｒｅｅよりも効率のよいインデクスを作ることができる。
【００６４】
具体的なＭＢＲ（Minimum Bounding Rectangle：最小被覆図形）の作成方法について説明する。まず、ＭＢＲを作成する時刻ｔの各移動オブジェクトの位置ベクトルｐ（ｔ）を調べ、各移動オブジェクト間の距離を調べておく。次に、クラスタリング手法の１つである群平均法を用いて、予め決められた数のクラスに分ける。このクラスタリングにより、比較的近くにある移動オブジェクト同士が同じクラスに属することになる。なお、１つのクラスに属する移動オブジェクトの数は予め定めておく。作成されたクラスに含まれるそれぞれの移動オブジェクトの位置を調べ、これを葉ノードのＭＢＲとする。中間ノードのＭＢＲは、葉ノードのＭＢＲを作成した後に作成する。その後、各オブジェクトについて移動先の予測を行い、時刻ｔ＋１からｔ＋ｎまでの予測ＭＢＲを作成する。
【００６５】
予測されたＭＢＲから、実際の移動オブジェクトが逸脱してしまった場合は、次のようにする。もし移動オブジェクトの逸脱が、ＭＢＲが生成されてから予め決められた時間間隔ｕ以内に発生したら、該当する時刻の該当するＭＢＲのサイズを、移動オブジェクトを含むサイズに変更することのみで対処する。もし時間間隔ｕを越えてこの逸脱が生じた場合は、すべての移動オブジェクトに対してＭＢＲを生成しなおす。ｕは予め装置の管理者によって決められた時間間隔である。
【００６６】
このようにしてＭＢＲを作成すると、移動オブジェクトを１つずつ追加しながらＲ−Ｔｒｅｅを作成していく場合に比べ、はるかに面積の小さなＭＢＲが作成される。なお、時刻ｔの時点に存在しなかった移動オブジェクトがそれ以降に追加されたときは、通常のＲ−Ｔｒｅｅ等と同じようにして、根側のＭＢＲから葉側へ追加を行う。
【００６７】
［第３の実施の形態］
次に、図５および図６を参照して、移動オブジェクトＤＢシステムのオブジェクトデータ管理装置２におけるデータ検索動作について説明する。図５は、インデクス（ＭＢＲ）の階層構成を示す上面図である。図６は、インデクス（ＭＢＲ）の階層構成を示すツリー構造図である。
オブジェクトデータの検索は、Ｒ−Ｔｒｅｅ（既存技術）と同様の方法にて行う。具体的な方法について、最も基本的な方法を説明する。
【００６８】
まず、作成されたインデクス（ＭＢＲ）を、時刻ごとに図６に示すように階層化しておく。上位の層のＭＢＲは、図５に示すように、下位の層のＭＢＲを完全に包含するように作成する。そして、ＭＢＲが含む下位のＭＢＲ群の位置とサイズを記録しておく。この操作を上位層に向かって繰り返す。このように操作を行うと、最も上位の層のＭＢＲは、すべての下位の層のＭＢＲを含む形状になる。
【００６９】
データの検索の操作は、指定された範囲にあるオブジェクトを全て求める操作である。まず、作成した階層構造の最上層にあるＭＢＲに、指定された範囲が含まれるかどうかを判定する。ここで、指定された範囲がＭＢＲの形状内に含まれない場合は、求めるべき移動オブジェクトが存在しないことを意味する。すなわち、「該当オブジェクトなし」という答えを返す。
【００７０】
ＭＢＲ内に指定された範囲が含まれる場合は、ＭＢＲが含んでいる下位のＭＢＲの形状と、指定された範囲とに重複する部分があるかどうかを調べる。もし重複する範囲があれば、重複部位を持つＭＢＲについて、さらにそのＭＢＲが含む下位層のＭＢＲ群について、同様の範囲重複チェックを行う。このようにして、最も下位の層にあるＭＢＲのうち、指定された範囲と重複する部位を持つＭＢＲのリストを取り出す。最後に、この取り出されたＭＢ：Ｒに含まれるオブジェクトのうち、指定された範囲に含まれているオブジェクトに関するオブジェクトデータをデータ蓄積部２３から取り出す。この取り出されたオブジェクトデータを検索結果４Ｂとして返す。
【図面の簡単な説明】
【００７１】
【図１】本発明の第１の実施の形態にかかる移動予測装置が用いられる移動オブジェクトＤＢシステムの構成を示すブロック図である。
【図２】本発明の第１の実施の形態にかかる移動予測装置における移動予測処理を示すフローチャートである。
【図３】直進状態での移動予測範囲を示す説明図である。
【図４】乱歩状態での移動予測範囲を示す説明図である。
【図５】インデクス（ＭＢＲ）の階層構成を示す上面図である。
【図６】インデクス（ＭＢＲ）の階層構成を示すツリー構造図である。
【図７】ＴＲＰ−Ｔｒｅｅによる位置予測方法を示す説明図である。
【符号の説明】
【００７２】
１…軌跡データ入力装置、１１…データ取得部、１Ａ…軌跡データ、２…オブジェクトデータ管理装置、２１…データ生成部、２２…データ検索部、２３…データ蓄積部、２Ａ…予測要求、２Ｂ…予測結果、３…移動予測装置、３１…移動予測部、４…データ検索装置、４１…データ検索部、４Ａ…検索要求、４Ｂ…検索結果、５…軌跡データ、６Ａ…検索要求、６Ｂ…検索結果。
【図１】
0004627256.tif 000002
【図２】
0004627256.tif 000003
【図３】
0004627256.tif 000004
【図４】
0004627256.tif 000005
【図５】
0004627256.tif 000006
【図６】
0004627256.tif 000007
【図７】
0004627256.tif 000008