秦紅星徐 雷

(重慶郵電大學(xué)計算智能重慶市重點(diǎn)實(shí)驗室 重慶 400065)

(重慶郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 重慶 400065)

基于信息論的KL-Reg點(diǎn)云配準(zhǔn)算法

秦紅星*徐 雷

(重慶郵電大學(xué)計算智能重慶市重點(diǎn)實(shí)驗室 重慶 400065)

(重慶郵電大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 重慶 400065)

針對含有高噪聲、體外點(diǎn)及不完整點(diǎn)云數(shù)據(jù)的配準(zhǔn)失效問題，該文提出以信息論為理論基礎(chǔ)，相對熵度量點(diǎn)云相似度的KL-Reg算法。該算法不需要顯式地建立對應(yīng)關(guān)系，首先將點(diǎn)云數(shù)據(jù)建模為高斯混合模型，然后用相對熵度量高斯混合模型間的分布距離，最后通過最小化分布距離計算模型變換。實(shí)驗結(jié)果表明所提的KL-Reg算法配準(zhǔn)精度高、穩(wěn)定性強(qiáng)。

機(jī)器視覺；點(diǎn)云配準(zhǔn)；KL散度；高斯混合模型

1 引言

點(diǎn)云數(shù)據(jù)配準(zhǔn)是計算機(jī)視覺和計算機(jī)圖形學(xué)中的重要研究內(nèi)容，是3維重建、圖像配準(zhǔn)[1]和3維形狀檢索[2,3]的核心技術(shù)，其主要目的是尋找一個模型變換以實(shí)現(xiàn)兩幅點(diǎn)云的對齊。點(diǎn)云配準(zhǔn)過程面臨許多挑戰(zhàn)。首先，數(shù)據(jù)本身存在的高噪聲、體外點(diǎn)等會影響配準(zhǔn)精度；其次，在3維數(shù)據(jù)采集過程中，由于掃描儀的視角和自遮擋問題，獲得的數(shù)據(jù)經(jīng)常存在缺失或者只有少部分重合等問題。使得尋找點(diǎn)到點(diǎn)的對應(yīng)關(guān)系變得非常困難，并由于點(diǎn)云間對應(yīng)不準(zhǔn)確往往造成配準(zhǔn)失效。另外，點(diǎn)云數(shù)據(jù)的初始位置也會影響配準(zhǔn)算法的性能。

目前的點(diǎn)云配準(zhǔn)算法主要分為3類：迭代最近點(diǎn)配準(zhǔn)算法ICP(Iterate Closed Point)[4,5]、基于統(tǒng)計的方法和基于特征對應(yīng)的配準(zhǔn)方法。1992年Besl和McKay提出了ICP[4]算法，該方法以歐式距離最近的點(diǎn)對作為對應(yīng)點(diǎn)對，思想簡單、易于實(shí)現(xiàn)是最常用的點(diǎn)云配準(zhǔn)算法。但是ICP算法依賴對應(yīng)關(guān)系[6]，對兩幅點(diǎn)云的初始距離比較敏感。2013年Tagliasacch等人[5]提出稀疏迭代最近點(diǎn)算法(sparse iterative closet point)，該算法在配準(zhǔn)含噪聲和體外點(diǎn)的點(diǎn)云數(shù)據(jù)時可以保持很好的魯棒性，但當(dāng)兩幅點(diǎn)云距離較遠(yuǎn)時，配準(zhǔn)的效果仍不理想。為了解決ICP算法對噪聲敏感問題，基于統(tǒng)計的配準(zhǔn)方法[7?11]被相繼提出。Myronenko等人[8]提出的CPD (Coherent Point Drift)算法，基本思想是先通過E步確定對應(yīng)概率，根據(jù)對應(yīng)概率建立似然函數(shù)，再通過M步最大化似然函數(shù)計算變換模型。不同于ICP算法中對應(yīng)點(diǎn)是一對一的關(guān)系，這類方法用概率建立兩幅點(diǎn)云之間的軟對應(yīng)(多對多)關(guān)系。另一類基于特征的配準(zhǔn)算法[12?17]一般是通過特征匹配建立點(diǎn)對的對應(yīng)關(guān)系，其中Lombaert 等人[16]提出的方法根據(jù)點(diǎn)的熱核坐標(biāo)[18,19]尋找對應(yīng)點(diǎn)。雖然特征方法在計算線性變換時的性能優(yōu)良，但需要大量的計算資源而且同樣會面臨特征對應(yīng)不準(zhǔn)確的問題。

