Stereo Vision
두 이미지에서 동일한 점을 삼각으로 측정해서 depth를 복원한다
The epipolar constraint
매칭 포인트는 해당 epipolar line 상에 놓인다
대응하는 epipolar line을 따라서 1차원 탐색하여 대응 문제를 축소한다
매칭의 비용과 ambiguity를 줄여준다
Rectifination
epipolar line을 평행하게 만들어주는 것
평행하게 해야 알고리즘 수행이 가능하다
Model Fitting
Fitting a Model to Data
모델을 일부 선택된 부분에 맞춰어 이미지 부분을 함께 cluster한다
example
- line이 point의 집합에 맞으면, 우연에 의한 가능성이 낮으므로 그 점들을 선으로 표현한다
- 3D 모델이 rotate되고 translate 되어 점이나 선분 집합에 잘 맞출 수 있다. 잘 맞으면 객체가 인식된다
해당 작업이 어려운 이유는
- 불필요한 데이터가 있어 어떤 부분이 모델이 속하는지 알기 어렵다
- 누락된 데이터가 있어 모델의 일부만 존재한다
- 노이즈
- 비용 면에서 가능한 feature의 모든 조합을 확인하는 것은 불가능하다
직선 방정식
일반적인 형태의 직선 방정식 \(y=mx+b\)는 m이 무한대로 갈 수 있다
따라서 극좌표를 이용한다
Hough Transform
각 점은 해당 점을 통과하는 선에 투표한다
$$xsin\theta - ycos\theta +d=0$$
위 직선을 만족하는 점 (x,y)의 집합이 있다
어떤 (x,y)점에 대해서도 이 점을 지나는 \(\theta, d\) 매개변수의 집단이 있다
각 점은 집단의 각 선에 투표한다(floating)
투표를 더 많이 받은 선은 그 선을 위해서 투표한 점들 근처를 지나는 선이 된다
Hough transform은 linear time안에 잡음에서 feature 그룹을 추출할 수 있다
RANSAC (RANdom SAmple Consensus)
1. 모델을 맞추는 데 필요한 최소한의 데이터 점 집합 샘플을 무작위로 선택한다
2. 모델에서 일정 거리 threshold t 이내에 있는 점들은 consensus 집합이다. consensus 집합의 크기는 모델의 support(지지력)정도이다
3. N개의 샘플에 대해서 반복한다. 가장 큰 지지력을 가진 모델이 가장 견고한 적합 모델이다
최적의 모델에서 거리 t안에 있는 점들은 inliers이다
최종 모델을 모든 inlier에 맞춘다
After RANSAC
RANSAC은 데이터를 inliers와 outliers로 나누고 최소한의 inlier 집합으로부터 계산된 추정치를 제공한다
이 초기 추정치를 모든 inlier을 사용한 추정치로 개선한다
하지만 inlier을 변경할 수 있기 때문에, 적합성과 inlier/outlier으로 재분류를 번갈아 수행한다
Discussion of RANSAC
장점
- 다양한 모델 피팅 문제에 적합안 일반적인 방법이다
- 구현이 쉽고 실패율 계산이 쉽다
단점
- 중간 정도의 outliers만 처리할 수 있고, 그 이상은 비용이 급증한다
- 실제 문제들은 높은 정도의 outlier을 가지고 있다
hough transform은 높은 비율의 outlier을 처리할 수 있지만, 큰 bin에서는 noise와 같은 false collision이 증가한다
