[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
Edge detection and matching
Reading: (Szeliski 3.3.2-4)
Hyung Jin Chang
Lecture 1 – 3 14/02/2021
In this session
• Edge detection and matching
– process the image gradient to find
curves/contours
– comparing contours
Edge detection
• Goal: map image from 2d array of pixels to a set of
curves or line segments or contours. • Why?
Figure from J. Shotton et al., PAMI 2007
Figure from D. Lowe
• Main idea: look for strong gradients, post-process Slide credit: Kristen Grauman
Gradients -> edges
Three primary edge detection steps:
1. Smoothing: suppress noise
2. Edge enhancement: increase contrast (by differentiating) 3. Edge localization
– Determine which local maxima from filter output are actual edges vs. noise
• Threshold, Thin
Slide credit: Kristen Grauman
Thresholding
• Chooseathresholdvaluet
• Setanypixelslessthanttozero(off)
• Setanypixelsgreaterthanorequaltottoone (on)
Slide credit: Kristen Grauman
Slide credit: Kristen Grauman
Original image
Gradient magnitude image
Thresholding gradient with a lower threshold
Slide credit: Kristen Grauman
Thresholding gradient with a higher threshold
Slide credit: Kristen Grauman
Hysteresis Thresholding
Hysteresis Thresholding
Designing an Edge Detector
16
Canny Edge Detector
• Most popular edge detector in computer vision
• Theoretical model:
Step edges with added Gaussian noise.
• Canny showed that first derivative of a Gaussian well approximates the operator that optimizes a trade-off between signal-to-noise ratio and localization
MATLAB:
>> edge (image, ‘canny’);
>> help edge
J. Canny, A Computational Approach To Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence, 8:679-714, 1986. Cited 36493! (10/02/2021)
• • •
•
Canny edge detector
Filter image with derivative of Gaussian Calculate the gradient magnitude and orientation Non-maximum suppression:
– Thinwide“ridges”downtoonepixelwidth Linking and thresholding (hysteresis):
– Definetwothresholds:lowandhigh
– Applyahighthresholdonthemagnitudeto initialize a contours and continue tracing the contour until the magnitude falls below a low threshold
The Canny edge detector
original image (Lena)
Slide credit: Steve Seitz
The Canny edge detector
gradient magnitude
Slide credit: Kristen Grauman
Compute Gradients
X-Derivative of Gaussian Y-Derivative of Gaussian Gradient Magnitude
Slide credit: Svetlana Lazebnik
The Canny edge detector
gradient magnitude
Slide credit: Kristen Grauman
The Canny edge detector
Get Orientation at Each Pixel
Slide credit: Kristen Grauman
The Canny edge detector
Thresholding: Set magnitudes lower than a prescribed threshold to 0.
Slide credit: Kristen Grauman
The Canny edge detector
How to turn these thick regions of the gradient into thinner curves?
thresholding
Slide credit: Kristen Grauman
Non-maximum suppression
• Check if pixel is local maximum along gradient direction
• Select single max across width of the edge
• Requires checking interpolated pixels p and r
Slide credit: Kristen Grauman
Non-maximum suppression
Before Non-maximum Suppression
After Non-maximum Suppression
Slide credit: Kristen Grauman
The Canny edge detector
thinning (non-maximum suppression)
Problem: pixels along this edge didn’t survive the thresholding
Hysteresis Thresholding
Hysteresis Thresholding
• Trace each contour separately (e.g., using 4-connectedness).
• Apply two thresholds Thigh and Tlow – Start tracing a line only at pixels that
pass the Thigh threshold.
– Continue tracking if the pixels pass Tlow threshold.
• Typical threshold ratio: Thigh / Tlow = 2
Hysteresis Thresholding
:
Hysteresis thresholding
original image
high threshold low threshold hysteresis threshold
(strong edges) (weak edges) 34
Slide credit: Fei-Fei Li
• • •
•
Canny edge detector
Filter image with derivative of Gaussian Calculate the gradient magnitude and orientation Non-maximum suppression:
– Thinwide“ridges”downtoonepixelwidth Linking and thresholding (hysteresis):
– Definetwothresholds:lowandhigh
– Applyahighthresholdonthemagnitudeto initialize a contours and continue tracing the contour until the magnitude falls below a low threshold
35
Slide credit: David Lowe, Fei-Fei Li
Canny Characteristics
• The Canny operator gives single-pixel-wide images with good continuation between adjacent pixels
• It is the most widely used edge operator today. Many implementations are available.
• It is very sensitive to its parameters, which need to be adjusted for different application domains.
36
Canny edge detector in Action Input image gradient magnitude gradient angle
thinned Thresholded
Canny edge detector in Action
Input image gradient magnitude gradient angle
thinned thresholded
Beyond Canny edge detector
• Recently lots of new approaches for edge detection by machine learning.
• Essentially, look at patches and learn what an edge is by inferring the structure from intensities.
Sketch Tokens, CVPR 2013. Joseph Lim, C. Zitnick, and P. Dollár
Beyond Canny edge detector
• Real-time edge detection by machine learning using random forests [1].
• Recent state of the art: – Pb
– Edge Tokens
– Regression-based
For those interested in [1]: Source code and papers: link
[1] Dollar, P. and Zitnick, L., Fast Edge Detection Using Structured Forests, arXiv:1406.5549v1 [cs.CV] 20 Jun 2014
Beyond Canny edge detector
Document Scanner – Structured Forests for Fast Edge Detection + Hough Transform
Low-level edges vs. perceived contours
Background Texture
Slide credit: Kristen Grauman
42
Shadows
Low-level edges vs. perceived contours
image human segmentation gradient magnitude
• Berkeley segmentation database:
http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/
43
Slide credit: Svetlana Lazebnik
Learn from humans which combination of features is most indicative of a “good” contour?
[D. Martin et al. PAMI 2004]
Slide credit: Kristen Grauman
Human-marked segment boundaries
44
Holistically-Nested Edge Detection (Xie, Tu ICCV 2015)
1. holisticimage training and
prediction
2. multi-scale and multi-level feature learning
3. Deeply-supervised fully-convolutional network
45
State-of-the-Art in Contour Detection HED
46
State-of-the-Art in Contour Detection
Zhiding Yu et al. “CASENet: Deep Category-Aware Semantic Edge Detection” CVPR 2017
State-of-the-Art in Contour Detection
Zhiding Yu et al. “CASENet: Deep Category-Aware Semantic Edge Detection” CVPR 2017
In this session
• Edge detection and matching
– process the image gradient to find
curves/contours
– comparing contours
Figure from Belongie et al.
50
Chamfer distance
Chamfer distance • Average distance to nearest feature/edge
I= T=
dI (t) = Minimum distance between point t and some point in I
Set of edge points in image
Set of edge points on (shifted) template
52
Chamfer distance • Average distance to nearest feature
Slide credit: Kristen Grauman
Edge image
How is the measure different than just filtering with a mask having the shape points?
How expensive is a naïve implementation?
54
Distance transform
Image features (2D)
Distance Transform
1
0
1
2
3
4
3
2
1
0
1
2
3
3
2
1
1
0
1
2
3
2
1
0
1
0
0
1
2
1
0
1
2
1
1
2
1
0
1
2
3
2
2
2
1
0
1
2
4
3
3
2
1
0
1
2
5
4
4
3
2
1
0
1
Distance Transform is a function D(×) that for each image pixel p assigns a non-negative number D(p) corresponding to distance from p to the nearest feature in the image I
Slide credit: Yuri Boykov
55
original
Distance transform
edges
distance transform
Value at (x,y) tells how far that position is from the nearest edge point (or other binary image structure)
>> help bwdist
56
Slide credit: Kristen Grauman
Chamfer distance • Average distance to nearest feature
Slide credit: Kristen Grauman
Edge image Distance transform image 59
Chamfer distance
Edge image Distance transform image 60
Fig from D. Gavrila, DAGM 1999
Chamfer Distance based hand detection
Chamfer distance: properties
• Sensitivetoscaleandrotation
• Tolerantofsmallshapechanges,clutter • Needlargenumberoftemplateshapes • Inexpensivewaytomatchshapes
64
Slide credit: Kristen Grauman
Thank you
Hyung Jin Chang
14/02/2021