Minutia Cylinder-Code

Fingerprint recognition is an intriguing pattern recognition problem studied by more than forty years. Although very effective solutions are nowadays available, fingerprint recognition cannot be considered a fully solved problem, and the design of accurate, interoperable and computationally light algorithms is still an open issue.Most fingerprint matching algorithms are based on minutiae (i.e., ridge ending and bifurcations). Unfortunately, most of the global minutiae matching algorithms are computationally demanding, and lack of robustness with respect to non-linear fingerprint distortion. In the last decade these weaknesses were addressed by introducing local minutiae matching techniques. Local minutiae structures are characterized by attributes that are invariant with respect to global transformations (e.g., translation, rotation, etc.) and therefore are suitable for matching without any a priori global alignment. Matching fingerprints based only on local minutiae arrangements relaxes global spatial relationships, which are highly distinctive, and therefore reduces the amount of information available for discriminating fingerprints. However, the benefits of both local and global matching can be preserved by implementing hybrid strategies that perform a local structure matching followed by a consolidation stage.

Motivations and Contributions
The main motivations that induced us to design a new local minutiae matching technique are:

• need of accurate and interoperable minutiae-only algorithms;
• portability on light architectures;
• suitability for fingerprint indexing and template protection techniques.

• it is a fixed-radius approach and therefore it tolerates missing and spurious minutiae better than nearest neighbor-based approaches;
• unlike traditional fixed-radius techniques, it relies on a fixed-length invariant coding for each minutia and this makes the computation of local structure similarities very simple;
• border problems are gracefully managed without extra burden in the coding and matching stages;
• local distortion and small feature extraction errors are tolerated thanks to the adoption of smoothed functions (i.e., error tolerant) in the coding stage;
• it effectively deals with noisy fingerprint regions where minutiae extraction algorithms tend to place numerous spurious minutiae (close to each other); this is made possible by the saturation effect produced by a limiting function;
• the bit-oriented coding makes cylinder matching extremely simple and fast, reducing it to a sequence of bit-wise operations (e.g., AND, XOR) that can be efficiently implemented even on very simple CPUs.

The New Local Structures Representation
MCC representation associates a local structure to each minutia. This structure encodes spatial and directional relationships between the minutia and its (fixed-radius) neighborhood and can be conveniently represented as a cylinder whose base and height are related to the spatial and directional information, respectively.

• invariant for translation and rotation;
• robust against skin distortion (which is small at a local level) and against small feature extraction errors;
• with a fixed-length.

The Local Similarity Measure
Thanks to the characteristics of the proposed local structures, the similarity between two cylinders(C_a and C_b)can be simply defined using a vector correlation measure (Eq. 1).

Bit-Based Implementation
The characteristics of the local structures and the similarity measure previously described make MCC well suited for a bit-based implementation. The cylinders can be transformed into binary vectors using a simple unit step function and a bit-based version of the similarity measure (Eq. 2) can be implemented very efficiently, even on light architectures (e.g., smart cards), where floating point operations are absent or very slow.

Global Score and Consolidation
In order to compare two minutiae templates a single value (global score) denoting their overall similarity has to be obtained from the local similarities. As a preliminary step n_R minutiae pairs are selected starting from those with highest local similarity then a relaxation approach has been applied to iteratively modify local similarities on the basis of the compatibility among minutia global spatial relationships. Finally, the global score is calculated as the average of the relaxed similarity values of the n_P pairs with the largest efficiency selected from the n_R pre-selected pairs.

Experimental Evaluation
In order to compare MCC with three well-known approaches, a systematic experimentation has been carried out, involving a total of 24 matching approaches over 20 minutiae datasets (compliant to ISO/IEC 19794-2 (2005)) extracted from FVC2006 databases, resulting in more than nine millions matching attempts.
The graph reports the average EER and the FMR1000 on FVC2006 DB2.

Optimization
The current optimized bit-based implementation is extremely fast: on a PC it is able to process about:

• 7 million comparisons per second using SSE instructions (CPU);
• 10 million comparisons per second using CUDA (a NVIDIA Tesla C2075 GPU);
• 70 million comparisons per second using CUDA (a NVIDIA Titan X Pascal GPU).
• 78 million comparisons per second using CUDA (a NVIDIA GeForce GTX 1080 Ti GPU).
• 117 million comparisons per second using CUDA (a NVIDIA Titan RTX GPU).
• 204 million comparisons per second using CUDA (a NVIDIA GeForce RTX 4090 GPU).

Conclusion
Experimental results demonstrate that MCC is more accurate than well-known minutiae-only local matching techniques. MCC is also very fast and suitable to be simply coded in hardware, due to the bit-wise nature of the matching technique; this allows its porting on inexpensive secure platforms such as a smart-card or a system-on-a-chip.

Software Development Kit (SDK)
A .Net DLL library that enables to develop fingerprint verification applications using the Minutia Cylinder-Code (MCC) algorithms is available here.

Bibliography

	M. Ferrara, Biometric Fingerprint Recognition Systems, Lambert Academic Publishing, 2010.
	R. Cappelli, M. Ferrara and D. Maltoni, "Large scale fingerprint recognition accelerated in hardware", in Martin Drahanský, Hand-Based Biometrics: Methods and technology, IET, 2018. Abstract
	R. Cappelli, M. Ferrara and D. Maltoni, "Minutiae-Based Fingerprint Matching", in Liu Chengjun, Mago Vijay Kumar, Cross Disciplinary Biometric Systems, Springer, 2012. Abstract
	R. Cappelli, M. Ferrara and D. Maltoni, "Large-scale fingerprint identification on GPU", Information Sciences, vol.306, pp.1-20, June 2015. Abstract
	M. Ferrara, D. Maltoni and R. Cappelli, "Noninvertible Minutia Cylinder-Code Representation", IEEE Transactions on Information Forensics and Security, vol.7, no.6, pp.1727-1737, December 2012. Abstract
	R. Cappelli and M. Ferrara, "A Fingerprint Retrieval System Based on Level-1 and Level-2 Features", Expert Systems With Applications, vol.39, no.12, pp.10465-10478, September 2012. Abstract
	R. Cappelli, M. Ferrara and D. Maio, "A Fast and Accurate Palmprint Recognition System based on Minutiae", IEEE Transactions on Systems, Man and Cybernetics - Part B, vol.42, no.3, pp.956-962, June 2012. Abstract
	R. Cappelli, M. Ferrara and D. Maltoni, "Robust Fingerprint Matching using Minutia Cylinder-Code Representation", IEEE Biometrics Council Newsletter, vol.3, pp.5, April 2012.
	R. Cappelli, M. Ferrara and D. Maltoni, "Fingerprint Indexing based on Minutia Cylinder-Code", IEEE Transactions on Pattern Analysis Machine Intelligence, vol.33, no.5, pp.1051-1057, May 2011. Abstract
	R. Cappelli, M. Ferrara and D. Maltoni, "Minutia Cylinder-Code: a new representation and matching technique for fingerprint recognition", IEEE Transactions on Pattern Analysis Machine Intelligence, vol.32, no.12, pp.2128-2141, December 2010. Abstract
	R. Cappelli, M. Ferrara, D. Maio and D. Maltoni, "Metodo di codifica delle minuzie di una impronta digitale e corrispondente metodo di riconoscimento di impronte digitali", Patent N. ITBO2009A000149, 2009.  Abstract
	M. Ferrara, D. Maltoni and R. Cappelli, "A Two-Factor Protection Scheme for MCC Fingerprint Templates", in proceedings International Conference of the Biometrics Special Interest Group (BIOSIG), Darmstadt, Germany, September 2014. Abstract
	R. Cappelli, M. Ferrara, D. Maltoni and M. Tistarelli, "MCC: a Baseline Algorithm for Fingerprint Verification in FVC-onGoing", in proceedings 11th International Conference on Control, Automation, Robotics and Vision (ICARCV), Singapore, December 2010. Abstract
	M. Ferrara, D. Maltoni and R. Cappelli, "A Simple and Effective Two-Factor Protection Scheme for MCC Fingerprint Templates", Technical Report, Biometric System Lab - University of Bologna, April 2014. Abstract