基于Sparse ICP的三維點(diǎn)云耳廓識(shí)別

王　森， 王　璐， 洪靖惠， 李思慧， 孫曉鵬,2

(1. 遼寧師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院計(jì)算機(jī)系統(tǒng)研究所，遼寧 大連 116081；2. 北京郵電大學(xué)智能通信軟件與多媒體北京市重點(diǎn)實(shí)驗(yàn)室，北京 100876)

基于Sparse ICP的三維點(diǎn)云耳廓識(shí)別

王森1， 王璐1， 洪靖惠1， 李思慧1， 孫曉鵬1,2

(1. 遼寧師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院計(jì)算機(jī)系統(tǒng)研究所，遼寧 大連 116081；2. 北京郵電大學(xué)智能通信軟件與多媒體北京市重點(diǎn)實(shí)驗(yàn)室，北京 100876)

提出一種新穎的三維耳廓識(shí)別方法，首先基于PCA和SVD分解對(duì)三維耳廓點(diǎn)云模型進(jìn)行歸一化預(yù)處理，以統(tǒng)一數(shù)據(jù)庫(kù)中所有耳廓點(diǎn)云模型的位置與姿態(tài)；然后基于 Iannarelli分類系統(tǒng)提取三維耳廓的4個(gè)局部特征區(qū)域，并利用Sparse ICP算法對(duì)局部特征區(qū)域進(jìn)行匹配；最后根據(jù)局部特征區(qū)域中對(duì)應(yīng)點(diǎn)間的距離判斷耳廓之間的差異測(cè)度，實(shí)現(xiàn)耳廓形狀識(shí)別。實(shí)驗(yàn)證明，本文算法與其他算法相比具有較高的識(shí)別精度和識(shí)別效率。

耳廓識(shí)別；PCA；Iannarelli；局部特征；Sparse ICP

生物特征識(shí)別技術(shù)有效地避免了傳統(tǒng)身份鑒別方式的不足之處，將人體所固有的生物特征數(shù)字化、隱性化，更具有普遍性、獨(dú)特性、永久性和易采集性。

耳廓識(shí)別技術(shù)是近幾年來新興的生物識(shí)別技術(shù)，主要利用人耳外形的溝壑曲折等三維形狀特征進(jìn)行識(shí)別，同手掌、指紋、虹膜、DNA等人類生物特征一樣，是永久性的生物標(biāo)識(shí)。耳廓的三維形狀特征不受發(fā)型、表情、胡須、化妝、眼鏡、膚色、光照等因素的影響[1]，且在7～70歲之間，人類耳廓的結(jié)構(gòu)和外形不會(huì)發(fā)生明顯改變；即便是雙胞胎的耳廓也存在可測(cè)量的差異[2]；因此與其他人類生物特征相比，耳廓的三維形狀特征具有高度的穩(wěn)定性和唯一性。

1　相關(guān)工作

根據(jù)不同輸入耳廓數(shù)據(jù)的類型，耳廓識(shí)別可以分為二維耳廓識(shí)別、三維耳廓識(shí)別兩種方式。與二維耳廓識(shí)別技術(shù)相比，三維耳廓姿態(tài)受光照等外界因素影響較小，具有顯著的健壯性優(yōu)勢(shì)。三維耳廓識(shí)別一般包括三個(gè)步驟：耳廓探測(cè)、特征提取以及特征匹配，其中特征提取、特征匹配是三維耳廓識(shí)別的核心問題。

1.1三維耳廓特征提取

