1

Learning Fingerprint Reconstruction:
From Minutiae to Image
Kai Cao and Anil K. Jain, Fellow, IEEE

Abstract—The set of minutia points is considered to be the most distinctive feature for fingerprint representation and is widely used in fingerprint matching. It was believed that the minutiae set does not contain sufficient information to reconstruct the original fingerprint image from which minutiae were extracted. However, recent studies have shown that it is indeed possible to reconstruct fingerprint images from their minutiae representations. Reconstruction techniques demonstrate the need for securing fingerprint templates, improve the template interoperability and improve fingerprint synthesis. But, there is still a large gap between the matching performance obtained from original fingerprint images and their corresponding reconstructed fingerprint images. In this paper, the prior knowledge about fingerprint ridge structures is encoded in terms of orientation patch and continuous phase patch dictionaries to improve the fingerprint reconstruction. The orientation patch dictionary is used to reconstruct the orientation field from minutiae, while the continuous phase patch dictionary is used to reconstruct the ridge pattern. Experimental results on three public domain databases
(FVC2002 DB1 A, FVC2002 DB2 A and NIST SD4) demonstrate that the proposed reconstruction algorithm outperforms the stateof-the-art reconstruction algorithms in terms of both i) spurious and missing minutiae and ii) matching performance with respect to type-I attack (matching the reconstructed fingerprint against the same impression from which minutiae set was extracted) and type-II attack (matching the reconstructed fingerprint against a different impression of the same finger).
Index Terms—fingerprint reconstruction, orientation patch dictionary, continuous phase patch dictionary, minutiae set, AMFM model.

I. I NTRODUCTION
INGERPRINTS are ridge and valley patterns present on the surface of human fingertips [1]. The purported uniqueness of fingerprints is characterized by three levels of features [1] (see Fig. 1). Global features, such as pattern type, ridge orientation and frequency fields, and singular points, are called level-1 features. Level-2 features mainly refer to minutia points in a local region; ridge endings and ridge bifurcations are the two most prominent types of minutiae.
Level 3 features include all dimensional attributes at a veryfine scale, such as width, shape, curvature and edge contours of ridges, pores, incipient ridges, as well as other permanent details. Among these three types of features, the set of minutia points (called minutiae) is regarded as the most distinctive feature and is most commonly used in fingerprint matching

F

Kai Cao and Anil K. Jain are with the Dept. of Computer Science and
Engineering, Michigan State University, East Lansing, MI 48824, U.S.A. Kai
Cao is also affiliated with the School of Life Sciences and Technology, Xidian
University, Xi’an, Shaanxi 710126, China.
E-mail: {kaicao, jain}@cse.msu.edu

systems. An international standard ISO/IEC 19794-2 [2] has been proposed for minutiae template representation for the purpose of interoperability of matching algorithms. FVConGoing [3], a well-known web-based automated evaluation platform for fingerprint recognition algorithms, has set up a benchmark to evaluate fingerprint matching algorithms using this standard minutiae template format.
It was believed that it is not possible to reconstruct a fingerprint image given its extracted minutiae set. However, it has been demonstrated that it is indeed possible to reconstruct the fingerprint image from the minutiae; the reconstructed image can be matched to the original fingerprint image with a reasonable high accuracy [7], [8], [9]. There is still a room for improvement in the accuracies, particularly for type-II attack. The aim of fingerprint reconstruction from a given minutiae set is to make the reconstructed fingerprint resemble the original fingerprint. A successful reconstruction technique demonstrates the need for securing fingerprint templates. Such a technique would also be useful in improving the matching performance with ISO templates as well as addressing the issue of template interoperability [7]. It also could be used to improve synthetic fingerprint reconstruction and restore latent fingerprint images [8].
Existing reconstruction algorithms essentially consist of two main steps: i) orientation field reconstruction and ii) ridge pattern reconstruction. The orientation field, which determines the ridge flow, can be reconstructed from minutiae and/or singular points. In [4], the orientation field was reconstructed from the singular points (core and delta) using the zero-pole model [5]. However, the orientation field in fingerprints cannot simply be accounted for by singular points only. Cappelli et al. [7] proposed a variant of the zero-pole model with additional degrees of freedom to fit the model to the minutiae directions. However, the orientation field reconstructed based on zero-pole model cannot be guaranteed when the singular points are not available. In [6], a set of minutiae triplets was proposed to reconstruct orientation field in triangles without using singular points. The algorithm proposed by Feng and
Jain [8] predicts an orientation value for each block by using the nearest minutia in each of the eight sectors. The approaches in [10] and [11] reconstruct orientation field from minutiae to improve the matching performance. However, these orientation reconstruction approaches, based on given minutiae, do not utilize any prior knowledge of the fingerprint orientation pattern and may result in a non-fingerprint-like orientation field. The other step in fingerprint reconstruction is ridge pattern reconstruction based on the reconstructed orientation field. The ridge pattern reconstruction proposed in [4] only generates

2

Fig. 1: Illustration of fingerprint features at three different levels. (a) A gray-scale fingerprint image (NIST SD30, A002 01),
(b) level 1 features: orientation field and singular points (core shown as circle and delta shown as triangle), (c) level 2 features: ridge endings (red squares) and ridge bifurcations (blue circles) and (d) level 3 features: pores and dots.
TABLE I: A comparison of fingerprint reconstruction algorithms proposed in the literature
Algorithm

Orientation field reconstruction Hill [4]

Zero-pole model [5]

Ross et al. [6]

Minutiae triplets

Cappelli et al. [7]

Modified zero-pole model Feng and Jain [8]

Li and Kot [9]

Proposed algorithm a b c d e

Nearest minutiae in eight sectors

Nearest minutiae in eight sectors

Orientation dictionary patch

Ridge pattern reconstruction
Partial skeleton reconstruction
Streamlines and line integral convolution

Performance evaluation

Comments

N/A
Type-I attack: 23% rank-1 identification rate on NIST SD4

Gabor filtering

Type-I attack: 81.49% TARa at 0% of FARb on FVC2002 DB1 (average of eight matchers)

AM-FM model

Type-I attackc: TAR=94.12% at FAR=0.1% on
FVC2002 DB1 A and 99.70% rank-1 identification rate on NIST SD4; Type-II attackd :
TAR=45.89% at FAR=0.1% on FVC2002
DB1 A and 65.75% rank-1 identification rate on NIST SD4 by Verifinger SDK 4.2.

Only partial skeleton of a fingerprint is obtained
Only partial fingerprint is reconstructed Many spurious minutiae appear in the reconstructed fingerprint
Spurious minutiae and blocking effect appear in the reconstructed fingerprint.

AM-FM model

Type-II attack: TAR=86.48% at on FVC2002 DB1 A by Verifinger SDK 6.3.

Ridge flow and ridge frequency may change in the continuous phase compared to the original fingerprint.

Continuous phase patch dictionary

Type-I attack: TAR=100% at FAR=0.01% on both FVC2002 DB1 A and FVC2002 DB2 A and 100% rank-1 identification rate on
NIST SD4; Type-II attack: TAR=85.23% and
TAR=90.29% at FAR=0.01% on FVC2002
DB1 A and FVC2002 DB2 A, respectively,
80.55% rank-1 identification rate on NIST
SD4 by Verifinger SDK 6.3.

