JP4438418B2 - ３次元デ−タ処理方法及び装置 - Google Patents

Description

本発明は、３次元デ−タ処理方法及び装置に関し、より具体的には、レ−ザ走査等の方法でサンプリングされた３次元点デ−タから地形面以外のデ−タを削除する３次元デ−タ処理方法及び装置に関する。

地形の調査には、地形図の読図及び空中写真判読以外に、河川の流路長、流域面積及び山地の起伏量などを地形図上で定量的に計測する手法（地形計測）がある。ただし、地形図上で行う地形計測は、非常に時間がかかり、熟練した技能が必要になるだけでなく、ある程度の誤差を避けられない。

これに対し、広い範囲で地形の３次元形状を測定する手段として、ヘリコプタ−又は軽飛行機にレ−ザ測距装置を搭載して目標地域上を飛行し、地上にレ−ザビ−ムを照射することで、地表面及び地上物体の３次元標高座標を測定するシステム、所謂、ＬｉＤＡＲ（Ｌｉｇｈｔ Ｄｅｔｅｃｔｉｏｎ ａｎｄ Ｒａｎｇｉｎｇ）システムが知られている。この種のレ−ザ測量システムでは、レ−ザパルスにより対象物までの距離を計測し、飛行機の３次元位置、レ−ザ照射方向及び測定距離から、対象物の３次元座標を決定する。従って、対象物を空間的にサンプリングした３次元座標値を得ることができる。この場合、地上の建物及び街路樹等も一緒に計測される。図１４は、ＬｉＤＡＲシステムにより計測される、ある断面におけるサンプル例を示す。黒丸が、計測された３次元座標デ−タの計測点を示す。図１４から分かるように、ＬｉＤＡＲシステム等で得られる３次元点デ−タは、地表面以外に、建物の屋根部分及び側壁部分の点デ−タを含み、樹冠表面部分の点デ−タを含む。

このように、ＬｉＤＡＲシステム及びこれに類似する方法で空中から計測される３次元点デ−タから建物及び樹木等の点デ−タを除去することで、地表面形状を示すＤＴＭ（Ｄｉｇｉｔａｌ Ｔｅｒｒａｉｎ Ｍｏｄｅｌ）デ−タを得ることができる。ＤＴＭデ−タを用いることにより、容易かつ同一の精度で地形の３次元形状を計測できる。

ランダムな点群に対して自動的に地形面以外のデ−タを除去する方法として、一定（例えば１０ｍ×１０ｍ）の狭いエリアに区切り、各エリア内で最低標高のデ−タのみを抽出する方法が知られている。

しかし、各エリアで最低標高の点デ−タのみを抽出する方法では、例えば、尾根等の突起した部分が消えてしまう。従って、尾根等の突起部分がある場合、別途、尾根等の部分の位置デ−タを自動又は手動で抽出しておき、地形面以外のデ−タを除去する後の標高デ−タに追加する必要があった。

また、従来の方法では、樹木、小面積の建物、及び大面積の建物の除去精度が悪く、オペレ−タがマニュアルで、時には航空写真等を参照して、不要なデ−タを削除する必要があった。

即ち、従来の方法は、膨大な手間と費用がかかる。人の判断と人手の処理が介在することから、作成されるＤＴＭデ−タの品質が一定しないという問題点があった。

本発明は、このような不都合を解消し、３次元位置を計測された多数の点デ−タから、より効率的且つ精度良く表面以外のデ−タを削除する３次元デ−タ処理方法及び装置を提示することを目的とする。

本発明に係る３次元デ−タ処理方法は、３次元点デ−タをｘ−ｙ面内の第１の方向で複数のタイルに分割する第１のタイル分割ステップと、当該第１の方向で分割された各タイルについて、点デ−タを順方向にフィルタ処理することにより地表面を示す第１の点デ−タを抽出する第１のフィルタ処理ステップと、当該第１の方向で分割された各タイルについて、点デ−タを逆方向にフィルタ処理することにより地表面を示す第２の点デ−タを抽出する第２のフィルタ処理ステップと、当該第１の点デ−タと当該第２の点デ−タの少なくとも一方に含まれる点デ−タを抽出する第１の抽出ステップとを具備することを特徴とする。

複数のタイルに分割し、タイル単位で地表面の点デ−タを求めるので、演算を２次元化することが可能になり、処理負担が軽減される。また、順方向と逆方向の両方で、地表面点デ−タを抽出するフィルタ処理を行うことで、下り坂の部分で地表面データが消えてしまうことを防止できる。

本発明に係る方法は更に、当該３次元点デ−タをｘ−ｙ面内の第１の方向に直交する第２の方向で複数のタイルに分割する第２のタイル分割ステップと、当該第２の方向で分割された各タイルについて、点デ−タを順方向にフィルタ処理することにより地表面を示す第３の点デ−タを抽出する第３のフィルタ処理ステップと、当該第２の方向で分割された各タイルについて、点デ−タを逆方向にフィルタ処理することにより地表面を示す第４の点デ−タを抽出する第４のフィルタ処理ステップと、当該第１の抽出ステップに代わる、当該第１、第２、第３及び第４の点デ−タの少なくとも一つに含まれる点デ−タを抽出する第２の抽出ステップとを具備することを特徴とする。

これにより、２方向のタイルで地表面を探索することになり、山の頂上部分や尾根のように複雑な傾斜面でも、地表面を示す点デ−タを精度よく抽出できる。

好ましくは、当該第１及び当該第２のフィルタ処理ステップで使用されるフィルタ処理が同じアルゴリズムに基づく。また、好ましくは、当該第１、第２、第３及び第４のフィルタ処理ステップで使用されるフィルタ処理が同じアルゴリズムに基づく。これにより、例えば、順方向の探索で突起部分を見逃すとしても、逆方向の探索でこれを探知できることになり、地表面の点デ−タを誤認する可能性が低減する。

当該フィルタ処理が、互いに異なる点デ−タにその並び方向で基準点（ｉ）、検査点（ｊ）及び対象点（ｋ）を設定するステップと、当該基準点（ｉ）と当該対象点（ｋ）との距離を判定するステップと、当該基準点（ｉ）と当該対象点（ｋ）との距離が所定値より大きく、且つ、基準点（ｉ）の高さが検査点（ｊ）の高さ以下の場合に、基準点（ｉ）の点デ−タを当該第１の点デ−タとして採用すると共に、検査点（ｊ）及び対象点（ｋ）をそれぞれ次の点デ−タに更新するステップと、当該基準点（ｉ）と当該対象点（ｋ）の距離が所定値以下の場合に、基準点（ｉ）、検査点（ｊ）及び対象点（ｋ）から当該検査点（ｊ）の要否を判定する判定ステップと、当該判定ステップにより当該検査点が不要と判定された場合に、当該検査点の次の点を新たな検査点（ｊ）とし、当該検査点の次の次の点を新たな対象点（ｋ）とし、当該判定ステップにより当該検査点が必要と判定された場合に、当該検査点の次の次の点を新たな対象点とするステップとを具備する。

地表面を示す点デ−タと、地表面である可能性の低いデ−タとを３点の比較で逐次的に切り分けるので、地表面を示す点デ−タを高い確度で決定できる。

好ましくは、当該判定ステップが、当該基準点（ｉ）と当該検査点（ｊ）を結ぶ線の傾きと、当該基準点（ｉ）と当該対象点（ｋ）を結ぶ線の傾きを算出し、両傾きの比較により、当該検査点（ｊ）の要否を判定することを特徴とする。これにより、比較的簡単な演算で、地表面である可能性の低いデ−タを除去できる。

好ましくは、当該判定ステップが、当該基準点（ｉ）と当該対象点（ｋ）に接する所定半径の下側の円の中心から当該検査点（ｊ）までの距離を算定し、当該距離が所定値より大きい場合に当該検査点（ｊ）を不要と判定し、当該距離が当該所定値以下の場合に当該検査点（ｊ）を必要と判定することを特徴とする。これにより、高い確度で地表面以外の点デ−タを予め除外できる。

好ましくは、当該３次元点デ−タが、処理対象地域に所定のマ−ジンを含めた地域の点デ−タからなり、当該３次元デ−タ処理方法が更に、当該第１の抽出ステップで抽出された点デ−タから当該処理対象地域内の点デ−タをクリップするステップを具備することを特徴とする。好ましくは、当該３次元点デ−タが、処理対象地域に所定のマ−ジンを含めた地域の点デ−タからなり、当該３次元デ−タ処理方法が更に、当該第２の抽出ステップで抽出された点デ−タから当該処理対象地域内の点デ−タをクリップするステップを具備することを特徴とする。これにより、処理対象地域内で確実に地表面を示す点デ−タを検出できる。

本発明に係る３次元デ−タ処理装置は、３次元点デ−タをｘ−ｙ面内の第１の方向で複数のタイルに分割する第１のタイル分割手段と、当該第１の方向で分割された各タイルについて、点デ−タを順方向にフィルタ処理し、地表面を示す第１の点デ−タを出力する第１のフィルタ処理手段と、当該第１の方向で分割された各タイルについて、点デ−タを逆方向にフィルタ処理し、地表面を示す第２の点デ−タを出力する第２のフィルタ処理手段と、当該第１の点デ−タと当該第２の点デ−タの少なくとも一方に含まれる点デ−タを抽出する抽出器とを具備することを特徴とする。

複数のタイルに分割し、タイル単位で地表面の点デ−タを求めるので、演算を２次元化することが可能になり、処理負担が軽減される。また、順方向と逆方向の両方で、地表面点デ−タを抽出するフィルタ処理を行うことで、下り坂の部分で地表面データが消えてしまうことを防止できる。

本発明に係る３次元デ−タ処理装置は更に、当該３次元点デ−タをｘ−ｙ面内の第１の方向に直交する第２の方向で複数のタイルに分割する第２のタイル分割手段と、当該第２の方向で分割された各タイルについて、点デ−タを順方向にフィルタ処理し、地表面を示す第３の点デ−タを出力する第３のフィルタ処理手段と、当該第２の方向で分割された各タイルについて、点デ−タを逆方向にフィルタ処理し、地表面を示す第４の点デ−タを出力する第４のフィルタ処理手段とを具備し、当該抽出器が、当該第１、第２、第３及び第４の点デ−タの少なくとも一つに含まれる点デ−タを抽出することを特徴とする。

これにより、２方向のタイルで地表面を探索することになり、山の頂上部分や尾根のように複雑な傾斜面でも、地表面を示す点デ−タを精度よく抽出できる。

好ましくは、当該第１及び当該第２のフィルタ処理手段のフィルタ処理が同じアルゴリズムに基づくことを特徴とする。好ましくは、当該第１、第２、第３及び第４のフィルタ処理手段のフィルタ処理が同じアルゴリズムに基づくことを特徴とする。これにより、例えば、順方向の探索で突起部分を見逃すとしても、逆方向の探索でこれを探知できることになり、地表面の点デ−タを誤認する可能性が低減する。

好ましくは、当該フィルタ処理が、互いに異なる点デ−タにその並び方向で基準点（ｉ）、検査点（ｊ）及び対象点（ｋ）を設定する処理と、当該基準点（ｉ）と当該対象点（ｋ）との距離を判定する処理と、当該基準点（ｉ）と当該対象点（ｋ）との距離が所定値より大きく、且つ、基準点（ｉ）の高さが検査点（ｊ）の高さ以下の場合に、基準点（ｉ）の点デ−タを当該第１の点デ−タとして採用すると共に、検査点（ｊ）及び対象点（ｋ）をそれぞれ次の点デ−タに更新する処理と、当該基準点（ｉ）と当該対象点（ｋ）の距離が所定値以下の場合に、基準点（ｉ）、検査点（ｊ）及び対象点（ｋ）から当該検査点（ｊ）の要否を判定する判定処理と、当該判定処理により当該検査点が不要と判定された場合に、当該検査点の次の点を新たな検査点（ｊ）とし、当該検査点の次の次の点を新たな対象点（ｋ）とし、当該判定処理により当該検査点が必要と判定された場合に、当該検査点の次の次の点を新たな対象点とする処理とを具備する。

地表面を示す点デ−タと、地表面である可能性の低いデ−タとを３点の比較で逐次的に切り分けるので、地表面を示す点デ−タを高い確度で決定できる。

好ましくは、当該判定処理が、当該基準点（ｉ）と当該検査点（ｊ）を結ぶ線の傾きと、当該基準点（ｉ）と当該対象点（ｋ）を結ぶ線の傾きを算出し、両傾きの比較により、当該検査点（ｊ）の要否を判定することを特徴とする。これにより、比較的簡単な演算で、地表面である可能性の低いデ−タを除去できる。

好ましくは、当該判定処理が、当該基準点（ｉ）と当該対象点（ｊ）に接する所定半径の下側の円の中心から当該検査点（ｊ）までの距離を算定し、当該距離が所定値より大きい場合に当該検査点（ｊ）を不要と判定し、当該距離が当該所定値以下の場合に当該検査点（ｊ）を必要と判定することを特徴とする。これにより、高い確度で地表面以外の点デ−タを予め除外できる。

好ましくは、当該３次元点デ−タが、処理対象地域に所定のマ−ジンを含めた地域の点デ−タからなり、当該３次元デ−タ処理装置が更に、当該第１の抽出ステップで抽出された点デ−タから当該処理対象地域内の点デ−タをクリップする装置（３０）を具備することを特徴とする。好ましくは、当該３次元点デ−タが、処理対象地域に所定のマ−ジンを含めた地域の点デ−タからなり、当該３次元デ−タ処理装置が更に、当該第抽出器（２８）で抽出された点デ−タから当該処理対象地域内の点デ−タをクリップする装置（３０）を具備することを特徴とする。これにより、処理対象地域内で確実に地表面を示す点デ−タを検出できる。

本発明によれば、３次元点デ−タから地表面を示す点デ−タを精度よく抽出することができる。

以下、図面を参照して、本発明の実施例を詳細に説明する。

図１は、本発明の一実施例の概略構成ブロック図を示す。なお、本実施例では、図２に示すように、ＬｉＤＡＲシステム等で離散的に計測された地域を、所定サイズ（例えば、１００ｍ×１００ｍ）の矩形又は長方形の領域Ｒ（ｎ，ｍ）に分割した上で、その個々の領域Ｒ（ｎ，ｍ）を単位に地表面以外のデ−タを除去する。

メモリ１０（又は入力ファイル）には、ＬｉＤＡＲシステム等で離散的に計測された地上面の３次元点デ−タ｛Ｐｉ（ｘ，ｙ，ｚ）｝が収容されている。本実施例では、先ず、処理対象抽出装置１２は、図３に示すように、処理対象領域Ｒ（ｎ，ｍ）よりも一定距離ＤだけＸ方向及びＹ方向に広い範囲内の３次元位置デ−タをメモリ１０から読み出し、メモリ１４に一時的に格納する。Ｄはいわばマ−ジンであり、後述するＲｒｅｆ以上であるのが好ましい。

本実施例では、処理対象抽出装置１２がメモリ１０から読み出した領域を更に、Ｘ方向及びＹ方向の短冊状のタイルに分割し、各タイル内で地表面以外のデ−タを削除する。

即ち、ｘ方向タイル分割装置１６は、図４に示すように、メモリ１４に一時的に格納される３次元点デ−タ｛Ｐｉ（ｘ，ｙ，ｚ）｝（即ち、処理対象抽出装置１２がメモリ１０から読み出してメモリ１４に格納した３次元点デ−タ｛Ｐｉ（ｘ，ｙ，ｚ）｝）の内の、左右のマ−ジンＤを除いた部分を、ｘ方向に所定幅Ｗｘの、ｙ方向に延びる複数のタイルに分割する。

