林洪彬 劉 彬 張玉存

1.燕山大學，秦皇島，066004

2.河北省測試計量技術與儀器重點實驗室，秦皇島，066004

0 引言

點云配準是計算機視覺領域的基本問題之一，廣泛應用于距離數據融合、醫(yī)學圖像對準、目標定位、跟蹤及識別［1］。ICP算法是經典的點云配準算法，然而，ICP算法存在如下不足：①代價函數的不可微性要求點云之間有足夠的重疊區(qū)域，否則算法容易陷入局部極小；②ICP算法需要一個緊的初始條件。上述兩點要求在應用ICP算法之前必須通過一定的預處理方法估計點云之間的重疊區(qū)域，并進行粗配準，以獲得ICP算法的初始值。點云配準的難點在于異常值、背景和噪聲等對配準精度的影響。為了消除上述因素對配準算法精度和魯棒性的影響，文獻［2－3］相繼對ICP算法進行了改進。除此之外，人們還提出了兩類方法對配準算法的魯棒性進行改善。第一類方法通過對異常值、背景和噪聲進行統(tǒng)計學建模，進而采用 ML/MAP估計的方法進行配準。如Hasler等［4］研究了圖像配準中的異常值建模問題；Ying等［5］研究了基于統(tǒng)計模型的局部重疊對象識別問題。然而，這類方法的問題在于，在許多實際應用場合，對干擾因素的精確統(tǒng)計學建模是不可行的。第二類方法采用變換不變的魯棒特征結合代價函數進行配準，以獲得針對異常值、背景和噪聲等干擾魯棒性更好的配準算法。如Viola等［6］提出了一種基于融合信息的配準算法；Tsin等［7］提出了一種基于統(tǒng)計相關的魯棒點云配準算法（KC算法）；Huttenlocher等［8］提出了一種基于局部Hausdorff距離的配準算法；Chui等［9］提出了一種基于混合模型的特征配準算法；Jian等［10］提出了一種基于高斯混合模型的魯棒配準算法（GMM（gaussian mixture model）算法）等。楊靜等［11］提出了一種基于簡單Schur凹函數的圖像配準測度；李暉等［12］提出了塔式分解和模糊梯度場的圖像配準算法。這類算法的問題在于不同的代價函數和優(yōu)化方法對算法性能影響較大。因此，設計合適的代價函數并根據代價函數的特點探尋全局合適的優(yōu)化方法成為此類算法的關鍵，本文即屬于此類方法。

本文基于核密度估計理論提出了一種新的測度函數，對不同參數下測度的性能進行分析，論證了利用該測度進行尋優(yōu)配準時存在的局部極值現象和極值漂移現象。在此基礎上提出了一種基于BFGS擬牛頓法的變尺度優(yōu)化配準算法，解決了算法魯棒性與配準精度之間的矛盾。

1 點云的核密度分布模型建立

設M＝｛mi，i＝1，2，…，Nm｝表示模型點云，S＝｛si，i＝1，2，…，Ns｝表示場景點云，兩個點云可以視為對目標所對應的實向量空間Rd進行觀測所得到的樣本。

其中，H為d×d階正定帶寬矩陣，為簡化計算，取H＝hId，Id為d×d階單位矩陣；K：Rd→R為滿足如下條件的非負核函數：

對于三維點云，d＝3。出于一般性考慮，選取高斯函數作為概率估計的核函數，即

由此，可以通過上述過程分別建立離散點云M和S的連續(xù)核密度分布模型。

2 相似性測度的構造

核密度函數相似性測度對配準算法性能的提高具有重要作用，通常用于描述兩個核密度分布相似性的測度有積分絕對值誤差測度、Kullback－Liebler測度、MI（mutual information）測度、歐氏測度等［10］。不同的測度函數優(yōu)化過程具有不同的魯棒性和計算效率，如歐氏距離計算方便、意義明確，在相似性評價方面得到了廣泛應用，但相比于Kullback－Liebler測度，其魯棒性稍差。在文獻［10］提出的GMM測度函數的基礎上，本文提出了如下測度函數：

當α→0時，有

當α→1時，有

