基于近似最近鄰搜索的并行光流計(jì)算

楊昕欣，姜精萍

北京航空航天大學(xué) 電子信息工程學(xué)院，北京 100191

1 引言

1.1 光流計(jì)算簡(jiǎn)介

光流（Optical Flow）的概念是Gibson于1950年首先提出的，它是由相機(jī)和場(chǎng)景相對(duì)運(yùn)動(dòng)產(chǎn)生的，表示的是圖像中各像素瞬時(shí)相對(duì)運(yùn)動(dòng)的速度情況。光流場(chǎng)是指圖像灰度模式的表面運(yùn)動(dòng)[1]。光流計(jì)算是當(dāng)今計(jì)算機(jī)視覺(jué)的熱點(diǎn)之一，光流算法被廣泛應(yīng)用于運(yùn)動(dòng)目標(biāo)檢測(cè)與跟蹤[2]、機(jī)器人導(dǎo)航[3]、三維重建[4]等領(lǐng)域。20世紀(jì)80年代初期，Horn和Schunck[5]提出了建立在光流平滑性假設(shè)基礎(chǔ)上的稠密光流算法，為光流計(jì)算的發(fā)展起了奠基性作用，之后學(xué)者們相繼提出了多種計(jì)算光流的算法，Barron[6]等人根據(jù)數(shù)學(xué)方法和相應(yīng)的理論基礎(chǔ)，將計(jì)算光流的方法分為基于梯度的方法、基于塊匹配的方法、基于能量的方法和基于相位的方法。

與其他計(jì)算光流的方法相比，基于塊匹配的光流法具有運(yùn)算速度快、易于硬件實(shí)現(xiàn)的優(yōu)點(diǎn)。塊匹配是圖像處理中很常見(jiàn)的一種問(wèn)題，尤其在視頻編碼中的運(yùn)動(dòng)估計(jì)中應(yīng)用廣泛，許多年來(lái)，學(xué)者們已經(jīng)提出了許多塊匹配的算法，如雙十字搜索法[7]、六邊形搜索法[8]、十字-菱形搜索法[9]等。為了進(jìn)一步提高運(yùn)算速度，學(xué)者們提出了近似塊匹配算法，如局部搜索[10]、降低維度[11]等，雖然這些方法得到的結(jié)果只是精確匹配的近似，但由于其大大減少了運(yùn)算量而被廣泛應(yīng)用于各種高層圖像處理中。最近，Barnes[12]等提出了一種近似最近鄰域塊匹配算法，該算法利用了圖像的局部相關(guān)性，基于“相鄰塊的最近鄰域也是相鄰的”這一假設(shè)，將前面已經(jīng)匹配好的結(jié)果傳遞給相鄰塊，與其他近似塊匹配算法相比，該算法利用了塊匹配的特性，極大地減少了運(yùn)算量，本文將其應(yīng)用于光流計(jì)算中。

1.2 Barnes近似塊匹配算法

Barnes近似最近鄰搜索算法利用了塊匹配結(jié)果的特點(diǎn)，即相鄰的查詢(xún)塊的匹配塊也有很大的可能性是相鄰的。同時(shí)Barnes算法還基于另一個(gè)假設(shè)：大范圍隨機(jī)的初始坐標(biāo)也可能包含有某些塊的正確匹配塊的坐標(biāo)。

該算法首先定義了一個(gè)最近鄰域場(chǎng)NNF（Nearest-Neighbor Field）。假設(shè)查詢(xún)圖像為A，參考圖像為B，每個(gè)圖像塊的塊坐標(biāo)用其中心點(diǎn)的坐標(biāo)表示。NNF是方程 f:A??2，定義域?yàn)锳中所有塊可能的坐標(biāo)，值域?yàn)槠ヅ鋲K相對(duì)于查詢(xún)塊的坐標(biāo)偏移量，如果查詢(xún)圖像A中坐標(biāo)為a的查詢(xún)塊的最近鄰域塊為在參考圖像B中的坐標(biāo)為b，則有：

給定某一特定距離計(jì)算函數(shù)E，E(f(a))表示查詢(xún)圖像中坐標(biāo)為a的塊與參考圖像中坐標(biāo)為a+f(a)的塊的誤差，一般用歐式距離。Barnes算法包括初始化和迭代修正兩個(gè)階段。

