Fingerprint Identification Using Local Features Computer Science Essay

Published:

This chapter presents two novel algorithms. The first proposed algorithm is for person identification based on the local features of fingerprint image. The second proposed algorithm is a novel thinning algorithm capable of thinning the fingerprint image to a single pixel width. In this chapter we shall concentrate on detection of bifurcation points as the local features of a fingerprint image. In the literature many schemes uses local landmarks i.e. minutiae based fingerprint matching systems. The minutiae based automatic identification techniques first locate the minutiae points and then match their relative placement in a given finger and the stored template. A good quality fingerprint contains 60 to 80 minutiae, but different fingerprints have different number of minutiae. The major steps for minutiae extraction in the proposed algorithm that uses local features for person identification are smoothing, local ridge orientation estimation, ridge extraction, thinning, and minutiae detection. Recognition results are heavily dependent on the accuracy of each step. After finding the minutia points in the fingerprint image, matching is carried out using Euclidian distance between the query and template image. Performance of the proposed algorithm has been evaluated in terms of total error rate and found to be 4.5%. The second proposed algorithm is the modification in the thinning algorithm proposed by Ahmed et al [93]. The unique feature that distinguishes the thinning algorithm is that it thins the symbols (any) or fingerprints to their central lines i.e. the shape of the symbol is preserved and the method is rotation invariant. Also, the diagonal lines of two pixel width either in horizontal or vertical i.e. the extremity of a zigzag diagonal line are converted into a exact diagonal of single pixel width, which was not considered in [93]. The algorithm is iterative. The system has 21 rules in its inference engine. These rules are applied simultaneously to each pixel in the image for every iteration. Therefore the system has advantages of symmetrical thinning and speed. The result of thinning shows that the algorithm is very efficient in preserving the topology of any symbols or fingerprints, even if it is containing exact diagonals. The modified thinning algorithm is implemented for thinning fingerprints to a single pixel width. To this single pixel wide image we implement a 24 rule based mask for detection of ridge bifurcations, which will be helpful in recognition/identification of fingerprints.

4.1 Introduction

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

Fingerprints are the ridge and furrow patterns of the tip of the finger and can be used for personal identification of people. An automatic recognition of people based on fingerprints requires the input fingerprint to be matched with a large number of fingerprints in a database. Different databases may consist of large sets of data dealing with various features extracted from a fingerprint. There are two main types of features in a fingerprint: the first contain local ridge and furrow minute details of features such as ridge endings and bifurcations, also known as minutiae, and the second contain global ridge and furrow structures that form special patterns in the central region of the fingerprint.

4.2 Fingerprint identification using minutia features

This Section describes the traditional method of person identification based on minutia features. Minutia are the local anomalies in the ridge flow like ridge endings and ridge bifurcation points in the fingerprint image as shown in Figure 4.1.

Figure 4.1 Minutia points in the fingerprint image.

The method of person identification using local features of the fingerprint image works only for the good quality fingerprint images. It also needs pre-processing and post-processing steps. Various steps involved in the minutia based fingerprint matching are shown in Figure 4.2. The method is suitable for applications like access control, transactions etc.

Image ROI Ridge image Thinned Minutiae

Figure 4.2 Steps in minutia extraction.

After finding the minutia points in an fingerprint image the matching is carried out to find the distance between the minutia points of two fingerprint image as shown in Figure 4.3. Euclidian distance is used for matching the two fingerprint images. The performance of the proposed algorithm is evaluated on the FVC 2002 database in terms of total error rate. For FVC2002 with 2800 genuine tests and 4950 impostor tests a best result of Total Error Rate of 4.5% is obtained. The results are graphically illustrated in Figure 4.4.

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

Figure 4.3 Fingerprint verification using minutia features.

Figure 4.4 Performance evaluation of the proposed algorithm on FVC2002 database.

4.3 Thinning of fingerprint images

