CN100492395C - Fingerprint feature fast matching method, device and application thereof - Google Patents

Abstract

A quick matching method of fingerprint utilizes global character information and local detailed character information of fingerprint to accurately and conveniently as well as quickly judge out whether two fingerprints are matched to each other or not. The device and intelligent card for realizing said method are also disclosed.

Description

Fingerprint feature fast matching method, device and application thereof

technical field

The present invention relates to a method for realizing fast matching of fingerprint features by using the global feature information of the fingerprint (that is, the central point of the fingerprint image) and the local detailed feature information (that is, the bifurcation point and the endpoint of the fingerprint ridge line), and also relates to a method for realizing the fingerprint feature. The device of the fingerprint feature fast matching method also relates to a smart card (smartcard) using the fingerprint feature fast matching device for fingerprint feature matching, which belongs to the field of pattern recognition and smart card technology.

Background technique

Smart card technology is recognized as an effective technical means for enterprises and governments to solve identity and security issues.

At present, smart card technology has developed to the stage of using biometrics for identification. In addition to the combination of public key structure and Java ^TM technology, the combination of smart card technology and biometric identification technology can realize the strongest identity verification method. Therefore, as a portable multifunctional identification and communication medium with the highest security, smart cards with biometric technology are recognized as the best solution for reliable personal authentication both online and offline. The biometric technology mentioned here refers to the technology of collecting and analyzing the unique characteristics of the human body, such as fingerprints, retinal and voice patterns, etc., for identity verification.

Among biometric identification technologies, fingerprint identification technology developed the earliest, and people began to use computers to process fingerprints in the 1960s. After continuous development, fingerprint recognition is now a relatively mature technology, and many related technical achievements have come out. For example, the invention patent application with publication number CN1735908 discloses a fingerprint matching device and method, a recording medium and a program capable of quickly performing fingerprint matching processing with a small amount of data. The CPU detects the center point C, bifurcation points P1 to P8, and end points Q1 to Q10 of the fingerprint image and generates a triangle by connecting the bifurcation point P1 closest to the center point C and two bifurcation points P2 and P3 near the bifurcation point W1. The area S1 of the triangle and the lengths of the three sides are stored in the flash memory. In addition, the CPU calculates the position of the branch point P1 and the end point Q1 near the branch point P1, the position of the branch point P2 and the end point Q3 near the branch point P2, and the position of the branch point P3 and the end point Q3 near the branch point P3. locations, and store these locations in flash memory as registered templates. When performing matching, the CPU judges whether the area and side length of the triangle and the position of the end point obtained from the matching image coincide with the registered template.

The invention patent application with the publication number CN1716276 also discloses a fingerprint identification algorithm and system, which is characterized in that: the input method of the fingerprint feature information and the registered fingerprint feature information input by the above input method, the input method input by the above input method The relevant information of fingerprint features and the memory method of fingerprint information; the similarity degree of two fingerprints is calculated from the relevant information of the input two kinds of fingerprint features; The approximate value of the difference in position is called the first position calculation method. After correcting the difference between the position of the registered fingerprint calculated by the above-mentioned first position calculation method and the position of the input fingerprint, it is calculated by using the above-mentioned similarity degree calculation method. The approximate value of the rotation difference between the registered fingerprint and the input fingerprint is called the first rotation calculation method, the difference between the positions of the registered fingerprint and the input fingerprint, and the approximate value of the rotation difference; The difference between the fingerprint and the input fingerprint position, and the approximate value of the rotation difference, and the calculation method of the above-mentioned similarity, compare the difference between the registered fingerprint position memorized by the above-mentioned fingerprint memory method and the input fingerprint position, and determine the approximate value at In a smaller range, a detailed comparison is called the second position calculation method. Use the above-mentioned second position calculation method to calculate the difference between the registered fingerprint position and the input fingerprint position and the above-mentioned similarity calculation method, and use the fingerprint memory method to match the difference between the registered rotation and the input fingerprint rotation to its approximate value, which is the same as the above-mentioned first rotation calculation. method to compare, determine it within a smaller range, and make a detailed comparison, which is called the second rotation position calculation method; using the second position calculation method, the second rotation position calculation method calculates the registered fingerprint position and input The difference between the position and rotation position of the fingerprint is corrected, and then the degree of similarity is calculated by using the calculation method of the degree of similarity mentioned above, and according to the result, it is judged whether the registered fingerprint and the fingerprint entered are the same person; the above judgment result is output.

From a technical point of view, fingerprint recognition is a typical pattern recognition problem, which is mainly composed of two parts: feature extraction and feature matching of fingerprints. At present, most of the fingerprint recognition and comparison algorithms use the detail comparison method, which are mainly divided into two categories: comparison algorithm with center point and comparison algorithm without center point. The non-center point comparison algorithm uses some redundant features of details to assist matching, and the center point is not required in the matching process. Its advantage is that it does not require high positioning of the collected fingerprint images, but the comparison efficiency is low, and it is not suitable for occasions with high time requirements, and it is not suitable for smart cards with limited computing resources and computing capabilities. The center point comparison algorithm uses the center point to assist in positioning and matching fingerprint images. Its advantage is that the comparison speed is very fast, but the disadvantage is that the accuracy of center point positioning is relatively high. If the center point positioning accuracy is not accurate enough Otherwise, the comparison often fails.

To use the fingerprint feature recognition technology in the smart card, the characteristics of the smart card itself must be fully considered. Compared with the computer, the storage space in the smart card is limited, so the feature data of fingerprints cannot be too much; in addition, the computing power of the processor in the smart card is often limited, so the fingerprint feature matching algorithm must be simple and efficient, and can quickly determine whether the fingerprints match . However, existing fingerprint matching algorithms often ignore the limitations brought by the above-mentioned characteristics of smart cards, so algorithms that work well in computers may not necessarily achieve satisfactory results in smart cards. At present, as far as the applicant knows, there are not many fingerprint matching algorithms specially optimized for the characteristics of smart cards.

Contents of the invention

