RANSAC Slide 1/11 RANSAC Slide 2/11

Finding Straight Lines from Edges

RANSAC: Random Sample and Consensus

Feature Finding Using RANSAC Model-based feature detection: features based on some a priori
model
Robert B. Fisher Works even in much noise and clutter
School of Informatics Tunable failure rate
University of Edinburgh
Assume
• Shape of feature determined by T true data points
• Hypothesized feature is valid if V data points nearby

c
°2014, School of Informatics, University of Edinburgh c
°2014, School of Informatics, University of Edinburgh

RANSAC Slide 3/11 RANSAC Slide 4/11

RANSAC Pseudocode RANSAC Termination Limit

pall−f is probability of algorithm failing to detect a feature
for i = 1 : Trials p1 is probability of a data point belonging to a valid feature
pd is probability of a data point belonging to same feature
Select T data points randomly Algorithm fails if T rials consecutive failures
Estimate feature parameters pall−f = (pone−f )T rials
if number of nearby data points > V Success if all needed T random data items are valid
return success
pone−f = 1 − p1 (pd )T −1
end
Solving for expected number of trials:
end log(pall−f )
T rials =
return failure log(1 − p1 (pd )T −1 )

c
°2014, School of Informatics, University of Edinburgh c
°2014, School of Informatics, University of Edinburgh
RANSAC Slide 5/11 RANSAC Slide 6/11

RANSAC Line Detection

RANSAC on Edge Subset
Model: infinite line through 2 randomly chosen points (T = 2)
Valid point if 28 neighbouring edge points within 2.5 pixels of line Zeroed complex middle to simplify example
Accept line if at least 130 valid points 96 lines 108 lines
pall−f = 0.001, p1 = 0.1, pd = 0.01, T rials = 688 0
overlay of left image lines − from RANSAC
0
overlay of right image lines − from RANSAC

203 lines 216 lines 500 500

1000 1000

1500 1500

2000 2000

0 500 1000 1500 2000 2500 3000 0 500 1000 1500 2000 2500 3000

Mostly accurate lines, but don’t know endpoints

c
°2014, School of Informatics, University of Edinburgh c
°2014, School of Informatics, University of Edinburgh

RANSAC Slide 7/11 RANSAC Slide 8/11

Zoom on Wedge Edges Finding actual line segments

Some random data points on line since crosses whole image
Want to find approximate observed start and end of true segment
1. Project points {~xi } onto ideal line thru point p~ with direction
~a: λi = (~xi − p~) · ~a. Projected point is p~ + λi~a

x a

p λ

2. Remove points not having 0.9τ neighbor points within τ = 130

pixels distance along line
All wedge lines, but lots of duplicate and unrelated lines 3. Endpoints are given by smallest and largest remaining λi .

c
°2014, School of Informatics, University of Edinburgh c
°2014, School of Informatics, University of Edinburgh
RANSAC Slide 9/11 RANSAC Slide 10/11

Found Raw Wedge Lines + Midpoints

Edge Points Used
left image edges found by RANSAC

2000 2000

1500 1500

1000 1000

500 500

0 0
0 500 1000 1500 2000 2500 3000 0 500 1000 1500 2000 2500 3000

All lines present but some midpoints not well placed due to
coincidental alignments

c
°2014, School of Informatics, University of Edinburgh c
°2014, School of Informatics, University of Edinburgh

RANSAC Slide 11/11

What We Have Learned

• A general robust and tunable parametric shape detection
algorithm
• Lots of edges means lots of lines
• Does find desired lines but may extend beyond if coincidental
alignments

c
°2014, School of Informatics, University of Edinburgh