上述3類方法存在的缺點(diǎn)是當(dāng)對應(yīng)缺失或者對應(yīng)不準(zhǔn)確時，會嚴(yán)重影響配準(zhǔn)結(jié)果。本文提出的基于信息論的KL-Reg配準(zhǔn)算法，不需要建立顯式的對應(yīng)關(guān)系，解決了由于對應(yīng)不準(zhǔn)確造成的配準(zhǔn)失效問題。與Jian[8]和CPD算法[9]相比本文方法不需要優(yōu)化高斯混合模型中的每一個高斯組件的權(quán)值。

2 KL-Reg算法思想

設(shè)點(diǎn)云M, S都是從一個實(shí)體對象采樣獲得的兩幅點(diǎn)云數(shù)據(jù)，p(x|S,r), p(x|M,w)表示點(diǎn)云S, M的采樣模型分布，配準(zhǔn)S, M，就是使它們的分布模型盡可能相似。本節(jié)內(nèi)容包括：點(diǎn)云數(shù)據(jù)的分布模型表達(dá)；用信息理論中的KL散度度量分布距離的方法；最后是如何最小化距離目標(biāo)函數(shù)計算映射變換。

2.1 點(diǎn)云數(shù)據(jù)的模型表達(dá)

點(diǎn)云模型是由大量的散亂點(diǎn)混合在一起，設(shè)這些散亂點(diǎn)獨(dú)立同分布，則可用高斯分布來建立點(diǎn)云分布模型。文獻(xiàn)[8]把點(diǎn)云中的每一個點(diǎn)表達(dá)為一個單高斯模型(組件)，點(diǎn)云M的高斯混合模型表達(dá)為p(x|M)其中mj為M中第j的坐標(biāo)，為第j個點(diǎn)的高斯分布，wj為第j個組件的權(quán)值，, δ為高斯核函數(shù)的寬度，N為M中

M點(diǎn)的數(shù)量。