Requires learning orientation field and ridge pattern

FAR=0.01%e

Type-I attack refers to matching the reconstructed fingerprint against the same impression from which the minutiae set was extracted.
Type-II attack refers to matching the reconstructed fingerprint against a different impression of the same finger.
TAR means true accept rate.
FAR means false accept rate.
Only minutiae position and direction were used in the matching experiments. Texture information, such as ridge frequency and curvature around minutiae, were ignored.

a partial skeleton of the fingerprint, which is obtained by drawing a sequence of splines passing through the minutiae.
This method was further improved in [6] by using linear integral convolution to impart texture-like appearance and low-pass filtering to get wider ridges. However, it can only generate a partial fingerprint, and the resulting ridge pattern is quite different from that of the target fingerprint. The approach proposed by Cappelli et al. [7] is able to reconstruct a full fingerprint image from minutiae points. An image is first initialized by local minutiae prototypes, followed by iterative Gabor filtering with the estimated orientation field and predefined ridge frequency to generate ridge pattern.
However, this approach introduces many spurious minutiae around the intersections of regions generated from different

minutiae; these spurious minutiae cannot be controlled. Feng and Jain [8] utilized the amplitude and frequency modulated (AM-FM) model [13] to reconstruct fingerprints, where the phase, consisting of continuous phase and spiral phase
(corresponding to minutiae), completely determines the ridge structure and minutiae. Continuous phase reconstruction is therefore a critical step in the AM-FM model based fingerprint reconstruction. In [8], the continuous phase is obtained by a piecewise planar model. However, the piecewise planar model introduces many spurious minutiae and results in visible blocking effects during the continuous phase reconstruction. Instead of using piecewise planar model, Li and Kot [9] reconstructed continuous phase from a binary ridge pattern generated using
Gabor filtering with the reconstructed orientation field and

3

Fig. 2: A comparison of fingerprint images reconstructed using four different reconstruction algorithms. (a) and (b) are two impressions from the same finger, (c) minutiae points extracted from (a), and its reconstructed fingerprint images using: (d) algorithm by Feng and Jain [8], (e) algorithm by Li and Kot [9], (f) proposed algorithm with a fixed ridge frequency and
(g) proposed algorithm with adaptive ridge frequency around each minutiae. The matching scores, S(·, ·), between the two impressions (F1 and F2) and the reconstructed images (R1, R2, R3 and R4) using Verifinger SDK 6.3 [12] are shown around the two impressions.

predefined ridge frequency; the continuous phase was obtained by subtracting spiral phase from the phase of the binary ridge pattern. While this approach ensures that no spirals will appear in the continuous phase, the continuous phase after removing all spirals may be quite different from the desired one in terms of ridge flow and ridge frequency, as shown in Fig. 3. Table
I summarizes various fingerprint reconstruction algorithms proposed in the literature and their reported performance.
Although several fingerprint reconstruction algorithms have been proposed, the matching performance of the reconstructed fingerprints compared with the original fingerprint images is still not very satisfactory. That means the reconstructed fingerprint image is not very close to the original fingerprint image that the minutiae were extracted from. An important reason for this loss of matching performance is that no prior knowledge of fingerprint ridge structure was utilized in these reconstruction approaches to reproduce the fingerprint characteristics. In the literature, such prior knowledge has been represented in terms of using orientation patch dictionary [14] and ridge structure dictionary [15] for latent segmentation and enhancement. In this paper, our goal is to utilize a similar dictionary-based approach to improve the fingerprint reconstruction from a given minutiae set. Two dictionaries are constructed for fingerprint reconstruction: 1) orientation patch dictionary and 2) continuous phase patch dictionary.
The orientation patch dictionary is used to reconstruct the orientation field from a minutiae set, while the continuous phase patch dictionary is used to reconstruct the ridge pattern.

Instead of reconstructing continuous phase and spiral phase globally, we propose to reconstruct fingerprint patches using continuous phase patch dictionary and minutiae belonging to these patches; these patches are optimally selected to form a fingerprint image. The spurious minutiae, which are detected in the phase of the reconstructed fingerprint image but not included in the input minutiae template, are then removed using the global AF-FM model. The proposed reconstruction algorithm has been evaluated on three different public domain databases, namely, FVC2002 DB1 A, FVC2002 DB2 A and
NIST SD4, in terms of minutiae set accuracy with respect to the given minutiae set and matching performance of the reconstructed fingerprint. Experimental results demonstrate that the proposed algorithm performs better than two stateof-the-art reconstruction algorithms [8] and [9], as shown in
Fig. 2. The superior performance of the proposed algorithm over [8] and [9] can be attributed to:
1) Use of prior knowledge of orientation pattern, i.e., orientation patch dictionary, which provides better orientation field reconstruction, especially around singular points.
2) The sequential process which consists of (i) reconstructing locally based on continuous phase patch dictionary,
(ii) stitching these patches to form a fingerprint image and (iii) removing spurious minutiae. Instead of generating a continuous phase and then adding spiral phase to the continuous phase globally, this procedure is able to better preserve the ridge structure.

4

3) Use of local ridge frequency around minutiae.
The rest of the paper is organized as follows. The preliminaries of the AM-FM fingerprint model are introduced in section II. The details of the proposed algorithm are presented in section III. Experimental results are reported in section IV.
Finally, conclusions and future research directions are reported in section V.
II. AM-FM F INGERPRINT M ODEL
The AM-FM fingerprint model proposed by Larkin and
Fletcher [13] represents a fingerprint image I as a hologram,
i.e., consisting of 2D amplitude and frequency modulated fringe pattern:
I(x, y) = a(x, y) + b(x, y) cos(ψ(x, y)) + n(x, y),

(1)

where a(x, y), b(x, y) and n(x, y) are, respectively, the offset, amplitude and noise, which make the fingerprint realistic, and ψ(x, y) is the phase which completely determines the ridge structures and minutiae of the fingerprint. According to the
Helmholtz Decomposition Theorem [17], a phase ψ(x, y) can be uniquely decomposed into a continuous phase ψC (x, y) and a spiral phase ψS (x, y), i.e., ψ(x, y) = ψC (x, y) + ψS (x, y).
For a fingerprint image I(x, y), its phase ψ(x, y) can be obtained by demodulation [13], [17]. Before the demodulation, the offset (or DC) term a(x, y), which can be estimated as the mid-value in a local area, is removed from I(x, y). The offset removed image I ′ (x, y) is
I ′ (x, y) = I(x, y) − a(x, y) ≈ b(x, y) cos(ψ(x, y)).

(2)

With the application of demodulation operator R, which is defined as
R[I ′ (x, y)] ∼ F −1 {eiϕ(u,v) F {I ′ (x, y)}},
(3)
=
√
where eiϕ(u,v) = (u + iv)/ (u2 + v 2 ) is a spiral Fourier multiplier, F (·) and F −1 (·) are the Fourier transform and inverse Fourier transform, respectively, the cosine term in (2) can be converted to a sine term (in quadrature to the cosine),
−ie−iβ(x,y) R[I ′ (x, y)] = b(x, y) sin(ψ(x, y)),

