摘   要: 將樹匹配引入身份識別,，將每只耳廓表示為一棵最小生成樹，通過兩棵樹的相似測度衡量兩只耳廓的相似度,，以完成耳廓匹配,。首先從耳廓點云數(shù)據(jù)中選取一定數(shù)量的關(guān)鍵點;然后分別對兩只耳廓的關(guān)鍵點集采用Kruskal算法生成最小生成樹，計算兩只耳廓匹配產(chǎn)生的3個相似度測量值;最后經(jīng)過置信加權(quán)求和,，求出兩只耳廓之間的整體相似度,，進而完成耳廓匹配。

　　關(guān)鍵詞: 耳廓匹配,；樹匹配,；相似測度

　　隨著科學技術(shù)的不斷發(fā)展，基于身份證和密碼的傳統(tǒng)身份鑒別技術(shù)暴露出越來越多的缺陷,，已經(jīng)不能滿足人們對快速,、便捷,、有效的身份識別技術(shù)的需求,，在此情況下，基于生物特征的身份識別技術(shù)應(yīng)運而生,。生物特征識別是利用人類特有的生理或行為特征進行個人身份識別的技術(shù)[1],，它提供了一種高穩(wěn)定性、可靠性的身份鑒別途徑,。而耳廓憑借其特殊的生理位置和結(jié)構(gòu)特征,，已經(jīng)成為生物特征識別領(lǐng)域的后起之秀。與指紋識別,、人臉識別,、虹膜識別等方法相比，耳廓識別不受化妝和表情變化的影響,，具有更高的唯一性,、穩(wěn)定性和健壯性。耳廓識別在公共安全,、信息安全等領(lǐng)域具有潛在的應(yīng)用前景,。

　　根據(jù)輸入數(shù)據(jù)的不同，可以將耳廓特征識別方法分為基于二維圖像的識別和基于三維點云的識別,，相比較而言,，三維耳廓數(shù)據(jù)將提供更多的細節(jié)信息，能夠在不同的光照和姿態(tài)變化條件下取得較好的識別效果,。最初,，基于三維耳廓點云的耳廓識別算法大多采用ICP算法，參考文獻[2]用經(jīng)典的ICP算法配準三維圖形，參考文獻[3]用耳廓/外耳廓表示法進行人耳曲面匹配,，但基于ICP算法的識別算法復(fù)雜度很高,。參考文獻[4]基于直方圖的形狀描述匹配骨架圖；參考文獻[5]基于圖的直方圖及路徑相似性進行圖匹配,；參考文獻[6]通過測量圖的相似性來匹配兩張臉,；參考文獻[7]基于二分圖來匹配三維耳廓形狀特征。

　　1 算法基礎(chǔ)

　　針對兩只待匹配耳廓,，首先選取分布在三維空間中的若干關(guān)鍵點并提取附屬在關(guān)鍵點上的特征向量,，以此來建立特征描述。

　　1.1 提取關(guān)鍵點及特征

　　在三維耳廓模型上隨機選取一點vi,，以vi為球心,、r為半徑做球， 記球內(nèi)所有點構(gòu)成的矩陣為Ri,， 其均值向量為m,、協(xié)方差矩陣為C。對C進行主成分分析得到特征向量和特征值矩陣,。將Ri中所有點分別投影到較大的兩個特征值對應(yīng)的特征向量上,，記兩個方向上投影的最大值和最小值之差分別為dx和dy，若d=|dx-dy|大于指定閾值,，則選vi為關(guān)鍵點,，記作kvi。重復(fù)該過程,，直到獲得指定的關(guān)鍵點數(shù)目,，記該耳廓的關(guān)鍵點集合為KV。大量實驗數(shù)據(jù)表明,當關(guān)鍵點數(shù)目n=200時,，實驗效果最佳,。

