張子星,文 穎

(華東師范大學(xué) 計算機科學(xué)技術(shù)系,上海 200062)

1 概述

光流估計是計算機視覺的一個基礎(chǔ)研究領(lǐng)域,其計算結(jié)果被廣泛用于物體分割、跟蹤、運動場景分類等許多領(lǐng)域[1].自從 Horn 和 Schunck 的工作[2]以來,光流估計領(lǐng)域的研究已經(jīng)持續(xù)了幾十年.傳統(tǒng)的方法[3–5]通過變分法框架最小化能量函數(shù)來求解光流場,這在小位移場景下能獲得較精確的結(jié)果,但往往難以解決大位移光流問題.盡管Brox[3]采用由粗到細(xì)(coarse-tofine)的策略將高分辨率下的大位移轉(zhuǎn)化為低分辨率下的小位移來計算,但對于位移比物體本身尺寸更大的情況仍然難以適應(yīng)[6].

為了克服變分法框架處理大位移時的缺陷,Brox等人在變分法模型中集成了稀疏的描述子匹配的結(jié)果[6,7],用描述子匹配得到的運動場拉動變分法光流的計算.通過將匹配結(jié)果與變分法相融合,可以有效地提高變分法光流的精度[8].Deepflow[9]通過非剛性匹配得到半稠密的運動場,進(jìn)一步提高了描述子對變分法的拉動能力.文獻(xiàn)[10]將圖像進(jìn)行分割并分別求取變換矩陣,在單一運動場景和復(fù)雜運動場景下都取得了較好的結(jié)果,近年來出現(xiàn)的基于 PatchMatch 的方法[11–13]通過隨機搜索和鄰域塊之間的信息傳播[14]加快了尋找匹配對的過程,有效提高了匹配精度.

近年來,馬爾科夫隨機場也被許多學(xué)者用來嘗試作為尋找圖像間匹配點的模型.求解馬爾科夫隨機場的推斷算法如置信度傳播在實際應(yīng)用中能得到較精確的匹配結(jié)果,但是存在著計算量太大的問題.Felzenszwalb等人提出了一種高效的循環(huán)置信度傳播算法[15],在有限次的消息傳遞迭代以后就能獲得較好的結(jié)果,但該方法適用于小位移場景,在大位移場景下仍然過于耗時.SPM-BP方法[16]將消息傳遞算法與PatchMatch的隨機搜索相結(jié)合,在減小標(biāo)簽空間的同時獲得了亞像素精度的位移場.FullFlow[17]提出了一種全局的消息傳遞優(yōu)化方法并將消息傳遞的計算復(fù)雜度從二次降為線性,取得了較為精確的匹配結(jié)果.將置信度傳播應(yīng)用于光流估計的關(guān)鍵在于在標(biāo)簽空間和位移場精度之間取得平衡.高精度的大位移估計意味著較大的標(biāo)簽空間,這會導(dǎo)致計算時間及內(nèi)存上的巨大開銷.FullFlow雖然提出了改進(jìn)方法,但在大位移場景下的精確估計仍然比較耗時,SPM-BP雖然利用隨機搜索有效縮短了時間,但是精度不穩(wěn)定,錯誤的標(biāo)簽空間選取可能導(dǎo)致嚴(yán)重的誤差.

綜上所述,以往提出的方法存在的不足之處主要表現(xiàn)在光流計算精度有限和處理速度緩慢的問題,為了解決上述問題,我們提出了分層置信度傳播算法用以計算精確光流.圖1展示了我們模型的主要流程.我們構(gòu)建了兩層馬爾科夫隨機場:超像素層與像素層.我們首先在超像素層執(zhí)行置信度傳播得到一個大范圍但低精度的位移場,然后利用該位移場限定每個像素點可能的位移范圍,從而有效減小像素層置信度傳播的標(biāo)簽空間,然后在像素層執(zhí)行置信度傳播得到每個點的高精度位移.通過分層的方式,我們有效地提高了利用置信度傳播計算光流的效率.為了提高算法的魯棒性,我們還在置信度傳播模型中加入了相鄰多幀的圖像信息作為參考,對于存在嚴(yán)重遮擋的運動場景,多幀信息能有效減少誤匹配的發(fā)生.

