# Fingerprint Classification Combining Curvelet Transform and Gray-Level Cooccurrence Matrix

Authors: Jing Luo; Dan Song; Chunbo Xiu; Shuze Geng; Tingting Dong
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Fingerprint classification is an important indexing scheme to reduce fingerprint matching time for a large database for efficient large-scale identification. The abilities of Curvelet transform capturing directional edges of fingerprint images make the fingerprint suitable to be classified for higher classification accuracy. This paper presents an efficient algorithm for fingerprint classification combining Curvelet transform (CT) and gray-level cooccurrence matrix (GLCM). Firstly, we use fast discrete Curvelet transform warping (FDCT_WARPING) to decompose the original image into five scales Curvelet coefficients and construct the Curvelet filter by Curvelet coefficients relationship at adjacent scales to remove the noise from signals. Secondly, we compute the GLCMs of Curvelet coefficients at the coarsest scale and calculate 16 texture features based on 4 GLCMs. Thirdly, we construct 49 direction features of Curvelet coefficients at the other four scales. Finally, fingerprint classification is accomplished byK-nearest neighbor classifiers. Extensive experiments were performed on 4000 images in the NIST-4 database. The proposed algorithm achieves the classification accuracy of 94.6 percent for the five-class classification problem and 96.8 percent for the four-class classification problem with 1.8 percent rejection, respectively. The experimental results verify that proposed algorithm has higher recognition rate than that of wavelet-based techniques.


---

## Body

## 1. Introduction

As a type of human biometrics, fingerprint has been widely used for personal recognition in forensic and civilian applications because of its uniqueness, immutability, and low cost. An automatic recognition of people based on fingerprints requires matching of an input fingerprint with a large number of fingerprints in a database. However, the database can be huge (e.g., the FBI database contains more than 70 million fingerprints), such a task can be very expensive in terms of computational burden and time. In order to reduce the search time and computational burden, fingerprints in the database are classified into several prespecified types or subclasses. When an input fingerprint is received, a coarse level matching is applied to determine which subclass the input belongs to, and then at a finer level, it is compared to samples within the subset of the database for recognition. While such a scheme is obviously more efficient, the first step, that is, fingerprint classification, must be accurate and reliable and hence has attracted extensive research in recent years [1–13].Fingerprints are classified based on their shapes, and in literature it is common to have five classes as shown in Figure1  (x):(A) (x = a, b, c, d, e), including whorl (W), right loop (R), left loop (L), arch (A), and tent arch (T). Although these five classes appear very different to us as a person, automatically classifying a fingerprint by a machine is in fact a very challenging pattern recognition problem, due to the small interclass variability, the large intraclass variability and the difficulty for poor quality fingerprints. Fingerprint classification is carried out by analysis and comparison of the features. Over the past decade various approaches have been proposed by means of different types of features, such as singularities [1–3], orientation field [4–6], and statistical and frequency features [7–10]. The methods based on singularities [1–3] accomplish fingerprint classification according to the number and relative position of the core and delta points. The approaches using orientation field [4–6] partition the fingerprint orientation field into “homogeneous” orientation regions and the relational graphs of these regions are used to make fingerprint classification. Gabor filter [9] can also be used to extract the fingerprint features for classification where the input image is decomposed into four component images by four Gabor filters, and the standard deviation of the component images in each sector to generate the feature vector, and uses a K-nearest neighbor classifier to make fingerprint classification.(a) (A) Original right loop image and (B) denoised right loop image. (b) (A) Original left loop image, (B) denoised left loop image. (c) (A) Original whorl image and (B) denoised whorl image. (d) (A) Original arch image and (B) denoised arch image. (e) (A) Original tented arch image and (B) denoised tented arch image.
(a)
(b)
(c)
(d)
(e)In 2001, Tico et al. [10] proposed an approach to use wavelet transform as features for fingerprint recognition. In [10], a wavelet decomposition on 6 octaves of each fingerprint image was performed, and the normalized l2-norm of each wavelet subimage is computed to extract a feature vector of length 18. The experimental database contains 168 fingerprint images collected from 21 fingers (8 images per finger). The algorithm achieves the accuracy of 100% when wavelet basis Symmlet 6 or Symmlet 9 was employed. The work in [10] shows that the wavelet features are suitable for matching complex patterns of oriented texture such as fingerprints. However, wavelets are characterized by isotropic scaling (e.g., the standard orthogonal wavelet transform contains wavelets in the directions of primary vertical, primary horizontal, and primary diagonal only) and hence their abilities to resolve directional features are limited. So wavelets are not able to detect curved singularities effectively.Inspired by the success of wavelets, a number of other multiresolution analysis tools have also been proposed with the aim to present better the edges and other singularities along curves. These tools include contourlet, ridgelet, and Curvelet. In recent years, researchers have used Curvelets for fingerprint image enhancement [11, 12] and for fingerprint recognition [13]. Comparing to the limited directional features of wavelets, Curvelets are more powerful as they are able to describe a signal by a group of matrices at multiscale and multidirection. Furthermore, with the increase of the scale, the number of directions is much finer.In 2008, Mandal and Wu [13] proposed to use Curvelet transform for fingerprint recognition and achieved the accuracy of 100%. However, the performance of the proposed algorithm was only tested on a small database of 120 fingerprint images (containing only 15 individuals). Furthermore, in order to ensure the accuracy, the technique requires manual detection of the core of the fingerprint image. Also, before extracting the Curvelet features, the technique needs complex image enhancement process which includes estimation of local ridge-orientation, estimation of local ridge-frequency across the fingerprint, filtering of the image, and binarization (conversion of a gray-scale fingerprint image to binary image).In this paper, we present a novel fingerprint classification algorithm. Firstly, we use fast discrete Curvelet transform warping (FDCT_WARPING) to decompose the original image into five-scale Curvelet coefficients and construct the Curvelet filter by Curvelet coefficients relationship at adjacent scales to smooth the discontinuities of ridges and remove the noise in the fingerprint image. Secondly, we calculate four gray-level cooccurrence matrices (GLCMS) of Curvelet coefficients at the coarsest scale and calculate 16 texture features based on 4 GLCMS. Furthermore, we construct 49 direction features of Curvelet coefficients at the other four scales. Finally, these combined Curvelet-GLCM based features act as the feature set to aK-nearest neighbor classifier.In the following sections, we will present the details of our fingerprint classification algorithm. Section2 presents our noise filtration scheme and our feature extraction scheme. Section 3 presents some experimental results achieved on NIST-4 databases. Finally Section 4 draws the conclusions and outlines the open problems.


## 2. Fingerprint Classification

### 2.1. Fingerprint Alignments

Considering the translation and rotation between template images and probe images, this paper adopted the algorithm in [14] to accomplish the fingerprint image registration. The algorithm used the reference points of the central area to calculate the parameters of translation and rotation, which is much more general when there are no cores in the fingerprint images.


### 2.2. Fast Discrete Curvelet Transform (FDCT)

Curvelets were proposed by Candese and Donoho [15], constituting a family of frames that are designed to represent the edges and other singularities along curves. Conceptually, the Curvelet transform is a multiscale pyramid with many orientations and positions at each length scale and needle-shaped elements at fine scale. This pyramid is nonstandard, however. Indeed, Curvelets have useful geometric features that set them apart from wavelets and the likes. For instance, Curvelets present highly anisotropic behavior as it has both variablelength andwidth. At fine scale, anisotropy increases with decreasing scale, in keeping with power law.In 2006, Candès et al. proposed two fast discrete Curvelet transforms (FDCT) [16]. The first one is based on unequally spaced fast Fourier transforms (USFFT) [16], and the other is based on the wrapping of specially selected Fourier samples (FDCT_WARPING) [16]. Curvelets by warping have been used for this work, because this is the fastest Curvelet transform currently available [16].After Curvelet transform, several groups of Curvelet coefficients are generated at different scales and angles. Curvelet coefficients at scalej and angle l are represented by a matrix Cj,l, and scale j is from finest to coarsest scale, and angle l starts at the top-left corner and increases clockwise.Suppose thatf(t1,t2), 1≤t1≤N1, 1≤t2≤N2 denotes original image and f^[n1,n2] denotes 2D discrete Fourier transform; N1, N2 is the size of original image.The implementation of FDCT_WARPING is as follows.Step 1.
2D FFT (fast Fourier transform) is applied onf(t1,t2) to obtain Fourier samples f^[n1,n2].Step 2.
Resamplef^[n1,n2] at each pair of scale and direction j, l in frequency domain, yielding the new sampling function:
(1)f^[n1,n2-n1tan⁡θl],(n1,n2)∈Pj,
where Pj={(n1,n2),n1,0≤n1<n1,0+L1,j,n2,0≤n2<n2,0+L2,j} and n1,0 and n2,0 are two initial positions of the window function u~j,l[n1,n2].
L
1
,
j and L2,j are relevant parameters of 2j and 2j/2, respectively, and they are length and width components of window function support interval.Step 3.
Multiplication of the new sampling functionf^[n1,n2-n1tan⁡θl] with window function u~j[n1,n2], and the result is [16]
(2)f~j,l[n1,n2]=f^[n1,n2-n1tan⁡θl]u~j,l[n1,n2],
where
(3)u~j,l[n1,n2]=wj(w1,w2)vj(sθl·(2⌊j/2⌋w2)w1),wj(w1,w2)=ϕj+12(w2)-ϕj2(w2),ϕj(w1,w2)=ϕ(2-jw1)ϕ(2-jw2),sθl=[10-tan⁡θl1],tan⁡θl=l×2⌊-j/2⌋,l=-2⌊-j/2⌋,…,2⌊-j/2⌋-1.Step 4.
Apply the inverse 2D FFT to eachf~j,l, hence collecting the discrete coefficients Cj,l.


### 2.3. Fingerprint Image FDCT and Noise Filtration Technique

Curvelet transform describes a signal by the power at each scale, angle, and position. Curvelets have variable length in addition to variable width. Curvelet transform has improved directional capability and better ability to represent edges and other singularities along curves compared to other multiscale transforms, for example, wavelet transform. Image like fingerprints often have two nearby regions (ridges and valleys) that differ in pixel values. These variations in pixel values between two consecutive regions are likely to form such “edges” and this edge information is eventually captured by digital Curvelet transform.


#### 2.3.1. Acquisition of Curvelet Coefficients

