光流算法比較分析研究

摘 要： 運(yùn)動(dòng)目標(biāo)檢測(cè)是計(jì)算機(jī)視覺中重要的課題，運(yùn)動(dòng)目標(biāo)的正確檢測(cè)與正確分割影響著后續(xù)目標(biāo)的跟蹤與識(shí)別；光流法是運(yùn)動(dòng)目標(biāo)檢測(cè)和分析的重要方法，它能夠在不知道任何預(yù)先場(chǎng)景情況下檢測(cè)出獨(dú)立的運(yùn)動(dòng)目標(biāo)，并且可適用于動(dòng)態(tài)場(chǎng)景的情況。首先介紹了光流的基本概念，然后介紹了常用的光流的四種算法；接著以智能交通中路口車輛視頻為例，將這四種光流算法用于車輛檢測(cè)，然后對(duì)四種光流算法的優(yōu)缺點(diǎn)進(jìn)行分析；最后對(duì)光流法在未來可能研究及改進(jìn)的方向提出展望。

關(guān)鍵詞： 光流算法； 車輛檢測(cè)； 智能交通； 計(jì)算機(jī)視覺

中圖分類號(hào)： TN911.7?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

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

光流場(chǎng)是指圖像灰度模式的表面運(yùn)動(dòng)[6]，光流是三維運(yùn)動(dòng)場(chǎng)在二維圖像平面上的投影；研究光流算法是利用圖像序列中灰度的時(shí)域、空域變化和相關(guān)性來確定圖像像素的運(yùn)動(dòng)矢量，也就是研究圖像灰度在時(shí)間上變化的大小和方向。研究光流算法的目的就是從圖像中得到運(yùn)動(dòng)目標(biāo)的運(yùn)動(dòng)矢量。因?yàn)楣饬鞯挠?jì)算不需要預(yù)先知道場(chǎng)景的信息，不需要在圖像中建立起特征之間的對(duì)應(yīng)關(guān)系，所以光流計(jì)算屬于高層次的視覺表述。目前，光流法被廣泛地應(yīng)用于目標(biāo)檢測(cè)、跟蹤、識(shí)別、物體弱運(yùn)動(dòng)，步態(tài)分析、消除波動(dòng)性干擾、3D結(jié)構(gòu)恢復(fù)以及運(yùn)動(dòng)估計(jì)等圖像處理與模式識(shí)別領(lǐng)域，也廣泛地應(yīng)用在智能交通、醫(yī)療、導(dǎo)航與制導(dǎo)、海洋、軍事和天文等領(lǐng)域。

1 研究現(xiàn)狀

光流由Gibson于1950年首先提出，在光流的基本約束方程提出之后得到廣泛發(fā)展。80年代初期，Horn和Schunck提出建立在光流平滑性假設(shè)基礎(chǔ)上的使全局能量達(dá)到最小化原則的全局光流算法[7]，可以得到百分之百的稠密光流場(chǎng)。之后Lucas和Kanade提出了使用局部領(lǐng)域最小二乘法來計(jì)算光流的局部光流算法，之后就掀起了光流研究的熱潮，提出了很多種方法。根據(jù)數(shù)學(xué)方法和相應(yīng)理論基礎(chǔ)可以將光流算法分為基于梯度的方法、基于區(qū)域的方法、基于能量的方法、基于相位的方法和神經(jīng)動(dòng)力學(xué)法。然而在計(jì)算光流的時(shí)候，大位移和孔徑問題是光流計(jì)算的難點(diǎn)，因?yàn)閺膱D像灰度的變化不能確定像素的真實(shí)運(yùn)動(dòng)矢量[8]。

1.1 基于梯度的方法

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

微分法假設(shè)光流是連續(xù)的，再附加一定的約束條件，將光流的計(jì)算問題轉(zhuǎn)化成最小化泛函能量的數(shù)學(xué)極值問題。成熟的數(shù)學(xué)優(yōu)化理論為求解光流矢量創(chuàng)造了條件。

1.2 塊匹配法

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

1.3 基于能量法的方法

在頻率域中設(shè)像素點(diǎn)[X=x，y]的速度為[V]，[V=（u，v）T，]根據(jù)式（1）：

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

進(jìn)行傅里葉變換，結(jié)果如下：

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

式中[δ?]為狄里克利函數(shù)。

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

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

1.4 相位法

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

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