ｘ方向タイル分割装置１６により分割された各タイルについて、順方向フィルタ１８Ｆ及び逆方向フィルタ１８Ｂにより地表面以外のデ−タを除去する。即ち、順方向フィルタ１８Ｆは、注目するタイルに含まれる３次元点デ−タ｛Ｐｉ（ｘ，ｙ，ｚ）｝を順方向（ｙ方向）にサ−チして、後述するアルゴリズムにより地表面以外の点デ−タを除去し、他方、逆方向フィルタ１８Ｂは、逆方向（−ｙ方向）にサ−チして、後述するアルゴリズムにより地表面以外の点デ−タを除去する。

図５は、ｘ方向タイル分割装置１６，順方向フィルタ１８Ｆ及び逆方向フィルタ１８Ｂにおける処理のフロ−チャ−トを示す。

先ず、ｘ方向タイル分割装置１６は、処理対象領域Ｒ（ｍ，ｎ）よりｘ，ｙ方向にＤだけ広い範囲に含まれる全点デ−タ（メモリ１４に格納される点デ−タ）｛Ｐｉ（ｘ，ｙ，ｚ）｝をｘの昇順でソ−トする（Ｓ１）。分割装置１６は、ソ−ト結果を、図４に示すように、ｘ方向に幅Ｗｘの複数のタイルに短冊状に分割する（Ｓ２）。

分割されたタイルの内の最初のタイルを指定する（Ｓ３）。指定されたタイル内の全点デ−タ｛Ｐｉ（ｘ，ｙ，ｚ）｝をｙの昇順でソ−トする（Ｓ４）。順方向フィルタ１８Ｆは、指定タイル内の全点デ−タ｛Ｐｉ（ｘ，ｙ，ｚ）｝をｙの昇順で逐次的にサ−チし、ｙ−ｚ面内での距離を勘案して、地表面以外の点デ−タを削除する又は地表面を示す点デ−タを抽出する（Ｓ５）。順方向フィルタ１８Ｆは、残った点デ−タをメモリ２０Ｆに格納する（Ｓ６）。また、逆方向フィルタ１８Ｂは、指定タイル内の全点デ−タ｛Ｐｉ（ｘ，ｙ，ｚ）｝をｙの降順で逐次的にサ−チし、ｙ−ｚ面内での距離を勘案して、地表面以外の点デ−タを削除する又は地表面を示す点デ−タを抽出する（Ｓ７）。逆方向フィルタ１８Ｂは、残った点デ−タをメモリ２０Ｂに格納する（Ｓ６）。

未処理のタイルがあれば（Ｓ９）、次のタイルを指定して（Ｓ１０）、Ｓ４乃至Ｓ８を繰り返す。全タイルについてフィルタ処理を終了したら、終了する。即ち、ｘ方向タイル分割装置１６で分割された全タイルについて、ステップＳ４乃至Ｓ８の処理を実行する。

順方向フィルタ１８Ｆ及び逆方向フィルタ１８Ｂのフィルタ処理のアルゴリズムは、後で詳細に説明する。但し、本実施例のフィルタ処理アルゴリズムは、上り坂の部分で地表面を効率良く探索するように設計されているので、下り坂の部分では地表面データを除去してしまう可能性がある。このように順方向のフィルタ処理と逆方向のフィルタ処理を併用し、その結果を合算することで、下り坂の地表面を誤って除去してしまうことを防止できる。この点で、順方向のフィルタ処理と逆方向のフィルタ処理は同じアルゴリズムに基づくのが好ましい。

ｙ方向タイル分割装置２２は、図６に示すように、メモリ１４に一時的に格納される３次元点デ−タ｛Ｐｉ（ｘ，ｙ，ｚ）｝の内の、ｙ方向の両側の距離Ｄのマ−ジン部分を除いた部分を、ｙ方向に所定幅Ｗｙの、ｘ方向に延びる複数のタイルに分割する。

ｙ方向タイル分割装置２２により分割された各タイルについて、順方向フィルタ２４Ｆ及び逆方向フィルタ２４Ｂにより地表面以外のデ−タを除去する。即ち、順方向フィルタ２４Ｆは、注目するタイルに含まれる３次元点デ−タ｛Ｐｉ（ｘ，ｙ，ｚ）｝を順方向（ｘ方向）にサ−チして、後述するアルゴリズムにより地表面以外の点デ−タを除去し、他方、逆方向フィルタ２４Ｂは、逆方向（−ｘ方向）にサ−チして、後述するアルゴリズムにより地表面以外の点デ−タを除去する。

図７は、ｘ方向タイル分割装置２２、順方向フィルタ２４Ｆ及び逆方向フィルタ２４Ｂにおける処理のフロ−チャ−トを示す。

ｙ方向タイル分割装置２２は、処理対象領域Ｒ（ｍ，ｎ）よりｘ，ｙ方向にＤだけ広い範囲に含まれる全点デ−タ｛Ｐｉ（ｘ，ｙ，ｚ）｝をｙの昇順でソ−トする（Ｓ２１）。分割装置２２は、ソ−ト結果を、図６に示すように、ｙ方向に幅Ｗｙの複数のタイルに短冊状に分割する（Ｓ２２）。

分割されたタイルの内の最初のタイルを指定する（Ｓ２３）。指定されたタイル内の全点デ−タ｛Ｐｉ（ｘ，ｙ，ｚ）｝をｘの昇順でソ−トする（Ｓ２４）。順方向フィルタ２４Ｆは、指定タイル内の全点デ−タ｛Ｐｉ（ｘ，ｙ，ｚ）｝をｘの昇順で逐次的にサ−チし、ｘ−ｚ面内での距離を勘案して、地表面以外の点デ−タを削除する（Ｓ２５）。順方向フィルタ２４Ｆは、残った点デ−タをメモリ２６Ｆに格納する（Ｓ２６）。また、逆方向フィルタ２４Ｂは、指定タイル内の全点デ−タ｛Ｐｉ（ｘ，ｙ，ｚ）｝をｘの降順で逐次的にサ−チし、ｘ−ｚ面内での距離を勘案して、地表面以外の点デ−タを削除する（Ｓ２７）。逆方向フィルタ２４Ｂは、残った点デ−タをメモリ２６Ｂに格納する（Ｓ２８）。

未処理のタイルがあれば（Ｓ２９）、次のタイルを指定して（Ｓ３０）、Ｓ２４乃至Ｓ２８を繰り返す。全タイルについてフィルタ処理を終了したら、終了する。即ち、ｙ方向タイル分割装置２２で分割された全タイルについて、ステップＳ２４乃至Ｓ２８の処理を実行する。

順方向フィルタ２４Ｆ及び逆方向フィルタ２４Ｂのフィルタ処理のアルゴリズムは、それぞれ、順方向フィルタ１８Ｆ及び逆方向フィルタ１８Ｂのフィルタ処理のアルゴリズムと同じでよい。各フィルタ処理を同じにすることで、同じフィルタ処理ソフトウエア又は機能を共用できる。

以上の処理の結果、メモリ２０Ｆ，２０Ｂ，２６Ｆ，２６Ｂには、フィルタ処理方向の異なる４種類の処理結果が格納される。各フィルタ処理でも同じ点デ−タが残ることがありうる。重複削除装置２８が、同じｘ，ｙ，ｚ座標の点デ−タを削除する。クリップ装置３０は、重複削除装置２８で重複を削除された点デ−タ群から、処理対象領域Ｒ（ｎ，ｍ）内の点デ−タのみを抽出して、処理結果メモリ３２に格納する。クリップ装置３０はまた、制御装置３４に１つの処理対象領域Ｒ（ｎ，ｍ）の処理が終了したことを通知する。制御装置３４は、これに応じて、次の処理対象領域、例えば、領域Ｒ（ｎ，ｍ＋１）とこれよりｘ，ｙ方向に距離Ｄだけ広い範囲に含まれる点デ−タＰｉ（ｘ，ｙ，ｚ）をメモリ１０から読み出して、メモリ１４に格納するように、処理対象抽出装置１２に指令する。

