846
`
`IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 9, NO. 5, MAY 2000
`
`Filterbank-Based Fingerprint Matching
`
`Anil K. Jain, Fellow, IEEE, Salil Prabhakar, Lin Hong, and Sharath Pankanti
`
`Abstract—With identity fraud in our society reaching un-
`precedented proportions and with an increasing emphasis on the
`emerging automatic personal identification applications, biomet-
`rics-based verification, especially fingerprint-based identification,
`is receiving a lot of attention. There are two major shortcomings
`of
`the traditional approaches to fingerprint representation.
`For a considerable fraction of population, the representations
`based on explicit detection of complete ridge structures in the
`fingerprint are difficult to extract automatically. The widely
`used minutiae-based representation does not utilize a significant
`component of the rich discriminatory information available in
`the fingerprints. Local ridge structures cannot be completely
`characterized by minutiae. Further, minutiae-based matching has
`difficulty in quickly matching two fingerprint images containing
`different number of unregistered minutiae points. The proposed
`filter-based algorithm uses a bank of Gabor filters to capture
`both local and global details in a fingerprint as a compact fixed
`length FingerCode. The fingerprint matching is based on the
`Euclidean distance between the two corresponding FingerCodes
`and hence is extremely fast. We are able to achieve a verification
`accuracy which is only marginally inferior to the best results of
`minutiae-based algorithms published in the open literature [1].
`Our system performs better than a state-of-the-art minutiae-based
`system when the performance requirement of the application
`system does not demand a very low false acceptance rate. Finally,
`we show that the matching performance can be improved by
`combining the decisions of the matchers based on complementary
`(minutiae-based and filter-based) fingerprint information.
`
`Index Terms—Biometrics, FingerCode, fingerprints, flow pat-
`tern, Gabor filters, matching, texture, verification.
`
`I. INTRODUCTION
`
`WITH THE advent of electronic banking, e-commerce,
`
`and smartcards and an increased emphasis on the pri-
`vacy and security of information stored in various databases,
`automatic personal identification has become a very important
`topic. Accurate automatic personal identification is now needed
`in a wide range of civilian applications involving the use of
`passports, cellular telephones, automatic teller machines, and
`driver licenses. Traditional knowledge-based [password or per-
`sonal identification number (PIN)] and token-based (passport,
`driver license, and ID card) identifications are prone to fraud be-
`cause PIN’s may be forgotten or guessed by an imposter and the
`tokens may be lost or stolen. As an example, Mastercard credit
`card fraud alone now amounts to more than 450 million U.S.
`
`Manuscript received May 11, 1999; revised November 16, 1999. The asso-
`ciate editor coordinating the review of this manuscript and approving it for pub-
`lication was Prof. Alan C. Bovik.
`A. K. Jain and S. Prabhakar are with the Department of Computer Science and
`Engineering, Michigan State University, East Lansing, MI 48824 USA (e-mail:
`jain@pilot.msu.edu).
`L. Hong is with Visionics Corporation, Jersey City, NJ 07302 USA.
`S. Pankanti is with the Exploratory Computer Vision and Intelligent Robotics
`Group, IBM T. J. Watson Research Center, Yorktown Heights, NY 10598 USA.
`Publisher Item Identifier S 1057-7149(00)03864-1.
`
`Fig. 1. Ridges and automatically detected minutiae points in a fingerprint
`image. The core is marked with a .
`
`dollars annually [2]. Biometrics, which refers to identifying an
`individual based on his or her physiological or behavioral char-
`acteristics has the capability to reliably distinguish between an
`authorized person and an imposter.
`A biometric system can be operated in two modes: 1) veri-
`fication mode and 2) identification mode. A biometric system
`operating in the verification mode either accepts or rejects a
`user’s claimed identity while a biometric system operating in the
`identification mode establishes the identity of the user without
`a claimed identity information. In this work, we have focused
`only on a biometric system operating in the verification mode.
`Among all the biometrics (e.g., face, fingerprints, hand ge-
`ometry, iris, retina, signature, voice print, facial thermogram,
`hand vein, gait, ear, odor, keystroke dynamics, etc. [2]), finger-
`print-based identification is one of the most mature and proven
`technique.
`A fingerprint is the pattern of ridges and valleys on the sur-
`face of the finger [3]. The uniqueness of a fingerprint can be de-
`termined by the overall pattern of ridges and valleys as well as
`the local ridge anomalies [a ridge bifurcation or a ridge ending,
`called minutiae points (see Fig. 1)]. Although the fingerprints
`possess the discriminatory information, designing a reliable au-
`tomatic fingerprint matching algorithm is very challenging (see
`Fig. 2). As fingerprint sensors are becoming smaller and cheaper
`[4], automatic identification based on fingerprints is becoming
`an attractive alternative/complement to the traditional methods
`of identification. The critical factor in the widespread use of fin-
`gerprints is in satisfying the performance (e.g., matching speed
`and accuracy) requirements of the emerging civilian identifi-
`cation applications. Some of these applications (e.g., finger-
`print-based smartcards) will also benefit from a compact rep-
`resentation of a fingerprint.
`
`1057-7149/00$10.00 © 2000 IEEE
`
`ASSA ABLOY Ex 1038 - Page 1
`ASSA ABLOY AB, et al. v. CPC Patent Technologies Pty Ltd.
`IPR2022-01093 - U.S. Patent No. 8,620,039
`
`

`

