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).

Minutia point matching

This week end, I analyse the problem of matching two sets of minutiae points. First, I give in a formal form the problem we need to solve, and then explain an algorithm (Ransac) that can be employed to approximate the solution.
I used the book Computer Vision: a modern approach and the Handbook of Fingerprint Recognition.


Problem formulation:

Let T and I be the template and input fingerprint we are trying to match. We said that we store the position and orientation of the minutiae point. I and T may not have the same number of feature points: let m and n be the number of points for T and I.
T={m1,m2,...mm}, with mi={ xi, yi, θi} i=1..m
I={m'1,m'2,...m'n}, with m'j={ x'j, y'j, θ'j} j=1..n

Two minutiae points mi and m'j are considered to match, if their position and orientation are close. This can be written with a mathematical formula, using the spatial distance (sd) and direction difference (dd):
sd(mi, m'j)=sqrt( (xi – x'j)² + (yi – y'j)² ) < R0
dd(mi, m'j)=min( | θ'j – θi |, 360 - | θ'j – θi |) < θ0
where R0 and θ0 are the two tolerance parameters we can adjust. Those inequalities come from the classic euclidian distance in 2D and the circularity of angles.

Let mm be the function that says if two minutiae points are close or not i.e.
md(mi, m'j)=1 if (sd(mi, m'j) < R0 and dd(mi, m'j) < θ0 ), 0 otherwise.

Now, we try to match the points i.e. finding a transformation:
y=map(x), for all points x in the 3D space, it returns an other point y.
We need a pairing function P:
P(i)=j means that the mate of the mi in T is the minutia m'j in I.

Finally the matching problem can be written as finding map and P that maximise
sum( md( map( m'P(i) ), mi ) )



Ransac algorithm (RANdom Sample Consensus):

Parameters:
n: number of random 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 set.
- We find a transformation from the template random points that gives the imput random
- 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.
This process is repeated k times, and stop if we count d matching points.


Some questions:
In the ressources I used (books, cse252B website), we can use n=7 or 8 matching points. This comes from some properties of the epipolar geometry, with a linear transformation. Homogenous coordinates are used (a third coordinate is added), and the transform matrices are 3x3.
Here are some questions I need to answer:
- How can we find the linear transformation between two sets of points? Is the order of the points important (pairing)? Why 7 or 8 matching points?

First post

In order to have a first introduction to fingerprints, I watch a presentation made by Dr. Anil K. Jain. He is a University Distinguished Professor at Michigan State University, and did a lot of research on biometrics and especially fingerprints. The video and the slides are available here.

This video help me to have an overview of the work and research I need to do. Here are some points I found important. This slide shows the classic process for identification:
- in the first step (enrollment), the digit is scanned, and minutiae points are extracted. Then, only this information is stored in a database, not the whole scanned image.
- in the second step (authentication), the digit is scanned and minutiae points are extracted again. Then those points are matched (or not), with an other set of points stored in the database.

When we extract minutiae points, we try to find as much points of singularity as we can. They are of called either ridge bifurcation or ridge ending. Actually, we store the position information (x,y) and the angle of the ridge. We may extract core and delta points, which are characteristic points where the flow field of the ridges changes quickly. We also may store the type of the fingerprint to improve the speed of the algorithm.

Why do we use minutiae point matching and not image matching?
Most of the information in image is contained in the minutiae points. Every scan of a digit are different. It is really hard to match two images since there can be linear transformation between the two scans (rotation, translation, scaling and shear), plus other non linear transformation (elasticity of the skin, digit pressure), and noise coming from the sensor and the dryness of the finger.

I am currently learning how the RANSAC algorithm works, why it is used, and the mathematical background of it. I read the paragraph explaining the process in the book « Computer Vision: a modern approach », from David A. Forsyth and Jean Ponce (page 346). I need to go deeper in the details, so I am going to read the Handbook of Fingerprint Recognition from D. Maltoni, D. Maio, A. K. Jain, S. Prabhakar, and other web references.