6.151 다시점 기하학과 삼각 측량

다시점 기하학(multi-view geometry)은 여러 대의 카메라 또는 한 대의 카메라가 다른 위치에서 촬영한 이미지들로부터 3차원 장면의 구조를 복원하는 기하학적 원리를 다루는 분야이다. 삼각 측량(triangulation)은 두 개 이상의 이미지에서 관측된 점 대응으로부터 3차원 점의 위치를 계산하는 핵심 연산이다. 본 절에서는 삼각 측량의 선형대수학적 정식화와 다시점 기하학의 주요 개념을 체계적으로 다룬다.

1. 삼각 측량의 기본 원리

두 카메라의 투영 행렬이 $P_1$ , $P_2$ 이고, 3차원 점 $\mathbf{P}$ 가 각각의 이미지에 $\tilde{\mathbf{p}}_1$ , $\tilde{\mathbf{p}}_2$ 로 투영된다고 하자. 투영 관계는 다음과 같다.

$\lambda_1 \tilde{\mathbf{p}}_1 = P_1 \tilde{\mathbf{P}}, \quad \lambda_2 \tilde{\mathbf{p}}_2 = P_2 \tilde{\mathbf{P}}$

여기서 $\tilde{\mathbf{P}} = [X, Y, Z, 1]^\top$ 은 동차 좌표이고, $\lambda_1, \lambda_2$ 는 깊이에 해당하는 스케일 인수이다. 이상적인 경우 두 광선은 정확히 한 점에서 교차하지만, 측정 잡음과 카메라 파라미터 오차로 인해 실제로는 교차하지 않는 것이 일반적이다. 따라서 삼각 측량은 과결정 시스템의 최적 해를 구하는 문제로 정식화된다.

2. 선형 삼각 측량: DLT 방법

스케일 인수를 제거하기 위해 외적을 이용한다. $\tilde{\mathbf{p}}_i \times (P_i \tilde{\mathbf{P}}) = \mathbf{0}$ 으로부터 다음의 방정식을 얻는다.

$\tilde{\mathbf{p}}_i \times (P_i \tilde{\mathbf{P}}) = \mathbf{0}$

$\tilde{\mathbf{p}}_i = [u_i, v_i, 1]^\top$ 이고 $P_i$ 의 행을 $\mathbf{p}_i^{j\top}$ ( $j = 1, 2, 3$ )으로 표기하면, 외적을 전개하여 다음의 세 방정식을 얻는다.

$u_i (\mathbf{p}_i^{3\top} \tilde{\mathbf{P}}) - (\mathbf{p}_i^{1\top} \tilde{\mathbf{P}}) = 0$

$v_i (\mathbf{p}_i^{3\top} \tilde{\mathbf{P}}) - (\mathbf{p}_i^{2\top} \tilde{\mathbf{P}}) = 0$

$u_i (\mathbf{p}_i^{2\top} \tilde{\mathbf{P}}) - v_i (\mathbf{p}_i^{1\top} \tilde{\mathbf{P}}) = 0$

세 번째 방정식은 처음 두 방정식의 선형 결합이므로, 각 이미지에서 2개의 독립 방정식이 생성된다. 두 이미지로부터 $4 \times 4$ 행렬 $A$ 를 구성한다.

$A = \begin{bmatrix} u_1 \mathbf{p}_1^{3\top} - \mathbf{p}_1^{1\top} \\ v_1 \mathbf{p}_1^{3\top} - \mathbf{p}_1^{2\top} \\ u_2 \mathbf{p}_2^{3\top} - \mathbf{p}_2^{1\top} \\ v_2 \mathbf{p}_2^{3\top} - \mathbf{p}_2^{2\top} \end{bmatrix}$

선형 삼각 측량 문제는 다음과 같다.

$A \tilde{\mathbf{P}} = \mathbf{0}$

$\lVert \tilde{\mathbf{P}} \rVert = 1$ 조건 하에서 $\lVert A \tilde{\mathbf{P}} \rVert$ 를 최소화하는 해는 $A$ 의 SVD에서 최소 특이값에 대응하는 오른쪽 특이 벡터이다.

$A = U \Sigma V^\top$

$\tilde{\mathbf{P}}$ 는 $V$ 의 마지막 열이며, 비동차 좌표로 변환하면 다음과 같다.

$\mathbf{P} = \frac{1}{\tilde{P}_4} \begin{bmatrix} \tilde{P}_1 \\ \tilde{P}_2 \\ \tilde{P}_3 \end{bmatrix}$

3. 다시점 삼각 측량

$M$ 개의 카메라에서 동일한 3차원 점이 관측된 경우, 각 카메라로부터 2개의 방정식을 얻어 $2M \times 4$ 행렬 $A$ 를 구성한다.

