非督導式指紋資料分群之研究

A Study of Unsupervised Fingerprint Image Clustering

莊英良(Eng-Liang Chuang)

指導教授 ： 黃文增 ； 蔡偉和

國立臺北科技大學/機電學院/通訊與資訊產業研發碩士專班/碩士(2008年)

摘要

指紋辨識的應用程度已日益廣泛，除了在於刑事偵察上可提供比對嫌犯的線索之用外，更能應用於許多資訊安全的防護上。然而，當所採集的指紋數量不斷增加時，如何管理以及增加比對的速度也變成一個重要的課題。本論文探討自動指紋分群技術，在不須人工介入的情況下，將所採集的未知指紋進行分群，使其達到每一群內均只包括同一人的指紋。如此，當我們欲判斷或標示每一枚指紋所屬何人時，只需以一群一群的方式來進行即可，不需要逐一判斷單一指紋，因此將可省去大量的人力。本文中利用結構式指紋比對法以及階層式聚合資料分群來建構以相似度為主的指紋資料分群，藉由此種方式除了可以幫助整理大量的指紋，並且有助於快速的尋找相似度高的指紋，且由分群的組合可以提高指紋的辨識速度。
首先本文使用影像處理的方式，例如：直方圖等化、二值化、正規化、細線化等，將輸入的指紋影像做大量的影像增強，藉此取出其相關特徵；接著利用取出的指紋特徵，如端點、叉點等，經由這些結構特徵彼此之間的關係，一一組成特徵結構；最後將兩枚指紋的特徵結構互相比對之後，求得其相似度的關係。而後使用階層式資料聚合分群將大量透過結構式比對評分的指紋集合，依照其相關性將指紋做分群的動作，並且利用群集純度(Cluster Purity)以及Rand Index來作為分群優劣的指標。

關鍵字

指紋辨識 ； 分群 ； 群集純度比較 ； Rand Index比較 ； 指紋特徵

並列摘要

The applications of fingerprint identification become more and more important today. Fingerprint identification not only applies to information security but also contributes to criminal investigation, such as suspect matching . However the fingerprint database is getting larger, it is necessary to manage and increase the speed of matching. In this dissertation, we discuss the method of automatic clustering fingerprints without clustering by person. We cluster the fingerprints which is unknown and make all fingerprints in a cluster that belongs to the same person. If we want to check or mark a fingerprint belonged to whom, we only need to check it’s group by group instead of checking it one by one. So it can save lots of manpower and time cost. In the content, it will present to utilize structural matching and hierarchical agglomerative clustering algorithms to build clusters of fingerprints which base on similarity so as to support a great quantity of fingerprint and the method would be beneficial to search high similarity fingerprint quickly, and furthermore, the cluster of combination can improve the speed of fingerprint matching.

In the dissertation , image processing will be applied by several methods, such as : histogram equalization, binarization, normalization, thinning ,etc. Input the fingerprint image and proceed with a large quantity of image enhancement so that obtain the related features. Then use these related features, for example: termination, bifurcation, to compose a feature structure separately. Finally, put the feature structure of two fingerprints into a minutia matching to get the degree of similarity. Base on hierarchical agglomerative clustering algorithm, the fingerprint can be clustered according to the similarity. Moreover, cluster purity and rand index can be provided to be a norm of the quality of cluster.

並列關鍵字

Fingerprint Identification ； Data clustering ； Cluster Purity ； Rand Index ； Fingerprint Minutia

參考文獻

8.余信緯，低價格與小體積之指紋辨識系統，碩士論文，國立台北科技大學，電腦與通訊研究所，台北，2006。

10.曾銘崧，熱感式指紋成像及其自動辨識法之研究，碩士論文，私立中原大學電子工程系，桃園，2001。

11.林昶竹，熱感式指紋影像之特徵擷取，碩士論文，私立中原大學電子工程系，桃園，2001。

6.黃文增、余信緯、沈毅偉、黃仲麟、周慶棟，「低功率、低價格與小面積之指紋辨識系統之研究與實作」，台北科技大學學報，Vol. 38-2, pp.23-38, March, 2005。

14.Hubert, L., and Arabie, P., 1985. Comparing Partitions. Journal of Classification 2:193-218.