Geekly Articles each Day
📜 ⬆️ ⬇️

Fingerprint recognition methods and implementation by means of Python

In the current semester, the subject “Methods and means of protecting computer information” has appeared in the schedule, part of which is laboratory work on biometrics, or rather, fingerprint recognition. Also, recently, on Habré there was an article about devices intended for scanning. I decided to write here about the recognition algorithms.


As a student, there is a fairly standard task in front of me: fingerprint verification (comparison with the standard). Since this laboratory, appeared only this year, the methodological manual on it yet. But in view of the interestingness of the problem, I went to Google.

Strangely enough, the second part of the article indicated in the topic about scanners turned out to be the most informative. It describes, quite clearly, several algorithms:
')
1. Correlation comparison
This approach consists in pixel-by-pixel comparison of two images, for various shifts and rotation angles, on the basis of the results obtained, they make decisions on coincidence. (in modern conditions it does not apply, due to the high labor intensity)

2. Comparisons of the pattern
Depending on the required accuracy, the image of the print is divided into areas. Further, the pattern in each of the areas is described by a sinusoidal wave, with parameters:

This class of algorithms does not require high resolution when scanning.

3. Comparison of individual points
Singular points are end points and branch points. These points are highlighted on both images, and then by the method of their correlation comparison, the verdict on the correspondence of prints is made.
In view of its relatively simple implementation and speed, these algorithms are more common.
I chose this type of algorithm for implementation in the laboratory. Therefore, we dwell on it in more detail.

Since the article gave only a general idea, I continued to google. The third line of issue was this presentation.
It describes in some detail the steps to implement the chosen approach.

So, a plan of action:

It was decided to do the implementation in Python. Accordingly, besides Python itself (I have version 2.7.1), I need a PIL (Python Imaging Library) to parse the image into pixels.

Step 1. Binarization
Then I did not invent, and did everything quite simply, in the forehead.
def binary ( img ) :
bImg = [ ]
for i in range ( img. size [ 0 ] ) :
tmp = [ ]
for j in range ( img. size [ 1 ] ) :
t = img. getpixel ( ( i, j ) )
p = t [ 0 ] * 0.3 + t [ 1 ] * 0.59 + t [ 2 ] * 0.11
if p > 128 :
p = 1
else :
p = 0
tmp. append ( p )
bImg. append ( tmp )
return bImg

If you need a different result, you should look at the themes of the “Image Processing” blog, there binarization is affected quite often.

Step 2. Skeletization
This step caused the greatest difficulty, since the algorithms google the hardest. As a result, 4 algorithms were found:

A template method was chosen, and the first set, since unlike the second set of templates, it requires only one traversal of the image. True, to reduce the level of inaccuracies, some of the templates from the second set are used.

Patterns correspond to a 3 * 3 matrix, where the center element is the current pixel in the image crawl.
image
here gray indicates pixels whose color does not matter

The eight first templates are the main part. Four at the bottom to eliminate the “noise”, at which these four can also be rotated 90, 180 and 270 degrees, and are sought by the second detour of the image.

If we stumble on a template, the central pixel is painted white (does not belong to the skeleton). The crawl continues while the deletion remains.

The code for this action is divided into several functions:
def tmpDelete ( img ) : # call skeletonization procedure, lists of lists as input (after binarization)
w = len ( img )
h = len ( img [ 0 ] )
count = 1
while count ! = 0 : # repeat at least one pixel was deleted
count = delete ( img, w, h )
if count:
delete2 ( img, w, h )


def delete ( img, w, h ) : # delete a pixel on the main set, return count of deleted
count = 0
for i in range ( 1 , h- 1 ) :
for j in range ( 1 , w- 1 ) :
if img [ j ] [ i ] == 0 :
if deletable ( img, j, i ) :
img [ j ] [ i ] = 1
count + = 1
return count