此時，d1（f，g）為與之間的歐氏距離。因此，利用本文提出的測度函數可以通過單一參數α可以調整算法的魯棒性和漸進效率。

當配準對象為剛體時，空間變換矩陣T可以表示為：T（M）＝Rmi＋t，（i＝ 1，2，…，Nm），其中R為3×3階旋轉矩陣，t為3×1階平移向量。此時，

令x＝Rx′＋t，則

由式（3）可得

由于R為剛體變換矩陣，故，RRT＝I3，detR＝1，則

將式（10）代入式（8）可得

當α＝1時，測度函數F（T）的解析表達式為

當α＝2時，測度函數F（T）的解析表達式為

3 相似性測度的性能分析

首先，隨機生成一個3×100的服從正態(tài)分布的隨機矩陣作為場景點云M。其次，對場景點云M沿x軸方向平移3個單位，并隨機選取其中50列作為模型點云S。h分別取0.1，10，20，50，100時，測度函數隨偏移量tx的變化關系如圖1所示（說明：本文除角度的量綱?。ā悖┗騬ad，其他均為量綱一量）。再采用同樣的方法測試測度函數對旋轉參數的性能，設定模型點云和場景點云之間的旋轉關系為θx＝π/3。此時，測度函數隨旋轉量θx的變化關系如圖2所示。

圖1 不同參數下測度函數與偏移量tx關系曲線

圖2 不同參數下測度函數與繞x軸旋轉角θx關系曲線

由式（14）可知，α＝1的情況下本文測度等價于文獻［7］和文獻［14］所采用的測度。圖1表明，針對平移變換，通過搜索測度函數的極大值可以確定平移參量，實現點云的平移配準。圖1a表明：α＝1時，尺度參數越大測度函數曲線越寬，曲線越光滑，峰值位置偏離真實值，采用大尺度參數的測度函數進行配準時將存在殘余誤差，我們把這種現象稱為過尺度參數導致的極值漂移現象；尺度參數越小測度函數曲線越窄，曲線可能出現局部極值點，采用小尺度參數的測度函數進行配準時算法可能因陷入局部極小而導致失配，我們把這種現象稱為欠尺度參數導致的局部極值現象。圖1b表明，當選取α＝2時，測度函數曲線在極值漂移和局部極值方面性能更好，采用此測度函數的配準算法具有更好的魯棒性和配準精度。圖2表明，在進行旋轉參數的配準時，選取參數α＝1也會導致極大值漂移和局部極值的問題，而選取參數α＝2可以改善這兩種現象，提高算法的魯棒性和準確性。

為了檢驗測度函數極值點的統(tǒng)計穩(wěn)定性，將實驗重復進行100次，統(tǒng)計各種測度函數全局極大值所在位置的均值μ和標準差σ，實驗結果如表1和表2所示。

表1 測度函數對平移參數估計結果統(tǒng)計表

表2 測度函數對旋轉參數估計結果統(tǒng)計

對比三種測度可以發(fā)現，與MI測度相比，本文提出的測度和GMM測度對于平移參數和旋轉參數的估計均具有更好的準確性和有效性。通過對比GMM測度實驗結果和本文測度實驗結果可以發(fā)現，當α＝1時，本文測度的估計性能與GMM測度估計性能相同，而當α＝2時，測度對參數估計的性能優(yōu)于GMM測度的估計性能。

4 基于BFGS優(yōu)化的變尺度配準算法

通過表1和表2可以發(fā)現，應用本文提出的測度可以改善配準參數估計的準確性和有效性。然而，對比不同尺度參數下GMM測度和本文測度的性能可以發(fā)現，隨著尺度的增大，對平移參數和旋轉參數估計的偏倚現象明顯，導致參數估計準確度降低。圖1和圖2也表明，尺度參數過小可能會導致局部極值現象的產生，從而導致點云失配。為此，本文提出了一種基于BFGS優(yōu)化的變尺度配準算法，其優(yōu)化過程如圖3所示。

首先，隨機選取初始參數T0作為極值點搜索的初始條件，同時，為了保證算法的收斂域和平滑性，選取一個較大的初始參數h0。再利用BFGS擬牛頓法搜索該尺度下測度函數極大值所在位置T1，在通過某種機制減小尺度參數h并以T1為搜索初始條件，獲得T2依次類推，直至達到預定的配準精度。

