Fitting

 

* 이 포스트는 컴퓨터 비젼에 대한 개인 학습용으로 작성한 포스트입니다.

 

 

Least Squares Line Fitting

Data가 n개 있을 때, line을 fitting하는 방법으로 least square method를 사용한다. y 값에 대해 square error를 사용하여 fitting한다. 아래식에 대한 cost function을 사용한다.

최종적으로, 아래식 (dagger matrix)를 통해 b를 구할 수 있다.

 

 

Total Least Squares

위의 방법으로는, line이 수직선에 가까울수록, error가 점점 커진다. 즉, 선의 모양에 따라 error크기가 달라지므로, 점과 직선간의 거리 (직선의 법선 벡터 방향) 으로 error를 측정한다. $ax+by=d$직선과 $(x_i, y_i)$와의 거리는 $
|ax_i + by_i -d|$이므로, cost function은 다음과 같다.

 

이를 풀기 위해 미분하면,

 

$(U^TU)n = 0$을 푸는 것과 같다.

 

 

 

Robust Estimators

대부분, model을 fitting할 때, noise가 존재하여 그 것까지 고려하는 Generative model을 구성한다. 하지만, 이 distribution을 따르지 않는 outlier가 존재하고 위의 방법에 따르면 크게 모델이 잘못 fitting된다. 즉, inlier보다 outlier의 contribution이 높아 제대로 된 모델을 찾을 수 없다.

 

 

 

 

 

Outlier의 큰 contribution을 방지하기 위해, 아래 그래프처럼, 거리에 따라 가중치를 둬서 영향에 제한을 둔다. 아래 robust function에서 $\sigma$에 따라 가중치 정도를 정할 수 있다.

 

 

 

 

 

 

RANSAC

Random Sample Consensus

1. 랜덤하게 minimal subset을 고른다.

2. 해당 subset에 맞는 model을 설정한다.

3. 모든 점에 대해 error를 계산한다.

4. margin안에 드는 (threshold)안의 점을 모두 조사하여 평가한다.

5. model hypothesize와 verify를 반복하여 가장 맞는 모델을 찾는다.

 

아래는 위의 과정을 알고리즘으로 표현한 psuedo-code이다.

 

 

 

마지막에는 최종 $S_i$에 대해, 다시 re-estimate (Total least squares 등) 하는 과정이다. 이를 수행하면 더 정확한 결과를 얻을 수 있다.

 

 

Distance threshold

noise가 Gaussian distribution을 따른다하면, $d^2$은 $\chi$ distribution을 따른다. RANSAC에서는 threshold를 정하는 것이 중요한데, threshold 안에 들어올 확률 $\alpha$를 설정하면 threshold $t$를 설정할 수 있다.

 

표준편차가 $\sigma$인 Gaussian distribution을 따를 경우, 아래와 같이 결정된다.

 

 

How many samples

그 다음 parameter로, 얼마나 sampling을 해야하는지 sampling 횟수 $N$을 정하는 것이 중요하다.

이 때, 하나의 point가 outlier일 확률을 $\epsilon$이라 하자.

그러면, 한 point가 inlier일 확률 $\omega$는 $\omega = 1 - \epsilon$이다.

 

이때, $p$ parameter를 정의하자.

$p$는 N개의 sample 중에, 하나 이상의 sample (s개의 point)가 모두 inlier에 포함될 확률이다.

그럼 아래와 같은 공식으로 $\omega$또는 $\epsilon$에 대한 식으로 유도된다.

 

 

이를 통해 N을 다음과 같이 잡을 수 있다.

 

 

여기서, 충분히 작은 $\epsilon$이 보장된다면, 굉장히 작은 N에 대해서 알고리즘이 수행될 수 있다는 것을 알 수 있다.

 

 

Adaptive determination of the # of samples

하지만 위에서의 문제점은 $\epsilon$을 알 수 없는 경우가 많다. 그리고 굳이 N번을 모두 실행하지 않아도 끝낼 수 있다는 점이다.

아래 알고리즘은 expected inlier가 도달하면 알고리즘을 terminate한다. $T = (1 - \epsilon)n$

그리고 sample을 뽑을 때마다 $\epsilon$을 업데이트하여 추정한다.

 

 

 

 

Final step

마지막으로, 수집한 전체 inlier을 통해 re-estimate를 진행한다. (least squares)

 

 

Pros & Cons

Pros : simple하고 general함. 그리고 여러 어려운 문제에 대해 응용할 수 있음.

Cons : 많은 parameter를 tuning해야함. outlier 비율이 높을 경우 잘 작동하지 않음.