def delete2 ( img, w, h ) : # deleting a pixel by noise set
for i in range ( 1 , h- 1 ) :
for j in range ( 1 , w- 1 ) :
if img [ j ] [ i ] == 0 :
if deletable2 ( img, j, i ) :
img [ j ] [ i ] = 1


def fringe ( a ) : # definition of accessories 3 * 3 to noise
t = [ [ 1 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 1 ] ,

[ 1 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 0 ] ,
[ 1 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 1 ] ,
[ 0 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 1 ] ,
[ 1 , 1 , 0 , 1 , 0 , 0 , 1 , 1 , 1 ] ,

[ 1 , 1 , 1 , 1 , 0 , 1 , 0 , 0 , 1 ] ,
[ 0 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 1 ] ,
[ 1 , 0 , 0 , 1 , 0 , 1 , 1 , 1 , 1 ] ,
[ 1 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 0 ] ,

[ 1 , 1 , 1 , 1 , 0 , 1 , 0 , 0 , 0 ] ,
[ 0 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 1 ] ,
[ 0 , 0 , 0 , 1 , 0 , 1 , 1 , 1 , 1 ] ,
[ 1 , 1 , 0 , 1 , 0 , 0 , 1 , 1 , 0 ] ]
for i in t:
if a == i:
return true

def check ( a ) : # determination of the belonging of 3 * 3 to the main templates
t123457 = [ 1 , 1 , 0 , 0 , 1 , 0 ]
t013457 = [ 1 , 1 , 1 , 0 , 0 , 0 ]
t134567 = [ 0 , 1 , 0 , 0 , 1 , 1 ]
t134578 = [ 0 , 0 , 0 , 1 , 1 , 1 ]
t0123457 = [ 1 , 1 , 1 , 0 , 0 , 0 , 0 ]
t0134567 = [ 1 , 0 , 1 , 0 , 0 , 1 , 0 ]
t1345678 = [ 0 , 0 , 0 , 0 , 1 , 1 , 1 ]
t1234578 = [ 0 , 1 , 0 , 0 , 1 , 0 , 1 ]

t = [ a [ 1 ] , a [ 2 ] , a [ 3 ] , a [ 4 ] , a [ 5 ] , a [ 7 ] ]
if t == t123457:
return true
t = [ a [ 0 ] , a [ 1 ] , a [ 3 ] , a [ 4 ] , a [ 5 ] , a [ 7 ] ]
if t == t013457:
return true
t = [ a [ 1 ] , a [ 3 ] , a [ 4 ] , a [ 5 ] , a [ 6 ] , a [ 7 ] ]
if t == t134567:
return true
t = [ a [ 1 ] , a [ 3 ] , a [ 4 ] , a [ 5 ] , a [ 7 ] , a [ 8 ] ]
if t == t134578:
return true
t = [ a [ 0 ] , a [ 1 ] , a [ 2 ] , a [ 3 ] , a [ 4 ] , a [ 5 ] , a [ 7 ] ]
if t == t0123457:
return true
t = [ a [ 1 ] , a [ 3 ] , a [ 4 ] , a [ 5 ] , a [ 6 ] , a [ 7 ] , a [ 8 ] ]
if t == t1345678:
return true
t = [ a [ 0 ] , a [ 1 ] , a [ 3 ] , a [ 4 ] , a [ 5 ] , a [ 6 ] , a [ 7 ] ]
if t == t0134567:
return true
t = [ a [ 1 ] , a [ 2 ] , a [ 3 ] , a [ 4 ] , a [ 5 ] , a [ 7 ] , a [ 8 ] ]
if t == t1234578:
return true

def deletable ( img, x, y ) : # receiving 3 * 3, pass for verification for DOS.
a = [ ]
for i in range ( y- 1 , y + 2 ) :
for j in range ( x- 1 , x + 2 ) :
a. append ( img [ j ] [ i ] )
return check ( a )

