CS计算机代考程序代写 matlab algorithm [06-30213][06-30241][06-25024]

[06-30213][06-30241][06-25024]
Computer Vision and Imaging &
Robot Vision
Dr Hyung Jin Chang Dr Yixing Gao
h.j.chang@bham.ac.uk y.gao.8@bham.ac.uk
School of Computer Science

Image Filtering
Hyung Jin Chang, Yixing Gao
08/02/2021

Next topic
• Image filtering
• Suggested reading:
– R. Szeliski, Computer Vision – Algorithms and Applications, Springer 2010:
– Chapter 3 Image Processing • 3.2 Linear filtering
• 3.4 Fourier transforms
Hyung Jin Chang, Yixing Gao
08/02/2021

Image Formation
Slide credit: Derek Hoiem

Digital images
Slide credit: Derek Hoiem
CMOS sensor

Images as functions
• We can think of an image as a function, 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]
• A color image is just three functions pasted 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

Images as functions
• An image contains discrete number of pixels, e.g.
– “grayscale”
(or “intensity”): [0,255]
Source: F.F Lei

Images as functions
• An image contains discrete number of pixels, e.g.
– “grayscale”
(or “intensity”): [0,255]
– Color
• RGB: [R, G, B]
• Lab: [L, a, b] • HSV: [H, S, V]
Source: F.F Lei

Digital color images
Color images, RGB color space
Slide credit: Kristen Grauman
RGB

Images as discrete functions
• 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.
2D
1D

Images as discrete functions • Cartesian coordinates

Images in Matlab
• Images represented as a matrix
• Suppose we have an NxM RGB image called “im”
– im(1,1,1) = top-left pixel value in R-channel
– im(y, x, b) = y pixels down, x pixels to right in the bth channel
– im(N, M, 3) = bottom-right pixel in B-channel
• imread(filename) returns a uint8 image (values 0 to 255) – Convert to double format (values 0 to 1) with im2double
row column R
0.92
0.95
0.89
0.96
0.71
0.49
0.86
0.96
0.69
0.79
0.91
0.93
0.89
0.72
0.95
0.81
0.62
0.84
0.67
0.49
0.73
0.94
0.94
0.82
0.51 0.92
0.88 0.95
0.81 0.89
0.60 0.96
0.74 0.71
0.54 0.49
0.56 0.86
0.90 0.96
0.89 0.69
0.79
0.91
0.97
0.89
0.55 0.93
0.94 0.89
0.87 0.72
0.58 0.95
0.58 0.81
0.85 0.62
0.66 0.84
0.67 0.67
0.49 0.49
0.73
0.94
0.62
0.56
0.51 0.94
0.56 0.82
0.57 0.51
0.92 0.50
0.88
0.95 0.51
0.81
0.89 0.48
0.60
0.96 0.43
0.74
0.71 0.33
0.54
0.49 0.41
0.56 0.86
0.90 0.96
0.89 0.69
0.79
0.91
0.37
0.31
0.42 0.97
0.46 0.89
0.37 0.55
0.93 0.60
0.94
0.89 0.39
0.87
0.72 0.37
0.58
0.95 0.42
0.58
0.81 0.61
0.85
0.62 0.78
0.66 0.84
0.67 0.67
0.49 0.49
0.73
0.94
0.85
0.75
0.57 0.62
0.91 0.56
0.80 0.51
0.94 0.58
0.56
0.82 0.73
0.57
0.51 0.88
0.50
0.88 0.77
0.51
0.81 0.69
0.48
0.60 0.78
0.43 0.74
0.33 0.54
0.41 0.56
0.90
0.89
0.97
0.92
0.41 0.37
0.87 0.31
0.88 0.42
0.97 0.50
0.46
0.89 0.92
0.37
0.55 0.90
0.60
0.94 0.73
0.39
0.87 0.79
0.37
0.58 0.77
0.42 0.58
0.61 0.85
0.78 0.66
0.67
0.49
0.93
0.81
0.49 0.85
0.90 0.75
0.89 0.57
0.62 0.61
0.91
0.56 0.91
0.80
0.51 0.94
0.58
0.56 0.71
0.73
0.57 0.73
0.88
0.50 0.89
0.77 0.51
0.69 0.48
0.78 0.43
0.33
0.41
0.92
0.95
0.91 0.97
0.97 0.92
0.79 0.41
0.37 0.45
0.87
0.31 0.49
0.88
0.42 0.82
0.50
0.46 0.90
0.92
0.37 0.93
0.90
0.60 0.99
0.73 0.39
0.79 0.37
0.77 0.42
0.61
0.78
0.99
0.91
0.92 0.93
0.95 0.81
0.85 0.49
0.85 0.33
0.90
0.75 0.74
0.89
0.57 0.93
0.61
0.91 0.99
0.91
0.80 0.97
0.94
0.58 0.93
0.71 0.73
0.73 0.88
0.89 0.77
0.69
0.78
0.92
0.95
0.91 0.97
0.97 0.92
0.79 0.41
0.45 0.87
0.49 0.88
0.82 0.50
0.90 0.92
0.93 0.90
0.99 0.73
0.79
0.77
0.99
0.91
0.92 0.93
0.95 0.81
0.85 0.49
0.33 0.90
0.74 0.89
0.93 0.61
0.99 0.91
0.97 0.94
0.93 0.71
0.73
0.89
0.92
0.95
0.91
0.97
0.79
0.45
0.49
0.82
0.90
0.93
0.99
0.99
0.91
0.92
0.95
0.85
0.33
0.74
0.93
0.99
0.97
0.93
G
B
Slide credit: Derek Hoiem

