基于分層置信度傳播的光流估計方法①

張子星,文 穎

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

1 概述

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

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

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

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

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

2 相關工作

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

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

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

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

并選擇向量bp中的最小值對應的標簽作為節點p最后的標簽.

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

3 本文方法

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

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

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

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

3.1 分層結構

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

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

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

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

圖2 min-convolution 算法求取下包絡

3.2 數據項定義

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

3.3 多幀信息

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

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

3.4 后處理

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

圖3 多幀信息示意圖

4 實驗及結果分析

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

4.1 參數分析

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

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

圖4 d的不同取值對結果誤差的影響

圖5 δ的不同取值對結果誤差的影響

4.2 MPI Sintel實驗結果

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

表1 本文方法與相關方法在 Sintel上的結果

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

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

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

圖6 本文方法與相關方法的可視化結果比較

5 結束語

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

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