[3D CV] Two View Geometry (2)

Fundamental Matrix & Essential Matrix

이번에는 저번 Twe View Geometry (1)에 이어

Fundamental matrix를 더 자세히 공부하고 Essential matrix에 대해 배움

(참고: https://dohlab.tistory.com/119)

 

$F$가 언제 유효한 fundamental matrix인지?

$P$와 $P'$이 있을 때 어떻게 $F$를 구할까?

$F$를 $P$와 $P'$으로 어떻게 decompose할까?

 

$R$, $\mathbf{t}$는 모르지만 $K$를 알 때, essential matrix $E$가 무엇일까?

2개의 calibration된 카메라로 어떻게 $E$를 구할까?

$E$로 어떻게 2개의 카메라 파라미터 $P$, $P'$으로 decompose할까?

$E$가 언제 유효한 essential matrix인지?

 

하나씩 살펴보자

 

Projective Ambiguity of Cameras Given $F$

$P$랑 $P'$이 주어졌을 때 $F$를 구하는건 이전에 배웠음

$$[ \mathbf{e}']_\times P' P^+ = F$$

반대로 $F$가 주어졌을 때, $P$, $P'$을 구해보자

$$P \mathbf{X} = (PH)(H^{-1} \mathbf{X})$$

$$P' \mathbf{X} = (P'H)(H^{-1} \mathbf{X})$$

임의의 4x4 matrix $H$를 가정했을 때,

projection 식을 위와 같이 가운데 $H$를 넣을 수 있음

여기서 $P$는 $PH$라는 새로운 파라미터가 되고

$\mathbf{X}$는 $H^{-1} \mathbf{X}$라는 새로운 3D 포인트가 됨

 

이게 무슨 의미냐면 카메라도 $PH$로 변환시키고,

world coordinate $\mathbf{X}$도 $H^{-1}$이라는 homography로 변환시킴

극단적으로 $P$와 $X$의 주변환경, 세상을 바꾼후에 둘을 곱해도 $P\mathbf{X}$가 됨

즉, 3D 환경을 카메라와 포인트 둘다 잘 바꾸면 2D상에서는 구분 불가능

→ solution이 여러개가 될 수 있음

 

약간 비슷한 예시로는 동영상 찍을 때 카메라는 가만히 있는데 환경이 움직이거나,

환경은 가만히있는데 카메라가 움직여도 같은 영상이 나올 수 있는? 그런 느낌

 

$$[ \mathbf{e}']_\times P' P^+ = F$$

마찬가지로 $P'$, $P^+$을 $P'H$, $H^{-1} P^+$으로 바꿔도 $F$는 그대로 유지됨

그렇기 때문에 $P$, $P'$을 가지고 $F$를 구하는건 유일한 solution이 나오지만

$F$에서 $P$, $P'$을 구하는건 유일한 solution이 나오지 않음

→ ambiguity 발생
→ $F$를 분해해도 정확한 $P$, $P’$이 안 나올 수 있음

 

Canonical Forms of Camera Matrices

$F$를 구하는 방법 중 Canonical form에 대한 내용

$$P = [I | \mathbf{0}], \quad P' = [M | \mathbf{m}]$$
$P$, $P’$이 위와 같은 형태일 때,

$$\mathbf{e}' = P' C = [M | \mathbf{m}] [ 0, 0, 0, 1]^T =\mathbf{m}$$

그리고

$$[\mathbf{e}']_\times P' P^+ = F$$

이므로

$$F = [\mathbf{e}']_\times P' P^+ = [\mathbf{m}]_\times [M|\mathbf{m}] \begin{bmatrix} I_{3 \times 3} \\ 0_{3 \times 1} \end{bmatrix} = [\mathbf{m}]_\times M$$

$$F = [\mathbf{m}]_\times M$$
$F$가 위와 같이 구해짐

 

Skew Symmetric Matrix

그리고 Skew symmetric Matrix에 특별한 성질이 있는데

Skew symmetric Matrix는 위 성질을 만족하고

3D cross product matrix를 만들 때 사용함

$$a \times b = [a]_\times b$$

예를들어,

$$ \mathbf{e} = \begin{bmatrix} e_1 \\ e_2 \\ e_3 \end{bmatrix} \rightarrow [\mathbf{e}]_\times = \begin{bmatrix} 0 & -e_3 & e_2 \\ e_3 & 0 & -e_1 \\ -e_2 & e_1 & 0 \end{bmatrix}$$

이제 이걸로 matrix multiplication을 수행하면 cross product가 됨

 

그리고 skew symmetric matrix의 정의는

$$A = -A^T$$

다음 성질을 만족하면 됨

 

그리고 skew symmetric matrix는 eigen decompose를 하면 항상 아래와 같이 됨

$$A = UDU^T \text{where} \begin{cases} D = \begin{bmatrix} 0 & -\lambda \\ \lambda & 0 \end{bmatrix} & \text{in 2D} \\ D= \begin{bmatrix} 0 & -\lambda & 0 \\ \lambda & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} & \text{in 3D} \end{cases}$$

위처럼 $D$가 나옴

 

그리고 또 다른 특별한 성질은

$$x^T A x = 0, \forall x \iff A \text{ is skew-symmetric}$$

위와 같은 quadratic form에 대해서 0을 만족하면 $A$는 skew-symmetric

 

증명은 다음과 같음

$$x^T A x = (x^T A x)^T = x^T A^T x $$

Transpose 해도 성립하는 이유는 어차피 좌변이 scalar여서 상관 없음

만일, $A$가 skew-symmetric이면 $A=-A^T$이므로

$$x^T A^T x = -x^T A x$$

따라서,

$$x^T A x = -x^T Ax$$

결국, $A$가 skew-symmetric이면 반드시 $x^T A x = 0$

위 증명은 if and only if에서 좌측방향으로 증명이고

반대로 우측방향 증명도 해보면

 

$$x^T A x = 0, \forall x$$

위 조건을 만족하면,

$$e_i^T A e_i = 0 \Rightarrow A_{ii} = 0$$

($e_i$는 $i$번째 원소만 값이 1이고 나머지는 0인 벡터)

$e_i$를 $x$에 대입했을 때, 0을 만족하려면 $A$의 대각성분은 전부 0이 되야함

 

$$(e_i + e_j)^T A (e_i + e_j) = 0 \Rightarrow A_{ij} + A_{ji} = 0$$

이번에는 $e_i + e_j$를 $x$에 대입하면, 대칭성분 끼리 더했을 때 전부 0이 나옴

 

위 2개를 조합해서 보면 결국

$A = -A^T$를 만족하게 됨

 

Canonical Cameras Given $F$

이제 필요한 것들은 배웠고,

$F$라는 matrix가 언제 Fundamental Matrix가 될까?

$$P^{'T} F P$$

위와 같은 행렬이 skew-symmetric이면 $F$는 $P$와 $P'$의 Fundamental Matrix

$$P^{'T} F P \text{ is skew-symmetric} \iff \mathbf{X}^T P^{'T} FP \mathbf{X} = 0 , \forall \mathbf{X}$$

$$\underbrace{\mathbf{X}^T P^{'T}}_{\mathbf{x}^{'T}} F \underbrace{P \mathbf{X}}_{\mathbf{x}} = 0 , \forall \mathbf{X}$$

$\mathbf{X}^T P^{'T} = (P' \mathbf{X})^T$는 3D point를 2D로 projection 시킨것이므로 결국 아래와 같은 형태가됨

$$x^T A x = 0, \forall x \iff A \text{ is skew-symmetric}$$

따라서, $P$와 $P'$에 대해 유효한 $F$가 됨

 

이번에는 $F$를 decompose 해보자

맨 처음에 말했듯이 유일한 $P$, $P'$으로 decompose 할 수 없음

일단은 $P$를 간단하게 Canonical form으로 가정하면

$$P = [I | \mathbf{0}]$$

$P$가 이러면 나머지 $P'$은 다음과 같이 되야함

$$P' = [SF | \mathbf{e}']$$

$S$는 임의의 skew symmetric matrix이면서, $P'$을 Rank=3을 만들 수 있어야함
$F$는 알고있고, $\mathbf{e}'$은 $F$의 null space로 구하면 됨

증명은 $P^{'T} F P$가 skew symmetric 만족하면 됨

$$ [SF |\mathbf{e}']^T F [I | \mathbf{0}] = \begin{bmatrix} F^T S^T F & \mathbf{0} \\ \mathbf{e}' F & 0 \end{bmatrix} = \begin{bmatrix} F^T S^T F & \mathbf{0} \\ 0 & 0 \end{bmatrix}$$

($F \mathbf{e} = 0$, $F^T \mathbf{e}' = 0$)

맨 마지막 결과의 skew symmetric 성질을 확인

$$-\begin{bmatrix} F S F^T & \mathbf{0} \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} F^T S^T F & \mathbf{0} \\ 0 & 0 \end{bmatrix}^T$$

skew-symmetric 성질인 $A = -A^T$ 만족

따라서, $P'^T FP$의 결과가 skew-symmetric 성질 만족함

 

그러면 $S$는 조건만 만족하면 아무거나 된다고 했는데 주로 사용하는 형태가 있음

$$S = [\mathbf{e}']_\times$$

$\mathbf{e}'$의 skew-symmetric 형태를 $S$를 사용하면 됨
$\mathbf{e}'$은 Null space로 구하기

따라서, $P$, $P'$은 다음과 같음

$$P = [I | \mathbf{0}], \quad P' = [[\mathbf{e}']_\times F | \mathbf{e}']$$
다시 말하지만 이 $P$, $P'$은 유일한한게 아님, solution이 더 있음
어쨌든든 $F$가 주어지면 $P$, $P'$으로 decompose 할 수 있음

 

Essential Matrix $E$

$F$는 $P$랑 $P'$으로부터 유도됨

만일, calibration이 되어있다면 $K$를 알 수 있고,

$$\mathbf{x} = K[R| \mathbf{t}] \mathbf{X}$$

$$K^{-1} \mathbf{x} = [R | \mathbf{t}] \mathbf{X}$$

$K$를 알고 있으니 역함수를 곱할 수 있음

$$\hat{\mathbf{x}} = [R|\mathbf{t}] \mathbf{X}$$

왼쪽이 $\hat{\mathbf{x}}$가 되는데 normalized coordinate라 (back-projection)
이제 $K$를 제거한 형태인 $\hat{\mathbf{x}}$를 다루는게 Essential Matrix

 

이전의 다양한 $P$, $P'$에 따라 Fandamental matrix 형태가 있었는데

 

이부분을 가져다가 아래 식에 대입

$$\mathbf{x}^{'T} F \mathbf{x} = 0$$

$$\mathbf{x}^{'T} K^{'-T} [ \mathbf{t}]_\times R K^{-1} \mathbf{x} = 0$$

$$\hat{\mathbf{x}'}^T [\mathbf{t}]_\times R \hat{\mathbf{x}} = 0$$

위의 가운데를 $E$ Essential matrix라고 부름

$$\hat{\mathbf{x}'}^T E \hat{\mathbf{x}} = 0$$

$$E = [\mathbf{t}]_\times R$$

그리고 $F= K^{'-T} [\mathbf{t}]_\times R K^{-1}$을 사용하면

$F$와의 관계도 추가할 수 있음

$$E = [\mathbf{t}]_\times R = K^{'T} F K$$

$E$가 중요한 이유는 두 카메라 사이의 geometry는 위치관계가 중요한데

$E$는 식을보면 $\mathbf{t}$랑 $R$만 관련이 있음

 

$R$은 3x3 Full Rank=3이고 $[\mathbf{t}]_\times$는 skew-symmetric이면서 Rank=2

따라서, $E$는 3x3, up-to scale, Rank=2, DoF는 3($\mathbf{t}$) + 3($R$) - 1 (up-to scale) = 5 DoF

 

$E$의 특징을 보면

$E$를 SVD 하면 다음과 같음

$$E = U \begin{bmatrix} \lambda & 0 & 0 \\ 0 & \lambda & 0 \\ 0 & 0 & 0 \end{bmatrix} V^T$$

$E$가 유효한 Essential matrix이면 SVD를 했을 때 같은 singular value가 대각성분에 나와야 함

증명은 생략

 

Extracting Cameras from Essential Matrix $E$

이번에는 $E$를 decompose해서 $\mathbf{t}$, $R$을 구해보자
$E$는 $F$와 다르게 solution이 무한히 많지 않고 4개정도 나옴, 그 중에 1개를 고르면 됨

$$E = [\mathbf{t}]_\times R$$

그리고 결과를 미리 말하면 decompose 해서 나오는 solution을 보면

2개의 카메라 사이의 위치 관계가 바로 나옴 → 이후에 배울 SfM의 첫번째 단계

$$E = U \begin{bmatrix} \lambda & 0 & 0 \\ 0 & \lambda & 0 \\ 0 & 0 & 0 \end{bmatrix} V^T$$

먼저 SVD로 분해한다음 up-to scale이니깐 $\lambda$를 나눠서 제거

$$E = U \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} V^T$$

그런다음 $Z$랑 $W$라는 matrix를 가정

$$Z = \begin{bmatrix} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \quad W = \begin{bmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

그리고 $Z$와 $W$는 특이한 형태가나오는데

$$ZW = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \quad ZW^T = \begin{bmatrix} -1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 0 \end{bmatrix} $$

$E$의 SVD의 대각행렬 형태가 나옴 ($ZW^T$는 up-to scale이므로 $-$ 무시가능)

이제 SVD의 가운데를 $ZW$ 또는 $ZW^T$ 둘중 아무거나로 대체가 가능한데

둘다 가능하니깐 $W$의 2가지 경우를 $X$라고 가정

$$X= W \text{ or } W^T$$

$$E = U(ZX)V^T$$

그리고 $U$랑 $V^T$는 orthogonal 이여서 자기자신을 Transpose해서 곱하면 $I$가 됨

$Z$와 $X$ 사이에 $U^T U = I$를 대입하면

$$E = U(ZX)V^T = U (Z (U^T U) X)V^T$$

$$E = UZU^T UXV^T = (UZU^T)(UXV^T)$$

$UZU^T$는 3x3 skew-symmetric인 $[\mathbf{t}]_\times$이고

$UXV^T$는 3x3 rotation인 $R$이 됨

 

$UXV^T =R$ 인걸 증명하려면
$R^T R =I$ 증명하면 됨
$(UXV^T)^T (UXV^T)$ 
$=VX^T U^T U X V ^T$
$=VX^T XV^T$
$=VW^T W V^T$
$=VIV^T$
$=VV^T$
$=I$

 

그리고 $UZU^T$도 skew-symmetric 성질로 증명하면됨
$(UZU^T)^T$
$= UZ^T U^T$
$= -UZU^T$
따라서, $A^T = -A$ 만족하므로 skew-symmetric 성질 증명 완료

 

결국,

$$E = (UZU^T)(UXV^T)$$

이렇게 $[\mathbf{t}]_\times$와 $R$로 decompose가 되는데

$$X= W \text{ or } W^T$$

$X$가 2개 중 아무거나 선택하면 되서 $R$의 경우의 수가 2개가 나옴

또한, $U$의 3번째 column이 $\mathbf{t}$가 되는데 부호가 $\pm$이여서 경우의 수 2개가 나옴

$$\mathbf{t} = \pm \mathbf{u}_3$$

따라서, 분해할 수 있는 모든 경우의 수가 4개가 됨

 

이제 $P$, $P'$ pair 쌍을 경우의 수에 따라 확인해보면

$$P = [I| \mathbf{0}]$$

먼저 카메라 하나는 center가 world origin이라고 가정하면 나머지 $P'$은 4개가 나옴

$$P' = [UWV^T \mid +\mathbf{u}_3] \ \text{or} \ [UWV^T \mid -\mathbf{u}_3] \ \text{or} \ [UW^TV^T \mid +\mathbf{u}_3] \ \text{or} \ [UW^T V^T \mid -\mathbf{u}_3]$$

 

4가지 solution에 대해 실제로 visualizing을 해보면 위처럼 나오는데

4개의 solution 중 (a)처럼 1개만 3D point가 2대의 카메라에 앞쪽에 위치하게 됨

따라서, 이거를 solution으로 고르면 정답

 

나머지 3개는 카메라 뒤에 있는 point가 projection되는 경우도 solution에 포함 되어서 그럼

 

8 Points Algorithm

$$\mathbf{x}'^T F \mathbf{x} = 0 \quad \mathbf{x} = (x, y, 1)^T \quad \mathbf{x}' = (x', y', 1)^T$$

$$\implies x'x f_{11} + x'y f_{12} + x'f_{13} + y'x f_{21} + y'y f_{22} + y'f_{23} + x f_{31} + y f_{32} + f_{33} = 0$$

$$\implies (x'x, x'y, x', y'x, y'y, y', x, y, 1) \mathbf{f} = 0$$

$$\implies A \mathbf{f} = \begin{bmatrix} x_1'x_1 & x_1'y_1 & x_1' & y_1'x_1 & y_1'y_1 & y_1' & x_1 & y_1 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ x_n'x_n & x_n'y_n & x_n' & y_n'x_n & y_n'y_n & y_n' & x_n & y_n & 1 \end{bmatrix} \mathbf{f} = \mathbf{0}$$

$F$를 찾는 8 points 알고리즘인데
2개의 이미지 사이의 correspondence가 주어진다면
대입해서 방정식 만든 다음 $f$에 대해서 쭉 정리 (DLT 처럼 하면 됨)
$F$의 DoF = 7이라고 했는데 Rank=2라는 컨셉을 적용했기 때문임

Rank=2 컨셉을 적용하지 않고 일반적인 $F$로 생각하면 3x3니깐 9 - 1(up-to scale) DoF = 8 DoF
따라서, 8개의 row, corresponding points가 필요

 

이번에는 Rank=2 고려

Rank=2를 고려 안하면 왼쪽 그림처럼 Epipole 한점에서 안 만날 수 있음(by correspondence 노이즈)
→ Rank=2인 $F$를 강제해야함

 

일단, DLT로 $F$를 구한 다음 SVD를 함

$$F = UDV^T \longrightarrow F' = UD'V^T$$

Rank=2가 아니면 D(diagonal matrix)의 3개의 singular value가 나옴

singular value 3개중에 마지막 요소를 그냥 0으로 만들고 그 $D$를 $D'$이라하면
Rank=2이면서 $F$와 가장 근접하고 최적화된 $F'$을 얻을 수 있음

 

$F'$은 원래 $F$로 부터의 Frobenius norm을 minimize하면서 $det(F')=0$ (Rank=2)인 것을 만족시킴

$$\text{Frobenius norm : }||F - F'||_F$$
PCA 이미지 압축 느낌으로

→ 왼, 위쪽에 있는 singular value일수록 중요한 값이므로 중요하지 않은 오른, 아래쪽 값들을 없애서 최적화

 

7 Points Algorithm

7 Points 알고리즘은 7개의 correspondence로 Rank=2인 $F$를 바로 찾는 방법인데 생략

 

5 Points Algorithm(Estimating $E$)

5 Points 알고리즘은 $E$를 구할 때 사용함

$E$는 5 DoF라서 5개의 correspondence로 구하면 됨

이것도 복잡해서 자세한 내용은 생략하고 Opencv에서 가져다 쓰면 됨

https://docs.opencv.org/4.x/d9/d0c/group__calib3d.html#gab705726dc6b655acf50bc936942824ef

 

Estimating $F$ (or $E$) in Practice(8 Points Algorithm)

실제로 $F$를 구할 때 바로 correspondence를 적용하면 잘 안됨
만약 image resolution이 엄청 큰 (1000x500)과 같은 이미지면 point 좌표가 엄청 커짐
좌표값이 큰값이므로 노이즈가 조금이라도 있으면 노이즈도 엄청 큼
따라서, point에 대해 normalize를 해야함
point들의 centroid(중심)를 origin에 있게하고 RMS 거리를 $\sqrt{2}$가 되도록 normalize하는 $T$를 만듬

$$\hat{\mathbf{x}}_i = T \mathbf{x}_i , \quad \hat{\mathbf{x}}'_i = T' \mathbf{x}'_i$$

이렇게 모든 point를 normalize가 된 space로 옮기고
이걸 가지고 $\hat{F}$를 구함

이전에 배웠듯이 DLT를 쓴 후 SVD를 통해 $det(\hat{F})=0$(Rank=2)을

만족하도록 하는 $\hat{F}$를 찾으면 됨

이렇게 구한 normalize 된 $\hat{F}$을 denormalize 해서 $F$를 구해야함

$$\text{Denormalization : } F = T^{'T} \hat{F} T \quad \text{for} \quad \mathbf{x}_t \leftrightarrow \mathbf{x}_t'$$