에피폴라 기하

1. 개요[편집]

왼쪽 사진의 이 점이 오른쪽 사진 어디에 있을까? 온 화면을 뒤질 필요 없다. 선 하나만 보면 된다.

에피폴라 기하(epipolar geometry)는 같은 장면을 서로 다른 두 시점에서 찍었을 때, 장면의 3차원 구조와 무관하게 오직 두 카메라의 상대적 배치와 내부 파라미터만으로 결정되는 두 영상 사이의 사영기하학적 구속 관계다. 이 구속은 3×3 행렬 하나로 압축되며, 비보정 카메라에서는 기초행렬(fundamental matrix) $F$, 보정된 카메라에서는 본질행렬(essential matrix) $E$ 라고 부른다.¹

실용적 가치는 한 문장으로 요약된다. 2차원 탐색이 1차원 탐색으로 줄어든다. 대응점 후보가 영상 전체($O(N^2)$ 화소)에서 직선 위($O(N)$ 화소)로 줄어드니 계산량도, 오대응 확률도 함께 줄어든다. 스테레오·SfM·시각 SLAM이 전부 이 한 줄의 절약 위에 서 있다.

2. 구속의 기하 — 코플래너리 한 줄[편집]

3D 점 $\mathbf X$, 첫 번째 카메라 중심 $\mathbf C$, 두 번째 카메라 중심 $\mathbf C'$ 세 점은 언제나 한 평면 위에 있다. 이 평면을 에피폴라 평면이라 한다. 그러면 자동으로 따라오는 이름들:

• 기선(baseline) — 두 카메라 중심을 잇는 직선.
• 에피폴(epipole) $\mathbf e,\mathbf e'$ — 기선이 각 영상면과 만나는 점. 즉 한 카메라에 비친 다른 카메라의 상이다. 두 카메라가 서로를 정면으로 보고 있으면 에피폴이 영상 한가운데에 오고, 광축이 평행하면 무한원으로 달아난다.
• 에피폴라 선 — 에피폴라 평면과 영상면의 교선. 한 영상의 모든 에피폴라 선은 반드시 그 영상의 에피폴에서 만난다(선다발, pencil).

정규화 좌표(내부행렬을 이미 나눈 좌표)에서 두 번째 카메라가 첫 번째에 대해 $(R,\mathbf t)$ 만큼 놓여 있다면, 세 벡터 $\mathbf t$, $R\hat{\mathbf x}$, $\hat{\mathbf x}'$ 가 공면이라는 조건이 바로

$$\hat{\mathbf x}'^{\mathsf T}\,[\mathbf t]_\times R\,\hat{\mathbf x} \;=\; 0 \qquad\Longrightarrow\qquad E = [\mathbf t]_\times R$$

이다. 여기서 $[\mathbf t]_\times$ 는 외적을 행렬로 쓴 반대칭행렬. 픽셀좌표로 되돌리면 $\hat{\mathbf x}=K^{-1}\mathbf x$ 이므로

$$\mathbf x'^{\mathsf T} F\,\mathbf x = 0, \qquad F = K'^{-\mathsf T} E\, K^{-1}, \qquad E = K'^{\mathsf T} F K$$

가 된다. 에피폴라 구속은 이 한 줄, $\mathbf x'^{\mathsf T}F\mathbf x=0$ 이다.

여기서 결정적인 관찰. $\mathbf l' = F\mathbf x$ 는 두 번째 영상에서의 직선이고, 대응점 $\mathbf x'$ 는 반드시 그 위에 있어야 한다. 반대 방향은 $\mathbf l = F^{\mathsf T}\mathbf x'$. 그리고 $F\mathbf e = \mathbf 0$, $F^{\mathsf T}\mathbf e' = \mathbf 0$ — 에피폴은 $F$ 의 우/좌 영벡터다.

구속은 필요조건일 뿐 충분조건이 아니다. 에피폴라 선 위에 있다고 대응점인 것은 아니다. 그 선 위 어딘가에 있다는 것만 보장하고, 깊이가 어디인지는 아무것도 말해 주지 않는다. 에피폴라 기하는 매칭기가 아니라 탐색 공간 축소기다.

3. F와 E — 자유도 세어 보기[편집]

	기초행렬 $F$	본질행렬 $E$
전제	내부 파라미터 모름	$K,K'$ 를 안다(보정됨)
크기	3×3, rank 2	3×3, rank 2
자유도	7	5
특이값	$(\sigma_1,\sigma_2,0)$, 둘은 자유	$(\sigma,\sigma,0)$, 둘이 같아야 함
최소표본	7점(또는 선형 8점)	5점
복원 가능한 것	사영 복원까지	스케일 뺀 유클리드 복원

