Return to Digital Photography Articles

JPEG Huffman Coding Tutorial

After quantization, huffman / entropy coding is one of the more significant contributors to the file size savings in JPEG compression. This page provides a tutorial on how the huffman coding works in a JPEG image. If you have ever wondered how JPEG compression works, this may provide you with some detailed insight.

Why I wrote this tutorial

In attempting to understand the inner workings of JPEG compression, I was unable to find any real details on the net for how Huffman coding is used in the context of JPEG image compression. There are many sites that describe the generic huffman coding scheme, but none that describe how it will appear in a JPEG image, after factoring in the DHT tables, interleaved chroma subsampling components, etc. While it is relatively easy to understand the JPEG marker extraction, the Start of Scan data segment is the least understood and most important part of the image data. Therefore, I decided to create a page to walk through a decompression example. Hopefully others will find this useful!

The relevant sections in the JPEG Standard are quite obscure -- enough so that I set out to analyze several JPEG images to reverse-engineer how the huffman coding was being applied in a JPEG JFIF file.

Latest Update:

[09/22/2009]: Corrected Table 5 (added entry for DC 00 code).
[09/19/2008]: Corrected Table 1 (added entry for codes of length 9 bits).
[12/03/2007]: Corrected typo in text near Table 5 (code 00101). Added JPEGsnoop output (at end of Tutorial).
[01/27/2007]: Added section describing how to expand DHT into bit strings.

The Goal

The goal of this tutorial is to take a simple JPEG image and try to decode the compressed image data by hand, learning how the Huffman compression scheme works in the process.

Simplest JPEG Example

Most digital photos are full-color natural/organic images, which means that all three image components (one luminance and two color channels) will all have both low and high-frequency content. In addition, nearly all digital photos use chroma subsampling, which makes the extraction process a little more complicated. For the purposes of showing the basic huffman extraction, we will start with the simplest of all JPEG images:

  • Grayscale - no content in the two color channels
  • Solid color in each MCU - By making all pixels in an 8x8 block the same color, there will be no AC components.
  • No chroma subsampling - Makes scan data extraction simpler: Y, Cb, Cr, Y, Cb, Cr, etc.
  • Small Image - Total image size is 16x8 = two MCUs or blocks. This makes the extraction in this tutorial shorter.

Creating the Image

For the purposes of this tutorial, my working image will simply be a 16x8 pixel image, with two solid color blocks: one black and the other white. Note that each block is 8x8 pixels in size. The actual image is here: . If you want to download it, right-click and select Save Picture As...

Creating the sample image was trivial, working at 1600% view. Important that dimensions and any changes in the content are on 8-pixel boundaries. Overall image dimensions should be a multiple of 8 pixels as well, in both directions. The image below is a magnified version with a grid overlayed.

Once the image was created, it was saved with Photoshop CS2's Save for Web... command. This kept the file size down as it discards other extraneous file information (metadata, etc.) that is not relevant to this tutorial. Some other important points:

  • Use Save for Web - Reduces total file content to minimal subset.
  • Use Quality level 51+ - This ensures that there is no chroma subsampling enabled in the JPEG encoding process, according to the way that Photoshop Save for Web operates. I used quality 80 for this example.
  • Turn Optimized Off - For the purposes of this example, I think it is important to work with realistic huffman tables, not degenerate single-entry tables. Therefore I recommend that JPEG Huffman Table Optimization is left off.
  • Other settings: Blur off, Progressive off, ICC profile off.

Grayscale Photoshop Images

It should be noted that when you save a JPEG image from within Photoshop it always contains three components (Y, Cb, Cr). If you change the mode to grayscale (via Mode->Grayscale), the three components are still saved, even though the JPEG standard supports an image with only one component (which would be assumed to be grayscale).

What is Huffman Coding / Entropy Coding?

Huffman coding is a method that takes symbols (e.g. bytes, DCT coefficients, etc.) and encodes them with variable length codes that are assigned according to statistical probabilities. A frequently-used symbol will be encoded with a code that takes up only a couple bits, while symbols that are rarely used are represented by symbols that take more bits to encode.

A JPEG file contains up to 4 huffman tables that define the mapping between these variable-length codes (which take between 1 and 16 bits) and the code values (which is an 8-bit byte). Creating these tables generally involves counting how frequently each symbol (DCT code word) appears in an image, and allocating the bit strings accordingly. But, most JPEG encoders simply use the huffman tables presented in the JPEG standard. Some encoders allow one to optimize these tables, which means that an optimal binary tree is created which allows a more efficient huffman table to be generated.

For a reasonable explanation of how it works, please see this example of Huffman coding an ASCII string and the overview from Wikipedia.

For more details, please see my article on Optimized JPEGs - optimizing the huffman tables, particularly the first introductory sections and the section near the end titled "Standard Huffman Tables".

Decoding the JPEG Scan Data

Using JPEGsnoop

For those who are trying to understand the complex huffman decoding in a JPEG image, I'm happy to report that JPEGsnoop can now report all of the variable length code decoding for each MCU (use the Detailed Decode option). For the sample output, scroll to the bottom of this tutorial.

Decoding by Hand

The following is the decode method done by hand, which is obviously impractical for most images, but is shown here in detail to help one learn the process involved.

 

The above hex dump datastream shows the beginning of the Start of Scan (SOS marker 0xFFDA) marked in yellow, followed by some additional details in green and then the actual scan data selected in dark blue. Finally, the image is terminated with an End of Image (EOI marker 0xFFD9). So, the huffman-coded data content is only 9 bytes long.

Comparison of Compression File Sizes

For the sake of comparison, the original image (16 pixels by 8 pixels) contains a total of 128 pixels (2 MCUs). With 8 bits per channel (RGB), this corresponds to an uncompressed image size of 384 bytes (128 pixels x 8 bits/channel x 3 channels x 1 byte/8 bits). Clearly, using a run-length encoded format such as GIF would have produced even more image compression in examples like this (although GIF actually takes 22 bytes to code the stream because there are 16 separate runs). JPEG is not really designed to be optimized for this type of synthetic (non-organic) image.

If one uses optimized JPEG encoding, it is possible to reduce the image content size even further. In the example image, the optimized version has much smaller huffman tables (DHT) and shorter bitstrings to represent the same codewords. The net effect is that the image content size is reduced even further (to 7 bytes).

File FormatTotal Size Overhead Size Image Content Size
BMP (Uncompressed) 440 Bytes 56 Bytes 384 Bytes
JPEG653 Bytes 644 Bytes 9 Bytes
JPEG (Optimized) 304 Bytes 297 Bytes 7 Bytes
GIF60 Bytes 38 Bytes 22 Bytes

Scan Data Decode

