|
Academic Open Internet Journal |
Volume 16, 2005 |
Fingerprint Compression using wavelet based Contourlet Transform
1Sudhakar.R, 2Jayaraman.S, 3Karthiga.R
1 Lecturer, Dept of ECE, PSG College of Technology, Coimbatore 641 004, Tamilnadu, India.
2 Professor & Head, Dept of ECE, PSG College of Technology, Coimbatore 641 004,Tamilnadu, India.
3PG Student, Dept of ECE, PSG College of Technology, Coimbatore 641 004, Tamilnadu, India.
{1sudha_radha2000@yahoo.co.in, 2jayaramathreya@yahoo.com, 3karthigaragupathy@yahoo.com }
Abstract: Large volumes of fingerprints are collected and stored every day in a wide range of applications, including forensics, access control etc., It is evident from the database of Federal Bureau of Investigation (FBI) which contains more than 70 million finger prints Compression is the process of representing information in a compact form so as to reduce the bit rate for transmission or storage while maintaining acceptable fidelity or data quality. Due to the increasing traffic caused by multimedia information and digitized form of representation of images; image compression has become a necessity. New algorithms for image compression based on wavelets result in high compression ratios compared to other compression techniques. It is by now a well-established fact that the usual two-dimensional tensor product wavelet bases are not optimal for representing images consisting of different regions of smoothly varying grey-values, separated by smooth boundaries. This issue is addressed by the directional transforms, such as contourlets or curvelets, which have the property of preserving edges.
The paper focuses mainly on a modified form of Contourlet Transform called WBCT (Wavelet Based Contourlet Transform). An elaborated repositioning algorithm for the WBCT coefficients is developed in such a way that a similar spatial orientation trees as the ones used for scanning the wavelet coefficients, can be used. The results and discussions show this efficient coding of this Algorithm
Keywords: Image compression, wavelet transforms, directional transforms, PDFB, Contourlets, WBCT, SPIHT
1. INTRODUCTION
Finger Prints are the ridge and furrow patterns on the tip of the finger and are used for personal identification of the people. An automatic recognition of people based on fingerprints requires that the input fingerprint be matched with a large number of finger prints. Due to large volume of data in a database consumes more amount of memory. Hence an effective method should be adopted to utilize the memory effectively by storing the Finger prints in a compressed format Image compression is now essential for applications such as transmission and storage in data bases. In many different fields, digitized images are replacing conventional analog images as photograph or x-rays. The volume of data required to describe such images greatly slow transmission and makes storage prohibitively costly. The information contained in images must, therefore, be compressed by extracting only visible elements, which are then encode. The quantity of data involved is thus reduced substantially. The fundamental goal of image compression is to reduce the bit rate for transmission or storage while maintaining an acceptable fidelity or image quality.
The underlying idea of any compression scheme is to remove the correlation present in the data. Correlated data is characterized by the fact that one can, given one part of the data, fill in the missing part. The paper is organized as follows, section 2 deals with Motivation for transform Coding section 3 deals with Motivation for Directional Transforms section 4 deals with Contourlet Transform section 5 deals with Wavelet based Contourlet Transform section 6 deals with Results and Discussion section 7 deals with Discussion and section 8 deals with references.
2. MOTIVATION FOR TRANSFORM CODING
Compression can be achieved by transforming the data, projecting it on a basis of functions, and then encoding this transform. To avoid redundancy, which hinders compression, the transform must be at least biorthogonal and in order to save CPU time, the corresponding algorithm must be fast. The two-dimensional wavelet transform satisfies each of these conditions.
With newer techniques, like wavelets, a compression rate of up to 1:300 is achievable. Most lossy compression techniques are based on two-dimensional transforms, followed by quantization and encoding stages. The loss of information is introduced by the quantization stage which intentionally rejects less relevant parts of the image information. Specially adapted techniques which achieve high compression rates exist for artificial images. Wavelet compression allows the integration of various compression techniques into one algorithm.
Wavelets are being used in a number of different applications. The practical implementation of wavelet compression schemes is very similar to that of sub band coding schemes. As in the case of sub band coding, the signal is decomposed using filter banks. In a discrete wavelet transform, an image can be analyzed by passing it through an analysis filter bank followed by a decimation operation. When a signal passes through these filters, it is split into two bands. The low pass filter, which corresponds to an averaging operation, extracts the coarse information of the signal. The high pass filter, which corresponds to a differencing operation, extracts the detail information of the signal. The output of the filtering operations is then decimated by two.
A two-dimensional transform can be accomplished by performing two separate one-dimensional transforms. First, the image is filtered along the x-dimension using low pass and high pass analysis filters and decimated by two. Because of decimation, the total size of the transformed image is same as the original image. Then, it is followed by filtering the sub-image along the y-dimension and decimated by two. Finally, the image has been split into four bands denoted by LL, HL, LH, and HH, after one level of decomposition. The LL band is again subject to the same procedure. This process of filtering the image is called PYRAMIDAL DECOMPOSITION OF IMAGE.
 |