このようにして、計測範囲の全処理対象領域Ｒ（ｎ，ｍ）について、順次、地表面以外の点デ−タが削除され得る。並列実行可能な処理は、複数のＣＰＵ又はコンピュータを並列動作させることで、短時間に結果を得ることができる。

次に、順方向フィルタ１８Ｆ，２４F及び逆方向フィルタ１８Ｂ，２４Ｂのフィルタ処理例を具体的に説明する。本実施例では、順方向フィルタ１８Ｆ，２４F及び逆方向フィルタ１８Ｂ，２４Ｂの各フィルタ処理は、同じアルゴリズムに基づき、異なるのは、サ−チ方向と距離計算に使用する座標値（ｘ又はｙ）である。

図８は、順方向フィルタ１８Ｆのフィルタ処理のフロ−チャ−トを示す。図９は、タイル分割装置１６で分割されたｙ方向に延びるタイルに含まれる点デ−タのｙ−ｚ面で見た配置例を示す。１タイル中にＮ個の点デ−タ、即ちＮ個の座標値があり、これらの点デ−タをＰ（ｉ）と表記する。Ｐ（ｉ）は、構造体の要素としてｘ座標値、ｙ座標値及びｚ座標値を含む。点デ−タＰ（ｉ）は、図８に示すフロ−の前処理として、ｙ座標値の小さい順にソ−トされているものとする。フィルタ出力を、Ｐ（ｉ）と同様の構造体からなる配列Ｑ（ｎ）とする。

本実施例では、基準点、検査点及び対象点の３つの点を設定し、注目する基準点が地表面を代表するか否かを、基準点とこれに先行する検査点と対象点との位置関係により判定する。図８に示すフロ−では、変数ｉが基準点を示し、変数ｊが検査点を示し、変数ｋが対象点を示す。常にｉ＜ｊ＜ｋである。

先ず、入力点デ−タＰ（ｉ）の変数ｉと、出力点デ−タＱ（ｎ）の変数ｎを０で初期化する（Ｓ３１）。変数ｊにｉ＋１を設定し、変数ｋにｊ＋１を設定する（Ｓ３２）。即ち、基準点の次の点を検査点に設定し、検査点の次の点を対象点に設定する。

ｋがＮ以上（Ｓ３３）、又は、ｉ＋２がＮ以上の場合（Ｓ３４）、処理を終了する。これらの場合、Ｎ個の点デ−タＰ（ｉ）内で対象点を設定できなくなくなり、以下に説明する方法では、基準点が地表面を示すか否かを判定できなくなるからである。

ｋ＋１がＮより大きいかどうかを調べる（Ｓ３５）。対象点（ｋ）が最終の点デ−タを越える場合、距離基準Ｒｒｅｆに基づく判定が不確かなものになる可能性がある。即ち、ｋ＋１がＮを越える場合、基準点、検査点及び対象点の３点の比較では地表面か否かを判定できなくなる。そこで、ｋ＋１がＮを越える場合には、検査点の削除判定（Ｓ４６）をせずに、地表面かどうかを最終判定する処理（Ｓ３７）に移行する。

ｋ＋１がＮ以下の場合には（Ｓ３５）、対象点のｙ座標値Ｐ（ｋ）．ｙと基準点のｙ座標値Ｐ（ｉ）．ｙの差が基準値Ｒｒｅｆより大きいかどうか、即ち、Ｐ（ｋ）．ｙ−Ｐ（ｉ）．ｙ＞Ｒｒｅｆかどうかを調べ（Ｓ３６）、Ｐ（ｋ）．ｙ−Ｐ（ｉ）．ｙ＞Ｒｒｅｆの場合には、対象点Ｐ（ｋ）が基準点Ｐ（ｉ）から十分に離れているので、基準点Ｐ（ｉ）又は検査点Ｐ（ｊ）が地表面かどうかを最終判定する処理（Ｓ３７）に移行する。Ｐ（ｋ）．ｙ−Ｐ（ｉ）．ｙがＲｒｅｆ以下の場合には（Ｓ３６）、ステップＳ４０以降で、地表面以外を示す検査点を除去する処理を実行する。

ステップＳ３７では、基準点のｚ座標値Ｐ（ｉ）．ｚが検査点ｚ座標値Ｐ（ｊ）．ｚ以下かどうかを調べる（Ｓ３６）。この際、当然であるが、一定の誤差を考慮して、基準点のｚ座標値Ｐ（ｉ）．ｚと検査点ｚ座標値Ｐ（ｊ）．ｚを比較する。

基準点のｚ座標値Ｐ（ｉ）．ｚが検査点ｚ座標値Ｐ（ｊ）．ｚ以下の場合（Ｓ３７）、その基準点の点デ−タＰ（ｉ）を出力点Ｑ（ｎ）に代入し、変数ｎをインクリメントし（Ｓ３８）、変数ｉに変数ｊをセットする（Ｓ３９）。即ち、基準点の点デ−タＰ（ｉ）を、地表面を代表する点デ−タとして採用し、検査点を次の基準点とする。

ステップＳ３７の条件が満たされない場合、変数ｉに変数ｊをセットする（Ｓ３９）。即ち、注目する基準点を破棄して、検査点を次の基準点とする。ステップＳ３９の後、Ｓ３２に戻り、Ｓ３２以降を繰り返す。

対象点のｙ座標値Ｐ（ｋ）．ｙと基準点のｙ座標値Ｐ（ｉ）．ｙの差が、所定基準値Ｒｒｅｆ以下の場合（Ｓ３６）、基準点のｚ座標値Ｐ（ｉ）．ｚと検査点のｚ座標値Ｐ（ｊ）．ｚとの距離の絶対値が誤差ε以下かどうかを調べる（Ｓ４０）。基準点のｚ座標値と検査点のｚ座標値が誤差ε以下ということは、基準点と検査点が誤差ε以内で実質的に同じ高さになっていることを意味する。この場合、基準点を地表面を代表する点と認定しても支障ない。そこで、基準点のｚ座標値Ｐ（ｉ）．ｚと検査点のｚ座標値Ｐ（ｊ）．ｚとの距離が誤差ε以下の場合（Ｓ４０）、基準点の点デ−タＰ（ｉ）を出力点Ｑ（ｎ）に代入し、変数ｎをインクリメントし（Ｓ３８）、変数ｉに変数ｊをセットする（Ｓ３９）。先に説明したように、ステップＳ３９の後、Ｓ３２に戻り、Ｓ３２以降を繰り返す。

基準点のｚ座標値Ｐ（ｉ）．ｚと検査点のｚ座標値Ｐ（ｊ）．ｚとの距離が誤差εより大きい場合（Ｓ４０）、所定の誤差の下で、基準点のｙ座標値Ｐ（ｉ）．ｙと検査点のｙ座標値Ｐ（ｊ）．ｙが実質的に等しいかどうかを調べる（Ｓ４１）。両者が実質的に等しい場合（Ｓ４１）、基準点のｚ座標値Ｐ（ｉ）．ｚと検査点のｚ座標値Ｐ（ｊ）．ｚのどちらが小さいかを調べる（Ｓ４２）。基準点（ｉ）の高さ（ｚ）が検査点（ｊ）の高さ（ｚ）より高い場合（Ｓ４２）、検査点を新たな基準点とし（Ｓ４３）、対象点を新たな検査点とし、対象点の次の点を新たな対象点とする（Ｓ４４）。基準点（ｉ）の高さが検査点（ｊ）の高さ以下の場合（Ｓ４２）、対象点を新たな検査点とし、対象点の次の点を新たな対象点とする（Ｓ４４）。

ステップＳ４１，Ｓ４２では、基準点（ｉ）と検査点（ｊ）のＹ座標値が実質的に同じ場合（Ｓ４１）、基準点（ｉ）が高ければ、その基準点（ｉ）を捨てて、検査点（ｊ）と対象点（ｋ）を更新し（Ｓ４３）、検査点（ｊ）が高ければ、基準点（ｉ）を維持して、検査点（ｊ）と対象点（ｋ）を更新する（Ｓ４４）。これは、建物の壁面及び樹木などがある場所で、ｚ座標値の小さい方の点を地表面を代表する点として採用し、それ以外を削除することを意味する。

基準点のｙ座標値Ｐ（ｉ）．ｙと検査点のｙ座標値Ｐ（ｊ）．ｙが実質的に等しくない場合（Ｓ４１）、検査点の除去を判断する処理を実行する（Ｓ４５）。この検査点削除判定処理（Ｓ４５）は、樹冠表面及び建物の屋上等の、地表面から離れていることが確実な点を検査点から削除する処理である。

このフィルタ処理には、２種類の方法が考えられる。第１の方法は、基準点と検査点を結ぶ線の傾きと、基準点と対象点を結ぶ線の傾きを比較する方法であり、第２の方法は、基準点と対象点を円周上に持つ所定半径の２つの円の内、中心が低い位置にある円を設定し、その円内に検査点が実質的に入るかどうかを調べる方法である。フィルタ処理の具体例は、後述する。

検査点削除判定処理（Ｓ４５）の結果に従い、検査点を削除すべき場合には（Ｓ４６）、対象点Ｐ（ｋ）を新たな検査点Ｐ（ｊ）に設定し（Ｓ４７）、現在の対象点Ｐ（ｋ）の次の点を新たな対象点とする（Ｓ４８）。検査点を削除しない場合には（Ｓ４６）、現在の対象点Ｐ（ｋ）の次の点を新たな対象点とする（Ｓ４８）。ステップＳ４８の後、ステップＳ３５以降を繰り返す。

図１０は、第１の方法による検査点削除判定処理（Ｓ４５）のフロ−チャ−トを示す。基準点Ｐ（ｉ）と検査点Ｐ（ｊ）を結ぶ線の水平線からの傾き（傾き１）と、基準点Ｐ（ｉ）と対象点Ｐ（ｋ）を結ぶ線の水平線からの傾き（傾き２）を計算する（Ｓ５１）。傾き１が傾き２より大きい場合（Ｓ５２）、検査点は地表面ではないと判断できるので、検査点削除フラグに’１’をセットし（Ｓ５３）、そうでなければ、検査点削除フラグに’０’をセットする（Ｓ５４）。ここで計算される傾きは、例えば、水平方向から時計方向に対して負値であり、水平方向から反時計方向では正値である。

図１１は、第２の方法によるフィルタ処理（Ｓ４４）のフロ−チャ−トを示す。ｙ−ｚ面内で基準点Ｐ（ｉ）と対象点Ｐ（ｋ）を円周上に持つ半径Ｒｒｅｆの２つの円を設定し、その内、ｚ値が小さい方の円を採用する（Ｓ６１）。その円の中心と検査点Ｐ（ｊ）との距離Ｄｉｓｔを算出する（Ｓ６２）。誤差εを考慮して、検査点Ｐ（ｊ）が円内に入らない場合、即ちＲｒｅｆ＋ε＜Ｄｉｓｔの場合（Ｓ６３）、検査点削除フラグに’１’をセットし（Ｓ６４）、そうでなければ、検査点削除フラグに’０’をセットする（Ｓ６５）。

図１０に示す方法は、簡単な演算で済むので、処理負担が軽い。他方、図１１に示す方法は、図１０に示す方法に比べ、演算が複雑になるものの、測定対象の地表面で存在しうる地表面の曲率半径に応じて図１１でのＲｒｅｆを決定することで、図１０に示す方法に比べて、より高い確度で地表面以外の点を検出できる。

図１２は、図９に示す点デ−タの例に対して、図８及び図１０に示すフロ−による地表面デ−タの採用と検査点の削除の遷移の模式図である。図１２で、削除（ｎ）は、以下のｎ回目の処理で削除される点デ−タであることを示し、採用（ｎ）は、ｎ回目の処理で地表面デ−タとして採用された点デ−タであることを示す。右向きの矢印は、基準点からの距離Ｒｒｅｆを示す。

図８の１回目の処理では、点Ｐ（１）が基準点、点Ｐ（２）が検査点、点Ｐ（３）が対象点である。ｙ方向で対象点Ｐ（３）が基準点Ｐ（１）から距離Ｒｒｅｆ以内にあり（Ｓ３６）、基準点Ｐ（１）と検査点Ｐ（２）の高さが異なる（Ｓ４０）。基準点Ｐ（１）と検査点Ｐ（２）のｙ座標値も異なるので（Ｓ４１）、検査点削除判定処理（Ｓ４５）を実行する。検査点Ｐ（２）に対する傾き１が対象点Ｐ（３）に対する傾き２より大きいので（Ｓ５２）、検査点Ｐ（２）を削除する（Ｓ５３）。この結果、Ｐ（３）を検査点とし（Ｓ４７）、Ｐ（４）を対象点とする（Ｓ４８）。即ち、点Ｐ（２）が削除される。

２回目では、対象点Ｐ（４）が基準点Ｐ（１）からｙ方向でＲｒｅｆ以上に離れている（Ｓ３６）。基準点Ｐ（１）と検査点Ｐ（３）の高さを比較すると（Ｓ３７）、基準点Ｐ（１）が低いので、点Ｐ（１）を地表面デ−タと判定し（Ｓ３８）、検査点であった点Ｐ（３）を基準点とし、その次の点Ｐ（４）を検査点、次の次の点Ｐ（５）を対象点とする（Ｓ３２）。

３回目の処理では、点Ｐ（３）が基準点、点Ｐ（４）が検査点、点Ｐ（５）が対象点である。ｙ方向で対象点Ｐ（５）が基準点Ｐ（３）から距離Ｒｒｅｆ以内にあり（Ｓ３６）、基準点Ｐ（３）と検査点Ｐ（４）の高さが異なる（Ｓ４０）。基準点Ｐ（３）と検査点Ｐ（４）のｙ座標値も異なるので（Ｓ４１）、検査点削除判定処理（Ｓ４５）を実行する。検査点Ｐ（４）に対する傾き１が対象点Ｐ（５）に対する傾き２より大きいので（Ｓ５２）、検査点Ｐ（４）を削除する（Ｓ５３）。この結果、対象点Ｐ（５）を新たな検査点とし（Ｓ４７）、対象点Ｐ（５）の次の点Ｐ（６）を新たな対象点とする（Ｓ４８）。即ち、点Ｐ（４）が削除される。

４回目の処理では、点Ｐ（３）が基準点、点Ｐ（５）が検査点、点Ｐ（６）が対象点である。ｙ方向で対象点Ｐ（６）が基準点Ｐ（３）からＲｒｅｆ以上に離れている（Ｓ３６）。基準点Ｐ（３）と検査点Ｐ（５）の高さを比較すると（Ｓ３７）、基準点Ｐ（３）が低いので、点Ｐ（３）を地表面デ−タと判定し（Ｓ３８）、検査点であった点Ｐ（５）を新たな基準点とし、その次の点Ｐ（６）を新たな検査点、次の次の点Ｐ（７）を新たな対象点とする（Ｓ３２）。

