Laporkan Masalah

Minutiae-based Matching Algorithm Using Modified Hough Transform with k-nearest Neighborhood

SOUVANLIT, Kiewlamphone, Agus Bejo, S.T., M.Eng., D.Eng.;Dr.Eng Ir. Risanuri Hidayat, M.Sc.;Hanung Adi Nugroho, S.T.,M.E.,PhD.

2017 | Tesis | S2 Teknik Elektro

Pengenalan sidik jari telah diterapkan pada berbagai sistem pada masa sekarang. Pada dekade terakhir ini, pengenalan sidik jari telah menjadi sistem autentikasi berbasis biometri yang paling populer. Sistem pengenalan berbasis sidik jari yang paling mutakhir adalah Automated Fingerprint Identification System (AFIS). AFIS memiliki peran yang sangat penting dalam hal keamanan karena dinilai lebih aman, kuat, andal, dan ramah pengguna dibandingkan metode konvensional seperti token (misalnya ID card) dan personal identification number (PIN). Secara teknis, AFIS masih menyisakan beberapa tantangan dan menarik para peneliti hingga saat ini. Akurasi dari pengenalan sidik jari sangat dipengaruhi oleh sensitivitas terhadap berbagai faktor seperti arah, posisi, kondisi jari (misalnya basah, kering, atau kotor), dan distorsi. Algoritme pengenalan sidik jari terdiri dari dua tahapan utama: (1) ekstraksi ciri, dan (2) pencocokan ciri. Pendekatan konvensional yang paling komprehensif untuk proses pencocokan adalah pencocokan sidik jari berbasis minutiae dengan menggunakan Hough Transform (HT). Teknik ini berkaitan dengan beberapa permasalahan fundamental seperti rotasi dan perpindahan. Ketika pendekatan HT konvensional diberikan ciri dari hasil ekstraksi dengan distorsi yang tinggi, terdapat kesulitan pada fase pencocokan yang disebabkan oleh distorsi dan kesalahan pada minutiae yang didapat ketika ekstraksi ciri. Konsekuensinya, akurasi yang tinggi tidak bisa dicapai. Karena itu, pengurangan kesalahan sangat dibutukan. Penelitian ini berfokus pada pengurangan kesalahan pada pencocokan ciri. Dua solusi diusulkan untuk mengurangi kesalahan sekaligus meningkatkan akurasi dari pendekatan HT konvensional, yaitu: (1) modifikasi pendekatan HT yang digabungkan dengan jarak Euclidian (EUHT) dan (2) modifikasi pendekatan HT dengan memperkenalkan konsep k-nearest neighborhood (kNNHT). Untuk mengevaluasi algoritme yang diusulkan, digunakan dua basis data yang disebut dengan DB1 dan DB2 yang masing-masing terdiri dari 45 dan 100 citra sidik jari dengan format standar ISO/IEC 19794-2. Hasil percobaan menunjukkan bahwa kedua pendekatan yang diusulkan (EUHT dan kNNHT) dapat meningkatkan akurasi secara signifikan dibandingkan dengan HT konvensional. Error equal rate (EER) dari HT, EUHT, dan kNNHT pada DB1 dan DB2 adalah berturut-turut sebesar 2,71%, 0%, 0%, dan 3,68%, 0,41%, 0%. Dalam hal waktu komputasi, kedua metode yang diusulkan memerlukan 1,6 dan 2,2 kali lebih besar dibanding HT konvensional. Dari hasil tersebut, dapat disimpulkan bahwa kedua pendekatan yang diusulkan dapat meningkatkan akurasi secara signifikan tanpa memerlukan lebih banyak waktu komputasi tambahan.

Fingerprint recognition has been applied to various systems recently. It becomes the most popular biometric-based authentication systems in the past decades. The most renewed fingerprint-based recognition system is Automated Fingerprint Identification System (AFIS). AFIS plays a crucial role in security aspects. It is more secure, robust, reliable and user-friendly than conventional methods such as token (e.g., ID card), and personal identification number (PIN). Technically, it remains challenges and attracts researchers until present days. The accuracy of fingerprint recognition suffers from sensitivity caused by various factors such as direction, position, quality of finger (e.g., wet, dried, dirty finger), and distortion. Fingerprint recognition algorithm consists of two main processes: (1) feature extraction, and (2) feature matching. The most comprehensive conventional approach for matching process is minutiae-based fingerprint matching that uses Hough Transform (HT). This technique addresses some fundamental issues such as rotation and displacement. When conventional HT approach deals the feature extracted from high distortion, it shows the difficulty in matching phase caused by distortion, and false minutiae obtained from feature extraction. Consequently, it cannot achieve high accuracy. Therefore, reducing the errors is essentially necessary. This research focuses on reducing the errors of the feature matching. Two solutions are proposed to reduce the errors as well as improving the accuracy of conventional HT approach: (1) modified HT approach by combining with Euclidian distance (EUHT) and (2) modified HT approach by introducing k-nearest neighborhood concept (kNNHT). To evaluated the proposed algorithms, two databases called DB1 and DB2 are applied. DB1 and DB2 respectively contain 45 and 100 fingerprint images in standard ISO/IEC 19794-2 format. The experiment results show that the accuracy of the two proposed approaches (EUHT and kNNHT) are significantly improved compared to that of conventional HT. The Error Equal Rate (EER) of HT, EUHT, and kNNHT on DB1 and DB2 are 2.71%, 0.00%, 0.00% and 3.68%, 0.41%, 0.00% respectively. In term of computation time, the two proposed methods consume 1.6 and 2.2 times greater than conventional HT. From these results, it can be concluded that the two proposed approaches can improve the accuracy significantly without losing too much computation time.

Kata Kunci : Fingerprint recognition, minutiae-based matching, Hough Transform, Euclidian distance, k-nearest neighborhood.