Fig. 1 Three level octave-band decomposition of Saturn image
The reconstruction of the image can be carried out by the following procedure. First, the data is up sampled by a factor of two on all the four sub bands at the coarsest scale and filter the sub bands in each dimension. Then the four filtered sub bands are summed to reach the low-low sub band at the next finer scale. This process is repeated until the image is fully reconstructed.
3. MOTIVATION FOR DIRECTIONAL TRANSFORMS
Sparse signal expansion lies at the foundation of many signal processing tasks, including compression, filtering, and feature extraction. We are interested in the construction of sparse expansions for two-dimensional signals which are smooth away from discontinuities across smooth curves. Such signals resemble natural images where discontinuities are generated by edges – referred to points in the image with sharp contrast in the intensity, whereas edges are often gathered along smooth contours that are created by typically smooth boundaries of physical objects. For one-dimensional piecewise smooth signals, wavelets provide the right tool. However, in 2-D the commonly used separable wavelets obtained by a tensor-product of 1-D wavelets are only
good at capturing the discontinuities at edge points, but do not see the smoothness along contours. Thus, more powerful schemes are needed in higher dimensions.
To see how one can improve the 2-D separable wavelet transform for representing images with smooth contours, consider the following scenario. Imagine that there are two painters, one with a “wavelet”-style and the other with a new style, both wishing to paint a natural scene. Both painters apply a refinement technique to increase resolution from coarse to fine. Here, efficiency is measured by how quickly, that is with how few brush strokes, one can faithfully reproduce the scene. Consider the situation when a smooth contour is being painted. Because 2-D wavelets are constructed from tensor products of 1-D wavelets, the “wavelet”-style painter is limited to using square-shaped brush strokes along the contour, using different sizes corresponding to the multiresolution structure of wavelets. As the resolution becomes finer, the limitation of the wavelet-style painter is that he needs to use many fine “dots” to capture the contour. The new style painter, on the other hand, explores effectively the smoothness of the contour by making brush strokes with different elongated shapes and in a variety of directions following the contour.
It is known from physiological studies [1] that the receptive fields in the visual cortex are characterized as being localized, oriented and band pass. Recently, several studies to identify the sparse components of natural image patches of small sizes. Strikingly, these sparse components resemble closely the aforementioned characteristics of the visual cortex. This result supports the hypothesis that the human visual system has been tuned so as to capture the essential information of a natural scene using a least number of visual active cells. More importantly, this result suggests that for a computational image representation to be efficient, it should be based on a local, directional, and multireslution expansion. To capture smooth contours in images, the representation should contain basis functions
with variety of shapes, in particular with different aspect ratios. This is the anisotropy property. A major challenge in capturing geometry and directionality in images comes from the discrete nature of the data: the input is typically sampled images defined on rectangular grids. Because of pixelization, the notion of smooth contours on sampled images is not obvious. For these reasons, unlike other transforms that were initially developed in the continuous-domain and then discretized for sampled data, the new approach starts with a discrete-domain construction and then investigate its convergence to an expansion in the continuous-domain. This construction results in a flexible multiresolution, local, and directional image expansion using contour segments, and thus it is named the contourlet transform [2], [4], [5].
To sum up, in order to provide sparse expansions for piecewise smooth images with smooth contours, in addition to localization and multiresolution features, new 2-D schemes should contain basis functions with elongated shapes with different aspect rations and oriented at variety of directions, as in the contourlet transform.
4. CONTOURLET TRANSFORM
The grouping of wavelet coefficients suggests that one can obtain a sparse image expansion by first applying a multiscale transform and then applying a local directional transform to gather the nearby basis functions at the same scale into linear structures. In essence, first a wavelet-like transform is used for edge (points) detection, and then a local directional transform for contour segments detection. With this insight, one can construct a double filter bank structure (Fig. 2(a)) in which at first the Laplacian pyramid (LP) [10] is used to capture the point discontinuities, and followed by a directional filter bank (DFB) [10] to link point discontinuities into linear structures. The overall result is an image expansion with basis images as contour segments, and thus it is named the contourlet transform. The combination of this double filter bank is named pyramidal directional filter bank (PDFB).
Fig 2. (a) shows the block diagram of a PDFB. First a standard multiscale decomposition into octave bands is computed, where the low pass channel is sub-sampled while the high pass is not. Then a directional decomposition with a DFB is applied to each high pass channel. Fig 2. (b) shows the support shapes for contourlets implemented by a PDFB that satisfies the anisotropy scaling relation. From the upper line to the lower line, the scale is reduced by four while the number of directions is doubled.
In general, the contourlet construction allows for any number of DFB decomposition levels lj to be applied at each LP level j. For the contourlet transform to satisfy the anisotropy scaling relation, one simply
 |