Thinning is the process of reducing the thickness of each line of patterns to just a single pixel. The requirements of a good thinning algorithm with respect to a fingerprint are 1) The thinned fingerprint image obtained should be of single pixel width with no discontinuities, 2) Each ridge should be thinned to its centre pixel, 3) Noise and singular pixels should be eliminated from the image. Many rules applicable for thinning of characters or symbols may not be necessarily applicable for thinning of the fingerprint images. For example most of the algorithms take care that singular pixels should not be deleted. But in a fingerprint image such singular pixels are unnecessary and can be safely removed. Traditionally a large number of thinning algorithms are present but none of the methods, address rotation invariant thinning. Many are specific to digits, characters, and letters written in English, Chinese, Arabic, or any other script. In this Section we present a thinning system that can be used to thin any symbols irrespective of their shape and orientation. The resultant thinned symbol will be the central lines of the symbol and thus the system is invariant to rotations on the original pattern. The thinned pattern is single pixel wide. The system preserves the topology and does not produce any discontinuity. The thinning algorithm to be applied is iterative and the number of iterations depends on the thickest ridge present in the image. On completion of the thinning process we apply 24 rule-based masks on the thinned image to extract the bifurcation points of the image.

4.3.1 Proposed rotation invariant thinning algorithm

The algorithm is iterative. Our process of thinning begins with eliminating the pixels that lie on the outer boundary of the ridges until the ridge is one pixel wide. This result in the 21 rules listed in Figure 4.5.

Rule 2

IF THEN

1

X

0

1

1

0

1

1

X

1

X

0

1

0

0

1

1

X

Rule 3

IF THEN

IF THEN

1

1

X

1

1

0

1

X

0

1

1

X

1

0

0

1

X

0

Rule 1

IF THEN

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

Rule 4

IF THEN

IF THEN

1

1

1

X

1

1

0

0

X

1

1

1

X

0

1

0

0

X

Rule 5

IF THEN

1

1

1

1

1

X

X

0

0

1

1

1

1

0

X

X

0

0

Rule 6

IF THEN

1

X

0

1

1

0

X

0

0

1

X

0

1

0

0

X

0

0

Rule 7

IF THEN

IF THEN

1

1

X

X

1

0

0

0

0

1

1

X

X

0

0

0

0

0

Rule 8

IF THEN

IF THEN

1

1

1

1

1

0

1

1

1

1

1

1

1

0

0

1

1

1

Rule 9

IF THEN

1

1

1

1

1

1

1

01

1

1

1

1

1

0

1

1

0

1

Rule 10

IF THEN

X

0

0

1

1

0

1

X

0

X

0

0

1

0

0

1

X

0

Rule 11

IF THEN

IF THEN

0

0

0

X

1

0

1

1

X

0

0

0

X

0

0

1

1

X

Rule 12

IF THEN

IF THEN

X

1

10

01

1

X

0

0

0

X

1

1

0

0

X

0

0

0

Rule 13

IF THEN

0

X

1

0

1

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

1

0

0

X

0

X

1

0

0

1

0

0

X

Rule 14

IF THEN

0

0

0

0

1

X

X

1

1

0

0

0

0

0

X

X

1

1

Rule 15

IF THEN

0

0

X

0

1

1

0

X

1

0

0

X

0

0

1

0

X

1

Rule 16

IF THEN

IF THEN

1

1

1

0

1

1

1

1

1

1

1

1

0

0

1

1

1

1

Rule 17

IF THEN

1

0

1

1

1

1

1

1

1

1

0

1

1

0

1

1

1

1

Rule 18

IF THEN

IF THEN

0

X

1

0

1

1

X

1

1

0

X

1

0

0

1

X

1

1

Rule 19

IF THEN

IF THEN

X

1

1

0

1

1

0

X

1

X

1

1

0

0

1

0

X

1

Rule 20

IF THEN

IF THEN

0

0

X

X

1

1

1

1

1

0

0

X

X

0

1

1

1

1

Rule 21

IF THEN

IF THEN

X

0

0

1

1

X

1

1

1

X

0

0

1

0

X

1

1

1

IF THEN IF THEN

IF THEN IF THEN

IF THEN IF THEN

IF THEN IF THEN IF THEN

Figure 4.5 Twenty-one rules for thinning.

These rules are applied simultaneously at every iteration to each pixel. If the resultant image has a ridge of single pixel width then that pixel is to be considered as the centre pixel of the ridge. In each iteration we delete the outermost pixel of a ridge until it attains single pixel width. For the thinning process we consider a pixel neighborhood of a black pixel and its 8 neighbor pixels. If we simply apply only the 21 rules some ridges containing only two-pixel width are deleted causing discontinuities. To overcome this problem, apart from the 21 rules, other issues have to be considered initially. These issues are taken care by following the procedure.

4.3.2 Thinning of Diagonal Lines

Ahmed et al [93] have presented a rule-based rotation-invariant thinning algorithm to produce a single-pixel wide skeleton from a binary image. In this method diagonal lines having two pixels either in horizontal or in vertical has not been considered for thinning. This leads to diagonal lines with two-pixel width within the image. To overcome this we shall rotate the two masks shown in Figure 4.6 over the resultant image after completion of all iterations. Peter I. Rockett [94] also showed examples where this algorithm fails on two-pixel wide lines and proposed a modified method which corrects this shortcoming based on graph connectivity. Figure 4.7(a) shows the original image consisting of diagonal lines with varied pixel widths. Figure 4.7(b) is the thinned version using the method in [93]. It can be seen that diagonal lines are not thinned to single pixel width. Figure 4.7(c) is obtained by using our modified algorithm and the results obtained displays a uniform image of single pixel wide diagonals.

If Then

(a)

If Then

(b)

(b)

Figure 4.6 Masks for conversion of double pixel diagonals to single pixel diagonals.

(a)

(b)

(c)

Figure 4.7 (a) Original image consisting of diagonal lines with varied pixel width,

(b) Thinned by Ahmed and Ward algorithm (c) Thinned by proposed algorithm.

4.3.3 Steps to be followed for Thinning

Repeat the following iteration until no changes occur from one iteration to the next. For th iteration of thinning algorithm at any pixel in the image apply steps 1 to 7 as below:

If belongs to two pixels wide in the vertical direction, go to 2). If belongs two pixels wide in the horizontal direction, go to 3); otherwise go to 6.

If belongs to Figure 4.8(a), stop calculations for that pixel, otherwise check if belongs to Figure 4.8(b). If yes, delete and stop calculations for that pixel, otherwise go to 4.

If belongs to Figure 4.8(c), stop calculations for this pixel, else, check if belongs to Figure 4.8(d), If yes, delete and stop calculations for this pixel, otherwise go to 5).

Ifbelongs to Figure 4.8(e) or Figure 4.8(f), stop calculations for that pixel, otherwise check if belongs to Figure 4.8(g) or Figure 4.8(h). If yes, stop calculations for this pixel, otherwise go to 6).

Ifbelongs to Figure 4.8(i) or Figure 4.8(j), stop calculations for that pixel, otherwise check if belongs to Figure 4.8(k) or Figure 4.8(l). If yes, stop calculations for this pixel, otherwise go to 6).

Apply the 21 rules and stop calculations for this pixel.

After completion of the above iterations run the masks of Figure 4.6(a) and Figure 4.6(b) over the resultant image to remove any diagonal pixels.

(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l)

(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l)

X

0

X

1

w

1

1

1

1

X

0

X

X

0

X

1

1

1

1

w

1

X

0

X

1

w

1

1

1

1

X

0

X

1

1

X

1

w

1

1

1

1

X

0

X

1

1

X

X

0

X

1

w

1

1

1

1

X

0

X

X

0

X

1

1

1

1

w

1

X

0

X

1

0

0

1

1

0

0

w

0

0

0

0

1

0

0

1

1

0

0

w

0

0

0

