Filtering

CSE 803– Fall 2024, MSU

Xiaoming Liu

Thank many researchers who have made their slides and course materials available
 Let’s Take An Image

credit: D Fouhey
 Let’s Fix Things
• We have noise in our image
• Let’s replace each pixel with a weighted
average of its neighborhood
• Weights are filter kernel
Pixel Pixel Pixel
1/9 1/9 1/9
1 2 3
Pixel Pixel Pixel
X 1/9 1/9 1/9 Out
4 5 6
Pixel Pixel Pixel
1/9 1/9 1/9
7 8 9
Input image patch Weight for each pixel Output
Slide Credit: D. Lowe
 1D Case

Signal/ 10 12 9 11 10 11 12
Front Row

Filter/ 1/3 1/3 1/3

David

Output 10.33 10.66 10 10.66 11

credit: D Fouhey
 Applying a Linear Filter

Input Filter Output

I11 I12 I13 I14 I15 I16

I21 I22 I23 I24 I25 I26 F11 F12 F13 O11 O12 O13 O14

I31 I32 I33 I34 I35 I36 F21 F22 F23 O21 O22 O23 O24

I41 I42 I43 I44 I45 I46 F31 F32 F33 O31 O32 O33 O34

I51 I52 I53 I54 I55 I56

credit: D Fouhey
 Applying a Linear Filter

Input & Filter Output

F11
I11 F12
I12 F13
I13 I14 I15 I16

F21
I21 F22
I22 F23
I23 I24 I25 I26 O11

F31
I31 F32
I32 F33
I33 I34 I35 I36

I41 I42 I43 I44 I45 I46

I51 I52 I53 I54 I55 I56

O11 = I11*F11 + I12*F12 + … + I33*F33

credit: D Fouhey
 Applying a Linear Filter

Input & Filter Output

I11 F11
I12 F12
I13 F13
I14 I15 I16

I21 F21
I22 F22
I23 F23
I24 I25 I26 O11 O12

I31 F31
I32 F32
I33 F33
I34 I35 I36

I41 I42 I43 I44 I45 I46

I51 I52 I53 I54 I55 I56

O12 = I12*F11 + I13*F12 + … + I34*F33

credit: D Fouhey
 Applying a Linear Filter

Input Filter Output

I11 I12 I13 I14 I15 I16

I21 I22 I23 I24 I25 I26 F11 F12 F13

I31 I32 I33 I34 I35 I36 F21 F22 F23

I41 I42 I43 I44 I45 I46 F31 F32 F33

I51 I52 I53 I54 I55 I56

How many times can we apply a

3x3 filter to a 5x6 image?

credit: D Fouhey
 Applying a Linear Filter

Input Filter Output

I11 I12 I13 I14 I15 I16

I21 I22 I23 I24 I25 I26 F11 F12 F13 O11 O12 O13 O14

I31 I32 I33 I34 I35 I36 F21 F22 F23 O21 O22 O23 O24

I41 I42 I43 I44 I45 I46 F31 F32 F33 O31 O32 O33 O34

I51 I52 I53 I54 I55 I56

Oij = Iij*F11 + Ii(j+1)*F12 + … + I(i+2)(j+2)*F33

Given a M by N image, with a K by K filter, the filtering output
size can be (M-2*(K-1)/2)*(N-(K-1)) assuming no padding on
either side.
credit: D Fouhey
 Painful Details – Edge Cases
Convolution doesn’t keep the whole image.
Suppose f is the image and g the filter.
Full – any part of g touches f. Same – same size as f;
Valid – only when filter doesn’t fall off edge.
full same valid
g g g g
g g

f f f

g g
g g g g
f/g Diagram Credit: D. Lowe
 Painful Details – Edge Cases
What to about the “?” region?

???? Symm: fold sides over

g g

Circular/Wrap: wrap around

f

pad/fill: add value, often 0

g g

f/g Diagram Credit: D. Lowe

 Painful Details – Does it Matter?
(I’ve applied the filter per-color channel)
Which padding did I use and why?
Input Box Filtered Box Filtered
Image ??? ???

Note – this is a zoom of the filtered, not a filter of the zoomed

credit: D Fouhey
 Painful Details – Does it Matter?
(I’ve applied the filter per-color channel)

Input Box Filtered Box Filtered

Image Symm Pad Zero Pad

Note – this is a zoom of the filtered, not a filter of the zoomed

credit: D Fouhey
 Practice with Linear Filters

0 0 0
0 1 0
?
0 0 0

Original

Slide Credit: D. Lowe

 Practice with Linear Filters

0 0 0
0 1 0
0 0 0

Original The Same!

Slide Credit: D. Lowe

 Practice with Linear Filters

0 0 0
0 0 1 ?
0 0 0

Original

Slide Credit: D. Lowe

 Practice with Linear Filters

0 0 0
0 0 1
0 0 0

Original Shifted
LEFT
1 pixel

Slide Credit: D. Lowe

 Practice with Linear Filters

0 1 0
0 0 0 ?
0 0 0

Original