圖3 變尺度優(yōu)化過程示意圖

基于BFGS優(yōu)化方法的變尺度配準算法流程如下：

（1）初始化。h0＝3λmax和T0＝［00000 0］T，并令k＝0，其中，λmax為兩個點云自相關矩陣的最大特征值，I4表示4×4階單位矩陣。

（2）更新變換矩陣T。以Tk為初始條件，以hk為尺度，利用BFGS擬牛頓法搜索測度函數F（Tk，hk）的極大值。并將此極大值所在位置記為Tk＋1。

（3）更新尺度參數h。hk＋1＝μhk，選取μ∈（0.9，0.96），k←k＋1。

（4）循環(huán)步驟（2）、（3），直至 ‖Tk＋1－Tk‖ ＜ε。

采用這種衰減尺度的BFGS擬牛頓搜索法進行配準主要有三個優(yōu)點：① 拓展了算法的收斂域；②克服了欠尺度參數導致的局部極值現象，減小了算法失配的可能；③克服了過尺度參數導致的極大值漂移現象，提高了配準精度。

5 實驗研究

為了驗證算法的性能，本節(jié)分別通過仿真信號和實測信號的配準實驗對算法的可靠性和魯棒性進行分析和比較。

5.1 受白噪聲干擾點云配準實驗（實驗1）

（1）模型點云M的構造。通過如下公式構造一條三維空間曲線，并在該曲線均勻選取200個點作為模型點云M：

（2）場景點云S的構造。對模型點云M進行旋轉和平移變換，變換參數

再增加信噪比為20dB的白噪聲作為干擾，由此構造場景點云S。原始點云以及通過ICP、GMM和本文方法的配準結果如圖4所示。

圖4表明，在給定實驗條件下ICP算法、GMM算法和本文算法均可實現點云的精確配準，說明這幾種方法相對與白噪聲干擾都具有魯棒性。

圖4 帶噪聲點云配準實驗結果

5.2 配準算法收斂性能實驗（實驗2）

為了檢驗算法的收斂性能，設計了實驗2，實驗中模型點云M的生成方法和實驗1相同。在此基礎上分別改變繞x軸方向轉角θx∈（－π，π）和沿x方向平移tx∈（－20，20），并附加20dB白噪聲作為場景點云S。分別用ICP算法，GMM算法和本文算法（α＝1，μ＝0.9）進行配準，求取各種算法的配準誤差。配準誤差隨變換參數變化關系曲線如圖5所示。

圖5 配準誤差隨變換參數變化關系曲線

觀察圖5a可以發(fā)現，在針對單純平移參數的配準中，ICP算法和本文算法在（－20，20）范圍內可獲得全局收斂的配準效果，而GMM算法的收斂范圍為（－4.3，4.3）。這說明在處理單一平移參數的配準時，GMM算法要求兩個點云之間的相對平移量較小，限制了算法的實際應用。由圖5b可知，針對單純旋轉變換，ICP算法的收斂區(qū) 間 為（－85°，85°），GMM 算 法 的 收 斂 區(qū) 間為（－90°，105°），而 本 文 算 法 的 收 斂 區(qū) 間為（－180°，170°）。收斂區(qū)間越寬，說明使用該算法時兩個點云之間的相對變換參數的允許范圍就越大，從而算法的適用性就越好。綜合分析圖5可以發(fā)現，不論是針對旋轉參數的配準還是針對平移參數的配準，相對于ICP算法和GMM算法，本文提出的算法都具有更好的收斂性能。

5.3 局部重疊點云配準實驗（實驗3）

為了驗證點云局部重疊情況下本文算法與傳統(tǒng)算法的性能，設計了實驗3。實驗原始數據為一組人臉激光掃描散亂點云，記為PtsFace，掃描點數NPtsFace＝392，點云PtsFace的坐標分布范圍如下：（x×y×z）∈（［－1.18，1.11］×［－0.58，1.15］×［－1.82，2.56］）。取散亂點PtsFace的前80%的點作為模型點云M。再對PtsFace進行變換，參數［θxθyθztxtytz］T＝［π/5 0 0 0.2 0 0］T，取變換后點云的后70% 作為場景點云S。實驗結果如圖6所示。

圖6 局部重疊點云配準實驗結果

圖6表明，在給定實驗條件下，ICP算法陷入局部極小，不能實現給定點云的配準。圖6c表明，當參數選取為σ＝0.56時，GMM算法存在殘余誤差。由前面的理論分析可知，該殘余誤差是由過尺度參數引起的極值點漂移引起的，不能通過增加迭代次數和降低門限值的方法加以改善。

圖6d表明，當參數選取為σ＝0.02時，GMM算法配準失敗，由上文分析可知，這是由于欠尺度參數導致的局部極值現象所引起的，而這種現象主要存在于點云之間存在非重疊區(qū)域的情況。然而，在實際應用中點云之間往往存在明顯的非重疊區(qū)域。因此，GMM算法在實際應用中也受到限制。圖6e和圖6f表明，本文方法可以實現具有非重疊區(qū)域點云的精確配準。

6 結束語

針對傳統(tǒng)點云配準算法魯棒性差、收斂區(qū)間窄的缺點，基于核密度估計的思想，提出了一種新的魯棒的點云配準算法。本文從點云的概率分布模型建立入手，將點云配準問題表述為核密度函數相似性尋優(yōu)問題，提出了用于描述核密度分布相似性的測度函數，研究了該測度函數的性能及其與其它測度函數之間的關系。針對算法實際應用中過尺度參數和欠尺度參數兩種情況造成的配準殘余誤差和配準失敗的情況，提出了一種變尺度BFGS尋優(yōu)方法，實現了點云的魯棒、精確配準。

［1］Salvi J，Matabosch C，Fofi D，et al.A Review of Recent Range Image Registration Methods with Accuracy Evaluation［J］.Image and Vision Computing，2007，25（5）：578－596.

［2］Fitsgibbon A W.Robust Registration of 2Dand 3D Point Sets［J］.Image and Vision Computing，2001，21（13/14）：1145－1153.

［3］Granger S，Pennec X.Multi－scale EM－ICP：A Fast and Robust Approach for Surface Registration［C］//In ECCV’02.London：Springer－ Verlag，2002：418－432.

［4］Hasler D，Sviaz L，Süsstrunk S.Outlier Modeling in Image Matching［J］.PAMI，IEEE Trans.，2003，25（3）：301－315.

［5］Ying Z，Castanon D.Partially Occluded Object Recognition Using Statistical Models［J］.International Journal of Computer Vision，2002，49（1）：57－78.

［6］Viola P，WellsⅢ W M.Alignement by Maximization of Mututal Information［J］.International Journal of Computer Vision，1997，24（2）：137－154.

［7］Tsin Y，Kanade T.A Correlation－based Approach to Robust Point Set Registration［C］//ECCV’04.London：Springer－Verlag，2004：558－569.

［8］Huttenlocher D P，Klanderman G A，Gregory A K，et al.Comparing Images Using the Hausdorff Distance［J］.IEEE Trans.Pattern Anal.Mach.Intell.，1993，15（9）：850－863.

［9］Chui H，Rangarajan A.A Feature Registration Framework Using Mixture Models［C］//IEEE Workshop on Mathematical Methods in Biomedical Image Analysis，Washington：IEEE Computer Society，2000：190－197.

［10］Jian B，Vemuri B C.A Robust Algorithm for Point Set Registration Using Mixture of Gaussians［C］//ICCV’05.Beijing，2005：1246－1251.

［11］楊靜，胡順波，劉常春，等.基于簡單Schur凹函數的圖像配準測度研究［J］.電子學報，2008，36（12）：2328－2332.

［12］李暉，彭玉華，尹勇.基于平移旋轉不變的塔式分解和模糊梯度場的醫(yī)學圖像配準［J］.電子學報，2009，37（4）：854－859.

［13］Silverman B W.Density Estimation for Statistics and Data Analysis［M］.London：Chapman and Hall，1986：170－180.

［14］Boughorbel F，Mercimek M.A New Method for the Registration of Three－dimensional Pointsets：The Gaussian Fields Framework［J］.Image and Vision Computing，2010，28（1）：124－137.