CH04. Stereo Systems (2)

Perspective structure from motion

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

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

$$M_i=\left[\begin{array}{cccc}{a}_{11}& a_{12}& a_{13}& b_1\\ a_{21}& a_{22}& a_{23}& b_2\\ a_{31}& a_{32}& a_{33}& 1\end{array}\right]$$

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

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

(motion matrix에는 $4\times 4$ 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\times 4$ 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_1{H}^{-1}$을 canonical하다고 잡을 수 있다.

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

$$M_1{H}^{-1}=\left[\begin{array}{cc}I& 0\end{array}\right]M_2{H}^{-1}=\left[\begin{array}{cc}A& b\end{array}\right]$$

일단 이 문제를 해결하기 위해서는 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 }$은 다음과 같이 변환된다.

$$\begin{gathered} p=M_{1}P=M_1{H}^{-1}HP=\left[\begin{array}{cc}I& 0\end{array}\right]\tilde{P} \\ {p}^{\prime }=M_{2}P=M_2{H}^{-1}HP=\left[\begin{array}{cc}A& b\end{array}\right]\tilde{P} \end{gathered}$$

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

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

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

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

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

따라서,

$$\begin{array}{rl}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{array}$$

이 성립한다. 그런데 마지막 식의 꼴을 보면 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를 이용해 $\Vert b\Vert =1$일 때 $Fb=0$의 least square solution을 구하는 것이다.

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

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

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

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

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

$$\widetilde{M_1}=\left[\begin{array}{cc}I& 0\end{array}\right]\widetilde{M_2}=\left[\begin{array}{cc}-[b_{\times }]F& b\end{array}\right]$$

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

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

Epipole 또한 $F{e}_2=0$ 과 $F^T{e}_1=0$ 과 같은 식을 만족했다.

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

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

$$\widetilde{M_1}=\left[\begin{array}{cc}I& 0\end{array}\right]\widetilde{M_2}=\left[\begin{array}{cc}-[e_{\times }]F& e\end{array}\right]$$  

 

Determining motion from the Essential matrix

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

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

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

$$E=K^{T}FK$$

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=\left[\begin{array}{ccc}0& -1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right],Z=\left[\begin{array}{ccc}0& 1& 0\\ -1& 0& 0\\ 0& 0& 0\end{array}\right]$$

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

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

 

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

$$[t{]}_{\times }=UZ{U}^T$$

($U$는 orthogonal matrix임)

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

$$E=U\text{diag}(1,1,0)(W{U}^{T}R)$$

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

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

$$[t{]}_{\times }=UZ{U}^T,R=UW{V}^T\text{or}U{W}^T{V}^T$$

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

이런 $E$의 factorization은 행렬 $UW{V}^T$와 $U{W}^T{V}^T$가 orthogonal할 때만 보장된다.

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

$$R=(detUW{V}^T)UW{V}^T\text{or}(detU{W}^T{V}^T)U{W}^T{V}^T$$

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

Cross product의 정의에 따라,

$$t\times t=[t{]}_{\times }t=UZ{U}^{T}t=0$$

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

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

$$t=\pm U\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]=\pm u_3$$

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

뿐만 아니라 $[t{]}_{\times }=UZ{U}^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 참고