The first object of the present invention is to provide a fast fingerprint feature matching method specially optimized for the characteristics of limited computing and storage capabilities of the smart card. This method utilizes the global features and detail features of fingerprints, and can quickly and accurately match fingerprint features.

The second object of the present invention is to provide a device for realizing the method for quickly matching fingerprint features.

The third object of the present invention is to provide a smart card that uses the above-mentioned fingerprint feature rapid matching device to perform fingerprint feature matching.

For realizing above-mentioned purpose of the invention, the present invention adopts following technical scheme:

A fingerprint feature fast matching method, which performs matching calculations in a polar coordinate system, is characterized in that it includes the following steps:

(1) detect the central point of the fingerprint image;

(2) If the center point is found, then carry out detail feature matching with the center point of the fingerprint image as the reference corresponding point; if the center point cannot be found, then proceed to step (9);

(3) Is the match successful?

(4) If the matching is successful, it is judged to be the same fingerprint. If it is not successful, the center point is used as the reference center, and the detailed feature points that can be used as matching reference corresponding points are searched for in the template and the input feature point set. record it;

(5) Matching the minutiae features of the fingerprint with the recorded minutiae feature points as the reference corresponding point;

(6) Is the match successful?

(7) If the matching is successful, it is judged to be the same fingerprint, and if unsuccessful, then proceed to step (9);

(9) use the unused template and the input feature point pair in the preceding steps as the reference corresponding point, and carry out minutiae point matching;

(10) Is the match successful?

(11) If the matching is successful, it is judged as the same fingerprint, and if it is not successful, it is judged as not the same fingerprint.

Wherein, in the step (1), the center point is determined by the following steps W:

W1) Divide the input fingerprint image into blocks of size W×W, where W is an integer;

W2) Calculate the gradients G _x and G _y of each pixel in each block;

W3) calculate the local main direction of each block;

W4) transform the direction field into a continuous vector field, and correct the ridge direction through a low-pass filter;

W5) calculate the direction field of the fingerprint image;

W6) Calculate the Poincare index of a certain point, if the Poincare index value of this point is 1/2, then this point is the center point.

When there are several candidate center points, the final center point position is obtained through the k-means clustering algorithm.

After the block where the center point is located is determined, the block is further divided into smaller blocks, and the method as described in step W is used to recalculate the position of the center point.

The detailed feature matching is divided into two steps. First, the local neighborhood structure information of a pair of reference points in the feature point set is used to perform rough matching of local structure information. After the rough matching is passed, the reference point is used as the corresponding point Do a global exact match.

The detailed feature matching method is divided into the following steps:

1) Using template minutiae and input minutiae as reference minutiae, transform the neighborhood minutiae or global minutiae in the input point set and template point set to the polar coordinate system;

2) Sorting the template detail points and input detail points in the polar coordinates according to the increasing direction of the polar angle, and connecting them into strings;

3) Match the string with the adaptive bounding box method, find out and record the matching score, and use the size of the matching score as the basis for whether to carry out global precision or matching success;

4) Find the maximum value of each matching score, and use it as the matching score between the input minutiae point set and the template minutiae point set, if the matching score is higher than a preset threshold, it is considered that the input image and the template image are from the same fingerprint, otherwise they are considered to be from different fingerprints.

The size of the self-adaptive bounding box is represented by radius_size and angle_size, and the radius_size and angle_size of the template detail points with a polar radius of r are calculated by the following formula:

$\mathrm{<span\; class="notranslate">\; radius</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; =</span>\left\{\begin{array}{ccc}\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; small</span>}& \mathrm{<span\; class="notranslate">\; if</span>}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; small</span>}\\ \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}& \mathrm{<span\; class="notranslate">\; if</span>}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; small</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; large</span>}\\ \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; large</span>}& \mathrm{<span\; class="notranslate">\; if</span>}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; \&Greater\; Equal;</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; large</span>}\end{array}\right.$

r_size=α ₁ +β ₁ r

$\mathrm{<span\; class="notranslate">\; the\; angle</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; =</span>\left\{\begin{array}{ccc}\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; small</span>}& \mathrm{<span\; class="notranslate">\; if</span>}& \mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; small</span>}\\ \mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}& \mathrm{<span\; class="notranslate">\; if</span>}& \mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; small</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; large</span>}\\ \mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; large</span>}& \mathrm{<span\; class="notranslate">\; if</span>}& \mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; \&Greater\; Equal;</span>\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; large</span>}\end{array}\right.$

a_size=α ₂ -β ₂ r

Among them, α ₁ , β ₁ , α ₂ , and β ₂ are preset empirical parameters, and they are all greater than zero. r is the polar radius of the template detail point, r_small, r_large, a_small, and a_large are the upper bounds of radius_size and angle_size and Lower bounds, which are pre-set values through experimentation.

The matching score Ms is obtained by the following formula:

$\mathrm{<span\; class="notranslate">\; Ms.</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 100</span>}<span\; class="notranslate">\; \&times;</span>\sqrt{\frac{\mathrm{<span\; class="notranslate">\; nb</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; pair</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; nb</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; pair</span>}}{{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}<span\; class="notranslate">\; *</span>{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&alpha;</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; nb</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; pair</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; \&beta;</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; match</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; error</span>}$

Where nb_pair is the number of minutiae point pairs on matching, match_error is the cumulative matching error of each matching point pair, M _c , N _c are the number of feature points in the common area of the template and the input fingerprint image, α, β are predetermined weighting factor.

Wherein, the value of α is 2, and the value of β is 3.

A fingerprint feature fast matching device is characterized in that it comprises:

A center point judging unit is used to find and judge the center point in the fingerprint;

The matching corresponding point selection unit is used to find possible templates and input feature point pairs that can be used as matching corresponding points in the template and the input feature points, and record them;

A matching judging unit, configured to perform matching calculation of feature points;

A polar coordinate conversion unit, used for converting the spatial position of the relevant feature point and the central point into polar coordinates;

First, the central point judging unit searches for and judges the central point in the fingerprint. If there is a central point, the central point is used as the corresponding point, and the matching judgment unit performs matching calculation to obtain a matching result; if the central point cannot be found, then The matching corresponding point selection unit and the matching judging unit use other unconsidered templates and input feature point pairs as reference corresponding points to match the minutiae points of the two fingerprints to obtain the matching result; , then the matching corresponding point selection unit uses the two center points as a reference to find possible templates and input feature point pairs that can be used as matching corresponding points in the template and input feature points, and use these feature point pairs as the matching algorithm. Referring to the corresponding points, the matching judging unit performs feature point matching on the template and the input feature points to obtain a matching result.

Before the matching judgment unit performs matching calculation, the polar coordinate conversion unit converts the spatial positions of the central point and the feature point into polar coordinates.

A kind of smart card, has microprocessor, memory, communication circuit, is characterized in that:

The smart card also has the above-mentioned fast matching device for fingerprint features.

A method for identity authentication using the above-mentioned smart card, the user inputs his fingerprint through the fingerprint collection device on the card reader, after the fingerprint sensor collects the fingerprint data, submits it to the feature extraction module, and transfers the fingerprint feature to the smart card; The smart card matches the input fingerprint feature with the preserved fingerprint feature, if the matching is successful, the identity authentication is completed, and it is characterized in that:

The smart card uses the above-mentioned fast fingerprint feature matching method to perform fingerprint feature matching.

The fingerprint feature fast matching method provided by the present invention has the following advantages:

(1) Since the feature comparison process is carried out under the guidance of the center point information, the rotation and translation transformation relationship between the two fingerprint images can be quickly determined, thus overcoming the inefficiency of the non-center point matching algorithm;

(2) When using the designated reference point to compare the detailed features of two fingerprints, the method of first performing local neighborhood rough matching and then global precise matching has greatly accelerated the speed of fingerprint comparison;

(3) Since the calculation of the matching score takes into account the influence of the matching error of the detail feature points on the matching result, a more accurate matching result can be obtained.

The smart card adopting the above-mentioned fast matching method of fingerprint features can further improve its security, reliability and ease of use, thus providing a feasible way for the integration of biometric identification technology and smart card application technology.

Description of drawings

The present invention will be further described below in conjunction with the accompanying drawings and specific embodiments.

Figure 1 is a schematic diagram of a discrete representation of a closed curve.

Figure 2 shows the table for finding the direction of the singular point.

Fig. 3 is a schematic diagram of local feature vectors.

Figure 4 shows an example of a variable-sized bounding box.

Fig. 5 is a basic flow chart of the fingerprint feature fast matching method provided by the present invention.

Fig. 6 is a logical structure diagram of a typical smart card.

Fig. 7 introduces a typical process of fingerprint feature matching for a smart card with a built-in fingerprint feature fast matching device.

Detailed ways

For ease of understanding, the following first focuses on the specific implementation and implementation device of the fingerprint feature fast matching method provided by the present invention, and then specifically introduces the application of this method in smart cards.

This fast fingerprint feature matching method mainly includes the following technical contents: fingerprint image center point detection, fingerprint image registration, rough matching of details based on local structural information, precise matching of details based on global structural information, and feature matching based on singular point information. Matches and match score calculations. Let's introduce them one by one.

1. Fingerprint image center point detection

The calculation of the center point is based on the direction field. In order to obtain the direction field of the fingerprint image accurately, the following steps are adopted:

1) Divide the input fingerprint image into blocks of size W×W. Wherein, W is an integer;

2) Calculate the gradients G _x and G _y of each pixel in each block;

3) Compute the local principal directions for each block:

$\mathrm{<span\; class="notranslate">\; \&theta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; the\; tan</span>}}^{<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\frac{\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\overset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\overset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; 2</span>}{\mathrm{<span\; class="notranslate">\; G</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; G</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span>}{\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\overset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\overset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; G</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; G</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

where G _x and G _y are the gradients in the x and y directions, respectively, W is the width of the block used to estimate the direction field, and θ(i, j) is the main direction of the block where the point (i, j) is located.

4) Due to the presence of noise, broken ridges and valleys, the estimated ridge direction θ(i, j) may not always be correct. In the neighborhood without singularity, the local ridge direction changes slowly, and a low-pass filter can be used to modify the incorrect ridge direction. In order to do this, the direction field needs to be transformed into a continuous vector field:

φ _x (i, j) = cos(2θ(, j)) (2)

φ _y (i, j) = sin (2θ (, j)) (3)

φ _x , φ _y are the x and y components of the vector field, and the low-pass filter can be expressed as follows:

${\mathrm{<span\; class="notranslate">\; \&phi;</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\overset{{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\overset{{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; u</span>}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; v</span>}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$

${\mathrm{<span\; class="notranslate">\; \&phi;</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\overset{{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; 2</span>}}{\overset{{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; u</span>}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; v</span>}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; )</span>$

where h is a two-dimensional low-pass filter whose integral is 1, and w _φ × w _φ is the size of the filter. This smoothing operation is performed on blocks. Its default size is 5×5.

5) Compute the local direction field at (i, j):

$\mathrm{<span\; class="notranslate">\; o</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; the\; tan</span>}}^{<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; )</span>$

In this way we get the direction field of the fingerprint image.

6) Calculation of singular points

Let O be the orientation field of the fingerprint image, the Poincare index at point (i, j) is calculated as follows:

$\mathrm{<span\; class="notranslate">\; Poincare</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; \&pi;</span>}}\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; \&psi;</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; \&Delta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 7</span>}<span\; class="notranslate">\; )</span>$

$\mathrm{<span\; class="notranslate">\; \&Delta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; if</span>}<span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; <</span>\frac{\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}\\ \mathrm{<span\; class="notranslate">\; \&pi;</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; if\; \&delta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&le;</span><span\; class="notranslate">\; -</span>\frac{\mathrm{<span\; class="notranslate">\; \&pi;</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}\\ \mathrm{<span\; class="notranslate">\; \&pi;</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>& \mathrm{<span\; class="notranslate">\; otherwise</span>}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; )</span>$

$\mathrm{<span\; class="notranslate">\; \&delta;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; o</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&psi;</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&prime;</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; \&psi;</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&prime;</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; o</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&psi;</span>}}_{\mathrm{<span\; class="notranslate">\; x</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; \&psi;</span>}}_{\mathrm{<span\; class="notranslate">\; the\; y</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 9</span>}<span\; class="notranslate">\; )</span>$

$\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&prime;</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; mod</span>}{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; \&psi;</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 10</span>}<span\; class="notranslate">\; )</span>$

where ψ _x (i) and ψ _y (i) are the x and y coordinates of the i-th point on the closed curve with N _ψ pixels centered on the given point, respectively. If the Poincare index value is 1/2, then the A given point (i, j) is determined as the center point.

In the present invention, the closed curve is taken in a 5×5 grid. As shown in Figure 1, the value of the Poincare index on the curve D ₁ D ₂ ... D ₁₂ D ₁ is as follows:

$\mathrm{<span\; class="notranslate">\; Poincare</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; 12</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; D.</span>}}_{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; mod</span>}\mathrm{<span\; class="notranslate">\; 12</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 11</span>}<span\; class="notranslate">\; )</span>$

