摘   要: 將樹(shù)匹配引入身份識(shí)別,，將每只耳廓表示為一棵最小生成樹(shù),，通過(guò)兩棵樹(shù)的相似測(cè)度衡量?jī)芍欢南嗨贫龋酝瓿?a class="innerlink" href="http://forexkbc.com/tags/耳廓匹配" title="耳廓匹配" target="_blank">耳廓匹配,。首先從耳廓點(diǎn)云數(shù)據(jù)中選取一定數(shù)量的關(guān)鍵點(diǎn);然后分別對(duì)兩只耳廓的關(guān)鍵點(diǎn)集采用Kruskal算法生成最小生成樹(shù),，計(jì)算兩只耳廓匹配產(chǎn)生的3個(gè)相似度測(cè)量值;最后經(jīng)過(guò)置信加權(quán)求和，求出兩只耳廓之間的整體相似度，進(jìn)而完成耳廓匹配,。

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

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

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

　　1 算法基礎(chǔ)

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

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

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

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

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

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

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

　　2 MST的相似測(cè)度

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

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

　　2.1 衡量?jī)啥娜齻€(gè)相似測(cè)度

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

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

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

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

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

　　2.2 整體相似測(cè)度

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

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

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

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

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

　　3.1 匹配精度

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

　　3.2 時(shí)間復(fù)雜度

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

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

　　參考文獻(xiàn)

　　[1] 王曉云.基于代數(shù)方法的人耳識(shí)別研究[D].沈陽(yáng):沈陽(yáng)工業(yè)大學(xué),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.