HOME

TheInfoList



OR:

Quantization, involved in
image processing An image or picture is a visual representation. An image can be two-dimensional, such as a drawing, painting, or photograph, or three-dimensional, such as a carving or sculpture. Images may be displayed through other media, including a pr ...
, is a
lossy compression In information technology, lossy compression or irreversible compression is the class of data compression methods that uses inexact approximations and partial data discarding to represent the content. These techniques are used to reduce data size ...
technique achieved by compressing a range of values to a single quantum (discrete) 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 An image or picture is a visual representation. An image can be Two-dimensional space, two-dimensional, such as a drawing, painting, or photograph, or Three-dimensional space, three-dimensional, such as a carving or sculpture. Images may be di ...
makes it possible to reduce its file size. Specific applications include DCT data quantization in
JPEG JPEG ( , short for Joint Photographic Experts Group and sometimes retroactively referred to as JPEG 1) is a commonly used method of lossy compression for digital images, particularly for those images produced by digital photography. The degr ...
and DWT data quantization in
JPEG 2000 JPEG 2000 (JP2) is an image compression standard and coding system. It was developed from 1997 to 2000 by a Joint Photographic Experts Group committee chaired by Touradj Ebrahimi (later the JPEG president), with the intention of superseding their ...
.


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 algorithm, and an algorithm based on
octree An octree is a tree data structure in which each internal node has exactly eight child node, children. Octrees are most often used to partition a three-dimensional space by recursive subdivision, recursively subdividing it into eight Octant (geo ...
s. It is common to combine color quantization with
dither Dither is an intentionally applied form of noise used to randomize quantization error, preventing large-scale patterns such as color banding in images. Dither is routinely used in processing of both digital audio and video data, and is ofte ...
ing to create an impression of a larger number of colors and eliminate banding artifacts.


Grayscale quantization

Grayscale quantization, also known as gray level quantization, is a process in digital image processing that involves reducing the number of unique intensity levels (shades of gray) in an image while preserving its essential visual information. This technique is commonly used for simplifying images, reducing storage requirements, and facilitating processing operations. In grayscale quantization, an image with ''N'' intensity levels is converted into an image with a reduced number of levels, typically ''L'' levels, where ''L''<''N''. The process involves mapping each pixel's original intensity value to one of the new intensity levels. One of the simplest methods of grayscale quantization is uniform quantization, where the intensity range is divided into equal intervals, and each interval is represented by a single intensity value. Let's say we have an image with intensity levels ranging from 0 to 255 (8-bit grayscale). If we want to quantize it to 4 levels, the intervals would be -63 4-127 28-191 and 92-255 Each interval would be represented by the midpoint intensity value, resulting in intensity levels of 31, 95, 159, and 223 respectively. The formula for uniform quantization is: Q(x) = \left \lfloor \frac \right \rfloor \times \Delta + \frac Where: * ''Q''(''x'') is the quantized intensity value. * ''x'' is the original intensity value. * Δ is the size of each quantization interval. Let's quantize an original intensity value of 147 to 3 intensity levels. Original intensity value: ''x''=147 Desired intensity levels: ''L''=3 We first need to calculate the size of each quantization interval: \Delta = \frac = \frac = 127.5 Using the uniform quantization formula: Q(x) = \left \lfloor \frac \right \rfloor \times 127.5 + \frac Q(x) = \left \lfloor 1.15294118 \right \rfloor \times 127.5 + \frac Q(x) = 1 \times 127.5 + 63.75 = 191.25 Rounding 191.25 to the nearest integer, we get Q(x) = 191 So, the quantized intensity value of 147 to 3 levels is 191.


Frequency quantization for image compression

The human eye is fairly good at seeing small differences in
brightness Brightness is an attribute of visual perception in which a source appears to be radiating/reflecting light. In other words, brightness is the perception dictated by the luminance of a visual target. The perception is not linear to luminance, and ...
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 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, is emitted from, or is reflected from a particular area, and falls wit ...
than
chrominance Chrominance (''chroma'' or ''C'' for short) is the signal used in video systems to convey the color information of the picture (see YUV color model), separately from the accompanying Luma (video), luma signal (or Y' for short). Chrominance is usu ...
, further compression can be obtained by working in a non-RGB color space which separates the two (e.g.,
YCbCr YCbCr, Y′CbCr, also written as YCBCR or Y′CBCR, is a family of color spaces used as a part of the color image pipeline in digital video and digital photography, photography systems. Like YPbPr, YPBPR, it is based on RGB primaries; the two ...
), and quantizing the channels separately.John Wiseman, ''An Introduction to MPEG Video Compression'', https://web.archive.org/web/20111115004238/http://www.john-wiseman.com/technical/MPEG_tutorial.htm


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 transform A discrete cosine transform (DCT) expresses a finite sequence of data points in terms of a sum of cosine functions oscillating at different frequency, frequencies. The DCT, first proposed by Nasir Ahmed (engineer), Nasir Ahmed in 1972, is a widely ...
(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 quantization 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 (Digital Video Express) is a discontinued digital video format. Created in part by Circuit City, it was an unsuccessful attempt to create an alternative to video rental in the United States. The format's poor reception from consumers resu ...
, Xvid, and
3ivx 3ivx ( ) was an MPEG-4 compliant video codec suite, created by 3ivx Technologies, based in Sydney, Australia. 3ivx video codecs were released from 2001 to 2012, with releases of related technologies continuing until 2015. 3ivx provided plugins to ...
) and compression standards (such as
MPEG-2 MPEG-2 (a.k.a. H.222/H.262 as was defined by the ITU) 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 ...
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: : \begin -415 & -33 & -58 & 35 & 58 & -51 & -15 & -12 \\ 5 & -34 & 49 & 18 & 27 & 1 & -5 & 3 \\ -46 & 14 & 80 & -35 & -50 & 19 & 7 & -18 \\ -53 & 21 & 34 & -20 & 2 & 34 & 36 & 12 \\ 9 & -2 & 9 & -5 & -32 & -15 & 45 & 37 \\ -8 & 15 & -16 & 7 & -8 & 11 & 4 & 7 \\ 19 & -28 & -2 & -26 & -2 & 7 & -44 & -21 \\ 18 & 25 & -12 & -44 & 35 & 48 & -37 & -3 \end A common quantization matrix is: : \begin 16 & 11 & 10 & 16 & 24 & 40 & 51 & 61 \\ 12 & 12 & 14 & 19 & 26 & 58 & 60 & 55 \\ 14 & 13 & 16 & 24 & 40 & 57 & 69 & 56 \\ 14 & 17 & 22 & 29 & 51 & 87 & 80 & 62 \\ 18 & 22 & 37 & 56 & 68 & 109 & 103 & 77 \\ 24 & 35 & 55 & 64 & 81 & 104 & 113 & 92 \\ 49 & 64 & 78 & 87 & 103 & 121 & 120 & 101 \\ 72 & 92 & 95 & 98 & 112 & 100 & 103 & 99 \end Dividing the DCT coefficient matrix element-wise with this quantization matrix, and rounding to integers results in: : \begin -26 & -3 & -6 & 2 & 2 & -1 & 0 & 0 \\ 0 & -3 & 4 & 1 & 1 & 0 & 0 & 0 \\ -3 & 1 & 5 & -1 & -1 & 0 & 0 & 0 \\ -4 & 1 & 2 & -1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end For example, using −415 (the DC coefficient) and rounding to the nearest integer : \mathrm \left( \frac \right) = \mathrm \left( -25.9375 \right) =-26 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.


See also

*
Image segmentation In digital image processing and computer vision, image segmentation is the process of partitioning a digital image into multiple image segments, also known as image regions or image objects (Set (mathematics), sets of pixels). The goal of segmen ...
* Image-based meshing * Range segmentation


References

{{DEFAULTSORT:Quantization (Image Processing) Lossy compression algorithms Image compression Data compression