Slide Credit: D. Lowe

 Practice with Linear Filters

0 1 0
0 0 0
0 0 0

Original Shifted
DOWN
1 pixel

Slide Credit: D. Lowe

 Practice with Linear Filters

1/9 1/9 1/9

1/9 1/9 1/9 ?
1/9 1/9 1/9

Original

Slide Credit: D. Lowe

 Practice with Linear Filters

1/9 1/9 1/9

1/9 1/9 1/9
1/9 1/9 1/9

Original Blur
(Box Filter)

Slide Credit: D. Lowe

 Practice with Linear Filters
0 0 0
0 2 0
0 0 0

-
?
1/9 1/9 1/9
Original
1/9 1/9 1/9
1/9 1/9 1/9

Slide Credit: D. Lowe

 Practice with Linear Filters
0 0 0
0 2 0
0 0 0

-
1/9 1/9 1/9
Original Sharpened
1/9 1/9 1/9 (Acccentuates
difference from
1/9 1/9 1/9 local average)

Slide Credit: D. Lowe

 Sharpening

Slide Credit: D. Lowe

 Properties – Linear
Assume: I image f1, f2 filters
Linear: apply(I,f1+f2) = apply(I,f1) + apply(I,f2)
I is a white box on black, and f1, f2 are rectangles

A( , + ) =A( , )=

A( , )+A( , )= + =
Note: I am showing filters un-normalized and blown up. They’re a smaller
box filter (i.e., each entry is 1/(size^2))
credit: D Fouhey
 Properties – Shift-Invariant

Assume: I image, f filter

Shift-invariant: shift(apply(I,f)) = apply(shift(I,f))
Intuitively: only depends on filter neighborhood

A( , )=

A( , )=
credit: D Fouhey
 Painful Details – Signal Processing

Often called “convolution”. Actually cross-

correlation.

Cross-Correlation Convolution
(Original Orientation) (Flipped in x and y)

credit: D Fouhey
 Properties of Convolution
• Any shift-invariant, linear operation is a convolution (⁎)
• Commutative: f ⁎ g = g ⁎ f
• Associative: (f ⁎ g) ⁎ h = f ⁎ (g ⁎ h)
• Distributes over +: f ⁎ (g + h) = f ⁎ g + f ⁎ h
• Scalars factor out: kf ⁎ g = f ⁎ kg = k (f ⁎ g)
• Identity (a single one with all zeros):

* =
Property List: K. Grauman
 Questions?

• Nearly everything onwards is a convolution.

• This is important to get right.
 Smoothing With A Box
Intuition: if filter touches it, it gets a contribution.
Input Box Filter

credit: D Fouhey
 Solution – Weighted Combination

Intuition: weight contributions according to

closeness to center.

𝐹𝑖𝑙𝑡𝑒𝑟𝑖𝑗 ∝ 1
What’s this?

𝑥2 + 𝑦2
𝐹𝑖𝑙𝑡𝑒𝑟𝑖𝑗 ∝ exp −
2𝜎 2
credit: D Fouhey
 Recognize the Filter?
It’s a Gaussian!

1 𝑥2 + 𝑦2
𝐹𝑖𝑙𝑡𝑒𝑟𝑖𝑗 ∝ 2
exp −
2𝜋𝜎 2𝜎 2

0.003 0.013 0.022 0.013 0.003

0.013 0.060 0.098 0.060 0.013
0.022 0.098 0.162 0.098 0.022
0.013 0.060 0.098 0.060 0.013
0.003 0.013 0.022 0.013 0.003

credit: D Fouhey
 Smoothing With A Box & Gauss
Still have some speckles, but it’s not a big box
Input Box Filter Gauss. Filter

credit: D Fouhey
 Gaussian Filters

σ=1 σ=2 σ=4 σ=8

filter = 21x21 filter = 21x21 filter = 21x21 filter = 21x21

Note: filter visualizations are independently normalized throughout

the slides so you can see them better
credit: D Fouhey
 Applying Gaussian Filters

credit: D Fouhey
 Applying Gaussian Filters
Input Image
(no filter)

credit: D Fouhey
 Applying Gaussian Filters
σ=1

credit: D Fouhey
 Applying Gaussian Filters
σ=2

credit: D Fouhey
 Applying Gaussian Filters
σ=4

credit: D Fouhey
 Applying Gaussian Filters
σ=8

credit: D Fouhey
 Picking a Filter Size
Too small filter → bad approximation
Want size ≈ 6σ (99.7% of energy)
Left far too small; right slightly too small!
σ = 8, size = 21 σ = 8, size = 43

credit: D Fouhey
 Runtime Complexity
Image size = NxN = 6x6
Filter size = MxM = 3x3
I11 I12 I13 I14 I15 I16
for ImageY in range(N):
I21 F11
I22 F12
I23 F13
I24 I25 I26 for ImageX in range(N):
I31 I32
F21 I33
F22 I34
F23 I35 I36 for FilterY in range(M):
I41 F31
I42 F32
I43 F33
I44 I45 I46
for FilterX in range(M):
…
I51 I52 I53 I54 I55 I56

