在電腦視覺和圖形辨識領域的科學家及工程師們，正努力實現一套智慧型系統用於辨識生活中各種不同有用的資訊。在生物特徵中包括有指紋、虹膜、臉形、掌紋、聲紋、簽名等，由於指紋具有獨特性與不變性且基於成本等各種考量，使得指紋辨識在各種生物資訊中最廣為科學家及工程師們所研究、發展，將指紋辨識應用於有關安全性的系統上。指紋辨識中比對的方式有許多，但最廣為研究使用的為Minutiae-based，而利用Minutiae-based比對方式所需處理的動作，例如：影像增強、二值化、細線化等這些動作往往是很費時；特徵點數目的不同，特徵點的匹配和比對亦是需要不少的計算時間。指紋影像經細線化後容易產生誤判的特徵點，且比對的準確度往往受到指紋影像品質的影響。
另有學者提出不以特徵點做為指紋的比對特徵，而將指紋影像視為具方向性的紋理結構，利用指紋紋線資訊做為比對特徵數據。利用Gabor filterbank頻率與方向擷取出指紋影像中全域與區域資訊當作固定長度的特徵向量(Fingercode)，而比對的方式為計算兩指紋影像Fingercode的歐式距離，計算出它們的相似或相異程度，故其比對速度快。本論文提出改善Ridge Feature-based比對方式，處理有關指紋影像偏轉的問題，增加辨識準確性與正確性，以Nios-Stratix 發展板實現成硬體晶片，提供了一個指紋辨識發展平台，以實驗室購買的電容式指紋擷取器，擷取16位同學左拇指與右拇指的指紋影像，每隻拇指按壓兩次共64張指紋影像，整體辦識成功率為96.875%。

The scientists and engineers of the field in computer vision and pattern recognition, make great efforts to realize that a set of intelligent systems are being used for recognizable all kinds of useful information in life. The biological characteristics include fingerprint, iris, shape of face, palm, voiceprint, signing, etc. Because fingerprint has uniqueness and invariable and consideration of cost, fingerprint is most widely used for personal identification in security. Among fingerprint matching algorithms can be broadly classified as minutiae-based and ridge feature-based. The widely used minutiae-based needs to deal with image enhancement, binarization, thinning that are very time-consuming. It usually detects many of the false minutiae and quality of fingerprint is critical fact of accuracy.
A.K. Jain[20] thought fingerprint feature as oriented texture and proposed filter-based algorithm use a bank of Gabor filters to capture both local and global information in fingerprint as a compact fixed length Fingercode. The matching is to finding the Euclidean distance between these Fingercode, hence the matching is very fast.
This thesis proposes improving ridge feature-based deal with the problem about rotation and transfer of fingerprint, and increase the accuracy. I implement the fingerprint identification to the system on a programmable chip with Altera’s Nios Stratix development kit and use capacitive sensor to capture the fingerprint of left thumb and right thumb of 16 classmates. The accuracy of matching is 96.875%.

目錄

中文摘要	I
英文摘要	III
目錄	V
圖目錄	VIII

第一章 緒論	1
	1.1前言	1
	1.2指紋辨識原理和方法概述	2
	1.3本文研究方向	4
第二章 指紋特徵資訊與相關背景	5
	2.1指紋影像擷取裝置	5
	2.2指紋影像中的失真與雜訊	7
	2.3指紋影像的特徵	10
		2.3.1指紋影像中的紋線與谷線	10
		2.3.2指紋影像的宏觀辨識	11
		2.3.3指紋影像的粗略分類	15
		2.3.4指紋影像的細觀辨識	18
		2.3.5擷取指紋特徵點	19
	2.4指紋比對種類	21
	2.5本文所採用比對方式	23

第三章 可規劃系統單晶片SoPC	24
	3.1 SoPC系統設計流程	24
	3.2 Nios辨識系統硬體模組設計流程	26
	3.3 Nios辨識系統軟體設計流程	31
第四章 系統架構	32
	4.1軟體設計流程	32
第五章 研究方法與理論	35
	5.1指紋影像前處理	35
		5.1.1正規化	36
		5.1.2平滑處理與直方圖等化	38
	5.2流向計算	39
		5.2.1 Slit-sum	39
		5.2.2由梯度方向來獲得指紋紋線方向	45
	5.3擷取奇異點	54
		5.3.1形態遮罩	54
		5.3.2 Poincare Index	58
		5.3.3 Sine Component Map	61
		5.3.4各參考點搜尋法結果之比較	67