耳廓由耳輪、對(duì)耳輪、耳舟、三角窩、耳屏、對(duì)耳屏、耳垂等部分構(gòu)成，具有顯著的起伏外形，具有獨(dú)特的三維形狀特征。2005年，Chen和Bhanu[3]提取三維耳廓模型中耳輪部位的點(diǎn)作為特征點(diǎn)，判斷耳輪部分對(duì)應(yīng)點(diǎn)之間的距離，實(shí)現(xiàn)了對(duì)耳廓的識(shí)別。2007年，Chen和Bhanu[4]引入表面的局部曲面片(local surface patch，LSP)方法提取耳廓特征，每個(gè)三維點(diǎn)上的 LSP由該點(diǎn)鄰域內(nèi)點(diǎn)集的中心點(diǎn)坐標(biāo)、該點(diǎn)形狀索引對(duì)應(yīng)的形狀類型、以及相應(yīng)的直方圖組成，通過比較兩個(gè)直方圖的差異測(cè)度判斷耳廓特征的相似性；由于待測(cè)耳廓之間所有特征點(diǎn)都要進(jìn)行比較，故識(shí)別效率較低。2009年，陳雷蕾等[5]采用兩種方式提取耳廓特征，第一種方法將耳廓的深度圖像與耳廓的曲率信息相結(jié)合，并利用主成分分析(principle component analysis，PCA)降維提取耳廓形狀特征，最后利用最近鄰分類完成耳廓的識(shí)別；第二種方法利用不變特征迭代最近點(diǎn)(iterative closest points using invariant features，ICPIF)算法[6]計(jì)算耳廓之間的匹配誤差，實(shí)現(xiàn)了較好的識(shí)別效果。2011年，Islam等[7]隨機(jī)采樣三維耳廓上的點(diǎn)，并對(duì)采樣點(diǎn)的鄰域進(jìn)行 PCA分析，將第一主軸和第二主軸的長(zhǎng)度之差大于指定閾值的點(diǎn)作為關(guān)鍵點(diǎn)，以關(guān)鍵點(diǎn)及其鄰域點(diǎn)集的擬合曲面作為特征曲面，實(shí)現(xiàn)了耳廓識(shí)別。

1.2迭代最近點(diǎn)算法

現(xiàn)有的三維耳廓識(shí)別大多基于迭代最近點(diǎn)(iterative closest point，ICP)算法對(duì)三維耳廓模型進(jìn)行匹配。ICP算法通過循環(huán)迭代、反復(fù)精細(xì)調(diào)整點(diǎn)云模型的位置及姿態(tài)、最小化總體配準(zhǔn)誤差，從而實(shí)現(xiàn)總體最佳匹配。針對(duì)ICP算法計(jì)算復(fù)雜度較高、需要初始對(duì)齊等不足，諸多改進(jìn)的 ICP算法相繼提出。

2002年Granger和Pennec[8]提出了EM-ICP算法，省去了初始對(duì)齊步驟，直接對(duì)變換較大的模型進(jìn)行配準(zhǔn)，解決ICP算法初始對(duì)齊的局限性。由于EM-ICP算法較為復(fù)雜，計(jì)算量較大，2010年Tamaki等[9]提出了基于GPU的EM-ICP算法并對(duì)其進(jìn)行加速；同時(shí)引入加權(quán)因子解決EM-ICP算法中的噪聲值和異常值等問題。2013年 Mohammadzade和Hatzinakos[10]提出新配準(zhǔn)方式：迭代最近法向量點(diǎn)(iterative closest normal point，ICNP)算法，其實(shí)質(zhì)是參考模型根據(jù)目標(biāo)模型點(diǎn)集特征的采樣，有效找出所有參考模型中具有相同特征的對(duì)應(yīng)點(diǎn)集，即最近法向量點(diǎn)(closest normal points，CNPs)，避免了一些剛性配準(zhǔn)算法只適用于幾乎不會(huì)發(fā)生變形的特定區(qū)域之間的配準(zhǔn)，對(duì)于表情變化區(qū)域，無法實(shí)現(xiàn)準(zhǔn)確的配準(zhǔn)。然而，利用ICNP算法得到的CNPs不能判斷模型間配準(zhǔn)質(zhì)量。同年Bouaziz等[11]提出了一種新的改進(jìn)方式——稀疏度迭代最近點(diǎn)(sparse iterative closest point，Sparse ICP)算法。利用lp范數(shù)取代歐式距離，優(yōu)化解決最小二乘法問題，降低了異常值和不完整數(shù)據(jù)對(duì)配準(zhǔn)的影響，并且采用拉格朗日方法、交換方向乘子法解決非凸性和非平滑性等問題，與啟發(fā)式方法調(diào)整模型間配準(zhǔn)相比，如丟棄比較遠(yuǎn)對(duì)應(yīng)對(duì)、除去幾何邊界上各點(diǎn)等，Sparse ICP算法省略人工交互干涉等繁瑣步驟，算法更加可靠。

2　三維耳廓點(diǎn)云預(yù)處理

由于三維耳廓數(shù)據(jù)集構(gòu)建時(shí)間跨距較大，不同的采集時(shí)間上獲取的同一耳廓數(shù)據(jù)將受到被采集耳廓與采集設(shè)備之間的距離、角度等因素的影響，因此首先需要對(duì)三維耳廓數(shù)據(jù)庫(kù)中的耳廓模型進(jìn)行歸一化預(yù)處理。

則，V的3個(gè)1階幾何矩和6個(gè)2階幾何矩分別為：

對(duì)于頂點(diǎn)集合V的任意頂點(diǎn)(xi, yi, zi)做如下變換：