In this way, several adjacent candidate center points are obtained, and the final center point position can be obtained by k-means clustering algorithm.

In some fingerprint images, due to the influence of noise and other factors, there may be false central points. In order to eliminate the false center point, the Poincare value of the inner curve d ₁ d ₂ ... d ₈ d ₁ at the same point is also calculated. Only when the Poincare value (1/2) in 3×3 and 5×5 is the same, this candidate center point is used as the true center point.

For each center point, determine its direction as follows: In the direction field of 5×5, calculate the sum of the difference between the directions on the eight directions (ie 0, 1...7 in Fig. 2), the minimum The direction is the direction of the center point, as shown in Fig. 2 . During the calculation process, the sum of the two directions may be the same, at this time, the average value of these two directions can be taken as the direction of the center point.

The center point of the fingerprint image provides available information for the matching of fingerprint minutiae feature points, but this is related to the accuracy of center point detection. The center point detection method given above can only obtain the center point position based on the block. If these center point positions are used as the corresponding points of the two fingerprints, the accuracy is obviously not enough. In order to obtain a more accurate center point point position, a precise positioning process of the center point position is also required, that is, the position of the center point is recalculated with a smaller block size in the local neighborhood of the above position. Since this calculation is done on a small image scale, it can be very fast.

2. Fingerprint image registration

For the template fingerprint to be matched and the input fingerprint, what we get is only the coordinate position, direction and type information of the minutiae and central point detected from the fingerprint image. Since the corresponding relationship between the two fingerprints is not known in advance, it is necessary to find a suitable transformation to match them first. This process is the registration of fingerprints. We use a pair of feature points (one from the template fingerprint and one from the input fingerprint) as reference points, and use the coordinate translation and direction rotation relationship between them to construct a similar transformation, transforming the input fingerprint feature points to the template fingerprint feature points in the coordinate space of . Since the nonlinear deformation of the fingerprint image is often radial, the deformation in a certain area is relatively large, and then expands nonlinearly, so the nonlinear deformation can be better described in polar coordinates. In addition, in the polar coordinate system, we do not need to consider the translation between the reference point of the input image and the template image, because the translation between the input image and the template image is fixed, that is to say, the translation between another pair of corresponding points It is the same as the translation between the reference points, so that when the coordinates of another pair of corresponding points are converted into polar coordinates relative to the reference point, the translation is canceled out, and, in the polar coordinate system, it is obviously better than in the rectangular coordinates It is easier to handle the rotation between two images in the system. Based on the above reasons, the present invention will perform detail matching in the polar coordinate system.

Even if the input fingerprint and the template fingerprint come from the same finger, there will still be deformations such as translation, rotation, and scale change between them. Before matching the two images, it is necessary to estimate the deformation parameters between them, and then calibrate the two images. Since the two fingerprint images are usually collected by the same instrument, it can be assumed that the coefficient of scale variation between them is 1. In addition, the translation between the two images can be disregarded in polar coordinates. Therefore, only the rotation parameters between the input image and the template image need to be estimated.

make

$\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; \&theta;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; \&theta;</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 12</span>}<span\; class="notranslate">\; )</span>$

Represents M minutiae points in the template fingerprint,

$\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; q</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; \&theta;</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; q</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; ,</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}^{\mathrm{<span\; class="notranslate">\; q</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}^{\mathrm{<span\; class="notranslate">\; q</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; \&theta;</span>}}_{\mathrm{<span\; class="notranslate">\; N</span>}}^{\mathrm{<span\; class="notranslate">\; q</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; T</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 13</span>}<span\; class="notranslate">\; )</span>$

Represents N minutiae points in the input fingerprint.

In order to convert the minutiae points to the polar coordinate system, we need to select a reference point in the template minutiae point set and the input minutiae point set as the origin of the corresponding polar coordinate system, and calculate the polar coordinates of other minutiae points relative to the reference point. coordinate. If there is a center point in both fingerprints, the center point is first used as a reference point pair; if one or both fingerprints do not have a center point, it is impossible to know the corresponding relationship between the template detail point set and the input detail point set. All possible pairs of reference points will be considered.

For each point P _i (1≤i≤M) in the template point set and each point Q _j (1≤j≤N) in the input point set, if they are minutiae points of the same type, calculate the Euclidean The distance and the rotation angle _{rotate[i][j] in the direction of Pi relative to the direction of Q j .} If the two meet certain threshold conditions (such as the distance does not exceed 80, the angle difference does not exceed 45), then they will be used as a pair of reference points for the next rough matching and precise matching process. Otherwise, other possible reference point pairs are then examined.

To calibrate the input image and the template image in the polar coordinate system, it is only necessary to convert all other input minutiae points and template minutiae points to the polar coordinate system with respect to the reference points P _i and Q _j respectively, and then at all input minutiae points Add an angle rotate[i][j] to the polar angle of . That is to say, the input minutiae points and the template minutiae points are transformed into the polar coordinate system with respect to the reference points P _i and Q _j respectively by the following formula

$\left(\begin{array}{c}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}\\ {\mathrm{<span\; class="notranslate">\; e</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}\\ {\mathrm{<span\; class="notranslate">\; \&theta;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}\end{array}\right)<span\; class="notranslate">\; =</span>\left(\begin{array}{c}\sqrt{{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}^{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}^{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}\\ {\mathrm{<span\; class="notranslate">\; the\; tan</span>}}^{<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}^{\mathrm{<span\; class="notranslate">\; r</span>}}}{{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}^{\mathrm{<span\; class="notranslate">\; r</span>}}}<span\; class="notranslate">\; )</span>\\ {\mathrm{<span\; class="notranslate">\; \&theta;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; \&theta;</span>}}^{\mathrm{<span\; class="notranslate">\; r</span>}}\end{array}\right)<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 14</span>}<span\; class="notranslate">\; )</span>$