`JAIN et al.: FILTERBANK-BASED FINGERPRINT MATCHING
`
`847
`
`fingerprint images scanned at 500 dpi, there is a little variation
`in the spatial frequencies (inter-ridge distances) among different
`fingerprints. This implies that there is an optimal scale (spatial
`frequency) for analyzing the fingerprint texture. Every point in
`a fingerprint image is associated with a dominant local orien-
`tation and a local measure of coherence of the flow pattern. A
`symbolic description of a fingerprint image can be derived by
`computing the angle and coherence at each point in the image.
`Fingerprints can be identified by using quantitative measures as-
`sociated with the flow pattern (oriented texture) as features.
`It is desirable to explore representation schemes which com-
`bine global and local information in a fingerprint. We present
`a new representation for the fingerprints which yields a rela-
`tively short, fixed length code, called FingerCode [6] suitable
`for matching as well as storage on a smartcard. The matching
`reduces to finding the Euclidean distance between these Finger-
`Codes and hence the matching is very fast and the representa-
`tion is amenable to indexing. We utilize both the global flow
`of ridge and valley structures and the local ridge characteristics
`to generate a short fixed length code for the fingerprints while
`maintaining a high recognition accuracy.
`The proposed scheme of feature extraction tessellates the re-
`gion of interest of the given fingerprint image with respect to
`a reference point (Fig. 3). A feature vector is composed of an
`ordered enumeration of the features extracted from the (local)
`information contained in each subimage (sector) specified by
`the tessellation. Thus, the feature elements capture the local in-
`formation and the ordered enumeration of the tessellation cap-
`tures the invariant global relationships among the local patterns.
`The local discriminatory information in each sector needs to be
`decomposed into separate components. Gabor filterbanks are a
`well-known technique to capture useful information in specific
`bandpass channels as well as to decompose this information into
`biorthogonal components in terms of spatial frequencies. A fea-
`ture vector, which we call FingerCode, is the collection of all
`the features (for every sector) in each filtered image. These fea-
`tures capture both the global pattern of ridges and valleys and
`the local characteristics. Matching is based on the Euclidean dis-
`tance between the FingerCodes.
`
`II. FILTER-BASED FEATURE EXTRACTION
`
`It is desirable to obtain representations for fingerprints which
`are scale, translation, and rotation invariant. Scale invariance is
`not a significant problem since most fingerprint images could
`be scaled as per the dpi specification of the sensors. The rota-
`tion and translation invariance could be accomplished by estab-
`lishing a reference frame based on the intrinsic fingerprint char-
`acteristics which are rotation and translation invariant. It is also
`possible to establish many frames of reference based upon sev-
`eral landmark structures in a fingerprint to obtain multiple repre-
`sentations. At the expense of additional processing and storage
`cost, the multiple representations offer robust matching perfor-
`mance when extraction algorithm fails to detect one or more
`frames of reference. In the proposed feature extraction scheme,
`translation is handled by a single reference point location during
`the feature extraction stage. The present implementation of fea-
`ture extraction assumes that the fingerprints are vertically ori-
`
`Fig. 2. Difficulty in fingerprint matching. (a) and (b) have the same global
`configuration but are images of two different fingers.
`
`The popular fingerprint representation schemes have evolved
`from an intuitive system design tailored for fingerprint experts
`who visually match the fingerprints. These schemes are either
`based on predominantly local landmarks (e.g., minutiae-based
`fingerprint matching systems [1], [5]) or exclusively global
`information (fingerprint classification based on the Henry
`system [6]–[8]). The minutiae-based automatic identification
`techniques first locate the minutiae points and then match their
`relative placement in a given finger and the stored template
`[1]. A good quality fingerprint contains between 60 and 80
`minutiae, but different fingerprints have different number of
`minutiae. The variable sized minutiae-based representation
`does not easily lend itself to indexing mechanisms. Further,
`typical graph-based [9]–[11], and point pattern-based [1],
`[12], [13] approaches to match minutiae from two fingerprints
`need to align the unregistered minutiae patterns of different
`sizes which makes them computationally expensive. Corre-
`lation-based techniques [14], [15] match the global patterns
`of ridges and valleys to determine if the ridges align. The
`global approach to fingerprint representation is typically used
`for indexing [6]–[8], and does not offer very good individual
`discrimination. Further, the indexing efficacy of existing global
`representations is poor due to a small number of categories that
`can be effectively identified and a highly skewed distribution of
`the population in each category. The natural proportion of fin-
`gerprints belonging to categories whorl (whorl and double loop
`put together), loop (right and left loop put together), and arch
`(arch and tented arch put together), is 0.279, 0.655, and 0.066,
`respectively. Both these approaches utilize representations
`which cannot be easily extracted from poor quality fingerprints.
`The smooth flow pattern of ridges and valleys in a fingerprint
`can be viewed as an oriented texture field [16]. The image inten-
`sity surface in an ideal fingerprint image is comprised of ridges
`whose direction and height vary continuously, which consti-
`tutes an oriented texture. Most textured images contain a limited
`range of spatial frequencies, and mutually distinct textures differ
`significantly in their dominant frequencies [17]–[19]. Textured
`regions possessing different spatial frequency, orientation, or
`phase can be easily discriminated by decomposing the texture
`in several spatial frequency and orientation channels. For typical
`
`ASSA ABLOY Ex 1038 - Page 2
`ASSA ABLOY AB, et al. v. CPC Patent Technologies Pty Ltd.
`IPR2022-01093 - U.S. Patent No. 8,620,039
`
`

`

`848
`
`IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 9, NO. 5, MAY 2000
`
`Fig. 3. System diagram of our fingerprint authentication system.
`
`ented. In reality, the fingerprints in our database are not exactly
`vertically oriented; the fingerprints may be oriented up to
`away from the assumed vertical orientation. This image rotation
`is partially handled by a cyclic rotation of the feature values
`in the FingerCode in the matching stage; in future implemen-
`tations, the image rotation will be correctly handled by auto-
`matically determining the fingerprint orientation from the image
`data. The current scheme of feature extraction tessellates the re-
`gion of interest in the given fingerprint image with respect to the
`point of reference. The four main steps in our feature extraction
`algorithm are
`1) determine a reference point and region of interest for the
`fingerprint image;
`2) tessellate the region of interest around the reference point;
`3) filter the region of interest in eight different directions
`using a bank of Gabor filters (eight directions are required
`to completely capture the local ridge characteristics in
`a fingerprint while only four directions are required to
`capture the global configuration [6]);
`
`4) compute the average absolute deviation from the mean
`(AAD) of gray values in individual sectors in filtered im-
`ages to define the feature vector or the FingerCode.
`In the current implementation, we have used the AAD features
`which give slightly better performance than variance features
`[6] on both the MSU_DBI and NIST 9 databases. Although
`AAD features perform reasonably well, we believe that a sig-
`nificantly better performance can be achieved by using more
`discriminative features.
`Let
`in an
`denote the gray level at pixel
`fingerprint image and let
`denote the reference point.
`The region of interest is defined as the collection of all the sec-
`tors
`, where the th sector
`is computed in terms of param-
`eters
`as follows:
`
`(1)
`
`ASSA ABLOY Ex 1038 - Page 3
`ASSA ABLOY AB, et al. v. CPC Patent Technologies Pty Ltd.
`IPR2022-01093 - U.S. Patent No. 8,620,039
`
`

`

