(57)【特許請求の範囲】
【請求項１】
物体の表面上の位置を計測した計測結果である複数の位置を表す３次元点群に基づいて、局所形状情報を用いたクラスタリング処理を行って、３次元点群を含む平面領域と３次元点群を含む道路走行面とを検出する平面領域検出部と、
前記平面領域検出部によって検出された前記平面領域の各々について、周辺地物との相対位置を考慮して、標識候補領域であるか否かを判定する標識候補領域判定部と、
前記標識候補領域の各々について、境界平面により分割可能であるか否かを判定し、分割可能であると判定された前記標識候補領域を前記境界平面により分割する標識領域分割処理部と、
を含む標識検出装置。
【請求項２】
前記標識領域分割処理部は、
前記標識候補領域の各々について、前記標識候補領域に含まれる３次元点群の注目点と前記注目点の周辺点群の各周辺点との相対ベクトルの各々が成す角度から、複数のエッジ候補点を検出し、前記検出された前記複数のエッジ候補点から、サンプリング処理により２点以上選択して前記境界平面を生成し、前記標識候補領域に含まれる３次元点群で生成されるグラフを前記生成した前記境界平面で分割するコストを評価して、前記境界平面により分割可能であるか否かを判定し、分割可能であると判定された前記標識候補領域を前記境界平面により分割することを繰り返し行う請求項１記載の標識検出装置。
【請求項３】
前記標識領域分割処理部は、
前記検出された前記複数のエッジ候補点から、サンプリング処理により２点以上選択して前記境界平面を生成し、標識の配置関係の事前知識を基に前記生成した前記境界平面の法線方向を補正し、前記コストを評価する評価関数として、ＮｏｒｍａｌｉｚｅｄＣｕｔの評価基準を用いて、前記コストを評価する請求項２記載の標識検出装置。
【請求項４】
前記標識領域分割処理部によって分割された前記標識候補領域の各々について、前記標識候補領域のスケールに応じて作成された、複数の幾何形状テンプレートとのマッチングにより、前記標識候補領域の標識形状の種類を識別する標識形状識別部を更に含む請求項１〜請求項３の何れか１項記載の標識検出装置。
【請求項５】
前記３次元点群の各３次元点は、物体の表面上の位置及び反射強度を計測した計測結果を表し、
前記標識候補領域判定部は、前記平面領域検出部によって検出された前記平面領域の各々について、前記平面領域に含まれる３次元点群の反射強度を更に考慮して、標識候補領域であるか否かを判定する請求項１〜請求項４の何れか１項記載の標識検出装置。
【請求項６】
平面領域検出部が、物体の表面上の位置を計測した計測結果である複数の位置を表す３次元点群に基づいて、局所形状情報を用いたクラスタリング処理を行って、３次元点群を含む平面領域と３次元点群を含む道路走行面とを検出するステップと、
標識候補領域判定部が、前記平面領域検出部によって検出された前記平面領域の各々について、周辺地物との相対位置を考慮して、標識候補領域であるか否かを判定するステップと、
標識領域分割処理部が、前記標識候補領域の各々について、境界平面により分割可能であるか否かを判定し、分割可能であると判定された前記標識候補領域を前記境界平面により分割するステップと、
を含む標識検出方法。
【請求項７】
コンピュータを、請求項１〜請求項５のいずれか１項に記載の標識検出装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、標識検出装置、方法、及びプログラムに係り、特に、物体の表面の位置を計測した点群から標識を検出するための標識検出装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
近年、モバイルマッピングシステム（ＭＭＳ）と呼ばれるカメラやレーザースキャナを搭載した車が、街中を走行することで道路周辺の構造物である建造物や道路などの物体の表面の形状を計測できるシステムが利用されつつある。このシステムは、ＧＰＳ（全地球測位システム）やＩＭＳ(慣性計測装置)を用いて物体の表面を３次元の座標情報（３次元点群）として記録できる。この技術を利用して、道路周辺の地物（信号機や電柱、標識、ガードレール等）の検出による３次元の地図作成保守・保全業務への活用が期待されている。
【０００３】
非特許文献１では、ＭＭＳで計測した道路および周辺の構造物の点群およびカメラ画像を用いて、道路の白線や横断歩道、また標識を登録するシステムを開発している。このシステムでは、白線や標識については、画像認識ソフトにより自動的に検出を行い、誤検出や検出漏れが生じた道路および周辺の構造物については、後から手動で修正を行い、高精度な道路地物位置計測を作成している。
【０００４】
非特許文献２では、ＭＭＳで計測した点群のみを入力とし、標識および柱状構造物などの地物の自動で検出が行われている。標識については、柱状構造物の近傍に存在する平面であると見なして検出を行っている。具体的には、柱状構造物周辺の点群について、主成分分析したときの固有値を特徴として、平面（標識）が存在するか判定している。
【０００５】
非特許文献３では、ＭＭＳで計測した点群およびカメラ画像を用いることで、道路標識を自動で検出が行われている。標識のレーザーの反射強度が強いこと、更に３次元の点群の平面形状であることを手掛かりとして標識の３次元空間での位置をまず検出している。次に、その３次元位置からカメラ画像上での標識位置を算出し、その位置に対して画像認識処理を行うことで、標識認識を行っている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】橋詰、「モービルマッピングシステムを用いた既設道路舗装状態の道路CADおよびGIS連接に関する実証的研究」、JACIC 平成２１年度研究助成事業成果報告(http://www.douga.jacic.or.jp/douga/091113hashizume0197/Contents/index.html)
【非特許文献２】深野、増田、「機械学習を用いた移動計測点群データの分類」、精密工学会学術講演会講演論文集 2013A(0), 625-626, 2013
【非特許文献３】Lipu Zhou, Zhidong Deng, “LIDAR and vision-based real-time traffic sign detection and recognition algorithm for intelligent vehicle”, IEEE 17th International Conference on Intelligent Transportation Systems (ITSC), pp. 578 − 583, 2014
【非特許文献４】Jianbo Shi and Jitendra Malik (1997): "Normalized Cuts and Image Segmentation", IEEE Conference on Computer Vision and Pattern Recognition, pp 731−737
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、非特許文献１においては、自動検出においては画像情報のみを基にして標識を検出しているため、オクルージョンの影響や天候状況などの撮影環境の影響により検出精度が低下しやすいという課題がある。また、人手による操作が必要なため、大規模な地域での運用には人的リソースのコストが大きくなるという課題もある。
【０００８】
また、非特許文献２では、検出した柱状構造物周辺の点群について、平面領域を検出することで標識を検出している。しかしながら、この技術では標識を平面として認識しているために、隣接した標識を同一の標識と誤って判定してしまうという、つまり、検出漏れが生じる課題がある。また、標識の形状の分類もわからない。例えば、図１（Ａ）や図１（Ｂ）に示すような、隣接した標識について検出精度が低いという課題がある。
【０００９】
また、非特許文献３において、ＭＭＳで計測した点群から反射強度が高いことを仮定しているが、反射強度が高くない標識、例えば高速道路の案内標識が検出漏れを生じるという課題がある。また、カメラ画像を用いて画像上での正確な位置および種類を認識しているが、上述したように標識の位置の検出精度は撮影状態により、標識の形状やテクスチャの推定精度は低下するという課題は残っている。交差点付近での曲がり角での撮影時の画像のブレやトンネル内外への切り替わりでの露光条件の差によるホワイトアウト等の問題が存在する。
【００１０】
本発明は、上記問題点を解決するために成されたものであり、精度よく標識を検出することができる標識検出装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、第１の発明に係る標識検出装置は、物体の表面上の位置を計測した計測結果である複数の位置を表す３次元点群に基づいて、局所形状情報を用いたクラスタリング処理を行って、３次元点群を含む平面領域と３次元点群を含む道路走行面とを検出する平面領域検出部と、前記平面領域検出部によって検出された前記平面領域の各々について、周辺地物との相対位置を考慮して、標識候補領域であるか否かを判定する標識候補領域判定部と、前記標識候補領域の各々について、境界平面により分割可能であるか否かを判定し、分割可能であると判定された前記標識候補領域を前記境界平面により分割する標識領域分割処理部と、を含んで構成されている。
【００１２】
また、第１の発明に係る標識検出装置において、前記標識領域分割処理部は、前記標識候補領域の各々について、前記標識候補領域に含まれる３次元点群の注目点と前記注目点の周辺点群の各周辺点との相対ベクトルの各々が成す角度から、複数のエッジ候補点を検出し、前記検出された前記複数のエッジ候補点から、サンプリング処理により２点以上選択して前記境界平面を生成し、前記標識候補領域に含まれる３次元点群で生成されるグラフを前記生成した前記境界平面で分割するコストを評価して、前記境界平面により分割可能であるか否かを判定し、分割可能であると判定された前記標識候補領域を前記境界平面により分割することを繰り返し行うようにしてもよい。
【００１３】
また、第１の発明に係る標識検出装置において、前記標識領域分割処理部は、前記検出された前記複数のエッジ候補点から、サンプリング処理により２点以上選択して前記境界平面を生成し、標識の配置関係の事前知識を基に前記生成した前記境界平面の法線方向を補正し、前記コストを評価する評価関数として、ＮｏｒｍａｌｉｚｅｄＣｕｔの評価基準を用いて、前記コストを評価するようにしてもよい。
【００１４】
また、第１の発明に係る標識検出装置において、前記標識領域分割処理部によって分割された前記標識候補領域の各々について、前記標識候補領域のスケールに応じて作成された、複数の幾何形状テンプレートとのマッチングにより、前記標識候補領域の標識形状の種類を識別する標識形状識別部を更に含むようにしてもよい。
【００１５】
また、第１の発明に係る標識検出装置において、前記３次元点群の各３次元点は、物体の表面上の位置及び反射強度を計測した計測結果を表し、前記標識候補領域判定部は、前記平面領域検出部によって検出された前記平面領域の各々について、前記平面領域に含まれる３次元点群の反射強度を更に考慮して、標識候補領域であるか否かを判定するようにしてもよい。
【００１６】
第２の発明に係る標識検出方法は、平面領域検出部が、物体の表面上の位置を計測した計測結果である複数の位置を表す３次元点群に基づいて、局所形状情報を用いたクラスタリング処理を行って、３次元点群を含む平面領域と３次元点群を含む道路走行面とを検出するステップと、標識候補領域判定部が、前記平面領域検出部によって検出された前記平面領域の各々について、周辺地物との相対位置を考慮して、標識候補領域であるか否かを判定するステップと、標識領域分割処理部が、前記標識候補領域の各々について、境界平面により分割可能であるか否かを判定し、分割可能であると判定された前記標識候補領域を前記境界平面により分割するステップと、を含んで実行することを特徴とする。
【００１７】
第３の発明に係るプログラムは、コンピュータを、第１の発明に係る標識検出装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１８】
本発明の標識検出装置、方法、及びプログラムによれば、３次元点群に基づいて、局所形状情報を用いたクラスタリング処理を行って、３次元点群を含む平面領域と３次元点群を含む道路走行面とを検出し、検出された平面領域の各々について、周辺地物との相対位置を考慮して、標識候補領域であるか否かを判定し、標識候補領域の各々について、境界平面により分割可能であるか否かを判定し、分割可能であると判定された標識候補領域を境界平面により分割することにより、精度よく標識を検出することができる、という効果が得られる。
【図面の簡単な説明】
【００１９】
【図１】隣接した標識の一例を示す図である。
【図２】本発明の第１の実施の形態に係る標識検出装置の構成を示すブロック図である。
【図３】本発明の第１の実施の形態に係る標識検出装置における標識検出処理ルーチンを示すフローチャートである。
【図４】標識検出処理ルーチンのステップＳ１の詳細なフローチャートである。
【図５】標識検出処理ルーチンのステップＳ２の詳細なフローチャートである。
【図６】標識検出処理ルーチンのステップＳ３の詳細なフローチャートである。
【図７】注目点とその周辺点群の成す角度及び位置関係を示す図である。
【図８】領域分割処理の全体の流れを示す図である。
【図９】領域分割処理におけるステップＳ３−３の詳細なフローチャートである。
【図１０】法線に対する補正処理の一例を示す図である。
【図１１】領域Ａ及び領域Ｂについて決定された境界平面の一例を示す図である。
【図１２】本発明の第２の実施の形態に係る標識検出装置の構成を示すブロック図である。
【図１３】本発明の第２の実施の形態に係る標識検出装置における標識検出処理ルーチンを示すフローチャートである。
【図１４】標識検出処理ルーチンのステップＳ４の詳細なフローチャートである。
【図１５】テンプレートマッチングを行う領域の一例を示す図である。
【図１６】本発明の第３の実施の形態に係る標識検出装置の構成を示すブロック図である。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２１】
［発明の概要］
（第１の概要）
【００２２】
本発明の実施の形態では、具体的には、標識候補領域として検出された点群について、エッジ上に存在する点をまず検出し、 次に、その検出したエッジ点をサンプリングして境界平面候補を多数生成する。これらの境界平面候補の中で、グラフ分割のコストの累積値を最小にするものを境界平面として決定する。
【００２３】
また、案内標識のように反射強度が小さい場合でも検出が可能なように、平面と周辺地物との相対関係を考慮することで平面の検出精度も向上させる。道路上の標識は、門型柱状構造物に設置されることや、トンネル内の天井に設置されるなど、走行道路の真上に位置していることが多い。そこで、本発明では、道路走行面との相対位置関係を考慮した標識候補領域の判定処理を行う。
【００２４】
（第２の概要）
【００２５】
更に本発明の実施の形態では、切り出された点群から標識形状の識別を行う。個々に検出された標識については、その中心位置および縦横の大きさ（スケール）を推定することは容易である。そこで、推定したスケールに合わせ、かつ、検出対象となる形状に合わせた幾何テンプレートとして、具体的には、丸や三角、長方形等の図形とのマッチングにより形状識別を行う。
【００２６】
（第３の概要）
【００２７】
また、柱状構造物の位置を考慮することで更に判定条件を厳しくし、誤検出を抑制する。
【００２８】
［実施形態の概説］
【００２９】
本実施の形態に係る点群解析による標識検出装置は、レーザースキャナ等で計測された３次元点群を入力として標識の位置検出と標識の種類を認識するシステムである。本実施の形態においては、３次元情報（位置情報）とは、緯度、経度、海抜（高さ）情報でもよいし、ユーザーが設定した特定の位置を原点とした３次元ユークリッド座標系でも極座標系でもよい。本実施の形態においては、ユーザーが設定した原点における３次元ユークリッド座標系（各方向をＸ，Ｙ，Ｚ座標とする）を想定する。
【００３０】
各座標の単位はメートル(m)やセンチメートル(cm)、ミリメートル(mm)で表現するが、他の単位でもよい。３次元点とは、上記の３次元座標に、その点が撮影された時刻、レーザーの反射強度、赤・青・緑などの色情報等が付与された点でもよい。３次元点に付与される情報に制限はないが、少なくとも位置情報（Ｘ，Ｙ，Ｚ座標）は付与されたものであり、３次元点群とは、これらの情報を含む点の集合である。
【００３１】
また、本実施の形態においては、ユークリッド座標系のＺ軸の方向は鉛直（高さ）方向を意味し、Ｘ軸とＹ軸の張る二次元平面は水平面を意味するものとする。また、３次元点群はレーザースキャナ以外にも、距離情報を取得できるセンサであればよく、例えば超音波センサやステレオカメラにより取得した奥行き情報から求めた３次元点群でもよい。
【００３２】
[第１の実施の形態]
（標識検出装置全体の説明）
【００３３】
次に、本発明の第１の実施の形態に係る点群解析による標識検出装置の構成について説明する。図２に示すように、第１の実施の形態に係る点群解析による標識検出装置１００は、ＣＰＵと、ＲＡＭと、後述する点群解析処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この点群解析による標識検出装置１００は、機能的には、記憶部１０３と、標識検出部１０４とを含んで構成されている。また、標識検出装置１００には、被写体計測部１０１と、入力部１０２とが接続されている。
【００３４】
被写体計測部１０１は、物体の表面上の位置を計測した計測結果である複数の位置を表す３次元点群を計測するものであり、３次元点群を計測する装置は、レーザーレンジファインダや、赤外線センサ、または超音波センサなど、被写体とセンサとの距離を測定可能な装置である。例えば、レーザーレンジファインダをＧＰＳ（Global Positioning System）を搭載された車の上にこれら被写体表面の３次元位置を計測するシステムであるＭＭＳ（Mobile Mapping System）を用いればよい。またステレオカメラのように複数のカメラ画像を用いて、三角測量の原理から奥行きを推定する計測機器でもよい。
【００３５】
入力部１０２は、マウスやキーボードなどのユーザーインターフェースであり、点群解析による標識検出装置１００で使用するパラメータを入力するものである。また、パラメータを記憶したＵＳＢメモリなどの外部記憶媒体でもよく、記憶部１０３の演算処理用パラメータ記憶部１１１にパラメータを供給する。
【００３６】
記憶部１０３は、３次元点群記憶部１１０と、演算処理用パラメータ記憶部１１１と、標識情報記憶部１１２と、を含んで構成されている。また、記憶部１０３は、例えば、ＨＤＤ（Hard Disk Drive）や、ＳＳＤ（Solid State Drive）等のハードウェアによる記憶装置である。
【００３７】
標識情報記憶部１１２には、標識検出部１０４で検出された標識の３次元座標位置と標識の平面の法線方向が記憶される。
【００３８】
標識検出部１０４は、平面領域検出部１２０と標識候補領域判定部１２１と標識領域分割処理部１２２とを含んで構成されている。
【００３９】
平面領域検出部１２０において、入力された３次元点群に対して局所形状に基づきクラスタリングを行い、３次元点群からなる領域を平面領域に分割する。領域分割された３次元点群は標識候補領域判定部１２１に供給され、各平面領域について標識候補領域であるか判定処理が行われる。次に、標識領域分割処理部１２２は、隣接する標識があれば切り分け処理を行い、記憶部１０３に検出した標識の情報を出力する。
【００４０】
（標識検出部１０４の動作説明）
【００４１】
まず、本実施の形態の標識検出装置１００による標識検出部１０４の処理全体の流れについて図３を参照して説明する。
【００４２】
（ステップＳ１：平面領域検出部）
ステップＳ１において、記憶部１０３から供給される３次元点群および地物情報に基づいて、局所形状情報を用いたクラスタリング処理を行って、３次元点群を含む平面領域と、３次元点群を含む道路走行面とを検出する。ここで、地物情報とは３次元点群の計測位置や柱状構造物の位置を意味するが、それ以外の建造物の情報を含んでいてもよい。なお、地物情報が無くても標識検出部１０４の動作は可能である。
【００４３】
（ステップＳ２：標識候補領域判定部）
ステップＳ２において、平面領域検出部１２０から入力された平面領域の各々について、周辺地物との相対位置を考慮して、標識候補領域であるか否かを判定する。このとき、第１の実施の形態では、地物情報にＭＭＳの走行軌跡もしくは地図の道路位置情報が含まれている場合には、この道路走行面と標識候補領域の相対位置を考慮して判定が行われる。
【００４４】
（ステップＳ３：標識領域分割処理部）
ステップＳ３において、標識候補領域判定部１２１から入力された標識候補領域の各々について、境界平面により分割可能であるか否かを判定し、分割可能であると判定された標識候補領域を境界平面により分割する処理を行い、記憶部１０３に標識情報を出力する。標識情報とは、標識領域に属する点群番号や標識の中心位置、大きさや形状の種類等を意味する。
【００４５】
以下、点群の位置の単位は[m]（メートル）とし、レーザーの反射強度は計測機器により値が異なるため、事前処理として値が０から２５５になるように正規化処理しておくものとする。
【００４６】
以下にステップＳ１〜Ｓ３における処理の詳細について説明する。
【００４７】
本実施の形態では、３次元点群の反射強度および法線方向、距離を特徴として、３次元点群をクラスタリング（統合処理）していく。クラスタリング（以下、統合と呼ぶ）された３次元点群のことを以降では領域とよび、各領域を区別する番号をｃ(∈{１,２,３,..,Ｃ})、点群を区別する番号をｉ、統合された各領域に含まれる点の総数をＮｐｏｉｎｔｓＣとする。
【００４８】
ここで、入力された３次元点群位置を
【００４９】
【数１】
0006381137.tif 000002
【００５０】
で表現する。ただし、[ｘｉ，ｙｉ，ｚｉ]は、Ｘ，Ｙ，及びＺ軸の座標成分を意味し、右上の添え字の記号「Ｔ」は転置を意味とする。以降では、領域の番号を用いて、処理の流れを説明する。統合された領域ｃに属する点は、以下（２）式のように右上の添え字にクラスタの番号を示すことで表記することとする。
【００５１】
【数２】
0006381137.tif 000003
【００５２】
（ステップＳ１：平面領域検出部）
図４にステップＳ１の詳細なフローを示す。
【００５３】
（ステップＳ１−１：Ｋ近傍点検出、法線方向の算出）
ステップＳ１−１において、３次元点群における注目点ｐｉについて、半径ｒ内に含まれる３次元点を周辺点ｐｊとし、ｊを周辺点群の点を区別する記号ｊ(∈{１,２,３,..,Ｎｕｍｊ})とする。ｎｉとｎｊとをそれぞれの点の法線方向とし、各３次元点のレーザーの反射強度をｒｅｆ(ｉ)、ｒｅｆ(ｊ)で表現すると以下の（３）〜（５）式を満たす３次元点をクラスタリングしていく。ただし、本実施の形態では法線の検出方法には非特許文献５に記載の方法を用いるが、法線の検出方法は特に限定されるものではない。
【００５４】
（ステップＳ１−２：クラスタリング処理）
ステップＳ１−２において、以下の（３）〜（５）式を全て満たすとき、注目点ｐｉ及び周辺点ｐｊは同じ領域にクラスタリングされる。
【００５５】
【数３】
0006381137.tif 000004
【００５６】
ここで、記号「||  ||」はベクトルの２ノルムを意味し、記号「・」はスカラー値の場合には掛け算を、ベクトルの場合には内積を意味し、記号「｜｜」は絶対値を意味する。半径ｒや閾値Ｔｈ＿ａｎｇｌｅ，Ｔｈ＿ｒｅｆｌｅｃｔｉｏｎは演算処理用パラメータ記憶部１１１に登録されているパラメータである。以降では、このようなパラメータを「実験的に決めるパラメータである」と記載する。本実施の形態において、ｒ＝０．３（ｍ）とした。閾値Ｔｈ＿ａｎｇｌｅ，Ｔｈ＿ｒｅｆｌｅｃｔｉｏｎも実験的に決めるパラメータであり、本実施の形態ではＴｈ＿ａｎｇｌｅ＝５、Ｔｈ＿ｒｅｆｌｅｃｔｉｏｎ＝３０とした。反射強度を考慮することは精度を向上させる観点で望ましいが、しかし、入力された点群の反射強度が無い場合には、（５）式を用いないこととする。
【００５７】
（４）式は物理的には、法線方向の成す角度を意味する。本実施の形態では、平面領域を検出する必要があるため、このパラメータＴｈ＿ａｎｇｌｅは３度〜１０度と小さい値が望ましい。計測ノイズの大きい場合には、この閾値を大きくし、計測ノイズが小さい場合には閾値も小さく設定すればよい。
【００５８】
入力した３次元点群全てについて、上記のクラスタリング処理を終わったあとに生成されたクラスタｃについて、当該クラスタｃの３次元点群の総数が閾値Ｔｈ＿ｐｏｉｔｎｓより小さいときにはノイズと判定して除去する。本実施の形態では、Ｔｈ＿ｐｏｉｔｎｓ＝２０［点］とした。
【００５９】
（ステップＳ１−３：平面判定処理）
次に、ステップＳ１−３において、ステップＳ１−２で生成された各クラスタｃについて平面領域であるか否かの判定処理を行う。具体的には、クラスタｃの領域について平面近似を行ったときの近似精度に基づいて判定される。近似する平面は、各クラスタに属する３次元点群の座標から共分散行列を作成し、その共分散行列を固有値分解することで求める。
【００６０】
まず、クラスタｃの重心位置ｐｇｃを以下の（６）式で求める。
【００６１】
【数４】
0006381137.tif 000005
【００６２】
次に、クラスタｃの共分散行列Ｑは以下の（７）式で求める。
【００６３】
【数５】
0006381137.tif 000006
【００６４】
ただし、添え字記号「Ｔ」は転置することを意味する。
【００６５】
次に、共分散行列Ｑを固有値分解したときの固有値ベクトルについて、固有値が一番大きいものに対応する第一固有値ベクトルをｕｃ、固有値が２番目に大きいベクトルをｖｃ、一番小さい固有値に対応するベクトルをｎｃとして求める。また、ｎｃは物理的には平面近似した際の法線方向を意味し、ｕｃは平面近似した際の“長軸”方向、ｖｃは“短軸”方向を意味する。ただし、長軸と短軸の意味は、点群の分布が広い方向と、分布が狭い方向に対応する。以降、このｎｃをクラスタｃの代表法線方向とする。
【００６６】
次に、代表法線方向ｎｃを用いて、以下の（８）式により、クラスタｃの領域についての近似誤差Ｅｒｒｏｒ＿ｐｌａｎｅが求められる。
【００６７】
【数６】
0006381137.tif 000007
【００６８】
そしてステップＳ１−３では、（８）式により求めた近似誤差Ｅｒｒｏｒ＿ｐｌａｎｅが閾値Ｔｈ＿ｐｌａｎｅ＿ｅｒｒｏｒよりも小さいときに、クラスタｃについて、平面領域であると判定する。閾値Ｔｈ＿ｐｌａｎｅ＿ｅｒｒｏｒは実験的に決めるパラメータであり、本実施の形態では閾値Ｔｈ＿ｐｌａｎｅ＿ｅｒｒｏｒ＝０．０１［ｍ］とした。
【００６９】
（ステップＳ１−４：道路走行面検出）
ステップＳ１−４において、ステップＳ１−３により平面領域と判定されたクラスタの中から、道路走行面を検出する。ステップＳ１−４では、平面領域と判定された各クラスタの法線方向ｎｃと、ＭＭＳの走行軌跡との相対位置と、クラスタに属する点群の大きさとにより判定処理を行う。
【００７０】
平面領域の大きさは、以下（９）式及び（１０）式に示す、クラスタｃに属する点群ｐｉｃの長軸方向の最大値Ｈｅｉｇｈｔと短軸方向の最大値Ｗｉｄｔｈとにより求まる。
【００７１】
【数７】
0006381137.tif 000008
【００７２】
注目クラスタｃについて、道路走行軌跡をＰＲｏａｄ、走行軌跡の計測位置の総数をＮｒｏａｄ、各点をｐｊｒｏａｄ(ｊ∈１,２,…,Ｎｒｏａｄ)で表すと、以下の（１１）〜（１４）式を全て満たすときに道路走行面と判定する。
【００７３】
【数８】
0006381137.tif 000009
【００７４】
（１１）式及び（１２）式では、クラスタｃの重心と走行軌跡ＰＲｏａｄとの最小距離、すなわち、クラスタｃを平面と仮定したときの平面上での距離を基準として、道路走行面判定をしている。ただし、関数ａｂｓ（）は、絶対値を出力する関数とする。
【００７５】
（１１）式は、道路走行軌跡をクラスタｃの法線方向に対して正射影したときの重心位置に対する長軸方向の最小距離を意味し、（１２）式は、短軸方向の最小距離を意味している。（１３）式は、クラスタcの法線方向とＺ軸方向
【００７６】
【数９】
0006381137.tif 000010
【００７７】
との相対角度を意味している。ここではＺ軸方向に近いほど、道路走行面と判定されやすい。（１４）式は、平面近似したクラスタｃの大きさを意味している。ここでは平面の大きさが大きいほど、道路走行面と判定されやすい。
【００７８】
本実施の形態においては、
【００７９】
【数１０】
0006381137.tif 000011
【００８０】
とした。また、以降のステップにおいては、道路走行面と判定されたクラスタについて、道路走行面クラスタＲｏａｄという１つのクラスタであると見なす。
【００８１】
以上、ステップＳ１−４において道路走行面クラスタの検出方法について説明したが、入力される３次元点群のデータによっては、事前に手動で道路走行面の点群を除いている場合がある。つまり、ステップＳ１−４で道路走行面クラスタが検出されなかった場合は、道路走行面クラスタはＮｕｌｌ（不明）として道路走行面クラスタの情報を登録する。
【００８２】
（ステップＳ２：標識候補領域判定部）
ステップＳ２では、平面領域と判定されたクラスタについて、周辺地物との相対位置を考慮して、標識候補領域であるか判定を行う。本実施の形態においては、平面領域と判定されたクラスタについて、道路走行面クラスタＲｏａｄとの位置関係を考慮して標識候補領域かどうか判定する。
【００８３】
ただし、反射強度が低い平面の中には、仮に道路走行面上に存在したとしても陸橋の側面部や、トンネルの入り口部分などの、建造物の一部分である可能性がある。そこで、本実施の形態では、検出した平面が他の建造物の一部であるか、他の３次元点群から独立した３次元点群かどうか評価を行い、その評価値も考慮して標識候補領域であるか判定する。
【００８４】
図５にステップＳ２の詳細なフローを示す。
【００８５】
（ステップＳ２−１：クラスタ情報抽出）
ステップＳ２−１では、注目クラスタｃについて、建造物表面に存在している３次元点と接している注目点ｐｉｃの割合に基づいて、独立度合いＥｉｓｏｌａｔｅを算出する。ここで、建造物表面に存在している３次元点とは、注目クラスタｃ以外の３次元点群全てと見なす。ただし、その３次元点が属するクラスタの大きさが閾値以上の大きさの場合とする。
【００８６】
クラスタｃの注目点ｐｉｃについて、ｋｐ個の近傍点ｐｊ (ｊ∈１,２,..,ｋｐ)について、その近傍点が所属するクラスタをＣｌｕｓｔｅｒ(ｐｊ)と表現すると、注目クラスタｃ以外のクラスタについて、長軸および短軸方向の長さをＨｅｉｇｈｔ（Ｃｌｕｓｔｅｒ（ｐｊ））、Ｗｉｄｔｈ（Ｃｌｕｓｔｅｒ（ｐｊ））で表現すると、以下の（１５）式及び（１６）式を満たす時に、注目点ｐｉｃは建造物と接していると判定する。
【００８７】
【数１１】
0006381137.tif 000012
【００８８】
ここで、閾値Ｔｈ＿ｂｕｉｌｄｉｎｇは実験的に決めるパラメータであり、本実施の形態ではＴｈ＿ｂｕｉｌｄｉｎｇ＝０．５［ｍ］とした。また、近傍点とは注目点ｐｉｃから距離が近い順にｋｐ点選んだ点を意味している。繰り返しになるが、上記Ｃｌｕｓｔｅｒ（ｐｊ）がクラスタｃとなる近傍点であるかは考慮しない。
【００８９】
クラスタｃについて、独立度合いＥｉｓｏｌａｔｅ(c)は以下の（１７）式により求まる。
【００９０】
【数１２】
0006381137.tif 000013
【００９１】
代表反射強度ｒｅｆ（ｃ）については、本実施の形態においてクラスタｃに属する３次元点群の反射強度の平均値もしくは中央値を用いることとする。平均値を用いた算出例を以下に示す。
【００９２】
【数１３】
0006381137.tif 000014
【００９３】
ただし、入力点群に反射強度が含まれていないときは、代表反射強度ｒｅｆ（ｃ）は０とする。０とする理由は、下記で判定する標識候補クラスタの判定条件を厳しくするという意味である。つまり、反射強度を有しない点群は、より厳しい条件での判定を行う。
【００９４】
ステップ２−１について以下に説明する処理は、登録されている道路走行面クラスタの情報がＮｕｌｌ(不明)ではないときのみ行われる。
【００９５】
道路走行面と各クラスタの相対位置は、ＸＹ平面に射影したときの道路走行面上の点と注目クラスタの重心位置の水平面上での最短距離、クラスタ代表法線方向と道路走行面における点の法線の成す角度の最小値、注目クラスタの重心位置の道路からの高さ、以上の組み合わせにより表す。
【００９６】
道路走行面クラスタＲｏａｄに属している点をｐｈＲｏａｄ、その法線方向ｎｈＲｏａｄと表現すると、クラスタｃの重心位置ｐｇｃに対する、Ｒｏａｄに属している点群ｋｒ個の近傍点ｐｈＲｏａｄ(ｈ∈１,２,３,..,ｋｒ)を用いて、以下（１８）〜（２０）式により、上記の最短距離Ｄｉｓｔａｎｃｅ＿ｍｉｎ、最小の成す角度Ａｎｇｌｅ＿ｍｉｎ、及び最小地上高Ｈｅｉｇｈｔ＿ｍｉｎを求める。
【００９７】
【数１４】
0006381137.tif 000015
【００９８】
ただし、記号「×」はベクトルの外積を意味する。
【００９９】
クラスタ情報とは、上記で求めた各クラスタの独立度合いＥｉｓｏｌａｔｅ(c)、長軸と短軸方向の長さＨｅｉｇｈｔ（ｃ），Ｗｉｄｔｈ（ｃ）、各クラスタの代表位置と道路軌跡との最短距離Ｄｉｓｔａｎｃｅ＿ｍｉｎ（ｃ）、各クラスタの代表法線方向と道路走行面の法線との成す最小角度Ａｎｇｌｅ＿ｍｉｎ（ｃ）、道路走行面からの最低地上高Ｈｅｉｇｈｔ＿ｍｉｎ（ｃ）、及び代表反射強度ｒｅｆ（ｃ）のことである。ただし、ステップＳ１−４において、道路走行面クラスタが検出されていないときは、道路走行面クラスタ情報がＮｕｌｌ(不明)となっている。
【０１００】
（ステップＳ２−２：標識候補判定処理）
ステップＳ２−２において、ステップＳ２−１で求めたクラスタ情報に基づいて、クラスタｃの平面領域が標識候補領域であるか否かの判定を行う。本実施の形態において、標識であるかの判定基準は大きく分けて２つあり、高い反射強度を有する平面を対象とした判定条件が比較的緩いもの、もう一つは高い反射強度を有さない平面を対象としたより判定基準を厳しくしたものである。
【０１０１】
クラスタｃの代表反射強度が高いかどうかは、閾値Ｔｈ＿Ｓｉｇｎ＿ｒｅｆｌｒｅｃｔｉｏｎに対する大小関係により決定する。以下の（２１）式を満たす時、反射強度は高いと判定する。
【０１０２】
【数１５】
0006381137.tif 000016
【０１０３】
本実施の形態では、Ｔｈ＿Ｓｉｇｎ＿ｒｅｆｌｒｅｃｔｉｏｎ＝２２０とした。
【０１０４】
高い反射強度のとき、以下の（２２）式に示す全ての判定条件を満たせば、標識候補クラスタであると判定する。
【０１０５】
【数１６】
0006381137.tif 000017
【０１０６】
ただし、閾値Ｔｈ１＿Ｓｉｇｎ＿Ｄｉｓｔａｎｃｅ＝４．０［ｍ］、Ｔｈ１＿Ｓｉｇｎ＿Ｈｅｉｇｈｔ＝１．０［ｍ］、Ｔｈ１＿Ｓｉｇｎ＿Ａｎｇｌｅ＝６０［度］、Ｔｈ＿ｉｓｏｌａｔｅ＝０．２とした。物理的には、Ｄｉｓｔａｎｃｅ＿ｍｉｎは重心と道路走行面との水平面での距離を表し、閾値Ｔｈ１＿Ｓｉｇｎ＿Ｄｉｓｔａｎｃｅ＝４．０は、道路からある程度離れても標識であると判定することを意味している。Ａｎｇｌｅ＿ｍｉｎは、クラスタｃと道路走行面との法線の成す角度を意味し、これが大きい値であるほど２つの平面の関係は垂直であることを意味する。
【０１０７】
また、道路走行面クラスタの情報がＮｕｌｌ（不明）のときは、Ｄｉｓｔａｎｃｅ＿ｍｉｎ（ｃ）、Ｈｅｉｇｈｔ＿ｍｉｎ（ｃ）、Ａｎｇｌｅ＿ｍｉｎ（ｃ）の判定式は使用しない。
【０１０８】
低い反射強度のとき、以下の（２３）式に示す全ての判定条件を満たせば、標識候補クラスタであると判定する。
【０１０９】
【数１７】
0006381137.tif 000018
【０１１０】
ただし、閾値については、Ｔｈ＿Ｓｉｇｎ＿ａｒｅａｓｑｕａｒｅ＝０．２５［ｍ２］  、Ｔｈ＿Ｓｉｇｎ＿Ｈ＝０．５［ｍ］、Ｔｈ２＿Ｓｉｇｎ＿Ｄｉｓｔａｎｃｅ＝０．２［ｍ］、Ｔｈ２＿Ｓｉｇｎ＿Ｈｅｉｇｈｔ＝２．５［ｍ］、Ｔｈ２＿Ｓｉｇｎ＿Ａｎｇｌｅ＝６０［度］、Ｔｈ＿ｉｓｏｌａｔｅ＝０．２とした。また、道路走行面クラスタの情報がＮｕｌｌ（不明）のときは、Ｄｉｓｔａｎｃｅ＿ｍｉｎ（ｃ）、Ｈｅｉｇｈｔ＿ｍｉｎ（ｃ）、Ａｎｇｌｅ＿ｍｉｎ（ｃ）の判定式は使用しない。
【０１１１】
（ステップＳ３：標識候補分割処理）
ステップＳ３において、ステップＳ２−２で標識候補領域であると判定されたクラスタについて、標識候補分割処理を行う。境界平面の数及び位置は不明なため、本ステップではＲＡＮＳＡＣ処理により決定を行う（ステップＳ３−３）。まず、各クラスタについてエッジ候補となる点からサンプリングした点を用いて、多数の境界平面候補を生成する。次に、分割コストを最小化する境界平面を決定し、グラフを分割する。分割したグラフについて、再度サンプリングおよび境界平面の決定を繰り返し行い、評価関数の分割コストが閾値以上になったときに終了する。
【０１１２】
また、本ステップについては、標識候補領域であると判定された各クラスタについて独立して処理を行えばよく、並列処理を行うことでも、クラスタの番号の降順、昇順で逐次的に処理を行ってもよい。本実施の形態においては、昇順での処理をする例を示す。ステップＳ３−１からステップＳ３−４の処理を、すべてのクラスタについて処理が終了するまで繰り返す。
【０１１３】
図６にステップＳ３の詳細なフローを示す。
【０１１４】
（ステップＳ３−１：注目クラスタ番号ｃの選択）
ステップＳ３−１において、注目クラスタの番号を選択する。初めてステップＳ３−１処理を行う場合のみ、変数Ｌｏｏｐ←１（記号「←」は代入を意味する。）と設定し、標識候補領域と判定されたクラスタの番号の中で最も小さい番号を選択する。２回目以降にステップＳ３−１を実行する場合には、Ｌｏｏｐ←Ｌｏｏｐ＋１とし、標識候補領域と判定されたクラスタの中で、Ｌｏｏｐ番目に小さい番号を選択する。
【０１１５】
（ステップＳ３−２：エッジ候補点の検出）
ステップＳ３−２において、注目クラスタについて、標識候補領域に含まれる３次元点群の注目点と、注目点の周辺点群の各周辺点との相対ベクトルの各々が成す角度に基づいて、エッジ候補点を検出する。ここで、エッジとは、平面のコーナー（端）を意味し、エッジ候補点とは本ステップにより検出したエッジ上に存在すると推定された点群と定義する。図７に示すように、注目点とその周辺点群の位置関係を、周辺点群との相対ベクトルの成す角度により判定する。
【０１１６】
クラスタｃにおける注目点をｐｉｃ、近傍点をｐｊｃ(ｊ∈１,２,..,ｋｉ)、近傍点の数をｋｉとすると、以下の（２４）式を満たす場合に注目点ｐｉｃはエッジ候補点であると判定する。
【０１１７】
【数１８】
0006381137.tif 000019
【０１１８】
ただし、添え字記号「→」は、ノルムが１のベクトルであることを意味し、添え字ｔとｊは近傍点を区別する番号（j≠t）とし、右下の添え字「ｔ_ｉ」のついたベクトルは、注目点ｐｉｃを基準とした相対ベクトルとする。
【０１１９】
具体的な例を示すと、
【０１２０】
【数１９】
0006381137.tif 000020
【０１２１】
は以下の（２５）式で表現できる。
【０１２２】
【数２０】
0006381137.tif 000021
【０１２３】
閾値Ｔｈ＿Ａｎｇｌｅ＿Ａｒｒｏｕｎｄは、本実施の形態ではＴｈ＿Ａｎｇｌｅ＿Ａｒｒｏｕｎｄ＝１２０［度］とした。
【０１２４】
（ステップＳ３−３：領域分割処理）
ステップＳ３−３において、ステップＳ３−２で検出された複数のエッジ候補点から、サンプリング処理により２点以上選択して境界平面を生成し、標識候補領域に含まれる３次元点群で生成されるグラフを生成した境界平面で分割するコストを評価して、境界平面により分割可能であるか否かを判定する。そして、分割可能であると判定された標識候補領域を境界平面に分割する。上記の判定処理及び分割処理を繰り返し行うことにより、領域分割処理を行う。コストを評価する際には、点群をノードの集合と考え、個々のノード間の張るリンクとリンクの強さを設定する。設定したリンクを分割する際に生じるコストの総和を最小化するような境界平面を検出する。
【０１２５】
従来、領域分割を行うときにグラフ分割の問題として解く技術は、例えば非特許文献４に記載のように、２次元画像の領域分割について、Ｎｏｒｍａｌｉｚｅｄ  Ｃｕｔという評価基準（評価関数）を用いる技術がある。グラフ分割を固有値問題に帰着させて解析的に解くことが可能である。
【０１２６】
しかし、非特許文献４のような固有値分解により解くグラフ分割技術では、ノイズやオクルージョン（計測時の障害物の影響による部分的な点群の欠損）の影響により、同一の物体内であっても境界平面が生じることがある。ノイズや欠損は不規則な位置にランダムな形状で発生しやすく、境界平面も標識内部に生じやすい。結果として、過分割されやすい。
【０１２７】
そこで本実施の形態においては、境界平面も平面のような単純な形状で区切れるという制約を加える。図８に全体の流れを示す。ステップＳ３−２において検出したエッジ候補点をサンプリングし、サンプリングにより生成した境界平面を多数作成し、この境界平面の中から分割コストを最小化し、かつ閾値より小さい分割コストであるものを真の境界平面と決定する。
【０１２８】
以下、図９を用いて、ステップＳ３−３の詳細なフローを説明する。
【０１２９】
（ステップＳ３−３：ＲＡＮＳＡＣによる境界平面の算出フロー）
（ステップＳ３−３−１：境界平面生成処理）
ステップＳ３−３−１において、エッジ候補点をサンプリングして境界平面をＴ[個]生成する。一般的に平面を規定するには、最低３点以上の点が必要であるが、本ステップにおいては、分割対象は平面領域を対象としているため、この平面に垂直な境界平面であると仮定すれば２点あればよい。つまり、クラスタＣのエッジ候補点から任意の点をランダムに選択した２点により規定される直線と、クラスタＣの代表法線方向により張る面を境界平面とする。つまり、以下で求めるｎ（ｔ）ｃとｇ（ｔ）ｃとの組で境界平面が表現される。
【０１３０】
ｔ(∈{１,２,３,..,Ｔ})個目の境界平面について、クラスタＣのエッジ候補点から任意の点をランダムに２点選択した点をｐ１（ｔ）Ｃ, ｐ２（ｔ）Ｃ、クラスタＣの代表法線方向をｎｃとすると、t個目の境界平面の法線方向ｎ（ｔ）ｃは以下の（２６）式により求まる。
【０１３１】
【数２１】
0006381137.tif 000022
【０１３２】
ただし、境界平面はサンプリングした点の重心位置ｇ（ｔ）ｃを含む（距離が０である）とする。
【０１３３】
【数２２】
0006381137.tif 000023
【０１３４】
ここで、境界平面の数Ｔは実験的に決めるパラメータであり、Ｔの数が多い方が精度は向上する。本実施の形態ではＴ＝１０００とした。
【０１３５】
また、本実施の形態においては隣接する標識の配置は上下、左右、もしくは斜め４５度（右上、左下もしくは右下、左上）に配置してある確率が高いという事前知識を用いて、境界平面の法線方向を量子化補正する。
【０１３６】
図１０に示すように、サンプリングして生成した境界平面の法線ｎ（ｔ）ｃとＺ軸との成す角度が、４５度刻みの整数に対して±Δθ度以内のとき、成す角度が４５度の整数になるように補正処理を行う。
【０１３７】
以下の（２８）式により、上記で求めた境界平面の法線について、Ｚ軸を４５度刻みで量子化した角度からの偏差ｄｉｆｆ（θ）を求める。
【０１３８】
【数２３】
0006381137.tif 000024
【０１３９】
ここで、関数ｍｏｄ（ｘ，ｙ）は、実数ｘを実数ｙで割り算したときの整数値を出力する関数である。
【０１４０】
偏差ｄｉｆｆ（θ）の大きさが、閾値Δθ以内の時に、補正処理を行う。Δθは実験的に決めるパラメータであり、本実施の形態ではΔθ＝３度とした。
【０１４１】
補正後の法線方向
【０１４２】
【数２４】
0006381137.tif 000025
【０１４３】
は、サンプリングに決定した境界平面の法線方向ｎ（ｔ）ｃとＺ軸の外積により生成したベクトルｍ（ｔ）ｃに対して、右ねじの回転方向（反時計まわり）にＺ軸を回転した方向として求まる。
【０１４４】
【数２５】
0006381137.tif 000026
【０１４５】
ただし、関数Ｒｏｔ（ｍ，θ）は、ベクトルｍに対してθ度回転する回転行列（３行３列）を算出する関数であり、本実施の形態においてはロドリゲスの公式を用いる。
【０１４６】
最後に
【０１４７】
【数２６】
0006381137.tif 000027
【０１４８】
とし、以降のステップＳ３−３−２〜Ｓ３−３−５の処理では、補正後の法線ベクトルを用いる。上記の補正処理は必須ではないが、境界平面の数Ｔが少ない場合などには、サンプリングによる誤差を抑制する効果として有効である。
【０１４９】
（ステップＳ３−３−２：最小コスト分割面決定）
ステップＳ３−３−２において、Ｔ[個]の境界平面のグラフ分割コストを算出し、最小コストの境界平面を決定する。クラスタｃに属する点群の各点をノードとし、ノード間のリンクを近傍の点との間について作成する。コストを評価する評価関数としては、非特許文献４に記載のＮｏｒｍａｌｉｚｅｄＣｕｔの評価基準を用いる。
【０１５０】
クラスタｃの注目点ｐｉＣと、そのｋ近傍点ｐｊ（ｉ）(ｊ∈{１,２,３,..,ｋ})について、リンクｌｉｎｋ(ｉ,ｊ)の強さは２点間距離に応じて小さくなるように以下（３０）式のように算出される。
【０１５１】
【数２７】
0006381137.tif 000028
【０１５２】
リンクｌｉｎｋ(ｉ,ｊ)の強さは、２点の反射強度も考慮して、以下の（３１）式のように求めてもよい。
【０１５３】
【数２８】
0006381137.tif 000029
【０１５４】
ただし、σｄｉｓｔ, σｒｅｆ、ｋは実験的に決めるパラメータであり、本実施の形態ではσｄｉｓｔ＝０．５, σｒｅｆ＝２０,ｋ＝１０とした。関数ｒｅｆ(ｉＣ)は、クラスタｃに属する注目点ｉの反射強度を意味するとする。
【０１５５】
次に、クラスタｃに所属する注目点ｐｉＣについて、その近傍点ｐｊ（ｉ）(ｊ∈{１,２,..,ｋ})との間が、境界平面を横切るかどうかを以下の（３２）式の評価関数Ｆｌａｇにより判定する。
【０１５６】
【数２９】
0006381137.tif 000030
【０１５７】
ここで、関数ｓｉｇｎ(ｘ)は実数ｘの値が正のときは１を、それ以外は０（零）を出力する関数、関数ξ［数式］は、入力された数式の等号が成り立たない時に１を、成り立つときは０を出力する関数とする。このため、評価関数Ｆｌａｇ(ｐｉＣ, ｐｊＣ)は、境界平面の重心位置を基準として、法線ベクトルｎ（ｔ）ｃにおいて同一の方向（正側か負側）に注目点とその近傍点が存在するときに０を、異なる方向のときに１を出力する。近傍点の数ｋは実験的に決めるパラメータであり、本実施の形態ではｋ＝１０とした。
【０１５８】
ステップ３−３−２においては、推定した境界平面を用いて２つの領域を設定し、その２つの領域間の点群を用いてグラフの分割コストを計算する。図１１のように、２つの領域を領域Ａと領域Ｂとすると、各領域に所属する点群は境界平面からの距離ｄｉｓｔと法線との成す角度により決定される。境界平面からの距離が閾値ｄ以下で、かつ法線との成す角度が９０度未満のときは領域Ａと判定し、境界平面からの距離ｄｉｓｔがｄ以下で、かつ法線との成す角度が９０度以上のときは領域Ｂとする。法線との成す角度が９０度未満かの判定および距離ｄｉｓｔは以下の（３３）式で求まる。
【０１５９】
【数３０】
0006381137.tif 000031
【０１６０】
ここで、関数ｓｉｇｎの値が正のときに０と判定し、値が負のときに１と判定する。
【０１６１】
境界平面の法線ベクトル方向を用いて、領域Ａと領域Ｂを設定する。クラスタｃにおいて、領域Ａの注目点をｐａｉ（Ｃ_Ａ）、その点の近傍点群をｐａｊ（Ｃ_Ａ）(ｊ∈１,２,..,ｋａ)、領域Ｂの点群をｐｂｉ（Ｃ_Ｂ）、その近傍点群をｐｂｊ（Ｃ_Ｂ）(ｊｂ∈１,２,..,ｋｂ)で表し、注目点と近傍点との間が境界平面を横切るかどうか判定する式を、以下の（３４）式によりグラフ分割コストＥ（ｔ）（Ａ,Ｂ）は求まる。
【０１６２】
【数３１】
0006381137.tif 000032
【０１６３】
ただし、ＮＡおよびＮＢは、領域Ａと領域Ｂとの点群の総数を表し、変数εは零割を防ぐ微小値である。領域Ａと領域Ｂを規定する変数である距離ｄは実験的に決めるパラメータである。本実施の形態では、ε＝０．０１、距離ｄ＝０．２［ｍ］とした。
【０１６４】
Ｔ個の境界平面のうち、分割コストＥ（ｔ）を最小にする境界平面を出力する。
【０１６５】
【数３２】
0006381137.tif 000033
【０１６６】
【数３３】
0006381137.tif 000034
【０１６７】
の組で定まる境界平面が、ステップＳ３−３−２において求められる境界平面となる。
【０１６８】
（ステップＳ３−３−３：境界平面存在判定処理）
【０１６９】
ステップＳ３−３−３において、境界平面が存在するか判定する。最小の分割コストＥ（ｔ）が境界平面判定閾値Ｔｈ＿Ｓｕｒｆ未満のときに境界平面が存在すると判定する。
【０１７０】
【数３４】
0006381137.tif 000035
【０１７１】
閾値Ｔｈ＿Ｓｕｒｆは、本実施の形態においてＴｈ＿Ｓｕｒｆ＝０．１と設定した。境界平面が有ると判定された場合、ステップＳ３−３−４のクラスタ分割処理を行い、境界平面が有ると判定されない場合は、分割処理をおこなわずにクラスタｃの点群を処理する。つまり、ステップＳ３−３の入力と出力の注目クラスタに属する点群に変更は無い。
【０１７２】
境界平面が存在しないと判定されたクラスタは、標識クラスタとして出力される。
【０１７３】
（ステップＳ３−３−４：クラスタ分割処理）
ステップＳ３−３−４において、検出した境界平面に基づき領域を分割する。ステップＳ３−３−３で求めた重心位置からの相対ベクトルについて法線方向の正もしくは負の領域にあるかで判定する。クラスタｃの注目点ｐｉＣについて、以下の（３７）式の値が１のときに領域１と判定し、値が０のときに領域２と判定する。
【０１７４】
【数３５】
0006381137.tif 000036
【０１７５】
（ステップＳ３−３−５：境界平面についてクラスタ分割処理）
分割後のクラスタＣ−１とクラスタＣ−２について、再度ステップＳ３−３の入力とする。それぞれのクラスタは独立して処理をすればよいが、番号の小さい順番にＣ−１→Ｃ−２と逐次的に処理を行ってもよい。
【０１７６】
もし、分割後の注目クラスタＣ−１について、境界平面が存在しない場合には、注目クラスタＣ−１については処理を終了する。境界平面が存在するときには、注目クラスタＣ−１を更に分割処理し、再度ステップＳ３−３の入力とする。図９に示すように、ステップＳ３−３−５で、分割後の全てのクラスタの各々について、再度、ステップＳ３−３を実行して、領域分割処理を行う。
【０１７７】
（ステップＳ３−４：位置・大きさ推定処理）
ステップＳ３−４において、ステップＳ３−３で分割された領域分割後のクラスタについて、当該領域分割後のクラスタの３次元点群に基づいて、それぞれの中心位置および縦（上下）と左右（水平）方向の大きさを推定する。注目クラスタｃの分割後のクラスタ数をＦ、各クラスタを区別する番号をｆと表現すると、クラスタｆの点群を用いて、（６）式、及び（７）式から重心位置ｇｆと代表法線ベクトルｎｆと長軸方向ｕｆ、短軸方向ｖｆを求める。
【０１７８】
次に、代表法線ベクトルｎｆに垂直な平面上における、縦軸方向および横軸方向を決定する。縦軸方向とは、Ｚ軸方向を代表法線ベクトルｎｆに垂直な平面（ｕｆ，ｖｆ）に射影した方向
【０１７９】
【数３６】
0006381137.tif 000037
【０１８０】
として求まり、横軸方向
【０１８１】
【数３７】
0006381137.tif 000038
【０１８２】
はベクトルｎｆと方向
【０１８３】
【数３８】
0006381137.tif 000039
【０１８４】
の外積として求まる。
【０１８５】
【数３９】
0006381137.tif 000040
【０１８６】
注目クラスタｆの注目点をｐｉｆと表記すると、以下の（３９）式により長軸方向の長さＬｅｎｇＺ’および短軸方向の長さＬｅｎｇＹ’、中心位置の座標Ｃｏｒｒｄｉ（ｈａｌｆ＿Ｚ’ｆ）と短軸方向の中心位置座標Ｃｏｒｒｄｉ（ｈａｌｆ＿Ｙ’ｆ）が求まる。なお、長軸方向の長さ、及び短軸方向の長さは、クラスタの各軸方向の半分の長さである。
【０１８７】
【数４０】
0006381137.tif 000041
【０１８８】
標識クラスタｆの３次座標ベクトルＣｌｕｓｔｅｒｆＸＹＺは、以下の（４０）式により求まる。
【０１８９】
【数４１】
0006381137.tif 000042
【０１９０】
（ステップＳ３−５：終了判定処理）
ステップＳ３−５において、標識候補領域と判定された全てのクラスタについて領域分割処理をしたかを判定する。標識候補領域と判定された全てのクラスタについて処理を行っていない場合にはステップＳ３−１に戻る。全てのクラスタについて処理を終了した場合、ステップＳ３を終了して、分割後のクラスタを標識クラスタとして出力する。
【０１９１】
以上説明したように、第１の実施の形態に係る標識検出装置によれば、３次元点群に基づいて、局所形状情報を用いたクラスタリング処理を行って、３次元点群を含む平面領域と３次元点群を含む道路走行面とを検出し、検出された平面領域の各々について、周辺地物との相対位置を考慮して、標識候補領域であるか否かを判定し、標識候補領域の各々について、境界平面により分割可能であるか否かを判定し、分割可能であると判定された標識候補領域を境界平面により分割することにより、精度よく標識を検出することができる。
【０１９２】
[第２の実施の形態]
次に、第２の実施の形態に係る点群解析による標識検出装置の構成について説明する。なお、第１の実施の形態と同様の構成となる箇所については、同一符号を付して説明を省略する。
【０１９３】
図１２に示すように、第２の実施の形態においては、標識検出部１０４において平面領域検出部１２０と、標識候補領域判定部１２１と、標識領域分割処理部１２２と、標識形状識別部１２３と含んで構成されている。
【０１９４】
標識形状識別部１２３は、標識領域分割処理部１２２から供給される分割された３次元点群からなる標識候補領域の各々について、標識候補領域のスケールに応じて作成された、複数の幾何形状テンプレート（例えば、丸、三角、四角等）とのマッチングにより、標識候補領域の標識形状の種類を識別し、記憶部１０３に形状の識別結果として出力する。
【０１９５】
図１３に本実施の形態における標識検出装置の処理フローを示す。第１の実施の形態における標識検出装置の処理フローとの違いはステップＳ４が追加されている点である。
【０１９６】
以下、図１３及び図１４に示すステップＳ４について詳細に説明する。
【０１９７】
（ステップＳ４：形状識別処理）
ステップ４において、ステップ３で標識であると判定されたクラスタについて、複数の幾何形状テンプレートに基づいて、標識形状の識別を行う。本実施の形態において、標識形状は大きく分けて２種類と考える。一つは図１５に示すように中心位置を基準とした点対象な図形、もう一つは中心に位置を通る縦軸と横軸に線対象な図形である。
【０１９８】
（ステップＳ４−１：テンプレート形状当てはめ評価スコアの算出）
点対称な図形としては、円１種類、正三角形（上下）２種類の幾何形状テンプレートを用意し、線対象な図形として長方形１種類とひし形１種類の計５個を用いる。ただし、三角形の２種類は、三角形の１辺を横軸と平行とした三角形とし、この１辺に接していない頂点が縦軸方向の正と負の側に配置される正三角形２種類とした。
【０１９９】
このとき、点対象の図形では、標識クラスタの中心位置から距離Ｒ＿ｐｌａｔｅ＝ＬｅｎｇＺ’の位置に検出図形の輪郭が存在するようなテンプレートを生成する。線対称の図形においては、標識クラスタの中心位置から、縦軸方向にＲＺｐｌａｔｅ＝ＬｅｎｇＺ’の距離と横軸方向にＲＹ＿ｐｌａｔｅ＝ＬｅｎｇＹ’の距離に検出対象となる図形の輪郭線が存在するようなテンプレートを生成する。
【０２００】
図１５に示すように検出対象の輪郭線から距離ΔＲについて、内側領域（Ｒｅｇｉｏｎ１）と外側領域（Ｒｅｇｉｏｎ２）とを設定し、これらの領域において点群の有無を用いて、３次元点群のテンプレートマッチング評価を行う。評価関数をＥｍａｔｃｈは、図１５の輪郭線（破線）より内側の領域に点群が存在するときに評価値は大きくなり、外側の領域に点群が存在すると評価値が下がる。
【０２０１】
標識クラスタと判定されたクラスタの番号をｆ、クラスタｆに含まれる点において、代表法線方向に射影したときに、Ｒｅｇｉｏｎ１に含まれる点群をｐｉｆ１、Ｒｅｇｉｏｎ１に含まれる点群をｐｊｆ２、Ｒｅｇｉｏｎ１とＲｅｇｉｏｎ２の領域に含まれる点群数をそれぞれＮｕｍ１，Ｎｕｍ２とすると、テンプレート番号Ｇの評価関数Ｅｍａｔｃｈは以下の（４１）式により求まる。
【０２０２】
【数４２】
0006381137.tif 000043
【０２０３】
（ステップＳ４−２：形状判定処理）
標識形状は以下（４２）式に従って評価関数の値を最大にする幾何形状テンプレートを標識候補領域の標識形状であると判定する。
【０２０４】
【数４３】
0006381137.tif 000044
【０２０５】
なお、第２の実施の形態に係る標識検出装置１００の他の構成及び作用は第１の実施の形態と同様であるため説明を省略する。
【０２０６】
以上説明したように、第２の実施の形態に係る標識検出装置によれば、３次元点群に基づいて、局所形状情報を用いたクラスタリング処理を行って、３次元点群を含む平面領域と３次元点群を含む道路走行面とを検出し、検出された平面領域の各々について、周辺地物との相対位置を考慮して、標識候補領域であるか否かを判定し、標識候補領域の各々について、境界平面により分割可能であるか否かを判定し、分割可能であると判定された標識候補領域を境界平面により分割し、分割した標識候補領域の形状を識別することにより、精度よく標識を検出することができる。
【０２０７】
[第３の実施の形態]
次に、第３の実施の形態に係る点群解析による標識検出装置の構成について説明する。なお、第１及び第２の実施の形態と同様の構成となる箇所については、同一符号を付して説明を省略する。
【０２０８】
図１６に示すように、第３の実施の形態においては、標識検出装置１００は、機能的には、記憶部１０３と、標識検出部１０４と、柱状構造物検出部１０５を含んで構成されている。
【０２０９】
第３の実施の形態においては、標識候補領域判定部１２１は、記憶部１０３から３次元点群、及び柱状構造物の位置（ＸＹＺ座標）が供給される。供給された柱状構造物の位置を用いて、標識候補領域判定部１２１は判定処理を行う点が第１及び第２の実施の形態と異なる。
【０２１０】
柱状構造物検出部１０５は、標識の種類、位置、及び３次元点群の計測環境情報を検出する。計測環境情報とは、計測位置情報や走行軌跡であり、走行軌跡とはＭＭＳを搭載した車の軌跡を意味し、ＧＰＳ情報から取得される。ＧＰＳ情報が無い場合は、地図を代用して手動により走行車線位置を記録しても問題ない。なお、柱状構造物検出部１０５の検出方法には限定はなく、例えば非特許文献５を用いることで実現可能である。
【０２１１】
[非特許文献５]：新垣、島村、新井、谷口、「３次元点群からの局所形状と大域的な形状モデルを用いた柱状物体検出」、信学技報, vol. 112, no. 441, PRMU2012-131, pp. 7-12, 2013年2月.
【０２１２】
標識情報記憶部１１２には、標識検出部１０４で検出された標識の３次元座標位置と標識の平面の法線方向、並びに柱状構造物検出部１０５で検出された標識の種類、位置、及び３次元点群の計測環境情報が記憶される。
【０２１３】
上記第１及び第２の実施の形態においては、標識候補領域判定部１２１において、誤検出を抑制するために、低反射強度のクラスタについて、高反射強度のクラスタよりも閾値条件を厳しくしていた。
【０２１４】
第３の実施の形態における標識候補領域判定部１２１では、柱状構造物の位置を考慮することで更に判定条件を厳しくし、誤検出を抑制する。つまり、標識候補領域が柱状構造物に取り付けられたものであるか否かを判定する。
【０２１５】
標識候補領域判定部１２１は、柱状構造物検出部１０５から供給された柱状構造物について、柱状構造物を区別する番号をｑ、その柱状構造物の下端の位置座標をＰｏｌｅｑ、その柱状構造物の傾き方向をＶｑと表記すると、低反射強度のクラスタについての判定において、以下（４３）式の判定条件を追加する。
【０２１６】
【数４４】
0006381137.tif 000045
【０２１７】
閾値Ｔｈ＿ｄｉｓｔａｎｃｅｐｏｌｅより短い距離のとき、標識と判定する。本実施の形態においてＴｈ＿ｄｉｓｔａｎｃｅｐｏｌｅ＝１．０とした。ただし、非特許文献５においては、傾き方向を検出しているが、地図情報を用いて電柱や街灯等の柱状構造物の位置を取得した場合には、傾き方向およびＺ座標の値が不明である。その場合には、
【０２１８】
【数４５】
0006381137.tif 000046
【０２１９】
とし、Ｚ座標の値を０として代用する。
【０２２０】
（ステップＳ２：標識候補領域判定部）
上記図３に示す第３の実施の形態のステップＳ２では、入力された平面領域の各々について、周辺地物との相対位置及び柱状構造物との相対位置を考慮して、標識候補領域であるか否かを判定する。このとき、地物情報にＭＭＳの走行軌跡もしくは地図の道路位置情報が含まれている場合には、この道路走行面と標識候補領域の相対位置を考慮して判定が行われる。また、地物情報に柱状構造物の位置情報が含まれているため、柱状構造物との相対位置も考慮して標識領域であるか否かの判定を行う。
【０２２１】
なお、第３の実施の形態に係る標識検出装置１００の他の構成及び作用は第１及び第２の実施の形態と同様であるため説明を省略する。
【０２２２】
以上説明したように、第３の実施の形態に係る標識検出装置によれば、３次元点群に基づいて、局所形状情報を用いたクラスタリング処理を行って、３次元点群を含む平面領域と３次元点群を含む道路走行面とを検出し、検出された平面領域の各々について、周辺地物との相対位置及び柱状構造物との相対位置を考慮して、標識候補領域であるか否かを判定し、標識候補領域の各々について、境界平面により分割可能であるか否かを判定し、分割可能であると判定された標識候補領域を境界平面により分割し、分割した標識候補領域の形状を識別することにより、精度よく標識を検出することができる。
【０２２３】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【０２２４】
１００ 標識検出装置
１０１ 被写体計測部
１０２ 入力部
１０３ 記憶部
１０４ 標識検出部
１０５ 柱状構造物検出部
１１０ ３次元点群記憶部
１１１ 演算処理用パラメータ記憶部
１１２ 標識情報記憶部
１２０ 平面領域検出部
１２１ 標識候補領域判定部
１２２ 標識領域分割処理部
１２３ 標識形状識別部
【図１】
0006381137.tif 000047
【図２】
0006381137.tif 000048
【図３】
0006381137.tif 000049
【図４】
0006381137.tif 000050
【図５】
0006381137.tif 000051
【図６】
0006381137.tif 000052
【図７】
0006381137.tif 000053
【図８】
0006381137.tif 000054
【図９】
0006381137.tif 000055
【図１０】
0006381137.tif 000056
【図１１】
0006381137.tif 000057
【図１２】
0006381137.tif 000058
【図１３】
0006381137.tif 000059
【図１４】
0006381137.tif 000060
【図１５】
0006381137.tif 000061
【図１６】
0006381137.tif 000062