Color Quantization
• Suppose you have a 24-bit color image and need to convert it to a 8-bit color (index) image. So we have to devise a Color LUT for this image.
• This process is called color quantization.
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 18
Copyright By PowCoder代写 加微信 powcoder
Color Quantization (2)
• 2 steps:
– Step 1 : Generate 8-bit LUT
– Step 2 : Convert each 24-bit pixel to 8-bit LUT index
• You may choose the method in two ways
– Pre-designed or fixed version
– Adaptively “quantized” version for the best result. Most adaptive quantization methods are based on popularity.
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 19
Color Quantization: 24-bit→8-bit 24-bit value
8-bit value
CSULA CS451 Multimedia Software Systems by Eun-Young Kang
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 21
Color Quantization – Assumption
• Let’s assume that we have 24-bit RGB color space and
want to quantized in 𝐾 = 256.
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 22
Uniform Color Quantization
• Uniform Color Quantization is one of the fixed color quantization. • Step 1:
– Divide RGB cube into equal slices in each dimension. That is each axis is divided into equal sized segments. (e.g. red and green axis into 8 segments, blue axis into 4 segments resulting into 256 regions.)
– Each one of these regions will produce a color for the LUT. The representative color for each region is the average (or center) of all colors in that region.
• Step 2: Find a region which the original 24-bit color is mapped to. Convert 24-bit color to 8-bit index.
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 23
LUT by Uniform Color Quantization
8 bits (0 ~ 255) 8 bits (0 ~ 255)
3 bits (0-7) 3 bits (0-7)
CSULA CS451 Multimedia Software Systems by Eun-Young Kang
8 bits (0 ~ 255)
2 bits (0-3)
LUT by Uniform Color Quantization
0 (00000000)
1 (00000001)
255 (11111111)
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 25
Pixel Conversion by Uniform Color Quantization
• For a 24-bit color (255, 255, 100) pixel, when the uniform color quantization is used to convert to 8-bit color image:
– What is the LUT index for the pixel? – What is the RGB value for that index?
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 26
Uniform Color Quantization – Example
Original After Uniform Quantization
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 27
Uniform Color Quantization – Example
Original After Uniform Quantization
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 28
Uniform Color Quantization – Example
Original After Uniform Quantization
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 29
Uniform Color Quantization
– Quick and easy to implement.
– But it does not yield good results.
• Modification
– Because the human eye cannot distinguish dark colors as well as bright ones, this algorithm can also be applied in a non- linear manner if the axis are broken on a logarithmic scale instead of linear. This will produce slightly better result.
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 30
Adaptive Color Quantization Methods
• The process occurs in stages
– 1st stage: Sampling the original image for color statistics (Histogram)
– 2nd stage: Creating a LUT based on those statistics
– 3rd stage: Mapping colors to their representative colors to get new image
• Different algorithms proposed and used depend on how the second step above is done
– Popularity Algorithm – Median Cut Algorithm – Octree–quantization
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 31
Popularity Algorithms
• A variation of uniform quantization.
• The algorithm breaks the color space into much smaller regions initially.
– E.g. divide 64 segments for each axis resulting in 262,144 regions in total.
• The original colors are again mapped to the regions they fall in. The representative color for each region is the average of the colors mapped to it. The color map is selected by taking the representative colors of the 256 most popular regions. If a non-empty region is not selected for the color map, the index into the color map is the entry in the color map that is closest to its representative color.
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 32
Popularity Algorithms – Example
Original After Popularity Quantization
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 33
Popularity Algorithms – Example
Original After Popularity Quantization
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 34
Popularity Algorithms – Example
Original After Popularity Quantization
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 35
Popularity Algorithms
– Easy to implement. Give better results than the uniform quantization algorithm.
– But it takes slightly longer to execute and requires significantly larger storage requirement depending on the size of regions.
– Also, depending on the image characteristics, it may not produce a good result.
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 36
Median Cut Algorithms
• The premise behind median cut algorithm is to have every entry in the LUT represent the same/similar number of pixels in the original image. The algorithm divides the color space based on the distribution of the original colors.
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 37
Median Cut Algorithms • Process
1. Find the smallest bounding box which contains all the colors in the image
2. Sort the enclosed colors along the longest axis of the box
3. Split the box into 2 regions at median of the sorted list
4. Repeat the above process (1~3) until the original color space has been divided into 256 regions
• The representative colors are found by averaging color in each box, and the appropriate color map index assigned to each color in that box.
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 38
Median Cut Quantization – Example
Original After Median Cut Quantization
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 39
Median Cut Quantization – Example
Original After Median Cut Quantization CSULA CS451 Multimedia Software Systems by Eun-Young Kang 40
Median Cut Quantization – Example
Original After Median Cut Quantization CSULA CS451 Multimedia Software Systems by Eun-Young Kang 41
Median Cut Algorithms
• Comments: It produces good results because the algorithm use image information while having memory and time complexity no worse than popularity algorithm.
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 42
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com