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