計算機視覺的最終體現是三維視覺，而三維視覺的表達方式則是點雲，點雲處理在整個三維視覺領域占有非常重要的地位，幾乎涉及到所有相關領域，例如自動駕駛感知定位、SLAM、三維場景重建、AR/VR、SFM、姿态估計、三維識别、結構光、立體視覺、三維測量、視覺引導等。近年來，無論是學術界還是工業界，開始逐漸将注意力轉移到點雲工作上，與之相關的應用呈爆發趨勢，對應崗位更是需遠大于供，随之而來的則是企業不惜重金招聘點雲處理相關算法工程人員。什麼是點雲？什麼是點雲配準？我們來簡單了解下咯

點雲配準（point cloud registration）是圖形學、視覺、機器人學科中的基礎問題。給定兩個局部重疊的3D點雲，配準的目的是識别一個嚴格的轉換函數以實現對齊。這類方法首先建立兩個點雲之間的關聯，再利用關聯來估計轉換函數。顯然，這類的方法的核心在于找到高質量的關聯。

點雲是在同一空間參考系下表達目标空間分布和目标表面特性的海量點集合，在獲取物體表面每個采樣點的空間坐标後，得到的是點的集合，稱之為“點雲”（Point Cloud）。點雲配準就是多角度多幀數據的拼接，通過計算相鄰幀數據的對應點，完成配準拼接。

首先，點雲配準過程，就是求一個兩個點雲之間的旋轉平移矩陣（rigid transform or euclidean transform 剛性變換或歐式變換），将源點雲(source cloud)變換到目标點雲(target cloud)相同的坐标系下。可以表示為以下的方程:

其中

就是target cloud與source cloud中的一對對應點。而我們要求的就是其中的R與T旋轉平移矩陣。這裡，我們并不知道兩個點集中點的對應關系。這也就是配準的核心問題。

粗配準就是再兩個點雲還差得十萬八千裡、完全不清楚兩個點雲的相對位置關系的情況下，找到一個這兩個點雲近似的旋轉平移矩陣（不一定很精确，但是已經大概是對的了）。精配準就是在已知一個旋轉平移的初值的情況下（這個初值大概已經是正确的了），進一步計算得到更加精确的旋轉平移矩陣。

這裡從精配準開始講起。精配準的模式基本上已經固定為使用ICP算法及其各種變種。ICP算法由Besl and McKay 1992, Method for registration of 3-D shapes文章提出。文中提到的算法不僅僅考慮了點集與點集之間的配準，還有點集到模型、模型到模型的配準等。簡要介紹一下點集到點集ICP配準的算法：1)ICP算法核心是最小化一個目标函數：

（這裡的表述與原文略微有些不同，原文是用四元數加上一個偏移向量來表達旋轉平移變換。）

就是一對對應點，總共有

對對應點。這個目标函數實際上就是所有對應點之間的歐式距離的平方和。2)尋找對應點。可是，我們現在并不知道有哪些對應點。因此，我們在有初值的情況下，假設用初始的旋轉平移矩陣對source cloud進行變換，得到的一個變換後的點雲。然後将這個變換後的點雲與target cloud進行比較，隻要兩個點雲中存在距離小于一定阈值（這就是題主所說的ICP中的一個參數），我們就認為這兩個點就是對應點。這也是"最鄰近點"這個說法的來源。3)R、T優化。有了對應點之後，我們就可以用對應點對旋轉R與平移T進行估計。這裡R和T中隻有6個自由度，而我們的對應點數量是龐大的（存在多餘觀測值）。因此，我們可以采用最小二乘等方法求解最優的旋轉平移矩陣。一個數值優化問題，這裡就不詳細講了。4)疊代。我們優化得到了一個新的R與T，導緻了一些點轉換後的位置發生變化，一些最鄰近點對也相應的發生了變化。因此，我們又回到了步驟2)中的尋找最鄰近點方法。2)3)步驟不停疊代進行，直到滿足一些疊代終止條件，如R、T的變化量小于一定值，或者上述目标函數的變化小于一定值，或者鄰近點對不再變化等。（這裡也是題主所說的ICP算法中的一個參數）

算法大緻流程就是上面這樣。這裡的優化過程是一個貪心的策略。首先固定R跟T利用最鄰近算法找到最優的點對，然後固定最優的點對來優化R和T，依次反複疊代進行。這兩個步驟都使得目标函數值下降，所以ICP算法總是收斂的，這也就是原文中收斂性的證明過程。這種優化思想與K均值聚類的優化思想非常相似，固定類中心優化每個點的類别，固定每個點的類别優化類中心。