初始化是將NNF初始化為隨機(jī)的值或是使用先驗(yàn)知識(shí)。例如，采用參考圖像B中全部區(qū)域的獨(dú)立均勻采樣偏移值，作為NNF的初始值。

迭代修正包括傳播和隨機(jī)搜索，這兩個(gè)步驟交替進(jìn)行，對(duì)NNF進(jìn)行修正。傳播：假設(shè)當(dāng)前要計(jì)算的是點(diǎn)p(x,y)，可以利用 p的相鄰像素來(lái)改善 p的結(jié)果，因?yàn)閷?duì)于相鄰的像素來(lái)說(shuō)，其偏移量是差不多的。對(duì)于p來(lái)說(shuō)，f(x-1,y)和 f(x,y-1)是已經(jīng)計(jì)算好了的結(jié)果，可以用它們來(lái)修正當(dāng)前塊 p的匹配結(jié)果 f(x,y)，即令

這樣做的意義在于，如果(x,y)的映射是正確的，但其相鄰區(qū)域?的映射不正確，這樣做之后，?區(qū)域右方和下方的點(diǎn)都能得到正確的映射值。進(jìn)一步，在奇數(shù)次迭代中采取右下方向的傳播，在偶數(shù)次迭代中采取左上方向的傳播，這樣就解決了修正過(guò)程中的方向問(wèn)題。隨機(jī)搜索過(guò)程是以當(dāng)前查詢(xún)塊的最近鄰域值為中心，在一個(gè)窗口大小指數(shù)遞減的搜索窗內(nèi)隨機(jī)搜索候選塊，利用這些候選塊來(lái)改善當(dāng)前查詢(xún)塊的匹配信息。候選塊產(chǎn)生方式如下：

其中v0=f(x,y)，Ri為內(nèi)的一個(gè)均勻采樣的隨機(jī)點(diǎn)，w為搜索窗大小，為圖像的寬度和高度中的最大值，α為搜索窗半徑衰減率，i=1,2,…直到wαi的值小于一個(gè)像素。

2 基于Barnes算法的塊匹配光流法

本文參考facebook在surround 360中的源碼，將Barnes算法應(yīng)用于計(jì)算稠密光流時(shí)，有以下三個(gè)調(diào)整。

2.1 基于梯度的匹配準(zhǔn)則

Barnes算法中的誤差計(jì)算函數(shù)D常用的是絕對(duì)誤差和準(zhǔn)則（SAD），SAD在塊匹配中應(yīng)用的最多，因?yàn)槠洳恍枰M(jìn)行乘法計(jì)算，因此節(jié)省時(shí)間容易實(shí)現(xiàn)。SAD公式表示為：

其中塊大小為M×N，塊的運(yùn)動(dòng)矢量即為SAD最小時(shí)的 (u,v)，即

SAD雖然常用，但當(dāng)場(chǎng)景中存在光照變化時(shí)，得到的光流場(chǎng)會(huì)有明顯的離散化，因此本文使用另一種匹配準(zhǔn)則，基于梯度守恒的準(zhǔn)則[13]。

圖像序列可以看成是圖像灰度值與時(shí)間、空間位置的函數(shù)，可以將圖像中像素點(diǎn)的灰度值表示為函數(shù)的形式：

使用泰勒公式將 f(x+u,y+v,t+Δt)展開(kāi)，忽略高階無(wú)窮小項(xiàng)并認(rèn)為時(shí)間無(wú)限趨近于0，得到：

將式（7）代入式（6），得到：

將式（8）代入式（5）中，得：

要求上式的最小值，可以用最小二乘法得到關(guān)于(u,v)T的非齊次方程組，然后可以得到新的匹配準(zhǔn)則

其中m(i,j)代表窗口權(quán)重，表示了塊中每個(gè)像素點(diǎn)對(duì)匹配結(jié)果的影響，在實(shí)際計(jì)算中，一般用以ρ為半徑的高斯函數(shù)代替，并計(jì)算高斯函數(shù)與圖像序列梯度差值之間的卷積?？梢钥吹?，在新的匹配規(guī)則中，匹配塊與待匹配塊之間的差異只由圖像的梯度決定，而不是灰度。而光照會(huì)對(duì)圖像的灰度產(chǎn)生影響但不會(huì)對(duì)圖像的梯度產(chǎn)生影響，因此，采用基于梯度的匹配準(zhǔn)則可以很好地避免光照帶來(lái)的不利因素，使得到的光流場(chǎng)更準(zhǔn)確。