def deletable2 ( img, x, y ) : # receiving 3 * 3, pass to test for noise
a = [ ]
for i in range ( y- 1 , y + 2 ) :
for j in range ( x- 1 , x + 2 ) :
a. append ( img [ j ] [ i ] )
return fringe ( a )


Step 3. Selection of special points
It's all trivial. If in a neighborhood of 8 points, there is only one black, then this is the end point. If there are 2 of them, then this is just a point of the line. Three is a branch point.
def checkThisPoint ( img, x, y ) : # count the number of blacks in the neighborhood
c = 0
for i in range ( x- 1 , x + 2 ) :
for j in range ( y- 1 , y + 2 ) :
if img [ i ] [ j ] == 0 :
c + = 1
return c- 1

def findCheckPoint ( img ) : # forming lists of branch points and end points
x = len ( img )
y = len ( img [ 0 ] )
branchPoint = [ ]
endPoint = [ ]
for i in range ( x ) :
for j in range ( y ) :
if img [ i ] [ j ] == 0 :
t = checkThisPoint ( img, i, j )
if t == 1 :
endPoint. append ( ( i, j ) )
if t == 3 :
branchPoint. append ( ( i, j ) )
return ( branchPoint, endPoint )

The only problem was not completely eliminating noise, which led to the appearance of processes that were recognized as special points. In order not to take them into account, the removal of close-standing (10 * 10) branch points and end points was made.
def __removeDouble ( x, y ) : # returns a list of elements that do not have the same in another list
z = [ ]
for i in x:
c = true
for j in y:
if i == j:
c = False
if c:
z. append ( i )
for i in y:
c = true
for j in x:
if i == j:
c = False
if c:
z. append ( i )
return z

def delNoisePoint ( r ) : # inlet tuple (branch, finite)
tmp = [ ]
tmp2 = [ ]
for i in r [ 1 ] :
x = range ( i [ 0 ] - 5 , i [ 0 ] + 5 )
y = range ( i [ 1 ] - 5 , i [ 1 ] + 5 )
for j in r [ 0 ] :
if j [ 0 ] in x and j [ 1 ] in y:
tmp. append ( i )
tmp2. append ( j )
return ( __removeDouble ( r [ 0 ] , tmp2 ) , __ removeDouble ( r [ 1 ] , tmp ) )


Step 4. Comparing points
A simple search for a point that falls in a neighborhood of 30 * 30 and is a point of the same type.
def matchingPoint ( r, v ) : # input: a tuple of reference points and a tuple of the test; output (by coincidence, in total)
all = 0
match = 0
for i in v [ 0 ] :
x = range ( i [ 0 ] - 15 , i [ 0 ] + 15 )
y = range ( i [ 1 ] - 15 , i [ 1 ] + 15 )
all + = 1
for j in r [ 0 ] :
if j [ 0 ] in x and j [ 1 ] in y:
match + = 1
break
for i in v [ 1 ] :
x = range ( i [ 0 ] - 15 , i [ 0 ] + 15 )
y = range ( i [ 1 ] - 15 , i [ 1 ] + 15 )
all + = 1
for j in r [ 1 ] :
if j [ 0 ] in x and j [ 1 ] in y:
match + = 1
break

return ( match, all )


Additionally:
All code is valid for images of the same size (although it will work on different ones).

Findings:
1. This implementation is simple and clumsy. It is possible to supplement it with several checks, for example, to look at the angles of occurrence of lines at particular points. When checking, fold back the pairs already found, for those cases when many points of the same type fall into the neighborhood.
2. The implementation in Python is rather slow: the speed of execution on my machine is completely unsuitable for items with a lot of human traffic. It is possible that using NumPy would improve performance, and I am not the best implementer.
3. Fully take the code here . Tested on this kit .

PS I would like comments on the code, as I am rather weak in the python. Well, the opinions of those who are seriously engaged in fingerprinting.

Source: https://habr.com/ru/post/116603/

More articles:


All Articles