自動指紋識別系統(tǒng)的實現(xiàn)

陳 英

（浙江科技學院 校園網(wǎng)管理中心，杭州310023）

生物特征識別技術指的是在某些需要進行身份驗證的環(huán)境下，運用自動化手段來測量一個人的身體特征，并將測量結果與數(shù)據(jù)庫的模板數(shù)據(jù)比較后完成認證。生物特征識別過程一般包含4步：圖像獲取→取特征→比較→匹配。

通常警用指紋自動識別系統(tǒng)主要應用于刑偵工作上，如“現(xiàn)場查十指”“十指查現(xiàn)場”“現(xiàn)場查現(xiàn)場”及“十指查十指”［1］。“現(xiàn)場查十指”通常是指“以案到人”，亦稱作“正查”，就是將現(xiàn)場采集來的指紋信息與系統(tǒng)數(shù)據(jù)庫中已備案的罪犯指紋信息進行比對，以此來確定犯罪嫌疑人?！笆覆楝F(xiàn)場”指的是“以人到案”，亦稱“倒查”，就是將個人身份已知的罪犯指紋同現(xiàn)場所采集回來的指紋加以比對，以此來確定此人是否具有犯罪嫌疑?！艾F(xiàn)場查現(xiàn)場”指的是“以案到案”，就是將若干個尚未確定的現(xiàn)場指紋進行比對，以此來確定它們之間存在的潛在聯(lián)系，實現(xiàn)串案并案?！笆覆槭浮敝傅氖恰耙匀说饺恕?，就是將待查的捺印指紋與指紋數(shù)據(jù)庫中已知身份的指紋進行比對，以確定該指紋的個人身份及前科。

輸入采集到的指紋，即可使用指紋自動識別系統(tǒng)對指紋圖像加以處理，找出每個指紋上的特征點，如指位、紋型、紋線的端點和交點、指紋的細節(jié)特征等，然后再與系統(tǒng)數(shù)據(jù)庫中已存儲的指紋進行比對。使用預先編制好的電腦程序可以在數(shù)據(jù)庫中實現(xiàn)高速檢索，并從中選出50～100枚最為相似的指紋供比對人員進行最后的比對處理。在整個指紋識別過程中，使用系統(tǒng)能夠完成80%以上的工作，同時綜合處理的速度要比人工比對快上好幾十倍甚至好幾百倍，而在采集活體和輸入捺印指紋圖像的過程中，基本上不再需要人工干預，從而大大降低了人工成本，提高了工作效率。

圖1 警用指紋自動識別系統(tǒng)的總體框架圖Fig.1 Frame diagram of police fingerprint automatic identification system

1 警用指紋自動識別系統(tǒng)總體框架及關鍵技術

警用指紋自動識別系統(tǒng)的總體框架如圖1所示，系統(tǒng)主要由指紋圖像采集、指紋圖像預處理、指紋圖像特征提取、指紋分類和指紋圖像匹配五部分組成。

1.1 指紋圖像采集

指紋圖像采集是指將能夠被計算機系統(tǒng)所處理的數(shù)字指紋圖像采集來并將其錄入自動指紋識別系統(tǒng)的一個過程［2］。它是自動指紋識別系統(tǒng)的首要環(huán)節(jié)。目前可以用于采集活體指紋的設備［3］主要有：光電式指紋采集器、晶體式指紋采集器和超聲波指紋采集器。這三種技術各有其優(yōu)缺點，總體看來，當前的活體指紋采集器多數(shù)存在以下缺點：手指的干濕度及清潔度對指紋圖像的質(zhì)量影響較嚴重；采集設備表面積較小，故采集到的指紋圖像并不完整，并且其中包含的特征信息量很少，以致無法為識別提供足夠的依據(jù)。

1.2 指紋圖像預處理