(4)

where β(x, y) is the directional map (in the range (−π, π]) which is normal to local ridge orientation (in the range
(− π , π ]). There are several methods to convert orientation
2 2 field to directional map (e.g., [9], [8]). Based on Eqs. (2) and
(4), the phase is obtained by ψ(x, y) = tan−1 (−ie−iβ(x,y) R[I ′ (x, y)], I ′ (x, y)).

(5)

To get a smooth phase, directional filtering, such as Gabor filtering [16], is applied to enhance the gray-scale fingerprint image before demodulation. Figs. 3(b) and (d) show the enhanced fingerprint image and the phase of fingerprint image in Fig. 3(a). With the phase ψ(x, y), its ideal fingerprint representation is
I(x, y) = cos(ψ(x, y)).

(6)

The spirals in the phase image (i.e., minutiae in a fingerprint) can be detected by the clockwise phase difference
[9], [18]. Let ψ0 , ψ1 , ψ2 and ψ3 denote the phase values

at positions (x, y), (x + 1, y), (x + 1, y + 1) and (x, y + 1), respectively. The clockwise phase difference ε(x, y) at location
(x, y) is defined as ε(x, y) =

3
∑

dθ(ψ(i+1)

mod 4 , ψi ),

(7)

i=0

where mod is the modulo operator, and dθ(ψa , ψb ) is the phase difference between ψa and ψb

ψa − ψb + 2π, if ψa − ψb ≤ π,

dθ(ψa , ψb ) = ψa − ψb − 2π, if ψa − ψb > π, (8)

 ψa − ψb , otherwise. The value of ε(x, y) can be used as an indication of non-spiral
(0), negative spiral (−π) and positive spiral (π). Minutiae set with n minutiae points can be removed from cos(ψ(x, y)) by subtracting a spiral phase ψS (x, y), which consists of a set of n spirals: ψS (x, y) =

n
∑
i

pi tan−1 (

y − yi
),
x − xi

(9)

where (xi , yi ) denotes the coordinates of the ith spiral and pi ∈ {−1, 1} is its polarity determined by the sign of ε(xi , yi ).
After removing all the minutiae points or spirals from ψ(x, y), the continuous phase ψC (x, y), the integral of whose gradient around any simple close path is zero, is retained. Figs. 3(f) and (g) show the cosines of spiral phase and continuous phase, respectively. Note that after removing the spirals (minutiae), the ridge flow and ridge frequency of the continuous phase may be quite different from those of the gray-scale fingerprint image. III. P ROPOSED R ECONSTRUCTION A LGORITHM
The goal of fingerprint reconstruction is to reconstruct a gray-scale fingerprint image based on an input set of n minutiae M = {mi = (xi , yi , αi )}n , where (xi , yi ) and i=1 αi (−π < alphai < π) denote the location and direction of the ith minutia, respectively. In this paper, a dictionary-based fingerprint reconstruction method is proposed. Two kinds of dictionaries are learnt off-line as prior knowledge: 1) orientation patch dictionary and 2) continuous phase patch dictionary.
For an input fingerprint minutiae set, the orientation patch dictionary is used to reconstruct the orientation field from the minutiae set, while the continuous phase dictionary is used to reconstruct the ridge pattern. In addition, the spurious minutiae introduced in the reconstructed fingerprint are removed using the global AM-FM model. The flowchart of the proposed algorithm is illustrated in Fig. 4.
A. Dictionary Construction
1) Orientation Patch Dictionary: The orientation patch dictionary proposed by Feng et al. [14] for latent enhancement is directly utilized as prior knowledge of ridge flow for orientation field reconstruction. The orientation patch dictionary DO , consisting of a number of orientation patches, is constructed from a set of high quality fingerprints (50 rolled fingerprint images). An orientation patch consists of 10 × 10

5

Fig. 3: Phase analysis of a gray-scale fingerprint image. (a) A gray-scale fingerprint image (NIST SD4, S0005.bmp), (b) enhancement of (a) using Gabor filtering in [16], (c) unwrapped orientation field based on the approach proposed in [9], (d) phase image ψ, (e) cos(ψ), (f) cos(ψS ), where ψS is the spiral phase, and (g) cos(ψC ), where ψC is the continuous phase.
Note that after removing the spirals (minutiae), the ridge flow and ridge frequency may change.

Fig. 5: Some example elements from the orientation patch dictionary. Fig. 6: Orientation field of 24 orientation patch centers.

orientation elements with each orientation element referring to the dominant orientation in a block of size 16 × 16 pixels.
Fig. 5 shows some examples of orientation patches from DO .
2) Continuous Phase Patch Dictionary: The continuous phase patch dictionary, which includes a number of continuous phase patches (without spirals), is constructed through the following steps:
i) Fingerprint selection and processing: High quality fin-

Fig. 7: Same examples from the continuous phase patch dictionary. The continuous phase patches in a specific row are from the same orientation patch cluster center. Each patch is of size 48 × 48 pixels.

gerprints in NIST SD4 [19], whose NIST Fingerprint
Image Quality (NFIQ) [20] index1 is less than 3, are selected for dictionary construction. For each selected fingerprint, the orientation field and the quality map with a block size of 8 × 8 pixels are obtained by
1 NFIQ ranges from 1 (the highest quality) to 5 (the lowest quality fingerprint). 6

Orientation patch dictionary construction Orientation patch dictionary

Orientation field of rolled prints

Input minutiae

Reconstructed orientation field and minutiae

Postprocessed
Reconstructed fingerprint reconstructed fingerprint and spurious minutiae

Initial orientation field and minutiae

…
…

…
…

…

Enhanced rolled prints

…
…

Continuous phase patch dictionary construction Continuous phase patch dictionary

Fig. 4: Flowchart of the proposed reconstruction algorithm.

MINDTCT [21], and the frequency field is computed by the method proposed in [16]. Gabor filtering [16] is utilized to enhance the selected fingerprints. This is followed by the demodulation in Eq. (5) to get the ideal representation using Eq. (6). ii) Orientation patch clustering: A set of orientation patches of size 6 × 6 blocks (with each block being 8 × 8 pixels) is then selected by sliding a window over the orientation field with a step size of 1 block; if the average quality value of a patch is larger than a predefined threshold T
(T is set to 3.75), the patch is included in the training set.
Each orientation patch is converted to an 18-dimensional vector by down sampling by a factor of 2 (converting the block size from 8 × 8 pixels to 16 × 16 pixels) and representing an orientation element θ in an orientation patch as a 2-dimensional vector (cos 2θ, sin 2θ) to deal with the ambiguity between − π and π . The k-means
2
2 clustering method [22] is then adopted to find 24 cluster centers among the set of orientation patches. Fig. 6 displays the orientation fields of the 24 orientation patch cluster centers. iii) Fingerprint patch clustering: For each orientation patch center, a set of fingerprint patches of size 48 × 48 pixels (100,000 patches in our experiments) are selected by sliding a window over the ideal representation of selected fingerprint images with a step size of 8 pixels. A fingerprint patch is selected for the ith orientation patch center if it satisfies the quality requirement in step ii) and its closest orientation patch center is the ith one. A

