DeepFlow高效的光流匹配演算法（下）

• 2019 年 10 月 6 日
• 筆記

分

享

本周主要介紹一篇基於傳統光流法而改進的實現快速的稠密光流演算法。該演算法已經集成到OpenCV中，演算法介紹網址：http://lear.inrialpes.fr/src/deepmatching/

在介紹該高效的演算法之前，我們先介紹一下經典的LK光流演算法，所以這篇文章將分為上下兩篇。

第一篇DeepFlow高效的光流匹配演算法（上）主要介紹光流演算法的基礎知識,以及理論推導。

第二篇將介紹改進的稠密光流演算法匹配演算法DeepFlow，並展示Demo效果。

DeepMatching是jerome revaud在2013年開發的一種匹配演算法。其目的是計算兩幅影像之間的密集對應關係。深度匹配依賴於為匹配影像而設計的深層、多層、卷積結構。它可以處理非剛性變形和重複紋理，因此可以在影像之間存在顯著變化的情況下有效地確定稠密對應關係。

在這個匹配演算法的基礎上又改進了很多其他方面的計算，相關論文主要有：

《DeepMatching: Hierarchical Deformable Dense Matching》

《DeepFlow:Large displacement optical flow with deep matching》

《EpicFlow: Edge-Preserving Interpolation of Correspondences for Optical Flow》

《Fast Optical Flow using Dense Inverse Search》

論文貢獻

在經典的光流演算法中，在計算小位移的光流演算法中在過去幾十年中得到了廣泛的研究。每個像素的運動被限制在幾個像素以內。大位移問題是近幾年才引起人們的關注，至今仍是一個懸而未決的問題。大位移光流覆蓋了運動不受限制且比物體尺寸更大的更真實情況。為了改善類似問題，正如上一篇文章所述，LK光流又增加了影像金字塔來針對處理大位移的光流的情況。而本文主要的是介紹一種，稠密光流的演算法。

DeepFlow可以說是DeepMatching演算法的改進演算法，將匹配演算法與變分方法相結合，應用於光流的計算，是一種適應光流問題的描述子匹配演算法，可以提高光流法在快速運動的表現。匹配演算法建立在更多層數層，交錯卷積和最大池的多層架構之上，這種結構類似於深度卷積網路。同時基於DeepMatching的改進演算法還有EpicMatching，以及改進光流計算效率的演算法Fast Optical Flow using DIS。

這篇文章做了兩個貢獻：首先，提出了一種新的匹配演算法，稱為深度匹配。其次它建立在一個多階段的架構之上，交錯卷積和最大池，就像在深卷積神經網路中那樣。深度匹配具有平滑效果，即便在兩幀影像之間存在顯著變化的情況下，也能夠有效的確定稠密對應集。最後，利用brox和malik的方法在大位移光流中進行深度匹配。

這是一種新的匹配演算法—-深度匹配

1， 多層結構、交織卷積和最大池

2， 自平滑匹配

3， 大位移光流：集成變分方法中深度匹配對大位移顯示出很好的魯棒性

該演算法的相比經典光流

經典的光流估計的基本準則是在滿足一定前提條件下，最小化能量值。這部分內容可以細細閱讀上一篇文章DeepFlow高效的光流匹配演算法（上）。

一般情況下，大位移的光流依賴於剛性匹配或者小區域的匹配演算法，所用的特徵點一般是基於Hog或者sift描述子，採用最近鄰方法匹配。

缺點是

1，基於塊區域內是光流的一致性，如果在這個塊區域內有著不同方向的位移像素，此時這種方法是無法解決的。

2，在紋理不明顯的地方這種方法是不可靠的。

該論文里提出的深度匹配演算法，介紹如何生成稠密的光流，並且相比較經典演算法更能解決以上的一些缺點。

該演算法優點有

1，可以應用塊區域內的子區域的在一定區域內可以按照不同方向的獨立運動

2，使用卷積和最大池快速計算

3，使用了遞歸的方法

演算法的具體步驟

模組一

1，給定兩幅影像，我們首先從第一幅影像中提取小的4×4塊。

2，使用第一幅圖中的patch與第二幅圖patch進行卷積

3，此時我們得到了這個patch的響應Map

4,對所有的影像中的patch重複此過程。得到論文中稱之為響應影像。

模組二

在模組一得到的響應圖上再繼續一下操作

1，應用一個max pooling操作符。允許該結果的響應圖與patch移動1像素時的響應圖相同。

2，由於響應圖現在在空間上變化緩慢，這裡增加了一個下取樣步驟。該步驟可以減少後面步驟的複雜性。