Image filtering
• 1st stage in most CV applications; image processing converts image into more suitable form for further analysis.
• Compute a function of the local neighborhood at each pixel in the image
– Function specified by a “filter” or mask saying how to combine values from neighbors
• Uses of filtering:
– Enhance an image (denoise, resize, increase contrast, etc) – Extract information (texture, edges, interest points, etc) – Detect patterns (template matching)
Slide credit: Kristen Grauman, Adapted from Derek Hoiem

Can be applied for…

Motivation: noise reduction
• Even multiple images of the same static scene will not be identical.
Slide adapted from Kristen Grauman

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
– Basic assumption:
Noise is an i.i.d. (independent & identically distributed)
Slide credit: Steve Seitz

Gaussian noise
Matlab:
>> im = imread(“peppers.jpg”);
>> noise = randn(size(im)).*sigma; >> output = im + noise;
Figure from Martial Hebert
What is impact of the sigma?

Effect of sigma on Gaussian noise:
Image shows the noise values themselves.

sigma=1
Effect of sigma on Gaussian noise:
This shows the noise values added to the raw intensities of an image.

sigma=16
Effect of sigma on Gaussian noise
This shows the noise values added to the raw intensities of an image.

Motivation: noise reduction
• Even multiple images of the same static scene will not be identical.
• How could we reduce the noise, i.e., give an estimate of the true intensities?
• What if there’s only one image? Slide credit: Kristen Grauman

First attempt at a solution
• Let’s replace each pixel with an average of all the values in its neighborhood
• Assumptions:
– Expect pixels are similar to their neighboring pixels
– Expect noise processes to be independent from pixel to pixel
(i.i.d. = independent, identically distributed)
Slide credit: Kristen Grauman

First attempt at a solution
• Let’s replace each pixel with an average of all the values in its neighborhood
• Moving average in 1D:
Slide credit: S. Marschner

Weighted Moving Average
• Can add weights to our moving average
• Weights [1, 1, 1, 1, 1] / 5
Slide credit: S. Marschner

Weighted Moving Average
• Non-uniform weights [1, 4, 6, 4, 1] / 16
Slide credit: S. Marschner

Moving Average In 2D
g[x, y]
f [x, y]
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
Slide credit: Steve Seitz

Moving Average In 2D
g[x, y]
f [x, y]
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
Slide credit: Steve Seitz

Correlation filtering
Say the averaging window size is 2k+1 x 2k+1:
Attribute uniform Loop over all pixels in neighborhood weight to each pixel around image pixel f[i,j]
Now generalize to allow different weights depending on neighboring pixel’s relative position:
Slide adapted from Kristen Grauman
Non-uniform weights

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.
(0, 0)
f
(N, N)
Slide adapted from Matej Kristan
40
1h2 34

