COMP9517_24T2W2_Image_Processing_Part_2.pdf

COMP9517 Computer Vision 2024 Term 2 Week 2 Dr Dong Gong Image Processing Part 2 Types of image processing (recap) Two main types of image processing operations: – Spatial domain operations (in image space) Today –...

COMP9517 Computer Vision 2024 Term 2 Week 2 Dr Dong Gong Image Processing Part 2 Types of image processing (recap) Two main types of image processing operations: – Spatial domain operations (in image space) Today – Transform domain operations (mainly in Fourier space) Two main types of spatial domain operations: – Point operations (intensity transformations on individual pixels) – Neighbourhood operations (spatial filtering on groups of pixels) Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 2 Topics and learning goals Describe the principles of the Fourier transform for image processing Forward & inverse transform, convolution theorem, properties, discrete Fourier transform Understand the effects of various Fourier domain filtering methods Filtering procedure, notch filtering, low-pass filtering, high-pass filtering Combine filtering operations to allow multiresolution image processing Difference of Gaussians, image pyramids, approximation, reconstruction Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 3 What is lost when lowering resolution? Downsampling Upsampling Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 4 Jean Baptiste Joseph Fourier (1768-1830) Fourier Had a crazy idea (1807) Any univariate function can be rewritten as a weighted sum of sines and cosines of different frequencies Laplace Don’t believe it? Neither did Lagrange, Laplace, Legendre, and other big wigs Fourier’s idea was not translated into English until 1878 Lagrange “...the manner in which the author arrives at these But it’s (mostly) true! equations is not exempt of difficulties and...his analysis It is now called the Fourier series to integrate them still leaves something to be desired on the score of generality and even rigour.” Legendre There are some subtle restrictions Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 5 Weighted sum of sines Basic building block waves 𝑓! 𝑥 = 𝑎! sin 𝜔! 𝑥 + 𝜑! 𝑎! is the weight (amplitude) 𝜔! is the radial frequency 𝜑! is the phase sum Add enough of them and you can get any signal you want: 𝑓 = 𝑓" + 𝑓# + 𝑓$ + 𝑓% + ⋯ Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 6 Weighted sum of sines https://en.wikipedia.org/wiki/Fourier_series 𝑓# 𝑓$ 𝑓% 𝑓& Approximation of a square wave Approximation of a sawtooth wave Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 7 Spatial versus frequency 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 frequency Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 8 Frequency domain overview High frequencies correspond to rapidly changing intensities across pixel Low frequency components correspond to large-scale image structures Frequency domain image processing via the Fourier transform Fourier Frequency Inverse Fourier transform filtering transform 𝑓(𝑥, 𝑦) 𝐹(𝑢, 𝑣) 𝐹 𝑢, 𝑣 𝐻(𝑢, 𝑣) 𝑔(𝑥, 𝑦) Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 9 Definition of the Fourier transform (1D) Forward Fourier transform Notation " 𝐹 𝑢 = $ 𝑓(𝑥)e!#$%&' 𝑑𝑥 𝑓(𝑥) is the spatial input function !" 𝐹(𝑢) is the Fourier transform Inverse Fourier transform e!'( = cos 𝜔𝑥 + 𝑖 sin 𝜔𝑥 " 𝜔 = 2𝜋𝑢 is radial frequency 𝑓 𝑥 = $ 𝐹(𝑢)e#$%&' 𝑑𝑢 !" 𝑢 is spatial frequency 𝑖 = −1 Uses complex valued sinusoids Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 10 Definition of the Fourier transform (1D) We want to reparametrize the signal 𝑓(𝑥) in the frequency domain by u. " 𝐹 𝑢 = $ 𝑓(𝑥)e!#$%&' 𝑑𝑥 e!"# = cos 𝜔𝑥 + 𝑖 sin 𝜔𝑥 !" For every u, F(u) holds the amplitude A and phase 𝜙 of the corresponding sinusoid (with a specific frequency), 𝐴𝑠𝑖𝑛(𝑢𝑥 + 𝜙). *(,) 𝐹(𝑢) = 𝑅(𝑢) + 𝑖𝐼(𝑢) with 𝐴 = ± 𝑅(𝑢)$ + 𝐼(𝑢)$; 𝜙 = 𝑡𝑎𝑛)#.(,) Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 11 Definition of the Fourier transform (1D) https://zh.wikipedia.org/wiki/File:Fourier_transform_time_and_frequency_do mains_(small).gif Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 12 Properties of the Fourier transform Property Spatial Frequency Superposition 𝑓#(𝑥) + 𝑓$(𝑥) 𝐹#(𝑢) + 𝐹$(𝑢) Translation 𝑓(𝑥 − ∆𝑥) 𝐹(𝑢)e)!$:,∆( Convolution 𝑓 𝑥 ∗ ℎ(𝑥) 𝐹 𝑢 𝐻(𝑢) Correlation 𝑓 𝑥 ⊗ ℎ(𝑥) 𝐹 𝑢 𝐻 ∗ (𝑢) Multiplication 𝑓 𝑥 ℎ(𝑥) 𝐹 𝑢 ∗ 𝐻(𝑢) Scaling 𝑓 𝑎𝑥 𝐹 𝑢/𝑎 /𝑎 Differentiation 𝑓 (=) 𝑥 (𝑖2𝜋𝑢)= 𝐹 𝑢 Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 13 Definition of the Fourier transform (2D) Forward Fourier transform Fourier transform pair " " 𝐹 𝑢, 𝑣 = $ $ 𝑓(𝑥, 𝑦)e!#$% &' ) *+ 𝑑𝑥𝑑𝑦 𝑓↔𝐹 !" !" 𝐹 =𝑅+𝑖𝐼 Real part + Imaginary part Inverse Fourier transform Amplitude " " 𝑓 𝑥, 𝑦 = $ $ 𝐹(𝑢, 𝑣)e #$% &' ) *+ 𝑑𝑢𝑑𝑣 𝑎= 𝑅$ + 𝐼$ !" !" Phase 𝜑 = tan)# 𝐼/𝑅 Uses complex valued sinusoids Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 14 Discrete Fourier transform (DFT) Digital images are discrete 2D functions The discrete Fourier Forward discrete Fourier transform transform and its ?)# A)# inverse always exist ,( D@ )!$: ? C A 𝐹 𝑢, 𝑣 = O O 𝑓(𝑥, 𝑦)e (>" @>" for 𝑢 = 0 … 𝑀 − 1 and 𝑣 = 0 … 𝑁 − 1 Discrete Fourier transform basis 𝑥 𝒖 Inverse discrete Fourier transform 𝑦 ?)# A)# 1 !$: ,( D@ 𝑓(𝑥, 𝑦) = O O 𝐹(𝑢, 𝑣)e ?C A 𝑀𝑁 𝒗 ,>" D>" for 𝑥 = 0 … 𝑀 − 1 and 𝑦 = 0 … 𝑁 − 1 Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 15 2D Discrete Fourier transformer 1D Fourier transformer: & 𝐹 𝑢 = Q 𝑓(𝑥)e%!'($# 𝑑𝑥 e!$# = cos 𝑢𝑥 + 𝑖 sin 𝑢𝑥 %& 2D Fourier transformer: +%,.%, %!'( $# 1- 0 e!($#01-) = cos 𝑢𝑥 + 𝑣𝑦 + 𝑖 sin 𝑢𝑥 + 𝑣𝑦 𝐹 𝑢, 𝑣 = U U 𝑓(𝑥, 𝑦)e +. #)* -)* Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 16 2D Discrete Fourier transformer Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 17 Discrete Fourier transform (DFT) 2D Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 18 Discrete Fourier transform (DFT) 2D Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 19 Frequency domain filtering Each 𝐹(𝑢, 𝑣) depends on all 𝑓 𝑥, 𝑦 , 𝑥 = 0 … 𝑀 − 1, 𝑦 = 0 … 𝑁 − 1 Frequencies in the Fourier domain correspond to patterns in the image The value of 𝐹(0,0) is the average intensity over all pixels of the image Low frequencies correspond to slowly varying intensities across pixels High frequencies correspond to rapid intensity changes across pixels Noise typically corresponds to fluctuations in the highest frequencies Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 20 Frequency domain filtering Fourier images are typically centred for visualisation and processing Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 21 Frequency domain filtering Centering the Fourier images means multiplying the spatial images by −1 (C@ #$ % '$ ( !$: C ) Translation property: 𝐹 𝑢 − 𝑢", 𝑣 − 𝑣" ↔ 𝑓(𝑥, 𝑦)e & Centering by translation over: 𝑢" = 𝑀/2 and 𝑣" = 𝑁/2 Substitution yields: 𝐹 𝑢 − 𝑀/2, 𝑣 − 𝑁/2 ↔ 𝑓(𝑥, 𝑦)e!: (C@ Which boils down to: 𝑓 𝑥, 𝑦 cos 𝜋 𝑥 + 𝑦 + 𝑖 sin 𝜋 𝑥 + 𝑦 = 𝑓(𝑥, 𝑦) −1 (C@ = −1 or 1 =0 𝑥 + 𝑦 has integer value Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 22 Procedure for frequency domain filtering 1. Multiply the input image 𝑓(𝑥, 𝑦) by −1 (C@ to ensure centering 𝐹(𝑢, 𝑣) 2. Compute the transform 𝐹(𝑢, 𝑣) from image 𝑓(𝑥, 𝑦) using the 2D DFT 3. Multiply 𝐹(𝑢, 𝑣) by a centred filter 𝐻(𝑢, 𝑣) to obtain the result 𝐺(𝑢, 𝑣) 4. Compute the inverse DFT of 𝐺(𝑢, 𝑣) to obtain the spatial result 𝑔(𝑥, 𝑦) 5. Take the real component of 𝑔(𝑥, 𝑦) (the imaginary component is zero) 6. Multiply the result by −1 (C@ to remove the pattern introduced in 1. Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 23 Example: low-pass filtering 1. Multiply the input image 𝑓(𝑥, 𝑦) by −1 (C@ to ensure centering 𝐹(𝑢, 𝑣) Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 24 Example: low-pass filtering 2. Compute the transform 𝐹(𝑢, 𝑣) from image 𝑓(𝑥, 𝑦) using the 2D DFT Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 25 Example: low-pass filtering 3. Multiply 𝐹(𝑢, 𝑣) by a centred filter 𝐻(𝑢, 𝑣) to obtain the result 𝐺(𝑢, 𝑣) × Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 26 Example: low-pass filtering 3. Multiply 𝐹(𝑢, 𝑣) by a centred filter 𝐻(𝑢, 𝑣) to obtain the result 𝐺(𝑢, 𝑣) Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 27 Example: low-pass filtering 4. Compute inverse DFT 5. Take real component 6. Multiply by −1 (C@ Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 28 Example: low-pass filtering The resulting low-pass filtered image is a smoothed version of the original Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 29 Example: notch filtering Satellite image showing Result image using the scanline artifacts notch reject filter Fourier transform of Noise pattern captured the satellite image by the notch pass filter Notch pass filter Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 30 Exploiting the convolution theorem Filtering in the frequency domain can be computationally more efficient Designing filters can be more intuitive in the frequency domain Low-pass filter: keep low frequencies but attenuate high frequencies High-pass filter: keep high frequencies but attenuate low frequencies Band-pass filter: keep frequencies in a given band and attenuate the rest Take the inverse transform to get the corresponding spatial filter Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 31 Gaussian filter (low-pass) The Fourier transform of a Gaussian is a Gaussian 54 ! % 4 %"# 4 $ 4 &4 1D: ℎ 𝑥 = e 46 ↔ 𝐻 𝑢 = e "#$ 4 54 7 8 4 ! % 4 $4 &4 ( ) 4 2D: ℎ 𝑥, 𝑦 = 4e 464 ↔ 𝐻 𝑢, 𝑣 = e%"# "#$ 4 ! */" %59 7 … 7 54; 4 $4 &94 ( … ( &; 4 nD: ℎ 𝑥! , … , 𝑥* = e 4 46 ↔ 𝐻 𝑢! , … , 𝑢* = e%"# "#$ 4 Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 32 Difference of Gaussian filter (high-pass) Approximation of an inverted Laplacean filter DoG 𝑥 = 𝑎! ℎ 𝑥; 𝜎! − 𝑎" ℎ 𝑥; 𝜎" ↔ DoG 𝑢, 𝑣 = 𝑎#𝐻 𝑢; 𝜎# − 𝑎$𝐻 𝑢; 𝜎$ Gaussian DoG Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 33 What is lost when lowering resolution? Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 34 Multiresolution image processing Small objects and fine details benefit from high resolution Large objects and coarse structures can make do with lower resolution If both are present at the same time, multiple resolutions may be useful This requires computing image pyramids Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 35 Creating image pyramids 1. Compute an approximation of the input image by filtering and downsampling 2. Upsample the output of step 1 and filter the result (interpolation) 3. Compute the difference between the prediction of step 2 Repeating this produces an approximation and prediction residual pyramid and the input to step 1 Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 36 Example To reconstruct the image: Approximation pyramid 1. Upsample and filter the lowest resolution approximation image 2. Add the one-level higher prediction Residual pyramid residual Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 37 Further reading on discussed topics Chapter 4 of Gonzalez and Woods 2002 Sections 3.4-3.5 of Szeliski 2010 Acknowledgement Some images drawn from the above resources Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 38 Example exam question Which one of the following statements on image filtering is incorrect? A. Median filtering reduces noise in images. B. Low-pass filtering results in blurry images. C. High-pass filtering smooths fine details in images. D. Notch filtering removes specific image frequencies. Copyright (C) UNSW COMP9517 24T2W2 Image Processing Part 2 39