Quantization (image processing)
Encyclopedia
Quantization, involved in image processing
, is a lossy compression technique achieved by compressing a range of values to a single quantum value. When the number of discrete symbols in a given stream is reduced, the stream becomes more compressible. For example, reducing the number of colors required to represent a digital image
makes it possible to reduce its file size. Specific applications include DCT
data quantization in JPEG
and DWT
data quantization in JPEG 2000
.
__FORCETOC__
, and an algorithm based on octree
s.
It is common to combine color quantization with dither
ing to create an impression of a larger number of colors and eliminate banding
artifacts.
over a relatively large area, but not so good at distinguishing the exact strength of a high frequency (rapidly varying) brightness variation. This fact allows one to reduce the amount of information required by ignoring 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.
As human vision is also more sensitive to luminance
than chrominance
, further compression can be obtained by working in a non-RGB color space which separates the two (e.g., YCbCr
), and quantizing the channels separately.
(DCT) to calculate the frequency components, both horizontally and vertically. The resulting block (the same size as the original block) is then pre-multiplied by the quantisation scale code and divided element-wise by the quantization matrix, and rounding each resultant element. The quantization matrix is designed to provide more resolution to more perceivable frequency components over less perceivable components (usually lower frequencies over high frequencies) in addition to transforming as many components to 0, which can be encoded with greatest efficiency. Many video encoders (such as DivX
, Xvid
, and 3ivx
) and compression standards (such as MPEG-2
and H.264/AVC) allow custom matrices to be used. The extent of the reduction may be varied by changing the quantizer scale code, taking up much less bandwidth than a full quantizer matrix.
This is an example of DCT coefficient matrix:
A common quantization matrix is:
Dividing the DCT coefficient matrix element-wise with this quantization matrix, and rounding to integers results in:
For example, using −415 (the DC coefficient) and rounding to the nearest integer
Typically this process will result in matrices with values primarily in the upper left (low frequency) corner. By using a zig-zag ordering to group the non-zero entries and run length encoding, the quantized matrix can be much more efficiently stored than the non-quantized version.
Image processing
In electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
, is a lossy compression technique achieved by compressing a range of values to a single quantum value. When the number of discrete symbols in a given stream is reduced, the stream becomes more compressible. For example, reducing the number of colors required to represent a digital image
Image
An image is an artifact, for example a two-dimensional picture, that has a similar appearance to some subject—usually a physical object or a person.-Characteristics:...
makes it possible to reduce its file size. Specific applications include DCT
Discrete cosine transform
A discrete cosine transform expresses a sequence of finitely many data points in terms of a sum of cosine functions oscillating at different frequencies. DCTs are important to numerous applications in science and engineering, from lossy compression of audio and images A discrete cosine transform...
data quantization in JPEG
JPEG
In computing, JPEG . The degree of compression can be adjusted, allowing a selectable tradeoff between storage size and image quality. JPEG typically achieves 10:1 compression with little perceptible loss in image quality....
and DWT
Discrete wavelet transform
In numerical analysis and functional analysis, a discrete wavelet transform is any wavelet transform for which the wavelets are discretely sampled...
data quantization in JPEG 2000
JPEG 2000
JPEG 2000 is an image compression standard and coding system. It was created by the Joint Photographic Experts Group committee in 2000 with the intention of superseding their original discrete cosine transform-based JPEG standard with a newly designed, wavelet-based method...
.
__FORCETOC__
Color quantization
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 algorithmMedian cut
Median cut is an algorithm to sort data of an arbitrary number of dimensions into series of sets by cutting each set of data at the median point....
, and an algorithm based on octree
Octree
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees. The name is formed from oct + tree,...
s.
It is common to combine color quantization with dither
Dither
Dither is an intentionally applied form of noise used to randomize quantization error, preventing large-scale patterns such as color banding in images...
ing to create an impression of a larger number of colors and eliminate banding
Colour banding
Colour banding is a problem of inaccurate colour presentation in computer graphics. While in 24 bit colour modes, 8 bits per channel should be enough to render images in the full visible spectrum, in some cases there is a risk of producing abrupt changes between shades of the same colour...
artifacts.
Frequency quantization for image compression
The human eye is fairly good at seeing small differences in brightnessBrightness
Brightness is an attribute of visual perception in which a source appears to be radiating or reflecting light. In other words, brightness is the perception elicited by the luminance of a visual target...
over a relatively large area, but not so good at distinguishing the exact strength of a high frequency (rapidly varying) brightness variation. This fact allows one to reduce the amount of information required by ignoring 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.
As human vision is also more sensitive to luminance
Luminance
Luminance is a photometric measure of the luminous intensity per unit area of light travelling in a given direction. It describes the amount of light that passes through or is emitted from a particular area, and falls within a given solid angle. The SI unit for luminance is candela per square...
than chrominance
Chrominance
Chrominance is the signal used in video systems to convey the color information of the picture, separately from the accompanying luma signal . Chrominance is usually represented as two color-difference components: U = B' − Y' and V = R' − Y'...
, further compression can be obtained by working in a non-RGB color space which separates the two (e.g., YCbCr
YCbCr
YCbCr or Y′CbCr, sometimes written or , is a family of color spaces used as a part of the color image pipeline in video and digital photography systems. Y′ is the luma component and CB and CR are the blue-difference and red-difference chroma components...
), and quantizing the channels separately.
Quantization matrices
A typical video codec works by breaking the picture into discrete blocks (8×8 pixels in the case of MPEG). These blocks can then be subjected to discrete cosine transformDiscrete cosine transform
A discrete cosine transform expresses a sequence of finitely many data points in terms of a sum of cosine functions oscillating at different frequencies. DCTs are important to numerous applications in science and engineering, from lossy compression of audio and images A discrete cosine transform...
(DCT) to calculate the frequency components, both horizontally and vertically. The resulting block (the same size as the original block) is then pre-multiplied by the quantisation scale code and divided element-wise by the quantization matrix, and rounding each resultant element. The quantization matrix is designed to provide more resolution to more perceivable frequency components over less perceivable components (usually lower frequencies over high frequencies) in addition to transforming as many components to 0, which can be encoded with greatest efficiency. Many video encoders (such as DivX
DivX
DivX is a brand name of products created by DivX, Inc. , including the DivX Codec which has become popular due to its ability to compress lengthy video segments into small sizes while maintaining relatively high visual quality.There are two DivX codecs; the regular MPEG-4 Part 2 DivX codec and the...
, Xvid
XviD
Xvid is a video codec library following the MPEG-4 standard, specifically MPEG-4 Part 2 Advanced Simple Profile . It uses ASP features such as b-frames, global and quarter pixel motion compensation, lumi masking, trellis quantization, and H.263, MPEG and custom quantization matrices.Xvid is a...
, and 3ivx
3ivx
3ivx is a video codec suite, created by 3ivx Technologies, based in Sydney, Australia, that allows the creation of MPEG-4 compliant data streams. It has been designed around a need for decreased processing power for use mainly in embedded systems. First versions were published in 2001...
) and compression standards (such as MPEG-2
MPEG-2
MPEG-2 is a standard for "the generic coding of moving pictures and associated audio information". It describes a combination of lossy video compression and lossy audio data compression methods which permit storage and transmission of movies using currently available storage media and transmission...
and H.264/AVC) allow custom matrices to be used. The extent of the reduction may be varied by changing the quantizer scale code, taking up much less bandwidth than a full quantizer matrix.
This is an example of DCT coefficient matrix:
A common quantization matrix is:
Dividing the DCT coefficient matrix element-wise with this quantization matrix, and rounding to integers results in:
For example, using −415 (the DC coefficient) and rounding to the nearest integer
Typically this process will result in matrices with values primarily in the upper left (low frequency) corner. By using a zig-zag ordering to group the non-zero entries and run length encoding, the quantized matrix can be much more efficiently stored than the non-quantized version.