假設(shè)點(diǎn)云中的每一個點(diǎn)都是以相同的概率從一個高斯混合模型隨機(jī)采樣獲得，則每一個高斯組件的權(quán)值是相同的，設(shè)wj=1/NM。為了對噪聲和體外點(diǎn)建模，高斯混合模型中增加一個額外的統(tǒng)一采樣分布p(x|M')=1/NM表示噪聲和體外點(diǎn)。假定點(diǎn)云M, S都是從一個實(shí)體對象采樣獲得的數(shù)據(jù)，則兩個高斯混合模型的高斯核寬度相同，噪聲比例相同。加入噪聲后M的高斯混合模型可表達(dá)為

其中0≤p(x|mj)≤1,wj=1/NM, η表達(dá)點(diǎn)云中噪聲點(diǎn)所占比重。同理點(diǎn)云S的高斯混合模型可表達(dá)為

其中0≤p(x|si)≤1,

當(dāng)兩幅點(diǎn)云距離越近時，其模型相似度就越高。因此配準(zhǔn)的目標(biāo)可以描述為，尋找一個模型變換T，使點(diǎn)云M經(jīng)過該變換后與點(diǎn)云S的模型分布距離最小。

2.2 高斯混合模型的相似性度量

我們采用相對熵度量點(diǎn)云M和點(diǎn)云S分布的相似程度。Hershey等人[20]論證了度量高斯混合模型KL散度的可行性，因此保證了本文算法的有效性。設(shè)f(x)和g(x)為D維空間中的兩個分布函數(shù)，其KL散度定義為

由KL散度的性質(zhì)可知：當(dāng)密度函數(shù)f(x)=g(x)時，kl(f(x)||g(x))=0；當(dāng)f(x)與g(x)的差異越大，kl(f(x)||g(x))值越大。兩幅點(diǎn)云的模型分布距離為kl(p(x|S,r)||p(x|M,w))。因此配準(zhǔn)問題可表達(dá)為

2.3 目標(biāo)函數(shù)優(yōu)化

我們通過優(yōu)化兩個分布模型距離的上界間接優(yōu)化式(3)目標(biāo)函數(shù)，分布函數(shù)f(x),g(x)的KL散度可轉(zhuǎn)化為

其中H(f(x),g(x))為f(x)和g(x)的交叉熵，H(f(x))為f(x)的信息熵。根據(jù)Hershey的方法[20]，式(4)的上界可表示為

其中klub(f(x),g(x))表示式(4)的上界，Hup(f(x), g(x))為H(f(x),g(x))上界，Hlb(f(x))為H(f(x))的下界。令f(x)=p(x|S,r ),g(x)=p(x|M,w,T)則有

其中

優(yōu)化問題轉(zhuǎn)化為求解式(1)上界，即式(6)來求解變換參數(shù)。當(dāng)2δ確定時，上述目標(biāo)函數(shù)可化為

式(7)目標(biāo)函數(shù)是機(jī)器視覺領(lǐng)域中常見的優(yōu)化問題，可以通過梯度下降法[9]來解決。高斯函數(shù)的寬度δ的選擇是上述優(yōu)化問題收斂的關(guān)鍵。本文2δ的選取采取自適應(yīng)的方法，令

在每次迭代中，點(diǎn)云M經(jīng)過模型變換后同時調(diào)整δ2。事實(shí)上可以將δ2等同于模擬退火算法中的溫度，即隨著迭代次數(shù)的增大，參數(shù)δ2逐漸減小。另外當(dāng)點(diǎn)云之間旋轉(zhuǎn)角度較大時，算法往往會陷入局部最優(yōu)，當(dāng)?shù)螖?shù)達(dá)到迭代的上限并且δ2仍然未收斂到時，即認(rèn)為配準(zhǔn)失敗。收斂閾值的大小取決于對配準(zhǔn)時間和配準(zhǔn)精度的要求，實(shí)驗表明閾值越小配準(zhǔn)的精度越高，但配準(zhǔn)的時間就越長。本文結(jié)合蟻群算法[21]的思想，當(dāng)?shù)螖?shù)達(dá)到一個閾值，并且算法不收斂時就選擇一個比較差的解，重新迭代。實(shí)驗表明一般經(jīng)過兩次調(diào)整后即可找到全局最優(yōu)解。

3 實(shí)驗結(jié)果與分析

本文算法用Matlab實(shí)現(xiàn)，硬件平臺為2.5 GHz Intel CPU, 2G內(nèi)存空間。實(shí)驗包括2維點(diǎn)云和3維點(diǎn)云配準(zhǔn)實(shí)驗以及定量對比實(shí)驗。為了與其他方法[8]的實(shí)驗結(jié)果進(jìn)行對比，本文采用文獻(xiàn)[8]中使用的數(shù)據(jù)和3維掃描儀的掃描數(shù)據(jù)進(jìn)行配準(zhǔn)實(shí)驗。配準(zhǔn)實(shí)驗收斂閾值取為10?8，調(diào)整解空間的迭代次數(shù)為30次。

3.1 2維點(diǎn)云配準(zhǔn)實(shí)驗