The scan data is:

FC FF 00 E2 AF EF F3 15 7F

To help resiliency in the case of data corruption, the JPEG standard allows JPEG markers to appear in the huffman-coded scan data segment. Therefore, a JPEG decoder must watch out for any marker (as indicated by the 0xFF byte, followed by a non-zero byte). If the huffman coding scheme needed to write a 0xFF byte, then it writes a 0xFF followed by a 0x00 -- a process known as adding a stuff byte.

For our extraction purposes, we will replaceme any padding bytes (0xFF00 with 0xFF):

FC FF E2 AF EF F3 15 7F

The expectation is that image content is 3 components (Y, Cb, Cr). Within each component, the sequence is always one DC value followed by 63 AC values.

For each MCU, with no chroma subsampling, we would expect the following data to be encoded:

Section123456
ComponentYCbCr
AC / DCDCACDCACDCAC

Note that some people get the order of the chrominance channels mixed up, and assume that it is YCrCb instead.

The figure below shows what the DCT matrix from a single MCU (8x8 pixel square) in a digital photo typically looks like. These are the entries after quantization, which has caused many of the higher-frequency components (towards the bottom-right corner of the matrix) to become zero. By the distribution of values in the frequency-domain matrix representation, it is possible to determine that the 8x8 pixel square had very little high-frequency content (i.e. it had only a gradual intensity / color change).

