[컴퓨터 비젼] CV-06 Optical Flow

1. Motion Estimation (=Optical Flow)

• 화면 안에서 움직이는 피사체 / 움직이는 카메라 / 둘 다 움직인 경우에서의 분석(비디오)
• 이전 stiching은 서로 다른 두 이미지의 같은 부분을 찾고 관계를 찾아 붙이는 거고, optical flow는 프레임 별 이미지를 비교해서 찾아낸 움직임
• 연속적인 움직임을 갖는 이미지에서 움직임을 찾으려면 local로는 부족하므로 global도 봐야한다

Why estimate visual motion

• 화면 상에서의 움직임을 알아내서 역으로 적용하면 video stabilize할 수 있음 (손떨림 보정)
• 카메라가 움직일 때 생기는 motion parallax 현상(가까이 있는거 빠르게, 멀리 있는거 느리게)으로 물체와 카메라 사이 거리z를 알아낼 수 있음
  (Projective geometry의 한계 극복; ray상의 물체가 있는 것만 알았지 어디있는지 몰랐었는데 이제 알 수 있음)

◾ Motion field and Optical flow

• Motion field: 3차원 world에서 점이 이동하면, image에 project될 때도 점이 이동하는데, 이때 이러한 점의 이동
• Optical flow: 하지만 실제 world의 상황은 모르고 projecet된 image만 고려하기 때문에 image에서 우리가 항상 motion field를 측정할 수 있다는 보장을 못해서, 항상 측정할 수 있는 밝기의 변화를 토대로 움직임을 측정하고자하고, 이때 이러한 밝기의 변화
• 각 픽셀마다 존재하는 optical flow로 motion field 구함
  • sparse motion field: feature의 optical flow만 모음, feature 픽셀에 대해서만 방향과 거리가 나타남
  • dense motion field: 모든 픽셀의 optical flow를 모음, 각 픽셀이 다음 프레임에서 어디로 이동하는지에 대한 방향과 거리가 나타남

◾ Optical flow Constraint Equation

• Optical flow로 Motion field를 구할 때의 두 가지 조건 (필기 참고)

1. 이미지의 밝기는 변하지 않는다
   • 이미지의 특정 픽셀이 움직여도 그 픽셀은 밝기를 유지
   • 이 조건 때문에 아주 짧은 시간이라면 거의 같은 이미지니까 밝기 차이가 거의 없음이라고 생각할 수도 있음
2. motion(u, v)이 작다
   • 시간이 dt만큼 지났을 때, 점x,y가 x+udt, y+vdt로 이동
     (u, v: 속도; x, y축으로 얼마나 움직였는지에 대한 정도(Offset, Optical flow))
   • dt가 아주 짧은 시간이면 거의 그대로니까 아래 식 성립
   • 테일러 급수를 사용하여 좌변을 정리하면 Brightness Comstancy Equation 식이 나옴
     (u, v가 작을 때는 locally linear하므로 미분값이 상수)

Brightness Comstancy Equation

• Spatio Temporal Derivatives (Direct methods)
• Brightness Comstancy Equation으로 u, v를 구하면 이전 프레임의 점 x, y에서 현재 프레임의 점 x+u, y+v로 이동했음을 알 수 있게됨
  (Image gradient에 얼마나 scale을 해줘야 temporal gradient를 매꿔줄 수 있는가)
• Brightness Constraint에 따라 밝기는 변하지 않기로 했는데, 시간이 지났는데 변했다 -> 픽셀이 이동했다 -> gradient 방향으로 이미지의 이동 방향을 알 수 있다(u, v)
  • 만약 시간이 지나서 내 자리가 밝아졌다면, 밝은 픽셀이 내 자리에 온 것
    -> gradient의 방향의 픽셀이 내 자리로 온 것
  • gradient방향과 픽셀의 이동방향이 반대이므로 spatial derivative는 음수 (반대방향 내적)
  • Brightness Comstancy Equation를 만족하기 위해 temporlal derivative는 양수가 되야함
    -> 시간이 지나면서 내 자리 픽셀이 밝아짐을 의미
  • 만약 이동 방향과 gradient가 수직이라면, 변화X (수직 내적 = 0)
