Computational workload in biometric identification systems: an overview <s> Open Issues <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> BIB001 </s> Computational workload in biometric identification systems: an overview <s> Open Issues <s> Identity management using biometrics is a reality. E-passports incorporate biometric technology, and biometric technology has also become more prevalent on personal computers. Applications that will recognise nomadic users through biometrics are also emerging, as mobile devices are equipped with more sensors. <s> BIB002 </s> Computational workload in biometric identification systems: an overview <s> Open Issues <s> Biometric recognition has undoubtedly made great strides over the past 50 years. To ensure that current academic research in biometrics has a positive impact on future technological developments, this paper documents some guidelines encouraging researchers to focus on high-impact problems, develop solutions that are practically viable, report results using sound experimental and evaluation protocols, and justify claims based on verifiable facts. The intent is to ensure that methods and results published in the literature have been properly evaluated and are practically feasible for automated or semi-automated human recognition. It is believed that following these guidelines will avoid inflated claims and support published research on a legitimate foundation that can be embraced by practitioners and peers in biometrics and related scientific disciplines (e.g., forensic science. <s> BIB003 </s> Computational workload in biometric identification systems: an overview <s> Open Issues <s> For digital imagery, face detection and identification are functions of great importance in wide-ranging applications, including full facial recognition systems. The development and evaluation of unique and existing face detection and face identification applications require a significant amount of data. Increased availability of such data volumes could benefit the formulation and advancement of many biometric algorithms. Here, the utility of using synthetically generated face data to evaluate facial biometry methodologies to a precision that would be unrealistic for a parametrically uncontrolled dataset, is demonstrated. Particular attention is given to similarity metrics, symmetry within and between recognition algorithms, discriminatory power and optimality of pan and/or tilt in reference images or libraries, susceptibilities to variations, identification confidence, meaningful identification mislabelings, sensitivity, specificity, and threshold values. The face identification results, in particular, could be generalized to address shortcomings in various applications and help to inform the design of future strategies. <s> BIB004 </s> Computational workload in biometric identification systems: an overview <s> Open Issues <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> BIB005
Several open issues/challenges remain in research related to computational workload reduction in biometric identification systems: Standardisation As described in subsection 2.2, as of yet there exists no standardised way of reporting results for biometric computational workload and its reduction. This leads to a multitude of methodologies and metrics in the scientific literature, thereby making direct benchmarks and comparative assessment of the proposed methods extremely cumbersome to carry out. Moreover, in many publications, even the baseline results (i.e. exhaustive search with a state-of-the-art algorithm) are not reported, which further exacerbates this issue. In BIB005 , experimental prerequisites and metrics for such evaluations are proposed; as of this writing, there is an ongoing effort to include metrics to measure computational workload and its reduction in the current revision of the ISO/IEC IS 19795-1. This effort notwithstanding, the standardisation in this research area remains an open debate subject within the standardisation committee and in general. Scalability Due to limited availability of large-scale biometric data for academic research, many, if not most, of the surveyed approaches were tested on relatively small databases (mostly up to hundreds or thousands of subjects; tens of thousands of samples). Hence, the scalability of many of the proposed methods remains questionable or unproven in practice (cf. table 1 w.r.t. the sizes of large real-world deployments of biometric systems). Some authors are fortunate enough to receive access to large-scale, sequestered databases (e.g. law enforcement) in order to evaluate and validate their approaches (e.g.  BIB001 ), but such cases are rare in the surveyed literature, likely as a consequence of the significant practical and legal hurdles associated with accessing the sensitive biometric/personal data. Biometric performance trade-off It appears that many approaches are capable of delivering significant (e.g. one or two orders of magnitude) decrease in computational workload requirements. However, further reductions prove elusive for most methods due to rapidly degenerating biometric performance. Some of the surveyed methods incorporate in their designs information fusion (from multiple biometric characteristics or multiple instances of the same characteristics) to mitigate this issue to a certain degree. Dissonance between academia and industry There seem to exist, to a certain degree, discrepancies between methods and goals of the research conducted within the academia, and the actual practical use cases in the industry. Several examples (also partially related to the aforementioned issues of standardisation and scalability) relevant to the topic of this article are: Evaluation protocol Whereas a substantial number of the surveyed publications perform their experiments using the closedset identification, the real-world systems are essentially universally required to perform the much more challenging open-set identification. Decision thresholds Almost all of the surveyed publications do not report decision thresholds at which the given biometric performance was achieved. Furthermore, evaluations on different datasets with fixed decision thresholds are rarely performed. This is in stark contrast with the industry/law enforcement practices, where decision thresholds and fixed operational points are used extensively in the operational systems. Results reporting The surveyed publications often report results using metrics, which are of limited value in the industry practice. For instance, operational systems would not typically operate at EER (even if it ever was an operational point at all), but rather at fixed false-positive identification-error rates acceptable within their respective system policies. Many publications use rank-based reporting and CMC curves, which imply the less interesting (from the industry point of view) closed-set evaluation protocol, as mentioned above. Acceleration As evidenced by subsection 3.6, significant research efforts have been devoted to develop biometric algorithms suitable for FPGA or GPU computations. However, as mentioned in subsection 4.3, the existing deployments of large-scale biometric systems lean towards distributed architectures of commodity CPU hardware due to other practical considerations; additionally, software optimisations, which play an important role in the commercial systems, are only superficially treated in the scientific literature. Thus, aside from the technical challenges (and potential limits) of improving on the trade-offs between biometric performance and computational workload reduction, there are two key areas that should be considered by the large-scale biometric identification practitioners from academia and industry alike: Academia and industry cooperation Much tighter integration between the academic research and industry requirements is needed. The academics should seek out industry partners to validate their proposed systems and solutions outside of a lab setting; conversely, the industry should engage in outreach initiatives to academia in order to promote the actual prerequisites, requirements, and challenges of the commercial systems. More frequent and deeper joint (research or otherwise) projects and partnerships between academia and industry could potentially help to ameliorate the aforementioned dissonances. Jain et al. BIB003 recently published the short "Guidelines for Best Practices in Biometric Research". This document can serve as a good starting point outlining the absolute essentials for legitimate and practical reporting of results within biometrics research. Furthermore, the representatives from all the stakeholders should begin or continue to actively engage in the international standardisation efforts, for instance the ones by the ISO/IEC JTC 1/SC 37 (who are responsible for, among others, the biometric performance evaluation and harmonized biometric vocabulary standards   ) and/or of other national agencies, such as NIST in the USA and BSI in Germany. This way, meaningful consensus w.r.t. evaluation protocols, metrics, and benchmarks that reflect the real use cases can be attained. Practical evaluations Entities (e.g. governmental agencies, universities, companies) in possession of large amounts of biometric data should support large-scale evaluations, thus facilitating scalability assessment and fair benchmarks between the systems developed by the academic researchers and the commercial vendors. Such benchmarks make available an API against which algorithms can be coded, then submitted to a central server, and finally ran and evaluated there using the same experimental protocol and metrics. Such tests offer an additional advantage, in that the vast majority of the image data used for evaluation remains unseen by the algorithm authors, which in turn facilitates higher generalisably of the proposed algorithms. Lastly, synthetically generated data could be used to some extent in the context of biometric scalability testing (see e.g. BIB004 ). Interesting existing initiatives in this area are, for example: the BEAT platform BIB002 with the aim of developing a general standard framework biometric technologies' evaluation, along with several more constrained initiatives such as the indexing competition under Fingerprint Verification Competition (FVC-onGoing)  , the 1:N Evaluation under Face Recognition Vendor Test (FRVT) [208] , one-to-many evaluations under Iris Exchange (IREX) -for fingerprint, face, and iris characteristics, respectively.