Linear Filters, Smoothing

& Edge Detection

Linear filters, smoothing & edge detection 1

 Image Filtering

• Images that are acquired usually need to be processed

before we can use them.
• Images may be corrupted by:
– Random variations in intensity,
– Variations in illumination
– Poor contrast

Linear filters, smoothing & edge detection 2

Poor illumination, blotches, wear

bad good
Linear filters, smoothing & edge detection 3
 Poor illumination

bad good

Linear filters, smoothing & edge detection 4

 Noise

bad good

Linear filters, smoothing & edge detection 5

Inhomogeneous illumination

bad good

Linear filters, smoothing & edge detection 6

Blurring, poor contrast

bad good

Linear filters, smoothing & edge detection 7

 Histogram Equalization

• Images contain unevenly distributed gray values.

• All intensity values lie within a small range.
• In histogram equalization, we stretch the contrast of
such images by uniformly distributing the gray values.
• Helps when the image is to be viewed by humans.

Linear filters, smoothing & edge detection 8

Histogram Equalization

As is Histogram Equalized

Linear filters, smoothing & edge detection 9

 How does it work?

• One way of performing histogram equalization is via

image scaling: the pixels in the range [a,b] are
expanded to fill the range [z1,zk]

zk − z1
z'= ( z − a) + z1
b−a
zk − z1 z1b − zk a
z' = z+
b−a b−a

Linear filters, smoothing & edge detection 10

Noise & Smoothing

Linear filters, smoothing & edge detection 11

 Smoothing by averaging

• Think of noise as a random value, with an average

value of zero.
• If we average pixels in a local neighborhood, it should
in theory average out the noise.
• This process is known as smoothing or blurring.
• It turns out that it is not a very good model for
blurring.
• Rather consider blurring using a Gaussian.

Linear filters, smoothing & edge detection 12

 Smoothing by averaging

Original image Blurring (averaging) Blurring (Gaussian)

Linear filters, smoothing & edge detection 13

Smoothing with a Gaussian

Normalizes the integral

over the whole plane = 1

1 ⎛ (x 2 + y 2)⎞
Gσ (x, y) = exp⎜⎜− ⎟
⎟
2πσ ⎝ 2 σ 2
⎠

Standard deviation
(pixels)

Linear filters, smoothing & edge detection 14

 Effect of varying σ
• When σ is small:
– smoothing has little effect
• When σ is large: 2 k+
– Consensus of neighborhood 1 2 k+1
– Noise largely suppressed
– Good estimate of pixel’s value
• A discrete smoothing kernel: Choose σ carefully

H ij =
1 ⎜
exp −
( (
⎛ i − k −1 2 + j − k −1 2
) ( ) ) ⎞
⎟
2πσ ⎜ 2σ 2 ⎟
⎝ ⎠
Linear filters, smoothing & edge detection 15
Effect of varying σ
Degree of added noise

Degree of smoothing
Linear filters, smoothing & edge detection 16
Linear, Space-Invariant
(LSI) systems

Linear filters, smoothing & edge detection 17

 Linear Space Invariant system

• Space invariant: the response to a translated stimulus is

a TRANSLATION of the response to the stimulus.

Input Image LSI system Output image

f(x,y) g(x,y) h(x,y)

• Linear è Superposition holds:

a. f1 ( x, y ) + b. f 2 ( x, y ) ⇒ a.h1 (x, y )+ b.h2 (x, y )

Linear filters, smoothing & edge detection 18

 Linear Systems & Impulse response

• For a linear system, when the input to the system is an

impulse centered at the origin, the output g(x,y) is the
system’s impulse response.

Input Output
Linear system
δ(x,y) g(x,y)

Linear filters, smoothing & edge detection 19

 LSI & Convolution

• The response of an LSI to a stimulus is obtained by

