導(dǎo)讀：

3D點云配準(zhǔn)是計算機視覺的關(guān)鍵研究問題之一，在多領(lǐng)域工程應(yīng)用中具有重要應(yīng)用，如逆向工程、SLAM、圖像處理和模式識別等。點云配準(zhǔn)的目的是求解出同一坐標(biāo)下不同姿態(tài)點云的變換矩陣，利用該矩陣實現(xiàn)多視掃描點云的精確配準(zhǔn)，最終獲取完整的3D數(shù)字模型、場景。本質(zhì)上，關(guān)于六自由度(旋轉(zhuǎn)和平移)的3D點云配準(zhǔn)問題是典型的非凸優(yōu)化問題，其目標(biāo)函數(shù)在六維可行域空間中具有多個波峰波谷，即優(yōu)化求解過程中受初始變換矩陣影響，容易陷入局部最優(yōu)解。點云配準(zhǔn)結(jié)果雖然受限于其初始位置，但是早期的一些局部的配準(zhǔn)算法對解決點云配準(zhǔn)問題具有重要的應(yīng)用、啟示意義。因此，本文重點介紹一些魯棒性或效率較好的局部、全局3D點云配準(zhǔn)算法。

--局部的3D點云配準(zhǔn)算法--

ICP（Iterative Closest Point）算法是應(yīng)用最廣泛的3D點云配準(zhǔn)算法之一, 其通過歐式變換求解出兩片點云的旋轉(zhuǎn)平移矩陣及對應(yīng)的配準(zhǔn)誤差。

ICP算法的核心思想可以簡述為:假設(shè)數(shù)據(jù)點云 。向源點云 移動配準(zhǔn)，ICP算法通過不斷求解估計的變換矩陣，直到RMSE(Root Mean Square Error)配準(zhǔn)誤差收斂于局部最優(yōu)解 (每一次迭代過程可以描述為：在 中搜索關(guān)于 的最近鄰點集，構(gòu)造協(xié)方差矩陣，奇異值分解獲得單位四元數(shù)，進(jìn)而求解旋轉(zhuǎn)矩陣，平移向量則由對應(yīng)點云的質(zhì)心確定，由此實現(xiàn)數(shù)據(jù)點云的旋轉(zhuǎn)平移變換)。其中，關(guān)于RMSE的配準(zhǔn)模型可以表示為：

在對旋轉(zhuǎn)、平移可行域進(jìn)行參數(shù)化的前提下，關(guān)于 范數(shù)配準(zhǔn)模型的點云配準(zhǔn)問題可以轉(zhuǎn)化為關(guān)于旋轉(zhuǎn)和平移的非凸優(yōu)化問題。ICP雖然具有簡單、收斂性好等優(yōu)點，但其受限于點云初始位置且在解決具有離群值的點云配準(zhǔn)問題，容易陷入局部最優(yōu)解。

為了提高ICP算法的魯棒性，學(xué)者提出了一系列的變種ICP算法。LM-ICP算法提出利用Levenberg-Marquardt算法對ICP配準(zhǔn)模型進(jìn)行求解，并利用DT（Distance-Transform）算法替代KD-tree搜索最近鄰點時，減小點云初始位置對其配準(zhǔn)結(jié)果的影響，并提高了配準(zhǔn)效率。Chetverikov等。在ICP算法的基礎(chǔ)上，提出了魯棒性更好、更實用的Trimmed ICP 算法，對每次迭代匹配得到的最近鄰點進(jìn)行篩選，即對兩兩估計的匹配點的歐式距離進(jìn)行排序，摒棄其中距離較大的點集，懲罰的百分率由核函數(shù)動態(tài)計算。Trimmed ICP 算法應(yīng)用于具有離群值、噪聲的點云配準(zhǔn)問題時，能獲得良好的配準(zhǔn)精度。然而，高占比的離群值對點云配準(zhǔn)算法的魯棒性要求仍然是巨大的挑戰(zhàn)。Bouaziz等提出Sparse ICP算法利用稀疏表示理論對進(jìn)一步改進(jìn)ICP算法的魯棒性，即在 范數(shù)配準(zhǔn)模型上增加p范數(shù)的懲罰項，提高每次迭代中求解匹配點的準(zhǔn)確性，但其利用增廣拉格朗日求解大規(guī)模點云配準(zhǔn)問題時效率較差。Mavridis等結(jié)合模擬退火算法提出了更為高效的Efficient Sparse ICP算法，加速點云配準(zhǔn)的收斂速度。

