傳統上，我們常用密碼來限制保全系統的存取權。然而當密碼外洩時，保全系統將會輕易的被破解。隨著科技的進步，生物特徵被用來改善這個系統保密的問題。在生物特徵辨識的領域中，指紋因為本身的唯一性和不變性而具有相當高的可靠度。此外，指紋辨識系統開發成本較低、使用方便等種種優越之處使得它已被廣泛的運用在資料保全系統上。
    大部分的指紋辨識方法是以指紋的奇異點及紋線的端點、叉點的分佈位置、數目作為判別的依據。而擷取到的指紋影像與資料庫中的資料之間多少都會存在旋轉量與偏移量，因此會造成特徵點座標偏移的產生。為修正此偏移誤差，一般做法是將特徵點座標作多次固定角度的旋轉計算之後，再一一與資料庫中的特徵點資料做歐氏距離計算，此方法不僅無效率而且修正後的準確性也有進步的空間。
    本論文提出一種新的比對方法來增進比對單元的效率，在一連串有效的影像前處理步驟之後進行特徵擷取，我們利用不同特性特徵點相對的關係作進一步的處理，並以經過特殊處理的特徵值作為兩枚指紋之間比對及判斷的依據，在演算法確立且軟體模擬成功之後，我們試著將提出的指紋影像辨識流程硬體化，利用Nios嵌入式處理器來實現個人身份辨識系統。

Traditionally, passwords have used to restrict access to secure system. However, security can be easily discredited in these systems when a password is leaked to an unauthorized user. With the growth of technology, biometric features are used to solve the problems in traditional identification system. In the field of biometric identification, fingerprints have one of the highest levels of reliability because of the uniqueness and invariability. Besides, fingerprint identification systems are also cost-effective, convenient and have been extensively used in data security systems.
  Most identification methods are dependent on the locations and numbers of ridge endings and bifurcations. The extracted fingerprint impressions usually have translation and rotation in different times which cause the coordinates of minutiae change. In order to align the position variance, the minutiae information is rotated a constant angle in several times and calculate the Euclidean Distance between query and database information. This method is inefficient and the accuracy needs to be improved.
  In this thesis, we propose a novel matching scheme to improve the efficiency of matching. After the pre-processing steps, the minutiae are extracted. We use the relation of minutiae as the information to identify fingerprint impressions. When the algorithm is simulated successfully, we implement it to build an automatic fingerprint identification system via a Nios embedded processor.

中文摘要...................................................................................................................Ⅰ 
英文摘要...................................................................................................................Ⅱ 
目  錄........................................................................................................................Ⅲ 
圖目錄......................................................................................................................Ⅵ 
表目錄......................................................................................................................Ⅸ 
第一章 序 論...............................................................................................................1 
1.1 前  言....................................................................................................................1 
1.2 指紋如何用於辨識.................................................................................................2 
1.3 指紋辨識之優點....................................................................................................3 
1.4 指紋辨識的應用方向..............................................................................................5 
1.5 本文研究方向........................................................................................................7 
1.6 內容大綱..............................................................................................................8 
第二章 指紋辨識相關技術............................................................................................9 
2.1 指紋的特徵...........................................................................................................9 
2.1.1 指紋的紋線與谷線..............................................................................................9 
2.1.2 指紋的流向........................................................................................................9 
2.1.3 指紋的奇異點...................................................................................................10 
2.1.4 指紋的特徵點...................................................................................................15 
2.2 指紋比對方式......................................................................................................17 
2.3 指紋擷取裝置......................................................................................................18 
2.4 生物辨識系統的複合式應用...................................................................................20 
第三章 SOPC嵌入式系統...........................................................................................23 
3.1 嵌入式系統..........................................................................................................23 
3.2 嵌入式系統之硬體組成架構...................................................................................26 
3.2.1 嵌入式系統微處理器..........................................................................................26 
3.2.2 記憶體..............................................................................................................29 
3.2.3 傳輸介面..........................................................................................................29 
3.3 嵌入式系統軟體開發.............................................................................................30 
3.4 SOPC系統...........................................................................................................32 
3.4.1 SOPC設計流程.................................................................................................33 
3.4.2 硬體設計方案....................................................................................................34 
3.4.2.1 SOPC晶片.....................................................................................................34 
3.4.2.2 SOPC組成架構...............................................................................................35 
3.4.2.3 EDA硬體發展工具...........................................................................................37 
3.4.3 軟體設計方案....................................................................................................39 
3.4.4 量產轉移程序....................................................................................................39 
第四章 指紋辨識方法與理論........................................................................................41 
4.1 指紋辨識演算法流程.............................................................................................41 
4.2 正規化.................................................................................................................42 
4.3 改良式奇異點偵測法.............................................................................................44 
4.4 影像裁剪..............................................................................................................54 
4.5 二值化.................................................................................................................56 
4.6 細線化.................................................................................................................58 
4.7 特徵點偵測...........................................................................................................62 
4.8 簡化極座標表示法.................................................................................................64 
4.9 特徵比對..............................................................................................................66 
第五章 系統設計與實現...............................................................................................69 
5.1 Nios辨識系統硬體設計流程....................................................................................69 
5.1.1 設計系統模組.....................................................................................................70 
5.1.2 系統編譯...........................................................................................................75 
5.1.3 下載規劃Stratix晶片...........................................................................................76 
5.2 Nios辨識系統軟體設計流程....................................................................................77 
5.2.1 確立辨識系統作業流程........................................................................................77 
5.2.2 應用程式設計....................................................................................................79 
第六章 模擬與實作結果...............................................................................................82 
6.1 演算法模擬結果....................................................................................................82 
6.2 系統實作結果........................................................................................................84 
第七章 結論與展望......................................................................................................87 
7.1 結  論....................................................................................................................87 
7.2 未來研究方向........................................................................................................87 
參考文獻....................................................................................................................89 

