一種基于k鄰域算法的指紋匹配算法研究

陳志楚

（湖北汽車工業(yè)學(xué)院 電氣與信息工程學(xué)院，湖北 十堰 442001）

一種基于k鄰域算法的指紋匹配算法研究

陳志楚

（湖北汽車工業(yè)學(xué)院 電氣與信息工程學(xué)院，湖北 十堰 442001）

由于指紋的唯一性，指紋識別已成為目前最方便、安全的個(gè)人身份鑒定技術(shù)之一.而在指紋識別中，指紋匹配的效果最終決定了指紋識別的鑒別率.本文提出了一種基于鄰域算法的指紋匹配算法.實(shí)驗(yàn)證明，該方法有效實(shí)用.

k鄰域；指紋識別；指紋匹配

1 引言

指紋匹配過程是將兩個(gè)指紋進(jìn)行比較，返回相似度（不失一般性相似度范圍設(shè)為0到1）或者二值的斷言（匹配/不匹配）.只有極少數(shù)匹配算法是直接在灰度圖像進(jìn)行運(yùn)算，大多數(shù)算法需要通過特征提出，然后比較特征點(diǎn).

指紋匹配是一個(gè)非常困難的問題，主要是由于相同指紋采集的不同圖像存在大量變化的因素如圖1.比如指紋主要成分在圖像中的位置，指紋的旋轉(zhuǎn)，手指移動造成的部分重疊，擠壓造成的非線性形變，按捺力度和指紋表面的潔凈度，傳感系統(tǒng)的噪聲以及特征提取過程中產(chǎn)生的錯誤等等都會對指紋匹配造成影響，降低匹配的準(zhǔn)確度.

圖1 同一指紋的不同采集圖像

目前指紋匹配算法可以大致分為三類：

（1）基于相關(guān)度的方法，兩幅指紋圖像部分重疊，則可以通過旋轉(zhuǎn)和平移可以排成一列，計(jì)算對應(yīng)的像素點(diǎn)相關(guān)度即可.

（2）基于細(xì)節(jié)特征匹配的方法，這是使用最為廣泛的匹配技術(shù)，特征點(diǎn)從兩幅指紋圖像中提取出來，存儲成二維平面上一系列的點(diǎn).基于細(xì)節(jié)特征匹配算法必須找到使輸入指紋和比對模板之間特征數(shù)量最多的排列，使兩組特征向量盡可能的對齊.

（3）基于非細(xì)節(jié)特征點(diǎn)的匹配方法，在低質(zhì)量的指紋中提取準(zhǔn)確的細(xì)節(jié)特征信息十分困難，但是其他的一些脊線模式的特征信息則相對容易檢測，比如局部的方向，脊線的頻率，脊線的形狀以及紋理信息，但是這些信息的特性性和延續(xù)性通常較低.利用這些信息也可以進(jìn)行匹配.

基于特征點(diǎn)的匹配是使用最為廣泛和知名的指紋匹配方法，該類方法在全世界作為嚴(yán)格的法醫(yī)鑒定和法律上指紋證據(jù)鑒定的方法.而基于特征點(diǎn)的匹配目前存在H o u g h變換法、松弛法、能量最小法等很多方法.但基于實(shí)際應(yīng)用場合多采用單片機(jī)或者D S P類計(jì)算能力有限的終端設(shè)備，如何找到一種運(yùn)算相對簡單、效果較好的匹配方法是一個(gè)迫切要解決的問題.下面將介紹一種基于鄰域搜索的匹配方法.

2 特征向量匹配過程建模

設(shè)T和I分別代表模板和輸入的指紋.其元素為指紋特征向量，通常使用的特征向量是三元素向量（x,y,θ)，x，y代表特征點(diǎn)的位置，θ代表特征點(diǎn)的方向.

式中，m和n分別代表模板和輸入指紋的特征數(shù).當(dāng)輸入特征I中m'j和模板T中m'j的空間距離小于給定的容忍度r0和方向差小于給定的角度θ0時(shí)，認(rèn)為兩個(gè)特征向量匹配，公式表示如下：

