Image Compression
 
  Introduction
  Classifying image data
  Quantization
  Bit Allocation
  Entropy Coding
  Source Code

Back to main page


Quantization


Quantization refers to the process of approximating the continuous set of values in the image data with a finite (preferably small) set of values. The input to a quantizer is the original data, and the output is always one among a finite number of levels. The quantizer is a function whose set of output values are discrete, and usually finite. Obviously, this is a process of approximation, and a good quantizer is one which represents the original signal with minimum loss or distortion.

There are two types of quantization - Scalar Quantization and Vector Quantization. In scalar quantization, each input symbol is treated separately in producing the output, while in vector quantization the input symbols are clubbed together in groups called vectors, and processed to give the output. This clubbing of data and treating them as a single unit increases the optimality of the vector quantizer, but at the cost of increased computational complexity. Here, we'll take a look at scalar quantization.

A quantizer can be specified by its input partitions and output levels (also called reproduction points). If the input range is divided into levels of equal spacing, then the quantizer is termed as a Uniform Quantizer, and if not, it is termed as a Non-Uniform Quantizer. A uniform quantizer can be easily specified by its lower bound and the step size. Also, implementing a uniform quantizer is easier than a non-uniform quantizer. Take a look at the uniform quantizer shown below. If the input falls between n*r and (n+1)*r, the quantizer outputs the symbol n.

Fig 1. A uniform quantizer

Just the same way a quantizer partitions its input and outputs discrete levels, a Dequantizer is one which receives the output levels of a quantizer and converts them into normal data, by translating each level into a 'reproduction point' in the actual range of data. It can be seen from literature, that the optimum quantizer (encoder) and optimum dequantizer (decoder) must satisfy the following conditions.

  • Given the output levels or partitions of the encoder, the best decoder is one that puts the reproduction points x' on the centers of mass of the partitions. This is known as centroid condition.
  • Given the reproduction points of the decoder, the best encoder is one that puts the partition boundaries exactly in the middle of the reproduction points, i.e. each x is translated to its nearest reproduction point. This is known as nearest neighbour condition.

The quantization error (x - x') is used as a measure of the optimality of the quantizer and dequantizer.
 


Classifying image data Bit allocation

Copyright (c) Satish Kumar. S 2001-2003. Last Modified - 22 Oct 2001
Suggestions/Broken links/queries? Write to satish@debugmode.com