圖1為KL-Reg算法與CPD算法[8]配準(zhǔn)2維魚形點(diǎn)云[22]的對比實(shí)驗，圖1(a), 1(b), 1(c)為點(diǎn)云的初始分布，圖1(d),1(e),1(f)為CPD算法的配準(zhǔn)結(jié)果，圖1 (g),1(h),1(i)為KL- Reg算法的配準(zhǔn)結(jié)果。實(shí)驗結(jié)果表明CPD算法配準(zhǔn)圖1 (b)中數(shù)據(jù)時不能得到全局最優(yōu)解，文獻(xiàn)[7]的算法對2維魚形點(diǎn)云可適應(yīng)的旋轉(zhuǎn)弧度范圍為[?2.0, 2.0]。本文根據(jù)蟻群算法[21]的思想，自動調(diào)整解空間，一般經(jīng)過兩次調(diào)整后就能找到全局最優(yōu)解，實(shí)驗表明KL-Reg算法可適應(yīng)的旋轉(zhuǎn)角度范圍為[?π, π]。

圖1(c),1(f),1(i)為數(shù)據(jù)不完整時的配準(zhǔn)實(shí)驗，當(dāng)點(diǎn)云數(shù)據(jù)只有部分重合或者點(diǎn)云數(shù)據(jù)不完整時往往難以建立準(zhǔn)確的對應(yīng)關(guān)系，從而造成配準(zhǔn)失敗。實(shí)驗結(jié)果表明，KL-Reg算法在對應(yīng)不準(zhǔn)確時仍然可以準(zhǔn)確地配準(zhǔn)點(diǎn)云，算法穩(wěn)定性強(qiáng)。

圖1(a), 1(d), 1(g)為配準(zhǔn)含噪聲和數(shù)據(jù)不完整點(diǎn)云時的實(shí)驗，圖1 (d), 1(g)分別為CPD算法和KL-Reg算法配準(zhǔn)結(jié)果。在配準(zhǔn)此類數(shù)據(jù)時，KL-Reg算法比CPD算法的配準(zhǔn)結(jié)果更準(zhǔn)確。

3.2 3維點(diǎn)云配準(zhǔn)實(shí)驗

圖2數(shù)據(jù)為斯坦福掃描的中國龍點(diǎn)云數(shù)據(jù)[23]，采集中國龍點(diǎn)云時兩個掃描儀夾角分別為24°，圖2(a), 2(d)分別為從正面和背面觀察兩幅點(diǎn)云的初始位置。圖2(b), 2(e)為CPD算法配準(zhǔn)的結(jié)果，圖2(c), 2(f)為KL-Reg算法配準(zhǔn)結(jié)果?？梢园l(fā)現(xiàn)，圖2(b), 2(e)采用CPD算法配準(zhǔn)的結(jié)果中龍頭處存在較大誤差，而KL-Reg算法取得了較好的配準(zhǔn)結(jié)果(圖2(c), 2(f))。

3.3 量性對比實(shí)驗

為了更加詳盡地驗證KL-Reg算法的有效性，本文與ICP[4], CPD[8], KC-Reg[9]和EM-ICP[10]算法進(jìn)行了實(shí)驗對比，配準(zhǔn)數(shù)據(jù)為2維魚形點(diǎn)云。對比實(shí)驗包括：配準(zhǔn)含不同比例噪聲點(diǎn)云時各個算法的配準(zhǔn)時間和誤差；配準(zhǔn)不完整點(diǎn)云數(shù)據(jù)時各個算法的配準(zhǔn)誤差。圖3中配準(zhǔn)時間單位為s，誤差計算公式為

其中dis(c(M,N))為配準(zhǔn)后兩幅點(diǎn)云中對應(yīng)點(diǎn)的距離和函數(shù)，Nc為對應(yīng)點(diǎn)的個數(shù)。