total of 1,024 fingerprint patch cluster centers are constructed by the k-means clustering method [23] for each orientation patch center. The minutiae points in each cluster are removed using the method in section II to get its continuous phase which forms the continuous phase patch dictionary; a 24 × 1, 024 dictionary is constructed.
Fig. 7 shows some examples from the continuous phase patch dictionary. iv) Orientation and frequency fields estimation: The method in [16] is adopted to compute the orientation field and average ridge frequency for each dictionary element, which is used for dictionary lookup. Its unwrapped pixel-wise orientation field, which is used for adding input minutiae (spiral phase) to the continuous phase, is computed using the approach proposed in [9].
B. Orientation Field Reconstruction
The orientation field is considered only in the foreground region of a fingerprint which is determined by dilating the convex hull of the input minutiae points with a disk-shape mask with a radius of 32 pixels. The image is divided into non-overlapping blocks of size 16 × 16 pixels. For the blocks containing minutiae, their orientations are simply replaced by the directions of their corresponding minutiae (modulated by π), as shown in Fig. 8(b). Since the minutiae points are usually non-uniformly distributed (sparsely distributed in some regions), it is difficult to select representative orientation patches from DO in the region without minutiae or with one or two minutiae. Orientation patch dictionary, therefore, cannot

7

(a)

(b)

(c)

Fig. 9: A comparison of orientation field reconstruction. (a) Minutiae shown on the gray-scale fingerprint image, (b) orientation field reconstructed by the method in [8] and (c) orientation field reconstructed by the proposed method. Note that the proposed method provides better reconstruction results near the singular points (marked as yellow circles).

be used to reconstruct the orientation field directly. In order to address this problem, orientation density is introduced, and the orientations of blocks with low orientation density values are interpolated iteratively using Delaunay triangulation. Suppose that B = {(xi , yi )}Nb is the set of Nb blocks with orientations i=1 initialized by minutia direction (modulated by π) and DTB is the Delaunay triangulation of B. The orientation density D at block (x, y) is defined as
D(x, y) =

Nb
∑
i=1

Fig. 8: Illustration of orientation field interpolation methods.
(a) Minutiae shown on the gray-scale fingerprint image, (b) orientation field obtained from minutiae, (c) interpolated orientation field, (d) and (e) are the orientation density maps of
(b) and (c), respectively.

exp(−

(x − xi )2 + (y − yi )2
)
2σ 2

(10)

where σ is a parameter which controls the neighborhood influence. Fig. 8 (d) shows the density map of orientation field in Fig. 8 (b). Note that the orientation density values in some of the blocks are very small. Suppose the orientation density value D(xb , yb ) at block b = (xb , yb ) is the minimum value in the foreground and D(xb , yb ) is less than the density threshold
TD . The orientation θb at block b is then interpolated by blocks b1 , b2 and b3 , where △b1 b2 b3 ∈ DTB and b is in △b1 b2 b3 . Let θi denote the orientation of block bi and di be the Euclidean distance between bi and b (1 ≤ i ≤ 3). The cosine and sine components (u, v) of 2θb are computed as d2 d3 cos 2θ1 + d1 d3 cos 2θ2 + d1 d2 cos 2θ3 d2 d3 + d1 d3 + d1 d2 d2 d3 sin 2θ1 + d1 d3 sin 2θ2 + d1 d2 sin 2θ3 v= d2 d3 + d1 d3 + d1 d2

u=

(11)
(12)

The orientation θb at block b is obtained by θb = tan−1 (v, u)/2.

Fig. 10: Orientation interpolation in a triplet; b1 , b2 and b3 are three blocks shown with their orientations.

(13)

The block b is then added into the set B and the triangle
△b1 b2 b3 ∈ DTB is replaced by three triangles △bb2 b3 ,
△b1 bb3 and △b1 b2 b. The orientation density D(x, y) is updated using Eq. (10). The interpolation process continues till the orientation density values in all the blocks in the foreground are larger than TD . Figs. 8(c) and (e) show the interpolated orientation field and its corresponding orientation density map, respectively.

8

The orientation patch dictionary and context-based optimization [24] are then adopted to reconstruct the whole orientation field. The orientation field of blocks in B is regarded as the initial orientation field. For an initial orientation patch
(of size 10 × 10 blocks), 6 reference orientation patches from
DO are retrieved based on the similarity between the initial orientation patch and the reference orientation patches. The orientation similarity S O (Θ, Φ) between an initial orientation patch Θ and an orientation patch Φ from DO is defined as
S O (Θ, Φ) = (1 − λ)s(Θm , Φm ) + λs(Θv , Φv ),

Fig. 11: Fingerprint patch reconstruction.
(14)

where Θm and Φm are the sets of orientations at the blocks containing minutiae (shown in blue in Fig. 8 (c)) of the two orientation patches, Θv and Φv are the sets of orientations at the blocks without minutiae (shown in red in Fig. 8 (c)) of the two orientation patches, λ is a weight parameter (λ = 2 in
3
this paper to preserve the orientations obtained from minutiae better) and s({αi }n , {βi }n ) is the similarity between two i=1 i=1 orientation sets {α}n and {β}n , defined as i=1 i=1
1∑
cos(αi − βi ). n i=1 n s({αi }n , {βi }n ) = i=1 i=1

(15)

O
Let ri be the selected reference orientation patch candidate
O
for the initial orientation patch i. The selection of ri is affected not only by its fitness to the orientation field patch i but also by its neighboring selections. The optimal indices
O
O O vector rO = {r1 , r2 , ..., rNO } of all the NO orientation patches in the foreground can be selected by minimizing the following energy function E(ro ):
O
O
E O (rO ) = Es (rO ) + Ec (rO ),

(16)

O
O
where Es (rO ) is the dissimilarity term and Ec (rO ) is the compatibility term. The dissimilarity term is determined by the dissimilarity between the set of initial foreground patches V O and their corresponding selected reference orientation patches:
∑
O
O
Es (rO ) =
(1 − S O (Θi , Φi,ri )),
(17)
i∈V O
O
where Φi,ri is the ri th candidate reference orientation patch for initial orientation patch i and S O (·, ·) is defined in Eq.
(14). The compatibility term is defined as
∑
O
O
O
Ec (r) =
(1 − C O (Φi,ri , Φj,rj )),
(18)

containing minutiae. A modified Gaussian filtering is proposed to preserve the orientation around minutiae:
i) The orientations at the blocks with minutiae are replaced by the directions of minutiae (modulated by π). ii) The cosine and sine components of the double values of the orientations at the blocks without minutiae are smoothed using a Gaussian mask (with standard deviation value of 2). iii) Repeat Step ii) 3 times.
Fig. 9 compares the reconstructed orientation field from the algorithm in [8] and the proposed algorithm. It shows that the proposed algorithm is able to obtain better orientation approximation, especially in the regions near singular points.
This is achieved because of our use prior knowledge of local orientation pattern.
If the ridge frequency associated with minutiae is available, the Delaunay triangulation can be used to interpolate the ridge frequency field. Suppose that B is the set of Nb blocks with minutiae and DTB is the Delaunay triangulation of B. The ridge frequency fb at block b is interpolated by the triangle
△b1 b2 b3 ∈ DTB covering b: d2 d3 f1 + d1 d3 f2 + d1 d2 f3
,
(20) d2 d3 + d1 d3 + d1 d2 where fi denotes the ridge frequency of block bi which is obtained from the ridge frequency associated with the minutia contained in block bi , di is the Euclidean distance between bi and b (1 ≤ i ≤ 3). The ridge frequency at the blocks that are not in the convex hull of the block set B is estimated as the median frequency value within the convex hull of the block set
B. Otherwise, a constant frequency value 0.12, as suggested in [8], is used for the whole image. fb =

