目前用來做為個人身份辨識的生物特徵，已有瞳孔、容貌、指紋等，其中利用指紋來辨識是最常為人所使用的方法之一。它除了擁有辨識所需的唯一性以及不變性之特質外，在價格與效果的整體考量上，比採用其他的生物特徵划算許多，而且在法律的認證上，指紋辨識也佔有重要的地位。所以如何正確地分辨一枚指紋與其他指紋是否相同，在個人身份辨識上是一個很重要的課題。
    從指紋擷取器所獲得的指紋影像，因按捺壓力大小不同以及機器所產生的雜訊，使得指紋影像的品質不如我們所預期地好，造成辨識錯誤的情況發生。本文先將指紋影像做前處理，試圖去增強及還原原始的指紋影像，並提出一個快速的指紋特徵搜尋法，去找出指紋特徵位置座標，再以粒子群最佳化演算法(PSO)，去與資料庫中的指紋做比對，從模擬結果來看，本文之演算法能更正確及快速地辨識個人身份。最後，將所提出之方法，在可程式化之系統晶片(SOPC)上，以嵌入式軟核心處理器來實現，能做到更快速且即時(On-Line)的指紋辨識系統。

Biometric features, such as pupils, faces and fingerprints, have been used to develop the personal identification system at present. Among all of them, the fingerprint identification is one of the most commonly used methods. It has not only the characters of the uniqueness and the time-invariance when recognizing but also lower costs and higher performance while comparing with other biological features. And the fingerprint identification also plays an important role in the legal authentication. Therefore, it is quite an important issue to distinguish accurately fingerprints from the others on the personal identification.
  The quality of the fingerprint image obtained from a sensor is not good as we expect because of the different pressure and the noise caused by the sensor. And it leads to the wrong identification result. In this paper, we first make a series of image pre-processes in order to enhance and restore the original fingerprint image. And then we propose a fast minutiae extraction method to find the coordinates of minutiae. After the minutiae extraction, we use a particle swarm optimization method (PSO) to match the fingerprints in a database. The experimental result shows that the personal identification is more accurate and faster via our algorithm. Finally, we apply our proposal to a system on a programmable chip (SOPC) by using the soft core embedded processor. And we can get a faster and on-line fingerprint identification system.

<<目錄>>
中文摘要.......................................................................................................Ⅰ 
英文摘要.......................................................................................................Ⅱ 
目錄.............................................................................................................Ⅲ 
圖目錄..........................................................................................................Ⅵ 
表目錄.......................................................................................................ⅩⅡ
 
第一章、序論.................................................................................................1 
1.1 前言.........................................................................................................1 
1.2 指紋辨識之發展歷史..................................................................................2 
1.3 指紋辨識之優點 ........................................................................................3 
1.4 指紋辨識之應用方向..................................................................................4 
1.5 研究方向..................................................................................................5 
1.6 內容大綱...................................................................................................6 
第二章、相關背景...........................................................................................8 
2.1 指紋影像擷取裝置......................................................................................8 
2.2 指紋影像之特徵 .......................................................................................10 
2.2.1 指紋影像之宏觀辨認...............................................................................11 
2.2.2 指紋影像之微觀辨認...............................................................................13 
2.3 指紋影像之比對種類..................................................................................15 
2.4 SOPC系統...............................................................................................17 
2.4.1 SOPC系統之發展流程............................................................................19 
2.4.2 硬體設計解決方案..................................................................................20 
2.4.3 軟體設計解決方案..................................................................................21 
2.4.4 量產轉移程序(Migration Process)............................................................22 
第三章、系統架構..........................................................................................23 
3.1 演算法設計流程 .......................................................................................23 
3.2 晶片設計流程...........................................................................................31 
第四章、指紋影像前處理單元..........................................................................43 
4.1 裁減影像.................................................................................................44 
4.2 正規化處理..............................................................................................47 
4.3 中值濾波處理...........................................................................................49 
4.4 計算指紋流向場........................................................................................51 
4.5 修正指紋流向場........................................................................................57 
4.6 Gabor濾波二值化......................................................................................63 
第五章、指紋特徵搜尋單元與指紋特徵比對單元................................................74 
5.1 指紋特徵搜尋單元.....................................................................................75 
5.2 指紋特徵比對單元.....................................................................................83 
5.2.1 粒子群最佳化演算法(PSO)......................................................................83 
5.2.2 應用PSO於指紋最佳變形量之搜尋...........................................................88 
第六章、系統模擬與實作結果..........................................................................97 
6.1 系統模擬..................................................................................................97 
6.2 實作結果................................................................................................101 
第七章、結論與未來研究方向........................................................................106 
7.1 結論......................................................................................................106 
7.2 未來研究方向.........................................................................................107 
參考文獻.....................................................................................................108 


