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

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

0 引言

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

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

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

1 相關(guān)工作

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

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

　　根據(jù)上述學(xué)者們的研究，本文提出了一種兩步式迭代最近點(diǎn)算法對(duì)三維人耳點(diǎn)云模型進(jìn)行配準(zhǔn),。首先采用基于CUDA加速的EM-ICP算法作為ICP算法的初始配準(zhǔn),，使人耳點(diǎn)云數(shù)據(jù)大致調(diào)整為同一姿態(tài),，然后基于該算法提供的初始變化采用ICP算法對(duì)三維人耳點(diǎn)云數(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)提供一個(gè)理想的初始變換。本文采用基于CUDA加速的EM-ICP算法對(duì)三維人耳模型進(jìn)行初始變換,，EM-ICP算法不需要建立初始對(duì)應(yīng)關(guān)系,，以權(quán)重表示兩點(diǎn)間的配準(zhǔn)概率，迭代運(yùn)算優(yōu)化配準(zhǔn)概率,，最終實(shí)現(xiàn)點(diǎn)云配準(zhǔn),。

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

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

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

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

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

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

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

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

　?。?）計(jì)算模型X,、Y對(duì)應(yīng)點(diǎn)之間的距離dij；

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

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

　　（8）更新控制參數(shù),；

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

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

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

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

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

　?。?）點(diǎn)云模型X與模型Y初始對(duì)齊；

　?。?）找到點(diǎn)云Y中距離點(diǎn)云X中xi最近的點(diǎn)yi,；

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

　　實(shí)驗(yàn)所用三維掃描儀的分辨率為640×480,，幀頻為24 f/s。實(shí)驗(yàn)程序運(yùn)行硬件配置為：Intel Xeon [email protected] GHz處理器,，16 GB內(nèi)存,，NVIDIA Quadro 2000顯卡，192個(gè)CUDA核心,，1 GB GDDR5顯存容量,，計(jì)算能力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í)驗(yàn)中將使用提取得到的三個(gè)人耳數(shù)據(jù),，如圖1所示，提取得到的人耳數(shù)據(jù),，方向各不相同,，分別為其編號(hào)為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)模型,，對(duì)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)模型,，對(duì)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)時(shí)間

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

參考文獻(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/.