PowerPoint Presentation
12. Image Filtering & Scaling
Dr. Hamish Carr
COMP 5812M: Foundations of Modelling & Rendering
What Is an Image?
An ideal or continuous image is a function
That maps location on the image to intensity
We should also represent wavelength
Or even irradiance:
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
On the Retina
Consider the irradiance on the retina
Integrates all light at that wavelength
Over all incoming directions
If lens is perfect, only one direction counts
But the retina is not continuous
It is made of cells of varying area
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Discrete Retina / Image
Retinal cells are blobs
We will assume a nice square array
i.e. the pixels on the image plane
indexed on i,j
So we can transform this to:
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Colour Response
Each cell has its own response function
, , or
How strongly it responds to wavelength
It may actually vary between cells
So assume we have :
We could even parameterise with time t
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Assumptions
Assume a perfect lens (only one matters)
Assume square pixels (retinal cells)
Assume one wavelength
And assume we are storing as floats
not integers
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Sampling
We never actually compute this
although perhaps we should
Instead, we sample the function
measure the light at the centre of the pixel
Then display the same value across the pixel
And this leads immediately to errors
In particular, aliasing
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Reconstruction
Suppose we measure a function at 10 points
Can we reconstruct the function?
i.e. recover the continuous version
Only if there is a unique representation
And it is easy to show there isn’t
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
1-D Example
Both green and red have the same samples
Which one is right?
The screen does a third thing
Because of hardware
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Aliasing
A general phenomenon
Caused by not enough samples
Reconstruction dominated by error
We know this should be a straight line
But it is jaggy when discretised
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Solution (Goal)
Replace it with a grey-level
Overlap between line of width 1 & pixel
Aliased
Anti-aliased
Far away
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Immediate Use: Fonts
Binary Font
Anti-aliased
Using Greyscale
TrueType
(RGB in different
columns, eg LCD)
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Aliased Motion
Object moves 2 pixels in 4 time steps
But it looks like it speeds up in the middle
Really just the same problem
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Solution
Treat the object as a function itself
Combine the function with the pixel
Object
Pixel
Product
Sample
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Mathematically
Clearly, this varies with the offset
between object and pixel
We express this as a function (of course)
And an operation called convolution
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Convolution
Convolution works with any functions
and has nice mathematical properties
Object
Pixel
Product
Sample
, centred at 0
g, centred at h
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Filtering
Depends on distance from pixel to object
So the overlap varies as the pixel moves
But cost over an image is
N is the number of pixels
M is the size of the filter
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Blurring
Simple trick: filter with a slightly larger area
average all adjacent pixels
But this is just a 3×3 filter!
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Sampling Theory
The next piece of the puzzle
Treats the image like an electrical signal
Or an audio signal
Breaks it down into frequencies
i.e. how rapidly it changes
Expressed with Fourier analysis
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Fourier Analysis
Any periodic function can be broken down
Into a sum of sines & cosines
In the complex plane
Based on our samples
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
But . . .
We will have to assume a band limit
I.e. a maximum spatial frequency
y = sin(x)
y = sin(11x)
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Fourier Transform
Rewrites our function
from a function of x
to a function of : spatial frequency
Expressed as samples:
actually a complex number
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Frequency Filtering
One Row
Fourier Transform
Box Filter
After Filtering
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Results
Taj Mahal
Low Frequency
Mid Frequency
High Frequency
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Sinc Filter
What does this box filter look like?
In the spatial domain
It becomes the sinc filter
Which uses the entire image
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Sampling
Sampling
Function
Taj Mahal
Sampled
Function
Fourier
Transform
Fourier
Transform
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
More generally
Mipmapping is a special case
We need a more general solution
But scaling up & scaling down are different
Scaling up – use the sinc filter if possible
Scaling down – increases the frequency
And no longer band-limited
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Scaling Up
Increasing spatial resolution
Decreasing frequency resolution
Bandwidth limit is preserved
Frequency
Spatial
Original Signal
Rescaled Signal
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Two Dimensions
Just do one dimension at a time
Either order produces same result (separable)
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Terminology
Support of f is interval where it is nonzero
Can be finite (e.g. box) or infinite (e.g. sinc)
Images typically have finite support
So scaling up isn’t usually a problem
And sinc filters preserve detail
Bilinear filtering isn’t as good at this
But textures are more often scaled down
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Scaling Down
We have to add an extra box filter
In order to preserve the bandlimit
Ideal
Optimised
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Boundary Effects
What happens at the image boundary?
Not enough pixels for filter
So we have to invent / assume extra pixels
And each method has it’s side effects
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Boundary Assumptions
We can also limit the reconstruction filter
Or we can cheat & re-weight
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Side-Effects
Extend by Zeroes:
Leads to darkening around edge of image
Extend by Reflection:
Not necessarily realistic
Extend by Constants:
Tends to smear boundary inwards
Finite Support Filter
Impossible to do in both domains at once
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
Band-Limited Filters
We want a wider filter than linear
But not as wide as sinc
Iterate the box (tent) filter multiple times
Leads to cubic B-spline filters
Which we will deal with in Chapter 22
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering
The Standard Hack
Each filter assigns weights to pixels
And should guarantee they sum to 1
(otherwise we lose/gain brightness overall)
Omit filter pixels outside the image
This drops the sum below 1
So divide by the sum of the weights kept
Result: interpolation only uses valid pixels
COMP 5812M: Foundations of Modelling & Rendering
COMP 5812M: Foundations of Modelling & Rendering