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

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

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

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

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

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

圖1 子頻段編碼原理圖

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

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

圖2 三級(jí)小波分解

1.2 圖像壓縮

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

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

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

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

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

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

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

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

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

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

2.3 指紋預(yù)處理

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

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

2.3.1 指紋圖像分割

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

2.3.1.1 定義F盒維數(shù)

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

(1)

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

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

(2)

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

(3)

2.3.1.3 計(jì)算梯度值

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

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

2.3.2 指紋圖像增強(qiáng)

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

圖6 原指紋圖像

圖7 增強(qiáng)后的指紋圖像

2.3.3 二值化和細(xì)化

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

H為切向像素值和：

(4)

V為法向像素值和：

(5)

如果V大于H，那么該點(diǎn)在脊線上，反之在谷線上。

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

2.4 指紋分類

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

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

圖8 指紋全局特征

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

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

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

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

判定奇異點(diǎn)需要使用Poincaré公式，求Po值：

(6)

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

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

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

(7)

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

(8)

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

2.5 指紋匹配

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

圖10 特征點(diǎn)匹配流程圖

圖11 固定界限盒模型

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

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

比對(duì)特征個(gè)數(shù)=0；

For eachPin 模板

For eachP′ in 樣板

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

{

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

比對(duì)特征個(gè)數(shù)++;

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

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

}

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

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

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

表1 不同識(shí)別算法對(duì)FVC2004的驗(yàn)證結(jié)果比較

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

4 結(jié)語

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