Monday, January 29, 2007

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.

No comments: