# A Data Structure for Efficient Biometric Identification

Kensuke Baba, Serina Egawa

► To cite this version:

Kensuke Baba, Serina Egawa. A Data Structure for Efficient Biometric Identification. 1st International Conference on Information and Communication Technology (ICT-EurAsia), Mar 2013, Yogyakarta, Indonesia. pp.528-533, 10.1007/978-3-642-36818-9_61. hal-01480259

HAL Id: hal-01480259

https://inria.hal.science/hal-01480259

Submitted on 1 Mar 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
A Data Structure for Efficient Biometric
Identification

Kensuke Baba and Serina Egawa

Kyushu University, Fukuoka, Japan

{baba.kensuke.060@m, s-egawa@soc.ait}.kyushu-u.ac.jp

**Abstract.** This paper proposes an efficient algorithm for personal iden-
tification with biometric images. In identification based on image com-
parison, the number of comparisons is an important factor to estimate the
total processing time in addition to the processing time of a single com-
parison. Maeda et al. proposed an identification algorithm that reduces
the number of comparisons from the linear search algorithm, however
the processing time of each comparison is proportional to the number
of registered images. The algorithm in this paper is an improvement of
the algorithm by Maeda et al. with constant-time image comparisons.
This paper evaluates the algorithms in terms of the processing time and
the accuracy with practical palmprint images, and proves that the novel
algorithm can reduce the number of image comparisons from the linear
search algorithm as the algorithm by Maeda et al. without loss of the
accuracy.

# 1 Introduction

Personal authentication is an essential issue in many systems, especially, biometric authentication is an important technology to compensate some weaknesses of token- and knowledge-based authentication [6]. With the spread of computers and networks, the number of persons who use each application system is supposed to become huge. For authentication based on biometric information, there exist two possible procedures of matching, that is, verification and identification [6]. Identification searches for the target person, while verification confirms that the target person is a particular person. Identification requires a long processing time and it becomes more conspicuous in systems with a large number of users.

The aim of this paper is an acceleration of personal identification with bio-
metric images. If biometric images are formalized as numerical vectors, the iden-
tification can be reduced to the problem of nearest neighbor search, that is, to
search a set of vectors for the most similar vector to the input vector. Hence, an
approach to the aim is an acceleration of nearest neighbor search by a suitable
data structure [4] or an approximation [5]. In some practical systems, however,
the process of image matching is implemented as a distinct module and treated
as a black box whose input is a pair of two images and output is a similarity
between the two images. In such a situation, identification should be conducted
on the basis of image comparisons. In this paper, we focus on such comparison-based algorithms for identification with biometric images.

If we arrow some deterioration of accuracy, we can consider a method that searches for an image whose similarity with the input image is larger than a given threshold, instead of the most similar image. In this method, the processing time can be reduced by stopping the search when a similar image is found. Maeda et al. [9] proposed an identification algorithm (MSM) that reduces the number of image comparisons in the linear search. The main idea of the algorithm is that, for *N* images that were registered for authentication, a similarity between any pair of the registered images is calculated in advance, and then the order of comparisons with the input image is decided according to the *N* × *N* matrix of the similarities. They reported that the average number of comparisons is experimentally $O(\sqrt{N})$, while that in the linear search is $O(N)$. However, the process to choose the image for each comparison is comparing the *N* row vectors in the matrix, hence the processing time of a single image comparison is proportional to *N*. Therefore, the total processing time is estimated to be proportional to $N^{3/2}$ on the assumption that the number of comparisons is $O(\sqrt{N})$ [3].

In this paper, we propose an identification algorithm with biometric images as an improvement of MSM. The main idea is to prepare the order of image comparisons statically by a kd-tree [4] instead of the dynamic $O(N)$ computation from the $N \times N$ matrix. By the assumption of comparison-based identification, any algorithm requires $O(N)$ comparisons of images. The time complexity of the novel algorithm is no more than $O(N)$. Additionally, we examine the processing time and the accuracy of the three identification algorithms, the novel one, MSM, and the linear search, with the features extracted by Scale-Invariant Feature Transform (SIFT) [7, 8] from practical palmprint images. We confirm that the novel algorithm reduces the number of image comparisons as MSM and does not worsen the accuracy.

## 2 Preliminaries

The problem of personal identification with biometric images is called identifcation. In identification, each image corresponds to a person. The input of identification consists of an image (called an input image) and a set of images (called a set of templates). The output is the name of the person judged to correspond to the input image or “null” if the person of the input image is judged to be not included in the persons of the templates.

In the rest of this paper, we consider comparison-based algorithms for identification. We suppose that an idea of similarity on biometric images is given and only the similarity of images can be obtained as leads for identification. Then, the linear search algorithm is, for a given threshold,

