Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> From the Publisher: ::: The updated new edition of the classic Introduction to Algorithms is intended primarily for use in undergraduate or graduate courses in algorithms or data structures. Like the first edition,this text can also be used for self-study by technical professionals since it discusses engineering issues in algorithm design as well as the mathematical aspects. ::: In its new edition,Introduction to Algorithms continues to provide a comprehensive introduction to the modern study of algorithms. The revision has been updated to reflect changes in the years since the book's original publication. New chapters on the role of algorithms in computing and on probabilistic analysis and randomized algorithms have been included. Sections throughout the book have been rewritten for increased clarity,and material has been added wherever a fuller explanation has seemed useful or new information warrants expanded coverage. ::: As in the classic first edition,this new edition of Introduction to Algorithms presents a rich variety of algorithms and covers them in considerable depth while making their design and analysis accessible to all levels of readers. Further,the algorithms are presented in pseudocode to make the book easily accessible to students from all programming language backgrounds. ::: Each chapter presents an algorithm,a design technique,an application area,or a related topic. The chapters are not dependent on one another,so the instructor can organize his or her use of the book in the way that best suits the course's needs. Additionally,the new edition offers a 25% increase over the first edition in the number of problems,giving the book 155 problems and over 900 exercises thatreinforcethe concepts the students are learning. <s> BIB001 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> Biometric identification has emerged as a reliable means of controlling access to both physical and virtual spaces. In spite of the rapid proliferation of large-scale databases, the research has thus far been focused only on accuracy within small databases. However, as the size of the database increases, not only does the response time deteriorate, but so does the accuracy of the system. Thus for larger applications it is essential to prune the database to a smaller fraction which would not only ensure higher speeds, but also aid in achieving higher accuracy. Unlike structured information such as text or numeric data that can be sorted, biometric data does not have a natural sorting order making indexing the biometric database a challenging problem. In this paper we show the efficacy of indexing hand geometry biometric using the Pyramid Technique, to reduce the search space to just 8.86% of the entire database, while maintaining a 0% FRR. <s> BIB002 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> The paper proposes an efficient indexing scheme for binary feature template using B+ tree. In this scheme the ::: input image is decomposed into approximation, vertical, horizontal and diagonal coefficients using the discrete ::: wavelet transform. The binarized approximation coefficient at second level is divided into four quadrants of equal ::: size and Hamming distance (HD) for each quadrant with respect to sample template of all ones is measured. This ::: HD value of each quadrant is used to generate upper and lower range values which are inserted into B+ tree. ::: The nodes of tree at first level contain the lower and upper range values generated from HD of first quadrant. ::: Similarly, lower and upper range values for the three quadrants are stored in the second, third and fourth level ::: respectively. Finally leaf node contains the set of identifiers. At the time of identification, the test image is ::: used to generate HD for four quadrants. Then the B+ tree is traversed based on the value of HD at every node ::: and terminates to leaf nodes with set of identifiers. The feature vector for each identifier is retrieved from the ::: particular bin of secondary memory and matched with test feature template to get top matches. The proposed ::: scheme is implemented on ear biometric database collected at IIT Kanpur. The system is giving an overall ::: accuracy of 95.8% at penetration rate of 34%. <s> BIB003 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> This paper proposes an efficient indexing technique that can be used in an identification system with large multimodal biometric databases. The proposed technique is based on Kd-tree with feature level fusion which uses the multi- dimensional feature vector. A multi dimensional feature vector of each trait is first normalized and then, it is projected to a lower dimensional feature space. The reduced dimensional feature vectors are fused at feature level and the fused feature vectors are used to index the database by forming Kd-tree. The proposed method reduces the data retrieval time along with possible error rates. The system is tested on multimodal databases (feature level fusion of ear, face, iris and signature) consists of 5400 images of 150 subjects (i.e. 9 images per subject per trait). Out of the 9, 8 images are used for training and 1 is used for testing. The performance of the proposed indexing technique has been compared with indexing based on score level fusion. It is found that proposed technique based on feature level fusion performs better than score level fusion. <s> BIB004 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> Given a query iris image, the goal of indexing is to identify and retrieve a small subset of candidate irides from the database in order to determine a possible match. This can significantly improve the response time of iris recognition systems operating in the identification mode. In this work, we analyze two different approaches to iris indexing. The first technique is based on the analysis of IrisCodes (post-encoding indexing); the second technique is based on the analysis of features extracted from the iris texture (pre-encoding indexing). Experiments on a subset of the publicly available CASIA-IrisV3 database compare the two approaches and illustrate the potential of the proposed indexing methods for large scale iris identification. <s> BIB005 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> The key concern of indexing is to retrieve small portion of database for searching the query. In the proposed paper iris database is indexed using energy histogram. The normalised iris image is divided into subbands using multiresolution DCT transformation. Energy based his- togram is formed for each subband using all the images in the database. Each histogram is divided into fixed size bins to group the iris images having similar energy value. The bin number for each subband is obtained and all subands are traversed in Morton order to form a global key for each image. During database preparation the key is used to traverse the B tree. The images with same key are stored in the same leaf node. For a given query image, the key is generated and tree is traversed to end up to a leaf node. The templates stored at the leaf node are retrieved and compared with the query template to find the best match. The proposed indexing scheme is showing considerably low penetration rate of 0.63%, 0.06% and 0.20% for CASIA, BATH and IITK iris databases respectively. <s> BIB006 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> Given the existence of large fingerprint databases, including distributed systems, the development of algorithms for performing fast searches in them has become the important topic for biometric researchers. In this paper, we propose a new indexing method for fingerprint templates consisting of a set of minutia points. In contrast to previously presented methods, our algorithm is tree-based and well addresses the efficiency needs of complex (possibly distributed) systems. One large index tree is constructed and the enrolled templates are represented by the leaves of the tree. The branches in the index tree correspond to different local configurations of minutia points. Searching the index tree entails extracting local minutia neighborhoods of the test fingerprint and matching them against tree nodes. Therefore, the search time does not depend on the number of enrolled fingerprint templates, but only on the index tree configuration. This framework can be adapted for different tree-building parameters (feature sets, indexing levels, bin boundaries) according to user requirements and different enrollment and searching techniques can be applied to improve accuracy. We conduct a number of the experiments on Fingerprint Verification Competition databases, as well as the databases of synthetically generated fingerprint templates. The experiments confirm the ability of the proposed algorithm to find correct matches in the database and the minimum search time requirements. <s> BIB007 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> This paper proposes a hierarchical approach to retrieve an iris image efficiently from for a large iris database. This approach is a combination of both iris color and texture. Iris color is used for indexing and texture is used for retrieval of iris images from the indexed iris database. An index which is determined from the iris color is used to filter out the images that are not similar to the query image in color. Further, iris texture features of those filtered images, are used to determine the images which are similar to the query image. The iris color information helps to design an efficient indexing scheme based on color indices. The color indices are computed by averaging the intensity values of all red and blue color pixels. Kd-tree is used for real-time indexing based on color indices. The iris texture features are obtained through Speeded Up Robust Features (SURF) algorithm. These features are used to get the query's corresponding image at the top best match. The performance of the proposed indexing scheme is compared with two well known iris indexing schemes (Mehrotra, Majhi, & Gupta, 2010; Puhan & Sudha, 2008) on UPOL (Dobes, Machala, Tichavsky, & Pospi'sil, 2004) and UBIRIS (Proencca & Alexandre, 2005) iris databases. It is observed that combination of iris color and texture improves the performance of iris recognition system. <s> BIB008 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> Most of the methods to index iris biometric signatures were designed for decision environments with a clear separation between genuine and impostor matching scores. However, in case of less controlled data acquisition, images will be degraded and the decision environments poorly separated. This paper proposes an indexing/retrieval method for degraded images and operates at the code level, making it compatible with different feature encoding strategies. Gallery codes are decomposed at multiple scales, and according to their most reliable components at each scale, the position in an n-ary tree determined. In retrieval, the probe is decomposed similarly, and the distances to multiscale centroids are used to penalize paths in the tree. At the end, only a subset of the branches is traversed up to the last level. When compared with related strategies, the proposed method outperforms them on degraded data, particularly in the performance range most important for biometrics . Finally, according to the computational cost of the retrieval phase, the number of enrolled identities above which indexing is computationally cheaper than an exhaustive search is determined. <s> BIB009 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> A content-based indexing approach that facilitates the iris image database retrieval process is provided in this article. Our indexing model is based on a HOG-based image feature extraction producing high-dimension feature vectors that are accessed via SAM (Spatial Access Methods). These content-based feature vectors are indexed by using a K-D-tree indexing structure. An efficient image retrieval procedure, using a relevance-feedback scheme and performing a K-NN database search based on this index, is then described in our paper. <s> BIB010 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> Conventional biometric identification systems require exhaustive 1 ∶ N comparisons in order to identify biometric probes, i.e. comparison time frequently dominates the overall computational workload. Biometric database indexing represents a challenging task since biometric data is fuzzy and does not exhibit any natural sorting order. In this paper we present a preliminary study on the feasibility of applying Bloom filters for the purpose of iris biometric database indexing. It is shown, that by constructing a binary tree data structure of Bloom filters extracted from binary iris biometric templates (iris-codes) the search space can be reduced to O(logN). In experiments, which are carried out on a database of N = 256 classes, biometric performance (accuracy) is maintained for different conventional identification systems. Further, perspectives on how to employ the proposed scheme on large-scale databases are given. <s> BIB011 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> Many related studies have reported promising results in finger vein recognition, but it is still challenging to perform robust image retrieval, especially in the application scenarios with large scale populations. With the purpose in consideration, this paper presents a binary search path of hierarchical vocabulary tree based finger vein image retrieval method. In detail, a vocabulary tree is built based on the local finger vein textons by the hierarchical k-means method. Each image patch is represented by the binary path in the search of its most similar leaf node, and the value of each bit in the path is labeled as 1 or 0 according to whether the corresponding node is passed or skipped in search. The similarity of two images is defined as the number of overlapped bits in all involved path pairs. And, the enrolled images with top t scores in the sorted score vector will be selected as candidates to narrow the search space. Experimental results on five finger vein databases confirm that the proposed method can improve the retrieval performance on both accuracy and efficiency. <s> BIB012 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> Indexing/retrieving sets of iris biometric signatures has been a topic of increasing popularity, mostly due to the deployment of iris recognition systems in nationwide scale scenarios. In these conditions, for each identification attempt, there might exist hundreds of millions of enrolled identities and is unrealistic to match the probe against all gallery elements in a reasonable amount of time. Hence, the idea of indexing/retrieval is - upon receiving one sample - to find in a quick way a subset of elements in the database that most probably contains the identity of interest, i.e., the one corresponding to the probe. Most of the state-of-the-art strategies to index iris biometric signatures were devised to decision environments with a clear separation between genuine and impostor matching scores. However, if iris recognition systems work in low quality data, the resulting decision environments are poorly separable, with a significant overlap between the distributions of both matching scores. This chapter summarizes the state-of-the-art in terms of iris biometric indexing/retrieval and focuses in an indexing/retrieval method for such low quality data and operates at the code level, i.e., after the signature encoding process. Gallery codes are decomposed at multiple scales, and using the most reliable components of each scale, their position in a n-ary tree is determined. During retrieval, the probe is decomposed similarly, and the distances to multi-scale centroids are used to penalize paths in the tree. At the end, only a subset of branches is traversed up to the last level. <s> BIB013 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> We present a multi-iris indexing system for efficient and accurate large-scale identification. The system is based on Bloom filters and binary search trees. We describe and empirically evaluate several possible information fusion strategies for the system. Those experiments are performed using a combination of several publicly available datasets; the proposed system is tested in an open-set identification scenario consisting of 6,000 genuine and 100,000 impostor transactions. The system maintains the near-optimal biometric performance of an iris-code, score fusion based baseline system, while reducing the required lookup workload to less than 1% thereof. <s> BIB014 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> Indexing of iris data is required to facilitate fast search in large-scale biometric systems. Previous works addressing this issue were challenged by the tradeoffs between accuracy, computational efficacy, storage costs, and maintainability. This work presents an iris indexing approach based on rotation invariant iris representation and LSH-Forest to produce an accurate and easily maintainable indexing structure. The complexity of insertion or deletion in the proposed method is limited to the same logarithmic complexity of a query and the required storage grows linearly with the database size. The proposed approach was extended into a multi-instance iris indexing scheme resulting in a clear performance improvement. Single iris indexing scored a hit rate of 99.7% at a 0.1% penetration rate while multi-instance indexing scored a 99.98% hit rate at the same penetration rate. The evaluation of the proposed approach was conducted on a large database of 50k references and 50k probes of the left and the right irises. The advantage of the proposed solution was put into prospective by comparing the achieved performance to the reported results in previous works. <s> BIB015 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> Explosive growth in the volume of stored biometric data has resulted in classification and indexing becoming important operations in image database systems. Consequently, researchers are focused on finding suitable features of images that can be used as indexes. Stored templates have to be classified and indexed based on these extracted features in a manner that enables access to and retrieval of those data by efficient search processes. This paper proposes a method that extracts the most relevant features of iris images to facilitate minimisation of the indexing time and the search area of the biometric database. The proposed method combines three transformation methods DCT, DWT and SVD to analyse iris images and extract their local features. Further, the scalable K-means++ algorithm is used for partitioning and classification processes, and an efficient parallel technique that divides the features groups causing the formation of two b-trees based on index keys is applied for search and retrieval. Moreover, search within a group is achieved using a proposed half search algorithm. Experimental results on three different publicly iris databases indicate that the proposed method results in a significant performance improvement in terms of bin miss rate and penetration rate compared with conventional methods. <s> BIB016 </s> Computational workload in biometric identification systems: an overview <s> 3.3.1 <s> Large-scale biometric deployments are becoming ubiquitous. The computational workload of the conventional retrieval method, requiring 1:N comparisons in the identification mode, is impractical for such systems. In recent years, many approaches for efficient biometric identification were proposed, but their scalability is often questionable. Furthermore, the lack of a unified methodology for biometric workload reduction reporting often makes a direct benchmark or a thorough evaluation of the proposed schemes cumbersome. We present an iris indexing scheme based on Bloom filters and binary search trees. With a statistical model, the system is shown to be theoretically scalable for arbitrarily many enrollees. We evaluate this system on a combined database from several publicly available datasets, containing a total of 11,936 iris images from 1477 instances. In an open-set identification scenario, the system maintains the biometric performance of an iris-code 1:N baseline – a true positive identification rate of approximately 98% measured at 0.1% false positive identification rate, at only 10% of the baseline workload. In a proof-of-concept multi-iris indexing experiment, the true positive identification rate is further increased to over 99%, without additional workload costs. Lastly, we define several prerequisites necessary for a transparent and comprehensive methodology of biometric workload reduction results dissemination. <s> BIB017
Hierarchical: Approaches in this category are most often tree-based, most prominently utilising k-d trees (e.g.  BIB008 BIB010 BIB004 ), b or b+ trees (e.g. BIB006 BIB016 BIB002 BIB003 ), other tree-like search structures (e.g. BIB013 BIB005 BIB007 BIB011 BIB009 BIB012 ), and forests thereof (e.g. BIB014 BIB017 BIB015  ). The differences between the various types of used trees (some of which are each other's generalisations) are out of scope for this article; instead, the reader is referred to e.g.  BIB001 . The key idea is to create a search structure, which repeatedly partitions the data (i.e. the search space -the enrolment database) into successively smaller subsets. For this partitioning, the highly discriminative (and high-dimensional) feature vectors themselves and/or the more coarse auxiliary features can be used. By doing so, sub-linear or even logarithmic lookup complexity can be achieved, thereby substantially reducing the computational workload of biometric identification.