3D Vision 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.

Slides:



Advertisements
Similar presentations
입체영상 세미나 아주대 정보통신연구소 게임애니메이션 센터 김주철
Advertisements

검출기 눈, 사진, Photoelectric device, Photomultipliers, Image intensifiers, Charged Coupled Device,
Multimedia Programming 04: Point Processing Departments of Digital Contents Sang Il Park.
Sources of the Magnetic Field
Chapter 7 ARP and RARP.
스테레오 비젼을 위한 3장 영상의 효율적인 영상정렬 기법
제 5 장 스테레오.
Multimedia Programming 05: Point Processing
Snake : Active Contour Model Computer Vision & Pattern Recognition
Mesh Saliency 김 종 현.
Internet Computing KUT Youn-Hee Han
Multimedia Programming 05: Point Processing
일반 의약품의 오 남용 (다이어트 약 중심으로)
Multimedia Programming 06: Point Processing3
On the computation of multidimensional Aggregates
Accelerometer Data Collection and Preprocessing
Genetic Algorithm 신희성.
쉽게 배우는 알고리즘 9장. 그래프 알고리즘.
Dynamic Programming.
3D Vision Lecture 7 동작 이해 (광류).
알고리즘(Algorithm) – Greedy Method (탐욕적 방법)
1 도시차원의 쇠퇴실태와 경향 Trends and Features of Urban Decline in Korea
Chapter 2. Finite Automata Exercises
Cluster Analysis (군집 분석)
숭실대학교 마이닝연구실 김완섭 2009년 2월 8일 아이디어  - 상관분석에 대한 연구
for Robust Facial Landmark Localization
Point Pattern Matching by Using Parameterization
자동제어 영남대학교 기계공학부 정 병 묵.
EnglishCare 토.마.토. 토익 L/C 일상 어휘 ④ 강 사 : 김 태 윤.
Dongchul Kim / / OpenCV Tutorials Course Dongchul Kim / /
Medical Instrumentation
진대제 장관이 말하는 '100점짜리 인생의 조건' ▲ 진대제 정보통신부 장관    `인생을 100점짜리로 만들기 위한 조건은 무엇일까요`  진대제 정보통신부 장관이 대한상의 초청 조찬 간담회를 시작하며 참석자 들에게 던진 `조크성` 질문이다. 진 장관은 "제가 재미있는 얘기하나 하겠습니다"고 말하고, 
Parallel software Lab. 박 창 규
PCA Lecture 9 주성분 분석 (PCA)
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
Multimedia Programming 10: Unsharp Masking/ Histogram Equalization
제 15 장 거시경제의 측정 PowerPoint® Slides by Can Erbil
Professional Sales Negotiations
패러다임과 과학혁명.
Course Guide - Algorithms and Practice -
Dynamic Programming.
감마선스펙트럼 방사능측정 불확도 Environmental Metrology Center
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
KMP ALPS 알고리즘 세미나 김태리.
3D Vision Lecture 6 스테레오 비전
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
Signature, Strong Typing
Signature, Strong Typing
이산수학(Discrete Mathematics)
평생 간직할 멋진 말 Excellent thought applicable through our whole life
Signature, Strong Typing
PCA 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.
제 5강 지각.
히스토그램 그리고 이진화 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'
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
점화와 응용 (Recurrence and Its Applications)
창 병 모 숙명여대 전산학과 자바 언어를 위한 CFA 창 병 모 숙명여대 전산학과
이산수학(Discrete Mathematics)
The general form of 0-1 programming problem based on DNA computing
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
A SMALL TRUTH TO MAKE LIFE 100%
검출기 눈, 사진, Photoelectric device, Photomultipliers, Image intensifiers, Charged Coupled Device,
A SMALL TRUTH TO MAKE LIFE 100%
제10장. Other Models of TM’s 학습목표
[CPA340] Algorithms and Practice Youn-Hee Han
Ray Casting 발표자 : 박 경 와
Chapter 2. Coulomb’s Law & Electric Field Intensity
Chapter 4. Energy and Potential
Traditional Methods – Part 1
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
Presentation transcript:

3D Vision 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. 스테레오 비전

삼각형의 닮은꼴 원리를 이용하여 거리 정보 추출 두 가지 작업 (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 12 C. Loop and Z. Zhang, “Computing Rectifying Homographies for Stereo Vision,” IEEE Conf. Computer Vision and Pattern Recognition, 1999.

Rectification 13

Rectification 14

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)

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;

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