圖1 本文提出的分層置信度傳播光流估計算法的流程示意圖

2 相關(guān)工作

應(yīng)用于計算機視覺的置信度傳播算法的一般框架是將圖像中的每一個像素點作為馬爾科夫隨機場中的一個節(jié)點,并用邊連接四鄰接的像素點.對每個節(jié)點而言,每一種可能的取值都是一個標(biāo)簽.對光流估計問題來說,每一個標(biāo)簽都代表一種可能的位移.目標(biāo)函數(shù)一般定義為:

其中,P 是節(jié)點構(gòu)成的集合,fp是賦給節(jié)點p的標(biāo)簽,在光流估計問題中,每個候選標(biāo)簽代表一種候選位移.N代表四鄰接節(jié)點間互相連接的邊.Cp(fp)代表數(shù)據(jù)項,即節(jié)點p在標(biāo)簽fp下的代價,S(fp,fq)代表平滑項,用以衡量兩個相鄰節(jié)點p和q的標(biāo)簽差異.

根據(jù)Felzenszwalb等人的工作[15],在帶環(huán)的馬爾科夫隨機場中最小化能量函數(shù)(1)可以通過循環(huán)置信度傳播來實現(xiàn).循環(huán)置信度傳播通過消息迭代傳遞來更新每個節(jié)點的狀態(tài),消息迭代更新的公式如下:

其中,mts?p1(fp)表示在t? 1次迭代時節(jié)點s向節(jié)點p傳遞的消息.s是p的鄰接節(jié)點中除了以外的節(jié)點.消息mtpq(fq)是一個向量,維度與節(jié)點的候選標(biāo)簽數(shù)量相同.經(jīng)過若干次迭代以后,通過如下公式計算置信度向量:

并選擇向量bp中的最小值對應(yīng)的標(biāo)簽作為節(jié)點p最后的標(biāo)簽.

當(dāng)處理存在大位移場景的高分辨率圖片時,過大的節(jié)點數(shù)量和標(biāo)簽空間使得上述框架計算極為耗時.上文提到的FullFlow雖然可以通過置信度傳播取得較為精確的結(jié)果,但是其計算極為消耗資源,而SPMBP利用隨機選取來獲取候選標(biāo)簽的方法并不穩(wěn)定,錯誤的標(biāo)簽可能造成較大的誤差.本文提出的方法不但能有效提升置信度傳播的效率,而且可以獲得較高精度的結(jié)果,在時間消耗和光流估計的精度上取得了較好的平衡.

3 本文方法

定義輸入的兩幀圖像是I1、I2,將I1視作馬爾科夫隨機場.L代表候選標(biāo)簽的集合,每個標(biāo)簽都是一個候選的二維位移向量.馬爾科夫隨機場中的每個節(jié)點需要賦予一個合適的標(biāo)簽.

定義fp∈L為賦給節(jié)點p的標(biāo)簽,fp=(up,vp)代表通過位移(up,vp)將中的節(jié)點p(x,y)映射到I2中的p′(x+up,y+vp)處.本文將能量函數(shù)定義為:

其中,p是I1中的一個節(jié)點,是兩個相鄰節(jié)點,Ccolor和Cdesc分別代表移動前后的顏色差異、描述子差異.平滑項S(fp,fq)用于懲罰相鄰節(jié)點p與q運動的不一致性.本文模型中的數(shù)據(jù)項由Ccolor和Cdesc構(gòu)成,即:

我們利用公式(2)和公式(3)來最小化能量函數(shù)(4),為了克服置信度傳播在大位移場景下巨大計算量,我們的模型引入了分層結(jié)構(gòu).

3.1 分層結(jié)構(gòu)

基于上述模型,較直觀的方法是將I1中的每個像素點作為一個節(jié)點.但是當(dāng)進(jìn)行大位移光流估計時,直接應(yīng)用該模型會導(dǎo)致 L 包含成千上萬的標(biāo)簽.較大的節(jié)點數(shù)量和過大的標(biāo)簽空間使得計算變得過于耗時.為了克服這個問題,我們提出了分層結(jié)構(gòu)來提高計算效率.

本文對于置信度傳播過程的改進(jìn)基于這樣的假設(shè):一個物體表面局部區(qū)域內(nèi)的像素點的運動往往是一致的,因此可以將每一小塊這樣的區(qū)域作為一個節(jié)點構(gòu)建馬爾科夫隨機場.如果能得到每塊區(qū)域的大致位移,區(qū)域內(nèi)的每個像素點在進(jìn)行置信度傳播時就能將候選位移控制在較小的范圍內(nèi).為了得到這些小塊的區(qū)域,我們將I1、I2進(jìn)行分割,利用SLIC分割算法[18]將原圖分割成若干超像素塊.相較于規(guī)則分割,超像素分割能更好地貼合物體的邊緣,保留邊緣細(xì)節(jié),有利于保持運動場中物體邊緣的清晰.我們在超像素圖像和原圖像上分別構(gòu)建馬爾科夫隨機場,在超像素層和像素層兩個層面執(zhí)行循環(huán)置信度傳播.節(jié)點p在超像素層和像素層分別代表一個超像素塊和一個像素點.我們首先在超像素層執(zhí)行置信度傳播,為了進(jìn)一步加快計算,本文方法在超像素層面獲取的是一個低精度的位移場,也就是說限定每個節(jié)點的候選位移步長為d,即fp∈R2,R={0,d,?d,2d,?2d,···}.本文利用二維的 distance transform算法[15]來迭代地更新消息.為了計算公式(5),需要確定超像素塊p在經(jīng)過位移fp后在I2上的對應(yīng)塊,為此,將超像素p的中心點x沿著fp移動到I2上的x′處,將x′所屬的超像素塊p′作為p在fp下的對應(yīng)超像素塊,然后計算p與p′之間的顏色與描述子差異.

在完成超像素層的循環(huán)置信度傳播后,得到了一個基礎(chǔ)的位移場.利用這個基礎(chǔ)結(jié)果來引導(dǎo)像素層的置信度傳播,能夠有效地減少每個像素點的標(biāo)簽數(shù)量.用代表像素層節(jié)點p的一個候選位移,注意如前文所述,節(jié)點p在像素層代表一個像素點,代表節(jié)點p所在的超像素塊在超像素層置信度傳播中得到的位移,則up=du+usp,vp=dv+vsp,其中,dv∈ [?δ,δ],δ決定了像素層每個節(jié)點的候選標(biāo)簽個數(shù),本文在像素層設(shè)置步長為1,則每個節(jié)點的標(biāo)簽數(shù)量為.像素層置信度傳播是在超像素位移場基礎(chǔ)上的進(jìn)一步微調(diào).本文利用min-convolution算法[17]來執(zhí)行像素層的消息迭代更新.由于相鄰的節(jié)點可能屬于不同的超像素塊,因而它們可能擁有不同的基礎(chǔ)位移,需要對min-convolution的方法作修改以解決這個問題.min-convolution的消息更新的過程被分解為兩個求下包絡(luò)的過程:

其中 是懲罰函數(shù),本文使用L1范數(shù).p和q是兩個鄰接節(jié)點,?pq(up,vp)=Cp(fp)+s∈Npqmts?p1(fp).首先根據(jù)vp的每一種可能的取值計算公式(7),然后利用(7)的結(jié)果根據(jù)vq的 每一種取值計算公式(6).若p與q擁有相同的基礎(chǔ)位移,則上述計算過程就是計算下包絡(luò)的過程.當(dāng)p與q的基礎(chǔ)位移不同時,我們將上述求得的下包絡(luò)函數(shù)圖像向外延伸以覆蓋p與q標(biāo)簽的取值范圍.圖2顯示了up與uq的基礎(chǔ)位移存在1個像素的相對偏移時的情況,對于公式(7),當(dāng)vp值固定,先假設(shè)up與擁有相同的基礎(chǔ)位移,計算函數(shù)的下包絡(luò),即圖中加粗黑線部分,然后再將下包絡(luò)向外延伸1個單位以覆蓋uq的取值范圍.

圖2 min-convolution 算法求取下包絡(luò)

3.2 數(shù)據(jù)項定義

在像素層,每個像素點都對應(yīng)MRF中的一個節(jié)點,由于節(jié)點數(shù)量多,如果計算每個節(jié)點在每一種候選位移下對應(yīng)點間的SIFT特征歐式距離將使得像素層的數(shù)據(jù)項計算變得極為耗時.為了有效地減少計算時間,本文方法在像素層上使用Census變換[20]提取每個點的局部特征,然后利用漢明距離計算運動前后的Cdesc.相較于 SIFT 特征,Census變換求取方便且特征維數(shù)低,通過位運算實現(xiàn)的漢明距離也比歐式距離計算時間短.SPM-BP方法[16]同樣利用Census變換來計算數(shù)據(jù)項,其工作驗證了Census變換提取的特征作為數(shù)據(jù)項可以在較小的時間開銷下獲得穩(wěn)定的性能.

3.3 多幀信息

為了解決由于大位移和物體運動到畫面以外而導(dǎo)致的遮擋問題,進(jìn)一步提高結(jié)果精度,本文提出的模型考慮了前后多幀圖像的信息,由于物體的運動具有慣性,同一物體在相鄰多幀圖像上的運動往往具有一致性,多幀信息在一定程度上可以彌補前后兩幀圖像中部分區(qū)域丟失的信息[21].我們在計算數(shù)據(jù)項Cp(fp)時沿著運動方向向前和向后分別映射到相鄰多幀圖像上,分別計算數(shù)據(jù)項然后取最小值作為最終的數(shù)據(jù)項結(jié)果,以此提高模型的魯棒性.

圖3顯示了使用多幀信息的示意圖.It?1、、It+1和It+2是連續(xù)的四幅輸入圖像,我們要計算節(jié)點pt在It與It+1之間的光流,(u,v)是一個候選標(biāo)簽,則我們將pt沿移動到It?1上的pt?1處,沿移動到It+1的pt+1處,沿(2u,2v)移動到It+2的pt+2處.根據(jù)公式(5)分別計算pt與pt?1、pt+1和pt+2之間的顏色與特征差異,得到,取最小值作為pt在標(biāo)簽下的數(shù)據(jù)項,即:

3.4 后處理

在完成分層置信度傳播以后,通過前后一致性檢查來去除錯誤的位移,得到一個半稠密的光流場.之后我們采用EpicFlow[22]的插值方法,通過現(xiàn)有的半稠密光流場插值填充空白區(qū)域的位移,得到最終的亞像素精度的光流場結(jié)果.

圖3 多幀信息示意圖

4 實驗及結(jié)果分析

實驗在常用的光流數(shù)據(jù)集MPI Sintel數(shù)據(jù)集[23]上對本文方法進(jìn)行評估.MPI Sintel數(shù)據(jù)集提供了包含大位移、運動模糊和大面積遮擋等場景的動畫視頻序列.數(shù)據(jù)集包含23個訓(xùn)練集圖像序列,12個測試集圖像序列,每個圖像序列都包含清晰版和加入了運動模糊、氣流變化的最終版本,由于最終版本圖像更接近于真實場景圖像,實驗在最終版本的圖像上評估算法性能.實驗平臺為 4 核 Intel i5-4590 3.30 GHz CPU 和 8 GB RAM的個人臺式計算機.