Fig 2 (a) Block Diagram of a PDFB (b) Supports for Contourlets
needs to impose that in the PDFB, the number of directions is doubled at every other finer scale of the pyramid. Fig. 2 (b) graphically depicts the supports of the basis functions generated by such a PDFB. As can be seen from the two shown pyramidal levels, the support size of the LP is reduced by four times while the number of directions of the DFB is doubled. Combine these two steps, the support size of the PDFB basis functions are changed from one level to next in accordance with the curve scaling relation. In this contourlet scheme, each generation doubles the spatial resolution as well as the angular resolution.
The PDFB provides a frame expansion for images with frame elements like contour segments, and thus is also called the contourlet transform. The contourlet frame has small redundancy, inherent due to the LP, which is at most 4/3. Hence, it may not be the optimum choice for image coding applications. Recently, some approaches have been attempted to introduce non-redundant image transforms based on DFB with the capability of both radial and angular decomposition.
5. WAVELET BASED CONTOURLET TRANSFORM
The Wavelet-Based Contourlet Transform (WBCT) is a new non-redundant image transform, with a construction similar to the contourlet transform. The WBCT achieves both radial and angular decomposition to an arbitrary extent and obeys the anisotropy scaling law of width= length 2 [1]. Compared to the DFB-based non-redundant transforms, the WBCT can easily be realized by applying DFB on the wavelet co-efficients of an image.
Similar to the contourlet transform, the WBCT consists of two filter bank stages. The first stage provides sub band decomposition, which in the case of the WBCT is a wavelet transform, in contrast to the Laplacian pyramid used in contourlets. The second stage of the WBCT is a directional filter bank (DFB), which provides angular decomposition . The first stage is realized by separable filter banks, while we implement the second stage using non-separable filter banks. For the DFB stage, we employ the iterated tree-structured filter banks using fan filters [11][3][4]. For the first two levels, it is sufficient to use a simple quincunx filter bank. For higher levels of the wavelet decomposition, we use another building block, which is resampling followed by the quincunx filter bank. At each level (j) in the wavelet transform, we obtain the traditional three high pass bands corresponding to the LH, HL, and HH bands. We apply DFB with the same number of directions to each band in a given level (j). Starting from the desired maximum number of directions N D= 2L on the finest level of the wavelet transform J, we decrease the number of directions at every other dyadic scale when we proceed through the coarser levels ( j < J ). This way, we could achieve the anisotropy scaling law. Fig. 3 illustrates a schematic plot of the WBCT using 3 wavelet levels and L=3 directional levels.
 |
