JP2018100921A - 移動軌跡に応じて地図上の経路を推定するプログラム、装置及び方法 - Google Patents

Abstract

【課題】携帯端末の移動軌跡の中で、少ない位置情報数で且つ少ない計算量で、地図上の滞在地間の経路を高精度に推定することができるプログラム、装置及び方法を提供する。
【解決手段】経路推定装置は、過去の複数の移動軌跡に基づく各履歴地点を蓄積した履歴地点蓄積手段と、滞在地間に、異なる経路種別の複数の経路が表示された地図を重畳する地図重畳手段と、滞在地間で、経路推定対象の移動軌跡における移動地点それぞれと距離が最も近い、滞在地間の地図上の経路を選択する第１の経路選択手段と、選択された経路の経路種別が、所定経路種別以外である場合に、履歴地点蓄積手段に蓄積された複数の履歴地点の中から、所定条件に一致する履歴地点を、補間地点として選定する補間地点選定手段と、複数の補間地点それぞれと距離が最も近い、滞在地間の地図上の経路を選択する第２の経路選択手段としてコンピュータを機能させる。
【選択図】図１

Description

本発明は、携帯端末を所持したユーザの移動軌跡を推定する技術に関する。

従来、移動体の軌跡に途切れが頻発する場合でも、どの移動体の軌跡であるかを高精度に識別する技術がある（例えば特許文献１参照）。この技術によれば、人物の移動軌跡（動線）を推定するために、カメラによる撮影画像を用いている。特定人物の識別情報及び特徴情報を予め学習しておき、運用段階の映像からその人物の画像を抽出する。これによって、異なる複数のカメラによって撮影された映像から、特定人物の動線を推定することができる。

また、観測領域内で、移動体の動線を高精度に補正する技術もある（例えば特許文献２参照）。この技術によれば、観測領域内に設置された複数の設備装置の位置情報を予め記憶し、移動体がこれら設備装置に近接又は接触した際に、その設備装置の位置情報を用いて、移動体の動線を補正する。

更に、車両の現在地から目的地までの経路が複数ある場合、自車が過去に通過した経路内に存在する区間の通過回数に基づいて、走行する可能性が高い経路を選定する技術もある（例えば特許文献３参照）。

更に、出発地から目的地までの経路間に生じた測位点間の移動経路を推定する技術もある（例えば特許文献４参照）。この技術によれば、第１及び第２の基準点の位置情報及び種別情報に基づいて、その間の複数の経路及び経路毎の所要時間を探索し、測位点間の測位時刻に基づいて第１及び第２の測位点間の移動経路を推定する。

更に、他の位置情報を用いて、当該ユーザの位置情報を補間して移動軌跡を再現する技術もある（例えば非特許文献１参照）。この技術によれば、不規則に得られたユーザの位置情報から、位置情報が欠落した区間の空間情報（地図情報）と時刻情報を算出し、欠落した区間と時刻に生じた他の位置情報を用いて、当該ユーザの位置情報として補間する。

特許５６８２５６３号公報 特開２０１０−１９７１９４号公報 特開２０１６−０９５１６１号公報 特開２０１２−２１２３２０号公報

M. Li, A. Ahmed, and A. J. Smola. "Inferring movement trajectories from gps snippets", In International Conference on Web Search and Data Mining (WSDM), 2015.、[online]、［平成２８年１２月７日検索］、インターネット＜URL:http://www.cs.cmu.edu/~muli/file/geo.pdf＞

特許文献１に記載の技術によれば、人物の動線のエリアにカメラを設置し、人物の映像を撮影する必要がある。
特許文献２に記載の技術によれば、人物の動線のエリアに、通信デバイスを搭載した設備装置を配置する必要がある。設備装置の通信デバイスは、移動体が近接又は接触する毎に、そのデータをサーバへ送信する必要がある。
このように、従来技術によれば、移動体の軌跡を高精度に検出するために、カメラや設備装置のような他の装置を必要としている。

特許文献３に記載の技術によれば、ユーザが例えば道路工事等の影響によって、経路を変更した場合、正しい経路を推定することは難しい。
特許文献４に記載の技術によれば、移動時の位置情報があることを前提としているため、道路と線路が並行している区間にのみ移動の位置情報があった場合、正しく推定することは難しい。
非特許文献１に記載の技術によれば、補間区間と一定の距離以内かつ一定の時刻差の時のログを用いているが、移動速度を考慮していないため、単純に人が最も多く通った道路が選定される可能性が高い。

一方で、携帯端末の位置情報のみから高精度に移動軌跡を検出する場合、携帯端末は、自ら測位した位置情報を、高い頻度（短い時間間隔）でサーバへ送信する必要がある。
しかしながら、ＧＰＳ(Global Positioning System)を用いた場合、携帯端末は、そのＧＰＳを常時起動し、位置情報を常時送信しなければならず、携帯端末の消費電力や無線リソースの観点から負担が大きい。
また、基地局測位の場合、基地局配置の空間的粒度が粗く、ＧＰＳのように高い測位精度は得られない。
更に、無線ＬＡＮやＢＬＥ(Bluetooth Low Energy)の場合、測位精度は高いが、狭域の屋内を対象とした位置情報しか検出できない。
更に、ＰＤＲ（Pedestrian Dead Reckoning、歩行者向け自律航法）の場合、ユーザの移動軌跡を取得するために常時起動しておく必要があり、測位のために起点や向きのような他の情報を要する。
更に、低密度な位置情報を用いて、地図にマッピングして経路を推定することもできるが、最短距離や最短時間の経路が推定されやすい。また、推定された経路も、例えば道路幅が広い道路に限定的されやすい。

そこで、本発明は、携帯端末の移動軌跡の中で、少ない位置情報数で且つ少ない計算量で、地図上の滞在地間の経路を高精度に推定することができるプログラム、装置及び方法を提供することを目的とする。

本発明によれば、経路推定対象の移動軌跡に沿って滞在地間の経路を推定するように、コンピュータを機能させるプログラムであって、
過去の複数の移動軌跡に基づく各履歴地点を蓄積した履歴地点蓄積手段と、
滞在地間に、異なる経路種別の複数の経路が表示された地図を重畳する地図重畳手段と、
滞在地間で、経路推定対象の移動軌跡における移動地点それぞれと距離が最も近い、滞在地間の地図上の経路を選択する第１の経路選択手段と、
選択された経路の経路種別が、所定経路種別以外である場合に、履歴地点蓄積手段に蓄積された複数の履歴地点の中から、所定条件に一致する履歴地点を、補間地点として選定する補間地点選定手段と、
複数の補間地点それぞれと距離が最も近い、移動地点同士の間又は滞在地と移動地点との間の、地図上の経路を選択する第２の経路選択手段と
してコンピュータを機能させることを特徴とする。

本発明のプログラムにおける他の実施形態によれば、
第１の経路選択手段は、１つ以上の移動地点と、滞在地間の地図上の各経路との間の最短距離を算出し、該最短距離の積算値が最小となる経路を選択し、
第２の経路選択手段は、複数の補間地点それぞれと、滞在地間の地図上の所定経路種別以外の経路との間の最短距離を算出し、該最短距離の積算値が最小となる経路を選択する
ようにコンピュータを機能させることも好ましい。

本発明のプログラムにおける他の実施形態によれば、
補間地点選定手段における所定経路種別は、線路である
ようにコンピュータを機能させることも好ましい。

本発明のプログラムにおける他の実施形態によれば、
経路推定対象の移動軌跡における時系列の位置情報から、所定時間以上の滞留状態を判定し、該滞留状態の位置情報を滞在地として推定する滞在地推定手段と
して更にコンピュータを機能させることも好ましい。

本発明のプログラムにおける他の実施形態によれば、
補間地点選定手段によって選定された補間地点に、第２の経路選択手段によって選択された経路の経路種別をラベル付けし、当該補間地点を履歴地点として履歴地点蓄積手段へ再度蓄積する経路種別付与手段と
して更にコンピュータを機能させ、
補間地点選定手段は、第１の経路選択手段によって選択された経路の経路種別と同じ経路種別のラベルが付与された履歴地点のみを、補間地点として選定する
ようにコンピュータを機能させることも好ましい。

本発明のプログラムにおける他の実施形態によれば、
所定方位角を予め設定した選定条件設定手段と、
経路推定対象の移動軌跡に沿って、移動地点間毎に、移動前地点から移動後地点への移動方位を算出する移動方位算出手段と
して更にコンピュータを機能させ、
補間地点選定手段は、履歴地点蓄積手段に蓄積された複数の履歴地点の中から、移動前地点から移動方位に向かって「所定方位角」の地域範囲に含まれる履歴地点を、補間地点として選定する
ようにコンピュータを機能させることも好ましい。

本発明のプログラムにおける他の実施形態によれば、
補間地点選定手段は、移動後地点から移動前地点への逆向きの移動方位に向かって所定方位角の地域範囲に含まれる履歴地点に更に絞り込んで選定する
ようにコンピュータを機能させることも好ましい。

本発明のプログラムにおける他の実施形態によれば、
履歴地点蓄積手段は、過去の複数の移動軌跡に基づく各履歴地点に、当該履歴地点から移動後履歴地点への第１の履歴方位を更に対応付けて蓄積しており、
選定条件設定手段は、「第１の所定方位差」を更に設定しており、
補間地点選定手段は、経路推定対象の移動方位との差が、第１の所定方位差以下となる第１の履歴方位の履歴地点に更に絞り込んで選定する
ようにコンピュータを機能させることも好ましい。

本発明のプログラムにおける他の実施形態によれば、
履歴地点蓄積手段は、過去の複数の移動軌跡に基づく各履歴地点に、当該履歴地点から、経路推定対象の移動後地点への第２の履歴方位を更に対応付けて蓄積しており、
選定条件設定手段は、「第２の所定方位差」を更に設定しており、
補間地点選定手段は、経路推定対象の移動方位との差が、第２の所定方位差以下となる第２の履歴方位の履歴地点に更に絞り込んで選定する
ようにコンピュータを機能させることも好ましい。

