在當今的社會中，資料安全的防護與門禁管理系統以及身分辨識是一項相當重要的課題。現今生物辨識技術逐漸廣泛的被運用在系統保密性以及身分辨別上，現在主要的生物辨識技術有，聲音、容貌、虹膜、指紋，其中指紋因為具有唯一性和不變性且具有相當高的可靠度而最常為人們所採用。
    大部分的指紋辨識方法，都是先將指紋影像經過正規化、濾波雜訊、取指紋流向、流向濾波、細線化、偵測奇異點與特徵點。其中，又主要以指紋的奇異點(核心點、三角點)及紋線的特徵點(端點、叉點)的分布位置、數目作為之後比對的依據。指紋流向場若能精確的求得，那要擷取出特徵點以及核心點將是一件容易的事情。本文將提出一種新的改良式二值化法來取代以往大家常使用的Gabor濾波二值化法來加速指紋比對的速度以及成功率。
    本論文又提出一種新的比對流程來加速比對單元的效率，在經過前面有效的影像處理步驟之後，我們省略了細線化直接做特徵擷取，並經由其核心點附近的流向對其做快速的指紋分類建檔，在比對單元方面，會先經由其分類建檔的資料庫來比對，將會大大的改善整個比對單元的辨識效率。

Nowadays, the importance of the information protection and the entrance guard control system are quite important lessons. Today, biometric verification technique is applied on enhancing the system of maintaining secrecy and recognized identifications. Biometric verification techniques which are available now are mainly as follows: voice, appearance, iris, fingerprint. Fingerprint is so authentic adopted for people constantly because of its singularity and constancy.
    Most identification methods would including normalization, noise filter, calculate fingerprint flow direction, flow filter, thinning, detect the positions of the singular points and minutiae. The primal methods are depend on the locations and numbers of ridge endings and bifurcations. If we can get the fingerprint flow field exactly, it will be easy to find out the minutiae and singular points. In this thesis, we propose a novel improved binarization to replace gabor filter. This method can accelerate the speed of the calculation of fingerprint flow and help us gain the flow more accurately.
    We also advance a new verification process to promote the efficiency of verification. After a series of valid image preprocessing procedure, we detect the minutiae without Thinning, and use the flow nearing the core point to classify the fingerprints speedily. As for the verification unit, the new verification process would verify the fingerprints of its classified database first, which will improve the verification efficiency of the whole verification unit.

中文摘要……………………………………………..………………...……Ⅰ
英文摘要………………………………………………………..…………...Ⅱ
目  錄………………………………………...…………..…………………Ⅲ
圖目錄.……………..………………………………………………….…...VII
表目錄………………………………………………...………….....…….XIII

第一章、緒  論………………………………………...…………..…………1
1.1 研究背景與動機……………………………....…………..……1
1.2 指紋辨識原理………………………………..........................…2
1.3指紋辨識應用範圍……………………….......……….…….…..4
1.4 研究方向………………………………………………...…...…5
1.4 內容大綱………………………………………………...…...…6
第二章、指紋辨識相關背景…………...………………..……………………8
2.1 指紋影像擷取裝置………………………...…………………...8
2.2 指紋影像特徵……………………….………...…………....…10
2.2.1 指紋影像之宏觀辨認….………….…..……...……. ……11
2.2.2 指紋影像之微觀辨認…………..……………...…………16
2.3 指紋影像之比對種類………………………...……..…...........19
第三章、指紋影像前處理單元	21
       3.1 背景去除	22
       3.2 正規化與中值濾波處理	24
         3.2.1 正規化處理	24
         3.2.2 中值濾波	27
       3.3指紋流向場計算	30
         3.3.1 Slite-sum	31
         3.3.2梯度法	32
         3.3.3指紋流向分類法	34
       3.4流向法比較	42
         3.4.1模擬比較	43
         3.4.2流向修正法	46
       3.5奇異點偵測	49
       3.6影像剪裁	51
       3.7改良式二值化	53
第四章、指紋特徵點搜尋及比對	57
       4.1 指紋分類	57
       4.2 特徵點搜尋	62
4.3 特徵點比對	71
第五章、系統設計……………………………………... ………... ………...75
5.1 嵌入式系統……………………………………………………75
5.2 嵌入式系統架構……………………………………………....77
5.3 DSP系統…………………………………………….... .... .... ..79
  5.3.1 DSP的優點…………………………………………….... .81
  5.3.1 DSP的應用…………………………………………….... .82
