許多點雲處理步驟中都需要法線，在pcl中。對於法線的計算已經封裝好，主要是積分圖以及PCA法進行法線估算。自己研究了一下原理--主成分分析法（PCA）。在文章展開前，網上已有很多關於PCA分析的文章博客，側重點不盡相同，主要是從數學、統計角度。

我不相應的展開。推薦一些我覺得還不錯的博文：

徹底理解PCA（Principal Component Analysis）主成分分析

徹底學會PCA1-理解PCA原理

我將儘可能的以易懂的方式，聊一聊PCA在法線估計中的應用。

1、問題情境的理解：

假設初始點雲是沒有法矢的，我們的目的是為了求取法矢。

法矢的特性是垂直於其點所在的平面。所謂三點(不共線)確定一個平面，所以我我們可以猜想：採用當前點的鄰近點，擬合出一個局部平面，那麼法矢就好求了。

其它出的點也一樣：

但是會出現二異性問題，畢竟經過一點且垂直一個面的法矢是有兩條的：

所以後續還需要用特定的方法進行法矢定向，這裡先不用展開

還記得現在的問題思路麼？

求取某點法矢--》先求該點所在的擬合平面--》求擬合平面？

好了，理解了問題的出發點，下一步就是尋找解決方案了。

2、用什麼方法擬合平面好呢？

擬合出的平面應當具有一個性質：候選點到這個平面的距離最小

翻譯一下，局部平面擬合的方式：

  • 選取當前點的 k 個臨近點（上述圖都 k=2）。或者劃定一個半徑為 r 的球，選取球內部所在的點
  • 找到一個平面，使得以上選出得到點到這個平面的距離最小

（所以你明白為什麼pcl做這些的時候為什麼要建立 kd-tree/octree, 還限定search radius了吧）

說到平面擬合，我們最常見的當然是最小二乘法了：

下圖首先給出的二維情況下，回顧一下點集擬合直線的情況。

但是我們是要擬合平面，所以這裡的距離，而是考慮垂直距離：

3、PCA怎麼做？

好了，PCA終於上場了。忘記大家通常說的PCA的先驗知識吧，比如用來降維什麼的。就把場景限定在這裡：

  • PCA是為了找到一組新的變換後的正交基（下圖綠色部分），這組正交基是給定點集的最佳表達。

可以理解為PCA的問題其實是一個正交基的變換，使得變換後的數據有著最大的方差

到這裡，你可能尚且不明白它的目的，但是看起來，我們似乎要建立一個新的正交坐標系統。

好了，還記得之前的問題場景麼？我們是要尋找一個平面，使得點到這個平面的距離最小。

假設這個平面的中心點為 c , 穿過中心點的法矢為 n, 那麼點 xi 到平面的距離 d ，可以看作是向量 xi-c 在法線方向上投影向量的長度，所以這個問題就化解為下圖框起來的部分。

補充知識點：向量A在向量B上的投影長度計算：A·B = |A| *|B| cos(θ) = A^T*

接下來是很多數學的部分！可能你看不懂，但是請記住涉及到的關鍵點：協方差矩陣和奇異值分解。

這是我看PCA的很大一個障礙，我一度不知道為什麼要這麼做。我會在下一節裏去闡述。

1、定義中心原點。

這個m為什麼可以是原點，因為原點的特性就是其他點到它的距離的平方和最小。

接下來，問題轉化為：

解釋一下這個式子：

備註：數學公式裏argmin 就是使後面這個式子達到最小值時的變數的取值。也就是，當所有候選點到目標點c距離的平方和最小時，m就是這個c點

到這裡問題一路化簡為，（不要忘記 yi 的含義），下面的式子看著腦殼疼，但是無非就是把積分號移動了，注意 n 是未知待求解的。

2、構建協方差矩陣S：

? 其中：

也就是 前文上圖中的 yi

3、奇異值分解

4、取U中的最後一列作為法矢

總結一下：

你可能對步驟1和步驟2還能跟上。到了奇異值分解就開始疑問了。不要著急，下面來說為什麼要做這樣的操作。

4、協方差矩陣、奇異值分解、特徵向量、特徵值是為了幹嘛？

奇異值分解：

這裡比較推薦這篇文章，圖文並茂。關鍵是從幾何角度闡釋了奇異值分解的意義。

奇異值分解(SVD) --- 幾何意義

如果你看這篇文章還是覺得數學很多，那麼我定性的給你解釋：

在此處，可以把矩陣 Y 看作三個其它的矩陣相乘

  • U 表示經過變換之後新的坐標系下的正交基

代表V中的向量與U對應的向量的變換關係

  • V 代表變換前原坐標系下的正交基坐標系，T代表轉置（有些地方寫的是*）

至於怎麼求解，可以看一下這片文章：奇異值分解(SVD)原理與在降維中的應用

我們看到最後取的法向量就是U中的最後一列，也就是特徵值最小的那些特徵向量。為什麼呢，這就要說到協方差矩陣的意義了。

協方差矩陣的意義：

? 協方差矩陣衡量了沿著特定方向v的點的相關性

?

舉例：如果找一條穿過原點 m 的直線 l , 直線 l 沿著方向 v , 把點xi 投影在直線上，

得到點 xi 。 然後下面這一串數學公式，表達的就是點 xi 的相關性

可以看到相關性越大（對應的特徵值也就越大）的點，幾乎就快落在（甚至重合）直線l上。

當然PCA的應用還有很多，比如在數據分析中常常被用來降維。而這裡就不展開了。


推薦閱讀：
相關文章