$A = \begin{bmatrix} u_1 \mathbf{p}_1^{3\top} - \mathbf{p}_1^{1\top} \\ v_1 \mathbf{p}_1^{3\top} - \mathbf{p}_1^{2\top} \\ \vdots \\ u_M \mathbf{p}_M^{3\top} - \mathbf{p}_M^{1\top} \\ v_M \mathbf{p}_M^{3\top} - \mathbf{p}_M^{2\top} \end{bmatrix} \in \mathbb{R}^{2M \times 4}$

$M \geq 2$ 이면 과결정 시스템이 되어, 잡음 평균화 효과에 의해 단일 이미지 쌍보다 정확한 3차원 점 복원이 가능하다.

4. 최적 삼각 측량

DLT 방법은 대수적 오차(algebraic error)를 최소화하므로, 기하학적으로 최적이지 않다. 기하학적으로 의미 있는 비용 함수는 재투영 오차(reprojection error)이다.

$\hat{\mathbf{P}} = \arg\min_{\mathbf{P}} \sum_{i=1}^{M} \lVert \tilde{\mathbf{p}}_i - \pi(P_i, \mathbf{P}) \rVert^2$

여기서 $\pi(P_i, \mathbf{P})$ 는 투영 함수로, $\mathbf{P}$ 를 $i$ 번째 카메라로 투영한 픽셀 좌표이다.

$\pi(P_i, \mathbf{P}) = \frac{1}{(P_i \tilde{\mathbf{P}})_3} \begin{bmatrix} (P_i \tilde{\mathbf{P}})_1 \\ (P_i \tilde{\mathbf{P}})_2 \end{bmatrix}$

이 비용 함수는 비선형이므로, 가우스-뉴턴 또는 레벤버그-마쿼트 알고리즘으로 반복적으로 최소화한다. DLT의 해를 초기값으로 사용한다.

5. 두 시점에서의 최적 삼각 측량

Hartley와 Sturm이 제안한 두 시점에서의 최적 삼각 측량 방법은 다음과 같은 비용 함수를 최소화한다.

$\min_{\hat{\mathbf{p}}_1, \hat{\mathbf{p}}_2} \lVert \tilde{\mathbf{p}}_1 - \hat{\tilde{\mathbf{p}}}_1 \rVert^2 + \lVert \tilde{\mathbf{p}}_2 - \hat{\tilde{\mathbf{p}}}_2 \rVert^2 \quad \text{subject to} \quad \hat{\tilde{\mathbf{p}}}_2^\top F \hat{\tilde{\mathbf{p}}}_1 = 0$

이는 에피폴라 제약을 만족하면서 관측 점에 가장 가까운 보정 점 쌍 $(\hat{\tilde{\mathbf{p}}}_1, \hat{\tilde{\mathbf{p}}}_2)$ 을 찾는 문제이다. 이 문제는 6차 다항식의 근을 구하는 것으로 귀결되며, 닫힌 형태의 최적 해가 존재한다.

6. 삼각 측량의 기하학적 해석

삼각 측량은 기하학적으로 두 광선 사이의 최근접점(closest point)을 구하는 문제이다. 첫 번째 카메라의 광선은 다음과 같다.

$\mathbf{r}_1(\lambda) = \mathbf{C}_1 + \lambda \mathbf{d}_1$

두 번째 카메라의 광선은 다음과 같다.

$\mathbf{r}_2(\mu) = \mathbf{C}_2 + \mu \mathbf{d}_2$

여기서 $\mathbf{C}_i$ 는 카메라 중심, $\mathbf{d}_i = M_i^{-1} \tilde{\mathbf{p}}_i$ 는 광선 방향이다. 두 광선 사이의 거리를 최소화하는 $\lambda$ , $\mu$ 를 구하면, 최근접점의 중점을 3차원 점의 추정치로 사용한다.

$\min_{\lambda, \mu} \lVert \mathbf{r}_1(\lambda) - \mathbf{r}_2(\mu) \rVert^2$

이를 $\lambda$ 와 $\mu$ 에 대하여 미분하면 $2 \times 2$ 선형 시스템이 얻어진다.

$\begin{bmatrix} \mathbf{d}_1^\top \mathbf{d}_1 & -\mathbf{d}_1^\top \mathbf{d}_2 \\ \mathbf{d}_1^\top \mathbf{d}_2 & -\mathbf{d}_2^\top \mathbf{d}_2 \end{bmatrix} \begin{bmatrix} \lambda \\ \mu \end{bmatrix} = \begin{bmatrix} \mathbf{d}_1^\top (\mathbf{C}_2 - \mathbf{C}_1) \\ \mathbf{d}_2^\top (\mathbf{C}_2 - \mathbf{C}_1) \end{bmatrix}$

7. 삼각 측량의 불확실성