5.4指紋影像縮減	73
5.5扇形化	75
5.6濾波二值化	81
第六章 Fingercode特徵擷取與比對	91
第七章 模擬與實作結果	100
7.1辨識系統模擬於電容式指紋擷取器	101
7.2辨識系統模擬於光學式指紋擷取器	105
7.3辨識系統模擬於熱感應掃描式指紋擷取器	109
第八章 結論與未來研究方向	113
參考文獻		115

圖目錄

圖1.1指紋辨識系統架構	3
圖2.1光學感測式擷取器所擷取到的指紋影像	5
圖2.2電容感測式擷取器所擷取到的指紋影像	6
圖2.3原始影像與其平移狀況	7
圖2.4原始影像與其旋轉狀況	7
圖2.5原始影像與其擷取區域偏上方狀況	8
圖2.6原始影像與其部分影像重疊狀況	8
圖2.7原始影像與其按壓力道不均偏重或手指較溼的狀況	8
圖2.8原始影像與其按壓力道不均偏輕或手指較乾的狀況	9
圖2.9指紋影像中的痕溝	9
圖2.10指紋影像中之紋線與谷線	10
圖2.11指紋影像中的核心點與三角點	11
圖2.12弧形類	12
圖2.13帳形類	13
圖2.14右箕形紋	13
圖2.15左箕形紋	14
圖2.16螺旋形類	14
圖2.17雙箕螺紋	15
圖2.18粗略的分類演算流程	16
圖2.19指紋細微特徵類型	18
圖2.20特徵點	18
圖2.21典型的指紋特徵點擷取流程圖	19
圖3.1 SoPC系統設計流程	25
圖3.2 Nios辨識系統晶片架構圖	26
圖3.3 SoPC Builder元件模組設定	27
圖3.4 Nios的系統設定	28
圖3.5 Nios辨識系統模組產生	29
圖3.6 Quartus II的BDF硬體模組	30
圖3.7 Nios SDK Shell執行畫面	31
圖4.1本文指紋辨識系統主體架構	32
圖5.1前處理流程	35
圖5.2原始指紋影像與其直方圖	37
圖5.3正規化後的指紋影像與其直方圖	37
圖5.4平滑處理後的指紋影像與其直方圖	38
圖5.5直方圖等化後的指紋影像與其直方圖	38
圖5.6指紋紋路之八種方向	40
圖5.7 9x9之遮罩	40
圖5.8 Silt-sum流向計算之流程	40
圖5.9 WxW區塊	41
圖5.10選取區塊中最黑與最白像素點	41
圖5.11以9x9遮罩套入8x8區塊中最黑與最白之像素點位置	41
圖5.12原始指紋影像	43
圖5.13修正前的指紋流向圖	43
圖5.14修正方式	44
圖5.15修正後的指紋流向圖	45
圖5.16指紋影像中區域梯度方向與流向方向	45
圖5.17 3x3 Sobel運算子遮罩	46
圖5.18黃色區塊流向	47
圖5.19梯度向量場中對立方向的向量	47
圖5.20原始指紋影像	49
圖5.21指紋流向圖	49
圖5.22平均修正	49
圖5.23手指按壓力道不均	50
圖5.24指紋影像品質差	51
圖5.25指紋影像品質不佳	52
圖5.26 核心點位置	54
圖5.27三角點位置	55
圖5.28利用形態遮罩擷取奇異點流程	56
圖5.29核心點附近之流向	56
圖5.30三角點附近之流向	56
圖5.31奇異點位置	57
圖5.32計算Poincare Index流程	58
圖5.33核心點位置	59
圖5.34三角點位置	59
圖5.35各指紋類型利用Poincare Index所擷取到奇異點位置	60
圖5.36 Poincare Index於不同指紋影像品質的表現	60
圖5.37弧形類	61
圖5.38 Concave ridges	61
圖5.39原始指紋影像與平滑處理後的指紋流向場	62
圖5.40 Since component map	62
圖5.41上半圓遮罩	63
圖5.42參考點位置與相對應e(i,j)之位置	64
圖5.43弧形類與其Sine component map	65
圖5.44非弧形類之指紋影像	67
圖5.45各參考點搜尋法結果之比較	68
圖5.46各參考點搜尋法結果於指紋影像品質不佳下之比較	69
圖5.47未經低通濾波所得到指紋流向圖	71
圖5.48低通濾波後所得到指紋流向圖	71
圖5.49未經低通濾波，Poincare index所擷取到可能的參考點位置	72
圖5.50經經低通濾波，Poincare index所擷取到可能的參考點位置	72
圖5.51指紋影像中參考點可能位置	74
圖5.52扇形化流程圖	75
圖5.53扇形化各參數	76
圖5.54圓盤區域經扇形化後劃分為64個扇形區塊	77
圖5.55定義指紋影像座標軸與四個象限位置	79
圖5.56扇形區塊編碼	80
圖5.57定義Gabor空間遮罩參數	82
圖5.58 Gabor各旋轉角度	82
圖5.59八個方向的Gabor空間遮罩	83
圖5.60指紋影像增強	84
圖5.61指紋影像增強與流向正確性之關係	85
圖5.62不同指紋影像品質經影像增強後的結果	86
圖5.63手指按壓力道不均經影像增強後的結果	87
圖5.64八個方向的近似Gabor空間遮罩	88
圖5.65 Gabor空間遮罩與近似Gabor空間遮罩效果之比較	89
圖6.1正規化前後之指紋影像	91
圖6.2指紋Fingercode特徵擷取流程	92
圖6.3濾波後影像	93
圖6.4正規化與影像增強效果之比較	94
圖6.5原始指紋影像與其Fingercode	96
圖6.6一般手指按壓時無偏轉的情況	97
圖6.7參考點下方區域之流向與旋轉修正	98
圖6.8 Tented Arch類與其參考點下方區域之流向	99
圖7.1 Kuo之指紋影像	102
圖7.2 Hao之指紋影像	103
圖7.3 Min與Wei之指紋影像	104
圖7.4 FVC2002 DB2資料庫中的指紋影像	105
圖7.5 7_6、7_7、7_8之參考點與其扇形化和正規化後的指紋影像	106
圖7.6 7_6、7_7、7_8各指紋影像之Fingercode	107
圖7.7 FVC2004 DB3資料庫中的指紋影像	109
圖7.8 89_7、96_8參考點誤判	110
圖7.9指紋影像參考點附近痕溝影響參考點擷取的準確性	111
圖7.10 FVC2004 DB3資料庫中指紋影像比對成功的例子	112
圖8.1指紋流向場與特徵點和指紋紋線數	114

