4
$\begingroup$

I understand how the discrete cosine transform is used in image compression in standards like JPEG. However, the concept of wavelets is a mystery to me. I do know that wavelets are functions that have a wave like functions with value >0 only for short intervals of time, then they vanish. That is why they are called wavelets. I do not know anymore

What is not clear to me is precisely how such functions help in image compression and achieve a higher compression rate than our other transforms like the cosine transform.

What is the best place to learn this?

$\endgroup$

4 Answers 4

6
$\begingroup$

A common wavelet based standard is JPEG 2000 and a common DCT based standard is JPEG.

JPEG 2000 uses wavelets, but a good portion of the better compression it achieves than JPEG is due to the fact that JPEG uses a much much simpler entropy coder (JPEG does context-dependent Huffman codes and run length coding, JPEG 2000 does arithmetic coding with some extra tricks). You can gain a lot by tweaking the entropy coding stage. The particular wavelet transform you choose will make a difference as well. And how you decide to compress the coefficients makes a huge difference as well (JPEG reads its dct block coefficients in a zig-zag pattern and uses run length coding to compress long runs of zeros in the higher freq components due to the nature of the quantizers it uses).

The primary advantage of wavelets as used in JPEG 2000 versus rounding the DCT coefficients in the manner of JPEG is that it reduces blocking artifacts.

If you're not familiar with wavelets, you can look at an introductory text on wavelets, like Mallat's Wavelet tour of Signal Processing or Vetterli's new book (freely available online). Then, you can read the JPEG 2000 standard. These notes are kinda nice at a high level as well (and it has good pointers to the references).

For a quick review of JPEG, you can look at Gonzalez & Woods' Digital Image Processing (second or third edition should be fine).

$\endgroup$
2
  • $\begingroup$ I know that for JPEG we take the original image and carry out a DCT on it on 8x8 blocks, then we scan diagonally and carry out entropy encoding using huffman encoding. I know about that. What is mystery to me is what is a wavelet transform and how does it help in compression. $\endgroup$
    – quantum231
    Commented May 10, 2015 at 18:42
  • $\begingroup$ I've pointed you out to some references. It helps compression in the same way transforming and quantizing DCT coefficients -- if you choose the right wavelet, you can zero out some coefficients and quantize others and store them instead of all the coefficients and get pretty good approximations of the image. $\endgroup$
    – Batman
    Commented May 11, 2015 at 0:13
2
$\begingroup$

I think that modern video codecs using block transforms in intra mode have better subjective/objective compression or at least on par with jpeg 2000. See eg: https://hal.archives-ouvertes.fr/hal-02169185/document

See also the h265-intra based heif still image format used by Apple as a jpeg replacement: https://en.m.wikipedia.org/wiki/High_Efficiency_Image_File_Format

A codec that is slightly less efficient at compressing but offers the right kind of flexibility (or simplicity), lower compute cost, scalability, robustness to storage errors could be the better choice. Codec success is also about license/patents, politics, availability of hardware acceleration and suitability of special cpu instructions like simd.

While wavelets may be a beautiful theory with a well founded mathematical development, my impression is that in practical codec implementations on digital computers, traditional dsp methods behave quite similar and have been quite competitive - wavelets are hard to distinguish from filterbanks once they are implemented in code or logic gates. Some proponents of wavelets seems to be unaware of 50 years of dsp history, choosing rather to pit wavelets up against whole image ffts or similar representations that makes wavelets look more revolutionary than reality.

$\endgroup$
2
$\begingroup$

Continuous wavelets are indeed functions that wiggle and eventually vanish. For the discrete ones, used in image compression, their is another point of view. Given a block $B$ of pixels of size $2K\times 2K$, a wavelet will convert it into four $K\times K$ blocks, that contain the same information content as the original block, but hopefully reorganized in a way such that useful information pops up first, so that it can compressed more easily: because the salient data is more evident, because less useful info is scattered, because its faster, whatever. Four parts are, typically:

  • A: an approximation of the whole block, like some a down-sampled average, on a four-fold smaller picture, not orientation-specific
  • H: an "horizontal" detail that detect mostly horizontal features
  • V: an "horizontal" detail that detect mostly vertical features
  • D: an "horizontal" detail that detect mostly diagonal features

A rendition is proposed below, and it can be iterated to better capture features are different scales. wavelet decomposition

Hopefully, subimages A, D, H, V are together somehow simpler than the original image; hence easier to code. Some combined wavelet properties allow this to happen:

  • wavelets absorb polynomial: a part of the image that is regular enough (smooth like a polynomial eg a slow-varying shading) can be summarized efficiently
  • wavelets have derivative properties: they could enhance some edges
  • wavelets oscillate somehow, and may match wiggling or periodic textures
  • wavelets separate the above from noise when evenly spread.

Then, we could keep a list of the highest wavelet coefficients. Only a small percentage of ten may encode large part of the image. The decomposition is somehow sparse. However, how elegant they could be, the actual coefficient encoding is a bit complicated, and other scheme can be more efficient in compression ratio, visual quality and speed.

Note that wavelet compression can be used in some domains, like pre-production movie storage, medical imaging. It can also be used in the coding of heterogeneous tree-dimensional meshes, as we did in our HexaShrink, an exact scalable framework for hexahedral meshes with attributes and discontinuities: multiresolution rendering and storage of geoscience models, combining 12, 2D and 3D wavelets.

$\endgroup$
-1
$\begingroup$

In Mallat's introduction in Wavelet Analysis & Its Applications A Wavelet Tour of Signal Processing, he explains how Fourier transforms are adapted to "stationary" (constant by translations) signals (cos, sin), and wavelets are adapted to transitory or local signals.

Fourier encoding is not as natural as wavelets to represent local signals, properties.

However, wavelets are well localized and few coefficients are needed to represent local transient structures. As opposed to a Fourier basis, a wavelet basis defines a sparse representation of piecewise regular signals, which may include transients and singularities. In images, large wavelet coefficients are located in the neighborhood of edges and irregular textures.

$\endgroup$
3
  • $\begingroup$ Hey, you're a mathematician: Define "stationary", please, because that term has a meaning in stochastic signals (i.e., the things you can compress) and it's not compatible with what you write! Define "hard to represent" as well (what's a measure for "hardness", please?). $\endgroup$ Commented Feb 8, 2022 at 20:34
  • $\begingroup$ @MarcusMüller Thanks for the suggestions. I edited to improve that, while avoiding being formal. $\endgroup$
    – Soleil
    Commented Feb 8, 2022 at 23:58
  • 1
    $\begingroup$ Thanks! Is it possible "constant by translation" means "periodic"? $\endgroup$ Commented Feb 9, 2022 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.