Parmakizi görüntülerinin model tabanlı yaklaşımla sıkıştırılması

Abstract

Parmakizi karşılaştırma yöntemi, parmakizlerinin şahıslan tekil olarak ayırt edici özelliklerinden dolayı, yıllardan beri kullanılan en yaygın ve en güvenilir tanıma yöntemlerinden biri olmuştur. Bilgi işlem makinalarının gelişmesi ile otomatik hale getirilen tanıma işleminin en büyük sorunlarından biri, sayısallaştırılan milyonlarca parmakizi görüntüsünün saklanması olmuştur. Bu ihtiyacın bir sonucu olarak, görüntü sıkıştırma alanında yapılan çalışmalar parmakizi görüntülerine uygulanmaya çalışılmıştır. Kayıpsız sıkıştırma yöntemlerinin sıkıştırma oranlan çok yetersiz kalırken, dönüşüme dayalı kayıplı sıkıştırma yöntemleri, görüntüde insan gözünün seçemeyeceği bazı ayrıntıları atmaya yönelik çalıştıkları için, tanıma amacı ile tasarlanmış yazılım ve donanımların başarımını büyük oranda düşürmektedirler. Bu tezde, parmakizi görüntülerinin sıkıştırılması için model tabanlı bir yaklaşım önerilmiş ve gerçeklenmiştir. Parmakizi görüntüleri, son derece düzenli bir yapıya sahiptirler. Bu yapı, çoğu yerde sırtların (mürekkepli bölgelerin) ve vadilerin (mürekkepsiz bölgelerin) birbirlerine koşut gittikleri bir şekildedir ve tanıma için bu yapının oluşturduğu öznitelikler kullanılır. Sadece bu öznitelikleri içeren sırt iskeletinin saklanması tanıma işlemi için yeterlidir. Tanımanın son aşamasında yine insan onayı gerektiği için, sıkıştırılan veriden tekrar kurulan parmakizi görüntülerinin özgün görüntülere benzemesi de, insan gözüne hitap etmesi açısından önemlidir. Bu yöntemi gerçeklemek amacıyla, parmakizi görüntülerinden sırt iskeletleri elde edilmiş, bu iskeletler kodlanarak sıkıştırılmış, sıkıştırılan veriden parmakizi görüntüsünü tekrar kurabilmek amacı ile iskeletler üzerindeki gri renk düzeyleri kodlanmış ve kurma aşamasında, seyrek veri üzerine zar ve ince levha modellerinden oluşan karma model yardımı ile yüzey kurularak özgün görüntüye çok yakın parmakizi görüntüleri elde edilmiştir. Elde edilen sonuçlar, bu modelin iyi bir sıkıştırma oranı ile tanıma aşamasında gerekli olacak nitelikleri kaybetmeden parmakizi görüntülerini sıkıştırdığını göstermektedir. Bu modelin diğer sıkıştırma yöntemlerine göre bir avantajı da sıkıştırılmış veri üzerinden tanıma işleminin yapılmasına olanak sağlamasıdır.

