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

　　關鍵詞: 耳廓匹配；樹匹配；相似測度

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

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

　　1 算法基礎

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

　　1.1 提取關鍵點及特征

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

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

　　1.2 兩耳廓關鍵點集間的映射

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

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

　　2 MST的相似測度

　　對于已經確定了對應關系的兩只待匹配耳廓，將已匹配關鍵點分別投影到2D平面上，對其進行Delaunay三角剖分后，再把剖分結果投影回三維空間，得到一張三維網格圖。然后對剖分圖進行MST計算，不同耳廓和同一耳廓的不同掃描數據樹的結構如圖1所示。

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

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

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

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

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

　　其中，εpi和εgi分別表示兩棵樹中第i條對應邊的邊長，me表示邊的數量。

　　在構造MST之前已經計算出耳廓上各關鍵點的特征，用對應特征之間的RMS距離作為特征誤差計算:

　　2.2 整體相似測度

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

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

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

　　3 實驗結果及分析

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

　　3.1 匹配精度

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

　　3.2 時間復雜度

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

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

　　參考文獻

　　[1] 王曉云.基于代數方法的人耳識別研究[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.