表1為各個算法在配準(zhǔn)數(shù)據(jù)不完整點(diǎn)云時的配準(zhǔn)誤差。實(shí)驗結(jié)果表明KL-Reg算法的配準(zhǔn)誤差一直穩(wěn)定在10?16左右，并不會隨噪聲比例的增加而增加，而CPD算法的配準(zhǔn)誤差對不完整點(diǎn)云數(shù)據(jù)比較敏感。KC-Reg算法、EM-ICP算法和ICP算法的配準(zhǔn)誤差會隨噪聲的比例遞增而遞增，其中ICP算法的配準(zhǔn)誤差遞增的速度最快。圖3為配準(zhǔn)含不同比例噪聲數(shù)據(jù)的時間對比，ICP算法的配準(zhǔn)時間最短，雖然KL-Reg算法時間復(fù)雜度與CPD算法相當(dāng)，而配準(zhǔn)誤差一直保持穩(wěn)定，說明KL-Reg算法要比CPD算法魯棒性更高。

表1 數(shù)據(jù)缺失時的配準(zhǔn)誤差

圖1 2維魚形點(diǎn)云配準(zhǔn)實(shí)驗

圖2 中國龍3維點(diǎn)云配準(zhǔn)實(shí)驗

圖3 含噪聲點(diǎn)云數(shù)據(jù)配準(zhǔn)時間對比

4 結(jié)束語

針對配準(zhǔn)含有高噪聲、體外點(diǎn)點(diǎn)云及不完整點(diǎn)云數(shù)據(jù)時，由于難以找到準(zhǔn)確的對應(yīng)關(guān)系導(dǎo)致的配準(zhǔn)失效問題。本文提出的基于信息論的KL-Reg點(diǎn)云配準(zhǔn)算法，提高了在對應(yīng)關(guān)系不準(zhǔn)確時配準(zhǔn)的有效性和穩(wěn)定性。KL-Reg算法認(rèn)為點(diǎn)云從一個實(shí)體對象表面采樣獲得，且存在一個共同的采樣分布，那么配準(zhǔn)后的兩幅點(diǎn)云應(yīng)該符合這個采樣分布，因此配準(zhǔn)的過程描述為兩個采樣分布的擬合過程。與文獻(xiàn)[7]和文獻(xiàn)[8]CPD算法相比，本文方法不需要優(yōu)化高斯混合模型中的每一個高斯組件的權(quán)值，本文基于總體分布的思想更為簡單，易于實(shí)現(xiàn)。最后與ICP[4], CPD[8], KC-Reg[9]和EM-ICP[10]算法的實(shí)驗表明，本文算法不僅能夠精確配準(zhǔn)點(diǎn)云，而且在配準(zhǔn)不完整點(diǎn)云及有噪聲點(diǎn)云時魯棒性更高。

[1] Zitova B and Flusser J. Image registration methods: a survey[J]. Image and Vision Computing, 2003, 21(11): 977-1000.

[2] Lian Z, Godil A, Bustos B, et al.. A comparison of methods for non-rigid 3D shape retrieval[J]. Pattern Recognition, 2013, 46(1): 449-461.

[3] Liu M, Vemuri B C, Amari S I, et al.. Shape retrieval using hierarchical total bregman soft clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(12): 2407-2419.

[4] Besl P J and McKay N D. Method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 586-606.

[5] Tagliasacchi A, Bouaziz S, and Pauly M. Sparse iterative closest point[J]. Computer Graphics Forum, 2013, 32(5): 113-123.

[6] Tam G K L, Cheng Z Q, Lai Y K, et al.. Registration of 3D point clouds and meshes: a survey from rigid to nonrigid[J]. IEEE Transactions on Visualization and Computer Graphics, 2013, 19(7): 1199-1217.

