Fast and Robust Edge Extraction in Unorganized Point Clouds
Paper（5000 words）
Fast and Robust Edge Extraction in Unorganized Point Clouds - IEEE Conference Publication
ABSTRACT
- 本論文では，点群表面のエッジを検出する課題について調査する．
- 一般的に，エッジ認識は，法線や曲率などの幾何学的特徴の抽出が必要である．
- エッジ抽出は，点群の密度やスケールに依存したパラメータを用いた複数のステップで構成される．
- 本論文では，各点のk-NNによって定義された共分散行列の固有値を分析することで，鮮明な(sharp)エッジ特徴を抽出する，高速かつ精確な手法を提案する．
1. INTRODUCTION
- エッジ抽出は，CVの分野において多くの注目を集めている．
- 鮮明なエッジは，視覚的認知を向上させる．
- 加えて，セグメンテーションの際に，特徴領域の情報は大いに役立つ．
- 本論文では，最初に3次元サーフェスの二面角において，鮮明なエッジ抽出を試みる．
- 我々の意図は，様々な手法で鮮明なエッジを抽出し，結果の精度と計算負荷を定量的に比較することである．
5. CONCLUSION
- 本論文では，エッジ抽出における法線推定が，triangulationよりもPCAを利用した方が計算負荷が明らかに小さいということを証明した．（両者とも検出の効率は同じ）
- また，共分散行列の固有値分析手法によるエッジ抽出は，二面角において高速かつ正確であることも証明した．
- 加えて，エッジ抽出手法におけるユーザ依存のパラメータを削減できる．
4. EXPERIMENTAL RESULTS
A. Experimental data
- エッジのシャープさの効果を分析するために，Fig. 2に示す二平面を実験データとして用いる．
- また，Fig. 3に示すようなカーブオブジェクトも用いる．
- 点密度は両者とも一様．
B. Experimental results
- F1-Scoreを式(5)のように定義する．
- Precisionは，エッジ抽出により正確に検出された点の割合で定義される．
- Recallは，ground truthとしてラベル付けされた点の割合で定義される．
（※ground truthというのは，質問と回答の紐付けデータのこと．） - PrecisionとRecallは，式(6)のように定義する．
- TPは，正確に検出された点の数を表す，True Positivesの意味．
- FPは，誤って検出された点の数を表す，False Positivesの意味．
- FNは，誤った棄却，すなわちground truthに属するがエッジ抽出によって検出されなかった点を表す，False Negativesの意味．
1）Edge extraction for a small dihedral angle:
- Table1. において，triangulationとPCAを比較する．
- F1-Scoresは，角度が大きいとき（90°と67.5°）はほぼ同じだが，角度が小さいとき（45°と22.5°）は，triangulationの方がわずかに正確である．
- 計算時間は，triangulationの方がPCAよりも60倍遅い．（Table2. ）
- 固有値を分析することによるsurface variation methodは，triangulation，PCAと比較して，45°と22.5°のときの結果がより正確である．（Table1. ）
- surface variation methodは，法線ベクトルを明確に推定しないが，triangulationとPCAは，近傍における法線ベクトルをグループ化する．
- surface variation methodは，triangulationとPCAよりも，精確さと計算時間の面で，確かなアドバンテージがある．（Table1&2）
- 固有値分析手法の定性的評価のために，Bunny，Dragon，Trim-Starに対して適用した結果を示す．（Fig. 5）
2）Fast edge extraction:
- 計算時間に観点で，固有値分析手法のパフォーマンスを測るために，３つの手法の合計時間をTable. 2に示す．
- PCAを用いた法線推定は，triangulationより60倍高速．（Table. 2）
- 固有値分析手法は，PCAよりもさらに2倍高速．（Table. 2）
3）Robustness to noise:
- 固有値分析手法のノイズに対するロバスト性をテストするために，ガウシアンノイズを10%，20%加えたモデルに対する結果を示す．（Fig. 6）
- ガウシアンノイズを伴ったエッジ抽出に対するF1-Scoresの表を示す．（Table. 3）
- F1-Scoresは，20%ノイズを含んでいる点群に対しても，0.5を超えている．（Table. 3）
- ガウシアンノイズのパーセンテージが増えるにつれて，ノイズが多くなりfalseエッジ点としてカウントされることで，recallが増え，precisionが減少する．
3. PROPOSED APPROACH
- 我々は，PCAを用いて法線を推定し，次にWeberの方法に従って法線をクラスタリングして，エッジ特徴を抽出するIII-Aを提案する．
- しかし，法線を推定することによる特徴抽出手法は，二面角が小さい場合にうまくいかないことが多い．
- そこで，我々は，各点のk近傍によって定義される共分散行列の固有値を分析するだけで，特徴を抽出する高速な手法III-Bを提案する．
A. PCA and agglomerative clustering
- 我々は，Weberの法線推定をPCAで置き換えることを提案する．
B. Eigenvalue analysis
- エッジ抽出の複雑な処理（法線推定とクラスタリングという2つのステップ）を回避するために，クラスタリングを行わずにエッジ抽出する手法を提案する．
- PCAによる法線推定は，共分散行列の固有値に基づいているため，単に各点の固有値のバリエーションを用いてエッジ抽出を行う．
REFERENCES
