(57)【要約】方法、データベース、メモリ、コンピュータが読取可能な媒体、及びナビゲーション装置が開示される。少なくとも１つの実施形態において、本方法は、複数の投影点を作成するために、複数の既知の住所地点を、地図データベースの住所セグメント・ベクトルに投影するステップ（Ｓ１）と、対応する複数の補間点を作成するために、当該複数の住所地点の住所について位置を補間するステップ（Ｓ２）と、投影点と対応する補間点との距離が閾値距離を上回る場合に、当該住所セグメント・ベクトルを、複数の住所サブセグメント・ベクトルに分割するステップ（Ｓ３）とを含む。実施形態は、住所セグメント・ベクトルが分割された場合に、本方法における複数の住所サブセグメント・ベクトルを、対応する住所セグメント・ベクトルの代わりに、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納したデジタル地図アプリケーション・データベースを含むメモリ（２３０）と、当該メモリ（２３０）を含むナビゲーション装置（２００）と、複数の住所セグメント・ベクトル及び複数の住所サブセグメント・ベクトルを含むデジタル地図アプリケーション・データベースと、当該デジタル地図アプリケーション・データベースを含むコンピュータ可読媒体と、を含む。
2012511721.tif 000002
【特許請求の範囲】
【請求項１】
自動化された方法であって、
複数の投影点を作成するために、複数の既知の住所地点を、地図データベースの住所セグメント・ベクトルに投影するステップ（Ｓ１）と、
対応する複数の補間点を作成するために、前記複数の住所地点の住所について位置を補間するステップ（Ｓ２）と、
投影点と対応する補間点との距離が閾値距離を上回る場合に、前記住所セグメント・ベクトルを、複数の住所サブセグメント・ベクトルに分割するステップ（Ｓ３）と、
を含むことを特徴とする方法。
【請求項２】
対応する投影点と補間点との距離のうちで、相対的に最大の距離を判定するステップを更に含み、
前記分割は、前記判定された相対的に最大の距離が前記閾値距離を上回る場合に実行されること
を特徴とする請求項１に記載の方法。
【請求項３】
投影点と対応する補間点との全てのペアの距離の平均値を判定するステップを更に含み、
前記分割は、前記判定された距離の平均値が前記閾値距離を上回る場合に実行されること
を特徴とする請求項１に記載の方法。
【請求項４】
前記投影するステップ、前記補間するステップ、及び前記分割するステップは、
複数の住所サブセグメント・ベクトルの各々の範囲内における、複数の投影点と対応する複数の補間点との距離の平均値が、前記閾値距離よりも小さくなるように、又は、前記複数の住所サブセグメント・ベクトルの各々の範囲内における前記相対的に最大の距離よりも小さくなるように、
前記複数の住所サブセグメント・ベクトルへの複数の分割のために実行されること
を特徴とする請求項２又は３に記載の方法。
【請求項５】
前記閾値距離は、最大の数の、又は相対的に最大の数の補間住所のみが、投影点と対応する補間点のペアとの間の範囲内に収まるように設定されることを特徴とする請求項１に記載の方法。
【請求項６】
前記閾値距離は距離の関数であることを特徴とする請求項１乃至５の何れか１項に記載の方法。
【請求項７】
前記複数の住所サブセグメント・ベクトルを、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより、前記地図データベースに保存するステップを更に含むこと
を特徴とする請求項１乃至６の何れか１項に記載の方法。
【請求項８】
前記距離が前記住所セグメント・ベクトルについての前記閾値距離を上回らない場合に、更なる分割を行わずに当該住所セグメント・ベクトルを保存するステップを更に含むことを特徴とする請求項１又は６に記載の方法。
【請求項９】
前記判定された相対的に最大の距離が住所セグメント・ベクトル又は住所サブセグメント・ベクトルについての前記閾値距離を上回らない場合に、更なる分割を行わずに当該住所セグメント・ベクトル又は当該サブセグメント・ベクトルを保存するステップを更に含むことを特徴とする請求項２又は３に記載の方法。
【請求項１０】
前記判定された距離の平均値が住所セグメント・ベクトル又は住所サブセグメント・ベクトルについての前記閾値距離を上回らない場合に、更なる分割を行わずに当該住所セグメント・ベクトル又は当該サブセグメント・ベクトルを保存するステップを更に含むことを特徴とする請求項４又は５に記載の方法。
【請求項１１】
前記閾値距離は異なる複数の条件に対して調整可能であることを特徴とする請求項１乃至１０の何れか１項に記載の方法。
【請求項１２】
前記分割は、前記住所セグメント・ベクトル又は住所サブセグメント・ベクトルに沿う少なくとも１つの点であって、投影点と補間点との全てのペアの距離の平均値を低減する点において実行されること
を特徴とする請求項１乃至１１の何れか１項に記載の方法。
【請求項１３】
前記点は投影点であることを特徴とする請求項１２に記載の方法。
【請求項１４】
住所セグメント・ベクトルは、ストリートの一方の辺から成るストリート・セグメントに対応することを特徴とする請求項１乃至１３の何れか１項に記載の方法。
【請求項１５】
住所セグメント・ベクトルは、ストリートの両方の辺から成るストリート・セグメントに対応することを特徴とする請求項１乃至１４の何れか１項に記載の方法。
【請求項１６】
住所セグメント・ベクトル又は住所サブセグメント・ベクトルは、複数の前記投影点のうちの１つにおいて分割されることを特徴とする請求項１乃至１５の何れか１項に記載の方法。
【請求項１７】
メモリ（２３０）であって、
分割されていない複数の住所セグメント・ベクトルを格納しており、かつ、
住所セグメント・ベクトルが分割されたている場合に、請求項１乃至１６の何れか１項に記載の方法における前記複数の住所サブセグメント・ベクトルを、対応する複数の住所セグメント・ベクトルに代えて、及び対応する複数の住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納していること
を特徴とするメモリ。
【請求項１８】
請求項１７に記載のメモリ（２３０）を含むナビゲーション装置（２００）。
【請求項１９】
コンピュータが読取可能な媒体であって、
複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含む地図データベースを含み、
前記複数の住所サブセグメント・ベクトルは、
前記住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、前記住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも１つにより、前記地図データベースに格納されていること
を特徴とする媒体。
【請求項２０】
前記地図データベースは、
対応する投影点と補間点との距離のうちの相対的に最大の距離が前記閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納された、前記複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項１９に記載の媒体。
【請求項２１】
前記地図データベースは、
相対的に最大の距離が前記閾値距離以下になるまで更に分割された複数の住所サブセグメント・ベクトルであって、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納された、複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項１９又は２０に記載の媒体。
【請求項２２】
前記地図データベースは、
投影点と対応する補間点との全てのペアの間で判定された距離の平均値が前記閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納された、前記複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項１９に記載の媒体。
【請求項２３】
前記地図データベースは、
前記住所サブセグメント・ベクトルの投影点と対応する補間点との距離の平均値が前記閾値距離よりも小さくなるまで更に分割された複数の住所サブセグメント・ベクトルであって、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納された、複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項１９又は２２に記載の媒体。
【請求項２４】
前記閾値距離は、最大の数の、又は相対的に最大の数の補間住所のみが、投影点と対応する補間点のペアとの間の範囲内に収まるように設定されること
を特徴とする請求項１９乃至２４の何れか１項に記載の媒体。
【請求項２５】
記憶媒体に格納可能な地図データベースであって、
複数の住所セグメント・ベクトルと、
複数の住所サブセグメント・ベクトルと、
を含み、
前記複数の住所サブセグメント・ベクトルは、
前記住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、前記住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも１つにより、前記地図データベースに格納されていること
を含むことを特徴とする地図データベース。
【請求項２６】
前記地図データベースは、
対応する投影点と補間点との距離のうちの相対的に最大の距離が前記閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納された、前記複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項２５に記載の地図データベース。
【請求項２７】
前記地図データベースは、
相対的に最大の距離が前記閾値距離以下になるまで更に分割された複数の住所サブセグメント・ベクトルであって、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納された、複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項２５又は２６に記載の地図データベース。
【請求項２８】
前記地図データベースは、
投影点と対応する補間点との全てのペアの間で判定された距離の平均値が前記閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納された、前記複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項２５に記載の地図データベース。
【請求項２９】
前記地図データベースは、
前記住所サブセグメント・ベクトルの投影点と対応する補間点との距離の平均値が前記閾値距離よりも小さくなるまで更に分割された複数の住所サブセグメント・ベクトルであって、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納された、複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項２５又は２８に記載の地図データベース。
【請求項３０】
前記閾値距離は、最大の数の、又は相対的に最大の数の補間住所のみが、投影点と対応する補間点のペアとの間の範囲内に収まるように設定されること
を特徴とする請求項２５乃至２９の何れか１項に記載の地図データベース。
【請求項３１】
地図データベースを格納したメモリ（２３０）と、
前記格納された地図データベースを用いて、入力又は選択された住所の位置を出力する出力装置（２６０）と、
を備える装置であって、
前記地図データベースは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含み、
前記複数の住所サブセグメント・ベクトルは、
前記住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、前記住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも１つにより、前記地図データベースに格納されていること
を特徴とする装置。
【請求項３２】
前記出力装置は、ディスプレイ、文字出力装置、及び可聴出力装置のうちの少なくとも１つであることを特徴とする請求項３１に記載の装置。
【請求項３３】
前記地図データベースは、
対応する投影点と補間点との距離のうちの相対的に最大の距離が前記閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納された、前記複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項３１又は３２に記載の装置。
【請求項３４】
前記地図データベースは、
相対的に最大の距離が前記閾値距離以下になるまで更に分割された複数の住所サブセグメント・ベクトルであって、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納された、複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項３１乃至３３の何れか１項に記載の装置。
【請求項３５】
前記地図データベースは、
投影点と対応する補間点との全てのペアの間で判定された距離の平均値が前記閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納された、前記複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項３１又は３２に記載の装置。
【請求項３６】
前記地図データベースは、
前記住所サブセグメント・ベクトルの投影点と対応する補間点との距離の平均値が前記閾値距離よりも小さくなるまで更に分割された複数の住所サブセグメント・ベクトルであって、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより格納された、複数の住所サブセグメント・ベクトルを含むこと
を特徴とする請求項３１、３２又は３５に記載の装置。
【請求項３７】
前記閾値距離は、最大の数の、又は相対的に最大の数の補間住所のみが、投影点と対応する補間点のペアとの間の範囲内に収まるように設定されること
を特徴とする請求項３１乃至３６の何れか１項に記載の装置。
【請求項３８】
前記装置は、ナビゲーション装置であり、
前記ナビゲーション装置は、
移動目的地の入力又は選択を促す入力装置（２２０）と、
前記入力又は選択された移動目的地への移動ルートを計算するプロセッサ（２１０）と、
を更に備え、
前記移動ルートの計算では、前記保存された地図データベースを利用し、
前記出力装置は、前記計算された移動ルートを出力するために使用可能であること
を特徴とする請求項３１乃至３７の何れか１項に記載の装置。
【請求項３９】
ポータブルナビゲーション装置であることを特徴とする請求項３８に記載のナビゲーション装置（２００）。
【請求項４０】
車両搭載型のナビゲーション装置であることを特徴とする請求項３８又は３９に記載のナビゲーション装置（２００）。
【請求項４１】
ユーザに所望の位置に対応する情報を提供するシステム（９００）であって、
複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含む地図データベース（９３０）と、
前記所望の位置に関するクエリに応じて、アプリケーション・プログラムを使用して、前記地図データベースに含まれる住所セグメント・ベクトル又は住所サブセグメント・ベクトルに対応する補間された位置を検索するプロセッサ（９１４）と、
を備え、
前記複数の住所サブセグメント・ベクトルは、
前記住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、前記住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも１つにより、前記地図データベースに格納されていること
を特徴とするシステム。
【請求項４２】
インターネットに基づくシステムから成ることを特徴とする請求項４１に記載のシステム（９００）。
【請求項４３】
車両搭載型のナビゲーションシステムから成ることを特徴とする請求項４１に記載のシステム（９００）。
【請求項４４】
ユーザに所望の位置に対応する情報を提供する、地理情報システム（ＧＩＳ）に基づくアプリケーション・プログラムであって、
複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含む地図データベースを含み、
前記複数の住所サブセグメント・ベクトルは、
前記住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、前記住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも１つにより、前記地図データベースに格納されていること
を特徴とするアプリケーション・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、概して、特定の住所の位置を判定するための情報を有する地図データベース及び地図データベース形成方法に関するものであり、より具体的には、ユーザが所望する場所の位置又は所在地を正確に判定するために使用されるデータ構造を有する地図データベースに関するものである。
【背景技術】
【０００２】
近年、消費者がデジタル地図上で場所を特定できるように、種々の装置及びシステムが消費者に提供されている。「場所（place）」という用語は、本発明の実施形態の説明全体を通して使用されている一般的な用語である。「場所」という用語は、ストリート住所（street addresses）、事業及びランドマーク等の、ストリート住所に位置する建物、及び、ショッピングモールやビジネスパーク等の、多くのストリート住所に位置する施設を含む。消費者により使用される種々の装置及びシステムは、運転者がストリートや道路（roads）をナビゲートできるようにする車両搭載型のナビゲーションシステムと、パーソナルデジタルアシスタント（「ＰＤＡ」）、パーソナルナビゲーション装置（ＰＮＤ：personal navigation device）、及び携帯電話又はそれと同一機能を実行できる他の種類の移動装置等の、ハンドヘルド装置と、ユーザが所望の場所を示す地図を生成できるデスクトップ・アプリケーション及びインターネット・アプリケーションと、の形式を取る。上記の種類及び他の種類の装置及びシステムの全てに共通する態様は、地理的特徴（geographic features）、ベクトル及び属性の地図データベース、並びにユーザ入力に応じて当該地図データベースにアクセスし、操作し、ナビゲートするソフトウェアである。
【０００３】
基本的に、上記の装置及びシステムの全てにおいて、ユーザは所望の場所を入力でき、その場所の位置が返される。一般に、ユーザは、レストラン等の事業の名称、Golden Gate Bridge等の目的地のランドマーク、又は住所等を入力する。その後、装置／システムは、要求された場所の位置を判定して返す。当該位置は、地図表示上に示されてもよく、既知の方法で当該位置への運転指示を計算及び表示するために使用されてもよく、あるいは他の方法で使用されてもよい。
【０００４】
地図データベースは、ストリート上の家屋及び建物の位置に関する情報を提供する。地図データベースの開発者は、所与のストリート又はストリート・セグメント（住所セグメント）についての所与の住所範囲にわたる住所データを、地図データベースに収録する。当該住所範囲には、始点の家屋番号（house number）及び位置、終点の家屋番号及び位置、並びにオプションでいくつかの中間の家屋番号及び位置とともに、ストリート・セグメントの所与の辺に対応する建物番号（building number）又は家屋番号の集合が含まれる。
【０００５】
ユーザによる所望の目的地の入力又は選択に応じて所望の場所の位置を特定するために、装置又はシステムのソフトウェアは、最初に当該所望の場所のアドレスを判定し、次に所望の選択又は入力されたアドレスを含むアドレス範囲を有するストリート・セグメントの位置を特定し、その後、当該アドレス範囲内で補間を実行して、当該所望の場所の位置を推定する。しかし、多くの場合、補間アルゴリズムには、所与のストリート・ブロックに沿った建物番号又は家屋番号の分布のばらつきに起因した問題がある。例えば、ブロックの始点又は中間に公園が存在する場合、家屋がブロックに沿って不均一に分布している場合、及び、住所範囲の端点に存在する建物がストリートの交差点に正確に位置していない場合のうち、少なくとも何れかがあり得る。
【０００６】
理想的には、住所範囲の端点に存在する建物番号及び家屋番号の少なくとも何れかが、実際の建物の住所を表し、それにより中間の家屋番号を補間する際の誤差が減少する。しかし、これは必ずしも事実ではない。いくつかの地図データベースは、端点に存在する潜在的な建物番号又は家屋番号を使用した住所範囲を用いてモデル化されており、このことは、建物番号又は家屋番号を正確に補間するという問題を悪影響を及ぼす。例えば、地図データベースは、米国郵政公社により割り当てられた潜在的な建物番号又は家屋番号を使用して住所範囲をモデル化してもよい。更に、一例としては、ストリートが１００個の住所番号から成るブロックに分けられるNew York Cityの商業地区では、ブロックの辺に沿った複数の建物番号又は家屋番号が、住所範囲全体を表すことはほとんどなく、一端又は他端において当該範囲を完結させるには不十分である場合が多い。
【０００７】
上記の方法を使用する補間は、格納されたストリート・セグメント又は範囲の長さの５０％以上の誤差を有する場合がある。これらの補間誤差は、例えば数十メートル又は数百メートルの誤差になることがあり、それにより、所望の目的地の補間位置へナビゲートしたユーザにとって、所望の場所が視界の範囲外になる可能性がある。
【０００８】
図１に示すように、既知のデジタル地図データベースは、当該既知のデジタル地図データベースにおいて一般に住所セグメント・ベクトルとして表される、複数の住所セグメント又は住所セグメントについての複数の辺（複数の住所セグメント辺）を含む。一般に住所セグメント・ベクトルとして表されるそのような住所セグメント又は住所セグメント辺は、一般に、（場合によっては、例えば以下に説明する形状点ＳＰを使用して図１に示すような形状を有する）線により接続された、始点及び終点を有する特徴として、地図データベースを含むメモリに格納される。一般に、そのような住所セグメント・ベクトルは、住所セグメントの一方の辺である住所セグメント辺を表す（この場合、住所セグメントは、名称により識別可能であり、且つ、既知の住所を含む移動経路（travel route）であって、道路、ストリート、幹線道路等を含むがそれらに限定されない任意の移動経路を意味すると理解される）。
【０００９】
一例としては、図１の＃２等の始点及び図１の＃９８等の終点は、一般に、住所セグメント又はストリートの辺の、始点及び終点の家屋番号又は建物番号を表す。住所範囲は、住所セグメント又は住所セグメント辺についての全ての住所を表すために使用され、通常は始点の家屋番号から終点の家屋番号（例えば、図１の＃２〜＃９８）にわたり、場合によっては何らかのパリティ（parity）を有する（住所セグメントの一方の辺について偶数の番号のみを含み、且つ、住所セグメントの他方の辺について奇数の番号のみを含むか、あるいは、住所セグメントの両方の辺が表される場合は両方の番号を含む）。
【００１０】
一般に、住所セグメント又は住所セグメント辺についての住所範囲は、住所セグメント・ベクトルと共にデジタル地図データベースに格納され、既知の方法でナビゲーションに使用され得るとともに、移動目的地（travel destinations）の位置を既知の方法で特定する及び他の種類の地図技術において使用され得る。一般に、住所セグメント・ベクトルは、属性情報と共にデジタル地図データベースに格納され、当該属性情報は、例えば、住所セグメントにおける速度制限、右左折制限又は一方通行に関する何らかの指示、国勢調査（census）コード、郵便番号、ストリート名等を含むが、それらに限定されない
。
【００１１】
典型的には、中間の家屋番号の（住所範囲の始点と終点との間の）位置は、線形補間を使用して当該住所範囲内において既知の方法で計算される。例えば図２に示すように、典型的には、家屋＃５０は、線形補間によって図２の住所セグメントの形状に沿って、住所＃２と住所＃９８との中間に存在すると判定される。そのような補間は、位置、移動目的地、場所等を判定するためにデジタル地図データベースを利用する、ジオコーディング（geocoding）及びナビゲーション・アプリケーションにおいて一般に使用される。
【００１２】
補間誤差を生じる可能性のある線形補間法を使用することには、いくつかの問題がある。第１に、一部のデジタル地図データベースは、住所セグメントの始点及び終点についての実際の家屋番号を使用しない。代わりに、それらのデータベースは、デジタル地図データベースの構築後に建設される可能性のある建物の位置の特定に対応するために、又は郵便配達を容易にするために、潜在的な郵便住所（米国郵政公社によって当該住所セグメントに対して確保された住所）を使用する。例えば図１及び図２に示すように、セグメントにおける潜在的な郵便住所の範囲が＃２〜＃９８である場合、道路の湾曲に従った線形補間によって、当該セグメントの中間点付近に住所＃５０が位置付けられる。しかし、例えば図３に示すように、端点の実際の住所が＃２及び＃６０である場合、図３の点＃５０ｂの住所が正確に補間されるのではなく、＃２〜＃９８である潜在的な郵便住所範囲を用いて線形補間が使用されて、図３に示すように、当該セグメントの湾曲に従って住所が点＃５０ａに位置付けられる。従って、ナビゲーション及びジオコーディング・アプリケーションの少なくとも何れかにおいて誤差が生じることになる。
【００１３】
更に、図４に示すように、実際には、一般に、住所はセグメント上に線形に分布していない。図４は、ブロックの中央に大きな公園又は空き地１４０を含む写真の一例を示す。大きな公園又は空き地１４０に起因して、住所番号が住所セグメントに沿って不均一に分布する場合がある。
【００１４】
一部のデジタル地図データベースは、セグメントの始点及び終点として、潜在的な郵便番号ではなく、実際の住所番号を使用して構築されている。これにより中間点の補間が改善される場合がある一方で、住所がセグメントに沿って均一に分布していない場合、例えば、ブロック上に公園、駐車場又は共同住宅が存在する場合には、線形補間は依然として大きな誤差を示すことがある。また、物理的な住所が住所セグメントの一端に集中すると仮定する対数補間等の、非線形補間法が使用されてもよい。しかし、中間点の補間のために使用されたアルゴリズムに従って住所が容易に割り当てられない場合には、この方法でも失敗する。
【００１５】
更に他のデジタル地図データベースは、実際の位置に従って住所セグメントに追加された一部又は全ての個別の（点）住所を用いて構築されている。この一例は、２００６年２月８日に出願され、且つ、本明細書でその全ての内容を援用する、Michael Geilichによる特許文献１において説明されている。これは、探している住所地点を直接的に見つけるために、又は、誤差を最小化する最短補間を少なくとも可能にするために、十分な情報を提供する一方で、住所から位置を判定するために使用されるアルゴリズムを大幅に変更することになり、場合によっては装置において住所地点データを格納するための記憶容量のコストが高くなる。そのような異なる新規のロジックは、この改善された新規な地図を使用する装置に対して、かなりのソフトウェア・アップデートを必要とする。旧式のユニットにおいては、そのようなソフトウェアの変更を導入することが困難であるか、高コストであるか、又は、不可能である可能性がある。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】米国特許出願第１１／３５１，１５６号，“MAP DATABASE HAVING ADDRESS POINTS FOR DETERMINING DESTINATIONS（目的地を決定するための住所地点を有する地図データベース）”
【発明の概要】
【課題を解決するための手段】
【００１７】
住所セグメント・ベクトル（住所セグメント）上に投影された実際の既知の住所地点を含み得る投影点を使用することによって、住所セグメント・ベクトルは、投影点と当該投影点の補間位置との間の距離が閾値距離を上回る場合に、修正（modified）又は分割（segmented）される。そのようにして、住所セグメントを、地図データベースにおいて住所サブセグメントに置き換えることによって、ジオコーディング及びナビゲーション等のアプリケーション自体において基本となる補間アルゴリズムに対する変更を全く必要とせずに、それらのアプリケーションについての線形補間アルゴリズムが改善される。改善された地図データベースが、住所セグメント・ベクトルを含み、且つ、必要に応じて住所サブセグメント・ベクトルを含むことに起因して、線形補間アルゴリズムが改善される。
【００１８】
そのため、本発明の実施形態においては、例えばジオコーディングやナビゲーション等におけるデータの既存のアプリケーションにおける補間アルゴリズムを変更する必要なく、道路の住所セグメント又は住所セグメント辺に沿って、実際の家屋番号の分布が変化する状況に対応可能である。更に、以下の実施形態の説明から明らかになるように、住所サブセグメント・ベクトルが、必要に応じて（例えば投影点と補間点との間の閾値距離を上回ることに基づいて）対応する住所セグメント・ベクトルの代わりに地図データベースに格納されるため、多くの追加の記憶容量を必要としない。これは、記憶容量が制限されるポータブルナビゲーション装置（ＰＮＤ：portable navigation device）において特に有利である。従って、本発明の実施形態において、住所セグメント・ベクトルを住所サブセグメント・ベクトルに分割することにより、例えばジオコーディングやナビゲーションを含むがそれらに限定されないアプリケーションについて、補間処理が改善されるために、住所範囲データがさらに改善される。
【００１９】
本発明の少なくとも１つの実施形態は、複数の投影点を作成するために、複数の既知の住所地点を、地図データベースの住所セグメント・ベクトルに投影するステップと、対応する複数の補間点を作成するために、当該複数の住所地点の住所について位置を補間するステップと、投影点と対応する補間点との距離が閾値距離を上回る場合に、当該住所セグメント・ベクトルを、複数の住所サブセグメント・ベクトルに分割するステップと、を含むことを特徴とする方法を対象としている。
【００２０】
本発明の別の実施形態は、分割されていない複数の住所セグメント・ベクトルを格納しており、かつ、住所セグメント・ベクトルが分割されている場合に、上記で対処した少なくとも１つの実施形態の方法における当該複数の住所サブセグメント・ベクトルを、対応する複数の住所セグメント・ベクトルに代えて、又は対応する複数の住所セグメント・ベクトルとともに、格納していることを特徴とするメモリを対象としている。
【００２１】
本発明の少なくとも１つの実施形態は、記憶媒体に格納可能な地図データベースを対象としている。当該地図データベースは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含み、当該複数の住所サブセグメント・ベクトルは、当該住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、当該住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも１つにより、当該地図データベースに格納されていることを特徴とする。
【００２２】
本発明の少なくとも１つの実施形態は、上記で対処した少なくとも１つの実施形態の地図データベースを含むコンピュータが読取可能な媒体を対象としている。
【００２３】
本発明の別の実施形態は、地図データベースを保存したメモリと、保存された地図データベースを用いて、入力又は選択された住所の位置を表示するディスプレイと、を備える装置を対象としており、当該地図データベースは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含み、当該複数の住所サブセグメント・ベクトルは、当該住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、当該住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも１つにより、当該地図データベースに格納されていることを特徴とする。少なくとも１つの他の実施形態において、当該装置は、ナビゲーション装置であり、当該ナビゲーション装置は、移動目的地の入力又は選択を促す入力装置と、入力又は選択された移動目的地への移動ルートを計算するプロセッサと、を更に備え、移動ルートの計算では、保存された地図データベースを利用し、ディスプレイは、計算された移動ルートを表示するために使用可能であること、を特徴とする。
【００２４】
本発明の別の実施形態は、ユーザに所望の位置に対応する情報を提供するシステムを対象としている。当該システムは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含む地図データベースと、当該所望の位置に関するクエリに応じて、アプリケーション・プログラムを使用して、当該地図データベースに含まれる住所セグメント・ベクトル又は住所サブセグメント・ベクトルに対応する補間された位置を検索するプロセッサと、を備え、当該複数の住所サブセグメント・ベクトルは、当該住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、当該住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも１つにより、当該地図データベースに格納されていることを特徴とする。
【００２５】
最後に、少なくとも１つの他の実施形態は、ユーザに所望の位置に対応する情報を提供する、地理情報システム（ＧＩＳ）に基づくアプリケーション・プログラムを対象としている。当該プログラムは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルと、を含む地図データベースを含み、当該複数の住所サブセグメント・ベクトルは、当該住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、当該住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも１つにより、当該地図データベースに格納されていることを特徴とする。
【００２６】
これらの実施形態の利点について、以下で詳細に説明するとともに、これらの実施形態のそれぞれの更なる詳細及び特徴について、添付の従属請求項、及び以下の詳細な説明における何れかの部分において明らかにする。
【図面の簡単な説明】
【００２７】
以下では、添付の図面を参照し、図示される例を用いて、本発明の実施形態の教示の種々の態様、及びそれら教示を実現する構成について説明する。
【００２８】
【図１】ストリート・セグメント辺のデジタル地図表現の一例を示す図である。
【図２】中間の家屋番号を見つけるために使用される線形補間の一例を示す図である。
【図３】実際の住所範囲及び潜在的な住所範囲に対する補間の差異を含む、補間の一例を示す図である。
【図４】ストリート・セグメントに沿って非線形に分布した住所に存在する実際の家屋を示す写真の一例を示す図である。
【図５】建物、一区画等を表す実際の住所地点を示す写真の一例を示す図である。
【図６】実際の住所地点、投影点及び補間点を示す写真の一例を示す図である。
【図７】本発明の方法の一実施形態を示す図である。
【図８】ストリート・セグメント上に投影された住所地点の一実施形態を示す図である。
【図９】投影点、補間点及びそれらの間の距離の一実施形態を示す図である。
【図１０】既知の補間技術（１０Ａ）及びストリートの分割後における改善された補間（１０Ｂ）の実施形態を示す図である。
【図１１】パーソナルナビゲーション装置（ＰＮＤ）等のハンドヘルド装置において使用される一実施形態を示す図である。
【図１２】全地球測位システム（ＧＰＳ）等の車両搭載型のナビゲーションシステムにおいて使用される一実施形態を示す図である。
【図１３】航空写真上に重ね合わされた住所地点の一実施形態を示す図である。
【図１４】地図データベース９３０の実施形態が地図データベース・アプリケーション９７０と分離していることを示す図である。
【図１５】本発明の一実施形態のナビゲーション装置を提供するように構成された電子構成要素を示す図である。
【図１６】ナビゲーション装置が無線通信チャネルを介して情報を受信し得る一実施形態を示す図である。
【発明を実施するための形態】
【００２９】
本発明の一実施形態は、ジオコーディング及びナビゲーションを含むがそれらに限定されないアプリケーションにおける補間を改善するために有用であると考えられる場合に、（一般にストリート・セグメントとして知られている）住所セグメント・ベクトルにアルゴリズムを適用して、当該住所セグメント・ベクトルを分割（セグメント化）することに関するものである。そのような住所セグメント・ベクトル又はストリート・セグメントは、始点及び終点を有する道路の幾何学的配置（road geometry）の一部分を含み、一般に、始点及び終点は、他のストリート又は地物（features）との交点によって定義される。一般に、ストリート・セグメントは２つの辺を有し、各辺は、通常、独自の始点及び終点を有し、且つ、独自の住所範囲を有する。当該範囲は、ストリート・セグメントの特定の辺において見つけられ得る可能性のある複数の住所を表す。尚、ストリート・セグメントの始点及び終点は、他の地物との交点によってのみ定義される必要はなく、住所範囲内の幾何学的配置の任意の複数のセクション（section）として更に定義されてもよい。
【００３０】
更に、本発明の実施形態の態様は、ストリートの一方の辺を対象としたストリート・セグメントに限定されず、ストリート・セグメントの両方の辺が別々に考慮されないストリート・セグメントに対しても適用可能であってもよい。そのような例において、本発明の実施形態のアルゴリズムは、ストリート・セグメントの両方の辺に同時に適用されてもよい。他の変形例において、本発明の実施形態のアルゴリズムは、住所を割り当てられていないストリート・セグメント又はストリート・セグメント辺に適用されてもよい。その場合、最初に、道路名及び住所範囲の少なくとも何れかをストリート・セグメントに割り当てるための技術が使用されてもよく、その後、当該ストリート・セグメントは、例えば本発明の実施形態のアルゴリズムに基づく分割のために検証されてもよい。
【００３１】
デジタル地図データベースは、住所セグメント・ベクトル又はストリート・セグメントを含むことが知られており、住所セグメント・ベクトル又はストリート・セグメントは、始点及び終点、ストリート名及び他の種類の属性、並びに、当該セグメント上に割り当てられた住所を表す住所範囲を有する。そのようなデジタル地図データベース（地図データベース）は、（例えば、ナビゲーション装置の一体型入力表示装置を介して選択又は入力された）所望の移動目的地等の場所の位置を特定する場合に、例えばジオコーディング、ＧＩＳ及びナビゲーション技術において使用される。一般に、デジタル地図データベース（例えば、デジタル地図データベースのベンダにより通常は保守され、且つ、本明細書中でソース・デジタル地図データベースと呼ばれるデジタル地図データベース）は、中央サーバに格納可能であり（且つ、例えばジオコーディング・アプリケーションの場合は直接アクセス可能であり）、その簡易バージョン（本明細書中でデジタル地図アプリケーション・データベースとして参照される）は、ジオコーディング装置、車両搭載型のナビゲーション装置、パーソナルナビゲーション装置、及び、携帯電話、ＰＤＡ等を含むがそれらに限定されないナビゲーション機能を有する他の何らかの装置、のうちの少なくとも１つを含むがそれらに限定されない装置のメモリにダウンロード若しくは転送可能であり、並びに／又は、メモリ若しくは何らかの種類のデジタル媒体に格納可能である。そのようなソース・デジタル地図データベースは、住所セグメント・ベクトル（及び、以下に説明する住所サブセグメント・ベクトルの少なくとも何れか）を含み得るとともに、当該住所セグメント・ベクトル（及び住所サブセグメント・ベクトルの少なくとも何れか）は、格納された当該住所セグメント・ベクトル（及び住所サブセグメント・ベクトルの少なくとも何れか）に割り当てられた多くの種類の属性を含む。一般に、デジタル地図アプリケーション・データベースは、そのようなソース・デジタル地図データベースから形成され、格納された住所セグメント・ベクトル（及び住所サブセグメント・ベクトルの少なくとも何れか）に割り当てられた、相対的に少ない種類の属性を有する住所セグメント・ベクトル（及び住所サブセグメント・ベクトルの少なくとも何れか）を含む。ソース・デジタル地図データベースからそのようなデジタル地図アプリケーション・データベースを形成すること、及び、当該デジタル地図アプリケーション・データベースを形成するためにソース・デジタル地図データベースの一部分をコピーすること、の少なくとも何れかを目的とした技術については、当業者には既知であり、簡潔にするために本明細書中では説明しない。
【００３２】
一般に、そのようなデジタル地図アプリケーション・データベースは、パーソナルナビゲーション装置、又は、ジオコーディング及びナビゲーション機能の少なくとも何れかと、マッピング機能との少なくとも何れかを有する他の任意の装置にもダウンロード可能である。当該装置は、例えばインターネット又はモバイルネットワーク接続を介してサーバから新たなデジタル地図アプリケーション・データベースに定期的に（例えば、新たな情報が受信される数ヶ月毎に）アクセスしてダウンロード又はコピーすることによってダウンロード可能であり、あるいは、車両搭載型のナビゲーション装置の場合、そのようなデジタル地図アプリケーション・データベースは、例えばＣＤ−ＲＯＭに格納された新たな更新済のデジタル地図アプリケーション・データベースによってダウンロード可能である。ここで、ＣＤ−ＲＯＭは、車両の車両搭載型のナビゲーション装置のメモリに格納されたデジタル地図アプリケーション・データベースを更新するために、当該車両搭載型のナビゲーション装置に入力可能である。そのような更新技術は、上述の技術に限定されず、デジタル地図アプリケーション・データベースを更新する任意の技術も含み得る。そのような更新技術については当業者には既知であり、簡潔にするために本明細書中では説明しない。
【００３３】
そのような既知のソース・デジタル地図データベースの全てにおいて、各ストリート・セグメント（デジタル地図データベースの住所セグメント・ベクトル）について、１つ以上の既知の住所地点の集合が存在する（尚、ソース・デジタル地図データベースは、既知の住所地点を含む一方で、デジタル地図アプリケーション・データベースは、一般にそれらを含まないが、記憶容量の制約により可能ならば既知の住所地点を含み得る）。例えば図５に示すように、そのような既知の住所地点＃１６８−１７２、＃１８０及び＃１８４は、既知の地理的位置と、ストリート・セグメント又は住所セグメント・ベクトルに沿う当該位置に対応する１つ（＃１８０及び＃１８４）又は複数（＃１６８−１７２）の住所番号又は住所とを有する。住所地点は、物理的構造、一区画（parcel）又は他の住所位置の、位置及び番号を表してもよく、建物、一区画等の実際の位置であることが既知である固定点である。これらは、例えば病院及び警察署等の、対象とする緊急地点の正確な位置、地図データベース内に自身の事業の正確な位置を配置するために航空写真の費用を支払った事業（例えば、チェーン展開しているレストラン等）の場所、税地図や境界線地図等から取得された正確な住所位置等を含み得る。いずれの場合も、そのような住所地点は、物理的構造や一区画等の、実際の位置及び番号を表す。そのような既知の住所地点は、正確な位置を提供する点で非常に価値があるが、（特にデジタル地図アプリケーション・データベースに）あまりに多くの住所地点が含まれていると、パーソナルナビゲーション装置、及び、携帯電話やＰＤＡ等のナビゲーション機能を有する他の何らかの小型／ポータブル型の装置の少なくとも何れか等の、特に、記憶容量が少ない装置の場合に、メモリの記憶容量の問題が生じる。その上、大部分の既存のアプリケーションは、それら既知の住所地点を使用するための特別なロジックを有さない。
【００３４】
図６は、仮想システム上のアプリケーションにおいて使用される一実施形態を示す。当該アプリケーションは、ＰＤＡ、携帯電話又はナビゲーション装置等のハンドヘルド装置、あるいはコンピュータ又はラップトップにおいて使用されてもよく、あるいはインターネットを介して使用されてもよい。探索の一例としては、仮想地図アプリケーションを使用するユーザによって、156 Dartmouth College Highway, Lebanon New Hampshireに対して実行される。現時点で、当該アプリケーションは、補間点であるドットＧを含むバブル内に地図上の住所の位置を表示している。しかし、実際の住所は地点Ａに位置する。一方、本発明の実施形態は、住所地点Ａ、投影点Ｅ、及び、投影点Ｅと補間点Ｇとの間の距離を使用して、それらの間の距離（実際には２６３ｍ）が閾値距離を上回るかを判定することができる。閾値距離を上回る場合、本発明の実施形態は、住所セグメント・ベクトルの分割処理を使用して、明らかに図６のバブルＧに存在しない建物又は当該建物が位置する敷地についての、更に正確な位置を見つけることが可能である。この住所地点Ａはソース地図データベースに格納される。その後、アプリケーション地図の新しいバージョンにおいて分割処理が実行され、当該バージョンは、種々の装置のアプリケーションにおいて使用されるように、それら装置に配信されてもよい。このように、本発明の実施形態は、以下に説明するように、より正確な位置決め情報（positioning information）を提供できる。
【００３５】
本発明の少なくとも１つの実施形態は、ソース・デジタル地図データベースのこれら既知の住所地点（あるいは、そのような既知の住所地点がデジタル地図アプリケーション・データベース内に存在する場合は、当該デジタル地図アプリケーション・データベースの既知の住所地点）を有効に利用する方法を対象とする。本発明がソース・デジタル地図データベースのこれら既知の住所地点を利用する実施形態において、その結果は、デジタル地図アプリケーション・データベースに変換され、且つ、本発明の実施形態を有効に使用可能なアプリケーションを実行する装置に配信されてもよい。図７に示すように、本発明の一実施形態において、方法は、複数の投影点を作成するために、複数の既知の住所地点を、地図データベースの住所セグメント・ベクトルに投影するステップ（Ｓ１）と、対応する複数の補間点を作成するために、当該複数の住所地点について位置を補間するステップ（Ｓ２）と、投影点と対応する補間点との間の距離が閾値距離を上回る場合に、当該住所セグメント・ベクトルを、複数の住所サブセグメント・ベクトルに分割するステップ（Ｓ３）とを含む。以下では、図８〜図１０に関して、そのような一実施形態の一例を説明する。
【００３６】
例えば図８に示すように、所与のストリート・セグメント又はストリート・セグメント辺について、それに対応する住所地点が判定される。例えば図８のElm Streetは、＃２〜＃９８の範囲の住所を有する第１の辺１６０と、＃１〜＃９９の範囲の住所を有する第２の辺１６２とを有する。デジタル地図データベース内には、（範囲＃２〜＃９８に含まれるため、Elm Streetのストリート・セグメント又は住所セグメント・ベクトルの辺１６０に対応する）既知の住所地点#16 Elm Streetと、＃１〜＃９９の住所範囲に含まれるためElm Streetのストリート・セグメント辺１６２（Elm Streetの住所セグメント・ベクトル）に対応する、既知の住所地点#45 Elm Street及び#57 Elm Streetと、が格納されている。このように、住所地点は、ストリート名が同一であるストリート・セグメントに割り当てられ、当該地点の住所番号は、ストリート・セグメント又はストリート・セグメント辺（住所セグメント・ベクトル）に一般に割り当てられる範囲内に存在する。更に、ストリート・セグメント辺を割り当てるために、住所番号のパリティが一般に使用される。尚、特定の住所地点の住所番号のパリティは、特定の住所地点に対応するストリート・セグメント辺を判定するために基本となるセグメント辺についての、住所範囲のパリティを一致させるために使用可能である（偶数値の地点＃１６は、偶数値の住所を含むElm Streetの辺１６０上に存在し、奇数値の住所地点＃４５及び＃５７は、Elm Streetのストリート・セグメントの奇数値の住所を含むストリート・セグメント辺１６２上に配置される）。尚、本発明の実施形態の目的のため、住所セグメント・ベクトルには、ストリート・セグメント全体が含まれてもよく、ストリート・セグメントの一方の辺（例えば、図８の要素１６０又は１６２）が含まれていてもよい。この場合も、図８に示す住所地点#16 Elm Street、#45 Elm Street及び#57 Elm Streetは、既知の住所地点に対応し、当該既知の住所地点は、上述のように物理的構造、一区画、所在地等の、実際の位置及び番号であり、且つ、既知の実際の位置である。
【００３７】
何れの既知の住所地点が、何れのストリート・セグメント及び何れのストリート・セグメント辺の少なくとも何れかと対応するかを判定する際には、注意が必要である。これは、ストリート・セグメント及び住所地点の少なくとも何れかが、現実に対して正確に位置決めされていない場合には、ストリートの一方の辺に存在するように見える住所地点が、実際には当該ストリートの他方の辺に位置する可能性があるためである。ストリート・セグメント辺が、対応する住所範囲を有しない場合、ストリート・セグメントの正しい辺に住所地点を割り当てるために、他の技術が使用されてもよい。例えば、地理的近接（geographic proximity）は使用されてもよい１つの技術である。
【００３８】
既知の住所地点がストリート・セグメント又はストリート・セグメント辺（住所セグメント・ベクトル）に割り当てられると、ストリート・セグメント辺又はストリート・セグメント上に当該既知の住所地点の位置を投影するために、空間技術を含むがそれに限定されない技術が使用可能である。図８に示すように、地図データベースの住所セグメント・ベクトル上に既知の住所地点を投影する１つの技術は、ストリート・セグメント辺に垂線を下ろすことである。そのため、住所セグメント・ベクトル（例えば、＃２〜＃９８である偶数値の範囲を含むElm Streetのストリート辺１６０についての住所セグメント・ベクトル）に投影点１６４を作成するために、#16 Elm Street等の既知の住所地点が使用されてもよい。同様に、例えば＃１〜＃９９である奇数値の住所範囲を含むElm Streetの住所セグメント・ベクトルに、例えば既知の住所地点#45 Elm Street及び#57 Elm Streetをそれぞれ投影することにより、他の投影点１６６及び１６８を作成できる。従って、本発明の一実施形態において、例えば図８に示すように、住所地点は、相対的に最も近いストリート・セグメント辺に沿って、相対的に最も近い位置に投影される。そのような投影点の形成又は作成は、投影点のパリティとセグメント辺の範囲とが一致することの確認等の、割り当てに関するチェックを更に含んでもよい（例えば、奇数値の住所地点＃４５及び＃５７が投影された場合に、それらが例えば図８に示すように＃１〜＃９９の範囲等の奇数範囲を含むストリート・セグメントの一方の辺又は住所セグメント・ベクトルに投影されることを保証するために、チェックが行われてもよい）。
【００３９】
図９は、本発明の一実施形態の方法の次のステップの一例を示す。このステップにおいて、投影点に加えて、補間点が作成される。図９に示すように、投影点１６４、１６６及び１６８は残ったままである。これらの点に加えて、対応する補間点が、住所地点の住所に対して作成される。例えば、線形補間等の既知の補間技術を利用して、Elm Streetに沿う住所であって、#8 Elm Streetについての住所地点の住所の補間位置を表す補間点１７４が、住所#8 Elm Streetに対して作成されてもよい。同図から分かるように、当該補間点は、ストリート・セグメントの住所範囲内の数値的な位置に基づいて、ストリート・セグメントの湾曲に従った補間位置に存在する（既知の線形補間技術により予測されるように、住所＃８は住所＃２の近くに位置決めされる）。そのため、補間点１７４は、Elm Streetについての住所セグメント・ベクトルに沿って、当該住所セグメント・ベクトル内に#8 Elm Streetに対する住所地点の住所の位置を（既知の補間技術を使用して）補間することによって、既知の方法で形成される。同様に、補間点１７６は、Elm Streetの住所セグメント・ベクトルに沿って、#45 Elm Streetに対する住所地点の住所の位置を補間することによって、既知の住所#45 Elm Streetに対して形成又は作成されてもよく、補間点１７８は、Elm Streetの住所セグメント・ベクトルに沿って、#57 Elm Streetに対する住所地点の住所の位置を補間することによって、既知の住所#57 Elm Streetに対して形成又は作成されてもよい。
【００４０】
例えば、投影点１６４、１６６及び１６８、並びに対応する補間点１７４、１７６及び１７８（例えば、投影点が事前に作成されたElm Streetの住所について形成又は作成された補間点）が作成されると、本発明の一実施形態の方法において、これらの点はストリート・セグメント又は住所セグメント・ベクトルをサブセグメント又は住所サブセグメント・ベクトルに分割するために使用可能である。これは、例えば、地図データベースにおけるサブセグメント又は住所サブセグメント・ベクトルに含まれる住所の線形補間が、ストリート・セグメント又はストリート・セグメント辺上の線形補間よりも全体として投影点に近くなる状況であって、住所の実際の位置を更に伝えるのに分割が有用である状況において、実行されてもよい。特に、本発明の一実施形態において、投影点と対応する補間点（投影点及び補間点のペア）の間の距離が閾値距離を上回る場合に、住所セグメント・ベクトルは、複数の住所サブセグメント・ベクトルに分割される。尚、本実施形態において、当業者には既知であるように、当該距離は、実際には、絶対値、二乗値又は最大値等の距離の関数であってもよく、あるいは、平均値、中央値、平均、二乗平均値又は二乗平均平方根等の、複数のそのような距離の関数であってもよい。
【００４１】
本発明の一実施形態において、任意の所与のストリート・セグメント又はストリート・セグメント辺について、同一の住所に関連する投影点及び対応する補間点のペア（対応する投影点及び補間点、又は投影点及び補間点のペアとしても知られる）の間で、距離が計算されてもよい（例えば、補間点１７４及び投影点１６４のペアのように、投影点が事前に作成された例えばElm Streetの住所について、補間点が形成又は作成される）。少なくとも１つの実施形態において、対応する投影点と補間点との間の距離の中で、相対的に最大の距離が判定されてもよい。図９に示す例において、そのような距離は、ストリート・セグメントのそれぞれの辺について計算されてもよい。その場合、ストリート・セグメント辺１６０についての、投影点と補間点との間の相対的に最大の距離は、例えば図９の要素１８０により識別される距離であり、即ち、（これがストリート・セグメント辺１６０について計算された唯一の距離であるため）#8 Elm Streetに関する補間点１７４と投影点１６４との間の距離である。Elm Streetのストリート・セグメントのストリート・セグメント辺１６２についてのそのような距離は、距離１８２であり、これは、#45 Elm Streetに関する投影点１６６及び補間点１７６についての距離よりも相対的に長い。
【００４２】
その後、対応する投影点と補間点との間のこれら相対的に最大の距離の各々について、閾値距離との比較が行われ、例えば、判定された相対的に最大の距離が閾値距離を上回る場合には、分割が行われる。住所セグメント・ベクトルを使用して住所サブセグメント・ベクトルが作成されると、当該住所サブセグメント・ベクトルは、当該住所セグメント・ベクトルと共に、（例えば、ベンダの）ソース・デジタル地図データベースに（対応する住所セグメント・ベクトルに割り当てられた属性の全てと共に）格納される。その後、当該ソース・デジタル地図データベースから、既知の方法でデジタル地図アプリケーション・データベースを作成可能である。しかし、本発明の少なくとも１つの実施形態に基づいて、そのようなデジタル地図アプリケーション・データベースは、この時点で、（各々が、デジタル地図アプリケーション・データベースの住所セグメント・ベクトルに一般に割り当てられれる、限られた数の属性を含む）新たに作成された住所サブセグメント・ベクトルを、住所セグメント・ベクトルの代わりに及び／又はそれと共に、含んでいてもよい。
【００４３】
そのような閾値距離は、全ての比較のために使用される不変の距離である必要はない。例えば、そのような閾値は、市街地において相対的に小さくてもよい。多くの建物を含む市街地においては、例えば１００〜２００ヤードの相対的に短い距離でも位置が離れている場合、数百ヤードしか離れていないユーザの視界が、例えば他の建物又は構造によって妨げられることに起因して、ユーザの視界が損なわれ、その結果、ユーザが特定の所望の位置を見つけることは困難になる場合がある。更に、郊外においては、（例えば、０．２５マイル等の）相対的により大きな閾値が使用されてもよい。その場合、所望の目的地の実際の位置から遠く離れた住所の位置にユーザが到着したとしても、当該ユーザの視界が他の建物の存在によって損なわれる可能性は低いため、当該ユーザは、例えば建物等の所望の移動目的地の実際の位置を、それでも容易に目で確認することができるであろう。
【００４４】
従って、本発明の実施形態では、特定の閾値には限定されず、異なる複数の地域における異なる複数の閾値（例えば、市街地若しくは都市部における１００〜２００ヤード、又は郊外における０．２５マイル）等の、異なる複数の閾値を使用可能である。尚、本発明の実施形態は、本明細書中に記載された（市街地及び郊外の閾値の例を含む）特定の閾値に限定されることはない。
【００４５】
本発明の実施形態は、装置のデジタル地図アプリケーション・データベースにおいて、住所の位置の適切な分割を生じさせる何れの閾値を用いても動作するように設計されることによって、例えば、ジオコーディング技術及びナビゲーション技術の少なくとも何れかを使用するユーザが、ジオコーディング装置又はナビゲーション装置内で既存の補間アルゴリズムを利用して、ジオコーディング装置及びナビゲーション装置の少なくとも何れかによって示された目的地から、正確かつ所望の、実際の目的地に気づくか又はそれを見ることができるほど、建物又は他の移動目的地に十分に近い範囲内の位置を得られる。更に、サブセグメント・ベクトルを含む（例えば、ベンダの）ソース・デジタル地図データベースが、例えばジオコーディング・アプリケーション又はナビゲーション装置への格納用に、サブセグメント・ベクトルを含むデジタル地図アプリケーション・データベースを作成するために使用される場合、本発明の実施形態の態様は、ジオコーディング装置及びナビゲーション装置の少なくとも何れかの、ジオコーディング機能及びナビゲーション機能の少なくとも何れかをさらに向上させるように設計される。その後、本発明の一実施形態のサブセグメント・ベクトルを含む、そのような格納されたデジタル地図アプリケーション・データベースは、所望の位置にユーザを到着させるためのジオコーディング装置及びナビゲーション装置の少なくとも何れかの利用を更に向上させるために、上述の既存の補間技術と関連して使用されてもよい。
【００４６】
尚、分割するタイミング、及び分割が望ましい又は望ましくないタイミングを決定する際に、上述の方法において使用される補間閾値を決定するために、種々の技術が使用され得る。本発明の一実施形態において、当該補間閾値又は閾値距離は、補間点と投影点との間の距離であって、許容範囲にある相対的に最大の距離であってもよく、これは位置の精度の推定値としても考慮される。例えば、この相対的に最大の、又は最大の許容値は、地形（例えば上述のように、市街地か又は郊外か）によって、又は他の理由によって変化してもよい。そのような確定された閾値に基づいて、対応する投影点と補間点との間の距離の中で相対的に最大の距離が判定され得るとともに、本発明の一実施形態の分割処理は、当該判定された相対的に最大の距離が閾値距離を上回る場合に実行されてもよい。
【００４７】
本発明の別の実施形態において、当該閾値距離は、分割するタイミングを決定する際に、最大数の補間された住所のみ、又は相対的に最多の数の補間された住所のみが、投影住所地点とそれに対応する補間点との間に含まれるように、設定されてもよい。例えば、当該閾値が最大で２つの住所に設定され、且つ、補間された住所＃３４、＃３６及び＃３８が住所＃３２についての投影点及び補間点のペアの間に含まれる場合には、当該閾値を上回り、分割が行われる必要がある。この方法は、範囲内における全ての住所について、補間された住所を必要としてもよい。補間閾値を確立及び評価するための他の方法も、同様に実行可能である。
【００４８】
本発明の別の実施形態において、閾値距離は、分割するタイミングを決定する際に、住所セグメントに沿う投影点及び対応する補間点の全てのペアの間で判定された平均判定距離が、閾値距離を上回る場合に、分割を実行するように設定されてもよい。
【００４９】
別の実施形態において、補間閾値は、限られた数のサブセグメント又は住所サブセグメント・ベクトルのみを作成するように設定されてもよい。特定のアプリケーション（例えば、メモリが制限される小型装置におけるナビゲーション・アプリケーション等）は、住所セグメント及び住所サブセグメント・ベクトルのためのメモリ内の記憶容量が限られる場合がある。異なる複数の閾値が異なる複数のアプリケーションについて使用されてもよく、その結果、記憶装置が多くの住所サブセグメント・ベクトルを収容できるほど、位置の精度が向上する。限られたメモリの一例としては、ポータブル型であるが限られた量のメモリのみを含むパーソナルナビゲーション装置（ＰＮＤ）のメモリであってもよい。
【００５０】
上述の本発明の実施形態において、投影処理、補間処理及び判定処理は、住所サブセグメント・ベクトルへの複数の分割処理について実行されてもよい。従って、上述の実施形態において、住所サブセグメント・ベクトルは、特定の条件が満たされるまで、複数の住所サブセグメント・ベクトルに更に分割されてもよい。例えば、住所サブセグメント・ベクトルの分割処理は、相対的に最大又は最大の距離が、閾値距離以下になるまで又は細分化（subdivisions）の最大数に達するまで、実行されてもよい。更に、別の実施形態において、住所サブセグメント・ベクトルの分割は、住所サブセグメント・ベクトルの投影点と対応する補間点との間の距離の平均値（平均距離）が閾値距離を下回るまで、実行されてもよい。従って、少なくとも１つの実施形態において、投影処理、補間処理及び判定処理は、平均距離、最大距離、及び各住所サブセグメント・ベクトル内の投影点と対応する補間点との間の距離の関数のうちの少なくとも１つが、閾値距離を下回るように又は細分化の最大数に達するまで、住所サブセグメント・ベクトルへの複数の分割処理について実行される。尚、そのような反復処理には、補間値の再計算が含まれていてもよい。また、複数のサブセグメントは、反復法を使用せずに直接的に計算されてもよい。
【００５１】
この場合も、本発明の実施形態は、図９に示すようなストリート・セグメントの一方の辺に対応する住所セグメント・ベクトルの分割処理に限定されない。本発明の少なくとも１つの実施形態において、ストリート・セグメントの両方の辺１６０及び１６２が共に考慮されてもよく、その場合、相対的に最大の距離を有する投影点及び補間点の対応するペアは、当該複数の辺について見つけられてもよい。例えば図９の例に示すように、要素１８２は、Elm Streetのセグメント又は住所セグメント・ベクトルの両方の辺が共に考慮される場合に、対応する投影点と補間点との間の距離の中で、相対的に最大の距離に相当する。単一の相対的に最大の距離１８２が利用される場合、又はストリート・セグメントの各辺１６０及び１６２についての相対的に最大の距離が利用される場合（即ち、距離１８０及び１８２）の何れにおいても、ストリート・セグメントの一方の辺又は両方辺の分割処理に対して以下の技術が同様に適用可能である。本発明の実施形態の目的のため、ストリート・セグメント全体又はストリート・セグメントの個々の辺１６０及び１６２が住所セグメント・ベクトルとみなされてもよく、それらの何れの分割も、住所サブセグメント・ベクトルとみなされてもよい。
【００５２】
従って、本発明の実施形態において、投影点と対応する補間点との間の距離が補間閾値距離を上回ることが分かった場合、住所セグメント・ベクトルは、上記の実施形態において説明したように分割されてもよい。少なくとも１つの実施形態において、当該分割処理は、投影点と対応する補間点との全てのペアの間の平均距離を低減する、住所セグメント・ベクトル又は住所サブセグメント・ベクトルに沿った点において、実行されてもよい。少なくとも１つの限定しない例において、その点は投影点であってもよい（しかし、本発明の実施形態は、セグメント点として投影点を使用することに限定されると考えられるべきではない）。従って、少なくとも１つの実施形態において、住所セグメント・ベクトル又は住所サブセグメント・ベクトルは、住所セグメント・ベクトル又は住所サブセグメント・ベクトルに沿う投影点のうちの１つにおいて、分割されてもよい。以下では、限定することのない一実施形態について説明する。
【００５３】
一実施形態において、ストリート・セグメント辺１６０についての点１６４、又はストリート・セグメント辺１６２についての点１６８等の投影点は、住所セグメント・ベクトルの分割を行うための「分割点（split point）」になってもよい。従って、住所セグメント・ベクトルは、この点において分割（split）又はセグメント化（分割）（segmented）されてもよく、分割点の住所は、結果として得られた複数の住所サブセグメント・ベクトルのうちの１つについての住所範囲の端点に割り当てられてもよく、また、（範囲内かつ方向の範囲内で）隣接する住所は、もう１つの住所サブセグメント・ベクトルに割り当てられてもよい。
【００５４】
住所サブセグメント・ベクトルへの住所セグメント・ベクトルの分割の限定しない一例を図示する一実施形態を、図１０Ａ及び図１０Ｂに関して示す。図１０Ａは、＃２〜＃９８の住所範囲を有する住所セグメント・ベクトル（ストリート・セグメント）を示す。図１０Ａは、要素１８０により特定される既知の住所地点＃５０の実際の住所と、住所セグメント・ベクトルの住所範囲＃２〜＃９８の中間に存在する既知の住所地点＃５０についての補間された住所地点とを更に示す。これは要素１８２により特定される。当該実際の住所の投影点は、要素１８４により示される。投影点１８４と補間点１８２との間の距離を利用して、かつ、この距離と閾値距離とを比較することによって、対応する投影点１８４と補間点１８２との間の距離が閾値距離を上回る場合に、分割が必要であると判定できる。
【００５５】
対応する投影点１８４と補間点１８２との間の距離が閾値距離を上回ると判定される場合、複数の住所サブセグメント・ベクトルへの住所セグメント・ベクトルの分割が、上述の本発明の実施形態の何れかの方法で実行される。図１０Ｂに示すように、実際の住所＃５０の投影点１８４は、住所セグメント・ベクトルを複数の住所サブセグメント・ベクトルに分割するための「分割点」として使用可能である。その場合、例えば既知の住所地点の住所を端点として使用して第１のサブセグメント１８６が形成され、住所サブセグメント・ベクトル１８６の住所範囲は＃２〜＃５０の範囲となる。次に、最初の住所セグメント・ベクトルの範囲における次の住所地点が、他方の住所サブセグメント・ベクトル１８８の始点の住所として使用され、その結果、図１０Ｂに示すように＃５２〜＃９８の住所範囲が作成される。
【００５６】
このように、実際の住所＃５０が第１の住所サブセグメント１８６の住所範囲の一部になるため、住所サブセグメント・ベクトル１８６及び１８８を利用する補間処理は、図１０Ａに示す住所セグメント・ベクトルを利用する場合よりも、はるかに改善されることが理解されよう。例えば、ナビゲーション装置のユーザが住所＃６０の位置を見つけたい場合、メモリに住所サブセグメント・ベクトル１８８を格納した（図１０Ａの住所セグメント・ベクトル１８１の代わりに、あるいは記憶容量がある場合には住所セグメント・ベクトル１８１とともに）デジタル地図アプリケーション・データベースを使用するナビゲーション装置は、この住所サブセグメント・ベクトル１８８内で、住所＃６０に対応する建物の実際の位置にはるかに近い位置を見つける。図１０Ａと比較すると分かるように、ナビゲーション装置が図１０Ａの＃２〜＃９８の範囲の住所セグメント・ベクトル１８１のみを含むデジタル地図アプリケーション・データベースを代わりに利用した場合、既知の補間技術では、＃６０について図１０Ａの補間された住所１８２にはるかに近い結果になることにより、（実際は図１０Ｂの住所サブセグメント・ベクトル１８８内に存在する）住所＃６０に対応する建物の実際の位置から遠く離れた結果が生じる。
【００５７】
従って、住所＃５０が＃２〜＃９８の住所範囲を有する住所セグメント・ベクトル辺における分割点である場合、分割の後、その一方のサブセグメントは＃２〜＃５０の住所範囲を割り当てられ、他方のサブセグメントは＃５２〜＃９８の住所範囲を割り当てられる。あるいは、一方のサブセグメント辺（一方の住所サブセグメント・ベクトル）は＃２〜＃４８の住所範囲を割り当てられてもよく、他方のサブセグメント辺は＃５０〜＃９８の範囲を割り当てられてもよい。本発明の実施形態は、何れの変形例にも同様に適用可能である。また、別の実施形態においては、例えばシステム／アプリケーションが２つの＃５０が存在するという曖昧性を処理可能であると仮定すると、分割点は、１つのサブセグメントの始点の住所と別のサブセグメントの終点の住所とが、１つの住所で分離されずに等しくなるように、両方の住所範囲に含まれてもよい。
。
【００５８】
本発明の一実施形態において、分割点は、サブセグメント上の中間の投影点と補間点との間の全ての距離の平均値を低減するサブセグメント又は住所サブセグメント・ベクトルに割り当てられてもよい。別の実施形態においては、分割点は、サブセグメント上の中間の投影点と補間点とのペアの何れかの間の、相対的に最大の距離を低減するサブセグメントに割り当てられてもよい。当業者には明らかであるように、例えば、サブ範囲の大きさを最も近くするサブベクトルに分割点を割り当てる等の、そのような分割点を割り当てる他の方法が、住所セグメント・ベクトルの分割に対して同様に適用可能である。
【００５９】
住所セグメント・ベクトルを複数の住所サブセグメント・ベクトルに分割した後、当該分割処理は、結果として得られた複数の住所サブセグメント・ベクトルの各々について繰り返されてもよい。言い換えると、各住所サブセグメント・ベクトルの住所範囲は、上述のように割り当てられてもよいし、複数の既知の住所地点は、複数の投影点を作成するために各住所サブセグメント・ベクトルに個別に投影されてもよいし、また、当該複数の投影点についての位置は、各住所サブセグメント・ベクトルについて個別に、複数の補間点を作成するために補間される。その後、投影点と対応する補間点との間の距離が閾値距離を上回る場合、住所サブセグメント・ベクトルは、複数の住所サブセグメント・ベクトルに更に分割可能である。これは、各住所サブセグメント・ベクトルについて繰り返され得るとともに、何れかの住所サブセグメント・ベクトルにおいて、投影点と補間点とのペアの何れかについて判定された相対的に最大の距離が、閾値距離以下になるまでの間、必要に応じて連続して更に繰り返され得る。少なくとも１つの実施形態においては、当該分割処理は、投影点と対応する補間点とのペアの間の距離の平均値を低減する点であって、住所セグメント・ベクトルに沿う点において、実行されてもよい。他の実施形態において、３つ以上の住所サブセグメント・ベクトルの計算は、他の反復法により実行されるか、あるいは当業者には既知である種々の非反復計算により実行されてもよい。
【００６０】
従って、一実施形態において、既知の住所地点は、対応する住所サブセグメント・ベクトル上に再投影されてもよく、その後、補間点が当該住所地点の住所について判定又は作成されてもよく、その後、対応する投影点と補間点とのペアの間の距離が計算されてもよく、その後、相対的に最大の距離を有する投影点と補間点とのペアが、選択され、且つ、補間閾値と比較されてもよい。あるいは、別の実施形態において、当該既知の住所地点は、対応する住所サブセグメント・ベクトル上に再投影されてもよく、その後、補間点が住所地点の住所に対して判定又は作成されてもよく、住所サブセグメント・ベクトルが、住所サブセグメント・ベクトルの投影点と対応する補間点との間の距離の平均値が閾値距離より小さくなるまでの間、複数の住所サブセグメント・ベクトルに更に分割されてもよい。閾値距離を上回る場合には、住所サブセグメント・ベクトルは、例えば当該位置において、又は投影点等の点において、再度分割されてもよく、当該分割処理は、住所サブセグメント・ベクトルについての対応する投影点と補間点との間の距離の全てが補間閾値を下回るまで、セグメントの住所範囲の下限及び上限が同一になる（住所サブセグメント・ベクトルが単一の家屋番号のみを含むようになる）まで、あるいは、住所サブセグメント・ベクトルについて投影点が存在しなくなるまで、各ストリート・サブセグメント（住所サブセグメント・ベクトル）又は各ストリート・サブセグメント辺（住所サブセグメント・ベクトル）について再帰的に繰り返されてもよい。
【００６１】
ソース・デジタル地図データベース及びデジタル地図アプリケーション・データベースは、始点及び終点を有する住所セグメント・ベクトル又はストリート・セグメント、ストリート名及び他の種類の属性、並びに、当該セグメントに割り当てられた住所を表す住所範囲を含むことが既知であり、ソース・デジタル地図データベースは、デジタル地図アプリケーション・データベースの住所セグメント・ベクトル又はストリート・セグメントよりも多くの属性を有する住所セグメント・ベクトル又はストリート・セグメントを有する。本発明の一実施形態のソース・デジタル地図データベースから作成されたデジタル地図アプリケーション・データベースは、住所セグメント・ベクトルの代わりに、及び住所セグメント・ベクトルとともに、のうちの少なくとも１つにより、住所サブセグメント・ベクトルを含み、各住所サブセグメント・ベクトルは、本発明の一実施形態の（住所サブセグメント・ベクトルを含む）ソース・デジタル地図データベースからコピー又は作成される前に、当該デジタル地図アプリケーション・データベースに事前に格納された対応する住所セグメント・ベクトルの属性を含む。そのようなデジタル地図アプリケーション・データベースは、例えばジオコーディング、ＧＩＳ及びナビゲーション技術において、例えば（例えば、ナビゲーション装置の一体型入力表示装置を介して選択又は入力された）所望の移動目的地等の場所の位置を特定する場合に使用されてもよい。そのようなデジタル地図アプリケーション・データベースは、例えばジオコーディングにおいて使用される場合は中央サーバに格納されてもよく、車両搭載型のナビゲーション装置、パーソナルナビゲーション装置、及び、携帯電話、ＰＤＡ等を含むがそれらに限定されないナビゲーション機能を有する他の何らかの装置、の少なくとも何れかに格納されてもよく、並びに／又は何らかの種類のデジタル媒体に格納されてもよい。
【００６２】
一般に、そのようなデジタル地図アプリケーション・データベースは、例えばインターネット又はモバイル無線接続を介して新たなデジタル地図アプリケーション・データベース（本発明の一実施形態の住所サブセグメント・ベクトルを含む新たなデジタル地図アプリケーション・データベース等）に定期的に（例えば、新たな情報が受信される数ヶ月毎に）アクセスしてそれをダウンロード又はコピーすることにより、あるいは、車両搭載型のナビゲーション装置の場合、当該車両搭載型のナビゲーション装置のメモリに格納された地図情報を更新するために車両の当該車両搭載型のナビゲーション装置に入力可能なＣＤ−ＲＯＭ等に格納された新たな更新済のデジタル地図アプリケーション・データベースにより、パーソナルナビゲーション装置（ＰＮＤ）、あるいは、ＰＤＡ、携帯電話等のナビゲーション機能及びマッピング機能の少なくとも何れかを有する他の何らかの装置にダウンロード可能である。そのような更新技術は、上述の技術に限定されず、地図データベースを更新する任意の技術も含み得る。
【００６３】
従って、分割された住所セグメント・ベクトル又は分割された住所サブセグメント・ベクトルから生じる、上述の実施形態の何れかから得られた住所サブセグメント・ベクトルを含むデジタル地図アプリケーション・データベースは、対応する住所セグメント・ベクトルの代わりに、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも１つにより、（例えば、中央サーバに、後に例えば車両搭載型のナビゲーション装置のメモリに格納するためにＣＤ−ＲＯＭ又はコンピュータが読取可能な他の媒体に、ナビゲーション装置のメモリに）格納されてもよい。そのような格納（保存）処理は、ジオコーディングのための装置及びナビゲーション装置の少なくとも何れかにおけるメモリと、中央サーバにおけるメモリとの少なくとも何れかにおいて行われる。対応する住所セグメント・ベクトルの代わりに、又は対応する住所セグメント・ベクトルとともに保存された場合、元の住所セグメント・ベクトルの属性のうちの何れか又は全ては、結果として得られている住所サブセグメント・ベクトルに対して割り当てられてもよい。分割点の何れかの辺に関する属性を保持することが最も重要であり、その場合、住所番号（及び他の属性）は、それに対して割り当てられるか、又は保持される。何れの場合も、何らかの割り当て方法で結果として得られた住所サブセグメント・ベクトルの属性として、住所セグメント・ベクトルの住所番号を割り当てる必要がある。
【００６４】
住所サブセグメント・ベクトルが作成されると、複数の住所サブセグメント・ベクトルは、対応する住所セグメント・ベクトルの代わりに（あるいは、いくつかの例においては対応する住所セグメント・ベクトルとともに）、本発明の一実施形態におけるメモリのデジタル地図アプリケーション・データベースに格納されてもよい（この場合、「メモリ」という用語は、ナビゲーション機能を有する装置へ後にダウンロードさせるための中央サーバのメモリ、ＣＤ−ＲＯＭ、又は、ナビゲーション装置等の装置が上述の少なくとも１つの実施形態の分割処理を実行する機能を有する場合にはその装置のメモリ、を含んでもよいが、それらに限定されない）。例えば図１０Ａ及び図１０Ｂの例に示すように、例えば住所セグメント・ベクトル＃２〜＃９８（図１０Ａの要素１８１）の代わりに、住所サブセグメント・ベクトル＃２〜＃５０（図１０Ｂの要素１８６）及び住所サブセグメント・ベクトル＃５２〜＃９８（図１０Ｂの要素１８８）が格納されてもよい。更に、これらの（住所範囲＃２〜＃５０を有する）住所サブセグメント・ベクトル１８６及び（＃５２〜＃９８の住所範囲を有する）住所サブセグメント・ベクトル１８８は、図１０Ａに示す＃２〜＃９８の住所範囲についての住所セグメント・ベクトルの代わりに格納されてもよく、これらの住所サブセグメント・ベクトルは、他の住所セグメント・ベクトル又は住所サブセグメント・ベクトルと共に、メモリのデジタル地図アプリケーション・データベースに格納されてもよい。例えば、相対的に最大の距離又は判定された距離の平均値等の、投影点と補間点との間の距離が、住所セグメント・ベクトルについての閾値距離以下である場合、当該住所セグメント・ベクトルは、更に分割されることなく、データベース及びメモリの少なくとも何れかに、格納又は保持されてもよい。そのため、分割された場合にユーザが所望の位置を見つけるのに有用である住所セグメント・ベクトル（又はサブベクトル）のみが、分割されて、メモリに格納される必要がある。従って、不必要に大量の住所サブセグメント・ベクトルをメモリに格納する必要がないため、補間アルゴリズムの性能が向上するとともに、必要なメモリ空間が必要以上に増加しない。このことは、ＰＮＤ、携帯電話、ＰＤＡ及びナビゲーション機能を有するが記憶容量が限られる他の装置等の、ポータブルナビゲーション装置及びハンドヘルドナビゲーション装置において特に重要である。
【００６５】
例えば対応する投影点と補間点との間の距離が補間閾値を下回る場合、住所セグメント・ベクトルは（それらの属性と共に）メモリに格納され続ける。しかし、投影点と補間点との間の距離が補間閾値を上回ると、住所セグメント・ベクトルは、例えば既知の住所地点の投影点において住所サブセグメント・ベクトルに分割されてもよい。尚、当該分割処理は、投影点と補間点との間の距離として相対的に最小の距離を提供する、（住所サブセグメント・ベクトルの終点又は住所サブセグメント・ベクトルの始点である分割点を含む）住所範囲と、結果として得られる住所サブセグメント・ベクトルとは無関係に、実行されてもよい。当該分割処理の後、上述の本発明の実施形態の方法は、住所サブセグメント・ベクトルについて繰り返されてもよい。
【００６６】
少なくとも１つの実施形態において、住所セグメント・ベクトルの代わりに住所サブセグメント・ベクトルをデジタル地図アプリケーション・データベースに格納することがアプリケーションにとって有利である可能性があり、また、少なくとも１つの実施形態において、住所サブセグメント・ベクトル及び保存されている住所セグメント・ベクトルの両方をデジタル地図アプリケーション・データベースに格納することがアプリケーションにとって有利である可能性がある。従って、住所サブセグメント・ベクトルは、住所セグメント・ベクトルの代わりに、及び住所セグメント・ベクトルとともに、のうちの少なくとも何れかにより格納されてもよい。例えば、分割されていない住所セグメント・ベクトルを使用することは、表示目的又は表示用途について、より有効である可能性がある一方で、分割された住所サブセグメント・ベクトルを使用することは、位置の特定／ナビゲーションの目的又は用途について、より有効である可能性がある。メモリの制約により、デジタル地図アプリケーション・データベースにその両方を格納することが可能である場合には、少なくとも１つの実施形態において、新たな住所サブセグメント・ベクトル及び住所セグメント・ベクトルの両方を、システムをより有効化するためにそれぞれが使用され得るように、デジタル地図アプリケーション・データベースに格納することは、有用であろう。
【００６７】
尚、住所セグメント・ベクトルの分割処理をさらに改善するため、既知の住所地点をどのように当該住所セグメント・ベクトルに適用するかを判定するために、記載されたアルゴリズム以外の技術が実行可能であってもよい。従って、本発明の実施形態は、上述のアルゴリズムによって限定されるべきではない。本出願は、本出願に記載された特許請求の範囲によってのみ限定されるべきである。本発明の少なくとも１つの実施形態の主旨は、改善が生じる場合に住所セグメント・ベクトルの分割を利用することによって、補間処理を更に改善することである。
【００６８】
本発明の別の実施形態は、分割されていない複数のベクトルを格納するとともに、住所セグメント・ベクトルが分割された場合に、上述の方法の実施形態により作成された複数の住所サブセグメント・ベクトルを、対応する複数の住所セグメント・ベクトルの代わりに、及び対応する複数の住所セグメント・ベクトルとともに、のうちの少なくとも何れかにより格納しているメモリを対象としている。少なくとも１つの実施形態において、住所セグメント・ベクトルの代わりに住所サブセグメント・ベクトルをデジタル地図アプリケーション・データベースに格納しているメモリが、アプリケーションにとって有利である可能性があり、また、少なくとも１つの実施形態において、住所サブセグメント・ベクトル及び住所セグメント・ベクトルの両方をデジタル地図アプリケーション・データベースに格納するメモリがアプリケーションにとって有利である可能性がある。例えば、分割されていない住所セグメント・ベクトルは、表示の目的においてより有効である可能性があり、分割された住所サブセグメント・ベクトルは、上述のように位置の特定／ナビゲーションの目的においてより有効である可能性がある。メモリの制約によりその両方を格納することが可能である場合には、少なくとも１つの実施形態において、住所サブセグメント・ベクトル及び住所セグメント・ベクトルの両方を格納することは有用であろう。本発明の別の実施形態は、そのようなメモリを含むナビゲーション装置等の装置を対象としている。
【００６９】
本発明の実施形態はデジタル地図アプリケーション・データベースに対する変更を伴う一方で、他のベンダは、当該デジタル地図アプリケーション・データベースを、又はそれから派生した当該データの編集版を利用する、デジタル地図アプリケーション・データベース／アプリケーション変換器及びデバイス・アプリケーション・ソフトウェアを提供する。少なくとも１つの実施形態は、所望の場所に対応する情報をユーザに提供するための、地理情報システム（ＧＩＳ）に基づくアプリケーション・プログラムを対象としている。当該アプリケーション・プログラムは、複数の住所セグメント・ベクトル及び複数の住所サブセグメント・ベクトルを含む地図データベース（デジタル地図アプリケーション・データベース）を含む。当該複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、当該住所地点の住所についての補間された位置に相当する補間点との間の距離が、補間距離を上回る場合に、対応する住所セグメント・ベクトルの代わりに地図データベースに格納される。
【００７０】
デバイス・アプリケーション・ソフトウェアは、ユーザ入力に応じて、派生したデジタル地図アプリケーション・データベースにアクセスして操作する。ユーザに対するソフトウェアの出力は、リスト、テキスト、地図若しくは映像等のグラフィック表示、発話等の音声、又は他の種類の出力であってもよい。多くのＧＩＳアプリケーション、インターネット。アプリケーション、及びナビゲーション・アプリケーションは、上述の本発明の実施形態を使用できる。これらのアプリケーションは、（テキスト／リストに基づく）ジオコーディング・アプリケーション、（グラフィック／リスト／発話に基づく）経路計画／方向アプリケーション、及びグラフィックに基づく表示アプリケーションを含む。当該アプリケーションは、とりわけ、ナビゲーションシステム、インターネットに基づくシステム、及び地理情報システム（ＧＩＳ）を含んでもよい。当該アプリケーションは、マッピング・プログラム、ナビゲーション・プログラム、又は何らかの他の種類のプログラムであってもよい。上述のように、地図アプリケーションの消費者は、所望の場所の位置を特定するための、種々の装置及びシステムを提供されている。これらの装置及びシステムは、運転者がストリート及び道路をナビゲートし、且つ、所望の場所を入力できるようにする車両搭載型のナビゲーションシステム、同一機能を実行できるパーソナルデジタルアシスタント（「ＰＤＡ」）及び携帯電話等のハンドヘルド装置、並びに、ユーザが所望の結果を使用又は描写する地図にユーザがアクセス可能なインターネット・アプリケーションの形態をとる。本開示の目的のため、そのような結果の全ては単に「場所」として定義される。
【００７１】
図１１は、パーソナル・デジタル・アシスタント（ＰＤＡ）等のポータブルハンドヘルド装置において使用される一実施形態を示す。当該装置は、例えば携帯電話であってもよい。ＰＤＡの地図ソフトウェアにおいて、探索の一例は、150 Central Park Westへの運転指示を求めるユーザにより実行されてもよい。ＰＤＡの地図ソフトウェアは、本発明の実施形態を利用して、150 Central Park Westの位置を正確に表示する。
【００７２】
図１２は、全地球測位システム（ＧＰＳ）等の車両搭載型のナビゲーションシステムにおいて使用される方法、データベース、メモリ等の一実施形態を示す。ＧＰＳ地図ソフトウェアにおいて、探索の一例は、ＧＰＳ地図ソフトウェアの下部に示すように35 West Hill Roadへの運転指示を求める運転者により実行されてもよい。当該運転者が当該ＧＰＳ地図ソフトウェアを使用して自身の目的地に到着すると、当該ＧＰＳの地図ソフトウェアは、本発明の実施形態を利用して35 West Hill Roadの位置を正確に表示する。
【００７３】
図１３は、航空写真上に重ね合わされた住所地点の一例を示す一実施形態を示す。本例において、住所地点付近に位置を補間するためにサブセグメント化（sub-segmenting）が必要である可能性があり、これはセグメント上の範囲に依存してもよい。例えば、住所範囲が１１０１〜１１９９である場合、１１５５の補間位置はブロックの端部ではなく中央に存在し、サブセグメント化により補間が改善されるであろう。しかし、Detroit Stの当該部分における範囲が１１０７〜１１５５である場合、サブセグメント化は、非常に高精度のアプリケーション以外では不要であろう。その場合、サブセグメント化は、ストリート・セグメントに沿う住所の分布におけるより小さな非線形性に対応するために適用され得る。
【００７４】
本発明の別の実施形態は、所望の位置に対応する情報をユーザに提供する図１４のシステム９００を対象としている。システム９００は、複数の住所セグメント・ベクトル、及び複数の住所サブセグメント・ベクトルを含むソース地図データベース９３０と、所望の位置に関するクエリに応じて、アプリケーション・プログラムを使用して、デジタル地図アプリケーション・データベースに含まれる住所セグメント・ベクトル又は住所サブセグメント・ベクトルに対応する住所範囲内の、少なくとも１つの住所地点を検索するプロセッサ又は演算装置９１０とを備える。当該複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、住所地点の住所についての補間された位置に相当する補間点との間の距離が、閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて（及び／又は、対応する住所セグメント・ベクトルとともに）、デジタル地図アプリケーション・データベースに格納される。以下では、システム９００の一例について説明する。
【００７５】
図１４は、本発明の実施形態と共に使用可能なシステム９００の一例を示すブロック図である。図１４は構成要素を論理的に別個のものとして示すが、これは単に図示する目的のためである。同図に示される構成要素が、組み合わせ可能であり、又は、個別のソフトウェア、ファームウェア及びハードウェア構成要素の少なくとも何れかに分割可能であることは、当業者には明らかであろう。更に、そのような構成要素は、それらが組み合わされるか又は分割される方法に関係なく、同一の演算装置／システム上で実行可能であり、あるいは、１つ以上のネットワーク又は他の適切な通信手段によって接続された異なる演算装置／システムに分散可能であることも、
当業者には明らかであろう。
【００７６】
図１４に示すように、システム９００は、一般に、１つ以上のメモリ９１２、１つ以上のプロセッサ９１４、及び、１つ以上の何らかの種類の記憶装置又はリポジトリ（repository）９１６を備え得る演算装置９１０を含み、装置９１６のうちの少なくとも１つはデジタル地図アプリケーション・データベース９７０を含む。演算装置９１０は、表示装置９１８を更に含んでいてもよく、表示装置９１８は、当該装置上で動作し、且つ、システムがユーザに対して地図及び他の情報を表示可能なグラフィカル・ユーザ・インタフェース、即ちＧＵＩ９２０を含む。ユーザは、演算装置を使用することにより、例えば地図上に場所（locality）を表示することを要求するか、あるいは、地図上の経路及びテキスト指示の少なくとも何れかとして、運転指示を表示することを要求する。
【００７７】
ソース地図データベース９３０は、演算装置又はシステム９１０の外部記憶装置として示されるが、いくつかの例において、ソース地図データベース９３０は記憶装置９１６と同一の記憶装置であってもよい。本発明の実施形態によれば、ソース地図データベース９３０は、地図セグメント及び地図サブセグメントのテーブル及びインデックス９３２、住所地点のテーブル及びインデックス９３４、並びに、形状点のテーブル及びインデックス９３６を含む。
【００７８】
自社開発の地図データベース作成ソフトウェア９４０は、ソース地図データベース９３０内の地図セグメントのテーブル及びインデックス９３２、住所地点のテーブル及びインデックス９３４、並びに形状点のテーブル及びインデックス９３６をそれぞれ作成するために、実世界の（real-world）場所ソース（locality sources）及び緯度／経度ソース９６０を使用する。ソース地図データベース９３０からの情報は、ソース地図データベース／アプリケーション地図データベース変換器９５０によって使用され、これは最終的に演算装置９１０のユーザによって使用される。ソース地図データベース／アプリケーション地図データベース変換器９５０は、ユーザの演算装置９１０に対してリモートであると示されている。この変換は、地図ベンダの結果、及びアプリケーション・ソフトウェア・プロバイダの結果であってもよい。結果として得られたデジタル地図アプリケーション・データベース９７０は、一般に、装置の記憶装置９１６に格納される。このデバイス・アプリケーション・ソフトウェア９５０もリモートであると示されるが、ユーザの演算装置９１０に備わっていてもよい。
【００７９】
従って、本発明の一実施形態は、所望の位置に対応する情報をユーザに提供するシステム９００を対象としていてもよい。システム９００は、複数の住所セグメント・ベクトル及び複数の住所サブセグメント・ベクトルを含むデジタル地図アプリケーション・データベース９７０を備える。当該複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、当該住所地点の住所の補間された位置に相当する補間点との間の距離が、閾値距離を上回る場合に、対応する住所セグメント・ベクトルの代わりに、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも何れかにより、デジタル地図アプリケーション・データベース（９７０）に格納される。上述の処理のアプリケーションは、変換プロセス９５０を介してデジタル地図アプリケーション・データベース９７０に変換された関連する結果を用いて、ソース地図データベース９３０に適用される。プロセッサ９１４は、所望の位置に関するクエリに応じて、デジタル地図アプリケーション・データベース９７０を検索し、アプリケーション・プログラムを使用してデジタル地図アプリケーション・データベースの住所セグメント・ベクトル又は住所サブセグメント・ベクトルに対応する補間された位置を計算する。当該システムは、例えば、インターネットに基づくシステム及び車両搭載型のナビゲーションシステムの少なくとも何れかを含んでもよい。本発明の一実施形態は、例えばナビゲーション装置２００等の装置を対象としている。ナビゲーション装置は、ポータブルナビゲーション装置又は車両搭載型のナビゲーション装置であってもよい。本発明の一実施形態の装置は、複数の住所セグメント・ベクトル及び複数の住所サブセグメント・ベクトルを含むデジタル地図アプリケーション・データベースを格納するメモリ２３０（又はメモリリソース）と、格納されたアプリケーション地図データベースを使用して、入力又は選択された住所の位置を表示するディスプレイ２４０とを含んでもよい。複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に対応する投影点と、当該住所地点の住所の補間位置に対応する補間点との間の距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルの代わりに、及び対応する住所セグメント・ベクトルとともに、のうちの少なくとも何れかにより、デジタル地図アプリケーション・データベースに格納される。当該装置がナビゲーション装置２００である場合、ナビゲーション装置２００は、移動目的地の入力又は選択を促す入力装置（２２０）と、入力又は選択された移動目的地への移動経路を計算するプロセッサ（２１０）とを更に含んでもよい。移動経路の計算には、格納されたアプリケーション地図データベースを利用し、ディスプレイは計算された移動経路を表示するために使用可能である。
【００８０】
本発明の少なくとも１つの実施形態は、例えば以下に説明する、移動目的地の入力又は選択を求める入力装置２２０及び表示画面２４０を含む一体型入力表示装置と、複数の住所セグメント・ベクトル及び複数の住所サブセグメント・ベクトルを含む地図データベース（デジタル地図アプリケーション・データベース）を格納するメモリ２３０（又はメモリリソース）と、入力又は選択された移動目的地への移動経路を計算するプロセッサ２１０とを備えるナビゲーション装置２００を対象としていてもよい。当該複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に対応する投影点と、当該住所地点の住所の補間位置に対応する補間点との間の距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルの代わりにデジタル地図アプリケーション・データベースに格納される。移動経路の計算は、格納されたアプリケーション地図データベースを利用する。以下では、そのようなナビゲーション装置２００についての限定しない一実施形態について説明する。
【００８１】
図１５は、本願の一実施形態のナビゲーション装置２００の電子構成要素の一例を、ブロック構成要素の形式で示す、例示的な表現である（図１１及び図１２の表現よりも詳細なものを提供するが、図１２の車両搭載型のナビゲーション装置は、図１１のポータブルナビゲーション装置よりもメモリに組み込まれることが多いことに留意されたい）。尚、ナビゲーション装置２００のブロック図は、ナビゲーション装置の全ての構成要素を含むものではなく、構成要素の多くの例を表すにすぎない。
【００８２】
ナビゲーション装置２００は、筐体（不図示）内に位置付けられる。筐体は、入力装置２２０及び表示画面２４０に接続されるプロセッサ２１０を含む。入力装置２２０は、キーボード装置、音声入力装置、タッチパネル、及び情報を入力するために利用される他の任意の既知の入力装置のうちの少なくとも１つを、それらに限定されることなく含み得る。また、表示画面２４０は、例えばＬＣＤディスプレイ等の、任意の種類の表示画面を含み得る。特定の装置例においては、入力装置２２０及び表示画面２４０は、タッチパッド又はタッチスクリーン入力を含む一体型入力表示装置に一体化され、これにより、ユーザは、複数の表示選択肢のうちの１つを選択するか、又は複数の仮想ボタンのうちの１つを操作するためには、表示画面２４０の一部分に触れるだけでよい。
【００８３】
ナビゲーション装置２００は、例えば、可聴出力装置（例：ラウドスピーカ）、文字出力装置等の、出力装置２６０を含んでいてもよい。出力装置２６０がナビゲーション装置２００のユーザに対して可聴情報を生成できるため、同様に、入力装置２４０は、入力音声コマンドを受信するマイク及びソフトウェアを更に含み得ると理解される。
【００８４】
ナビゲーション装置２００において、プロセッサ２１０は、接続２２５を介して入力装置２２０に動作可能に接続され、且つ、入力装置２２０から入力情報を受信するように設定される。また、プロセッサ２１０は、情報を出力するために、表示画面２４０及び出力装置２６０のうちの少なくとも一方に、出力接続２４５を介して動作可能に接続される。更に、プロセッサ２１０は、接続２３５を介してメモリリソース２３０に動作可能に接続され、接続２７５を介して入出力（Ｉ／Ｏ）ポート２７０との間で情報を送受信するように更に構成される。この場合、Ｉ／Ｏポート２７０は、ナビゲーション装置２００の外部のＩ／Ｏ装置２８０に接続可能である。メモリリソース２３０は、上述の本発明の実施形態のうちの何れかにおいて説明したように、デジタル地図アプリケーション・データベース（又は、ナビゲーション装置２００が、十分なメモリ記憶容量を有するとともに、例えば図７の方法を実行する一例の実施形態の、少なくとも１つの場合においては、ソース・データベース）を格納しており、例えばランダム・アクセス・メモリ（ＲＡＭ）等の揮発性メモリや、例えば、デジタルメモリ、フラッシュメモリ等の不揮発性メモリから成る。外部Ｉ／Ｏ装置２８０は、例えばイヤホン等の外部聴音装置を含んでもよいが、これに限定されない。更に、Ｉ／Ｏ装置２８０への接続は、例えばハンズフリー動作と音声起動動作との少なくとも一方のため、イヤホン又はヘッドフォンへの接続のため、並びに／あるいは、例えば移動電話への接続のためのカーステレオユニット等の他の任意の外部装置への、有線接続又は無線接続であってもよい。この場合、移動電話接続は、ナビゲーション装置２００とインターネット又は例えば他の任意のネットワークとの間のデータ接続を確立するためと、インターネット又は例えば他の任意のネットワークを介するサーバへの接続を確立するためとの少なくとも一方のために使用されてもよい。
【００８５】
図１５は、接続２５５を介するプロセッサ２１０とアンテナ／受信機２５０との間の動作可能な接続を更に示す。この場合、アンテナ／受信機２５０は、例えばＧＰＳアンテナ／受信機であってもよい。参照番号２５０で示されるアンテナ及び受信機は、図示のために概略的に組み合わされるが、当該アンテナ及び受信機は、別個に位置する構成要素であってもよく、当該アンテナは、例えばＧＰＳパッチアンテナ又はヘリカルアンテナであってもよいことが理解されるだろう。
【００８６】
更に、図１５に示す電子構成要素が従来の方法で電源（不図示）により電力を供給されることが当業者には理解されるだろう。当業者によって理解されるように、図１５に示す構成要素の異なる構成が本願の範囲内であると考えられる。例えば、図１５に示す構成要素は、有線接続と無線接続との少なくとも一方等を介して互いに通信状態であってもよい。従って、本願のナビゲーション装置２００の範囲には、ポータブル又はハンドヘルドナビゲーション装置２００、及び車両搭載型のナビゲーション装置の少なくとも一方が含まれる。
【００８７】
また、図１５のポータブル又はハンドヘルドナビゲーション装置２００は、例えば、自転車、オートバイ、自動車、又はボート等の車両に、既知の方法で接続されるか又は「ドッキング」される。その場合、そのようなナビゲーション装置２００は、ポータブル又はハンドヘルドナビゲーションとして使用するために、ドッキングされた場所から取り外し可能である。
【００８８】
更に、少なくとも１つの実施形態において、ナビゲーション装置２００は、新たに作成された、（例えば、図６の方法で作成された）住所サブセグメント・ベクトルを含むデジタル地図アプリケーション・データベースをメモリ２３０に格納できるだけでなく、ナビゲーション装置２００は、上述のように既知の住所地点を含むデジタル地図データベース又は他のデータベースを格納する際に、当該ナビゲーション装置２００自体のプロセッサ２１０を使用して、上述した図７の方法の実施形態の動作を実行できる。例えば、少なくとも１つの代替的な実施形態においては、図７の方法は、複数の住所サブセグメント・ベクトルを含むデジタル地図ソース・データベースから作成された、その後にメモリ２３０に格納される、新たに作成されたデジタル地図アプリケーション・データベースを用いて、ナビゲーション装置２００内のプロセッサ２１０によって実行され得る。
【００８９】
ここで図１６を参照すると、ナビゲーション装置２００は、デジタル接続（例えば、既知のＢｌｕｅｔｏｏｔｈ技術を介するデジタル接続）を確立する（不図示の）移動装置（移動電話、ＰＤＡ、及び移動電話技術を用いる任意の装置のうちの少なくとも１つ等）を介して、サーバ３０２との「モバイル」ネットワーク接続又は通信ネットワーク接続を確立してもよい。そうして、そのネットワークサービスプロバイダを介して、当該移動装置は、サーバ３０２とのネットワーク接続を（例えば、インターネットを介して）確立できる。そのため、「モバイル」ネットワーク接続は、情報に対する「リアルタイム」又は少なくとも非常に「最新」のゲートウェイを提供するために、（単体時、及び車載走行時の少なくとも一方において移動可能であり、且つ、多くの場合移動している）ナビゲーション装置２００とサーバ３０２との間で確立される。
【００９０】
例えばインターネット（World Wide Web等）を使用して、（サービスプロバイダを介する）移動装置とサーバ３０２等の別の装置との間にネットワーク接続を確立することは、既知の方法で行われ得る。これには、例えばＴＣＰ／ＩＰ層プロトコルの使用が含まれ得る。当該移動装置は、ＣＤＭＡ、ＧＳＭ、ＷＡＮ等の任意の数の通信規格を利用できる。そのため、ナビゲーション装置２００は、例えば図６に関して上述した方法の実施形態を用いて作成された、複数の住所サブセグメント・ベクトルを含む新たに作成されたデジタル地図データベースを受信可能であり、その後にそれをメモリ２３０に格納可能である。
【００９１】
そのため、例えば移動電話又はナビゲーション装置２００内の移動電話技術を介するデータ接続を介して達成されるインターネット接続が利用されてもよい。この接続の場合、サーバ３０２とナビゲーション装置２００との間でインターネット接続が確立される。これは、例えば、移動電話又は他の移動装置及びＧＰＲＳ（汎用パケット無線サービス）接続（ＧＰＲＳ接続は、通信会社により提供される移動装置用高速データ接続であり、ＧＰＲＳはインターネットへの接続方法である）を介して行われ得る。
【００９２】
更に、ナビゲーション装置２００は、移動装置４００とのデータ接続を完了し、例えば既存のＢｌｕｅｔｏｏｔｈ技術を介して既知の方法でインターネット及びサーバ３０２とのデータ接続を最終的に完了する。この場合、例えばデータプロトコルは、ＧＳＭ規格に対するデータプロトコル規格であるＧＳＲＭ等の任意の数の規格を利用できる。そのため、ナビゲーション装置２００は、例えば図６に関して上述した方法の実施形態を用いて作成された、複数の住所サブセグメント・ベクトルを含む新たに作成されたデジタル地図データベースを受信可能であり、その後にそれをメモリ２３０に格納可能である。
【００９３】
ナビゲーション装置２００は、ナビゲーション装置２００自体の中に、自らの移動電話技術を含んでもよい（例えばアンテナを含み、この場合ナビゲーション装置２００の内部アンテナがオプションとして用いられてもよい）。ナビゲーション装置２００内の移動電話技術は、上述のような内部構成要素を含みこと、及び、例えば必要な移動電話技術とアンテナとの少なくとも一方を備える挿入可能なカードを含むことのうち、少なくとも一方が可能である。そのため、ナビゲーション装置２００内の移動電話技術は、任意の移動装置４００の方法と同様の方法で、例えばインターネットを介して、ナビゲーション装置２００とサーバ３０２との間にネットワーク接続を同様に確立できる。そのため、ナビゲーション装置２００は、例えば図６に関して上述した方法の実施形態を用いて作成された、複数の住所サブセグメント・ベクトルを含む新たに作成されたデジタル地図データベースを受信可能であり、その後にそれをメモリ２３０に格納可能である。
【００９４】
ＧＲＰＳ電話設定の場合、移動電話の機種、製造業者等の多様な範囲に関して正しく動作するために、Ｂｌｕｅｔｏｏｔｈ対応の装置が使用されてもよく、機種／製造業者専用設定は、例えばナビゲーション装置２００に格納されてもよい。この情報のために格納されたデータは更新され得る。
【００９５】
図１６は、汎用通信チャネル３１８を介してサーバ３０２と通信する、異なる多数の構成の何れかによって実現可能なナビゲーション装置２００を示している。通信チャネル３１８を介する接続がサーバ３０２とナビゲーション装置２００との間に確立される場合、サーバ３０２とナビゲーション装置２００とは通信可能である（尚、そのような接続は、移動装置を介するデータ接続、インターネットを介してパーソナル・コンピュータを介する直接接続等である）。そのため、ナビゲーション装置２００は、例えば図６に関して上述した方法の実施形態を用いて作成された、複数の住所サブセグメント・ベクトルを含む新たに作成されたデジタル地図データベースを受信可能であり、その後にそれをメモリ２３０に格納可能である。
【００９６】
サーバ３０２は、図示しない他の構成要素に加えて、メモリ３０６に動作可能に接続され、且つ、有線又は無線接続３１４を介して大容量データ記憶装置３１２に動作可能に更に接続される、プロセッサ３０４を含む。更に、プロセッサ３０４は、通信チャネル３１８を介してナビゲーション装置２００と情報の送受信を行うために、送信機３０８及び受信機３１０に動作可能に接続される。送受信される信号は、データ信号、通信信号及び他の伝搬信号の少なくとも１つを含んでもよい。送信機３０８及び受信機３１０は、ナビゲーション装置２００の通信設計において使用される通信条件及び通信技術に従って選択又は設計されてもよい。尚、送信機３０８及び受信機３１０の機能は、信号送受信機に組み合わされてもよい。
【００９７】
サーバ３０２は、大容量記憶装置３１２に更に接続される（又は、大容量記憶装置３１２を含む）。尚、大容量記憶装置３１２は、通信リンク３１４を介してサーバ３０２に接続されてもよい。大容量記憶装置３１２は、ナビゲーションデータ及び地図情報のストアを含む。また、大容量記憶装置３１２は、サーバ３０２とは別個の装置であってもよく、サーバ３０２に組み込まれてもよい。
【００９８】
ナビゲーション装置２００は、通信チャネル３１８を介してサーバ３０２と通信するように構成され、図１５に関して上述したように、プロセッサ２１０、メモリ２３０等を含むだけでなく、信号及びデータの少なくとも何れかを、通信チャネル３１８を介して送信する送信機３２０及び受信する受信機３２２を含む。尚、これらの装置は、更に、サーバ３０２以外の装置と通信するためにも使用され得る。更に、送信機３２０及び受信機３２２は、ナビゲーション装置２００の通信設計において使用される通信条件及び通信技術に従って選択又は設計され、送信機３２０及び受信機３２２の機能は、単一の送受信機に組み合わされてもよい。そのため、ナビゲーション装置２００は、例えば図６に関して上述した方法の実施形態を用いて作成された、複数の住所サブセグメント・ベクトルを含む新たに作成されたデジタル地図データベースを受信可能であり、その後にそれをメモリ２３０に格納可能である。
【００９９】
サーバメモリ３０６に格納されるソフトウェアは、プロセッサ３０４に命令を提供し、サーバ３０２がナビゲーション装置２００にサービスを提供できるようにする。サーバ３０２により提供される１つのサービスには、ナビゲーション装置２００からの要求の処理、及び大容量データ記憶装置３１２からナビゲーション装置２００へのナビゲーションデータの送信を含が含まれる。サーバ３０２によって提供される別のサービスには、所望のアプリケーション用の種々のアルゴリズムを使用したナビゲーションデータの処理、及びナビゲーション装置２００へのこれらの計算の結果の送信が含まれる。
【０１００】
一般に、通信チャネル３１８は、ナビゲーション装置２００とサーバ３０２とを接続する伝搬媒体又はパスを表す。サーバ３０２及びナビゲーション装置２００の両方は、通信チャネルを介してデータを送信する送信機と、通信チャネルを介して送信されたデータを受信する受信機とを含む。
【０１０１】
通信チャネル３１８は、特定の通信技術に限定されない。更に、通信チャネル３１８は、単一の通信技術に限定されない。即ち、チャネル３１８は、種々の技術を使用する複数の通信リンクを含んでもよい。例えば、通信チャネル３１８は、電気通信、光通信、及び電磁通信のうちの少なくとも１つ等のためのパスを提供するように構成され得る。そのため、通信チャネル３１８は、電気回路、ワイヤ及び同軸ケーブル等の電気導体、光ファイバケーブル、コンバータ、無線周波数（ＲＦ）波、大気、空間等のうちの１つ又はそれらの組み合わせを含むが、それらに限定されない。更に、通信チャネル３１８は、例えば、ルータ、リピータ、バッファ、送信機及び受信機等の中間装置を含み得る。
【０１０２】
１つの例示的な構成において、通信チャネル３１８は、電話及びコンピュータネットワークを含む。更に、通信チャネル３１８は、無線周波数、マイクロ波周波数、赤外線通信等の無線通信に適応できてもよい。更に、通信チャネル３１８は衛星通信に適応できる。
【０１０３】
通信チャネル３１８を介して送信される通信信号は、所与の通信技術において必要とされる又は望まれる信号を含むが、それらに限定されない。例えば、当該信号は、時分割多元接続（ＴＤＭＡ）、周波数分割多元接続（ＦＤＭＡ）、符号分割多元接続（ＣＤＭＡ）、グローバル・システム・フォー・モバイル・コミュニケーションズ（ＧＳＭ：Global System for Mobile Communications）等のセルラ通信技術において使用されるように構成されてもよい。デジタル信号及びアナログ信号の両方が、通信チャネル３１８を介して送信できる。これらの信号は、通信技術にとって望ましい変調信号、暗号化信号、及び圧縮信号のうちの少なくとも１つであってもよい。
【０１０４】
サーバ３０２は、無線チャネルを介してナビゲーション装置２００がアクセス可能なリモートサーバを含む。サーバ３０２は、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、仮想プライベートネットワーク（ＶＰＮ）等に位置するネットワークサーバを含んでもよい。
【０１０５】
サーバ３０２は、デスクトップ又はラップトップコンピュータ等のパーソナル・コンピュータを含んでもよく、通信チャネル３１８は、パーソナル・コンピュータとナビゲーション装置２００との間に接続されるケーブルであってもよい。あるいは、パーソナル・コンピュータは、ナビゲーション装置２００とサーバ３０２との間に接続されて、サーバ３０２とナビゲーション装置２００との間にインターネット接続を確立してもよい。あるいは、インターネットを介してナビゲーション装置２００をサーバ３０２に接続するために、移動電話又は他のハンドヘルド装置がインターネットへの無線接続を確立してもよい。そのため、ナビゲーション装置２００は、例えば図６に関して上述した方法の実施形態を用いて作成された、複数の住所サブセグメント・ベクトルを含む新たに作成されたデジタル地図データベースを受信可能であり、その後にそれをメモリ２３０に格納可能である。
【０１０６】
ナビゲーション装置２００は、（例えば、上述の本発明の応用の一実施形態についての方法（例えば図７の方法等）から作成されたデジタル地図ソース・データベースから生成される、デジタル地図アプリケーション・データベース等の）情報を、情報ダウンロードを介してサーバ３０２から与えられてもよい。当該情報は、自動的に更新される情報（例えば、地図、又は地図データベース情報等）、若しくはユーザがナビゲーション装置２００をサーバ３０２に接続する場合に、周期的に更新される情報であってもよいし、又は、例えば無線移動接続装置及びＴＣＰ／ＩＰ接続を介して、サーバ３０２とナビゲーション装置２００との間で、より継続して若しくは接続が頻繁に確立される場合に、更に動的な情報であってもよいし、それらの両方であってもよい。多くの動的な計算のために、サーバ３０２内のプロセッサ３０４が、大量の処理要求に対処するために使用されてもよい。しかし、ナビゲーション装置２００のプロセッサ２１０は、多くの場合、サーバ３０２への接続に関係なく、多くの処理及び計算にも対処可能である。これまでに示したように、複数の住所サブセグメント・ベクトルを含むデジタル地図データベースは、サーバ３０２において、あるいは、（ナビゲーション装置に格納されたデジタル地図データベースが既知の住所地点を含むことを想定した場合には）少なくとも１つの実施形態においてはナビゲーション装置２００自体においても、例えば図６に関して上述した方法の実施形態を用いて作成されてもよい。また、当業者には理解されるように、上述した本願の方法の実施形態に含まれる技術の何れも、本明細書で説明した装置又はナビゲーション装置２００のデジタル地図データベースに対して同様に適用可能である。
【０１０７】
図１５に示すように、ナビゲーション装置２００は、プロセッサ２１０、入力装置２２０、表示画面２４０を含む。入力装置２２０及び表示画面２４０は、例えば、タッチパネルスクリーンを介して、（直接入力、メニュー選択等により）情報を入力すること及び情報を表示することの両方を可能にするために、一体型入力表示装置に統合される。このようなスクリーンは、当業者には周知のものであるように、例えば、タッチ入力ＬＣＤスクリーンであってもよい。更に、ナビゲーション装置２００は、例えば、音声入力／出力装置等の、更なる任意の入力装置２２０と更なる任意の出力装置２６０との少なくとも何れかを有していてもよい。
【０１０８】
ソフトウェア技術の当業者にとっては明らかであるように、熟練のプログラマは、本願で開示した教示に基づいて、適切なソフトウェア・コーディングを容易に作成することが可能である。本発明の実施形態は、当業者によって直ちに明らかになるように、特定用途向け集積回路を作成することによって、又は、従来の構成要素の回路を含む適切なネットワークを相互に接続することによって、実現されてもよい。
【０１０９】
本発明の実施形態は、媒体上／媒体内に格納された、本発明の実施形態のプロセスの何れかを実行するようにコンピュータをプログラミングするために使用され得る命令を含む記憶媒体（メディア）である、コンピュータ・プログラムを含む。記憶媒体は、フロッピー（登録商標）ディスク、光学ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、マイクロドライブ、光磁気ディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、ＶＲＡＭ、フラッシュメモリデバイス、磁気カード、光学カード、分子記憶ＩＣを含むナノシステム、又は、命令及びデータの少なくとも何れかを格納するのに適した任意の種類のシステム若しくは装置を含む、任意の種類のディスクを含み得るが、それらに限定されない。
【０１１０】
本発明の実施形態は、コンピュータが読取可能な媒体を含み、当該媒体は地図データベースを含む。当該地図データベースは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルとを含む。当該複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも１つにより、地図データベースに格納されている。また、当業者には理解されるように、上述した本願の方法の実施形態に含まれる技術の何れもが、本明細書で説明した、コンピュータで読取可能な媒体の地図データベースに対して同様に適用可能である。
【０１１１】
本願の少なくとも１つの実施形態は、記憶媒体（コンピュータで読取可能な媒体又はメモリ等）に格納可能なデジタル地図アプリケーション・データベースを対象としている。当該データベースは、複数の住所セグメント・ベクトルと、複数の住所サブセグメント・ベクトルとを含む。当該複数の住所サブセグメント・ベクトルは、住所セグメント・ベクトルに投影された既知の住所地点に相当する投影点と、対応する補間点であって、住所地点の住所についての補間された位置に相当する補間点との距離が閾値距離を上回る場合に、対応する住所セグメント・ベクトルに代えて、及び対応する住所セグメント・ベクトルとともに、の少なくとも１つにより、地図データベースに格納されている。また、当業者には理解されるように、上述した本願の方法の実施形態に含まれる技術の何れもが、本明細書で説明した、コンピュータで読取可能な媒体の地図データベースに対して同様に適用可能である。また、当業者には理解されるように、上述した本願の方法の実施形態に含まれる技術の何れもが、本明細書で説明したデジタル地図アプリケーション・データベースに対して同様に適用可能である。
【０１１２】
コンピュータで読取可能な媒体（メディア）の何れか１つに格納された場合、本発明の実施形態は、汎用／専用のコンピュータ又はマイクロプロセッサのハードウェアを制御するためのソフトウェアと、コンピュータ又はマイクロプロセッサが、本発明の実施形態の結果を利用するヒューマン・ユーザ又は他の機構と相互に作用できるようにするソフトウェアとを含む。そのようなソフトウェアは、デバイス・ドライバ、オペレーティング・システム、及びユーザ・アプリケーションを含んでもよいが、それらに限定されない。結局、コンピュータで読取可能なそのような媒体は、上述したように、本発明の実施形態を実行するソフトウェアを更に含む。
【０１１３】
汎用／専用のコンピュータ又はマイクロプロセッサのプログラミング又はソフトウェアには、本発明の実施形態の教示を実行するソフトウェア・モジュールが含まれる。本発明の実施形態は、当業者にとって明らかであるように、本開示の教示に従ってプログラミングされた、従来の汎用又は専用のデジタル・コンピュータ又はマイクロプロセッサを使用して、都合良く実行されてもよい。
【０１１４】
本発明の実施形態についての上述の説明は、例示及び説明を目的として提供されている。当該説明は、包括的であること、又は開示したままの形態に本発明の実施形態を限定することを意図したものではない。当業者には、多くの変更及び変形が明らかであろう。当該実施形態は、本発明の原理及びその現実的な応用について最良の説明を行うために選択及び説明されており、それにより、当該技術に精通した他者が、本発明の種々の実施形態に関する発明と、予期される特定の用途に適した種々の変更とを理解することが可能になる。本発明の範囲は以下の特許請求の範囲及びそれらの均等物によって規定されることが意図されている。
【０１１５】
本発明の種々の態様及び実施形態についてこれまでに説明してきたが、本発明の範囲は、本明細書で詳しく説明した特定の装置に限定されるのではなく、添付した特許請求の範囲の範囲に属する全ての構成とそれらに対する変更及び修正とを包含することにまで及ぶことが理解されよう。
【０１１６】
例えば、上述した目的地ビューは、目的地の住所の周囲の建物を表す画像を含む一方で、目的地の住所のみのレンダリングされた画像を含んだ目的地ビューは、やはりユーザが当該住所を特定してナビゲートするのに役立つ可能性があることが理解されよう。従って、目的地の住所及び近隣の建物を含むレンダリングされた画像を生成することが望ましい一方で、これは本発明に必須の特徴ではない。
【０１１７】
例えば、上記の詳細な説明において説明した実施形態ではＧＰＳに言及しているが、ナビゲーション装置は、ＧＰＳの代わりとして（又は実際にはＧＰＳとともに）任意の種類の位置感知技術を利用してもよいことに留意されたい。例えば、ナビゲーション装置は、欧州ガリレオシステム（European Galileo system）等の、他のグローバル・ナビゲーション衛星システムを利用してもよい。同様に、衛星ベースのものには限定されることはないが、装置が地理的位置を判定することを可能にする地上ベースのビーコン又は他の任意の種類のシステムを使用して、容易に機能してもよい。
【０１１８】
好適な本実施形態は、ソフトウェアを用いて特定の機能を実現する一方で、当該機能はハードウェア単独で（例えば、１つ以上のＡＳＩＣ（特定用途向け集積回路）を用いて）、又はハードウェア及びソフトウェアを実際に組み合わせて、同様に実行され得ることが、当業者には理解されよう。そのため、本発明の範囲は、ソフトウェアのみにおける実行に限定されるものと解釈されるべきではない。
【０１１９】
最後に、添付の特許請求の範囲は、本明細書で説明した特徴の特定の組み合わせを記述しているが、本発明の範囲は、以下で請求されている特定の組み合わせに限定されることはなく、当該特定の組み合わせが現時点で添付の特許請求の範囲に具体的に列挙されているか否かにかかわらず、本明細書で開示した特徴又は実施形態の組み合わせの何れをも包含することに及ぶことに留意されたい。
【図１】
2012511721.tif 000003
【図２】
2012511721.tif 000004
【図３】
2012511721.tif 000005
【図７】
2012511721.tif 000006
【図８】
2012511721.tif 000007
【図９】
2012511721.tif 000008
【図１０】
2012511721.tif 000009
【図１１】
2012511721.tif 000010
【図１２】
2012511721.tif 000011
【図１４】
2012511721.tif 000012
【図１５】
2012511721.tif 000013
【図１６】
2012511721.tif 000014
【図４】
2012511721.tif 000015
【図５】
2012511721.tif 000016
【図６】
2012511721.tif 000017
【図１３】
2012511721.tif 000018
【国際調査報告】
2012511721.tif 000019
2012511721.tif 000020
2012511721.tif 000021