近年來，資料安全的防護與門禁管理系統的重要性越來越受到重視，傳統的密碼保密已漸漸的被淘汰，取而代之的，生物辨識技術逐漸被運用在增強系統保密性，現存的生物辨識技術主要有，虹膜、聲音、容貌、指紋，其中指紋最常為人所使用，指紋辨識的優點：方便、精確，不像虹膜辨識必須接觸眼睛容易傳染疾病；聲音容易因情緒而變調；容貌因胖瘦而有改變，且指紋具有唯一性，故指紋已被廣泛的運用在資料保全系統上。
大部分的指紋辨識系統，都是先將指紋影像經過正規化、濾除雜訊、取指紋流向、流向濾波、細線化、偵測奇異點與特徵點，建檔指紋的奇異點及紋線的端點、叉點的分佈位置作為爾後比對的依據。
但遇上龐大的指紋資料庫時，整體的比對效率是最常為人所詬病的，故本論文提出一種新的比對流程來增進比對單元的效率，在一連串有效的影像前處理步驟之後，我們省略細線化直接做特徵擷取，並經由其核心點附近的流向對其做快速的指紋分類建檔，在比對單元方面，會先經由其分類建檔的資料庫來比對，將會大大的改善整個比對單元的辨識效率，在演算法確立且軟體模擬成功之後，我們試著將提出的指紋影像辨識流程硬體化，利用數位訊號處理器(DSP)來實現個人身份辨識系統。

Nowadays, the importance of the information protection and the entrance guard control system have be attached importance to the people. Traditional secret maintaining methods like setting up passwords are eliminated gradually, and the biometric verification technique is to take it over. Biometric verification technique is applied on enhancing the system of maintaining secrecy gradually. Biometric verification techniques which are available now are mainly as follows : iris, voice, appearance, and fingerprint. On account of its precision and convenience, fingerprint is the most wildly-used technique; whereas iris verification may cause transmitted disease because of the contact with eyes, voice may inflect for emotion, appearance maybe changed as weight. What’s more, fingerprints possess exclusive character, therefore, fingerprints have been using on information security system generally.
	Most of the fingerprint verification systems would including normalization, noise filter, calculate fingerprint flow direction, flow filter, thinning, detect the positions of the singular points and minutiae, as a basis for the later verification.
However, the verification efficiency of a huge recognition database is often censorable when encountering. Therefore, this thesis brings up 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. After the confirmation of algorithm and the success of simulation, we try to realize the procedure of fingerprint image verification by hardware, using DSP to achieve personal identity verification system.

目  錄

中文摘要……………………………Ⅰ
英文摘要……………………………Ⅱ
目  錄………………………………Ⅲ
圖目錄………………………………VI
表目錄………………………………XI

第一章、緒  論………………………………1
1.1 研究動機與目的………………………1
1.2 研究背景………………………………2
  1.2.1 指紋背景知識…………………2
  1.2.2 指紋應用範圍…………………3
1.3 研究方向………………………………4
1.4 內容大綱………………………………5
第二章、指紋辨識……………………………6
2.1 指紋影像擷取裝置……………………6
2.2 指紋的特徵……………………………7
2.2.1 指紋宏觀辨認 - 指紋分類………8
2.2.2 指紋細微辨認 - 流向及特徵點…13
2.3 指紋比對種類…………………………16
2.4 本論文提出之比對流程………………17
第三章、系統架構……………………………18
3.1 演算法設計流程	………………………18
3.2 晶片設計流程	………………………26
3.2.1 嵌入式系統	……………………26
3.2.2 DSP系統	……………………29
3.2.2.1 DSP的優點	…………………30
3.2.2.2 C67x DSP晶片………………31
3.2.2.3系統開發整合工具 …………35
3.2.3 系統測試模擬與除錯……………36
3.2.4 產品開發	……………………39
第四章、指紋辨識演算法……………………41
4.1 指紋影像前處理單元…………………42
4.1.1 正規化	……………………43
4.1.2 中值濾波	……………………45
4.1.3 計算指紋流向場…………………48
4.1.4 奇異點偵測	……………………56
4.1.5 影像裁剪	……………………58
4.1.6 二值化	……………………60
4.2 指紋特徵擷取與分類單元……………63
4.2.1 指紋分類	……………………63
4.2.2 特徵擷取	……………………68
4.3 指紋比對辨識單元……………………76
第五章、演算法模擬與硬體實作結果………79
5.1 演算法模擬……………………………79
5.2 硬體實作結果…………………………82
第六章、結論與未來研究方向………………85
6.1 結論……………………………………85
6.2 未來研究方向…………………………85
參考文獻………………………………………87


