Optical Flow Introduction

by allenlu2007

本文主要參考 Alex Work Blog 如下。

http://alex-phd.blogspot.tw/2014/03/optical-flowopencv.html

以及

IJCV2011有一篇文章,《A Database and Evaluation Methodology for Optical Flow》裡面對主流的光流算法做了簡要的介紹和對不同算法進行了評估。網址是:

Video magnification

Please refer MIT paper

 

What is Optical Flow

光流(optical flow)是什麼呢?名字很專業,感覺很陌生,但本質上,我們是最熟悉不過的了。因為這種視覺現象我們每天都在經歷。從本質上說,光流就是你在這個運動著的世界裡感覺到的明顯的視覺運動。

這種運動可以分為平行視角方向和垂直視角方向。

平行方向的運動和物體的運動速度和遠近有關。垂直方向的運動則和運動速度和視角有關。

例如在火車上往窗外看。可以看到樹、地面、建築等等,都在往後退。這個運動就是光流。而且他們的運動速度居然不一樣?這就給我們提供了一個挺有意思的信息:通過不同目標的運動速度判斷它們與我們的距離。一些比較遠的目標,例如雲、山,它們移動很慢,感覺就像靜止一樣。但一些離得比較近的物體,例如建築和樹,就比較快的往後退,然後離我們的距離越近,它們往後退的速度越快。一些非常近的物體,例如路面的標記啊,草地啊等等,快到好像在我們耳旁發出嗖嗖的聲音。

光流除了提供遠近外,還可以提供角度信息。與咱們的眼睛正對著的方向成90度方向運動的物體速度要比其他角度的快,當小到0度的時候,也就是物體朝著我們的方向直接撞過來,我們就是感受不到它的運動(光流)了,看起來好像是靜止的。當它離我們越近,就越來越大(當然了,我們平時看到感覺還是有速度的,因為物體較大,它的邊緣還是和我們人眼具有大於0的角度的)。

光流的概念是Gibson在1950年首先提出來的。它是空間運動物體在觀察成像平面上的像素運動的瞬時速度,是利用圖像序列中像素在時間域上的變化以及相鄰幀之間的相關性來找到上一幀跟當前幀之間存在的對應關係,從而計算出相鄰幀之間物體的運動信息的一種方法。一般而言,光流是由於場景中前景目標本身的移動、相機的運動,或者兩者的共同運動所產生的。

       當人的眼睛觀察運動物體時,物體的景像在人眼的視網膜上形成一系列連續變化的圖像,這一系列連續變化的信息不斷「流過」視網膜(即圖像平面),好像一種光的「流」,故稱之為光流(optical flow)。光流表達了圖像的變化,由於它包含了目標運動的信息,因此可被觀察者用來確定目標的運動情況。
       研究光流場的目的就是為了從圖片序列中近似得到不能直接得到的運動場。運動場,其實就是物體在三維真實世界中的運動;光流場,是運動場在二維圖像平面上(人的眼睛或者攝像頭)的投影。

 

Optical Flow Methodology

Optical Flow (光流法) 是 video signal processing 中非常基本卻很重要的算法。

Optical flow 同時結合 space and time signal processing. 

一般可以應用在影像移動偵和分析,物體深度,或是微動作放大 (MIT Michael Rubinstein). 

 

從 high level 來看,有兩種 methodologies. 

(a) 一種是從電磁波角度。我們可以看見物體是因為物體反射光 (or EM wave).  

當物體或是 camera 在移動時。反射光的角度就會改變。比較前後的影像的差異,就可以分析出物體的移動位置和方向。

實務上當然更複雜。因為我們不知道物體的遠近 ( 除非有 Lidar 或是 stereoscope), 光源的位置, 以及物體可能被遮擋或變形。一般會需要做一些假設。如平行光,同一物體位於同一個遠近 (物體本身沒有深度), 以及忽略遮擋和形變。

(b) 則是從流體力學角度。每一個 3D 物體的 voxel (最後成像為 2D 的 pixel) 都自己會發光 ( 當然所發的光其實是反射光,所以也是 time varying function).  物體在移動時每一個 voxel 就像流體力學的 voxel 移動發光轉換為 2D 的 pixel change.

 

(a) 和 (b) 比起來 (b) 似乎比較單純,可以應用或類比流體力學的 framework.  (a) 要考慮的問題不只是物件和場影,還有光源 (通常不在可見範圍內).  (a) 比較常用於 computer graphic, 因為是 generative model 而非 inductive model. 

 

Optical Flow 算法分類

Optical flow 算法依場景可分為兩類:  (1) sparse optical flow and (2) dense optical flow algorithms.

 

Sparse 算法基本上假設背景和鏡頭為固定,算法針對少數移動物體的 optical flow.  常見於 surveillance camera 的應用。