5.4 TMS320C6713 DSK 簡介………………………………………84
  5.4.1 C6x晶片簡介……………………………………………....85
  5.4.2指紋擷取器簡介…………………………………………..87
第六章、系統模擬與硬體實作結果…………….……………….…..……90
6.1 演算法模擬……………………………………………………90
6.2 實作結果………………………………………………………94
第七章、結論與未來研究方向……….……….……………….…..………99
       7.1 結論…………………………………………………………....99
       7.2 未來研究方向………………………………………………..100
參考文獻…………………………………….……………………………..101

圖2.1指紋之紋線與谷線	10
圖2.2指紋影像中的核心點與三角點	11
圖2.3帳型類	12
圖2.4平弧紋	13
圖2.5左箕形纹	13
圖2.6右箕形纹	14
圖2.7平螺紋	14
圖2.8囊形紋	15
圖2.9雙箕螺紋	15
圖2.10雜形類	16
圖2.11流向的八個方向	16
圖2.12指紋影像與其流向圖	17
圖2.13指紋細微特徵	18
圖2.14指紋影像中之細微特徵(端點、叉點)	18
圖3.1指紋影像前處理流程	21
圖3.2含大量背景之指紋圖	22
圖3.3  (a)初步指紋背景去除 (b)完整指紋背景去除	23
圖3.4背景去除流程圖	23
圖3.5正規化流程圖	24
圖3.6   (a)原始影像 (b)背景去除和正規化後影像	26
圖3.7   (a)原始影像灰階值直方圖 (b)正規化後影像灰階值直方圖	26
圖3.8  (a)胡椒鹽式雜訊圖 (b)經過中值濾波的圖	28
圖3.9   (a)原始矩陣 (b)排序後矩陣	28
       (c)中值濾波後矩陣	29
圖3.10  (a)未經中值濾波影像 (b)中值濾波後影像	29
圖3.11  指紋紋路之八個方向	30
圖3.12 Slite-sum 之9×9流向遮罩	31
圖3.13  (a) Sobel運算式 (b)Gx  (c)Gy	33
圖3.14 流向分類法流程圖	34
圖3.15 (a)第一類 (b)第二類 (c)第三類 (d)第四類……………………..35
圖3.16區塊二值化圖……………………………………………………….36
圖3.17區塊反白圖………………………………………………………….36
圖3.18第二類判斷遮罩…………………………………………………….38
圖3.19左右斜中心遮罩一…………………………………………………39
圖3.20 (a)第三類左右斜遮罩一 (b)第三類左右斜遮罩二……………….40
圖3.21左右斜中心遮罩二………………………………………………….41
圖3.22(a)第四類左右斜遮罩一 (b)第四類左右斜遮罩二………………..41
圖3.23 破碎指紋流向圖…………………………………………………..44
圖3.24 梯度法錯誤流向圖…………………………………………………44
圖3.25 流向分類法錯誤流向圖……………………………………………44
圖3.26 流向修正法示意圖…………………………………………………46
圖3.27 (a)指紋流向場修正前 (b)指紋流向場修正後…………………….47
圖3.28 流向修正規則遮罩………………………………………………...47
圖3.29 指紋流向修正後圖…………………………………………………48
圖3.30 Poincare Index遮罩…………………………………………………49
圖3.31 計算Poincare Index示意圖………………………………………..50
圖3.32 奇異點偵測的例子…………………………………………………50
圖3.33 指紋裁剪之示意圖…………………………………………………51
圖3.34 影像裁剪的例子……………………………………………………52
圖3.35參考點中央時的影像剪裁………………………………………….52
圖3.36參考點靠左邊時的影像剪裁……………………………………….52
圖3.37 區域平均臨界值法的8×8區塊移動示意圖………………………54
圖3.38 臨界二值化後的影像………………………………………………54
圖3.39 改良區域平均臨界值法的8×8區塊移動示意圖…………………56
圖3.40二值化後的影像……………………………………………………56
圖4.1 五種指紋分類………………………………………………………..58
圖4.2 核心區與流向對稱線示意圖
(a)核心區與流向對稱線 (b)對稱線兩旁的理想流向	58
圖4.3 左箕紋
         (a)指紋圖 (b)以核心區與流向對稱線判斷	59