本発明のプログラムにおける他の実施形態によれば、
履歴地点蓄積手段は、過去の複数の移動軌跡に基づく各履歴地点に、当該履歴地点から移動後履歴地点への時間経過に伴う履歴速度を更に対応付けて蓄積しており、
経路推定対象の移動軌跡に沿って、移動前地点から移動後地点への移動速度を算出する移動速度算出手段として更に機能させ、
選定条件設定手段は、「所定速度差」を更に設定しており、
補間地点選定手段は、経路推定対象の移動速度との差が、所定速度差以下となる履歴速度の履歴地点に更に絞り込んで選定する
ようにコンピュータを機能させることも好ましい。

本発明のプログラムにおける他の実施形態によれば、
経路推定対象の移動軌跡に沿った移動地点と、履歴地点蓄積手段に蓄積された過去の複数の移動軌跡に基づく履歴地点とは、同一ユーザによって又は異なるユーザによって記録されたものであり、
選定条件設定手段は、同一ユーザに対する選定条件と、異なるユーザに対する選定条件とを別々に設定する
ようにコンピュータを機能させることも好ましい。

本発明によれば、経路推定対象の移動軌跡に沿って滞在地間の経路を推定する装置であって、
過去の複数の移動軌跡に基づく各履歴地点を蓄積した履歴地点蓄積手段と、
滞在地間に、異なる経路種別の複数の経路が表示された地図を重畳する地図重畳手段と、
滞在地間で、経路推定対象の移動軌跡における移動地点それぞれと距離が最も近い、滞在地間の地図上の経路を選択する第１の経路選択手段と、
選択された経路の経路種別が、所定経路種別以外である場合に、履歴地点蓄積手段に蓄積された複数の履歴地点の中から、所定条件に一致する履歴地点を、補間地点として選定する補間地点選定手段と、
複数の補間地点それぞれと距離が最も近い、移動地点同士の間又は滞在地と移動地点との間の、地図上の経路を選択する第２の経路選択手段と
を有することを特徴とする。

本発明によれば、経路推定対象の移動軌跡に沿って滞在地間の経路を推定する装置の経路推定方法であって、
装置は、過去の複数の移動軌跡に基づく各履歴地点を蓄積した履歴地点蓄積部を有し、
装置は、
滞在地間に、異なる経路種別の複数の経路が表示された地図を重畳する第１のステップと、
滞在地間で、経路推定対象の移動軌跡における複数の移動地点を抽出する第２のステップと、
複数の移動地点それぞれと距離が最も近い、滞在地間の地図上の経路を選択する第３のステップと、
選択された経路の経路種別が、所定経路種別以外である場合に、履歴地点蓄積手段に蓄積された複数の履歴地点の中から、所定条件に一致する履歴地点を、補間地点として選定する第４のステップと、
複数の補間地点それぞれと距離が最も近い、移動地点同士の間又は滞在地と移動地点との間の、地図上の経路を選択する第５のステップと
を実行することを特徴とする。

本発明のプログラム、装置及び方法によれば、携帯端末の移動軌跡の中で、少ない位置情報数で且つ少ない計算量で、地図上の滞在地間の経路を高精度に推定することができる。

本発明における経路推定装置の機能構成図である。 滞在地間を結ぶ地図上の経路を重畳した説明図である。 移動地点それぞれと距離が最も近い経路として、道路が選択された説明図である。 本発明における移動地点と補間用の履歴地点とを表す説明図である。 本発明における移動方位に対する所定方位角の地理範囲を表す説明図である。 本発明における逆向きの移動方位に対する所定方位角の地理範囲を表す説明図である。 本発明における移動方位に対する第１の所定方位差以内の履歴地点を表す説明図である。 本発明における移動速度に対する所定速度差以内の履歴地点を表す説明図である。 本発明によって推定された経路を表す説明図である。

以下、本発明の実施形態について、図面を用いて詳細に説明する。

図１は、本発明における経路推定装置の機能構成図である。

図１によれば、経路推定装置１は、携帯端末２（経路推定対象）の移動軌跡に沿って「滞在地」間の経路を推定する。経路推定装置１は、広域無線通信網に配置されており、携帯端末２からのデータを受信することができる。携帯端末２は、スマートフォンやタブレット、携帯電話機、ウェアラブルデバイスのようなものであり、一般に測位機能を搭載している。携帯端末２は、例えばＧＰＳによって自ら測位した「移動地点（緯度経度）」を経路推定装置１へ送信することができる。移動地点は、緯度経度であることが好ましいが、方位や速度を算出可能であれば任意の位置情報であってもよい。

尚、携帯端末２から移動地点が送信されるタイミングは、ユーザ操作に基づく能動的な通信に限られず、バックグラウンドで通信した場合や、ハンドオーバが実行された場合であってもよい。即ち、本発明によれば、携帯端末２の位置情報を取得するタイミングは何ら制約されない。

携帯端末２から移動地点を収集する頻度を増やすほど、地図上の経路を特定することは容易であるが、位置情報を取得する携帯端末２の処理負荷や、位置情報を転送するネットワークの処理負荷が増大することとなる。
ここで、携帯端末２を所持したユーザが、例えば線路上を電車で移動していると判断できる場合、収集した移動地点が少なくても、その経路は明確に特定することができる。
一方で、携帯端末２を所持したユーザが、例えば道路を移動していると判断できる場合、収集した移動地点が少ないほど、その経路は不明確となってしまう。
本発明の経路推定装置１は、携帯端末の移動軌跡の中で、収集すべき移動地点の数と、経路推定のための計算量と、経路の推定精度とのトレードオフを考慮して、経路推定の処理を実行することができる。