(i,j)∈N O

where N O is the set of four-connected neighboring orientation
O
O patches. The compatibility C O (Φi,ri , Φj,rj ) between two
O
O neighboring reference orientation patches Φi,ri and Φj,rj
O
O is measured by their orientations ϕi,ri and ϕj,rj in the overlapping blocks, defined as
O
O
O
O
C O (Φi,ri , Φj,rj ) = s(ϕi,ri , ϕj,rj ).

(19)

The loopy belief propagation algorithm [24], which has been shown to perform well on graphs with closed loops, is adopted to find the optimal reference orientation patches.
The orientation field reconstructed by the orientation patch dictionary may also change the orientations in the blocks

C. Fingerprint Reconstruction
The continuous phase patch dictionary is used to reconstruct fingerprint image patches based on the reconstructed orientation field and ridge frequency field in section III-B.
Global optimization is then adopted to obtain the reconstructed fingerprint image.
1) Fingerprint patch reconstruction: For a patch p of size
48 × 48 pixels in the initial image (only the reconstructed orientation field and ridge frequency field are available), its orientation field θp with 3 × 3 blocks and average frequency fp are obtained from the reconstructed orientation field and frequency field. The closest subdictionary, among the 24 continuous phase patch subdictionaries, is selected based on

9

the orientation similarity (defined in Eq.(15)) between θp and the orientation patch centers in Fig. 6. A set of Np continuous j Np phase patches {ψC }j=1 in the selected subdictionary are selected according to their similarity with θp and fp . The similarity between an initial image patch and a continuous phase patch (with orientation field θ and average ridge frequency f ) is defined as
2
1
−( f1 − f )2 /(2σf ) p S I ({θp , fp }, {θ, f }) = s(θp , θ) · e

,

(21)

where s(·, ·) is defined in (15) and σf is a parameter controlling the frequency similarity (σf = 3 in this paper).
The minutiae can be added by combining the continuous phase patch and the spiral phase computed from the minutiae p p np in a patch. Let M p = {mp = (xp , yi , αi )}i=1 denote the set i i p p of np minutiae in the patch p, where (xp , yi ) and αi are the i coordinates and direction of the ith minutia, respectively. The polarity pj of the ith minutiae on the jth selected continuous i j phase patch ψC is determined by the difference between p p αi and its unwrapped pixel-wise orientation field βj (xp , yi ) i which is obtained in III-A2 as
{
p p 1, if cos(αi − βj (xp , yi )) > 0, j i pi =
(22)
p p −1, if cos(αi − βj (xp , yi )) ≤ 0. i j j Then the spiral phase ψS of M p , corresponding to ψC , can be obtained by using Eq. (9). The jth phase ψj with minutiae j j is the combination of ψS and ψC and the reconstructed fingerprint patch Ij is cos(ψj ). Fig. 11 illustrates this process.
2) Fingerprint image reconstruction: The fingerprint image reconstruction can now be viewed as a combinatorial optimization problem similar to fingerprint orientation reconstruction in section III-B. For an initial fingerprint patch, a list of fingerprint patch candidates can be constructed using the approach in previous steps. The optimal candidates selection
I
I I rI = {r1 , r2 , ..., rNI } for all NI foreground initial fingerprint patches is performed by minimizing the following energy function, I
I
(23)
E I (rI ) = Es (rI ) + ωc Ec (rI ),
I
I where Es (rI ) is the dissimilarity term, Ec (rI ) is the compatibility term and ωc is the weight parameter. The dissimilarity term measures the dissimilarity of orientation field and frequency field between an initial fingerprint patch and its selected reconstructed fingerprint patch
∑
I
I
I
Es (rI ) =
(1 − S I ({θi , fi }, {θi,ri , fi,ri })),
(24)
i∈V I

where V I is the set of foreground fingerprint patches and S I (·, ·) is defined in Eq. (21). The compatibility
I
I
C I (Ii,ri , Ij,rj ) between two neighboring reconstructed fingerI
I
print patches Ii,ri and Ij,rj is measured by the difference of gray values at overlapping pixels. Let {xi }n and {yi }n i=1 i=1
I
I denote the set of coordinates for Ii,ri and Ij,rj at the n overI
I
lapping pixels, respectively. The C I (Ii,ri , Ij,rj ) is computed as n
1∑
I
I
I
C I (Ii,ri , Ij,rj ) =
(I I (xi ) − Ij,rj (yi ))2 .
(25)
n i=1 i,ri

I
The compatibility term Ec (rI ) is defined as
∑
I
I
I
Ec (rI ) =
(1 − C I (Ii,ri , Ij,rj )),

(26)

(i,j)∈N I

where N I is the set of four-connected neighboring patches.
The fingerprint patch selection is performed via the loopy belief propagation algorithm [24].
In order to alleviate the blocking effect when composing the fingerprint image using the selection of the reconstructed fingerprint patches, a weighting strategy [25] is used. Fig. 12
(a) shows a reconstructed fingerprint image and the minutiae detected in its phase image. There are no missing minutiae in this example. However, there may be a few spurious minutiae in the reconstructed fingerprints that are introduced in the overlapping regions because suboptimal selection may be obtained in minimizing the energy function (23).
D. Fingerprint Image Refinement
We adopt the global AM-FM model to remove the spurious minutiae from the reconstructed image I. The blockwise orientation field is expanded to pixel-wise orientation field. The orientation unwrapping method proposed in [9] is adopted to obtain the unwrapped orientation field Ou . For orientation field with singular points, there are horizontal discontinuity segments, which will introduce discontinuity in the unwrapped orientation field and then in the phase image. A discontinuity segment D(x1 , x2 , y) from pixel (x1 , y) to pixel (x2 , y) can be identified using the following two conditions [9]: 1) |Ou (x, y) − Ou (x, y − 1)| ≥ π/2 when x ∈ [x1 , x2 ], and 2) |Ou (x, y) − Ou (x, y − 1)| < π/2 when x ̸∈ [x1 , x2 ]. The position of a discontinuity segment
D(x1 , x2 , y = a) can be changed to the other side by adding sign(Ou (x1 , a) − Ou (x1 , a − 1))π for all rows y < a or subtracting sign(Ou (x1 , a) − Ou (x1 , a − 1))π for all rows y ≥ a.
In order to alleviate the effect of the discontinuity, the ith
(i ≥ 2) segment (according to the y coordinate in increasing order) is changed, if necessary, to reduce the overlapping x coordinates with (i − 1)th segment. We still use Ou to denote the optimized unwrapped orientation field. The phase image ψ of I is obtained by applying demodulation with the unwrapped orientation field Ou . Spurious minutiae (should not overlap with the input minutiae and the discontinuity segments), which are detected in ψ using the method in section
II, can be removed by subtracting the spirals formed by the spurious minutiae. However, due to the discontinuity in the phase image, spirals are also introduced at the discontinuity segments. The spirals at the ith discontinuity segment are removed using the following two steps: i i) A complementary unwrapped orientation field Ou is computed by (1) changing the ith discontinuity segment to the other side by adding or subtracting π and (2) changing other discontinuity segments, if necessary, to reduce the overlapping x coordinates with the ith discontinuity segment. ii) cos(ψi−1 ), where ψi−1 is the phase image obtained by removing the spirals around the (i − 1)th segment, is

