Minutiae-based fingerprint matching algorithm
<p><strong>The problem</strong></p>

<p><em>I need to match two fingerprints and give a score of resemblance.</em></p>

<p>I have posted a <a href="https://stackoverflow.com/questions/39120120/i-processed-fingerprints-how-do-i-compare-the-resuts">similar question</a> before, but I think I've made enough progress to warrant a new question.</p>

<p><strong>The input</strong></p>

<p>For each image, I have a list of minutiae (important points). I want to match the fingerprints by matching these two lists.</p>

<p>When represented graphically, they look like this:</p>

<p><a href="https://i.stack.imgur.com/5o9Bk.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/5o9Bk.png" alt="minutiae"></a></p>

<p>A minutia consists of a triplet <code>(i, j, theta)</code> where:</p>

<ul>
<li><code>i</code> is the row in a matrix</li>
<li><code>j</code> is the column in a matrix</li>
<li><code>theta</code> is a direction. I don't use that parameter yet in my matching algorithm.</li>
</ul>

<p><strong>What I have done so far</strong></p>

<ul>
<li><em>For each list, find the "dense regions" or "clusters"</em>. Some areas have more points than others, and I have written an algorithm to find them. I can explain further if you want.</li>
<li><em>Shifting the second list</em> in order to account for the difference in finger position between both images. I neglect differences in finger rotation. The shift is done by aligning the barycenters of the centers of the clusters. (It is more reliable than the barycenter of all minutiae)</li>
<li><p>I tried building a matrix for each list (post-shift) so that for every minutia increments the corresponding element and it's close neighbours, like below.</p>

<p><code>1 1 1 1 1 1 1</code></p>

<p><code>1 2 2 2 2 2 1</code></p>

<p><code>1 2 3 3 3 2 1</code></p>

<p><code>1 2 3 4 3 2 1</code></p>

<p><code>1 2 3 3 3 2 1</code></p>

<p><code>1 2 2 2 2 2 1</code></p>

<p><code>1 1 1 1 1 1 1</code></p></li>
<li><p>By subtracting the two matrices and adding up the absolute values of all elements in the resulting matrix, I hoped to get low numbers for close fingerprints.</p></li>
</ul>

<p><strong>Results</strong></p>

<ul>
<li>I tested a few fingerprints and found that the number of clusters is very stable. Matching fingerprints very often have the same number of clusters, and different fingers give different numbers. So that will definitely be a factor in the overall resemblance score.</li>
<li>The sum of the differences didn't work at all however. There was no correlation between resemblance and the sum.</li>
</ul>

<p><strong>Thoughts</strong></p>

<ul>
<li>I may need to use the directions of the points but I don't know how yet</li>
<li>I could use the standard deviation of the points, or of the clusters.</li>
<li>I could repeat the process for different types of minutiae. Right now my algorithm detects ridge endings and ridge bifurcations but maybe I should process these separately.</li>
</ul>

<p><strong>Question: How can I improve my algorithm ?</strong></p>

<p><strong>Edit</strong></p>

<p>I've come a long way since posting this question, so here's my update.</p>

<p>I dropped the bifurcations altogether, because my thinning algorithm messes those up too often. I did however end up using the angles quite a lot.</p>

<p>My initial cluster-counting idea does hold up pretty well on the small scale tests I ran (different combinations of my fingers and those of a handful of volunteers).</p>

<p>I give a score based on the following tests (10 tests, so 10% per success. It's a bit naïve but I'll find a better way to turn these 10 results into a score, as each test has its specificities):</p>

<ul>
<li>Cluster-thingy (all the following don't use clusters, but minutiae. This is the only cluster-related approach I took)</li>
<li>Mean <code>i</code> position</li>
<li>Mean angle</li>
<li><code>i</code> variance</li>
<li><code>j</code> variance</li>
<li>Angle variance</li>
<li><code>i</code> kurtosis</li>
<li><code>j</code> kurtosis</li>
<li>Angle kurtosis</li>
<li><code>j</code> skewness</li>
</ul>

<p>A statistical approch indeed.</p>

<p>Same finger comparisons give pretty much always between 80 and 100%. Odd finger comparisons between 0 and 60% (not often 60%). I don't have exact numbers here so I won't pretend this a statistically significant success but it seems like a good first shot.</p>