variable and depends on the local minutiae density; this can
lead to a more complex local matching, but, in principle, is
more tolerant against missing and spurious minutiae. Two
drawbacks of [7] are: 1) the absolute encoding of radial angles
(whose corresponding relative encoding is denoted as d
R
in
Fig. 7) that requires a sophisticated local matching and 2) the
missing directional difference between the central minutia
and the neighboring ones (denoted as d
in Fig. 7).
Furthermore, the approach in [7], like most fixed-radius
ones, can lead to border errors: In particular, minutiae close to
the local-region border in one of the two fingerprints can be
mismatched because local distortion or location inaccuracy
may cause the same minutiae to move out of the local region
in the other fingerprint. The technique proposed by Feng in
[12] does not suffer from the above drawbacks and can be
considered a state-of-the-art fixed-radius local matching
algorithm. In particular, the border problem is dealt with by
considering minutiae not close to the border as matchable and
minutiae near the border as should-be-matchable.
This paper introduces a novel minutiae-only local
representation aimed at combining the advantages of both
neighbor-based and fixed-radius structures, without suffer-
ing from their respective drawbacks.
The rest of this paper is organized as follows: Section 2
introduces the main motivations of this work and sum-
marizes the advantages of the new technique. Section 3
defines the minutiae local structures and discusses how to
measure the similarity between them. Section 4 proposes
four simple approaches to consolidate local similarities into
a global score. In Section 5, a large number of experiments
are reported to compare the new approach with three
“minutiae-only” implementations of the well-known ap-
proaches described in [6], [7], [12]. Finally, Section 6 draws
some concluding remarks.
2MOTIVATIONS AND CONTRIBUTIONS
The main motivations that induced us to design a new local
minutiae matching technique are:
. Need for accurate and interoperable minutiae-only algo-
rithms. Most of the fingerprint matching algorithms
rece ntly proposed exploit several extra features
besides minutiae; in [34], some statistics about the
features used by FVC2004 participants are reported.
Researchers have shown that combining features (at
least partially independent) is a very effective way to
improve accuracy. On the other hand, unlike
minutiae features, there is still no convergence on
standards that precisely define and encode these
extra features (one of the first attempts is CDEFFS
(2008) [35], but it is still at an early stage). The world-
wide large-scale deployment of fingerprint systems
demands a new generation of accurate and highly
interoperable algorithms and, for this reason, we
believe that minutiae-only matching algorithms
compliant to ISO/IEC 19794-2 (2005) [36] (or the
very similar ANSI/INCITS 378 (2004) [37]) will play
a central role in coming years. Furthermore, minu-
tiae-only templates also allow us to compress into a
few hundred bytes the salient fingerprint informa-
tion, thus enabling their storage on inexpensive
smart cards.
. Portability on light architectures. One effective way to
secure biometric applications against external attacks
is to confine the computation inside a closed system,
that is, a secure hardware platform such as a smart
card or a system-on-a-chip. Unfortunately, the
computational power of these low-cost secure plat-
forms is a hundred or thousand times lower than that
of a modern PC [1] and resource demanding
algorithms cannot be executed on board. Algorithms
designers then concentrated on the development of
simplified optimized versions, often based on local
minutiae matching techniques and precomputed
information. However, recent MINEX II results [38]
have shown that the best existing match-on-card
algorithms cannot compete with the corresponding
PC implementations and further research efforts are
necessary. Analogous conclusions were drawn in [34]
concerning the performance drop of the light cate-
gory with respect to the open category in FVC2004.
. Suitability for template protection techniques. Template
protection is currently receiving much attention
because of the great benefits it can provide (e.g.,
nonreversibility, diversity, and revocability) [39], [1].
Unfortunately, designing effective template protec-
tion techniques (e.g., fuzzy vault [40], [41], [42], [43],
[44]) without incurring a relevant accuracy drop is
very challenging and seems to require alignment
free, fixed-length, and noise-tolerant feature coding.
As of now, no fully satisfactory solution has been
proposed.
The local minutiae representation introduced in this paper is
based on 3D data structures (called cylinders), built from
invariant distances and angles in a neighborhood of each
minutia. Cylinders can be created starting from a subset of
mandatory features in standards like ISO/IEC 19794-2 (2005).
In particular, we use only the position and direction of the
minutiae, but not the minutiae type and the minutiae quality:
In fact, minutiae type is not a robust feature and the definition
of minutiae quality is not semantically clear in the standards
(and could lead to interoperability problems). Thanks to the
cylinder invariance, fixed-length, and bit-oriented coding,
some simple but effective metrics can be defined to compute
cylinder similarity. Four global-scoring techniques are then
proposed to combine local similarities into a unique global
score denoting the overall similarity between two finger-
prints. The main advantages of the new method, called
Minutia Cylinder-Code (MCC), are:
. MCC is a fixed-radius approach and therefore it
tolerates missing and spurious minutiae better than
nearest neighbor-based approaches.
. Unlike traditional fixed-radius techniques, MCC
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.
. MCC effectively deals with noisy fingerprint regions
where minutiae extraction algorithms tend to place
CAPPELLI ET AL.: MINUTIA CYLINDER-CODE: A NEW REPRESENTATION AND MATCHING TECHNIQUE FOR FINGERPRINT RECOGNITION 2129
