Linear Filtering

670: Computer Vision

Grant Van Horn

February 27, 2024
Announcements
HW2 is out, due March 5th

Course Project:
• Proposals: Friday, March 15 (2.5 weeks away!)
• Use Piazza to nd partners (teams of size 2-3)
• Talk to us in OHs about project ideas
• Poster Presentation: Friday May 10th, 2-4pm, LGRC A112.
• Reports: Sunday, May 12th
• Details: https://cvl-umass.github.io/compsci670-spring-2024/project/

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 2

fi
Overview
Linear ltering (aka convolutions)
• Mathematical model
• Implementation details

Applications
• Denoising
• Sharpening
• Edge detection

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 3

fi
Motivation
How can we reduce noise in a photograph?

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 4

Moving average
Let’s replace each pixel with a weighted average of its neighborhood
The weights are called the filter kernel
What are the weights for the average of a 3x3 neighborhood?

1 1 1

1 1 1

1 1 1

“box filter”

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: D. Lowe 5
Filtering
Let f be the image and g be the kernel. The output of ltering f with g denoted f *g is given by:
X
(f ⇤ g)[m, n] = f [m + k, n + l]g[k, l]
k,l

Filtering computes the correlation between the g and f at each location

Convolution is ltering with a ipped g (by notation)
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: F. Durand 6
fi
fl
fi
Filtering: multi-channel case
Let f be the image and g be the kernel. The output of ltering f with g denoted f *g is given by:
X
(f ⇤ g)[m, n] = f [m + k, n + l, c]g[k, l, c]
k,l,c

g g
multi-channel f

multi-channel

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: F. Durand 7
fi
Key properties
Linearity: lter(f1 + f2) = lter(f1) + lter(f2)
Shift invariance: same behavior regardless of pixel location: lter(shift(f)) = shift( lter(f))
Theoretical result: any linear shift-invariant operator can be represented as a convolution

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 8

fi
fi
fi
fi
fi
Properties in more detail
Commutative: a * b = b * a
• Conceptually no difference between lter and signal

Associative: a * (b * c) = (a * b) * c
• Often apply several lters one after another: (((a * b1) * b2) * b3)

• This is equivalent to applying one lter: a * (b1 * b2 * b3)

Distributes over addition: a * (b + c) = (a * b) + (a * c)

Scalars factor out: ka * b = a * kb = k (a * b)
Identity: unit impulse e = […, 0, 0, 1, 0, 0, …], a * e = a

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 9

fi
fi
fi
Annoying details
What is the size of the output?
Python: scipy.ndimage.correlate / convolve
• shape = ‘full’: output size is sum of sizes of f and g
• shape = ‘same’: output size is same as f
• shape = ‘valid’: output size is difference of sizes of f and g

full same valid

g g
g g
g g

f f f

g g
g g
g g
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 10
 Annoying details
What about near the edge?
• the lter window falls off the edge of the image
• need to extrapolate
• methods:
• clip lter (black) — correlate(f, g, mode=‘constant’, cval=0.0)
• wrap around — correlate(f, g, mode=‘wrap’)
• copy edge — correlate(f, g, mode=‘nearest’)
• re ect across edge –– correlate (f, g, mode=‘re ect’)

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: S. Marschner 11
fl
fi
fi
fl
Practice with linear lters

0 0 0
0 1 0 ?
0 0 0

Original

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: D. Lowe 12
fi
Practice with linear lters

0 0 0
0 1 0
0 0 0

Original Filtered
(no change)

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: D. Lowe 13
fi
Practice with linear lters

0 0 0
0 0 1 ?
0 0 0

Original

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: D. Lowe 14
fi
Practice with linear lters

0 0 0
0 0 1
0 0 0

Original Shifted left

By 1 pixel

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: D. Lowe 15
fi
Practice with linear lters

1 1 1
1 1 1 ?
1 1 1

Original

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: D. Lowe 16
fi
Practice with linear lters

1 1 1
1 1 1
1 1 1

Original Blur (with a

box filter)

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: D. Lowe 17
fi
Practice with linear lters

0 0 0 1 1 1
0 2 0
0 0 0
- 1 1 1
1 1 1
?
(Note that filter sums to 1)
Original

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: D. Lowe 18
fi
Practice with linear lters

0 0 0 1 1 1
0 2 0
0 0 0
- 1 1 1
1 1 1

Original