10

(b)

(a)

(c)

(d)

(e)

(f)

(g)

(h)

Fig. 12: Illustration of spurious minutiae removal. (a) Fingerprint reconstructed using continuous phase patch dictionary, where red squares refer to input minutiae and blue circles refer to spurious minutiae, (b) unwrapped orientation field Ou , (c) and (d)
1
2 complementary unwrapped orientation fields Ou and Ou , respectively, (e) cos(ψ0 ), where ψ0 is the phase image after removing spurious minutiae, (f) cos(ψ1 ), where ψ1 is the phase image after removing spirals around the top discontinuity segment, (g) cos(ψ2 ), where ψ2 is the phase image after removing spirals around the discontinuity segment in the lower left region of the image, and (h) the final reconstruction image. The red squares in (e) and (f) are spirals around discontinuity segments. i demodulated to get ψi with Ou . The spirals around the ith segment in ψi are detected and removed.
After all discontinuity segments have been considered, Gabor filtering is used to smooth the fingerprint region around these discontinuity segments, and demodulation is used again to obtain the final phase image and then final reconstruction. Fig.
12 illustrates this process, where Fig. 12 (h) shows removal of the discontinuity.

IV. E XPERIMENTAL R ESULTS
The proposed fingerprint reconstruction algorithm is evaluated on two plain fingerprint databases (FVC2002 DB1 A and FVC2002 DB2 A), each of which contains 800 plain fingerprint images from 100 fingers, and one rolled fingerprint database (NIST SD4) which contains 4,000 rolled fingerprint images from 2,000 fingers (for each finger there are two impressions: a file fingerprint and a search fingerprint). Verifinger
SDK 6.3 [12] is used for minutiae extraction and fingerprint matching. The minutiae template includes coordinates
(x, y), direction (θ) and ridge frequency (f ) for each minutia point. For each fingerprint minutiae template, we reconstruct a fingerprint image using the proposed algorithm based on the following two types of inputs: 1) Minutiae: minutiae coordinates, minutiae directions and a fixed ridge frequency, and 2) Minutiae + Frequency: minutiae coordinates, minutiae directions and ridge frequency around each minutiae. The two reconstructed images for each template are compared with two other state-of-the-art approaches proposed by Feng and Jain

[8] and Li and Kot [9]. The codes for [8] and [9] were provided by the authors. Fig. 13 shows some reconstructed fingerprint images from different algorithms. The reconstruction performance is evaluated in terms of reconstructed minutiae2 accuracy with respect to input minutiae and matching performance in both verification and identification modes. The algorithm was implemented in MATLAB and run on a machine with Intel
Core i7 Q720 1.60GHz, 4GB RAM and 64-bit Windows 7 operating system. The average computation time for FVC2002
DB1, FVC200 DB2 and NIST SD4 is 20.55, 26.93 and 31.41 seconds, respectively, after loading all the dictionaries.
A. Reconstructed Minutiae Accuracy
Minutiae play a critical role in fingerprint recognition.
Missing and spurious minutiae in the reconstructed fingerprint image may deteriorate the matching performance between the reconstructed image and the original fingerprint image.
An input minutia p (input to the reconstruction algorithm) is regarded as missing if there are no minutiae in the reconstructed fingerprint within 10 pixels and 30 degrees of p’s location and direction. A minutia q in the reconstructed fingerprint is regarded as spurious if there are no input minutiae within 10 pixels and 30 degrees of q’s location and direction. The reconstructed minutiae accuracy is evaluated based on two measures: Missing Minutiae Rate (MMR) and
Spurious Minutiae Rate (SMR), where MMR refers to the
2 The reconstructed minutiae refer to the minutiae extracted by Verifinger
SDK 6.3 from the reconstructed fingerprint image.

11

Fig. 13: Examples of reconstructed fingerprint images. (a) Original fingerprint images (f1519.bmp (top, NFIQ3 =3) and f0669
(bottom, NFIQ=4) from NIST SD4), (b) reconstructed fingerprint images by the algorithm in [8], (c) reconstructed fingerprint images by the algorithm in [9], (d) reconstructed fingerprint images by the proposed algorithm with a fixed ridge frequency and (e) reconstructed fingerprint images by the proposed algorithm with ridge frequency around each minutiae. The true mate of the top fingerprint in (a) is retrieved at rank 64, 18, 2 and 1 for (b), (c), (d) and (e), respectively, and the true mate of the bottom fingerprint in (a) is retrieved at rank 1,470, 335, 182 and 1 for (b), (c), (d) and (e), respectively, in type-II attack.

percentage of missing minutiae and SMR refers to the percentage of spurious minutiae. As shown in Tables II and III, the proposed reconstruction algorithm outperforms two stateof-the-art algorithms, [8] and [9], in terms of MMR and is comparable with [9] in terms of SMR for all three databases.
TABLE II: Comparison of average Missing Minutiae Rate
(MMR) (%)
Databases
FVC2002 DB1 A
FVC2002 DB2 A
NIST SD4

Feng and
Jain [8]
26.64
25.42
25.70

Li and
Kot [9]
16.32
14.37
15.24

Minutiae
10.73
8.80
11.65

Minutiae
+ Frequency
9.79
9.18
12.18

TABLE III: Comparison of average Spurious Minutiae Rate
(SMR) (%)
Databases
FVC2002 DB1 A
FVC2002 DB2 A
NIST DB4

Feng and
Jain [8]
31.06
37.26
21.91

Li and
Kot [9]
7.63
8.49
7.72

Minutiae
8.42
8.51
5.67

Minutiae
+ Frequency
9.29
8.44
5.67

B. Fingerprint Verification
The verification experiments are conducted on the FVC2002
DB1 A and FVC2002 DB2 A databases. In order to evaluate the verification performance, type-I and type-II attacks, proposed in [8], are considered. In type-I attack, each reconstructed fingerprint is matched against the same impression from which the minutiae template was extracted, while in typeII attack, each reconstructed fingerprint is matched against
3 NFIQ [20] assigns a quality value of 1 (highest quality) - 5 (lowest quality) to a fingerprint image.