Where (x _i , y _i , θ _t ) ^T is the coordinate of the minutiae point to be converted, (x ^r , y ^r , θ ^r ) ^T is the coordinate of the reference minutiae point, (r _i , e _i , θ _i ) ^T is The representation of minutiae points in polar coordinates (r _i represents the polar radius, e _i represents the polar angle, and _θi represents the angle between the direction of the minutiae point and the direction of the reference minutiae point). Then, we add an angle rotate[i][j] to e _i of each input detail point.

3. Rough matching of details based on local structure information

For a given pair of reference points, first use their local neighborhood structure information in the feature point set to judge whether they can be used as true corresponding points for global accurate matching. Only the reference point pairs that have passed the rough matching of the local structure information can be used as the corresponding points for the real global precise matching, which greatly reduces the calculation amount of the detail point matching, and improves the accuracy of the matching algorithm and the efficiency of the operation.

For a certain feature point P _k ＝(x _k , y _k , φ _k ,) ^T , use the other m feature points closest to it (m generally takes a value of 6~9) and itself to establish a feature vector, and put this The feature vector is used as local structure information, and this local feature is invariant to rotation and translation. Fig. 3 illustrates the situation of m=2, and its eigenvector description is as follows:

Fl _k ＝((d _ki , θ _ki , φ _ki ) ^T , (d _kj , θ _kj , φ _kj ) ^T ) (15)

${\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; the\; ki</span>}}<span\; class="notranslate">\; =</span>\sqrt{{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}$

in

Among them, d _ki is the distance between two feature points, θ _ki is the angle between the line direction of feature point P _k , P _i and the direction of feature point P _k , φ _ki is the angle between the direction of two feature points . The above calculation process is essentially a polar coordinate transformation with the feature point _Pk as the origin.

For any two reference feature points, after calculating their respective local feature vectors, use the following point matching algorithm to determine the matching of neighborhood detail points. If the number of neighborhood matching detail points exceeds a certain threshold, use them as corresponding points for global precise matching, otherwise, continue to examine other reference point pairs.

4. Accurate matching of minutiae points based on global structural information

After a reference point pair P _b (b=b1, b2) has passed the rough matching of the neighborhood structure information, these two feature points are used as the corresponding reference points for further global matching, and the nearest neighbor points on the image are removed Coordinate transformation of other feature points P _k relative to the corresponding point P _b :

Fg _k represents the vector obtained after the polar coordinate transformation of the feature point P _k relative to the corresponding point P _b . All Fg _k and the calculated local eigenvectors of P _b together form the global eigenvector. Use the following minutiae point matching algorithm to match the global feature vector to obtain the global matching result.

5. Matching of detail points

In the process of rough matching of local structure information and precise matching of global information mentioned above, the problem of matching feature vectors of minutiae points in the polar coordinate system is involved. The minutiae point matching algorithm in the present invention is as follows:

1) Take the template minutiae P _i and the input minutiae _Qj as the reference minutiae, use the method described above to transform the neighborhood minutiae or global minutiae in the input point set and the template point set to the polar coordinate system;

2) Sort the template detail points and input detail points in the polar coordinates according to the increasing direction of the polar angle, and connect them into a string, expressed as follows:

Among them, M and N are the number of minutiae points in the template and input feature vector, respectively;

找出并记录匹配分数，将匹配分数的大小作为是否进行全局精确或匹配成功与否的依据；3) Use the adaptive bounding box method to be introduced later to match strings and

Find and record the matching score, and use the size of the matching score as the basis for global precision or matching success;

4) Find the maximum value of each matching score, and use it as the matching score between the input minutiae point set and the template minutiae point set. If the matching score is higher than a pre-set threshold, the input image and the template image are considered to be from the same fingerprint, otherwise they are considered to be from different fingerprints.

The adaptive bounding box and its size are shown in Fig. 4, a bounding box is a box placed on the template minutiae. The size of the bounding box is represented by radius_size and angle_size, and their values will change with the size of the polar radius of the minutiae. Use the following formula to calculate the radius_size and angle of the template minutiae with the polar radius r.

$\mathrm{<span\; class="notranslate">\; radius</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; =</span>\left\{\begin{array}{ccc}\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; small</span>}& \mathrm{<span\; class="notranslate">\; if</span>}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; small</span>}\\ \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}& \mathrm{<span\; class="notranslate">\; if</span>}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; small</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; large</span>}\\ \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; large</span>}& \mathrm{<span\; class="notranslate">\; if</span>}& \mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; \&Greater\; Equal;</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; large</span>}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 20</span>}<span\; class="notranslate">\; )</span>$

r_size=α ₁ +β ₁ r (21)

$\mathrm{<span\; class="notranslate">\; the\; angle</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; =</span>\left\{\begin{array}{ccc}\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; small</span>}& \mathrm{<span\; class="notranslate">\; if</span>}& \mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; small</span>}\\ \mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}& \mathrm{<span\; class="notranslate">\; if</span>}& \mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; small</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; large</span>}\\ \mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; large</span>}& \mathrm{<span\; class="notranslate">\; if</span>}& \mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; \&Greater\; Equal;</span>\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; large</span>}\end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; twenty\; two</span>}<span\; class="notranslate">\; )</span>$

a_size=α ₂ -β ₂ r (23)

Among them, α ₁ , β ₁ , α ₂ , and β ₂ are preset empirical parameters, and all of them are greater than zero. r is the polar radius of the template detail point, r_small, r_large, a_small, a_large are the upper and lower bounds of radius_size and angle_size respectively, and their values are also pre-set through experiments.

