1、Fingerprint Recognition SystemAbstractFingerprint recognition system consist of image preprocessing, features extraction and features matching that runs effectively and accurately on personal computer. The image preprocessing includes noise removal, histogram equalization, global thresholding and ri

2、dgeline thinning which are necessary for the features extraction. Extracted features are then stored in a file for fingerprint matching. Matching algorithm presented here is a simple, fast and accurate. Experimental results for matching are accurate, reliable and fast for implementation using a pers

3、onal computer and fingerprint reader. The proposed fingerprint algorithm can provide an effective way of automated identification and can be extended to other security or identification applications. Further the algorithm can be implanted on a FPGA platform for a real time personal automated identif

4、ication system.Keywords:biometric recognition;histogram equalization;ridge thinning;ridge ending;ridge bifurcation.1. INTRODUCTIONFingerprint recognition systems are termed under the umbrella of biometrics. Biometric recognition refers to the distinctive physiological (e.g. fingerprint, face, iris,

5、retina) and behavioral(e.g. signature, gait) characteristics, called biometric identifiers or simply biometrics, for automatically recognizing individuals. In 1893, it was discovered that no two individuals have same fingerprints. After this discovery fingerprints were used in criminal identificatio

6、n and till now fingerprints are extensively used in various identification applications in various fields of life. Fingerprints are graphical flow-like ridges present on human fingers. They are fully formed at about seventh month of fetus development and fingerprint configuration do not change throu

7、ghoutthe life except due to accidents such as bruises or cut on fingertips.Because of immutability and uniqueness, the use of fingerprints for identification has always been of great interest to pattern recognition researchers and law enforcement agencies. Conventionally, fingerprint recognition has

8、 been conducted via either statistical or syntactic approaches. In statistical approach a fingerprints features are extracted and stored in an n-dimensional feature vector and decision making process is determined by some similarity measures. In syntactic approach, a pattern is represented as a stri

9、ng, tree 1, or graph 2 of fingerprint features or pattern primitives and their relations. The decision making process is then simply a syntax analysis or parsing process.This paper suggests the statistical approach. Experimental results prove the effectiveness of this method on a computer platform,

10、hence making it suitable for security applications with a relatively small database. The preprocessing of fingerprints is carried out using modified basic filtering methods which are substantially good enough for the purpose of our applications with reasonable computational time. Block diagram for t

11、he complete process is shown in Figure.1.2. IMAGE PREPROCESSINGFor the proper and true extraction of minutiae, image quality is improved and image preprocessing is necessary for the features extraction because we cannot extract the required points from the original image. First of all, any sort of n

12、oise present in the image is removed. Order statistics filters are used to remove the type of noise which occurs normally at image acquisition. Afterwards the following image preprocessing techniques are applied to enhance the fingerprint images for matching.2.1 Histogram EqualizationThis method is

13、used where the unwanted part of the image is made lighter in intensity so as toemphasize the desired the desired part. Figure 2(a) shows the original image and Figure 2(b) histogram equalization in which the discontinuities in the small areas are removed. For the histogram equalization, let the inpu

14、t and the output level for an arbitrary pixel be i and l, respectively. Then the accumulation of histogram from 0 to i ( 0 i 255,0 k 255) is given bywhere H(k) is the number of pixel with gray level k, i.e. histogram of an area, and C(i) is alsoknown as cumulative frequency. 2.2 Dynamic Thresholding

15、Basic purpose of thresholding is to extract the required object form the background. Thresholding is simply the mapping of all data points having gray level more that average gray level. The results of thresholding are shown in Figure 3.2.3 Ridgeline ThinningBefore the features can be extracted, the

16、 fingerprints have to be thinned or skeletonised so that all ridges are one pixel thick. When a pixel is decided as a boundary pixel, it is deleted directly form the image 3-5 or flagged and not deleted until the entire image been scanned 6-7. There are deficiencies in both cases. In the former, del

17、etion of each boundary pixel will change the object in the image and hence affect the object symmetrically. To overcome this problem, some thinning algorithms use several passes in one thinning iteration. Each pass is an operation to remove boundary pixels from a given direction. Pavlidis 8 and Fieg

18、in and Ben-Yosef 9 have developed effective algorithms using this method. However, both the time complexity and memory requirement will increase. In the latter, as the pixels are only flagged, the state of the bitmap at the end of the last iteration will used when deciding which pixel to delete. How

19、ever, if this flag map is not used to decide whether a current pixel is to be deleted, the information generated from processing the previous pixels in current iteration will be lost. In certain situations the final skeleton may be badly distorted. For example, a line with two pixels may be complete

20、ly deleted. Recently, Zhou, Quek and Ng 10 have proposed an algorithm that solves the problem described earlier and is found to perform satisfactorily while providing a reasonable computational time. The thinning effect is illustrated in Figure 43. FEATURES EXTRACTIONThe two basic features extracted

