(57)【要約】方法は、まず３次元（３Ｄ）点の集合を距離場に変換することによって、プリミティブ形状をこの３Ｄ点の集合にフィッティングする。距離場における各要素は、３Ｄ点の集合における最近傍点への距離に関連付けられる。２つ以上の候補の集合は、プリミティブ形状から仮定され、距離場を用いて、候補ごとにスコアが求められる。次に、３Ｄ点にフィッティングするプリミティブ形状は、候補からそれらのスコアに従って、選択される。【選択図】図１
2016523394.tif 000002
【特許請求の範囲】
【請求項１】
３次元（３Ｄ）点の集合にプリミティブ形状をフィッティングする方法であって、
前記３Ｄ点の集合を距離場に変換するステップであって、前記距離場内の各要素は前記３Ｄ点の集合における最近傍点への距離に関連付けられる、ステップと、
前記プリミティブ形状の２つ以上の候補の集合を仮定するステップと、
前記距離場を用いて、候補ごとのスコアを求めるステップと、
前記スコアに従って、前記３Ｄ点にフィッティングする前記プリミティブ形状として前記候補を選択するステップと、
を備え、
前記ステップは、プロセッサにおいて実行される、
３Ｄ点の集合にプリミティブ形状をフィッティングする方法。
【請求項２】
前記３Ｄ点は、３Ｄセンサによって取得される、
請求項１に記載の方法。
【請求項３】
前記距離場の勾配ベクトル場を求めるステップをさらに備えた、
請求項１に記載の方法。
【請求項４】
前記仮定するステップは、前記距離場において、各候補のパラメータを求めるのに必要な最小数の前記要素を用いる、
請求項３に記載の方法。
【請求項５】
前記距離場から選択された前記候補を取り去り、前記変換するステップ、前記仮定するステップ、前記求めるステップおよび前記選択するステップを繰り返すことによって、プリミティブ形状の集合をフィッティングするステップをさらに備えた、
請求項１に記載の方法。
【請求項６】
勾配降下手順を用いることによって、選択された前記候補を精緻化するステップをさらに備え、
前記勾配降下手順は、前記勾配ベクトル場を用いる、
請求項３に記載の方法。
【請求項７】
ｉ＝１，．．．，Ｎについて、Ｐ＝｛ｐｉ｝は、前記３Ｄ点の集合であり、前記距離場は、Ｄ（ｘ）であり、ここで、ｘは、Ｗ×Ｈ×Ｌのサイズを有する規則的なボリュームグリッドにおける３Ｄボクセルを表し、Ｒは、３×３の回転行列であり、ｔは、３×１の並進ベクトルであり、ｓは、前記３Ｄ点の集合の座標系を前記距離場の座標系に変換するためのスケール係数であり、ｉ番目の３Ｄ点ｐｉは、全てのｑｉが前記距離場内にあるように、ｑｉ＝ｓ（Ｒｐｉ＋ｔ）として前記距離場の前記座標系に変換される、
請求項１に記載の方法。
【請求項８】
ｑｉは、ｑｄｉ＝ｒｏｕｎｄ（ｑｉ）として前記距離場の最近傍格子点に離散化され、関数ｒｏｕｎｄ（・）は、前記３Ｄ点の前記最近傍格子点を求める、
請求項７に記載の方法。
【請求項９】
前記距離場は、最小化
【数１】
2016523394.tif 000019
を解くことによって求められ、ここで、関数ｄは、点ｘと点ｙとの間の距離を求め、Ｔは、インジケータ関数
【数２】
2016523394.tif 000020
である、
請求項８に記載の方法。
【請求項１０】
前記勾配ベクトル場を用いてヤコビ行列を求めるステップをさらに備えた、
請求項６に記載の方法。
【請求項１１】
各要素は、３Ｄロケーションおよび３Ｄ方向ベクトルを有する有向３Ｄ点である、
請求項３に記載の方法。
【請求項１２】
前記プリミティブ形状は、無限平面、平面セグメント、球、円柱、直方体、およびそれらの組み合わせからなる群から選択される、
請求項１に記載の方法。
【請求項１３】
前記スコアは、前記プリミティブ形状の表面積によって重み付けされる、
請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、３次元（３Ｄ）データを処理することに関し、より詳細には、プリミティブ形状を３Ｄデータにフィッティングすることに関する。
【背景技術】
【０００２】
構造化光、レーザ走査、または飛行時間に基づく３次元（３Ｄ）センサが、ロボット工学、コンピュータビジョンおよびコンピュータグラフィックスにおける多くの用途で用いられている。センサは、一般的に３Ｄ点群と呼ばれる３Ｄ点の集合として３Ｄシーンを走査する。３Ｄセンサによって取得された幾つかの走査を単一の座標系にレジストレーションすることによって、より大規模なシーンのための３Ｄ点群を得ることができる。
【０００３】
３Ｄ点群を記憶および処理することは、十分なメモリおよび計算リソースを必要とする。なぜなら、各３Ｄ点は別個に記憶および処理されなくてはならないためである。プリミティブ形状の集合として３Ｄ点群を表すことは、小型なモデル化および高速処理のために望ましい。
【０００４】
１つの方法は、ランダムサンプルコンセンサス（ＲＡＮＳＡＣ）フレームワークを用いてプリミティブ形状を３Ｄ点群にフィッティングする。その方法は、幾つかのプリミティブ形状を仮定し、仮定されるプリミティブ形状のスコアに従って最良のプリミティブ形状を選択する。その方法は、スコアを求めるために未加工の３Ｄ点群を用い、これは、仮定されるプリミティブ形状ごとに、３Ｄ点群内の全ての点をトラバースするか、または仮定されたプリミティブ形状における基準点を所与として３Ｄ点群内の近傍点を探索することを必要とする。これには時間がかかる。
【発明の概要】
【０００５】
本発明の実施形態は、プリミティブ形状を３Ｄ点群にフィッティングする方法を提供する。本方法は、距離場によって３Ｄ点群を表す。ＲＡＮＳＡＣフレームワークは、プリミティブ形状フィッティングを効果的に実行する。
【０００６】
距離場は、３Ｄ点群内の各点から、最近傍のオブジェクト表面までの距離を表す。これによって、ＲＡＮＳＡＣフレームワークにおけるスコア評価が効率的になる。距離場は、点ごとに最近傍のオブジェクト表面までの勾配方向も提供する。これは、勾配降下に基づく精緻化プロセスに役立つ。
【０００７】
このため、従来技術と対照的に、距離場表現の使用によって、ＲＡＮＳＡＣフレームワークにおいて生成された仮定のための高速のスコア計算、および仮定された形状パラメータの効率的な精緻化が可能になる。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施形態による、距離場を用いてプリミティブ形状を３Ｄ点群にフィッティングする方法の流れ図である。
【発明を実施するための形態】
【０００９】
図１に示すように、本発明の実施形態は、距離場を用いてプリミティブ形状を３Ｄ点群にフィッティングする方法を提供する。方法への入力は３Ｄ点群１０１である。３Ｄ点群は、３Ｄセンサの走査として取得することもできるし、３Ｄセンサの複数の走査または幾つかの異なる３Ｄセンサからの走査をレジストレーションすることによって取得することもできる。
【００１０】
３Ｄ点群は距離場１０２に変換される（１０５）。距離場は、ＲＡＮＳＡＣベースのプリミティブ形状フィッティングプロセス１１０において用いられ、対応する形状のパラメータを求めるのに必要とされる最小数の点を用いることによって、２つ以上の候補形状１００の集合が仮定される（１１１）。形状候補ごとにスコア１２１が求められる。
【００１１】
本方法は、候補間で最小スコアを有する最良の候補プリミティブ形状を選択する（１２０）。任意選択により、最良のプリミティブ形状のパラメータを、勾配降下手順を用いて精緻化することができる（１３０）。点群におけるプリミティブ形状の集合を求めるために、選択されたプリミティブ形状を距離場から取り去った（１４０）後、プロセス１１０を反復する。本方法の出力は、プリミティブ形状の集合を定義するパラメータ１０９の集合である。
【００１２】
本方法は、当該技術分野において既知のようにメモリおよび入／出力インターフェースに接続されるプロセッサ１５０において実行することができる。
【００１３】
点群から距離場への変換
ｉ＝１，．．．，Ｎについて、Ｐ＝｛ｐｉ｝が３Ｄ点群の点の集合であるものとする。点群を距離場Ｄ（ｘ）に変換する。ここで、ｘは距離場における要素を表す。要素は、ボリュームＶ＝Ｗ×Ｈ×Ｌを有する規則的な立方体グリッド内の３Ｄボクセルとすることができる。ここで、Ｗ、ＨおよびＬは、グリッドの幅、高さおよび長さである。３Ｄ点の集合のうちの最近傍点への距離が要素またはボクセルに関連付けられる。
【００１４】
点群の座標系を距離場の座標系に変換するために、Ｒが３×３の回転行列であり、ｔが３×１の並進ベクトルであり、ｓがスケール係数であるものとする。次に、点群内のｉ番目の３Ｄ点ｐｉが、ｑｉ＝ｓ（Ｒｐｉ＋ｔ）として距離場の座標系に変換される。全てのｑｉがＷ×Ｈ×Ｌのボクセルの距離場内にあるように、Ｒ、ｔおよびｓを求める。
【００１５】
変換された点ｑｉは、ｑｄｉ＝ｒｏｕｎｄ（ｑｉ）として距離場の最近傍格子点に離散化される。ここで、関数ｒｏｕｎｄ（・）は、引数内の３Ｄ点の最近傍格子点を求める。Ｑ＝｛ｑｄｉ｝が離散化点の集合であるものとする。点群の距離場は、以下の最小化問題を解くことによって求められる。
【数１】
2016523394.tif 000003
ここで、関数ｄによって、点ｘおよびｙ間の距離が決まり、Ｔはインジケータ関数
【数２】
2016523394.tif 000004
である。
【００１６】
式（１）の最小化問題への単純な解は、Ｏ（Ｖ２）時間を必要とする。Ｏ（Ｖ）時間で距離場を求めるための手順は、マンハッタン距離、ユークリッド距離およびＬ１距離等の幾つかの距離関数ｄについて既知である。そのような手順は、次元ごとに順次１次元の距離場計算を実行する。本発明の好ましい実施形態は、距離関数としてユークリッド距離を用いる。
【００１７】
式（１）を解くことによって距離場を求めた後、距離場を以下のようにトランケートする。
【数３】
2016523394.tif 000005
ここで、Ｃはトランケートに用いられる閾値である。これによって、欠落データが存在する場合であっても、プリミティブフィッティングプロセスが正確になる。
【００１８】
次に、Ｄ（ｘ）の勾配ベクトル場を求める。これを用いて、３Ｄ点の法線ベクトルを仮定し、勾配降下ベースの精緻化プロセスのためのヤコビ行列を求めることができる。以下の式を用いて勾配ベクトル場を求める。
【数４】
2016523394.tif 000006
【００１９】
プリミティブ形状を効率的に仮定するために、ゼロ距離を有するボクセルＺの集合、すなわちＺ＝｛ｘｉ｜Ｄ（ｘｉ）＝０｝を記憶する。ボクセルはオブジェクト表面上の点に対応し、本発明ではプリミティブ形状を効率的に仮定するのに用いる。
【００２０】
上記の好ましい実施形態は、一様の大きさの要素またはボクセルを用いる。八分木ベースの表現等の適応サイズのボクセルも用いることができることに留意されたい。
【００２１】
距離場を用いたプリミティブ形状フィッティング
距離場および勾配ベクトル場を所与として、プリミティブ形状フィッティングのためにＲＡＮＳＡＣフレームワークを用いる。２つ以上の候補プリミティブ形状の集合を仮定し、それらのスコアを求め、最小スコアを有する最良の候補を選択する。好ましい実施形態では、無限平面、平面セグメント、球、円柱および直方体をプリミティブ形状として用いる。しかしながら、異なるプリミティブ形状の数は無制限とすることができる。
【００２２】
プリミティブごとに、形状仮定を生成するのに必要とされる最小数のボクセルを用いる。そのようなボクセルを集合Ｚから選択する。各ボクセルは位置ｒｉ∈Ｚおよび法線
【数５】
2016523394.tif 000007
を有することに留意されたい。このため、各ボクセルは、有向３Ｄ点、すなわち、３Ｄ方向ベクトルを有する３Ｄ点とみなすことができる。以下において、集合１００内のプリミティブ形状ごとに形状仮定を生成するための手順を説明する。
【００２３】
無限平面プリミティブ
無限平面、すなわち、境界を有しない平面は、単一の有向点（ｒ１，ｎ１）をサンプリングすることによって仮定することができる。この平面上の全ての点ｒは以下の平面方程式を満たすべきである。
【数６】
2016523394.tif 000008
【００２４】
この平面のためのスコアｖを求めるために、
【数７】
2016523394.tif 000009
を満たす距離場のボリューム内の幾つかの点ｒｊ（ｊ＝１，．．．，Ｊ）をサンプリングする。ここで、εは、平面方程式（６）からのサンプリングされた点の小さなずれを許容する小さな閾値である。次に、サンプリングされた点の距離を以下のように平均化する。
【数８】
2016523394.tif 000010
【００２５】
これ以降、式（７）等において、雑音および離散化に起因した厳密な値からの小さなずれを許容する小さな閾値をεとして表す。εは異なる方程式の場合に異なり得ることに留意されたい。
【００２６】
平面セグメントプリミティブ
平面セグメントプリミティブは、その平面方程式と、平面セグメントのメンバーである点の集合とによって表される。第１に、無限平面プリミティブにおけるように単一の有向点（ｒ１，ｎ１）をサンプリングすることによって平面方程式を求める。次に、サンプリングされた点位置ｒ１から接続された、この面における点の集合を定義する。具体的には、式（７）およびＤ（ｒｍ）＜εを満たすｒ１から近傍点ｒｍを得る。点ｒｍ（ｍ＝１，．．．，Ｍ）の集合を平面セグメント仮定のメンバーとして維持する。仮定のためのスコアを求めるために、ｒｍから幾つかの点ｒｊをサンプリングし、式（８）におけるようにサンプリングされた点の距離を平均化する。
【００２７】
球プリミティブ
２つの有向点（ｒ１，ｎ１）および（ｒ２，ｎ２）をサンプリングすることによって、球を仮定することができる。２つの点が球上に位置するためには、ｒ１を通過し方向ｎ１を有する線が、ｒ２を通過し方向ｎ２を有する線と、球の中心に対応する点ｃにおいて交差する。交点は、線の双方に最も近傍の点を見つけることによって取得される。この制約に加えて、点ｒ１および点ｒ２が球の中心ｃから同じ距離に位置するように、
【数９】
2016523394.tif 000011
であることを確かめなければならない。これらの制約を用いて、２つの有向点の誤ったサンプルを除去する。２つの線が交差しないか、または式（９）が満たされない場合、サンプリングされた点を破棄し、第１の点からサンプリングプロセスを再始動する。
【００２８】
ｃからｒ１およびｒ２までの平均距離を、球の半径ｒとして求める。すなわち、以下となる。
【数１０】
2016523394.tif 000012
【００２９】
球上に位置する全ての点ｒは以下を満たす。
【数１１】
2016523394.tif 000013
【００３０】
球のスコアは、式（１１）を満たすこの球上の幾つかの点をサンプリングし、サンプリングされた点の距離を、式（８）を用いて平均化することによって求められる。
【００３１】
円柱プリミティブ
円柱を仮定するために、まず、円柱の軸および半径を定義する２つの有向点（ｒ１，ｎ１）および（ｒ２，ｎ２）をサンプリングする。軸の方向は、ｎａ＝ｎ１×ｎ２として定義され、ここで×は外積を表す。２つの有向点（ｒ１，ｎ１）および（ｒ２，ｎ２）を、軸ｎａの方向に沿って、共通平面上に投影し、平面上に投影された２つの有向点によって画定された平面上の２つの線の交点を求める。２つの投影された点は、交点から概ね同じ距離にあり、それによって交点と投影された２つの点との間の平均距離を用いて円柱の半径を求めることができる。この条件が満たされない場合、サンプリングされた点を破棄し、第１の点からサンプリングプロセスを再始動する。
【００３２】
次に、他の２つの有向点（ｒ３，ｎ３）および（ｒ４，ｎ４）をサンプリングして、円柱の２つの平面を画定する。２つの点は、ｎ３およびｎ４が軸ｎａの方向に平行である、すなわち、
【数１２】
2016523394.tif 000014
であるという条件を満たす。
【００３３】
この条件が満たされない場合、サンプリングされた点を破棄して、第１の点からサンプリングプロセスを再始動する。
【００３４】
円柱のスコアを求めるために、円柱の表面上に幾つかの点をサンプリングし、式（８）に示すように、サンプリングされた点の距離を平均化する。
【００３５】
直方体プリミティブ
６つの有向点をサンプリングすることによって、直方体を仮定することができる。法線ｎ１およびｎ２が互いに平行となるように、すなわち、
【数１３】
2016523394.tif 000015
となるように、第１の２つの点（ｒ１，ｎ１）および（ｒ２，ｎ２）をサンプリングする。
【００３６】
次の点（ｒ３，ｎ３）および（ｒ４，ｎ４）を、ｎ３がｎ１に対し直交し、ｎ４がｎ３に平行となるように、すなわち、
【数１４】
2016523394.tif 000016
となるようにサンプリングする。
【００３７】
最後の２つの点（ｒ５，ｎ５）および（ｒ６，ｎ６）を、ｎ５がｎ１およびｎ３の双方に対し直交し、ｎ６がｎ５に対し平行となるように、すなわち、
【数１５】
2016523394.tif 000017
となるようにサンプリングする。
【００３８】
６つの点をサンプリングする間、上記の条件のうちのいずれかが満たされていない場合、サンプリングされた点を廃棄し、第１の点からサンプリングプロセスを再始動する。
【００３９】
６つの点のそれぞれが、立方体の面を画定する。スコアを求めるために、６つの面上の点の集合をサンプリングし、サンプリングされた点の距離値を、式（８）におけるように平均化する。
【００４０】
最良のプリミティブ選択
本方法の反復ごとに、幾つかのプリミティブ形状を仮定し、上記で説明したようにそれらの対応するスコアを求める。次に、全ての仮定間で最小のスコアを有する最良のプリミティブを選択する。
【００４１】
この単純なスコアリング方法は、小さな表面積を有するプリミティブ形状を優先する。そのような小さなプリミティブ形状を選択することを回避するために、最良のプリミティブ選択のためのプリミティブ形状の表面積によって重み付けされたスコアを用いる。具体的には、重み付けされたスコアとしてｖ／Ｓｐを用いる。ここで、Ｓはプリミティブの表面積を表し、ｐは、スコアと表面積との間の重み付けの平衡をとるパラメータである。
【００４２】
精緻化
任意選択で、勾配降下手順を用いて、最良のプリミティブ形状のパラメータを精緻化する（１３０）。ＲＡＮＳＡＣプロセスにおいて求められたプリミティブパラメータからの勾配降下を開始する。勾配降下ステップごとに、現在のプリミティブパラメータを所与として、プリミティブ形状の表面上の幾つかの点ｒｋ（ｋ＝１，．．．，Ｋ）をサンプリングし、それらの勾配ベクトル
【数１６】
2016523394.tif 000018
を用いて、パラメータを精緻化するためのプリミティブ形状の各パラメータに関してヤコビ行列を求める。
【００４３】
サブトラクション
最良のプリミティブを所与として、距離場から、プリミティブにおける点を取り去る。プリミティブ形状の表面と、集合Ｚ内の各点との間の距離を求め、距離が小さな閾値以内である場合、点をＺから除去する。次に、Ｚ内の点の新たな集合を用いることによって距離場Ｄ（ｘ）を求め、勾配ベクトル場も更新する。新たな距離場および勾配ベクトル場は、本発明による方法の次の反復において用いられる。
【図１】
2016523394.tif 000021
【手続補正書】
【提出日】平成27年12月3日(2015.12.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１
【補正方法】変更
【補正の内容】
【請求項１】
３次元（３Ｄ）点の集合にプリミティブ形状をフィッティングする方法であって、
前記３Ｄ点の集合を距離場に変換するステップであって、前記距離場内の各要素は前記３Ｄ点の集合における最近傍点への距離に関連付けられる、ステップと、
前記プリミティブ形状の２つ以上の候補の集合を仮定するステップと、
前記距離場のボリューム内の点をサンプリングしてサンプリングされた点の距離を平均化することによって、候補ごとのスコアを求めるステップと、
前記スコアに従って、前記３Ｄ点にフィッティングする前記プリミティブ形状として前記候補を選択するステップと、
を備え、
前記ステップは、プロセッサにおいて実行される、
３Ｄ点の集合にプリミティブ形状をフィッティングする方法。
【国際調査報告】
2016523394.tif 000022
2016523394.tif 000023