xxxx-xxxx/0x/$xx.00 © 200x IEEE

Fig. 8. Some registration results using proposed algorithm: column (a), (b) and (c) are template images, input images and registration results, respectively.

Fig. 9. Normalized distributions of MI for same fingers and different fingers (Wd = 8, n = 18).

Fig. 10. Some registration results using our algorithm and minutiae-based algorithm: (a) Template images, (b) Input images, (c) Registration results of proposed method, and (d) Registration results of minutiae-based method.

Fig. 11. Registration result that is similar to human’s comparison: (1) Template image (2) Input image (3) Superposed gray-scale image. (4) Superposed thinning image.

paInformation Theory Based Fingerprint Matching

Lifeng Liu, Tianzi Jiang, Member, IEEE, Jianwei Yang, and, Chaozhe Zhu

Abstract—Fingerprint matching is a critical step in fingerprint verification. Although a variety of matching algorithms have been proposed, accurate fingerprint registration remains an unresolved problem. Based on information theory, we propose a new algorithm for fingerprint registration. This algorithm finds the correct alignment by maximization of mutual information between features extracted from orientation fields of template and input fingerprint images. Orientation field, representing the flow of ridges, is a relatively stable feature of fingerprint images. The primary characteristics of this method are that it uses this stable global feature to align fingerprints, and that its behavior may resemble the way humans compare fingerprints. Then, the maximal mutual information acquired in the registration stage is integrated into minutiae matching to give the final result. Experimental results show that the occurrence of misalignment is dramatically reduced and that registration accuracy is greatly improved at the same time, leading to enhanced matching performance.

Index Terms—Biometrics, fingerprints, information theory, mutual information, minutia, orientation field, registration, matching.

————————————————

The authors are with National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Sciences, Beijing 100080, P.R. China.

Email: {lfliu, jiangtz, jwyang, czzhu}@nlpr.ia.ac.cn

T. Jiang is with the Department of Computer Science, University of Houston, Texas, TX 77204-3010, USA.

Manuscript received 17 June. 2002.

——————————  ——————————

1	Introduction

F INGERPRINTS are the flow-like ridges present on human fingers. Fingerprint-based personal identification has been used for a very long time [16]. Owning to their distinctiveness and stability, fingerprints today are the most widely used biometric features. Nowadays, most automatic fingerprint identification systems (AFIS) are based on matching minutiae, which are local ridge characteristics in the fingerprint pattern. The two most prominent minutiae types are ridge ending and ridge bifurcation (Fig. 1).

Fig. 1. Ridge bifurcation and endpoint (a) Bifurcation, (b) Endpoint.

Based on the features that the matching algorithms use, fingerprint matching can be classified into image-based and graph-based matching. Image-based matching [1], [2] uses the entire gray scale fingerprint image as a template to match against input fingerprint images. The primary shortcoming of this method is that matching may seriously be affected by some factors such as contrast variation, image quality variation, and distortion, which are inherent properties of fingerprint images. The reason for such limitation lies in the fact that gray scale values of a fingerprint image are not stable features, and may change among different impressions. Another shortcoming is the large size of template required because the whole gray scale image is to be stored. In addition, in some nations it is illegal to store fingerprint images due to the possibility of invasion of privacy. Another image-based approach, i.e., matching by entire ridge structure is invariant to the brightness variations but is very sensitive to image quality.

Jain et al., have proposed an innovative image-based fingerprint matching algorithm [12]. This method first detects a reference point and then tessellates the fingerprint around this point. Afterwards, a bank of Gabor filters (oriented in eight directions) is used to construct a feature vector, called ‘FingerCode’. Thus, matching between two fingerprint images reduces to finding the Euclidean distance between two FingerCodes. The salient advantage of this method is that it can be highly efficient in matching a query fingerprint against a very large database because it uses index/retrieval mechanics. However, it is impossible to locate the reference point precisely each time, and sometimes the reference point cannot be detected at all due to poor image quality or only partial finger presented in the image. These shortcomings limit the application of this method for reliable identification.

