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

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

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

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

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

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

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

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

Optical Flow Assumptions: * Slide from Michael Black

Optical Flow Assumptions: * Slide from Michael Black,

{ 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

Tracking in the 1D case: ?

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

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

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:

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

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

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,

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

Aperture Problem Exposed Motion along just an edge is ambiguous

Aperture Problem: Example

Aperture Problem in Real Life

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

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

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

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

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

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

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

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

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

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

Reduce the resolution! * From Khurram Hassan-Shafique

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

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

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

Optical Flow Results

Optical Flow Results

Optical flow Results