Optical Flow – Re-introduction

by allenlu2007

本文主要根據 Thomas Pock 的 note

http://www.icg.tugraz.at/courses/lv710.080/info/motion_estimation.pdf

and Utah notes

http://www.sci.utah.edu/~gerig/CS6320-S2013/Materials/CS6320-CV-S2012-OpticalFlow-I.pdf

http://www.sci.utah.edu/~gerig/CS6320-S2013/Materials/CS6320-CV-S2012-OpticalFlow-Ib.pdf

http://www.sci.utah.edu/~gerig/CS6320-S2013/Materials/CS6320-CV-S2012-OpticalFlow-II.pdf

加上一些對於 optical flow 新的領悟,主要是 based on D’Alembert 虛位移原理。

 

下面唐魯孫說的故事和本文有關。不過我只找到簡體版。  

从前梨园行,大半都喜欢闻点鼻烟,尤其名角大老板闻烟还要闻好的。当年唱老生有个叫白文奎的,他有个女婿是个跑外国轮船上的厨师。不知道他从那一国,得到一罐荔枝味儿的鼻烟,后来白文奎把这罐鼻烟,送给余叔岩。小余是闻鼻烟的行家,什么好烟都闻过,可是闻荔枝味儿的鼻烟,也是第一遭。当然把这罐鼻烟,视同瑰宝收藏起来。有一天小余在烟炕上给师傅谭鑫培打烟泡,一面烧烟一面跟傅讨教玩艺。小余说每次唱定军山,一耍大刀花,不是刀钻裹护背旗,就是把护背旗打得卷在旗杆上了,每一耍刀下场亮相,都显得不干净,不利落,您说那是怎么回事。老谭好像全神贯注抽烟,根本不搭碴儿。小余再问第二遍,老谭还是顾左右而言他。呆了一会,老谭忽然冒了一句说,听说你最近彩头不错,得了点好鼻烟,还寻摸着一只好烟壶。小余本来是绝顶聪明,听弦歌而知雅意。立刻回说,最近有人送点外洋鼻烟,从古玩铺买了一只古月轩百子图的料壶,本来预备带来,请您给鉴定真假好坏的。谁知出门一慌竦,把这事忘了,说完话马上回家去拿。一会见功夫,小余就把百子鼻烟壶装满了荔枝味鼻烟拿来。老谭把烟壶端详了半天,认定烟壶的确是古月轩制品。再一闻鼻烟,频频点头认为澹发芬馨,也是从所未尝。小余聆听之下,当然把烟壶带鼻烟,一并孝敬了老师。等了一会儿,老谭自己反倒旧话重提问起小余来。在小余再次请益之下,老谭拿着烟签子一比划,说把烟签子当刀头。耍大刀花时,两眼全盯住刀头转,自然脑袋也跟着动,不是刀钻就把护背旗让开了吗。一语惊醒梦中人,就是这一招,就花了小余银子若干两。这是当年余叔岩亲口告诉张伯驹的,大概此事不假。一所以小余给徒弟说戏也不痛快,因为人家玩艺,也是花了大把银子虿来的。老谭爱闻鼻烟,那是众所周知的。言菊朋不但唱上学老谭,就是言谈动作,也要曲意摹仿。老谭爱闻鼻烟,言三也当然不能例外,所以言三一到后台扮戏,得先洗鼻子。梨园行朋友说话向来是不饶人的,大家给他起了个外号;尊称言三为言五子。宽脸子(言脸宽而短),短胡子,薄靴子,洗鼻子,妆孙子。话虽近谑,可也是实情。

 

* Constant Brightness Optical flow 就是 wave function local approximation + global interpretation/coordination

* 也可以說 Constant Brightness 就是眼睛盯住一點(或一區), 腳下跟著移動 (motion vector). 這是 local 的部份。

* 盯住每一不同點 I(x, y),腳下對應的 motion vector (u, v) 都不同。如何協調所有不同的 motion vector.  這是 global 的部份。例如同一 object 的 (u,v) 應該相同 (rigid body), 或平滑 (penalty on large gradient), etc. 

* Constant Brightness 其實很像 D’Alembert 的虛位移或是虛功原理。把動態問題轉為靜態問題。再藉著虛位移找 

optical flow constraint equation. 參考本文

 

What is Optical Flow

* 基本上所有的生物視覺系統都會 perform optical flow.

* Optical flow 可視為 3D motion (velocity) field projected to 2D camera plane.

* 因此 optical flow 並非 “true” 3D motion of the objects.  

  OPTICAL FLOW = apparent motion of brightness patterns (pattern 很重要)

* “True” 3D motion 稱為 “scene flow” 需要額外的 3D information (e.g. stereoscope).

 

Optical Flow 可分為:  global approach (variational method), local approach, model matching … 

– 1980: Horn and Schunck (global approach)

– 1981: Lucas and Kanade (local approach)

– 1989: Shulman and Herve (discontinuity preserving)

– 1993: Black and Anandan (robust optical flow)

– 1999: Alvarez et al. (PDE model)

– 2003: Bruhn et al. (realtime optical flow using mulitgrid)

– 2004: Brox et al. (high accuracy using warping)

– 2007: Zach, Pock, Bischof: (duality based minimization)

– …

 

What is Optical Flow Basic Assumptions

* Brightness constancy assumption: Intensity/illumination remain constant

* (空間) Spatial coherence assumption: Neighboring pixels are likely to have the same motion

* (時間) Temporal persistence: Motion changes gradually over time; small motion approximation

Brightness constancy assumption 的問題。

* Aperture Problem: Only the normal flow can be estimated

注意 Normal (optical) flow 並不一定等於 3D motion.  如下面的 Barber pole illusion.

NewImage

* Untextured Areas Problem: 如果區域中沒有任何的 pattern/texture, 也無法提供任何 information for optical flow method

NewImage

* Change Illumination Problem: 改變照光所照成的 optical flow 並非真的 motion field.

如何解決?  真是更 advanced 的問題。本文忽略。

NewImage

 

Constant Brightness Optical Flow Constraint (OFC)

OFC 包含兩個 variables, u and v.  所以是 underdetermined problem. 如果是 RGB? 是否可以增加 constraints? 

Ix u + Iy v + It = 0

NewImage

 

 

 

Optical Flow: 1D Motion

 

NewImage

 

NewImage

 

Wave Function Point of View

另一個角度是從 wave function 來看。如果一個 W(x, t) 可以寫為

W(x, t) = W(x-vt)  代表如果視角以 v 的速度移動,永遠看到一個靜止不動的函數!

速度 v = – ∂W/∂t / ∂W/∂x = – Wt / Wx

當然以 optical flow 而言,不會每一點都定速移動。但每一個 local patch 來說,可以用 Taylor expansion

做 first order approximation, 而得到 local 的 wave function!!

(請自動假設 camera plan 是無窮大!  以免被 boundary 限制住! )

 

Constant Brightness Optical Flow 數學上的推導如下:

Let f(t) = I( x(t), t ) = I( x(t+dt), t+dt )  ==>  f(t) 和 I(x, t) 並不相同 ==> f(t) 是假設視角已經隨之移動, 而看到 constant brightness!

所以 f(t) = C (constant)    因此  df(t)/dt = 0 

=> ∂I/∂x dx/dt + ∂I/∂t = 0  =>  Ix v + It = 0    => v(x) = – It / Ix


很容易看出如果 Ix = 0, 或是 I(x, t) 在 x-axis 是等亮度 (constant), 則 v 是無意義!  

因為無法分辨是否移度或是移動速度多快!

這是上述提到的 untexture area problem, 在 1D OFC 就會出現

 

How Iterative Method Refine The Velocity Vector?