Fig 3. A Schematic plot of WBCT
It should be noted that, the capability of a transform to efficiently approximating an image, does not automatically result in an efficient coder . The other important issue that should be taken into account is how one codes the positions of the significant coefficients (used in the non-linear approximation) efficiently. In [13], Shapiro pioneered the notion of zero-trees for coding the positions of significant wavelet coefficients. Following his work, Said and Pearlman [12] developed the SPIHT algorithm for wavelet coding of images and could achieve significant improvement over the EZW coder [13]. In the tree-based wavelet coding algorithms such as EZW and SPIHT, considering a threshold T, if a wavelet coefficient, a( i,j) is insignificant, i.e. , a(i,j)< T , due to a self-similarity amongst the wavelet coefficients in different sub bands, it is likely that its descendents at the finer wavelet scales are insignificant. A similar observation can be made about the proposed WBCT coefficients; however, the definition of the “descendants” of a WBCT coefficient needs to be modified. Therefore, using this presumption, and similar to the original SPIHT algorithm, we can assign a non-significant WBCT coefficient to the list of insignificant set (LIS) and perform the same set partitioning algorithm as done within the SPIHT algorithm for wavelet coding. Hence, following the same approach of SPIHT, we create three sets of LIP (list of insignificant pixels), LIS, and LSP (list of significant pixels) and perform set partitioning and refining the significant pixels of the WBCT coefficients during coding. Similar to the spatial orientation tree (or zero-tree) concept of wavelet coefficients in which we have a parent-child relationship along wavelet scales, one can find parent-child dependencies in other sub band systems. In the case of the contourlet transform, one can assume two different parent child relationships depending on the number of directional decompositions in the contourlet sub bands [13]. If the two successive scales in which the parent and children lie have the same number of directional decompositions, then the parent and children would lie in the corresponding directional sub bands; however if the scale in which the children lie has twice as many directional sub bands as the scale in which the parent lies, the four children will be in two adjacent directional sub bands. These two directional sub bands correspond to the directional decomposition of the directional sub band in which the parent is located. Due to the similarities of the WBCT to the contourlet transform, for each LH, HL, and HH sub band we can assume the same parent-child relationships as illustrated in Fig. 4.
 |
Fig. 4. Two possible parent-child relationships in the WBCT (a) When the number of directional sub bands are the same at the two wavelet scales. Here we have 4directions at each wavelet sub band. (b) When the number of directional sub bands in the finer wavelet scale (8) is twice as many as those in the coarser wavelet scale (4).
Wavelet sub bands (or radial sub bands in the WBCT) are separated by the solid lines and directional sub bands separated by the dotted lines. Therefore, due to differences in parent-children dependencies between the WBCT and the wavelet transform, before applying the SPIHT algorithm, we reposition the transform coefficients in the WBCT in such a way to be able to use a similar SPIHT algorithm
Fig. 5 shows an example of repositioning a radial sub band in the WBCT having 8 directional decompositions. This example assumes that the coarser sub band has 4 directional decompositions. In the left image of Fig.5 , we have 8 directional sub bands (separated by dashed lines).
 |
Fig. 5. An example of repositioning a radial sub band in the WBCT having 8 directional sub bands assuming its coarser sub band is at first level and has 4 directional decompositions
Each two adjacent horizontal sub bands (upper half sub bands) and each two adjacent vertical sub bands (lower half sub bands) are corresponding to a horizontal sub band and a vertical sub band in the coarser scale, respectively. So, if we reposition the columns of the horizontal directional sub bands and the rows of the vertical directional sub bands in a manner to set the children beside each other, we can benefit from using a similar tree-based wavelet coding algorithm for the WBCT coefficients. However, as we move forward along the scales, the repositioning algorithm becomes more complex and we have to interlace sets of 2, 4, or any higher number of columns (rows) of the horizontal (vertical) sub bands in order to maintain the descendent of a WBCT coefficient adjacent to each other similar to the wavelet coefficients. After reallocating the WBCT coefficients, the SPIHT is applied to it and it is called as CSPIHT (Contourlet SPIHT).
6. RESULTS AND DISCUSSIONS
We tested the proposed coding scheme as well as the original SPIHT coder on the following images, each having a size of 256 X 256: Fingerprint A and Fingerprint B Fig 6(a) shows the original Finger print A and Fig 7(a) shows the original Finger print B Fig 6(b) shows the reconstructed fingerprint A under Wavelet based SPIHT scheme for the decomposition level 6. Fig 6(c) shows the reconstructed fingerprint A under Contourlet based SPIHT scheme for the same decomposition level. Fig 7(b) shows the shows the reconstructed Fingerprint B under Wavelet based SPIHT scheme for the decomposition level 6. Fig 7(c) shows the reconstructed fingerprint B under Contourlet based SPIHT scheme for the same decomposition level.
The compression ratio and PSNR were found. The results are tabulated below in Tables I and II.
(a) |
(b) |
(c) |
Fig.6 (a) Original Fingerprint A (b) Reconstructed Fingerprint A under WSPIHT scheme with level of Decomposition is 6 (c) Reconstructed Fingerprint A under CSPIHT scheme with level of Decomposition is 6
 |
