[CS5670] Lecture 13: Stereo

자료 출처: CS5670 Stereo

 

두 이미지 사이에 어떤 차이가 있는 것 같나요? 두 이미지를 번갈아가며 비교해보면 각도에 따른 차이가 있습니다. 이 차이는 objects가 수평으로 조금씩 이동하는 것으로 느낄 수 있고, 이 이동량은 카메라로부터의 거리에 반비례합니다.

 

가까운 거리에 있는 object일수록 이동이 더 크고, 멀수록 덜 움직입니다.

 

 

 

 

Disparity

 

각 camera center에 따른 $O, O^\prime$이 있고, 이들은 3D point의 $X$로 향합니다.

 

여기서 f는 focal lenght로 camera center와 image plane 사이까지의 거리를 의미합니다.

 

 

또한, 3D point와 baseline 사이의 거리를 Z라 둡니다.

 

baseline의 길이는 b로 둡니다.

삼각형 닮음에 의해 다음과 같은 관계식을 가집니다.

오른쪽도 위의 방법과 같이 구할 수 있습니다.

 

최종적으로 $x$가 이동한 거리인 $d$는 baseline에 비례하고, $Z$와는 반비례함을 알 수 있습니다.

 

이렇게 stereo pair를 통해서 $x$의 좌표 픽셀 값의 dispaarity를 구했습니다. Disparity는 inverse depth를 의미합니다.

 

그 이유는 아래에 정리해두었는데요.

 

 

triangulation으로 비례식에 따라 각각 $x_l$, $x_r$이 정의되고 이를 합쳐서 $z$를 표현할 수 있습니다. 또한, $x$축에서의 수평 차이($x_l-x_r$)가 곧 disparity(=$d$)이므로 $d$로 다시 정리하면 $\frac{b \times f }{z}$로 표현할 수 있습니다.

 

 

즉, baseline과 focal length에 비례하고 거리에는 반비례하게 됩니다. 베이스라인과 초점거리는 물리적인 요소로 고정적 상수라 볼 수 있기 때문에 실제 3차원 거리($z$)에 큰 영향을 미치는 것은 시차(=$d$)라고 볼 수 있습니다.

 

위 Figure 2.11에 따라서도 Z에 따른 d의 변화를 볼 수 있습니다. → d = inverse depth

 

 

해당 내용은 Epipolar geometry와 연관이 있습니다. epipolar geometry는 2개의 카메라 이미지 사이에 정의되는 기하학적 관계를 의미합니다. 이는 3차원 물체의 구조와는 독립적이고, 오로지 카메라 내부 파라미터와 두 카메라 사이의 상대 포즈에만 의존합니다.

 

 

• 1) Epipolar Plane
• 2) Epipole
• 3) Epipolar Line

 

이 세가지 개념이 나옵니다.

 

• 1) 이때 두 카메라의 중심점 $C, C^\prime$과 점 $X$가 주어졌을 때, 세 점을 통해 결정되는 평면을 Epipolar Plane $\pi$라고 합니다.
• 2) 카메라 중심점 $C$를 $P^\prime$을 통해 projection한 점 $P^\prime C=e^\prime$을 이미지 평면 $\pi_{c^\prime}$의 Epipole $e^\prime$이라 합니다.
• 3) $e^\prime$과 $x^\prime$을 잇는 직선을 Epipolar Line $l^\prime$이라 합니다.

 

 

그럼 이제 stereo pair를 통해 어떻게 depth를 계산할 수 있을까요?

아까 disparity를 통해 depth를 파악할 수 있었는데, 이 depth를 구하기 위해 알아야 할 것이 더 많습니다.

 

• Steps
  • Calibrate cameras
  • Rectify images
  • Compute disparity
  • Estimate depth

 

Stereo를 위한 큰 과정은 위와 같습니다. 먼저 baseline이 명확하게 있어야하고, disparity를 얻기 위해 이미지들이 retification 되어야 합니다. 그러기 위해 필요한 것이 epipolar lines horizontal입니다.

 

Basic stereo matching algorithm

 

 