経路推定装置１は、滞在地推定部１１と、地図重畳部１２と、第１の経路選択部１３と、履歴地点蓄積部１０１と、選定条件設定部１０２と、移動方位算出部１４１と、移動速度算出部１４２と、補間地点選定部１５と、第２の経路選択部１６と、経路種別付与部１７とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。また、これら機能構成部の処理の流れは、装置の経路推定方法としても理解できる。

［滞在地推定部１１］
滞在地推定部１１は、携帯端末２によって測位された時系列の位置情報（移動地点）を収集する。位置情報は、携帯端末２から直接的に受信するものであってもよいし、特定の位置情報サーバから取得するものであってもよい。

次に、滞在地推定部１１は、携帯端末２毎に、時系列の位置情報から滞留状態を判定し、その滞留状態の位置情報を「滞在地」として推定する。
具体的には、滞在地推定部１１は、時系列の位置情報における所定時間（例えば３０分）以上の滞留を抽出し、当該滞留の位置を「滞在地」と推定する。
他の実施形態として、滞在地推定部１１は、携帯端末毎に、滞留する時間帯から、駅やバス停のような交通分岐位置を推定するものであってもよい。少なくとも交通分岐位置は、滞在地となる。

滞在地推定部１１は、交通分岐位置を予め登録しておき、その位置を中心とする所定半径に含まれる位置情報を、「交通分岐位置」と推定するものであってもよい。
また、滞在地推定部１１は、多数の携帯端末の滞留する時間帯の傾向から、交通分岐位置か否かを推定するものであってもよい。
例えば、時系列の位置情報について、「例えば半径５０ｍの地域範囲に連続して１０分以上滞留する携帯端末が、所定数以上存在する」場合、その地域範囲を「交通分岐位置」と推定することができる。また、「その滞留している日が、毎日の所定時間範囲で発生する」とする条件を更に加えて、その地域範囲を「交通分岐位置」と推定することも好ましい。
尚、滞在地推定部１１によって、携帯端末２の位置情報について、滞在地以外は、移動地点と判定される。

［地図重畳部１２］
地図重畳部１２は、滞在地間に、異なる経路種別の複数の経路が表示された地図を重畳する。

図２は、滞在地間を結ぶ地図上の経路を重畳した説明図である。
図２によれば、携帯端末２を所持したユーザの移動軌跡の中で、滞在地推定部１１によって、移動地点Ａと移動地点Ｂとが表されている。そして、推定された滞在地間に、線路及び道路のような、異なる経路種別の複数の経路が表示された地図が重畳されている。
そして、滞在地間で、携帯端末２の移動軌跡における１つ以上の移動地点が抽出される。

［第１の経路選択部１３］
第１の経路選択部１３は、移動地点それぞれと距離が最も近い、滞在地間の地図上の経路を選択する。具体的には、第１の経路選択部１３は、１つ以上の移動地点と、滞在地間の地図上の各経路との間の最短距離を算出し、該最短距離の積算値が最小となる経路を選択する。
尚、図２によれば、移動地点それぞれと距離が最も近い経路として、「線路１」が選択されている。

図３は、移動地点それぞれと距離が最も近い経路として、道路が選択された説明図である。
図３によれば、携帯端末２に対して、最短距離としては道路２が選択されている。ここで、道路が選択された場合、移動地点間の距離が長いほど、いずれの道路を経路としているか、不明なものとなる。一方で、携帯端末２から収集する移動地点の数を増やせば、携帯端末２の処理負荷や、位置情報を転送するネットワークの処理負荷が増大することとなる。
そこで、図３のように携帯端末２の経路として、「線路」以外、即ち例えば「道路」が推定された場合、過去の他のユーザの複数の履歴地点の中から補間地点を選定し、その補間地点を用いて、滞在地間の地図上の経路を選択する。

［履歴地点蓄積部１０１］
履歴地点蓄積部１０１は、過去の複数の移動軌跡に基づく各「履歴地点」を蓄積したものである。
これら「履歴地点」は、後述する経路種別付与部１７に基づく経路種別のラベルが付与されたものであってもよい。

［選定条件設定部１０２］
選定条件設定部１０２は、例えば以下のような条件を設定している。
＜条件１：履歴地点の選定＞
（条件１１）「所定方位角」の地域範囲に含まれる履歴地点の選定
（条件１２）逆向き「所定方位角」の地域範囲に含まれる履歴地点の選定
（条件１３）移動方位に対する「第１の所定方位差」に含まれる履歴地点の選定
（条件１４）移動方位に対する「第２の所定方位差」に含まれる履歴地点の選定
（条件１５）移動速度に対する「所定速度差」に含まれる履歴地点の選定
（条件１６）「所定日時刻範囲」に含まれる履歴地点の選定
＜条件２：履歴地点の間引き＞
（条件２１）履歴地点同士で「所定時間差」以下となる履歴地点の間引き
（条件２２）履歴地点同士で「所定距離」以下となる履歴地点の間引き
（条件２３）移動前地点から移動後地点までの距離以上となる履歴地点の間引き
（条件２４）移動前地点から移動後地点までの時間差以上となる履歴地点の間引き

履歴地点は、経路推定対象となる同一ユーザから過去に収集されたものであってもよいし、それ以外の他の異なるユーザから過去に収集されたものであってよい。
そのとき、選定条件設定部１０２は、同一ユーザに対する選定条件と、異なるユーザに対する選定条件とを別々に設定することが好ましい。
即ち、同一ユーザの過去の移動軌跡に基づく履歴地点を用いて補間する場合、高い精度で経路を推定することができる。この場合、選定条件の許容範囲が広くてもよいと考えられる。
一方で、異なるユーザの過去の移動軌跡に基づく多数の履歴地点を用いる場合、同一ユーザの場合ほど高い精度で経路を推定することはできない。この場合、選定条件の許容範囲を狭くした方がよいと考えられる。
同一ユーザに対する選定条件の許容範囲
＞ 異なるユーザに対する選定条件の許容範囲

図４は、本発明における移動地点と補間用の履歴地点とを表す説明図である。

図４によれば、以下の２つの地点が表されている。
経路推定対象となる携帯端末の移動前地点Ａ及び移動後地点Ｂ
過去の複数の移動履歴に基づく補間用の履歴地点１〜１５

移動地点について、以下のように用語を定義する。
「移動地点」 ：経路推定対象の携帯端末の移動軌跡に沿って測位された地点
「移動前地点」：移動地点であって、経路推定対象区間における移動前の地点
「移動後地点」：移動地点であって、経路推定対象区間における移動後の地点
尚、移動前地点又は移動後地点の一方が、滞在地となる場合もある。
また、移動前地点及び移動後地点との間の経路を推定するために、補間用に選定される履歴地点について、以下のように用語を定義する。
「履歴地点」 ：過去の複数の移動軌跡に沿った地点
「移動後履歴地点」：過去の移動軌跡の中で、当該履歴地点の次に移動した地点

図４（ａ）によれば、経路推定対象の携帯端末における移動前地点及び移動後地点に、以下の情報が対応付けられている。
＜位置情報（緯度・経度）、日時刻、移動方位、移動速度＞
「移動方位」は、移動前地点の緯度経度から、北を基準として、移動後地点の緯度経度へ向かう角度である。
「移動速度」は、移動前地点の日時刻から移動後地点の日時刻までの移動時間に対して、緯度経度に基づく移動距離から算出された速度である。

図４（ｂ）によれば、過去の複数の移動軌跡に基づく各履歴地点に、図４（ａ）と同様に、以下の情報が対応付けられている。
＜位置情報（緯度・経度）、日時刻、第１の履歴方位、第２の履歴方位、履歴速度＞
「第１の履歴方位」は、過去の移動軌跡に基づく当該履歴地点の緯度経度から、北を基準として、移動後履歴地点の緯度経度へ向かう角度である。
「第２の履歴方位」は、過去の移動軌跡に基づく当該履歴地点の緯度経度から、北を基準として、経路推定対象の移動後地点の緯度経度へ向かう角度である。
「履歴速度」は、過去の移動軌跡に基づく当該履歴地点の日時刻から移動後履歴地点の日時刻までの移動時間と、履歴地点間の履歴距離とから算出された速度である。
また、図４（ｂ）の履歴地点の情報として、路線や道路等を示す「経路種別のラベル」（後述）の項目が追加されてもよい。

［移動方位算出部１４１］
移動方位算出部１４１は、経路推定対象の移動軌跡に沿って、移動前地点から移動後地点への「移動方位」を算出する。具体的には、前述した図４（ａ）の「移動方位」を算出する。

［移動速度算出部１４２］
移動速度算出部１４２は、経路推定対象の移動軌跡に沿って、移動前地点から移動後地点への移動速度を算出する。
移動速度＝移動距離／（移動後地点の日時刻−移動前地点の日時刻）
移動速度は、例えば後述する図７で用いられる。

［補間地点選定部１５］
補間地点選定部１５は、最初に、選択された経路の経路種別が、所定経路種別（例えば路線）以外であるか否かを判定する。
即ち、補間地点選定部１５は、所定経路種別（例えば路線）である場合、その電車による移動経路は明確であって、以下のように補間地点を用いて移動経路を推定するまでもない。
一方で、補間地点選定部１５は、所定経路種別（例えば路線）以外、例えば「道路」である場合、履歴地点蓄積部１０１に蓄積された複数の履歴地点の中から、以下の条件のいずれか又はそれらの組み合わせに一致する履歴地点を、「補間地点」として選定する。

＜条件１：履歴地点の選定＞
（条件１１）「所定方位角」の地域範囲に含まれる履歴地点の選定
図５は、本発明における移動方位に対する所定方位角の地理範囲を表す説明図である。

選定条件設定部１０２には、「所定方位角」が設定されているとする。
このとき、補間地点選定部１５は、履歴地点蓄積部１０１に蓄積された複数の履歴地点の中から、移動前地点から移動方位に向かって「所定方位角」の地域範囲に含まれる履歴地点を選定する。

図５によれば、例えば「所定方位角＝４５度」が設定されているとする。
このとき、移動前地点Ａから移動後地点Ｂに向かう移動方位に対する４５度の地域範囲に含まれる履歴地点１、３、４、５、６、７、８、９、１０、１２、１３、１４が選定される。
一方で、移動方位に対する４５度の地域範囲に含まれない履歴地点２、１１、１５は、携帯端末２の経路を推定する補間対象の履歴地点としては選定しない。

