摘  要： 提出了一種新型兩步式迭代最近點(diǎn)算法對(duì)三維人耳點(diǎn)云模型進(jìn)行配準(zhǔn)，該過(guò)程主要分為兩步完成：（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)過(guò)程中局部對(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ù)存在容易被偽造、被盜取以及容易遺失等問(wèn)題，暴露出越來(lái)越多的缺陷。它們已經(jīng)不能滿(mǎn)足人們對(duì)快速、便捷、有效的身份識(shí)別技術(shù)的需求。在此情況下，生物特征識(shí)別技術(shù)應(yīng)時(shí)而生。人耳識(shí)別是以人耳作為識(shí)別媒介來(lái)進(jìn)行身份的鑒別，是一種很有發(fā)展?jié)摿Φ纳锾卣髯R(shí)別技術(shù)，受到了國(guó)內(nèi)外眾多研究機(jī)構(gòu)的廣泛關(guān)注。研究指出，沒(méi)有任何兩個(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ā)展起來(lái)。三維人耳模型不但能夠很好的反應(yīng)人耳的輪廓信息，而且能夠很好地描述人耳的結(jié)構(gòu)和姿態(tài)信息。采用三維人耳數(shù)據(jù)進(jìn)行識(shí)別能有效解決姿態(tài)變換、陰影和光照條件改變等問(wèn)題對(duì)識(shí)別率的影響，因此更適合采用三維的方式來(lái)進(jìn)行采集和識(shí)別。

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

1 相關(guān)工作

　　迭代最近點(diǎn)（Iterative Closest Points，ICP）算法[1]是目前最常用的三維數(shù)據(jù)配準(zhǔn)算法，通過(guò)迭代最小化兩待配準(zhǔn)點(diǎn)云上對(duì)應(yīng)點(diǎn)間的距離誤差，獲得最佳的旋轉(zhuǎn)矩陣和平移矩陣，實(shí)現(xiàn)精確配準(zhǔn)。迭代最近點(diǎn)算法能夠滿(mǎ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]通過(guò)主成分分析（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)合并算法的效率已無(wú)法滿(mǎn)足實(shí)時(shí)性的需求。圖形處理單元GPU進(jìn)行并行計(jì)算，由多個(gè)流處理器分別進(jìn)行數(shù)值運(yùn)算，實(shí)現(xiàn)任務(wù)級(jí)和數(shù)據(jù)級(jí)的并行，能夠很好地解決上述問(wèn)題。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ì)算的部分，高度線(xiàn)程化的并行處理任務(wù)則由CPU和GPU共同完成，大大提高了程序的運(yùn)行效率和數(shù)據(jù)的處理速度，使由于數(shù)據(jù)規(guī)模較大、精度要求較高造成的配準(zhǔn)及合并效率降低等問(wè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)重的大小來(lái)表示配準(zhǔn)概率。通過(guò)求解模型的變換矩陣R與t，更改人耳點(diǎn)云模型Y的位置，直到點(diǎn)云模型間誤差函數(shù)E最小。

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

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

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

　　（6）若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)鍵問(wèn)題是將運(yùn)算過(guò)程分為向量與矩陣的運(yùn)算和矩陣內(nèi)元素間的運(yùn)算兩種，利用CUBLAS（CUDA Basic Linear Algebra Subprograms）[10]對(duì)向量與矩陣間的運(yùn)算進(jìn)行加速，編寫(xiě)CUDA kernel函數(shù)對(duì)矩陣元素間的運(yùn)算進(jìn)行加速[9]。具體步驟如下：

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

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

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

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

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

　　（9）若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，通過(guò)求解模型的變換矩陣R與t，更改模型點(diǎn)云Y的位置，直到點(diǎn)云模型間誤差函數(shù)E最小。

　　ICP算法的主要目的是求解兩個(gè)點(diǎn)云模型之間的空間變換，通過(guò)這個(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 E5-2609@2.40 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ù)采集

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

　　提取到人耳數(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)過(guò)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)精度。由圖可見(jià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/.