1. Rectify images (make epipolar lines horizontal)
2. For each pixel
   • a. Find epipolar line
   • b. Scan line for best match
   • c. Compute depth from disparity

 

$Z = \frac{bf}{d}$

 

오른쪽 이미지에서 같은 epipolar line의 모든 픽셀을 비교하고, 가장 최소인 match cost인 픽셀을 고릅니다. 이땐 window를 사용할 수 있습니다.

 

Stereo Block Matching

 

 

• Epipolar line을 따라 window를 sliding하고, 해당 window를 왼쪽 이미지의 reference와 비교합니다.
• Matching cost: SSD 또는 normalized correlation을 사용합니다.

 

 

 

 

Similarity Measure & Formula

 

 

유사도를 측정할 수 있는 대표적 공식과 식입니다.

 

 

 

 

Effect of window size

 

 

윈도우 사이즈에 따른 차이입니다. 윈도우 사이즈가 작을수록 더 디테일해지고 노이즈가 커집니다. 윈도우가 클수록 disparity maps이 부드러워지고 디테일이 감소됩니다. 또한 근처 경계선이 줄어듭니다.

 

이런 stereo block matching이 실패하는 경우로는

 

• textureless regions
• repeated patterns
• specularities

 

가 있습니다.

 

따라서 뒤에 이러한 매칭을 강화시키는 내용에 대해 다룰 예정입니다. (Improving Stereo Block Matching)

 

 

 

 

epipolar lines horizontal

 

epipolar lines horizontal을 어떻게 만들까요?

 

image plane을 평행하게 맞춰야 horizontal한 baseline을 구할 수 있습니다. 또한, 이 과정을 통해 correspondence와 triangulation을 더 쉽게 구할 수 있습니다.

 

좌표계를 translate하고 rotation하는 과정이 필요합니다.

 

 

그러면 $x^\prime$의 좌표를 얻을 수 있습니다.

 

그러나 이는 2D homogeneous transformation만으로는 힘듭니다.

 

 

Rotation은 Identity입니다. 왜냐하면 위 그림에서는 같은 방향(same orientation)을 갖고 있기 때문에 I로 표현되었습니다. 따라서 translate는 $x$축으로만 하면 됩니다.

 

$E=t \times R$로 translate을 해준 행렬의 모습을 갖고 있고, $x^T E x^\prime$의 관계를 갖는다고 합니다.

 

해당 내용과 수식에 대해선 더 공부한 뒤 보충하겠습니다.

 

보충+)

 

 

여기서 각 camera center가 $k$로 나와있는데, 이를 $k_1, k_2$로 두겠습니다. 그리고 이 두 값이 여기서 알고 있는 값이 됩니다.

 

$x, y, z$ 세 축이 나와 있는데, $x$축은 $O_1, O_2$와 평행합니다.

 

$E=[t_x]R$

 

아까 translation하고 Rotation한 행렬 E를 구했습니다.

 

여기서 $t_x$가 의미하는 것은 Cross product as matrix multiplication입니다.

 

 

 

다시 이미지를 보면 카메라 좌표에서 이미지 평면으로 ray를 projection 시키는데 여기서 image plane는 $(u,v)$ 좌표를 갖는다고 볼 수 있습니다.

 

이미지 평면 위의 좌표 $p$를 $(u,v)$에 1의 한 차원을 추가해서 $(u,v,1)$의 homogeneous coordinates로 바꿔줍니다.

 

그리고 $(u \ v \ 1)$과 행렬 $E$, $(u^\prime \ v^\prime \ 1)^T$를 곱합니다.

 

 $(u \ v \ 1) E (u^\prime \ v^\prime \ 1)^T$ = 0

$= p^T E p^\prime = 0$

 

 

목표는 image plane을 평행하게 만드는 것이었습니다.

 

 

따라서 이미지를 평행하게 만들어줄 perspective transformation $H$를 측정해야 합니다.

 

이렇게 두 이미지가 있을 때 $H$를 통해 구할 수 있었습니다. ($X^\prime_i = H X_i$)

 

