光流算法研究

張 拯，賈鶴萍

（1.太原理工大學材料科學與工程學院，太原 030024；2.山西大學物理電子工程學院，太原 030006）

光流算法研究

張 拯1，賈鶴萍2

（1.太原理工大學材料科學與工程學院，太原 030024；2.山西大學物理電子工程學院，太原 030006）

光流的測量是視頻序列處理和視頻挖掘中的基本問題。首先簡述了光流法的基本原理，即物體亮度不變特性；然后闡述了計算光流的4類算法：微分方法、區(qū)域匹配方法、基于能量的方法和基于相位的方法，并對當前主流的能量算法進行了詳細探討；最后對各種光流算法的評測方法與測試集進行了說明。

光流法，運動檢測，能量法，視頻挖掘

0 引言

光流是指空間運動物體在觀測成像面上的像素運動的瞬時速度。光流的測量是視頻序列處理和視頻挖掘中的基本問題，它主要用于運動物體檢測、識別與跟蹤等。光流的思想最早由Gibson在1950年提出，而對光流的計算，則源于Horn、Schunck［1］和 Lucas、Kanade［2］等人的研究。但Horn-Schunck和Lucas-Kanade算法局限性較大，抗噪能力不強，因此，作為一個被廣泛關(guān)注的研究領(lǐng)域，幾十年來一直有改進算法和新算法出現(xiàn)。

1 光流法基本原理

光流法的基本原理是物體亮度的不變特性，即對于空間移動物體上的一個點，在時間序列的不同時刻上，該點的亮度是不變的。對于一個二維的圖像，可以用表示圖像上坐標為的點在t時刻的亮度值。在t時刻，空間中移動的物體上有一點，經(jīng)過一段時間δt，該點在圖像平面上位移到了，根據(jù)亮度不變特性可以得到：

利用泰勒展開式可以得到：

由泰勒公式知，高階微量ε是趨向于0的，于是有：

即有

可以簡化寫成

式中，Ix、Iy表示圖像平面相對x、y軸方向的強度變化，It表示同一個像素點在相鄰時刻（連續(xù)圖像上同一個像素點）的強度變化

2 光流算法

光流的計算方法大多數(shù)是建立在Horn-Schunck算法和Lucas-Kanade算法基礎(chǔ)之上，其基本假設(shè)一般為：亮度不變和圖像全局平滑。改進算法的研究主要集中在如何削弱以上假設(shè)以及提高算法的抗噪性。按照Barron［4］在1994年提出的分類方法，光流算法可以分為微分方法、區(qū)域匹配方法、基于能量的方法和基于相位的方法等4類。

2.1 微分方法

微分方法是利用視頻序列中圖像灰度（或其濾波形式）的時空微分，計算像素瞬時速度的方法。其典型代表是Horn-Schunck算法，它結(jié)合亮度不變假設(shè)和圖像全局平滑假設(shè)，估算光流場

基于此思想，一些改進算法不斷提出：Nagel［7］采用有條件的平滑約束，通過約束條件構(gòu)造加權(quán)矩陣，利用加權(quán)矩陣的控制對梯度進行不同平滑處理；Black 和 Anandan［8］針對多運動的估計問題，提出了分段平滑的計算方法。Lucas-Kanade算法則是假設(shè)在一個很小的臨近范圍內(nèi)光流為常數(shù)，由此通過最小二乘法解出超正定方程組的解。Jodoin［9］提出了一個忽略邊緣的算法，利用最小二乘法計算出了一個小運動區(qū)域，可以證明該區(qū)域是多峰區(qū)域，合理地處理了銳利邊緣的情況。Bruhn［10］等提出將Horn-Schunck算法中的全局方法與Lucas-Kanade算法中的局部方法結(jié)合起來，即將全局方法中的稠密光流和局部方法的魯棒性結(jié)合起來。

微分方法大多根據(jù)亮度不變和平滑假設(shè)得出光流方程，因此，比較容易受到光照的影響，抗噪能力不足，此外還存在相關(guān)參數(shù)的選取比較困難等問題。

2.2 區(qū)域匹配方法

在區(qū)域匹配方法中，光流被定義為不同時刻圖像區(qū)域之間所產(chǎn)生最佳擬合的位移。區(qū)域匹配則是通過諸如 SSD（Sum-of-Squared Difference）、互信息或相關(guān)系數(shù)等相似度測量的最大化，實現(xiàn)區(qū)域的最優(yōu)匹配。