　　對于任意關(guān)鍵點kvi，本文基于參考文獻[8]方法對其鄰域內(nèi)的全部點進行曲面擬合,。首先在參數(shù)區(qū)域上沿u方向和v方向分別進行均勻采樣,，得到均勻分布的nu×nv個采樣點，記其深度集合{Zuv}組成的局部形狀特征為LSFi,，則定義在關(guān)鍵點集KV上的局部形狀特征集合為{LSFi},。為保證特征的計算效率及精度，本文對局部形狀特征進行必要的壓縮,，采用參考文獻[6]的方法將kvi上的nu×nv維局部形狀特征LSFi壓縮為11維,，同時保證壓縮后的精度保持在97.3%。

　　1.2 兩耳廓關(guān)鍵點集間的映射

　　針對模型耳廓p,，考察數(shù)據(jù)庫中的測試耳廓g,，根據(jù)兩耳廓上各關(guān)鍵點的局部形狀特征計算兩個特征的相似度,，從而找到特征之間的對應(yīng)關(guān)系。特征之間的相似度由兩個特征之間的均方根距離RMS來計算：

　　其中,，pi和gi分別表示模型耳廓和測試耳廓第i對關(guān)鍵點上特征向量的分量,。RMS距離值最小的一對特征建立對應(yīng)關(guān)系。

　　2 MST的相似測度

　　對于已經(jīng)確定了對應(yīng)關(guān)系的兩只待匹配耳廓,，將已匹配關(guān)鍵點分別投影到2D平面上,，對其進行Delaunay三角剖分后，再把剖分結(jié)果投影回三維空間,，得到一張三維網(wǎng)格圖,。然后對剖分圖進行MST計算，不同耳廓和同一耳廓的不同掃描數(shù)據(jù)樹的結(jié)構(gòu)如圖1所示,。

　　圖1中每一列為同一耳廓的不同掃描數(shù)據(jù),，每一行為不同的耳廓數(shù)據(jù)，節(jié)點為關(guān)鍵點,，線條為MST,。通過比較可知，不同的耳廓上樹的結(jié)構(gòu)存在明顯的差異,；同一耳廓的樹的結(jié)構(gòu)大致相同,，具有很高的重復(fù)率。

　　2.1 衡量兩耳廓的三個相似測度

　　已經(jīng)確定了兩只待匹配耳廓關(guān)鍵點之間的對應(yīng)關(guān)系,，將樹節(jié)點之間的平均測地距離作為點誤差:

　　其中,(xpi,ypi,zpi)和(xgi,ygi,zgi)分別表示兩棵樹中第i個節(jié)點的坐標值,，mp表示已匹配樹節(jié)點數(shù)量,。

　　搜索兩棵最小生成樹,，分別記錄每條邊的邊長及組成邊的節(jié)點，形成邊表,。比較兩張邊表,，計算兩棵樹對應(yīng)邊之間的誤差:

　　其中，εpi和εgi分別表示兩棵樹中第i條對應(yīng)邊的邊長,，me表示邊的數(shù)量,。

　　在構(gòu)造MST之前已經(jīng)計算出耳廓上各關(guān)鍵點的特征，用對應(yīng)特征之間的RMS距離作為特征誤差計算:

　　2.2 整體相似測度

　　以上描述了兩只耳廓匹配得到的3個相似測度Pd,、Ed,、Fd,將模型耳廓與測試庫中所有耳廓進行匹配就會得到3組相似測度，用min-max準則將3個向量規(guī)范化到0~1之間后,，模型耳廓和測試耳廓之間的整體相似度可以用置信加權(quán)和來表示：

　　S=Kp×Pd+Ke×Ed+Kf×Fd  (5)

　　其中,，Kp、Ke,、Kf分別表示3個相似測度的置信度[6],。最后得到的S向量包含N個元素，分別表示模型耳廓與測試庫中N個耳廓的匹配結(jié)果，即兩者的整體相似度,。取S值最小的測試耳廓作為最終判斷的依據(jù),。

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

