Quantization (image processing): Difference between revisions

Revision as of 08:46, 6 April 2006

Revision as of 20:50, 2 May 2006

Line 1:

'''Quantization''', involved in [[image processing]]. Quantization techniques generally compress by compressing a range of values to a single quantum value. By reducing the number of discrete symbols in a given stream, the stream becomes more compressible. For example seeking to reduce the number of colors required to represent an [[image]]. Another widely used example — [[DCT]] data quantization in [[JPEG]] and [[DWT]] data quantization in [[JPEG 2000]].

== QuantizationColor in file formatsquantization ==

{{mainarticle|Color quantization}}

Although more frequent in the past, nowadays color quantization with pallets of lower than 256 colours is mainly used in [[GIF]] and [[PNG]] images. Using "nearest-neighbor" quantization and allowing fewer colours usually results in smaller file sizes, however sophisticated "random dithering" can actually inflate the final size.

Color quantization reduces the number of colors used in an image; this is important for displaying images on devices that support a limited number of colors and for efficiently compressing certain kinds of images. Most bitmap editors and many operating systems have built-in support for color quantization. Popular modern color quantization algorithms include the nearest color algorithm (for fixed palettes), the [[median cut algorithm]], and an algorithm based on [[octree]]s.

The infinite number of colors available through the lens of a camera is impossible to display on a computer screen. Since a computer can display only a finite number of colors, quantization is always necessary.

It is common to combine color quantization with [[dither|dithering]] to create an impression of a larger number of colors and eliminate banding artifacts.

Many early computers were limited in the number of colors they could display at one time — commonly 16 (and later 256) colours. Modern computers can now display millions of colours at once, far more than can be distinguished by the human eye.

== QuantizationFrequency inquantization for image compression ==

Most quantization algorithms allow you to set exactly how many colors you want to use. With the few colors available on early computers, different quantization algorithms produced very different-looking output images. As a result, a lot of time was spent on writing sophisticated algorithms to be more lifelike. Nowadays almost every algorithm produces an output indistinguishable from the view through the camera lens.

=== Quantization algorithms ===

A standard quantization [[algorithm]] works in 2 steps:

# Analyze the image's color usage to select the new color palette.

# [[Dithering|Dither]] the image to the new color palette.

A common quantization algorithm is the Octree-based algorithm, as described in the [http://msdn.microsoft.com MSDN] article on [[ASP.NET]] color quantization.

<!-- FIXME: is there a link directly to the referenced article? -->

Another popular quantization algorithm is the "median cut" algorithm.

== Quantization in image compression ==

The human eye is fairly good at seeing small differences in [[brightness]] over a relatively large area, but not so good at distinguishing the exact strength of a high frequency brightness variation. This fact allows one to get away with greatly reducing the amount of information in the high frequency components. This is done by simply dividing each component in the frequency ___domain by a constant for that component, and then rounding to the nearest integer. This is the main lossy operation in the whole process. As a result of this, it is typically the case that many of the higher frequency components are rounded to zero, and many of the rest become small positive or negative numbers.