$F$ 의 자유도는 원소 9개에서 전체 배율 1과 $\det F=0$ 이라는 제약 1을 빼서 7이다. $E$ 는 회전 3 + 이동 3 − 배율 1 = 5. 이 「2 차이」가 실전에서 크다. RANSAC의 반복 횟수는 최소표본 크기의 지수함수이므로, 카메라를 미리 보정해 두면 오염된 매칭에서 살아남을 확률 자체가 달라진다.

$E$ 의 특이값 두 개가 같아야 한다는 조건은 등가적으로

$$2\,E E^{\mathsf T}E - \operatorname{tr}(E E^{\mathsf T})\,E = \mathbf 0$$

로 쓸 수 있고, 이 아홉 개의 3차식이 5점 알고리즘의 재료가 된다.

4. 8점 알고리즘과 한나 정규화[편집]

$\mathbf x'^{\mathsf T}F\mathbf x=0$ 은 $F$ 의 9개 원소에 대해 선형이다. 대응점 하나가 방정식 하나를 주므로 8개면 배율을 뺀 해가 정해진다. 이것이 롱게-히긴스(1981)의 8점 알고리즘이다.

1. 각 대응에서 $(x'x,\;x'y,\;x',\;y'x,\;y'y,\;y',\;x,\;y,\;1)$ 행을 쌓아 $A\mathbf f=\mathbf 0$ 을 만든다.
2. 특이값 분해로 $A$ 의 최소 특이값에 대응하는 우특이벡터를 취해 $F_{\text{raw}}$ 를 만든다.
3. rank 2 를 강제한다. $F_{\text{raw}}=U\,\mathrm{diag}(\sigma_1,\sigma_2,\sigma_3)\,V^{\mathsf T}$ 에서 $\sigma_3$ 을 0으로 만들고 다시 곱한다. 에카르트-영 정리에 의해 이것이 프로베니우스 노름 기준 가장 가까운 rank 2 행렬이다.

3단계를 빠뜨리면 $\det F\neq0$ 이라 에피폴라 선들이 한 점에서 만나지 않고 살짝 어긋난 부채꼴이 된다. 그림으로 그려 보면 바로 보이는 증상이다.

그리고 2단계 앞에는 반드시 한나 정규화가 온다. 각 영상에서 점들의 중심을 원점으로 옮기고 원점까지 거리의 RMS가 $\sqrt2$ 가 되도록 스케일한 뒤 $\hat F$ 를 풀고 $F=T'^{\mathsf T}\hat F T$ 로 되돌린다. 이유는 호모그래피의 DLT와 완전히 같다 — $A$ 의 원소가 $x'x \sim 10^5$ 부터 $1$ 까지 걸쳐 있어 조건수가 참사 수준이기 때문이다. 한나가 1997년에 「8점 알고리즘이 나쁜 게 아니라 정규화를 안 한 게 나빴다」는 논문을 쓴 뒤로 8점 알고리즘의 평판이 통째로 복구되었다.²

7점 알고리즘은 $\det F=0$ 까지 쓴다. 대응 7개면 $A$ 의 영공간이 2차원이라 $F=\alpha F_1+(1-\alpha)F_2$ 꼴이고, 여기에 $\det F=0$ 을 넣으면 $\alpha$ 에 대한 3차식이 나와 실근이 1개 또는 3개 나온다. 최소표본이 하나 줄어드는 대가로 후보를 여러 개 검증해야 하지만, RANSAC 반복 횟수가 절반 이하로 떨어지므로 남는 장사다.

5. 5점 알고리즘[편집]

보정된 카메라라면 $E$ 의 자유도가 5뿐이므로 대응 5개로 충분하다. 니스테르(Nistér, 2004)의 알고리즘이 표준이 됐다. 얼개는 이렇다 — 5개 대응의 선형 방정식에서 $E$ 의 4차원 영공간을 구하고, 거기에 $\det E=0$ 과 위의 3차식 아홉 개를 대입해 정리하면 최종적으로 10차 다항식 하나가 남아 최대 10개의 해가 나온다. 각 해에 대해 나머지 대응으로 검증해 하나를 고른다.

계산은 확실히 험하다. 그럼에도 모두가 5점을 쓰는 이유는 오직 하나, 최소표본 크기의 지수적 효과다. 내점 비율 0.3에서 5점과 8점의 필요 반복 횟수는 수십 배 차이가 난다. 게다가 5점 알고리즘에는 결정적인 부가 이득이 있다 — 평면 장면에서도 축퇴하지 않는다. 8점 알고리즘은 장면이 평면이면 행렬 계수가 모자라 무너지지만, 5점은 보정 정보가 방정식을 채워 주므로 살아남는다. 지면·벽면이 화면을 지배하는 실외 영상에서 이 차이는 결정적이다.

