背景

3次元点群が平面を構成しているか(直線上に並んでいないか)を検出したいときがあったので、手法などをこちらにまとめました。直線上に並んでいて、平面を構成できていない下画像のようなものを検出するのが目的です。

手法

こちらのAlgorithm 3.1のやり方をベースにやってみました。特異値分解することにより、x, y, z方向の散らばり具合を求めて、値が大きい2つの値の比を求めることにより、平面を構成しているか確認しました。主成分分析の資料も参考になりました。

1. 3次元点群の中心を求める

c=\frac{1}{n}\sum_{i=1}^{n}p_i

2. 元の点群から中心を引いた行列を作る

A = [p1 − c, . . . , pn − c]

3. 行列Aを特異値分解する

U S V ^{T} = A

4. 特異値のS[0], S[1]の比を算出して、閾値より大きいかチェックする

散らばり具合が大きい軸の値からS[0], S[1], S[2]と並ぶので、S[0]がS[1]より極めて大きい場合は、点群が直線上に並んでいる可能性が高いです。

ratio = S[0] / S[1]

実装

詳細は省きますが、Pythonであれば、numpyのlinalg.svdを使えば特異値分解は簡単にできます。S[0]/S[1]の値の閾値に関しては、今は40より大きい場合は平面を構成していないとみなすようにしています。この値は、実際のデータで実験しながら決めていくといいと思います。S[1]の値が0になる可能性もあるので、注意してください。

参考資料