3，然後利用4個響應圖的稀疏卷積，即4個位移響應圖之和，計算較大patch的響應圖。

4, 最後加入一個非線性濾波，以避免過快的收斂到1。結果，得到了虛擬8×8塊的響應圖，

其中每個子塊的位置在3×3像素附近優化。

5，然後，從這個第二級響應映射的計算，獲取虛擬16×16響應映射。

6，重複以上過程

最終迭代過程的結果是一個多尺寸的響應金字塔。在其中擴展了尺度的局部最大值。

對於每個最大值，演算法都會回溯到允許獲得該最大值的配置，從而產生准密集的對應關係。它是使用動態編程完成的。其中，金字塔是使用自下而上的方法構建的，而提取對應關係則使用自上而下的方法。

上圖是論文中如何檢索對應關係的示例。

考慮金字塔上的紅點是一個局部最大值。

然後它對應於一個叫大的Patch移動。這個最大值是使用4個較小的Patch構建的，檢索它們並獲得較小的patch匹配。不斷的繼續下去，就會出現像右邊一樣出現的小patch。

下面是從重複紋理影像中，利用深度匹配演算法提取的對應關係的示例，其中每個顏色都指一個局部最大值。

深度匹配會產生稠密對應點。它使用多尺度的Patch，允許匹配不同比例的對象。成功地處理了紋理重複的影像，而不能處理標準剛性匹配或小patch之間的匹配，也不能處理非剛性變形。最後，允許的變換集提供了一個內置的平滑效果。實際上，局部最大值會導致許多匹配，由於對可行變換集的約束，這些匹配幾乎相同。

結論

deepflow使用ldof方法將深度匹配集成到變分方法中。

在經典的數據項和平滑項的基礎上，增加了一個匹配項，對輸入匹配項和光流估計項之間的差異進行了計算。然後，使用從粗計算到細計算的策略、定點迭代和經典線性系統求解器（如sor）對其進行優化。

DeepFlow拓展演算法

以上主要是介紹匹配的方法，能夠處理大位移以及塊區域中像素不滿足光流一致性的前提條件。同時在論文中《Fast Optical Flow using Dense Inverse Search》詳細的介紹了如何更加高效的計算光流的值，是一種更為高效的優化方法。

論文中計算光流的步驟：

（1）初始化：對兩幅影像構建影像金字塔，以及一些計算量進行初始化

（2）for循環：這一步與LK光流一致，都是從最頂層到最低層的迭代求解的過程

1 根據當前層的梯度影像計算影像的塊狀積分圖

2 逆向搜索求解稀疏的影像光流場，（這一步是這篇論文的核心和關鍵，提出了完全不同於傳統光流不一樣的求解方法）

3，根據稀疏光流場計算稠密光流。

（3）最底層的光流resize到跟原始影像一樣大小並乘以相應的放大比例，得到最後的光流。

分解這三個部分

1） 影像塊狀積分圖，用於逆向搜索，輸入為影像的x,y方向上的梯度Ix,Iy，一般通過soble 運算元卷積得到，這一步驟，其實與LK光流求塊區域的積分影像沒有任何區別。

2）將步驟1）中的輸出結果作為這一步的輸入，逆向搜索得到稀疏光流場，這一步就是這篇論文的核心所在，是作者創造性的將每一層的光流的迭代量(deltaU,DeltaV)放到了能量最小化公式的左邊，從上一篇文章中我們知道傳統的光流求解方程為

每一層影像上的光流結果為初始值+迭代量

u += delU, v+= delV

最終的求解並優化的殘差函數為

在最小化該函數時，需要根據泰勒展開迭代的求解一階導數S和二階導數H，就是要多次求解S，H效率低下

而逆向搜索是將上面的公式中寫成了

I(x-delU,y-delV,t-1) = I(x+u,y+v,t)

並且最終的殘差函數為變成求解

所以與傳統光流不同的是，最終求得到光流位移量為

u -= delU, v-= delV

使用一階泰勒展開後得到

此時最小化的殘差函數變成了

此時從這個殘差函數中我們可以得到，每次迭代只需要計算一次S和H，計算速度提升很多，而且精度相差不大。這就是本篇文章的核心。

3）計算稠密光流，輸入稀疏光流場，當前層的每一個像素對應的光流等於所有包含該點的影像塊對應的稀疏光流的加權求和

以下demo是集成在OpenCV4.0以上版本的DIS光流演算法：（說明：將光流場轉換到HSV空間中顯示，光流的數值用不同顏色來區分，色斑顏色深淺代表運動速率，白色代表物體無運動。）