A NOVEL SPECTRAL GRAPH THEORETIC APPROACH TO USER IDENTIFICATION USING HAND GEOMETRY

SHANUMUKHAPPA A ANGADI¹*, SANJEEVAKUMAR M HATTURE²*
¹Department of Computer Science and Engineering, Basaveshwar Engineering College, Bagalkot, Karnataka State, India
²Department of Computer Science and Engineering, Basaveshwar Engineering College, Bagalkot, Karnataka State, India
* Corresponding Author : smhatture@yahoo.com

Received : 06-11-2011     Accepted : 09-12-2011     Published : 12-12-2011
Volume : 3     Issue : 4       Pages : 282 - 288
Int J Mach Intell 3.4 (2011):282-288
DOI : http://dx.doi.org/10.9735/0975-2927.3.4.282-288

Conflict of Interest : None declared

Biometric technologies are becoming the basis for highly secure identification and personal verification solutions.Hand geometry biometric identification system uses the geometric shape of the hand to identify the person. A novel graph theoretic approach to hand geometry biometrics is presented in this paper. The user hand is represented as weighted undirected complete connected graph and spectral properties of the graph are used as features vectors. User identification is performed using multilayer feed-forward neural network. Experiments show that the proposed method when tested on GPDS150 peg-free hand database of users’ right hand offers a promising result of 97.05% correct personal identification.

Spectral properties, Multilayer neural network, Graph representation of hand geometry, Biometrics.

Biometrics plays an increasingly important role in authentication and identification systems. The biometric system allows identification/verification of individuals based on the physical or behavioral characteristics which cannot be hacked/stolen easily. Hand geometry biometric is concerned with measuring the physical characteristics of the user's hand. It has many advantages compared to other biometric technologies. Firstly, hand geometry measurements are easily obtained due to both the dexterity of the hand and relatively simple method of sensing, which does not impose undue requirements on the imaging optics. It requires low resolution hand image capture device, hence is less expensive. Hand characteristics are more numerous and easy to acquire. Moreover, it offers a good balance of performance characteristics and is relatively easy to use.
The hand geometry biometric system identifies individuals based on the unique features of the hand. In order to extract the discriminative features of the hand image, the image is represented as a graph and graph properties are employed to represent the hand. Graph-based techniques have been widely used within the context of biometric applications mainly with reference to identification problems. In graph-based representation, graphs are used to encode features and structural relationships of the hand images. The well-developed theory and techniques of algebra, graphs and combinatorics help in modeling the image in terms of a graph with the help of eigenvalues and eigenvectors of adjacency matrix (also similarity matrix or weight matrix) naturally associated with the graphs known as graph spectra or spectral graph properties [1] .
The most fundamental description of a graph is its topology and all the matrix representations are defined using it. The matrices which are naturally associated with a graph such as the adjacency matrix, the incidence matrix, the distance matrix and the laplacian matrix [2] are used in graph spectra. Among the eigenvalues of the adjacency matrix, the largest eigenvalue and the smallest eigenvalues are known as spectral radius and the least eigenvalue, respectively and associated eigenvectors are known as principal eigenvectors [3] .
In the proposed work,a novel graph theoretic approach to hand geometry biometrics is presented. The peg-free user hand image is represented as weighted undirected complete connected graph. The new set of features vectors (i.e. principal eigenvectors) are extracted from adjacency matrix associated with the graph.The multilayer feed-forward neural network is used for graph matching for identification of the user. The General Primary Data Sources (GPDS150) hand database is used for experimentation. The experimental results show that the proposed method offers genuine acceptance rate of about 97.05% for personal identification.
The rest of the paper is organized into four sections: section 2 reviews the developments in hand based biometric technology. The proposed model of hand geometry identification system is described in section 3. The experimental results and analysis are given in section 4. The section 5 concludes the work and lists the future directions.

Based on the use of hand image acquisition device the hand geometry techniques are classified into three categories namely peg-based, peg-free and contact-free methods. A few state of the art approaches that have used these methods for hand geometry biometrics are summarized here; In Peg based methods a scanner with either five pegs [4] or six pegs [5] were used to guide the placement of a hand. 16 geometric sizes, including widths, lengths, and thicknesses of fingers, as well as the widths of the palm at different positions are measured. By using absolute and weighted Euclidean distance classifiers the false acceptance rate (FAR) of 2%, false reject rate (FRR) of 15% and an equal error rate (EER) of 6% are reported in [4] . Further six peg scanner is used to extract 31 geometrical features. Verification is performed using four different methods such as Euclidean distance, hamming distance, Gaussian mixture model and radial basis function and recognition accuracies between 88% and 97% are reported in [5] .
In peg-free methods either flatbed scanner [6,7,8] or document scanner [9,10] device is used to acquire the hand image. In [6] landmark points are located on the hand to extract five length and eight width measurements together with the contour of three fingertips. On a dataset of 288 images recorded from 22 subjects the verification rate of 89% and false acceptance rate of 2.2% is achieved. Further in [7] every hand image is characterized by a vector of length 1x16. A set of fusional operations are carried out on the vector to find matching score between the vector and the shared identity. The matching score is used to indicate his/her identity. Another approach that separates fingers and palm from the hand image is proposed in [8] . Each feature vector includes profiled curvatures, the lengths and widths of each individual finger. The palm width, length and area of the palm are also included in the feature vector. For 80 users with Euclidean distance classifier an FAR of 0.8% and FRR of 3.8% is achieved.A methodology used to extract feature vector from low resolution hand image is discussed in [9] . Peg free and position invariant features are calculated using Radon Transform. The method is tested on a data set of 136 images with simple Euclidean norm based match score and achieved an EER of 5.1%. Further in [10] , circles were fitted into different areas of the fingers and the palm to measure 30 geometric sizes of the hand. The radiuses, perimeters, and areas of the circles, together with the lengths and widths of fingers are measured. By using these measurements the FAR of 1% and FRR of 3% are reported. However, peg-free devices reduce user inconvenience, during hand image acquisition and it suffers from the inconsistent positions of a hand due to the hand motion.
Some of the researchers have attempted to develop contact-free hand geometry techniques to solve segmentation problems in a real environment [11-17] . A commercial modified webcam with a 320x240 pixels resolution is used to acquire hand images. The geometrical features are obtained from the index, middle and ring fingers. Using support vector machine classifier for recognition; an EER of 3.4% is achieved in [11] . Further, a statistical pattern recognition technique is used for verification of 20 users in [12] . The morphological features are extracted from 200 hand images and Gaussian mixture modeling method is used to obtain genuine acceptance rate of 97% and EER of 10%. In [13] efforts have been made to fit B-spline curves on fingers. The identification is done by utilizing the differences between the curves generated by various hand geometries. On a database of 200 images from 20 persons a recognition rate of 97% and error rate of 5% are reported. Besides that, a feature-based hierarchical framework for hand geometry recognition based on finger widths, lengths, and interfinger baselines and employs the fingertips as well is presented in [14] . The fingertip curves are extracted from the top one-eighth portion of the index, middle and ring fingers are then aligned, resampled and compared through Euclidean distance. Further to improve the speed and performance of hand geometry biometrics system,the active appearance model (AAM) fitting algorithm is used in [15] . 14 distance features including the lengths of the fingers as well as the length and width of the palm are computed with respect to AAM model points. With these features the accuracy of 90% is reported. However, 3D hand geometry features have significant discriminatory information to reliably authenticate individuals [16] . A methodology that uses time series conversion techniques for 3D hand geometry features (i.e. the centroid-based conversion technique and the angle-based technique) and dynamic time warping distance measurement with Sakoe-Chiba band learning method, for user verification is discussed in [17] .
Out of many works cited in the literature it is generally agreed that peg-based alignment is not very satisfactory and pegs become an issue due to hygiene and public-health concerns. Although peg removal reduces user inconvenience, it raises more challenging research problems due to the increase in intra-class variance. Most of the researchers have used either geometrical, hand contour or special hand pattern features for identification of user. Hence, there is a scope to explore new techniques for hand feature extraction. The proposed method represents the peg-free hand image as aweighted undirected complete connected graph and further usesspectral properties of the graph as feature vectors. The detailed description of the proposed methodology is given in the next section.

The steps involved in proposed peg-free hand geometry identification system are shown in [Fig-1] . It consists of four modules such as image preprocessing, hand segmentation, graph representation/ feature extraction and identification/verification with the help of multilayer feed-forward neural network.
In presented methodology, for user identification the right hand image from GPDS150 hand database is used. Firstly, these hand images are preprocessed to remove the noise. The noise free gray scale hand image is converted into binary image. Further, hand image is segmented from the background of binary image to derive a single pixel wide contour of the hand using canny edge detection. By tracing the hand contour 12 nodes are located on hand image to represent it as weighted undirected complete connected graph and further spectral properties are extracted from the adjacency matrix representation graph to frame feature vector. In order to identify the claimed user, the feature vectors extracted from all the users of the system are used to train multilayer feed-forward neural network. The detailed description of each module is presented in the following subsections.

Image acquisition and preparation is the first step in a hand geometry biometrics system. It captures the hand images by using optical scanner and stores in to a database. The proposed system uses peg-free hand images from GPDS150 Hand database. In the database, 10 different hand images from 144 people are acquired with a peg-free desk scanner using 8 bits per pixel (256 gray levels) and a resolution of 120dpi (1021 X 1403 pixel resolution) [18] as shown in [Fig-2] .

Hand images are preprocessed in order to extract features. Firstly the additive noise from hand image is removed using theadaptive filter as it preserve edges and other high-frequency components. Since the portion above the wrist is required for the hand geometry analysis, the tip of the middle finger and wrist are identified to crop the portion above the wrist from the original hand image. Further, the cropped hand images were scaled down to four times for handling them with better performance in terms of speed as shown in [Fig-3] (a).
To derive a single pixel wide contour of the hand image, the preprocessed gray level hand image is binarized using Otsu's auto-thresholding method [19] . Since the binary image produced by thresholding method suffers from small gaps and isolated pixels. A morphological filter is employed to fill-in all small gaps and blacken the isolated white pixels and to reduce the blurring of edges. The resulting image is shown in [Fig-3] (b). Finally, the hand contour of the hand is segmented from the processed binary image using canny edge detection technique which localizes pixel intensity transitions as shown in [Fig-3] (c).

In order to represent the hand image into weighted undirected complete connected graph it is required to trace the hand contour to locate twelve landmarks points (nodes). While tracing the hand contour eight – connected component technique is used. Firstly the five fingertip nodes(i.e. P3, P5, P7, P9 and P11) and four valley point nodes (i.e.P4, P6, P8 and P10) between adjacent fingers are located.Further two reference nodes (P1, P12) are located above the wrist.
Where nodes P1and P12 are the bottom left and bottom right points of the palm respectively. Node P12 is located by searching the pixel value from the location of the node P10 i.e. width of the thumb finger. Further, nodes P1 andP2 are located by searching the pixel value towards left from the nodes P12 and P10 respectively.
The twelve nodes (vertices) located on the hand contour image are described below and are shown in [Fig-4] (a).
• 5 fingertip nodes (i.e. P3, P5, P7, P9 and P11)
• 4 valley nodes (i.e. P4, P6, P8 and P10)
• 1 left reference node i.e. P2
• 2 bottom reference nodes above the wrist (i.e. P1 and P12)
After locating the ‘N’ (twelve) landmark nodes on the hand contour, every node is connected with all other (N-1) nodes of the hand image as shown in [Fig-4] (b) and weights are assigned to each of the N/2*(N-1) edges.
Let G = (V, E) be the weighted undirected complete connected graph representation of the hand with N number of nodes i.e. N=12, where V= (P1, P2,. ., PN) denotes set of vertices of a graph including finger tips, valley points and reference points and E denotes its set of edges which are N/2*(N-1) in number. Each edge in E is an unordered pair of vertices, with the edge connecting distinct vertices Pi and Pj written as E (Pi, Pj). Each edge is assigned a distance value d:V ×V → R satisfying d (Pi, Pj) = d (Pj, Pi) and d (Pi, Pj) ≥ 0. Where‘d’ is the straight-line distance between any pair of nodes, calculated using the Euclidean distance measure. i.e.

(1)

where (xi, yi) and (xj, yj) are spatial coordinates of two nodes Pi and Pj of the complete connected graph representation of the hand image respectively.
As seen in the section 2, there are several features that can be extracted from the geometry of hand. In theproposed work spectral properties are extracted and represented as feature vectors. In order to calculate the spectral properties (eigenvalues and eigenvectors), the adjacency matrix representation of the weighted undirected complete connected graph is used. Let A be the adjacency matrix (also known as similarity matrix or weight matrix) representing the distances between all pairs of the vertices of a hand image graph. The adjacency matrix is symmetric for undirected graph. In general terms this can be written as

d_ij if (P_i, P_j) E 1 ≤ i ≤ 12, 1 ≤ j ≤ 12
A (P_i, P_j) = 0 Otherwise (2)

In geometric terms the relationship between weighted adjacency matrix A and spectral properties is given by

Au = u (3)

where u is a column vector and is a scalar. For non-zerovector u the scalar is called an eigenvalueof the graph's adjacency matrix A and the vector u is called an eigenvector corresponding to . Among the eigenvalues of the adjacency matrix, the largest eigenvalue and the smallest eigenvalues (i.e. spectral radius) contain the principal eigenvectors. The feature vector or template is constructed by selecting the principal eigenvectors of the adjacency matrix A. Since adjacency matrix A is of size 12X12, each column contains 12 values hence, total of two columns (i.e. two principal eigenvectors) are selected as feature vector for each hand image. In summary the geometric shapes of the hand image is represented by principal eigenvectors of the graph representing it.

In the proposed work to identify the user a multilayer feed-forward neural network classifier is used.An artificial neural network (ANN) is a computational model that tries to simulate the structure and/or functional aspects of biological neural networks. It consists of an interconnected group of artificial neurons and processes information using a connectionist approach to computation. It can be used to model complex relationships between inputs and outputs or to find patterns in data. Basically there are four steps in the training process; (i) assemble the feature vectors or templates (ii) create the multilayer network (iii) train the network and (iv) simulate the network response to new inputs. There are various methods to train neural networks. In this work feed forward back propagation training algorithm is used for multilayer neural networks. The multilayer neural network model is developed to identify the persons as shown in Figure 5. In the multilayer neural network the number of neurons in the input layer is equal to the dimensionality of the input feature vector i.e.I = 24 in this work. The number of neurons in the hidden layer is calculated using

(4)

where h = number of nodes in hidden layer,
I = number of input features,
O = number of outputs, and
y = number of input patterns in the training set.
The number of neurons in the output layer is equal to the number of persons available in the database i.e. O = 144 that the neural network has been trained to identify.
In order to identify the user, the multilayer feed forward neural network performs a matching between the test and trained hand images with the help of graph spectral property represented by principal eigenvectors of the adjacency matrix. The user is identified as ‘Oi’ if the i^th output of the network is “high” while all other outputs are “low”.

The performance of the proposed method is evaluated on a GPDS150 hand database of 1440 right hand images. From each user six hand images are used for training and the other four hand images for testing purposes. To train a multilayer feed-forward back propagation neural network classifier 864 feature vectors are extracted from 144 users. During identification, the spectral properties (i.e. principal eigenvector features) are extracted from claimed user’ right hand image similar to the method discussed in section 3. These features are presented to the trained neural network, which identifies the person based on the available knowledge.
The performance of biometrics system is measured using correct identification rate (CIR) or correct recognition rate (CRR), false acceptance rate (FAR) and false rejection rate (FRR). The CIR is the ratio of the number of authorized users accepted by the biometric system to the total number of identification attempts made. It is stated as follows:

(5)

The FAR or ‘type 2 error’ is the ratio of the number of unauthorized users accepted by the biometric system to the total number of identification attempts made. It is stated as follows:

(6)

The FRR or ‘type 1 error’ is the ratio of the number of authorized users rejected by the biometric system to the total number of attempts made. It is stated as follows:

(7)

Hence, by using these parameters the identification accuracy of around 97.05% is achieved and false rejection rate of 1.91% is obtained for the 144 users of GPDS150 hand database. The performance of the proposed system is tabulated in [Table-1] .
The proposed methodology produces promising results for peg-free hand images. The result shows that, the proposed hand geometry biometric systems can be useful for low to medium security applications. This approach can be further extended for contact-free hand images.

