移動通信端末機に地図情報を提供する方法およびシステム
本発明は、移動通信端末機で表示される可能性が高い地図データのみを前記移動通信端末機に送信することによって、地図データ送信の効率性を高めた、移動通信端末機への地図情報提供方法およびシステムに関する。本発明は、移動通信端末機へ地図情報を提供する方法を提供し、該方法は、複数の地図データを含む地図情報データベースを維持する段階と、前記移動通信端末機から経路探索要求を受信する段階と、前記経路探索要求に応答し、経路探索を遂行して経路を決定する段階と、前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階とを含む。本発明によると、移動通信端末機で表示される可能性が高い地図データのみを選択して前記移動通信端末機に送信することによって、地図データを効率的に伝送することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動通信端末機に地図情報を提供する方法に関し、より詳しくは、前記移動通信端末機で表示される可能性が高い地図データのみを前記移動通信端末機に送信することによって、地図データ送信の効率性を高めた地図情報提供方法およびシステムに関する。
【背景技術】
【０００２】
最近、通信網を用いたサービスの提供によって携帯型コンピュータおよび移動電話などの無線通信環境内における情報検索の機会が増加している。これに伴い、ユーザは自由に移動しながら、いつどこででも必要な情報サービスを検索して提供を受けることが可能となった。
【０００３】
ナビゲーションシステム(Navigation System)は、人工衛星を用いて車両などの運送装置(vehicle)の走行のための情報を提供するシステムであって、自動航法システムとも言われる。このようなナビゲーションシステムは、GPS受信機を用いて地球上に浮かんでいるGPS(global positioning system)衛星から所定のデータを受信し、前記受信されたデータに基づいて自分の位置を計算する。地球上には多数のGPS衛星が浮かんでいるが、運送装置は地球上のどの地域にいたとしても3つのGPS衛星からGPS信号を受信することができ、前記3つのGPS衛星から受信されたGPS信号に基づいて自分の位置を計算することができるようになっている。ナビゲーションシステムは、このように計算された自分の位置情報に基づいて多様な走行情報を前記車両などの運送装置に提供する。このようなナビゲーションシステムは、既存では主に航空機や船舶などの大型移動体の位置計算と航法に用いられていたが、最近では自動車などにも広く用いられている。前記ナビゲーションシステムは、運送装置の現在の位置情報、運送装置の現在の位置から前記運送装置の目的地までの経路情報、前記位置情報および経路情報と関連した地図情報、交通状況情報など、非常に多様な情報をユーザに提供している。
【０００４】
このようなナビゲーション装置において、運送装置の現在位置などの情報をユーザに伝達する時に地図を用いると、ユーザがより簡単に前記現在位置などの情報を認識することができるため、地図情報が共に提供されるのが一般的である。
【０００５】
従来技術によると、このような地図情報は、CD-ROMまたはDVD-ROMのような格納媒体を介して提供されていた。このような従来技術によるナビゲーション装置は、必要な度にCD-ROMなどの格納媒体に格納された地図情報を読み取り、これを所定の表示手段に表示していた。しかし、このような従来技術のナビゲーション装置において、地図情報を更新しなければならない場合、CD-ROMなどの格納媒体を交換する必要があるため、その後のアップデート時に相当な不便があった。すなわち、ユーザは前記地図情報を含んだCD-ROMの提供者から継続してCD-ROMを追加購入しなければならないという経済的および時間的負担が発生していた。また、前記地図情報の提供者が変更される地図情報をリアルタイムで反映したCD-ROMなどを製作してユーザに提供することは不可能であるため、変更された地図情報(例えば、道路、建物などが新しく生じたり消滅した場合)をリアルタイムでユーザに提供することができなかった。
【０００６】
また、いわゆるテレマティックス(tele-matics)と呼ばれる更に他の従来技術によると、移動電話などの移動通信端末機を用いたナビゲーションサービスが提供されている。前記テレマティックスサービスは、ユーザに音声を用いて道を案内したり、自分の車が交通事故にあった場合、GPS衛星を用いて自動的に事故車の位置を追跡し、最も近くに位置する119救助隊や病院などに前記情報を伝達することによって救難活動を簡単にしている。しかし、従来技術による移動電話などを用いたナビゲーションサービスにおいては、移動電話のメモリサイズによる制限のため、地図情報を移動電話に格納しておくことができないという問題点があった。これにより、前記従来技術によると、車の位置情報、走行情報などをユーザに提供する時、地図を共にユーザに提供することができずに音声またはテキスト形態で提供していたため、ユーザが従来技術によるナビゲーションシステムを用いることに不便さが生じていた。
【０００７】
これにより、移動通信端末機に通信網を用いて地図情報を提供することによって、道路などの地図情報の変更をリアルタイムで反映することができるナビゲーションシステムが要求されている。
【０００８】
しかし、移動通信端末機のメモリは制限的であるため、無制限的な地図データを前記移動通信端末機に提供することはあまり効率的ではない。また、移動通信端末機のメモリ容量が拡大されたとしても、このような地図情報を移動通信網を用いて送信する場合においては、いかなる場合であってもデータ通信量を減らす必要がある。なぜなら、データ通信量が多くなると、個別ユーザの立場では通信サービス料金が過多し、サービス提供者の立場では不必要なトラフィックを多く処理するようになるため、通信の効率性を阻害するようになる。
【０００９】
従って、前記移動通信端末機に通信網を用いて地図データを提供することにおいて、表示される可能性が高い地図データのみを送信することによって、地図データ送信の効率性を図る必要性がある。また、このようにユーザの移動通信端末機で表示される可能性が高い地図データを効率的に検索する方法も必要である。しかし、従来技術においては、このような問題点が全く認識されていないだけでなく、この解決策をも全く提示していない。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、前記のような従来技術を改善するために案出されたものであり、移動通信端末機で表示される可能性が高い地図データのみを選択して前記移動通信端末機に送信することによって、地図データを効率的に送信する地図情報提供方法およびシステムを提供することを目的とする。
【００１１】
また、移動通信端末機に表示される可能性が高い地図データを効率的に決定することができる方法およびシステムを提供することを他の目的とする。
【００１２】
また、移動通信端末機が経路を離脱した場合でも、前記離脱した位置と連関した地図をすぐに表示することができる方法およびシステムを提供することを他の目的とする。
【００１３】
また、経路周辺の地図データをハードウェアに大きい負荷を与えずに迅速に検索して移動通信端末機に提供する方法およびシステムを提供することを他の目的とする。
【００１４】
また、移動通信端末機が経路を離脱した場合、地図情報提供サーバ(ナビゲーションサーバ)に移動通信端末機の現在位置と隣接した地域に対する地図データを要請し、これを受信可能にすることによって、経路が離脱した場合でも効率的に処理することができる方法およびシステムを提供することを他の目的とする。
【課題を解決するための手段】
【００１５】
上記の目的を達成し、従来技術の問題点を解決するために、本発明は、複数の地図データを含む地図情報データベースを維持する段階と、前記移動通信端末機から経路探索要求を受信する段階と、前記経路探索要求に応答し、経路探索を遂行して経路を決定する段階と、前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階とを含む地図情報提供方法を提供する。この時、前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階において、本発明によるナビゲーションサーバは、前記決定された経路および前記決定された経路から一定範囲内に属する地図データを前記移動通信端末機に送信することができる。
【００１６】
本発明の一態様によって移動通信端末機に地図情報を提供する方法は、複数の地図データを含む地図情報データベースを維持する段階(前記地図データに含まれる道路と連関した道路データは、通行料に関する情報を含む)と、前記移動通信端末機から経路探索要求を受信する段階と、前記経路探索要求に応答して検索された複数の経路のうち、前記複数の経路と連関した道路の通行料が最も少ない経路を決定する段階と、前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階とを含む。
【００１７】
本発明の更に他の一態様による移動通信端末機に地図情報を提供する地図情報提供システムは、複数の地図データを格納する地図情報データベース(前記地図データのそれぞれは、図葉と連関する)と、前記移動通信端末機から経路探索要求を受信する受信部と、前記経路探索要求に応答し、経路探索を遂行して経路を決定する経路探索部と、前記決定された経路と連関した地図データを前記地図情報データベースから検索する地図データ検索部と、前記検索された地図データを前記移動通信端末機に送信する送信部とを含む。
【発明の効果】
【００１８】
以上の説明から知ることができるように、本発明によると、移動通信端末機で表示される可能性が高い地図データのみを選択して前記移動通信端末機に送信することによって、地図データを効率的に送信する地図情報提供方法およびシステムが提供される。
【００１９】
また、本発明によると、移動通信端末機に表示される可能性が高い地図データを効率的に決定することができ、移動通信端末機が経路を離脱した場合でも、前記離脱した位置と連関した地図をすぐに表示することができる。
【００２０】
また、本発明によると、経路周辺の地図データをハードウェアに大きい負荷を与えず、迅速に検索して移動通信端末機に提供することができる。
【００２１】
また、本発明によると、移動通信端末機が経路を離脱した場合、地図情報提供サーバ(ナビゲーションサーバ)に移動通信端末機の現在位置と隣接した地域に対する地図データを要請し、これを受信できるようにすることによって、経路が離脱した場合にも効率的に処理することができる。
【発明を実施するための最良の形態】
【００２２】
以下、添付された図面を参照して、本発明の実施例を詳しく説明する。
【００２３】
図1は本発明による地図情報提供サーバおよび移動通信端末機間の連結を示したブロック図である。
【００２４】
移動通信端末機(101、102)は携帯電話に限定されず、通信機能が支援される移動性のあるユーザ端末機を意味する。本発明の好ましい実施例において、移動通信端末機(101、102)は携帯電話端末機である。移動通信端末機(101、102)は、移動通信網(103)を介して本発明によるナビゲーションサーバ(104)に接続する。ナビゲーションサーバは、移動通信端末機(101、102)からのナビゲーションと関連したユーザ要請を受信してこれを処理する。ナビゲーションサーバ(104)は、地図情報を含む地図情報データベース(105)と連結する。地図情報データベースは、ナビゲーションサーバ(104)内に含まれて構成されることもある。移動通信端末機(101、102)は、自分の現在位置を確認するためにGPS受信機を内蔵したり、GPS受信機(未図示)と連結したりする。
【００２５】
図2は、本発明によるナビゲーションサーバの内部構成を示したブロック図である。
【００２６】
ナビゲーションサーバ(navigation server)(200)は、受信部(201)、経路探索部(202)、地図データ検索部(203)および送信部(204)を含む。
【００２７】
受信部(201)は、移動通信端末機からの経路探索要求など、ナビゲーションと関連した様々なユーザ要求を受信する。
【００２８】
経路探索部(202)は、ユーザの経路探索要求に応答して経路探索を遂行する。経路探索の方法は、最短経路(Shortest Path)検索、最適経路検索、無料道路優先経路検索などの方法が用いられる。最短経路検索は、出発地から目的地までの複数の経路のうち、出発地から目的地までの距離が最も短い経路を選択してユーザに提供する方法である。最適経路検索は、出発地から目的地までの複数の経路のうち、出発地から目的地までかかる予想時間が最も少ない経路を選択してユーザに提供する方法である。最適経路を検索するためには、各道路当りの平均時速のような速度情報、または現在の渋滞情報などのような交通情報などを参照する。無料道路優先経路検索は、出発地から目的地までの複数の経路のうち、各経路を通過するのに必要な通行料などの費用情報を参照し、このような費用が最も少なく発生する経路を選択してユーザに提供する方法である。このため、地図情報データベース(205)の地図データに含まれる道路と連関した道路データは、通行料などの費用に関する情報を含む。
【００２９】
地図データ検索部(203)は、経路探索部(202)で決定された経路と連関した地図データを地図情報データベース(205)から検索する。このように検索された地図データは送信部(204)に伝達され、送信部(204)は前記検索された地図データを移動通信端末機に経路探索情報と共に送信する。
【００３０】
ユーザが所定の出発地から目的地までの経路探索を要請したとすると、前記ユーザは、前記出発地から前記目的地まで前記経路に沿って走行する可能性が高い。従って、前記経路による地図データ(または前記経路および前記経路の周辺に対する地図情報)を前記ユーザ端末機に提供することによって、ユーザ端末機で表示される可能性が高いデータのみを送信することができるようになる。前記経路と関連したデータは、全体データと比較すると非常に小さい量のデータであるため、全体地図データを送信する場合と比較して見ると、本発明がいかに効率的であるかを知ることができる。
【００３１】
図3は、本発明による地図情報提供方法の手順を示した流れ図である。
【００３２】
段階(301)で、ナビゲーションサーバは、複数の地図データを含む地図情報データベースを維持する。地図情報データベースは、ナビゲーションサーバと物理的に独立して存在したり、物理的にナビゲーションサーバに含まれたりする。
【００３３】
段階(302)で、ナビゲーションサーバは、ユーザ端末機(ユーザの移動通信端末機)から経路探索要求を受信する。前記経路探索要求は、出発地および目的地に関する情報を含む。または、出発地が前記ユーザ端末機の現在位置であり、前記現在位置がすでにナビゲーションサーバに格納されていると、ユーザ端末機は、目的地に関する情報のみをナビゲーションサーバに送信して経路探索を要請することもある。
【００３４】
ユーザ端末機で経路を探索するための目的地を入力する画面の例が図4に示されている。図４（ａ）で、ユーザは、ユーザ端末機のナビゲーション関連メニューのうち、“2．目的地設定”を選択する。そうすると、図４（ｂ）で目的地設定のための多様な方法が提示される。“1．名称検索”は、目的地の名称を用いて検索する方法であり、"2．住所検索"は、目的地の住所を用いて検索する方法である。"3．住所録検索"は、ユーザがすでに住所録に登録している目的地に関する情報を用いて目的地を検索する方法であり、"4．電話番号簿検索"は、電話番号を用いて目的地を検索する方法である。
【００３５】
図４（ｂ）では名称を用いた検索を選択し、この場合、ユーザ端末機は、ユーザに名称の入力を要請する画面を表示する(未図示)。図４（ｃ）は、ユーザが前記名称として"ギャラリア"と入力した場合の出力画面である。ユーザ端末機は"ギャラリア"を含んだ様々な目的地候補のリストを表示する。このような目的地検索は、ユーザ端末機において目的地検索と関連した情報を全て含んでユーザ端末機が単独で遂行することもできるし、ナビゲーションサーバで必要な情報を格納し、前記ナビゲーションサーバとの通信を介して遂行することもできる。
【００３６】
図5は、ナビゲーションサーバに経路探索を要請するユーザインターフェイスを示した図である。出発地と目的地の設定が終わった後、ユーザは図５（ａ）で"走行経路設定"を選択して経路探索を要請する。この時、経路探索の方法が様々である場合、図５（ｂ）のように、経路探索の方法の中でどのような方法を用いるかをユーザに質疑する。図５（ｂ）は、ユーザが"最適経路"による経路探索を選択した画面である。このように、ユーザが経路探索を要請すると、このような経路探索要請はナビゲーションサーバに伝達される。
【００３７】
段階(303)で、ナビゲーションサーバは、ユーザの経路探索要求に応答して経路探索を遂行する。経路探索は、出発地から目的地までの一つ以上の候補経路のうち、一つを選択する。前記で説明したように、前記選択の方法としては、出発地から目的地までの距離が最も短い経路を選択する最短経路検索、出発地から目的地までかかる予想時間が最も少ない経路を選択する最適経路検索がある。また、本発明においては、地図情報データベース(205)の地図データに含まれる道路と連関した道路データは、通行料などの費用に関する情報を含み、出発地から目的地までの複数の経路のうち、各経路を通過するのに必要な通行料などの費用情報を参照し、このような費用が最も少なく発生する経路を選択する無料道路優先経路検索を支援する。
【００３８】
段階(304)では、段階(303)で決定された経路と連関した地図データを地図情報データベースを参照して検索する。経路探索の結果、決定された経路と連関した地図データを決定する方法に関しては、図7以下において詳しく説明する。
【００３９】
段階(305)では、前記検索された地図データを前記決定された経路情報と共に移動通信端末機に送信する。そうすると、移動通信端末機は、受信した経路情報および地図データに基づき、ユーザの走行情報を地図画面を用いて移動通信端末機のディスプレイに表示する。
【００４０】
図6は、本発明の一実施例によってナビゲーションサーバから受信した経路情報および地図情報に基づき、走行画面をユーザに提供するユーザインターフェイスを示した図である。
【００４１】
図６（ａ）で、ユーザが"走行スタート"を選択すると、図６（ｂ）のような経路探索情報がユーザに提供される。ユーザが図６（ｂ）で"走行スタート"を選択すると、図６（ｃ）に示されたように、ユーザの走行と関連した情報が受信された地図データを用いてユーザ端末機のディスプレイに表示される。
【００４２】
図7は、本発明の一実施例によってナビゲーションサーバにおける経路探索の結果、決定された経路が通る図葉の地図データを表示したものである。
【００４３】
全体地図データを一定サイズの複数の区域(セル)に区分して管理するのが地図データ管理上において便利であるため、図7に示されたように、全体地図データを複数のセルに分割する。この時、分割された一つのセルを図葉(701)と言う。図面符号(702)は、経路探索の結果、決定された経路を示したものである。前記で説明したように、経路と関連した地図データはユーザによって用いられる可能性が高いため、前記経路が通る図葉(図7にて灰色で表示された図葉)に該当する地図データをユーザ端末機に送信する地図データとして決定する。
【００４４】
ナビゲーションサーバは、上記のように決定された地図データをユーザの移動通信端末機に送信する。この時、本発明の一実施例によると、決定された経路が通る複数の図葉の全てと連関した地図データを一度に移動通信端末機に送信する。本実施例によると、経路と関連した全ての地図データを一度に移動通信端末機が受信するため、前記経路の進行中、移動通信端末機が追加で地図データを受信する必要がないという長所がある。
【００４５】
本発明の更に他の実施例によると、前記決定された経路が通る複数の図葉のうち、一部の図葉と連関した地図データをユーザの移動通信端末機に送信する。例えば、図7において灰色で表示された図葉のうち、出発地が含まれた図葉と連関した地図データをユーザの移動通信端末機に送信し、灰色で表示された残りの図葉と連関した地図データは、前記移動通信端末機の経路の進行に従って前記移動通信端末機に送信する。経路と関連した全体図葉と連関した地図データを一度に送信しようとすると時間が多く要されるが、一部の図葉と連関した地図データの送信は要される時間が相対的に少ない。従って、本実施例によると、移動通信端末機が優先的に必要とする少ない量の地図データを移動通信端末機に送信するため、短時間内に移動通信端末機で経路と関連した地図を表示することができるという長所がある。
【００４６】
本発明の一実施例によると、前記のように一部の図葉と連関した地図データを先に送信した後、前記移動通信端末機の経路進行に従って必要な図葉を予測し、適切な時点に必要な図葉と連関した地図データを送信する。例えば、図葉(703)と連関した地図データを送信した後、移動通信端末機が走行をして図葉(703)の地図領域を過ぎ、所定時間以内に図葉(704)の地域に移動することが予測される場合、図葉(704)を移動通信端末機に送信する。本実施例は、図8以下の他の実施例にも適用される。
【００４７】
本発明の更に他の実施例によると、一部の図葉を送信した後、移動通信端末機が地図を表示している間、バックグラウンド(background)で経路が通る残りの図葉と連関した地図データを移動通信端末機に送信する。本実施例は、図8以下の他の実施例にも適用される。
【００４８】
図8は、本発明の一実施例によって探索された経路の周辺領域を示した図である。
【００４９】
図7と関連した実施例においては、経路探索の結果から得られた経路が通る図葉と連関した地図データを移動通信端末機に送信するが、以下の実施例においては、経路探索の結果、決定された経路(801)および前記探索された経路から一定範囲内(802)に該当する地図データを移動通信端末機に送信する。本実施例によると、移動通信端末機が装着された車両などが前記経路探索された経路以外の経路で走行する場合でも、移動通信端末機がすでに経路周辺の地図データをダウンロードしているため、追加の地図データをダウンロードしなくてもすぐに現在の走行地点と関連した地図を移動通信端末機が表示することができる。また、探索された経路および探索された経路の周辺領域(buffered area)に関する地図データのみを送信するため、全体地図データを送信する場合に比べてデータ送信量が革新的に減少する。特にメモリサイズが大きくない携帯電話などに地図データを用いたナビゲーションサービスを提供するためには、このようにデータ送信量を革新的に減少させる方法が非常に重要である。このような周辺領域(buffered area)を決定する方法をバッファ検索(buffered search)と呼び、これと関連した詳細な実施例を図9以下で詳しく説明する。本発明においてバッファ検索とは、探索された経路周辺の客体を検索することを意味する。
【００５０】
図9は、本発明の一実施例によって決定された探索経路の周辺領域を示した図である。図9の実施例においては、経路探索の結果、決定された経路(901)を中心点として所定の半径を有する円(902)を決定する。その後、前記円の外郭線を全て含む領域(903)が本実施例で決定した周辺領域(buffered area)となる。本実施例においては、前記決定された周辺領域が属する図葉を決定する。すなわち、前記決定された経路を中心点として所定の半径を有する円が属する図葉を決定する。このように決定された図葉は、図9にて灰色で示されている。このように、経路および前記円が通る図葉(図9にて灰色で示された図葉)と連関した地図データを移動通信端末機に送信する。本発明の更に他の実施例によると、前記実施例における円の代わりに、所定サイズの四角形または他の多角形を用いて遂行することもできる。このような図葉と連関した地図データを一度に送信したり、一部分を先に送信したりする方法は、図6と関連して説明された実施例と同様である。
【００５１】
図10は、本発明の更に他の一実施例であるバッファ・ポリゴン検索(buffer polygon search)によって得られた探索経路の周辺領域を示した図である。
【００５２】
バッファ・ポリゴン検索(buffer polygon search)は、探索された経路を中心としたバッファ・ポリゴン(buffer polygon)を決定する方法である。図10には、探索された経路(1001)を中心として決定されたバッファ・ポリゴン(1002)が示されている。従って、本実施例によると、経路探索によって決定された経路を中心として所定の幅を有するバッファ・ポリゴンを決定し、前記バッファ・ポリゴンが属する図葉(図10にて灰色で示された図葉)を決定する。その後、前記決定された図葉と連関した地図データを移動通信端末機に送信する。
【００５３】
一つの曲線または直線を中心にポリゴン・アウトライン(polygon outline)を生成する方法は、様々な方法を用いることができる。例えば、探索された経路を中心として所定の幅を有するバッファ・ポリゴンを決定することもある。また、いわゆる"Moving a Disk"と呼ばれるミンコフスキー和(Minkowski Sum)アルゴリズムは、経路に沿って円を移動させながら、その外郭線に沿ってポリゴンを生成する方法も用いられる。また、本記載によって、当業系において一つの曲線または直線を中心としてポリゴン・アウトライン(polygon outline)を生成する他の方法も本発明に用いることができる。
【００５４】
図11は、ヒルベルト曲線を説明するための図である。これは、下記図12と連関してヒルベルト値(Hibert Value)を用いた周辺領域(buffered area)の決定方法を説明するためのものである。ヒルベルト曲線は、本発明に属した技術分野において通常の技術を有する者に周知されているため、本発明においては、これに対して簡単に説明する。ヒルベルト曲線は、図11に示されたように、2次元空間上の客体を1次元空間上でマッピングする方法に関するものである。すなわち、2次元空間上の客体に0から始まって順次に隣接した客体に番号を付与する。図11に表示されたように、地図を構成する各図葉に対して図11と同じヒルベルト値を割り当てることができる。すなわち、一番左側の一番下側の図葉にヒルベルト値‘0’を割り当て、それと一番隣接していてまだヒルベルト値が割り当てられていない図葉にその次のヒルベルト値を割り当てる。このように、2x2の図葉に対してヒルベルト値を割り当てた例が図１１（ａ）、4x4の図葉に対してヒルベルト値を割り当てた例が図１１（ｂ）、8x8の図葉に対してヒルベルト値を割り当てた例が図１１（ｃ）に示されている。このように、ヒルベルト値を各図葉に割り当てておくと、特定のヒルベルト値を有する図葉と隣り合う図葉に関する情報を複雑な算術演算なく定数時間ですぐに求めることができる。
【００５５】
図12および図13は、本発明の更に他の一実施例によって経路およびヒルベルト曲線を用いて決定された経路の周辺領域を示した図である。
【００５６】
本実施例によると、地図情報データベースには、地図データと連関した図葉それぞれに対してヒルベルト値が割り当てられて維持される。各図葉にヒルベルト値を割り当てる方法は、図11に説明されたとおりである。移動通信端末機の経路探索要請に対して経路探索をし、前記経路が通る図葉をまず決定する。その後、前記経路が通る図葉が隣接した図葉をヒルベルト値を用いて決定する。一つの図葉のヒルベルト値が分かれば、それと隣り合う図葉のヒルベルト値は定数時間ですぐに計算が可能であるため、非常に迅速に経路が通る図葉および前記経路が通る図葉と隣り合う図葉を決定することができる。例えば、ヒルベルト値2を有する図葉と隣り合う図葉のヒルベルト値は、図11を参照すると、それぞれ0、1、3、4、7、8、13および14であることを知ることができる。
【００５７】
その後、このように決定された図葉と連関した地図データを移動通信端末機に送信する。本実施例によると、特定のヒルベルト値を有する図葉と隣り合う図葉に関する情報を複雑な算術演算なく定数時間ですぐに求めることができるため、経路周辺の地図データを定数時間の計算によってすぐに把握することができる。従って、大量の地図データの要請もサーバの過多な計算なく効率的にすぐに支援することができるようになる。
【００５８】
図12および図13の相違点は、経路が通る図葉と隣り合う図葉の概念が少し異なる。図12では所定の図葉と角を用いて連結した図葉を隣り合う図葉として把握し、図13では所定の図葉と角を用いて連結した図葉および前記所定の図葉と頂点を用いて連結した図葉も隣り合う図葉として把握する。例えば、図１１（ｂ）にて図12の実施例によると、ヒルベルト値2を有する図葉と隣り合う図葉のヒルベルト値は、それぞれ1、3、7、13であり、図13の実施例によると、それぞれ0、1、3、4、7、8、13および14である。本発明において"隣り合う図葉"は、前記2種類の場合を包括する意味として用いられる。
【００５９】
本発明の更に他の実施例によると、移動通信端末機はGPS受信機を用いて自分の現在位置を計算し、これに基づいてマップマッチング(map matching)を遂行する。この時、移動通信端末機は、自分の現在位置が探索された経路から離脱しているかを判断する。すなわち、自分の現在位置が探索された経路上に存在しなければ、経路を離脱したということになる。この場合、本発明の実施例によると、経路周辺の地図データもすでに移動通信端末機が受信して格納しているため、追加で地図データを要請しなくてもすぐに前記離脱した位置に対する地図をユーザに表示することができる。また、すでに前記周辺の地図データが移動通信端末機に格納されているが、前記ユーザが前記経路を更に離脱して他の所に進行するようになると、前記移動通信端末機が格納していない図葉の地図データが必要になることがある。従って、このような場合のため、移動通信端末機が経路を離脱した場合、地図情報提供サーバ(ナビゲーションサーバ)に移動通信端末機の現在位置と隣接した地域に対する地図データを要請する。そうすると、地図情報提供サーバは、経路から離脱した移動通信端末機の現在位置と隣接した地域の図葉と連関した地図データを移動通信端末機に送信する。
【００６０】
本発明の実施例は、多様なコンピュータで具現される動作を遂行するためのプログラム命令を含むコンピュータ読み取り可能媒体を含む。前記コンピュータ読み取り可能媒体は、プログラム命令、データファイル、データ構造などを単独または組み合わせて含むことができる。前記媒体は、プログラム命令は本発明のために特別に設計されて構成されたものであったり、コンピュータソフトウェア当業者に公知されて使用可能なものであったりする。コンピュータ読み取り可能記録媒体の例としては、ハードディスク、フロッピィーディスクおよび磁気テープのような磁気媒体(magnetic media)、CD-ROM、DVDのような光記録媒体(optical media)、フロプティカルディスク(floptical disk)のような磁気-光媒体(magneto-optical media)、およびROM、RAM、フラッシュメモリなどのようなプログラム命令を格納して遂行するように特別に構成されたハードウェア装置が含まれる。前記媒体は、プログラム命令、データ構造などを指定する信号を送信する搬送波を含む光または金属線、導波管などの送信媒体であったりする。プログラム命令の例としては、コンパイラによって生成されるものと同じ機械語コードだけでなく、インタプリタなどを用いてコンピュータによって実行される高級言語コードを含む。
【００６１】
以上のように、本発明は、限定された実施例と図面によって説明されたが、本発明は前記の実施例に限定されるものでなく、これは本発明が属する分野において通常の知識を有する者にとっては、このような記載から多様な修正および変形が可能である。よって、本発明思想は、添付の特許請求の範囲によってのみ把握されるべきであり、これの均等または等価的変形の全ては本発明思想の範囲に属するであろう。
【図面の簡単な説明】
【００６２】
【図１】本発明による地図情報提供サーバおよび移動通信端末機間の連結を示したブロック図である。
【図２】本発明によるナビゲーションサーバの内部構成を示したブロック図である。
【図３】本発明による地図情報提供方法の手順を示した流れ図である。
【図４】本発明の一実施例によって経路探索のための目的地を入力するユーザインターフェイスを示した図である。
【図５】本発明の一実施例によってナビゲーションサーバに経路探索を要請するユーザインターフェイスを示した図である。
【図６】本発明の一実施例によってナビゲーションサーバから受信した経路情報および地図情報に基づいて走行画面をユーザに提供するユーザインターフェイスを示した図である。
【図７】本発明の一実施例によってユーザ端末機に送信する地図データの図葉を示した図である。
【図８】本発明の一実施例によって探索された経路の周辺領域を示した図である。
【図９】本発明の一実施例によって決定された探索経路の周辺領域を示した図である。
【図１０】本発明の更に他の一実施例によって決定された探索経路の周辺領域を示した図である。
【図１１】ヒルベルト曲線を説明するための図である。
【図１２】本発明の更に他の一実施例によってヒルベルト曲線を用いて決定された経路の周辺領域を示した図である。
【図１３】本発明の更に他の一実施例によってヒルベルト曲線を用いて決定された経路の周辺領域を示した図である。
【技術分野】
【０００１】
本発明は、移動通信端末機に地図情報を提供する方法に関し、より詳しくは、前記移動通信端末機で表示される可能性が高い地図データのみを前記移動通信端末機に送信することによって、地図データ送信の効率性を高めた地図情報提供方法およびシステムに関する。
【背景技術】
【０００２】
最近、通信網を用いたサービスの提供によって携帯型コンピュータおよび移動電話などの無線通信環境内における情報検索の機会が増加している。これに伴い、ユーザは自由に移動しながら、いつどこででも必要な情報サービスを検索して提供を受けることが可能となった。
【０００３】
ナビゲーションシステム(Navigation System)は、人工衛星を用いて車両などの運送装置(vehicle)の走行のための情報を提供するシステムであって、自動航法システムとも言われる。このようなナビゲーションシステムは、GPS受信機を用いて地球上に浮かんでいるGPS(global positioning system)衛星から所定のデータを受信し、前記受信されたデータに基づいて自分の位置を計算する。地球上には多数のGPS衛星が浮かんでいるが、運送装置は地球上のどの地域にいたとしても3つのGPS衛星からGPS信号を受信することができ、前記3つのGPS衛星から受信されたGPS信号に基づいて自分の位置を計算することができるようになっている。ナビゲーションシステムは、このように計算された自分の位置情報に基づいて多様な走行情報を前記車両などの運送装置に提供する。このようなナビゲーションシステムは、既存では主に航空機や船舶などの大型移動体の位置計算と航法に用いられていたが、最近では自動車などにも広く用いられている。前記ナビゲーションシステムは、運送装置の現在の位置情報、運送装置の現在の位置から前記運送装置の目的地までの経路情報、前記位置情報および経路情報と関連した地図情報、交通状況情報など、非常に多様な情報をユーザに提供している。
【０００４】
このようなナビゲーション装置において、運送装置の現在位置などの情報をユーザに伝達する時に地図を用いると、ユーザがより簡単に前記現在位置などの情報を認識することができるため、地図情報が共に提供されるのが一般的である。
【０００５】
従来技術によると、このような地図情報は、CD-ROMまたはDVD-ROMのような格納媒体を介して提供されていた。このような従来技術によるナビゲーション装置は、必要な度にCD-ROMなどの格納媒体に格納された地図情報を読み取り、これを所定の表示手段に表示していた。しかし、このような従来技術のナビゲーション装置において、地図情報を更新しなければならない場合、CD-ROMなどの格納媒体を交換する必要があるため、その後のアップデート時に相当な不便があった。すなわち、ユーザは前記地図情報を含んだCD-ROMの提供者から継続してCD-ROMを追加購入しなければならないという経済的および時間的負担が発生していた。また、前記地図情報の提供者が変更される地図情報をリアルタイムで反映したCD-ROMなどを製作してユーザに提供することは不可能であるため、変更された地図情報(例えば、道路、建物などが新しく生じたり消滅した場合)をリアルタイムでユーザに提供することができなかった。
【０００６】
また、いわゆるテレマティックス(tele-matics)と呼ばれる更に他の従来技術によると、移動電話などの移動通信端末機を用いたナビゲーションサービスが提供されている。前記テレマティックスサービスは、ユーザに音声を用いて道を案内したり、自分の車が交通事故にあった場合、GPS衛星を用いて自動的に事故車の位置を追跡し、最も近くに位置する119救助隊や病院などに前記情報を伝達することによって救難活動を簡単にしている。しかし、従来技術による移動電話などを用いたナビゲーションサービスにおいては、移動電話のメモリサイズによる制限のため、地図情報を移動電話に格納しておくことができないという問題点があった。これにより、前記従来技術によると、車の位置情報、走行情報などをユーザに提供する時、地図を共にユーザに提供することができずに音声またはテキスト形態で提供していたため、ユーザが従来技術によるナビゲーションシステムを用いることに不便さが生じていた。
【０００７】
これにより、移動通信端末機に通信網を用いて地図情報を提供することによって、道路などの地図情報の変更をリアルタイムで反映することができるナビゲーションシステムが要求されている。
【０００８】
しかし、移動通信端末機のメモリは制限的であるため、無制限的な地図データを前記移動通信端末機に提供することはあまり効率的ではない。また、移動通信端末機のメモリ容量が拡大されたとしても、このような地図情報を移動通信網を用いて送信する場合においては、いかなる場合であってもデータ通信量を減らす必要がある。なぜなら、データ通信量が多くなると、個別ユーザの立場では通信サービス料金が過多し、サービス提供者の立場では不必要なトラフィックを多く処理するようになるため、通信の効率性を阻害するようになる。
【０００９】
従って、前記移動通信端末機に通信網を用いて地図データを提供することにおいて、表示される可能性が高い地図データのみを送信することによって、地図データ送信の効率性を図る必要性がある。また、このようにユーザの移動通信端末機で表示される可能性が高い地図データを効率的に検索する方法も必要である。しかし、従来技術においては、このような問題点が全く認識されていないだけでなく、この解決策をも全く提示していない。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、前記のような従来技術を改善するために案出されたものであり、移動通信端末機で表示される可能性が高い地図データのみを選択して前記移動通信端末機に送信することによって、地図データを効率的に送信する地図情報提供方法およびシステムを提供することを目的とする。
【００１１】
また、移動通信端末機に表示される可能性が高い地図データを効率的に決定することができる方法およびシステムを提供することを他の目的とする。
【００１２】
また、移動通信端末機が経路を離脱した場合でも、前記離脱した位置と連関した地図をすぐに表示することができる方法およびシステムを提供することを他の目的とする。
【００１３】
また、経路周辺の地図データをハードウェアに大きい負荷を与えずに迅速に検索して移動通信端末機に提供する方法およびシステムを提供することを他の目的とする。
【００１４】
また、移動通信端末機が経路を離脱した場合、地図情報提供サーバ(ナビゲーションサーバ)に移動通信端末機の現在位置と隣接した地域に対する地図データを要請し、これを受信可能にすることによって、経路が離脱した場合でも効率的に処理することができる方法およびシステムを提供することを他の目的とする。
【課題を解決するための手段】
【００１５】
上記の目的を達成し、従来技術の問題点を解決するために、本発明は、複数の地図データを含む地図情報データベースを維持する段階と、前記移動通信端末機から経路探索要求を受信する段階と、前記経路探索要求に応答し、経路探索を遂行して経路を決定する段階と、前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階とを含む地図情報提供方法を提供する。この時、前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階において、本発明によるナビゲーションサーバは、前記決定された経路および前記決定された経路から一定範囲内に属する地図データを前記移動通信端末機に送信することができる。
【００１６】
本発明の一態様によって移動通信端末機に地図情報を提供する方法は、複数の地図データを含む地図情報データベースを維持する段階(前記地図データに含まれる道路と連関した道路データは、通行料に関する情報を含む)と、前記移動通信端末機から経路探索要求を受信する段階と、前記経路探索要求に応答して検索された複数の経路のうち、前記複数の経路と連関した道路の通行料が最も少ない経路を決定する段階と、前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階とを含む。
【００１７】
本発明の更に他の一態様による移動通信端末機に地図情報を提供する地図情報提供システムは、複数の地図データを格納する地図情報データベース(前記地図データのそれぞれは、図葉と連関する)と、前記移動通信端末機から経路探索要求を受信する受信部と、前記経路探索要求に応答し、経路探索を遂行して経路を決定する経路探索部と、前記決定された経路と連関した地図データを前記地図情報データベースから検索する地図データ検索部と、前記検索された地図データを前記移動通信端末機に送信する送信部とを含む。
【発明の効果】
【００１８】
以上の説明から知ることができるように、本発明によると、移動通信端末機で表示される可能性が高い地図データのみを選択して前記移動通信端末機に送信することによって、地図データを効率的に送信する地図情報提供方法およびシステムが提供される。
【００１９】
また、本発明によると、移動通信端末機に表示される可能性が高い地図データを効率的に決定することができ、移動通信端末機が経路を離脱した場合でも、前記離脱した位置と連関した地図をすぐに表示することができる。
【００２０】
また、本発明によると、経路周辺の地図データをハードウェアに大きい負荷を与えず、迅速に検索して移動通信端末機に提供することができる。
【００２１】
また、本発明によると、移動通信端末機が経路を離脱した場合、地図情報提供サーバ(ナビゲーションサーバ)に移動通信端末機の現在位置と隣接した地域に対する地図データを要請し、これを受信できるようにすることによって、経路が離脱した場合にも効率的に処理することができる。
【発明を実施するための最良の形態】
【００２２】
以下、添付された図面を参照して、本発明の実施例を詳しく説明する。
【００２３】
図1は本発明による地図情報提供サーバおよび移動通信端末機間の連結を示したブロック図である。
【００２４】
移動通信端末機(101、102)は携帯電話に限定されず、通信機能が支援される移動性のあるユーザ端末機を意味する。本発明の好ましい実施例において、移動通信端末機(101、102)は携帯電話端末機である。移動通信端末機(101、102)は、移動通信網(103)を介して本発明によるナビゲーションサーバ(104)に接続する。ナビゲーションサーバは、移動通信端末機(101、102)からのナビゲーションと関連したユーザ要請を受信してこれを処理する。ナビゲーションサーバ(104)は、地図情報を含む地図情報データベース(105)と連結する。地図情報データベースは、ナビゲーションサーバ(104)内に含まれて構成されることもある。移動通信端末機(101、102)は、自分の現在位置を確認するためにGPS受信機を内蔵したり、GPS受信機(未図示)と連結したりする。
【００２５】
図2は、本発明によるナビゲーションサーバの内部構成を示したブロック図である。
【００２６】
ナビゲーションサーバ(navigation server)(200)は、受信部(201)、経路探索部(202)、地図データ検索部(203)および送信部(204)を含む。
【００２７】
受信部(201)は、移動通信端末機からの経路探索要求など、ナビゲーションと関連した様々なユーザ要求を受信する。
【００２８】
経路探索部(202)は、ユーザの経路探索要求に応答して経路探索を遂行する。経路探索の方法は、最短経路(Shortest Path)検索、最適経路検索、無料道路優先経路検索などの方法が用いられる。最短経路検索は、出発地から目的地までの複数の経路のうち、出発地から目的地までの距離が最も短い経路を選択してユーザに提供する方法である。最適経路検索は、出発地から目的地までの複数の経路のうち、出発地から目的地までかかる予想時間が最も少ない経路を選択してユーザに提供する方法である。最適経路を検索するためには、各道路当りの平均時速のような速度情報、または現在の渋滞情報などのような交通情報などを参照する。無料道路優先経路検索は、出発地から目的地までの複数の経路のうち、各経路を通過するのに必要な通行料などの費用情報を参照し、このような費用が最も少なく発生する経路を選択してユーザに提供する方法である。このため、地図情報データベース(205)の地図データに含まれる道路と連関した道路データは、通行料などの費用に関する情報を含む。
【００２９】
地図データ検索部(203)は、経路探索部(202)で決定された経路と連関した地図データを地図情報データベース(205)から検索する。このように検索された地図データは送信部(204)に伝達され、送信部(204)は前記検索された地図データを移動通信端末機に経路探索情報と共に送信する。
【００３０】
ユーザが所定の出発地から目的地までの経路探索を要請したとすると、前記ユーザは、前記出発地から前記目的地まで前記経路に沿って走行する可能性が高い。従って、前記経路による地図データ(または前記経路および前記経路の周辺に対する地図情報)を前記ユーザ端末機に提供することによって、ユーザ端末機で表示される可能性が高いデータのみを送信することができるようになる。前記経路と関連したデータは、全体データと比較すると非常に小さい量のデータであるため、全体地図データを送信する場合と比較して見ると、本発明がいかに効率的であるかを知ることができる。
【００３１】
図3は、本発明による地図情報提供方法の手順を示した流れ図である。
【００３２】
段階(301)で、ナビゲーションサーバは、複数の地図データを含む地図情報データベースを維持する。地図情報データベースは、ナビゲーションサーバと物理的に独立して存在したり、物理的にナビゲーションサーバに含まれたりする。
【００３３】
段階(302)で、ナビゲーションサーバは、ユーザ端末機(ユーザの移動通信端末機)から経路探索要求を受信する。前記経路探索要求は、出発地および目的地に関する情報を含む。または、出発地が前記ユーザ端末機の現在位置であり、前記現在位置がすでにナビゲーションサーバに格納されていると、ユーザ端末機は、目的地に関する情報のみをナビゲーションサーバに送信して経路探索を要請することもある。
【００３４】
ユーザ端末機で経路を探索するための目的地を入力する画面の例が図4に示されている。図４（ａ）で、ユーザは、ユーザ端末機のナビゲーション関連メニューのうち、“2．目的地設定”を選択する。そうすると、図４（ｂ）で目的地設定のための多様な方法が提示される。“1．名称検索”は、目的地の名称を用いて検索する方法であり、"2．住所検索"は、目的地の住所を用いて検索する方法である。"3．住所録検索"は、ユーザがすでに住所録に登録している目的地に関する情報を用いて目的地を検索する方法であり、"4．電話番号簿検索"は、電話番号を用いて目的地を検索する方法である。
【００３５】
図４（ｂ）では名称を用いた検索を選択し、この場合、ユーザ端末機は、ユーザに名称の入力を要請する画面を表示する(未図示)。図４（ｃ）は、ユーザが前記名称として"ギャラリア"と入力した場合の出力画面である。ユーザ端末機は"ギャラリア"を含んだ様々な目的地候補のリストを表示する。このような目的地検索は、ユーザ端末機において目的地検索と関連した情報を全て含んでユーザ端末機が単独で遂行することもできるし、ナビゲーションサーバで必要な情報を格納し、前記ナビゲーションサーバとの通信を介して遂行することもできる。
【００３６】
図5は、ナビゲーションサーバに経路探索を要請するユーザインターフェイスを示した図である。出発地と目的地の設定が終わった後、ユーザは図５（ａ）で"走行経路設定"を選択して経路探索を要請する。この時、経路探索の方法が様々である場合、図５（ｂ）のように、経路探索の方法の中でどのような方法を用いるかをユーザに質疑する。図５（ｂ）は、ユーザが"最適経路"による経路探索を選択した画面である。このように、ユーザが経路探索を要請すると、このような経路探索要請はナビゲーションサーバに伝達される。
【００３７】
段階(303)で、ナビゲーションサーバは、ユーザの経路探索要求に応答して経路探索を遂行する。経路探索は、出発地から目的地までの一つ以上の候補経路のうち、一つを選択する。前記で説明したように、前記選択の方法としては、出発地から目的地までの距離が最も短い経路を選択する最短経路検索、出発地から目的地までかかる予想時間が最も少ない経路を選択する最適経路検索がある。また、本発明においては、地図情報データベース(205)の地図データに含まれる道路と連関した道路データは、通行料などの費用に関する情報を含み、出発地から目的地までの複数の経路のうち、各経路を通過するのに必要な通行料などの費用情報を参照し、このような費用が最も少なく発生する経路を選択する無料道路優先経路検索を支援する。
【００３８】
段階(304)では、段階(303)で決定された経路と連関した地図データを地図情報データベースを参照して検索する。経路探索の結果、決定された経路と連関した地図データを決定する方法に関しては、図7以下において詳しく説明する。
【００３９】
段階(305)では、前記検索された地図データを前記決定された経路情報と共に移動通信端末機に送信する。そうすると、移動通信端末機は、受信した経路情報および地図データに基づき、ユーザの走行情報を地図画面を用いて移動通信端末機のディスプレイに表示する。
【００４０】
図6は、本発明の一実施例によってナビゲーションサーバから受信した経路情報および地図情報に基づき、走行画面をユーザに提供するユーザインターフェイスを示した図である。
【００４１】
図６（ａ）で、ユーザが"走行スタート"を選択すると、図６（ｂ）のような経路探索情報がユーザに提供される。ユーザが図６（ｂ）で"走行スタート"を選択すると、図６（ｃ）に示されたように、ユーザの走行と関連した情報が受信された地図データを用いてユーザ端末機のディスプレイに表示される。
【００４２】
図7は、本発明の一実施例によってナビゲーションサーバにおける経路探索の結果、決定された経路が通る図葉の地図データを表示したものである。
【００４３】
全体地図データを一定サイズの複数の区域(セル)に区分して管理するのが地図データ管理上において便利であるため、図7に示されたように、全体地図データを複数のセルに分割する。この時、分割された一つのセルを図葉(701)と言う。図面符号(702)は、経路探索の結果、決定された経路を示したものである。前記で説明したように、経路と関連した地図データはユーザによって用いられる可能性が高いため、前記経路が通る図葉(図7にて灰色で表示された図葉)に該当する地図データをユーザ端末機に送信する地図データとして決定する。
【００４４】
ナビゲーションサーバは、上記のように決定された地図データをユーザの移動通信端末機に送信する。この時、本発明の一実施例によると、決定された経路が通る複数の図葉の全てと連関した地図データを一度に移動通信端末機に送信する。本実施例によると、経路と関連した全ての地図データを一度に移動通信端末機が受信するため、前記経路の進行中、移動通信端末機が追加で地図データを受信する必要がないという長所がある。
【００４５】
本発明の更に他の実施例によると、前記決定された経路が通る複数の図葉のうち、一部の図葉と連関した地図データをユーザの移動通信端末機に送信する。例えば、図7において灰色で表示された図葉のうち、出発地が含まれた図葉と連関した地図データをユーザの移動通信端末機に送信し、灰色で表示された残りの図葉と連関した地図データは、前記移動通信端末機の経路の進行に従って前記移動通信端末機に送信する。経路と関連した全体図葉と連関した地図データを一度に送信しようとすると時間が多く要されるが、一部の図葉と連関した地図データの送信は要される時間が相対的に少ない。従って、本実施例によると、移動通信端末機が優先的に必要とする少ない量の地図データを移動通信端末機に送信するため、短時間内に移動通信端末機で経路と関連した地図を表示することができるという長所がある。
【００４６】
本発明の一実施例によると、前記のように一部の図葉と連関した地図データを先に送信した後、前記移動通信端末機の経路進行に従って必要な図葉を予測し、適切な時点に必要な図葉と連関した地図データを送信する。例えば、図葉(703)と連関した地図データを送信した後、移動通信端末機が走行をして図葉(703)の地図領域を過ぎ、所定時間以内に図葉(704)の地域に移動することが予測される場合、図葉(704)を移動通信端末機に送信する。本実施例は、図8以下の他の実施例にも適用される。
【００４７】
本発明の更に他の実施例によると、一部の図葉を送信した後、移動通信端末機が地図を表示している間、バックグラウンド(background)で経路が通る残りの図葉と連関した地図データを移動通信端末機に送信する。本実施例は、図8以下の他の実施例にも適用される。
【００４８】
図8は、本発明の一実施例によって探索された経路の周辺領域を示した図である。
【００４９】
図7と関連した実施例においては、経路探索の結果から得られた経路が通る図葉と連関した地図データを移動通信端末機に送信するが、以下の実施例においては、経路探索の結果、決定された経路(801)および前記探索された経路から一定範囲内(802)に該当する地図データを移動通信端末機に送信する。本実施例によると、移動通信端末機が装着された車両などが前記経路探索された経路以外の経路で走行する場合でも、移動通信端末機がすでに経路周辺の地図データをダウンロードしているため、追加の地図データをダウンロードしなくてもすぐに現在の走行地点と関連した地図を移動通信端末機が表示することができる。また、探索された経路および探索された経路の周辺領域(buffered area)に関する地図データのみを送信するため、全体地図データを送信する場合に比べてデータ送信量が革新的に減少する。特にメモリサイズが大きくない携帯電話などに地図データを用いたナビゲーションサービスを提供するためには、このようにデータ送信量を革新的に減少させる方法が非常に重要である。このような周辺領域(buffered area)を決定する方法をバッファ検索(buffered search)と呼び、これと関連した詳細な実施例を図9以下で詳しく説明する。本発明においてバッファ検索とは、探索された経路周辺の客体を検索することを意味する。
【００５０】
図9は、本発明の一実施例によって決定された探索経路の周辺領域を示した図である。図9の実施例においては、経路探索の結果、決定された経路(901)を中心点として所定の半径を有する円(902)を決定する。その後、前記円の外郭線を全て含む領域(903)が本実施例で決定した周辺領域(buffered area)となる。本実施例においては、前記決定された周辺領域が属する図葉を決定する。すなわち、前記決定された経路を中心点として所定の半径を有する円が属する図葉を決定する。このように決定された図葉は、図9にて灰色で示されている。このように、経路および前記円が通る図葉(図9にて灰色で示された図葉)と連関した地図データを移動通信端末機に送信する。本発明の更に他の実施例によると、前記実施例における円の代わりに、所定サイズの四角形または他の多角形を用いて遂行することもできる。このような図葉と連関した地図データを一度に送信したり、一部分を先に送信したりする方法は、図6と関連して説明された実施例と同様である。
【００５１】
図10は、本発明の更に他の一実施例であるバッファ・ポリゴン検索(buffer polygon search)によって得られた探索経路の周辺領域を示した図である。
【００５２】
バッファ・ポリゴン検索(buffer polygon search)は、探索された経路を中心としたバッファ・ポリゴン(buffer polygon)を決定する方法である。図10には、探索された経路(1001)を中心として決定されたバッファ・ポリゴン(1002)が示されている。従って、本実施例によると、経路探索によって決定された経路を中心として所定の幅を有するバッファ・ポリゴンを決定し、前記バッファ・ポリゴンが属する図葉(図10にて灰色で示された図葉)を決定する。その後、前記決定された図葉と連関した地図データを移動通信端末機に送信する。
【００５３】
一つの曲線または直線を中心にポリゴン・アウトライン(polygon outline)を生成する方法は、様々な方法を用いることができる。例えば、探索された経路を中心として所定の幅を有するバッファ・ポリゴンを決定することもある。また、いわゆる"Moving a Disk"と呼ばれるミンコフスキー和(Minkowski Sum)アルゴリズムは、経路に沿って円を移動させながら、その外郭線に沿ってポリゴンを生成する方法も用いられる。また、本記載によって、当業系において一つの曲線または直線を中心としてポリゴン・アウトライン(polygon outline)を生成する他の方法も本発明に用いることができる。
【００５４】
図11は、ヒルベルト曲線を説明するための図である。これは、下記図12と連関してヒルベルト値(Hibert Value)を用いた周辺領域(buffered area)の決定方法を説明するためのものである。ヒルベルト曲線は、本発明に属した技術分野において通常の技術を有する者に周知されているため、本発明においては、これに対して簡単に説明する。ヒルベルト曲線は、図11に示されたように、2次元空間上の客体を1次元空間上でマッピングする方法に関するものである。すなわち、2次元空間上の客体に0から始まって順次に隣接した客体に番号を付与する。図11に表示されたように、地図を構成する各図葉に対して図11と同じヒルベルト値を割り当てることができる。すなわち、一番左側の一番下側の図葉にヒルベルト値‘0’を割り当て、それと一番隣接していてまだヒルベルト値が割り当てられていない図葉にその次のヒルベルト値を割り当てる。このように、2x2の図葉に対してヒルベルト値を割り当てた例が図１１（ａ）、4x4の図葉に対してヒルベルト値を割り当てた例が図１１（ｂ）、8x8の図葉に対してヒルベルト値を割り当てた例が図１１（ｃ）に示されている。このように、ヒルベルト値を各図葉に割り当てておくと、特定のヒルベルト値を有する図葉と隣り合う図葉に関する情報を複雑な算術演算なく定数時間ですぐに求めることができる。
【００５５】
図12および図13は、本発明の更に他の一実施例によって経路およびヒルベルト曲線を用いて決定された経路の周辺領域を示した図である。
【００５６】
本実施例によると、地図情報データベースには、地図データと連関した図葉それぞれに対してヒルベルト値が割り当てられて維持される。各図葉にヒルベルト値を割り当てる方法は、図11に説明されたとおりである。移動通信端末機の経路探索要請に対して経路探索をし、前記経路が通る図葉をまず決定する。その後、前記経路が通る図葉が隣接した図葉をヒルベルト値を用いて決定する。一つの図葉のヒルベルト値が分かれば、それと隣り合う図葉のヒルベルト値は定数時間ですぐに計算が可能であるため、非常に迅速に経路が通る図葉および前記経路が通る図葉と隣り合う図葉を決定することができる。例えば、ヒルベルト値2を有する図葉と隣り合う図葉のヒルベルト値は、図11を参照すると、それぞれ0、1、3、4、7、8、13および14であることを知ることができる。
【００５７】
その後、このように決定された図葉と連関した地図データを移動通信端末機に送信する。本実施例によると、特定のヒルベルト値を有する図葉と隣り合う図葉に関する情報を複雑な算術演算なく定数時間ですぐに求めることができるため、経路周辺の地図データを定数時間の計算によってすぐに把握することができる。従って、大量の地図データの要請もサーバの過多な計算なく効率的にすぐに支援することができるようになる。
【００５８】
図12および図13の相違点は、経路が通る図葉と隣り合う図葉の概念が少し異なる。図12では所定の図葉と角を用いて連結した図葉を隣り合う図葉として把握し、図13では所定の図葉と角を用いて連結した図葉および前記所定の図葉と頂点を用いて連結した図葉も隣り合う図葉として把握する。例えば、図１１（ｂ）にて図12の実施例によると、ヒルベルト値2を有する図葉と隣り合う図葉のヒルベルト値は、それぞれ1、3、7、13であり、図13の実施例によると、それぞれ0、1、3、4、7、8、13および14である。本発明において"隣り合う図葉"は、前記2種類の場合を包括する意味として用いられる。
【００５９】
本発明の更に他の実施例によると、移動通信端末機はGPS受信機を用いて自分の現在位置を計算し、これに基づいてマップマッチング(map matching)を遂行する。この時、移動通信端末機は、自分の現在位置が探索された経路から離脱しているかを判断する。すなわち、自分の現在位置が探索された経路上に存在しなければ、経路を離脱したということになる。この場合、本発明の実施例によると、経路周辺の地図データもすでに移動通信端末機が受信して格納しているため、追加で地図データを要請しなくてもすぐに前記離脱した位置に対する地図をユーザに表示することができる。また、すでに前記周辺の地図データが移動通信端末機に格納されているが、前記ユーザが前記経路を更に離脱して他の所に進行するようになると、前記移動通信端末機が格納していない図葉の地図データが必要になることがある。従って、このような場合のため、移動通信端末機が経路を離脱した場合、地図情報提供サーバ(ナビゲーションサーバ)に移動通信端末機の現在位置と隣接した地域に対する地図データを要請する。そうすると、地図情報提供サーバは、経路から離脱した移動通信端末機の現在位置と隣接した地域の図葉と連関した地図データを移動通信端末機に送信する。
【００６０】
本発明の実施例は、多様なコンピュータで具現される動作を遂行するためのプログラム命令を含むコンピュータ読み取り可能媒体を含む。前記コンピュータ読み取り可能媒体は、プログラム命令、データファイル、データ構造などを単独または組み合わせて含むことができる。前記媒体は、プログラム命令は本発明のために特別に設計されて構成されたものであったり、コンピュータソフトウェア当業者に公知されて使用可能なものであったりする。コンピュータ読み取り可能記録媒体の例としては、ハードディスク、フロッピィーディスクおよび磁気テープのような磁気媒体(magnetic media)、CD-ROM、DVDのような光記録媒体(optical media)、フロプティカルディスク(floptical disk)のような磁気-光媒体(magneto-optical media)、およびROM、RAM、フラッシュメモリなどのようなプログラム命令を格納して遂行するように特別に構成されたハードウェア装置が含まれる。前記媒体は、プログラム命令、データ構造などを指定する信号を送信する搬送波を含む光または金属線、導波管などの送信媒体であったりする。プログラム命令の例としては、コンパイラによって生成されるものと同じ機械語コードだけでなく、インタプリタなどを用いてコンピュータによって実行される高級言語コードを含む。
【００６１】
以上のように、本発明は、限定された実施例と図面によって説明されたが、本発明は前記の実施例に限定されるものでなく、これは本発明が属する分野において通常の知識を有する者にとっては、このような記載から多様な修正および変形が可能である。よって、本発明思想は、添付の特許請求の範囲によってのみ把握されるべきであり、これの均等または等価的変形の全ては本発明思想の範囲に属するであろう。
【図面の簡単な説明】
【００６２】
【図１】本発明による地図情報提供サーバおよび移動通信端末機間の連結を示したブロック図である。
【図２】本発明によるナビゲーションサーバの内部構成を示したブロック図である。
【図３】本発明による地図情報提供方法の手順を示した流れ図である。
【図４】本発明の一実施例によって経路探索のための目的地を入力するユーザインターフェイスを示した図である。
【図５】本発明の一実施例によってナビゲーションサーバに経路探索を要請するユーザインターフェイスを示した図である。
【図６】本発明の一実施例によってナビゲーションサーバから受信した経路情報および地図情報に基づいて走行画面をユーザに提供するユーザインターフェイスを示した図である。
【図７】本発明の一実施例によってユーザ端末機に送信する地図データの図葉を示した図である。
【図８】本発明の一実施例によって探索された経路の周辺領域を示した図である。
【図９】本発明の一実施例によって決定された探索経路の周辺領域を示した図である。
【図１０】本発明の更に他の一実施例によって決定された探索経路の周辺領域を示した図である。
【図１１】ヒルベルト曲線を説明するための図である。
【図１２】本発明の更に他の一実施例によってヒルベルト曲線を用いて決定された経路の周辺領域を示した図である。
【図１３】本発明の更に他の一実施例によってヒルベルト曲線を用いて決定された経路の周辺領域を示した図である。
【特許請求の範囲】
【請求項１】
移動通信端末機に地図情報を提供する方法において、
複数の地図データを含む地図情報データベースを維持する段階と、
前記移動通信端末機から経路探索要求を受信する段階と、
前記経路探索要求に応答し、経路探索を遂行して経路を決定する段階と、
前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階と、
を含むことを特徴とする地図情報提供方法。
【請求項２】
前記地図データのそれぞれは図葉と連関し、
前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階は、
前記決定された経路が通る図葉と連関した地図データを前記移動通信端末機に送信する段階を含む、
ことを特徴とする請求項1に記載の地図情報提供方法。
【請求項３】
前記決定された経路が通る図葉と連関した地図データを前記移動通信端末機に送信する段階は、
前記決定された経路が通る複数の図葉のうち、一部の図葉と連関した地図データを前記移動通信端末機に送信する段階を含む、
ことを特徴とする請求項2に記載の地図情報提供方法。
【請求項４】
前記複数の図葉のうち、一部の図葉と連関した前記地図データを前記移動通信端末機に送信した後、バックグラウンドで前記複数の図葉のうちの残りの図葉と連関した地図データを前記移動通信端末機に送信する段階を更に含むことを特徴とする請求項3に記載の地図情報提供方法。
【請求項５】
前記決定された経路が通る図葉と連関した地図データを前記移動通信端末機に送信する段階は、
前記決定された経路が通る複数の図葉全てと連関した地図データを前記移動通信端末機に送信する段階を含む、
ことを特徴とする請求項2に記載の地図情報提供方法。
【請求項６】
前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階は、
前記決定された経路および前記決定された経路から一定範囲内に属する地図データを前記移動通信端末機に送信する段階を含む、
ことを特徴とする請求項1に記載の地図情報提供方法。
【請求項７】
前記地図データのそれぞれは図葉と連関し、
前記決定された経路および前記決定された経路から一定範囲内に属する地図データを前記移動通信端末機に送信する段階は、
前記決定された経路が通る第1図葉を決定する段階と、
前記決定された経路を中心として所定の半径を有する円に含まれる範囲を決定する段階と、
前記円が属した第2図葉を決定する段階と、
前記第1図葉および前記第2図葉と連関した地図データを前記移動通信端末機に送信する段階と、
を含む、
ことを特徴とする請求項6に記載の地図情報提供方法。
【請求項８】
前記地図データのそれぞれは図葉と連関し、
前記決定された経路および前記決定された経路から一定範囲内に属する地図データを前記移動通信端末機に送信する段階は、
前記決定された経路を中心としてバッファ・ポリゴンを決定する段階と、
前記バッファ・ポリゴンが属した図葉を決定する段階と、
前記決定された図葉と連関した地図データを前記移動通信端末機に送信する段階と、
を含む、
ことを特徴とする請求項6に記載の地図情報提供方法。
【請求項９】
前記地図データと連関した図葉それぞれに対してヒルベルト値を維持する段階(前記地図データのそれぞれは、図葉と連関する)を更に含み、
前記決定された経路および前記決定された経路から一定範囲内に属する地図データを前記移動通信端末機に送信する段階は、
前記決定された経路が通る第1図葉を決定する段階と、
前記ヒルベルト値を用いて前記第1図葉と隣り合う第2図葉を決定する段階と、
前記第1図葉および前記第2図葉と連関した地図データを前記移動通信端末機に送信する段階と、
を含む、
ことを特徴とする請求項6に記載の地図情報提供方法。
【請求項１０】
前記決定された経路および前記決定された経路から一定範囲内に属する地図データを前記移動通信端末機に送信する段階は、
前記決定された経路および前記決定された経路から一定範囲が通る複数の図葉のうち、一部の図葉と連関した地図データを前記移動通信端末機に送信する段階を含む、
ことを特徴とする請求項6に記載の地図情報提供方法。
【請求項１１】
前記移動通信端末機が経路を離脱したかを判断する段階と、
前記移動通信端末機が経路を離脱した場合、前記地図情報データベースを維持する地図提供サーバに前記移動通信端末機の現在位置と隣接した地域に対する地図データを要請する段階と、
を更に含むことを特徴とする請求項1に記載の地図情報提供方法。
【請求項１２】
移動通信端末機に地図情報を提供する方法において、
複数の地図データを含む地図情報データベースを維持する段階(前記地図データに含まれる道路と連関した道路データは、通行料に関する情報を含む)と、
前記移動通信端末機から経路探索要求を受信する段階と、
前記経路探索要求に応答して検索された複数の経路のうち、前記複数の経路と連関した道路の通行料が最も少ない経路を決定する段階と、
前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階と、
を含むことを特徴とする地図情報提供方法。
【請求項１３】
請求項1ないし12のいずれか一つによる方法をコンピュータで具現するプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１４】
移動通信端末機に地図情報を提供する地図情報提供システムにおいて、
複数の地図データを格納する地図情報データベース(前記地図データのそれぞれは、図葉と連関する)と、
前記移動通信端末機から経路探索要求を受信する受信部と、
前記経路探索要求に応答し、経路探索を遂行して経路を決定する経路探索部と、
前記決定された経路と連関した地図データを前記地図情報データベースから検索する地図データ検索部と、
前記検索された地図データを前記移動通信端末機に送信する送信部と、
を含むことを特徴とする地図情報提供システム。
【請求項１５】
前記地図データ検索部は、
前記決定された経路および前記決定された経路から一定範囲内に属する地図データを検索する、
ことを特徴とする請求項14に記載の地図情報提供システム。
【請求項１】
移動通信端末機に地図情報を提供する方法において、
複数の地図データを含む地図情報データベースを維持する段階と、
前記移動通信端末機から経路探索要求を受信する段階と、
前記経路探索要求に応答し、経路探索を遂行して経路を決定する段階と、
前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階と、
を含むことを特徴とする地図情報提供方法。
【請求項２】
前記地図データのそれぞれは図葉と連関し、
前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階は、
前記決定された経路が通る図葉と連関した地図データを前記移動通信端末機に送信する段階を含む、
ことを特徴とする請求項1に記載の地図情報提供方法。
【請求項３】
前記決定された経路が通る図葉と連関した地図データを前記移動通信端末機に送信する段階は、
前記決定された経路が通る複数の図葉のうち、一部の図葉と連関した地図データを前記移動通信端末機に送信する段階を含む、
ことを特徴とする請求項2に記載の地図情報提供方法。
【請求項４】
前記複数の図葉のうち、一部の図葉と連関した前記地図データを前記移動通信端末機に送信した後、バックグラウンドで前記複数の図葉のうちの残りの図葉と連関した地図データを前記移動通信端末機に送信する段階を更に含むことを特徴とする請求項3に記載の地図情報提供方法。
【請求項５】
前記決定された経路が通る図葉と連関した地図データを前記移動通信端末機に送信する段階は、
前記決定された経路が通る複数の図葉全てと連関した地図データを前記移動通信端末機に送信する段階を含む、
ことを特徴とする請求項2に記載の地図情報提供方法。
【請求項６】
前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階は、
前記決定された経路および前記決定された経路から一定範囲内に属する地図データを前記移動通信端末機に送信する段階を含む、
ことを特徴とする請求項1に記載の地図情報提供方法。
【請求項７】
前記地図データのそれぞれは図葉と連関し、
前記決定された経路および前記決定された経路から一定範囲内に属する地図データを前記移動通信端末機に送信する段階は、
前記決定された経路が通る第1図葉を決定する段階と、
前記決定された経路を中心として所定の半径を有する円に含まれる範囲を決定する段階と、
前記円が属した第2図葉を決定する段階と、
前記第1図葉および前記第2図葉と連関した地図データを前記移動通信端末機に送信する段階と、
を含む、
ことを特徴とする請求項6に記載の地図情報提供方法。
【請求項８】
前記地図データのそれぞれは図葉と連関し、
前記決定された経路および前記決定された経路から一定範囲内に属する地図データを前記移動通信端末機に送信する段階は、
前記決定された経路を中心としてバッファ・ポリゴンを決定する段階と、
前記バッファ・ポリゴンが属した図葉を決定する段階と、
前記決定された図葉と連関した地図データを前記移動通信端末機に送信する段階と、
を含む、
ことを特徴とする請求項6に記載の地図情報提供方法。
【請求項９】
前記地図データと連関した図葉それぞれに対してヒルベルト値を維持する段階(前記地図データのそれぞれは、図葉と連関する)を更に含み、
前記決定された経路および前記決定された経路から一定範囲内に属する地図データを前記移動通信端末機に送信する段階は、
前記決定された経路が通る第1図葉を決定する段階と、
前記ヒルベルト値を用いて前記第1図葉と隣り合う第2図葉を決定する段階と、
前記第1図葉および前記第2図葉と連関した地図データを前記移動通信端末機に送信する段階と、
を含む、
ことを特徴とする請求項6に記載の地図情報提供方法。
【請求項１０】
前記決定された経路および前記決定された経路から一定範囲内に属する地図データを前記移動通信端末機に送信する段階は、
前記決定された経路および前記決定された経路から一定範囲が通る複数の図葉のうち、一部の図葉と連関した地図データを前記移動通信端末機に送信する段階を含む、
ことを特徴とする請求項6に記載の地図情報提供方法。
【請求項１１】
前記移動通信端末機が経路を離脱したかを判断する段階と、
前記移動通信端末機が経路を離脱した場合、前記地図情報データベースを維持する地図提供サーバに前記移動通信端末機の現在位置と隣接した地域に対する地図データを要請する段階と、
を更に含むことを特徴とする請求項1に記載の地図情報提供方法。
【請求項１２】
移動通信端末機に地図情報を提供する方法において、
複数の地図データを含む地図情報データベースを維持する段階(前記地図データに含まれる道路と連関した道路データは、通行料に関する情報を含む)と、
前記移動通信端末機から経路探索要求を受信する段階と、
前記経路探索要求に応答して検索された複数の経路のうち、前記複数の経路と連関した道路の通行料が最も少ない経路を決定する段階と、
前記決定された経路と連関した地図データを前記移動通信端末機に送信する段階と、
を含むことを特徴とする地図情報提供方法。
【請求項１３】
請求項1ないし12のいずれか一つによる方法をコンピュータで具現するプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１４】
移動通信端末機に地図情報を提供する地図情報提供システムにおいて、
複数の地図データを格納する地図情報データベース(前記地図データのそれぞれは、図葉と連関する)と、
前記移動通信端末機から経路探索要求を受信する受信部と、
前記経路探索要求に応答し、経路探索を遂行して経路を決定する経路探索部と、
前記決定された経路と連関した地図データを前記地図情報データベースから検索する地図データ検索部と、
前記検索された地図データを前記移動通信端末機に送信する送信部と、
を含むことを特徴とする地図情報提供システム。
【請求項１５】
前記地図データ検索部は、
前記決定された経路および前記決定された経路から一定範囲内に属する地図データを検索する、
ことを特徴とする請求項14に記載の地図情報提供システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公表番号】特表２００６−５２７５０６（Ｐ２００６−５２７５０６Ａ）
【公表日】平成１８年１１月３０日（２００６．１１．３０）
【国際特許分類】
【出願番号】特願２００５−５００５８６（Ｐ２００５−５００５８６）
【出願日】平成１５年１０月２２日（２００３．１０．２２）
【国際出願番号】ＰＣＴ／ＫＲ２００３／００２２２０
【国際公開番号】ＷＯ２００４／１１００８４
【国際公開日】平成１６年１２月１６日（２００４．１２．１６）
【出願人】（５０５３５４１５４）シンクウェア システムズ コーポレーション (11)
【Ｆターム（参考）】
【公表日】平成１８年１１月３０日（２００６．１１．３０）
【国際特許分類】
【出願日】平成１５年１０月２２日（２００３．１０．２２）
【国際出願番号】ＰＣＴ／ＫＲ２００３／００２２２０
【国際公開番号】ＷＯ２００４／１１００８４
【国際公開日】平成１６年１２月１６日（２００４．１２．１６）
【出願人】（５０５３５４１５４）シンクウェア システムズ コーポレーション (11)
【Ｆターム（参考）】
[ Back to top ]