近年來，在這多元化的社會中，人們生活方式也越來越複雜，在很多情況下，安全保密以及身分辨識是ㄧ項相當重要的課題。早期是使用密碼和鑰匙來當作個人的保密工具，印章和簽名來當作身分辨識，但是這類的工具存在著不方便性、易遺失、遺忘、盜用等問題因素。
    由於人的身體特徵具有不可複製的特點，因此學者們都在探討，能否以生物特徵來當作個人身份識別的工具？在生物識別的領域中，指紋因為本身的唯一性和不變性而具有相當高的可靠度。此外，指紋辨識系統開發成本較低，使用方便等種種優越之處使得他已被廣泛的運用在資料保全系統上。
    大部分的指紋辨識方法是以指紋的奇異點(核心點、三角點)及紋線特徵點(端點、叉點)的分布位置、數目作為判別的依據。而若能將指紋流向場精確的求得，那要擷取出特徵點以及核心點將是ㄧ件容易的事情。因此許多學者都提出了計算流向的方法，最常用的方法不外乎Stock與Swonger所提出的Slite-Sum，以及利用梯度方向來得到的指紋流向。
    一般的指紋影像處理方式都是先將指紋影像經過背景去除、正規化、濾除雜訊、取指紋流向、流向的修正、Gabor濾波二値化、特徵點的搜尋與擷取以及最後的建檔與比對。但遇上龐大的指紋資料庫時，整體的比對效率是最常為人所詬病的，故本文提出ㄧ種新的指紋流向演算法(模糊聚類)來計算指紋流向場，以便更精確的擷取指紋中心核心點及修正指紋的偏移量與旋轉量，最後利用計算流向場所得到的歸屬度去做建檔或利用歐式距離的計算來做指紋資料庫比對，這將會大幅提升指紋辨識精確度以及未來實現在指紋辨識硬體方面的效率與準確性。

Now, people’s life are getting more and more complicated in this diversified society. In many situations, keeping secret safely and identifying recognition are quite important. In early days, people kept secret by using secret code and keys and recognized identifications by seals and signatures. But these ways are inconvenient and easily lost, forgotten and stolen.
  Because the characters of human bodies can not be copied, scientists have explored the possibility of biological characteristics as a personal identification tool. In the field of Biometric recognitions, fingerprints because of their own uniqueness and invariance which have very high reliability. And it has widely used in protection systems because of the advantage of the lower development cost. 
  Most identification methods depend on the locations and numbers of ridge endings and bifurcations. If we can get the fingerprint flow field exactly, it will be easy to find out the minutiae and singular points. As the result, there are many scholars propose many ways to calculate flow. The ways mostly used are Slite-Sum methods proposed by Stock and Swonger. The fingerprint flow is got by using gradient.
  Most of the fingerprint verification systems would including normalization, noise filter, calculate fingerprint flow direction, Gabor filter, detect the positions of the singular points and minutiae, as a basis for the later verification. But, if we have a huge database of fingerprint, the whole efficiency of compare is the most frequently denounced, therefore, here is a new fingerprint flow algorithm bring up in this thesis to compute the fingerprint flow field, for the purpose of selecting fingerprint core more accurate and correcting the offset and rotation of the fingerprint, in the end, use the membership grade by calculate flow field to set up file or use the compute of Euclidean distance to build up the compare of the fingerprint database, that will promote the accuracy by a wide margin and accomplish the efficiency and the accuracy in the hardware of the fingerprint identification in the future.

目錄

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

第一章、緒論.................................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 指紋影像之特徵.......................9
    2.2.1 指紋影像之宏觀辨認.........10
    2.2.2 指紋影像之微觀辨認.........13
2.3 指紋影像之比對種類...................16
第三章、模糊理論與模糊聚類基本介紹...........18
3.1 模糊（Fuzzy）理論....................18
3.2 模糊集合理論.........................19
3.3 模糊聚類分析.........................24
    3.3.1 硬式c-分群演算法...........26
    3.3.2 硬式c-平均值演算法.........27
    3.3.3 模糊c-平均值演算法.........29
第四章、指紋影像處理與比對驗證...............32
4.1 背景去除.............................33
4.2 正規化與中值濾波處理.................37
    4.2.1 正規化處理.................37
    4.2.2 中值濾波處理...............39
4.3 計算指紋流向場.......................42
    4.3.1 Slite-Sum法................43
    4.3.2 梯度法.....................45
    4.3.3 流向場之改良...............46
4.4 參考點擷取與指紋影像剪裁.............51
    4.4.1 Sine Component Map.........52
    4.4.2 指紋影像剪裁...............53
4.5 偏移量與旋轉量修正...................55
4.6 比對驗證.............................57
第五章、模擬比較結果.........................59
5.1 流向場之模擬比較.....................59
第六章、結論與未來研究方向...................65
6.1 結論.................................65
6.2 未來研究方向.........................66
參考文獻.....................................68

圖目錄

