COMP9517: Computer Vision
Image Processing I
Week 2
18/02/2021 COMP9517 T1 2021
1
Image processing
• Imageprocessing=imagein>imageout
• Aims to suppress distortions and enhance relevant information • Preparesimagesforfurtheranalysisandinterpretation
• Image analysis = image in > features out
• Computervision=imagein>interpretationout
18/02/2021 COMP9517 T1 2021
2
Types of image processing
• Twomaintypesofimageprocessingoperations:
– Spatial domain operations (in image space)
– Frequency domain operations (mainly in Fourier space)
• Twomaintypesofspatialdomainoperations:
– Point operations (intensity transformations on individual pixels) – Neighbourhood operations (spatial filtering on groups of pixels)
18/02/2021 COMP9517 T1 2021
3
Types of image processing
• Twomaintypesofimageprocessingoperations:
– Spatial domain operations (in image space)
– Frequency domain operations (mainly in Fourier space)
• Twomaintypesofspatialdomainoperations:
– Point operations (intensity transformations on individual pixels) – Neighbourhood operations (spatial filtering on groups of pixels)
18/02/2021 COMP9517 T1 2021
4
Topics and learning goals
• Describe the workings of basic point operations
Contrast stretching, thresholding, inversion, log/power transformations
• Understandingandusingtheintensityhistogram Histogram specification, equalization, matching
• Definingarithmeticandlogicaloperations Summation, subtraction, AND, OR, et cetera
18/02/2021 COMP9517 T1 2021
5
Spatial domain operations • Generalformofspatialdomainoperations
where
18/02/2021
is the input image
is the processed image is the operator applied at
COMP9517 T1 2021
6
Spatial domain operations • Point operations: operates on individual pixels
• Neighbourhood operations: operates on multiple pixels
18/02/2021
COMP9517 T1 2021
7
Point operations
18/02/2021 COMP9517 T1 2021
8
Neighbourhood operations
18/02/2021 COMP9517 T1 2021
9
Contrast stretching Input
Output
COMP9517 T1 2021
T
18/02/2021
LH
𝐼𝑛𝑝𝑢𝑡 𝑖𝑛𝑡𝑒𝑛𝑠𝑖𝑡𝑦 𝑙𝑒𝑣𝑒𝑙
10
𝑂𝑢𝑡𝑝𝑢𝑡 𝑖𝑛𝑡𝑒𝑛𝑠𝑖𝑡𝑦 𝑙𝑒𝑣𝑒𝑙
Contrast stretching
• Producesimagesofhighercontrast
• Puts values below in the input to black in the output
• Puts values above in the input to white in the output
• Linearly scales values between and in the input to the maximum range in the output
18/02/2021 COMP9517 T1 2021
11
Intensity thresholding Input
Output
T
18/02/2021
COMP9517 T1 2021
Threshold
𝐼𝑛𝑝𝑢𝑡 𝑖𝑛𝑡𝑒𝑛𝑠𝑖𝑡𝑦 𝑙𝑒𝑣𝑒𝑙
12
𝑂𝑢𝑡𝑝𝑢𝑡 𝑖𝑛𝑡𝑒𝑛𝑠𝑖𝑡𝑦 𝑙𝑒𝑣𝑒𝑙
Intensity thresholding • Limitingcaseofcontraststretching
• Producesbinaryimagesofgray-scaleimages
• Puts values below the threshold to black in the output
• Puts values equal/above the threshold to white in the output
• Popularmethodforimagesegmentation(discussedlater)
• Usefulonlyifobjectandbackgroundintensitiesareverydifferent
18/02/2021 COMP9517 T1 2021
13
Automatic intensity thresholding
• Otsu’smethodforcomputingthethreshold
Exhaustively searches for the threshold minimising the intra-class variance
Equivalent to maximising the inter-class variance (much faster to compute)
Here, 𝑝 is the fraction of pixels below the threshold (class 0), 𝑝 is the fraction of pixels equal
to or above the threshold (class 1), 𝜇 and 𝜇 are the mean intensities of pixels in class 0 and class 1, 𝜎 and 𝜎 are the intensity variances, and 𝑝 + 𝑝 = 1 and 𝜎 + 𝜎 = 𝜎
18/02/2021 COMP9517 T1 2021
14
Otsu thresholding
18/02/2021 COMP9517 T1 2021
15
Automatic intensity thresholding
• Iso-data method for computing the threshold 1. Select an arbitrary initial threshold
2. Compute and with respect to the threshold
3. Update the threshold to the mean of the means:
4. If the threshold changed in Step 3, go to Step 2
Upon convergence, the threshold is midway between the two class means
18/02/2021 COMP9517 T1 2021
16
Iso-data thresholding
18/02/2021 COMP9517 T1 2021
17
Multi-level thresholding
Input
Output
COMP9517 T1 2021
O
T
18/02/2021
I
18
Intensity inversion
Input
O
Output
T
18/02/2021
COMP9517 T1 2021
I
19
Intensity inversion
Useful for enhancing gray/white details in images within dominant black areas
18/02/2021 COMP9517 T1 2021
20
Log transformation • Definitionoflogtransformation
where is the input intensity, is the output intensity, and is a constant
– Mapsnarrowrangeoflowgray-levelvaluesintowiderrangeofoutput values, and opposite for higher gray-level values
– Alsocompressesdynamicrangeofimageswithlargevariationsinpixel values (such as Fourier spectra, discussed later)
18/02/2021 COMP9517 T1 2021
21
Log transformation
18/02/2021 COMP9517 T1 2021
22
Power transformation • Definition of power transformation
where and are constants
– Similartologtransformation
– Representsawholefamilyoftransformationsbyvarying
– Manydevicesrespondaccordingtoapowerlaw(gammacorrection) – Usefulforgeneral-purposecontrastmanipulation
18/02/2021 COMP9517 T1 2021
23
Power transformation
18/02/2021 COMP9517 T1 2021
24
Power transformation Input
18/02/2021
COMP9517 T1 2021
25
Piecewise linear transformations
• Complementarytoothertransformationmethods • Enable more fine-tuned design of transformations • Canhaveverycomplexshapes
• Requiresmoreuserinput
18/02/2021 COMP9517 T1 2021
26
Piecewise contrast stretching
• Oneofthesimplestpiecewiselineartransformations
• Increasesthedynamicrangeofgraylevelsinimages
• Used in display devices or recording media to span full range
18/02/2021 COMP9517 T1 2021
27
Piecewise contrast stretching
Week2 18/02/2021
COMP95172020T3 COMP9517 T1 2021
28 28
Transform
Input
Transformed
Binary Thresholding
Gray-level slicing
• Usedtohighlightspecificrangeofgraylevels
• Two different slicing approaches:
1) Highvalueforallgraylevelsinarangeofinterestandlowvalueforall
others (produces a binary image)
2) Brightenadesiredrangeofgraylevelswhilepreservingbackground and other gray-scale tones of the image
18/02/2021 COMP9517 T1 2021
29
Gray-level slicing
18/02/2021
COMP9517 T1 2021
30
Transform 1 Input
Transform 2
Result of Transform 1
Bit-plane slicing
• Highlightscontributiontototalimagebyspecificbits • Animagewithn-bits/pixelhasnbit-planes
• Slicingcanbeusefulforimagecompression
18/02/2021 COMP9517 T1 2021
31
Bit-planes of an 8-bit image
Bit-plane 7 (most significant)
151 =
1 0 0 1 0 1 1 1
Bit-plane 0 (least significant)
32
18/02/2021
COMP9517 T1 2021
Bit-planes of an 8-bit image
Input Bit-planes
18/02/2021
COMP9517 T1 2021
33
Histogram of pixel intensities
• Foreverypossibleintensitylevel,countthenumberofpixelshaving that level, and plot the pixel counts as a function of the level
h(r)
𝐿=2 =256 𝑁 = #pixels
L1
h(r) N
r0
Normalized histogram
= probability function
1 h(r) p(r) N
34
8-bit image
Intensity Level
18/02/2021
COMP9517 T1 2021
Count
Histogram processing
• Histogram equalization
Aim: To get an image with equally distributed intensity levels over the full intensity range
• Histogramspecification(alsocalledhistogrammatching) Aim: To get an image with a specified intensity distribution, determined by the shape of the histogram
18/02/2021 COMP9517 T1 2021
35
Histogram processing
18/02/2021 COMP9517 T1 2021
36
Enhances contrast for intensity values near histogram maxima and decreases contrast near histogram minima
Histogram equalization
18/02/2021
COMP9517 T1 2021
37 37
Histogram bins are much more “equal” here
• •
Histogram equalization
Let represent gray levels of the image represents black and represents white
Consider transformations , , satisfying
1) is single-valued and monotonically increasing in This guarantees that the inverse transformation exists
2) for
This guarantees that the input and output ranges will be the same
18/02/2021 COMP9517 T1 2021
38
Histogram equalization (continuous case)
Consider𝑟and𝑠ascontinuousrandomvariablesover 0,𝐿−1 withPDFs𝑝(𝑟)and𝑝(𝑠) If 𝑝(𝑟) and 𝑇(𝑟) are known and 𝑇(𝑠) satisfies monotonicity, then, from probability theory
𝑝 𝑠 = 𝑝(𝑟)||
Letuschoose: 𝑠=𝑇 𝑟 =(𝐿−1)∫𝑝 ξ 𝑑ξ
This is the CDF of 𝑟 which satisfies conditions (1) and (2)
Now: = ()= 𝐿−1 ∫𝑝 ξ 𝑑ξ =(𝐿−1)𝑝(𝑟)
Therefore: 𝑝𝑠 𝑠 = 𝑝𝑟 𝑟
This is a uniform distribution!
18/02/2021
= for0≤𝑠≤𝐿−1
COMP9517 T1 2021
39
Histogram equalization (discrete case)
For discrete values we get probabilities and summations instead of PDFs and integrals:
𝑝𝑟(𝑟𝑘)=𝑛𝑘/𝑀𝑁 for 𝑘 = 0,1,…,𝐿−1
where 𝑀𝑁 is total number of pixels in image, 𝑛 is the number of pixels with gray level 𝑟𝑘
and 𝐿 is the total number of gray levels in the image
Thus𝑠𝑘 =𝑇 𝑟𝑘 =(𝐿−1)∑𝑝 𝑟 = ∑𝑛 for 𝑘=0,1,…,𝐿−1
This transformation is called histogram equalization
However, in practice, getting a perfectly uniform distribution for discrete images is rare
18/02/2021 COMP9517 T1 2021
40
Histogram matching (continuous case)
Assume that 𝑟 and 𝑠 are continuous intensities and 𝑝(𝑧) is the target distribution for the output image From our previous analysis we know that the following transformation results in a uniform distribution:
𝑠=𝑇𝑟 =(𝐿−1)∫𝑝 ξ𝑑ξ
Now we can define a function 𝐺(𝑧) as:
𝐺 𝑧 = 𝐿 − 1 ∫ 𝑝 ξ 𝑑ξ = 𝑠
Therefore:
18/02/2021
𝑧=𝐺 𝑠 =𝐺 𝑇(𝑟)
COMP9517 T1 2021
41
Histogram matching (discrete case) For discrete image values we can write:
𝐿−1 𝑠𝑘=𝑇𝑟𝑘=(𝐿−1)𝑝𝑟=𝑀𝑁 𝑛
and therefore:
𝑘 = 0, 1, … , 𝐿 − 1
𝐺 𝑧 =(𝐿−1)∑𝑝(𝑧) 𝑧 = 𝐺(𝑠)
COMP9517 T1 2021
18/02/2021
42
•
Arithmetic and logical operations Defined on a pixel-by-pixel basis between two images
+ − ∗
/=
18/02/2021
COMP9517 T1 2021
43
^
AND OR XOR
…
Arithmetic and logical operations
• Useful arithmetic operations include addition and subtraction
–
18/02/2021 COMP9517 T1 2021
44
Arithmetic and logical operations • Useful logical operations include AND and OR
18/02/2021
Input Mask Input AND Mask
COMP9517 T1 2021
45
Arithmetic/Logic Operations
• on pixel-by-pixel basis between 2 or more images
• AND and OR operations are used for masking- selecting subimages as RoI
• subtraction and addition are the most useful arithmetic operations
18/02/2021
COMP9517 T1 2021 46
Chapter 3
Image Enhancement in the Spatial Domain
? (1)
18/02/2021
COMP9517 T1 2021
47
? (2)
Image Averaging
• Noisy image g(x, y) formed by adding noise n(x, y) to uncorrupted image f(x, y):
g(x, y) = f(x, y) + n(x, y)
• Assume that at each (x, y), the noise is uncorrelated and has zero average value.
• Aim: To obtain smoothed result by averaging a set of noisy images gi(x,y), i=1,2,…,K
1K
g (x ,y) K gi (x, y)
i1
• As K increases, the variability of the pixel values decreases
• assumes that images are spatially registered
18/02/2021
COMP9517 T1 2021 48
Chapter 3
Image Enhancement in the Spatial Domain
18/02/2021 COMP9517 T1 2021 49
Spatial Filtering
• These methods use a small neighbourhood of a pixel in the input image to produce a new brightness value for that pixel
• Also called filtering techniques
• Neighbourhood of is usually a square or rectangular subimage
centred at – called filter / mask / kernel /template / window
• A linear transformation calculates a value in the output image g(i, j) as a linear combination of brightnesses in a local neighbourhood of the pixel in the input image f(i, j), weighted by coefficients h:
• This is called a discrete convolution with a convolution mask 18/02/2021 COMP9517 T1 2021
50
Convolution
Spatial Filtering
18/02/2021
COMP9517 T1 2021
51
Smoothing Spatial Filters
Used for blurring, noise reduction
Neighbourhood Averaging (Mean Filter)
• Replace intensity at pixel (x, y) with the average of the intensities in a neighbourhood of (x, y).
• We can also use a weighted average, giving more importance to some pixels over others in the neighbourhood- reduces blurring
• Neighbourhood averaging blurs edges
COMP9517 T1 2021
(,)∈
18/02/2021
52
18/02/2021
Chapter 3
Image Enhancement in the Spatial Domain
COMP9517 T1 2021 53
Chapter 3
Image Enhancement in the Spatial Domain
18/02/2021 COMP9517 T1 2021
54
18/02/2021
• Uses redundancy in the image data
• May blur sharp edges, so care is needed
COMP9517 T1 2021
55
Another example
Consider an image of constant intensity, with widely isolated pixels with different intensity from the background. We wish to detect these pixels.
Use the following mask:
-1 -1 -1
-1 8 -1 -1 -1 -1
Smoothing Spatial Filters
• Aim: To suppress noise, other small fluctuations in image- may be result of sampling, quantization, transmission, environment disturbances during acquisition
18/02/2021
Gaussian Filter
• Replace intensity at pixel (x, y) with the weighted average of the intensities in a neighbourhood of (x, y).
• It is a set of weights that approximate the profile of a Gaussian function.
• It is very effective in reducing noise and also reducing details (image blurring )
COMP9517 T1 2021
56
Gaussian Filter
18/02/2021 COMP9517 T1 2021
57
Non-linear Spatial Filters
Also called order-statistics filters- response based on ordering the pixels in the neighbourhood, and replacing centre pixel with the ranking result.
Median Filter
•intensity of each pixel is replaced by the median of the intensities in neighbourhood of that pixel
•Median M of a set of values is the middle value such that half the values in the set are less than M and the other half greater than M
•Median filtering forces points with distinct intensities to be more like their neighbours, thus eliminating isolated intensity spikes
•Also, isolated pixel clusters (light or dark), whose area is <= n^2/2, are eliminated by nxn median filter
•Good for impulse noise (salt-and-pepper noise)
•Other examples of order-statistics filters are max and min filters
COMP 9517 T2, 2020 18/02/2021 COMP9517 T1 2021
58
Median Filter
69
37
19
51
43
44
50
58
68
?
69
37
19
51
43
44
50
58
68
19
37
43
44
50
51
58
68
69
18/02/2021 COMP9517 T1 2021
59
Chapter 3
Image Enhancement in the Spatial Domain
18/02/2021 COMP9517 T1 2021
60
Pooling
Max / average/ median pooling
Provides translation invariance
Reduces computations
Popular in deep convolutional neural networks (deep learning)
18/02/2021 COMP9517 T1 2021
61
Sharpening Spatial Filters-Edge Detection
• Goal is to highlight fine details, or enhance details that have been blurred
• Spatial differentiation is the tool-strength of response of derivative operator is proportional to degree of discontinuity of the image at the point where operator is applied
• Image differentiation enhances edges, and de-emphasizes slowly varying gray-level values.
18/02/2021 COMP9517 T1 2021
62
Derivative definitions
•For 1-D function f(x), the first order derivative is approximated as:
•The second-order derivative is approximated as:
•These are partial derivatives, so that extension to 2D is easy.
18/02/2021 COMP9517 T1 2021 63 63
Chapter 3
Image Enhancement in the Spatial Domain
18/02/2021
COMP9517 T1 2021 64
64
Basic idea - Derivatives
• Horizontal scan of the image
• Edge modelled as a ramp- to represent blurring due to sampling
• First derivative is
– Non-zero along ramp
– zero in regions of constant intensity
– constant during an intensity transition
• Second derivative is
– Nonzero at onset and end of ramp
– Stronger response at isolated noise point
– zero everywhere except at onset and termination of intensity transition
• Thus, magnitude of first derivative can be used to detect the presence of an edge, and sign of second derivative to determine whether a pixel lies on dark or light side of an edge.
18/02/2021
COMP9517 T1 2021 65
Summary - Derivatives
• First-order derivatives produce thicker edges, have stronger
response to gray-level step
• Second-order derivatives produce stronger response to fine detail (thin lines, isolated points), produce double response at step changes in gray level
18/02/2021 COMP9517 T1 2021
66
Gradient Operator First-order derivatives implemented using magnitude of the gradient
For function f(x, y), the gradient of f at (x, y) is G with x and y components Gx The magnitude of the gradient vector is
G[f(x,y)]= G2 G2 xy
Thisiscommonlyapproximatedby: G[f(x,y)]=|Gx | +|Gy | Gx and Gy are linear and may be obtained by using masks
, Gy
We use numerical techniques to compute these- give rise to different masks, e.g. Roberts’ 2x2 cross-gradient operators, Sobel’s 3x3 masks
18/02/2021 COMP9517 T1 2021
67
Chapter 3
Image Enhancement in the Spatial Domain
18/02/2021
COMP9517 T1 2021 68
The Laplacian Second order derivatives based on the Laplacian.
For a function f (x, y), the Laplacian is defined by
D2 f ¶2 f ¶2 f
¶x2 ¶y2 This is a linear operator, as all derivative operators are.
In discrete form:
and similarly in y direction. Summing them gives us
18/02/2021
¶2 f f(x1,y) f(x1,y)2f(x,y) ¶x2
COMP9517 T1 2021
69
Chapter 3
Image Enhancement in the Spatial Domain
18/02/2021
COMP9517 T1 2021 70
18/02/2021
Laplacian ctd
• There are other forms of the Laplacian- can include diagonal directions, for example
• Laplacian highlights grey-level discontinuities and produces dark featureless backgrounds
• The background can be recovered by adding or subtracting the Laplacian image to the original image
COMP9517 T1 2021 71
Chapter 3
Image Enhancement in the Spatial Domain
72
18/02/2021 COMP9517 T1 2021
Chapter 3
Image Enhancement in the Spatial Domain
18/02/2021 COMP9517 T1 2021
73
Chapter 3
Image Enhancement in the Spatial Domain
18/02/2021 COMP9517 T1 2021
74
Chapter 3
Image Enhancement in the Spatial Domain
18/02/2021 COMP9517 T1 2021
75
• •
Padding
When we use spatial filters for pixels on the boundary of an image, we do not have enough neighbours
To get an image with the same size as input image o Zero: set all pixels outside the source image to 0
o Constant: set all pixels outside the source image to a specified border value o Clamp: repeat edge pixels indefinitely
o Wrap: copy pixels from opposite side of the image
o Mirror: reflect pixels across the image edge
18/02/2021
COMP9517 T1 2021 76
Padding Example
18/02/2021
Szeliski, “Computer Vision”, Chapter 3
COMP9517 T1 2021
77
• • •
References and acknowledgements Chapter 3 of Gonzalez and Woods 2002
Sections 3.1-3.3 of Szeliski
Some images drawn from above resources
18/02/2021 COMP9517 T1 2021
78