그런데 $H$를 구하기 위해 자유도가 필요하고, $H$를 잘못 구하면 이미지에 심각한 projective distortion이 발생합니다. 그래서 이 H를 구하는 동안 여러 가지 제한 사항을 둡니다.

 

그게 아까 위에 나왔던 $v = v^\prime$입니다. 이렇게 같다고 두는 이유는 3D point가 있는 이미지는 항상 같은 수평선 위에 존재합니다. 그래서 y 좌표는 항상 같기 때문에 $v=v^\prime$이라 볼 수 있고, Translate가 적용된 경우에도 같습니다. ($Tv=Tv^\prime$)

 

 

 

Recall

 

0. Compute epipoles

 

 

 

1. Map e to the x-axis at location [1,0,1]T (normalization)

 

 

 

2. Send epipole to infinity: $e = [1 \ 0 \ 1]^T$ → $[1 \ 0 \ 0]^T$

 

 

 

3. Define: $H=H_2 H_1$ 

4. Align epipolar lines

 

 

 

Projective Transformation of a Line

 

 

 

• Makes the correspondence problem easier
• Makes triangulation easy

 

 

Stereo Rectification

 

 

stereo rectification이란 무엇일까요? 회색 평면이 image plane이라고 할 때, 노란색처럼 평행하게 만들어야 하는데요. 결국 앞에서 계속 보았던 두 이미지를 평행하게 만드는 과정입니다.

 

이때 camera center를 연결한 line과 평행한 노란색 plane으로 image plane을 각 projective transformation합니다. 그러면 image plane과 노란 평면 사이의 homography를 통해 projection이 가능합니다.

 

1. Rotate the right camera by $R$ (aligns camera coordinate system orientation
   only)
2. Rotate (rectify) the left camera so that the epipole is at infinity
3. Rotate (rectify) the right camera so that the epipole is at infinity
4. Adjust the scale

 

Rectification Steps

 

1. Compute $E$ to get $R$
2. Rotate right image by $R$
3. Rotate both images by $R_{rect}$
4. Scale both images by $H$

 

Setting the epipole to infinity

 

rectification 한 다음엔 무엇을 해야할까요? 이제 infinity에 epipole을 세팅합니다.

 

Stereo Rectification Algorithm

1. Estimate $E$ using the 8 point algorithm (SVD)
2. Estimate the epipole $e$ (SVD of $E$)
3. Build Rrect from $e$
4. Decompose $E$ into $R$ and $T$
5. Set $R_1=R_{rect}$ and $R_2 = RR_{rect}$
6. Rotate each left camera point (warp image) → $[x’ y’ z’] = R1 [x y z]$
7. Rectified points as $p = f/z’[x’ y’ z’]$
8. Repeat 6 and 7 for right camera points using $R_2$

 

 

Stereo block matching fail

 

• textureless regions: 아무것도 없는 부분이 많으면 다 유사하게 판단될 수 있음
• repeated patterns: 반복되는 부분이 윈도우 사이즈 보다 크면 반복되는 부분이 잘못 매칭 될 수 있음
• specularities: 빛이 반사되는 양이 다르면 matching이 안 될 수 있음

 

 

Stereo Results

• Too many discontinuities
• We expect disparity values to change slowly
• Assumption: depth should change smoothly

 

Better solution

• disparity들을 측정하는 각각의 대응점들을 넘어,
  • Scanline at a time (DP)
  • Full 2D grid (graph cut)

이 필요합니다.

 

 

 

Energy minimization

• 위 두조건을 만족하는 에너지를 최소화하는 stereo를 구성할 수 있습니다. 
• 이를 구성하기 위해 에너지 함수 E(d)를 최소화 할 disparity map d’을 찾아야 합니다.
• simple pixel과 window에서 matching 할 때, Disparity space image에서 각 column의 최솟값을 독립적으로 선택해야 합니다.

 

 

좋은 stereo 대응점을 찾기 위해 무엇을 정의해야할까요?

 

1. Match quality: 다른 이미지에서 각 픽셀에 잘 일치하는 것을 찾고 싶음
2. Smoothness: 만약 두 픽셀들이 인접하다면, 같은 양만큼 움직여야 함(disparity가 유사해야함)

 

