Last modified: Mon Feb 11 10:57:02 UTC+0100 2019 © A. Tarpai

Little about progressive JPEG decoding

Ad the documentation of a progressive jpeg decoder.
�32-bit, integer, ansi C, jpg -> bmp in memory conversion. �

A JPEG file consist of a series of markers, between SOI and EOI, and various lenght bitstreams belonging to each marker:

[marker]---------bits------->

Progressive JPEG has multiple 'scans' in SOS markers: each scan contains a subset of coded coefficients from the whole image, which adds to the previous, giving an option of increased detail level after decoding each scan (progressive display).

Here is a simple progressive jpeg file that has 3 scans (3 full images on different details):

[SOI]
  [SOF]-------->
  [DHT]-------->
  [DQT]------>
  [SOS]---------------------------------->
  [SOS]---------------------------------------------------->
  [SOS]--------------------------------------------->
[EOI]

Progressive display

The purpose of a progressively coded image is to be able to display some rough image while the image is loading from slow network. A baseline JPEG can only be displayed row-by-row so the user has to wait to see the complete, whole image. A progressive JPEG will show a rough image first, then after scan-by-scan the image is getting finer and finer.

Baseline jpeg: MCU by MCU

BBBBBBBB......    BBBBBBBBBBBBBB    BBBBBBBBBBBBBB
..............    BBBBBBBBBBBBBB    BBBBBBBBBBBBBB
..............    BBBBBBBBBB....    BBBBBBBBBBBBBB
..............    ..............    BBBBBBBBBBBBBB
..............    ..............    BBBBBBBBBBBBBB

Progressive JPEG: scan by scan

IIIIIIIIIIIIII    PPPPPPPPPPPPPP    BBBBBBBBBBBBBB
IIIIIIIIIIIIII    PPPPPPPPPPPPPP    BBBBBBBBBBBBBB
IIIIIIIIIIIIII    PPPPPPPPPPPPPP    BBBBBBBBBBBBBB
IIIIIIIIIIIIII    PPPPPPPPPPPPPP    BBBBBBBBBBBBBB
IIIIIIIIIIIIII    PPPPPPPPPPPPPP    BBBBBBBBBBBBBB

JPEG compression is DCT based and this is achieved by transferring only a subset of the DCT coefficients in each scan. Either by band or by refining the coefficient values in each scan.

An example

For simplicity, lets suppose a data unit (DU) consists of 4x4 coefficients (so I don't have to draw that much), and forget about successive approximation for now and sub-sampling also. In progressive JPEG each scan contains coded coefficients belonging to a band (the Ss and Se parameter in the SOS header). An example of 3 scans:

                                                                       Ss Se
[SOS]ooooooooooooooooooooooooooooooooooo                     for band [0...0]
[SOS]xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx   for band [1...5]
[SOS]zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz          for band [6...15]

They fill each DU of the whole image:

DU             DU after       DU after       DU after
empty   -->    scan 1    -->  scan 2    -->  scan 3

. . . .        o . . .        o x x x        o x x x
. . . .        . . . .        x x . .        x x z z
. . . .        . . . .        . . . .        z z z z
. . . .        . . . .        . . . .        z z z z

The first band, the DC-band is always the first in JPEG. After dequantization (zeroes remain zeroes) the idct is performed. The result of the idct is pixel color values finally, something to display. The nature of the idct is, when only the DC coefficient is non zero, all values will be the same giving an average of the block.

o . . .         a a a a
. . . .   idct  a a a a
. . . .   --->  a a a a
. . . .         a a a a

Giving a 4x4 pixel area of the final image with the same color. A kind of 8x8 blocky image, but something to see even after the first scan.

The drawback: full coefficient buffer

Progressive JPEG decoding for progressive display requires a full coefficient buffer of the image. The decoder has to store and remember the previously decoded coefficients and this buffer can be quite large. For an 800x600 color image with 3 color components, computing with 16-bit coefficients it is 800 x 600 x 3 x 2 is almost 3 MB, which can be unacceptable in some applications.

Successive approximation

From the decoder point of view. Why? Because it's really not easy to just 'read backward' the figs in the standard, so here it is.

The most difficult part is how to handle runs and eob-s. As a thumbrule: every RUN skips zeroes - and zeroes only. Here is an example coefficient block from the previous scan: some coefficients have already a non-zero value (a,b and c). The k is the actual index during decoding. Lets suppose k points to 'a' and a new Huffman code comes.. a new coefficient with different RUN values:

. . . . . . a x 0 b 0 0 0 c 0 0 0 0 0 0 0 0 0 0 0 0 0
            |
            k

read new coef x
read r
skip r zeroes AND read as many successive bits as non-zero on the way

Examples:

. . . . . . a x 0 b 0 0 0 c 0 0 0 0 0 0 0 0 0 0 0 0 0 (r=0, 1 successive bit read)
            | |
            k k

. . . . . . a 0 x b 0 0 0 c 0 0 0 0 0 0 0 0 0 0 0 0 0 (r=1, 1 successive bit read)
            |   |
            k   k

. . . . . . a 0 0 b x 0 0 c 0 0 0 0 0 0 0 0 0 0 0 0 0 (r=2, 2* successive bit read)
            |       |
            k       k

. . . . . . a 0 0 b 0 x 0 c 0 0 0 0 0 0 0 0 0 0 0 0 0 (r=3, 2* successive bit read)
            |         |
            k         k

                                             (Note 2*: corrected by JC Li, thanks!)
               ....



. . . . . . a 0 0 b 0 0 0 c 0 0 0 0 0 0 0 0 0 0 x 0 0 (r=15, 3 successive bit read)
            |                                   |
            k                                   k

ZRL

. . . . . . a 0 0 b 0 0 0 c 0 0 0 0 0 0 0 0 0 0 0 0 0 (r=15, 3 successive bit read)
            |                                   |
            k                                   k

move 15 zeroes AND do nothing after!

The next iteration moves k to the next position and the process repeats.

When an EOB code comes, it's a little simpler:

. . . . . . a 0 0 b 0 0 0 c 0 0 0 0
            |
            k - - >

find all non-zero and read successive bits
3 successive bits read
done with this block.