公式中取|θ'j-θi|和360°-|θ'j-θi|的最小值是因?yàn)榻嵌仁侵芷谛缘?，比?58°和2°只差了4°，而不是356°.

比較時(shí)需要將兩個(gè)指紋旋轉(zhuǎn)一定的角度對齊，使?jié)M足上式的特征向量的點(diǎn)的對數(shù)最多.要將兩個(gè)指紋最大限度的對齊需要進(jìn)行位移，旋轉(zhuǎn)等操作，定義操作m a p()，設(shè)I中的向量為m'j，變換為向量為m"j，位移為[△x,△y],旋轉(zhuǎn)角度為θ，則有一下對齊變換：

定義特征點(diǎn)匹配函數(shù)m m()當(dāng)s d(m"j,mi)≤r0且d d(m"j,mj)≤θ0函數(shù)為1，認(rèn)為兩特征對齊，否則取0：

則最終的匹配過程可以描述為一下公式：

其中p(i)是決定I和T之間匹配對的未知函數(shù)，特別的，每個(gè)特征在另一個(gè)指紋中有特征點(diǎn)可以對應(yīng)，或者沒有任何點(diǎn)與之對應(yīng)：

（1）P(i)=j，表示T中的mi與I中的m'j對應(yīng)；

（2）P(i)=N u l l表明T中的mi與I中的任何特征向量均不對應(yīng)；

（3）如果p(i)≠j,坌i=1…m，表示I中特征向量m'j與T中任何向量均不對應(yīng);

（4）坌i=1…m,k=1…m,i≠k圯p(i)≠P(k)或者P(i)=P(k) =n u l l表示對I中的每個(gè)特征向量，在T中最多只有一個(gè)特征向量與之對應(yīng).

為了實(shí)現(xiàn)最優(yōu)匹配，需要一個(gè)復(fù)雜的表，事實(shí)上當(dāng)I中的一個(gè)特征向量與T中的某特征向量是在一個(gè)超球面中匹配的，最匹配不代表示最優(yōu)匹配，而最優(yōu)的變換是使匹配的特征向量數(shù)最多，如圖2.

圖2 非最大化匹配

圖2中m1和m"2匹配，他們是最近的一對點(diǎn)，但是此時(shí)m"1和m2不匹配，為了得到最大化的匹配對數(shù)，我們使m"1和m"2對應(yīng)，這樣m1和m2也可以匹配上.

圖3 匹配示意圖(Kryszczuk,Drygajlo,and Morier,2004)

實(shí)際上P的確定即參數(shù)△x,△y,θ的確定是非常復(fù)雜的，使用暴力方法即計(jì)算所有的特征點(diǎn)的匹配度來確定變換方式是不可取的，這樣當(dāng)特征點(diǎn)的數(shù)目增多時(shí)會造成指數(shù)爆炸.

3 基于K鄰域最近特征向量相似的特征點(diǎn)匹配算法

其中k為匹配點(diǎn)對數(shù)，n和m分別為輸入指紋和模板的特征向量個(gè)數(shù)

具體的步驟如下：

（1）尋找每個(gè)有效特征點(diǎn)最近的3個(gè)特征點(diǎn).

（2）由近到遠(yuǎn)計(jì)算每個(gè)特征點(diǎn)的三值向量，歐拉距離d，向量方向與中心特征點(diǎn)方向的偏移b e t a，兩特征點(diǎn)方向偏移g a m a.

（3）尋找匹配的三星形線，即星形線線段長度和線段之間的夾角小于設(shè)定的容忍度.

（4）得到變換參數(shù)組，變換參數(shù)d t h e t a為匹配的三星形線中最短那根線與特征中心點(diǎn)方向之夾角，作為輸入圖像的旋轉(zhuǎn)角度，d x，d y為模板中三星形線中心點(diǎn)的坐標(biāo).

