Chapter 8 Image Segmentation
Image Segmentation
• Image segmentation is the process of dividing an image into constituent meaningful regions.
• Challenge
– Image quality
– Noise
– Need to integrate with high-level information
• Typically done based on:
– Intensity discontinuity, Intensity similarity, morphology
2
8.1 Edge Detection
3
1st Derivative
• The formula for the 1st derivative of a function is as follows:
• =
• For discrete-time signals, it is the difference between subsequent values:
–Backward1stDerivative: = −(−1) –Forward1stDerivative: = +1 −() –Center1stDerivative: = +1 −(−1)
4
2nd Derivative
• The 2nd derivative of a discrete-time signal can be defined as:
5
Edge Detection
• A place in the image where intensities are changing rapidly.
• Edge models
6
Using 1st and 2nd Derivatives for Edge Detection
7
Using 1st and 2nd Derivatives for Edge Detection
• Observations:
– First-order derivatives produce thicker edge
– Second-order derivatives have a stronger response to fine detail (e.g., thin line, isolated point, noise)
– Second-order derivatives produce a double- edge response at ramp and step transitions
– The sign of the second derivatives can be used to determine whether we have a light to dark OR dark to light transition
8
Edge Detection
• Edge can be localized precisely by the zero crossing of the 2nd derivative.
9
1st and 2nd Derivative under noise
1st order derivative is not useful for detecting edge at this noise level
2nd order derivative becomes useless even at lower noise level
10
Gradient
Alternatively, edge strength can be characterized by:
= +
11
Gradient Operators
• Prewitt and Sobel operators integrate smoothing and edge detection.
12
Gradient Operators: Diagonal Edges
13
Gradient Operators
14
Gradient Operators
15
Gradient Operators
16
Gradient Operation Followed by Thresholding
all (x,y)
17
Gradient Operation Followed by Thresholding
Thresholded Sobel gradient amplitudes at 33% of max value
• Some edges (arrow) are broken
• principal edges are highlighted more
• edges are more connected
18
Laplacian Operator
• A good place to look for edges is the maxima of the first derivative or the zeros of the second derivative.
• The 2D extension approximates the second derivative by the Laplacian operator:
∇ = +
19
Laplacian-based Edge Detection
Choose only zero-crossing point with high enough variance.
20
Laplacian-based Edge Detection
21
•
Marr and Hildreth [1980] argued that an operator should be capable of being tuned to detect edges of different scales.
LoG Filter
22
LoG Filter
(i.e., Circle centred at origin
with radius 2
23
LoG Filter
• Fundamental ideas
– The Gaussian blurs the image. It reduces the intensity of structures at scales much smaller than σ.
– The Laplacian is isotropic and no other directional mask is needed.
• Workflow:
1. Filter input image with a Gaussian
Laplacian filter
filter with standard deviation . 2. Compute the Laplacian of the
0 1 0 1 -4 1 0 1 0
Gaussian filtered image.
3. Find the zero crossing of the image obtained in Step 2.
24
Finding Zero Crossing
xxx xxx xxx
• The corresponding cross in the above 3×3 neighbourhood has opposite signs.
• The difference between them is larger than a threshold. Thresholding removes weak edges.
25
LoG Filter
26
Effect of in LoG Filter
27
Canny Edge Detector
• Criteria for an “optimal” edge detector [Canny 1986]:
– Good detection: the optimal detector must minimize the probability of false positives (detecting spurious edges caused by noise), as well as that of false negatives (missing real edges).
– Good localization: the edges detected must be as close as possible to the true edges
– Single response: the detector must return one point only for each true edge point; that is, minimize the number of local maxima around the true edge.
28
Workflow
1. Filter image with derivative of Gaussian.
2. Find magnitude and orientation of gradient.
3. Non-maximum suppression:
• Thin multi-pixel wide “ridges” down to single pixel width.
4. Linking and thresholding (hysteresis):
– Define two thresholds: low and high
– Use the high threshold to start edge curves and the low threshold to continue them.
29
Workflow
30
Non-maximal suppression
• Ateverypoint(x,y)
xxx xxx xxx
• Denotethedirectionsofthefourdiagonalsby , , , .
• Let the output of this step (,)
– Find the direction that is closest to (, ).
– If the value of (, ) is less than at least one of its neighboursalong , , =0
– Otherwise, , is left untouched.
31
Hysteresis Thresholding
32
Hysteresis Thresholding
33
Canny Edge Detector
Non-maximum suppression and hysteresis thresholding
34
Canny, LoG and Thresholded Gradient
35
Canny, LoG and Thresholded Gradient
36
Edge Linking
• In practice, the detected pixels do not completely characterize edges completely due to occlusions, non-uniform illumination and noise.
• Edge linking is needed.
37
Edge Linking
38
Edge Linking
4. Scan along vertical and diagonal directions using the same scanning strategy.
39
Edge Linking
40