Main Content

2-D Wavelet Packet Analysis

In this section, we employ the Wavelet Packet 2-D tool to analyze and compress an image of a fingerprint. This is a real-world problem: the Federal Bureau of Investigation (FBI) maintains a large database of fingerprints — about 30 million sets of them. The cost of storing all this data runs to hundreds of millions of dollars.

“The FBI uses eight bits per pixel to define the shade of gray and stores 500 pixels per inch, which works out to about 700,000 pixels and 0.7 megabytes per finger to store finger prints in electronic form.” (Wickerhauser, see the reference [Wic94] p. 387, listed in References).

“The technique involves a 2-D DWT, uniform scalar quantization (a process that truncates, or quantizes, the precision of the floating-point DWT output) and Huffman entropy coding (i.e., encoding the quantized DWT output with a minimal number of bits).” (Brislawn, see the reference [Bris95] p. 1278, listed in References).

By turning to wavelets, the FBI has achieved a 15:1 compression ratio. In this application, wavelet compression is better than the more traditional JPEG compression, as it avoids small square artifacts and is particularly well suited to detect discontinuities (lines) in the fingerprint.

Note that the international standard JPEG 2000 will include the wavelets as a part of the compression and quantization process. This points out the present strength of the wavelets.

Starting the Wavelet Packet 2-D Tool

  1. From the MATLAB® prompt, type waveletAnalyzer. The Wavelet Analyzer appears.

    Click the Wavelet Packet 2-D menu item.

    Importing an Image

    At the MATLAB command prompt, type

    load detfingr;
    In the Wavelet Packet 2-D tool, select File > Import from Workspace > Import Image. When the Import from Workspace dialog box appears, select the X variable. Click OK to import the fingerprint image.

    Analyzing an Image

  2. Make the appropriate settings for the analysis. Select the haar wavelet, level 3, and entropy type shannon. Click the Analyze button.

    Note

    Many capabilities are available using the command area on the right of the Wavelet Packet 2-D window.

  3. Click the Best Tree button to compute the best tree before compressing the image.

Compressing an Image Using Wavelet Packets

  1. Click the Compress button to bring up the Wavelet Packet 2-D Compression window. Select the Bal. sparsity-norm (sqrt) option from the Select thresholding method menu.

    Notice that the default threshold (7.125) provides about 64% compression while retaining virtually all the energy of the original image. Depending on your criteria, it may be worthwhile experimenting with more aggressive thresholds to achieve a higher degree of compression. Recall that we are not doing any quantization of the image, merely setting specific coefficients to zero. This can be considered a precompression step in a broader compression system.

  2. Alter the threshold: type the number 30 in the text field opposite the threshold slider located on the right side of the Wavelet Packet 2-D Compression window. Then press the Enter key.

    Setting all wavelet packet coefficients whose value falls below 30 to zero yields much better results. Note that the new threshold achieves around 92% of zeros, while still retaining nearly 98% of the image energy.

  3. Click the Compress button to start the compression.

    You can see the result obtained by wavelet packet coefficients thresholding and image reconstruction. The visual recovery is correct, but not perfect. The compressed image, shown side by side with the original, shows some artifacts.

  4. Click the Close button located at the bottom of the Wavelet Packet 2-D Compression window. Update the synthesized image by clicking Yes when the dialog box appears.

Take this opportunity to try out your own compression strategy. Adjust the threshold value, the entropy function, and the wavelet, and see if you can obtain better results.

Hint

The bior6.8 wavelet is better suited to this analysis than is haar, and can lead to a better compression ratio. When a biorthogonal wavelet is used, then instead of “Retained energy” the information displayed is “Energy ratio.” For more information, see Compression Scores.

Before concluding this analysis, it is worth turning our attention to the “colored coefficients for terminal nodes plot” and considering the best tree decomposition for this image.

This plot is shown in the lower right side of the Wavelet Packet 2-D tool. The plot shows us which details have been decomposed and which have not. Larger squares represent details that have not been broken down to as many levels as smaller squares. Consider, for example, this level 2 decomposition pattern:

Looking at the pattern of small and large squares in the fingerprint analysis shows that the best tree algorithm has apparently singled out the diagonal details, often sparing these from further decomposition. Why is this?

If we consider the original image, we realize that much of its information is concentrated in the sharp edges that constitute the fingerprint's pattern. Looking at these edges, we see that they are predominantly oriented horizontally and vertically. This explains why the best tree algorithm has “chosen” not to decompose the diagonal details — they do not provide very much information.