[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 光流的幾種計(jì)算方法

2.1 HS全局光流算法

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

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

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

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

這個(gè)值越小表示相鄰像素間變化越小，光流場(chǎng)越平滑。設(shè)[e2c]為全局平滑表達(dá)式為：

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

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

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

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

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

求解式（10）使得[Ehs]達(dá)到最小值的方法是解歐拉方程，使得[Ehs]關(guān)于[u，v]的導(dǎo)數(shù)為零。采用遞歸算法最后得到光流值為：

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

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

當(dāng)[n=0]時(shí)就是光流的初始值，這個(gè)值影響著光流的收斂速度，當(dāng)相鄰兩次迭代后光流值之差小于一個(gè)很小的數(shù)時(shí)，迭代結(jié)束，調(diào)節(jié)[λ]可以調(diào)節(jié)平滑約束量的比重。

2.2 LK局部平滑光流算法

局部平滑約束由Lucas和Kanade首次提出，假設(shè)圖像局部平滑，即假設(shè)在一個(gè)較小的空間領(lǐng)域[Ω]上運(yùn)動(dòng)矢量保持衡定，通過聯(lián)立窗口內(nèi)所有像素，使用最小二乘法估計(jì)光流，能得到稀疏光流場(chǎng)，具有較強(qiáng)的魯棒性。

在一個(gè)較小的空間領(lǐng)域[Ω]上，引入權(quán)系數(shù)后光流估計(jì)誤差定義為：

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

式中：[Wx]表示窗口權(quán)重函數(shù)，窗口中心部分對(duì)光流約束的貢獻(xiàn)大，權(quán)重要高。

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

[w=ATW2A-1ATW2b] （14）

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

但是當(dāng)[ATW2A]不可逆的時(shí)候，光流場(chǎng)無解。

2.3 BM塊匹配光流算法

塊匹配光流算法是將視頻劃分為確定大小的圖像子塊，每個(gè)圖像子塊中所有像素假設(shè)具有相同的位移，也就是說具有相同的光流場(chǎng)，每個(gè)圖像塊只做平移運(yùn)動(dòng)，這樣只要每個(gè)圖像子塊只要計(jì)算一個(gè)光流矢量就可以得到整個(gè)圖像塊中的所有像素的運(yùn)動(dòng)矢量。當(dāng)塊比較小時(shí)，假設(shè)圖像子塊中具有相同的位移是成立的。

2.4 PryLK金字塔光流算法

傳統(tǒng)的光流算法只有在小位移的條件下才滿足灰度連續(xù)性假設(shè)，而在大位移下圖像灰度將不連續(xù)，造成光流估計(jì)失敗。

為了計(jì)算運(yùn)動(dòng)目標(biāo)快速移動(dòng)情況下的光流，引入了在LK局部平滑光流算法的基礎(chǔ)上進(jìn)行金字塔分層迭代來計(jì)算光流場(chǎng)。將圖像進(jìn)行金字塔分層，在金字塔的最上層圖像的分辨率最低，這樣由最上層開始計(jì)算光流值，計(jì)算的結(jié)果加上上一層的初始值作為下一層的光流初值，再對(duì)下一層計(jì)算光流場(chǎng)，在除最高層外的其他層進(jìn)行光流迭代，迭代到最后一層就形成光流矢量。

3 四種光流算法性能分析

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

由圖1可知，LK光流算法的計(jì)算時(shí)間為15 ms，HS光流算法的計(jì)算時(shí)間為62 ms，PryLK金字塔光流算法的計(jì)算時(shí)間為15 ms，BM塊匹配光流算法的計(jì)算時(shí)間為16 ms，其中箭頭代表光流矢量的方向，橫線長(zhǎng)度代表光流的大小，通過各種光流算法的計(jì)算時(shí)間分析可知，HS光流算法消耗的時(shí)間最多，PryLK光流算法消耗時(shí)間最少，因?yàn)镠S光流算法是對(duì)圖像中的每一個(gè)像素計(jì)算光流場(chǎng)，而PryLK光流算法是對(duì)特征點(diǎn)計(jì)算金字塔光流場(chǎng)。

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

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

4 光流技術(shù)的研究方向

光流算法可以得到運(yùn)動(dòng)點(diǎn)的速度和方向，通過光流場(chǎng)的分析可以得知光流技術(shù)的研究方向有如下幾點(diǎn)：

（1）通過光流算法得到全局光流場(chǎng)，對(duì)光流場(chǎng)進(jìn)行聚類分析，檢測(cè)運(yùn)動(dòng)物體。

（2）可以通過分析光流場(chǎng)，解決由于相機(jī)抖動(dòng)，或則樹葉的擺動(dòng)等引起的波動(dòng)式干擾，因?yàn)檫@些波動(dòng)式干擾造成光流矢量呈現(xiàn)周期性變化的趨勢(shì)。

（3）通過光流預(yù)測(cè)進(jìn)行運(yùn)動(dòng)目標(biāo)的跟蹤。

（4）光流法可以得到亞像素級(jí)的運(yùn)動(dòng)矢量，可以用光流技術(shù)進(jìn)行步態(tài)分析。

（5）由于光流法是計(jì)算物體間的相對(duì)運(yùn)動(dòng)，所以可以用光流技術(shù)來實(shí)現(xiàn)動(dòng)態(tài)背景下的目標(biāo)檢測(cè)與跟蹤。

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

參考文獻(xiàn)

[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] 馬頌德，張正友.計(jì)算機(jī)視覺：計(jì)算理論與算法基礎(chǔ)[M].北京：科學(xué)出版社，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.