(57)【特許請求の範囲】
【請求項１】
対象空間における地物表面の三次元形状を表す点群データに基づいて前記地物の壁面を検出するデータ解析装置であって、
前記対象空間を垂直面により水平面内にて二次元メッシュ状に分割して、柱状の複数の部分空間を設定する部分空間設定手段と、
前記部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する部分空間選択手段と、
前記注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定するブロック空間設定手段と、
水平面内における前記壁面の位置を探索する水平面内探索手段と、を有し、
前記水平面内探索手段は、前記ブロック空間ごとに、前記水平面内の線分のうち、前記水平面に射影された前記点群が予め設定した基準以上に近傍に集まるものを探索して水平面内壁面位置と定めること、
を特徴とするデータ解析装置。
【請求項２】
請求項１に記載のデータ解析装置において、
前記対象空間にて前記水平面内壁面位置に存在する前記壁面の垂直方向の位置を求める垂直位置決定手段を有し、
当該垂直位置決定手段は、前記水平面内壁面位置ごとに、前記点群のうち前記水平面への射影位置が当該水平面内壁面位置から予め設定した距離内にあるものを注目点群として抽出し、垂直方向に関して当該注目点群が予め設定した閾値以上存在する各範囲を当該水平面内壁面位置での垂直方向壁面位置と定めること、
を特徴とするデータ解析装置。
【請求項３】
請求項２に記載のデータ解析装置において、
前記水平面内壁面位置での各垂直方向壁面位置に存在する前記壁面の形状を、当該垂直方向壁面位置での前記注目点群の分布範囲に基づいて求める壁面形状決定手段を有し、
前記壁面形状決定手段は、前記水平面内壁面位置における鉛直面上の台形であって、その平行な２辺を鉛直方向に設定され、前記分布範囲を前記鉛直面に射影した形状を近似するものを前記壁面の形状とすること、
を特徴とするデータ解析装置。
【請求項４】
請求項２又は請求項３に記載のデータ解析装置において、
既に検出されている前記水平面内壁面位置における前記垂直方向壁面位置ごとに、当該水平面内壁面位置の端部に連なる新たな前記水平面内壁面位置を求める追跡手段を有し、
前記追跡手段は、既検出の前記水平面内壁面位置の端部に短辺の中点を接続された長方形を平面形状とする直方体の空間であってその高さが前記垂直方向壁面位置に対応して配置される隣接空間を、前記長方形の長辺に沿った中心線を前記水平面内壁面位置の延長線に一致させて設定し、当該隣接空間内に前記点群が予め設定した基準以上に集まる場合には当該隣接空間内の点群の前記水平面内での分布に沿った線分を新たな前記水平面内壁面位置とし、一方、前記中心線を前記延長線に一致させて設定した前記隣接空間にて新たな前記水平面内壁面位置が検出されなかった場合は、前記水平面内での前記中心線の向きを変えて内部に最も点群が集まる前記隣接空間を探索し、得られた当該隣接空間内の点群の前記水平面内での分布に沿った線分を新たな前記水平面内壁面位置とすること、
を特徴とするデータ解析装置。
【請求項５】
対象空間における地物表面の三次元形状を表す点群データに基づいて前記地物の壁面を検出するデータ解析方法であって、
前記対象空間を垂直面により水平面内にて二次元メッシュ状に分割して、柱状の複数の部分空間を設定する部分空間設定ステップと、
前記部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する部分空間選択ステップと、
前記注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定するブロック空間設定ステップと、
水平面内における前記壁面の位置を探索する水平面内探索ステップと、を有し、
前記水平面内探索ステップは、前記ブロック空間ごとに、前記水平面内の線分のうち、前記水平面に射影された前記点群が予め設定した基準以上に近傍に集まるものを探索して水平面内壁面位置と定めること、
を特徴とするデータ解析方法。
【請求項６】
コンピュータに、対象空間における地物表面の三次元形状を表す点群データに基づいて前記地物の壁面を検出するデータ解析を行わせるためのプログラムであって、当該コンピュータを、
前記対象空間を垂直面により水平面内にて二次元メッシュ状に分割して、柱状の複数の部分空間を設定する部分空間設定手段、
前記部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する部分空間選択手段、
前記注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定するブロック空間設定手段、及び
水平面内における前記壁面の位置を探索する水平面内探索手段、として機能させ、
前記水平面内探索手段は、前記ブロック空間ごとに、前記水平面内の線分のうち、前記水平面に射影された前記点群が予め設定した基準以上に近傍に集まるものを探索して水平面内壁面位置と定めること、
を特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地物表面の三次元形状を表す点群データに基づいて地物の壁面を検出するデータ解析装置、データ解析方法、及びプログラムに関する。
【背景技術】
【０００２】
特許文献１には、レーザスキャナを用いて、地物の形状を表す三次元点群データを取得する技術が示されている。例えば、モービルマッピングシステムでは、レーザスキャナは自動車の上部に搭載され、周囲にレーザを照射する。レーザの光軸は仰俯角及び方位角を変えることにより垂直方向及び水平方向に走査され、走査範囲内にて微小角度ごとにレーザパルスが発射される。レーザの発射から反射光の受信までの時間に基づいて距離が計測され、またその際、レーザの発射方向、時刻、及び車体の位置・姿勢などが計測される。それら計測データから、レーザパルスを反射した点の三次元座標を表す点群データが求められる。
【０００３】
また、点群データの取得と同時に、カメラを用いて映像が撮影される。画像はデータ解析にてユーザが計測対象部分を指定する際に利用することができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００９−２０４６１５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来、点群データをもとに地物を判読するためには人手を要しており、三次元ＣＡＤで編集ツール等を利用して手作業で地物の抽出作業が行われていた。
【０００６】
本発明は、地物表面の三次元形状を表す点群データに基づいて地物の壁面を自動的に検出するデータ解析装置、データ解析方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係るデータ解析装置は、対象空間における地物表面の三次元形状を表す点群データに基づいて前記地物の壁面を検出するものであって、前記対象空間を垂直面で分割して、柱状の複数の部分空間を設定する部分空間設定手段と、前記部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する部分空間選択手段と、前記注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定するブロック空間設定手段と、水平面内における前記壁面の位置を探索する水平面内探索手段と、を有し、前記水平面内探索手段は、前記ブロック空間ごとに、前記水平面内の線分のうち、前記水平面に射影された前記点群が予め設定した基準以上に近傍に集まるものを探索して水平面内壁面位置と定める。
【０００８】
他の本発明に係るデータ解析装置は、前記対象空間にて前記水平面内壁面位置に存在する前記壁面の垂直方向の位置を求める垂直位置決定手段を有し、当該垂直位置決定手段は、前記水平面内壁面位置ごとに、前記点群のうち前記水平面への射影位置が当該水平面内壁面位置から予め設定した距離内にあるものを注目点群として抽出し、垂直方向に関して当該注目点群が予め設定した閾値以上存在する各範囲を当該水平面内壁面位置での垂直方向壁面位置と定める。
【０００９】
また他の本発明に係るデータ解析装置は、さらに、前記水平面内壁面位置での各垂直方向壁面位置に存在する前記壁面の形状を、当該垂直方向壁面位置での前記注目点群の分布範囲に基づいて求める壁面形状決定手段を有し、前記壁面形状決定手段は、前記水平面内壁面位置における鉛直面上の台形であって、その平行な２辺を鉛直方向に設定され、前記分布範囲を前記鉛直面に射影した形状を近似するものを前記壁面の形状とする。
【００１０】
別の本発明に係るデータ解析装置は、既に検出されている前記水平面内壁面位置における前記垂直方向壁面位置ごとに、当該水平面内壁面位置の端部に連なる新たな前記水平面内壁面位置を求める追跡手段を有し、前記追跡手段は、既検出の前記水平面内壁面位置の端部に短辺の中点を接続された長方形を平面形状とする直方体の空間であってその高さが前記垂直方向壁面位置に対応して配置される隣接空間を、前記長方形の長辺に沿った中心線を前記水平面内壁面位置の延長線に一致させて設定し、当該隣接空間内に前記点群が予め設定した基準以上に集まる場合には当該隣接空間内の点群の前記水平面内での分布に沿った線分を新たな前記水平面内壁面位置とし、一方、前記中心線を前記延長線に一致させて設定した前記隣接空間にて新たな前記水平面内壁面位置が検出されなかった場合は、前記水平面内での前記中心線の向きを変えて内部に最も点群が集まる前記隣接空間を探索し、得られた当該隣接空間内の点群の前記水平面内での分布に沿った線分を新たな前記水平面内壁面位置とする。
【００１１】
本発明に係るデータ解析方法は、対象空間における地物表面の三次元形状を表す点群データに基づいて前記地物の壁面を検出する方法であって、前記対象空間を垂直面で分割して、柱状の複数の部分空間を設定する部分空間設定ステップと、前記部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する部分空間選択ステップと、前記注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定するブロック空間設定ステップと、水平面内における前記壁面の位置を探索する水平面内探索ステップと、を有し、前記水平面内探索ステップは、前記ブロック空間ごとに、前記水平面内の線分のうち、前記水平面に射影された前記点群が予め設定した基準以上に近傍に集まるものを探索して水平面内壁面位置と定める。
【００１２】
本発明に係るプログラムは、コンピュータに、対象空間における地物表面の三次元形状を表す点群データに基づいて前記地物の壁面を検出するデータ解析を行わせるためのプログラムであって、当該コンピュータを、前記対象空間を垂直面で分割して、柱状の複数の部分空間を設定する部分空間設定手段、前記部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する部分空間選択手段、前記注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定するブロック空間設定手段、及び水平面内における前記壁面の位置を探索する水平面内探索手段、として機能させ、前記水平面内探索手段は、前記ブロック空間ごとに、前記水平面内の線分のうち、前記水平面に射影された前記点群が予め設定した基準以上に近傍に集まるものを探索して水平面内壁面位置と定める。
【発明の効果】
【００１３】
本発明によれば、地物表面の三次元形状を表す点群データに基づいて地物の壁面を自動的に検出することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施形態に係る壁面抽出システムの概略の構成を示すブロック図である。
【図２】本発明の実施形態に係る壁面抽出システムによる壁面抽出処理の概略のフロー図である。
【図３】部分空間設定手段及び部分空間選択手段による処理の概略のフロー図である。
【図４】ブロック空間設定手段及び水平面内探索手段による処理の概略のフロー図である。
【図５】ブロック空間でのエッジの探索処理を説明する模式図である。
【図６】垂直位置決定手段及び壁面形状決定手段による処理の概略のフロー図である。
【図７】垂直位置決定手段による垂直探索空間における点群のグループ化を説明するための説明図である。
【図８】壁面要素の形状を求める処理を説明する模式図である。
【図９】追跡手段による処理の概略のフロー図である。
【図１０】連続壁面追跡処理の概略のフロー図である。
【図１１】連続壁面追跡処理の概略のフロー図である。
【図１２】エッジの微調整処理の概略のフロー図である。
【図１３】エッジの微調整処理の概略のフロー図である。
【図１４】壁面要素登録手段による処理の概略のフロー図である。
【図１５】或る階層における主エッジについての処理を終えた後の処理フロー図である。
【図１６】多重エッジ処理の概略のフロー図である。
【図１７】多重エッジ処理を説明する模式図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態（以下実施形態という）である壁面抽出システム２について、図面に基づいて説明する。本システムは、地物表面の三次元形状を表す点群データに基づいて地物の壁面、すなわち地物表面のうち地表面に略垂直である面を検出するデータ解析装置である。点群データは例えば、上述のモービルマッピングシステムのように地上を走行する車両に搭載されたレーザスキャナにより取得される。また、レーザスキャナを地上に設置して計測を行っても良い。点群データが地物表面の三次元形状を表すには、地物表面の凹凸のスケールに応じた点密度でレーザスキャンが行われる必要がある。この点、車両や三脚を用いて道路等の地上から行うレーザスキャンは、例えば、道路の近傍に建つ建物、塀、看板及び標識などの壁面の形状を捉えることができる程度の走査密度を実現できる。
【００１６】
図１は、壁面抽出システム２の概略の構成を示すブロック図である。本システムは、演算処理装置４、記憶装置６、入力装置８及び出力装置１０を含んで構成される。演算処理装置４として、本システムの各種演算処理を行う専用のハードウェアを作ることも可能であるが、本実施形態では演算処理装置４は、コンピュータ及び、当該コンピュータ上で実行されるプログラムを用いて構築される。
【００１７】
当該コンピュータのＣＰＵ（Central Processing Unit）が演算処理装置４を構成し、後述する部分空間設定手段２０、部分空間選択手段２２、ブロック空間設定手段２４、水平面内探索手段２６、垂直位置決定手段２８、壁面形状決定手段３０、追跡手段３２、及び壁面要素登録手段３４として機能する。
【００１８】
記憶装置６はコンピュータに内蔵されるハードディスクなどで構成される。記憶装置６は演算処理装置４を部分空間設定手段２０、部分空間選択手段２２、ブロック空間設定手段２４、水平面内探索手段２６、垂直位置決定手段２８、壁面形状決定手段３０、追跡手段３２及び壁面要素登録手段３４として機能させるためのプログラム及びその他のプログラムや、本システムの処理に必要な各種データを記憶する。例えば、記憶装置６は、処理対象データとして解析の対象空間の点群データを格納される。例えば、道路に沿った地域が解析の対象空間とされる。
【００１９】
入力装置８は、キーボード、マウスなどであり、ユーザが本システムへの操作を行うために用いる。
【００２０】
出力装置１０は、ディスプレイ、プリンタなどであり、本システムにより求められた壁面の対象空間内での位置を画面表示、印刷等によりユーザに示す等に用いられる。
【００２１】
図２は、壁面抽出システム２による壁面抽出処理の概略のフロー図である。この図２を参照しながら、演算処理装置４の各手段を説明する。
【００２２】
部分空間設定手段２０は、対象空間を垂直面で分割して得られる柱状の複数の部分空間を壁面抽出の処理の初期の単位空間として設定する（Ｓ４０）。本実施形態では、部分空間設定手段２０は、対象空間を水平面（ＸＹＺ直交座標系でＸ−Ｙ平面とする）内にて二次元直交格子（メッシュ）状に分割して四角柱形状の部分空間を生成する。例えば、部分空間の水平断面は幅Ｗ及び奥行きＤが５０ｃｍの正方形とすることができる。部分空間の高さＨは対象空間の高さ（Ｚ軸方向の寸法）と一致させることができ、その高さは検出目的とする壁面の高さ、具体的には建物の高さや、看板・標識が配置された高さより大きく設定される。なお、部分空間設定手段２０を構成するプログラムでは、幅Ｗ、奥行きＤ及び高さＨはパラメータ化されており、例えば、ユーザが入力装置８を用いて変更することができる。
【００２３】
部分空間選択手段２２は部分空間のうち予め設定した閾値以上の高低差を有する点群を含むものを注目部分空間として選択する。具体的には、部分空間選択手段２２は、複数設定された部分空間を所定の順序で選択し、当該部分空間内の点群に閾値以上の高低差が存在する場合に、当該部分空間を注目部分空間とする。上述したように点群データは道路等に位置するレーザスキャナからのレーザ照射によって取得され、当該レーザスキャナから見える壁面が点群データによる三次元形状上に捉えられる。そこで、部分空間選択手段２２は例えば、当該三次元形状にて道路等に対応する平面の部分に基づいて基準平面を決定し、また、道路に沿って道幅内に水平に当該三次元形状の中心線を設定する（Ｓ４２）。そして、当該中心線に沿って順番に部分空間の選択の起点を設定し、中心線に直交する線に沿って両側方向に当該起点から近い順に部分空間を選択して（Ｓ４４）、選択した部分空間内の点群の高低差が閾値以上であれば当該部分空間を注目部分空間と判定する（Ｓ４６）。
【００２４】
ブロック空間設定手段２４は、注目部分空間を水平面で分割して、縦に積み重なる複数のブロック空間を設定する（Ｓ４８）。例えば、ブロック空間の高さＨＢは部分空間の幅Ｗ、奥行きＤと同程度に設定することができる。
【００２５】
水平面内探索手段２６は、ブロック空間ごとに、水平面内にて当該水平面に射影された点群が予め設定した基準以上に近傍に集まる線分を探索して、当該線分を水平面内における壁面の位置（水平面内壁面位置）と定める（Ｓ５０）。ブロック空間ごとに水平面内壁面位置を探索することで、垂直方向に細長い注目部分空間にて異なる高さに存在し得る、位置・向きが相違した複数の壁面を弁別できる。
【００２６】
垂直位置決定手段２８は、対象空間にて水平面内壁面位置に存在する壁面の垂直方向の位置を求める（Ｓ５２）。具体的には、垂直位置決定手段２８は、注目部分空間にて検出される水平面内壁面位置ごとに、当該注目部分空間の点群のうち水平面への射影位置が当該水平面内壁面位置から予め設定した距離内にあるものを注目点群として抽出する。そして、水平面内壁面位置ごとに抽出された注目点群について、垂直方向の位置に関して当該注目点群が予め設定した閾値以上存在する各範囲を当該水平面内壁面位置での垂直方向壁面位置と定める。これにより、或るブロック空間で検出された水平面内壁面位置に基づいて、当該ブロック空間以外の高さ範囲にて当該水平面内壁面位置に存在する壁面も検出される。例えば、連続する複数のブロック空間に跨がる壁面について一つの垂直方向壁面位置が定められる。また、高さ方向に分離した複数の壁面が同じ水平面内壁面位置に存在する、つまり壁面が垂直方向に階層をなす場合には、それら階層をなす壁面それぞれについて垂直方向壁面位置が求められる。
【００２７】
水平面内壁面位置と当該水平面内壁面位置に対する垂直方向壁面位置との組は、注目部分空間内の一枚の壁面の配置を表す。当該壁面は当該注目部分空間の外側、つまり横方向に広がるより大きな壁面の一部であり得ることから、ここでは壁面要素と称する。
【００２８】
壁面形状決定手段３０は、水平面内壁面位置において各垂直方向壁面位置に存在する壁面要素の形状を、当該垂直方向壁面位置での注目点群の分布範囲に基づいて求める（Ｓ５４）。具体的には、壁面形状決定手段３０は、水平面内壁面位置を通る鉛直面にて注目点群を射影し、射影された点群の分布範囲に基づいて壁面要素の形状を求める。当該形状は、平行な２辺である上底及び下底を鉛直方向に設定され、かつ鉛直面に射影された点群の分布範囲を近似する台形とされる。
【００２９】
追跡手段３２は、既に検出されている水平面内壁面位置における垂直方向壁面位置ごとに、当該水平面内壁面位置の端部に連なる新たな水平面内壁面位置を求める（Ｓ５６）。追跡手段３２は壁面要素の横方向に隣接する直方体の空間を設定し、当該隣接空間内の点群を水平面に射影し、射影された点群が予め設定した基準以上に近傍に集まる線分を探索して新たな水平面内壁面位置と定める。当該処理を順次繰り返すことで、注目部分空間にて特定された壁面要素から横方向に連続する壁面の水平面内壁面位置がトレースされる。
【００３０】
具体的には、隣接空間は、平面形状が既検出の水平面内壁面位置の端部に短辺の中点を接続された長方形である直方体に設定される。ここでは、当該長方形の長辺に沿った中心線を水平面内での隣接空間の向きとする。また、当該隣接空間の高さ、つまり直方体の上面と底面とで定義される垂直方向の範囲は、垂直方向壁面位置に対応した位置に配置される。
【００３１】
追跡手段３２はまず、既検出の水平面内壁面位置を真っ直ぐに延長した向きに隣接空間を設定する。つまり、隣接空間はその平面形状の長方形の上記中心線が既検出の水平面内壁面位置の延長線に一致するように配置される。そして、当該隣接空間内に点群が予め設定した基準以上に集まる場合には当該隣接空間内の点群の水平面内での分布に沿った線分を新たな水平面内壁面位置とする。一方、既検出の水平面内壁面位置の延長線に向きを一致させて設定した隣接空間にて新たな水平面内壁面位置が検出されなかった場合は、追跡手段３２は隣接空間の向きを変化させて水平面内壁面位置を探す。つまり、向きを変化させた隣接空間のうち内部に最も点群が集まるものを探索し、得られた当該隣接空間内の点群の水平面内での分布に沿った線分を新たな水平面内壁面位置とする。
【００３２】
上述のようにして対象空間にて検出された壁面要素に関する情報は壁面要素登録手段３４により記憶装置６に登録される。登録された壁面要素の形状の情報や接続関係の情報は例えば、建物の壁面形状の認識や建物の三次元モデルの構築に用いられる。
【００３３】
以下、壁面抽出システム２の処理例をより詳しく説明する。図３、図４、図６、図９〜図１６は、演算処理装置４が実行する一連の処理の流れを分割して示す処理フロー図である。図３に示す処理は上述した部分空間設定手段２０及び部分空間選択手段２２による処理に当たる。壁面抽出システム２が壁面抽出処理を開始すると（Ｓ６０）、部分空間設定手段２０は、対象空間内に部分空間を順次作成する。例えば、対象空間をＸ軸方向及びＹ軸方向に沿ってメッシュ状に分割する場合、部分空間の幅Ｗ及び奥行きＤがパラメータとして設定されると、それらが当該メッシュの間隔（部分空間のサイズ）となり、対象空間のサイズに応じてＸ，Ｙ各方向の部分空間の配列個数が定まる。当該配列個数により、Ｘ，Ｙ各方向の部分空間の位置を示すインデックスの範囲が決定される。部分空間設定手段２０は、部分空間の二次元メッシュ状の配置を表すインデックスを所定の順番で変更し、設定されたインデックスに応じた位置（Ｘ，Ｙ各方向の座標範囲）で定義される部分空間を設定する（Ｓ６２）。
【００３４】
ここで、道路を走行する車両上からレーザ照射を行い点群データを取得した場合、上述したように、点群データが表す三次元形状にて道路等に対応する平面の部分に基づいて基準平面が設定され、道路に沿って当該三次元形状の中心線が設定される。説明を簡単にするために、当該中心線をＸ軸（つまりＹ＝０）とし、車両が走行する方向にＸ方向のインデックスが増加し、道幅方向に対応するＹ方向に関しては、中心線から離れるに従ってインデックスの絶対値が増加するものとする。例えば、Ｙ方向のインデックスは中心線の位置では０とし、走行方向に対して左向きに、１，２，３，…と設定し、右向きには−１，−２，−３，…と設定することができる。この場合、部分空間設定手段２０は例えば、Ｘ方向のインデックスを順番にインクリメントし、Ｘ方向のインデックスの各値にて、Ｙ軸の正方向と負方向との両方向にＹ方向のインデックスを変化させる。すなわち、部分空間設定手段２０はＸ方向の或るインデックスの値にて、Ｙ方向のインデックスを０から順番に増加させて部分空間を設定し、また−１から順番に減少させて部分空間を設定する。
【００３５】
インデックス指定されたメッシュの部分空間が未処理のものであれば（Ｓ６４にて「Ｎｏ」の場合）、部分空間選択手段２２は当該部分空間内の点群を例えば、ハードディスク等の記憶装置６からＲＡＭ（Random Access Memory）等の作業領域に取り込む（Ｓ６６）。部分空間に取り込んだ点群内に所定閾値Ｔｈ１以上の高低差がある場合（Ｓ６８にて「Ｙｅｓ」の場合）には、部分空間選択手段２２は当該部分空間を注目部分空間と判断して、当該注目部分空間での水平面内壁面位置や垂直方向壁面位置の探索等の処理が開始される（図４のノードＢへ処理が進む）。例えば、閾値Ｔｈ１は道路等の地表の略平坦な部分のみを含む部分空間を排除できる程度に小さく設定することができる。また、閾値Ｔｈ１を、壁面を検出しようとする地物の高さに応じて設定して、関心のない低い地物の壁面は検出しないようにすることもできる。例えば、道路から見て建物の手前に存在するガードレールや郵便ポストなどの比較的低い地物を検出対象外とするように閾値Ｔｈ１を建物の１階の高さ程度に設定することができる。
【００３６】
設定した部分空間から取り込んだ点群の高低差が閾値Ｔｈ１未満である場合（Ｓ６８にて「Ｎｏ」の場合）には、当該部分空間における壁面抽出処理は行わない。この場合は、部分空間設定手段２０が次の部分空間を設定する（ノードＡへ処理が戻る）。
【００３７】
全てのメッシュについて処理が終わっている場合は（Ｓ６４にて「Ｙｅｓ」の場合）、演算処理装置４は壁面抽出の処理を終える（Ｓ７０）。
【００３８】
図４は演算処理装置４が実行する一連の処理のうち上述したブロック空間設定手段２４及び水平面内探索手段２６が行う部分の概略の処理フロー図である。
【００３９】
ブロック空間設定手段２４は、注目部分空間を一定の高さＨＢごとに分割して、縦に積み重なる複数のブロック空間を設定し、各ブロック空間内に位置する点群のデータを記憶装置６からＲＡＭ等の作業領域に取り込む（Ｓ８０）。例えば、部分空間の幅Ｗ、奥行きＤを５０ｃｍとする場合にはブロック空間の高さＨＢは２０〜５０ｃｍとすることができる。当該分割により設定されるブロック空間の段数をｎ段とし、インデックスＩを用いて下から順に第Ｉ階(Ｉ＝１，２，…，ｎ）と表す。
【００４０】
水平面内探索手段２６はｎ段のブロック空間を順番に選択して、当該ブロック空間にエッジ（水平面内壁面位置）が存在するかを調べる。例えば、水平面内探索手段２６はインデックスＩを１ずつ増加させて、エッジの存在を調べるブロック空間を選択する（Ｓ８２，Ｓ８４）。水平面内探索手段２６は、選択した第Ｉ階のブロック空間にエッジが存在するかを調べ（Ｓ８６）、存在しない場合には（Ｓ８８にて「Ｎｏ」の場合）次のブロック空間を選択する（Ｓ８４）。なお、Ｉがｎを越えた場合には、図３のノードＡに戻り、次の注目部分空間を探す（Ｓ９０）。
【００４１】
図５はブロック空間でのエッジの探索処理Ｓ８６を説明する模式図である。図５は、ブロック空間を上面から見た図であり、ブロック空間の幅Ｗ及び奥行きＤで定義される矩形１００と、ブロック空間内の点群のＸ−Ｙ面内での配置の一例が示されている。水平面内探索手段２６は、ブロック空間内の点群から任意の２つのデータ点ＰＡ，ＰＢを選択し、それら２点を両端とするＸ−Ｙ面内での線分Ｌ０をエッジの候補線として設定すると共に、線分Ｌ０を中心としてその両側にそれぞれ幅ｗ（合計幅２ｗ）の帯状領域ＥＡを設定する。水平面内探索手段２６は点群のうちＸ−Ｙ平面での座標が当該領域ＥＡ内に位置するデータ点の個数をカウントする。データ点が領域ＥＡ内であるか否かは例えば、Ｘ−Ｙ平面上での当該データ点から線分Ｌ０への垂線の長さがｗ以下であるか否かによって判定可能である。また、エッジの条件として、領域ＥＡ内の点群が表す三次元形状が平坦でないことを課す。具体的には、水平面内探索手段２６は、領域ＥＡ内に包含されるデータ点の高低差（最大標高と最小標高との差）ΔＺが予め設定した段差閾値γ以上であれば平坦ではないと判定する。
【００４２】
ここで、幅ｗはパラメータであり、壁面に対応するデータ点のエッジに直交する方向の位置のばらつきを吸収する。例えば、ｗは３ｃｍ程度とすることができる。また、高低差の閾値γは例えば２ｃｍ程度に設定できる。
【００４３】
水平面内探索手段２６は、ブロック空間内の２つのデータ点の全ての組み合わせについて候補線を設定して上述の判定を行い、領域ＥＡ内に最もデータ点が多く集まり、かつΔＺが閾値γ以上である線分Ｌ０をブロック空間にて見つけられたエッジとする。エッジが存在した場合には（Ｓ８８にて「Ｙｅｓ」の場合）、当該エッジが壁面要素を決定するための処理を行われていない新規なものであるか判定される（Ｓ９２）。当該判定は、壁面要素を決定するための処理の対象とされたエッジを登録したリストを検索して、処理Ｓ８６で見つけられたエッジと同一のものが存在するか否かに基づいて行われる。リストに同一のものが存在しなければ新規なエッジと判定し（Ｓ９２にて「Ｎｏ」の場合）、リストにエッジの両端ＰＡ，ＰＢの座標（ａｘ，ａｙ），（ｂｘ，ｂｙ）を登録する（Ｓ９４）。このように或るブロック空間にて新たなエッジが検出されると、当該エッジについて当該注目部分空間での垂直方向壁面位置の探索、及び壁面要素の形状の決定が行われる（図６のノードＤへ処理が進む）。一方、処理Ｓ８６にて見つけられたエッジと同一のエッジが他のブロック空間についての処理で既にリストに登録されると共に、垂直方向壁面位置の探索等の処理が行われている場合もあり、その場合は（Ｓ９２にて「Ｙｅｓ」の場合）、当該エッジについてのリストへの登録や垂直方向壁面位置の探索等の処理は省略され、水平面内探索手段２６は次のブロック空間について処理を行う（ノードＣへ処理が戻る）。
【００４４】
図６は垂直位置決定手段２８及び壁面形状決定手段３０の概略の処理フロー図である。垂直位置決定手段２８は、処理Ｓ８６にて抽出されたエッジＬ０での垂直方向における壁面の位置を探索するための空間として垂直探索空間を設定し、当該垂直探索空間内に位置する点群のデータを記憶装置６からＲＡＭ等の作業領域に取り込む（Ｓ１１０）。垂直探索空間は、平面形状がエッジＬ０を長手方向の中心軸とする矩形である直方体形状の空間であり、その底面及び上面は部分空間の底面及び上面と同じ高さに位置する。平面形状の矩形の短辺の寸法ξは例えば、エッジを抽出した帯状領域ＥＡの幅２ｗと同じ、またはやや大きめに設定することができる。例えば、ξは１０ｃｍに設定することができる。
【００４５】
垂直位置決定手段２８は垂直探索空間内の点群をＺ方向の分布に基づいてグループ化する（Ｓ１１２）。これにより或る水平面内壁面位置における垂直方向の壁面の階層構造が捉えられる。
【００４６】
グループ化において垂直位置決定手段２８は例えば、垂直探索空間に取り込んだ点群の最小標高から上へ、又は最大標高から下へ向けて一定の刻み幅ｈでＺ方向に複数の区間を設定する。そして、当該区間に基づいて垂直探索空間内の点群を複数の階層（ランク）に区分し、ランクごとに点群の数（点数）を集計する。ここで刻み幅ｈに応じて、垂直方向に隣接した２つの壁面を分離して検出できる分解能が定まり、基本的にはｈはＨＢ以下に設定される。ここでｈが小さいほど分解能が高くなるが、ｈが小さすぎると、壁面が存在する高さ範囲の区間での点数が小さくなり、壁面が存在しない高さ範囲での点数（基本的には０であることが期待される）との弁別が難しくなる。ｈはこれらを勘案して設定される。垂直位置決定手段２８はランクごとに点群の数を集計した点群分布に基づいて、垂直探索空間における点群をグループ化する。具体的には、点群が集まっているランク範囲をそれぞれ点群の１つのグループとし、当該ランク範囲を１つの垂直方向壁面位置とする。
【００４７】
図７はグループ化を説明するための説明図であり、ｈを０．２ｍとしてランクごとに点群の数を集計した結果である点群分布表の一例を示している。垂直位置決定手段２８は例えば、ランクを下（最小標高）から上へ順番に調べて、０より大きい点数を有するランクが連続する範囲ごとに順番にグループ番号を付与する。図７に示す例では点数が０より大きいランク範囲は、ランク１〜４、ランク９〜１２、ランク１８〜２２、及びランク２５〜２６の４つであり、これらランク範囲に順番にグループ番号１〜４が付与される。なお、点数が０より大きいランクが単独で現れる場合、つまり当該ランクの前後では点数が０である場合には、垂直位置決定手段２８は当該１つのランクを１つのランク範囲としてグループ番号を付与する。
【００４８】
グループ化により定まる階層数をｍと表す。図７に示す例ではｍは４である。壁面形状決定手段３０はｍ階層に設定されたランク範囲（垂直方向壁面位置）を順番に選択する。例えば、壁面形状決定手段３０はグループ番号Ｊを１ずつ増加させて、壁面要素の形状を決定するランク範囲を選択する（Ｓ１１４，Ｓ１１６）。そして、垂直探索空間に存在する点群のうち選択したランク範囲に存在するもののデータを記憶装置６からＲＡＭ等の作業領域に取り込み（Ｓ１２０）、当該点群データから壁面要素となる台形を決定する処理を行う（Ｓ１２２）。壁面要素の形状を決定できた場合には（Ｓ１２４にて「Ｙｅｓ」の場合）、当該壁面要素の横方向につながる壁面要素の水平面内壁面位置を順次求める追跡処理が開始される（図９のノードＦへ処理が進む）。
【００４９】
なお、ｍ階層全てについて壁面要素の決定処理が終わると（Ｓ１１８にて「Ｙｅｓ」の場合）、図４のノードＣへ戻り、次のエッジが探索され当該エッジについて同様の処理が繰り返される。また、或る階層にて壁面要素の形状を決定できなかった場合は（Ｓ１２４にて「Ｎｏ」の場合）、処理Ｓ１１６に戻り、次の階層についての処理が行われる。
【００５０】
図８は壁面要素の形状を求める処理Ｓ１２２を説明する模式図であり、垂直探索空間に存在する点群のうち１つの階層に対応するものをエッジを通る鉛直面に射影した様子の一例を示している。図８において矩形で示す鉛直面１３０に分布する黒点１３２が点群を射影した点である。矩形の鉛直面１３０は横方向がエッジに沿っており、左側がエッジの一方端ＰＡの側、右側が他方端ＰＢの側に対応している。また、鉛直面１３０の縦方向が鉛直方向であり、上端、下端はそれぞれランク範囲の上端、下端に対応している。壁面形状決定手段３０は鉛直面１３０を格子状に区切り、縦横に行列配置された複数の小矩形１３４を定義する。例えば、小矩形１３４の幅は１０ｃｍ程度、高さは５ｃｍ程度とすることができる。
【００５１】
壁面形状決定手段３０は、縦に並ぶ小矩形１３４の列を例えば左側から順に選択し、点群が射影される小矩形１３４が２つ以上存在する列を探す。そのような列が現れる範囲、つまり最初の位置（第ηＳ列）から最後の位置（第ηＥ列）までの列範囲が得られた場合には、さらに壁面要素の形状を特定する処理が行われる。一方、そのような列範囲が存在しない場合には当該階層には壁面要素は存在しないと判断される。
【００５２】
壁面形状決定手段３０は鉛直面１３０に射影された点群（黒点１３２）のうち左端部分に位置するものに基づいて台形の平行な２辺のうちの一方（ここではこれを台形の上底とする）とする鉛直線のＸ，Ｙ座標を定め、左端部分に分布する点群の標高に基づいて当該辺（上底）の両端のＺ座標を定める。また、右端部分に位置するものに基づいて台形の平行な２辺のうちの他方（ここではこれを台形の下底とする）とする鉛直線のＸ，Ｙ座標を定め、右端部分に分布する点群の標高に基づいて当該辺（下底）の両端のＺ座標を定める。例えば、壁面形状決定手段３０は、第ηＳ列と第（ηＳ＋１）列との２列における点群の分布に基づいて台形の上底のＸ，Ｙ座標及びその両端のＺ座標を定め、第ηＥ列と第（ηＥ−１）列との２列における点群の分布に基づいて台形の下底のＸ，Ｙ座標及びその両端のＺ座標を定める。この場合、具体的には、第ηＳ列と第（ηＳ＋１）列との２列における点群のＺ座標のうち最大値（点１３６に対応）及び最小値（点１３８に対応）を上底の両端のＺ座標とすることができ、第ηＥ列と第（ηＥ−１）列との２列における点群のＺ座標のうち最大値（点１４０に対応）及び最小値（点１４２に対応）を下底の両端のＺ座標とすることができる。上底のＸ，Ｙ座標は、点群のうち最も左側の点１４４や、第ηＳ列と第（ηＳ＋１）列との境界線１４６でのＸ，Ｙ座標で、また、下底のＸ，Ｙ座標は、点群のうち最も右側の点１４８や、第ηＥ列と第（ηＥ−１）列との境界線１５０でのＸ，Ｙ座標で定義することができる。
【００５３】
図９は追跡手段３２の概略の処理フロー図である。追跡手段３２は注目部分空間にて検出されたエッジを連続追跡処理の基点として設定し（Ｓ１６０）、エッジリストＡ，Ｂを空にする初期化処理を行う（Ｓ１６２）。基点エッジについて取得された壁面要素が既に図形データベースに図形登録されているか調べ（Ｓ１６６）、登録されていない、つまり新規である場合には（Ｓ１６６にて「Ｎｏ」の場合）、当該壁面要素をエッジリストＡに追加する（Ｓ１６８）。
【００５４】
さらに追跡手段３２は、基点エッジの両端それぞれに連なるエッジを追跡する。具体的には、垂直方向壁面位置ごとに基点エッジの一方端ＰＡから伸びる向きに連なるエッジを順次検出し、検出したエッジに対応する壁面要素を求める連続壁面追跡処理が行われ、取得した壁面要素はエッジリストＡに追加登録される（Ｓ１７０）。同様に、基点エッジの他方端ＰＢから伸びる向きにも連続壁面追跡処理が行われ、取得された壁面要素はエッジリストＢに追加登録される（Ｓ１７２）。或る基点エッジについて追跡手段３２による処理が終わると、壁面要素登録手段３４による処理が行われる（図１４のノードＧへ処理が進む）。
【００５５】
一方、処理Ｓ１６６において、基点エッジでの壁面要素が既に図形データベースに図形登録されている場合には（Ｓ１６６にて「Ｙｅｓ」の場合）、演算処理装置４は、当該壁面要素についての追跡処理や登録処理は行わずに、処理を図１５に示すノードＨに進める。この場合の処理については後述する。
【００５６】
図１０、図１１は処理Ｓ１７０，Ｓ１７２にて行われる連続壁面追跡処理の概略のフロー図である。追跡手段３２は既に検出されているエッジに連続するエッジを探索する空間として直方体の探索空間を設定する。探索空間は既検出エッジの探索空間に隣接する空間であり、探索空間の平面形状である長方形の短辺の中点は既検出エッジの端部に配置される。また、探索空間のＺ値の範囲（上面及び底面の高さ）は、既検出エッジにおける壁面要素の垂直方向の位置に応じて設定される。例えば、既検出の壁面要素の形状である台形の上側の辺と下側の辺が勾配を有し得ることを考慮して、探索空間の上面の高さを既検出の壁面要素の鉛直な２辺のうち当該探索空間が接続される側の辺の上端より高く設定し、一方、探索空間の底面の高さを当該辺の下端より低く設定することができる。探索空間の平面形状の長辺の長さは部分空間の幅Ｗや奥行きＤと同程度に設定することができ、例えば５０ｃｍとすることができる。
【００５７】
まず、追跡手段３２は既険出のエッジである線分を追跡しようとする側に延長し、当該延長線の向きに探索空間を配置する（Ｓ１８０）。すなわち、探索空間はその平面形状である長方形の長辺に沿った中心線を当該延長線に一致させるように配置される。そして、当該探索空間内に位置する点群のデータを記憶装置６からＲＡＭ等の作業領域に取り込み（Ｓ１８０）、処理Ｓ８６と同様の手法により当該探索空間にてエッジを探す（Ｓ１８２）。当該探索空間にてエッジが存在した場合（Ｓ１８４にて「Ｙｅｓ」の場合）、追跡手段３２はさらに、処理Ｓ１２２と同様にして探索空間の点群データから壁面要素となる台形を決定する処理を行う（Ｓ１８６）。壁面要素の形状を取得できた場合には（Ｓ１８８にて「Ｙｅｓ」の場合）、エッジの微調整処理が行われる（Ｓ１９０）。そして処理は処理Ｓ１８０に戻り、今得られたエッジを既検出エッジとして、連続壁面の追跡処理が継続される。
【００５８】
既検出エッジの延長線上の探索空間にてエッジ又は壁面要素を検出できない場合（処理Ｓ１８４にて「Ｎｏ」の場合、及びＳ１８８にて「Ｎｏ」の場合）は、図１１のノードＣＢに進み、既検出エッジの延長線からずれた方向における探索処理が行われる。当該探索処理では、探索空間をその中心軸を水平面内にて当該延長線の位置から時計回り方向と反時計回り方向とに変化させて設定する。例えば、延長線の向きからの中心軸の向きの変化範囲（±θ）とその分割数ｋを設定し、θ／ｋずつ水平面内での角度が異なる複数の探索空間を設定し、各探索空間にてエッジを探し、そして角度を変えて設定した複数の探索空間にて得られたエッジのうち最も点群が集まるものを選択する（Ｓ２００）。
【００５９】
一番点群が集まるエッジを特定できた場合（Ｓ２０２にて「Ｙｅｓ」の場合）、追跡手段３２はさらに、処理Ｓ１２２と同様にして探索空間の点群データから壁面要素となる台形を決定する処理を行う（Ｓ２０４）。壁面要素の形状を取得できた場合には（Ｓ２０６にて「Ｙｅｓ」の場合）、後述する微調整処理が行われる（Ｓ２０８）。そして処理は図１０のノードＣＡに戻り、今得られたエッジを既検出エッジとして、連続壁面の追跡処理が継続される。
【００６０】
角度を変えた探索空間にてエッジ又は壁面要素を検出できない場合（処理Ｓ２０２にて「Ｎｏ」の場合、及びＳ２０６にて「Ｎｏ」の場合）は、連続壁面追跡処理は終了し、当該処理をサブルーチンとして呼び出した処理Ｓ１７０又はＳ１７２に戻る。
【００６１】
図１２及び図１３はエッジの微調整処理Ｓ１９０，Ｓ２０８の概略のフロー図である。演算処理装置４はエッジを示す線分が得られると、当該線分を一定の長さの区間に区切り（Ｓ２２０）、各区間にてエッジが通る点（代表点）を探索し、エッジをＸ−Ｙ面内にてＰＡ，ＰＢを結ぶ線分に代えて、各区間にて求めた代表点をつなぐ折れ線とする。ここでは区間数をＮとする。演算処理装置４は、選択した区間Ｋから代表点ＰＫが得られると、当該代表点ＰＫの水平面内の座標（ＸＫ，ＹＫ）と、当該区間での壁面要素の標高値の最小値ＺＬＫ及び最大値ＺＨＫとを、代表点情報として求める。例えば、ＺＬＫ，ＺＨＫはエッジの両端ＰＡ，ＰＢでの値を補間して求めることができる。
【００６２】
演算処理装置４はまず、エッジの一方端ＰＡを代表点とし、ＰＡについての代表点情報をエッジ代表点リストに格納する（Ｓ２２２）。続いて、区間番号Ｋを１ずつ増加させて、区間を選択し（Ｓ２２４，Ｓ２２６）、各区間にて代表点を探索する（Ｓ２３０）。当該処理Ｓ２３０では、水平断面が選択した区間の近傍領域であり、垂直方向に壁面要素に応じた高さを有する空間を設定し、当該区間内の点群データを取り込んで、当該空間の水平断面内にて最も点群が密集する位置を求める。そして当該位置に密集する点の数が予め定めた個数以上であれば（Ｓ２３２にて「Ｙｅｓ」の場合）、当該位置を代表点としてエッジ代表点リストに追加する（Ｓ２３４）。一方、当該位置に密集する点の数が予め定めた個数未満であれば（Ｓ２３２にて「Ｎｏ」の場合）、当該区間からはエッジの代表点をエッジ代表点リストに追加せずに次の区間の処理に進む。全ての区間について処理が終わると（Ｓ２２８にて「Ｙｅｓ」の場合）、エッジの他方端ＰＢをエッジ代表点リストに追加し（Ｓ２３６）、図１３のノードＣＶ−Ｒに進む。
【００６３】
演算処理装置４はエッジ代表点リストに格納されている代表点の数ｍをカウントする（Ｓ２４０）。そして、隣接する代表点ＰＪとＰＪ＋１の対をＪを１から（ｍ−１）まで１ずつ増加させて選択し（Ｓ２４２〜Ｓ２４６）、ＰＪの代表点情報とＰＪ＋１の代表点情報とで表される壁面要素が既に図形データベースに図形登録されているか調べる（Ｓ２４８）。登録されていない場合には（Ｓ２５０にて「Ｎｏ」の場合）、当該壁面要素をエッジリストＡ又はＢに追加し（Ｓ２５２）、処理Ｓ２４４に戻る。一方、既に図形データベースに図形登録されていた場合（Ｓ２５０にて「Ｙｅｓ」の場合）、エッジの微調整処理Ｓ１９０，Ｓ２０８を終了する。
【００６４】
さて、図９の説明で述べたように、或る基点エッジについて追跡手段３２による処理が終わると、壁面要素登録手段３４による処理が行われる。図１４は壁面要素登録手段３４の概略の処理フロー図である。壁面要素登録手段３４は、追跡手段３２により生成されたエッジリストＡ，Ｂが空でなければ（Ｓ２６０，Ｓ２６４にて「Ｎｏ」の場合）、それらエッジリストに格納されている壁面要素を図形データベースに登録し（Ｓ２６２，Ｓ２６６）、図１５のノードＨへ処理を進める。
【００６５】
ここまで処理を行ってきた基点エッジは、処理Ｓ８４で指定される第Ｉ階のブロック空間から処理Ｓ８８で検出されたエッジである。演算処理装置４は当該基点エッジについて処理Ｓ１１６で指定された第Ｊ階層での処理を終えると、注目部分空間のうち当該階層に対応する高さ範囲にて、他のエッジを探索して壁面要素を決定する処理を行う。これにより例えば、同じ高さ範囲における多重エッジを検出して、それぞれに対応する壁面要素を決定することができる。図１５は第Ｊ階層にて最初のエッジ（主エッジと称する）についての処理を終えた後の処理フロー図である。演算処理装置４は第Ｊ階層にて主エッジの処理を終えると、当該階層に存在する他のエッジ（多重エッジと称する）を探索して壁面要素を決定する処理（多重エッジ処理）Ｓ２７０を行う。多重エッジ処理Ｓ２７０が終了すると、処理は図６のノードＥに戻り、次の階層における主エッジの処理が開始される。
【００６６】
図１６は多重エッジ処理の概略の処理フロー図である。多重エッジ処理では、主エッジの両側に別のエッジがないか探索する。図１７は多重エッジ処理を説明する模式図であり、部分空間の平面配置を示している。図１７（ａ）に示す例では、注目部分空間２８０には最も点群が集まるエッジ２８２と、エッジ２８２より点群の集まり度合いが低いエッジ２８４とが存在している。既に説明した水平面内探索手段２６、垂直位置決定手段２８、壁面形状決定手段３０、追跡手段３２及び壁面要素登録手段３４による処理で、主エッジとなるエッジ２８２が検出され、当該エッジ２８２について追跡や図形登録の処理が行われる。多重エッジ処理では、当該エッジ２８２を含まないようにその両側に多重エッジ探索空間２８６，２８８を設定する（図１７（ｂ））。多重エッジ探索空間は例えば、平面形状が部分空間と同程度の大きさ・形状の矩形であり、Ｚ値の範囲が第Ｊ階層と同程度である直方体の空間に設定される。例えば、主エッジ（図１７のエッジ２８２）が延びるいずれかの方向に向かって、当該エッジより左側の領域に多重エッジ探索空間を作成して当該空間内の点群を取り込み（Ｓ３００）、処理Ｓ８６と同様に当該多重エッジ探索空間でエッジの探索を行い、エッジが存在するかを判定する（Ｓ３０２）。エッジが存在する場合（Ｓ３０２で「Ｙｅｓ」の場合）は、多重エッジ探索空間内にて当該エッジを中心として図６の処理Ｓ１１０における垂直探索空間と同様の平面形状の空間を設定し、当該空間内の点群から処理Ｓ１２２と同様にして壁面要素の形状を決定する処理を行う（Ｓ３０４）。壁面要素の形状を取得できた場合には（Ｓ３０６にて「Ｙｅｓ」の場合）、図９で説明した追跡手段３２による連続壁面追跡処理Ｓ１６０〜Ｓ１７２、及び図１４で説明した壁面要素登録手段３４による登録処理Ｓ２６０〜Ｓ２６６と同様の処理Ｓ３０８が行われる。同様に主エッジより右側の領域に多重エッジ探索空間を作成して、上述した左側の場合の処理Ｓ３００〜Ｓ３０８と同様の処理Ｓ３１０〜Ｓ３１８が行われる。
【００６７】
上記実施形態では、コンピュータを壁面抽出システム２の各手段として動作させるプログラムは記憶装置６に格納され、コンピュータはこれを読み出して実行する構成としたが、他の構成では、当該プログラムはネットワーク等の通信媒体を介してコンピュータに提供することができ、この場合、壁面抽出システム２は通信装置を備え当該通信装置がネットワーク等からプログラムを取得し、演算処理装置４に提供したり、記憶装置６に記憶させる。また、当該プログラムはＣＤ−ＲＯＭ（Compact Disc Read Only Memory）等の記録媒体に格納して提供することも可能である。
【符号の説明】
【００６８】
２  壁面抽出システム、４  演算処理装置、６  記憶装置、８  入力装置、１０  出力装置、２０  部分空間設定手段、２２  部分空間選択手段、２４  ブロック空間設定手段、２６  水平面内探索手段、２８  垂直位置決定手段、３０  壁面形状決定手段、３２  追跡手段、３４  壁面要素登録手段。
【図１】
0005566353.tif 000002
【図２】
0005566353.tif 000003
【図３】
0005566353.tif 000004
【図４】
0005566353.tif 000005
【図５】
0005566353.tif 000006
【図６】
0005566353.tif 000007
【図７】
0005566353.tif 000008
【図８】
0005566353.tif 000009
【図９】
0005566353.tif 000010
【図１０】
0005566353.tif 000011
【図１１】
0005566353.tif 000012
【図１２】
0005566353.tif 000013
【図１３】
0005566353.tif 000014
【図１４】
0005566353.tif 000015
【図１５】
0005566353.tif 000016
【図１６】
0005566353.tif 000017
【図１７】
0005566353.tif 000018