Return to Digital Photography Articles

What is an Optimized JPEG?

What is an Optimized JPEG?

An optimized JPEG is simply a JPEG file that includes custom Huffman tables that were created after statistical analysis of the image's unique content.

What is Huffman Coding?

The huffman coding scheme used in JPEG compression reduces file size further by replacing the fixed-size (eg. 12-bit) codes with variable-length codes (1-16 bit). The hope is that on average, the replacement codes will add up to fewer bits than the original. If, on average, 10% fewer bits are needed to store the quantized DCT coefficients, then this will directly translate into 10% file size reduction. The difficult part is deciding which codes to replace with which variable-length bit-strings. The Huffman Tables define these mappings, and are stored inside every JPG image file. A separate huffman table is required for each of the following four components: luminance DC component, luminance AC components, chrominance DC component and chrominance AC components.

The example photo used for Optimization

How much reduction in file size?

The following shows an example of the file size reductions that are possible after using an optimized huffman table instead of the standard tables. A 6 megapixel digital photo (from a Canon 10d, #1) was opened up in Photoshop and resaved via both Save As (#3, #4) and Save for the Web (#5, #6). The original photo was also passed into jpegtran to perform a lossless huffman optimization step (Photoshop cannot do this without applying its own quantization tables and hence it isn't lossless).

In the two Photoshop tests, both Optimized and Standard modes were used. Both files in each of the three pairs of comparisons have identical quantization tables (meaning that the JPEG compression quality is the same). In other words, #1 & #2 have the same table, #3 & #4 have the same table and #5 & #6 have the same tables. However, each group (1+2, 3+4 and 5+6) will have different tables.

File Image Mode Total SizeOverhead Scan Data Savings
1 Canon 10d Original 2,212,302 9,822 2,202,480 -
2 Canon 10d (jpegtran) Optimized 2,150,174 403 2,149,771 2.4%
3 Photoshop CS2 - Save As - Quality 11 Standard 1,999,226 31,031 1,968,195 -
4 Photoshop CS2 - Save As - Quality 11 Optimized 1,872,068 30,774 1,841,294 6.4%
5 Photoshop CS2 - Save For Web - Quality 85 Standard 1,970,500 641 1,969,859 -
6 Photoshop CS2 - Save For Web - Quality 85 Optimized 1,836,522 410 1,836,112 6.8%

 

As is shown by the above results, the file size savings over and above the standard tables (which are used by File #1, the original photo) are not particularly great. A lot of extra computation is required to devise this optimum table, all for the sake of 2-6 % savings in file size.

Does JPEG Optimization affect Image Quality?

No! The huffman table optimization is a lossless (reversible) process that has absolutely no effect on the resulting image quality. If one has the option, it is almost always best to enable JPEG optimization. The extra file size savings can't hurt. However, as it may potentially reduce compatibility with some bad JPEG decoders, this may be enough of a reason for you to disable it.

Are JPEG images from Digital Cameras Optimized?

No! It would appear safe to say that every single JPEG photo generated by a recent digital camera uses the "typical" huffman tables provided in the JPEG ITU-T81 standard (tables K3, K4, K5 and K6 and reproduced below). I have confirmed this to be the case after examining photos from over a hundred digital cameras, from high-end full-frame dSLRs to point & shoot digicams.

Why don't digital cameras optimize their JPEG photos?

As you will see later in the section detailing how the optimization is done, generating the optimized huffman tables is quite laborious. It requires considerable counting, sorting and reorganization to produce an optimum result. Most high-end digital SLRs probably have the computing power to process this for every photo, but the extra complexity and performance penalty are probably not outweighed by the slight reduction in average file sizes (when using the standard's suggested Huffman tables). For a 6% file size savings, the additional hardware may not be justifiable.

While optimizing JPG images is likely not worth implementing in digital camera hardware, it certainly is a viable option for any photo editing computer program. The amount of time taken to compute the tables is insignificant when compared with the average user's response time after initiating a save operation!

Are Quantization Tables ever Optimized?

When you select optimized JPEG in Photoshop or other photo editing programs you are almost certainly not getting any optimization (or change) of the quantization tables. Nearly every program includes some predefined quantization tables that are used (and a scaling thereof), depending on the user's desired quality setting. Trying to calculate an optimum quantization table (given targets in file size and knowledge about the characteristics of the human visual system) would be very difficult. I believe this has been the focus of a few published theses, but not adopted in any popular computer software.

How to Calculate an Optimized Huffman Table

NOTE: The following sections are somewhat complicated, so only read on if you are truly curious about the details!

There are many ways of calculating the optimized JPG's huffman table, but one of the simplest methods is to do the following. First, we start with the entropy coding of code-words:

  • Calculate the quantized DCT coefficients for all MCU blocks in the image, repeating for the Y, Cb and Cr components
  • Reorder the coefficients using the zig-zag sequence starting with the DC coefficient and then all 63 AC coefficients.
  • Replace any continuous sequence of zeros with an appropriate code-word whose first nybble defines the number of zeros (i.e. from 0-15). The second nybble defines the number of bits used to represent the bit-size of the signed coefficient that follows the run of zeros (from 1-11). For example, to encode a run of 7 zeros and then the AC coefficient +35, we would select the code word 76 (run=7 zeros, size=6 bits). Note that the calculation of the size field (e.g. 6) from the coefficient value (e.g. +35) is described by Table 5 "Huffman DC Value Encoding" in the Huffman Encoding Tutorial page.
  • Replace the DC coefficient of each MCU with the huffman-coded size field ("category"), followed by the value itself. For example, if the DC value were -13, then the code word would be 04 followed by the bit-string "0010". The size field is defined by Table 5 as in the previous step. For this particular example, one would look up -13 in Table 5 and recognize that 4 bits are required to encode any value in the range -15...-8,8...15. Looking at the sequence, one then determines that the "additional bits" required to define -13 is the binary string 0010 (0000 is -15, 0001 is -14, 0010 is -13, etc.)

The above steps simply create the code-words in preparation for optimization. Now, we can perform the optimization. The following is only a very brief summary of the huffman algorithm, so it would be worth looking at other useful references first (e.g. ASCII string into Huffman codes, or any other general huffman coding tutorials).

  • Separately for each of the four sets of image data (code for the DC luminance of each block, code for the DC chrominance of each block, codes for the AC luminance of each block and codes for the AC chrominance for each block), count the number of times that each code word is used.
  • Sort the code-word list (e.g. for DC luminance) in order from most frequent to least frequent.
  • Select two least-frequent codes and add them to the bottom leaf nodes of a binary tree. Record the frequency of each code. Above this pair, create a node with a value equal to the sum of the two nodes added below.
  • Again, find the two least-frequent codes (with the new combined nodes replacing the two component nodes). Group these two and add the frequencies together.
  • Repeat until all codes have been paired up into a binary tree with a root node equal to 1 (i.e. 100% frequency).
  • Assign binary 0 and 1 to each branch of the tree from top to bottom. Each node will have a variable-length bitstring associated with it, which is simply the concatenation of the binary value of each path taken from the root node.
  • Traversing the binary tree starting with level 1, from left-to-right, read out each code word and add to the DHT (huffman table definition).

Photoshop and Huffman Tables

Photoshop Save As provides three JPEG save modes: Baseline Standard, Baseline Optimized and Progressive. Photoshop's Save for Web provides either Optimized or not Optimized. For the purposes of this discussion, Progressive mode will be ignored. Save As defaults to no Optimzation, whereas Save for Web defaults to Optimization enabled.

Compatibility of Optimized JPEG

According to Adobe's documentation with Photoshop:

"Optimized: Creates an enhanced JPEG with a slightly smaller file size. The Optimized JPEG format is recommended for maximum file compression; however, some older browsers do not support this feature."

It is highly unlikely that you will ever run into any problems using "optimized" JPEGs. Optimized JPEGs don't use an extra feature, nor is there really anything different except that they have written a huffman table that uses different values than the most common tables in use.

Any standards-compliant JPEG decoder must parse the quantization and huffman tables in the file so there should never be an issue with optimized versus standard. That said, it seems that there may have been a bug in one of the earliest (i.e. 10 years ago) web browsers that did make an assumption about the huffman tables (probably never bothered to decode the DHT entries) and hence the incompatibility. It is almost improbable that anyone would be using such a web browser today!

Optimization according to JPEG Quality

It is interesting to note that in Photoshop CS2, the Save As for the Baseline Standard operation uses different huffman tables depending on the quality level setting you choose. None of these tables match the huffman tables of the JPEG standard. Some academic research has shown that the frequency distribution of huffman codes differs predictably according to the JPEG compression quality (defined by the quantization tables). This is essentially a half-way optimization -- using tables that are optimized for the compression quality but not the image content itself. As this involves using "non-standard" huffman tables, I see very little point in using Baseline Standard over Baseline Optimized.

Photoshop Quality Levels
with same Huffman Table
DC Lum
# codes
DC Chr
# codes
AC Lum
# codes
AC Chr
# codes
0, 1, 2 12 12 98 * 91 *
3, 4, 5 12 12 114 * 111 *
6, 7, 8, 9, 10 12 12 162 162
11 12 12 162 162
12 12 12 162 162

 

An interesting detail about the use of tables tailored per quality level is shown in the number of code words in the huffman tables written into the JPEG files from Photoshop. For quality levels 0 through 5 (relatively poor quality), not all code words have been included in the huffman tables. Therefore, the expectation is that saving images in Photoshop with these quality levels (by using the built-in quantization tables), it would be impossible to generate the Run+Size AC codewords that were left out. 51 of 162 possible code words are missing from the DHT tables when saving at quality level 5.

In fact, what you may notice is that (for example, quality level 3-5), the AC code-words only have a maximum "size" field of 7 bits, not 10 bits (maximum code word is 0xF7 not 0xFA). This would imply that it is impossible to have a quantized AC DCT coefficient greater than +/- 127.

IrfanView and Huffman Table Optimization

IrfanView can perform lossless re-optimization of a JPEG photo by selecting Option->JPG Lossless Operations menu option, then choosing None for Transformations and enable the Optimize JPG File checkbox. In doing so, one will achieve exactly the same optimization performance (and tables) as what you would get through the IJG utilities such as jpegtran.

By default, IrfanView saves all images with huffman table optimization enabled. There doesn't appear to be any way to save with the standard non-optimized tables -- and realistically, one shouldn't need to anyway.

Note about DHT Ordering

For some reason, the newer Canon dSLR and Point & Shoot digicams store the huffman tables in a different order than all other digital cameras and the older Canon models. I have no idea why this was changed. The last models to use the more traditional ordering (DC-Luminance, DC-Chrominance, AC-Luminance, AC-Chrominance) within each model series are: Canon 10d, 300d, A70, G6 Pro1, S40, etc. All newer models instantiate the huffman tables in the order DC-Luminance, AC-Luminance, DC-Chrominance, AC-Chrominance. This should have absolutely no impact on the image.

Standard Huffman Tables

The following tables are provided in the JPEG standard / specification as examples of "typical" huffman tables. They were apparently generated from "the average statistics of a large set of video images with 8-bit precision". Presumably, these will provide a reasonably close approximation to the compression performance of a true custom-optimized table for the majority of photographic content. The advantage of using these tables is that no compute-intensive second-pass analysis would then be required prior to encoding into the JPEG file format.

You will note that the standard huffman tables provide lookups for all possible codeword bytes. In the DC tables, the first nybble is always 0, and the size field can only be from 0 to 11 (0x0 to 0xB). Therefore, codewords will run from x00 to x0B. Codeword x00 is a special value that basically indicates the end of block (i.e. no values). For the DC entry this simply means that there is no change in value from the previous block (MCU). So, the standard huffman tables for luminance and chrominance both include all 12 possible DC code words.

For the AC tables, the first nybble encodes the run-length of zeros that precede the non-zero quantized DCT coefficient. This can be from 0 to 15 (0x0 to 0xF). The second nybble in the code word indicate the size in bits of the non-zero coefficient that followed the run of zeros. This can be from 1 to 10 (0x1 to 0xA). Together, this would give 16 x 10 = 160 possible code words. However, there are two additional codewords that are used in describing the AC scan entries: 0x00 and 0xF0. x00 represents an End of Block (EOB), which indicates that there are no more non-zero AC coefficients in this component, and that the decoder/encoder will move on to the next component. xF0 represents a Zero Run Length (ZRL) which indicates that there was a run of > 15 zeros. This codeword represents a run of 16 zeros, and will be followed by another codeword that indicates another ZRL or a normal run + size codeword. So, there are in total 162 possible AC code words. The standard huffman AC tables include all 162.

Standard DC Luminance Huffman Table
Code Length (bits)Code Words
(Size or Category)
200
3 01 02 03 04 05
4 06
5 07
6 08
7 09
8 0A
9 0B
Total number of code words in table: 12

 

Standard DC Chrominance Huffman Table
Code Length (bits)Code Words
(Size or Category)
2 00 01 02
3 03
4 04
5 05
6 06
7 07
8 08
9 09
10 0A
11 0B
Total number of code words in table: 12

 

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


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

Optimized Huffman Tables

In contrast to the above tables that are provided in the ITU-T standard, the following is an example of the huffman tables used by Photoshop CS2 when optimization is enabled for an image from a 6 megapixel dSLR.

When comparing this to the non-optimized tables, you'll note a few differences. Most importantly: fewer codewords are available. Not all combinations of runs and AC values are used. A few observations you might notice:

  • For the DC Chrominance table: there are no 0A or 0B code words. This indicates that the source photograph did not have any two adjacent MCUs (block) with extreme 10 or 11-bit swings in average color value.
  • For the DC Luminance table, the standard table places the 00 code word (marking the End of Block) with a 2-bit value. While this may be optimum for encoding images with wide areas of constant luminance (e.g. perfect white background), this characteristic is not prevalent in the example photo (shown at the top of this page). Instead, the EOB code is assigned to a 5-bit string.

Overall, there are fewer entries in the tables, and on average the entries consume fewer bits to encode. Therefore, the end result is a more efficient representation of the code words in the final JPEG file (meaning a smaller file size). The following tables were derived from a recoding of the JPEG photo (from above) by using jpegtran's lossless optimization method. This method will preserve the original image content and quantization tables, allowing us to isolate the effects of huffman table optimization.

You will note that the number of code words in each table (besides the DC luminance) don't include all possible codewords. This is because the example photo didn't need to use these run+size combinations and so they could be eliminated. By eliminating these codes, other codewords could occupy shorter variable-length codes and lead to decreased file size.

Optimized example of DC Luminance Huffman Table
Code Length (bits)Code Words
(Size or Category)
2 03 04
3 02 05
4 01 06 07
5 00
6 08
7 09
8 0A
9 0B
Total number of code words in table: 12 out of a possible 12

 

Optimized example of DC Chrominance Huffman Table
Code Length (bits)Code Words
(Size or Category)
2 02 03 04
3 01
4 05
5 00
6 06
7 07
8 08
9 09
Total number of code words in table: 10 out of a possible 12

 

Optimized example of AC Luminance Huffman Table
Code Length (bits)Code Words
(Run / Size)
2 01
3 11 02 03
4 00 21
5 31 41 12 04
6 51 61 71 05
7 81 22 13 06
8 91 A1 B1 07
9 F0 C1 D1 32 14
10 E1 F1 42 23
11 52 08
12 15
13 62 33 24
15 09
16 72 16 82 43 17 92 A2 53 34 25 0A B2 C2 D2 63 44
35 18 F2 73 26
Total number of code words in table: 63 out of a possible 162

 

Optimized example of AC Chrominance Huffman Table
Code Length (bits)Code Words
(Run / Size)
2 00 01
3 11 02
4 31 03
5 21 12
6 41 51
7 13
8 61 22 32 04
9 71
10 05
11 F0 81 91 A1 B1 42 14
12 E1 52 23 06
13 C1 D1
14 F1
15 62 33
16 15 43 07 72 24 16 82
Total number of code words in table: 44 out of a possible 162

 


Reader's Comments:

Please leave your comments or suggestions below!
2017-04-10Ron Bates
 Very nice guide and explanation. I started informing myself a bit about file formats, and I read about jpeg from this ... but couldn't understand some difference, so thank you for explaining the difference with compressed jpeg and how it works.
2016-12-23David T
 Thanks so much for all your helpful references which have helped me make a thumbnail program (mostly just for fun!). I noticed that as I was encoding the JPEGs, I noticed that if I encoded a DHT resulting in one code of all 1's (which should be allowed, and results from the natural Huffman coding), common decoders such as Chrome would fail to read it. For example, this table fails:

length 1: 00 (0)
length 2: 01 (10)
length 3: 02 (110) 03 (111)

whereas this table does fine:

length 1: 00 (0)
length 2: 01 (10)
length 3: 02 (110)
length 4: 03 (1110)

I can't find any documentation of this fact, even on your page, but I wondered if you had come across it since your optimized tables all seem compliant.
 The restriction for all-1s comes from Annex C in the ITU T.81 standard:
the codes shall be generated such that the all-1-bits code word of any length is reserved as a prefix for longer code words

Given the above, defining an all-1s code could lead to ambiguity upon decode.
2016-09-17Nina Cording
 One funny side effect of un-optimized huffman codes in JPGs is that they're wonderfully suited for base64-encoded data-URLs.
I have made a utility to use JPGs to store lossy compressed transparent images.
I was shocked to find out, that, for very simple images with large empty areas, there was a lot of repitition in the base64 code of the JPG. Since you mentioned that the huffman table is 12 bits, this may fit very well into the 6-bitness of base64.
If you now use these base-64 data-urls inline in css or html files (or svg and tell the server to gzip them on transfer), the LZW will reduce their size dramatically.
Transparent PNG > SVG
 Nina -- that's a really interesting finding. Thanks for sharing this!
2015-10-25Rin
 Hi.
How much precentage does huffman coding compress data if we use standard tables, and count out the effect of encoding the zero run length ? It is my understanding that this process just replaces a byte with a bit string and not necessary fewer than 8 bits. I'm implementing jpeg compression for microcontroller and wondering if it's really worth it to include those lengthy lookup table. If it's just reduce the number of zero then I can do it with a few lines of code.
 When encoding a 24-bit image, a uncompressed 8x8 pixel block theoretically contains 192 bytes of image data. You are right that the huffman coding scheme can result in codes that are greater than 8 bits in length, however the huffman coding doesn't actually compress bytes of input data. Instead, after we have converted the 8x8 pixel block into a frequency-domain representation and reduced complexity through quantization, we are usually left with a small number of values to compress/encode. For these "values", small changes from neighboring pixels can be represented by very short compressed codes (eg. 4 or more bits). Since the majority of the image deltas map to these frequently-used short codes, we actually get significant compression savings. The net result is that the 192 byte input image block may be compressed to ~30 bytes.
2014-04-28Stanley
 Hello! and thanks for your excellent site. I was wondering, did you ever put all typical JPEG tables in your site? and if not, were can i find them. I tried everywhere but no results!

thanks again!
 Hi Stanley -- thanks! When you say "all typical JPEG tables", do you mean ones that are found in common digicams or software encoders? I have posted a subset of ones on JPEG quantization tables but this is only a small fraction. I have seen tens of thousands of different tables / signatures, so it may be a little impractical to show them all :)
2014-04-08PanYumin
 Reply to "2012-09-12 JC".
"I asked why we don't exhaust 101, 110 before tuning into 1010? But as, for example, you've used 101 for 3 bits, 1010 can not be used in the table anymore due to JPEG huffman coding rules, so that you saved for 101 in 3-bit coding, but you lose a lot of opportunities in 4-bit coding, as 1010 and 1011 are no longer valid to be used."
I think you misused "101" and "110".
2013-09-13cosimo
 The codeword xF0 (the ZRL) which indicates that there was a run of > 15 zeros. This codeword represents a run of 15 zeros.

I think the xF0 should represent 16 zeros? That means "a runlength of 15 zeros is followed by another zero still".
 I think you're right... thanks for the correction!
2012-09-25JC
 Forget to mention about the sub-optimization of the longer huffman codes.

As the occuring freq. of those long codes are extremely low, so although the sub-optimization, the effect is really really really small. People just don't care.
2012-09-25JC
 I think I've figured out the answer to the question I raised in my previous post on "2012-09-12".

The huffman code are actually generated in a huffman binary tree, which ensures the optimal codes to be generated. Today, the "usual" (or most) code generation method follows the Annex K of the JPEG spec, which employs a sub-optimal method to generating the codes. And the longer codes in the optimized table suffer more from the sub-optimization, according to libjpeg (http://libjpeg.cvs.sourceforge.net/viewvc/libjpeg/libjpeg/) implementation jchuff.c function jpeg_gen_optimal_table():

"
695 * The JPEG standard requires Huffman codes to be no more than 16 bits long.
696 * If some symbols have a very small but nonzero probability, the Huffman tree
697 * must be adjusted to meet the code length restriction. We currently use
698 * the adjustment method suggested in JPEG section K.2. This method is *not*
699 * optimal; it may not choose the best possible limited-length code. But
700 * typically only very-low-frequency symbols will be given less-than-optimal
701 * lengths, so the code is almost optimal. Experimental comparisons against
702 * an optimal limited-length-code algorithm indicate that the difference is
703 * microscopic --- usually less than a hundredth of a percent of total size.
704 * So the extra complexity of an optimal algorithm doesn't seem worthwhile.
705 */
"

I didn't go into the maths details (I'm too dumb to understand the details). Taking one example can partly explains that the question I raised was a stupid question for shorter huffman codes in the table.

huff_code
00 = 01
01 = 01
100 = 11
1010 = 00 (EOB)
...

I asked why we don't exhaust 101, 110 before tuning into 1010? But as, for example, you've used 110 for 3 bits, 1010 can not be used in the table anymore due to JPEG huffman coding rules, so that you saved for 110 in 3-bit coding, but you lose a lot of opportunities in 4-bit coding, as 1010 and 1011 are no longer valid to be used.

Forget to mention about the sub-optimization of the longer huffman codes.

As the occuring freq. of those long codes are extremely low, so although the sub-optimization, the effect is really really really small. People just don't care.
 Fantastic! Thank you very much for digging this out. The explanation makes sense. I had overlooked the fact that the JPEG "optimzation" is sub-optimal.
 
2012-09-15Pranav
 Thank you so much for pointing about Irfanview's ability to use Huffman tables for lossless jpeg compression. I have been looking for a way to compress images before uploading to my wordpress blog.
2012-09-12JC
 Hi, one thing I don't fully understand. Taking this optimized AC table as example.

Optimized example of AC Luminance Huffman Table
Code Length (bits)	Code Words (Run / Size)
2	01
3	11 02 03
4	00 21
5	31 41 12 04
6	51 61 71 05
7	81 22 13 06
8	91 A1 B1 07
9	F0 C1 D1 32 14
10	E1 F1 42 23
11	52 08
12	15
13	62 33 24
15	09
16	72 16 82 43 17 92 A2 53 34 25 0A B2 C2 D2 63 44
35 18 F2 73 26

Since, if we want, we can still add more 15-bit huffman code before turning to 16-bit codes, why we don't leverage that but turning to 16-bit that soon? Also, < 15 bit huffman codes are not fully filled yet. Why is that?

As whatever possibility a 16-bit huffman code represents, it always gonna use 1-bit more if it was represented by a 15-bit huffman code?
 Excellent question, JC! Off the top of my head, I can't think of an obvious reason why the other codewords weren't shifted to shorter bit strings. If you do come across the answer, please post back here as I would be most interested.
2010-06-02Francois
 Hello,

Do you know the % oj the jpeg files, on the web for example, with non standard Huffman tables ?
2010-03-03ron
 Hi, found your articles useful in learning about JPEG Huffman encoding. Regarding Huffman tree formation, it might be useful to the novice to explicitly point out the tree formation rules that for a given bit-size the codes are listed in the DHT left to right and top to bottom in decending order of frequency, and that the lower frequency pair member of a leaf is placed to the left, and that the left branch is zero and the right is one. Thanks for the articles, Ron.
 Thanks Ron!
2010-02-02Moti
 How the progressive spectral selection is encoded? and what will be the impact of error in the file?
2009-07-12wim vanhauwaert
 I think I have found the answer to one of my questions

Because of the fact that different lengths (from 1 to 10) are allowed in the case of the 10 bit representation it is possible to encode (almost) 11 bits.
the number of representations is S= 2 (length 1) + 2^2 (length 2) + ...+ 2^10 (length 10)
This equals to S=2S-S=(2^2+2^3+...+2^10+2^11)-
(2^1+2^2+...+2^9+2^10)=2^11-2
This is alright because we have to decode a non zero number
 Exactly! The zero number (what would have been the 2^0 term in your sum) is instead encoded by the RRRR bits, if you consider the codeword byte RRRRSSSS (as defined by the ITU-T standard).
2009-06-28wim vanhauwaert
 Congratulations on your beautiful website!!

[1] The JPEG Still Picture Compression Standard
by Gregory K. Wallace, Article found on the internet

quote from [1] p11
A numerical analysis of the 8x8 FDCT equation shows
that, if the 64 point (8x8 block) input signal contains
N-bit integers, then the nonfractional part of the output
numbers (DCT coefficients) can grow by at most 3 bits.
This is also the largest possible size of a quantized
DCT coefficient when its quantizer step size has
integer value.

[2] http://www.impulseadventure.com/photo/optimized-jpeg.html

quote from [2]
For the AC tables, the first nybble encodes the run-length
of zeros that precede the non-zero quantized DCT
coefficient. This can be from 0 to 15 (0x0 to 0xF).
The SECOND NYBBLE in the code word indicate the size
in bits of the non-zero coefficient that followed the
run of zeros. THIS CAN BE FROM 1 TO 10 (0x1 to 0xA).
Together, this would give 16 x 10 = 160 possible code
words. However, there are two additional codewords
that are used in describing the AC scan entries:
0x00 and 0xF0. x00 represents an End of Block (EOB),
which indicates that there are no more non-zero AC
coefficients in this component, and that the
decoder/encoder will move on to the next component.
xF0 represents a Zero Run Length (ZRL) which
indicates that there was a run of > 15 zeros.
This codeword represents a run of 15 zeros, and
will be followed by another codeword that
indicates another ZRL or a normal run + size
codeword. So, there are in total 162 possible
AC code words. The standard huffman AC tables
include all 162.

Question:
Is it possible that those quotes contradict one another?
Because in [2] the maximum number of bits is 0xA (=10)
while according to [1] we are working with bytes
(8 bits) that can get three bits longer which means
11 bits. It is either 10 bits or 11 bits but which
one is right? I would also like to request a reference
for the claim of [1] Thank you very much for reading this
 Great question, wim! See my response to your question posted on 07/12.
2009-05-12Ravi
 Hi,
I need to change the huffman table (i need to add one more EOB code to the table). For this what i need to do?

based on your articles what i came to know is that i need to add in code length and code word. am i correct? if yes where can i add these two?
Thank you very much for your great articles.
 Usually, each Huffman table only has a single EOB code defined -- it seems a bit odd to add another EOB (why?). Adding another EOB would mean finding an unused bitstring, which could present a challenge, with a codeword value of 00. You would then need to sort the bitstrings (as defined by the ITU-T standard) to arrange in the necessary sequence order for the JFIF DHT.
2008-11-16chintito
 About this comment: It is highly unlikely that you will ever run into any problems using "optimized" JPEGs. Just to let you know I cannot view optimized jpegs in my cell phone, some MP4 players and a digital photo frame I just bought. Therefore, that comment is not accurate. Regards.
 Thanks for sharing your observations about this point. It is very strange that the JPEG decoders in these devices have trouble with optimized JPEGs as there is very little that differentiates it from an "un-optimized" JPEG. The potential issues I can imagine being responsible for this: 1) JPEG decoder had hardcoded the huffman tables (I would be very surprised if this was the case) or 2) JPEG decoder can't handle the shorter DHT (eg. missing codes, etc.)

