摘 要: 將樹匹配引入身份識(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算法生成最小生成樹,，計(jì)算兩只耳廓匹配產(chǎn)生的3個(gè)相似度測(cè)量值;最后經(jīng)過置信加權(quán)求和,，求出兩只耳廓之間的整體相似度，進(jìn)而完成耳廓匹配,。
關(guān)鍵詞: 耳廓匹配,；樹匹配；相似測(cè)度
隨著科學(xué)技術(shù)的不斷發(fā)展,，基于身份證和密碼的傳統(tǒng)身份鑒別技術(shù)暴露出越來越多的缺陷,，已經(jīng)不能滿足人們對(duì)快速、便捷,、有效的身份識(shí)別技術(shù)的需求,，在此情況下，基于生物特征的身份識(shí)別技術(shù)應(yīng)運(yùn)而生,。生物特征識(shí)別是利用人類特有的生理或行為特征進(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]通過測(cè)量圖的相似性來匹配兩張臉；參考文獻(xiàn)[7]基于二分圖來匹配三維耳廓形狀特征,。
1 算法基礎(chǔ)
針對(duì)兩只待匹配耳廓,，首先選取分布在三維空間中的若干關(guān)鍵點(diǎn)并提取附屬在關(guān)鍵點(diǎn)上的特征向量，以此來建立特征描述,。
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ā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ù)庫中的測(cè)試耳廓g,，根據(jù)兩耳廓上各關(guān)鍵點(diǎn)的局部形狀特征計(jì)算兩個(gè)特征的相似度，從而找到特征之間的對(duì)應(yīng)關(guān)系,。特征之間的相似度由兩個(gè)特征之間的均方根距離RMS來計(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ù)樹的結(jié)構(gòu)如圖1所示,。
圖1中每一列為同一耳廓的不同掃描數(shù)據(jù)，每一行為不同的耳廓數(shù)據(jù),，節(jié)點(diǎn)為關(guān)鍵點(diǎn),，線條為MST。通過比較可知,，不同的耳廓上樹的結(jié)構(gòu)存在明顯的差異,；同一耳廓的樹的結(jié)構(gòu)大致相同，具有很高的重復(fù)率。
2.1 衡量?jī)啥娜齻€(gè)相似測(cè)度
已經(jīng)確定了兩只待匹配耳廓關(guān)鍵點(diǎn)之間的對(duì)應(yīng)關(guān)系,，將樹節(jié)點(diǎn)之間的平均測(cè)地距離作為點(diǎn)誤差:
其中,(xpi,ypi,zpi)和(xgi,ygi,zgi)分別表示兩棵樹中第i個(gè)節(jié)點(diǎn)的坐標(biāo)值,，mp表示已匹配樹節(jié)點(diǎn)數(shù)量。
搜索兩棵最小生成樹,，分別記錄每條邊的邊長(zhǎng)及組成邊的節(jié)點(diǎn),，形成邊表。比較兩張邊表,，計(jì)算兩棵樹對(duì)應(yīng)邊之間的誤差:
其中,，εpi和εgi分別表示兩棵樹中第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è)試庫中所有耳廓進(jìn)行匹配就會(huì)得到3組相似測(cè)度，用min-max準(zhǔn)則將3個(gè)向量規(guī)范化到0~1之間后,，模型耳廓和測(cè)試耳廓之間的整體相似度可以用置信加權(quán)和來表示：
S=Kp×Pd+Ke×Ed+Kf×Fd (5)
其中,，Kp、Ke,、Kf分別表示3個(gè)相似測(cè)度的置信度[6],。最后得到的S向量包含N個(gè)元素，分別表示模型耳廓與測(cè)試庫中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),，就說明匹配正確，正確匹配點(diǎn)對(duì)數(shù)與圖節(jié)點(diǎn)總數(shù)量的比值為匹配精度,。隨著圖節(jié)點(diǎn)數(shù)量的增加,，對(duì)已有數(shù)據(jù)庫中所有耳廓的不同掃描數(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ù)庫中所有個(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í)間最少且變化不大?？梢?，本文算法的時(shí)間復(fù)雜度更低、匹配效率更高,。
本文采用基于最小生成樹相似測(cè)度的耳廓匹配方法,，把樹匹配問題應(yīng)用于解決耳廓識(shí)別問題，獲得了較好的實(shí)驗(yàn)效果,，顯然,，本文選取耳廓上一定數(shù)量的關(guān)鍵點(diǎn)進(jìn)行匹配,避免了原數(shù)據(jù)中近10萬節(jié)點(diǎn)反復(fù)迭代計(jì)算的過程，計(jì)算復(fù)雜度大大降低,，匹配精度高,。耳廓具有豐富的特征結(jié)構(gòu)，僅僅考慮局部特征會(huì)造成不同的凸起之間,、凹陷之間產(chǎn)生錯(cuò)誤匹配,，下一步考慮將局部匹配與全局匹配相結(jié)合，進(jìn)一步提高匹配的精度,。
參考文獻(xiàn)
[1] 王曉云.基于代數(shù)方法的人耳識(shí)別研究[D].沈陽:沈陽工業(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.