[7] Jian B and Vemuri B C. Robust point set registration using gaussian mixture models[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1633-1645.

[8] Myronenko A and Song X. Point set registration: coherent point drift[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(12): 2262-2275.

[9] Tsin Y and Kanade T. A correlation-based approach to robust point set registration[C]. Computer Vision-ECCV 2004. Springer Berlin Heidelberg, Prague, 2004: 558-569.

[10] Granger S and Pennec X. Multi-scale EM-ICP: a fast and robust approach for surface registration[C]. Computer Vision—ECCV 2002, Springer Berlin Heidelberg, Copenhagen, 2002: 418-432.

[11] Hermans J, Smeets D, Vandermeulen D, et al.. Robust point set registration using EM-ICP with information-theoretically optimal outlier handling[C]. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Colorado, USA, 2011: 2465-2472.

[12] Lipman Y, Yagev S, Poranne R, et al.. Feature matching with bounded distortion[J]. ACM Transactions on Graphics, 2014, 33(3), DOI: 10.1145/2602142.

[13] Paulus S, Dupuis J, Mahlein A K, et al.. Surface feature based classification of plant organs from 3D laserscanned point clouds for plant phenotyping[J]. BMC Bioinformatics, 2013, 14(1), DOI: 10.1186/147-2105-14-238.

[14] Zeng Y, Wang C, Gu X, et al.. A generic deformation model for dense non-rigid surface registration: a higher-order MRF-based approach[C]. IEEE International Conference on Computer Vision (ICCV), Sydney, Australia, 2013: 3360-3367.

[15] Hou T and Qin H. Robust dense registration of partial nonrigid shapes[J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(8): 1268-1280.

[16] Lombaert H, Grady L, Polimeni J R, et al.. FOCUSR: feature oriented correspondence using spectral regularization?a method for precise surface matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, Australia, 2013, 35(9): 2143-2160.

[17] Chang W and Zwicker M. Automatic registration for articulated shapes[J]. Computer Graphics Forum, 2008, 27(5): 1459-1468.

[18] Bronstein M M and Kokkinos I. Scale-invariant heat kernel signatures for non-rigid shape recognition[C]. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), San Francisco, 2010: 1704-1711.

[19] Sun J, Ovsjanikov M, and Guibas L. A concise and provably informative multi-scale signature based on heat diffusion[J]. Computer Graphics Forum, 2009, 28(5): 1383-1392.

[20] Hershey J R and Olsen P A. Approximating the Kullback Leibler divergence between Gaussian mixture models[C]. IEEE International Conference on Acoustics, Speech and Signal Processing, Honolulu, 2007(4): 317-320.

[21] Karaboga D, Gorkemli B, Ozturk C, et al.. A comprehensive survey: artificial bee colony (ABC) algorithm and applications[J]. Artificial Intelligence Review, 2014, 42(1): 21-57.

[22] Chui Hai-li. Point matching[OL]. http://www.cise.ufl.edu /～anand/students/chui/research.html. 2014.5.

[23] Stanford computer graphics laboratory. 3Dscanrep[OL]. http://graphics.stanford.edu/data/3Dscanrep/. 2014.5.

秦紅星： 男，1978年生，教授，主要研究方向為計算機(jī)圖形學(xué)與可視化.

徐 雷： 男，1989年生，碩士生，研究方向為計算機(jī)圖形學(xué).

Information Theory Based KL-Reg Point Cloud Registration

Qin Hong-xing Xu Lei
(Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)
(College of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

The registration of point clouds with high noises, outliers and missing data will be failure because the correspondence between point clouds is inaccurate. This paper proposes a information theory based point cloud registration method called KL-Reg algorithm without building correspondence. The method represents the point cloud with Gaussian mixture model, then computes the transformation through minimizing the KL divergence without build explicit correspondence. Experimental results show that KL-Reg algorithm is precise and stable.

Machine vision; Point clouds registration; KL-divergence; Gaussian mixture model

TP391

： A

：1009-5896(2015)06-1520-05

10.11999/JEIT141248

2014-09-25收到，2015-02-27改回

國家自然科學(xué)基金青年科學(xué)基金(61100113)，國家教育部留學(xué)歸國基金教外司留[2012]940號，重慶市首批青年骨干教師項目(渝教人(2011)31號)，重慶市基礎(chǔ)與前沿研究計劃項目(cstc2013jcyjA 40062)，重慶郵電大學(xué)學(xué)科引進(jìn)人才基金(A2010-12)和重慶市研究生科研創(chuàng)新項目(CYS14142)資助課題

*通信作者：秦紅星 qinhx@cqupt.edu.cn