Search
Duplicate

AI/ Essential Matrix, Fundamental Matrix

Essential Matrix와 Fundamental Matrix는 epipolar line을 찾기 위해 계산하며, epipolar line은 stereo 이미지를 rectify 하기 위해 사용된다.

Essential Matrix

epipolar geometry framework에서 두 카메라가 K=K′=IK = K' = I인 canonical camera이고, 첫 번째 카메라를 기준계로 설정하여, 두 번째 카메라가 첫 번째 카메라에 대해 rotation RR 한 다음 translation TT만큼 offset되어 있다고 가정하자. 이 경우 두 카메라에 대한 Camera Projection Matrix는 다음과 같이 정의된다.
M=K[I0]M′=[R⊤−R⊤T]\begin{aligned} M &= K\begin{bmatrix} I & 0 \end{bmatrix} \\ M' &= \begin{bmatrix} R^\top & -R^\top T \end{bmatrix} \end{aligned}
여기서 RR은 첫 번째 카메라를 두 번째 카메라와 같은 방향에 놓이도록 하는 rotation 값이고, TT는 첫 번째 카메라의 위치를 두 번째 카메라의 위치로 이동시키는 translation 값이다. 따라서 TT는 baseline 벡터가 되며, 3d점 PP와 두 카메라의 원점 O1,O2O_1, O_2를 포함하는 epipolar plane 위에 놓이게 된다. camera projection에 대한 더 자세한 내용은 AI/ Camera Projection Matrix 참조.
이것은 3d점 PP의 두 번째 카메라에 투영된 점 p′p'가 첫 번째 카메라의 기준계에서 Rp′+TRp' + T가 된다는 것을 의미한다. Rp′+TRp' + T와 TT가 epipolar plane에 놓이므로 둘에 대한 cross product를 구하면 다음과 같다.
T×(Rp′+T)=T×(Rp′)+T×T=T×(Rp′) (∵T×T=0)T \times (Rp' + T) = T\times (Rp') + T \times T = T \times (Rp') \ (\because T \times T = 0)
평면 위의 두 점에 대해 cross product를 구하면 해당 평면에 normal인 점이 되므로 T×(Rp′)T \times (Rp')는 epipolar plane에 normal인 점이 된다. 그것은 다시 epipolar plane에 존재하는 점 pp와 dot product하면 0이 된다는 뜻이다.
p⊤⋅[T×(Rp′)]=0p^\top \cdot [T \times (Rp')] = 0
임의의 두 벡터 a\bold{a}와 b\bold{b} 사이의 cross product를 다음과 같이 행렬-벡터 곱 형태로 표현할 수 있다. 이때 행렬을 [a×][\bold{a}_\times]로 표기한다.
a×b=[0−azayaz0−ax−ayax0][bxbybz]=[a×]b\bold{a} \times \bold{b} = \begin{bmatrix}0 & -\bold{a}_z & \bold{a}_y \\ \bold{a}_z & 0 & -\bold{a}_x \\ -\bold{a}_y & \bold{a}_x & 0 \end{bmatrix} \begin{bmatrix} \bold{b}_x \\ \bold{b}_y \\ \bold{b}_z \end{bmatrix} = [\bold{a}_\times]\bold{b}
이 표현식을 이용하여 위의 p⊤⋅[T×(Rp′)]=0p^\top \cdot [T \times (Rp')] = 0 을 아래처럼 작성할 수 있다.
p⊤[T×]Rp′=0p^\top[T_\times]Rp' = 0
여기서 E=[T×]RE = [T_\times]R을 바로 Essential Matrix라고 한다. Essential Matrix를 이용하여 위의 식을 다음처럼 작성할 수 있다.
p⊤Ep′=0p^\top E p' = 0
Essential 행렬은 5개 자유도를 갖는 3×33 \times 3 행렬로 rank-2이고 singular이다. Essential 행렬이 rank-2라는 것은 독립인 열이나 행이 2개이고, 0이 아닌 특잇값이 2개라는 의미이다.
E=UΣV⊤,Σ=[σ1000σ20000]\bold{E} = \bold{U}\boldsymbol{\Sigma}\bold{V}^\top, \boldsymbol{\Sigma} = \begin{bmatrix} \sigma_1 & 0 & 0 \\ 0 & \sigma_2 & 0 \\ 0 & 0 & 0 \end{bmatrix}
Essential 행렬을 이용하면 pp와 p′p'와 연관된 epipolar line을 쉽게 계산 할 수 있다. 예컨대 첫 번째 카메라의 점 pp에 대한 두 번째 카메라에서 epipolar line은 다음과 같다.
ℓ′=E⊤p\ell' = E^\top p
이것은 (p⊤E)⊤=E⊤p(p^\top E)^\top = E^\top p에서 유도된다. 유사하게 두 번째 카메라의 점 p′p'에 대해 첫 번째 카메라에서 epipolar line은 다음이 된다.
ℓ=Ep′\ell = Ep'
Essential 행렬이 3×33 \times 3이고 점 pp는 3×13 \times 1이므로 epipolar line은 3×13 \times 1 벡터 ℓT=[a,b,c]\ell^T = [a, b, c]가 된다. 이 벡터의 값은 다음과 같이 나타나는 직선의 방정식의 3개의 계수를 의미한다.
ax+by+c=0ax + by + c = 0
Essential 행렬의 또 다른 흥미로운 속성은 epipole과 dot product하면 0이 된다는 것이다.
E⊤e=Ee′=0E^\top e = Ee' = 0
정의에 따라 epipolar line은 epipole과 3d 점을 이미지에 투영한 점을 잇는 선이므로, 카메라 1에서 epipole ee를 제외한 임의의 점 xx에 대해 카메라 2의 이미지에서 해당하는 epipolar line ℓ′=E⊤x\ell' = E^\top x는 epipole e′e'를 포함한다. 따라서 e′e'는 모든 xx에 대해 e′⊤(E⊤x)=(e′⊤E⊤)x=(Ee′)⊤x=0e'^\top(E^\top x) = (e'^\top E^\top)x = (Ee')^\top x = 0를 만족하므로 Ee′=0Ee' = 0이다. 유사하게 E⊤e=0E^\top e = 0이다.

Fundamental Matrix

Fundamental Matrix는 Essential Matrix에서 카메라가 canonical이 아닌 경우에 해당한다. 다시 말해 Essential Matrix는 Fundamental Matrix에 대해 카메라가 canonical인 특수한 경우이다.
우선 두 카메라에 대해 첫 번째 카메라를 기준으로 두 번째 카메라를 첫 번째 카메라의 회전과 평행이동으로 정의하므로 projection matrix는 다음과 같이 주어진다. Essential Matrix와 달리 K=K′=IK = K' = I가 성립하지 않으므로 두 번째 카메라에 대해 별도의 카메라 행렬 K′K'이 곱해져야 한다.
M=K[I0]M′=K′[R⊤−R⊤T]\begin{aligned} M &= K\begin{bmatrix} I & 0 \end{bmatrix} \\ M' &= K'\begin{bmatrix} R^\top & -R^\top T \end{bmatrix} \end{aligned}
Essential Matrix에서 아래와 같이 유도 했음을 떠올려라. 여기서 [T×]R=E[T_\times]R = E가 된다.
p⊤[T×]Rp′=0p^\top[T_\times]Rp' = 0
Fundamental Matrix에서는 두 카메라의 카메라 행렬을 반영하여 다음처럼 작성한다.
p⊤K−⊤[T×]RK′−1p′=0p^\top K^{-\top}[T_\times]RK'^{-1}p' = 0
Essential Matrix에서와 유사하게 여기서 행렬 F=K′−T[T×]RK−1F = K'^{-T}[T_\times]RK^{-1}를 Fundamental Matrix라고 한다. 여기서 Fundamental Matrix는 3×33 \times 3 행렬이고 rank-2이다.
F=UΣV⊤,Σ=[σ1000σ20000]\bold{F} = \bold{U}\boldsymbol{\Sigma}\bold{V}^\top, \boldsymbol{\Sigma} = \begin{bmatrix} \sigma_1 & 0 & 0 \\ 0 & \sigma_2 & 0 \\ 0 & 0 & 0 \end{bmatrix}
Essential Matrix에서와 유사하게 Fundamental Matrix에서도 두 점 p,p′p, p'와 epipolar line ℓ,ℓ′\ell, \ell'에 대해 다음이 성립한다.
p⊤Fp′=0ℓ′=F⊤pℓ=Fp′\begin{aligned} &p^\top F p' = 0 \\& \ell' = F^\top p \\ &\ell = Fp' \end{aligned}
Fundamental Matrix와 Essential Matrix 사이의 주요한 차이는 Fundamental Matrix가 7개의 자유도를 갖는데 반해 Essential Matrix는 5개의 자유도만 포함한다는 것이다.
Essential matrix와 유사하게 Fundamental matrix를 알면 이미지 상의 점만 알아도 다른 이미지에서 해당하는 점에 대한 쉬운 제약조건(epipolar line)을 얻을 수 있다. 따라서 3d 공간에서 PP의 실제 위치나 카메라의 extrinsic 또는 intrinsic 특성을 모르더라도 임의의 pp와 p′p' 사이의 관계를 설정할 수 있다.

The Eight-Point Algorithm

카메라의 extrinsic이나 intrinsic을 모르더라도 Fundamental Matrix를 추정할 수 있게 하는 방법이 Eight-Point Algorithm이다. 이것은 8개의 독립적인 파라미터를 갖는 3×33 \times 3 Fundamental Matrix FF를 구하기 위해 두 이미지 사이에 8쌍의 대응점 집합을 이용한다.
각 대응점 쌍 pi,pi′\bold{p}_i, \bold{p}_i'에 대해 pi=(xi,yi,1)\bold{p}_i = (x_i, y_i, 1)과 pi′=(xi′,yi′,1)\bold{p}_i' = (x_i', y_i', 1)을 사용하여 다음의 선형 방정식을 형성한다.
pi⊤Fpi′=xi(f11xi′+f12yi′+f13)+yi(f21xi′+f22yi′+f23)+(f31xi′+f32yi′+f33)=0\bold{p}_i^\top\bold{F}\bold{p}_i' = x_i(f_{11}x_i' + f_{12}y_i' + f_{13}) + y_i(f_{21}x_i' + f_{22}y_i' + f_{23}) \\+ (f_{31}x_i' + f_{32}y_i' + f_{33}) = 0
이것을 행렬 형식으로 나타내면 다음과 같다.
[x1x1′x1y1′x1y1x1′y1y1′y1x1′y1′1x2x2′x2y2′x2y2x2′y2y2′y2x2′y2′1⋮⋮⋮⋮⋮⋮⋮⋮⋮x8x8′x8y8′x8y8x8′y8y8′y8x8′y8′1][f11f12f13f21f22f23f31f32f33]=0\begin{bmatrix} x_1x_1' & x_1y_1' & x_1 & y_1x_1' & y_1y_1' & y_1 & x_1' & y_1' & 1 \\ x_2x_2' & x_2y_2' & x_2 & y_2x_2' & y_2y_2' & y_2 & x_2' & y_2' & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ x_8x_8' & x_8y_8' & x_8 & y_8x_8' & y_8y_8' & y_8 & x_8' & y_8' & 1 \end{bmatrix} \begin{bmatrix} f_{11} \\ f_{12} \\ f_{13} \\ f_{21} \\ f_{22} \\ f_{23} \\ f_{31} \\ f_{32}\\f_{33} \end{bmatrix} = 0
이것은 다음의 형태가 된다.
Af=0\bold{Af} = 0
여기서 A\bold{A}는 N≥8N \ge 8개의 대응점에서 유도된 N×9N \times 9 행렬이고, f\bold{f}는 원하는 Fundamental Matrix의 값이다. 실제로는 noisy 측정의 효과를 줄이기 위해 8개 이상의 대응점과 더 큰 행렬 AA을 사용하는 것이 좋다.
위 방정식에 least squares 방법을 사용하여 f\bold{f}를 구한다. 이를 위해서는 A\bold{A}에 대해 SVD(Singular Value Decomposition)을 수행한 다음 최소 특이 값에 대응하는 특이벡터를 구한다.
A=UΣV⊤\bold{A} = \bold{U}\boldsymbol{\Sigma}\bold{V}^\top
여기서 U\bold{U}는 8×88 \times 8 행렬이고, Σ\boldsymbol{\Sigma}는 8×98 \times 9 행렬이고, V\bold{V}U\bold{U}9×99 \times 9 행렬이 된다. Σ\boldsymbol{\Sigma}가 A\bold{A}의 특잇값을 포함하는 대각행렬인데, 크기 순으로 정렬되어 있으므로 가장 마지막 행이 최소 특잇값을 포함하게 되고, 이는 V\bold{V}의 마지막 열 벡터와 곱해지므로, V\bold{V}의 마지막 열이 최소 특잇값에 대응하는 특이 벡터가 된다. 따라서 V\bold{V}의 마지막 열이 Af=0\bold{Af} = 0의 최소 제곱해를 나타낸다.
V\bold{V}의 마지막 열을 3×33\times3 행렬로 만들면 구하고자 하는 Fundamental Matrix의 근사해 F^\hat{\bold{F}}가 된다. 이렇게 구한 F^\hat{\bold{F}}는 full rank일 수 있는데, Fundamental Matrix는 rank-2여야 한다. 따라서 F^\hat{\bold{F}}에 대해 best rank-2 근사를 구해야 한다. 이를 위해 다음의 least squares를 풀어야 한다.
min⁡F∥F−F^∥Fsubject to det⁡F=0\begin{aligned} \min_\bold{F} \|\bold{F} -\hat{\bold{F}}\|_F \\ \text{subject to } \det \bold{F} = 0 \end{aligned}
이것을 해결하기 위해 다시 SVD F^=UΣV⊤\hat{\bold{F}} = \bold{U}\boldsymbol{\Sigma}\bold{V}^\top를 수행한다. 그러면 최종 F\bold{F}는 F^\hat{\bold{F}}의 특잇값 중 3번째 특잇값을 0으로 만들어서 구할 수 있다.
F=U[Σ1000Σ20000]V⊤\bold{F} = \bold{U} \begin{bmatrix} \Sigma_1 & 0 & 0 \\ 0 & \Sigma_2 & 0 \\ 0 & 0 & 0 \end{bmatrix} \bold{V}^\top

Eight-Point Algorithm 절차

정리하면 Eight-Point Algorithm의 절차는 아래와 같다.
1.
두 이미지에서 8개의 대응점 쌍 (pi,pi′)(\bold{p}_i, \bold{p}_i') 수집
2.
pi⊤Fpi′=0\bold{p}_i^\top\bold{F}\bold{p}_i' = 0을 이용하여 Af=0\bold{Af} = 0를 구성하는 행렬 A\bold{A}를 구성
3.
A\bold{A}에 대해 SVD를 수행
4.
A\bold{A}의 SVD 결과에 대해 V\bold{V}의 마지막 열을 3×33\times 3 행렬 F^\hat{\bold{F}}로 구성
5.
F^\hat{\bold{F}}에 대해 다시 SVD 수행
6.
F^\hat{\bold{F}}의 SVD 결과에 대해 Σ\boldsymbol{\Sigma}의 마지막 특잇값을 0으로 설정하여 F\bold{F}를 구성

Normalized Eight-Point Algorithm

실제에서 Eight-Point Algorithm에 대한 표준 least-squares 접근은 정확하지 않은데, 점 pip_i와 그것에 해당하는 epipolar line ℓi=Fp′\ell_i = Fp' 사이의 거리가 일반적으로 10 pixel 이상이기 때문이다. 표준 Eight-Point Algorithm이 제대로 작동하려면 A\bold{A}의 특잇값 중 하나는 0 (또는 0에 가까운) 값이어야 하고, 다른 값은 0이 아니어야 하는데, 현대 카메라의 고해상도 픽셀 범위 때문에 매우 큰 특잇값과 나머지는 상대적으로 작은 값을 갖게 될 수 있다.
이 문제를 해결하기 위해 Eight-Point Algorithm을 수행하기 전에 전처리를 하고, 그 결과에 대해 후처리를 하는 방법을 Normalized Eight-Point Algorithm이라 한다.
전처리 단계에서는 각 이미지의 중심 (xˉ,yˉ)(\bar{x}, \bar{y})을 원점으로 이동시키고, 평균 거리가 2\sqrt{2}가 되도록 스케일링한다. 이를 위한 정규화 변환 행렬 T,T′T, T'를 다음과 같이 정의할 수 있다.
T=[2sx0−2xˉsx02sy−2ysy001]T = \begin{bmatrix} {2\over s_x} & 0 & -{2\bar{x} \over s_x} \\ 0 & {2\over s_y} & -{2y \over s_y} \\ 0 & 0 & 1 \end{bmatrix}
여기서 (xˉ,yˉ)(\bar{x}, \bar{y})는 대응점의 centroid이고, sx,sys_x, s_y는 대응점의 평균거리이다.
이를 이용하여 다음처럼 대응점을 normalize 한다.
pinorm=Tpipi′norm=T′pi′\bold{p}_i^\text{norm} = T\bold{p}_i \\ \bold{p}_i'^\text{norm} = T'\bold{p}_i'
그 다음 이 normalized 좌표를 이용하여 regular Eight-Point Algorithm을 수행하여 Fnorm\bold{F}^\text{norm}을 얻는다.
Fnorm\bold{F}^\text{norm}은 normalized 좌표에 대한 Fundamental Matrix이므로 이를 다시 원래 좌표계로 변환해야 한다. 이는 다음처럼 수행할 수 있다.
F=T′⊤FnormT\bold{F} = T'^\top \bold{F}^\text{norm} T

참고

Made with