6. E에서 R, t 꺼내기 — 네 개의 해와 가시성[편집]

$E$ 를 얻었으면 자세를 복원한다. $E = U\,\mathrm{diag}(1,1,0)\,V^{\mathsf T}$ 로 분해하고

$$W=\begin{pmatrix}0&-1&0\\1&0&0\\0&0&1\end{pmatrix}$$

을 쓰면 $R \in \{\,UWV^{\mathsf T},\; UW^{\mathsf T}V^{\mathsf T}\,\}$, $\mathbf t = \pm\,\mathbf u_3$ ($U$ 의 세 번째 열)로 조합 4가지가 나온다. ($\det R=-1$ 이 나오면 부호를 뒤집어 정칙 회전으로 만든다.)

네 해의 기하학적 의미는 명확하다. 두 번째 카메라를 기선 방향으로 앞뒤로 놓은 것 × 기선을 축으로 180° 돌려 놓은 것(「꼬인 쌍」, twisted pair). 진짜 해를 고르는 기준은 가시성 조건(cheirality)³ — 대응점 하나를 삼각측량해 보고 두 카메라 모두에서 깊이가 양수인 해가 정답이다. 나머지 셋에서는 점이 카메라 뒤에 있거나 한쪽 뒤에 있다. 잡음을 감안해 몇 개 점을 삼각측량해 양수 깊이가 가장 많은 해를 고르는 것이 실무 구현이다.

$\mathbf t$ 는 방향만 나온다. 단안 두 장으로는 「가까운 작은 장면」과 「먼 큰 장면」을 구별할 수 없다는 스케일 모호성이 여기서도 그대로다. 절대 스케일은 기선 길이를 실측하거나, IMU·휠 오도메트리·이미 아는 물체 크기 같은 외부 정보로 넣어야 한다.

7. 스테레오 정류[편집]

에피폴라 선이 아무 방향으로나 기울어 있으면 화소 접근이 대각선으로 튀어 캐시가 죽는다. 그래서 정류(rectification)를 한다. 두 영상에 각각 호모그래피 $H,H'$ 를 걸어 에피폴을 무한원점 $(1,0,0)^{\mathsf T}$ 로 보내면 에피폴라 선이 전부 수평이 되고, 대응점은 같은 행(scanline) 위에 놓인다. 정류 후의 기초행렬은

$$F = \begin{pmatrix}0&0&0\\0&0&-1\\0&1&0\end{pmatrix}$$

이라는 아주 예쁜 꼴이 되고, 구속은 $y'=y$ 로 축약된다.

이후 대응 탐색은 「같은 행에서 수평으로 몇 픽셀 밀렸는가」, 즉 시차(disparity) $d = x - x'$ 하나를 찾는 1차원 문제가 된다. 정류된 평행 스테레오에서 깊이는

$$Z = \frac{f\,B}{d}$$

로 바로 나온다($B$ = 기선 길이). 시차와 깊이가 반비례하므로 먼 곳일수록 깊이 정밀도가 급격히 나빠진다⁴ — 정밀도가 필요하면 기선을 늘려야 하고, 기선을 늘리면 가림(occlusion)과 외형 변화가 심해져 매칭이 어려워진다. 이 맞교환이 스테레오 비전 설계의 전부라고 해도 과언이 아니다.

정류 호모그래피는 유일하지 않아서 왜곡을 최소화하는 선택이 따로 필요하고(루프-장의 방법이 대표적), 에피폴이 영상 안에 있는 경우 — 즉 카메라가 광축 방향으로 전진한 경우 — 에는 정류가 원리적으로 불가능하다. 무한원으로 보내야 할 점이 화면 한가운데에 있으니 영상이 무한대로 늘어난다. 전진 운동 스테레오에서 정류를 포기하고 극좌표 정류나 원 에피폴라 탐색을 쓰는 이유다.

8. 추정 실무 — 잔차를 무엇으로 재는가[편집]

$F$ 를 RANSAC 안에서 추정할 때 잔차로 무엇을 쓸지가 결과를 좌우한다.

• 대수적 잔차 $\mathbf x'^{\mathsf T}F\mathbf x$ — 계산은 제일 싸지만 기하학적 의미가 없고 좌표 스케일에 끌려다닌다. 단독으로 쓰지 않는다.
• 에피폴라 선까지의 거리 — $\mathbf x'$ 에서 $F\mathbf x$ 까지, $\mathbf x$ 에서 $F^{\mathsf T}\mathbf x'$ 까지의 수직거리(양방향 합). 픽셀 단위라 임계값을 감으로 잡기 좋다.
• 샘슨 거리(Sampson distance) — 재투영오차의 1차 근사로, 계산은 거의 공짜인데 기하오차에 훨씬 가깝다.

