在現今的社會中，科技的日新月異、經濟的快速發展，社會形態的變化也越趨於多元，人們生活方式也就更加複雜，在很多情況下個人的生命財產與安全保密性變成一項相當重要的課題。早期，是以鑰匙和密碼來做為個人的保密工具，但是這類的工具存在著不方便性、易遺忘與易遺失等問題。因此，學者們都在探討能否以生物特徵來做為個人身份識別的工具，利用生物特徵來當作辨識身份的方法。
所謂的「生物特徵辨識」就是運用使用者身上與生俱有生理或行為的生物特徵(如臉形、指紋、手掌幾何(掌形)、書寫、眼睛虹膜、視網膜及聲音等)來辨認或驗證使用者個人的身份。本論文以生物辨識中的指紋特徵來加以探討與研究。在一般的辨識上還是以指紋辨識為優先考量，除了有生物特徵中「唯一性、不變性與獨特性」外，在成本與功能的比較上也比其他辨識所採用的生物特徵來得低廉與實用。因此，指紋辨識長久以來已被廣泛的在法庭上使用，做為驗證罪犯身份的重要依據，並且成為日常生活中鑑定人們身份的重要方法之一。
本論文所研究的目的是以FPGA(Field Programmable Gate Array)晶片本身所具備的高整合、可循環、快速度、可攜性、高密度、高容量、低耗電與無限次可編程等優點。提出有效的前處理方式來處理指紋影像，並且由指紋擷取器取出指紋影像，找尋奇異點作指紋分類，最後與資料庫中進行分類比對與指紋影像建立存檔。本論文並將所提出之方法實現在可程式單晶片系統(SOPC)上，選擇使用Altera的Cyclone晶片為主架構並結合周邊元件完成硬體製作；並搭配Altera的QuartusⅡ(FPGA設計流程)與NiosⅡ(軟式核心嵌入式處理器)之設計軟體來實現指紋辨識晶片系統，最後系統在以RS232與電腦連接來驗證指紋辨識系統架構。

Because the advance of the technology and fast development of economy, the personal wealth and security privacy have become important issues. People use key and password for security in general, but these kinds of tool are inconvenient to carry and maybe have the problem of forgetfulness and loss.Therefore, the personal identification with the biological characteristics is researching by professionals.

Biometrics recognition is the use of a person's inherent unique physical characteristics or behaviors such as face, fingerprint, palm, signature, iris, voice to verify their identity. In this thesis, we study and discuss the characteristics of fingerprint and utilize unique physical characteristics to verify their identity.Fingerprint is the most widely used characteristic for personal identification because the fingerprints have invariance and uniqueness. We measure the cost and performance that fingerprint is cheap and practically more than the others. Hence, fingerprint recognition has already been used in the court to verify criminal's identity and it has become one of the important methods of people's identity.

FPGA (Field Programmable Gate Array) has a lot of advantages, such as high integration, reconfiguration, high speed, portable, high density, high capacity, low power consumption and infinitely reconfigurable. We propose an effective pre-process to enhance the fingerprint image. First, we obtain a fingerprint image from a sensor and then search singular points for classification. Finally, we can match it with the database. We implement our proposal on a SOPC (system on a programmable chip). We choose a chip of Cyclone from Altera and integrate peripheral components to accomplish it. And we achieve a fingerprint identification system via Altera’s QuartusⅡ (FPGA design flow) and NiosⅡ (soft core embedded processor). Finally, we verify the system through RS232 connected with a computer.

中文摘要	Ⅰ
英文摘要	Ⅱ
目錄	Ⅲ
圖索引	Ⅵ
表索引	ⅩⅢ

第一章、序論	1
1.1 引言	1
1.2 指紋辨識之發展歷史	3
1.3 指紋辨識之優點	4
1.4 指紋辨識之應用方向	5
1.5 本文研究方向	6
1.6 內容大綱	7

第二章、背景知識介紹	9
2.1指紋影像之擷取裝置	9
2.2指紋影像之紋線與谷線	11
2.3指紋影像特徵	11
2.4指紋影像之辨認	12
    2.4.1 宏觀辨認	12
    2.4.2 細微辨認	16
