(57)【要約】  地図データおよび道路周辺データを記憶する地図データ記憶部５と、目的地が設定された場合に、地図データ記憶部５に記憶された地図データを用いて現在地から目的地に至る経路を設定する経路設定部１と、設定された経路の周辺データの検索が指示された場合に、経路を構成する経路ノード間を所定の距離に分割した地点に補間点を設け、経路ノードおよび補間点を基準とした矩形領域をデータ抽出領域に特定するエリア特定部３１を備えた。
2012090240.tif 000002
【特許請求の範囲】
【請求項１】
地図データおよび道路周辺データを記憶する記憶部と、
目的地が設定された場合に、前記記憶部に記憶された前記地図データを用いて現在地から前記目的地に至る経路を設定する経路設定部と、
前記経路設定部が設定した経路の周辺データの検索が指示された場合に、前記経路を構成する経路ノード間を所定の距離に分割した地点に補間点を設け、前記経路ノードおよび前記補間点を基準とした矩形領域をデータ抽出領域に特定するエリア特定部とを備えた情報抽出装置。
【請求項２】
前記記憶部に記憶された道路周辺データをＸ座標およびＹ座標順にそれぞれソートしたＸ座標ソート列およびＹ座標ソート列を作成し、当該Ｘ座標ソート列およびＹ座標ソート列を参照して、前記エリア特定部が特定したデータ抽出領域にＸ座標およびＹ座標が位置する道路周辺データを抽出する周辺データ抽出部とを備えたことを特徴とする請求項１記載の情報抽出装置。
【請求項３】
前記記憶部に記憶された地図データを所定範囲の矩形ブロックに分割し、当該矩形ブロックに前記経路からの距離に応じた識別情報を付すブロック特定部と、
前記矩形ブロックの識別情報を参照し、前記記憶部に記憶された道路周辺データのうち前記経路から所定の距離以内の矩形ブロックに位置する道路周辺データを抽出するブロック内周辺データ抽出部とを備え、
前記周辺データ抽出部は、前記ブロック内周辺データ抽出部が取得した前記経路から所定の距離以内の矩形ブロックに位置する道路周辺データをＸ座標およびＹ座標順にそれぞれソートしたＸ座標ソート列およびＹ座標ソート列を作成することを特徴とする請求項２記載の情報抽出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ルート周辺情報の検索を行う情報抽出装置に関するものである。
【背景技術】
【０００２】
従来より、経路案内を行うナビゲーション装置などにおいて、現在地から目的地までの最適経路を検索して表示すると共に、ユーザが指定した施設、例えばガソリンスタンド、コンビニエンスストア、カー用品店などのうち、経路から所定の距離以内にある店舗や施設を表示する機能が搭載されている。例えば、特許文献１には、地図をメッシュに区切り、当該メッシュ内において経路から所定の距離内の範囲を経路周辺領域と設定し、当該経路周辺領域の中に存在する地図データから、経路との距離が所定の範囲内の店舗や施設を抽出する方法が提案されている。また、特許文献２には、地図をメッシュに区切り、当該メッシュ内において、経路から一定の距離内を周辺領域として設定し、この中から地図データを抽出する技術が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００５−３２１２２４号公報
【特許文献２】特開２００４−１３２８１４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、特許文献１に開示された従来の周辺施設検索装置では、メッシュ内に含まれる店舗数や施設数の増加に比例して平方根計算を伴う距離計算処理回数が増加し、処理に時間がかかるという課題があった。また、特許文献２に開示された技術では、設定した周辺領域から対象を抽出する動作については明記されておらず、周辺領域内の情報を高速に抽出することはできないという課題があった。【０００５】
この発明は、上記のような課題を解決するためになされたもので、ルート周辺情報を高速に抽出することを目的とする。
【課題を解決するための手段】
【０００６】
この発明に係る情報抽出装置は、地図データおよび道路周辺データを記憶する記憶部と、目的地が設定された場合に、記憶部に記憶された地図データを用いて現在地から目的地に至る経路を設定する経路設定部と、経路設定部が設定した経路の周辺データの検索が指示された場合に、経路を構成する経路ノード間を所定の距離に分割した地点に補間点を設け、経路ノードおよび補間点を基準とした矩形領域をデータ抽出領域に特定するエリア特定部とを備えるものである。
【発明の効果】
【０００７】
この発明によれば、目的地までの経路の周辺データの検索が指示された場合に、経路を構成する経路ノード間を所定の距離に分割した地点に補間点を設け、経路ノードおよび補間点を基準とした矩形領域をデータ抽出領域に特定するように構成したので、ルート周辺情報を高速に抽出することができる。
【図面の簡単な説明】
【０００８】
【図１】実施の形態１による情報抽出装置の構成を示すブロック図である。
【図２】実施の形態１による情報抽出装置の動作を示すフローチャートである。
【図３】実施の形態１による情報抽出装置の施設シンボル抽出処理の一例を示した説明図である。
【図４】実施の形態１による情報抽出装置の抽出エリア特定部の動作を示すフローチャートである。
【図５】実施の形態１による情報抽出装置の施設シンボル抽出部の動作を示すフローチャートである。
【図６】実施の形態１による情報抽出装置の抽出処理部のその他の動作の一例を示すフローチャートである。
【図７】実施の形態２による情報抽出装置の構成を示すブロック図である。
【図８】実施の形態２による情報抽出装置の動作を示すフローチャートである。
【図９】実施の形態２による情報抽出装置のブロック設定処理の一例を示した説明図である。
【図１０】実施の形態２による情報抽出装置のブロック抽出部の動作を示すフローチャートである。
【図１１】実施の形態２による情報抽出装置のブロック内施設シンボル抽出部の動作を示すフローチャートである。
【図１２】実施の形態２による情報抽出装置の施設シンボル抽出部の動作を示すフローチャートである。
【発明を実施するための形態】
【０００９】
以下、この発明をより詳細に説明するために、この発明を実施するための形態について、添付の図面に従って説明する。
実施の形態１．
図１は、この発明の実施の形態１による情報抽出装置の構成を示すブロック図である。
情報抽出装置１０は、経路設定部１、抽出制御部２、抽出処理部３、パラメータ制御部４、地図データ記憶部（記憶部）５、および描画部６で構成されている。また、情報抽出装置１０は、外部からユーザ操作などによる入力を受け付ける操作入力部１１、および描画した地図を表示する表示部１２と接続されている。
【００１０】
経路設定部１は、操作入力部１１を介して入力される経路探索指示に基づき目的地までの経路を設定する。また、経路周辺情報の検索指示の入力を受け付け、当該経路周辺情報検索指示を抽出制御部２に出力する。抽出制御部２は、経路設定部１から入力される経路周辺情報検索指示に基づいて、ガソリンスタンドなどの商標アイコン、東京タワーやディズニーランドなどの固有施設および信号や一方通行アイコンなどの交通規制マークなどの道路周辺データ（以下、総称して施設シンボルと記載する。）の抽出を指示する施設シンボル抽出制御情報を出力する。
【００１１】
抽出処理部３は、抽出エリア特定部（エリア特定部）３１および施設シンボル抽出部（周辺データ抽出部）３２で構成されている。抽出エリア特定部３１は、抽出制御部２から入力される施設シンボル抽出制御情報により施設シンボルの抽出を指示された場合には、経路から所定の距離以内のエリアを特定する。施設シンボル抽出部３２は、抽出エリア特定部３１において特定したエリアから施設シンボルを抽出する。パラメータ制御部４は、地図データを描画するためのパラメータを有している。なお、使用パラメータは、抽出制御部２で設定する。地図データ記憶部５は、道路データ、背景データおよび施設シンボルデータを格納する。描画部６は、目的地までの経路を示した地図を描画すると共に、当該地図上に施設シンボル抽出部３２が抽出した施設シンボルを描画する。
【００１２】
図２は、この発明の実施の形態１による情報抽出装置の動作を示すフローチャートである。図２を参照しながら、情報抽出装置１０の動作について説明する。
まず、操作入力部１１を介して経路探索指示が入力されると、経路設定部１は地図データ記憶部５に記憶された道路データを参照して目的地までの経路を設定する（ステップＳＴ１）。また経路設定部１は、操作入力部１１を介して経路周辺情報検索指示が入力されると、当該経路周辺情報検索指示を抽出制御部２に出力する（ステップＳＴ２）。なお、経路探索指示が入力されると自動的に経路周辺情報検索指示を抽出制御部２に出力するように構成してもよい。
【００１３】
抽出制御部２は、ステップＳＴ２で入力された経路周辺情報検索指示に基づき、ステップＳＴ１において設定された目的地までの経路周辺に位置する施設シンボルの抽出を指示する、施設シンボル抽出制御情報を抽出処理部３に出力する（ステップＳＴ３）。抽出処理部３は、ステップＳＴ３で入力された施設シンボル抽出制御情報に従い、まず抽出エリア特定部３１が施設シンボルを抽出するエリアを特定し、施設シンボル抽出エリアとして施設シンボル抽出部３２に出力する（ステップＳＴ４）。なお、抽出するエリアを特定する際に用いるパラメータ（例えば、後述する補間点の間隔や、矩形の１辺の長さなど）は、パラメータ制御部４から入力される。
【００１４】
施設シンボル抽出部３２は、地図データ記憶部５から取得した施設シンボルデータとステップＳＴ４で入力された施設シンボル抽出エリアを参照し、目的地までの経路周辺に位置する施設シンボルを抽出し、抽出した施設シンボルに関するデータを描画部６に出力する（ステップＳＴ５）。描画部６は、抽出処理部３から入力される経路ノード、抽出した施設シンボルに関するデータ、地図データ記憶部５から取得する道路データおよび背景データに基づいて、地図および施設シンボルを描画する（ステップＳＴ６）。これにより、表示部１２に施設シンボルが描画された地図情報が表示される。
【００１５】
次に、抽出エリア特定部３１が施設シンボルを抽出するエリアを特定する処理（ステップＳＴ４）の詳細、および施設シンボル抽出部３２が施設シンボルを抽出する処理（ステップＳＴ５）の詳細について図３から図５を参照しながら説明を行う。
図３は、実施の形態１による情報抽出装置の施設シンボルの抽出例を示した説明図である。また、図４は実施の形態１による情報抽出装置の抽出エリア特定部の動作を示すフローチャートであり、図５は施設シンボル抽出部の操作を示すフローチャートである。
【００１６】
まず、図３および図４を参照しながら抽出エリア特定部３１の処理動作について説明する。
抽出エリア特定部３１は、抽出制御部２から施設シンボル抽出制御情報が入力されると、経路設定部１から目的地までの経路ノードを取得する（ステップＳＴ１１）。また、パラメータ制御部４から、抽出エリアを特定するためのパラメータ、例えば補間点の間隔や矩形の１辺の長さを示すパラメータを取得する（ステップＳＴ１２）。
【００１７】
ステップＳＴ１１で取得した経路ノードは、データ量を削減するため、例えば直線に近い場合は頂点間距離が長く、逆に曲線に近い場合は頂点間距離が短く設定されるなど、頂点間距離が不均一に構成されている（図３（ａ）参照）。そのため、ステップＳＴ１２で取得したパラメータのうち、補間点の間隔を示すパラメータに基づいて経路ノード間に新たな補間点を設け、経路ノードを等距離に分割する処理を行う（ステップＳＴ１３、図３（ｂ）参照）。なお、経路ノードを分割する際に用いる経路ノードの距離を算出する開始地点は、経路設定部１から取得した全ての経路ノードに設定してもよく、また取得した経路ノードのいずれか１つに設定してもよい。
【００１８】
次に、経路ノードあるいは補間点の座標を対角線の交点にもつ矩形を生成し、当該矩形に含まれる領域を施設シンボル抽出エリアに設定する（ステップＳＴ１４、図３（ｃ）参照）。なお、矩形の１辺の長さは、ステップＳＴ１２で取得したパラメータに基づいて決定される。全ての経路ノードおよび補間点について矩形を生成したか否か判定を行い（ステップＳＴ１５）、全ての経路ノードおよび補間点について生成していないと判定された場合にはステップＳＴ１４の処理に戻り、上述した処理を繰り返す。一方、全ての経路ノードおよび補間点について生成したと判定された場合には、施設シンボル抽出エリアを施設シンボル抽出部３２に出力し（ステップＳＴ１６）、処理を終了する。
【００１９】
次に、図３および図５を参照しながら施設シンボルを抽出する処理について説明する。
施設シンボル抽出部３２は、地図データ記憶部５から施設シンボルデータを取得し（ステップＳＴ２１）、表示範囲内に位置する施設シンボルデータをＸ座標でソートしたソート列を生成する（ステップＳＴ２２）と共に、Ｙ座標でソートしたソート列を生成する（ステップＳＴ２３）。次に、抽出エリア特定部３１から入力されるシンボル抽出エリアを参照し、矩形の４頂点の座標を取得して抽出範囲を設定する（ステップＳＴ２４、図３（ｃ）参照）。
【００２０】
ステップＳＴ２２で生成したＸ座標のソート列からステップＳＴ２４において設定した抽出範囲内にＸ座標を持つ施設シンボルを抽出する（ステップＳＴ２５）。
具体的な抽出方法としては、例えば補間点の位置がＸｉ、矩形の一辺の長さがＷである場合、Ｘｉ−Ｗ／２以上、Ｘｉ＋Ｗ／２以下となるＸ座標を持つ施設シンボルをＸ座標のソート列から抽出する。このとき、まず２分探索などの手法を用いてＸ座標のソート列からＸｉ座標の挿入位置を検出し、その後Ｘ座標のソート列の中から当該挿入位置を中心にＷ幅の範囲内の座標を持つ施設シンボルを抽出する。
【００２１】
同様にステップＳＴ２３で生成したＹ座標のソート列からステップＳＴ２４において設定した抽出範囲内にＹ座標を持つ施設シンボルを抽出する（ステップＳＴ２６）。次に、ステップＳＴ２５およびＳＴ２６で抽出した施設シンボルの中から、抽出範囲内にＸ座標およびＹ座標が共通して含まれる施設シンボルを抽出する（ステップＳＴ２７）。
【００２２】
その後、全ての抽出範囲について施設シンボルを抽出したか否か判定を行い（ステップＳＴ２８）、全ての抽出範囲について施設シンボルの抽出が行われていないと判定された場合にはステップＳＴ２４の処理に戻り、上述した処理を繰り返す。一方、全ての抽出範囲について施設シンボルの抽出が行われたと判定された場合には、抽出した施設シンボルデータを描画部６に出力し（ステップＳＴ２９）、処理を終了する。
【００２３】
なお、上述の説明では、抽出エリア特定部３１の抽出エリアを特定する処理と施設シンボル抽出部３２の施設シンボル抽出処理を独立して行う構成を示したが、当該抽出エリア特定処理および施設シンボル抽出処理において、全ての補間点について処理を行ったか否か判定する処理は共通であるため、まとめて処理するように構成してもよい。図６は、抽出エリア特定処理と施設シンボル抽出処理を一つの構成（例えば抽出処理部３）がまとめて行う場合の処理を示すフローチャートである。なお、ブロック図については記載を省略する。
【００２４】
抽出処理部３は、経路設定部１から経路ノードを取得する（ステップＳＴ１１）。また、パラメータ制御部４から、抽出エリアを特定するためのパラメータ、例えば補間点の間隔や矩形の１辺の長さを示すパラメータを取得する（ステップＳＴ１２）。ステップＳＴ１２で取得したパラメータのうち、補間点の間隔を示すパラメータに基づいて経路ノード間に新たな補間点を設け、経路ノードを等距離に分割する処理を行う（ステップＳＴ１３）。
【００２５】
施設シンボル抽出部３２は、地図データ記憶部５から施設シンボルデータを取得し（ステップＳＴ２１）、表示範囲内に位置する施設シンボルデータをＸ座標でソートしたソート列を生成する（ステップＳＴ２２）と共に、Ｙ座標でソートしたソート列を生成する（ステップＳＴ２３）。経路ノードおよび補間点の座標を対角線の交点にもつ矩形を生成し、当該矩形に含まれる領域を抽出範囲に設定する（ステップＳＴ１４）。ステップＳＴ２２で生成したＸ座標のソート列からステップＳＴ１４において設定した抽出範囲内にＸ座標を持つ施設シンボルを抽出する（ステップＳＴ２５）。同様にステップＳＴ２３で生成したＹ座標のソート列からステップＳＴ２４において設定した抽出範囲内にＹ座標を持つ施設シンボルを抽出する（ステップＳＴ２６）。
【００２６】
その後、ステップＳＴ２５およびＳＴ２６で抽出した施設シンボルの中から、抽出範囲内にＸ座標およびＹ座標が共通して含まれる施設シンボルを抽出する（ステップＳＴ２７）。全ての抽出範囲について施設シンボルを抽出したか否か判定を行う（ステップＳＴ２８）。ステップＳＴ２８において全ての抽出範囲について施設シンボルの抽出が行われていないと判定された場合にはステップＳＴ１４の処理に戻り、上述した処理を繰り返す。一方、ステップＳＴ２８において全ての抽出範囲について施設シンボルの抽出が行われたと判定された場合には、抽出した施設シンボルデータを描画部６に出力し（ステップＳＴ２９）、処理を終了する。
【００２７】
抽出エリアの特定と施設シンボルの抽出をまとめて行うことにより、図４のステップＳＴ１５で示したすべての経路ノードおよび補間点について生成したか否かの確認処理を省略することができる。また、抽出エリア特定部３１が生成した矩形を抽出範囲に設定するため、図５のステップＳＴ２４で示した抽出範囲を設定する処理を省略することができる。これらにより、施設シンボル抽出処理の高速化を実現することができる。
【００２８】
以上のように、この実施の形態１によれば、表示範囲内に位置する施設シンボルをＸ座標およびＹ座標でソートし、当該ソート列から抽出範囲内に位置する施設シンボルを抽出する施設シンボル抽出部３２を備えるように構成したので、描画すべき施設シンボルを高速に抽出することができる。
【００２９】
また、この実施の形態１によれば、経路ノードおよび補間点の座標を対角線の交点にもつ矩形を設定し、当該矩形を経路から所定距離以内に位置する抽出エリアと特定する抽出エリア特定部３１を備えるように構成したので、経路からの距離の計算を抽出エリア（矩形）の内側に位置するかあるいは抽出エリアの外側に位置するかの判定で代用することができ、経路からの距離を計算する処理にかかる時間を短縮することができる。
【００３０】
また、上述した実施の形態１の構成において、経路ノードおよび補間点上に配置する矩形の大きさは経路ノード、補間点毎に固有の大きさとすることが可能である。これにより、抽出範囲を任意形状とすることが可能となる。こうすることで、例えば、経路上で自車位置に近い程、抽出範囲を広めて多くのシンボルを表示することが可能となる。
【００３１】
また、上述した実施の形態１では、Ｘ座標ソート列から矩形内に包含されるデータ抽出を行う構成を示したが、Ｙ座標ソート列から先に抽出してもよい。
【００３２】
また、上述した実施の形態１では、パラメータ制御部４から与えられるパラメータに基づいて抽出エリアを生成する構成を示したが、ユーザから与えられる設定値に基づいて抽出エリアを生成するように構成してもよい。
【００３３】
実施の形態２．
上述した実施の形態１では、表示範囲内に位置する全ての施設シンボルをＸ座標およびＹ座標でソートしたソート列を生成し、当該ソート列から描画対象となる施設シンボルを抽出する構成を示したが、この実施の形態２では、より高速な情報抽出処理を実現するために、地図を所定の大きさのブロックに分割し、経路周辺のブロック内に位置する施設シンボルのみをソートする構成を示す。
【００３４】
図７は、実施の形態２による情報抽出装置の構成を示すブロック図である。この実施の形態２では、実施の形態１の情報抽出装置１０の抽出処理部３にブロック特定部３３およびブロック内施設シンボル抽出部（ブロック内周辺データ抽出部）３４を追加して設けている。なお、以下では、実施の形態１による情報抽出装置１０の構成要素と同一または相当する部分には実施の形態１で使用した符号と同一の符号を付して説明を省略または簡略化する。
【００３５】
ブロック特定部３３は、地図データ記憶部５から取得する地図データを所定の大きさのブロック（矩形）に等分割し、経路周辺に位置するブロックを特定する。ブロックの特定は、該当するブロックに識別情報を付す（例えば、該当するブロックにフラグを立てる、あるいは目印を付すなど）。ブロック内施設シンボル抽出部３４は、地図データ記憶部５から施設シンボルデータを取得し、ブロック特定部３３が特定したブロック内に位置する施設シンボルを抽出する。ブロック特定部３３およびブロック内施設シンボル抽出部３４が取得および算出した特定ブロック、ブロック内に位置する施設シンボルに関するデータ、地図データ、経路ノードおよび補間点などに関する情報は抽出エリア特定部３１あるいは当該抽出エリア特定部３１を介して施設シンボル抽出部３２に出力される。
【００３６】
抽出エリア特定部３１は、入力される経路ノードおよび補間点の座標を対角線の交点にもつ矩形を生成し、当該矩形に含まれる領域を施設シンボル抽出エリアに設定する。施設シンボル抽出部３２は、ブロック内施設シンボル抽出部３４が抽出したブロック内に位置する施設シンボルをＸ座標およびＹ座標でソートしたソート列を生成し、抽出エリア特定部３１が特定したエリア内に位置する施設シンボルを当該ソート列から抽出する。なお、補間点は必ずしも矩形の対角線の交点である必要はなく、当該矩形は所定の規則に従って補間点を基準に設定してもよい。
【００３７】
次に、実施の形態２による情報抽出装置の動作について図８のフローチャートを参照しながら説明する。なお、実施の形態１による情報抽出装置と同一の処理を行うステップについては図２と同一のステップ番号を付し、説明を省略または簡略化する。
抽出処理部３は、ステップＳＴ３で入力された施設シンボル抽出制御情報に従い、まず、ブロック特定部３３が地図を所定の大きさのブロックに等分割し、経路周辺に位置するブロックにフラグを立てて特定し、特定したブロックに関する情報をブロック内施設シンボル抽出部３４に出力する（ステップＳＴ３１）。ブロック内施設シンボル抽出部３４は、地図データ記憶部５から取得した施設シンボルデータを参照して、ステップＳＴ３１で入力された特定されたブロック内に位置する施設シンボルを抽出し、その他の情報と共に抽出エリア特定部３１に出力する（ステップＳＴ３２）。
【００３８】
抽出エリア特定部３１は、ステップＳＴ３２において入力される経路ノードおよび補間点に基づき施設シンボルを抽出するエリアを特定してその他の情報と共に施設シンボル抽出部３２に出力する（ステップＳＴ４´）。施設シンボル抽出部３２は、ブロック内施設シンボル抽出部３４が抽出した施設シンボルのうち、前記ステップＳＴ４´において抽出エリア特定部３１が特定した抽出エリアに位置する施設シンボルを抽出し、抽出した施設シンボルに関するデータを描画部６に出力する（ステップＳＴ５´）。
【００３９】
次に、ブロック特定部３３がブロックを特定する処理（ステップＳＴ３１）、ブロック内施設シンボル抽出部３４が特定ブロック内の施設シンボルを抽出する処理（ステップＳＴ３２）、および施設シンボル抽出部３２が施設シンボルを抽出する処理（ステップＳＴ５´）の詳細について図９から図１１を参照しながら説明を行う。図９は、実施の形態２による情報抽出装置の施設シンボルの抽出例を示した説明図である。また図１０は実施の形態２による情報抽出装置のブロック特定部の動作を示すフローチャート、図１１はブロック内施設シンボル抽出部の動作を示すフローチャート、図１２は施設シンボル抽出部の動作を示すフローチャートである。
なお、抽出エリア特定部３１が施設シンボルを抽出するエリアを特定する処理（ステップＳＴ４´）は実施の形態１とほぼ同一であるため、説明を省略する。
【００４０】
まず、図９および図１０を参照しながらブロック特定部３３の処理動作について説明する。
ブロック特定部３３は、図８のステップＳＴ３で施設シンボル抽出制御情報が入力されると、経路設定部１から目的地までの経路ノードを取得する（ステップＳＴ４１）。また、パラメータ制御部４から、ブロックを特定するためのパラメータ、例えば補間点の間隔やブロックの当分割を示すパラメータを取得する（ステップＳＴ４２）。ステップＳＴ４２で取得したパラメータのうち、補間点の間隔を示すパラメータに基づいて経路ノード間に新たな補間点を設け、経路ノードを等距離に分割する処理を行う（ステップＳＴ４３、図９（ａ）参照）。
【００４１】
次に地図データ記憶部５から地図データを取得し、ステップＳＴ４２において取得したパラメータのうちブロックを等分割するためのパラメータ（例えば、矩形面積や矩形一辺の長さなどを示す値）に基づき地図データを等分割する（ステップＳＴ４４）。次に経路ノードおよび補間点が位置する全てのブロックに目印を付す（ステップＳＴ４５、図９（ｂ）参照）。ここで目印を付す処理とは、所定のブロックにフラグを立てるなどして、経路から所定の距離以内に位置するブロックとそれ以外のブロックとを区別する処理のことである。しかし、経路ノードまたは補間点がブロックの端に位置している場合には、経路からの距離が近いにも関わらずフラグが立たない場合が発生する。これを防ぐために、経路ノードおよび補間点が位置するブロックに加えて周囲８ブロックにもフラグを立てる（図９（ｃ）参照）。これにより経路ノードおよび補間点がブロックの端に位置している場合であっても、フラグの設定漏れを防ぐことができる。なお以下では、図９（ｂ）に示す経路ノードおよび補間点が位置するブロックを選択ブロックとし、図９（ｃ）に示す周囲８ブロックを周辺ブロックとして説明を行う。
【００４２】
その後ブロック特定部３３は、全ての経路ノードおよび補間点について位置するブロックおよびその周囲８ブロックにフラグを立てたか否か判定を行う（ステップＳＴ４６）。ステップＳＴ４６において全ての経路ノードおよび補間点について処理していないと判定された場合にはステップＳＴ４５の処理に戻る。一方、ステップＳＴ４６において全ての経路ノードおよび補間点について処理したと判定された場合には選択ブロックおよび周辺ブロックを含めたブロックに関するデータをブロック内施設シンボル抽出部３４に出力し（ステップＳＴ４７）、処理を終了する。
【００４３】
次に、図９および図１１を参照しながらブロック内施設シンボル抽出部３４の処理動作について説明する。
ブロック内施設シンボル抽出部３４は、ブロック特定部３３からブロックに関するデータを取得する（ステップＳＴ５１）と共に、地図データ記憶部５から施設シンボルデータを取得する（ステップＳＴ５２）。次に、表示範囲内に位置する施設シンボルが位置するブロックを特定し（ステップＳＴ５３）、特定したブロックにフラグが立っているか否か判定を行う（ステップＳＴ５４）。
【００４４】
ステップＳＴ５４において、フラグが立っていると判定された場合には、ブロック内の施設シンボルを抽出する（ステップＳＴ５５）。一方、ステップＳＴ５４においてフラグが立っていないと判定された場合にはステップＳＴ５６の処理に進む。全ての施設シンボルについてブロックの特定およびフラグの有無をチェックしたか否か判定を行う（ステップＳＴ５６）。ステップＳＴ５６において全ての施設シンボルについて処理が行われていないと判定された場合にはステップＳＴ５３の処理に戻る。一方、ステップＳＴ５６において処理が行われたと判定された場合には、抽出した施設シンボルデータとその他の情報を抽出エリア特定部３１に出力する（ステップＳＴ５７）。
【００４５】
次に、図９および図１２を参照しながら施設シンボル抽出部３２の処理動作について説明する。
施設シンボル抽出部３２は、ブロック内施設シンボル抽出部３４が抽出した施設シンボルデータを取得し（ステップＳＴ６１）、当該施設シンボルデータをＸ座標でソートしたソート列を生成（ステップＳＴ６２）すると共に、Ｙ座標でソートしたソート列を生成する（ステップＳＴ６３）。また、抽出エリア特定部３１から入力されたシンボル抽出エリアである矩形の４頂点の座標を取得し、抽出範囲を設定する（ステップＳＴ２４）。
【００４６】
次に、ステップＳＴ６２およびステップＳＴ６３で生成したＸ座標およびＹ座標のソート列からステップＳＴ２４で設定した抽出範囲にＸ座標およびＹ座標を持つ施設シンボルを抽出する（ステップＳＴ６４、ＳＴ６５、図９（ｄ）参照）。図９（ｄ）に示すように、ステップＳＴ６４およびステップＳＴ６５の抽出処理が選択ブロックおよび周辺ブロックの範囲に限定されるため、施設シンボルの抽出処理を高速に行うことができる。以降の処理は実施の形態１と同様であるため、説明を省略する。
【００４７】
なお、実施の形態１と同様に抽出エリア特定部３１と施設シンボル抽出部３２の処理をまとめて行うように構成してもよい。
【００４８】
以上のように、この実施の形態２によれば、地図データを所定のブロックに等分割し、経路が位置するブロックおよび当該ブロックの周囲ブロックに識別情報を付すブロック特定部３３と、識別情報が付されたブロック内の施設シンボルを抽出するブロック内施設シンボル抽出部３４と、識別情報が付されたブロック内の施設シンボルをＸ座標およびＹ座標でソートしたソート列を生成し、当該ソート列から施設シンボルを抽出する施設シンボル抽出部３２を備えるように構成したので、ブロック内で施設シンボルの間引きを行うことができ、経路周辺施設シンボルの抽出を高速に行うことができる。そのため、短時間で多くの経路周辺の施設シンボルを検索することができる。また、ソート処理にかかる時間と、ソート列から２分探索などの探索手法を用いて施設シンボルを抽出する際に必要となる時間を短縮することができ、より高速な処理を実現することができる。
【００４９】
なお、上述した実施の形態２では、パラメータ制御部４から与えられるパラメータに基づいて地図データを等分割する構成を示したが、ユーザから与えられる設定値に基づいて分割するように構成してもよいし、また分割は等分割に限定されるものではなく地図情報などに基づいて適宜変更可能である。
【００５０】
また、上述した実施の形態２では、経路ノードおよび補間点が位置するブロックに加えて周囲８ブロックにも識別情報を付す構成を示したが、識別情報を付す周辺ブロックの数は適宜変更可能である。
【００５１】
なお、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。
【産業上の利用可能性】
【００５２】
この発明に係る情報抽出装置は、ナビゲーションシステムなどのルート周辺情報の検索処理において、検索処理にかかる時間の短縮に利用することができる。
【符号の説明】
【００５３】
１  経路設定部、２  抽出制御部、３  抽出処理部、４  パラメータ制御部、５  地図データ記憶部、６  描画部、１０  情報抽出装置、１１  操作入力部、１２  表示部、３１  抽出エリア特定部、３２  施設シンボル抽出部、３３  ブロック特定部、３４  ブロック内施設シンボル抽出部
【図１】
2012090240.tif 000003
【図２】
2012090240.tif 000004
【図３】
2012090240.tif 000005
【図４】
2012090240.tif 000006
【図５】
2012090240.tif 000007
【図６】
2012090240.tif 000008
【図７】
2012090240.tif 000009
【図８】
2012090240.tif 000010
【図９】
2012090240.tif 000011
【図１０】
2012090240.tif 000012
【図１１】
2012090240.tif 000013
【図１２】
2012090240.tif 000014
【手続補正書】
【提出日】平成24年11月15日(2012.11.15)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ルート周辺情報の検索を行う情報抽出装置に関するものである。
【背景技術】
【０００２】
従来より、経路案内を行うナビゲーション装置などにおいて、現在地から目的地までの最適経路を検索して表示すると共に、ユーザが指定した施設、例えばガソリンスタンド、コンビニエンスストア、カー用品店などのうち、経路から所定の距離以内にある店舗や施設を表示する機能が搭載されている。例えば、特許文献１には、地図をメッシュに区切り、当該メッシュ内において経路から所定の距離内の範囲を経路周辺領域と設定し、当該経路周辺領域の中に存在する地図データから、経路との距離が所定の範囲内の店舗や施設を抽出する方法が提案されている。また、特許文献２には、地図をメッシュに区切り、当該メッシュ内において、経路から一定の距離内を周辺領域として設定し、この中から地図データを抽出する技術が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００５−３２１２２４号公報
【特許文献２】特開２００４−１３２８１４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、特許文献１に開示された従来の周辺施設検索装置では、メッシュ内に含まれる店舗数や施設数の増加に比例して平方根計算を伴う距離計算処理回数が増加し、処理に時間がかかるという課題があった。また、特許文献２に開示された技術では、設定した周辺領域から対象を抽出する動作については明記されておらず、周辺領域内の情報を高速に抽出することはできないという課題があった。
【０００５】
この発明は、上記のような課題を解決するためになされたもので、ルート周辺情報を高速に抽出することを目的とする。
【課題を解決するための手段】
【０００６】
この発明に係る情報抽出装置は、地図データおよび道路周辺データを記憶する記憶部と、目的地が設定された場合に、記憶部に記憶された地図データを用いて現在地から目的地に至る経路を設定する経路設定部と、経路設定部が設定した経路の周辺データの検索が指示された場合に、経路を構成する経路ノード間を所定の距離に分割した地点に補間点を設け、経路ノードおよび補間点を基準とした矩形領域をデータ抽出領域に特定するエリア特定部と、記憶部に記憶された道路周辺データからデータ抽出領域の道路周辺データを抽出する周辺データ抽出部とを備えるものである。
【発明の効果】
【０００７】
この発明によれば、目的地までの経路の周辺データの検索が指示された場合に、経路を構成する経路ノード間を所定の距離に分割した地点に補間点を設け、経路ノードおよび補間点を基準とした矩形領域をデータ抽出領域に特定するように構成したので、ルート周辺情報を高速に抽出することができる。
【図面の簡単な説明】
【０００８】
【図１】実施の形態１による情報抽出装置の構成を示すブロック図である。
【図２】実施の形態１による情報抽出装置の動作を示すフローチャートである。
【図３】実施の形態１による情報抽出装置の施設シンボル抽出処理の一例を示した説明図である。
【図４】実施の形態１による情報抽出装置の抽出エリア特定部の動作を示すフローチャートである。
【図５】実施の形態１による情報抽出装置の施設シンボル抽出部の動作を示すフローチャートである。
【図６】実施の形態１による情報抽出装置の抽出処理部のその他の動作の一例を示すフローチャートである。
【図７】実施の形態２による情報抽出装置の構成を示すブロック図である。
【図８】実施の形態２による情報抽出装置の動作を示すフローチャートである。
【図９】実施の形態２による情報抽出装置のブロック設定処理の一例を示した説明図である。
【図１０】実施の形態２による情報抽出装置のブロック抽出部の動作を示すフローチャートである。
【図１１】実施の形態２による情報抽出装置のブロック内施設シンボル抽出部の動作を示すフローチャートである。
【図１２】実施の形態２による情報抽出装置の施設シンボル抽出部の動作を示すフローチャートである。
【発明を実施するための形態】
【０００９】
以下、この発明をより詳細に説明するために、この発明を実施するための形態について、添付の図面に従って説明する。
実施の形態１．
図１は、この発明の実施の形態１による情報抽出装置の構成を示すブロック図である。
情報抽出装置１０は、経路設定部１、抽出制御部２、抽出処理部３、パラメータ制御部４、地図データ記憶部（記憶部）５、および描画部６で構成されている。また、情報抽出装置１０は、外部からユーザ操作などによる入力を受け付ける操作入力部１１、および描画した地図を表示する表示部１２と接続されている。
【００１０】
経路設定部１は、操作入力部１１を介して入力される経路探索指示に基づき目的地までの経路を設定する。また、経路周辺情報の検索指示の入力を受け付け、当該経路周辺情報検索指示を抽出制御部２に出力する。抽出制御部２は、経路設定部１から入力される経路周辺情報検索指示に基づいて、ガソリンスタンドなどの商標アイコン、東京タワーやディズニーランドなどの固有施設および信号や一方通行アイコンなどの交通規制マークなどの道路周辺データ（以下、総称して施設シンボルと記載する。）の抽出を指示する施設シンボル抽出制御情報を出力する。
【００１１】
抽出処理部３は、抽出エリア特定部（エリア特定部）３１および施設シンボル抽出部（周辺データ抽出部）３２で構成されている。抽出エリア特定部３１は、抽出制御部２から入力される施設シンボル抽出制御情報により施設シンボルの抽出を指示された場合には、経路から所定の距離以内のエリアを特定する。施設シンボル抽出部３２は、抽出エリア特定部３１において特定したエリアから施設シンボルを抽出する。パラメータ制御部４は、地図データを描画するためのパラメータを有している。なお、使用パラメータは、抽出制御部２で設定する。地図データ記憶部５は、道路データ、背景データおよび施設シンボルデータを格納する。描画部６は、目的地までの経路を示した地図を描画すると共に、当該地図上に施設シンボル抽出部３２が抽出した施設シンボルを描画する。
【００１２】
図２は、この発明の実施の形態１による情報抽出装置の動作を示すフローチャートである。図２を参照しながら、情報抽出装置１０の動作について説明する。
まず、操作入力部１１を介して経路探索指示が入力されると、経路設定部１は地図データ記憶部５に記憶された道路データを参照して目的地までの経路を設定する（ステップＳＴ１）。また経路設定部１は、操作入力部１１を介して経路周辺情報検索指示が入力されると、当該経路周辺情報検索指示を抽出制御部２に出力する（ステップＳＴ２）。なお、経路探索指示が入力されると自動的に経路周辺情報検索指示を抽出制御部２に出力するように構成してもよい。
【００１３】
抽出制御部２は、ステップＳＴ２で入力された経路周辺情報検索指示に基づき、ステップＳＴ１において設定された目的地までの経路周辺に位置する施設シンボルの抽出を指示する、施設シンボル抽出制御情報を抽出処理部３に出力する（ステップＳＴ３）。抽出処理部３は、ステップＳＴ３で入力された施設シンボル抽出制御情報に従い、まず抽出エリア特定部３１が施設シンボルを抽出するエリアを特定し、施設シンボル抽出エリアとして施設シンボル抽出部３２に出力する（ステップＳＴ４）。なお、抽出するエリアを特定する際に用いるパラメータ（例えば、後述する補間点の間隔や、矩形の１辺の長さなど）は、パラメータ制御部４から入力される。
【００１４】
施設シンボル抽出部３２は、地図データ記憶部５から取得した施設シンボルデータとステップＳＴ４で入力された施設シンボル抽出エリアを参照し、目的地までの経路周辺に位置する施設シンボルを抽出し、抽出した施設シンボルに関するデータを描画部６に出力する（ステップＳＴ５）。描画部６は、抽出処理部３から入力される経路ノード、抽出した施設シンボルに関するデータ、地図データ記憶部５から取得する道路データおよび背景データに基づいて、地図および施設シンボルを描画する（ステップＳＴ６）。これにより、表示部１２に施設シンボルが描画された地図情報が表示される。
【００１５】
次に、抽出エリア特定部３１が施設シンボルを抽出するエリアを特定する処理（ステップＳＴ４）の詳細、および施設シンボル抽出部３２が施設シンボルを抽出する処理（ステップＳＴ５）の詳細について図３から図５を参照しながら説明を行う。
図３は、実施の形態１による情報抽出装置の施設シンボルの抽出例を示した説明図である。また、図４は実施の形態１による情報抽出装置の抽出エリア特定部の動作を示すフローチャートであり、図５は施設シンボル抽出部の操作を示すフローチャートである。
【００１６】
まず、図３および図４を参照しながら抽出エリア特定部３１の処理動作について説明する。
抽出エリア特定部３１は、抽出制御部２から施設シンボル抽出制御情報が入力されると、経路設定部１から目的地までの経路ノードを取得する（ステップＳＴ１１）。また、パラメータ制御部４から、抽出エリアを特定するためのパラメータ、例えば補間点の間隔や矩形の１辺の長さを示すパラメータを取得する（ステップＳＴ１２）。
【００１７】
ステップＳＴ１１で取得した経路ノードは、データ量を削減するため、例えば直線に近い場合は頂点間距離が長く、逆に曲線に近い場合は頂点間距離が短く設定されるなど、頂点間距離が不均一に構成されている（図３（ａ）参照）。そのため、ステップＳＴ１２で取得したパラメータのうち、補間点の間隔を示すパラメータに基づいて経路ノード間に新たな補間点を設け、経路ノードを等距離に分割する処理を行う（ステップＳＴ１３、図３（ｂ）参照）。なお、経路ノードを分割する際に用いる経路ノードの距離を算出する開始地点は、経路設定部１から取得した全ての経路ノードに設定してもよく、また取得した経路ノードのいずれか１つに設定してもよい。
【００１８】
次に、経路ノードあるいは補間点の座標を対角線の交点にもつ矩形を生成し、当該矩形に含まれる領域を施設シンボル抽出エリアに設定する（ステップＳＴ１４、図３（ｃ）参照）。なお、矩形の１辺の長さは、ステップＳＴ１２で取得したパラメータに基づいて決定される。全ての経路ノードおよび補間点について矩形を生成したか否か判定を行い（ステップＳＴ１５）、全ての経路ノードおよび補間点について生成していないと判定された場合にはステップＳＴ１４の処理に戻り、上述した処理を繰り返す。一方、全ての経路ノードおよび補間点について生成したと判定された場合には、施設シンボル抽出エリアを施設シンボル抽出部３２に出力し（ステップＳＴ１６）、処理を終了する。
【００１９】
次に、図３および図５を参照しながら施設シンボルを抽出する処理について説明する。
施設シンボル抽出部３２は、地図データ記憶部５から施設シンボルデータを取得し（ステップＳＴ２１）、表示範囲内に位置する施設シンボルデータをＸ座標でソートしたソート列を生成する（ステップＳＴ２２）と共に、Ｙ座標でソートしたソート列を生成する（ステップＳＴ２３）。次に、抽出エリア特定部３１から入力されるシンボル抽出エリアを参照し、矩形の４頂点の座標を取得して抽出範囲を設定する（ステップＳＴ２４、図３（ｃ）参照）。
【００２０】
ステップＳＴ２２で生成したＸ座標のソート列からステップＳＴ２４において設定した抽出範囲内にＸ座標を持つ施設シンボルを抽出する（ステップＳＴ２５）。
具体的な抽出方法としては、例えば補間点の位置がＸｉ、矩形の一辺の長さがＷである場合、Ｘｉ−Ｗ／２以上、Ｘｉ＋Ｗ／２以下となるＸ座標を持つ施設シンボルをＸ座標のソート列から抽出する。このとき、まず２分探索などの手法を用いてＸ座標のソート列からＸｉ座標の挿入位置を検出し、その後Ｘ座標のソート列の中から当該挿入位置を中心にＷ幅の範囲内の座標を持つ施設シンボルを抽出する。
【００２１】
同様にステップＳＴ２３で生成したＹ座標のソート列からステップＳＴ２４において設定した抽出範囲内にＹ座標を持つ施設シンボルを抽出する（ステップＳＴ２６）。次に、ステップＳＴ２５およびＳＴ２６で抽出した施設シンボルの中から、抽出範囲内にＸ座標およびＹ座標が共通して含まれる施設シンボルを抽出する（ステップＳＴ２７）。
【００２２】
その後、全ての抽出範囲について施設シンボルを抽出したか否か判定を行い（ステップＳＴ２８）、全ての抽出範囲について施設シンボルの抽出が行われていないと判定された場合にはステップＳＴ２４の処理に戻り、上述した処理を繰り返す。一方、全ての抽出範囲について施設シンボルの抽出が行われたと判定された場合には、抽出した施設シンボルデータを描画部６に出力し（ステップＳＴ２９）、処理を終了する。
【００２３】
なお、上述の説明では、抽出エリア特定部３１の抽出エリアを特定する処理と施設シンボル抽出部３２の施設シンボル抽出処理を独立して行う構成を示したが、当該抽出エリア特定処理および施設シンボル抽出処理において、全ての補間点について処理を行ったか否か判定する処理は共通であるため、まとめて処理するように構成してもよい。図６は、抽出エリア特定処理と施設シンボル抽出処理を一つの構成（例えば抽出処理部３）がまとめて行う場合の処理を示すフローチャートである。なお、ブロック図については記載を省略する。
【００２４】
抽出処理部３は、経路設定部１から経路ノードを取得する（ステップＳＴ１１）。また、パラメータ制御部４から、抽出エリアを特定するためのパラメータ、例えば補間点の間隔や矩形の１辺の長さを示すパラメータを取得する（ステップＳＴ１２）。ステップＳＴ１２で取得したパラメータのうち、補間点の間隔を示すパラメータに基づいて経路ノード間に新たな補間点を設け、経路ノードを等距離に分割する処理を行う（ステップＳＴ１３）。
【００２５】
施設シンボル抽出部３２は、地図データ記憶部５から施設シンボルデータを取得し（ステップＳＴ２１）、表示範囲内に位置する施設シンボルデータをＸ座標でソートしたソート列を生成する（ステップＳＴ２２）と共に、Ｙ座標でソートしたソート列を生成する（ステップＳＴ２３）。経路ノードおよび補間点の座標を対角線の交点にもつ矩形を生成し、当該矩形に含まれる領域を抽出範囲に設定する（ステップＳＴ１４）。ステップＳＴ２２で生成したＸ座標のソート列からステップＳＴ１４において設定した抽出範囲内にＸ座標を持つ施設シンボルを抽出する（ステップＳＴ２５）。同様にステップＳＴ２３で生成したＹ座標のソート列からステップＳＴ２４において設定した抽出範囲内にＹ座標を持つ施設シンボルを抽出する（ステップＳＴ２６）。
【００２６】
その後、ステップＳＴ２５およびＳＴ２６で抽出した施設シンボルの中から、抽出範囲内にＸ座標およびＹ座標が共通して含まれる施設シンボルを抽出する（ステップＳＴ２７）。全ての抽出範囲について施設シンボルを抽出したか否か判定を行う（ステップＳＴ２８）。ステップＳＴ２８において全ての抽出範囲について施設シンボルの抽出が行われていないと判定された場合にはステップＳＴ１４の処理に戻り、上述した処理を繰り返す。一方、ステップＳＴ２８において全ての抽出範囲について施設シンボルの抽出が行われたと判定された場合には、抽出した施設シンボルデータを描画部６に出力し（ステップＳＴ２９）、処理を終了する。
【００２７】
抽出エリアの特定と施設シンボルの抽出をまとめて行うことにより、図４のステップＳＴ１５で示したすべての経路ノードおよび補間点について生成したか否かの確認処理を省略することができる。また、抽出エリア特定部３１が生成した矩形を抽出範囲に設定するため、図５のステップＳＴ２４で示した抽出範囲を設定する処理を省略することができる。これらにより、施設シンボル抽出処理の高速化を実現することができる。
【００２８】
以上のように、この実施の形態１によれば、表示範囲内に位置する施設シンボルをＸ座標およびＹ座標でソートし、当該ソート列から抽出範囲内に位置する施設シンボルを抽出する施設シンボル抽出部３２を備えるように構成したので、描画すべき施設シンボルを高速に抽出することができる。
【００２９】
また、この実施の形態１によれば、経路ノードおよび補間点の座標を対角線の交点にもつ矩形を設定し、当該矩形を経路から所定距離以内に位置する抽出エリアと特定する抽出エリア特定部３１を備えるように構成したので、経路からの距離の計算を抽出エリア（矩形）の内側に位置するかあるいは抽出エリアの外側に位置するかの判定で代用することができ、経路からの距離を計算する処理にかかる時間を短縮することができる。
【００３０】
また、上述した実施の形態１の構成において、経路ノードおよび補間点上に配置する矩形の大きさは経路ノード、補間点毎に固有の大きさとすることが可能である。これにより、抽出範囲を任意形状とすることが可能となる。こうすることで、例えば、経路上で自車位置に近い程、抽出範囲を広めて多くのシンボルを表示することが可能となる。
【００３１】
また、上述した実施の形態１では、Ｘ座標ソート列から矩形内に包含されるデータ抽出を行う構成を示したが、Ｙ座標ソート列から先に抽出してもよい。
【００３２】
また、上述した実施の形態１では、パラメータ制御部４から与えられるパラメータに基づいて抽出エリアを生成する構成を示したが、ユーザから与えられる設定値に基づいて抽出エリアを生成するように構成してもよい。
【００３３】
実施の形態２．
上述した実施の形態１では、表示範囲内に位置する全ての施設シンボルをＸ座標およびＹ座標でソートしたソート列を生成し、当該ソート列から描画対象となる施設シンボルを抽出する構成を示したが、この実施の形態２では、より高速な情報抽出処理を実現するために、地図を所定の大きさのブロックに分割し、経路周辺のブロック内に位置する施設シンボルのみをソートする構成を示す。
【００３４】
図７は、実施の形態２による情報抽出装置の構成を示すブロック図である。この実施の形態２では、実施の形態１の情報抽出装置１０の抽出処理部３にブロック特定部３３およびブロック内施設シンボル抽出部（ブロック内周辺データ抽出部）３４を追加して設けている。なお、以下では、実施の形態１による情報抽出装置１０の構成要素と同一または相当する部分には実施の形態１で使用した符号と同一の符号を付して説明を省略または簡略化する。
【００３５】
ブロック特定部３３は、地図データ記憶部５から取得する地図データを所定の大きさのブロック（矩形）に等分割し、経路周辺に位置するブロックを特定する。ブロックの特定は、該当するブロックに識別情報を付す（例えば、該当するブロックにフラグを立てる、あるいは目印を付すなど）。ブロック内施設シンボル抽出部３４は、地図データ記憶部５から施設シンボルデータを取得し、ブロック特定部３３が特定したブロック内に位置する施設シンボルを抽出する。ブロック特定部３３およびブロック内施設シンボル抽出部３４が取得および算出した特定ブロック、ブロック内に位置する施設シンボルに関するデータ、地図データ、経路ノードおよび補間点などに関する情報は抽出エリア特定部３１あるいは当該抽出エリア特定部３１を介して施設シンボル抽出部３２に出力される。
【００３６】
抽出エリア特定部３１は、入力される経路ノードおよび補間点の座標を対角線の交点にもつ矩形を生成し、当該矩形に含まれる領域を施設シンボル抽出エリアに設定する。施設シンボル抽出部３２は、ブロック内施設シンボル抽出部３４が抽出したブロック内に位置する施設シンボルをＸ座標およびＹ座標でソートしたソート列を生成し、抽出エリア特定部３１が特定したエリア内に位置する施設シンボルを当該ソート列から抽出する。なお、補間点は必ずしも矩形の対角線の交点である必要はなく、当該矩形は所定の規則に従って補間点を基準に設定してもよい。
【００３７】
次に、実施の形態２による情報抽出装置の動作について図８のフローチャートを参照しながら説明する。なお、実施の形態１による情報抽出装置と同一の処理を行うステップについては図２と同一のステップ番号を付し、説明を省略または簡略化する。
抽出処理部３は、ステップＳＴ３で入力された施設シンボル抽出制御情報に従い、まず、ブロック特定部３３が地図を所定の大きさのブロックに等分割し、経路周辺に位置するブロックにフラグを立てて特定し、特定したブロックに関する情報をブロック内施設シンボル抽出部３４に出力する（ステップＳＴ３１）。ブロック内施設シンボル抽出部３４は、地図データ記憶部５から取得した施設シンボルデータを参照して、ステップＳＴ３１で入力された特定されたブロック内に位置する施設シンボルを抽出し、その他の情報と共に抽出エリア特定部３１に出力する（ステップＳＴ３２）。
【００３８】
抽出エリア特定部３１は、ステップＳＴ３２において入力される経路ノードおよび補間点に基づき施設シンボルを抽出するエリアを特定してその他の情報と共に施設シンボル抽出部３２に出力する（ステップＳＴ４´）。施設シンボル抽出部３２は、ブロック内施設シンボル抽出部３４が抽出した施設シンボルのうち、前記ステップＳＴ４´において抽出エリア特定部３１が特定した抽出エリアに位置する施設シンボルを抽出し、抽出した施設シンボルに関するデータを描画部６に出力する（ステップＳＴ５´）。
【００３９】
次に、ブロック特定部３３がブロックを特定する処理（ステップＳＴ３１）、ブロック内施設シンボル抽出部３４が特定ブロック内の施設シンボルを抽出する処理（ステップＳＴ３２）、および施設シンボル抽出部３２が施設シンボルを抽出する処理（ステップＳＴ５´）の詳細について図９から図１１を参照しながら説明を行う。図９は、実施の形態２による情報抽出装置の施設シンボルの抽出例を示した説明図である。また図１０は実施の形態２による情報抽出装置のブロック特定部の動作を示すフローチャート、図１１はブロック内施設シンボル抽出部の動作を示すフローチャート、図１２は施設シンボル抽出部の動作を示すフローチャートである。
なお、抽出エリア特定部３１が施設シンボルを抽出するエリアを特定する処理（ステップＳＴ４´）は実施の形態１とほぼ同一であるため、説明を省略する。
【００４０】
まず、図９および図１０を参照しながらブロック特定部３３の処理動作について説明する。
ブロック特定部３３は、図８のステップＳＴ３で施設シンボル抽出制御情報が入力されると、経路設定部１から目的地までの経路ノードを取得する（ステップＳＴ４１）。また、パラメータ制御部４から、ブロックを特定するためのパラメータ、例えば補間点の間隔やブロックの当分割を示すパラメータを取得する（ステップＳＴ４２）。ステップＳＴ４２で取得したパラメータのうち、補間点の間隔を示すパラメータに基づいて経路ノード間に新たな補間点を設け、経路ノードを等距離に分割する処理を行う（ステップＳＴ４３、図９（ａ）参照）。
【００４１】
次に地図データ記憶部５から地図データを取得し、ステップＳＴ４２において取得したパラメータのうちブロックを等分割するためのパラメータ（例えば、矩形面積や矩形一辺の長さなどを示す値）に基づき地図データを等分割する（ステップＳＴ４４）。次に経路ノードおよび補間点が位置する全てのブロックに目印を付す（ステップＳＴ４５、図９（ｂ）参照）。ここで目印を付す処理とは、所定のブロックにフラグを立てるなどして、経路から所定の距離以内に位置するブロックとそれ以外のブロックとを区別する処理のことである。しかし、経路ノードまたは補間点がブロックの端に位置している場合には、経路からの距離が近いにも関わらずフラグが立たない場合が発生する。これを防ぐために、経路ノードおよび補間点が位置するブロックに加えて周囲８ブロックにもフラグを立てる（図９（ｃ）参照）。これにより経路ノードおよび補間点がブロックの端に位置している場合であっても、フラグの設定漏れを防ぐことができる。なお以下では、図９（ｂ）に示す経路ノードおよび補間点が位置するブロックを選択ブロックとし、図９（ｃ）に示す周囲８ブロックを周辺ブロックとして説明を行う。
【００４２】
その後ブロック特定部３３は、全ての経路ノードおよび補間点について位置するブロックおよびその周囲８ブロックにフラグを立てたか否か判定を行う（ステップＳＴ４６）。ステップＳＴ４６において全ての経路ノードおよび補間点について処理していないと判定された場合にはステップＳＴ４５の処理に戻る。一方、ステップＳＴ４６において全ての経路ノードおよび補間点について処理したと判定された場合には選択ブロックおよび周辺ブロックを含めたブロックに関するデータをブロック内施設シンボル抽出部３４に出力し（ステップＳＴ４７）、処理を終了する。
【００４３】
次に、図９および図１１を参照しながらブロック内施設シンボル抽出部３４の処理動作について説明する。
ブロック内施設シンボル抽出部３４は、ブロック特定部３３からブロックに関するデータを取得する（ステップＳＴ５１）と共に、地図データ記憶部５から施設シンボルデータを取得する（ステップＳＴ５２）。次に、表示範囲内に位置する施設シンボルが位置するブロックを特定し（ステップＳＴ５３）、特定したブロックにフラグが立っているか否か判定を行う（ステップＳＴ５４）。
【００４４】
ステップＳＴ５４において、フラグが立っていると判定された場合には、ブロック内の施設シンボルを抽出する（ステップＳＴ５５）。一方、ステップＳＴ５４においてフラグが立っていないと判定された場合にはステップＳＴ５６の処理に進む。全ての施設シンボルについてブロックの特定およびフラグの有無をチェックしたか否か判定を行う（ステップＳＴ５６）。ステップＳＴ５６において全ての施設シンボルについて処理が行われていないと判定された場合にはステップＳＴ５３の処理に戻る。一方、ステップＳＴ５６において処理が行われたと判定された場合には、抽出した施設シンボルデータとその他の情報を抽出エリア特定部３１に出力する（ステップＳＴ５７）。
【００４５】
次に、図９および図１２を参照しながら施設シンボル抽出部３２の処理動作について説明する。
施設シンボル抽出部３２は、ブロック内施設シンボル抽出部３４が抽出した施設シンボルデータを取得し（ステップＳＴ６１）、当該施設シンボルデータをＸ座標でソートしたソート列を生成（ステップＳＴ６２）すると共に、Ｙ座標でソートしたソート列を生成する（ステップＳＴ６３）。また、抽出エリア特定部３１から入力されたシンボル抽出エリアである矩形の４頂点の座標を取得し、抽出範囲を設定する（ステップＳＴ２４）。
【００４６】
次に、ステップＳＴ６２およびステップＳＴ６３で生成したＸ座標およびＹ座標のソート列からステップＳＴ２４で設定した抽出範囲にＸ座標およびＹ座標を持つ施設シンボルを抽出する（ステップＳＴ６４、ＳＴ６５、図９（ｄ）参照）。図９（ｄ）に示すように、ステップＳＴ６４およびステップＳＴ６５の抽出処理が選択ブロックおよび周辺ブロックの範囲に限定されるため、施設シンボルの抽出処理を高速に行うことができる。以降の処理は実施の形態１と同様であるため、説明を省略する。
【００４７】
なお、実施の形態１と同様に抽出エリア特定部３１と施設シンボル抽出部３２の処理をまとめて行うように構成してもよい。
【００４８】
以上のように、この実施の形態２によれば、地図データを所定のブロックに等分割し、経路が位置するブロックおよび当該ブロックの周囲ブロックに識別情報を付すブロック特定部３３と、識別情報が付されたブロック内の施設シンボルを抽出するブロック内施設シンボル抽出部３４と、識別情報が付されたブロック内の施設シンボルをＸ座標およびＹ座標でソートしたソート列を生成し、当該ソート列から施設シンボルを抽出する施設シンボル抽出部３２を備えるように構成したので、ブロック内で施設シンボルの間引きを行うことができ、経路周辺施設シンボルの抽出を高速に行うことができる。そのため、短時間で多くの経路周辺の施設シンボルを検索することができる。また、ソート処理にかかる時間と、ソート列から２分探索などの探索手法を用いて施設シンボルを抽出する際に必要となる時間を短縮することができ、より高速な処理を実現することができる。
【００４９】
なお、上述した実施の形態２では、パラメータ制御部４から与えられるパラメータに基づいて地図データを等分割する構成を示したが、ユーザから与えられる設定値に基づいて分割するように構成してもよいし、また分割は等分割に限定されるものではなく地図情報などに基づいて適宜変更可能である。
【００５０】
また、上述した実施の形態２では、経路ノードおよび補間点が位置するブロックに加えて周囲８ブロックにも識別情報を付す構成を示したが、識別情報を付す周辺ブロックの数は適宜変更可能である。
【００５１】
なお、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。
【符号の説明】
【００５２】
１  経路設定部、２  抽出制御部、３  抽出処理部、４  パラメータ制御部、５  地図データ記憶部、６  描画部、１０  情報抽出装置、１１  操作入力部、１２  表示部、３１  抽出エリア特定部、３２  施設シンボル抽出部、３３  ブロック特定部、３４  ブロック内施設シンボル抽出部
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
地図データおよび道路周辺データを記憶する記憶部と、
目的地が設定された場合に、前記記憶部に記憶された前記地図データを用いて現在地から前記目的地に至る経路を設定する経路設定部と、
前記経路設定部が設定した経路の周辺データの検索が指示された場合に、前記経路を構成する経路ノード間を所定の距離に分割した地点に補間点を設け、前記経路ノードおよび前記補間点を基準とした矩形領域をデータ抽出領域に特定するエリア特定部と、
前記記憶部に記憶された前記道路周辺データから前記データ抽出領域の前記道路周辺データを抽出する周辺データ抽出部とを備えた情報抽出装置。
【請求項２】
前記周辺データ抽出部は、前記記憶部に記憶された道路周辺データをＸ座標およびＹ座標順にそれぞれソートしたＸ座標ソート列およびＹ座標ソート列を作成し、当該Ｘ座標ソート列およびＹ座標ソート列を参照して、前記エリア特定部が特定したデータ抽出領域にＸ座標およびＹ座標が位置する道路周辺データを抽出することを特徴とする請求項１記載の情報抽出装置。
【請求項３】
前記記憶部に記憶された地図データを所定範囲の矩形ブロックに分割し、当該矩形ブロックに前記経路からの距離に応じた識別情報を付すブロック特定部と、
前記矩形ブロックの識別情報を参照し、前記記憶部に記憶された道路周辺データのうち前記経路から所定の距離以内の矩形ブロックに位置する道路周辺データを抽出するブロック内周辺データ抽出部とを備え、
前記周辺データ抽出部は、前記ブロック内周辺データ抽出部が取得した前記経路から所定の距離以内の矩形ブロックに位置する道路周辺データをＸ座標およびＹ座標順にそれぞれソートしたＸ座標ソート列およびＹ座標ソート列を作成することを特徴とする請求項２記載の情報抽出装置。
【国際調査報告】
2012090240.tif 000015
2012090240.tif 000016
2012090240.tif 000017
2012090240.tif 000018