presented by:
P.Srinivasulu
D.Anjireddy
M.Manidha

---

[attachment=9619]
A FINGER PRINT RECOGNISER USING FUZZY EVOLUTIONARY PROGRAMMING
ABSTRACT:
A fingerprint recognizing system is built with two principal components: the fingerprint administrator and the fingerprint recognizer. Fingerprints are identified by their special features such as ridge endings, ridge bifurcation, short ridges, and ridge enclosures, which are collectively called the minutiae. It explains the finger print characteristics that are used to identify individuals and the process of minutiae extraction. The fingerprint administrator uses the method of gray scale ridge tracing backed up by a validating procedure to extract the minutiae of fingerprints. The fingerprint recognizer employs the technique of fuzzy evolutionary programming to match the minutiae of an input fingerprint with those from a database.
1. INTRODUCTION:
Fingerprints have been used for many centuries as a means of identifying people. As it is well known that fingerprints of an individual are unique and are normally unchanged during the whole life, the use of fingerprints is considered one of the most reliable methods of personal verification. This method has been widely used in criminal identification, access authority verification, financial transferring confirmation, and many other civilian applications. In the old days, fingerprint recognition was done manually by professional experts. But this task has become more difficult and time consuming, particularly in the case where a very large number of fingerprints are involved. During the past decade, several automatic fingerprint identification systems have been made available to meet the demand of new applications. The methods used in these systems are still far from complete satisfaction, however, due to in accurate extraction of fingerprint characteristics and ineffective pattern matching procedures, which are the two major tasks of fingerprint identification.
The Federal Bureau of Investigation's method of identifying a fingerprint by its set of minutiae is widely used in automatic fingerprint identification systems. However, the way of extracting a fingerprint's minutiae differs from system to system. Many systems require some form of image preprocessing such as transforming the fingerprint into a binary image and trimming the image's ridges into single pixel lines, before the detection of minutiae is carried out. This may cause some loss of information and result in inaccurate detection of the fingerprint's minutiae. The task of matching an input fingerprint's minutiae with those from a database is much more difficult. The existing methods that are based on mathematical approximation and string matching algorithms or on relaxation and simulated annealing have shown to be rather ineffective and time consuming. The method of discrete Hough transform is obviously inappropriate as the search space is continuous. These difficulties stem from possible skin elasticity, different scales, and difference in positions of fingerprints.
In this paper, we explain the method of direct gray scale minutiae detection proposed in improved by a backup validating procedure to eliminate false minutiae. As for minutiae matching, we employed the technique of fuzzy evolutionary programming, which has been used successfully in speaker identification, images clustering, and fuzzy algebraic operations.
2. Fingerprint characteristics:
A fingerprint is a textural image containing a large number of ridges that form groups of almost parallel curves (Figure 1). It has been established that fingerprint's ridges are individually unique and are unlikely to change during the whole life.
Although the structure of ridges in a fingerprint is fairly complex, it is well known that a fingerprint can be identified by its special features such as:
Ridge endings: The ending of the ridges takes place at the middle as shown in fig 2(a)
Ridge bifurcation: The division of the ridges in the middle as shown in fig 2(b)
Short ridges: The small lines present in between two ridges as shown in fig2© and
Ridge enclosures: These are the loops formed between the ridges as shown in fig 2(d) These ridge features are collectively called the minutiae of the fingerprint. It is also reported in that for automatic detection of a fingerprint, it suffices to focus on two types of minutiae, namely ridge endings and bifurcation. Figure 2 shows the forms of various minutiae of a fingerprint. A full fingerprint normally contains 50 to 80 minutiae. A partial fingerprint may contain fewer than 20 minutiae. According to the Federal Bureau of Investigation, it suffices to identify a fingerprint by matching 12 minutiae, but it has been reported that in most cases 8 matched minutiae are enough.
3. MINUTAE EXTRACTION;
For convenience, we represent a fingerprint image in reverse gray scale. That is, the dark pixels of the ridges are assigned high values where as the light pixels of the valleys are given low values. Figure 3 shows a section of ridges in this representation. In a fingerprint, each minutia is represented by its location (x, y) and the local ridge direction Figure 4 shows the attributes of a fingerprint's minutia. The process of minutiae detection starts with finding a summit point on a ridge, and then continues by tracing the ridge until a minutia, which can be either a ridge ending or bifurcation, is encountered. Details of these tasks are described in the following subsections.
3.1 FINDING A RIDGE SUMMIT POINT:
To find a summit point on a ridge, we start from a point x = (x1, x2) and compute the direction angle by using the gradient method. Then the vertical section orthogonal to the direction is constructed (To suppress light noise, the section gray values are convoluted with a Gaussian weight function). The point in this section with maximum gray level is a summit point on the nearest ridge. The direction angle at a point x mentioned above is computed as follows. A 9×9 neighborhood around x is used to determine the trend of gray level change. At each pixel u = (u1, u2) in this neighborhood, a gradient vector v(u) = (v1(u), v2(u)) is obtained by applying the operator h = (h1, h2) with
to the gray levels in a neighborhood of u. That is, Where y runs over the eight neighboring pixels around u and g(y) is the gray level of pixel y in the image. The angle represents the direction of the unit vector t that is (almost) orthogonal to all gradient vectors v. That is, t is chosen so that is minimum.
3.2 TRACING A RIDGE:
The task of tracing a ridge line to detect minutiae is described in the following algorithm. This algorithm also constructs a traced image of the fingerprint. Every time a new summit point of the ridge is found, its location in the traced image is assigned a high gray value and the surrounding
pixels are given lower gray levels if they have not been marked.
Algorithm 1 (Ridge tracing):
Start from a summit point x of a ridge.
Repeat
Compute the direction angle at x;
Move pixels from x along the direction to another point y;
Find the next summit point z on the ridge, which is the local maximum of the section orthogonal to direction at point y; Set x = z;
Until point x is a termination point (i.e. a minutia or off valid area).
Determine if the termination point x is a valid minutia, if so record it.
End Algorithm 1
There are three criteria used to terminate tracing a ridge. The first stopping condition is that then the current point is out of the area of interest. That is, the current point is within 10 pixels from the border, as experiments show that there are rarely any minutiae close to the edges of the image. The second criterion determines a ridge ending: the section at the current point contains no pixels with gray levels above a pre-specified threshold. In this case, the previous point on the ridge is recorded as a ridge endpoint. The last stopping condition corresponds to the case of a possible bifurcation: the current point is detected to be on another ridge that has been marked on the traced image. Algorithm 1 is backed up by a checking procedure that determines if a termination point is a valid minutia. The procedure is expressed as follows.
Algorithm 2 (Elimination of false minutiae):
If the current ridge end is close to another ridge end with almost opposite direction, then delete both of them and join the gap, as they are simply broken ends of the same ridge. If the current bifurcation point is close to the end of one of its branch, then delete both of them, as short branch of a bifurcation is normally a result of light noise in the image. If the current termination is close to more than two other terminations, then delete all of them, as they are likely caused by damaged ridges in the image.
End of algorithm2
The above algorithms form one major component of our fingerprint recognizing system, called the Fingerprint Administrator. Figure 7 depicts the user-interface feature of the Fingerprint Administrator. The input fingerprint image is displayed in the left box, and the result of ridge tracing and detection of minutia is shown in a traced image in the right box. Observe that in the traced image, the ridge summits are shown in black color, their surrounding of five pixels is colored red, and the detected minutiae are marked with yellow tangent vectors. If the Savebutton is clicked, the coordinates of the detected minutiae and their associated direction angles are saved in a database in the form of linked list. The Fingerprint Administrator is used to extract minutiae of known fingerprints and store them in a database. It is also used to extract minutiae of an input fingerprint for the purpose of identification. Experimental results are reported in