圖2.1 指紋影像中之紋線與谷線.............9
圖2.2 指紋影像中之中心點與三角點.........10
圖2.3 帳形類.............................11
圖2.4 平弧紋.............................11
圖2.5 左箕形紋...........................12
圖2.6 右箕形紋...........................12
圖2.7 螺旋形.............................12
圖2.8 流向的八個方向.....................14
圖2.9 指紋影像[6]與其流向圖..............14
圖2.10 指紋細微特徵......................15
圖2.11 指紋影像中之細微特徵(端點、叉點)..16
圖3.1  明確集合..........................20
圖3.2  模糊集合..........................20
圖4.1 指紋辨識系統之主體架構圖...........32
圖4.2 含大量背景之指紋圖.................33
圖4.3 (a) 初步指紋背景去除 (b) 完整指紋背景去除....34
圖4.4 背景去除流程圖.....................34
圖4.5 修正背景去除遮罩一.................36
圖4.6 修正背景去除遮罩二.................36
圖4.7 正規化流程圖.......................37
圖4.8 (a)原圖 (b)背景去除和正規化後......39
圖4.9 (a)胡椒鹽式雜訊圖 (b)經過中值濾波的圖...40
圖4.10 (a)原始矩陣 (b)排序後矩陣.........40
圖4.10 (c)中值濾波後矩陣.................41
圖4.11 (a)未經中值濾波 ..................41
圖4.11 (b)中值濾波後.....................42
圖4.12 指紋紋路的八種方向................43
圖4.13 Slite-sum之 遮罩..................44
圖4.14 (a)  Sobel運算式 (b) Gx (c) Gy....45
圖4.15流向分類法流程圖	47
圖4.16 (a)第一類 (b)第二類 (c)第三類 (d )第四類....48
圖4.17 區塊二值化圖......................49
圖4.18 區塊反白圖........................49
圖4.19參考點三角形遮罩...................52
圖4.20 右旋類參考點示意圖................53
圖4.21 弧形類參考點示意圖................53
圖4.22 參考點靠中央的情況................54
圖4.23 參考點靠左邊的情況................54
圖4.24 (a)參考點中央時的影像剪裁 (b)參考點左邊時的影像剪裁....55
圖4.25一般手指壓下無偏轉的情況...........56
圖4.26 (a)參考點下方的區域流向 (b)原指紋流向 (c)轉修正後方向.......................................56
圖4.27 Tented Arch類與其參考點下方區域之流向.....57
圖5.1 各流向法比較模擬圖.................61
圖5.2 各流向法比較模擬圖.................62
圖5.3 各流向法比較模擬圖.................63

表目錄

表5.1 流向法比較表.......................60
表5.2 修正後流向法比較表.................64

參考文獻

[1] 	A. K. Hrechak and J. A. Mchugh, “Automated Fingerprint Recognition Using Structural Matching,” Pattern Recognition, vol. 23, no. 8, 1990, pp. 893-904.
[2]  蕭志豪，改良式多級指紋比對演算法指紋辨識晶片設計，民國95年。
[3]  劉政衛，改良式流向法之指紋辨識系統設計，民國95年。
[4]	彭韻瑞，手指紋大分類法之研究，中原大學電子所碩士論文，民國86年。
[5]	The Biometric Report, SJB Services, 1995, p. 47.
[6]	F. Galton, Fingerprints, Macmillan London, 1892.
[7]  E. R. Henry, Classification and Uses of Finger Prints, Rutledge, London, 1900.
[8]	李宗瀚，即時指紋辨識演算法，輔仁大學資工所碩士論文，民國90年。
[9]	國際指紋識別競賽(Fingerprint Verification Competition，FVC2000)之指紋資料庫，http://bias.csr.unibo.it/fvc2000/。
[10] 	呂狀元，指紋分類系統設計，淡江大學電機所碩士論文，民國89年。
[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, Mar. 1976, pp. 262-274.
[14]	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.
[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 Topological Approach to the Matching of Single Fingerprints: Development of Algorithms for Use on Rolled Impressions,” NBS Special Publication 500-124, May 1985.
[17]	T. C. 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] 繆紹綱，“數位影像處理 活用Matlab”，全華科技圖書股份有限公司，民國88年3月
[22]	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.
[23] 	M. Kawagone and A. Tojo, “Fingerprint Pattern Classification,” Pattern Recognition, Vol 17, No. 3, 1984, pp.295-303.
[24] 	M. Kass and A. Witkin, “Analyzing oriented pattern,” Computer Vision, Graphics and Image Processing, vol. 37, 1987, pp. 362-385.
[25] 	S. Probhakar, “Fingerprint Classification and Matching Using A filterbank,” pp. 88-102.
[26] 	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. 
[27] 	A. R. Rao, A Taxonomy for Texture Description and Identification. New York: Springer-Verlag, 1990.
[28] 	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.
[29] 	J. Canny, “A Computational Approach to Edge Detection,” IEEE Transactions on PAMI, vol. 8, No. 6, 1986, pp. 679-698.
[30] 	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.
[31]	郭丁溢，以濾波比對方式之指紋辨識晶片設計，淡江大學電機所碩士論文，民國94年。
[32]	李建潁，快速特徵搜尋之指紋辨識晶片設計，淡江大學電機所碩士論文，民國94年。
[33] 	A. K. Jain, S. Prabhaker, L. Hong, and S. Pankanti, “Filterbank-based fingerprint matching,” Proc. IEEE, vol. 85, No. 9, 1997, pp. 1365-1388.
[34] 	D. Maltoni, D. Maio, A. K. Jain and S. Prabhakar, Handbook of fingerprint Recognition, Springer(New York), 2003.
[35]	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.
[36]	何政昌，智慧型導盲監控暨身份識別系統，淡江大學電機所碩士論文，民國95+年。
[37] 探矽工作室，2002嵌入式系統開發聖經，學貫行銷股份有限公司，2002年9月。
[38] 陳宏宇，DSP程式設計，文魁資訊股份有限公司，2004年7月。
[39]	林家慶，利用嵌入式軟核心處理器之指紋辨識系統，淡江大學電機所碩士論文，民國93年。
[40] 林睿鵬，利用改良式極座標比對法之指紋辨識晶片設計，民國94年。
[41] 郭丁溢，Filter-based比對方式之指紋辨識晶片設計，民國94年。