21、 from the image are ridge endings and ridge bifurcation. Forfingerprint images used in automated identification, ridge endings and bifurcation are referred to as minutiae. To determine the location of these features in the fingerprint image, a 3x3 window mask is used (Figure 5). M is the detected po

22、int and X1 X8 are its neighboring points in a clockwise direction. If Xn is a black pixel, then its response R (n) will be 1 or otherwise it will be 0. If M is an ending, the response of the matrix will bewhere R(9)=R(1). For M to be a bifurcation,for example, if a bifurcation is encountered during

23、extraction, mask will contain the pixelinformation such as R(1) = R(3)= R(4) = R(6) = R(7) = 0, R(2) = R(5) = R(8) = R(9) = 1, andFor all the minutiae detected in the interpolated thinned image, the coordinates and their minutiae type is save as feature file. At the end of feature extraction, a feat

24、ure record of the fingerprint is formed.4. MATCHINGFingerprint matching is the central part of this paper. The proposed technique is based on structural model of fingerprints 11. One of the major breakthroughs of this method is its ability to mach fingerprints that are shifted, rotated and stretched

25、. This is achieved by a different matching approach. As it is clear that this algorithm matches the two fingerprint images captured at different time. This matching is based on the minutiae identification and minutiae type matching. Matching procedure is complex due to two main reasons;1) The minuti

26、ae of the fingerprint captured may have different coordinates2) The shape of the fingerprint captured at different time may be different due to stretching.An automated fingerprint identification system that is robust must have following criteria:1) Size of features file must be small2) Algorithm mus

27、t be fast and robust3) Algorithm must be rotationally invariant4) Algorithm must be relatively stretch invariantTo achieve these criteria, the structural matching method described by Hrechak and McHugh 11 is adopted as the basis of our recognition algorithm, with changes made to the algorithm, to pr

28、ovide more reliable and improving overall matching speed. This matching represents the local identification approach, in which local identified features, their type and orientation is saved in features file, is correlated with the other images extracted features file. The model is shown in Figure 6.

29、For each extracted features on the fingerprint, a neighborhood of some specified radius R about the central feature is defined and then Euclidean distance and relative angles between the central point and the other point is noted with the points type. Since the distance among the pointremains the sa

30、me throughout the life. So this technique works well for the rotated and shifted images.5. CONCLUSIONA fingerprint recognition algorithm that is fast, accurate and reliable has been successfully implemented. This algorithm can be modified, introducing the ridgeline count, and then could beused in on

31、line and real time automated identification and recognition system.REFERENCES1 MOAYER, B., and FU, K.S.: A tree system approach for fingerprint pattern recognition, IEEE Trans., 1986,PAMT-8, (3), pp. 376-3872 ISENOR, D.K., and ZAKY, S.G.: Fingerprint identification using graph matching, Pattern Reco

32、gnit., 1986,19, (2) pp. 113-1223 TAMURA, H.: A comparison of line thinning algorithms from digital geometry viewpoint. Proceedings of fourth international joint conference on Pattern Recognition, Kyoto, Nov. 1978, pp. 715-7194 HILDITCH, C.J.: Linear skeleton from square cupboards, Machine Intel., 19

33、69, 4, pp.403-4205 NACCACHE, N.J., and SHINCHAL, R.: An investigation into the skeletonization approach of Hilditch,Pattern Recognit., 1984, 17, (3), pp. 279-2846 JANG, B.K., and CHIN, P.T.: Analysis of thinning algorithms using mathematical morphology, IEEE Trans.,Pattern Anal. Machine Intel., 1990

34、, 12, (6), pp. 541-5517 XU, W., and WANG, C.: CGT: a fast thinning algorithm implemented on sequential computer, IEEE Trans.,1987, SMC-17, (5), pp. 847-8518 PAVLIDIS, T.: Algorithm for graphical and image processing, Comput. Graph. Image Process., 1982, 20,pp133-1579 FEIGIN, G., and BEN YOSEF, N.: L

35、ine thinning algorithm, Proc. SPIE Int. Soc. Opt. Eng., 1984, 397, pp.108-11210ZHOU, R.W., QUEK, C., and NG, G.S.: Novel single-pass thinning algorithm, Pattern Recognit. Lett., 1995,16, (12), pp.1267-127511HRECHAK, A.K., and MCHUGH, J.A.: Automated fingerprint recognition using structural matching,