Graph-based matching [5], [8] represents the minutiae in the form of graphs. The high computational complexity of graph matching hinders its implementation. To reduce the computational complexity, matching the minutiae sets of template and input fingerprint images can be done with point pattern matching. Several point pattern matching algorithms have been proposed and commented on the literature [9], [10], [19], [22], [23]. Point pattern matching is generally intractable due to the lack of knowledge about the correspondence between two point sets. To address this problem, Jain et al. proposed alignment-based minutiae matching algorithms [9], [10]. Two sets of minutiae are first aligned using corresponding ridges to find a reference minutiae pair, one from the input fingerprint and another from the template fingerprint, and then all the other minutiae of both images are converted with respect to reference minutiae. Afterwards, the aligned point patterns are compared to give a matching result. Jiang et al. also proposed an improved method [13], using minutia together with its neighbors to find the best registration. All of these approaches may fail when the correct alignment cannot be recovered in fingerprint images with poor quality.

Fig. 2. Block diagram of our system. This paper proposes a novel fingerprint registration algorithm, in which the best alignment of two fingerprint images, template and input, is achieved by maximization of mutual information between features extracted from their orientation fields. Then, matching result is determined jointly from minutiae matching and the maximal mutual information achieved during registration. The orientation field of a fingerprint image, a relatively stable feature independent of fingerprint capture devices and image contrast variation, represents the intrinsic nature of the fingerprint images and can be generally estimated reliably. When humans compare fingerprints, we may first use global structures like ridge flows to find the correspondence of two fingerprints and then use local characteristics such as minutiae to give a matching result. Our automated method emulates this behavior. In minutiae matching, the registration result can be integrated into the final decision. Experimental results show that our algorithm achieves correct registration and very good verification performance. The block diagram of our system is shown in Fig. 2.

The rest of this paper is organized as follows. Section 2 gives the definitions of entropy and mutual information. In section 3, our feature extraction method is briefly described. Section 4 is devoted to our information theory based matching algorithm. Experimental results on fingerprint databases are described in section 5. Summary and discussions are outlined in the last section.

2	Entropy and Mutual Information

Entropy

Entropy is a statistical measure that summarizes randomness. Given a discrete random variable, its entropy is defined by

(1)

whereis the sample space andis the member of it. represents the probability when takes on the value. We can see in equation (1) that the more random a variable is, the more entropy it will have.

Conditional Entropy, Joint Entropy and Mutual Information

Conditional and joint entropy relate the predictability of two random variables. Conditional entropy and joint entropy are defined as:

(2)

(3)

Conditional entropy measures the randomness of when is given, and joint entropy measures the randomness of and . With the increase of , gets more dependent on . However, conditional entropy by itself is not a measure of dependency. A small value of implies either is small or is less dependent on .

When and are independent, (2) and (3) can be expressed using and :

(4)

(5)

Mutual information, MI, between two random variables is defined as:

(6)	(7)

Because conditional entropy can be expressed in terms of marginal and joint entropies:

.	(7)	(8)

Fig. 3. Fingerprint image and its mean directions in different blocks. The size of each block is 88. We can get two equivalent expressions for MI:

,	(8)	(9)

.	(9)	(10)

MI measures the statistical dependency between two random variables. The physical meaning of MI is the reduction in entropy of given.

Viola et al. proposed [25] that registration could be achieved by maximization of mutual information. Registration using MI is widely used in medical image registration, and it has achieved excellent results for rigid registration. In this paper, we apply MI to fingerprint registration. To the best of our knowledge, this is the first attempt to apply this concept in biometrics. The details will be described in Section 4.

3	Feature Extraction

In feature extraction, we want to extract both the orientation field and the minutiae, i.e. endpoints and bifurcations, of both template and input fingerprint images. Orientation field is a reliable feature of fingerprint images, which can be exploited for fingerprint enhancement, minutiae extraction and matching in our method. Minutiae are other stable feature upon which most matching algorithms are based.

Normalization and Segmentation

To increase the estimation accuracy of the orientation field, we first normalize fingerprint images using the algorithm described in [7] to adjust the contrast of images. Then, we extract region of interest from the normalized images.

Orientation Field Estimation

Fingerprint images can be regarded as oriented texture patterns. The orientation field of a fingerprint image is an intrinsic nature. In our algorithm, orientation field plays a crucial role in enhancing and aligning fingerprint images.

Rao et al. proposed an algorithm to estimate the orientation of texture images [20]. Rao’s algorithm consists of three main steps:

divide the input fingerprint image into blocks of size (in our experiments),

compute the gradientsandat each pixel in each block, and

estimate the local orientation of each block using the following equation:

(10)	(11)

where andare the gradient magnitudes in x and y directions, respectively. Finally, is normalized into the range of . We use a sliding window technique to efficiently extract every pixel’s direction in the entire fingerprint image [27].

Direction Feature Extraction

After the orientation field is estimated, we calculate direction features. During fingerprint template enrollment, we divide the whole fingerprint image into blocks and the mean of directions in each block is computed. All the directions of computed blocks are stored as features for registration described later. Fig. 3 shows a fingerprint and its mean directions in different blocks.

Fingerprint Image Enhancement

We use an improved Gabor filter to enhance fingerprint images [28]. Fig. 4 shows a result using this algorithm.

Minutiae Extraction

Enhanced fingerprint images are binarized using locally adaptive binarization method [24]. Then they are thinned as described in [3]. We assume that a pixel on a thinned ridge has a value of 1, with pixel values of 0 otherwise. After images are thinned, minutiae can be easily detected by counting the occurrences of 1 in its eight neighbors of a pixel located on a ridge [9]. Parameters of x-coordinate, y-coordinate, direction, and type are recorded for each detected minutia. Finally, a post-processing algorithm similar to that in [4] is used to eliminate false minutiae and to validate genuine ones.

Fingerprint Matching

The purpose of fingerprint matching is to determine whether two fingerprints, template and input, are from the same finger. To this end, we assume that minutiae and direction features of the template fingerprint image have been extracted during enrollment, and the minutiae and orientation field of the input fingerprint image have been extracted in the feature extraction stage. Here we match fingerprint images using minutiae and direction features. Since we do not have any prior knowledge about the relative position of template and input fingerprint images, we must first align them to get the correct correspondence. Then matching comparison of two sets of minutiae is carried out to get the matching result. Our method of matching can be divided into two stages: registration and matching.

Fig. 4. Result of enhanced fingerprint images using improved Gabor filter: (a) Original fingerprint image. Registration Using Mutual Information

Registration or alignment is a process through which the correct transformation is determined. Registration using mutual information is a method of maximization of similarity measures. It uses mutual information as the similarity measure and aligns images by maximizing mutual information between them under different transformations. In our method, orientation fields of two fingerprint images are regarded as two random variables. Then, mutual information is used to measure the similarity or correlation between these two random variables. Mutual information describes the uncertainty in estimating the orientation field at a certain location given another orientation field. The more similar or correlated the orientation fields are, the more mutual information they have.

The definitions of entropy and mutual information, MI, have been given in Section 2. Here we use MI between template and input’s direction features to align the fingerprints. Although MI can be estimated using equations (6), (7), or (9), the difficulty of estimating conditional entropy of two random variables hinders the application of both (6) and (7). Fortunately, we can estimate MI using (9) with some conversion of random variables.

In our registration algorithm, we assume that distortion is not very large. Since distortion in fingerprint images is usually nonlinear and difficult to represent, a complex and time-consuming non-rigid registration is required if one wants to remediate distortion exactly. But in most circumstances, this is not necessary if distortion is not very large because minutiae matching can usually compensate for some distortions. Registration by maximization of mutual information can also tolerate certain distortions, so this approach can be used for general purpose. If distortion is large, this method is not appropriate.

Given a transformation, the orientation field of the input fingerprint image can be transformed into the template coordinate system:

(11)	(12)

Then, the transformed orientation field image is superposed on the template image (which is not present in the matching stage). The resulted image is divided into blocks in the same way as was the template image during enrollment (see Fig. 6(a)). The mean direction of each overlapped block can be computed the same way as calculating the mean direction of the template image. To keep the reliability of the mean direction, from experimental results, we drop the blocks whose overlapped size is less than four-fifths of the whole block size (blue blocks in Fig. 6(a)). When the number of overlapped blocks is less than one-third (selected based on experimental results) of the entire valid direction blocks in the template image, the transformation is discarded because too small an overlapped size usually means a false registration, and as a result some images from the same fingers may not be aligned. This is understandable because when the overlapped area is small, there is insufficient evidence to verify whether the two images are from the same finger or images from different fingers are accidentally aligned. The computation of mutual information also requires that there are adequate samples to estimate distributions correctly.

