Computational workload in biometric identification systems: an overview <s> Hashing: <s> A general method for model-based object recognition in occluded scenes is presented. It is based on geometric hashing. The method stands out for its efficiency. We describe the general framework of the method and illustrate its applications for various recogni- tion problems both in 3-D and 2-D. Special attention is given to the recognition of 3-D objects in occluded scenes from 2-D gray scale images. New experimental results are included for this important case. <s> BIB001 </s> Computational workload in biometric identification systems: an overview <s> Hashing: <s> The nearestor near-neighbor query problems arise in a large variety of database applications, usually in the context of similarity searching. Of late, there has been increasing interest in building search/index structures for performing similarity search over high-dimensional data, e.g., image databases, document collections, time-series databases, and genome databases. Unfortunately, all known techniques for solving this problem fall prey to the \curse of dimensionality." That is, the data structures scale poorly with data dimensionality; in fact, if the number of dimensions exceeds 10 to 20, searching in k-d trees and related structures involves the inspection of a large fraction of the database, thereby doing no better than brute-force linear search. It has been suggested that since the selection of features and the choice of a distance metric in typical applications is rather heuristic, determining an approximate nearest neighbor should su ce for most practical purposes. In this paper, we examine a novel scheme for approximate similarity search based on hashing. The basic idea is to hash the points Supported by NAVY N00014-96-1-1221 grant and NSF Grant IIS-9811904. Supported by Stanford Graduate Fellowship and NSF NYI Award CCR-9357849. Supported by ARO MURI Grant DAAH04-96-1-0007, NSF Grant IIS-9811904, and NSF Young Investigator Award CCR9357849, with matching funds from IBM, Mitsubishi, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment. Proceedings of the 25th VLDB Conference, Edinburgh, Scotland, 1999. from the database so as to ensure that the probability of collision is much higher for objects that are close to each other than for those that are far apart. We provide experimental evidence that our method gives signi cant improvement in running time over other methods for searching in highdimensional spaces based on hierarchical tree decomposition. Experimental results also indicate that our scheme scales well even for a relatively large number of dimensions (more than 50). <s> BIB002 </s> Computational workload in biometric identification systems: an overview <s> Hashing: <s> This paper proposes an efficient indexing scheme for searching large iris biometric database that achieves invariance to similarity transformations, illumination and occlusion. The proposed scheme considers local descriptors as well as relative spatial configuration for claiming identity. To overcome the effect of non-uniform illumination and partial occlusion due to eyelids, local features are extracted from noise independent annular iris image using scale invariant feature transform (SIFT). The detected keypoints are used to index iris database by applying geometric hashing scheme that is robust to similarity transformations as well as occlusion. During iris retrieval, geometric hashed location from query iris image is obtained to access the appropriate bin of hash table and for every entry found there, a vote is casted. The iris images that receive more than certain number of votes are considered as possible candidates. In order to find the potential matches, the keypoint descriptor of the list of possible candidates is matched with the query iris. Since only small portion of database is scanned to find a match it reduces the query retrieval time and improves accuracy. This approach is tested on UBIRIS, BATH, CASIA and IITK iris databases and shows a substantial improvement over exhaustive search technique in terms of time and accuracy. <s> BIB003 </s> Computational workload in biometric identification systems: an overview <s> Hashing: <s> This paper proposes an efficient indexing scheme for palmprint-based identification system. The proposed system uses geometric hashing of SURF key-points to index the palmprint into hash table and makes score level fusion of voting strategy based on geometric hashing and SURF score to identify the live palmprint. All ordered pairs of SURF key-points of the palmprint are scaled and mapped to a predefined coordinate system and all other points are similarity transformed. The new location after transformation serves as the index of the hash table. During identification, all ordered pairs of key-points of live palmprint are scaled and mapped to the coordinate system while remaining points are similarity transformed. A vote is casted to all images in the corresponding bins. Images having votes more than certain threshold are considered as candidate images of the live palmprint. SURF features of the live palmprint and the candidate images are compared for matching. Matching scores which are based on SURF key-points and vote of the corresponding candidate image are fused using weighted sum rule. The candidate image with the highest fused score is considered as the best match. The system is tested on IITK, CASIA and PolyU datasets. It has been observed that penetration rate of the proposed system is less than 30% for 0% bin miss rate (BMR) and has the identification accuracy of more than 97% for all three datasets. Further, the system is evaluated for robustness on downscaled and rotated. It has been found that the identification accuracy of the system for top best match is more than 90% for images downscaled up to 49% and accuracy is more than 85% when images are rotated at any angle. <s> BIB004 </s> Computational workload in biometric identification systems: an overview <s> Hashing: <s> Abstract This paper presents an efficient scheme to index the database of facial images. It has made use of the modified geometric hashing technique. It uses minimum amount of search space and memory to provide top best matches with high accuracy against a query image. Control points are extracted using Speeded-Up Robust Feature points (SURF) operator. A pre-processing technique consisting of mean centring, principal components, rotation and normalization has been proposed to make these control points invariant to translation, rotation and scaling. The modified geometric hashing is used to hash these control points to index of the hash table. The indexing scheme has been tested on FERET face database which has achieved 100% hit rate for top 4 best matches. <s> BIB005 </s> Computational workload in biometric identification systems: an overview <s> Hashing: <s> Similarity search (nearest neighbor search) is a problem of pursuing the data items whose distances to a query item are the smallest from a large database. Various methods have been developed to address this problem, and recently a lot of efforts have been devoted to approximate search. In this paper, we present a survey on one of the main solutions, hashing, which has been widely studied since the pioneering work locality sensitive hashing. We divide the hashing algorithms two main categories: locality sensitive hashing, which designs hash functions without exploring the data distribution and learning to hash, which learns hash functions according the data distribution, and review them from various aspects, including hash function design and distance measure and search scheme in the hash coding space. <s> BIB006
Hashing makes it possible to map the highlydimensional biometric feature vectors into compact hashtables or similar data-structures, which facilitate efficient retrieval. Since biometric data is inherently fuzzy (recall section 1), many traditional hashing approaches are not suitable. Nevertheless, there exist methods, which can deal with fuzzy data. One of such method is BIB002 , which refers to a family of functions, which can be used to map data points into buckets in such a way, that it is highly probable for data points which are close to each to be located in the same buckets; conversely, data points which are distant from each other, are likely located in different buckets. Several authors utilised LSH and variations/extensions thereof to facilitate efficient retrieval of (in most cases) fingerprint data [126-129, 131, 135] . Geometric hashing BIB001 , which was originally developed for object recognition (matching similar geometric shapes irrespective of translation, rotation, and scaling), has also been applied in the context of biometrics by coupling it with general-purpose keypoint detectors BIB005 BIB003  BIB004 . Deeper descriptions of the various hashing algorithms and their extensions are out of scope for this article -the reader is referred to e.g. BIB006  . Generally, by significantly reducing the dimensionality of the data and facilitating retrieval of a subset of candidate identities, general purpose fuzzy hashing methods adapted to the biometric data can be used to greatly reduce the computational workload. Aside from potential biometric performance degradation due to hashtable/bucket misses, the storage requirements of the system (especially in the case of geometric hashing) are typically increased.