Singh［11］提出了一種兩步驟的區(qū)域匹配方法。第1步對視頻中相鄰的3張通過帶通濾波處理 過 的圖像 I-1、I0、I1進行 SSD 計 算；然后將轉(zhuǎn)換到概率分布。光流可被估算為該分布的均值。Anandan［12］提出的方法是基于拉普拉斯金字塔和由粗到細的SSD匹配策略。

在基于區(qū)域匹配的方法中，如何選擇區(qū)域問題，目前尚無明確的標準；而計算的復雜度也和選取區(qū)域的大小有關(guān)；由于SSD是單峰的，選取區(qū)域的大小還會影響最終的估計效果。

2.3 基于能量的方法

基于能量的方法是目前光流計算的主流算法。其基本思路是將光流計算轉(zhuǎn)化為一個全局能量函數(shù)在一系列約束條件下的最優(yōu)化問題。通常還會采用罰函數(shù)法將有約束的優(yōu)化問題進一步轉(zhuǎn)化為無約束的優(yōu)化問題。

能量函數(shù)一般表達式為：

其中，EData為數(shù)據(jù)項，用于表征輸入圖像中光流的不變性，如亮度不變、梯度不變等。由于EData中約束條件較少，故需要增加其他先驗的約束條件才可以解出。故式（3）中引入先驗項EPrior。一般而言，EPrior為平滑約束?；谀芰糠椒ǖ难芯?，實質(zhì)上就是圍繞EData、EPrior的選取與能量函數(shù)的最優(yōu)化進行，以下分別闡述之。

2.3.1 數(shù)據(jù)項選擇

數(shù)據(jù)項定義了各種不變性的假設(shè)：亮度不變、梯度不變、Hessian矩陣不變、梯度范數(shù)不變、Hessian范數(shù)不變、Hessian行列式不變等［13］。此外，部分文獻［14-15］提出時空信號（即圖像）在時間t和t+1是高度相關(guān)的，由此來定義數(shù)據(jù)項的不變約束［16］。Xiang［17］等則將圖像LUV色彩信息與亮度不變約束結(jié)合起來，以加權(quán)鄰域最小二乘法求解光流，同時利用LUV中的U和V來確定加權(quán)系數(shù)。

最常用的光流計算的不變性為亮度不變假設(shè)和梯度不變假設(shè)。其中，亮度不變假設(shè)是指像素在畫面中移動時，其強度或顏色保持不變，即其約束方程為式（2）。

亮度不變假設(shè)容易受到光照的影響，但是光照的變化只會改變光流梯度的大小，而不會改變光流梯度的方向?；诖耍梢愿鶕?jù)光流梯度方向的不變性，給出如下的約束條件：

各種不變性假設(shè)均有其優(yōu)點與局限性，因此，Papenberg［13］等對多種不變性的線性組合進行研究。

不變性假設(shè)是針對各個像素點定義的，由此也在像素點上引入誤差。因此，數(shù)據(jù)項的定義需要將各個像素點的誤差疊加起來。在Horn-Schunck算法中，數(shù)據(jù)項采用2范數(shù)定義為：

但采用2范數(shù)隱含了誤差呈高斯分布的假設(shè)，這一點在實際中未必成立。Black［8］等提出一種基于魯棒估計，他使用具有魯棒性的罰函數(shù)的算法。在各類罰函數(shù)中，當前被廣泛接受的是［18-21］采用1范數(shù)或其變體：

式中，E為誤差Ex，y的向量，ε為一個小的正數(shù)，可以取為一個固定的值。

根據(jù)處理思想的不同，式（5）可以變換出很多其他的罰函數(shù)方程。如Brox［18］等認為二次的罰函數(shù)對最后的估計結(jié)果影響較大，提出了凹函數(shù)作為罰函數(shù)，具體的數(shù)據(jù)項能量函數(shù)為

主要試驗如下：①膨脹試驗，包括自由膨脹和限制膨脹試驗；②壓汞試驗，通過計算汞壓入量間接確定孔隙的孔徑大小，適合干燥試樣；③核磁共振試驗，通過核磁共振技術(shù)測定含水狀態(tài)下的孔隙分布，測試原理見參考文獻[13]；④XRD試驗，通過XRD方法確定晶體礦物；⑤SEM試驗，觀察試樣的微觀形貌。

2.3.2 先驗項選擇

一個最簡單的先驗項就是依據(jù)光流場中的一階微分來計算。例如Horn-Schunck算法中就是利用2范數(shù)表示先驗項：