普通指紋數(shù)據(jù)庫中，低質(zhì)量的指紋圖像占10%左右，現(xiàn)場指紋比例就更高了。由于實際輸入的指紋圖像常常是一幅包含大量噪聲的灰度圖像，若不對其加以預處理操作，就會產(chǎn)生大量偽特征，指紋的真實特征被遺漏，或者指紋特征的位置和方向等信息出現(xiàn)了錯誤，這將直接影響到后續(xù)的處理工作。為了保證指紋識別系統(tǒng)運轉(zhuǎn)的整體效率，確保識別算法對輸入圖像質(zhì)量的魯棒性，并減少不必要的資源開銷，就有必要在分類、提取指紋特征前采取適當?shù)膱D像分割或增強處理，去除掉一些無用的圖像信息，使指紋脊線更清晰。對原始的指紋圖像直接提取其指紋特征時，預處理過程只不過是簡單的對指紋進行增強，也就是用一個濾波器來濾除噪聲并加強指紋脊線與谷線間的對比度；對細化的指紋圖像提取其指紋細節(jié)特征時，預處理過程一般要包括指紋圖像的分割→濾波增強→二值化過程→細化等一系列步驟，最終獲得一幅單像素的指紋脊線二值化圖像。

1.3 指紋圖像特征提取

指紋圖像特征提取是為了能較為準確地提取指紋特征，以確定每個指紋的類型，從而實現(xiàn)指紋匹配。當前的識別系統(tǒng)算法主要依靠以下特征［4－6］來進行指紋識別：

1）紋型 依照公安部所制定的標準，指紋紋型可分為“弓形紋”“斗形紋”“右箕形紋”“左箕形紋”“缺指”“其他”“未知”這七種類型，而其中“未知”類型只能應用在現(xiàn)場指紋上。

2）中心點 即讀取指紋和比對指紋的參考點，是指紋紋路的漸進中心位置（圖2）。

3）三角點 能夠提供指紋紋路的計數(shù)跟蹤起點。一般來說，三角點是指位于從中心點開始的第一個“端點”或“分叉點”，或是兩條紋路的“會聚點”“折轉(zhuǎn)點”“孤立點”，或是指向這些奇異點的點（圖2）。

圖2 指紋中心點、三角點、端點及分叉點簡圖Fig.2 Diagram of fingerprint center point，points of triangle，endpoint and bifurcation

4）局部特征點的分類 一般來講指紋特征包括“起點”“終點”“結合”“分叉”“點”“棒”“眼”“橋”“鉤”九大特征。通常計算機指紋識別系統(tǒng)只提取“端點”和“分叉”這兩類局部指紋特征。

5）方向 局部特征點可朝向一定的方向。

6）曲率 指紋紋路方向改變的速度。

7）位置 節(jié)點位置可通過坐標（x，y）來描述，可以是絕對的，也可以是相對的。

指紋的特征提取是指從已進行預處理后的指紋圖中提取全部指紋特征的一個過程。指紋的特征提取大多采用“鏈碼搜索法”來對紋線進行搜索，將其各種特征及坐標位置提取出來，并最終形成包含有指紋特征點的大小、種類、方向和坐標等有用信息的指紋特征文件。

1.4 指紋的分類

E.Henry最早提出了著名的Henry指紋分類系統(tǒng)，大大提高了指紋驗證效率，為指紋運用于個人標識起了非常重要的推動作用及更為科學的鑒別標準。該指紋分類法根據(jù)指紋中心點位置附近的紋線結構及指紋中心點與三角點的數(shù)量和相對位置，將指紋主要分成如圖3所示的五類結構：弓形、帳拱形、左箕形、右箕形和螺形。

圖3 指紋結構類型示圖Fig.3 Diagram of fingerprint types

指紋分類的核心目的就是為了提高系統(tǒng)識別效率。在刑偵工作中以案到人、以人到案、以案到案等模式均屬1∶N的指紋識別模式。在這種識別模式下，通過指紋分類后輸入的指紋只需與數(shù)據(jù)庫中同類型的指紋相匹配即可，大大減少了匹配次數(shù)，進而提高了1∶N模式的識別速度。

1.5 指紋圖像的匹配

指紋匹配就是指通過對兩幅不同的指紋圖像的特征集進行相似性比較后，判斷它們是不是屬于同一枚手指的一個過程［5］。目前指紋匹配模式識別上主要存在的難點有：剛性形變、彈性形變、部分重疊和特征集的可靠性［6］。

