地図内の区間を位置特定するための方法
本発明においては、第１の地図における区間に関連する起源ルート点を規定し、起源ルート点の座標を検出し、起源ルート点から出発して複数のブランチからなる起源ツリー構造を形成し、起源ツリー構造のブランチのツリー点を、ツリー点が第１の地図における交通網の点にそれぞれ対応するように配置し、第２の地図において照合ルート点を、起源ルート点の座標の近傍に規定し、照合ルート点から出発して複数のブランチからなる照合ツリー構造を形成し、照合ツリー構造のブランチのツリー点を、ツリー点が第２の地図における交通網の点にそれぞれ対応するように配置し、起源ツリー構造と照合ツリー構造を比較し、照合ツリー構造と起源ツリー構造との所定の一致が達成されるまで別の照合ルート点を規定し、第１の地図における起源ルート点についての区間の参照に基づき、第２の地図における照合ルート点に関する区間を検出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、交通網のディジタル化された第１の地図に由来する所定の区間を交通網のディジタル化された第２の地図内で位置特定するための方法に関する。
【０００２】
車両ナビゲーションのための基礎として、ナビゲーションシステムは交通網ないし道路網のディジタル化された地図にアクセスする。これらの地図は標準化されていないので、異なるメーカの地図ではディジタル化された地図情報に差異が生じる可能性がある。
【０００３】
今日では慣例となっている動的なナビゲーションにおいては、ナビゲーションシステムによって、受信した最新の交通状況についてのトラフィックデータに基づき既に計算されたルートが検査されるか、変化した交通状況を考慮して新たにルートが計算される。通常の場合、位置特定を実現するためにトラフィックデータは交通網の所定の区間に対応付けられている。ナビゲーションシステムは、受信したトラフィックニュースをルート計算の際に考慮できるようにするために、位置特定された区間をこのナビゲーションシステムが使用できる地図において一義的に位置特定しなければならない。この位置特定を照合とも称する。
【０００４】
実際に交通網の一部を照合する際には、区間の（形状）点の座標がディジタル化された第１の地図を有する符号化側において符号化され、所定の属性と共に復号化システムに伝送され、この復号化システムがディジタル化された第２の地図にアクセスする。この座標および属性に基づき、対応する区間が復号化側において同定される。伝送されるべきこの座標は部分的に等間隔になり、また部分的に所定のアルゴリズムを用いて、例えばダグラスポイカー（Douglas-Peuker）アルゴリズムを用いて選択される。復号のために受信器側の地図のデータを用いて相関が計算される。伝送された座標は所定の範囲内でシフトされる。最大値においては正確なシフトが想定され、このシフトは属性に基づき証明される。したがって区間の一義的な同定が実現される。
【０００５】
更なる属性を使用しなければ、例えば並行車線を区別することができないので、復号は十分でないことが多い。しかしながら走行方向などの更なる属性を考慮したとしても一義的な最大値を検出できない可能性がある。付加的に、相関化された点を通るルートは復号化器の動作時間を延ばす。しかしながらこのことは、最初のステップにおけるそれらの点の相関化の際にはトポロジを考慮することができないので不可欠である。したがって、本来隣接している点が道路網の異なる道路に置かれてしまう可能性がある。さらには伝送すべき点が多数ある場合データ量は非常に急増するが、道路が幾つかある場合には正確な同定のために点は複数なくてはならない。
【０００６】
したがって本発明の課題は、ディジタル化された地図における区間を同定するための改善された方法を提供することである。
【０００７】
この課題は、請求項１の特徴を有する方法によって解決される。
【０００８】
本発明によれば、冒頭で述べたような方法において、起源ルート点が第１の地図における区間に関して規定され、この起源ルート点の座標が検出される。起源ルート点から出発して複数のブランチからなる起源ツリー構造が形成され、この起源ツリー構造のツリー点は、それらのツリー点が第１の地図における交通路のそれぞれの点に対応するように配置されている。照合ルート点は第２の地図において起源ルート点の座標の近傍において規定され、同様にして照合ツリー構造が照合ルート点に基づき複数のブランチから形成され、この照合ツリー構造のツリー点は、それらのツリー点が第２の地図における交通路のそれぞれの点に対応するように配置されている。起源ツリー構造および照合ツリー構造は相互に比較され、別の照合ルート点が別の照合ツリー構造を形成するために規定され、これは照合ツリー構造と起源ツリー構造の所定の一致が達成されるまで行われる。続いて区間が第２の地図における照合ルート点を参照する区間が、第１の地図における起源ルート点についての区間の参照に基づき検出される。
【０００９】
ツリー構造を形成することによって、検索すべき区間を含んでいる第１の地図内の交通網の対応する区間が地図データから取り出され抽出されて表示される。したがって異なるディジタル化された地図における交通網の極僅かな差異によりそれぞれのツリー構造の最小限の変更しか生じない。全く同じツリー構造は同一のルート点における同一の地図データに関してしか考えられないので、所定量の差異内での２つのツリー構造の一致は、本発明による照合ツリー構造と起源ツリー構造との比較にとって十分である。したがって地図情報を部分毎に相互に比較することができ、２つの地図における交通網の所定の区間を位置特定することができる。
【００１０】
有利には、起源ルート点および／または照合ルート点は交通網のそれぞれ１つの点に対応する。このようにして、ツリー構造を規定する全ての点が道路ないし交通路上に存在することが達成される。
【００１１】
第１の地図に関するツリー構造と第２の地図に関するツリー構造をより簡単に相互に比較するために、有利にはツリー点に対応する交通路の点は、ルート点または他の例えば隣接するツリー点に対応する交通路の他の点までの所定の区間距離を有するように配置されている。
【００１２】
有利には区間距離を事前に決定することができる。択一的に、区間距離を区間の長さに依存して決定することができる。これによって、ツリー構造の拡張部が同定すべき区間の拡張部とそれぞれ所定の関係にあることが達成される。
【００１３】
並行する車線も正確に同定できるようにするために有利には、対応するルート点から出発して到達することができるツリー点のみが考慮される。すなわちこの場合には、分岐規則、法定上定められた走行方向（一方通行道路）および別の交通規則が一緒に考慮される。
【００１４】
さらに有利には、所定の交通路クラスの交通路上の点に対応するツリー点のみが考慮される。このことは、場合によっては存在する裏通りないし脇道における複数のツリー点に起因する複雑なツリー構造を回避する。
【００１５】
有利には起源ツリー構造がバイナリに符号化され伝送される。これにより伝送すべき伝送量を低減することができる。
【００１６】
以下では、添付の図面を参照しながら本発明の実施例を詳細に説明する。ここで、
図１は、相互に比較される２つの概略的な地図を示す。
図２は、選択された区間を有する第１の地図の一部を概略的に示す。
図３および図４は、図２に示されている区間を位置特定するための第２の地図の一部を概略的に示す。
図５ａから図５ｃはそれぞれ、図２から図４のツリー構造を概略的に示す。
図６は、別の区間を有する第１の地図の一部を概略的に示す。
図７は、図６に示されている区間を位置特定するための第２の地図の対応する部分を示す。
【００１７】
図１には、交通網ないし道路網の一部であり位置特定されるべき区間２が存在する地図１が示されている。アプリケーション３、例えば交通管理局は例えばこの区間２内の交通渋滞および／または工事現場を通知するために地図１にアクセスする。本発明による別の考えられる用途は、観光ポイント、例えばレストランおよび／またはホテルの位置の照合、またはディジタル化された地図への新たな地図データの挿入である。アプリケーション３は以下において説明する本発明による方法を用いて、区間２を同定するための相応の道路情報を符号化し、符号化されたデータを適切な送信装置４に引渡す。
【００１８】
続いて、送信装置４は符号化された道路データを受信装置５に伝送する。図１においてはジグザグの線６によって示されている伝送は無線伝送でよく、例えばＵＫＷ送信器ＲＤＳ（Radio Data System）のためのディジタルデータ伝送システムを介して行うことができる。さらに、ＤＡＢ（Digital Audio Broadcasting）、インターネットまたは通信コネクションを介する伝送も考えられる。
【００１９】
受信装置５は符号化されたデータをアプリケーション７に転送し、このアプリケーション７は受信したデータを復号する。アプリケーション７は道路地図８にアクセスし、この地図８における対応する区間９の位置特定を行う。アプリケーション７として例えばナビゲーションシステムが考えられる。ナビゲーションシステムはここで交通ニュースをルート計画および目的地案内の際に考慮することができる。
【００２０】
図２は、道路網１１を有する第１の地図１０を拡大して概略的に示す。道路網１１においては破線で区間１２がマーキングされており、この区間１２が他のマップ（図３ないし図４）において位置特定されるべきである。区間１２内では先ず起源ルート点１３が規定され、この起源ルート点１３は道路網１１における交点に対応する。起源ルート点１３は有利には交点上に位置するか、少なくともその交点の近傍に位置する。何故ならば、形成すべきツリー構造の特性は交差する道路の数が増えるに連れ高まるからである。しかしながら道路上の他のあらゆる点またはその道路から離れた点も選択することができる。
【００２１】
起源ルート点１３から出発して先ずツリー点１４ａが規定され、このツリー点１４ａは道路網１１上において起源ルート点１３から所定の距離を有する点に対応する。続いてこのツリー点１４ａから出発して同様にツリー点１５が規定され、また後続のステップではツリー点１６ｂ，１６ｃおよび１６ａが規定される。ツリー点を選択する際には、考察する線から北に向かってツリー点は時計回りに連続して選択される。
【００２２】
ブランチ線が最後のツリー点、この実施例ではツリー点１６ａに達している場合には、１つ前のツリー点、この実施例ではツリー点１５ａから時計回りで別のツリー点、この実施例では１６ｂが規定される。これらのステップは、ツリー点１５ａから別のツリー点に達しなくなるまで繰り返される。
【００２３】
ツリー点１６ａ，１６ｂおよび１６ｃはそれぞれ道路点に対応しており、これらの点は全て起源ルート点１３に対応する道路点から同一の距離を有する。起源ルート点１３からツリー点１４ａを介するツリー点１５までの結合、さらにはツリー点１６ａ，１６ｂおよび１６ｃまでの結合を段階的に行うことによって、起源ツリー構造に関する第１のブランチが形成される。
【００２４】
同等のやり方で、起源ルート点１３から出発してツリー点１７ａおよび１７ｂならびに１８ａおよび１８ｂを有するツリー構造の第２のブランチが形成される。生じたツリー構造の第３のブランチはツリー点１９ａおよび１９ｂならびにそれに続く４つのツリー点２０ａ，２０ｂ，２０ｃおよび２０ｄを有する。このようにして形成されたツリー構造が図５に示されている。分かりやすくするために起源ルート点１３にのみ参照番号を付している。個々のツリー点は基礎となる道路網を考慮せずに相互に接続され、これによって道路網から取り出され抽出された表示が得られる。
【００２５】
ツリー構造を構築するために、起源ルート点の選択後には所期の間隔を置いて、分岐した道路上に１つのツリー点がセットされる。選択された間隔は例えばルート点から測定して５０ｍ，１００ｍおよび２００ｍにある。例えば、起源ルート点１３から出発してそれぞれの終端点１６ａ〜１６ｃ，１８ａおよび１８ｂならびに２０ａ〜２０ｄまでの全てのブランチが順に分岐され、起源ルート点１３から遠ざかる各ステップに対しては１が記録され、起源ルート点１３へと戻る各ステップに対しては０が記録されることによってツリー構造を適切に符号化することができる。
【００２６】
これによりこの実施例においては、起源ルート点１３から第１のツリー点１４までのステップに関して１が１回現われ、またツリー点１５を介してツリー点１６ａに達するためにはさらに１が２回現われる。ツリー点１６ａからはツリー点１５に戻らなければならないので、したがって０が記録される。連続してツリー点１６ｂと１６ｃに達するためには結果１０１が規定される。さらに３ステップ戻ると、すなわち３回続けて０が現われると再び起源ルート点１３に達する。同様にして、最終的に再び起源ルート点１３に達するまでには別の２つのブランチが分岐される。この実施例における全体的な結果は1110101000111001100011100110101000である。この文字列が起源ルート点１３の地理座標、また必要に応じて区間１２を限定するためのさらなる属性および長さ属性と共に伝送される。
【００２７】
図３は第２の地図２１の一部を示し、この部分は図２に示されている地図部分１０に実質的に対応するが、道路網１１ではなく道路網２２が表示されている。つまり道路２３はこの地図部分２１においては２車線に構成されており、この道路２３は図２の地図部分１０においては単に１車線として示されている。２つの道路網１１および１２の別の相違点は相応の図面から見て取れる。
【００２８】
図２に示されている起源ルート点１３の地理座標は伝達されているので、図３の地図部分２１においては照合ルート点２４が規定され、この照合ルート点２４は伝達された地理座標の近傍に存在する。照合ルート点２４から出発して、図２を参照しながら説明したようにして、図２のツリー点１４ａ，１４ｂおよび１４ｃにほぼ対応するツリー点２５ａ，２５ｂおよび２５ｃを有する第２のツリー構造が構築される。
【００２９】
ツリー点２５ａから出発して、ツリー点２６，２７ａ，２７ｂおよび２７ｃを有する第１のブランチが延びる。ツリー点２５ｂから始まる第２のブランチはツリー点２８，２９ａおよび２９ｂを有するように延びる。最後に、ツリー点２５ｃから始まる第３のブランチはツリー点３０，３１ａ，３１ｂ，３１ｃ，３１ｄ，３１ｅおよび３１ｆを有するように延びる。形成されたツリー構造が図５ｂに概略的に示されている。図５ａに示されている起源ツリー構造と図５ｂの照合ツリー構造とを比較するとこれらのツリー構造が著しく異なることが分かる。つまりツリー構造の十分な一致は達成されていない。
【００３０】
図４には、図３の道路網２２を有する地図部分２１が再び示されている。図４においては道路網２２上に別の照合ルート点３２が規定され、この照合ルート点３２から出発して別の第３のツリー構造が形成される。第３のツリー構造はツリー点３３，３４，３５ａ，３５ｂおよび３５ｃを有する第１のブランチを有する。第２のブランチはツリー点３６，３７ａ，３７ｂ，３８ａおよび３８ｂを有する。最後に第３のブランチはツリー点３９，４０ａ，４０ｂならびに４１ａ，４１ｂ，４１ｃ，４１ｄ，４１ｅおよび４１ｆを有する。
【００３１】
形成された第３のツリー構造が図５ｃに概略的に示されている。図５ｃのツリー構造と図５ａのツリー構造を比較すると、それぞれの第１のブランチはほぼ同一であり、第３のブランチは端部領域においてのみ僅かに相違していることが分かる。この相違は、図３および図４における道路２３が２車線で考慮されるが、これに対し図２において対応する道路は１車線として示されていることに起因する。
【００３２】
続いて区間４２が図４における照合ルート点３２を参照して、図２における起源ルート点１３についての区間１２の参照に基づき検出される。
【００３３】
２つの並行な車線を有する道路においては対向する走行方向に関して、一方の車線にのみ関与する区間を一義的に同定できるようにするために、ツリー構造を形成する際には、分岐規則および他の交通規則を考慮する際にもルート点から道路の相応の点に到達することができる、もしくは向かうことができる場合にのみツリー点はセットされる。付加的に、ルート点からの距離が長くなるにつれ、同等の道路クラスまたはより高い道路クラスの道路のみが考慮されるようにツリー点の選択を制限することができる。このことは、細い裏通りまた場合によっては重要でない裏通りに起因する複雑なツリー構造を回避する。
【００３４】
さらには、照合された区間が第２の地図ないし復号化側の地図内に存在しない場合には、検索された区間が存在する領域を例えば伝送すべきパターン要素を用いて表すことができる。これによって、非常に多くの量のデータを伝送する必要なく、接している道路を同定することにより復号化側における地図データの補完が実現される。この補完を図６および図７に基づき詳細に説明する。
【００３５】
図６には、図２の交通網１１を有する地図部分１０が示されている。交通網１１はＦ字型に近い裏通りの配置構成４３を有する。図６においてはやはり起源ルート点１３から出発してツリー構造が形成される。このツリー構造は実質的に図５ａに概略的に示したツリー構造に対応する。図７には、道路網２２を有する地図部分２１が再び示されている。図６における裏通りの配置構成４３は図７には存在していないことがはっきりと見て取れる。
【００３６】
起源ルート点１３の伝送された座標に基づき、地図部分２１においては照合ルート点３２が決定され、この照合ルート点３２から出発して図６のツリー構造と十分に一致するツリー構造を形成することができる。続いてパターン４４内に存在する地図情報を図７の道路網２２に置くことができる。したがってこのようにして図７に示されている地図２１を形成することができる。
【図面の簡単な説明】
【００３７】
【図１】相互に比較される２つの概略的な地図を示す。
【図２】選択された区間を有する第１の地図の一部を概略的に示す。
【図３】図２に示されている区間を位置特定するための第２の地図の一部を概略的に示す。
【図４】図２に示されている区間を位置特定するための第２の地図の一部を概略的に示す。
【図５ａ】図２から図４のツリー構造を概略的に示す。
【図５ｂ】図２から図４のツリー構造を概略的に示す。
【図５ｃ】図２から図４のツリー構造を概略的に示す。
【図６】別の区間を有する第１の地図の一部を概略的に示す。
【図７】図６に示されている区間を位置特定するための第２の地図の対応する部分を示す。
【技術分野】
【０００１】
本発明は、交通網のディジタル化された第１の地図に由来する所定の区間を交通網のディジタル化された第２の地図内で位置特定するための方法に関する。
【０００２】
車両ナビゲーションのための基礎として、ナビゲーションシステムは交通網ないし道路網のディジタル化された地図にアクセスする。これらの地図は標準化されていないので、異なるメーカの地図ではディジタル化された地図情報に差異が生じる可能性がある。
【０００３】
今日では慣例となっている動的なナビゲーションにおいては、ナビゲーションシステムによって、受信した最新の交通状況についてのトラフィックデータに基づき既に計算されたルートが検査されるか、変化した交通状況を考慮して新たにルートが計算される。通常の場合、位置特定を実現するためにトラフィックデータは交通網の所定の区間に対応付けられている。ナビゲーションシステムは、受信したトラフィックニュースをルート計算の際に考慮できるようにするために、位置特定された区間をこのナビゲーションシステムが使用できる地図において一義的に位置特定しなければならない。この位置特定を照合とも称する。
【０００４】
実際に交通網の一部を照合する際には、区間の（形状）点の座標がディジタル化された第１の地図を有する符号化側において符号化され、所定の属性と共に復号化システムに伝送され、この復号化システムがディジタル化された第２の地図にアクセスする。この座標および属性に基づき、対応する区間が復号化側において同定される。伝送されるべきこの座標は部分的に等間隔になり、また部分的に所定のアルゴリズムを用いて、例えばダグラスポイカー（Douglas-Peuker）アルゴリズムを用いて選択される。復号のために受信器側の地図のデータを用いて相関が計算される。伝送された座標は所定の範囲内でシフトされる。最大値においては正確なシフトが想定され、このシフトは属性に基づき証明される。したがって区間の一義的な同定が実現される。
【０００５】
更なる属性を使用しなければ、例えば並行車線を区別することができないので、復号は十分でないことが多い。しかしながら走行方向などの更なる属性を考慮したとしても一義的な最大値を検出できない可能性がある。付加的に、相関化された点を通るルートは復号化器の動作時間を延ばす。しかしながらこのことは、最初のステップにおけるそれらの点の相関化の際にはトポロジを考慮することができないので不可欠である。したがって、本来隣接している点が道路網の異なる道路に置かれてしまう可能性がある。さらには伝送すべき点が多数ある場合データ量は非常に急増するが、道路が幾つかある場合には正確な同定のために点は複数なくてはならない。
【０００６】
したがって本発明の課題は、ディジタル化された地図における区間を同定するための改善された方法を提供することである。
【０００７】
この課題は、請求項１の特徴を有する方法によって解決される。
【０００８】
本発明によれば、冒頭で述べたような方法において、起源ルート点が第１の地図における区間に関して規定され、この起源ルート点の座標が検出される。起源ルート点から出発して複数のブランチからなる起源ツリー構造が形成され、この起源ツリー構造のツリー点は、それらのツリー点が第１の地図における交通路のそれぞれの点に対応するように配置されている。照合ルート点は第２の地図において起源ルート点の座標の近傍において規定され、同様にして照合ツリー構造が照合ルート点に基づき複数のブランチから形成され、この照合ツリー構造のツリー点は、それらのツリー点が第２の地図における交通路のそれぞれの点に対応するように配置されている。起源ツリー構造および照合ツリー構造は相互に比較され、別の照合ルート点が別の照合ツリー構造を形成するために規定され、これは照合ツリー構造と起源ツリー構造の所定の一致が達成されるまで行われる。続いて区間が第２の地図における照合ルート点を参照する区間が、第１の地図における起源ルート点についての区間の参照に基づき検出される。
【０００９】
ツリー構造を形成することによって、検索すべき区間を含んでいる第１の地図内の交通網の対応する区間が地図データから取り出され抽出されて表示される。したがって異なるディジタル化された地図における交通網の極僅かな差異によりそれぞれのツリー構造の最小限の変更しか生じない。全く同じツリー構造は同一のルート点における同一の地図データに関してしか考えられないので、所定量の差異内での２つのツリー構造の一致は、本発明による照合ツリー構造と起源ツリー構造との比較にとって十分である。したがって地図情報を部分毎に相互に比較することができ、２つの地図における交通網の所定の区間を位置特定することができる。
【００１０】
有利には、起源ルート点および／または照合ルート点は交通網のそれぞれ１つの点に対応する。このようにして、ツリー構造を規定する全ての点が道路ないし交通路上に存在することが達成される。
【００１１】
第１の地図に関するツリー構造と第２の地図に関するツリー構造をより簡単に相互に比較するために、有利にはツリー点に対応する交通路の点は、ルート点または他の例えば隣接するツリー点に対応する交通路の他の点までの所定の区間距離を有するように配置されている。
【００１２】
有利には区間距離を事前に決定することができる。択一的に、区間距離を区間の長さに依存して決定することができる。これによって、ツリー構造の拡張部が同定すべき区間の拡張部とそれぞれ所定の関係にあることが達成される。
【００１３】
並行する車線も正確に同定できるようにするために有利には、対応するルート点から出発して到達することができるツリー点のみが考慮される。すなわちこの場合には、分岐規則、法定上定められた走行方向（一方通行道路）および別の交通規則が一緒に考慮される。
【００１４】
さらに有利には、所定の交通路クラスの交通路上の点に対応するツリー点のみが考慮される。このことは、場合によっては存在する裏通りないし脇道における複数のツリー点に起因する複雑なツリー構造を回避する。
【００１５】
有利には起源ツリー構造がバイナリに符号化され伝送される。これにより伝送すべき伝送量を低減することができる。
【００１６】
以下では、添付の図面を参照しながら本発明の実施例を詳細に説明する。ここで、
図１は、相互に比較される２つの概略的な地図を示す。
図２は、選択された区間を有する第１の地図の一部を概略的に示す。
図３および図４は、図２に示されている区間を位置特定するための第２の地図の一部を概略的に示す。
図５ａから図５ｃはそれぞれ、図２から図４のツリー構造を概略的に示す。
図６は、別の区間を有する第１の地図の一部を概略的に示す。
図７は、図６に示されている区間を位置特定するための第２の地図の対応する部分を示す。
【００１７】
図１には、交通網ないし道路網の一部であり位置特定されるべき区間２が存在する地図１が示されている。アプリケーション３、例えば交通管理局は例えばこの区間２内の交通渋滞および／または工事現場を通知するために地図１にアクセスする。本発明による別の考えられる用途は、観光ポイント、例えばレストランおよび／またはホテルの位置の照合、またはディジタル化された地図への新たな地図データの挿入である。アプリケーション３は以下において説明する本発明による方法を用いて、区間２を同定するための相応の道路情報を符号化し、符号化されたデータを適切な送信装置４に引渡す。
【００１８】
続いて、送信装置４は符号化された道路データを受信装置５に伝送する。図１においてはジグザグの線６によって示されている伝送は無線伝送でよく、例えばＵＫＷ送信器ＲＤＳ（Radio Data System）のためのディジタルデータ伝送システムを介して行うことができる。さらに、ＤＡＢ（Digital Audio Broadcasting）、インターネットまたは通信コネクションを介する伝送も考えられる。
【００１９】
受信装置５は符号化されたデータをアプリケーション７に転送し、このアプリケーション７は受信したデータを復号する。アプリケーション７は道路地図８にアクセスし、この地図８における対応する区間９の位置特定を行う。アプリケーション７として例えばナビゲーションシステムが考えられる。ナビゲーションシステムはここで交通ニュースをルート計画および目的地案内の際に考慮することができる。
【００２０】
図２は、道路網１１を有する第１の地図１０を拡大して概略的に示す。道路網１１においては破線で区間１２がマーキングされており、この区間１２が他のマップ（図３ないし図４）において位置特定されるべきである。区間１２内では先ず起源ルート点１３が規定され、この起源ルート点１３は道路網１１における交点に対応する。起源ルート点１３は有利には交点上に位置するか、少なくともその交点の近傍に位置する。何故ならば、形成すべきツリー構造の特性は交差する道路の数が増えるに連れ高まるからである。しかしながら道路上の他のあらゆる点またはその道路から離れた点も選択することができる。
【００２１】
起源ルート点１３から出発して先ずツリー点１４ａが規定され、このツリー点１４ａは道路網１１上において起源ルート点１３から所定の距離を有する点に対応する。続いてこのツリー点１４ａから出発して同様にツリー点１５が規定され、また後続のステップではツリー点１６ｂ，１６ｃおよび１６ａが規定される。ツリー点を選択する際には、考察する線から北に向かってツリー点は時計回りに連続して選択される。
【００２２】
ブランチ線が最後のツリー点、この実施例ではツリー点１６ａに達している場合には、１つ前のツリー点、この実施例ではツリー点１５ａから時計回りで別のツリー点、この実施例では１６ｂが規定される。これらのステップは、ツリー点１５ａから別のツリー点に達しなくなるまで繰り返される。
【００２３】
ツリー点１６ａ，１６ｂおよび１６ｃはそれぞれ道路点に対応しており、これらの点は全て起源ルート点１３に対応する道路点から同一の距離を有する。起源ルート点１３からツリー点１４ａを介するツリー点１５までの結合、さらにはツリー点１６ａ，１６ｂおよび１６ｃまでの結合を段階的に行うことによって、起源ツリー構造に関する第１のブランチが形成される。
【００２４】
同等のやり方で、起源ルート点１３から出発してツリー点１７ａおよび１７ｂならびに１８ａおよび１８ｂを有するツリー構造の第２のブランチが形成される。生じたツリー構造の第３のブランチはツリー点１９ａおよび１９ｂならびにそれに続く４つのツリー点２０ａ，２０ｂ，２０ｃおよび２０ｄを有する。このようにして形成されたツリー構造が図５に示されている。分かりやすくするために起源ルート点１３にのみ参照番号を付している。個々のツリー点は基礎となる道路網を考慮せずに相互に接続され、これによって道路網から取り出され抽出された表示が得られる。
【００２５】
ツリー構造を構築するために、起源ルート点の選択後には所期の間隔を置いて、分岐した道路上に１つのツリー点がセットされる。選択された間隔は例えばルート点から測定して５０ｍ，１００ｍおよび２００ｍにある。例えば、起源ルート点１３から出発してそれぞれの終端点１６ａ〜１６ｃ，１８ａおよび１８ｂならびに２０ａ〜２０ｄまでの全てのブランチが順に分岐され、起源ルート点１３から遠ざかる各ステップに対しては１が記録され、起源ルート点１３へと戻る各ステップに対しては０が記録されることによってツリー構造を適切に符号化することができる。
【００２６】
これによりこの実施例においては、起源ルート点１３から第１のツリー点１４までのステップに関して１が１回現われ、またツリー点１５を介してツリー点１６ａに達するためにはさらに１が２回現われる。ツリー点１６ａからはツリー点１５に戻らなければならないので、したがって０が記録される。連続してツリー点１６ｂと１６ｃに達するためには結果１０１が規定される。さらに３ステップ戻ると、すなわち３回続けて０が現われると再び起源ルート点１３に達する。同様にして、最終的に再び起源ルート点１３に達するまでには別の２つのブランチが分岐される。この実施例における全体的な結果は1110101000111001100011100110101000である。この文字列が起源ルート点１３の地理座標、また必要に応じて区間１２を限定するためのさらなる属性および長さ属性と共に伝送される。
【００２７】
図３は第２の地図２１の一部を示し、この部分は図２に示されている地図部分１０に実質的に対応するが、道路網１１ではなく道路網２２が表示されている。つまり道路２３はこの地図部分２１においては２車線に構成されており、この道路２３は図２の地図部分１０においては単に１車線として示されている。２つの道路網１１および１２の別の相違点は相応の図面から見て取れる。
【００２８】
図２に示されている起源ルート点１３の地理座標は伝達されているので、図３の地図部分２１においては照合ルート点２４が規定され、この照合ルート点２４は伝達された地理座標の近傍に存在する。照合ルート点２４から出発して、図２を参照しながら説明したようにして、図２のツリー点１４ａ，１４ｂおよび１４ｃにほぼ対応するツリー点２５ａ，２５ｂおよび２５ｃを有する第２のツリー構造が構築される。
【００２９】
ツリー点２５ａから出発して、ツリー点２６，２７ａ，２７ｂおよび２７ｃを有する第１のブランチが延びる。ツリー点２５ｂから始まる第２のブランチはツリー点２８，２９ａおよび２９ｂを有するように延びる。最後に、ツリー点２５ｃから始まる第３のブランチはツリー点３０，３１ａ，３１ｂ，３１ｃ，３１ｄ，３１ｅおよび３１ｆを有するように延びる。形成されたツリー構造が図５ｂに概略的に示されている。図５ａに示されている起源ツリー構造と図５ｂの照合ツリー構造とを比較するとこれらのツリー構造が著しく異なることが分かる。つまりツリー構造の十分な一致は達成されていない。
【００３０】
図４には、図３の道路網２２を有する地図部分２１が再び示されている。図４においては道路網２２上に別の照合ルート点３２が規定され、この照合ルート点３２から出発して別の第３のツリー構造が形成される。第３のツリー構造はツリー点３３，３４，３５ａ，３５ｂおよび３５ｃを有する第１のブランチを有する。第２のブランチはツリー点３６，３７ａ，３７ｂ，３８ａおよび３８ｂを有する。最後に第３のブランチはツリー点３９，４０ａ，４０ｂならびに４１ａ，４１ｂ，４１ｃ，４１ｄ，４１ｅおよび４１ｆを有する。
【００３１】
形成された第３のツリー構造が図５ｃに概略的に示されている。図５ｃのツリー構造と図５ａのツリー構造を比較すると、それぞれの第１のブランチはほぼ同一であり、第３のブランチは端部領域においてのみ僅かに相違していることが分かる。この相違は、図３および図４における道路２３が２車線で考慮されるが、これに対し図２において対応する道路は１車線として示されていることに起因する。
【００３２】
続いて区間４２が図４における照合ルート点３２を参照して、図２における起源ルート点１３についての区間１２の参照に基づき検出される。
【００３３】
２つの並行な車線を有する道路においては対向する走行方向に関して、一方の車線にのみ関与する区間を一義的に同定できるようにするために、ツリー構造を形成する際には、分岐規則および他の交通規則を考慮する際にもルート点から道路の相応の点に到達することができる、もしくは向かうことができる場合にのみツリー点はセットされる。付加的に、ルート点からの距離が長くなるにつれ、同等の道路クラスまたはより高い道路クラスの道路のみが考慮されるようにツリー点の選択を制限することができる。このことは、細い裏通りまた場合によっては重要でない裏通りに起因する複雑なツリー構造を回避する。
【００３４】
さらには、照合された区間が第２の地図ないし復号化側の地図内に存在しない場合には、検索された区間が存在する領域を例えば伝送すべきパターン要素を用いて表すことができる。これによって、非常に多くの量のデータを伝送する必要なく、接している道路を同定することにより復号化側における地図データの補完が実現される。この補完を図６および図７に基づき詳細に説明する。
【００３５】
図６には、図２の交通網１１を有する地図部分１０が示されている。交通網１１はＦ字型に近い裏通りの配置構成４３を有する。図６においてはやはり起源ルート点１３から出発してツリー構造が形成される。このツリー構造は実質的に図５ａに概略的に示したツリー構造に対応する。図７には、道路網２２を有する地図部分２１が再び示されている。図６における裏通りの配置構成４３は図７には存在していないことがはっきりと見て取れる。
【００３６】
起源ルート点１３の伝送された座標に基づき、地図部分２１においては照合ルート点３２が決定され、この照合ルート点３２から出発して図６のツリー構造と十分に一致するツリー構造を形成することができる。続いてパターン４４内に存在する地図情報を図７の道路網２２に置くことができる。したがってこのようにして図７に示されている地図２１を形成することができる。
【図面の簡単な説明】
【００３７】
【図１】相互に比較される２つの概略的な地図を示す。
【図２】選択された区間を有する第１の地図の一部を概略的に示す。
【図３】図２に示されている区間を位置特定するための第２の地図の一部を概略的に示す。
【図４】図２に示されている区間を位置特定するための第２の地図の一部を概略的に示す。
【図５ａ】図２から図４のツリー構造を概略的に示す。
【図５ｂ】図２から図４のツリー構造を概略的に示す。
【図５ｃ】図２から図４のツリー構造を概略的に示す。
【図６】別の区間を有する第１の地図の一部を概略的に示す。
【図７】図６に示されている区間を位置特定するための第２の地図の対応する部分を示す。
【特許請求の範囲】
【請求項１】
交通網のディジタル化された第１の地図に由来する所定の区間を交通網のディジタル化された第２の地図内で位置特定するための方法において、
前記第１の地図における前記区間に関連する起源ルート点を規定し、該起源ルート点の座標を検出し、
前記起源ルート点から出発して複数のブランチからなる起源ツリー構造を形成し、前記起源ツリー構造のブランチのツリー点を、該ツリー点が前記第１の地図における交通網の点にそれぞれ対応するように配置し、
前記第２の地図において照合ルート点を、前記起源ルート点の前記座標の近傍に規定し、前記照合ルート点から出発して複数のブランチからなる照合ツリー構造を形成し、前記照合ツリー構造のブランチのツリー点を、該ツリー点が前記第２の地図における交通網の点にそれぞれ対応するように配置し、
前記起源ツリー構造と前記照合ツリー構造を比較し、前記照合ツリー構造と前記起源ツリー構造との所定の一致が達成されるまで別の照合ルート点を規定し、
前記第１の地図における前記起源ルート点についての区間の参照に基づき、前記第２の地図における前記照合ルート点に関する区間を検出することを特徴とする、方法。
【請求項２】
前記起源ルート点および／または前記照合ルート点は前記交通網のそれぞれ１つの点に対応する、請求項１記載の方法。
【請求項３】
前記交通網の前記ツリーに対応する点が、前記ルート点または他のツリー点に対応する前記交通網の点まで所定の区間距離を有するよう前記ツリー点を規定する、請求項１または２記載の方法。
【請求項４】
前記区間距離は事前に決定されている、請求項３記載の方法。
【請求項５】
前記区間距離を前記区間の長さに依存して決定する、請求項３記載の方法。
【請求項６】
対応するルート点から出発して到達可能であるツリー点のみを考慮する、請求項１から５までのいずれか１項記載の方法。
【請求項７】
所定の交通路クラスの交通路上の点に対応するツリー点のみを考慮する、請求項１から６までのいずれか１項記載の方法。
【請求項８】
前記起源ツリー構造をバイナリに符号化し伝送する、請求項１から７までのいずれか１項記載の方法。
【請求項１】
交通網のディジタル化された第１の地図に由来する所定の区間を交通網のディジタル化された第２の地図内で位置特定するための方法において、
前記第１の地図における前記区間に関連する起源ルート点を規定し、該起源ルート点の座標を検出し、
前記起源ルート点から出発して複数のブランチからなる起源ツリー構造を形成し、前記起源ツリー構造のブランチのツリー点を、該ツリー点が前記第１の地図における交通網の点にそれぞれ対応するように配置し、
前記第２の地図において照合ルート点を、前記起源ルート点の前記座標の近傍に規定し、前記照合ルート点から出発して複数のブランチからなる照合ツリー構造を形成し、前記照合ツリー構造のブランチのツリー点を、該ツリー点が前記第２の地図における交通網の点にそれぞれ対応するように配置し、
前記起源ツリー構造と前記照合ツリー構造を比較し、前記照合ツリー構造と前記起源ツリー構造との所定の一致が達成されるまで別の照合ルート点を規定し、
前記第１の地図における前記起源ルート点についての区間の参照に基づき、前記第２の地図における前記照合ルート点に関する区間を検出することを特徴とする、方法。
【請求項２】
前記起源ルート点および／または前記照合ルート点は前記交通網のそれぞれ１つの点に対応する、請求項１記載の方法。
【請求項３】
前記交通網の前記ツリーに対応する点が、前記ルート点または他のツリー点に対応する前記交通網の点まで所定の区間距離を有するよう前記ツリー点を規定する、請求項１または２記載の方法。
【請求項４】
前記区間距離は事前に決定されている、請求項３記載の方法。
【請求項５】
前記区間距離を前記区間の長さに依存して決定する、請求項３記載の方法。
【請求項６】
対応するルート点から出発して到達可能であるツリー点のみを考慮する、請求項１から５までのいずれか１項記載の方法。
【請求項７】
所定の交通路クラスの交通路上の点に対応するツリー点のみを考慮する、請求項１から６までのいずれか１項記載の方法。
【請求項８】
前記起源ツリー構造をバイナリに符号化し伝送する、請求項１から７までのいずれか１項記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５ａ】
【図５ｂ】
【図５ｃ】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５ａ】
【図５ｂ】
【図５ｃ】
【図６】
【図７】
【公表番号】特表２００９−５０６３８８（Ｐ２００９−５０６３８８Ａ）
【公表日】平成２１年２月１２日（２００９．２．１２）
【国際特許分類】
【出願番号】特願２００８−５４４９２６（Ｐ２００８−５４４９２６）
【出願日】平成１８年１１月２２日（２００６．１１．２２）
【国際出願番号】ＰＣＴ／ＥＰ２００６／０６８７５９
【国際公開番号】ＷＯ２００８／０６１５６１
【国際公開日】平成２０年５月２９日（２００８．５．２９）
【出願人】（３９００２３７１１）ローベルト ボツシユ ゲゼルシヤフト ミツト ベシユレンクテル ハフツング (2,908)
【氏名又は名称原語表記】ＲＯＢＥＲＴ ＢＯＳＣＨ ＧＭＢＨ
【住所又は居所原語表記】Ｓｔｕｔｔｇａｒｔ， Ｇｅｒｍａｎｙ
【Ｆターム（参考）】
【公表日】平成２１年２月１２日（２００９．２．１２）
【国際特許分類】
【出願日】平成１８年１１月２２日（２００６．１１．２２）
【国際出願番号】ＰＣＴ／ＥＰ２００６／０６８７５９
【国際公開番号】ＷＯ２００８／０６１５６１
【国際公開日】平成２０年５月２９日（２００８．５．２９）
【出願人】（３９００２３７１１）ローベルト ボツシユ ゲゼルシヤフト ミツト ベシユレンクテル ハフツング (2,908)
【氏名又は名称原語表記】ＲＯＢＥＲＴ ＢＯＳＣＨ ＧＭＢＨ
【住所又は居所原語表記】Ｓｔｕｔｔｇａｒｔ， Ｇｅｒｍａｎｙ
【Ｆターム（参考）】
[ Back to top ]