the other 7 impressions of the same finger, which is more challenging than type-I attack. Therefore, there are 800 type-I attacks and 5,600 type-II attacks for each database that can be launched against the fingerprint verification system. The match scores from type-I or type-II attacks are regarded as genuine match scores. A total number of 4,950 imposter match scores are obtained by cross matching the first impression of each finger following the FVC2002 protocol [26]. The thresholds at different false accept rate (FAR) are calculated based on the imposter match scores. The Receiver Operating Characteristic
(ROC) curves of the four reconstructions for each image in
FVC2002 DB1 A and FVC2002 DB2 A are plotted in Figs.
14 and 15, respectively. The matching performance of the proposed reconstruction algorithm is significantly better than that of the two state-of-the-art reconstruction algorithms. In other words, given a minutiae template, the proposed reconstruction algorithm is better than the other two algorithms [8], [9] in terms of preserving the original fingerprint characteristics.
In the type-I attack, the ROC curves of the proposed reconstruction are quite close to the original image on both databases. With a fixed ridge frequency, the true accept rates
(TAR) at a FAR=0.01% of the proposed reconstruction are
99.38% and 99.88% on FVC2002 DB1 A and FVC2002
DB2 A, respectively. In the type-II attack, TAR at the same
FAR of the proposed reconstruction is at least 24% higher on FVC2002 DB1 A and at least 19% higher on FVC2002
DB2 A than the methods in [8] and [9], respectively.
Ridge frequency is an important feature that helps improve the reconstruction performance. Given the ridge frequency around each minutia, the TAR (at FAR=0.01% ) of typeI attack based on our reconstructed fingerprints is further improved to 100% on both FVC2002 DB1 A and FVC2002

12

1

1
0.95
0.9
True Accept Rate (TAR)

True Accept Rate (TAR)

0.98

0.96

0.94

0.92
Image
Feng and Jain [8]
Li and Kot [9]
Minutiae
Minutiae+Frequency

0.9

0.88
−4
10

−3

10

−2

10
False Accept Rate (FAR)

−1

10

0.85
0.8
0.75
0.7
0.65
Image
Feng and Jain [8]
Li and Kot [9]
Minutiae
Minutiae+Frequency

0.6
0.55
0.5
−4
10

0

10

−3

10

(a)

−2

10
False Accept Rate (FAR)

−1

10

0

10

(b)

Fig. 14: ROC curves of different reconstruction algorithms on FVC2002 DB1 A under (a) type-I attack and (b) type-II attack.

0.95

0.98

0.9

True Accept Rate (TAR)

1

0.99

True Accept Rate (TAR)

1

0.97

0.96

0.95
Image
Feng and Jain [8]
Li and Kot [9]
Minutiae
Minutiae+Frequency

0.94

0.93
−4
10

−3

10

−2

10
False Accept Rate (FAR)

−1

10

0.85

0.8

0.75
Image
Feng and Jain [8]
Li and Kot [9]
Minutiae
Minutiae+Frequency

0.7

0

10

(a)

0.65
−4
10

−3

10

−2

10
False Accept Rate (FAR)

−1

10

0

10

(b)

Fig. 15: ROC curves of different reconstruction algorithms on FVC2002 DB2 A under (a) type-I attack and (b) type-II attack.

DB2 A. The TAR (at FAR=0.01% ) of type-II attack is further improved to 85.23% and 90.29% on FVC2002 DB1 A and
FVC2002 DB2 A, respectively.

C. Fingerprint Identification
The minutiae templates of 2,000 file fingerprints from NIST
SD4 are used to reconstruct fingerprints for fingerprint identification experiments. Each reconstructed fingerprint is matched against 2,000 file fingerprints as the gallery to obtain 2,000 type-I attacks and against 2,000 search fingerprints as the gallery to obtain 2,000 type-II attacks. The Cumulative Match
Characteristic (CMC) curves of type-I and type-II attacks for four reconstructions, as well as original fingerprints, are compared in Fig. 16. Similar to the verification experiments, the identification performance of type-I attack is very high.
The rank-1 identification rate of the proposed algorithm with a fixed ridge frequency is 99.05%. When the ridge frequency around minutiae is utilized in reconstruction, the rank-1 identification rate is improved to 99.95%, which indicates that the features in the reconstructed fingerprint images are very close to the features in the original images.

In terms of type-II attack, the rank-1 identification rate of the proposed algorithm with a fixed ridge frequency is 71.00%, which is 28.20% higher than the algorithm in [9] and 18.50% higher than the algorithm in [8]. With the ridge frequency around minutiae, the rank-1 identification rate is improved to
82.45%. The comparative results confirm that the proposed reconstruction algorithm performs better than the two stateof-the-art reconstruction algorithms of [8] and [9].
We also investigate the attack performance (both type-I and type-II attacks) of the reconstructed fingerprint images with respect to the quality of fingerprints from which minutiae templates are extracted. NFIQ [20] is used as a quality index.
Tables IV and V compare the identification performance of the three reconstruction algorithms for type-I and type-II attacks, respectively. These results show that, as expected, the identification performance of all three algorithms drops when fingerprint quality decreases, especially for type-II attack.
Fig. 13 compares the four reconstructions of a fingerprint image shown in Fig. 13 (a). Given the prior knowledge of orientation pattern (i.e., orientation patch dictionary), the orientation field reconstructed from the proposed algorithm is better than the method proposed in [8]; the singular points

13

Cumulative Match Characteristic

Cumulative Match Characteristic
100

100
99

90
Identification Rate (%)

Identification Rate (%)

98
97
96
95
94
93

Original image
Feng and Jain [8]
Li and Kot [9]
Minutiae
Minutiae+Frequency

92
91
90

10

20

30

40

50
Rank

60

70

80

90

100

(a)

80

70

60
Original image
Feng and Jain [8]
Li and Kot [9]
Minutiae
Minutiae+Frequency

50

40

10

20

30

40

50
Rank

60

70

80

90

100

(b)

Fig. 16: CMC curves of different reconstruction algorithms on NIST SD4 under (a) type-I attack and (b) type-II attack.

obtained from the proposed algorithm are very close to the original ones. Although a fixed ridge frequency was used in
[9], variations in ridge frequency are visible in the reconstructed image shown in Fig. 13 (c). As shown in section II, the main reason is that the ridge structure does change after editing the minutiae (removing or adding minutiae). While the ridge frequency in Fig. 13 (b) is preserved well, there is a noticeable blocking effect. Based on these experimental results, we conclude that the proposed phase patch dictionary based reconstruction algorithm is able to preserve the ridge structure compared to published methods.
TABLE IV: Rank-1 identification performance of type-I attack on NIST SD4 for different NFIQ values (%).
NFIQ
1
2
3
4
5

Original image 100.00
100.00
100.00
100.00
100.00

Feng and
Jain [8]
97.95
92.08
92.09
88.54
61.64

Li and
Kot [9]
94.46
87.46
89.60
85.35
65.38

Minutiae
99.88
98.68
99.12
96.82
88.46

Minutiae
+ Frequency
100.00
100.00
100.00
100.00
96.15

TABLE V: Rank-1 identification performance of type-II attack on NIST SD4 for different NFIQ values (%).
NFIQ
1
2
3
4
5

Original image 99.04
99.01
96.93
84.71
61.54

Feng and
Jain [8]
70.76
53.47
40.56
14.01
3.85

Li and
Kot [9]
56.44
42.24
34.70
13.38
3.85

Minutiae
87.97
67.99
62.81
32.48
11.54

Minutiae
+ Frequency
95.79
88.12
76.28
40.13
7.69