2.5 NIST之分類方法	19
2.6指紋影像之比對種類	20
2.7本文之處理方式	22

第三章、系統架構與相關技術	23
3.1 軟體設計流程	23
3.2 SOPC系統介紹	28
    3.2.1 SOPC設計流程	30
    3.2.2 硬體設計解決方案	31
    3.2.3 軟體設計解決方案	32
    3.2.4 量產轉移程序	33
3.3 Altera系統開發工具	33
3.4 Altera-Nios嵌入式處理器	36

第四章、研究方法與理論	42
4.1 指紋辨識之分類器演算法設計	42
4.2 指紋影像輸入單元	44
4.3背景去除	44
4.4雜訊去除	48
4.5 正規化	51
4.6 指紋流向計算	54
4.7 指紋流向修正	59
4.8 奇異點搜尋	61
4.9 分類器與資料庫建檔單元	71
4.10 Nios系統之設計流程	76
4.11 Nios系統之模組設計	82

第五章、系統之硬體實現	87
5.1 電路設計	88
5.2 電路圖繪製	90
5.3 系統電路說明	99
5.4 電路Layout	112
5.5 沖洗電路板	112
5.6 零件規格之選用與採購	113
5.7 電路板焊接製作	116
5.8 電路設計驗證測試	117
5.9 指紋辨識晶片系統整合測試	118

第六章、系統之分類建檔與模擬結果	119
6.1 分類建檔	119
6.2 模擬結果	121

第七章、結論與未來展望	127
7.1 結論	127
7.2 未來展望	128

參考文獻	130

圖2.1 指紋影像之紋線與谷線	11
圖2.2 指紋影像中的中心點與三角點	12
圖2.3 弧形類（Arch）	13
圖2.4 箕形類（Loop）	14
圖2.5 螺旋形類（Whorl）	15
圖2.6 雜形紋（Accidental）	16
圖2.7 指紋影像與其方向（流向）圖	17
圖2.8 指紋細微特徵（短山脊、端點、交叉點、分叉點）	18
圖2.9 指紋細微特徵（突刺、橋點、島、點）	18
圖2.10 指紋八種細微特徵類型	18
圖2.11 NIST之分類
       （a）、Left Loop-左旋類	19
       （b）、Right Loop-右旋類	19
       （c）、Arch-弧形類	19
       （d）、Tented Arch-帳形類	19
圖2.11 NIST之分類(續)
       （e）、Whorl-囊形類	20
