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