In this paper, fingerprint images are from NIST-4 databases. Firstly, the size of all the images is normalized to 256 × 256 pixels. The proposed algorithm is implemented by using MATLAB 7.5 programming language and is executed under Windows XP Professional O.S. on a PC with AMD Dual-Core CPU E-350 at 1.28 GHz. The original image is decomposed by FDCT_WARPING [16].Suppose thatf(t1,t2), 1≤t1≤N1, 1≤t2≤N2 denotes original fingerprint image and f^[n1,n2] denotes 2D discrete Fourier transform; N1, N2 is the size of original fingerprint image.The number of scales can be calculated by(4)Nscales=ceil(log⁡2(min⁡(N1,N2))-3),
where min⁡(N1,N2) returns the minimum of N1 and N2 and ceil(·) rounds the input to the nearest integers greater than or equal to input.The number of orientation at scale2,3,…,Nscales-1, is calculated by
(5)lj=16×2ceil((Nscales-i)/2),
where i=Nscales, j=2; i=Nscales-1, j=3;…; i=3, and j=Nscales-1.Noted that if FDCT_WARPING chooses the Curvelets for the coefficients at the finest levelNscales, the number of orientation at scale Nscales can be determined by (2). On the other hand, when choosing the wavelets for the coefficients at the finest level Nscales, there is only one angle at the finest level Nscales. In this paper, we adopt the wavelets for the coefficients at the finest level Nscales. As a result, there is only one angle at the finest level Nscales.For scalej=2,3,…,(Nscales-1), all the Curvelet coefficients are divided into the four quadrants. The quadrant label of Curvelet coefficients is denoted by quad, and four quadrants are denoted by quad=1,2,3,4, respectively. At each quadrant, Curvelet coefficients are further subdivided in angular panels. The number of angular panels at each quadrant of each scale j, denoted by nquad-j, can be calculated as follows:
(6)nquad-j=4×2ceil((Nscales-i)/2),
where i=Nscales, j=2; i=Nscales-1, j=3;…; i=3, and j=Nscales-1.In this paper, according to (4), we can get the number of scales Nscales=5. According to (5), the number of angle at scale 4 is 32, at scale 3 is 32, and at scale 2 is 16. At scale 4, the number of angular panels of each quadrant is 8. At scale 3, the number of angular panels of each quadrant is 8. At scale 2, the number of angular panels of each quadrant is 4. After decomposition, the original image was divided into three levels: coarse, detail, and fine. The low-frequency coefficients were assigned to coarse. The high-frequency coefficients were assigned to fine. The middle-frequency coefficients were assigned to detail. According to FDCT_WARPING [16], the scale j is from finest to coarsest scale and angle l starts at the top-left corner and increases clockwise.The acquisition of Curvelet coefficients is as follows.Step 1.
2D FFT (fast Fourier transform) is applied onf(t1,t2) to obtain Fourier samples f^[n1,n2].Step 2.
Acquire the Curvelet coefficients at scale 5, denoted by matrixC5,1.Suppose that(7)M1=N16,M2=N26,lNscales-1=floor(2×M1)-floor(M1)-1,lNscales-2=floor(2×M2)-floor(M2)-1.
In this paper, floor(·) rounds the input to the nearest integers less than or equal to the input.(1)
Construct the right and left windows along the horizontal direction, denoted by row vectorWr-1 and Wl-1, respectively. Consider
(8)Wr-1(i)={1,i=0,e(1-1/(1-e(1-1/i))),i=1lNscales-1,2lNscales-1,…,lNscales-1-1lNscales-1,0,i=1,Wl-1(i)={0,i=0,e(1-1/(1-e(1-1/(1-i)))),i=1lNscales-1,2lNscales-1,…,lNscales-1-1lNscales-1,1,i=1.(2)
Construct the right and left windows along the vertical direction, denoted by row vectorWr-2 and Wl-2, respectively. Consider
(9)Wr-2(i)={1,i=0,e(1-1/(1-e(1-1/i))),i=1lNscales-2,2lNscales-2,…,lNscales-2-1lNscales-2,0,i=1,(10)Wl-2(i)={0,i=0,e(1-1/(1-e(1-1/(1-i)))),i=1lNscales-2,2lNscales-2,…,lNscales-2-1lNscales-2,1,i=1.Wr-1, Wl-1, Wr-2, and Wl-2 are normalized by
(11)Wr-1(i)=Wr-1(i)[Wr-1(i)]2+[Wl-1(i)]2,Wl-1(i)=Wl-1(i)[Wr-1(i)]2+[Wl-1(i)]2,Wr-2(i)=Wr-2(i)[Wr-2(i)]2+[Wl-2(i)]2,Wl-2(i)=Wl-2(i)[Wr-2(i)]2+[Wl-2(i)]2.(3)
Construct the two sub-low-pass filters, denoted by row vectorflowpasssub1 and flowpasssub2, respectively. Consider
(12)flowpasssub1=[Wl-1,1,1⋯1︸p1,Wr-1]1×[2×floor(2×M1)+1],flowpasssub2=[Wl-2,1,1⋯1︸p2,Wr-2]1×[2×floor(2×M2)+1],
where p1=2×floor(M1)+1, p2=2×floor(M2)+1.(4)
Construct a low-pass filter at scale 5, denoted by matrix(flowpass_5)[2×floor(2×M1)+1]×[2×floor(2×M2)+1], and
(13)flowpass_5=(flowpasssub1)T×flowpasssub2,
where (·)T is the transpose vector or matrix of the input vector or matrix.(5)
Construct a high-pass filter at scale 5, denoted by matrixfhipass_5, which has the same size as flowpass_5. Consider
(14)fhipass_5=1-(flowpass_5)2.(6)
f^[n1,n2] is filtered by fhipass_5, hence generating the filtered high-pass signal at scale 5 fhipass_5′, which has the same size of N1×N2 as f^[n1,n2]. Consider
(15)fhipass_5′(n1,n2)={f^(n1,n2)×fhipass_5(n1,n2),a≤n1≤b,c≤n2≤d,f^(n1,n2),others,
where the filter at scale 5 has the following range:
(16)a=-floor(2×M1)+ceil((N1+1)2),b=floor(2×M1)+ceil((N1+1)2),c=-floor(2×M2)+ceil((N2+1)2),d=-floor(2×M2)+ceil((N2+1)2).(7)
Inverse 2DFFT (inverse fast Fourier transform) is applied tofhipass_5′, hence generating the discrete Curvelet coefficients at scale 5, C5,1.(8)
f^[n1,n2] is filtered by flowpass_5, hence generating the filtered low-pass signal at scale 5, (flowpass_5′)[2×floor(2×M1)+1]×[2×floor(2×M2)+1] and
(17)flowpass5′(n1,n2)=f^(n1,n2)×flowpass5(n1,n2),iiiiiiiiiiiiiiiiiiiiiiiiiiiiia≤n1≤b,c≤n2≤d.Step 3.
Acquire the Curvelet coefficients at scale 4 and angle 1 to angle 32,C4,l, l=1,2,…,32.Firstly, we acquire the Curvelet coefficients at scale 4 and angle 1,C4,1.Suppose that(18)M1=N1(6×2),M2=N2(6×2).The filter at scale 4 has the following range:(19)aNscales-1=-floor(2×M1)+floor(4×M1)+1,bNscales-1=floor(2×M1)+floor(4×M1)+1,cNscales-1=-floor(2×M2)+floor(4×M2)+1,dNscales-1=floor(2×M2)+floor(4×M2)+1.(1)
Construct a low-pass filter at scale 4 and angle 1 in the same way as at scale 5,(flowpass_4)[2×floor(2×M1)+1]×[2×floor(2×M2)+1].(2)
Construct a high-pass filter at scale 4 and angle 1 in the same way as at scale 5,(fhipass_4)[2×floor(2×M1)+1]×[2×floor(2×M2)+1].(3)
flowpass_5′ is filtered by flowpass_4, hence generating the filtered low-pass signal at scale 4 (flowpass_4′)[2×floor(2×M1)+1]×[2×floor(2×M2)+1].(4)
flowpass_5′ is filtered by fhipass_4, hence generating the filtered high-pass signal at scale 4 fhipass_4′, which has the same size as that of flowpass_5′.(5)
Determine the discrete locating window of wedge wave at scale 4 and angle 1.The Curvelet coefficients at scale 4 are divided into the four quadrants. The quadrant label of Curvelet coefficients is denoted byquad, and four quadrants are denoted by quad=1,2,3,4, respectively. Each quadrant has 8 angles. In the first quadrant, quad=1, angle ranges from 1 to 8, in the second quadrants, quad=2, angle ranges from 9 to 16, in the third quadrants, quad=3, angle ranges from 17 to 24, in the fourth quadrants, and quad=4, angle ranges from 25 to 32.Suppose that(20)Mhoriz=M2,Mvert=M1,quad=1or3,Mhoriz=M1,Mvert=M2,quad=2or4,p=12×nquad-4,q=2×floor(4×Mhoriz),
where nquad-4 denotes the number of angle at each quadrant at scale 4; in this paper, nquad-4=8.The left vector of wedge wave is denoted byWleft=(a1,k+1)1×(nquad-4+1), where a1,k+1=round(k×p×q+1), k=0,1,2,…,nquad-4.The right vector of wedge wave is denoted byWright=(a1,k+1)1×(nquad-4), where a1,k+1=q+2-round(k×p×q+1), k=nquad-4,nquad-4-1,…,1.The combination wedge wave vector is denoted byW=[Wleft,Wright]1×(2×nquad-4+1).The endpoint vector of wedge wave is denoted byWend=(a1,k)1×(nquad-4), where a1,k=W(2×k)⋯k=1,2,…,nquad-4.The first midpoint vector of wedge wave is denoted byWmid1=(a1,k)1×(nquad-4-1), where a1,k=Wend(k)⋯k=1,2,…,nquad-4-1.The second midpoint vector of wedge wave is denoted byWmid2=(a1,k)1×(nquad-4-1), where a1,k=Wend(k)⋯k=2,3,…,nquad-4.The combination midpoint vector of wedge wave is denoted byWmid=(a1,k)1×(nquad-4-1), where a1,k=((Wmid1(k)+Wmid2(k))/2)⋯k=1,2,3,…,nquad-4-1.The first wedge wave endpoint along the vertical orientation is denoted by(21)rfirst_wedge_endpont=round(2×floor(4×Mvert)2×nquad-4+1).The length of the first wedge wave is denoted by(22)swedge=floor(4×Mvert)-floor(Mvert)+ceil(rfirst_wedge_endpont4).The width of the wedge wave is denoted byWwedge=Wend(2)+Wend(1)-1.The slope of the first wedge wave issslope=[floor(4×Mhoriz)+1-Wend(1)]/floor(4×Mvert).The left line vector is denoted bysleft_line=(a1,k)1×(swedge), where a1,k=round(2-Wend(1)+sslope×(k-1))⋯k=1,2,…,swedge.The first row coordinate isrfirst=floor(4×Mvert)+2-ceil((swedge+1)/2).The first column coordinate iscfirst=floor(4×Mhoriz)+2-ceil((Wwedge+1)/2).Condition column vector is denoted byVcol=(a1,k)1×Wwedge, where
(23)a1,k=sleft_line(k+1)+mod⁡((k-sleft_line(k+1)+cfirst),Wwedge),iiiiiiiiiiiiiiiiiiiiiiiiiiiik=0,1,2,…,Wwedge-1,mod⁡(x,y)={x-n×yn=floor(xy),y≠0,x,y=0.Thus, the discrete locating window of wedge wave is denoted byWdata=(an1,n2)swedge×Wwedge, where
(24)an1,n2={fhipass4′(n1,n2),Vcol(n2)>0,0,Vcol(n2)≤0,
where
(25)n1=1+mod⁡(k-rfirst,swedge),k=1,2,…,swedge,(26)n2=0.5×Vcol(k)+1+|Vcol(k)-1|,iiiiiiiiiiiiiiiiiiiiiiik=1,2,…,Wwedge.(6)
The discrete locating window of wedge waveWdata is filtered and rotated, hence generating matrix Wdata_2.Suppose that(27)ycorner=(a1,k)1×swedge,
where a1,k=k, k=1,2,3,…,swedge and
(28)xcorner=(a1,k)1×q,
where a1,k=k, k=1,2,3,…,q+1 and
(29)X=[xcornerxcornerxcorner⋮xcorner]swedge×q,YT=[ycornerycornerycorner⋮ycorner]q×swedge,Xwrap=(X(n1,n2))swedge×Wwedge,
where n1, n2 are calculated by (25) and (26), respectively. Consider
(30)Ywrap=(Y(n1,n2))swedge×Wwedge,
where n1, n2 are calculated by (25) and (26), respectively.The slope of right wedge wave issslope-right=(floor(4×Mhoriz)+1-Wmid(1))/floor(4×Mvert).The middle line matrixMmid-line-right=(an1,n2)swedge×Wwedge, where an1,n2=Wmid(1)+sslope-right×(Ywrap(n1,n2)-1).The right coordinate matrix isCcord-right=(an1,n2)swedge×Wwedge, where
(31)an1,n2=0.5+floor(4×Mvert)Wend(2)-Wend(1)×Xwrap(n1,n2)-Mmid-line-right(n1,n2)floor(4×Mvert)+1-Ywrap(n1,n2),c2=1×((2×(floor(4×Mvert)(rfirst-wedge-endpont-1))-1)-112×(floor(4×Mhoriz)/(Wend(1)-1))-1-1iiiiiiiii+1×(2×(floor(4×Mvert)rfirst-wedge-endpont-1)-1)-1)-1,c1=c22×((floor(4×Mhoriz))/(rfirst-wedge-endpont-1))-1.The corner coordinate matrixCcord-corner=(an1,n2)swedge×Wwedge, where
(32)an1,n2=c1+c2×[Xwrap(n1,n2)-1floor(4×Mhoriz)-Ywrap(n1,n2)-1floor(4×Mvert)],×(2-[Xwrap(n1,n2)-1floor(4×Mhoriz)-Ywrap(n1,n2)-1floor(4×Mvert)])-1.TheCcord-corner is wrapped, yielding the matrix Wl-left and Wr-right:
(33)Wl-left(n1,n2)={1,Ccord-coner(n1,n2)=0,e(1-1/(1-e(1-1/Ccord-corner(n1,n2)))),0<Ccord-corner(n1,n2)<1,0,Ccord-lcorner(n1,n2)=1,Wl-right(n1,n2)={1,Ccord-corner(n1,n2)=0,e(1-1/(1-e(1-1/(1-Ccord-corner(n1,n2))))),0<Ccord-corner(n1,n2)<1,0,Ccord-corner(n1,n2)=1.In the same way, theCcord-right is wrapped, yielding the matrix Wwl-left and Wwr-right.The discrete locating window of wedge waveWdata is filtered, yielding the matrix Wdata-tran=(an1,n2)swedge×Wwedge, where an1,n2=Wdata(n1,n2)×[Wl-left(n1,n2)×Wwr-right(n1,n2)].The matrixWdata-tran is rotated, yielding the matrix Wdata_2(34)Wdata_2=rot⁡90(Wdata-tran,-(quad-1)),
where rot⁡90(A,k) rotates matrix A counterclockwise by k×90∘ degrees.(7)
Inverse 2DFFT is applied toWdata_2, hence generating the Curvelet coefficient at scale 4 and angle 1, C4,1.(8)
Repeat(5), (6), and (7) in Step 3, in the same way of acquiring C4,1; Curvelet coefficients at scale 4 and angle from 2 to 8 are generated.Noted that at angle from 2 to 32, the left line vector is denoted bysleft_line=(a1,k)1×(swedge), where a1,k=round(Wend(lsub-1)+sslope×(k-1))⋯k=1,2,…,swedge. Consider
(35)lsub=2,3,4,…,8.(9)
The Curvelet coefficients at scale 4 and other three quadrants,C4,l, l=9,10,…,32 are acquired in the same way as that in the first quadrants.Finally, the Curvelet coefficients at scale 4,C4,l, l=1,2,…,32, are generated after Step 3.Step 4.
Repeat Step3, hence generating the Curvelet coefficients at scale 3, C3,l, l=1,2,…,32.Note that the discrete locating window of wedge wave at scale 3 can be calculated by(36)Wdata_3=(an1,n2)swedge-3×Wwedge-3,
where
(37)an1,n2={fhipass3′(n1,n2),Vcol3(n2)>0,0,Vcol_3(n2)≤0,swedge-3, Wwedge-3 is the length and width of the discrete locating window of wedge wave at scale 3, and Vcol_3 is condition vector at scale 3.Step 5.
Repeat Step3, hence generating the Curvelet coefficients at scale 2, C2,l, l=1,2,…,16.Note that the discrete locating window of wedge wave at scale 2 can be calculated by(38)Wdata_2=(an1,n2)swedge-2×Wwedge-2,
where
(39)an1,n2={fhipass2′(n1,n2),Vcol2(n2)>0,0,Vcol_2(n2)≤0,
and Vcol_2 is condition vector at scale 2.Step 6.
Inverse 2DFFT is applied to the low-pass signal at scale 2,flowpass2′(n1,n2), generating the Curvelet coefficient at scale 1 C1,1.The detailed structure of the Curvelet coefficients obtained by FDCT_WARPING is shown in Table1.Table 1
Structure of Curvelet transform coefficients.
Levels
Scales (j)
Orientation (l)
Matrix formCj,i
Coarse
1
1
21
×
21
Details
2
16
18
×
22
16
×
22
16
×
22
18
×
22
22
×
18
22
×
16
22
×
16
22
×
18
18
×
22
16
×
22
16
×
22
18
×
22
22
×
18
22
×
16
22
×
16
22
×
18
3
32
34×2232×2232×2232×2232×2232×2232×2234×2222×3422×3222×3222×3222×3222×3222×3222×3434×2232×2232×2232×2232×2232×2232×2234×2222×3422×3222×3222×3222×3222×3222×3222×34
4
32
67×4464×4364×4364×4464×4464×4364×4367×4444×6743×6443×6444×6444×6443×6443×6444×6767×4464×4364×4364×4464×4464×4364×4367×4444×6743×6443×6444×6444×6443×6443×6444×67
Fine
5
1
256
×
256


#### 2.3.2. Fingerprint Image Noise Filtration Technique

Noise always arises from the acquiring fingerprint images. The noise may result in the vagueness and many discontinuities of ridges (or valleys) in the image and thus affects accurate feature extraction and recognition. So, it is necessary and important to denoise in fingerprint images.The relationship of the Curvelet coefficients between the different scales is similar to the relationship of the wavelet coefficients; that is, there exists strong correlation between them.From Table1, there are 16 and 32 orientations at scale 2 and scale 3, respectively. Each Curvelet coefficient matrix is at scale 2 and each orientation corresponds to two adjacent matrices generated at scale 3. The ridges in a fingerprint image correspond to the Curvelet coefficients with large magnitude at scale 2. Each Curvelet coefficient matrix at scale 2 is decomposed into two Curvelet coefficient matrices at scale 3 and at two adjacent orientations. The corresponding two Curvelet coefficient matrices at scale 3 also have large magnitude, while the magnitude of the Curvelet coefficients corresponding to the noise dies out swiftly from scale 2 to scale 3. So, we use the direct spatial correlation of Curvelet coefficients at scale 2 and scale 3 to accurately distinguish ridges from noise. For scales 4 and 5, we adopt hard thresh method to filter the noise. Finally, we reconstruct all the Curvelet coefficients by the technique [17] and accomplish fingerprint image filtration.The proposed noise filtration technique has the following steps.Step 1.
Noise filtration of Curvelet coefficient matrices at scale 2 and scale 3, respectively.This section details the major steps of the proposed noise filtration algorithm of Curvelet coefficient matrices generated at scales 2 and 3.Assume each matrix to be at scale 2 and orientationl, C2,l, corresponds to two adjacent matrices generated at scale 3, C3,2×(l-1)+1 and C3,2×(l-1)+2, (l ranges from 1 to 16×2ceil((5-3)/2)). Let (r0,c0) be the size of C2,l. The sizes of C3,2×(l-1)+1 and C3,2×(l-1)+2 are (r1×c1) and (r2×c2), respectively. The matrices at scales 2 and 3 are filtered as follows.(1)
Decompose the Curvelet coefficients matrixC3,2×(l-1)+1 into two matrices A and B with the same size as C2,l, r0×c0. The elements of A are extracted from row 1 to r0 and column 1 to c0 of C3,2×(l-1)+1, and the elements of B are extracted from row r1-r0+1 to r1 and column c1-c0+1 to c1 of C3,2×(l-1)+1. Consider
(40)A=(an1,n2)r0×c0,
where an1,n2=C3,2×(l-1)+1(n1,n2), n1=1,2,3,…,r0, n2=1,2,3,…,c0, and
(41)B=(an1,n2)r0×c0,
where an1,n2=C3,2×(l-1)+1(n1,n2), n1=r1-r0+1, r1-r0+2,…,r1, n2=c1-c0+1, c1-c0+2,…,c1.(2)
Decompose the Curvelet coefficients matrixC3,2×(l-1)+2 into two matrices D and E with the size of r0×c0:
(42)D=(an1,n2)r0×c0,
where an1,n2=C3,2×(l-1)+2(n1,n2), n1=1,2,3,…,r0, n2=1,2,3,…,c0, and
(43)E=(an1,n2)r0×c0,
where an1,n2=C3,2×(l-1)+2(n1,n2), n1=r1-r0+1, r1-r0+2,…,r1, n2=c1-c0+1, c1-c0+2,…,c1.(3)
Calculate the four multiplication coefficient matrices(mk,k=1,2,34) between C2,l and the four matrices A, B, D, and E, respectively. Consider
(44)m1(n1,n2)=C2,l(n1,n2)×A(n1,n2),iin1=1,2,…,r0,n2=1,2,…,c0,m2(n1,n2)=C2,l(n1,n2)×B(n1,n2),iin1=1,2,…,r0,n2=1,2,…,c0,m3(n1,n2)=C2,l(n1,n2)×D(n1,n2),iin1=1,2,…,r0,n2=1,2,…,c0,m4(n1,n2)=C2,l(n1,n2)×E(n1,n2),iin1=1,2,…,r0,n2=1,2,…,c0.(4)
Filter the Curvelet coefficient matricesC3,2×(l-1)+1 and C3,2×(l-1)+2 by
(45)A′(n1,n2)={A(n1,n2),||m1(n1,n2)|-|m3(n1,n2)||>Ts,0,otherwise,D′(n1,n2)={D(n1,n2),||m1(n1,n2)|-|m3(n1,n2)||>Ts,0,otherwise,B′(n1,n2)={B(n1,n2),||m2(n1,n2)|-|m4(n1,n2)||>Ts,0,otherwise,E′(n1,n2)={E(n1,n2),||m2(n1,n2)|-|m4(n1,n2)||>Ts,0,otherwise,
where A′, D′, B′, and E′ are the Curvelet coefficient matrices at scale 3 after filtration, the operation |·| returns the complex modulus (magnitude) of the input, and Ts is the threshold. For example, if ||m1(n1,n2)|-|m3(n1,n2)||>Ts, we assume that the Curvelet coefficients correspond to the ridges of the image. Otherwise, the Curvelet coefficients correspond to the noise of the image, which are assigned to 0.(5)
When filtering the Curvelet coefficient matrixC2,l, if any of the filtered Curvelet coefficient matrices (A′, D′, B′,and E′) equal to Z, C2,l is considered as noise and assigned to Z. Where Z is a matrix with all elements are zero.(6)
repeat(1) to (5) with 16 times (the number of orientation of Curvelet coefficients at scale 2).After(1)–(5), all the Curvelet coefficients at scale 2 and scale 3 are filtered.Step 2.
Noise Filtration of Curvelet coefficient matrices at scale 4 and scale 5, respectively.The Curvelet coefficient matrices generated at scale 4 are filtered by(46)Cj,l′(i,j)={Cj,l(n1,n2),|Cj,l(n1,n2)|>thresh×Ej,l,0,otherwise,
where Cj,l′ are the filtered Curvelet coefficient matrices, |·| is the complex modulus operation, and thresh is the threshold; in this paper, thresh=1.5, and
(47)Ej,l=∑i=1n∑j=1m|Cj,l(i,j)|2n×m,
where (n,m) is the size of matrix Cj,l.The Curvelet coefficient matrices generated at scale 5 are filtered in the same way as the Curvelet coefficient matrices generated at scale 4. Note that at scale 5thresh=2.Step 3.
After the coefficients at scale 2, 3, 4, and 5 are filtered, we reconstruct the coefficients using the technique [16] and accomplish image noise filtration.T
s in (45) can be acquired by the statistics of difference of correlation coefficients in adjacent directions at the same scale. Finally, Ts=100 is selected by many experiments. Figure 1 shows the noise filtration results of five types of fingerprint image by proposed noise filtration algorithm.From Figure1  (x):(B) (x = a, b, c, d, e), we can see many discontinuities of ridges in the original image can be smoothed after filtering and the direction of ridge is well followed, which founds the good basis for accurate feature extraction and recognition. We demonstrate Curvelet coefficients at different scales of five types of filtered images in Figure 2.Curvelet coefficients of five filtered fingerprint classes. (a) Right loop (R), (b) left loop (L), (c) whorl (W), (d) arch (A), and (e) tented arch (T).
(a)
(b)
(c)
(d)
(e)As Figure2(a) to Figure 2(e) show, there are strong orientations in the Curvelet coefficients images. The white parts in the images represent partial edges of the ridge of fingerprint image in different orientations. Meanwhile, it means the significant Curvelet coefficients of images. The low-frequency (coarse scale) coefficients are stored at the center of the display. The Cartesian concentric coronae show the coefficients at different scales; the outer coronae correspond to higher frequencies. There are four strips associated with each corona, corresponding to the four cardinal points; these are further subdivided in angular panels. Each panel represents coefficients at a specified scale and along the orientation suggested by the position of the panel.


### 2.4. Fingerprint Feature Extraction

Haralick et al. [18] first proposed gray-level cooccurrence matrix (GLCM) for texture descriptions in the 1970s. It is still popular until today and widely used in various texture classifications [19–23], because of its good statistic performance. The GLCM is a second order statistics method which describes the spatial interrelationships of the grey tones in an image.GLCM contains elements that are counts of the number of pixel pairs, which are separated by certain distance and at some angular direction. Typically, the GLCM is calculated in a small window, which scans the whole image. The texture feature will be associated with each pixel.In our studies, GLCM is computed based on two parameters, which are the distance between the pixel paird and their angular relationship θ. d=1 and θ are quantized in four directions (0°, 45°, 90°, and 135°). For image I, defined square window N×N, brightness levels i and j, the nonnormalized GLCM pij are defined by
(48)pi,j,θ=∑x=1N∑y=1NC{(I(x,y)=i)(I(x±dθ0,y∓dθ1)=j)},
where C{·}=1 if the argument is true and C{·}=0, otherwise. The signs ± and ∓ in (10) mean that each pixel pair is counted twice: once forward and once backward in order to make the GLCM diagonally symmetric. For each direction, θ0 and θ1 are shown in Table 2.Table 2
Direction values.
θ
0°
45°
90°
135°
θ
0
0
1
1
1
θ
1
1
1
0
−1The procedures of feature extraction are as follows.Step 1.
Scale the grayscale values in Curvelet transform coefficients into 8 levers and compute the GLCMs of Curvelet coefficients at scale 1C1,1 and calculate 16 texture features based on 4 GLCMs:(1)
Angular second moment (ASM)(49)f1=∑i=0G-1∑j=0G-1p(i,j)2.(2)
Contrast (CON)(50)f2=∑n=0G-1n2{∑i=0G-1∑j=0G-1p(i,j)2},
where |i-j|=n.(3)
Correlation (COR)(51)f3=∑i=0G-1∑j=0G-1(ij)p(i,j)-μ1μ2σ12σ22,
where
(52)μ1=∑i=0G-1i∑j=0G-1p(i,j),μ2=∑i=0G-1j∑j=0G-1p(i,j),σ12=∑i=0G-1(i-μ1)2∑j=0G-1p(i,j),σ22=∑i=0G-1(j-μ2)2∑i=0G-1p(i,j).(4)
Entropy (ENT)(53)f4=-∑i=0G-1∑j=0G-1p(i,j)log⁡⁡p(i,j).Step 2.
Calculate averagedl1 -norm of Curvelet coefficients in 8 directions at the second scale C2,l and acquire 8 texture features according to (51). Consider
(54)El=1m1×m2∑im1∑jm2|C2,l(i,j)|,
where, (m1,m2) is the size of the matrix C2,l, and l=1,2,3,4,5,…,16.Step 3.
Calculate averagedl1-norm of Curvelet coefficients in 16 directions at the third scale C3,l and acquire 16 texture features according to (54).Step 4.
Calculate averagedl1-norm of Curvelet coefficients in 16 directions at the fourth scale C4,l and acquire 16 texture features according to (54).Step 5.
Calculate averagedl1-norm of Curvelet coefficients at the fifth scale C5,1 and acquire 1 texture feature.Note that in Step2, Step 3, and Step 4, we only calculate the averaged l1-norm of Curvelet coefficients in even directions to assure the classification accuracy and reduce the recognition time. So, a feature vector containing 57 components for each image can be extracted.


## 2.1. Fingerprint Alignments

Considering the translation and rotation between template images and probe images, this paper adopted the algorithm in [14] to accomplish the fingerprint image registration. The algorithm used the reference points of the central area to calculate the parameters of translation and rotation, which is much more general when there are no cores in the fingerprint images.


## 2.2. Fast Discrete Curvelet Transform (FDCT)

Curvelets were proposed by Candese and Donoho [15], constituting a family of frames that are designed to represent the edges and other singularities along curves. Conceptually, the Curvelet transform is a multiscale pyramid with many orientations and positions at each length scale and needle-shaped elements at fine scale. This pyramid is nonstandard, however. Indeed, Curvelets have useful geometric features that set them apart from wavelets and the likes. For instance, Curvelets present highly anisotropic behavior as it has both variablelength andwidth. At fine scale, anisotropy increases with decreasing scale, in keeping with power law.In 2006, Candès et al. proposed two fast discrete Curvelet transforms (FDCT) [16]. The first one is based on unequally spaced fast Fourier transforms (USFFT) [16], and the other is based on the wrapping of specially selected Fourier samples (FDCT_WARPING) [16]. Curvelets by warping have been used for this work, because this is the fastest Curvelet transform currently available [16].After Curvelet transform, several groups of Curvelet coefficients are generated at different scales and angles. Curvelet coefficients at scalej and angle l are represented by a matrix Cj,l, and scale j is from finest to coarsest scale, and angle l starts at the top-left corner and increases clockwise.Suppose thatf(t1,t2), 1≤t1≤N1, 1≤t2≤N2 denotes original image and f^[n1,n2] denotes 2D discrete Fourier transform; N1, N2 is the size of original image.The implementation of FDCT_WARPING is as follows.Step 1.
2D FFT (fast Fourier transform) is applied onf(t1,t2) to obtain Fourier samples f^[n1,n2].Step 2.
Resamplef^[n1,n2] at each pair of scale and direction j, l in frequency domain, yielding the new sampling function:
(1)f^[n1,n2-n1tan⁡θl],(n1,n2)∈Pj,
where Pj={(n1,n2),n1,0≤n1<n1,0+L1,j,n2,0≤n2<n2,0+L2,j} and n1,0 and n2,0 are two initial positions of the window function u~j,l[n1,n2].
L
1
,
j and L2,j are relevant parameters of 2j and 2j/2, respectively, and they are length and width components of window function support interval.Step 3.
Multiplication of the new sampling functionf^[n1,n2-n1tan⁡θl] with window function u~j[n1,n2], and the result is [16]
(2)f~j,l[n1,n2]=f^[n1,n2-n1tan⁡θl]u~j,l[n1,n2],
where
(3)u~j,l[n1,n2]=wj(w1,w2)vj(sθl·(2⌊j/2⌋w2)w1),wj(w1,w2)=ϕj+12(w2)-ϕj2(w2),ϕj(w1,w2)=ϕ(2-jw1)ϕ(2-jw2),sθl=[10-tan⁡θl1],tan⁡θl=l×2⌊-j/2⌋,l=-2⌊-j/2⌋,…,2⌊-j/2⌋-1.Step 4.
Apply the inverse 2D FFT to eachf~j,l, hence collecting the discrete coefficients Cj,l.


## 2.3. Fingerprint Image FDCT and Noise Filtration Technique

Curvelet transform describes a signal by the power at each scale, angle, and position. Curvelets have variable length in addition to variable width. Curvelet transform has improved directional capability and better ability to represent edges and other singularities along curves compared to other multiscale transforms, for example, wavelet transform. Image like fingerprints often have two nearby regions (ridges and valleys) that differ in pixel values. These variations in pixel values between two consecutive regions are likely to form such “edges” and this edge information is eventually captured by digital Curvelet transform.


### 2.3.1. Acquisition of Curvelet Coefficients

In this paper, fingerprint images are from NIST-4 databases. Firstly, the size of all the images is normalized to 256 × 256 pixels. The proposed algorithm is implemented by using MATLAB 7.5 programming language and is executed under Windows XP Professional O.S. on a PC with AMD Dual-Core CPU E-350 at 1.28 GHz. The original image is decomposed by FDCT_WARPING [16].Suppose thatf(t1,t2), 1≤t1≤N1, 1≤t2≤N2 denotes original fingerprint image and f^[n1,n2] denotes 2D discrete Fourier transform; N1, N2 is the size of original fingerprint image.The number of scales can be calculated by(4)Nscales=ceil(log⁡2(min⁡(N1,N2))-3),
where min⁡(N1,N2) returns the minimum of N1 and N2 and ceil(·) rounds the input to the nearest integers greater than or equal to input.The number of orientation at scale2,3,…,Nscales-1, is calculated by
(5)lj=16×2ceil((Nscales-i)/2),
where i=Nscales, j=2; i=Nscales-1, j=3;…; i=3, and j=Nscales-1.Noted that if FDCT_WARPING chooses the Curvelets for the coefficients at the finest levelNscales, the number of orientation at scale Nscales can be determined by (2). On the other hand, when choosing the wavelets for the coefficients at the finest level Nscales, there is only one angle at the finest level Nscales. In this paper, we adopt the wavelets for the coefficients at the finest level Nscales. As a result, there is only one angle at the finest level Nscales.For scalej=2,3,…,(Nscales-1), all the Curvelet coefficients are divided into the four quadrants. The quadrant label of Curvelet coefficients is denoted by quad, and four quadrants are denoted by quad=1,2,3,4, respectively. At each quadrant, Curvelet coefficients are further subdivided in angular panels. The number of angular panels at each quadrant of each scale j, denoted by nquad-j, can be calculated as follows:
(6)nquad-j=4×2ceil((Nscales-i)/2),
where i=Nscales, j=2; i=Nscales-1, j=3;…; i=3, and j=Nscales-1.In this paper, according to (4), we can get the number of scales Nscales=5. According to (5), the number of angle at scale 4 is 32, at scale 3 is 32, and at scale 2 is 16. At scale 4, the number of angular panels of each quadrant is 8. At scale 3, the number of angular panels of each quadrant is 8. At scale 2, the number of angular panels of each quadrant is 4. After decomposition, the original image was divided into three levels: coarse, detail, and fine. The low-frequency coefficients were assigned to coarse. The high-frequency coefficients were assigned to fine. The middle-frequency coefficients were assigned to detail. According to FDCT_WARPING [16], the scale j is from finest to coarsest scale and angle l starts at the top-left corner and increases clockwise.The acquisition of Curvelet coefficients is as follows.Step 1.
2D FFT (fast Fourier transform) is applied onf(t1,t2) to obtain Fourier samples f^[n1,n2].Step 2.
Acquire the Curvelet coefficients at scale 5, denoted by matrixC5,1.Suppose that(7)M1=N16,M2=N26,lNscales-1=floor(2×M1)-floor(M1)-1,lNscales-2=floor(2×M2)-floor(M2)-1.
In this paper, floor(·) rounds the input to the nearest integers less than or equal to the input.(1)
Construct the right and left windows along the horizontal direction, denoted by row vectorWr-1 and Wl-1, respectively. Consider
(8)Wr-1(i)={1,i=0,e(1-1/(1-e(1-1/i))),i=1lNscales-1,2lNscales-1,…,lNscales-1-1lNscales-1,0,i=1,Wl-1(i)={0,i=0,e(1-1/(1-e(1-1/(1-i)))),i=1lNscales-1,2lNscales-1,…,lNscales-1-1lNscales-1,1,i=1.(2)
Construct the right and left windows along the vertical direction, denoted by row vectorWr-2 and Wl-2, respectively. Consider
(9)Wr-2(i)={1,i=0,e(1-1/(1-e(1-1/i))),i=1lNscales-2,2lNscales-2,…,lNscales-2-1lNscales-2,0,i=1,(10)Wl-2(i)={0,i=0,e(1-1/(1-e(1-1/(1-i)))),i=1lNscales-2,2lNscales-2,…,lNscales-2-1lNscales-2,1,i=1.Wr-1, Wl-1, Wr-2, and Wl-2 are normalized by
(11)Wr-1(i)=Wr-1(i)[Wr-1(i)]2+[Wl-1(i)]2,Wl-1(i)=Wl-1(i)[Wr-1(i)]2+[Wl-1(i)]2,Wr-2(i)=Wr-2(i)[Wr-2(i)]2+[Wl-2(i)]2,Wl-2(i)=Wl-2(i)[Wr-2(i)]2+[Wl-2(i)]2.(3)
Construct the two sub-low-pass filters, denoted by row vectorflowpasssub1 and flowpasssub2, respectively. Consider
(12)flowpasssub1=[Wl-1,1,1⋯1︸p1,Wr-1]1×[2×floor(2×M1)+1],flowpasssub2=[Wl-2,1,1⋯1︸p2,Wr-2]1×[2×floor(2×M2)+1],
where p1=2×floor(M1)+1, p2=2×floor(M2)+1.(4)
Construct a low-pass filter at scale 5, denoted by matrix(flowpass_5)[2×floor(2×M1)+1]×[2×floor(2×M2)+1], and
(13)flowpass_5=(flowpasssub1)T×flowpasssub2,
where (·)T is the transpose vector or matrix of the input vector or matrix.(5)
Construct a high-pass filter at scale 5, denoted by matrixfhipass_5, which has the same size as flowpass_5. Consider
(14)fhipass_5=1-(flowpass_5)2.(6)
f^[n1,n2] is filtered by fhipass_5, hence generating the filtered high-pass signal at scale 5 fhipass_5′, which has the same size of N1×N2 as f^[n1,n2]. Consider
(15)fhipass_5′(n1,n2)={f^(n1,n2)×fhipass_5(n1,n2),a≤n1≤b,c≤n2≤d,f^(n1,n2),others,
where the filter at scale 5 has the following range:
(16)a=-floor(2×M1)+ceil((N1+1)2),b=floor(2×M1)+ceil((N1+1)2),c=-floor(2×M2)+ceil((N2+1)2),d=-floor(2×M2)+ceil((N2+1)2).(7)
Inverse 2DFFT (inverse fast Fourier transform) is applied tofhipass_5′, hence generating the discrete Curvelet coefficients at scale 5, C5,1.(8)
f^[n1,n2] is filtered by flowpass_5, hence generating the filtered low-pass signal at scale 5, (flowpass_5′)[2×floor(2×M1)+1]×[2×floor(2×M2)+1] and
(17)flowpass5′(n1,n2)=f^(n1,n2)×flowpass5(n1,n2),iiiiiiiiiiiiiiiiiiiiiiiiiiiiia≤n1≤b,c≤n2≤d.Step 3.
Acquire the Curvelet coefficients at scale 4 and angle 1 to angle 32,C4,l, l=1,2,…,32.Firstly, we acquire the Curvelet coefficients at scale 4 and angle 1,C4,1.Suppose that(18)M1=N1(6×2),M2=N2(6×2).The filter at scale 4 has the following range:(19)aNscales-1=-floor(2×M1)+floor(4×M1)+1,bNscales-1=floor(2×M1)+floor(4×M1)+1,cNscales-1=-floor(2×M2)+floor(4×M2)+1,dNscales-1=floor(2×M2)+floor(4×M2)+1.(1)
Construct a low-pass filter at scale 4 and angle 1 in the same way as at scale 5,(flowpass_4)[2×floor(2×M1)+1]×[2×floor(2×M2)+1].(2)
Construct a high-pass filter at scale 4 and angle 1 in the same way as at scale 5,(fhipass_4)[2×floor(2×M1)+1]×[2×floor(2×M2)+1].(3)
flowpass_5′ is filtered by flowpass_4, hence generating the filtered low-pass signal at scale 4 (flowpass_4′)[2×floor(2×M1)+1]×[2×floor(2×M2)+1].(4)
flowpass_5′ is filtered by fhipass_4, hence generating the filtered high-pass signal at scale 4 fhipass_4′, which has the same size as that of flowpass_5′.(5)
Determine the discrete locating window of wedge wave at scale 4 and angle 1.The Curvelet coefficients at scale 4 are divided into the four quadrants. The quadrant label of Curvelet coefficients is denoted byquad, and four quadrants are denoted by quad=1,2,3,4, respectively. Each quadrant has 8 angles. In the first quadrant, quad=1, angle ranges from 1 to 8, in the second quadrants, quad=2, angle ranges from 9 to 16, in the third quadrants, quad=3, angle ranges from 17 to 24, in the fourth quadrants, and quad=4, angle ranges from 25 to 32.Suppose that(20)Mhoriz=M2,Mvert=M1,quad=1or3,Mhoriz=M1,Mvert=M2,quad=2or4,p=12×nquad-4,q=2×floor(4×Mhoriz),
where nquad-4 denotes the number of angle at each quadrant at scale 4; in this paper, nquad-4=8.The left vector of wedge wave is denoted byWleft=(a1,k+1)1×(nquad-4+1), where a1,k+1=round(k×p×q+1), k=0,1,2,…,nquad-4.The right vector of wedge wave is denoted byWright=(a1,k+1)1×(nquad-4), where a1,k+1=q+2-round(k×p×q+1), k=nquad-4,nquad-4-1,…,1.The combination wedge wave vector is denoted byW=[Wleft,Wright]1×(2×nquad-4+1).The endpoint vector of wedge wave is denoted byWend=(a1,k)1×(nquad-4), where a1,k=W(2×k)⋯k=1,2,…,nquad-4.The first midpoint vector of wedge wave is denoted byWmid1=(a1,k)1×(nquad-4-1), where a1,k=Wend(k)⋯k=1,2,…,nquad-4-1.The second midpoint vector of wedge wave is denoted byWmid2=(a1,k)1×(nquad-4-1), where a1,k=Wend(k)⋯k=2,3,…,nquad-4.The combination midpoint vector of wedge wave is denoted byWmid=(a1,k)1×(nquad-4-1), where a1,k=((Wmid1(k)+Wmid2(k))/2)⋯k=1,2,3,…,nquad-4-1.The first wedge wave endpoint along the vertical orientation is denoted by(21)rfirst_wedge_endpont=round(2×floor(4×Mvert)2×nquad-4+1).The length of the first wedge wave is denoted by(22)swedge=floor(4×Mvert)-floor(Mvert)+ceil(rfirst_wedge_endpont4).The width of the wedge wave is denoted byWwedge=Wend(2)+Wend(1)-1.The slope of the first wedge wave issslope=[floor(4×Mhoriz)+1-Wend(1)]/floor(4×Mvert).The left line vector is denoted bysleft_line=(a1,k)1×(swedge), where a1,k=round(2-Wend(1)+sslope×(k-1))⋯k=1,2,…,swedge.The first row coordinate isrfirst=floor(4×Mvert)+2-ceil((swedge+1)/2).The first column coordinate iscfirst=floor(4×Mhoriz)+2-ceil((Wwedge+1)/2).Condition column vector is denoted byVcol=(a1,k)1×Wwedge, where
(23)a1,k=sleft_line(k+1)+mod⁡((k-sleft_line(k+1)+cfirst),Wwedge),iiiiiiiiiiiiiiiiiiiiiiiiiiiik=0,1,2,…,Wwedge-1,mod⁡(x,y)={x-n×yn=floor(xy),y≠0,x,y=0.Thus, the discrete locating window of wedge wave is denoted byWdata=(an1,n2)swedge×Wwedge, where
(24)an1,n2={fhipass4′(n1,n2),Vcol(n2)>0,0,Vcol(n2)≤0,
where
(25)n1=1+mod⁡(k-rfirst,swedge),k=1,2,…,swedge,(26)n2=0.5×Vcol(k)+1+|Vcol(k)-1|,iiiiiiiiiiiiiiiiiiiiiiik=1,2,…,Wwedge.(6)
The discrete locating window of wedge waveWdata is filtered and rotated, hence generating matrix Wdata_2.Suppose that(27)ycorner=(a1,k)1×swedge,
where a1,k=k, k=1,2,3,…,swedge and
(28)xcorner=(a1,k)1×q,
where a1,k=k, k=1,2,3,…,q+1 and
(29)X=[xcornerxcornerxcorner⋮xcorner]swedge×q,YT=[ycornerycornerycorner⋮ycorner]q×swedge,Xwrap=(X(n1,n2))swedge×Wwedge,
where n1, n2 are calculated by (25) and (26), respectively. Consider
(30)Ywrap=(Y(n1,n2))swedge×Wwedge,
where n1, n2 are calculated by (25) and (26), respectively.The slope of right wedge wave issslope-right=(floor(4×Mhoriz)+1-Wmid(1))/floor(4×Mvert).The middle line matrixMmid-line-right=(an1,n2)swedge×Wwedge, where an1,n2=Wmid(1)+sslope-right×(Ywrap(n1,n2)-1).The right coordinate matrix isCcord-right=(an1,n2)swedge×Wwedge, where
(31)an1,n2=0.5+floor(4×Mvert)Wend(2)-Wend(1)×Xwrap(n1,n2)-Mmid-line-right(n1,n2)floor(4×Mvert)+1-Ywrap(n1,n2),c2=1×((2×(floor(4×Mvert)(rfirst-wedge-endpont-1))-1)-112×(floor(4×Mhoriz)/(Wend(1)-1))-1-1iiiiiiiii+1×(2×(floor(4×Mvert)rfirst-wedge-endpont-1)-1)-1)-1,c1=c22×((floor(4×Mhoriz))/(rfirst-wedge-endpont-1))-1.The corner coordinate matrixCcord-corner=(an1,n2)swedge×Wwedge, where
(32)an1,n2=c1+c2×[Xwrap(n1,n2)-1floor(4×Mhoriz)-Ywrap(n1,n2)-1floor(4×Mvert)],×(2-[Xwrap(n1,n2)-1floor(4×Mhoriz)-Ywrap(n1,n2)-1floor(4×Mvert)])-1.TheCcord-corner is wrapped, yielding the matrix Wl-left and Wr-right:
(33)Wl-left(n1,n2)={1,Ccord-coner(n1,n2)=0,e(1-1/(1-e(1-1/Ccord-corner(n1,n2)))),0<Ccord-corner(n1,n2)<1,0,Ccord-lcorner(n1,n2)=1,Wl-right(n1,n2)={1,Ccord-corner(n1,n2)=0,e(1-1/(1-e(1-1/(1-Ccord-corner(n1,n2))))),0<Ccord-corner(n1,n2)<1,0,Ccord-corner(n1,n2)=1.In the same way, theCcord-right is wrapped, yielding the matrix Wwl-left and Wwr-right.The discrete locating window of wedge waveWdata is filtered, yielding the matrix Wdata-tran=(an1,n2)swedge×Wwedge, where an1,n2=Wdata(n1,n2)×[Wl-left(n1,n2)×Wwr-right(n1,n2)].The matrixWdata-tran is rotated, yielding the matrix Wdata_2(34)Wdata_2=rot⁡90(Wdata-tran,-(quad-1)),
where rot⁡90(A,k) rotates matrix A counterclockwise by k×90∘ degrees.(7)
Inverse 2DFFT is applied toWdata_2, hence generating the Curvelet coefficient at scale 4 and angle 1, C4,1.(8)
Repeat(5), (6), and (7) in Step 3, in the same way of acquiring C4,1; Curvelet coefficients at scale 4 and angle from 2 to 8 are generated.Noted that at angle from 2 to 32, the left line vector is denoted bysleft_line=(a1,k)1×(swedge), where a1,k=round(Wend(lsub-1)+sslope×(k-1))⋯k=1,2,…,swedge. Consider
(35)lsub=2,3,4,…,8.(9)
The Curvelet coefficients at scale 4 and other three quadrants,C4,l, l=9,10,…,32 are acquired in the same way as that in the first quadrants.Finally, the Curvelet coefficients at scale 4,C4,l, l=1,2,…,32, are generated after Step 3.Step 4.
Repeat Step3, hence generating the Curvelet coefficients at scale 3, C3,l, l=1,2,…,32.Note that the discrete locating window of wedge wave at scale 3 can be calculated by(36)Wdata_3=(an1,n2)swedge-3×Wwedge-3,
where
(37)an1,n2={fhipass3′(n1,n2),Vcol3(n2)>0,0,Vcol_3(n2)≤0,swedge-3, Wwedge-3 is the length and width of the discrete locating window of wedge wave at scale 3, and Vcol_3 is condition vector at scale 3.Step 5.
Repeat Step3, hence generating the Curvelet coefficients at scale 2, C2,l, l=1,2,…,16.Note that the discrete locating window of wedge wave at scale 2 can be calculated by(38)Wdata_2=(an1,n2)swedge-2×Wwedge-2,
where
(39)an1,n2={fhipass2′(n1,n2),Vcol2(n2)>0,0,Vcol_2(n2)≤0,
and Vcol_2 is condition vector at scale 2.Step 6.
Inverse 2DFFT is applied to the low-pass signal at scale 2,flowpass2′(n1,n2), generating the Curvelet coefficient at scale 1 C1,1.The detailed structure of the Curvelet coefficients obtained by FDCT_WARPING is shown in Table1.Table 1
Structure of Curvelet transform coefficients.
Levels
Scales (j)
Orientation (l)
Matrix formCj,i
Coarse
1
1
21
×
21
Details
2
16
18
×
22
16
×
22
16
×
22
18
×
22
22
×
18
22
×
16
22
×
16
22
×
18
18
×
22
16
×
22
16
×
22
18
×
22
22
×
18
22
×
16
22
×
16
22
×
18
3
32
34×2232×2232×2232×2232×2232×2232×2234×2222×3422×3222×3222×3222×3222×3222×3222×3434×2232×2232×2232×2232×2232×2232×2234×2222×3422×3222×3222×3222×3222×3222×3222×34
4
32
67×4464×4364×4364×4464×4464×4364×4367×4444×6743×6443×6444×6444×6443×6443×6444×6767×4464×4364×4364×4464×4464×4364×4367×4444×6743×6443×6444×6444×6443×6443×6444×67
Fine
5
1
256
×
256


### 2.3.2. Fingerprint Image Noise Filtration Technique

Noise always arises from the acquiring fingerprint images. The noise may result in the vagueness and many discontinuities of ridges (or valleys) in the image and thus affects accurate feature extraction and recognition. So, it is necessary and important to denoise in fingerprint images.The relationship of the Curvelet coefficients between the different scales is similar to the relationship of the wavelet coefficients; that is, there exists strong correlation between them.From Table1, there are 16 and 32 orientations at scale 2 and scale 3, respectively. Each Curvelet coefficient matrix is at scale 2 and each orientation corresponds to two adjacent matrices generated at scale 3. The ridges in a fingerprint image correspond to the Curvelet coefficients with large magnitude at scale 2. Each Curvelet coefficient matrix at scale 2 is decomposed into two Curvelet coefficient matrices at scale 3 and at two adjacent orientations. The corresponding two Curvelet coefficient matrices at scale 3 also have large magnitude, while the magnitude of the Curvelet coefficients corresponding to the noise dies out swiftly from scale 2 to scale 3. So, we use the direct spatial correlation of Curvelet coefficients at scale 2 and scale 3 to accurately distinguish ridges from noise. For scales 4 and 5, we adopt hard thresh method to filter the noise. Finally, we reconstruct all the Curvelet coefficients by the technique [17] and accomplish fingerprint image filtration.The proposed noise filtration technique has the following steps.Step 1.
Noise filtration of Curvelet coefficient matrices at scale 2 and scale 3, respectively.This section details the major steps of the proposed noise filtration algorithm of Curvelet coefficient matrices generated at scales 2 and 3.Assume each matrix to be at scale 2 and orientationl, C2,l, corresponds to two adjacent matrices generated at scale 3, C3,2×(l-1)+1 and C3,2×(l-1)+2, (l ranges from 1 to 16×2ceil((5-3)/2)). Let (r0,c0) be the size of C2,l. The sizes of C3,2×(l-1)+1 and C3,2×(l-1)+2 are (r1×c1) and (r2×c2), respectively. The matrices at scales 2 and 3 are filtered as follows.(1)
Decompose the Curvelet coefficients matrixC3,2×(l-1)+1 into two matrices A and B with the same size as C2,l, r0×c0. The elements of A are extracted from row 1 to r0 and column 1 to c0 of C3,2×(l-1)+1, and the elements of B are extracted from row r1-r0+1 to r1 and column c1-c0+1 to c1 of C3,2×(l-1)+1. Consider
(40)A=(an1,n2)r0×c0,
where an1,n2=C3,2×(l-1)+1(n1,n2), n1=1,2,3,…,r0, n2=1,2,3,…,c0, and
(41)B=(an1,n2)r0×c0,
where an1,n2=C3,2×(l-1)+1(n1,n2), n1=r1-r0+1, r1-r0+2,…,r1, n2=c1-c0+1, c1-c0+2,…,c1.(2)
Decompose the Curvelet coefficients matrixC3,2×(l-1)+2 into two matrices D and E with the size of r0×c0:
(42)D=(an1,n2)r0×c0,
where an1,n2=C3,2×(l-1)+2(n1,n2), n1=1,2,3,…,r0, n2=1,2,3,…,c0, and
(43)E=(an1,n2)r0×c0,
where an1,n2=C3,2×(l-1)+2(n1,n2), n1=r1-r0+1, r1-r0+2,…,r1, n2=c1-c0+1, c1-c0+2,…,c1.(3)
Calculate the four multiplication coefficient matrices(mk,k=1,2,34) between C2,l and the four matrices A, B, D, and E, respectively. Consider
(44)m1(n1,n2)=C2,l(n1,n2)×A(n1,n2),iin1=1,2,…,r0,n2=1,2,…,c0,m2(n1,n2)=C2,l(n1,n2)×B(n1,n2),iin1=1,2,…,r0,n2=1,2,…,c0,m3(n1,n2)=C2,l(n1,n2)×D(n1,n2),iin1=1,2,…,r0,n2=1,2,…,c0,m4(n1,n2)=C2,l(n1,n2)×E(n1,n2),iin1=1,2,…,r0,n2=1,2,…,c0.(4)
Filter the Curvelet coefficient matricesC3,2×(l-1)+1 and C3,2×(l-1)+2 by
(45)A′(n1,n2)={A(n1,n2),||m1(n1,n2)|-|m3(n1,n2)||>Ts,0,otherwise,D′(n1,n2)={D(n1,n2),||m1(n1,n2)|-|m3(n1,n2)||>Ts,0,otherwise,B′(n1,n2)={B(n1,n2),||m2(n1,n2)|-|m4(n1,n2)||>Ts,0,otherwise,E′(n1,n2)={E(n1,n2),||m2(n1,n2)|-|m4(n1,n2)||>Ts,0,otherwise,
where A′, D′, B′, and E′ are the Curvelet coefficient matrices at scale 3 after filtration, the operation |·| returns the complex modulus (magnitude) of the input, and Ts is the threshold. For example, if ||m1(n1,n2)|-|m3(n1,n2)||>Ts, we assume that the Curvelet coefficients correspond to the ridges of the image. Otherwise, the Curvelet coefficients correspond to the noise of the image, which are assigned to 0.(5)
When filtering the Curvelet coefficient matrixC2,l, if any of the filtered Curvelet coefficient matrices (A′, D′, B′,and E′) equal to Z, C2,l is considered as noise and assigned to Z. Where Z is a matrix with all elements are zero.(6)
repeat(1) to (5) with 16 times (the number of orientation of Curvelet coefficients at scale 2).After(1)–(5), all the Curvelet coefficients at scale 2 and scale 3 are filtered.Step 2.
Noise Filtration of Curvelet coefficient matrices at scale 4 and scale 5, respectively.The Curvelet coefficient matrices generated at scale 4 are filtered by(46)Cj,l′(i,j)={Cj,l(n1,n2),|Cj,l(n1,n2)|>thresh×Ej,l,0,otherwise,
where Cj,l′ are the filtered Curvelet coefficient matrices, |·| is the complex modulus operation, and thresh is the threshold; in this paper, thresh=1.5, and
(47)Ej,l=∑i=1n∑j=1m|Cj,l(i,j)|2n×m,
where (n,m) is the size of matrix Cj,l.The Curvelet coefficient matrices generated at scale 5 are filtered in the same way as the Curvelet coefficient matrices generated at scale 4. Note that at scale 5thresh=2.Step 3.
After the coefficients at scale 2, 3, 4, and 5 are filtered, we reconstruct the coefficients using the technique [16] and accomplish image noise filtration.T
s in (45) can be acquired by the statistics of difference of correlation coefficients in adjacent directions at the same scale. Finally, Ts=100 is selected by many experiments. Figure 1 shows the noise filtration results of five types of fingerprint image by proposed noise filtration algorithm.From Figure1  (x):(B) (x = a, b, c, d, e), we can see many discontinuities of ridges in the original image can be smoothed after filtering and the direction of ridge is well followed, which founds the good basis for accurate feature extraction and recognition. We demonstrate Curvelet coefficients at different scales of five types of filtered images in Figure 2.Curvelet coefficients of five filtered fingerprint classes. (a) Right loop (R), (b) left loop (L), (c) whorl (W), (d) arch (A), and (e) tented arch (T).
(a)
(b)
(c)
(d)
(e)As Figure2(a) to Figure 2(e) show, there are strong orientations in the Curvelet coefficients images. The white parts in the images represent partial edges of the ridge of fingerprint image in different orientations. Meanwhile, it means the significant Curvelet coefficients of images. The low-frequency (coarse scale) coefficients are stored at the center of the display. The Cartesian concentric coronae show the coefficients at different scales; the outer coronae correspond to higher frequencies. There are four strips associated with each corona, corresponding to the four cardinal points; these are further subdivided in angular panels. Each panel represents coefficients at a specified scale and along the orientation suggested by the position of the panel.


## 2.3.1. Acquisition of Curvelet Coefficients

In this paper, fingerprint images are from NIST-4 databases. Firstly, the size of all the images is normalized to 256 × 256 pixels. The proposed algorithm is implemented by using MATLAB 7.5 programming language and is executed under Windows XP Professional O.S. on a PC with AMD Dual-Core CPU E-350 at 1.28 GHz. The original image is decomposed by FDCT_WARPING [16].Suppose thatf(t1,t2), 1≤t1≤N1, 1≤t2≤N2 denotes original fingerprint image and f^[n1,n2] denotes 2D discrete Fourier transform; N1, N2 is the size of original fingerprint image.The number of scales can be calculated by(4)Nscales=ceil(log⁡2(min⁡(N1,N2))-3),
where min⁡(N1,N2) returns the minimum of N1 and N2 and ceil(·) rounds the input to the nearest integers greater than or equal to input.The number of orientation at scale2,3,…,Nscales-1, is calculated by
(5)lj=16×2ceil((Nscales-i)/2),
where i=Nscales, j=2; i=Nscales-1, j=3;…; i=3, and j=Nscales-1.Noted that if FDCT_WARPING chooses the Curvelets for the coefficients at the finest levelNscales, the number of orientation at scale Nscales can be determined by (2). On the other hand, when choosing the wavelets for the coefficients at the finest level Nscales, there is only one angle at the finest level Nscales. In this paper, we adopt the wavelets for the coefficients at the finest level Nscales. As a result, there is only one angle at the finest level Nscales.For scalej=2,3,…,(Nscales-1), all the Curvelet coefficients are divided into the four quadrants. The quadrant label of Curvelet coefficients is denoted by quad, and four quadrants are denoted by quad=1,2,3,4, respectively. At each quadrant, Curvelet coefficients are further subdivided in angular panels. The number of angular panels at each quadrant of each scale j, denoted by nquad-j, can be calculated as follows:
(6)nquad-j=4×2ceil((Nscales-i)/2),
where i=Nscales, j=2; i=Nscales-1, j=3;…; i=3, and j=Nscales-1.In this paper, according to (4), we can get the number of scales Nscales=5. According to (5), the number of angle at scale 4 is 32, at scale 3 is 32, and at scale 2 is 16. At scale 4, the number of angular panels of each quadrant is 8. At scale 3, the number of angular panels of each quadrant is 8. At scale 2, the number of angular panels of each quadrant is 4. After decomposition, the original image was divided into three levels: coarse, detail, and fine. The low-frequency coefficients were assigned to coarse. The high-frequency coefficients were assigned to fine. The middle-frequency coefficients were assigned to detail. According to FDCT_WARPING [16], the scale j is from finest to coarsest scale and angle l starts at the top-left corner and increases clockwise.The acquisition of Curvelet coefficients is as follows.Step 1.
2D FFT (fast Fourier transform) is applied onf(t1,t2) to obtain Fourier samples f^[n1,n2].Step 2.
Acquire the Curvelet coefficients at scale 5, denoted by matrixC5,1.Suppose that(7)M1=N16,M2=N26,lNscales-1=floor(2×M1)-floor(M1)-1,lNscales-2=floor(2×M2)-floor(M2)-1.
In this paper, floor(·) rounds the input to the nearest integers less than or equal to the input.(1)
Construct the right and left windows along the horizontal direction, denoted by row vectorWr-1 and Wl-1, respectively. Consider
(8)Wr-1(i)={1,i=0,e(1-1/(1-e(1-1/i))),i=1lNscales-1,2lNscales-1,…,lNscales-1-1lNscales-1,0,i=1,Wl-1(i)={0,i=0,e(1-1/(1-e(1-1/(1-i)))),i=1lNscales-1,2lNscales-1,…,lNscales-1-1lNscales-1,1,i=1.(2)
Construct the right and left windows along the vertical direction, denoted by row vectorWr-2 and Wl-2, respectively. Consider
(9)Wr-2(i)={1,i=0,e(1-1/(1-e(1-1/i))),i=1lNscales-2,2lNscales-2,…,lNscales-2-1lNscales-2,0,i=1,(10)Wl-2(i)={0,i=0,e(1-1/(1-e(1-1/(1-i)))),i=1lNscales-2,2lNscales-2,…,lNscales-2-1lNscales-2,1,i=1.Wr-1, Wl-1, Wr-2, and Wl-2 are normalized by
(11)Wr-1(i)=Wr-1(i)[Wr-1(i)]2+[Wl-1(i)]2,Wl-1(i)=Wl-1(i)[Wr-1(i)]2+[Wl-1(i)]2,Wr-2(i)=Wr-2(i)[Wr-2(i)]2+[Wl-2(i)]2,Wl-2(i)=Wl-2(i)[Wr-2(i)]2+[Wl-2(i)]2.(3)
Construct the two sub-low-pass filters, denoted by row vectorflowpasssub1 and flowpasssub2, respectively. Consider
(12)flowpasssub1=[Wl-1,1,1⋯1︸p1,Wr-1]1×[2×floor(2×M1)+1],flowpasssub2=[Wl-2,1,1⋯1︸p2,Wr-2]1×[2×floor(2×M2)+1],
where p1=2×floor(M1)+1, p2=2×floor(M2)+1.(4)
Construct a low-pass filter at scale 5, denoted by matrix(flowpass_5)[2×floor(2×M1)+1]×[2×floor(2×M2)+1], and
(13)flowpass_5=(flowpasssub1)T×flowpasssub2,
where (·)T is the transpose vector or matrix of the input vector or matrix.(5)
Construct a high-pass filter at scale 5, denoted by matrixfhipass_5, which has the same size as flowpass_5. Consider
(14)fhipass_5=1-(flowpass_5)2.(6)
f^[n1,n2] is filtered by fhipass_5, hence generating the filtered high-pass signal at scale 5 fhipass_5′, which has the same size of N1×N2 as f^[n1,n2]. Consider
(15)fhipass_5′(n1,n2)={f^(n1,n2)×fhipass_5(n1,n2),a≤n1≤b,c≤n2≤d,f^(n1,n2),others,
where the filter at scale 5 has the following range:
(16)a=-floor(2×M1)+ceil((N1+1)2),b=floor(2×M1)+ceil((N1+1)2),c=-floor(2×M2)+ceil((N2+1)2),d=-floor(2×M2)+ceil((N2+1)2).(7)
Inverse 2DFFT (inverse fast Fourier transform) is applied tofhipass_5′, hence generating the discrete Curvelet coefficients at scale 5, C5,1.(8)
f^[n1,n2] is filtered by flowpass_5, hence generating the filtered low-pass signal at scale 5, (flowpass_5′)[2×floor(2×M1)+1]×[2×floor(2×M2)+1] and
(17)flowpass5′(n1,n2)=f^(n1,n2)×flowpass5(n1,n2),iiiiiiiiiiiiiiiiiiiiiiiiiiiiia≤n1≤b,c≤n2≤d.Step 3.
Acquire the Curvelet coefficients at scale 4 and angle 1 to angle 32,C4,l, l=1,2,…,32.Firstly, we acquire the Curvelet coefficients at scale 4 and angle 1,C4,1.Suppose that(18)M1=N1(6×2),M2=N2(6×2).The filter at scale 4 has the following range:(19)aNscales-1=-floor(2×M1)+floor(4×M1)+1,bNscales-1=floor(2×M1)+floor(4×M1)+1,cNscales-1=-floor(2×M2)+floor(4×M2)+1,dNscales-1=floor(2×M2)+floor(4×M2)+1.(1)
Construct a low-pass filter at scale 4 and angle 1 in the same way as at scale 5,(flowpass_4)[2×floor(2×M1)+1]×[2×floor(2×M2)+1].(2)
Construct a high-pass filter at scale 4 and angle 1 in the same way as at scale 5,(fhipass_4)[2×floor(2×M1)+1]×[2×floor(2×M2)+1].(3)
flowpass_5′ is filtered by flowpass_4, hence generating the filtered low-pass signal at scale 4 (flowpass_4′)[2×floor(2×M1)+1]×[2×floor(2×M2)+1].(4)
flowpass_5′ is filtered by fhipass_4, hence generating the filtered high-pass signal at scale 4 fhipass_4′, which has the same size as that of flowpass_5′.(5)
Determine the discrete locating window of wedge wave at scale 4 and angle 1.The Curvelet coefficients at scale 4 are divided into the four quadrants. The quadrant label of Curvelet coefficients is denoted byquad, and four quadrants are denoted by quad=1,2,3,4, respectively. Each quadrant has 8 angles. In the first quadrant, quad=1, angle ranges from 1 to 8, in the second quadrants, quad=2, angle ranges from 9 to 16, in the third quadrants, quad=3, angle ranges from 17 to 24, in the fourth quadrants, and quad=4, angle ranges from 25 to 32.Suppose that(20)Mhoriz=M2,Mvert=M1,quad=1or3,Mhoriz=M1,Mvert=M2,quad=2or4,p=12×nquad-4,q=2×floor(4×Mhoriz),
where nquad-4 denotes the number of angle at each quadrant at scale 4; in this paper, nquad-4=8.The left vector of wedge wave is denoted byWleft=(a1,k+1)1×(nquad-4+1), where a1,k+1=round(k×p×q+1), k=0,1,2,…,nquad-4.The right vector of wedge wave is denoted byWright=(a1,k+1)1×(nquad-4), where a1,k+1=q+2-round(k×p×q+1), k=nquad-4,nquad-4-1,…,1.The combination wedge wave vector is denoted byW=[Wleft,Wright]1×(2×nquad-4+1).The endpoint vector of wedge wave is denoted byWend=(a1,k)1×(nquad-4), where a1,k=W(2×k)⋯k=1,2,…,nquad-4.The first midpoint vector of wedge wave is denoted byWmid1=(a1,k)1×(nquad-4-1), where a1,k=Wend(k)⋯k=1,2,…,nquad-4-1.The second midpoint vector of wedge wave is denoted byWmid2=(a1,k)1×(nquad-4-1), where a1,k=Wend(k)⋯k=2,3,…,nquad-4.The combination midpoint vector of wedge wave is denoted byWmid=(a1,k)1×(nquad-4-1), where a1,k=((Wmid1(k)+Wmid2(k))/2)⋯k=1,2,3,…,nquad-4-1.The first wedge wave endpoint along the vertical orientation is denoted by(21)rfirst_wedge_endpont=round(2×floor(4×Mvert)2×nquad-4+1).The length of the first wedge wave is denoted by(22)swedge=floor(4×Mvert)-floor(Mvert)+ceil(rfirst_wedge_endpont4).The width of the wedge wave is denoted byWwedge=Wend(2)+Wend(1)-1.The slope of the first wedge wave issslope=[floor(4×Mhoriz)+1-Wend(1)]/floor(4×Mvert).The left line vector is denoted bysleft_line=(a1,k)1×(swedge), where a1,k=round(2-Wend(1)+sslope×(k-1))⋯k=1,2,…,swedge.The first row coordinate isrfirst=floor(4×Mvert)+2-ceil((swedge+1)/2).The first column coordinate iscfirst=floor(4×Mhoriz)+2-ceil((Wwedge+1)/2).Condition column vector is denoted byVcol=(a1,k)1×Wwedge, where
(23)a1,k=sleft_line(k+1)+mod⁡((k-sleft_line(k+1)+cfirst),Wwedge),iiiiiiiiiiiiiiiiiiiiiiiiiiiik=0,1,2,…,Wwedge-1,mod⁡(x,y)={x-n×yn=floor(xy),y≠0,x,y=0.Thus, the discrete locating window of wedge wave is denoted byWdata=(an1,n2)swedge×Wwedge, where
(24)an1,n2={fhipass4′(n1,n2),Vcol(n2)>0,0,Vcol(n2)≤0,
where
(25)n1=1+mod⁡(k-rfirst,swedge),k=1,2,…,swedge,(26)n2=0.5×Vcol(k)+1+|Vcol(k)-1|,iiiiiiiiiiiiiiiiiiiiiiik=1,2,…,Wwedge.(6)
The discrete locating window of wedge waveWdata is filtered and rotated, hence generating matrix Wdata_2.Suppose that(27)ycorner=(a1,k)1×swedge,
where a1,k=k, k=1,2,3,…,swedge and
(28)xcorner=(a1,k)1×q,
where a1,k=k, k=1,2,3,…,q+1 and
(29)X=[xcornerxcornerxcorner⋮xcorner]swedge×q,YT=[ycornerycornerycorner⋮ycorner]q×swedge,Xwrap=(X(n1,n2))swedge×Wwedge,
where n1, n2 are calculated by (25) and (26), respectively. Consider
(30)Ywrap=(Y(n1,n2))swedge×Wwedge,
where n1, n2 are calculated by (25) and (26), respectively.The slope of right wedge wave issslope-right=(floor(4×Mhoriz)+1-Wmid(1))/floor(4×Mvert).The middle line matrixMmid-line-right=(an1,n2)swedge×Wwedge, where an1,n2=Wmid(1)+sslope-right×(Ywrap(n1,n2)-1).The right coordinate matrix isCcord-right=(an1,n2)swedge×Wwedge, where
(31)an1,n2=0.5+floor(4×Mvert)Wend(2)-Wend(1)×Xwrap(n1,n2)-Mmid-line-right(n1,n2)floor(4×Mvert)+1-Ywrap(n1,n2),c2=1×((2×(floor(4×Mvert)(rfirst-wedge-endpont-1))-1)-112×(floor(4×Mhoriz)/(Wend(1)-1))-1-1iiiiiiiii+1×(2×(floor(4×Mvert)rfirst-wedge-endpont-1)-1)-1)-1,c1=c22×((floor(4×Mhoriz))/(rfirst-wedge-endpont-1))-1.The corner coordinate matrixCcord-corner=(an1,n2)swedge×Wwedge, where
(32)an1,n2=c1+c2×[Xwrap(n1,n2)-1floor(4×Mhoriz)-Ywrap(n1,n2)-1floor(4×Mvert)],×(2-[Xwrap(n1,n2)-1floor(4×Mhoriz)-Ywrap(n1,n2)-1floor(4×Mvert)])-1.TheCcord-corner is wrapped, yielding the matrix Wl-left and Wr-right:
(33)Wl-left(n1,n2)={1,Ccord-coner(n1,n2)=0,e(1-1/(1-e(1-1/Ccord-corner(n1,n2)))),0<Ccord-corner(n1,n2)<1,0,Ccord-lcorner(n1,n2)=1,Wl-right(n1,n2)={1,Ccord-corner(n1,n2)=0,e(1-1/(1-e(1-1/(1-Ccord-corner(n1,n2))))),0<Ccord-corner(n1,n2)<1,0,Ccord-corner(n1,n2)=1.In the same way, theCcord-right is wrapped, yielding the matrix Wwl-left and Wwr-right.The discrete locating window of wedge waveWdata is filtered, yielding the matrix Wdata-tran=(an1,n2)swedge×Wwedge, where an1,n2=Wdata(n1,n2)×[Wl-left(n1,n2)×Wwr-right(n1,n2)].The matrixWdata-tran is rotated, yielding the matrix Wdata_2(34)Wdata_2=rot⁡90(Wdata-tran,-(quad-1)),
where rot⁡90(A,k) rotates matrix A counterclockwise by k×90∘ degrees.(7)
Inverse 2DFFT is applied toWdata_2, hence generating the Curvelet coefficient at scale 4 and angle 1, C4,1.(8)
Repeat(5), (6), and (7) in Step 3, in the same way of acquiring C4,1; Curvelet coefficients at scale 4 and angle from 2 to 8 are generated.Noted that at angle from 2 to 32, the left line vector is denoted bysleft_line=(a1,k)1×(swedge), where a1,k=round(Wend(lsub-1)+sslope×(k-1))⋯k=1,2,…,swedge. Consider
(35)lsub=2,3,4,…,8.(9)
The Curvelet coefficients at scale 4 and other three quadrants,C4,l, l=9,10,…,32 are acquired in the same way as that in the first quadrants.Finally, the Curvelet coefficients at scale 4,C4,l, l=1,2,…,32, are generated after Step 3.Step 4.
Repeat Step3, hence generating the Curvelet coefficients at scale 3, C3,l, l=1,2,…,32.Note that the discrete locating window of wedge wave at scale 3 can be calculated by(36)Wdata_3=(an1,n2)swedge-3×Wwedge-3,
where
(37)an1,n2={fhipass3′(n1,n2),Vcol3(n2)>0,0,Vcol_3(n2)≤0,swedge-3, Wwedge-3 is the length and width of the discrete locating window of wedge wave at scale 3, and Vcol_3 is condition vector at scale 3.Step 5.
Repeat Step3, hence generating the Curvelet coefficients at scale 2, C2,l, l=1,2,…,16.Note that the discrete locating window of wedge wave at scale 2 can be calculated by(38)Wdata_2=(an1,n2)swedge-2×Wwedge-2,
where
(39)an1,n2={fhipass2′(n1,n2),Vcol2(n2)>0,0,Vcol_2(n2)≤0,
and Vcol_2 is condition vector at scale 2.Step 6.
Inverse 2DFFT is applied to the low-pass signal at scale 2,flowpass2′(n1,n2), generating the Curvelet coefficient at scale 1 C1,1.The detailed structure of the Curvelet coefficients obtained by FDCT_WARPING is shown in Table1.Table 1
Structure of Curvelet transform coefficients.
Levels
Scales (j)
Orientation (l)
Matrix formCj,i
Coarse
1
1
21
×
21
Details
2
16
18
×
22
16
×
22
16
×
22
18
×
22
22
×
18
22
×
16
22
×
16
22
×
18
18
×
22
16
×
22
16
×
22
18
×
22
22
×
18
22
×
16
22
×
16
22
×
18
3
32
34×2232×2232×2232×2232×2232×2232×2234×2222×3422×3222×3222×3222×3222×3222×3222×3434×2232×2232×2232×2232×2232×2232×2234×2222×3422×3222×3222×3222×3222×3222×3222×34
4
32
67×4464×4364×4364×4464×4464×4364×4367×4444×6743×6443×6444×6444×6443×6443×6444×6767×4464×4364×4364×4464×4464×4364×4367×4444×6743×6443×6444×6444×6443×6443×6444×67
Fine
5
1
256
×
256


## 2.3.2. Fingerprint Image Noise Filtration Technique

Noise always arises from the acquiring fingerprint images. The noise may result in the vagueness and many discontinuities of ridges (or valleys) in the image and thus affects accurate feature extraction and recognition. So, it is necessary and important to denoise in fingerprint images.The relationship of the Curvelet coefficients between the different scales is similar to the relationship of the wavelet coefficients; that is, there exists strong correlation between them.From Table1, there are 16 and 32 orientations at scale 2 and scale 3, respectively. Each Curvelet coefficient matrix is at scale 2 and each orientation corresponds to two adjacent matrices generated at scale 3. The ridges in a fingerprint image correspond to the Curvelet coefficients with large magnitude at scale 2. Each Curvelet coefficient matrix at scale 2 is decomposed into two Curvelet coefficient matrices at scale 3 and at two adjacent orientations. The corresponding two Curvelet coefficient matrices at scale 3 also have large magnitude, while the magnitude of the Curvelet coefficients corresponding to the noise dies out swiftly from scale 2 to scale 3. So, we use the direct spatial correlation of Curvelet coefficients at scale 2 and scale 3 to accurately distinguish ridges from noise. For scales 4 and 5, we adopt hard thresh method to filter the noise. Finally, we reconstruct all the Curvelet coefficients by the technique [17] and accomplish fingerprint image filtration.The proposed noise filtration technique has the following steps.Step 1.
Noise filtration of Curvelet coefficient matrices at scale 2 and scale 3, respectively.This section details the major steps of the proposed noise filtration algorithm of Curvelet coefficient matrices generated at scales 2 and 3.Assume each matrix to be at scale 2 and orientationl, C2,l, corresponds to two adjacent matrices generated at scale 3, C3,2×(l-1)+1 and C3,2×(l-1)+2, (l ranges from 1 to 16×2ceil((5-3)/2)). Let (r0,c0) be the size of C2,l. The sizes of C3,2×(l-1)+1 and C3,2×(l-1)+2 are (r1×c1) and (r2×c2), respectively. The matrices at scales 2 and 3 are filtered as follows.(1)
Decompose the Curvelet coefficients matrixC3,2×(l-1)+1 into two matrices A and B with the same size as C2,l, r0×c0. The elements of A are extracted from row 1 to r0 and column 1 to c0 of C3,2×(l-1)+1, and the elements of B are extracted from row r1-r0+1 to r1 and column c1-c0+1 to c1 of C3,2×(l-1)+1. Consider
(40)A=(an1,n2)r0×c0,
where an1,n2=C3,2×(l-1)+1(n1,n2), n1=1,2,3,…,r0, n2=1,2,3,…,c0, and
(41)B=(an1,n2)r0×c0,
where an1,n2=C3,2×(l-1)+1(n1,n2), n1=r1-r0+1, r1-r0+2,…,r1, n2=c1-c0+1, c1-c0+2,…,c1.(2)
Decompose the Curvelet coefficients matrixC3,2×(l-1)+2 into two matrices D and E with the size of r0×c0:
(42)D=(an1,n2)r0×c0,
where an1,n2=C3,2×(l-1)+2(n1,n2), n1=1,2,3,…,r0, n2=1,2,3,…,c0, and
(43)E=(an1,n2)r0×c0,
where an1,n2=C3,2×(l-1)+2(n1,n2), n1=r1-r0+1, r1-r0+2,…,r1, n2=c1-c0+1, c1-c0+2,…,c1.(3)
Calculate the four multiplication coefficient matrices(mk,k=1,2,34) between C2,l and the four matrices A, B, D, and E, respectively. Consider
(44)m1(n1,n2)=C2,l(n1,n2)×A(n1,n2),iin1=1,2,…,r0,n2=1,2,…,c0,m2(n1,n2)=C2,l(n1,n2)×B(n1,n2),iin1=1,2,…,r0,n2=1,2,…,c0,m3(n1,n2)=C2,l(n1,n2)×D(n1,n2),iin1=1,2,…,r0,n2=1,2,…,c0,m4(n1,n2)=C2,l(n1,n2)×E(n1,n2),iin1=1,2,…,r0,n2=1,2,…,c0.(4)
Filter the Curvelet coefficient matricesC3,2×(l-1)+1 and C3,2×(l-1)+2 by
(45)A′(n1,n2)={A(n1,n2),||m1(n1,n2)|-|m3(n1,n2)||>Ts,0,otherwise,D′(n1,n2)={D(n1,n2),||m1(n1,n2)|-|m3(n1,n2)||>Ts,0,otherwise,B′(n1,n2)={B(n1,n2),||m2(n1,n2)|-|m4(n1,n2)||>Ts,0,otherwise,E′(n1,n2)={E(n1,n2),||m2(n1,n2)|-|m4(n1,n2)||>Ts,0,otherwise,
where A′, D′, B′, and E′ are the Curvelet coefficient matrices at scale 3 after filtration, the operation |·| returns the complex modulus (magnitude) of the input, and Ts is the threshold. For example, if ||m1(n1,n2)|-|m3(n1,n2)||>Ts, we assume that the Curvelet coefficients correspond to the ridges of the image. Otherwise, the Curvelet coefficients correspond to the noise of the image, which are assigned to 0.(5)
When filtering the Curvelet coefficient matrixC2,l, if any of the filtered Curvelet coefficient matrices (A′, D′, B′,and E′) equal to Z, C2,l is considered as noise and assigned to Z. Where Z is a matrix with all elements are zero.(6)
repeat(1) to (5) with 16 times (the number of orientation of Curvelet coefficients at scale 2).After(1)–(5), all the Curvelet coefficients at scale 2 and scale 3 are filtered.Step 2.
Noise Filtration of Curvelet coefficient matrices at scale 4 and scale 5, respectively.The Curvelet coefficient matrices generated at scale 4 are filtered by(46)Cj,l′(i,j)={Cj,l(n1,n2),|Cj,l(n1,n2)|>thresh×Ej,l,0,otherwise,
where Cj,l′ are the filtered Curvelet coefficient matrices, |·| is the complex modulus operation, and thresh is the threshold; in this paper, thresh=1.5, and
(47)Ej,l=∑i=1n∑j=1m|Cj,l(i,j)|2n×m,
where (n,m) is the size of matrix Cj,l.The Curvelet coefficient matrices generated at scale 5 are filtered in the same way as the Curvelet coefficient matrices generated at scale 4. Note that at scale 5thresh=2.Step 3.
After the coefficients at scale 2, 3, 4, and 5 are filtered, we reconstruct the coefficients using the technique [16] and accomplish image noise filtration.T
s in (45) can be acquired by the statistics of difference of correlation coefficients in adjacent directions at the same scale. Finally, Ts=100 is selected by many experiments. Figure 1 shows the noise filtration results of five types of fingerprint image by proposed noise filtration algorithm.From Figure1  (x):(B) (x = a, b, c, d, e), we can see many discontinuities of ridges in the original image can be smoothed after filtering and the direction of ridge is well followed, which founds the good basis for accurate feature extraction and recognition. We demonstrate Curvelet coefficients at different scales of five types of filtered images in Figure 2.Curvelet coefficients of five filtered fingerprint classes. (a) Right loop (R), (b) left loop (L), (c) whorl (W), (d) arch (A), and (e) tented arch (T).
(a)
(b)
(c)
(d)
(e)As Figure2(a) to Figure 2(e) show, there are strong orientations in the Curvelet coefficients images. The white parts in the images represent partial edges of the ridge of fingerprint image in different orientations. Meanwhile, it means the significant Curvelet coefficients of images. The low-frequency (coarse scale) coefficients are stored at the center of the display. The Cartesian concentric coronae show the coefficients at different scales; the outer coronae correspond to higher frequencies. There are four strips associated with each corona, corresponding to the four cardinal points; these are further subdivided in angular panels. Each panel represents coefficients at a specified scale and along the orientation suggested by the position of the panel.


## 2.4. Fingerprint Feature Extraction

Haralick et al. [18] first proposed gray-level cooccurrence matrix (GLCM) for texture descriptions in the 1970s. It is still popular until today and widely used in various texture classifications [19–23], because of its good statistic performance. The GLCM is a second order statistics method which describes the spatial interrelationships of the grey tones in an image.GLCM contains elements that are counts of the number of pixel pairs, which are separated by certain distance and at some angular direction. Typically, the GLCM is calculated in a small window, which scans the whole image. The texture feature will be associated with each pixel.In our studies, GLCM is computed based on two parameters, which are the distance between the pixel paird and their angular relationship θ. d=1 and θ are quantized in four directions (0°, 45°, 90°, and 135°). For image I, defined square window N×N, brightness levels i and j, the nonnormalized GLCM pij are defined by
(48)pi,j,θ=∑x=1N∑y=1NC{(I(x,y)=i)(I(x±dθ0,y∓dθ1)=j)},
where C{·}=1 if the argument is true and C{·}=0, otherwise. The signs ± and ∓ in (10) mean that each pixel pair is counted twice: once forward and once backward in order to make the GLCM diagonally symmetric. For each direction, θ0 and θ1 are shown in Table 2.Table 2
Direction values.
θ
0°
45°
90°
135°
θ
0
0
1
1
1
θ
1
1
1
0
−1The procedures of feature extraction are as follows.Step 1.
Scale the grayscale values in Curvelet transform coefficients into 8 levers and compute the GLCMs of Curvelet coefficients at scale 1C1,1 and calculate 16 texture features based on 4 GLCMs:(1)
Angular second moment (ASM)(49)f1=∑i=0G-1∑j=0G-1p(i,j)2.(2)
Contrast (CON)(50)f2=∑n=0G-1n2{∑i=0G-1∑j=0G-1p(i,j)2},
where |i-j|=n.(3)
Correlation (COR)(51)f3=∑i=0G-1∑j=0G-1(ij)p(i,j)-μ1μ2σ12σ22,
where
(52)μ1=∑i=0G-1i∑j=0G-1p(i,j),μ2=∑i=0G-1j∑j=0G-1p(i,j),σ12=∑i=0G-1(i-μ1)2∑j=0G-1p(i,j),σ22=∑i=0G-1(j-μ2)2∑i=0G-1p(i,j).(4)
Entropy (ENT)(53)f4=-∑i=0G-1∑j=0G-1p(i,j)log⁡⁡p(i,j).Step 2.
Calculate averagedl1 -norm of Curvelet coefficients in 8 directions at the second scale C2,l and acquire 8 texture features according to (51). Consider
(54)El=1m1×m2∑im1∑jm2|C2,l(i,j)|,
where, (m1,m2) is the size of the matrix C2,l, and l=1,2,3,4,5,…,16.Step 3.
Calculate averagedl1-norm of Curvelet coefficients in 16 directions at the third scale C3,l and acquire 16 texture features according to (54).Step 4.
Calculate averagedl1-norm of Curvelet coefficients in 16 directions at the fourth scale C4,l and acquire 16 texture features according to (54).Step 5.
Calculate averagedl1-norm of Curvelet coefficients at the fifth scale C5,1 and acquire 1 texture feature.Note that in Step2, Step 3, and Step 4, we only calculate the averaged l1-norm of Curvelet coefficients in even directions to assure the classification accuracy and reduce the recognition time. So, a feature vector containing 57 components for each image can be extracted.


## 3. Experiment Results

### 3.1. Datasets

NIST special fingerprint database 4(NIST-4) is one of the most important benchmarks for fingerprint classification. Most published results on fingerprint classification are based on this database. For comparison with other approaches, we also perform our fingerprint classification algorithm on this database for the five-class fingerprint classification problem. Since fingerprint classes A (arch) and T (tented arch) have a substantial overlap, it is very difficult to separate these two classes. Therefore, we also report our results for the four-class classification problem, where classes A and T have been merged into one class. NIST-4 contains 4000 fingerprints of size 480 × 512 pixels, taken from 2000 fingers. Each finger has two impressions (f and s). The first fingerprint instances are numbered from f0001 to f2000 and the second fingerprint instances are numbered from s0001 to s2000. All fingerprints in this database are used in our experiment. We form our training set with the first 2,000 fingerprints from 1,000 fingers (f0001 to f1000 and s0001 to s1000) and the test set contains the remaining 2,000 fingerprints (f1001 to f2000 and s1001 to s2000).To eliminate the large difference between the feature vectors, each feature vectorvk is normalized according to
(55)vk(i)=vk(i)-vmin⁡(i)vmax⁡(i)-vmin⁡(i),
where vk(i) represents the ith element of vector vk, vmin⁡(i) denotes the minimum of the ith element of all the row vectors, and vmax⁡(i) denotes the maximum of the ith element of all the row vectors.


### 3.2. Experiment Results and Analysis

The performance of a fingerprint classification algorithm is often measured in terms of accuracy. The accuracy is computed as the ratio between the number of correctly classified fingerprint and the total number of fingerprints in the test set. Each image is labeled with one or more of the five classes (W, R, L, A, and T). To simplify the training procedure, we make use of only the first label of a fingerprint to train our system. For testing, however, we make use of all the labels for a fingerprint and consider the output of our classifier to be correct if the output matches any one of the labels. This is in line with the common practice used by other researchers in comparing the classification results on the NIST-4 database.Classification accuracy does not always increase with increasingK of the K-nearest neighbor classifier; there exists an optimal value of K for finite training sample size classification problems. According to the method in [24], in our experiments, 10 nearest neighbors (K=10) are considered. The classification results of our proposed approach are shown in Table 3. The diagonal entries in Table 3 show the number of test patterns from different classes which are correctly classified.Table 3
Fingerprint classification results on NIST-4.
True class
Hypothesized class
A
T
L
R
W
A
432
12
3
1
2
T
28
296
8
4
0
L
4
5
370
0
4
R
3
8
1
386
3
W
3
1
6
5
380From Table3, we can conclude that the proposed algorithm achieves an accuracy of 94.6 percent for the five-class classification task. For the four-class classification task (where classes A and T were collapsed into one class), an accuracy of 96.8 percent is achieved.Experiment. To evaluate the performance of the proposed algorithm, we have compared the proposed approach to wavelet-based, GLCM-based, and Curvelet-based, respectively. We use wavelet transform to decompose gray images into five scales wavelet coefficients using wavelet bases “Symmlets 4, 5, 6, 8, and 9” and calculate averaged l1-norm of wavelet coefficients at each scale. Finally, WT feature vector with dimension of 16 are acquired. The reason using “Symmlets 4, 5, 6, 8, and 9” is that in the work of Tico et al. [10] best results were obtained with these five wavelet bases. In Table 4, we show the comparison results for the five-class classification.Table 4
Comparison of accuracy on NIST-4 for the five-class classification.
Features
AccuracyA
AccuracyT
AccuracyL
AccuracyR
AccuracyW
Wavelet(Symmlet 4)
92%
79.7%
94.2%
93.3%
93.7%
Wavelet(Symmlet 5)
92%
82.7%
94.5%
93.5%
93.1%
Wavelet(Symmlet 6)
92%
83.7%
94.2%
93.0%
93.7%
Wavelet(Symmlet 8)
92%
82.7%
94.2%
93.0%
93.7%
Wavelet(Symmlet 9)
92%
81.2%
94.2%
93.0%
93.7%
GLCM
78.4%
77.7%
79.4%
72.8%
82.7%
Curvelet
93.6%
84.7%
95.0%
94.0%
94.5%
Proposed algorithm
96.0%
88.1%
96.6%
96.3%
96.2%From Table4, we can conclude that our algorithm achieves higher accuracy of classes W by reducing the misclassification of W as L or R. Our algorithm also achieves higher accuracy of classes R by reducing the misclassification of R as A. Finally, our algorithm achieves higher accuracy of classes A by reducing the misclassification of A as T.Also, Curvelet-based is better than wavelet-based and GLCM-based. The reason is CT can better capture the direction of fingerprint ridge than WT and GLCM. Furthermore, the proposed algorithm can provide much more information on the ridge direction by combining the good statistic performance of GLCM and well capturing the direction of CT.Most of misclassifications in the proposed approach are caused by heavy noise in the poor quality fingerprints, where it is very difficult to correctly extract Curvelet coefficients.


## 3.1. Datasets

NIST special fingerprint database 4(NIST-4) is one of the most important benchmarks for fingerprint classification. Most published results on fingerprint classification are based on this database. For comparison with other approaches, we also perform our fingerprint classification algorithm on this database for the five-class fingerprint classification problem. Since fingerprint classes A (arch) and T (tented arch) have a substantial overlap, it is very difficult to separate these two classes. Therefore, we also report our results for the four-class classification problem, where classes A and T have been merged into one class. NIST-4 contains 4000 fingerprints of size 480 × 512 pixels, taken from 2000 fingers. Each finger has two impressions (f and s). The first fingerprint instances are numbered from f0001 to f2000 and the second fingerprint instances are numbered from s0001 to s2000. All fingerprints in this database are used in our experiment. We form our training set with the first 2,000 fingerprints from 1,000 fingers (f0001 to f1000 and s0001 to s1000) and the test set contains the remaining 2,000 fingerprints (f1001 to f2000 and s1001 to s2000).To eliminate the large difference between the feature vectors, each feature vectorvk is normalized according to
(55)vk(i)=vk(i)-vmin⁡(i)vmax⁡(i)-vmin⁡(i),
where vk(i) represents the ith element of vector vk, vmin⁡(i) denotes the minimum of the ith element of all the row vectors, and vmax⁡(i) denotes the maximum of the ith element of all the row vectors.


## 3.2. Experiment Results and Analysis

The performance of a fingerprint classification algorithm is often measured in terms of accuracy. The accuracy is computed as the ratio between the number of correctly classified fingerprint and the total number of fingerprints in the test set. Each image is labeled with one or more of the five classes (W, R, L, A, and T). To simplify the training procedure, we make use of only the first label of a fingerprint to train our system. For testing, however, we make use of all the labels for a fingerprint and consider the output of our classifier to be correct if the output matches any one of the labels. This is in line with the common practice used by other researchers in comparing the classification results on the NIST-4 database.Classification accuracy does not always increase with increasingK of the K-nearest neighbor classifier; there exists an optimal value of K for finite training sample size classification problems. According to the method in [24], in our experiments, 10 nearest neighbors (K=10) are considered. The classification results of our proposed approach are shown in Table 3. The diagonal entries in Table 3 show the number of test patterns from different classes which are correctly classified.Table 3
Fingerprint classification results on NIST-4.
True class
Hypothesized class
A
T
L
R
W
A
432
12
3
1
2
T
28
296
8
4
0
L
4
5
370
0
4
R
3
8
1
386
3
W
3
1
6
5
380From Table3, we can conclude that the proposed algorithm achieves an accuracy of 94.6 percent for the five-class classification task. For the four-class classification task (where classes A and T were collapsed into one class), an accuracy of 96.8 percent is achieved.Experiment. To evaluate the performance of the proposed algorithm, we have compared the proposed approach to wavelet-based, GLCM-based, and Curvelet-based, respectively. We use wavelet transform to decompose gray images into five scales wavelet coefficients using wavelet bases “Symmlets 4, 5, 6, 8, and 9” and calculate averaged l1-norm of wavelet coefficients at each scale. Finally, WT feature vector with dimension of 16 are acquired. The reason using “Symmlets 4, 5, 6, 8, and 9” is that in the work of Tico et al. [10] best results were obtained with these five wavelet bases. In Table 4, we show the comparison results for the five-class classification.Table 4
Comparison of accuracy on NIST-4 for the five-class classification.
Features
AccuracyA
AccuracyT
AccuracyL
AccuracyR
AccuracyW
Wavelet(Symmlet 4)
92%
79.7%
94.2%
93.3%
93.7%
Wavelet(Symmlet 5)
92%
82.7%
94.5%
93.5%
93.1%
Wavelet(Symmlet 6)
92%
83.7%
94.2%
93.0%
93.7%
Wavelet(Symmlet 8)
92%
82.7%
94.2%
93.0%
93.7%
Wavelet(Symmlet 9)
92%
81.2%
94.2%
93.0%
93.7%
GLCM
78.4%
77.7%
79.4%
72.8%
82.7%
Curvelet
93.6%
84.7%
95.0%
94.0%
94.5%
Proposed algorithm
96.0%
88.1%
96.6%
96.3%
96.2%From Table4, we can conclude that our algorithm achieves higher accuracy of classes W by reducing the misclassification of W as L or R. Our algorithm also achieves higher accuracy of classes R by reducing the misclassification of R as A. Finally, our algorithm achieves higher accuracy of classes A by reducing the misclassification of A as T.Also, Curvelet-based is better than wavelet-based and GLCM-based. The reason is CT can better capture the direction of fingerprint ridge than WT and GLCM. Furthermore, the proposed algorithm can provide much more information on the ridge direction by combining the good statistic performance of GLCM and well capturing the direction of CT.Most of misclassifications in the proposed approach are caused by heavy noise in the poor quality fingerprints, where it is very difficult to correctly extract Curvelet coefficients.


## 4. Conclusion

In this paper, we present an efficient fingerprint classification algorithm that uses CT and GLCM to model the feature set of fingerprint. There are two main contributions in this paper. Firstly, we construct Curvelet filter that can smooth the discontinuities of ridges and remove the noise in the original image. As a result, the direction of ridge is well followed. Secondly, in combination with the effectiveness of CT and GLCM, we propose to construct a 53-dimensional feature vector as classifier input that can represent curves singularities and the statistics in fingerprint image with compact feature. We have tested our algorithm on the NIST-4 database and a very good performance has been achieved (94.6 percent for the five-class classification problem and 96.8 percent for the four-class classification problem with 1.8 percent rejection). These good performances of the proposed algorithm could be ascribed to the high information contents of Curvelet features and to the combination of GLCM and CT.Our system takes about 1.47 seconds on a AMD E-350 PC to classify one fingerprint, which needs to be improved. Since image decomposition (filtering) steps account for 82 percent of the total compute time, special purpose hardware for Curvelet transform can significantly decrease the overall time for classification.



---

*Source: 592928-2014-08-17.xml*