本文在計(jì)算稠密光流時(shí)，使用的塊大小為1，即m(i,j)=1，用G0x,G0y,G1x,G1y分別表示圖像G0,G1在x方向和y方向的梯度值矩陣。則式（10）可以簡(jiǎn)化表示為：

為了使E(u,v)在定義域內(nèi)連續(xù)可導(dǎo)，將式（11）等價(jià)地寫(xiě)為下面的形式：

式（12）就是本文使用的匹配誤差計(jì)算公式。其中u,v表示該像素點(diǎn)的位移，為保證計(jì)算的精確度，將其類(lèi)型定義為浮點(diǎn)數(shù)，而G1x,G1y中只有整數(shù)坐標(biāo)有值，因此計(jì)算G1x(i+u,j+v)、G1y(i+u,j+v)時(shí)需要進(jìn)行線(xiàn)性插值。例如，在G1x中，假設(shè)點(diǎn)(i+u,j+v)周?chē)罱乃膫€(gè)整數(shù)坐標(biāo)分別為(m,n),(m+1,n),(m,n+1),(m+1,n+1)，令：

則根據(jù)雙線(xiàn)性插值原理，得到：

于是由式（12）～（14）便可以求解出每個(gè)點(diǎn)的匹配誤差。

2.2 多分辨率迭代

將圖像按金字塔式分層，是圖像處理中的一種常見(jiàn)的策略，經(jīng)典的Lucas-Kanade光流算法后來(lái)就應(yīng)用了這一策略[14]。采用由粗到精的金字塔算法，不僅可以減少運(yùn)算量，還可以避免陷入局部點(diǎn)，增強(qiáng)魯棒性。在光流算法中，采用金字塔策略，可以有效獲得大位移光流。

具體方法為設(shè)圖像的原始尺寸為(W0,H0)，將其設(shè)為圖像金字塔的最底層（即第0層），定義縮放因子λ（小于1的常數(shù)，本文設(shè)為0.9），則第一層圖像尺寸為(λW0,λH0),依次類(lèi)推，第 L層的圖像尺寸(WL,HL)=(λLW0,λLH0)，當(dāng)圖像的寬度或高度小于某閾值MinSize時(shí)，停止分層。

設(shè)圖像金字塔共Lm+1層，光流的計(jì)算從最頂層（即第Lm層）圖像開(kāi)始。每層的計(jì)算方法是利用上一層的光流場(chǎng)作為初始值，然后逐點(diǎn)進(jìn)行傳播和修正。其中，最頂層圖像的光流場(chǎng)初始值為(0,1)之間的隨機(jī)均勻采樣值。以第L層圖像的光流計(jì)算為例：

設(shè)第L+1層的光流場(chǎng)為 fL+1,其尺寸為(WL+1,HL+1),由于第L層圖像的尺寸(WL+1/λ,HL+1/λ)，因此首先需要對(duì) fL+1進(jìn)行上采樣，為使結(jié)果盡量平滑，上采樣過(guò)程中使用雙三次插值[15]。設(shè)經(jīng)上采樣后的光流場(chǎng)為那么第L層圖像光流場(chǎng)的初始值為：

乘上1/λ是因?yàn)閳D像放大后，相應(yīng)的像素點(diǎn)的運(yùn)動(dòng)位移也會(huì)變大。接下來(lái)對(duì)每個(gè)像素點(diǎn)進(jìn)行傳播修正，用偽代碼描述如下：

其中，匹配誤差的計(jì)算公式見(jiàn)式（12），梯度下降法修正光流將在2.3節(jié)論述。至此，第L層圖像的光流場(chǎng)計(jì)算完畢。每一層都如此計(jì)算，當(dāng)計(jì)算完第0層時(shí)，就得到了最終的光流場(chǎng)。

2.3 光流修正