設(shè)UΔUT=SVD(M)，即對(duì)協(xié)方差矩陣M進(jìn)行SVD分解[13]，其中U為矩陣M的特征向量矩陣，對(duì)應(yīng)耳廓模型V的3個(gè)主軸，Δ為矩陣M的特征值矩陣，對(duì)耳廓模型V的任意頂點(diǎn)(xi, yi, zi)如下變換：

從而使耳廓模型的第一主軸與y軸對(duì)齊，第二主軸與x軸對(duì)齊，第三主軸與z軸對(duì)齊，實(shí)現(xiàn)數(shù)據(jù)庫(kù)中所有耳廓點(diǎn)云模型均歸一化到基本一致的姿態(tài)和位置，如圖1所示。

圖1　三維耳廓點(diǎn)云模型歸一化前后對(duì)比效果圖

3　關(guān)鍵點(diǎn)提取

2010年，Abaza和Ross[14]基于Iannarelli分類系統(tǒng)[15]測(cè)量左、右耳廓的幾何信息，通過對(duì)比左、右耳廓之間幾何信息的差異度對(duì)耳廓進(jìn)行識(shí)別。圖2所示為一個(gè)完整的Iannarelli分類系統(tǒng)，該方法基于耳廓的解剖學(xué)特征，計(jì)算耳廓重要組成部分的相似度，然而在二維圖像上各部分尺寸均需要手工測(cè)量，無法精確定位。

圖2　Iannarelli分類系統(tǒng)

本文基于二維圖像空間的 Iannarelli分類系統(tǒng)實(shí)現(xiàn)三維空間的耳廓形狀特征提取與識(shí)別。首先將耳廓模型V的第一主軸與第二主軸作為一對(duì)方向，同時(shí)將這兩個(gè)主軸的對(duì)角作為另外一對(duì)方向，然后沿著這4個(gè)方向做法平面與耳廓模型求交，最后提取耳廓中4個(gè)局部特征區(qū)域?qū)ΧM(jìn)行匹配，這4個(gè)局部特征區(qū)域包含了Iannarelli分類系統(tǒng)中12個(gè)重要幾何特征(如圖3所示)。在人耳數(shù)據(jù)庫(kù)中，每個(gè)耳廓模型上都提取這樣4個(gè)局部特征區(qū)域，對(duì)不同的特征區(qū)域進(jìn)行標(biāo)號(hào)，不同耳廓點(diǎn)云數(shù)據(jù)模型中，具有相同標(biāo)號(hào)的局部特征區(qū)域進(jìn)行匹配，提高了耳廓模型匹配的精確度。

圖3　提取耳廓模型4個(gè)子區(qū)域

4　Sparse ICP算法

設(shè)兩個(gè)三維耳廓點(diǎn)云模型X和Y分別為參考模型和目標(biāo)模型，記 X和 Y間的對(duì)齊誤差向量為zi=Rxi+t?yi，則，記X和Y間的距離為其中并且并記模型間X和Y的誤差函數(shù)為對(duì)齊誤差向量的lp范數(shù)：

為了進(jìn)一步優(yōu)化配準(zhǔn)問題，在求解最小化誤差函數(shù)中，基于拉格朗日方法將對(duì)齊誤差向量的lp范數(shù)重新定義為：

步驟1. 參考模型X與目標(biāo)模型Y初始對(duì)齊，初始化拉格朗日乘λi、懲罰因子μ以及閾值；

步驟2. 對(duì)于X的任意點(diǎn)，計(jì)算Y上歐式距離該點(diǎn)最近的點(diǎn)，從而得到X和Y之間全部初始匹配點(diǎn)對(duì)；

步驟6. 若?(x,y)大于閾值τ，返回到步驟 2，否則迭代結(jié)束。

圖4為Sparse ICP算法流程，由于引入稀疏度對(duì)模型配準(zhǔn)優(yōu)化，并利用 lp范數(shù)取代歐式距離，最大化對(duì)應(yīng)點(diǎn)間距離為 0的數(shù)量，避免了局部對(duì)齊等問題發(fā)生。同時(shí)，算法采用拉格朗日方法對(duì)誤差函數(shù)重新定義，解決對(duì)齊方式造成的模型表面非凸性和非平滑性等問題，并利用交換方向乘子法將重新定義的誤差函數(shù)分成 3個(gè)簡(jiǎn)單的子問題，并通過收縮算子進(jìn)行求解，提高了算法的精度和穩(wěn)定性。

圖4　Sparse ICP算法流程

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

