Minutiae Based Extraction in Fingerprint Recognition

The most popular and widely used biometric identification method is fingerprint recognition. Fingerprints are unique and remain permanent throughout a person’s life.

Fingerprint identification has a great utility in forensic science and aids criminal investigations etc. Most of the automatic fingerprint recognition systems are based on local ridge features known as minutiae. Hence it is extremely important to mark these minutiae accurately and reject the false ones.

However, fingerprint images are prone to degradation and corruption due to factors such as skin variations and impression conditions such as scars, dirt, humidity and non-uniform contact with the scanning device. Thus it is necessary to apply some type of image enhancement techniques before minutiae extraction.

The most important step in automatic fingerprint matching is to reliably extract the minutiae from the captured fingerprint images. There exists a variety of techniques for extracting fingerprint minutiae and are broadly classified into two types – techniques that work on binarized images and those techniques that work on gray scale images.

A fingerprint is a distinct pattern of ridges and valleys on the finger surface of an individual. A ridge is defined to be a single curved segment whereas a valley is the area between two adjacent ridges. So the dark areas of the fingerprint are called ridges and white area that exists between them is known as valleys.

In case of a fingerprint identification system, the captured fingerprint image needs to be matched against the stored fingerprint templates of every user in the database. This involves a lot of computation and search overhead and thus we need a fingerprint classification system that will help us to severely restrict the size of the templates database. To accomplish this, we extract the minutiae features and match against the incoming fingerprint. The template size of minutiae-based fingerprint representation is small and most of the fingerprint identification systems are based on minutiae.

Minutiae points are the major features of a fingerprint image and are used in the matching of fingerprints. These minutiae points are used to determine the uniqueness of a fingerprint image. A good quality fingerprint image can have 25 to 80 minutiae depending on the fingerprint scanner resolution and the placement of finger on the sensor.

What is the definition of minutiae? Minutiae can be defined as the points where the ridge lines end or fork. So the minutiae points are the local ridge discontinuities and can be of many types. These types are –

• Ridge ending is the point where the ridge ends suddenly.
• Ridge bifurcation is the point where a single ridge branches out into two or more ridges.
• Ridge dots are very small ridges.
• Ridge islands are slightly longer than dots and occupy a middle space between two diverging ridges.
• Ponds or Lakes are the empty space between two diverging ridges.
• Spurs is a notch protruding from a ridge.
• Bridges are the small ridges that join two longer adjacent ridges.
• Crossovers are formed when two ridges cross each other.

Ridge endings and ridge bifurcations are the most commonly used minutia types since all other types of minutiae are based on a combination of these two types. Figure below shows some of the common minutiae patterns.

It is the most widely used technique of fingerprint representation and its configuration is highly distinctive. It is more accurate compared to other correlation based systems and the template size is smaller in minutiae-based fingerprint representation. In this system, two fingerprints match if their minutiae points match. Minutiae based fingerprint technique is the backbone of most currently available fingerprint recognition products.

Compared to other fingerprint features, the minutia point features having corresponding orientation maps are distinct enough to distinguish between fingerprints robustly. Fingerprint representation using minutiae feature reduces the complex issue of fingerprint recognition to an issue of point pattern matching.

Since the original image cannot be reconstructed using only the minutiae information, the minutiae-based fingerprint identification systems can also assist privacy issues and the minutiae are actually sufficient enough to prove finger individuality. In terms of contrast, image resolution and global distortion the minutiae are more stable and robust in relation to other fingerprint matching schemes.

However, the primary challenge lies in extracting the minutiae from a poor quality image.

A good quality image is absolutely essential for minutiae extraction. However, sometimes the image quality might be poor due to various reasons and hence it becomes necessary to enhance the fingerprint images before minutiae matching of fingerprints. The minutiae extraction methods are classified into two broad categories.

Methods that work on binarized fingerprint images:

1. Methods that work directly on gray-scale fingerprint images.
2. Given below is a diagram showing the different categories of minutiae extraction techniques.

The following subsections will discuss the above methods elaborately.

We will look at the three methods of minutiae extraction from unthinned binarized images. These techniques are: Chaincode processing, Run based methods and Ridge flow and local pixel analysis based methods.

a) Chaincode processing

