摘  要： 提出了一種新型兩步式迭代最近點算法對三維人耳點云模型進(jìn)行配準(zhǔn),，該過程主要分為兩步完成：（1）采用基于CUDA并行加速的ICP" title="EM-ICP" target="_blank">EM-ICP算法進(jìn)行初始配準(zhǔn),，從而使人耳點云數(shù)據(jù)大致調(diào)整為同一姿態(tài)，并且為下一步提供良好的初始變化,；（2）基于ICP算法對三維人耳點云數(shù)據(jù)進(jìn)行精確配準(zhǔn),。該方式能夠有效避免ICP算法配準(zhǔn)過程中局部對齊等缺陷。實驗結(jié)果證明,，采用兩步式迭代最近點算法配準(zhǔn)后的三維人耳數(shù)據(jù)具有良好的配準(zhǔn)效果與配準(zhǔn)速度,。

　　關(guān)鍵詞： EM-ICP；ICP；人耳,；點云配準(zhǔn)；CUDA

0 引言

　　在當(dāng)今信息化時代,，隨著科學(xué)技術(shù)的不斷發(fā)展,，傳統(tǒng)的基于身份證、學(xué)生證,、磁卡等的身份鑒別技術(shù)存在容易被偽造,、被盜取以及容易遺失等問題，暴露出越來越多的缺陷,。它們已經(jīng)不能滿足人們對快速,、便捷、有效的身份識別技術(shù)的需求,。在此情況下,，生物特征識別技術(shù)應(yīng)時而生。人耳識別是以人耳作為識別媒介來進(jìn)行身份的鑒別,，是一種很有發(fā)展?jié)摿Φ纳锾卣髯R別技術(shù),，受到了國內(nèi)外眾多研究機(jī)構(gòu)的廣泛關(guān)注。研究指出,，沒有任何兩個人（即使是雙胞胎）的耳朵是完全一樣的,，并且在8~70歲之間都不會有顯著的變化，可以作為個體生物識別的依據(jù),。人耳形狀特征很豐富,，其表面具有大量的溝和脊，不受胡須,、化妝品,、年齡、表情等影響,，具有更高的穩(wěn)定性,、唯一性和健壯性，為人耳識別技術(shù)提供了理論研究價值和實際應(yīng)用前景,。

　　隨著三維掃描技術(shù)的迅速發(fā)展,，三維數(shù)據(jù)的獲取變得更加方便，三維模型已經(jīng)成為繼數(shù)字音頻,、數(shù)字圖像,、數(shù)字視頻之后一種新的數(shù)字媒體形式。三維人耳模型包含的特征信息比二維圖像更為豐富,，因此基于三維人耳的識別技術(shù)便逐漸發(fā)展起來,。三維人耳模型不但能夠很好的反應(yīng)人耳的輪廓信息，而且能夠很好地描述人耳的結(jié)構(gòu)和姿態(tài)信息。采用三維人耳數(shù)據(jù)進(jìn)行識別能有效解決姿態(tài)變換,、陰影和光照條件改變等問題對識別率的影響,，因此更適合采用三維的方式來進(jìn)行采集和識別。

　　三維人耳模型識別的步驟大致如下：首先使用三維掃描儀獲取人側(cè)臉的深度圖像,；其次將人耳數(shù)據(jù)從人側(cè)臉數(shù)據(jù)中準(zhǔn)確地提取出來,；最后將不同人耳數(shù)據(jù)或其特征進(jìn)行配準(zhǔn)，通過比較人耳數(shù)據(jù)之間的配準(zhǔn)誤差,，從而實現(xiàn)三維人耳識別,。

1 相關(guān)工作

　　迭代最近點（Iterative Closest Points，ICP）算法[1]是目前最常用的三維數(shù)據(jù)配準(zhǔn)算法,，通過迭代最小化兩待配準(zhǔn)點云上對應(yīng)點間的距離誤差,，獲得最佳的旋轉(zhuǎn)矩陣和平移矩陣，實現(xiàn)精確配準(zhǔn),。迭代最近點算法能夠滿足大多數(shù)三維數(shù)據(jù)的配準(zhǔn)要求,，但這些算法在不知道待配準(zhǔn)模型之間對應(yīng)點的情況下都需要有一個良好的初始變換，不好的初始變換會導(dǎo)致三維模型局部收斂,，直接影響著三維數(shù)據(jù)的配準(zhǔn)效果,。因此，為避免該缺陷,，許多研究者采用了很多解決方式,。2002年Granger等[2]提出EM-ICP算法，將最大期望（EM）算法[3]應(yīng)用到ICP算法中,，從而避免了初始配準(zhǔn)的步驟,。2005年，Hui等[4]利用兩步迭代最近點算法對人耳進(jìn)行配準(zhǔn),，首先利用ICP算法對耳輪數(shù)據(jù)進(jìn)行粗配準(zhǔn),，然后將該變換矩陣作為初始變換再次應(yīng)用在ICP算法中，對第一步的匹配進(jìn)行優(yōu)化,，提高識別效率,。2007年，Yan等[5]通過主成分分析（PCA）[6]算法對待配準(zhǔn)點云先進(jìn)行初始配準(zhǔn),，調(diào)整人耳的姿態(tài),，再對初始配準(zhǔn)后的結(jié)果使用ICP算法進(jìn)行精確配準(zhǔn)。同年,，Chen等[7]利用四元組計算初始變換進(jìn)行粗對齊,，再利用ICP算法進(jìn)行精確匹配。