本文實(shí)驗(yàn)在UND三維耳廓數(shù)據(jù)庫(kù)上進(jìn)行，該數(shù)據(jù)庫(kù)包含來自415人的1 800幅三維耳廓[18]。本文基于Sparse ICP算法對(duì)相同耳廓的不同掃描數(shù)據(jù)以及不同耳廓的不同掃描數(shù)據(jù)進(jìn)行多組實(shí)驗(yàn)的匹配，其相關(guān)實(shí)驗(yàn)結(jié)果比較及分析如下。

5.1匹配精度

圖5為待測(cè)耳廓模型05129d002ear與數(shù)據(jù)庫(kù)中耳廓模型Sparse ICP算法匹配后計(jì)算的歐式距離平方和相似度分布，其中紅色的線表示使用完整耳廓模型進(jìn)行匹配后的結(jié)果，藍(lán)色的線表示使用提取的耳廓區(qū)域進(jìn)行匹配后的結(jié)果。從圖中可以看出，采用局部區(qū)域匹配的耳廓模型精度較高。

圖5　采用整個(gè)模型與耳廓局域特征區(qū)域的精度比較

同樣，以05129d002ear為待測(cè)耳廓模型，分別于數(shù)據(jù)庫(kù)中其他耳廓模型進(jìn)行匹配，計(jì)算模型之間匹配點(diǎn)對(duì)之間平均距離，即：

其中，n表示匹配點(diǎn)對(duì)的個(gè)數(shù)；MinDis表示匹配點(diǎn)對(duì)之間的距離；i表示匹配點(diǎn)對(duì)的序號(hào)；k表示區(qū)域的序號(hào)。顯然，DisAvg越小，兩個(gè)模型相似度越高；DisAvg越大，兩個(gè)模型相似度越低。平均每個(gè)局域的平均距離，即可得到耳廓模型之間的相似度(如表1所示)。顯然，Sparse ICP算法與ICP、ICNP算法相比，精度較高，且能夠有效區(qū)分相同耳廓不同數(shù)據(jù)的模型。

表1　耳廓間平均距離比較

采 用 累 積 匹 配 特 性 (cumulative match characteristics，CMC)曲線來評(píng)估算法的識(shí)別效率，其中CMC曲線的橫坐標(biāo)表示在耳廓匹配實(shí)驗(yàn)結(jié)果匹配最好的前k個(gè)的模型，縱坐標(biāo)表示為三維耳廓識(shí)別的正確率。圖6將Sparse ICP算法，ICP算法的 CMC曲線進(jìn)行對(duì)比。從該圖可以看出，Sparse ICP算法的識(shí)別率比 ICP算法的識(shí)別率高，其中rank-1達(dá)到了93.8%。

圖6　CMC曲線

采用接收器操作特性(receiver operating characteristic，ROC)曲線反映正確接受率(genuine acceptance rate，GAR)與錯(cuò)誤接受率(false acceptance rate，F(xiàn)AR)的相互關(guān)系，GAR表示正確的耳廓被視為正確的百分率，F(xiàn)AR表示錯(cuò)誤的耳廓被視為正確的百分率。圖7將Sparse ICP算法、ICP算法的ROC曲線進(jìn)行對(duì)比。從該圖可以看出，Sparse ICP算法的識(shí)別率比ICP算法的識(shí)別率高。

圖7　ROC曲線

5.2匹配時(shí)間

本實(shí)驗(yàn)基于2.40 GHz的Intel(R) Xeon(R) CPU，16.0 GB RAM，64位操作系統(tǒng)的計(jì)算環(huán)境中，對(duì)UND三維耳廓數(shù)據(jù)庫(kù)中的1 800個(gè)三維耳廓模型分別提取耳廓特征區(qū)域，并對(duì)比了利用完整耳廓模型進(jìn)行Sparse ICP、ICP、ICNP算法的匹配情況，相應(yīng)的匹配用時(shí)對(duì)比如表2所示?？梢钥闯?，基于耳廓局部特征區(qū)域的匹配用時(shí)顯然小于基于完整耳廓模型的匹配用時(shí)，并且與ICP和ICNP算法相比，Sparse ICP算法時(shí)間消耗較少。

表2　匹配時(shí)間比較(s)

6　結(jié)　論

隨著三維模型掃描技術(shù)的成熟發(fā)展，三維模型的規(guī)?？焖僭鲩L(zhǎng)，三維形狀特征具有顯著的客觀性、唯一性，且抗干擾能力強(qiáng)，能夠避免二維圖像中光照、姿態(tài)等因素的影響。三維耳廓模型識(shí)別技術(shù)，受到越來越多研究者的關(guān)注，成為一個(gè)新的研究熱點(diǎn)。

