基于多重網格法的變分光流計算

摘 要：光流是計算機視覺的重要組成部分，光流法是運動圖像序列分析的重要方法，在許多應用中需要精確的估計，而基于變分的光流計算則能滿足上述要求。提出一種新的變分模型，并將多重網格法運用于模型的計算，以最快速度求解線性方程組，近乎實時地得到圖像序列的光流場。實驗表明該方法是有效的。

關鍵詞：變分法；多重網格法；光流；線性方程組

中圖分類號：TP391 文獻標識碼：B 文章編號：1004-373X(2008)02-145-04

Multigrid Methods for Variational Optical Flow Computation

WANG Xiao，WANG Weiwei，NIE Xiuzhi

(College of Science，Xidian University，Xi′an，710071，China)

Abstract：Optical flow is very important in the Computer Vision community and optical flow estimation is an important method to motion image analysis where its accurate estimation is strongly needed for many applications.This paper introduces a new variation model and uses multigrid method for model′s computation，solves linearly equation systems by the fastest speed，almost achieves the optical flow field of the image sequences in real-time.Experimental results show that this method is suitable and effective.

Keywords：variational methods;multigrid methods;optical flow;linearly equation systems

1 引 言

光流是指圖像中灰度模式運動速度，他是基于象素點定義的，所有光流的集合稱之為光流場。光流場的計算最初由Horn和Schunck［1］于1981年提出，光流作為一種重要的運動分析方法［2］，得到了很大的發展。光流場計算不需預先處理圖像、抽取特征，而是直接對圖像進行計算。變分法是應用最廣泛的用于估計序列圖像的光流的方法，其中許多基于變分技術，這些基于變分的技術雖然效率高、易于實現，但在臨近邊界點的地方的光流速度會產生“漂移”。本文提出一種基于變分的新模型來計算光流場，能夠減少瞬時位置速度迭代時鄰域的影響，克服臨近邊界點的速度“漂移”，保持運動物體的邊界位置。并且將多重網格法運用于線性方程組的求解計算當中，從而快速計算出光流場。

2 Horn-Schunck［1］和Lucas-Kanade［3］光流法

3 改進的光流估算方法

傳統的光流計算方法主要是基于灰度值守恒假設和光流場的平滑性假設。但是這些假設使光流在邊界、陰影的地方不再成立，尤其在運動物體的邊緣位置會產生速度“漂移”，為此本文做出如下改進。

3.1 基于變分的新模型

Horn-Schunck方法的思想是附加一個全局平滑性約束條件，這種算法容易實現，能夠得到精確的瞬時位置速度。但其也存在嚴重的缺陷，例如灰度值恒定的假設使得在圖像的邊緣處的光流估算有較大的誤差；附加的全局平滑性約束條件會迫使估算的光流場平滑地穿過圖像的遮合區域，從而丟失物體形狀特點的重要信息；同時，也使得光流估算對噪聲的敏感度高于基于局部區域信息的Lucas-Kanade方法。

因此，本文在Lucas-Kanade方法的基礎上結合Horn-Schunck的全局思想，并且附加一個梯度約束條件，用以克服上述缺陷。

3.4 多重網格方法

3.4.1 多重網格法的理論基礎

多重網格法［4， 5］是一種加速收斂的算法，其基本思想是：誤差可分為高頻分量和低頻分量，細網格可以消除相對于自身網格的高頻分量，但對低頻分量又無能為力；如網格尺寸增大，細網格上的低頻分量又成了粗網格的高頻分量；因此可利用一系列的細粗網格，在細網格上消除高頻分量，在粗網格上消除低頻分量，從而達到加速收斂的效果。因此運用多重網格方法能顯著提高光流場的計算速度。

3.4.2 網格生成

將多重網格法應用于光流計算時，本文將圖像的象素點看作為網格點，因而將整幅圖像看作為一個二維網格。當從細網格轉向粗網格時，網格點數呈2的指數次遞減，網格尺寸卻呈2的指數次遞增。即若剛開始時圖像尺寸為512×512，網格尺寸h=20。那么第一次轉向粗網格后的網格點數為256×256，網格尺寸h=21；第二次轉向粗網格后的網格點數為128×128，網格尺寸h=22；依此類推直到網格點數為2×2時，可通過直接的矩陣求逆得到精確解。有了最粗網格上的精確解后，再依據多重網格法原理對其進行逐層校正。 

3.4.3 二重網格上的一個循環

由式(9)、(10)所得的線性方程組轉化成如下的矩陣形式：

經過上述7個步驟，完成了二重網格方法的1個循環，但是二重網格方法在(4)時即要求精確求解方程組，這在方程組尚為高階的時候是不現實的。因此本文采用第2.4.4節介紹的多重網格V循環求解方程組。

3.4.4 多重網格的一個V循環［5］

V型循環首先在初始網格進行迭代計算，將得到的光流場變量和殘差傳遞到下一層網格上，繼續進行迭代，這一過程沿著粗網格重復下去直到最粗的網格為止；求出最粗網格上的精確解后，沿著每層網格向上，對上一層的光流場進行修正，一直到初始網格為止，到此完成多重網格的一個V型循環，得到光流場，具體的流程圖如圖1所示。

4 實驗結果與分析

為了驗證本文算法的有效性，分別采用1組合成圖像序列和1組真實圖像序列進行實驗。通過采用本文算法對圖像序列估計光流，然后與真實光流比較，做出定量評估。根據Barron等［1］提出的誤差估計方法，假定vc是真實的光流場，vg是計算所得的光流場，采用如下方法進行誤差估計。

5 結 語

針對經典光流計算方法的不足，本文提出一種改進的算法，有效避免圖像序列運動邊緣的速度“漂移”現象。并且將多重網格法運用于大型線性方程組的求解，使得光流場的求解非常迅速，基本上可以滿足實時應用的要求。

參 考 文 獻

［1］Horn B，Schunck B.Determining Optical Flow ［J］.Artificial Intelligence，1981，17:185-203.

［2］Barron J L，Fleet D J，Beauchemin S S.Performance of Optical Flow Techniques［J］.Int.J.Comput.Vis.，1994，12(1):43-77.

［3］Lucas B，Kanade T.An Iterative Image Registration Technique with an Application to Stereo Vision ［C］.In Proc.Seventh International Joint Conference on Artifical Intelligence，xVancouver，Canada，1981:674-679.

［4］哈克布思.W多重網格方法 ［M］.林群，譯.北京:科學出版社，1988.

［5］陸金甫，關治.偏微分方程數值解法 ［M］.2版.北京:清華大學出版社，2004.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。