基于點(diǎn)模式的指紋匹配

◎徐建國

基于點(diǎn)模式的指紋匹配

◎徐建國

自動(dòng)指紋識(shí)別已在各個(gè)領(lǐng)域廣泛應(yīng)用，除了傳統(tǒng)的司法公安領(lǐng)域，自動(dòng)指紋識(shí)別還可以作為計(jì)算機(jī)操作系統(tǒng)和網(wǎng)絡(luò)訪問認(rèn)證用戶的手段，以及用于金融保險(xiǎn)方面的身份確認(rèn)。指紋匹配是自動(dòng)指紋識(shí)別最重要問題之一。一般用脊線的分歧點(diǎn)和端點(diǎn)這樣的細(xì)節(jié)點(diǎn)來表示一個(gè)指紋，并通過細(xì)節(jié)匹配來進(jìn)行指紋匹配。

在采集手指指紋信息時(shí)，因?yàn)榘磯旱牧Χ?、方向、位置不一樣，都?huì)導(dǎo)致指紋圖像出現(xiàn)非線性形變、平移和旋轉(zhuǎn)，導(dǎo)致相同指紋的圖像仍然不盡相同。在指紋識(shí)別算法中，怎樣準(zhǔn)確識(shí)別這類圖像，是問題的難點(diǎn)和重點(diǎn)。

以校準(zhǔn)點(diǎn)為基準(zhǔn)的特征點(diǎn)匹配算法可靠性高，原理簡(jiǎn)單，專家學(xué)者開展了大量研究。在指紋匹配算法中也可以使用這一算法：

1.校準(zhǔn)特征點(diǎn)集：對(duì)模板特征點(diǎn)和輸入特征點(diǎn)進(jìn)行匹配和定位，對(duì)二者的平移和旋轉(zhuǎn)參數(shù)進(jìn)行計(jì)算，校準(zhǔn)平移和旋轉(zhuǎn)參數(shù)以后，在點(diǎn)集中保存。

2.點(diǎn)匹配：對(duì)特征點(diǎn)集進(jìn)行校準(zhǔn)，然后轉(zhuǎn)化到極坐標(biāo)系內(nèi)，通過相應(yīng)的點(diǎn)匹配算法進(jìn)行匹配（用于減小誤差或形變帶來的干擾）。

描述指紋特征點(diǎn)的參數(shù)

指紋節(jié)點(diǎn)的特點(diǎn)主要包括以下三類：1.位置，可以利用（x，y）坐標(biāo)表示不同節(jié)點(diǎn)的位置，能采用絕對(duì)坐標(biāo)或相對(duì)坐標(biāo)。2.方向，節(jié)點(diǎn)與某一個(gè)方向一致。3.曲率，反映了指紋線路改變程度。在匹配指紋時(shí)，方向和位置這兩個(gè)特征點(diǎn)使用較為廣泛。計(jì)算指紋曲率要跟蹤指紋線路，計(jì)算難度相對(duì)較大。

坐標(biāo)系的選取

利用點(diǎn)匹配理論，能夠?qū)煞鶊D像進(jìn)行匹配。采用伸縮、平移、旋轉(zhuǎn)等方式，將指紋圖像加入到模板之中。根據(jù)圖像校準(zhǔn)點(diǎn)進(jìn)行的匹配散發(fā)，要先對(duì)待測(cè)和實(shí)際指紋間的對(duì)應(yīng)關(guān)系進(jìn)行計(jì)算，并對(duì)比二者的特征。圖像校準(zhǔn)就是指確定二者變換關(guān)系。出現(xiàn)非線性形變的指紋圖像，圖片的某個(gè)區(qū)域會(huì)出現(xiàn)放射性的擴(kuò)張。所以，利用極坐標(biāo)反應(yīng)非線性形變更為合適。與此同時(shí)，極坐標(biāo)不必對(duì)圖像平移進(jìn)行分析，模板和待測(cè)指紋圖像之間的平移參數(shù)是相同的。利用極坐標(biāo)，能夠抵消掉存在平移的兩個(gè)對(duì)應(yīng)點(diǎn)。因此，相對(duì)于指標(biāo)坐標(biāo)系，對(duì)圖像旋轉(zhuǎn)進(jìn)行處理更適宜采用極坐標(biāo)系。所以，本文重點(diǎn)介紹基于極坐標(biāo)系的節(jié)點(diǎn)匹配技術(shù)。

參考點(diǎn)的定位

要準(zhǔn)確定位參考點(diǎn)的位置，以保證特征點(diǎn)的平移和旋轉(zhuǎn)不變性。在指紋識(shí)別中，確定指紋圖像參考點(diǎn)的位置是極為關(guān)鍵的技術(shù)。分級(jí)中心搜索法、點(diǎn)方向一致性度量法、Poincare索引法等都能用于定位參考點(diǎn)。上述算法以圖像局部特征為基準(zhǔn)進(jìn)行。此外，有學(xué)者指出，可以通過細(xì)化圖對(duì)參考點(diǎn)進(jìn)行跟蹤。然而，該算法難度較大。如果圖像中存在大量噪聲，會(huì)導(dǎo)致頂點(diǎn)確實(shí)，就不能準(zhǔn)確尋找到中心點(diǎn)，也不能完成匹配。