0

0

0

0

0

w

1

0

0

0

0

01

0

0

0

1

0

w

1

0

0

0

1

01

0

0

0

0

0

1

w

0

0

0

0

01

0

1

1

0

0

1

w

0

0

0

0

01

0

Figure 4.8 Various masks for pre-thinning procedure.

4.3.4 Implementation of Thinning Algorithm on Fingerprint Image

On completion of the above procedure we shall achieve the thinned image of the original fingerprint. Figure 4.9(a) shows an original image that has to be thinned. Figure 4.9(b) shows the image obtained using the Hilditch algorithm, Figure 4.9(c) shows the thinned image using [60], and Figure 4.9(d) shows the thinned image obtained by using our modified algorithm. It can be seen that the Hilditch algorithm produces an image whose ridges are not centered. Also the ridge ends are shortened producing false ridge ends. Figure 4.9(c) does not take into consideration single or isolated pixels, which may be caused due to noise present. Also diagonal lines have not been thinned to single pixel value. Figure 4.9(d) shows a highly thinned image whereby the single pixels (individual pixels) are eliminated and hence noise is suppressed. Also diagonal lines are thinned to single pixel values.

(a)

(b)

(c)

(d)

Figure 4.9(a) Original Fingerprint Image, (b) Thinned by Hilditch algorithm,

(c) Thinned by Ahmed and Ward algorithm, (d) Thinned by proposed algorithm.

4.3.5 Ridge Bifurcation Detection

A ridge bifurcation is that point on an image where the ridge branches out into two. This feature is unique for every other fingerprint and is used for fingerprint recognition. A database is created for all the detected ridge bifurcations in an image after false rejection. The 24 masks shown in Figure 4.10 consider all possibilities of occurrence of bifurcations. Each mask is applied simultaneously to the thinned image. The center pixel of the mask is the point of bifurcation.

(1) (2) (3) (4) (5) (6) (7) (8)

(9) (10) (11) (12) (13) (14) (15) (16)

(17) (18) (19) (20) (21) (22) (23) (24)

Figure 4.10 Masks of all bifurcation points.

The conditions to validate a bifurcation point are as follows:

There must be minimum three pixels within the immediate neighborhood of the center pixel such that all three pixels apart from the center pixel are never adjacent to each other.

The maximum number of pixels allowable in the mask is 5.

The center pixel is connected to every other pixel.

Since all possible conditions have been considered here the process is rotation invariant and hence can be applied to any fingerprint image. The results obtained are found to have the same distances between bifurcation points irrespective of their orientation. After obtaining the thinned image of the original fingerprint we shall rotate the masks in Figure 4.10 over the single pixel image for recognition of bifurcation points. Figure 4.11(a) is the same as Figure 4.9(d). Figure 4.11(b) displays the bifurcation points present. Figure 4.11(c) displays the bifurcation points after false rejection. For false rejection we have used a mask.

(a)

(b)

(c)

Figure 4.11 (a) Thinned image, (b) Bifurcation points,

(c) Bifurcation points after false rejection.

4.4 Conclusions

Thinning algorithm should preserve the topology (shape) of symbols. Preserving shape is accomplished by representing symbols by their central lines. Since the central lines of the symbol form the resultant thinned symbol, our system can be used to thin symbols, characters and letters belonging to any language or script, or fingerprint images. The proposed algorithm has 21 rules that are applied in parallel on every pixel in each iteration. The number of iterations is half the number of pixels in the thickest part of the pattern. The method has the advantage of being rotation invariant, if the original image is rotated, the resultant thinned image is also rotated by the same angle. Also, the diagonal lines of two-pixel width either in horizontal or vertical i.e. the extremity of a zigzag diagonal line are converted into a exact diagonal of single pixel width. Experimental results show that the developed method is effective, fast, and can thin any symbol, irrespective of the direction of rotation or flipping, or containing the extremity of a zigzag diagonal line. The system is also shown to tolerate noisy symbols.

***