先驗項的罰函數(shù)構(gòu)造方法與數(shù)據(jù)項類似。Black［22］假設(shè)光流場中梯度遵循高斯獨立同分布，采用了二階范數(shù)作為罰函數(shù)；當前更為被廣泛接受的是一階范數(shù)，如 Brox［18］、Wedel［19］等就采用了一階范數(shù)。

在確定罰函數(shù)后，一般是對每個導數(shù)各自使用罰函數(shù)，然后將其相加；或先將梯度的平方或絕對值相加，然后對其使用罰函數(shù)。

對罰函數(shù)賦予空間各異和各向異性權(quán)重是先驗項細化的常用手段。例如在Horn-Schunck算法中對罰函數(shù)賦予空間各異的權(quán)重：

式中，權(quán)重函數(shù)具體值和該點亮度有關(guān)，這樣在圖像邊緣處，其亮度值較低，權(quán)重也低，而邊緣處一般最容易受到噪聲的影響，這樣通過權(quán)重函數(shù)便可以降低對圖像全局平滑的要求。

此外，在先驗項中，除了一階微分外，高階微分可能會帶來更精確的運動估計。如Trobin［26］引入二階微分，采用圓諧函數(shù)將二階微分算子變換到一個正交空間，在此基礎(chǔ)上對能量進行優(yōu)化。與此相關(guān)的，過參數(shù)化（Over-parameterized）在光流計算中也得到了應用，如 Nir［27］等。

2.3.3 最優(yōu)化

最優(yōu)化算法可分為連續(xù)優(yōu)化與離散優(yōu)化兩大類。常見的連續(xù)優(yōu)化算法有梯度下降算法和變分法等。梯度下降算法中以梯度函數(shù)作為衡量計算精確度的標準，如果迭代使得梯度函數(shù)下降，那么計算結(jié)果就更加精確。為了達到一定的精確度，可以通過設(shè)定一個閾值，作為迭代終止的條件。例如Baker［28］介紹了高斯牛頓法、牛頓法和Levenberg-Marquardt等。

最為常用的連續(xù)優(yōu)化算法為變分法［1，10，18，25，27］，即假設(shè)全局能量函數(shù)可寫為如下形式：

除了以上介紹的兩種主要算法，其他文獻也提出了一些獨特的方法。如Wedel［19］采取了分步優(yōu)化的策略：

而對于離散優(yōu)化，一般采用的方法有融合方法［26，29-30］和稀疏狀態(tài)空間動態(tài)重參數(shù)化方法［31-32］。在采用離散優(yōu)化后，還可以繼續(xù)采用連續(xù)優(yōu)化來進一步精細結(jié)果。

一些其他的處理思路也值得借鑒。Xu［33］給出了一個魯棒的全變差方法，這種算法不要求光流場是全局平滑的，并且允許光照的變化，它能夠有效地克服噪聲的影響。Figueira［34］利用光流法從人機混合環(huán)境中分析出人物，改進了以前的光流法，提出一種標準化光流向量，根據(jù)現(xiàn)實生活中人的動作在圖像中的映射關(guān)系，另外通過對目標在空間域上的位移來進行時間采樣，從而克服了噪聲的影響，保持了系統(tǒng)的穩(wěn)定性。

2.4 基于相位的方法

Fleet［35］提出了利用相位信息來計算光流。光流可以從帶通濾波器輸出的相位特性來確定，因此，被稱為相位法。相位模型實際上是將問題轉(zhuǎn)化到頻域上研究。光流的分速度為垂直與帶通速度濾波器輸出中的等相位輪廓瞬時運動，帶通速度濾波器按照尺度、速度和方向分離輸入信號。帶通速度濾波器的輸出為：為輸出信號的幅值，為輸出的信號的相位。

相位方法有一定的復雜度，同時，雖然帶通濾波器輸出的相位分量比幅值分量更穩(wěn)定，但在相位奇點的鄰域內(nèi)，也可能不穩(wěn)定。此外，相位方法對圖像序列中的時間混疊比較敏感。

2.5 其他方法與實現(xiàn)技術(shù)

除了以上提到的主要方法，還有一些其他的解決思路。如Fay［36］等模擬視網(wǎng)膜中時空處理和大腦視覺運動，基于并聯(lián)動力學提出一個多層神經(jīng)網(wǎng)絡(luò)用于提取畫面邊緣的法向速度；Tagliasacchi［37］提出利用進化計算進行光流估算；Seitz［38］則將光流計算轉(zhuǎn)變?yōu)閷ふ乙粡垐D像到另一張圖像的時空線性濾波，通過對亮度、模糊以及其他外觀變化，建模為不同的濾波器，采用線性規(guī)劃對此進行全局優(yōu)化。

