Transcript n - Department of Information and Computing Sciences

RANSAC experimentation
Slides by Marc van Kreveld
1
Experimental research
• Research in computer science may result in:
– definitions of new, useful structures or concepts
– new algorithms to solve problems
• Further knowledge on the new structure, concept or
algorithm can be obtained by:
– proofs of properties, complexities, efficiency of structures,
concepts or algorithms
– experiments to answer research questions where proofs
cannot be given, e.g. running times on real-World data;
user studies to determine aesthetics or perceived difficulty
2
3
Common sense tips in experiments
• Know exactly what you are doing and why
• Make sure to fix some specific research questions
at the start
• Do not even think about trying to answer more
questions, or hoping to get more information,
during the design phase. Concentrate on the
chosen questions only
• Design your data and your experiment to answer
the questions as well as reasonably possible
• Make sure your experiment can be replicated
4
Common sense tips in experiments
• Is your data sufficient in quality and size?
• Are there enough experiments?
• Are there enough different experiments to establish
relationships?
• Should I report all outcomes, a summary (histogram,
mean, standard deviation, …)?
• How strong can I / how weak must I phrase my
observations and conclusions?
5
Visualization of results
•
•
•
•
•
•
Table with numbers
Scatterplot
Graph
Chart
Pie diagram
Bar chart
6
Visualization of results
7
Visualization of results
8
Visualization of results
9
Visualization of results
10
Visualization of results
11
Visualization of results
12
Visualization of results
13
14
RANSAC
Goal: Given a set of points P, some of which lie on a line L*.
Find line L*
1. Choose a threshold distance d
2. For #iterations do
–
–
–
Choose 2 points, make line L
For each point q in P, test if q lies within distance d from L
If yes, increase the support of L by 1
If L has higher support than the highest-support line
found so far, remember L and its support
3. Return L as the line with most points near it
15
RANSAC
• For testing whether a point q supports a line L, we do
not actually compute the distance from q to L
• Instead, we generate two lines at distance d from L
• Then we test for each point whether it lies below the
upper and above the lower line
16
RANSAC
• How large should the threshold distance d be?
• How many iterations should we do to have a high
probability of finding the line with highest support?
 the threshold distance is related to the measurement error
(~5 cm) and the flatness of the surface
 the number of iterations depends on the inlier-outlier ratio
and with how much probability we want to find the best line
17
RANSAC, iterations
• Suppose we want to have 95% probability, p=0.95,
of finding the line
• Suppose there are k points on the line (inliers) and
n points in total
• Then the probability of choosing 2 points on the
line is (k/n)2
• The probability of never selecting 2 points on the
line in r iterations is ( 1 – (k/n)2 )r
• The probability of finding the line in r iterations is
1 – ( 1 – (k/n)2 )r
18
RANSAC, iterations
• So we want 1 – ( 1 – (k/n)2 )r > p
( 1 – (k/n)2 )r
<
log ( 1 – (k/n)2 )r <
r log ( 1 – (k/n)2 ) <
1–p
log (1 – p)
log (1 – p)
r > log (1 – p) / log ( 1 – (k/n)2 )
19
RANSAC, iterations
• Examples:
– if 10% of the points lie on the line and we want to find it
with 95% certainty, we need nearly 300 iterations
– If 5% of the points lie on the line and we want to find it
with 95% certainty, we need nearly 1200 iterations
– if 10% of the points lie on the line and we want to find it
with 90% certainty, we need nearly 230 iterations
20
Practical 3: RANSAC with Noise
21
Practical 3: RANSAC with Noise
• 1. Does the number of
iterations required to
find the best plane
increase when noise is
present, and how does
it increase in the
amount of noise?
22
Practical 3: RANSAC with Noise
• 1. Does the number of
iterations required to
find the best plane
increase when noise is
present, and how does
it increase in the
amount of noise?
• 2. When noise is
present, does the facet
shape influence the
number of iterations
that is needed, and in
what way?
23
Experimental research
• http://en.wikipedia.org/wiki/Design_of_experiments
• http://en.wikipedia.org/wiki/Charts
24