光流算法比較分析研究

摘 要： 運動目標檢測是計算機視覺中重要的課題，運動目標的正確檢測與正確分割影響著后續目標的跟蹤與識別；光流法是運動目標檢測和分析的重要方法，它能夠在不知道任何預先場景情況下檢測出獨立的運動目標，并且可適用于動態場景的情況。首先介紹了光流的基本概念，然后介紹了常用的光流的四種算法；接著以智能交通中路口車輛視頻為例，將這四種光流算法用于車輛檢測，然后對四種光流算法的優缺點進行分析；最后對光流法在未來可能研究及改進的方向提出展望。

關鍵詞： 光流算法； 車輛檢測； 智能交通； 計算機視覺

中圖分類號： TN911.7?34 文獻標識碼： A 文章編號： 1004?373X（2013）13?0039?04

Comparative analysis of optical flow algorithms

ZHANG Jia?wei1， ZHI Rui?feng2

（1. North China University of Technology， Beijing 100144， China； 2. Tianshui Power Supply Corporation， Tianshui 741000， China）

Abstract： Moving object detection is currently one of the most active subjects in the domain of computer vision. Moving object detection and segmentation influence tracking and classification of the follow?up objects. Optical flow algorithm is an important method for moving object detection and analysis. It can detect the independent moving object in unknown scene and dynamic scene. The basic concept of optical flow is introduced in this paper at first and then the four common optical flow algorithms， which are applied to detection of vehicles at the crossroads in intelligent transportation video. The advantages and disadvantages of the four optical flow algorithms are analyzed while possible researches and modified direction prospect of the optical flow algorithms are proposed at the end.

Keywords： optical flow algorithm； vehicle detection； intelligent transportation； computer vision

0 引 言

基于視頻的運動目標檢測的目的就是要在序列圖像中將運動目標從場景中提取出來。但是由于光照的影響、風吹、樹葉擺動、運動目標陰影、攝像機抖動以及運動目標的遮擋現象給運動目標的正確檢測造成了極大的困難。運動目標能否正確檢測和分割影響著后續運動目標能否正確跟蹤與識別，因此運動目標檢測成了計算機視覺中的一項重要課題。傳統的運動目標檢測方法有光流算法[1?2]，幀間差分法[3]，背景建模法[4]和運動能量法[5]。背景建模法通過建立背景模型，然后將當前幀中每個像素點與背景模型進行比較來確定背景圖像。但是背景往往會隨著時間的推移發生變化，需要時刻更新背景圖像，需要背景圖像自適應的更新。幀間差分法可以適應環境的動態變化，可以實現運動目標的實時檢測，但檢測出的目標存在空洞嚴重且不連續。

光流場是指圖像灰度模式的表面運動[6]，光流是三維運動場在二維圖像平面上的投影；研究光流算法是利用圖像序列中灰度的時域、空域變化和相關性來確定圖像像素的運動矢量，也就是研究圖像灰度在時間上變化的大小和方向。研究光流算法的目的就是從圖像中得到運動目標的運動矢量。因為光流的計算不需要預先知道場景的信息，不需要在圖像中建立起特征之間的對應關系，所以光流計算屬于高層次的視覺表述。目前，光流法被廣泛地應用于目標檢測、跟蹤、識別、物體弱運動，步態分析、消除波動性干擾、3D結構恢復以及運動估計等圖像處理與模式識別領域，也廣泛地應用在智能交通、醫療、導航與制導、海洋、軍事和天文等領域。

1 研究現狀

光流由Gibson于1950年首先提出，在光流的基本約束方程提出之后得到廣泛發展。80年代初期，Horn和Schunck提出建立在光流平滑性假設基礎上的使全局能量達到最小化原則的全局光流算法[7]，可以得到百分之百的稠密光流場。之后Lucas和Kanade提出了使用局部領域最小二乘法來計算光流的局部光流算法，之后就掀起了光流研究的熱潮，提出了很多種方法。根據數學方法和相應理論基礎可以將光流算法分為基于梯度的方法、基于區域的方法、基于能量的方法、基于相位的方法和神經動力學法。然而在計算光流的時候，大位移和孔徑問題是光流計算的難點，因為從圖像灰度的變化不能確定像素的真實運動矢量[8]。

1.1 基于梯度的方法