指紋匹配算法大致可以分為點模式匹配、相關性匹配、脊線特征匹配這三種類型，而目前應用最廣泛的就是基于點模式的指紋匹配方法。該方法主要優(yōu)勢有：一是點模式匹配方法只需提取少量的指紋細節(jié)點特征，因而信息存儲量較小；二是硬件發(fā)展對數(shù)據(jù)存儲空間的要求逐漸降低，使得指紋細節(jié)點可以加入與之相關聯(lián)的指紋脊線和紋理等信息數(shù)據(jù)，進而提高了匹配的準確性和校準的可靠性；三是硬件運算速度不斷提高，使得混合多種細節(jié)點匹配算法成為可能，進而提高了匹配的準確性。

2 算法實現(xiàn)及系統(tǒng)演示

本研究使用Visual C＋＋6.0設計開發(fā)了自動指紋識別算法演示系統(tǒng)。該系統(tǒng)主要包括指紋圖像數(shù)據(jù)的讀取與存儲、指紋圖像的預處理、指紋特征的提取與匹配等部分，基本上可以演示出自動指紋識別系統(tǒng)的整個過程。

2.1 基于矢量三角法的指紋匹配算法

基于矢量三角形法的指紋匹配算法［7－10］，利用3個近鄰特征點所組成的三角形結構，求取基準點定位和變換參數(shù)，并通過坐標的轉(zhuǎn)換，在極坐標中來進行匹配，并在匹配過程中引入多判決條件與可變界限盒匹配，以提高識別率。

指紋匹配過程中很重要的一步就是匹配基準點的求取。本研究選用了一種根據(jù)特征點集中3個近鄰點所組成的子集之間的相互關系來確定基準點及變換參數(shù)的算法。經(jīng)過細節(jié)提取和后處理等一些步驟之后，提取出來的每個細節(jié)點需要記錄三方面的信息，就是細節(jié)點的xy坐標、細節(jié)點的方向和細節(jié)點的類型。定義兩個細節(jié)特征點集P和Q，其中細節(jié)特征點集Q表示的是從輸入的指紋圖中所提取出來的N個細節(jié)點；點集P表示的是從模板圖像中所提取出來的M個細節(jié)點。這兩個點集可分別表示為：

其中（xPi，yPi，θPi）記錄了點集P中第i個特征點的3條信息：x坐標、y坐標和特征點方向。同理，（xQj，yQj，θQj）記錄了點集Q中第j個特征點的3條信息：x坐標、y坐標和特征點方向。

定義1若直角坐標系下的不在同一條直線上3個有向點按逆時針次序排列，稱這3個點按標準向系排列，所構成的三角形為標準系下矢量三角形。

定義2若2個同為標準系下的矢量三角形滿足如下條件，稱2個矢量三角形全等［8］。

1）三對對應邊長分別相等；

2）三對對應頂點間的方向角相等；

3）三對對應點的類型相同；

4）三對對應邊所穿過的脊線數(shù)目相同。

對模板集中的每個點A，在指紋圖上尋找與其最近的兩個特征點，其一記為R，另一個記為S，逆時針方向把它們連接起來組成一個三角形。那么把點A、點R與點S的類型（末梢點或分支點）分別記為nType1，nType2與nType3；方向角分別記為nBeta1，nBeta2與nBeta3。把連接點A與點R、點A與點S、點R與點S的3條虛擬的線段長度分別記為nDist1、nDist2和nDist3；所跨越的脊線數(shù)分別記為nCrossNum1、nCrossNum2和nCrossNum3。通常情況下，紋線數(shù)目比距離、相對角更具有魯棒性，因此，在判斷2個矢量三角形是否全等時，筆者增加了這個條件。并把點類型、方向角、邊長信息與跨越脊線數(shù)記入點A的對象中［9］。如果A屬于點集Q，B屬于點集P，下面式子均成立：

則認為2個矢量三角形全等，點A和點B分別是模板圖像和輸入圖像的參照點。

按指紋時由于用力的差異等多種原因必然會使兩幅指紋圖像間存在著非線性形變。即使是經(jīng)過校準，輸入圖像當中的細節(jié)點也不可能和模板圖像中的對應點完全重合。再加上采集過程中存在著噪聲等原因，就使得兩幅圖像上的對應點之間可能會存在一定的偏差。這些都要求細節(jié)匹配算法具有一定的彈性，即細節(jié)匹配算法應該是能在一定程度上包容由于提取出來的細節(jié)點位置不準確或者圖像的非線性形變而造成的對應點位置的差異。因此在判斷兩點的對應跨越脊線數(shù)、方向角、邊長是否相等時，都留下了一定的松弛量（Tc、T?和Td）。把找到的參照點記錄在兩個數(shù)組中，以便在后面的極坐標轉(zhuǎn)換中使用。

