________________________________________________________________________________________________________________________
Introduction Information Description Functional Description Behavioral Description
Applications Validation Criterion Conclusion
________________________________________________________________________________________________________________________
Functional Description
1. 1.Functional Partitioning.
Since we have used the concurrent development model, our project has been divided into ten modules. The modules were developed contemporaneously with the input image being gray scale image from a scanner scanning at a resolution of 500 dpi. These modules were integrated at a later stage after the development of the entire project.
The modules in our project are:
1.Fingerprint Image Enhancement.
a. Normalization.
b. Gray Filtering.
c. Binarization.
d. Median Filtering.
2. Thinning.
3. Noise Removal.
4. Depuration.
5. Extraction of Minutiae.
6. Matching.
2 .Module Description.
1. Fingerprint Image Enhancement.
a) Normalization
A gray-level fingerprint image, I, is defined as an N XN matrix, where I(i, j) represents the intensity of the pixel at the ith row and jth column. We assume that all the images are scanned at a resolution of 500 dots per inch (dpi). The mean and variance of a gray-level fingerprint image, I, are defined as
and
respectively.
Let I(i, j) denote the gray-level value at pixel (i, j), M and VAR denote the estimated mean and variance of I, respectively, and G(i, j) denote the normalized gray-level value at pixel (i, j). The normalized image is defined as follows:
Where M0 and VAR0 are the desired mean and variance values, respectively. Normalization is a pixel-wise operation. It does not change the clarity of the ridge and valley structures. The main purpose of normalization is to reduce the variations in gray-level values along ridges and valleys, which facilitates the subsequent processing steps.
b) Gray Filtering
Its details are given in median filtering in point (d) later.
c) Binarization (Regional Average Thresholding)
Gray level images cannot be operated on for the determination of key features as the range of values of pixel intensities vary widely. So it is very difficult to discriminate conspicuously the valleys from the ridges, as well as ridge bifurcations from ridge endings. Hence some half toning technique needs to be applied on the fingerprint image. A popular technique is that of Thresholding or Binarization.
In many image-processing applications it is desired to convert the gray images into white and black (bi-level) image. Thresholding involves looking at each pixel and deciding whether it should be converted into white (0) or black (255), The decision is made by comparing the numeric pixel value against a fixed number called a threshold level (T). If any pixel of image (x,y) is less than the threshold level (T), the pixel is set to zero (background point), otherwise it is set to 255(object point).
Our system divides the original image into 4X4 regions. The thresholding is done on each region by using the gray level average of the related region as a single threshold value. This is called regional average thresholding (RAT). In our RAT scheme, on a 256 level gray scale image, a square shaped window of 16 pixels moves around starting from the left hand corner of the image at the bottom. An average threshold level is calculated within the current window but only applied to the first half of the current window. The window then moves by half of the used window size pixels to the adjacent square (For Example, if we use 8 pixel squares, the window moves by 4 pixels to the adjacent square). This time again the left most half of the image window is thresholded although the average threshold level is calculated for the whole window. The process continues until although the image is thresholded in this way. Since, the average threshold levels are calculated regionally, much more of the features are preserved in comparison with global thresholding. This stage also eliminates the fields that contain no information on the edges of the fingerprint.
The algorithm is as follows:
1) Divide the image into 4 X 4 regions.
2) Calculate the average of gray level in the first 4 X 4 region.
3) Threshold the leftmost region of 4 X 2 by using average gray level calculated in stage 2.
4) Move the 4 X 4 operation window by 2 pixels to the right. If right edge of the image is reached, then move the window 4 pixels up and return to the left edge.
5) Repeat stage 2 to stage 4 until the entire image is processed by RAT.
.
c) Median Filtering.
Linear filters effectively suppress Gaussian Noise but perform very poorly in case of binary noise. It is herein that median filters prove to be very handy. The median filter selects the medium value. Since binary noise completely changes the gray value, it is very unlikely that it will show the medium gray value in the neighborhood. In this way, the medium gray value of the neighborhood is used to restore the gray value of the distorted pixel.
Noisy parts of the fingerprint image become more apparent after Regional Average Thresholding operates on the image. The median filtering sorts the pixels in any odd window size (3x3 was used by us) into ascending numerical order and picks the middle value as new value for the pixel of interest which is the centre pixel of the window. In our work the effect of median filtering is applied to both gray scale and thresholded (binary) images.
When it is applied to binary images, the number of background and foreground colors is counted in the window. If the number of background colors is greater than the number of foreground colors, the pixel of interest is set to background color; otherwise it is set to foreground color.
When it is applied to grayscale images, all the pixels in the 3x3 window are sorted in ascending order and the median value is set as the value of the pixel of interest.
2. Thinning
Our thinning algorithm is based on ridge following. Such an algorithm has a better probability of enhancing the required properties of the image. Ridges exist in all fingerprints and they form the features either by ending (ridge endings) or by forking (bifurcations. In our work we use black pixels as the ridges in fingerprints. Our thinning algorithm deals with just black pixels, which are between two white pixels.
Once a ridge is detected by the algorithm, thinning is done by the following the ridge until the algorithm reaches the end of the ridge. Then it starts looking for a new ridge in the image. This is done until all ridges are found out in the binary image
The algorithm operates in the following stages:
The image is read from bottom left to the right side lines by line and the algorithm always tries to find any of black pixels in the original image. Because it is obvious that any of black pixels may be constituent of a ridge.
1) The algorithm finds out (x,y) location of the first black pixel which is not processed yet in the original binary image.
2) A black pixel is inserted into thinned image at (x,y) location (gray pixels) and the black pixel is removed from the original binary image at the location.
3) Then the algorithm looks at the ridge continuity, if there is ridge continuity, it follows the ridge.
The conditions for the ridge continuity are:
1) One of adjacent of (x, y) location must be black pixel.
2) There must be at least one white pixel among the surrounding pixels of this location.
If the algorithm satisfies the above conditions it goes back to stage 2.
If not, it means the algorithm is in the end of the ridge. And goes back to stage 1 and looks for a new black pixel, which is not processed in the image.
During this stage on each step the algorithm runs horizontally or vertically (this depends on the ridge continuity) until it finds the first white pixel and removes all black pixels from the original image. In this way all image processed until all ridges are thinned.
3. Noise Removal.
After applying thinning module we are left with an image that still has got some noise, i.e. some ridges are not of one pixel width or some other noise, This module is used to remove this noise.
In this module we check if in the neighborhood of a pixel there are more than five pixels. Less than five pixels imply that this pixel is a ridge end or bifurcation or some part of a ridge. More than five pixels imply that this pixel is associated with some noise.
4. Depuration.
The image obtained from previous module still is not suitable for minutiae detection. This module removes some more defects.
Depuration of the ridge map involves the removal of the spurious elements, identified as undesirable spikes, and to join the broken lines using a smoothing procedure. This depuration process is carried out be simple rules like:
- To remove small isolated lines.
- To merge all the lines who have end points with similar direction and the distance between them is small.
Steps of the algorithm: -
1. First identify the pixel which is a ridge end
2. Then find out another black pixel in the 7x7 matrix neighborhood of this pixel.
3. If this pixel exists then we find out the slope of two respective ridges at their respective ridge ends in 7x7 matrix.
4. If the slopes obtained are comparable then join ridge ends by using DDA algorithm.
5. Extraction of Minutiae.
Feature (minutiae) extraction is a key step in accurate functioning of any AFIS. Due to imperfections of the image acquisition process, minutiae extraction methods are prone to missing some real minutiae while picking up spurious points (artifacts). Image imperfections can also cause errors in determining the location coordinates of the true minutiae and their relative orientation in the image.
Minutiae may be defined as follows: Whenever there is a ridge bifurcation or a ridge ending in the fingerprint image, it may be regarded as a feature point. These feature points are unique characteristics of a particular image and differ from person to person.
The Feature Extraction consists of finding the ridge endings and the ridge bifurcations from the input fingerprint images, where each minutiae is described by its location (x,y coordinates ). The final ridge structure is used to generate a fingerprint feature vector or minutiae map, which will characterize the fingerprint. This one will be a template formed by a list of minutiae and it will be stored by the system. Minutiae are extracted w.r.t a Reference point which is expected to be present in the image even when it is taken at a different orientation or time.
Minutiae detection:
A simple pattern recognition algorithm for minutiae detection in the fingerprint image, which we have used in our project, is delineated as follows. Without loss of generality, we assume that if a pixel is on a thinned ridge (eight - connected), it has a value on one, and zero otherwise. Let (x,y) denote a pixel on a thinned ridge and N0,N1,N2.... N7 denote its neighbors.
A pixel (x, y) is a ridge ending if:
7
å Ni =2
i=0
I.e. if there is only one black pixel in the entire 8 X 8 matrix nearby to a particular black pixel.
It’s a ridge bifurcation if:
7
å Ni > 2
i=0
i.e. if there are two or more than two black pixels nearer to a black pixel.
However, the presence of undesired spikes and breaks present in a thinned ridge map may lead to detection of many spurious minutiae. The experimental results reveal that our system identifies the most of minutiae present in the original acquired image. Furthermore, we note that the final number of minutiae obtained depends heavily on the image enhancement stages and the noise removal modules, which are the major pre-processing steps.
In our case, we are using text files as databases. We use two text files, one for storing the bifurcation information, and another for storing the ridge information. Every time a new fingerprint image is operated upon, a set of two text files are generated, along with another file for keeping information about the person whose fingerprint is under scrutiny. In case of verification the text files generated are matched with the existing ones, and the number of matches are displayed. The matching is done according to an algorithm that is described in the next module.
3 .Minutiae matching.
Fingerprint matching entails determining the similarity between two such ridge feature maps. This representation is used along with the minutiae set of the fingerprint image for matching purposes. The proposed representation and matching scheme are motivated by the following observations:
(1) Global image information, as defined by the ridge pattern of the fingerprint, is not being explicitly used during the matching phase in most of the current matching systems. We believe that the ridge pattern, when observed at various resolutions and orientations, provides discriminatory information that can be used for matching fingerprints.
(2) Minutiae information may not be very discriminative in the case of solid-state sensors, which typically capture only a small area of the fingertip. For example, the average number of minutiae points extracted from Digital Biometrics optical sensor images (500 X 500 image at 500 dpi) is 45 compared to 25 minutiae obtained from Veridicom solid-state sensor images (300 X 300 image at 500 dpi). Alternate representations, to supplement minutiae information, are necessary to maintain sufficient fingerprint identification performance in such cases. Further, in poor quality images, while it is difficult to accurately locate minutiae points, the ridge pattern features may be easier to detect.
(3) The problem of aligning and registering fingerprint image pairs is a computationally intensive task. Hybrid matchers, that use minutiae sets to align ridge feature maps, do not require additional computation time for registering images.
Minutiae-based technique attempt to align two sets of minutiae points and determine the total number of matched minutiae.
This is done in our matching module in the following way:
Every bifurcation’s information obtained from the recently processed fingerprint is matched with each and every tuple in the bifurcation database of a particular fingerprint feature that had already been extracted and enrolled. The number of matches is noted. The matching procedure is essentially an N X N matching algorithm. The ridge ending tuples of the now generated file is also given the same treatment. The output of the module also shows the number of matches found when the recently processed image is matched with the existing database. This matching is done with every single user enrolled with the database. If no information is found then the software enquires the name of the current user and enrolls her to the database.
Minutiae Matching
