access icon free Locality sensitive hashing based space partitioning approach for indexing multidimensional feature vectors of fingerprint image data

© The Institution of Engineering and Technology
Received 25/05/2017, Accepted 28/01/2018, Revised 22/12/2017, Published 01/02/2018

In recent years, biometric applications have significantly gained popularity. Such applications involve voluminous databases of high dimensional data. These enormous databases increase the cost of identification and degrade the system performance. To resolve such an issue a plethora of algorithms based on geometric hashing, k–d tree, k-means clustering, etc., have been proposed in the literature. Although, these algorithms solve a number of concomitant challenges of multi-dimensional data, yet, they fail to present a universal solution. In this study, we propose an indexing mechanism, which partitions the data space effectively into zones and blocks using a set of hash functions. Furthermore, the index locations are divided into maximum nine sub-locations to store data. This helps in carrying out an efficient search of the queried data, thereby minimising the false acceptance and rejection rate. To validate the proposed approach, the mechanism has been applied to the fingerprint verification competition and National Institute of Standards and Technology fingerprint image databases. The experimental results substantiate the efficacy of our approach in terms of accuracy, speed, reduction of search space and the number of comparisons to store and retrieve data.

Inspec keywords: fingerprint identification; vectors; database indexing; image retrieval; visual databases; storage management

Other keywords: National Institute of Standards and Technology fingerprint image databases; rejection rate; data storage; search space reduction; biometric applications; indexing mechanism; multidimensional feature vectors; fingerprint verification competition databases; hash functions; data space partitions; fingerprint image data; queried data search; data retrieval; index locations; false acceptance

Subjects: Algebra; Information analysis and indexing; File organisation; Information retrieval techniques; Computer vision and image processing techniques; Spatial and pictorial databases

