Minutiae points detection and matching

I have been working on minutiae points detection using template matching. The goal was to find a filter that, when applied on the enhanced print, pops out the bifurcation and ridge endings.

After trying some real minutia point template in various direction, I decided to create a template using maths functions. The main motivation is because it allows to orient the template in any direction without problems in filling the holes of the rotation. It is also convenient because it can be tuned easily. I did not remember having seen this kind of approach in the literature or the net, but it is attractive and quite powerful. I used interpolated cosine wave functions with different frequencies.

Due to the duality of ridge ending and bifurcation, the enhanced image has to be filtered using two filters. This can be done by inverting the image, or the filter, or rotating the filter of 180°. I chose the first solution even if it is not the faster one. Then the local maxima of the two filtered images need to be extracted and merged together (a threshold can be adjusted here). The next picture shows all those steps.



After having the minutiae point position and direction, I tryed Ransac on different prints even if I do not specify correspondences. The next picture shows that the two fingerprints are considered to match.



I also made functions to save and load minutiae points from a text file, which allows me to begin some tests. The first impression is that is is very slow, because I compute for each pixel the corresponding oriented Gabor filter and minutia template. It takes 15 seconds to enroll a print. It also take 10 seconds to do 5000 iterations of Ransac. An other thing that can be improved is to use pointers and increment them instead of using the convenient function cvGetReal2D(img, i, j). The second impression is that I do not have false accepts, but some true rejects. That is because I mainly tune the program on good quality prints. Also Ransac need correspondences to work accurately and decrease those rates.

Next steps:
- Find correspondences: I tryed to run David Lowe's SIFT algorithm, but it gives features of 1 pixel size. Moreover, It founds more than 2000 features. I may also try Normalized Cross Correlation.
- Do the draft report.
- Test and tune the program.

Gabor filters are cool

A picture worth more than a thousand words, so I am going to explain briefly what I did, and then show the results.

- I tryed SVD on the covariance matrix of the gradient versus averaging the gradient, and SVD gives better results. It provides an estimation of the reliability of the orientation (using the ratio of the two eigenvalues). The ridge orientation is given by the orientation of the vector having the smallest eigenvalue (which is positive because the covariance matrix is symetric).

- I change the color legend used to plot the orientation. HSV color space is used: Hue for the orientation (0°=red, 120°=green and so on), Saturation is maximum (full color), and Value is the max eigenvalue normalised in the overall image (I notice writting this post that it needs to be the ratio of the eigenvalues instead). Orientation directions are the same length on the picture.

- In order to get the orientation for each pixel in the image, orientation is bilinearly interplolated using the orientation computed on the small windows.

- Finally, I applied Gabor filters to enhance the fingerprint. For each pixel, given the orientation, I compute the Gabor filter having that direction (it is really expensive, but I was lazy to precompute a bank of filters). This gives a pretty neat nearly black and white image, where ridges are clearly visible. As the authors of "the handbook of fingerprint recognition" advised, I fixed the standard deviation of the gaussian in x and y to 4. I used a sine wave instead of a cosine (against what is used in the book), so that the average value of the filter is 0. The frequency of the sine wave can be set, but I did not estimate the local ridge frequency. I will do that later on.

Here is the picture summing up the results:

Ridge Orientation

First of all, since minutiae points detection has to be trainned using fingerprints, I separate evenly my database into the trainning set and the testing set (about 600 prints each). I then separate the trainning set into 2 subsets, which will allow me to do trainning-testing cycles without using the original testing set. The fingerprints were downloaded from the FVC (Fingerprint Verification Competition). Of course, I will not use the testing set until the end of the project.

Then, the first set in minutia detection is to estimate rigde field orientation. This allows to find the local orientation of the ridges. In the handbook of fingerprint recognition, several methods are presented. I programed the first one, which is directly inspired from CSE166.