基于梯度的方法又稱為微分法，利用時空梯度函數，使得全局能量泛函達到最小化來計算像素的速度矢量。由于微分法具有強大的數學理論支持，所以得到了廣泛研究和應用。常用的代表有Lucas?Kanade局部平滑法[9]、Horn?Schunck全局平滑法[7]、以及Nagel的有向平滑法[10]。Horn?Schunck光流法是在光流基本約束方程的基礎上附加了全局平滑假設，使得泛函能量函數達到最小化。Lucas和Kanade使用局部平滑假設，假設一個窗口內的所有像素具有相同的運動矢量。Nagel采用有向平滑約束假設，使用加權Hessian矩陣對梯度進行不同方向上的平滑處理。Black和Anandan提出分段平滑的方法來對多目標進行估計[11]。

微分法假設光流是連續的，再附加一定的約束條件，將光流的計算問題轉化成最小化泛函能量的數學極值問題。成熟的數學優化理論為求解光流矢量創造了條件。

1.2 塊匹配法

匹配法，也叫區域匹配法，研究的是區域匹配問題，塊匹配法認為上一幀中某個區域，在下一幀中會形成對應的模式，塊匹配光流定義為相鄰兩幀中，相應區域塊之間產生最佳擬合的位移。假設連續兩幀圖像[f1]和[f2]，對于圖像[f1]中的每個像素點[x，y]，以此像素為中心建立一個大小為16×16的相關窗[Wc]，一般來說16×16大小的塊已經可以滿足要求了，再圍繞圖像中對應點[x，y]，建立一個圖像搜索窗[Ws]，搜索窗口不能太小也不能太大，可根據最大可能位移的先驗知識來確定。相似性度量一般常用像素差平方和（SSD）、平均絕對誤差（MAD）以及均方差誤差函數（MSE）來進行。可進行各種快速搜索算法如三步搜索法來進行搜索，使得誤差函數達最小值的位移就是光流矢量。

1.3 基于能量法的方法

在頻率域中設像素點[X=x，y]的速度為[V]，[V=（u，v）T，]根據式（1）：

[IX，t=IX-Vt，0] （1）

進行傅里葉變換，結果如下：

[I～k，w=I0～kδw+VTk] （2）

式中[δ?]為狄里克利函數。

使用基于能量的方法來計算光流是利用調諧濾波器的輸出能量達到最大來計算光流，調諧濾波器是在頻域中進行設計的，因而基于能量的方法也叫做基于頻率的方法。Heeger等人建立了一個在式（1）和式（2）的基礎上，進行局部光流計算的模型[12]，成為基于能量法的代表。Heeger在頻率空間平面和時空能量上采用最小二乘法擬合來估計光流，使用Gabor濾波器來提取局部能量，Gabor濾波器有多個尺度參數，多個方向，它們是對不同頻率和方向的調諧。對于一個簡單的平移運動，Gabor濾波器的響應都集中在一個平面上。使式（3）最小化，即可求得光流：

[fu，v=i=112mi-miEiu，vEiu，v2] （3）

1.4 相位法

相位信息用以計算光流由Fleet和Jepson首次提出[13]。在計算光流的時候圖像上的相位信息往往比亮度信息更加可靠。所以利用相位信息獲得的光流場更加具有魯棒性。

將二維圖像變換到頻率域中，變換如下：

[IX，t=I0X，n-Vt] （4）

式中[n=（sinα，-cosα）]，[α]是圖像的屬性角。

通過帶通濾波器，圖像的相位為：

[RX，t=ρX，texpiφX，t] （5）

式中：[ρ]為濾波器輸出的幅值；[φ]為相角。

最后，光流為：

[Vn=sn， s=-φtx，t?φx，t， n=φx，t?φx，t] （6）

式中：[s]代表速率；[n]代表法向單位矢量；[?φ=][φxx，t，φyx，tT]為相位梯度。

2 光流的幾種計算方法

2.1 HS全局光流算法

Horn?Schunck在光流基本約束方程的基礎上，結合光流全局平滑條件，既在相鄰像素間光流不會突變，從而解決了孔徑問題。其假設光流場同時滿足基本方程和全局平滑條件。

全局平滑條件可以用光流矢量梯度平方來表示：

[?u2+?v2=?u?x2+?u?y2+?v?x2+?v?y2] （7）

式中：[u，v]分別是[x，y]方向上的光流。

這個值越小表示相鄰像素間變化越小，光流場越平滑。設[e2c]為全局平滑表達式為：

