基于兩步式迭代最近點(diǎn)的三維人耳配準(zhǔn)算法

蓋宇

（大連醫(yī)科大學(xué)　中山學(xué)院　計(jì)算機(jī)與信息工程學(xué)院，遼寧　大連　116085）

基于兩步式迭代最近點(diǎn)的三維人耳配準(zhǔn)算法

蓋宇

（大連醫(yī)科大學(xué)中山學(xué)院計(jì)算機(jī)與信息工程學(xué)院，遼寧大連116085）

提出了一種新型兩步式迭代最近點(diǎn)算法對(duì)三維人耳點(diǎn)云模型進(jìn)行配準(zhǔn)，該過程主要分為兩步完成：（1）采用基于CUDA并行加速的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)速度。

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ù)，受到了國內(nèi)外眾多研究機(jī)構(gòu)的廣泛關(guān)注。研究指出，沒有任何兩個(gè)人（即使是雙胞胎）的耳朵是完全一樣的，并且在8～70歲之間都不會(huì)有顯著的變化，可以作為個(gè)體生物識(shí)別的依據(jù)。人耳形狀特征很豐富，其表面具有大量的溝和脊，不受胡須、化妝品、年齡、表情等影響，具有更高的穩(wěn)定性、唯一性和健壯性，為人耳識(shí)別技術(shù)提供了理論研究價(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)概率。

已知σ、d，計(jì)算

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

（1）對(duì)σp，σimf，，σf控制參數(shù)初始化；

（2）根據(jù)兩個(gè)點(diǎn)云模型X和Y上的點(diǎn)，計(jì)算αij；

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

（5）更新控制參數(shù)σp=σp×σf；

（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í)間很長，對(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ù)初始化；

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

（4）CUBLAS sgemv函數(shù)求解A的每行元素之和，A1→C，C=（C1，…，Cny）T；利用 CUBLAS saxpy函數(shù)計(jì)算

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

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

（8）更新控制參數(shù)σp=σp×σf；

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

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

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

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

（4）更新模型Y的位置X=RX+t；

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

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

實(shí)驗(yàn)所用三維掃描儀的分辨率為640×480，幀頻為24f/s。實(shí)驗(yàn)程序運(yùn)行硬件配置為：Intel XeonE5-2609@2.40GHz處理器，16GB內(nèi)存，NVIDIAQuadro 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。

圖1　最終得到的人耳數(shù)據(jù)

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　不同角度的人耳模型進(jìn)行配準(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)一致的位置。

圖2　對(duì)比配準(zhǔn)后的人耳數(shù)據(jù)與待配準(zhǔn)數(shù)據(jù)

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)于其他方式。

圖3　配準(zhǔn)精度對(duì)比

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í)間消耗差距不大。

表2　配準(zhǔn)時(shí)間對(duì)比（單位：s）

［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 threedimensional 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 InternationalTechnicalConferenceonCircuits/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/.（收稿日期：2015-04-15）

（1）：1-6.

［8］TEWARINC，KODUVELYHM，GUHAS，etal.MapReduce implementation of variational bayesian probabilistic matrix factorization algorithm［C］.Big Data，2013 IEEE International Conference on.IEEE，2013：145-152.

A new two-step iterative closest points algorithm for 3D human ear registration

Gai Yu

（College of Computer and Information Engineering，Zhongshan College of Dalian Medical University，Dalian 116085，China）

This paper presents a new two-step iterative closest points algorithm for 3D human ear point cloud model registration.The process is mainly divided into two steps.Step 1，we adapt EM-ICP algorithm based on CUDA parallel mechanism to make the initial registration in order to make the ear point cloud data in the same direction to provied a favorable inital transform for following step.Step2，we use the ICP algorithm for accurate registration of 3D ear data.The algorithm is able to avoid local alignment and other problems in the ICP algorithm process.The experimental results show that，the 3D ear data registration with a good effect and good speed.

EM-ICP；ICP；ear；point clouds registration；CUDA

TP301

A

1674-7720（2015）15-0022-04

蓋宇.基于兩步式迭代最近點(diǎn)的三維人耳配準(zhǔn)算法［J］.微型機(jī)與應(yīng)用，2015，34（15）：22-25.

蓋宇（1987-），男，研究生，主要研究方向：計(jì)算機(jī)圖形學(xué)。

2015-03-11）