Barnes算法的迭代修正過(guò)程中，傳播和隨機(jī)搜索交替進(jìn)行，隨機(jī)搜索是在大范圍內(nèi)設(shè)置搜索窗口來(lái)改善匹配結(jié)果，而視頻序列中連續(xù)的兩幀圖像的時(shí)間間隔一般很小，大部分像素的運(yùn)動(dòng)矢量也較小，這種情況下，對(duì)每個(gè)塊在大范圍隨機(jī)搜索來(lái)改善匹配結(jié)果的效率就不高。同時(shí)，由于采取了多分辨率迭代策略，已經(jīng)可以有效獲得大位移光流，因此，在傳播后，可以不再用隨機(jī)搜索，而是使用梯度下降法來(lái)修正光流。

對(duì)于某個(gè)點(diǎn)來(lái)說(shuō)，其匹配誤差可以看成是其運(yùn)動(dòng)矢量的函數(shù)（見(jiàn)式（12）），其真實(shí)的光流矢量就是使誤差函數(shù)最小時(shí)的運(yùn)動(dòng)矢量。

在式（12）中，G0x和 G0y與 u,v無(wú)關(guān)，而由式（13）、（14）可知，G1x和G1y是關(guān)于u,v的連續(xù)可導(dǎo)的函數(shù)，于是誤差函數(shù)E(u,v)也是關(guān)于u,v的連續(xù)可導(dǎo)的函數(shù)，由微積分原理可知：

注意上式僅在逼近點(diǎn)(u,v)的鄰域內(nèi)成立，在實(shí)際計(jì)算中，用下式近似計(jì)算：

式（18）中，du和 dv取0.001，根據(jù)前面的分析，每次傳播后，修正光流矢量為：

由式（16）可知，修正后誤差總是會(huì)減小。式（19）就是機(jī)器學(xué)習(xí)中常用的梯度下降法。其中，α為步長(zhǎng)，本文采用動(dòng)態(tài)步長(zhǎng)的策略，因?yàn)樵诮咏鼒D像金字塔頂層時(shí)，誤差一般較大，可以將步長(zhǎng)設(shè)置大一些，當(dāng)接近金字塔底層時(shí)，步長(zhǎng)應(yīng)該小一些。將步長(zhǎng)α可以設(shè)置為金字塔層數(shù)的函數(shù)，第L層的步長(zhǎng)為：

綜上所述，整個(gè)算法流程用偽代碼描述如下：

//開(kāi)始

讀入兩幀圖像G0,G1；轉(zhuǎn)換為灰度圖并做歸一化；

初始化第Lm層的光流場(chǎng) fLm為（0，1）之間的隨機(jī)均勻采樣值；

對(duì)光流場(chǎng) fL進(jìn)行一次右下方向的傳播修正；

對(duì)光流場(chǎng) fL進(jìn)行一次左上方向的傳播修正；

對(duì)光流場(chǎng) fL進(jìn)行中值濾波；

if L＞0:

對(duì) fL進(jìn)行上采樣，作為下一層的初始值；

}

//結(jié)束

現(xiàn)對(duì)整個(gè)算法的復(fù)雜度進(jìn)行簡(jiǎn)要分析。對(duì)于n×n的原始圖像，總共處理的像素點(diǎn)個(gè)數(shù)為：

對(duì)于每層圖像的每個(gè)像素點(diǎn)，其傳播過(guò)程僅與相鄰的4個(gè)像素點(diǎn)有關(guān)，所用時(shí)間為常數(shù)；其光流修正過(guò)程與周?chē)袼攸c(diǎn)無(wú)關(guān)，所用時(shí)間也為常數(shù)；因此傳播和修正算法的時(shí)間復(fù)雜度僅為O(c?1)，其中c為常數(shù)。因此整個(gè)算法的時(shí)間復(fù)雜度為，即等效于平方復(fù)雜度O(n2)。

3 并行加速方法

圖形處理器GPU是由成千上萬(wàn)的更小、更高效的核心組成的大規(guī)模并行計(jì)算架構(gòu)，專(zhuān)為同時(shí)處理多任務(wù)而設(shè)計(jì)。如今，GPU的運(yùn)算能力已經(jīng)遠(yuǎn)遠(yuǎn)超過(guò)了CPU。GPU相比CPU在浮點(diǎn)運(yùn)算能力，內(nèi)存帶寬，以及價(jià)格上都體現(xiàn)了極大的優(yōu)勢(shì)。

關(guān)于圖像的算法由于要處理數(shù)量龐大的像素點(diǎn)，通常比較耗時(shí)。例如，本文在計(jì)算每個(gè)像素點(diǎn)的光流時(shí)，要計(jì)算相鄰4個(gè)點(diǎn)的匹配誤差，用梯度下降法修正光流時(shí)，還要計(jì)算一次匹配誤差，而每次計(jì)算匹配誤差都要進(jìn)行雙線(xiàn)性插值運(yùn)算，因此每個(gè)像素點(diǎn)總的運(yùn)算量也不小，隨著圖像尺寸的增大，總的運(yùn)行時(shí)間會(huì)以快速增加。因此，對(duì)算法用GPU進(jìn)行并行加速就非常有意義。

但從上面Barnes的算法描述可知，Barnes算法并不易于在GPU上并行實(shí)現(xiàn)，原因在于其傳播過(guò)程是以逐塊掃描式的，即當(dāng)前塊(x,y)的計(jì)算依賴(lài)于(x-1,y)和(x,y-1)兩個(gè)塊的計(jì)算，這樣的串行性使得算法難以并行實(shí)現(xiàn)。

為此，本文對(duì)傳播過(guò)程稍作修改。每次傳播時(shí)，將當(dāng)前塊的計(jì)算僅依賴(lài)于相鄰的一個(gè)塊，而不是之前的兩個(gè)塊，同時(shí)將好的結(jié)果也只傳播給相鄰的一個(gè)塊，這樣就可使得每一行或每一列的傳播變得獨(dú)立，因此很容易在GPU上并行實(shí)現(xiàn)。

具體來(lái)說(shuō)，對(duì)每層圖像的光流場(chǎng)，由之前的傳播兩次變?yōu)閭鞑?次，依次是從左到右、從上到下、從右到左、從下到上。每次傳播時(shí)，每行或每列的計(jì)算是并行的。

該方法的可行性分析如下，假設(shè)其中的某個(gè)塊p獲得了最好的匹配結(jié)果，其傳播的過(guò)程如圖1所示。

圖1 傳播過(guò)程示意圖

圖1 中深色的塊表示當(dāng)前傳播到的塊?？梢钥闯?，經(jīng)過(guò)4次傳播，其好的結(jié)果能傳遍圖像中所有的點(diǎn)。

4 實(shí)驗(yàn)分析

實(shí)驗(yàn)將本文算法及本文并行加速的算法與OpenCV實(shí)現(xiàn)的稠密光流Farneback[16]算法和Dual TV L1[17-18]算法進(jìn)行對(duì)比。

Farneback算法的基本思想是用一個(gè)二次多項(xiàng)式來(lái)對(duì)圖像進(jìn)行近似建模：，其中A是一個(gè)2×2對(duì)稱(chēng)矩陣，b是2×1的矩陣。對(duì)于每幀圖像中的每個(gè)像素點(diǎn)周?chē)O(shè)定一個(gè)鄰域(2n+1)×(2n+1)，利用鄰域內(nèi)的共(2n+1)2個(gè)像素點(diǎn)作為最小二乘法的樣本點(diǎn)，擬合得到中心像素點(diǎn)的系數(shù)。該過(guò)程中使用了分離卷積的方式，有效地降低了運(yùn)算量。對(duì)于某個(gè)像素點(diǎn)，假設(shè)其原灰度值為 f(x)，增加全局位移后的值為f(x+d)，由灰度一致性假設(shè)可知 f(x)=f(x+d)，然后根據(jù)多項(xiàng)式相應(yīng)的系數(shù)相等，可以求解出該像素點(diǎn)的全局位移d。對(duì)每個(gè)像素點(diǎn)均計(jì)算后，就得到了圖像的稠密光流場(chǎng)。

Dual TV L1算法是在TV L1光流模型的基礎(chǔ)上提出的。TV L1光流模型是指基于L1范數(shù)的整體變分（Total Variation-TV）光流模型，它是用L1范數(shù)代替文獻(xiàn)[5]中HS光流模型的L2范數(shù)，因?yàn)榛贚1范數(shù)的方程具有更優(yōu)的間斷處理能力。但由于TV L1方程的數(shù)據(jù)項(xiàng)和平滑項(xiàng)沒(méi)有完全、連續(xù)的可微性，因此求解較困難。Zach[17]等為此提出了一種對(duì)偶的方法來(lái)求解TV L1光流模型，它將原模型數(shù)據(jù)項(xiàng)中的原光流變量(u,v)用對(duì)偶變量(u′,v′)替換，從而構(gòu)造了TV L1的對(duì)偶模型（Duality TV L1）。同時(shí)將模型分為兩部分凸替求解(u,v)和 (u′,v′)。這樣求得的結(jié)果相比傳統(tǒng)的TV L1光流模型具有更好的全局最優(yōu)性。

