Dealing with the minutiae of fingerprint analysis -

Dealing with the minutiae of fingerprint analysis


Click image to go to digital edition.

Fingerprint analysis involves using fingerprint sensors and sophisticated DSP-based image-processing algorithms. Here’s a description of the minutiae-based system for fingerprint analysis.

Many biometric characteristics are used to verify identity, including hand and face geometry, retinal scans, voice recognition, and fingerprint analysis. Because no two fingerprints have ever been proved identical, fingerprint matching is among the most popular and accurate biometric techniques used for identification purposes.

A popular and reliable way to compare fingerprints is to analyze the minutiae of the fingerprint. To do so, a system must first capture the image of a fingerprint and process the image to make it easy for image analysis. After the analysis, the minutiae will be extracted and saved in a template format. The system must then store the data of the minutiae to be used for future comparison. Figure 1 illustrates a typical fingerprint authentication processing flow.

Click on image to enlarge.

Fingerprint sensors
Based on the fingerprint processing diagram, a sensor is the “front-end” of the system, playing an import role: it captures the image of the fingerprint. The two types of popular sensors used in fingerprint analysis are the optical and swipe sensors. Here are basic descriptions of how they operate.

Optical sensor. An optical fingerprint sensor captures a digital image of the fingerprint by using visible light. The following describes the operation principle of an optical sensor (see Figure 2 for an illustration):

  • First, the light source inside of a sensor will emit light to illuminate the surface of the finger.
  • The light reflected from the finger passes to a solid-state pixels sensor (either a charge-coupled device [CCD] or complementary metal oxide semiconductor [CMOS] image sensor), which captures a visual image of the fingerprint. On the path of the light, a specially designed lens will be used.

Click on image to enlarge.

Swipe sensor. A swipe sensor is a type of active capacitance sensor. Here is how an active capacitance sensor works (see Figure 3 for an illustration):

  • First, the active capacitance sensors will apply a voltage to the skin. This will generate an electrical field in the space between the skin and sensor.
  • Since the electrical field between the finger-skin and sensor follows the pattern of the ridges in the dermal skin layer, the effective capacitance will be measured across this field.
  • The distances between skin and sensors can then be calculated mathematically by using this equation: C = ε0*εr*(A /d ); here “d ” represents the distance.
  • Based on the calculated distances across the field, the fingerprint image can be mapped.

Click on image to enlarge.
Fingerprint processing
After an image of a fingerprint is captured, a sequence of image processing algorithms will be applied to the captured image. In fingerprint authentication applications, two main types of technologies are being used: one is called minutiae based , and the other is called image based . This article presents the minutiae–based flow. The following sections will describe the main steps of the process as well as the key functions of each processing algorithms.

Minutiae are the special spots of a fingerprint that show the changing of the print. These spots have been predefined and categorized. Figure 4 shows two main features of minutiae, which are extracted from these spots:

  • Ridge ending.
  • Bifurcation.

Click on image to enlarge.

However, the minutiae are not limited to these two features.

In a minutiae-based system, the goal is to find the minutiae in the captured fingerprint image and compare them with fingerprints that are in the database. In order to extract the minutiae successfully, the fingerprint images must be preprocessed, which usually involves computationally-intensive image processing algorithms. The digital image signal processing steps include:

  • Segmentation and filtering.
  • Contrast enhancement.
  • Orientation calculation.
  • Gabor filtering.
  • Binarization.
  • Thinning.
  • Feature extraction.

Segmentation and filtering. The main purpose of segmentation is to get the “good” area of a captured fingerprint image, then separate this valid fingerprint from the image background. Some filtering can be applied to the image to filter out the noise in the image.

Contrast enhancement. After segmentation, the image is subjected to gray stretch to increase the global contrast of the image. Because the skin of an entire finger has a similar color, the more interesting parts of the fingerprint and the less interesting areas have a very low level of contrast. During this step, the algorithm will stretch the gray levels of the ridges, short ridges, and bifurcation of the fingerprint and compress the gray levels of the less interesting parts of the fingerprint. Mathematically, this type of operation is transformation .

Orientation calculation. The ridges of fingerprint have a “directional” characteristic. Mapping out the orientation of a fingerprint’s ridges is essential for getting the valid minutiae. There are different implementations for mapping the orientation of a fingerprint. The most popular algorithm to map the orientation of fingerprints is the gradient-based approach.

The gradient ∇(x, y) at point [x ,y ] of I (an image) is a two-dimensional vector [∇x(x, y)∇y(x,y)].

Mathmatically, gradient ∇ is the first derivative of the image, the ∇x and ∇y are the derivatives on X and Y directions, respectively.

In a fingerprint system, to numerically calculate the ∇x(x, y)and ∇y(x,y), a popular method is to use the Sobel operator. The following is a 3×3 Sobel mask:

Click on image to enlarge.

The gradient can be calculated as following:

Click on image to enlarge.

Then the gradient’s direction, angle θ, can be calculated as:

Click on image to enlarge.

These calculations will be applied across the fingerprint image, and an orientation map will be created.

Gabor filtering.
A Gabor filter is defined as a two-dimensional Gaussian function multiplied by a sinusoidal plane wave function:

Click on image to enlarge.

Here the x θ and y θ are the point coordinate [x,y ] rotated (90-θ) degrees, defined as:

Click on image to enlarge.

Also, here:

  • θ represents the orientation.
  • f represents the frequency of the ridge-valley-ridge pattern; it can be the reciprocal of the width of ridge-valley measurement.
  • σx and σy are the standard deviations of the Gaussian envelope on x and y directions, respectively.

Based on its definition, we can tell that the Gabor filtering is selective on both frequency and direction; this characteristic will dramatically enhance the fingerprint image. The certain desired frequencies of the image have been enhanced, and undesired noise has been removed. This leads to a robust image for reliable minutia-feature extracting.
Binarization. So far, the image we discussed is in gray-level and has many levels of intensity. The goal of binarization is to convert the gray-level image to binary level “1” or “0.” In other words, this space-changing operation converts the image to black or white with no levels in between. The key in this operation is to set the threshold value between black and white. Depending on the implementation, there are various ways to set the threshold value. Also, some filtering, such as band-stop, can be applied to prevent information loss.

Thinning. After the binarization, the ridges and valleys are in black and white, respectively, but the width of lines may be wider than one pixel. To further reduce the complexity of minutiae extraction, a thinning algorithm will be applied to the image. Usually a 3×3-pixel window is applied to each pixel across the image. In total, nine neighboring pixels will be used at one time. Depending on the calculation result, a decision will be made whether or not to select the current pixel in the skeleton line.

Feature extraction. Figure 5 illustrates the fingerprint image for each processing step during the entire fingerprint analysis flow. After these steps of signal processing, we will obtain the final fingerprint image. The minutiae-based features, such as ridge ending and bifurcation, will be found and extracted from the final image.

To illustrate how a minutia is found, let us take a closer look at the last image of Figure 5 and zoom in on a ridge-ending area as an example. In the checker diagram in Figure 6 , each grid represents one pixel. By comparing the center pixel values with the neighboring pixels in this window, a minutia can be detected. From the algorithm’s aspect, the result of this comparison is defined by the “crossing number” cn(p) numerically. The value of the crossing number will determine if a minutia is there and what kind of minutia it is.

Click on image to enlarge.

Click on image to enlarge.

Selecting a processor for fingerprint analysis
Usually the application- or system-level requirements will play the dominant role in your decision when your team selects the platform. Using the entrance and access control as an application example, let’s take a quick look at the rough requirements:

  • Speed: for residential or some commercial use, less than two seconds of recognition time is desired.
  • Size of the fingerprint identification database: for commercial use, such as a medium-size department store, between 50 to 100 prints is desired.
  • Power consumption: for battery-powered systems, the battery-changing frequency should be in the months range.

Back on the processing level, we have seen so far that fingerprint analysis is a calculation-intensive application. However, if we emphasize the performance by simply increasing the frequency of the central processing unit (CPU), we will not be able to meet the power requirement. It will be a critical decision to select a processor with an optimized architecture. The following factors should be kept in mind when making that decision:

  • The core architecture of a processor: A dual multiply-accumulate (MAC) or single-MAC core should be considered for this application. The MAC will perform the calculation like: x = a*b + c in one CPU cycle. Fundamentally, the MAC is not a separated multiplier and adder; instead it is an integrated singular hardware design.
  • Bus architecture: The x = a*b + c calculation is directly related to the efficient implementation of the convolution algorithms based on the y [n ] =∑c [k ]∗x [nk ] computation, which has been widely used during the entire processing flow as described in this article. If we take a close look at this calculation, the “a,” “b” and “c” are the data from memories, such as pixel values. (To sustain this single cycle calculation, a parallel multi-bus architecture will be essential to fetch different data from memories in a single cycle.)
  • Power management integration: Integration of power management enables high efficiency.
  • Others : Other important considerations include dedicated hardware for different addressing modes, loop control and execution control and peripheral integration.

These key factors show a strong correlation with entrance/access control application requirements. An optimized processor will lead to a highly efficient fingerprint analysis system in aspects of in performance, power consumption and cost.

Wen Li is an elected member of the technical staff at Texas Instruments, where he has worked since 1996. He has over 15 years of experience in VLSI design, system, and application engineering. His main research interests are video and image processing, ultra-low-power digital signal processor architecture and signal processing in biometrics applications. Li received a master of science degree in electrical engineering from the University of South Florida, Tampa.

Srik Gurrapu has been with Texas Instruments for more than 10 years and has worked on various technologies in digital communications and audio processors, wireless base stations, and embedded processors. He is a member of the technical staff. Gurrapu has a master’s degree in electronic and computer engineering from University of Kansas as well as two patents in embedded processing architectures.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.