Averaging filter
• What values belong in the kernel h for the moving average example?
f [x, y]
h[u,v]
g[x, y]
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
1
1
1
1
?
1
1
1
1
1
“box filter”
Slide adapted from Kristen Grauman

Smoothing by averaging
original
This is a box filter: white = high value black = low value
Slide credit: Kristen Grauman
What if the filter size was 5 x 5 instead of 3 x 3?
filtered

Boundary issues
• What about near the edge?
– the filter window falls off the edge of the image – need to extrapolate
– methods:
• clip filter (black)
• wrap around
• copy edge
• reflect across edge
Slide credit: S. Marschner

Boundary issues
• What about near the edge?
– the filter window falls off the edge of the image
– need to extrapolate – methods (MATLAB):
Slide credit: S. Marschner
• clip filter (black):
• wrap around:
• copy edge:
• reflect across edge: imfilter(f, g, ‘symmetric’)
imfilter(f, g, 0)
imfilter(f, g, ‘circular’)
imfilter(f, g, ‘replicate’)

Gaussian filter
• What if we want nearest neighboring pixels to have the most influence on the output?
This kernel is an approximation of a 2d 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
h[u,v] f [x, y]
• Removes high-frequency components from the image (“low-pass filter”).
Slide credit: Steve Seitz

Gaussian Smoothing

Smoothing with a Gaussian

Smoothing with a box-filter

• •
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 σ = 5 with 30 x 30 kernel kernel
Slide credit: Kristen Grauman

Gaussian filters
• What parameters matter here?
• Variance of Gaussian: determines extent of smoothing
σ = 2 with 30 x 30 σ = 5 with 30 x 30 kernel kernel
Slide credit: Kristen Grauman

Matlab
>> hsize = 30;
>> sigma = 5;
>> h = fspecial(‘gaussian’, hsize, sigma);
>> mesh(h);
>> imagesc(h);
>> outim = imfilter(im, h); % correlation >> imshow(outim);
Slide credit: Kristen Grauman
outim

Smoothing with a Gaussian
Parameter σ is the “scale” / “width” / “spread” of the Gaussian kernel, and controls the amount of smoothing.
…
for sigma=1:3:10
h = fspecial(‘gaussian‘, hsize, sigma); out = imfilter(im, h);
imshow(out);
pause;
end
Slide credit: Kristen Grauman

Properties of smoothing filters
• Smoothing
– Values positive
– Sum to 1→constant regions same as input
– Amount of smoothing proportional to mask size
– Remove “high-frequency” components; “low-pass” filter
Slide credit: Kristen Grauman

Filtering an impulse signal
What is the result of filtering the impulse signal (image) f with the arbitrary kernel h?
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
?
a
b
c
d
e
f
g
h
i
f [x, y] Slide adapted from Kristen Grauman
g[x, y]
h[u,v]

Convolution
• Convolution:
– Flip the filter in both dimensions (bottom to top, right to left) – Thenapplycross-correlation
h
f
Slide adapted from Kristen Grauman
Notation for convolution operator
h

Convolution vs. correlation
• Correlation
Matlab function: filter2 imfilter
• Convolution
—
Matlab function:
conv2
*
• For a symmetric filter, h(-u,-v) = h(u,v), this holds: correlation ≡ convolution
Slide adapted from Matej Kristan

Properties of convolution
• Shift-invariant:
• Operator behaves the same everywhere, i.e. the value of
the output depends on the pattern in the image neighborhood, not the position of the neighborhood.
• Linearity:
Slide adapted from Matej Kristan