3 光流法性能比較

光流法性能評測的規(guī)范化與標準化最早由Barron［4］等人在1994年提出，共針對9種算法及其變體以及不同的參數(shù)進行了評測，評測采用的測試集包括已知運動場的人造視頻序列和真實的視頻場景，評測標準為角度差（AE），統(tǒng)計量為均值與標準差。此后，2007 年，Baker［6］等設(shè)計了新的測試數(shù)據(jù)庫，對近年來出現(xiàn)的幾十種主要光流算法進行了評測，其評測標準增加了光流終點差（EE）以及歸一化插值誤差（NE），在統(tǒng)計量上增加了對魯棒性的重視和基于百分比的精確度，并通過遮罩對圖像中感興趣區(qū)域的誤差進行測量與統(tǒng)計。其測試結(jié)果在互聯(lián)網(wǎng)上（http：//vision.middlebury.edu/flow/data/）公布。此后，很多關(guān)于光流法的論文都將Middlebury測試集作為標準并將測試結(jié)果提交更新。目前，已有超過50種光流算法的具體實現(xiàn)參與了評測。

［1］HORN B K P，SCHUNCK B G.Determining optical flow［J］.Artificial intelligence，1981，17（1-3）：185-203.

［2］LUCAS B D，KANADE T.An iterative image registration technique with an application to stereo vision［C］//IJCAI'81 Proceedings of the 7th international joint conference on Artificial intelligence.Citeseer，1981：674-679

［3］AGGARWAL J，NANDHAKUMAR N.On the computation of motion from sequences of images-a review［J］.Proceedings of the IEEE，1988，76（8）：917-935.

［4］BARRON J L，F(xiàn)LEET D，BEAUCHEMIN S.Performance of optical flow techniques［J］.International Journal of Computer Vision，1994，12（1）：43-77.

［5］STILLER C，KONRAD J.Estimating motion in image sequences［J］.IEEE Signal Processing Magazine，1999，16（4）：70-91.

［6］BAKER S，ROTH S，SCHARSTEIN D，et al.A database and evaluation methodology for optical flow［C］//2007 IEEE 11th International Conference on Computer Vision，2007：

［7］NAGEL H H.On the estimation of optical flow：Relations between different approaches and some new results［J］.Artificial intelligence，1987，33（3）：299-324.

［8］BLACK M J，ANANDAN P.The robust estimation of multiple motions：Parametric and piecewise-smooth flow fields［J］.Computer Vision and Image Understanding，1996，63（1）：75-104.

［9］JODOIN P M，MIGNOTTE M.Optical-flow based on anedge-avoidance procedure［J］.Computer Vision and Image Understanding，2009，113（4）：511-531.

［10］BRUHN A，WEICKERT J，SCHN C，et al.Lucas/Kanade meets Horn/Schunck：Combining local and global optic flow methods ［J］.International Journal of Computer Vision，2005，61（3）：211-231.

［11］SINGH A.An estimation-theoretic framework for image-flow computation［C］//Computer Vision，1990.Proceedings， Third InternationalConference on，1989：168-177.

［12］ANANDAN P.A computational framework and an algorithm for the measurement of visual motion ［J］.International Journal of Computer Vision，1989，2（3）：283-310.

［13］PAPENBERG N，BRUHN A，BROX T，et al.Highly accurate optic flow computation with theoretically justified warping［J］.International Journal of Computer Vision，2006，67（2）：141-158.

［14］BURT P J，YEN C，XU X.Local correlation measures for motion analysis：a comparative study［C］//IEEE CPRIP，1982：274.

［15］PRATT W K.Correlation techniques of image registration［J］.Aerospace and Electronic Systems，IEEE Transactions on，1974（3）：353-358.

［16］SUN C.Fast optical flow using cross correlation and shortest-path techniques［C］//Proceedings of Digital Image Computing：Techniques and Applications，1999：143-148.

［17］XIANG X，PENG Y，ZHANG L.A method of optical flow computation based on LUV color space［C］//Test and Measurement，2009.ICTM'09.International Conference on，IEEE，2009：378-381.

［18］BROX T，BRUHN A，PAPENBERG N.et al.High accuracy optical flow estimation based on a theory for warping［C］//Computer Vision-ECCV 2004，2004：25-36.

［19］WEDEL A，POCK T，BRAUN J，U.et al.Duality TV-L1 flow with fundamental matrix prior［C］//Image and Vision Computing New Zealand，2008.IVCNZ 2008.23rd International Conference，2008：1-6.

