# Simple, streaming, lossless image compression

Does anyone know of any image compression techniques with the following characteristics:

• lossless
• streaming - I want to compress on the fly, pixel-by-pixel.
• low-memory overhead - I can afford to buffer a single line, but ideally not even that.
• no dynamic dictionaries
• "real-world" images only, so performance on "nasty cases" like chequerboards is not important
• 2-3x compression (5x-10x would be even better, but that's asking a lot I know)
• can operate on 10-16 bit pixels (depending on my camera)

My images will be ~1k pixels wide, with pixel rates of ~20Mpix/sec. The pixel depth will be something between 10 and 16 bits per pixel (depending on the choice of camera). Assume sub-16-bit pixel widths would be represented within a 16-bit word for now, rather than needing to be extracted from a continuous bit-stream.

Some form of delta+arithmetic coding perhaps?

• Are your 10 - 16 bit pixels always padded to say, 16 bits, or are they packed ? – Paul R Jan 27 '12 at 15:42
• Seems like there aren't many image-specific requirements there. At the risk of sounding obvious, have you considered trying a standard streaming-data compression algorithm, like zlib, LZMA, etc.? – Jason R Jan 27 '12 at 16:04
• @PaulR - question updated - the pixels will be padded. – Martin Thompson Jan 27 '12 at 16:14
• @JasonR: I have done a bit of investigation on "standard" techniques, but my (possibly innaccurate?) impression is they seem to be too dynamic and fairly memory hungry (relative to my "even 1K stretches it" criterion :) – Martin Thompson Jan 27 '12 at 16:18
• the huffyuv mentioned below is quite similar to your own 'delta+arithmetic' suggestion. Although obviously it uses huffman instead of arithmetic coding for the entropy coding part. on 8 bits/pixel it typically reaches slightly above 2x compression, with only 1 line-buffer. – Mr. White Feb 22 '12 at 16:55

You can consider using Huffyuv : http://neuron2.net/www.math.berkeley.edu/benrg/huffyuv.html

This is no great better than simple zip, but still slightly optimized for images.

Any Image related compression comes from the techniques like Vector quantization or Transform coding. In order to make use of transform such as DCT/Wavelet yet make it lossless you can think of JPEG-LS or JPEG2000 for compression. Only thing is, it is not streaming in your sense of definition.

• Huffyuv only requires one line buffer, it's spatial decorrelation technique (the median predictor) is therefore simple. For higher compression rates, a good spatial predictor is key. Expect the required amount of line buffers to go up significantly. DCT/Wavelet for example, requires 4 to 8 lines at least, in order to achieve better results than Huffyuv – Mr. White Feb 22 '12 at 17:03

This looks like what you would put in a digital camera for a lossless RAW.

1/ Check the source code of dcraw to see what various camera manufacturers are already doing. For example Pentax uses some variable length int scheme (length N coded with a huffman code, then N bits) to code the delta of a pixel wrt the previous pixel of the same color in the Bayer mosaic ; and this routinely achieves 1:1.5 to 1:2 ratios.

2/ DNG files can be compressed too. Check how it is done from the Adobe specs... Not sure if it is based on a similar prediction + variable length int encoding (which is streaming) ; or if it uses the more advanced JPEG-LS based on LOCO (and which unfortunately requires several passes on the data).

zlib has a compression mode ("HUFFMAN_ONLY") that is fast and does not require a lot of memory. For typical photos using zlib with libpng I get about 1:2 compression ratios. You can try it out with ImageMagick, GraphicsMagick, or pngcrush.

convert input.ppm -quality 1 output_im.png
gm convert input.ppm -quality 1 output_gm.png
pngcrush -force -m 12 input.png output_pc.png


These examples all use the PNG "sub" filter (1) which is effective for photos. For *Magick, "-quality 1" and for pngcrush, "-m 12" means to use the "sub" filter and "huffman_only" compression.