*에너지 기반 모델은 x에서 y를 분류하는 것 보다, 특정 (x,y)의 짝들이 서로 맞는지 아닌지를 예측합니다.

 

• energy function E(d)를 최소화 시켜줄 disparity map $d$를 찾기
• 각 픽셀 별로 window matching하면서 차이를 계산하는데 절대차 혹은 제곱차를 사용합니다. 
• Data term: 비슷한 픽셀들끼리 매치
• Smoothness term: 대부분의 근처 픽셀은 비슷한 disparity를 가진다는 점 → spacila smoothness를 줌

 

Data term

• 여기선 Sum of squared difference를 사용하였습니다.
• 좌우 윈도우 내 존재하는 픽셀들 값의 차이에 제곱하여 합산하여 계산합니다.

 

 

Smoothness term

 

• Smoothness term이 들어오면서 더 좋은 cost function이 됩니다.
• 4 neighbor(manhattan metric) 혹은 8 neighbor에서 2개의 인접한 부분의 disparity에 대해 V라는 function의 합입니다.

 

V도 두 가지 방법이 있습니다.

 

1. L1 distance
2. 0과 1로 두는 potts model(같으면 1, 다르면 0)

 

• 만약 λ = infinity이라면, 오직 smoothness만 고려한다.
• 최상의 솔루션은 depth/disparity의 surface를 가지는 것입니다.

 

 

Dynamic programming

• 1D scanline의 경우, 동적 프로그래밍을 사용해서 E를 최소화할 수 있습니다.

 

• Basic idea: 한 번에 한 열씩 cost function을 update합니다.

이 솔루션의 minimum cost입니다.

 

• 1D 스캔라인의 경우 동적 프로그래밍을 사용하여 E를 정확히 최소화할 수 있습니다.
• 기본 아이디어: 비용 테이블을 한 번에 한 열씩 점진적으로 작성합니다.

 

• 왼쪽→오른쪽으로 DPI를 통해 low-cost를 갖는 smooth한 부분을 찾습니다.
• 노드를 방문하면 data cost가 발생하고, 한 열에서 다음 열로 가는 disparity의 전환에도 smoothness cost가 발생합니다.

Q: 최단 거리 방법은 2D에서도 잘 적용되나요?

A: No. 오직 1D path에서만 작동됩니다.

 

 

Properties

• 2D image의 경우, E의 global minimum을 찾는 것은 NP-hard입니다.
  • Why? → 탐색할 공간이 너무 큽니다.

• gradient descent의 경우, 수많은 local minima가 있기 때문에 잘 작동되지 않습니다.
• Good approximation이 존재합니다. E.g. → Graph cuts algorithms

 

설명 보충

 

• $n \times m$ size를 가진 이미지의 disparity의 경우, $k^{nm}$의 가능한 솔루션이 나옵니다. 따라서 일반적으로 global minimum을 찾는 것이 NP-hard입니다.
• NP-hard란 다항시간내에 풀 수 없는 문제를 뜻합니다. 다항 방정식 대신에 지수 방정식으로 풀 수 있는 문제를 말합니다. 즉, 결정석 다항식으로 구성할 수 없다는 것입니다.(=다항식으로 해당 문제의 방정식을 제시할 수 없음)
• 좋은 근사치란 어떤 알려져 있는 적절한 범위내에 있는 차선의 (suboptimal) 해결책을 빠르게 찾는 알고리즘을 의미하기도 합니다.
• 모든 NP-complete 문제가 good approximation algorithms 을 가진 것은 아니며, good approximation algorithm 을 발견한 문제도 문제 그 자체를 해결하기에 충분하지는 않다.

 

 

 

Graph Cuts

• 2D graph에서 shortest path를 찾는 방법
• region + boundary

• 각 픽셀을 정점으로 정의하고, 연결된 간선(link)를 유사도라고 생각하면 그리드 형태의 그래프로 생각할 수 있습니다.
• region을 cut하는 optimal boundary를찾는 것

 

 

 

내용에 잘못된 부분이 있다면 댓글로 알려주세요. 감사합니다.