International Journal of Electrical and Computer Engineering (IJECE) Vol. 3, No. 6, December 2013, pp. 823~830 ISSN: 2088-8708  823 Ordinal Measure of Discrete Cosine Transform (DCT) Coefficients And Its Application to Fingerprint Matching Fitri Arnia1,2, Hendra Hidayat1, Roslidar1, Khairul Munadi1,2 1 Department of Electrical Engineering, Engineering Faculty, Syiah Kuala University 2 Master Program of Electrical Engineering, Syiah Kuala University Article Info ABSTRACT Article history: Recently, the identification system is not limited in using an ID and personal identification number (PIN) but also in using biometriccharacteristics.One of biometric characteristics that has been widely used is fingerprint.This paper proposes a fingerprint matching algorithms using ordinal measure of DCT coefficient. The ordinal measure of DCT coefficient is generated from DCT blocks with size 8x8 pixels. Matching level was determined by computing the Minkowski distance between features of input fingerprint image and fingerprint images in the database. The simulations were accomplished using 128 fingerprints that have been normalized, from which as many as 1024 genuine attempts and 15360 impostor attempts were generated. The proposed algorithms achievedan Equal Error Rate (EER) at threshold 0.3. At the EER, it resulted in FAR value of 0.82%, and FRR value of 78.41% respectively. The low value of FAR showed that the system wasconsiderably secure. Received Sep 16, 2013 Revised Oct 19, 2013 Accepted Nov 6, 2013 Keyword: Discrete cosine transform False acceptence rate (FAR) False rejection rate (FRR) Fingerprint Ordinal measure of DCT Copyright © 2013 Institute of Advanced Engineering and Science. All rights reserved. Corresponding Author: Fitri Arnia Departement of Electrical Engineering, Faculty of Engineering, Syiah Kuala Univeraity, Jl. T. Syech Abdurrauf No. 7, Darussalam, Banda Aceh, Indonesia Email: f.arnia@unsyiah.ac.id 1. INTRODUCTION The rapid growth of technology has enforced the development in all aspects including identification technology. Recently, the identification system is not limited in using an ID and personal identification number (PIN) but also in using biometriccharacteristics. Biometric characteristics is an individual biologic characteristic that identifies a person.One of the biometric characteristic that has been widely used is fingerprint. This identification system is applied mostly for security system and authentication system [1]. The system has two stages, the first stage is capturing fingerprint features and the second deciding the matching level of the input fingerprint featureto the features saved in the database. The fingerprint feature is usually categorized into three levels. The first level is macro feature of the fingerprint such as ridge flow and pattern type. The second feature level is known as Galton feature (minutiae) such as ridge bifurcations and endings. The third feature level or shape includes all attributes of ridges such as ridge path deviation, width, shape, breaks, scars and other permanent details [2]. The performance enhancement of the fingerprint recognition is investigated in [2] where second and third feature levels are used. It is found that there is an improvement around20% in terms of EER if both of the features are employed. The work in [3] proposes a combination of texture features and minutiae for fingerprint matching. It is argued that features (descriptors) instead of the minutiae itself are required to increase the matching rate of a fingerprint system. The correspondent between two individual features is established by an alignment-based greedy matching algorithm. The features are implied in order to carry out the deficiency of minutiae in the orientation matching. Journal homepage: http://iaesjournal.com/online/index.php/IJECE IJECE ISSN: 2088-8708  824 One of the features that resists to the changing of orientation and lighting is ordinal measure of DCT coefficient [4]. This feature has been used for image matching in image retrieval application. Particularly for biometric, the ordinal measure of DCT coefficient was also applied as a feature to identify iris biometric [5, 6, 7]. It was reported that the ordinal measure of DCT coefficient was able to reach the iris identification rate of more than 60%. This paper proposeda fingerprint matching algorithmusing ordinal measures of DCT coefficient asfeatures. The ordinal measure was calculated by ordering the absolute value of AC components of DCT coefficients of each image’s block with size 8x8 pixels. Matchingwas determined by computing the Minkowski distance between features of input fingerprint image and fingerprint images in the database. Furthermore, a threshold value that provided a trade-off between FAR and FRR values, wasselected. The simulation wasaccomplished using 128 fingerprints that have been normalized, from which as many as 1024 genuine attempts and 15360 impostor attempts were generated. The proposed algorithms achieved an Equal Error Rate (EER) at threshold 0.3. On the EER, the value of FAR and FRR were 0.82% and 78.41% respectively. The low value of FAR shows that the system wasconsiderably secure because the possibility that the system receives the fingerprint from unregistered individual was small. On the other hand, high FRR value shows that the system was very selective, means that there was no guarantee that the registered users will be accepted by the system. 2. RESEARCH METHOD The fingerprint matching algorithm proposed in this paper was evaluated based on simulation results. Initial step in this research was the preparation of fingerprint image database, followed by designing the identification algorithm. Finally, the algorithm was implemented and evaluated using fingerprint images saved in the database. The database of fingerprint imageswas obtained from UPEK Fingerprint Database [8]. The images in the database were taken from 16 individuals (classes), in which each class consisted of 8 image versions; thus the total image in the database was 128. The actual size of each image in the database was 338 x 248 pixels. These images were first normalized with regard to size and its relative spatial position. The size of the normalized image was 128 x 128 pixels while the center of the fingerprint was set manually so that it was located in the centre of the image. Several original images in the database and their normalized versions are shown in Figure 1. The proposed matching algorithm was divided into two stages and illustrated in block diagrams as shown in Figure 2. The first stagewas the process of building fingerprint image database, which is illustrated in Figure 2(a). The second stagewas fingerprint image matching process as shown in Figure 2(b). The building of database was initiated with normalizing the size of the images in the database into 128 x 128 pixels. Furthermore, the normalized images were tiled into blocks with size 8 x 8 so that the total block was 256. Then, each block was transformed using discrete cosine transform (DCT) so that each block haditsDCTcoefficients. Finally, the absolute value of the AC component of DCT coefficientof each block was sorted in order to obtain the ordinal measure. All of these ordinal measures were stored in the database for subsequent matching process. In this case, ordinal measure of DCT coefficient is the feature of the proposed algorithm. a. Original fingerprint images with size of 338 x 248 pixels b. Normalized fingerprint images with size of 128 x 128 pixels Figure 1. Original fingerprint images and their normalization Ordinal Measure of Discrete Cosine Transform (DCT) Coefficients And Its Application to… (Fitri Arnia) 825  ISSN: 2088-8708 a. Image database generation process b. Diagram of the proposed matching technique Figure 2. Database generation and the proposed matching technique The proposed matching algorithm was similar to the database building process. The input images were normalized, tiled, and transformed to DCT in order to obtain the ordinal measure. Furthermore; the distance of ordinal measure of the input image and all of ordinal measure in the database were calculated using Minkowski distance based on Eq. 1. ( ) ∑ | | (1) where q dan u were ordinal measure of the input image and the database image respectively , and lwas the total AC components from each 8x8-pixel block, which were 63 coefficients. In the matching process, ideal condition was achieved if the Minkowski distances between the images in a particular class were very small or approaching zero. Performance of the proposed algorithms was obtained by calculating the distances between all the images in the database. For instance, distances ofthe first image to 128 other images in the database werecomputed, and then distance of the second image to 128 other images in the database were also computed, and so on until 16384 distance values were obtained. From the total distance, 1024 were the genuine attempts and 15360 were impostor attempts. These distance values were used to create two distribution curves named as genuine distribution and impostor distribution. Genuine distribution was a histogram of all image distances from one class, while the impostor distribution was the histogram of all image distances from different classes. The proposed algorithm performance was measured using two evaluating parameters, which are False Acceptance Rate (FAR) and False Rejection Rate (FRR). FAR is defined as the acceptance error rate in matching process. It happens when the system accepts the input image that supposed to be rejected because it comes from different classes. The FAR is formulated in Eq. 2 as follows (2) The FRR denotes the condition if the system is making an error when rejecting the input. This means that the input image that supposed to be accepted by the system because the image has been registered in the database, being rejected by the system. The FRR is given in Eq. 3 as follows IJECE Vol. 3, No. 6, December 2013 : 823 – 830 IJECE 826  ISSN: 2088-8708 (3) The value of FAR and FRR can be calculated by joining genuine distribution and impostor distribution curves. Then, on the combined curve the value of Equal Error Rate (EER) can be determined. 3. RESULTS AND ANALYSIS Analysis of simulation results were classified into into three sections. The first section described the Minkowski distance between one input image and other images from different classes that were available in the database. The second section illustrated the distance variability in one image class. The simulation data from the first and the second part were tabulated in Tables1 to 12. These results describedempiric results of the proposed algorithm. The third section discussed the whole performance of the proposed algorithm, indicating by FAR and FRR value as shown in Figure 4. 3.1. Minkowski Distance of Inter Class Images Table 1 to 12provideseveral instances of distances betweenan input image and all images in the database. There are sixteen classes, in which each class consisted of eight versions that were written as 1_1, 1_2, … 2_1, 2_2, … 16_1, … and 16_8. The highlighted data in these tables meant that the data belong to the same class as the input image, and will contribute to genuine distribution. On the other hand, data that were not highlighted are data from different class and give contribution to impostor distribution. Table 1. Matching rank and Minkowski distance of input image 7_8 Rank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Database’s Images 7_8 7_6 7_1 7_7 7_3 7_5 7_2 14_7 13_4 13_8 1_8 13_2 9_8 13_1 Minkowski distance 0 0.5483 0.5971 0.6035 0.6043 0.6277 0.6307 0.6443 0.6522 0.6654 0.6672 0.6701 0.6783 0.6791 Table 3. Matching rank and Minkowski distance of input image 1_1 Rank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Database’s Images 1_1 1_7 1_5 13_3 1_8 1_2 1_4 13_2 13_4 1_3 13_1 3_3 14_8 14_7 Minkowski distance 0 0.526 0.5754 0.5884 0.5959 0.5989 0.608 0.6091 0.6136 0.6206 0.6222 0.6225 0.6323 0.6328 Table 2. Matching rank and Minkowski distance of input image 8_4 Rank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Database’s Images 8_4 8_3 8_6 8_7 6_8 12_7 8_8 6_7 8_2 11_6 6_3 6_4 8_5 8_1 Minkowski distance 0 0.4631 0.479 0.4874 0.4903 0.4955 0.4988 0.5002 0.5018 0.5021 0.5067 0.5069 0.5075 0.5122 Table 4. Matching rank and Minkowski distance of input image 15_8 Rank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Database’s Images 15_8 5_7 15_5 15_7 4_6 4_8 16_5 4_5 5_8 4_2 15_3 13_7 5_5 15_6 Minkowski distance 0 0.2452 0.2456 0.2468 0.2501 0.2522 0.2544 0.2598 0.2601 0.263 0.2647 0.2665 0.2666 0.2728 Table 1 to 4 present several distance values between input fingerprint images and the images in the database after being sorted from the closest to the furthest. Four samples of input images, namely image 7_8, Ordinal Measure of Discrete Cosine Transform (DCT) Coefficients And Its Application to… (Fitri Arnia) 827  ISSN: 2088-8708 8_4, 1_1 and 15_8 were evaluated. These tables contained only fourteen closest distances. Table 1 shows a good matching result, in which seven fingerprint images were being identified as genuine from total eight images that represent one individual (class).At this point, it may be said that the matching rate approaching 82.5%. Table2 and 3 show poor matching results since the images belong to a particular class did not have the closest distance to the input image of the corresponding class. In Table 2, all of the images from the same classeswererankedfrom number one to fourteen, but not at the highest ranks. The worst condition was illustrated in Table 4, in which only five images from the same class obtained the smallest distance. The distance values given in Tables2 to 4 expose inter-classvariability. 3.2. Minkowski Distance of Intra-class Images Table 5 to 12 contain matching rank and Minkowski distance from the images in one class. Here, it wasrepresented by class 10. In Table 6 and 9, the matching rate approached 87.5%, while in Table 7, the matching rate was 100%. In other tables, the matching rate varied in the range of 25% to 75%. The distance values in those tables indicated that the intra-class variability wassufficiently high. To obtain illustration of the relationship between the matching rates and the condition of the images used in the simulation, please refer to Figure 3. Figure 3 shows the images whose distance valuesbetween them provided in Table 5 to 12. Observation to those images related to variation of matching rates resulted in two considerations. The first one is that those images did not go through an image registration process. There was pixel shifting from one imageto another, which was caused by manually cropping the images during the normalization process. The second onewassize of DCT block applied in the process was very small, which was8x8 pixels in this case. Theblock size was not sufficient to represents uniqueness of ordinal measures of DCT coefficients of the corresponding blocks. Table 5. Matching rank and Minkowski distance of input image 10_1 Rank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Database’s Images 10_1 15_2 16_8 16_5 16_7 16_4 10_4 13_5 15_3 16_1 16_3 15_6 13_7 5_6 Minkowski distance 0 0.3822 0.3822 0.3829 0.3844 0.3851 0.386 0.3908 0.3909 0.3944 0.4032 0.4034 0.4041 0.4056 Table 7. Matching rank and Minkowski distance of input image 10_3 Rank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Database’s Images 10_3 10_2 10_4 10_6 10_7 10_1 10_8 10_5 15_2 16_2 13_6 15_1 16_6 7_7 Minkowski distance 0 0.4729 0.4832 0.4937 0.5004 0.507 0.5133 0.5151 0.526 0.5301 0.5383 0.5387 0.541 0.5422 IJECE Vol. 3, No. 6, December 2013 : 823 – 830 Table 6. Matching rank and Minkowski distance of input image 10_2 Rank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Database’s Images 10_2 10_3 10_4 10_5 10_8 10_7 15_2 16_2 13_6 7_2 16_6 16_3 10_6 7_7 Minkowski distance 0 0.4736 0.502 0.5025 0.5138 0.5169 0.5189 0.5328 0.5331 0.5368 0.5384 0.5386 0.5404 0.5416 Table 8. Matching rank and Minkowski distance of input image 10_4 Rank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Database’s Images 10_4 10_1 16_2 16_1 16_3 16_7 10_3 15_2 13_6 10_8 16_4 16_5 10_7 10_5 Minkowski distance 0 0.4255 0.4333 0.4404 0.4419 0.4419 0.4432 0.4487 0.4521 0.4531 0.4535 0.4559 0.4565 0.4579 IJECE  ISSN: 2088-8708 Table 9. Matching rank and Minkowski distance of input image 10_5 Rank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Database’s Images 10_5 10_7 10_8 16_2 15_2 10_4 10_2 15_1 16_1 15_3 15_4 10_3 16_7 10_6 Minkowski distance 0 0.3821 0.4094 0.447 0.4532 0.4639 0.4662 0.4726 0.4774 0.4778 0.4779 0.4786 0.4793 0.4815 Table 11. Matching rank and Minkowski distance of input image 10_7 Rank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Database’s Images 10_7 10_8 10_5 16_1 15_1 16_3 15_4 16_2 15_2 10_6 16_5 15_3 15_6 16_6 Minkowski distance 0 0.3637 0.3653 0.4145 0.4175 0.4212 0.423 0.4237 0.4243 0.4254 0.427 0.4273 0.4285 0.4337 828 Table 10. Matching rank and Minkowski distance of input image 10_6 Rank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Database’s Images 10_6 10_7 10_8 10_3 10_4 15_2 15_4 16_2 15_3 15_1 10_5 16_6 16_1 16_3 Minkowski distance 0 0.4566 0.4577 0.4707 0.4828 0.4838 0.4845 0.4893 0.4898 0.4916 0.494 0.5009 0.5062 0.5065 Table 12. Matching rank and Minkowski distance of input image 10_8 Rank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Database’s Images 10_8 10_7 10_5 16_1 16_3 16_4 15_3 15_2 16_6 15_5 16_2 15_4 16_7 16_5 Minkowski distance 0 0.369 0.3971 0.413 0.4163 0.4222 0.423 0.4274 0.428 0.4282 0.4286 0.4296 0.4303 0.4314 Figure 3. Images of class 10 3.3. FAR and FRR of the Proposed Algorithm Figure 4 illustrates the overall performance of the proposed algorithm using FAR and FRR curves. Histogram of genuine distribution drawn in dash line as shown in Figure 4(a) was generated from 1024 genuine attempts. While an impostor distribution demonstrated by the graph in Figure 4(a) as the solid line was sketch based on as many as 15360 impostor attempts. A better illustration of FAR and FRR values are provided in Figure 4(b). In this figure, it can be observed that the intersection of impostor distribution and genuine distribution curves occured at threshold 0.3. This point is called Equal Error Rate (EER) point. From this EER point, the FAR value of 0.82% was obtained (that is the percentage of impostor occurrence at values less than 0.3), and the FRR value was 78.41% (that is the percentage of genuines occurrence at velues higher than 0.3) The value of FRR and FAR describesa trade-off between security and ease of the proposed algorithm. The low value of FAR shows that the system wasconsiderably secure because the possibility that the system receives the fingerprint from unregistered individual was small. Based on the data achieved from the simulation, from 100 impostors that trying to access system that less than one individual is success. On the other hand, high FRR value shows that the system was very selective, means that there was no guarantee that the registered users will be accepted by the system. Ordinal Measure of Discrete Cosine Transform (DCT) Coefficients And Its Application to… (Fitri Arnia) 829  ISSN: 2088-8708 a. Genuine and impostor distribution of the proposed method b. False Acceptance and False Rejection Rate Figure 4. Performance of the proposed method 4. CONCLUSION This paper proposed a fingerprint matching algorithms using ordinal measure of DCT coefficient. The ordinal measure of DCT coefficient was generated from DCT blocks with size 8x8 pixels. The simulation was accomplished using 128 fingerprint images that have been normalized, from which as many as 1024 genuine attempts and 15360 impostor attempts were generated. The proposed algorithms resulted in an Equal Error Rate (EER) at threshold 0.3. On the EER, it achieved FAR value of 0.82% and FRR value of 78.41% respectively. ACKNOWLEDGEMENTS The work reported in this paper is the result of research projects partially funded by Directorate General of Higher Education (DGHE) of the Republic of Indonesia, under Penelitian Kerjasama Luar Negeri dan Publikasi Internasional with contract No. 007/UN11.2/LT/SP3/2013. REFERENCES [1] Lidong Wang. The effect of force on Fingerprint Image quality and fingerprint distortion”. International Journal of Electrical and Computer Engineering (IJECE). 2013; 3(3): 294-300. [2] Anil K Jain, Y Chen, & M Demirkus. “Pores and Ridges: High resolution Fingerprint Matching Using Level 3 Features”. IEEE Transaction on Pattern Analysis and Machine Intelligence. 2007; 29(1): 15-27. [3] Jin Jiang Feng. “Combining Minutiae Descriptors for Fingerprint Matching”. Pattern Recognition. 2008; 41: 342352. [4] Changick Kim. “Content-based image copydetection”. Signal Processing: Image Communication. 2003; 18: 169– 184. [5] Fitri Arnia and Khairul Munadi. “Iris Recognition Method Based on Ordinal Measure of Discrete Cosine Transform Coefficients”. in Proceeding of IEEE Symposium on Computers and Informatics. 2012: 203-207. [6] Fitri Arnia, Fery Irianda, Siti Aisyah and Khairul Munadi. “Ordinal Measure of Discrete Cosine Transform Blocks for Iris Identification”. in Proceeding of Annual International Conference (AIC), Universitas Syiah Kuala. 2012: 285-290. [7] Fitri Arnia, Khairul Munadi, Roslidar, M Fujiyoshi and H Kiya. “Improved Iris Matching Technique Using Reduced Sized of Ordinal Measure of DCT Coefficients”. in Proceeding of IEEE International Symposium of Consumer Electronics. 2013: 287-288. IJECE Vol. 3, No. 6, December 2013 : 823 – 830 IJECE ISSN: 2088-8708  830 [8] UPEK Fingerprint Database, http://www.advancedsourcecode.com/fingerprintdatabase.asp, 2013, retrieved April 13, 2013. BIOGRAPHY OF AUTHORS Fitri Arnia received B. Eng degree from Universitas Sumatera Utara (USU), Medan in 1997. She finished her master and doctoral degree from Universsity of New South Wales (UNSW), Sydney, Australia and Tokyo Metropolitan University, Japan in 2004 and 2008 respectively. She has been with the Department of Electrical Engineering, Faculty of Engineering, Syiah Kuala University since 1999. She is a member of IEEE and IAENG. Her research interests are signal, image and multimedia information processing. Hendra Hiadayat received B. Eng degree from Universitas Syiah Kuala (UNSYIAH), Banda Aceh in 2013. His research interests are image processing and computer vision. Roslidar was born in Banda Aceh, Indonesia, on July 19, 1978. In 2002, she received her bachelor degree at Electrical Engineering Department of Syiah Kuala University at the same place where then she become a lecturer. She graduated from Telecommunication Engineering of University of Arkansas for her Master degree in 2009. Khairul Munadi received the B.E. degree from Sepuluh Nopember Institute of Technology, Surabaya, Indonesia, in 1996, and the M.Eng. and Ph.D. degrees from Tokyo Metropolitan University (TMU), Japan, in 2004 and 2007 respectively, all in electrical engineering. From 1996 to 1999, he was with Alcatel Indonesia as a system engineer. Since 1999, he joined Syiah Kuala University, Banda Aceh, Indonesia, as a lecturer at the Electrical Engineering Department. He was a visiting researcher at the Information and Communication Systems Engineering, Faculty of System Design, TMU, Japan, from March 2007 to March 2008. His research interests include multimedia signal processing and communications. Ordinal Measure of Discrete Cosine Transform (DCT) Coefficients And Its Application to… (Fitri Arnia)