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?