3D Vision Lecture 7 동작 이해 (광류).

Presentation on theme: "3D Vision Lecture 7 동작 이해 (광류)."— Presentation transcript:

1 3D Vision Lecture 7 동작 이해 (광류)

2 Optical Flow: Outline 예제 (Examples) Formal definition, 1D case
From 1D to 2D: Aperture Problem Course motion and pyramids

3 Optical flow 광류 (optical flow) = 각 픽셀에서 움직임 측정값

4 Problem definition: optical flow
영상 H 에서 I 로 변형되는 각 픽셀 움직임을 어떻게 계산 ? 픽셀 대응 관계를 구하여 해결 H 영상의 각 픽셀에 대해, I 영상에서 이웃한 픽셀들 중에서 컬러 값이 유사한 픽셀 선택 Key assumptions 색 일관성 (color constancy) : H 영상에서 각 픽셀들은 I 영상에서도 비슷한 컬러 값을 갖는다 For grayscale images, this is brightness constancy 작은 움직임 (small motion) : 픽셀들의 움직임은 비교적 작은 범위에 제한된다 This is called the optical flow problem

5 Optical Flow: Outline Examples
1D의 경우 광류 정의 (Formal definition, 1D case)_ From 1D to 2D: Aperture Problem Course motion and pyramids Flow Segmentation

6 Optical Flow Image sequence Tracked sequence (single camera)
Image tracking 3D computation Image sequence (single camera) Tracked sequence 3D structure + 3D trajectory

7 What is Optical Flow? Optical Flow Velocity vectors Common assumption:
영상 패치들은 밝기 값의 변화가 없다 (brightness constancy)

8 Optical Flow Assumptions: Brightness Constancy
* Slide from Michael Black,

9 Optical Flow Assumptions:
* Slide from Michael Black

10 Optical Flow Assumptions:
* Slide from Michael Black,

11 { Optical Flow: 1D Case Brightness Constancy Assumption:
Because no change in brightness with time The gray level of a point does not change when moved over a short period of time. Ix v It

12 Tracking in the 1D case: ?

13 Tracking in the 1D case: Temporal derivative Spatial derivative
Assumptions: Brightness constancy Small motion

14 Tracking in the 1D case: Iterating helps refining the velocity vector
Temporal derivative at 2nd iteration Can keep the same estimate for spatial derivative Converges in about 5 iterations

15 Algorithm for 1D tracking:
Compute local image derivative at p: Initialize velocity vector: Repeat until convergence: Compensate for current velocity vector: Compute temporal derivative: Update velocity vector: For all pixel of interest p: Need access to neighborhood pixels round p to compute Need access to the second image patch, for velocity compensation: The pixel data to be accessed in next image depends on current velocity estimate (bad?) Compensation stage requires a bilinear interpolation (because v is not integer) The image derivative needs to be kept in memory throughout the iteration process Requirements:

16 Optical Flow: Outline Examples Formal definition, 1D case
1D에서 2D로 확장: 구멍 문제 (Aperture Problem) Course motion and pyramids Flow Segmentation

17 From 1D to 2D tracking 1D: 2D:
Shoot! One equation, two velocity (u,v) unknowns…

18 From 1D to 2D tracking We get at most “Normal Flow” – with one point we can only detect movement perpendicular to the brightness gradient. Solution is to take a patch of pixels Around the pixel of interest. * Slide from Michael Black,

19 How does this show up visually? Known as the “Aperture Problem”

20 Aperture Problem Exposed
Motion along just an edge is ambiguous

21 Aperture Problem: Example

22 Aperture Problem in Real Life

23 From 1D to 2D tracking The Math is very similar:
Window size here ~ 5x5 or 11x11

24 More Detail: Solving the aperture problem
각 픽셀에 대해 더 많은 수식을 어떻게 구할 것인가 ? 기본 아이디어 : 추가적인 제약조건을 사용 광류는 지역적으로 매우 유사하다는 가정 사용 방법-1 : 각 픽셀의 이웃 픽셀들은 동일한 광류 (u,v)를 갖는다고 가정 이웃 픽셀을 정의하기 위해 5x5 윈도우 사용하면, 각 픽셀당 25개의 수식이 만들어짐 * From Khurram Hassan-Shafique

25 Lukas-Kanade flow 문제점 : 모른 변수 수보다 더 많은 수식이 만들어짐
문제점 : 모른 변수 수보다 더 많은 수식이 만들어짐 해결책 : 최소 에러 문제로 변환하여 해결 해 d 를 구하기 위한 최소 에러 해결 방법은 : 합 연산은 KxK 크기의 윈도우 내의 모든 픽셀에 대해 수행 이 방법은 Lukas & Kanade (1981) 에 의하여 제안됨 * From Khurram Hassan-Shafique

26 Conditions for solvability
최적의 (u, v) 다음과 같은 Lucas-Kanade 수식을 만족함 equation 위 식을 풀기 위해서는 ? ATA should be invertible ATA should not be too small due to noise eigenvalues l1 and l2 of ATA should not be too small ATA should be well-conditioned l1/ l2 should not be too large (l1 = larger eigenvalue) * From Khurram Hassan-Shafique

27 Edge gradients have one dominant direction large l1, small l2
* From Khurram Hassan-Shafique

28 Low texture region gradients have small magnitude small l1, small l2
* From Khurram Hassan-Shafique

29 High textured region gradients have different directions, large magnitudes large l1, large l2 * From Khurram Hassan-Shafique

30 Observation 광류 계산식은 두 영상을 비교하여 해를 구하지만, BUT
해의 민감도는 한 영상의 상황을 분석하여 계산 가능 ! 위 분석을 통해 어떤 픽셀의 추적은 비교적 용이하고 어떤 픽셀의 추적은 어려운지 판단 가능 특징 추적에 매우 유용하게 사용될 수 있음 ... Once suggestion: Track Harris Corners! * From Khurram Hassan-Shafique

31 Optical Flow: Outline Examples Formal definition, 1D case
From 1D to 2D: Aperture Problem 피라미드 (pyramid) 를 이용한 광류 계산

32 Revisiting the small motion assumption
작은 움직임이라 할 수 있나 ? Probably not—it’s much larger than one pixel (2nd order terms dominate) 이 문제를 어찌 해결할 것인가 ? * From Khurram Hassan-Shafique

33 Reduce the resolution! * From Khurram Hassan-Shafique

34 Coarse-to-fine optical flow estimation
Gaussian pyramid of image It-1 Gaussian pyramid of image I image I image It-1 u=10 pixels u=5 pixels u=2.5 pixels u=1.25 pixels image It-1 image I

35 Coarse-to-fine optical flow estimation
Gaussian pyramid of image It-1 Gaussian pyramid of image I image I image It-1 run iterative L-K warp & upsample run iterative L-K . image J image I

36 Multi-resolution Lucas Kanade Algorithm
Compute Iterative LK at highest level For Each Level i Take flow u(i-1), v(i-1) from level i-1 Upsample the flow to create u*(i), v*(i) matrices of twice resolution for level i. Multiply u*(i), v*(i) by 2 Compute It from a block displaced by u*(i), v*(i) Apply LK to get u’(i), v’(i) (the correction in flow) Add corrections u’(i), v’(i) to obtain the flow u(i), v(i) at ith level, i.e., u(i)=u*(i)+u’(i), v(i)=v*(i)+v’(i) upsampling = To increase the sampling rate

37 Optical Flow Results

38 Optical Flow Results

39 Optical flow Results