姚麗莎，徐國明，陳乃金，周 歡

(安徽新華學(xué)院信息系統(tǒng)軟件研究所，安徽 合肥 230088)

近年來，指紋識別技術(shù)現(xiàn)今已經(jīng)發(fā)展成熟，國內(nèi)外許多指紋識別研究成果主要描述如何構(gòu)造特征描述符。目前指紋描述符主要分為基于細(xì)節(jié)點的描述符和基于紋理的描述符兩類。TICO M[1]提出一種基于方向信息的描述符，PARK U[2]提出描述指紋信息的SIFT[3]描述符，JIANG X[4]提出最近鄰描述符，CHEN X[5]提出固定半徑的特征描述符，F(xiàn)ENG J[6]提出混合描述符可以結(jié)合細(xì)節(jié)點和紋理特征，CAPPELLI R[7]提出細(xì)節(jié)點柱形編碼(Minutia Cylinder-Code，MCC)結(jié)構(gòu)。

但是，指紋識別領(lǐng)域目前的研究重心主要在提高指紋識別的準(zhǔn)確度，忽略了海量指紋數(shù)據(jù)識別的時間問題，海量指紋識別的實用性成為主要難題。MIRON R[8]提出了一種新的指紋識別架構(gòu)，在多個服務(wù)器上分別放置大量的指紋數(shù)據(jù)，在各個服務(wù)器上順序檢索指紋，檢索成功后結(jié)束。該架構(gòu)雖然解決了數(shù)據(jù)集分布式存儲的問題，但是仍為集中式計算，并未實現(xiàn)分布式并行計算，不能完成實時檢索。PERALTA D[9]根據(jù)指紋的分布式特點，在多個節(jié)點上進行指紋數(shù)據(jù)分布，在每個節(jié)點上并行的檢索指紋，可以解決海量指紋數(shù)據(jù)實時檢索的問題。目前的指紋識別系統(tǒng)主要通過暴力匹配，而這對于海量指紋是不適用的。本文提出了分布式海量指紋識別技術(shù)，首先對采集的指紋進行特征提取，然后利用指紋特征對指紋進行全局指紋分類，最后利用匹配界限盒方法進行指紋匹配以完成未知指紋數(shù)據(jù)的身份確認(rèn)。利用分布式網(wǎng)絡(luò)計算的運算特性，設(shè)計了一個分布式海量指紋識別系統(tǒng)。

1 指紋數(shù)據(jù)的壓縮及存儲

在海量指紋數(shù)據(jù)檢索的過程中，需要從數(shù)據(jù)庫下載一些待比對的指紋圖像到本地，為了滿足應(yīng)用需要，對指紋數(shù)據(jù)進行壓縮傳輸。目前，存在一種壓縮方法可以滿足對指紋圖像數(shù)據(jù)進行壓縮傳輸?shù)默F(xiàn)實應(yīng)用要求，可以把原有的指紋特點保存，這種壓縮方法就是小波壓縮[10]。小波變換子頻段編碼的實現(xiàn)方法：①用一組濾波器采用重復(fù)卷積的方法，把采集信號分為低頻和高頻。②統(tǒng)計低頻和高頻分量，量化特征相類似的編碼器。③在解碼時，為了重建圖像需要對低頻分量和高頻分量進行插值和共軛濾波?；驹砣鐖D1所示。

圖1 子頻段編碼原理圖

1.1 小波變換子頻段編碼的工作過程

小波變換子頻段編碼的主要工作包括：①一個濾波器(Qualcomm，low pass)把輸入端在水平方向的信號進行卷積，同時另一個濾波器(Qualcomm，low pass)把輸入端在垂直方向的信號進行卷積[11]。②能夠獲得四塊面積，把這四塊面積與原圖像進行相比，可以看到占到原圖面積的25%，這四塊面積包括：低頻分量LL、垂直方向的高頻分量HL、水平方向的高頻分量LH和對角線方向的高頻分量HH。③編碼高頻分量以及量化編碼，編碼低頻分量以及量化編碼。④繼續(xù)分解垂直高頻分量得到二級小波分解和三級小波分解，編碼也類似[12]。三級小波分解如圖2所示。

圖2 三級小波分解

1.2 圖像壓縮

圖像壓縮具體做法包括：設(shè)置一個閾值σ，把經(jīng)過小波變換得到的水平、垂直和對角細(xì)節(jié)分量值與該閾值σ比較，再把小于等于σ的細(xì)節(jié)分量值設(shè)置為“0”。由此進行編碼，這樣就實現(xiàn)了圖像壓縮。

