COMP 9517 Computer Vision Image Processing (Part 2)
22.02.2021 COMP 9517 T1,2021 1
Image Processing Recap
Spatial domain, intensity transformations (on single pixels)
26.02.2020
• Image thresholding
• Otsu’s method
• Balanced histogram thresholding
• Multi-band thresholding
• Image negative
• Log transform • Power-law
COMP 9517 T1, 2020 2
Image Processing Recap
Spatial domain, intensity transformations (on single pixels) :
26.02.2020
• Piecewise-linear transformation
• Contrast stretching
• Gray-level slicing
• Bit-plane slicing
• Histogram processing
• Histogram equalization
• Histogram matching
• Arithmetic/Logic Operations
COMP 9517 T1, 2020 3
Image Processing Recap
Spatial Filtering (on neighbourhoods)
• Smoothing Filters: averaging, Gaussian
• Order-statistics Filters: median, min, max
26.02.2020
COMP 9517 T1, 2020 4
• Sharpening Filters
• Gradient
• Laplacian
• Combining filters
• Padding
Frequency Domain Techniques
Goal:
• to gain working knowledge of Fourier transform
and frequency domain for use in IP
• focus on fundamentals and relevance to IP
• not signal processing expertise!
22.02.2021 COMP 9517 T1,2021 5
Why does a lower resolution image still make sense to us? What do we lose?
22.02.2021 COMP 9517 T21,20210 6
Image: http://www.flickr.com/photos/igorms/136916757/ Slide: Hoiem
Jean Baptiste Joseph Fourier (1768-
1830)
…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.
had crazy idea (1807):
•
Any univariate function can be rewritten as a weighted sum of sines and cosines of different frequencies.
Don’tbelieveit?
– Neither did Lagrange, Laplace, Poisson and other big wigs
– Nottranslatedinto English until 1878!
But it’s (mostly) true!
– called Fourier Series
– there are some subtle
restrictions
Laplace
•
22.02.2021
COMP 9517 T21,20210
Lagrange
Legendr
7
e
A sum of sines Our building block:
Asin(x Add enough of them to get
any signal g(x) you want!
22.02.2021 COMP 9517 T12,20210 8
Frequency Versus Spatial Domain
• Spatial domain
– the image plane itself
– direct manipulation of pixels
– changes in pixel position correspond to changes in
the scene
• Frequencydomain
– 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
22.02.2021 COMP 9517 T21,20210 9
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
• Frequencydomain
– defined by values of the Fourier transform and its
frequency variables (u, v)
22.02.2021 COMP 9517 T21,20210 10
Frequency Domain Overview • Frequency domain processing
2 2 . 0 2 . 2 0 2 1 C C O O M M P P 9 9 5 5 1 1 7 7 T T 21 , , 2 2 0 0 2 2 1 0 1 1 1 1
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 =
22.02.2021 COMP 9517 T12,20210 12
A sum of sines
https://en.wikipedia.org/wiki/File:Fourier_series_square_wave_circles_animation.gif https://en.wikipedia.org/wiki/File:Fourier_series_sawtooth_wave_circles_animation.gif
22.02.2021 COMP 9517 T21,20210 13
A sum of sines
https://zh.wikipedia.org/wiki/File:Fourier_transform_time_and_frequency_domains_(small).gif
22.02.2021 COMP 9517 T12,20210 14
One-Dim Fourier Transform and its
Inverse
For a single variable continuous function f(x), the
Fourier transform F(u) is defined by:
F(u) = f(x) exp(-j2ux) dx (1)
where: transform:
j 1
Given F(u), we recover f(x) using the inverse Fourier
f(x) = F(u) exp(j2ux) du (2)
(1) and (2) constitute a Fourier transform pair
22.02.2021 COMP 9517 T21,20210 15
Two-Dim Fourier Transform and Inverse • In two dimensions, we have:
F(u,v)= f(x,y)exp(-j2(uxvy))dxdy -
f(x,y)= F(u,v)exp(j2(uxvy))dudv -
(3) (4)
22.02.2021 COMP 9517 T12,20210
16
Discrete Fourier Transform • Inonedimension,
F(u)=
for u = 0,1,2,…,M-1 (5)
f(x)=
for x = 0,1,2,…,M-1 (6)
• Notethatthelocationof1/Mdoesnotmatter,so
long as the product of the two multipliers is 1/M
• Alsointhediscretecase,theFouriertransform and its inverse always exist
22.02.2021 COMP 9517 T21,20210 17
Discrete Fourier Transform
• Consider Euler’s formula:
• Substituting this expression into (5), and noting
, we obtain
1 M 1
F(u)=Mf(x)[cos2ux/M-jsin2ux/M], foru0,1,2,,M-1. (8)
x0
• 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.
22.02.2021 COMP 9517 T21,20210 18
2-D Discrete Fourier Transform • Digitalimagesare2-Ddiscretefunctions:
22.02.2021 COMP 9517 T12,20210 19
Frequency Domain Filtering
• Frequencyisdirectlyrelatedtorateofchange,so frequencies in the Fourier transform may be related to patterns of intensity variations in the image.
• Slowestvaryingfrequencyatu=v=0correspondsto average gray level of the image.
• Lowfrequenciescorrespondtoslowlyvarying components in the image- for example, large areas of similar gray levels.
• Higherfrequenciescorrespondtofastergraylevel changes- such as edges, noise etc.
22.02.2021 COMP 9517 T12,20210 20
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
22.02.2021 COMP 9517 T21,20210 21
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 filte
22.02.2021 COMP 9517 T12,20210 22
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)andF(u,v)H(u,v)constituteaFourier transform pair , i.e. spatial convolution (LHS) can be obtained by taking the inverse transform of RHS, and conversely, the RHS can be obtained as the forward Fourier transform of LHS.
– Analogously, convolution in the frequency domain reduces to multiplication in the spatial domain, and vice versa.
• Using this theorem, we can also show that filters in the spatial and frequency domains constitute a Fourier transform pair.
22.02.2021 COMP 9517 T12,20210 23
Exploiting the correspondence
• Iffiltersinthespatialandfrequencydomainsareof the same size, then filtering is more efficient computationally in frequency domain.
• However,spatialfilterstendtobesmallerinsize.
• Filteringisalsomoreintuitiveinfrequencydomain-
so design it there.
• Then,taketheinversetransform,andusethe resulting filter as a guide to design smaller filters in the spatial domain.
22.02.2021 COMP 9517 T12,20210 24
Example of Smoothing an Image
• Inspatialdomain,wejustconvolvetheimagewitha Gaussian kernel to smooth it
• Infrequencydomain,wecanmultiplytheimagebya filter achieve the same effect
22.02.2021 COMP 9517 T12,20210 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
22.02.2021 COMP 9517 T12,20210 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
22.02.2021 COMP 9517 T12,20210 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 result by (-1)x+y
22.02.2021 COMP 9517 T12,20210 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
22.02.2021 COMP 9517 T12,20210 29
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
f (x, y)* g(x, y)
F(u, v)G(u, v)
https://docs.opencv.org/master/de/dbc/tutorial_py_fourier_transform.html
COMP 9517 T12,20210 30
22.02.2021
• •
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 Aexp222×2
This is usually a lowpass filter.
•
•
22.02.2021 COMP 9517 T12,20210 31
DoG Filter
• Difference of Gaussians may be used to construct highpass filters:
u2 u2 H(u)=Aexp 212 Bexp 22
withAB andδ1 >δ2.
• The corresponding filter in the spatial domain is
h(x)= 21 Aexp2212×2 22 Bexp222×2 22.02.2021 COMP 9517 T12,20210 32
Why does a lower resolution image still make sense to us? What do we lose?
22.02.2021 COMP 9517 T12,20210 33
Image: http://www.flickr.com/photos/igorms/136916757/ Slide: Hoiem
Multiresolution Processing
• Smallobjects,lowcontrastbenefitfromhigh resolution
• Largeobjects,highcontrast,canmakedowithlower resolution
• Ifbothpresentatthesametime,multiple resolutions may be useful
• Localstatisticssuchasintensityaveragescanvaryin different parts of an image
• Exploitthisinmultiresolutionprocessing
22.02.2021 COMP 9517 T21,20210 34
Image Pyramids
• An image pyramid is a collection of decreasing resolution images arranged in the shape of a pyramid.
22.02.2021 COMP 9517 T12,20210 35
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
22.02.2021 COMP 9517 T12,20210 36
Image Pyramids
Two image pyramids and their statistics (Gaussian approx pyramid, Laplacian prediction residual pyramid)
To recreate image
–
–
22.02.2021
Upsample and filter the lowest resolution approximation image
Add the 1-level higher Laplacian’s prediction residual
COMP 9517 T12,20210 37
References and Acknowledgement
• Gonzalez and Woods, 2002, Chapter 3.5-3.8
• Gonzalez and Woods, 2002, Chapter 4.1-4.4, 7.1 • SzeliskiChapter3.1-3.5
• Somematerial,includingimagesandtables,weredrawn from the textbook, Digital Image Processing by Gonzalez and Woods, and P.C. Rossin’s presentation.
22.02.2021 COMP 9517 T12,20210 38