CMT107 Visual Computing
CMT107 Visual Computing
Copyright By PowCoder代写 加微信 powcoder
Image Filtering
School of Computer Science and Informatics
Cardiff University
• Linear filtering
• Convolution
• Box filtering
• Gaussian filtering
• Separable kernel
• Median filter
• Sharpening
Acknowledgement
The majority of the slides in this section are from at University of Illinois at Urbana-Champaign
CMT107 Visual Computing 2
Image Filtering
• Filtering is a technique for modifying or enhancing an image
• Emphasise certain features or remove other feature
• Filtering is a neighbourhood operation
• The output value of any given pixel is determined by the values of the pixels in the
neighbourhood of the corresponding input pixel
• Linear filtering is filtering in which the value of an output pixel is a linear
combination (weighted average) of the values of the pixels in the input pixel’s
neighbourhood
• Linear filtering can be represented by convolution
CMT107 Visual Computing 3
Linear Filtering
CMT107 Visual Computing 4
Motivation: Image Denoising
• How can we reduce noise in a photograph?
CMT107 Visual Computing 5
Moving Average
• Let’s replace each pixel with a weighted average of its neighbourhood
• The weights are called the filter kernel
Source: D. MT107 Visual Computing 6
Moving Average
• Let’s replace each pixel with a weighted average of its neighbourhood
• The weights are called the filter kernel
• What are the weights for the average of a 3×3 neighbourhood?
Source: D. MT107 Visual Computing 7
Moving Average
• Let’s replace each pixel with a weighted average of its neighbourhood
• The weights are called the filter kernel
• What are the weights for the average of a 3×3 neighbourhood?
“box filter”
Source: D. MT107 Visual Computing 8
Moving Average
• Let’s replace each pixel with a weighted average of its neighbourhood
• The weights are called the filter kernel
• What are the weights for the average of a 3×3 neighbourhood?
“box filter”
Source: D. MT107 Visual Computing 9
Moving Average
• Let’s replace each pixel with a weighted average of its neighbourhood
• The weights are called the filter kernel
• What are the weights for the average of a 3×3 neighbourhood?
“box filter”
Source: D. MT107 Visual Computing 10
Convolution
• Let 𝑓 be the image and 𝑔 be the kernel. The output of convolving 𝑓 with 𝑔 is
denoted 𝑓 ∗ 𝑔
Source: F. MT107 Visual Computing 11
Convolution
• Let 𝑓 be the image and 𝑔 be the kernel. The output of convolving 𝑓 with 𝑔 is
denoted 𝑓 ∗ 𝑔
Source: F. MT107 Visual Computing 12
Convolution
• Let 𝑓 be the image and 𝑔 be the kernel. The output of convolving 𝑓 with 𝑔 is
denoted 𝑓 ∗ 𝑔
Source: F. : kernel is
flipped for convolution
CMT107 Visual Computing 13
Convolution
• Let 𝑓 be the image and 𝑔 be the kernel. The output of convolving 𝑓 with 𝑔 is
denoted 𝑓 ∗ 𝑔
Source: F. MT107 Visual Computing 14
Convention: kernel is
flipped for convolution
Convolution
• Let 𝑓 be the image and 𝑔 be the kernel. The output of convolving 𝑓 with 𝑔 is
denoted 𝑓 ∗ 𝑔
Source: F. Durand
𝑓 ∗ 𝑔 𝑥, 𝑦 =
𝑓 𝑥 − 𝑖, 𝑦 − 𝑗 𝑔[𝑖, 𝑗]
CMT107 Visual Computing 15
Convention: kernel is
flipped for convolution
Linear Filter: Key Properties
• Linearity: filter(𝑓1 + 𝑓2) = filter(𝑓1) + filter(𝑓2)
• Shift invariance: same behaviour regardless of pixel location
filter(shift(𝑓)) = shift(filter(𝑓))
• Theoretical result: any linear shift-invariant operator can be represented as a
convolution
CMT107 Visual Computing 16
Linear Filter: More Properties
• Commutative: 𝑎 ∗ 𝑏 = 𝑏 ∗ 𝑎
• Conceptually no difference between filter and signal
• Associative: 𝑎 ∗ 𝑏 ∗ 𝑐 = 𝑎 ∗ 𝑏 ∗ 𝑐
• Often apply several filters one after another: ((𝑎 ∗ 𝑏1 ∗ 𝑏2) ∗ 𝑏3)
• This is equivalent to applying one filter: 𝑎 ∗ (𝑏1 ∗ 𝑏2 ∗ 𝑏3)
• Distributive over addition: 𝑎 ∗ 𝑏 + 𝑐 = (𝑎 ∗ 𝑏) + (𝑎 ∗ 𝑐)
• Scalars factor out: 𝑘𝑎 ∗ 𝑏 = 𝑎 ∗ 𝑘𝑏 = 𝑘(𝑎 ∗ 𝑏)
• Identity: unit pulse 𝑒 = … , 0, 0, 1, 0, 0, … , 𝑎 ∗ 𝑒 = 𝑎
CMT107 Visual Computing 17
Size of the Output
• “full”: output size is the sum of sizes of 𝑓 and 𝑔 minus 1
• “same”: output size is the same as the size of 𝑓
• “valid”: output size is the difference of the sizes of 𝑓 and 𝑔
full same valid
CMT107 Visual Computing 18
Boundary Pixels
• What about near the edge?
• The filter window falls off the edge of the image
• Need to extrapolate
• Clip filter (black)
• Wrap around
• Copy edge
• Reflect across edge
Source: S. Marschner
CMT107 Visual Computing 19
Boundary Pixels
• Clip filter (black)
Source: S. Marschner
CMT107 Visual Computing 20
Boundary Pixels
• Wrap around
Source: S. Marschner
CMT107 Visual Computing 21
Boundary Pixels
• Copy edge
Source: S. Marschner
CMT107 Visual Computing 22
Boundary Pixels
• Reflect across edge
Source: S. Marschner
CMT107 Visual Computing 23
Practice with Linear Filter
Source: D. MT107 Visual Computing 24
Practice with Linear Filter
Source: D.
(no change)
CMT107 Visual Computing 25
Practice with Linear Filter
Source: D. MT107 Visual Computing 26
Practice with Linear Filter
Source: D. left
by 1 pixel
CMT107 Visual Computing 27
Practice with Linear Filter
Source: D. MT107 Visual Computing 28
Practice with Linear Filter
Source: D.
(with a box filter)
CMT107 Visual Computing 29
Practice with Linear Filter
(Note that filter weights sum to 1)
Source: D. MT107 Visual Computing 30
Practice with Linear Filter
(Note that filter weights sum to 1)
Source: D. filter:
Accentuates differences
with local average
CMT107 Visual Computing 31
Smoothing with Box Filter revisited
• What’s wrong with this picture?
• What’s the solution?
Source: D. MT107 Visual Computing 32
Smoothing with Box Filter revisited
• What’s wrong with this picture?
• What’s the solution?
• To eliminate edge effect, weight contribution of neighbourhood pixels according to
their closeness to the centre.
“fuzzy blob”
CMT107 Visual Computing 33
• Constant factor at front makes volume sum to 1 (can be ignored when
computing the filter values, as we should renormalize weights to sum to 1 in
Gaussian Kernel
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. MT107 Visual Computing 34
Gaussian Kernel
• Standard deviation 𝜎 determines the extent of smoothing
σ = 2 with 30 x 30 kernel σ = 5 with 30 x 30 kernel
Source: K. Grauman
CMT107 Visual Computing 35
Choosing Kernel Width
• The Gaussian function has infinite support, but discrete filters use finite
σ = 5 with 10 x 10 kernel σ = 5 with 30 x 30 kernel
Source: K. Grauman
CMT107 Visual Computing 36
Choosing Kernel Width
• Rule of thumb: set filter half width to about 3𝜎
CMT107 Visual Computing 37
Gaussian vs. Box Filtering
CMT107 Visual Computing 38
Gaussian Filters
• Remove “high frequency” component from the image (low-pass filter)
• Convolution with self is another Gaussian
• So can smooth with small-𝜎 kernel, repeat, and get same result as large-𝜎 kernel
would have
• Convolving two times with Gaussian kernel with standard deviation 𝜎 is the same as
convolving one with Gaussian kernel with standard deviation 𝜎 2
• Separable kernel
• Factors into product of two 1D Gaussians
Source: K. Grauman
CMT107 Visual Computing 39
Separability of the Gaussian Filter
• The 2D Gaussian can be expressed as the product of two 1D functions: one is
a function of 𝑥, and the other is a function of 𝑦.
• In this case, the two functions are the identical 1D Gaussian.
Source: D. MT107 Visual Computing 40
Separability Example
Source: K. Grauman
2D convolution
(centre location only) *
CMT107 Visual Computing 41
Separability Example
Source: K. Grauman
332 = 1 × 2 + 2 × 3 + 1 × 3 = 11
= 2 × 3 + 4 × 5 + 2 × 5 = 36
= 1 × 4 + 2 × 4 + 1 × 6 = 18
2D convolution
(centre location only) *
CMT107 Visual Computing 42
Separability Example
Source: K. Grauman
332 = 1 × 2 + 2 × 3 + 1 × 3 = 11
= 2 × 3 + 4 × 5 + 2 × 5 = 36
= 1 × 4 + 2 × 4 + 1 × 6 = 18
2D convolution
(centre location only)
The filter factors into a
product of 1D filters
CMT107 Visual Computing 43
Separability Example
Source: K. Grauman
332 = 1 × 2 + 2 × 3 + 1 × 3 = 11
= 2 × 3 + 4 × 5 + 2 × 5 = 36
= 1 × 4 + 2 × 4 + 1 × 6 = 18
2D convolution
(centre location only)
The filter factors into a
product of 1D filters
Perform convolution along
CMT107 Visual Computing 44
Separability Example
Source: K. Grauman
332 = 1 × 2 + 2 × 3 + 1 × 3 = 11
= 2 × 3 + 4 × 5 + 2 × 5 = 36
= 1 × 4 + 2 × 4 + 1 × 6 = 18
2D convolution
(centre location only)
The filter factors into a
product of 1D filters
Perform convolution along
CMT107 Visual Computing 45
Separability Example
Source: K. Grauman
332 = 1 × 2 + 2 × 3 + 1 × 3 = 11
= 2 × 3 + 4 × 5 + 2 × 5 = 36
= 1 × 4 + 2 × 4 + 1 × 6 = 18
2D convolution
(centre location only)
The filter factors into a
product of 1D filters
Perform convolution along
Followed by convolution
along the remaining
CMT107 Visual Computing 46
Separability Example
Source: K. Grauman
332 = 1 × 2 + 2 × 3 + 1 × 3 = 11
= 2 × 3 + 4 × 5 + 2 × 5 = 36
= 1 × 4 + 2 × 4 + 1 × 6 = 18
2D convolution
(centre location only)
The filter factors into a
product of 1D filters
Perform convolution along
Followed by convolution
along the remaining
* = 1 × 11 + 2 × 18 + 1 × 18 = 65
CMT107 Visual Computing 47
Why is Separability Useful
• What is the complexity of filtering an 𝑛 × 𝑛 image with an 𝑚 ×𝑚 kernel?
• 𝑂(𝑛2 ×𝑚2)
• What if the kernel separable?
• 𝑂(𝑛2 ×𝑚)
CMT107 Visual Computing 48
• 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. MT107 Visual Computing 49
Gaussian Noise
• Mathematical model: sum
of many independent
• Good for small standard
deviations
• Assumption: independent,
zero-mean noise
Source: M. MT107 Visual Computing 50
Reducing Gaussian Noise
CMT107 Visual Computing 51
Reducing Salt and Pepper Noise
• What’s wrong with the results?
3×3 5×5 7×7
CMT107 Visual Computing 52
Alternative Idea: Median Filtering
• A median filter operates over a window by selecting the median intensity in
the window
• Is median filtering linear?
Source: K. Grauman
CMT107 Visual Computing 53
Median Filter
• What advantage does median filtering have over Gaussian filtering?
• Robustness to outliers
Source: K. Grauman
CMT107 Visual Computing 54
Median Filter
Salt-and-pepper noise Median filtered
Source: M. MT107 Visual Computing 55
Gaussian vs. Median Filter
3×3 5×5 7×7
CMT107 Visual Computing 56
Sharpening revisited
Source: D. MT107 Visual Computing 57
Sharpening revisited
• What does blurring take away?
original smoothed (5×5)
CMT107 Visual Computing 58
Sharpening revisited
• What does blurring take away?
original smoothed (5×5)
CMT107 Visual Computing 59
Sharpening revisited
• What does blurring take away?
• Let’s add it back
original smoothed (5×5)
original detail
CMT107 Visual Computing 60
Sharpening revisited
• What does blurring take away?
• Let’s add it back
original smoothed (5×5)
original detail
CMT107 Visual Computing 61
Unsharp Mask Filter
𝑓 + 𝛼 𝑓 − 𝑓 ∗ 𝑔 = 1 + 𝛼 𝑓 − 𝛼𝑓 ∗ 𝑔 = 𝑓 ∗ ( 1 + 𝛼 𝑒 − 𝛼𝑔)
image blurred
unit impulse
(identity)
CMT107 Visual Computing 62
Unsharp Mask Filter
𝑓 + 𝛼 𝑓 − 𝑓 ∗ 𝑔 = 1 + 𝛼 𝑓 − 𝛼𝑓 ∗ 𝑔 = 𝑓 ∗ ( 1 + 𝛼 𝑒 − 𝛼𝑔)
image blurred
unit impulse
(identity)
Gaussianunit impulse Laplacian of Gaussian
CMT107 Visual Computing 63
Image Filtering with Java
• Use filter() in BufferedImageOp
• Implement filtering without using filter() function
CMT107 Visual Computing 64
Use filter() Function
• Define a filter kernel
float[] km = { // low-pass filter kernel
0.1f, 0.1f, 0.1f, // Suppose the matrix has been flipped
0.1f, 0.2f, 0.1f,
0.1f, 0.1f, 0.1f
Kernel kernel = new Kernel(3, 3, km);
• Define an operator
BufferedImageOp op = null;
op = new ConvolveOp(kernel, ConvolveOp.EDGE_NO_OP, null);
• Call the filter() function
out = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
op.filter(in, out);
ConvolveOp(Kernel kernel, int edgeCondition,
RenderingHints hints)
• edgeCondition: ConvolveOp.EDGE_NO_OP or
ConvolveOp.EDGE_ZERO_FILL
CMT107 Visual Computing 65
Not Use filter() Function
• Define a filter kernel matrix
float[] km = { // low-pass filter kernel
0.1f, 0.1f, 0.1f, // Suppose the matrix has been flipped
0.1f, 0.2f, 0.1f,
0.1f, 0.1f, 0.1f
• Calculate convolution on each pixel
int[] rArray = new int[width*height]; //
for each pixel {
get the neighbourhood colours of the pixel
calculate the colour according to the convolution formula
set the pixel colour in the output image
• More details in Lab session 6
CMT107 Visual Computing 66
• What is filtering? What is linear filtering?
• What is convolution?
• How to do sharpening of image?
• What is box filtering, Gaussian filtering, and median filtering?
• What is separable kernel? Why use separable kernel?
CMT107 Visual Computing 67
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com