background

Niko's Project Corner

Fingerprint matching algorithm

Description Automated fingerprint matching
Languages Matlab
C++
SDL
Tags Com­puter Vi­sion
De­lay­nay Tri­an­gu­la­tion
K-d Tree
Data Struc­ture
Affine Trans­for­ma­tion
Duration Spring 2010 – Fall 2010
Modified 25th June 2013
thumbnail

For my Bach­elor of Sci­ence de­gree I de­vel­oped a novel fin­ger­print match­ing al­go­rithm, which ended up beat­ing many al­ter­na­tive meth­ods which were de­vel­oped by re­search groups around the world. The used dataset the same which was used for FVC 2000 (Fin­ger­print Ver­ifi­ca­tion Com­pe­ti­tion).

If the false pos­itive is set to a rel­atively low level (1% and less), my al­go­rithm pro­duced more true pos­itive matches than 3 of the 11 par­tic­ipated meth­ods, and I was quite happy with that re­sult. This granted me the high­est pos­si­ble grade. Nat­urally I've learned a lot more since, and could eas­ily im­prove the ac­cu­racy even fur­ther by us­ing lo­cal tex­ture fea­tures. My orig­inal method was purely based on de­tail's rel­ative lo­ca­tions.

The ba­sic steps can be seen in Fig­ure 1. Once the im­age is smoothed along lo­cal di­rec­tion of the ridges, the im­age is bi­na­rized us­ing lo­cally adap­tive 2nd or­der parametriza­tion. The re­sult­ing im­age is thinned, and two types of in­ter­est points can be found (ridge end­ings and split­tings). There can be some spu­ri­ous ridge end­ings, if the qual­ity of the print wasn't ideal.

Once spu­ri­ous in­ter­est points have been dis­carded, a De­lay­nay tri­an­gu­la­tion is pro­duced, and from this lo­cal groups of 4 in­ter­est points are in­dexed into a 3-di­men­sional K-d tree data structure, using rotation, scale and translation invariant metrics. Fingerprint matching is based on finding similar groups of interest points, and checking that several independent groups are related to reach other by approximately same affine transformation.

fingerprint_steps
Figure 1: (a) Orig­inal im­age. (b) Smoothed re­sult. (c) De­tected ridges. (d) Fixed bro­ken ridges (red) and gen­er­ated De­lau­nay-tri­an­gu­la­tion (blue).

Related blog posts:

OmniCamera
MapStitcher
ReceiptUndistort
CarTracking
InterestPointTracking