The purpose of using adaptively sized bounding boxes instead of fixed-sized bounding boxes is to make the algorithm more robust to non-linear deformations. Nonlinear deformation is generally larger in a specific region, and then expands nonlinearly outward. When the polar diameter of the minutiae is small, a small deformation can cause a large change in the polar angle, while the change in the polar radius is small. So in this case the angle_size of the bounding box should be larger and the radius_size should be smaller. On the other hand, when the polar radius of the minutiae is large, a small change in the polar angle will cause a large change in the position of the minutiae, and the deformation of the polar radius can be regarded as the difference between the minutiae and the reference minutiae. The accumulation of the deformation of the region. So in this case the angle_size of the bounding box should be smaller and the radius_size should be larger.

和

的算法描述如下：match

and

The algorithm is described as follows:

1) Use (20)~(23) to determine the size of the bounding box of each template detail point. Set nb_pair[i][j]=0. (nb_pair[i][j] represents the number of minutiae pairs matched when using the template minutiae Pi and the input minutiae Qj as reference minutiae points for feature matching)

2) Do the following loop:

While 1≤m≤M do

While 1≤n≤N do

If template detail point m and input detail point n satisfy condition1, then

nb_pair[i][j]=nb_pair[i][j]+1;

End if

Increase n;

End while

Increase m;

End while

In the above process, condition1 is defined as:

in:

$\mathrm{<span\; class="notranslate">\; \&Delta;r</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}^{\mathrm{<span\; class="notranslate">\; q</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 25</span>}<span\; class="notranslate">\; )</span>$

$\mathrm{<span\; class="notranslate">\; \&Delta;\&theta;</span>}<span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; a</span>}& \mathrm{<span\; class="notranslate">\; if</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; \&theta;</span>}}_{\mathrm{<span\; class="notranslate">\; m</span>}}^{\mathrm{<span\; class="notranslate">\; p</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; \&theta;</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}}^{\mathrm{<span\; class="notranslate">\; q</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 360</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; mod</span>}\mathrm{<span\; class="notranslate">\; 360</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 180</span>}\\ \mathrm{<span\; class="notranslate">\; a</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 180</span>}& \end{array}\right.<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 26</span>}<span\; class="notranslate">\; )</span>$

r_low[m], r_high[m], θ_low[m], θ_high[m] are the lower limit and upper limit of the limit and polar radius and polar angle error of the template detail point m respectively. condition1 is the condition for treating template minutiae m and input minutiae n as matching point pairs. It means that the input minutiae n should be inside the bounding box of the template minutiae m, and the direction difference between these two minutiae should be less than ε (eg ε=30).

6. Calculation of matching score

After completing the above matching process with reference to two minutiae points (one from the template fingerprint and one from the input fingerprint), assuming that the number of minutiae point pairs on the match is nb_pair, the cumulative matching error of each matching point pair is match_error. The matching score is then calculated as follows:

$\mathrm{<span\; class="notranslate">\; Mrs.</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 100</span>}<span\; class="notranslate">\; \&times;</span>\sqrt{\frac{\mathrm{<span\; class="notranslate">\; nb</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; pair</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; nb</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; pair</span>}}{{\mathrm{<span\; class="notranslate">\; m</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}<span\; class="notranslate">\; *</span>{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&alpha;</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; nb</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; pair</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; \&beta;</span>}<span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; match</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; error</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 28</span>}<span\; class="notranslate">\; )</span>$

的加权平均，α，β为预定的加权系数(其典型值分别为2.0和3.0)。将以上匹配分数与预先设定的匹配阈值进行比较，即可作出匹配与否的判断。Among them, M _c and N _c are the number of feature points in the common area of the template and the input fingerprint image respectively, and match_error is the matching error of each matching detail point pair (including the

The weighted average of , α, β are predetermined weighting coefficients (the typical values are 2.0 and 3.0, respectively). Comparing the above matching scores with the preset matching threshold, a judgment of matching or not can be made.

7. Feature matching based on center point information

After the center point detection of the fingerprint image, the fingerprint feature information includes two parts: one part is the local detail feature point information, which is the bifurcation point and endpoint of the fingerprint ridge line; the other part is the global feature information of the fingerprint, which is the fingerprint center point . Therefore, with the center point information of the fingerprint, the operating efficiency of the matching algorithm can be improved. To sum up, the feature point matching algorithm among the present invention is as shown in Figure 5, carried out with the following steps:

1) If there are center points in both the template fingerprint and the input fingerprint, the center point of the two fingerprints is used as the corresponding point for feature point matching, and the feature point matching algorithm is as described in Section 5 above; otherwise, go to the fourth step;

2) If the center point is used as the corresponding point for feature point matching and the matching result is returned, then the feature matching algorithm ends; otherwise, with the above two center points as a reference, it is possible to find a possible match between the template and the input feature point as a matching Point templates and input feature point pairs (enlarge the size of the template detail point limit and re-match the global detail feature points), and record them in the set Point Pair;

3) Use each feature point pair obtained in the second step as the reference corresponding point of the matching algorithm to perform feature point matching on the template and the input minutiae points, and end the feature matching algorithm when encountering a matching consistent result;

4) Use other unused templates and input minutiae pairs as reference corresponding points to perform minutiae matching on the two fingerprints, and end the feature matching algorithm when a consistent matching result is encountered.

Considering the response time of fingerprint comparison in the card, the method provided by the present invention will return no matter whether the matching is successful or not after considering enough reference corresponding point pairs and matching the minutiae points.

The above-mentioned fast fingerprint feature matching method is mainly specially optimized and designed for the specific environment with limited storage and computing capabilities in the smart card. Due to the full use of the guiding role of the center point in the matching process, the two fingerprint images are quickly registered, which greatly improves the time efficiency of the algorithm; at the same time, the minutiae point matching method using adaptive limit integration effectively overcomes the fingerprint image non-identity. The impact of linear deformation on the accuracy of the matching algorithm; for a given pair of reference points, the rough matching of the local neighborhood structure information is performed first, and then the precise matching of the global detail information is performed, thereby greatly reducing the calculation amount of the detail point matching process, At the same time, the precision of the matching algorithm and the efficiency of operation are improved.