4.1 參數(shù)分析

我們隨機選取MPI Sintel數(shù)據(jù)集中10%的訓(xùn)練集數(shù)據(jù)來進(jìn)行模型參數(shù)的評估實驗.在公式(4)中,系數(shù)α和 β分別控制著顏色和描述子的權(quán)重.在3.1節(jié)中,步長d影響超像素層置信度傳播的標(biāo)簽空間大小,δ決定了像素層標(biāo)簽空間的大小.因為顏色信息和SIFT描述子在尋找點匹配中的作用已被許多研究者論證,我們主要關(guān)注 δ和步長d對光流估計結(jié)果的影響.實驗采用終點誤差(EndPoint Error,EPE)來衡量得到的光流場與真值之間的誤差,即求每個點的位移向量與真值的歐式距離作為該點的誤差,然后求所有點的誤差的平均值作為最終的誤差.在超像素層,參數(shù)設(shè)置為 α=1,β=250,在像素層,參數(shù)設(shè)置為α=0,β= 3.

圖4顯示了不同d取值對超像素層置信度傳播結(jié)果的影響,d的取值越大,則候選位移選取時的步長越大,同樣的位移范圍下標(biāo)簽空間越小.此處的誤差是在超像素層完成置信度傳播后計算得到的.通過圖中的曲線可以看出,在超像素層的置信度傳播運算并不需要高精度的候選位移,d= 4、d=5都取得了較好的結(jié)果.因為d的取值越大,節(jié)點的候選標(biāo)簽空間越小,消息更新的速度更快,在后續(xù)實驗中設(shè)置參數(shù)d=5.圖5顯示了像素點位移范圍 δ的不同取值對誤差的影響,由于有超像素層的位移對像素點的位移范圍進(jìn)行了限制,在像素層進(jìn)行置信度傳播時,取較小的值就可以得到比較精確的結(jié)果,擴(kuò)大像素點標(biāo)簽空間并不會進(jìn)一步提升光流估計的精度.通過該實驗可知分層結(jié)構(gòu)的確可以有效地減小像素點的標(biāo)簽空間,提高置信度傳播的執(zhí)行效率.在后續(xù)試驗中設(shè)置參數(shù) δ=10.

圖4 d的不同取值對結(jié)果誤差的影響

圖5 δ的不同取值對結(jié)果誤差的影響

4.2 MPI Sintel實驗結(jié)果

實驗?zāi)Ｐ蛥?shù)設(shè)置為:超像素層上 α=1,β= 250,像素層上 α=0,β= 3,δ= 10.本文模型對原圖像進(jìn)行1/2降采樣以后執(zhí)行分層置信度傳播,在超像素層執(zhí)行2輪消息更新迭代,在像素層執(zhí)行3輪消息更新迭代.表 1 和表 2 展示了實驗結(jié)果.“EPE All”表示整幅圖像上所有點的位移的誤差,“EPE Noc”表示在求取光流的兩幅圖像上都出現(xiàn)的區(qū)域的位移誤差.“EPE Occ”表示在第一幅圖像中可見而在第二副圖像中被遮擋的區(qū)域的位移誤差.表1顯示的是采用了置信度傳播的相關(guān)方法的實驗結(jié)果的比較.FullFlow方法效果略優(yōu)于我們的結(jié)果,但是由于使用了全局優(yōu)化的方法,根據(jù)文獻(xiàn)中報告的結(jié)果,他們的時間開銷將近240 s,且是在工作站上運行,時間及內(nèi)存開銷遠(yuǎn)大于我們的方法.而我們的方法在普通8 GB內(nèi)存的臺式計算機上的運行時間為45 s左右,說明本文的模型能有效提高置信度傳播的執(zhí)行效率.本文模型的時間消耗與SPM-BP接近,但是獲得的光流估計的精度更高,說明本文的模型在效率和精度上取得了較好的平衡.HCOF[21]在模型中也加入的多幀信息,但是無論是在處理效率和結(jié)果精度上都低于本文方法.