（条件１２）逆向き「所定方位角」の地域範囲に含まれる履歴地点の選定
図６は、本発明における逆向きの移動方位に対する所定方位角の地理範囲を表す説明図である。

補間地点選定部１５は、履歴地点蓄積部１０１に蓄積された複数の履歴地点の中から、移動後地点から移動前地点への逆向きの移動方位に向かって所定方位角の地域範囲に含まれる履歴地点に更に絞り込んで選定する。

図６によれば、移動後地点Ｂから移動前地点Ａへ逆向きの移動方位に対する４５度（所定方位角）の地域範囲に含まれる履歴地点１、３、４、５、７、８、９、１０、１２、１３が選定される。
一方で、逆向きの移動方位に対する４５度の地域範囲に含まれない履歴地点６、１４は、携帯端末２の経路を推定する補間対象の履歴地点としては選定しない。

（条件１３）移動方位に対する「第１の所定方位差」に含まれる履歴地点の選定
図７は、本発明における移動方位に対する第１の所定方位差以内の履歴地点を表す説明図である。

選定条件設定部１０２には、「第１の所定方位差」が更に設定されている。
また、履歴地点蓄積部１０１は、過去の複数の移動軌跡に基づく各履歴地点に、当該履歴地点から移動後履歴地点への第１の履歴方位を更に対応付けて蓄積している。
このとき、補間地点選定部１５は、経路推定対象の移動方位との差が、第１の所定方位差以下となる第１の履歴方位の履歴地点に更に絞り込んで選定する。

図７によれば、例えば「第１の所定方位差＝４５度」が設定されているとする。
このとき、移動前地点Ａから移動後地点Ｂに向かう移動方位に対する４５度の方位差以内となる履歴地点１、４、５、７、８、１０、１２が選定される。
一方で、移動方位に対する４５度の第１の所定方位差以内とならない第１の履歴方位の履歴地点３、９、１３は、携帯端末２の経路を推定する補間対象の履歴地点としては選定しない。

（条件１４）移動方位に対する「第２の所定方位差」に含まれる履歴地点の選定
選定条件設定部１０２には、「第２の所定方位差」が更に設定されている。
また、履歴地点蓄積部１０１は、過去の複数の移動軌跡に基づく各履歴地点に、当該履歴地点から、経路推定対象の移動後地点への第２の履歴方位を更に対応付けて蓄積している。
このとき、補間地点選定部１５は、経路推定対象の移動方位との差が、第２の所定方位差以下となる第２の履歴方位の履歴地点に更に絞り込んで選定する。

例えば「第２の所定方位差＝４５度」が設定されているとする。
このとき、移動前地点Ａから移動後地点Ｂに向かう移動方位に対する４５度の方位差以内となる履歴地点１、４、５、７、８、１０、１２が選定される。
一方で、図示しないが、移動方位に対する４５度の第２の所定方位差以内とならない第２の履歴方位の履歴地点は、携帯端末２の経路を推定する補間対象の履歴地点としては選定しない。

（条件１５）移動速度に対する速度差に基づく履歴地点の選定
図８は、本発明における移動速度に対する所定速度差以内の履歴地点を表す説明図である。

選定条件設定部１０２には、「所定速度差」が更に設定されている。
また、履歴地点蓄積部１０１は、過去の複数の移動軌跡に基づく各履歴地点に、当該履歴地点から移動後履歴地点への時間経過に伴う履歴速度を更に対応付けて蓄積している。
このとき、補間地点選定部１５は、経路推定対象の移動速度との差が、所定速度差以下となる履歴速度の履歴地点に更に絞り込んで選定する。

図８によれば、例えば「第１の所定方位差＝１０ｋｍ／ｈ」が設定されているとする。
このとき、移動前地点Ａから移動後地点Ｂに向かう移動速度に対して、１０ｋｍ／ｈの速度差以内となる履歴地点１、４、５、８、９が選定される。
一方で、移動速度に対する１０ｋｍ／ｈの速度差以内とならない履歴地点３、７、１０、１２，１３は、携帯端末２の経路を推定する補間対象の履歴地点としては選定しない。

（条件１６）「所定日時刻範囲」に含まれる履歴地点の選定
選定条件設定部１０２には、「所定日時刻範囲」が更に設定されている。
このとき、補間地点選定部１５は、所定日時刻範囲に含まれる履歴日時刻の履歴地点に更に絞り込んで選定する。

＜条件２：履歴地点の間引き＞
ここでは、多数の履歴地点が選定され過ぎないようにするものであって、以下の条件のいずれか又はそれらの組み合わせに一致する履歴地点同士は、いずれか一方の履歴地点しか選定されないようにする。

（条件２１）履歴地点同士で「所定時間差」以下となる履歴地点の間引き
履歴地点蓄積部１０１は、過去の複数の移動軌跡に基づく各履歴地点に、当該履歴地点を記録した「履歴時刻（１日２４時間の中での時刻）」を更に対応付けて蓄積している。
そして、補間地点選定部１５は、第１の履歴地点の履歴時刻と第２の履歴地点の履歴時刻との間の時間差が「所定時間差」以上となるように、履歴地点を間引いて選定する。これによって、類似の時間帯で取得された履歴地点を選定しないようにする。