NewImage

這也是用到 Brightness Constancy 的觀念。如果視角以 v 速度移度,還是看到 p 點亮度隨時間改變而非定值。

代表之前估計的 v 速度不精確。這時可以 locally 修正 v 速度以維持 p 點亮點。

如何修正 p 點亮點? 就看 p 點 local 附近的亮度以及亮度隨時間的變化。

v(new) = v(old) – It / Ix

 

Optical Flow: 2D Motion

假設 3D intensity plot 如下圖,contour plot 如下圖。

NewImage

NewImage

 

同樣 Let f(t) = I( x(t), y(t), t ) = I( x(t+dt), y(t+dt), t+dt )  ==>  f(t) 和 I(x, y, t) 並不相同

==> f(t) 是假設視角已經隨之移動, 而看到 constant brightness!

所以 f(t) = C (constant)    因此  df(t)/dt = 0 

=> ∂I/∂x dx/dt + ∂I/∂y dy/dt + ∂I/∂t = 0  =>  Ix u(x,y) + Iy v(x,y) + It = 0    

此時有兩個 variables, (u, v) two velocities.  但只有 1 constraint equation (OFC) => 無法決定唯一解!!

也就是 2D OFC 是 under-determined!


同樣可以用直觀的解釋,假設 p 點在斜坡上 (例如對應在綠色的 contour 中) 一點。假設 δt 時間 p 點的亮度減少 δI (掉到淺藍色區域中).  為了要回到原來的亮度 (brightness constancy),  需要一個 (u, v) motion vector.  
在移動 (δx = u δt, δy = v δt) 後,又會回到原來的亮度(綠色區)。 
 
注意因為我們只假設 constant brightness, 回到綠色區 (不一定是同一點) 的方式有無限多種。因為我們只有非常 local information, 沒有更多的 information (如附近的地形) 或是 global information.  
 

解決的方式(至少)有三種:

(1) 集合附近多點 (稱為 patch, 補丁, e.g. 3×3) 的 information.  

同時假設 (a) patch 的 (u, v) 都一樣 (rigid prior information); (b) patch 內有 texture 可以做 1-to-1 mapping.  這種解法把 under-determined equation 變成 over-determined equations.   這是 Lucas-Kanade method.  (a) 造出多個 equations; (b) 保証 equations 之間是 linear independent.  

(2) 用 global information to constraint local motion vectors.

例如魚群彼此會互相影響以及牽制個別魚的 local motion vectors.  如果 global constraint 是 motion vectors 儘可能平滑變化,也就是 penalize ⊽u and ⊽v, 也可以間接 constraint local motion vectors.  這是 Horn-Schunck method. 或是 Total Variation – L1 Regularization (TV-L1) method.

(3) 使用更多的 local information

目前只假設 constant brightness.  如果有更多的 local information, 例如 constant chroma, 或是 constant gradient, 或是 stereo-depth information 可以 further constraint motion vector.  

 

2D Optical Flow Problems:  Un-texture and Aperture Problems

Un-texture Problem

Un-texture 問題可以用下圖看出。在轉盤白色部份 (un-texture) 無法用 local method 找出 motion vector.

數學上就是 Ix=Iy=0.  這也是 1D un-texture 問題的 général case.  

在更高維如 3D optical flow 如 stereoscope view 也會有 un-texture problem.  在一間全白的屋中,不論如何移動也無法看出深度。

NewImage

Un-texture 問題無法用上述 (1) or (3) 解決。因為 local information 完全不足。只能用 global information 來限制。

例如上圖轉盤邊的花紋有 (u, v) vector; 轉盤上的魔術方塊也有 (u, v) vector.  如果假設 global motion vectors 是平滑。可以藉由 global constraint 得到 local motion vectors.

 

Aperture Problem

Aperture 問題可以從下圖看出。三個方向的移動都會造成同樣的”孔徑視覺”結果。