圖3.1 指紋辨識系統之分類器主體架構	23
圖3.2 指紋辨識系統之分類與建檔流程圖	27
圖3.3 SOPC設計流程圖	31
圖3.4 QuartusⅡ使用介面	34
圖3.5 QuartusⅡ硬體開發流程圖	35
圖3.6 SOPC Builder使用介面	35
圖3.7 Nios系統架構圖	38
圖3.8 Nios嵌入式處理器方塊圖	39
圖4.1 指紋辨識系統之分類流程	43
圖4.2 AF-S2晶片式指紋擷取器	44
圖4.3 背景去除之運算方式	47
圖4.4 原始影像與經背景去除後之影像	47
圖4.5 帶通濾波器運算示意圖	49
圖4.6 雜訊去除之運算方式	50
圖4.7 雜訊去除之影像
(a) 背景去除後之影像	50
(b) 經帶通濾波器後之影像	50
圖4.8 正規化前/後之指紋影像
(a) 指紋影像於正規化前之影像	53
(b) 指紋影像於正規化後之影像	53
圖4.9 流向計算之處理動作	54
圖4.10 指紋紋路之八種方向	55
圖4.11 9×9之遮罩	55
圖4.12 以8×8區塊選取之指紋影像	56
圖4.13 選取最黑與最白之像素點位置圖示	56
圖4.14 以9×9遮罩套入8×8區塊中最黑與最白之像素點位置
（a）	以最黑之像素點代入之圖說	57
（b）	以最白之像素點代入之圖說	57
圖4.15 指紋影像經流向計算判斷後其結果	59
圖4.16 指紋流向修正	60
圖4.17 修正前的流向圖	60
圖4.18 修正後的流向圖	60
圖4.19 指紋影像核心點出現時附近之紋路	61
圖4.20 核心點位置與其附近之流向
（a）	核心點位置附近之流向	62
（b）	核心點位置附近之流向編號	62
圖4.21 各流向對應至核心點之座標	62
圖4.22 指紋影像左偏時核心點附近之流向與流向編號	64
圖4.23 指紋影像右偏時核心點附近之流向與流向編號	64
圖4.24 可能出現核心點位置之區塊	65
圖4.25 正確之核心點位置	66
圖4.26 下方核心點出現時附近之流向與流向編號
（a）	下方核心點出現時附近之流向	67
（b）	下方核心點附近之流向編號	67
圖4.27 左偏時下方核心點附近之流向與流向編號	67
圖4.28 右偏時下方核心點附近之流向與流向編號	68
圖4.29 指紋影像之下方核心點	68
圖4.30 三角點附近之流向與流向編號	69
圖4.31 左偏時三角點附近之流向與流向編號	69
圖4.32 右偏時三角點附近之流向與流向編號	70
圖4.33 指紋影像之三角點	70
圖4.34 Class A：左旋類(Left Loop)	 72
圖4.35 Class B：右旋類(Right Loop) 	72
圖4.36 Class C：弧形與帳形類(Arch and Tented Arch) 	72
圖4.37 Class D：囊形類(Whorl) 	73
圖4.38 Class E：其他類(Others) 	73
圖4.39 分類建檔流程圖	74
圖4.40 資料庫建檔之運算方式示意圖	75
圖4.41 SOPC Builder之系統內容	77
圖4.42 Nios之系統設定	78
圖4.43 SOPC系統產生	79
圖4.44 QuartusⅡ的BDF檔	80
圖4.45 Nios SDK Shell執行畫面	81
圖4.46 Nios系統晶片架構圖	82
圖4.47 組態控制器與Flash記憶體間之關係圖	84
圖4.48 Tri-state PIO組態	85
圖4.49 Output-Only PIO組態	85
圖4.50 Input-Only PIO組態	86
圖5.1 硬體設計流程圖	87
圖5.2 電路圖(一)：Nios處理器(二之一)	91
圖5.3 電路圖(二)：Nios處理器(二之二)	92
圖5.4 電路圖(三)：系統電源與系統時鐘源	93
圖5.5 電路圖(四)：同步動態隨機存取記憶體與快閃記憶體	94
圖5.6 電路圖(五)：靜態隨機存取記憶體	95
圖5.7 電路圖(六)：重置電路	96
圖5.8 電路圖(七)：非同步收發器介面、液晶顯示器介面與鍵盤介面	97
圖5.9 電路圖(八)：指紋擷取器介面	98
圖5.10 系統電源
(a)	DC-9V轉為+5V	99
圖5.10 系統電源(續)
(b)	處理器I/O電壓3.3V	100
(c)	處理器核心電壓1.5V	100
圖5.10 系統電源(續)
(d)	記憶體使用電壓M3.3V	101
圖5.11 Nios處理器
(a)	處理器之一	102
圖5.11 Nios處理器(續)
(b)	處理器之二	103
圖5.12 系統時鐘源	104
圖5.13 重置電路	105
圖5.14 快閃記憶體	106
圖5.15 同步動態隨機存取記憶體	107
圖5.16 靜態隨機存取記憶體	108
圖5.17 非同步收發器介面	109
圖5.18 液晶顯示器介面	110
圖5.19 鍵盤介面	110
圖5.20 指紋擷取器介面	111
圖6.1 分類建檔流程圖	120
圖6.2 系統操作流程	125
圖6.3 實驗板實體拍攝	126

表5.6.1 使用之主動元件	113
表5.6.2 使用之被動元件	114
表5.6.3 使用之機構元件	115
表5.6.4 使用之功能元件	115
表5.6.5 零件代理商	115
表6.2.1 使用990枚指紋影像進行分類之模擬結果	122