為了進(jìn)一步提高配準(zhǔn)效率，Li等利用CAD模型的三角切片性質(zhì)，高效求解最近鄰點，保證了配準(zhǔn)精度，并進(jìn)一步提出動態(tài)步長試探性配準(zhǔn)，避免收斂曲線出現(xiàn)震蕩。但實際掃描點云的分布并非均勻，基于CAD 模型的配準(zhǔn)方法僅適用性于理想點云配準(zhǔn)問題。Zhu等通過設(shè)置硬、軟指標(biāo)實現(xiàn)點云的高效精確配準(zhǔn)，即在每次迭代過程中利用雙向匹配的方式對噪聲及離群值進(jìn)行懲罰。但是配準(zhǔn)結(jié)果受限于核函數(shù)中參數(shù)的預(yù)設(shè)值。上述基于 范數(shù)的迭代最近點配準(zhǔn)算法主要包括ICP算法及其變種算法，該類局部的配準(zhǔn)算法受限于點云初始位置，僅適用于小角度錯開的點云配準(zhǔn)問題。在人機交互獲得較好點云初始位置的前提下，迭代最近點算法在解決點云配準(zhǔn)問題時具有良好的魯棒性，但也存在一些可以繼續(xù)優(yōu)化的不足，可以總結(jié)為三點：

（一）受限于主成分分析、奇異值分解算法，迭代最近點算法雖然具有良好的收斂性，但其迭代次數(shù)較多，后期收斂緩慢。

（二）受限于數(shù)據(jù)結(jié)構(gòu)，迭代最近點算法在每次迭代過程中搜索最近鄰點的成本較高，KD-tree雖然搜索效率較高，但仍無法滿足于解決大規(guī)模點云的配準(zhǔn)問題。

（三）受限于點云的稀疏特性，并且實際應(yīng)用中主要通過對點云進(jìn)行下采樣以提高配準(zhǔn)效率，迭代最近點算法無法實現(xiàn)精確配準(zhǔn)。

針對上述不足點，學(xué)者區(qū)別于迭代最近點的配準(zhǔn)算法構(gòu)建新的配準(zhǔn)模型，如概率密度模型、隱式最小二乘函數(shù)和高斯混合模型等，并結(jié)合其它優(yōu)化算法提高點云配準(zhǔn)的效率和精度。Biber等基于概率密度模型提出了Normal Distribute Transform（NDT）算法，即使用D維的高斯函數(shù)作為配準(zhǔn)模型：

NDT算法通過對源點云Q進(jìn)行體素劃分，即求解點云Q的包圍盒，并對該包圍盒進(jìn)行細(xì)分，對包含于不同體素的源點云分別構(gòu)建高斯模型。該算法最大的優(yōu)勢是迭代過程中不需要求解最近鄰匹配點，其計算復(fù)雜度較低。其中體素的劃分方式與點云配準(zhǔn)的精度和效率相關(guān)，可利用回環(huán)控制點云配準(zhǔn)精度，主要應(yīng)用于機器人的實時Simultaneous Localization And Mapping（SLAM）環(huán)節(jié)。Jian等提出利用混合高斯模型替代單一的高斯模型。為了提高配準(zhǔn)模型的魯棒性，體素高斯模型被分別進(jìn)行加權(quán)計算，其中多尺度的點云配準(zhǔn)方法應(yīng)用較為廣泛，如NDT、EM-ICP等。上述基于概率模型的點云配準(zhǔn)算法只需在每次迭代中求解雅可比矩陣，計算復(fù)雜度大大降低，且Magnusson等指出NDT算法較ICP算法能更好地避免點云初始位置對配準(zhǔn)結(jié)果的影響。

針對點云配準(zhǔn)的精度問題，部分學(xué)者提出了點到面的點云配準(zhǔn)算法，利用曲線、曲面擬合求解出源點云的顯、隱式表達(dá)，并利用法向量求解每次迭代中的對應(yīng)點對，如下圖所示

Liu等提出利用動曲面構(gòu)建源點云的拓?fù)渫庑螌崿F(xiàn)點云配準(zhǔn)，主要應(yīng)用于簡單形狀組合而成的零件點云配準(zhǔn)問題，如圓錐、圓柱、旋轉(zhuǎn)掃掠螺旋曲面等。為了解決復(fù)雜外形點云的配準(zhǔn)問題，學(xué)者提出了魯棒性更強的曲面擬合方法，如B樣條模型、八叉樹結(jié)點等。該類配準(zhǔn)算法的實用性更強且應(yīng)用范圍更廣。在此基礎(chǔ)上，張等分析了移動最小二乘法在曲面擬合應(yīng)用中的發(fā)展及其優(yōu)越性，并提出該方法能實現(xiàn)精確的點云配準(zhǔn)且對噪聲具有良好的魯棒性。但是此類算法其需要預(yù)先設(shè)置較好的參數(shù)，如分支數(shù)、權(quán)值等。