The DC component represents the average value of all pixels in the 8x8 MCU. Since we have deliberately created an image where all pixels in the 8x8 block are the same, we expect this value to represent either the black or white "color". The code provided in the DC entry (#0) indicates a huffman-encoded size (e.g. 1-10 bits) which is the number of bits needed to represent the average value for the MCU (eg. -511...+511).

Note that the DC component is encoded as a relative value with respect to the DC component of the previous block. The first block in the JPEG image is assumed to have a previous block value of zero.

Following the single DC component entry, one or more entries are used to describe the remaining 63 entries in the MCU. These entries (1..63) represent the low and high-frequency AC coefficients after DCT transformation and quantization. The earlier entries represent low-frequency content, while the later entries represent high-frequency image content. Since the JPEG compression algorithm uses quantization to reduce many of these high-frequency values to zero, one typically has a number of non-zero entries in the earlier coefficients and a long run of zero coefficients to the end of the matrix.

For the purposes of this tutorial, I have deliberately created an image that has constant color across all 8x8 pixels in each of the two MCU. Because there are no changes in value across each 8x8 pixel region, there is no AC (or higher frequency content) within the block. As a result, all 63 entries in the AC portion are expected to be zero (unlike the figure above). This allows us to focus on the DC component, which we do expect to change from MCU to MCU block.

The hex string shown earlier (after removal of padding bytes) can be represented in binary as the following:

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111

Extract Huffman Code Tables

Using a utility such as JPEGsnoop, you can extract the Huffman tables from the JPEG image file. Often, you will find four huffman table entries (tagged with a DHT marker):

  • DHT Class=0 ID=0 - Used for DC component of Luminance (Y)
  • DHT Class=1 ID=0 - Used for AC component of Luminance (Y)
  • DHT Class=0 ID=1 - Used for DC component of Chrominance (Cb & Cr)
  • DHT Class=1 ID=1 - Used for AC component of Chrominance (Cb & Cr)

The huffman compression tables are encoded in a somewhat confusing manner. Although you can draw out the binary tree by hand, it will be easier if you rely on a tool such as JPEGsnoop to generate all of the binary comparison strings for each huffman code in all four DHT sections.

The following four tables were extracted from the JPEG file that was created by Photoshop for the purposes of this tutorial. Other JPEG images may be reliant on different DHT tables, so it is important to extract them prior to analyzing the file. Note that turning on JPEG Optimization will create vastly different Huffman tables, with far fewer entries. For a point of comparison, the image described in this tutorial would only need optimized huffman tables of one entry each to represent our image content.

NOTE: It is important to realize that in each case the DHT entries in the JPEG file only list the Length and Code values, not the actual Bit String mapping. It is up to you to rebuild the binary tree representation of the DHT table to derive the bit strings! Please see the DHT Expansion section near the end of this tutorial for more details.

Table 1 - Huffman - Luminance (Y) - DC

LengthBitsCode
3 bits 000
001
010
011
100
101
110		 04
05
03
02
06
01
00 (End of Block)
4 bits 1110 07
5 bits 1111 0 08
6 bits 1111 10 09
7 bits 1111 110 0A
8 bits 1111 1110 0B

Table 2 - Huffman - Luminance (Y) - AC

LengthBitsCode
2 bits 00
01		 01
02
3 bits 100 03
4 bits 1010
1011
1100		 11
04
00 (End of Block)
5 bits 1101 0
1101 1
1110 0 		05
21
12
6 bits 1110 10
1110 11 		31
41
... ... ...
12 bits ...
1111 1111 0011
...		 ...
F0 (ZRL)
...
... ... ...
16 bits ...
1111 1111 1111 1110 		...
FA

Table 3 - Huffman - Chrominance (Cb & Cr) - DC

LengthBitsCode
2 bits 00
01		 01
00 (End of Block)
3 bits 100
101		 02
03
4 bits 1100
1101
1110		 04
05
06
5 bits 1111 0 07
6 bits 1111 10 08
7 bits 1111 110 09
8 bits 1111 1110 0A
9 bits 1111 1111 0 0B

Table 4 - Huffman - Chrominance (Cb & Cr) - AC

LengthBitsCode
2 bits 00
01		 01
00 (End of Block)
3 bits 100
101		 02
11
4 bits 1100 03
5 bits

1101 0
1101 1

04
21
6 bits 1110 00
1110 01
1110 10 		12
31
41
... ... ...
9 bits ...
1111 1100 0
...		 ...
F0 (ZRL)
...
... ... ...
16 bits ...
1111 1111 1111 1110 		...
FA

 

Table 5 - Huffman DC Value Encoding

The following table shows how the bit fields that follow a DC entry can be converted into their signed decimal equivalent. To use this table, start with the DC code value and then extract "Size" number of bits after the code. These "Additional Bits" will represent a signed "DC Value" which becomes the DC value for that block. Note that this table applies to any JPEG file -- this table is not written anywhere in the JPEG file itself.

For example, let's assume that one was about to decompress a chrominance DC entry. If the previously-decoded "DC Code" was 05, then we must extract 5 bits following the code bits. If the next 5 bits were 00101, then this can be interpreted as decimal -26. The bits 10001 would be +17 and 11110 would be +30.

DC Code Size Additional Bits DC Value
00 0   0
01 1 01 -11
02 2 00,0110,11 -3,-22,3
03 3 000,001,010,011100,101,110,111 -7,-6,-5,-44,5,6,7
04 4 0000,...,01111000,...,1111 -15,...,-88,...,15
05 5 0 0000,... ...,1 1111 -31,...,-16 16,...,31
06 6 00 0000,... ...,11 1111 -63,...,-32 32,...,63
07 7 000 0000,... ...,111 1111 -127,...,-64 64,...,127
08 8 0000 0000,... ...,1111 1111 -255,...,-128 128,...,255
09 9 0 0000 0000,... ...,1 1111 1111 -511,...,-256 256,...,511
0A 10 00 0000 0000,... ...,11 1111 1111 -1023,...,-512 512,...,1023
0B 11 000 0000 0000,... ...,111 1111 1111 -2047,...,-1024 1024,...,2047

Block 1 - Luminance

Luminance (Y) - DC

Referring to the Y(DC) table (Table 1), we start with the first few bits of the coded stream (1111 1100 1111...) and recognize that code x0A matches the bit string 1111 110.

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> Code: 0A

This code implies that hex A (10) additional bits follow to represent the signed value of the DC component. The next ten bits after this code is 0 1111 1111 1. Table 5 above shows the DC values represented by these "additional bits" -- in this case, the bit string corresponds to a value of -512.

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> Value: -512

Our progress so far:

Bits1111 1100 1111 1111 1 110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
MCU1???
ComponentY ???
AC/DC DC ???
Value -512 ???

Luminance (Y) - AC

After the DC component, we begin the 63-entry AC matrix for the Y Luminance. This uses a different Huffman table (Table 2).

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> Code: 00 (EOB)

In the above huffman code table, the code 1100 corresponds to an EOB (End of Block). Therefore, the AC components was cut short early (no other codes). This means that all 63 entries of the matrix (all entries except the 1st entry, which is the DC component) are zeros. Since we have finished the luminance component, we then move on to the chrominance components (Cb and Cr).

Bits1111 1100 1111 1111 1 1100010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
MCU1???
ComponentY ???
AC/DC DC AC ???
Value -512 0???

Block 1 - Chrominance

Chrominance (Cb) - DC

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> Code: 00 (EOB)

End of chrominance DC, start on AC.

Chrominance (Cb) - AC

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> Code: 00 (EOB)

Again, the AC is terminated right away. Now, we move on to the second chrominance channel, Cr.

Bits1111 1100 1111 1111 1 11000101010 1111 1110 1111 1111 0011 0001 0101 0111 1111
MCU1???
Component Y Cb ???
AC/DC DC AC DC AC ???
Value -512 000???

Chrominance (Cr) - DC

Refer to Table 3 for the relevant Huffman codes.

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> Code: 00 (EOB)

This marks the end of the DC.

Chrominance (Cr) - AC

Refer to Table 4 for the relevant Huffman codes.

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> Code: 00 (EOB)

This marks the end of the AC.

Bits1111 1100 1111 1111 1 110001 0101 01111 1110 1111 1111 0011 0001 0101 0111 1111
MCU1???
ComponentY Cb Cr ???
AC / DC DC AC DC AC DC AC ???
Value -51200000???

Block 2 - Luminance

Luminance (Y) - DC

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> CODE: 0A

This code indicates that the value is stored in the next ten bits (A in hex is 10 in decimal):

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> Value: +1020

Bits1111 1100 1111 1111 1 110001 0101 01111 1110 1111 1111 0011 0001 0101 0111 1111
MCU12???
ComponentY Cb Cr Y???
AC / DC DC AC DC AC DC AC DC ???
Value -512 00000 +1020 ???

Luminance (Y) - AC

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> CODE: EOB

The end-of-block indicator means that all remaining values are zero. Since we haven't even started with the first value, all 63 values can be interpreted as zero. This means that there is no non-DC image content, which is to be expected since all 64 pixels (8x8) in the block are the same color.

Bits1111 1100 1111 1111 1 110001 0101 01111 1110 1111 1111 00 1100 01 0101 0111 1111
MCU12???
ComponentY Cb Cr Y???
AC / DC DC AC DC AC DC AC DC AC ???
Value -512 00000 +1020 0???

Block 2 - Chrominance

Chrominance (Cb) - DC

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> CODE: 00 (EOB)

Chrominance (Cb) - AC

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> CODE: 00 (EOB)

Chrominance (Cr) - DC

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> CODE: 00 (EOB)

Chrominance (Cr) - AC

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111
=> CODE: 00 (EOB)

Bits1111 1100 1111 1111 1 110001 0101 01111 1110 1111 1111 00 1100 0101010111 1111
MCU12X
ComponentY Cb Cr Y Cb Cr X
AC / DC DC AC DC AC DC AC DC AC DC AC DC AC X
Value -512 00000 +1020 00000X

Remainder

Because the scan data must end on a byte boundary, there may be a remainder of bits that will simply be tossed. In this case we see 6 bits (all-1's) that will be discarded.

1111 1100 1111 1111 1110 0010 1010 1111 1110 1111 1111 0011 0001 0101 0111 1111

Conversion to Spatial Domain

Now that we have the DCT (Discrete Cosine Transform) values, we can try to determine what the content of the image was in the spatial domain. Remember that the DC & AC values that we decompressed from the huffman coding are the frequency-domain representation of the image, not the real YCbCr values.

Given that all of the values in the Cb and Cr channels (chrominance) are zero, we can assume that the image is grayscale and instaed focus on the luminance values (brightness).

Second, all of the AC component values are zero, which means that there is no higher frequency content in the images -- in fact, we can determine that all of the image data in each 8x8 block is of the same color & intensity (i.e. only the DC component remains).

We can determine the following:

BlockEncoded (Relative) DC Value
1Y = -512
2 Y = +1020

Relative DC to Absolute DC

Note that the DC components are encoded as a difference from the previous block (with the first block assumed to start relative to zero). Therefore, we know that block 1 has a DC value of -512, but that block 2 has a DC value of +1020 relative to block 1. So, we now know:

BlockActual (Absolute) DC Value
1Y = -512
2 Y = +508

DCT to RGB

Finally, we want to convert the DCT DC value to an RGB value. Assuming that the gain of the DCT transform is 4, we divide the values by 4 to get block1 = -128, block2 = +127.

Now, we have to convert between YCbCr and RGB. Please refer to the formulae provided on the JPEG color conversion page. There, you will see that we require a level shift of +128 to get input values in the range (0..255).

Color conversion yields RGB values of:

BlockRGB Value (hex)RGB Value (decimal)
1(0x00,0x00,0x00)(0,0,0)
2 (0xFF,0xFF,0xFF) (255,255,255)

... and these are the original values that were used to create the JPEG image!

Expansion of DHT Table into binary bit strings

Note that the DHT tables that appear in the JPEG file only define the number of codes for each bitstring length, followed by a sequence of all the code words. The bit strings that are used to represent each of these code words is not included! It is the job of the JPEG decoder to derive these bit strings from the little information that is provided.

There are many methods in which the generation of the binary strings is performed in a decoder, and most of them are heavily optimized for performance (e.g. the djpeg huffman routines). These implementations are quite difficult to learn from. I find it much more instructive to generate these bit sequences by drawing out the huffman binary tree by hand.

In an extreme simplification, binary trees are composed of a root node which has a left and right branch to other nodes. Each of these nodes can either be a leaf node (the end of a branch) or split further into two more nodes.

The actual DHT in the JPEG file:

The following was extracted directly from the DHT (Define Huffman Table, shown above in Table 2: Luminance AC) in the JPEG file using JPEGsnoop.

  Class = 1 (AC Table)
  Destination ID = 0
    Codes of length 01 bits (000 total): 
    Codes of length 02 bits (002 total): 01 02 
    Codes of length 03 bits (001 total): 03 
    Codes of length 04 bits (003 total): 11 04 00 
    Codes of length 05 bits (003 total): 05 21 12 
    Codes of length 06 bits (002 total): 31 41 
    Codes of length 07 bits (004 total): 51 06 13 61 
    Codes of length 08 bits (002 total): 22 71 
    Codes of length 09 bits (006 total): 81 14 32 91 A1 07 
    Codes of length 10 bits (007 total): 15 B1 42 23 C1 52 D1 
    Codes of length 11 bits (003 total): E1 33 16 
    Codes of length 12 bits (004 total): 62 F0 24 72 
    Codes of length 13 bits (002 total): 82 F1 
    Codes of length 14 bits (006 total): 25 43 34 53 92 A2 
    Codes of length 15 bits (002 total): B2 63 
    Codes of length 16 bits (115 total): 73 C2 35 44 27 93 A3 B3 36 17 54 64 74 C3 D2 E2 
                                         08 26 83 09 0A 18 19 84 94 45 46 A4 B4 56 D3 55 
                                         28 1A F2 E3 F3 C4 D4 E4 F4 65 75 85 95 A5 B5 C5 
                                         D5 E5 F5 66 76 86 96 A6 B6 C6 D6 E6 F6 37 47 57 
                                         67 77 87 97 A7 B7 C7 D7 E7 F7 38 48 58 68 78 88 
                                         98 A8 B8 C8 D8 E8 F8 29 39 49 59 69 79 89 99 A9 
                                         B9 C9 D9 E9 F9 2A 3A 4A 5A 6A 7A 8A 9A AA BA CA 
                                         DA EA FA 
    Total number of codes: 162

So, how do we create the binary bit-strings for each of these codes?

Well, we start to build a binary tree, creating new branches and putting the code words into leaf nodes of the tree. Row 1 of the tree contains code words that only require 1 bit to encode, row 2 contains code words (leaf nodes) that only require 2 bits to encode and so on.

We first start with row 0:

  • Row 0 (the root node) is almost always a parent node, creating a left and a right branch down to the next row. We label the left branch 0 and the right branch 1.
  • At row 1, we try to fill in any of the nodes (there are 2 at this level) with code words that take 1 bit to encode. We see from the DHT that there are no codes of length 1 bit. So, for each of the two nodes we spawn off a left and right node below (on row 2), creating a total of 4 nodes. Again, for these branches, we label the left one 0 and the right one 1.
  • At row 2, we will try to fill in any codes of length 2 bits, starting from left to right. This time we see in the DHT that there are two codes that can be encoded with bit strings of length 2. So, we take the first code value x01 (hex) and place this in the first node, making it a leaf node (no further branches will come from it). We then take the second code value x02 and place this in the second node, making it too a leaf node. At this point we have two more nodes left in this row of the tree but no more codewords listed in the DHT for this bitstring length. Therefore, we create two branches for each of the remaining nodes of this row. Since two nodes are left, this will create a total of 4 branches, meaning that there will be again 4 nodes in the third row of the binary tree.
  • At row 3, we have four nodes available, but the DHT indicates only one codeword uses 3 bits to encode. So, we place x03 at the leftmost of these nodes, and we create branches for each of the remaining three nodes (making 6 nodes for row 4).
  • At row 4, we have six nodes available, but the DHT indicates only three codewords use 4 bits to encode. This time we terminate three nodes (making them leaf nodes) and we further extend the other three down to row 5.

This process continues until we have used all of the codewords defined in the DHT table. The diagram below shows the expansion of the first four rows of the above DHT.

Binary Tree Expansion of DHT

Once the binary tree has been completed, you can read off the bit strings for each code word by combining the bit labels of each branch on the path down from the root node. For example, code word 0x04 is encoded by the binary bit string 1011 because we need to take branch 1 from the root node, 0 from the node on row 1, 1 from the node on row 2 and branch 1 from the node on row 3.

This process can be quite laborious, and the binary tree often takes on a shape that would be difficult to draw through to completion. To make this easier, I have added a feature, DHT Expand, to JPEGsnoop that determines the binary bit strings for each of the code words appearing in the DHT table.

Below is the expansion of the first few rows of the table, using JPEGsnoop with the DHT Expand mode enabled.

  Expanded Form of Codes:
    Codes of length 02 bits:
      00 = 01
      01 = 02
    Codes of length 03 bits:
      100 = 03
    Codes of length 04 bits:
      1010 = 11
      1011 = 04
      1100 = 00 (EOB)
    Codes of length 05 bits:
      11010 = 05
      11011 = 21
      11100 = 12
    Codes of length 06 bits:
      111010 = 31
      111011 = 41
    Codes of length 07 bits:
      1111000 = 51
	   ...
    Codes of length 15 bits:
      111111111000100 = B2
      111111111000101 = 63
    Codes of length 16 bits:
      1111111110001100 = 73
      1111111110001101 = C2
	   ...
      1111111111111100 = DA
      1111111111111101 = EA
      1111111111111110 = FA

Implementations in real JPEG decoders optimize this mechanism heavily as the bitstring search / parsing process is not a trivial task in processors designed to work with 32-bit words or bytes. Most of them end up creating large lookup tables that define lower and upper bounds for a match of a particular bitstring / code.

More Realistic JPEG Images

Obviously the above is an extremely simple example JPEG image. However, real images will have some other characteristics that you will encounter:

  • Chroma subsampling - You can expect that most photos will have 2x1 chroma subsampling, which will mean that the decoding sequence per MCU will be Y1 Y2 Cb Cr instead of Y Cb Cr.
  • AC components - You most certainly will have non-zero AC coefficients, unlike the above. In such a case, you will generally have a few non-zero values, which will eventually be terminated with a ZRL (code word 0xF0) which indicates a run of 16 zeros and then probably a EOB (code word 0x00).

Some more detail regarding Huffman coding with chroma subsampling and other factors are described in the JPEG decoder page.

JPEGsnoop Detailed Decode Output

Running JPEGsnoop on the image shown above, with the Scan Segment->Detailed Decode option enabled, the following output is shown:

*** Decoding SCAN Data ***
  OFFSET: 0x00000282
  Scan Decode Mode: Full IDCT (AC + DC)


    Lum (Tbl #0), MCU=[0,0]
      [0x00000282.0]: ZRL=[ 0] Val=[ -512] Coef=[00= DC] Data=[0x FC FF 00 E2 = 0b (11111100 11111111 1------- --------)] 
      [0x00000285.1]: ZRL=[ 0] Val=[    0] Coef=[01..01] Data=[0x E2 AF EF F3 = 0b (-1100--- -------- -------- --------)] EOB
                      DCT Matrix=[-1024     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]

    Chr(0) (Tbl #1), MCU=[0,0]
      [0x00000285.5]: ZRL=[ 0] Val=[    0] Coef=[00= DC] Data=[0x E2 AF EF F3 = 0b (-----01- -------- -------- --------)] EOB
      [0x00000285.7]: ZRL=[ 0] Val=[    0] Coef=[01..01] Data=[0x E2 AF EF F3 = 0b (-------0 1------- -------- --------)] EOB
                      DCT Matrix=[    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]

    Chr(0) (Tbl #1), MCU=[0,0]
      [0x00000286.1]: ZRL=[ 0] Val=[    0] Coef=[00= DC] Data=[0x AF EF F3 15 = 0b (-01----- -------- -------- --------)] EOB
      [0x00000286.3]: ZRL=[ 0] Val=[    0] Coef=[01..01] Data=[0x AF EF F3 15 = 0b (---01--- -------- -------- --------)] EOB
                      DCT Matrix=[    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]


    Lum (Tbl #0), MCU=[1,0]
      [0x00000286.5]: ZRL=[ 0] Val=[ 1020] Coef=[00= DC] Data=[0x AF EF F3 15 = 0b (-----111 11101111 111100-- --------)] 
      [0x00000288.6]: ZRL=[ 0] Val=[    0] Coef=[01..01] Data=[0x F3 15 7F FF = 0b (------11 00------ -------- --------)] EOB
                      DCT Matrix=[ 2040     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]

    Chr(0) (Tbl #1), MCU=[1,0]
      [0x00000289.2]: ZRL=[ 0] Val=[    0] Coef=[00= DC] Data=[0x 15 7F FF D9 = 0b (--01---- -------- -------- --------)] EOB
      [0x00000289.4]: ZRL=[ 0] Val=[    0] Coef=[01..01] Data=[0x 15 7F FF D9 = 0b (----01-- -------- -------- --------)] EOB
                      DCT Matrix=[    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]

    Chr(0) (Tbl #1), MCU=[1,0]
      [0x00000289.6]: ZRL=[ 0] Val=[    0] Coef=[00= DC] Data=[0x 15 7F FF D9 = 0b (------01 -------- -------- --------)] EOB
      [0x0000028A.0]: ZRL=[ 0] Val=[    0] Coef=[01..01] Data=[0x 7F FF D9 00 = 0b (01------ -------- -------- --------)] EOB
                      DCT Matrix=[    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]
                                 [    0     0     0     0     0     0     0     0]

 

Reader's Comments:

Please leave your comments or suggestions below!
2010-07-15ari
 hi

i'm doing well untill the dequantization stage and then after the idct and color conversion process i dont get the right RGB values like the RGB values shown in jpegsnoop. i think i miss something here.

i do the idct process by multipying the dequantized values with the idct matrix element by element and then i do the level shift and convert it to RGB values using your formula.

can you give me some hints??? thanks
2010-06-22ari
 i am now working on my project to make a jpeg decoder using c. can you tell me how to generate the binary tree for the huffman decoding stage??
2010-06-08Thuan Nguyen
 Thank you very much for your tutorial. It helped me a lot.
2010-05-14G Suresh
 Very Nice Material Boss.....
But One Thing I didnt get here. Here U mentioned only about DC component decoding . I mean U considered all 63 AC components are Zeros .

If U dont Mind can u give some suggestion to decode if all AC components not zeros
 The example I showed was designed to be extremely simple, and based on an image that had AC coefficients that were all zero. The technique to perform the huffman decoding of the AC coefficients is very similar to the DC coefficients but you have to handle the Zero Run Length values (first digit in the code).
2010-05-06Rob B
 These tutorials are worth so much to us, since they are the only ones I have found that are practical instead of just theoretical.

Using this tutorial and JPEGsnoop.exe to fill in the information gaps, I was able to program for fast 1/8 scale decoding (parsing all data but using DC terms only, so no IDCT!) of grayscale jpegs on a very limited embedded microprocessor.

These tools you have provided are incredibly useful!! THANK YOU!!
 Great news! Thanks for letting me know, Rob!
2010-04-27Puneeth
 Hi,
Great Post. Thank you.
2010-04-18sowmya
 Hi,
I have the standard jpeg huffman tables(2 of them,one ac and one dc because im working with grayscale images).Whats the first step in writing a code (in matlab)to do huffman encoding..
This is a part of my project.it'll be really greatl if u could help..
Thnx..
2010-04-14cana
 Hi, i'm still learn for jpeg compression and already try your JPEG Snoop, and try to make my own encoder, now i've a problem at the last step, that's about entropy coding..
can i get a source code about it ?

Thanks :)
2010-03-25james
 Hi,
I have been trying to decode huffman compressed jpeg files from a fax machine harddrive image, we do forensics investigation and sometimes are required to image a fax machine. So far I have not bee able to read the encoded jpegs, hopefully your tutorial will help.
Could I send you a jpeg file to see what you think.
Regards
James
 Sure, send me an example JPEG and I'll take a look.
2010-03-24Chris
 Great article. Thank you!
2010-03-18Sandrine
 Thanks a lot for this tutorial which truly helped me a lot. It's the best page I found on the web to explain JPEG. JPEG Snoop also prooves very useful
2010-03-16Ankit
 Hello Calvin,

I have a RAW data, it is compressed via differential Huffman coding, can this data be considered under the category of differnetial lossless JPEG compression. The thing is Adobe DNG uses TIFF, I need to compress the DNG file and the only possiblilty is by using lossless JPEG, unfortunetly the Huffman is runed over RGB data.

Can you atleast provide me the confirmation that lossless compression for RGB data is supported JPEG.
2010-02-16kd
 I used your app for testing my corrupted img which I get from my IP camera. Every app says Premature end of data segment and displays only a small part of image. I'd opened image with your app and IMAGE was displayed correctly and without any error printed.
Could you please help me to handle my problem?
 Hi kd -- JPEGsnoop was designed with a more robust JPEG decoder than other programs, and that is the reason why it may open fine in JPEGsnoop. If it works there, you may be able to recover it for use with other programs by "Export JPEG".
2010-02-15tz
 It took me a while to figure out how to unpack all the bits. jpegsnoop doesn't split the huffman tree from the lumiance value, so something like 0101 in the bitstream might be [01] [01] tree 01, Y -2.

I've been experimenting with generating JPEGs with just black and white pixels, and I figured out this as the missing piece. jpegsnoop could do a different color or something to split out the table and value in the full decode.

But for those who can't quite understand, here is my post on doing 8x8 squares in two levels at 3.5 pixels per bit or 3.0 pixels per bit:

http://harleyhacking.blogspot.com/2010/02/jpeg-huff-puff.html

This is probably the simplest example of something with an actual image (i.e. not a single black pixel). I will probably put the code up somewhere when I clean it up - the 8 bit codes version is at github from a link near the top of the post.

And note that because of the way it is coded, it does end up with two bits of overhead per bit. AC which is always 0, and 1 bit tree + 1 bit value minimum to go between 50% gray and white.

(I'm doing two-tone jpegs because EyeFi cards will only upload jpegs, and I want to use an embedded processor that doesn't have a lot of resources to generate text or barcodes).
2010-02-08Veeranjaneyulu Toka
 I have a couple of questions.

1. Can JPEG have Alpha blending?. if it can not, why does it so?

2. Can i achive cropping with JPEG image which has got Progressive compressive mode?

Thanks,
Veeru.
 Hi Veeru -- The standard JPEG does not support Alpha blending (like GIF or PNG). Theoretically, it may have been possible to support the transparency in another channel (ie. YCCA), but compression artifacts in an alpha channel would look very bad. Ideally, the alpha channel would be compressed with a much better quality (ie. lossless) so as to preserve the sharp edge transitions and flat constant sections, but doing so would greatly add to the file size. As for progressive mode and cropping, I'm not sure as I haven't spent much time looking into progressive files.
2010-01-31wacs5
 Thanks for your attention for my question at 2009-12-04

I have no idea at converse YUV 2 RGB.
for example, I have a YUV code (-127,0,0), then after add 128 to each component. we get (0,128,128)

using the Formulae

RGB=
101.402
1-0.34414-0.71414
11.7720
 * YUV= [179.4, 135.5, 226.8]

I just get the answer RGB=(179,136,227)

Can you get me a solve step with an example.
 Yes - I see that I made an error in the description of the last step. The level shift (+128) is required after the matrix calculation, not before. Therefore, the YCC input ranges should be [-128,+127] as they enter the formula shown. I have now updated the text in the JPEG Color Conversion page. Thanks for pointing this out!
2010-01-28chetan
 Hi , i am implementing JPEG decoder . I am done with Baseline DCT ( FFC0) . Now i want to implement Extended Sequential ( FFC1) (SOF1) with 8bpp only. I will be getting 4 AC tables and 4 DC tables from the bitstream . But in scan header , we will be passing only one of the AC and DC table ( totally 2 AC ( 1 each for chroma and luma) and 2 DC ) . So if we know which one will be used always by all the MCU's in a scan component . why to encode 4 Huffman tables . ?? Please tell me the use case of it .
2010-01-17Shadowhhl
 I really APPRECIATE this!! Thank!!!
2009-12-04wacs5
 Thanks for your introduce.

I have a question about YUV to RGB.
After Huffman decoding, we get Y of block1 = -128, block2 = +127
and U,V=0

I used the Formulae from http://www.impulseadventure.com/photo/jpeg-color-space.html

But I can not get the RGB in Block 1 and Block 2
(0,0,0)
(255,255,255)
 Hi there -- I have now added a comment into the color conversion page to indicate that the formula requires unsigned input values in the range (0..255). This means that your Y'CbCr input triple is now (0,128,128) and (255,128,128).
2009-11-04lewis
 Thanks from bottom of my heart for who creating this page!!
2009-11-02jinesh kumat
 thanks for this tutorial at last i got what i wanted. thank u very much
 Great! You're welcome.
2009-09-19Dave
 If I understand correctly after you have run the DCT you need to add 128 to all of the coefficients. So, if all the coeffiecients are 0 (the cb and cr in the example) then wouldn't they all end up being 128?
 If the Cb & Cr coefficients all zero then you are right in that when we convert from signed representation to unsigned, we'll need to add +128 (which gives us the midpoint of both components: Cb=128, Cr=128). The color conversion formula will take this positive range into account to produce the RGB triplet.
2009-09-15eddie
 Hi,
From your articles, I came to know that JPEG SOI marker is 0xFFD8 and DHT and etc markers. However, if I wanna decode the chroma subsampling, may I know what marker I should take note of so that I could extract and know the subsampling factor?

Thank you.
 The subsampling factors are defined within the SOF marker section. Following the number of image components (Nf) is a list of component entries, each with an identifier byte, a sampling factor byte (horizontal in upper 4-bits, vertical in lower 4-bits) and a quantization table select byte.
2009-07-16Ajaz H
 Nice!!!!!!!
 
2009-06-18Dan
 Calvin, thanks so much for these great articles!!!
2009-06-10Sebastian Ptak
 Hi Calvin
I am currently creating a decoder for DICOM Lossless JPEG format (JPEG Lossless, Non-Hierarchical, First-Order Prediction (Process 14 [Selection Value 1]) and i've stumbled upon something strange. When i try to decode the scan data sometimes i can't seem to find the code (almost like the scan data or huffman tables would be corrupt).
When i tried to open the extracted image in the source code from Cornell University it also said that the image data is corrupt. What is strange is that DICOM viewers read the image without any problems.

I just noticed that the bit array that couldn't be decoded start with 0xFF (the wrong values are 0xFFD2, 0xFFA9, 0xFF9D). Does that mean that the values are markers encoded in the scan? I thought that if a marker appears in the scan it should be bit shifted by appending 1-bits after the last code.
Do you have any idea what might be wrong? I'm fairly sure that i extracted the image fragment from DICOM correctly.

Here's a link to the image data:
http://uploading.com/files/C5Z2DMQX/1FRAME.html
And the errors seem to pop up at positions 21938, 80517 and 203364.
Any help would be appreciated:)
 Hi there Sebastian -- I have not yet experimented with JPEG Lossless decode, so I'm not able to test out your image decode to track down your Huffman decode issue. I have seen examples of other digital cameras that insert their own proprietary marker codes into the bitstream, so it is possible that these are indeed markers. I believe the markers are usually byte-aligned by padding with 1-bits; have you tried stripping out various bit alignments around these codes to see if you can resume decode OK? Sorry I'm not able to provide more of an answer. Perhaps someone else can comment with their experience in DICOM.
2009-05-22Gajanan Ambi
 Thanks a lot Calvin.
2009-05-22Gajanan Ambi
 Thanks a lot Calvin.
 Glad it's useful!
2009-05-04Rohit
 Hi Calvin,

I was successful in designing a parallel decoder for images with restart markers (as you have mentioned as well).
However, with images without RSI or with RSI not optimally positioned, I m facing problems. I was thinking I could huffman decode serially and parallelize the rest of the decode among 3-4 threads.
Then I received ur reply - "do a scan through the huffman codes, determining bit offsets for various vertical sections you hope to parallelize." This seems to be a similar approach at first look. Can you please elaborate on this point of yours? Particularly, is it possible to find bit offsets in the encoded stream? (Since the bitmap data would be encoded into 'variable' length H-codes)

Thanks
Rohit
 Hello Rohit -- As you have probably discovered, there is no easy way to determine the bit offsets within the encoded stream. Fortunately, the process only needs to perform the Huffman code tables searches and no more of the JPEG decoding process. Once the starting point offsets for each "segment" (of the image to parallelize) has been identified, you can then begin each of the parallel decoders and then merge the result.
2009-04-28Rohit
 Hi Calvin,

First of all, a great article! Thanks.

I've a doubt in the huffman-decoding stage. I'm basically trying to parallelize JPEG decoding. I realised in the process that Huffman decoding will be a bottleneck. But again I'm not sure. Hence I ask.
Is it possible to decode a huffman stream from a random location in the stream?
In particular, is it possible to split up the stream into, say,4 parts and get 4 threads to decode them in parallel?
And even if its possible, will it be more efficient than a single threaded operation.
Note - I've a multi processor machine to work with. So thread switching overhead isn't that big a deal.

Look forward to your opinions eagerly.

Thanks in advance,
Rohit
 Hi Rohit --

You'll quickly find that JPEG decoding is usually not an easy task to parallelize. The problem is that it is very difficult to deduce your pixel location within the Huffman bitstream, or even your starting bit alignment within the Huffman codes. If JPEG Restart Markers (RST) were encoded into the image, then the process can be parallelized much easier, but these markers are not commonly used.

That said, you might find some benefit to have one thread quickly do a scan through the huffman codes, determining bit offsets for various vertical sections you hope to parallelize. Then, proceed to do the decode in parallel. Lastly, you will have to adjust the YCC offsets for each of the parallel decodes to adjust for the YCC DC offset at each starting point (since the DC offsets are cumulative across the entire image).

Good luck, and please report back if you achieve some success with this process!
2009-04-05Sebastian
 Hi,
first of all thank you for this small guide, it really helps a lot!

I still have a question: In the end of this example you have absolute dc values -512 for MCU 0 and 508 for MCU 1. After dividing by the gain of the DCT we get -128 and +127, we should be the average luminance in the MCU. The next step would be the color-space conversion to RGB. But in between i seem to miss a step?
For the black MCU, Luminance should obviously be 0 before conversion:
(0,0,0)[RGB] -> (0,0,0)[YCbCr] != (-128, 0 , 0)[YCbCr]
Is there some sort of general shift (like add +128 on all values) or how does it work?
Thanks in advance ;)
 Yes. For final representation you will need to convert the signed range (centered at 0) to a range that has a center at the midpoint of the precision (eg. by adding +128).
2009-02-26Visakh
 Hi Calvin,
Great article. Especially the explanation showing the decoding of the scan data. Learned a lot. Thanks!!
 Thanks Visakh!
2008-12-01Brian Mearns
 Very nice article. Question about the Huffman tables shown though: Both of the AC tables show only a single entry with the longest length, which is non-optimal. For instance in Table 1, you have 1111 110 for 0A and 1111 1110 for 0B, where as B could also be encoded using 7 bits as 1111 111, and it would still be prefix free. This is actually a property of all optimum codes: the two least probable symbols always have the same length.

Thanks.
 Hi Brian -- I believe your question is along similar lines to that posted by Daniel on 2007-10-10. The ITU-T spec restricts one from using the all-1's pattern, presumably to future-proof the extension of larger codewords.
2008-11-14Nikhil
 hi
i m trying to encode a .jpg file given a raw image data, i dont want to use any image libraries. I m stuck up at the step of Huffman coding.
as written in above the first few bits represent the Huffman code. using this Huffman code we get the corresponding size eg 0A is 10, which mean that next 10 bits are useful which gave us an int which was -512 in case above.
in one of the example given the table contains FA, which means next 250 bits represent an int, how is it possible to have an image value to be 2^250?
I m sure that there could be some mistake on my side, plz help me to clarify this!!
if possible plz direct me to some links regarding JPEG specific Huffman coding...
thx
 Hi Nikhil --
It sounds like you are trying to decode an AC huffman code. The key point is that for AC huffman codes, you split the code into two parts: the run-length of zero coefficients, followed by the huffman code length. In other words, 0xFA is actually (15,10): a run of 15 zero coefficients, followed by a 10-bit huffman code.
2008-11-10Mongkoy
 Thank you for this wonderful article . I learned a lot thanks,
one question is it possible to Guess DHT (lossless table) given only the compressed image data? many thanks, Mongkoy
 Interesting question. In some situations, I think you probably can.

In many cases, the same DHT tables are generated each time by a particular camera model or JPEG compression software tool. This is because it is easier to use a predefined Huffman table than it is to calculate the optimal Huffman tree.

However, if the JPEG file was produced with optimized Huffman tables (eg. Photoshop with "Optimized" enabled), then it will be extremely hard to determine where the transitions are from one variable-length code (VLC) to the next. If you happened to figure out the list of VLC codes, you could then sort their frequency and perhaps determine the order within the DHT table (from most frequent to least), but there would be many challenges in carrying this out.
2008-10-26Tree
 Hi,

Thank you for learning your great tutorial.

I have some question. but I am poor at writing in English.

I beg you to forgive my writing.

Please, would you explain the process after huffman decoding in detail ?

1. Multiply MCU member by Quantization Table.
2. Inverse Discrete Cosine Transform
3. Convert Relative DC to Absolute DC.
4. Convert YCbCr to RGB.

Is that right?

and In third process, Is DC belong to only Luminance, or Chrominance element?
and In fourth process, Is YCbCr value between -128 and 127?

I want you to understand my poor writing and give me some hint. ^^;

please help me.
2008-10-06Rahul
 Hi Calvin,
First of all, I would like to thank you for such a wonderful article clearly explaining the decoding method in JPEG images.
Moving a step further, I would like to know about decoding in Progressive images, if at all ,they are different.
Particularly , I am confused about JPEG Images with SOF markers other than 0xFFC0.
Counting on your early reply... !!!
Thanks a lot in advance.
2008-09-25Xtreme Kommander
 Thanks for making this! It's been quite helpful! :-)

I do have a question though....what would be the best way to crop a JPEG image? Do you have any suggestions?

Thanks,
Xtreme Kommander
2008-09-24Xtreme Kommander
 Hello,

Very helpful tutorial! Congrats! I have a question though....

How would I go about cropping an image? I'm sure it's not too hard, but it would be helpful if you could give me some clues! :-)

Thanks,
Xtreme Kommander
2008-09-19Takis
 Thanks for this article! It makes JPEG a lot easier to understand! :-)

On remark though: I had the impression Table 1 was complete, but, I think it is missing one entry:
8 bits 11111 110 0B

With friendly regards,
Takis
 You're right, Takis! I have updated the table accordingly. Thanks for noticing this.
2008-09-18Daniel
 Hi, Calvin,
For a more realistic JPEG which contains ac component, could I use the following sequence to decode it:
1. look up ac table for run/size
2. if an eob was found, then fill the rest ac component with all 0's;
3. if not, recode the run, and look for size number of bits and then look up huffman ac encoding table for ac value.
4. compose run and ac value for output.
Am I correct? And what is the huffman ac encoding? Do all JPEF ac component share one single huffman ac encoding just like dc do?
And could you give me some hint on design a hardware huffman decoder? Could the reqirement "output one element at anygiven time" be satisfied?
Thank you!
2008-09-11Kaku
 Hi, Thanks for making such a great tuorial !
I have one question though, I have looked at various jpeg files opened in a hex editor. My impression was that FF DA was the start of scan flag not FF DA 00 0C. Also how can you tell where the actual scan data starts? (is it the 00 3F 00 - maybe?) - and one last question - what is the significance of the details that have been highlighted in green?
Sorry for asking so many questions but I cant seem to get the information anywhere else, JPEGS own documents are very hard to follow...
Thanks
2008-07-29Giri
 hi Calvin
I want to create a JPEG File buffer like malloc (not directly write into the file), but every bytes we are creating in runtime only, Iis there any way to predict the JPEG file buffer size before start the Encoding process by the relation of HEIGHT & WIDTH.

thks for reply
 Hi Giri -- Unfortunately, it is very difficult to predict the resulting compressed file size from height & width since you don't know how "compressible" the image will be. This will vary widely on a few factors: quantization table (compression level), image dimensions, complexity of image content and image noise. That said, you can start with some approximate estimates based on previous images or on more general assumptions about compression with a given quantization table.
2008-07-23Peter
 A thousand thanks for this great article!
2008-07-23Peter
 A thousand thanks for this great article!
2008-07-15Steffen G
 Hi Calvin,

I've been trying to write a video converter for one of those "MP4" players for which you only get Windows software (I'm a Unix guy)... I've had a hard time analyzing the file format of the videos the player would accept, and found that these are basically MJPEG with MP3 interleaved. Mission almost accomplished.
There's only one obstacle left: the JPEGs have to be encoded in a way that *only* Huffman tables with #0 are used. All software I could find would use #0 for Y, and #1 for Cb/Cr :( but at least the "standard" tables are used.
Any suggestion how to force usage of #0 tables?
I'm using libjpeg6b now but *anything* would be appreciated...
 Interesting project Steffen!

First off, I am less familiar with libjpeg since I wrote my own decoder, but having a quick look at the source code for the library, I believe you should be able to change the dc_tbl_no and ac_tbl_no parameters to 0 before doing any compression. If you look at jpeg_set_colorspace(), which is called by jpeg_set_defaults(), you'll see that the calls to SET_COMP default to using DHT tables 0 for Y and 1 for Cb & Cr. If you override the DHT table specification there, the rest of the compression may work as you're intending.

Please let me know if that helps! Cal.
2008-07-08Jiri
 Hello, Calvin

I like to thank you for this site and JPEGsnoop . I am working on implementation of steganographic content detector and your work save me a lot of time. Now I got stuck on Huffman code histogram stats ,could explane how to make it ? Becouse by my implementation I always get different stats from yours , I probably missed something , but I can't find what .

Thank you for your time ,have a nice day.
P.S. sorry for my english :)
 Sounds like an interesting program to write! If you can send me a link to it, that would be great.

The statistics that I'm collecting on the huffman codewords usage is fairly basic. I increment a count corresponding to each codeword each time that the decoder encounters the code in the bitstream. Perhaps you could give me an idea of what differences you're noticing?

Many thanks, Cal.
2008-06-28Abhishek
 hey Calvin !
... thanks for all ur gud work !

I was really messed up with the Huffman decoder in JPEG.
JPEG specs didnt helped my doubts clear ... though it was fine with huffman decoding itself, but implementing in JPEG was where i stuck ... THANKS a lot for all this koool stuff, i m clear now !
actually i m making a hardware JPEG decoder .. so needed this all.
I also saw Victor Lopez in the list ... kool ... he has indeed made that hardware JPEG coder and available on Opencores.org

i saw other sections of ur webpage too ... this makes me curious to know abt u ... what actually u do etc ... though its a kind of non relevant question ... but still !

So u r in india these days ... hw do u like the place .. kind of weird and different, happy people in tough condition :)
(i m from india too, but these days working in Tokyo )
 Great that it helped out!
(Private message sent)
2008-06-18sachin
 Hi very good info......i have one doubt......why don't you look for Y-DC EOB marker in above example....just like CR-DC..what happens if you can't find any value for Y_DC .....do u then look for its EOB or u just start looking for Y-AC
2008-06-18sachin
 Hey excellent page......I have one problem....
I had an similar image like above but with diff Q table it had data strings which I can post if u want.
The problem is that when I tried to decode it using its huffman table for Y-DC Y-Ac C-DC C-Ac tables with assuming the DC encoding table above which is standard I found that like it says to encode next 8 bits for Dc value but there are not 8 bits before EOI marker.
Can you tell me how to solve this problem means I don't find enough bits after number mentioned in th data code.

Also can you post the AC Encoding table as I the above example of yours uses only DC encoding values.

 

Leave a comment or suggestion for this page:

(Never Shown - Optional)