2/11/2021
CSE 473/573
‘-
Introduction to Computer Vision and Image Processing
1
IMAGE PROCESSING
‘-
2
1
2/11/2021
Creating an Image… Lets Drill Down…
Digital Camera
Image Processing Image Processing
‘-
SCENE
3
‘-
Slide credit Fei Fei Li
4
2
2/11/2021
Upcoming classes: three views of filtering
• Image filters in spatial domain
– Filter is a mathematical operation of a grid of numbers – Smoothing, sharpening, measuring texture
‘-
• Image filters in the frequency domain
– Filtering is a way to modify the frequencies of images – Denoising, sampling, image compression
• Templates and Image Pyramids
– Filtering is a way to match a template to the image
– Detection, coarse-to-fine registration 5
Today: Image Filters
Smooth/Sharpen Images… Find edges…
‘-
Find Waldo…
6
3
2/11/2021
Image filtering
• Image filtering: compute function of local neighborhood at each position
• Really important! • Enhance images
‘-
‐ Denoise, resize, increase contrast, etc. • Extract information from images
‐ Texture, edges, distinctive points, etc. • Detect patterns
‐ Template matching
‐ Deep Convolutional Networks
7
Image neighborhoods
• Q: What happens if we reshuffle all pixels within the images?
‘-
• A: Its histogram won’t change. Point-wise processing unaffected.
• Need to measure properties relative to small neighborhoods of pixels
8
4
2/11/2021
Images as functions
• Wecanthinkofanimageasafunction,f,from R2 to R:
• f( x, y ) gives the intensity at position ( x, y )
• Realistically, we expect the image only to be defined over a
rectangle, with a finite range: – f: [a,b] x [c,d][0, 1.0]
• Acolorimageisjustthreefunctionspasted together. We can write this as a “vector-valued”
function:
‘-
r(x, y) f (x, y) g(x, y)
b(x, y)
Source: S. Seitz
9
Digital images
• In computer vision we operate on digital (discrete) images:
• Sample the 2D space on a regular grid
• Quantize each sample (round to nearest integer)
‘-
• Image thus represented as a matrix of integer values.
f(x,y) y
x
2D 1D
10
Adapted from S. Seitz
5
2/11/2021
Motivation: noise reduction
• We can measure noise in multiple images of the same static scene.
• How could we reduce the noise, i.e., give an estimate of the true intensities?
‘-
11
Common types of noise
• Salt and pepper noise: random occurrences of black and white pixels
• Impulse noise: random occurrences of white pixels
• Gaussian noise: variations in intensity drawn from a Gaussian normal distribution
Original ‘-
Impulse noise
Salt and pepper noise
Gaussian noise
Source: S. Seitz
12
6
2/11/2021
Gaussian noise
‘-
13
Fig: M. Hebert
sigma=1
Effect of sigma on Gaussian noise:
‘- Image shows the noise values
themselves.
14
7
2/11/2021
sigma=4
‘-
15
sigma=16
‘-
16
8
2/11/2021
sigma=1
Effect of sigma on Gaussian noise:
This shows the noise values added to the raw intensities of an image.
17
‘-
sigma=16
‘-
18
9
2/11/2021
First attempt at a solution
• Let’s replace each pixel with an average of all the values in its neighborhood
• Assumptions:
• Expect pixels to be like their neighbors ‘-
• Expect noise processes to be independent from pixel to pixel
19
First attempt at a solution
• Let’s replace each pixel with an average of all the values in its neighborhood
• Assumptions:
• Expect pixels to be like their neighbors
• Expect noise processes to be independent from pixel to pixel ‘-
• Moving average in 1D:
20
Source: S. Marschner
10
2/11/2021
Weighted Moving Average
• Can add weights to our moving average • Weights [1,1,1,1,1] /5
‘-
21
Source: S. Marschner
Weighted Moving Average
• Non-uniform weights [1, 4, 6, 4, 1] / 16
‘-
22
Source: S. Marschner
11
2/11/2021
Example: Box Filter
g[,] ‘- 1
Slide credit: David Lowe (UBC)
1
1
1
1
1
1
1
1
23
f [.,.] h[.,.]
g[,]
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0 0
0 0
0 0
90 90
0 0
90 90
90 90
90 90
0 0
0 0
0 0
0 0
0 0
90 90
90 90
90 90
90 90
90 90
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
90 90
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0
‘-
h[m,n]g[k,l] f[mk,nl] k,l
24
Credit: S. Seitz
1
1
1
1
1
1
1
1
1
12
2/11/2021
1
1
1
f [.,.] h[.,.]
g[,]
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
0
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
‘-
h[m,n]g[k,l] f[mk,nl] k,l
25
Credit: S. Seitz
f [.,.] h[.,.]
g[,]
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
0
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
20
‘-
h[m,n]g[k,l] f[mk,nl] k,l
26
Credit: S. Seitz
1
1
1
1
1
1
1
1
1
13
2/11/2021
1
1
1
f [.,.] h[.,.]
g[,]
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
0
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
20
30
‘-
h[m,n]g[k,l] f[mk,nl] k,l
27
Credit: S. Seitz
f [.,.] h[.,.]
g[,]
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
0
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
20
30
30
‘-
h[m,n]g[k,l] f[mk,nl] k,l
28
Credit: S. Seitz
1
1
1
1
1
1
1
1
1
14
2/11/2021
f [.,.] h[.,.]
g[,]
0
10
20
30
30
‘-
?
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
0
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
h[m,n]g[k,l] f[mk,nl] k,l
29
Credit: S. Seitz
1
1
1
1
1
1
1
1
1
1
1
1
f [.,.] h[.,.]
g[,]
1
1
1
1
1
1
0
10
20
30
30
‘-
?
50
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
0
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
h[m,n]g[k,l] f[mk,nl] k,l
30
Credit: S. Seitz
15
2/11/2021
1
1
1
f [.,.] h[.,.]
g[,]
1
1
1
1
1
1
0
10
20
30
30
30
20
10
0
20
40
60
60
60
40
20
0
30
‘-
60
90
90
90
60
30
0
30
50
80
80
90
?
60
30
0
30
50
80
80
90
60
30
0
20
30
50
50
60
40
20
10
20
30
30
30
30
20
10
10
10
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
0
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
h[m,n]g[k,l] f[mk,nl] k,l
31
Credit: S. Seitz
What does it do?
• Replaces each pixel with an average of its neighborhood
• Achieve smoothing effect (remove sharp features)
g[,]
1
‘- 1
1
1
1
1
1
1
1
Slide credit: David Lowe (UBC)
32
16
2/11/2021
Smoothing with box filter
‘-
33
=? *
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
*
=?
‘-
0
0
0
0
2
0
0
0
0
1
1
1
1
1
1
1
1
1
*
–
=?
Predict the filtered outputs
34
17
2/11/2021
Practice with linear filters
Original
‘- ?
0
0
0
0
1
0
0
0
0
35
Source: D. Lowe
Practice with linear filters
Original
‘-
0
0
0
0
1
0
0
0
0
Filtered (no change)
Source: D. Lowe
36
18
2/11/2021
Practice with linear filters
Original
‘- ?
0
0
0
0
0
1
0
0
0
37
Source: D. Lowe
Practice with linear filters
Original
‘-
0
0
0
0
0
1
0
0
0
Shifted left By 1 pixel
Source: D. Lowe
38
19
2/11/2021
Practice with linear filters
0
0
0
0
2
0
0
0
0
1
1
1
1
1‘-1
1
1
1
–
(Note that filter sums to 1)
?
39
Source: D. Lowe
Original
Practice with linear filters
0
0
0
0
2
0
0
0
0
1
1
1
1
1‘-1
1
1
1
–
Original
Sharpening filter
Accentuates differences with local average
40
Source: D. Lowe
20
2/11/2021
Sharpening
‘-
41
Source: D. Lowe
Correlation filtering
Say the averaging window size is 2k+1 x 2k+1:
‘-
Now generalize to allow different weights depending on neighboring pixel’s relative position:
Non-uniform weights
Attribute uniform Loop over all pixels in neighborhood weight to each pixel around image pixel F[i,j]
42
21
2/11/2021
Correlation filtering
‘-
This is called cross-correlation, denoted
Filtering an image: replace each pixel with a linear combination of its neighbors.
The filter “kernel” or “mask” H[u,v] is the prescription for the weights in the linear combination.
43
Key properties of linear filters
Linearity:
imfilter(I, f1 + f2) = imfilter(I,f1) + imfilter(I,f2)
Shift invariance: same behavior regardless of pixel location imfilter(I,shift(f)) = shift(imfilter(I,f))
Any linear, shift-invariant operator can be represented as a convolution
45
Source: S. Lazebnik
‘-
22
2/11/2021
More properties
• Commutative:a*b=b*a
• Conceptually no difference between filter and signal
• But particular filtering implementations might break this equality
• Associative:a*(b*c)=(a*b)*c
• Often apply several filters one after another: (((a * b1) * b2) * b3)
• This is equivalent to applying one filter: a * (b1 * b2 * b3)
• Distributesoveraddition:a*(b+c)=(a*b)+(a*c)
• Scalarsfactorout:ka*b=a*kb=k(a*b)
• Identity: unit impulse e = [0, 0, 1, 0, 0], a*e=a
‘-
46
Source: S. Lazebnik
Gaussian filter
• What if we want nearest neighboring pixels to have the most influence on the output?
This kernel is an approximation of a Gaussian function:
‘-
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
90
0
90
90
90
0
0
0
0
0
90
90
90
90
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
1
2
4
2
1
2
1
47
Source: S. Seitz
23
2/11/2021
Smoothing with a Gaussian
Parameter σ is the “scale” / “width” / “spread” of the Gaussian kernel, and controls the amount of smoothing.
‘-
…
48
Gaussian filters
• What parameters matter here? • Size of kernel or mask
• Note, Gaussian function has infinite support, but
discrete filters use finite kernels
σ = 5 with 10 x 10 kernel σ = 5 with 30 x 30 kernel 49
‘-
24
2/11/2021
• Variance of Gaussian: determines extent of smoothing
σ = 2 with 30 x 30 kernel
‘-
σ = 5 with 30 x 30 kernel
50
Gaussian filters
• Remove “high-frequency” components from the image (low- pass filter)
• Images become more smooth
• Convolution with self is another Gaussian
– So can smooth with small-width kernel, repeat, and get same result as larger-width kernel would have
– Convolving two times with Gaussian kernel of width σ is same as convolving once with kernel of width σ√2
• Separable kernel
– Factors into product of two 1D Gaussians
‘-
51
Source: K. Grauman
25
2/11/2021
Smoothing with Gaussian filter
‘-
52
Smoothing with box filter
‘-
53
26
2/11/2021
Separability of the Gaussian filter
‘-
54
Source: D. Lowe
Separability
• In some cases, filter is separable, and we can factor into
two steps: e.g.,
h
g
f
What is the computational complexity advantage for a separable filter of size k x k, in terms of number of
f * (g * h) = (f * g) * h
operations per output pixel?
55
‘-
27
2/11/2021
Practical matters
How big should the filter be?
• Values at edges should be near zero
• Rule of thumb for Gaussian: set filter half-width to about 3 σ
‘-
56
Median filter
Salt and pepper noise
Median filtered
‘-
Plots of a row of the image
57
Source: M. Hebert
28
2/11/2021
Median filter
• Median filter is edge preserving
‘-
58
Other filters
‘-
1
0
-1
2
0
-2
1
0
-1
Sobel
Vertical Edge 59 (absolute value)
29
2/11/2021
Other filters
‘-
1
2
1
0
0
0
-1
-2
-1
Sobel
Horizontal Edge 60 (absolute value)
Filters for features
• Previously, thinking of filtering as a way to remove or reduce noise
• Now, consider how filters will
allow us to abstract higher-level ‘- “features”.
• Map raw pixels to an intermediate representation that will be used for subsequent processing
• Goal: reduce amount of data, discard redundancy, preserve what’s useful
61
30