To rule out 1, one could try to see if the hardware decoder was able to view images that had non-standard huffman tables. Most digital cameras use the same huffman table, but one could try to locate one (eg. via JPEGsnoop) that uses a different table (it wouldn't be "optimized", however, as most digicams do not do any Huffman optimization).
2008-09-16saba
 excellent job! really informative.....

i want to work on this as " optimal binary search tree and implementation of huffman coding" and i need ur help when i proceed. so will u help me in this regard???????
2008-03-23jpgcurious
 I use the jpegtran -optimize all the time. I have the following question: Does jpegtran -optimize result in the theoretical smallest possible file that is still compatible with a standard jpeg decoder? Or is the output just one of many highly optimized possibilities? A "perfect" exhaustive search for huffman encoding that results in the absolute minimal jpeg size could be worth it for many web applications.
 Great question. The jpegtran -optimize mode should result in the smallest file. It does this by a two-pass process. The first pass collects statistics about how frequently each symbol is used. Then, it constructs a huffman tree that is based upon the frequency distribution of each code symbol, not an exhaustive search. I don't see how this could be refined much further, although extremely slight variations in resulting performance may be possible. So long a the JPEG decoder can read the embedded huffman tables (DHT), there should be no incompatibilities (very early web browsers might have hardcoded the DHT for some reason, but I have not seen any definitive proof).

If you run an optimized JPEG through JPEGsnoop, you can report out the frequency distribution of the different huffman codes. This will show you how well the optimization worked. Note that you'll need to compare all DHT tables at once (as it is the combination of all of these that dictates overall compression performance).

For example, I ran a standard JPEG photo through jpegtran -optimize and get the following results (trimmed):
  Compression stats:
    Compression Ratio: 10.84:1
    Bits per pixel:     2.21:1

  Huffman code histogram stats:
    Huffman Table: (Dest ID: 0, Class: DC)
      # codes of length 01 bits:        0 (  0%)
      # codes of length 02 bits:    27069 ( 22%)
      # codes of length 03 bits:    47782 ( 38%)
      # codes of length 04 bits:    42360 ( 34%)
      # codes of length 05 bits:     5400 (  4%)
      # codes of length 06 bits:     2122 (  2%)
      ...

    Huffman Table: (Dest ID: 1, Class: DC)
      # codes of length 01 bits:        0 (  0%)
      # codes of length 02 bits:    88201 ( 71%)
      # codes of length 03 bits:    15300 ( 12%)
      # codes of length 04 bits:    11205 (  9%)
      # codes of length 05 bits:     7626 (  6%)
      # codes of length 06 bits:     2381 (  2%)
      ...

    Huffman Table: (Dest ID: 0, Class: AC)
      # codes of length 01 bits:        0 (  0%)
      # codes of length 02 bits:  1176666 ( 47%)
      # codes of length 03 bits:   252266 ( 10%)
      # codes of length 04 bits:   355289 ( 14%)
      # codes of length 05 bits:   381904 ( 15%)
      # codes of length 06 bits:   173519 (  7%)
      ...

    Huffman Table: (Dest ID: 1, Class: AC)
      # codes of length 01 bits:        0 (  0%)
      # codes of length 02 bits:   320855 ( 53%)
      # codes of length 03 bits:   143907 ( 24%)
      # codes of length 04 bits:    62023 ( 10%)
      # codes of length 05 bits:    33520 (  6%)
      # codes of length 06 bits:    19568 (  3%)
      # codes of length 07 bits:     4956 (  1%)
      # codes of length 08 bits:    11638 (  2%)
      # codes of length 09 bits:     3126 (  1%)
      ...
You'll see that in most cases the optimization has produced a selection of shorter code symbols, which will produce smaller overall files. For more details in how the huffman tree is generated, have a look at the htest_one_block function call in IJG's jchuff.c.
2007-06-28mark cox
 The last models to use the more traditional ordering (DC-Luminance, AC-Luminance, DC-Chrominance, AC-Chrominance) within each model series are: Canon 10d, 300d, A70, G6 Pro1, S40, etc. All newer models instantiate the huffman tables in the order DC-Luminance, AC-Luminance, DC-Chrominance, AC-Chrominance.

The paragraph above lists the same order, not different order.
 Fixed. Thanks!

 


Leave a comment or suggestion for this page:

(Never Shown - Optional)
 

Visits!