參考文獻

[1] The Biometric Report, SJB Services, 1995, pp.47,
[2] F. Galton, Finger Prints, Macmillan London, 1892.
[3] E. R. Henry, Classification and Uses of Finger Prints, Routledge, London, 1900.
[4] K. Karu and A. K. Jain, “Fingerprint classification,” Pattern Recognition, vol. 29, No. 3, 1996, pp. 389-404.
[5] R. Cappelli, A. Lumini, D. Maio and D. Maltoni, “Fingerprint classification by directional image partitioning,” IEEE Transaction on Pattern Recognition and Machine Intelligence, vol. 21, No. 5, 1999, pp. 402-421. 
[6] A. K. Jain and S. Minut, “Hierarchical kernel fitting for fingerprint classification and alignment,” Pattern Recognition, vol. 2, 2002, pp. 469-473.
[7] B. G. Sherlock, D. M. Monro, and K. Millard, “Fingerprint enhancement by directional Fourier filtering,” IEE Proc. Vis. Image Signal Processing, vol. 141, 1994, pp. 87-94.
[8] D. C. D. Hung, “Enhancement and feature purification of fingerprint image,” Pattern Recognition, vol. 26, 1993, pp. 1661-1671.
[9] L. Hong, Y. Wan, and A. Jain, “Fingerprint image enhancement: Algorithm and performance evaluation,” IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 20, 1998, pp. 777-789. 
[10] L. Coetzee, and E. C. Botha “Fingerprint recognition in low quality images,” Pattern Recognition, vol. 26, 1993, pp. 1441-1460.
[11] N. K. Ratha, S. Chen, and A. Jain, “Adaptive flow orientation-based feature extraction in fingerprint images,” Pattern Recognition, vol. 28, pp. 1657-1672.
[12] B. Moayer, and K. S. Fu, “A tree system approach for fingerprint pattern recognition,” IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 8, No. 3, 1986, pp.  376-388.
[13] D. Maio and D. Maltoni, “Direct gray-scale minutiae detection in fingerprints,” IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 19, No. 1, 1997, pp. 27-39. 
[14] X. Jiang, W. Y. Yau, and W. Ser, “Detecting the fingerprint minutiae by adaptive tracing the gray-level ridge,” Pattern Recognition, vol. 29, 34(5), 2001, pp. 999-1013.
[15] C. Domeniconi, S. Tari and P. Liang, “Direct gray scale ridge reconstruction in fingerprint images,” Proc. IEEE Int. Conference on Acoustics Speech and Signal Processing, vol.5, 1998, pp. 2941-2944.
[16] A. Sibbald, Method and apparatus for Fingerprint Characterization and Recognition Using Auto-correlation Pattern. US Patent 5633947, 1997.
[17] E. C. Driscoll, C. O. Martin, K. Ruby, J. J. Russel, and J. G. Watson, Method and apparatus for verifying identity using image correlation, U.S. patent 5067162, 1991.
[18] A. Ross, J. Reisman, and A. K. Jain, “Fingerprint matching using feature space correlation,” Proc. ECCV Workshop on Biometric Authentication, Copenhagen, 2002.
[19] A. K. Jain, L. Hong, S. Pankanti, and R. Bolle, “An identity authentication system using fingerprints,” Proc. IEEE, vol. 85, No. 9, 1997, pp. 1365-1388.
[20] A. K. Jain, S. Prabhakar, L. Hong, and S. Pankanti, “Filterbank-based fingerprint matching,” IEEE Trans. Image Processing, vol. 9, No. 5, 2000, pp. 846-859.
[21] 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.
[22] M. Kawagoe and A. Tojo, “Fingerprint Pattern Classification,” Pattern Recognition, Vol. 17, No. 3, 1984, pp. 295-303.
[23] M. Kass and A. Witkin, “Analyzing oriented pattern,” Computer Vision, Graphics and Image Processing, Vol. 37, 1987, pp. 362-385.
[24] S. Probhakar, “Fingerprint Classification and Matching Using A Filterbank,” pp. 88-102.
[25] 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.
[26] A. R. Rao, A Taxonomy for Texture Description and Identification. New York: Springer-Verlag, 1990.
[27] 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.
[28] J. Canny, “A Computational Approach to Edge Detection,” IEEE Transactions on PAMI, Vol. 8, No. 6, 1986, pp. 679-698.
[29] 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.
[30] D. Maltoni, D. Maio, A. K. Jain and S. Prabhakar, Handbook of Fingerprint Recognition, Springer (New York), 2003.
[31] Sheng-Hua Lee, Shih-Hsu Chang, Fang-Hsuan Cheng and Wen-Hsing Hsu, "Fingerprint Classification Using Singularn Points," IPPR Conference on CVGI, 1999,       pp. 311-316.
[32] K. C. Chan, Y. S. Moon, and P. S. Chen, “Fast Fingerprint Verification Using Subregions of Fingerprint Images,” IEEE Transaction on Circuits and Systems for Video Technology, Vol. 21, No. 1, 2004, pp. 95-101. 
[33] D. Maio, D. Maltoni, R. Cappelli, J. L. Wayman and A. K. Jain, “FVC2000: Fingerprint Verification Competition,” IEEE Transactions on Pattern Analysis Machine Intelligence, vol.24, No.3, March 2002, pp. 402-412.
[34] D. Maio, D. Maltoni, R. Cappelli, J. L. Wayman and A. K. Jain, "FVC2002: Second Fingerprint Verification Competition," in proceedings 16th International Conference on Pattern Recognition, Québec City, vol. 3, 2002, pp. 811-814.
[35] D. Maio, D. Maltoni, R. Cappelli, J. L. Wayman and A. K. Jain, "FVC2004: Third Fingerprint Verification Competition," Proc. International Conference on Biometric Authentication (ICBA), July 2004, pp. 1-7.
[36] “Embedded Processor System Design,” http://www.Altera.com.
[37] “Nios Embedded Processor System Builder Tutorial,” http://www.Altera.com.
[38] “SoPC Builder Data Sheet,” http://www.Altera.com.
[39] “Nios Embedded Processor System Development,” http://www.Alter.com.
[40] 蕭如宣，SOPC系統設計，儒林圖書公司2003。