圖4.4 右箕紋
(a)指紋圖 (b)以核心區與流向對稱線判斷	60
圖4.5 弧形紋
(a)指紋圖 (b)以核心區與流向對稱線判斷	60
圖4.6 螺旋紋
(a)指紋圖 (b)以核心區與流向對稱線判斷	61
圖4.7 雜形紋
(a)指紋圖 (b)以核心區與流向對稱線判斷	61
圖4.8 指紋細線化處理
(a)指紋細線化前 (b)指紋細線化後	62
圖4.9 特徵搜尋遮罩圖……………………………………………………..63
圖4.10 端點遮罩圖…………………………………………………………63
圖4.11 叉點遮罩圖…………………………………………………………64
圖4.12 全特徵點圖…………………………………………………………64
圖4.13 特徵點檢測遮罩圖…………………………………………………65
圖4.14 正確特徵點示意圖…………………………………………………65
圖4.15 錯誤特徵點示意圖…..…………………………………………….65
圖4.16 特徵點檢測遮罩套入端點圖……………………………………...66
圖4.17 OR運算後的端點圖………………………………………………..66
圖4.18特徵點檢測遮罩套入叉點圖……………………………………….67
圖4.19 AND運算後的叉點圖………………………………………………67
圖4.20 特徵點叢聚現象……………………………………………………68
圖4.21 特徵點選取框線示意圖……………………………………………69
圖4.22 最後選取特徵點……………………………………………………69
圖4.23 紀錄特徵點示意圖………………………………………………....70
圖4.24 特徵點位置........................................................................................71
圖4.25 分類資料庫比對……………………………………………………72

圖4.42 指紋比對辨識成功例子
(a)欲比對辨識指紋 (b)資料庫指紋	74
圖5.1 典型之嵌入式系統架構…………………………………………….77
圖5.2 TI TMS320C6713™DSK以及ATMEL AT77C101B指紋讀取器......84
圖5.3 C6713 DSK的硬體方塊圖…………………………………………..85
圖5.4 C6x系統方塊圖……………………………………………………...86
圖5.5 AT77C101B熱感式指紋擷取器……………………………………..88
圖5.6 ATMEL AT77C101B 指紋讀取器的硬體方塊圖...............................89
圖6.1 CCS介面……………………………………………………………..95
圖6.2 軟硬體除錯介面……………………………………………………..96
圖6.3 硬體操作流程圖……………………………………………………..97

表3.1 流向法比較表………………………………………………………..43
表3.2 修正後流向法比較表………………………………………………..48
表6.1 指紋分類結果………………………………………………………..92
表6.2 與其他論文比較表………………………………………………….93
表6.3 演算法模擬結果…………………………………………………….93
表6.4 與其他論文比較表………………………………………………….98

