(57)【特許請求の範囲】
【請求項１】
物体の表面上の位置を計測した計測結果である複数の位置を表す３次元点群から、３次元点における平面度合い及び密度に基づいて、前記物体の高自己相関断面形状を求めるための代表点群を決定する代表点群決定部と、
前記代表点群に含まれる代表点の各々について、前記代表点の周辺点群の３次元形状が、ある特定の３次元方向において高自己相関断面形状を有するか否かを判定する規定断面形状存在判定部と、
前記規定断面形状存在判定部により前記高自己相関断面形状を有すると判定された代表点の各々について、押し出し方向と、前記代表点の周辺点群とに基づいて、規定断面形状を生成する規定断面形状生成部と、
前記規定断面形状生成部により前記代表点の各々について生成された規定断面形状に基づいて、前記押し出し方向及び前記規定断面形状の類似度を指標として、前記規定断面形状を統合し、前記３次元点群から、前記統合された前記規定断面形状が表す押し出し形状領域に含まれる点群を検出する規定断面統合部と、
を含む領域分割処理装置。
【請求項２】
前記規定断面形状存在判定部は、
前記代表点群に含まれる代表点の各々について、前記代表点を注目代表点とし、
前記注目代表点から特定の距離に含まれる周辺点群に基づいて複数の自己相関算出方向を決定し、
前記複数の自己相関算出方向の各々を用いて、前記周辺点群の自己相関算出方向における位置を指標とした複数の断面形状画像を生成し、
前記複数の自己相関算出方向の各々について、前記自己相関算出方向を用いて生成した複数の断面形状画像における断面形状ベクトルの自己相関値を算出し、前記算出した複数の断面形状画像における断面形状ベクトルの自己相関値に基づいて、前記高自己相関断面形状を有するか否かを判定すると共に、前記自己相関値が大きい前記自己相関算出方向の集合を押し出し方向群として求める請求項１に記載の領域分割処理装置。
【請求項３】
前記代表点群決定部は、
局所領域内での前記３次元点の点群密度及び平面度を考慮して、密度が高く、かつ、平面度が低い３次元点を優先して前記代表点のリサンプリング処理を行う請求項１又は請求項２に記載の領域分割処理装置。
【請求項４】
前記規定断面形状生成部は、
押し出し方向に前記代表点の周辺点群から生成される断面形状画像の部分断面画像の各々について、前記部分断面画像における部分断面ベクトルの自己相関値を算出し、前記部分断面画像の各画素が有効であるか否かを判定して、前記規定断面形状を生成する請求項１〜請求項３のいずれか１項に記載の領域分割処理装置。
【請求項５】
前記規定断面統合部は、
前記代表点の各々について、前記代表点を注目代表点とし、前記注目代表点の押し出し方向と、周辺の代表点の押し出し方向とのペアのうち、類似した押し出し方向のペアごとに求めた規定断面形状の重複強さに基づいて、前記注目代表点と前記周辺の代表点との間にリンクを構築し、
リンクが構築された代表点群を同一のクラスタと判定して、同一のクラスタの代表点群の前記規定断面形状を統合する請求項１〜請求項４のいずれか１項に記載の領域分割処理装置。
【請求項６】
代表点群決定部が、物体の表面上の位置を計測した計測結果である複数の位置を表す３次元点群から、３次元点における平面度合い及び密度に基づいて、前記物体に共通した断面形状を求めるための代表点群を決定するステップと、
規定断面形状存在判定部が、前記代表点群に含まれる代表点の各々について、前記代表点の周辺点群の３次元形状が、ある特定の３次元方向において高自己相関断面形状を有するか否かを判定するステップと、
規定断面形状生成部が、前記規定断面形状存在判定部により前記高自己相関断面形状を有すると判定された代表点の各々について、押し出し方向と、前記代表点の周辺点群とに基づいて、規定断面形状を生成するステップと、
規定断面統合部が、前記規定断面形状生成部により前記代表点の各々について生成された規定断面形状に基づいて、前記押し出し方向及び前記規定断面形状の類似度を指標として、前記規定断面形状を統合し、前記３次元点群から、前記統合された前記規定断面形状が表す押し出し形状領域に含まれる点群を検出するステップと、
を含む領域分割処理方法。
【請求項７】
コンピュータを、請求項１〜請求項５のいずれか１項に記載の領域分割処理装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、領域分割処理装置、方法、及びプログラムに係り、特に、入力された３次元点群の領域を分割するための領域分割処理装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
モバイルマッピングシステム（ＭＭＳ）と呼ばれるカメラやレーザースキャナを搭載した車が、街中を走行することで道路周辺の構造物表面の形状を計測できるシステムが利用されつつある。このシステムは、ＧＰＳ（全地球測位システム）やＩＭＳ(慣性計測装置)を用いて物体の表面を３次元の座標情報として記録できる。この技術を利用して、道路周辺の建造物や道路の検出による３次元の地図作成や、信号機や標識などのインフラ設備の保守・保全業務への活用が期待されている。
【０００３】
従来技術においては、点群をまず地物（電柱や街灯、建造物など）ごとに分割し、分割された点群の形状を解析することで、分割された点群が検出対象物であるか判定処理を行っている。そのため、入力点群を精度よく地物単位ごとに切り出すことが重要であった。
【０００４】
非特許文献１では、前処理により地面を構成する点群を除いた後に、点群を電柱や街灯、建造物などの地物単位で点群をクラスタリングし、クラスタリングされた点群の形状を細線化処理することで、細線化された度合いにより柱状構造物が存在するかどうか検出処理を行っている。
【０００５】
非特許文献２では、点群を点群の法線に垂直な面と相対位置関係と法線のＺ軸方向の成分の大きさを指標としてクラスタリングを行っている。同一の物体であれば、法線面は滑らかに変化しているという条件により、ノイズに頑健にクラスタリングが可能となり、さらにＺ軸に対してほぼ垂直な法線を持つ点群について近傍点についてクラスタリングを行うという条件をつけることで、車や建造物壁面など法線が急激に変化するコーナーの領域があっても同一の領域としてクラスタリングが可能となった。
【０００６】
非特許文献３では、法線や点の色情報、距離情報等を指標としたときの類似度が高い点群を優先的にクラスタリングしていく。このとき、クラスタリングの閾値を、クラスタの大きさや各クラスタ内の類似度の大きさに応じて変化させることができ、よりノイズにも頑健にクラスタリングが可能である。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Hiroki Yokoyama, Hiroaki Date, Satoshi Kanai, Hiroshi Takeda: "Detection and Classification of Pole-like Objects from Mobile Laser Scanning Data of Urban Environments", International Journal of CAD/CAM, 13(2), 31-40 (2013)
【非特許文献２】Moosmann, F., Pink, O., Stiller, C. (2009). Segmentationof 3D Lidar Data in Non-flat Urban Environments using a Local Convexity Criterion, Proc. IEEE Intelligent Vehicles,Symposium, 215-220 (2009)
【非特許文献３】Johannes H. Strom, Andrew Richardson, and Edwin Olson,”Graph-based segmentation for colored 3D laser point clouds”, IROS, page 2131-2136. IEEE, (2010)
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、ＭＭＳで計測した点群は、同一スキャンラインの点群の密度は高いが、スキャンライン間の点群の密度は低いことが多い。例えば、高速道路では走行速度が速いため、同一スキャンラインの隣り合う点群の相対距離は数ｃｍ以内に対して、スキャンラインは２０ｃｍ〜３０ｃｍ程になることもある。
【０００９】
また、市街地内においては、建造物同市や樹木等が隣接するために、局所的な形状情報、法線情報や曲率情報の推定精度が低くなるという問題がある。そのため、これら局所形状を指標としたクラスタリング手法では、領域分割精度が低下するという課題がある。特に、ガードレールのような、曲率の大きさが急激に変化する部分を多く含むような物体の場合には、法線推定精度は低下しやすく、クラスタリング精度が低下する。
【００１０】
また、局所形状推定精度が低い場合、クラスタリングの閾値設定が厳しいと、同一物体でも複数のクラスタが生成されやすく、つまり過分割されやすい。一方、クラスタリングの閾値の設定を緩めると、隣接物と同一クラスタとなりやすくなってしまい、閾値の設定が困難であるという課題がある。
【００１１】
また、近傍点を用いてクラスタリングを行っているために、オクルージョン（障害物により計測されない被写体表面領域）による欠損部分が境界となってしまうため、クラスタリングの精度が低下する。つまり、同一物体であっても、異なる物体の領域と判定されるという課題がある。
【００１２】
本発明は、上記問題点を解決するために成されたものであり、隣接する構造物が存在する場合でも、精度よく、点群領域を分割できる領域分割処理装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するために、第１の発明に係る領域分割処理装置は、物体の表面上の位置を計測した計測結果である複数の位置を表す３次元点群から、３次元点における平面度合い及び密度に基づいて、前記物体の自己相関値の高い高自己相関断面形状を求めるための代表点群を決定する代表点群決定部と、前記代表点群に含まれる代表点の各々について、前記代表点の周辺点群の３次元形状が、ある特定の３次元方向に自己相関値の高い高自己相関断面形状を有するか否かを判定する規定断面形状存在判定部と、前記規定断面形状存在判定部により前記高自己相関断面形状を有すると判定された代表点の各々について、押し出し方向と、前記代表点の周辺点群とに基づいて、規定断面形状を生成する規定断面形状生成部と、前記規定断面形状生成部により前記代表点の各々について生成された規定断面形状に基づいて、前記押し出し方向及び前記規定断面形状の類似度を指標として、前記規定断面形状を統合し、前記３次元点群から、前記統合された前記規定断面形状が表す押し出し形状領域に含まれる点群を検出する規定断面統合部と、を含んで構成されている。
【００１４】
また、第１の発明に係る領域分割処理装置において、前記規定断面形状存在判定部は、前記代表点群に含まれる代表点の各々について、前記代表点を注目代表点とし、前記注目代表点から特定の距離に含まれる周辺点群に基づいて複数の自己相関算出方向を決定し、前記複数の自己相関算出方向の各々を用いて、前記周辺点群の自己相関算出方向における位置を指標とした複数の断面形状ベクトルを生成し、前記複数の自己相関算出方向の各々について、前記自己相関算出方向の位置を指標として用いて生成した複数の断面形状画像の断面形状ベクトルの相関値を算出し、前記算出した複数の断面形状画像の断面形状ベクトルの相関値に基づいて、前記高自己相関断面形状を有するか否かを判定すると共に、前記相関値が大きい前記自己相関算出方向の集合を押し出し方向群として求めるようにしてもよい。
【００１５】
また、第１の発明に係る領域分割処理装置において、前記代表点群決定部は、局所領域内での前記３次元点の点群密度及び平面度を考慮して、密度が高く、かつ、平面度が低い３次元点を優先して前記代表点のリサンプリング処理を行うようにしてもよい。
【００１６】
また、第１の発明に係る領域分割処理装置において、前記規定断面形状生成部は、押し出し方向の位置を指標として生成される断面形状画像の部分断面画像の各々について、前記部分断面画像の相関値を算出し、前記断面形状画像の各画素が有効であるか否かを判定して、前記規定断面形状を生成するようにしてもよい。
【００１７】
また、第１の発明に係る領域分割処理装置において、前記規定断面統合部は、前記代表点の各々について、前記代表点を注目代表点とし、前記注目代表点の押し出し方向と、周辺の代表点の押し出し方向とのペアのうち、類似した押し出し方向のペアごとに求めた規定断面形状の重複強さに基づいて、前記注目代表点と前記周辺の代表点との間にリンクを構築し、リンクが構築された代表点群を同一のクラスタと判定して、同一のクラスタの代表点群の前記規定断面形状を統合するようにしてもよい。
【００１８】
第２の発明に係る領域分割処理方法は、代表点群決定部が、物体の表面上の位置を計測した計測結果である複数の位置を表す３次元点群から、３次元点における平面度合い及び密度に基づいて、前記物体の高自己相関断面形状を求めるための代表点群を決定するステップと、規定断面形状存在判定部が、前記代表点群に含まれる代表点の各々について、前記代表点の周辺点群の３次元形状が、ある特定の３次元方向において高自己相関断面形状を有するか否かを判定するステップと、規定断面形状生成部が、前記規定断面形状存在判定部により前記高自己相関断面形状を有すると判定された代表点の各々について、押し出し方向と、前記代表点の周辺点群とに基づいて、規定断面形状を生成するステップと、規定断面統合部が、前記規定断面形状生成部により前記代表点の各々について生成された規定断面形状に基づいて、前記押し出し方向及び前記規定断面形状の類似度を指標として、前記規定断面形状を統合し、前記３次元点群から、前記統合された前記規定断面形状が表す押し出し形状領域に含まれる点群を検出するステップと、を含んで実行することを特徴とする。
【００１９】
第３の発明に係るプログラムは、コンピュータを、第１の発明に係る領域分割処理装置の各部として機能させるためのプログラムである。
【発明の効果】
【００２０】
本発明の領域分割処理装置、方法、及びプログラムによれば、３次元点群から、３次元点における平面度合い及び密度に基づいて、代表点群を決定し、代表点群に含まれる代表点の各々について、代表点の周辺点群の３次元形状が、特定の３次元方向に高自己相関断面形状を有するか否かを判定し、高自己相関断面形状を有すると判定された代表点の各々について、押し出し方向と、代表点の周辺点群とに基づいて、規定断面形状を生成し、押し出し方向及び規定断面形状の類似度を指標として、規定断面形状を統合し、３次元点群から、統合された規定断面形状が表す押し出し形状領域に含まれる点群を検出することにより、隣接する構造物が存在する場合でも、精度よく、点群領域を分割できる、という効果が得られる。
【図面の簡単な説明】
【００２１】
【図１】任意曲線の押し出し形状の一例を示す概念図である。
【図２】隣接した物体（標識柱とフェンス）の模式図である。
【図３】押し出し形状領域の一例を示す概念図である。
【図４】本発明の実施の形態に係る領域分割処理装置の構成を示すブロック図である。
【図５】本発明の実施の形態に係る領域分割処理装置における領域分割処理ルーチンを示すフローチャートである。
【図６】領域分割処理ルーチンのステップＳ１の詳細なフローチャートである。
【図７】領域分割処理ルーチンのステップＳ２の詳細なフローチャートである。
【図８】領域分割処理ルーチンのステップＳ２−１の詳細なフローチャートである。
【図９】押し出し形状領域における規定断面形状の検出の一例を示す概念図。
【図１０】相関値計算の一例を示す概念図である。
【図１１】領域分割処理ルーチンのステップＳ３の詳細なフローチャートである。
【図１２】領域分割処理ルーチンのステップＳ３−２の詳細なフローチャートである。
【図１３】相関値計算の一例を示す概念図である。
【図１４】領域分割処理ルーチンのステップＳ４の詳細なフローチャートである。
【図１５】領域分割処理ルーチンのステップＳ４−２の詳細なフローチャートである。
【図１６】注目点と規定断面のペアの一例を示す概念図である。
【発明を実施するための形態】
【００２２】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２３】
［発明の概要］
【００２４】
まず、本発明の実施の形態における概要を説明する。
【００２５】
建造物や柱状構造物等の人工物の多くは、ある任意の形状（以下、規定断面形状と呼ぶ）をその形状に垂直な方向へ押し出した形状で構成されていることが多い。例えば、図１に示すように、電柱でいえば円形を、平面でいえば直線を、立方体であれば四角形を、その図形が存在する平面に垂直な方向へ押し出した形状と考えられ、建造物はそれらの形状の組み合わせと考えられる。
【００２６】
また、同一の押し出し形状領域であれば、任意の位置で表面に垂直な断面形状が、この規定断面形状になる。そこで本発明の実施の形態では、３次元点群の中から押し出し形状を検出し、類似した規定断面形状をクラスタリングすることで押し出し形状領域を検出する。これにより、曲率が急激に変化する領域を多く含む形状であっても、精度よくクラスタリングが可能である。一方、平面部分については、平面近似により押し出し方向（法線に垂直な方向）と形状（直線）であることが解析的に判定できる。本発明の実施の形態においては、推定した規定断面形状について、隣接する規定断面形状同士の連結強さを指標としてクラスタリングを行う。これにより、個々の点で推定した法線や距離情報を指標としたクラスタリング技術と異なり、よりスケールの大きな物体の形状を指標とすることになり、精度向上を行うことができる。
【００２７】
例えば、図２に示すように、従来技術では近傍点の距離を大きくすると、類似した法線を有する点群が同一物体としてクラスタリングされてしまう（図２（Ａ））。しかし、物体ごとに形状が異なるため、法線と異なり、規断面形状の形と押し出し方向は異なる物体では類似しづらい（図２（Ｂ）及び図２（Ｃ））。そのため、隣接している状態でも、規定断面形状を指標にしたクラスタリングをすることで、領域分割の精度低下を抑制できる。
【００２８】
また、クラスタリングするための探索距離を広くできることにより、オクルージョンによる欠損部分に対しても頑健にクラスタリングが可能である。例えば、欠損領域幅が２０ｃｍ〜３０ｃｍであったとしても、それ以上の探索距離を設定すればよい。
【００２９】
建造物のように複数の押し出し形状領域により構成される物体についても、各領域で推定した規定断面形状の重複度合により、複数の押し出し形状領域を１つの領域としてクラスタリングすることが可能である。なぜなら、図３に示すように、押し出し領域Ａと押し出し領域Ｂについて接する部分が、部分的である場合においても、平面領域と判定された点群（領域Ｃ）を介して、押し出し領域Ａと押し出し領域Ｂの点群が１つのクラスタすることが可能なためである。
【００３０】
［実施形態の概説］
【００３１】
本発明の実施の形態に係る領域分割処理装置は、３次元点群を入力として、クラスタリングを行うことにより、個々の人工物ごとに属する点群になるように切り分けること（領域分割）を目的とするものである。
【００３２】
本発明の実施の形態での３次元情報とは、緯度、経度、海抜（高さ）情報でもよいし、ユーザーが設定した特定の位置を原点とした３次元ユークリッド座標系でも極座標系でもよい。以下の例では、ユーザーが設定した原点における３次元ユークリッド座標系（各方向をＸ，Ｙ，Ｚ座標とする）を想定する。各座標の単位はメートル(ｍ)やセンチメートル(ｃｍ)、ミリメートル(ｍｍ)で表現するが、他の単位でもよい。以降に距離の単位が記載されていないときは、単位はメートル（ｍ)とする。
【００３３】
３次元点とは、各点に上記の３次元座標に、その点群が撮影された時刻や、レーザーの反射強度や赤・青・緑などの色情報等が付与されている点である。３次元点に付与される情報に制限はないが、少なくとも位置情報（Ｘ，Ｙ，Ｚ座標）と時刻は付与されたものであり、３次元点群とはその３次元点が2点以上集まった集合である。また、本実施例において、ユークリッド座標系のZ軸の方向は鉛直（高さ）方向を意味し、X軸とY軸の張る二次元平面は水平面を意味するとする。また、３次元点群はレーザースキャナ以外にも、距離情報を取得できるセンサであればよく、例えばステレオカメラにより取得した奥行き情報から求めた３次元点群でもよい。
【００３４】
ここで、本発明の実施の形態においての重要な用語の説明を記載する。点群を「クラスタリング」するとは、設定した指標として、同一の物体に属する点であると判定して統合する処理を意味し、その結果を「クラスタ」と定義する。点群をクラスタリングした結果は、点群の集合となる。また、「領域」とは、ある物体が存在する３次元空間中の範囲とし、同一の物体であると判定された点群の集合の存在する範囲とする。「自己相関」もしくは「自己相関値」とは、ある特定の領域内の物理的な形状や波形を特定の方向に沿ってずらしたときの形状の類似度（相関値）を意味する。３次元点群においては、ある特定の範囲に含まれる点群形状を、ある特定の方向や規則に沿ってずらした部分的な形状（本発明の実施の形態では特に断面）と比較したときの類似度を意味する。
【００３５】
[実施の形態]
（領域分割処理装置全体の説明）
【００３６】
次に、本発明の実施の形態に係る点群解析による領域分割処理装置の構成について説明する。図４に示すように、本発明の実施の形態に係る点群解析による領域分割処理装置１００は、ＣＰＵと、ＲＡＭと、後述する点群解析処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この点群解析による領域分割処理装置１００は、機能的には、記憶部１０３と、標識検出部１０４とを含んで構成されている。また、領域分割処理装置１００には、被写体計測部１０１と、入力部１０２とが接続されている。
【００３７】
被写体計測部１０１は、物体の表面上の位置を計測した計測結果である複数の位置を表す３次元点群を計測するものであり、３次元点群を計測する装置は、レーザーレンジファインダや、赤外線センサ、または超音波センサなど、被写体とセンサとの距離を測定可能な装置である。例えば、レーザーレンジファインダをＧＰＳ（Global Positioning System）を搭載された車の上、もしくはＧＰＳの搭載された飛行機に搭載し、移動しながら計測することで、屋外の環境の地物を被写体とし、例えばケーブル、建物、ガードレール、道路地面などであり、これら被写体表面の３次元位置を計測するシステムである。本実施の形態では、被写体計測部１０１として、車上にＧＰＳとレーザーレンジファインダとが搭載されているＭＭＳ（Mobile Mapping System）を想定している。ただし、被写体計測部１０１は、ある特定の位置（交差点など）１箇所からの計測できる距離計測可能な装置で計測された３次元点群であっても、本発明を適用することは可能である。
【００３８】
入力部１０２は、マウスやキーボードなどのユーザーインターフェースであり、点群解析による領域分割処理装置１００で使用するパラメータを入力するものである。また、パラメータを記憶したＵＳＢメモリなどの外部記憶媒体でもよく、記憶部１０３にパラメータを供給する。例えば、パラメータには、地図上の柱状構造物の位置情報などが登録されている。
【００３９】
記憶部１０３は、３次元点群記憶部１１０と、演算処理用パラメータ記憶部１１１と、領域分割結果記憶部１１２と、を含んで構成されている。３次元点群記憶部１１０は、被写体計測部１０１から３次元点群情報を取得し、領域統合処理部１０４に供給する。演算処理用パラメータ記憶部１１１は、入力部１０２からパラメータの値を取得し、領域統合処理部１０４に供給する。領域分割結果記憶部１１２は、領域統合処理部１０４から出力される領域分割結果が存在する３次元位置や３次元空間の領域、もしくは検出した３次元点群の番号などの情報を記憶する。これら３つの手段により構成される記憶部１０３は、例えば、ＨＤＤ（Hard Disk Drive）や、ＳＳＤ（Solid State Drive）等のハードウェアによる記憶装置である。
【００４０】
領域統合処理部１０４は、代表点群決定部１２１と、規定断面形状存在判定部１２２と、規定断面形状生成部１２３と、規定断面統合部１２４とを含んで構成される。領域統合処理部１０４は、記憶部１０３から供給された３次元点群を入力として、押し出し形状領域を構成する規定断面形状を検出し、検出した規定断面形状を統合し、統合結果を領域統合結果として記憶部１０３の領域分割結果記憶部１１２へ出力する。
【００４１】
（領域統合処理部１０４の動作説明）
【００４２】
まず、本実施例の領域分割処理装置１００による領域統合処理部１０４全体の処理について図５を参照して説明する。
【００４３】
（ステップＳ１：代表点群決定）
【００４４】
ステップＳ１では、代表点群決定部１２１によって、３次元点群から、３次元点における平面度合い及び密度に基づいて、物体の高自己相関断面形状を求めるための代表点群を決定する。ここでは、ある一定の間隔や点数ごとに、曲率の変化が大きい領域の中から処理対象とする注目点を決定し、決定した複数の注目点（以降、代表点群と呼ぶ）の位置情報をステップＳ２へ出力する。
【００４５】
ここで代表点群とは、ステップＳ２以降で検出する既定断面形状について、その存在判定処理を行うときの注目点という意味とする。また、従来技術の課題でも説明したが、領域分割の精度低下の要因の一つは、従来技術では推定精度が低い曲率の変化が大きい領域、つまり平面でない領域である。そこでステップＳ１においては、平面度（誤差）を算出し、局所領域内での３次元点の点群密度及び平面度を考慮して、密度が高く、かつ、平面度が低い３次元点を優先して代表点のリサンプリング処理を行う。
【００４６】
また、本ステップＳ１は、領域分割の精度を落とさずに、計算量の削減するために行われる。物体の境界付近、例えば柱状構造物と樹木が接する位置において、既定断面形状を検出することは、柱状構造物単体で存在する場合に比べて難しい。そのため、物体同士の境界近くに存在する点を避けつつ、入力点群をリサンプリングして代表点群を決定することが望ましい。
【００４７】
境界付近の点を避けて物体内部の点を選択する方法は、例えば、領域を過分割して、その過分割された領域の重心の位置を代表点群の位置としてもよいし、また３次元空間における密度推定を行い、局所的な密度の最大値の場所（極大値の３次元位置）を代表点群としてもよい。
【００４８】
以上のように、本実施の形態においては、平面度合と密度の２つの指標を用いたリサンプリング処理によって、代表点群を決定する。
【００４９】
入力点群を区別する番号をｉ、点群の総数をＮｉとすると、各３次元点の３次元位置は以下（１）式により表現する。
【００５０】
【数１】
0006397386.tif 000002
【００５１】
ただし、[ｘｉ，ｙｉ，ｚｉ］は、Ｘ，Ｙ，Ｚ軸の座標成分を意味し、右上の添え字の記号「Ｔ」は転置を意味とする。また、数式の記号の説明をすると記号「・」は、数値の掛け算もしくはベクトル間の内積を意味し、記号「×」はベクトルの外積、記号「←」は変数に値を代入することを意味する。
【００５２】
次に、図６を参照して、ステップＳ１の詳細なフローを説明する。
【００５３】
ステップＳ１−１では、まず、入力された３次元点群のすべてについて、密度推定および平面上の点であるかの判定を行う。注目点ｐｉについて、半径ｒ以内の距離を局所領域と定義し、この局所領域内部の点をｐｊ（ｊ∈１，２，３，…，Ｎｊ）、局所領域内の点群の総数を
【００５４】
【数２】
0006397386.tif 000003
【００５５】
と表記する。
【００５６】
半径ｒ以内の距離に含まれる点は、次の（２）式を満たす点として求められる。
【００５７】
【数３】
0006397386.tif 000004
【００５８】
ただし、記号「｜｜  ｜｜」はベクトルの２ノルムを意味する。このとき注目点ｐｉの密度Ｄｅｎｓｅ（ｐｉ）は次の（３）式により求まる。
【００５９】
【数４】
0006397386.tif 000005
【００６０】
平面度の算出は、以下（４）式に示す局所領域内の点群の平面近似誤差ＥｒｒＰｌａｎｅにより行われる。
【００６１】
【数５】
0006397386.tif 000006
【００６２】
ただし、
【００６３】
【数６】
0006397386.tif 000007
【００６４】
は注目点ｐｉの局所領域の点群の重心位置であり、ｎｉは局所領域の点群を平面近似したときの法線方向である。法線方向ｎｉは、共分散行列Ｐを固有値分解したときの第３固有値（一番小さい固有値）に対応する固有ベクトルが法線ベクトルである。共分散行列Ｐは次の（５）式により求まる。
【００６５】
【数７】
0006397386.tif 000008
【００６６】
次に、ステップＳ１−２において、仮代表点群を求めるためにリサンプリング処理を行う。最終的に出力する代表点群のリサンプリング距離ｄｒｅｓａｍｐとすると、平面度合の低い点、つまり平面近似誤差の大きい点群から優先して、リサンプリング距離ｄｒｅｓａｍｐごとに点群を間引き、残りの点群を代表候補点群とする。これは、平面以外の形状でも精度よくクラスタリングするため、平面以外の点を優先的に代表点に設定するためである。
【００６７】
ここで、点群を間引くことは、具体的には以下のように行う。まず点群を平面近似誤差の大きな順番になるように点群の番号を付け直す。次に、点群を区別する番号をｉ，注目点ｐｉからリサンプリング距離以内に含まれる周辺点群ｐｊとすると、注目点ｐｉについて仮リサンプリング距離ｄｒｅｓａｍｐに含まれる周辺点群について、以下（６）式に示すように、注目点の平面近似誤差平面近似誤差ＥｒｒＰｌａｎｅ（ｐｉ）よりも平面近似誤差ＥｒｒＰｌａｎｅ（ｐｊ）が小さいとき、該当する周辺点群を除去する。
【００６８】
【数８】
0006397386.tif 000009
【００６９】
ただし、一度間引かれた点については上記処理を行わない。
【００７０】
ステップＳ１−２では、最終的に、上記の間引き処理が終わったときに、除去されずに残っている点群を代表候補点群として出力する。
【００７１】
次に、ステップＳ１−３において、代表点群を求めるために、代表候補点群から近傍の密度局大点の検出処理を行う。代表候補点群を区別する番号をｉ、注目点ｐｉから極大密度推定距離ｄｄｅｎｓｅ以内の周辺点群ｐｊについて、注目点の密度を指標として最大密度となる点を代表点とする。
【００７２】
具体的には、注目点の密度Ｄｅｎｓｅ（ｐｉ）よりも局所領域に含まれる点の密度Ｄｅｎｓｅ（ｐｊ）が小さいとき、該当する周辺点について代表候補点群から除去する。
【００７３】
【数９】
0006397386.tif 000010
【００７４】
ステップＳ１−３では、上記処理を代表候補点群の全てについて処理した後に、代表候補点として残っている点群を代表点群と判定し、決定した代表点群をステップＳ２へ出力する。なお、ステップＳ１において、局所領域を定義するための半径ｒとリサンプリング距離ｄｒｅｓａｍｐ、ｄｄｅｎｓｅは実験的に決めるパラメータであり、本実施の形態においてはｒ＝０．２［ｍ］、ｄｒｅｓａｍｐ＝０．２［ｍ］、ｄｄｅｎｓｅ＝０．０５［ｍ］とした。
【００７５】
（ステップＳ２：規定断面形状存在の判定）
【００７６】
ステップＳ２では、規定断面形状存在判定部１２２によって、代表点群に含まれる代表点の各々について、代表点の周辺点群の３次元形状が、ある特定の３次元方向に繰り返される断面形状（押し出し形状を規定する断面、以下では規定断面と呼ぶ）を有するか否かを判定する。本発明の実施の形態においては、繰り返される形状の定義として自己相関値が高いことと定義していることが特徴である。図７に示すステップＳ２の処理は、各代表点群について独立して処理をしてもよいし、代表点群の密度の大きい順に処理をしてもよい。
【００７７】
代表点群を区別する番号をｉとし、注目代表点ｐｉから半径Ｒ以内に含まれる点群を周辺点群ｐｊ（ｊ∈１，２，３，．．，Ｎｊ（Ｒ））、この周辺点群の総数をＮｊ（Ｒ）とし、この周辺点群を用いて推定する。ただし、半径Ｒは演算処理用パラメータ記憶部１１１に登録されているパラメータであり、本実施の形態ではＲ＝０．５［ｍ］とした。
【００７８】
（ステップＳ２−１：高相関となる押し出し方向の推定）
【００７９】
ステップＳ２−１では、以下に説明するように、注目代表点ｐｉ位置における押し出し方向を推定する。図８にステップＳ２−１の詳細なフローに示す。ステップＳ２−１では、複数回推定した押し出し方向の中から、押し出し方向として最適なものを、複数生成した断面形状の相関値を指標として決定する。例えば、図９に示すような電柱（円筒）を例にすると、ある特定の方向に一定の間隔で生成したときのみ円形が重複する、一方、それ以外の方向のときは、全て楕円形となるが重複した形状とならない。この重複した断面形状の有無を、断面形状から生成した断面形状ベクトルの相関値を用いて推定する。
【００８０】
（ステップＳ２−１−１：サンプリング）
【００８１】
ステップＳ２−１−１において、注目代表点から特定の距離に含まれる周辺点群に基づいて自己相関算出方向を決定する。ここでは、注目代表点群ｐｉの周辺点群ｐｊ（ｊ∈１，２，３，．．，Ｎｊ（Ｒ））からサンプリングして自己相関算出方向（押し出し方向）を決定する。サンプリングとは、ランダムに（規則性なく）点を選択することを意味する。本発明の実施の形態においては、方向を決定するため2点をサンプリングすれば十分である。周辺点群の中から、ランダムに選択した２点の番号をｊ１、ｊ２と表記すると、ステップＳ２−１の繰り返し処理Ｌｏｏｐ回目の自己相関算出方向ｍ（Ｌｏｏｐ）は次の（８）式により求まる。
【００８２】
【数１０】
0006397386.tif 000011
【００８３】
なお、右上の添え字（Ｌｏｏｐ）は、繰り返し処理の回数の変数Ｌｏｏｐを意味する。
【００８４】
ここで、ランダムに選択する方法に限定はない。例えば、次の（９）式により、周辺点群の番号Ｎｏを選択できる。
【００８５】
【数１１】
0006397386.tif 000012
【００８６】
ただし、ｒａｎｄ（）は乱数を発生する関数である。例えば、メルセンヌ・ツイスタという擬似乱数生成器を用いればよい。関数ｍｏｄ（ｘ，ｙ）は、実数ｘを整数ｙで割り算したときの余りを出力する関数とする。サンプリングの数が２点の場合、上記の関数ｍｏｄを用いて、番号を２回出力すればよい。
【００８７】
（ステップＳ２−１−２：複数断面の相関値計算）
【００８８】
ステップＳ２−１−２では、以下に説明するように、自己相関算出方向における、周辺点群を用いた複数の断面形状画像を生成し、自己相関算出方向において、代表点を基準とする周辺点群の３次元形状から推定された断面形状ベクトルの自己相関値を算出する。
【００８９】
まず、ステップＳ２−１−１において求めた自己相関算出方向ｍ（Ｌｏｏｐ）を用いて、代表点および半径その周辺の点群ｐｊ（ｊ∈１，２，３，．．，Ｎｊ（Ｒ））について複数の断面を作成する。ここで断面とは、物理的には３次元物体を横切ったときに生成される、切り口の形状（表面の形状）を意味する。本発明の実施の形態においては、ＭＭＳで計測した場合３次元物体の表面は離散的に計測されるため、自己相関値算出方向（押し出し方向）に垂直な平面近傍の点群を用いて生成される形状を意味する。この断面形状画像から断面形状ベクトルを生成し、自己相関値を計算する。
【００９０】
複数の断面の作成にあたり、まず、各周辺点ｐｊについて、サンプリング方向に沿った位置（距離）により、どの断面ｓ（∈１，２，．．，Ｎｓ）に属するか、つまり断面作成に使用する近傍点かを決める。各周辺点ｐｊが属する断面形状画像の番号ｓは次の（１０）式により決定する。
【００９１】
【数１２】
0006397386.tif 000013
【００９２】
ここで、ｓｔｅｐＺは断面形状画像の存在する平面を設定する間隔（距離）であり、分割数Ｎｓにより決定される。
【００９３】
本実施の形態においては、ＭＭＳのレーザースキャンラインの間隔が高速道路では車の走行速度に応じて長くなり、最大２０ｃｍまで長くなることを考慮し、半径Ｒ＝０．５［ｍ］、Ｎｓ＝５とした。
【００９４】
次に、断面形状画像を生成する。断面形状画像Ｉｓは、自己相関算出方向ｍ（Ｌｏｏｐ）のベクトルに垂直な平面の基底ベクトルを、
【００９５】
【数１３】
0006397386.tif 000014
【００９６】
とすると、周辺点ｑｊｃについて断面形状画像の画素位置は、次の（１１）式により
【００９７】
【数１４】
0006397386.tif 000015
【００９８】
として求まる。
【００９９】
【数１５】
0006397386.tif 000016
【０１００】
ただし、関数ｒｏｕｎｄ（）は、入力した実数値の小数点を四捨五入することを意味し、Δｄは画像座標を求める際の量子化の幅である。本実施例ではΔｄ＝０．０２（ｍ）とする。
【０１０１】
このとき、断面形状画像Ｉｓは、画素の位置
【０１０２】
【数１６】
0006397386.tif 000017
【０１０３】
について次の（１２）式により更新を行う。
【０１０４】
【数１７】
0006397386.tif 000018
【０１０５】
最後に断面形状ベクトルを用いて相関値を計算する。断面形状ベクトルとは、断面形状画像をラスタースキャンして生成される1次元のベクトルとする。また、自己相関値の指標について、本発明の実施の形態においては、隣接物の影響を抑制するために、条件の厳しい指標と条件の緩和した指標の複数の指標を用いる。
【０１０６】
条件の厳しい指標とは、注目代表点の位置における基準断面が、それ以外の断面全てにおいて高い相関値を有しているか、信頼性の高さを判定する基準として用いる。条件の緩和した指標とは、注目代表点の位置における基準断面が人工物の断面の可能性があるかどうか判定する指標として用いる。
【０１０７】
信頼性の高い指標として、複数断面の相関値Ｅｈａｒｄを次の（１３）式で計算する。
【０１０８】
【数１８】
0006397386.tif 000019
【０１０９】
ここで、断面形状ベクトルとは、断面形状画像Ｉｔに記号「→」をつけたものとする。ただし、記号「→」がついたベクトルは、ノルムが１．０に正規化されているとする。例えば、ベクトルの２ノルムの大きさで割り算すれば、ノルムは１．０に正規化される。また、ラスタースキャンの代わりに、画像を２次元行列と考え、ある一定の規則により１次元のベクトルにしたものでもよい。
【０１１０】
上記（１３）式は、人工物など押し出し形状方向に共通の断面形状を有する物体においては高い値をとる。しかし、図２に示すような例において、複数の物体が隣接する状況、つまり点ｐ１と点ｐ２の位置に近い代表点においては、相関値が低くなる傾向がある。
【０１１１】
そこで、人工物の断面の可能性を調べる指標として、複数断面の相関値Ｅｓｏｆｔを次の（１４）式もしくは（１５）式で計算する。
【０１１２】
【数１９】
0006397386.tif 000020
【０１１３】
これにより、オクルージョンに部分的に欠けた領域が存在する場合や、付属品により一部の断面形状が類似した断面形状でない場合でも、指標Ｅｓｏｆｔでは大きな値が得られる。
【０１１４】
（ステップＳ２−１−３：  押し出し方向群候補の保存）
【０１１５】
ステップＳ２−１−３において、複数断面の自己相関値が高くなる押し出し方向群Ｍを保存する。
【０１１６】
厳しい指標での相関値が次の（１６）式を満たすとき、当該自己相関算出方向を、押し出し方向群Ｍｈａｒｄとして保存する。
【０１１７】
【数２０】
0006397386.tif 000021
【０１１８】
また、緩和された指標での相関値が次の（１７）式を満たすとき、当該自己相関算出方向を、押し出し方向群Ｍｓｏｆｔとして保存する。
【０１１９】
【数２１】
0006397386.tif 000022
【０１２０】
ただし、閾値ＴＨｈａｒｄと閾値ＴＨｓｏｆｔは実験的に決めるパラメータであり、本実施の形態においてＴＨｈａｒｄ＝０．６、閾値ＴＨｓｏｆｔ＝０．５とした。
【０１２１】
また、本実施の形態においては、異なる２つの指標を用いたが、同一の指標を用いつつも閾値を変えて、厳しい条件および緩和された条件と複数用意することにより同様の効果が期待できる。例えば、複数相関値の指標Ｅｈａｒｄを用いて、厳しい条件の指標を次の（１８）式のように設定し、
【０１２２】
【数２２】
0006397386.tif 000023
【０１２３】
緩和された条件の指標を次の（１９）式のように設定してもよい。
【０１２４】
【数２３】
0006397386.tif 000024
【０１２５】
（ステップＳ２−１−４：  繰り返し処理の判定）
【０１２６】
ステップＳ２−１−４において、繰り返し処理を閾値ＴｈＬｏｏｐ回以上行った場合、繰り返し処理を終了する。繰り返し処理の回数がＴｈＬｏｏｐ未満の場合は、ステップＳ２−１−５において繰り返し変数Ｌｏｏｐ←Ｌｏｏｐ＋１としてから、ステップＳ２−１−１へ戻る。本実施の形態において、閾値ＴｈＬｏｏｐ＝２００とした。
【０１２７】
（ステップＳ２−２：規定断面存在判定）
【０１２８】
ステップＳ２−２において、ステップＳ２−１−２で算出した複数の断面形状ベクトルの相関値に基づいて、高自己相関断面形状を有するか否かを判定する。ここでは、注目代表点群ｐｉの位置における押し出し方向群によって規定される自己相関値の高低により、高相関の断面形状を有するか有しないか判定する。
【０１２９】
まず、ステップＳ２−１において出力された押し出し方向群について、厳しい指標での押し出し方向群Ｍｈａｒｄが存在しているとき、自己相関値の高い断面形状（高相関規定断面）が存在すると判定し、押し出し方向群としてＭｈａｒｄを出力する。
【０１３０】
【数２４】
0006397386.tif 000025
【０１３１】
次に、厳しい指標での押し出し方向群Ｍｈａｒｄが存在しない場合であって、緩和された指標での押し出し方向群Ｍｓｏｆｔが存在する場合、自己相関値の低い断面形状（低相関規定断面）が存在すると判定し、押し出し方向群としてＭｓｏｆｔを出力する。
【０１３２】
【数２５】
0006397386.tif 000026
【０１３３】
ステップＳ３へは、押し出し方向群Ｍと規定断面の判定結果を出力する。
【０１３４】
（ステップＳ３：規定断面形状生成）
【０１３５】
ステップＳ３では、規定断面形状生成部１２３によって、ステップＳ２により高相関の断面形状を有すると判定された代表点の各々について、押し出し方向群と、当該代表点の周辺点群とに基づいて、規定断面形状を生成する。
【０１３６】
ステップＳ２で規定断面が存在すると判定された代表点の各々において、当該代表点ごとに推定した押し出し方向群Ｍについて、各押し出し方向に該当する断面形状点を決定する。図１０に示すように、ステップＳ２においては、半径Ｒに含まれる点群を用いて断面の相関値を計算していたため、個々の点についてノイズであるか真の断面を構成する点であるか判定はしていなかった。
【０１３７】
具体的には、代表点における押し出し方向ｍについて、代表点が属する断面形状画像において各画素が有効な断面点であるか判定処理を行う。ステップＳ３における断面点生成処理フローの概要を図１１に示す。
【０１３８】
（ステップＳ３−１：注目代表点の選定）
【０１３９】
ステップＳ３−１において、処理する注目代表点を決める。ここで、注目代表点を決めるとは、例えば入力された代表点群について処理する番号を選択することを意味する。本実施例では、各代表点については独立して処理を行うこととするが、例えば密度の大きい順番に代表点を選択するように、逐次的に注目点を選定してもよい。
【０１４０】
（ステップＳ３−２：規定断面群の生成）
【０１４１】
ステップＳ３−２では、以下に説明するように、注目代表点の属する断面形状画像の部分断面画像の各々について、部分断面ベクトルの自己相関値を算出し、断面形状画像の各画素が有効であるか否かを判定して、規定断面形状を生成する。部分断面ベクトルの自己相関値が高いときに有効点と判定する。
【０１４２】
ここでは、注目代表点における押し出し方向群Ｍの方向ごとに規定断面形状を生成する。図１２を参照してステップＳ３−２の詳細なフローを説明する。
【０１４３】
ステップＳ３−２−１において、押し出し方向ｍｗ（ｗ＝１，２，３，．．，Ｗ）を選定する。本発明の実施の形態においては、ｗ＝１，２，３，．．，Ｗと逐次的に処理を行う。
【０１４４】
ステップＳ３−２−２において、注目代表点における押し出し方向ｍｗについて有効断面点を推定し、規定断面形状を生成する。ここで、有効断面点とは、注目代表点の属する断面形状画像の画素であって、当該画素を中心とした局所領域（スケールの小さな領域）での部分断面画像における部分断面ベクトルの自己相関値の高い画素と定義する。断面形状ベクトルと同様に、部分断面ベクトルは、部分断面画像をラスタースキャンすることによって生成されたベクトルについて、ノルムを１に正規化したベクトルとする。
【０１４５】
以下、注目代表点が属する断面形状画像に含まれる全ての画素について処理を行う。
【０１４６】
まず、注目画素［ｘｊ，ｙｊ］位置から半径Ｒｓｍａｌｌ以内の画素の領域を部分断面画像
【０１４７】
【数２６】
0006397386.tif 000027
【０１４８】
と定義する。
【０１４９】
このとき、注目代表点が属していない複数の断面形状画像について、同様に画素位置［ｘｊ，ｙｊ］位置から半径Ｒｓｍａｌｌ以内の画素の領域を用いて、部分断面画像Ｉｓを設定する。
【０１５０】
部分断面画像
【０１５１】
【数２７】
0006397386.tif 000028
【０１５２】
とそれ以外の部分断面画像Ｉｓについて、次の（２０）式により自己相関値を求めることで、注目画素が有効断面点であるか判定を行う。図１３に、部分断面画像における部分断面ベクトルの自己相関値の概念図を示す。
【０１５３】
【数２８】
0006397386.tif 000029
【０１５４】
ここで、ＴＨｓｕｂｒｅｇｉｏｎは有効断面点であるか判定する閾値であり、本実施の形態においてはＴＨｓｕｂｒｅｇｉｏｎ＝０．４とした。
【０１５５】
そして、有効断面点と判定された画素の点の集合として規定断面形状を求める。規定断面形状
【０１５６】
【数２９】
0006397386.tif 000030
【０１５７】
は次の（２１）式の集合により求まる。
【０１５８】
【数３０】
0006397386.tif 000031
【０１５９】
ただし、ｆｊは画素位置［ｘｊ，ｙｊ］を３次元座標位置に変換したベクトルを意味する。注目代表点の位置をｐｉ、断面形状画像を作成するときに使用した画像座標系でのＸ座標とＹ座標の方向をｍＸｗ，ｍｙｗと表現すると、ｆｊは次の（２２）式で求まる。
【０１６０】
【数３１】
0006397386.tif 000032
【０１６１】
ステップＳ３−２−３において、全ての押し出し方向について処理が終わったら、注目代表点の規定断面形状群を出力する。全ての押し出し方向の処理が終了していないときは、ステップＳ３−２−１へ戻り次の押し出し方向を選択して処理を繰り返す。
【０１６２】
（ステップＳ３−３：ステップＳ３の終了判定）
【０１６３】
すべての注目代表点について処理を行っていない場合、ステップＳ３−１へ戻り次の注目代表点を選択して処理を繰り返す。全ての注目代表点について処理を行った場合、ステップＳ３を終了し、注目代表点ごとに推定した規定断面形状群を出力する。
【０１６４】
（ステップＳ４：規定断面統合処理）
【０１６５】
ステップＳ４では、規定断面統合部１２４によって、代表点の各々について、代表点を注目代表点とし、注目代表点の押し出し方向と、周辺の代表点の押し出し方向とのペアのうち、類似した押し出し方向のペアごとに求めた規定断面形状の重複強さに基づいて、注目代表点と周辺の代表点との間にリンクを構築し、リンクが構築された代表点群を同一のクラスタと判定して、同一のクラスタの代表点群の規定断面形状を統合する。
【０１６６】
ここで、注目する代表点の押し出し形状領域と周辺の代表点群の押し出し形状領域の重複強さを定義し、この重複強さを指標として統合処理を行う。統合処理とは、具体的には注目する代表点と周辺の代表点についてリンクを設定する処理を意味し、リンクが構築された代表点群は同一の領域であると判定する処理を意味する。
【０１６７】
図１４にステップＳ４の断面統合処理フローを示す。
【０１６８】
（ステップＳ４−１：押し出し領域との統合）
【０１６９】
ステップＳ４−１では、処理対象とする注目代表点を決める。ステップＳ２において人工物の可能性の高い代表点を推定したが、ノイズや隣接物の影響により誤って非人工物（例えば樹木の葉）を押し出し形状物と判定していることもある。そこで、ステップＳ４の処理では、注目代表点とは、高い相関値を持つ代表点とし、この注目代表点と重複した断面をもつ代表点についてのみ統合を行う。
【０１７０】
ただし、高い相関を持つ各注目代表点については、独立して処理をしてもよいし、逐次的に処理をしてもよい。
【０１７１】
ステップＳ４−２では、以下に説明するように、注目代表点と周辺代表点について、類似した押し出し方向のペアで求めた規定断面形状の重複強さによりリンクを設定する。図１５に規定断面におけるリンク設定処理フローを示す。
【０１７２】
（ステップＳ４−２−１：注目する周辺代表点の選択）
【０１７３】
まず、ステップＳ４−２−１では、注目代表点Ａにおける周辺代表点を１つ選択する。
【０１７４】
本実施の形態において、注目代表点Ａについて、近傍の代表点群のｋＡ個を周辺代表点とする。ここで、近傍の代表点数ｋＡは実験的に決めるパラメータであり、本実施例においてはｋＡ＝１０とした。ただし、例えばｋ近傍とは、注目する点の位置から３次元の距離が近い順にならべたときの上位ｋ個ことを意味するとする。本実施例においては、周辺代表点を距離が近い順に選択するとする。
【０１７５】
（ステップＳ４−２−２：重複強さの算出）
【０１７６】
次に、ステップＳ４−２−２では、注目代表点Ａと選択された周辺代表点Ｂとの組み合わせについて、規定断面形状の重複強さＥｏｖｅｒｌａｐを算出する。本実施の形態においては、ｋＡ近傍に存在する２つの代表点が同一の物体に属するときには、２つの代表点のそれぞれの位置について同一方向で、かつ類似した規定断面形状が存在していると仮定している。
【０１７７】
そこで、注目代表点Ａの位置ベクトルｐＡと周辺代表点Ｂの位置ベクトルをｐＢとすると、それぞれの押し出し方向群ＭａとＭｂについて、まず類似方向ペアを求め、それぞれの類似方向のペアごとに規定断面形状の類似度を計算し、類似度が大きいときには、注目代表点Ａと周辺代表点Ｂとの間にリンクを設定し、統合を行う。
【０１７８】
ここで、代表点群はリサンプリングされて距離が離れているため、注目代表点と周辺代表点の規定断面形状同士が完全に同じ形状になることは少ない。本実施の形態においては、リサンプリングされた代表点群の規定断面形状のずれを考慮し、連結度を規定断面が重複しているかどうか、つまり断面が重なるかどうか（重複度合）を計算する。
【０１７９】
注目代表点Ａと周辺代表点Ｂについて、それぞれの押し出し方向ｍａ（∈Ｍａ）とｍｂ（∈Ｍｂ）を類似した押し出し方向ペアとすると、規定断面形状の重複強さＥｏｖｅｒｌａｐ（Ａ；Ｂ）（０＜Ｅｏｖｅｒｌａｐ＜１）を次の（２３）式で求める。
【０１８０】
【数３２】
0006397386.tif 000033
【０１８１】
ここで、
【０１８２】
【数３３】
0006397386.tif 000034
【０１８３】
は注目代表点Ａの規定断面形状を、
【０１８４】
【数３４】
0006397386.tif 000035
【０１８５】
は周辺代表点Ｂの規定断面形状を意味し、
【０１８６】
【数３５】
0006397386.tif 000036
【０１８７】
は周辺代表点Ｂの規定断面形状を構成する規定断面点、つまり、ステップＳ３−２−２で求めた有効断面点を意味する。
【０１８８】
【数３６】
0006397386.tif 000037
【０１８９】
は、物理的には周辺代表点Ｂの規定断面点
【０１９０】
【数３７】
0006397386.tif 000038
【０１９１】
について、注目代表点Ａの規定断面形状
【０１９２】
【数３８】
0006397386.tif 000039
【０１９３】
へ押し出し方向ｍａで射影した時の最短距離を意味する。関数Ｃｏｕｎｔは規定断面点
【０１９４】
【数３９】
0006397386.tif 000040
【０１９５】
が規定断面形状Ａと重複しているときは１をそれ以外は０を出力する関数であり、関数ＳｉｍＣＳは規定断面形状Ｂを構成する規定断面点
【０１９６】
【数４０】
0006397386.tif 000041
【０１９７】
が規定断面形状Ａに重複する割合を算出する関数である。
【０１９８】
また、押し出し方向ｍａ（∈Ｍａ）とｍｂ（∈Ｍｂ）について、下記（２４）式を満たすとき類似方向と見なし、類似する押し出し方向ペアと判定する。
【０１９９】
【数４１】
0006397386.tif 000042
【０２００】
δｓは規定断面点
【０２０１】
【数４２】
0006397386.tif 000043
【０２０２】
が規定断面形状Ａと重複するか判定するための距離の閾値パラメータであり、本実施の形態ではδｓ＝０．０３［ｍ］とした。δａｎｇｌｅは、類似する押し出し方向のペアであるか判定するための角度の閾値パラメータであり、本実施例ではδａｎｇｌｅ＝１５［度］とした。上記式（２４）を満たすペアが存在しない場合には、重複強さＥｏｖｅｒｌａｐは０となる。
【０２０３】
（ステップＳ４−２−３：リンク設定処理）
【０２０４】
ステップＳ４−２−３では、次の（２５）式を満たすとき、注目代表点Ａと周辺代表点Ｂとの間にリンクを設定する。
【０２０５】
【数４３】
0006397386.tif 000044
【０２０６】
ただし、ＴＨｏｖｅｒｌａｐは実験的に決めるパラメータであり、本実施例においてはＴＨｏｖｅｒｌａｐ＝０．３とした。
【０２０７】
上記（２２）式で定義した重複強さと相関値の違いを記載すると、相関値は２つの比較形状の類似度を計算するため、部分的にしか類似していないときには小さい値を出力する。一方、重複強さの場合には、部分的であっても一定以上の大きさで類似した部分が存在していれば大きな値を出力し、かつ片方の規定断面形状が他方の形状を包含するときは、最大値である１．０に近い値を出力できる。
【０２０８】
例えば、図３のように平面押し出し領域Ｃやコーナー部分の押し出し領域Ｂについて、規定断面形状はそれぞれ異なる形状であるが、重複している領域が存在するときに重複強さを利用することは有効である。また、本発明の実施の形態では、代表点がリサンプリングされており、押し出し領域Ｂの中でもずれが生じることがあるため、重複強さを指標としてリンクを設定する。
【０２０９】
（ステップＳ４−２−４：注目代表点におけるステップＳ４−２の終了判定）
【０２１０】
ｋＡ近傍すべての周辺代表点について処理を行っていない場合、ステップＳ４−２−１へ戻り、処理を行っていない周辺代表点を選択する。全ての周辺代表点について処理を行った場合、注目代表点についてステップＳ４−２を終了する。
【０２１１】
（ステップＳ４−３：ステップＳ４の終了判定）
【０２１２】
すべての注目代表点について処理を行っていない場合、ステップＳ４−１へ戻る。全ての注目代表点について処理を行った場合、ステップＳ４−４へリンクを設定した代表点群を出力する。
【０２１３】
（ステップＳ４−４：統合処理）
【０２１４】
リンクが構築された代表点を同一のクラスタと判定し、統合された代表点の周辺点群がどの領域に含まれるのか判定処理を行う。リンクが構築された代表点は統合できるが、この段階では代表点以外の入力された３次元点群は、どの領域に属するか不明である。
【０２１５】
そこで、統合された代表点について、代表点の規定断面形状群を用いて、周辺点群へ統合された代表点のクラスタの番号を付与する。例えば、代表点の総数が５、ステップＳ４−３の出力で番号１と３と５についてリンクが張られており、番号２と４の代表点にリンクが張られているとすると、クラスタの総数は２である。クラスタの番号は任意の規則で決めて良いが、本実施の形態ではクラスタに含まれる代表点の数が多い順につけるとした。同数のクラスタに対しては、最も数字が小さい代表点の番号を含むものから番号を付与した。
【０２１６】
ある注目点を規定断面形状の押し出し方向に射影したとき、その注目点が規定断面形状上に射影される場合、最も距離の近い規定断面形状の代表点のクラスタの番号を、当該注目点に付与する。図１６にリンクが構築された代表点群の一例を示す。例えば、図１６（Ｃ）の例では、距離が短いｄ１（＜ｄ２）の規定断面形状の代表点のクラスタに注目点は属すると判定する。
【０２１７】
具体的には、３次元群の各３次元点を注目点ｑとし、注目点ｑの半径Ｒｑ以内に存在し、かつ注目点ｑからｋｑ近傍の代表点を用いて、所属するべき代表点を求める。次に、所属すべき代表点のクラスタ番号を注目点ｑに付与することで、最終的な統合領域が求まる。
【０２１８】
注目点の属する代表点ｂｅｌｏｎｇ（ｑ）は次の（２６）式で求まる。
【０２１９】
【数４４】
0006397386.tif 000045
【０２２０】
ただし、ｐｒｏｊｄｉｓｔ（ＭＢ；ｑ）は近傍代表点の一つである近傍代表点Ｂにおける規定断面形状群に射影したときの最短距離を出力する関数とする。
【０２２１】
周辺代表点Ｂにおける押し出し方向をｍｂ（∈ＭＢ）とすると、次の（２７）式で求まる。
【０２２２】
【数４５】
0006397386.tif 000046
【０２２３】
ただし、規定断面形状上に射影される点とは、下記（２８）に示すように距離誤差ｅｒｒｄｉｓｔが閾値未満の点とする。
【０２２４】
【数４６】
0006397386.tif 000047
【０２２５】
ここで、注目点ｑの所属する番号は、代表点の番号がｂｅｌｏｎｇ（ｑ）の代表点が属するクラスタ番号となる。半径Ｒｑ、近傍の数ｋｑ、及びＴｈｅｒｒｏｒｄｉｓｔは実験的に決めるパラメータであり、本実施の形態においてはｋｑ＝２、半径Ｒｑ＝０．５［ｍ］、Ｔｈｅｒｒｏｒｄｉｓｔ＝０．０３［ｍ］とした。
【０２２６】
以上説明したように、本発明の実施の形態に係る領域分割処理装置によれば、代表点群決定部１２１が、３次元点群から、３次元点における平面度合い及び密度に基づいて、代表点群を決定し、規定断面形状存在判定部１２２が、代表点群に含まれる代表点の各々について、高自己相関断面形状を有するか否かを判定し、規定断面形状生成部１２３が、高自己相関断面形状を有すると判定された代表点の各々について、押し出し方向と、代表点の周辺点群とに基づいて、規定断面形状を生成し、規定断面統合部１２４が、生成された規定断面形状に基づいて、押し出し方向及び規定断面形状の類似度を指標として、規定断面形状を統合し、３次元点群から、統合された規定断面形状が表す押し出し形状領域に含まれる点群を検出することにより、隣接する構造物が存在する場合でも、精度よく、点群領域を分割できる。
【０２２７】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【０２２８】
１００ 領域分割処理装置
１０１ 被写体計測部
１０２ 入力部
１０３ 記憶部
１０４ 領域統合処理部
１１０ 次元点群記憶部
１１１ 演算処理用パラメータ記憶部
１１２ 領域分割結果記憶部
１２１ 代表点群決定部
１２２ 規定断面形状存在判定部
１２３ 規定断面形状生成部
１２４ 規定断面統合部
【図１】
0006397386.tif 000048
【図２】
0006397386.tif 000049
【図３】
0006397386.tif 000050
【図４】
0006397386.tif 000051
【図５】
0006397386.tif 000052
【図６】
0006397386.tif 000053
【図７】
0006397386.tif 000054
【図８】
0006397386.tif 000055
【図９】
0006397386.tif 000056
【図１０】
0006397386.tif 000057
【図１１】
0006397386.tif 000058
【図１２】
0006397386.tif 000059
【図１３】
0006397386.tif 000060
【図１４】
0006397386.tif 000061
【図１５】
0006397386.tif 000062
【図１６】
0006397386.tif 000063