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.