4.1 評(píng)估指標(biāo)

光流場(chǎng)的評(píng)估理論和方法一直是學(xué)者們研究的一個(gè)重要主題。2011年，Baker[19]等對(duì)光流場(chǎng)的評(píng)估方法做了一個(gè)詳細(xì)的總結(jié)。本次實(shí)驗(yàn)的評(píng)估指標(biāo)采用常用的平均角誤差（Average Angle Error，AAE）和平均點(diǎn)誤差（Average Endpoint Error，AEE）。

AAE的計(jì)算公式為：其中，N表示圖像中像素點(diǎn)的總數(shù)，(ui,vi)表示計(jì)算得到的圖像某像素點(diǎn)的光流矢量表示圖像某像素點(diǎn)標(biāo)準(zhǔn)的光流失量。AAE反映了計(jì)算得到的光流矢量整體偏移標(biāo)準(zhǔn)光流矢量的角度，是評(píng)估光流算法準(zhǔn)確性的重要指標(biāo)。

平均點(diǎn)誤差(AEE)的計(jì)算公式為：

AEE反映的計(jì)算得到的光流場(chǎng)矢量端點(diǎn)偏離標(biāo)準(zhǔn)光流場(chǎng)矢量端點(diǎn)的距離，這是個(gè)絕對(duì)的量，有一定局限性，比如當(dāng)標(biāo)準(zhǔn)光流場(chǎng)矢量很小時(shí)，這個(gè)值一般較小，而當(dāng)標(biāo)準(zhǔn)光流場(chǎng)矢量較大時(shí)，這個(gè)值一般較大，為方便不同圖片的比較，本文還使用Mccane[20]定義的歸一化點(diǎn)誤差（Normalized Endpoint EEROR，NEE），其計(jì)算公式為：

其中c表示真實(shí)光流，e表示計(jì)算光流，T為顯著性閾值，設(shè)置T是為了避免小光流帶來(lái)的不利影響。本文使用歸一化化點(diǎn)誤差的平均值（ANEE）作為統(tǒng)計(jì)指標(biāo)：

ANEE反映了點(diǎn)誤差占標(biāo)準(zhǔn)光流矢量大小的平均百分比。

4.2 實(shí)驗(yàn)過(guò)程

實(shí)驗(yàn)的硬件環(huán)境為：CPU為Core i7 3.4 GHz，RAM 32 GB，顯卡為NVIDIA GeForce GTX 1080。

實(shí)驗(yàn)的軟件環(huán)境為：Windows 10，Visual Studio 2015，OpenCV3.1.0，cuda 8.0。

實(shí)驗(yàn)的測(cè)試圖片采用Middlebury[21]網(wǎng)站提供的包含真實(shí)光流場(chǎng)的訓(xùn)練組序列。訓(xùn)練組序列包含自然場(chǎng)景序列和合成場(chǎng)景序列，自然場(chǎng)景序列包括Dimetrodon、Hydrangea、RubberWhale，其中包含了大位移運(yùn)動(dòng)，非剛性運(yùn)動(dòng)以及真實(shí)而多樣性的光照效果；合成場(chǎng)景序列包括Grove類(lèi)序列以及Urban類(lèi)序列，其中Grove類(lèi)序列是由多個(gè)程序合成的石頭和樹(shù)組成，地面紋理和表面位移是隨機(jī)生成的，含有明顯的遮擋，攝像機(jī)還有自旋和3D運(yùn)動(dòng)。Urban類(lèi)序列是模擬的城市環(huán)境，含有許多的運(yùn)動(dòng)間斷點(diǎn)，較大的位移，還有獨(dú)立的運(yùn)動(dòng)物體。目前所有的合成序列明顯超越了先前的Yosemite序列。

