Automated fingerprint matching is a complex process based on rules coded in a programming language. These sets of rules or instructions are called algorithms. They are time-tested, well-defined instructions for processing a fingerprint scan as well as exceptions.
There are different approaches that can be used in the matching of fingerprint images such as transform-based algorithms, correlation-based algorithms, minutiae algorithms, etc.
Minutiae-based algorithms only extract local features of a fingerprint image. Minutiae are basically the characteristics of finger ridges such as ridge ending or ridge bifurcation.
Some algorithms use pattern-based method which covers the whole area of the fingerprint images. It includes both local and global features of a fingerprint image.
This article discusses the minutiae algorithm and steps involved in minutiae-based fingerprint identification such as reference point detection and feature extraction.
Fingerprint sensor working principle
Fingerprint sensors in the fingerprint recognition systems serve as an important component of the data acquisition subsystem. A fingerprint recognition system needs a highly precise digital image of user fingerprints and fingerprint sensors to help them acquire that.
Fingerprint sensors may have different sensing mechanisms such as optical, capacitive, ultrasonic, etc., which leverages different technologies to capture a fingerprint image.
Despite the technological differences in sensing and creating the fingerprint image, all fingerprint sensors have a common objective: to capture a high-quality fingerprint image.
Optical image sensors are more or less like image sensors used in digital photography. They are divided into several pixels that capture information of an image using visible light. The image can be focused on the sensor with the help of lenses.
Capacitive sensors, on the other hand, make use of human skin conductivity to create a fingerprint image. A grid or array of several tiny capacitors is used in these sensors. They are so small that they can act as good as a single pixel of an optical scanner.
Skin conductivity differs in finger ridges and valleys and this difference is captured by the grid of tiny capacitors, creating a fingerprint image depending on the internal programming.
Ultrasonic sensors make use of ultrasonic sound waves to create a fingerprint image. The ultrasonic fingerprint sensor working principle is based on the detection of ultrasonic sound waves that are reflected from the skin surface.
The ultrasonic sensor can create a 3D image of user fingerprints and is considered highly secure than other fingerprint sensor technologies.
Regardless of the difference in sensing technology and working mechanism, the fingerprint sensor working principle focuses on high-quality fingerprint image capture.
The fingerprint matching can be carried out using different methods. Transform-based methods typically use two-dimensional Fourier Transforms and Howe Transforms applied to the pixel array representing the fingerprint.
The idea is to mathematically transform the image in some way and then compare the coefficients of the transformed images. In this context, the features of fingerprints are conversion factors.
A standard has been developed for the transmission and storage of fingerprints using a transformation-based method.
Correlation-based methods take into account that fingerprints and their representative matrices obtained from a scanner cannot simply be superimposed due to all the differences. However, small areas of two fingerprints may be correlated when superimposed.
If the geometric relationships between the centers of small areas remain roughly the same when superimposed to maximize the correlation between the two images, the images may be related to the same papillary ridges of the finger.
The matching of two fingerprint images is based on the numbering of minutiae and bifurcation points. Minutia-based methods tend to emulate what forensic experts do. Minutiae-based algorithms only extract local features of a fingerprint image.
A fingerprint image contains minutiae points, core points, ridges, valleys, background area, foreground area, local features as well as global features.
Ridges are represented by black lines while valleys are seen as while lines in a typical fingerprint image. The core point is the central area of a fingerprint image, while minutiae points are seen as small lines.
- Ridge ending
Minutia points also have a direction associated with the ridge at the point of their origin. A mathematical algorithm moves through the image looking for ridges where they separate or end, and maps the minutiae.
When comparing two fingerprints, minutia cards are placed one above the other and rotated/moved relative to one another. In this case, if a certain number of minutiae are obtained that coincide in position and direction, it is considered a coincidence.
Steps involved in minutiae-based fingerprint identification
Typicalminutiae-based fingerprint identification includes local features of the fingerprint image. The two most prominent local ridge characteristics are ridge ending and ridge bifurcation.
A ridge ending fingerprint is the one in which a ridge ends abruptly. When a ridge forks or diverges into branch ridges, it is called ridge bifurcation. Collectively they are called minutiae.
Minutiae-based fingerprint identification algorithm recognizes fingerprints with the help of valid bifurcation points. The valid bifurcation points are extracted using the cross-numbering method and spurious minutiae are removed by applying false minutiae removal techniques.
For enhancing a fingerprint image intensity adjustment is on the basis of the threshold value. First, obtain the threshold of an image and then based on the threshold, decide whether to adjust the intensity or not. If the intensity is to be adjusted, how much it should be.
Here binarization is done with NOT operation which changes the value and color of ridges and furrows. Here ridges are represented by white or 1’s and furrows are represented by black or 0’s.
Here 1 is the greyscale image and B is a binary image.
Extracting ROI and ridge thinning in fingerprint recognition
OPEN and CLOSE operation is done to extract regions of interest from binary images. Open operations remove noise in the background and close operation shrinks images to remove cavities.
Ridge thinning makes the ridges just one pixel wide without changing their basic structure. It helps in removing the redundant pixels.
A 3×3 pixel window is used to extract the minutiae points. The window contains 0s and 1s values called pixels. If the center pixel having value 1 corresponds to its three neighbors having value 1 then it is called bifurcation point otherwise it is a ridge ending point.
A ridge ending fingerprint is the one in which a ridge ends abruptly. This method of minutiae extraction is relatively simple, which may be prone to extracting false bifurcation points.
After all the bifurcation points are examined, we can apply the false point removal technique.
If any of these points satisfy the bifurcation condition (3 neighboring 1s) that the point is removed and the process is repeated for all bifurcation points.
This is achieved by examining four neighboring pixels – one above, one below, one on the right, and one on the left of a bifurcation point.
After removing these false minutiae points, valid bifurcations were deleted. So to avoid it, the neighboring bifurcation points are deleted, which are just 1 pixel close to each other i.e. there are n 1-pixel close bifurcation points then delete n-1 points.
If a 4×4 pixel window is taken as shown in the table above, then extra neighbors are detected with value one, which creates false minutiae points.
Removal of false minutiae
False minutiae are the points that occur because of breaks, noise, gaps, etc. Sometimes, fingerprint image enhancement process enables removal of false minutiae, so the false minutiae points are removed during the post-processing of the fingerprint image.
- First, calculate the average distance D between two neighbour’s ridges.
- Then calculate the distance between two minutiae points. Let’s call this distance d.
- If d is less than D and the two minutiae points are in the same ridge then remove both of them.
- After the removal of false minutiae points, mark the valid minutiae points and the image is matched on the basis of these minutiae points.
Reference point detection and features extraction are crucial for the minutiae fingerprint recognition and matching algorithm to function. The approach discussed in this article uses local features of a fingerprint image to recognize and match fingerprints.
However, there are matching algorithms that use global features of the fingerprint images such as ridge patterns, their location, rotation as well as the direction of ridges.
Fingerprint matching algorithms that use global features along with local ones are seen to improve the overall feature extraction process, mainly the extraction of bifurcation and total minutiae points.