$$d_{\text{Sampson}}^2=\frac{\bigl(\mathbf x'^{\mathsf T}F\mathbf x\bigr)^2}{(F\mathbf x)_1^2+(F\mathbf x)_2^2+(F^{\mathsf T}\mathbf x')_1^2+(F^{\mathsf T}\mathbf x')_2^2}$$

실무 표준 조합은 한나 정규화 + 7점(또는 5점) RANSAC + 내점 전체로 재적합 + 샘슨 오차 비선형 정련이다. 잔차가 두꺼운 꼬리를 가지므로 마지막 정련에는 후버 같은 로버스트 통계의 손실을 얹는 것이 국룰이다.

9. 축퇴 — 조용히 틀리는 경우들[편집]

1. 순수 회전. $\mathbf t=\mathbf 0$ 이면 $E=[\mathbf 0]_\times R = \mathbf 0$ 이고 $F$ 도 정의되지 않는다. 기선이 없으니 에피폴라 평면 자체가 안 만들어진다. 이럴 땐 $F$ 가 아니라 호모그래피로 모형을 바꿔야 하고, 눈치채지 못하면 잡음이 만들어 낸 무의미한 $F$ 를 그대로 다음 단계로 흘려보낸다.
2. 평면 장면. 모든 점이 한 평면 위에 있으면 8점 알고리즘의 $A$ 가 계수부족이 되어 $F$ 가 한 개로 결정되지 않는다(호모그래피와 양립하는 $F$ 가 2-매개변수 다발로 존재한다). RANSAC이 그중 아무거나 골라 「내점 100%」라는 만족스러운 보고를 올리는 것이 무서운 점. 축퇴 검사를 넣은 DEGENSAC 계열이 이래서 나왔다.
3. 작은 기선. 이동이 회전에 비해 작으면 $E$ 추정이 극도로 불안정해진다. 시각 오도메트리에서 정지 중인 차량이 자세를 미친 듯이 흔드는 현상의 절반이 이것이다.
4. 모든 점이 같은 깊이. 평면 장면의 특수한 경우이지만, 멀리 있는 배경만 매칭됐을 때도 사실상 같은 상황이 된다.

$H$ 와 $F$ 중 무엇을 쓸지 자동으로 판정하는 모형선택 기준(GRIC 계열)이 정석 처방이고, ORB-SLAM류가 초기화 단계에서 $H$ 와 $F$ 를 둘 다 추정해 점수를 비교하는 것이 대표적인 구현이다.

10. 관련 문서[편집]

• 호모그래피 · RANSAC · 로버스트 통계
• 특이값 분해 · 조건수 · 최소자승법 · 레벤버그-마쿼트 방법
• 회전행렬 · 점군 정합 · 칼만 필터
• 스케일 공간 · 에지 검출 · 허프 변환
• 삼각측량 · 스테레오 비전 · Structure from Motion · 카메라 보정

11. Footnotes[편집]

1. 우리말 번역이 통일되어 있지 않다. fundamental matrix 는 기초행렬·기본행렬, essential matrix 는 본질행렬·필수행렬이 모두 쓰인다. 헷갈릴 땐 영어 약자 $F$/$E$ 로 부르는 게 사고를 예방한다. 참고로 essential matrix 가 먼저(1981) 나왔고 fundamental matrix 는 그것의 비보정 일반화(1992)인데, 이름만 보면 순서가 반대인 것 같아서 더 헷갈린다. ↩

2. Hartley, R. (1997). “In Defense of the Eight-Point Algorithm.” IEEE TPAMI 19(6). 정규화 코드 다섯 줄로 논문 한 편이 나왔다며 비웃을 일이 아니다. 그 다섯 줄이 없어서 10년 넘게 「8점 알고리즘은 못 쓴다」가 정설이었다. ↩

3. cheirality 는 그리스어 «손»(χείρ)에서 온 말로 화학의 카이랄성(chirality)과 어원이 같다. 왼손과 오른손처럼 거울상이 겹치지 않는 성질을 가리키는데, 여기서는 「점이 카메라 앞에 있느냐 뒤에 있느냐」라는 부호 문제를 뜻한다. 네 해 중 셋이 장면을 카메라 뒤에 놓는다는 것은, 수식만으로는 「뒤로 걸어가며 뒤집힌 세상을 찍는 카메라」를 배제할 방법이 없다는 뜻이다. ↩

4. $Z=fB/d$ 를 미분하면 깊이 오차가 $Z^2$ 에 비례한다는 결론이 나온다. 즉 2배 멀어지면 정밀도는 4배 나빠진다. 자율주행 스테레오 카메라의 유효 거리가 대개 수십 미터에서 끊기는 것, 그 너머는 라이다나 레이더에 넘기는 것이 이 제곱항 때문이다. ↩