圖目錄
圖2.1 指紋影像中之紋線與谷線................... 8
圖2.2 指紋影像中之中心點與三角點............... 9
圖2.3（1）平弧紋 （2）帳形紋................... 10
圖2.4（1）左箕形紋（2）右箕形紋................ 11
圖2.5（1）平螺紋（2）囊形紋（3）雙箕螺紋....... 12
圖2.6 雜形紋................................... 12
圖2.7 定義的八個流向........................... 13
圖2.8 指紋影像與其流向圖....................... 13
圖2.9 指紋細微特徵（端點、分叉點、短山脊、交叉點） 14
圖2.10 指紋細微特徵（突刺、點、島、橋點）...... 15
圖2.11 指紋八種細微特徵類型.................... 15
圖3.1 常見之指紋辨識演算法流程圖............... 18
圖3.2 本文之指紋辨識演算法流程圖............... 19
圖3.3 指紋辨識系統之建檔流程圖................. 23
圖3.4 指紋辨識系統之比對辨識流程圖............. 25
圖3.5 典型之嵌入式系統架構..................... 28
VII
圖3.6 C67x™晶片系統方塊圖............................................. 34
圖3.7 TMS320C6713™DSK 的硬體方塊圖............. 35
圖3.8 透過JTAG 連接主機與DSP 系統.............. 37
圖3.9 CCS 的操作畫面........................... 37
圖3.10 CCS 程式開發工具........................ 38
圖3.11 下載程式至DSP 板上...................... 39
圖4.1 指紋辨識演算法流程....................... 41
圖4.2 指紋影像前處理流程....................... 42
圖4.3 (a)原始影像 (b)正規化後影像.............. 45
圖4.4 (a)原始影像灰階值直方圖 (b)正規化後影像灰階值直方圖 45
圖4.5 中值濾波的流程圖......................... 47
圖4.6 (a)正規化後影像 (b)中值化後影像.......... 48
圖4.7 計算指紋流向之流程....................... 49
圖4.8 以8×8 區塊選取指紋影像及找出最黑或最白的五個像素點 50
圖4.9 指紋紋路之八個方向....................... 51
圖4.10 9×9 之流向遮罩.......................... 51
圖4.11 以9×9 流向遮罩套入8×8 區塊中最黑或最白之像素點位置
(a)套入紋線上最黑之像素點 (b)套入谷線上最白之像素點…52
圖4.12 指紋影像經流向判斷後其結果
(a)以最黑與最白三點作流向判斷
(b)以最黑或最白五點作流向判斷................. 54
圖4.13 3×3 流向修正遮罩....................... 55
圖4.14 流向修正的例子......................... 55
圖4.15 指紋流向經流修正後其結果
(a)流向修正前的流向 (b)流向修正後的流向....... 56
圖4.16 Poincare Index 遮罩.................... 57
圖4.17 計算Poincare Index 示意圖.............. 57
圖4.18 奇異點偵測的例子....................... 58
圖4.19 指紋裁剪之示意圖....................... 59
圖4.20 指紋裁剪的例子......................... 59
圖4.21 區域平均臨界值法的8×8 區塊移動示意圖... 61
圖4.22 臨界二值化後的影像..................... 61
圖4.23 改良區域平均臨界值法的9×9 區塊移動示意圖 62
圖4.24 改良式二值化後的影像................... 63
圖4.25 五種指紋分類........................... 64
圖4.26 核心區與流向對稱線示意圖
(a)核心區與流向對稱線 (b)對稱線兩旁的理想流向. 65
圖4.27 左箕紋
(a)指紋圖 (b)以核心區與流向對稱線判斷......... 66
圖4.28 右箕紋
(a)指紋圖 (b)以核心區與流向對稱線判斷......... 66
圖4.29 弧形紋
(a)指紋圖 (b)以核心區與流向對稱線判斷..........67
圖4.30 螺旋紋
(a)指紋圖 (b)以核心區與流向對稱線判斷......... 67
圖4.31 雜形紋
(a)指紋圖 (b)以核心區與流向對稱線判斷......... 68
圖4.32 指紋細線化處理
(a)指紋細線化前 (b)指紋細線化後............... 69
圖4.33 特徵偵測區塊........................... 69
圖4.34 特徵擷取示意圖......................... 71
圖4.35 搜尋後之端點及叉點位置................. 71
圖4.36 指紋特徵修正之遮罩..................... 73
圖4.37 指紋特徵修正之示意圖................... 73
圖4.38 修正後之端點及叉點位置................. 74
圖4.39 紀錄特徵點示意圖
(a)特徵點相對位置 (b)以核心點為圓心切分指紋影像75
圖4.40 特徵點位置
(a)端點位置 (b)叉點位置....................... 75
圖4.41 分類資料庫比對......................... 76
圖4.42 指紋比對辨識成功例子
(a)欲比對辨識指紋 (b)資料庫指紋............... 78
圖5.1 指紋辨識系統實體圖...................... 82
圖5.2 硬體操作流程圖.......................... 83