Fingerprints have been used as a unique identifier of individuals for a very long time. They are still considered as one of the most reliable means of distinguishing a man from his fellows. Although closely allied with the art of criminal apprehension, fingerprint recognition also provides a reliable method of personal identification for various other areas, including intelligence and security, banking and credit. Before the advent of automation, all the fingerprint identification was carried out visually and manually. Due to the increasing volume of fingerprints, there has been a correspondingly increasing demand for replacing visual and manual fingerprint identification with a fast and automated fingerprint identification system. The advent of digital computers and the development of computer based techniques such as image processing and pattern recognition have greatly contributed to this need. As a result of automating the fingerprint recognition process, millions of fingerprints had to be scanned and stored which were printed in inking on cards. One of the important problems of this digitization process is the need of storage for digitized fingerprint images which are 200KB - 300KB each. Advances in image compression, which is one of the most popular topics in image processing, made possible to solve this problem. Compression techniques have been developed to achieve compression ratios of between 2:1 and 10:1. These techniques include pixel coding, predictive coding and transform coding [1]. While the lossless compression techniques remain inefficient by means of compression ratio achieved, transform based coding techniques, such as JPEG [2], decreases the performance of automated fingerprint recognition sytems because high compression ratio is achieved by losing some details which can be neglected or interpolated by human eye but not recognition system. The most classical result of these compression schemes is the blocking effect in the decompressed image which leads to loss of some features in fingerprint images. However, fingerprint images constitute a particularly interesting image type due to the binary nature of their "ridge- valley" patterns that closely resemble lines and curves. ix Ridges are dark areas which are formed by pressing inked fingers to the card. Valleys are white areas between ridges which are less inked due to the natural form of fingers. The characteristics that enable a fingerprint to be uniquely identified are called "minutiae", which are derived from these lines and curves. They constitute ridge endings and ridge bifurcations. The singular points, namely the core and delta points, act as points of registration for comparing these point patterns. Further, the distance in terms of number of ridges between the core and delta points is used to reduce the search space in database. This observations lead to the conclusion that the "ridge skeleton" of a fingerprint image is sufficient to identify it uniquely. This special structure of fingerprint images can be better utilized by means of model based coding techniques [3] in order to achieve higher compression ratios without losing important features from the fingerprint. In this thesis, a model based fingerprint image compression scheme is presented which makes it possible to reconstruct a good replica of the original fingerprint image from relatively small amount of information, and to extract all features of the original image from the compressed one without any further processing. In this approach, compression is achieved by storing the ridge skeleton of fingerprint image effectively. Decompression is a reconstruction process which is based on minimization of an energy functional. The functional is a combination of energy functionals associated with a membrane and a thin plate [4,5]. A hybrid model controlled by two parameters is developed to generate surfaces with different properties, so that one can select appropriate values of parameters to obtain the original fingerprint image from sparse information. First of all grayscale image should be converted to a binary image to obtain the ridge skeleton. A fingerprint image is often noisy due to smudging, over-inking or excessive pressure while fingerprinting. Some preprocessing operations for noise elimination are necessary to minimize the effects of noise on the form of the skeleton and the rate of compression. An adaptive thresholding algorithm is used to avoid the effect of excessive pressure or over-inking. A window is slided over the image in which local variance and local luminance mean is calculated to estimate local threshold value for binarization. Slided window should be large enough to cover at least one portion of ridge and one portion of valley to estimate threshold successfully. It is observed that the sweat pores on ridges are imaged as white gaps which leads to corruption of ridges. This is an effect which reduces compression ratio as well as recognition performance. To avoid this effect, a weighted smoothing algorithm is applied to the image to fill these gaps prior to the adaptive thresholding. This binary image is then thinned to obtain a 8-connected skeleton of ridges with unit thickness. Ridge segments are extracted from binary image by a tracing algorithm. Each ridge segment is then encoded by using 2-bit differential chain codes. To accomplish this, ridge segments should be traced in a particular way so that directions of successive pixels in a ridge segment should be whether equal or differ 45 degrees at most. This enables to encode ridge segments with 2 bits per pixel. Through this method, a high compression ratio is achieved without loss of fingerprint features. To reconstruct a good replica of original fingerprint image, differences between grayscale values along ridges are collected and these differences are coded by variable length Huffman coding [6]. Generally, the pixel values on a ridge are similar. This makes possible that the substraction process along ridges gives very small values, nearby zero. Entropy coding gives better results with this difference values for which the probabilities are condensed in a small region of the whole range of values. Approximate locations of valleys are extracted from ridge skeleton by finding the mid curves between successive ridge curves and average grayscale value on each valley curve is calculated. Since the valley curves are extracted from the ridges, their locations do not have to be encoded. These data are used to create a sparse representation of fingerprint image which is used to reconstruct dense fingerprint image by minimizing an energy functional. Other necessary information to build sparse representation are beginning coordinates and initial directions of ridge segments. In development phase of this approach, it is seen that using Discrete Cosine Transform [6] gives better compression results than variable length Huffman coding to store the grayscale values along the ridges and valleys. Using DCT made also possible to store more precise pixel values of the valleys which increases the quality of the resulting fingerprint image. The decoding part of the scheme is based on a surface reconstruction using regularization theory. Regularization is a theoretical approach to solve ill-posed problems such as early vision problems. A problem is said to be well-posed if : - its solution exists. - the solution is unique. - the solution continuously depends on data d. In regularization, a unique solution is found by imposing constraints on the solution. These constraints are imposed as a variational principle such as a cost functional. Smoothness is an important constraint that is used in surface reconstruction. In this case, the missing data can be found by imposing the smoothness constraint, i.e., the solution should be smooth over the data. Using regularization theory, the reconstructed surface is obtained by finding the function /that minimizes the hybrid energy fuctional associated with membrane and thin plate [4,5]. £*') = JJo pa-^.^i-x)^;,/;)^^^/^/;)] dxdy M XI d is the sparse data built by decoding phase. Differential chain codes are decoded and the coordinates of every pixel on ridge skeleton are calculated. The valley skeleton is built by using the same algorithm used in the coding part. After obtaining locations of both ridge and valley skeletons, grayscale values are decoded and assigned to ridge segments. Given this sparse data d(x,y) containing grayscale values on ridges and valleys, the fingerprint image f(x,y) can be obtained by minimizing (1). In this functional, D term is a measure of closeness to the sparse data d and S term is the measure of smoothness. The compromise between these two terms is controlled by a real-valued regularization parameter X where X > 0. t e [0,1] is the real-valued continuity control parameter which controls the association of smoothness term to membrane or thin plate. By sweeping these two parameters İn their specified range, one can generate the Xr-space representation of the image. The properties of this space İs studied in detail in [5]. Two parameter values which produce the best approximation to the original fingerprint image are determined and then encoded. /?is the sparseness parameter which indicates whether data exists at the specified point. Minimization of (1) with respect to /means covering the sparse data d with a hybrid surface. Using the finite difference method, this functional can be written as £» = X l{p Jw,Wj2+4(i-*)M,+tPj} (2) where M d = (uij-Ui-ij) +(uij~Ui,j-i) <2a) and Pd= (ui+\,j-2uij+Ui-\,j) + (ui,j+\-2uij+Ui,j-i) @b) +2((w/,y + i-«/-i,y+i)"("ij-"/-u)) The condition for u desired to be minimum is that 3 Utj = 0,Vi (3) Energy £ is a quadratic function of u. As a result, this is a system of linear simultaneous equations and E is convex which means that there is one and only one solution. There are numerous ways to solve such an equation, most of which involve successive adjustments of the % to reduce E, until it can be reduced no further. The worst way to achieve that is simply to give small changes to each of the Uy in turn, and to accept changes which reduce E. It does work but will be inefficient. xu A better solution is to use the gradient dE/d utJ as a guide how % should be changed, in order to reduce E faster. To solve (3) for u iteratively, the Successive Over- relaxation (SOR) method is used : where co is the relaxation parameter and a e (0,2). T is a constant carefully chosen to ensure convergence for any ca e (0,2). n denotes the iteration number in increasing order. The iterations proceed until the difference between succesive solutions are negligible, i.e., when the condition M(»+i)_M<») is satisfied.