`JAIN et al.: FILTERBANK-BASED FINGERPRINT MATCHING
`
`849
`
`Fig. 5. Concave and convex ridges in a fingerprint image when the finger is
`positioned upright.
`
`It is difficult to rely on feature extraction based on explicit de-
`tection of structural features in fingerprints, especially in poor
`quality images. Features based on statistical properties of im-
`ages are likely to degrade gracefully with the image quality de-
`terioration. For this study, we use grayscale variance-based fea-
`tures. The average absolute deviation of the gray levels from the
`mean value in an image sector is indicative of the overall ridge
`activity in that sector which we claim to be useful for finger-
`print verification. As noted in Section IV, our matcher based on
`this simple statistical feature performs well and we expect to
`achieve significantly better accuracies with more discriminative
`attributes.
`
`A. Reference Point Location
`Fingerprints have many conspicuous landmark structures and
`a combination of them could be used for establishing a reference
`point. We define the reference point of a fingerprint as the point
`of maximum curvature of the concave ridges (see Fig. 5) in the
`fingerprint image.
`Many previous approaches to determination of a reference
`point (
`) critically relied on the local features like Poincaré
`index or some other similar properties of the orientation field.
`While these methods work well in good quality fingerprint
`images,
`they fail
`to correctly localize reference points in
`poor quality fingerprints with cracks and scars, dry skin, or
`poor ridge and valley contrast. Recently, Hong and Jain have
`attempted to judiciously combine the orientation field informa-
`tion with available ridge details in a fingerprint [8]. However,
`this method does not reliably handle poor quality fingerprints
`when the orientation field is very noisy and can be misled by
`poor structural cues in the presence of finger cracks.
`In order that a reference point algorithm gracefully handle
`local noise in a poor quality fingerprint, the detection should
`necessarily consider a large neighborhood in the fingerprint.
`On the other hand, for an accurate localization of the reference
`point, the approach should be sensitive to the local variations in
`a small neighborhood. To meet these conflicting requirements of
`an accurate and reliable localization, we propose a new method
`of reference point determination based on multiple resolution
`analysis of the orientation fields. Our new method locates the
`reference point more precisely than the algorithm proposed by
`Hong and Jain [8].
`Let us first define the orientation field,
`, for a fingerprint
`image. The orientation field,
`, is defined as a
`image,
`where
`represents the local ridge orientation at pixel
`. Local ridge orientation is usually specified for a block
`rather than at every pixel; an image is divided into a set of
`nonoverlapping blocks and a single orientation is defined for
`
`(),
`Fig. 4. Reference point
`superimposed on a fingerprint.
`
`the region of
`
`interest, and 80 sectors
`
`where
`
`(2)
`(3)
`(4)
`(5)
`
`is the number of sectors considered
`is the width of each band,
`in each band, and
`, where
`is the number
`of concentric bands considered around the reference point for
`feature extraction. These parameters depends upon the image
`resolution and size. In our first experiment with MSU_DBI data-
`base (image size =
`pixels, scanned at 500 dpi), we
`considered five concentric bands (
`) for feature extraction.
`Each band is 20-pixels wide (
`), and segmented into six-
`teen sectors (
`) (Fig. 4). A 20-pixel wide band captures
`an area spanning about one ridge and valley pair, on an average,
`in a 500 dpi fingerprint image. A band with a width of 20 pixels
`is necessary to capture a single minutia in a sector, allowing our
`low-level features to capture this local information. If the sector
`width is more than 20 pixels, then the local information may
`be modulated by more global information. The innermost band
`(circle) is not used for feature extraction because the flow field
`in a region around a very high curvature point (core) has poor co-
`herence. Thus, absolute deviations of oriented Gabor responses
`to this region would be expected to be unreliable matching fea-
`tures. Thus, we have a total of
`sectors (
`through
`) and the region of interest is a circle of radius 120 pixels,
`centered at the reference point. Eighty features for each of the
`eight filtered images provide a total of 640 (
`) features per
`fingerprint image. Each feature can be quantized into 256 values
`and requires 1 byte of storage, so the entire feature vector re-
`quires only 640 bytes of storage. In our second experiment with
`NIST 9 database (image size =
`pixels, scanned at
`500 dpi), we used seven concentric bands (
`),
`, and
`, giving us an 896 byte FingerCode.
`
`ASSA ABLOY Ex 1038 - Page 4
`ASSA ABLOY AB, et al. v. CPC Patent Technologies Pty Ltd.
`IPR2022-01093 - U.S. Patent No. 8,620,039
`
`