The mean direction ranges from, inclusive. For expression convenience, we convert this to , inclusive. In order to estimate MI, the continuous direction needs to be evenly discretized and the continuity between and should be reserved:

(12)	(13)

where is the number of discrete directions.

Having discretized both the template and transformed input mean directions, we can define joint probability of an overlapped block (see Fig. 5). For example, if the mean direction of the template of a certain block falls into the range of and the corresponding transformed input mean direction falls into the range of , then the elementof joint probability adds one. After all the overlapped blocks are examined, we can get the joint and marginal probability distributions using the following equations:

(13)	(14)

then MI of a given transformation can be estimated using equations (1), (3) and (10).

Fig. 5. Estimation of joint distribution. We have put forward an approach to estimate MI between mean directions of template and input fingerprint images given a transformation. Now, we need to search the parameter space to find the maximal MI so that the best registration between two fingerprints can be obtained. Fig. 6 (b) shows the 3-D searching space of rotation and translation of and . Although the parameter space is not very large, it is still time-consuming to search the whole parameter space pixelwise (in our experiments, we set ranges of these parameters to make majority of images fall into these ranges). To resolve the contradiction between processing time and accuracy, we use a hierarchical approach: coarse and fine registration.

In coarse registration, we search the parameter space with a relatively large step to find the maximal MI, indicating an approximate alignment. It should be noticed that, if the searching step is too large, the algorithm may be trapped in local maxima and the best registration won’t be found. If the searching step is too small, the computational requirements will be very heavy. So this is a trade-off between efficiency and accuracy. Then in fine registration, we find the best transformation in the subspace around the parameters found in coarse registration. The best transformation with maximal MI can usually be found using the above-mentioned strategy and the corresponding MI and transformation are recorded for matching described below.

Matching

In this section, we will judge whether two fingerprints are from the same finger or not based on maximal MI and minutiae matching. Since our registration result resembles human comparison of fingerprints, we can define four categories of situations in practical comparison of fingerprints:

from the same finger with high similarity (large MI);

from the same finger but with less similarity because of noise or small area of overlapped sections (medium MI);

Fig. 6. Graphic representation of transformation and search space: (a) Orientation field of input fingerprint image is superposed on imaginary template orientation field, (b) Search space. from different fingers but with high similarity, possibly because they belong to the same class (medium MI); and

TABLE 1 Errors of Registration	Algorithm	Parameters	DB-b	DB1	DB2	DB3	DB4
Proposed	Wd = 8, n = 9 6 14 47 107 71 Wd = 8, n = 18 9 16 57 115 80 Wd = 8, n = 36 49 59 92 162 130
Minutiae-based	—	55	—	—	—	—
Fig. 7. A result of coarse and fine registration: (a) Template fingerprint image, (b) Input fingerprint image, (c) Result of coarse registration, (d) Result of fine registration. from different fingers with little similarity (small MI).

By thresholding MI, we can partially differentiate 1 and 4 from 2 and 3. When MI is greater than a threshold , we say that the two fingerprints are from the same finger, 1. And if MI is less than a threshold , we judge that the two fingerprints come from different fingers, 4. The other two cases 2 and 3 cannot be differentiated solely from MI, so we use minutiae matching to discriminate them [21].

Experimental Results

We have tested our novel fingerprint matching algorithm on the databases downloaded from Università di Bologna, Italy (DB-b) and FVC2000 databases (set B). DB-b contains 168 fingerprint images from 21 different fingers with 8 images per finger. The size of these images is 256256. Databases from FVC2000 consist of four databases (DB1, DB2, DB3 and DB4) with resolutions of 300300, 364256, 478448, and 320240, respectively [18]. Each of these four databases (set B) consists of 10 fingers with 8 images per finger. These fingerprint images vary in quality.

5.1 Registration

In our experiments, we use all the five databases to test our registration algorithm. We set different ranges of rotation and translation of and for each database to make majority of images fall into these ranges. Each image is aligned with all the others in the same database, so a total of 28056 (167168) registrations for DB-b and 6320 (7980) for each of the FVC2000 databases are performed. Since images in DB3 have a larger size, if we align them using the original images directly, the process will be very much slower than smaller images. So instead we use a down-sampling technique (taking every other point in each row and column) to reduce processing time. Down-sampling will not degrade registration accuracy significantly because the orientation field will not change much when down-sampled. After the orientation field has been estimated, we down-sample the orientation field (taking every other point in both rows and columns) to get a 239224 field. Then, registration is carried out on the down-sampled orientation field. Once the best registration for the down-sampled images is found, the transformation parameters are adjusted to the original images: the rotation parameters of original images are the same as that of the down-sampled ones, while translation parameters of original images are two times of those of down-sampled ones. Finally, registration is optimized on the original images by slightly varying the transformation parameters found for the down-sampled images (rotation is the same, and translation of and is varied by one pixel).

TABLE 2 Average Processing Time for Registration on a Pentium 4, 1.3GHz CPU with 128MB RAM DB-b (seconds)DB1 (seconds)DB2 (seconds)DB3 (seconds)DB4 (seconds)Wd = 8, n = 91.1132.0562.2051.29121.866Wd = 8, n = 181.2252.2142.4161.38311.982Wd = 8, n = 361.3672.4672.6841.47232.103 TABLE 3 Statistics of Translation and Rotation on Different Databases Translation X (pixel)Translation Y (pixel)Rotation (degree)MeanStandard DeviationMaxMeanStandard DeviationMaxMeanStandard DeviationMaxDB-b15.5312.957425.2924.211321.472.5614DB133.7832.1914851.3740.691572.313.0615DB231.2125.2513747.0939.111902.713.3616DB319.7817.8612931.7625.871252.773.4418DB439.4928.1212839.9131.071559.496.39522 We use a three-level hierarchical registration. The size of the window used to compute mean direction is 88. The number n of discretized mean direction is 9, 18, and 36, respectively. Fig. 7 shows the result of course and fine registration. Fig. 8 shows some registration results of different image qualities. In this figure, the first row demonstrates that when overlapped part is relatively small, the right registration could still be found, and the other three rows demonstrate that proposed algorithm could correctly align fingerprint images with certain noises and scars. Fig. 9 shows normalized distributions of MI for same and different fingers in DB-b (= 8 and = 18). Table 1 lists the numbers of misalignment of same fingers for different parameters after manual check. The number of misalignment of DB-b using minutiae matching [21] is also listed in the same table. From these results we can see that our algorithm is superior to general minutiae-based registration in the reduction of false registrations. We also observed that when n is large, for example = 36 in our experiments, the errors of misalignment dramatically increased. They are quite stable when n is decreased to 18 and 9 in our experiments. One reason for this phenomenon is that when n gets larger, the mean direction is discretized more accurately and more sensitive to orientation field estimation. As a result, small changes in mean direction may greatly affect its distribution. Another reason is that the number of mean direction samples is too few to estimate distribution correctly. Thus, when n is large, registration is much more sensitive to image quality, resulting in an estimation of orientation field with reduced accuracy. On the other hand, if n is small, misalignments will decrease but so will registration accuracy. A balanced value for n must be found.

After manually checking registration results, we find that there are several reasons for false alignment. The most prominent one is that the size of overlapped area is too small. It is required that enough samples be present for the mutual information method to correctly estimate distribution of orientation field. So when there are an inadequate number of samples, it is less possible for the mutual information method to find the correct alignment. This is most evident in the 9th and 10th fingers of DB3, and 105_6 of DB2, in which most fingerprint images cannot be aligned. A second reason for false alignment is poor image quality. Although registration using mutual information can tolerate some noises, the correct result cannot be obtained when a large part of orientation field cannot be estimated correctly. Many noisy images, such as the 9th finger of DB2, can be aligned well. But some images, such as the 8th finger of DB2 and the 5th finger of DB3, are seriously corrupted by noises and blemishes, so registration results for these images are not good. DB4 contains synthesized images and orientation fields of many of these images cannot be estimated reliably. As a result, registration results on this dataset are not good. The third reason is distortion. When distortion is not very large or only exists in a small portion of an image, our method can find relatively good registration (some parts of the images may not align well due to distortion). When distortion is very large or exists in a large portion of an image, correct registration cannot be achieved. Finally, some images are occasionally not aligned due to the coarse-to-fine registration mechanism. Sometimes registration results may be trapped at local maxima during coarse registration.

Our registration algorithm was implemented using Visual C++ program in an IBMTM PC compatible with Pentium 4, 1.3GHz processor with 128MB RAM. Table 2 shows average processing time. Processing time is effected by many factors, such as the size of the parameters space, the size of the region of interest, and the number n of discretized mean directions. Table 3 lists registration statistics for same comparisons in these databases. In computing these statistics, we exclude those images that are falsely aligned. The time to compute the logarithm in the mutual information equation takes the largest part of the total processing time, so making this calculation more efficient will speedup registration. We have tried to use the Least Square Mean (LSM) method to measure the similarity of orientation fields, but the result is worse than mutual information. For same comparisons in DB-b ( = 8 and = 18), there are 35 misalignments using LSM method, while there are only 9 misalignments using mutual information method. For many correct aligned images, the registration accuracy of LSM method is worse than that of mutual information method.

Generally, our proposed algorithm can align two fingerprint images more accurate than minutiae-based methods. Fig. 10 shows some comparisons of registration results. In Fig. 11, an example of registration, which is similar to registration by humans, is demonstrated. From all of these experimental results we can argue that the proposed algorithm is quite robust and accurate.

Fig. 12. Receiver operating characteristic curves of three algorithms. 5.2 Matching

In experiments for minutiae matching, we use three algorithms based on [21]. Algorithm A uses the method described in [21] to align and match fingerprint images solely using detected minutiae. Algorithm B uses the registration of our algorithm and the same minutiae matching method as in A. Algorithm C is the same as B except that we use MI to initially differentiate same and different fingers as described in Section 4.2. We set both the width and height of elastic box to 10, and the largest difference of minutiae direction to . We also set = 8 and = 18 in the registration phase of algorithm B and C. In algorithm C, and of MI, as described in Section 4.2, is set to 2.0 and 1.2, respectively.

The receiver operating characteristic curves (ROCs) [7] of the tests for the three algorithms are shown in Fig. 12. From the results, we can observe that the performance of proposed registration method is much better than the minutiae-based method in verification rate. We observe that matching errors are caused mainly by inaccurate minutiae detection, which is seriously effected by image quality. We can improve this by excluding poor fingerprint images and implementing a better feature extraction algorithm. In addition, inaccurate registration caused by distortion also affects the matcher performance.

Conclusions and Future Work

We have proposed a novel fingerprint registration algorithm. The orientation field of fingerprint images, a relatively stable feature representing global characteristics of fingerprints, is introduced into fingerprint registration. Mutual information is used to measure the similarity between orientation fields. Then, registration between two fingerprints is achieved through maximization of mutual information between features extracted from their orientation fields. The primary characteristic of our algorithm is that it uses relatively stable global characteristics to align fingerprints, which may resemble the human behavior when comparing two fingerprints. As a result, the errors of misalignment, which often occur in a minutiae-based registration algorithm, are dramatically decreased, resulting in better verification performance. Finally, the matching result is jointly determined by the maximal mutual information acquired in the registration stage and minutiae matching. Experimental results show that our algorithm can generally find the accurate registration and can achieve better verification performance than approaches using only minutiae matching.

We use mutual information as similarity measure and use a hierarchical approach to speedup registration. There may be other similarity measures and optimization methods which work better and are more efficient. Based on the experimental results, we find that registration errors mainly result from small overlapped areas. Registration using mutual information requires adequate samples to correctly estimation distribution, but this is not satisfied when overlapped area is too small. This is not serious in practice because when the overlapped area becomes too small, there will be insufficient evidence to verify whether two images are from the same finger. Image quality may also affect registration results. Although our method can tolerate some inaccuracy or errors in the estimation of orientation field, it may not do well when images are seriously corrupted, making it impossible to correctly estimate orientation field. In such cases, other method, such as minutiae-based approaches, may also fail. So restoration of corrupted images becomes very important for all methods. Distortion through elastic deformation is indeed the most serious and difficult problem to be solved. There is always nonlinear distortion existing in fingerprint images because of the elasticity of skin. If distortion is very large, it will seriously affect registration and matching results. Distortion is usually compensated in elastic minutiae matching, which may, however, increase the likelihood of false matching. Further study is needed account for distortion during registration.

Acknowledgements

The authors are highly grateful to five anonymous reviewers for their significant and constructive critiques and suggestions, which improved the paper very much. We would like to thank Xiaochuan Pan at University of Chicago for his careful proof reading of the manuscript. We also thank our colleagues for useful discussion. This work was partially supported by Hundred Talents Programs of the Chinese Academy of Sciences, the Natural Science Foundation of China, Grant No. 60172056 and 697908001, and Watchdata Digital Company. We would like to acknowledge our gratitude to the Università di Bologna of Italy for access to their fingerprint database for testing our algorithm.

References

Access Control Applications Using Optical Computing. http://www.mytec.com/. 1997.

R. Bahuguna, “Fingerprint Verification Using Hologram Matched Filterings,” Proc. Biometric Consortium Eighth Meeting, San Jose, California, June 1996.

Y. S. Chen and W.H. Hsu, “A Modified Fast Parallel Algorithm for Thinning Digital Patterns,” Pattern Recognition Letters, vol. 7, no. 2, pp. 99-106, 1988.

A. Farina, Z.M. Kovács-Vajna, and A. Leone, “Fingerprint Minutiae Extraction from Skeletonized Binary Images,” Pattern Recognition, vol. 32, no. 5, pp. 877-889, 1999.

S. Gold and A. Rangarajan, “A Graduated Assignment Algorithm for Graph Matching,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 4, pp. 377-388, 1996.

R.M. Haralick, L.T. Watson, and T.J. Laffey, “The Topographic Primal Sketch,” Int. J. Robotics Research, vol. 2, pp. 50-72, 1983.

L. Hong, Y.F. Wan, and A. Jain, “Fingerprint Image Enhancement: Algorithm and Performance Evaluation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 8, pp. 777-789, August 1998.

D.K. Isenor and S.G. Zaky, “Fingerprint Identification Using Graph Matching,” Pattern Recognition, vol. 19. no. 2, 1986.

A. Jain, L. Hong, and R. Bolle, “On-line Fingerprint Verification,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 4, pp. 302-314, 1997.

A.K. Jain, L. Hong, S. Pankanti, and R. Bolle, “An Identity Authentication System Using Fingerprints,” Proc. Of the IEEE, vol. 85, pp. 1365-1388, Sep. 1997.

A.K. Jain, S. Prabhakar, and S. Chen, “Combination Multiple Matchers for a High Security Fingerprint Verification System,” Pattern Recognition Letters, vol. 20, pp. 1371-1379, 1999.

A.K. Jain, S. Prabhakar, L. Hong, and S. Pankanti, “Filterbank-Based Fingerprint Matching,” IEEE Trans. Image Processing, vol. 9, no. 5, pp. 846-859, 2000.

X. Jiang and W. Yau, “Fingerprint Minutiae Matching Based on the Local and Global Structures,” International Conference on Pattern Recognition, pp. 1038-1041, Spain, 2000.

T. Kamei and M. Mizoguchi, “Fingerprint Preselection using Eigenfeatures,” CVPR98: Proceedings of Computer Vision and Pattern Recognition 98, Santa Barbara, CA., June 23-25, 1998, pp. 918-923.

Z.M. Kovács-Vajna, “A Fingerprint Verification System Based on Triangular Matching and Dynamic Time Warping,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no.11, pp. 1266-1276, 2000.

H.C. Lee and R.E. Gaensslen, eds., Advances in Fingerprint Technology, New York: Elsevier, 1991.

D. Maio and D. Maltoni, “Direct Gray-scale Minutiae Detection in Fingerprints,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 1, pp. 27-38, 1997.

D. Maio, D. Maltoni, R. Cappelli, J.L. Wayman, and A.K. Jain, “FVC2000: Fingerprint Verification Competition,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 3, pp. 402-412, March 2002.

A. Ranade and A. Rosenfeld, “Point Pattern Matching by Relaxation,” Pattern Recognition, vol. 12, no. 2, pp. 269-275, 1993.

A. Rao, A Taxonomy for Texture Description and Identification, New York: Springer-Verlag, 1990.

N. Ratha, K. Karu, S. Chen, and A. K. Jain, “A Real-Time Matching System for Large Fingerprint Databases,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 8, pp. 799-813, 1996.

J.P.P. Starink and E. Backer, “Finding Point Correspondence Using Simulated Annealing,” Pattern Recognition, vol. 28, no. 2, pp. 231-240, 1995.

J. Ton and A.K. Jain, “Registering Landset Images by Point Matching,” IEEE Trans. Geoscience and Remote Sensing, vol. 27, no. 5, pp. 642-651, 1989.

O.D. Trier and A. Jain, “Goal-Directed Evaluation of Binarization Methods,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 12, pp. 1191-1201, 1995.

P. Viola, “Alignment By Maximization of Mutual Information,” Ph. D thesis, M.I.T. Artificial Intelligence Laboratory, 1995.

W.M. Wells III, P. Viola, H. Atsumi, S. Nakajima, and R. Kikinis. “Multi-modal Volume Registration by Maximization of Mutual Information", Medical Image Analysis, 1(1):35-51, 1996.

J. Yang, L. Liu and T. Jiang, “An Improved Method for Extraction of Fingerprint Features,” Proc. International Conference on Image and Graph, August 2002, Anhui, China.

J. Yang, L. Liu, T. Jiang, and Y. Fan, “A Modified Gabor Filter Design Method for Fingerprint Image Enhancement,” Pattern Recognition Letters, vol. 24, no. 12, pp. 1805-1817, Aug. 2003.

Lifeng Liu received the BEng degree in Communications Engineering from Changchun Institute of Posts and Telecommunications (now College of Communication Engineering, Jinlin University), China, in 2000. He is currently pursuing his MEng degree in Institute of Automation, Chinese Academy of Sciences. His research interests include image processing, computer vision, computer graphics and pattern recognition.

Tianzi Jiang received the B.Sc. degree in computational mathematics from Lanzhou University, China, in 1984, the M.Sc. degree in applied mathematics and Ph.D. degree in computational mathematics from Hangzhou University (now Zhejiang University), China, in 1992 and 1994, respectively. From 1984-1989, he was an associate lecturer at Suzhou Silk Engineering Institute. Then he worked as a postdoctoral research fellow (1994-1996) and an associate research professor (1996-1999) at the National Laboratory of Pattern Recognition (NLPR), Institute of Automation, Chinese Academy of Sciences. From 1997-1999, he was a Vice-Chancellor's postdoctoral research fellow at the University of New South Wales, Sydney, Australia, while adjunctively with NLPR. From 1999-2000, he was a visiting scientist at the Max-Planck Institute of Cognitive Neuroscience, Leipzig, Germany. From 2000-2001, he was a research fellow at the Queen's University of Belfast, UK. Since 2001, he is a full professor and the director of Medical Imaging and Computing Group at the National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Sciences, supported by the Hundred Talents Programs of the Chinese Academy of Sciences. His research interests include functional brain imaging, medical image analysis, computer vision, computer graphics and visualization, evolutionary computation in image processing and bioinformatics, protein structure prediction, and applied mathematics. He is the author of over 50 reviewed journal papers in these fields. Dr. Jiang is on the editorial boards of International Journal of Computer Mathematics (2002-present) and The Chinese Journal of Medical Imaging and Technology (2003-present). He is a member of the scientific committees of several international conferences. He won the Natural Science Award of the Chinese Academy of Sciences in 1996.

Jiangwei Yang received his B.Sc. degree in automation from Tianjin University, P. R. China, in 2000. He is currently a M.Sc. candidate in the National Laboratory of Pattern Recognition, Institute of Automation of Chinese Academy of Sciences. His research interests include biometrics, image processing, pattern recognition, and computer vision.

Chaozhe Zhu received the BEng degree in Electrical Engineering from XiDian Uni., China, in 1996; received the M.Sc. degrees in Control Engineering from Beijing Institute of Technology, China, 2001. He is currently pursuing his Ph. D degree in Institute of Automation, Chinese Academy of Sciences. His research interests include medical image segmentation, statistical shape analysis.

AUTHOR: TITLE	10

10	IEEE TRANSACTIONS ON XXXXXXXXXXXXXXXXXXXX, vol. #, no. #, MMMMMMMM 1996

IEEE TRANSACTIONS ON Pattern Analysis ANd machine intelligence, manuscript #116785	10

Transaction / Regular Paper Title

New styles and page layout for 1996.

lfliu

2003-06-05T09:29:00

Rainer Bielefeld