36、Pattern Recognit., 1990, 23, (8), pp. 893-90412GOUNZALEZ, R.C., and WOOD, R.E.: Digital image processing (Pearson Education, 2002) 指紋識別系統(tǒng)摘要指紋識別系統(tǒng)包括圖像預(yù)處理、特征提取和在個人計(jì)算機(jī)上進(jìn)行有效、準(zhǔn)確地匹配的功能。圖像預(yù)處理包括去除噪聲、直方圖均衡、全局閾值和脊線細(xì)化這些必要的特征提取。提取的特征，然后存儲在指紋匹配的文件里。這里提出的匹配算法是一種簡單、快速、準(zhǔn)確的算法。匹配實(shí)驗(yàn)結(jié)果準(zhǔn)確、可靠、快速，使用一臺個人電腦和指紋識別器實(shí)施。提出的指紋算法可

37、以提供一個有效的自動識別方式，并可以擴(kuò)展到其他安全或者識別應(yīng)用。該算法可以進(jìn)一步植入一個FPGA平臺上的個人實(shí)時自動識別系統(tǒng)。關(guān)鍵詞：生物特征識別；直方圖均衡化；山脊細(xì)化；脊的結(jié)局；脊分岔1、引言指紋識別系統(tǒng)被稱為處在生物識別技術(shù)的保護(hù)傘下。生物識別是指獨(dú)特的生理（如指紋、人臉、虹膜、視網(wǎng)膜）和行為（如簽名、步態(tài)）特點(diǎn)，被稱為生物識別或簡單的生物識別技術(shù)，自動識別的個人。在1893年，它被發(fā)現(xiàn)，任何兩個人都不會有相同的指紋。在這個發(fā)現(xiàn)之后指紋被應(yīng)用在刑事鑒定中，直到現(xiàn)在指紋被廣泛應(yīng)用于各種智能識別應(yīng)用在生活的各個領(lǐng)域。指紋是人類手指上的圖形流的山脊。他們在胎兒發(fā)育和指紋配置的大約七個月就完全形

38、成，整個生命中都不會改變，除非由于事故，如瘀傷或指傷。由于不變性和唯一性，指紋識別應(yīng)用一直是模式識別研究人員和執(zhí)法機(jī)構(gòu)的極大興趣。傳統(tǒng)上，指紋識別已經(jīng)通過任何統(tǒng)計(jì)或句法的方法進(jìn)行。統(tǒng)計(jì)方法的指紋特征是提取并存儲在一個N維的特征向量和決策過程中由一些相似的措施決定。在句法方法，一個模式表示為一個字符串，樹1，或圖2的指紋特征或模式基元及其相互關(guān)系。然后決策過程就是簡單地句法分析或解析過程。本文提出的統(tǒng)計(jì)方法。計(jì)算機(jī)平臺上的實(shí)驗(yàn)結(jié)果證明該方法的有效性，因此適合安全應(yīng)用于一個相對嬌較小的數(shù)據(jù)庫。指紋的預(yù)處理進(jìn)行了修改基本的過濾方法，足夠合理的計(jì)算時間與我們的應(yīng)用程序的目的。完整的過程方框圖在圖1中表

39、示圖像捕捉圖像預(yù)處理特征提取匹配存儲特征點(diǎn)圖1 框圖2、圖像預(yù)處理為正確和真實(shí)的細(xì)節(jié)提取，圖像質(zhì)量得到改善，圖像預(yù)處理，特征提取是必要的，因?yàn)槲覀儾荒軓脑紙D像中提取所需的點(diǎn)。首先，任何類型的圖像中的噪聲目前被刪除。順序統(tǒng)計(jì)濾波器用于消除噪聲的類型，通常發(fā)生在圖像采集之后，下面的圖像預(yù)處理技術(shù)應(yīng)用于提高匹配的指紋圖像。2、1 直方圖均衡化使用這種方法使圖像不必要的部分強(qiáng)度輕，以便強(qiáng)調(diào)需要所需的部分。圖2（a）顯示原始圖像和圖2（b）顯示直方圖均衡化的圖像，其中不連續(xù)的小區(qū)域被刪除。直方圖均衡化，讓任意像素的輸入和輸出電平分別是i和I。然后從0到i（0 i 255,0 k 255）直方圖的累積由

40、 (1) 求得其中H(k)為k層灰色的像素?cái)?shù)，即一個區(qū)域的直方圖，C(i)也被成為累積概率。 圖2(a) 原始圖像 圖2(b) 直方圖均衡的圖像2、2 動態(tài)閾值閾值的基本目的是提出所需的對象窗體背景。閾值僅僅是灰色的水平，平均灰度水平的所有數(shù)據(jù)點(diǎn)的映射。閾值的結(jié)果如圖3所示。圖3 動態(tài)閾值結(jié)果2、3 山脊細(xì)化在特征可以被提取之前，指紋必須變薄或鏤空，所以，所有的山脊是一個像素厚。當(dāng)一個像素作為一個邊界像素決定，它直接刪除圖像3-5或標(biāo)記，但不會刪除，直到整個圖像被掃描6-7。在這兩種情況下是有缺陷的。在前者，每個邊界像素的缺失會改變圖像中的對象，因而影響對稱對象。為了克服這個問題，一些細(xì)化算法