This technique is based on the chaincode representation of object contours and the pixel image can be recovered fully from the chaincode of its contour. In this method, the transitions from white background to black foreground are identified by scanning the image from top to bottom and right to left. It is then expressed as an array of contour elements by tracing the contour counter clockwise and each element represents a pixel on the contour. By tracing a ridge line along its boundary counter clockwise, a minutiae ending is located when the ridge line makes a significant left turn. Similarly, if the trace makes a right turn a bifurcation minutia is detected.

b) Run representation based methods

This technique is based on the horizontal and vertical run length encoding from binary images. This process results in fast minutiae extraction without requiring a computationally expensive thinning process. After the run-length encoding, the fingerprint images are depicted by a cascade of runs and characteristic images are found out by checking the runs adjacency of the runs. Not all characteristic runs are true minutiae and their validity needs to be checked by some geometric constraints.

This technique of minutiae extraction is explained with the diagram shown below:

As shown in the above figure, the image is pre-processed for enhancement. The image is first extracted from the background by segmenting it and then normalized to have a predefined mean and variance. The local orientation and ridge frequency around each pixel is calculated and the Gabor filter is applied which enhances the ridges oriented in the direction of local orientation. Thus the contrast between the foreground and the background ridges increases and the noise effectively reduces.

The next step is image binarization in which a threshold value is chosen and all pixels having values above the threshold are classified as white while all other pixels are classified as black. A correct threshold is selected by using adaptive image binarization where an optimal threshold is chosen for each image area. As the run-length representation reduces memory space and also speeds up processing time, it is considered very efficient for binary or labelled images.

c) Ridge flow and local pixel analysis

This is a square based method to extract minutiae from unthinned binarized images in which a 3×3 square mask is created around each pixel in the fingerprint image and the average of pixels is computed. The pixel is treated as a ridge termination minutiae if the average is less than 0.25 and a bifurcation minutiae if the average is greater than 0.75.

This method of minutiae extraction is also known as skeletonization-based minutiae extraction. Here again, pre-processing techniques are applied to enhance the image and as explained in the above sections the image is segmented and binarized. The binarized image is then thinned using an algorithm that removes pixels from ridges until the ridges are one pixel wide. After extracting the minutiae from the enhanced, binarized and thinned image some post processing is performed on this final image to eliminate any spurious minutiae. The techniques in this category are of two types – Crossing number based and Morphology based.

a) Crossing number based

Crossing number based is the most widely used method of minutiae extraction in the thinned binarized images category. It is preferred over other methods because of its computational efficiency and intrinsic simplicity. In this method, a skeleton image is used where the ridge flow pattern is eight-connected. As shown in the figure below, the local neighbourhood of each ridge pixel in the image is scanned using a 3×3 window from which the minutiae are extracted.

Then the crossing number value is computed. The crossing number properties can be used to classify a ridge pixel as an ending, bifurcation or non-minutiae point. Figure below shows the crossing number properties.

For example, a ridge pixel with a CN of 0 will correspond to an isolated point and a CN of 4 corresponds to a crossing point.

b) Morphology based

These minutiae extraction techniques are based on mathematical morphology in which the image is pre-processed so as to reduce the effort in the post processing stage. The image is pre-processed with morphological operators to remove spurs, bridges etc. and then the true minutiae are extracted using the morphological hit or miss transform. The morphological operators are shape operators which allow the manipulation of shapes for identification and also the composition of objects and object features. The structuring elements for the different types of minutiae in a fingerprint image are developed by this technique which are then used by the Hit or Miss transform to extract the valid minutiae.

Although it is still being researched, there are a number of techniques to extract minutiae directly from gray scale fingerprint images without binarization and thinning. This extraction technique has a lot of relevance due to the following reasons:

• A great deal of information might be lost during the binarization process.
• Binarization and thinning are time consuming processes.
• Binarization thinning operations introduce a large number of spurious minutiae.
• The binarization techniques do not prove to be particularly useful when applied to low quality images.

One of the proposed methods in this technique is to directly extract the minutiae from the gray scale image by following the ridge flow lines with the help of local orientation field. This method works on finding a local maximum relative to the cross-section which is orthogonal to the ridge direction.

A gray scale image is observed to have two distinct levels of gray pixels. One such level is formed by darker pixels and constitutes the ridges. The other level is formed by the lighter pixels and constitutes the valleys and furrows. These two levels are modelled using fuzzy logic and then appropriate fuzzy rules are applied to extract the minutiae accurately.

In this article, we reviewed the different techniques of extracting minutiae from fingerprint images. We see that the quality of fingerprint images are directly linked to the good performance of automatic fingerprint authentication systems.