摘 要： 利用SVM(Support Vector Machine)解決二類分類問題的優勢，設計了一個粗細兩級指紋分類體器，提出并實現了一種新型的指紋分類算法" title="分類算法">分類算法。測試結果表明，該分類器" title="分類器">分類器具有很好的泛化能力，對于新樣本分類的正確率達98.5%,具有一定的實用價值。
關鍵詞： 指紋分類 分類器 特征提取" title="特征提取">特征提取 支持向量機
指紋作為個人身份的標志具有唯一性和終生不變性。隨著計算機技術的發展，指紋識別技術成為目前使用最廣泛的生物識別技術。一個典型的自動指紋識別系統通常包括五部分：采樣、預處理、特征提取、分類和細節匹配。指紋分類環節對于分解整個復雜的識別任務、縮小細節匹配的范圍和提高識別的效率都具有非常重要的意義。分類算法取決于特征提取環節,大致分為以下五種：
·語法分析法(Syntactic Approach)[1～2]；
·幾何法(Geometry Approach)[3]；
·隨機法(Stochastic Approach)[4]；
·神經網絡法(Neural Network Approach)[5～6]；
·基于奇異點的分類法(Singularity－based Approach)[7～9]。
神經網絡方法在指紋識別技術中應用較為廣泛,但是由于理論本身存在缺陷，神經網絡法容易陷入局部最優和過學習。本文算法的理論基礎——SVM方法擁有嚴密的數學解釋，因此，與神經網絡方法相比推廣能力大大提高。
目前，SVM理論在指紋分類中的應用并不多：王崇文等人提出了一種基于隱馬爾可夫模型和支持向量機" title="支持向量機">支持向量機的兩級分類方法[10]；Shesha Shah等人利用五個SVM分類器將指紋分成了五類[11]，其中分類的原則是反饋型線檢測器的特征提取。該算法中普通弓形和帳弓形的指紋對于新樣本的范化能力不理想，正確率只有79.10%。本文設計的基于支持向量機理論粗細二級分類，使用五個SVM分類器，充分利用它們進行二類分類的優勢，將指紋分為六類。本算法對于新樣本的范化能力有明顯提高，其中弓形分類的正確率可以達到96.7%。本文從四個方面闡述基于支持向量機理論的二級指紋分類算法。SVM這一新的理論不僅為將來指紋分類工作的研究提供了堅實的理論基礎，而且給算法的簡化和不斷完善開拓了嶄新的思路。
1 支持向量機理論
支持向量機是貝爾實驗室研究人員V. Vapnik 等人在對統計學習理論多年的研究基礎上發展起來的一種全新的機器學習算法[12～14]。機器學習的實際風險由兩部分構成：經驗風險和置信范圍，其中后者與Vapnik提出的VC維的概念有關。傳統的使用經驗風險最小化ERM(Empirical Risk Minimization)的分類訓練方法，雖然能取得小的經驗風險，但置信范圍很大，導致過學習，推廣能力下降。SVM方法建立在統計學習的VC 維(Vapnik-Chervonenkis Dimension)理論和結構風險最小化原理SRM(Structural Risk Minimization)基礎上，兼顧了兩部分風險構成，把函數構造為一個函數子集序列，在子集間折衷考慮經驗風險和置信范圍，可以使實際風險最小。
本文設計的粗細二級分類使用五個SVM分類器，其中兩個將指紋粗分為三類，另外三個將指紋細分為六類，SVM分類器解決的都是二類分類問題。
2 算法實現步驟
2.1特征提取
指紋圖像通過預處理后，已經是二值化和細化后的圖像，見圖1。
要分析指紋圖像，首先需進行特征提取。本文采用基于奇異點的特征提取。指紋的特征分為兩種：全局特征和局部細節特征[15]。前者用于指紋分類，后者用于細節匹配。全局特征點即奇異點包括：三角點(delta) 和核心點(core),見圖2。三角點位于從核心點兩個方向差別較大的紋路的匯聚處；核心點位于指紋紋路的漸進中心，它是指紋中心脊線上曲率最大的點。
2.2 根據特征提取設計分類器
指紋通?？梢苑殖晌孱悾憾沸汀⒂倚?、左旋、拱形和帳篷形[13]。為了更好地發揮SVM算法解決二類分類問題的優勢，本文設計了一個兩級分類器，結構框架見圖3。分類器包括粗分類和細分類兩級。第一級將指紋粗分為：斗形(Whorl)、旋形(Loop)和弓形(Arch)三類；第二級,弓形細分為普通弓形(Normal Arch)和帳弓形(Tented Arch)，旋形細分為左旋(Left Loop)和右旋(Right Loop)，斗形細分為單斗(Single Whorl)和雙斗(Twins Whorl)。
2.3 分類判別準則
第一級粗分類遵循如下原則：
·分離斗形，分類準則：核心點的個數(只有斗形的核心點是兩個)；
·區分旋形和弓形，分類準則：兩者雖然擁有同樣的奇異點(一個核心點和一個三角點)，奇異點的連線相對于圖像參考軸的夾角不同。
第二級細分類均為二類分類問題。細分依據分別為： ·斗形：兩核心點的連線與圖像參考軸的相對位置；
·旋形：核心點和三角點連線與圖像參考軸的夾角；
·弓形：核心點的數目。
2.4 SVM分類器
根據兩級分類的判別標準決定SVM的n維輸入向量X(x1,x2,…，xn)的維數，訓練樣本(x1,y1),…，(xn,yn),x∈Rn,y∈{+1,-1}服從某個未知的概率分布，通過對樣本歸一化，求解最優的分類超平面：
yi(xi·W+b)-1≥0????????????????????? (1)
并且使分類間隔1W最大，從而將兩類樣本無誤地分開。這是一個線性約束的二次規劃問題，利用Lagrange函數：
解出支持向量α，再將
帶入(1)式，確定最優超平面，將兩類正確地分開。以旋形的細分類為例，首先根據分類的判別準則確定輸入向量的維數，這里輸入向量X是三維,包括三角點相對橫坐標x1、相對縱坐標x2、三角點和核心點連線與圖像參考軸的夾角x3，即X(x1,x2,x3)，然后根據上述公式求解出支持向量α，最終確定將左旋和右旋正確分開的超平面。
3 實驗結果
實驗使用了FVC2004的指紋數據庫和晶體2100型指紋采集儀，抽取不同數目的指紋作為訓練樣本，使用Microsoft Visual Studio.Net2003編程實現了使用SVM方法的二級指紋分類。選取的樣本容量以及分類正確率，見表1。對于新樣本SVM方法表現出了很好的泛化能力，分類判別的正確率大大提高，而且由于實現的是二級粗細分類，需要進行判斷樣本的數目分流，加快了分類的速度。通過驗證不同容量的訓練樣本可以得出結論，SVM方法在解決二類分類問題上的確有優于其他算法之處。
SVM方法不但能提高分類的速率，而且不限制模型的選擇。SVM有三種不同的內核函數" title="核函數">核函數：(1)多項式核函數(polynomial)：K(x,xi)=[(x·xi)+1]q；(2)徑向基函數(Radial Basis Function)：K(x,xi)=exp
；(3)Sigmoid函數：K(x,xi)=tanh(v(x·xi)+c)。實驗使用三種核函數的模型對弓形進行細分類，訓練樣本容量選取100，數據見表2，其中統計了兩類的支持向量的數目分別用Positive_SVM和Negative_SVM表示。
實驗結果表明，核函數的選取對分類的效果影響甚小，因此算法在模型的選擇上具有很大的靈活性。
實驗表明，將支持向量機理論應用于指紋分類是可行的，而且對于提高指紋分類算法的效率有不可或缺的作用。SVM方法基于嚴密的數學理論，遵循SRM原則尋找最優超平面。本文設計的粗細二級分類器,將指紋先后分成了三類和六類，充分發揮了SVM理論解決二類分類問題的優勢，通過編程實現，訓練樣本具有較好的泛化能力。與神經網絡方法相比，本文提出的算法無論是在理論基礎方面還是在模型選擇的靈活性方面都表現出了極大的優越性。
參考文獻
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]. 微電子學與計算機, 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]. 電子與信息學報,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