(57)【要約】    過去の軌跡データ（２８）を用いて、纏められた物体（２２）のための障害横断情報を判断する方法。類似する地理的及び行き先の特徴を有する記録された軌跡は、軌跡密度が、位置及び時間（ｓ，ｔ）の関数として計測できるように、束に纏められる。視覚化されて表示された軌跡情報は、デジタルマップで有用な、あるタイプの障害横断情報を判断するために用いることができる。多数の軌跡密度時系列に対する周波数分析は、車両の大幅な増加を検出することにより、特定の障害横断場所（２６）を判断するために行うことができる。このような周波数分析は、また、横断パターンにおける障害横断時間及びスケジュールを示す。
2013534621.tif 000002
【特許請求の範囲】
【請求項１】
過去の軌跡データ（２８）を用いて、纏められた物体（２２）の障害（１６）横断情報を判断する方法であって、
障害（１６）によって互いに分断された第１（１８）及び第２の（２０）の道路部分を有するデジタルマップを提供する工程であって、前記第１及び第２の道路部分間の前記分断距離が障害の弧長（Ｌ）を含む工程と、
前記第１（１８）及び第２の（２０）の道路部分間の障害（１６）を横断する複数の物体（２２）から、時間（ｔ）をかけて、軌跡（２８）を記録する工程であって、各軌跡が時系列のジオポジション（ｓ）及びタイムスタンプ（ｔ）データを含む工程と、
類似した地理的及び行き先の特徴を有する記録された軌跡（２８）を束に纏める工程と、
前記束（２８’）の軌跡密度を、位置（ｓ）及び時間（ｔ）の関数として計測する工程と、
前記束（２８’）の前記軌跡密度における測定された変化に基づいて、纏められた物体（２２）の障害横断情報を判断する工程とを有し、前記障害横断情報は、出発地点（２６）、横断時刻表、横断頻度、横断時間、及び平均横断速度（ｖ）の少なくとも１つを含むことを特徴とする方法。
【請求項２】
前記束の弧長上にある位置（ｓ）における密度が、零から零よりも十分に大きい値に突然変化する場合に、前記束（２８’）を集団的横断と特定する工程を更に有することを特徴とする請求項１に記載の方法。
【請求項３】
前記束に纏める工程は、代表的な軌跡を選択する工程を含むことを特徴とする請求項１または２に記載の方法。
【請求項４】
前記束に纏める工程は、既存のデジタルマップに照合することにより選択された既存の幾何学を用いる工程を含むことを特徴とする請求項１乃至３のいずれか１項に記載の方法。
【請求項５】
時間（ｔ）の間、前記束（２８’）の弧長上の位置（ｓ）における、前記束（２８’）の前記軌跡密度の周期的な変化の周波数を判断する工程を更に有することを特徴とする請求項１乃至４のいずれか１項に記載の方法。
【請求項６】
スペクトルエネルギー図における前記周波数の変化を図表を用いて表す工程を更に有することを特徴とする請求項５に記載の方法。
【請求項７】
前記スペクトルエネルギー図は周波数毎の振幅を識別し、前記振幅スペクトルから、集団的横断周波数を直接判断する工程を更に有することを特徴とする請求項６に記載の方法。
【請求項８】
前記周波数分布に基づいて前記障害横断経路の終点（２６）を識別する工程を更に有することを特徴とする請求項１乃至７のいずれか１項に記載の方法。
【請求項９】
前記束の前記終点（２６）を識別する工程は、
ｖ０＝振幅スペクトルにおける最も大きいピークの周波数
ｖ１＝振幅スペクトルにおける次に大きいピークの周波数
Ａ（ｖ）＝周波数ｖの振幅スペクトルにおける振幅の絶対値
である場合に、式
Ｃ＝Ａ（ｖ１）／Ａ（ｖ０）
により表される２つの最も大きい周波数ピーク間の比に等しい閾値基準（Ｃ）を確立する工程を含むことを特徴とする請求項８に記載の方法。
【請求項１０】
前記閾値基準（Ｃ）は、約０．３であることを特徴とする請求項９に記載の方法。
【請求項１１】
前記周期的な周波数を判断する工程は、労働日と、非労働日について別々に周波数の決定を行うことを特徴とする請求項１乃至１０のいずれか１項に記載の方法。
【請求項１２】
異なる日について時刻表を決定する工程を更に有することを特徴とする請求項１乃至１１のいずれか１項に記載の方法。
【請求項１３】
前記判断された障害横断情報を属性に変換し、更に、前記デジタルマップに属性として補足する工程を更に有することを特徴とする請求項１乃至１２のいずれか１項に記載の方法。
【請求項１４】
前記束（２８’）の各軌跡（２８）に属性を付ける工程を更に有することを特徴とする請求項１３に記載の方法。
【請求項１５】
複数の物体（２２）を供給する工程を更に有し、前記物体（２２）の少なくともいくつかは、時系列のジオポジション（ｓ）及び時間（ｔ）の記録を含む新しい軌跡（２８）を生成することができることを特徴とする請求項１乃至１４のいずれか１項に記載の方法。
【請求項１６】
前記障害（１６）付近の前記第１の道路部分（１８）上にある前記物体を周期的に集め、前記障害（１６）を横断した前記第２の道路部分（２０）まで、前記物体（２２）を定期的に纏めて輸送する工程を更に有することを特徴とする請求項１乃至１５のいずれか１項に記載の方法。
【請求項１７】
前記障害（１６）挟む前記第１（１８）及び第２（２０）の道路部分を結ぶカーフェリー（２４）を示すために、必要に応じて前記デジタルマップを変更する工程を更に有することを特徴とする請求項１乃至１６のいずれか１項に記載の方法。
【請求項１８】
前記デジタルマップを更新する工程は、パーソナルナビゲーション機器（１０）の表示画面を変更する工程を含むことを特徴とする請求項１乃至１７のいずれか１項に記載の方法。
【請求項１９】
纏められた物体（２２）の障害横断スケジュール、横断時間及び／または場所（２６）を過去の軌跡データ（２８）を用いて判断する方法であって、
障害（１６）によって互いに分断された第１（１８）及び第２の（２０）の道路部分を有するデジタルマップを提供する工程であって、第１及び第２の道路部分間の前記分断距離は、距離（Ｌ）を有する障害の弧長を含む工程と、
統計的に適切な時間、前記障害（１６）を横断する複数の物体（２２）から、軌跡（２８）を記録する工程であって、各軌跡（２８）は連続したジオポジション （ｓ）及び タイムスタンプ（ｔ）記録を含む工程と、
類似した地理的及び行き先の特徴を有する記録された軌跡（２８）を束に纏める工程と、
前記束（２８’）の軌跡密度を、位置（ｓ）及び時間の関数として計測する工程と、
前記束（２８’）の前記軌跡密度における測定された変化に基づいて、纏められた物体（２２）の障害横断情報を判断する工程であって、前記障害横断情報が、集団が横断する場所（２６）、集団が横断する時刻表、集団の横断頻度、横断時間及び平均横断速度（ｖ）の少なくとも１つを含む工程と、
前記束の弧長上にある位置（ｓ）における密度が、１日の間に繰り返し大きく変化する場合に、前記束（２８’）を集団的横断であると特定する工程と、
時間（ｔ）の間、前記束（２８’）の弧長上の位置（ｓ）における、前記束（２８’）の前記軌跡密度における周期的な変化の周波数を判断する工程と、
スペクトルエネルギー図における前記周波数の変化を図表を用いて表す工程と、
前記スペクトルエネルギー図は、周波数毎の振幅を識別し、前記振幅スペクトルから、集団的横断周波数を直接判断する工程と、
前記障害横断経路の終点（２６）を、周波数分布の形状に基づいて識別する工程であって、前記束（２８’）の前記終点（２６）を識別する工程は、
ｖ０＝振幅スペクトルにおける最も大きいピークの周波数
ｖ１＝振幅スペクトルにおける次に大きいピークの周波数
Ａ（ｖ）＝周波数ｖの振幅スペクトルにおける振幅の絶対値
である場合に、式
Ｃ＝Ａ（ｖ１）／Ａ（ｖ０）
により表される２つの最も大きい周波数ピーク間の比に等しい閾値基準（Ｃ）を確立する工程であって、
前記周期的な周波数を判断する工程では、労働日と、非労働日について別々に周波数の決定を行い、
運行の異なる日について時刻表を決定する工程と、
前記判断された障害横断情報を属性に変換し、更に、前記デジタルマップに属性として補足する工程と
を有することを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、道路または経路情報を表示するタイプのデジタルマップに関し、更に詳しくは、フェリーで運搬される自動車等の纏められた対象物のための障害横断スケジュール、横断時間及び／または場所を決定するための方法に関する。
【背景技術】
【０００２】
パーソナルナビゲーション機器は、ＧＰＳや他のデータストリームから得られる正確な位置データが組み合わせられたデジタルマップを用いる。デジタルマップには、パーソナルコンピュータ、携帯機器、その他のシステム等からアクセスすることができる。これらの機器は、自動車のドライバーのためのナビゲーション支援など、様々な用途のために開発されている。これらナビゲーションシステムの有効性は、本質的に、メモリに記憶された、または、無線信号、有線接続、電話線といった、適したデータベースへの接続を介してアクセスされるデジタルマップの正確さに依存する。
【０００３】
図１に示すナビゲーションシステム１０は、道路１４の道路網として記憶されたデジタルマップの一部を表示する表示部１２を含む。ＧＰＳ対応のナビゲーション機器１０にアクセスしている旅行者の位置は、通常、特定の道路１４の近く、または道路１４またはその一部に関連付けて、デジタルマップ上で特定することができる。いくつかのＧＰＳ対応のナビゲーション機器１０は、TomTom NV (www.tomtom.com) により製造されたいくつかのモデルと同様に、一定（時には不定）の間隔で受動的にジオポジション（geo-position）の測定点を生成するプローブとして構成してもよい。これらの記録は軌跡データとも呼ばれ、例えば、２秒毎に記憶される一連のジオコード化された位置を構成する。当然のことながら、例えば、ハンドヘルドデバイスや携帯電話等を含む他の適したデバイスを用いて軌跡データを生成しても良い。従って、軌跡データは車両（またはプローブを持つ人物）の動きに関する、タイムスタンプされた地理上の位置（ｘｙｚ座標）及び、場合によってはメタデータ（車両の速度、受信機のタイプ、車両のタイプ等）をも含む、一連の情報として表される。
【０００４】
デジタルマップを漸次生成、及び／または更新するために、プローブの測定値を集めることが知られている。このようにして生成された軌跡データは、無線（例えば、携帯電話）送信、インターネットアップロード、または他の都合の良い方法により、オンザフライまたは順次に、集積サービスまたはその他のマップデータ分析サービスに送信することができる。インターネットアップロードは、ナビゲーションデバイスのユーザがサービスとして享受できるデジタルマップの更新に伴って行われるように同期しても良い。集められた軌跡データから道路形状を推測することができるとともに、他の特徴及び属性を、適切な分析方法により導き出すことができる。
【０００５】
デジタルマップの特定部分を通過する複数のプローブから、連続した期間に集められた典型的な軌跡データは、それぞれがジオコード化され、タイムスタンプを押された、膨大な量の離散的なデータポイントを含んでいる。時間をかけて集められたプローブの軌跡は、デジタルマップの共通領域と一致するもの同士でグループ分けしたり纏めたりした後、マップデータベース編集者が判断できるように重ねて表示することができる。編集者は、様々な数学的且つ統計的なテクニックを用いて、道路形状を決定または推測したり、スピードプロファイル、加速プロファイル、行き先、標高を算出したり、２つの道路網を比較するために、道路網の変化や、その他多くの事項を検出したりする。
【０００６】
デジタルマップのプロバイダは、地図を向上し、更新するために、常に努力している。例えば、不正確なデータは、ナビゲーションの要求に対して最適なルートを計算したり、他の信頼できる情報を旅行者に供給するのには適さない。デジタルマップに含まれる不正確または不完全な情報は、貧弱または誤ったナビゲーション指示となり、望ましくないナビゲーションの判断となってしまう。
【０００７】
ナビゲーションの判断では、通行の障害となる景観の自然の特徴を考慮に入れなければならない。例えば、河川は、車両による通行だけではなく、歩行者及び自転車の通行への制約となる。典型的には、河川は、フェリー、橋、またはトンネルを使うことによってのみ、渡ることができる。橋、フェリー、またはトンネルの存在の有無は、デジタルマップに記録すべき重要な詳細を構成する。同様に、これまでに障害を超えた車両の平均速度も、デジタルマップにとって重要な詳細である。
【０００８】
水の障害だけではなく、踏切や他の多くの障害のタイプを含むいくつかの障害の特徴として、車両または移動物体を集めておき、周期的にそれらを障害の反対側へ纏めて移動させることが普通になされている。水の障害を横断する自動車では、フェリーが、十分に予測可能なタイムスケジュールで自動車の一群を水の障害の反対側に運搬する。障害を横断する他のシナリオも、車両または他の物体が定期的に繰り返して纏めて障害を横断するように動かされることから、当業者は気がつくであろう。
【０００９】
デジタルマップがフェリー航路をそもそも認識していない場合に、存在する水路図またはデジタル道路マップに軌跡を単純に当てはめることで、例えばフェリー航路などの障害を横断する場所を検出するのは有効ではない。同様に、デジタルマップ（例えば水路図）が十分に正確でない場合も、有効ではない。距離測定値に基づいて多数の軌跡を纏める、計算量の多い方法を用いて、一群の移動物体及び軌跡を検出するための技術が提案されている。例えば、そのような方法の一つが、H. Jeungらにより、Proceedings of the VLDB Endowment, Volume I, Issue 1 （２００８年８月） Session: Spatial and Motion data, 1068-1080頁 (ISSN: 2150-8097)の"Discovery of Convoys in Trajectory Databases"において提案されている。しかしながら、このような方法は、しばらくの間一緒に動く一群の物体である纏まりを見つけるのには非効率的であることが分かっている。更に、従来例における技術では、これらの良く定義され、おそらくは最も複雑ではないタイプの纏まりを検出し、時刻表及び横断頻度を推定するために、フェリーなどの障害横断の特定のタイプの繰り返される日々の特徴や、その他の管理された横断場所の特徴を利用しない。
【００１０】
従って、この技術では、フェリーなどの特定のタイプの障害横断を識別するために、過去の軌跡データを集める必要があり、そうすることで纏められた物体（例えば車両）が定期的且つ予測通りに障害を越えて護送される。
【先行技術文献】
【特許文献】
【００１１】
【非特許文献１】"Discovery of Convoys in Trajectory Databases", H. Jeunget. al., Proceedings of the VLDB Endowment, Volume I, Issue 1 （２００８年８月） Session: Spatial and Motion data, 1068-1080頁 (ISSN: 2150-8097)
【発明の概要】
【００１２】
本発明は、過去の軌跡データを用いて、纏められた物体のための障害横断情報を判断する方法に関する。当該方法は、集められた軌跡データを、障害横断スケジュール、横断時間及び／または出発地点の観点で評価できるようにする。本発明の方法は、障害によって互いに分断された第１及び第２の道路部分を含むデジタルマップを含む。第１及び第２の道路部分間の分断距離は、障害の距離を含む。軌跡 は、第１及び第２の道路部分間の障害を横断する複数の物体から、時間をかけて記録される。各軌跡は時系列のジオポジション及びタイムスタンプデータを含む。類似する地理的及び行き先の特徴を有する記録された軌跡は、束に纏められる。束の密度は、位置及び時間の記録の関数として計測される。そして本発明によれば、障害横断情報は、纏められた物体について、計測された束の軌跡密度の変化に基づいて決定することができる。障害横断情報は、出発地点、横断時刻表、横断頻度、横断時間及び横断速度の少なくとも１つを含む。
【００１３】
本発明の原理は、デジタルマップに現在存在しない、例えば、フェリー航路、踏切、及び特定の昇降橋横断等の障害横断場所を効率的に特定するために用いることができる。更に、横断スケジュールまたは時刻表も、測定した軌跡密度の変化だけではなく、横断頻度情報及び横断時間の詳細から導き出すことができ、これらは全て、ナビゲーション及び経路検索に非常に有用である。
【００１４】
本発明のこれらまたは他の特徴及び利点は、以下に示す詳細な説明及び添付図面を関連付けて考えることで、より容易に理解できるであろう。
【図面の簡単な説明】
【００１５】
【図１】図１は、マップデータ情報を示す表示画面を含む本発明の一実施形態におけるポータブルナビゲーションデバイスの一例を示す図である。
【図２】図２は、障害の片側にある道路部分と反対側にある道路部分とをつなぐフェリーサービスを有する水の障害を示す簡略正面図である。
【図３】図３は、水の障害の両側にある道路部分をつなぐフェリー航路を示すデジタルマップの図である。
【図４】図４は、本発明の方法と共に用いることのできる集められたプローブデータからの軌跡情報を、図３に重ね合わせ合成した図である。
【図５】図５は、類似した地理的及び行き先の特徴を有する記録された軌跡を、後で行う分析のために纏める方法の一例を示す図である。
【図６Ａ】、
【図６Ｂ】、
【図６Ｃ】、
【図６Ｄ】、
【図６Ｅ】、
【図６Ｆ】、
【図６Ｇ】、
【図６Ｈ】図６Ａ〜Ｈは、纏められた物体の典型的な動きを、同様の場所の同じ時間における多数の物体として観察することのできる、障害横断場所における時系列（ｔ１〜ｔ８）を示す図である。
【図７】図７は、図６Ａ〜Ｈに示す選択されたタイムスケジュールｔ１〜ｔ１６の間のフェリー航路の場所対時間（ｓ，ｔ）の図の一例で、軌跡密度をグレースケール強度で表現した図である。
【図８】図８は、高速道路上のある場所について、時間に対する軌跡密度をプロットした時系列の一例を示す図である。
【図９】図９は、図６Ａ〜Ｈに示すようなフェリー航路上のある場所についての、図８に示すような時間に対する密度を示す図である。
【図１０Ａ】、
【図１０Ｂ】、
【図１０Ｃ】図１０Ａ〜図１０Ｃは、高速道路上のいくつかの場所（図１０Ａ）、横断終了点、すなわち、出発点（図１０Ｂ）、及び横断中（図１０Ｃ）における、頻度に対する振幅スペクトルを表す頻度分析図である。
【図１１】図１１は、２つの最も高い頻度のピーク間の割合と等しい、閾値の基準Ｃを確立することによって、障害横断のために、終点、即ち出発点を識別するための、束の弧長を示すグラフである。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明を説明するが、複数の図面において、同じ参照番号は同様または対応する構成を示す。本発明は、ナビゲーションシステム、及び、インターネットに接続されたコンピュータ、パーソナルデジタルアシスタント（ＰＤＡ）、携帯電話、ポータブルナビゲーション機器、ダッシュボード内車載ナビゲーションシステム等を介して閲覧可能なアプリケーションを含む、その他のマップアプリケーションにより用いられるデジタルマップに関する。
【００１７】
図２は、河川、湖、または海１６などの形態を有する水の障害を簡単に表した図である。この水の障害１６は、交通障害の１つのタイプの単なる例である。水以外の障害も広義の意味での障害に含まれると考えられ、谷、踏切、建設／修理事業、及び、道路または他の進路において自動車またはその他纏められた物体の自由な流れを周期的に妨げるまたは制限するその他の特徴を有する。第１及び第２の道路部分１８、２０は、デジタルマップに含まれる全ての道路網１４の部分を含むが、特に、障害１６のすぐ横に位置している。典型的には、道路部分１８、２０は車両交通の流れをサポートできるタイプのものであるが、本発明の原則は、自転車及び歩行者の通路、及び、どのような物体も運ぶことのできるその他の進路にも同等に適用される。自動車２２が、障害１６を渡って第２の道路部分２０につなぐフェリー２４に乗るところが示されている。フェリー２４は、自動車２２が障害１６をグループまたは纏まって越えるための輸送の１つの方法である。しかしながら、フェリー２４は障害を越えなくてはならない状況において用いられるほんの一例である。いくつかの状況では、自動車２２は障害を自力で越えなくてはならない。例えば、はね橋の場合、はね橋が上がっているときに、車両２２は道路部分１８、２０のいずれかに集まり、はね橋が下がったときに、自力で障害１６を（少なくとも最初は）まとまって越えるであろう。
【００１８】
図３は、第１及び第２の道路部分１８、２０が、ここでは例えば河川等の障害１６によって互いに分断されている場合の、デジタルマップの一例を示す図である。破線２４は、この例ではフェリー航路を表している。第１及び第２の道路部分１８、２０の間の分断距離は、障害の弧長（Ｌ）である。障害横断経路の終点２６は、この場合、それぞれ、第１及び第２の道路部分１８、２０を結ぶフェリーの発着場所を表している。従って、車両は、終点２６においてフェリー２４に乗船し、下船する。障害１６を横断する複数の車両２２による軌跡２８は、時間をかけて少しずつ、例えば、上述したプローブ記録技術を利用して集めることができる。簡単な例として、図４は、図３のデジタルマップ画像上に重畳した軌跡データ２８のサンプリングを示す。このような軌跡２８は、第１の道路部分１８から第２の道路部分２０へ、または反対に、第２の道路部分２０から第１の道路部分１８へ渡る車両を表す。
【００１９】
類似した地理的及び行き先の特徴を有する軌跡２８を纏めることは、本発明の目的において都合が良い。第１の道路部分１８から第２の道路部分２０へ（即ち、南の方へ）障害１６を越える軌跡２８を纏めることができる。同様に、時間をかけて集められた、障害１６を北に向かって（即ち、第２の道路部分２０から第１の道路部分１８へ）渡る全ての軌跡２８もまた、纏めることができる。図５はどのようにして軌跡２８を纏めるかを示す。図５の左側は、例えば、東西方向に動いたいくつかの軌跡２８と、南北方向に動いたいくつかの軌跡２８とを示している。纏めるために、同じ方向に動いた全ての軌跡が集められ、その結果、図５の右側に示す束２８’となっている。軌跡２８を纏めるために、別の様々な方法を用いることができる。即ち、軌跡２８はいくつかの異なる方法でかためることが可能である。一例として、代表的な１つの軌跡２８を、束２８’として選択しても良い。別の方法では、既存のデジタルマップに軌跡２８を一致させることにより選択された既存の幾何学を束として用いても良い。更に別の方法では、束２８’を導き出すために適した平均化アルゴリズムを用いても良い。選択した方法に関わらず、束２８’は、横断情報の為に後で分析される特徴を表している。より具体的には、障害の横断経路に対応する束の一部または長さを適切に分類することができる。一度分類されると、束２８’に含まれる（または表される）各々の軌跡２８は障害横断情報として、属性の形式で分類される。
【００２０】
上述したように、各軌跡は道路１４上にある物体２２（例えば車両）の動きを示す、一連のジオポジション及びタイムスタンプの記録を構成する。軌跡２８は、各車両２２のこれらの位置及び時間の記録の履歴を表している。そして、束２８’は、時間をかけて集められた、類似した地理的及び行き先の特徴を有する軌跡２８の集まりを示す。図６Ａは、水の障害１６が、大きな水の特徴の両端にある第１と第２の道路部分１８、２０を分断しているデジタルマップからの部分例を示している。軌跡の束２８’をあるタイムスライス、例えば、時間ｔｌの間、観察すると、各軌跡２８により表されるジオポジションの記録の集まりは、各道路部分１８、２０の出発点または終点２６付近に集まった、データポイントの集合または雲として現れている。この描写は、水の障害１６の両岸にあるフェリーに自動車が乗せられているところを象徴している。時間ｔ２において、図６Ｂに示すように、各フェリーは対岸目指して出発する。集められたデータポイントは、車両２２（不図示）が各フェリーにより輸送されている時の、車両２２の各位置の記録を示している。これらの図では、（束２８’に含まれる）障害横断経路の距離または弧長をＬとした場合、軌跡の束２８’上のどの場所もｓで表されている。
【００２１】
図６Ｃは、時間ｔ２（図６Ｂ）の後のタイムスライスｔ３を表し、障害１６の反対側に向かって更に進んでいる軌跡の束２８’に含まれる各データポイントを表している。図６Ｄは、時間ｔ４において、２つのフェリーがすれ違い、それぞれのデータポイントが近くに現れている様子を示している。図６Ｅ及び図６Ｆは、タイムスライスｔ５及びｔ６をそれぞれ示し、纏まった物体２２の更なる動きを示している。図６Ｇにおいて、フェリーは対岸に到着し、車両２２は下船し始める。時間ｔ８において、図６Ｈに示すように、車両は各フェリーの埠頭から離れ、様々な道路部分上を移動して離れ始める。従って、上述した例において記載した海上フェリー２４は、多数の車両２２を同様の場所で同じ時間に集めるとともに、別の時には、フェリー航路上に車両２２が１台も無いか、ほぼ存在しないという、非常に典型的な動きをするものとして表される。更に、フェリー航路、及び、他の多くの種々の障害横断システムは、しばしば、複数日に亘って同じ動作を繰り返すため、軌跡２８を多くの日数に亘って集めた場合に、この動きはより顕著になる。一方、従来の道路においては、繰り返される交通渋滞を考慮したとしても、動いている車両２２は時間及び場所においてより分散する。
【００２２】
多くのタイプの障害横断経路での繰り返しの動きは、束２８’の軌跡密度を位置及び時間の関数として計測することで表すことができる。ここで、密度とは、ある特定の場所（ｓ）及び時間（ｔ）において束２８’に含まれる各軌跡２８のデータポイントの数を示す。または、密度が、ある特定の場所（ｓ）及び時間（ｔ）におけるそれぞれの軌跡２８の数を指しても良い。図７は、図６Ａ〜Ｈに示す例に対応する、場所対時間（ｓ，ｔ）図の一例を示す。軌道の密度は、ここではグレースケールによる強度により表されている。言い換えると、ある特定の場所及び時間を通り過ぎるデータポイントまたは軌跡の数が５０（この例では、任意にこの数を選択した）よりも多い時、最大強度、即ち白色が示されている。反対に、障害１６の弧長上で、特定の時間ｔにおいて特定の場所ｓに含まれるデータポイントまたは軌跡データが無い場合、黒色強度で表される。このように、図６Ａ〜Ｈに示されているタイムスライスの１つにおいて、高強度の軌跡点が、表示された構成データポイントのクラスタまたはグループに対応するように現れる。全ての時間（ｔ）においてほぼ滑らかなグレーの値で表されているように、車２２は第１及び第２の道路部分１８、２０からほぼコンスタントに発着している。しかし、フェリー航路は明らかに識別可能で、ある時点では車２２は無く、別の時点では全ての車を識別することができる。これは、あるタイムスライスの間の白黒強度図間の顕著な違いである。もし、このような強度図を終日推定したとすると、最大強度が現れる日中により多くの交通が見られるであろう。乗降場所２６では車両はゆっくりと進むため、障害横断経路の終点２６付近では全ての時間において強度が大きくなる原因となっている。しかしながら、強度をデータポイントではなく軌跡の数から導き出した場合、障害横断経路の終点２６近辺で全ての時間においてはっきりと強度が高くなることは無いであろう。このような強度図から、集団の横断場所や、横断時刻表、即ち、出発時間のスケジュール、横断頻度、さらには横断時間までも、直接識別することができる。例えば、この例における横断時間は、ｔ１とｔ８の間の時間、またはｔ８とｔ１５の間の時間等として得ることができる。これは、一方の道路部分からフェリーが出発し、障害１６の反対側にある他方の道路部分に到着するまでの時間である。
【００２３】
図８及び図９に示すように、束の密度の変化は、重要な情報がデジタルマップ編集者にとって明らかになるように、時間をかけて描画される。図８は、道路網１４における主要または準主要道路における、一例の道路上を走行する車両から集められたデータを示す。束の密度は、交通量がピークとなる時間帯で徐々に高くなり、交通量が減る時間帯で低い密度に落ち着いて行く。しかしながら、図９は、束２８’上のある場所を示しており、この図から、車両が突然増えることが容易に分かる。このような車両の大幅な増加は、一日を通して定期的に起こる、急激な密度の変化の繰り返しを構成する。これらの０から０よりも十分に大きい値への急激な変化は、先の例で説明したフェリーのような集団横断を示す。長い時間、束２８’の軌跡密度の周期的な周波数の変化を分析することで、デジタルマップをより充実したものにするために有用な分析をすることができる。
【００２４】
図８及び図９を比較するとわかるように、動く物体（例えば、車両）の密度が一日の間にゆっくりと変化する道路は、主に低周波成分を有する。このことは、時系列の時間曲線における軌跡密度がゆっくりと変化することを示している。このことは、毎日繰り返される渋滞の状況についても言える。しかしながら、ある特定の場所において車両の密度が１日に何度も０から０よりも十分に大きい値に突然変化する、車両の急激な増加のある束２８’は、少なくとも１つの顕著な大きな周波数成分を有する。時系列におけるこのタイプの周波数分析結果は、図１０Ａ〜Ｃに示すような周波数図または振幅スペクトルにより視覚化することができる。振幅スペクトルにおける周波数のピーク（ほぼ０ＨｚでＤＣ成分から離れた）は、障害横断頻度に対応する。このように、図１０Ａは、目に見える周波数のピークをほとんどまたは全く持たない、開いた道路部分について集められた軌跡データを示している。しかしながら、図１０Ｂに示すように、降り場または終点２６においては、約０．１及び０．２Ｈｚで周波数のピークを識別することができる。図１０Ｃは、振幅スペクトルにおける大きな周波数のピークを観察することができる、障害横断経路上の点（ｓ）を表している。周波数分布の形状に基づいて、その束２８’の点における軌跡であるフェリー航路の特徴を判断することができる。
【００２５】
この判断をするために、様々な判断基準を考えることができる。一例として、図１１に図示するように、
ｖｏ＝振幅スペクトルにおける最も大きいピークの周波数
ｖ１＝振幅スペクトルにおける次に大きいピークの周波数
Ａ（ｖ）＝周波数ｖの振幅スペクトルにおける振幅の絶対値
である場合、使用する判断基準Ｃは、式
Ｃ＝Ａ（ｖ１）／Ａ（ｖ０）
によって表される、２つの最も大きい周波数ピーク間の比としても良い。
【００２６】
この方法論を用いると、滑らかに交通量が増加する道路は、０と何れにしても実質的に１よりも小さい値の間にある、条件Ｃの値を持たなければならない。しかしながら、纏められた物体２２を動かすためのフェリー航路及びその他の障害横断の方法論では、条件Ｃ値は、より大きく、１に近い値を持たなければならない。閾値は、障害横断経路に対応する束上の場所（ｓ）を決定するために、値Ｃに設定される。この零では、閾値０．３が選択され、これを図１１に水平破線として表す。図１１における、水平破線（即ち、閾値０．３）と、条件Ｃのグラフとの交点において、終点２６は、およそｓ＝０．４、０．９の（標準化された）弧長位置において識別される。閾値より上では障害横断経路が推測され、閾値より下では道路部分１８、２０が推測される。しかしながら、先に提案した通り、２つの最も高い振幅の周波数ピーク間の比のためにＣの値を決めるためのこの技術は、フェリー航路の性質を見つけるためのほんの１つのアプローチに過ぎない。さらにこの判定を進歩させるために、例えば、ｓの近傍の他の場所における周波数分布形状に応じて、横断場所を決定するなど、多くの展開が行われる。当業者であれば、他の技術についても理解できるであろう。
【００２７】
例えば、どのくらい頻繁にフェリーが運行しているかを示す、障害の横断に集団で出発する頻度は、図９の振幅スペクトルまたは図７の強度図から直接読み取ることができる。図９の振幅スペクトルを用いた時、周波数ｖ１に大きなピークが存在する場合、軌跡密度の周期的に顕著な増加がｔ１＝１／ｖ１（ｓ）毎にあることを意味し、これはフェリーがｔ１（ｓ）毎に運行していることを意味している。もちろん周波数分析は、各タイプの日について（例えば、冬期の月の月曜日、日曜日など）行っても良く、これにより、異なる日、一年の一部、運行期間中等について、時刻表を判断することができる。これにより、デジタルマップをこれらの属性で拡張し、ナビゲーション及び経路計画のための非常に価値のある情報源を提供することができる。
【００２８】
図７の場所対時間（ｓ，ｔ）の軌跡図から、フェリー航路の航行時間及び航行距離を判断することができる。上述した例の状況を用いると、フェリー航路は点（ｓ１，ｔ１）と（ｓ２，ｔ２）とを結ぶ高密度線として現れる。そして、航行時間は（ｔ２−ｔ１）であり、航行距離は（ｓ２−ｓ１）である。このようにして計算された航行時間は、ナビゲーション及び経路検索にも用いることができる。更に、もし航行時間及び航行距離が両方分かっているならば、平均横断速度もｖ＝（ｓ２−ｓ１）／（ｔ２−ｔ１）として直接求めることができる。場合によっては、物体２２の集合体の平均横断速度（ｖ）は役に立つことがある。
【００２９】
従って、本発明の方法を用いることにより、軌跡情報を場所対時間（ｓ，ｔ）図における束２８’に沿って視覚化して、ある場所におけるある時間の間（例えば、労働日対休日等）の軌跡密度または活動を評価することができる。上述した周波数分析は、可能な場所における車両の突発的な増加を検出することによってフェリー航路の場所を判断するために、多数の軌跡の時系列に対して応用してもよい。即ち、車両が無かった場所に、動いている車両が大量に突然現れることは、周波数分析技術により躊躇無く認めることができる。更に、ある特定の場所のための軌跡密度時系列に対するこれらの周波数分析技術を、フェリーの時刻表及びフェリーの運航頻度、そして他のタイプの集団的横断状況を判断するために応用してもよい。
【００３０】
適切な法的基準に法って上記発明を説明してきたが、この記述はその性質を制限するものではなく、例示である。開示された実施形態に対する様々な変更及び変形が可能であることは、当業者には明らかになるとともに、本発明の範囲に含まれる。
【図１】
2013534621.tif 000003
【図２】
2013534621.tif 000004
【図３】
2013534621.tif 000005
【図４】
2013534621.tif 000006
【図５】
2013534621.tif 000007
【図６Ａ】
2013534621.tif 000008
【図６Ｂ】
2013534621.tif 000009
【図６Ｃ】
2013534621.tif 000010
【図６Ｄ】
2013534621.tif 000011
【図６Ｅ】
2013534621.tif 000012
【図６Ｆ】
2013534621.tif 000013
【図６Ｇ】
2013534621.tif 000014
【図６Ｈ】
2013534621.tif 000015
【図７】
2013534621.tif 000016
【図８】
2013534621.tif 000017
【図９】
2013534621.tif 000018
【図１０Ａ】
2013534621.tif 000019
【図１０Ｂ】
2013534621.tif 000020
【図１０Ｃ】
2013534621.tif 000021
【図１１】
2013534621.tif 000022
【手続補正書】
【提出日】平成25年2月19日(2013.2.19)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
過去の軌跡データ（２８）を用いて、障害横断情報を判断する方法であって、
通路網における物体の自由な流れを周期的に妨げるまたは制限する少なくとも１つの障害横断（１６）を含む前記通路網（１４）上の、時間に対する複数の物体（２２）の動きを示す軌跡データであって、複数の時系列のタイムスタンプを押されたジオポジションを含む物体の前記軌跡データ（２８）を受信する工程と、
前記受信した軌跡データ（２８、２８’）を、前記通路網（１４）を示す、デジタルマップの一部（１８、２０）に関連付ける工程と、
前記軌跡データ（２８、２８’）から、少なくとも前記部分のいくつかにおける、特定の場所及び時間における物体（２２）の数を表す軌跡密度を、場所と時間の関数として決定する工程と、
前記軌跡密度が周期的に零から零よりも十分に大きい値に変化する場所を特定する工程と、
前記特定された場所を用いて、第１の部分（１８）と第２の部分（２９）との間に存在する障害横断（１６）の場所（２６）を決定し、前記決定した前記障害横断の場所により、前記デジタルマップを補足する工程と、
前記軌跡密度における変化から、前記障害横断（１６）の横断時刻表及び／または横断頻度を判断する工程と、
前記判断された横断時刻表及び／または横断頻度を前記デジタルマップにおける前記障害横断（１６）に関連づける工程と
を含むことを特徴とする方法。
【請求項２】
類似した地理的及び行き先の特徴を有する複数の物体（２２）から軌跡データを束に纏め、前記１以上の束（２８’）を前記デジタルマップの部分（１８、２０）に関連づける工程を更に有することを特徴とする請求項１に記載の方法。
【請求項３】
前記軌跡密度における変化から、前記障害横断（１６）の横断時間及び平均横断速度の少なくとも１つを決定する工程を含むことを特徴とする請求項１または２に記載の方法。
【請求項４】
障害横断の場所を判断するために前記特定された場所を用いる前記工程は、
ｖ０＝振幅スペクトルにおける最も大きいピークの周波数
ｖ１＝振幅スペクトルにおける次に大きいピークの周波数
Ａ（ｖ）＝周波数ｖの振幅スペクトルにおける振幅の絶対値
である場合に、式
Ｃ＝Ａ（ｖ１）／Ａ（ｖ０）
により表される軌跡密度変化の周波数分布の２つの最も大きい周波数ピーク間の比に等しい閾値基準（Ｃ）を確立する工程を含むことを特徴とする請求項１乃至３のいずれか１項に記載の方法。
【請求項５】
前記閾値基準（Ｃ）は、約０．３であることを特徴とする請求項４に記載の方法。
【請求項６】
前記軌跡密度における変化から前記障害横断（１６）のための横断頻度を判断する工程は、労働日と、非労働日について別々に周波数の決定を行う工程を含むことを特徴とする請求項１乃至５のいずれか１項に記載の方法。
【請求項７】
異なる日について横断時刻表を決定する工程を更に有することを特徴とする請求項１乃至６のいずれか１項に記載の方法。
【国際調査報告】
2013534621.tif 000023
2013534621.tif 000024
2013534621.tif 000025