Home   >   CSC-OpenAccess Library   >    Manuscript Information
Face Images Database Indexing for Person Identification Problem
Jyotirmay Dewangan , Somnath Dey, Debasis Samanta
Pages - 93 - 122     |    Revised - 15-08-2013     |    Published - 15-09-2013
Volume - 7   Issue - 2    |    Publication Date - September 2013  Table of Contents
MORE INFORMATION
KEYWORDS
Biometric, Face Identification, Biometric-data Indexing, SURF, Index Key Generation.
ABSTRACT
Face biometric data are with high dimensional features and hence, traditional searching techniques are not applicable to retrieve them. As a consequence, it is an issue to identify a person with face data from a large pool of face database in real-time. This paper addresses this issue and proposes an indexing technique to narrow down the search space. We create a two level index space based on the SURF key points and divide the index space into a number of cells. We define a set of hash functions to store the SURF descriptors of a face image into the cell. The SURF descriptors within an index cell are stored into kd-tree. A candidate set is retrieved from the index space by applying the same hash functions on the query key points and kd-tree based nearest neighbor searching. Finally, we rank the retrieved candidates according to their occurrences. We have done our experiment with three popular face databases namely, FERET, FRGC and CalTech face databases and achieved 95.57%, 97.00% and 92.31% hit rate with 7.90%, 12.55% and 23.72% penetration rate for FERET, FRGC and CalTech databases, respectively. The hit rate increases to 97.78%, 99.36% and 100% for FERET, FRGC and CalTech databases, respectively when we consider top fifty ranks. Further, in our proposed approach, it is possible to retrieve a set of face templates similar with query template in the order of milliseconds. From the experimental results we can substantiate that application of indexing using hash function on SURF key points is effective for fast and accurate face image retrieval.
1 Google Scholar 
2 CiteSeerX 
3 refSeek 
4 TechRepublic 
5 Scribd 
6 SlideShare 
7 PdfSR 
A. Batur and M. Hayes. “Linear Subspace for Illumination Robust Face Recognition.” in Proc. IEEE International Conference on Computer Vision and Pattern Recognition, Dec 2001.
A. Gyaourova and A. Ross. “Index Codes for Multibiometric Pattern Retrieval.” IEEE Trans. on Information Forensics and Security, vol. 7, no. 2, pp. 518–529, 2012.
A. Jensen and A. L. Cour-Harbo. Ripples in Mathematics: The Discrete Wavelet Transform. Springer,2001.
A. K. Jain, B. Klare and U. Park. “Face Matching and Retrieval in Forensics Applications.” IEEE Multimedia, vol. 19, no. 1, pp. 20–28, 2012.
A. Mhatre, S. Palla, S. Chikkerur and V. Govindaraju. “Efficient Search and Retrieval in Biometric Databases.” in Proc. SPIE Defense and Security Symposium, vol. 5779, Orlando FL, Mar. 2005, pp.265–273.
A. Moore. “A Tutorial on Kd-trees.” Tech. Rep., University of Cambridge,1991, Internet:http://www.cs.cmu.edu/simawm/papers.html [Nov. 20, 2011].
B. Bhanu and X. Tan. “Fingerprint Indexing Based on Novel Features of Minutiae Triplet.” IEEE Trans.on Pattern Analysis and Machine Intelligence, vol. 25, no. 5, pp. 616–622, 2003.
D. S. Bolme, J. R. Beveridge, M. L. Teixeira and B. Draper. “The CSU Face Identification Evaluation System: Its Purpose, Features and Structure.” in Proc. 3rd International Conf. on Computer Vision Systems, 2003.
D.-S. Kim, S.-Y. Lee, B.-S. Kim, S.-C. Lee and D.-H. Chung. “On the Design of an Embedded Biometric Smart Card Reader.” IEEE Trans. on Consumer Electronics. vol. 54, no. 2, pp. 573–577, 2008.
G. Griffin, A. Holub and P. Perona. “Caltech-256 Object Category Dataset.” Tech. Rep., California Institute of Technology, 2007.
H. Bay, A. Ess, T. Tuytelaars and L. V. Gool. “SURF: Speeded Up Robust Features.” Computer Vision and Image Understanding, vol. 110, no. 3, pp. 346–359, 2008.
H. Bay, T. Tuytelaars and L. V. Gool. “SURF: Speeded Up Robust Features.” in Proc. 9th European Conference on Computer Vision, vol. 3951, 2006, pp. 404–417.
H. Lee, S.-H. Lee, T. Kim and H. Bahn. “Secure User Identification for Consumer Electronics Devices.”IEEE Trans. on Consumer Electronics, vol. 54, no. 4, pp. 1798–1802, 2008.
H. Wolfson and I. Rigoutsos. “Geometric Hashing: An Overview.” IEEE Computational Science and Engineering, vol. 4, no. 4, pp. 10–21, 1997.
Identity Card Policy, “List of National Identity Card Policies by Country.” Internet:http://en.wikipedia.org/wiki/List of identity card policies by country [Jun. 25, 2012].
J. L. Bentley. “Multidimensional Binary Search Trees Used for Associative Searching.” Communications of the ACM, vol. 18, no. 9, pp. 509–517, 1975.
J. Lu, K. Plataniotis and A. Venetsanopoulos. “Face Recognition Using LDA-Based Algorithms.” IEEE Trans. on Neural Networks, vol. 14, no. 1, pp. 195–200, 2003.
J. Phillips and P. J. Flynn. “Overview of the Face Recognition Grand Challenge.” in Proc. IEEE Conference on Computer Vision and Pattern Recognition, Jun, 2005.
J. R. Beveridge, D. Bolme, B. A. Draper and M. Teixeira. “The CSU Face Identification Evaluation System.” Machine Vision and Applications, vol. 16, no. 2, pp. 128–138, 2005.
K. H. Lin, K. M. Lam, X. Xie and W. C. Siu. “An Efficient Human Face Indexing Scheme Using Eigenfaces.” in Proc. IEEE International Conference on Neural Networks and Signal Processing, 2003,pp. 920–923.
M. Muja and D. G. Lowe. “Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration.” in Proc. International Conference on Computer Vision Theory and Applications (VISAPP’09), 2009, pp. 331–340.
M. Turk and A. Pentland. “Eigenfaces for Recognition.” Journal of Cognitive Neurosicence, vol. 3, no. 1,pp. 71–86, 1991.
N. B. Puhan and N. Sudha. “A Novel Iris Database Indexing Method Using the Iris Color.” in Proc. 3rd IEEE Conf. on Industrial Electronics and Applications (ICIEA 2008), Singapore, Jun 2008, pp. 1886–1891.
N. Mittal and E. Walia. “Face Recognition Using Improved Fast PCA Algorithm.” in Proc. Congress on Image and Signal Processing, Sanya, Hainan, 2008, pp. 554–558.
P. Belhumeur, J. Hespanha and D. Kriegman. “Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection.” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 19, no. 7,pp. 711–720, 1997.
P. J. Phillips, H. Moon, S. A. Rizvi and P. J. Rauss. “The FERET Evaluation Methodology for Face Recognition Algorithms.” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 22, no. 10, pp.1090–1104, 2000.
P. J. Phillips, P. J. Flynn, T. Scruggs, K. W. Bowyer and W. Worek. “Preliminary Face Recognition Grand Challenge Results.” in Proc. 7th International Conference on Automatic Face and Gesture Recognition, 2006, pp. 15–24.
P. Mohanty, S. Sarkar, R. Kasturi and P. J. Phillips. “Subspace Approximation of Face Recognition Algorithms: An Empirical Study.” IEEE Trans. on Information Forensics and Security, vol. 3, no. 4, pp.734–748, 2008.
P. Quintiliano and A. Rosa. “Face Recognition Applied to Computer Forensics.” The International Journal of Forensic Computer Science, vol. 1, no. 1, pp. 19–27, 2006.
P. Viola and M. J. Jones. “Robust Real-time Face Detection.” International Journal of Computer Vision,vol. 57, no. 2, pp. 137–154, 2004.
P. Yuen and J. Lai. “Face Representation Using Independent Component Analysis.” Pattern Recognition,vol. 35, no. 6, pp. 1247–1257, 2002.
R. Cappelli, M. Ferrara and D. Maltoni. “Fingerprint Indexing Based on Minutia Cylinder-Code.” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 33, no. 5, pp. 1051–1057, 2011.
S. Arya and D. M. Mount. “Algorithms for Fast Vector Quantization.” in Proc. of DCC ’93: Data Compression Conference, Snowbird, UT, 1993, pp. 381–390.
S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman and A. Y. Wu. “An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions.” Journal of the ACM, vol. 45, no. 6, pp.891–923, 1998.
S. T. Roweis and L. K. Saul. “Nonlinear Dimensionality Reduction by Locally Linear Embedding.”Science, vol. 290, no. 5500, pp. 2323–2326, 2000.
T. Huang, Z. Xiong and Z. Zhang. Handbook of Face Recognition. NY: Springer, 2011, pp. 617–638.
T. Lindeberg. “Feature Detection with Automatic Scale Selection.” International Journal of Computer Vision, vol. 30, no. 2, pp. 79–116, 1998.
T. Shakunaga and K. Shigenari. “Decomposed Eigenface for Face Recognition under Various Lighting Conditions.” in Proc. IEEE International Conference on Computer Vision and Pattern Recognition, Dec 2001.
V. D. Kaushik, A. K. Gupta, U. Jayaraman and P. Gupta. “Modified Geometric Hashing for Face Database Indexing.” in Proc. 7th international conference on Advanced Intelligent Computing Theories and Applications: with Aspects of Artificial Intelligence, 2011, pp. 608–613.
W. Louis and K. N. Plataniotis. “Frontal Face Detection for Surveillance Purposes using Dual Local Binary Patterns Features,” in Proc. 17th IEEE International Conference on Image Processing (ICIP),Sept 2010, pp. 3809–3812.
W. Yu, X. Teng and C. Liu. “Face Recognition Using Discriminant Locality Preserving Projections.”Image and Vision Computing, vol. 24, no. 3, pp. 239–248, 2006.
W. Zhao, R. Chellappa, A. Rosenfeld and P. Phillips. “Face Recognition: A Literature Survey.” ACM Computing Surveys, vol. 35, no. 4, pp. 399–458, 2003.
X. He and P. Niyogi. “Locality Preserving Projections.” in Proc. Conference Advances In Neural Information Processing Systems 16, 2003, pp. 153–160.
Y. Lamdan and H. J. Wolfson. “Geometric Hashing: A General and Efficient Model-based Recognition Scheme.” in Proceedings of the 2nd International Conference on Computer Vision, 1988, pp. 238–249.
“Biometric Passport from Wikipedia.” Internet: http://en.wikipedia.org/wiki/Biometric passport [Jun. 22,2012].
“Biometrics from Wikipedia.” Internet: http://en.wikipedia.org/ wiki/Biometrics#Countries applying biometrics [Jul. 15, 2012].
“CalTech 256.” Internet: http://www.vision.caltech.edu/Image_Datasets/Caltech256/ [Mar. 7, 2012]
“Face Recognition Grand Challenge (FRGC).” Internet: http://www.nist.gov/itl/iad/ig/frgc.cfm [May 8,2012].
“FLANN - Fast Library for Approximate Nearest Neighbors.” Internet:http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN [May 27, 2012].
“Identity Document from Wikipedia.” Internet: http://en.wikipedia.org/wiki/Identity document#Bangladesh[Jul. 17, 2012].
“Physical access control biometrics.” Internet: http://www.findbiometrics.com/physical-access/ [Jun. 12,2012].
“The Color FERET Database: Version 2.” Internet: http://www.nist.gov/itl/iad/ig/colorferet.cfm [Feb. 10,2012].
“The Facial Recognition Technology (FERET) Database.” Internet: http://www.itl.nist.gov/iad/humanid/feret/feret master.html [Dec. 10, 2011].
“The Open Source Computer Vision (OpenCV) Library.” Internet: http://opencv.willowgarage.com/wiki/Welcome [Dec. 16, 2011].
“UIDAI Strategy Overview: Creating a Unique Identity Number for Every Resident in India.” Internet:http://uidai.gov.in/UID PDF/Front Page Articles/Documents/Strategy Overveiw- 001.pdf [May 18, 2012].
“Unique Identification Authority of India.” Internet: http://uidai.gov.in/ [Jul. 12, 2012].
“Using the Iris Recognition Immigration System (IRIS).” Internet:http://www.ukba.homeoffice.gov.uk/customs-travel/Enteringtheuk/usingiris/ [Jan. 20, 2012].
Mr. Jyotirmay Dewangan
NetApps - India
Dr. Somnath Dey
Indian Institute of Technology Indore - India
somnath_dey2003@yahoo.co.in
Dr. Debasis Samanta
Indian Institute of Technology Kharagpur - India