Image Processing
Quantization Filtering
Blur Detect edges Uniform Quantization Random dither Ordered dither Floyd-Steinberg dither
Image Processing
Tom Funkhouser Princeton University COS 426, Spring 2006
Warping
Scale Rotate Warp
Pixel operations
Add random noise Add luminance Add contrast Add saturation
Combining
Composite Morph
What is an Image?
An image is a 2D rectilinear array of samples
Image Resolution
Intensity resolution
Each pixel has only Depth bits for colors/intensities
Spatial resolution
Image has only Width x Height pixels
Temporal resolution
Monitor refreshes images at only Rate Hz
Width x Height 640 x 480 1280 x 1024 3000 x 2000 6600 x 5100 Depth 8 24 12 1 Rate 30 75 24 -
Typical Resolutions
Continuous image
Digital image
NTSC Workstation Film Laser Printer
Sources of Error
Intensity quantization
Not enough intensity resolution
Overview
Image representation
What is an image?
Spatial aliasing
Not enough spatial resolution
Halftoning and dithering
Reduce visual artifacts due to quantization
Temporal aliasing
Not enough temporal resolution
Sampling and reconstruction
Reduce visual artifacts due to aliasing
E2 =
( x, y )
(I ( x, y) P( x, y) )2
Quantization
Artifacts due to limited intensity resolution
Frame buffers have limited number of bits per pixel Physical devices have limited dynamic range
Uniform Quantization
P(x, y) = round( I(x, y) ) where round() chooses nearest value that can be represented.
P(x,y)
I(x,y)
I(x,y)
P(x,y) (2 bits per pixel)
Uniform Quantization
Images with decreasing bits per pixel:
Reducing Effects of Quantization
Dithering
Random dither Ordered dither Error diffusion dither
Halftoning
Classical halftoning 8 bits 4 bits 2 bits 1 bit
Notice contouring.
Dithering
Distribute errors among pixels
Exploit spatial integration in our eye Display greater range of perceptible intensities
Random Dither
Randomize quantization errors
Errors appear as noise
P(x,y)
I(x,y)
Original (8 bits) Uniform Quantization (1 bit) Floyd-Steinberg Dither (1 bit)
P(x,y)
I(x,y)
P(x, y) = round( I(x, y) + noise(x,y) )
Random Dither
Ordered Dither
Pseudo-random quantization errors
Matrix stores pattern of threshholds
Original (8 bits)
Uniform Quantization (1 bit)
Random Dither (1 bit)
i = x mod n 3 1 j = y mod n D2 = 0 2 e = I(x,y) - trunc(I(x,y)) threshold = (D(i,j)+1)/(n2+1) if (e > threshold) 0 1/5 2/5 3/5 4/5 P(x,y) = ceil(I(x, y)) else P(x,y) = floor(I(x,y)) thresholds
Ordered Dither
Bayers ordered dither matrices
4 Dn + D2 (1,1)U n
2 2
Ordered Dither
Dn =
4 Dn + D2 (2,1)U n
2 2
4 Dn + D2 (1,2)U n
2 2
4 Dn + D2 (2,2)U n
15 3 12 0 7 11 4 8 13 1 14 2 5 9 6 10
2 2
D2 =
3 0
1 2
D4 =
Original (8 bits)
Random Dither (1 bit)
Ordered Dither (1 bit)
Error Diffusion Dither
Spread quantization error over neighbor pixels
Error dispersed to pixels right and below
Error Diffusion Dither
Original (8 bits)
Figure 14.42 from H&B
+ + + = 1.0
Random Dither (1 bit)
Ordered Dither (1 bit)
Floyd-Steinberg Dither (1 bit)
Reducing Effects of Quantization
Dithering
Random dither Ordered dither Error diffusion dither
Classical Halftoning
Use dots of varying size to represent intensities
Area of dots proportional to intensity in image
Halftoning
Classical halftoning
I(x,y)
P(x,y)
Classical Halftoning
Halftone patterns
Use cluster of pixels to represent intensity
Trade spatial resolution for intensity resolution
Q: In this case, would we use four halftoned pixels in place of one original pixel?
From Town Topics, Princeton Figure 14.37 from H&B
Overview
Image representation
What is an image?
What is an Image?
An image is a 2D rectilinear array of samples
Halftoning and dithering
Reduce visual artifacts due to quantization
Sampling and reconstruction
Reduce visual artifacts due to aliasing
Continuous image
Digital image
Sampling and Reconstruction
Sampling and Reconstruction
Sampling
Reconstruction
Figure 19.9 FvDFH
Image Processing
Quantization
Uniform Quantization Random dither Ordered dither Floyd-Steinberg dither
Adjusting Brightness
Filtering
Blur Detect edges
Simply scale pixel components
Must clamp to range (e.g., 0 to 255)
Warping
Scale Rotate Warps
Pixel operations
Add random noise Add luminance Add contrast Add saturation
Combining
Composite Morph Original Brighter
Adjusting Contrast
Compute mean luminance for all pixels
luminance = 0.30*r + 0.59*g + 0.11*b
Image Processing
Quantization
Uniform Quantization Random dither Ordered dither Floyd-Steinberg dither
Filtering
Blur Detect edges
Scale deviation from
for each pixel component
Must clamp to range (e.g., 0 to 255)
Warping
Scale Rotate Warps
Pixel operations
Add random noise Add luminance Add contrast Add saturation Original More Contrast
Combining
Composite Morph
Image Processing
Consider reducing the image resolution
Image Processing
Image processing is a resampling problem
Resampling
Original image
1/4 resolution Thou shalt avoid aliasing!
Aliasing
In general:
Artifacts due to under-sampling or poor reconstruction
Spatial Aliasing
Artifacts due to limited spatial resolution
Specifically, in graphics:
Spatial aliasing Temporal aliasing
Under-sampling
Figure 14.17 FvDFH
Spatial Aliasing
Artifacts due to limited spatial resolution
Temporal Aliasing
Artifacts due to limited temporal resolution
Strobing Flickering
Jaggies
Temporal Aliasing
Artifacts due to limited temporal resolution
Strobing Flickering
Temporal Aliasing
Artifacts due to limited temporal resolution
Strobing Flickering
Temporal Aliasing
Artifacts due to limited temporal resolution
Strobing Flickering
Sampling Theory
When does aliasing happen?
How many samples are required to represent a given signal without loss of information? What signals can be reconstructed without loss for a given sampling rate?
Spectral Analysis
Spatial domain:
Function: f(x) Filtering: convolution
Fourier Transform
Frequency domain:
Function: F(u) Filtering: multiplication
Any signal can be written as a sum of periodic functions.
Figure 2.6 Wolberg
Fourier Transform
Fourier transform:
Sampling Theorem
A signal can be reconstructed from its samples, if the original signal has no frequencies above 1/2 the sampling frequency - Shannon The minimum sampling rate for bandlimited function is called Nyquist rate
F (u ) =
f ( x)e i 2xu dx
Inverse Fourier transform:
f ( x) =
F (u )e + i 2ux du
A signal is bandlimited if its highest frequency is bounded. The frequency is called the bandwidth.
Antialiasing
Sample at higher rate
Not always possible Doesnt always solve problem
Image Processing
Real world Sample Discrete samples (pixels) Reconstruct Reconstructed function Transform Transformed function Filter Bandlimited function Sample Discrete samples (pixels) Reconstruct Display
Pre-filter to form bandlimited signal
Form bandlimited function using low-pass filter Trades aliasing for blurring
Image Processing
Real world Sample Discrete samples (pixels) Reconstruct Reconstructed function Transform Transformed function Filter Bandlimited function Sample Discrete samples (pixels) Reconstruct Display
Image Processing
Real world Sample Discrete samples (pixels) Reconstruct Reconstructed function Transform
Continuous Function
Transformed function Filter Bandlimited function Sample Discrete samples (pixels) Reconstruct Display
Discrete Samples
Image Processing
Real world Sample Discrete samples (pixels) Reconstruct Reconstructed function Transform Transformed function Filter Bandlimited function Sample Discrete samples (pixels) Reconstruct Display
Image Processing
Real world Sample Discrete samples (pixels) Reconstruct Reconstructed function Transform
Reconstructed Function
Transformed function Filter Bandlimited function Sample Discrete samples (pixels) Reconstruct Display
Transformed Function
Image Processing
Real world Sample Discrete samples (pixels) Reconstruct Reconstructed function Transform Transformed function Filter Bandlimited function Sample Discrete samples (pixels) Reconstruct Display
Image Processing
Real world Sample Discrete samples (pixels) Reconstruct Reconstructed function Transform
Bandlimited Function
Transformed function Filter Bandlimited function Sample Discrete samples (pixels) Reconstruct Display
Discrete samples
Image Processing
Real world Sample Discrete samples (pixels) Reconstruct Reconstructed function Transform Transformed function Filter Bandlimited function Sample Discrete samples (pixels) Reconstruct Display
Ideal Bandlimiting Filter
Frequency domain
f max
Display
Spatial domain
Sinc ( x ) = sin x x
Figure 4.5 Wolberg
Practical Image Processing
Finite low-pass filters
Point sampling (bad) Triangle filter Gaussian filter
Real world Sample Discrete samples (pixels) Reconstruct Reconstructed function Transform Transformed function Filter Bandlimited function Sample Discrete samples (pixels) Reconstruct Display
Convolution
Spatial domain: output pixel is weighted sum of pixels in neighborhood of input image
Pattern of weights is the filter
Filter
Convolution
Input
Output
Convolution with a Triangle Filter
Example 1:
Filter
Convolution with a Triangle Filter
Example 1:
0.5 0.25 0.25
Filter
Input
Output
Input
Output
Convolution with a Triangle Filter
Example 1:
0.5 0.25 0.25
Convolution with a Triangle Filter
Example 1:
0.5 0.25 0.25
Filter
Filter
Input
Output
Input
Output
10
Convolution with a Triangle Filter
Example 1:
0.5 0.25 0.25
Convolution with a Triangle Filter
Q: What if the filter runs off the end?
Filter Filter
Input
Output
Input
Output
Convolution with a Triangle Filter
Example 1:
0.67 0.33
Convolution with a Triangle Filter
Q: what if the filter is not centered on a sample?
Filter Filter
Input
Output
Input
Output
Convolution with a Triangle Filter
Example 2:
0.40 0.15 0.35 0.10
Convolution with a Triangle Filter
Example 2:
0.40 0.15 0.35 0.10
Filter
Filter
Input
Output
Input
Output
11
Convolution with a Triangle Filter
Example 3 (triangle filter of radius 1):
Filter
Convolution with a Gaussian Filter
Example 4:
Filter
Input
Output
Input
Output
Figure 2.4 Wolberg
Figure 2.4 Wolberg
Image Processing
Quantization
Uniform Quantization Random dither Ordered dither Floyd-Steinberg dither
Adjust Blurriness
Filtering
Blur Detect edges
Convolve with a filter whose entries sum to one
Each pixel becomes a weighted average of its neighbors
Warping
Scale Rotate Warps
Pixel operations
Add random noise Add luminance Add contrast Add saturation
Combining
Composite Morph
Original Blur
Filter = 216 416 216
1 2 16 16 1 16 1 2 16 16 1 16
Edge Detection
Convolve with a filter that finds differences between neighbor pixels
Image Processing
Quantization
Uniform Quantization Random dither Ordered dither Floyd-Steinberg dither
Filtering
Blur Detect edges
Warping
Scale Rotate Warps
Pixel operations
Original Detect edges
1 1 1 Filter = 1 + 8 1 1 1 1
Add random noise Add luminance Add contrast Add saturation
Combining
Composite Morph
12
Scaling
Resample with triangle or Gaussian filter
More on this next lecture!
Image Processing
Image processing is a resampling problem
Avoid aliasing Use filtering
Original
1/4X resolution
4X resolution
Summary
Image representation
A pixel is a sample, not a little square Images have limited resolution
Halftoning and dithering
Reduce visual artifacts due to quantization Distribute errors among pixels Exploit spatial integration in our eye
Sampling and reconstruction
Reduce visual artifacts due to aliasing Filter to avoid undersampling Blurring is better than aliasing
13