相較之下，迭代最近點的點云配準(zhǔn)算法的魯棒性更強，因其不需設(shè)置冗余的優(yōu)化參數(shù)，但其它算法則在提高效率和精度方面更具優(yōu)勢。上述局部算法及其變種廣泛應(yīng)用于解決點云配準(zhǔn)問題，且可有效避免噪聲和離群值對配準(zhǔn)結(jié)果的影響。但是，此類配準(zhǔn)算法受限于點云初始位置，容易陷入局部最優(yōu)。區(qū)別于此類具有魯棒性的局部配準(zhǔn)算法，學(xué)者針對點云初始配準(zhǔn)位置的優(yōu)化問題提出了一系列全局優(yōu)化的配準(zhǔn)算法。

--全局的3D點云配準(zhǔn)算法--

Silva等將點云配準(zhǔn)問題轉(zhuǎn)換為多變量的非凸優(yōu)化問題，并結(jié)合遺傳算法求解出全局優(yōu)化的變換矩陣，能有效避免點云初始位置對配準(zhǔn)結(jié)果的影響。其他應(yīng)用于點云全局配準(zhǔn)的智能算法還包括粒子群算法、模擬退火等。然而，此類啟發(fā)式算法需多次調(diào)用配準(zhǔn)模型進(jìn)行優(yōu)化求解，在處理大規(guī)模點云配準(zhǔn)問題時效率較低，且其全局解并未有嚴(yán)格的證明。為了提高點云配準(zhǔn)效率，部分學(xué)者提出通過構(gòu)造幾何不變量匹配對應(yīng)點對（理論上三組匹配點對就可求解出點云配準(zhǔn)的變換矩陣），該類方法同樣不受點云初始位置影響，且計算復(fù)雜度更低。Wyngaerd等通過曲率特征求解對應(yīng)點對，實現(xiàn)點云全局配準(zhǔn)；Gelfand等則通過構(gòu)造積分體積特征計算匹配點對求解變換矩陣；Rusu等提出構(gòu)造點特征直方圖作為局部描述符。RANSAC方法被直接應(yīng)用于點云配準(zhǔn)，但受限于其配準(zhǔn)效率，一開始主要應(yīng)用于解決二維的點云配準(zhǔn)問題。隨后，Aiger等利用4點法構(gòu)造幾何特征進(jìn)而提取稀疏的匹配點對，使得RANSAC方法能有效地應(yīng)用于三維點云配準(zhǔn)。當(dāng)點云的特征不變量較為明顯時，基于幾何不變量的點云配準(zhǔn)方法可以作為性能優(yōu)異的算法使用。

Yang等基于 范數(shù)配準(zhǔn)模型首次推導(dǎo)出了關(guān)于六維變換域的上下界函數(shù)，并利用分支定界算法提出了全局優(yōu)化的Go-ICP算法，且該算法有效地證明了所求解變換矩陣的全局最優(yōu)性。但是，Go-ICP算法需結(jié)合DT算法才可能高效地實現(xiàn)點云配準(zhǔn)，而DT算法的初始化較為耗時。Lian等提出了更為高效的AMP算法進(jìn)行點云全局優(yōu)化配準(zhǔn)，但其主要適用于圖像處理領(lǐng)域。為了提高點云配準(zhǔn)效率，Chin等提出了Glob-GM-ML算法將六維的點云配準(zhǔn)問題分解為兩個獨立的三維平移、旋轉(zhuǎn)問題，該算法通過構(gòu)建特征不變量求解平移參數(shù)并認(rèn)為其在配準(zhǔn)問題中是先驗的，即六維的點云配準(zhǔn)問題有效地轉(zhuǎn)化為關(guān)于旋轉(zhuǎn)的三維非凸優(yōu)化問題。該方法利用解耦的思想高效地實現(xiàn)點云全局優(yōu)化配準(zhǔn)，是近些年研究的熱點之一，Liu和Li等基于旋轉(zhuǎn)不變量并利用分支定界方法求解出全局優(yōu)化的平移參數(shù)，進(jìn)而實現(xiàn)高效的點云全局優(yōu)化配準(zhǔn)。

為了解決構(gòu)造旋轉(zhuǎn)不變量是的超參數(shù)設(shè)置問題，Yang等利用多項式時間提出了TEASER算法對解決具有極高離群值的點云全局配準(zhǔn)問題具有良好的魯棒性。區(qū)別于應(yīng)用于CPU常規(guī)硬件的全局點云配準(zhǔn)算法，GOGMA算法等基于混合高斯模型構(gòu)建了適用于GPU框架的高效點云全局優(yōu)化配準(zhǔn)算法，即在全局優(yōu)化過程中可利用GPU框架實現(xiàn)并行計算，提高加速點云全局優(yōu)化配準(zhǔn)效率。