IP 08 · How many coefficients can you throw away?
IntermediateIP 07 · Wavelet and Other Image TransformsImage lab
Description
Transform a real photo with an 8 × 8 block DCT or a Haar wavelet, round every coefficient to a coarse step, and see where the lost information shows up.
Try this: Set the DCT step to 0.6 and look at the sky in the zoom box. Then switch to Haar at the same step: does the staircase go away, and which transform keeps fewer nonzero coefficients at about the same PSNR? Finally move the zoom box to the grass: how much of the texture is left?
Hints
The chapter section that uses this lab:
Explanation
Answer the prediction first, or open the explanation when you are ready.
Show the explanation
A smooth patch is described almost completely by its average, so rounding costs little there. An edge or a texture spreads its energy over many coefficients, and many of them are smaller than half a step, so they become zero and the detail they carried is gone. At the default setting (DCT, step 0.2) the mean absolute error is 2.8 gray levels on the smoothest half of the pixels and 7.5 on the busiest half, about 2.7 times more. The smooth half is not error-free: rounding still shifts each block average a little, which is what draws the 8 × 8 seams at coarse steps.
Lab · IP 08 · How many coefficients can you throw away?
Loading image…
Try this: Set the DCT step to 0.6 and look at the sky in the zoom box. Then switch to Haar at the same step: does the staircase go away, and which transform keeps fewer nonzero coefficients at about the same PSNR? Finally move the zoom box to the grass: how much of the texture is left?
A real 256 × 256 version of the camera test image (a 2 × 2 average of skimage.data.camera), gray values in [0, 1]. Both transforms are orthonormal: an 8 × 8 block DCT (each block coded on its own) and a 5-level 2-D Haar wavelet transform. The quantizer is uniform: every coefficient c becomes round(c / step) × step, with the same step for all coefficients including the block averages, so a coefficient survives only if |c| is at least step / 2. This is simpler than the frequency-dependent table of JPEG in IP 08, so the pictures show what the transform and the rounding do on their own. "Nonzero" counts surviving coefficients. It is not a bit rate: no entropy coder is implemented, and the real cost also depends on which coefficients survive and how they are coded. PSNR has peak 1 and uses the decoder output before clipping. Because both transforms are orthonormal, the squared error in pixels equals the squared error in the coefficients: what the quantizer removes is exactly the error, and the decoder cannot bring it back, because many different images give the same quantized coefficients. A bottleneck autoencoder (ML 06A) loses detail in the same way, except that its basis is learned from data instead of fixed. The error image shows (reconstruction − original) × 10 around mid-gray. "Smoothest" and "busiest" halves are the pixels with the smaller and larger Sobel gradient of the original. Haar is the simplest wavelet and is piecewise constant, so it also produces blocks, of several sizes; smoother wavelets such as the one in IP 08’s wavelet comparison blur instead.
Method and image sources
- Rafael C. Gonzalez & Richard E. Woods, Digital Image Processing, 4th ed., Pearson, 2018 (compression, transforms)
- N. Ahmed, T. Natarajan and K. R. Rao, Discrete Cosine Transform, IEEE Transactions on Computers, C-23(1), 1974
- Alfred Haar, Zur Theorie der orthogonalen Funktionensysteme, Mathematische Annalen 69(3), 1910
- Gregory K. Wallace, The JPEG still picture compression standard, IEEE Transactions on Consumer Electronics 38(1), 1992
- scikit-image test images (skimage.data): camera is CC0 by Lav Varshney; coins is from the Brooklyn Museum collection, no known copyright restrictions; astronaut is a NASA photograph in the public domain