In this paper, we compare performance of several dimension reduction techniques, namely LSI, FastMap, and SDD in Iris recognition. We compare the quality of these methods from both the visual impact, and quality of generated "eigenirises". K. Richta, J. Pokorny´, V. Sn´aˇsel (Eds.): Dateso 2009, pp. 80-89, ISBN 978-80-01-04323-3.
1 Introduction Methods of human identification using biometric features like fingerprint, hand geometry, face, voice and iris are widely studied.
A human eye iris has its unique structure given by pigmentation spots, furrows and
other tiny features which are stable throughout life. It is possible to scan an iris without
physical contact in spite of wearing contact lenses or eyeglasses. The iris is hard to forge
which makes the iris a suitable object for the identification of people. Iris recognition
seems to be more reliable than other biometric techniques like face recognition[
In this paper, we use the Petland’s approach to image retrieval: image vectors of
complete images of the size width × height of the image [
To fight the high dimension of image vector, we can extract several features which represent the image and concatenate them into a feature vector. The feature extraction methods can use different aspects of images as the features, typically the color features (histograms), shape features (moments, contours, templates), texture features and others (e.g. eigenvectors). Such methods are either using a heuristics based on the known properties of the image collection, or are fully automatic and may use the original image vectors as an input.
In this paper we will concentrate on the last category – other feature extraction methods which use known dimension reduction techniques and clustering for automatic feature extraction.
Singular value decomposition (SVD) was already successfully used for automatic
feature extraction. In case of face collection (such as our test data), the base vectors
can be interpreted as images, describing some common characteristics of several faces.
These base vectors are often called eigenfaces. For a detailed description of eigenfaces,
see [
However SVD is not suitable for huge collections and is computationally expensive, so other methods of dimension reduction were proposed. We test two of them – SemiDiscrete decomposition.
Recently, Toeplitz matrix minimal Eigenvalues are also playing a role towards
image description and feature extraction [
The rest of this paper is organized as follows. The second section explains used dimension reduction methods. In the third section, we briefly describe qualitative measures used for evaluation of our tests. In the next section, we supply results of tests for several methods on ORL face collection. In conclusions we give ideas for future research. 2
Dimension Reduction Methods We used three methods of dimension reduction for our comparison – Singular Value Decomposition, Semi-Discrete Decomposition and FastMap, which are briefly described bellow. 2.1
Singular Value Decomposition
SVD [
Formally, we decompose the matrix of images A by singular value decomposition (SVD), calculating singular values and singular vectors of A.
We have matrix A, which is an n × m rank-r matrix and values σ1, . . . , σr are calculated from eigenvalues (λi) of matrix AAT as σi = √λi. Based on them, we can calculate column-orthonormal matrices U = (u1, . . . , ur) and V = (v1, . . . , vr), where U T U = In a V T V = Im, and a diagonal matrix Σ = diag(σ1, . . . , σr), where σi > 0, σi ≥ σi+1.
The decomposition
A = U ΣV T is called singular decomposition of matrix A and the numbers σ1, . . . , σr are singular values of the matrix A. Columns of U (or V ) are called left (or right) singular vectors of matrix A.
Now we have a decomposition of the original matrix of images A. We get r nonzero singular numbers, where r is the rank of the original matrix A. Because the singular values usually fall quickly, we can take only k greatest singular values with the corresponding singular vector coordinates and create a k-reduced singular decomposition of A.
Let us have k (0 < k < r) and singular value decomposition of A
A = U ΣV T ≈ Ak = (UkU0) Σk 0 0 Σ0
VkT V0T We call Ak = UkΣkVkT a k-reduced singular value decomposition (rank-k SVD).
Instead of the Ak matrix, a matrix of image vectors in reduced space Dk = ΣkVkT is used in SVD as the representation of image collection. The image vectors (columns in Dk) are now represented as points in k-dimensional space (the feature-space). For an illustration of rank-k SVD see Figure 1.
Rank-k SVD is the best rank-k approximation of the original matrix A. This means that any other decomposition will increase the approximation error, calculated as a sum of squares (Frobenius norm) of error matrix B = A−Ak. However, it does not implicate that we could not obtain better precision and recall values with a different approximation.
To execute a query Q in the reduced space, we create a reduced query vector qk = UkT q (another approach is to use a matrix Dk′ = VkT instead of Dk, and qk′ = Σk−1UkT q). Instead of A against q, the matrix Dk against qk (or qk′) is evaluated.
Once computed, SVD reflects only the decomposition of original matrix of images.
If several hundreds of images have to be added to existing decomposition (folding-in),
the decomposition may become inaccurate. Because the recalculation of SVD is
expensive, so it is impossible to recalculate SVD every time images are inserted. The
SVDUpdating [
Dk Nonnegative real values
YkT
Values {-1,0,1} the resulting required storage may be even larger than the one needed by the original term-by-document matrix A.
To improve the required storage size and query time, the semidiscrete decomposition was defined as
A ≈ Ak = XkDkYkT , where each coordinate of Xk and Yk is constrained to have entries from the set ϕ = {−1, 0, 1}, and the matrix Dk is a diagonal matrix with positive coordinates.
The SDD does not reproduce A exactly, even if k = n, but it uses very little storage with respect to the observed accuracy of the approximation. A rank-k SDD (although from mathematical standpoint it is a sum on rank-1 matrices) requires the storage of k(m + n) values from the set {−1, 0, 1} and k scalars. The scalars need to be only single precision because the algorithm is self-correcting. The SDD approximation is formed iteratively.
The optimal choice of the triplets (xi, di, yi) for given k can be determined using greedy algorithm, based on the residual Rk = A − Ak−1 (where A0 is a zero matrix). 2.3
FastMap
FastMap [
In first step, it chooses two points (feature vectors) from the matrix A, which should be most distant for calculated reduced dimension. Because it would be expensive to calculate distances between all points, it uses following heuristics (all chosen points are image vectors from matrix A): 1. A random point c0 is chosen. 2. The point bi having maximal distance δ(ci, bi) from ci is chosen, and based on it we select the point ai with maximal distance δ(bi, ai) 3. We iteratively repeat step 2 with ci+1 = ai (authors suggest 5 iterations). 4. Points a = ai and b = bi in the last iteration are pivots for the next reduction step.
In second step (having the two pivots a, b), we use the cosine law to calculate position of each point on line joining a and b. The coordinate xi of point pi is calculated as xi = δ2(ai, pi) + δ2(ai, bi) − δ2(bi, pi) and the distance function for next reduction step is modified to
δ′2(p′i, p′j ) = δ2(pi, pj ) − (xi − xj )2
The pivots in original and reduced space are recorded and when we need to process a query, it is projected using the second step of projection algorithm only. Once projected, we can again use the original distance function in reduced space. 3
Since we need an universal evaluation of any retrieval method, we use some measures to determine quality of such method. In case of Information Retrieval we usually use two such measures - precision and recall. Both are calculated from the number of objects relevant to the query Rel – determined by some other method, e.g. by manual annotation of given collection and the number of retrieved objects Ret. Based on these numbers we define precision (P ) as a fraction of retrieved relevant objects in all retrieved objects and recall (R) as a fraction of retrieved relevant objects in all relevant objects. Formally: P = |Rel ∩ Ret| |Ret| and R = |Rel ∩ Ret| |Rel|
So we can say that recall and precision denote, respectively, completeness of
retrieval and purity of retrieval. Unfortunately, it was observed that with the increase of
recall, the precision usually decreases [
For the overall comparison of precision and recall across different methods on a
given collection, we usually use the technique of rank lists [
For testing of the different methods, we used iris collection consisting of 384 irises. The
iris were scanned by TOPCON optical device connected to the CCD Sony camera. The
acquired digitized image is RGB of size 576 × 768 pixels. Only the red (R) component
of the RGB image has been used in our experiments because it appears to be more
reliable than recognition based on green or blue components or converting the irises
to grayscale first. It is in accord with [
We have excluded one of the three irises for each eye for further querying (so that the query iris would not be included in the collection and skew the query results), which led to a collection of 256 irises of 64 people.
An example of several irises from the collection is shown in Figure 3, the first 12
query vectors are shown in Figure 8. We did not isolate the central part and eyelids to
provide comparable results with[
Generated “Eigenirises” and Reconstructed Images Many of tested methods were able to generate a set of base images, which could be considered to be “eigenirises” as is the case of PCA, SVD and several other methods. We are going to provide examples of both factors (base vectors) – “eigenirises” and reconstructed images which can be obtained from regenerated Ak. We calculated results for all methods in several dimensions, for the demonstration images we will use k = 64. We do not provide these images for FastMap, where it is not possible (we could have provided the images used as pivots in each step of FastMap process).
With SVD, we obtain factors with different generality, the most general being among the first. The first few are shown in figure 4. The eigenirises with higher index bring more details to reconstructed images.
The reconstructed images for rank-64 SVD method are somewhat blurred, but generally still recognizable, which can bee observed in figure 5.
The SDD method differs slightly from previous methods, since each factor contains only values {−1, 0, 1}. Gray in the factors shown in figure 6 represents 0; −1 and 1 are represented with black and white respectively.
The images in figure 7 are reconstructed least exactly from all methods (although consistently), but this is to be expected due to the three-valued encoding of base vectors. One may note a general loss of fine details, which is unfortunate, since it means that the query process would be highly affected and the retrieval results poor. Fig. 6. First 18 base vectors (out of 100) for SDD method
First, we calculated the mean average precision (MAP) for all relevant images in rank lists. The relative MAPs (against original matrix A – 100%) are shown in Table 1.
One would suspect, that querying in original dimension would provide better results that any of the dimension reduction methods. In Table 2 we show the number of queries, where the first returned iris was of the same person (out of 128). 5
Conclusion In this paper, we have compared several dimension reduction methods on real-live image data (using L2 metrics). Whilst the SVD is known to provide quality results, it is computationally expensive and in case we only need to beat the “curse of dimensionality” by reducing the dimension, FastMap may suffice.
There are some other newly-proposed methods, which may be interesting for
future testing, e.g. the SparseMap [