Computer Vision
Image Processing II
1
Recap
• Spatial domain, intensity transformations (on single pixels)
• Image thresholding
• Otsu’s method
• Balanced histogram thresholding
• Multi-band thresholding
• Image negative
• Log transform
• Power-law
• Piecewise-linear transformation
• Contrast stretching
• Gray-level slicing
• Bit-plane slicing
• Histogram processing
• Histogram equalization
• Histogram matching
2
Recap
• Spatial domain, intensity transformations (on single pixels)
• Histogram processing
• Histogramequalization • Histogrammatching
• Arithmetic/Logic Operations • +,-,AND,OR,XOR
• Image averaging
• Spatial Filtering (using neighbouring pixels) • Smoothing
• GaussianFilter • MedianFilter • Pooling
• Laplacian
• Padding
3
Frequency Domain Techniques
Goal:
• to gain working knowledge of Fourier transform and
frequency domain for use in Image Processing
• focus on fundamentals and relevance to Image Processing
• not signal processing expertise!
4
Jean Baptiste Joseph Fourier (1768-1830)
had crazy idea (1807):
Any univariate function can be rewritten as a weighted sum of sines and cosines of different frequencies.
• Don’t believe it?
– Neither did Lagrange, Laplace, Poisson
and other big wigs
– Not translated into English until 1878!
• But it’s (mostly) true!
– called Fourier Series
– there are some subtle restrictions
…the manner in which the author arrives at these equations is not exempt of difficulties and…his analysis to integrate them still leaves something to be desired on the score of generality and even rigour.
Laplace
Lagrange
Legendre
5
A sum of sines
Our building block:
Asin(x+)
Add enough of them to get any signal g(x) you want!
6
Frequency VS Spatial Domain
• Spatial domain
–the image plane itself
–direct manipulation of pixels
–changes in pixel position correspond to changes in the scene
• Frequency domain
–Fourier transform of an image
–directly related to rate of changes in the image
–changes in pixel position correspond to changes in the spatial frequency
7
Frequency Domain Overview
• Frequency in image
–high frequencies correspond to pixel values that change rapidly
across the image
–low frequency components correspond to large scale features in the image
• Frequency domain
–defined by values of the Fourier transform and its frequency variables (u, v)
8
Frequency Domain Overview
Frequency domain processing
9
Fourier Series
• Periodic function can be represented as a weighted sum of sines and cosines of different frequencies
• Even functions that are not periodic (but whose area under the curve is finite) can be expressed as the integral of sines and/or cosines multiplied by a weight function
sum =
10
Sum of Sines
11
1-D Fourier Transform and its Inverse
For a single variable continuous function f(x), the Fourier Transform
F(u) is defined by:
)1( 𝑥𝑑𝑥𝑢𝜋𝑗2−𝑒 𝑥 𝑓 ∞ = )F(u ∞−
where:j= −1
Given F(u), we recover f(x) using the Inverse Fourier Transform:
)2( 𝑢𝑑𝑥𝑢𝜋𝑒𝑗2 𝑢 𝐹 ∞ = )f(x ∞−
(1) and (2) constitute a Fourier transform pair
13
2-D Fourier Transform and its Inverse
In two dimensions, we have:
∞∞
𝐹 𝑢,𝑣 = න න 𝑓 𝑥,𝑦 𝑒−𝑗2𝜋(𝑢𝑥+𝑣𝑦)𝑑𝑥 𝑑𝑦 (3) −∞ −∞
∞∞
𝑓 𝑥,𝑦 = න න 𝐹 𝑢,𝑣 𝑒𝑗2𝜋(𝑢𝑥+𝑣𝑦)𝑑𝑢𝑑𝑣 (4) −∞ −∞
14
Discrete Fourier Transform
• In one dimension,
F u = 1 σ𝑀−1 𝑓 𝑥 𝑒−𝑗2𝜋𝑢𝑥 for u = 0,1,2,…,M-1 (5)
𝑀𝑥=0 𝑀
f x = σ𝑀−1 𝐹 𝑢 𝑒𝑗2𝜋𝑢𝑥 for x = 0,1,2,…,M-1 (6) 𝑢=0 𝑀
• Note that the location of 1/M does not matter, so long as the product of the two multipliers is 1/M
• Also in the discrete case, the Fourier transform and its inverse always exist
15
Discrete Fourier Transform
Consider Euler’s formula:
𝑒𝑗𝜃=cos𝜃 +𝑗sin𝜃
Substituting this expression into (5), and noting cos −𝜃 = cos(𝜃), we obtain
𝐹 𝑢 = 1 σ𝑀−1𝑓(𝑥) cos2𝜋𝑢𝑥 −𝑗sin2𝜋𝑢𝑥 𝑀𝑥=0 𝑀 𝑀
(7)
foru=0,1,2,…,M-1 (8) • Each term of F depends on all values of f(x), and values of f(x) are multiplied
by sines and cosines of different frequencies.
• The domain over which values of F(u) range is called the frequency domain, as u determines the frequency of the components of the transform.
16
2-D Discrete Fourier Transform
Digital images are 2-D discrete functions:
1 𝑀−1 𝑁 𝑢𝑥 𝑣𝑦 𝐹𝑢,𝑣 =𝑀𝑁𝑓𝑥,𝑦 𝑒−𝑗2𝜋 𝑀+𝑁
𝑥=0 𝑦=0
𝑓𝑜𝑟 𝑢 = 0,1,2, … , 𝑀 − 1 𝑎𝑛𝑑 𝑣 = 0,1,2, … , 𝑁 − 1. (9)
𝑀−1𝑁−1 𝑢𝑥 𝑣𝑦
𝑓𝑥,𝑦 = 𝐹𝑢,𝑣𝑒𝑗2𝜋 𝑀+𝑁 𝑢=0 𝑦=0
𝑓𝑜𝑟 𝑥 = 0,1,2, … , 𝑀 − 1 𝑎𝑛𝑑 𝑦 = 0,1,2, … , 𝑁 − 1. (10)
17
Frequency Domain Filtering
• Frequency is directly related to rate of change, so frequencies in the Fourier transform may be related to patterns of intensity variations in the image.
• Slowest varying frequency at u = v = 0 corresponds to average gray level of the image.
• Low frequencies correspond to slowly varying components in the image- for example, large areas of similar gray levels.
• Higher frequencies correspond to faster gray level changes- such as edges, noise etc.
18
Procedure for Filtering in the Frequency Domain
1. Multiply the input image by (-1)x+y to centre the transform at (M/2, N/2), which is the centre of the MxN area occupied by the 2D DFT
2. Compute the DFT F(u,v) of the resulting image
3. Multiply F(u,v) by a filter H(u,v)
4. Compute the inverse DFT transform g*(x,y)
5. Obtain the real part g(x,y)
6. Multiply the result by (-1)x+y
20
Example: Notch Filter
• We wish to force the average value of an image to zero. We can achieve this by setting F(0, 0) =0, and then taking its inverse transform.
• So choose the filter function as:
H(u,v)=0if (u,v)=(M/2,N/2)
H (u, v) = 1 otherwise.
• Called the notch filter- constant function with a hole (notch) at the origin.
• A filter that attenuates high frequencies while allowing low frequencies to pass through is called a lowpass filter.
• A filter that attenuates low frequencies while allowing high frequencies to pass through is called a highpass filter
21
Convolution Theorem: correspondence between spatial and frequency domain filtering
Let F(u, v) and H( u, v) be the Fourier transforms of f(x, y) and h(x,y). Let * be spatial convolution, and multiplication be element-by-element product. Then
• f(x, y) * h(x, y) and F(u, v) H(u, v) constitute a Fourier transform pair • Analogously, convolution in the frequency domain reduces to
multiplication in the spatial domain, and vice versa.
(𝑓∗h)(𝑡)⟺(𝐻 ∙𝐹)(𝑢)
(𝑓∙h)(𝑡)⟺(𝐻 ∗𝐹)(𝑢)
Using this theorem, we can also show that filters in the spatial and frequency domains constitute a Fourier transform pair.
23
Exploiting the correspondence
• If filters in the spatial and frequency domains are of the same size, then filtering is more efficient computationally in frequency domain.
• However, spatial filters tend to be smaller in size.
• Filtering is also more intuitive in frequency domain- so design it
there.
• Then, take the inverse transform, and use the resulting filter as a guide to design smaller filters in the spatial domain.
24
Example of Smoothing an Image
• In spatial domain, we just convolve the image with a Gaussian kernel to smooth it
• In frequency domain, we can multiply the image by a filter achieve the same effect
25
Example of Smoothing an Image
1.Multiply the input image by (-1)x+y to center the transform
2.Compute the DFT F(u,v) of the resulting image 3.Multiply F(u,v) by a filter G(u,v)
4.Computer the inverse DFT transform h*(x,y) 5.Obtain the real part h(x,y) of 4
6.Multiply the result by (-1)x+y
26
Example of Smoothing an Image
1.Multiply the input image by (-1)x+y to center the transform
2.Compute the DFT F(u,v) of the resulting image
3.Multiply F(u,v) by a filter G(u,v)
4.Computer the inverse DFT transform h*(x,y) 5.Obtain the real part h(x,y) of 4
6.Multiply the result by (-1)x+y
27
Example of Smoothing an Image
1.Multiply the input image by (-1)x+y to center the transform 2.Compute the DFT F(u,v) of the resulting image
3.Multiply F(u,v) by a filter G(u,v)
4.Computer the inverse DFT transform h*(x,y)
5.Obtain the real part h(x,y) of 4 6.Multiply the rХesult by (-1)x+y
28
Example of Smoothing an Image
1. Multiply the input image by (-1)x+y to center the transform 2. Compute the DFT F(u,v) of the resulting image
3. Multiply F(u,v) by a filter G(u,v)
4.Compute the inverse DFT transform h*(x,y) 5.Obtain the real part h(x,y)
6.Multiply the result by (-1)x+y
Gaussian Filter
• Gaussian filters are important because their shapes are easy to specify, and both the forward and inverse Fourier transforms of a Gaussian function are real Gaussian functions.
• Let H(u) be a one dimensional Gaussian filter specified by: − u2
H(u)=Aexp 22
• where σ is the standard deviation of the Gaussian curve.
• The corresponding filter in the spatial domain is
h(x)= 2 Aexp−222×2
• This is usually a lowpass filter.
30
Difference of Gaussian – DoG Filter
• Difference of Gaussians may be used to construct highpass filters: − u2 − u2
H(u)=Aexp 212 −Bexp 22 withABandσ1 >σ2.
• The corresponding filter in the spatial domain is
h(x)= 21 Aexp−2212×2 − 22 Bexp−222×2
31
Why does a lower resolution image still make sense to us? What do we lose?
32
Multiresolution Processing
• Small objects, low contrast benefit from high resolution
• Large objects, high contrast, can do with lower resolution
• If both present at the same time, multiple resolutions may be useful
• Local statistics such as intensity averages can vary in different parts of an image
• Exploit this in multiresolution processing
33
Image Pyramids
• An image pyramid is a collection of decreasing resolution images arranged in the shape of a pyramid.
34
Image Pyramids
System block diagram for creating image pyramids
1. Compute a reduced-resolution approximation of the input image by filtering and downsampling (mean, Gaussian, subsampling)
2. Upsample the output of step 1 and filter the result (possibly with interpolation)
3. Compute the difference between the prediction of step 2 and the input to step 1
Repeating, produce approximation and prediction residual pyramids
35
Image Pyramids
Two image pyramids and their statistics (Gaussian approx pyramid, Laplacian prediction residual pyramid)
To recreate image
– Upsample and filter the lowest resolution approximation image – Add the 1-level higher Laplacian’s prediction residual
36
References and Acknowledgement
• Gonzalez and Woods, 2002, Chapter 4.1-4.4, 7.1
• Szeliski Chapter 3.1-3.5
• Some material, including images and tables, were drawn from the textbook, Digital Image Processing by Gonzalez and Woods, and P.C. Rossin’s presentation.
37