編碼是壓縮的最后一個步驟。通常結(jié)合赫夫曼編碼和快速余弦變換方法來壓縮低分辨率子圖HH，去除細(xì)節(jié)子圖的高頻分量，結(jié)合Huffman編碼來壓縮圖像。使用赫夫曼編碼方法包括以下步驟：①按降序排列概率的大小。②對兩個最小的概率進行加法運算，然后一個新的概率集合就構(gòu)成了，按降序排列概率的大小，以此類推，一直到只存在兩個概率為止。③碼子需從最后開始完成反向分配，對最后兩個概率一個賦予“0”，一個賦予“1”。對碼子進行概率統(tǒng)計。然而在實際應(yīng)用中，每幅圖像的出現(xiàn)概率是不同的，對于任何圖像壓縮而言，需要進行概率統(tǒng)計。

2 分布式海量指紋識別技術(shù)

分布式網(wǎng)絡(luò)是把指紋數(shù)據(jù)庫分布存儲，根據(jù)不同地域，將指紋存儲在不同地方。并且每個分?jǐn)?shù)據(jù)庫根據(jù)指紋特征分類存儲指紋數(shù)據(jù)信息，每一個分?jǐn)?shù)據(jù)庫服務(wù)器同時搜尋，進而提高對未知指紋數(shù)據(jù)身份確認(rèn)的速度。

2.1 分布式海量指紋識別系統(tǒng)組成

海量指紋數(shù)據(jù)庫識別系統(tǒng)包括3個部分：①利用指紋采集設(shè)備對個體進行指紋采集，然后對采集的指紋進行指紋預(yù)處理和特征提取。②計算機發(fā)送采集的指紋數(shù)據(jù)到數(shù)據(jù)庫服務(wù)器。③利用全局指紋分類系統(tǒng)驗證采集的指紋，通過以上操作進行未知指紋數(shù)據(jù)的身份確認(rèn)。原理圖如圖3所示。

圖3 分布式海量指紋識別系統(tǒng)的原理圖

圖4 分布式海量指紋識別系統(tǒng)架構(gòu)

2.2 分布式海量指紋識別系統(tǒng)工作流程

分布式海量指紋識別系統(tǒng)的工作流程包括：①利用指紋采集設(shè)備對個體進行指紋采集。②計算機通過預(yù)處理和對采集的指紋進行特征提取，利用計算機將采集的指紋數(shù)據(jù)發(fā)送到指紋數(shù)據(jù)庫主服務(wù)器中。③指紋數(shù)據(jù)主服務(wù)器將特征信息發(fā)送給每個指紋數(shù)據(jù)分服務(wù)器。④每個指紋數(shù)據(jù)分服務(wù)器對特征信息進行提取,并在指紋數(shù)據(jù)庫分服務(wù)器中搜尋，然后將結(jié)果發(fā)送到指紋數(shù)據(jù)主服務(wù)器。⑤指紋數(shù)據(jù)主服務(wù)器把結(jié)果發(fā)送到計算機。具體流程如圖4所示。

2.3 指紋預(yù)處理

指紋預(yù)處理目的是提高指紋圖像的質(zhì)量，將特征提取的準(zhǔn)確性提高。本文預(yù)處理過程包括圖像分割、增強、二值化和細(xì)化。指紋預(yù)處理流程圖如圖5所示。

圖5 指紋預(yù)處理流程圖

2.3.1 指紋圖像分割

因為指紋與圖像背景難以區(qū)分，需要對指紋圖像進行分割。背景的梯度值較低，而指紋圖像的梯度場值比較高。因此，利用梯度場來進行指紋圖像分割，即采用分型維數(shù)來分割指紋圖像。圖像塊的分形維數(shù)描述了其紋理和灰度分布的復(fù)雜程度，其是單位區(qū)域上的梯度，利用前景與背景的分形維數(shù)可以區(qū)分圖像的前景和背景。本文利用分形維數(shù)來分割指紋圖像的背景與前景，具體步驟如下：

2.3.1.1 定義F盒維數(shù)

即設(shè)F是Rn上的任意非空的有界子集，Nσ是直徑最大為σ、可以覆蓋F的集合的最少個數(shù)。則F的盒維數(shù)定義為：

(1)

2.3.1.2 計算圖像的盒維數(shù)

圖像中像素點的灰度值表示為Z=f(x,y)，其中，(x,y)為像素點的位置坐標(biāo)，Z代表對應(yīng)點的灰度值。設(shè)圖像大小為M×M，將圖像的XY平面分成大小為σ×σ的格子，設(shè)該XY坐標(biāo)系中格子(i,j)里像素點灰度最大值為uσ(i,j)，灰度最小值為bσ(i,j)，且定義兩者的差值為：

(2)

對于所有邊長σ、格子非空的盒子總數(shù)Nσ的計算公式為：

(3)

2.3.1.3 計算梯度值

2.3.1.4 通過梯度閾值分割前景和背景

