3D Vision Lecture 6 스테레오 비전 This course is a basic introduction to parts of the field of computer vision. This version of the course covers topics in 'early' or 'low' level vision and parts of 'intermediate' level vision. It assumes no background in computer vision, a minimal background in Artificial Intelligence and only basic concepts in calculus, linear algebra, and probability theory. Lecture 6 스테레오 비전

Stereo Vision

삼각형의 닮은꼴 원리를 이용하여 거리 정보 추출 두 가지 작업 (Two parts) : Main Points 삼각형의 닮은꼴 원리를 이용하여 거리 정보 추출 두 가지 작업 (Two parts) : 대응점 찾기 깊이 계산 (easy part). 제약 조건 (Constraints) : Geometry, epipolar constraint. Photometric: Brightness constancy, only partly true. Ordering: only partly true. Smoothness of objects: only partly true.

Main Points (continued) 알고리즘 유형 : What you compare: points, regions, features. 최적화 방법 : Local greedy matches. 1D search. 2D search.

같은 뷰 라인 상에 모든 3D 점들은 2D 영상에서 같은 점으로 투영: Why Stereo Vision? 2D 영상은 실세계 3D 점을 2D 평면에 투영 : O P’=Q’ P Q 같은 뷰 라인 상에 모든 3D 점들은 2D 영상에서 같은 점으로 투영: 2D 영상은 깊이 정보 손실을 가져옴

Stereo 2 대의 카메라에서 얻은 좌/우 영상과 카메라 위치에 대한 정보로 부터 깊이 정보 추출

Recovering Depth Information: Q P’1 P’2=Q’2 Q’1 O2 O1 Depth can be recovered with two images and triangulation.

So Stereo has two steps 두 영상에서 대응점을 찾아 깊이 정보 계산

Epipolar Constraint 가장 강력한 대응관계를 위한 제약조건 대응 점 찾기 문제를 매우 단순한 형태의 작업으로 변환

Stereo correspondence 대응 픽셀 찾기 Pairs of points that correspond to same scene point epipolar plane epipolar line epipolar line 에피폴라 제약 조건 대응점 찾기 문제를 에피폴라 라인 상에서의 1D 탐색 문제로 제한

Simplest Case 좌/우 영상 평면이 서로 평행하다 초점 (Focal point)이 서로 같은 높이를 갖는다 초점 거리가 같다 에피폴라 라인은 수평 스캔 라인이 된다

영상교정 (image rectification)을 통해 위의 기하구조 획득 가능 영상 교정 영상 평면을 두 초점을 연결하는 선에 평행한 평면으로 재투영 Notice, only focal point of camera really matters

Image Reprojection 에피폴라 라인이 수평선이 되도록 입력 영상을 워핑 (Warping) Rectification (perspective transformation) 에피폴라 라인이 수평선이 되도록 입력 영상을 워핑 (Warping) Procedure 영상 평면을 공통 평면으로 재투영, 공통 평면은 두 초점을 연결하는 선에 평행한 평면 A homography (3x3 transform) applied to both input images 라인을 재샘플링 작업 수행 - Resample lines (and shear/stretch) to place lines in correspondence, and minimize distortion 14 C. Loop and Z. Zhang, “Computing Rectifying Homographies for Stereo Vision,” IEEE Conf. Computer Vision and Pattern Recognition, 1999.

Rectification 15

Rectification 16

Let’s discuss reconstruction with this geometry before correspondence, because it’s much easier. Z Disparity: xl xr f pl pr Ol Or T Then given Z, we can compute X and Y. T is the stereo baseline d measures the difference in retinal position between corresponding points

대응 관계 : 무엇을 대응시켜야 ? Objects? Edges? Pixels? Collections of pixels?

대응관계 : 에피폴라 제약조건

대응 관계 : 광측정 (Photometric) 제약조건 실세계의 한 점은 좌 우 영상에 같은 밝기값으로 투영된다 앞면이 평행한 램버션 평면 (Lambertian fronto-parallel) Issues: Noise Specularity Foreshortening 입체각에서 모든 방향으로 균일한 광속을 갖는 반사체로 반사 광도가 보는 각도에 관계없이 일정함. 모든 방향으로 일정하게 반사되는 표면을 완전확산면, 램버시안 표면이라고 한다

제약 조건들을 이용해 스테레오 정합 시도 For each epipolar line Improvement: match windows For each pixel in the left image For each epipolar line compare with every pixel on same epipolar line in right image pick pixel with minimum match cost This will never work, so:

Comparing Windows: ? = g f Most popular For each window, match to closest window on epipolar line in other image.

Comparing Windows: Left Right scanline SSD error disparity Left Right

Window size W = 3 W = 20 Effect of window size Better results with adaptive window T. Kanade and M. Okutomi, A Stereo Matching Algorithm with an Adaptive Window: Theory and Experiment,, Proc. International Conference on Robotics and Automation, 1991. D. Scharstein and R. Szeliski. Stereo matching with nonlinear diffusion. International Journal of Computer Vision, 28(2):155-174, July 1998 smaller window: more detail, more noise bigger window: less noise, more detail