• 공간적인 변화율과 시간적인 변화율이 같아야한다 ✔️
  
  
• 필기

---

✔️ Optical Flow를 찾는 방법은 1. Feature-based method와 2. direct-method 두 개가 존재하며, 필요한 상황에 따라 구분해서 사용 (보통 u,v가 크면 전자로, 작으면 후자로 구한다)

1. Feature-based methods

• 현재 프레임의 feature가 이전 프레임에서 어디였는지 (앞서 배운 feature detection, feature matching 해당 내용)
• Sparse motion field: 몇 개의 feature로 파악하기 때문에 듬성듬성한 데이터가 나오지만, 눈에 띄는 feature 부분은 정교하게 나옴 (robust;튼튼)
• 이미지가 많이/빠르게/큰 움직인 경우(large u, v)에 잘 찾아짐 -> 수십개 pixel의 움직임에서 잘 찾아짐

1-1. Matching Methods

• feature based methods에서 움직임을 계산하는 방법
• Feature point를 찾아 matching한 뒤, 그것을 track (어디서 어디로 갔는지 파악)
• matching의 error minimization

  • 이 방법은 아래 Lucas-Kanade와 다르게 움직임이 클 때 사용
  • 움직임이 크다고 Aperture 크기를 키우면 Aperture에 배경과 움직이는 물체가 같이 있는 경우가 생겨 판단하기 어려워짐
  • 그래서 이런 경우는 feature만 찾아서 그 점들만 tracking하는 것

1-2. Patch matching

• templete window(초록박스)를 움직이며 block matching(SSD 최소화나 Correlation 극대화 사용)으로 d를 구하면 motion을 추정할 수 있다
• 왼쪽 이미지를 d만큼 이동시켰을 때 밝기 변화가 거의 없다 = 오른쪽 이미지와 같다 = SSD가 최소 = Correlation 최대

2. Direct-methods

• Dense motion field: feature가 아닌, 모든 픽셀에 대해 track
• 이미지가 미세하게 움직인 경우(small u, v)에 잘 찾아짐 -> 10pixel 이내 움직임 ex) CCTV

2-1. Differential Methods

• Direct-methods에서 움직임을 계산하는 방법
• Spatio위치-Temporal시간 Image brightness variations (Spatio-Temporal Derivatives)
• 각 픽셀에 대한 시간과 위치에 따른 밝기 변화(=시공간 미분)로 motion 추정

2-2. Lucas-Kanade Method

• spatio-temporal derivatives을 이용한 motion estimation
• brightness consatancy equation을 주변 픽셀까지 계산하여 경향성 파악

Method	compute motion	example	motion	motion field	how
Feature-based Methods	Matching methods	Patch matching	for large	sparse(locally)	min SSD or max Correlation
Direct Methods	Differential methods	Lucas-Kanade	for small	dense(globally)	Spatio-temporal derivative

◾ Lucas-Kanade Method

• 카메라 이동으로 동일한 피사체의 밝기가 변했다면, 주변 밝기도 동일하게 변할 것
  -> 한 점만 볼 것이 아니라 x, y 주변의 점Ω들의 평균적인 움직임을 찾아야 한다 -> 시그마 들어감
• brightness consatancy equation을 한 점에 대해서만 하는게 아니라, image patch에 대해서도 성립하도록 u, v를 풀어 움직임 알아내기
• 가정: 임의의 작은 patch안에서는 모든 pixel이 같은 motion vector를 가진다
• 위 식의 왼쪽 2x2 행렬의 역행렬로 u, v를 구한다

✔️ Lucas-Kanade Method에는 3가지 문제가 있는데, 이 3가지를 다 보완해주는 방법은 Coarse-to-Fine Estimation이고, [Ⅱ. Large u, v]만을 보완해주는 것은 Iterative Refinement이다. (근데 결국 u, v를 보완해주면서.. 나머지도 해결?)

Ⅰ. Aperture problem

Local Patch Analysis