This paper has presenteda novel graph theoretic approach to hand geometry biometrics. Spectral properties (i.e. principal eigenvector features) of the adjacency matrix of weighted undirected complete connected graph of the hand image are used as feature vector. By using the peg-free hand images from GPDS150 hand database, with the help of multilayer feed-forward back propagation neural network classifier the recognition accuracy of 97.05% is achieved. In future, the images of both hands can be examined to improve the rate of identification. The proposed results indicate that the peg-free based hand geometry biometrics system constitutes a promising addition to the biometrics-based personal identification systems.

[1] Wang H. and Hancock E.R. (2004), Proc. Int. Workshops Advances in Structural and Syntactic P.R. and Stat. Tech. in P.R. 361-369.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[2] Leordeanu M. and Hebert M. (2005) Proc. Int. Conf. Computer Vision.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[3] White D. and Wilson R.C (2007) Proc. Int. Conf. Image Analysis and Processing, 35-42.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[4] Jain A.K., Ross A. and Pankanti S. (1999) Proc. 2nd Int. Conf. on Audio- and video based personal authentication (AVBPA), Washington, USA, 166–171.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[5] Reillo R.S., Avila C.S. (2000) IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 10, 1168-1171.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[6] Wong A.L.N. and Shi P. (2002) IAPR Workshop on Machine Vision Applications.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[7] Kumar A., Wong D.C.M., Shen H.C. and Jain A.K. (2003) Proc. 4th Int. Conf. Audio Video- based Biometric Person Authentication, Guildford, U.K., 668 - 678.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[8] Boreki G. and Zimmer A. (2005) Proc. 4th IEEE Workshopon Automatic Identification Advanced Technologies, 149–154.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[9] Mostayed Ahmed, Kabirt Ekramul Md (2009) Proc. of 12th Int. Conf. on Computer and Information Technology (ICCIT 2009) Dhaka, Bangladesh IEEE Transaction 587-592.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[10] Bulatov Y., Jambawalikar S., Kumar P. and Sethia S. (2002) DIMACS Workshop on Computational Geometry, Piscataway, NJ.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[11] Morales Aythami, Ferrer A. Miguel, Francisco Díaz, Jesús B. Alonso, Carlos M. Travieso(2008), Centre for Innovation in Comm, University of Las Palmas de Gran Canaria Campus de Tafira, 35017, Spain.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[12] Vivek Kanhangad, Ajay Kumar, David Zhang (2011), IEEE Transaction on Image Processing, 20(5), 1415-1424.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[13] Ying Liang Ma, Frank Pollick, W. Terry Hewitt (2004) InternationalConference of Pattern Recognition. Vol 3, :274–277.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[14] Wong A.L.N., Shi P. (2002) IAPR workshop on machine vision appls, Nara, Japan, 281 - 284.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[15] Ralph Gross, Yiheng Li, Latanya Sweeney, Xiaoqian Jiang, Wanhong Xu, and Daniel Yurovsky (2007), IEEE.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[16] Vivek Kanhangad, A. Kumar and David Zang (2011), IEEE Trans. on Inf. Forensics and Security, Vol. 6, No. 3, 1014-1027.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[17] Niennattrakul Vit and Ratanamahatana Chotirat (2008), 120-128.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[18] Miguel A. Ferrer, Aythami Morales, 41 Annual IEEE International Carnahan Conf. on Security Tech., ISBN:1-4244-1129-7, 52-58, Otawa, Canada.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[19] Otsu N. (1978), IEEE Trans. on SMC, Vol. 8, 62-66.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[20] Bahareh Aghili, Hamed Sadjedi (2010) 3rd International Congress on Image and Signal Processing (CISP2010),2619-2623.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[21] Goh Kah Ong Michael, Tee Connie, Lau Siong Hoe, Andrew Teoh Beng Jin (2010) International Symposium on Information Technology (ITSIM) 2010, 978-984.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[22] Md. Arafatur Rahman, Farhat Anwar, Md. Saiful Azad, (2008) In Proceedings of the International Conference on Computer and Communication Engineering, 1177-1180.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

	Fig. 1- Steps involved in hand geometry biometrics
	Fig. 2- Original hand image
	Fig. 3- (a) Preprocessed hand image (b) Binarized hand image (c) Segmented hand image
	Fig. 4- (a) Extraction of referencing nodes (b) Interconnection between nodes (c) Graph representation of the hand image
	Fig. 5- Multilayer Feed-forward Neural Network
	Table 1- Recognition performance