Computational workload in biometric identification systems: an overview <s> Sub-sampling: <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> Sub-sampling: <s> AFIS system design and performance is heavily impacted by data correlations and error rate variability both within and across individual fingerprint records, but little is known about these issues. In this paper, we report on experiments done with the best algorithms from six major AFIS vendors tested using a 4128 × 4080 database of electronically collected flat prints. We obtain Receiver Operating Characteristic curves for thumb through ring finger on right and left hands, as well as experimental penetration and binning error rates for one-, two-, four-, and eight-print systems. Impact of binning on the overall ROC curve is measured. “Zero-effort” impostor error rate variability (“lambs” and “wolves”) is observed across the data. <s> BIB002 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> This paper proposes a novel algorithm for the automatic coarse classification of iris images using a box-counting method to estimate the fractal dimensions of the iris. First, the iris image is segmented into sixteen blocks, eight belonging to an upper group and eight to a lower group. We then calculate the fractal dimension value of these image blocks and take the mean value of the fractal dimension as the upper and the lower group fractal dimensions. Finally, all the iris images are classified into four categories in accordance with the upper and the lower group fractal dimensions. This classification method has been tested and evaluated on 872 iris cases, and the proportions of these categories in our database are 5.50%, 38.54%, 21.79%, and 34.17%. The iris images are classified with two algorithms, the double threshold algorithm, which classifies iris images with an accuracy of 94.61%, and the backpropagation algorithm, which is 93.23% accurate. When we allow for the border effect, the double threshold algorithm is 98.28% accurate. <s> BIB003 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> Iris pattern is commonly regarded as a kind of phenotypic feature without relation to the genes. In this paper, we propose a novel ethnic classification method based on the global texture information of iris images. So we would argue that iris texture is race related, and its genetic information is illustrated in coarse scale texture features, rather than preserved in the minute local features of state-of-the-art iris recognition algorithms. In our scheme, a bank of multichannel 2D Gabor filters is used to capture the global texture information and AdaBoost is used to learn a discriminant classification principle from the pool of the candidate feature set. Finally iris images are grouped into two race categories, Asian and non-Asian. Based on the proposed method, we get an encouraging correct classification rate (CCR) of 85.95% on a mixed database containing 3982 iris samples in our experiments. <s> BIB004 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> In this paper, we propose a fast search algorithm for a large fuzzy database that stores iris codes or data with a similar binary structure. The fuzzy nature of iris codes and their high dimensionality render many modern search algorithms, mainly relying on sorting and hashing, inadequate. The algorithm that is used in all current public deployments of iris recognition is based on a brute force exhaustive search through a database of iris codes, looking for a match that is close enough. Our new technique, Beacon Guided Search (BGS), tackles this problem by dispersing a multitude of ldquobeaconsrdquo in the search space. Despite random bit errors, iris codes from the same eye are more likely to collide with the same beacons than those from different eyes. By counting the number of collisions, BGS shrinks the search range dramatically with a negligible loss of precision. We evaluate this technique using 632,500 iris codes enrolled in the United Arab Emirates (UAE) border control system, showing a substantial improvement in search speed with a negligible loss of accuracy. In addition, we demonstrate that the empirical results match theoretical predictions. <s> BIB005 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> In a very large iris database, the design of an effective iris indexing method reduces the computational complexity of feature matching process. This paper presents a new iris indexing technique based on the iris color for noisy iris images. The proposed method using the chrominance components achieves high indexing performance in defocused, reflection-contained and eyelid-occluded iris images. The performance measures such as the hit rate and the penetration rate computed on a recently created noisy iris database, namely UBIRIS (Proenca and Alexandre, 2005), show the effectiveness of the iris color to index very large iris databases. <s> BIB006 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> The goal of this paper is to analyze the texture of irides and determine if they can be quantitatively measured and assigned into multiple categories. Such an exercise would ensure that irides, like fingerprints, can be partitioned into multiple classes thereby allowing for faster retrieval of identities in large scale biometric systems. In order to facilitate this, a set of 68 statistical features is extracted from the iris texture. These features correspond to the high frequency information associated with anatomical structures in the iris such as crypts, furrows and pigment spots. The statistical features extracted from different blocks in the iris are fused at the feature level and decision level. Experimental analysis using the UPOL database indicates the efficacy of the proposed scheme in (a) clustering iris texture, and (b) assigning an input iris to the correct cluster based on its textural content. The feasibility of using blocks of iris to perform partial iris matching is also investigated <s> BIB007 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> This paper addresses the problem of fast fingerprint retrieval in a large database using clustering-based descriptors. Common solutions fall into two categories: classification and indexing. However, those methods only use one form for space narrowing and neglecting the complementary uniqueness of classification and indexing. In addition, there are two major problems in fingerprint identification: partialness and non-linear distortion. Recently, many proposed features focus on global and minutia information and both of them can not deal well with those two problems. This paper has three contributions. First, it proposes a composite classification-indexing-retrieval framework that greatly reduces time complexity. Second, clustering-based descriptors are extracted for indexing so that the search space is narrowed largely. Third, the class-jumping principle (CJP) is proposed to determine the correctness of classification and handle the problem of misclassification. <s> BIB008 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> This work studies eye color as a soft biometric trait and provides a novel insight about the influence of pertinent factors in this context, like color spaces, illumination and presence of glasses. A motivation for the paper is the fact that the human iris color is an essential facial trait for Caucasians, which can be employed in iris pattern recognition systems for pruning the search or in soft biometrics systems for person re-identification. Towards studying iris color as a soft biometric trait, we consider a system for automatic detection of eye color, based on standard facial images. The system entails automatic iris localization, followed by classification based on Gaussian Mixture Models with Expectation Maximization. We finally provide related detection results on the UBIRIS2 database employable in a real time eye color detection system. <s> BIB009 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> Biometrie identification often involves explicit comparison of a probe against each template stored in a database. This process becomes extremely time-consuming as the size of the database increases. Filtering approaches use a light weight comparison to select a smaller set of candidate templates from the database for explicit comparison. However, most existing filtering schemes use specific features that are hand-crafted for the biometrie trait at each stage of the filtering. In this work, we explore the effectiveness of weak features in a cascade for filtering fingerprint databases. We start with a set of potential indexing features computed from minutiae triplets and minutiae quadruplets. Each stage of filtering consists of projecting the probe onto a specific line and the removal of database samples outside a window around the probe. The critical problem in this process is the selection of lines for projection at each stage of the filtering. We show that by using a set of random lines and the proposed fitness function, one can achieve better results that optimization methods such as PCA or LDA. Experimental results show that using an ensemble of projections we can reduce the penetration to 26% at a hit rate of 99%. As each stage of the cascade is extremely fast, and filtering is progressive along the cascade, one can terminate the cascade at any point to achieve the desired performance. One can also combine this method with other indexing methods to improve the overall accuracy and speed. We present detailed experimental results on various aspects of the process on the FVC 2002 dataset. <s> BIB010 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> Fingerprints and palmprints are the most common authentic biometrics for personal identification, especially for forensic security. Previous research have been proposed to speed up the searching process in fingerprint and palmprint identification systems, such as those based on classification or indexing, in which the deterioration of identification accuracy is hard to avert. In this paper, a novel hierarchical minutiae matching algorithm for fingerprint and palmprint identification systems is proposed. This method decomposes the matching step into several stages and rejects many false fingerprints or palmprints on different stages, thus it can save much time while preserving a high identification rate. Experimental results show that the proposed algorithm can save almost 50% searching time compared with traditional methods and illustrate its effectiveness. <s> BIB011 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> In this paper, we propose a method to apply the popular cascade classifier into face recognition to improve the computational efficiency while keeping high recognition rate. In large scale face recognition systems, because the probability of feature templates coming from different subjects is very high, most of the matching pairs will be rejected by the early stages of the cascade. Therefore, the cascade can improve the matching speed significantly. On the other hand, using the nested structure of the cascade, we could drop some stages at the end of feature to reduce the memory and bandwidth usage in some resources intensive system while not sacrificing the performance too much. The cascade is learned by two steps. Firstly, some kind of prepared features are grouped into several nested stages. And then, the threshold of each stage is learned to achieve user defined verification rate (VR). In the paper, we take a landmark based Gabor+LDA face recognition system as baseline to illustrate the process and advantages of the proposed method. However, the use of this method is very generic and not limited in face recognition, which can be easily generalized to other biometrics as a post-processing module. Experiments on the FERET database show the good performance of our baseline and an experiment on a self-collected large scale database illustrates that the cascade can improve the matching speed significantly. <s> BIB012 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> Personal recognition using palm–vein patterns has emerged as a promising alternative for human recognition because of its uniqueness, stability, live body identification, flexibility, and difficulty to cheat. With the expanding application of palm–vein pattern recognition, the corresponding growth of the database has resulted in a long response time. To shorten the response time of identification, this paper proposes a simple and useful classification for palm–vein identification based on principal direction features. In the registration process, the Gaussian-Radon transform is adopted to extract the orientation matrix and then compute the principal direction of a palm–vein image based on the orientation matrix. The database can be classified into six bins based on the value of the principal direction. In the identification process, the principal direction of the test sample is first extracted to ascertain the corresponding bin. One-by-one matching with the training samples is then performed in the bin. To improve recognition efficiency while maintaining better recognition accuracy, two neighborhood bins of the corresponding bin are continuously searched to identify the input palm–vein image. Evaluation experiments are conducted on three different databases, namely, PolyU, CASIA, and the database of this study. Experimental results show that the searching range of one test sample in PolyU, CASIA and our database by the proposed method for palm–vein identification can be reduced to 14.29%, 14.50%, and 14.28%, with retrieval accuracy of 96.67%, 96.00%, and 97.71%, respectively. With 10,000 training samples in the database, the execution time of the identification process by the traditional method is 18.56 s, while that by the proposed approach is 3.16 s. The experimental results confirm that the proposed approach is more efficient than the traditional method, especially for a large database. <s> BIB013 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> This paper is concerned in analyzing iris texture in order to determine “soft biometric”, attributes of a person, rather than identity. In particular, this paper is concerned with predicting the gender of a person based on analysis of features of the iris texture. Previous researchers have explored various approaches for predicting the gender of a person based on iris texture. We explore using different implementations of Local Binary Patterns from the iris image using the masked information. Uniform LBP with concatenated histograms significantly improves accuracy of gender prediction relative to using the whole iris image. Using a subject-disjoint test set, we are able to achieve over 91 % correct gender prediction using the texture of the iris. To our knowledge, this is the highest accuracy yet achieved for predicting gender from iris texture. <s> BIB014 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> Finger vein indexing refers to the process of creating clusters of finger vein samples based on the extracted features from the image. In large scale finger vein identification, the input probe image needs to be compared with a large set of gallery images to match the identity. Clusters can be used to confine the process of identity match of the images present in the gallery to the probe sample of the same cluster. In this work, we explored a new finger vein indexing and retrieval scheme with K-means clustering and pre-selection of features & comparison(PSFC). For a input probe sample, the centroid with the smallest distance will be chosen and compare with them for identification with K-means and P% of features (First, Last and Random) are compared with gallery samples features to choose for identification with PSFC. Extensive set off experiments are carried on a large scale data set of 2850 unique instances created using publicly available finger vein databases. Single cluster search with K-means clustering demonstrated the performance with pre-selection error of 9.38% (hit rate of 90.62%), Multi-cluster search with K-means clustering has achieved best performance with pre-selection error of 2.53% (hit rate of 97.47%) and PSFC has demonstrated the efficiency with pre-selection error of 9.58/9.85/8.05% (hit rate of 90.42/90.15/91.95%)for first/last/random features. <s> BIB015 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> Soft biometric modalities have shown their utility in different applications including reducing the search space significantly. This leads to improved recognition performance, reduced computation time, and faster processing of test samples. Some common soft biometric modalities are ethnicity, gender, age, hair color, iris color, presence of facial hair or moles, and markers. This research focuses on performing ethnicity and gender classification on iris images. We present a novel supervised autoencoder based approach, Deep Class-Encoder, which uses class labels to learn discriminative representation for the given sample by mapping the learned feature vector to its label. The proposed model is evaluated on two datasets each for ethnicity and gender classification. The results obtained using the proposed Deep Class-Encoder demonstrate its effectiveness in comparison to existing approaches and state-of-the-art methods. <s> BIB016 </s> Computational workload in biometric identification systems: an overview <s> Sub-sampling: <s> The increasingly large scale of deployed biometric systems necessitates approaches for computational workload reduction in order to perform identification queries efficiently. Simple database binning based on classification of features in biometric samples is amongst the most frequently used and researched methods for achieving said goal. However, multi-instance database binning appears to be a neglected topic in the scientific literature: best to the authors’ knowledge, for fingerprints there exists only one, entirely theoretical, study on this subject. In this paper, we propose a retrieval algorithm based on multi-instance binning of fingerprint databases, along with usage of statistical information on fingerprint classes and their correlations. The aforementioned statistics are obtained from NIST SD9 database and data obtained from the German Federal Criminal Police Office. Subsequently, the experimental evaluation of the proposed algorithm is performed on the NIST SD9 database. The proposed system is evaluated using a classifier based on the PCASYS tool and neuronal networks. The results show a significant workload reduction from a baseline exhaustive search scenario – down to 12.7% for this particular classifier and 5.8% for a theoretical perfect (completely accurate) classifier. The proposed method could be seamlessly integrated into operational systems, as it relies on well-established features and compatibility with the current acquisition methods. <s> BIB017
The key idea behind sub-sampling is to utilise partial information from the original feature vectors once or in an incremental manner to facilitate search space reduction via accurate early rejection of unlikely candidates. In other words, parts of the original feature vector itself act as an index in this case. This can be done trivially by deterministically or randomly selecting the partial information or, in more advanced approaches, by reorganising the feature vectors based on reliability and discriminative power (see e.g.  ), as well as utilising other heuristics. In the literature, numerous conceptually similar approaches have been presented e.g. in BIB010 BIB011 BIB012 BIB007   BIB015 for various biometric characteristics, including fingerprints, face, iris, and fingervein. In all the aforementioned publications, the computational workload is shown to be substantially reduced without causing degradation of the biometric performance. In BIB005 a more sophisticated approach, which relies on creating an auxiliary search guiding structure and an early search termination strategy, was presented with impressive results, albeit on proprietary data. Based on the global pattern formed by the ridge lines, fingerprints can be classified into a number of classes/types initially proposed by Galton [76] and Henry  (currently typically 4 or 5, i.e. whorls, right and left loops, and (tented) arches, sometimes extended with additional sub-types). Over time, numerous approaches to automated fingerprint type classification have been proposed (see e.g.   for a comprehensive survey). The classification accuracy on data of reasonable quality is near-optimal; however, it tends to vary somewhat across the different fingerprint types. Binning based on fingerprint classes has been evaluated for single fingerprints by e.g. BIB001 BIB008 and for multi-instance data in BIB002 BIB017 . Attributes extracted from iris data can also be used in this manner. Conceptually similar systems are presented in BIB003 ,  , and BIB013 , where binning based on biometric characteristic-specific geometric/texture features is proposed for irs, palmprint, and palmvein data, respectively. In BIB004 BIB014 BIB016 , it has been demonstrated, that ethnicity and gender information can be extracted from iris images. When reliably extracted, such features could be used for simple database binning. Binning based on iris colour has been performed e.g. in BIB006  . Although the vast majority of the human population has brown eyes, for certain population groups, the eye colour can be used as a somewhat distinguishing soft biometric trait. Currently, all practical iris recognition systems operate within the near-infrared (NIR) light spectrum. In recent years, significant advances in the visible-wavelength (VW) iris recognition have been made, hence potentially making it an emerging technology. See e.g. BIB009 for an investigation of the reliability of the iris colour as a soft biometric trait. Facial region is a rich source of potential soft biometric attributes. In addition to simple approaches based on sex, age, or ethnicity classification, binning based on marks, scars, and tattoos has been proposed  . While the aforementioned attributes are not discriminative enough to be directly used in biometric identification, they allow for a relatively straightforward binning of biometric databases according to a predefined number of classes. In other words, the potential search space for a given biometric probe can be narrowed down to one (or a few) bin(s), thereby reducing the penetration rate, and hence the computational workload.