Monday, March 19, 2007
Final report
My final report is available here (follow the link). I definitely enjoyed to work hard on this project. I also learned a lot from the others CSE190a projects. Thank you all!
Wednesday, March 14, 2007
Final review
Here is a link to the final presentation. It summarizes the overall approach of the project and the results I got.
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.
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.
Subscribe to:
Posts (Atom)