　　隨著三維掃描技術(shù)的不斷發(fā)展,，三維掃描儀的掃描精度不斷提高,，數(shù)據(jù)規(guī)模也隨之增大,。由于ICP算法、EM-ICP算法均需要對大規(guī)模的矩陣進(jìn)行運(yùn)算,，數(shù)據(jù)規(guī)模的增大必然導(dǎo)致工作效率的降低,，傳統(tǒng)的串行配準(zhǔn)合并算法的效率已無法滿足實時性的需求。圖形處理單元GPU進(jìn)行并行計算,，由多個流處理器分別進(jìn)行數(shù)值運(yùn)算,，實現(xiàn)任務(wù)級和數(shù)據(jù)級的并行，能夠很好地解決上述問題,。NVIDIA公司推出的統(tǒng)一計算架構(gòu)CUDA提供了高性能的GPU并行計算環(huán)境，可用于大規(guī)模三維數(shù)據(jù)的處理,。由CPU作為主機(jī)負(fù)責(zé)邏輯性強(qiáng)的事務(wù)處理和串行計算,，GPU作為協(xié)處理器完成可并行計算的部分，高度線程化的并行處理任務(wù)則由CPU和GPU共同完成,，大大提高了程序的運(yùn)行效率和數(shù)據(jù)的處理速度,，使由于數(shù)據(jù)規(guī)模較大、精度要求較高造成的配準(zhǔn)及合并效率降低等問題得以解決,。2008年Choi等[8]基于CUDA對ICP算法進(jìn)行了并行加速,，實現(xiàn)了對深度圖像進(jìn)行實時配準(zhǔn)。2010年Tamaki等[9]基于CUDA對EM-ICP算法進(jìn)行了并行加速,，配準(zhǔn)速度明顯提高,。

　　根據(jù)上述學(xué)者們的研究，本文提出了一種兩步式迭代最近點算法對三維人耳點云模型進(jìn)行配準(zhǔn),。首先采用基于CUDA加速的EM-ICP算法作為ICP算法的初始配準(zhǔn),，使人耳點云數(shù)據(jù)大致調(diào)整為同一姿態(tài)，然后基于該算法提供的初始變化采用ICP算法對三維人耳點云數(shù)據(jù)進(jìn)行精確配準(zhǔn),，相當(dāng)于進(jìn)行了兩次配準(zhǔn),，最終達(dá)到配準(zhǔn)效果。

2 基于EM-ICP的初始配準(zhǔn)

　　初始配準(zhǔn)能夠有效調(diào)整三維模型的位置與姿態(tài),，為精確配準(zhǔn)提供一個理想的初始變換,。本文采用基于CUDA加速的EM-ICP算法對三維人耳模型進(jìn)行初始變換，EM-ICP算法不需要建立初始對應(yīng)關(guān)系,，以權(quán)重表示兩點間的配準(zhǔn)概率,，迭代運(yùn)算優(yōu)化配準(zhǔn)概率，最終實現(xiàn)點云配準(zhǔn),。

　　已知三維人耳點云模型X={xi,，i=1，…,，n}與三維人耳點云模型Y={yi,，i=1,，…，m},，n與m分別表示人耳點云模型X與Y中點云個數(shù),，模型X上的任意一點xi與模型Y上所有點都存在一個對應(yīng)關(guān)系，且用權(quán)重的大小來表示配準(zhǔn)概率,。通過求解模型的變換矩陣R與t,，更改人耳點云模型Y的位置，直到點云模型間誤差函數(shù)E最小,。

　　其中,，ij表示xi與對應(yīng)點yi的配準(zhǔn)概率。