Properties of convolution
• Commutative:
• Associative:
𝑓∗𝑔=𝑔∗𝑓
(𝑓 ∗ 𝑔) ∗ h = 𝑓 ∗ (𝑔 ∗ h)
• Application of multiple filters: (((𝑓 ∗ 𝑏1) ∗ 𝑏2) ∗ 𝑏3)
• Equal to application of a single filter: 𝑓 ∗ (𝑏 ∗ 𝑏 ∗ 𝑏 ) 123
• Distributes over addition:
𝑓∗ 𝑔+h =𝑓∗𝑔+𝑓∗h • Scalarsfactorout: 𝑘𝑓∗𝑔=𝑓∗𝑘𝑔=𝑘(𝑓∗𝑔)
• Identity:
• Differentiation:
Slide adapted from Matej Kristan
𝑓∗𝑒=𝑓
• A unit impulse: 𝑒 = […,0,0,1,0,0,…]
𝜕 (𝑓∗𝑔)=(𝜕 𝑓)∗𝑔=𝑓∗ (𝜕 𝑔) 𝜕𝑥 𝜕𝑥 𝜕𝑥

Effects of Convolution
• Convolution of two functions in image space is equivalent to the product of their corresponding spectra (Fourier transform).
𝑓∗𝑔↔𝐹∙𝐺
• Convolution manipulates the image spectrum – Enhancing/suppressingfrequencybansinimage

Convolution: removing noise

Low-band vs. High-band pass filters

Predict the outputs using correlation filtering
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
*
–
=?
Slide credit: Kristen Grauman

Practice with linear filters
0
0
0
0
1
0
0
0
0
?
Slide credit: David Lowe
Original

Practice with linear filters
0
0
0
0
1
0
0
0
0
Slide credit: David Lowe
Original
Filtered
(no change)

Practice with linear filters
0
0
0
0
0
1
0
0
0
?
Slide credit: David Lowe
Original

Practice with linear filters
0
0
0
0
0
1
0
0
0
Slide credit: David Lowe
Original
Shifted left by 1 pixel with correlation

Practice with linear filters
1
1
1
1
1
1
1
1
1
?
Slide credit: David Lowe
Original

Practice with linear filters
1
1
1
1
1
1
1
1
1
Slide credit: David Lowe
Original
Blur (with a box filter)

Practice with linear filters
0
0
0
0
2
0
0
0
0
1
1
1
1
1
1
1
1
1
–
?
Original
Slide credit: David Lowe

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:
Enhances differences by local average
Slide credit: David Lowe

Filtering examples: sharpening
Slide credit: Kristen Grauman

Separability
• In some cases, filter is separable, and we can factor into two steps:
– Convolve all rows
– Convolve all columns
Slide credit: Kristen Grauman

Separability
• In some cases, filter is separable, and we can factor into two
steps: e.g.,
g
f
Slide credit: Kristen Grauman
f * (g * h) = (f * g) * h
h

Efficient Implementation

Effect of smoothing filters
Slide credit: Kristen Grauman
Additive Gaussian noise Salt and pepper noise

Median filter (Non-linear filter)
• Basic idea
• Replace the pixel intensity by a median of intensities within a small patch
• Properties
• No new pixel values
introduced
• Removes spikes:
good for impulse, salt & pepper noise
• Non-linear filter
Slide credit: Kristen Grauman

Median filter
Salt and pepper noise
Median filtered
Slide credit: Martial Hebert
Plots of a col of the image
Matlab: output im = medfilt2(im, [h w]);

Median filter
• Median filter is edge preserving
Slide credit: Kristen Grauman

Gaussian Filter vs. Median Filter
Slide credit: Svetlana Lazebnik

Filtering application: Hybrid Images
Slide credit: Kristen Grauman Aude Oliva & Antonio Torralba & Philippe G Schyns, SIGGRAPH 2006

Application: Hybrid Images
Gaussian Filter
A. Oliva, A. Torralba, P.G. Schyns, “Hybrid Images,” SIGGRAPH 2006
Laplacian Filter
Slide credit: Kristen Grauman
unit impulse
Gaussian Laplacian of Gaussian

Aude Oliva & Antonio Torralba & Philippe G Schyns, SIGGRAPH 2006

Summary
• Image formation
• Image “noise”
• Linear filters and convolution useful for
– Enhancing images (smoothing, removing noise) • Box filter
• Gaussian filter
• Impact of scale / width of smoothing filter
Hyung Jin Chang, Yixing Gao
08/02/2021

Related Posts