convolution.
• The output image h(x,y) of a system f(x,y) to an impulse
stimulus is the convolution (denoted by `*’) of f(x,y)
with the impulse response g(x,y)

h(x, y) = f (x, y)* g(x ', y')

∞ ∞
= ∫ ∫
−∞ −∞
f (x ', y')g(x − x ', y − y')dx 'dy'

Linear filters, smoothing & edge detection 20

 Discrete convolutions

• If f and h are images, convolution becomes the

computation of weighted sums of image pixels.

h [i, j ] = f [i, j ] * g [ k, l ]
n m
= ∑∑ f [k, l ] g [i − k, j − l ]
k=1 l=1

Linear filters, smoothing & edge detection 21

 Linear filters & Convolution
• By manipulating an image, we can extract different
images representing various information.
(2k+1) x (2k+1) window called kernel
For example:
u= i+k v= j +k
1
hij = ∑ ∑f
(2k + 1)
2 uv
u= i− k v= j−k

Output image Input image

Linear filters, smoothing & edge detection 22

 Convolution
• The pattern of the weights used for a linear filter is
referred to as the kernel of the filter.
• The process of applying the filter is referred to as
convolution.

hij = ∑ g i− u, j−v f u,v

u,v

Output pixel Kernel pixel Input pixel

Linear filters, smoothing & edge detection 23

 Convolution mask
• The impulse response g[i,j] is known as the convolution
mask.
• For each pixel [i,j], the value h[i,j] is found by
translating the convolution mask to pixel [i,j] and then
taking the weighted sum of the pixels in the
neighborhood.
• The individual weights are the corresponding values in
the convolution mask.

h[i, j ] = Ap1 + Bp2 + Cp3 + Dp4 + Ep5 + Fp6 + Gp7 + Hp8 + Ip9

Linear filters, smoothing & edge detection 24

 Linear filtering

• The output of a convolution is shift invariant and

linear:
– Shift invariant: output depends on the pattern in the
image neighborhood, rather than the position of the
neighborhood.
– Linear: the output for the sum of two images is the
same as the sum of the outputs obtained for the
images separately.

Linear filters, smoothing & edge detection 25

 Intuitive explanation of convolution

• Best understood as a summation of responses of a

system to impulse responses.

EXPLANATION NEXT…

Linear filters, smoothing & edge detection 26

 Impulse response

• As an example, consider the system described by the

differential equation:

y( t ) + y( t ) + y( t ) = f ( t )

output input

• When f(t) is the impulse at time (t = 0), we refer to the

output as the impulse response and write it as h(t).

Linear filters, smoothing & edge detection 27

 Impulse response
• The impulse response for the above differential equation
is:

⎛ ⎞
⎜ ⎟
⎜ 1 −0.5t ⎛ 3 ⎟⎞
h(t ) = e sin ⎜ t ⎟⎟ , t > 0
⎜
⎜ 3 4 ⎠⎟
⎜ ⎝ ⎟
⎝ 4 ⎠

Linear filters, smoothing & edge detection 28

 Response to arbitrary functions

• We have learned methods to

find the response of a system to
an impulse, step, ramp, or even
a sinusoid input.
• The QUESTION here is how
can we find the response of a
system to an arbitrary input?

Linear filters, smoothing & edge detection 29

 Convolution – sum of impulse
responses…

• Let us first represent the

above input signal in
discrete form by sampling it
every 0.8s.

Linear filters, smoothing & edge detection 30

 Discrete convolution

• Next replace every pulse by

its corresponding impulse.

Linear filters, smoothing & edge detection 31

Impulse response

Linear filters, smoothing & edge detection 32

 Discrete convolution

• Next, we assume
superposition holds and that
the response of a system to a
string of impulses is just the
sum of response to the
individual impulses.

Linear filters, smoothing & edge detection 33

 Discrete convolution
• The response of system to a unit impulse is:
δ (t ) → h(t )
• If the impulse is delayed by i.Δt is:

δ (t − iΔt ) → h(t − iΔt )

• If the impulse has an area A:

δ (t − iΔt ) → Ah(t − iΔt )

Linear filters, smoothing & edge detection 34
 Discrete convolution
• The height of the input function at time i.Δt is:

f (iΔt )
• The area of the impulse at time i.Δt is:

f (iΔt )Δt
• Therefore, the delayed and shifted response is:

response = Ah(t − iΔt ) = f (iΔt )(Δt )h(t − iΔt )

Linear filters, smoothing & edge detection 35
 Discrete convolution

• The response to a series of impulses is therefore

Area of the ith
impulse
∞
y (t ) = ∑ ( f (iΔt )Δt )h(t − iΔt )
i =1

Output Time delay Output

of impulse

Linear filters, smoothing & edge detection 36

 Discrete convolution

• If we take the limit at Δt goes to zero:

iΔt → τ
Δt → dτ

+∞
y (t ) = ∫ f (τ )h(t − τ )dτ
0

Linear filters, smoothing & edge detection 37

 Discrete convolution

• We can also flip the order of the functions as follows:

+∞ +∞

∫
0
f (τ )h(t − τ )dτ = ∫ h(τ ) f (t − τ )dτ
0

• Recall in the context of images:

hij = ∑ g i− u, j−v f u,v

u,v

Linear filters, smoothing & edge detection 38

Summing up the response

Linear filters, smoothing & edge detection 39

 Discrete convolution -
increasing the sampling rate dt = 0.3

Linear filters, smoothing & edge detection 40

 Solving problem: filtering with
kernels Analytical (no CV2)
Use this blurring kernel, to manually apply a
conv filter on an image4

Multiply the kernel values with ROI region, and

use [Link]

Since the kernel has a 3x3 dimension leave 1

pixel intact at the edge of the original image

Linear filters, smoothing & edge detection Slide 41

 Lab exercise :Blurring cv2
Use cv2 functions for blurring
Average blurring [Link](image, (15, 15))
Kernel size (15, 15)

Gaussian Blur [Link](image, (15, 15), 0)

(source image, (kernel width, kernel height), sigma)

Median Blur [Link](image, 5) Kernel size 5

Add Sliders to observe interactive

results

Linear filters, smoothing & edge detection Slide 42

Lab exercise: Kernels and 2d Filters

Choose a kernel, and use cv2.filter2d, to apply

filter

Linear filters, smoothing & edge detection Slide 43

 Finding edges
Direction derivative

Linear filters, smoothing & edge detection 44

 Derivatives & finite differences

• Image derivatives can be estimated using a symmetric

finite difference:
!0 0 0$
∂h # &
≈ hi+1, j − hi−1, j H = #1 0 -1 &
∂x #"0 0 0 &%

• Problematic when an image has noise in it (typical noise

is high frequency); finite difference filters pick it up.
• Solution: some smoothing before edge detection would
help.

Linear filters, smoothing & edge detection 45

Derivatives & finite differences
Direction of derivative

>>Added noise

Linear filters, smoothing & edge detection 46

Edge Detection

Chapter 5 (F&P)

Linear filters, smoothing & edge detection 47

 Edges

• Sharp changes in brightness are often called edges or

edge points.
• It is difficult to determine meaningful edges from
nuisance edges.
• This is usually a matter of perception.
• Edges are the basis for finding objects using bottom-up
approaches in Computer Vision.

Linear filters, smoothing & edge detection 48

Example on Lena

Linear filters, smoothing & edge detection 49

 Noise

• Unfortunately, noise is also high frequency and comes

about as a sharp change in intensity.
• Noise signifies image measurements from which we do
not know how to extract information; all the rest is the
signal.
• Noise is everything we don’t wish to use.

Linear filters, smoothing & edge detection 50

 Additive stationary Gaussian noise

• With additive stationary Gaussian

noise, each pixel has added to it a
value chosen independently, but from
the same Gaussian Probability
Distribution.
0
• The mean of this PDF is ZERO.
• The standard deviation is a parameter
of the model.

Linear filters, smoothing & edge detection 51

Additive stationary Gaussian noise
σ = 1/256 σ = 4 /256 σ = 16 /256

R(N ) i, j = ∑G i− u, j−vN u,v

u,v

Linear filters, smoothing & edge detection 52

 Estimating Derivatives

• Finite difference filters give strong response to noise.

• Therefore, applying 2 finite difference filters (one in
each direction) is a poor way to estimate a gradient.
• A solution to this is to smooth the image and then
differentiate it. Alternatively, we could smooth the
derivative kernel.

Linear filters, smoothing & edge detection 53

 Estimating Derivatives

• If we assume a kernel always exists that differentiates:

∂I
= K(∂ /∂ x) ∗∗I
∂x

• Now if we write convolution kernel for the smoothing

as S, convolution is associative:

⎛∂ S ⎞
( ) ( )
K(∂ /∂ x ) ∗∗( S ∗∗I ) = K(∂ /∂ x) ∗∗S ∗∗I = ⎜ ⎟ ∗∗I
⎝∂ x ⎠

Linear filters, smoothing & edge detection 54

 Estimating Derivatives

• When the smoothing function is a Gaussian:

∂ (Gσ ∗∗I ) ∂ (Gσ )

= ∗∗I
∂x ∂x

• This means we only need to convolve with the

derivative of a Gaussian, rather than convolve and then
differentiate.

Linear filters, smoothing & edge detection 55

 Derivative of a Gaussian filter

• Notice how smoothing via the derivative of Gaussian

reduces the impact of the noise.

σ noise = 0.03 σ noise = 0.09

Linear filters, smoothing & edge detection 56

 Profile stays, noise is reduced !!

• In general, the border separating foreground from

background will be long compared to random changes
due to noise.
• Therefore, when we smooth, noise should be eliminated
while object boundaries remain.

Linear filters, smoothing & edge detection 57

 Gaussian filter
• The choice of σ determines the scale of the smoothing.
The scale has a substantial effect on the response of a
derivative filter.

σ = 1 pixel σ = 3 pixel σ = 7 pixel

Linear filters, smoothing & edge detection 58

 Gaussian properties
• If we convolve a Gaussian with a Gaussian, the result is
a Gaussian:

Gσ 1 ∗∗Gσ 2 = G
σ 12 +σ 22

• Convolving with a Gaussian is efficient. If we need to

convolve with a large kernel (e.g., 10 pixels), we can
instead convolve with a much smaller kernel multiple
times.
Large smoothing: smooth, subsample, smooth, subsample,…

Linear filters, smoothing & edge detection 59

 Gaussian properties
• Central limit theorem:
- Convolving any member of a
family of functions with itself
repeatedly eventually yields a
Gaussian.
- So, if we choose a smoothing
kernel different than a Gaussian and
apply it repeatedly to an image, it
looks like it has been convolved
with a Gaussian.

Linear filters, smoothing & edge detection 60

 Gaussian properties

• Gaussians are separable: an isotropic Gaussian can be

factored as a product of two Gaussians.
• So, convolving an image with a 2D kernel can be
achieved by convolving it with a 1D kernel in the x
direction, followed with a 1D kernel in the y direction.

Gaussian2D Gaussian1D x Gaussian1D

Linear filters, smoothing & edge detection 61

 Detecting edges

• We can find edges via one

of two methods:
1) Look for locations where the
first derivative is maximum.
2) Look for locations where the
second derivative is zero.

Linear filters, smoothing & edge detection 62

 Using a Laplacian
• In 1D, the second derivative of a signal is zero ⎡0 0 ⎤
when the magnitude is extremal. ⎢1 -1 ⎥
⎢ ⎥
⎢⎣ 0 0 ⎥⎦
• In 2D, it is the Laplacian that has this property.
⎡0 1 0 ⎤
∂ f ∂ f 2 2

(∇ f )( x, y ) = ∂x 2 + ∂y 2
2 ⎢1 -4 1 ⎥
⎢ ⎥
⎢⎣ 0 1 0 ⎥⎦

• Because the Laplacian is a linear operator:

(K ∇ 2 ∗∗(Gσ ∗∗I )) = (K ∇ 2 ∗∗Gσ ) ∗∗I = (∇ 2Gσ ) ∗∗I

Laplacian of a Gaussian

Linear filters, smoothing & edge detection 63

 Laplacian & LoG filters

LoG filter

Laplacian filter

Linear filters, smoothing & edge detection 64

Laplacian of a Gaussian

Linear filters, smoothing & edge detection 65

 Laplacian

Retina LoG

A B

LoG Kernel
Sharpened:
A+B

Linear filters, smoothing & edge detection 66

 Disadvantage of LoG

• The LoG is not oriented

• This means that behaviors at corners is poor
• Therefore, the main disadvantage of the Laplacian of a
Gaussian is that it marks sharp boundaries inaccurately.
• It also has difficulty recording the topology of the
corner correctly.
• A second disadvantage that the zero crossing may not
lie exactly on an edge.

Linear filters, smoothing & edge detection 67

Problem of LoG at corners

Linear filters, smoothing & edge detection 68

 Gradient-based edge detector
• In gradient-based edge detector we compute the
gradient magnitude, using a Gaussian as a smoothing
kernel.
• The gradient magnitude is large along a thick trail in the
image. What we want is the profile of this trail looking
for the most distinctive points.

Linear filters, smoothing & edge detection 69

Result of Derivative of Gaussian
Fixed scale

Fixed gradient magnitude threshold

Linear filters, smoothing & edge detection 70
Gradient magnitude

Linear filters, smoothing & edge detection 71

 Gradient magnitude

• What we can do is look for points where the gradient

magnitude is maximum along the perpendicular to the
edge.

Linear filters, smoothing & edge detection 72

 Gradient Based Edge Detection

• Algorithm 5.1: Gradient-based edge detection

- Form an estimate of the image gradient
- Obtain the gradient magnitude from this estimate
- Identify image points where the gradient is max in
the direction perpendicular to the edge.

Linear filters, smoothing & edge detection 73

 Nonmaximum suppression

• To get rid of local small maxima (low hills) and keep

the large maximum (hilltop) we perform nonmax
suppression.

Linear filters, smoothing & edge detection 74

 Line following (nonmax suppression)
• Continued: Nonmaximum suppression
- While there are points with high gradient (not visited)
- Find a start point that is a local maximum in the direction
perpendicular to the gradient. Erase points that have been
checked.
- Expand a chain through the current point:
- Predict a set of next points (perp to gradient)
- Find local maximum in the gradient direction
- Test if the gradient magnitude is sufficient
- Leave a record that point has been visited
- Record the next point as current point
Linear filters, smoothing & edge detection 75
 Hysteresis thresholding

• To restrict the maxima, we use hysteresis thresholding:

– We have a large threshold when starting an edge chain,
– We have a small threshold while following an edge chain.

Problem: T1:

Solution: T1:
T2:

Linear filters, smoothing & edge detection 76

 Canny Edge Detector
• Algorithm: Canny Edge Detector
- Apply derivative of Gaussian
- Non-maximum suppression, Thin multi-pixel wide
“ridges” down to single pixel
- Hysteresis Thresholding. Low, high edge-strength
thresholds. Accept all edges over low threshold that are
connected to edge over high threshold
These points are edge points.

Linear filters, smoothing & edge detection 77

 [Link] vertical edges horizontal edges

norm of the gradient after thresholding after thinning

Linear filters, smoothing & edge detection 78

 Example 1

σ =1, σ =4, σ =4,

high threshold high threshold low threshold

Linear filters, smoothing & edge detection 79

 Example 2

σ =1, σ =4, σ =4,

high threshold high threshold low threshold
Linear filters, smoothing & edge detection 80
 Example 3

σ =1, σ =4, σ =4,

high threshold high threshold low threshold
Linear filters, smoothing & edge detection 81
Edges: Masks Based on Gradient

Linear filters, smoothing & edge detection 82

 Other Edges detectors

• Roberts
• Sobel
• Prewitt
• Kirsch
• Robinson
• Laplace

Linear filters, smoothing & edge detection 83

 Lab exercise

Read an image
Apply blur (gaussian or similar)

Use [Link] to detect and display edges

Add sliders to for thresholds from 0 to 255

MECH 642 Linear filters, smoothing & edge detection Slide 84

 Corner Detection

• Corners are intersections of image lines and capture

corner structures in patterns of intensities.
• Corners are relatively stable (at least more than edges)
across sequences of images.
• The question is how to determine corners.
• Here we start talking about `Interest Points’

Linear filters, smoothing & edge detection 85

 Harris corner detector
• If we consider:
P
H = ( I)( I)T
window ( )
P ( @G
@x ⇤ ⇤I)( @G
@x ⇤ ⇤I) ( @G
@x ⇤ ⇤I)( @G
@y ⇤ ⇤I)
⇡ @G @G
window ( @y ⇤ ⇤I)( @x ⇤ ⇤I) ( @G
@y ⇤ ⇤I)( @G
@y ⇤ ⇤I)

• Harris looks for maxima of:

trace(H) 2
det(H) k( )
2

Linear filters, smoothing & edge detection Slide 86

 Corner detection
• The eigenvectors encode edge directions, ⎡λ1 0⎤
C=⎢
• The eigenvalues encode edge strength. ⎣0 λ2 ⎥⎦

• A corner is a location where the smaller eigenvalue λ2 is

larger than a threshold.

Linear filters, smoothing & edge detection 87

 Corner detection (local maxima)
Square of the average
trace(H) 2 Eigenvalues
det(H) k( )
2

Product of
Eigenvalues

Linear filters, smoothing & edge detection 88

 Harris Corner detection
• Algorithm:
– The input to the algorithm is the image I and 3 parameters:
• the value of k to detect all corners
• threshold on corners
• the size of the square window 2N+1
– Compute the image gradient over the entire image I
– Convolve the image gradient with the Harris mask
– For each image point p:
• If the Harris measure > threshold save the
coordinate of p into a list L
– Sort L in decreasing order of λ2

Linear filters, smoothing & edge detection 89

 Building a neigborhood
• To turn a corner into a neighborhood we must estimate
the radius of the circular patch.
• An efficient way to do this is to use a Laplacian of a
Gaussian and choose the radius (scale) of the best fitting
blob.
2 2
2 @ f @ f
(5 f )(x, y) = 2
+ 2
@x @y

(Kr2 ⇤ ⇤(G ⇤ ⇤I)) = (Kr2 ⇤ ⇤G ) ⇤ ⇤I = (r2 G ) ⇤ ⇤I

Linear filters, smoothing & edge detection Slide 90

Linear filters, smoothing & edge detection Slide 91
 Location, scale, & orientation of elements
using a corner detector
• Assume a fixed scale parameter k
• Apply a corner detector to the image I
• Initialize a list of patches
For each corner detected
• Write (xc, yc) for the location of the corner. Compute the radius r
for the patch at (xc,yc) as:

r(xc , yc ) =argmax r2 I(xc , yc )

by computing r2 I(xc , yc ) for a variety of values of σ,
interpolating these values, and maximizing

Linear filters, smoothing & edge detection 92

• Compute an orientation histogram H(θ) for gradient orientations
within a radius kr of (xc, yc).
argmax
• Compute the orientation of the patch θp as ✓p =✓ H(✓)
• If there is more than one theta that maximizes this histogram,
make one copy of the patch for each.
• Attach (xc, yc, r, θp) to the list of patches for each copy

Linear filters, smoothing & edge detection 93

Spatial frequency &
Fourier Transform

Linear filters, smoothing & edge detection 94

 Spatial frequency

• A signal g(x,y) is a weighted sum of a number of basis

functions (e.g., sines & cosines)
• Different bases can express different information.
• If you want to shrink an image you cannot simply take
every kth pixel (think of aliasing). Frequency
information is important here!

Linear filters, smoothing & edge detection 95

 Fourier Transform
• The Fourier transform reveals the frequency content of a
signal or image
∞
F (g(x, y))(u,v) = ∫ ∫ g(x, y)e −i2 π ( ux +vy )
dxdy
−∞

cos(2π ( ux + vy )) + isin(2π ( ux + vy ))

Sinusoids on the x,y plane whose orientation and

frequency are given by u and v.

Linear filters, smoothing & edge detection 96

 Spatial frequency components
• These sinusoids are referred to as spatial frequency
components.
• Take the origin at the center of the image
v
tan θ = Frequency = u 2 + v 2
u

(u,v ) = (0,0.4 ) (u,v ) = (1,2) (u,v ) = (10,−5)

Linear filters, smoothing & edge detection 97
 Properties of Fourier basis

• If we fix u and v, the value of the Fourier transform is

the dot product between a sinusoid in x and y and the
original function.
• The value of the transform at a particular u and v can be
seen as measuring the amount of sinusoid with given
frequency and orientation in the signal.

Linear filters, smoothing & edge detection 98

 Properties of Fourier Transform

• Linearity: the Fourier transform is linear

F (g(x, y) + h(x, y)) = F (g(x, y)) + F (h(x, y))

F (kg(x, y)) = kF (g(x, y))

• The inverse Fourier Transform:

∞
g(x, y) = ∫ ∫ F (g(x, y))(u,v)e i2 π ( ux +vy )
dudv
−∞

Linear filters, smoothing & edge detection 99

 Phase & Magnitude
• The Fourier transform consists of a real and complex
component.
• We plot these independently and call them respectively
the magnitude spectrum and the phase spectrum.
• The value of the Fourier transform of a function at a
particular frequency (u,v) depends on the whole
function.
• This means that a local change leads to a change at
every point in the Fourier Transform.

Linear filters, smoothing & edge detection 100

 Phase & Magnitude

• We usually plot the magnitude spectrum and phase

spectrum separately (Bode plots)
∞
F (g(x, y))(u,v) = ∫ ∫ g(x, y)cos(2π (ux + vy ))dxdy
−∞
∞
+i∫ ∫ g(x, y)sin(2π (ux + vy ))dxdy
−∞

= ℜ( F (g)) + iℑ( F (g))

= FR (g) + iFI (g)

Linear filters, smoothing & edge detection 101

 Fourier Transform

• The magnitude of the Fourier Transform is NOT a good

representation to use to detect patterns.
• The magnitude spectra could be similar for different
images since the Fourier Transform does NOT account
for the location of frequency component.
• Phase is more informative for perception than the
magnitude spectrum.

Linear filters, smoothing & edge detection 102

Fourier Transform

Linear filters, smoothing & edge detection 103

 Filters as Templates
• Filters offer a natural mechanism for finding simple
patterns because they respond strongly to pattern
elements that look like the filter.
• The kernel of the filter looks like the effect it is intended
to detect.

Linear filters, smoothing & edge detection 104

 Convolution as a dot product
• The response of a linear filter to an image H is given
by:
Rij = ∑ Gi−u, j−v H u,v
u,v

• The response is found by associating image elements

with filter kernel elements, multiplying the associated
elements and summing (dot product??)

Linear filters, smoothing & edge detection 105

 Convolution as a dot product

• We know that the dot product is largest when the

vectors are // to each other (i.e., cos(0) = 1).
• This means that a filter responds most strongly when it
encounters an image pattern that looks like the filter
(Cooool).
• Furthermore, the response of a filter gets larger as a
region gets brighter.

Linear filters, smoothing & edge detection 106

Filters as Templates

Linear filters, smoothing & edge detection 107

 Lab exercise : corner detection

Use cv2 corner harris detection

[Link](gray, blockSize=2,
ksize=3, k=0.04)

Extract a binary mask of the corners, with

a certain thresholding value

Display image with corners

MECH 642 Linear filters, smoothing & edge detection Slide 108
 Sampling
• The number of samples
that are taken when
converting from a
continuous signal to a
discrete one refers to as
sampling.
• During sampling some
information is lost:
sample2D(F(x,y)) = F

Linear filters, smoothing & edge detection 109

Sampling in 2D

Bed of nails function

Linear filters, smoothing & edge detection 110

 A continuous model of a sampled
signal
• The model consists of the delta function at each sample
point weighted by the value of the sample at that point.
• We call such a function a comb function for 1D
sampling and a bed-of-nails function for 2-D sampling.
∞ ∞
sample2D ( f ) = ∑ ∑ f (x, y)δ(x − i, y − j)
i= −∞ j=−∞

⎧⎪ ∞ ∞ ⎫⎪
= f (x, y)⎨ ∑ ∑δ (x − i, y − j)⎬
⎪⎩ i= −∞ j=−∞ ⎪⎭

Linear filters, smoothing & edge detection 111

 Aliasing

• A signal that is sampled too slowly is misrepresented by

the samples;
• Aliasing results in high spatial frequency components of
the original signal appearing as low frequency
components in the sampled signal.

Linear filters, smoothing & edge detection 112

Aliasing example

Linear filters, smoothing & edge detection 113

Aliasing example

Linear filters, smoothing & edge detection 114

Aliasing example

Linear filters, smoothing & edge detection 115

 The Fourier transform of a sampled
signal
• A sampled signal is obtained by the product of the
original signal (image) with a bed-of-nails function.
• The Fourier transform of this product is the convolution
of the Fourier transforms of the two functions.
• Therefore, the Fourier Transform of sampled signal is
obtained by convolving the Fourier Transform of the
signal with ANOTHER bed-of-nails function.

Linear filters, smoothing & edge detection 116

 The Fourier transform of a sampled
signal

• Convolving a function with a shifted -> function shifts

the function.
• Therefore, the Fourier transform of a sampled signal is
the sum of a collection of shifted versions of the Fourier
transforms of the signal.

Linear filters, smoothing & edge detection 117

 ⎛ ⎧⎪ ∞ ∞ ⎫⎪⎞
F ( sample2D ( f ( x, y ))) = F ⎜⎜ f (x, y)⎨ ∑ ∑δ (x − i, y − j)⎬⎟⎟
⎝ ⎪⎩ i= −∞ j=−∞ ⎪⎭⎠

⎛⎧⎪ ∞ ∞ ⎫⎪⎞
= F ( f (x, y)) ∗ F ⎜⎜⎨ ∑ ∑δ (x − i, y − j)⎬⎟⎟
⎝⎪⎩ i= −∞ j=−∞ ⎪⎭⎠

⎛⎧ ∞ ∞ ⎫⎞
= F ( f (x, y)) ∗ F ⎜⎜⎨ ∑ ∑δ (x − nTi , y − nT j )⎬⎟⎟
⎝⎩ n=−∞ n=−∞ ⎭⎠

∞
k k
= ∑ F ∗ δ (u − ,v − )
k=−∞
Ti Tj

∞
F ( sample2D ( f ( x, y ))) = ∑ F(u − k ⋅ freq , v − k ⋅ freq )
i j
k =-∞

Linear filters, smoothing & edge detection 118

 Can we reconstruct the signal?

• If the support of shifted

versions DO NOT
intersect, we CAN
reconstruct a signal from
the sampled version.

Linear filters, smoothing & edge detection 119

 Sampling too slowly (aliasing)

• If the support of shifted

versions DO intersect,
we CANNOT
reconstruct a signal
from the sampled
version.

Linear filters, smoothing & edge detection 120

 Smoothing & Resampling
• Important: Nyquist’s theorem implies that it is dangerous to
shrink an image by simply taking every kth pixel.
Slower sampling

Original image
sub-sampled

Magnitude of
Fourier transform

Linear filters, smoothing & edge detection 121

Smoothing & Resampling

Linear filters, smoothing & edge detection 122

Smoothing & Resampling

Linear filters, smoothing & edge detection 123

 Algorithm: Subsampling an image
by 2
• Algorithm 7.1: Subsampling an image by a factor of 2
Apply a low-pass filter to the original image
(Gaussian with a 1< σ < 2 )
Create a new image whose dimensions on edge are
half those of the old image
Set the value of the i, jth pixel of the new image to the
value of the 2i, 2jth pixel of the filtered image.

Linear filters, smoothing & edge detection 124