<<圖目錄>> 
圖2.1 指紋影像中之紋線與谷線........................................................................10 
圖2.2 指紋影像中之中心點與三角點..................................................................11 
圖2.3 指紋影像與其流向圖...............................................................................14 
圖2.4 指紋影像中之細微特徵(端點、叉點).........................................................15 
圖2.5 SOPC系統之發展流程圖.........................................................................20 
圖3.1 指紋辨識系統之主體架構圖.....................................................................23 
圖3.2 指紋辨識系統之建檔流程圖.....................................................................28 
圖3.3 指紋辨識系統之比對流程圖.....................................................................30 
圖3.4 指紋辨識晶片系統之設計流程圖 
(a)硬體模組設計流程 (b)應用程式軟體設計流程..................................................34 
圖3.5 指紋辨識晶片系統之架構圖.....................................................................34 
圖3.6 SOPC Builder之系統內容.......................................................................35 
圖3.7 SOPC系統合成產生之完成圖..................................................................39 
圖3.8 完成後之指紋辨識晶片系統硬體模組(bdf檔) .............................................40 
圖3.9 下載組成資料(sof檔)至StratixTM晶片中....................................................41 
圖3.10 下載可執行檔(srec檔)至發展板中...........................................................42 
圖4.1 指紋影像前處理之流程圖........................................................................43 
圖4.2 裁減指紋影像之示意圖...........................................................................46 
圖4.3 裁減指紋影像 
(a)原始指紋影像 (b)裁減後之指紋影像(208×208)................................................46 
圖4.4 正規化指紋影像 
(a)正規化指紋影像前 (b)正規化指紋影像後........................................................49 
圖4.5 中值濾波處理之例子..............................................................................50 
圖4.6 中值濾波處理指紋影像 
(a)中值濾波處理指紋影像前 (b)中值濾波處理指紋影像後.....................................51 
圖4.7 流向計算之細部處理動作........................................................................52 
圖4.8 指紋紋線之八個方向..............................................................................53 
圖4.9 9×9之空間遮罩......................................................................................53 
圖4.10 以8×8遮罩選取指紋影像.......................................................................54 
圖4.11 尋找此區塊最黑與最白之像素點位置......................................................54 
圖4.12 以9×9遮罩代入最黑與最白之像素點位置 
(a)代入最黑之像素點位置 (b)代入最白之像素點位置...........................................54 
圖4.13 計算指紋影像流向場 
(a)指紋影像及其流向場 (b)指紋流向場..............................................................57 
圖4.14 指紋流向場修正演算法.........................................................................58 
圖4.15 指紋流向場修正法－Step MO 1例子......................................................59 
圖4.16 修正指紋流向場－Step MO 1 
(a)指紋流向場修正前 (b)指紋流向場修正後........................................................60 
圖4.17 指紋流向場修正法－Step MO 2例子......................................................61 
圖4.18 修正指紋流向場－Step MO 2 
(a)指紋流向場修正前 (b)指紋流向場修正後........................................................62 
圖4.19 修正指紋流向場(含指紋影像) 
(a)指紋流向場修正前 (b)指紋流向場修正後........................................................62 
圖4.20 修正指紋流向場 
(a)指紋流向場修正前 (b)指紋流向場修正後........................................................63 
圖4.21 定義Gabor遮罩各方向角度....................................................................64 
圖4.22 以22.5度為一區間之各角度Gabor方向空間遮罩圖 
(a)0度之Gabor空間遮罩 (b)22.5度之Gabor空間遮罩 
(c)45度之Gabor空間遮罩 (d)67.5度之Gabor空間遮 
(e)90度之Gabor空間遮罩 (f)112.5度之Gabor空間遮罩.........................................65 
圖4.22 以22.5度為一區間之各角度Gabor方向空間遮罩圖(續) 
(g)135度之Gabor空間遮罩 (h)157.5度之Gabor空間遮罩......................................66 
圖4.23 以22.5度為一區間之各角度Gabor方向遮罩灰階圖 
(a)0度之Gabor遮罩灰階圖 
(b)22.5度之Gabor遮罩灰階圖 
(c)45度之Gabor遮罩灰階圖 
(d)67.5度之Gabor遮罩灰階圖..........................................................................66 
圖4.23 以22.5度為一區間之各角度Gabor方向遮罩灰階圖(續) 
(e)90度之Gabor遮罩灰階圖 
(f)112.5度之Gabor遮罩灰階圖 
(g)135度之Gabor遮罩灰階圖 
(h)157.5度之Gabor遮罩灰階圖........................................................................67 
圖4.24 Gabor濾波二值化之例子......................................................................67 
圖4.25 改良式Gabor空間遮罩(0度) .................................................................69 
圖4.26 Gabor各方向之遮罩灰階圖與改良式遮罩灰階圖 
(a)0度 (b)22.5度 (c)45度 (d)67.5度 
(e)90度 (f)112.5度 (g)135度 (h)157.5度.............................................................70 
圖4.27 改良式Gabor濾波二值化 
(a)Gabor濾波二值化指紋影像前 
(b)Gabor濾波二值化指紋影像後......................................................................72 
圖4.28 二值化效果之比較圖...........................................................................73 
圖4.29 二值化效能之比較圖...........................................................................73 
圖5.1 指紋特徵搜尋單元及指紋特徵比對單元...................................................74 
圖5.2 指紋細線化處理 
(a)指紋細線化前 (b)指紋細線化後....................................................................75 
圖5.3 區域示意圖..........................................................................................76 
圖5.4 搜尋後之端點及叉點位置 
(a)二值化影像 (b)二值化影像及指紋特徵位置...................................................78 
圖5.5 指紋特徵修正之示意圖.........................................................................79 
圖5.6 修正後之端點及叉點位置 
(a)修正前 (b)修正後.......................................................................................80 
圖5.7 合併端點及叉點 
(a)合併前 (b)合併後.......................................................................................81 
圖5.8 最後所取出之20個指紋特徵位置 
(a)取出前 (b)取出後.......................................................................................82 
圖5.9 PSO執行流程圖...................................................................................87 
圖5.10 定義粒子群搜尋空間分量.....................................................................89 
圖5.11 PSO點比對流程圖..............................................................................90 
圖5.12 相同指紋比對 
(a)儲存於資料庫中之指紋...............................................................................91 
(b)欲比對之輸入指紋.....................................................................................92 
圖5.13 相同指紋比對之每回合最佳能量值........................................................93 
圖5.14 相異指紋比對 
(a)儲存於資料庫中之指紋 
(b)欲比對之輸入指紋.....................................................................................94 
圖5.15 相異指紋比對之每回合最佳能量值........................................................95 
圖6.1 24枚指紋影像圖 
(a)A_1、A_2、A_3 (b)B_1、B_2、B_3 
(c)C_1、C_2、C_3 (d)D_1、D_2、D_3 
(e)E_1、E_2、E_3 (f)F_1、F_2、F_3 
(g)G_1、G_2、G_3 (h)H_1、H_2、H_3..........................................................98 
圖6.2 指紋辨識系統之整體操作流程圖...........................................................103 
圖6.3 指紋辨識系統之實體外觀圖..................................................................104 