The software used to implement the method can be made into a fast fingerprint feature matching device in the form of firmware, which is integrated in the smart card. The fingerprint feature fast matching device includes a central point judging unit, which is used to find and judge the central point in the fingerprint; a matching corresponding point selection unit, which is used to find possible templates and input that can be used as matching corresponding points among templates and input feature points feature point pairs, and record them; the matching judging unit is used to perform the matching calculation of the feature points, and the polar coordinate conversion unit is used to convert the spatial positions of the relevant feature points and the central point into polar coordinates. When performing fast matching operation of fingerprint features, firstly, the central point judging unit finds and judges the central point in the fingerprint, if there is a central point, then takes the central point as the corresponding point, and the matching judgment unit performs matching calculation to obtain the matching result ; If the central point is not found, then the matching corresponding point selection unit and the matching judging unit use other unconsidered templates and input feature point pairs as reference corresponding points to perform minutiae matching on the two fingerprints to obtain a matching result. If the result of the matching calculation of the center point is a mismatch, the matching corresponding point selection unit uses the above two center points as a reference to find a possible pair of templates and input feature points that can be used as matching corresponding points in the template and input feature points , using these feature point pairs as the reference corresponding points of the matching algorithm, the matching judging unit performs feature point matching on the template and the input feature points, and obtains a matching result. Before the matching judgment unit performs the matching calculation, the polar coordinate conversion unit converts the spatial position of the center point and the feature point into polar coordinates. The matching operation is based on the polar coordinate data, which can reduce the amount of calculation and obtain the result faster .

The above-mentioned device for quickly matching fingerprint features is mainly used in smart cards. Figure 6 introduces the internal logic structure of a typical contactless smart card. The microprocessor chip used is MPU, which has logic control, management functions, encryption and decryption functions, etc., and the memory includes ROM, RAM, EEPROM, etc. RFC is a radio frequency transceiver circuit, which mainly solves card reading and writing communication and power supply, CAU is an encryption operation coprocessor, and SL is a security logic. Of course, it is also completely possible for the above-mentioned device to be used in a contact smart card.

The memory space size of different types of smart cards varies from 512Byte to 16KB, and there are different partition options. For the smart card implementing the method of the present invention, due to the need to store fingerprint feature data, the capacity of the smart card should generally be selected to be above 1KB. In the present invention, if the coordinate model of feature points is used and only two types of feature points, ridge tip and bifurcation point, are considered, the encrypted feature data of a fingerprint does not exceed 256 Byte and can be stored in the storage area of the smart card.

For the smart card that uses the method of the present invention for fast matching of fingerprint features, the above-mentioned fast fingerprint feature matching device can be built into the microprocessor of the smart card, or can be set independently. Fig. 7 introduces a typical process of fingerprint feature matching for a smart card with a built-in fingerprint feature fast matching device. The user uses a card reader with fingerprint recognition to input his fingerprint through the fingerprint collection device on the card reader. After the fingerprint sensor collects the fingerprint data, it submits it to the feature extraction module to extract the fingerprint feature of this time and transfer the fingerprint feature to the Smart card: The smart card matches the input fingerprint feature with the saved fingerprint feature, if successful, allows the user to perform subsequent operations, if the match is unsuccessful, prompts the user to re-input the fingerprint data. Generally, the smart card can be automatically locked after repeated unsuccessful attempts.

There is still a security weakness in the above scheme, if the attacker obtains the user's fingerprint information through other channels, as long as he obtains the user's smart card, he can send the fingerprint information obtained in advance to the smart card to complete the fingerprint matching and authentication process . There are two ways to solve this security weakness. One way is to integrate the fingerprint sensor, card reader and smart card into one device, so that the smart card only accepts fingerprint data from this device, which is costly. Another method is to integrate the card reader and the fingerprint sensor. The smart card and the card reader perform mutual authentication before exchanging data, and the data is encrypted for transmission. The disadvantage of this is that the technical solution is complicated.

The above is only a preferred embodiment of the present invention, but the scope of protection of the present invention is not limited thereto. Any person skilled in the art within the technical scope disclosed in the present invention can easily think of changes or Replacement should be covered within the protection scope of the present invention. Therefore, the protection scope of the present invention should be determined by the protection scope of the claims.

Claims (12)

1. a fingerprint characteristic quickly matching method mates calculating under polar coordinate system, it is characterized in that comprising following steps:

(1) central point of detection fingerprint image;

(2) if find central point, then the central point with fingerprint image is to carry out the minutia coupling with reference to corresponding point; If can not find central point, then change step (9) over to;

(3) whether coupling successful?

(4) if the match is successful then to be judged as be same fingerprint, if unsuccessful then be reference center with described central point, it is right that searching can be used as the details of match reference corresponding point in template and input feature vector point set, and they are noted;

(5) with the details noted to as with reference to corresponding point, the minutia of fingerprint is mated;

(6) whether coupling successful?

(7) if the match is successful then to be judged as be same fingerprint, if unsuccessful then change step (9) over to;

(9) with untapped template and input feature vector point in the abovementioned steps to as with reference to corresponding point, carry out the minutiae point coupling;

(10) whether coupling successful?

(11) if the match is successful then to be judged as be same fingerprint, if unsuccessful then be judged as non-same fingerprint.

2. fingerprint characteristic quickly matching method as claimed in claim 1 is characterized in that:

In the described step (1), described central point is determined as follows:

1) will import fingerprint image be divided into the size be the piece of W * W, wherein, W is an integer;

2) calculate the gradient G of each pixel in each piece _xAnd G _y

3) calculate the local principal direction of each piece;

4) field of direction is transformed in the continuous vector field, by low-pass filter correction crestal line direction;

5) field of direction of calculated fingerprint image;

6) calculate certain any Poincare index, if the Poincare index value of this point is 1/2, then this is a central point.

3. fingerprint characteristic quickly matching method as claimed in claim 2 is characterized in that:

