algorithmtransformtrigonometryzigzag

Image compressing - zigzag after Discrete Cosine Transform


I'm trying to make application which compress image from camera. I have mat image and 3 separate arrays for channels. I've found something about discrete cosine transform DCT and read that I should do zigzag algorithm (I've found something with zigzag here).
I understand that DCT makes output array but I can't see if zigzag makes one too and where.
Maybe there is some simple example of zigzag algorithm (or dct with zigzag) with input and output arrays?


Solution

  • Images are from this wikipedia article.

    TL,DR: see the bold part below.

    Start with a 2D array of pixel values. There are 64 bytes of information.

    enter image description here

    After applying an offset, and computing the DCT, the output is a 2D array of frequency coefficients. So now there are 64 floating point values.

    enter image description here

    Here's the key behind how JPEG compression works. The frequency coefficients in the upper left of the array (the low frequencies) are much more important to the image quality than the frequency coefficients in the lower right of the array (the high frequencies).

    So the next step is to apply quantization to the array. The quantization allocates a variable number of bits to each value in the array. Values in the upper left get more bits, and values in the lower right get fewer bits. After quantization, the array looks like this.

    enter image description here

    Notice that many of the values in the lower right are now zero. So finally we get to the zigzag, which looks like this:

    enter image description here

    The purpose of the zigzag is to convert the 2D array of quantized DCT coefficients into a 1D array, where the first elements come from the upper left, and later elements come from the lower right, of the 2D array. After the zigzag, the array looks like this

    -26 -3 0 -3 -2 -6 2 -4 1 -3 1 1 5 1 2 -1 1 -1 2 0 0 0 0 0 -1 -1 0 0 ...
    

    where the ... is all 0. Depending on how much compression is desired, the array can be chopped at any point. In this example, chopping the array after 19 elements is a good trade-off between quality and compression. So only the first 19 elements get stored in the JPEG file, as opposed to storing the original 64 raw pixel values.

    Note there are additional compression steps after chopping the zigzag output. Those are described in the linked article.