Multimedia Software Systems CS4551
Image Quantization Dithering and Error Diffusion
• Suppose that an image uses 𝑁 intensity levels (or uses 𝑁 colors) to represent its content.
• Suppose that the rendering device on which this is to be displayed can use only 𝑛 colors, and 𝑛 < 𝑁.
Copyright By PowCoder代写 加微信 powcoder
• How can we reproduce the image in a satisfactory way?
• Solution
– Quantization from 𝑁 to 𝑛 levels, but as 𝑛 gets smaller, quantization starts showing artifacts
– What if 𝑛 = 2 : use Dithering and Error Diffusion
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 2
• Assume the original image has only 𝑘2 + 1 intensity levels.
• Each pixel of the original image is mapped into a 𝑘 × 𝑘 block of the dithered image.
– Example:𝑘=2
• Problem: the effective display image resolution is reduced to 1/𝑘 (because each pixel is “zoomed” into one 𝑘 × 𝑘 block).
– It’snoproblemifthedisplayarrayislargerthantheimagearray.
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 3
Dithering Matrix • DitheringiscontrolledbythedithermatrixD.
• For example, with 𝑘 = 3: 𝐷=103
• To display an intensity 𝐼 (with 0 ≤ 𝐼 ≤ 9), just “turn on” all pixels in the 3 × 3 block whose values are less than 𝐼
• Must be carefully designed to avoid artifacts
– Whathappenswithconstant𝐼=3forfollowing𝐷?
684 𝐷=102 537
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 4
Dithering Matrices
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 5
Ordered Dithering
• It is possible to keep the image resolution the same as the original image by ensuring that each image point
𝑥, 𝑦 should control only the 𝑥, 𝑦 display pixel
• A possible technique – Ordered Dithering – Compute𝑖=𝑥mod𝑘,𝑗=ymod𝑘
– Turn on/off the output pixel at position 𝑥, 𝑦 𝐼𝑥,𝑦 and𝐷𝑖,𝑗
𝑂 𝑥,𝑦 =ቊ1, 𝐼 𝑥,𝑦 >𝐷 𝑖,𝑗 0, 𝐼𝑥,𝑦 ≤𝐷𝑖,𝑗
CSULA CS451 Multimedia Software Systems by Eun-Young Kang
by comparing
Example – Dithering
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 7
Error Diffusion
• When trying to display an image having colors more in number than the display device (or printer device), a selection has to be made to approximate the value of the display color, which is done using
– Precomputed Lookup Tables (LUT)
– Dynamic Color Quantization
• Either way the difference in the selector color value and the original value results in an error.
• Large color errors degrade the quality of the displayed image. If the error is diffused in the neighborhood, such effects are minimized.
• Error Diffusion Algorithms do this by distributing the errors among all the pixels such that the total error for the entire image is zero (or very close to zero).
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 8
Error Diffusion Algorithm
• Let A be the original image and B be the final quantized image
• For each pixel A[i,j]
– Quantization
• FindthevalueQ(0or255ifBisabi-level image) that is nearest to the original pixel’s value A[i,j].
• Assign Q to B[i,j] (Quantization step) – Error diffusion
• Calculate the quantization error e=A[i,j]-B[i,j] for the pixel A[i,j]. Error e can be negative.
• Distribute this error e to four of A[i,j]’s nearest neighbors that haven’t been scanned yet (the one on the right and the three ones centered below) according to a filter weight (e.g. – Floyd-Steinberg)
CSULA CS451 Multimedia Software Systems by Eun-Young Kang
E.g. – Floyd-
the neighbor A[i,j+1] will be updated as A[i,j+1] = A[i,j+1] + e*7/16
* Updated neighbor pixel values can be negative.
Error Diffusion Steps (1)
1. Quantize
2. Update image (error diffusion)
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 10
A (grayscale image)
B (quantized bi-level image)
Error Diffusion Steps (2)
1. Quantize
150 > 256/2→to 255
A (grayscale image)
B (quantized bi-level image)
CSULA CS451 Multimedia Software Systems by Eun-Young Kang
Error Diffusion Steps (3)
A (grayscale image)
B (quantized bi-level image)
2. Update image A (error diffusion)
Calculate𝑒=A𝑖,𝑗 −B𝑖,𝑗 and distribute 𝑒 (-105) to 4 neighbors using Floyd-Steinberg weights.
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 12
Example – Error Diffusion
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 13
Comparison on Dithering and Diffusion
Original Threshold
Floyd SULA CS451 Multimedia Software Systems by Eun-Young Kang
Ordered dithering
Example – Error Diffusion
Input Gray-scale
Quad-level
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 15
Hybrid: Error Diffusion for Color Quantization
Input image (left)
Uniform Color Quantization (middle)
Uniform Color Quantization + Error Diffusion (right)
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 16
Hybrid: Error Diffusion for Color Quantization
Input image (left)
Uniform Color Quantization (middle)
Uniform Color Quantization + Error Diffusion (right)
CSULA CS451 Multimedia Software Systems by Eun-Young Kang 17
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com