Automatic Fingerprint Identification System using P-tree[1]
William Perrizo
Computer Science Department, North Dakota State University
Fargo, ND 58105, USA
And
Mohammad Kabir Hossain
Computer Science Department, North South University
Dhaka, Bangladesh
Abstract:
Fingerprint image analysis for automatic identification technology has been develops to the point where it can be used in a number of major applications. Important industries affected by this technology include network security and protection, smart money, ATM transaction, and biometric identifier systems for many major government sectors such as FBI, NIST, and DMV. In this paper we first review the technology behind such a identification system and then we propose a new method for fingerprint identification system. This new method involve with the use of P-tree which is mostly for using spatial raster data.
Key words: Fingerprint, Automatic fingerprint identification system, matching, search space, image processing, P-tree, quadrant ID.
1. Introduction:
The fingerprints have been uses as mean for identifying individual for a long time because the fingerprints are unique and stay unchanged through out an individual life time [1]. Currently there are about 200 million FBI cards (10 fingerprints per cards) stored in cabinets that would fill an area of one acre. The manual effort of identifying and maintaining such a system is very cumbersome, time consuming and expensive as the number of finger print records grow at a rate form 30 to 50 thousand per day [2].
With the advancement of computer technology the problem of automatic finger print identification has attracted wide attention among researchers since 1969 that result in few state of the art automatic fingerprint identification system (AFIS).
Going in hand, with the recognition problem, is the problem of real-time matching system for large fingerprint databases. Since the storage requirement for such a large amount of data can be thousands of terabytes system, data compression is another aspect of automatic identification using fingerprints. Currently FBI data compression specification for finger is the de facto national standard, which is based on wavelet transform scalar quantization (WSQ). In this paper we are proposing a new technique for data compression also that is using P-tree, as P-tree is a loss-less data compression technique [3].
2. Context:
How and exactly when the awareness of papillary ridge designs on human fingerprint entered into the consciousness of mankind, is difficult to say now, but there are ample proofs available that by 3000 B.C. people had knowledge about these intricate designs found on human hands and fingers [4]. Palm print of at that time has been found on the slab of clay in the tomb of Egyptian king Tut en Khamen [4]. But as stated earlier the actual research has begun in this field after the advancement of computer knowledge and different pattern recognition theories are used in this context [5].
3. Preview of AFIS:
There are four main parts of an AFIS; they are Image processing, Recognition algorithm, Database searching, and Data compression algorithm.
3.1 Image processing:
Taking the image: A live scanner is used to capture the image from an individual’s finger. The scanner should have good resolution with 500 pixels per inch in both row and column.
Noise reduction: There is one potential problem of the scanner being high resolution that is it would introduce unexpected dots in the image from dust or sweat under the finger. Various algorithms exist to eliminate those noises.
Thinning: The image taken from the scanner has another problem. The quality of image becomes different when taking the image of the same finger depending on the pressure applied to the scanner. Some time the lines of the fingerprint become thicker with high pressure and some time not so thick although these two images are of the same finger. It introduces extra work to do. So what is done the image is first thinned to a single lined for all the lines in the fingerprints [6].
Saving- The image after the above processing is saved for future reference.
3.2 Recognition Algorithm:
Current fingerprint verification system consists of two stages: Feature extraction and feature matching.
Feature extraction-it involves identifying different features of a fingerprint like arch, tended arch, loop, whorl etc.
Feature matching-This features are then matched with the features of the fingerprint stored in the database. Figure shows a typical AFIS and how it works.
Figure 2: AFIS
3.3 Database Searching:
As the database of the fingerprint is very large the efficient search techniques should be used to prune the database to reduce the search space.
3.4 Data Compression:
Data compression is another important issue of such system because the fingerprints are adding to the database in a large volume. The compression technique must also be lossless so that no important feature of a fingerprint is lost during the compression.
4 Main Idea:
What we have done in this paper is that we introduce P-tree in the whole process. First it begins with the image processing.
P-tree may be used in two different aspect of fingerprint identification system one, it can be used as exact matching of two image or two, to reduce the search space.
In this paper we also introduce some improvement in such system while using R-tree. We are discussing them below.
4.1 Introducing P-tree:
At first image clipped, thinned to the appropriate size. As the characteristic of the fingerprint shows, we can clip the side most parts of a finger print keeping its main feature that is distinguishing features. This process will reduce the image size and will help us in later works. The reason of thinning an image has been discussed earlier.
Image is then converted into black and white image of lines and curves. The whole image is then converted into one bit one band spatial data in raster order.
So the whole image can be represented in one P-tree for further processing. We assume that we do not need any shifting and rotating operation of the finger print image.
4.2 Constructing the P-tree:
First we divide the processed image into equal number of rows and columns. The number of rows and column must multiple of four so that we can construct P-tree. The higher those numbers the better the resolution would be. Figure 3 shows the division of an image into 16 rows and 16 columns.
Figure 3
After that we examine individual pixels whether any line of fingerprint has passed through that pixel or not. If one passing line is found then that pixel is given a value 1 and else its value remains 0. After completing this task we are left with n x n matrix of bit patterns (in figure 3 it is 16x16) from which we will construct our P-tree.
Following figure 4 shows the P-tree constructed from the finger print shown in figure 3.
4.3 Matching of Fingerprints:
After converting the image into P-tree the matching of two fingerprints is nothing but matching of two P-trees. As stated earlier matching task can be done for two purposes-for exact matching and for search space reduction.
Figure 4: P-tree (3 levels shown)
For exact matching we will, beginning form the top level, first compare the root counts of two P-trees. If they match we will go one level down and match four quadrant of the root node. At this we will compare the quadrant ID Q0 , Q1 , Q2 , Q3. If these quadrant match for both P-trees then we will further go one level down to the Q0.0, Q0.1,Q0.2, Q0.3 and then Q1.0, Q1.1,Q1.2, Q1.3 …and so forth. If they match we will go one level down and check Qi,j,k and ultimately go to the root node. If the root counts match all the way to the leaf node we will decide that the two finger print match. But if at any of the above places if two root counts do not match we will decide that these two fingerprints do not match.
In the figure 6 we showed another finger print and compare those two. We see that these two finger prints do not match as they differ in the Q2 and Q3.
Figure 6:
In case of reducing search space we will not go through the leaf nodes of the tree rather we will stop matching some level after the root of the P-trees. And in case of matching we might introduce a threshold value t, if two root counts differ more than t we will say that they do not match and discontinue our search. But if the difference is less than t we will continue our search. Thus after certain level of exploration we will reduce the search space in great deal.
4.4 Some improvement:
If we look closely to the bit maps of the two finger print images in the figure 7, we will see that they are almost alike. In fact, fingerprints mostly differ from one another in the middle or center. So we can reduce the search space if we first begin our matching from the center of the images.
Figure : 7
Now there is a way of doing this. For that, we will find the center image of the first finger print by calculating the root counts of the following
Center Count= RC(Q0.3+ Q1.2+ Q2.1+ Q3.0) … … … (1)
Now we calculate the value of equation (1) for both the fingerprints and we find that although their root counts are same they differ form one another because Center counts are 29 and 27 respectively and do not match.
5. Conclusion and Future work:
In this paper we have shown how we can apply P-tree in finger print identification. In fact this idea can be implemented in any scene-matching algorithm. This can be applied more efficiently if we can find suitable algorithm for shifting and rotating bits in a P-tree. So much work can be done in future in this regard.
Also as future work, this method will be compared to current practices regarding fingerprint management and matching.
Reference:
[1] Finger Print Recognition: Technology and application – Tri Caohuu, Dept of EE, San Jose Stat University, One Washington square, San Jose, CA 95192-0084
and
Le Thuy, Super Computer Group, Fusitsu of America, Inc. 3055 Orchard Drive, San Jose, CA 95134-2022
[2] C.M Brislawn, J.N. Bradeley, R.J. Onyshczak, T. Hopper, “The FBI compression standerd for digitization fingerprint image”, Proc. SPIE, Vol. 2847, Denver, Aug. 1996
[3]
[4] Central finger printbureau
[5] Fingerprint – Search and Match System /Algorithm
[6] Online-fingerprint verification using direct minuatiae Extraction – in-gu Bae at al, Dept of Computer Engineering , Kyungpook National university, Taegum Korea 702-701
[1]Patents are pending on the bSQ and P-tree technology. This work is partially supported by GSA Grant ACT#=96130308.