（条件２２）履歴地点同士で「所定距離」以下となる履歴地点の間引き
補間地点選定部１５は、第１の履歴地点と第２の履歴地点との間の距離が「所定距離」以上となるように、履歴地点を間引いて選定する。履歴地点同士の距離が短い履歴地点を選定しないようにする。

（条件２３）移動前地点から移動後地点までの距離以上となる履歴地点の間引き
補間地点選定部１５は、移動前地点から履歴地点までの距離が、移動前地点から移動後地点までの「移動距離」以下となるように、履歴地点を間引いて選定する。移動距離よりも離れた履歴地点を選定しないようにする。

（条件２４）移動前地点から移動後地点までの時間差以上となる履歴地点の間引き
補間地点選定部１５は、移動前地点の時刻から履歴地点の時刻までの時間が、移動前地点の時刻から移動後地点の時刻までの「移動時間」以下となるように、履歴地点を更に絞り込んで選定する。移動前地点の時刻よりも離れた時間帯の履歴地点を選定しないようにする。

［第２の経路選択部１６］
第２の経路選択部１６は、選択された滞在地間の経路の種別が所定経路種別（例えば路線）以外、例えば「道路」である場合には、経路推定対象の移動前地点と移動後地点との間の経路を、補間地点選定部１５によって選定された履歴地点によって補間して推定する。
複数の補間地点それぞれと距離が最も近い、移動地点同士の間又は滞在地と移動地点との間の、地図上の経路を選択する。

図９は、本発明によって推定された経路を表す説明図である。

図９によれば、第２の経路選択部１６は、複数の補間地点それぞれと、滞在地間の地図上の所定経路種別以外の経路との間の最短距離を算出し、該最短距離の積算値が最小となる経路を選択する。

［経路種別付与部１７］
経路種別付与部１７は、補間地点選定部１５によって選定された補間地点に、第２の経路選択部１６によって選択された経路の経路種別を、ラベル付けする。例えば図８によれば、補間地点に、経路種別「道路」が付与される。そして、その補間地点を履歴地点として履歴地点蓄積部１０１へ再度蓄積する。
これによって、補間地点選定部１５は、第１の経路選択部１３によって選択された経路の経路種別と同じ経路種別のラベルが付与された履歴地点のみを、補間地点として選定することができる。

以上、詳細に説明したように、本発明のプログラム、装置及び方法によれば、携帯端末の移動軌跡の中で、少ない位置情報数で且つ少ない計算量で、地図上の滞在地間の経路を高精度に推定することができる。

前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。

１ 経路推定装置
１０１ 履歴地点蓄積部
１０２ 選定条件設定部
１１ 滞在地推定部
１２ 地図重畳部
１３ 第１の経路選択部
１４１ 移動方位算出部
１４２ 移動速度算出部
１５ 補間地点選定部
１６ 第２の経路選択部
１７ 経路種別付与部
２ 携帯端末

Claims (13)

1. 経路推定対象の移動軌跡に沿って滞在地間の経路を推定するように、コンピュータを機能させるプログラムであって、
   過去の複数の移動軌跡に基づく各履歴地点を蓄積した履歴地点蓄積手段と、
   滞在地間に、異なる経路種別の複数の経路が表示された地図を重畳する地図重畳手段と、
   滞在地間で、経路推定対象の移動軌跡における移動地点それぞれと距離が最も近い、滞在地間の地図上の経路を選択する第１の経路選択手段と、
   選択された前記経路の経路種別が、所定経路種別以外である場合に、前記履歴地点蓄積手段に蓄積された複数の履歴地点の中から、所定条件に一致する履歴地点を、補間地点として選定する補間地点選定手段と、
   複数の補間地点それぞれと距離が最も近い、移動地点同士の間又は滞在地と移動地点との間の、地図上の経路を選択する第２の経路選択手段と
   してコンピュータを機能させることを特徴とするプログラム。
2. 第１の経路選択手段は、１つ以上の移動地点と、滞在地間の地図上の各経路との間の最短距離を算出し、該最短距離の積算値が最小となる経路を選択し、
   第２の経路選択手段は、複数の補間地点それぞれと、滞在地間の地図上の所定経路種別以外の経路との間の最短距離を算出し、該最短距離の積算値が最小となる経路を選択する
   ようにコンピュータを機能させることを特徴とする請求項１に記載のプログラム。
3. 前記補間地点選定手段における前記所定経路種別は、線路である
   ようにコンピュータを機能させることを特徴とする請求項１又は２に記載のプログラム。
4. 経路推定対象の移動軌跡における時系列の位置情報から、所定時間以上の滞留状態を判定し、該滞留状態の位置情報を滞在地として推定する滞在地推定手段と
   して更にコンピュータを機能させることを特徴とする請求項１から３のいずれか１項に記載のプログラム。
5. 前記補間地点選定手段によって選定された補間地点に、第２の経路選択手段によって選択された経路の経路種別をラベル付けし、当該補間地点を履歴地点として前記履歴地点蓄積手段へ再度蓄積する経路種別付与手段と
   して更にコンピュータを機能させ、
   前記補間地点選定手段は、第１の経路選択手段によって選択された経路の経路種別と同じ経路種別のラベルが付与された履歴地点のみを、補間地点として選定する
   ようにコンピュータを機能させることを特徴とする請求項１から４のいずれか１項に記載のプログラム。
