CV 3. Fitting

Computer Vision [3]

1. Fitting (Modeling)

특정 Feature Extraction Methods로부터 추출된 Features는 우리가 원하는 특정 값과의 상관성을 찾는데 사용될 수 있다. Features를 사용하여 특정 값과의 상관성을 찾는 방법 중에는 가장 많이 사용되는 Least Square Method와 outlier에 강인한 RANSAC (Random SAmple Consensus)가 있다. 

2. Least Square Method

최소자승법이라고 불리는 Least Square Method는 y = ax +b와 같은 선형 관계를 찾는데 사용된다. y는 우리가 원하는 특정 값이며, x는 입력 Feature이다. a와 b를 찾는 것이 상관성을 찾아내서 모델화를 시키는 방법이다. 

1) Ordinary Linear Least Square

Least Square Method는 위의 식을 만족하는 a와 b를 찾는 방법이다. 즉, hypothesis (ax+b)가 실제 y와 얼마나 비슷한지를 L2 norm의 제곱으로 나타낸 것이다. (Square Error) 간단히 다음과 같은 행렬연산으로 (a,b)를 찾을 수 있다.

하지만, 이 방법은 문제가 있는데,

(1) Rotation에의해 a,b가 변화되며

(2) horizontal line과 vertical line을 표현할 수 없다.

이는, 우리가 ax+b와 실제 y사이의 차이를 계산할 때, ax+b에 수직인 거리를 계산한 것이 아니라 y 축 상의 거리를 계산하였기 때문에 발생하는 문제이다. (ax+b의 결과는 y`이라고 보고, 실제 값이 y라면 y-y`이 거리가 된다. 이는 실제 data (x,y)와 ax+b사이의 수직 거리가 아니다.)

2) Total Linear Least Square

(x,y)와 우리의 hypothesis 사이의 수직 거리를 계산하기 위해서 약간의 식의 변환이 필요하다. 어떤 특정 점(xi,yi)에서 평면 사이(ax+by+c=0)까지의 거리는 다음과 같이 계산된다.

(a,b)를 unit vector로 가정하면, 다음과 같이 나타낼 수 있다.

거리의 절대 값의 크기를 줄이는 것은 거리의 제곱 값의 키기를 줄이는 것과 같은 문제이므로, 

으로 나타낼 수 있으며, 이는 다음과 같은 최적화문제로 변경된다.

여기서, 우리는 가장 error를 최소화하는 a,b,c를 찾는 것이 문제이다.

위 식의 과정을 통해서 새로운 objective function을 구하면,

위의 식을 최소화하기 위해서는 b는 D의 가장 작은 eigenvalue에 해당하는 unit vector([0,...,1])여야하며, 이 경우 a는 X^TX의 가장 작은 eigenvalue에 해당하는 eigenvector가 된다. 

이를 이해하기 위해서는 b가 [0,...,1]인 unit vector일 때 가장 작은 eigenvalue가 ||Xa||^2이 되고, 이는 이 objective function의 minimum값이 된다는 것을 알아야한다.

3. RANSAC

하지만, Total Linear Least Square를 사용하더라도 outlier로 인한 모델의 contamination을 해결할 수 없다. Least Square Method는 전체 데이터에 해당하는 error의 제곱의 합을 고려하기 때문에, 몇몇 outlier들에 의한 큰 에러의 제곱에 민감하다. 따라서, outlier를 제거하는 방법이 필요하고 이 방법이 바로 RANSAC이다. (물론, model을 fitting하는 방법은 Least Square Method가 아니어도 된다.) 핵심 아이디어는 "여러번 sampling을 하면서 inlier가 많은 모델을 추정해나가는것"이다. (inlier가 많다면 그 모델은 나름 general한 모델이라는 것이다.)

RANSAC의 순서는 다음과 같다.

1. model의 fitting에 필요한 최소한의 point를 sampling한다. (line이라면 2개, circle이면 3개)

2. sampling된 point로 model을 fitting한다.

3. fitting된 모델 주위의 inlier의 개수를 계산하고, 이 개수가 특정 fixed된 t보다 많은 경우 이 모델을 채택한다. 그렇지 않은 경우 1-2 과정을 N번 반복한다. inlier는 model의 fitting 값과 실제 값 사이의 "거리"가 얼마나 작은지 큰지를 기준으로 결정하며 d로 표현한다.

RANSAC: Inliers and Outliers, 출처: Wikipedia, Random sample consensus, https://en.wikipedia.org/wiki/Random_sample_consensus

4. 최종적으로 가장 많은 inlier를 갖는 모델을 선택하고 inlier로 다시 모델을 fitting 한다.

RANSAC에서 N, t, d는 model의 designer가 설정해줘야하는 값이며, N같은 경우 outlier ratio를 고려한다면 다음과 같은 식으로 계산할 수 있다.

p는 noise-free parameter estimation의 확률이며, e는 outlier의 ratio다. 

밑의 그림은 outlier가 많은 상황에서, RANSAC으로 찾은 general model을 보여주고 있다.

• 

  A data set with many outliers for which a line has to be fitted.

 
• 

  Fitted line with RANSAC; outliers have no influence on the result.

• 출처: wikipedia, Random sample consensus, https://en.wikipedia.org/wiki/Random_sample_consensus

4. What is the next?

RANSAC은 분명 꽤 직관적인 아이디어로 시작한 fitting 알고리즘이다. 하지만, N, t, d와 같은 hyper-parameter를 튜닝해야하는 어려움이 있다. 딥러닝에서는 RANSAC보다는 다른 regularization methods를 사용하여 general한 모델을 찾고자 노력한다. Weight decay, Dropout 등이 그 사례이다. 

Least Square Method, RANSAC, Model Fitting