(57)【要約】【課題】簡易な処理で、３次元の点群データにおける３次元形状を解釈することができるようにする。【解決手段】点群取得部１８によって、３次元点群を取得する。ＣＧＡ変換部２０によって、３次元点群の各点を、ＣＧＡ空間上に変換する。染色体作成部２２によって、点及び無限遠基底の中から何れか３つ又は４つの遺伝子を選択して染色体を作成し、外積を用いて遺伝子を結合して幾何学構造を演算する。適応度算出部２４によって、３次元点群の各点について、幾何学構造との距離を内積演算により求め、染色体の適応度を算出する。更新部２８によって、染色体の適応度に基づいて、染色体の世代交代を行う。最適化部２６によって、適応度が最大化されるように、染色体の世代交代及び適応度の算出を繰り返して、適応度が最大となる染色体の幾何学構造が表す３次元形状を出力する。【選択図】図１
2014038495.tif 000002
【特許請求の範囲】
【請求項１】
３次元座標を持つ複数の点からなる点群データを取得する点群取得手段と、
前記点群データの前記複数の点を、ＣＧＡ（Ｃｏｎｆｏｒｍａｌ  Ｇｅｏｍｅｔｒｉｃ  Ａｌｇｅｂｒａ）空間上に変換する空間変換手段と、
前記ＣＧＡ空間上に変換された前記点群データの前記複数の点及び無限遠の基底の中から何れか３つ又は４つからなる組み合わせを選択し、前記選択した組み合わせを外積を用いて結合して、予め定められた複数種類の３次元形状の何れかを表す幾何学構造データを作成する作成手段と、
前記ＣＧＡ空間上に変換された前記点群データの前記複数の点の各々について、前記点と前記作成手段によって作成された幾何学構造データとの距離を内積演算により求め、前記複数の点の各々について求められた前記距離に基づいて、前記幾何学構造データの適応度を算出する適応度算出手段と、
前記幾何学構造データの適応度に基づいて、前記幾何学構造データに含まれる前記組み合わせを更新する更新手段と、
前記適応度が最大化されるように、前記更新手段による更新及び前記適応度算出手段による算出を繰り返して、前記幾何学構造データが表す３次元形状を出力する最適化手段と、
を含む３次元形状解釈装置。
【請求項２】
前記作成手段は、前記ＣＧＡ空間上に変換された前記点群データの前記複数の点及び無限遠の基底の中から何れか３つ又は４つを遺伝子の組み合わせとして選択して、３つ又は４つの遺伝子の組み合わせを含む複数の染色体を作成し、各染色体について、前記染色体の遺伝子の組み合わせを外積を用いて結合して前記幾何学構造データを作成し、
前記適応度算出手段は、前記複数の染色体の各々について、前記染色体の幾何学構造データの適応度を算出し、
前記更新手段は、前記適応度算出手段によって算出された前記複数の染色体の各々の適応度に基づいて、前記染色体の２つを選択し、前記選択された２つの染色体の遺伝子を交叉させることにより、前記複数の染色体を更新する請求項１記載の３次元形状解釈装置。
【請求項３】
前記幾何学構造データは、選択された３つの点と無限遠の基底とからなる組み合わせを外積で結合した、平面を表す幾何学構造データ、選択された３つの点と、前記選択された３つの点に基づいて追加された点とからなる組み合わせを外積で結合した、曲面を表す幾何学構造データ、前記選択された３つの点について高さ成分が一致するように変更した３つの点からなる組み合わせを外積で結合した、円柱を表す幾何学構造データ、及び前記選択された２つの点と無限遠の基底とからなる組み合わせを外積で結合した、直線を表す幾何学構造データの何れかである請求項１又は２記載の３次元形状解釈装置。
【請求項４】
前記適応度算出手段は、前記点群データの部分集合の点の各々について、前記点と前記作成手段によって作成された幾何学構造データとの距離を内積演算により求め、前記部分集合の点の各々について求められた前記距離に基づいて、前記幾何学構造データの適応度を算出し、
前記適応度算出手段による算出が繰り返される度に異なるように前記部分集合が決定される請求項１〜請求項３の何れか１項記載の３次元形状解釈装置。
【請求項５】
前記点群取得手段は、車両の周辺の３次元座標を持つ複数の点からなる点群データを取得し、
前記最適化手段は、前記適応度が最大化されるように、前記更新手段による更新及び前記適応度算出手段による算出を繰り返して、前記車両の周辺に存在する前記幾何学構造データが表す３次元形状を出力する請求項１〜請求項４の何れか１項記載の３次元形状解釈装置。
【請求項６】
前記車両の位置情報を測位する測位手段を更に含み、
前記点群データの各点の３次元座標は、前記測位手段によって測位された前記車両の位置情報を用いて求められる実座標系の３次元座標である請求項５記載の３次元形状解釈装置。
【請求項７】
前記最適化手段によって出力された前記幾何学構造データが表す３次元形状を、地図上に登録する地図登録手段を更に含む請求項６記載の３次元形状解釈装置。
【請求項８】
前記作成手段は、前記幾何学構造データを繰り返し作成し、
前記最適化手段によって前回出力された前記幾何学構造データに含まれる前記点の組み合わせを除外した前記点群データの前記複数の点、及び無限遠の基底の中から何れか３つ又は４つからなる組み合わせを選択し、前記幾何学構造データを作成する請求項１〜請求項７の何れか１項の記載の３次元形状解釈装置。
【請求項９】
コンピュータを、
３次元座標を持つ複数の点からなる点群データを取得する点群取得手段、
前記点群データの前記複数の点を、ＣＧＡ（Ｃｏｎｆｏｒｍａｌ  Ｇｅｏｍｅｔｒｉｃ  Ａｌｇｅｂｒａ）空間上に変換する空間変換手段、
前記ＣＧＡ空間上に変換された前記点群データの前記複数の点及び無限遠の基底の中から何れか３つ又は４つからなる組み合わせを選択し、前記選択した組み合わせを外積を用いて結合して、予め定められた複数種類の３次元形状の何れかを表す幾何学構造データを作成する作成手段、
前記ＣＧＡ空間上に変換された前記点群データの前記複数の点の各々について、前記点と前記作成手段によって作成された幾何学構造データとの距離を内積演算により求め、前記複数の点の各々について求められた前記距離に基づいて、前記幾何学構造データの適応度を算出する適応度算出手段、
前記幾何学構造データの適応度に基づいて、前記幾何学構造データに含まれる前記組み合わせを更新する更新手段、及び
前記適応度が最大化されるように、前記更新手段による更新及び前記適応度算出手段による算出を繰り返して、前記幾何学構造データが表す３次元形状を出力する最適化手段
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元形状解釈装置及びプログラムに係り、特に、３次元の点群データから、３次元形状を解釈する３次元形状解釈装置及びプログラムに関する。
【背景技術】
【０００２】
従来より、物体の３次元パラメトリック形状モデルを定義し、点群との距離が最小となるような対応付けを探索により求め、物体の位置姿勢を認識する方法が知られている（非特許文献１）。
【０００３】
カメラとレーザスキャナを備えた車両で市街地を走行し、高精細な道路の3次元点群を取得する俯瞰画像生成方法が知られている（特許文献１）。
【０００４】
点群から局所領域ごとに平面当てはめをし、それらを連結することで3次元物体の輪郭を算出する点群データ処理装置が知られている（特許文献２）。
【０００５】
点群に三角ポリゴンを当てはめ、それらに平面方程式または曲面方程式をあてはめることで形状判定する三次元形状の自動生成装置が知られている（特許文献３）。
【０００６】
また、当てはめる形状をConformal Geometric Algebra空間の式で表現し、係数を推定することにより、「直線と円」「平面と球」など異なる形状を共通のモデルで表し、当てはめ結果をもとに形状を分類する方法が知られている（非特許文献２、３）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１２−０１８１７０号公報
【特許文献２】特開２０１２−１３６６０号公報
【特許文献３】特開２００４−２７２４５９号公報
【非特許文献】
【０００８】
【非特許文献１】P.J. Besl and H.D. McKay, "A method for registration of 3-D shapes", Trans. PAMI vol.14, no.2, pp.239-256, 1992.
【非特許文献２】D. Hildenbrand, “Geometric computing in computer graphics using conformal geometric algebra", Computers and Graphics, vol.29 (2005), no.5, pp.802-810.
【非特許文献３】ファンミントゥン，橘完太，吉川大弘，古橋武，"Conformal Geometric Algebraを用いた近似方法の提案とその応用"，第１回コンピューテーショナル・インテリジェンス研究会予稿集，pp. 29-36, 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上述したように、点群からの物体検出に関する先行文献が多く存在するが、複雑な計算処理が必要であり、実装が容易ではない。
【００１０】
上記の非特許文献１に記載の方法では、複雑な形状の物体を点群と対応付けることができるが、あらかじめ形状モデルを物体ごとに個別に作成する必要があり、幾何演算や探索処理が複雑となる、という問題がある。
【００１１】
上記の特許文献１に記載の方法は、点群の取得方法および道路画像の生成法であるが、構造物を構造物として認識するためには、認識処理が別途必要である、という問題がある。
【００１２】
上記の特許文献２に記載の技術では、局所平面当てはめのためにノイズ判定する必要があり、局所平面の連結処理が必要である、という問題がある。
【００１３】
上記の特許文献３に記載の技術では、平面・曲面がそれぞれ別々の方程式で定義されているため、それぞれの方程式に対し当てはめ誤差を評価しなければならない、という問題がある。
【００１４】
上記の非特許文献２、３に記載の技術では、Conformal Geometric Algebraを利用することで点群から特定の形状を抽出することが可能である。しかし、形状当てはめに最小二乗法を用いているため、ノイズを含む３次元点群に適用する場合、外れ値の影響で位置の精度や物体の識別性能が低下する。また、３次元点群に適用する場合、上記の非特許文献２、３記載の共通モデルで表すことのできる物体は平面と球の２種類であり、直線、円、円柱などは表現式が異なる（Conformal Geometric Algebra空間上で高次の係数が必要）ため扱うことができない、という問題がある。
【００１５】
本発明は、上記の問題点を解決するためになされたもので、簡易な処理で、３次元の点群データにおける３次元形状を解釈することができる３次元形状解釈装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
上記の目的を達成するために本発明に係る３次元形状解釈装置は、３次元座標を持つ複数の点からなる点群データを取得する点群取得手段と、前記点群データの前記複数の点を、ＣＧＡ（Ｃｏｎｆｏｒｍａｌ  Ｇｅｏｍｅｔｒｉｃ  Ａｌｇｅｂｒａ）空間上に変換する空間変換手段と、前記ＣＧＡ空間上に変換された前記点群データの前記複数の点及び無限遠の基底の中から何れか３つ又は４つからなる組み合わせを選択し、前記選択した組み合わせを外積を用いて結合して、予め定められた複数種類の３次元形状の何れかを表す幾何学構造データを作成する作成手段と、前記ＣＧＡ空間上に変換された前記点群データの前記複数の点の各々について、前記点と前記作成手段によって作成された幾何学構造データとの距離を内積演算により求め、前記複数の点の各々について求められた前記距離に基づいて、前記幾何学構造データの適応度を算出する適応度算出手段と、前記幾何学構造データの適応度に基づいて、前記幾何学構造データに含まれる前記組み合わせを更新する更新手段と、前記適応度が最大化されるように、前記更新手段による更新及び前記適応度算出手段による算出を繰り返して、前記幾何学構造データが表す３次元形状を出力する最適化手段と、を含んで構成されている。
【００１７】
本発明に係るプログラムは、コンピュータを、３次元座標を持つ複数の点からなる点群データを取得する点群取得手段、前記点群データの前記複数の点を、ＣＧＡ（Ｃｏｎｆｏｒｍａｌ  Ｇｅｏｍｅｔｒｉｃ  Ａｌｇｅｂｒａ）空間上に変換する空間変換手段、前記ＣＧＡ空間上に変換された前記点群データの前記複数の点及び無限遠の基底の中から何れか３つ又は４つからなる組み合わせを選択し、前記選択した組み合わせを外積を用いて結合して、予め定められた複数種類の３次元形状の何れかを表す幾何学構造データを作成する作成手段、前記ＣＧＡ空間上に変換された前記点群データの前記複数の点の各々について、前記点と前記作成手段によって作成された幾何学構造データとの距離を内積演算により求め、前記複数の点の各々について求められた前記距離に基づいて、前記幾何学構造データの適応度を算出する適応度算出手段、前記幾何学構造データの適応度に基づいて、前記幾何学構造データに含まれる前記組み合わせを更新する更新手段、及び前記適応度が最大化されるように、前記更新手段による更新及び前記適応度算出手段による算出を繰り返して、前記幾何学構造データが表す３次元形状を出力する最適化手段として機能させるためのプログラムである。
【００１８】
本発明によれば、点群取得手段によって、３次元座標を持つ複数の点からなる点群データを取得する。空間変換手段によって、前記点群データの前記複数の点を、ＣＧＡ（Ｃｏｎｆｏｒｍａｌ  Ｇｅｏｍｅｔｒｉｃ  Ａｌｇｅｂｒａ）空間上に変換する。
【００１９】
そして、作成手段によって、前記ＣＧＡ空間上に変換された前記点群データの前記複数の点及び無限遠の基底の中から何れか３つ又は４つからなる組み合わせを選択し、前記選択した組み合わせを外積を用いて結合して、予め定められた複数種類の３次元形状の何れかを表す幾何学構造データを作成する。適応度算出手段によって、前記ＣＧＡ空間上に変換された前記点群データの前記複数の点の各々について、前記点と前記作成手段によって作成された幾何学構造データとの距離を内積演算により求め、前記複数の点の各々について求められた前記距離に基づいて、前記幾何学構造データの適応度を算出する。
【００２０】
そして、更新手段によって、前記幾何学構造データの適応度に基づいて、前記幾何学構造データに含まれる前記組み合わせを更新する。最適化手段によって、前記適応度が最大化されるように、前記更新手段による更新及び前記適応度算出手段による算出を繰り返して、前記幾何学構造データが表す３次元形状を出力する。
【００２１】
このように、点群データの複数の点を、ＣＧＡ空間上に変換し、複数の点又は無限遠の基底の組み合わせを選択し外積を用いて結合して、３次元形状を表す幾何学構造データを作成し、点群データの点と幾何学構造データとの距離を内積演算により求めて、幾何学構造データの適応度を算出し、幾何学構造データの適応度に基づいて、幾何学構造データを更新し、適応度が最大化されるように、幾何学構造データの更新及び適応度の算出を繰り返して、幾何学構造データが表す３次元形状を出力することにより、簡易な処理で、３次元の点群データにおける３次元形状を解釈することができる。
【００２２】
本発明に係る作成手段は、前記ＣＧＡ空間上に変換された前記点群データの前記複数の点及び無限遠の基底の中から何れか３つ又は４つを遺伝子の組み合わせとして選択して、３つ又は４つの遺伝子の組み合わせを含む複数の染色体を作成し、各染色体について、前記染色体の遺伝子の組み合わせを外積を用いて結合して前記幾何学構造データを作成し、前記適応度算出手段は、前記複数の染色体の各々について、前記染色体の幾何学構造データの適応度を算出し、前記更新手段は、前記適応度算出手段によって算出された前記複数の染色体の各々の適応度に基づいて、前記染色体の２つを選択し、前記選択された２つの染色体の遺伝子を交叉させることにより、前記複数の染色体を更新するようにすることができる。このように、遺伝子アルゴリズムを用いて、３次元の点群データにおける３次元形状を精度よく解釈することができる。
【００２３】
上記の幾何学構造データは、選択された３つの点と無限遠の基底とからなる組み合わせを外積で結合した、平面を表す幾何学構造データ、選択された３つの点と、前記選択された３つの点に基づいて追加された点とからなる組み合わせを外積で結合した、曲面を表す幾何学構造データ、前記選択された３つの点について高さ成分が一致するように変更した３つの点からなる組み合わせを外積で結合した、円柱を表す幾何学構造データ、及び前記選択された２つの点と無限遠の基底とからなる組み合わせを外積で結合した、直線を表す幾何学構造データの何れかである。
【００２４】
本発明の適応度算出手段は、前記点群データの部分集合の点の各々について、前記点と前記作成手段によって作成された幾何学構造データとの距離を内積演算により求め、前記部分集合の点の各々について求められた前記距離に基づいて、前記幾何学構造データの適応度を算出し、前記適応度算出手段による算出が繰り返される度に異なるように前記部分集合が決定されるようにすることができる。これによって、計算量の増大を抑制して、３次元の点群データにおける３次元形状を解釈することができる。
【００２５】
本発明に係る点群取得手段は、車両の周辺の３次元座標を持つ複数の点からなる点群データを取得し、前記最適化手段は、前記適応度が最大化されるように、前記更新手段による更新及び前記適応度算出手段による算出を繰り返して、前記車両の周辺に存在する前記幾何学構造データが表す３次元形状を出力するようにすることができる。
【００２６】
本発明に係る３次元形状解釈装置は、前記車両の位置情報を測位する測位手段を更に含み、前記点群データの各点の３次元座標は、前記測位手段によって測位された前記車両の位置情報を用いて求められる実座標系の３次元座標であるようにすることができる。
【００２７】
上記の３次元形状解釈装置は、前記最適化手段によって出力された前記幾何学構造データが表す３次元形状を、地図上に登録する地図登録手段を更に含むようにすることができる。
【００２８】
本発明に係る作成手段は、前記幾何学構造データを繰り返し作成し、前記最適化手段によって前回出力された前記幾何学構造データに含まれる前記点の組み合わせを除外した前記点群データの前記複数の点、及び無限遠の基底の中から何れか３つ又は４つからなる組み合わせを選択し、前記幾何学構造データを作成するようにすることができる。
【発明の効果】
【００２９】
以上説明したように、本発明の３次元形状解釈装置及びプログラムによれば、点群データの複数の点を、ＣＧＡ空間上に変換し、複数の点又は無限遠の基底の組み合わせを選択し外積を用いて結合して、３次元形状を表す幾何学構造データを作成し、点群データの点と幾何学構造データとの距離を内積演算により求めて、幾何学構造データの適応度を算出し、幾何学構造データの適応度に基づいて、幾何学構造データを更新し、適応度が最大化されるように、幾何学構造データの更新及び適応度の算出を繰り返して、幾何学構造データが表す３次元形状を出力することにより、簡易な処理で、３次元の点群データにおける３次元形状を解釈することができる、という効果が得られる。
【図面の簡単な説明】
【００３０】
【図１】本発明の実施の形態に係る３次元形状解釈装置を示すブロック図である。
【図２】ＣＧＡ空間を説明するための図である。
【図３】基底間の内積を説明するための図である。
【図４】（Ａ）球を示す図、（Ｂ）平面を示す図、（Ｃ）円を示す図、及び（Ｄ）直線を示す図である。
【図５】世代交代のときの処理を説明するための図である。
【図６】本発明の実施の形態に係る３次元形状解釈装置における３次元形状解釈処理ルーチンの内容を示すフローチャートである。
【図７】（Ａ）ステレオカメラにより入力された片方の画像の例を示す図、及び（Ｂ）構造物が登録された地図を表示した例を示す図である。
【発明を実施するための形態】
【００３１】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００３２】
図１に示すように、本発明の実施の形態に係る３次元形状解釈装置１０は、道路領域を含む自車両前方を撮像して画像を出力する撮像装置１２と、自車両位置を測定するＧＰＳを含む測位装置１４と、撮像装置１２から得られる画像及び測位装置１４による測位情報に基づいて、自車両前方の構造物の３次元形状を抽出し、地図データ上に登録する処理を実行するコンピュータ１６と、を含んで構成されている。
【００３３】
撮像装置１２は、車両に搭載され、道路領域を含む自車両前方を撮像してステレオ画像を出力する。撮像装置１２は、自車両前方を撮像し、画像の画像信号を生成する２つの撮像部（図示省略）と、２つの撮像部で生成された画像信号をＡ／Ｄ変換するＡ／Ｄ変換部（図示省略）と、Ａ／Ｄ変換された画像信号を一時的に格納するための画像メモリ（図示省略）とを備えている。撮像装置１２は、撮像した２枚の画像を、ステレオ画像としてコンピュータ１６に出力する。
【００３４】
測位装置１４は、自車両に搭載されたＧＰＳ装置を用いて、実座標系における自車両の位置を測定し、測定結果をコンピュータ１６に出力する。
【００３５】
コンピュータ１６は、ＣＰＵと、ＲＡＭと、後述する３次元形状解釈処理ルーチンを実行するためのプログラムを記憶したＲＯＭと、これらを接続するバスとを含んで構成されている。このコンピュータ１６をハードウエアとソフトウエアとに基づいて定まる機能実現手段毎に分割した機能ブロックで説明すると、点群取得部１８と、ＣＧＡ変換部２０と、染色体作成部２２と、適応度算出部２４と、最適化部２６と、更新部２８と、地図登録部３０と、実座標系の道路平面を表わす地図データを記憶する記憶部３２と、を含んだ構成で表すことができる。
【００３６】
点群取得部１８は、撮像装置１２によって撮像されたステレオ画像から、エッジ点を抽出し、ステレオマッチングにより得られた視差から、撮像装置１２を基準としたエッジ点の３次元位置を求める。また、点群取得部１８は、所定の距離内の複数のフレームのステレオ画像について求められた複数の３次元点を、複数のフレームの各々に対応して測位装置１４により得られた測位情報を用いて統合することにより、実空間上の３次元座標を持つ３次元点群を求める。
【００３７】
なお、画像中のエッジ点は従来既知の手法を用いて抽出すればよく、例えば、Cannyのアルゴリズム等により抽出する。
【００３８】
また、撮像装置１２を基準とした３次元点の位置は、キャリブレーションされたカメラを用い、以下の文献の方法により求めることができる。
【００３９】
参考文献：Ｍ  Ｂｅｒｔｏｚｚ，Ａ  Ｂｒｏｇｇｉ，“Ｓｔｅｒｅｏ  ｉｎｖｅｒｓｅ  ｐｅｒｓｐｅｃｔｉｖｅ  ｍａｐｐｉｎｇ：ｔｈｅｏｒｙ  ａｎｄ  ａｐｐｌｉｃａｔｉｏｎｓ”，ｉｍａｇｅ  Ｖｉｓ．Ｃｏｍｐｕｔ．，ｖｏｌ．８，ｎｏ．１６，ｐｐ．５８５−５９０，１９９８．
【００４０】
なお、ステレオカメラである撮像装置１２の代わりに、レーザレーダを用いて、点群を取得してもよい。
【００４１】
ＣＧＡ変換部２０は、３次元点群の各点について、Ｃｏｎｆｏｒｍａｌ  Ｇｅｏｍｅｔｒｉｃ  Ａｌｇｅｂｒａ（ＣＧＡ）空間に変換する。まず、３次元点（ｘ１、ｘ２、ｘ３）を３つの基底（ｅ１、ｅ２、ｅ３）を用いて以下の（１）式で表す。
【００４２】
【数１】
2014038495.tif 000003
【００４３】
そして、基底を２つ（ｅ∞，ｅO）追加した５次元のＣＧＡ空間上で、３次元点群の各点は、以下の（２）式で表現される（図２参照）。
【００４４】
【数２】
2014038495.tif 000004
【００４５】
変換後のＣＧＡ空間では、外積演算（Ｏｕｔｅｒ  ｐｒｏｄｕｃｔ）により点群を通る図形が求められ、内積演算（ｉｎｎｅｒ  ｐｒｏｄｕｃｔ）により図形間の距離が求められる、という利点がある。この性質を用いることで、点群への幾何学構造の当てはめが容易になる。
【００４６】
Ｃｏｎｆｏｒｍａｌ  Ｇｅｏｍｅｔｒｉｃ  Ａｌｇｅｂｒａの詳細は以下の文献に記述されている。
【００４７】
参考文献：Ｌ．Ｄｏｒｓｔ，Ｄ．Ｆｏｎｔｉｊｎｅ，ａｎｄ  Ｓ．Ｍａｎｎ，Ｇｅｏｍｅｔｒｉｃ  Ａｌｇｅｂｒａ  ｆｏｒ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ−Ａｎ  Ｏｂｊｅｃｔ  −  ｏｒｉｅｎｔｅｄ  ａｐｐｒｏａｃｈ  ｔｏ  Ｇｅｏｍｅｔｒｙ（Ｅｌｓｅｖｉｅｒ−Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ  Ｐｕｂｌｉｓｈｅｒｓ，  Ｓａｎ  Ｆｒａｎｃｉｓｃｏ，２００７）
【００４８】
ここで、ＣＧＡ空間での内積演算、外積演算、及びデュアル演算について説明する。
【００４９】
まず、基底間の内積は、以下の（３）式で表される。
【００５０】
【数３】
2014038495.tif 000005
【００５１】
上記（３）式の内積演算を表で表わすと、図３のようになる。
【００５２】
デュアル演算（*）は、以下の（４）式で表される。
【００５３】
【数４】
2014038495.tif 000006
【００５４】
また、外積演算（∧）では、任意のＣＧＡ点 a, b, c とスカラーβに対し、以下の（５）式〜（９）式が成立する。
【００５５】
【数５】
2014038495.tif 000007
【００５６】
また、ＣＧＡ点 a, bの外積演算の結果と基底との内積は、以下の（１０）式で表される。
【００５７】
【数６】
2014038495.tif 000008
【００５８】
ＣＧＡ点に外積演算（∧）とデユアル演算（*）を適用することで、多様な図形を表現することが可能となる。
【００５９】
例えば、図４（Ａ）に示すように点Ｐ１、Ｐ２、Ｐ３、Ｐ４を通る球は、以下の（１１）式で表される。
【００６０】
【数７】
2014038495.tif 000009
【００６１】
図４（Ｂ）に示すように、点Ｐ１、Ｐ２、Ｐ３点を通る平面は以下の（１２）式で表される。
【００６２】
【数８】
2014038495.tif 000010
【００６３】
図４（Ｃ）に示すように、点Ｐ１、Ｐ２、Ｐ３を通る円は以下の（１３）式で表される。
【００６４】
【数９】
2014038495.tif 000011
【００６５】
図４（Ｄ）に示すように、点Ｐ１、Ｐ２を通る直線は以下の（１４）式で表される。
【００６６】
【数１０】
2014038495.tif 000012
【００６７】
染色体作成部２２は、ＣＧＡ空間上に変換された３次元点群と無限遠点に対応する基底ｅ∞とを合わせた集合の中から、いずれか３つ又は４つを遺伝子として選択して、選択された遺伝子の組み合わせを含む染色体を複数作成し、各染色体について、染色体の遺伝子の点又は基底を外積により結合して、染色体が表わす幾何学構造を演算する。点のあらゆる組み合わせの中で最適な染色体を遺伝的アルゴリズムにより推定することで、３次元点群に当てはまる物体の３次元形状を推定することができる。
【００６８】
選択した遺伝子の組み合わせに応じて、物体（幾何学構造）の種類属性が（平面・曲面・円柱・直線）のいずれかから決まり、選択した遺伝子の外積演算及びデュアル演算により、当該種類属性の幾何学構造を演算する。当てはまる幾何学構造を得るための式は以下の表１にまとめられる。
【００６９】
【表１】
2014038495.tif 000013
【００７０】
選択した遺伝子の組み合わせが、表１の遺伝子の組み合わせに該当しない場合には、再度、３つ又は４つを遺伝子として選択する。
【００７１】
また、一部の種類属性では、計算簡単化のための特別処置を施す。
【００７２】
具体的には、曲面について、球により近似するものとし、３つの点Ｐ１Ｐ２Ｐ３に基づいて、球の中心が撮像装置１２と同じ高さになるような制約を与える４つ目の点Ｐ４を追加し、外積演算及びデュアル演算により、幾何学構造を演算する。
【００７３】
円柱について、道路面と平行な円により近似するものとし、点Ｐ１と高さ成分ｘ２が一致するように点Ｐ２Ｐ３を鉛直方向に平行移動させた点Ｐ’２Ｐ’３を用い、外積演算及びデュアル演算により、幾何学構造を演算する。
【００７４】
曲面と円柱の区別は、遺伝子として選択された３つの点Ｐ１Ｐ２Ｐ３が所定の距離範囲内にあるかどうかにより区別される。このとき電柱の直径（４０ｃｍ程度）を閾値とし、点Ｐ１Ｐ２Ｐ３の間の距離の最大値が、閾値以下である場合には、円柱であると区別し、点Ｐ１Ｐ２Ｐ３の間の距離の最大値が、閾値より大きい場合には、曲面であると区別する。
【００７５】
適応度算出部２４は、染色体の幾何学構造が３次元点群に当てはまるかどうかを判定するために、染色体の幾何学構造と点との距離を内積（・）により求め、どれだけの点が当該幾何学構造と至近距離にあるかを以って、染色体の適応度とする。
【００７６】
ただし、染色体の幾何学構造Ｓと点Ｐとの距離は以下の（１５）式に従って計算される。
【００７７】
【数１１】
2014038495.tif 000014
【００７８】
なお、円柱は円として表現されているため、円と同じ平面上で点と円の距離を計算する。
【００７９】
距離が所定の閾値以下となる点群（近傍点）の数Ｎを適応度とする。適応度を算出するとき、全ての点群との距離を求めると、点群の数と遺伝的アルゴリズムの世代交代数が多い場合に計算量が膨大となる。そこで、本実施の形態では、３次元点群の小規模な部分集合を定め、部分集合に含まれる点群に対し、近傍点数Ｎを求める。
【００８０】
例えば、３次元点群の各点にインデクスを付与し、ｋ番目の世代では、最適個体を取り出すまでの世代交代数Ｋでインデクスを割ったときの余りがｋになる点のみを部分集合に含める。
【００８１】
ただし、最適個体を取り出すＫ世代では、全ての３次元点群に対して近傍点数を求めて、適応度を計算する。
【００８２】
最適化部２６は、適応度を最大化する染色体を遺伝的アルゴリズムに基づき求めることで、自車両前方の走路中の構造物の３次元形状を抽出する。
【００８３】
具体的には、最適化部２６は、図５に示すように、世代交代時に子孫を残す個体（染色体）を、個体集合（染色体の集合）から２つ選択する。個体の選択は適応度で重み付けしたルーレット選択により行う。
【００８４】
更新部２８は、上記図５に示すように、選択された２つの染色体の遺伝子（点および種類属性）を交叉させる。このとき、新たに生成される次世代の染色体において、４つの遺伝子の何れかが重複しないように交叉を行う。世代交代時に所定の低い確率で突然変異を行い、選択された染色体の一部の遺伝子を乱数で初期化することも有効である。
【００８５】
最適化部２６は、所定回数Ｋだけ世代交代させた場合には、各染色体の適応度に基づいて、適応度が最大となる最適個体(染色体)を抽出し、抽出された染色体の幾何学構造を、自車両前方の走路の構造物の３次元形状とする。対象範囲内に複数の構造物が含まれている可能性があるので、最適個体を取り出した後、染色体作成部２２の処理へ戻り、上記の処理を繰り返す。そのたびに、取り出した最適個体が表す幾何学構造に含まれる点群（当該幾何学構造との距離が閾値以下の点群）を除外していき、いずれの幾何学構造の解釈にも含まれない点群が十分少なくなったときに処理を中断する。最適個体の近傍点数が所定の閾値を下回った場合も処理を中断する。
【００８６】
最適化部２６の結果として得られた最適個体群は、平面・曲面・円柱・直線のいずれかの構造物を表す。
【００８７】
平面はガードレールや壁のみならず、道路平面や歩道平面も含まれる。特に道路平面は点の絶対数が多いため、他の構造物よりも先に抽出される場合が多い。
【００８８】
ガードレールと縁石は、道路平面を基準とした近傍点の高さ分布をもとに区別することができる。近傍点の高さの最頻値が所定の閾値を上回る場合、ガードレールと判断し、そうでない場合、縁石と判断する。
【００８９】
地図登録部３０は、上記のように構造物の種別を判断すると共に、当該構造物を、記憶部３２に記憶されている地図データ上に、構造物の種別と共に登録する。このとき、最適個体を構成する遺伝子（点群）を地図データ上に登録してもよく、一般的な図形の方程式に変換して登録してもよい。いずれの場合も解釈結果を地図データ上に登録し、後処理で利用することができる。
【００９０】
次に、本発明の実施の形態に係る３次元形状解釈装置１０の作用について説明する。まず、撮像装置１２によって、自車両前方の撮像が開始されると共に、測位装置１４によって、自車両の位置が随時測定されると、コンピュータ１６において、図６に示す３次元形状解釈処理ルーチンが繰り返し実行される。
【００９１】
ステップ１００で、測位装置１４で得られた所定の距離範囲分の測位情報、及び撮像装置１２で撮像された同一の距離範囲分の複数のフレームのステレオ画像を取得する。
【００９２】
次に、ステップ１０２で、上記ステップ１００で取得した各フレームのステレオ画像から、エッジ点を抽出する。ステップ１０４では、上記ステップ１０２で抽出した各フレームのステレオ画像のエッジ点群の各点について３次元位置を求めると共に、上記ステップ１００で取得した測位情報を用いて、各フレームのエッジ点群を統合して、３次元点群とする。
【００９３】
そして、ステップ１０６において、上記（１）式、（２）式に従って、上記ステップ１０４で得られた３次元点群の各点を、ＣＧＡ空間へ変換する。ステップ１０８では、世代を示す変数ｋを初期値である１に設定する。
【００９４】
次のステップ１１０では、ＣＧＡ空間に変換された３次元点群及び基底ｅ∞から、３つ又は４つの遺伝子を選択し、物体の種類属性に応じた遺伝子の組み合わせからなる染色体を所定個作成する。そして、各染色体について、遺伝子である点または基底を外積で結合し、デュアル演算を行うことにより、幾何学構造を得るための式を演算する。
【００９５】
ステップ１１２では、世代ｋに基づいて３次元点群の部分集合を決定し、上記ステップ１１０で作成した各染色体について、上記（１５）式に従って、決定した部分集合の各点との距離を算出し、距離が閾値以下となる点の数を、適応度として求める。なお、世代がＫである場合には、３次元点群の全ての点を対象として、適応度を求めるようにする。
【００９６】
次のステップ１１４では、ｋが、最適個体を抽出するための世代交代数Ｋ未満であるか否かを判定する。ｋがＫ未満である場合には、ステップ１１６において、ｋを１だけインクリメントする。ステップ１１８では、上記ステップ１１２で算出した適応度に基づいて、２つの染色体を選択し、選択された２つの染色体の遺伝子を交叉させて、所定個の染色体を更新する。そして、各染色体について、遺伝子である点または基底を外積で結合し、デュアル演算を行うことにより、幾何学構造を得るための式を演算し、上記ステップ１１２へ戻る。
【００９７】
一方、ｋがＫに到達した場合には、ステップ１２０へ進み、上記ステップ１１２で算出した適応度に基づいて、最適個体となる染色体を抽出する。また、３次元点群から、抽出された染色体の幾何学構造に含まれる点群を求め、求められた点群を３次元点群から除外する。
【００９８】
ステップ１２２では、遺伝子アルゴリズムの処理を中断するか否かを判定する。処理を中断しない場合には、上記ステップ１０８へ戻る。一方、処理を中断する場合には、ステップ１２４において、上記ステップ１２０で抽出された各最適個体の染色体の幾何学構造について、構造物の種別を判断し、当該幾何学構造（３次元形状の方程式又は３次元形状を構成する点群）を構造物の種別と共に地図データ上に登録して、３次元形状解釈処理ルーチンを終了する。
【００９９】
たとえば、図７（Ａ）に示すようなステレオ画像が入力された場合には、図７（Ｂ）に示すように、抽出された幾何学構造が地図データ上に登録される。
【０１００】
以上説明したように、本発明の実施の形態の３次元形状解釈装置によれば、ステレオ画像から取得した３次元点群の各点を、ＣＧＡ空間上に変換し、複数の点又は無限遠の基底を遺伝子として選択して染色体を作成し、染色体の遺伝子を外積を用いて結合し、かつ、デュアル演算を行って、３次元形状を表す幾何学構造を演算し、３次元点群の点と幾何学構造との距離を内積演算により求めて、染色体の適応度を算出し、染色体の適応度に基づいて、染色体の世代交代を行って更新し、適応度が最大化されるように、染色体の世代交代及び適応度の算出を繰り返して、適応度が最大となる染色体の幾何学構造が表す３次元形状を出力することにより、簡易な処理で、３次元点群における３次元形状を解釈することができる。
【０１０１】
また、ステレオ画像から得られた３次元点群をConformal Geometric Algebra空間に射影すると、平面や曲面など異なる形状の物体を同一形式で表すことができるため、電柱やガードレールなど異種形状の物体が混在する環境下においても、物体抽出や形状分類が容易に行える。Conformal Geometric Algebra空間では、点群から物体を抽出する処理を、点群（または基底）の外積演算を用い単純に記述できるため、画一的な最適化処理の枠組みにより物体抽出できる。従って、測位情報とステレオ画像により得た３次元点群から簡易な処理で道路上の物理境界（ガードレール・縁石・電柱）を解析できる。また、最適化処理を反復するたけで、走路の３次元構造（道路平面、歩道平面、ガードレール、縁石、電柱）が順次抽出され、地図上に登録することができる。
【０１０２】
また、走路が直線か曲線か（曲率等）の知識が、最適化の結果により得ることができるため、走路形状に関する事前知識やモデルを必要としない。
【０１０３】
また、従来技術における５次元のＣＧＡ空間では、点・球・平面を以下の共通式により表現できる。
【０１０４】
【数１２】
2014038495.tif 000015
【０１０５】
上記の非特許文献３では、上式の５つの係数（ｘ１、ｘ２、ｘ３、ｘ∞、ｘＯ）を最小二乗法により推定することで、球または平面の自動分類を試みている。しかし、非特許文献３の技術では、球と平面以外の物体は、高次の係数（例：ｅ１∧ｅ２）を考慮しなければならず、この方式で扱うことはできない、という問題がある。また、最小二乗法は外れ値の影響を受けやすいという問題がある。ステレオの３次元点群はノイズを多く含むため、ノイズを適切に除去しない限り形状分類を誤る可能性がある。
【０１０６】
一方、本実施の形態では、係数推定の必要がなく、少数の点のみから物体を定めることができる。
【０１０７】
なお、上記の実施の形態では、３次元形状解釈装置を車両に搭載した場合を例に説明したが、これに限定されるものではなく、車両以外のもの、例えばロボットに搭載してもよい。
【０１０８】
また、遺伝的アルゴリズムを用いて、最適な幾何学構造を求める場合を例に説明したが、遺伝的アルゴリズム以外の方法を用いて、幾何学構造を３次元点群に当てはめ、最適な幾何学構造を求めるようにしてもよい。
【０１０９】
本発明のプログラムは、記憶媒体に格納して提供するようにしてもよい。
【符号の説明】
【０１１０】
１０   ３次元形状解釈装置
１２   撮像装置
１４   測位装置
１６   コンピュータ
１８   点群取得部
２０   ＣＧＡ変換部
２２   染色体作成部
２４   適応度算出部
２６   最適化部
２８   更新部
３０   地図登録部
【図２】
2014038495.tif 000016
【図３】
2014038495.tif 000017
【図６】
2014038495.tif 000018
【図１】
2014038495.tif 000019
【図４】
2014038495.tif 000020
【図５】
2014038495.tif 000021
【図７】
2014038495.tif 000022