"対象空間における地物表面の三次元形状を表す点群データに基づいて前記地物の壁面を検出するデータ解析装置であって、前記対象空間を垂直面で分割して、柱状の複数の部分空間を設定する部分空間設定手段と、前記部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する部分空間選択手段と、前記注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定するブロック空間設定手段と、水平面内における前記壁面の位置を探索する水平面内探索手段と、を有し、前記水平面内探索手段は、前記ブロック空間ごとに、前記水平面内の線分のうち、前記水平面に射影された前記点群が予め設定した基準以上に近傍に集まるものを探索して水平面内壁面位置と定めること、を特徴とするデータ解析装置。請求項1に記載のデータ解析装置において、前記対象空間にて前記水平面内壁面位置に存在する前記壁面の垂直方向の位置を求める垂直位置決定手段を有し、当該垂直位置決定手段は、前記水平面内壁面位置ごとに、前記点群のうち前記水平面への射影位置が当該水平面内壁面位置から予め設定した距離内にあるものを注目点群として抽出し、垂直方向に関して当該注目点群が予め設定した閾値以上存在する各範囲を当該水平面内壁面位置での垂直方向壁面位置と定めること、を特徴とするデータ解析装置。請求項2に記載のデータ解析装置において、前記水平面内壁面位置での各垂直方向壁面位置に存在する前記壁面の形状を、当該垂直方向壁面位置での前記注目点群の分布範囲に基づいて求める壁面形状決定手段を有し、前記壁面形状決定手段は、前記水平面内壁面位置における鉛直面上の台形であって、その平行な2辺を鉛直方向に設定され、前記分布範囲を前記鉛直面に射影した形状を近似するものを前記壁面の形状とすること、を特徴とするデータ解析装置。請求項2又は請求項3に記載のデータ解析装置において、既に検出されている前記水平面内壁面位置における前記垂直方向壁面位置ごとに、当該水平面内壁面位置の端部に連なる新たな前記水平面内壁面位置を求める追跡手段を有し、前記追跡手段は、既検出の前記水平面内壁面位置の端部に短辺の中点を接続された長方形を平面形状とする直方体の空間であってその高さが前記垂直方向壁面位置に対応して配置される隣接空間を、前記長方形の長辺に沿った中心線を前記水平面内壁面位置の延長線に一致させて設定し、当該隣接空間内に前記点群が予め設定した基準以上に集まる場合には当該隣接空間内の点群の前記水平面内での分布に沿った線分を新たな前記水平面内壁面位置とし、一方、前記中心線を前記延長線に一致させて設定した前記隣接空間にて新たな前記水平面内壁面位置が検出されなかった場合は、前記水平面内での前記中心線の向きを変えて内部に最も点群が集まる前記隣接空間を探索し、得られた当該隣接空間内の点群の前記水平面内での分布に沿った線分を新たな前記水平面内壁面位置とすること、を特徴とするデータ解析装置。対象空間における地物表面の三次元形状を表す点群データに基づいて前記地物の壁面を検出するデータ解析方法であって、前記対象空間を垂直面で分割して、柱状の複数の部分空間を設定する部分空間設定ステップと、前記部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する部分空間選択ステップと、前記注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定するブロック空間設定ステップと、水平面内における前記壁面の位置を探索する水平面内探索ステップと、を有し、前記水平面内探索ステップは、前記ブロック空間ごとに、前記水平面内の線分のうち、前記水平面に射影された前記点群が予め設定した基準以上に近傍に集まるものを探索して水平面内壁面位置と定めること、を特徴とするデータ解析方法。コンピュータに、対象空間における地物表面の三次元形状を表す点群データに基づいて前記地物の壁面を検出するデータ解析を行わせるためのプログラムであって、当該コンピュータを、前記対象空間を垂直面で分割して、柱状の複数の部分空間を設定する部分空間設定手段、前記部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する部分空間選択手段、前記注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定するブロック空間設定手段、及び水平面内における前記壁面の位置を探索する水平面内探索手段、として機能させ、前記水平面内探索手段は、前記ブロック空間ごとに、前記水平面内の線分のうち、前記水平面に射影された前記点群が予め設定した基準以上に近傍に集まるものを探索して水平面内壁面位置と定めること、を特徴とするプログラム。従来、点群データをもとに地物を判読するためには人手を要しており、三次元CADで編集ツール等を利用して手作業で地物の抽出作業が行われていた。本発明は、地物表面の三次元形状を表す点群データに基づいて地物の壁面を自動的に検出するデータ解析装置、データ解析方法、及びプログラムを提供することを目的とする。本発明に係るデータ解析装置は、対象空間における地物表面の三次元形状を表す点群データに基づいて前記地物の壁面を検出するものであって、前記対象空間を垂直面で分割して、柱状の複数の部分空間を設定する部分空間設定手段と、前記部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する部分空間選択手段と、前記注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定するブロック空間設定手段と、水平面内における前記壁面の位置を探索する水平面内探索手段と、を有し、前記水平面内探索手段は、前記ブロック空間ごとに、前記水平面内の線分のうち、前記水平面に射影された前記点群が予め設定した基準以上に近傍に集まるものを探索して水平面内壁面位置と定める。他の本発明に係るデータ解析装置は、前記対象空間にて前記水平面内壁面位置に存在する前記壁面の垂直方向の位置を求める垂直位置決定手段を有し、当該垂直位置決定手段は、前記水平面内壁面位置ごとに、前記点群のうち前記水平面への射影位置が当該水平面内壁面位置から予め設定した距離内にあるものを注目点群として抽出し、垂直方向に関して当該注目点群が予め設定した閾値以上存在する各範囲を当該水平面内壁面位置での垂直方向壁面位置と定める。また他の本発明に係るデータ解析装置は、さらに、前記水平面内壁面位置での各垂直方向壁面位置に存在する前記壁面の形状を、当該垂直方向壁面位置での前記注目点群の分布範囲に基づいて求める壁面形状決定手段を有し、前記壁面形状決定手段は、前記水平面内壁面位置における鉛直面上の台形であって、その平行な2辺を鉛直方向に設定され、前記分布範囲を前記鉛直面に射影した形状を近似するものを前記壁面の形状とする。別の本発明に係るデータ解析装置は、既に検出されている前記水平面内壁面位置における前記垂直方向壁面位置ごとに、当該水平面内壁面位置の端部に連なる新たな前記水平面内壁面位置を求める追跡手段を有し、前記追跡手段は、既検出の前記水平面内壁面位置の端部に短辺の中点を接続された長方形を平面形状とする直方体の空間であってその高さが前記垂直方向壁面位置に対応して配置される隣接空間を、前記長方形の長辺に沿った中心線を前記水平面内壁面位置の延長線に一致させて設定し、当該隣接空間内に前記点群が予め設定した基準以上に集まる場合には当該隣接空間内の点群の前記水平面内での分布に沿った線分を新たな前記水平面内壁面位置とし、一方、前記中心線を前記延長線に一致させて設定した前記隣接空間にて新たな前記水平面内壁面位置が検出されなかった場合は、前記水平面内での前記中心線の向きを変えて内部に最も点群が集まる前記隣接空間を探索し、得られた当該隣接空間内の点群の前記水平面内での分布に沿った線分を新たな前記水平面内壁面位置とする。本発明に係るデータ解析方法は、対象空間における地物表面の三次元形状を表す点群データに基づいて前記地物の壁面を検出する方法であって、前記対象空間を垂直面で分割して、柱状の複数の部分空間を設定する部分空間設定ステップと、前記部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する部分空間選択ステップと、前記注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定するブロック空間設定ステップと、水平面内における前記壁面の位置を探索する水平面内探索ステップと、を有し、前記水平面内探索ステップは、前記ブロック空間ごとに、前記水平面内の線分のうち、前記水平面に射影された前記点群が予め設定した基準以上に近傍に集まるものを探索して水平面内壁面位置と定める。本発明に係るプログラムは、コンピュータに、対象空間における地物表面の三次元形状を表す点群データに基づいて前記地物の壁面を検出するデータ解析を行わせるためのプログラムであって、当該コンピュータを、前記対象空間を垂直面で分割して、柱状の複数の部分空間を設定する部分空間設定手段、前記部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する部分空間選択手段、前記注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定するブロック空間設定手段、及び水平面内における前記壁面の位置を探索する水平面内探索手段、として機能させ、前記水平面内探索手段は、前記ブロック空間ごとに、前記水平面内の線分のうち、前記水平面に射影された前記点群が予め設定した基準以上に近傍に集まるものを探索して水平面内壁面位置と定める。本発明によれば、地物表面の三次元形状を表す点群データに基づいて地物の壁面を自動的に検出することができる。以下、本発明の実施の形態以下実施形態というである壁面抽出システム2について、図面に基づいて説明する。本システムは、地物表面の三次元形状を表す点群データに基づいて地物の壁面、すなわち地物表面のうち地表面に略垂直である面を検出するデータ解析装置である。点群データは例えば、上述のモービルマッピングシステムのように地上を走行する車両に搭載されたレーザスキャナにより取得される。また、レーザスキャナを地上に設置して計測を行っても良い。点群データが地物表面の三次元形状を表すには、地物表面の凹凸のスケールに応じた点密度でレーザスキャンが行われる必要がある。この点、車両や三脚を用いて道路等の地上から行うレーザスキャンは、例えば、道路の近傍に建つ建物、塀、看板及び標識などの壁面の形状を捉えることができる程度の走査密度を実現できる。図1は、壁面抽出システム2の概略の構成を示すブロック図である。本システムは、演算処理装置4、記憶装置6、入力装置8及び出力装置10を含んで構成される。演算処理装置4として、本システムの各種演算処理を行う専用のハードウェアを作ることも可能であるが、本実施形態では演算処理装置4は、コンピュータ及び、当該コンピュータ上で実行されるプログラムを用いて構築される。当該コンピュータのCPUCentralProcessingUnitが演算処理装置4を構成し、後述する部分空間設定手段20、部分空間選択手段22、ブロック空間設定手段24、水平面内探索手段26、垂直位置決定手段28、壁面形状決定手段30、追跡手段32、及び壁面要素登録手段34として機能する。記憶装置6はコンピュータに内蔵されるハードディスクなどで構成される。記憶装置6は演算処理装置4を部分空間設定手段20、部分空間選択手段22、ブロック空間設定手段24、水平面内探索手段26、垂直位置決定手段28、壁面形状決定手段30、追跡手段32及び壁面要素登録手段34として機能させるためのプログラム及びその他のプログラムや、本システムの処理に必要な各種データを記憶する。例えば、記憶装置6は、処理対象データとして解析の対象空間の点群データを格納される。例えば、道路に沿った地域が解析の対象空間とされる。入力装置8は、キーボード、マウスなどであり、ユーザが本システムへの操作を行うために用いる。出力装置10は、ディスプレイ、プリンタなどであり、本システムにより求められた壁面の対象空間内での位置を画面表示、印刷等によりユーザに示す等に用いられる。図2は、壁面抽出システム2による壁面抽出処理の概略のフロー図である。この図2を参照しながら、演算処理装置4の各手段を説明する。部分空間設定手段20は、対象空間を垂直面で分割して得られる柱状の複数の部分空間を壁面抽出の処理の初期の単位空間として設定するS40。本実施形態では、部分空間設定手段20は、対象空間を水平面XYZ直交座標系でX-Y平面とする内にて二次元直交格子メッシュ状に分割して四角柱形状の部分空間を生成する。例えば、部分空間の水平断面は幅W及び奥行きDが50cmの正方形とすることができる。部分空間の高さHは対象空間の高さZ軸方向の寸法と一致させることができ、その高さは検出目的とする壁面の高さ、具体的には建物の高さや、看板標識が配置された高さより大きく設定される。なお、部分空間設定手段20を構成するプログラムでは、幅W、奥行きD及び高さHはパラメータ化されており、例えば、ユーザが入力装置8を用いて変更することができる。部分空間選択手段22は部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する。具体的には、部分空間選択手段22は、複数設定された部分空間を所定の順序で選択し、当該部分空間内の点群に閾値以上の高低差が存在する場合に、当該部分空間を注目部分空間とする。上述したように点群データは道路等に位置するレーザスキャナからのレーザ照射によって取得され、当該レーザスキャナから見える壁面が点群データによる三次元形状上に捉えられる。そこで、部分空間選択手段22は例えば、当該三次元形状にて道路等に対応する平面の部分に基づいて基準平面を決定し、また、道路に沿って道幅内に水平に当該三次元形状の中心線を設定するS42。そして、当該中心線に沿って順番に部分空間の選択の起点を設定し、中心線に直交する線に沿って両側方向に当該起点から近い順に部分空間を選択してS44、選択した部分空間内の点群の高低差が閾値以上であれば当該部分空間を注目部分空間と判定するS46。ブロック空間設定手段24は、注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定するS48。例えば、ブロック空間の高さHBは部分空間の幅W、奥行きDと同程度に設定することができる。水平面内探索手段26は、ブロック空間ごとに、水平面内にて当該水平面に射影された点群が予め設定した基準以上に近傍に集まる線分を探索して、当該線分を水平面内における壁面の位置水平面内壁面位置と定めるS50。ブロック空間ごとに水平面内壁面位置を探索することで、垂直方向に細長い注目部分空間にて異なる高さに存在し得る、位置向きが相違した複数の壁面を弁別できる。垂直位置決定手段28は、対象空間にて水平面内壁面位置に存在する壁面の垂直方向の位置を求めるS52。具体的には、垂直位置決定手段28は、注目部分空間にて検出される水平面内壁面位置ごとに、当該注目部分空間の点群のうち水平面への射影位置が当該水平面内壁面位置から予め設定した距離内にあるものを注目点群として抽出する。そして、水平面内壁面位置ごとに抽出された注目点群について、垂直方向の位置に関して当該注目点群が予め設定した閾値以上存在する各範囲を当該水平面内壁面位置での垂直方向壁面位置と定める。これにより、或るブロック空間で検出された水平面内壁面位置に基づいて、当該ブロック空間以外の高さ範囲にて当該水平面内壁面位置に存在する壁面も検出される。例えば、連続する複数のブロック空間に跨がる壁面について一つの垂直方向壁面位置が定められる。また、高さ方向に分離した複数の壁面が同じ水平面内壁面位置に存在する、つまり壁面が垂直方向に階層をなす場合には、それら階層をなす壁面それぞれについて垂直方向壁面位置が求められる。水平面内壁面位置と当該水平面内壁面位置に対する垂直方向壁面位置との組は、注目部分空間内の一枚の壁面の配置を表す。当該壁面は当該注目部分空間の外側、つまり横方向に広がるより大きな壁面の一部であり得ることから、ここでは壁面要素と称する。壁面形状決定手段30は、水平面内壁面位置において各垂直方向壁面位置に存在する壁面要素の形状を、当該垂直方向壁面位置での注目点群の分布範囲に基づいて求めるS54。具体的には、壁面形状決定手段30は、水平面内壁面位置を通る鉛直面にて注目点群を射影し、射影された点群の分布範囲に基づいて壁面要素の形状を求める。当該形状は、平行な2辺である上底及び下底を鉛直方向に設定され、かつ鉛直面に射影された点群の分布範囲を近似する台形とされる。追跡手段32は、既に検出されている水平面内壁面位置における垂直方向壁面位置ごとに、当該水平面内壁面位置の端部に連なる新たな水平面内壁面位置を求めるS56。追跡手段32は壁面要素の横方向に隣接する直方体の空間を設定し、当該隣接空間内の点群を水平面に射影し、射影された点群が予め設定した基準以上に近傍に集まる線分を探索して新たな水平面内壁面位置と定める。当該処理を順次繰り返すことで、注目部分空間にて特定された壁面要素から横方向に連続する壁面の水平面内壁面位置がトレースされる。具体的には、隣接空間は、平面形状が既検出の水平面内壁面位置の端部に短辺の中点を接続された長方形である直方体に設定される。ここでは、当該長方形の長辺に沿った中心線を水平面内での隣接空間の向きとする。また、当該隣接空間の高さ、つまり直方体の上面と底面とで定義される垂直方向の範囲は、垂直方向壁面位置に対応した位置に配置される。追跡手段32はまず、既検出の水平面内壁面位置を真っ直ぐに延長した向きに隣接空間を設定する。つまり、隣接空間はその平面形状の長方形の上記中心線が既検出の水平面内壁面位置の延長線に一致するように配置される。そして、当該隣接空間内に点群が予め設定した基準以上に集まる場合には当該隣接空間内の点群の水平面内での分布に沿った線分を新たな水平面内壁面位置とする。一方、既検出の水平面内壁面位置の延長線に向きを一致させて設定した隣接空間にて新たな水平面内壁面位置が検出されなかった場合は、追跡手段32は隣接空間の向きを変化させて水平面内壁面位置を探す。つまり、向きを変化させた隣接空間のうち内部に最も点群が集まるものを探索し、得られた当該隣接空間内の点群の水平面内での分布に沿った線分を新たな水平面内壁面位置とする。上述のようにして対象空間にて検出された壁面要素に関する情報は壁面要素登録手段34により記憶装置6に登録される。登録された壁面要素の形状の情報や接続関係の情報は例えば、建物の壁面形状の認識や建物の三次元モデルの構築に用いられる。以下、壁面抽出システム2の処理例をより詳しく説明する。図3、図4、図6、図9~図16は、演算処理装置4が実行する一連の処理の流れを分割して示す処理フロー図である。図3に示す処理は上述した部分空間設定手段20及び部分空間選択手段22による処理に当たる。壁面抽出システム2が壁面抽出処理を開始するとS60、部分空間設定手段20は、対象空間内に部分空間を順次作成する。例えば、対象空間をX軸方向及びY軸方向に沿ってメッシュ状に分割する場合、部分空間の幅W及び奥行きDがパラメータとして設定されると、それらが当該メッシュの間隔部分空間のサイズとなり、対象空間のサイズに応じてX,Y各方向の部分空間の配列個数が定まる。当該配列個数により、X,Y各方向の部分空間の位置を示すインデックスの範囲が決定される。部分空間設定手段20は、部分空間の二次元メッシュ状の配置を表すインデックスを所定の順番で変更し、設定されたインデックスに応じた位置X,Y各方向の座標範囲で定義される部分空間を設定するS62。ここで、道路を走行する車両上からレーザ照射を行い点群データを取得した場合、上述したように、点群データが表す三次元形状にて道路等に対応する平面の部分に基づいて基準平面が設定され、道路に沿って当該三次元形状の中心線が設定される。説明を簡単にするために、当該中心線をX軸つまりY=0とし、車両が走行する方向にX方向のインデックスが増加し、道幅方向に対応するY方向に関しては、中心線から離れるに従ってインデックスの絶対値が増加するものとする。例えば、Y方向のインデックスは中心線の位置では0とし、走行方向に対して左向きに、1,2,3,...と設定し、右向きには-1,-2,-3,...と設定することができる。この場合、部分空間設定手段20は例えば、X方向のインデックスを順番にインクリメントし、X方向のインデックスの各値にて、Y軸の正方向と負方向との両方向にY方向のインデックスを変化させる。すなわち、部分空間設定手段20はX方向の或るインデックスの値にて、Y方向のインデックスを0から順番に増加させて部分空間を設定し、また-1から順番に減少させて部分空間を設定する。インデックス指定されたメッシュの部分空間が未処理のものであればS64にてNoの場合、部分空間選択手段22は当該部分空間内の点群を例えば、ハードディスク等の記憶装置6からRAMRandomAccessMemory等の作業領域に取り込むS66。部分空間に取り込んだ点群内に所定閾値Th1以上の高低差がある場合S68にてYesの場合には、部分空間選択手段22は当該部分空間を注目部分空間と判断して、当該注目部分空間での水平面内壁面位置や垂直方向壁面位置の探索等の処理が開始される図4のノードBへ処理が進む。例えば、閾値Th1は道路等の地表の略平坦な部分のみを含む部分空間を排除できる程度に小さく設定することができる。また、閾値Th1を、壁面を検出しようとする地物の高さに応じて設定して、関心のない低い地物の壁面は検出しないようにすることもできる。例えば、道路から見て建物の手前に存在するガードレールや郵便ポストなどの比較的低い地物を検出対象外とするように閾値Th1を建物の1階の高さ程度に設定することができる。設定した部分空間から取り込んだ点群の高低差が閾値Th1未満である場合S68にてNoの場合には、当該部分空間における壁面抽出処理は行わない。この場合は、部分空間設定手段20が次の部分空間を設定するノードAへ処理が戻る。全てのメッシュについて処理が終わっている場合はS64にてYesの場合、演算処理装置4は壁面抽出の処理を終えるS70。図4は演算処理装置4が実行する一連の処理のうち上述したブロック空間設定手段24及び水平面内探索手段26が行う部分の概略の処理フロー図である。ブロック空間設定手段24は、注目部分空間を一定の高さHBごとに分割して、縦に積み重なる複数のブロック空間を設定し、各ブロック空間内に位置する点群のデータを記憶装置6からRAM等の作業領域に取り込むS80。例えば、部分空間の幅W、奥行きDを50cmとする場合にはブロック空間の高さHBは20~50cmとすることができる。当該分割により設定されるブロック空間の段数をn段とし、インデックスIを用いて下から順に第I階I=1,2,...,nと表す。水平面内探索手段26はn段のブロック空間を順番に選択して、当該ブロック空間にエッジ水平面内壁面位置が存在するかを調べる。例えば、水平面内探索手段26はインデックスIを1ずつ増加させて、エッジの存在を調べるブロック空間を選択するS82,S84。水平面内探索手段26は、選択した第I階のブロック空間にエッジが存在するかを調べS86、存在しない場合にはS88にてNoの場合次のブロック空間を選択するS84。なお、Iがnを越えた場合には、図3のノードAに戻り、次の注目部分空間を探すS90。図5はブロック空間でのエッジの探索処理S86を説明する模式図である。図5は、ブロック空間を上面から見た図であり、ブロック空間の幅W及び奥行きDで定義される矩形100と、ブロック空間内の点群のX-Y面内での配置の一例が示されている。水平面内探索手段26は、ブロック空間内の点群から任意の2つのデータ点PA,PBを選択し、それら2点を両端とするX-Y面内での線分L0をエッジの候補線として設定すると共に、線分L0を中心としてその両側にそれぞれ幅w合計幅2wの帯状領域EAを設定する。水平面内探索手段26は点群のうちX-Y平面での座標が当該領域EA内に位置するデータ点の個数をカウントする。データ点が領域EA内であるか否かは例えば、X-Y平面上での当該データ点から線分L0への垂線の長さがw以下であるか否かによって判定可能である。また、エッジの条件として、領域EA内の点群が表す三次元形状が平坦でないことを課す。具体的には、水平面内探索手段26は、領域EA内に包含されるデータ点の高低差最大標高と最小標高との差ΔZが予め設定した段差閾値γ以上であれば平坦ではないと判定する。ここで、幅wはパラメータであり、壁面に対応するデータ点のエッジに直交する方向の位置のばらつきを吸収する。例えば、wは3cm程度とすることができる。また、高低差の閾値γは例えば2cm程度に設定できる。水平面内探索手段26は、ブロック空間内の2つのデータ点の全ての組み合わせについて候補線を設定して上述の判定を行い、領域EA内に最もデータ点が多く集まり、かつΔZが閾値γ以上である線分L0をブロック空間にて見つけられたエッジとする。エッジが存在した場合にはS88にてYesの場合、当該エッジが壁面要素を決定するための処理を行われていない新規なものであるか判定されるS92。当該判定は、壁面要素を決定するための処理の対象とされたエッジを登録したリストを検索して、処理S86で見つけられたエッジと同一のものが存在するか否かに基づいて行われる。リストに同一のものが存在しなければ新規なエッジと判定しS92にてNoの場合、リストにエッジの両端PA,PBの座標ax,ay,bx,byを登録するS94。このように或るブロック空間にて新たなエッジが検出されると、当該エッジについて当該注目部分空間での垂直方向壁面位置の探索、及び壁面要素の形状の決定が行われる図6のノードDへ処理が進む。一方、処理S86にて見つけられたエッジと同一のエッジが他のブロック空間についての処理で既にリストに登録されると共に、垂直方向壁面位置の探索等の処理が行われている場合もあり、その場合はS92にてYesの場合、当該エッジについてのリストへの登録や垂直方向壁面位置の探索等の処理は省略され、水平面内探索手段26は次のブロック空間について処理を行うノードCへ処理が戻る。図6は垂直位置決定手段28及び壁面形状決定手段30の概略の処理フロー図である。垂直位置決定手段28は、処理S86にて抽出されたエッジL0での垂直方向における壁面の位置を探索するための空間として垂直探索空間を設定し、当該垂直探索空間内に位置する点群のデータを記憶装置6からRAM等の作業領域に取り込むS110。垂直探索空間は、平面形状がエッジL0を長手方向の中心軸とする矩形である直方体形状の空間であり、その底面及び上面は部分空間の底面及び上面と同じ高さに位置する。平面形状の矩形の短辺の寸法ξは例えば、エッジを抽出した帯状領域EAの幅2wと同じ、またはやや大きめに設定することができる。例えば、ξは10cmに設定することができる。垂直位置決定手段28は垂直探索空間内の点群をZ方向の分布に基づいてグループ化するS112。これにより或る水平面内壁面位置における垂直方向の壁面の階層構造が捉えられる。グループ化において垂直位置決定手段28は例えば、垂直探索空間に取り込んだ点群の最小標高から上へ、又は最大標高から下へ向けて一定の刻み幅hでZ方向に複数の区間を設定する。そして、当該区間に基づいて垂直探索空間内の点群を複数の階層ランクに区分し、ランクごとに点群の数点数を集計する。ここで刻み幅hに応じて、垂直方向に隣接した2つの壁面を分離して検出できる分解能が定まり、基本的にはhはHB以下に設定される。ここでhが小さいほど分解能が高くなるが、hが小さすぎると、壁面が存在する高さ範囲の区間での点数が小さくなり、壁面が存在しない高さ範囲での点数基本的には0であることが期待されるとの弁別が難しくなる。hはこれらを勘案して設定される。垂直位置決定手段28はランクごとに点群の数を集計した点群分布に基づいて、垂直探索空間における点群をグループ化する。具体的には、点群が集まっているランク範囲をそれぞれ点群の1つのグループとし、当該ランク範囲を1つの垂直方向壁面位置とする。図7はグループ化を説明するための説明図であり、hを0.2mとしてランクごとに点群の数を集計した結果である点群分布表の一例を示している。垂直位置決定手段28は例えば、ランクを下最小標高から上へ順番に調べて、0より大きい点数を有するランクが連続する範囲ごとに順番にグループ番号を付与する。図7に示す例では点数が0より大きいランク範囲は、ランク1~4、ランク9~12、ランク18~22、及びランク25~26の4つであり、これらランク範囲に順番にグループ番号1~4が付与される。なお、点数が0より大きいランクが単独で現れる場合、つまり当該ランクの前後では点数が0である場合には、垂直位置決定手段28は当該1つのランクを1つのランク範囲としてグループ番号を付与する。グループ化により定まる階層数をmと表す。図7に示す例ではmは4である。壁面形状決定手段30はm階層に設定されたランク範囲垂直方向壁面位置を順番に選択する。例えば、壁面形状決定手段30はグループ番号Jを1ずつ増加させて、壁面要素の形状を決定するランク範囲を選択するS114,S116。そして、垂直探索空間に存在する点群のうち選択したランク範囲に存在するもののデータを記憶装置6からRAM等の作業領域に取り込みS120、当該点群データから壁面要素となる台形を決定する処理を行うS122。壁面要素の形状を決定できた場合にはS124にてYesの場合、当該壁面要素の横方向につながる壁面要素の水平面内壁面位置を順次求める追跡処理が開始される図9のノードFへ処理が進む。なお、m階層全てについて壁面要素の決定処理が終わるとS118にてYesの場合、図4のノードCへ戻り、次のエッジが探索され当該エッジについて同様の処理が繰り返される。また、或る階層にて壁面要素の形状を決定できなかった場合はS124にてNoの場合、処理S116に戻り、次の階層についての処理が行われる。図8は壁面要素の形状を求める処理S122を説明する模式図であり、垂直探索空間に存在する点群のうち1つの階層に対応するものをエッジを通る鉛直面に射影した様子の一例を示している。図8において矩形で示す鉛直面130に分布する黒点132が点群を射影した点である。矩形の鉛直面130は横方向がエッジに沿っており、左側がエッジの一方端PAの側、右側が他方端PBの側に対応している。また、鉛直面130の縦方向が鉛直方向であり、上端、下端はそれぞれランク範囲の上端、下端に対応している。壁面形状決定手段30は鉛直面130を格子状に区切り、縦横に行列配置された複数の小矩形134を定義する。例えば、小矩形134の幅は10cm程度、高さは5cm程度とすることができる。壁面形状決定手段30は、縦に並ぶ小矩形134の列を例えば左側から順に選択し、点群が射影される小矩形134が2つ以上存在する列を探す。そのような列が現れる範囲、つまり最初の位置第ηS列から最後の位置第ηE列までの列範囲が得られた場合には、さらに壁面要素の形状を特定する処理が行われる。一方、そのような列範囲が存在しない場合には当該階層には壁面要素は存在しないと判断される。壁面形状決定手段30は鉛直面130に射影された点群黒点132のうち左端部分に位置するものに基づいて台形の平行な2辺のうちの一方ここではこれを台形の上底とするとする鉛直線のX,Y座標を定め、左端部分に分布する点群の標高に基づいて当該辺上底の両端のZ座標を定める。また、右端部分に位置するものに基づいて台形の平行な2辺のうちの他方ここではこれを台形の下底とするとする鉛直線のX,Y座標を定め、右端部分に分布する点群の標高に基づいて当該辺下底の両端のZ座標を定める。例えば、壁面形状決定手段30は、第ηS列と第ηS1列との2列における点群の分布に基づいて台形の上底のX,Y座標及びその両端のZ座標を定め、第ηE列と第ηE-1列との2列における点群の分布に基づいて台形の下底のX,Y座標及びその両端のZ座標を定める。この場合、具体的には、第ηS列と第ηS1列との2列における点群のZ座標のうち最大値点136に対応及び最小値点138に対応を上底の両端のZ座標とすることができ、第ηE列と第ηE-1列との2列における点群のZ座標のうち最大値点140に対応及び最小値点142に対応を下底の両端のZ座標とすることができる。上底のX,Y座標は、点群のうち最も左側の点144や、第ηS列と第ηS1列との境界線146でのX,Y座標で、また、下底のX,Y座標は、点群のうち最も右側の点148や、第ηE列と第ηE-1列との境界線150でのX,Y座標で定義することができる。図9は追跡手段32の概略の処理フロー図である。追跡手段32は注目部分空間にて検出されたエッジを連続追跡処理の基点として設定しS160、エッジリストA,Bを空にする初期化処理を行うS162。基点エッジについて取得された壁面要素が既に図形データベースに図形登録されているか調べS166、登録されていない、つまり新規である場合にはS166にてNoの場合、当該壁面要素をエッジリストAに追加するS168。さらに追跡手段32は、基点エッジの両端それぞれに連なるエッジを追跡する。具体的には、垂直方向壁面位置ごとに基点エッジの一方端PAから伸びる向きに連なるエッジを順次検出し、検出したエッジに対応する壁面要素を求める連続壁面追跡処理が行われ、取得した壁面要素はエッジリストAに追加登録されるS170。同様に、基点エッジの他方端PBから伸びる向きにも連続壁面追跡処理が行われ、取得された壁面要素はエッジリストBに追加登録されるS172。或る基点エッジについて追跡手段32による処理が終わると、壁面要素登録手段34による処理が行われる図14のノードGへ処理が進む。一方、処理S166において、基点エッジでの壁面要素が既に図形データベースに図形登録されている場合にはS166にてYesの場合、演算処理装置4は、当該壁面要素についての追跡処理や登録処理は行わずに、処理を図15に示すノードHに進める。この場合の処理については後述する。図10、図11は処理S170,S172にて行われる連続壁面追跡処理の概略のフロー図である。追跡手段32は既に検出されているエッジに連続するエッジを探索する空間として直方体の探索空間を設定する。探索空間は既検出エッジの探索空間に隣接する空間であり、探索空間の平面形状である長方形の短辺の中点は既検出エッジの端部に配置される。また、探索空間のZ値の範囲上面及び底面の高さは、既検出エッジにおける壁面要素の垂直方向の位置に応じて設定される。例えば、既検出の壁面要素の形状である台形の上側の辺と下側の辺が勾配を有し得ることを考慮して、探索空間の上面の高さを既検出の壁面要素の鉛直な2辺のうち当該探索空間が接続される側の辺の上端より高く設定し、一方、探索空間の底面の高さを当該辺の下端より低く設定することができる。探索空間の平面形状の長辺の長さは部分空間の幅Wや奥行きDと同程度に設定することができ、例えば50cmとすることができる。まず、追跡手段32は既険出のエッジである線分を追跡しようとする側に延長し、当該延長線の向きに探索空間を配置するS180。すなわち、探索空間はその平面形状である長方形の長辺に沿った中心線を当該延長線に一致させるように配置される。そして、当該探索空間内に位置する点群のデータを記憶装置6からRAM等の作業領域に取り込みS180、処理S86と同様の手法により当該探索空間にてエッジを探すS182。当該探索空間にてエッジが存在した場合S184にてYesの場合、追跡手段32はさらに、処理S122と同様にして探索空間の点群データから壁面要素となる台形を決定する処理を行うS186。壁面要素の形状を取得できた場合にはS188にてYesの場合、エッジの微調整処理が行われるS190。そして処理は処理S180に戻り、今得られたエッジを既検出エッジとして、連続壁面の追跡処理が継続される。既検出エッジの延長線上の探索空間にてエッジ又は壁面要素を検出できない場合処理S184にてNoの場合、及びS188にてNoの場合は、図11のノードCBに進み、既検出エッジの延長線からずれた方向における探索処理が行われる。当該探索処理では、探索空間をその中心軸を水平面内にて当該延長線の位置から時計回り方向と反時計回り方向とに変化させて設定する。例えば、延長線の向きからの中心軸の向きの変化範囲±θとその分割数kを設定し、θ/kずつ水平面内での角度が異なる複数の探索空間を設定し、各探索空間にてエッジを探し、そして角度を変えて設定した複数の探索空間にて得られたエッジのうち最も点群が集まるものを選択するS200。一番点群が集まるエッジを特定できた場合S202にてYesの場合、追跡手段32はさらに、処理S122と同様にして探索空間の点群データから壁面要素となる台形を決定する処理を行うS204。壁面要素の形状を取得できた場合にはS206にてYesの場合、後述する微調整処理が行われるS208。そして処理は図10のノードCAに戻り、今得られたエッジを既検出エッジとして、連続壁面の追跡処理が継続される。角度を変えた探索空間にてエッジ又は壁面要素を検出できない場合処理S202にてNoの場合、及びS206にてNoの場合は、連続壁面追跡処理は終了し、当該処理をサブルーチンとして呼び出した処理S170又はS172に戻る。図12及び図13はエッジの微調整処理S190,S208の概略のフロー図である。演算処理装置4はエッジを示す線分が得られると、当該線分を一定の長さの区間に区切りS220、各区間にてエッジが通る点代表点を探索し、エッジをX-Y面内にてPA,PBを結ぶ線分に代えて、各区間にて求めた代表点をつなぐ折れ線とする。ここでは区間数をNとする。演算処理装置4は、選択した区間Kから代表点PKが得られると、当該代表点PKの水平面内の座標XK,YKと、当該区間での壁面要素の標高値の最小値ZLK及び最大値ZHKとを、代表点情報として求める。例えば、ZLK,ZHKはエッジの両端PA,PBでの値を補間して求めることができる。演算処理装置4はまず、エッジの一方端PAを代表点とし、PAについての代表点情報をエッジ代表点リストに格納するS222。続いて、区間番号Kを1ずつ増加させて、区間を選択しS224,S226、各区間にて代表点を探索するS230。当該処理S230では、水平断面が選択した区間の近傍領域であり、垂直方向に壁面要素に応じた高さを有する空間を設定し、当該区間内の点群データを取り込んで、当該空間の水平断面内にて最も点群が密集する位置を求める。そして当該位置に密集する点の数が予め定めた個数以上であればS232にてYesの場合、当該位置を代表点としてエッジ代表点リストに追加するS234。一方、当該位置に密集する点の数が予め定めた個数未満であればS232にてNoの場合、当該区間からはエッジの代表点をエッジ代表点リストに追加せずに次の区間の処理に進む。全ての区間について処理が終わるとS228にてYesの場合、エッジの他方端PBをエッジ代表点リストに追加しS236、図13のノードCV-Rに進む。演算処理装置4はエッジ代表点リストに格納されている代表点の数mをカウントするS240。そして、隣接する代表点PJとPJ1の対をJを1からm-1まで1ずつ増加させて選択しS242~S246、PJの代表点情報とPJ1の代表点情報とで表される壁面要素が既に図形データベースに図形登録されているか調べるS248。登録されていない場合にはS250にてNoの場合、当該壁面要素をエッジリストA又はBに追加しS252、処理S244に戻る。一方、既に図形データベースに図形登録されていた場合S250にてYesの場合、エッジの微調整処理S190,S208を終了する。さて、図9の説明で述べたように、或る基点エッジについて追跡手段32による処理が終わると、壁面要素登録手段34による処理が行われる。図14は壁面要素登録手段34の概略の処理フロー図である。壁面要素登録手段34は、追跡手段32により生成されたエッジリストA,Bが空でなければS260,S264にてNoの場合、それらエッジリストに格納されている壁面要素を図形データベースに登録しS262,S266、図15のノードHへ処理を進める。ここまで処理を行ってきた基点エッジは、処理S84で指定される第I階のブロック空間から処理S88で検出されたエッジである。演算処理装置4は当該基点エッジについて処理S116で指定された第J階層での処理を終えると、注目部分空間のうち当該階層に対応する高さ範囲にて、他のエッジを探索して壁面要素を決定する処理を行う。これにより例えば、同じ高さ範囲における多重エッジを検出して、それぞれに対応する壁面要素を決定することができる。図15は第J階層にて最初のエッジ主エッジと称するについての処理を終えた後の処理フロー図である。演算処理装置4は第J階層にて主エッジの処理を終えると、当該階層に存在する他のエッジ多重エッジと称するを探索して壁面要素を決定する処理多重エッジ処理S270を行う。多重エッジ処理S270が終了すると、処理は図6のノードEに戻り、次の階層における主エッジの処理が開始される。図16は多重エッジ処理の概略の処理フロー図である。多重エッジ処理では、主エッジの両側に別のエッジがないか探索する。図17は多重エッジ処理を説明する模式図であり、部分空間の平面配置を示している。図17aに示す例では、注目部分空間280には最も点群が集まるエッジ282と、エッジ282より点群の集まり度合いが低いエッジ284とが存在している。既に説明した水平面内探索手段26、垂直位置決定手段28、壁面形状決定手段30、追跡手段32及び壁面要素登録手段34による処理で、主エッジとなるエッジ282が検出され、当該エッジ282について追跡や図形登録の処理が行われる。多重エッジ処理では、当該エッジ282を含まないようにその両側に多重エッジ探索空間286,288を設定する図17b。多重エッジ探索空間は例えば、平面形状が部分空間と同程度の大きさ形状の矩形であり、Z値の範囲が第J階層と同程度である直方体の空間に設定される。例えば、主エッジ図17のエッジ282が延びるいずれかの方向に向かって、当該エッジより左側の領域に多重エッジ探索空間を作成して当該空間内の点群を取り込みS300、処理S86と同様に当該多重エッジ探索空間でエッジの探索を行い、エッジが存在するかを判定するS302。エッジが存在する場合S302でYesの場合は、多重エッジ探索空間内にて当該エッジを中心として図6の処理S110における垂直探索空間と同様の平面形状の空間を設定し、当該空間内の点群から処理S122と同様にして壁面要素の形状を決定する処理を行うS304。壁面要素の形状を取得できた場合にはS306にてYesの場合、図9で説明した追跡手段32による連続壁面追跡処理S160~S172、及び図14で説明した壁面要素登録手段34による登録処理S260~S266と同様の処理S308が行われる。同様に主エッジより右側の領域に多重エッジ探索空間を作成して、上述した左側の場合の処理S300~S308と同様の処理S310~S318が行われる。上記実施形態では、コンピュータを壁面抽出システム2の各手段として動作させるプログラムは記憶装置6に格納され、コンピュータはこれを読み出して実行する構成としたが、他の構成では、当該プログラムはネットワーク等の通信媒体を介してコンピュータに提供することができ、この場合、壁面抽出システム2は通信装置を備え当該通信装置がネットワーク等からプログラムを取得し、演算処理装置4に提供したり、記憶装置6に記憶させる。また、当該プログラムはCD-ROMCompactDiscReadOnlyMemory等の記録媒体に格納して提供することも可能である。"