上述不正確。 Sparse 應是集中在一些特徵點如 edge, corners 計算 optical flow 而非移動物髒。(移動物件要更 high level 才能偵測,是 based on optical flow 的結果。倒因為果)  另外 sparse 算法也不用假設背景和鏡頭固定!  也非只用於 surveillance.    Sparse 的好處是 computation 少,比較容易用於 real-time application.    但比較不 robust, 容易受 noise or other factors 影響。

 

Dense 算法則是全景都是移動,一般用於行動裝置如手機,無人機,或車用 camera 上。

上述也不正確。 Dense 算法是全部 camera plan 的 pixel 都計算 motion vector 而非只有特徵點。

 

Sparse 算法是 dense 算法的特例。Dense 算法主要的缺點是計算量非常大。

 

Sparse optical flow 算法:  (一般需要是 local method)

Pyramidal Lucas-Kanade algorithm: 只計算某些點集的光流 (稀疏光流)。”Pyramidal Implementation of the Lucas Kanade Feature Tracker Description of the Algorithm”

上述不精確。LK method 是 local method.  因此可以只挑一些特徵點計算 motion vector.  但 LK 也可做 dense optical flow.


Dense optical flow 算法: (可以是 local or global method)

Horn-Schunck 算法 (1981): “Determining Optical Flow”

HS 是 global method and compute variational minimization.  需要用到所有 pixel motion vectors, 因此是 dense method.

Farneback 算法計算所有像素點的光流。”Two-Frame Motion Estimation Based on Polynomial Expansion”

Farneback method 是 local method.

 

另一種分類是 based on physics and math models:  

基於能量方法, 基於梯度方法, 基於匹配方法, 基於相位方法, 以及神經動力學方法。

我們先從 energy 開始。Gradient method, neural dynamic method, 或是 Bayesian (probablistic) method 都和 energy method 相關。

很多 optical flow algorithms 可視為 global energy function 的 optimization 問題:

EGlobal = EData + λ EPrior.  — (1)

EData measures optical flow 和 input image 的 consistency.  E 可視為  energy 或是 error function.

都是愈小愈好。

EPrior 是 Prior Term, which favors certain flow field over others.  例如 smoothly varying flow fields 可視為一種 prior knowledge.  其他的 prior knowledge 後面再補充。

 

Brightness Constancy (energy base; 能量方法)

I(x, y, t) = I(x+u, y+v, t+1)   — (2)  integral form

I(x,y,t) = I(x,y,t) + u ∂I/∂x + v ∂I/∂y + 1 ∂I/∂t   — (3) 

For Optical Flow Constraint equation:

u ∂I/∂x + v ∂I/∂y + ∂I/∂t  = 0    — (4) differential form

只有一個 constraint.  還缺另一個 constraint.  解決的方法至少有三種,可以參考下文

“Optical Flow Re-introduction”

 

Eq (2) or (4) 代表 per pixel constraint or error.  Aggregated error over the image 就會得到 Edata.

Horn and Schunck proposed L2 norm (1981)

NewImage

(需要由 L2 norm penalty function 來提供。(Horn and Schunck)

另一種是 L1 norm penalty function proposed by Brox (2004) and Wedel (2008).

L1 norm penalty 可以容許 motion field discontinuity.  對於 video 應用比較實用。

 

Gradient Constancy (gradient base; 梯度方法)

NewImage

實務上 gradient constancy 比起 brightness constancy 來的 robust.

不過 (7) 基本上假設 brightness 也是 constancy (除了差一個常數), 額外假設 optical flow 是 locally translational.  

 

其他的方法暫略過不表。

 

Prior Term

(1) Smooth Variation

NewImage 

(2) Rigidity Priors.

 

Optical Flow 如何可視

光流場是圖片中每個像素都有一個x方向和y方向的位移,所以在上面那些光流計算結束後得到的光流flow是個和原來圖像大小相等的雙通道圖像。那怎麼可視化呢?這篇文章用的是Munsell顏色系統來顯示。

關於孟塞爾顏色系統(MunsellColor System),可以看wikibaike。它是美國藝術家阿爾伯特孟塞爾(Albert H. Munsell,1858-1918)在1898年創製的顏色描述系統。

孟塞爾顏色系統的空間大致成一個圓柱形:

南北軸=明度(value,從全黑(1)到全白(10)。
經度=色相(hue)。把一週均分成五種主色調和五種中間色:紅(R)、紅黃(YR)、黃(Y)、黃綠(GY)、綠(G)、綠藍(BG)、藍(B)、藍紫(PB)、紫(P)、紫紅(RP)。相鄰的兩個位置之間再均分10份,共100份。
距軸的距離=色度(chroma),表示色調的純度。其數值從中間(0)向外隨著色調的純度增加,沒有理論上的上限(普通的顏色實際上限為10左右,反光、螢光等材料可高達30)。由於人眼對各種顏色的的敏感度不同,色度不一定與每個色調和明度組合相匹配。
具體顏色的標識形式為:色相+明度+色度 
下圖 show the result.
NewImage
Advertisements