Computational workload in biometric identification systems: an overview <s> Clustering: <s> The problem of searching the elements of a set that are close to a given query element under some similarity criterion has a vast number of applications in many branches of computer science, from pattern recognition to textual and multimedia information retrieval. We are interested in the rather general case where the similarity criterion defines a metric space, instead of the more restricted case of a vector space. Many solutions have been proposed in different areas, in many cases without cross-knowledge. Because of this, the same ideas have been reconceived several times, and very different presentations have been given for the same approaches. We present some basic results that explain the intrinsic difficulty of the search problem. This includes a quantitative definition of the elusive concept of "intrinsic dimensionality." We also present a unified view of all the known proposals to organize metric spaces, so as to be able to understand them under a common framework. Most approaches turn out to be variations on a few different concepts. We organize those works in a taxonomy that allows us to devise new algorithms from combinations of concepts not noticed before because of the lack of communication between different communities. We present experiments validating our results and comparing the existing approaches. We finish with recommendations for practitioners and open questions for future development. <s> BIB001 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <s> Similarity search is a very important operation in multimedia databases and other database applications involving complex objects, and involves finding objects in a data set S similar to a query object q, based on some similarity measure. In this article, we focus on methods for similarity search that make the general assumption that similarity is represented with a distance metric d. Existing methods for handling similarity search in this setting typically fall into one of two classes. The first directly indexes the objects based on distances (distance-based indexing), while the second is based on mapping to a vector space (mapping-based approach). The main part of this article is dedicated to a survey of distance-based indexing methods, but we also briefly outline how search occurs in mapping-based methods. We also present a general framework for performing search based on distances, and present algorithms for common types of queries that operate on an arbitrary "search hierarchy." These algorithms can be applied on each of the methods presented, provided a suitable search hierarchy is defined. <s> BIB002 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <s> In this article, we evaluate the effectiveness of a pre-classification scheme for the fast retrieval of faces in a large image database. The studied approach is based on a partitioning of the face space through a clustering of face images. Mainly two issues are discussed. How to perform clustering with a non-trivial probabilistic measure of similarity between faces? How to assign face images to all clusters probabilistically to form a robust characterization vector? It is shown experimentally on the FERET face database that, with this simple approach, the cost of a search can be reduced by a factor 6 or 7 with no significant degradation of the performance. <s> BIB003 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <s> Given a query fingerprint, the goal of indexing is to identify and retrieve a set of candidate fingerprints from a large database in order to determine a possible match. This significantly improves the response time of fingerprint recognition systems operating in the identification mode. In this work, we extend the indexing framework based on minutiae triplets by utilizing ridge curve parameters in conjunction with minutiae information to enhance indexing performance. Further, we demonstrate that the proposed technique facilitates the indexing of fingerprint images acquired using different sensors. Experiments on the publicly available FVC database confirm the utility of the proposed approach in indexing fingerprints. <s> BIB004 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <s> Fingerprint identification has been a great challenge due to its complex search of database. This paper proposes an efficient fingerprint search algorithm based on database clustering, which narrows down the search space of fine matching. Fingerprint is non-uniformly partitioned by a circular tessellation to compute a multi-scale orientation field as the main search feature. The average ridge distance is employed as an auxiliary feature. A modified K-means clustering technique is proposed to partition the orientation feature space into clusters. Based on the database clustering, a hierarchical query processing is proposed to facilitate an efficient fingerprint search, which not only greatly speeds up the search process but also improves the retrieval accuracy. The experimental results show the effectiveness and superiority of the proposed fingerprint search algorithm. <s> BIB005 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <s> One of the main challenges in building an efficient and scalable automatic fingerprint identification system is to identify features which are highly discriminative and are reproducible across different prints of the same finger. Most existing fingerprint matching approaches rely on minutiae geometry. Relatively, little effort has gone into analyzing ridge flow patterns present in the fingerprint, partly due to difficulty in extracting robust discriminative features from the fingerprint images. In this paper, we analyze the usefulness of ridge curvature information for fingerprint matching and classification applications. Specifically, for an indexing framework, we explore whether the curvature information can be utilized along with the existing minutiae geometry-based features for further reducing the number of potential candidates for fingerprint identification. Experimental results indicate the robustness of the proposed curvature-based characterization and its usefulness in improving the efficiency of existing fingerprint-based identification systems. <s> BIB006 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <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> BIB007 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <s> We propose, in this paper, a new biometric identification approach which aims to improve recognition performances in identification systems. We aim to split the identity database into well separated partitions in order to simplify the identification task. In this paper we develop a face identification system and we use the reference algorithms of Eigenfaces and Fisherfaces in order to extract different features describing each identity. These features, which describe faces, are generally optimized to establish the required identity in a classical identification process. In this work, we develop a novel criterion to extract features used to partition the identity database. We develop database partitioning with clustering methods which split the gallery by bringing together identities which have similar features and separating dissimilar features in different bins. Pruning the most dissimilar bins from the query identity features allows us to improve the identification performances. We report results from the XM2VTS database. <s> BIB008 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <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> BIB009 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <s> The computational complexity of matching an input fingerprint against every entry in a large-scale fingerprint database can be prohibitive. In fingerprint indexing, a small set of candidate fingerprints is selected from the database and only images in this set are compared against the input probe fingerprint thereby avoiding an exhaustive matching process. In this paper, a new structure named “minutiae quadruplet” is proposed for indexing fingerprints and is used in combination with a clustering technique to filter a fingerprint database. The proposed indexing algorithm is evaluated on all datasets in the Fingerprint Verification Competition (FVC) 2000, 2002 and 2004 databases. The high hit rates achieved at low penetration rates suggest that the proposed algorithm is beneficial for indexing. Indeed, it was observed that for 50% of the fingerprints, in most of the datasets, the penetration rate was less than 5.5% at a 100% hit rate. The robust performance across different databases suggests that the indexing algorithm can be adapted for use in large-scale databases. <s> BIB010 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <s> Accuracy, security and efficiency are the drivers for exploiting multibiometric systems. A multi-modal or multibiometric system is relatively more secure than a single-biometric system as a result of the rich biometric content, lower error rates and resilience to impostor attacks. The availability and easy acquisition of the ten prints of an individual with fewer resources, give multi-finger biometric fusion scheme an advantage over other fusion schemes based on different biometric modalities. In this paper, multi-finger indexing is proposed using minutiae quadruplets in combination with a clustering scheme. Four, five and ten fingerprints from a subject are fused at the rank level using the highest rank rule. The minutiae quadruplet features are observed to be robust and the clustering scheme assists in quickly identifying a list of potential candidates in the gallery database. Results from the experiments show good performance of the fusion scheme with minutiae quadruplet features in fingerprint indexing. <s> BIB011 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <s> The number of images and videos available for search on the Internet is in the order of a trillion images, making current brute force search techniques prohibitively inefficient on such large scales. As society continues to increase our desire and ability to search these vast collections of data, improving upon traditional face recognition search techniques becomes an important problem to address. Because face recognition (and other biometric) algorithms are only commercially available as black box systems, any indexing scheme developed to perform efficient search must operate without access to the underlying feature vectors used to measure facial similarity. To address this restriction, we propose a structured search that separates the facial feature space into clusters derived from sets of prototype subjects we refer to as “synecdoches”. After an offline training step, our proposed method assigns each gallery image to a cluster in the face space based on its similarity to a set of synecdoche clusters. In turn, query images are compared to the target gallery images based on the closest synecdoche cluster in sequence. Our results show a minimal drop in accuracy when only considering half of the clusters, thus reducing the search space in half. Additional experiments demonstrate the viability of our proposed approach to improve search efficiency amidst the common restriction of a black box matcher. <s> BIB012 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <s> Iris recognition as a reliable method for personal identification has been well-studied with the objective to assign the class label of each iris image to a unique subject. In contrast, iris image classification aims to classify an iris image to an application specific category, e.g., iris liveness detection (classification of genuine and fake iris images), race classification (e.g., classification of iris images of Asian and non-Asian subjects), coarse-to-fine iris identification (classification of all iris images in the central database into multiple categories). This paper proposes a general framework for iris image classification based on texture analysis. A novel texture pattern representation method called Hierarchical Visual Codebook (HVC) is proposed to encode the texture primitives of iris images. The proposed HVC method is an integration of two existing Bag-of-Words models, namely Vocabulary Tree (VT), and Locality-constrained Linear Coding (LLC). The HVC adopts a coarse-to-fine visual coding strategy and takes advantages of both VT and LLC for accurate and sparse representation of iris texture. Extensive experimental results demonstrate that the proposed iris image classification method achieves state-of-the-art performance for iris liveness detection, race classification, and coarse-to-fine iris identification. A comprehensive fake iris image database simulating four types of iris spoof attacks is developed as the benchmark for research of iris liveness detection. <s> BIB013 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <s> Ear classification refers to the process by which an input ear image is assigned to one of several pre-defined classes based on a set of features extracted from the image. In the context of large-scale ear identification, where the input probe image has to be compared against a large set of gallery images in order to locate a matching identity, classification can be used to restrict the matching process to only those images in the gallery that belong to the same class as the probe. In this work, we utilize an unsupervised clustering scheme to partition ear images into multiple classes (i.e., clusters), with each class being denoted by a prototype or a centroid. A given ear image is assigned class labels (i.e., cluster indices) that correspond to the clusters whose centroids are closest to it. We compare the classification performance of three different texture descriptors, viz. Histograms of Oriented Gradients, uniform Local Binary Patterns and Local Phase Quantization. Extensive experiments using three different ear datasets suggest that the Local Phase Quantization texture descriptor scheme along with PCA for dimensionality reduction results in a 96.89% hit rate (i.e., 3.11% pre-selection error rate) with a penetration rate of 32.08%. Further, we demonstrate that the hit rate improves to 99.01% with a penetration rate of 47.10% when a multi-cluster search strategy is employed. <s> BIB014 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <s> ABSTRACT Nowadays, the need to techniques, approaches, and algorithms to search on data is increased due to improvements in computer science and increasing amount of information. This ever increasing information volume has led to time and computation complexity. Recently, different methods to solve such problems are proposed. Among the others, nearest neighbor search is one of the best techniques to this end which is focused by many researchers. Different techniques are used for nearest neighbor search. In addition to put an end to some complexities, variety of these techniques has made them suitable for different applications such as pattern recognition, searching in multimedia data, information retrieval, databases, data mining, and computational geometry to name but a few. In this paper, by opening a new view to this problem, a comprehensive evaluation on structures, techniques and different algorithms in this field is done and a new categorization of techniques in NNS is presented. This categorization is consists of seven groups: Weighted, Reductional, Additive, Reverse, Continuous, Principal Axis and Other techniques which are studied, evaluated and compared in this paper. Complexity of used structures, techniques and their algorithms are discussed, as well. <s> BIB015 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <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> BIB016 </s> Computational workload in biometric identification systems: an overview <s> Clustering: <s> Finger vein recognition has emerged as the robust biometric modality because of their unique vein pattern that can be captured using near infrared spectrum. The large scale finger vein based biometric solutions demand the need of searching the probe finger vein sample against the large collection of gallery samples. In order to improve the reliability in searching for the suitable identity in the large-scale finger vein database, it is essential to introduce the finger vein indexing and retrieval scheme. In this work, we present a novel finger vein indexing and retrieval scheme based on unsupervised clustering. To this extent we investigated three different clustering schemes namely K-means, K-medoids and Self Organizing Maps (SOM) neural networks. In addition, we also present a new feature extraction scheme to extract both compact and discriminant features from the finger vein images that are more suitable to build the indexing space. Extensive experiments are carried out on a large-scale heterogeneous finger vein database comprised of 2850 unique identities constructed using seven different publicly available finger vein databases. The obtained results demonstrated the efficacy of the proposed scheme with a pre-selection rate of 7.58% (hit rate of 92.42%) with a penetration rate of 42.48%. Further, the multi-cluster search demonstrated the performance with pre-selection error rate of 0.98% (hit rate of 99.02%) with a penetration rate of 52.88%. <s> BIB017
Cluster analysis or clustering refers to the unsupervised or semi-supervised classification of patterns (i.e. feature vectors, data items, or observations) into groups (referred to as clusters), wherein the items are, in some sense, similar to each other. With applications across many different disciplines, k-means clustering is currently one of the most popular and effective algorithms used in data mining  . Likewise, in the surveyed literature, k-means clustering (and its various extensions/derivatives) is by far the most popular method, used in e.g. BIB016 BIB004 BIB005 BIB006 BIB010 BIB011 BIB008 BIB012 BIB007 BIB013  BIB017  BIB014 . Other methods include e.g. multimap clustering  , expectation maximisation clustering BIB003 , and principal direction divisive partitioning BIB009 . Comparing the various clustering methods is out of scope for this article. For more details regarding this field of research, the reader is referred to surveys, e.g.   . Generally, the approaches referenced in this subsection extract certain biometric characteristic-specific features (e.g. orientation field or Delaunay triangles for fingerprint, or general-purpose texture descriptors for iris) to facilitate the clustering or apply it directly with the feature vectors (e.g. minutiae points) themselves. As a result, the search space is separated into distinct bins, whereby during biometric identification, candidates only from the most likely one(s) are retrieved. Hence, the penetration rate (and thereby the computational workload) is significantly reduced. Figure 5 shows a conceptual overview of hierarchical retrieval approaches, while table 4 summarises the surveyed methods. A multitude of methods, algorithms, and data-structures (whose detailed descriptions are out of scope for this article) has been used in the surveyed approaches. For a general introduction to on approximate searching, relevant concepts, and most commonly used datastructures, the reader is referred to existing surveys, e.g. BIB001 BIB002 BIB015 for theoretical, practical, and easily digestible perspectives, respectively.