Using Sobel filter, I compute the gradient in x and y of the image (Ix and Iy). Then, for each pixel in the image, I can compute the orientation and the norm of the gradient and plot it. The orientation is a number between 0° and 180° representing the angle from the x axis. Since it is influenced by noise and difficult to plot, we need to compute an average inside a small window (let's say 8x8). A trick is used to average the angles: because we don't want that the average of 10° and 170° be 90°, the angles are doubled. Averaging 20° and 340° gives 180°, which is the right direction angle (same direction as 0°).

One thing to notice is that the orientation given by the formula atan(Iy/Ix), is not the direction of the ridge. We need to add Pi/2 to it.

I had some problems to plot the direction of the minutiae points. I was first testing it on a circle image:



After I got it working right, I then tryed it on a fingerprint using a 4x4 window. Here are the original print, the direction field thresholded, and height map (the norm field).





Some issues to test:
- what is the right size of the small window?
- Using an other method, based on SVD on the covariance matrix of the gradient.

Ransac in action

Here is a video showing how ransac works. After some iterations, the right transformation is found (does not show up well at the end of the video).


Sometimes, after the transformation, all the points are aligned, or shrinked onto one point. Thus the number of matches may be high. To avoid that problem, I verify that the transformation spread the points by computing the determinant of A (the rotation, scaling, shearing matrix). If is under 0.1, It means that the transformation is not valid, and it doesn't worth counting the number of matches.

I choose to compute only the determinant and not the ratio between the norm of eigen values because it is quite expensive. This may be added later if needed. From now, all my test sets involve rigid transformation (rotation+translation), so the determinant is equal (or close) to 1. I think there will be some scaling effect between the natural fingerprints I have, but It may not be too important (the ratio may stay between 0.5 and 2).

Then, I generated an other print in two position. For each position, I made 5 groups of minutiae points (colored in red, blue, cyan, green and yellow), that are the corresponding points.


The colors allow to load an image and run ransac on it. It does a good job by finding the transformation (not shown here).
I then delete about 2-3 points in every set and every group of colors: in each picture, 13 points are thrown away. Initially, there were 49 points in each set, now there are only 49-2x13=23 corresponding points and 26 outliers (13 in each set). Ransac do not care about outliers and still finds the transformation as this picture shows.



I will explain later the statistics involved in ransac algorithm, why it is important to find a small subset of correspondences, how estimate the error we can make (false acceptance and false rejection).

I still need to refine the transformation using matching points (see if it increases the number of points), and then I am going to begin the detection of minutiae points and creation of a feature vector. I will need to have a closer look to the fingerprint database, and separate evenly in two subsets: one for the testing, one for the training.

Matching algorithm coding

This week end, I coded a simple version of the matching algorithm. I am using OpenCV library, and defined some C++ classes: minutiaPoint, minutiaePoints. I coded the function that find the optimal affine transformation between N correspondences (that is mainly used for N=3, that gives an exact solution).

I coded the ransac algorithm using the transformation function. It needs 2 sets of minutiae points, each minutia in the first set has some correspondences in the other set. Then 3 points are chosen randomly in the first set, and their correspondences are chosen randomly in the set of possible correspondences.

To see the results, I used the minutiae points posted last time. The red crosses correspond to the first set of points, the green ones are for the second set. The first image is the unmatched version (surimposed points).




Then find and apply the transformation using 3 close points (in green in the bottom of the image). This gives a first alignment, which is not so good (especially with far points).




Then I used 3 far points to estimate the transformation (one at the top, one on the left, one at the bottom). The alignment is better.




The best alignment found is by using all the 27 minutiae points and estimating the transformation. This shows that in ransac, it is good to reestimate the transformation using all the inliers found (the points that are found to match). It is not good to estimate the transformation using all the points as there are a lot of outliers that will influence the results. That's the job of the ransac algorithm: get rid of the outliers.

The ideal case

Here is an example of what the ideal case in fingerprint identification can be. I generate the two fingerprints using the program Sfinge from the university of Bologna, Italy. It allows to generate a synthetic fingerprint by changing a lot of different parameters (orientation, dryness, orientation, scratches...).

Here I generate the ideal fingerprint (best contrast, no noise, no scratches). This case never happens in reality but shows what my program should do without problems. First of all minutiae points are found (in red on the picture): I did it manually, I will deal with that automatically later. I show only the points and not the orientation since only the points are used for matching. The two fingerprints come from the same finger, and I vary only the rotation and translation between them. We should be able to find a 2x2 matrix A and a vector 2x1 B such as for each corresponding point on the left Li, and on the right Ri we have the formula:
Li=A.Ri + B

This a linear transformation (translation, rotation, scaling and shear). As there are 6 degrees of freedom, we only need 3 corresponding points (3 on the left, 3 on the right). I will use the same method as in homework7 of CSE166: here the solution will be an exact inverse (not a pseudo inverse with an over determined equation). Two problems need to be solved: how can we find the correspondence between the points, and how can we find the best fitting transformation?

To find the correspondences, I need to compute some vector containing features that is not influenced by rotation, translation, noise. Then the corresponding points will have approximatelly the same feature vector. This is a way to reduce the combinatorial size of the problem. Thus a point will have a reduced set of correspondences. I will deal with this issue later using SIFT or other feature detection algorithm.

To find the transformation, I will use Ransac on the corresponding points previously found. The algorithm will be:

Parameters:
n=3: number of random points (we use the minimum number of points)
k: number of iterations required
d: number of matching points required to assert that the transformation fits well
R0, θ0: threshold used to identify that a point fits well

The algorithm is based on this process:
- We take n random points both in the template and input sets among the correspondences.
- We find the transformation from the template random points that gives the imput random (L=A.R + B)
- We count the number of points which match (using md function) after applying the transformation to the all the template points. That will give a score (using the distance between the points) of the matching.
- If we count d matching points, then we approximate A and B using the matching points, and using the least square solution (pseudo inverse).
This process is repeated k times.
At the end, the solution is given by the A and B having the greatest score. We may end having no solution, in that case, we need to increase k, and/or improve the correspondence matching algorithm.

Matching figure

This figure shows the different situations we can find when trying to match minutiae points. This figure is used to explain the presentation of the matching problem (see next post).