[e2c=?u2+?v2=u2x+u2y+v2x+v2y] （8）

光流基本約束方程就是要使得相鄰兩幀間像素偏差達到最小，設[e2b]為光流基本約束條件，表達式為：

[e2b=fxu+fyv+ft] （9）

要求得光流矢量就是要使得[e2c]和[e2b]都到達最小，就是要使得式（10）的泛函能量達到最小值。

[Ehs=α2e2c+e2bdxdy=α2u2x+u2y+v2x+v2ydxdy] （10）

求解式（10）使得[Ehs]達到最小值的方法是解歐拉方程，使得[Ehs]關于[u，v]的導數為零。采用遞歸算法最后得到光流值為：

[un+1=un-IxIxun+Iyvn+Itλ+I2x+I2y] （11）

[vn+1=vn-IxIxun+Iyvn+Itλ+I2x+I2y] （12）

當[n=0]時就是光流的初始值，這個值影響著光流的收斂速度，當相鄰兩次迭代后光流值之差小于一個很小的數時，迭代結束，調節[λ]可以調節平滑約束量的比重。

2.2 LK局部平滑光流算法

局部平滑約束由Lucas和Kanade首次提出，假設圖像局部平滑，即假設在一個較小的空間領域[Ω]上運動矢量保持衡定，通過聯立窗口內所有像素，使用最小二乘法估計光流，能得到稀疏光流場，具有較強的魯棒性。

在一個較小的空間領域[Ω]上，引入權系數后光流估計誤差定義為：

[Elk=x，y∈ΩW2xfxu+fyv+ft2] （13）

式中：[Wx]表示窗口權重函數，窗口中心部分對光流約束的貢獻大，權重要高。

通過最小二乘法來求解式（13） 可以得到：

[w=ATW2A-1ATW2b] （14）

式中：[A=fxx1，fyx1T，…，fxxn，fyxnT；][W=][Wx1，…，Wxn；b=-Itx1，…，ItxnT。]

但是當[ATW2A]不可逆的時候，光流場無解。

2.3 BM塊匹配光流算法

塊匹配光流算法是將視頻劃分為確定大小的圖像子塊，每個圖像子塊中所有像素假設具有相同的位移，也就是說具有相同的光流場，每個圖像塊只做平移運動，這樣只要每個圖像子塊只要計算一個光流矢量就可以得到整個圖像塊中的所有像素的運動矢量。當塊比較小時，假設圖像子塊中具有相同的位移是成立的。

2.4 PryLK金字塔光流算法

傳統的光流算法只有在小位移的條件下才滿足灰度連續性假設，而在大位移下圖像灰度將不連續，造成光流估計失敗。

為了計算運動目標快速移動情況下的光流，引入了在LK局部平滑光流算法的基礎上進行金字塔分層迭代來計算光流場。將圖像進行金字塔分層，在金字塔的最上層圖像的分辨率最低，這樣由最上層開始計算光流值，計算的結果加上上一層的初始值作為下一層的光流初值，再對下一層計算光流場，在除最高層外的其他層進行光流迭代，迭代到最后一層就形成光流矢量。

3 四種光流算法性能分析

通過上述四種光流算法的原理，以路口車輛視頻為例，用上述四種光流算法分別進行實驗，設計了一個演示界面。實驗平臺為：VC 6.0，Opencv 1.0，Windows XP，Intel Pentium Dual Cor?e，1.86 GHz（2CPU），1G RAM，測試圖像為640×480。實驗結果如圖1所示。

由圖1可知，LK光流算法的計算時間為15 ms，HS光流算法的計算時間為62 ms，PryLK金字塔光流算法的計算時間為15 ms，BM塊匹配光流算法的計算時間為16 ms，其中箭頭代表光流矢量的方向，橫線長度代表光流的大小，通過各種光流算法的計算時間分析可知，HS光流算法消耗的時間最多，PryLK光流算法消耗時間最少，因為HS光流算法是對圖像中的每一個像素計算光流場，而PryLK光流算法是對特征點計算金字塔光流場。

圖1 HS，LK，BM，PryLK光流算法演示界面