　　本文實驗數(shù)據(jù)為利用VIVID910三維激光掃描儀自主采集的三維耳廓數(shù)據(jù)，其中每只耳廓獲得2~6個掃描數(shù)據(jù)不等,。本文自行實現(xiàn)了參考文獻[2]和參考文獻[7]所述算法,，并在同樣的數(shù)據(jù)集進行了匹配實驗。相關(guān)實驗結(jié)果比較分析如下,。

　　3.1 匹配精度

　　當對兩只耳廓進行匹配時,，RMS距離最小的一對特征之間將建立對應(yīng)關(guān)系,相應(yīng)的關(guān)鍵點對為匹配點對，若一對已匹配關(guān)鍵點對在空間內(nèi)的距離值在給定的閾值范圍內(nèi),，就說明匹配正確,，正確匹配點對數(shù)與圖節(jié)點總數(shù)量的比值為匹配精度。隨著圖節(jié)點數(shù)量的增加,，對已有數(shù)據(jù)庫中所有耳廓的不同掃描數(shù)據(jù)進行匹配實驗,，本文算法與參考文獻[2]、參考文獻[7]算法的平均匹配精度如圖2所示,。顯然,，本文算法的匹配精度最高且逐漸趨于穩(wěn)定。

　　3.2 時間復(fù)雜度

　　本文令關(guān)鍵點數(shù)目從100逐漸增加至200,，并對耳廓數(shù)據(jù)庫中所有個體的不同掃描數(shù)據(jù)進行匹配實驗,，參考文獻[2]、參考文獻[7]與本文算法平均匹配一對耳廓所用時間對比情況如圖3所示,。顯然,，隨著圖節(jié)點數(shù)的不斷增加，3種算法的匹配時間都有不同程度的增加,，其中參考文獻[2]算法所用時間變化尤為劇烈,，而本文算法所用時間最少且變化不大?？梢?，本文算法的時間復(fù)雜度更低、匹配效率更高,。

　　本文采用基于最小生成樹相似測度的耳廓匹配方法,，把樹匹配問題應(yīng)用于解決耳廓識別問題，獲得了較好的實驗效果,，顯然,，本文選取耳廓上一定數(shù)量的關(guān)鍵點進行匹配,避免了原數(shù)據(jù)中近10萬節(jié)點反復(fù)迭代計算的過程，計算復(fù)雜度大大降低,，匹配精度高,。耳廓具有豐富的特征結(jié)構(gòu),，僅僅考慮局部特征會造成不同的凸起之間、凹陷之間產(chǎn)生錯誤匹配,，下一步考慮將局部匹配與全局匹配相結(jié)合,，進一步提高匹配的精度。

　　參考文獻

　　[1] 王曉云.基于代數(shù)方法的人耳識別研究[D].沈陽:沈陽工業(yè)大學,2011.

　　[2] BESL P, NEIL B. A method for registration of 3D shapes[J].IEEE Transactions on Pattern AnalysisMachinInteligence,1992,14(2):239-256.

　　[3] Chen Hui, BHANU B. Human ear recognition in 3D[J].IEEE Transaction on Pattern Analysis and Machine Intelli-gence,2007,29(4):718-737.

　　[4] Tang Jin,Jiang Bo,Luo Bin.Shape description and skeleton-graph matching algorithm based on histogram[J]. Journal ofSouth China University of Technology,2010,38(7):27-32.

　　[5] Tang Jin, Jiang Bo, Luo Bin. Graph matching based on graph histogram and path similarity[J].Journal of Computer-Aided Design and Computer Graphics, 2011,23(9):1481-1489.

　　[6] BENNAMOUN M, OWENS R A. Keypoint detection and local feature matching for textured 3D face recognition[J]. International Journal of Computer Vision,2008,79(1):1-12.

　　[7] Sun Xiaopeng, Wang Xingyue, Wang Guan. 3D ear shapefeature optimal matching using bipartite graph[J]. Frontier and Future Development of Information Technology in Med-icine and Education,2013:3133-3138.

　　[8] D’ERICO J. Surface fitting using gridfit[EB/OL].MATLABCentral File Exchange Select,2006.