圖像質(zhì)量不同，閾值的取值也不同。通常，若圖像平滑則閾值取30～40，若圖像平滑度不夠則閾值取50。單位區(qū)域閾值通過計算單位區(qū)域上的平均梯度來取值。其算法是：f(x,y)為圖像的函數(shù)，T(x,y)為某位置(x,y)的梯度，則T(x,y)=f(x,y)。設(shè)A為分割閾值，若T(x0,y0)>A，則(x0,y0)點屬于指紋圖像的前景。若T(x0,y0)

2.3.2 指紋圖像增強

采用Gabor增強算法實現(xiàn)指紋圖像增強。用該圖像塊的紋線方向設(shè)置每塊圖像對應(yīng)的濾波器的方向，用該圖像塊的紋線頻率設(shè)置每塊圖像所對應(yīng)的濾波器的頻率。指紋圖像的增強效果受濾波器通帶大小設(shè)置的影響。設(shè)置較大通帶時，噪聲的抑制效果不明顯，增強效果不佳，但對頻率和方向誤差有一定程度的容忍；設(shè)置較小通帶時，濾波器的頻率和方向選擇性較強，因此對濾波器頻率和方向的誤差較敏感，但是對分離枯連紋線和連接斷裂紋線的效果佳。先驗值表明，濾波器窗口設(shè)為11時，濾波效果佳。具體算法如下：①拆分指紋圖像為互不相交的區(qū)域；②分別計算各區(qū)域指紋的頻率和方向；③為每個圖像區(qū)域構(gòu)建相應(yīng)的增強模板；④對所有圖像區(qū)域進行濾波。圖6為原指紋圖像，圖7為增強后的指紋圖像。

圖6 原指紋圖像

圖7 增強后的指紋圖像

2.3.3 二值化和細(xì)化

為了使指紋紋線脊的灰度值趨于一致，需對指紋圖像進行二值化。對于紋線上的黑點來說，黑點大多分布在沿紋線方向的附近區(qū)域，其灰度值的和較小。白點大多分布在紋線方向的垂直方向附近，其在垂直方向上灰度值的和較大。對于紋線之間的白點來說，白點大多分布在沿紋線方向的附近區(qū)域，其灰度值的和較大，黑點大多分布在紋線方向的垂直方向附近，其在垂直方向上灰度值的和較小。因此，如果某點的法向灰度和大于切向灰度和，則判定黑點在脊線上，反之則白點在谷上。設(shè)f(x0,y0)為該點的灰度值，其方向場為ο(x0,y0)，σ為某一范圍。

H為切向像素值和：

(4)

V為法向像素值和：

(5)

如果V大于H，那么該點在脊線上，反之在谷線上。

為了刪除紋線的邊緣像素，突出指紋紋線主要特征，對指紋圖像進行細(xì)化處理。本文的細(xì)化算法采用查表法。

2.4 指紋分類

指紋是表皮上最突出的一條線，是指手指末端的凹凸皮膚的線條。因為每個指紋不相同，所以指紋又被人們稱為“人體身份證”。指紋的特征包括全局和細(xì)節(jié)特征[13]。

全局特征是指人們通過眼睛能夠看到的指紋特征，主要包括：①模式區(qū)：包含指紋整體特征的地方，通過模式區(qū)域可以區(qū)分指紋的類別。②三角點：斷點、核心點或兩紋線間出現(xiàn)的第一個分岔點，如圖8所示。三角點可以用于線的計數(shù)和跟蹤。③紋數(shù)：在模式區(qū)中指紋紋路的個數(shù)。④樣式線：包圍模式區(qū)的紋線開始平行的地方所出現(xiàn)的交叉紋路，其通常很短就中斷了，但其外側(cè)線開始連續(xù)延伸。⑤中心點：指紋紋線的漸進中心，常作為讀取指紋的參考點。中心點位置如圖8所示。

圖8 指紋全局特征

局部特征指的是指紋上的節(jié)點。每個人的指紋總體特征可能相似，但是它們的節(jié)點是不可能一樣的。圖9給出了常見的細(xì)節(jié)點類型。

圖9 常見的局部細(xì)節(jié)點類型

節(jié)點包括：①端點：紋線終結(jié)點。②分歧點：兩條平行紋線的分開起點。③分叉點：一條紋線分開成多條的起點。④孤立點：一條很短的線以至于形成一個點。⑤環(huán)點：一條紋線分開成為兩條之后，又合并成一條。⑥短紋：一條很短的線，但不至于形成一個點的紋路。

利用奇異點的類別和個數(shù)對指紋進行分類。奇異點包括了中心點和三角點，它描述了指紋的整體特征，提取特征點提取進行指紋分類。指紋分類可以依據(jù)一個中心點類型、兩個中心點類型、一個中心點和一個三角點類型、零個三角點和零個中心點類型，用這四種類型進行分類。