(a) (b) (c)
Fig.7(a) Original Fingerprint B (b) Reconstructed Fingerprint B under WSPIHT scheme with level of Decomposition is 6 (c) Reconstructed Fingerprint B under CSPIHT scheme with level of Decomposition is 6
It is easily seen that the PSNR values for Countourlet based SPIHT(CSPIHT) is approximately 2dB more than the value from Wavelet based SPIHT (WSPIHT)scheme. This implies that the user may get the extra quality in CSPIHT scheme than WSPIHT scheme under the same value of Compression Ratio(CR).This shown in Fig .10 and Fig .11 for both fingerprints. The Fig.8 and Fig. 9 reflects the same. This is due to the fact that the CSPIHT scheme better captures edges in the images than WSPIHT scheme. The main reason for the above statement is due the directional based basis function available in the Countourlet transform. The experiments indicated that the proposed scheme is superior in preserving textures and details in the coded images. This clearly shows the capability of the proposed coder for images consisting of mainly textures and oscillatory patterns,in which Fingerprints are not exceptional.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Table I: PSNR & CR for wavelet based SPIHT
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Table II: PSNR & CR for CSPIHT
Fig.8 Comparison PSNR values for Fingerprint A
Fig.9 Comparison PSNR values for Fingerprint B
Fig.10 Comparison PSNR values for Fingerprint A under common CR
Fig.11Comparison PSNR values for Fingerprint B under common CR
7. CONCLUSION
In this work, we constructed a discrete transform that can offer a sparse expansion for typical images having smooth contours. Using recent results from harmonic analysis and vision, we first identified two key features of a new image representation that improves over the separable 2-D wavelet transform, namely directionality and anisotropy. Based on this observation, we developed a new filter bank structure, the contourlet filter bank, that can provide a flexible multiscale and directional decomposition for images. The developed discrete filter bank has an associated continuous-domain contourlet expansion similar to filter bank iterations and the associated wavelet constructions. This connection was made precise via a newly defined directional multiresolution analysis that provides successive refinements at both spatial and directional resolution. With parabolic scaling and sufficient directional vanishing moments, the contourlet expansion is shown to achieve the optimal approximation rate for piecewise C2 smooth images with C2 smooth contours. Experiments with real images indicate the potential of contourlets in several image processing applications
8. REFERENCES
[1] D. H. Hubel and T. N. Wiesel, “Receptive fields, binocular interaction and functional architecture in the
cat’s visual cortex,” Journal of Physiology, no. 160, pp. 106–154, 1962.
[2] E. J. Candes and D. L. Donoho, “Curvelets – a suprizingly effective nonadaptive representation for objects with edges,” in Curve and Surface Fitting, a. Cohen, C. Rabut, and L. L. Schumaker Eds., Saint-
Malo, 1999, Vanderbuilt Univ. Press.
[3] A. Cohen, I. Daubechies, O. Guleryuz, and M. Orchard, “On the Importance of Combining Wavelet-Based Non-linear Approximation with Coding Strategies,” in IEEE trans. Information Theory, vol. 48,no. 7, pp. 1895-1921, Jul. 2002.
[4] M. N. Do, Directional multiresolution image representations. Ph.D. thesis, EPFL, Lausanne, Switzerland, Dec. 2001.
[5] M. N. Do and M. Vetterli, “Contourlets,” in Beyond Wavelets, J.Stoeckler and G. V. Welland, Eds. Academic Press, New York, 2003.
[6] R. Eslami and H. Radha, “On low bit-rate coding using the contourlet transform,” to be published in Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, USA, Nov. 2003.
[7] R. Eslami and H. Radha, “The contourlet transform for image denoising using cycle spinning,” to be published in Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, USA, Nov. 2003.
[8] P. Hong and M. J. T. Smith, “An octave-band family of non-redundant directional filter banks,” in IEEE proc. ICASSP, vol. 2, pp. 1165-1168, 2002.
[9] Image Communication Lab., UCLA, Wavelet Image
[10] S. Park, M. J. T. Smith, and R. M. Mersereau, “A new directional filter bank for image analysis and classification,” in IEEE proc. ICASSP, vol. 3, pp. 1417-1420, Mar. 1999
[11] D. D.-Y. Po and M. N. Do, “Directional multiscale modeling of images using the contourlet transform,” submitted to IEEE trans. on Image Processing, 2003.
[12] A. Said and W. A. Pearlman, “A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees,” IEEE trans. On Circuits and Systems for Video Technology, vol. 6, pp. 243-250, June 1996.
[13] J.M. Shapiro, “Embedded image coding using zerotrees of wavelet coefficients,” IEEE trans. on Signal Processing (Special Issue, Wavelets and Signal Processing), vol. 41, pp. 3445-3462, Dec. 1993.
Technical College - Bourgas,
All rights reserved,
© March, 2000