`

`850
`
`IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 9, NO. 5, MAY 2000
`
`Fig. 6. Estimating the reference point. (a) Smoothed orientation field overlapped on the original image. (b) Orientation field (w = 10) shown as intensity
`distribution; the background has been segmented. (c) sine component of the orientation field; the darkest pixel marks the detected reference point. Images have
`been scaled for viewing.
`
`each block [see Fig. 6(a) and (b)]. Note that there is an ambi-
`in fingerprint orientation, i.e., local ridges oriented at
`guity of
`and ridges oriented at
`cannot be differentiated from
`each other. A number of methods have been developed to esti-
`mate the orientation field in a fingerprint [20]–[23]. The least
`mean square orientation estimation algorithm [33] has the fol-
`lowing steps.
`1) Divide , the input image, into nonoverlapping blocks of
`size
`.
`2) Compute the gradients
`at each pixel
`and
`. Depending on the computational requirement, the
`gradient operator may vary from the simple Sobel oper-
`ator to the more complex Marr–Hildreth operator [24].
`3) Estimate the local orientation of each block centered at
`pixel
`using the following equations [23]:
`
`and
`
`andwhere
`components of the
`and
`, are the
`and
`vector field, respectively. With the resulting vector field,
`the low-pass filtering can then be performed as follows:
`
`(10)
`
`and
`
`(11)
`
`(12)
`
`(6)
`
`(7)
`
`(8)
`
`where
`is a two-dimensional low-pass filter with unit
`integral and
`specifies the size of the filter. Note
`that the smoothing operation is performed at the block
`level. For our experiments, we used a
`mean filter.
`The smoothed orientation field
`at
`is computed
`as follows:
`
`(13)
`
`where
`is the least square estimate of the local
`ridge orientation at the block centered at pixel
`.
`Mathematically, it represents the direction that is orthog-
`onal to the dominant direction of the Fourier spectrum
`of the
`window.
`A summary of our reference point location algorithm is pre-
`sented below.
`1) Estimate the orientation field
`a window size of
`.
`2) Smooth the orientation field in a local neighborhood. Let
`the smoothed orientation field be represented as
`. In
`order to perform smoothing (low-pass filtering), the ori-
`entation image needs to be converted into a continuous
`vector field, which is defined as follows:
`
`as described above using
`
`(9)
`
`3) Compute , an image containing only the sine component
`of
`[see Fig. 6(c)]
`
`(14)
`
`, a label image used to indicate the reference
`
`4) Initialize
`point.
`5) For each pixel
`in , integrate pixel intensities (sine
`component of the orientation field) in regions
`and
`shown in Fig. 7 and assign the corresponding pixels in
`the value of their difference
`
`(15)
`
`(see Fig. 7) were determined em-
`and
`The regions
`pirically by applying the reference point location algo-
`rithm over a large database. The geometry of regions
`and
`is designed to capture the maximum curvature
`
`ASSA ABLOY Ex 1038 - Page 5
`ASSA ABLOY AB, et al. v. CPC Patent Technologies Pty Ltd.
`IPR2022-01093 - U.S. Patent No. 8,620,039
`
`

`