　　因此,，點云模型間誤差函數(shù)E可重寫為：

　　EM-ICP算法[2]具體步驟如下：

　?。?）若E大于閾值τ且?滓p小于0.3，則返回到（2）,，否則迭代結(jié)束,。

　　EM-ICP算法中，點云模型X上的每一個點都與點云模型Y上所有點存在一個對應(yīng)關(guān)系,，即匹配概率ij,，因此計算全映射的關(guān)系矩陣A=（ij）與兩個點云模型的規(guī)模密切相關(guān)，當(dāng)點云模型的規(guī)模較大時,，對矩陣A運(yùn)算的時間很長,，對矩陣A的計算進(jìn)行GPU并行加速，加快算法效率,。

　　對原算法進(jìn)行并行加速的關(guān)鍵問題是將運(yùn)算過程分為向量與矩陣的運(yùn)算和矩陣內(nèi)元素間的運(yùn)算兩種,，利用CUBLAS（CUDA Basic Linear Algebra Subprograms）[10]對向量與矩陣間的運(yùn)算進(jìn)行加速，編寫CUDA kernel函數(shù)對矩陣元素間的運(yùn)算進(jìn)行加速[9],。具體步驟如下：

　?。?）將模型X、Y拷貝到顯存中,，并且對CUDA環(huán)境及CUBLAS庫函數(shù)初始化,；

　　（2）計算模型X,、Y對應(yīng)點之間的距離dij,；

　　（6）求解旋轉(zhuǎn)矩陣R,、平移矩陣t,；

　　（7）更新模型Y的位置Y=RY+t,；

　?。?）更新控制參數(shù),；

　　（9）若E大于閾值τ且p小于0.3,，則返回到（2）,，否則迭代結(jié)束。

3 基于ICP的精確配準(zhǔn)

　　本文采用ICP算法對粗配準(zhǔn)后的三維人耳模型進(jìn)行精確配準(zhǔn),。ICP算法能夠?qū)ι疃葓D像進(jìn)行有效的配準(zhǔn),，是當(dāng)前眾多配準(zhǔn)算法的基礎(chǔ)。ICP算法不斷地更新一個點云模型的位置,，直到該模型與另一個點云模型對應(yīng)點之間的距離達(dá)到某閾值為止,。在ICP算法中，點云模型X上的任意一點xi在點云模型Y上有且僅有一個對應(yīng)點,。

　　已知點云模型X={xi,，i=1，…,，n}與點云模型Y={yi，i=1,，…,，m}，n與m分別表示人耳點云模型X與Y中點云個數(shù),，尋找點云模型X上每一個點xi到點云模型Y上的最近點yi,，通過求解模型的變換矩陣R與t，更改模型點云Y的位置,，直到點云模型間誤差函數(shù)E最小,。

　　ICP算法的主要目的是求解兩個點云模型之間的空間變換，通過這個空間變換使得兩點云模型之間的距離最小,，其具體步驟如下：

　?。?）點云模型X與模型Y初始對齊；

　?。?）找到點云Y中距離點云X中xi最近的點yi,；

　　（3）采用四元數(shù)方法解旋轉(zhuǎn)矩陣R,，平移矩陣t,，并求解；

　?。?）更新模型Y的位置X=RX+t,；

　　（5）若E大于閾值τ,，則返回到（2）,，否則迭代結(jié)束,。

4 實驗結(jié)果及分析

　　實驗所用三維掃描儀的分辨率為640×480，幀頻為24 f/s,。實驗程序運(yùn)行硬件配置為：Intel Xeon [email protected] GHz處理器,，16 GB內(nèi)存，NVIDIA Quadro 2000顯卡,，192個CUDA核心,，1 GB GDDR5顯存容量，計算能力2.1,。系統(tǒng)環(huán)境：Fedora 16 Linux,，CUDA6.5，GCC4.6.3,。

　　4.1 數(shù)據(jù)采集

　　通過三維激光掃描儀可以得到人耳側(cè)面的掃描數(shù)據(jù),，但是得到的數(shù)據(jù)不僅包括人耳數(shù)據(jù)，還包括人耳附近的皮膚數(shù)據(jù),，需要將這些無用的數(shù)據(jù)除去,，將人耳數(shù)據(jù)提取出來。

　　提取到人耳數(shù)據(jù)后,，去掉其顏色信息,，得到需要的三維人耳數(shù)據(jù)模型。在下面的實驗中將使用提取得到的三個人耳數(shù)據(jù),，如圖1所示,，提取得到的人耳數(shù)據(jù)，方向各不相同,，分別為其編號為ear_a,，ear_b，ear_c,。

