圧縮装置、ルート検索装置、ナビゲーションシステム、圧縮装置の動作方法、ルート検索装置の動作方法、およびナビゲーション装置の動作方法
【課題】従来の圧縮技術には、例えばノードを偏角で表す際の変換処理の負荷が高いために、装置側に高い演算処理能力が要求されるなどの課題がある。また差分を利用したデータ圧縮には、例えば、上記例のように数値データ同士の値が近似していれば圧縮効率を高く維持できるが、値が大きく異なるデータ同士の場合、逆にデータ量が多くなってしまう可能性があるなどの課題がある。また、それを回避するためにデータ量を削減できるか否かの判断処理を行うと、結局処理時間がかかってしまうことになる。
【解決手段】上の課題を解決するために、本発明は、主に隣接点で構成されることが多く上位桁の数字が近似している地図上の座標組を受付け、その座標組に関して差分を演算しデータ量を圧縮する機能を備える座標圧縮装置を提供する。
【解決手段】上の課題を解決するために、本発明は、主に隣接点で構成されることが多く上位桁の数字が近似している地図上の座標組を受付け、その座標組に関して差分を演算しデータ量を圧縮する機能を備える座標圧縮装置を提供する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、緯度経度などの地図上の座標情報のデータ量を圧縮する技術に関する。
【背景技術】
【０００２】
現在、ユーザ端末にて閲覧可能な地図データが、インターネットを介したＡＳＰの利用やスタンドアロンのユーザ端末へのインストールなど様々な形態で提供されている。このような地図データでは、緯度経度情報などによって地図上の座標点を特定し、ランドマークの位置やルートなどを表示することができる。
【０００３】
ところで、この座標を示すデータは、例えば緯度経度情報であれば「３５．６５８６２５、１３９．７４５４１５」という具合に、位置解像度合いに応じて差はあるものの、所定水準以上のサービス提供のためには桁数の大きな数値データ列で表す必要がある。そのためインターネットを介したルート検索サービスの場合、この座標を示すデータをそのままユーザ端末に送信すると、通信に時間がかかってしまい地図情報の表示が遅い、などの問題が生じる。そこで、緯度経度情報などの座標を示すデータ量を削減するための圧縮方法が様々提供されている。
【０００４】
例えば、特許文献１には地図上の所定のノードの位置情報を直前のノードからの偏角で表すことで数値的に偏りのあるデータに変換し（数値範囲が−１８０から１８０の間に収まり、また、直線であれば偏角は０度に偏るため）、可変長符号化によってデータ量を削減する技術が開示されている。
【０００５】
また、一般的に、数値データ群のデータサイズを圧縮する方法として、その差分を利用する方式も利用されている。この方式では、データ群について１つ前の数値との差分値を算出し、その差分値でデータ群を表現することで、例えば「１００００、１００１０、１００２０」というデータ群を、「１００００、＋１０、＋１０」といった具合に少ない情報量（ビット数）とすることができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００３−２３３５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、上記従来の圧縮技術には以下のような課題がある。すなわち、特許文献１の技術においては、ノードを偏角で表す際の変換処理の負荷が高いために、装置側に高い演算処理能力が要求される、あるいは処理に時間がかかりユーザを待たせてしまう、などの課題がある。
【０００８】
また、上記差分を利用したデータ圧縮には、例えば、上記例のように数値データ同士の値が近似していれば圧縮効率を高く維持できるが、値が大きく異なるデータ同士の場合、例えば「３００００、１０」のデータ群であれば、差分が「３００００、−２９９９０」となってしまうなど、逆にデータ量が多くなってしまう可能性があるなどの課題がある。また、それを回避するためにデータ量を削減できるか否かの判断処理を行うと、結局処理時間がかかってしまうことになる。
【課題を解決するための手段】
【０００９】
以上の課題を解決するために、本発明は、主に隣接点で構成されることが多く上位桁の数字が近似している地図上の座標組を受付け、その座標組に関して差分を演算しデータ量を圧縮する機能を備える座標圧縮装置を提供する。
【００１０】
具体的には、地図上の位置を表す複数の座標を一組として座標組を受付ける座標組受付部と、取得した座標組に含まれる複数の座標の中から基準座標を選択する基準座標選択部と、座標組に含まれる基準座標と他の座標との差分演算を行い、当該他の座標を差分座標として取得する差分座標取得部と、差分座標として表されない基準座標と差分座標とを一組として、この座標組を受付けた座標組に対応する圧縮座標組として出力する圧縮座標組出力部と、を有する座標圧縮装置である。
【００１１】
また、上記の構成を基本として、基準座標選択部が、基準座標として差分座標として表されるべき座標をも選択する相対選択手段を有する座標圧縮装置も提供する。
【００１２】
また、例えばルート検索で検索されたルートは、値が極めて近く、かつ連続的に変化する緯度経度などで示される座標組によって構成されるので、より圧縮効率を高めることができる。そこで、上記の構成のいずれかを基本として、座標組受付部が、地図上のルートを、複数の座標を隣同士連続させた線として表現するために、当該複数の座標をルート組として受付けるルート組受付手段を有し、基準座標選択部が、ルート組に含まれる複数の座標の中から常に差分座標取得部での演算対象となる座標に隣接する座標を基準座標として選択する隣接座標選択手段を有する座標圧縮装置も提供する。
【００１３】
また、上記構成の座標圧縮装置を含むルート検索装置や、そのルート検索装置と、端末装置と、からなるナビゲーションシステムも提供する。また、これら座標圧縮装置やルート検索装置、ナビゲーションシステムの動作方法も提供する。
【発明の効果】
【００１４】
以上のような構成をとる本発明によって、処理負荷をかけることなく効率的に座標組のデータ量を圧縮することができる。また、それによって、例えば携帯電話網など比較的低速のネットワークを介した通信型のナビゲーションシステムなどにおいても、ストレスを感じないスピードで座標組をクライアント端末に送信することができる。
【図面の簡単な説明】
【００１５】
【図１】実施例１の座標圧縮装置における座標組の圧縮処理の一例を説明するための概念図
【図２】実施例１の座標圧縮装置における機能ブロックの一例を表す図
【図３】実施例１の座標圧縮装置の差分座標取得部での差分座標取得の一例を表す概念図
【図４】実施例１の座標圧縮装置の圧縮座標組出力部にて実行されるデータ圧縮処理の一例を表す概念図
【図５】実施例１の座標圧縮装置におけるハードウェア構成の一例を表す図
【図６】実施例１の座標圧縮装置における処理の流れの一例を表すフローチャート
【図７】実施例２の座標圧縮装置において取得される座標組の特徴を説明するための概念図
【図８】実施例２の座標圧縮装置における機能ブロックの一例を表す図
【図９】実施例２の座標圧縮装置における処理の流れの一例を表すフローチャート
【図１０】実施例３のルート検索装置における機能ブロックの一例を表す図
【図１１】実施例３のルート検索装置における処理の流れの一例を表すフローチャート
【図１２】実施例４のナビゲーションシステムの一例を表す概念図
【図１３】実施例４のナビゲーションシステムを構成する各装置の機能ブロックの一例を表す図
【図１４】実施例４のナビゲーションシステムにおける処理の流れの一例を表すフローチャート
【発明を実施するための形態】
【００１６】
以下に、図を用いて本発明の実施の形態を説明する。なお、本発明はこれら実施の形態に何ら限定されるものではなく、その要旨を逸脱しない範囲において、種々なる態様で実施しうる。
【００１７】
なお、実施例１は、主に請求項１、２、６、７について説明する。また、実施例２は、主に請求項３、８について説明する。また、実施例３は、主に請求項４、９について説明する。また、実施例４は、主に請求項５、１０について説明する。
【００１８】
≪実施例１≫
＜概要＞
図１は、本実施例の座標圧縮装置における座標組の圧縮処理の一例を説明するための概念図である。例えばユーザαがお気に入りのレストランを友人βに紹介するため、図１（ａ）にあるように地図データ上のレストランＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆを特定する。そしてユーザαは、本実施例の座標圧縮装置を利用して、図１（ｂ）に示すように上記レストランＡからＦの位置を示す緯度経度の値について差分を取り、６４進数値への変換などの処理を行うことで、送信するデータのサイズを例えば２０パーセントほどのサイズに圧縮して、その圧縮データをユーザβの端末に送信した。
【００１９】
このようにして、ユーザαは、通常よりも軽いデータサイズで友人βにお勧めのレストランの位置を教えることができる。
【００２０】
＜機能的構成＞
図２は、本実施例の座標圧縮装置における機能ブロックの一例を表す図である。なお、以下に記載する本座標圧縮装置の機能ブロックは、ハードウェア、ソフトウェア、又はハードウェア及びソフトウェアの両方として実現され得る。具体的には、コンピュータを利用するものであれば、ＣＰＵや主メモリ、バス、あるいは二次記憶装置（ハードディスクや不揮発性メモリ、ＣＤやＤＶＤなどの記憶メディアとそれらメディアの読取ドライブなど）、情報入力に利用される入力デバイス、印刷機器や表示装置、その他の外部周辺装置などのハードウェア構成部、またその外部周辺装置用のインターフェース、通信用インターフェース、それらハードウェアを制御するためのドライバプログラムやその他アプリケーションプログラム、ユーザインターフェース用アプリケーションなどが挙げられる。
【００２１】
そして主メモリ上に展開したプログラムに従ったＣＰＵの演算処理によって、入力デバイスやその他インターフェースなどから入力され、メモリやハードディスク上に保持されているデータなどが加工、蓄積されたり、上記各ハードウェアやソフトウェアを制御するための命令が生成されたりする。また、この発明は座標圧縮装置として実現できるのみでなく、方法としても実現可能である。また、このような発明の一部をソフトウェアとして構成することができる。さらに、そのようなソフトウェアをコンピュータに実行させるために用いるソフトウェア製品、及び同製品を記録媒体に固定した記録媒体も、当然にこの発明の技術的な範囲に含まれる（本明細書の全体を通じて同様である）。
【００２２】
そして、この図２にあるように、本実施例の「座標圧縮装置」（０２００）は、「座標組受付部」（０２０１）と、「基準座標選択部」（０２０２）と、「差分座標取得部」（０２０３）と、「圧縮座標組出力部」（０２０４）と、を有する。
【００２３】
「座標組受付部」（０２０１）は、地図上の位置を表す複数の座標を一組として座標組を受付ける機能を有し、例えばＣＰＵ（中央演算装置）や主メモリ、Ｉ／Ｏ（インプット／アウトプット）、座標組受付プログラムなどで実現することができる。また、「座標」とは位置を示すための数値情報をいい、例えば緯度経度情報のほか、本発明などにあわせ特別に設定された位置特定のための数値情報なども挙げられる。また、「複数の座標を一組」とは、緯度経度情報などの位置情報で示される座標点を複数まとめて一組とする、という意味である。
【００２４】
そして「座標組受付部」は、具体的に、例えば上記概要のようにユーザ端末に対して地図を提示し、ユーザによる地図上の任意の複数地点を指定する操作入力に応じて、当該複数地点の緯度経度情報を座標組として受付ける、などの構成が挙げられる。あるいは、ランドマーク名とそのランドマークのある位置の緯度経度情報を関連付けたテーブルデータを参照し、ユーザによって入力された複数のランドマーク名の緯度経度情報を座標組として受付ける構成も挙げられる。また、ＧＰＳ（全地球測位システム）を利用した位置測定情報や、その他の位置測定方法（例えば無線ＬＡＮスポットや携帯電話基地局の固有位置情報などを利用した位置測定方法）による位置測定情報に基づいて、複数の緯度経度情報などの座標の組を取得する構成も挙げられる。
【００２５】
また、実施例３などで後述するように、ルート検索の結果求められたルートを表す複数の緯度経度情報を座標組として受付けても良い。もちろん上記以外のその他の構成によって複数の座標の組を受付けても良い。
【００２６】
このように、本実施例の座標圧縮装置では複数の座標を示す数値情報を取得する。そして、当該座標情報は、主に所定範囲の地図上に含まれる複数点を示すものであるため隣接点の座標情報の組で構成されることが多い。したがって、上位桁の数字が近似しており、高いデータ量圧縮を行うことができる点を特徴とする。
【００２７】
「基準座標選択部」（０２０２）は、取得した座標組に含まれる複数の座標の中から基準座標を選択する機能を有し、例えば、ＣＰＵや主メモリ、基準座標選択プログラムなどによって実現することができる。この基準座標の選択方法としては、具体的には、例えば座標組の中で１番最初／最後に受付けた座標点を基準座標として選択する方法などが挙げられる。この場合、例えば「３５．６７５２８７、３５．６７５４４０、３５．６７５７４１」という座標（緯度）組に関して、最初の「３５．６７５２８７」を基準座標として選択する、という具合である。
【００２８】
また、１の座標を固定的に基準座標とする選択方法のほか、階差的（相対的）に前項の座標を基準座標として選択する方法も挙げられる。その場合には、基準座標選択部が、図示しない「相対選択手段」を有すると良い。「相対選択手段」とは、基準座標として、差分座標として表されるべき座標をも選択する機能を有する。具体的には、例えば前掲の「３５．６７５２８７、３５．６７５４４０、３５．６７５７４１」という座標（緯度）組に関して、２番目の「３５．６７５４４０」に対してはその前の「３５．６７５２８７」を基準座標として選択する。また、３番目の「３５．６７５７４１」に対してはその前の「３５．６７５４４０」を基準座標として選択する、という具合である。
【００２９】
上記のようにこの基準座標選択部にて基準座標を固定的／相対的に選択することで、次の差分座標取得部にて座標組に含まれる複数の各座標を基準座標からの差分値として表すことができる。
【００３０】
「差分座標取得部」（０２０３）は、座標組に含まれる基準座標と他の座標との差分演算を行い、当該他の座標を差分座標として取得する機能を有し、例えばＣＰＵや主メモリ、差分座標取得プログラムなどによって実現することができる。具体的には、図３（ａ）にあるように、例えば「３５．６７５２８７、３５．６７５４４０、３５．６７５７４１、３５．６７６０９１、・・・」という座標（緯度）組が取得され、その中で最初の「３５．６７５２８７」が基準座標として選択された。するとこの差分座標取得部では、その他の座標と基準座標との差分値「３５６７５２８７、＋１５３、＋４５４、＋８０４、・・・」を演算し、それを差分座標として取得する、という具合である。
【００３１】
また、図３（ｂ）にあるように、例えば基準座標として階差的に前項の座標を選択する場合、この差分座標取得部では、差分値として「３５６７５２８７、＋１５３、＋３０１、＋３５０、・・・」を演算し、それを差分座標として取得する。
【００３２】
このように、座標組を基準座標との差分で表すことで、そのデータビット量を低減することができる。さらに本実施例では、主に所定範囲の地図上に含まれる複数点を示す座標の組であるため、緯度経度などの上位桁の数字が近似しており、高いデータ圧縮となる点を特徴とする。
【００３３】
なお、上記例では１番最初の座標については差分ではなくそのままの８桁の緯度経度値として表されているが、以下のような構成によってその桁数を減じ、データ量を削減するようしても良い。すなわち、基準座標選択部において、例えば日本であれば東京都港区麻布台にある緯度経度原点（３５．３９２９１５７、１３９．４４２８８７５）など所定の座標を絶対的な基準座標として選択する。そして、前述の例では、固定的／相対的いずれの場合でもそのまま８桁の緯度経度値で表されていた１番最初の座標を、その絶対的な基準座標との差分値として表すとともに、日本の絶対的な基準座標を識別するための符号「０１」などを付加する。このようにして、伸張する装置側で識別符号と絶対的な基準座標との関係を示すテーブルデータを保持しておく必要があるものの、１番最初の座標の桁数も減じることができるので、さらにデータ圧縮率を高めることができる。
【００３４】
また、東京都の絶対的な基準座標、神奈川県の絶対的な基準座標といった具合に、地域をさらに細かい単位で分割して絶対的な基準座標を設けるよう構成しても良い。その場合には、ＧＰＳ測位情報やユーザ入力情報などに応じて、複数の絶対的な基準座標から好適な座標が選択されるよう構成すると良い。
【００３５】
「圧縮座標組出力部」（０２０４）は、差分座標として表されない基準座標と差分座標とを一組として、この座標組を受付けた座標組に対応する圧縮座標組として出力する機能を有し、例えばＣＰＵや主メモリ、圧縮座標組出力プログラムなどによって実現することができる。
【００３６】
また、上記のように座標組に含まれる複数の座標を基準座標との差分値にて表すことで所定のビットデータ量圧縮を実現することができるが、この圧縮座標組出力部にてその差分値で表された座標組に対する別のデータ圧縮処理をさらに実行するよう構成しても良い。具体的には、例えば図４に示すように、まずプラスまたはマイナスの符号が付された上記差分値を絶対値化し、さらに２進数変換処理を行う。そして変換後の２進数値に対して、上記絶対値化処理以前の当該数値のプラス又はマイナスの符号を示す符号ビットを、例えばプラスならば「１」、マイナスならば「０」として２進数値の最後尾に付加する。
【００３７】
つづいて、その数値列を５ビット単位で分割し、次の５ビット単位と組み合わせて一の座標情報を形成する単位には「０」を付加し、一の座標情報の終端となる５ビット単位には「１」を付加する（一の座標情報が緯度と経度で表される場合は、緯度と経度それぞれの終端に「１」を付加すると良い）。そして、このようにして６ビット単位とした２進数値を、６ビットデータを１文字で表せる６４（＝２６）進数値に変換する。
【００３８】
以上の処理によって、６個の地点を示す緯度経度情報を、例えば「４８２ｓｉｔｇｋＣ２ＭＶｉＢｃ５ＡＲｍＺＧＶｑｐｇｌＥＤｍｔＵｂ」といった３２個の文字列で表すことができる。したがって、この場合２０パーセントほどのデータサイズに圧縮することができる。
【００３９】
またもちろん、本実施例の座標圧縮装置の処理によって圧縮され出力された圧縮座標組は、上記の圧縮処理とは逆の伸張処理を行うことで簡単に復元することができる。
【００４０】
＜ハードウェア構成＞
図５は、上記機能的な各構成要件をハードウェアとして実現した際の、座標圧縮装置における構成の一例を表す概略図である。この図を利用して座標組のデータ量圧縮処理におけるそれぞれのハードウェア構成部の働きについて説明する。
【００４１】
この図にあるように、座標圧縮装置は、基準座標選択部、差分座標取得部、および圧縮座標組出力部であり、またその他の各種演算処理を実行する「ＣＰＵ」（０５０１）と、「主メモリ」（０５０２）と、を備えている。また各種データやプログラムなどを蓄積保持する「フラッシュメモリ」（０５０３）や、座標組受付部である「Ｉ／Ｏ」（０５０４）も備えている。そしてそれらが「システムバス」などのデータ通信経路によって相互に接続され、情報の送受信や処理を行う。
【００４２】
また、「主メモリ」にはプログラムが読み出され、「ＣＰＵ」は読み出された当該プログラムを参照し、プログラムで示される手順に従い各種演算処理を実行する。また、この「主メモリ」や「フラッシュメモリ」にはそれぞれ複数のアドレスが割り当てられており、「ＣＰＵ」の演算処理においては、そのアドレスを特定し格納されているデータにアクセスすることで、データを用いた演算処理を行うことが可能になっている。
【００４３】
ここでユーザ入力結果やルート検索結果などに応じて特定される複数の座標（緯度経度情報など）の組を、「Ｉ／Ｏ」を介して取得すると、「ＣＰＵ」は座標組受付プログラムにしたがってそれら座標を「主メモリ」のアドレス１などに格納する。つづいて「ＣＰＵ」は、基準座標選択プログラムを解釈し、その解釈結果にしたがって、例えば「主メモリ」に格納された座標組の中で、１番最初に取得された座標を基準座標として選択し、「主メモリ」のアドレス２に格納する。なお、この選択処理は、前述のように一の座標を固定的に基準座標として選択しても良いし、座標の差分を階差的にとるために前項の座標を相対的に基準座標として順次選択する処理としても良い。また座標が緯度経度で示されていれば、緯度と経度それぞれについて基準座標を選択する。そして「ＣＰＵ」は、差分座標取得プログラムを解釈し、その解釈結果にしたがって、固定的／相対的に選択された基準座標と次の座標との差分値を、緯度と経度のそれぞれについて四則演算処理によって算出し、「主メモリ」のアドレス３などに格納する。
【００４４】
その後、「ＣＰＵ」は圧縮座標組出力プログラムを解釈し、その解釈結果に従って、例えば「主メモリ」に格納された最初の基準座標値や差分座標値を絶対値化した後、２進数値に変換する。つづいて変換した２進数値に絶対値化前のプラス又はマイナスの符号を示す符号ビットを付加し、その数字列を５ビット単位に分割する。そして、次の５ビット単位と組み合わせて一の座標情報を形成する単位には「０」を付加し、一の座標情報の終端となる５ビット単位には「１」を付加する。そして、このようにして６ビット単位とした２進数値を例えば「４８２ｓｉｔ・・・」といった具合に６４進数値に変換し、「主メモリ」のアドレス４に格納する。
【００４５】
そして、このようにしてデータ量が大幅に削減された圧縮座標組のデータは、時間をかけずに他の端末装置などに送信することができる。
【００４６】
＜処理の流れ＞
図６は、本実施例の座標圧縮装置における処理の流れの一例を表すフローチャートである。なお、以下に示すステップは、上記のような計算機の各ハードウェア構成によって実行されるステップであっても良いし、媒体に記録され、計算機を制御するためのプログラムを構成する処理ステップであっても構わない。
【００４７】
この図にあるように、まず、例えばユーザ入力やルート検索処理などで特定されるなどした地図上の位置を表す複数の座標を一組として、Ｉ／Ｏなどを介してその座標組を受付ける（ステップＳ０６０１）。つづいて、取得した座標組に含まれる複数の座標の中から、例えば最初に取得された座標などを基準座標として選択し（ステップＳ０６０２）、座標組に含まれる他の座標の基準座標との差分値を演算して、当該他の座標を表す差分座標として取得する（ステップＳ０６０３）。なお、前述のように基準座標はステップＳ０６０２で選択した一の座標を固定的に利用しても良いし、この図に示すようにステップＳ０６０３にて一の座標について差分座標を取得するたびに、階差をとるため前項の座標を基準座標として選択し直す構成としても良い。
【００４８】
そして、差分座標として表されない基準座標と差分座標とを一組に対して、例えば前述の絶対値化処理や２進数変換処理、符号ビットの付加処理、５ビット単位への分割処理、６４進数変換処理などを行い、データ量の削減された圧縮座標組を出力する（ステップＳ０６０４）。
【００４９】
＜効果の簡単な説明＞
以上のように本実施例の座標圧縮装置によって、座標組を基準座標との差分で表すことで、そのデータビット量を低減することができる。さらに本実施例では、主に所定範囲の地図上に含まれる複数点を示す座標の組であるため、緯度経度などの上位桁の数字が近似しており、高いデータ圧縮となる点を特徴とする。
【００５０】
したがって、例えば携帯電話網など比較的低速のネットワークを介した通信型のナビゲーションシステムなどにおいても、ストレスを感じないスピードで座標組をクライアント端末に送信することができる。
【００５１】
≪実施例２≫
＜概要＞
本実施例は、上記実施例を基本として、座標組受付部にて受付ける座標組が、地図上のルートを示すための複数の座標点であることを特徴とする座標圧縮装置である。図７に示すように、ある地点Ａから別の地点Ｂを結ぶルートを示す複数の座標点ａ〜ｄは、それぞれが「近接」し、かつ「連続」したものとなる。したがって、階差をとるために前項の座標を基準座標として選択し相対的に差分をとると、その差分値は比較的小さな値をとることになり、高い圧縮効率を実現することができる、という具合である。
【００５２】
＜機能的構成＞
図８は、本実施例の座標圧縮装置における機能ブロックの一例を表す図である。この図にあるように、本実施例の「座標圧縮装置」（０８００）は、上記実施例を基本として、「座標組受付部」（０８０１）と、「基準座標選択部」（０８０２）と、「差分座標取得部」（０８０３）と、「圧縮座標組出力部」（０８０４）と、「相対選択手段」（０８０５）と、を有する。なお、これらの構成要件に関する詳細な説明は、上記実施例にて記載済みなので省略する。
【００５３】
そして、本実施例の座標圧縮装置の特徴点は、座標組受付部が「ルート組受付手段」（０８０６）をさらに有する点と、基準座標選択部が「隣接座標選択手段」（０８０７）をさらに有する点である。
【００５４】
「ルート組受付手段」（０８０６）は、地図上のルートを、複数の座標を隣同士連続させた線として表現するために、当該複数の座標をルート組として受付ける機能を有し、例えば、ＣＰＵや主メモリ、Ｉ／Ｏ、ルート組受付プログラムなどで実現することができる。また「ルート」とは、ある地点から別の地点を結ぶ道路などの移動経路を示す地図上の線をいう。そして前述のようにルートは線であるので、そのルートを表現する座標点の組は「近接」し、かつ「連続」したものとなることを特徴とする。
【００５５】
「隣接座標選択手段」（０８０７）は、ルート組に含まれる複数の座標の中から、常に差分座標取得部での演算対象となる座標に隣接する座標を基準座標として選択する機能を有し、例えばＣＰＵや主メモリ、隣接座標選択プログラムなどで実現できる。そして、前述のようにルートの座標組は「連続」したものであるため、基本的には隣接点との差分をとると、非隣接点同士の差分値と比較してその差分値は小さい値となる。
【００５６】
したがって、本実施例の座標圧縮装置ではさらに高い圧縮効率で、座標組を圧縮することができる。
【００５７】
＜処理の流れ＞
図９は、本実施例の座標圧縮装置における処理の流れの一例を表すフローチャートである。なお、以下に示すステップは、上記のような計算機の各ハードウェア構成によって実行されるステップであっても良いし、媒体に記録され、計算機を制御するためのプログラムを構成する処理ステップであっても構わない。
【００５８】
この図にあるように、まず、例えばユーザ入力やルート検索処理などで特定されるなどした地図上のルートを複数の座標を隣同士連続させた線として表現するために、当該複数の座標をルート組としてＩ／Ｏなどを介して受付ける（ステップＳ０９０１）。つづいて、取得したルート組に含まれる複数の座標の中から、例えば最初に取得された座標などを基準座標として選択し（ステップＳ０９０２）、基準座標に隣接する２番目の座標と基準座標との差分値を演算して、当該２番目の座標を表す差分座標を取得する（ステップＳ０９０３）。
【００５９】
つづいて、今度は２番目の座標を基準座標として、その２番目の座標点に隣接する３番目の座標の差分値の演算を行い、当該３番目の座標を表す差分座標を取得する。そして、この処理を全てのルート組に含まれる座標に対して実行する（ステップＳ０９０４）まで繰返す。
【００６０】
そして、差分座標として表されない基準座標と差分座標とを一組に対して、例えば前述の絶対値化処理や２進数変換処理、符号ビットの付加処理、５ビット単位への分割処理、６４進数変換処理など行い、データ量の削減された圧縮座標組を出力する（ステップＳ０９０５）。
【００６１】
＜効果の簡単な説明＞
以上のように本実施例の座標圧縮装置によって、ルートを示す「連続」した座標組に対して隣接点との差分をとることができる。したがって、本実施例の座標圧縮装置ではさらに高い圧縮効率で、座標組を圧縮することができる。
【００６２】
≪実施例３≫
＜概要＞
本実施例は、上記実施例の座標圧縮装置をハードウェア、又は／及びソフトウェア的に組み込んだことを特徴とするルート検索装置である。
【００６３】
＜機能的構成＞
図１０は、本実施例のルート検索装置における機能ブロックの一例を表す図である。この図にあるように、本実施例の「ルート検索装置」（１０００）には、上記実施例２の座標圧縮装置が含まれ、したがって「座標組受付部」（１００１）と、「基準座標選択部」（１００２）と、「差分座標取得部」（１００３）と、「圧縮座標組出力部」（１００４）と、「相対選択手段」（１００５）と、「ルート組受付手段」（１００６）と、「隣接座標選択手段」（１００７）と、を有する。なお、これらの構成要件に関する詳細な説明は、上記実施例にて記載済みなので省略する。
【００６４】
そして、本実施例のルート検索装置は、さらに「地点情報取得部」（１００８）と、「ルート検索部」（１００９）と、「ルート組出力部」（１０１０）と、を有する。
【００６５】
「地点情報取得部」（１００８）は、複数の地点を示す地点情報を取得する機能を有し、ＣＰＵや主メモリ、Ｉ／Ｏ、地点情報取得プログラムなどによって実現できる。「地点情報」とは、地点を示す情報をいい、例えば緯度経度情報やその他の地図上の位置を示す座標情報、あるいはそれら地点情報と関連付けられたランドマーク名や住所名などが挙げられる。そしてこの地点情報取得部は、具体的には、通常のルート検索装置と同様に、例えばＧＰＳによる測位情報や、ユーザによる地図上の点やランドマーク名の指定入力などの情報に応じて複数の地点を示す地点情報を取得する、という具合である。
【００６６】
「ルート検索部」（１００９）は、取得した地点情報に基づき前記複数の地点を結ぶルートを検索する機能を有し、例えばＣＰＵや主メモリ、ルート検索プログラムなどによって実現することができる。具体的には、通常のルート検索装置と同様に、例えばダイクストラ法やその他のルート検索アルゴリズムを利用して、複数の地点を結ぶルートを検索する、という具合である。
【００６７】
「ルート組出力部」（１０１０）は、検索されたルートを示す複数の座標をルート組受付手段に対して出力する機能を有し、例えばＣＰＵや主メモリ、Ｉ／Ｏ、ルート組出力プログラムなどによって実現することができる。このようにして、本実施例のルート検索装置では、例えばユーザが指定入力などした複数の地点を結ぶルートを検索し、その検索結果を示す連続した複数の座標からなるルート組のデータ量を、高い圧縮率で圧縮することができる。
【００６８】
＜処理の流れ＞
図１１は、本実施例のルート検索装置における処理の流れの一例を表すフローチャートである。なお、以下に示すステップは、上記のような計算機の各ハードウェア構成によって実行されるステップであっても良いし、媒体に記録され、計算機を制御するためのプログラムを構成する処理ステップであっても構わない。
【００６９】
この図にあるように、まず、例えばＧＵＩを介したユーザからの指定入力などに応じて、複数の地点情報を取得する（ステップＳ１１０１）と、例えばダイクストラ法に基づくアルゴリズムなどにしたがって、取得した複数の地点を結ぶ、複数の座標を隣同士連続させた線として表現したルートを検索する（ステップＳ１１０２）。そして、そのルート検索によって特定されたルートを示す複数の座標をルート組として出力する（ステップＳ１１０３）。そして出力されたルート組を取得し（ステップＳ１１０４）、その中から、例えば最初に取得された座標などを基準座標として選択し（ステップＳ１１０５）、基準座標に隣接する２番目の座標と基準座標との差分値を演算して、当該２番目の座標を表す差分座標を取得する（ステップＳ１１０６）。
【００７０】
つづいて、今度は２番目の座標を基準座標として、その２番目の座標点に隣接する３番目の座標の差分値の演算を行い、当該３番目の座標を表す差分座標を取得する。そして、この処理を全てのルート組に含まれる座標に対して実行する（ステップＳ１１０７）まで繰返す。
【００７１】
そして、差分座標として表されない基準座標と差分座標とを一組に対して、例えば前述の絶対値化処理や２進数変換処理、符号ビットの付加処理、５ビット単位への分割処理、６４進数変換処理など行い、データ量の削減された圧縮座標組を出力する（ステップＳ１１０８）。
【００７２】
＜効果の簡単な説明＞
以上のように、本実施例のルート検索装置によって、例えばユーザが指定入力などした複数の地点を結ぶルートを検索し、その検索結果を示す連続した複数の座標からなるルート組のデータ量を、高い圧縮率で圧縮することができる。
【００７３】
≪実施例４≫
＜概要＞
本実施例は、図１２にあるように、上記実施例にて説明したルート検索装置と、そのルート検索装置に対してルート検索をリクエストし、またそのレスポンス（検索結果）を示す圧縮座標組を受信する（複数の）端末装置と、からなることを特徴とするナビゲーションシステムである。
【００７４】
＜機能的構成＞
図１３は、本実施例のナビゲーションシステムを構成する各装置の機能ブロックの一例を表す図である。この図にあるように、本実施例のナビゲーションシステムは、「ルート検索装置」（１３００）と、「端末装置」（１３１０）と、からなる。
【００７５】
そして、「ルート検索装置」は、上記実施例を基本として図示しない「座標組受付部」と、「基準座標選択部」と、「差分座標取得部」と、「圧縮座標組出力部」と、「相対選択手段」と、「ルート組受付手段」と、「隣接座標選択手段」と、「地点情報取得部」と、「ルート検索部」と、「ルート組出力部」と、を有する。なお、これらの構成要件に関する詳細な説明は、上記実施例にて記載済みなので省略する。
【００７６】
そして、さらにこのルート検索装置は、「地点情報受信部」（１３０１）と、「圧縮座標組返信部」（１３０２）と、を有する。
【００７７】
「地点情報受信部」（１３０１）は、端末装置から送信された前記地点情報を受信する機能を有し、ＣＰＵや主メモリ、Ｉ／Ｏ、地点情報受信プログラムなどで実現することができる。具体的には、例えばインターネットなどの通信回線網を介して、端末装置に対して地点情報入力用の地図などを含むＧＵＩ用データを送信する。そして、当該ＧＵＩを利用して入力され、ＨＴＴＰリクエストとして送信されてきた地点情報を受信する、という具合である。
【００７８】
「圧縮座標組返信部」（１３０２）は、前記受信した地点情報に基づく圧縮座標組を端末装置に返信する機能を有し、例えばＣＰＵや主メモリ、Ｉ／Ｏ、圧縮座標組返信プログラムなどで実現することができる。具体的には、上記実施例にて記載したような処理により受信した地点情報からルート検索を実行し、検索されたルートを示す座標の組に対して圧縮座標組を生成する処理を実行する。そして、例えば地点情報受信部で受信した地点情報を含むＨＴＴＰリクエストへのレスポンスとして、そのリクエストの送信元の端末装置に対して生成した圧縮座標組を返信する、という具合である。
【００７９】
また、圧縮座標組の返信先として、例えば前記地点情報入力のためのＧＵＩなどにて返信先の端末装置を指定する情報が予め入力されていれば、当該返信先指定情報にしたがった別の端末装置を返信先として処理を行っても良い。
【００８０】
以上が、本実施例のナビゲーションシステムを構成する「ルート検索装置」の構成要件の説明である。続いて、同じく本実施例のナビゲーションシステムを構成する「端末装置」について図１３を用いて説明する。なお、「端末装置」とは、エンドユーザの利用する装置（Ｐ２Ｐ型のシステムにおいては全ユーザの利用装置）をいい、例えばデスクトップＰＣ（パーソナルコンピュータ）やノートＰＣ、スマートフォン、携帯電話などが挙げられる。
【００８１】
そして、この図１３にあるように「端末装置」（１３１０）は、「地点情報入力受付部」（１３１１）と、「地点情報送信部」（１３１２）と、「圧縮座標組受信部」（１３１３）と、「伸張部」（１３１４）と、「復元部」（１３１５）と、を有する。
【００８２】
「地点情報入力受付部」（１３１１）は、地点情報の入力を受付ける機能を有し、例えばＣＰＵや主メモリ、入力デバイス、そしてＧＵＩを含む地点情報入力受付プログラムなどが挙げられる。なお、「地点情報」とは、地点を示す情報をいい、例えばルート検索の際の出発地、目的地及び経由地等の地点を示す情報が挙げられる。そしてこの地点情報入力受付部では、具体的に、例えば端末装置のディスプレイ上に地図画像を表示し、ユーザが入力デバイスで指定した地図上のカーソル位置を入力された地点情報として受付ける方法などが挙げられる。あるいは、「東京駅」などランドマーク名や住所名などを、プルダウンメニューなどを利用して選択入力したり、テキスト入力欄を利用してフリー入力したりする方法なども挙げられる。
【００８３】
「地点情報送信部」（１３１２）は、受付けた地点情報を前記ルート検索装置に送信する機能を有し、例えばＣＰＵや主メモリ、Ｉ／Ｏ、地点情報送信プログラムなどで実現することができる。
【００８４】
「圧縮座標組受信部」（１３１３）は、送信した地点情報に応じて返信される圧縮座標組を受信する機能を有し、例えばＣＰＵや主メモリ、Ｉ／Ｏ、圧縮座標組受信プログラムなどで実現することができる。
【００８５】
「伸張部」（１３１４）は、受信した圧縮座標組を元の基準座標と差分座標の組に伸張する機能を有し、例えばＣＰＵや主メモリ、伸張プログラムなどによって実現できる。具体的には、例えば上記実施例の圧縮座標組出力部にて説明した処理と逆の処理、すなわち６４進数値で表されている圧縮座標組であれば、（１）２進数値への変換処理、（２）６ビット単位で最後の符合を参照した終端判断処理、（３）プラスかマイナスかを示す符号ビットの削除処理、（４）１０進数値への変換処理、（５）削除した符合ビットに応じたプラス又はマイナスの符号付加処理などを行うと良い。そして、この伸張処理によって、例えば「４８２ｓｉｔｇｋＣ２ＭＶｉＢｃ５ＡＲｍＺＧＶｑｐｇｌＥＤｍｔＵｂ」という圧縮座標組が、「３５６７５２８７、＋１５３、＋３０１、＋３５０、・・・」といった（差分座標として表されない）基準座標と差分値のデータに変換される、という具合である。
【００８６】
「復元部」（１３１５）は、基準値と差分値の組から複数の座標の組を復元する機能を有し、例えばＣＰＵや主メモリ、復元プログラムなどによって実現できる。具体的には、「３５６７５２８７、＋１５３、＋３０１、＋３５０、・・・」という差分値を含み表された座標の組を、「３５．６７５２８７、３５．６７５４４０、３５．６７５７４１、３５．６７６０９１、・・・」という全ての点が緯度経度で表される座標の組に復元する、という具合である。
【００８７】
このようにして、本実施例のナビゲーションシステムでは、端末装置からの入力受付に応じて行ったルート検索結果を示す複数の座標を、データ量を削減した圧縮座標組としてインターネット網などを介して簡単に送受信することができる。
【００８８】
なお、例えばユーザＡがユーザＢにルートを教える場合など、地点情報を送信する端末装置と、それに基づいて返信された圧縮座標組を伸張、復元し地図上などに表示する端末装置とは別体の装置であっても良い。すなわち本実施例のナビゲーションシステムは、ユーザＡの端末装置がルート検索装置に地点情報を送信し、その結果返信された圧縮座標組をユーザＢの端末装置に転送して、そこで伸張部および復元部の処理が実行される、という構成であっても良い。
【００８９】
＜処理の流れ＞
図１４は、本実施例のナビゲーションシステムにおける処理の流れの一例を表すフローチャートである。なお、以下に示すステップは、上記のような計算機の各ハードウェア構成によって実行されるステップであっても良いし、媒体に記録され、計算機を制御するためのプログラムを構成する処理ステップであっても構わない。
【００９０】
この図にあるように、まず、端末装置にてＧＵＩなどを介して複数の地点情報の入力を受付ける（ステップＳ１４１１）と、端末装置はルート検索装置に対して受付けた複数の地点情報を送信する（ステップＳ１４１２）。
【００９１】
ルート検索装置では、端末装置から送信された複数の地点情報を受信し、取得する（ステップＳ１４０１）と、例えばダイクストラ法に基づくアルゴリズムなどにしたがって、取得した複数の地点を結ぶ、複数の座標を隣同士連続させた線として表現したルートを検索する（ステップＳ１４０２）。そして、そのルート検索によって特定されたルートを示す当該複数の座標を出力し（ステップＳ１４０３）、取得する（ステップＳ１４０４）。そしてその中から、例えば最初に取得された座標などを基準座標として選択し（ステップＳ１４０５）、基準座標に隣接する２番目の座標と基準座標との差分値を演算して、当該２番目の座標を表す差分座標を取得する（ステップＳ１４０６）。
【００９２】
つづいて、今度は２番目の座標を基準座標として、その２番目の座標点に隣接する３番目の座標の差分値の演算を行い、当該３番目の座標を表す差分座標を取得する。そして、この処理を全てのルート組に含まれる座標に対して実行する（ステップＳ１４０７）まで繰返す。そして、差分座標として表されない基準座標と差分座標とを一組に対して、例えば前述の絶対値化処理や２進数変換処理、符号ビットの付加処理、５ビット単位への分割処理、６４進数変換処理など行い、データ量の削減された圧縮座標組を出力し（ステップＳ１４０８）、端末装置に対して返信する（ステップＳ１４０９）。
【００９３】
端末装置では、返信された圧縮座標組を受信する（ステップＳ１４１３）。そして、受信した圧縮座標組に対して伸張処理、例えば６４進数値から２進数値への変換処理や終端判断処理、符号ビットの削除処理、１０進数値への変換処理、プラス又はマイナスの符号付加処理などを実行し、基準座標と差分とで表される座標組を取得する（ステップＳ１４１４）。そして、取得した基準座標と差分とから、地図上の位置を表す複数の座標組を復元する（ステップＳ１４１５）。
【００９４】
＜効果の簡単な説明＞
以上のように、本実施例のナビゲーションシステムによって、端末装置からの入力受付に応じて行ったルート検索結果を示す複数の座標を、データ量を削減した圧縮座標組としてインターネット網などを介して簡単に送受信することができる。
【符号の説明】
【００９５】
０２００ 座標圧縮装置
０２０１ 座標組受付部
０２０２ 基準座標選択部
０２０３ 差分座標取得部
０２０４ 圧縮座標組出力部
【技術分野】
【０００１】
本発明は、緯度経度などの地図上の座標情報のデータ量を圧縮する技術に関する。
【背景技術】
【０００２】
現在、ユーザ端末にて閲覧可能な地図データが、インターネットを介したＡＳＰの利用やスタンドアロンのユーザ端末へのインストールなど様々な形態で提供されている。このような地図データでは、緯度経度情報などによって地図上の座標点を特定し、ランドマークの位置やルートなどを表示することができる。
【０００３】
ところで、この座標を示すデータは、例えば緯度経度情報であれば「３５．６５８６２５、１３９．７４５４１５」という具合に、位置解像度合いに応じて差はあるものの、所定水準以上のサービス提供のためには桁数の大きな数値データ列で表す必要がある。そのためインターネットを介したルート検索サービスの場合、この座標を示すデータをそのままユーザ端末に送信すると、通信に時間がかかってしまい地図情報の表示が遅い、などの問題が生じる。そこで、緯度経度情報などの座標を示すデータ量を削減するための圧縮方法が様々提供されている。
【０００４】
例えば、特許文献１には地図上の所定のノードの位置情報を直前のノードからの偏角で表すことで数値的に偏りのあるデータに変換し（数値範囲が−１８０から１８０の間に収まり、また、直線であれば偏角は０度に偏るため）、可変長符号化によってデータ量を削減する技術が開示されている。
【０００５】
また、一般的に、数値データ群のデータサイズを圧縮する方法として、その差分を利用する方式も利用されている。この方式では、データ群について１つ前の数値との差分値を算出し、その差分値でデータ群を表現することで、例えば「１００００、１００１０、１００２０」というデータ群を、「１００００、＋１０、＋１０」といった具合に少ない情報量（ビット数）とすることができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００３−２３３５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、上記従来の圧縮技術には以下のような課題がある。すなわち、特許文献１の技術においては、ノードを偏角で表す際の変換処理の負荷が高いために、装置側に高い演算処理能力が要求される、あるいは処理に時間がかかりユーザを待たせてしまう、などの課題がある。
【０００８】
また、上記差分を利用したデータ圧縮には、例えば、上記例のように数値データ同士の値が近似していれば圧縮効率を高く維持できるが、値が大きく異なるデータ同士の場合、例えば「３００００、１０」のデータ群であれば、差分が「３００００、−２９９９０」となってしまうなど、逆にデータ量が多くなってしまう可能性があるなどの課題がある。また、それを回避するためにデータ量を削減できるか否かの判断処理を行うと、結局処理時間がかかってしまうことになる。
【課題を解決するための手段】
【０００９】
以上の課題を解決するために、本発明は、主に隣接点で構成されることが多く上位桁の数字が近似している地図上の座標組を受付け、その座標組に関して差分を演算しデータ量を圧縮する機能を備える座標圧縮装置を提供する。
【００１０】
具体的には、地図上の位置を表す複数の座標を一組として座標組を受付ける座標組受付部と、取得した座標組に含まれる複数の座標の中から基準座標を選択する基準座標選択部と、座標組に含まれる基準座標と他の座標との差分演算を行い、当該他の座標を差分座標として取得する差分座標取得部と、差分座標として表されない基準座標と差分座標とを一組として、この座標組を受付けた座標組に対応する圧縮座標組として出力する圧縮座標組出力部と、を有する座標圧縮装置である。
【００１１】
また、上記の構成を基本として、基準座標選択部が、基準座標として差分座標として表されるべき座標をも選択する相対選択手段を有する座標圧縮装置も提供する。
【００１２】
また、例えばルート検索で検索されたルートは、値が極めて近く、かつ連続的に変化する緯度経度などで示される座標組によって構成されるので、より圧縮効率を高めることができる。そこで、上記の構成のいずれかを基本として、座標組受付部が、地図上のルートを、複数の座標を隣同士連続させた線として表現するために、当該複数の座標をルート組として受付けるルート組受付手段を有し、基準座標選択部が、ルート組に含まれる複数の座標の中から常に差分座標取得部での演算対象となる座標に隣接する座標を基準座標として選択する隣接座標選択手段を有する座標圧縮装置も提供する。
【００１３】
また、上記構成の座標圧縮装置を含むルート検索装置や、そのルート検索装置と、端末装置と、からなるナビゲーションシステムも提供する。また、これら座標圧縮装置やルート検索装置、ナビゲーションシステムの動作方法も提供する。
【発明の効果】
【００１４】
以上のような構成をとる本発明によって、処理負荷をかけることなく効率的に座標組のデータ量を圧縮することができる。また、それによって、例えば携帯電話網など比較的低速のネットワークを介した通信型のナビゲーションシステムなどにおいても、ストレスを感じないスピードで座標組をクライアント端末に送信することができる。
【図面の簡単な説明】
【００１５】
【図１】実施例１の座標圧縮装置における座標組の圧縮処理の一例を説明するための概念図
【図２】実施例１の座標圧縮装置における機能ブロックの一例を表す図
【図３】実施例１の座標圧縮装置の差分座標取得部での差分座標取得の一例を表す概念図
【図４】実施例１の座標圧縮装置の圧縮座標組出力部にて実行されるデータ圧縮処理の一例を表す概念図
【図５】実施例１の座標圧縮装置におけるハードウェア構成の一例を表す図
【図６】実施例１の座標圧縮装置における処理の流れの一例を表すフローチャート
【図７】実施例２の座標圧縮装置において取得される座標組の特徴を説明するための概念図
【図８】実施例２の座標圧縮装置における機能ブロックの一例を表す図
【図９】実施例２の座標圧縮装置における処理の流れの一例を表すフローチャート
【図１０】実施例３のルート検索装置における機能ブロックの一例を表す図
【図１１】実施例３のルート検索装置における処理の流れの一例を表すフローチャート
【図１２】実施例４のナビゲーションシステムの一例を表す概念図
【図１３】実施例４のナビゲーションシステムを構成する各装置の機能ブロックの一例を表す図
【図１４】実施例４のナビゲーションシステムにおける処理の流れの一例を表すフローチャート
【発明を実施するための形態】
【００１６】
以下に、図を用いて本発明の実施の形態を説明する。なお、本発明はこれら実施の形態に何ら限定されるものではなく、その要旨を逸脱しない範囲において、種々なる態様で実施しうる。
【００１７】
なお、実施例１は、主に請求項１、２、６、７について説明する。また、実施例２は、主に請求項３、８について説明する。また、実施例３は、主に請求項４、９について説明する。また、実施例４は、主に請求項５、１０について説明する。
【００１８】
≪実施例１≫
＜概要＞
図１は、本実施例の座標圧縮装置における座標組の圧縮処理の一例を説明するための概念図である。例えばユーザαがお気に入りのレストランを友人βに紹介するため、図１（ａ）にあるように地図データ上のレストランＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆを特定する。そしてユーザαは、本実施例の座標圧縮装置を利用して、図１（ｂ）に示すように上記レストランＡからＦの位置を示す緯度経度の値について差分を取り、６４進数値への変換などの処理を行うことで、送信するデータのサイズを例えば２０パーセントほどのサイズに圧縮して、その圧縮データをユーザβの端末に送信した。
【００１９】
このようにして、ユーザαは、通常よりも軽いデータサイズで友人βにお勧めのレストランの位置を教えることができる。
【００２０】
＜機能的構成＞
図２は、本実施例の座標圧縮装置における機能ブロックの一例を表す図である。なお、以下に記載する本座標圧縮装置の機能ブロックは、ハードウェア、ソフトウェア、又はハードウェア及びソフトウェアの両方として実現され得る。具体的には、コンピュータを利用するものであれば、ＣＰＵや主メモリ、バス、あるいは二次記憶装置（ハードディスクや不揮発性メモリ、ＣＤやＤＶＤなどの記憶メディアとそれらメディアの読取ドライブなど）、情報入力に利用される入力デバイス、印刷機器や表示装置、その他の外部周辺装置などのハードウェア構成部、またその外部周辺装置用のインターフェース、通信用インターフェース、それらハードウェアを制御するためのドライバプログラムやその他アプリケーションプログラム、ユーザインターフェース用アプリケーションなどが挙げられる。
【００２１】
そして主メモリ上に展開したプログラムに従ったＣＰＵの演算処理によって、入力デバイスやその他インターフェースなどから入力され、メモリやハードディスク上に保持されているデータなどが加工、蓄積されたり、上記各ハードウェアやソフトウェアを制御するための命令が生成されたりする。また、この発明は座標圧縮装置として実現できるのみでなく、方法としても実現可能である。また、このような発明の一部をソフトウェアとして構成することができる。さらに、そのようなソフトウェアをコンピュータに実行させるために用いるソフトウェア製品、及び同製品を記録媒体に固定した記録媒体も、当然にこの発明の技術的な範囲に含まれる（本明細書の全体を通じて同様である）。
【００２２】
そして、この図２にあるように、本実施例の「座標圧縮装置」（０２００）は、「座標組受付部」（０２０１）と、「基準座標選択部」（０２０２）と、「差分座標取得部」（０２０３）と、「圧縮座標組出力部」（０２０４）と、を有する。
【００２３】
「座標組受付部」（０２０１）は、地図上の位置を表す複数の座標を一組として座標組を受付ける機能を有し、例えばＣＰＵ（中央演算装置）や主メモリ、Ｉ／Ｏ（インプット／アウトプット）、座標組受付プログラムなどで実現することができる。また、「座標」とは位置を示すための数値情報をいい、例えば緯度経度情報のほか、本発明などにあわせ特別に設定された位置特定のための数値情報なども挙げられる。また、「複数の座標を一組」とは、緯度経度情報などの位置情報で示される座標点を複数まとめて一組とする、という意味である。
【００２４】
そして「座標組受付部」は、具体的に、例えば上記概要のようにユーザ端末に対して地図を提示し、ユーザによる地図上の任意の複数地点を指定する操作入力に応じて、当該複数地点の緯度経度情報を座標組として受付ける、などの構成が挙げられる。あるいは、ランドマーク名とそのランドマークのある位置の緯度経度情報を関連付けたテーブルデータを参照し、ユーザによって入力された複数のランドマーク名の緯度経度情報を座標組として受付ける構成も挙げられる。また、ＧＰＳ（全地球測位システム）を利用した位置測定情報や、その他の位置測定方法（例えば無線ＬＡＮスポットや携帯電話基地局の固有位置情報などを利用した位置測定方法）による位置測定情報に基づいて、複数の緯度経度情報などの座標の組を取得する構成も挙げられる。
【００２５】
また、実施例３などで後述するように、ルート検索の結果求められたルートを表す複数の緯度経度情報を座標組として受付けても良い。もちろん上記以外のその他の構成によって複数の座標の組を受付けても良い。
【００２６】
このように、本実施例の座標圧縮装置では複数の座標を示す数値情報を取得する。そして、当該座標情報は、主に所定範囲の地図上に含まれる複数点を示すものであるため隣接点の座標情報の組で構成されることが多い。したがって、上位桁の数字が近似しており、高いデータ量圧縮を行うことができる点を特徴とする。
【００２７】
「基準座標選択部」（０２０２）は、取得した座標組に含まれる複数の座標の中から基準座標を選択する機能を有し、例えば、ＣＰＵや主メモリ、基準座標選択プログラムなどによって実現することができる。この基準座標の選択方法としては、具体的には、例えば座標組の中で１番最初／最後に受付けた座標点を基準座標として選択する方法などが挙げられる。この場合、例えば「３５．６７５２８７、３５．６７５４４０、３５．６７５７４１」という座標（緯度）組に関して、最初の「３５．６７５２８７」を基準座標として選択する、という具合である。
【００２８】
また、１の座標を固定的に基準座標とする選択方法のほか、階差的（相対的）に前項の座標を基準座標として選択する方法も挙げられる。その場合には、基準座標選択部が、図示しない「相対選択手段」を有すると良い。「相対選択手段」とは、基準座標として、差分座標として表されるべき座標をも選択する機能を有する。具体的には、例えば前掲の「３５．６７５２８７、３５．６７５４４０、３５．６７５７４１」という座標（緯度）組に関して、２番目の「３５．６７５４４０」に対してはその前の「３５．６７５２８７」を基準座標として選択する。また、３番目の「３５．６７５７４１」に対してはその前の「３５．６７５４４０」を基準座標として選択する、という具合である。
【００２９】
上記のようにこの基準座標選択部にて基準座標を固定的／相対的に選択することで、次の差分座標取得部にて座標組に含まれる複数の各座標を基準座標からの差分値として表すことができる。
【００３０】
「差分座標取得部」（０２０３）は、座標組に含まれる基準座標と他の座標との差分演算を行い、当該他の座標を差分座標として取得する機能を有し、例えばＣＰＵや主メモリ、差分座標取得プログラムなどによって実現することができる。具体的には、図３（ａ）にあるように、例えば「３５．６７５２８７、３５．６７５４４０、３５．６７５７４１、３５．６７６０９１、・・・」という座標（緯度）組が取得され、その中で最初の「３５．６７５２８７」が基準座標として選択された。するとこの差分座標取得部では、その他の座標と基準座標との差分値「３５６７５２８７、＋１５３、＋４５４、＋８０４、・・・」を演算し、それを差分座標として取得する、という具合である。
【００３１】
また、図３（ｂ）にあるように、例えば基準座標として階差的に前項の座標を選択する場合、この差分座標取得部では、差分値として「３５６７５２８７、＋１５３、＋３０１、＋３５０、・・・」を演算し、それを差分座標として取得する。
【００３２】
このように、座標組を基準座標との差分で表すことで、そのデータビット量を低減することができる。さらに本実施例では、主に所定範囲の地図上に含まれる複数点を示す座標の組であるため、緯度経度などの上位桁の数字が近似しており、高いデータ圧縮となる点を特徴とする。
【００３３】
なお、上記例では１番最初の座標については差分ではなくそのままの８桁の緯度経度値として表されているが、以下のような構成によってその桁数を減じ、データ量を削減するようしても良い。すなわち、基準座標選択部において、例えば日本であれば東京都港区麻布台にある緯度経度原点（３５．３９２９１５７、１３９．４４２８８７５）など所定の座標を絶対的な基準座標として選択する。そして、前述の例では、固定的／相対的いずれの場合でもそのまま８桁の緯度経度値で表されていた１番最初の座標を、その絶対的な基準座標との差分値として表すとともに、日本の絶対的な基準座標を識別するための符号「０１」などを付加する。このようにして、伸張する装置側で識別符号と絶対的な基準座標との関係を示すテーブルデータを保持しておく必要があるものの、１番最初の座標の桁数も減じることができるので、さらにデータ圧縮率を高めることができる。
【００３４】
また、東京都の絶対的な基準座標、神奈川県の絶対的な基準座標といった具合に、地域をさらに細かい単位で分割して絶対的な基準座標を設けるよう構成しても良い。その場合には、ＧＰＳ測位情報やユーザ入力情報などに応じて、複数の絶対的な基準座標から好適な座標が選択されるよう構成すると良い。
【００３５】
「圧縮座標組出力部」（０２０４）は、差分座標として表されない基準座標と差分座標とを一組として、この座標組を受付けた座標組に対応する圧縮座標組として出力する機能を有し、例えばＣＰＵや主メモリ、圧縮座標組出力プログラムなどによって実現することができる。
【００３６】
また、上記のように座標組に含まれる複数の座標を基準座標との差分値にて表すことで所定のビットデータ量圧縮を実現することができるが、この圧縮座標組出力部にてその差分値で表された座標組に対する別のデータ圧縮処理をさらに実行するよう構成しても良い。具体的には、例えば図４に示すように、まずプラスまたはマイナスの符号が付された上記差分値を絶対値化し、さらに２進数変換処理を行う。そして変換後の２進数値に対して、上記絶対値化処理以前の当該数値のプラス又はマイナスの符号を示す符号ビットを、例えばプラスならば「１」、マイナスならば「０」として２進数値の最後尾に付加する。
【００３７】
つづいて、その数値列を５ビット単位で分割し、次の５ビット単位と組み合わせて一の座標情報を形成する単位には「０」を付加し、一の座標情報の終端となる５ビット単位には「１」を付加する（一の座標情報が緯度と経度で表される場合は、緯度と経度それぞれの終端に「１」を付加すると良い）。そして、このようにして６ビット単位とした２進数値を、６ビットデータを１文字で表せる６４（＝２６）進数値に変換する。
【００３８】
以上の処理によって、６個の地点を示す緯度経度情報を、例えば「４８２ｓｉｔｇｋＣ２ＭＶｉＢｃ５ＡＲｍＺＧＶｑｐｇｌＥＤｍｔＵｂ」といった３２個の文字列で表すことができる。したがって、この場合２０パーセントほどのデータサイズに圧縮することができる。
【００３９】
またもちろん、本実施例の座標圧縮装置の処理によって圧縮され出力された圧縮座標組は、上記の圧縮処理とは逆の伸張処理を行うことで簡単に復元することができる。
【００４０】
＜ハードウェア構成＞
図５は、上記機能的な各構成要件をハードウェアとして実現した際の、座標圧縮装置における構成の一例を表す概略図である。この図を利用して座標組のデータ量圧縮処理におけるそれぞれのハードウェア構成部の働きについて説明する。
【００４１】
この図にあるように、座標圧縮装置は、基準座標選択部、差分座標取得部、および圧縮座標組出力部であり、またその他の各種演算処理を実行する「ＣＰＵ」（０５０１）と、「主メモリ」（０５０２）と、を備えている。また各種データやプログラムなどを蓄積保持する「フラッシュメモリ」（０５０３）や、座標組受付部である「Ｉ／Ｏ」（０５０４）も備えている。そしてそれらが「システムバス」などのデータ通信経路によって相互に接続され、情報の送受信や処理を行う。
【００４２】
また、「主メモリ」にはプログラムが読み出され、「ＣＰＵ」は読み出された当該プログラムを参照し、プログラムで示される手順に従い各種演算処理を実行する。また、この「主メモリ」や「フラッシュメモリ」にはそれぞれ複数のアドレスが割り当てられており、「ＣＰＵ」の演算処理においては、そのアドレスを特定し格納されているデータにアクセスすることで、データを用いた演算処理を行うことが可能になっている。
【００４３】
ここでユーザ入力結果やルート検索結果などに応じて特定される複数の座標（緯度経度情報など）の組を、「Ｉ／Ｏ」を介して取得すると、「ＣＰＵ」は座標組受付プログラムにしたがってそれら座標を「主メモリ」のアドレス１などに格納する。つづいて「ＣＰＵ」は、基準座標選択プログラムを解釈し、その解釈結果にしたがって、例えば「主メモリ」に格納された座標組の中で、１番最初に取得された座標を基準座標として選択し、「主メモリ」のアドレス２に格納する。なお、この選択処理は、前述のように一の座標を固定的に基準座標として選択しても良いし、座標の差分を階差的にとるために前項の座標を相対的に基準座標として順次選択する処理としても良い。また座標が緯度経度で示されていれば、緯度と経度それぞれについて基準座標を選択する。そして「ＣＰＵ」は、差分座標取得プログラムを解釈し、その解釈結果にしたがって、固定的／相対的に選択された基準座標と次の座標との差分値を、緯度と経度のそれぞれについて四則演算処理によって算出し、「主メモリ」のアドレス３などに格納する。
【００４４】
その後、「ＣＰＵ」は圧縮座標組出力プログラムを解釈し、その解釈結果に従って、例えば「主メモリ」に格納された最初の基準座標値や差分座標値を絶対値化した後、２進数値に変換する。つづいて変換した２進数値に絶対値化前のプラス又はマイナスの符号を示す符号ビットを付加し、その数字列を５ビット単位に分割する。そして、次の５ビット単位と組み合わせて一の座標情報を形成する単位には「０」を付加し、一の座標情報の終端となる５ビット単位には「１」を付加する。そして、このようにして６ビット単位とした２進数値を例えば「４８２ｓｉｔ・・・」といった具合に６４進数値に変換し、「主メモリ」のアドレス４に格納する。
【００４５】
そして、このようにしてデータ量が大幅に削減された圧縮座標組のデータは、時間をかけずに他の端末装置などに送信することができる。
【００４６】
＜処理の流れ＞
図６は、本実施例の座標圧縮装置における処理の流れの一例を表すフローチャートである。なお、以下に示すステップは、上記のような計算機の各ハードウェア構成によって実行されるステップであっても良いし、媒体に記録され、計算機を制御するためのプログラムを構成する処理ステップであっても構わない。
【００４７】
この図にあるように、まず、例えばユーザ入力やルート検索処理などで特定されるなどした地図上の位置を表す複数の座標を一組として、Ｉ／Ｏなどを介してその座標組を受付ける（ステップＳ０６０１）。つづいて、取得した座標組に含まれる複数の座標の中から、例えば最初に取得された座標などを基準座標として選択し（ステップＳ０６０２）、座標組に含まれる他の座標の基準座標との差分値を演算して、当該他の座標を表す差分座標として取得する（ステップＳ０６０３）。なお、前述のように基準座標はステップＳ０６０２で選択した一の座標を固定的に利用しても良いし、この図に示すようにステップＳ０６０３にて一の座標について差分座標を取得するたびに、階差をとるため前項の座標を基準座標として選択し直す構成としても良い。
【００４８】
そして、差分座標として表されない基準座標と差分座標とを一組に対して、例えば前述の絶対値化処理や２進数変換処理、符号ビットの付加処理、５ビット単位への分割処理、６４進数変換処理などを行い、データ量の削減された圧縮座標組を出力する（ステップＳ０６０４）。
【００４９】
＜効果の簡単な説明＞
以上のように本実施例の座標圧縮装置によって、座標組を基準座標との差分で表すことで、そのデータビット量を低減することができる。さらに本実施例では、主に所定範囲の地図上に含まれる複数点を示す座標の組であるため、緯度経度などの上位桁の数字が近似しており、高いデータ圧縮となる点を特徴とする。
【００５０】
したがって、例えば携帯電話網など比較的低速のネットワークを介した通信型のナビゲーションシステムなどにおいても、ストレスを感じないスピードで座標組をクライアント端末に送信することができる。
【００５１】
≪実施例２≫
＜概要＞
本実施例は、上記実施例を基本として、座標組受付部にて受付ける座標組が、地図上のルートを示すための複数の座標点であることを特徴とする座標圧縮装置である。図７に示すように、ある地点Ａから別の地点Ｂを結ぶルートを示す複数の座標点ａ〜ｄは、それぞれが「近接」し、かつ「連続」したものとなる。したがって、階差をとるために前項の座標を基準座標として選択し相対的に差分をとると、その差分値は比較的小さな値をとることになり、高い圧縮効率を実現することができる、という具合である。
【００５２】
＜機能的構成＞
図８は、本実施例の座標圧縮装置における機能ブロックの一例を表す図である。この図にあるように、本実施例の「座標圧縮装置」（０８００）は、上記実施例を基本として、「座標組受付部」（０８０１）と、「基準座標選択部」（０８０２）と、「差分座標取得部」（０８０３）と、「圧縮座標組出力部」（０８０４）と、「相対選択手段」（０８０５）と、を有する。なお、これらの構成要件に関する詳細な説明は、上記実施例にて記載済みなので省略する。
【００５３】
そして、本実施例の座標圧縮装置の特徴点は、座標組受付部が「ルート組受付手段」（０８０６）をさらに有する点と、基準座標選択部が「隣接座標選択手段」（０８０７）をさらに有する点である。
【００５４】
「ルート組受付手段」（０８０６）は、地図上のルートを、複数の座標を隣同士連続させた線として表現するために、当該複数の座標をルート組として受付ける機能を有し、例えば、ＣＰＵや主メモリ、Ｉ／Ｏ、ルート組受付プログラムなどで実現することができる。また「ルート」とは、ある地点から別の地点を結ぶ道路などの移動経路を示す地図上の線をいう。そして前述のようにルートは線であるので、そのルートを表現する座標点の組は「近接」し、かつ「連続」したものとなることを特徴とする。
【００５５】
「隣接座標選択手段」（０８０７）は、ルート組に含まれる複数の座標の中から、常に差分座標取得部での演算対象となる座標に隣接する座標を基準座標として選択する機能を有し、例えばＣＰＵや主メモリ、隣接座標選択プログラムなどで実現できる。そして、前述のようにルートの座標組は「連続」したものであるため、基本的には隣接点との差分をとると、非隣接点同士の差分値と比較してその差分値は小さい値となる。
【００５６】
したがって、本実施例の座標圧縮装置ではさらに高い圧縮効率で、座標組を圧縮することができる。
【００５７】
＜処理の流れ＞
図９は、本実施例の座標圧縮装置における処理の流れの一例を表すフローチャートである。なお、以下に示すステップは、上記のような計算機の各ハードウェア構成によって実行されるステップであっても良いし、媒体に記録され、計算機を制御するためのプログラムを構成する処理ステップであっても構わない。
【００５８】
この図にあるように、まず、例えばユーザ入力やルート検索処理などで特定されるなどした地図上のルートを複数の座標を隣同士連続させた線として表現するために、当該複数の座標をルート組としてＩ／Ｏなどを介して受付ける（ステップＳ０９０１）。つづいて、取得したルート組に含まれる複数の座標の中から、例えば最初に取得された座標などを基準座標として選択し（ステップＳ０９０２）、基準座標に隣接する２番目の座標と基準座標との差分値を演算して、当該２番目の座標を表す差分座標を取得する（ステップＳ０９０３）。
【００５９】
つづいて、今度は２番目の座標を基準座標として、その２番目の座標点に隣接する３番目の座標の差分値の演算を行い、当該３番目の座標を表す差分座標を取得する。そして、この処理を全てのルート組に含まれる座標に対して実行する（ステップＳ０９０４）まで繰返す。
【００６０】
そして、差分座標として表されない基準座標と差分座標とを一組に対して、例えば前述の絶対値化処理や２進数変換処理、符号ビットの付加処理、５ビット単位への分割処理、６４進数変換処理など行い、データ量の削減された圧縮座標組を出力する（ステップＳ０９０５）。
【００６１】
＜効果の簡単な説明＞
以上のように本実施例の座標圧縮装置によって、ルートを示す「連続」した座標組に対して隣接点との差分をとることができる。したがって、本実施例の座標圧縮装置ではさらに高い圧縮効率で、座標組を圧縮することができる。
【００６２】
≪実施例３≫
＜概要＞
本実施例は、上記実施例の座標圧縮装置をハードウェア、又は／及びソフトウェア的に組み込んだことを特徴とするルート検索装置である。
【００６３】
＜機能的構成＞
図１０は、本実施例のルート検索装置における機能ブロックの一例を表す図である。この図にあるように、本実施例の「ルート検索装置」（１０００）には、上記実施例２の座標圧縮装置が含まれ、したがって「座標組受付部」（１００１）と、「基準座標選択部」（１００２）と、「差分座標取得部」（１００３）と、「圧縮座標組出力部」（１００４）と、「相対選択手段」（１００５）と、「ルート組受付手段」（１００６）と、「隣接座標選択手段」（１００７）と、を有する。なお、これらの構成要件に関する詳細な説明は、上記実施例にて記載済みなので省略する。
【００６４】
そして、本実施例のルート検索装置は、さらに「地点情報取得部」（１００８）と、「ルート検索部」（１００９）と、「ルート組出力部」（１０１０）と、を有する。
【００６５】
「地点情報取得部」（１００８）は、複数の地点を示す地点情報を取得する機能を有し、ＣＰＵや主メモリ、Ｉ／Ｏ、地点情報取得プログラムなどによって実現できる。「地点情報」とは、地点を示す情報をいい、例えば緯度経度情報やその他の地図上の位置を示す座標情報、あるいはそれら地点情報と関連付けられたランドマーク名や住所名などが挙げられる。そしてこの地点情報取得部は、具体的には、通常のルート検索装置と同様に、例えばＧＰＳによる測位情報や、ユーザによる地図上の点やランドマーク名の指定入力などの情報に応じて複数の地点を示す地点情報を取得する、という具合である。
【００６６】
「ルート検索部」（１００９）は、取得した地点情報に基づき前記複数の地点を結ぶルートを検索する機能を有し、例えばＣＰＵや主メモリ、ルート検索プログラムなどによって実現することができる。具体的には、通常のルート検索装置と同様に、例えばダイクストラ法やその他のルート検索アルゴリズムを利用して、複数の地点を結ぶルートを検索する、という具合である。
【００６７】
「ルート組出力部」（１０１０）は、検索されたルートを示す複数の座標をルート組受付手段に対して出力する機能を有し、例えばＣＰＵや主メモリ、Ｉ／Ｏ、ルート組出力プログラムなどによって実現することができる。このようにして、本実施例のルート検索装置では、例えばユーザが指定入力などした複数の地点を結ぶルートを検索し、その検索結果を示す連続した複数の座標からなるルート組のデータ量を、高い圧縮率で圧縮することができる。
【００６８】
＜処理の流れ＞
図１１は、本実施例のルート検索装置における処理の流れの一例を表すフローチャートである。なお、以下に示すステップは、上記のような計算機の各ハードウェア構成によって実行されるステップであっても良いし、媒体に記録され、計算機を制御するためのプログラムを構成する処理ステップであっても構わない。
【００６９】
この図にあるように、まず、例えばＧＵＩを介したユーザからの指定入力などに応じて、複数の地点情報を取得する（ステップＳ１１０１）と、例えばダイクストラ法に基づくアルゴリズムなどにしたがって、取得した複数の地点を結ぶ、複数の座標を隣同士連続させた線として表現したルートを検索する（ステップＳ１１０２）。そして、そのルート検索によって特定されたルートを示す複数の座標をルート組として出力する（ステップＳ１１０３）。そして出力されたルート組を取得し（ステップＳ１１０４）、その中から、例えば最初に取得された座標などを基準座標として選択し（ステップＳ１１０５）、基準座標に隣接する２番目の座標と基準座標との差分値を演算して、当該２番目の座標を表す差分座標を取得する（ステップＳ１１０６）。
【００７０】
つづいて、今度は２番目の座標を基準座標として、その２番目の座標点に隣接する３番目の座標の差分値の演算を行い、当該３番目の座標を表す差分座標を取得する。そして、この処理を全てのルート組に含まれる座標に対して実行する（ステップＳ１１０７）まで繰返す。
【００７１】
そして、差分座標として表されない基準座標と差分座標とを一組に対して、例えば前述の絶対値化処理や２進数変換処理、符号ビットの付加処理、５ビット単位への分割処理、６４進数変換処理など行い、データ量の削減された圧縮座標組を出力する（ステップＳ１１０８）。
【００７２】
＜効果の簡単な説明＞
以上のように、本実施例のルート検索装置によって、例えばユーザが指定入力などした複数の地点を結ぶルートを検索し、その検索結果を示す連続した複数の座標からなるルート組のデータ量を、高い圧縮率で圧縮することができる。
【００７３】
≪実施例４≫
＜概要＞
本実施例は、図１２にあるように、上記実施例にて説明したルート検索装置と、そのルート検索装置に対してルート検索をリクエストし、またそのレスポンス（検索結果）を示す圧縮座標組を受信する（複数の）端末装置と、からなることを特徴とするナビゲーションシステムである。
【００７４】
＜機能的構成＞
図１３は、本実施例のナビゲーションシステムを構成する各装置の機能ブロックの一例を表す図である。この図にあるように、本実施例のナビゲーションシステムは、「ルート検索装置」（１３００）と、「端末装置」（１３１０）と、からなる。
【００７５】
そして、「ルート検索装置」は、上記実施例を基本として図示しない「座標組受付部」と、「基準座標選択部」と、「差分座標取得部」と、「圧縮座標組出力部」と、「相対選択手段」と、「ルート組受付手段」と、「隣接座標選択手段」と、「地点情報取得部」と、「ルート検索部」と、「ルート組出力部」と、を有する。なお、これらの構成要件に関する詳細な説明は、上記実施例にて記載済みなので省略する。
【００７６】
そして、さらにこのルート検索装置は、「地点情報受信部」（１３０１）と、「圧縮座標組返信部」（１３０２）と、を有する。
【００７７】
「地点情報受信部」（１３０１）は、端末装置から送信された前記地点情報を受信する機能を有し、ＣＰＵや主メモリ、Ｉ／Ｏ、地点情報受信プログラムなどで実現することができる。具体的には、例えばインターネットなどの通信回線網を介して、端末装置に対して地点情報入力用の地図などを含むＧＵＩ用データを送信する。そして、当該ＧＵＩを利用して入力され、ＨＴＴＰリクエストとして送信されてきた地点情報を受信する、という具合である。
【００７８】
「圧縮座標組返信部」（１３０２）は、前記受信した地点情報に基づく圧縮座標組を端末装置に返信する機能を有し、例えばＣＰＵや主メモリ、Ｉ／Ｏ、圧縮座標組返信プログラムなどで実現することができる。具体的には、上記実施例にて記載したような処理により受信した地点情報からルート検索を実行し、検索されたルートを示す座標の組に対して圧縮座標組を生成する処理を実行する。そして、例えば地点情報受信部で受信した地点情報を含むＨＴＴＰリクエストへのレスポンスとして、そのリクエストの送信元の端末装置に対して生成した圧縮座標組を返信する、という具合である。
【００７９】
また、圧縮座標組の返信先として、例えば前記地点情報入力のためのＧＵＩなどにて返信先の端末装置を指定する情報が予め入力されていれば、当該返信先指定情報にしたがった別の端末装置を返信先として処理を行っても良い。
【００８０】
以上が、本実施例のナビゲーションシステムを構成する「ルート検索装置」の構成要件の説明である。続いて、同じく本実施例のナビゲーションシステムを構成する「端末装置」について図１３を用いて説明する。なお、「端末装置」とは、エンドユーザの利用する装置（Ｐ２Ｐ型のシステムにおいては全ユーザの利用装置）をいい、例えばデスクトップＰＣ（パーソナルコンピュータ）やノートＰＣ、スマートフォン、携帯電話などが挙げられる。
【００８１】
そして、この図１３にあるように「端末装置」（１３１０）は、「地点情報入力受付部」（１３１１）と、「地点情報送信部」（１３１２）と、「圧縮座標組受信部」（１３１３）と、「伸張部」（１３１４）と、「復元部」（１３１５）と、を有する。
【００８２】
「地点情報入力受付部」（１３１１）は、地点情報の入力を受付ける機能を有し、例えばＣＰＵや主メモリ、入力デバイス、そしてＧＵＩを含む地点情報入力受付プログラムなどが挙げられる。なお、「地点情報」とは、地点を示す情報をいい、例えばルート検索の際の出発地、目的地及び経由地等の地点を示す情報が挙げられる。そしてこの地点情報入力受付部では、具体的に、例えば端末装置のディスプレイ上に地図画像を表示し、ユーザが入力デバイスで指定した地図上のカーソル位置を入力された地点情報として受付ける方法などが挙げられる。あるいは、「東京駅」などランドマーク名や住所名などを、プルダウンメニューなどを利用して選択入力したり、テキスト入力欄を利用してフリー入力したりする方法なども挙げられる。
【００８３】
「地点情報送信部」（１３１２）は、受付けた地点情報を前記ルート検索装置に送信する機能を有し、例えばＣＰＵや主メモリ、Ｉ／Ｏ、地点情報送信プログラムなどで実現することができる。
【００８４】
「圧縮座標組受信部」（１３１３）は、送信した地点情報に応じて返信される圧縮座標組を受信する機能を有し、例えばＣＰＵや主メモリ、Ｉ／Ｏ、圧縮座標組受信プログラムなどで実現することができる。
【００８５】
「伸張部」（１３１４）は、受信した圧縮座標組を元の基準座標と差分座標の組に伸張する機能を有し、例えばＣＰＵや主メモリ、伸張プログラムなどによって実現できる。具体的には、例えば上記実施例の圧縮座標組出力部にて説明した処理と逆の処理、すなわち６４進数値で表されている圧縮座標組であれば、（１）２進数値への変換処理、（２）６ビット単位で最後の符合を参照した終端判断処理、（３）プラスかマイナスかを示す符号ビットの削除処理、（４）１０進数値への変換処理、（５）削除した符合ビットに応じたプラス又はマイナスの符号付加処理などを行うと良い。そして、この伸張処理によって、例えば「４８２ｓｉｔｇｋＣ２ＭＶｉＢｃ５ＡＲｍＺＧＶｑｐｇｌＥＤｍｔＵｂ」という圧縮座標組が、「３５６７５２８７、＋１５３、＋３０１、＋３５０、・・・」といった（差分座標として表されない）基準座標と差分値のデータに変換される、という具合である。
【００８６】
「復元部」（１３１５）は、基準値と差分値の組から複数の座標の組を復元する機能を有し、例えばＣＰＵや主メモリ、復元プログラムなどによって実現できる。具体的には、「３５６７５２８７、＋１５３、＋３０１、＋３５０、・・・」という差分値を含み表された座標の組を、「３５．６７５２８７、３５．６７５４４０、３５．６７５７４１、３５．６７６０９１、・・・」という全ての点が緯度経度で表される座標の組に復元する、という具合である。
【００８７】
このようにして、本実施例のナビゲーションシステムでは、端末装置からの入力受付に応じて行ったルート検索結果を示す複数の座標を、データ量を削減した圧縮座標組としてインターネット網などを介して簡単に送受信することができる。
【００８８】
なお、例えばユーザＡがユーザＢにルートを教える場合など、地点情報を送信する端末装置と、それに基づいて返信された圧縮座標組を伸張、復元し地図上などに表示する端末装置とは別体の装置であっても良い。すなわち本実施例のナビゲーションシステムは、ユーザＡの端末装置がルート検索装置に地点情報を送信し、その結果返信された圧縮座標組をユーザＢの端末装置に転送して、そこで伸張部および復元部の処理が実行される、という構成であっても良い。
【００８９】
＜処理の流れ＞
図１４は、本実施例のナビゲーションシステムにおける処理の流れの一例を表すフローチャートである。なお、以下に示すステップは、上記のような計算機の各ハードウェア構成によって実行されるステップであっても良いし、媒体に記録され、計算機を制御するためのプログラムを構成する処理ステップであっても構わない。
【００９０】
この図にあるように、まず、端末装置にてＧＵＩなどを介して複数の地点情報の入力を受付ける（ステップＳ１４１１）と、端末装置はルート検索装置に対して受付けた複数の地点情報を送信する（ステップＳ１４１２）。
【００９１】
ルート検索装置では、端末装置から送信された複数の地点情報を受信し、取得する（ステップＳ１４０１）と、例えばダイクストラ法に基づくアルゴリズムなどにしたがって、取得した複数の地点を結ぶ、複数の座標を隣同士連続させた線として表現したルートを検索する（ステップＳ１４０２）。そして、そのルート検索によって特定されたルートを示す当該複数の座標を出力し（ステップＳ１４０３）、取得する（ステップＳ１４０４）。そしてその中から、例えば最初に取得された座標などを基準座標として選択し（ステップＳ１４０５）、基準座標に隣接する２番目の座標と基準座標との差分値を演算して、当該２番目の座標を表す差分座標を取得する（ステップＳ１４０６）。
【００９２】
つづいて、今度は２番目の座標を基準座標として、その２番目の座標点に隣接する３番目の座標の差分値の演算を行い、当該３番目の座標を表す差分座標を取得する。そして、この処理を全てのルート組に含まれる座標に対して実行する（ステップＳ１４０７）まで繰返す。そして、差分座標として表されない基準座標と差分座標とを一組に対して、例えば前述の絶対値化処理や２進数変換処理、符号ビットの付加処理、５ビット単位への分割処理、６４進数変換処理など行い、データ量の削減された圧縮座標組を出力し（ステップＳ１４０８）、端末装置に対して返信する（ステップＳ１４０９）。
【００９３】
端末装置では、返信された圧縮座標組を受信する（ステップＳ１４１３）。そして、受信した圧縮座標組に対して伸張処理、例えば６４進数値から２進数値への変換処理や終端判断処理、符号ビットの削除処理、１０進数値への変換処理、プラス又はマイナスの符号付加処理などを実行し、基準座標と差分とで表される座標組を取得する（ステップＳ１４１４）。そして、取得した基準座標と差分とから、地図上の位置を表す複数の座標組を復元する（ステップＳ１４１５）。
【００９４】
＜効果の簡単な説明＞
以上のように、本実施例のナビゲーションシステムによって、端末装置からの入力受付に応じて行ったルート検索結果を示す複数の座標を、データ量を削減した圧縮座標組としてインターネット網などを介して簡単に送受信することができる。
【符号の説明】
【００９５】
０２００ 座標圧縮装置
０２０１ 座標組受付部
０２０２ 基準座標選択部
０２０３ 差分座標取得部
０２０４ 圧縮座標組出力部
【特許請求の範囲】
【請求項１】
地図上の位置を表す複数の座標を一組として座標組を受付ける座標組受付部と、
取得した座標組に含まれる複数の座標の中から基準座標を選択する基準座標選択部と、
座標組に含まれる基準座標と他の座標との差分演算を行い、当該他の座標を差分座標として取得する差分座標取得部と、
差分座標として表されない基準座標と差分座標とを一組として、この座標組を受付けた座標組に対応する圧縮座標組として出力する圧縮座標組出力部と、
を有する座標圧縮装置。
【請求項２】
基準座標選択部は、基準座標として、差分座標として表されるべき座標をも選択する相対選択手段を有する請求項１に記載の座標圧縮装置。
【請求項３】
座標組受付部は、
地図上のルートを、複数の座標を隣同士連続させた線として表現するために、当該複数の座標をルート組として受付けるルート組受付手段を有し、
基準座標選択部は、
ルート組に含まれる複数の座標の中から常に差分座標取得部での演算対象となる座標に隣接する座標を基準座標として選択する隣接座標選択手段を有する請求項２に記載の座標圧縮装置。
【請求項４】
請求項３に記載の座標圧縮装置を含むルート検索装置であって、
複数の地点を示す地点情報を取得する地点情報取得部と、
取得した地点情報に基づき前記複数の地点を結ぶルートを検索するルート検索部と、
検索されたルートを示す複数の座標をルート組受付手段に対して出力するルート組出力部と、
を有するルート検索装置。
【請求項５】
請求項４に記載のルート検索装置と、端末装置と、からなるナビゲーションシステムであって、
前記ルート検索装置が、
端末装置から送信された前記地点情報を受信する地点情報受信部と、
前記受信した地点情報に基づく圧縮座標組を端末装置に返信する圧縮座標組返信部と、
を有し、
前記端末装置が、
地点情報の入力を受付ける地点情報入力受付部と、
受付けた地点情報を前記ルート検索装置に送信する地点情報送信部と、
送信した地点情報に応じて返信される圧縮座標組を受信する圧縮座標組受信部と、
受信した圧縮座標組を元の基準座標と差分座標の組に伸張する伸張部と、
基準値と差分値の組から複数の座標の組を復元する復元部と、
を有するナビゲーションシステム。
【請求項６】
地図上の位置を表す複数の座標を一組として座標組を受付ける座標組受付ステップと、
取得した座標組に含まれる複数の座標の中から基準座標を選択する基準座標選択ステップと、
座標組に含まれる基準座標と他の座標との差分演算を行い、当該他の座標を差分座標として取得する差分座標取得ステップと、
差分座標として表されない基準座標と差分座標とを一組として、この座標組を受付けた座標組に対応する圧縮座標組として出力する圧縮座標組出力ステップと、
を計算機に実行させる座標圧縮装置の動作方法。
【請求項７】
基準座標選択ステップは、基準座標として差分座標として表されるべき座標をも選択する相対選択ステップを含みさらに計算機に実行させる請求項６に記載の座標圧縮装置の動作方法。
【請求項８】
座標組受付ステップは、
地図上のルートを、複数の座標を隣同士連続させた線として表現するために、当該複数の座標をルート組として受付けるルート組受付ステップを含み、
基準座標選択ステップは、
ルート組に含まれる複数の座標の中から常に差分座標取得ステップでの演算対象となる座標に隣接する座標を基準座標として選択する隣接座標選択ステップを含みさらに計算機に実行させる請求項７に記載の座標圧縮装置の動作方法。
【請求項９】
請求項８に記載の座標圧縮装置の動作方法を含むルート検索装置の動作方法であって、
複数の地点を示す地点情報を取得する地点情報取得ステップと、
取得した地点情報に基づき前記複数の地点を結ぶルートを検索するルート検索ステップと、
検索されたルートを示す複数の座標をルート組受付ステップに対して出力するルート組出力ステップと、
を計算機に実行させるルート検索装置の動作方法。
【請求項１０】
請求項９に記載のルート検索装置の動作方法と、端末装置の動作方法と、を含むナビゲーションシステムの動作方法であって、
前記ルート検索装置の動作方法において、
端末装置から送信された前記地点情報を受信する地点情報受信ステップと、
前記受信した地点情報に基づく圧縮座標組を端末装置に返信する圧縮座標組返信ステップと、
をさらに計算機に実行させ、
前記端末装置の動作方法が、
地点情報の入力を受付ける地点情報入力受付ステップと、
受付けた地点情報を前記ルート検索装置に送信する地点情報送信ステップと、
送信した地点情報に応じて返信される圧縮座標組を受信する圧縮座標組受信ステップと、
受信した圧縮座標組を元の基準座標と差分座標の組に伸張する伸張ステップと、
基準値と差分値の組から複数の座標の組を復元する復元ステップと、
を計算機に実行させるナビゲーションシステムの動作方法。
【請求項１】
地図上の位置を表す複数の座標を一組として座標組を受付ける座標組受付部と、
取得した座標組に含まれる複数の座標の中から基準座標を選択する基準座標選択部と、
座標組に含まれる基準座標と他の座標との差分演算を行い、当該他の座標を差分座標として取得する差分座標取得部と、
差分座標として表されない基準座標と差分座標とを一組として、この座標組を受付けた座標組に対応する圧縮座標組として出力する圧縮座標組出力部と、
を有する座標圧縮装置。
【請求項２】
基準座標選択部は、基準座標として、差分座標として表されるべき座標をも選択する相対選択手段を有する請求項１に記載の座標圧縮装置。
【請求項３】
座標組受付部は、
地図上のルートを、複数の座標を隣同士連続させた線として表現するために、当該複数の座標をルート組として受付けるルート組受付手段を有し、
基準座標選択部は、
ルート組に含まれる複数の座標の中から常に差分座標取得部での演算対象となる座標に隣接する座標を基準座標として選択する隣接座標選択手段を有する請求項２に記載の座標圧縮装置。
【請求項４】
請求項３に記載の座標圧縮装置を含むルート検索装置であって、
複数の地点を示す地点情報を取得する地点情報取得部と、
取得した地点情報に基づき前記複数の地点を結ぶルートを検索するルート検索部と、
検索されたルートを示す複数の座標をルート組受付手段に対して出力するルート組出力部と、
を有するルート検索装置。
【請求項５】
請求項４に記載のルート検索装置と、端末装置と、からなるナビゲーションシステムであって、
前記ルート検索装置が、
端末装置から送信された前記地点情報を受信する地点情報受信部と、
前記受信した地点情報に基づく圧縮座標組を端末装置に返信する圧縮座標組返信部と、
を有し、
前記端末装置が、
地点情報の入力を受付ける地点情報入力受付部と、
受付けた地点情報を前記ルート検索装置に送信する地点情報送信部と、
送信した地点情報に応じて返信される圧縮座標組を受信する圧縮座標組受信部と、
受信した圧縮座標組を元の基準座標と差分座標の組に伸張する伸張部と、
基準値と差分値の組から複数の座標の組を復元する復元部と、
を有するナビゲーションシステム。
【請求項６】
地図上の位置を表す複数の座標を一組として座標組を受付ける座標組受付ステップと、
取得した座標組に含まれる複数の座標の中から基準座標を選択する基準座標選択ステップと、
座標組に含まれる基準座標と他の座標との差分演算を行い、当該他の座標を差分座標として取得する差分座標取得ステップと、
差分座標として表されない基準座標と差分座標とを一組として、この座標組を受付けた座標組に対応する圧縮座標組として出力する圧縮座標組出力ステップと、
を計算機に実行させる座標圧縮装置の動作方法。
【請求項７】
基準座標選択ステップは、基準座標として差分座標として表されるべき座標をも選択する相対選択ステップを含みさらに計算機に実行させる請求項６に記載の座標圧縮装置の動作方法。
【請求項８】
座標組受付ステップは、
地図上のルートを、複数の座標を隣同士連続させた線として表現するために、当該複数の座標をルート組として受付けるルート組受付ステップを含み、
基準座標選択ステップは、
ルート組に含まれる複数の座標の中から常に差分座標取得ステップでの演算対象となる座標に隣接する座標を基準座標として選択する隣接座標選択ステップを含みさらに計算機に実行させる請求項７に記載の座標圧縮装置の動作方法。
【請求項９】
請求項８に記載の座標圧縮装置の動作方法を含むルート検索装置の動作方法であって、
複数の地点を示す地点情報を取得する地点情報取得ステップと、
取得した地点情報に基づき前記複数の地点を結ぶルートを検索するルート検索ステップと、
検索されたルートを示す複数の座標をルート組受付ステップに対して出力するルート組出力ステップと、
を計算機に実行させるルート検索装置の動作方法。
【請求項１０】
請求項９に記載のルート検索装置の動作方法と、端末装置の動作方法と、を含むナビゲーションシステムの動作方法であって、
前記ルート検索装置の動作方法において、
端末装置から送信された前記地点情報を受信する地点情報受信ステップと、
前記受信した地点情報に基づく圧縮座標組を端末装置に返信する圧縮座標組返信ステップと、
をさらに計算機に実行させ、
前記端末装置の動作方法が、
地点情報の入力を受付ける地点情報入力受付ステップと、
受付けた地点情報を前記ルート検索装置に送信する地点情報送信ステップと、
送信した地点情報に応じて返信される圧縮座標組を受信する圧縮座標組受信ステップと、
受信した圧縮座標組を元の基準座標と差分座標の組に伸張する伸張ステップと、
基準値と差分値の組から複数の座標の組を復元する復元ステップと、
を計算機に実行させるナビゲーションシステムの動作方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１０−２４５９１３（Ｐ２０１０−２４５９１３Ａ）
【公開日】平成２２年１０月２８日（２０１０．１０．２８）
【国際特許分類】
【出願番号】特願２００９−９３５７７（Ｐ２００９−９３５７７）
【出願日】平成２１年４月８日（２００９．４．８）
【出願人】（５００２５７３００）ヤフー株式会社 (1,128)
【Ｆターム（参考）】
【公開日】平成２２年１０月２８日（２０１０．１０．２８）
【国際特許分類】
【出願日】平成２１年４月８日（２００９．４．８）
【出願人】（５００２５７３００）ヤフー株式会社 (1,128)
【Ｆターム（参考）】
[ Back to top ]