- 學位論文
利用圖論之多連通特性移除指紋錯誤特徵點之研究
Fingerprint Minutiae Purifying by Biconnected Porperty of Graph Theorem
摘要
生物辨識技術是利用人體的生理上或是行為上的特徵以辨別個人身分的技術。在現今的生物辨識技術中，其中以指紋辨識最為成熟，而且穩定且準確。而指紋辨識系統中，以指紋線條端點及分岔點作為辨識依據的特徵點比對方法最為常見。同時國際標準組織(ISO)已經於2005年公佈指紋辨識標準特徵格式(ISO19794-2)，因此基於特徵點的指紋辨識技術將在未來成為應用的標準及主流。 基於特徵點的指紋辨識系統可略分為四個處理程序：指紋影像擷取、指紋影像前處理、特徵點抽取及指紋特徵點比對這幾個程序。在這個特徵抽取的過程中，經常因為影像品質不良、影像前處理過程的錯誤而產生冗餘特徵點或正確特徵點的遺漏。其中尤其以誤判的冗餘特徵點造成影響最大；冗餘的特徵點不但會降低相同指紋的比對正確率，同時增加不同指紋間的誤判率。且多餘的錯誤特徵點更會造成比對運算時間的增加。 在本論文中，我們提出以圖論中的雙連通特性為基礎，應用於前處理之後的細線化指紋線條中，找出由於影像處理錯誤造成的網狀圖形，並且去除此區域造成的錯誤特徵點。首先，由細線化影像中取出的線條分岔點視為圖形中的節點，而相連的指紋線條視為圖形中的邊，得到一初始的圖形。接著分離出各個獨立的雙連通子圖形，藉此找出在細線化影像中不合理的連通區域，並且刪去子圖形中的節點，也就是錯誤的特徵點，以達到提升性能的目標。 由實驗結果可以證明經過加入所提出的特徵點判斷方法，的確降低了比對的錯誤率，並且使特徵點的數量降低，驗證了本研究的方法的確達到預期的效果。
並列摘要
Biometrics is a kind of technology by which personal identification can be distinct, utilizes the physiological or behavioral characteristics. Fingerprint identification is the most well-developed of biometrics in the twentieth century and it is also steady and accurate. In fingerprint identification systems, the matching method using ridge ending points and bifurcation points as matching features is the most conventional. Furthermore, " Biometric Data Interchange Formats - Finger Minutiae Data " (ISO19794-2) has already been proclaimed by International Standard Organization (ISO) in 2005. As a result, minutiae-based fingerprint identification system will become an applied standard and mainstream in the future. The minutiae-based fingerprint identification system can be separated into four procedures as follows, fingerprint image acquisition, image preprocessing, minutiae extraction, and minutiae matching. In minutiae extraction procedure, false minutiae or the lack of correct minutiae usually happen because of poor image quality or the distortion in image processing process, especially the spurious minutiae make the greatest influence. Spurious minutiae not only decrease the acception ratio of genuine matching between corresponding fingerprints but also increase acception ratio of imposter matching between different fingerprints. In real systems, matching operation time will increase because of spurious minutiae. In this research, biconnected property of graph theory is applied on skeleton image, the meshed or complex loop regions resulted from poor image quality and reject the false minutiae in this area can be found. Hence, the spurious minutiae can be eliminated to increase matching performance. First of all, the bifurcation points extracted from skeletonized image are regarded as nodes in the graph, and the connected ridges are considered as edges of the graph. So far, an initialized graph of the fingerprint is obtained. Then we separate each independent biconnected subgraphs in the unreasonable regions in the skelentonized image and delete the nodes in subgraphs which are also false minutiae. It can be proved by the experimental results that the false matching ratio indeed decreased by applying the proposed minutiae purifying method and decreased the amount of minutiae. Therefore, the effects of this research can be validated.