各種算法滿足實時性要求只是最基本的要求，關鍵是比較車輛檢測的效果，通過觀察圖1可以得到如下結論：BM塊匹配、HS光流算法都有較大的干擾，因為HS光流算法是全局光流算法，對噪聲比較敏感，但卻能得到稠密的光流場。LK和PryLK光流算法對噪聲具有一定的魯棒性，但只能得到稀疏的光流場，在實驗中通過光流場的計算可以得到運動矢量，包括運動速度和運動方向，所以說根據光流算法來進行車輛檢測可以得到車輛的速度與方向，這是其他車輛檢測技術不可比擬的。利用光流的方向可以在路口進行逆行檢測，利用光流速度可以對車輛超速違章進行檢測。

4 光流技術的研究方向

光流算法可以得到運動點的速度和方向，通過光流場的分析可以得知光流技術的研究方向有如下幾點：

（1）通過光流算法得到全局光流場，對光流場進行聚類分析，檢測運動物體。

（2）可以通過分析光流場，解決由于相機抖動，或則樹葉的擺動等引起的波動式干擾，因為這些波動式干擾造成光流矢量呈現周期性變化的趨勢。

（3）通過光流預測進行運動目標的跟蹤。

（4）光流法可以得到亞像素級的運動矢量，可以用光流技術進行步態分析。

（5）由于光流法是計算物體間的相對運動，所以可以用光流技術來實現動態背景下的目標檢測與跟蹤。

在復雜環境下，比如道路十字路口，因環境較復雜，環境干擾較大，再加上光流技術對光線、環境比較敏感，所以必須對光流技術進行改進。從近年來光流研究中可以看出，在設計光照與濾波的基礎上無法完全解決光照問題，近年來很多人將光流技術與幀差法、背景建模、圖像直方圖結合起來對車輛進行檢測。可以看出，光流技術融合其他車輛檢測技術將會是光流技術的發展方向。而解決光流算法對光照敏感，提高光流計算準確性，降低光流算法的計算時間將成為光流技術的關鍵問題。

參考文獻

[1] IKETANI A， KUNO Y， et al. Real time surveillance system detecting persons in complex scenery [C]// Proceedings of Image Analysis and Processing. [S.l.]： [s.n.]， 1999： 11?17.

[2] BARRON J， FLEET D， BEAUCHEMIN S. Performance of optical flow techniques [J]. International Journal of Computer Vision， 1994， 12（1）： 42?77.

[3] ANDERSON C， BURT P， VAN DER WAL G. Change detection and tracking using pyramid transformation techniques [J]. SPIE， 1985， 579： 72?78.

[4] COLLINS R T， LIPTON A， ALAN J， et al. A system for video surveillance and monitoring， CMU?RI?TR?00?12 [EB/OL]. [2003?12?21]. http：//www.cs.cmu.edu.

[5] WILDES R P. A measure of motion salience for surveillance application [C]// Proceedings of IEEE International Conference on Image Processing. [S.l.]： IEEE， 1998： 183?187.

[6] 馬頌德，張正友.計算機視覺：計算理論與算法基礎[M].北京：科學出版社，1998.

[7] HORN B K， SCHUNCK B. Determining optical flow [J]. Artificial Intelligence Laboratory， 1981， 17（1）： 185?203.

[8] LUCAS B D， KANADE T. An iterative image registration technique with an application to stereo vision [C]// Proceedings of the 7th International Joint Conference on Artificial Intelligence. [S.l.]： IJCAI， 1981： 674?679.

[9] NAGEL H H， ENKELMANN W. An investigation of smoothness constraints for the estimation of displacement vector field from image sequences [J]. IEEE Trans. on Pattern Analyze and Machine Intelligence， 1986， 8（5）： 565?593.

[10] BLAEK M J， ANANDAN. The robust estimation of multiple motions： parametric and piecewise smooth flow fields [J]. Computer Vision and Image Understanding， 1996，63（1）： 75?104.

[11] HEEGER D J. Model for the extraction of image flow [J] Optical Society of America， 1987， A4（8）： 1455?1471.

[12] FLEET D J， JEPSON A D. Computation of component image?velocity form local phase information [J]. International Journal of Computer Vision， 1990， 5（1）： 77?104.

[13] GROSSBERG S， MINGOLLAA E. Neural dynamics of visual motion perception： local detection and global grouping [C]// Neural Networks for Vision and Image Processing. Massachusetts： MIT Press， 1992： 293?342.

[14] FAY D， WAXMAN A M. Neurodynamics of real?time image velocity extraction [C]// Neural Networks for Vision and Image Processing. Massachusetts： MTT Press， 1992： 221?246.