[1]	彭韻瑞，手指紋大分類法之研究，中原大學電子所碩士論文，民國86年。
[2]	李宗瀚，即時指紋辨識演算法，輔仁大學資工所碩士論文，民國90年。
[3]	國際指紋識別競賽(Fingerprint Verification Competition，FVC2000)之指紋資料庫，http://bias.csr.unibo.it/fvc2000/。
[4]  E. R. Henry, Classification and Uses of Finger Prints. Routledge, London, 1900.
[5]  陳俊良，“有效的指紋前處理及分類”，淡江大學資工所碩士論文，2001年6月。
[6]  K. Karu and A. K. Jain, “Fingerprint Classification,” Pattern Recognition, vol. 18, no. 3, 1996, pp. 389-404.
[7]  A. K. Hrechak and J. A. Mchugh, “Automated Fingerprint Recognition using Structural Matching,” Pattern Recognition, vol. 23, no. 8, 1990, pp. 893-904.
[8]  A. M. Bazen, G. T. B. Verwaaijen, S. H. Gerez, L. P. J. Veelenturf, and B. J. van der Zwaag, “A Correlation-Based Fingerprint Verification System,” in Proceedings of ProRISC2000, 11th Annual Workshop on Circuits, Systems and Signal Processing, Veldhoven, The Netherlands, Nov. 2000, pp. 205-213.
[9]  N. K. Ratha, K. Karu, S. Chen, and A. K. Jain, “A Real-Time Matching System for Large Fingerprint Databases,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 8, Aug. 1996, pp. 799-813.
[10]  A. K. Jain, L. Hong, and R. Bolle, “On-Line Fingerprint Verification,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 4, Apr. 1997, pp. 302-313.
[11]  R. S. Germain, A. Califano, and S. Colville, “Fingerprint Matching Using Transformation Parameter Clustering,” IEEE Computational Science and Eng., vol. 4, no. 4, 1997, pp. 42-49.
[12]  A. Wahab, S. H. Chin, and E. C. Tan, “Novel Approach to Automated Fingerprint Recognition,” IEE Proc. Vision, Image and Signal Processing, vol. 145, no. 3, June 1998, pp. 160-166.
[13]  Z. M. Kovacs-Vajna, “A Fingerprint Verification System based on Triangular Matching and Dynamic Time Warping,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 11, Nov. 2000, pp. 1266-1276.
[14]  C. J. Lee and S. D. Wang, “Fingerprint Feature Extraction Using Gabor Filters,” Electronics Letters, vol. 35, no. 4, Feb. 1999, pp. 288-290.
[15]  A. K. Jain, S. Prabhakar, L. Hong, and S. Pankanti, “Filterbank-Based Fingerprint Matching,” IEEE Trans. Image Processing, vol. 9, no. 5, May 2000, pp. 846-859.
[16]  M. Tico, P. Kuosmanen, and J. Saarinen, “Wavelet Domain Features for Fingerprint Recognition,” Electronics Letters, vol. 37, no. 1, Jan. 2001, pp. 21-22.
[17]  L. Hong, Y. Wan, and A. Jain, “Fingerprint Image Enhancement: Algorithm and Performance Evaluation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, no. 8, Aug. 1998, pp. 777-789.
[18]	吳鐵民、鄭伯順、張光耀，中文字形二元化臨界值法則用於光學中文文字識別之研究，電信研究季刊，第20卷第1期，民國79年3月。
[19]	R. M. Stock and C. W. Swonger, “Development and evaluation of a reader of fingerprint minutiae,” Cornell Aeronautical Laboratory, Technical Report, CAL No. XM-2478-X-1, 1969, pp. 13-17.
[20] 	M. Kawagone and A. Tojo, “Fingerprint Pattern Classification,” Pattern Recognition, Vol 17, No. 3, 1984, pp.295-303.
[21] 	M. Kass and A. Witkin, “Analyzing oriented pattern,” Computer Vision, Graphics and Image Processing, Vol. 37, 1987, pp. 362-385.
[22] 	S. Probhakar, “Fingerprint Classification and Matching Using A filterbank,” pp. 88-102.
[23] 	A. K. Jain, L. Hong, S. Pankanti, and R. Bolle, “An Identity Authentication System Using Fingerprint,” Proceedings of the IEEE, Vol. 85, No.9, 1997, pp. 1365-1388. 
[24] 	A. R. Rao, A Taxonomy for Texture Description and Identification. New York: Springer-Verlag, 1990.
[25] 	N. Ratha, K, Karu, S. Chen and A. K. Jain, “A Real-time Matching System for Large Fingerprint Database,” IEEE Trans. on Pattern Anal. Machine Intell., Vol. 18, No. 8, 1996, pp. 799-813.
[26] 	J. Canny, “A Computational Approach to Edge Detection,” IEEE Transactions on PAMI, Vol. 8, No. 6, 1986, pp. 679-698.
[27] 	A. M. Bazen and S. H. Gerez, “Systematic Methods for the Computation of the Directional Fields and Singular Points of Fingerprints,” IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, Vol. 24, No.7, JULY 2002, pp. 905-919.
[28]	郭丁溢，以濾波比對方式之指紋辨識晶片設計，淡江大學電機所碩士論文，民國94年。
[29]	李建潁，快速特徵搜尋之指紋辨識晶片設計，淡江大學電機所碩士論文，民國94年。
[30]  I. Emiroglu and M. B. Akhan, “Pre-processing of Fingerprint Images,” European Conference on Security and Detection, Apr. 1997, pp. 147-151.
[31]  J. L. Blue, G. T. Candela, P. J. Grother, R. Chellappa, C. L. Wilson, and J. D. Blue, “Evaluation of pattern classifiers for fingerprint and OCR applications,” Pattern Recognition, vol. 27, 1994., pp. 485–501.

[32]  L. Hong, Y. Wan, and A. Jain, “Fingerprint Image Enhancement: Algorithm and Performance Evaluation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, no. 8, Aug. 1998, pp. 777-789.
[33] 探矽工作室，2002嵌入式系統開發聖經，學貫行銷股份有限公司，2002年9月。
[34]  陳宏宇，DSP程式設計，文魁資訊股份有限公司，2004年7月。
[35]	 李釋書，利用嵌入式軟核心處理器之指紋辨識晶片設計與實作，淡
      江大學電機所碩士論文，民國94年。
[36]	 蕭志豪，改良式多級指紋比對演算法指紋辨識晶片設計，淡江大學  
      電機所碩士論文，民國95年。
[37]	 劉政衛，改良式流向法之指紋辨識系統設計，淡江大學電機所碩士   
      論文，民國95年。