Sharpening filter: accentuates differences with local average

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: D. Lowe 19
fi
Smoothing with box lter revisited
What’s wrong with this picture?
What’s the solution?

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: D. Forsyth 20
fi
Smoothing with box lter revisited
What’s wrong with this picture?
What’s the solution?
• To eliminate edge effects, weight contribution of neighborhood pixels according to their
closeness to the center

“fuzzy blob”

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 21

fi
Gaussian kernel
Constant factor at front makes volume sum to 1 (can be ignored when computing the lter
values, as we should renormalize weights to sum to 1 in any case)

0.003 0.013 0.022 0.013 0.003

0.013 0.059 0.097 0.059 0.013
0.022 0.097 0.159 0.097 0.022
0.013 0.059 0.097 0.059 0.013
0.003 0.013 0.022 0.013 0.003

5 x 5, σ = 1

Source: C. Rasmussen
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 22

fi
Gaussian kernel
Standard deviation σ: determines extent of smoothing

σ = 2 with 30 x 30 σ = 5 with 30 x 30
kernel kernel

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: K. Grauman 23
Choosing kernel width
The Gaussian function has in nite support, but discrete lters use nite kernels

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: K. Grauman 24
fi
fi
fi
Choosing kernel width
Rule of thumb: set lter half-width (radius) to about 3σ

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 25

fi
Gaussian vs. box ltering

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 26

fi
Gaussian lters
Remove high-frequency components from the image (low-pass filter)
Convolution with self is another Gaussian
• So can smooth with small-σ kernel, repeat, and get same result as larger-σ kernel would have
• Convolving two times with Gaussian kernel with std. dev. σ
is same as convolving once with kernel with std. dev. σ 2
Separable kernel
• Factors into product of two 1D Gaussians
• Discrete example:

&1 2 1 # &1 #
$2 4 2! = $2![1 2 1]
$ ! $ !
$%1 2 1 !" $%1 !"

Source: K. Grauman
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 27
fi
Separability of the Gaussian lter

Source: D. Lowe
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24
fi
28
Why is separability useful?
Separability means that a 2D convolution can be reduced to two 1D convolutions (one among
rows and one among columns)
What is the complexity of ltering an n×n image with an m×m kernel?
• O(n2 m2)
What if the kernel is separable?
• O(n2 m)

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 29

fi
Types of noise
Salt and pepper noise: contains random
occurrences of black and white pixels
Impulse noise: contains random
occurrences of white pixels
Gaussian noise: variations in intensity
drawn from a Gaussian normal distribution

Source: S. Seitz
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 30
Gaussian noise
Mathematical model: sum of many independent factors
Good for small standard deviations
Assumption: independent, zero-mean noise

Source: M. Hebert
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 31
Reducing Gaussian noise
noise

Smoothing with larger standard deviations suppresses noise, but

also blurs the image
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 32
Reducing salt-and-pepper noise
3x3 5x5 7x7

Gaussian smoothing with increasing standard deviation

How can we improve these results?

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 33
Alternative idea: Median ltering
A median filter operates over a window by selecting the median intensity in the window

Question: is median filtering linear?

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: K. Grauman 34
fi
Median lter
What advantage does median ltering have over Gaussian ltering?

Robustness to outliers

Source: K. Grauman
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 35
fi
fi
fi
Median lter
Salt-and-pepper noise Median filtered

Matlab: med lt2 Python: scipy.ndimage.median_ lter

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: M. Hebert 36
fi
fi
fi
Sharpening

Source: D. Lowe
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 37
Sharpening
What does blurring take away?

– =

original smoothed (5x5) detail

Let’s add it back:

+α =

original detail sharpened

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 38
Unsharp mask lter
f + α ( f − f ∗ g ) = (1 + α ) f − α f ∗ g = f ∗ ((1 + α )e − g )

image blurred unit impulse

image (identity)

unit impulse
Gaussian Laplacian of Gaussian

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 39

fi
Hybrid Images
A. Oliva, A. Torralba, P.G. Schyns, “Hybrid Images,” SIGGRAPH 2006

Gaussian Filter

Laplacian Filter

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 40

41
motorcycle and bicycle 42
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 43
dolphin and car 44
COMPSCI 670 dolphin and car Grant Van Horn — UMass Amherst, Spring 24 45
Fooling deep networks

“Adversarial examples”

+ =

Schoolbus Perturbation Ostrich

(rescaled for visualization)

