Thu Apr 18

lossy compression : JPEGs, DCT, and all that.

First: how many bits in a (say) 1024 x 1024 RGB image?

• raw data (minimal) size ... e.g. digital camera sensor output

Second: How much smaller can we get with lossless encoding? Well, PNG is one example.

• PNG
• "color table"
• DEFLATE : LZ77 + Huffman (!)

Third: JPEG - a lossy (information is lost, depending on how blurry we are willing to allow it to be) compression algorithm, with several steps :

1. color transformation (R.G.B -> Y.Cb.Cr)
2. quantization of Cb & Cr (by factor of 2 or so, i.e. 8bits - 3 or 4 bits; this is a lossy step)
3. each color channel is split into 8 x 8 blocks
4. each 8 x 8 color block goes through a DCT (discrete cosine transform, into spatial horizontal and vertical frequencies)
5. quantization of the higher spatial frequencies (this is the biggest lossy step)
6. the pixel data are put into a 1D zig-zag order (lowest to highest spacial frequency)

Both JPEG and PNG file formats also have meta data info at the front of the file in addition to the pixel data.

Note that all these are "raster" (pixel) formats - there are also "vector" formats which store math-ish info about smooth curves rather than pixels.

On to the details ...

• There are whole courses on this stuff ... we're just tryingto get some intuition, not do all the math.
• This is part of the subject of Linear Algebra : in particular, the notion of a "basis".
• The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face
• wikipedia: jpeg
• DCT - Jim's jupyter notebook | on jupyter

What is "quantization" ... and how is it a (lossy) compression technique? Do an example.

Color compression :

• RGB
• YCbCr

aside

• an image of shakespeare which is also a zip archive of all his plays | hackernews discussion
• wikipedia: steganography - hiding messages in images or other media
• cheating AI caught using steganogrophy | hackernews discussion