摘 要： 利用SVM(Support Vector Machine)解決二類分類問題的優(yōu)勢，設(shè)計了一個粗細兩級指紋分類體器，提出并實現(xiàn)了一種新型的指紋分類算法" title="分類算法">分類算法。測試結(jié)果表明，該分類器" title="分類器">分類器具有很好的泛化能力，對于新樣本分類的正確率達98.5%,具有一定的實用價值。
關(guān)鍵詞： 指紋分類 分類器 特征提取" title="特征提取">特征提取 支持向量機
指紋作為個人身份的標志具有唯一性和終生不變性。隨著計算機技術(shù)的發(fā)展，指紋識別技術(shù)成為目前使用最廣泛的生物識別技術(shù)。一個典型的自動指紋識別系統(tǒng)通常包括五部分：采樣、預(yù)處理、特征提取、分類和細節(jié)匹配。指紋分類環(huán)節(jié)對于分解整個復(fù)雜的識別任務(wù)、縮小細節(jié)匹配的范圍和提高識別的效率都具有非常重要的意義。分類算法取決于特征提取環(huán)節(jié),大致分為以下五種：
·語法分析法(Syntactic Approach)[1～2]；
·幾何法(Geometry Approach)[3]；
·隨機法(Stochastic Approach)[4]；
·神經(jīng)網(wǎng)絡(luò)法(Neural Network Approach)[5～6]；
·基于奇異點的分類法(Singularity－based Approach)[7～9]。
神經(jīng)網(wǎng)絡(luò)方法在指紋識別技術(shù)中應(yīng)用較為廣泛,但是由于理論本身存在缺陷，神經(jīng)網(wǎng)絡(luò)法容易陷入局部最優(yōu)和過學(xué)習(xí)。本文算法的理論基礎(chǔ)——SVM方法擁有嚴密的數(shù)學(xué)解釋，因此，與神經(jīng)網(wǎng)絡(luò)方法相比推廣能力大大提高。
目前，SVM理論在指紋分類中的應(yīng)用并不多：王崇文等人提出了一種基于隱馬爾可夫模型和支持向量機" title="支持向量機">支持向量機的兩級分類方法[10]；Shesha Shah等人利用五個SVM分類器將指紋分成了五類[11]，其中分類的原則是反饋型線檢測器的特征提取。該算法中普通弓形和帳弓形的指紋對于新樣本的范化能力不理想，正確率只有79.10%。本文設(shè)計的基于支持向量機理論粗細二級分類，使用五個SVM分類器，充分利用它們進行二類分類的優(yōu)勢，將指紋分為六類。本算法對于新樣本的范化能力有明顯提高，其中弓形分類的正確率可以達到96.7%。本文從四個方面闡述基于支持向量機理論的二級指紋分類算法。SVM這一新的理論不僅為將來指紋分類工作的研究提供了堅實的理論基礎(chǔ)，而且給算法的簡化和不斷完善開拓了嶄新的思路。
1 支持向量機理論
支持向量機是貝爾實驗室研究人員V. Vapnik 等人在對統(tǒng)計學(xué)習(xí)理論多年的研究基礎(chǔ)上發(fā)展起來的一種全新的機器學(xué)習(xí)算法[12～14]。機器學(xué)習(xí)的實際風(fēng)險由兩部分構(gòu)成：經(jīng)驗風(fēng)險和置信范圍，其中后者與Vapnik提出的VC維的概念有關(guān)。傳統(tǒng)的使用經(jīng)驗風(fēng)險最小化ERM(Empirical Risk Minimization)的分類訓(xùn)練方法，雖然能取得小的經(jīng)驗風(fēng)險，但置信范圍很大，導(dǎo)致過學(xué)習(xí)，推廣能力下降。SVM方法建立在統(tǒng)計學(xué)習(xí)的VC 維(Vapnik-Chervonenkis Dimension)理論和結(jié)構(gòu)風(fēng)險最小化原理SRM(Structural Risk Minimization)基礎(chǔ)上，兼顧了兩部分風(fēng)險構(gòu)成，把函數(shù)構(gòu)造為一個函數(shù)子集序列，在子集間折衷考慮經(jīng)驗風(fēng)險和置信范圍，可以使實際風(fēng)險最小。
本文設(shè)計的粗細二級分類使用五個SVM分類器，其中兩個將指紋粗分為三類，另外三個將指紋細分為六類，SVM分類器解決的都是二類分類問題。
2 算法實現(xiàn)步驟
2.1特征提取
指紋圖像通過預(yù)處理后，已經(jīng)是二值化和細化后的圖像，見圖1。
要分析指紋圖像，首先需進行特征提取。本文采用基于奇異點的特征提取。指紋的特征分為兩種：全局特征和局部細節(jié)特征[15]。前者用于指紋分類，后者用于細節(jié)匹配。全局特征點即奇異點包括：三角點(delta) 和核心點(core),見圖2。三角點位于從核心點兩個方向差別較大的紋路的匯聚處；核心點位于指紋紋路的漸進中心，它是指紋中心脊線上曲率最大的點。
2.2 根據(jù)特征提取設(shè)計分類器
指紋通常可以分成五類：斗型、右旋、左旋、拱形和帳篷形[13]。為了更好地發(fā)揮SVM算法解決二類分類問題的優(yōu)勢，本文設(shè)計了一個兩級分類器，結(jié)構(gòu)框架見圖3。分類器包括粗分類和細分類兩級。第一級將指紋粗分為：斗形(Whorl)、旋形(Loop)和弓形(Arch)三類；第二級,弓形細分為普通弓形(Normal Arch)和帳弓形(Tented Arch)，旋形細分為左旋(Left Loop)和右旋(Right Loop)，斗形細分為單斗(Single Whorl)和雙斗(Twins Whorl)。
2.3 分類判別準則
第一級粗分類遵循如下原則：
·分離斗形，分類準則：核心點的個數(shù)(只有斗形的核心點是兩個)；
·區(qū)分旋形和弓形，分類準則：兩者雖然擁有同樣的奇異點(一個核心點和一個三角點)，奇異點的連線相對于圖像參考軸的夾角不同。
第二級細分類均為二類分類問題。細分依據(jù)分別為： ·斗形：兩核心點的連線與圖像參考軸的相對位置；
·旋形：核心點和三角點連線與圖像參考軸的夾角；
·弓形：核心點的數(shù)目。
2.4 SVM分類器
根據(jù)兩級分類的判別標準決定SVM的n維輸入向量X(x1,x2,…，xn)的維數(shù)，訓(xùn)練樣本(x1,y1),…，(xn,yn),x∈Rn,y∈{+1,-1}服從某個未知的概率分布，通過對樣本歸一化，求解最優(yōu)的分類超平面：
yi(xi·W+b)-1≥0????????????????????? (1)
并且使分類間隔1W最大，從而將兩類樣本無誤地分開。這是一個線性約束的二次規(guī)劃問題，利用Lagrange函數(shù)：
解出支持向量α，再將
帶入(1)式，確定最優(yōu)超平面，將兩類正確地分開。以旋形的細分類為例，首先根據(jù)分類的判別準則確定輸入向量的維數(shù)，這里輸入向量X是三維,包括三角點相對橫坐標x1、相對縱坐標x2、三角點和核心點連線與圖像參考軸的夾角x3，即X(x1,x2,x3)，然后根據(jù)上述公式求解出支持向量α，最終確定將左旋和右旋正確分開的超平面。
3 實驗結(jié)果
實驗使用了FVC2004的指紋數(shù)據(jù)庫和晶體2100型指紋采集儀，抽取不同數(shù)目的指紋作為訓(xùn)練樣本，使用Microsoft Visual Studio.Net2003編程實現(xiàn)了使用SVM方法的二級指紋分類。選取的樣本容量以及分類正確率，見表1。對于新樣本SVM方法表現(xiàn)出了很好的泛化能力，分類判別的正確率大大提高，而且由于實現(xiàn)的是二級粗細分類，需要進行判斷樣本的數(shù)目分流，加快了分類的速度。通過驗證不同容量的訓(xùn)練樣本可以得出結(jié)論，SVM方法在解決二類分類問題上的確有優(yōu)于其他算法之處。
SVM方法不但能提高分類的速率，而且不限制模型的選擇。SVM有三種不同的內(nèi)核函數(shù)" title="核函數(shù)">核函數(shù)：(1)多項式核函數(shù)(polynomial)：K(x,xi)=[(x·xi)+1]q；(2)徑向基函數(shù)(Radial Basis Function)：K(x,xi)=exp
；(3)Sigmoid函數(shù)：K(x,xi)=tanh(v(x·xi)+c)。實驗使用三種核函數(shù)的模型對弓形進行細分類，訓(xùn)練樣本容量選取100，數(shù)據(jù)見表2，其中統(tǒng)計了兩類的支持向量的數(shù)目分別用Positive_SVM和Negative_SVM表示。
實驗結(jié)果表明，核函數(shù)的選取對分類的效果影響甚小，因此算法在模型的選擇上具有很大的靈活性。
實驗表明，將支持向量機理論應(yīng)用于指紋分類是可行的，而且對于提高指紋分類算法的效率有不可或缺的作用。SVM方法基于嚴密的數(shù)學(xué)理論，遵循SRM原則尋找最優(yōu)超平面。本文設(shè)計的粗細二級分類器,將指紋先后分成了三類和六類，充分發(fā)揮了SVM理論解決二類分類問題的優(yōu)勢，通過編程實現(xiàn)，訓(xùn)練樣本具有較好的泛化能力。與神經(jīng)網(wǎng)絡(luò)方法相比，本文提出的算法無論是在理論基礎(chǔ)方面還是在模型選擇的靈活性方面都表現(xiàn)出了極大的優(yōu)越性。
參考文獻
1 B Moayer, K S Fu. A syntactic approach to fingerprint pat-tern recognition [J]. Pattern Recognition, 1975;7(5):1～23
2 K Rao, K Balck. Typeclassification of fingerprints:a syntactic approach [J]. IEEE Trans. Pattem Anal. and Machine Intell,1980;2(3):223～231
3 M M Chong. Geometric framework for fingerprint image clas-sification [J]. Pattern Recognition, 1997;30(9):1475～1488
4 T K Moon，W C Stirling. Mathematical methods and algorithms for signal processing [Z].Upper Sadle River:Prentice Hall, 1999
5 Hugo Vieira Neto, Dibio Leandro Borges. Fingerprint Classi-fication with Neural Networks. IEEE,1997:66～72
6 蔡 俊,任德官. 基于BP神經(jīng)網(wǎng)絡(luò)的指紋模板分類器分類算法[J]. 微電子學(xué)與計算機, 2002;(9):1～3
7 Leong Chung Ern. Fingerprint Classification Approaches: an Overview. ISSPA, IEEE, 2001:347～350
8 R appelli, A Lumini. Fingerprint classification by directional image partitioning [J].IEEE Trans.Pattem Anal. and Machine Intell, 1999;21(5):256～261
9 Sen Wang Wei Wei, Zhang Yang Sheng Wang. Fingerprint classification by directional fields [Z]. Pro. of the 4th IEEE International Conference on Multimodal Interfaces. 2002
10 王崇文,李見為,陳為民. 基于HMM和SVM的指紋分類方法[J]. 電子與信息學(xué)報,2003;(25):1488～1493
11 Shesha Shah, P Sastry. Fingerprint classification using a feedback-based line detector [J]. IEEE Trans. Transactions on system, 2004;34(1):85～94
12 Boser B E, Guyon I M, Vapnik V. A training algorithm for optimal margin classifiers. Pro. of the 5th Annual Workshop on Computational Learning Theory,1992:144～152
13 Vapnik V. Statistical Learning Theory[M].New York: Wiley,1998
14 Cortes C ,Vapnik V. Support vector networks[J].Machine Learning ,1995;20(3):273～297
15 Anil K. Jain, Salil Prabhakar, Lin Hong. A Multichannel Approach to Fingerprint Classification [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence,1999;21(4): 348～359