matrix - Minutiae-based fingerprint matching algorithm -

the problem

i need match 2 fingerprints , give score of resemblance.

i have posted similar question before, think i've made enough progress warrant new question.

the input

for each image, have list of minutiae (important points). want match fingerprints matching these 2 lists.

when represented graphically, this:

a minutia consists of triplet (i, j, theta) where:

• i row in matrix
• j column in matrix
• theta direction. don't use parameter yet in matching algorithm.

what have done far

• for each list, find "dense regions" or "clusters". areas have more points others, , have written algorithm find them. can explain further if want.
• shifting second list in order account difference in finger position between both images. neglect differences in finger rotation. shift done aligning barycenters of centers of clusters. (it more reliable barycenter of minutiae)

• i tried building matrix each list (post-shift) every minutia increments corresponding element , it's close neighbours, below.

  1 1 1 1 1 1 1

  1 2 2 2 2 2 1

  1 2 3 3 3 2 1

  1 2 3 4 3 2 1

  1 2 3 3 3 2 1

  1 2 2 2 2 2 1

  1 1 1 1 1 1 1

• by subtracting 2 matrices , adding absolute values of elements in resulting matrix, hoped low numbers close fingerprints.

results

• i tested few fingerprints , found number of clusters stable. matching fingerprints have same number of clusters, , different fingers give different numbers. factor in overall resemblance score.
• the sum of differences didn't work @ however. there no correlation between resemblance , sum.

thoughts

• i may need use directions of points don't know how yet
• i use standard deviation of points, or of clusters.
• i repeat process different types of minutiae. right algorithm detects ridge endings , ridge bifurcations maybe should process these separately.

question: how can improve algorithm ?

edit

i've come long way since posting question, here's update.

i dropped bifurcations altogether, because thinning algorithm messes often. did end using angles quite lot.

my initial cluster-counting idea hold pretty on small scale tests ran (different combinations of fingers , of handful of volunteers).

i give score based on following tests (10 tests, 10% per success. it's bit naïve i'll find better way turn these 10 results score, each test has specificities):

• cluster-thingy (all following don't use clusters, minutiae. cluster-related approach took)
• mean i position
• mean angle
• i variance
• j variance
• angle variance
• i kurtosis
• j kurtosis
• angle kurtosis
• j skewness

a statistical approch indeed.

same finger comparisons give pretty between 80 , 100%. odd finger comparisons between 0 , 60% (not 60%). don't have exact numbers here won't pretend statistically significant success seems first shot.

your clustering approach interesting, 1 thing i'm curious how you've tested it. new matching algorithm useful respect research , methods exists, need have reasonably low eer. have tested method of standard databases? have doubts ability of cluster counts , locations alone identify individuals @ larger scales.

1) fingerprint matching studied problem , there many papers can implement this. nice place start, check out paper, "fingerprint minutiae matching based on local , global structures" jiang & yau. it's classic paper, short read (only 4 pages), , can implemented reasonably. define scoring metric can used quantify degree 2 fingerprint images match. again, should starting point because these days there many algorithms perform better.

2) if want algorithm robust, should consider transformations of fingerprint between images. scanned fingerprints , latent prints may not consistent image image.

also, calculating direction of minutiae points provides method handling fingerprint rotations. measuring angles between minutiae point directions, remain same or close same across multiple images regardless of global rotation (though small inconsistencies may occur because skin not rigid , may stretch slightly), can find best set of corresponding minutia pairs or triplets , use them basis rotational alignment.

3) recommend distinguish between ridge line endings , bifurcations. more features can isolate, more accurately can determine whether or not fingerprints match. might consider number of ridge lines occur between each minutiae point.

this image below illustrates features used jiang , yau.

• d: euclidean distance between minutiae
• θ: angle measure between minutiae directions
• φ: global minutiae angle
• n: number of ridge lines between minutiae , j

if haven't read handbook of fingerprint recognition, recommend it.