I61 I62 I63 I64 I65 I66

Time: O(N2M2)

credit: D Fouhey
 Separability

Conv(vector, transposed vector) → outer product

Fx1 * Fx2 * Fx3 *

Fy1 Fy1 Fy1 Fy1

Fy2 ⁎ Fx1 Fx2 Fx3 = Fx1 *

Fy2
Fx2 *
Fy2
Fx3 *
Fy2

Fx1 * Fx2 * Fx3 *

Fy3 Fy3 Fy3 Fy3

credit: D Fouhey
 Separability

1 𝑥2 + 𝑦2
𝐹𝑖𝑙𝑡𝑒𝑟𝑖𝑗 ∝ 2
exp −
2𝜋𝜎 2𝜎 2

→
𝑥21 1 𝑦2
𝐹𝑖𝑙𝑡𝑒𝑟𝑖𝑗 ∝ exp − 2 exp − 2
2𝜋𝜎 2𝜎 2𝜋𝜎 2𝜎

credit: D Fouhey
 Separability
1D Gaussian ⁎ 1D Gaussian = 2D Gaussian
Image ⁎ 2D Gauss = Image ⁎ (1D Gauss ⁎ 1D Gauss )
= (Image ⁎ 1D Gauss) ⁎ 1D Gauss

⁎ =

credit: D Fouhey
 Runtime Complexity
Image size = NxN = 6x6
Filter size = Mx1 = 3x1
I11 I12 I13 I14 I15 I16
for ImageY in range(N):
I21 F1
I22 I23 I24 I25 I26 for ImageX in range(N):
I31 I32
F2 I33 I34 I35 I36 for FilterY in range(M):
I41 F3
I42 I43 I44 I45 I46
…
for ImageY in range(N):
I51 I52 I53 I54 I55 I56
for ImageX in range(N):
I61 I62 I63 I64 I65 I66
for FilterX in range(M):
What are my compute …
savings for a 13x13 filter?
credit: D Fouhey
Time: O(N2M) old: N^2*13*13 new: N^2*13*2
 Why Gaussian?

Gaussian filtering removes parts of the signal

above a certain frequency. Often noise is high
frequency and signal is low frequency.

credit: D Fouhey
 Where Gaussian Fails

credit: D Fouhey
 Applying Gaussian Filters
σ=1

credit: D Fouhey
 Why Does This Fail?
Means can be arbitrarily distorted by outliers

Signal 10 12 9 8 1000 11 10 12

Filter 0.1 0.8 0.1

Output 11.5 9.2 107.3 801.9 109.8 10.3

What else is an “average” other than a mean?

credit: D Fouhey
 Non-linear Filters (2D)

[040, 081, 013, 125, 830, 076, 144, 092, 108]

Sort
40 81 13 22
[013, 040, 076, 081, 092, 108, 125, 144, 830]
125 830 76 80
144 92 108 95 92
132 102 106 87
[830, 076, 080, 092, 108, 095, 102, 106, 087]

Sort
[076, 080, 087, 092, 095, 102, 106, 108, 830]

95
credit: D Fouhey
 Applying Median Filter
Median
Filter
(size=3)

credit: D Fouhey
 Applying Median Filter
Median
Filter
(size = 7)

credit: D Fouhey
 Is Median Filtering Linear?

1 1 1 0 0 0 1 1 1
1 1 2 + 0 1 0 = 1 2 2
2 2 2 0 0 0 2 2 2
Median Filter

1 + 0 = 2

Example from (I believe): Kristen Grauman

 Filtering – Sharpening
Image Smoothed

-
Details

=
credit: D Fouhey
 Filtering – Sharpening
Image Details

+α
“Sharpened” α=1

=
credit: D Fouhey
 Filtering – Sharpening
Image Details

+α
“Sharpened” α=0

=
credit: D Fouhey
 Filtering – Sharpening
Image Details

+α
“Sharpened” α=2

=
credit: D Fouhey
 Filtering – Extreme Sharpening
Image Details

+α
“Sharpened” α=10

=
credit: D Fouhey
 Filtering

What’s this Filter?

T
-1 0 1 -1 0 1

Dx Dy

credit: D Fouhey
 Filtering – Derivatives

(Dx2 + Dy2 )1/2

credit: D Fouhey
 Filtering – Counting

How many “on” pixels have

10+ neighbors within 10 pixels?

Pixels Disk ???

⁎ r=10
=

credit: D Fouhey
 Filtering – Counting

How many “on” pixels have

10+ neighbors within 10 pixels?

Pixels Density Answer

x =

credit: D Fouhey
 Filtering – Missing Data
Oh no! Missing data!
(and we know where)

Common with many non-normal cameras (e.g., depth cameras)

credit: D Fouhey
 Filtering – Missing Data

Image ⁎

Per-element /

Binary
Mask ⁎
 Filtering – Missing Data

Image

Per-element /

Binary
Mask
Filtering – Missing Data

Before
Filtering – Missing Data

After
Filtering – Missing Data

After (without missing data)