Ken Webster discusses the guts of JPEG compression:

  1. ). Discrete cosine transform (DCT)
  2. ). Quantization
  3. ). 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:

http://kdsl32.dnvr.uswest.net/cgi-bin/tl.exe/JPEG%20library

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:

http://www.amazon.com/exec/obidos/ASIN/0201604434/kenwebstershomep

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:

http://kdsl32.dnvr.uswest.net/cgi-bin/tl.exe/JPEG%20library/README.TXT

The code that does the DCT and quantization is posted here:

http://kdsl32.dnvr.uswest.net/cgi-bin/tl.exe/JPEG%20library/jpendu.cpp

The quantization tables are in this source file:

http://kdsl32.dnvr.uswest.net/cgi-bin/tl.exe/JPEG%20library/jpenquan.cpp

The Huffman coding is done by this code:

http://kdsl32.dnvr.uswest.net/cgi-bin/tl.exe/JPEG%20library/jpenhuff.cpp

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:

http://kdsl32.dnvr.uswest.net/cgi-bin/tl.exe/AERC/Poscalc/math1h.asm

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:

http://kdsl32.dnvr.uswest.net/cgi-bin/tl.exe/JPEG%20library/jpegenco.cpp

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.

Comments: