background

Niko's Project Corner

Fingerprint matching algorithm

Description Automated fingerprint matching
Languages Matlab
C++
SDL
Tags Com­puter Vi­sion
Data Struc­tures
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 struc­ture, us­ing ro­ta­tion, scale and trans­la­tion in­vari­ant met­rics. Fin­ger­print match­ing is based on find­ing sim­ilar groups of in­ter­est points, and check­ing that sev­eral in­de­pen­dent groups are re­lated to reach other by ap­prox­imately same affine trans­for­ma­tion.

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:

Agadmator
LaserMap
OmniCamera
MapStitcher
ReceiptUndistort