In general, 任何方向的移動搭配適當的斜紋都會有同樣的結果。

因此只從 local 條紋的變化無法唯一決定 motion vector, (u, v).

NewImage

Aperture 問題和 Un-texture 問題不同,但是相關。

Un-texture 問題是在 Ix=Iy=0 就是在 2D camera plane “任何方向” 亮度沒有變化。

 

Aperture 問題則是在 2D camera plane “一個方向” 亮度沒有變化 (gradient=0),也就是其中一個維度 degenerate.

因此任何在 gradient=0 方向的 motion 都無法偵測。

如果把 motion vector 分解為平行和垂直於 gradient=0 方向的 motion vectors.  

垂直方向的 motion vector 稱為 “normal flow”.  這是可以根據 Ix and Iy 計算出來。

但是平行方向的 motion vector 就像 un-texture 問題一樣,是無法用 local information 計算,同樣需要 global information or constraint.

下圖是簡單的數學關係。 ∇ I * U = -It = 0  (在 normal flow 垂直方向的亮度 gradient

NewImage

Optical Flow 三種方法

Local Approach (Lucas Kanade)

如上文運用 patch 有同樣的 motion vector 但仍有 texture.  可以把 under-determined OFC 轉為 over-determined equations.  運用 least square error minimization 得到 motion vector.

NewImage

NewImage

NewImage

Lucas Kanade (LK) method

NewImage

 

Global Approaches (Horn-Schunck, TV-L1)

先談 HS method.  首先定義 Energy function 

 NewImage

NewImage

藉著 variational minimization using Euler-Lagrange equations 可以得到

NewImage

或是用 iterative method 在 coupled PDEs 如下:

NewImage

Horn-Schunck (HS) method

NewImage

 

Global Approaches

再談 TV-L1.  最主要是解決 HS method heavily penalizes flow field discontinuities 問題。

重點是用 quadratic functions by L1 norm.   

NewImage

 

Total Variation – L1 Regularization (TV-L1) method

 NewImage

Improve Optical Flow: Coarse-to-fine Warping Framework

參考 Chapter 2 Optical Flow Estimation for detailed math derivation. (Stereo Scene Flow for 3D Motion Analysis)

因為 OFC 是假設 small motion or displacement.  因此在大位移時會有很大的誤差。

如何解決 large motion or displacement?   使用 coarse-to-fine image pyramid 方式

前文提到過 KS method + image pyramid.  下文是 general framework.

 

1. 是從 coarse level to fine level.  因為 coarse level 可以 capture 大的位移。

2. 每一層可以用 local (KS) or global (HS or TV-L1) method 計算 motion field.  並非只限於 local method.

3. 除了第一層以外。每一層在計算 motion field:

    (i) 都先用上一層所得到的 motion field 作 interpolation and re-scaling 做為 (Uavg, Vavg)

    (ii) transform moving image by the given flow field (warping);  

    (iii) 使用 linearized model to iterative compute small signal motion vector.  

 

NewImage

 
再用幾張 Utah slides 來說明。
 
Step 1: 首先前置工作是先處理 Image I and J, 先產生 pyramid images.  基本上是 LPF+down sampling.  一般最多四到五層就夠了。多則失去太多 details, 少則無法容納大位移。

 NewImage

 

Step 2: 開始 coarse-to-fine optical flow calculation.  從 coarse image 開始計算 optical flow (OF).  Up-sampling 之後給下一層使用。

NewImage 

Data flow 如下。Image J (pyramid layer) 先 based on 上一層的 motion vector 做 warping 變成 Jw.

再用 linearized model 和 Image I (同一 pyramid layer) 去找 small signal motion vector (可以用 local or global methods).

再把上一層的 motion vector up-sampling (large signal) + 本層的 small signal motion vector (signal signal) 合併為本層的 motion vector.

NewImage

 

Coarse-to-Fine Warping Framework

NewImage

 

Advertisements