５回目の処理では、点Ｐ（５）が基準点、点Ｐ（６）が検査点、点Ｐ（７）が対象点である。ｙ方向で対象点Ｐ（７）が基準点Ｐ（５）から距離Ｒｒｅｆ以内にあり（Ｓ３６）、基準点Ｐ（５）と検査点Ｐ（６）の高さが異なる（Ｓ４０）。基準点Ｐ（５）と検査点Ｐ（６）のｙ座標値も異なるので（Ｓ４１）、検査点削除判定処理（Ｓ４５）を実行する。検査点Ｐ（６）に対する傾き１が対象点Ｐ（７）に対する傾き２より小さい（負方向で大きい）ので（Ｓ５２）、検査点Ｐ（４）を削除せずに（Ｓ５３）、対象点Ｐ（７）の次の点Ｐ（８）を新たな対象点とする（Ｓ４８）。即ち、対象点のみを移動する。

６回目の処理では、点Ｐ（５）が基準点、点Ｐ（６）が検査点、点Ｐ（８）が対象点である。ｙ方向で対象点Ｐ（８）が基準点Ｐ（５）からＲｒｅｆ以上に離れている（Ｓ３６）。基準点Ｐ（５）と検査点Ｐ（６）の高さを比較すると（Ｓ３７）、基準点Ｐ（５）より検査点Ｐ（６）が低いので（Ｓ３７）、検査点Ｐ（６）を新たな基準点とし（Ｓ３９）、その次の点Ｐ（７）を新たな検査点、次の次の点Ｐ（８）を対象点とする（Ｓ３２）。即ち、点Ｐ（５）を削除する。

７回目の処理では、点Ｐ（６）が基準点、点Ｐ（７）が検査点、点Ｐ（８）が対象点である。ｙ方向で対象点Ｐ（８）が基準点Ｐ（６）から距離Ｒｒｅｆ以内にあり（Ｓ３６）、基準点Ｐ（６）と検査点Ｐ（７）の高さが異なる（Ｓ４０）。基準点Ｐ（６）と検査点Ｐ（７）のｙ座標値も異なるので（Ｓ４１）、検査点削除判定処理（Ｓ４５）を実行する。検査点Ｐ（７）に対する傾き１が対象点Ｐ（８）に対する傾き２より小さいので（Ｓ５２）、検査点Ｐ（７）を削除せずに（Ｓ５３）、対象点Ｐ（８）の次の点Ｐ（９）を新たな対象点とする（Ｓ４８）。即ち、対象点のみを移動する。

８回目の処理では、点Ｐ（６）が基準点、点Ｐ（７）が検査点、点Ｐ（９）が対象点である。ｙ方向で対象点Ｐ（９）が基準点Ｐ（６）からＲｒｅｆ以上に離れている（Ｓ３６）。基準点Ｐ（６）と検査点Ｐ（７）の高さを比較すると（Ｓ３７）、基準点Ｐ（６）が検査点Ｐ（７）より低いので（Ｓ３７）、基準点Ｐ（６）を地表面デ−タと判定し（Ｓ３８）、検査点であった点Ｐ（７）を新たな基準点とし、その次の点Ｐ（８）を新たな検査点、次の次の点Ｐ（９）を新たな対象点とする（Ｓ３２）。

１つのタイル内で終了条件（Ｓ３３，Ｓ３４）が満たされるまで、以上の処理が繰り返される。このような処理を繰り返すことで、地表面から突出している可能性の高い点デ−タを除外して、地表面を確度よく判定できる。

図１３は、図９に示す点デ−タの例に対して、図８及び図１１に示すフロ−による地表面デ−タの採用と検査点の削除の遷移の模式図である。図１３で、削除（ｎ）は、以下のｎ回目の処理で削除される点デ−タであることを示し、採用（ｎ）は、ｎ回目の処理で地表面デ−タとして採用された点デ−タであることを示す。右向きの矢印は、基準点からの距離Ｒｒｅｆを示す。

図８の１回目の処理では、点Ｐ（１）が基準点、点Ｐ（２）が検査点、点Ｐ（３）が対象点である。ｙ方向で対象点Ｐ（３）が基準点Ｐ（１）から距離Ｒｒｅｆ以内にあり（Ｓ３６）、基準点Ｐ（１）と検査点Ｐ（２）の高さが異なる（Ｓ４０）。基準点Ｐ（１）と検査点Ｐ（２）のｙ座標値も異なるので（Ｓ４１）、検査点削除判定処理（Ｓ４５）を実行する。検査点Ｐ（２）は、基準点Ｐ（１）と対象点Ｐ（３）に接する半径Ｒｒｅｆの下側の円の中心から所定距離Ｒｒｅｆ＋ε以上離れているので（Ｓ６３）、検査点Ｐ（２）を削除する（Ｓ６４）。この結果、Ｐ（３）を検査点とし（Ｓ４７）、Ｐ（４）を対象点とする（Ｓ４８）。即ち、点Ｐ（２）が削除される。

２回目では、対象点Ｐ（４）が基準点Ｐ（１）からｙ方向でＲｒｅｆ以上に離れている（Ｓ３６）。基準点Ｐ（１）と検査点Ｐ（３）の高さを比較すると（Ｓ３７）、基準点Ｐ（１）が低いので、点Ｐ（１）を地表面デ−タと判定し（Ｓ３８）、検査点であった点Ｐ（３）を基準点とし、その次の点Ｐ（４）を検査点、次の次の点Ｐ（５）を対象点とする（Ｓ３２）。

３回目の処理では、点Ｐ（３）が基準点、点Ｐ（４）が検査点、点Ｐ（５）が対象点である。ｙ方向で対象点Ｐ（５）が基準点Ｐ（３）から距離Ｒｒｅｆ以内にあり（Ｓ３６）、基準点Ｐ（３）と検査点Ｐ（４）の高さが異なる（Ｓ４０）。基準点Ｐ（３）と検査点Ｐ（４）のｙ座標値も異なるので（Ｓ４１）、検査点削除判定処理（Ｓ４５）を実行する。検査点Ｐ（４）は、基準点Ｐ（３）と対象点Ｐ（５）に接する半径Ｒｒｅｆの下側の円の中心から所定距離Ｒｒｅｆ＋ε以上離れているので（Ｓ６３）、検査点Ｐ（４）を削除する（Ｓ６４）。この結果、対象点Ｐ（５）を新たな検査点とし（Ｓ４７）、対象点Ｐ（５）の次の点Ｐ（６）を新たな対象点とする（Ｓ４８）。即ち、点Ｐ（４）が削除される。

４回目の処理では、点Ｐ（３）が基準点、点Ｐ（５）が検査点、点Ｐ（６）が対象点である。ｙ方向で対象点Ｐ（６）が基準点Ｐ（３）からＲｒｅｆ以上に離れている（Ｓ３６）。基準点Ｐ（３）と検査点Ｐ（５）の高さを比較すると（Ｓ３７）、基準点Ｐ（３）が低いので、点Ｐ（３）を地表面デ−タと判定し（Ｓ３８）、検査点であった点Ｐ（５）を新たな基準点とし、その次の点Ｐ（６）を新たな検査点、次の次の点Ｐ（７）を新たな対象点とする（Ｓ３２）。

５回目の処理では、点Ｐ（５）が基準点、点Ｐ（６）が検査点、点Ｐ（７）が対象点である。ｙ方向で対象点Ｐ（７）が基準点Ｐ（５）から距離Ｒｒｅｆ以内にあり（Ｓ３６）、基準点Ｐ（５）と検査点Ｐ（６）の高さが異なる（Ｓ４０）。基準点Ｐ（５）と検査点Ｐ（６）のｙ座標値も異なるので（Ｓ４１）、検査点削除判定処理（Ｓ４５）を実行する。検査点Ｐ（６）は、基準点Ｐ（５）と対象点Ｐ（７）に接する半径Ｒｒｅｆの下側の円の中心から所定距離Ｒｒｅｆ＋ε以内にあるのでので（Ｓ６３）、検査点Ｐ（６）を削除せずに（Ｓ６５）、対象点Ｐ（７）の次の点Ｐ（８）を新たな対象点とする（Ｓ４８）。即ち、対象点のみを移動する。

