K-Means Graph Database Clustering and Matching for Fingerprint Recognition

Vaishali Pawar, Mukesh Zaveri

Department of Computer Engineering, SVNIT, Surat, India.

DOI: 10.4236/iim.2015.74019                

Abstract

The graph can contain huge amount of data. It is heavily used for pattern recognition and matching tasks like symbol recognition, information retrieval, data mining etc. In all these applications, the objects or underlying data are represented in the form of graph and graph based matching is performed. The conventional algorithms of graph matching have higher complexity. This is because the most of the applications have large number of sub graphs and the matching of these sub graphs becomes computationally expensive. In this paper, we propose a graph based novel algorithm for fingerprint recognition. In our work we perform graph based clustering which reduces the computational complexity heavily. In our algorithm, we exploit structural features of the fingerprint for K-means clustering of the database. The proposed algorithm is evaluated using realtime fingerprint database and the simulation results show that our algorithm outperforms the existing algorithm for the same task.

Keywords

Pattern Recognition, Fingerprint Matching, Graph Matching, Clustering

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Jain, A.K., Prabhakar, S. and Hong, L. (1999) A Multichannel Approach to Fingerprint Classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21, 348-358. http://dx.doi.org/10.1109/34.761265
[2]	Rao, K. and Balck, K. (1980) Type Classification of Fingerprints: A Syntactic Approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2, 223-231. http://dx.doi.org/10.1109/TPAMI.1980.4767009
[3]	Lumini, A., Maio, D. and Maltoni, D. (1999) Inexact Graph Matching for Fingerprint Classification. Journal of Machine Graphics and Vision, 8, 241-248.
[4]	Serrau, A., Marcialis, G.L., Bunke, H. and Roli, F. (2005) An Experimental Comparison of Fingerprint Classification Methods Using Graphs. Proceedings of the 5th International Workshop on Graph-Based Representations in Pattern Recognition GbR05, Poitiers, 11-13 April 2005, 281-290.
[5]	Cappelli, R., Maio, D., and Maltoni, D. (2002) A Multi-Classifier Approach to Fingerprint Classification. Pattern Analysis and Appllications, 5, 136-144. http://dx.doi.org/10.1007/s100440200012
[6]	Rao, K. and Balck, K. (1980) Type Classification of Fingerprints: A Syntactic Approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2, 223-231. http://dx.doi.org/10.1109/TPAMI.1980.4767009
[7]	Neuhaus, M. and Bunke, H. (2005) A Graph Matching Based Approach to Fingerprint Classification Using Directional Variance. Proceedings of 5th International Conference on Audio and Video Based Biometric Person Authentication, AVBPA 05, Hilton Rye Town, 20-22 July 2005, 191-200.
[8]	Neuhaus, M. and Bunke, H. (2005) Graph-Based Multiple Classifier System—A Data Levels Fusion Approach. Proceedings of 13th International Conference on Image Analysis and Processing ICIAP05, Cagliari, 6-8 September 2005, 479-486.
[9]	Llados, J., Marti, E. and Villanueva, J.J. (2001) Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23, 1137-1143.http://dx.doi.org/10.1109/34.954603
[10]	Sanchez, G., Llados, J. and Tombre, K. (2002) An Error Correction Graph Grammar to Recognize Textured Symbols. In: Blostein, D. and Kwon, Y.-B., Eds., Graphics Recognition Algorithms and Applications, Springer, Berlin, 128-138.
[11]	Sossa, H. and Horaud, R. (1992) Model Indexing: The Graph-Hashing Approach. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Urbana, June 1992, 811-814.
[12]	Messmer, B.T. and Bunke, H. (2000) Efficient Subgraph Isomorphism Detection: A Decomposition Approach. IEEE Transactions on Knowledge and Data Engineering, 12, 307-323. http://dx.doi.org/10.1109/69.842269
[13]	Hlaoui, A. and Wang, S. (2003) A New Median Graph Algorithm. In: Hancock, E. and Vento, E., Eds., Graph Based Representations in Pattern Recognition, Springer, Berlin, 225-234.
[14]	Ferrer, M. and Bunke, H. (2010) An Iterative Algorithm for Approximate Median Graph Computation. Proceedings of International Conference on Pattern Recognition, Turkey, 23-26 August 2010, 1562-1565. http://dx.doi.org/10.1109/icpr.2010.386
[15]	Riesen, K. and Bunke, H. (2009) Dissimilarity Based Vector Space Embedding of Graphs Using Prototype Reduction Schemes. Proceedings of the Machine Learning and Data Mining in Pattern Recognition, Leipzig, July 23-25 2009, 617-631.
[16]	Hlaoui, A. and Wang, S. (2004) Approximate Graph Matching and Computing Median Graph for Graph Clustering. Proceedings of the International Workshop on Multidisciplinary Image, Video, and Audio Retrieval and Mining, Quebec, 25-26 October 2004.
[17]	Isenor, D.K. and Zaky, S.G. (1986) Fingerprint Identification Using Graph Matching. Pattern Recognition, Elsevier, 19, 113-122. http://dx.doi.org/10.1016/0031-3203(86)90017-8
[18]	Pawar, V.S. and Zaveri, M.A. (2011) Graph Based Pattern Matching. Proceedings of the 8th International Conference FSKD 2011, Shanghai, 26-28 July 2011, 1022-1026. http://dx.doi.org/10.1109/fskd.2011.6019722
[19]	Changhua, L., Bing, Y., Weixin, X. (2000) Online Hand-Sketched Graphics Recognition Based on Attributed Relational Graph Matching. Proceedings of the 3rd World Congress on Intelligent Control and Automation, Hefei, 28 June-2 July 2000, 2549-2553. http://dx.doi.org/10.1109/wcica.2000.862507
[20]	Shapiro, L. and Haralick, R. (1982) Organization of Relational Models for Scene Analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 3, 595-602. http://dx.doi.org/10.1109/TPAMI.1982.4767312