V. C ONCLUSIONS AND F UTURE W ORK
The goal of fingerprint reconstruction is to reproduce the original fingerprint image from an input minutiae set. There are essentially three main reasons for studying the problem of fingerprint image reconstruction from a given minutiae set:
(i) to demonstrate the need for securing minutiae template,
(ii) to improve the interoperability of fingerprint templates generated by different combinations of sensors and algorithms,

(iii) to improve fingerprint synthesis. Despite a significant improvement in the performance of reconstruction algorithms over the past ten years, there is still a discrepancy between the reconstructed fingerprint image and original fingerprint image (from which the minutiae template was extracted) in terms of matching performance. In this paper, we propose a reconstruction algorithm that utilizes prior knowledge of fingerprint ridge structure to improve the reconstructed fingerprint image. The prior knowledge is represented in terms of two kinds of dictionaries, orientation patch and continuous phase patch dictionaries. The orientation patch dictionary is used to reconstruct the orientation field from the given minutiae set, while the continuous phase patch dictionary is used to reconstruct the ridge pattern. Experimental results on three public domain fingerprint databases ( FVC2002 DB1 A,
FVC2002 DB2 A and NIST SD4) show that the proposed reconstruction algorithm outperforms two state-of-the-art reconstruction algorithms [8] and [9] in terms of reconstructed minutiae accuracy and matching performance for both type-I and type-II attacks.
Although the reconstructed fingerprints, as shown in Fig.
13, are very close to the original fingerprints from which the minutiae were extracted in terms of orientation field, ridge frequency field and minutiae distribution, it is still difficult to fool a human expert because the reconstructed fingerprints are ideal fingerprints (without any noise) and have the synthetic appearance. Future work will investigate to make the reconstructed fingerprints more realistic. The proposed method for orientation field reconstruction only considers the local orientation pattern. The use of global orientation prior knowledge as well as singular points may further improve the ridge orientation reconstruction. The ridge frequency field used in this paper can be either a fixed priori or reconstructed from the ridge frequency around minutiae. Future work will investigate frequency field reconstruction directly from the minutiae position and direction.
ACKNOWLEDGMENT
The authors would like to thank Prof. Alex C. Kot and
Sheng Li for providing us their reconstruction code for our

14

comparative analysis, and Sunpreet S. Arora for conducting some of the initial experiments. Kai Cao’s research was partially supported by National Natural Science Foundation of China (Grant No. 61101247 and 61473214).
R EFERENCES
[1] D. Maltoni, D. Maio, A. Jain, and S. Prabhakar, Handbook of Fingerprint
Recognition, second edition ed. Springer, 2009.
[2] ISO/IEC 19794-2:2005, Information technology – Biometric data interchange formats – Part 2: Finger minutiae data, 2005.
[3] BioLab, “FVC-onGoing,” http://bias.csr.unibo.it/fvcongoing.
[4] C. Hill, “Risk of masquerade arising from the storage of biometrics,”
2001, Bachelor’s Thesis.
[5] B. G. Sherlock and D. M. Monro, “A model for interpreting fingerprint topology,” Pattern Recognition, vol. 26, no. 7, pp. 1047–1055, 1993.
[6] A. Ross, J. Shah, and A. Jain, “From template to image: Reconstructing fingerprints from minutiae points,” IEEE Transactions on Pattern
Analysis and Machine Intelligence, vol. 29, no. 4, pp. 544–560, 2007.
[7] R. Cappelli, D. Maio, A. Lumini, and D. Maltoni, “Fingerprint image reconstruction from standard templates,” IEEE Transactions on Pattern
Analysis and Machine Intelligence, vol. 29, no. 9, pp. 1489–1503, 2007.
[8] J. Feng and A. K. Jain, “Fingerprint reconstruction: From minutiae to phase,” IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 33, no. 2, pp. 209–223, Feb. 2011.
[9] S. Li and A. Kot, “An improved scheme for full fingerprint reconstruction,” IEEE Transactions on Information Forensics and Security, vol. 7, no. 6, pp. 1906–1912, 2012.
[10] F. Chen, J. Zhou, and C. Yang, “Reconstructing orientation field from fingerprint minutiae to improve minutiae-matching accuracy,” IEEE
Transactions on Information Forensics and Security, vol. 18, no. 7, pp.
1906–1912, 2009.
[11] E. Liu, H. Zhao, L. Pang, K. Cao, J. Liang, and J. Tian, “Method for fingerprint orientation field reconstruction from minutia template,”
Electronics Letters, vol. 47, no. 2, pp. 98–100, January 2011.
[12] Neurotechnology Inc, “Verifinger,” http://www.neurotechnology.com/ verifinger.html. [13] K. G. Larkin and P. A. Fletcher, “A coherent framework for fingerprint analysis: Are fingerprints holograms,” Optics Express, vol. 15, pp. 8667–
8677, 2007.
[14] J. Feng, J. Zhou, and A. K. Jain, “Orientation field estimation for latent fingerprint enhancement,” IEEE Transactions on Pattern Analysis and
Machine Intelligence, vol. 54, no. 4, pp. 925–940, 2013.
[15] K. Cao, E. Liu, and A. Jain, “Segmentation and enhancement of latent fingerprints: A coarse to fine ridge structure dictionary,” IEEE
Transactions on Pattern Analysis and Machine Intelligence. To appear.
[16] L. Hong, Y. Wan, and A. Jain, “Fingerprint image enhancement:
Algorithm and performance evaluation,” IEEE Transactions on Pattern
Analysis and Machine Intelligence, vol. 20, no. 8, pp. 777–789, 1998.
[17] D. C. Ghiglia and M. D. Pritt, Two-Dimensional Phase Unwrapping:
Theory, Algorithm, and Software. New York, NY: John Wiley and
Sons, 1998.
[18] R. M. Goldstein, H. A. Zebker, and C. L. Werner, “Satellite radar interferometry: Two-dimensional phase unwrapping,” Radio
Science, vol. 23, no. 4, pp. 713–720, 1988. [Online]. Available: http://dx.doi.org/10.1029/RS023i004p00713 [19] “NIST Special Database 4,” http://www.nist.gov/srd/ nistsd4.cfm.
[20] E. Tabassi, C. Wilson, and C. Watson, “Fingerprint image quality,”
NISTIR 7151, 2004.
[21] M. D. Garris, E. Tabassi, C. I. Wilson, R. M. McCabe, S. Janet, and
C. I. Watson, “NIST fingerprint image software 2,” 2004. [Online].
Available: http://www.nist.gov/itl/iad/ig/nbis.cfm
[22] G. Nagy, “State of the art in pattern recognition,” Proceedings of the
IEEE, vol. 56, no. 5, pp. 836–863, 1968.
[23] A. K. Jain, “Data clustering: 50 years beyond k-means,” Pattern Recognition Letters, vol. 31, no. 8, pp. 651 – 666, 2010.
[24] C. R. Andrew Blake, Pushmeet Kohli, Markov Random Fields for Vision and Image Processing. MIT Press, 2011.
[25] S. Chikkerur, A. N. Cartwright, and V. Govindaraju, “Fingerprint enhancement using STFT analysis,” Pattern Recognition, vol. 40, no. 1, pp. 198–211, 2007.
[26] FVC2002, “http://bias.csr.unibo.it/fvc2002/,” 2002.