[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]  A. K. Jain, L. Hong, S. Pankanti and R. Bolle,
“An identity-authentication system using fingerprints,”Proceedings IEEE, Vol. 85, No. 9, 1998, pp. 1365-1388.
[5]  彭韻瑞，“ 手指紋大分類法之研究 ”，中原大學電子所碩士論文，1997年6月。
[6]  李宗瀚，“ 即時指紋辨識演算法 ”，輔仁大學資工所碩士論文，2001年6月。
[7]  呂狀元，“ 指紋分類系統設計 ”，淡江大學電機所碩士論文，2000年6月。
[8]  J. S. Lim, “Two-Dimensional Signal and Image Processing,”Prentice Hall, Inc., 1990, pp. 496.
[9]  B. M. Mehtre, N. N. Murthy and S. Kapoor, “Segmentation of Fingerprint Image Using The Directional Image,” Pattern Recognition, Vol. 20, No. 4, 1987, pp. 429-435.
[10]  C. J. Watson and C. L. Wilson, “Fingerprint Database, NIST Imaging Database 4,” http://www.nist.gov/.
[11]  A. Grasselli, “On the automatic classification of fingerprints some consideration on the linguistic interpretation of pictures,” Methodologies of Pattern Recognition, pp. 253-273.
[12]  B. Moayer and K. S. Fu, “An application of stochastic languages to fingerprint pattern recognition,” Pattern Recognition, Vol. 8, 1976, pp. 173-179.
[13]  B. Moayer and K. S. Fu, “A Tree System Approach for Fingerprint,” Pattern Recognition IEEE Transition on Computers, Vol. C-25, No. 3, March 1976, pp. 262-274.
[14]  C. C. Kameswara Rao and Kenneth Black, “Finding the Core Point in a Fingerprint,” IEEE Transaction on Computers, Vol. C-27, No. 1, January, 1978, pp. 77-81.
[15]  M. Kawagoe and A. Tojo, “Fingerprint Pattern Classification,” Pattern Recognition, Vol. 17, No. 3, 1984, pp. 195-303.
[16]  M. K. Sparrow and P. J. Sparrow, “A Topoligocal Approach to the Matching of Single Fingerprints：Development of Algorithms for Use on Rolled Impressions,” NBS Special Publication, 500-124, May 1985.
[17] T. Ch Malleswara Rao, “Feature Extraction for Fingerprint Classification,” Pattern Recognition, Vol. 8, 1976, pp. 181-192.
[18]  C. V. Kameswara Rao, “On Fingerprint Recognition,” Pattern Recognition, Vol. 10, 1978, pp. 15-18.
[19]  “Automated Fingerprint Identification System,” NEC.
[20]  D. K. Isenor and S. G. Zaky, “Fingerprint Identification using Graph Matching,” Pattern Recognition, Vol. 19, No. 2, 1986, pp. 13-122.
[21]  陳俊良，“有效的指紋前處理及分類”，淡江大學資工所碩士論文，2001年6月。
[22]  D. L. Sancho-Pradel, S. R. Jones and R. M. Goodall, “System on programmable chip for real-time control implementations Field-Programmable Technology,”Proceedings of the IEEE International Conference Field-Programmable Technology, 16-18, Dec. 2002, pp. 276-283.
[23]  B. Dalay, “Accelerating system performance using SOPC builder,” Proceedings of IEEE International Symposium on System-on-Chip,  19-21, Nov. 2003.
[24]  W. H. Wolf, “Hardware-software co-design of embedded systems,” Proceedings of the IEEE, Vol. 82, No. 7, July, 1994, pp. 967-989.
[25]  S. Knapp and D. Tavana, “Field Configurable System-on-Chip device architecture,”Proceedings of IEEE Custom Integrated Circuit Conference, Orlando, FL USA, 2000, pp. 155-158.
[26]  蕭如宣，“SOPC系統設計”，儒林圖書公司，2003年6月。
[27] “SOPC Builder Data Sheet,”http://www.altera.com.
[28] “Nios embedded processor system builder tutorial,”http://www.altera.com.
[29] “Embedded processor system design,”http://www.altera.com.
[30] “Nios embedded processor system development,”http://www.altera.com.
[31] “Avalon bus specification reference manual,”http://www.altera.com.
[32]  林宸生、邱創乾、陳德請，“數位信號處理”，高立，1999年6月。