6. 所定方位角を予め設定した選定条件設定手段と、
   経路推定対象の移動軌跡に沿って、移動地点間毎に、移動前地点から移動後地点への移動方位を算出する移動方位算出手段と
   して更にコンピュータを機能させ、
   前記補間地点選定手段は、前記履歴地点蓄積手段に蓄積された複数の履歴地点の中から、前記移動前地点から前記移動方位に向かって「所定方位角」の地域範囲に含まれる履歴地点を、補間地点として選定する
   ようにコンピュータを機能させることを特徴とする請求項１から５のいずれか１項に記載のプログラム。
7. 前記補間地点選定手段は、前記移動後地点から前記移動前地点への逆向きの移動方位に向かって所定方位角の地域範囲に含まれる履歴地点に更に絞り込んで選定する
   ようにコンピュータを機能させることを特徴とする請求項６に記載のプログラム。
8. 前記履歴地点蓄積手段は、過去の複数の移動軌跡に基づく各履歴地点に、当該履歴地点から移動後履歴地点への第１の履歴方位を更に対応付けて蓄積しており、
   前記選定条件設定手段は、「第１の所定方位差」を更に設定しており、
   前記補間地点選定手段は、経路推定対象の前記移動方位との差が、第１の所定方位差以下となる第１の履歴方位の履歴地点に更に絞り込んで選定する
   ようにコンピュータを機能させることを特徴とする請求項６又は７に記載のプログラム。
9. 前記履歴地点蓄積手段は、過去の複数の移動軌跡に基づく各履歴地点に、当該履歴地点から、前記経路推定対象の移動後地点への第２の履歴方位を更に対応付けて蓄積しており、
   前記選定条件設定手段は、「第２の所定方位差」を更に設定しており、
   前記補間地点選定手段は、経路推定対象の前記移動方位との差が、第２の所定方位差以下となる第２の履歴方位の履歴地点に更に絞り込んで選定する
   ようにコンピュータを機能させることを特徴とする請求項６から８のいずれか１項に記載のプログラム。
10. 前記履歴地点蓄積手段は、過去の複数の移動軌跡に基づく各履歴地点に、当該履歴地点から移動後履歴地点への時間経過に伴う履歴速度を更に対応付けて蓄積しており、
    経路推定対象の移動軌跡に沿って、移動前地点から移動後地点への移動速度を算出する移動速度算出手段として更に機能させ、
    前記選定条件設定手段は、「所定速度差」を更に設定しており、
    前記補間地点選定手段は、経路推定対象の前記移動速度との差が、所定速度差以下となる履歴速度の履歴地点に更に絞り込んで選定する
    ようにコンピュータを機能させることを特徴とする請求項６から９のいずれか１項に記載のプログラム。
11. 経路推定対象の移動軌跡に沿った移動地点と、前記履歴地点蓄積手段に蓄積された過去の複数の移動軌跡に基づく履歴地点とは、同一ユーザによって又は異なるユーザによって記録されたものであり、
    前記選定条件設定手段は、同一ユーザに対する選定条件と、異なるユーザに対する選定条件とを別々に設定する
    ようにコンピュータを機能させることを特徴とする請求項６から１０のいずれか１項に記載のプログラム。
12. 経路推定対象の移動軌跡に沿って滞在地間の経路を推定する装置であって、
    過去の複数の移動軌跡に基づく各履歴地点を蓄積した履歴地点蓄積手段と、
    滞在地間に、異なる経路種別の複数の経路が表示された地図を重畳する地図重畳手段と、
    滞在地間で、経路推定対象の移動軌跡における移動地点それぞれと距離が最も近い、滞在地間の地図上の経路を選択する第１の経路選択手段と、
    選択された前記経路の経路種別が、所定経路種別以外である場合に、前記履歴地点蓄積手段に蓄積された複数の履歴地点の中から、所定条件に一致する履歴地点を、補間地点として選定する補間地点選定手段と、
    複数の補間地点それぞれと距離が最も近い、移動地点同士の間又は滞在地と移動地点との間の、地図上の経路を選択する第２の経路選択手段と
    を有することを特徴とする装置。
13. 経路推定対象の移動軌跡に沿って滞在地間の経路を推定する装置の経路推定方法であって、
    前記装置は、過去の複数の移動軌跡に基づく各履歴地点を蓄積した履歴地点蓄積部を有し、
    前記装置は、
    滞在地間に、異なる経路種別の複数の経路が表示された地図を重畳する第１のステップと、
    滞在地間で、経路推定対象の移動軌跡における移動地点それぞれと距離が最も近い、滞在地間の地図上の経路を選択する第２のステップと、
    選択された前記経路の経路種別が、所定経路種別以外である場合に、前記履歴地点蓄積部に蓄積された複数の履歴地点の中から、所定条件に一致する履歴地点を、補間地点として選定する第３のステップと、
    複数の補間地点それぞれと距離が最も近い、移動地点同士の間又は滞在地と移動地点との間の、地図上の経路を選択する第４のステップと
    を実行することを特徴とする装置の経路推定方法。

Images