(Szegedy et al, 2013)

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 46
Edge detection
Goal: Identify sudden changes (discontinuities) in an
image
• Intuitively, most semantic and shape information from the
image can be encoded in the edges
• More compact than pixels

Ideal: artist’s line drawing (but artist is also using

object-level knowledge)

Source: D. Lowe
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 47
Origin of edges
Edges are caused by a variety of factors:

surface normal discontinuity

depth discontinuity

surface color discontinuity

illumination discontinuity

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 Source: Steve Seitz 48
Edge detection
An edge is a place of rapid change in the image intensity function

intensity function
image (along horizontal scanline) first derivative

edges correspond to
extrema of derivative

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 49

Derivatives with convolution
For 2D function f(x,y), the partial derivative is:

∂f ( x, y ) f ( x + ε , y ) − f ( x, y )
= lim
∂x ε → 0 ε
For discrete data, we can approximate using nite differences:

∂f ( x, y ) f ( x + 1, y ) − f ( x, y )
≈
∂x 1
To implement the above as convolution, what would be the associated lter?

Source: K. Grauman
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 50
fi
fi
Partial derivatives of an image

∂f ( x, y ) ∂f ( x, y )
∂x ∂y

-1 1
-1 1 1 or
-1

Which one shows changes with respect to x?

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 51
Image gradient
The gradient of an image:

The gradient points in the direction of most rapid increase in

intensity
• How does this direction relate to the direction of the edge?

The gradient direction is given by

The edge strength is given by the gradient magnitude

Source: Steve Seitz

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 52
Effects of noise
Consider a single row or column of the image

Where is the edge?

Source: S. Seitz
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 53
Solution: smooth rst

f*g

d
( f ∗ g)
dx

d
• To find edges, look for peaks in ( f ∗ g)
dx Source: S. Seitz
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 54
fi
Derivative theorem of convolution
Differentiation is convolution, and convolution is associative:
d d
( f ∗ g) = f ∗ g
dx dx
This saves us one operation:

d
g
dx

d
f∗ g
dx
Source: S. Seitz
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 55
Derivative of Gaussian lters

x-direction y-direction

1) Which one nds horizontal edges?

2) Are these lters separable?
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 56
fi
fi
fi
Scale of Gaussian derivative lter

1 pixel 3 pixels 7 pixels

Smoothed derivative removes noise, but blurs edge. Also nds edges at different “scales”

Source: D. Forsyth
COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24
fi
57
fi
Smoothing and derivative lters
Smoothing lters
• Gaussian: remove “high-frequency” components;
“low-pass” lter
• Can the values of a smoothing lter be negative?
• What should the values sum to?
• One: constant regions are not affected by the lter

Derivative lters
• Derivatives of Gaussian
• Can the values of a derivative lter be negative?
• What should the values sum to?
• Zero: no response in constant regions
• High absolute value at points of high contrast

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 58

fi
fi
fi
fi
fi
fi
fi
Learning a boundary detector
Learning to Detect Natural Image Boundaries Using Local Brightness, Color, and Texture Cues, D.
Martin, C. Fowlkes, J. Malik, PAMI 2004
Convert it to a classi cation problem — e.g., is there a vertical edge at the center of this patch?
Compare average brightness, color, and texture of half-disks
Do this for 8 different orientations
non-boundaries

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 59

fi
Learning a boundary detector
Learning to Detect Natural Image Boundaries Using Local Brightness, Color, and Texture Cues, D.
Martin, C. Fowlkes, J. Malik, PAMI 2004
Convert it to a classi cation problem — e.g., is there a vertical edge at the center of this patch?
Compare average brightness, color, and texture of half-disks
Do this for 8 different orientations
boundaries

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 60

fi
Berkeley segmentation database

COMPSCI 670 Berkeley segmentation database

Grant Van Horn — UMass Amherst, Spring 24 61
example boundary detections 62
Further thoughts and readings …
Hybrid images project
• http://olivalab.mit.edu/hybridimage.htm

Canny edge detector

• www.limsi.fr/Individu/vezien/PAPIERS_ACS/canny1986.pdf

Bilateral ltering for image de-noising (and other application)

• http://people.csail.mit.edu/sparis/bf_course/

Berkeley segmentation dataset and other resources

• https://www2.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/resources.html

COMPSCI 670 Grant Van Horn — UMass Amherst, Spring 24 63

fi