Large window 좋은 전역적 정보 제공 정교한 대응점 위치를 찾지 못함 잡음에 덜 민감함 폭이 넓은 골 (wide-bottomed valley)을 형성 Dv(p)=∑(f(i,j)-g(i,j+p))sup2/sigma(f) p Dv(p)

Small window 잡음에 민감함 p0 에서의 Dv(p0) 와 다른 후보 점들 pi 에서의 Dv(pi) 와의 차이가 크지 않을 수 있음 복수의 골 (valley)이 형성될 수 상대적으로 폭이 좁은 골이 형성됨 p Dv(p)

Adaptive strategy for window size 1. let n=n0 (ex. n0=9=initial size) 2. compute Dv(p) for candidate points 3. if Dv(p) has only one valley such that Dv(p) < d1, choose the point and exit 4. if min{Dv(p)} > d2, no corresponding points and exit 5. if n = max (ex. Max=19),

6. let n=n+2 and consider only candidate points such that Dv(p) < d3 7. goto step2 not found d1 d3 d2 found d1 d3 d2 d1 d3 d2 retry

Stereo results Data from University of Tsukuba Scene Ground truth

Results with window correlation Window-based matching (best window size) Ground truth

Ordering constraint 일반적으로 좌/우 영상에서 대응점들은 같은 순서를 갖는다 – 순서 제약 조건

Ordering constraint 일반적인 경우, 대응점들의 순서는 같다 폐색의 경우, 순서가 보존되지 않을 있다 …and its failure

순서 제약 조건을 이용한 동적 프로그래밍 (dynamic programming) 왼쪽 영상의 수평 스캔 라인 상의 픽셀들과 오른쪽 영상의 수평 스캔라인 상의 픽셀들을 정합 최적 경로 (optimal path) 찾는 문제

Stereo Correspondences Left scanline Right scanline … Occlusion Match Match Match Disocclusion

Search Over Correspondences Occluded Pixels Left scanline Right scanline Disoccluded Pixels Three cases: Sequential – add cost of match (small if intensities agree) Occluded – add cost of no match (large cost) Disoccluded – add cost of no match (large cost)

Stereo Matching with Dynamic Programming Occluded Pixels Left scanline Start Dynamic programming yields the optimal path through grid. This is the best set of matches that satisfy the ordering constraint Dis-occluded Pixels Right scanline End

DF with continuous path 한 쪽 스캔 라인의 각 점은 다른 쪽 스캔 라인의 한 점 (not multi-points) 과 대응될 수 있다고 가정한다 단순 증가 순서 (monotonic ordering)를 가정한다 i.e., if z(l1) matches z(r1), then z(l1+1) may only match z(r1+j), j>0.

DF with discontinuous path 장면은 불연속 평면 (discontinuous surface)을 포함할 수 있다 – 폐색이 발생할 수 있음 왼쪽에서 보여진 부분이 오른쪽에서는 안보일 수 있음 – 대응 관계는 수직 경로가 됨 오른쪽에서 보여진 부분이 왼쪽에서는 안보일 수 있음 – 대응 관계는 수평 경로가 됨

DP algorithm D(i,j)=difference between light intensity profile around I in right image and that around j in left image F(i,j)=minimum cost associated with optimum path from start to (i,j). Occ =occlusion cost for no-match

How to calculate optimal match 1. for 0 ≤ i ≤ n F(i,0)=i∙Occ, F(0,i)= i∙Occ 2. for 0 ≤ i,j ≤ n min1 = F(i-1,j-1) + D(i,j) min2 = F(i-1,j) + Occ min3 = F(i,j-1) + Occ F(i,j) = cmin = Min(min1,min2,min3) if (cmin = min1) M(i,j) = 1 if (cmin = min2) M(i,j) = 2 if (cmin = min3) M(i,j) = 3

How to reconstruct optimal match 1. p = n, q = n 2. while (p != 0 && q != 0) switch(M(p,q)) case 1: p matches q; p--; q--; break; case 2: p is unmatched; p--; break; case 3: q is unmatched; q--; break;

동적 프로그램을 이용하여 거리정보를 추출하는 예제 영상

Other constraints 완만한 변화 (smoothness)제약조건 : 깊이 값은 너무 급작스럽게 변하지 않는다 완만한 변화 제약조건을 활용하기 위해서는 2D 공간 탐색이 요구됨 – 주변 영역의 깊이 값과 비교해야 하기 때문에 Solved with a host of graph algorithms, Markov Random Fields, Belief Propagation, ….

Summary 문제 해결을 쉽게 하는 제약조건들에 대한 이해 최적화 기법 설계 일부 조건은 매우 강한 조건임 (예: epipolar constraint) 순서 제약 조건은 강한 조건은 아니지만 적절히 사용되어 좋은 성능을 만들 수 일부 조건은 비교적 약한 조건임 (예: 광측정 제약조건, 완만한 변화 제약조건 ) 최적화 기법 설계 어떤 제약 조건을 사용할 것인가에 영향 받음