６回目の処理では、点Ｐ（５）が基準点、点Ｐ（６）が検査点、点Ｐ（８）が対象点である。ｙ方向で対象点Ｐ（８）が基準点Ｐ（５）からＲｒｅｆ以上に離れている（Ｓ３６）。基準点Ｐ（５）と検査点Ｐ（６）の高さを比較すると（Ｓ３７）、基準点Ｐ（５）より検査点Ｐ（６）が低いので（Ｓ３７）、検査点Ｐ（６）を新たな基準点とし（Ｓ３９）、その次の点Ｐ（７）を新たな検査点、次の次の点Ｐ（８）を対象点とする（Ｓ３２）。即ち、Ｐ（５）を削除する。

７回目の処理では、点Ｐ（６）が基準点、点Ｐ（７）が検査点、点Ｐ（８）が対象点である。ｙ方向で対象点Ｐ（８）が基準点Ｐ（６）から距離Ｒｒｅｆ以内にあり（Ｓ３６）、基準点Ｐ（６）と検査点Ｐ（７）の高さが異なる（Ｓ４０）。基準点Ｐ（６）と検査点Ｐ（７）のｙ座標値も異なるので（Ｓ４１）、検査点削除判定処理（Ｓ４５）を実行する。検査点Ｐ（７）は、基準点Ｐ（６）と対象点Ｐ（８）に接する半径Ｒｒｅｆの下側の円の中心から所定距離Ｒｒｅｆ＋ε以内にあるのでので（Ｓ６３）、検査点Ｐ（７）を削除せずに（Ｓ６５）、対象点Ｐ（８）の次の点Ｐ（９）を新たな対象点とする（Ｓ４８）。即ち、対象点のみを移動する。

８回目の処理では、点Ｐ（６）が基準点、点Ｐ（７）が検査点、点Ｐ（９）が対象点である。ｙ方向で対象点Ｐ（９）が基準点Ｐ（６）からＲｒｅｆ以上に離れている（Ｓ３６）。基準点Ｐ（６）と検査点Ｐ（７）の高さを比較すると（Ｓ３７）、基準点Ｐ（６）が検査点Ｐ（７）より低いので（Ｓ３７）、基準点Ｐ（６）を地表面デ−タと判定し（Ｓ３８）、検査点であった点Ｐ（７）を新たな基準点とし、その次の点Ｐ（８）を新たな検査点、次の次の点Ｐ（９）を新たな対象点とする（Ｓ３２）。

１つのタイル内で終了条件（Ｓ３３，Ｓ３４）が満たされるまで、以上の処理が繰り返される。このような処理を繰り返すことで、地表面から突出している可能性の高い点デ−タを除外して、地表面を確度よく判定できる。

図８と図１０又は、図８と図１１の何れの方法でも、下り坂の部分で地表面データを除去しすぎてしまう可能性がある。しかし、これは、順方向と逆方向の２方向で同じアルゴリズムにより地表面を探索し、その結果の加算、即ち論理和をとることで解決できる。即ち、どちらかの方向の探索で地表面と探知された点デ−タを、最終的に地表面デ−タであるとする。

特定の説明用の実施例を参照して本発明を説明したが、特許請求の範囲に規定される本発明の技術的範囲を逸脱しないで、上述の実施例に種々の変更・修整を施しうることは、本発明の属する分野の技術者にとって自明であり、このような変更・修整も本発明の技術的範囲に含まれる。

本発明の一実施例の概略構成ブロック図である。 処理対象領域の説明図である。 処理対象領域Ｒ（ｎ，ｍ）とメモリ１４に格納する領域の関係の説明図である。 ｘ方向タイル分割装置１６によるタイル分割の説明図である。 ｘ方向タイル分割装置１６、順方向フィルタ１８Ｆ及び逆方向フィルタ１８Ｂにおける処理のフロ−チャ−トである。 ｙ方向タイル分割装置２２によるタイル分割の説明図である。 ｙ方向タイル分割装置２２、順方向フィルタ２４Ｆ及び逆方向フィルタ２４Ｂにおける処理のフロ−チャ−トである。 順方向フィルタ１８Ｆのフィルタ処理のフロ−チャ−トである。 タイル分割装置１６で分割されたｙ方向に延びるタイルに含まれる点デ−タのｙ−ｚ面で見た配置例である。 検査点削除判定処理（Ｓ４５）の第１の方法のフロ−チャ−トである。 検査点削除判定処理（Ｓ４５）の第２の方法のフロ−チャ−トである。 図８及び図１０に示すフロ−による地表面デ−タの採用と検査点の削除の遷移の模式図である。 図８及び図１１に示すフロ−による地表面デ−タの採用と検査点の削除の遷移の模式図である。 ＬｉＤＡＲシステムにより計測された３次元点デ−タの例である。

符号の説明

１０：メモリ
１２：処理対象抽出装置
１４：メモリ
１６：ｘ方向タイル分割装置
１８Ｆ：順方向フィルタ
１８Ｂ：逆方向フィルタ
２０Ｆ，２０Ｂ：メモリ
２２：ｙ方向タイル分割装置
２４Ｆ：順方向フィルタ
２４Ｂ：逆方向フィルタ
２６Ｆ，２６Ｂ：メモリ
２８：重複削除装置
３０：クリップ装置
３２：処理結果メモリ
３４：制御装置

Claims (18)

1. ３次元点デ−タをｘ−ｙ面内の第１の方向で複数のタイルに分割する第１のタイル分割ステップと、
   当該第１の方向で分割された各タイルについて、点デ−タを順方向にフィルタ処理することにより地表面を示す第１の点デ−タを抽出する第１のフィルタ処理ステップと、
   当該第１の方向で分割された各タイルについて、点デ−タを逆方向にフィルタ処理することにより地表面を示す第２の点デ−タを抽出する第２のフィルタ処理ステップと、
   当該第１の点デ−タと当該第２の点デ−タの少なくとも一方に含まれる点デ−タを抽出する第１の抽出ステップ
   とを具備することを特徴とする３次元デ−タ処理方法。
2. 更に、
   当該３次元点デ−タをｘ−ｙ面内の第１の方向に直交する第２の方向で複数のタイルに分割する第２のタイル分割ステップと、
   当該第２の方向で分割された各タイルについて、点デ−タを順方向にフィルタ処理することにより地表面を示す第３の点デ−タを抽出する第３のフィルタ処理ステップと、
   当該第２の方向で分割された各タイルについて、点デ−タを逆方向にフィルタ処理することにより地表面を示す第４の点デ−タを抽出する第４のフィルタ処理ステップと、
   当該第１の抽出ステップに代わる、当該第１、第２、第３及び第４の点デ−タの少なくとも一つに含まれる点デ−タを抽出する第２の抽出ステップ
   とを具備する
   ことを特徴とする請求項１に記載の３次元処理方法。
3. 当該第１及び当該第２のフィルタ処理ステップで使用されるフィルタ処理が同じアルゴリズムに基づくことを特徴とする請求項１に記載の３次元デ−タ処理方法。
4. 当該第１、第２、第３及び第４のフィルタ処理ステップで使用されるフィルタ処理が同じアルゴリズムに基づくことを特徴とする請求項２に記載の３次元デ−タ処理方法。
5. 当該フィルタ処理が、
   互いに異なる点デ−タにその並び方向で基準点（ｉ）、検査点（ｊ）及び対象点（ｋ）を設定するステップ（Ｓ３１，Ｓ３２）と、
   当該基準点（ｉ）と当該対象点（ｋ）との距離を判定するステップ（Ｓ３６）と、
   当該基準点（ｉ）と当該対象点（ｋ）との距離が所定値より大きく（Ｓ３６）、且つ、基準点（ｉ）の高さが検査点（ｊ）の高さ以下の場合に（Ｓ３７）、基準点（ｉ）の点デ−タを当該第１の点デ−タとして採用すると（Ｓ３８）共に、検査点（ｊ）及び対象点（ｋ）をそれぞれ次の点デ−タに更新するステップ（Ｓ３２）と、
   当該基準点（ｉ）と当該対象点（ｋ）の距離が所定値以下の場合に（Ｓ３６）、基準点（ｉ）、検査点（ｊ）及び対象点（ｋ）から当該検査点（ｊ）の要否を判定する判定ステップ（Ｓ４５）と、
   当該判定ステップ（Ｓ４５）により当該検査点が不要と判定された場合に、当該検査点の次の点を新たな検査点（ｊ）とし、当該検査点の次の次の点を新たな対象点（ｋ）とし、当該判定ステップ（Ｓ４５）により当該検査点が必要と判定された場合に、当該検査点の次の次の点を新たな対象点とするステップ（Ｓ４６，Ｓ４７，Ｓ４８）
   とを具備することを特徴とする請求項３又は４に記載の３次元デ−タ処理方法。