When candidate's central point is several, obtain final center position by k-means clustering algorithm.

4. fingerprint characteristic quickly matching method as claimed in claim 2 is characterized in that:

Behind the block of definite central point place, this block further is divided into littler block, and uses the position of recomputating central point as method as described in the claim 2.

5. fingerprint characteristic quickly matching method as claimed in claim 1 is characterized in that:

Described minutia coupling was divided into for two steps and carries out, at first be to utilize the local neighborhood structural information of a pair of reference point in the unique point set to carry out partial structurtes information slightly to mate, after thick coupling is passed through, carry out accurately coupling of the overall situation as corresponding point with this reference point.

6. fingerprint characteristic quickly matching method as claimed in claim 5 is characterized in that:

Described minutia matching process is divided into following steps:

1) with template minutiae point and input minutiae point as the reference minutiae point, concentrated neighborhood minutiae point or the overall minutiae point of input point set and template point transformed to polar coordinate system;

2) template minutiae point in the polar coordinates and input minutiae point are increased progressively the direction ordering by polar angle, and connect bunchiness;

3) mate described string with self-adaptation gauge cassette method, find out and write down the coupling mark, with the size of coupling mark as whether carrying out accurate or the match is successful the whether foundation of the overall situation;

4) find out maximal value in each time coupling mark, it is used as the coupling mark of input details point set and template details point set, if the coupling mark is higher than a pre-set threshold, then thinks input picture and template image from same fingerprint, otherwise think that they are from different fingerprints.

7. fingerprint characteristic quickly matching method as claimed in claim 6 is characterized in that:

The size of described self-adaptation gauge box is represented with radius_size and angle_size, uses as shown in the formula calculating radius_size and the angle_size that polar radius is the template minutiae point of r:

$\mathrm{radius}\_\mathrm{size}=\left\{\begin{array}{cc}r\_\mathrm{small}& \mathrm{if\; r}\_\mathrm{size}\&le;r\_\mathrm{small}\\ r\_\mathrm{size}& \mathrm{if\; r}\_\mathrm{small}\&le;r\_\mathrm{size}\&le;r\_\mathrm{large}\\ r\_\mathrm{large}& \mathrm{if\; r}\_\mathrm{size}\&GreaterEqual;r\_\mathrm{large}\end{array}\right.$

r_size＝α ₁+β ₁r

$\mathrm{angle}\_\mathrm{size}=\left\{\begin{array}{cc}a\_\mathrm{small}& \mathrm{if\; a}\_\mathrm{size}\&le;a\_\mathrm{small}\\ a\_\mathrm{size}& \mathrm{if\; a}\_\mathrm{small}\&le;a\_\mathrm{size}\&le;a\_\mathrm{large}\\ a\_\mathrm{large}& \mathrm{if\; a}\_\mathrm{size}\&GreaterEqual;a\_\mathrm{large}\end{array}\right.$

a_size＝α ₂-β ₂r

α wherein ₁, β ₁, α ₂, β ₂Be predefined empirical parameter, and all greater than zero, r is the polar radius of template minutiae point, r_small, r_large, a_small, a_large are respectively the upper bound and the lower bounds of radius_size and angle_size, and they are values of setting by test in advance.

8. fingerprint characteristic quickly matching method as claimed in claim 6 is characterized in that:

Described coupling mark Ms obtains by following formula:

$\mathrm{Ms}=100\&times;\sqrt{\frac{\mathrm{nb}\_\mathrm{pair}*\mathrm{nb}\_\mathrm{pair}}{M_c*N_c}}+\mathrm{\&alpha;}*\mathrm{nb}\_\mathrm{pair}-\mathrm{\&beta;}*\mathrm{match}\_\mathrm{error}$

Wherein nb_pair is the right number of minutiae point on the coupling, and mat ch_error is the right cumulative matches error of each match point, M _c, N _cBe respectively template and input fingerprint image unique point number in the public domain, α, β is predetermined weighting coefficient.

9. fingerprint characteristic quickly matching method as claimed in claim 8 is characterized in that:

The value of described α is 2, and the value of β is 3.

10. fingerprint characteristic rapid matching apparatus is characterized in that comprising:

The central point judging unit is used for seeking and judging the central point of fingerprint;

Coupling corresponding point selected cell, it is right to be used for seeking the possible template and the input feature vector point that mate corresponding point of can be used as at template and input feature vector point, and they are write down;

The matching judgment unit is used to carry out the coupling calculating of unique point;

The polar coordinates converting unit is used for the locus of features relevant point and central point is converted to polar coordinates;

,, be corresponding point then at first, mate calculating, draw matching result by the matching judgment unit with this central point if there is central point by the central point in searching of central point judging unit and the judgement fingerprint; If central point fails to find, then other templates do not considered and input feature vector point are mated as the reference corresponding point two pieces of fingerprints being carried out minutiae point by coupling corresponding point selected cell and matching judgment unit, draw matching result; If it is not match that central point mates result calculated, be reference with described two central points then by coupling corresponding point selected cell, it is right to seek the possible template and the input feature vector point that can be used as the coupling corresponding point in template and input feature vector point, with these unique points to reference corresponding point as matching algorithm, by the matching judgment unit template and input feature vector point are carried out Feature Points Matching, draw matching result; Described matching judgment unit mates before the calculating, by the polar coordinates converting unit locus about central point and unique point is converted to polar coordinates.

11. a smart card has microprocessor, storer, telecommunication circuit, it is characterized in that:

Also has fingerprint characteristic rapid matching apparatus as claimed in claim 10 in the described smart card.

12. method of using smart card as claimed in claim 11 to carry out authentication, the user imports its fingerprint by the fingerprint collecting equipment on the card reader, after fingerprint sensor collects finger print data, submit to characteristic extracting module, and fingerprint characteristic is delivered to described smart card; Described smart card mates the fingerprint characteristic of input and the fingerprint characteristic of preservation, if the match is successful, then finishes authentication, it is characterized in that:

Described smart card adopts fingerprint characteristic quickly matching method as claimed in claim 1 to carry out the fingerprint characteristic coupling.

Images