(57)【要約】【課題】３次元データや画像データの特徴量を抽出し、抽出した特徴量を用いた解析により、データを構造化して管理するインデックスの作成が可能な解析装置を提供する。【解決手段】処理対象の形状をデータ化した対象データを記憶する記憶部４と、対象データから形状の特徴量を抽出し、対象データを特徴量により特定される形状の特徴部毎のデータに分類するデータ解析部２と、データ解析部２の分類結果に基づいて特徴部毎のデータ間の階層構造を規定し、この階層構造に従って特徴部毎のデータが階層的に参照されるインデックス情報を生成する管理構造生成部３とを備える。【選択図】図１
2007293597.tif 000002
【特許請求の範囲】
【請求項１】
処理対象の形状をデータ化した対象データを記憶する記憶部と、
前記対象データから前記形状の特徴量を抽出し、前記対象データを前記特徴量により特定される前記形状の特徴部毎のデータに分類するデータ解析部と、
前記データ解析部の分類結果に基づいて前記特徴部毎のデータ間の階層構造を規定し、この階層構造に従って前記特徴部毎のデータが階層的に参照されるインデックス情報を生成する管理構造生成部とを備えた解析装置。
【請求項２】
管理構造生成部は、特徴部毎のデータが複数のグループに分類され、前記グループ間に規定された階層構造に従って前記特徴部毎のデータが階層的に参照されると共に、前記特徴部間の境界部分に関連するデータに基づいて前記特徴部を表す図形要素に関するデータが参照されるインデックス情報を生成することを特徴とする請求項１記載の解析装置。
【請求項３】
データ解析部は、
対象データから特徴量を抽出する特徴量抽出手段と、
前記対象データを前記特徴量により特定される特徴部毎のグループに分類するグループ化手段とを備え、
管理構造生成部は、
前記グループ化手段の分類結果に基づいて前記グループ間の階層構造を規定する構造化部と、
前記階層構造に従って前記特徴部毎のデータが階層的に参照されるインデックス情報を生成するインデックス生成部とを備えたことを特徴とする請求項１記載の解析装置。
【請求項４】
インデックス生成部は、
グループ毎に分類された特徴部間の境界部分に関連するデータのインデックス情報を生成するグループインデックス生成手段と、
前記グループ毎に分類された特徴部を表す図形要素に関するデータのインデックス情報を生成する３次元データインデックス生成手段とを備えたことを特徴とする請求項３記載の解析装置。
【請求項５】
データ解析部は、処理対象の形状の大域的な特性を表す特徴量を対象データから抽出し、前記対象データを前記特徴量により特定される前記形状の特徴部毎のデータに分類することを特徴とする請求項１記載の解析装置。
【請求項６】
データ解析部は、対象データを複数の分割データに分割し、前記分割データにより表される形状の特徴量を抽出して、前記分割データを前記特徴量により特定される前記形状の特徴部毎のデータに分類し、
管理構造生成部は、前記分割データ間及び前記特徴部毎のデータ間の階層構造を規定し、この階層構造に従って前記分割データ及び前記特徴部毎のデータが階層的に参照されるインデックス情報を生成することを特徴とする請求項１記載の解析装置。
【請求項７】
処理対象の形状をデータ化した対象データを記憶する記憶部と、
前記対象データから前記形状の特徴量を抽出し、前記対象データを前記特徴量により特定される前記形状の特徴部毎のデータに分類するデータ解析部と、
前記データ解析部の分類結果に基づいて前記特徴部毎のデータ間の階層構造を規定し、この階層構造に従って前記特徴部毎のデータが階層的に参照されるインデックス情報を生成する管理構造生成部と、
前記処理対象の形状における指定部位に関するデータを検索するにあたり、前記インデックス情報により前記特徴部毎のデータを参照して前記指定部位に関するデータを検索する検索部とを備えた検索装置。
【請求項８】
処理対象の形状をデータ化した対象データを記憶すると共に、前記形状の特徴部毎のデータ間の階層構造が規定され、この階層構造に従って前記特徴部毎のデータが階層的に参照されるインデックス情報を記憶する記憶部と、
前記処理対象の形状における指定部位に関するデータを検索するにあたり、前記インデックス情報により前記特徴部毎のデータを参照して前記指定部位に関するデータを検索する検索部とを備えた検索装置。
【請求項９】
検索部は、
インデックス情報を用いて特徴部毎のデータにおける指定部位及びその近傍部に関するデータを検索する近傍検索手段と、
インデックス情報を用いて処理対象の形状に指定された閉領域内部及び前記閉領域の境界と交差する部分に関するデータを検索する閉領域検索手段とを備えたことを特徴とする請求項７または請求項８記載の検索装置。
【請求項１０】
記憶部は、特徴部毎のデータが複数のグループに分類され、前記グループ間に規定された階層構造に従って前記特徴部毎のデータが階層的に参照されると共に、前記特徴部間の境界部分に関連するデータに基づいて前記特徴部を表す図形要素に関するデータが参照されるインデックス情報を記憶し、
検索部は、前記インデックス情報を用いて、処理対象の形状における指定部位に関するデータを検索することを特徴とする請求項７または請求項８記載の検索装置。
【請求項１１】
処理対象の形状をデータ化した対象データを記憶する記憶部と、
前記対象データから前記形状の特徴量を抽出し、前記対象データを前記特徴量により特定される前記形状の特徴部毎のデータに分類するデータ解析部と、
前記データ解析部の分類結果に基づいて前記特徴部毎のデータ間の階層構造を規定し、この階層構造に従って前記特徴部毎のデータが階層的に参照されるインデックス情報を生成する管理構造生成部と、
前記処理対象の形状における指定部位に関するデータを検索するにあたり、前記インデックス情報により前記特徴部毎のデータを参照して前記指定部位に関するデータを検索する検索部と、
前記検索部により検索されたデータを用いて前記処理対象の形状に関する計測を行う計測部とを備えた計測装置。
【請求項１２】
処理対象の形状をデータ化した対象データを記憶すると共に、前記形状の特徴部毎のデータ間の階層構造が規定され、この階層構造に従って前記特徴部毎のデータが階層的に参照されるインデックス情報を記憶する記憶部と、
前記処理対象の形状における指定部位に関するデータを検索するにあたり、前記インデックス情報により前記特徴部毎のデータを参照して前記指定部位に関するデータを検索する検索部と、
前記検索部により検索されたデータを用いて前記処理対象の形状に関する計測を行う計測部とを備えた計測装置。
【請求項１３】
計測部は、
検索部により検索されたデータを用いて、処理対象の形状における、指定線分での断面を含む平面と交差する部位に関するデータを取得する交差データ取得手段と、
前記交差データ取得手段により取得されたデータを用いて処理対象の形状に関する３次元計測を行う３次元計測手段とを備えたことを特徴とする請求項１１または請求項１２記載の計測装置。
【請求項１４】
記憶部は、特徴部毎のデータが複数のグループに分類され、前記グループ間に規定された階層構造に従って前記特徴部毎のデータが階層的に参照されると共に、前記特徴部間の境界部分に関連するデータに基づいて前記特徴部を表す図形要素に関するデータが参照されるインデックス情報を記憶し、
検索部は、前記インデックス情報を用いて、処理対象の形状における指定部位に関するデータを検索し、
計測部は、
前記検索部により検索されたデータを用いて前記処理対象の形状に関する計測を行うことを特徴とする請求項１１または請求項１２記載の計測装置。
【請求項１５】
処理対象の形状をデータ化した対象データを記憶する記憶部、
前記対象データから前記形状の特徴量を抽出し、前記対象データを前記特徴量により特定される前記形状の特徴部毎のデータに分類するデータ解析部、
前記データ解析部の分類結果に基づいて前記特徴部毎のデータ間の階層構造を規定し、この階層構造に従って前記特徴部毎のデータが階層的に参照されるインデックス情報を生成する管理構造生成部としてコンピュータを機能させるプログラム。
【請求項１６】
処理対象の形状をデータ化した対象データを記憶する記憶部、
前記対象データから前記形状の特徴量を抽出し、前記対象データを前記特徴量により特定される前記形状の特徴部毎のデータに分類するデータ解析部、
前記データ解析部の分類結果に基づいて前記特徴部毎のデータ間の階層構造を規定し、この階層構造に従って前記特徴部毎のデータが階層的に参照されるインデックス情報を生成する管理構造生成部、
前記処理対象の形状における指定部位に関するデータを検索するにあたり、前記インデックス情報により前記特徴部毎のデータを参照して前記指定部位に関するデータを検索する検索部としてコンピュータを機能させるプログラム。
【請求項１７】
処理対象の形状をデータ化した対象データを記憶する記憶部、
前記対象データから前記形状の特徴量を抽出し、前記対象データを前記特徴量により特定される前記形状の特徴部毎のデータに分類するデータ解析部、
前記データ解析部の分類結果に基づいて前記特徴部毎のデータ間の階層構造を規定し、この階層構造に従って前記特徴部毎のデータが階層的に参照されるインデックス情報を生成する管理構造生成部、
前記処理対象の形状における指定部位に関するデータを検索するにあたり、前記インデックス情報により前記特徴部毎のデータを参照して前記指定部位に関するデータを検索する検索部、
前記検索部により検索されたデータを用いて前記処理対象の形状に関する計測を行う計測部としてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、画像や３次元座標データを解析する解析装置、この解析装置を用いて３次元データに関する検索を行う検索装置及びこの検索装置で検索された３次元データを用いて３次元計測を行う計測装置並びにこれら装置としてコンピュータを機能させるプログラムに関するものである。
【背景技術】
【０００２】
近年、レーザ測量技術の進展により高精度標高データの取得が可能になり、高精度３次元地図の作成が試みられている。また、現況地形の把握や土量計算等、３次元地図の活用に関する技術も文献上で開示されている。
【０００３】
例えば、特許文献１に開示される特徴的地形の判別方法では、空中写真に基づいて崩壊地や河川等の特徴的な地形を検出するにあたり、空中写真の色情報を用いて特徴的地形の候補となる領域（特異領域）を抽出したり、特異領域の３次元情報や勾配情報に基づいて特異領域を分別する。これにより、特徴的地形の判別を効率的に、かつ高精度に行うことができる。なお、３次元情報としては、例えばＴＩＮ(Trianglated Irregular Netwotk）やＤＴＭ（Digital Terrain Model）法により表現された標高を表す情報がある。
【０００４】
また、特許文献２には、ランダムな地点において３次元座標データを取得し、ランダムな点群データから作成した３次元ポリゴンデータを利用して土量計算を行う造成計画支援システムに関する技術が開示されている。
【０００５】
【特許文献１】特開２００３−１４０５４４号公報
【特許文献２】特開２００１−１４０２５７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
一般的に、広範囲の３次元データはデータ量が多く、高密度で計測された広範囲の３次元地図等はそのデータ量が膨大である。このため、業務支援システム等において３次元地図を活用する際に多くの処理時間を要するという課題がある。
【０００７】
そこで、従来から、３次元地図を活用するために３次元データの可視化技術が注目されおり、大容量の３次元データを高速に描画するためのデータ管理や表示方法が提案されている。データ管理方法としては、２次元領域をブロック領域（例えば１ｋｍ四方）に分割し、点や線等のデータを各ブロックに分類して管理する方法が広く知られている。
【０００８】
この方法では、複数のブロックに跨るデータをどちらのブロックに（或いは両方のブロックに）分類すればよいのかについて基準が不定である。なお、どちらかのブロックにもデータを分類しない場合、データを境界で分割する必要があり、データ編集が煩雑化して手間を要する。
【０００９】
また、特許文献２のような、測量や防災分野を想定したシステムが開示されているが、大容量の３次元データの中から所要の範囲に属するデータを高速に検索して抽出するための管理構造を有していない。このため、面積計算等におけるデータ取得の際、所要のデータであるか否かの判定を行う対象データ数が多くなり、検索時間が膨大となる。
【００１０】
特に、防災や土木、測量等の分野では、道路や河川流域のような他の領域に比べて重要性の高い領域が存在し、このような重要性の高い領域について面積や体積等の計測を行うことが多い。
【００１１】
また、２次元領域をブロック領域に分割してデータ管理する場合、重要性の高い部分とは無関係にデータが分類される。このため、検索領域が指定された際、必ずしも効率的な検索が行われるとは限らない。
【００１２】
この発明は、上記のような課題を解決するためになされたもので、３次元データや画像データの特徴量を抽出し、抽出した特徴量を用いた解析により、データを構造化して管理するインデックスの作成が可能な解析装置及びこの解析装置としてコンピュータを機能させるプログラムを得ることを目的とする。
【００１３】
また、この発明は、上記インデックスを利用して効率良く高速な空間検索が可能な検索装置及びこの検索装置としてコンピュータを機能させるプログラムを得ることを目的とする。
【００１４】
さらに、この発明は、３次元ポリゴンデータを用いた３次元計測を高精度かつ高速に行うことができる計測装置及びこの計測装置としてコンピュータを機能させるプログラムを得ることを目的とする。
【課題を解決するための手段】
【００１５】
この発明に係る解析装置は、処理対象の形状をデータ化した対象データを記憶する記憶部と、対象データから形状の特徴量を抽出し、対象データを特徴量により特定される形状の特徴部毎のデータに分類するデータ解析部と、データ解析部の分類結果に基づいて特徴部毎のデータ間の階層構造を規定し、この階層構造に従って特徴部毎のデータが階層的に参照されるインデックス情報を生成する管理構造生成部とを備えるものである。
【発明の効果】
【００１６】
この発明によれば、処理対象の形状として地形をデータ化した３次元データから地形の特徴量を抽出して、この特徴量により特定される地形の、例えば河川や道路等の特徴部毎のデータに当該３次元データを分類し、この分類結果に基づいて特徴部毎のデータ間の階層構造を規定して、この階層構造に従って特徴部毎のデータが階層的に参照されるインデックス情報を生成するので、河川管理や道路管理等の用途に即したデータを階層的に参照することができ、例えば本流と支流を含む或る河川に関してその流域に存在する３次元データ（ポリゴンデータ）を高速に検索できるという効果がある。
【発明を実施するための最良の形態】
【００１７】
実施の形態１．
本実施の形態１では、例えば３次元ポリゴンデータ等のような頂点の３次元座標及び頂点の接続順序が定まっている３次元データに関する解析を行い、３次元データを構造化して管理するインデックスを生成する。
【００１８】
図１は、この発明の実施の形態１による解析装置の構成を示すブロック図である。図に示すように、実施の形態１による解析装置１は、データ解析部２、管理構造生成部３、及び記憶部４を備える。また、データ解析部２は、特徴量抽出手段５及びグループ化手段６を備える。管理構造生成部３は、構造化部７及びインデックス生成部８を備える。インデックス生成部８は、グループインデックス生成手段９及び３次元データインデックス生成手段１０を有して構成される。
【００１９】
データ解析部２は、画像や３次元データ（以降、処理対象データと適宜称す）から抽出した複数種類の特徴量を解析して、処理対象データにおける３次元ポリゴンデータを、関連のある対象物を表現した３次元ポリゴンデータ毎に複数のグループに分類する。データ解析部２の特徴量抽出手段５では、処理対象データから色や形状等の特徴量を抽出する。データ解析部２のグループ化手段６は、特徴量抽出手段５により抽出された特徴量を用いて３次元のポリゴンデータを複数のグループに分類する。
【００２０】
管理構造生成部３は、データ解析部２により抽出された特徴量やグループ化の結果を用いて、３次元ポリゴンデータで表現される対象物の関連性に基づいてデータを構造化し、このデータを高速に検索して抽出するためのデータ構造（グループや３次元データに関するインデックス）を作成する。管理構造生成部３の構造化部７では、データ解析部２のグループ化手段６によりグループ化された結果を用いて隣接するグループや関連するグループをまとめ、複数種類のグループを構造化した階層構造を規定する情報を作成する。
【００２１】
管理構造生成部３のインデックス生成部８は、グループ化手段６によりグループ化されたグループ間及び３次元データに関して、頂点等の図形要素に関するデータを高速に抽出するためのインデックスを生成する。インデックス生成部８のグループインデックス生成手段９では、グループ化手段６により生成されたグループの境界となる部分に関連するデータのインデックスを生成する。インデックス生成部８の３次元データインデックス生成手段１０は、３次元データにおけるポリゴンや稜線等の図形要素に関するインデックスを生成する。
【００２２】
記憶部４は、地形や地物（道路、建物等）の３次元データ、及び航空写真等の画像のような解析対象のデータに加え、データ解析部２により処理対象データから抽出された解析結果等を記憶する。ここで、３次元データとしては、３次元座標を有する頂点及び頂点の接続順序を有したポリゴンデータがあり、三角形（ＴＩＮ法による表記を含む）や四角形、多角形の面で表現されるものがある。以降の説明では、三角形で表現されたポリゴンデータを使用する。
【００２３】
上述した、特徴量抽出手段５、グループ化手段６、構造化部７、グループインデックス生成手段９及び３次元データインデックス生成手段１０は、例えば本発明の趣旨に従う解析処理プログラムを、解析装置１を構成するコンピュータの演算処理装置に実行させてその動作を制御することにより、ソフトウエアとハードウエアとが協働した具体的な手段として実現することができる。
【００２４】
また、記憶部４については、例えば上記コンピュータに搭載されたハードディスク装置や、ドライブ装置で再生可能な記憶媒体、データ通信が可能な外部記憶装置等の記憶領域上に構成することができる。
【００２５】
なお、以下の説明において、本発明の解析装置１を具現化する上記コンピュータ自体の構成及びその基本的な機能については、当業者が当該技術分野の技術常識に基づいて容易に認識できるものであり、本発明の本質に直接関わるものではないので詳細な記載を省略する。
【００２６】
次に動作について説明する。
先ず、データ解析部２の特徴量抽出手段５が、記憶部４に格納されている画像や３次元データから特徴量を抽出する。このとき、特徴量抽出手段５では、画像や３次元形状に関する一般的な特徴量（色情報や曲率等）の他に、地形や地物の識別と領域分割が有効となるように、連続的なポリゴンの特性（大域的な特性）を考慮した特徴量を抽出する。
ここで、３次元データから抽出する特徴量の一例を以下に示す。
（１ａ）エッジの両側の面について２面がなす角度
（２ａ）近似ガウス曲率
（３ａ）ポリゴン密度
（４ａ）注目しているポリゴンの各辺の長さ
（５ａ）注目しているポリゴンに隣接しているポリゴンの頂点の存在範囲
（６ａ）注目しているポリゴンに隣接しているポリゴンの面積の特性
（７ａ）注目しているポリゴンにおける頂点の標高座標の最大値と最小値の差
（８ａ）付近の特徴稜線（形状特徴を表すポリゴン稜線）の並行性
【００２７】
なお、（１ａ）エッジの両側の面について２面がなす角度とは、３次元形状において、特徴的な稜線を抽出する際に利用される特徴量である。（２ａ）近似ガウス曲率は、形状の複雑度を求める際に利用される特徴量である。エッジの両側の面について２面がなす角度をａとすると、頂点Ｖにおける近似ガウス曲率Ｋは、下記式（１）で求めることができる。
Ｋ＝ａ／Ｓ      ・・・（１）
但し、エッジの両側の面について２面がなす角度ａとは、ａ＝２π−（Ｖに集まる面の隅の角度の和）であり、Ｓ＝（Ｖに集まる面積の和）／３である。また、Ｖに集まる面積の和とは、頂点Ｖを共通に有するポリゴンの面積の和であり、Ｖに集まる面の隅の角度とは、頂点Ｖを共通に有するポリゴン間の頂点Ｖにおける角度である。
【００２８】
（３ａ）ポリゴン密度は、形状の詳細度を調べるための特徴量であり、例えば注目するポリゴンから半径Ｒ以内に存在するポリゴンの数により求める。
（４ａ）注目しているポリゴンの各辺の長さは、注目しているポリゴンの形状特性を調べるための特徴量である。この特徴量を用いることにより、例えばポリゴンを構成する辺における最小長さの辺と最大長さの辺との比率を求めることができる。
【００２９】
（５ａ）注目しているポリゴンに隣接しているポリゴンの頂点の存在範囲は、注目しているポリゴンの付近で、地物の領域特性や同一地物内での形状特性の変化を調べるために用いる特徴量である。この特徴量により、例えば注目しているポリゴンに隣接する各ポリゴンに関して、現在注目しているポリゴンから最も離れている頂点との距離を求めることができる。
【００３０】
（６ａ）注目しているポリゴンに隣接しているポリゴンの面積の特性は、注目しているポリゴンの付近で、（５ａ）に示す特徴量の目的と同様に、地物の領域特性や同一地物内での形状特性の変化を調べるための特徴量である。この特徴量としては、例えば注目しているポリゴンの面積と隣接する各ポリゴンの面積との差分や、注目しているポリゴンの面積と隣接ポリゴンの面積との比率等がある。
【００３１】
（７ａ）注目しているポリゴンにおける頂点の標高座標の最大値と最小値の差は、地形や地物の３次元データにおいて、注目しているポリゴンの形状特性を調べるための特徴量である。地形や地物では、高さ方向の情報が有用であり、特にポリゴンを構成する頂点に関して標高値の最大値と最小値の差を特徴量として求める。
【００３２】
（８ａ）付近の特徴稜線（形状特徴を表すポリゴン稜線）の並行性は、地形や地物の３次元データにおいて、特徴稜線のうち河岸線や道路境界線等のように並行性を有する線を調べるための特徴量である。例えば、一定の長さ以上、連続している線分に関して、付近に存在する特徴稜線との距離を、線分に沿って一定間隔毎に算出する。
【００３３】
また、解析対象が画像データである場合、特徴量抽出手段５は、特徴量としてエッジや色情報、輝度等を画像から抽出する。
【００３４】
なお、処理対象データから抽出する特徴量は上記に限定するものではない。また、３次元データから（１ａ）〜（８ａ）に示す特徴量を抽出するにあたり、各特徴量の算出方法は、上記式（１）やその内容に限定されるものではない。
【００３５】
特徴量抽出手段５では、記憶部４から読み出した処理対象データから特徴量を抽出すると、この特徴量を抽出した各データに対応付けて記憶部４に格納するか、グループ化手段６に出力する処理の少なくとも一方を行う。
【００３６】
グループ化手段６は、記憶部４から特徴量を読み出すか、又は、特徴量抽出手段５から特徴量を入力すると、この特徴量を利用して３次元のポリゴンデータを複数のグループに分類する。以下、地形や地物の３次元データを解析対象とした場合における動作の具体例を説明する。
【００３７】
先ず、グループ化手段６は、特徴量抽出手段５により抽出された特徴量のうち、３次元データに関する、上述した（１ａ）、（２ａ）、（３ａ）の特徴量を用いて特徴稜線を抽出する。これにより、３次元データから、道路や河川の境界線等のような、異なる特徴量を有する領域の境界となり得る大局的な稜線を見つけることができる。
【００３８】
グループ化手段６では、３次元データから特徴稜線となる稜線を規定するデータを抽出すると、このデータに対して特徴稜線であることを示すフラグを付与して記憶部４に格納する。また、特徴稜線上に位置するポリゴンの頂点には、特徴稜線上の頂点であることを示すフラグを付与して記憶部４に格納する。
【００３９】
河川や堤防等に相当する領域では、形状変化の少ない平野部に比べると、高密度のポリゴンによって形状を詳細に表現する場合が多い。また、起伏の少ない平野部では、平野部に属するポリゴンが類似な形状で表現されるが、平野部と山岳部のように異なる特性を有する領域との境界では、ポリゴンの形状が変化する場合が多い。
【００４０】
そこで、グループ化手段６は、画像や３次元データに関する、上記（１ａ）、（２ａ）、（３ａ）以外の特徴量を用いて特徴稜線を適宜修正しながら、上記（４ａ）〜（８ａ）の特徴量を用いて付近のポリゴンの形状や面積を大域的に解析し、現在注目するポリゴンと隣接するポリゴンが同一の地物や領域の特性を有しているか否かを判定して、特徴稜線の付近のポリゴンをグループ化する。
【００４１】
また、このグループ化にあたり、グループ化手段６は、同じグループに属するポリゴンに同一の値をラベリングする。なお、グループ化において、画像から抽出した色情報等も利用してよい。グループ化手段６は、グループ化した結果を記憶部４に格納すると共に、管理構造生成部３の構造化部７に出力する。
【００４２】
管理構造生成部３の構造化部７では、グループ化手段６によりグループ化された結果を用いて、隣接するグループや関連するグループをまとめた階層構造を作成し、各階層の外接矩形領域の座標値を算出する。
【００４３】
ここで、構造化部７の具体的な動作例を説明する。
図２の右側に示す解析対象の３次元データの地形領域は、例えば４つの図郭１１で区切られており、エリア１は図郭１１中の任意の領域とする。また、グループ化手段６によって、エリア１内の３次元ポリゴンデータが図２の左側に示すようにＡ〜Ｅの５個のグループに分割されているものとする。
【００４４】
構造化部７では、このようなエリア１に対して、あるグループ内に属する頂点の標高平均や標高の最小値及び最大値、グループの境界線の全周長、特徴稜線の並行性や交差性（ある特徴稜線から一定範囲内に存在する他の特徴稜線が存在するか否か、存在する場合それらが交差するか否か）、連続する特徴稜線の長さ等の、連続的なポリゴンの特性（大域的な特性）を算出してグループ同士の関係性を取得する。
【００４５】
このグループ同士の関係性に基づいて、例えば図３右側の地形断面（図３の左側に示すエリア１中のａ−ａ線での断面）に示すような付近に比べて最小の標高を有し、並行性を有する特徴稜線１２で囲まれた部分に相当する、グループＡに属する領域を、河川と推定する（図３の左側を参照）。また、グループＡ内の頂点の標高値から河川の上流下流を推定し、グループＡに隣接するグループの対称性から土量領域（グループＢ，Ｄ）や堤防領域（グループＣ，Ｅ）が隣接していると推定する（図３を参照）。
【００４６】
上記の推定結果から、構造化部７は、グループＡ〜Ｅは河川を含む河川流域の構造物であるとみなして構造化する。例えば、エリア１である矩形領域にＸ−Ｙ座標を当てはめ、エリア１内の領域をＸ軸方向及びＹ軸方向に走査し、グループ同士の隣接関係を左右上下方向に調べてグループＡ〜Ｅ及びその他の部分（図２に示すグループＦ，Ｇに属する領域）を構造化する。
【００４７】
図４は、図２に示す地形領域データについての構造化の一例を示す図である。図４において、「河川」や「土領域（右）」等の名称は、グループ内に属する頂点の標高平均等に基づいて各グループの地物を推定した際に付与した名称である。また、右や左は、河川の上流から下流への向きに関しての左右を示す。名称の右に記しているＡ〜Ｅはエリア１内のポリゴンをグループに分けた際に付与したラベルであり、図２に示したグループＡ〜Ｅと対応している。
【００４８】
構造化部７では、図２に示すエリア１内のグループを、河川（グループＡ）の右側は河川に近い順にグループＤ、グループＥ、グループＧの順でさらにグループ化し、河川（グループＡ）の左側は河川に近い順にグループＢ、グループＣ、グループＦの順でさらにグループ化する。このようにして、エリア１内のグループＢ〜Ｅは、グループＡに関連するグループとして構造化される。つまり、図４では、河川についてのグループＡを最上位とし、その直近下位の階層にグループＢ，Ｄ、これらの下位にグループＣ，Ｅ、最下位にグループＦ，Ｇが位置する。
【００４９】
また、グループＡには、下位階層であるグループＢ〜Ｇの外接矩形領域の最小座標（図２の地点アに相当）、最大座標（図２の地点イに相当）が与えられる。つまり、グループＢ〜Ｇに外接する矩形領域（エリア１の枠）における最大座標値と最小座標値とが、グループＡに関する情報として設定される。
【００５０】
上述では、エリア１内に存在するグループが全て関連するグループである場合を示したが、互いに関連しないグループが存在する場合は、これらを区別して構造化する。
図５は、例えばエリア１内にグループＡ〜Ｅの他に、河川とは関連性の低いグループＰ（道路）とグループＱ（歩道）が存在する場合のデータ構造化を示す図である。なお、関連性の高低は、画像や３次元データに関する特徴量を用いて決定する。
【００５１】
図５の例では、道路に関するグループＰが、河川のグループＡとは別個に最上位に設定され、その下位階層として歩道に関するグループＱが設定されている。グループＰに対しても、下位階層であるグループＱの外接矩形領域の座標（最大座標、最小座標）が設定される。また、「歩道（右）」という名称は、グループＱの地物を推定した際に付与した名称であり、右は、図４と同様に、河川の上流から下流への向きに関しての左右を示す。Ｑはエリア１内のポリゴンをグループに分けた際に付与したラベルである。
【００５２】
このようにして得られた構造化の結果は、対象とする地形領域を図郭等でブロック領域に分割した際のブロックの階層構造と関連付けて管理される。
図６は、図２の右側に示した解析対象の地形領域に対するデータ構造化の例を示す図である。図６（ａ）では、図２の右側に示した解析対象の地形領域を所定の解析区域に分割しており、図郭毎のブロック（ブロック１〜４）に分割し、ブロック２をさらに小さい領域（エリア１〜４）に分割している。なお、図６において、ブロックやエリアの大きさ、分割位置は任意である。
【００５３】
また、図６（ｂ）は、図６（ａ）の解析区域毎の構造化結果が階層的にまとめられたデータ構造化の例を示しており、解析対象の地形領域及び各ブロックに割り当てられた各階層のデータにはそれぞれの外接矩形領域の最小座標・最大座標が関連付けられて設定されている。ブロック２の構造化データを構成する各エリア１〜４の構造化データは、図４や図５に示したようなエリア内の地物のグループ化により構造化されたデータである。
【００５４】
なお、対象領域の外接矩形領域とは、図６（ａ）のブロック１〜４を囲む枠に相当する領域であり、ブロック１〜４の各外接矩形領域とは、ブロック１〜４をそれぞれ囲む枠に相当する領域である。
【００５５】
管理構造生成部３の構造化部７は、図６に示すようなデータ構造化の結果（対象とする地形領域を複数のブロックに分割した際の領域の階層構造、及び、ブロック内の任意のエリアに関して、グループ同士の関連性や隣接性等に基づき作成した階層構造、及び、各階層の外接矩形領域の座標）を作成して記憶部４に格納する。
【００５６】
次に、管理構造生成部３のインデックス生成部８は、グループ化手段６により生成されたグループ間や３次元ポリゴンデータにおいて、所望のポリゴンや頂点を高速に抽出するためのインデックスを生成する。このインデックス生成において、インデックス生成部８のグループインデックス生成手段９では、グループ化手段６により生成されたグループに関して、グループの境界となる部分のデータに基づくインデックスを生成する。
【００５７】
図７は、図２に示すグループ化の結果から特徴稜線による線グループを作成する処理を説明するための図である。先ず、グループインデックス生成手段９は、記憶部４から特徴稜線やグループに関する情報を取得し、各グループに関してグループ間の境界線となる特徴稜線を複数の線グループ（以下、構成線とも適宜称す）に分ける。具体的には、グループの境界線となる特徴稜線のうち、隣接する特徴稜線同士が成す角度を順に求めていきながら、角度が閾値以下となる構成線同士を同じ線グループとしてまとめる。角度が閾値以上である場合は、別の線グループとする。
【００５８】
例えば、図７（ａ）に示すグループＡの境界線となる特徴稜線の情報として、グループＡの囲み部分の特徴稜線１〜４及びこれらを接続する頂点ａ１〜ａ５を取得した場合を考える。この場合、グループインデックス生成手段９は、隣接する特徴稜線同士がその頂点に対しグループＡの内側になす角度を順に求め、その角度が閾値以上となる特徴稜線同士を同じ線グループとしてまとめる。また、角度が閾値未満である場合は、別の線グループとする。
【００５９】
図７（ａ）の例では、特徴稜線１と特徴稜線２が頂点ａ２に対しグループＡの内側になす角度（図中、矢印で示す）、特徴稜線２と特徴稜線３が頂点ａ３に対しグループＡの内側になす角度は、同一線グループとしての分類基準となる閾値以上であるため、同一線グループに分類される。一方、特徴稜線３と特徴稜線４が頂点ａ４に対しグループＡの内側になす角度は上記閾値未満であるため、特徴稜線３側とは別の線グループに分類される。この結果、グループＡの境界線を構成する各特徴稜線は、図７（ｂ）に示すように、線グループ番号１〜８が付された線グループにそれぞれ分けられる。
【００６０】
ここで、例えば図７（ｃ）に示す境界線Ｘは、グループＡとグループＢとに共通する境界線である。このような境界線の場合、グループＢにおいて、上述のように線グループを設定するにあたり、グループＡで既に付された線グループ番号と同一の番号を設定する。つまり、境界線Ｘに関しては、グループＡにおける線グループ化によって線グループ番号１〜３が付されているので、グループＢにおける線グループ化に際しては、線グループ番号１４〜１６等とせず、図７（ｄ）に示すように、線グループ番号１〜３をそのまま設定する。これにより、グループＢに関する線グループの作成結果は、図７（ｄ）のようになる。
【００６１】
次に、グループインデックス生成手段９は、特徴稜線を構成線に分けた結果を利用し、各グループに関して構成線に基づくインデックス（以下、グループインデックスと称す）、及び、グループの境界となるポリゴンや稜線に関するリストを作成する。
図８は、図２中のグループＡに関するインデックスの例を示す図である。図８の「共有グループ１」、「共有グループ２」は、構成線の両側に存在するグループ（構成線を介して隣接するグループ）を示している。図２の場合、構成線１（線グループ番号１の線グループ）の共有グループは、グループＡ及びグループＢである。なお、図８において、「構成線」とは、グループＡを構成する構成線である。また、線グループ番号は、グループである閉領域に対して右回り或いは左回りの順に記す。
【００６２】
「共有グループ１のポリゴンリスト参照先」は、構成線を稜線として有するポリゴンのうち、「共有グループ１」に属するポリゴンの、ポリゴンリスト内における参照位置である。同様に、「共有グループ２のポリゴンリスト参照先」は、構成線を稜線として有するポリゴンのうち、「共有グループ２」に属するポリゴンの、ポリゴンリスト内における参照位置である。
【００６３】
例えば、グループＡの構成線１の付近が、図９のようになっている場合、グループインデックスの「構成線１」に関して「共有グループ１のポリゴンリスト参照先」を参照すると、構成線１を稜線として持つポリゴンのうち、グループＡに属するポリゴンとして、ポリゴンリスト内のポリゴン１０１、ポリゴン８６、ポリゴン９７に関する位置を参照することができる。
【００６４】
なお、参照先である「ポリゴンリスト」には、グループの境界となる稜線を有するポリゴンが管理されており、頂点座標等を含むポリゴンに関する詳細情報の参照位置が設定される。この「ポリゴンリスト」から参照位置を参照することで、頂点座標等の詳細情報を取得できる。ポリゴンの詳細情報に関するインデックスについては、３次元データインデックス生成手段１０による処理の説明で後述する。
【００６５】
また、「稜線リスト参照先」は、構成線に属する稜線の、稜線リスト内における参照位置を示している。参照先である「稜線リスト」には、グループの境界となる稜線のリストが管理されており、稜線に関する詳細情報（稜線の両端の頂点座標等）の参照位置が設定されている。なお、稜線の詳細情報に関するインデックスについては、３次元データインデックス生成手段１０による処理の説明で後述する。
【００６６】
「構成線の端点１の座標」、「構成線の端点２の座標」は、構成線同士の接続部分に位置する頂点の座標を格納する。図９に示す構成線１の場合、端点はＰ（ポリゴン１０１上の頂点）とＱ（ポリゴン９７上の頂点）となる。
上述のようにして作成されたグループインデックス、ポリゴンリスト、稜線リストは、グループインデックス生成手段９によって記憶部４に格納される。
【００６７】
３次元データインデックス生成手段１０では、３次元ポリゴンデータに関して、ポリゴンや稜線、頂点等の図形要素に関するインデックスを生成する。
図１０（ａ）は、ポリゴンを管理するインデックスの一例を示す図である。図１０（ａ）において、「ポリゴン」は、グループインデックス生成手段９において生成された、図８に示すようなポリゴンリストから参照される。このインデックスにおける「稜線１」、「稜線２」、「稜線３」はポリゴンを構成する稜線を示しており、「稜線１」、「稜線２」、「稜線３」の各々から後述する頂点座標等の稜線に関する詳細情報を参照することができる。なお、図１０（ａ）の例では稜線の数は３個であり、三角ポリゴンの場合を示している。
【００６８】
「稜線１」、「稜線２」、「稜線３」に記す稜線の順序は、ポリゴンに対して右回り（あるいは左回り）で規則的とする。なお、「ポリゴン」がグループの構成線上のポリゴンである場合には、「稜線１」、「稜線２」、「稜線３」の順に構成線上の稜線を格納する。例えば、２つの構成線を有するポリゴンは、「稜線１」、「稜線２」が構成線上の稜線である。
「頂点Ｘ座標」、「頂点Ｙ座標」、「頂点Ｚ座標」は、ポリゴンを構成する頂点の座標である。「稜線１の隣接ポリゴン」は、「稜線１」で示されるポリゴンに隣接するポリゴンであり、このポリゴンの参照先が設定される。「稜線２の隣接ポリゴン」、「稜線３の隣接ポリゴン」についても同様に、「稜線２」、「稜線３」で示されるポリゴンに隣接するポリゴンの参照先がそれぞれ設定される。
【００６９】
次に、稜線に関するインデックスについて説明する。
図１０（ｂ）は、稜線を管理するインデックスの一例を示す図である。図１０（ｂ）において、「稜線」は、グループインデックス生成手段９において生成された稜線リストや、図１０（ａ）に示すポリゴンに関するインデックスの「稜線１」〜「稜線３」から参照される。「共有ポリゴン１」及び「共有ポリゴン２」は、稜線の両側にあるポリゴン（稜線を介して隣接するポリゴン）について、ポリゴンに関するインデックスへの参照位置を示している。「頂点１」及び「頂点２」は、稜線の両端の２頂点である。
上述のようして作成されたインデックスは、３次元データインデックス生成手段１０によって記憶部４に格納される。
【００７０】
なお、上述した例では、３次元ポリゴンデータを対象としたが、レーザ測量等で得られる点群データの場合は、ボロノイ分割やその他の手法等によりポリゴンデータを作成し、このデータを記憶部４に入力することで、同様にして、データ解析部２、管理構造生成部３による処理を行うことができる。
【００７１】
また、３次元データに関する特徴量として、「エッジの両側の面について、２面がなす角度」、「近似ガウス曲率」、「ポリゴン密度」の３種類を用いて特徴稜線を抽出する例を示したが、特徴稜線の抽出に利用する特徴量は、上記３種類に限定するものではない。３次元データに基づいて算出可能な他の特徴量を用いて特徴稜線を求めても良い。
【００７２】
さらに、インデックスを構成する項目についても、図８や図１０（ａ）、（ｂ）に示したものにのみに限定されるものではない。つまり、他の項目を追加してもよく、また図８等に示すインデックスにおいて、一つのインデックスにまとめられている複数の項目を分割して、複数のインデックスを作成してもよい。また、データ構造は、テーブルやリスト等、特に限定するものではない。
【００７３】
以上のように、この実施の形態１によれば、隣接ポリゴンの面積の特性や隣接ポリゴンの頂点存在範囲等、大域的な３次元データ特性を考慮した特徴量を抽出するので、ポリゴンを複数のグループに分類する際に、地物や領域の特性に応じて分類することができる。このため、河川管理や道路管理等の用途に即した解析を行うことができ、用途に応じた高速な検索を実現可能なインデックスを作成することができる。
【００７４】
また、上記実施の形態１では、ポリゴンを複数のグループに分類する際に３次元データから特徴稜線を抽出し、抽出した特徴稜線と他の特徴量を用いた解析によって分類するので、元のポリゴンを分割して管理するという不要な処理の発生を回避できる。このため、元々の３次元データのポリゴン数が膨大である場合であっても、ポリゴン数がさらに増大することがなく、効率的に管理できる。
【００７５】
実施の形態２．
この実施の形態２は、上記実施の形態１で示した３次元データの解析結果に基づいて作成されたインデックスを用い、近傍検索等の空間検索を高速に行う検索装置を説明する。
【００７６】
図１１は、この発明の実施の形態２による検索装置の構成を示すブロック図である。図１１に示すように、実施の形態２による検索装置１３は、上記実施の形態１で示した図１の構成に加え、検索部１４が新たに設けられている。データ解析部２は、上記実施の形態１と同様に、画像や３次元データから複数種類の特徴量を抽出し、抽出した特徴量を解析して処理対象データ中の３次元ポリゴンデータを関連のある複数のグループに分類する。また、データ解析部２は、図１と同様に、特徴量抽出手段５及びグループ化手段６を備える。
【００７７】
管理構造生成部３は、データ解析部２において抽出された特徴量やグループ化の結果を用いて解析対象の３次元ポリゴンデータを階層構造を有するデータに構造化し、データを高速に抽出するためのデータ構造（グループや３次元データに関するインデックス）を作成する。また、管理構造生成部３は、図１と同様に、構造化部７及びインデックス生成部８を備え、インデックス生成部８は、グループインデックス生成手段９及び３次元データインデックス生成手段１０を備える。
【００７８】
記憶部４は、地形や地物（道路や建物等）の３次元データや航空写真等の画像、画像や３次元データから抽出した解析結果に加え、検索部１４による検索結果のデータ（ポリゴン、頂点座標、頂点の接続順序）を記憶する。３次元データとしては、３次元座標を有する頂点及び頂点の接続順序を有したポリゴンデータである。ポリゴンデータは、以降の説明では三角形（ＴＩＮを含む）で表現されたものを使用する例を示すが、四角形、多角形の面で表現されたものであってもよい。
【００７９】
検索部１４は、管理構造生成部３により作成された、頂点や稜線等の３次元データに関するインデックスや複数のポリゴンデータをまとめたグループに関するインデックスを用いて、処理対象データで表現される空間の検索を行う。検索部１４の近傍検索手段１５は、入力された地点等の付近に存在するデータを検索する。検索部１４の閉領域検索手段１６は、指定された閉領域内に存在するデータや閉領域と交差するデータを検索する。
【００８０】
データ解析部２、管理構造生成部３、検索部１４の近傍検索手段１５及び閉領域検索手段１６は、例えば本発明の趣旨に従う検索処理プログラムを、検索装置１３を構成するコンピュータの演算処理装置に実行させてその動作を制御することにより、ソフトウエアとハードウエアとが協働した具体的な手段として実現することができる。
【００８１】
次に動作について説明する。
先ず、データ解析部２の特徴量抽出手段５が、記憶部４に格納されている画像や３次元データから特徴量を抽出する。このとき、特徴量抽出手段５では、画像や３次元形状に関する一般的な特徴量（色情報や曲率等）の他に、地形や地物の識別と領域分割が有効となるように、連続的なポリゴンの特性（大域的な特性）を考慮した特徴量を抽出する。具体的な動作は、上記実施の形態１と同様である。
【００８２】
データ解析部２のグループ化手段６では、特徴量抽出手段５により抽出された複数種類の特徴量を用いて、３次元ポリゴンデータを複数のグループに分割する。具体的な動作は、上記実施の形態１と同様である。
【００８３】
管理構造生成部３の構造化部７は、データ解析部２のグループ化手段６によりグループ化された結果を用いて、隣接するグループや関連するグループをまとめた階層構造を作成し、各階層の外接矩形領域の座標値を算出する。具体的な動作は、上記実施の形態１と同様である。
【００８４】
さらに、インデックス生成部８のグループインデックス生成手段９では、グループ化手段６で生成したグループに関して、グループの境界となる部分のデータに基づくインデックスを生成する。インデックス生成部８の３次元データインデックス生成手段１０は、３次元データに関してポリゴンや稜線等の図形要素に関するインデックスを生成する。
これら手段９，１０による具体的な動作は、上記実施の形態１と同様である。このようにして構造化されたインデックスが構築され、記憶部４に格納される。
【００８５】
検索部１４では、記憶部４に格納された上記インデックスを用いて空間検索を行う。
先ず、検索部１４の近傍検索手段１５は、記憶部４からインデックスを読み込み、解析対象である地形領域における、指定されたデータの付近に存在するデータを検索する。
例えば、検索装置１３に接続する不図示の入力装置を用いて、ユーザがある地点の座標を入力すると、入力した座標値で特定される地点に最も近いポリゴンの頂点や、入力した座標値で特定される地点から一定範囲内の領域に存在する頂点等を検索する。地形領域の３次元データを検索対象とする場合、実施の形態２による検索装置１３では、少なくとも下記のデータを検索することができる。
（１ｂ）指定地点が属するポリゴン
（２ｂ）指定地点を含むポリゴンに隣接するポリゴン
（３ｂ）指定地点に最も近い順にＮ個の頂点
（４ｂ）指定地点から一定範囲内（例えば、半径Ｒの円内）に存在するポリゴンや頂点
【００８６】
先ず、（１ｂ）指定した地点が属するポリゴン及び（２ｂ）指定地点を含むポリゴンに隣接するポリゴンを検索する処理を具体的に説明する。
図１２は指定地点の検索動作を説明するための図である。図１２の左側図に示すブロック１〜ブロック４は、上記実施の形態１の図６で示したような階層構造を有しており、またブロック２内のエリア２に関するデータは、上記実施の形態１の図５で示したようなデータ構造化がなされているものとする。
【００８７】
ここで、ユーザが、不図示の入力装置を用いて地点ウの座標値を指定すると、検索部１４の近傍検索手段１５が、直ちに図１２左側図に示す地形領域に関するインデックスを記憶部４から読み出し、このインデックスを用いて図１２左側図におけるブロック１〜４の外接矩形領域の座標（最小座標、最大座標）を抽出し、地点ウの座標値と比較する。
【００８８】
これにより、例えば地点ウの座標値に近い外接矩形領域の座標値を有するブロックとしてブロック２が抽出されると、近傍検索手段１５は、このブロック２に関するインデックス情報を用いて、ブロック２の下位階層を順に辿り地点ウが属するエリアとしてエリア２を特定する。続いて、近傍検索手段１５は、エリア２に関するインデックス情報を用いて、エリア２の下位階層を順に辿り、地点ウが属するグループがグループＡであると特定する。このようにして、指定された地点ウの属するグループが特定される。
【００８９】
（１ｂ）指定した地点が属するポリゴン及び（２ｂ）指定地点を含むポリゴンに隣接するポリゴンを検索する処理をさらに詳細に説明する。
図１３は、指定地点が属するポリゴンの検索処理を説明するための図であり、グループＦに属するポリゴンＵ内の点Ｐが指定された場合を示している。また、グループＦは、グループＧに構成線１を介して隣接しており、構成線１を共通な稜線としてポリゴンＶ，Ｗがあり、これらとポリゴンＵとが隣接している。
【００９０】
図１３において、点Ｐの座標（２次元でも３次元でもよい）が指定されると、近傍検索手段１５は、記憶部４に格納されているインデックスを参照し、上述したようにブロックやエリアの外接矩形領域の座標値と指定点Ｐの座標値とを比較して、指定点Ｐに近い上位階層のブロックを特定し、さらにブロックの下位階層であるエリアを順に辿って指定点Ｐが属するグループＦを特定する。
【００９１】
近傍検索手段１５は、記憶部４から読み出したインデックスにおける、グループＦに関するインデックス情報を用いて指定点Ｐに最も近い構成線を特定し、この構成線を共通の稜線として有するポリゴンを、図８に示したような「ポリゴンリスト参照先」を参照して特定し、指定点Ｐに最も近いポリゴンを検索する。
【００９２】
図１３の例では、指定点Ｐに最も近い構成線として構成線１が特定され、構成線１に属するポリゴン（構成線１を稜線として有するポリゴン）のうち、指定点Ｐに最も近いポリゴンを探索することにより、当該ポリゴンとしてポリゴンＷ（指定点Ｐを含むポリゴンに隣接するポリゴン）が特定される。
【００９３】
続いて、近傍検索手段１５は、指定点Ｐに最も近いポリゴンＷが特定されると、このポリゴン上（あるいはポリゴン内）に指定点Ｐが存在しなければ、ポリゴンに関するインデックスを参照して、構成線１に属しないポリゴン（構成線１を稜線として有さないポリゴン）うち、隣接するポリゴンを順に特定し、指定点Ｐが属するポリゴンを特定する。
図１３の例では、ポリゴンＷに隣接するポリゴンとしてポリゴンＵが特定され、ポリゴンＵ内に指定点Ｐが存在するので、近傍検索手段１５が検索処理を終了する。これにより、ポリゴンＵに関するデータが検索結果のポリゴンとして出力される。
【００９４】
一方、図１３に示す点Ｑが指定点として入力された場合、上記と同様に、指定点Ｑが属するグループとしてグループＦが特定され、グループＦに関して指定点Ｑに最も近い構成線として構成線１が特定される。同様に、構成線１に属するポリゴンを順に特定していくことで、指定点Ｑに最も近いポリゴンとしてポリゴンＶが特定される。このポリゴンＶは、指定点Ｑを含むため、ポリゴンＶに関するデータが検索結果として出力される。
【００９５】
また、（２ｂ）指定地点を含むポリゴンに隣接するポリゴンを検索する処理としては、図１３で点Ｐを指定した場合のように、ポリゴンに関するインデックスを参照して、指定点Ｐを含むポリゴンを特定するために、これに隣接するポリゴンを先に順に特定する場合がある。また、点Ｑを指定した場合のように、先に指定点Ｑを含むポリゴンＶを特定し、これに隣接するポリゴンについて、ポリゴンに関するインデックスを参照して順に特定する場合も考えられる。
【００９６】
次に、（３ｂ）指定地点に最も近い順にＮ個の頂点を検索する処理を説明する。
指定点から近い順にＮ個の頂点を検索する処理では、上記検索動作によって指定点が属するポリゴンを特定した後、隣接するポリゴンを順に特定する動作を複数回繰り返して指定点を含むポリゴンの周辺のポリゴンを複数個特定し、各ポリゴンの頂点と指定点との距離が小さい順にＮ個の頂点を特定する。
【００９７】
図１４は、指定地点に最も近い順にＮ個の頂点を検索する処理を説明するための図であり、グループＦに属するポリゴンＵ内の点Ｐが指定された場合を示している。また、グループＦは、グループＧに構成線１を介して隣接しており、構成線１を共通な稜線としてポリゴンＶ，Ｗがあり、ポリゴンＶ、ポリゴンＷ及びポリゴンＸとポリゴンＵとが隣接している。また、ポリゴンＶ、ポリゴンＷは、構成線１を介してグループＧに属するポリゴンＹ及びポリゴンＺとそれぞれ隣接している。
【００９８】
図１４に示す点Ｐのようにグループの境界付近の地点が指定された場合、近傍検索手段１５は、指定点が含まれるグループ（図１４の例ではグループＦ）に属するポリゴンの他に、境界線（構成線１）を介して隣接するグループ（図１４の例ではグループＧ）に属するポリゴンも特定する。
【００９９】
図１４の例において、近傍検索手段１５は、指定点Ｐが存在するポリゴンとしてポリゴンＵが特定された後、ポリゴンＵに隣接するポリゴンとして、先ず同一グループであるグループＦに属するポリゴンＶ，Ｗ，Ｘを特定する。続いて、ポリゴンＷは、構成線１上に稜線を有しているため、この稜線を介して隣接するポリゴンを、ポリゴンに関するインデックスを参照してグループＧ内のポリゴンＹを特定する。構成線１上に稜線を有するポリゴンＶについても同様にして、グループＧに属する隣接するポリゴンＺを特定する。
【０１００】
この後、近傍検索手段１５は、ポリゴンＶ〜Ｚの各頂点と指定点Ｐとの距離が小さい順にＮ個の頂点を特定する。指定点Ｐを含むポリゴンＵの周辺のポリゴンＶ〜ＺからＮ個の頂点が得られると、検索を終了する。なお、頂点数がＮ個に満たない場合は、現在までに特定されているポリゴンにさらに隣接するポリゴンを特定し、頂点数が所定のＮ個になるまで上記処理を繰り返す。
【０１０１】
次に、（４ｂ）指定地点から一定範囲内に存在するポリゴンや頂点の検索処理について説明する。
指定地点から一定範囲内（例えば、半径Ｒの円内）に存在するポリゴンや頂点を検索する処理では、指定点を含むポリゴンを特定した後、そのポリゴンに隣接するポリゴンをポリゴンに関するインデックスを参照しながら順に特定していき、特定されたポリゴンの頂点と指定点との距離が半径Ｒを超えた場合に、そのポリゴンに隣接するポリゴンを検索する処理を終了する。
【０１０２】
例えば、上述した（１ｂ）〜（３ｂ）の検索処理を実行し、これまでに特定されている全てのポリゴンに関して、各々に隣接するポリゴンの頂点が、指定点から半径Ｒの円で規定される範囲外に存在する場合、当該検索処理を終了し、指定点から半径Ｒの円内のポリゴンと頂点とを検索結果として出力する。
【０１０３】
なお、上述した検索処理によって指定点から一定範囲内に存在するポリゴンを検索し、事後的にそのポリゴンの頂点と指定点との距離を半径Ｒと比較することで、指定点から一定範囲内に存在する頂点を検索するようにしてもよい。
【０１０４】
以上の動作により検索結果のデータ（例えば、特定したポリゴンの３次元データ、頂点座標、頂点の接続順序）が得られると、近傍検索手段１５は、当該検索結果を記憶部４に格納する。
【０１０５】
検索部１４の閉領域検索手段１６では、検索対象の３次元データ（地形領域）において指定された閉領域内に存在するデータや閉領域と交差するデータを検索する。
以降では、閉領域内にグループの構成線が存在する場合と、閉領域内にグループの構成線が存在しない場合（閉領域全体がグループ内に含まれる場合）とについて説明する。
【０１０６】
図１５は、閉領域内にグループの構成線が存在する場合の検索処理の流れを示すフローチャートである。図１６は、閉領域内にグループの構成線が存在する場合の検索処理を説明するための図であり、グループＦとグループＧの境界線である構成線１が閉領域内に存在する場合を示している。この図１６を適宜用いつつ、図１５に沿って動作を説明する。
【０１０７】
先ず、ユーザが、不図示の入力装置を用いて、図１６に示すような閉領域を構成する頂点座標値を入力すると、閉領域検索手段１６は、上記実施の形態１で示したグループインデックスを記憶部４から読み出し、このグループインデックスを参照して閉領域を構成する各頂点がどのグループに存在するかを調べる（ステップＳＴ１）。図１６の例では、閉領域を構成する頂点ａ〜ｄは、グループＦあるいはグループＧに属するとの結果が得られる。
【０１０８】
次に、閉領域検索手段１６は、閉領域を構成する頂点ａ〜ｄに関して、隣接する頂点が別のグループになる箇所を調べ、閉領域とグループとが交差する構成線を特定し、その構成線に属するポリゴンの中で閉領域と交差するポリゴン情報を取得する（ステップＳＴ２）。図１６の場合、頂点ａと頂点ｂの間、及び、頂点ｃと頂点ｄの間で、頂点が属するグループが異なるため、線分ａｂ及び線分ｃｄとが点ｐ、ｑでそれぞれ交差する構成線として構成線１が特定される。
【０１０９】
さらに、閉領域検索手段１６は、グループインデックスやポリゴンリスト、ポリゴンや稜線に関するインデックスを参照して、構成線１に属するポリゴンの中で閉領域に属するポリゴンとして、ポリゴンＦ１、ポリゴンＦ２、ポリゴンＦ３、ポリゴンＧ１、ポリゴンＧ２、ポリゴンＧ３を特定し、これらのポリゴン情報（頂点座標等のポリゴンデータ）を取得する。
【０１１０】
ステップＳＴ３において、閉領域検索手段１６は、ステップＳＴ２で特定されたポリゴンに関して、構成線ではない稜線と、この稜線を介して隣接するポリゴンとを特定する。例えば、ポリゴンＦ１の場合、ポリゴンＦ１の稜線の中で構成線上ではない稜線として稜線Ｌ１（図１６中、太線で示す）に関する情報を取得する。また、稜線Ｌ１に隣接するポリゴンとしてポリゴンＦ４のポリゴン情報を取得する。ポリゴンＦ２、ポリゴンＦ３、ポリゴンＧ１、ポリゴンＧ２、ポリゴンＧ３に関しても同様に処理する。ここまでの処理でポリゴンＦ１〜ポリゴンＦ６、ポリゴンＧ１〜ポリゴンＧ５についてのポリゴン情報が取得される。
【０１１１】
閉領域検索手段１６は、各ポリゴンＦ１〜Ｆ６，Ｇ１〜Ｇ５に対し、１つのポリゴン内の全頂点が閉領域外であるか否かを判定する（ステップＳＴ４）。このとき、全頂点が閉領域外である場合、ステップＳＴ５Ａの処理に進み、少なくとも１つの頂点が閉領域内にあるポリゴンであるならば、ステップＳＴ５Ｂの処理に進む。
【０１１２】
図１６の例では、ポリゴンＦ４は閉領域内にも頂点が存在するため、ステップＳＴ５Ｂの処理に移る。ステップＳＴ５Ｂでは、閉領域内に頂点が存在するポリゴンに対して隣接するポリゴンが特定される。ポリゴンＦ４の場合であれば、これに隣接するポリゴンとしてポリゴンＦ７が特定され、そのポリゴン情報が取得される。
【０１１３】
ポリゴンＦ７と同様にして、閉領域検索手段１６は、閉領域内の構成線１に属するポリゴンＦ１〜Ｆ３，Ｆ５，Ｆ６，Ｇ１〜Ｇ５について順に隣接するポリゴンを辿りながら閉領域と交差するポリゴンを特定し、ポリゴン情報を取得する。特定された全ポリゴンに対して、各々の隣接ポリゴンが全て取得済みとなった段階で当該処理を終了する。
【０１１４】
一方、ポリゴンＦ６の場合、全ての頂点が閉領域外であるため、ステップＳＴ５Ａの処理に移る。ステップＳＴ５Ａでは、全ての頂点が閉領域外であるポリゴンを検索結果としないものとされる。ポリゴンＦ６の場合、全ての頂点が閉領域外であるため、これに隣接するポリゴンの検索は行わず、ポリゴンＦ６は検索結果から外される。
【０１１５】
次に、閉領域内にグループの構成線が存在しない場合について説明する。
図１７は、閉領域内にグループの構成線が存在しない場合の検索処理の流れを示すフローチャートである。図１８は、閉領域内にグループの構成線が存在しない場合の検索処理を説明するための図であり、閉領域がグループＧと構成線１を介して隣接するグループＦ内に存在し、構成線１と交差しない場合を示している。この図１８を適宜用いつつ、図１７に沿って動作を説明する。
【０１１６】
先ず、ユーザが、不図示の入力装置を用いて、図１８に示すような閉領域を構成する頂点座標値を入力すると、閉領域検索手段１６は、上記実施の形態１で示したグループインデックスを記憶部４から読み出し、このグループインデックスを参照して閉領域を構成する各頂点がどのグループに存在するかを調べる（ステップＳＴ１）。図１８の例では、閉領域を構成する頂点ａ〜ｄの全てが、グループＦに属するとの結果が得られる。
【０１１７】
閉領域検索手段１６は、閉領域を構成する各頂点ａ〜ｄに対して、最も近いグループの構成線を特定する（ステップＳＴ２ａ）。図１８の例では、頂点ａ，ｂについては構成線４、頂点ｃについては構成線１、頂点ｄについては構成線３の情報が取得される。
【０１１８】
ステップＳＴ３ａにおいて、閉領域検索手段１６は、ステップＳＴ２ａで特定された構成線１，３，４に属するポリゴンのうち、閉領域を構成する頂点に最も近いポリゴンを特定し、ポリゴン情報を取得する。図１８の例では、頂点ａ〜ｄに関して、各々ポリゴンＦ１、ポリゴンＦ２、ポリゴンＦ３、ポリゴンＦ４の情報が取得される。
【０１１９】
続いて、閉領域検索手段１６は、ポリゴンに関するインデックスを参照してポリゴンＦ１〜Ｆ４に隣接するポリゴンを特定し、ポリゴン情報を取得する（ステップＳＴ４ａ）。図１８の例では、ポリゴンＦ１〜Ｆ４に隣接する、ポリゴンＦ５〜ポリゴンＦ１０が特定される。なお、閉領域を構成する頂点ａ〜ｄは、全て同一のグループＦ内に存在するため、隣接ポリゴンの検索で構成線１上の稜線を介して隣接するポリゴンは検索しない。例えば、ポリゴンＦ３の稜線Ｌ１ａ（図１８中、太線で示す）は構成線１上にあるため、稜線Ｌ１ａに隣接するポリゴンとしてグループＧに属するポリゴンＧ１のポリゴン情報は取得しない。
【０１２０】
この後、閉領域検索手段１６は、ステップＳＴ４ａで特定された各ポリゴンに対し、１つポリゴン内の全頂点が閉領域外であるか否かを判定する（ステップＳＴ５ａ）。このとき、全頂点が閉領域外である場合、ステップＳＴ６Ａの処理に進み、少なくとも１つの頂点が閉領域内にあるポリゴンであるならば、ステップＳＴ６Ｂの処理に進む。
【０１２１】
図１８の例では、閉領域検索手段１６が、ポリゴンＦ１〜Ｆ３，Ｆ５〜Ｆ９について順次隣接するポリゴンを辿りながら閉領域と交差するポリゴンを特定し、ポリゴン情報を取得していく。特定された全ポリゴンに対して、各々の隣接ポリゴンが全て取得済みとなった段階で当該処理を終了する。
【０１２２】
一方、ポリゴンＦ４及びポリゴンＦ１０の場合、全ての頂点が閉領域外であるため、ステップＳＴ６Ａの処理に移る。ステップＳＴ６Ａでは、全ての頂点が閉領域外であるポリゴンを検索結果としないものとされる。ポリゴンＦ４及びポリゴンＦ１０の場合、全ての頂点が閉領域外であるため、これに隣接するポリゴンの検索は行わず、ポリゴンＦ４及びポリゴンＦ１０は検索結果から外される。
【０１２３】
このようにして、本実施の形態２による検索装置１３は、ユーザに指定された閉領域内部に含まれるポリゴン及び閉領域に交差するポリゴンを特定しポリゴン情報を取得する。また、検索結果としてポリゴンの頂点や稜線に関するデータが記憶部４に格納されていれば、これらを読み出して閉領域との交差判定を行うことで、上述した閉領域に含まれる頂点や稜線、閉領域と交差する稜線を特定するデータを事後的に取得することができる。
【０１２４】
なお、上述の説明では、指定地点から一定範囲内に存在するポリゴンや頂点を検索するにあたり、近傍検索手段１５が、指定点から半径Ｒの円内で規定される領域内の検索例を示したが、検索範囲に用いる図形は円に限定しない。円の半径を与える代わりに、矩形の最小座標、最大座標を与えてもよい。
【０１２５】
以上のように、この実施の形態２によれば、３次元データの特徴量に基づいて構造化した結果を用いて、検索範囲として指定された頂点（閉領域を構成する頂点や近傍検索を行いたい１頂点）が属するグループを特定する。そして、検索範囲の頂点に近い、グループの構成線上に存在するポリゴンを手がかりとして検索を開始するので、検索範囲の付近のデータから順に判定を行うことができ、検索を効率的に行うことができる。
【０１２６】
例えば、広範囲の中から検索範囲が存在する領域を限定した後、グループ内では、検索範囲に近い部分から判定を行うことにより、検索範囲から離れたデータに対しては判定を行う可能性が低くなる。このため、検索結果となるポリゴンを効率的に検索することができる。従って、広範囲でポリゴン数が膨大な３次元データを対象とした場合であっても、高速に検索を行うことができる。
【０１２７】
また、複数のポリゴンをまとめたグループは、広範囲の中から検索範囲を限定する際や、検索開始時のポリゴンを取得する際に大きく関わるが、このグループの作成は、河川管理や道路管理等の利用用途を考慮した解析によって行うことができる。このため、利用用途を想定した解析とインデックスの構築によって、利用用途に応じた検索を高速に行うことができる。
【０１２８】
例えば、河川の氾濫において時間の経過とともに浸水領域が広がる場合に、構造化の結果を利用して河川から近い順に隣接するグループを特定し、各グループからは、河川に近い順に、河川から離れる方向に向かって隣接ポリゴンを順に特定していくことで、河川の付近のポリゴンを効率的に検索することができる。
【０１２９】
なお、上記実施の形態２では、検索装置１３として、データ解析部２と管理構造生成部３とを備える構成を示したが、上記実施の形態１で示した解析装置１による解析結果に基づいて作成されたインデックスをＣＤ−ＲＯＭ等の記憶媒体から読み込み、記憶部に格納するように構成してもよい。
【０１３０】
この場合、例えば図１９に示す検索装置１３Ａのように、上記実施の形態１で示した解析装置１と同様に機能するデータ解析部２と管理構造生成部３を省略してもよい。この検索装置１３Ａにおける記憶部４ａは、解析結果に基づいて作成されたインデックスをＣＤ−ＲＯＭ等の記憶媒体から読み込んで記憶しており、検索部１４は、この記憶部４ａに格納されたインデックスを参照して、上記実施の形態２と同様に検索を行う。
【０１３１】
実施の形態３．
この実施の形態３は、上記実施の形態１で示した３次元データの解析結果に基づいて作成されたインデックスを用いて近傍検索等の空間検索を行い、この検索結果を用いて解析対象の地形領域等の断面形状の取得や面積、体積算出等の３次元計測を行う計測装置について説明する。
【０１３２】
図２０は、この発明の実施の形態３による計測装置の構成を示すブロック図である。図２０に示すように、実施の形態３による計測装置１７は、上記実施の形態２で示した図１１の構成に加え、計測部１８が新たに設けられている。
【０１３３】
データ解析部２は、上記実施の形態１と同様に画像や３次元データから複数種類の特徴量を抽出し、抽出した特徴量を解析して処理対象データ中の３次元ポリゴンデータを関連のある複数のグループに分類する。また、データ解析部２は、図１と同様に、特徴量抽出手段５及びグループ化手段６を備える。
【０１３４】
管理構造生成部３は、データ解析部２において抽出された特徴量やグループ化の結果を用いて地物を階層構造を有するデータに構造化し、データを高速に抽出するためのデータ構造（グループや３次元データに関するインデックス）を作成する。また、管理構造生成部３は、図１と同様に、構造化部７及びインデックス生成部８を備え、インデックス生成部８は、グループインデックス生成手段９及び３次元データインデックス生成手段１０を備える。
【０１３５】
記憶部４は、地形や地物（道路や建物等）の３次元データや航空写真等の画像、画像や３次元データから抽出した解析結果に加え、検索部１４による検索結果のデータ（ポリゴン、頂点座標、頂点の接続順序）を記憶する。３次元データとしては、３次元座標を有する頂点及び頂点の接続順序を有したポリゴンデータである。ポリゴンデータは、以降の説明では三角形（ＴＩＮを含む）で表現されたものを使用する例を示すが、四角形、多角形の面で表現されたものであってもよい。
【０１３６】
検索部１４は、管理構造生成部３により作成された、頂点や稜線等の３次元データに関するインデックスや複数のポリゴンデータをまとめたグループに関するインデックスを用いて、処理対象データにおける空間検索を行う。また、検索部１４は、図１１と同様に、近傍検索手段１５及び閉領域検索手段１６を備える。
【０１３７】
計測部１８は、検索部１４により検索されたデータを用いて地形領域等の３次元データにより表現された物体や地物の面積や体積等の３次元計測を行う。計測部１８の交差データ取得手段１９は、断面をとるために指定された２地点で特定される線分を含む平面と交差するポリゴンや、当該平面とポリゴンとの交点のデータを取得する。計測部１８の３次元計測手段２０は、距離や面積、体積等の３次元計測を行う。
【０１３８】
データ解析部２、管理構造生成部３、検索部１４、計測部１８における交差データ取得手段１９及び３次元計測手段２０は、例えば本発明の趣旨に従う計測処理プログラムを、計測装置１７を構成するコンピュータの演算処理装置に実行させてその動作を制御することにより、ソフトウエアとハードウエアとが協働した具体的な手段として実現することができる。
【０１３９】
次に動作について説明する。
先ず、データ解析部２の特徴量抽出手段５が、記憶部４に格納されている画像や３次元データから特徴量を抽出する。このとき、特徴量抽出手段５では、画像や３次元形状に関する一般的な特徴量（色情報や曲率等）の他に、地形や地物の識別と領域分割が有効となるように、連続的なポリゴンの特性（大域的な特性）を考慮した特徴量を抽出する。具体的な動作は、上記実施の形態１と同様である。
【０１４０】
データ解析部２のグループ化手段６では、特徴量抽出手段５により抽出された複数種類の特徴量を用いて、３次元のポリゴンデータを複数のグループに分割する。具体的な動作は、上記実施の形態１と同様である。
【０１４１】
管理構造生成部３の構造化部７は、データ解析部２のグループ化手段６によりグループ化された結果を用いて、隣接するグループや関連するグループをまとめた階層構造を作成し、各階層の外接矩形領域の座標値を算出する。具体的な動作は、上記実施の形態１と同様である。
【０１４２】
さらに、インデックス生成部８のグループインデックス生成手段９では、グループ化手段６で生成したグループに関して、グループの境界となる部分のデータに基づくインデックスを生成する。インデックス生成部８の３次元データインデックス生成手段１０は、３次元データに関して、ポリゴンや稜線等の図形要素に関するインデックスを生成する。
これら手段９，１０による具体的な動作は、上記実施の形態１と同様である。このようにして構造化されたインデックスが構築され、記憶部４に格納される。
【０１４３】
検索部１４では、記憶部４から３次元ポリゴンデータに関するインデックスや複数のポリゴンデータをまとめたグループに関するインデックスを読み出し、これらインデックスを用いて空間検索を行う。なお、近傍検索手段１５及び閉領域検索手段１６の具体的な動作は、上記実施の形態２と同様である。本実施の形態３では、検索部１４が、計測部１７により断面形状や面積、体積の算出を行う処理対象データ（ポリゴン等）を検索する。
【０１４４】
計測部１７では、検索部１４により検索されたデータを用いて地形領域等の３次元データにより表現された物体や地物の面積や体積等の３次元計測を行う。以降では、計測部１７が、検索結果のポリゴンで表現される地形領域の断面形状を取得する処理を説明する。
【０１４５】
図２１は、地形領域の断面形状を計測する処理を説明するための図であり、ユーザ指定の２点を結ぶ直線での断面形状を求める例を示している。また、図２２は、断面形状を計測する処理の流れを示すフローチャートである。図２１を適宜用いつつ、図２２に沿って動作を説明する。
【０１４６】
検索部１４の近傍検索手段１５は、ユーザが不図示の入力装置を用いて断面を求める線分の両端となる２地点の座標を入力すると、入力された２地点のうち１点を始点として、上記実施の形態２で示した近傍検索を実行し、始点が存在するポリゴン（始点が属するポリゴン）が特定され、そのポリゴン情報が取得される。
【０１４７】
例えば、図２１において、ユーザから２地点Ｐ１，Ｐ２の座標値が入力され、点Ｐ１を始点とした場合を説明する。この場合、近傍検索手段１５によって、点Ｐ１に関する近傍検索が行われると、点Ｐ１が属するポリゴンとしてポリゴンＤが特定される。特定されたポリゴンＤを規定するポリゴン情報は、近傍検索手段１５により、検索結果として記憶部４に格納されると共に、計測部１７の交差データ取得手段１９に出力される。
【０１４８】
交差データ取得手段１９は、２地点Ｐ１，Ｐ２の座標値を入力すると、検索部１４の近傍検索手段１５から又は記憶部４に記憶された、始点（ここでは、点Ｐ１）が存在するポリゴンＤのポリゴン情報を取得し、２地点Ｐ１，Ｐ２を結んだ線分を含む平面と交差するポリゴン、及び上記線分とポリゴンの稜線との交点を求める処理を実行する。
【０１４９】
図２２は、交差データ取得手段による動作の流れを示すフローチャートであり、この図に沿って交差データの取得処理を説明する。
先ず、交差データ取得手段１９は、記憶部４からポリゴンに関するインデックスを読み出し、このポリゴンに関するインデックスを参照して、ポリゴンＤに関し、地点Ｐ１と地点Ｐ２を結ぶ線分を含む、図２１の紙面に垂直な平面（以下、横断面と称す）と稜線との交差判定を行って、横断面と交差する稜線を特定しその交点を求める（ステップＳＴ１ｂ）。図２１に示す例では、ポリゴンＤにおいて、点Ｐ１，Ｐ２を結ぶ線分を含む横断面と交差する稜線として稜線４５が特定され、横断面と稜線４５との交点として点Ｃ１が得られる。
【０１５０】
次に、交差データ取得手段１９は、ポリゴンに関するインデックスを参照して、ステップＳＴ１ｂで取得した稜線を介して隣接するポリゴンのポリゴン情報を取得し、この隣接するポリゴンに関して、現在の稜線以外の稜線と横断面との交差判定を行い、交差する稜線及び交点を求める（ステップＳＴ２ｂ）。図２１の場合、稜線４５を介してポリゴンＤと隣接するポリゴンとしてポリゴンＥが特定され、ポリゴンＥに関するデータが取得される。そして、ポリゴンＥの稜線のうち、稜線４５以外に横断面と交差する稜線として稜線４９が特定され、交点として点Ｃ２が算出される。
【０１５１】
以降は、終点Ｐ２が属するポリゴンＭに達するまで、ステップＳＴ２ｂの処理を繰り返す（ステップＳＴ３ｂ）。この過程で、ポリゴンＨ、ポリゴンＧ、ポリゴンＩ、ポリゴンＫが特定され、横断面と稜線４８，７８，１０８，１０１２との交点として交点Ｃ３〜Ｃ６が取得される。交差データ取得手段１９では、交点Ｃ６を取得した後、稜線１０１２を介してポリゴンＫに隣接するポリゴンとしてポリゴンＭを特定し、このポリゴンＭに関するポリゴン情報を取得する。交差データ取得手段１９は、終点Ｐ２が存在するポリゴンＭのポリゴン情報を取得すると、処理を終了する。
【０１５２】
上述した処理により取得された、横断面が交差するポリゴン（以下、交差ポリゴンと適宜称す）や稜線、交点に関するデータは、交差データ取得手段１９が、記憶部４に格納すると共に、計測部１８の３次元計測手段２０に出力する。
【０１５３】
なお、２地点を結ぶ線分を含む平面で断面をとる場合を示したが、３地点以上を指定して複数の線分をそれぞれ含む平面で断面をとる場合も同様である。図２３に示すように、点Ｐ１〜Ｐ３の３点が指定された場合、例えば点Ｐ１を始点として、上述と同様に点Ｐ１と点Ｐ２を結ぶ線分を含んだ横断面と交差するポリゴン、このポリゴンの稜線と横断面との交点を求め、次に点Ｐ２を始点として、上述と同様に点Ｐ２と点Ｐ３を結ぶ線分を含んだ横断面と交差するポリゴン、このポリゴンの稜線と横断面との交点を求める。
【０１５４】
３次元計測手段２０では、ユーザにより不図示の入力装置を介して入力された断面積の算出に用いる基準標高を取得すると、この基準標高、指定地点Ｐ１，Ｐ２、交差データ取得手段１９により取得された交点の座標値から断面の３次元形状を生成し、その断面積を算出する。図２４は、図２１で示す横断面での断面形状を示す図である。上述した基準標高とは、図２４（ａ）に示すように、断面積を算出する際に基準とする、最下部の標高である。
【０１５５】
また、断面積は、図２４（ｂ）に示すＡの部分とＢの部分のどちらも算出することができる。例えば、Ａの部分の断面積を求める場合、交差データ取得手段１９により取得された交点の３次元座標を用いて、図２４（ａ）に示す断面形状を構成する線分をそれぞれ求め、これら線分と基準標高位置までの距離（高さ）を算出し、断面形状を構成する線分の範囲で積算することにより、Ａの部分の断面積を求めることができる。
【０１５６】
また、Ｂの部分の断面積を求める場合は、例えば基準標高から断面形状を構成する線分までの距離が最大となる最大標高（図２４（ｂ）中に矢印で示す）を求め、この最大標高位置と断面形状を構成する線分までの距離を逐次算出し、断面形状を構成する線分の範囲で積算することにより、Ｂの部分の断面積を求めることができる。
【０１５７】
次に、複数の地点間の距離を求める動作について説明する。
交差データ取得手段１９は、ユーザが不図示の入力装置を用いて距離を求めたい複数の地点を入力すると、上記と同様の動作により、入力された複数の地点により規定される線分を含む横断面とポリゴンとの交点の３次元座標を取得する。３次元計測手段２０は、交差データ取得手段１９によって取得された交点の座標を受け取り、各交点間の距離を、入力された地点間の距離として算出する。
【０１５８】
なお、距離を求めたい地点として３点以上の地点が入力された場合、入力された地点のうちの１つを始点として線分を求め、この線分を含む横断面とポリゴンとの交点の３次元座標を取得し、各交点間の距離を算出する。そして、上述と同様に、順次前回始点とした入力点に隣接する入力点を始点として線分を求め、この線分を含む横断面とポリゴンとの交点の３次元座標を取得して各交点間の距離を終点の入力点まで算出することで処理できる。
【０１５９】
次に、指定された閉領域内の面積や体積を算出する動作について説明する。
面積は、閉領域を２次元平面上に投影した場合（各ポリゴンの頂点Ｚ座標を考慮しない場合）の他に、各ポリゴンの頂点Ｚ座標を考慮する場合の２種類の方法で求めることができる。
【０１６０】
２次元平面上に投影した閉領域（各ポリゴンの頂点Ｚ座標を考慮しない場合）の面積の算出処理を説明する。
不図示の入力装置を用いて、ユーザが閉領域を構成する頂点の座標を入力すると、計測部１８の３次元計測手段２０に当該座標が入力される。
３次元計測手段２０は、ユーザにより入力された閉領域を構成する頂点の座標列を用いて、下記式（２）を用いて２次元平面上に投影した閉領域の面積を求める。但し、閉領域を構成するｎ個の点Ｐ１，Ｐ２，・・・，Ｐｎの座標を（ｘ1，ｙ1），（ｘ2，ｙ2），・・・，（ｘn，ｙn）とし、閉領域であるので点Ｐ１と点Ｐｎは同一の点である。また、Ｐ１，Ｐ２，・・・，Ｐｎは時計回りに並んでいるものとする。なお、頂点が左回りに並んでいるとした場合は、絶対値｜Ｓ｜が面積となる。
【数１】
2007293597.tif 000003
【０１６１】
次に、各ポリゴンの頂点Ｚ座標を考慮した面積の算出処理を説明する。
検索部１４の閉領域検索手段１６は、ユーザが不図示の入力装置を用いて閉領域を構成する頂点の座標を入力すると、この閉領域内部に含まれるポリゴン、及び、閉領域に交差するポリゴンのポリゴン情報を取得する。具体的な動作は、上記実施の形態２と同様である。取得されたポリゴン情報は、検索結果として記憶部４に格納されると共に、計測部１８の３次元計測手段２０にも入力される。
【０１６２】
３次元計測手段２０では、閉領域内部に含まれるポリゴンのポリゴン情報を取得すると、各々のポリゴンの面積を算出する。また、閉領域を構成する線分と交差するポリゴンに関して、閉領域を構成する線分とポリゴンとの交点を算出し、ポリゴンを構成する頂点の中で閉領域内に存在する頂点を取得して閉領域内にある側の面積を算出する。このようにして各ポリゴンの面積を求めると、３次元計測手段２０は、上述のようにして求めた各ポリゴンの面積の総和を、ポリゴンの頂点Ｚ座標を考慮した場合の面積として算出する。
【０１６３】
次に、閉領域内の体積を算出処理を説明する。
検索部１４の閉領域検索手段１６は、ユーザが不図示の入力装置を用いて閉領域を構成する頂点の座標を入力すると、上記実施の形態２と同様にして、閉領域内部に含まれるポリゴン、及び、閉領域に交差するポリゴンのポリゴン情報を取得する。３次元計測手段２０は、閉領域検索手段１６により取得されたポリゴン情報を用いて、閉領域内のポリゴン及び閉領域に交差するポリゴンの体積をそれぞれ求め、各ポリゴンの体積の総和を閉領域内の体積として算出する。なお、面積を算出した場合と同様に、閉領域に交差するポリゴンに関しては閉領域内にある部分の体積を求める。
【０１６４】
以上のように、この実施の形態３によれば、入力された指定点により規定される線分に関して切った断面を含む平面とポリゴン（３次元ポリゴンデータ）との交点に基づいて断面形状を求めるので、高精細の３次元ポリゴンデータを利用する際、精度を劣化させずに断面形状を得ることができる。また、上記実施の形態１で示した解析結果に基づいて構築されたインデックスを利用するので、３次元データのポリゴン数が膨大である場合であっても高速に交点が取得され、高精度の断面形状を高速に計測することができる。
【０１６５】
また、上記実施の形態３によれば、指定された閉領域内に存在するポリゴンに基づいて面積や体積を算出するので、高精細の３次元ポリゴンデータを利用する際、精度を劣化させずに面積や体積を算出することができる。また、上記実施の形態１で示した解析結果に基づいて構築したインデックスを利用するので、３次元データのポリゴン数が膨大である場合であっても閉領域内に存在するポリゴンや閉領域に交差するポリゴンを高速に検索することができ、面積や体積を高精度、かつ高速に求めることができる。
【０１６６】
上記実施の形態３では、計測装置１７として、データ解析部２及び管理構造生成部３を備える構成を示したが、上記実施の形態１で示した解析装置１による解析結果に基づいて作成されたインデックスをＣＤ−ＲＯＭ等の記憶媒体から読み込み、記憶部に格納するように構成してもよい。
【０１６７】
この場合、例えば図２５に示す計測装置１７Ａのように、上記実施の形態１で示した解析装置１と同様に機能するデータ解析部２と管理構造生成部３を省略してもよい。この計測装置１７Ａにおける記憶部４ｂには、上記解析結果に基づいて作成されたインデックスがＣＤ−ＲＯＭ等の記憶媒体から読み込まれて記憶されており、検索部１４は、この記憶部４ｂに格納されたインデックスを参照して、上記実施の形態２と同様に検索を行い、計測部１８は、上記実施の形態３と同様に断面形状や体積の算出等を行うことができる。
【０１６８】
なお、上記実施の形態１〜３では、処理対象の形状として河川等の地形や道路等の地物を有する地形領域を例に挙げたが、インデックス生成の対象とする３次元データは、地形領域に関するデータに限定されるものではない。つまり、本発明は、３次元データ（ポリゴンデータ）等で表現できる形状を有するものであれば適用可能である。
同様に、指定点の近傍検索や、閉領域内に存在するデータや閉領域と交差するデータを検索する対象も、地形領域に関するデータに限定されるものではなく、検索結果のデータを用いて３次元計測する対象も地形領域に関するデータに限定されるものではない。
【図面の簡単な説明】
【０１６９】
【図１】この発明の実施の形態１による解析装置の構成を示すブロック図である。
【図２】解析対象の地形領域及びそのグループ化結果を示す図である。
【図３】図２中の地形領域において特定領域を決定する処理を説明するための図である。
【図４】処理対象データの構造化の一例を示す図である。
【図５】互いに関連しないグループが存在する場合における構造化の一例を示す図である。
【図６】図２の右側に示した解析対象の地形領域に対するデータ構造化の例を示す図である。
【図７】線グループを作成する処理を説明するための図である。
【図８】図２中のグループＡに関するインデックスの例を示す図である。
【図９】構成線及びこれに接するポリゴンを示す図である。
【図１０】インデックスの一例を示す図である。
【図１１】この発明の実施の形態２による検索装置の構成を示すブロック図である。
【図１２】指定地点の検索動作を説明するための図である。
【図１３】指定地点が属するポリゴンの検索処理を説明するための図である。
【図１４】指定地点に最も近い順にＮ個の頂点を検索する処理を説明するための図である。
【図１５】閉領域内にグループの構成線が存在する場合の検索処理の流れを示すフローチャートである。
【図１６】閉領域内にグループの構成線が存在する場合の検索処理を説明するための図である。
【図１７】閉領域内にグループの構成線が存在しない場合の検索処理の流れを示すフローチャートである。
【図１８】閉領域内にグループの構成線が存在しない場合の検索処理を説明するための図である。
【図１９】実施の形態２による検索装置の他の構成例を示すブロック図である。
【図２０】この発明の実施の形態３による計測装置の構成を示すブロック図である。
【図２１】地形領域の断面形状を計測する処理を説明するための図である。
【図２２】交差データ取得手段による動作の流れを示すフローチャートである。
【図２３】３地点で特定される線分で断面をとる場合を説明するための図である。
【図２４】図２１で示す横断面での断面形状を示す図である。
【図２５】実施の形態３による計測装置の他の構成例を示すブロック図である。
【符号の説明】
【０１７０】
１  解析装置、２  データ解析部、３  管理構造生成部、４，４ａ，４ｂ  記憶部、５  特徴量抽出手段、６  グループ化手段、７  構造化部、８  インデックス生成部、９  グループインデックス生成手段、１０  ３次元データインデックス生成手段、１１  図郭、１２  特徴稜線、１３，１３Ａ  検索装置、１４  検索部、１５  近傍検索手段、１６  閉領域検索手段、１７，１７Ａ  計測装置、１８  計測部、１９  交差データ取得手段、２０  ３次元計測手段。
【図１】
2007293597.tif 000004
【図２】
2007293597.tif 000005
【図３】
2007293597.tif 000006
【図４】
2007293597.tif 000007
【図５】
2007293597.tif 000008
【図６】
2007293597.tif 000009
【図７】
2007293597.tif 000010
【図８】
2007293597.tif 000011
【図９】
2007293597.tif 000012
【図１０】
2007293597.tif 000013
【図１１】
2007293597.tif 000014
【図１２】
2007293597.tif 000015
【図１３】
2007293597.tif 000016
【図１４】
2007293597.tif 000017
【図１５】
2007293597.tif 000018
【図１６】
2007293597.tif 000019
【図１７】
2007293597.tif 000020
【図１８】
2007293597.tif 000021
【図１９】
2007293597.tif 000022
【図２０】
2007293597.tif 000023
【図２１】
2007293597.tif 000024
【図２２】
2007293597.tif 000025
【図２３】
2007293597.tif 000026
【図２４】
2007293597.tif 000027
【図２５】
2007293597.tif 000028