??? 摘 要： 一種針對活體指紋采集樣本的分類算法" title="分類算法">分類算法。將指紋分為四類：弓形、左箕形、右箕形和斗形，并對斗形指紋給出了可用于進一步檢索的參數及計算方法。由于活體指紋的采集方法的限制，指紋的三角點有可能采集不到。該算法消除了傳統指紋分類算法過分依賴三角點的缺陷，耗時短，滿足實時系統的需求。利用該方法對2150個指紋進行分類，準確率達97.1％。
??? 關鍵詞： 指紋分類? 奇異點? 方向濾波? 連續分類
?
??? 目前指紋分類的研究對象主要是油墨指紋等滾動按捺得到的指紋圖像" title="指紋圖像">指紋圖像，一般采用美國中央情報局的NIST4、NIST9、NIST14、NIST24等指紋數據庫，這些指紋圖像通常保留了三角點和中心點" title="中心點">中心點等特征點。但活體采集通常不能完整采集三角點。活體采集的樣本與傳統油墨按捺采集的樣本有很大不同。從目前所能查閱的國內外文獻來看，針對活體采集樣本的分類算法研究并不多見[3～5]，而且效果并不是很理想。本文所研究的指紋庫是用主流芯片級指紋采集器" title="采集器">采集器——富士通公司的BMF200電容式的指紋傳感器采集得到的。這款采集器在自動指紋識別系統中得到廣泛應用。因此，針對這種樣本數據庫的分類算法的研究具有現實意義和理論意義。
??? 傳統的分類算法沿用指紋學上的分類法，把指紋分為五類：弓形(Arch)、帳弓形（Tent Arch）、左箕形（Left loop）、右箕形（Right loop）和斗形（Whorl）。根據公安部的統計，中國人指紋類型的分布，弓形和帳弓形分別為1.1％、1.4％。對于實際系統，把兩者分離的必要性不大。而且，弓形和帳弓形在結構上很相似，沒有明顯的特征可以把兩者很好地分開。文獻[2]的實驗表明：不把這兩類分開，可以在不影響分類器效率的情況下，提高正確率。本文采用指紋的結構特征分析方法，基于實用性的考慮，把采集的指紋分為四類：弓形(Arch)、左箕形（Left loop）、右箕形（Right loop）和斗形（Whorl）。如圖1所示。
?
1 指紋分類算法
??? 分類算法的基本步驟是：
??? （1）圖像預處理：為使指紋圖像有相同的均值和方差，對原始圖像進行歸一化處理，然后根據圖像灰度信息對圖像分割，把背景區分割出來；
??? （2）計算方向圖" title="方向圖">方向圖：計算指紋圖像每一點的方向；
??? （3）提取特征：根據方向圖，找出指紋的奇異點；
??? （4）分類：根據中心點數目和指紋特定區域的流向把指紋分為四類。
??? 程序流程圖如圖2。
?
1.1 圖像預處理
??? 預處理包括歸一化、背景分割。歸一化就是把原始圖像的灰度均值和方差變換為期望得到的均值和方差。
??? 歸一化后，對圖像進行分割，利用灰度信息把指紋區和背景區分開。
??? 圖3是一幅指紋圖像的分割結果。
?
1.2 方向圖的計算與平滑
??? 輸入的指紋圖像大小為240×264，分成8×8的小塊。首先計算每一點的方向，把平面空間量化成8個方向碼，通過式（1）計算每一點的方向。
??? 
??? 其中：D(i,j)表示點(i,j)的方向碼；N這里取值為8。G(i,j)表示點(i,j)的灰度值；w表示以點(i,j)中心，在方向為d的直線上，每一邊的點數。G(ik,jk)d表示d方向的直線上所取像素點的灰度值。點的方向碼的計算解釋如下：在某一個點較小的范圍內，紋線上的點的灰度值相差不大，而紋線上與非紋線的點的灰度值相差較大。因此沿著紋線計算的差的絕對值之和較小，而沿著其他方向計算出的差的絕對值之和則較大。
??? 為了保證方向圖的抗干擾能力，可在塊劃分不變的情況下，適當擴展方向碼的統計區域。塊的劃分尺寸為8×8，而統計該區域的方向碼時，則按照12×12的擴展區域。統計每一小塊對應區域中每一個方向碼的像素點數，像素點數最多的方向碼就是該小塊的主方向。
??? 為了消除局部的方向圖計算誤差，對方向圖進行平滑。平滑方式采用3×3均值濾波器實現平滑濾波[6]。圖4給出了濾波前后的方向圖。
?
1.3? 奇異點尋找與修正
??? 進行指紋分類前，先將指紋的特征點找出來。對指紋分類有用的是指紋的奇異點：中心點（core）和三角點（delta）。文獻[1]中介紹了判定中心點和三角點的方法。在中心點沿著逆時針方向一周的角度變化量（不大于90度）為180度，在三角點沿著逆時針方向一周的角度變化量（不大于90度）為-180度。
??? 在實際計算時，由于方向圖的劃分、干擾的存在，根據上述判據找到的中心點和三角點有可能是偽奇異點，需要根據實際情況作一些修正，刪除偽奇異點。修正奇異點的準則如下：
??? （1）如果指紋紋線在局部變化較大，就有可能出現相鄰兩個小塊的方向互相垂直，這可能使中心點和三角點重合。這種情況都發生在中心區域而不是三角區域，所以需要刪除與中心點重合的三角點。
??? （2）指紋圖像的邊緣區域噪聲較大，容易出現偽奇異點，所以在計算出的奇異點的一個適當的鄰域內如果有背景區，則刪除該奇異點。
??? （3）由于噪聲的影響，或是手指上有較大的皺紋，會使計算出的奇異點中出現相鄰很近的中心點和三角點，這些都是偽奇異點。所以，如果存在一個中心點和一個三角點距離小于設定的閾值，則刪除這兩個點，并進一步刪除與這兩個點距離小于閾值的其它奇異點；
??? （4）對于指紋紋線在特征區域變化較大的情況，有可能在一個特征區域找出多于一個的奇異點。所以，在經過上述三步偽奇異點的刪除后，使用聚類分析方法，把余下的中心點和三角點分成幾個聚類，每一個聚類的中心就是最后得到的奇異點。
??? 圖5給出了一幅質量較差的指紋圖像奇異點修正前和修正后的情況。
?
??? 本文根據中心點數目組織分類判據將指紋分為三類：0個中心點為弓形， 2個中心點為斗形，1個中心點為左箕形或右箕形。需要根據實際情況對此判據作進一步修正和改進。當中心點個數為1，存在三角點。如果三角點與中心點的距離小于一個閾值，則該指紋為弓形。
1.4 左箕、右箕的區分
??? 對于中心點個數為1的指紋，可以根據中心點下方指紋紋線的流轉方向進一步把指紋分成左箕形、右箕形。左箕形指紋紋線流向左方，右箕形流向右方。
??? 對中心點下方一定角度的區域進行90°的方向濾波，可以通過方向碼之間的計算近似實現方向濾波：
??? 
??? P是濾波值，N是該區域小塊的個數，pi是每一小塊的濾波值，Di是小塊的方向碼，D0是濾波方向，在這里D0＝4（90°）。不考慮與D0垂直的方向碼。
??? P為負是左箕形，否則為右箕形。
??? 圖6給出了兩種類形特征區域內指紋紋線的流向。
?
1.5 斗形的索引參數計算
??? 斗形指紋在漢族人中所占比例很大，大約在一半左右。因此有必要對斗形指紋進行細分。實際情況中,很難從結構特征把斗形分成幾個可以互相分得開的子類。本文以斗形的長短軸之比Flatness作為斗形的數據庫索引參數，對斗形進行連續分類。
分別以8個方向碼為坐標軸，將指紋方向圖在兩個垂直的方向投影，計算投影比。取最大的投影比為Flatness，作為索引參數。
??? 對斗形指紋，利用其長短軸之比，作為斗形指紋的索引，在數據庫中查找，是連續分類思想在斗形指紋進一步分類上的體現。文獻[7]提出了不同于傳統的明確的排他性分類（exclusive classification）的連續分類（continuous classification）概念。通過一定的特征提取方法，得到一個特征向量，然后把這個特征向量當作索引（a access key）。對于一個給定的容差ρ，在特征空間里，以待查樣本為中心，以ρ為半徑的超球作為待查樣本的搜索域。實際上，存在大量無法歸入既定類別的雜形指紋，和可以同時歸入一個以上類別、連指紋專家都無法確定其類別的模棱兩可的指紋，這都影響了傳統排他性分類算法的正確率。而對于連續分類，則不存在這種干擾。不過文獻[7]提出的分類算法主要是針對油墨滾動按捺的指紋圖像，而且有很大的算法復雜性，不適于實時系統。本文對斗形索引參數的計算，是連續分類思想在研究實時系統算法上的一個嘗試。
??? 圖7是方向碼為0，3的兩個坐標的示意圖。
?
??? 圖8是900個斗形指紋樣本的參數Flatness的分布圖。由圖8可以看出，應用斗形指紋的長短軸之比Flatness，可以把斗形指紋很好地排列開來。
?
2 實驗結果
??? 利用本算法對2150個指紋采集樣本進行實驗，這些樣本來自215個手指，每個手指采集10次。分錯樣本63個，分類準確率達97.1％。具體結果見表1。
?
??? 對910個斗形指紋計算長短軸之比，結果在1.0和2.8之間，每個手指紋在10次采樣的長短軸之比相差一般不超過0.5。說明該參數可以用作斗形指紋的特征參數。
??? 由于采集器的面積小，手指也不是滾動按捺，所以采集樣本與傳統的油墨按捺有很大不同，在算法、方向圖的計算、奇異點的修正和分類方法上都做了很大的改進。本文提出的算法計算量小，在CPU Pentium III 550MHz，內存288MB，處理一幅指紋圖像平均為0.26s，其中0.2s花費在對指紋圖像每一點的方向的計算上。這也是指紋識別的必需步驟。所以該算法對于自動指紋識別系統所引起的額外時間開銷很小，滿足實用的實時系統的要求。
??? 另外，由于指紋分類所依據的是指紋的宏觀特征，由于采集器面積小，這對分類帶來一定的難度，更加有效的分類算法有必要進一步研究。
參考文獻
1 M. Kawagoe, A. Tojo. Fingerprint Pattern Classification[J].?Pattern Recognition,1984；17（3）：295～303
2 Jain,A K, Prabhakar, S, Lin Hong. A multichannel approach to fingerprint classification[J]. Pattern Analysis and Machine?Intelligence. IEEE Transactions on,1999；21（4）：348～359
3 Byoung-Ho Cho, Jeung-Seop Kim, Jae-Hyung Bae, et al.?Fingerprint image classification by core analysis[J]. Signal?Processing Proceedings, 2000. WCCC-ICSP 2000. 5th International Conference on, 2000;3：1534～1537
4 Byoung-Ho Cho, Jeung-Seop Kim, Jae-Hyung Bae, et al.?Core-based fingerprint image classification[J].Pattern Recognition, 2000. Proceedings. 15th International Conference on,2000;2：859～862
5 Sen Wang, Wei Wei Zhang, Yang Sheng Wang. Fingerprint?classification by directional fields[J]. Multimodal Interfaces.?Proceedings. Fourth IEEE International Conference on, 2002：395～399
6 肖立宏. CMOS指紋采集器設計及活體指紋分類算法研究[D]. 清華大學碩士學位論文，2002