説明

目的地を判定するためのベクトルを有する地図データベース、及びベクトル判定方法

方法、データベース、メモリ、コンピュータが読取可能な媒体、及びナビゲーション装置が開示される。少なくとも1つの実施形態において、本方法は、複数の投影点を作成するために、複数の既知の住所地点を、地図データベースの住所セグメント・ベクトルに投影するステップ(S1)と、対応する複数の補間点を作成するために、当該複数の住所地点の住所について位置を補間するステップ(S2)と、投影点と対応する補間点との距離が閾値距離を上回る場合に、当該住所セグメント・ベクトルを、複数の住所サブセグメント・ベクトルに分割するステップ(S3)とを含む。実施形態は、住所セグメント・ベクトルが分割された場合に、本方法における複数の住所サブセグメント・ベクトルを、対応する住所セグメント・ベクトルの代わりに、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納したデジタル地図アプリケーション・データベースを含むメモリ(230)と、当該メモリ(230)を含むナビゲーション装置(200)と、複数の住所セグメント・ベクトル及び複数の住所サブセグメント・ベクトルを含むデジタル地図アプリケーション・データベースと、当該デジタル地図アプリケーション・データベースを含むコンピュータ可読媒体と、を含む。

【発明の詳細な説明】
【技術分野】
【0001】
本発明の実施形態は、概して、特定の住所の位置を判定するための情報を有する地図データベース及び地図データベース形成方法に関するものであり、より具体的には、ユーザが所望する場所の位置又は所在地を正確に判定するために使用されるデータ構造を有する地図データベースに関するものである。
【背景技術】
【0002】
近年、消費者がデジタル地図上で場所を特定できるように、種々の装置及びシステムが消費者に提供されている。「場所(place)」という用語は、本発明の実施形態の説明全体を通して使用されている一般的な用語である。「場所」という用語は、ストリート住所(street addresses)、事業及びランドマーク等の、ストリート住所に位置する建物、及び、ショッピングモールやビジネスパーク等の、多くのストリート住所に位置する施設を含む。消費者により使用される種々の装置及びシステムは、運転者がストリートや道路(roads)をナビゲートできるようにする車両搭載型のナビゲーションシステムと、パーソナルデジタルアシスタント(「PDA」)、パーソナルナビゲーション装置(PND:personal navigation device)、及び携帯電話又はそれと同一機能を実行できる他の種類の移動装置等の、ハンドヘルド装置と、ユーザが所望の場所を示す地図を生成できるデスクトップ・アプリケーション及びインターネット・アプリケーションと、の形式を取る。上記の種類及び他の種類の装置及びシステムの全てに共通する態様は、地理的特徴(geographic features)、ベクトル及び属性の地図データベース、並びにユーザ入力に応じて当該地図データベースにアクセスし、操作し、ナビゲートするソフトウェアである。
【0003】
基本的に、上記の装置及びシステムの全てにおいて、ユーザは所望の場所を入力でき、その場所の位置が返される。一般に、ユーザは、レストラン等の事業の名称、Golden Gate Bridge等の目的地のランドマーク、又は住所等を入力する。その後、装置/システムは、要求された場所の位置を判定して返す。当該位置は、地図表示上に示されてもよく、既知の方法で当該位置への運転指示を計算及び表示するために使用されてもよく、あるいは他の方法で使用されてもよい。
【0004】
地図データベースは、ストリート上の家屋及び建物の位置に関する情報を提供する。地図データベースの開発者は、所与のストリート又はストリート・セグメント(住所セグメント)についての所与の住所範囲にわたる住所データを、地図データベースに収録する。当該住所範囲には、始点の家屋番号(house number)及び位置、終点の家屋番号及び位置、並びにオプションでいくつかの中間の家屋番号及び位置とともに、ストリート・セグメントの所与の辺に対応する建物番号(building number)又は家屋番号の集合が含まれる。
【0005】
ユーザによる所望の目的地の入力又は選択に応じて所望の場所の位置を特定するために、装置又はシステムのソフトウェアは、最初に当該所望の場所のアドレスを判定し、次に所望の選択又は入力されたアドレスを含むアドレス範囲を有するストリート・セグメントの位置を特定し、その後、当該アドレス範囲内で補間を実行して、当該所望の場所の位置を推定する。しかし、多くの場合、補間アルゴリズムには、所与のストリート・ブロックに沿った建物番号又は家屋番号の分布のばらつきに起因した問題がある。例えば、ブロックの始点又は中間に公園が存在する場合、家屋がブロックに沿って不均一に分布している場合、及び、住所範囲の端点に存在する建物がストリートの交差点に正確に位置していない場合のうち、少なくとも何れかがあり得る。
【0006】
理想的には、住所範囲の端点に存在する建物番号及び家屋番号の少なくとも何れかが、実際の建物の住所を表し、それにより中間の家屋番号を補間する際の誤差が減少する。しかし、これは必ずしも事実ではない。いくつかの地図データベースは、端点に存在する潜在的な建物番号又は家屋番号を使用した住所範囲を用いてモデル化されており、このことは、建物番号又は家屋番号を正確に補間するという問題を悪影響を及ぼす。例えば、地図データベースは、米国郵政公社により割り当てられた潜在的な建物番号又は家屋番号を使用して住所範囲をモデル化してもよい。更に、一例としては、ストリートが100個の住所番号から成るブロックに分けられるNew York Cityの商業地区では、ブロックの辺に沿った複数の建物番号又は家屋番号が、住所範囲全体を表すことはほとんどなく、一端又は他端において当該範囲を完結させるには不十分である場合が多い。
【0007】
上記の方法を使用する補間は、格納されたストリート・セグメント又は範囲の長さの50%以上の誤差を有する場合がある。これらの補間誤差は、例えば数十メートル又は数百メートルの誤差になることがあり、それにより、所望の目的地の補間位置へナビゲートしたユーザにとって、所望の場所が視界の範囲外になる可能性がある。
【0008】
図1に示すように、既知のデジタル地図データベースは、当該既知のデジタル地図データベースにおいて一般に住所セグメント・ベクトルとして表される、複数の住所セグメント又は住所セグメントについての複数の辺(複数の住所セグメント辺)を含む。一般に住所セグメント・ベクトルとして表されるそのような住所セグメント又は住所セグメント辺は、一般に、(場合によっては、例えば以下に説明する形状点SPを使用して図1に示すような形状を有する)線により接続された、始点及び終点を有する特徴として、地図データベースを含むメモリに格納される。一般に、そのような住所セグメント・ベクトルは、住所セグメントの一方の辺である住所セグメント辺を表す(この場合、住所セグメントは、名称により識別可能であり、且つ、既知の住所を含む移動経路(travel route)であって、道路、ストリート、幹線道路等を含むがそれらに限定されない任意の移動経路を意味すると理解される)。
【0009】
一例としては、図1の#2等の始点及び図1の#98等の終点は、一般に、住所セグメント又はストリートの辺の、始点及び終点の家屋番号又は建物番号を表す。住所範囲は、住所セグメント又は住所セグメント辺についての全ての住所を表すために使用され、通常は始点の家屋番号から終点の家屋番号(例えば、図1の#2〜#98)にわたり、場合によっては何らかのパリティ(parity)を有する(住所セグメントの一方の辺について偶数の番号のみを含み、且つ、住所セグメントの他方の辺について奇数の番号のみを含むか、あるいは、住所セグメントの両方の辺が表される場合は両方の番号を含む)。
【0010】
一般に、住所セグメント又は住所セグメント辺についての住所範囲は、住所セグメント・ベクトルと共にデジタル地図データベースに格納され、既知の方法でナビゲーションに使用され得るとともに、移動目的地(travel destinations)の位置を既知の方法で特定する及び他の種類の地図技術において使用され得る。一般に、住所セグメント・ベクトルは、属性情報と共にデジタル地図データベースに格納され、当該属性情報は、例えば、住所セグメントにおける速度制限、右左折制限又は一方通行に関する何らかの指示、国勢調査(census)コード、郵便番号、ストリート名等を含むが、それらに限定されない