關于參數的選擇:ICP算法的參數主要有兩個。一個是ICP的鄰近距離，另外一個是疊代的終止條件。這些參數的選擇，與實際的工程應用相關。比如說你的儀器精度是5mm，那麼小于5mm是可以認為是對應點，而最終的疊代終止條件也就是匹配點之間平均距離小于5mm。而且這些參數可以由算法逐步疊代減小，最初使用較大的對應點距離參數，然後逐步減小到一個較小的值。（問過師兄才知道實際過程這樣操作會比較合适。）需要手動調整一些參數。（這跟機器學習調參比起來，簡直不是事~~）

3、粗配準前面介紹到了，ICP算法的基本原理。它需要一個旋轉平移矩陣的初值。這個初值如果不太正确，那麼由于它的greedy優化的策略，會使其目标函數下降到某一個局部最優點（當然也是一個錯誤的旋轉平移矩陣）。因此，我們需要找到一個比較準确的初值，這也就是粗配準需要做的。

粗配準目前來說還是一個難點。針對于不同的數據，有許多不同的方法被提出。我們先介紹配準的評價标準，再在這個标準下提出一些搜索策略。

評價标準：比較通用的一個是LCP(Largetst Common Pointset)。給定兩個點集P,Q，找到一個變換T(P)，使得變換後的P與Q的重疊度最大。在變換後的P内任意一點，如果在容差範圍内有另外一個Q的點，則認為該點是重合點。重合點占所有點數量的比例就是重疊度。

解決上述LCP問題，最簡單粗暴的方法就是遍曆。假設點集P,Q的大小分别為m,n。而找到一個剛體變換需要3對對應點。那麼brute force 搜索的需要

的複雜度。對于動辄幾百萬個點的點雲，這種時間複雜度是不可接受的。因此，許多搜索策略被提出。比較容易想到的是RANSAC之類的搜索方法。而對于不同的場景特點，可以利用需配準點雲的特定信息加快搜索。（例如知道點雲是由特定形狀的面構成的）這裡先介紹一個适用于各種點雲，不需要先驗信息的搜索策略，稱為4PC(4 Point Congruent)。

搜索策略：4PC搜索策略是在P,Q中找到四個共面的對應點。

如上圖所示（來自4PC原文），這四個共面的點相交于e。這裡有兩個比例在剛體變化下是不變的。

(實際上在仿射變換下也是不變的。)而4PC将對于三個點的搜索轉換為對e,e'的搜索，從而将複雜度降低到了

。這四個點的距離越遠，計算得到的轉換越穩健。但是這裡的四個點的搜索依賴于兩個點雲的重疊度。具體的算法可以參考4-Points Congruent Sets for Robust Pairwise Surface Registration的原文。

4PC算法通用性較好，但是對于重疊度較小、或是噪聲較大的數據也會出現配準錯誤或是運行時間過長的問題。針對于不同的場景很多其他的搜索策略也被提出。

這裡安利一下我師兄的論文吧~Automatic registration of large-scale urban scene point clouds based on semantic feature points我們課題組主要是研究室外地面站LiDAR獲取的點雲配準問題。這種情形下，由于掃描儀内有自動安平裝置，Z軸都是豎直方向（重力方向），剛體變換隻存在三維平移與平面（XoY面上的）旋轉。我們就在場景中搜索豎直的特征線并且得到它們與地面的交點。

再将這些交點構建出三角形，以三角形的全等關系來得到匹配。

找出其中一緻性最好的三角形集合，作為匹配的集合，進行粗配準。

這種方法适用于豎直線較多的場景，比如城區的建築物的邊線、林區樹木的樹幹等。設計的方法還是很巧妙的。當然如果場景内這種特征較少，就比較難以配準。

（填坑完成~）

參考文獻：[1] Besl P J, Mckay N D. Method for registration of 3-D shapes[C]// Robotics - DL tentative. International Society for Optics and Photonics, 1992:239-256.[2] Aiger D, Mitra N J, Cohen-Or D. 4-points congruent sets for robust pairwise surface registration[J]. Acm Transactions on Graphics, 2008, 27(3):85.[3]Yang B, Dong Z, Liang F, et al. Automatic registration of large-scale urban scene point clouds based on semantic feature points[J]. Isprs Journal of Photogrammetry & Remote Sensing, 2016, 113:43-58.

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!