삼각 측량의 정밀도는 기선 길이(baseline length)와 교차 각도(intersection angle)에 강하게 의존한다. 깊이 추정의 불확실성은 다음과 같이 근사된다.

$\sigma_Z \approx \frac{Z^2}{f \cdot b} \sigma_p$

여기서 $Z$ 는 깊이, $f$ 는 초점 거리, $b$ 는 기선 길이, $\sigma_p$ 는 이미지 점의 측정 불확실성이다. 이 관계에서 다음의 특성이 관찰된다.

깊이 불확실성은 $Z^2$ 에 비례하여 증가한다.
기선 길이 $b$ 가 길수록 정밀도가 향상된다.
기선이 매우 짧으면(두 광선이 거의 평행하면) 삼각 측량이 수치적으로 불안정해진다.

8. 삼점 텐서(Trifocal Tensor)

세 이미지 사이의 기하학적 관계는 삼점 텐서(trifocal tensor) $\mathcal{T}$ 로 기술된다. 삼점 텐서는 $3 \times 3 \times 3$ 텐서로, $27$ 개의 요소를 가지지만 독립적인 자유도는 $18$ 이다(스케일 자유도와 내부 제약에 의해).

세 이미지의 투영 행렬이 $P_1 = [I \vert \mathbf{0}]$ , $P_2 = [A \vert \mathbf{a}_4]$ , $P_3 = [B \vert \mathbf{b}_4]$ 일 때, 삼점 텐서의 성분은 다음과 같다.

$\mathcal{T}_i^{jk} = a_i^j b_4^k - a_4^j b_i^k$

여기서 $a_i^j$ 는 $A$ 의 $(j, i)$ 성분, $\mathbf{a}_4$ , $\mathbf{b}_4$ 는 각 투영 행렬의 마지막 열이다.

삼점 텐서를 이용하면 세 이미지에 걸친 점, 선 대응에 대한 제약 조건을 표현할 수 있다. 점-점-점 대응의 경우 다음이 성립한다.

$[\tilde{\mathbf{p}}_2]_\times \left( \sum_{i=1}^{3} p_{3}^{(i)} \mathcal{T}_i \right) [\tilde{\mathbf{p}}_1]_\times = \mathbf{0}_{3 \times 3}$

여기서 $\mathcal{T}_i \in \mathbb{R}^{3 \times 3}$ 는 삼점 텐서의 $i$ 번째 슬라이스이고, $p_3^{(i)}$ 는 $\tilde{\mathbf{p}}_3$ 의 $i$ 번째 성분이다.

9. 번들 조정

다시점 기하학에서 카메라 파라미터와 3차원 점 위치를 동시에 정밀화하는 과정이 번들 조정(bundle adjustment)이다. 비용 함수는 다음과 같다.

$\min_{\{P_i\}, \{\mathbf{P}_j\}} \sum_{i=1}^{M} \sum_{j \in \mathcal{V}_i} \lVert \tilde{\mathbf{p}}_{ij} - \pi(P_i, \mathbf{P}_j) \rVert^2$

여기서 $\mathcal{V}_i$ 는 $i$ 번째 카메라에서 관측 가능한 3차원 점의 집합이다. 이 비선형 최소 제곱 문제의 야코비 행렬 $J$ 는 희소(sparse) 구조를 가진다. 정규 방정식의 정보 행렬은 다음과 같이 분할된다.

$J^\top J = \begin{bmatrix} U & W \\ W^\top & V \end{bmatrix}$

여기서 $U$ 는 카메라 파라미터에 대한 블록 대각 부분, $V$ 는 3차원 점에 대한 블록 대각 부분, $W$ 는 교차 항이다. 슈어 보해(Schur complement)를 이용하면 카메라 파라미터에 대한 축소된 시스템을 효율적으로 풀 수 있다.

$(U - W V^{-1} W^\top) \delta \mathbf{c} = \boldsymbol{\epsilon}_c - W V^{-1} \boldsymbol{\epsilon}_p$

$V$ 가 블록 대각이므로 $V^{-1}$ 의 계산이 매우 효율적이며, 축소된 시스템의 크기는 카메라 파라미터의 수에만 의존한다.

참고 문헌

Hartley, R., & Zisserman, A. (2004). Multiple View Geometry in Computer Vision (2nd ed.). Cambridge University Press.
Hartley, R. I., & Sturm, P. (1997). Triangulation. Computer Vision and Image Understanding, 68(2), 146-157.
Triggs, B., McLauchlan, P. F., Hartley, R. I., & Fitzgibbon, A. W. (2000). Bundle Adjustment – A Modern Synthesis. In Vision Algorithms: Theory and Practice (pp. 298-372). Springer.
Ma, Y., Soatto, S., Kosecka, J., & Sastry, S. S. (2004). An Invitation to 3-D Vision. Springer.

v 0.1