- 한쌍의 corresponding point가 주어진다면 위의 coplarity constraint가 성립한다.
- 이 식은 Fundamental Matrix 계산과 동일한 형태이나, 정규화된 카메라 좌표계 (즉, 내부 파라미터 K를 제거한 상태)에서 사용된다는 점이 다름.
Constraints
[Fundamental Matrix]
- 마지막 특이값을 0으로 만들어 rank2를 보장한다.
[Essential Matrix]
- E도 마찬가지로 진행 - 추가적으로 non-zero singular value가 서로 같아야 한다. (scale이 중요하지 않다.) => D = diag(d,d,0) / D = diag(1,1,0)
Essential matrix A를 SVD해서 UDV를 얻음 UDV에 V를 취해서 E를 만들어 준다. E를 다시 SVD한다. => 나온 값을 U와 V는 그대로 쓰고 D를 [110]을 가진 diagonal matrix로 변경
Normalization
- Essential Matrix를 계산하기 위해 구성하는 행렬 A가 SVD에 적합하도록 수치적 조건(conditioning)을 개선해야 한다. 1. Transform: 모든 포인트의 중심을 (0,0)으로 이동 2. Scale: 좌표 범위를 [−1,1]안으로 맞춤
[수식 정리] 1. Define T (정규화 변환)
변환 후 좌표는 (0,0)을 중심으로 하고, scale은 [-1,1]
2. 정규화된 좌표로 Essential matrix 계산
3. 원래 좌표로 되돌린다.
Essential Matrix의 성질
5-Point Algorithm
- 현재 Essential Matrix E 계산을 위해 가장 널리 쓰이는 방법 - 다항식 시스템을 푸는 문제로 환원된다. (10차) - 이론적으로는 최대 10개의 해가 존재 - 주로 RANSAC과 함꼐 사용된다.
Computing Baseline and Rotation Given E
- 5,8 Point Algorithm을 이용해서 Essential matrix까지 구했다. => 이걸 가지고 Relative Orientation을 구하자!
Q) 이것은 Unique Solution인가? A) solution은 4개가 나온다. baseline : +,- ratation : +,- 이 중 하나만 정답이다.
=> 물리적으로 실현 가능한 정답은 하나 밖에 없다. (point들이 두 카메라 앞에 위치하는 것)
Hartley & Zisserman
E로부터 위 4가지의 Solution을 어떻게 구하지? * U, V : orthogonal matrix (rotation matrix가 될 수 있는 특성을 가지고 있다.) Z와 W를 임의로 설정하고 이로 분해다음 4가지의 solution이 나온다.
이것들 중 모든 point가 카메라 앞에 위치하는 한가지가 정답이다.
[Solution by Hartley & Zisserman] 1. E에 대해 SVD 진행
2. U, V를 Normalized (이건 굳이 할 필요 X)
3. 4가지 solution을 계산
4. 4가지 solution 중 올바른 해를 구한다. => 어떤 해에서 모든 점이 두 카메라 앞에 위치하는가를 테스트
5. 최종적으로 물리적으로 실현 가능한 카메라 설정만 선택
5,8 point로 Essential matrix를 구한다. SVD를 해서 UDV가 나온다. UDV를 Z와 W를 Hartley&Zisserman 방식으로 설정 basis와 ratation을 구할 수 있다. 4개의 solution을 구할 수 있다. 최종 solution은 모든 point들이 두 개의 카메라 앞에 있어야 한다.
Summary
- 위의 Algorithm들은 image data로부터 relative orientaion 계산 - Camera motion에 따라 분류된다. (except of the scale) Calibration O : Essential Matrix E Calibration X : Fundamental Matrix F
- Direct Solution 및 특징
1. E로부터 Sb, R 추출 가능 2. 수치적으로 optimal(최적)은 아니다. => solution은 낼 수 있고 빠르다. (RANSAC을 통해 그 중 제일 좋은 것을 선택) 3. RANSAC과 함께 사용 (Inlier / Ourlier 구별을 위해 사용) 4. 이후 반복 최적화(iterative refinement) 진행 (Least squares / 오직 inlier point만 이용하여 최종 정밀 추정)
RANSAC (RANdom SAmple Consensus)
- Random하게 8개씩 골라서 많이 만들어 그 중에 Essential Matrix를 제일 좋은 것을 고른다. - 시도해보고 좋은지 안좋은지 평가 - 비교적 내가 가진 datapoint에 outlier의 %가 높아도 사용 가능 (범용적인 알고리즘 / 어떤 모델에도 활용 가능)
Key Idea) data point 집합을 Inlier와 Outlier로 나누는 최적 분할을 찾는 것 => 가지고 있는 data point에서 Inlier로만 구성해서 모델을 만든다.
3-Step
1. Sample model을 만들기 위해 최소한의 점 수만큼 뽑아낸다. ex) 5-point, 8-point
2. Compute sampling된 point들을 이용해서 model parameter를 계산한다. ex) 모델을 만든다. Essential matrix를 구한다.
3. Score 전체 데이터에 대해, 계산된 모델에 얼마나 많은 점들이 inlier(허용 오차 이내에 있는 점)로 분류되는지를 측정 ex) 이렇게 만든 Essential matrix가 얼마나 좋은지를 평가 / Inlier의 개수가 score
# Repeat 1~3을 반복하며 high confidence를 가진 best model을 찾는다. ex) score가 가장 높은 것(Inlier 개수가 가장 많은 모델) : 최종 solution
Line fitting EX)
1. Sample
2. Compute
3. Score
# Repeat
=> 가장 좋은 값만 저장하고 있으면서 update
How to Choose the parameters?
- Sample 수 s : model을 적절히 fitting하는 데 필요한 최소 sample 수 - Outlier ratio e : 전체 data 중 outlier의 비율 - Numer of trials T : 시도(반복) 횟수 Q) 몇번의 시도(T)가 필요한가? A) => 몇 개를 뽑아야 하는가? (s) => data point에 outlier가 얼마나 섞여 있는가? (e) -> 이걸 알기가 어렵다. (probability를 줘서 T를 구할 순 있다.) 위 식 양변에 log를 취한다.T를 다음과 같이 계산 가능하다.
[결과] - outlier가 늘어나면 T가 급격하게 늘어난다. - RANSAC 입장에서는 5-point 알고리즘이 유리하다 (S값이 작아 T 횟수를 줄일 수 있다.)
RANSAC의 장단점 [장점] 1. oulier가 많아도 Robust하게 작동 2. 1~10개의 parameter 수(sample point 개수)에 대해서는 효과적이다. 3. 구현이 간단하고 이해하기 쉽다.
[단점] 1. parameter 수가 많아지면 계산 시간이 급격히 증가한다. 2. 하나의 모델을 fitting 하기는 좋지만, 여러 모델을 동시에 fitting하기는 어렵다. (Multiple model fitting 하기엔 좋지 않다.)
2개의 이미지간의 relative orientation(상대적인 위치)가 주어졌을 때 3D 상의 점들을 계산하자.
(크기는 모르지만 상대적인 structure는 다 구성할 수 있다.)
- 3D 상에서 어긋나서 정확히 만나지 않아 만나는 점을 못 찾을 수 있다.
=> 대충 쉽게 중간점을 찾자!
Finding point H
1. P에서 Q 직선까지 가장 가까운 점 G를 구한다.
2. Q에서 P 직선까지 가장 가까운 점 F를 구한다.
3. G와 F를 연결하여 중간점 H를 찾는다.
Triangulation (Geometric Solution)
AX=b꼴
- λ와 μ는 AX=b꼴이므로 위에서 구할 수 있다.
1. 간단한 3D Geometry로 solution을 계산한다. 2. 수학적으로는 2개의 미지수(λ, μ)를 가지는 2개의 선형 방정식을 푸는 문제 => optimal solution이 아닐 수 있다. (uncertainties를 고려하지 않았다.)
Intersection of Two Rays for the Stereo Normal Case
- 만약 y-parallax가 0이라면 이렇게 쓸 수 있다.Homogeneous Coordinate 진행parallax map 정의
=> 이는 3D Reconstruction을 가능하게 한다.
Triangulation-Summary
- R, O 주어져 있을때 3D를 구하는 방법 : Triangulation - F, G를 구해 그 사이 H(3D point)를 구한다. - Stero normal case: 가장 간단한 case (parallax만 알면 다 쉽게 계산이 가능) (y-parallax가 0이 되도록 정렬 / x-parallax만 알면 깊이 정보를 구할 수 있다.)
