??? 摘 要： 一種針對(duì)活體指紋采集樣本的分類算法" title="分類算法">分類算法。將指紋分為四類：弓形、左箕形、右箕形和斗形，并對(duì)斗形指紋給出了可用于進(jìn)一步檢索的參數(shù)及計(jì)算方法。由于活體指紋的采集方法的限制，指紋的三角點(diǎn)有可能采集不到。該算法消除了傳統(tǒng)指紋分類算法過(guò)分依賴三角點(diǎn)的缺陷，耗時(shí)短，滿足實(shí)時(shí)系統(tǒng)的需求。利用該方法對(duì)2150個(gè)指紋進(jìn)行分類，準(zhǔn)確率達(dá)97.1％。
??? 關(guān)鍵詞： 指紋分類? 奇異點(diǎn)? 方向?yàn)V波? 連續(xù)分類
?
??? 目前指紋分類的研究對(duì)象主要是油墨指紋等滾動(dòng)按捺得到的指紋圖像" title="指紋圖像">指紋圖像，一般采用美國(guó)中央情報(bào)局的NIST4、NIST9、NIST14、NIST24等指紋數(shù)據(jù)庫(kù)，這些指紋圖像通常保留了三角點(diǎn)和中心點(diǎn)" title="中心點(diǎn)">中心點(diǎn)等特征點(diǎn)。但活體采集通常不能完整采集三角點(diǎn)?；铙w采集的樣本與傳統(tǒng)油墨按捺采集的樣本有很大不同。從目前所能查閱的國(guó)內(nèi)外文獻(xiàn)來(lái)看，針對(duì)活體采集樣本的分類算法研究并不多見[3～5]，而且效果并不是很理想。本文所研究的指紋庫(kù)是用主流芯片級(jí)指紋采集器" title="采集器">采集器——富士通公司的BMF200電容式的指紋傳感器采集得到的。這款采集器在自動(dòng)指紋識(shí)別系統(tǒng)中得到廣泛應(yīng)用。因此，針對(duì)這種樣本數(shù)據(jù)庫(kù)的分類算法的研究具有現(xiàn)實(shí)意義和理論意義。
??? 傳統(tǒng)的分類算法沿用指紋學(xué)上的分類法，把指紋分為五類：弓形(Arch)、帳弓形（Tent Arch）、左箕形（Left loop）、右箕形（Right loop）和斗形（Whorl）。根據(jù)公安部的統(tǒng)計(jì)，中國(guó)人指紋類型的分布，弓形和帳弓形分別為1.1％、1.4％。對(duì)于實(shí)際系統(tǒng)，把兩者分離的必要性不大。而且，弓形和帳弓形在結(jié)構(gòu)上很相似，沒(méi)有明顯的特征可以把兩者很好地分開。文獻(xiàn)[2]的實(shí)驗(yàn)表明：不把這兩類分開，可以在不影響分類器效率的情況下，提高正確率。本文采用指紋的結(jié)構(gòu)特征分析方法，基于實(shí)用性的考慮，把采集的指紋分為四類：弓形(Arch)、左箕形（Left loop）、右箕形（Right loop）和斗形（Whorl）。如圖1所示。
?
1 指紋分類算法
??? 分類算法的基本步驟是：
??? （1）圖像預(yù)處理：為使指紋圖像有相同的均值和方差，對(duì)原始圖像進(jìn)行歸一化處理，然后根據(jù)圖像灰度信息對(duì)圖像分割，把背景區(qū)分割出來(lái)；
??? （2）計(jì)算方向圖" title="方向圖">方向圖：計(jì)算指紋圖像每一點(diǎn)的方向；
??? （3）提取特征：根據(jù)方向圖，找出指紋的奇異點(diǎn)；
??? （4）分類：根據(jù)中心點(diǎn)數(shù)目和指紋特定區(qū)域的流向把指紋分為四類。
??? 程序流程圖如圖2。
?
1.1 圖像預(yù)處理
??? 預(yù)處理包括歸一化、背景分割。歸一化就是把原始圖像的灰度均值和方差變換為期望得到的均值和方差。
??? 歸一化后，對(duì)圖像進(jìn)行分割，利用灰度信息把指紋區(qū)和背景區(qū)分開。
??? 圖3是一幅指紋圖像的分割結(jié)果。
?
1.2 方向圖的計(jì)算與平滑
??? 輸入的指紋圖像大小為240×264，分成8×8的小塊。首先計(jì)算每一點(diǎn)的方向，把平面空間量化成8個(gè)方向碼，通過(guò)式（1）計(jì)算每一點(diǎn)的方向。
??? 
??? 其中：D(i,j)表示點(diǎn)(i,j)的方向碼；N這里取值為8。G(i,j)表示點(diǎn)(i,j)的灰度值；w表示以點(diǎn)(i,j)中心，在方向?yàn)閐的直線上，每一邊的點(diǎn)數(shù)。G(ik,jk)d表示d方向的直線上所取像素點(diǎn)的灰度值。點(diǎn)的方向碼的計(jì)算解釋如下：在某一個(gè)點(diǎn)較小的范圍內(nèi)，紋線上的點(diǎn)的灰度值相差不大，而紋線上與非紋線的點(diǎn)的灰度值相差較大。因此沿著紋線計(jì)算的差的絕對(duì)值之和較小，而沿著其他方向計(jì)算出的差的絕對(duì)值之和則較大。
??? 為了保證方向圖的抗干擾能力，可在塊劃分不變的情況下，適當(dāng)擴(kuò)展方向碼的統(tǒng)計(jì)區(qū)域。塊的劃分尺寸為8×8，而統(tǒng)計(jì)該區(qū)域的方向碼時(shí)，則按照12×12的擴(kuò)展區(qū)域。統(tǒng)計(jì)每一小塊對(duì)應(yīng)區(qū)域中每一個(gè)方向碼的像素點(diǎn)數(shù)，像素點(diǎn)數(shù)最多的方向碼就是該小塊的主方向。
??? 為了消除局部的方向圖計(jì)算誤差，對(duì)方向圖進(jìn)行平滑。平滑方式采用3×3均值濾波器實(shí)現(xiàn)平滑濾波[6]。圖4給出了濾波前后的方向圖。
?
1.3? 奇異點(diǎn)尋找與修正
??? 進(jìn)行指紋分類前，先將指紋的特征點(diǎn)找出來(lái)。對(duì)指紋分類有用的是指紋的奇異點(diǎn)：中心點(diǎn)（core）和三角點(diǎn)（delta）。文獻(xiàn)[1]中介紹了判定中心點(diǎn)和三角點(diǎn)的方法。在中心點(diǎn)沿著逆時(shí)針?lè)较蛞恢艿慕嵌茸兓浚ú淮笥?0度）為180度，在三角點(diǎn)沿著逆時(shí)針?lè)较蛞恢艿慕嵌茸兓浚ú淮笥?0度）為-180度。
??? 在實(shí)際計(jì)算時(shí)，由于方向圖的劃分、干擾的存在，根據(jù)上述判據(jù)找到的中心點(diǎn)和三角點(diǎn)有可能是偽奇異點(diǎn)，需要根據(jù)實(shí)際情況作一些修正，刪除偽奇異點(diǎn)。修正奇異點(diǎn)的準(zhǔn)則如下：
??? （1）如果指紋紋線在局部變化較大，就有可能出現(xiàn)相鄰兩個(gè)小塊的方向互相垂直，這可能使中心點(diǎn)和三角點(diǎn)重合。這種情況都發(fā)生在中心區(qū)域而不是三角區(qū)域，所以需要?jiǎng)h除與中心點(diǎn)重合的三角點(diǎn)。
??? （2）指紋圖像的邊緣區(qū)域噪聲較大，容易出現(xiàn)偽奇異點(diǎn)，所以在計(jì)算出的奇異點(diǎn)的一個(gè)適當(dāng)?shù)泥徲騼?nèi)如果有背景區(qū)，則刪除該奇異點(diǎn)。
??? （3）由于噪聲的影響，或是手指上有較大的皺紋，會(huì)使計(jì)算出的奇異點(diǎn)中出現(xiàn)相鄰很近的中心點(diǎn)和三角點(diǎn)，這些都是偽奇異點(diǎn)。所以，如果存在一個(gè)中心點(diǎn)和一個(gè)三角點(diǎn)距離小于設(shè)定的閾值，則刪除這兩個(gè)點(diǎn)，并進(jìn)一步刪除與這兩個(gè)點(diǎn)距離小于閾值的其它奇異點(diǎn)；
??? （4）對(duì)于指紋紋線在特征區(qū)域變化較大的情況，有可能在一個(gè)特征區(qū)域找出多于一個(gè)的奇異點(diǎn)。所以，在經(jīng)過(guò)上述三步偽奇異點(diǎn)的刪除后，使用聚類分析方法，把余下的中心點(diǎn)和三角點(diǎn)分成幾個(gè)聚類，每一個(gè)聚類的中心就是最后得到的奇異點(diǎn)。
??? 圖5給出了一幅質(zhì)量較差的指紋圖像奇異點(diǎn)修正前和修正后的情況。
?
??? 本文根據(jù)中心點(diǎn)數(shù)目組織分類判據(jù)將指紋分為三類：0個(gè)中心點(diǎn)為弓形， 2個(gè)中心點(diǎn)為斗形，1個(gè)中心點(diǎn)為左箕形或右箕形。需要根據(jù)實(shí)際情況對(duì)此判據(jù)作進(jìn)一步修正和改進(jìn)。當(dāng)中心點(diǎn)個(gè)數(shù)為1，存在三角點(diǎn)。如果三角點(diǎn)與中心點(diǎn)的距離小于一個(gè)閾值，則該指紋為弓形。
1.4 左箕、右箕的區(qū)分
??? 對(duì)于中心點(diǎn)個(gè)數(shù)為1的指紋，可以根據(jù)中心點(diǎn)下方指紋紋線的流轉(zhuǎn)方向進(jìn)一步把指紋分成左箕形、右箕形。左箕形指紋紋線流向左方，右箕形流向右方。
??? 對(duì)中心點(diǎn)下方一定角度的區(qū)域進(jìn)行90°的方向?yàn)V波，可以通過(guò)方向碼之間的計(jì)算近似實(shí)現(xiàn)方向?yàn)V波：
??? 
??? P是濾波值，N是該區(qū)域小塊的個(gè)數(shù)，pi是每一小塊的濾波值，Di是小塊的方向碼，D0是濾波方向，在這里D0＝4（90°）。不考慮與D0垂直的方向碼。
??? P為負(fù)是左箕形，否則為右箕形。
??? 圖6給出了兩種類形特征區(qū)域內(nèi)指紋紋線的流向。
?
1.5 斗形的索引參數(shù)計(jì)算
??? 斗形指紋在漢族人中所占比例很大，大約在一半左右。因此有必要對(duì)斗形指紋進(jìn)行細(xì)分。實(shí)際情況中,很難從結(jié)構(gòu)特征把斗形分成幾個(gè)可以互相分得開的子類。本文以斗形的長(zhǎng)短軸之比Flatness作為斗形的數(shù)據(jù)庫(kù)索引參數(shù)，對(duì)斗形進(jìn)行連續(xù)分類。
分別以8個(gè)方向碼為坐標(biāo)軸，將指紋方向圖在兩個(gè)垂直的方向投影，計(jì)算投影比。取最大的投影比為Flatness，作為索引參數(shù)。
??? 對(duì)斗形指紋，利用其長(zhǎng)短軸之比，作為斗形指紋的索引，在數(shù)據(jù)庫(kù)中查找，是連續(xù)分類思想在斗形指紋進(jìn)一步分類上的體現(xiàn)。文獻(xiàn)[7]提出了不同于傳統(tǒng)的明確的排他性分類（exclusive classification）的連續(xù)分類（continuous classification）概念。通過(guò)一定的特征提取方法，得到一個(gè)特征向量，然后把這個(gè)特征向量當(dāng)作索引（a access key）。對(duì)于一個(gè)給定的容差ρ，在特征空間里，以待查樣本為中心，以ρ為半徑的超球作為待查樣本的搜索域。實(shí)際上，存在大量無(wú)法歸入既定類別的雜形指紋，和可以同時(shí)歸入一個(gè)以上類別、連指紋專家都無(wú)法確定其類別的模棱兩可的指紋，這都影響了傳統(tǒng)排他性分類算法的正確率。而對(duì)于連續(xù)分類，則不存在這種干擾。不過(guò)文獻(xiàn)[7]提出的分類算法主要是針對(duì)油墨滾動(dòng)按捺的指紋圖像，而且有很大的算法復(fù)雜性，不適于實(shí)時(shí)系統(tǒng)。本文對(duì)斗形索引參數(shù)的計(jì)算，是連續(xù)分類思想在研究實(shí)時(shí)系統(tǒng)算法上的一個(gè)嘗試。
??? 圖7是方向碼為0，3的兩個(gè)坐標(biāo)的示意圖。
?
??? 圖8是900個(gè)斗形指紋樣本的參數(shù)Flatness的分布圖。由圖8可以看出，應(yīng)用斗形指紋的長(zhǎng)短軸之比Flatness，可以把斗形指紋很好地排列開來(lái)。
?
2 實(shí)驗(yàn)結(jié)果
??? 利用本算法對(duì)2150個(gè)指紋采集樣本進(jìn)行實(shí)驗(yàn)，這些樣本來(lái)自215個(gè)手指，每個(gè)手指采集10次。分錯(cuò)樣本63個(gè)，分類準(zhǔn)確率達(dá)97.1％。具體結(jié)果見表1。
?
??? 對(duì)910個(gè)斗形指紋計(jì)算長(zhǎng)短軸之比，結(jié)果在1.0和2.8之間，每個(gè)手指紋在10次采樣的長(zhǎng)短軸之比相差一般不超過(guò)0.5。說(shuō)明該參數(shù)可以用作斗形指紋的特征參數(shù)。
??? 由于采集器的面積小，手指也不是滾動(dòng)按捺，所以采集樣本與傳統(tǒng)的油墨按捺有很大不同，在算法、方向圖的計(jì)算、奇異點(diǎn)的修正和分類方法上都做了很大的改進(jìn)。本文提出的算法計(jì)算量小，在CPU Pentium III 550MHz，內(nèi)存288MB，處理一幅指紋圖像平均為0.26s，其中0.2s花費(fèi)在對(duì)指紋圖像每一點(diǎn)的方向的計(jì)算上。這也是指紋識(shí)別的必需步驟。所以該算法對(duì)于自動(dòng)指紋識(shí)別系統(tǒng)所引起的額外時(shí)間開銷很小，滿足實(shí)用的實(shí)時(shí)系統(tǒng)的要求。
??? 另外，由于指紋分類所依據(jù)的是指紋的宏觀特征，由于采集器面積小，這對(duì)分類帶來(lái)一定的難度，更加有效的分類算法有必要進(jìn)一步研究。
參考文獻(xiàn)
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指紋采集器設(shè)計(jì)及活體指紋分類算法研究[D]. 清華大學(xué)碩士學(xué)位論文，2002