(57)【要約】【課題】形状データをテキスト形式に符号化することのできる形状データ符号化装置および形状データ符号化方法を提供すること。【解決手段】統計的に偏りを持つ形状データを得るため、地図データから所定の道路区間を一定の距離を持つリサンプリング区間長Ｌで等間隔にサンプリングする。したがって、各相対ノードにおける絶対方位の変位差、すなわち、偏角θと偏角統計予測値Ｓ（偏角で表した予測値）との差分（以下「予測値差分」という。）Δθを算出して、当該予測値差分Δθを各相対ノードの角度情報としている。そして、予測値差分Δθを相対ノード順に並べたデータ列に文字コードを割り当てることで、相対ノードの角度情報をテキスト形式に符号化する。【選択図】    図４
2004252651.tif 000002
【特許請求の範囲】
【請求項１】
マップマッチングで形状を特定するためのデジタル地図上の形状ベクトルを表すデータ（以下「形状データ」という。）をテキスト形式に符号化する形状データ符号化装置であって、
前記形状ベクトルを構成する各ノードの位置情報に算術加工を施して、前記位置情報を統計的に偏りを持つデータに変換し、
前記統計的に偏りを持つデータの内、統計的に強い偏りを持つ値の少なくとも１つから構成されるデータ列が１つの文字コードに対応する符号表を用いて、前記データをテキスト形式に符号化することを特徴とする形状データ符号化装置。
【請求項２】
前記形状ベクトルは、隣接するノードからの距離が等間隔となる位置に各ノードをリサンプルし、
前記統計的に偏りを持つデータは、前記リサンプルされた形状ベクトルを構成する各ノードの角度情報であることを特徴とする請求項１記載の形状データ符号化装置。
【請求項３】
前記角度情報を、前記隣接するノードから延びる直線の偏角で表し、
前記偏角をテキスト形式に符号化することを特徴とする請求項２記載の形状データ符号化装置。
【請求項４】
前記角度情報を、前記隣接するノードから延びる直線の偏角と偏角統計予測値との差分（以下「予測値差分」という。）で表し、
前記予測値差分をテキスト形式に符号化することを特徴とする請求項２記載の形状データ符号化装置。
【請求項５】
複数のノードから構成されるデジタル地図上の形状ベクトルを表すデータ（以下「形状データ」という。）をテキスト形式に符号化する形状データ符号化方法であって、
前記形状ベクトルを構成する各ノードの位置情報に算術加工を施して、前記位置情報を統計的に偏りを持つデータに変換し、
前記統計的に偏りを持つデータの内、統計的に強い偏りを持つ値の少なくとも１つから構成されるデータ列が１つの文字コードに対応する符号表を用いて、前記データをテキスト形式に符号化することを特徴とする形状データ符号化方法。
【請求項６】
前記形状ベクトルは、隣接するノードからの距離が等間隔となる位置に各ノードがリサンプルされており、
前記統計的に偏りを持つデータは、前記リサンプルされた形状ベクトルを構成する各ノードの角度情報であることを特徴とする請求項５記載の形状データ符号化方法。
【請求項７】
前記角度情報を、前記隣接するノードから延びる直線の偏角で表し、
前記偏角をテキスト形式に符号化することを特徴とする請求項６記載の形状データ符号化方法。
【請求項８】
前記角度情報を、前記隣接するノードから延びる直線の偏角と偏角統計予測値との差分（以下「予測値差分」という。）で表し、
前記予測値差分をテキスト形式に符号化することを特徴とする請求項６記載の形状データ符号化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、形状データをテキスト形式に符号化する形状データ符号化装置および形状データ符号化方法に関する。
【０００２】
【従来の技術】
車両等に利用されるカーナビゲーションシステムは、デジタル地図データベースを利用して、ＧＰＳ受信機で受信した情報から算出された位置データに基づき自車位置周辺の地図を画面に表示したり、走行軌跡や目的地までの経路探索結果を地図上に併せて表示する機能を有している。また、事故情報や渋滞情報等の交通情報の提供を受けて、事故が発生した地点や渋滞区間等を地図上に表示し、また旅行時間等を活用して経路誘導を行う機能も有している。
【０００３】
当該システムで利用されるデジタル地図データベースには、図１に示すように、道路区間を表すことのできるノード１１およびリンク１３について記憶されている。ノード１１とは、交差点や境界線等の地図上における目安となる地点であり、その位置が緯度・経度等によって表されている。なお、ノードに関する情報として、道路等を示すためにリンクされる他のノードとの接続関係についても記憶されている。また、リンク１３とはノード間を結ぶ線である。
【０００４】
当該システムでは、事故が発生した地点や渋滞区間等を地図上に表示するために、デジタル地図データベースに記憶されている地図データから所定の道路区間等を示す「形状ベクトル」が生成され、事故や渋滞等の事象情報と共に各車両に配信される。形状ベクトルは、図２に示すように、形状ベクトル列識別番号、道路等のベクトルデータ種別、および形状ベクトルを構成するノード総数やノード番号、各ノードの絶対座標（緯度・経度）または相対位置等を示すデータから構成されている。なお、形状ベクトルを構成するノードには２種類ある。一つは、道路区間中のいくつかの点を絶対位置（絶対緯度・経度および絶対方位）で表した「基点ノード」であり、もう一つは、隣接するノードとの相対位置で表した「相対ノード」である。なお、各ノードは、地図上の道路区間をサンプリングすることによって得られる。
【０００５】
従来の形状ベクトルでは、統計的に偏りを持つ形状データを得るため、図３に示すように、道路形状（元の形状）を一定の距離を持つリサンプリング区間長Ｌで等間隔にサンプリングすることがあった。この場合、各ノード間の距離は一定値Ｌであるため、各相対ノードの位置情報としては角度情報のみで良く、形状ベクトルのデータサイズを削減できるといった効果がある。当該角度情報には、大きく分けて図３の（ａ），（ｂ），（ｃ）に示す３種類がある。
【０００６】
まず、図３（ａ）に示すように、各相対ノードの真北（図の上方）の方位を０度とし、時計回りに０〜３６０度の範囲で大きさを指定する「絶対方位」による角度θで表すことができる。但し、この場合は、図３（ａ′）に示すように、角度θの発生頻度に統計的な偏りは現れない。また、図３（ｂ）に示すように、各相対ノードにおける絶対方位の変位差、すなわち、偏角θによって表すこともできる。この場合、直線的な道路が多い地域では、図３（ｂ′）に示すように、偏角θの発生頻度はθ＝０°に極大が現れる。
【０００７】
さらに、図３（ｃ）に示すように、各相対ノードにおける偏角θと偏角統計予測値Ｓ（偏角で表した予測値）との差分（以下「予測値差分」という。）Δθにより表すこともできる。偏角統計予測値Ｓとは、着目する相対ノードＰＪの偏角θｊを、それ以前の相対ノードＰＪ−１までの偏角を用いて推定した値である。道路形状は、直線や緩やかに曲がる曲線がほとんどであるため、偏角θの予測値差分Δθは０°付近に集中し、図３（ｃ′）に示すように、各相対ノードを示す予測値差分Δθの発生頻度は、Δθ＝０°を中心に強い偏りを見せる。
【０００８】
従来では、こうして得られた角度情報の特に偏角θの予測値差分Δθに対して、予測値差分Δθの値に応じた０，１から成る符号を割り当てることで可変長符号化を行っている。図６は、予測値差分Δθに対して割り当てる符号表の例を示す説明図である。同図に示すように、Δθ＝０は“０”に符号化し、Δθ＝＋１は符号１００に＋を表す付加ビット０を加えて１０００に符号化し、Δθ＝−１は符号１００に−を表す付加ビット１を加えて１００１に符号化する。
【０００９】
このように、形状データに算術加工を施して統計的な偏りを持たせた後、可変長符号化することにより、形状ベクトルのデータ量を削減することができる。具体的な例としては、相対ノードは１ノード当たり３〜６ビット程度で表すことができ、特に０°周辺は可変長符号化を行えば１〜３ビット程度で表すことができる。
【００１０】
【特許文献１】
国際公開第０２／０９１５８７号パンフレット
【００１１】
【発明が解決しようとする課題】
ところで、上記説明した従来技術によって得られる形状データはバイナリ形式である。しかし、一方で、形状データをテキスト形式で表現する方式も望まれていた。
【００１２】
本発明は、上記従来の要望に鑑みてなされたものであって、形状データをテキスト形式に符号化することのできる形状データ符号化装置および形状データ符号化方法を提供することを目的としている。
【００１３】
【課題を解決するための手段】
上記目的を達成するために、本発明に係る形状データ符号化装置は、マップマッチングで形状を特定するためのデジタル地図上の形状ベクトルを表すデータ（以下「形状データ」という。）をテキスト形式に符号化する形状データ符号化装置であって、前記形状ベクトルを構成する各ノードの位置情報に算術加工を施して、前記位置情報を統計的に偏りを持つデータに変換し、前記統計的に偏りを持つデータの内、統計的に強い偏りを持つ値の少なくとも１つから構成されるデータ列が１つの文字コードに対応する符号表を用いて、前記データをテキスト形式に符号化する。したがって、形状データをテキスト形式に符号化することができる。
【００１４】
また、本発明に係る形状データ符号化装置は、前記形状ベクトルは、隣接するノードからの距離が等間隔となる位置に各ノードをリサンプルし、前記統計的に偏りを持つデータは、前記リサンプルされた形状ベクトルを構成する各ノードの角度情報であることが望ましい。
【００１５】
また、本発明に係る形状データ符号化装置は、前記角度情報を、前記隣接するノードから延びる直線の偏角で表し、前記偏角をテキスト形式に符号化することが望ましい。
【００１６】
また、本発明に係る形状データ符号化装置は、前記角度情報を、前記隣接するノードから延びる直線の偏角と偏角統計予測値との差分（以下「予測値差分」という。）で表し、前記予測値差分をテキスト形式に符号化することが望ましい。
【００１７】
また、本発明に係る形状データ符号化方法は、複数のノードから構成されるデジタル地図上の形状ベクトルを表すデータ（以下「形状データ」という。）をテキスト形式に符号化する形状データ符号化方法であって、前記形状ベクトルを構成する各ノードの位置情報に算術加工を施して、前記位置情報を統計的に偏りを持つデータに変換し、前記統計的に偏りを持つデータの内、統計的に強い偏りを持つ値の少なくとも１つから構成されるデータ列が１つの文字コードに対応する符号表を用いて、前記データをテキスト形式に符号化する。
【００１８】
また、本発明に係る形状データ符号化方法は、前記形状ベクトルは、隣接するノードからの距離が等間隔となる位置に各ノードがリサンプルされており、前記統計的に偏りを持つデータは、前記リサンプルされた形状ベクトルを構成する各ノードの角度情報である。
【００１９】
また、本発明に係る形状データ符号化方法は、前記角度情報を、前記隣接するノードから延びる直線の偏角で表し、前記偏角をテキスト形式に符号化する。
【００２０】
さらに、本発明に係る形状データ符号化方法は、前記角度情報を、前記隣接するノードから延びる直線の偏角と偏角統計予測値との差分（以下「予測値差分」という。）で表し、前記予測値差分をテキスト形式に符号化する。
【００２１】
【発明の実施の形態】
以下、本発明に係る形状データ符号化装置および形状データ符号化方法の実施の形態について、図面を参照して詳細に説明する。なお、以下の説明では、形状ベクトルを生成して本実施形態の形状データ符号化方法によって形状ベクトルを表すデータ（以下「形状データ」という。）を符号化する形状データ符号化装置を有するエンコーダと、各車両に搭載された形状ベクトル等に基づいて所定の処理を行うデコーダとを備えたカーナビゲーションシステムについて説明する。
【００２２】
当該カーナビゲーションシステムでは、デコーダが、エンコーダから事故情報や渋滞情報等の交通情報の提供を受けて、事故が発生した地点や渋滞区間等を地図上に表示するといった機能を有している。このため、エンコーダは、デジタル地図データベースに記憶されている地図データから所定の道路区間等を示す「形状ベクトル」を生成し、事故や渋滞等の事象情報と共に各車両のデコーダに配信している。
【００２３】
なお、当該システムで利用されるデジタル地図データベースには、図１に示すように、道路区間を表すことのできるノード１１およびリンク１３について記憶されている。ノード１１とは、交差点や境界線等の地図上における目安となる地点であり、その位置が緯度・経度等によって表されている。なお、ノードに関する情報として、道路等を示すためにリンクされる他のノードとの接続関係についても記憶されている。また、リンク１３とはノード間を結ぶ線である。
【００２４】
形状ベクトルは、図２に示すように、形状ベクトル列識別番号、道路等のベクトルデータ種別、および形状ベクトルを構成するノード総数やノード番号、各ノードの絶対座標（緯度・経度）または相対位置等を示すデータから構成されている。また、当該形状ベクトルを構成するノードには２種類ある。一つは、道路区間中のいくつかの点を絶対位置（絶対緯度・経度および絶対方位）で表した「基点ノード」であり、もう一つは、隣接するノードとの相対位置で表した「相対ノード」である。なお、各ノードは、地図上の道路区間をサンプリングすることによって得られる。
【００２５】
本実施形態では、統計的に偏りを持つ形状データ（形状ベクトルのデータ）を得るため、図３に示すように、デジタル地図データベースに記憶されている地図データから所定の道路区間を一定の距離を持つリサンプリング区間長Ｌで等間隔にサンプリングする。したがって、各相対ノードの位置情報としては角度情報のみで良いが、本実施形態では、各相対ノードにおける絶対方位の変位差、すなわち、偏角θと偏角統計予測値Ｓ（偏角で表した予測値）との差分（以下「予測値差分」という。）Δθを算出して、当該予測値差分Δθを各相対ノードの角度情報としている。
【００２６】
偏角統計予測値Ｓとは、着目する相対ノードＰＪの偏角θｊを、それ以前の相対ノードＰＪ−１までの偏角を用いて推定した値である。道路形状は、直線や緩やかに曲がる曲線がほとんどであるため、偏角θの予測値差分Δθは０°付近に集中し、図３（ｃ′）に示すように、各相対ノードを示す予測値差分Δθの発生頻度は、Δθ＝０°を中心に強い偏りを見せる。したがって、角度情報の多くは予測値差分Δθ＝０，±１といった値となる。
【００２７】
本実施形態では、当該角度情報としての予測値差分Δθを相対ノード順に並べたデータ列に文字コードを割り当てることで、相対ノードの角度情報をテキスト形式に符号化する。図４は、本実施形態の予測差分値Δθに対して割り当てる符号表の例を示す説明図である。同図に示すように、予測値差分Δθのデータ列“０”を文字コードＡに符号化し、“＋１”をＢに符号化し、“−１”をＣに符号化し、“０，０”をＤに符号化し、“０，＋１”をＥに符号化し、“０，−１”をＦに符号化し、“＋１，０”をＧに符号化し、“−１，０”をＨに符号化する。また、予測差分値Δθがこれら以外の任意値に対しては、文字コードＸに加えて＋または−と３桁の数字で表す文字列に符号化する。
【００２８】
また、等間隔リサンプリングの区間長Ｌを示すデータには、区間長変更コードＹに加えて１桁の数字で表す文字列に符号化する。当該１桁の数字とは、例えば、区間長Ｌ＝２０ｍのときは“１”、Ｌ＝４０ｍのときは“２”といったように、区間長Ｌに応じて予め決められた値である。さらに、形状データの最後尾にはＥＯＤ（Ｅｎｄ  Ｏｆ  Ｄａｔａ）コードＺを付け加える。
【００２９】
例えば、２６個の相対ノードの角度情報が順に並んだデータ列「０，０，０，０，０，−１，−１，０，＋１，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，−４２，０」は、図４に示した符号表によれば「００，００，０−１，−１０，＋１０，００，００，００，００，００，００，００，−４２，０」と分けることができるため、「ＤＤＦＨＧＤＤＤＤＤＤＤＸ−０４２Ａ」といったテキスト形式の文字列に符号化される。
【００３０】
また、基点ノードは、上述したように絶対位置（絶対緯度・経度および絶対方位）で表され、数値はそのまま文字コードで表すことができるため、北緯と南緯、東経と西経を区別するための１文字（＋または−）を緯度情報および経度情報に追加する。なお、絶対方位は、基点ノードの真北の方位を０度とし、時計回りに０〜３６０度の範囲で表されるため、数値をそのまま文字コードで表す。
【００３１】
したがって、基点ノードの位置が北緯３５°５３′２３″９、東経１３５°１５′４３″２、次の相対ノードへの絶対方位が１４３°であり、区間長Ｌ＝４０ｍで等距離リサンプルされた相対ノードの角度情報が「０，０，０，０，０，−１，−１，０，＋１，０，０，０，０，０，０，０，０，０，０，０，０，０，０，０，−４２，０」の形状ベクトルに対しては、「＋１３５１５４３２＋３５５３２３９１４３Ｙ２ＤＤＦＨＧＤＤＤＤＤＤＤＸ−０４２ＡＺ」といったテキスト形式の文字列に符号化される。すなわち、上記文字列は「＋１３５１５４３２，＋３５５３２３９，１４３，Ｙ２ＤＤＦＨＧＤＤＤＤＤＤＤＸ−０４２Ａ，Ｚ」と分けることができ、「＋１３５１５４３２」は基点ノードの緯度情報、「＋３５５３２３９」は基点ノードの経度情報、「１４３」は基点ノードの絶対方位情報、「Ｙ２ＤＤＦＨＧＤＤＤＤＤＤＤＸ−０４２Ａ」は相対ノードの位置情報、「Ｚ」はＥＯＤコードを示している。
【００３２】
このように、テキスト形式に符号化された形状データは、事故や渋滞等の事象情報と共にエンコーダから各車両のデコーダに配信される。デコーダ側では、受信した形状データを図４に示した符号表の規則に従って形状データを復号化し、デコーダが有するデジタル地図データベースに記憶されている地図データと復号化した形状データが示す形状ベクトルとをマップマッチングした後、形状ベクトルを地図に重ねて表示する。
【００３３】
図５は、以上説明した本実施形態のカーナビゲーションシステムを示す構成図である。本実施形態のカーナビゲーションシステムは、同図に示すように、エンコーダ２００とデコーダ３００とを備えて構成されており、後述する形状データをエンコーダ２００からデコーダ３００に送信する。
【００３４】
なお、エンコーダ２００は、事象情報入力部２０１と、形状ベクトル抽出部２０３と、デジタル地図データベース２０５と、特許請求の範囲の形状データ符号化装置に該当する形状データ符号化部２０７と、符号表記憶部２０９と、形状データ送信部２１１とを有している。また、デコーダ３００は、形状データ受信部３０１と、形状データ復号化部３０３と、符号表記憶部３０５と、デジタル地図データベース３０７と、マップマッチング部３０９と、表示部３１１とを有している。
【００３５】
以下、本実施形態のカーナビゲーションシステムを構成するエンコーダ２００およびデコーダ３００が有する各構成要素について説明する。まず、エンコーダ２００が有する事象情報入力部２０１は、事故や渋滞等の事象情報を入力するためのものである。また、形状ベクトル抽出部２０３は、事象情報入力部２０１に入力された事象情報に応じた形状ベクトルをデジタル地図データベース２０５から抽出するものである。
【００３６】
また、形状データ符号化部２０７は、上述したように、形状データに対する等間隔リサンプリングやテキスト形式への符号化等を行うものである。なお、符号表記憶部２０９には図４に示したような符号表が記憶されており、形状データ符号化部２０７によるテキスト形式への符号化は当該符号表に従って行われる。また、形状データ送信部２１１は、形状データ符号化部２０７でテキスト形式に符号化された形状データをデコーダ３００に送信するものである。
【００３７】
次に、デコーダ３００が有する形状データ受信部３０１は、エンコーダ２００から送信された形状データを受信するものである。また、形状データ復号化部３０３は、形状データ受信部３０１が受信した形状データを復号化して形状ベクトルを特定するものである。なお、デコーダ３００が有する符号表記憶部３０５にも図４に示したような符号表が記憶されており、形状データ復号化部３０３による形状データの復号は当該符号表に従って行われる。
【００３８】
また、マップマッチング部３０９は、形状データ復号化部３０３で特定された形状ベクトルとデジタル地図データベース３０７に記憶されている地図データとをマップマッチングするものである。また、表示部３１１は、マップマッチングされた形状ベクトルをデジタル地図データベース３０７の地図に重ねて表示するものである。
【００３９】
以上説明したように、本実施形態の形状データ符号化方法によって形状データを符号化する形状データ符号化装置を備えたカーナビゲーションシステムによれば、エンコーダ側で形状ベクトルのデータ（形状データ）をテキスト形式に符号化することができる。形状データがテキスト形式であると、エンコーダとデコーダ間のネットワークがインターネットの場合にバイナリ形式よりも安定して伝送できる。また、エンコーダやデコーダがパーソナルコンピュータ等であっても形状データの活用を柔軟に行うことができる。
【００４０】
なお、本実施形態では、各相対ノードの角度情報を予測値差分Δθとして説明しているが、図３（ｂ）に示す偏角θを角度情報としても良い。
【００４１】
【発明の効果】
以上説明したように、本発明に係る形状データ符号化装置および形状データ符号化方法によれば、マップマッチングで形状を特定するためのデジタル地図上の形状ベクトルを構成する各ノードの位置情報に算術加工を施して、前記位置情報を統計的に偏りを持つデータに変換し、前記統計的に偏りを持つデータの内、統計的に強い偏りを持つ値の少なくとも１つから構成されるデータ列が１つの文字コードに対応する符号表を用いて、前記データをテキスト形式に符号化するため、形状データをテキスト形式に符号化することができる。
【図面の簡単な説明】
【図１】形状ベクトルの一例を示す説明図
【図２】形状ベクトルのデータ列を示す説明図
【図３】区間長Ｌで等間隔でリサンプルした形状ベクトルの各相対ノードの角度情報を示す説明図
【図４】実施形態の予測差分値Δθに対して割り当てる符号表の例を示す説明図
【図５】一実施形態のカーナビゲーションシステムを示す構成図
【図６】予測値差分Δθに対して割り当てる符号表の例を示す説明図
【符号の説明】
２００  エンコーダ
３００  デコーダ
２０１  事象情報入力部
２０３  形状ベクトル抽出部
２０５，３０７  デジタル地図データベース
２０７  形状データ符号化部
２０９，３０５  符号表記憶部
２１１  形状データ送信部
３０１  形状データ受信部
３０３  形状データ復号化部
３０９  マップマッチング部
３１１  表示部
【図１】
2004252651.tif 000003
【図２】
2004252651.tif 000004
【図３】
2004252651.tif 000005
【図４】
2004252651.tif 000006
【図５】
2004252651.tif 000007
【図６】
2004252651.tif 000008