Full search page →

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?

Predict first

You keep the default setting, where most coefficients are rounded to zero. Where in the picture will the reconstruction error be largest?

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?

Predict first

You keep the default setting, where most coefficients are rounded to zero. Where in the picture will the reconstruction error be largest?

Loading image…

Original (yellow box = zoom)
Reconstruction from the quantized coefficients
Surviving coefficients, log scale, zeros black (DCT: one 8 × 8 tile per block, block average top-left; Haar: coarsest average top-left, finer details outward)
Error: reconstruction − original, × 10, gray = 0
Zoom (32 × 32 pixels, 6 ×): original
Zoom: reconstruction (DCT: the ruler marks the 8-pixel blocks)

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

Open in the Playground →