判定奇異點需要使用Poincaré公式，求Po值：

(6)

Poincaré是對某點周圍一圈求方向場差的積分。方向場差求得值越大，Po值越大。其周圍方向場變化越劇烈，則奇點存在的可能性越大。

在數(shù)字指紋學(xué)中，需要用離散Poincaré建立數(shù)字模型，表示的方法為方格計算法。取一個5×5的方格，計算(i,j)為中心各以D或d為半徑的區(qū)域方向場差的和。

在5×5方格內(nèi)，以(i,j)為中心，形成順時針方向閉合曲線D1,D2,…,D12。該閉合曲線的Po值為：

(7)

在3×3方格內(nèi)，以(i,j)為中心，形成順時針方向閉合曲線D1,D2,…,D8。該閉合曲線的Po值為：

(8)

由于受圖像中存在噪聲等因素的影響，指紋可能存在偽奇異點。為了消除偽奇異點，計算閉合曲線順時針方向以(i,j)為中心的Po值。只有3×3方格和5×5方格的Po值相同時，候選奇異點才作為真正的奇異點。

2.5 指紋匹配

指紋匹配是指對輸入樣板圖像對比紋預(yù)留模板圖像中的所有特征點的匹配，該流程如圖10所示。設(shè)模板特征點為P，樣板特征點為P′，若P約等于P′，則給分?jǐn)?shù)累加上相應(yīng)的分?jǐn)?shù)。用相似度公式計算出相似度，與合格閾值進行對比，若小于合格閾值則返回比對成功，若大于合格閾值則返回比對失敗。指紋匹配算法采用匹配界限盒，固定界限盒模型如圖11所示，設(shè)定角度誤差上限為A，距離誤差上限為D，如果線性匹配誤差在界限盒內(nèi)，由表示模板上某個特征點與樣板上對應(yīng)特征點是匹配的，因此就在相似度公式的分?jǐn)?shù)項加分，完成線性匹配算法。

圖10 特征點匹配流程圖

圖11 固定界限盒模型

匹配界限盒流程偽代碼為：

總分?jǐn)?shù)=0；

比對特征個數(shù)=0；

For eachPin 模板

For eachP′ in 樣板

If (P與P′沒用被比對過且是否相似(P與P′相似分?jǐn)?shù)))

{

總分?jǐn)?shù)+=相似分?jǐn)?shù);

比對特征個數(shù)++;

標(biāo)記P被比對過

標(biāo)記P′被比對過

}

3 實驗結(jié)果分析

本文利用分布式網(wǎng)絡(luò)設(shè)計了一個分布式海量指紋識別系統(tǒng)，該系統(tǒng)包括指紋數(shù)據(jù)主服務(wù)器和分服務(wù)器。①在主服務(wù)器上打開一個指紋圖像；②通過主服務(wù)器連接到分服務(wù)器；③在分服務(wù)器進行測試；④在分服務(wù)器的Search ID框中，輸入from 2 to 6；⑤在分服務(wù)器獲取未知指紋；⑥通過分服務(wù)器向主服務(wù)器發(fā)送比對結(jié)果。

采用國際標(biāo)準(zhǔn)測試庫FVC2004指紋庫中的指紋作為標(biāo)準(zhǔn)指紋庫進行測試，采用文獻[7]中新的細(xì)節(jié)點柱形編碼(MCC)結(jié)構(gòu)的指紋識別技術(shù)和國際商用的BioCore SDK進行對比實驗。對比結(jié)果如表1所示。

表1 不同識別算法對FVC2004的驗證結(jié)果比較

在表1中，相等錯誤率(EER)表示給定匹配相似度下誤識率(FAR)和拒識率(FRR)相等時的錯誤率。可以看出，本文算法的識別準(zhǔn)確率和識別效果與其他兩種算法相差不大，但是識別效率大大提高了。

4 結(jié)語

目前指紋識別的研究大多都集中于如何提高指紋識別的準(zhǔn)確度，但是忽略了匹配的時間開銷，即沒有在海量數(shù)據(jù)下考慮問題。因此在海量指紋電子檔案中快速比對指紋是一個很大的難題。本文提出了分布式海量指紋識別技術(shù)，通過小波變換對指紋進行壓縮并存儲在分布式網(wǎng)絡(luò)中，提高算法效率。首先，通過分形維數(shù)分割指紋圖像背景，采用Gabor增強算法進行指紋預(yù)處理；然后，提取指紋奇異點，利用奇異點的個數(shù)和類別對指紋進行分類；最后，通過匹配界限盒完成指紋匹配。實驗結(jié)果表明，分布式海量指紋識別在海量指紋識別上具有很好的性能，提高了實時識別的效率。