Ken Webster discusses the guts of JPEG compression:
- ). Discrete cosine transform (DCT)
- ). Quantization
- ). Huffman encoding
The DCT transforms a 2-dimensional array of pixel data into a 2-dimensional array (of equal size) of coefficients for different frequencies of cosine functions which, when scaled by the coefficients and summed, yeild the original pixel data. Many bright people have worked on efficient ways to do this transformation and thus to implement it all you need to do is a coupple of simple matrix multiplications on an 8x8 array of image data. Code libraries are available (I give a link below) which do the DCT and quantization together with just a few multiplications and additions.
Quantization simply consists of dividing the DCT coefficients by a number (the numbers chosen affect the image quality and the amount of compression) and then rounding the results to integers. It is done because most of the higher frequency DCT coefficients will typically be truncated to zeros and can then be represented with a simple run-length code. The combination of DCT and quantization allowing all of these zero coefficients to be represented by a simple run-length code is what produces the most compression.
Huffman encoding simply assigns shorter bit codes to the most frequently used numbers and longer bit codes to the least frequently used numbers (and was discussed in detail in earlier posts).
I have JPEG encoder and decoder C++ libraries posted here:
They came with a book titled "Compressed Image File Formats" by John Miano. The book gives a very good description of how JPEG (and PNG, GIF, etc.) works. Here's a link to the Amazon.com page describing it:
The README.TXT accompanying the library indicates that it is ok to redistribute the source as long as it is accompanied by the README.TXT and any modifications are documented. I have not modified the library. The README.TXT is available here:
The code that does the DCT and quantization is posted here:
The quantization tables are in this source file:
The Huffman coding is done by this code:
The C++ code that does the DCT uses floating point numbers. If you want a floating point library I have a good 64-bit float library available here:
I don't care how you use this code as long as you don't redistribute the source without giving me credit (link to my home page http://ken.webster.org/ for example).
Another option is to use scaled integer arithmetic. The results of the DCT are quantized and rounded to integers anyway so simply starting with the quantization coefficients pre-multiplied by a power of two (left shifted) and then right-shifting the results will work great. Just make sure your integers are wide enough to represent the largest possible intermediate result.
The Huffman coding source-code is by far the most complex but it doesn't use any complicated math, library functions, or resources specific to PC environments. It may take some time to convert it to PIC assembly but it looks like it is all quite do-able.
The code that ties everything together is here:
It has a lot of stuff you won't need because you aren't doing color images, adhering to the JFIF specifications, dynamically selecting image quality, etc. One routine you will want to look at is CreateQuantizationTables. It scales the standard quantization tables by a quality factor to set the amount of compression and lossyness. For an embedded application it will probably make the most sense to just pick a quality factor and generate the scaled table ahead of time and store the scaled table in ROM.
|file: /Techref/datafile/jpeg/guts.htm, 5KB, , updated: 2006/12/8 13:45, local time: 2018/10/20 09:10,
|©2018 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?|
<A HREF="http://www.piclist.com/techref/datafile/jpeg/guts.htm"> Guts of JPEG compression</A>
|Did you find what you needed?|
PICList 2018 contributors:
o List host: MIT, Site host massmind.org, Top posters @20181020 RussellMc, Van Horn, David, Sean Breheny, David C Brown, Isaac M. Bavaresco, Neil, Bob Blick, Harold Hallikainen, John Gardner, AB Pearce - UKRI STFC,
* Page Editors: James Newton, David Cary, and YOU!
* Roman Black of Black Robotics donates from sales of Linistep stepper controller kits.
* Ashley Roll of Digital Nemesis donates from sales of RCL-1 RS232 to TTL converters.
* Monthly Subscribers: Gregg Rew. on-going support is MOST appreciated!
* Contributors: Richard Seriani, Sr.
Welcome to www.piclist.com!