實(shí)驗(yàn)時(shí)記錄各個(gè)算法在每組序列中的各項(xiàng)誤差指標(biāo)，同時(shí)記錄各算法的運(yùn)行時(shí)間，對(duì)于各算法的運(yùn)行時(shí)間均采用多次實(shí)驗(yàn)（10次）取平均的方法。另外，由于本文算法和本文并行加速的算法是隨機(jī)初始化的，故每次實(shí)驗(yàn)各項(xiàng)誤差數(shù)據(jù)也會(huì)有些微不同，因此也采用了多次實(shí)驗(yàn)（10次）取平均的方法記錄誤差數(shù)據(jù)。對(duì)于各算法得到的光流場(chǎng)，采用文獻(xiàn)[18]中使用的彩色圖表示法以方便直觀的對(duì)比，彩色圖中不同的顏色代表不同方向的光流矢量，顏色的深淺表示該點(diǎn)光流矢量的大?。桓魉惴ㄓ?jì)算的光流場(chǎng)與標(biāo)準(zhǔn)的光流場(chǎng)的誤差用灰度圖表示，圖中黑色的點(diǎn)表示沒(méi)有誤差，灰度值越大表示該點(diǎn)的誤差越大。

4.3 實(shí)驗(yàn)結(jié)果及分析

以自然場(chǎng)景序列Dimetrodon為例，實(shí)驗(yàn)結(jié)果如圖2。

圖2 Dimetrodon序列測(cè)試結(jié)果

表1 不同算法的各項(xiàng)指標(biāo)對(duì)比

圖2中第二行彩色圖為各算法所計(jì)算的光流場(chǎng)經(jīng)可視化后的圖像，第三行灰度圖為各算法計(jì)算得到的光流場(chǎng)的誤差。詳細(xì)的測(cè)試數(shù)據(jù)如表1所示。

結(jié)合表1和表2可以看出，F(xiàn)arneback算法各項(xiàng)誤差最大，Dual TV L1算法的對(duì)于自然場(chǎng)景序列效果較好，而對(duì)于有大位移的合成序列，算法誤差較大，比如對(duì)于序列Urban2，其平均點(diǎn)誤差超過(guò)了3個(gè)像素長(zhǎng)度。而本文基于Barnes算法實(shí)現(xiàn)的塊匹配光流法對(duì)于所有序列均表現(xiàn)良好，從表2的平均性能來(lái)看，其平均角度誤差不超過(guò)5°，平均點(diǎn)誤差不超過(guò)半個(gè)像素長(zhǎng)度，歸一化點(diǎn)誤差約為10%。而經(jīng)并行加速的算法的準(zhǔn)確度與原算法基本一致，均明顯好于OpenCV實(shí)現(xiàn)的兩種稠密光流算法。另外，本文原算法采用的是基于梯度的匹配準(zhǔn)則，對(duì)于光照變化的場(chǎng)景有良好的魯棒性，但對(duì)于有旋轉(zhuǎn)、縮放的場(chǎng)景，梯度守恒的假設(shè)便不再適用，因此本文算法對(duì)Grove3序列的準(zhǔn)確性次于其他序列。

表2 不同算法在所有測(cè)試圖片中的平均誤差

從時(shí)間性能來(lái)看，F(xiàn)arneback算法最快，本文原算法次之，Dual TV L1算法最慢，而本文的并行加速算法相比原算法有大約2.5倍的加速比，速度與最快的Farneback算法十分接近。

綜合準(zhǔn)確度和速度來(lái)看，本文的并行加速光流算法性能最佳。

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

本文在Barnes算法基礎(chǔ)上實(shí)現(xiàn)的稠密光流算法，使用了梯度作為匹配準(zhǔn)則，采用了金字塔分層策略，使用了梯度下降法修正光流，每個(gè)像素點(diǎn)的時(shí)間復(fù)雜度僅為O(1)，并且其準(zhǔn)確性明顯優(yōu)于OpenCV實(shí)現(xiàn)的兩種稠密光流算法。本文對(duì)原算法的傳播過(guò)程進(jìn)行改進(jìn)，從原來(lái)的兩次傳播變?yōu)?次傳播，使算法易于在GPU上實(shí)現(xiàn)并行加速，由此得到的并行加速算法相比本文的原始算法，而速度快了約2.5倍，幾乎與OpenCV中最快的Farneback算法相當(dāng)，而其各項(xiàng)誤差指標(biāo)明顯優(yōu)于Farneback算法。