Verification Algorithm
Our verification algorithm is built upon two different methods found in current fingerprint verification literature [9, 10]. The aim is to determine whether a test fingerprint image is taken from the same finger as a reference fingerprint image from the database. The hybrid algorithm is divided into two stages:
Local Neighborhood Matching
Our first stage is to create reference centers from our reference fingerprint image. We first draw a circle of radius 150 pixels around each minutiae (call this minutiae the central feature) and correlate the closest 4 neighboring minutiaes with this central feature (Figure 10). If a minutiae does not have 4 neighbors within this circle, it is rejected as a central feature.
Figure 10.
¡@
For each reference center and each of its neighbor, we obtained the following information:
(1) Neighbor minutiaes type (termination or bifurcation).
(2) Distance between the center and the neighbor
(3) Distance-relative angle. This is the angle between the line joining the center and the neighbor, and the ridge angle of the center (angle c in Figure 11.)
(4) Relative ridge angle. Difference between the ridge angle of the center and ridge angle of its neighbor.
Figure 11.
Therefore, there are 4 characteristics describing the center and each of its neighbor. Mital and Teoh only use the first 3 characteristics [9], but we found that adding the fourth characteristic proves to be very useful at decreasing the false acceptance rate. Let us call this 4 characteristics the feature vector. Therefore, each reference center has 4 feature vector. Note that the reference center neighborhoods calculation can be done at a leisurely pace since the images are from the reference database, and therefore this does not play a role in affecting our algorithmic speed.
The same process is repeated for the test image minutiaes. This time however, the test center is not limited to only 4 neighbors. This increases the successful verification rate in the event that the test center has one or two false minutiaes close to it.
¡@
At this stage, we have a list of reference centers and a corresponding lists of test centers. Now, for each reference center, we search through the list of test centers and try to find a list of suitable candidates. A test center is rated as a possible candidate of a reference center if at least 1 of its feature vector is close to any feature vector of a reference center (of course the test center must also be of the same type as the reference center, see Figure 12.) The best corresponding test neighbor is defined as the neighbor of the test center whose feature vector has the best match. Note that a single test center can be a candidate for more than one reference center, while each reference center has one or more test candidates (Figure 13)
Figure 12(a). Figure 12(b).
Figure 13.
¡@
Reasons for this stage:
(1) This stage significantly reduces the number of features we have to match. Suppose the two fingerprints each have 20 central minutiaes. This mean that, we will have 20x20 = 4000 comparisons to be done. Using this rough comparison (efficiently implemented in Matlab with clever use of matrices), we will only have around 20*2 = 40 comparisons to be made. The number 2 is experimentally determined: there are usually at most 2 candidates for each reference center candidate (if the two images are from the same finger) for the values of the constraints we set.
(2) The feature vector is rotationally and translational invariant.
(3) Local neighborhood tends to be more immune to distortion (for example due to different pressure on different points of the finger). Consider figure 14 and 15. We see that a ten percent distortion of a small square (Figure 14) can lead to huge distortion effects globally when there are a series of squares joined together (Figure 15), [10].
Figure 14.
Figure 15.
¡@
In order to better the algorithmic performance, this stage is followed by stage 2 in order to take local distortion into account.
¡@
¡@
Linear Roto-Translation Warping and Matching
Due to local distortion, a reference center and its corresponding test center might not match well even if they are supposed to. We model this distortion as a absolute orientation problem. Consider two set of points (a center and its neighbors) in two different coordinate systems. If the two set of points are supposed to be the same, what is the transformation that can be used to transform one set of points to another. The closed-form solution to this problem has already been found [11]. However, our problem is easier, because the points (minutiaes) are only two-dimensional. In fact we follow the equation used by Kovacs-Vajna [10] during the triangular matching stage in his paper for fingerprint verification
Note also, this model assumes the points are rigid under the transformation. This means the transformation consists of only scaling, rotational and translation (that is linear roto-translational warp). This might not be true globally for the image, but hopefully this would apply to small local neighborhoods, obtained in the first stage.
For a reference center and each test candidate (if any), we now have 2 pairs of points from the first stage which are found likely to match. The test center (X1, Y1) and the best corresponding test neighbor (X2, Y2) form one pair. The reference center (x1, y1) and the neighbor (x2, y2) corresponding to the best corresponding test neighbor forms the second pair. For each of the other neighbors (x3, y3) of the reference center, we now warp them accordingly to (X3, Y3) of the test image coordinate space, given that (X1, Y1) and (X2, Y2), are supposed to be matched to (x1, y1) and (x2, y2).
X3 = A*x3 + B*y3 + GX and Y3 = -B*x3 + A*y3 + GY,
where,
factor = (x2 ñ x1)^2 + (y2-y1)^2;
A = [(X2-X1)*(x2-x1) + (Y2-Y1)*(y2-y1)]/factor;
B = [(X2-X1)*(y2-y1) ñ (Y2-Y1)*(x2-x1)]/factor;
GX = X1 ñ A*x1 ñ B*y1;
GY = Y1 ñ A*y1 + B*x1;
We have therefore transformed the reference center and its neighborhood from the reference image space to the test image space. Now, we are confident of matching the reference center and test center more accurately. For each warped neighbor of the reference center, we try once again to match it with each of the neighbors of the test center, by comparing their differences in x and y coordinates. Comparing these two coordinates separately proves to be much better at discriminating false matches than simply using the difference in distance between each other or from the center.
¡@
Therefore each warped reference center has 3 neighbors to be matched to the test center (the fourth neighbor used in the warping algorithm obviously matches the best corresponding neighbor of the test center). For each match between the reference and test neighbors, we give the test fingerprint "1" point. Therefore, if a reference center matches a test center extremely well, the test image can score up to 3 points. If there is even 1 matched neighbor (besides the one used in warping), we consider the reference center and test center a match, and we move on to the next reference center, ignoring the other possible candidates of the reference center.
Awarding more points for better matches prove to be very important in improving correct verification in the case where there are many false minutiaes in two different images from the same finger, while not increasing the false acceptance rate. This is because an accidental false match (between two totally different fingerprints), which is not likely in the first place, is even least likely to get more than 1 match. Therefore these false matches are not likely to score more than 1 point.
Finally, we total up these points for each reference centers. If the total points exceed 5 (experimentally determined), we decide that the two fingerprint images are from the same finger.
¡@
¡@
