Why is stereo(multi-view) useful?

  • Calibration rig를 통해: 리그의 위치와 모양, K를 알 수 있음
  • 무한점과 무한선을 통해 그리고 직교선과 직교평면을 통해: 공간의 구조와 K를 알 수 있음
  • 그러나….3차원에서 2차원으로 갔기 때문에, 이미지 1장은 필연적으로 정보를 잃는다.

  • 사람은 왜 입체를 구분하는가? 눈이 2개이기 때문. 왼쪽 시선과 오른쪽 시선의 외적값이 교점이 되고, 이 교점을 제대로 인식할 수 있다. 1

  • Triangulation: Find $P^*$ that minimizes $d(p, MP^*)+d(p’, M’P^*)$
  • Multi(stereo)-view geomery
    • Camera geometry: 두 이미지의 대응되는 점에 대해, 카메라 행렬 또는 위치, 포즈를 찾아라
    • Scene geometry: 3차원 점이 2차원 이미지 2개 이상에 투영될 때, 3차원 점의 좌표를 찾아라
    • 상관관계: 한 점이 1번 이미지에 있을 때, 그 점이 2번 이미지 어느 위치에 있는가?

Epipolar geometry

In general

2

  • Epipolar geometry: 카메라와, 3차원의 점과, 대응되는 관찰을 엮는 기하학
  • Epipolar geometry의 구성: epipolar plane, baseline, epipolar lines, epipoles. 두 카메라가 같은 점 P를 관찰하고 있다고 가정하자.
  • Epipolra plane: $PO_1O_2$ 세 점으로 이뤄진 평면. Gray region above.
  • Baseline: $\overline{O_1O_2}$. Orange line above.
  • Epipolar lines: Intersection of epipolar plane and img planes. 2 blue lines above.
  • Epipoles: Intersection of baseline with img planes, or projections of the other camera center

When two img planes are parallel

3

  • Epipoles locate at infinity
  • Epipolar lines are parallel to an axis of each image plane( $u$ axis above)
  • Used in image rectification

Forward translation

4

  • 각 이미지에서 epipole의 위치가 같아짐
  • 이 경우 epipole을 FoE라고 부름(Focus of Expansion)

Epipolar constraints, Essential and Fundamental Matrix

  • 현실에선 보통 $P$의 위치는 알 수 없음. 그러나, 두 카메라의 위치, 방향, 카메라 행렬 등은 알 수 있음. 또 한 이미지에서의 투영된 $P$의 위치 $p$는 알 수 있음.
  • 에피폴라 기하학을 활용하면 다른 이미지에서의 투영된 점 위치도 알 수 있음. 에피폴라 평면을 알기 때문에 에피폴라 선들도 알 수 있고, 그 위에서 추정하면 되기 때문. 3D 구조를 자세하게 알지 않고도 가능
  • 필요한 셋업:
    • $M, M’$: 점이 각 이미지 평면에 투영되는 카메라 행렬
    • $O_1$에서 $O_2$로 회전 및 평행이동으로 이동하는 행렬들을 $R, T$라고 하고 $M=K[I,0]$이라 하면, $M’=K’[R^\top, -R^\top T]$
    • 왜? rotation 행렬은 역행렬=transpose이므로 다음 행렬의 역행렬을 계산해보면 유도할 수 있다.

    \(\begin{bmatrix}R&T\\0&1\end{bmatrix}\)

Essential matrix

  • 넘어가기 전, 다음 새로운 외적의 표기를 짚고 넘어가자.

\( \mathbf{a}\times\mathbf{b}=\begin{bmatrix}0&-\mathbf{a}_z&\mathbf{a}_y\\ \mathbf{a}_z&0&-\mathbf{a}_x \\ -\mathbf{a}_y&\mathbf{a}_x&0\end{bmatrix}\begin{bmatrix}\mathbf{b}_x\\ \mathbf{b}_y\\ \mathbf{b}_z\end{bmatrix}=[\mathbf{a}_\times]\mathbf{b} \)

  • $K=K’=I=K_\text{canonical camera}$인 경우를 가정하자. $M, M’$식이 간단해진다.
  • 이 경우 $O_1$ 카메라 좌표계에서 $p’$의 위치는 $Rp’+T$
  • epipolar plane의 법선벡터는 $T\times(Rp’+T)=T\times(Rp’)$
  • 즉 epipolar plane 위 점 p는 다음 식을 만족한다

\(p^\top\cdot[T\times(Rp’)]=p^\top[T_\times]Rp’=0\)

  • $E:=[T_\times]R$을 Essential Matrix라고 한다. 즉 $p^\top E p’=0$이고 이를 epipolar constraint라고 함. 다음과 같은 성질을 가진다.
    • rank가 2인 singular matrix이며, DoF가 5이다.
    • $I=Ep’$은 $p’$의 epipolar line, $I’=E^\top p$은 $p$의 epipolar line($\because$ epipolar constraint)
    • $Ee’=0$, $E^\top e=0$

Fundamental matrix

  • 카메라가 canonical하지 않다고 가정하자. 카메라가 canonical한 경우로 투영한 좌표를 각각 $p_c=K^{-1}p$, $p’_c=K’^{-1}p’$이라고 하면 다음 식이 성립한다.

\(p_c^\top[T_\times]Rp’_c=p^\top (K^{-1})^\top[T_{\times}]RK’^{-1}p’=0\)

  • 이 때 $F=(K^{-1})^\top[T_\times]RK’^{-1}$을 Fundamental Matrix라 한다. 다음 특징이 있다.
    • rank 2인 singular matrix며, DoF가 7이다.
    • epipolar line과 epipole이 위와 똑같은 조건을 만족한다.
    • 카메라 행렬과 회전, 평행이동 행렬을 몰라도 $E$만 안다면 epipolar line을 계산할 수 있다.
  • 실제 3차원 상의 점의 위치를 몰라도 한 이미지 위에 투영된 위치를 안다면, 다른 이미지에 투영된 위치를 알 수 있다. 3D 공간을 재구축할 필요가 없다.
  • 따라서 3D 재구축과 다시점 사물 매칭에 쓰인다.

Estimating F

The Eight-Point Algorithm

  • 근데 fundamental matrix만 있으면 다 해결된단 말도 좀 빡세보인다. 양 이미지에서 8점의 위치를 알면, 카메라 성분 분석 없이 fundamental matrix를 계산할 수 있다.
  • $p_i=(u_i, v_i, 1), p’_i=(u’_i, v’_i, 1)$이라고 하자. epipolar constraint에 의해 다음이 성립한다:

\( \begin{bmatrix}u_i u’_i&v_i v’_i&u_i&u’_i v_i&v_i v’_i&v_i&u’_i&v’_i&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 \)

  • 단 하나의 스칼라 식이므로, 위 식에 의한 fundamental matrix의 DoF는 8이다. 즉 식을 8개로 늘린 행렬 꼴 $W\mathbf{f}=0$으로 쓸 수 있다.
  • 실전에서는 측정이 정확하지 않으므로 8개 이상의 점을 쓰고, 이 경우 답이 trivial해질 수 있으므로 저번과 같이 SVD를 사용해서 크기가 1인 $\hat{\mathbf{f}}=\hat{F}$를 구한다. 그런데 이 행렬이 full rank일 수가 있다. fundamental matrix는 rank가 2인데?
  • 다음 식을 풀어서 해결한다.

\( \underset{\det F=0}{\text{minimize}}||F-\hat{F}||_{\text{Frobenius}} \)

  • SVD를 다시 한 번 더 사용하여 추정치 행렬 $\hat{F}=U\Sigma V^\top$의 rank-2 approximation을 구할 수 있다

\(F=U\begin{bmatrix}\Sigma_1&0&0\\0&\Sigma_2&0\\0&0&0\end{bmatrix}V^\top\)

The Normalized Eight-Point Algorithm

  • 기존 8포인트 알고리즘의 문제점:
    • 조건이 잘 설정되지 않고 극히 비대칭이다
    • W의 값들이 비슷한 크기를 가져야한다.
    • SVD 분해 과정에서 문제를 일으킨다. 잘 작동되려면 singular value 하나가 0에 가깝고 나머지가 nonzero여야 한다.
    • 실전에서, 점과 epipolar line 사이의 거리가 엄청 크다거나 해서 에러가 클 수 있다.

  • 아이디어: 이미지 좌표를 변환하여 $W$의 값들이 잘 설정되도록 한다(pre-conditioning) 5

  • translation+scaling을 통해 다음 두 조건을 만족하게 한다.
    • 원점이 이미지 포인트들 중 중앙쯤에 있는 놈이 되게 한다.
    • 이미지 포인트들의 원점으로부터의 평균 제곱거리가 2픽셀 안쪽이 되도록 한다.
  • Normalized 8-point algorithm을 하나로 정리하면 다음과 같다.
    1. 각 이미지에 대해 normalized map인 $T, T’$을 계산 (scaling factor=($\frac{2N}{\sum||x_i-\bar{x}||^2})^{1/2}$)
    2. Normalize $p_i, p’_i$: $q_i=Tp_i, q’_i=T’p’_i$
    3. 8점 알고리즘을 통해 $\hat{F}_q$ 계산
    4. rank 2 제약을 걸어 $F_q$도 계산
    5. De-normalize $F_q$: $F=T^\top F_q T’$

Examples

Image rectification

  • 두 이미지가 평행한 상황을 생각해보자. 이 경우 두 카메라 사이에 회전이 없으며, 같은 카메라를 사용하고 x축 translation만 존재한다고 가정할 수 있다. 즉,

\(E=[T_\times]R=\begin{bmatrix}0&0&0\\0&0&-T_x\\0&-T_x&0\end{bmatrix}\)

  • 이렇게 얻은 essential matrix로 epipolar line을 계산해보면 수평하다는 것을 알 수 있다.
  • 추가로, epipolar constraint를 계산하면 $v=v’$이라는 매우 간단한 constraint를 얻을 수 있다.
  • Rectification이란 이런 이점을 얻기 위해 이미지 2개를 평행하게 만드는 작업이다.
    • Epipolar constraint가 단순해진다
    • 선형 보간을 통해 새로운 시점을 합성할 수 있다. 6
  • Rectification 하는 방법
    • normalized 8점 알고리즘으로 fundamental matrix를 계산한다
    • epipole을 계산한다. 현실에서는 epipolar line이 noisy하므로, 여러 epipolar line을 행렬로 만들어 SVD를 통해 계산한다.
    • 이 epipole을 points at infinity로 보내는 $H$를 찾는다.
      • $e’$에 대한 맵 $H_2$는 평행이동, 회전, 계수추가행렬의 합성으로 만들어진다.
      • $e$에 대한 맵 $H_1$은 최적화 문제를 풀어서 구할 수 있는데, 대략 $H_A$란 행렬과 $H_2$와 $M$의 곱으로 이루어진다. 이걸 풀기 위해서 또 최적화 문제를 풀면, rectification을 수행할 수 있다.

Application

  • View morphing(1996)
  • Deep View Morphing(2017)