Computational workload in biometric identification systems: an overview <s> Multi-Feature: <s> With the current rapid growth in multimedia technology, there is an imminent need for efficient techniques to search and query large image databases. Because of their unique and peculiar needs, image databases cannot be treated in a similar fashion to other types of digital libraries. The contextual dependencies present in images, and the complex nature of two-dimensional image data make the representation issues more difficult for image databases. An invariant representation of an image is still an open research issue. For these reasons, it is difficult to find a universal content-based retrieval technique. Current approaches based on shape, texture, and color for indexing image databases have met with limited success. Further, these techniques have not been adequately tested in the presence of noise and distortions. A given application domain offers stronger constraints for improving the retrieval performance. Fingerprint databases are characterized by their large size as well as noisy and distorted query images. Distortions are very common in fingerprint images due to elasticity of the skin. In this paper, a method of indexing large fingerprint image databases is presented. The approach integrates a number of domain-specific high-level features such as pattern class and ridge density at higher levels of the search. At the lowest level, it incorporates elastic structural feature-based matching for indexing the database. With a multilevel indexing approach, we have been able to reduce the search space. The search engine has also been implemented on Splash 2-a field programmable gate array (FPGA)-based array processor to obtain near-ASIC level speed of matching. Our approach has been tested on a locally collected test data and on NIST-9, a large fingerprint database available in the public domain. <s> BIB001 </s> Computational workload in biometric identification systems: an overview <s> Multi-Feature: <s> Automatic personal identification is a significant component of security systems with many challenges and practical applications. The advances in biometric technology have led to the very rapid growth in identity authentication. This paper presents a new approach to personal identification using palmprints. To tackle the key issues such as feature extraction, representation, indexing, similarity measurement, and fast search for the best match, we propose a hierarchical multifeature coding scheme to facilitate coarse-to-fine matching for efficient and effective palmprint verification and identification in a large database. In our approach, four-level features are defined: global geometry-based key point distance (Level-1 feature), global texture energy (Level-2 feature), fuzzy "interest" line (Level-3 feature), and local directional texture energy (Level-4 feature). In contrast to the existing systems that employ a fixed mechanism for feature extraction and similarity measurement, we extract multiple features and adopt different matching criteria at different levels to achieve high performance by a coarse-to-fine guided search. The proposed method has been tested in a database with 7752 palmprint images from 386 different palms. The use of Level-1, Level-2, and Level-3 features can remove candidates from the database by 9.6%, 7.8%, and 60.6%, respectively. For a system embedded with an Intel Pentium III processor (500 MHz), the execution time of the simulation of our hierarchical coding scheme for a large database with 10/sup 6/ palmprint samples is 2.8 s while the traditional sequential approach requires 6.7 s with 4.5% verification equal error rate. Our experimental results demonstrate the feasibility and effectiveness of the proposed method. <s> BIB002 </s> Computational workload in biometric identification systems: an overview <s> Multi-Feature: <s> We present a theory for constructing linear subspace approximations to face-recognition algorithms and empirically demonstrate that a surprisingly diverse set of face-recognition approaches can be approximated well by using a linear model. A linear model, built using a training set of face images, is specified in terms of a linear subspace spanned by, possibly nonorthogonal vectors. We divide the linear transformation used to project face images into this linear subspace into two parts: 1) a rigid transformation obtained through principal component analysis, followed by a nonrigid, affine transformation. The construction of the affine subspace involves embedding of a training set of face images constrained by the distances between them, as computed by the face-recognition algorithm being approximated. We accomplish this embedding by iterative majorization, initialized by classical MDS. Any new face image is projected into this embedded space using an affine transformation. We empirically demonstrate the adequacy of the linear model using six different face-recognition algorithms, spanning template-based and feature-based approaches, with a complete separation of the training and test sets. A subset of the face-recognition grand challenge training set is used to model the algorithms and the performance of the proposed modeling scheme is evaluated on the facial recognition technology (FERET) data set. The experimental results show that the average error in modeling for six algorithms is 6.3% at 0.001 false acceptance rate for the FERET fafb probe set which has 1195 subjects, the most among all of the FERET experiments. The built subspace approximation not only matches the recognition rate for the original approach, but the local manifold structure, as measured by the similarity of identity of nearest neighbors, is also modeled well. We found, on average, 87% similarity of the local neighborhood. We also demonstrate the usefulness of the linear model for algorithm-dependent indexing of face databases and find that it results in more than 20 times reduction in face comparisons for Bayesian, elastic bunch graph matching, and one proprietary algorithm. <s> BIB003 </s> Computational workload in biometric identification systems: an overview <s> Multi-Feature: <s> Latent fingerprint identification is of critical importance to law enforcement agencies in apprehending criminals. Considering the huge size of fingerprint databases maintained by law enforcement agencies, exhaustive one-to-one matching is impractical and a database filtering technique is necessary to reduce the search space. Due to low image quality and small finger area of latent fingerprints, it is necessary to use several features for an efficient and reliable filtering system. A multi-stage filtering system is proposed, which utilizes pattern type, singular points and orientation field. We have tested our system by searching 258 latent fingerprints in NIST SD27 against a background database containing 10,258 rolled fingerprints (obtained by combining 2,000 in NIST SD4, 8,000 in SD14 and 258 in SD27). Although latent fingerprints contain very limited information, the filtering system not only improved the matching speed by three fold but also improved the rank-1 matching accuracy from 70.9% to 73.3%. <s> BIB004 </s> Computational workload in biometric identification systems: an overview <s> Multi-Feature: <s> In biometric identification systems, the identity associated with the input data is determined by comparing it against every entry in the database. This exhaustive matching process increases the response time of the system and, potentially, the rate of erroneous identification. A method that narrows the list of potential identities will allow the input data to be matched against a smaller number of identities. We describe a method for indexing large-scale multimodal biometric databases based on the generation of an index code for each enrolled identity. In the proposed method, the input biometric data is first matched against a small set of reference images. The set of ensuing match scores is used as an index code. The index codes of multiple modalities are then integrated using three different fusion techniques in order to further improve the indexing performance. Experiments on a chimeric face and fingerprint bimodal database indicate a 76% reduction in the search space at 100% hit rate. These results suggest that indexing has the potential to substantially improve the response time of multimodal biometric systems without compromising the accuracy of identification. <s> BIB005 </s> Computational workload in biometric identification systems: an overview <s> Multi-Feature: <s> Rotation compensation is one of the computational bottlenecks in large scale iris-based identification schemes, since a significant amount of Hamming distance computations is required in a single match due to the necessary shifting of the iris codes to compensate for eye tilt. To cope with this problem, a serial classifier combination approach is proposed for iris-based identification, combining rotation-invariant pre-selection with a traditional rotation compensating iris code-based scheme. The primary aim, a reduction of computational complexity, can easily be met at comparable recognition accuracy, the computational effort required is reduced to 20% or even less of the fully fledged iris code based scheme. As a by-product, the recognition accuracy is shown to be additionally improved in open-set scenarios. <s> BIB006 </s> Computational workload in biometric identification systems: an overview <s> Multi-Feature: <s> Biometric features are extracted from a complex pattern and stored as high dimensional data. These data do not follow traditional sorting order like numerical and alphabetical data. Hence, a linear search method makes the identification process extremely slow as well as increases the false acceptance rate beyond an acceptable range. To address this problem, we propose an efficient indexing mechanism to retrieve iris biometric templates using Gabor energy features. The Gabor energy features are calculated from the preprocessed iris texture in different scales and orientations to generate a 12-dimensional index key for an iris template. An index space is created based on the values of index keys of all individuals. A candidate set is retrieved from the index space based on the values of query index key. Next, we rank the retrieved candidates according to their occurrences. If the identity of the query template is matched, then it is a hit, otherwise a miss. We have experimented our approach with Bath, CASIA-V3-Interval, CASIA-V4-Thousand, MMU2, and WVU iris databases. Our proposed approach gives 11.3%, 14.5%, 16.3%, 13.5%, and 10.3% penetration rates and 98.2%, 91.1%, 90.7%, 85.2%, and 96% hit rates for Bath, CASIA-V3-Interval, CASIA-V4-Thousand, MMU2, and WVU iris database, respectively, when we consider the retrieving templates up to the fifth rank. Experiments substantiate that our approach is capable of retrieving biometric data with a higher hit rate and lower penetration rate compared to the existing approaches. Application of Gabor energy features to index iris data proves to be effective for fast and accurate retrieval. With our proposed approach, it is possible to retrieve a set of iris templates similar to the query template in the order of milliseconds and is independent of sizes of databases. <s> BIB007 </s> Computational workload in biometric identification systems: an overview <s> Multi-Feature: <s> In a biometric identification system, the identity corresponding to the input data (probe) is typically determined by comparing it against the templates of all identities in a database (gallery). Exhaustive matching against a large number of identities increases the response time of the system and may also reduce the accuracy of identification. One way to reduce the response time is by designing biometric templates that allow for rapid matching, as in the case of IrisCodes. An alternative approach is to limit the number of identities against which matching is performed based on criteria that are fast to evaluate. We propose a method for generating fixed-length codes for indexing biometric databases. An index code is constructed by computing match scores between a biometric image and a fixed set of reference images. Candidate identities are retrieved based on the similarity between the index code of the probe image and those of the identities in the database. The proposed technique can be easily extended to retrieve pertinent identities from multimodal databases. Experiments on a chimeric face and fingerprint bimodal database resulted in an 84% average reduction in the search space at a hit rate of 100%. These results suggest that the proposed indexing scheme has the potential to substantially reduce the response time without compromising the accuracy of identification. <s> BIB008 </s> Computational workload in biometric identification systems: an overview <s> Multi-Feature: <s> Photos with people (e.g., family, friends, celebrities, etc.) are the major interest of users. Thus, with the exponentially growing photos, large-scale content-based face image retrieval is an enabling technology for many emerging applications. In this work, we aim to utilize automatically detected human attributes that contain semantic cues of the face photos to improve content-based face retrieval by constructing semantic codewords for efficient large-scale face retrieval. By leveraging human attributes in a scalable and systematic framework, we propose two orthogonal methods named attribute-enhanced sparse coding and attribute-embedded inverted indexing to improve the face retrieval in the offline and online stages. We investigate the effectiveness of different attributes and vital factors essential for face retrieval. Experimenting on two public datasets, the results show that the proposed methods can achieve up to 43.5% relative improvement in MAP compared to the existing methods. <s> BIB009 </s> Computational workload in biometric identification systems: an overview <s> Multi-Feature: <s> Fingerprints have been widely used as a biometric trait for person recognition. Due to the wide acceptance and deployment of fingerprint matching systems, there is a steady increase in the size of fingerprint databases in law enforcement and national ID agencies. Thus, it is of great interest to develop methods that, for a given query fingerprint (rolled or latent), can efficiently filter out a large portion of the reference or background database based on a coarse matching (or indexing) strategy. In this work, we propose an indexing technique, primarily for latents, that combines multiple level 1 and level 2 features to filter out a large portion of the background database while maintaining the latent matching accuracy. Our approach consists of combining minutiae, singular points, orientation field and frequency information. Experimental results carried out on 258 latents in NIST SD27 against a large background database (267K rolled prints) show that the proposed approach outperforms state-of-the-art fingerprint indexing techniques reported in the literature. At a penetration rate of 20%, our approach can reach a hit rate of 90.3%, with a five-fold reduction in the latent search (indexing + matching) time, while maintaining the latent matching accuracy. <s> BIB010 </s> Computational workload in biometric identification systems: an overview <s> Multi-Feature: <s> Face retrieval is an enabling technology for many applications, including automatic face annotation, deduplication, and surveillance. In this paper, we propose a face retrieval system which combines a k-NN search procedure with a COTS matcher (PittPatt1) in a cascaded manner. In particular, given a query face, we first pre-filter the gallery set and find the top-k most similar faces for the query image by using deep facial features that are learned with a deep convolutional neural network. The top-k most similar faces are then re-ranked based on score-level fusion of the similarities between deep features and the COTS matcher. To further boost the retrieval performance, we develop a manifold ranking algorithm. The proposed face retrieval system is evaluated on two large-scale face image databases: (i) a web face image database, which consists of over 3, 880 query images of 1, 507 subjects and a gallery of 5, 000, 000 faces, and (ii) a mugshot database, which consists of 1, 000 query images of 1, 000 subjects and a gallery of 1, 000, 000 faces. Experimental results demonstrate that the proposed face retrieval system can simultaneously improve the retrieval performance (CMC and precision-recall) and scalability for large-scale face retrieval problems. <s> BIB011
The key idea behind the multi-feature approaches is the extraction of one or several auxiliary features, which in themselves do not have sufficient discriminative power for unique identification, but can nonetheless significantly reduce the search space (i.e. by acting as an index, which allows to determine a candidate short-list). Auxiliary features such as orientation field, ridge density, local (minutiae-based) and global (e.g. fingerprint types, which have been in use for decades for the purposes of manual indexing of analog ten-fingerprint records with the Henry Classification System, see e.g.   , and subsection 3.2) can be extracted from fingerprint images; some of them also pertain to other characteristics, such as vascular and palmprint patterns. Several authors (e.g. [39-44, 46, 57] ) utilise such coarse features as an index in a pre-filtering step. In other cases, the methods proposed in the scientific literature do not rely on specific, biometric characteristic-dependent features as above; instead, to create an index, they utilise general-purpose algorithms, such as texture extractors (e.g. BIB009 BIB007 ), principal component analysis (e.g. BIB003 ), and, more recently, deep learning (e.g. BIB011  ). It should be noted, that the pre-filtering can happen in a cascading manner, over two (e.g. BIB005 BIB008 BIB006 ) or multiple (e.g. BIB001 BIB004 BIB002 ) levels, which successively produce smaller candidate lists, or through direct application of information fusion strategies to the extracted features (e.g. BIB010 ). However, an in-depth analysis and evaluation concerning which of the methods (cascades or fusion) performs better has not yet been reported in the scientific literature.