One to Many 3D Face Recognition Enhanced Through k-d-Tree Based Spatial Access

  • Andrea F. Abate
  • Michele Nappi
  • Stefano Ricciardi
  • Gabriele Sabatino
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3665)


Most face based biometric systems and the underlying recognition algorithms are often more suited for verification (one-to-one comparison) instead of identification (one-to-many comparison) purposes. This is even more true in case of large face database, as the computational cost of an accurate comparison between the query and a gallery of many thousands of individuals could be too high for practical applications. In this paper we present a 3D based face recognition method which relies on normal image to represent and compare face geometry. It features fast comparison time and good robustness to a wide range of expressive variations thanks to an expression weighting mask, automatically generated for each enrolled subject. To better address one-to-many recognition applications, the proposed approach is improved via DFT based indexing of face descriptors and k-d-tree based spatial access to clusters of similar faces. We include experimental results showing the effectiveness of the presented method in terms of recognition accuracy and the improvements in one-to-many recognition time achieved thanks to indexing and retrieval techniques applied to a large parametric 3D face database.


Face Recognition Discrete Fourier Transform Iterative Close Point Biometric System Iterative Close Point 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Maltoni, D., Maio, D., Jain, A.K., Prabhakar, S.: Handbook of Fingerprint Recognition. Springer, New York (2003)zbMATHGoogle Scholar
  2. 2.
    Perronnin, G., Dugelay, J.L.: An Introduction to biometrics and face recognition. In: Proc. of IMAGE 2003: Learning, Understanding, Information Retrieval, Medical, Cagliari, Italy (June 2003)Google Scholar
  3. 3.
    Bartlett, M.S., Movellan, J.R., Sejnowski, T.J.: Face Recognition by Independent Component Analysis. IEEE Transactions on Neural networks 13(6), 1450–1464 (2002)CrossRefGoogle Scholar
  4. 4.
    Zhang, J., Yan, Y., Lades, M.: Face Recognition: Eigenface, Elastic Matching, and Neural Nets. Proc. of the IEEE 85(9), 1423–1435 (1997)CrossRefGoogle Scholar
  5. 5.
    Tan, T., Yan, H.: Face recognition by fractal transformations. In: Proc. of 1999 IEEE Int. Conference on Acoustics, Speech, and Signal Processing, March 1999, vol. 6(6), pp. 3537–3540 (1999)Google Scholar
  6. 6.
    Phillips, P.J., Grother, P., Micheals, R.J., Blackburn, D.M., Tabassi, E., Bone, M.: Face Recognition Vendor Test: Evaluation Report (March 2003),
  7. 7.
    Achermann, B., Jiang, X., Bunke, H.: Face recognition using range images. In: Proc. of International Conference on Virtual Systems and MultiMedia, pp. 129–136 (1997)Google Scholar
  8. 8.
    Achermann, B., Bunke, H.: Classifying range images of human faces with the hausdorff distance. In: Proc. of 15th International Conference on Pattern Recognition, Barcelona, Spain, vol. 2, pp. 813–817 (2000)Google Scholar
  9. 9.
    Tanaka, H.T., Ikeda, M., Chiaki, H.: Curvature-based face surface recognition using spherical correlation principal directions for curved object recognition. In: Proc. of Third International Conference on Automated Face and Gesture Recognition, pp. 372–377 (1998)Google Scholar
  10. 10.
    Hesher, C., Srivastava, A., Erlebacher, G.: A novel technique for face recognition using range images. In: Proc. of Seventh Int’l. Symp. on Signal Processing and Its Applications, Paris, France (July 2003)Google Scholar
  11. 11.
    Medioni, G., Waupotitsch, R.: Face recognition and modeling in 3D. In: Proc. of IEEE Int’l. Workshop on Analysis and Modeling of Faces and Gestures (AMFG 2003), October 2003, pp. 232–233 (2003)Google Scholar
  12. 12.
    Gu, X., Gortler, S., Hoppe, H.: Geometry images. In: Proc. of SIGGRAPH 2002, San Antonio, Texas, pp. 355–361. ACM, New York (2002)CrossRefGoogle Scholar
  13. 13.
    Lee, W., Magnenat-Thalmann, N.: Head Modeling from Pictures and Morphing in 3D with Image Metamorphosis based on triangulation. In: Magnenat-Thalmann, N., Thalmann, D. (eds.) CAPTECH 1998. LNCS (LNAI), vol. 1537, pp. 254–267. Springer, Heidelberg (1998)CrossRefGoogle Scholar
  14. 14.
    Agrawal, R., Faloutsos, C., Swami, A.: Efficient similarity search in sequence databases. In: Lomet, D.B. (ed.) FODO 1993. LNCS, vol. 730. Springer, Heidelberg (1993)Google Scholar
  15. 15.
    Petrakis, E.G.M., Faloutsos, C.: ImageMap: An Image Indexing Method Based on Spatial Similarity. Proc. of IEEE Transactions on Knowledge and Data Engineering 14(15), 979–987 (1999)Google Scholar
  16. 16.
    Berchtold, S., Keim, D.A., Kriegel, H.-P.: The X-Tree: An Index Structure for High-Dimensional Data. In: Proc. of 22nd Very Large Data Base Conf., pp. 28–39 (1996)Google Scholar
  17. 17.
    Katayama, N., Satoh, S.: The SR-tree: An Index Structure for High-Dimensional Nearest Neightbor Queries. In: Proc. of ACM SIGMOD, pp. 269–380 (1997)Google Scholar
  18. 18.
    Bentley, J.L.: Multidimensional binary search trees used for associative searching. Comm. ACM 18(9), 509–517 (1975)zbMATHCrossRefMathSciNetGoogle Scholar
  19. 19.
    Phillips, J.P., Moon, H., Rizvi, A.S., Rauss, P.J.: The FERET Evaluation Methodology for Face-Recognition Algorithms. IEEE Transaction on Pattern Analysis and Machine Intelligence 22(10), 1090–1104 (2000)CrossRefGoogle Scholar
  20. 20.
    Friedman, J.H., Bentley, J.L., Finkel, R.A.: An algorithm for finding best matches in logarithmic expected time. ACM Trans. Mathematical Software 3(3), 209–226 (1997)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Andrea F. Abate
    • 1
  • Michele Nappi
    • 1
  • Stefano Ricciardi
    • 1
  • Gabriele Sabatino
    • 1
  1. 1.Dipartimento di Matemarica e InformaticaUniversità di SalernoFisciano (Salerno)Italy

Personalised recommendations