Fingerprint verification method and apparatus based on global ridgeline

This invention refers to a fingerprint verification method and apparatus based on global ridgeline. Firstly, the invention search base point pair between the stored fingerprint template and the fingerprint template to be matched. The said base point pair is the positioning reference for position calibration between the stored fingerprint template and the fingerprint template to be matched. Secondly, generates fingerprint template after minutiae extraction with additional use of thinned global fingerprint ridgeline information. Then, observe similarity of minutiae topological structure or surrounding ridgeline distribution to determine base point pairs. Finally, align two fingerprints through base point pair alignment. Calculate matching ratio of ridgelines to determine whether two fingerprints match. Beneficial results of present invention: By using global ridgeline information, efficiency of searching & interference resistance capacity is greatly enhanced. Present invention overcomes disadvantage of fingerprint verification method based on minutiae, i.e. difficulty to verify fingerprints with too few minutiae points.

FIELD OF INVENTION

This invention relates generally to a method and apparatus for fingerprint verification; and more particularly refer to a fingerprint verification method and apparatus based on global ridgeline.

BACKGROUND OF THE INVENTION

Fingerprint verification is the process to determine whether two fingerprints are taken from the same finger. There are various methods of fingerprint verification. The most commonly used is called the fingerprint verification based on minutiae. Its working theory is as follows: (1) generate fingerprint templates by extracting minutiae (mainly refers to ridgeline ends and ridgeline bifurcations); (2) check the number of identical minutiae from the two templates; and (3) get verification results based on the number of identical minutiae.

As two fingerprints shall be placed on the same system in order to conduct fingerprint verification, therefore it is necessary to determine base point pair and align the two fingerprint images. There are various ways to search base point pair. The most commonly used method is to search base point pair in terms of minutiae type, minutiae direction and ridgeline curve.

The Chinese Patent case No. ZL88108482.4 (Publication No. CN1054225C) reveals an automatic fingerprint verification method. By comparing the minutiae of each fingerprint in the fingerprint database with that of the pre-calculated vector image of the to-be-verified fingerprint, the method is able to tell whether there is consistency between the fingerprint minutiae in database and the minutiae image of the to-be-verified fingerprint in terms of position and angle. The aforesaid fingerprint verification method is actually the improved version of the fingerprint verification method based on minutiae. The advantages of fingerprint verification method based on minutiae lie on the small size of fingerprint template and the high verification speed. Its disadvantages are: low efficiency in searching base point pair; inclination to lose true minutiae due to noise interference and image processing, which normally results in low identification rate; that it requests adequate number of minutiae to conduct valid verification, which normally results in limited application.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a fingerprint verification method and apparatus based on global ridgeline. The said invention generates fingerprint template after minutiae extraction with additional use of thinned global fingerprint ridgeline information. Then, observe the similarity of minutiae topological structure or the surrounding ridgeline distribution to determine base point pairs. Finally, align the two fingerprints through base point pair alignment. Calculate the matching ratio of the ridgelines to determine whether the two fingerprints match.

The technical solution of the present invention to overcome the disadvantages includes the following steps:1. Search base point pair between the stored fingerprint template and the fingerprint template to be matched. Base point pair is the positioning reference points for postural calibration between the stored fingerprint template and the fingerprint template to be matched.2. Conduct global verification. Conduct global verification between ridgeline points of the stored fingerprint template and that of the fingerprint template to be matched (Ridgeline is composed by ridgeline points) and check if the two fingerprints match. The realization is further done through the following 4 steps:2.1 Fingerprint Template Postural Calibration: Taking Base Point Pair as the alignment target and calculate the translation value & revolving value. Then align the template to be matched T2to the stored template T1.2.2 Obtain the total number (S1) of ridgeline points in overlapping area for T2: Align the template to be matched T2to the stored template T1, there will be an overlapping area. Calculate the number of ridgeline points of T2in the overlapping area and mark the number as S1;2.3 Ridgeline Point Verification: Check the number of all the ridgeline points of the template to be matched T2in the overlapping area and mark the number as S2;2.4 Calculate the match ratio between the stored fingerprint template and the template to be matched. Compare the result with the judgment threshold value T and output verification result.

The beneficial results of the present invention:

By using global ridgeline information, the efficiency of searching & interference resistance capacity is greatly enhanced. In addition, the present invention overcomes the disadvantage of the fingerprint verification method, i.e. the difficulty to verify fingerprints with too few of minutiae points.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

The following statement with illustration & example is the further description to the present invention. The present invention, a fingerprint verification method based on global ridgeline as shown inFIG. 1, mainly includes the following steps:1. Search base point pair between the stored fingerprint template & the fingerprint template to be matched. Base point pair is the positioning reference points for postural calibration between the stored fingerprint template and the template to be matched. Base point pair searching is an important step in the whole fingerprint verification process. The accuracy of base point pair searching directly influences the performance of the invention. The said base point pair point searching method is as per below:a) Establish the topological structure among minutiae. The following three characteristic values are required in order to establish topological structure among minutiae P1and P2. SeeFIG. 2for illustration.

1) dDistance between minutiae2) αThe clockwise angle formed between direction of P1and P1P23) βThe clockwise angle formed between direction of P2and P1P2b) Let us set T1as the stored template; T2as the template to be matched; Pias randomly taken minutiae in T1, and Qias randomly taken minutiae in T2. Search base point pair in the following steps:1) Assume Piand Qibelong to the same type of minutiae (either ridgeline ends or ridgeline bifurcations), and the direction error is less than threshold value. Observe the similarity of the ridgeline distribution of Piand Qiby taking Piand Qias the reference point respectively. Pjis any minutiae other than Piin T1, and Qjis another random minutia other than Qiin T2. The topological structure between Pjand Piis marked as A; the topological structure between Qjand Qiis marked as B. If the 3 characteristics values of A and B respectively are less than the corresponding threshold value, A and B are regarded as identical topological structure. Calculate the number of identical topological structure of Piand Qiin the same way. This number indicates the similarity of Piand Qi.2) Repeat the steps in 1) to all the minutiae in T1and T2. Save the minutiae, whose similarity is not zero, into a queue, and put them in sequence from high similarity to low.3) If there are minutiae in the queue, select several pairs of base point for global verification. If there are no minutiae existing in the queue, please go to step c).c) Assume Piand Qibelong to the same type of minutiae (either ridgeline ends or ridgeline bifurcations), and the direction error is less than threshold value. Observe the similarity of the ridgeline distribution of Piand Qiwithin the reference ranges centered on Piand Qirespectively with R as radius for both ranges.1) Align Qito Pi(including position and direction), all ridgeline points within Qireference range will change with Qi. Calculate the number of identical ridgeline points in T1and T2within their respective reference range. This number indicates the similarity between Qiand Pi.2) Repeat the above steps to all the minutiae in T1and T2. Save the minutiae, whose similarity is not zero, into a queue, and put them in sequence from high similarity to low.3) Select several pairs of base point in the queue for global matching.2. Conduct global verification. Conduct global verification between ridgeline point from both the stored fingerprint template T1and the template to be matched T2(Ridgeline is composed by ridgeline points). The realization is done through the following 4 steps:2.1 Fingerprint Template Postural Calibration: The stored fingerprint template and the template to be matched must be placed in the same system in order to conduct global ridgeline verification. Take Base Point Pair as the alignment target and calculate the translation value & revolving value. Then align the template to be matched T2to the stored template T1as shown inFIG. 4.2.2 Obtain the total number (S1) of ridgeline points in overlapping area for T2Align the template to be matched T2to the stored template T1there will be an overlapping area. Calculate the number of ridge point of T2in the overlapping area and mark the number as S1.2.3 Ridgeline Point Verification:

The verification method based on minutiae generally refers to verification among minutiae from different templates. Whether two fingerprints match depends on the matching ratio of minutiae. The present invention takes into consideration of the global ridgeline information. It verifies all ridge points in the template to see whether two fingerprints match. Minutiae in this case are regarded as base point used for postural calibration. SeeFIG. 5for ridgeline point verification:a) Take a random point pifrom any ridgeline in the template to be matched T2;b) Set an area centered on piwithin the distance of m pixel points as the search area. Search all the ridge points in the stored template T1within the search area. If there is ridge point in T1found, go to step c). If no, set pias invalid point.c) Repeat the step b) for the n ridge points other than pion the same ridge in T2;d) If ridgeline points from T1can be found within the search area of the n ridge points and the ridgeline points found are located on the same ridgeline in T1, then pishall be regarded as valid point. Otherwise, pishall be regarded as invalid point.

Observe all the ridge points in T2in the overlapping area and calculate the total number (S2) of valid point.2.4 Calculate the match ratio of the stored fingerprint template and the template to be matched:a) Calculate the relative match ratio: ηr=S2/S1b) Calculate absolute match ratio=S2/Sc(Scis a constant value)c) Calculate the final match ratio ηr=ηr×ηα=S22/(S1×Sc)

Relative match ratio ηrindicates the extent of matching between two fingerprint templates. The higher the number is, the greater extent of matching is. However, it is not proper to determine whether the fingerprint templates match or not with the relative matching ratio ηras the only criteria. Though the size of overlapping may be small and the value of S1and S2are low, it is possible that ηris still high. In this case, it is not appropriate to judge the matching extent solely depending on ηr. It is thus necessary to set absolute match ratio ηαto withhold S2. The key point of so doing is to make it clear that the present method must base on adequate number of ridge points and Scis a constant value that is above 1. The final match ratio ft ηfis the final match points of the two fingerprints. Final results will be output after comparing ηtwith threshold value T.