上述利用矢量三角形找參照點的方法由于利用了指紋圖像的結構信息，因而可以克服一定程度的指紋圖的變形、噪聲等干擾。

將細節(jié)點都轉(zhuǎn)換到極坐標下，在極坐標系中將輸入圖像與模板圖像的校準，只需將輸入細節(jié)點與模板細節(jié)點都分別相對于參照點Pi和Qi轉(zhuǎn)換到極坐標系中。即將輸入細節(jié)點與模板細節(jié)點都分別相對參照點Pi和Qi用下面的公式轉(zhuǎn)換到極坐標系中：

其中，（xiyiθi）T是待轉(zhuǎn)換細節(jié)點的坐標，（xcycθc）T是參照細節(jié)點的坐標，（rieiθi）T是細節(jié)點在極坐標中的表示（ri表示極半徑，ei表示極角，θi表示細節(jié)點相對于參照點的方向）。Δθ表示待測特征點的旋轉(zhuǎn)角度，即待測指紋點集P的參照點Pi相對模板點集Q的參照點Qi發(fā)生的旋轉(zhuǎn)角度，即：

其中，Pi→angle為參照點Pi沿著脊線的方向；Qi→angle為參照點Qi沿著脊線的方向。

在完成基點校準與得到模板特征的限界盒之后，就可以進行匹配了，匹配的原理亦是基于界限盒的匹配中所述的原理。采用匹配分數(shù)來表示待測指紋特征點集與模板點集之間的相似程度，分數(shù)越高匹配度也就越高。

2.2 指紋圖像預處理中的主要功能演示

指紋圖像的方向場是反映指紋圖像場的中心、圓形紋線趨勢場、斜角度直紋線趨勢場、水平紋線趨勢場及其混合趨勢場等，與物理場論的旋度和方向場相關［10］。該函數(shù)getOrientMap（）的功能就是實現(xiàn)指紋圖像方向場的算法。如圖4所示，（a）是指紋原圖，（b）是計算得到的梯度場，（c）是使用函數(shù)getOri entMap（）得到的方向場（代碼略）。

圖4 指紋圖像場Fig.4 Fingerprint image field

圖5 平滑和增強后的對比圖像Fig.5 Contrast image after smoothing and enhancement

指紋圖像經(jīng)過平滑、增強、二值化及過濾噪聲處理后，轉(zhuǎn)變?yōu)橘|(zhì)量較高的黑白指紋圖像，然而對二值化后的指紋圖像進行處理和提取出特征的程序還相當復雜，尚需要對指紋圖像經(jīng)過紋線圖像細化處理。指紋圖像細化函數(shù)void imageThin（）的功能就是實現(xiàn)指紋圖像增強的算法，圖6為指紋二值化圖和骨架細化提取后的圖像。

圖6 指紋二值化圖和骨架細化提取后的圖像Fig.6 Image of fingerprint two values of map and skeleton thinning after extraction

2.3 特征點提取的代碼實現(xiàn)及功能演示

中心點與三角點統(tǒng)稱為奇異點，它描述了指紋的整體特征，提取特征點的目的是進行指紋分類及比對過程中的坐標系校正。函數(shù)int getSingular（）實現(xiàn)了計算指紋圖像提取奇異點的功能。

指紋特征末梢點是指紋紋線兩頭末點，或起點和終點。函數(shù)bool IsEnd（）實現(xiàn)了對指紋圖像末梢點的提取運算。指紋特征分叉點是指紋兩條紋線相交匯集為一條紋線的交匯點。函數(shù)bool IsFork（）實現(xiàn)了對指紋圖像分叉點的提取運算。如圖7所示，（a）是指紋原圖像，（b）是指紋細化提取后圖像，（c）是計算得到的特征點，包括中心點、三角點、末梢點和分叉點。

圖7 指紋圖像的特征點提取結果圖Fig.7 Results map of feature point extraction for fingerprint image