• feature detection의 Harris Mat과 똑같은 Lucas-Kanade의 Mat -> feature와 관련
• Aperture: 2x2행렬의 sumation 영역 (아래 그림의 검정 원 부분)
• 점이 이동했을 때, 이동 방향을 찾기 위해서는 모든 방향(Ix, Iy)의 gradient가 0이 아니여야지 찾을 수 있다

1. Textured area
   • Aperture에 corner: 모든 방향으로 변화가 있어 점 주변의 gradient 분포를 알 수 있고 점이 이동했을 때 어디로 갔는지 분명히 찾을 수 있다
   • u, v값에 따른 SSD를 계산했을 때, SSD(E)가 최소(하얀색)가 되는 유일한 점u, v을 찾을 수 있다 (유일한 해)
2. Edge
   • Aperture에 edge: 한쪽 방향으로 변화x, 한 축의 gradient=0 -> 행렬의 det=0으로 역행렬 존재x
   • u, v값에 따른 SSD를 계산했을 때, SSD(E)가 최소가 되는 점u, v들이 많다 (해가 무수히 많다)
3. Homogeneous area
   • Aperture에 아무것도 없으면 모든 방향으로 변화x, gradient = 0 -> 0행렬
   • u, v값에 따른 SSD를 계산했을 때, 의미가 없다 (해가 없다)!
     -> patch 내에 gradient가 없어서 밝기 변화가 생겨도 어디서 온 점인지 알 수 없다

• Mu=b를 풀어서 각 픽셀마다 u, v를 계산
• M의 역행렬이 존재하지 않는 경우 (Singular)
  • edge 근처의 점들 -> 한쪽 방향으로 변화x
  • 전체적으로 feature가 없는 부분 -> 모든 방향으로 변화x
    -> u, v를 구할 수 없다
• sol: Aperture 크기를 키워서 Aperture안에 코너가 들어올 확률 높여주기

Ⅱ. Large u, v problem

• large motion이면 (u, v)가 크기 때문에 위에서 정했던 brighness constancy를 쓸 수 없다
• (u, v)가 작을 때는 locally linear하므로 미분값이 상수인데, (u, v)가 크면 그렇지 않게 됨
• 이미지가 많이 움직이면 멀리서 픽셀이 오는 것이고, brightness constancy equation을 주변 이웃들과 계산해봤자 의미가 없는 것임..
• sol: Iterative Refinement (아래)

Ⅲ. Aliasing problem

• 정답이 아닌 다른 것을 찾은 경우 (u, v가 커서 생기는 문제)
  ex) 시간이 지나서 점이 이동했는데, patch 내에 우연히 똑같은 패턴이 들어와서 u, v=0이 아닌데 0으로 나옴
• 반복적인 패턴(울퉁불퉁한 그래프)에서는 제대로된 correspondence를 찾기 어려움 (ex-펜스)

Sol 1. Iterative Refinement

• 큰 u, v로 생기는 문제(Ⅱ, Ⅲ) 해결해줌 (근데 결국 u, v를 보완해주면서.. Ⅰ도 해결?)

1. Lucas-kanade estimation으로 u, v 계산
2. 각 픽셀별로 u, v만큼 움직임 (픽셀마다 다른 u, v를 가짐) -> 이미지를 Warping한다
3. 반복
   -> u, v가 클 때는 iterative하게 풀면 답을 구할 수 있다

Iterative Estimation

• f1의 점이 어디로 가야 f2에 맞는가

1. f1을 x0에서 미분하고, 미분한 것과 f2의 교점의 x좌표와 x0좌표의 간격인 u를 찾고, u만큼 f1을 이동
2. f함수가 직선이 아니여서(linearX) 알맞게 찾아지지 않음 (u, v가 매우 작으면 local하게 linear했음) -> 똑같은 과정 반복

Issuses

1. 시간에 따라 움직이기 때문에 픽셀별로 다른 속도u, v를 가지고, 각 픽셀별로 다른 속도로 이미지를 warping하기 어려움
   (일관성있게 움직이던 이미지 transform으로 한 forward, inverse warping과 다름)
2. 각 Iterate마다 모든 픽셀의 gradient를 계산해야함
3. low-pass filter를 하면 안정적으로 찾을 수 있음