本文對(duì)指紋圖像進(jìn)行預(yù)處理后，提取出脊線信息，定位參考點(diǎn)的位置。通過預(yù)處理，能夠有效減小圖像噪聲，提高定位的準(zhǔn)確度。通過前期準(zhǔn)備，還能減少計(jì)算時(shí)間，提高效率。等間距采樣脊線，就能夠提取出脊線信息，將脊線平均距離作為抽樣間隔更為適宜。各指紋圖像里都包含大量特征點(diǎn)，離散采樣各特征點(diǎn)所在的脊線，會(huì)增加算法的復(fù)雜度，增加計(jì)算量，對(duì)于數(shù)據(jù)存儲(chǔ)量也有更高的要求。為了便于應(yīng)用，相較于端點(diǎn)而言，分叉點(diǎn)具有采樣結(jié)構(gòu)可靠性更高。因此，離散采樣采用分叉點(diǎn)所在脊線。

第一級(jí)匹配

大部分參考點(diǎn)都在指紋中，圓心就是參考點(diǎn)，半徑是指紋的長度。能夠在模板和輸入圖像里，得到面積一樣的關(guān)注區(qū)域。通過設(shè)置關(guān)注區(qū)，能夠減小指紋形變帶來的影響，還能為匹配提供方便。具體匹配流程如下：將關(guān)注區(qū)的半徑設(shè)置為96；對(duì)關(guān)注區(qū)內(nèi)分叉點(diǎn)和端點(diǎn)進(jìn)行搜索，并統(tǒng)計(jì)個(gè)數(shù)。Pb、Pe、Qb、Qe分別為模板和輸入圖像內(nèi)分叉點(diǎn)、端點(diǎn)的個(gè)數(shù)；對(duì)進(jìn)行計(jì)算。如滿足且條件，那么開始下一級(jí)匹配，如不滿足該條件，表示二者不匹配。

第二級(jí)匹配

完成一級(jí)匹配后，開始第二級(jí)匹配。假設(shè)具有絕對(duì)精準(zhǔn)匹配的兩個(gè)點(diǎn)模式集，則所有對(duì)應(yīng)點(diǎn)都是相互重合的。在該條件下，匹配點(diǎn)的過程就轉(zhuǎn)換換位統(tǒng)計(jì)重合點(diǎn)數(shù)量。但是，該情況并不會(huì)發(fā)生。首先，在檢測(cè)和定位細(xì)節(jié)點(diǎn)時(shí)，會(huì)存在一定的誤差，無法保證校準(zhǔn)結(jié)果的絕對(duì)精確。其次，校準(zhǔn)模型無法解決非線性形變的問題。所以，該算法有相應(yīng)的容忍度，彈性可調(diào)節(jié)。

針對(duì)彈性匹配算法，首先要對(duì)界限盒的概念進(jìn)行介紹：界限盒是指將盒子放到模板細(xì)節(jié)點(diǎn)上。A和B分別用來表示界限盒的尺寸。該盒子的極半徑差異為A，該盒子極角的差異為B。本文采用的界限盒大小可調(diào)節(jié)，即隨著極半徑的變化，A和B也會(huì)進(jìn)行相應(yīng)的調(diào)整。非線性形變的變化沒有規(guī)律，在特定范圍內(nèi)擴(kuò)張性的增長。如果極半徑不大，發(fā)生很小的變化就能導(dǎo)致極角出現(xiàn)很大變化，而極半徑只需進(jìn)行稍微調(diào)整。因此，在該條件下，A通常小于B；如果極半徑較大，極角發(fā)生很小的變化就能導(dǎo)致極半徑出現(xiàn)很大變化，而極角只需進(jìn)行稍微調(diào)整。因此，在該條件下，A通常大于B。尺寸可調(diào)節(jié)的界限盒具有更強(qiáng)的適應(yīng)能力。因此，其匹配精度更好。

設(shè)置好界限盒的尺寸后，按照下列步驟匹配特征點(diǎn)：對(duì)細(xì)節(jié)點(diǎn)進(jìn)行排序。沿著極角遞增的方向，對(duì)兩個(gè)模板排序；確定模板節(jié)點(diǎn)中所有節(jié)點(diǎn)的限界盒；對(duì)匹配分?jǐn)?shù)進(jìn)行初始化；匹配輸入圖像點(diǎn)L和模板圖像點(diǎn)K；對(duì) 進(jìn)行計(jì)算；如果模板內(nèi)節(jié)點(diǎn)的數(shù)量為n，則的結(jié)果如下：匹配下一個(gè)模板圖像和輸入圖像，重復(fù)步驟1，直到匹配完所有模板以后終止。把的最大值以及其對(duì)應(yīng)的模板計(jì)算出來。如果符合這一條件，表示匹配成功，否則匹配失敗。其中，用來表示預(yù)先設(shè)置的閾值范圍。

（作者單位：湖北工業(yè)大學(xué)）