Wednesday, March 7, 2007

Feature correspondence

As NCC and SIFT are not suited to find correspondences in fingerprints (a minutia point looks like an other minutia point), I tried to design my own algorithm. Serge advised me to imitate what humans do when tring to find correspondences between two sets of points: here is the simple algorithm I wrote.

The overall idea is to compute for each point in the two sets, a feature vector, and then compare the features using a feature distance.

Let's consider a minutia point M. The main idea, shown on the next picture, is to consider the 3 closest points around M, we can call them M1 M2 and M3. The distance between M and M' will be found using the euclidean distance between M1,M2,M3 and M'1,M'2,M'3. This can not be done directly and a few adjustments need to be done.

First of all, the orientation of the points may not be the same due to the print rotation. We need first to rotate all the points of an angle equal to the ridge orientation of M.
The indexing of the points may not correspond: for example M1<->M'3, M2<->M'1, M3<->M'2. So we need to compute the sum of the distances between the 3 correspondences, for all the permutations of the points: we then take the minimum of these. If the minimum is small, it means that the 3 points around M are in the same relative position as the 3 points around M'.

This is an algorithm based on 3 points assuming that there is no false minutia point. A 1 point distance, that can allow 2 false minutiae points is simply the minimum over all the distances between the points. If for example only M2<->M'3, then the distance will be small.

I used an indermediate 2 points distance, which gives quite good results. This is based on the same idea but for 2 points: it is the minimum of the sum of the distances between every two pairs of correspondences. For example: M1<->M'3, M2<->M'1 (M3 and M'2 may be far away from eachother). This method combines the advantages from the 1 and 3 points distance (robust to noise and accurate).

For the final step, I compared for each minutia point M the distance to the minutiae points in the other set and took the 5 smallest distances: those 5 points are said to be the the correspondences of M. This is then fed to Ransac, which greatly help to find quickly a solution (a solution is found, when there is one, in about 100 iterations).

This week end I also implemented the refinement method for Ransac. It helped sometimes to go over the limit of 10 matching points in both cases (false accept and true reject).

The next step is to tune a bit more the algorithm and run it on the testing set. I will be able to do 100x100 comparisons, but not 600x600.

As an hall of fame: I found 2 prints in my training set that are said to come from the same finger, but cannot see any similarity.

2 comments:

Anonymous said...

I happened across your Fingerprint Identification post and found your research interesting. One thing concerned me though. I may have misunderstood, but are you saying that the two prints you have displayed are NOT the same?
('As an hall of fame: I found 2 prints in my training set that are said to come from the same finger, but cannot see any similarity')
Or are you saying that your algorithm could not see any similarity?
In my opinion these two prints are definitely from the same person (based on many years of fingerprint identification work).
I'm happy to forward you an image showing the agreement if you wanted clarification.

Unknown said...

I agree and can verify that the Fingerprints have the same origin.