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

關(guān)鍵詞：變分法；多重網(wǎng)格法；光流；線性方程組

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：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 引 言

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

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

3 改進(jìn)的光流估算方法

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

3.1 基于變分的新模型

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

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

3.4 多重網(wǎng)格方法

3.4.1 多重網(wǎng)格法的理論基礎(chǔ)

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

3.4.2 網(wǎng)格生成

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

3.4.3 二重網(wǎng)格上的一個(gè)循環(huán)

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

經(jīng)過(guò)上述7個(gè)步驟，完成了二重網(wǎng)格方法的1個(gè)循環(huán)，但是二重網(wǎng)格方法在(4)時(shí)即要求精確求解方程組，這在方程組尚為高階的時(shí)候是不現(xiàn)實(shí)的。因此本文采用第2.4.4節(jié)介紹的多重網(wǎng)格V循環(huán)求解方程組。

3.4.4 多重網(wǎng)格的一個(gè)V循環(huán)［5］

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

4 實(shí)驗(yàn)結(jié)果與分析

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

5 結(jié) 語(yǔ)

針對(duì)經(jīng)典光流計(jì)算方法的不足，本文提出一種改進(jìn)的算法，有效避免圖像序列運(yùn)動(dòng)邊緣的速度“漂移”現(xiàn)象。并且將多重網(wǎng)格法運(yùn)用于大型線性方程組的求解，使得光流場(chǎng)的求解非常迅速，基本上可以滿(mǎn)足實(shí)時(shí)應(yīng)用的要求。

參 考 文 獻(xiàn)

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

［2］Barron J L，F(xiàn)leet 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多重網(wǎng)格方法 ［M］.林群，譯.北京:科學(xué)出版社，1988.

［5］陸金甫，關(guān)治.偏微分方程數(shù)值解法 ［M］.2版.北京:清華大學(xué)出版社，2004.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。