Algorithms

Spring 2019
course
site

Thu Apr 18

lossy compression : JPEGs, DCT, and all that.

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

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

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 ...

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

Color compression :

aside

https://cs.marlboro.college /cours /spring2019 /algorithms /notes /jpeg
last modified Thu July 16 2020 3:59 am