表1 本文方法與相關(guān)方法在 Sintel上的結(jié)果

表2將本文模型的實驗結(jié)果與目前前沿的一些方法作了比較.從表中可以看到本文方法的結(jié)果優(yōu)于大部分方法.我們的模型使用了EpicFlow[22]的插值方法,而其最終結(jié)果優(yōu)于EpicFlow,這說明本文提出的模型在精確匹配對應(yīng)點上比EpicFlow表現(xiàn)更好.從表中結(jié)果看出本文方法在精度上具有一定的競爭力.

圖6顯示了部分實驗結(jié)果可視化圖像的示例,圖中將本文提出的方法與EpicFlow與SPM-BP的結(jié)果進(jìn)行了對比.每一列的第一行和第二行為輸入圖像,第三行為EpicFlow的結(jié)果,第四行為SPM-BP的結(jié)果,第五行是本文方法的結(jié)果,最后一行為真值.圖中方框標(biāo)出的區(qū)域顯示了本文方法的優(yōu)勢.從第一列我們可以看到EpicFlow的結(jié)果在圖像右上角出現(xiàn)了明顯的錯誤,SPM-BP則在圖像的右下角區(qū)域出現(xiàn)明顯的錯誤,本文的方法與真值更接近.第二列的EpicFlow的結(jié)果沒有捕捉到人物手臂的運動,SPM-BP的結(jié)果中手臂的運動方向與真值相比出現(xiàn)了明顯的偏差,本文方法捕捉到了手臂及身后木棍的運動.第三列中,EpicFlow和SPM-BP都沒有捕捉到左上角手部的運動,而本文提出的方法則成功地捕捉到了手部的運動.第四列中,EpicFlow和SPM-BP在圖像左上方的運動方向都出現(xiàn)了明顯的錯誤.

表2 本文方法與部分常用方法在 Sintel上的結(jié)果

圖6 本文方法與相關(guān)方法的可視化結(jié)果比較

5 結(jié)束語

本文提出了一種分層執(zhí)行置信度傳播的方法來進(jìn)行光流估計,能在較短的時間內(nèi)獲得高精度的大位移光流場.為了克服將置信度傳播應(yīng)用于大位移場景時巨大的內(nèi)存與時間開銷,本文方法首先在超像素圖像上執(zhí)行置信度傳播,將每個超像素塊作為節(jié)點并擴(kuò)大候選位移的步長以提高運算效率,之后利用得到的超像素位移場來引導(dǎo)像素層的置信度傳播,將每個像素節(jié)點的標(biāo)簽空間限制在一個較小的范圍內(nèi),有效提高了像素層置信度傳播的效率.本文模型僅使用了常見的SIFT描述子及Census變換就在大位移場景下取得了較為精確的光流估計結(jié)果,這說明本文提出的模型能有效地尋找精確的點對應(yīng),適用于高精度的大位移光流估計.

本文模型中使用了SLIC超像素分割算法和稠密SIFT描述子,在之后的工作中,設(shè)計更為優(yōu)秀的分割算法和描述子,將進(jìn)一步提升模型的性能.此外,利用GPU并行實現(xiàn)本文算法也將進(jìn)一步提升分層置信度傳播的執(zhí)行效率.雖然本文提出的模型有效地提高了置信度傳播的執(zhí)行效率,但其執(zhí)行速度距離實時計算仍有差距,且計算精度仍有提升空間.我們相信通過后續(xù)的工作改進(jìn),置信度傳播算法將成為光流估計的一個有力工具.