Sol 2. Coarse-to-Fine Estimation

• ⅠⅡⅢ 세가지 문제를 해결해주는 method

Ⅰ. Aperture

• 특정 점 주변 범위Ω를 넓혀서 Aperture안에 Corner가 들어오도록 하기 (=이미지 크기 줄이기)
• feature detection 할 때처럼, multi scale을 사용해서 이미지를 줄여가며 같은 크기의 Aperture에 corner가 들어가도록 함
• 작은 크기의 이미지 입장에서는 Aperture가 커지는 효과 -> corner가 들어올 확률 커짐

Ⅱ. Large u, v

• Pyramid로 이미지의 크기를 줄이면 u, v도 충분히 작아짐

Ⅲ. Aliasing

• 작은 크기의 이미지 입장에서 커진 Aperture로 반복되는 패턴이 하나의 Aperture에 들어가게 됨
• 전체적으로 관찰해 같은 패턴이 이동한 것임을 알아냄

• Iterative Refinement를 multiscale 기법에 적용한 것 뿐임!!!
  1. 가장 작은 크기로 줄여둔 이미지에서부터 Lucas-kanade로 u, v를 찾음
  2. u, v(motion field)를 사용해 Optical flow에 맞게 warping -> 이상적으로 그 결과Jw가 다음 프레임 이미지I와 같아야한다 (같다면 다음 단계 이미지 갈 필요 없이 끝)
  3. 같지 않으면 warping한 결과Jw와 I의 차이Δa를 구한다 (이 차이만큼 더 있으면 같아졌을 테니까) -> Refine(다듬다)
  4. 같지 않으면 다음 단계의 이미지로 반복하는데, 이전 단계의 Δa를 더하여 warping한다
  • 마지막으로 나온 a_out이 예측된 motion

2. Parametric motion estimation

Global(parametric) motion models

• stiching의 나온 motion model은 local하게 본 것이고, optical flow에서는 global하게 어떻게 움직이는지 파악
• 2D Models (2D->2D)
  • Affine
  • Quadratic (위치에 따라 움직이는 속도 달라짐 표현)
  • Planar projective transform(Homography)
• 3D Models
  • Instantaneous camera motion models
  • Homography+epipole (stereo때 나옴)
  • Plane+Parallax (stereo때 나옴)

Motion models to Optical flow (2D models)

• 2D->2D Motion model들을 Optical flow에 적용하여 일반화
• 각 model마다 u, v를 어떻게 계산할까

1. Affine

   • Affine transformation으로 구한 새로운 좌표를 u, v로 나타냄
   • Brighness constancy equation의 u, v에 위의 x, y에 대한 1차식 대입
   • 모든 픽셀에 대해 Least square minimization (= Global optimization)하여 전체 변화Err가 최소화되는 미지수 6개 구하기
   • 두 개의 이미지를 가장 잘 맞추기 위한 Affine transform을 찾는 과정
     +) 위의 식에서 a1, a4만 남기면 translation model

2. Quadratic(2차식)

   • Brighness constancy equation의 u, v에 x, y에 대한 2차식 대입
   • 미지수 8개

3. Projective

   • Brighness constancy equation의 u, v에 x, y에 대한 식 대입
   • 미지수 9개 (하지만 1개의 미지수는 1이 되도록 고정을 하는 등의 조건이 있어야 구할 수 있음, 그렇지 않으면 무수히 많은 해)

Patch matcing

• patch matching으로 large displacement를 찾는다 (이미지의 전반적인 움직임)
• 특정 feature 점들의 block으로 가장 좋은 점을 찾고, 그 점으로 global motion model을 찾음
  • x,y의 patch와 x+u, y+v의 patch를 비교해서 SSD가 가장 작거나 Correlation이 가장 큰 x, y 점을 찾고, 그 때의 u, v motion vector로 glabal motion model 만듦

• 이제 이미지가 전체적으로 얼마나 움직였는지 파악해서 global motion model로 warping하고 ,
• 그 후에 detail한 것을 찾아 motion field로 warping
  (근데 Patch matching은 두 과정에서 다 쓰일 수 있는듯 ?)

matching 방법에는 correlation과 ssd가 있다

◾ Correlation and SSD

SSD의 문제점 - 시험 ⭐

• Correlation: 두 변수간 연관된 상관 관계의 정도 (두 이미지의 sample pixel들의 경향성이 얼마나 비슷한지를 나타냄)
  -> 밝기의 경향성이 같은 부분이 있으면 correlation이 높다 find max
• SSD: sum of squares difference
  -> 밝기가 비슷하면 차이가 적다 find min
• SSD는 전체 밝기가 변하면(contrasta 변화) 값이 달라짐
• 하지만 Correlation은 경향성 파악하기 때문에 contrasta가 변해도 값이 거의 변하지 않는다 (전체적인 밝기가 달라져도 linear하게 같은 경향성을 가짐)
• 그래서 두 이미지가 Photometric하게 차이가있다면 correlation 사용하면 좋다 (a, b에 큰 영향을 받지 않기 때문)

  • normalized correlation
    • correlation은 밝은 곳에서 너무 큰 값이 나오고, 어두운 곳에서는 작은 값이 나온다.
    • 밝기값에 영향을 받지 않도록 (어두운 곳에서도 비슷한 경향성이 있으면 큰 값이 나왔으면 좋겠다), 정규화를 한 correlation을 사용하기도 한다

correlation search window size

• window size 작으면
  • more false matches (motion vector가 window size보다 크면 어려움)
  • more detailed, less smooth
  • high flow resolution
• window size 크면
  • window 내 픽셀들이 따로 움직이면 motion model이 잘못나올 수 있음
    -> neighboring flow vectors tend to be more correlated (window 안에는 비슷하게 움직이는 애들만 있음 좋을텐데.. 어려움)
  • 따로 움직이는 방향의 SSD를 최소화하다보니 그 중간을 찾게되고, motion vector가 블러되는 느낌 (lower flow resolution)
  • high computing cost
• 부드럽고 전반적인 움직임은 window 크기를 키워서, 디테일하고 로컬한 움직임은 window 크기를 줄여서 구한다

◾ Discrete search method vs Gradient Based method

• matching 과정으로 찾은 motion vector가 정수?실수?
• Patch matching -> Discrete search method
  • 비슷한 patch를 찾기 위해 pixel to pixel로 u, v를 찾으므로 motion vector가 정수 (실수값의 u, v를 구하지 못한다)
• Lucas-Kanade -> Gradient based method
  • 2x2 Hessian 행렬을 찾아 u, v를 찾으므로 소수점 단위의 픽셀(sub-pixel) 이동 계산 가능
    (intensity function의 derivative가 linear하다 생각하고 품)
  • ex) 10만큼 밝아진게 1픽셀 움직인 것 -> 5만큼 밝아지면 0.5픽셀 움직인 것이구 나

◾ Shi-Tomasi feature tracker

• 내용 종합

1. 2x2 Hessian의 min eigenvalue를 찾아 좋은 features 찾기
2. Lucas-Kanade로 전체적인 translation 계산
3. Affine motion을 찾아내서 .. 머 반복?

• 영상 tracking 결과
  • 찾은 u, v로 translation만 계산
  • 여러 점으로 motion model을 찾아 affine transform -> 더 깔끔하게 찾아짐

Robust Estimation

• Least square(평균)로 구하는 Match를 방해하는 Outliers
  • noise
  • highlignts
  • jpeg artifacts
  • interlacing (홀/짝 따로그림)
  • motion blur
  • multiple motions (반투명한 물체와 그것에 가려진 물체가 따로 움직이거나 가려지는 경우)
• sol: Robust Estimation (outlier에 덜 민감한 평균 찾기 방법)
  • outlier가 될만한 요소들을 제거하고 계산
  • 기존의 error^2을 최소화하던 방법
    -> 미분하면 error의 영향을 직접적으로 받음을 알 수 있음
  • 그래프에서 위쪽에 많이 분포할 outlier를 무시하기 위해 s(어디까지 inlier로 볼 것인가)가 추가된 식을 최소화
    -> 미분하면 error가 커져도 분자에 의해 영향을 작게 만들 수 있음을 확인할 수 있다