- Compare the input image with each template in the set successively in an order;

- If a template whose similarity with the input image is not less than the threshold is found, then output the person of the image and terminate;
- If the similarities with every templates are less than the threshold, output "null" and terminate.

For the accuracy of an identification algorithm, we consider "the rate that the person who corresponds to the output image is different from the person of the input image", and this rate is called the error rate (ER) of the algorithm.

## 3 The Algorithm

We propose an identification algorithm that reduces the number of image comparisons in the linear search algorithm by a tree for deciding the order of image comparisons.

Let $N$ be the number of templates and $t_i$ a template for $1 \le i \le N$. First, we make the $N \times N$ matrix whose $(i,j)$-element $m_{ij}$ is the similarity between $t_i$ and $t_j$ for $1 \le i, j \le N$. Then, we construct a tree that decides the order of image comparisons as follows.

1. Choose $\ell$ templates for the initial comparisons;

2. Construct a kd-tree for the $N \ell$-dimensional vectors obtained by 1;

3. Add an order of image comparison to each leaf of the tree in 2 on the basis of Euclidean distance on the $\ell$-dimensional vectors.

Let $t_{r_1}, t_{r_2}, \dots, t_{r_\ell}$ be the $\ell$ templates chosen in the process 1. In process 2, the kd-tree is constructed for the $N \ell$-dimensional vectors

$$ (m_{1r_1}, m_{1r_2}, \dots, m_{1r_\ell}), (m_{2r_1}, m_{2r_2}, \dots, m_{2r_\ell}), \dots, (m_{Nr_1}, m_{Nr_2}, \dots, m_{Nr_\ell}), $$

and each of the $N$ leaves corresponds to a unique template. In process 3, an order of image comparisons is expressed as a list of the $N$ templates, and the order for the leaf of $t_i$ is decided as follows.

- The first template is $t_i$;

- The rest is the list of the templates except for $t_i$ such that the $j$th template is nearer to $t_i$ than $(j+1)$th template for $1 \le j \le N-2$,

where the distance between $t_i$ and $t_j$ is the distance between $(m_{ir_1}, m_{ir_2}, \dots, m_{ir_3})$ and $(m_{jr_1}, m_{jr_2}, \dots, m_{jr_3})$.

With the previous tree, identification is conducted as follows.

1. Compare the input image with the $\ell$ templates and obtain an $\ell$-dimensional vector;

2. Search the nearest vector to the obtained vector in the constructed tree, and decide the order of comparisons;

3. Conduct the linear search algorithm with the decided order.

The process 1 requires $\ell$ comparisons of images. Generally, nearest neighbor search with a kd-tree in $N \ell$-dimensional vectors needs $O(N^{1-1/\ell})$ time. In the process 3, since we have a fixed order of image comparisons, the processing time of a single comparison is constant. Therefore, the total processing time of the proposed algorithm is no more than $O(N)$. The practical number of image comparisons in the proposed algorithm is examined experimentally in the following section.
# 4 Experiments

The proposed algorithm in Section 3 was applied to practical palmprint images and evaluated in terms of the ER and the number of image comparisons.

## 4.1 Image Matching

We consider a matching of SIFT features for the comparison of palmprint images. This subsection defines the similarity on palmprint images for identification. In this paper, the region of interest on each palmprint was extracted as the circle that covers the maximal part on a palm as [3].

SIFT is one of the popular methods for image matching and object recognition and the detailed mechanism can be found in [7, 8]. SIFT translates an image into a set of key points and each key point has a vector as its feature. Then, a comparison of two images is done by matching two sets of key points. There exist several possible procedures for the matching of key points. In this paper, the similarity on images (that is, sets of key points) is defined as follows. Let $P$ and $Q$ be two sets of key points and $v(p)$ the feature vector of a key point $p$. We consider $q_p$, $p_q$, and $m$ such that

- For any $p \in P$, $q_p \in Q$ satisfies that $\|v(q_p) - v(p)\|$ is the smallest in $Q$.

- For any $q \in Q$, $p_q \in P$ satisfies that $\|v(p_q) - v(q)\|$ is the smallest in $P$.

- $m$ is the number of the pairs of $p \in P$ and $q \in Q$ such that $q_p = q$ and $p_q = p$.

Then, the similarity of two images whose features are respectively $P$ and $Q$ is defined to be $m/\max\{|P|, |Q|\}$.

## 4.2 Results

The experiments were conducted on the PolyU Palmprint Database [2]. For the practical process of SIFT, the function “SiftFeatureDetector” in OpenCV [1] was used. The parameter “threshold” of the function was fixed at 0.01 and the other parameters were set to the default values according to the results of some preparatory experiments about the processing time and the error rate of matching.

In addition to the proposed algorithm, MSM [9] and the linear search algorithm were applied to a sample set of palmprint images. The set contains 1,200 images that consists of 8 images times 150 persons. We separated the set into two sets of 4 × 150 images for templates and input images, and repeated each experiment with swapping the sets. The number of image comparisons in MSM depends on the choice of the pair of images for the first comparison, and that in the linear search depends on the order of templates in addition to the choice. Therefore, identification for the two algorithms were repeated for any combination of the initial pair (600 × 600 patterns), and moreover a cyclic order was chosen randomly and fixed for the repetition in the linear search. As for the proposed algorithm, the number of the repetition was 600.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** The ERs and the numbers of image comparisons in the proposed algorithm, MSM, and the linear search algorithm.</figcaption></figure>

<table><caption>**Table 1.** The optimum ERs and the numbers of image comparisons at the point of the optimum ERs in the proposed algorithm, MSM, and the linear search algorithm. * is the rate against the number in the linear search algorithm.</caption><thead><tr><th></th><th>ER</th><th>#comparisons (*)</th></tr></thead><tbody><tr><td>linear search</td><td>24.9</td><td>417.3 (1)</td></tr><tr><td>MSM</td><td>20.3</td><td>94.6 (0.23)</td></tr><tr><td>proposed</td><td>20.2</td><td>123.4 (0.30)</td></tr></tbody></table>

We fixed the number of initial comparisons $l = 10$ in the proposed algorithm and 10 initial templates were chosen randomly. Figure 1 shows the ERs and the number of image comparisons in the proposed algorithm with 10 initial comparisons, MSM, and the linear search algorithms at the different values of the threshold for the image similarity. The optimum ERs and the numbers of image comparisons at the optimum points are summarized in Table 1. The results report that the ER of the proposed algorithm is small compared to the linear search algorithm and almost same as MSM. The number of image comparisons in the proposed algorithm was drastically reduced from the linear search algorithm and is slightly larger than MSM.

# 5 Conclusion

This paper proposed an efficient algorithm for personal identification with bio-metric images as an improvement of the algorithm by Maeda et al. (MSM) [9]. We replaced the $O(N)$ process required for every image comparisons in MSM into an overhead of a single $O(N)$ process, where $N$ is the number of the templates. The proposed algorithm, MSM, and the linear search algorithm were evaluated with practical palmprint images in terms of the processing time and the accuracy. By the evaluation, we confirmed that the proposed algorithm can
reduce the number of image comparisons from the linear search algorithm with
no loss of the accuracy similarly as MSM.

In the experiment of the proposed algorithm, the number of initial compar-
isons was fixed to be 10, however the optimum number in the senses of the ER
and the number of comparisons is not clear. To make clear the relation between
the optimum number and the number of templates is one of our future work.

Acknowledgement

This work was partially supported by the Grant-in-Aid for Young Scientists (B)
No. 22700149 of the Ministry of Education, Culture, Sports, Science and Tech-
nology (MEXT) from 2010 to 2012 and CREST program of Japan Science and
Technology Agency (JST) from 2008 to 2012.

References

1. OpenCV. http://opencv.willowgarage.com/wiki/.

2. PolyU Palmprint Database. http://www.comp.polyu.edu.hk/~biometrics/.

3. S. Egawa, A. I. Awad, and K. Baba. Evaluation of acceleration algorithm for bio-metric identification. In *Networked Digital Technologies, Part II*, volume 294 of *Communications in Computer and Information Science*, pages 231–242. Springer, 2012.

4. J. H. Friedman, J. L. Bentley, and R. A. Finkel. An algorithm for finding best matches in logarithmic expected time. *ACM Trans. Math. Softw.*, 3(3):209–226, Sept. 1977.

5. P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In *Proceedings of the thirtieth annual ACM symposium on Theory of computing*, STOC '98, pages 604–613, New York, NY, USA, 1998. ACM.

6. A. K. Jain, A. A. Ross, and K. Nandakumar. *Introduction to Biometrics*. Springer, 2011.

7. D. G. Lowe. Object recognition from local scale-invariant features. In *Proc. IEEE International Conference on Computer Vision*, pages 1150–1157, 1999.

8. D. G. Lowe. Distinctive image features from scale-invariant keypoints. *International Journal of Computer Vision*, 60(2):91–110, 2004.

9. T. Maeda, M. Matsushita, and K. Sasakiwa. Identification algorithm using a match-
ing score matrix. *IEICE Transactions on Information and Systems*, E84-D(7):819-
824, 2001.