References

    1. 1)
      • 25. Jin, Z., Beng, A., Teoh, J.: ‘Construct a new fixed-length binary fingerprint representation using kernelized locality-sensitive hashing’. IEEE 10th Conf. on Industrial Electronics and Applications (ICIEA), 2015, pp. 296–301.
    2. 2)
      • 8. Henry, E.R.: ‘Classification and uses of finger prints’ (HM Stationery Office, London, 1905).
    3. 3)
      • 33. Yuan, B., Su, F., Cai, A.: ‘Fingerprint retrieval approach based on novel minutiae triplet features’. IEEE Fifth Int. Conf. on Biometrics: Theory, Applications and Systems (BTAS), 2012, pp. 170–175.
    4. 4)
      • 21. Cappelli, R., Ferrara, M.: ‘A fingerprint retrieval system based on level-1 and level-2 features’, Expert Syst. Appl., 2012, 39, (12), pp. 10465–10478.
    5. 5)
      • 35. Ahmed, T., Sarma, M.: ‘An advanced fingerprint matching using minutiae-based indirect local features’, Multimedia Tools Appl., 2017, pp. 1–20, doi: 10.1007/s11042-017-5444-9.
    6. 6)
      • 19. Mhatre, A., Chikkerur, S., Govindaraju, V.: ‘Indexing biometric databases using pyramid technique’. Int. Conf. on Audio- and Video-Based Biometric Person Authentication, 2005, pp. 841–849.
    7. 7)
      • 30. Erdos, P., Guy, R.K.: ‘Crossing number problems’, Am. Math. Month., 80, (1), 1973, pp. 52–58.
    8. 8)
      • 20. Cappelli, R., Ferrara, M., Maltoni, D.: ‘Fingerprint indexing based on minutia cylinder-code’, IEEE Trans. Pattern Anal. Mach. Intell., 2011, 33, (5), pp. 1051–1057.
    9. 9)
      • 17. Jayaraman, U., Gupta, A.K., Gupta, P.: ‘An efficient minutiae based geometric hashing for fingerprint database’, Neurocomputing, 2014, 137, pp. 115–126.
    10. 10)
      • 4. Maltoni, D., Maio, D., Jain, A., et al: ‘Handbook of fingerprint recognition’ (Springer-Verlag, London, 2009).
    11. 11)
      • 15. Liu, M., Yap, P.T.: ‘Invariant representation of orientation fields for fingerprint indexing’, Pattern Recognit., 2012, 45, (7), pp. 2532–2542.
    12. 12)
      • 5. Jain, A.K., Nandakumar, K., Nagar, A.: ‘Fingerprint template protection: from theory to practice’, in Campisi, P. (Ed.): ‘Security and privacy in Biometrics’ (Springer, London, 2013), pp. 187–214.
    13. 13)
      • 18. Singh, O.P., Dey, S., Samanta, D.: ‘Fingerprint indexing using minutiae-based invariable set of multidimensional features’, Int. J. Biometrics, 2014, 6, (3), pp. 272–303.
    14. 14)
      • 32. Rao, A.T., Ramaiah, N.P., Reddy, V.R., et al: ‘Nearest neighbour minutia quadruplets based fingerprint matching with reduced time and space complexity’. IEEE 14th Int. Conf. on Machine Learning and Applications (ICMLA), 2015, pp. 378–381.
    15. 15)
      • 38. Wang, Y., Hu, J., Phillips, D.: ‘A fingerprint orientation model based on 2d Fourier expansion (FOMFE) and its application to singular-point detection and fingerprint indexing’, IEEE Trans. Pattern Anal. Mach. Intell., 2007, 29, pp. 573–585.
    16. 16)
      • 2. Vielhauer, C. (ed.): ‘User-centric privacy and security in biometrics’ (The Institution of Engineering and Technology, Stevenage, UK, 2017).
    17. 17)
      • 3. Wayman, J.L.: ‘Biometric verification/identification/ authentication/recognition: the terminology’, in Li, S.Z., Jain, A. (Eds.): ‘Encyclopedia of Biometrics’ (Springer, US, 2015), pp. 263–268.
    18. 18)
      • 22. Damer, N., et al: ‘Indexing of single and multi-instance iris data based on LSH-forest and rotation invariant representation’. Int. Conf. on Computer Analysis of Images and Patterns, Cham, 2017, pp. 190–201.
    19. 19)
      • 24. Su, Y., Feng, J., Zhou, J.: ‘Fingerprint indexing with pose constraint’, Pattern Recognit., 2016, 54, pp. 1–13.
    20. 20)
      • 9. Bentley, J.L.: ‘Multidimensional binary search trees used for associative searching’, Commun. ACM, 1975, 18, (9), pp. 509–517.
    21. 21)
      • 29. ‘NIST Biometric Image Software (NBIS)’, Available at: https://www.nist.gov/services-resources/software/nist-biometric-image-software-nbis, accessed 7 December 2017.
    22. 22)
      • 11. Otair, M.A.: ‘Approximate k-nearest neighbour based spatial clustering using kd tree’, arXiv preprint arXiv:1303.1951, 2013, pp. 97–108.
    23. 23)
      • 36. Bazen, A.M., Verwaaijen, G.T., Gerez, S.H., et al: ‘A correlation-based fingerprint verification system’. 11th Annual Workshop Circuits Systems and Signal Processing, 2000, pp. 205–213.
    24. 24)
      • 6. Galar, M., Derrac, J., Peralta, D., et al: ‘A survey of fingerprint classification part I: taxonomies on feature extraction methods and learning models’, Knowl.-Based Syst., 2015, 81, pp. 76–97.
    25. 25)
      • 28. Betta, G., Capriglione, D., Corvino, M., et al: ‘Sensitivity analysis of influence quantities on signal-to-noise ratio in face-based recognition systems’. IEEE Int. Instrumentation and Measurement Technology Conf. (I2MTC), 2017, pp. 1–6.
    26. 26)
      • 31. Medina-Pérez, M.A., Garca-Borroto, M., Gutierrez-Rodrguez, A.E., et al: ‘Improving fingerprint verification using minutiae triplets’, Sensors, 2012, 12, (3), pp. 3418–3437.
    27. 27)
      • 14. Jiang, X., Liu, M., Kot, A.C.: ‘Fingerprint retrieval for identification’, IEEE Trans. Inf. Forensics Sec., 2006, 1, (4), pp. 532–542.
    28. 28)
      • 16. Ferreira, P.M., Sequeira, A.F., Rebelo, A.: ‘A fuzzy c-means algorithm for fingerprint segmentation’. Iberian Conf. on Pattern Recognition and Image Analysis, 2015, pp. 245–252.
    29. 29)
      • 26. Samanta, D.: ‘Classic data structures’ (Prentice Hall of India, Delhi, 2009, 2nd edn.).
    30. 30)
      • 27. Gonzalez, R., Woods, R.: ‘Digital image processing’ (Pearson, Upper Saddle River, NJ, 2008, 3rd edn.).
    31. 31)
      • 1. Mordini, E., Tzovaras, D.: ‘Second generation biometrics: the ethical, legal and social context’ (Springer, Dordrecht, 2012).
    32. 32)
      • 12. Beckmann, N., Kriegel, H.-P., Schneider, R., et al: ‘The r*-tree: an efficient and robust access method for points and rectangles’, SIGMOD Record, 1990, 19, (1), pp. 322–331.
    33. 33)
      • 10. Vandana, D.K., Singh, D., Raj, P., et al: ‘Kd-tree based fingerprint identification system’. IEEE 2nd Int. Conf. on Anti-counterfeiting, Security and Identification, 2008, pp. 5–10.
    34. 34)
      • 7. Cappelli, R.: ‘Fast and accurate fingerprint indexing based on ridge orientation and frequency’, IEEE Trans. Syst. Man Cybern. B, Cybern., 2011, 41, (6), pp. 1511–1521.
    35. 35)
      • 34. Fernandez-Saavedra, B., Sanchez-Reillo, R., Ros-Gomez, R., et al: ‘Small fingerprint scanners used in mobile devices: the impact on biometric performance’, IET Biometrics, 2016, 5, (1), pp. 28–36.
    36. 36)
      • 13. Li, G., Yang, B., Busch, C.: ‘A score-level fusion fingerprint indexing approach based on minutiae vicinity and minutia cylinder-code’. IEEE Int. Workshop on Biometrics and Forensics (IWBF), 2014, pp. 1–5.
    37. 37)
      • 37. Maio, D., Maltoni, D., Cappelli, R., et al: ‘Fvc2000: fingerprint verification competition’, IEEE Trans. Pattern Anal. Mach. Intell., 2002, 24, (3), pp. 402–412.
    38. 38)
      • 23. Hao, F., Daugman, J., Zielinski, P.: ‘A fast search algorithm for a large fuzzy database’, IEEE Trans. Inf. Forensics Sec., 2008, 3, (2), pp. 203–212.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ipr.2017.0550
Loading

Related content

content/journals/10.1049/iet-ipr.2017.0550
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading