CH04. Stereo Systems (2)

Perspective structure from motion

앞서서는 간단한 affine한 경우를 알아봤고, 이제는 좀 더 일반적인 projective cameras 에 대해 알아본다.

Projective cameras $M_i$는 11의 자유도를 가지고, up to scale로 다음과 같이 표현 가능하다.

$$ M_i=\begin{bmatrix}a_{11}&a_{12}&a_{13}&b_1\\a_{21}&a_{22}&a_{23}&b_2\\a_{31}&a_{32}&a_{33}&1\end{bmatrix} $$

Affine 의 경우에는 affine transformation을 structure 행렬, motion에 해줬던 것처럼,

이 경우에는 projective transformation을 struture, motion 행렬에 적용해줄 수 있다.

(motion matrix에는 $4\times4$ projective transformation $H$를, structure에는 $H^{-1}$를)

그렇게 해도 결과적으로 image plane에서의 observations은 달라지지 않는다.  

 

Affine의 경우와 마찬가지로 $m$개의 motion matrix $M_i$와 $n$개의 3D 점 $X_i$를 이용해 $mn$개의 observation $x_{ij}$를 잡을 수 있다.

카메라와 점들은 up to scale로 $4\times4$ projective transformation으로 변환될 수 있으므로, $2mn$개의 equation과 $11m+3n-15$의 미지수를 갖는다.

따라서 이를 이용해서 필요한 view와 observation의 개수를 결정할 수 있다.  

 

The algebraic approach

두 카메라에 대한 SFM을 구하기 위해 fundamental matrix $F$를 이용한 대수적 접근(algebraic approach)을 한번 다뤄보자.

이 대수적 접근법의 주 아이디어는 perspective transformation $H$가 적용된 카메라 행렬 $M_1, M_2$를 계산해내는 것이다.

각 카메라 행렬 $M_i$가 $H$가 적용된 행렬만 계산해낼 수 있기 때문에, 첫번째 카메라 projection matrix $M_1H^{-1}$을 canonical하다고 잡을 수 있다.

마찬가지로 두 번째 카메라에도 다음과 같이 똑같은 transformation이 적용돼야 한다.

$$ M_1H^{-1}=\begin{bmatrix}I&0\end{bmatrix}\quad\quad M_2H^{-1}=\begin{bmatrix}A&b\end{bmatrix} $$

일단 이 문제를 해결하기 위해서는 eight point algorithm을 이용해서 fundamental matrix $F$를 구해야 한다.

그 후, $F$를 이용해 $M_1,M_2$를 추정해낸다.

우선, 대응하는 observations $p,p^\prime$에 해당하는 3D 점 $P$를 정의한다.

우리가 두 camera projection matrix에 똑같이 $H^{-1}$을 적용했기 때문에, structure에는 $H$를 적용해줘야 한다. ( $\tilde{P}=HP$ )

따라서, pixel 좌표 $p,p^\prime$은 다음과 같이 변환된다.

$$ p=M_1P=M_1H^{-1}HP=\begin{bmatrix}I&0\end{bmatrix}\tilde{P}\\p^\prime=M_2P=M_2H^{-1}HP=\begin{bmatrix}A&b\end{bmatrix}\tilde{P} $$

그리고 $p$와 $p^\prime$으로부터 다음과 같은 식을 유도할 수 있다.

$$ \begin{align*}p^\prime&=[A|b]\tilde{P}\\&=A[I|0]\tilde{P}+b\\&=Ap+b\end{align*} $$

양변에 $b$를 cross product 해주면,

$$ p^\prime\times b=(Ap+b)\times b=Ap\times b $$

과 같고, cross product의 정의에 따라, $p^\prime\times b$는 $p^\prime$과 perpendicular하다.

따라서,

$$ \begin{align*}0&=p^{\prime T}(p^\prime\times b)\\&=p^{\prime T}(Ap\times b)\\&=p^{\prime T}(b\times Ap)\\&=p^{\prime T}[b]_\times Ap\end{align*} $$

이 성립한다. 그런데 마지막 식의 꼴을 보면 fundamental matrix의 정의인 $p^{\prime T}Fp=0$가 떠오를 것이다.

만약 $F=[b]_\times A$ 라고 잡으면, $A$와 $b$를 구하는 문제가 그냥 decomposition이 되는 것이다.  

 

그렇다면, 먼저 $b$를 결정해보자.

Cross product의 정의에 따라, $Fb$를 다음과 같이 쓸 수 있다.

$$ Fb=[b]_\times Ab=(b\times A)b=0 $$

$F$는 singular하기 때문에(rank가 2임), $b$ 는 SVD를 이용해 $\|b\|=1$일 때 $Fb=0$의 least square solution을 구하는 것이다.

다음은 $A$를 구해보자.

$A^\prime=-[b]_\times F$로 잡으면,

$$ \begin{align*}[b_\times]A^\prime&=-[b_\times][b_\times]F\\&=-(bb^T-|b|^2I)F\\&=-bb^TF+|b|^2F\\&=0+1\cdot F\\&=F\end{align*} $$

이므로 따라서 $A=A^\prime=-[b]_\times F$ 가 성립한다.

따라서 다음과 같이 카메라 행렬 $M_1H^{-1}$과 $M_2H^{-1}$에 대해 다음과 같은 식이 성립한다.

$$ \tilde{M_1}=\begin{bmatrix}I&0\end{bmatrix}\quad\quad\tilde{M_2}=\begin{bmatrix}-[b_\times]F&b\end{bmatrix} $$

단순히 식만 유도해내는 게 아니라, $b$를 기하학적으로 해석해보자.

$b$는 $Fb=0$을 만족한다.

Epipole 또한 $Fe_2=0$ 과 $F^Te_1=0$ 과 같은 식을 만족했다.

따라서 $b$는 epipole 임을 알 수 있다.

따라서 다음과 같이 camera projection camera의 식을 변형할 수 있다.

$$ \tilde{M_1}=\begin{bmatrix}I&0\end{bmatrix}\quad\quad\tilde{M_2}=\begin{bmatrix}-[e_\times]F&e\end{bmatrix} $$  

 

Determining motion from the Essential matrix

대수적 접근으로 reconstruction이 좀 더 잘되게 하려면 calibrate된 카메라를 사용하는 것이다.

앞서서 우리는 calibrate된 카메라의 경우 essential matrix를 썼었다.(fundamental의 특별한 경우, 즉 normalized coordinates)

또한, 다음과 같은 식도 우리는 알고 있다.

$$ E=K^TFK $$

Essential matrix의 경우는 calibrated camera의 경우이므로, 5의 자유도 즉 extrinsic parameter의 정보만을 encode하고 있다. (회전과 이동)

공교롭게도, 이 $R,t$가 딱 우리가 motion matrix를 찾아내기 위해 필요한 것들이다.

먼저 essential matrix $E$가 다음과 같이 표현되었다.

$$ E=[t]_\times R $$

그러므로 $E$를 두 개의 component로 분해해볼 수 있다.

먼저, cross product 행렬인 $[t]_\times$가 skew-symmetric하다.

그래서 여기서 분해에 사옹할 두 개의 행렬을 먼저 정의해보면,

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

(여기서 나중에 사용할 중요한 성질은, $Z=\text{diag}(1,1,0)W$ 이 up to a sign 으로 만족하고,

$ZW=ZW^T=\text{diag}(1,1,0)$ 이 up to a sign으로 만족한다.)  

 

Eigenvalue decomposition을 하면 up to scale로 다음과 같이 분해를 할 수 있다.

$$ [t]_\times=UZU^T $$

($U$는 orthogonal matrix임)

따라서, 이 분해를 다음과 같이 바꿔 쓸 수 있다.

$$ E=U\text{diag}(1,1,0)(WU^TR) $$

자세히 보면, SVD꼴인 $E=U\Sigma V^T$와 닮았다. (두 개의 singular value인 것도 비슷함)

따라서 다음과 같이 $E$를 factorization할 수 있다.

$$ [t]_\times=UZU^T,\quad\quad R=UWV^T\,\text{or}\,\,\,UW^TV^T $$

(위와 같은 factorization만이 가능함이 가능하고 타당함을 증명할 수 있지만 생략)

이런 $E$의 factorization은 행렬 $UWV^T$와 $UW^TV^T$가 orthogonal할 때만 보장된다.

그리고 이 $R$ 행렬이 타당한 회전행렬임을 확인하기 위해선, $R$의 determinant가 양수임을 보이기만 하면 된다.

$$ R=(\det{UWV^T})UWV^T\,\text{or}\,\,\,(\det{UW^TV^T})UW^TV^T $$

회전 행렬 $R$과 마찬가지로, 평행이동 벡터 $t$도 여러 개가 있을 수 있다.

Cross product의 정의에 따라,

$$ t\times t=[t]_\times t=UZU^Tt=0 $$

이며, $U$는 unitary하므로 $\|[t]_\times\|_F=\sqrt{2}$ 이다.

따라서, $E$는 up to scale인 것과 위의 방정식으로부터 이 factorization에서 $t$의 추정치는 다음과 같다.

$$ t=\pm U\begin{bmatrix}0\\0\\1\end{bmatrix}=\pm u_3 $$

($u_3$는 $U$의 마지막 column)

뿐만 아니라 $[t]_\times=UZU^T$를 이용해도 똑같은 결과를 얻을 수 있다.

위 그림처럼 4가지 가능한 $R,t$쌍이 있다. ($R,t$각각 2개의 경우의 수가 있으므로)

그러므로 이상적인 조건 하에서, 단 하나의 점만 있으면 정확한 $R,t$쌍을 찾을 수 있다.

올바른 $R,t$ 쌍에서, triangulated point $\hat{P}$는 두 카메라의 앞에 있어야 하고, 이는 이 점이 두 카메라 좌표계에서 $z$축으로 양의 값을 가짐을 의미한다.

Measurement noise로 인해 보통 하나의 점에 의존하지는 않고, 여러 점으로 triangulate를 진행하여 대부분의 점들이 카메라들의 앞쪽에 있도록 하는 올바른 $R,t$ 쌍을 찾는다.  

 

An example structure from motion pipeline

Motion 행렬 $M_i$를 찾고 나면, 이걸 이용해서 월드 좌표계의 점 $X_j$를 결정할 수 있다.

대수적 접근의 경우, 그런 점들의 추정치는 perspective transformation $H$에 upto scale하다.

Essential matrix로부터 카메라 행렬을 추출해낼 때, 이 추저이는 up to scale하다.

두 경우 모두 3D 점들은 앞에서 다뤘던 triangulatio method를 이용해 추정된 카메라 행렬에 의해 계산된다.

Multi-view로의 확장은 여러 카메라를 연결하여 수행할 수 있다.

어떤 카메라의 pair이던간에 충분한 대응점이 있다면, 앞서 다뤘던 대수적 접근법이나 essential matrix를 이용해 계산해낼 수 있다.

이렇게 reconstructed된 3D 점들은 카메라 쌍에서 사용가능한 포인트 대응에 연관이 된다.

이러한 pairwise solutions들은 bundle adjustment라는 기법을 통해 최적화될 수 있다.  

 

Bundle adjustment

이전 방법들의 경우 한계점이 있었다.

Factorization의 경우 모든 점들이 모든 image에서 보인다는 가정을 했었다.

하지만 실제로는 대응점을 찾기가 어렵거나 안 보일 때가 많다.

따라서, 대수적 접근이 카메라들을 연결하여 결합한 solution을 만들수는 있지만, 모든 카메라와 3D 점들을 사용한 일관되고 최적화된 reconstruction은 풀 수가 없다.  

 

이런 문제점을 해결하기 위해 nonlinear method인 bundle adjustment를 알아보자.

최적화에서는, estimated된 카메라로의 reconstructed point의 projection과 대응하는 observation사이의 pixel 거리인 reprojection error를 줄이는 것이 목표이다.

앞서 triangulation에서 다뤘던 nonlinear optimization에서는 두 개의 카메라의 경우를 가정했었고, 또 모든 대응점이 각 카메라에서 보인다고 가정했었다.

Bundle adjustment는 여러 개의 camera를 다루지만, 각 카메라에서 보이는 observation에 대해서만 reprojection error를 계산하므로, 앞서 배운 triangulation에서의 nonlinear method와 상당히 유사하다.  

 

이런 bundle adjustment를 풀기위한 대표적인 방법으로 Gauss-Newton 알고리즘과 Levenberg-Marquardt 알고리즘이 있다.

Bundle adjustment는 많은 수의 view에 대해서도 쉽게 처리를 할 수 있고, 모든 이미지에서 관찰되지 않은(일부 이미지에서만 해당 점이 관찰됨) 경우일지라도 처리를 할 수 있다.

하지만 view의 수가 많아질수록 파라미터의 수가 늘어나고, nonlinear optimization technique에 의존하므로 초기 조건이 매우 중요할 수 있다.

따라서, bundle adjustment는 보통 SFM의 마지막 단계에서 구현이 된다.

즉, factorization이나 algebraic approach를 이용해 합리적인 초기해를 구해 놓고, bundle adjustment를 진행하는 것이다.

 

 

더 자세한 factorization과 nonlinear method와 구현코드가 궁금하다면 

https://github.com/ianpark318/CS231A/blob/main/ps2/ps2_code/PSET2.ipynb 참고