<<表目錄>> 
表3.1 硬體乘法器時脈週期之比較表................................................................36 
表5.1 相同指紋比對之座標.............................................................................92 
表5.2 相同指紋比對之結果.............................................................................93 
表5.3 相異指紋比對之座標.............................................................................95 
表5.4 相異指紋比對之結果.............................................................................96 
表6.1 比對結果統計表....................................................................................99 
表6.2 與其他論文比較表...............................................................................105

[1] The Biometric Report, SJB Services, 1995, p. 47.
[2] F. Galton, Fingerprints, Macmillan London, 1892.
[3] E. R. Henry, Classification and Uses of Finger Prints, Rutledge, London, 1900.
[4] 彭韻瑞，手指紋大分類法之研究，中原大學電子所碩士論文，民國86年。
[5] 李宗瀚，即時指紋辨識演算法，輔仁大學資工所碩士論文，民國90年。
[6] 國際指紋識別競賽(Fingerprint Verification Competition，FVC2000)之指紋資料庫，http://bias.csr.unibo.it/fvc2000/。
[7] 呂狀元，指紋分類系統設計，淡江大學電機所碩士論文，民國89年。
[8] A. K. Hrechak and J. A. Mchugh, “Automated Fingerprint Recognition using Structural Matching,” Pattern Recognition, vol. 23, no. 8, 1990, pp.  893-904.
[9] A. Grasselli, “On the automatic classification of fingerprints some consideration on the linguistic interpretation of pictures,” Methodologies of Pattern Recognition, pp. 253-273.
[10] B. Moayer and K. S. Fu, “An application of stochastic languages to fingerprint pattern recognition,” Pattern Recognition, vol. 8, 1976, pp.  173-179.
[11] B. Moayer and K. S. Fu, “A Tree System Approach for Fingerprint Pattern Recognition,” IEEE Transition on Computers, vol. C-25, no. 3, Mar. 1976, pp. 262-274.
[12] C. C. Kameswara Rao and K. Black, “Finding the Core Point in a Fingerprint,” IEEE Transaction on Computers, vol. C-27, no. 1, Jan. 1978, pp. 77-81.
[13] M. Kawagoe and A. Tojo, “Fingerprint Pattern Classification,” Pattern Recognition, vol. 17, no. 3, 1984, pp. 195-303.
[14] M. K. Sparrow and P. J. Sparrow, “A Topological Approach to the Matching of Single Fingerprints: Development of Algorithms for Use on Rolled Impressions,” NBS Special Publication 500-124, May 1985.
[15] T. C. Malleswara Rao, “Feature Extraction for Fingerprint Classification,” Pattern Recognition, vol. 8, 1976, pp. 181-192.
[16] C. V. Kameswara Rao, “On Fingerprint Recognition,” Pattern Recognition, vol. 10, 1978, pp. 15-18.
[17] Automated Fingerprint Identification System, NEC.
[18] D. K. Isenor and S. G. Zaky, “Fingerprint Identification Using Graph Matching,” Pattern Recognition, vol. 19, no. 2, 1986, pp. 13-122.
[19] S. Knapp, and D. Tavana, “Field Configurable System-on-Chip device architecture,” Proceedings of IEEE Custom Integrated Circuits Conference, Orlando, FL, U.S.A., 2000, pp. 155-158.
[20] W. H. Wolf, “Hardware-software co-design of embedded systems,” Proceedings of the IEEE, vol. 82, no. 7, July 1994, pp. 967-989.
[21] 蕭如宣，“SOPC系統設計”，儒林圖書公司，民國92年。
[22] B. Dalay, “Accelerating system performance using SOPC builder,” Proceedings of IEEE International Symposium on System-on-Chip, Nov. 2003.
[23] 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, Dec. 2002, pp. 276-283.
[24] 鄭惠文，設計電力品質指標計用之模糊邏輯晶片，淡江大學電機所碩士論文，民國93年。
[25] 王仁舜，設計電力品質干擾事件之辨識晶片，淡江大學電機所碩士論文，民國93年。
[26] 陳俊良，有效的指紋前處理及分類，淡江大學資工所碩士論文，民國90年。
[27] L. Hong, Y. Wan and A. Jain, “Fingerprint Image Enhancement Algorithm and Performance Evaluation,” IEEE Transactions on Pattern Analysis and Matching Intelligence, vol. 20, no. 8, Aug. 1998.
[28] 丁鎮權，指紋辨識系統設計，淡江大學電機所碩士論文，民國92年。
[29] 林家慶，利用嵌入式軟核心處理器之指紋辨識系統，淡江大學電機所碩士論文，民國93年。
[30] 繆紹綱，“數位影像處理 活用Matlab”，全華科技圖書股份有限公司，民國88年3月。
[31] 吳鐵民、鄭伯順、張光耀，中文字形二元化臨界值法則用於光學中文文字識別之研究，電信研究季刊，第20卷第1期，民國79年3月。
[32] J. R. Parker, “Algorithms for image processing and computer vision,” wiley, 1996.
[33] T. Y. Zhang and C. H. Suen, “A Fast Parallel Algorithms for Thinning Digital Pattern,” Comm. ACM, vol. 27, May 1984, pp. 236-239.
[34] R. C. Eberhart and J. Kennedy, “A New Optimizer Using Particle Swarm Theory,” Proceedings of the Sixth International Symposium on Micro Machine and Human Science IEEE service center, Piscataway, NJ, Nagoya, Japan, 1995, pp. 39-43.
[35] K. Hara, M. Kimura and N. Honda, “A Method for Planning Economic Unit Commitment and Maintenance of Thermal Power Systems,” IEEE Transactions on Power Apparatus and Systems, vol. PAS-85, no. 5, 1996, pp. 427-436.
[36] 胡曉輝，粒子群優化算法介紹，民國91年4月，http://web.ics.purdue.edu/~hux/tutorials.shtml。
[37] Y. Shi and R. Eberhart, “A Modified Particle Swarm Optimizer,” IEEE World Congress on Computational Intelligence, May 1998, pp. 69-73.
[38] 陳慶翰、許世賢、曾俊傑、徐子恆，基於粒子群最佳化之模糊推論系統適應性學習，中華民國模糊協會2001年研討會(CFSAT2001)。
[39] C. K. Zhang, Y. Li and H. H. Shao, “A New Solved Artificial Neural Network and Its Application,” Proceedings of the 3rd World Congress on Intelligent Control and Automation, vol. 2, 2000, pp. 1065-1068.
[40] 趙維義，應用粒子最佳演算法於發電機組維修排程之研究，淡江大學電機所碩士論文，民國93年。
[41] 曾俊傑，一個智慧型指紋辨識系統設計方法論，義守大學電機所碩士論文，民國90年。
[42] 謝佳銘，嵌入式SoC-Based監視系統之設計實現，成功大學製造工程研究所碩士論文，民國91年。
[43] 吳家頎，指紋辨識的系統晶片，台灣科技大學資工所碩士論文，民國92年。
[44] 葉健福，SOPC為基礎之永磁同步馬達遠端監控系統設計，國防大學中正理工學院電子所碩士論文，民國92年。