圖2.1 指紋影像中之紋線與谷線......................................................................................9 
圖2.2 定義的八個流向.................................................................................................10 
圖2.3 指紋影像與其流向圖..........................................................................................10 
圖2.4 指紋影像中的核心點與三角點.............................................................................11 
圖2.5 （a）平弧紋（b）帳形紋...................................................................................12 
圖2.6 （a）左箕形紋（b）右箕形紋.............................................................................13 
圖2.7 （a）平螺紋（b）囊形紋（c）雙箕螺紋..............................................................14 
圖2.8 雜形紋.............................................................................................................14 
圖2.9 指紋細微特徵（端點、分叉點、短山脊、交叉點）................................................15 
圖2.10 指紋細微特徵（突刺、點、島、橋點）..............................................................16 
圖2.11 指紋的八種細微幾何特徵..................................................................................16 
圖2.12 複合式生物辨識系統.........................................................................................21 
圖3.1 典型之嵌入式系統架構.......................................................................................25 
圖3.2 系統設計與評估.................................................................................................31 
圖3.3 SOPC設計流程.................................................................................................34 
圖4.1 指紋辨識演算法的處理流程圖.............................................................................42 
圖4.2 （a）原始影像（b）灰階分布長方圖...................................................................43 
圖4.3 （a）正規化處理後的影像（b）灰階分布長方圖...................................................44 
圖4.4 梯度遮罩..........................................................................................................45 
圖4.5 梯度與流向.......................................................................................................46 
圖4.6 （a）餘弦的正負變化（b）正弦的正負變化.........................................................48 
圖4.7 （a）Xij矩陣的正負變化圖（b）Yij矩陣的正負變化圖............................................48 
圖4.8 （a）PXij矩陣的正負變化圖（b）PYij矩陣的正負變化圖........................................49 
圖4.9 （a）對PXij使用5×5平均濾波器...........................................................................50 
      （b）對PYij使用5×5平均濾波器...................................................................................50 
圖4.10 （a）對PXij使用7×7平均濾波器.........................................................................50 
       （b）對PYij使用7×7平均濾波器...................................................................................50 
圖4.11 （a）3×3遮罩找到的過渡曲線點轉換回原灰階像素的座標....................................51 
       （b）2×2遮罩找到的過渡曲線點轉換回原灰階像素的座標...............................................51 
圖4.12 （a）3×3遮罩找到的過渡曲線...........................................................................51 
       （b）2×2遮罩找到的過渡曲線.....................................................................................51 
圖4.13 （a）把三角點的PXij和PYij梯度方向作座標轉換.................................................52 
       （b）把核心點的PXij和PYij梯度方向作座標轉換...........................................................53 
圖4.14 判斷出的核心點與三角點位置...........................................................................54 
圖4.15 （a）可順利裁剪之影像...................................................................................55 
       （b）核心點太過靠近影像邊緣的情況..........................................................................55 