（5）將所有點(diǎn)進(jìn)行變換對齊計(jì)算對齊點(diǎn)數(shù)，轉(zhuǎn)到步驟（4），計(jì)算所有的變換參數(shù)組的變換效果，取對齊點(diǎn)數(shù)最多的變化參數(shù)為最終變換參數(shù).

（6）變換，比較計(jì)算偏差，計(jì)算得分.

由于距中心點(diǎn)較遠(yuǎn)的地方旋轉(zhuǎn)時(shí)誤差也會較大，所以

K鄰域搜索算法廣泛使用于模式識別和分類的一種方法.通常計(jì)算某點(diǎn)的k個(gè)最近鄰域的方法是求出指定點(diǎn)和其他n-1個(gè)點(diǎn)的歐式距離，并比較大小順序，最后確定前k個(gè)點(diǎn)作為k鄰域.通過對特征向量的聚類和分析，以及采用其他計(jì)算方式，k鄰域方法可以對連續(xù)和離散空間中的數(shù)據(jù)進(jìn)行分析、分類和識別.

K鄰域方法的關(guān)鍵是k值的選取和評估方式的選擇.本文有采用三鄰域相似向量法進(jìn)行匹配測試.采用的相似度得分公式為采用界限盒的思想，即當(dāng)旋轉(zhuǎn)后的點(diǎn)與中心點(diǎn)的距離較遠(yuǎn)時(shí)，容忍度適當(dāng)增大，以增加兩個(gè)圖像匹配的機(jī)會.

4 實(shí)驗(yàn)驗(yàn)證

測試的指紋圖像來自F V C 2004，國際指紋識別競賽使用的指紋庫.其中的圖像包括形變，噪聲污染，殘缺，褶皺等低質(zhì)量的指紋，處理難度相對較大，非常適合用來驗(yàn)證指紋識別算法的性能.實(shí)驗(yàn)結(jié)果如下圖：

圖4 匹配結(jié)果對比

由上圖可以匹配的效果還是不錯的，左下角的四個(gè)點(diǎn)匹配最準(zhǔn)確，說明它們是這次匹配的基準(zhǔn)點(diǎn)，即具有最大相似度的星形線，距它們較遠(yuǎn)的點(diǎn)，匹配誤差相對較大，比如左上角的一系列點(diǎn)，但是在容忍度之內(nèi).理論上，當(dāng)兩幅圖像超過12個(gè)點(diǎn)相匹配就可以認(rèn)為兩者是源于同一個(gè)手指，顯然圖中匹配點(diǎn)超過了12個(gè)，因此可以判定兩者匹配.

5 結(jié)論

對指紋匹配過程進(jìn)行了詳細(xì)的分析和建模，并介紹了一種三鄰域相似向量法解決指紋匹配問題.通過對指紋庫里樣本的應(yīng)用，表明該算法能夠較快的完成特征點(diǎn)匹配，簡單快捷，可以應(yīng)用于終端指紋識別系統(tǒng).

〔1〕Mariano Fons etc.Design of FPGA-based Hardware AcceleratorsforOn-line FingerprintMatcherSystems. IEEE.

〔2〕Sharat Chikkerur,Sharath Pankanti,Novel Approaches for Minutiae Verification in Fingerprint Images.IEEE.

〔3〕Anil K.Jain,Jianjiang Feng.Latent Fingerprint Matching. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE.2008.

〔4〕楊小冬,寧新寶,尹義龍.自動指紋識別系統(tǒng)預(yù)處理技術(shù)及細(xì)節(jié)特征提取算法的研究.南京大學(xué)學(xué)報(bào) (自然科學(xué))，2006，42（4）.

〔5〕郭娟.基于FPGA硬件方式實(shí)現(xiàn)指紋識別系統(tǒng)研究.中國科學(xué)研究院碩士論文，2007.

〔6〕楊磊,等.基于STM32的指紋識別系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn).機(jī)電工程，2011,28(12）.

T P 391.41

A

1673-260X（2012）10-0031-03