(57)【要約】【課題】  分離した要素間において直交・直進化処理を行った結果においても、それぞれの要素の方向が揃うことが可能であり、最適化処理における局所解を回避し、直交・直進化処理を完了する確率を高め、道路形状やランドマークなどの粗密性から生じる要素間に残る不自然な空白部分や、過密部分をなくし、視覚的にまとまった要約地図の生成を可能とする要約地図生成プログラムを提供する。【解決手段】  コンピュータに、補助線の生成処理を行わせる手順（Ｓ８２）、最適化処理が終了した後、評価関数の関数系を変化させて、再び最適化処理を行う手順（Ｓ８５）、地図上における所定範囲を、入力手段を介して入力された縮小率で縮小、または拡大率で拡大を行わせる手順をコンピュータに実行させることを特徴とする要約地図生成プログラムを提供する。【選択図】      図３
2006276785.tif 000002
【特許請求の範囲】
【請求項１】
入力を行う入力装置と、演算処理を行う演算装置と、出力を行う出力装置とを備えたコンピュータに、評価関数による最適化処理に基づいて道路地図の端点、および屈曲点であるノードを再配置する直交・直進化処理を行わせ、要約地図を生成させる要約地図生成プログラムにおいて、
前記演算装置に、
前記入力装置を介して入力された情報を基に、道路形状を示す線により構成される第１のオブジェクトと、前記第１のオブジェクトを構成する線とは交差しない少なくとも１本の線により構成される第２のオブジェクトを結ぶ仮想の線である補助線の生成処理を行わせる手順、
前記補助線と、前記第１のオブジェクトを構成する線と、第２のオブジェクトとを構成する少なくとも１本の線とを含んでなる線について、前記直交・直進化処理を行わせる手順、
前記直交・直進化処理の結果を前記出力装置へ出力させる手順、
を実行させること、を特徴とする要約地図生成プログラム。
【請求項２】
前記補助線は、前記入力装置を介して入力された道路地図上の範囲指定における領域境界線であることを特徴とする請求項１に記載の要約地図生成プログラム。
【請求項３】
前記領域境界線は、前記第２のオブジェクトが、いずれにも交差しない線、かつ前記領域境界線に結ばれない独立した線を有する場合には、前記領域境界線に、さらに第２の補助線を加えることを特徴とする請求項２に記載の要約地図生成プログラム。
【請求項４】
評価関数による最適化処理に基づいて道路地図の端点、および屈曲点であるノードを再配置する最適化手段を含んで構成される要約地図生成装置における要約地図生成プログラムであって、
前記最適化手段が、前記最適化処理が終了した後、前記評価関数の関数系を変化させて、再び最適化処理を行う手順を前記要約地図生成装置としてのコンピュータに実行させることを特徴とする要約地図生成プログラム。
【請求項５】
前記評価関数の関数系を変化させるとは、最適化処理が終了した時点の、ノードの配置を定数項に代入することを特徴とする請求項４に記載の要約地図生成プログラム。
【請求項６】
入力を行う入力装置と、演算処理を行う演算装置と、出力を行う出力装置を備えたコンピュータに、地図形状を簡略化するデフォルメ処理を行わせ、要約地図を生成させる要約地図生成プログラムにおいて、
前記演算装置に、
前記入力装置(4)を介して入力された情報を基に、地図上における所定範囲を、前記入力装置(4)を介して入力された縮小率で縮小を行わせる手順、または地図上における所定範囲を、前記入力装置(4)を介して入力された拡大率で拡大を行わせる手順、
前記縮小、または拡大を行わせる手順の結果を前記出力装置(4)へ出力させる手順、
を実行させること、を特徴とする要約地図生成プログラム。
【請求項７】
前記部分拡大縮小手順は、前記デフォルメ手順の後に実行することを特徴とする請求項６に記載の要約地図生成プログラム。
【請求項８】
前記所定部分は、地図上における空白部分であることを特徴とする請求項７に記載の要約地図生成プログラム。
【請求項９】
前記部分拡大縮小手順は、前記デフォルメ手順の後に実行することを特徴とする請求項６に記載の要約地図生成プログラム。
【請求項１０】
前記所定部分は、デフォルメ処理の結果、空白部分が生じる地図上における部分であることを特徴とする請求項９に記載の要約地図生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、詳細な地図データを簡略することによって要約地図を生成するプログラムに関する。
【背景技術】
【０００２】
従来、ユーザ要求に応じて検索された地図データから、案内目的に伴い、重要度の低い要素を間引いて必要な道路やランドマークなどの要素を抽出し、ユーザにとって見やすく、かつ分かりやすい形状に加工する地図の要約技術がある。このような要約技術では、道路の直交・直進化を基本とする様々なデフォルメ方法が用いられている。
【０００３】
道路地図の端点と屈曲点とを含むノードを初期配置として設定し、道路長の保存を示す第一の項と、道路の直交化を示す第二の項と、道路の直進化を示す第三の項とからなる評価関数に基づいてノードを再配置する最適化処理ループを該評価関数の収束条件が満足されるまで繰り返す直交・直進化処理を実行するデフォルメ方法が提示されている（例えば、特許文献１参照）。
【０００４】
また、記載内容が取捨選択されて簡素化され、かつ道路が直進化されるとともに、交差点では、直交化されることにより、見やすい地図表示を可能としたカーナビゲーション装置が提示されている（例えば、特許文献２参照）。
【特許文献１】特開２００４−１３９４８５号公報
【特許文献２】特開２００４−３４７０２０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来方法によって、検索地図から要約地図を生成する場合の直交・直進化処理では、例えば、検索地図上で道路と接していない短い道路や鉄道などといった互いに分離している要素については、それぞれ独立に直交・直進化処理が行われてしまい、結果として、それぞれの要素の方向が揃わない、といった問題があった。
また、直交・直進化処理は多変数関数を用いた最適化処理を行っているが、処理の中で局所解に陥る可能性があり、このような局所解に陥った場合には、直交・直進化処理が完了せずに処理が終了してしまうため、生成された地図がユーザに対してデフォルメ不足という印象を与えてしまう、といった問題があった。
さらに、例えば、多数並行している線路の一部を間引いたために駅と道路が離れている場合、広域地図で細道路を間引いたために道路同士が離れている場合など、道路が疎となっている場合に要約地図を生成すると、要素同士の間に不自然な空白が残るといった問題があり、逆に重要なランドマークなどが集中している場合には、要素同士が過密のまま改善されない、といった問題があった。
【０００６】
本発明は、このような背景に鑑みてなされたものであり、分離した要素間において直交・直進化処理を行った結果においても、それぞれの要素の方向が揃うことを第１の目的とした。
また、本発明は、最適化処理における局所解を回避し、直交・直進化処理を完了する確率を高めることを第２の目的とした。
また、本発明は、道路形状やランドマークなどの粗密性から生じる要素間に残る不自然な空白部分や、過密部分をなくし、視覚的にまとまった要約地図の生成を可能とすることを第３の目的とした。
【課題を解決するための手段】
【０００７】
前記の課題を解決するため、本発明では、入力を行う入力装置と、演算処理を行う演算装置と、出力を行う出力装置を備えたコンピュータに、地図形状を簡略化するデフォルメ処理を行わせ、前記デフォルメ処理は、評価関数による最適化処理に基づいて道路地図の端点、および屈曲点であるノードを再配置する直交・直進化処理を含む要約地図を生成させる要約地図生成プログラムにおいて、前記演算装置に、補助線の生成処理を行わせる手順、前記最適化処理が終了した後、前記評価関数の関数系を変化させて、再び最適化処理を行う手順、地図上における所定範囲を、前記入力手段を介して入力された縮小率で縮小を行わせる手順、または拡大率で拡大を行わせる手順をコンピュータに実行させることを特徴とする要約地図生成プログラムを提供する。
【発明の効果】
【０００８】
本発明によれば、分離した要素間を補助線で接続して直交・直進化処理を行うため、それぞれの要素の方向を揃えることが可能となる。また、最適化処理における局所解を回避し、直交・直進化処理を完了する確率を高めることが可能となる。さらに、道路形状やランドマークの粗密性から生じる要素間に残る不自然な空白部分や、過密部分をなくし、視覚的にまとまった要約地図の生成が可能となる。
【発明を実施するための最良の形態】
【０００９】
図１は、要約地図生成システムの構成を示すブロック図である。
要約地図生成システムは、要約地図の生成を行う要約地図生成装置１（演算装置）、道路形状などの地図情報が格納されている地図データベース（ＤＢ）２、地図上におけるランドマークの情報が格納されているランドマークデータベース（ＤＢ）３、情報の入力および出力を行う入出力部（入力装置、出力装置）４を含んで構成される。なお、地図ＤＢ２とランドマークＤＢ３は、同一のデータベース上に構築しても構わない。
【００１０】
さらに、要約地図生成装置１は、地図ＤＢ２に格納されている地図データとランドマークＤＢ３に格納されているランドマークデータを検索、取得する地図検索部１１、地図上の空白部分や過密部分を縮小、または拡大する部分拡大縮小処理部１２、情報を記憶する記憶部１３、地図上のレイヤを選択することによって、縮尺に応じた地図上のオブジェクトを選択するオブジェクト選択部１４、ランドマークなどを道路変形に合わせて対応する位置にマッピングさせるモーフィング処理部１５、部分拡大縮小処理が適切であったか否かを判定する判定部１６、地図データに対して、簡略化などの処理を実行することによって要約地図の生成を行うデフォルメ処理部１７を含んで構成される。
【００１１】
デフォルメ処理部１７は、多数の屈曲点で表現されている道路形状の屈曲点を間引くことによって、道路を直線化する直線化処理部１７１、交差点などにおいて直交していない道路や道なりに曲がっている道路を直交・直進化させる直交・直進化処理部１７２、道路が水平・垂直となるように座標回転する水平・垂直化処理部１７３、デフォルメ処理の処理回数が予め入力されたループ回数より小さいか否かを判定するループ判定部１７４、入力部を介して入力された情報を基に補助線を生成、または削除などの処理を行う補助線処理部１７５を含んで構成される。
【００１２】
なお、図１に示した要約地図生成装置１は、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ハードディスクドライブ、入出力インターフェースなどを含んで構成されるコンピュータを用いて具現され、要約地図生成装置１の各部は、このコンピュータのハードディスクドライブに格納されたプログラムをＲＡＭに展開し、ＣＰＵが実行することで具現され、地図ＤＢ２、ランドマークＤＢ３は、ハードディスクドライブの所定の領域を割り当てることで具現される。なお、本実施形態では、要約地図生成装置１、地図ＤＢ２、およびランドマークＤＢ３は別体となっているが、一体化してもよい。
【００１３】
（第１実施形態）
図２は、第１実施形態にかかる要約地図生成の処理の流れを示すフローである。
図１を参照しつつ、図２に沿って、要約地図生成の流れを説明する。
まず、検索条件が、入出力部４を介して、地図検索部１１に入力されることによって設定される（Ｓ１）。ここで、入力される検索条件としては、例えば、名称、電話番号の入力、またはカテゴリメニューから検索される目的地情報、名称の入力、または路線メニューから検索することによって入力される駅情報、住所、郵便番号の入力、または住所メニューから検索する住所情報、直接入力やＧＰＳ（Global Positioning System）から取得する緯度経度情報、などがある。
【００１４】
次に、ステップＳ１で入力された検索条件を基に、地図検索部１１が地図ＤＢ２に予め格納されている地図データを検索し、目的とする地図データを取得する（Ｓ２）。
さらに、地図検索部１１は、ステップＳ２で取得した地図データを基に、ランドマークＤＢ３からランドマークデータを検索、取得する（Ｓ３）。
次に、地図検索部１１は、入出力部４にステップＳ２で取得した地図データを送信し、入出力部４は、取得した地図データを表示することによって、検索地図の表示を行う（Ｓ４）。
【００１５】
次に、入出力部４が、要約地図の生成範囲を選択することによって、要約地図の生成範囲が設定される（Ｓ５）。具体的には、入出力部４に表示されている地図を、マウスなどで範囲指定することで、要約地図の生成範囲が設定される。そして、入出力部４が、記憶部１３に指定した要約地図の生成範囲の情報、例えば地図データ中における座標などを送り、記憶部１３は、設定した要約地図の生成範囲の情報を記憶する（Ｓ６）。
次に、生成範囲を設定された地図データは、オブジェクト選択部１４に送られ、オブジェクトの選択が実行される（Ｓ７）。具体的には、地図データにおけるレイヤの選択が行われる。例えば、小さな縮尺のレイヤ上では細かい家屋などのオブジェクトがあり、大きな縮尺のレイヤ上では大きなランドマークなどのオブジェクトのみというように、地図データにおける家屋などを表すオブジェクトは、各縮尺に応じたレイヤ上にのっている。オブジェクト選択部１４が縮尺に応じたレイヤを選択することによって、オブジェクトの選択が行われる。
【００１６】
次に、レイヤを選択された地図データは、デフォルメ処理部１７に送られ、デフォルメ処理が実行される（Ｓ８）。詳細は、図３を参照して説明する。
デフォルメ処理された地図データは、モーフィング処理部１５へ送られる。そして、モーフィング処理部１５は、送られた地図データに対し、モーフィング処理を実行する（Ｓ９）。具体的には、ランドマークなどが道路変形に合わせて対応する位置にマッピングされるなどの処理が行われる。
このようにして、モーフィング処理された地図データは、入出力部４へ送られ、入出力部４は、送られた地図データを表示することによって、生成した要約地図を表示する（Ｓ１０）。
【００１７】
次に、入出力部４に表示されている地図をマウスなどで範囲指定することで、部分拡大縮小範囲の設定が行われる（Ｓ１１）。具体的には、入出力部４に表示されている地図上の広すぎる空白部などをマウスなどで、範囲指定することで後記する部分拡大縮小範囲が設定される。
次に、部分拡大縮小率の設定が、入出力部４を介して、部分拡大縮小処理部１２に入力されることによって実行される（Ｓ１２）。
そして、入出力部４は、設定された部分拡大縮小範囲の情報、例えば地図データ中における座標などを記憶部１３に送り、記憶部１３は、設定した部分拡大縮小範囲の情報を記憶する（Ｓ１３）。
そして、部分拡大縮小処理部１２は、送られた地図データに対して、記憶部１３から取得した部分拡大縮小範囲の情報を基に、部分拡大縮小処理を実行する（Ｓ１４）。詳細は、図１３、および図１４を参照して後記する。
部分拡大縮小処理された地図データは、入出力部４へ送られ、入出力部４は、送られた地図データ、すなわち部分拡大縮小処理の結果を表示する（Ｓ１５）。
次に、例えばユーザが、ステップＳ１５で表示された部分拡大縮小処理の結果から、部分拡大縮小処理の結果が適切だったか否か、すなわち後記するように、要約地図上の不自然な空白部分や過密部分が適度な大きさの空白となっているか否かなどの判定を行い、その結果が入出力部４を介して、判定部１６へ入力される。判定部１６は、入力された情報から、部分拡大縮小が適切だったか否かを判定する（Ｓ１６）。判定部１６が部分拡大縮小が適切ではないと判定した場合（Ｓ１６→Ｎｏ）、ステップＳ１１に処理を戻す。適切な部分拡大縮小であったと判定部１６が判定した場合（Ｓ１６→Ｙｅｓ）、処理を終了する。
【００１８】
なお、本実施形態において、ステップＳ１１からステップＳ１５の処理は、ステップＳ８からステップＳ１０の任意の処理の間において処理されてもよい。この場合、ステップＳ１６の判定処理でＮｏが判定された場合、処理はステップＳ１１の処理へ戻る。
【００１９】
なお、ステップＳ１０より前にステップＳ１１からステップＳ１５が実施される場合に、ステップＳ１０は省略され、ステップＳ１５で要約地図と部分拡大縮小処理の結果を同時に表示してもよい。また、ステップＳ１１とステップＳ１２の順番は、どちらが先であっても構わない。さらに、ステップＳ１１では、前回の設定値を部分拡大縮小範囲の初期値に設定しておいてもよい。ステップＳ１２も同様に、前回の設定値、または予め設定しておいたデフォルト値を部分拡大縮小率の初期値に設定しておいてもよい。これより、部分拡大縮小率、または部分拡大縮小範囲のどちらか一方を変更して、部分拡大縮小処理を再度実行することも可能である。
【００２０】
図３は、図２のデフォルメ処理における処理の流れを示すフローである。
図１を参照しつつ、図３を参照してデフォルメ処理の流れを説明する。
まず、入出力部４を介して、ループ判定部１７４にループ回数が入力される（Ｓ８１）。ここで、ループ回数は、ユーザが入力した値を使用してもよいが、環境設定などの外部ファイルにより設定されている値、またはプログラムで設定されている値を使用してもよい。
次に、補助線処理部１７５が図２のステップＳ６で記憶した設定した要約地図の生成範囲の情報を記憶部１３から取得し、この情報を基に補助線生成の処理が行われる（Ｓ８２）。補助線生成の処理の詳細は、図４から図８を参照して後記する。
そして、入出力部４は、地図データ中における座標などの補助線に関するデータを記憶部１３へ送り、記憶部１３は送られた補助線の情報を記憶する（Ｓ８３）。
次に、補助線生成の処理を実行された地図データは、直線化処理部１７１へ送られる。直線化処理部１７１は、送られた地図データに対して直線化処理を実行する（Ｓ８４）。具体的には、地図データ中において、多数の屈曲点で表現されている道路形状を、屈曲点を間引くことによって、直線化処理を実行する（詳細は、特許文献１を参照）。
【００２１】
そして、直線化処理を実行された地図データは、直交・直進化処理部１７２へ送られ、直交・直進化処理部１７２は、送られた地図データと、記憶部１３から取得した補助線に関するデータを基に直交・直進化処理を実行する（Ｓ８５）。詳細は、図４から図１２を参照して後記する。
【００２２】
次に、直交・直進化処理部１７２は、記憶部１３に直交・直進化処理を実行した地図データを送り、記憶部１３は直交・直進化処理の結果を記憶する（Ｓ８６）。なお、ここで記憶した地図データは、後記する履歴表示で用いる。
直交・直進化処理を実行された地図データは、水平・垂直化処理部１７３へ送られ、水平・垂直化処理部１７３は、送られた地図データに対して、水平・垂直化処理を実行する（Ｓ８７）。具体的には、道路がなるべく水平・垂直になるよう座標回転などを行う（詳細は、特許文献１を参照）。
そして、ループ判定部１７４は、現時点でのデフォルメ処理の処理回数をカウントし、その処理回数がステップＳ８１で入力されたループ回数以上であるか否かを判定する（Ｓ８８）。ループ判定部１７４が、ループ回数が現時点の処理回数より小さいと判定した場合（Ｓ８８→Ｎｏ）、ステップＳ８２の処理へ戻る。ループ判定部１７４が、ループ回数が現時点の処理回数以上であると判定したとき（Ｓ８８→Ｙｅｓ）、入出力部４は、記憶部１３から直交・直進化処理の結果を取得し、これらを履歴として表示する（Ｓ８９）。詳細は、図１２を参照して後記する。そして、デフォルメ処理サブルーチンを終了し、図２のステップＳ９のモーフィング処理へ進む。
【００２３】
なお、本実施形態では、ステップＳ８８の処理をステップＳ８７の次に実行しているが、これに限らずステップＳ８５の処理の次に行わせ、ループ回数が現時点の処理回数より小さい場合（Ｓ８８→Ｎｏ）は、ステップＳ８５の処理に戻らせてもよい。
【００２４】
次に、図１、図２、図３を参照しつつ図４から図８を参照して、補助線生成の例を説明する。
図４は、直交・直進化処理における比較例を示す図であり、図４（ａ）は、要約地図生成前の検索地図の例を示す図であり、図４（ｂ）は、要約地図の例を示す図である。
図４の（ａ）に示すように、例えば道路のオブジェクト４０１（第１のオブジェクト）と鉄道のオブジェクト４０２（第２のオブジェクト）とが互いに分離したオブジェクトとして、地図データ中に存在している場合、これらのオブジェクトに対し、直交・直進化処理を行うと、道路のオブジェクト４０１と鉄道のオブジェクト４０２とがそれぞれ独立に直交・直進化されてしまうため、図４の（ｂ）に示すように、鉄道のオブジェクト４０２が、直交・直進化処理された道路のオブジェクト４０３に対して傾いた状態で直交・直進化されてしまうことがある。この結果、見づらい要約地図となってしまう、といった問題があった。
直交・直進化処理の詳細は、図１０を参照して後記する。
【００２５】
図５は、本実施形態にかかる補助線生成と、生成した補助線を用いた要約地図の例を示す図であり、図５（ａ）は補助線生成の例を示した図であり、図５（ｂ）は、生成した補助線を用いた要約地図の例を示す図である。
図５の（ａ）に示すように、地図データ中において、５０１は道路のオブジェクトを示し、５０２は鉄道のオブジェクトを示す。５０３は、ステップＳ５の要約地図の生成範囲の設定による領域境界線である。領域境界線とは、例えばマウスなどで範囲指定を行ったときの範囲を示す線のことである。領域境界線の地図データ中における座標などといった情報は、ステップＳ６において、記憶部１３に記憶される。
【００２６】
この領域境界線は、直交・直進化処理において、分離しているオブジェクトとオブジェクトをつなぐ補助線の役割を有している。すなわち、図５の（ａ）のように、離れている道路のオブジェクト５０１と鉄道のオブジェクト５０２を、領域境界線、すなわち補助線５０３によって接続することによって、道路のオブジェクト５０１と鉄道のオブジェクト５０２を一時的に一体化させることが可能となる。このため、道路のオブジェクト５０１と鉄道のオブジェクト５０２とを、互いに接続した一連のオブジェクトとして直交・直進化処理の対象とすることが可能となる。その結果、図５の（ｂ）における直交・直進化処理された道路のオブジェクト５０４と直交・直進化処理された鉄道のオブジェクト５０５の方向を揃えることが可能となり、視覚的に良好な要約地図の生成が可能となる。なお、補助線５０３は、これらのオブジェクトとは別のレイヤとすることで、直交・直進化処理後、補助線５０３を容易に消去することができる。また、本実施形態において、補助線５０３は矩形であるが、これに限らず多角形状、円形状などとしてもよい。さらに、本実施形態では、２種類のオブジェクトを補助線によって接続しているが、これに限らず、３種類以上のオブジェクトを接続してもよい。
【００２７】
図６は、本実施形態における補助線生成の一変形例を示す図であり、図６（ａ）は、本変形例における補助線生成の例を示す図であり、図６（ｂ）は、本変形例において生成した補助線を用いた要約地図の例を示す図である。
図６の（ａ）に示すように、補助線６０３，６０４をユーザが入出力部４を介して引くことも可能である。この場合も、図５と同様に、互いに分離している道路のオブジェクト６０１と鉄道のオブジェクト６０２を補助線６０３，６０４によって、一時的に一体化することが可能となる。結果、図６の（ｂ）に示すように、直交・直進化された道路のオブジェクト６０５と共に鉄道のオブジェクト６０６を直交・直進化することが可能となり、これら２種類のオブジェクトの方向を揃えることが可能となる。なお、本変形例では、補助線は２本引かれたが、１本とすることも可能であるし、３本以上とすることも可能である。また、本変形例では、２種類のオブジェクトを補助線によって接続しているが、これに限らず、３種類以上のオブジェクトを接続してもよい。
【００２８】
図７は、本実施形態における直交・直進化処理の一変形例を示す図であり、図７（ａ）は、図５に示した補助線生成の例を示す図であり、図７（ｂ）は、本変形例における補助線生成の例を示す図である。
図７の（ａ）に示すように、補助線の内側に、道路のオブジェクト７０１とも鉄道のオブジェクト７０２とも接続していないオブジェクト７０３が存在している場合、このオブジェクト７０３は、補助線７０４によっても道路のオブジェクト７０１とも鉄道のオブジェクト７０２とも一体化することができず、結果、オブジェクト７０３には、独立に直交・直進化処理が行われるため、道路のオブジェクト７０１、鉄道のオブジェクト７０２との方向が異なってしまう可能性がある。
このような場合、図７の（ｂ）に示すように、補助線７０５をオブジェクト７０３にかかるように、さらにもう１本加えることによって、オブジェクト７０３をオブジェクト７０１，７０２と一時的に一体化することが可能となる。この処理によって、オブジェクト７０３を、オブジェクト７０１，７０２と互いに接続した一連のオブジェクトとして、直交・直進化処理を適用することが可能となり、これらのオブジェクトの方向を揃えることが可能となる。結果、視覚的に良好な要約地図の生成が可能となる。なお、この補助線７０５は、ユーザが入出力部４を介して追加してもよいし，補助線処理部１７５が、自動的に加えてもよい。補助線処理部１７５が、補助線７０５を自動的に追加する際は、補助線処理部１７５が、最初から補助線７０５を追加するように設定してもよいし、補助線処理部１７５が、補助線７０４に触れていないオブジェクトが存在するか否かを検索し、存在した場合に補助線７０５を追加するようにしてもよい。なお、補助線は、例えば格子状にするなど、何本追加してもよい。また、本変形例では、３種類のオブジェクトを補助線によって接続しているが、これに限らず、４種類以上のオブジェクトを接続してもよい。
【００２９】
図８は、補助線処理部１７５が、補助線追加を自動的に行う際の処理の例を説明する図であり、図８（ａ）は、補助線と補助線から分離しているオブジェクトが存在する例を示す図、図８（ｂ）は、（ａ）に示す補助線に対し、２本の補助線を追加した例を示す図、図８（ｃ）は、追加した補助線とオブジェクトとの交点を示した例を示す図であり、図８（ｄ）は、オブジェクトと交わらない補助線を削除した例を示す図である。
図８の（ａ）に示すように、補助線８００と交わらないオブジェクト８０１が存在していたとする。ここで、補助線処理部１７５は、図８の（ｂ）に示すように、追加の補助線８０２，８０３を引く。次に、補助線処理部１７５は、図８の（ｃ）に示すように、追加した補助線８０２，８０３とオブジェクト８０１との交点８０５を算出し、追加した補助線がオブジェクト８０１との交点をもつか否かを判定する。この場合、オブジェクト８０１は、補助線処理部１７５によって、補助線８０３と交点をもつが、補助線８０２とは交点を持たないと判定される。その結果、図８の（ｄ）に示すように、補助線処理部１７５は、オブジェクト８０１と交点を持たない補助線８０２を削除する処理を行う。なお、この処理は、必須ではない。
このような処理を行うことで、補助線の増加による処理の負担を軽減することが可能となる。
【００３０】
次に、図１、図３を参照しつつ、図９から図１２を参照して、直交・直進化処理を説明する。
図９は、直交・直進化処理の比較例を示す図であり、図９（ａ）は、直交・直進化処理を行う前の検索地図の例を示す図であり、図９（ｂ）は、直交・直進化処理を行った後の要約地図の例を示す図である。
直交・直進化処理では、多変数関数を用いた最適化処理が行われる。本比較例では、例えば式（１）、式（２）に示すようなエネルギ関数を用いて、最適化処理が行われるが、これに限らず他の多変数関数による最適化処理を用いてもよい。
【００３１】
【数１】
2006276785.tif 000003
【００３２】
【数２】
2006276785.tif 000004
【００３３】
ここで、図１０を参照して、式（１）、式（２）における記号の説明をする。
図１０は、式（１）、式（２）における記号を説明する図であり、図１０（ａ）は、ｖijとθi→j→kとを説明する図、図１０（ｂ）は、Θi,j,kを説明する図である。
ここで、ｉ，ｊ，ｋ，ｌ，ｍは、交差点、屈曲点、および端点などのノードごとに付されたノードＩＤであり、ｋabcは、定数である。また、図１０の（ａ）に示すように、ｖijは、ノードｉ，ｊを結ぶ辺（道路）の長さであり、ｕijは、ノードｉ，ｊを結ぶ辺（道路）の長さの理想長である。θi→j→kは、ノードｉ，ｊ，ｋの右側のなす角であり、φi→j→kは、ノードＩＤｉ，ｊ，ｋの右側のなす角の理想角である。θi→j→k，φi→j→kは、２つの辺のなす角である。また、図１０の（ｂ）に示すように、Θi,j,kは、ノードｉ，ｊ，ｋの右側のなす角である。Θi,j,kは、１つの辺をはさんだ２つの辺のなす角である。そして、Δθは、量子化角度を表し、Δθ＝π／２，π／４といった値を設定する。[ｘ]は、ｘを超えない最大の整数を表す。
【００３４】
式（１）の第１項は、道路長を理想長のまま保存しようとする項であり、第２項は、道路間のなす角度を量子化する項であり、第３項は、道なりの道路を直線化する項である。
本比較例では、例えば準ニュートン法を用いて式（１）を反復計算することによって、極小解を求め、最適解を算出する、すなわち、式（１）のエネルギ関数の値が小さくなるような各ノードの配置を算出する。具体的には、予め入出力部４を介して、入力しておいた反復回数に従って計算を行い、式（１）のエネルギ関数の値が最も小さくなるような各ノードの配置を算出する。
しかし、多変数関数を用いた最適化処理は、しばしば局所解に陥ることがある。例えば、図９の（ａ）に示すような道路形状を有する地図データに対し、直交・直進化処理、すなわち最適化処理を行った結果、最適化処理が局所解に陥ってしまった場合、図９の（ｂ）に示すように、完全な直交・直進化が行われない状態で、処理が終了してしまい、デフォルメ不足の印象を与える場合がある、といった問題があった。
【００３５】
そこで、本実施形態では、直交・直進化処理部１７２が最適化処理を反復回数行った後に再び最適化処理を反復回数行うことを特徴とする。
この際、直交・直進化処理部１７２は、反復回数行った後の各ノードの配置を式（１）におけるｕij，φi→j→kに代入することによって、適用するエネルギ関数を前回の最適化処理におけるエネルギ関数とは、別のエネルギ関数系とする。すなわち、局所解の形状を変化させる。そして、この新たな関数系を用いて、再度ノードの初期配置から最適化処理を反復回数行うことによって、極小解を求める。
このような処理を行うことで、エネルギ関数の形状を変化させ、ノードの配置が極小解に到達する確率をより高めることができる。
【００３６】
図１１は、本実施形態における最適化処理を行った例を示す図であり、図１１（ａ）は、１回目の最適化処理の結果を示す例を示す図であり、図１１（ｂ）は、１回目の結果を、エネルギ関数に代入した２回目の最適化処理の結果の例を示す図である。
図１１の（ａ）に示すように、１回目の最適化処理では局所解に陥ってしまい、十分なデフォルメが得られていないが、図１１の（ｂ）に示すように、２回目の最適化処理では、１回目の最適化処理の結果をエネルギ関数の理想値に代入することによって、エネルギ関数の関数系を変化させ、極小解に到達していることがわかる。
関数系を変化させる回数は、本実施形態ではステップＳ８１において入力されたループ回数によって決定されるが、これに限らずシステムとして予めループ回数を決めておいてもよい。
【００３７】
図１２は、複数回、関数系を変化させて行った各回の最適化処理の結果を履歴として表示した画面例である。
本実施形態における最適化処理では、前に実行した最適化処理の結果の方が、後に行った最適化処理の結果よりも、望ましい結果となっていることがある。そこで、本実施形態では、図１２に示すように、入出力部４が、それぞれの最適化処理の結果１２０１から１２０６を履歴として表示する。このような方法を行うことにより、エネルギ関数における極小解に最も近いノードの配置をユーザが入出力部４を介して選択することが可能となる。本実施形態では、ステップＳ８６において、記憶部１３が直交・直進化処理の結果を記憶し、そしてステップＳ８９において、図１２のような履歴が表示されたとすると、最適化処理の結果１２０３を、極小解に近い結果として、ユーザが入出力部４を介して選択する。なお、この処理は必須ではない。
【００３８】
次に、図１、図２を参照しつつ、図１３から図１６を用いて、部分拡大縮小処理の例を説明する。
次に、図１３は、本発明にかかる比較例を示す図であり、図１３（ａ）は、デフォルメ処理前の検索地図の例を示す図であり、図１３（ｂ）は、デフォルメ処理後の要約地図の例を示す図である。
図１３の（ａ）に示すように、デフォルメ処理前の検索地図において、例えば駅に入る路線が多数存在するとする。この場合、例えば主要な路線は優先度が高いなどの優先順位が付され、優先度の低い路線は削除されるといった処理が行われる場合がある。このような処理に加えて、さらに直線化処理、直交・直進化処理、水平・垂直化処理といったデフォルメ処理が実行された場合、図１３の（ｂ）における空白部１３０１のように、広い空白部分が生じてしまう。
【００３９】
図１４は、本実施形態にかかる部分拡大縮小処理範囲の指定方法の例を示す図であり、図１４（ａ）は、部分拡大縮小範囲の指定を示す図であり、図１４（ｂ）は、部分拡大縮小処理の結果を示す図である。
図１４の（ａ）に示すように、デフォルメ処理の結果生じた空白部分を、入出力部４を介して、縮小したい（詰めたい）空白部分を範囲指定する。そして、範囲指定した領域境界線１４０１の座標などのデータは、まず記憶部１３に送られ、さらに部分拡大縮小処理部１２が範囲指定した領域境界線の座標などのデータを記憶部１３から取得し、ステップＳ１２において設定された、部分拡大縮小率に従って部分拡大縮小処理部１２が、範囲指定した領域の一定方向の縮小を実行する。部分拡大縮小処理を実行した結果、図１４の（ｂ）に示すように、縮小された空白部１４０２が生じる。
【００４０】
このような処理を行うことによって、広すぎる空白部分を縮小することが可能となり、視覚的に良好な要約地図を生成することが可能となる。なお、本実施形態では、部分拡大縮小処理は、広い空白部を縮小する処理を行っているが、これに限らず、例えばランドマークなどが過密に集中し、利用者にとって分かりづらくなっている部分を拡大して（分散させて）分かりやすくする処理としてもよい。
また、本実施形態においては、設定した領域境界線の一定方向の縮小を前提としたが、これに限らず、例えばステップＳ１２の部分拡大縮小率の設定において、領域境界線の縦・横の縮小率、または拡大率を設定することによって、空白部分全体の縮小、または拡大が可能となる。
【００４１】
（第２実施形態）
図１５は、第２実施形態にかかる要約地図作成の処理の流れを示すフローである。
第２実施形態においては、部分拡大縮小範囲の設定を、デフォルメ処理の前に行う。
図１５において、図２と共通の要素には同じ符号を付し、説明を省略する。
図１５に示すように、ステップＳ１１、ステップＳ１２、およびステップＳ１３が、ステップＳ６と、ステップＳ７の間で処理されている。また、ステップＳ１４が、ステップＳ９とステップＳ１０間で処理されている。
なお、本実施形態において、ステップＳ１１は、ステップＳ２からステップＳ８の任意の処理の間において処理されてもよい。この場合、ステップＳ１６の判定処理でＮｏが判定された場合、処理はステップＳ１１の処理へ戻る。ステップＳ１２、およびステップＳ１３は、ステップＳ１１からステップＳ８の任意の処理の間において処理されてもよく、ステップＳ１４は、ステップＳ８からステップＳ１０の任意の処理の間において処理されてもよい。また、本実施形態におけるステップＳ１０は、第１実施形態のステップＳ１５を含んでいる。すなわち、部分拡大縮小処理を行った結果と要約地図とを同時に表示している。しかし、これに限らず、部分拡大縮小処理の結果と、要約地図の表示を別の処理としてもよい。
なお、ステップＳ１１とステップＳ１２とは、この順番に限定されるものではなく、ステップＳ１１の前にステップＳ１２を処理してもよい。
さらに、ステップＳ１１では、前回の設定値を部分拡大縮小範囲の初期値に設定しておいてもよい。ステップＳ１２も同様に、前回の設定値、または予め設定しておいたデフォルト値を部分拡大縮小率の初期値に設定しておいてもよい。これより、部分拡大縮小率、または部分拡大縮小範囲のどちらか一方を変更して、部分拡大縮小処理を再度実行することも可能である。
【００４２】
図１６は、第２実施形態の部分拡大縮小範囲を指定する例を示す図であり、図１６（ａ）は、部分拡大縮小範囲の指定を示す図であり、図１６（ｂ）は、部分拡大縮小処理の結果を示す図である。
図１６の（ａ）に示すように、デフォルメ処理前に予めユーザが入出力部４を介して、大きな空白部分が生じると予想される部分１６０１を範囲指定することが可能である。そして、ステップＳ１４の部分拡大縮小処理を行った結果として、図１６の（ｂ）のように、縮小された空白部分１６０２が生成される。
なお、本実施形態では、部分拡大縮小処理は、広い空白部を縮小する処理を行っているが、これに限らず、例えばランドマークなどが過密に集中し、利用者にとって分かりづらくなっている部分を拡大して分かりやすくする処理としてもよい。
【図面の簡単な説明】
【００４３】
【図１】本発明にかかる要約地図生成システムの構成を示すブロック図である。
【図２】本発明にかかる第１実施形態の要約地図生成の処理の流れを示すフローである。
【図３】本発明にかかる第１実施形態の要約地図生成処理のデフォルメ処理における処理の流れを示すフローである。
【図４】本発明にかかる第１実施形態の要約地図生成処理の直交・直進化処理における比較例を示す図であり、図４（ａ）は、要約地図生成前の検索地図の例を示す図であり、図４（ｂ）は、要約地図の例を示す図である。
【図５】本発明にかかる第１実施形態の補助線生成と、生成した補助線を用いた要約地図の例を示す図であり、図５（ａ）は、補助線生成の例を示した図であり、図５（ｂ）は、生成した補助線を用いた要約地図の例を示す図である。
【図６】本発明にかかる第１実施形態の補助線生成の一変形例を示す図であり、図６（ａ）は、本変形例における補助線生成の例を示す図であり、図６（ｂ）は、本変形例において生成した補助線を用いた要約地図の例を示す図である。
【図７】本発明にかかる第１実施形態の直交・直進化処理の一変形例を示す図であり、図７（ａ）は、本変形例における補助線生成の例を示す図であり、図７（ｂ）は、本変形例において生成した補助線を用いた要約地図の例を示す図である。
【図８】本発明にかかる第１実施形態の補助線追加を自動的に行う際の処理の例を説明する図であり、図８（ａ）は、補助線と補助線から分離しているオブジェクトが存在する例を示す図、図８（ｂ）は、（ａ）に示す補助線に対し、２本の補助線を追加した例を示す図、図８（ｃ）は、追加した補助線とオブジェクトとの交点を示した例を示す図であり、図８（ｄ）は、オブジェクトと交わらない補助線を削除した例を示す図である。
【図９】本発明にかかる第１実施形態の直交・直進化処理の比較例を示す図であり、図９（ａ）は、直交・直進化処理を行う前の検索地図の例を示す図であり、図９（ｂ）は、直交・直進化処理を行った後の要約地図の例を示す図である。
【図１０】本発明にかかる第１実施形態の式（１）、式（２）における記号を説明する図であり、図１０（ａ）は、ｖijとθi→j→kを説明する図、図１０（ｂ）は、Θi,j,kを説明する図である。
【図１１】本発明にかかる第１実施形態の最適化処理を行った例を示す図であり、図１１（ａ）は、１回目の最適化処理の結果を示す例を示す図であり、図１１（ｂ）は、１回目の結果を、エネルギ関数に代入した２回目の最適化処理の結果の例を示す図である。
【図１２】本発明にかかる第１実施形態において複数回、関数系を変化させて行った各回の最適化処理の結果を履歴として表示した画面例である。
【図１３】本発明にかかる比較例を示す図であり、図１３（ａ）は、デフォルメ処理前の検索地図の例を示す図であり、図１３（ｂ）は、デフォルメ処理後の要約地図の例を示す図である。
【図１４】本実施形態にかかる部分拡大縮小処理範囲の指定方法の例を示す図であり、図１４（ａ）は、部分拡大縮小範囲の指定を示す図であり、図１４（ｂ）は、部分拡大縮小処理の結果を示す図である。
【図１５】本発明にかかる第２実施形態にかかる要約地図作成の処理の流れを示すフローである。
【図１６】本発明にかかる第２実施形態の部分拡大縮小範囲を指定する例を示す図であり、図１６（ａ）は、部分拡大縮小範囲の指定を示す図であり、図１６（ｂ）は、部分拡大縮小処理の結果を示す図である。
【符号の説明】
【００４４】
１      要約地図生成装置
２      地図データベース
３      ランドマークデータベース
４      入出力部
１１    地図検索部
１２    部分拡大縮小処理部
１３    記憶部
１４    オブジェクト選択部
１５    モーフィング処理部
１６    判定部
１７    デフォルメ処理部
１７１  直線化処理部
１７２  直交・直進化処理部
１７３  水平・垂直化処理部
１７４  ループ判定部
１７５  補助線処理部
【図１】
2006276785.tif 000005
【図２】
2006276785.tif 000006
【図３】
2006276785.tif 000007
【図４】
2006276785.tif 000008
【図５】
2006276785.tif 000009
【図６】
2006276785.tif 000010
【図７】
2006276785.tif 000011
【図８】
2006276785.tif 000012
【図９】
2006276785.tif 000013
【図１０】
2006276785.tif 000014
【図１１】
2006276785.tif 000015
【図１２】
2006276785.tif 000016
【図１３】
2006276785.tif 000017
【図１４】
2006276785.tif 000018
【図１５】
2006276785.tif 000019
【図１６】
2006276785.tif 000020