圖4.16 裁剪後的影像..................................................................................................55 
圖4.17 區域平均臨界值法的8×8區塊移動過程................................................................57 
圖4.18 二值化後的影像...............................................................................................57 
圖4.19 中值濾波處理後的二值化影像...........................................................................58 
圖4.20 3×3之細線化遮罩區塊......................................................................................59 
圖4.21 邊界像素點平滑條件，x表示該像素點被標記過...................................................60 
圖4.22 細線化之前不使用中值濾波的執行結果...............................................................61 
圖4.23 （a）不使用條件Ⅲ（b）完整的 細線化執行結果................................................62 
圖4.24 特徵點偵測結果...............................................................................................63 
圖4.25 誤判的特徵點（a）斷點（b）橋點（c）突刺點...................................................63 
圖4.26 消除誤判特徵點之後的結果...............................................................................64 
圖4.27 極座標表示法的誤差範圍..................................................................................65 
圖4.28 （a）端點對應的扇形區域（b）叉點對應的扇形區域...........................................66 
圖4.29 指紋比對成功範例............................................................................................68 
圖5.1 辨識系統硬體方塊圖..........................................................................................69 
圖5.2 SOPC Builder元件模組設定內容.........................................................................71 
圖5.3 Nios的系統設定................................................................................................72 
圖5.4 SOPC系統產生圖..............................................................................................73 
圖5.5 硬體模組之BDF檔.............................................................................................74 
圖5.6 系統模組編譯完成之編譯報告.............................................................................75 
圖5.7 完成下載規劃Stratix晶片....................................................................................76 
圖5.8 指紋辨識系統之建檔流程圖................................................................................78 
圖5.9 指紋辨識系統之比對流程圖................................................................................79 
圖5.10 軟體編譯完成..................................................................................................81 
圖6.1 系統實體照片....................................................................................................84 
圖6.2 指紋辨識系統操作流程圖....................................................................................85
 
表3.1 Nios嵌入式處理器晶片與軟體支援.......................................................................35 
表6.1 模擬結果...........................................................................................................83 
表6.2 演算法比較結果.................................................................................................86

[1]  K. Karu and A. K. Jain, “Fingerprint Classification,” Pattern Recognition, vol. 18, no. 3, 1996, pp. 389-404.
[2]  呂狀元，“指紋分類系統設計”，淡江大學電機所碩士論文，2000年6月。
[3]  E. R. Henry, Classification and Uses of Finger Prints. Routledge, London, 1900.
[4]  陳俊良，“有效的指紋前處理及分類”，淡江大學資工所碩士論文，2001年6月。
[5]  F. Galton, Finger Prints. Macmillan, London, 1892.
[6]  A. K. Hrechak and J. A. Mchugh, “Automated Fingerprint Recognition using Structural Matching,” Pattern Recognition, vol. 23, no. 8, 1990, pp. 893-904.
[7]  D. Maltoni, D. Maio, A. K. Jain and S. Prabhakar, Handbook of Fingerprint Recognition. Springer, New York, 2003.
[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]  探矽工作室，2002嵌入式系統開發聖經，學貫行銷股份有限公司，2002年9月。
[18]  蕭如宣，SOPC系統設計，儒林圖書有限公司，2003年6月。
[19]  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.
[20]  P. Ramo, M. Tico, V. Onnia and J. Saarinen, “Optimized Singular Point Detection Algorithm for Fingerprint Images,” in Proceedings of ICIP 2001, 2001 IEEE International Conference on Image Processing, Oct. 2001, Thessaloniki, Greece, pp. 242-245.
[21]  R. C. Gonzalez and R. E. Woods, Digital Image Processing, 2nd ed. Prentice Hall, 2002.
[22]  I. Emiroglu and M. B. Akhan, “Pre-processing of Fingerprint Images,” European Conference on Security and Detection, Apr. 1997, pp. 147-151.
[23]  R. W. Zhou, C. Quek, G. S. Ng, “A Novel Single-Pass Thinning Algorithm and an Effective Set of Performance Criteria,” Pattern Recognition Letters, 1995, vol.16, no. 12, pp. 1267-1275.
[24]  T. Mansfield and G. Roethenbaugh. (1999). 1999 Glossary of Biometric Terms. [Online]. Avaliable: 
http://www.afb.org.uk/downloads/glossary.pdf
[25]  林家慶，“利用嵌入式軟核心處理器之指紋辨識系統”，淡江大學電機所碩士論文，2004年6月。