　　4.2 配準(zhǔn)效果

　　本文選用CUDA加速的EM-ICP算法作為ICP算法的初始配準(zhǔn),，再使用ICP算法進(jìn)行精確配準(zhǔn)。進(jìn)行兩次配準(zhǔn),，既保證了配準(zhǔn)速度,，又保證了配準(zhǔn)精度，最終得到了理想的配準(zhǔn)效果,。如表1所示,，將ear_a作為待配準(zhǔn)模型，對ear_a與ear_b,，ear_a與ear_c分別進(jìn)行EM-ICP粗配準(zhǔn)與ICP精確配準(zhǔn),。

　　由表1能夠清楚看出，人耳模型ear_b,、ear_c經(jīng)過EM-ICP粗配準(zhǔn)后,，能夠初步調(diào)整人耳模型的位置,，ICP精確配準(zhǔn)后均達(dá)到了理想的配準(zhǔn)效果。

　　如圖2所示,，待配準(zhǔn)模型ear_a與配準(zhǔn)后的ear_b,、ear_c模型位置?？梢钥闯?，配準(zhǔn)后的ear_b、ear_c均調(diào)整到與模型ear_a姿態(tài)一致的位置,。

　　4.3 配準(zhǔn)精度

　　將ear_a作為配準(zhǔn)模型,，對ear_a與ear_b、ear_a與ear_c進(jìn)行不同方式的配準(zhǔn),，如圖3所示為分別基于ICP[1],、EM-ICP[9]、兩步式ICP[4]以及本文提出的EM-ICP和ICP算法相結(jié)合的方式進(jìn)行配準(zhǔn)得到的配準(zhǔn)精度,。由圖可見,，本文算法與其他算法相比，具有較高的配準(zhǔn)精度,，配準(zhǔn)效果優(yōu)于其他方式,。

　　4.4 配準(zhǔn)時間

　　如表2所示，將分別基于ICP[1],、EM-ICP[9],、兩步式ICP[4]以及本文提出的EM-ICP和ICP算法相結(jié)合的方式進(jìn)行配準(zhǔn)所用時間進(jìn)行對比,。顯然,，ICP算法效率略低，EM-ICP算法具有很高的效率,，采用兩種迭代方式的時間消耗比采用一種迭代方式的時間消耗高,，然而在均采用兩種迭代方式前提下，本文算法的時間消耗要優(yōu)于兩步式ICP算法,，并且本文算法與只基于ICP算法相比,，其時間消耗差距不大。

參考文獻(xiàn)

　　[1] BESL P J,， MCKAY N D. A method for registration of 3-d shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,， 1992，14（2）：239-256.

　　[2] GRANGER S,， PENNEC X. Multi-scale EM-ICP： a fast and robust approach for surface registration[C]. Proceedings of the 7th European Conference on Computer Vision. Copen-hagen,， Denmark： Springer-Verlag， 2002：418-432.

　　[3] DEMPSTER A,， LAIRD N,， RUBIN D. Maximum likelihood estimation from incomplete data via EM Algorithm[J]. Journal of the Royal Statistical Society,， 1977，39（1）：1-38.

　　[4] CHEN H,， BHANU B. Contour matching for 3D ear recognition[C]. In：Proceedings of IEEE Workshop on Application of Computer Vision,， 2005：123-128.

　　[5] YAN P， BOWYER K W,， Biometric recognition using three-dimensional ear shape[J]. IEEE Trans PAMI,， 2007，29（8）：1297-1308.

　　[6] ELAD M,， TAL A,， AR S. Content based retrieval of VRML objects-an iterative and interactive approach[C]. Proceedings of the Eurographics Workshop in Manchester， United Kingdom,， 2001：107-118.

　　[7] CHEN H,， BHANU B. Human ear recognition in 3D[J]. IEEE Transaction PAMI， 2007,，29（4）：718-737.

　　[8] CHOI S I,， PARK S Y， KIM J,， et al. Multi-view range image registration using CUDA[C]. Proceedings of the 23rd International Technical Conference on Circuits/Systems,， Computers and Communications， 2008：733-736.

　　[9] TAMAKI T,， ABE M,， RAYTCHEV B， et al. Softassign and EM-ICP on GPU[C]. Proceedings of the 2010 1st International Conference on Networking and Computing,， Washington DC,， USA： IEEE， 2010：179-183.

　　[10] NVIDIA. CUDA CUBLAS（CUDA Basic Linear Algebra Subprograms）Library[EB/OL].（2015-04-15）. http：//cudazone.nvidia.cn/cublas/.