Lecture 2: Filtering
Recall: blurring and edge detection
Denoising
Edge detection
Recall: neighborhood filtering
0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 0 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
| | | | | | |
| ? | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
Filter kernel
Input
Output
Recall: neighborhood filtering
0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 0 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
| | | | | | |
| ? | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
Input
Output
Filter kernel
Recall: neighborhood filtering
0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 0 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
| | | | | | |
| ? | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
Filter kernel
Input
Output
Recall: neighborhood filtering
0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 0 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
| | | | | | |
| 40 | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
Filter kernel
Input
Output
Recall: neighborhood filtering
0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 0 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
| | | | | | |
| 40 | ? | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
Filter kernel
Input
Output
Recall: neighborhood filtering
0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 90 | 0 | 90 | 90 | 0 | 0 |
0 | 90 | 90 | 90 | 90 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 |
| | | | | | |
| 40 | 60 | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
Filter kernel
Input
Output
Today
Filtering
10
Adapted from Torralba, Freeman, Isola
Remove unwanted sources of variation, keeping only information that’s relevant for a task.
Image indexed by pixel
f[n, m]
g[n, m]
H
Linear filtering
11
Source: Torralba, Freeman, Isola
g[n, m]
f[n, m]
H
In matrix form:
A very general transformation:
(Assuming 1D signal for simplicity)
Linear filtering
12
Source: Torralba, Freeman, Isola
g[n, m]
f[n, m]
H
In matrix form:
Linear filtering
13
A linear filter in its most general form can be written as (for a 1D signal of length N):
In matrix form:
Source: Torralba, Freeman, Isola
Linear filtering
14
Can generalize to 2D image (for image of size NxM):
Source: Torralba, Freeman, Isola
15
Photo by Fredo Durand, slide adapted from Torralba, Freeman, Isola
Why handle each spatial position differently?�
Often want translation invariance for our linear filters.
Translation Invariance
There is an eye in the original image and the shifted image.
Translation should have no e ffect on determining this image is an eye.
f (x + h) = f (x)
Future: filters for classification of images
Convolution
Let h be the image and g be the kernel. The output of convolving h with g is:
17
Source: F. Durand
Convention: �kernel is “flipped”
g
h
g
f
Cross-correlation
Let be the image and be the kernel. The output of cross-correlating with is:
18
Adapted from: F. Durand
f
g
image
output
kernel
h
Cross-correlation
Let be the image and be the kernel. The output of cross-correlating with is:
19
f
g
image
output
kernel
h
Cross-correlation
Let be the image and be the kernel. The output of cross-correlating with is:
20
Source: F. Durand
f
g
image
output
kernel
h
Cross-correlation
Let be the image and be the kernel. The output of cross-correlating with is:
21
Source: F. Durand
shift image by (m, n)
f
g
image
output
kernel
h
Cross-correlation
Let be the image and be the kernel. The output of cross-correlating with is:
22
Source: F. Durand
f
g
image
output
kernel
h
dot product between h and shifted f
Cross-correlation
Is this equivalent to what we saw last class? Yes.
f
g
image
output
zero padding
h
Convolution
Let g be the image and h be the kernel. The output of convolving f with h is:
24
h
h
Source: F. Durand
Convention: �kernel is “flipped”
f
g
image
output
kernel
Why flip the kernel?
25
Convolution versus Cross-Correlation
Properties of the convolution
28
Commutative (no distinction between filter and image):
Associative (doesn’t matter what order you do 2 convolutions):
Distributive with respect to the sum:
1D Example of Convolution
Convolution and cross correlation were described discretely here but can be also thought of continuously with integration.
Today
Rectangular filters
31
=
Source: Torralba, Freeman, Isola
f[m,n]
h[m,n]
g[m,n]
Rectangular filters
32
=
Source: Torralba, Freeman, Isola
f[m,n]
h[m,n]
g[m,n]
“Naturally” occurring filters
33
Motion blur
Input image
Source: Torralba, Freeman, Isola
“Naturally” occurring filters
34
Convolution output
Convolution weights
Input image
Source: Torralba, Freeman, Isola
35
Camera shake
[Fergus et al., 2007]
Source: Torralba, Freeman, Isola
“Naturally” occurring filters
36
Source: Torralba, Freeman, Isola
Blur
Blurring revisited
What’s wrong with this result?
37
Source: D. Forsyth
Box filter
Blurring revisited
38
Source: S. Lazebnik
Idea: weight contribution of neighborhood pixels according to their closeness to the center
“fuzzy blob”
…
Gaussian kernel
39
Source: K. Grauman
σ = 2 with 30 x 30 kernel
σ = 5 with 30 x 30 kernel
Gaussian kernel
40
Source: K. Grauman
σ = 2 with 30 x 30 kernel
σ = 5 with 30 x 30 kernel
Gaussian vs. box filtering
41
Source: S. Lazebnik
Gaussian standard deviation
42
σ=2
σ=4
σ=8
Source: Torralba, Freeman, Isola
Smoothing with box filter revisited
43
Source: D. Forsyth
Smoothing with box filter revisited
44
“fuzzy blob”
Source: S. Lazebnik
Gaussian Kernel
45
Source: K. Grauman
σ = 2 with 30 x 30 kernel
σ = 5 with 30 x 30 kernel
Choosing kernel width
46
Source: K. Grauman
Choosing kernel width
47
Gaussian filters
48
Source: K. Grauman
Gaussian filters
49
Source: K. Grauman
Useful properties of Gaussian filters
50
Convolve a Gaussian filter with itself? Get another Gaussian.
=
Useful properties of Gaussian filters
51
I
blur(blur(I))
blur(blur(blur(I)))
Smooth with small σ repeatedly. Equivalent to smoothing with large σ!
Exploits associativity:
Useful properties of Gaussian filters
52
Gaussian kernels are separable.
I
blurx(I)
blury(blurx(I))
Recall: derivatives
53
Adapted from: Torralba, Freeman, Isola
Another option:
Problems with simple derivative filters
54
[1 -1]
Sensitive to “tiny” edges
Where’s the edge?
55
Noisy input image
Source: S. Seitz
Solution: smooth first
56
f
h
f * h
Source: S. Seitz
To find edges, look for peaks in
Derivative of Gaussian filter
57
Gaussian
Derivative of Gaussian (x)
Source: N. Snavely
Derivative of Gaussian filter
58
x-direction
y-direction
Source: N. Snavely
Gaussian Scale
59
σ=2
σ=4
σ=8
Source: Torralba, Freeman, Isola
Derivative of Gaussian scales
60
σ=2
σ=4
σ=8
Source: Torralba, Freeman, Isola
Derivatives in other directions
61
Adapted from N. Snavely
1 | 0 |
0 | -1 |
desired direction
What if we need lots of angles? This could get expensive.
Image
Steerable filters
62
= ?
+
=
Use a multivariable calculus fact:
Directional derivative = linear combination of partial derivatives.
Source: N. Snavely
Given and , steer to direction .
Computing a directional derivative
63
+
=
From multivariable calculus:
Directional derivative is a linear combination of partial derivatives
Source: N. Snavely
Also works for derivative of Gaussian filter
64
x direction
y direction
+
=
Source: N. Snavely
See [Freeman and Adelson, “Design and Use of Steerable Filters”, 1991] for a deeper look.
Filter approximations
65
1 | 2 | 1 |
1 | 3 | 3 | 1 |
1 | 4 | 6 | 4 | 1 |
Binomial filter Gaussian
1 | 2 | 1 |
0 | 0 | 0 |
-1 | -2 | -1 |
Sobel filter
Derivative of Gaussian
2nd derivatives
66
1 | -1 |
1 | -1 |
1 | -2 | 1 |
Laplacian filter
67
0 | 1 | 0 |
1 | -4 | 1 |
0 | 1 | 0 |
Laplacian filter
68
Detects edges and blobs, and not sensitive to orientation. But sensitive to noise.
Source: Torralba, Freeman, and Isola
Laplacian of Gaussian
69
Combine with Gaussian. Picks up “blob-like” structures.
“Blob” detection with Laplacian
70
Source: S. Lazebnik
Decomposing an image
71
-
+
-
Gaussian filter
(a.k.a. “low pass”)
Approx. Laplacian
(a.k.a. “high pass”)
Source: Torralba, Freeman, Isola
72
-
+
-
+
=
Source: Torralba, Freeman, Isola
Approx. Laplacian
Application: Hybrid Images
[A. Oliva, A. Torralba, P.G. Schyns, Hybrid Images, SIGGRAPH 2006]
73
Source: S. Lazebnik
Hybrid Images
74
Oliva & Schyns
Hybrid Images
75
78
79
80
Today
Denoising revisited: salt and pepper noise
Gaussian filter doesn’t work as well!
82
Source: S. Lazebnik
Blurring
83
Gaussian filter
Images from [Paris et al. “A Gentle Introduction to Bilateral Filtering and its Applications”, 2008]
Image filters aren’t “aware” of edges
Median filtering
84
Gaussian filter
Bilateral filter
Median filtered
result
Median filtering window sizes
85
Gaussian filter
Bilateral filter
Original
w = 5
w = 13
w = 21
Another approach
86
Let’s start by rewriting the Gaussian filter:
Bilateral filter
Blurred intensity
Gaussian density:
Bilateral filtering
87
Gaussian filter
Bilateral filter
What if we weight by appearance?
Bilateral filtering
88
Gaussian filter
Bilateral filter
Gaussian filter:
Bilateral filter:
Spatial Gaussian
Range Gaussian
Normalization constant
(to make weights sum to 1)
Bilateral filter
89
[Paris et al. “A Gentle Introduction to Bilateral Filtering and its Applications”, 2008]
Bilateral filter
90
[Paris et al. “A Gentle Introduction to Bilateral Filtering and its Applications”, 2008]
Denoising with Gaussian
91
Source: [Paris et al. 2008]
Noisy image
Gaussian blur σ = 3
Gaussian blur σ = 5
Denoising with Bilateral Filter
92
Source: [Paris et al. 2008]
Original
Noisy image
Bilateral filtering
Iteratively applying the filter
93
Source: [Paris et al. 2008]
Iteratively applying the filter
94
[Winnemoller et al., 2006]
“Cartoonifying” a video
Image patches as filters
Source: D. Hoiem
Matching with filters
Method 1: Filter the image with
Input
Filtered Image
What went wrong?
f = image
g = filter
Source: D. Hoiem
Matching with filters
Input
Filtered Image (scaled)
Thresholded Image
True detections
False detections
mean of f
Method 2: Filter the image with zero-mean eye.
`
Source: D. Hoiem
Matching with filters
mean image patch
mean template
Method 3: Normalized cross-correlation. �Divide by standard deviation of both patches, so they are unit vectors.
Source: D. Hoiem
Matching with filters
Input
Normalized X-Correlation
Thresholded Image
True detections
Method 3: Normalized cross-correlation.
Source: D. Hoiem
Recognizing objects: is it really so hard?
This is a chair
Find the chair in this image
Output of normalized correlation
Source: A. Torralba
Recognizing objects: is it really so hard?
Find the chair in this image
Not so great!
Source: A. Torralba
What makes an image “natural”?
Natural image
“Fake” image
Source: Torralba, Freeman, Isola
Is it the distribution of pixel intensities?
Intensity histogram
No real structure here…
What about gradients?
g[m,n]
h[m,n]
=
f[m,n]
[-1, 1]
Source: Torralba, Freeman, Isola
What about gradients?
g[m,n]
h[m,n]
=
f[m,n]
[-1, 1]T
Source: Torralba, Freeman, Isola
Filter response distribution is pretty consistent!
Source: Torralba, Freeman, Isola
Red – true pdf
Black – best Gaussian fit
Image
[1 -1] filter output
[1 -1] output histogram
Intensity histogram
Source: Torralba, Freeman, Isola
Applications of image statistics
Compression
Image restoration
Learning
(later in course)
Taking a picture…
109
What the camera give us…
How do we correct this?
Source: R. Fergus
Image formation process
=
⊗
Blurry image
Sharp image
Blur �kernel
Input to algorithm
Desired output
Convolution�operator
Source: R. Fergus
Multiple possible solutions
=
⊗
Blurry image
Sharp image
Blur kernel
=
⊗
=
⊗
Source: R. Fergus
Natural image statistics
Histogram of image gradients
Characteristic distribution with heavy tails
Source: R. Fergus
Blurry images have different statistics
Histogram of image gradients
Source: R. Fergus
Removing motion blur
Original photograph
After matching filter distribution
Source: R. Fergus
Solve for an image with a distribution of edge gradients that “matches” a normal image.
Next class: image pyramids