41、使用幾個通行證在一個細(xì)化迭代里。每通是一個操作刪除從一個給定方向的邊界像素。Pavlidis 8 and Fiegin and Ben-Yosef 9已經(jīng)使用這種方法制定了有效的算法。然而，無論是時間復(fù)雜度和內(nèi)存需求將會增加。在后者，像素只有標(biāo)記，在最后一次迭代結(jié)束時的位圖的狀態(tài)將決定刪除哪一個像素時使用。但是，如果不使用這個標(biāo)志圖來決定是否要刪除當(dāng)前圖像，從以前的像素在當(dāng)前迭代處理產(chǎn)生的信息將丟失。在某些情況下，最終的骨架可能會被嚴(yán)重扭曲。例如，有兩個像素的線，可以完全刪除。最近，Zhou, Quek and Ng 10提出了一種算法，解決了前面所述的問題，并且圓滿的執(zhí)行，同時提供了一個合理

42、的計(jì)算時間。細(xì)化效果如圖4所示 a b 圖4 山脊細(xì)化a 細(xì)化前 b細(xì)化后3、特征提取從圖像中提取的兩個基本特征是脊末梢和脊分岔。對于自動識別所使用的指紋圖像，神經(jīng)末梢和分岔被稱為脊的特征點(diǎn)。為了確定這些特征點(diǎn)在指紋圖像的位置，使用了一個3x3的矩陣窗口(圖 5)。M是監(jiān)測點(diǎn)，X1 X8是在順時針方向的臨近點(diǎn)。如果Xn是一個黑色像素，那么與R (n)對應(yīng)的就是1，否則就是0。如果M是一個結(jié)尾，矩陣響應(yīng)為 （2）其中R(9)=R(1)。M是一個分支， （3）例如，如果在提取的過程中遇到了一個分支，掩碼將包含的像素信息如R(1) = R(3)= R(4) = R(6) = R(7) = 0, R(

43、2) = R(5) = R(8) = R(9) = 1,結(jié)果 插值細(xì)化圖像中檢測到的所有細(xì)節(jié)，坐標(biāo)和他們的特征點(diǎn)類型被保存為特征文件。在特征提取的最后，指紋特征記錄正在形成。X1X2X3X8MX4X7X6X5 圖5 3 x 3掩膜特征提取4、匹配指紋匹配時本文的核心內(nèi)容。提出的技術(shù)是基于指紋的結(jié)構(gòu)模型11。這種方法的重大突破之一是它對于移動、旋轉(zhuǎn)和伸展的指紋相匹配的能力。這是通過不同的匹配方法實(shí)現(xiàn)的。因?yàn)樗乔逦?，該算法匹配兩個在不同時間捕獲的指紋圖像。這種匹配是在特征點(diǎn)識別和特征點(diǎn)類型匹配的基礎(chǔ)上的。匹配程序是復(fù)雜的，由于兩個主要原因：1) 捕獲指紋的特征點(diǎn)可能有不同坐標(biāo)2) 在不同的時間

44、捕獲的指紋形狀由于伸展可能會不同強(qiáng)大的指紋自動識別系統(tǒng)必須具備下列條件：1) 特征文件的尺寸一定要小2) 算法必須快速和強(qiáng)大3) 算法必須是旋轉(zhuǎn)不變的4) 算法必須相對伸展不變?yōu)榱诉_(dá)到這些條件，由Hrechak 和McHugh 11描述的結(jié)構(gòu)匹配方法采用我們書別算法的基礎(chǔ)上，通過算法所做的更改，以提供更可靠，提高整體匹配速度。此匹配代表局部的識別方法，它們的類型和方位這些局部標(biāo)識的特征保存在特征文件，與其他圖像的特征文件有關(guān)。模型如圖6所示。 圖6 局部特征的結(jié)構(gòu)模型對于每個提取的指紋特征，臨近的一些特定的半徑為R的重要特征被定義，然后通過點(diǎn)的類型指出中央點(diǎn)和其他點(diǎn)之間的歐幾里得距離和相對角度。由于點(diǎn)之間的距離在整個生命期間保持不變。因此這項(xiàng)技術(shù)可以很好的用于轉(zhuǎn)移和旋轉(zhuǎn)的圖像。5、結(jié)論一個快速、準(zhǔn)確和可靠的指紋識別算法已經(jīng)成功實(shí)施。該算法可以修改，引入山脊計(jì)數(shù)，然后可以應(yīng)用于網(wǎng)上實(shí)時自動識別和識別系統(tǒng)。參考文獻(xiàn)1 MOAYER, B., and FU, K.S.: A tree system approach for fingerprint pattern