`JAIN et al.: FILTERBANK-BASED FINGERPRINT MATCHING
`
`851
`
`Fig. 7. Regions for integrating E pixel intensities for A(i; j).
`
`Fig. 9. Fingerprints have well defined local frequency and orientation. (a)
`Ridges in a local region and (b) Fourier spectrum of (a).
`
`mately 1 inter-ridge distance unit) away from its “true” loca-
`tion. Fig. 8 shows the results of our reference point location al-
`gorithm.
`
`B. Filtering
`
`Fingerprints have local parallel ridges and valleys, and well-
`defined local frequency and orientation (Fig. 9). Properly tuned
`Gabor filters [25], [26], can remove noise, preserve the true
`ridge and valley structures, and provide information contained
`in a particular orientation in the image. A minutia point can be
`viewed as an anomaly in locally parallel ridges and it is this
`information that we are attempting to capture using the Gabor
`filters.
`Before filtering the fingerprint image, we normalize the re-
`gion of interest in each sector separately to a constant mean and
`variance. Normalization is performed to remove the effects of
`sensor noise and gray level deformation due to finger pressure
`differences. Let
`denote the gray value at pixel
`,
`and
`, the estimated mean and variance of sector
`, respec-
`tively, and
`, the normalized gray-level value at pixel
`. For all the pixels in sector
`, the normalized image is
`defined as
`
`if
`
`otherwise
`
`(16)
`
`are the desired mean and variance values, re-
`and
`where
`spectively. Normalization is a pixel-wise operation which does
`not change the clarity of the ridge and valley structures. If nor-
`malization is performed on the entire image, then it cannot com-
`pensate for the intensity variations in different parts of the image
`due to the elastic nature of the finger. Separate normalization of
`each individual sector alleviates this problem. Fig. 10 shows an
`example of this normalization scheme. For our experiments, we
`set the values of both
`and
`to 100.
`
`Fig. 8. Examples of the results of our reference point location algorithm. Our
`reference point location algorithm fails on very poor quality fingerprints.
`
`in concave ridges (see Fig. 5). Although this successfully
`detects the reference point in most of the cases, including
`double loops [see Fig. 8(a)], the present implementation
`is not very precise and consistent for the arch type finger-
`prints.
`6) Find the maximum value in
`and assign its coordinate
`to the core, i.e., the reference point.
`7) For a fixed number of times, repeat steps 1–6 by using a
`window size of
`, where
`and restrict the
`search for the reference point in step 6 in a local neighbor-
`hood of the detected reference point. In our experiments,
`we used three iterations with
`, and
`pixels,
`respectively, and hence the precision of the detected ref-
`erence point is 5 pixels.
`Our representation scheme is able to tolerate the imprecision
`in the reference point estimates of up to 10 pixels (approxi-
`
`ASSA ABLOY Ex 1038 - Page 6
`ASSA ABLOY AB, et al. v. CPC Patent Technologies Pty Ltd.
`IPR2022-01093 - U.S. Patent No. 8,620,039
`
`

`

`852
`
`IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 9, NO. 5, MAY 2000
`
`Fig. 10. Normalized, filtered, and reconstructed fingerprint images: (a) area of interest, (b) normalized image, (c)–(j) 0 , 22.5 , 45 , 67.5 , 90 , 112.5 , 135 ,
`157.5 filtered images, respectively, (k) reconstructed image with four filters, and (l) reconstructed image with eight filters. While four directions are sufficient to
`capture the global structure of the fingerprint, eight directions are required to capture the local characteristics.
`
`An even symmetric Gabor filter has the following general
`form in the spatial domain:
`
`(17)
`
`(18)
`(19)
`
`where
`is the frequency of the sinusoidal plane wave along the
`direction
`from the -axis, and
`and
`are the space con-
`stants of the Gaussian envelope along
`and
`axes, respec-
`tively. The spatial characteristics of Gabor filters can be seen in
`[6].
`We perform the filtering in the spatial domain with a mask
`size of
`. However, to speed up the filtering process,
`we convolve a pixel only with those values in the filter mask
`whose absolute value is greater than 0.05. This speeds up the
`
`ASSA ABLOY Ex 1038 - Page 7
`ASSA ABLOY AB, et al. v. CPC Patent Technologies Pty Ltd.
`IPR2022-01093 - U.S. Patent No. 8,620,039
`
`

