RANSAC(RANdom SAmple Consensus)는 이름에서 알 수 있듯이 랜덤으로 정한 샘플에서 Consensus, 즉 샘플에서 얻은 모델이 데이터에 얼마나 일치하는지를 판단하는 방법입니다. 최소자승법(Least Square Method)과 다른점은 outlier를 제외한 inlier를 고려해 모델을 선택한다는 것입니다. 이 포스트에서는 가장 간단한 예제인 직선을 예로 들겠습니다.
Algorithm
RANSAC알고리즘을 이용해 직선을 추정하는 문제를 예로 들면 간단하게 순서로 나타내면 다음과 같이 생각할 수 있습니다.
- parameter : threshold, N
- N 번 반복
- data에서 random하게 sample을 2개 정합니다.
- 정한 sample에서 직선을 구합니다.
- 구한 직선과 data의 residual을 구합니다.
- threshold보다 residual이 작으면 inlier
- 가장 많은 inlier를 포함하고 있는 직선을 반환합니다.
여기서 가장 많은 inlier를 포함하고 있다는 것은 consensus가 가장 높다고 이야기 할 수 있습니다.
Residual?
Residual이란 표본집단에서 얻은 회귀식과 실제 관측값과의 차이를 말합니다. 잔차라고도 하며 이 예제에서는 sample로 부터 얻은 직선과 데이터와의 차이를 이야기합니다.
Inlier, Outlier?
먼저 Outlier는 통계학에서 쓰이는 용어로 특이치라는 뜻을 가집니다.
RANSAC 알고리즘에서 Inlier와 Outlier는 데이터와 모델의 Residual이 미리 정한 threshold에 보다 작은가? 로 판단됩니다.
이 예제에서는 residual이 thrheshold보다 작은 데이터를 inlier라고 가정합니다.
Example
다음은 노이즈가 끼어있는 데이터에서 직선을 추정하는 위키피디아의 Matlab코드로 구현되어있는 RANSAC예제를 python으로 구현한 것입니다.
import matplotlib.pyplot as plt
import numpy as np
import random
import numpy.matlib
from math import sqrt
def norm(A):
return sqrt(A[0]**2+A[1]**2)
# Residual을 계산하기위한 행렬의 repeatcopy
def repeatCopy(arg,size):
t1 = [arg[0]]*size
t2 = [arg[1]]*size
result = [t1,t2]
return np.array(result)
# return index
def findin(arg,threshold):
result = []
for i in range(len(arg)):
if abs(arg[i]) <= threshold:
result.append(i)
return result
def ransac_demo(data,thrheshold_dist,inlier_ratio,num,loop_const):
bestInNum = 0
while bestInNum == 0:
bestParameter1,bestParameter2 = 0.0,0.0
bestInlier_list = []
for i in range(len(data)*loop_const):
# 랜덤으로 점을 2개 선택합니다.
idx = random.sample(range(num),2)
sample = [[data[0][idx[0]],data[1][idx[0]]],[data[0][idx[1]],data[1][idx[1]]]]
# 선택한 2개의 점으로 직선을 구합니다.
kLine = np.subtract(sample[0],sample[1])
klineNorm = kLine / norm(kLine)
normVector = np.array([-klineNorm[1],klineNorm[0]])
# sample과 data의 residual을 구합니다.
sub_mat = np.subtract(data,repeatCopy(sample[0],num))
distance = np.dot(normVector,sub_mat)
# distance is 1-D vector
# residual의 inlier threshold로 inlier 판단
inlier_idx = findin(distance,thrheshold_dist)
inlier_num = len(inlier_idx)
# inlier의 최대값일 경우 값을 저장합니다.
if inlier_num >= inlier_ratio * num and inlier_num > bestInNum:
tmp_list = [[],[]]
for j in inlier_idx:
tmp_list[0].append(data[0][j])
tmp_list[1].append(data[1][j])
bestInlier_list = tmp_list.copy()
bestInNum = inlier_num
# 이예제의 경우 parameter는 직선을 이루는 2개의 상수입니다.
p1 = (sample[1][1] - sample[0][1])/(sample[1][0] - sample[0][0])
p2 = sample[0][1] - p1*sample[0][0]
bestParameter1,bestParameter2 = p1,p2
return bestParameter1,bestParameter2,bestInlier_list
def sample_line(x):
return x + 3
if __name__ == "__main__":
sample_n = 100
noise_ratio = 2
sample_data = [[],[]]
for i in range(sample_n):
if i % 2 == 0:
sample_data[0].append(random.random()*sample_n)
sample_data[1].append(random.random()*sample_n)
else:
sample_data[0].append(i+float(random.sample([-1,1],1)[0])*random.random()*noise_ratio)
sample_data[1].append(sample_line(i+float(random.sample([-1,1],1)[0])*random.random()*noise_ratio) + float(random.sample([-1,1],1)[0])*random.random()*noise_ratio)
p1,p2,inlier = ransac_demo(sample_data,1,0.1,sample_n,1)
ransac_result_x = np.array(list(range(0,100,1)))
true_result_y = sample_line(ransac_result_x)
ransac_result_y = np.multiply(ransac_result_x,p1) + p2
# plt.scatter(inlier[0],inlier[1],c='red',s=5,label='inlier')
plt.scatter(sample_data[0],sample_data[1],s=5,label='data')
plt.plot(ransac_result_x,ransac_result_y,label='estimation line loop const')
plt.plot(ransac_result_x,true_result_y,c='green',label='truth line',linewidth=3)
plt.legend()
plt.grid()
plt.show()
pass
결과
위 예제를 실행하면 그림과 같은 결과를 얻을 수 있습니다. 그림에서 보여지는 것과 같이 노이즈를 포함하고 있는 데이터에서도 어느정도 잘 동작함을 확인할 수 있습니다.