【0011】
典型的には、中間の家屋番号の(住所範囲の始点と終点との間の)位置は、線形補間を使用して当該住所範囲内において既知の方法で計算される。例えば図2に示すように、典型的には、家屋#50は、線形補間によって図2の住所セグメントの形状に沿って、住所#2と住所#98との中間に存在すると判定される。そのような補間は、位置、移動目的地、場所等を判定するためにデジタル地図データベースを利用する、ジオコーディング(geocoding)及びナビゲーション・アプリケーションにおいて一般に使用される。
【0012】
補間誤差を生じる可能性のある線形補間法を使用することには、いくつかの問題がある。第1に、一部のデジタル地図データベースは、住所セグメントの始点及び終点についての実際の家屋番号を使用しない。代わりに、それらのデータベースは、デジタル地図データベースの構築後に建設される可能性のある建物の位置の特定に対応するために、又は郵便配達を容易にするために、潜在的な郵便住所(米国郵政公社によって当該住所セグメントに対して確保された住所)を使用する。例えば図1及び図2に示すように、セグメントにおける潜在的な郵便住所の範囲が#2〜#98である場合、道路の湾曲に従った線形補間によって、当該セグメントの中間点付近に住所#50が位置付けられる。しかし、例えば図3に示すように、端点の実際の住所が#2及び#60である場合、図3の点#50bの住所が正確に補間されるのではなく、#2〜#98である潜在的な郵便住所範囲を用いて線形補間が使用されて、図3に示すように、当該セグメントの湾曲に従って住所が点#50aに位置付けられる。従って、ナビゲーション及びジオコーディング・アプリケーションの少なくとも何れかにおいて誤差が生じることになる。
【0013】
更に、図4に示すように、実際には、一般に、住所はセグメント上に線形に分布していない。図4は、ブロックの中央に大きな公園又は空き地140を含む写真の一例を示す。大きな公園又は空き地140に起因して、住所番号が住所セグメントに沿って不均一に分布する場合がある。
【0014】
一部のデジタル地図データベースは、セグメントの始点及び終点として、潜在的な郵便番号ではなく、実際の住所番号を使用して構築されている。これにより中間点の補間が改善される場合がある一方で、住所がセグメントに沿って均一に分布していない場合、例えば、ブロック上に公園、駐車場又は共同住宅が存在する場合には、線形補間は依然として大きな誤差を示すことがある。また、物理的な住所が住所セグメントの一端に集中すると仮定する対数補間等の、非線形補間法が使用されてもよい。しかし、中間点の補間のために使用されたアルゴリズムに従って住所が容易に割り当てられない場合には、この方法でも失敗する。
【0015】
更に他のデジタル地図データベースは、実際の位置に従って住所セグメントに追加された一部又は全ての個別の(点)住所を用いて構築されている。この一例は、2006年2月8日に出願され、且つ、本明細書でその全ての内容を援用する、Michael Geilichによる特許文献1において説明されている。これは、探している住所地点を直接的に見つけるために、又は、誤差を最小化する最短補間を少なくとも可能にするために、十分な情報を提供する一方で、住所から位置を判定するために使用されるアルゴリズムを大幅に変更することになり、場合によっては装置において住所地点データを格納するための記憶容量のコストが高くなる。そのような異なる新規のロジックは、この改善された新規な地図を使用する装置に対して、かなりのソフトウェア・アップデートを必要とする。旧式のユニットにおいては、そのようなソフトウェアの変更を導入することが困難であるか、高コストであるか、又は、不可能である可能性がある。
【先行技術文献】
【特許文献】
【0016】
【特許文献1】米国特許出願第11/351,156号,“MAP DATABASE HAVING ADDRESS POINTS FOR DETERMINING DESTINATIONS(目的地を決定するための住所地点を有する地図データベース)”
【発明の概要】
【課題を解決するための手段】
【0017】
住所セグメント・ベクトル(住所セグメント)上に投影された実際の既知の住所地点を含み得る投影点を使用することによって、住所セグメント・ベクトルは、投影点と当該投影点の補間位置との間の距離が閾値距離を上回る場合に、修正(modified)又は分割(segmented)される。そのようにして、住所セグメントを、地図データベースにおいて住所サブセグメントに置き換えることによって、ジオコーディング及びナビゲーション等のアプリケーション自体において基本となる補間アルゴリズムに対する変更を全く必要とせずに、それらのアプリケーションについての線形補間アルゴリズムが改善される。改善された地図データベースが、住所セグメント・ベクトルを含み、且つ、必要に応じて住所サブセグメント・ベクトルを含むことに起因して、線形補間アルゴリズムが改善される。
【0018】
そのため、本発明の実施形態においては、例えばジオコーディングやナビゲーション等におけるデータの既存のアプリケーションにおける補間アルゴリズムを変更する必要なく、道路の住所セグメント又は住所セグメント辺に沿って、実際の家屋番号の分布が変化する状況に対応可能である。更に、以下の実施形態の説明から明らかになるように、住所サブセグメント・ベクトルが、必要に応じて(例えば投影点と補間点との間の閾値距離を上回ることに基づいて)対応する住所セグメント・ベクトルの代わりに地図データベースに格納されるため、多くの追加の記憶容量を必要としない。これは、記憶容量が制限されるポータブルナビゲーション装置(PND:portable navigation device)において特に有利である。従って、本発明の実施形態において、住所セグメント・ベクトルを住所サブセグメント・ベクトルに分割することにより、例えばジオコーディングやナビゲーションを含むがそれらに限定されないアプリケーションについて、補間処理が改善されるために、住所範囲データがさらに改善される。
【0019】
本発明の少なくとも1つの実施形態は、複数の投影点を作成するために、複数の既知の住所地点を、地図データベースの住所セグメント・ベクトルに投影するステップと、対応する複数の補間点を作成するために、当該複数の住所地点の住所について位置を補間するステップと、投影点と対応する補間点との距離が閾値距離を上回る場合に、当該住所セグメント・ベクトルを、複数の住所サブセグメント・ベクトルに分割するステップと、を含むことを特徴とする方法を対象としている。
【0020】
本発明の別の実施形態は、分割されていない複数の住所セグメント・ベクトルを格納しており、かつ、住所セグメント・ベクトルが分割されている場合に、上記で対処した少なくとも1つの実施形態の方法における当該複数の住所サブセグメント・ベクトルを、対応する複数の住所セグメント・ベクトルに代えて、又は対応する複数の住所セグメント・ベクトルとともに、格納していることを特徴とするメモリを対象としている。
【0021】
本発明の少なくとも1つの実施形態は、記憶媒体に格納可能な地図データベースを対象としている。当該地図データベースは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含み、当該複数の住所サブセグメント・ベクトルは、当該住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、当該住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも1つにより、当該地図データベースに格納されていることを特徴とする。
【0022】
本発明の少なくとも1つの実施形態は、上記で対処した少なくとも1つの実施形態の地図データベースを含むコンピュータが読取可能な媒体を対象としている。
【0023】
本発明の別の実施形態は、地図データベースを保存したメモリと、保存された地図データベースを用いて、入力又は選択された住所の位置を表示するディスプレイと、を備える装置を対象としており、当該地図データベースは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含み、当該複数の住所サブセグメント・ベクトルは、当該住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、当該住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも1つにより、当該地図データベースに格納されていることを特徴とする。少なくとも1つの他の実施形態において、当該装置は、ナビゲーション装置であり、当該ナビゲーション装置は、移動目的地の入力又は選択を促す入力装置と、入力又は選択された移動目的地への移動ルートを計算するプロセッサと、を更に備え、移動ルートの計算では、保存された地図データベースを利用し、ディスプレイは、計算された移動ルートを表示するために使用可能であること、を特徴とする。
【0024】
本発明の別の実施形態は、ユーザに所望の位置に対応する情報を提供するシステムを対象としている。当該システムは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含む地図データベースと、当該所望の位置に関するクエリに応じて、アプリケーション・プログラムを使用して、当該地図データベースに含まれる住所セグメント・ベクトル又は住所サブセグメント・ベクトルに対応する補間された位置を検索するプロセッサと、を備え、当該複数の住所サブセグメント・ベクトルは、当該住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、当該住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも1つにより、当該地図データベースに格納されていることを特徴とする。
【0025】
最後に、少なくとも1つの他の実施形態は、ユーザに所望の位置に対応する情報を提供する、地理情報システム(GIS)に基づくアプリケーション・プログラムを対象としている。当該プログラムは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含む地図データベースを含み、当該複数の住所サブセグメント・ベクトルは、当該住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、当該住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも1つにより、当該地図データベースに格納されていることを特徴とする。
【0026】
これらの実施形態の利点について、以下で詳細に説明するとともに、これらの実施形態のそれぞれの更なる詳細及び特徴について、添付の従属請求項、及び以下の詳細な説明における何れかの部分において明らかにする。
【図面の簡単な説明】
【0027】
以下では、添付の図面を参照し、図示される例を用いて、本発明の実施形態の教示の種々の態様、及びそれら教示を実現する構成について説明する。
【0028】
【図1】ストリート・セグメント辺のデジタル地図表現の一例を示す図である。
【図2】中間の家屋番号を見つけるために使用される線形補間の一例を示す図である。
【図3】実際の住所範囲及び潜在的な住所範囲に対する補間の差異を含む、補間の一例を示す図である。
【図4】ストリート・セグメントに沿って非線形に分布した住所に存在する実際の家屋を示す写真の一例を示す図である。
【図5】建物、一区画等を表す実際の住所地点を示す写真の一例を示す図である。
【図6】実際の住所地点、投影点及び補間点を示す写真の一例を示す図である。
【図7】本発明の方法の一実施形態を示す図である。
【図8】ストリート・セグメント上に投影された住所地点の一実施形態を示す図である。
【図9】投影点、補間点及びそれらの間の距離の一実施形態を示す図である。
【図10】既知の補間技術(10A)及びストリートの分割後における改善された補間(10B)の実施形態を示す図である。
【図11】パーソナルナビゲーション装置(PND)等のハンドヘルド装置において使用される一実施形態を示す図である。
【図12】全地球測位システム(GPS)等の車両搭載型のナビゲーションシステムにおいて使用される一実施形態を示す図である。
【図13】航空写真上に重ね合わされた住所地点の一実施形態を示す図である。
【図14】地図データベース930の実施形態が地図データベース・アプリケーション970と分離していることを示す図である。
【図15】本発明の一実施形態のナビゲーション装置を提供するように構成された電子構成要素を示す図である。
【図16】ナビゲーション装置が無線通信チャネルを介して情報を受信し得る一実施形態を示す図である。
【発明を実施するための形態】
【0029】
本発明の一実施形態は、ジオコーディング及びナビゲーションを含むがそれらに限定されないアプリケーションにおける補間を改善するために有用であると考えられる場合に、(一般にストリート・セグメントとして知られている)住所セグメント・ベクトルにアルゴリズムを適用して、当該住所セグメント・ベクトルを分割(セグメント化)することに関するものである。そのような住所セグメント・ベクトル又はストリート・セグメントは、始点及び終点を有する道路の幾何学的配置(road geometry)の一部分を含み、一般に、始点及び終点は、他のストリート又は地物(features)との交点によって定義される。一般に、ストリート・セグメントは2つの辺を有し、各辺は、通常、独自の始点及び終点を有し、且つ、独自の住所範囲を有する。当該範囲は、ストリート・セグメントの特定の辺において見つけられ得る可能性のある複数の住所を表す。尚、ストリート・セグメントの始点及び終点は、他の地物との交点によってのみ定義される必要はなく、住所範囲内の幾何学的配置の任意の複数のセクション(section)として更に定義されてもよい。
【0030】
更に、本発明の実施形態の態様は、ストリートの一方の辺を対象としたストリート・セグメントに限定されず、ストリート・セグメントの両方の辺が別々に考慮されないストリート・セグメントに対しても適用可能であってもよい。そのような例において、本発明の実施形態のアルゴリズムは、ストリート・セグメントの両方の辺に同時に適用されてもよい。他の変形例において、本発明の実施形態のアルゴリズムは、住所を割り当てられていないストリート・セグメント又はストリート・セグメント辺に適用されてもよい。その場合、最初に、道路名及び住所範囲の少なくとも何れかをストリート・セグメントに割り当てるための技術が使用されてもよく、その後、当該ストリート・セグメントは、例えば本発明の実施形態のアルゴリズムに基づく分割のために検証されてもよい。
【0031】
デジタル地図データベースは、住所セグメント・ベクトル又はストリート・セグメントを含むことが知られており、住所セグメント・ベクトル又はストリート・セグメントは、始点及び終点、ストリート名及び他の種類の属性、並びに、当該セグメント上に割り当てられた住所を表す住所範囲を有する。そのようなデジタル地図データベース(地図データベース)は、(例えば、ナビゲーション装置の一体型入力表示装置を介して選択又は入力された)所望の移動目的地等の場所の位置を特定する場合に、例えばジオコーディング、GIS及びナビゲーション技術において使用される。一般に、デジタル地図データベース(例えば、デジタル地図データベースのベンダにより通常は保守され、且つ、本明細書中でソース・デジタル地図データベースと呼ばれるデジタル地図データベース)は、中央サーバに格納可能であり(且つ、例えばジオコーディング・アプリケーションの場合は直接アクセス可能であり)、その簡易バージョン(本明細書中でデジタル地図アプリケーション・データベースとして参照される)は、ジオコーディング装置、車両搭載型のナビゲーション装置、パーソナルナビゲーション装置、及び、携帯電話、PDA等を含むがそれらに限定されないナビゲーション機能を有する他の何らかの装置、のうちの少なくとも1つを含むがそれらに限定されない装置のメモリにダウンロード若しくは転送可能であり、並びに/又は、メモリ若しくは何らかの種類のデジタル媒体に格納可能である。そのようなソース・デジタル地図データベースは、住所セグメント・ベクトル(及び、以下に説明する住所サブセグメント・ベクトルの少なくとも何れか)を含み得るとともに、当該住所セグメント・ベクトル(及び住所サブセグメント・ベクトルの少なくとも何れか)は、格納された当該住所セグメント・ベクトル(及び住所サブセグメント・ベクトルの少なくとも何れか)に割り当てられた多くの種類の属性を含む。一般に、デジタル地図アプリケーション・データベースは、そのようなソース・デジタル地図データベースから形成され、格納された住所セグメント・ベクトル(及び住所サブセグメント・ベクトルの少なくとも何れか)に割り当てられた、相対的に少ない種類の属性を有する住所セグメント・ベクトル(及び住所サブセグメント・ベクトルの少なくとも何れか)を含む。ソース・デジタル地図データベースからそのようなデジタル地図アプリケーション・データベースを形成すること、及び、当該デジタル地図アプリケーション・データベースを形成するためにソース・デジタル地図データベースの一部分をコピーすること、の少なくとも何れかを目的とした技術については、当業者には既知であり、簡潔にするために本明細書中では説明しない。
【0032】
一般に、そのようなデジタル地図アプリケーション・データベースは、パーソナルナビゲーション装置、又は、ジオコーディング及びナビゲーション機能の少なくとも何れかと、マッピング機能との少なくとも何れかを有する他の任意の装置にもダウンロード可能である。当該装置は、例えばインターネット又はモバイルネットワーク接続を介してサーバから新たなデジタル地図アプリケーション・データベースに定期的に(例えば、新たな情報が受信される数ヶ月毎に)アクセスしてダウンロード又はコピーすることによってダウンロード可能であり、あるいは、車両搭載型のナビゲーション装置の場合、そのようなデジタル地図アプリケーション・データベースは、例えばCD−ROMに格納された新たな更新済のデジタル地図アプリケーション・データベースによってダウンロード可能である。ここで、CD−ROMは、車両の車両搭載型のナビゲーション装置のメモリに格納されたデジタル地図アプリケーション・データベースを更新するために、当該車両搭載型のナビゲーション装置に入力可能である。そのような更新技術は、上述の技術に限定されず、デジタル地図アプリケーション・データベースを更新する任意の技術も含み得る。そのような更新技術については当業者には既知であり、簡潔にするために本明細書中では説明しない。
【0033】
そのような既知のソース・デジタル地図データベースの全てにおいて、各ストリート・セグメント(デジタル地図データベースの住所セグメント・ベクトル)について、1つ以上の既知の住所地点の集合が存在する(尚、ソース・デジタル地図データベースは、既知の住所地点を含む一方で、デジタル地図アプリケーション・データベースは、一般にそれらを含まないが、記憶容量の制約により可能ならば既知の住所地点を含み得る)。例えば図5に示すように、そのような既知の住所地点#168−172、#180及び#184は、既知の地理的位置と、ストリート・セグメント又は住所セグメント・ベクトルに沿う当該位置に対応する1つ(#180及び#184)又は複数(#168−172)の住所番号又は住所とを有する。住所地点は、物理的構造、一区画(parcel)又は他の住所位置の、位置及び番号を表してもよく、建物、一区画等の実際の位置であることが既知である固定点である。これらは、例えば病院及び警察署等の、対象とする緊急地点の正確な位置、地図データベース内に自身の事業の正確な位置を配置するために航空写真の費用を支払った事業(例えば、チェーン展開しているレストラン等)の場所、税地図や境界線地図等から取得された正確な住所位置等を含み得る。いずれの場合も、そのような住所地点は、物理的構造や一区画等の、実際の位置及び番号を表す。そのような既知の住所地点は、正確な位置を提供する点で非常に価値があるが、(特にデジタル地図アプリケーション・データベースに)あまりに多くの住所地点が含まれていると、パーソナルナビゲーション装置、及び、携帯電話やPDA等のナビゲーション機能を有する他の何らかの小型/ポータブル型の装置の少なくとも何れか等の、特に、記憶容量が少ない装置の場合に、メモリの記憶容量の問題が生じる。その上、大部分の既存のアプリケーションは、それら既知の住所地点を使用するための特別なロジックを有さない。
【0034】
図6は、仮想システム上のアプリケーションにおいて使用される一実施形態を示す。当該アプリケーションは、PDA、携帯電話又はナビゲーション装置等のハンドヘルド装置、あるいはコンピュータ又はラップトップにおいて使用されてもよく、あるいはインターネットを介して使用されてもよい。探索の一例としては、仮想地図アプリケーションを使用するユーザによって、156 Dartmouth College Highway, Lebanon New Hampshireに対して実行される。現時点で、当該アプリケーションは、補間点であるドットGを含むバブル内に地図上の住所の位置を表示している。しかし、実際の住所は地点Aに位置する。一方、本発明の実施形態は、住所地点A、投影点E、及び、投影点Eと補間点Gとの間の距離を使用して、それらの間の距離(実際には263m)が閾値距離を上回るかを判定することができる。閾値距離を上回る場合、本発明の実施形態は、住所セグメント・ベクトルの分割処理を使用して、明らかに図6のバブルGに存在しない建物又は当該建物が位置する敷地についての、更に正確な位置を見つけることが可能である。この住所地点Aはソース地図データベースに格納される。その後、アプリケーション地図の新しいバージョンにおいて分割処理が実行され、当該バージョンは、種々の装置のアプリケーションにおいて使用されるように、それら装置に配信されてもよい。このように、本発明の実施形態は、以下に説明するように、より正確な位置決め情報(positioning information)を提供できる。
【0035】
本発明の少なくとも1つの実施形態は、ソース・デジタル地図データベースのこれら既知の住所地点(あるいは、そのような既知の住所地点がデジタル地図アプリケーション・データベース内に存在する場合は、当該デジタル地図アプリケーション・データベースの既知の住所地点)を有効に利用する方法を対象とする。本発明がソース・デジタル地図データベースのこれら既知の住所地点を利用する実施形態において、その結果は、デジタル地図アプリケーション・データベースに変換され、且つ、本発明の実施形態を有効に使用可能なアプリケーションを実行する装置に配信されてもよい。図7に示すように、本発明の一実施形態において、方法は、複数の投影点を作成するために、複数の既知の住所地点を、地図データベースの住所セグメント・ベクトルに投影するステップ(S1)と、対応する複数の補間点を作成するために、当該複数の住所地点について位置を補間するステップ(S2)と、投影点と対応する補間点との間の距離が閾値距離を上回る場合に、当該住所セグメント・ベクトルを、複数の住所サブセグメント・ベクトルに分割するステップ(S3)とを含む。以下では、図8〜図10に関して、そのような一実施形態の一例を説明する。
【0036】
例えば図8に示すように、所与のストリート・セグメント又はストリート・セグメント辺について、それに対応する住所地点が判定される。例えば図8のElm Streetは、#2〜#98の範囲の住所を有する第1の辺160と、#1〜#99の範囲の住所を有する第2の辺162とを有する。デジタル地図データベース内には、(範囲#2〜#98に含まれるため、Elm Streetのストリート・セグメント又は住所セグメント・ベクトルの辺160に対応する)既知の住所地点#16 Elm Streetと、#1〜#99の住所範囲に含まれるためElm Streetのストリート・セグメント辺162(Elm Streetの住所セグメント・ベクトル)に対応する、既知の住所地点#45 Elm Street及び#57 Elm Streetと、が格納されている。このように、住所地点は、ストリート名が同一であるストリート・セグメントに割り当てられ、当該地点の住所番号は、ストリート・セグメント又はストリート・セグメント辺(住所セグメント・ベクトル)に一般に割り当てられる範囲内に存在する。更に、ストリート・セグメント辺を割り当てるために、住所番号のパリティが一般に使用される。尚、特定の住所地点の住所番号のパリティは、特定の住所地点に対応するストリート・セグメント辺を判定するために基本となるセグメント辺についての、住所範囲のパリティを一致させるために使用可能である(偶数値の地点#16は、偶数値の住所を含むElm Streetの辺160上に存在し、奇数値の住所地点#45及び#57は、Elm Streetのストリート・セグメントの奇数値の住所を含むストリート・セグメント辺162上に配置される)。尚、本発明の実施形態の目的のため、住所セグメント・ベクトルには、ストリート・セグメント全体が含まれてもよく、ストリート・セグメントの一方の辺(例えば、図8の要素160又は162)が含まれていてもよい。この場合も、図8に示す住所地点#16 Elm Street、#45 Elm Street及び#57 Elm Streetは、既知の住所地点に対応し、当該既知の住所地点は、上述のように物理的構造、一区画、所在地等の、実際の位置及び番号であり、且つ、既知の実際の位置である。
【0037】
何れの既知の住所地点が、何れのストリート・セグメント及び何れのストリート・セグメント辺の少なくとも何れかと対応するかを判定する際には、注意が必要である。これは、ストリート・セグメント及び住所地点の少なくとも何れかが、現実に対して正確に位置決めされていない場合には、ストリートの一方の辺に存在するように見える住所地点が、実際には当該ストリートの他方の辺に位置する可能性があるためである。ストリート・セグメント辺が、対応する住所範囲を有しない場合、ストリート・セグメントの正しい辺に住所地点を割り当てるために、他の技術が使用されてもよい。例えば、地理的近接(geographic proximity)は使用されてもよい1つの技術である。
【0038】
既知の住所地点がストリート・セグメント又はストリート・セグメント辺(住所セグメント・ベクトル)に割り当てられると、ストリート・セグメント辺又はストリート・セグメント上に当該既知の住所地点の位置を投影するために、空間技術を含むがそれに限定されない技術が使用可能である。図8に示すように、地図データベースの住所セグメント・ベクトル上に既知の住所地点を投影する1つの技術は、ストリート・セグメント辺に垂線を下ろすことである。そのため、住所セグメント・ベクトル(例えば、#2〜#98である偶数値の範囲を含むElm Streetのストリート辺160についての住所セグメント・ベクトル)に投影点164を作成するために、#16 Elm Street等の既知の住所地点が使用されてもよい。同様に、例えば#1〜#99である奇数値の住所範囲を含むElm Streetの住所セグメント・ベクトルに、例えば既知の住所地点#45 Elm Street及び#57 Elm Streetをそれぞれ投影することにより、他の投影点166及び168を作成できる。従って、本発明の一実施形態において、例えば図8に示すように、住所地点は、相対的に最も近いストリート・セグメント辺に沿って、相対的に最も近い位置に投影される。そのような投影点の形成又は作成は、投影点のパリティとセグメント辺の範囲とが一致することの確認等の、割り当てに関するチェックを更に含んでもよい(例えば、奇数値の住所地点#45及び#57が投影された場合に、それらが例えば図8に示すように#1〜#99の範囲等の奇数範囲を含むストリート・セグメントの一方の辺又は住所セグメント・ベクトルに投影されることを保証するために、チェックが行われてもよい)。
【0039】
図9は、本発明の一実施形態の方法の次のステップの一例を示す。このステップにおいて、投影点に加えて、補間点が作成される。図9に示すように、投影点164、166及び168は残ったままである。これらの点に加えて、対応する補間点が、住所地点の住所に対して作成される。例えば、線形補間等の既知の補間技術を利用して、Elm Streetに沿う住所であって、#8 Elm Streetについての住所地点の住所の補間位置を表す補間点174が、住所#8 Elm Streetに対して作成されてもよい。同図から分かるように、当該補間点は、ストリート・セグメントの住所範囲内の数値的な位置に基づいて、ストリート・セグメントの湾曲に従った補間位置に存在する(既知の線形補間技術により予測されるように、住所#8は住所#2の近くに位置決めされる)。そのため、補間点174は、Elm Streetについての住所セグメント・ベクトルに沿って、当該住所セグメント・ベクトル内に#8 Elm Streetに対する住所地点の住所の位置を(既知の補間技術を使用して)補間することによって、既知の方法で形成される。同様に、補間点176は、Elm Streetの住所セグメント・ベクトルに沿って、#45 Elm Streetに対する住所地点の住所の位置を補間することによって、既知の住所#45 Elm Streetに対して形成又は作成されてもよく、補間点178は、Elm Streetの住所セグメント・ベクトルに沿って、#57 Elm Streetに対する住所地点の住所の位置を補間することによって、既知の住所#57 Elm Streetに対して形成又は作成されてもよい。
【0040】
例えば、投影点164、166及び168、並びに対応する補間点174、176及び178(例えば、投影点が事前に作成されたElm Streetの住所について形成又は作成された補間点)が作成されると、本発明の一実施形態の方法において、これらの点はストリート・セグメント又は住所セグメント・ベクトルをサブセグメント又は住所サブセグメント・ベクトルに分割するために使用可能である。これは、例えば、地図データベースにおけるサブセグメント又は住所サブセグメント・ベクトルに含まれる住所の線形補間が、ストリート・セグメント又はストリート・セグメント辺上の線形補間よりも全体として投影点に近くなる状況であって、住所の実際の位置を更に伝えるのに分割が有用である状況において、実行されてもよい。特に、本発明の一実施形態において、投影点と対応する補間点(投影点及び補間点のペア)の間の距離が閾値距離を上回る場合に、住所セグメント・ベクトルは、複数の住所サブセグメント・ベクトルに分割される。尚、本実施形態において、当業者には既知であるように、当該距離は、実際には、絶対値、二乗値又は最大値等の距離の関数であってもよく、あるいは、平均値、中央値、平均、二乗平均値又は二乗平均平方根等の、複数のそのような距離の関数であってもよい。
【0041】
本発明の一実施形態において、任意の所与のストリート・セグメント又はストリート・セグメント辺について、同一の住所に関連する投影点及び対応する補間点のペア(対応する投影点及び補間点、又は投影点及び補間点のペアとしても知られる)の間で、距離が計算されてもよい(例えば、補間点174及び投影点164のペアのように、投影点が事前に作成された例えばElm Streetの住所について、補間点が形成又は作成される)。少なくとも1つの実施形態において、対応する投影点と補間点との間の距離の中で、相対的に最大の距離が判定されてもよい。図9に示す例において、そのような距離は、ストリート・セグメントのそれぞれの辺について計算されてもよい。その場合、ストリート・セグメント辺160についての、投影点と補間点との間の相対的に最大の距離は、例えば図9の要素180により識別される距離であり、即ち、(これがストリート・セグメント辺160について計算された唯一の距離であるため)#8 Elm Streetに関する補間点174と投影点164との間の距離である。Elm Streetのストリート・セグメントのストリート・セグメント辺162についてのそのような距離は、距離182であり、これは、#45 Elm Streetに関する投影点166及び補間点176についての距離よりも相対的に長い。
【0042】
その後、対応する投影点と補間点との間のこれら相対的に最大の距離の各々について、閾値距離との比較が行われ、例えば、判定された相対的に最大の距離が閾値距離を上回る場合には、分割が行われる。住所セグメント・ベクトルを使用して住所サブセグメント・ベクトルが作成されると、当該住所サブセグメント・ベクトルは、当該住所セグメント・ベクトルと共に、(例えば、ベンダの)ソース・デジタル地図データベースに(対応する住所セグメント・ベクトルに割り当てられた属性の全てと共に)格納される。その後、当該ソース・デジタル地図データベースから、既知の方法でデジタル地図アプリケーション・データベースを作成可能である。しかし、本発明の少なくとも1つの実施形態に基づいて、そのようなデジタル地図アプリケーション・データベースは、この時点で、(各々が、デジタル地図アプリケーション・データベースの住所セグメント・ベクトルに一般に割り当てられれる、限られた数の属性を含む)新たに作成された住所サブセグメント・ベクトルを、住所セグメント・ベクトルの代わりに及び/又はそれと共に、含んでいてもよい。
【0043】
そのような閾値距離は、全ての比較のために使用される不変の距離である必要はない。例えば、そのような閾値は、市街地において相対的に小さくてもよい。多くの建物を含む市街地においては、例えば100〜200ヤードの相対的に短い距離でも位置が離れている場合、数百ヤードしか離れていないユーザの視界が、例えば他の建物又は構造によって妨げられることに起因して、ユーザの視界が損なわれ、その結果、ユーザが特定の所望の位置を見つけることは困難になる場合がある。更に、郊外においては、(例えば、0.25マイル等の)相対的により大きな閾値が使用されてもよい。その場合、所望の目的地の実際の位置から遠く離れた住所の位置にユーザが到着したとしても、当該ユーザの視界が他の建物の存在によって損なわれる可能性は低いため、当該ユーザは、例えば建物等の所望の移動目的地の実際の位置を、それでも容易に目で確認することができるであろう。
【0044】
従って、本発明の実施形態では、特定の閾値には限定されず、異なる複数の地域における異なる複数の閾値(例えば、市街地若しくは都市部における100〜200ヤード、又は郊外における0.25マイル)等の、異なる複数の閾値を使用可能である。尚、本発明の実施形態は、本明細書中に記載された(市街地及び郊外の閾値の例を含む)特定の閾値に限定されることはない。
【0045】
本発明の実施形態は、装置のデジタル地図アプリケーション・データベースにおいて、住所の位置の適切な分割を生じさせる何れの閾値を用いても動作するように設計されることによって、例えば、ジオコーディング技術及びナビゲーション技術の少なくとも何れかを使用するユーザが、ジオコーディング装置又はナビゲーション装置内で既存の補間アルゴリズムを利用して、ジオコーディング装置及びナビゲーション装置の少なくとも何れかによって示された目的地から、正確かつ所望の、実際の目的地に気づくか又はそれを見ることができるほど、建物又は他の移動目的地に十分に近い範囲内の位置を得られる。更に、サブセグメント・ベクトルを含む(例えば、ベンダの)ソース・デジタル地図データベースが、例えばジオコーディング・アプリケーション又はナビゲーション装置への格納用に、サブセグメント・ベクトルを含むデジタル地図アプリケーション・データベースを作成するために使用される場合、本発明の実施形態の態様は、ジオコーディング装置及びナビゲーション装置の少なくとも何れかの、ジオコーディング機能及びナビゲーション機能の少なくとも何れかをさらに向上させるように設計される。その後、本発明の一実施形態のサブセグメント・ベクトルを含む、そのような格納されたデジタル地図アプリケーション・データベースは、所望の位置にユーザを到着させるためのジオコーディング装置及びナビゲーション装置の少なくとも何れかの利用を更に向上させるために、上述の既存の補間技術と関連して使用されてもよい。
【0046】
尚、分割するタイミング、及び分割が望ましい又は望ましくないタイミングを決定する際に、上述の方法において使用される補間閾値を決定するために、種々の技術が使用され得る。本発明の一実施形態において、当該補間閾値又は閾値距離は、補間点と投影点との間の距離であって、許容範囲にある相対的に最大の距離であってもよく、これは位置の精度の推定値としても考慮される。例えば、この相対的に最大の、又は最大の許容値は、地形(例えば上述のように、市街地か又は郊外か)によって、又は他の理由によって変化してもよい。そのような確定された閾値に基づいて、対応する投影点と補間点との間の距離の中で相対的に最大の距離が判定され得るとともに、本発明の一実施形態の分割処理は、当該判定された相対的に最大の距離が閾値距離を上回る場合に実行されてもよい。
【0047】
本発明の別の実施形態において、当該閾値距離は、分割するタイミングを決定する際に、最大数の補間された住所のみ、又は相対的に最多の数の補間された住所のみが、投影住所地点とそれに対応する補間点との間に含まれるように、設定されてもよい。例えば、当該閾値が最大で2つの住所に設定され、且つ、補間された住所#34、#36及び#38が住所#32についての投影点及び補間点のペアの間に含まれる場合には、当該閾値を上回り、分割が行われる必要がある。この方法は、範囲内における全ての住所について、補間された住所を必要としてもよい。補間閾値を確立及び評価するための他の方法も、同様に実行可能である。
【0048】
本発明の別の実施形態において、閾値距離は、分割するタイミングを決定する際に、住所セグメントに沿う投影点及び対応する補間点の全てのペアの間で判定された平均判定距離が、閾値距離を上回る場合に、分割を実行するように設定されてもよい。
【0049】
別の実施形態において、補間閾値は、限られた数のサブセグメント又は住所サブセグメント・ベクトルのみを作成するように設定されてもよい。特定のアプリケーション(例えば、メモリが制限される小型装置におけるナビゲーション・アプリケーション等)は、住所セグメント及び住所サブセグメント・ベクトルのためのメモリ内の記憶容量が限られる場合がある。異なる複数の閾値が異なる複数のアプリケーションについて使用されてもよく、その結果、記憶装置が多くの住所サブセグメント・ベクトルを収容できるほど、位置の精度が向上する。限られたメモリの一例としては、ポータブル型であるが限られた量のメモリのみを含むパーソナルナビゲーション装置(PND)のメモリであってもよい。
【0050】
上述の本発明の実施形態において、投影処理、補間処理及び判定処理は、住所サブセグメント・ベクトルへの複数の分割処理について実行されてもよい。従って、上述の実施形態において、住所サブセグメント・ベクトルは、特定の条件が満たされるまで、複数の住所サブセグメント・ベクトルに更に分割されてもよい。例えば、住所サブセグメント・ベクトルの分割処理は、相対的に最大又は最大の距離が、閾値距離以下になるまで又は細分化(subdivisions)の最大数に達するまで、実行されてもよい。更に、別の実施形態において、住所サブセグメント・ベクトルの分割は、住所サブセグメント・ベクトルの投影点と対応する補間点との間の距離の平均値(平均距離)が閾値距離を下回るまで、実行されてもよい。従って、少なくとも1つの実施形態において、投影処理、補間処理及び判定処理は、平均距離、最大距離、及び各住所サブセグメント・ベクトル内の投影点と対応する補間点との間の距離の関数のうちの少なくとも1つが、閾値距離を下回るように又は細分化の最大数に達するまで、住所サブセグメント・ベクトルへの複数の分割処理について実行される。尚、そのような反復処理には、補間値の再計算が含まれていてもよい。また、複数のサブセグメントは、反復法を使用せずに直接的に計算されてもよい。
【0051】
この場合も、本発明の実施形態は、図9に示すようなストリート・セグメントの一方の辺に対応する住所セグメント・ベクトルの分割処理に限定されない。本発明の少なくとも1つの実施形態において、ストリート・セグメントの両方の辺160及び162が共に考慮されてもよく、その場合、相対的に最大の距離を有する投影点及び補間点の対応するペアは、当該複数の辺について見つけられてもよい。例えば図9の例に示すように、要素182は、Elm Streetのセグメント又は住所セグメント・ベクトルの両方の辺が共に考慮される場合に、対応する投影点と補間点との間の距離の中で、相対的に最大の距離に相当する。単一の相対的に最大の距離182が利用される場合、又はストリート・セグメントの各辺160及び162についての相対的に最大の距離が利用される場合(即ち、距離180及び182)の何れにおいても、ストリート・セグメントの一方の辺又は両方辺の分割処理に対して以下の技術が同様に適用可能である。本発明の実施形態の目的のため、ストリート・セグメント全体又はストリート・セグメントの個々の辺160及び162が住所セグメント・ベクトルとみなされてもよく、それらの何れの分割も、住所サブセグメント・ベクトルとみなされてもよい。
【0052】
従って、本発明の実施形態において、投影点と対応する補間点との間の距離が補間閾値距離を上回ることが分かった場合、住所セグメント・ベクトルは、上記の実施形態において説明したように分割されてもよい。少なくとも1つの実施形態において、当該分割処理は、投影点と対応する補間点との全てのペアの間の平均距離を低減する、住所セグメント・ベクトル又は住所サブセグメント・ベクトルに沿った点において、実行されてもよい。少なくとも1つの限定しない例において、その点は投影点であってもよい(しかし、本発明の実施形態は、セグメント点として投影点を使用することに限定されると考えられるべきではない)。従って、少なくとも1つの実施形態において、住所セグメント・ベクトル又は住所サブセグメント・ベクトルは、住所セグメント・ベクトル又は住所サブセグメント・ベクトルに沿う投影点のうちの1つにおいて、分割されてもよい。以下では、限定することのない一実施形態について説明する。
【0053】
一実施形態において、ストリート・セグメント辺160についての点164、又はストリート・セグメント辺162についての点168等の投影点は、住所セグメント・ベクトルの分割を行うための「分割点(split point)」になってもよい。従って、住所セグメント・ベクトルは、この点において分割(split)又はセグメント化(分割)(segmented)されてもよく、分割点の住所は、結果として得られた複数の住所サブセグメント・ベクトルのうちの1つについての住所範囲の端点に割り当てられてもよく、また、(範囲内かつ方向の範囲内で)隣接する住所は、もう1つの住所サブセグメント・ベクトルに割り当てられてもよい。
【0054】
住所サブセグメント・ベクトルへの住所セグメント・ベクトルの分割の限定しない一例を図示する一実施形態を、図10A及び図10Bに関して示す。図10Aは、#2〜#98の住所範囲を有する住所セグメント・ベクトル(ストリート・セグメント)を示す。図10Aは、要素180により特定される既知の住所地点#50の実際の住所と、住所セグメント・ベクトルの住所範囲#2〜#98の中間に存在する既知の住所地点#50についての補間された住所地点とを更に示す。これは要素182により特定される。当該実際の住所の投影点は、要素184により示される。投影点184と補間点182との間の距離を利用して、かつ、この距離と閾値距離とを比較することによって、対応する投影点184と補間点182との間の距離が閾値距離を上回る場合に、分割が必要であると判定できる。
【0055】
対応する投影点184と補間点182との間の距離が閾値距離を上回ると判定される場合、複数の住所サブセグメント・ベクトルへの住所セグメント・ベクトルの分割が、上述の本発明の実施形態の何れかの方法で実行される。図10Bに示すように、実際の住所#50の投影点184は、住所セグメント・ベクトルを複数の住所サブセグメント・ベクトルに分割するための「分割点」として使用可能である。その場合、例えば既知の住所地点の住所を端点として使用して第1のサブセグメント186が形成され、住所サブセグメント・ベクトル186の住所範囲は#2〜#50の範囲となる。次に、最初の住所セグメント・ベクトルの範囲における次の住所地点が、他方の住所サブセグメント・ベクトル188の始点の住所として使用され、その結果、図10Bに示すように#52〜#98の住所範囲が作成される。
【0056】
このように、実際の住所#50が第1の住所サブセグメント186の住所範囲の一部になるため、住所サブセグメント・ベクトル186及び188を利用する補間処理は、図10Aに示す住所セグメント・ベクトルを利用する場合よりも、はるかに改善されることが理解されよう。例えば、ナビゲーション装置のユーザが住所#60の位置を見つけたい場合、メモリに住所サブセグメント・ベクトル188を格納した(図10Aの住所セグメント・ベクトル181の代わりに、あるいは記憶容量がある場合には住所セグメント・ベクトル181とともに)デジタル地図アプリケーション・データベースを使用するナビゲーション装置は、この住所サブセグメント・ベクトル188内で、住所#60に対応する建物の実際の位置にはるかに近い位置を見つける。図10Aと比較すると分かるように、ナビゲーション装置が図10Aの#2〜#98の範囲の住所セグメント・ベクトル181のみを含むデジタル地図アプリケーション・データベースを代わりに利用した場合、既知の補間技術では、#60について図10Aの補間された住所182にはるかに近い結果になることにより、(実際は図10Bの住所サブセグメント・ベクトル188内に存在する)住所#60に対応する建物の実際の位置から遠く離れた結果が生じる。
【0057】
従って、住所#50が#2〜#98の住所範囲を有する住所セグメント・ベクトル辺における分割点である場合、分割の後、その一方のサブセグメントは#2〜#50の住所範囲を割り当てられ、他方のサブセグメントは#52〜#98の住所範囲を割り当てられる。あるいは、一方のサブセグメント辺(一方の住所サブセグメント・ベクトル)は#2〜#48の住所範囲を割り当てられてもよく、他方のサブセグメント辺は#50〜#98の範囲を割り当てられてもよい。本発明の実施形態は、何れの変形例にも同様に適用可能である。また、別の実施形態においては、例えばシステム/アプリケーションが2つの#50が存在するという曖昧性を処理可能であると仮定すると、分割点は、1つのサブセグメントの始点の住所と別のサブセグメントの終点の住所とが、1つの住所で分離されずに等しくなるように、両方の住所範囲に含まれてもよい。

【0058】
本発明の一実施形態において、分割点は、サブセグメント上の中間の投影点と補間点との間の全ての距離の平均値を低減するサブセグメント又は住所サブセグメント・ベクトルに割り当てられてもよい。別の実施形態においては、分割点は、サブセグメント上の中間の投影点と補間点とのペアの何れかの間の、相対的に最大の距離を低減するサブセグメントに割り当てられてもよい。当業者には明らかであるように、例えば、サブ範囲の大きさを最も近くするサブベクトルに分割点を割り当てる等の、そのような分割点を割り当てる他の方法が、住所セグメント・ベクトルの分割に対して同様に適用可能である。
【0059】
住所セグメント・ベクトルを複数の住所サブセグメント・ベクトルに分割した後、当該分割処理は、結果として得られた複数の住所サブセグメント・ベクトルの各々について繰り返されてもよい。言い換えると、各住所サブセグメント・ベクトルの住所範囲は、上述のように割り当てられてもよいし、複数の既知の住所地点は、複数の投影点を作成するために各住所サブセグメント・ベクトルに個別に投影されてもよいし、また、当該複数の投影点についての位置は、各住所サブセグメント・ベクトルについて個別に、複数の補間点を作成するために補間される。その後、投影点と対応する補間点との間の距離が閾値距離を上回る場合、住所サブセグメント・ベクトルは、複数の住所サブセグメント・ベクトルに更に分割可能である。これは、各住所サブセグメント・ベクトルについて繰り返され得るとともに、何れかの住所サブセグメント・ベクトルにおいて、投影点と補間点とのペアの何れかについて判定された相対的に最大の距離が、閾値距離以下になるまでの間、必要に応じて連続して更に繰り返され得る。少なくとも1つの実施形態においては、当該分割処理は、投影点と対応する補間点とのペアの間の距離の平均値を低減する点であって、住所セグメント・ベクトルに沿う点において、実行されてもよい。他の実施形態において、3つ以上の住所サブセグメント・ベクトルの計算は、他の反復法により実行されるか、あるいは当業者には既知である種々の非反復計算により実行されてもよい。
【0060】
従って、一実施形態において、既知の住所地点は、対応する住所サブセグメント・ベクトル上に再投影されてもよく、その後、補間点が当該住所地点の住所について判定又は作成されてもよく、その後、対応する投影点と補間点とのペアの間の距離が計算されてもよく、その後、相対的に最大の距離を有する投影点と補間点とのペアが、選択され、且つ、補間閾値と比較されてもよい。あるいは、別の実施形態において、当該既知の住所地点は、対応する住所サブセグメント・ベクトル上に再投影されてもよく、その後、補間点が住所地点の住所に対して判定又は作成されてもよく、住所サブセグメント・ベクトルが、住所サブセグメント・ベクトルの投影点と対応する補間点との間の距離の平均値が閾値距離より小さくなるまでの間、複数の住所サブセグメント・ベクトルに更に分割されてもよい。閾値距離を上回る場合には、住所サブセグメント・ベクトルは、例えば当該位置において、又は投影点等の点において、再度分割されてもよく、当該分割処理は、住所サブセグメント・ベクトルについての対応する投影点と補間点との間の距離の全てが補間閾値を下回るまで、セグメントの住所範囲の下限及び上限が同一になる(住所サブセグメント・ベクトルが単一の家屋番号のみを含むようになる)まで、あるいは、住所サブセグメント・ベクトルについて投影点が存在しなくなるまで、各ストリート・サブセグメント(住所サブセグメント・ベクトル)又は各ストリート・サブセグメント辺(住所サブセグメント・ベクトル)について再帰的に繰り返されてもよい。
【0061】
ソース・デジタル地図データベース及びデジタル地図アプリケーション・データベースは、始点及び終点を有する住所セグメント・ベクトル又はストリート・セグメント、ストリート名及び他の種類の属性、並びに、当該セグメントに割り当てられた住所を表す住所範囲を含むことが既知であり、ソース・デジタル地図データベースは、デジタル地図アプリケーション・データベースの住所セグメント・ベクトル又はストリート・セグメントよりも多くの属性を有する住所セグメント・ベクトル又はストリート・セグメントを有する。本発明の一実施形態のソース・デジタル地図データベースから作成されたデジタル地図アプリケーション・データベースは、住所セグメント・ベクトルの代わりに、及び住所セグメント・ベクトルとともに、のうちの少なくとも1つにより、住所サブセグメント・ベクトルを含み、各住所サブセグメント・ベクトルは、本発明の一実施形態の(住所サブセグメント・ベクトルを含む)ソース・デジタル地図データベースからコピー又は作成される前に、当該デジタル地図アプリケーション・データベースに事前に格納された対応する住所セグメント・ベクトルの属性を含む。そのようなデジタル地図アプリケーション・データベースは、例えばジオコーディング、GIS及びナビゲーション技術において、例えば(例えば、ナビゲーション装置の一体型入力表示装置を介して選択又は入力された)所望の移動目的地等の場所の位置を特定する場合に使用されてもよい。そのようなデジタル地図アプリケーション・データベースは、例えばジオコーディングにおいて使用される場合は中央サーバに格納されてもよく、車両搭載型のナビゲーション装置、パーソナルナビゲーション装置、及び、携帯電話、PDA等を含むがそれらに限定されないナビゲーション機能を有する他の何らかの装置、の少なくとも何れかに格納されてもよく、並びに/又は何らかの種類のデジタル媒体に格納されてもよい。
【0062】
一般に、そのようなデジタル地図アプリケーション・データベースは、例えばインターネット又はモバイル無線接続を介して新たなデジタル地図アプリケーション・データベース(本発明の一実施形態の住所サブセグメント・ベクトルを含む新たなデジタル地図アプリケーション・データベース等)に定期的に(例えば、新たな情報が受信される数ヶ月毎に)アクセスしてそれをダウンロード又はコピーすることにより、あるいは、車両搭載型のナビゲーション装置の場合、当該車両搭載型のナビゲーション装置のメモリに格納された地図情報を更新するために車両の当該車両搭載型のナビゲーション装置に入力可能なCD−ROM等に格納された新たな更新済のデジタル地図アプリケーション・データベースにより、パーソナルナビゲーション装置(PND)、あるいは、PDA、携帯電話等のナビゲーション機能及びマッピング機能の少なくとも何れかを有する他の何らかの装置にダウンロード可能である。そのような更新技術は、上述の技術に限定されず、地図データベースを更新する任意の技術も含み得る。
【0063】
従って、分割された住所セグメント・ベクトル又は分割された住所サブセグメント・ベクトルから生じる、上述の実施形態の何れかから得られた住所サブセグメント・ベクトルを含むデジタル地図アプリケーション・データベースは、対応する住所セグメント・ベクトルの代わりに、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより、(例えば、中央サーバに、後に例えば車両搭載型のナビゲーション装置のメモリに格納するためにCD−ROM又はコンピュータが読取可能な他の媒体に、ナビゲーション装置のメモリに)格納されてもよい。そのような格納(保存)処理は、ジオコーディングのための装置及びナビゲーション装置の少なくとも何れかにおけるメモリと、中央サーバにおけるメモリとの少なくとも何れかにおいて行われる。対応する住所セグメント・ベクトルの代わりに、又は対応する住所セグメント・ベクトルとともに保存された場合、元の住所セグメント・ベクトルの属性のうちの何れか又は全ては、結果として得られている住所サブセグメント・ベクトルに対して割り当てられてもよい。分割点の何れかの辺に関する属性を保持することが最も重要であり、その場合、住所番号(及び他の属性)は、それに対して割り当てられるか、又は保持される。何れの場合も、何らかの割り当て方法で結果として得られた住所サブセグメント・ベクトルの属性として、住所セグメント・ベクトルの住所番号を割り当てる必要がある。
【0064】
住所サブセグメント・ベクトルが作成されると、複数の住所サブセグメント・ベクトルは、対応する住所セグメント・ベクトルの代わりに(あるいは、いくつかの例においては対応する住所セグメント・ベクトルとともに)、本発明の一実施形態におけるメモリのデジタル地図アプリケーション・データベースに格納されてもよい(この場合、「メモリ」という用語は、ナビゲーション機能を有する装置へ後にダウンロードさせるための中央サーバのメモリ、CD−ROM、又は、ナビゲーション装置等の装置が上述の少なくとも1つの実施形態の分割処理を実行する機能を有する場合にはその装置のメモリ、を含んでもよいが、それらに限定されない)。例えば図10A及び図10Bの例に示すように、例えば住所セグメント・ベクトル#2〜#98(図10Aの要素181)の代わりに、住所サブセグメント・ベクトル#2〜#50(図10Bの要素186)及び住所サブセグメント・ベクトル#52〜#98(図10Bの要素188)が格納されてもよい。更に、これらの(住所範囲#2〜#50を有する)住所サブセグメント・ベクトル186及び(#52〜#98の住所範囲を有する)住所サブセグメント・ベクトル188は、図10Aに示す#2〜#98の住所範囲についての住所セグメント・ベクトルの代わりに格納されてもよく、これらの住所サブセグメント・ベクトルは、他の住所セグメント・ベクトル又は住所サブセグメント・ベクトルと共に、メモリのデジタル地図アプリケーション・データベースに格納されてもよい。例えば、相対的に最大の距離又は判定された距離の平均値等の、投影点と補間点との間の距離が、住所セグメント・ベクトルについての閾値距離以下である場合、当該住所セグメント・ベクトルは、更に分割されることなく、データベース及びメモリの少なくとも何れかに、格納又は保持されてもよい。そのため、分割された場合にユーザが所望の位置を見つけるのに有用である住所セグメント・ベクトル(又はサブベクトル)のみが、分割されて、メモリに格納される必要がある。従って、不必要に大量の住所サブセグメント・ベクトルをメモリに格納する必要がないため、補間アルゴリズムの性能が向上するとともに、必要なメモリ空間が必要以上に増加しない。このことは、PND、携帯電話、PDA及びナビゲーション機能を有するが記憶容量が限られる他の装置等の、ポータブルナビゲーション装置及びハンドヘルドナビゲーション装置において特に重要である。
【0065】
例えば対応する投影点と補間点との間の距離が補間閾値を下回る場合、住所セグメント・ベクトルは(それらの属性と共に)メモリに格納され続ける。しかし、投影点と補間点との間の距離が補間閾値を上回ると、住所セグメント・ベクトルは、例えば既知の住所地点の投影点において住所サブセグメント・ベクトルに分割されてもよい。尚、当該分割処理は、投影点と補間点との間の距離として相対的に最小の距離を提供する、(住所サブセグメント・ベクトルの終点又は住所サブセグメント・ベクトルの始点である分割点を含む)住所範囲と、結果として得られる住所サブセグメント・ベクトルとは無関係に、実行されてもよい。当該分割処理の後、上述の本発明の実施形態の方法は、住所サブセグメント・ベクトルについて繰り返されてもよい。
【0066】
少なくとも1つの実施形態において、住所セグメント・ベクトルの代わりに住所サブセグメント・ベクトルをデジタル地図アプリケーション・データベースに格納することがアプリケーションにとって有利である可能性があり、また、少なくとも1つの実施形態において、住所サブセグメント・ベクトル及び保存されている住所セグメント・ベクトルの両方をデジタル地図アプリケーション・データベースに格納することがアプリケーションにとって有利である可能性がある。従って、住所サブセグメント・ベクトルは、住所セグメント・ベクトルの代わりに、及び住所セグメント・ベクトルとともに、のうちの少なくとも何れかにより格納されてもよい。例えば、分割されていない住所セグメント・ベクトルを使用することは、表示目的又は表示用途について、より有効である可能性がある一方で、分割された住所サブセグメント・ベクトルを使用することは、位置の特定/ナビゲーションの目的又は用途について、より有効である可能性がある。メモリの制約により、デジタル地図アプリケーション・データベースにその両方を格納することが可能である場合には、少なくとも1つの実施形態において、新たな住所サブセグメント・ベクトル及び住所セグメント・ベクトルの両方を、システムをより有効化するためにそれぞれが使用され得るように、デジタル地図アプリケーション・データベースに格納することは、有用であろう。
【0067】
尚、住所セグメント・ベクトルの分割処理をさらに改善するため、既知の住所地点をどのように当該住所セグメント・ベクトルに適用するかを判定するために、記載されたアルゴリズム以外の技術が実行可能であってもよい。従って、本発明の実施形態は、上述のアルゴリズムによって限定されるべきではない。本出願は、本出願に記載された特許請求の範囲によってのみ限定されるべきである。本発明の少なくとも1つの実施形態の主旨は、改善が生じる場合に住所セグメント・ベクトルの分割を利用することによって、補間処理を更に改善することである。
【0068】
本発明の別の実施形態は、分割されていない複数のベクトルを格納するとともに、住所セグメント・ベクトルが分割された場合に、上述の方法の実施形態により作成された複数の住所サブセグメント・ベクトルを、対応する複数の住所セグメント・ベクトルの代わりに、及び対応する複数の住所セグメント・ベクトルとともに、のうちの少なくとも何れかにより格納しているメモリを対象としている。少なくとも1つの実施形態において、住所セグメント・ベクトルの代わりに住所サブセグメント・ベクトルをデジタル地図アプリケーション・データベースに格納しているメモリが、アプリケーションにとって有利である可能性があり、また、少なくとも1つの実施形態において、住所サブセグメント・ベクトル及び住所セグメント・ベクトルの両方をデジタル地図アプリケーション・データベースに格納するメモリがアプリケーションにとって有利である可能性がある。例えば、分割されていない住所セグメント・ベクトルは、表示の目的においてより有効である可能性があり、分割された住所サブセグメント・ベクトルは、上述のように位置の特定/ナビゲーションの目的においてより有効である可能性がある。メモリの制約によりその両方を格納することが可能である場合には、少なくとも1つの実施形態において、住所サブセグメント・ベクトル及び住所セグメント・ベクトルの両方を格納することは有用であろう。本発明の別の実施形態は、そのようなメモリを含むナビゲーション装置等の装置を対象としている。
【0069】
本発明の実施形態はデジタル地図アプリケーション・データベースに対する変更を伴う一方で、他のベンダは、当該デジタル地図アプリケーション・データベースを、又はそれから派生した当該データの編集版を利用する、デジタル地図アプリケーション・データベース/アプリケーション変換器及びデバイス・アプリケーション・ソフトウェアを提供する。少なくとも1つの実施形態は、所望の場所に対応する情報をユーザに提供するための、地理情報システム(GIS)に基づくアプリケーション・プログラムを対象としている。当該アプリケーション・プログラムは、複数の住所セグメント・ベクトル及び複数の住所サブセグメント・ベクトルを含む地図データベース(デジタル地図アプリケーション・データベース)を含む。当該複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、当該住所地点の住所についての補間された位置に相当する補間点との間の距離が、補間距離を上回る場合に、対応する住所セグメント・ベクトルの代わりに地図データベースに格納される。
【0070】
デバイス・アプリケーション・ソフトウェアは、ユーザ入力に応じて、派生したデジタル地図アプリケーション・データベースにアクセスして操作する。ユーザに対するソフトウェアの出力は、リスト、テキスト、地図若しくは映像等のグラフィック表示、発話等の音声、又は他の種類の出力であってもよい。多くのGISアプリケーション、インターネット。アプリケーション、及びナビゲーション・アプリケーションは、上述の本発明の実施形態を使用できる。これらのアプリケーションは、(テキスト/リストに基づく)ジオコーディング・アプリケーション、(グラフィック/リスト/発話に基づく)経路計画/方向アプリケーション、及びグラフィックに基づく表示アプリケーションを含む。当該アプリケーションは、とりわけ、ナビゲーションシステム、インターネットに基づくシステム、及び地理情報システム(GIS)を含んでもよい。当該アプリケーションは、マッピング・プログラム、ナビゲーション・プログラム、又は何らかの他の種類のプログラムであってもよい。上述のように、地図アプリケーションの消費者は、所望の場所の位置を特定するための、種々の装置及びシステムを提供されている。これらの装置及びシステムは、運転者がストリート及び道路をナビゲートし、且つ、所望の場所を入力できるようにする車両搭載型のナビゲーションシステム、同一機能を実行できるパーソナルデジタルアシスタント(「PDA」)及び携帯電話等のハンドヘルド装置、並びに、ユーザが所望の結果を使用又は描写する地図にユーザがアクセス可能なインターネット・アプリケーションの形態をとる。本開示の目的のため、そのような結果の全ては単に「場所」として定義される。
【0071】
図11は、パーソナル・デジタル・アシスタント(PDA)等のポータブルハンドヘルド装置において使用される一実施形態を示す。当該装置は、例えば携帯電話であってもよい。PDAの地図ソフトウェアにおいて、探索の一例は、150 Central Park Westへの運転指示を求めるユーザにより実行されてもよい。PDAの地図ソフトウェアは、本発明の実施形態を利用して、150 Central Park Westの位置を正確に表示する。
【0072】
図12は、全地球測位システム(GPS)等の車両搭載型のナビゲーションシステムにおいて使用される方法、データベース、メモリ等の一実施形態を示す。GPS地図ソフトウェアにおいて、探索の一例は、GPS地図ソフトウェアの下部に示すように35 West Hill Roadへの運転指示を求める運転者により実行されてもよい。当該運転者が当該GPS地図ソフトウェアを使用して自身の目的地に到着すると、当該GPSの地図ソフトウェアは、本発明の実施形態を利用して35 West Hill Roadの位置を正確に表示する。
【0073】
図13は、航空写真上に重ね合わされた住所地点の一例を示す一実施形態を示す。本例において、住所地点付近に位置を補間するためにサブセグメント化(sub-segmenting)が必要である可能性があり、これはセグメント上の範囲に依存してもよい。例えば、住所範囲が1101〜1199である場合、1155の補間位置はブロックの端部ではなく中央に存在し、サブセグメント化により補間が改善されるであろう。しかし、Detroit Stの当該部分における範囲が1107〜1155である場合、サブセグメント化は、非常に高精度のアプリケーション以外では不要であろう。その場合、サブセグメント化は、ストリート・セグメントに沿う住所の分布におけるより小さな非線形性に対応するために適用され得る。
【0074】
本発明の別の実施形態は、所望の位置に対応する情報をユーザに提供する図14のシステム900を対象としている。システム900は、複数の住所セグメント・ベクトル、及び複数の住所サブセグメント・ベクトルを含むソース地図データベース930と、所望の位置に関するクエリに応じて、アプリケーション・プログラムを使用して、デジタル地図アプリケーション・データベースに含まれる住所セグメント・ベクトル又は住所サブセグメント・ベクトルに対応する住所範囲内の、少なくとも1つの住所地点を検索するプロセッサ又は演算装置910とを備える。当該複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、住所地点の住所についての補間された位置に相当する補間点との間の距離が、閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて(及び/又は、対応する住所セグメント・ベクトルとともに)、デジタル地図アプリケーション・データベースに格納される。以下では、システム900の一例について説明する。
【0075】
図14は、本発明の実施形態と共に使用可能なシステム900の一例を示すブロック図である。図14は構成要素を論理的に別個のものとして示すが、これは単に図示する目的のためである。同図に示される構成要素が、組み合わせ可能であり、又は、個別のソフトウェア、ファームウェア及びハードウェア構成要素の少なくとも何れかに分割可能であることは、当業者には明らかであろう。更に、そのような構成要素は、それらが組み合わされるか又は分割される方法に関係なく、同一の演算装置/システム上で実行可能であり、あるいは、1つ以上のネットワーク又は他の適切な通信手段によって接続された異なる演算装置/システムに分散可能であることも、
当業者には明らかであろう。
【0076】
図14に示すように、システム900は、一般に、1つ以上のメモリ912、1つ以上のプロセッサ914、及び、1つ以上の何らかの種類の記憶装置又はリポジトリ(repository)916を備え得る演算装置910を含み、装置916のうちの少なくとも1つはデジタル地図アプリケーション・データベース970を含む。演算装置910は、表示装置918を更に含んでいてもよく、表示装置918は、当該装置上で動作し、且つ、システムがユーザに対して地図及び他の情報を表示可能なグラフィカル・ユーザ・インタフェース、即ちGUI920を含む。ユーザは、演算装置を使用することにより、例えば地図上に場所(locality)を表示することを要求するか、あるいは、地図上の経路及びテキスト指示の少なくとも何れかとして、運転指示を表示することを要求する。
【0077】
ソース地図データベース930は、演算装置又はシステム910の外部記憶装置として示されるが、いくつかの例において、ソース地図データベース930は記憶装置916と同一の記憶装置であってもよい。本発明の実施形態によれば、ソース地図データベース930は、地図セグメント及び地図サブセグメントのテーブル及びインデックス932、住所地点のテーブル及びインデックス934、並びに、形状点のテーブル及びインデックス936を含む。
【0078】
自社開発の地図データベース作成ソフトウェア940は、ソース地図データベース930内の地図セグメントのテーブル及びインデックス932、住所地点のテーブル及びインデックス934、並びに形状点のテーブル及びインデックス936をそれぞれ作成するために、実世界の(real-world)場所ソース(locality sources)及び緯度/経度ソース960を使用する。ソース地図データベース930からの情報は、ソース地図データベース/アプリケーション地図データベース変換器950によって使用され、これは最終的に演算装置910のユーザによって使用される。ソース地図データベース/アプリケーション地図データベース変換器950は、ユーザの演算装置910に対してリモートであると示されている。この変換は、地図ベンダの結果、及びアプリケーション・ソフトウェア・プロバイダの結果であってもよい。結果として得られたデジタル地図アプリケーション・データベース970は、一般に、装置の記憶装置916に格納される。このデバイス・アプリケーション・ソフトウェア950もリモートであると示されるが、ユーザの演算装置910に備わっていてもよい。
【0079】
従って、本発明の一実施形態は、所望の位置に対応する情報をユーザに提供するシステム900を対象としていてもよい。システム900は、複数の住所セグメント・ベクトル及び複数の住所サブセグメント・ベクトルを含むデジタル地図アプリケーション・データベース970を備える。当該複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、当該住所地点の住所の補間された位置に相当する補間点との間の距離が、閾値距離を上回る場合に、対応する住所セグメント・ベクトルの代わりに、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも何れかにより、デジタル地図アプリケーション・データベース(970)に格納される。上述の処理のアプリケーションは、変換プロセス950を介してデジタル地図アプリケーション・データベース970に変換された関連する結果を用いて、ソース地図データベース930に適用される。プロセッサ914は、所望の位置に関するクエリに応じて、デジタル地図アプリケーション・データベース970を検索し、アプリケーション・プログラムを使用してデジタル地図アプリケーション・データベースの住所セグメント・ベクトル又は住所サブセグメント・ベクトルに対応する補間された位置を計算する。当該システムは、例えば、インターネットに基づくシステム及び車両搭載型のナビゲーションシステムの少なくとも何れかを含んでもよい。本発明の一実施形態は、例えばナビゲーション装置200等の装置を対象としている。ナビゲーション装置は、ポータブルナビゲーション装置又は車両搭載型のナビゲーション装置であってもよい。本発明の一実施形態の装置は、複数の住所セグメント・ベクトル及び複数の住所サブセグメント・ベクトルを含むデジタル地図アプリケーション・データベースを格納するメモリ230(又はメモリリソース)と、格納されたアプリケーション地図データベースを使用して、入力又は選択された住所の位置を表示するディスプレイ240とを含んでもよい。複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に対応する投影点と、当該住所地点の住所の補間位置に対応する補間点との間の距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルの代わりに、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも何れかにより、デジタル地図アプリケーション・データベースに格納される。当該装置がナビゲーション装置200である場合、ナビゲーション装置200は、移動目的地の入力又は選択を促す入力装置(220)と、入力又は選択された移動目的地への移動経路を計算するプロセッサ(210)とを更に含んでもよい。移動経路の計算には、格納されたアプリケーション地図データベースを利用し、ディスプレイは計算された移動経路を表示するために使用可能である。
【0080】
本発明の少なくとも1つの実施形態は、例えば以下に説明する、移動目的地の入力又は選択を求める入力装置220及び表示画面240を含む一体型入力表示装置と、複数の住所セグメント・ベクトル及び複数の住所サブセグメント・ベクトルを含む地図データベース(デジタル地図アプリケーション・データベース)を格納するメモリ230(又はメモリリソース)と、入力又は選択された移動目的地への移動経路を計算するプロセッサ210とを備えるナビゲーション装置200を対象としていてもよい。当該複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に対応する投影点と、当該住所地点の住所の補間位置に対応する補間点との間の距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルの代わりにデジタル地図アプリケーション・データベースに格納される。移動経路の計算は、格納されたアプリケーション地図データベースを利用する。以下では、そのようなナビゲーション装置200についての限定しない一実施形態について説明する。
【0081】
図15は、本願の一実施形態のナビゲーション装置200の電子構成要素の一例を、ブロック構成要素の形式で示す、例示的な表現である(図11及び図12の表現よりも詳細なものを提供するが、図12の車両搭載型のナビゲーション装置は、図11のポータブルナビゲーション装置よりもメモリに組み込まれることが多いことに留意されたい)。尚、ナビゲーション装置200のブロック図は、ナビゲーション装置の全ての構成要素を含むものではなく、構成要素の多くの例を表すにすぎない。
【0082】
ナビゲーション装置200は、筐体(不図示)内に位置付けられる。筐体は、入力装置220及び表示画面240に接続されるプロセッサ210を含む。入力装置220は、キーボード装置、音声入力装置、タッチパネル、及び情報を入力するために利用される他の任意の既知の入力装置のうちの少なくとも1つを、それらに限定されることなく含み得る。また、表示画面240は、例えばLCDディスプレイ等の、任意の種類の表示画面を含み得る。特定の装置例においては、入力装置220及び表示画面240は、タッチパッド又はタッチスクリーン入力を含む一体型入力表示装置に一体化され、これにより、ユーザは、複数の表示選択肢のうちの1つを選択するか、又は複数の仮想ボタンのうちの1つを操作するためには、表示画面240の一部分に触れるだけでよい。
【0083】
ナビゲーション装置200は、例えば、可聴出力装置(例:ラウドスピーカ)、文字出力装置等の、出力装置260を含んでいてもよい。出力装置260がナビゲーション装置200のユーザに対して可聴情報を生成できるため、同様に、入力装置240は、入力音声コマンドを受信するマイク及びソフトウェアを更に含み得ると理解される。
【0084】
ナビゲーション装置200において、プロセッサ210は、接続225を介して入力装置220に動作可能に接続され、且つ、入力装置220から入力情報を受信するように設定される。また、プロセッサ210は、情報を出力するために、表示画面240及び出力装置260のうちの少なくとも一方に、出力接続245を介して動作可能に接続される。更に、プロセッサ210は、接続235を介してメモリリソース230に動作可能に接続され、接続275を介して入出力(I/O)ポート270との間で情報を送受信するように更に構成される。この場合、I/Oポート270は、ナビゲーション装置200の外部のI/O装置280に接続可能である。メモリリソース230は、上述の本発明の実施形態のうちの何れかにおいて説明したように、デジタル地図アプリケーション・データベース(又は、ナビゲーション装置200が、十分なメモリ記憶容量を有するとともに、例えば図7の方法を実行する一例の実施形態の、少なくとも1つの場合においては、ソース・データベース)を格納しており、例えばランダム・アクセス・メモリ(RAM)等の揮発性メモリや、例えば、デジタルメモリ、フラッシュメモリ等の不揮発性メモリから成る。外部I/O装置280は、例えばイヤホン等の外部聴音装置を含んでもよいが、これに限定されない。更に、I/O装置280への接続は、例えばハンズフリー動作と音声起動動作との少なくとも一方のため、イヤホン又はヘッドフォンへの接続のため、並びに/あるいは、例えば移動電話への接続のためのカーステレオユニット等の他の任意の外部装置への、有線接続又は無線接続であってもよい。この場合、移動電話接続は、ナビゲーション装置200とインターネット又は例えば他の任意のネットワークとの間のデータ接続を確立するためと、インターネット又は例えば他の任意のネットワークを介するサーバへの接続を確立するためとの少なくとも一方のために使用されてもよい。
【0085】
図15は、接続255を介するプロセッサ210とアンテナ/受信機250との間の動作可能な接続を更に示す。この場合、アンテナ/受信機250は、例えばGPSアンテナ/受信機であってもよい。参照番号250で示されるアンテナ及び受信機は、図示のために概略的に組み合わされるが、当該アンテナ及び受信機は、別個に位置する構成要素であってもよく、当該アンテナは、例えばGPSパッチアンテナ又はヘリカルアンテナであってもよいことが理解されるだろう。
【0086】
更に、図15に示す電子構成要素が従来の方法で電源(不図示)により電力を供給されることが当業者には理解されるだろう。当業者によって理解されるように、図15に示す構成要素の異なる構成が本願の範囲内であると考えられる。例えば、図15に示す構成要素は、有線接続と無線接続との少なくとも一方等を介して互いに通信状態であってもよい。従って、本願のナビゲーション装置200の範囲には、ポータブル又はハンドヘルドナビゲーション装置200、及び車両搭載型のナビゲーション装置の少なくとも一方が含まれる。
【0087】
また、図15のポータブル又はハンドヘルドナビゲーション装置200は、例えば、自転車、オートバイ、自動車、又はボート等の車両に、既知の方法で接続されるか又は「ドッキング」される。その場合、そのようなナビゲーション装置200は、ポータブル又はハンドヘルドナビゲーションとして使用するために、ドッキングされた場所から取り外し可能である。
【0088】
更に、少なくとも1つの実施形態において、ナビゲーション装置200は、新たに作成された、(例えば、図6の方法で作成された)住所サブセグメント・ベクトルを含むデジタル地図アプリケーション・データベースをメモリ230に格納できるだけでなく、ナビゲーション装置200は、上述のように既知の住所地点を含むデジタル地図データベース又は他のデータベースを格納する際に、当該ナビゲーション装置200自体のプロセッサ210を使用して、上述した図7の方法の実施形態の動作を実行できる。例えば、少なくとも1つの代替的な実施形態においては、図7の方法は、複数の住所サブセグメント・ベクトルを含むデジタル地図ソース・データベースから作成された、その後にメモリ230に格納される、新たに作成されたデジタル地図アプリケーション・データベースを用いて、ナビゲーション装置200内のプロセッサ210によって実行され得る。
【0089】
ここで図16を参照すると、ナビゲーション装置200は、デジタル接続(例えば、既知のBluetooth技術を介するデジタル接続)を確立する(不図示の)移動装置(移動電話、PDA、及び移動電話技術を用いる任意の装置のうちの少なくとも1つ等)を介して、サーバ302との「モバイル」ネットワーク接続又は通信ネットワーク接続を確立してもよい。そうして、そのネットワークサービスプロバイダを介して、当該移動装置は、サーバ302とのネットワーク接続を(例えば、インターネットを介して)確立できる。そのため、「モバイル」ネットワーク接続は、情報に対する「リアルタイム」又は少なくとも非常に「最新」のゲートウェイを提供するために、(単体時、及び車載走行時の少なくとも一方において移動可能であり、且つ、多くの場合移動している)ナビゲーション装置200とサーバ302との間で確立される。
【0090】
例えばインターネット(World Wide Web等)を使用して、(サービスプロバイダを介する)移動装置とサーバ302等の別の装置との間にネットワーク接続を確立することは、既知の方法で行われ得る。これには、例えばTCP/IP層プロトコルの使用が含まれ得る。当該移動装置は、CDMA、GSM、WAN等の任意の数の通信規格を利用できる。そのため、ナビゲーション装置200は、例えば図6に関して上述した方法の実施形態を用いて作成された、複数の住所サブセグメント・ベクトルを含む新たに作成されたデジタル地図データベースを受信可能であり、その後にそれをメモリ230に格納可能である。
【0091】
そのため、例えば移動電話又はナビゲーション装置200内の移動電話技術を介するデータ接続を介して達成されるインターネット接続が利用されてもよい。この接続の場合、サーバ302とナビゲーション装置200との間でインターネット接続が確立される。これは、例えば、移動電話又は他の移動装置及びGPRS(汎用パケット無線サービス)接続(GPRS接続は、通信会社により提供される移動装置用高速データ接続であり、GPRSはインターネットへの接続方法である)を介して行われ得る。
【0092】
更に、ナビゲーション装置200は、移動装置400とのデータ接続を完了し、例えば既存のBluetooth技術を介して既知の方法でインターネット及びサーバ302とのデータ接続を最終的に完了する。この場合、例えばデータプロトコルは、GSM規格に対するデータプロトコル規格であるGSRM等の任意の数の規格を利用できる。そのため、ナビゲーション装置200は、例えば図6に関して上述した方法の実施形態を用いて作成された、複数の住所サブセグメント・ベクトルを含む新たに作成されたデジタル地図データベースを受信可能であり、その後にそれをメモリ230に格納可能である。
【0093】
ナビゲーション装置200は、ナビゲーション装置200自体の中に、自らの移動電話技術を含んでもよい(例えばアンテナを含み、この場合ナビゲーション装置200の内部アンテナがオプションとして用いられてもよい)。ナビゲーション装置200内の移動電話技術は、上述のような内部構成要素を含みこと、及び、例えば必要な移動電話技術とアンテナとの少なくとも一方を備える挿入可能なカードを含むことのうち、少なくとも一方が可能である。そのため、ナビゲーション装置200内の移動電話技術は、任意の移動装置400の方法と同様の方法で、例えばインターネットを介して、ナビゲーション装置200とサーバ302との間にネットワーク接続を同様に確立できる。そのため、ナビゲーション装置200は、例えば図6に関して上述した方法の実施形態を用いて作成された、複数の住所サブセグメント・ベクトルを含む新たに作成されたデジタル地図データベースを受信可能であり、その後にそれをメモリ230に格納可能である。
【0094】
GRPS電話設定の場合、移動電話の機種、製造業者等の多様な範囲に関して正しく動作するために、Bluetooth対応の装置が使用されてもよく、機種/製造業者専用設定は、例えばナビゲーション装置200に格納されてもよい。この情報のために格納されたデータは更新され得る。
【0095】
図16は、汎用通信チャネル318を介してサーバ302と通信する、異なる多数の構成の何れかによって実現可能なナビゲーション装置200を示している。通信チャネル318を介する接続がサーバ302とナビゲーション装置200との間に確立される場合、サーバ302とナビゲーション装置200とは通信可能である(尚、そのような接続は、移動装置を介するデータ接続、インターネットを介してパーソナル・コンピュータを介する直接接続等である)。そのため、ナビゲーション装置200は、例えば図6に関して上述した方法の実施形態を用いて作成された、複数の住所サブセグメント・ベクトルを含む新たに作成されたデジタル地図データベースを受信可能であり、その後にそれをメモリ230に格納可能である。
【0096】
サーバ302は、図示しない他の構成要素に加えて、メモリ306に動作可能に接続され、且つ、有線又は無線接続314を介して大容量データ記憶装置312に動作可能に更に接続される、プロセッサ304を含む。更に、プロセッサ304は、通信チャネル318を介してナビゲーション装置200と情報の送受信を行うために、送信機308及び受信機310に動作可能に接続される。送受信される信号は、データ信号、通信信号及び他の伝搬信号の少なくとも1つを含んでもよい。送信機308及び受信機310は、ナビゲーション装置200の通信設計において使用される通信条件及び通信技術に従って選択又は設計されてもよい。尚、送信機308及び受信機310の機能は、信号送受信機に組み合わされてもよい。
【0097】
サーバ302は、大容量記憶装置312に更に接続される(又は、大容量記憶装置312を含む)。尚、大容量記憶装置312は、通信リンク314を介してサーバ302に接続されてもよい。大容量記憶装置312は、ナビゲーションデータ及び地図情報のストアを含む。また、大容量記憶装置312は、サーバ302とは別個の装置であってもよく、サーバ302に組み込まれてもよい。
【0098】
ナビゲーション装置200は、通信チャネル318を介してサーバ302と通信するように構成され、図15に関して上述したように、プロセッサ210、メモリ230等を含むだけでなく、信号及びデータの少なくとも何れかを、通信チャネル318を介して送信する送信機320及び受信する受信機322を含む。尚、これらの装置は、更に、サーバ302以外の装置と通信するためにも使用され得る。更に、送信機320及び受信機322は、ナビゲーション装置200の通信設計において使用される通信条件及び通信技術に従って選択又は設計され、送信機320及び受信機322の機能は、単一の送受信機に組み合わされてもよい。そのため、ナビゲーション装置200は、例えば図6に関して上述した方法の実施形態を用いて作成された、複数の住所サブセグメント・ベクトルを含む新たに作成されたデジタル地図データベースを受信可能であり、その後にそれをメモリ230に格納可能である。
【0099】
サーバメモリ306に格納されるソフトウェアは、プロセッサ304に命令を提供し、サーバ302がナビゲーション装置200にサービスを提供できるようにする。サーバ302により提供される1つのサービスには、ナビゲーション装置200からの要求の処理、及び大容量データ記憶装置312からナビゲーション装置200へのナビゲーションデータの送信を含が含まれる。サーバ302によって提供される別のサービスには、所望のアプリケーション用の種々のアルゴリズムを使用したナビゲーションデータの処理、及びナビゲーション装置200へのこれらの計算の結果の送信が含まれる。
【0100】
一般に、通信チャネル318は、ナビゲーション装置200とサーバ302とを接続する伝搬媒体又はパスを表す。サーバ302及びナビゲーション装置200の両方は、通信チャネルを介してデータを送信する送信機と、通信チャネルを介して送信されたデータを受信する受信機とを含む。
【0101】
通信チャネル318は、特定の通信技術に限定されない。更に、通信チャネル318は、単一の通信技術に限定されない。即ち、チャネル318は、種々の技術を使用する複数の通信リンクを含んでもよい。例えば、通信チャネル318は、電気通信、光通信、及び電磁通信のうちの少なくとも1つ等のためのパスを提供するように構成され得る。そのため、通信チャネル318は、電気回路、ワイヤ及び同軸ケーブル等の電気導体、光ファイバケーブル、コンバータ、無線周波数(RF)波、大気、空間等のうちの1つ又はそれらの組み合わせを含むが、それらに限定されない。更に、通信チャネル318は、例えば、ルータ、リピータ、バッファ、送信機及び受信機等の中間装置を含み得る。
【0102】
1つの例示的な構成において、通信チャネル318は、電話及びコンピュータネットワークを含む。更に、通信チャネル318は、無線周波数、マイクロ波周波数、赤外線通信等の無線通信に適応できてもよい。更に、通信チャネル318は衛星通信に適応できる。
【0103】
通信チャネル318を介して送信される通信信号は、所与の通信技術において必要とされる又は望まれる信号を含むが、それらに限定されない。例えば、当該信号は、時分割多元接続(TDMA)、周波数分割多元接続(FDMA)、符号分割多元接続(CDMA)、グローバル・システム・フォー・モバイル・コミュニケーションズ(GSM:Global System for Mobile Communications)等のセルラ通信技術において使用されるように構成されてもよい。デジタル信号及びアナログ信号の両方が、通信チャネル318を介して送信できる。これらの信号は、通信技術にとって望ましい変調信号、暗号化信号、及び圧縮信号のうちの少なくとも1つであってもよい。
【0104】
サーバ302は、無線チャネルを介してナビゲーション装置200がアクセス可能なリモートサーバを含む。サーバ302は、ローカルエリアネットワーク(LAN)、ワイドエリアネットワーク(WAN)、仮想プライベートネットワーク(VPN)等に位置するネットワークサーバを含んでもよい。
【0105】
サーバ302は、デスクトップ又はラップトップコンピュータ等のパーソナル・コンピュータを含んでもよく、通信チャネル318は、パーソナル・コンピュータとナビゲーション装置200との間に接続されるケーブルであってもよい。あるいは、パーソナル・コンピュータは、ナビゲーション装置200とサーバ302との間に接続されて、サーバ302とナビゲーション装置200との間にインターネット接続を確立してもよい。あるいは、インターネットを介してナビゲーション装置200をサーバ302に接続するために、移動電話又は他のハンドヘルド装置がインターネットへの無線接続を確立してもよい。そのため、ナビゲーション装置200は、例えば図6に関して上述した方法の実施形態を用いて作成された、複数の住所サブセグメント・ベクトルを含む新たに作成されたデジタル地図データベースを受信可能であり、その後にそれをメモリ230に格納可能である。
【0106】
ナビゲーション装置200は、(例えば、上述の本発明の応用の一実施形態についての方法(例えば図7の方法等)から作成されたデジタル地図ソース・データベースから生成される、デジタル地図アプリケーション・データベース等の)情報を、情報ダウンロードを介してサーバ302から与えられてもよい。当該情報は、自動的に更新される情報(例えば、地図、又は地図データベース情報等)、若しくはユーザがナビゲーション装置200をサーバ302に接続する場合に、周期的に更新される情報であってもよいし、又は、例えば無線移動接続装置及びTCP/IP接続を介して、サーバ302とナビゲーション装置200との間で、より継続して若しくは接続が頻繁に確立される場合に、更に動的な情報であってもよいし、それらの両方であってもよい。多くの動的な計算のために、サーバ302内のプロセッサ304が、大量の処理要求に対処するために使用されてもよい。しかし、ナビゲーション装置200のプロセッサ210は、多くの場合、サーバ302への接続に関係なく、多くの処理及び計算にも対処可能である。これまでに示したように、複数の住所サブセグメント・ベクトルを含むデジタル地図データベースは、サーバ302において、あるいは、(ナビゲーション装置に格納されたデジタル地図データベースが既知の住所地点を含むことを想定した場合には)少なくとも1つの実施形態においてはナビゲーション装置200自体においても、例えば図6に関して上述した方法の実施形態を用いて作成されてもよい。また、当業者には理解されるように、上述した本願の方法の実施形態に含まれる技術の何れも、本明細書で説明した装置又はナビゲーション装置200のデジタル地図データベースに対して同様に適用可能である。
【0107】
図15に示すように、ナビゲーション装置200は、プロセッサ210、入力装置220、表示画面240を含む。入力装置220及び表示画面240は、例えば、タッチパネルスクリーンを介して、(直接入力、メニュー選択等により)情報を入力すること及び情報を表示することの両方を可能にするために、一体型入力表示装置に統合される。このようなスクリーンは、当業者には周知のものであるように、例えば、タッチ入力LCDスクリーンであってもよい。更に、ナビゲーション装置200は、例えば、音声入力/出力装置等の、更なる任意の入力装置220と更なる任意の出力装置260との少なくとも何れかを有していてもよい。
【0108】
ソフトウェア技術の当業者にとっては明らかであるように、熟練のプログラマは、本願で開示した教示に基づいて、適切なソフトウェア・コーディングを容易に作成することが可能である。本発明の実施形態は、当業者によって直ちに明らかになるように、特定用途向け集積回路を作成することによって、又は、従来の構成要素の回路を含む適切なネットワークを相互に接続することによって、実現されてもよい。
【0109】
本発明の実施形態は、媒体上/媒体内に格納された、本発明の実施形態のプロセスの何れかを実行するようにコンピュータをプログラミングするために使用され得る命令を含む記憶媒体(メディア)である、コンピュータ・プログラムを含む。記憶媒体は、フロッピー(登録商標)ディスク、光学ディスク、DVD、CD−ROM、マイクロドライブ、光磁気ディスク、ROM、RAM、EPROM、EEPROM、DRAM、VRAM、フラッシュメモリデバイス、磁気カード、光学カード、分子記憶ICを含むナノシステム、又は、命令及びデータの少なくとも何れかを格納するのに適した任意の種類のシステム若しくは装置を含む、任意の種類のディスクを含み得るが、それらに限定されない。
【0110】
本発明の実施形態は、コンピュータが読取可能な媒体を含み、当該媒体は地図データベースを含む。当該地図データベースは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルとを含む。当該複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも1つにより、地図データベースに格納されている。また、当業者には理解されるように、上述した本願の方法の実施形態に含まれる技術の何れもが、本明細書で説明した、コンピュータで読取可能な媒体の地図データベースに対して同様に適用可能である。
【0111】
本願の少なくとも1つの実施形態は、記憶媒体(コンピュータで読取可能な媒体又はメモリ等)に格納可能なデジタル地図アプリケーション・データベースを対象としている。当該データベースは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルとを含む。当該複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも1つにより、地図データベースに格納されている。また、当業者には理解されるように、上述した本願の方法の実施形態に含まれる技術の何れもが、本明細書で説明した、コンピュータで読取可能な媒体の地図データベースに対して同様に適用可能である。また、当業者には理解されるように、上述した本願の方法の実施形態に含まれる技術の何れもが、本明細書で説明したデジタル地図アプリケーション・データベースに対して同様に適用可能である。
【0112】
コンピュータで読取可能な媒体(メディア)の何れか1つに格納された場合、本発明の実施形態は、汎用/専用のコンピュータ又はマイクロプロセッサのハードウェアを制御するためのソフトウェアと、コンピュータ又はマイクロプロセッサが、本発明の実施形態の結果を利用するヒューマン・ユーザ又は他の機構と相互に作用できるようにするソフトウェアとを含む。そのようなソフトウェアは、デバイス・ドライバ、オペレーティング・システム、及びユーザ・アプリケーションを含んでもよいが、それらに限定されない。結局、コンピュータで読取可能なそのような媒体は、上述したように、本発明の実施形態を実行するソフトウェアを更に含む。
【0113】
汎用/専用のコンピュータ又はマイクロプロセッサのプログラミング又はソフトウェアには、本発明の実施形態の教示を実行するソフトウェア・モジュールが含まれる。本発明の実施形態は、当業者にとって明らかであるように、本開示の教示に従ってプログラミングされた、従来の汎用又は専用のデジタル・コンピュータ又はマイクロプロセッサを使用して、都合良く実行されてもよい。
【0114】
本発明の実施形態についての上述の説明は、例示及び説明を目的として提供されている。当該説明は、包括的であること、又は開示したままの形態に本発明の実施形態を限定することを意図したものではない。当業者には、多くの変更及び変形が明らかであろう。当該実施形態は、本発明の原理及びその現実的な応用について最良の説明を行うために選択及び説明されており、それにより、当該技術に精通した他者が、本発明の種々の実施形態に関する発明と、予期される特定の用途に適した種々の変更とを理解することが可能になる。本発明の範囲は以下の特許請求の範囲及びそれらの均等物によって規定されることが意図されている。
【0115】
本発明の種々の態様及び実施形態についてこれまでに説明してきたが、本発明の範囲は、本明細書で詳しく説明した特定の装置に限定されるのではなく、添付した特許請求の範囲の範囲に属する全ての構成とそれらに対する変更及び修正とを包含することにまで及ぶことが理解されよう。
【0116】
例えば、上述した目的地ビューは、目的地の住所の周囲の建物を表す画像を含む一方で、目的地の住所のみのレンダリングされた画像を含んだ目的地ビューは、やはりユーザが当該住所を特定してナビゲートするのに役立つ可能性があることが理解されよう。従って、目的地の住所及び近隣の建物を含むレンダリングされた画像を生成することが望ましい一方で、これは本発明に必須の特徴ではない。
【0117】
例えば、上記の詳細な説明において説明した実施形態ではGPSに言及しているが、ナビゲーション装置は、GPSの代わりとして(又は実際にはGPSとともに)任意の種類の位置感知技術を利用してもよいことに留意されたい。例えば、ナビゲーション装置は、欧州ガリレオシステム(European Galileo system)等の、他のグローバル・ナビゲーション衛星システムを利用してもよい。同様に、衛星ベースのものには限定されることはないが、装置が地理的位置を判定することを可能にする地上ベースのビーコン又は他の任意の種類のシステムを使用して、容易に機能してもよい。
【0118】
好適な本実施形態は、ソフトウェアを用いて特定の機能を実現する一方で、当該機能はハードウェア単独で(例えば、1つ以上のASIC(特定用途向け集積回路)を用いて)、又はハードウェア及びソフトウェアを実際に組み合わせて、同様に実行され得ることが、当業者には理解されよう。そのため、本発明の範囲は、ソフトウェアのみにおける実行に限定されるものと解釈されるべきではない。
【0119】
最後に、添付の特許請求の範囲は、本明細書で説明した特徴の特定の組み合わせを記述しているが、本発明の範囲は、以下で請求されている特定の組み合わせに限定されることはなく、当該特定の組み合わせが現時点で添付の特許請求の範囲に具体的に列挙されているか否かにかかわらず、本明細書で開示した特徴又は実施形態の組み合わせの何れをも包含することに及ぶことに留意されたい。

【特許請求の範囲】
【請求項1】
自動化された方法であって、
複数の投影点を作成するために、複数の既知の住所地点を、地図データベースの住所セグメント・ベクトルに投影するステップ(S1)と、
対応する複数の補間点を作成するために、前記複数の住所地点の住所について位置を補間するステップ(S2)と、
投影点と対応する補間点との距離が閾値距離を上回る場合に、前記住所セグメント・ベクトルを、複数の住所サブセグメント・ベクトルに分割するステップ(S3)と、
を含むことを特徴とする方法。
【請求項2】
対応する投影点と補間点との距離のうちで、相対的に最大の距離を判定するステップを更に含み、
前記分割は、前記判定された相対的に最大の距離が前記閾値距離を上回る場合に実行されること
を特徴とする請求項1に記載の方法。
【請求項3】
投影点と対応する補間点との全てのペアの距離の平均値を判定するステップを更に含み、
前記分割は、前記判定された距離の平均値が前記閾値距離を上回る場合に実行されること
を特徴とする請求項1に記載の方法。
【請求項4】
前記投影するステップ、前記補間するステップ、及び前記分割するステップは、
複数の住所サブセグメント・ベクトルの各々の範囲内における、複数の投影点と対応する複数の補間点との距離の平均値が、前記閾値距離よりも小さくなるように、又は、前記複数の住所サブセグメント・ベクトルの各々の範囲内における前記相対的に最大の距離よりも小さくなるように、
前記複数の住所サブセグメント・ベクトルへの複数の分割のために実行されること
を特徴とする請求項2又は3に記載の方法。
【請求項5】
前記閾値距離は、最大の数の、又は相対的に最大の数の補間住所のみが、投影点と対応する補間点のペアとの間の範囲内に収まるように設定されることを特徴とする請求項1に記載の方法。
【請求項6】
前記閾値距離は距離の関数であることを特徴とする請求項1乃至5の何れか1項に記載の方法。
【請求項7】
前記複数の住所サブセグメント・ベクトルを、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより、前記地図データベースに保存するステップを更に含むこと
を特徴とする請求項1乃至6の何れか1項に記載の方法。
【請求項8】
前記距離が前記住所セグメント・ベクトルについての前記閾値距離を上回らない場合に、更なる分割を行わずに当該住所セグメント・ベクトルを保存するステップを更に含むことを特徴とする請求項1又は6に記載の方法。
【請求項9】
前記判定された相対的に最大の距離が住所セグメント・ベクトル又は住所サブセグメント・ベクトルについての前記閾値距離を上回らない場合に、更なる分割を行わずに当該住所セグメント・ベクトル又は当該サブセグメント・ベクトルを保存するステップを更に含むことを特徴とする請求項2又は3に記載の方法。
【請求項10】
前記判定された距離の平均値が住所セグメント・ベクトル又は住所サブセグメント・ベクトルについての前記閾値距離を上回らない場合に、更なる分割を行わずに当該住所セグメント・ベクトル又は当該サブセグメント・ベクトルを保存するステップを更に含むことを特徴とする請求項4又は5に記載の方法。
【請求項11】
前記閾値距離は異なる複数の条件に対して調整可能であることを特徴とする請求項1乃至10の何れか1項に記載の方法。
【請求項12】
前記分割は、前記住所セグメント・ベクトル又は住所サブセグメント・ベクトルに沿う少なくとも1つの点であって、投影点と補間点との全てのペアの距離の平均値を低減する点において実行されること
を特徴とする請求項1乃至11の何れか1項に記載の方法。
【請求項13】
前記点は投影点であることを特徴とする請求項12に記載の方法。
【請求項14】
住所セグメント・ベクトルは、ストリートの一方の辺から成るストリート・セグメントに対応することを特徴とする請求項1乃至13の何れか1項に記載の方法。
【請求項15】
住所セグメント・ベクトルは、ストリートの両方の辺から成るストリート・セグメントに対応することを特徴とする請求項1乃至14の何れか1項に記載の方法。
【請求項16】
住所セグメント・ベクトル又は住所サブセグメント・ベクトルは、複数の前記投影点のうちの1つにおいて分割されることを特徴とする請求項1乃至15の何れか1項に記載の方法。
【請求項17】
メモリ(230)であって、
分割されていない複数の住所セグメント・ベクトルを格納しており、かつ、
住所セグメント・ベクトルが分割されたている場合に、請求項1乃至16の何れか1項に記載の方法における前記複数の住所サブセグメント・ベクトルを、対応する複数の住所セグメント・ベクトルに代えて、及び対応する複数の住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納していること
を特徴とするメモリ。
【請求項18】
請求項17に記載のメモリ(230)を含むナビゲーション装置(200)。
【請求項19】
コンピュータが読取可能な媒体であって、
複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含む地図データベースを含み、
前記複数の住所サブセグメント・ベクトルは、
前記住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、前記住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも1つにより、前記地図データベースに格納されていること
を特徴とする媒体。
【請求項20】
前記地図データベースは、
対応する投影点と補間点との距離のうちの相対的に最大の距離が前記閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納された、前記複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項19に記載の媒体。
【請求項21】
前記地図データベースは、
相対的に最大の距離が前記閾値距離以下になるまで更に分割された複数の住所サブセグメント・ベクトルであって、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納された、複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項19又は20に記載の媒体。
【請求項22】
前記地図データベースは、
投影点と対応する補間点との全てのペアの間で判定された距離の平均値が前記閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納された、前記複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項19に記載の媒体。
【請求項23】
前記地図データベースは、
前記住所サブセグメント・ベクトルの投影点と対応する補間点との距離の平均値が前記閾値距離よりも小さくなるまで更に分割された複数の住所サブセグメント・ベクトルであって、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納された、複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項19又は22に記載の媒体。
【請求項24】
前記閾値距離は、最大の数の、又は相対的に最大の数の補間住所のみが、投影点と対応する補間点のペアとの間の範囲内に収まるように設定されること
を特徴とする請求項19乃至24の何れか1項に記載の媒体。
【請求項25】
記憶媒体に格納可能な地図データベースであって、
複数の住所セグメント・ベクトルと、
複数の住所サブセグメント・ベクトルと、
を含み、
前記複数の住所サブセグメント・ベクトルは、
前記住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、前記住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも1つにより、前記地図データベースに格納されていること
を含むことを特徴とする地図データベース。
【請求項26】
前記地図データベースは、
対応する投影点と補間点との距離のうちの相対的に最大の距離が前記閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納された、前記複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項25に記載の地図データベース。
【請求項27】
前記地図データベースは、
相対的に最大の距離が前記閾値距離以下になるまで更に分割された複数の住所サブセグメント・ベクトルであって、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納された、複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項25又は26に記載の地図データベース。
【請求項28】
前記地図データベースは、
投影点と対応する補間点との全てのペアの間で判定された距離の平均値が前記閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納された、前記複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項25に記載の地図データベース。
【請求項29】
前記地図データベースは、
前記住所サブセグメント・ベクトルの投影点と対応する補間点との距離の平均値が前記閾値距離よりも小さくなるまで更に分割された複数の住所サブセグメント・ベクトルであって、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納された、複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項25又は28に記載の地図データベース。
【請求項30】
前記閾値距離は、最大の数の、又は相対的に最大の数の補間住所のみが、投影点と対応する補間点のペアとの間の範囲内に収まるように設定されること
を特徴とする請求項25乃至29の何れか1項に記載の地図データベース。
【請求項31】
地図データベースを格納したメモリ(230)と、
前記格納された地図データベースを用いて、入力又は選択された住所の位置を出力する出力装置(260)と、
を備える装置であって、
前記地図データベースは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含み、
前記複数の住所サブセグメント・ベクトルは、
前記住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、前記住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも1つにより、前記地図データベースに格納されていること
を特徴とする装置。
【請求項32】
前記出力装置は、ディスプレイ、文字出力装置、及び可聴出力装置のうちの少なくとも1つであることを特徴とする請求項31に記載の装置。
【請求項33】
前記地図データベースは、
対応する投影点と補間点との距離のうちの相対的に最大の距離が前記閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納された、前記複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項31又は32に記載の装置。
【請求項34】
前記地図データベースは、
相対的に最大の距離が前記閾値距離以下になるまで更に分割された複数の住所サブセグメント・ベクトルであって、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納された、複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項31乃至33の何れか1項に記載の装置。
【請求項35】
前記地図データベースは、
投影点と対応する補間点との全てのペアの間で判定された距離の平均値が前記閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納された、前記複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項31又は32に記載の装置。
【請求項36】
前記地図データベースは、
前記住所サブセグメント・ベクトルの投影点と対応する補間点との距離の平均値が前記閾値距離よりも小さくなるまで更に分割された複数の住所サブセグメント・ベクトルであって、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも1つにより格納された、複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項31、32又は35に記載の装置。
【請求項37】
前記閾値距離は、最大の数の、又は相対的に最大の数の補間住所のみが、投影点と対応する補間点のペアとの間の範囲内に収まるように設定されること
を特徴とする請求項31乃至36の何れか1項に記載の装置。
【請求項38】
前記装置は、ナビゲーション装置であり、
前記ナビゲーション装置は、
移動目的地の入力又は選択を促す入力装置(220)と、
前記入力又は選択された移動目的地への移動ルートを計算するプロセッサ(210)と、
を更に備え、
前記移動ルートの計算では、前記保存された地図データベースを利用し、
前記出力装置は、前記計算された移動ルートを出力するために使用可能であること
を特徴とする請求項31乃至37の何れか1項に記載の装置。
【請求項39】
ポータブルナビゲーション装置であることを特徴とする請求項38に記載のナビゲーション装置(200)。
【請求項40】
車両搭載型のナビゲーション装置であることを特徴とする請求項38又は39に記載のナビゲーション装置(200)。
【請求項41】
ユーザに所望の位置に対応する情報を提供するシステム(900)であって、
複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含む地図データベース(930)と、
前記所望の位置に関するクエリに応じて、アプリケーション・プログラムを使用して、前記地図データベースに含まれる住所セグメント・ベクトル又は住所サブセグメント・ベクトルに対応する補間された位置を検索するプロセッサ(914)と、
を備え、
前記複数の住所サブセグメント・ベクトルは、
前記住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、前記住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも1つにより、前記地図データベースに格納されていること
を特徴とするシステム。
【請求項42】
インターネットに基づくシステムから成ることを特徴とする請求項41に記載のシステム(900)。
【請求項43】
車両搭載型のナビゲーションシステムから成ることを特徴とする請求項41に記載のシステム(900)。
【請求項44】
ユーザに所望の位置に対応する情報を提供する、地理情報システム(GIS)に基づくアプリケーション・プログラムであって、
複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含む地図データベースを含み、
前記複数の住所サブセグメント・ベクトルは、
前記住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、前記住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも1つにより、前記地図データベースに格納されていること
を特徴とするアプリケーション・プログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図13】
image rotate


【公表番号】特表2012−511721(P2012−511721A)
【公表日】平成24年5月24日(2012.5.24)
【国際特許分類】
【出願番号】特願2011−540666(P2011−540666)
【出願日】平成20年12月10日(2008.12.10)
【国際出願番号】PCT/US2008/013544
【国際公開番号】WO2010/068187
【国際公開日】平成22年6月17日(2010.6.17)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.Bluetooth
2.GSM
【出願人】(507388889)テレ アトラス ノース アメリカ インコーポレイテッド (23)
【Fターム(参考)】