2.4 系統(tǒng)演示

在系統(tǒng)開發(fā)過程中，將指紋的預處理和特征點提取兩個步驟合并在指紋模式識別算法綜合引擎FP模塊中。其中指紋圖像的預處理算法程序架構，由梯度和方向場、分割、均衡、收斂、平滑、智能增強、二值化及細化等圖像預處理算法程序模塊組成。指紋圖像特征點提取算法程序架構包括提取指紋對象特征端點、交叉點、中心點及三角點等算法程序模塊。使用指紋模式識別算法綜合引擎FP模塊預處理指紋圖像及提取指紋特征點的軟件界面如圖8所示。

圖8 指紋圖像預處理及特征點提取界面Fig.8 Fingerprint image preprocessing and feature extraction interface

指紋圖像特征比對算法程序操作如下，依次單擊“Open1”按鈕和“Open2”按鈕，導入兩幅指紋圖像，單擊“Match”按鈕，即進行兩指紋圖像的指紋對象特征比對。

圖9和圖10分別演示了系統(tǒng)運行過程，盡管這兩幅由兩次采集而得的指紋圖像看上去不同，但指紋的特征卻相同。因此，彈出消息框提示經(jīng)過算法比對是相同的結論“Same Fingerprint！”。

3 結 語

自動指紋識別技術是一個運用前景好且極其富挑戰(zhàn)性的研究課題，是一項綜合了計算機、模式識別及圖像處理等技術的復雜技術。本研究加深了筆者對該技術的了解，并取得了部分研究成果。因個人知識背景有限，尚有待進一步完善和改進的地方：一是當所采集到的指紋圖像的質(zhì)量很差時（比如犯罪現(xiàn)場的指紋），常規(guī)的分割方法不能夠精確地將指紋圖像背景區(qū)域和前景區(qū)域有效地分割開，而圖像分割的效果會直接影響特征提取的精確度（基本上依賴于人工標注指紋特征點），因此指紋圖像分割算法還需要進一步改進；二是本系統(tǒng)在針對高質(zhì)量指紋圖像（捺印指紋及CCD采集指紋）的處理時，取得了較好的實驗效果，但是對于低質(zhì)量（犯罪現(xiàn)場指紋）及一些扭曲形變較大的指紋圖像，特別是高質(zhì)量指紋圖像比對低質(zhì)量指紋圖像時（特征點數(shù)量相差較大），實驗結果并不理想，需要在指紋比對階段對匹配算法作進一步研究，做到自適應調(diào)整匹配算法的閾值；三是對于自動指紋識別系統(tǒng)的開發(fā)，筆者只設計出總體結構及功能，搭建了識別平臺，完成了指紋識別程序的開發(fā)，后續(xù)需要對指紋分類、壓縮及數(shù)據(jù)庫部分繼續(xù)開發(fā)，以便形成一整套警用指紋識別系統(tǒng)。

［1］顧勇.警用指紋識別系統(tǒng)中圖像預處理的研究［D］.重慶：重慶大學，2007.

［2］夏振華.指紋識別算法及小規(guī)模指紋識別系統(tǒng)的開發(fā)［D］.南京：南京航空航天大學，2006.

［3］尤松.指紋識別系統(tǒng)研究［D］.上海：東華大學，2005.

［4］徐國慶.指紋識別系統(tǒng)中的特征提取與匹配算法的研究和實現(xiàn)［D］.成都：電子科技大學，2007.

［5］王建永.指紋圖像的特征提取與匹配［D］.大連：大連理工大學，2003.

［6］劉健，王萬良.基于中心區(qū)域基準點的指紋匹配算法［J］.計算機應用與軟件，2011（2）：30－33.

［7］謝立鋒，陳靈梟.淺談指紋識別基本原理［J］.技術與市場，2008（1）：44－45.

［8］魏發(fā)建，游敏娟，王保帥，等.淺談指紋識別的基本原理［J］.中國科技信息，2009（10）：138－139.

［9］薛亞許，陳金玉.學校指紋考勤系統(tǒng)的設計與實現(xiàn)［J］.微型機與應用，2011（1）：83－85.

［10］賈聰智.指紋識別系統(tǒng)中的匹配算法研究與實現(xiàn)［D］.成都：電子科技大學，2004.