`

`JAIN et al.: FILTERBANK-BASED FINGERPRINT MATCHING
`
`853
`
`convolution process significantly while maintaining the infor-
`mation content as the convolution with small values of the filter
`mask does not contribute significantly to the overall convolu-
`tion. We also make use of the symmetry of the filter to speed up
`the convolution. However, convolution with Gabor filters is still
`the major contributor to the overall feature extraction time.
`to the av-
`In our experiments, we set the filter frequency
`erage ridge frequency (
`), where
`is the average inter-ridge
`distance. The average inter-ridge distance is approximately 10
`pixels in a 500 dpi fingerprint image. If
`is too large, spu-
`rious ridges are created in the filtered image whereas if
`is
`too small, nearby ridges are merged into one. We have used
`eight different values for
`(0 , 22.5 , 45 , 67.5 , 90 , 112.5 ,
`135 , and 157.5 ) with respect to the
`-axis. The normalized
`region of interest in a fingerprint image is convolved with each
`of these eight filters to produce a set of eight filtered images. A
`fingerprint convolved with a
`-oriented filter accentuates those
`ridges which are parallel to the -axis and smoothes the ridges
`in the other directions. Filters tuned to other directions work in
`a similar way. These eight directional-sensitive filters capture
`most of the global ridge directionality information as well as
`the local ridge characteristics present in a fingerprint. We illus-
`trate this through reconstructing a fingerprint image by adding
`together all the eight filtered images. The reconstructed image is
`very similar to the original image and only been slightly blurred
`(degraded) [Fig. 10(a)] due to lack of orthogonality among the
`filters. At least four directional filters are required to capture the
`entire global ridge information in a fingerprint [Fig. 10(k)], but
`eight directional filters are required to capture the local charac-
`teristics. So, while four directions are sufficient for classifica-
`tion [6], eight directions are needed for matching. Our empir-
`ical results support our claim, we could get better accuracy by
`using eight directions for matching as compared to only four di-
`rections. By capturing both the global and local information, the
`verification accuracy is improved although there is some redun-
`dancy among the eight filtered images. If
`and
`(standard
`deviations of the Gaussian envelope) values are too large, the
`filter is more robust to noise, but is more likely to smooth the
`image to the extent that the ridge and valley details in the fin-
`gerprint are lost. If
`and
`values are too small, the filter is
`not effective in removing the noise. The values for
`and
`were empirically determined and each is set to 4.0 (about half
`the average inter-ridge distance).
`
`C. Feature Vector
`
`Let
`for
`sector
`
`feature value,
`,
`the mean defined as
`
`be
`. Now,
`
`the
`
`-direction
`
`filtered
`
`image
`and
`, the
`is the average absolute deviation from
`
`(20)
`
`where
`is the mean of
`and
`is the number of pixels in
`pixel values of
`. The average absolute de-
`in sector
`viation of each sector in each of the eight filtered images de-
`fines the components of our feature vector. Our empirical results
`show that using AAD features give slightly better performance
`
`than variance features as used in [6]. The 640-dimensional fea-
`ture vectors (FingerCodes) for fingerprint images of two dif-
`ferent fingers from the MSU_DBI database are shown as gray
`level images with eight disks, each disk corresponding to one
`filtered image in Fig. 11. The gray level in a sector in a disk
`represents the feature value for that sector in the corresponding
`filtered image. Note that Fig. 11(c) and (d) appear to be visually
`similar as are Fig. 11(g) and (h), but the corresponding disks for
`two different fingers look very different.
`
`III. MATCHING
`
`Fingerprint matching is based on finding the Euclidean dis-
`tance between the corresponding FingerCodes. The translation
`invariance in the FingerCode is established by the reference
`point. However, in our present implementation, features are not
`rotationally invariant. An approximate rotation invariance is
`achieved by cyclically rotating the features in the FingerCode
`itself. A single step cyclic rotation of the features in the Fin-
`gerCode described by (21)–(23) corresponds to a feature vector
`which would be obtained if the image were rotated by
`.
`A rotation by
`steps corresponds to a
`rotation of
`the image. A positive rotation implies clockwise rotation while
`a negative rotation implies counterclockwise rotation. The
`FingerCode obtained after
`steps of rotation is given by
`
`div
`
`(21)
`(22)
`(23)
`
`sectors in a band,
`,
`,
`,
`,
`
`where
`
`(
`
`)
`
`is the number of
`, and
`,
`.
`,
`,
`For each fingerprint in the database, we store five templates
`corresponding to the following five rotations of the corre-
`sponding FingerCode:
`,
`,
`,
`, and
`. The input
`FingerCode is matched with the five templates stored in the
`database to obtain five different matching scores. The minimum
`matching score corresponds to the best alignment of the input
`fingerprint with the database fingerprint. Since a single cyclic
`rotation of the features in the FingerCode corresponds to a
`rotation of
`in the original image, we can only generate
`those representations of the fingerprint which are in steps of
`. Due to the nature of the tessellation, our features are
`invariant to only small perturbations that are within
`.
`Therefore, we generate another feature vector for each finger-
`print during the time of registration which corresponds to a
`rotation of
`. The original image is rotated by an angle
`of
`and its FingerCode is generated. Five templates
`corresponding to the various rotations of this FingerCode are
`also stored in the database. Thus, the database contains ten
`templates for each fingerprint. These ten templates correspond
`to all the rotations on the fingerprint image in steps of
`.
`As a result, we have generated FingerCodes for every
`rotation of the fingerprint image. This takes care of the rotation
`while matching the input FingerCode with the stored templates.
`The final matching distance score is taken as the minimum of
`the ten scores, i.e., matching of the input FingerCode with each
`of the ten templates. This minimum score corresponds to the
`best alignment of the two fingerprints being matched. Since the
`
`ASSA ABLOY Ex 1038 - Page 8
`ASSA ABLOY AB, et al. v. CPC Patent Technologies Pty Ltd.
`IPR