T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Robot Learning
5. RANSAC
Jeong-Yean Yang
2020/10/22
1
T&C LAB-AI
Nonlinear Regression with
Optimization Method
5
2
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Modeling with Least Square Eq.
• Find the proper Circle for the given points.
• Cost Function
3
2
2
2
:
Model x
y
r
2
( ,
)
i
i
i
X
x y
R
0
0
2
2
2
2
0
0
( ,
, )
(
)
(
)
N
i
i
i
J
J x y r
x
x
y
y
r
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Minimizing Error
with Gradient Descent method
• Gradient of J
• Gradient Descent Method
4
0
0
1
( ,
, )
k
k
P
x y r
P
P
J
0
0
2
2
2
2
0
0
( ,
, )
(
)
(
)
N
i
i
i
J
J x y r
x
x
y
y
r
0
0
0
0
0
0
( ,
, )
ˆ
ˆ
ˆ
J
J x y r
J
J
J
x
y
r
x
y
r
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
5
2
2
2
0
0
0
0
2
2
2
0
0
0
0
2
2
2
0
0
ˆ
2
(
)
(
)
2(
)
ˆ
2
(
)
(
)
2(
)
ˆ
2
(
)
(
)
2
N
i
i
i
i
N
i
i
i
i
N
i
i
i
J
x
x
y
y
r
x
x
x
x
x
y
y
r
y
y
y
x
x
y
y
r
r
r
0
0
1
2
2
2
0
1
0
0
0
0
2
2
2
0
1
0
0
0
0
2
2
2
1
0
0
( ,
, )
|
|
2
(
)
(
)
2(
)
|
|
2
(
)
(
)
2(
)
|
|
2
(
)
(
)
2
k
k
N
k
k
i
i
i
i
N
k
k
i
i
i
i
N
k
k
i
i
i
P
x y r
P
P
J
x
x
x
x
y
y
r
x
x
y
y
x
x
y
y
r
y
y
r
r
x
x
y
y
r
r
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Example of GDM-based Regression
• randn : Normal distribution= x~N(0,1)
• Our distribution with
– In Matlab code: circle1.m
6
x' ~
( , )
N
' ~
( , )
x
N
randn
-25
-20
-15
-10
-5
0
5
10
15
20
25
-25
-20
-15
-10
-5
0
5
10
15
20
25
Ex) Radius=20
Sigma =2
rm
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Example of GDM-based Regression
• GDM for finding x0,y0,r
• (circle2.m)
7
-30
-20
-10
0
10
20
30
-25
-20
-15
-10
-5
0
5
10
15
20
25
0
0
1
2
2
2
0
1
0
0
0
0
2
2
2
0
1
0
0
0
0
2
2
2
1
0
0
( ,
, )
|
|
2
(
)
(
)
2(
)
|
|
2
(
)
(
)
2(
)
|
|
2
(
)
(
)
2
k
k
N
k
k
i
i
i
i
N
k
k
i
i
i
i
N
k
k
i
i
i
P
x y r
P
P
J
x
x
x
x
y
y
r
x
x
y
y
x
x
y
y
r
y
y
r
r
x
x
y
y
r
r
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
l5regcircle
8
ex/ml/l5regcircle
l5regcircle.test(0,0,1)
Experiment:
Let’s try many initial guesses.
Test(0,0,1) test(20,20,50) , etc.
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Various Initial Guess
9
Large error of initial guess makes bad effects?
Try test(0,0,100) or test(100,0,1)
T&C LAB-AI
Stochastic Regression (RANSAC)
6
10
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Regression has the Problem like this
• Regression is Model-based method
• The given DATA is NOT a circle
• Thus, our model is wrong for data
– However, the data is a kind of Circles…
11
Circle
Model
Circle
2
2
2
2
|| (
)
(
)
||
N
i
i
i
J
x
a
y
b
r
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Generate Non Circle Data
• Circle3.m generate two overlapped circles
12
-30
-20
-10
0
10
20
30
40
-25
-20
-15
-10
-5
0
5
10
15
20
25
Find this circle
Remove
small
circle
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
RANSAC
• RANSAC
– Random Sample Consensus
– Pick Good sample from data and Throw away bad sample.
• Training set, T is given
• Pseudo code of RANSAC
– 1. Take a random Sample, S of size m from T.
– 2. Build a model, J with S
– 3. Compute error, e of J with all data T
– 4. if |e|< threshold, add S or small residuals into consensus
set, CS
– 5. repeat to 1 until CS is larger than some value.
13
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Pseudo Code of RANSAC 1
14
T
Pseudo code of RANSAC
1. Take a random Sample, S of size m from T.
2. Build a model, J with S
3. Compute error, e of J with all data T
4. if |e|< threshold, add S or small residuals into
consensus set, CS
5. repeat to 1 until CS is larger than some value.
1,2
S
3
Samples having small
residuals
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Pseudo Code of RANSAC 2
15
T
Pseudo code of RANSAC
1. Take a random Sample, S of size m from T.
2. Build a model, J with S
3. Compute error, e of J with all data T
4. if |e|< threshold, add S or small residuals into
consensus set, CS
5. repeat to 1 until CS is larger than some value.
1,2
S
3
Samples having small
residuals
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Pseudo Code of RANSAC 3
16
T
Pseudo code of RANSAC
1. Take a random Sample, S of size m from T.
2. Build a model, J with S
3. Compute error, e of J with all data T
4. if |e|< threshold, add S or small residuals into
consensus set, CS
5. repeat to 1 until CS is larger than some value.
1,2
S
3
Samples having small
residuals
It does NOT satisfy
|e|< threshold, then no
residual is NOT added into
CS
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Circle3 and Circle4.m
• Circle3: generate Overlapped circle
• Circle4: Simple RANSAC
17
-30
-20
-10
0
10
20
30
40
-30
-20
-10
0
10
20
30
-30
-20
-10
0
10
20
30
40
-30
-20
-10
0
10
20
30
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Test4.m
18
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
RANSAC:
Why it is so useful?
• l5regransac.py DOES NOT use RANSAC
19
Test(0,0,1)
Test(0,0,10)
GOOD
It is lucky!
BAD
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
See Iteration Error Graph
• Is it GOOD? Remind Convex Hulls.
20
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Test with Various Initial guess
What kinds of Problems occur?
• 1. Too sensitive to Initial guess.
– Regression method cannot satisfy circle + noise
simultaneously.
– Thus, It becomes UNSTABLE
• 2. In other words, Convex hulls are not so strong
– l2regcircle shows good stability
– However, l2regransac shows poor performance
– Convex hull in this example was so sharp
– Think differentiation leads to the optimal value
21
Solvable
Probably
Not
Solvable.
Diff
becomes
infinity
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Comparison with RANSAC
22
Without RANSAC
l5regransac.test(0,0,1)
With RANSAC
l5regransac2.test()
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
l5regransac2.py
• edit ex/ml/l5regransac2
• l5regransac2.test()
23
Load 2d point data
Get CS by RANSAC
l5regransac2.data
[-9.76,16.2], [-6.88,-19.6],….
cs =findcs()
cs is the INDEX of data
cs=[ 51,28,2,20,53,…]
Therefore,
Good sample is
data[cs[0]]
data[cs[1]]
data[cs[2]]
…
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
findcs : find good sample set= CS
24
Do sampling 1000 times
Number of sampling,
m=20
Larger m
or
Smaller m
?
1. Data number is 544
2. Sample number is m
3. Chose randint(544)
0, 1, 100, 200, 45, or 543
4. sample=[ 120, 3, …]
5. reg() is a regression
Function with sample.
Reg() tries to find a good
solution
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
HW. RANSAC Performance
• findcs() runs N=1000 times sampling with m=20
• HW. 1 :
– If we increase or decrease N, what happens?
– Explain why it occurs
• HW. 2:
– If we increase m=20, what happens?
– Explain why it occurs
• HW. 3: reg() function has stop condition,
–
if we increase error threshold, 4e6 ,
–
what happens?
25