［20］WEDEL A，POCK T，ZACH C，et al.An improved algorithm for TV-L 1 optical flow［J］.Statistical and GeometricalApproaches to VisualMotion Analysis， 2009，5064/2008：23-45.

［21］ZACH C，POCK T，BISCHOF H.A duality based approach for realtime TV-L 1 optical flow［C］//Proceedings of the 29th DAGMconferenceon Pattern recognition，2007：214-223.

［22］BLACK M J，ANANDAN P.Robust dynamic motion estimation over time［C］//Computer Vision and Pattern Recognition，1991.Proceedings CVPR'91.，IEEE Computer Society Conference on，1991：296-302.

［23］WERLBERGER M，TROBIN W，POCK T，et al.Anisotropic Huber-L1 optical flow［C］//Proceedings of the British machine vision conference，2009.

［24］SUN D，ROTH S，LEWIS J，et al.Learning optical flow［J］.Computer Vision-ECCV 2008，2008，5304/2008：83-97.

［25］ZIMMER H，BRUHN A，WEICKERT J，et al.Complementary optic flow［Z］.International Conference on Energy Minimization Methods in Computer Vision& Pattern Recognition，2009.

［26］TROBIN W，POCK T，CREMERS D.et al.An unbiased second-order prior for high-accuracy motion estimation［J］.Pattern Recognition，2008：396-405.

［27］NIR T，BRUCKSTEIN A M，KIMMEL R.Over-parameterized variational optical flow ［J］.International Journal of Computer Vision，2008，76（2）：205-216.

［28］BAKER S，MATTHEWS I.Lucas-kanade 20 years on：a unifying framework ［J］.International Journal of Computer Vision，2004，56（3）：221-255.

［29］JUNG H，LEE K，LEE S.Toward global minimum through combined local minima［J］.Computer Vision– ECCV 2008，2008：298-311.

［30］LEMPITSKY V，ROTH S，DARMSTADT T，et al.Fusion-Flow：discrete-continuous optimization for optical flow estimation［C］//Proceedings of the IEEE conference on computer vision and pattern recognition，2008.

［31］GLOCKER B，PARAGIOS N，KOMODAKIS N，G.et al.Optical flow estimation with uncertainties through dynamic MRFs［C］//2008 IEEE Conference on Computer Vision and Pattern Recognition，2008：1-8.

［32］LEI C，YANG Y H.Optical flow estimation on coarse-to-fine region-trees using discrete optimization ［C］//Computer Vision，2009 IEEE 12th International Conference on，2009：1562-1569.

［33］XU L，CHEN J，JIA J.A segmentation based variational model for accurate optical flow estimation［C］//Proceedings of the European conference on computer vision，2008：671-684.

［34］FIGUEIRA D，MORENO P，BERNARDINO A，et al.Optical flow based detection in mixed human robot environments［J］.Advances in Visual Computing，2009：223-232.

［35］FLEET D J，JEPSON A D.Computation of component image velocity from local phase information ［J］.International Journal of Computer Vision，1990，5（1）：77-104.

［36］FAY D，WAXMAN A.Real-time early vision neurocomputing［C］//Neural Networks，1991.，IJCNN-91-Seattle International Joint Conference on，IEEE，1991：621-626.

［37］TAGLIASACCHI M.A genetic algorithm for optical flow estimation［J］.Image and Vision Computing，2007，25（2）：141-147.

［38］SEITZSM，BAKERS.Filterflow［C］//ComputerVision，2009 IEEE12thInternationalConferenceon，2009：143-150.

A Survey on Optical Flow Algorithms

ZHANG Zheng1，JIA He-ping2
（1.College of Materials Science and Engineering,Taiyuan University of Technology，Taiyuan 030024，China；2.College of Physics and Electronic Engineering,Shanxi University，Taiyuan 030006，China）

The mearsurement of optical flow is the fundamental issue of image sequence processing and video mining.In this paper，the principle of optical flow method is introduced first.Four main catalogues of optical flow algorithms，including the differential technique，region-based matching，energy-based method and phase-based method，are disscussed in detail，especially the commonly used energy-based method.The evaluation methods and collection of optical flow methods are also introduced in this paper.

optical flow，motion detection，energy-based method，video mining

TP391

A

10.3969/j.issn.1002-0640.2017.07.023

1002-0640（2017）07-0105-05

2016-05-05

2016-07-08

張 拯（1970- ），男，山西渾源人，工程師。研究方向：光流算法在材料工業(yè)中的應用及電化學儲能器件。