本文首先采用 PCA算法對(duì)模型進(jìn)行歸一化，將所有模型姿態(tài)和位置調(diào)整一致，然后根據(jù)Iannarelli系統(tǒng)提取耳廓模型上的 4個(gè)局部特征區(qū)域，最后采用Sparse ICP算法對(duì)三維點(diǎn)云耳廓子區(qū)域進(jìn)行匹配。實(shí)驗(yàn)證明，本文算法與其他算法相比有很高的識(shí)別精度和效率。

[1] Prakash S, Gupta P. An efficient ear recognition technique invariant to illumination and pose [J]. Telecommunication Systems, 2013, 52(3): 1435-1448.

[2] Iannarelli A. Ear identification, forensic identification series [M]. California: Fremont Paramount Publishing Company, 1989: 108-119.

[3] Chen H, Bhanu B. Contour matching for 3D ear recognition [C]//Proceedings of Seventh IEEE Workshops on Application of Computer Vision, WACV/MOTIONS 2005, Breckenridge, 2005: 123-128.

[4] Chen H, Bhanu B. Human ear recognition in 3D [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(4): 718-737.

[5] 陳雷蕾, 王斌, 張立明. 快速三維人耳提取與識(shí)別[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2009, 21(10): 1438-1445.

[6] Sharp G C, Lee S W, Wehe D K. ICP registration using invariant features [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(1): 90-102.

[7] Islam S M S, Davies R, Bennamoun M, et al. Efficient detection and recognition of 3D ears [J]. International Journal of Computer Vision, 2011, 95(1): 52-73.

[8] 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 (ECCV) 2002, Copenhagen, 2002: 418-432.

[9] Tamaki T, Abe M, Raytchev B, et al. Softassign and EM-ICP on GPU [C]//Proceedings of the First International Conference on Networking and Computing (ICNC) 2010, Higashi Hiroshima, 2010: 179-183.

[10] Mohammadzade H, Hatzinakos D. Iterative closest normal point for 3D faces recognition [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(2): 381-397.

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

[12] 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.

[13] Arun K S, Huang T S, Blostein S D. Least-squares fitting of two 3-D point sets [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1987, 9(5): 698-700.

[14] Abaza A, Ross A. Towards understanding the symmetry of human ears: a biometric perspective [C]//Proceedings of 2010 4th IEEE International Conference on Biometrics: Theory Applications and Systems (BTAS), Washington DC, 2010: 1-7.

[15] Prakash S, Gupta P. An efficient ear recognition technique invariant to illumination and pose [J]. Telecommunication Systems, 2013, 52(3): 1435-1448.

[16] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers [J]. Foundations and Trends in Machine Learning, 2010, 3(1): 1-122.

[17] Parikh N, Boyd S. Proximal algorithms [J]. Foundations and Trends in Optimization, 2013, 1(3): 123-231.

[18] Yan Ping, Bowyer K W, Biometric recognition using three-dimensional ear shape [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(8): 1297-1308.

3D Ear Point Clouds Recognition Using Sparse ICP

Wang Sen1,Wang Lu1,Hong Jinghui1,Li Sihui1,Sun Xiaopeng1,2
(1. Computer System Institute, Department of Computer and Information Technology, Liaoning Normal University, Dalian Liaoning 116081, China; 2. Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications, Beijing 100876, China)

A novel 3D ear recognition method is proposed in this paper. Firstly, using the PCA and SVD algorithm to normalize 3D ear point clouds model, and adjust the position and posture of all ear point cloud models in the database. Then, based on the Iannarelli system, we extract four local feature regions of 3D ear model, and match them with Sparse ICP algorithm. Finally we match 3D ear models according to the distance between their corresponding points. The experiments show that our algorithm has higher recognition accuracy and efficiency compared with other algorithms.

ear recognition; PCA; Iannarelli; local feature; Sparse ICP

TP 391

A

2095-302X(2015)06-0862-06

2015-06-24；定稿日期：2015-07-08

國(guó)家自然科學(xué)基金資助項(xiàng)目(60873110，61170143，61472170)，智能通信軟件與多媒體北京市重點(diǎn)實(shí)驗(yàn)室開發(fā)課題(ITSM201301)

王森(1992–)，女，遼寧大連人，碩士研究生。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。E-mail：cadcg2008@gmail.com

孫曉鵬(1968–)，男，遼寧大連人，教授，博士。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。E-mail：xpsun2008@gmail.com