指紋識(shí)別算法是實(shí)現(xiàn)指紋識(shí)別的關(guān)鍵，它直接決定了識(shí)別率的高低，是指紋識(shí)別技術(shù)的核心。雖然這些算法日臻完善，但仍有進(jìn)一步降低錯(cuò)誤率的空間。
目前，指紋識(shí)別技術(shù)的研究無(wú)論是在前端的數(shù)據(jù)采集上還是在后端的指紋識(shí)別算法上都已經(jīng)取得了巨大的進(jìn)展。于是，很多人認(rèn)為現(xiàn)在的指紋識(shí)別技術(shù)已經(jīng)很完善了，不再需要研究了。但這種觀點(diǎn)是錯(cuò)誤的，在指紋識(shí)別技術(shù)上仍然有一些沒(méi)有解決好的問(wèn)題，如: 低質(zhì)量指紋圖像的處理、形變指紋圖像的匹配、活體指紋的檢測(cè)等。這些都是經(jīng)常遇到、非常重要和亟待解決的問(wèn)題。在國(guó)際指紋識(shí)別競(jìng)賽（FVC2004）中，指紋數(shù)據(jù)庫(kù)DB1中有些指紋圖像的形變就很大，而位于第一名的指紋識(shí)別算法的等錯(cuò)誤率(EER)是1.97%，從中可以看出形變指紋圖像的處理仍然不是很理想，有著很多工作要做。
自動(dòng)指紋識(shí)別系統(tǒng)（Automatic Fingerprint Identification System，簡(jiǎn)稱(chēng)AFIS）是通過(guò)特殊的光電轉(zhuǎn)換設(shè)備和計(jì)算機(jī)圖像處理技術(shù)，對(duì)活體指紋進(jìn)行采集、分析和比對(duì)，可以自動(dòng)、迅速、準(zhǔn)確地鑒別出個(gè)人身份的。一般可以分成“離線部分”和“在線部分”兩個(gè)部分。如圖1所示。
|
|
圖1 自動(dòng)指紋識(shí)別系統(tǒng)框圖
|
其中離線部分包括用指紋采集儀采集指紋、提取出細(xì)節(jié)點(diǎn)、將細(xì)節(jié)點(diǎn)保存到數(shù)據(jù)庫(kù)中形成指紋模板庫(kù)等主要步驟。在線部分包括用指紋采集儀采集指紋、提取出細(xì)節(jié)點(diǎn)、然后將這些細(xì)節(jié)點(diǎn)與保存在數(shù)據(jù)庫(kù)中模板細(xì)節(jié)點(diǎn)進(jìn)行匹配，判斷輸入細(xì)節(jié)點(diǎn)與模板細(xì)節(jié)點(diǎn)是否來(lái)自同一個(gè)手指的指紋。一般來(lái)說(shuō)，離線處理允許人工因素介入，可根據(jù)需要手動(dòng)調(diào)整系統(tǒng)參數(shù)，而在線處理應(yīng)完全由系統(tǒng)自動(dòng)完成所有操作。
本文主要對(duì)指紋圖像增強(qiáng)、特征點(diǎn)提取、匹配以及分類(lèi)和壓縮算法進(jìn)行介紹。
指紋圖像增強(qiáng)算法
采集獲得的指紋圖像通常都伴隨著各種各樣的噪聲，一部分是由于采集儀造成的，比如采集儀上的污漬，采集儀的參數(shù)設(shè)置不恰當(dāng)?shù)取Ａ硗庖徊糠质怯捎谑种傅臓顟B(tài)造成的，比如手指的過(guò)干、太濕、傷疤、脫皮等等。第一種相對(duì)來(lái)說(shuō)是固定的系統(tǒng)誤差，比較容易恢復(fù)。另外一類(lèi)和個(gè)體手指密切相關(guān)，比較難于恢復(fù)。指紋增強(qiáng)在指紋圖像的識(shí)別過(guò)程中是最為重要的一環(huán)，這部分算法的優(yōu)劣將對(duì)整個(gè)系統(tǒng)的性能產(chǎn)生至關(guān)重要的影響。如果這一部分沒(méi)有處理好，也很難通過(guò)改進(jìn)后面的細(xì)節(jié)提取過(guò)程而獲得好的效果。
指紋圖像是連續(xù)脊線和谷線組成的（在細(xì)節(jié)點(diǎn)處除外），具有豐富紋理信息的圖像。對(duì)于灰度指紋圖像，脊線和谷線在局部的小鄰域內(nèi)可以認(rèn)為是正弦波形狀，具有一定的頻率和方向。使用方向場(chǎng)和Gabor濾波器來(lái)進(jìn)行增強(qiáng)的算法就是基于這樣的特點(diǎn)進(jìn)行。
指紋專(zhuān)家通常是根據(jù)視覺(jué)上的脊線信息來(lái)準(zhǔn)確地識(shí)別出真正的細(xì)節(jié)點(diǎn)。這些脊線的關(guān)系有局部脊線的方向、脊線的連續(xù)性、脊線的曲率、光滑度、脊線走向趨勢(shì)等等。而諸如指紋的脊線連接、局部脊線方向和脊線的光滑度這樣的結(jié)構(gòu)信息是有可能在計(jì)算機(jī)中表示出來(lái)的。所以也可以把人對(duì)指紋結(jié)構(gòu)的認(rèn)識(shí)引入指紋圖像處理的過(guò)程中，用計(jì)算機(jī)來(lái)模擬指紋專(zhuān)家做圖像增強(qiáng)的算法。
圖像的預(yù)處理指的是在指紋進(jìn)行圖像增強(qiáng)前使用一些簡(jiǎn)單的圖像處理手段對(duì)圖像進(jìn)行初加工的過(guò)程。常見(jiàn)的預(yù)處理有: 灰度的均衡化，這可以消除不同圖像之間對(duì)比度的差異; 使用簡(jiǎn)單的低通濾波消除斑點(diǎn)噪聲、高斯噪聲; 計(jì)算出圖像的邊界，進(jìn)行圖像的裁剪，這樣可以減少下一步的計(jì)算工作量，提高系統(tǒng)的速度。
指紋特征提取算法
|
圖2 指紋圖像及其特征
|
|
用計(jì)算機(jī)的語(yǔ)言完整地描述穩(wěn)定而又有區(qū)別的指紋特征是實(shí)現(xiàn)自動(dòng)指紋識(shí)別的一個(gè)關(guān)鍵問(wèn)題。選擇什么特征以及如何表示這種特征既關(guān)系指紋本身的特點(diǎn)，又和具體的指紋匹配算法緊密聯(lián)系，同時(shí)還要考慮所采用的指紋采集設(shè)備的特點(diǎn)。目前的自動(dòng)指紋識(shí)別系統(tǒng)普遍采用的指紋特征是細(xì)節(jié)點(diǎn)（minutiae），分為極限末梢和分叉點(diǎn)，見(jiàn)圖2。
指紋的特征可以反映給定的人類(lèi)群體里來(lái)自不同手指的指紋之間相似的程度。指紋的特征信息很多。這些所有的指紋特征信息構(gòu)成了龐大的指紋特征集合。那么，特征層需要研究和解決的問(wèn)題主要與這些特征信息有關(guān)，比如: “特征是否是終生不變的、惟一的”，“特征之間存在什么樣的相互關(guān)系”，“什么樣的特征子集可以使某種算法達(dá)到最佳的識(shí)別效果”，“指紋特征用于身份鑒別是否更安全”等等。一組好的特征不僅要能達(dá)到身份識(shí)別的基本要求，而且對(duì)噪聲、畸變和環(huán)境條件不敏感。
圍繞指紋特征展開(kāi)研究是伴隨著人們對(duì)指紋進(jìn)行身份鑒別的認(rèn)識(shí)而進(jìn)行的，如今已經(jīng)有很長(zhǎng)的歷史。1892年英國(guó)Sir Francis Galton對(duì)指紋進(jìn)行了系統(tǒng)研究，首次提出了指紋特征惟一性的問(wèn)題。隨著信息技術(shù)的發(fā)展，人們對(duì)身份認(rèn)證的準(zhǔn)確性要求明顯提高，同時(shí)也對(duì)指紋有效鑒定身份的能力產(chǎn)生質(zhì)疑。2002年1月，美國(guó)聯(lián)邦法官路易斯·波拉克做出的“憑借指紋鑒定不能定罪”的裁決促動(dòng)了針對(duì)指紋特征的兩個(gè)方面的研究工作: (1)在實(shí)踐中為指紋定出可以作為有效特征的標(biāo)準(zhǔn)，使得兩幅指紋是否相符不依賴(lài)于鑒定人員的主觀判斷; (2)研究指紋特征產(chǎn)生誤差的根源，從技術(shù)角度將出現(xiàn)的誤差量化。
指紋匹配
指紋匹配指的是通過(guò)對(duì)兩枚指紋特征集間的相似性比較，來(lái)判斷對(duì)應(yīng)的指紋圖像是否來(lái)自同一手指的過(guò)程，它是一種非常經(jīng)典而又亟待解決的模式識(shí)別問(wèn)題。
目前，指紋細(xì)節(jié)點(diǎn)匹配算法分類(lèi)有多種: 根據(jù)指紋識(shí)別的目的可以分為一比一匹配和一比N匹配; 根據(jù)操作過(guò)程的差異可分為自動(dòng)匹配 和人機(jī)交互匹配; 根據(jù)匹配適應(yīng)性可以分為彈性匹配和剛性匹配。根據(jù)指紋細(xì)節(jié)點(diǎn)定義和相似性判斷函數(shù)選取的不同，指紋匹配方法更是多種多樣的，比如基于奇異點(diǎn)的、基于三角形的、基于極坐標(biāo)變換的，基于動(dòng)態(tài)規(guī)劃的、基于圖匹配的等等方法，不勝枚舉。需要說(shuō)明的是這些分類(lèi)方法都難以囊括所有的指紋匹配算法，因?yàn)橥瑫r(shí)有很多算法彼此交叉。
需要指出的是，上述分類(lèi)方法并不是絕對(duì)的，各種方法是相互聯(lián)系的，每個(gè)算法都有自己的特點(diǎn)，并針對(duì)特殊的應(yīng)用。比如: 圖匹配的方法對(duì)質(zhì)量差指紋圖的噪聲抗干擾能力較好，但方法未經(jīng)大規(guī)模實(shí)驗(yàn)的證實(shí); 細(xì)節(jié)點(diǎn)匹配對(duì)質(zhì)量好的指紋圖像計(jì)算準(zhǔn)確，紋理特征的可區(qū)分性不強(qiáng); 基于紋理信息和串匹配的混合匹配方法在一定程度上提高了識(shí)別率，但是計(jì)算代價(jià)非常高; 基于三角匹配和動(dòng)態(tài)規(guī)劃的混合匹配方法可以解決非線性形變的問(wèn)題，但是提取的特征過(guò)大，難以滿(mǎn)足在線實(shí)用的要求。總而言之，指紋圖像的幾何影像形變及錯(cuò)位等問(wèn)題是匹配算法需要做的首要工作。因此，在指紋識(shí)別中必須考慮這些指紋圖像中可能存在的線性或非線性形變。目前已有的算法依賴(lài)一個(gè)前提條件: 待匹配的兩幅指紋圖像是使用相同配置、相同采集儀來(lái)采集的，即同模態(tài)，并且，這些指紋允許存在一定程度的噪聲。而匹配算法的最終目的是對(duì)給定的兩幅指紋，尋求使這兩幅圖像的灰度(或特征)相似度之間差異達(dá)到最小的方法。在這種情況下，主要的工作常常是對(duì)指紋形變問(wèn)題的研究，建立一個(gè)定義在有窮的形變參數(shù)空間的帶參數(shù)的形變變換模型，最后進(jìn)行形變參數(shù)最優(yōu)化處理。
指紋分類(lèi)與壓縮
識(shí)別一個(gè)人需要將他的指紋與數(shù)據(jù)庫(kù)中的所有指紋做比較。在某些民用或刑偵場(chǎng)合，數(shù)據(jù)庫(kù)可能非常大（比如幾百萬(wàn)枚指紋）。在這種情況下，識(shí)別就需要耗費(fèi)很長(zhǎng)的時(shí)間，這是無(wú)法接受的。這一識(shí)別過(guò)程可以通過(guò)減少必須執(zhí)行的匹配次數(shù)來(lái)提高速度。在某些情況下，如果加入諸如性別、種族、年齡等與個(gè)體有關(guān)的信息能顯著降低搜索數(shù)據(jù)庫(kù)的范圍，然而這些信息并不總是存在的，比如在犯罪現(xiàn)場(chǎng)的指紋。通常的策略是將指紋數(shù)據(jù)庫(kù)劃分成幾個(gè)子類(lèi)，這樣識(shí)別指紋時(shí)只需將此指紋與數(shù)據(jù)庫(kù)中同一類(lèi)的指紋做比較。
指紋分類(lèi)就是研究如何以穩(wěn)定而且可靠的方式將指紋劃為某一類(lèi)別。指紋匹配多根據(jù)指紋的局部特征（如細(xì)節(jié)點(diǎn)）來(lái)判別，而指紋分類(lèi)則根據(jù)指紋的全局特征（如全局脊線結(jié)構(gòu)、奇異點(diǎn)）來(lái)判別。由于各指紋模式具有較小的類(lèi)間差距和較大的類(lèi)內(nèi)差距，指紋分類(lèi)是一個(gè)非常難的模式識(shí)別問(wèn)題。指紋圖像通常還有噪聲，這使得分類(lèi)任務(wù)更加困難，因此指紋分類(lèi)問(wèn)題一直是模式識(shí)別領(lǐng)域中的難點(diǎn)問(wèn)題，一直以來(lái)也吸引了科研人員的極大興趣。
指紋壓縮技術(shù)也是自動(dòng)指紋識(shí)別系統(tǒng)中的一項(xiàng)重要技術(shù)，在大容量的指紋庫(kù)中，為了節(jié)省存儲(chǔ)空間必須對(duì)指紋圖進(jìn)行壓縮存儲(chǔ)，使用時(shí)再進(jìn)行解壓縮。圖像壓縮編碼的目的是以盡量少的比特?cái)?shù)表示圖像，同時(shí)保持復(fù)原圖像的質(zhì)量，使它符合預(yù)定應(yīng)用場(chǎng)合的要求。基于小波的指紋壓縮算法，是目前技術(shù)較成熟、應(yīng)用較廣泛的指紋圖像壓縮算法。