表目錄
表5.1 指紋分類結果............................ 80
表5.2 與其他論文比較表........................ 81
表5.3 演算法模擬結果.......................... 81
表5.4 與其他論文比較表........................ 84

參考文獻

[1]  D. Maltoni, D. Maio, A. K. Jain and S. Prabhakar, Handbook of Fingerprint Recognition. Springer, New York, 2003.
[2]  呂狀元，“指紋分類系統設計”，淡江大學電機所碩士論文，2000年6月。
[3]  E. R. Henry, Classification and Uses of Finger Prints. Routledge, London, 1900.
[4]  陳俊良，“有效的指紋前處理及分類”，淡江大學資工所碩士論文，2001年6月。
[5]  K. Karu and A. K. Jain, “Fingerprint Classification,” Pattern Recognition, vol. 18, no. 3, 1996, pp. 389-404.
[6]  F. Galton, Finger Prints. Macmillan, London, 1892.
[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]  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.
[18]  探矽工作室，2002嵌入式系統開發聖經，學貫行銷股份有限公司，2002年9月。
[19]  陳宏宇，DSP程式設計，文魁資訊股份有限公司，2004年7月。
[20]  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.
[21]	吳鐵民、鄭伯順、張光耀，中文字形二元化臨界值法則用於光學中文文字識別之研究，電信研究季刊，第20卷第1期，民國79年3月。
[22]	M. Kawagoe and A. Tojo, “Finger Pattern Classification,” Pattern Recognition, vol. 17, no. 3, 1984, pp. 295-303.
[23]  I. Emiroglu and M. B. Akhan, “Pre-processing of Fingerprint Images,” European Conference on Security and Detection, Apr. 1997, pp. 147-151.
[24]	T. Y. Zhang and C. H. Suen, “A Fast Parallel Algorithms for Thinning Digital Pattern,” Comm. ACM, vol. 27, May 1984, pp. 236-239.

[25]	 李建潁，快速特徵搜尋之指紋辨識晶片設計，淡江大學電機所碩士
      論文，民國94年。
[26]	 李釋書，利用嵌入式軟核心處理器之指紋辨識晶片設計與實作，淡
      江大學電機所碩士論文，民國94年。
[27]	 林睿鵬，利用改良式極座標比對法之指紋辨識晶片設計，淡江大學 
      電機所碩士論文，民國94年。