立体地図簡略化装置及び立体地図簡略化方法
【課題】使用者の視認性が向上するように建物データを簡略化し、かつ立体地図を保持するための記憶容量も削減可能な立体地図簡略化技術を提供する。
【解決手段】立体地図画像を構成する各要素について、当該要素の重要度を計算する重要度計算手段１２、地上に配置された要素のうち、重要度が所定の閾値よりも小さい要素について、互いに近接する要素が同じグループとなるようにグループ分けするグループ化手段１７、及び、各グループに属する要素を結合し、１つの結合要素とする要素結合手段１８を備えた。重要度の低い要素については、複数の要素を結合して１つの要素とすることによって、立体地図画像内の要素のメッシュ数を減少させることができる。従って、表示する立体地図のデータ量を削減することが可能となる。
【解決手段】立体地図画像を構成する各要素について、当該要素の重要度を計算する重要度計算手段１２、地上に配置された要素のうち、重要度が所定の閾値よりも小さい要素について、互いに近接する要素が同じグループとなるようにグループ分けするグループ化手段１７、及び、各グループに属する要素を結合し、１つの結合要素とする要素結合手段１８を備えた。重要度の低い要素については、複数の要素を結合して１つの要素とすることによって、立体地図画像内の要素のメッシュ数を減少させることができる。従って、表示する立体地図のデータ量を削減することが可能となる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元データにより表される立体地図のデータを簡略化する立体地図簡略化技術に関し、特に、簡略化による違和感の少ない立体地図簡略化技術に関する。
【背景技術】
【０００２】
近年、携帯可能なカメラや携帯電話等の情報端末にて、立体地図を表示させてナビゲーションや位置確認等を行わせる技術の研究開発が行われつつある（例えば、特許文献１，２参照）。かかる携帯可能な情報端末では、小型化・省電力化が求められる。また、無線通信により地図情報を送信する場合、リアルタイムに地図情報を携帯端末に表示させるためには、地図情報の情報量の削減が必要である。従って、簡略な構成で立体地図の表示を行うための立体地図簡略化技術が必要とされている。
【０００３】
ところで、立体地図の編集、獲得、表示には３Ｄモデルが用いられる。３Ｄモデルには、ヴォリュームモデル、ソリッドモデル、スプラインパッチ等、様々な表現方法がある。その中でも、物体の表面をポリゴンで近似する３Ｄメッシュモデル（以下「３Ｄメッシュ」という。）は、高精細なモデル、アニメーションを比較的簡単に表現できることから広く用いられている（非特許文献１参照）。
【０００４】
通常、３Ｄモデルは、メッシュ情報以外にも、属性データと呼ばれる色、材質などを表す情報が含まれている。立体地図では、テクスチャを属性として持つ３Ｄメッシュが用いられる。テクスチャは、通常は画像として与えられる。テクスチャとして与えられた画像を３Ｄメッシュに貼り付けることを「マッピング」という。テクスチャを３Ｄメッシュにマッピングすることにより、色つき３Ｄメッシュが得られる。
【０００５】
元来、３Ｄメッシュは膨大な情報量を持つことが多い。従って、この３Ｄメッシュの情報をネットワーク配信し、データベース管理し、又は高速表示する為には、データ量の削減が必要である。ここでは、データ量の削減のことを「簡略化」と呼ぶ。
【０００６】
ところで、前述の通り、立体地図に用いられる３Ｄメッシュはメッシュ情報とテクスチャ情報とを併せ持つ。そのため、それぞれの情報について簡略化を行う必要がある。通常、テクスチャ（画像）の簡略化は、解像度（画像の縦横のサイズ）を縮小することによって容易に達成することができる。しかし、３Ｄメッシュに関しては工夫が必要とされる。
【０００７】
立体地図では、ビル、家、看板などの構成要素の一つ一つが直方体や円筒などの単純な形を持つ３Ｄメッシュで構成されている。比較的狭いエリアの立体地図でも、その構成要素の数は膨大となる。そのため、データベース化、伝送、表示には多くの計算量が必要とされる。特に、ＣＰＵ（中央演算装置）の演算能力、記憶容量、ディスプレイの解像度に強い制約がある携帯端末では、そのままではデータの伝送、表示が困難である。
【０００８】
そこで、立体地図の効果的なデータ構造を提案することで、高速に立体地図を表示する方法が幾つか提案されている。
【０００９】
特許文献１では、ビル等の複数の構造物が建築されている街区を、当該街区に存在する複数の構造物の概略形状を表す１つのブロックとして形成する方法が採られている。そして、視点の位置情報と方位情報を元に、テクスチャ（画像）データに視点に応じた変形処理や明暗処理を加え、処理された画像データを、対応するブロックの表面に貼り付けてマッピングする。
【００１０】
その方法による立体地図の表示例を図８に示す。図８に示すように、立体地図の各街区は、１つ直方体ブロック１００として形成されている。各直方体ブロック１００の表面には、変形処理や明暗処理がされたテクスチャを表す画像データ１０１，１０２が貼り付けられている。直方体ブロック１００と画像データ１０１，１０２との対応関係は常に保持される。
【００１１】
また、非特許文献１には、複数のレベルで簡略化した建物形状のデータを用意し、視点からの距離に応じてレベルを設定することにより、視点からの距離に応じて簡略化した建物形状を表示する方法が記載されている。
【００１２】
図９は非特許文献１における建物データの例を示す図である。この方法では、立体地図に含まれるすべての建物ｊについて、図９のような各レベルの建物データＳｊ＝｛Ｓｊ１，…，Ｓｊ７｝を予め生成し、保存しておく。建物データは、レベルが高いほど簡略化の度合いが大きくなるように構成されている。
【００１３】
立体地図の表示時には、視点から各建物までの距離ｄｉを計算する。そして、距離ｄｉに応じてレベルを決定し、そのレベルの建物データを表示する。このとき、視点からの距離が遠いほど、高いレベルを設定する。これにより、視点近傍の建物は低レベルの建物データが選択され、視点からの距離が遠くなるほど高レベルの建物データが選択される。従って、視点からの距離が遠いほど、簡略化された建物データが表示されることになる。これにより、表示画面上にポリゴンを配置する計算量の低減が図られている。
【特許文献１】特開２００１−５９９４号公報
【特許文献２】特開平１１−２１９１０６号公報
【非特許文献１】山田方根，「仮想都市の自動生成における建物形状の作成と表示」，平成１５年１月，筑波大学大学院システム情報工学研究科 平成１５年度修士論文，［平成１７年３月２０日検索］，インターネット＜URL:http://www.sie.tsukuba.ac.jp/H15syuron/200205245.pdf＞
【非特許文献２】H. Hoppe, "Progressive meshes", ACM SIGGRAPH 1996, pp.99-108.
【発明の開示】
【発明が解決しようとする課題】
【００１４】
上記特許文献１記載の方法を用いればメッシュデータを大幅に削減することが可能である。しかしながら、各街区を直方体ブロックで近似しているため、近似度合いが非常に粗くなる。その結果、使用者における景観の視認性が低下するという問題がある。
【００１５】
また、非特許文献１の手法では、各レベルの建物データをメモリに記憶しておく必要がある。そのため、大容量の記憶装置が必要となる。特に、記憶容量の制約が大きい携帯端末などに広域の立体地図を保持することが困難である。
【００１６】
そこで、本発明の目的は、使用者の視認性が向上するように建物データを簡略化し、かつ立体地図を保持するための記憶容量も削減可能な立体地図簡略化技術を提供することにある。
【課題を解決するための手段】
【００１７】
本発明に係る立体地図簡略化装置の第１の構成は、立体地図画像を簡略化する立体地図簡略化装置において、立体地図画像を構成する各要素について、当該要素の重要度を計算する重要度計算手段；地上に配置された要素のうち、前記重要度が所定の閾値よりも小さい要素について、互いに近接する要素が同じグループとなるようにグループ分けするグループ化手段；及び、前記各グループに属する要素を結合し、１つの結合要素とする要素結合手段；を備えたことを特徴とする。
【００１８】
この構成によれば、重要度の低い要素については、複数の要素を結合して１つの要素とすることによって、立体地図画像内の要素のメッシュ数を減少させることができる。従って、表示する立体地図のデータ量を削減することが可能となる。また、携帯端末等には簡略化された立体地図のデータを送信し、又は携帯端末等の内部の記憶装置に記憶させるようにすれば、記憶容量の少ない携帯端末においても広域の立体地図データを保持することができる。更に、複数のレベルで簡略化した建物データを作成する必要がないため、立体地図の記憶容量を低減することができると共に、データの作成も容易化される。
【００１９】
また、重要度の低い要素は簡略化され、重要度の高い要素は詳細に表示されるため、使用者の視認性は損なわれず、むしろ、風景の特徴を捉えやすくなるため視認性は向上する。
【００２０】
ここで、「要素」とは、建造物、道路、標識、看板等の立体地図を構成する要素（オブジェクト、物体）をいう。各要素は、表面をポリゴンで近似する３Ｄメッシュで表現される。
【００２１】
本発明に係る立体地図簡略化装置の第２の構成は、前記第１の構成において、前記要素結合手段は、前記各グループについて、当該グループに属する各要素を地面に投影し、投影した２次元投影図形の頂点を求める投影頂点決定手段；前記２次元投影図形の凸包を求め、これを当該要素の新たな地上投影図形Ｓとする地上投影図形生成手段；前記グループに属する各要素の高さから当該グループの要素の高さの代表値を決定する高さ決定手段；及び、前記地上投影図形Ｓを前記高さの代表値だけ高さ方向に引き延ばすことにより、前記結合要素を生成する結合要素生成手段；を備えていることを特徴とする。
【００２２】
この構成により、各グループに属する要素を違和感なく結合して、結合要素を生成することができる。
【００２３】
ここで、「代表値」としては最大値や平均値等が用いられる。
【００２４】
本発明に係る立体地図簡略化装置の第２の構成は、前記第１又は２の構成において、前記重要度計算手段は、要素を構成するメッシュのうち一のメッシュに対して、当該メッシュの単位法線ベクトルと他のメッシュの単位法線ベクトルとの内積を、要素を構成するすべてのメッシュについて積算した値である面複雑性が含まれる重要度を算出することを特徴とする。
【００２５】
この構成により、看板のような複雑な形状の要素は面複雑性が大きく、通常の建物のように比較的単純な形状の要素は面複雑性が小さくなる。従って、面複雑性を指標とすることにより、建物とその他の付属構造物との区別が或る程度可能となり、重要度の決定精度が向上する。
【００２６】
本発明に係る立体地図簡略化装置の第４の構成は、立体地図の各要素に属するテクスチャ画像を簡略化する立体地図簡略化装置であって、テクスチャの原画像を複数の閉領域に分割する領域分割手段；前記各閉領域に対して代表色を決定する代表色決定手段；前記各閉領域の色を前記代表色で置き換える色置換手段；を有し、前記代表色決定手段は、当該閉領域の色ヒストグラムＨ＝｛Ｈ（Ｃ）｝（Ｃは色を表す。）を生成するヒストグラム生成手段；前記色ヒストグラムから度数のピークの集合（以下「ピーク集合」という。）Ｐ＝｛Ｐ（Ｃｊ）｝を抽出するピーク抽出手段；前記ピーク集合Ｐから、度数が大きい順で且つより度数が大きい色との色空間上の距離が所定の閾値以上となるようにｎ０個の色を選出し代表色に決定する代表色選出手段；を備えたことを特徴とする。
【００２７】
この構成により、テクスチャを減色する際に、最も多くの領域を占める色彩から代表色に決定されると共に、各代表色間の色空間距離を或る閾値以上とすることで、代表色間のコントラストをつけることができる。そのため、最適な色選択による減色でテクスチャのデータ量が削減されるとともに、減色されたテクスチャの視認性を確保することができる。
【００２８】
本発明に係る立体地図簡略化方法の第１の構成は、立体地図画像を簡略化する立体地図簡略化方法であって、立体地図画像を構成する各要素について、当該要素の重要度を計算する重要度計算ステップ；地上に配置された要素のうち、前記重要度が所定の閾値よりも小さい要素について、互いに近接する要素が同じグループとなるようにグループ分けするグループ化ステップ；及び、前記各グループに属する要素を結合し、１つの結合要素とする要素結合ステップ；を有することを特徴とする。
【００２９】
本発明に係る立体地図簡略化方法の第２の構成は、前記第１の構成において、前記要素結合ステップは、前記各グループについて、当該グループに属する各要素を地面に投影し、投影した２次元投影図形の頂点を求める投影頂点決定ステップ；前記２次元投影図形の凸包を求め、これを当該要素の新たな地上投影図形Ｓとする地上投影図形生成ステップ；前記グループに属する各要素の高さから当該グループの要素の高さの代表値を決定する高さ決定ステップ；及び、前記地上投影図形Ｓを前記高さの代表値だけ高さ方向に引き延ばすことにより、前記結合要素を生成する結合要素生成ステップ；を有することを特徴とする。
【００３０】
本発明に係る立体地図簡略化方法の第３の構成は、前記第１又は２の構成において、前記重要度計算ステップでは、要素を構成するメッシュのうち一のメッシュに対して、当該メッシュの単位法線ベクトルと他のメッシュの単位法線ベクトルとの内積を、要素を構成するすべてのメッシュについて積算した値である面複雑性が含まれる重要度を算出することを特徴とする。
【００３１】
本発明に係る立体地図簡略化方法の第４の構成は、立体地図の各要素に属するテクスチャ画像を簡略化する立体地図簡略化方法であって、テクスチャの原画像を複数の閉領域に分割する領域分割ステップ；前記各閉領域に対して代表色を決定する代表色決定ステップ；前記各閉領域の色を前記代表色で置き換える色置換ステップ；を有し、前記代表色決定ステップにおいては、当該閉領域の色ヒストグラムＨ＝｛Ｈ（Ｃ）｝（Ｃは色を表す。）を生成するヒストグラム生成ステップ；前記色ヒストグラムから度数のピークの集合（以下「ピーク集合」という。）Ｐ＝｛Ｐ（Ｃｊ）｝を抽出するピーク抽出ステップ；前記ピーク集合Ｐから、度数が大きい順で且つより度数が大きい色との色空間上の距離が所定の閾値以上となるようにｎ０個の色を選出し代表色に決定する代表色選出ステップ；を有していることを特徴とする。
【００３２】
本発明に係るプログラムは、前記第１乃至４の何れか一の構成の立体地図簡略化方法を実行するプログラム。
【発明の効果】
【００３３】
以上のように、本発明によれば、重要度の低い要素を結合することによって、立体地図画像内の要素のメッシュ数を減少させ建物データを簡略化し、データ量の削減を図ることが可能となる。また、記憶容量の少ない携帯端末においても広域の立体地図データを保持することができる。更に、複数のレベルで簡略化した建物データを作成する必要がないため、立体地図の記憶容量を低減することができると共に、データの作成も容易化される。
【００３４】
また、重要度の低い要素を簡略化し、重要度の高い要素を詳細に表示することにより、風景の特徴を捉えやすくなり、使用者の視認性を向上させることができる。
【００３５】
更に、要素のテクスチャのデータについては、最適な色選択による減色でテクスチャのデータ量が削減され、減色されたテクスチャの視認性を確保することができる。
【発明を実施するための最良の形態】
【００３６】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００３７】
図１は、本発明の実施例１に係る立体地図簡略化装置の構成を表すブロック図である。実施例１に係る立体地図簡略化装置は、その構成として、メッシュ記憶手段１、テクスチャ記憶手段２、メッシュ簡略化モジュール３、簡略化メッシュ記憶手段４、テクスチャ簡略化モジュール５、簡略化テクスチャ記憶手段６、テクスチャ・マッピング手段７、景観データ記憶手段８、及び出力手段９を備えている。
【００３８】
メッシュ記憶手段１は、詳細な立体地図の各要素（ポリゴン）をメッシュ情報として記憶する。テクスチャ記憶手段２は、メッシュ記憶手段１に記憶された立体地図の各要素の表面に貼り付ける画像（以下「テクスチャ」という。）情報を記憶する。尚、これら詳細な立体地図のメッシュ情報とテクスチャ情報は、予め与えられているものとする。
【００３９】
メッシュ簡略化モジュール３は、メッシュ記憶手段１に記憶されたメッシュ情報（以下「詳細メッシュ」という。）を簡略化して簡略化メッシュを生成する。簡略化メッシュ記憶手段４は、メッシュ簡略化モジュール３が生成する簡略化メッシュを一時的に記憶する。
【００４０】
テクスチャ簡略化モジュール５は、テクスチャ記憶手段２に記憶されたテクスチャ情報（以下「詳細テクスチャ」という。）を簡略化して簡略化テクスチャを生成する。簡略化テクスチャ記憶手段６は、テクスチャ簡略化モジュール５が生成する簡略化テクスチャを一時的に記憶する。
【００４１】
テクスチャ・マッピング手段７は、簡略化メッシュに簡略化テクスチャをテクスチャ・マッピングし、所定の視点位置及び視方向からの簡略化された立体地図データ（以下「景観データ」という。）を合成する。景観データ記憶手段８は、テクスチャ・マッピング手段７により合成された景観データを記憶する。出力手段９は、景観データ記憶手段８に記憶された景観データを出力する。出力手段９としては、携帯端末に対して景観データを送信する送信装置や、景観データを携帯端末のディスプレイ上に表示する表示装置等が使用される。
【００４２】
ここで、上記メッシュ簡略化モジュール３は、要素抽出手段１１、重要度計算手段１２、要素分類手段１３、重要要素記憶手段１４、細瑣要素記憶手段１５、幾何情報簡略化手段１６、グループ化手段１７、要素結合手段１８、及び簡略化メッシュ出力手段１９を備えている。
【００４３】
要素抽出手段１１は、メッシュ記憶手段１から順次各要素を読み出す。重要度計算手段１２は、要素抽出手段１１により読み出された各要素について、当該要素の重要度を計算する。重要度の計算方法に関しては後述する。
【００４４】
要素分類手段１３は、要素抽出手段１１により読み出された各要素について、その当該要素の重要度に基づいて、当該要素を重要要素と細瑣要素とに分類する。この分類方法に関しては後述する。要素分類手段１３により重要要素に分類された要素は、重要要素記憶手段１４に一時保存される。また、細瑣要素に分類された要素は、細瑣要素記憶手段１５に記憶される。尚、「重要要素」とは、立体地図を概観した際に目に付きやすい要素又は目標物（ランドマーク）となり得る要素をいう。「細瑣要素」とは、重要要素ではない要素をいう。
【００４５】
幾何情報簡略化手段１６は、細瑣要素記憶手段１５に格納された細瑣要素について、不要な細瑣要素を削除し又は不要なメッシュを削減する。グループ化手段１７は、細瑣要素に含まれる近接する構造物が同じグループとなるようにグループ分けを行う。要素結合手段１８は、グループ化された各グループに属する細瑣要素を結合し、一つの結合要素とする。簡略化メッシュ出力手段１９は、各重要要素と各細瑣要素（又はグループ内で結合された結合要素）とを簡略化メッシュ記憶手段４へ出力する。
【００４６】
また、上記要素結合手段１８は、投影頂点決定手段２１、投影図形生成手段２２、高さ決定手段２３、及び結合要素生成手段２４を備えている。
【００４７】
投影頂点決定手段２１は、各グループについて、当該グループに属する各オブジェクトを地面に投影し、投影した二次元投影図形の頂点を計算する。投影図形生成手段２２は、計算された二次元投影図形の凸包を求め、これを当該要素の新たな地上投影図形Ｓとする。高さ決定手段２３は、グループに属する各要素の高さから当該グループの要素の高さの代表値ｈを決定する。結合要素生成手段２４は、地上投影図形Ｓを上記高さの代表値ｈだけ高さ方向に引き延ばすことにより、当該グループ内の各細瑣要素が結合して成る結合要素を生成する。
【００４８】
一方、上記テクスチャ簡略化モジュール５は、及び重要テクスチャ生成手段２５を備えている。これらは、それぞれ、テクスチャ記憶手段２に記憶された詳細テクスチャに基づき、重要テクスチャ及び細瑣テクスチャを生成する。
【００４９】
ここで、「重要テクスチャ」とは、重要要素のテクスチャ、及び細瑣要素のテクスチャうち視認されやすくランドマークや情報表示となり得るテクスチャをいう。「細瑣テクスチャ」とは、重要テクスチャ以外の各要素のテクスチャをいう。
【００５０】
重要テクスチャ生成手段２５は、領域分割手段２７、代表色決定手段２８、及び色置換手段２９を備えている。
【００５１】
領域分割手段２７は、詳細テクスチャの原画像を複数の閉領域に分割する。代表色決定手段２８は、各閉領域に対してその閉領域内の代表色を決定する。色置換手段２９は、各閉領域の色を上記の代表色で置き換える。
【００５２】
更に、上記代表色決定手段２８は、ヒストグラム生成手段３０、ピーク抽出手段３１、及び代表色選出手段３２を備えている。
【００５３】
ヒストグラム生成手段３０は、領域分割手段２７が生成する閉領域の色ヒストグラムＨ＝｛Ｈ（Ｃ）｝（Ｃは色を表す。）を生成する。ピーク抽出手段３１は、色ヒストグラムから度数のピークの集合（以下「ピーク集合」という。）Ｐ＝｛Ｐ（Ｃｊ）｝を抽出する。代表色選出手段３２は、ピーク集合Ｐから、度数が大きい順で且つより度数が大きい色との色空間上の距離が所定の閾値以上となるようにｎ０個の色を選出し代表色に決定する。
【００５４】
尚、図１の立体地図簡略化装置は、ハードウェアにより構成することもできるが、各機能ブロックをプログラムにより作成し、プログラムをコンピュータで実行することによって各機能ブロックを実現するように構成してもよい。
【００５５】
以上のように構成された本実施例に係る立体地図簡略化装置について、以下その動作を説明する。
【００５６】
（１）立体地図簡略化方法の全体の流れ
図２は、実施例１の立体地図簡略化方法の全体の流れを表す図である。
【００５７】
まず、ステップＳ１において、メッシュ簡略化モジュール３は、メッシュ記憶手段１に記憶されている詳細メッシュに基づいて簡略化メッシュを生成する。これにより、各要素の視認性を損なわずに詳細メッシュのメッシュ数が削減され、メッシュのデータ量が削減される。生成された簡略化メッシュは簡略化メッシュ記憶手段４に保存される。
【００５８】
次に、テクスチャ簡略化モジュール５は、テクスチャ記憶手段２に記憶されたテクスチャ（画像）に基づき、簡略化テクスチャを生成する。これにより、各要素のテクスチャの視認性を維持したまま、それぞれのテクスチャのデータ量が削減される。生成された簡略化テクスチャは、簡略化テクスチャ記憶手段６に保存される。
【００５９】
次に、ステップＳ３において、テクスチャ・マッピング手段７は、テクスチャ・マッピングにより各要素の簡略化メッシュに簡略化テクスチャを貼り付けるとともに、地図平面上の各位置に各要素を配置して、所定の視点からの景観データを作成する。作成された景観データは景観データ記憶手段８に保存される。
【００６０】
最後に、ステップＳ４において、出力手段９は、景観データ記憶手段８に記憶された景観データを出力して、一連の処理を終了する。
【００６１】
以下、上記ステップＳ１及びステップＳ２の処理に関して、詳細に説明する。
【００６２】
（２）簡略化メッシュの生成アルゴリズム（ステップＳ１）
図３は、簡略化メッシュの生成アルゴリズム（ステップＳ１）の全体の流れを表すフローチャートである。
【００６３】
簡略化メッシュの生成アルゴリズムにおいては、まずステップＳ１１〜Ｓ１８で、メッシュ記憶手段１に格納されたすべての要素に関しての重要度を計算し、重要要素又は細瑣要素に分類する。このとき、細瑣情報に関しては、幾何情報の簡略化によりメッシュ数の削減が行われる。ステップＳ１９，Ｓ２０では、細瑣要素の統合又は削除による要素数の削減が行われる。以下、順を追って詳細に説明する。
【００６４】
ステップＳ１１において、まず、要素抽出手段１１は、メッシュ記憶手段１から未選択の要素ｂｉを読み出す。
【００６５】
ステップＳ１２において、重要度計算手段１２は、要素ｂｉの重要度Ｉ（ｂｉ）を算出する。ここで、重要度Ｉ（ｂｉ）は、要素ｂｉの体積（又は表面積）Ｉ１（ｂｉ）、複雑さＩ２（ｂｉ）、属性Ｉ３（ｂｉ）の重み付き線形和として式（１）により表される。ここで、ｗ１，ｗ２，ｗ３は重み係数であり、実施の際に適宜調整して決められる定数である。
【００６６】
【数１】
【００６７】
要素ｂｉの体積（又は表面積）Ｉ１（ｂｉ）は、要素ｂｉを構成するメッシュの頂点座標により容易に計算できる。（尚、ここで体積又は表面積としたのは、交通標識のように体積が０で表面積が有限値の要素も存在するためである。）
【００６８】
要素ｂｉの複雑さＩ２（ｂｉ）は、次のようにして計算される。
【００６９】
（ア）まず、要素ｂｉを構成するｋ個のメッシュの面の単位法線ベクトルを求める。ここで、要素ｂｉを構成するｋ個のメッシュの面の集合をΞ（ｂｉ）＝｛ξ１（ｂｉ），…，ξｋ（ｂｉ）｝と記す。面ξｉ（∈Ξ（ｂｉ））の単位法線ベクトルの集合をＮ＝｛ｎ１，…，ｎｋ｝と記す。単位法線ベクトルの計算は、各メッシュの頂点座標に基づき容易に計算することができる。
【００７０】
（イ）次に、単位法線ベクトルの集合をＮから、基準となる単位法線ベクトル（以下「基準法線ベクトル」という。）を任意に一つ選択する。ここでは、基準法線ベクトルをｎ１とする。
【００７１】
（ウ）次に、基準法線ベクトルｎ１とその他の単位法線ベクトルとの内積の分散σ２を式（２）により求め、これを要素ｂｉの複雑さＩ２とする。
【００７２】
【数２】
【００７３】
属性Ｉ３（ｂｉ）は、要素ｂｉの視認性によって定まる重要度パラメータであり、式（３）により表される。
【００７４】
【数３】
【００７５】
ここで、ｈ（ｂ）は要素ｂの高さを表す。ｈ（ｂａｒ）は要素ｂｉからの距離が所定の範囲内にある建物要素の高さの平均値を表す。ｂｎｅは要素ｂｉの最も近隣の建物要素を表す。ｄ（ｂｉ，ｂｎｅ）は、要素ｂｉと要素ｂｉの最も近隣の要素との間の距離を表す。また、ａ１，ａ２，ａ３は重み係数であり、適宜定められる定数値である。
【００７６】
属性Ｉ３（ｂｉ）は、要素ｂｉが交差点の角に面する場合、周りの建物要素との高さの平均と当該要素ｂｉの高さの差が大きい場合、及び要素ｂｉに隣接する建物要素がない場合に大きな値を採る。
【００７７】
このようにして、要素ｂｉの複雑さ及び属性が数値化され、重要度Ｉ（ｂｉ）は式（１）の線形和で表される。
【００７８】
ステップＳ１３において、要素分類手段１３は、重要度Ｉ（ｂｉ）が所定の閾値ＴＩよりも大きいか否かを判定することにより、要素ｂｉを重要要素又は細瑣要素に分類する。ここで、Ｉ（ｂｉ）＞ＴＩならば、要素分類手段１３は要素ｂｉを重要要素と判定し、重要要素ｂｉを重要要素記憶手段１４に一時保存し（ステップＳ１４）、ステップＳ１８へ移行する。Ｉ（ｂｉ）≦ＴＩならば、要素分類手段１３は要素ｂｉを細瑣要素と判定し、ステップＳ１５へ移行する。
【００７９】
ステップＳ１５において、要素分類手段１３は、更に細瑣要素ｂｉを、「道路」，「交通案内標識」，「小物体」，「建物」の何れかに分類する。以下、この細瑣要素ｂｉの小分類をＵｉで記す。
【００８０】
ここで、要素分類手段１３による細瑣要素ｂｉの小分類Ｕｉの決定は以下のようにして実行される。
【００８１】
（ア）細瑣要素ｂｉのテクスチャを参照し、矢印、斜線、横断歩道、ゼブラゾーン等の道路に特有の所定のテクスチャが検出された場合、当該細瑣要素ｂｉの小分類Ｕｉは「道路」であるとする。
【００８２】
上記テクスチャが検出されない場合であっても、当該細瑣要素ｂｉの標高が所定の閾値Ｔlev以下であり且つ上記式（２）で算出された分散値σ２（ｎ）が所定の閾値Ｔσ以下である場合、当該細瑣要素ｂｉの小分類Ｕｉは「道路」であるとする。すなわち、標高が低く、かつ、分散値σ２（ｎ）が小さい細瑣要素は、地面に近く平らであると判断されるので、そのような細瑣要素は「道路」であるとする。
【００８３】
（イ）上記式（２）で算出された細瑣要素ｂｉの分散値σ２（ｎ）が０である場合、以下の３つの条件が満たされていれば、細瑣要素ｂｉの小分類Ｕｉは「交通案内標識」であるとする。
【００８４】
（ａ）細瑣要素ｂｉに張られるテクスチャが２色（青と白など）からなる。
（ｂ）細瑣要素ｂｉの法線ｎが地面（基準面）とほぼ平行である。
（ｃ）細瑣要素ｂｉの下端が地面に接していない（すなわち、空中に吊り下げられている）。
【００８５】
（ウ）細瑣要素ｂｉの体積（又は表面積）が所定の閾値ＴＳ以下の場合、その細瑣要素ｂｉの小分類Ｕｉは「小物体」であるとする。このような小物体としては、例えば、看板やポストなどが該当する。
【００８６】
（エ）上記（ア）〜（ウ）の何れでもない場合、その細瑣要素ｂｉの小分類Ｕｉは「建物」であるとする。
【００８７】
以上のようにして、すべての細瑣要素ｂｉの小分類Ｕｉが決定される。
【００８８】
ステップＳ１６において、要素分類手段１３は細瑣要素ｂｉ及びその小分類Ｕｉを細瑣要素記憶手段１５へ一時保存する。
【００８９】
ステップＳ１７において、幾何情報簡略化手段１６は、細瑣要素ｂｉの簡略化を以下のようにして行う。
【００９０】
（１）道路と交通標識の簡略化
細瑣要素ｂｉの小分類Ｕｉが「道路」又は「交通案内標識」の場合、その細瑣要素ｂｉは体積０の平面又は曲面である。この場合、面を構成する辺上にあるメッシュの頂点のみを残し、面内にあるメッシュの頂点をすべて削除する。また、面を構成する辺に直線部分がありその直線の両端以外にメッシュの頂点が存在する場合、そのような頂点もすべて削除する。そして、残った頂点のみでメッシュの再構成を行い、簡略化された細瑣要素ｂｉのメッシュを生成する。
【００９１】
（２）小物体の簡略化
上記ステップＳ１５において小分類Ｕｉが「小物体」とされた細瑣要素はすべて削除する。
【００９２】
（３）建物の簡略化
尚、上記ステップＳ１５において小分類Ｕｉが「建物」とされた細瑣要素（以下「建物要素」という。）については、相隣接する建物要素同士の統合処理を行うが、この処理は、後のステップＳ１９において行われる。
【００９３】
ステップＳ１８において、メッシュ記憶手段１内の全要素ｂｉについての上記一連の処理（Ｓ１１〜Ｓ１７）が終了していなければ、ステップＳ１１に戻る。終了していれば、ステップＳ１９へ移行する。
【００９４】
ステップＳ１９においては、グループ化手段１７及び要素結合手段１８により、細瑣要素記憶手段１５に記憶された建物要素の統合処理が行われる。この建物要素の統合処理については、この後で更に詳細に説明する。建物要素の統合処理により、細瑣要素は更に簡略化される。
【００９５】
ステップＳ２０において、簡略化メッシュ出力手段１９は、重要要素記憶手段１４に記憶された重要要素と、細瑣要素記憶手段１５に記憶された簡略化された細瑣要素を読み出して、簡略化メッシュ記憶手段４に保存し、簡略化テクスチャの生成アルゴリズムを終了する。
【００９６】
〔建物要素の統合処理〕
次に、上記ステップＳ１９における建物要素の統合処理について更に詳細に説明する。
【００９７】
図４は、建物要素の統合処理の統合処理の全体の流れを表すフローチャートである。
【００９８】
まず、ステップＳ３１において、グループ化手段１７は、細瑣要素記憶手段１５に記憶された建物要素を読み出して、互いに近接する建物要素を同じグループとしてグループ分けを行う。以下では、建物要素のグループをＧｉ、グループＧｉに属する建物要素をｂi,jと記す。Ｇｉ＝｛ｂi,j｝である。
【００９９】
ステップＳ３２において、要素結合手段１８は、１つの建物要素のグループＧｉを取り出す。そして、ステップＳ３３において、グループＧｉ内の建物要素の結合処理を行う（図５参照）。
【０１００】
次いで、ステップＳ３４において、すべてのグループについて建物要素の結合処理が行われていなければ、ステップＳ３２に戻り、次のグループについての処理を行う。すべてのグループについて建物要素の結合処理が行われた場合は、建物要素の統合処理を終了する。
【０１０１】
図５は、ステップＳ３２における建物要素の結合処理の流れを表すフローチャートである。ここでは、建物要素のグループをＧｉ、グループＧｉに属する建物要素をｂｉ,ｊ、建物要素をｂｉ,ｊに属するメッシュの頂点をｐｉ,ｊ,ｋと記す。
【０１０２】
まず、ステップＳ４１において、投影頂点決定手段２１は、グループＧｉに属するすべての要素ｂｉ，ｊ（∀ｂｉ，ｊ∈Ｇｉ）について、地上にある頂点ｐｉ,ｊ,ｋを抽出する（図５（ｂ）参照）。ここで、地上にあるか否かは、各頂点の高さの座標が、予め定められた基準面（地上面）の高さに一致するか否かによって判定することができる。抽出された頂点集合｛ｐｉ,ｊ,ｋ｝により構成される多角形は、グループをＧｉの各建物要素を地上に投影した地上投影図形である。
【０１０３】
ステップＳ４２において、投影図形生成手段２２は、抽出されたすべての頂点ｐｉ,ｊ,ｋから、折れ曲がり点以外の頂点を除去する。すなわち、抽出されたすべての頂点ｐｉ,ｊ,ｋにより構成される多角形の各直線部分について、その直線部分の両端点以外にメッシュの頂点が存在すれば、その頂点は冗長であるため除去する（図５（ｃ）参照）。
【０１０４】
ステップＳ４３において、投影図形生成手段２２は、残った頂点｛ｐｉ,ｊ,ｋ｝により構成される多角形について凸包（convex hull）を求める。これを新たな結合要素ｂｉの地上投影図形Ｓとする（図５（ｄ）参照）。
【０１０５】
ステップＳ４４において、高さ決定手段２３は、グループをＧｉの各建物要素の高さから、新たな結合要素ｂｉの高さｈ（ｂｉ）を決定する。この場合、高さｈ（ｂｉ）は、グループをＧｉの各建物要素の高さの最大値、平均値等として決定される。
【０１０６】
ステップＳ４５において、結合要素生成手段２４は、地上投影図形Ｓを上空に向かって高さｈ（ｂｉ）だけ引き延ばした多角柱を生成し、これを結合要素ｂｉとして、細瑣要素記憶手段１５に保存する。
【０１０７】
以上のような処理により、立体地図の詳細メッシュが簡略化され、大幅にデータ量を削減することができる。また、要素の重要度に応じて、重要度の低い物を視認性を確保しつつメッシュの削減を行うため、立体地図の視認性が低下することもない。むしろ、余分な要素が削減されるため地図構成がシンプルとなり、視認性を向上させる効果が期待できる。
【０１０８】
（３）簡略化テクスチャの生成アルゴリズム（ステップＳ２）
最後に、上記ステップＳ２において行われる簡略化テクスチャの生成処理についての説明を行う。
【０１０９】
まず、テクスチャ簡略化モジュール５は、要素分類手段１３により生成される各要素の分類を参照し、重要要素と、細瑣要素の中の「道路」、「交通案内標識」、及び「建物」のテクスチャを順次テクスチャ記憶手段２から読み出す。そして、読み出された各テクスチャについて以下のテクスチャ簡略化アルゴリズムを実行することによって各テクスチャの簡略化を行う。
【０１１０】
図６は、簡略化テクスチャの生成アルゴリズム（ステップＳ２）の全体の流れを表すフローチャートである。
【０１１１】
まず、ステップＳ５１において、領域分割手段２７は、テクスチャ画像にＳｏｂｅｌフィルタを適用して特徴画像を生成する。次に、ステップＳ５２において、特徴画像に対してＨｏｕｇｈ変換を行い、直線部分を検出する。そして、得られた直線を用いて、原画増（テクスチャ）を複数の閉領域｛ｓｉ｝に領域分割する。以下、代表色決定手段２８は、分割されたそれぞれの領域で代表色を決定していく。
【０１１２】
ステップＳ５４において、代表色決定手段２８は、一つの閉領域ｓｉを選択する。そして、ステップＳ５５において、閉領域ｓｉの代表色｛Ｃｉ（ｊ）｝を決定する。ここで、代表色は複数の色が決定される。この代表色決定処理の詳細については後述する。
【０１１３】
次に、ステップＳ５６において、色置換手段２９は、閉領域ｓｉ内の各画素について、その画素の色に対して色空間距離が最も近い代表色を選択し、その画素の色を選択した代表色で置換する。これにより、閉領域ｓｉ内のテクスチャは代表色｛Ｃｉ（ｊ）｝の要素数に減色される。
【０１１４】
ステップＳ５７において、すべての閉領域｛ｓｉ｝について上記ステップＳ５４〜Ｓ５６の処理を行ったか否かを判定し、行っていないものがあれば、その閉領域について処理を行うべくステップＳ５４に戻る。すべての閉領域｛ｓｉ｝について上記ステップＳ５４〜Ｓ５６の処理が終了すれば、簡略化テクスチャの生成アルゴリズムを終了する。
【０１１５】
次に、上述のステップＳ５５における代表色決定処理の詳細について説明する。
【０１１６】
〔代表色決定処理〕
図７は、代表色決定処理を表すフローチャートである。
【０１１７】
まず、ステップＳ６１において、ヒストグラム生成手段３０は、閉領域ｓｉの色ヒストグラムＨｉ＝｛Ｈｉ（Ｃ）｝を生成する。ここで、Ｃは色を表し、Ｈｉ（Ｃ）は閉領域ｓｉにおける色Ｃの度数を表す。
【０１１８】
ステップＳ６２において、ピーク抽出手段３１は、色ヒストグラムＨｉから度数のピークを抽出する。以下、このピークの集合をＱｉ＝｛ｑｉ（Ｃ）｝と記す。ｑｉは各ピーク点を表す。
【０１１９】
ステップＳ６３において、ピーク抽出手段３１は、ピーク集合Ｑｉの各ピークの中から、度数Ｈｉ（Ｃｊ）が最大のピークｑｉ（Ｃｊ）を抽出する。このピークｑｉ（Ｃｊ）に対応する色Ｃｊを第０番目の代表色Ｃｉ（０）とする。そして既に選択されたピークｑｉ（Ｃｊ）は、ピーク集合Ｑｉから削除する。すなわち、Ｑｉ←Ｑｉ−｛ｑｉ（Ｃｊ）｝として集合Ｑｉを更新する。
【０１２０】
ステップＳ６４において、代表色選出手段３２は、ピーク集合Ｑｉの各ピークｑｊ（∈Ｑｉ）の度数Ｈｉ（Ｃｊ）を、最大度数Ｈｉ（Ｃｉ（０））で規格化する（式（６））。規格化された度数はＲｉ（Ｃｊ）と記す。そして、ステップＳ６５で、内部変数として保持している選択色番号ｎを０に設定する。
【０１２１】
【数４】
【０１２２】
ステップＳ６６において、代表色選出手段３２は、ピーク集合Ｑｉの各ピークｑｊ（∈Ｑｉ）のうち、度数Ｒｉ（Ｃｊ）が最大の色Ｃｊを抽出する。
【０１２３】
ステップＳ６７において、代表色選出手段３２は、抽出した色Ｃｊについて、既に決定されている各代表色からの色空間における最短距離ｄｊを式（７）により計算する。
【０１２４】
【数５】
【０１２５】
ステップＳ６８において、代表色選出手段３２は、抽出色Ｃｊについての評価値ｘｊを式（８）により計算する。式（８）より、評価値ｘｊは最短距離ｄｊと度数Ｒｉ（Ｃｊ）との加重平均とされている。ｗ１，ｗ２は重み係数であり、適当な定数値に設定される。すなわち、既決定の代表色との最短距離ｄｊが大きいほど評価値ｘｊは大きくなり、また、度数Ｒｉ（Ｃｊ）が大きいほど評価値ｘｊは大きくなる。
【０１２６】
【数６】
【０１２７】
ここで、評価値ｘｊに既決定の代表色との最短距離ｄｊが考慮されている理由は、選択される代表値同士が近似色ばかりになることをなるべく防止することを意図したものである。近似色ばかりが選択されると、閉領域ｓｉは単色ですりつぶされたような状態となり、もとのテクスチャの情報が殆ど失われて視認性を下げるおそれがある。
【０１２８】
ステップＳ６８において、代表色選出手段３２は、評価値ｘｊと閾値ｘｔｈとを比較する。ｘｊ＞ｘｔｈであれば、代表色選出手段３２は抽出色Ｃｊを代表色Ｃｉ（ｎ）に決定する（ステップＳ７０）。ｘｊ≦ｘｔｈであれば、抽出色Ｃｊは捨てて、ステップＳ７１へ移る。
【０１２９】
ステップＳ７１において、代表色選出手段３２は、ピーク集合Ｑｉから、既評価のピークｑｉ（Ｃｊ）を削除する。すなわち、Ｑｉ←Ｑｉ−｛ｑｉ（Ｃｊ）｝として集合Ｑｉを更新する。
【０１３０】
ステップＳ７２において、代表色選出手段３２は、選択色番号ｎが規定値ｎ０に達したか否かを判定する。達していなければ、ステップＳ６６に戻る。達していれば、代表色決定処理を終了する。
【０１３１】
以上の処理により、ｎ０個の代表色が決定される。決定された代表色は、閉領域ｓｉの色の減色化に使用されるものであり、できるだけ多数の画素で使用され、できるだけ色空間上の距離が互いに離れた色が選択される。
【図面の簡単な説明】
【０１３２】
【図１】本発明の実施例１に係る立体地図簡略化装置の構成を表すブロック図である。
【図２】実施例１の立体地図簡略化方法の全体の流れを表す図である。
【図３】簡略化メッシュの生成アルゴリズム（ステップＳ１）の全体の流れを表すフローチャートである。
【図４】建物要素の統合処理の統合処理の全体の流れを表すフローチャートである。
【図５】ステップＳ３２における建物要素の結合処理の流れを表すフローチャートである。
【図６】簡略化テクスチャの生成アルゴリズム（ステップＳ２）の全体の流れを表すフローチャートである。
【図７】代表色決定処理を表すフローチャートである。
【図８】特許文献１の方法による立体地図の表示例である。
【図９】非特許文献１における建物データの例を示す図である。
【符号の説明】
【０１３３】
１ メッシュ記憶手段
２ テクスチャ記憶手段
３ メッシュ簡略化モジュール
４ 簡略化メッシュ記憶手段
５ テクスチャ簡略化モジュール
６ 簡略化テクスチャ記憶手段
７ テクスチャ・マッピング手段
８ 景観データ記憶手段
９ 出力手段
１１ 要素抽出手段
１２ 重要度計算手段
１３ 要素分類手段
１４ 重要要素記憶手段
１５ 細瑣要素記憶手段
１６ 幾何情報簡略化手段
１７ グループ化手段
１８ 要素結合手段
１９ 簡略化メッシュ出力手段
２１ 投影頂点決定手段
２２ 投影図形生成手段
２３ 高さ決定手段
２４ 結合要素生成手段
２５ 重要テクスチャ生成手段
２７ 領域分割手段
２８ 代表色決定手段
２９ 色置換手段
３０ ヒストグラム生成手段
３１ ピーク抽出手段
３２ 代表色選出手段
【技術分野】
【０００１】
本発明は、三次元データにより表される立体地図のデータを簡略化する立体地図簡略化技術に関し、特に、簡略化による違和感の少ない立体地図簡略化技術に関する。
【背景技術】
【０００２】
近年、携帯可能なカメラや携帯電話等の情報端末にて、立体地図を表示させてナビゲーションや位置確認等を行わせる技術の研究開発が行われつつある（例えば、特許文献１，２参照）。かかる携帯可能な情報端末では、小型化・省電力化が求められる。また、無線通信により地図情報を送信する場合、リアルタイムに地図情報を携帯端末に表示させるためには、地図情報の情報量の削減が必要である。従って、簡略な構成で立体地図の表示を行うための立体地図簡略化技術が必要とされている。
【０００３】
ところで、立体地図の編集、獲得、表示には３Ｄモデルが用いられる。３Ｄモデルには、ヴォリュームモデル、ソリッドモデル、スプラインパッチ等、様々な表現方法がある。その中でも、物体の表面をポリゴンで近似する３Ｄメッシュモデル（以下「３Ｄメッシュ」という。）は、高精細なモデル、アニメーションを比較的簡単に表現できることから広く用いられている（非特許文献１参照）。
【０００４】
通常、３Ｄモデルは、メッシュ情報以外にも、属性データと呼ばれる色、材質などを表す情報が含まれている。立体地図では、テクスチャを属性として持つ３Ｄメッシュが用いられる。テクスチャは、通常は画像として与えられる。テクスチャとして与えられた画像を３Ｄメッシュに貼り付けることを「マッピング」という。テクスチャを３Ｄメッシュにマッピングすることにより、色つき３Ｄメッシュが得られる。
【０００５】
元来、３Ｄメッシュは膨大な情報量を持つことが多い。従って、この３Ｄメッシュの情報をネットワーク配信し、データベース管理し、又は高速表示する為には、データ量の削減が必要である。ここでは、データ量の削減のことを「簡略化」と呼ぶ。
【０００６】
ところで、前述の通り、立体地図に用いられる３Ｄメッシュはメッシュ情報とテクスチャ情報とを併せ持つ。そのため、それぞれの情報について簡略化を行う必要がある。通常、テクスチャ（画像）の簡略化は、解像度（画像の縦横のサイズ）を縮小することによって容易に達成することができる。しかし、３Ｄメッシュに関しては工夫が必要とされる。
【０００７】
立体地図では、ビル、家、看板などの構成要素の一つ一つが直方体や円筒などの単純な形を持つ３Ｄメッシュで構成されている。比較的狭いエリアの立体地図でも、その構成要素の数は膨大となる。そのため、データベース化、伝送、表示には多くの計算量が必要とされる。特に、ＣＰＵ（中央演算装置）の演算能力、記憶容量、ディスプレイの解像度に強い制約がある携帯端末では、そのままではデータの伝送、表示が困難である。
【０００８】
そこで、立体地図の効果的なデータ構造を提案することで、高速に立体地図を表示する方法が幾つか提案されている。
【０００９】
特許文献１では、ビル等の複数の構造物が建築されている街区を、当該街区に存在する複数の構造物の概略形状を表す１つのブロックとして形成する方法が採られている。そして、視点の位置情報と方位情報を元に、テクスチャ（画像）データに視点に応じた変形処理や明暗処理を加え、処理された画像データを、対応するブロックの表面に貼り付けてマッピングする。
【００１０】
その方法による立体地図の表示例を図８に示す。図８に示すように、立体地図の各街区は、１つ直方体ブロック１００として形成されている。各直方体ブロック１００の表面には、変形処理や明暗処理がされたテクスチャを表す画像データ１０１，１０２が貼り付けられている。直方体ブロック１００と画像データ１０１，１０２との対応関係は常に保持される。
【００１１】
また、非特許文献１には、複数のレベルで簡略化した建物形状のデータを用意し、視点からの距離に応じてレベルを設定することにより、視点からの距離に応じて簡略化した建物形状を表示する方法が記載されている。
【００１２】
図９は非特許文献１における建物データの例を示す図である。この方法では、立体地図に含まれるすべての建物ｊについて、図９のような各レベルの建物データＳｊ＝｛Ｓｊ１，…，Ｓｊ７｝を予め生成し、保存しておく。建物データは、レベルが高いほど簡略化の度合いが大きくなるように構成されている。
【００１３】
立体地図の表示時には、視点から各建物までの距離ｄｉを計算する。そして、距離ｄｉに応じてレベルを決定し、そのレベルの建物データを表示する。このとき、視点からの距離が遠いほど、高いレベルを設定する。これにより、視点近傍の建物は低レベルの建物データが選択され、視点からの距離が遠くなるほど高レベルの建物データが選択される。従って、視点からの距離が遠いほど、簡略化された建物データが表示されることになる。これにより、表示画面上にポリゴンを配置する計算量の低減が図られている。
【特許文献１】特開２００１−５９９４号公報
【特許文献２】特開平１１−２１９１０６号公報
【非特許文献１】山田方根，「仮想都市の自動生成における建物形状の作成と表示」，平成１５年１月，筑波大学大学院システム情報工学研究科 平成１５年度修士論文，［平成１７年３月２０日検索］，インターネット＜URL:http://www.sie.tsukuba.ac.jp/H15syuron/200205245.pdf＞
【非特許文献２】H. Hoppe, "Progressive meshes", ACM SIGGRAPH 1996, pp.99-108.
【発明の開示】
【発明が解決しようとする課題】
【００１４】
上記特許文献１記載の方法を用いればメッシュデータを大幅に削減することが可能である。しかしながら、各街区を直方体ブロックで近似しているため、近似度合いが非常に粗くなる。その結果、使用者における景観の視認性が低下するという問題がある。
【００１５】
また、非特許文献１の手法では、各レベルの建物データをメモリに記憶しておく必要がある。そのため、大容量の記憶装置が必要となる。特に、記憶容量の制約が大きい携帯端末などに広域の立体地図を保持することが困難である。
【００１６】
そこで、本発明の目的は、使用者の視認性が向上するように建物データを簡略化し、かつ立体地図を保持するための記憶容量も削減可能な立体地図簡略化技術を提供することにある。
【課題を解決するための手段】
【００１７】
本発明に係る立体地図簡略化装置の第１の構成は、立体地図画像を簡略化する立体地図簡略化装置において、立体地図画像を構成する各要素について、当該要素の重要度を計算する重要度計算手段；地上に配置された要素のうち、前記重要度が所定の閾値よりも小さい要素について、互いに近接する要素が同じグループとなるようにグループ分けするグループ化手段；及び、前記各グループに属する要素を結合し、１つの結合要素とする要素結合手段；を備えたことを特徴とする。
【００１８】
この構成によれば、重要度の低い要素については、複数の要素を結合して１つの要素とすることによって、立体地図画像内の要素のメッシュ数を減少させることができる。従って、表示する立体地図のデータ量を削減することが可能となる。また、携帯端末等には簡略化された立体地図のデータを送信し、又は携帯端末等の内部の記憶装置に記憶させるようにすれば、記憶容量の少ない携帯端末においても広域の立体地図データを保持することができる。更に、複数のレベルで簡略化した建物データを作成する必要がないため、立体地図の記憶容量を低減することができると共に、データの作成も容易化される。
【００１９】
また、重要度の低い要素は簡略化され、重要度の高い要素は詳細に表示されるため、使用者の視認性は損なわれず、むしろ、風景の特徴を捉えやすくなるため視認性は向上する。
【００２０】
ここで、「要素」とは、建造物、道路、標識、看板等の立体地図を構成する要素（オブジェクト、物体）をいう。各要素は、表面をポリゴンで近似する３Ｄメッシュで表現される。
【００２１】
本発明に係る立体地図簡略化装置の第２の構成は、前記第１の構成において、前記要素結合手段は、前記各グループについて、当該グループに属する各要素を地面に投影し、投影した２次元投影図形の頂点を求める投影頂点決定手段；前記２次元投影図形の凸包を求め、これを当該要素の新たな地上投影図形Ｓとする地上投影図形生成手段；前記グループに属する各要素の高さから当該グループの要素の高さの代表値を決定する高さ決定手段；及び、前記地上投影図形Ｓを前記高さの代表値だけ高さ方向に引き延ばすことにより、前記結合要素を生成する結合要素生成手段；を備えていることを特徴とする。
【００２２】
この構成により、各グループに属する要素を違和感なく結合して、結合要素を生成することができる。
【００２３】
ここで、「代表値」としては最大値や平均値等が用いられる。
【００２４】
本発明に係る立体地図簡略化装置の第２の構成は、前記第１又は２の構成において、前記重要度計算手段は、要素を構成するメッシュのうち一のメッシュに対して、当該メッシュの単位法線ベクトルと他のメッシュの単位法線ベクトルとの内積を、要素を構成するすべてのメッシュについて積算した値である面複雑性が含まれる重要度を算出することを特徴とする。
【００２５】
この構成により、看板のような複雑な形状の要素は面複雑性が大きく、通常の建物のように比較的単純な形状の要素は面複雑性が小さくなる。従って、面複雑性を指標とすることにより、建物とその他の付属構造物との区別が或る程度可能となり、重要度の決定精度が向上する。
【００２６】
本発明に係る立体地図簡略化装置の第４の構成は、立体地図の各要素に属するテクスチャ画像を簡略化する立体地図簡略化装置であって、テクスチャの原画像を複数の閉領域に分割する領域分割手段；前記各閉領域に対して代表色を決定する代表色決定手段；前記各閉領域の色を前記代表色で置き換える色置換手段；を有し、前記代表色決定手段は、当該閉領域の色ヒストグラムＨ＝｛Ｈ（Ｃ）｝（Ｃは色を表す。）を生成するヒストグラム生成手段；前記色ヒストグラムから度数のピークの集合（以下「ピーク集合」という。）Ｐ＝｛Ｐ（Ｃｊ）｝を抽出するピーク抽出手段；前記ピーク集合Ｐから、度数が大きい順で且つより度数が大きい色との色空間上の距離が所定の閾値以上となるようにｎ０個の色を選出し代表色に決定する代表色選出手段；を備えたことを特徴とする。
【００２７】
この構成により、テクスチャを減色する際に、最も多くの領域を占める色彩から代表色に決定されると共に、各代表色間の色空間距離を或る閾値以上とすることで、代表色間のコントラストをつけることができる。そのため、最適な色選択による減色でテクスチャのデータ量が削減されるとともに、減色されたテクスチャの視認性を確保することができる。
【００２８】
本発明に係る立体地図簡略化方法の第１の構成は、立体地図画像を簡略化する立体地図簡略化方法であって、立体地図画像を構成する各要素について、当該要素の重要度を計算する重要度計算ステップ；地上に配置された要素のうち、前記重要度が所定の閾値よりも小さい要素について、互いに近接する要素が同じグループとなるようにグループ分けするグループ化ステップ；及び、前記各グループに属する要素を結合し、１つの結合要素とする要素結合ステップ；を有することを特徴とする。
【００２９】
本発明に係る立体地図簡略化方法の第２の構成は、前記第１の構成において、前記要素結合ステップは、前記各グループについて、当該グループに属する各要素を地面に投影し、投影した２次元投影図形の頂点を求める投影頂点決定ステップ；前記２次元投影図形の凸包を求め、これを当該要素の新たな地上投影図形Ｓとする地上投影図形生成ステップ；前記グループに属する各要素の高さから当該グループの要素の高さの代表値を決定する高さ決定ステップ；及び、前記地上投影図形Ｓを前記高さの代表値だけ高さ方向に引き延ばすことにより、前記結合要素を生成する結合要素生成ステップ；を有することを特徴とする。
【００３０】
本発明に係る立体地図簡略化方法の第３の構成は、前記第１又は２の構成において、前記重要度計算ステップでは、要素を構成するメッシュのうち一のメッシュに対して、当該メッシュの単位法線ベクトルと他のメッシュの単位法線ベクトルとの内積を、要素を構成するすべてのメッシュについて積算した値である面複雑性が含まれる重要度を算出することを特徴とする。
【００３１】
本発明に係る立体地図簡略化方法の第４の構成は、立体地図の各要素に属するテクスチャ画像を簡略化する立体地図簡略化方法であって、テクスチャの原画像を複数の閉領域に分割する領域分割ステップ；前記各閉領域に対して代表色を決定する代表色決定ステップ；前記各閉領域の色を前記代表色で置き換える色置換ステップ；を有し、前記代表色決定ステップにおいては、当該閉領域の色ヒストグラムＨ＝｛Ｈ（Ｃ）｝（Ｃは色を表す。）を生成するヒストグラム生成ステップ；前記色ヒストグラムから度数のピークの集合（以下「ピーク集合」という。）Ｐ＝｛Ｐ（Ｃｊ）｝を抽出するピーク抽出ステップ；前記ピーク集合Ｐから、度数が大きい順で且つより度数が大きい色との色空間上の距離が所定の閾値以上となるようにｎ０個の色を選出し代表色に決定する代表色選出ステップ；を有していることを特徴とする。
【００３２】
本発明に係るプログラムは、前記第１乃至４の何れか一の構成の立体地図簡略化方法を実行するプログラム。
【発明の効果】
【００３３】
以上のように、本発明によれば、重要度の低い要素を結合することによって、立体地図画像内の要素のメッシュ数を減少させ建物データを簡略化し、データ量の削減を図ることが可能となる。また、記憶容量の少ない携帯端末においても広域の立体地図データを保持することができる。更に、複数のレベルで簡略化した建物データを作成する必要がないため、立体地図の記憶容量を低減することができると共に、データの作成も容易化される。
【００３４】
また、重要度の低い要素を簡略化し、重要度の高い要素を詳細に表示することにより、風景の特徴を捉えやすくなり、使用者の視認性を向上させることができる。
【００３５】
更に、要素のテクスチャのデータについては、最適な色選択による減色でテクスチャのデータ量が削減され、減色されたテクスチャの視認性を確保することができる。
【発明を実施するための最良の形態】
【００３６】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００３７】
図１は、本発明の実施例１に係る立体地図簡略化装置の構成を表すブロック図である。実施例１に係る立体地図簡略化装置は、その構成として、メッシュ記憶手段１、テクスチャ記憶手段２、メッシュ簡略化モジュール３、簡略化メッシュ記憶手段４、テクスチャ簡略化モジュール５、簡略化テクスチャ記憶手段６、テクスチャ・マッピング手段７、景観データ記憶手段８、及び出力手段９を備えている。
【００３８】
メッシュ記憶手段１は、詳細な立体地図の各要素（ポリゴン）をメッシュ情報として記憶する。テクスチャ記憶手段２は、メッシュ記憶手段１に記憶された立体地図の各要素の表面に貼り付ける画像（以下「テクスチャ」という。）情報を記憶する。尚、これら詳細な立体地図のメッシュ情報とテクスチャ情報は、予め与えられているものとする。
【００３９】
メッシュ簡略化モジュール３は、メッシュ記憶手段１に記憶されたメッシュ情報（以下「詳細メッシュ」という。）を簡略化して簡略化メッシュを生成する。簡略化メッシュ記憶手段４は、メッシュ簡略化モジュール３が生成する簡略化メッシュを一時的に記憶する。
【００４０】
テクスチャ簡略化モジュール５は、テクスチャ記憶手段２に記憶されたテクスチャ情報（以下「詳細テクスチャ」という。）を簡略化して簡略化テクスチャを生成する。簡略化テクスチャ記憶手段６は、テクスチャ簡略化モジュール５が生成する簡略化テクスチャを一時的に記憶する。
【００４１】
テクスチャ・マッピング手段７は、簡略化メッシュに簡略化テクスチャをテクスチャ・マッピングし、所定の視点位置及び視方向からの簡略化された立体地図データ（以下「景観データ」という。）を合成する。景観データ記憶手段８は、テクスチャ・マッピング手段７により合成された景観データを記憶する。出力手段９は、景観データ記憶手段８に記憶された景観データを出力する。出力手段９としては、携帯端末に対して景観データを送信する送信装置や、景観データを携帯端末のディスプレイ上に表示する表示装置等が使用される。
【００４２】
ここで、上記メッシュ簡略化モジュール３は、要素抽出手段１１、重要度計算手段１２、要素分類手段１３、重要要素記憶手段１４、細瑣要素記憶手段１５、幾何情報簡略化手段１６、グループ化手段１７、要素結合手段１８、及び簡略化メッシュ出力手段１９を備えている。
【００４３】
要素抽出手段１１は、メッシュ記憶手段１から順次各要素を読み出す。重要度計算手段１２は、要素抽出手段１１により読み出された各要素について、当該要素の重要度を計算する。重要度の計算方法に関しては後述する。
【００４４】
要素分類手段１３は、要素抽出手段１１により読み出された各要素について、その当該要素の重要度に基づいて、当該要素を重要要素と細瑣要素とに分類する。この分類方法に関しては後述する。要素分類手段１３により重要要素に分類された要素は、重要要素記憶手段１４に一時保存される。また、細瑣要素に分類された要素は、細瑣要素記憶手段１５に記憶される。尚、「重要要素」とは、立体地図を概観した際に目に付きやすい要素又は目標物（ランドマーク）となり得る要素をいう。「細瑣要素」とは、重要要素ではない要素をいう。
【００４５】
幾何情報簡略化手段１６は、細瑣要素記憶手段１５に格納された細瑣要素について、不要な細瑣要素を削除し又は不要なメッシュを削減する。グループ化手段１７は、細瑣要素に含まれる近接する構造物が同じグループとなるようにグループ分けを行う。要素結合手段１８は、グループ化された各グループに属する細瑣要素を結合し、一つの結合要素とする。簡略化メッシュ出力手段１９は、各重要要素と各細瑣要素（又はグループ内で結合された結合要素）とを簡略化メッシュ記憶手段４へ出力する。
【００４６】
また、上記要素結合手段１８は、投影頂点決定手段２１、投影図形生成手段２２、高さ決定手段２３、及び結合要素生成手段２４を備えている。
【００４７】
投影頂点決定手段２１は、各グループについて、当該グループに属する各オブジェクトを地面に投影し、投影した二次元投影図形の頂点を計算する。投影図形生成手段２２は、計算された二次元投影図形の凸包を求め、これを当該要素の新たな地上投影図形Ｓとする。高さ決定手段２３は、グループに属する各要素の高さから当該グループの要素の高さの代表値ｈを決定する。結合要素生成手段２４は、地上投影図形Ｓを上記高さの代表値ｈだけ高さ方向に引き延ばすことにより、当該グループ内の各細瑣要素が結合して成る結合要素を生成する。
【００４８】
一方、上記テクスチャ簡略化モジュール５は、及び重要テクスチャ生成手段２５を備えている。これらは、それぞれ、テクスチャ記憶手段２に記憶された詳細テクスチャに基づき、重要テクスチャ及び細瑣テクスチャを生成する。
【００４９】
ここで、「重要テクスチャ」とは、重要要素のテクスチャ、及び細瑣要素のテクスチャうち視認されやすくランドマークや情報表示となり得るテクスチャをいう。「細瑣テクスチャ」とは、重要テクスチャ以外の各要素のテクスチャをいう。
【００５０】
重要テクスチャ生成手段２５は、領域分割手段２７、代表色決定手段２８、及び色置換手段２９を備えている。
【００５１】
領域分割手段２７は、詳細テクスチャの原画像を複数の閉領域に分割する。代表色決定手段２８は、各閉領域に対してその閉領域内の代表色を決定する。色置換手段２９は、各閉領域の色を上記の代表色で置き換える。
【００５２】
更に、上記代表色決定手段２８は、ヒストグラム生成手段３０、ピーク抽出手段３１、及び代表色選出手段３２を備えている。
【００５３】
ヒストグラム生成手段３０は、領域分割手段２７が生成する閉領域の色ヒストグラムＨ＝｛Ｈ（Ｃ）｝（Ｃは色を表す。）を生成する。ピーク抽出手段３１は、色ヒストグラムから度数のピークの集合（以下「ピーク集合」という。）Ｐ＝｛Ｐ（Ｃｊ）｝を抽出する。代表色選出手段３２は、ピーク集合Ｐから、度数が大きい順で且つより度数が大きい色との色空間上の距離が所定の閾値以上となるようにｎ０個の色を選出し代表色に決定する。
【００５４】
尚、図１の立体地図簡略化装置は、ハードウェアにより構成することもできるが、各機能ブロックをプログラムにより作成し、プログラムをコンピュータで実行することによって各機能ブロックを実現するように構成してもよい。
【００５５】
以上のように構成された本実施例に係る立体地図簡略化装置について、以下その動作を説明する。
【００５６】
（１）立体地図簡略化方法の全体の流れ
図２は、実施例１の立体地図簡略化方法の全体の流れを表す図である。
【００５７】
まず、ステップＳ１において、メッシュ簡略化モジュール３は、メッシュ記憶手段１に記憶されている詳細メッシュに基づいて簡略化メッシュを生成する。これにより、各要素の視認性を損なわずに詳細メッシュのメッシュ数が削減され、メッシュのデータ量が削減される。生成された簡略化メッシュは簡略化メッシュ記憶手段４に保存される。
【００５８】
次に、テクスチャ簡略化モジュール５は、テクスチャ記憶手段２に記憶されたテクスチャ（画像）に基づき、簡略化テクスチャを生成する。これにより、各要素のテクスチャの視認性を維持したまま、それぞれのテクスチャのデータ量が削減される。生成された簡略化テクスチャは、簡略化テクスチャ記憶手段６に保存される。
【００５９】
次に、ステップＳ３において、テクスチャ・マッピング手段７は、テクスチャ・マッピングにより各要素の簡略化メッシュに簡略化テクスチャを貼り付けるとともに、地図平面上の各位置に各要素を配置して、所定の視点からの景観データを作成する。作成された景観データは景観データ記憶手段８に保存される。
【００６０】
最後に、ステップＳ４において、出力手段９は、景観データ記憶手段８に記憶された景観データを出力して、一連の処理を終了する。
【００６１】
以下、上記ステップＳ１及びステップＳ２の処理に関して、詳細に説明する。
【００６２】
（２）簡略化メッシュの生成アルゴリズム（ステップＳ１）
図３は、簡略化メッシュの生成アルゴリズム（ステップＳ１）の全体の流れを表すフローチャートである。
【００６３】
簡略化メッシュの生成アルゴリズムにおいては、まずステップＳ１１〜Ｓ１８で、メッシュ記憶手段１に格納されたすべての要素に関しての重要度を計算し、重要要素又は細瑣要素に分類する。このとき、細瑣情報に関しては、幾何情報の簡略化によりメッシュ数の削減が行われる。ステップＳ１９，Ｓ２０では、細瑣要素の統合又は削除による要素数の削減が行われる。以下、順を追って詳細に説明する。
【００６４】
ステップＳ１１において、まず、要素抽出手段１１は、メッシュ記憶手段１から未選択の要素ｂｉを読み出す。
【００６５】
ステップＳ１２において、重要度計算手段１２は、要素ｂｉの重要度Ｉ（ｂｉ）を算出する。ここで、重要度Ｉ（ｂｉ）は、要素ｂｉの体積（又は表面積）Ｉ１（ｂｉ）、複雑さＩ２（ｂｉ）、属性Ｉ３（ｂｉ）の重み付き線形和として式（１）により表される。ここで、ｗ１，ｗ２，ｗ３は重み係数であり、実施の際に適宜調整して決められる定数である。
【００６６】
【数１】
【００６７】
要素ｂｉの体積（又は表面積）Ｉ１（ｂｉ）は、要素ｂｉを構成するメッシュの頂点座標により容易に計算できる。（尚、ここで体積又は表面積としたのは、交通標識のように体積が０で表面積が有限値の要素も存在するためである。）
【００６８】
要素ｂｉの複雑さＩ２（ｂｉ）は、次のようにして計算される。
【００６９】
（ア）まず、要素ｂｉを構成するｋ個のメッシュの面の単位法線ベクトルを求める。ここで、要素ｂｉを構成するｋ個のメッシュの面の集合をΞ（ｂｉ）＝｛ξ１（ｂｉ），…，ξｋ（ｂｉ）｝と記す。面ξｉ（∈Ξ（ｂｉ））の単位法線ベクトルの集合をＮ＝｛ｎ１，…，ｎｋ｝と記す。単位法線ベクトルの計算は、各メッシュの頂点座標に基づき容易に計算することができる。
【００７０】
（イ）次に、単位法線ベクトルの集合をＮから、基準となる単位法線ベクトル（以下「基準法線ベクトル」という。）を任意に一つ選択する。ここでは、基準法線ベクトルをｎ１とする。
【００７１】
（ウ）次に、基準法線ベクトルｎ１とその他の単位法線ベクトルとの内積の分散σ２を式（２）により求め、これを要素ｂｉの複雑さＩ２とする。
【００７２】
【数２】
【００７３】
属性Ｉ３（ｂｉ）は、要素ｂｉの視認性によって定まる重要度パラメータであり、式（３）により表される。
【００７４】
【数３】
【００７５】
ここで、ｈ（ｂ）は要素ｂの高さを表す。ｈ（ｂａｒ）は要素ｂｉからの距離が所定の範囲内にある建物要素の高さの平均値を表す。ｂｎｅは要素ｂｉの最も近隣の建物要素を表す。ｄ（ｂｉ，ｂｎｅ）は、要素ｂｉと要素ｂｉの最も近隣の要素との間の距離を表す。また、ａ１，ａ２，ａ３は重み係数であり、適宜定められる定数値である。
【００７６】
属性Ｉ３（ｂｉ）は、要素ｂｉが交差点の角に面する場合、周りの建物要素との高さの平均と当該要素ｂｉの高さの差が大きい場合、及び要素ｂｉに隣接する建物要素がない場合に大きな値を採る。
【００７７】
このようにして、要素ｂｉの複雑さ及び属性が数値化され、重要度Ｉ（ｂｉ）は式（１）の線形和で表される。
【００７８】
ステップＳ１３において、要素分類手段１３は、重要度Ｉ（ｂｉ）が所定の閾値ＴＩよりも大きいか否かを判定することにより、要素ｂｉを重要要素又は細瑣要素に分類する。ここで、Ｉ（ｂｉ）＞ＴＩならば、要素分類手段１３は要素ｂｉを重要要素と判定し、重要要素ｂｉを重要要素記憶手段１４に一時保存し（ステップＳ１４）、ステップＳ１８へ移行する。Ｉ（ｂｉ）≦ＴＩならば、要素分類手段１３は要素ｂｉを細瑣要素と判定し、ステップＳ１５へ移行する。
【００７９】
ステップＳ１５において、要素分類手段１３は、更に細瑣要素ｂｉを、「道路」，「交通案内標識」，「小物体」，「建物」の何れかに分類する。以下、この細瑣要素ｂｉの小分類をＵｉで記す。
【００８０】
ここで、要素分類手段１３による細瑣要素ｂｉの小分類Ｕｉの決定は以下のようにして実行される。
【００８１】
（ア）細瑣要素ｂｉのテクスチャを参照し、矢印、斜線、横断歩道、ゼブラゾーン等の道路に特有の所定のテクスチャが検出された場合、当該細瑣要素ｂｉの小分類Ｕｉは「道路」であるとする。
【００８２】
上記テクスチャが検出されない場合であっても、当該細瑣要素ｂｉの標高が所定の閾値Ｔlev以下であり且つ上記式（２）で算出された分散値σ２（ｎ）が所定の閾値Ｔσ以下である場合、当該細瑣要素ｂｉの小分類Ｕｉは「道路」であるとする。すなわち、標高が低く、かつ、分散値σ２（ｎ）が小さい細瑣要素は、地面に近く平らであると判断されるので、そのような細瑣要素は「道路」であるとする。
【００８３】
（イ）上記式（２）で算出された細瑣要素ｂｉの分散値σ２（ｎ）が０である場合、以下の３つの条件が満たされていれば、細瑣要素ｂｉの小分類Ｕｉは「交通案内標識」であるとする。
【００８４】
（ａ）細瑣要素ｂｉに張られるテクスチャが２色（青と白など）からなる。
（ｂ）細瑣要素ｂｉの法線ｎが地面（基準面）とほぼ平行である。
（ｃ）細瑣要素ｂｉの下端が地面に接していない（すなわち、空中に吊り下げられている）。
【００８５】
（ウ）細瑣要素ｂｉの体積（又は表面積）が所定の閾値ＴＳ以下の場合、その細瑣要素ｂｉの小分類Ｕｉは「小物体」であるとする。このような小物体としては、例えば、看板やポストなどが該当する。
【００８６】
（エ）上記（ア）〜（ウ）の何れでもない場合、その細瑣要素ｂｉの小分類Ｕｉは「建物」であるとする。
【００８７】
以上のようにして、すべての細瑣要素ｂｉの小分類Ｕｉが決定される。
【００８８】
ステップＳ１６において、要素分類手段１３は細瑣要素ｂｉ及びその小分類Ｕｉを細瑣要素記憶手段１５へ一時保存する。
【００８９】
ステップＳ１７において、幾何情報簡略化手段１６は、細瑣要素ｂｉの簡略化を以下のようにして行う。
【００９０】
（１）道路と交通標識の簡略化
細瑣要素ｂｉの小分類Ｕｉが「道路」又は「交通案内標識」の場合、その細瑣要素ｂｉは体積０の平面又は曲面である。この場合、面を構成する辺上にあるメッシュの頂点のみを残し、面内にあるメッシュの頂点をすべて削除する。また、面を構成する辺に直線部分がありその直線の両端以外にメッシュの頂点が存在する場合、そのような頂点もすべて削除する。そして、残った頂点のみでメッシュの再構成を行い、簡略化された細瑣要素ｂｉのメッシュを生成する。
【００９１】
（２）小物体の簡略化
上記ステップＳ１５において小分類Ｕｉが「小物体」とされた細瑣要素はすべて削除する。
【００９２】
（３）建物の簡略化
尚、上記ステップＳ１５において小分類Ｕｉが「建物」とされた細瑣要素（以下「建物要素」という。）については、相隣接する建物要素同士の統合処理を行うが、この処理は、後のステップＳ１９において行われる。
【００９３】
ステップＳ１８において、メッシュ記憶手段１内の全要素ｂｉについての上記一連の処理（Ｓ１１〜Ｓ１７）が終了していなければ、ステップＳ１１に戻る。終了していれば、ステップＳ１９へ移行する。
【００９４】
ステップＳ１９においては、グループ化手段１７及び要素結合手段１８により、細瑣要素記憶手段１５に記憶された建物要素の統合処理が行われる。この建物要素の統合処理については、この後で更に詳細に説明する。建物要素の統合処理により、細瑣要素は更に簡略化される。
【００９５】
ステップＳ２０において、簡略化メッシュ出力手段１９は、重要要素記憶手段１４に記憶された重要要素と、細瑣要素記憶手段１５に記憶された簡略化された細瑣要素を読み出して、簡略化メッシュ記憶手段４に保存し、簡略化テクスチャの生成アルゴリズムを終了する。
【００９６】
〔建物要素の統合処理〕
次に、上記ステップＳ１９における建物要素の統合処理について更に詳細に説明する。
【００９７】
図４は、建物要素の統合処理の統合処理の全体の流れを表すフローチャートである。
【００９８】
まず、ステップＳ３１において、グループ化手段１７は、細瑣要素記憶手段１５に記憶された建物要素を読み出して、互いに近接する建物要素を同じグループとしてグループ分けを行う。以下では、建物要素のグループをＧｉ、グループＧｉに属する建物要素をｂi,jと記す。Ｇｉ＝｛ｂi,j｝である。
【００９９】
ステップＳ３２において、要素結合手段１８は、１つの建物要素のグループＧｉを取り出す。そして、ステップＳ３３において、グループＧｉ内の建物要素の結合処理を行う（図５参照）。
【０１００】
次いで、ステップＳ３４において、すべてのグループについて建物要素の結合処理が行われていなければ、ステップＳ３２に戻り、次のグループについての処理を行う。すべてのグループについて建物要素の結合処理が行われた場合は、建物要素の統合処理を終了する。
【０１０１】
図５は、ステップＳ３２における建物要素の結合処理の流れを表すフローチャートである。ここでは、建物要素のグループをＧｉ、グループＧｉに属する建物要素をｂｉ,ｊ、建物要素をｂｉ,ｊに属するメッシュの頂点をｐｉ,ｊ,ｋと記す。
【０１０２】
まず、ステップＳ４１において、投影頂点決定手段２１は、グループＧｉに属するすべての要素ｂｉ，ｊ（∀ｂｉ，ｊ∈Ｇｉ）について、地上にある頂点ｐｉ,ｊ,ｋを抽出する（図５（ｂ）参照）。ここで、地上にあるか否かは、各頂点の高さの座標が、予め定められた基準面（地上面）の高さに一致するか否かによって判定することができる。抽出された頂点集合｛ｐｉ,ｊ,ｋ｝により構成される多角形は、グループをＧｉの各建物要素を地上に投影した地上投影図形である。
【０１０３】
ステップＳ４２において、投影図形生成手段２２は、抽出されたすべての頂点ｐｉ,ｊ,ｋから、折れ曲がり点以外の頂点を除去する。すなわち、抽出されたすべての頂点ｐｉ,ｊ,ｋにより構成される多角形の各直線部分について、その直線部分の両端点以外にメッシュの頂点が存在すれば、その頂点は冗長であるため除去する（図５（ｃ）参照）。
【０１０４】
ステップＳ４３において、投影図形生成手段２２は、残った頂点｛ｐｉ,ｊ,ｋ｝により構成される多角形について凸包（convex hull）を求める。これを新たな結合要素ｂｉの地上投影図形Ｓとする（図５（ｄ）参照）。
【０１０５】
ステップＳ４４において、高さ決定手段２３は、グループをＧｉの各建物要素の高さから、新たな結合要素ｂｉの高さｈ（ｂｉ）を決定する。この場合、高さｈ（ｂｉ）は、グループをＧｉの各建物要素の高さの最大値、平均値等として決定される。
【０１０６】
ステップＳ４５において、結合要素生成手段２４は、地上投影図形Ｓを上空に向かって高さｈ（ｂｉ）だけ引き延ばした多角柱を生成し、これを結合要素ｂｉとして、細瑣要素記憶手段１５に保存する。
【０１０７】
以上のような処理により、立体地図の詳細メッシュが簡略化され、大幅にデータ量を削減することができる。また、要素の重要度に応じて、重要度の低い物を視認性を確保しつつメッシュの削減を行うため、立体地図の視認性が低下することもない。むしろ、余分な要素が削減されるため地図構成がシンプルとなり、視認性を向上させる効果が期待できる。
【０１０８】
（３）簡略化テクスチャの生成アルゴリズム（ステップＳ２）
最後に、上記ステップＳ２において行われる簡略化テクスチャの生成処理についての説明を行う。
【０１０９】
まず、テクスチャ簡略化モジュール５は、要素分類手段１３により生成される各要素の分類を参照し、重要要素と、細瑣要素の中の「道路」、「交通案内標識」、及び「建物」のテクスチャを順次テクスチャ記憶手段２から読み出す。そして、読み出された各テクスチャについて以下のテクスチャ簡略化アルゴリズムを実行することによって各テクスチャの簡略化を行う。
【０１１０】
図６は、簡略化テクスチャの生成アルゴリズム（ステップＳ２）の全体の流れを表すフローチャートである。
【０１１１】
まず、ステップＳ５１において、領域分割手段２７は、テクスチャ画像にＳｏｂｅｌフィルタを適用して特徴画像を生成する。次に、ステップＳ５２において、特徴画像に対してＨｏｕｇｈ変換を行い、直線部分を検出する。そして、得られた直線を用いて、原画増（テクスチャ）を複数の閉領域｛ｓｉ｝に領域分割する。以下、代表色決定手段２８は、分割されたそれぞれの領域で代表色を決定していく。
【０１１２】
ステップＳ５４において、代表色決定手段２８は、一つの閉領域ｓｉを選択する。そして、ステップＳ５５において、閉領域ｓｉの代表色｛Ｃｉ（ｊ）｝を決定する。ここで、代表色は複数の色が決定される。この代表色決定処理の詳細については後述する。
【０１１３】
次に、ステップＳ５６において、色置換手段２９は、閉領域ｓｉ内の各画素について、その画素の色に対して色空間距離が最も近い代表色を選択し、その画素の色を選択した代表色で置換する。これにより、閉領域ｓｉ内のテクスチャは代表色｛Ｃｉ（ｊ）｝の要素数に減色される。
【０１１４】
ステップＳ５７において、すべての閉領域｛ｓｉ｝について上記ステップＳ５４〜Ｓ５６の処理を行ったか否かを判定し、行っていないものがあれば、その閉領域について処理を行うべくステップＳ５４に戻る。すべての閉領域｛ｓｉ｝について上記ステップＳ５４〜Ｓ５６の処理が終了すれば、簡略化テクスチャの生成アルゴリズムを終了する。
【０１１５】
次に、上述のステップＳ５５における代表色決定処理の詳細について説明する。
【０１１６】
〔代表色決定処理〕
図７は、代表色決定処理を表すフローチャートである。
【０１１７】
まず、ステップＳ６１において、ヒストグラム生成手段３０は、閉領域ｓｉの色ヒストグラムＨｉ＝｛Ｈｉ（Ｃ）｝を生成する。ここで、Ｃは色を表し、Ｈｉ（Ｃ）は閉領域ｓｉにおける色Ｃの度数を表す。
【０１１８】
ステップＳ６２において、ピーク抽出手段３１は、色ヒストグラムＨｉから度数のピークを抽出する。以下、このピークの集合をＱｉ＝｛ｑｉ（Ｃ）｝と記す。ｑｉは各ピーク点を表す。
【０１１９】
ステップＳ６３において、ピーク抽出手段３１は、ピーク集合Ｑｉの各ピークの中から、度数Ｈｉ（Ｃｊ）が最大のピークｑｉ（Ｃｊ）を抽出する。このピークｑｉ（Ｃｊ）に対応する色Ｃｊを第０番目の代表色Ｃｉ（０）とする。そして既に選択されたピークｑｉ（Ｃｊ）は、ピーク集合Ｑｉから削除する。すなわち、Ｑｉ←Ｑｉ−｛ｑｉ（Ｃｊ）｝として集合Ｑｉを更新する。
【０１２０】
ステップＳ６４において、代表色選出手段３２は、ピーク集合Ｑｉの各ピークｑｊ（∈Ｑｉ）の度数Ｈｉ（Ｃｊ）を、最大度数Ｈｉ（Ｃｉ（０））で規格化する（式（６））。規格化された度数はＲｉ（Ｃｊ）と記す。そして、ステップＳ６５で、内部変数として保持している選択色番号ｎを０に設定する。
【０１２１】
【数４】
【０１２２】
ステップＳ６６において、代表色選出手段３２は、ピーク集合Ｑｉの各ピークｑｊ（∈Ｑｉ）のうち、度数Ｒｉ（Ｃｊ）が最大の色Ｃｊを抽出する。
【０１２３】
ステップＳ６７において、代表色選出手段３２は、抽出した色Ｃｊについて、既に決定されている各代表色からの色空間における最短距離ｄｊを式（７）により計算する。
【０１２４】
【数５】
【０１２５】
ステップＳ６８において、代表色選出手段３２は、抽出色Ｃｊについての評価値ｘｊを式（８）により計算する。式（８）より、評価値ｘｊは最短距離ｄｊと度数Ｒｉ（Ｃｊ）との加重平均とされている。ｗ１，ｗ２は重み係数であり、適当な定数値に設定される。すなわち、既決定の代表色との最短距離ｄｊが大きいほど評価値ｘｊは大きくなり、また、度数Ｒｉ（Ｃｊ）が大きいほど評価値ｘｊは大きくなる。
【０１２６】
【数６】
【０１２７】
ここで、評価値ｘｊに既決定の代表色との最短距離ｄｊが考慮されている理由は、選択される代表値同士が近似色ばかりになることをなるべく防止することを意図したものである。近似色ばかりが選択されると、閉領域ｓｉは単色ですりつぶされたような状態となり、もとのテクスチャの情報が殆ど失われて視認性を下げるおそれがある。
【０１２８】
ステップＳ６８において、代表色選出手段３２は、評価値ｘｊと閾値ｘｔｈとを比較する。ｘｊ＞ｘｔｈであれば、代表色選出手段３２は抽出色Ｃｊを代表色Ｃｉ（ｎ）に決定する（ステップＳ７０）。ｘｊ≦ｘｔｈであれば、抽出色Ｃｊは捨てて、ステップＳ７１へ移る。
【０１２９】
ステップＳ７１において、代表色選出手段３２は、ピーク集合Ｑｉから、既評価のピークｑｉ（Ｃｊ）を削除する。すなわち、Ｑｉ←Ｑｉ−｛ｑｉ（Ｃｊ）｝として集合Ｑｉを更新する。
【０１３０】
ステップＳ７２において、代表色選出手段３２は、選択色番号ｎが規定値ｎ０に達したか否かを判定する。達していなければ、ステップＳ６６に戻る。達していれば、代表色決定処理を終了する。
【０１３１】
以上の処理により、ｎ０個の代表色が決定される。決定された代表色は、閉領域ｓｉの色の減色化に使用されるものであり、できるだけ多数の画素で使用され、できるだけ色空間上の距離が互いに離れた色が選択される。
【図面の簡単な説明】
【０１３２】
【図１】本発明の実施例１に係る立体地図簡略化装置の構成を表すブロック図である。
【図２】実施例１の立体地図簡略化方法の全体の流れを表す図である。
【図３】簡略化メッシュの生成アルゴリズム（ステップＳ１）の全体の流れを表すフローチャートである。
【図４】建物要素の統合処理の統合処理の全体の流れを表すフローチャートである。
【図５】ステップＳ３２における建物要素の結合処理の流れを表すフローチャートである。
【図６】簡略化テクスチャの生成アルゴリズム（ステップＳ２）の全体の流れを表すフローチャートである。
【図７】代表色決定処理を表すフローチャートである。
【図８】特許文献１の方法による立体地図の表示例である。
【図９】非特許文献１における建物データの例を示す図である。
【符号の説明】
【０１３３】
１ メッシュ記憶手段
２ テクスチャ記憶手段
３ メッシュ簡略化モジュール
４ 簡略化メッシュ記憶手段
５ テクスチャ簡略化モジュール
６ 簡略化テクスチャ記憶手段
７ テクスチャ・マッピング手段
８ 景観データ記憶手段
９ 出力手段
１１ 要素抽出手段
１２ 重要度計算手段
１３ 要素分類手段
１４ 重要要素記憶手段
１５ 細瑣要素記憶手段
１６ 幾何情報簡略化手段
１７ グループ化手段
１８ 要素結合手段
１９ 簡略化メッシュ出力手段
２１ 投影頂点決定手段
２２ 投影図形生成手段
２３ 高さ決定手段
２４ 結合要素生成手段
２５ 重要テクスチャ生成手段
２７ 領域分割手段
２８ 代表色決定手段
２９ 色置換手段
３０ ヒストグラム生成手段
３１ ピーク抽出手段
３２ 代表色選出手段
【特許請求の範囲】
【請求項１】
立体地図画像を簡略化する立体地図簡略化装置であって、
立体地図画像を構成する各要素について、当該要素の重要度を計算する重要度計算手段；
地上に配置された要素のうち、前記重要度が所定の閾値よりも小さい要素について、互いに近接する要素が同じグループとなるようにグループ分けするグループ化手段；
及び、前記各グループに属する要素を結合し、１つの結合要素とする要素結合手段；
を備えた立体地図簡略化装置。
【請求項２】
前記要素結合手段は、
前記各グループについて、当該グループに属する各要素を地面に投影し、投影した２次元投影図形の頂点を求める投影頂点決定手段；
前記２次元投影図形の凸包を求め、これを当該要素の新たな地上投影図形Ｓとする地上投影図形生成手段；
前記グループに属する各要素の高さから当該グループの要素の高さの代表値を決定する高さ決定手段；
及び、前記地上投影図形Ｓを前記高さの代表値だけ高さ方向に引き延ばすことにより、前記結合要素を生成する結合要素生成手段；
を備えていることを特徴とする請求項１記載の立体地図簡略化装置。
【請求項３】
前記重要度計算手段は、
要素を構成するメッシュのうち一のメッシュに対して、当該メッシュの単位法線ベクトルと他のメッシュの単位法線ベクトルとの内積を、要素を構成するすべてのメッシュについて積算した値である面複雑性が含まれる重要度を算出することを特徴とする請求項１又は２記載の立体地図簡略化装置。
【請求項４】
立体地図の各要素に属するテクスチャ画像を簡略化する立体地図簡略化装置であって、
テクスチャの原画像を複数の閉領域に分割する領域分割手段；
前記各閉領域に対して代表色を決定する代表色決定手段；
前記各閉領域の色を前記代表色で置き換える色置換手段；
を有し、
前記代表色決定手段は、
当該閉領域の色ヒストグラムＨ＝｛Ｈ（Ｃ）｝（Ｃは色を表す。）を生成するヒストグラム生成手段；
前記色ヒストグラムから度数のピークの集合（以下「ピーク集合」という。）Ｐ＝｛Ｐ（Ｃｊ）｝を抽出するピーク抽出手段；
前記ピーク集合Ｐから、度数が大きい順で且つより度数が大きい色との色空間上の距離が所定の閾値以上となるようにｎ０個の色を選出し代表色に決定する代表色選出手段；
を備えたことを特徴とする立体地図簡略化装置。
【請求項５】
立体地図画像を簡略化する立体地図簡略化方法であって、
立体地図画像を構成する各要素について、当該要素の重要度を計算する重要度計算ステップ；
地上に配置された要素のうち、前記重要度が所定の閾値よりも小さい要素について、互いに近接する要素が同じグループとなるようにグループ分けするグループ化ステップ；
及び、前記各グループに属する要素を結合し、１つの結合要素とする要素結合ステップ；
を有する立体地図簡略化方法。
【請求項６】
前記要素結合ステップにおいて、
前記各グループについて、当該グループに属する各要素を地面に投影し、投影した２次元投影図形の頂点を求める投影頂点決定ステップ；
前記２次元投影図形の凸包を求め、これを当該要素の新たな地上投影図形Ｓとする地上投影図形生成ステップ；
前記グループに属する各要素の高さから当該グループの要素の高さの代表値を決定する高さ決定ステップ；
及び、前記地上投影図形Ｓを前記高さの代表値だけ高さ方向に引き延ばすことにより、前記結合要素を生成する結合要素生成ステップ；
を有することを特徴とする請求項５記載の立体地図簡略化方法。
【請求項７】
前記重要度計算ステップでは、
要素を構成するメッシュのうち一のメッシュに対して、当該メッシュの単位法線ベクトルと他のメッシュの単位法線ベクトルとの内積を、要素を構成するすべてのメッシュについて積算した値である面複雑性が含まれる重要度を算出することを特徴とする請求項５又は６記載の立体地図簡略化方法。
【請求項８】
立体地図の各要素に属するテクスチャ画像を簡略化する立体地図簡略化方法であって、
テクスチャの原画像を複数の閉領域に分割する領域分割ステップ；
前記各閉領域に対して代表色を決定する代表色決定ステップ；
前記各閉領域の色を前記代表色で置き換える色置換ステップ；
を有し、
前記代表色決定ステップにおいては、
当該閉領域の色ヒストグラムＨ＝｛Ｈ（Ｃ）｝（Ｃは色を表す。）を生成するヒストグラム生成ステップ；
前記色ヒストグラムから度数のピークの集合（以下「ピーク集合」という。）Ｐ＝｛Ｐ（Ｃｊ）｝を抽出するピーク抽出ステップ；
前記ピーク集合Ｐから、度数が大きい順で且つより度数が大きい色との色空間上の距離が所定の閾値以上となるようにｎ０個の色を選出し代表色に決定する代表色選出ステップ；
を有していることを特徴とする立体地図簡略化方法。
【請求項９】
請求項５乃至８の何れか一の立体地図簡略化方法を実行するプログラム。
【請求項１】
立体地図画像を簡略化する立体地図簡略化装置であって、
立体地図画像を構成する各要素について、当該要素の重要度を計算する重要度計算手段；
地上に配置された要素のうち、前記重要度が所定の閾値よりも小さい要素について、互いに近接する要素が同じグループとなるようにグループ分けするグループ化手段；
及び、前記各グループに属する要素を結合し、１つの結合要素とする要素結合手段；
を備えた立体地図簡略化装置。
【請求項２】
前記要素結合手段は、
前記各グループについて、当該グループに属する各要素を地面に投影し、投影した２次元投影図形の頂点を求める投影頂点決定手段；
前記２次元投影図形の凸包を求め、これを当該要素の新たな地上投影図形Ｓとする地上投影図形生成手段；
前記グループに属する各要素の高さから当該グループの要素の高さの代表値を決定する高さ決定手段；
及び、前記地上投影図形Ｓを前記高さの代表値だけ高さ方向に引き延ばすことにより、前記結合要素を生成する結合要素生成手段；
を備えていることを特徴とする請求項１記載の立体地図簡略化装置。
【請求項３】
前記重要度計算手段は、
要素を構成するメッシュのうち一のメッシュに対して、当該メッシュの単位法線ベクトルと他のメッシュの単位法線ベクトルとの内積を、要素を構成するすべてのメッシュについて積算した値である面複雑性が含まれる重要度を算出することを特徴とする請求項１又は２記載の立体地図簡略化装置。
【請求項４】
立体地図の各要素に属するテクスチャ画像を簡略化する立体地図簡略化装置であって、
テクスチャの原画像を複数の閉領域に分割する領域分割手段；
前記各閉領域に対して代表色を決定する代表色決定手段；
前記各閉領域の色を前記代表色で置き換える色置換手段；
を有し、
前記代表色決定手段は、
当該閉領域の色ヒストグラムＨ＝｛Ｈ（Ｃ）｝（Ｃは色を表す。）を生成するヒストグラム生成手段；
前記色ヒストグラムから度数のピークの集合（以下「ピーク集合」という。）Ｐ＝｛Ｐ（Ｃｊ）｝を抽出するピーク抽出手段；
前記ピーク集合Ｐから、度数が大きい順で且つより度数が大きい色との色空間上の距離が所定の閾値以上となるようにｎ０個の色を選出し代表色に決定する代表色選出手段；
を備えたことを特徴とする立体地図簡略化装置。
【請求項５】
立体地図画像を簡略化する立体地図簡略化方法であって、
立体地図画像を構成する各要素について、当該要素の重要度を計算する重要度計算ステップ；
地上に配置された要素のうち、前記重要度が所定の閾値よりも小さい要素について、互いに近接する要素が同じグループとなるようにグループ分けするグループ化ステップ；
及び、前記各グループに属する要素を結合し、１つの結合要素とする要素結合ステップ；
を有する立体地図簡略化方法。
【請求項６】
前記要素結合ステップにおいて、
前記各グループについて、当該グループに属する各要素を地面に投影し、投影した２次元投影図形の頂点を求める投影頂点決定ステップ；
前記２次元投影図形の凸包を求め、これを当該要素の新たな地上投影図形Ｓとする地上投影図形生成ステップ；
前記グループに属する各要素の高さから当該グループの要素の高さの代表値を決定する高さ決定ステップ；
及び、前記地上投影図形Ｓを前記高さの代表値だけ高さ方向に引き延ばすことにより、前記結合要素を生成する結合要素生成ステップ；
を有することを特徴とする請求項５記載の立体地図簡略化方法。
【請求項７】
前記重要度計算ステップでは、
要素を構成するメッシュのうち一のメッシュに対して、当該メッシュの単位法線ベクトルと他のメッシュの単位法線ベクトルとの内積を、要素を構成するすべてのメッシュについて積算した値である面複雑性が含まれる重要度を算出することを特徴とする請求項５又は６記載の立体地図簡略化方法。
【請求項８】
立体地図の各要素に属するテクスチャ画像を簡略化する立体地図簡略化方法であって、
テクスチャの原画像を複数の閉領域に分割する領域分割ステップ；
前記各閉領域に対して代表色を決定する代表色決定ステップ；
前記各閉領域の色を前記代表色で置き換える色置換ステップ；
を有し、
前記代表色決定ステップにおいては、
当該閉領域の色ヒストグラムＨ＝｛Ｈ（Ｃ）｝（Ｃは色を表す。）を生成するヒストグラム生成ステップ；
前記色ヒストグラムから度数のピークの集合（以下「ピーク集合」という。）Ｐ＝｛Ｐ（Ｃｊ）｝を抽出するピーク抽出ステップ；
前記ピーク集合Ｐから、度数が大きい順で且つより度数が大きい色との色空間上の距離が所定の閾値以上となるようにｎ０個の色を選出し代表色に決定する代表色選出ステップ；
を有していることを特徴とする立体地図簡略化方法。
【請求項９】
請求項５乃至８の何れか一の立体地図簡略化方法を実行するプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００６−２８４７０４（Ｐ２００６−２８４７０４Ａ）
【公開日】平成１８年１０月１９日（２００６．１０．１９）
【国際特許分類】
【出願番号】特願２００５−１０１７５８（Ｐ２００５−１０１７５８）
【出願日】平成１７年３月３１日（２００５．３．３１）
【出願人】（８０２００００３１）財団法人北九州産業学術推進機構 (187)
【Ｆターム（参考）】
【公開日】平成１８年１０月１９日（２００６．１０．１９）
【国際特許分類】
【出願日】平成１７年３月３１日（２００５．３．３１）
【出願人】（８０２００００３１）財団法人北九州産業学術推進機構 (187)
【Ｆターム（参考）】
[ Back to top ]