Bài giảng Nhập môn thị giác máy tính - Chapter 8: Fitting - Voting and hough transform - Lê Thanh Hải
Chapter 8 – Fitting
8-1
Chapter 8
Fitting: Voting and Hough Transform
Prof. Fei-Fei Li, Stanford Univers ity
Department of Mechatronics
Chapter 8 – Fitting
8-2
Contents
Line fitting
• Hough Transform
• RANSAC (RANdom SAmple Consensus)
Department of Mechatronics
Chapter 8 – Fitting
8-3
Fitting as Search in Parametric Space
• Choose a parametric model to represent a set
of features
• Membership criterion is not local
– Can’t tell whether a point belongs to a given model just
by looking at that point.
• Three main questions:
– What model represents this set of features best?
– Which of several model instances gets which feature?
– How many model instances are there?
• Computational complexity is important
– It is infeasible to examine every possible set of
parameters and every possible combination of features
Department of Mechatronics
Chapter 8 – Fitting
8-4
Example: Line Fitting
• Why fit lines? Many objects characterized by presence of
straight lines
• Wait, why aren’t we done just by running edge detection?
Department of Mechatronics
Chapter 8 – Fitting
8-5
Difficulty of Line Fitting
• Extra edge points
(clutter), multiple models:
– Which points go with
which line, if any?
• Only some parts of each
line detected, and some
parts are missing:
– How to find a line that
bridges missing evidence?
• Noise in measured edge
points, orientations:
– How to detect true underlying
parameters?
Department of Mechatronics
Chapter 8 – Fitting
8-6
Voting
• It’s not feasible to check all combinations of features by
fitting a model to each possible subset.
• Voting is a general technique where we let the features
vote for all models that are compatible with it.
– Cycle through features, cast votes for model parameters.
– Look for model parameters that receive a lot of votes.
• Noise & clutter features will cast votes too, but typically
their votes should be inconsistent with the majority of
“good” features.
• Ok if some features not observed, as model can span
multiple fragments.
Slide credit: Kristen
Grauman
Department of Mechatronics
Chapter 8 – Fitting
8-7
Fitting Lines
• Given points that belong to a line,
what is the line?
• How many lines are there?
• Which points belong to which lines?
• Hough Transform is a voting technique
that can be used to answer all of these
• Main idea:
1. Record all possible lines on which each
edge point lies.
2. Look for lines that get many votes.
Department of Mechatronics
Chapter 8 – Fitting
8-8
Finding Lines in an Image: Hough Space
y
b
b0
m0
x
m
Image space
Hough (parameter) space
• Connection between image (x,y) and Hough (m,b)
spaces
– A line in the image corresponds to a point in Hough space.
– To go from image space to Hough space:
• Given a set of points (x,y), find all (m,b) such that y = mx + b
Department of Mechatronics
Chapter 8 – Fitting
8-9
Finding Lines in an Image: Hough Space
y
b
y0
x0
x
m
Image space
Hough (parameter) space
• Connection between image (x,y) and Hough (m,b) spaces
– A line in the image corresponds to a point in Hough space.
– To go from image space to Hough space:
• Given a set of points (x,y), find all (m,b) such that y = mx + b
– What does a point (x0, y0) in the image space map to?
• Answer: the solutions of b = -x0m + y0
• This is a line in Hough space
Department of Mechatronics
Chapter 8 – Fitting
8-10
Finding Lines in an Image: Hough Space
y
b
(x1, y1)
y0
(x0, y0)
b = –x1m + y1
x0
Image space
x
m
Hough (parameter) space
• What are the line parameters for the line that contains both (x0,
y0) and (x1, y1)?
– It is the intersection of the lines b = –x0m + y0 and b = –x1m + y1
Department of Mechatronics
Chapter 8 – Fitting
8-11
Finding Lines in an Image: Hough Space
y
b
x
m
Image space
Hough (parameter) space
• How can we use this to find the most likely parameters
(m,b) for the most prominent line in the image space?
– Let each edge point in image space vote for a set of possible
parameters in Hough space
– Accumulate votes in discrete set of bins; parameters with the
most votes indicate line in image space.
Department of Mechatronics
Chapter 8 – Fitting
8-12
Polar Representation for Lines
• Issues with usual (m,b) parameter space:
– Can take on infinite values;
– Undefined for vertical lines.
x
[0,0]
: perpendicular distance
from line to origin
d
: angle the perpendicular
line makes with the x-axis
d
y
x cos y sin d
where 휃 ∈ [0, 휋) and d∈ R
• Point in image space sinusoid segment in Hough space
Department of Mechatronics
12
Chapter 8 – Fitting
8-13
Hough Transform Algorithm
Using the polar parameterization:
x cos y sin d
Basic Hough transform algorithm
1. Initialize H[d, ] = 0.
2. For each edge point (x,y) in the image for [0, )
H[d, ] += 1
3. Find the value(s) of (d, ) where H[d, ] is
maximum
d
4. The detected line in the image is given by
d x cos y sin
• Time complexity (in terms of number of
votes)?
Department of Mechatronics
Chapter 8 – Fitting
8-14
Example: HT for Straight Lines
d
y
x
Image space edge coordinates
Votes
Bright value = high vote count
Black = no votes
Department of Mechatronics
Chapter 8 – Fitting
8-15
Example: HT for Straight Lines
Square:
Department of Mechatronics
Chapter 8 – Fitting
8-16
Example: HT for Straight Lines
Department of Mechatronics
Chapter 8 – Fitting
8-17
Real-World Examples
Department of Mechatronics
Chapter 8 – Fitting
8-18
Showing longest segments found
Department of Mechatronics
Chapter 8 – Fitting
8-19
Impact of Noise on Hough Transform
d
y
x
Image space
edge coordinates
Votes
What difficulty does this present for an implementation?
Department of Mechatronics
Chapter 8 – Fitting
8-20
Impact of Noise on Hough Transform
Image space
edge coordinates
Votes
Here, everything appears to be “noise”, or random edge points,
but we still see peaks in the vote space.
Department of Mechatronics
Tải về để xem bản đầy đủ
61 trang
25860
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nhập môn thị giác máy tính - Chapter 8: Fitting - Voting and hough transform - Lê Thanh Hải", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_nhap_mon_thi_giac_may_tinh_chapter_8_fitting_votin.pdf