6. 当該判定ステップ（Ｓ４５）が、当該基準点（ｉ）と当該検査点（ｊ）を結ぶ線の傾きと、当該基準点（ｉ）と当該対象点（ｋ）を結ぶ線の傾きを算出し（Ｓ５１）、両傾きの比較により（Ｓ５２）、当該検査点（ｊ）の要否を判定することを特徴とする請求項５に記載の３次元デ−タ処理方法。
7. 当該判定ステップ（Ｓ４５）が、当該基準点（ｉ）と当該対象点（ｋ）に接する所定半径の下側の円の中心から当該検査点（ｊ）までの距離を算定し（Ｓ６２）、当該距離が所定値より大きい場合に当該検査点（ｊ）を不要と判定し、当該距離が当該所定値以下の場合に当該検査点（ｊ）を必要と判定する（Ｓ６３）ことを特徴とする請求項５に記載の３次元デ−タ処理方法。
8. 当該３次元点デ−タが、処理対象地域に所定のマ−ジンを含めた地域の点デ−タからなり、
   当該３次元デ−タ処理方法が更に、当該第１の抽出ステップで抽出された点デ−タから当該処理対象地域内の点デ−タをクリップするステップを具備する
   ことを特徴とする請求項１に記載の３次元デ−タ処理方法。
9. 当該３次元点デ−タが、処理対象地域に所定のマ−ジンを含めた地域の点デ−タからなり、
   当該３次元デ−タ処理方法が更に、当該第２の抽出ステップで抽出された点デ−タから当該処理対象地域内の点デ−タをクリップするステップを具備する
   ことを特徴とする請求項２に記載の３次元デ−タ処理方法。
10. ３次元点デ−タをｘ−ｙ面内の第１の方向で複数のタイルに分割する第１のタイル分割手段（１６）と、
    当該第１の方向で分割された各タイルについて、点デ−タを順方向にフィルタ処理し、地表面を示す第１の点デ−タを出力する第１のフィルタ処理手段（１８Ｆ）と、
    当該第１の方向で分割された各タイルについて、点デ−タを逆方向にフィルタ処理し、地表面を示す第２の点デ−タを出力する第２のフィルタ処理手段（１８Ｂ）と、
    当該第１の点デ−タと当該第２の点デ−タの少なくとも一方に含まれる点デ−タを抽出する抽出器（２８）
    とを具備することを特徴とする３次元デ−タ処理装置。
11. 更に、
    当該３次元点デ−タをｘ−ｙ面内の第１の方向に直交する第２の方向で複数のタイルに分割する第２のタイル分割手段（２２）と、
    当該第２の方向で分割された各タイルについて、点デ−タを順方向にフィルタ処理し、地表面を示す第３の点デ−タを出力する第３のフィルタ処理手段（２４Ｆ）と、
    当該第２の方向で分割された各タイルについて、点デ−タを逆方向にフィルタ処理し、地表面を示す第４の点デ−タを出力する第４のフィルタ処理手段（２４Ｂ）
    とを具備し、
    当該抽出器（２８）が、当該第１、第２、第３及び第４の点デ−タの少なくとも一つに含まれる点デ−タを抽出することを特徴とする請求項１０に記載の３次元処理装置。
12. 当該第１及び当該第２のフィルタ処理手段（１８Ｆ，１８Ｂ）のフィルタ処理が同じアルゴリズムに基づくことを特徴とする請求項１０に記載の３次元デ−タ処理装置。
13. 当該第１、第２、第３及び第４のフィルタ処理手段（１８Ｆ，１８Ｂ，２４Ｆ，２４Ｂ）のフィルタ処理が同じアルゴリズムに基づくことを特徴とする請求項１１に記載の３次元デ−タ処理装置。
14. 当該フィルタ処理が、
    互いに異なる点デ−タにその並び方向で基準点（ｉ）、検査点（ｊ）及び対象点（ｋ）を設定する処理（Ｓ３１，Ｓ３２）と、
    当該基準点（ｉ）と当該対象点（ｋ）との距離を判定する処理（Ｓ３６）と、
    当該基準点（ｉ）と当該対象点（ｋ）との距離が所定値より大きく（Ｓ３６）、且つ、基準点（ｉ）の高さが検査点（ｊ）の高さ以下の場合に（Ｓ３７）、基準点（ｉ）の点デ−タを当該第１の点デ−タとして採用すると（Ｓ３８）共に、検査点（ｊ）及び対象点（ｋ）をそれぞれ次の点デ−タに更新する処理（Ｓ３２）と、
    当該基準点（ｉ）と当該対象点（ｋ）の距離が所定値以下の場合に（Ｓ３６）、基準点（ｉ）、検査点（ｊ）及び対象点（ｋ）から当該検査点（ｊ）の要否を判定する判定処理（Ｓ４５）と、
    当該判定処理（Ｓ４５）により当該検査点が不要と判定された場合に、当該検査点の次の点を新たな検査点（ｊ）とし、当該検査点の次の次の点を新たな対象点（ｋ）とし、当該判定処理（Ｓ４５）により当該検査点が必要と判定された場合に、当該検査点の次の次の点を新たな対象点とする処理（Ｓ４６，Ｓ４７，Ｓ４８）
    とを具備することを特徴とする請求項１２又は１３に記載の３次元デ−タ処理装置。
15. 当該判定処理（Ｓ４５）が、当該基準点（ｉ）と当該検査点（ｊ）を結ぶ線の傾きと、当該基準点（ｉ）と当該対象点（ｋ）を結ぶ線の傾きを算出し（Ｓ５１）、両傾きの比較により（Ｓ５２）、当該検査点（ｊ）の要否を判定することを特徴とする請求項１２に記載の３次元デ−タ処理装置。
16. 当該判定処理（Ｓ４５）が、当該基準点（ｉ）と当該対象点（ｊ）に接する所定半径の下側の円の中心から当該検査点（ｊ）までの距離を算定し（Ｓ６２）、当該距離が所定値以上の場合に当該検査点（ｊ）を不要と判定し、当該距離が当該所定値未満の場合に当該検査点（ｊ）を必要と判定する（Ｓ６３）ことを特徴とする請求項１４に記載の３次元デ−タ処理装置。
17. 当該３次元点デ−タが、処理対象地域に所定のマ−ジンを含めた地域の点デ−タからなり、
    当該３次元デ−タ処理装置が更に、当該第１の抽出ステップで抽出された点デ−タから当該処理対象地域内の点デ−タをクリップする装置（３０）を具備する
    ことを特徴とする請求項１１に記載の３次元デ−タ処理装置。
18. 当該３次元点デ−タが、処理対象地域に所定のマ−ジンを含めた地域の点デ−タからなり、
    当該３次元デ−タ処理装置が更に、当該第抽出器（２８）で抽出された点デ−タから当該処理対象地域内の点デ−タをクリップする装置（３０）を具備する
    ことを特徴とする請求項１２に記載の３次元デ−タ処理装置。

Images