Tile-based Optical Flow 演算法流程與基本思想

Tile-based Optical Flow 演算法是Google Jump 全景相機中使用的光流演算法，速度快，精度高，在以視覺效果為評價標準的virtual camera view 插值中表現出色。谷歌已經為其申請了專利，可見肯定了其商業價值。

其基本思想是，對參考圖像分塊(tile)，通過塊匹配，找到圖像劃分後的塊的光流，然後插值到像素級的光流，同時計算每個像素光流的置信度，把上述光流場和對應的置信度場矩陣輸入到雙邊運算元中，得到最終的邊緣平滑的光流場。

分塊和雙邊運算元是其最重要的特點，分塊匹配保證找到置信度較高的塊的光流，而且速度快，在插值過程中根據前步塊匹配的結果又能得到一個置信度場，雙邊運算元使filter結果保持邊緣平滑，既可以去噪又可以修補（inpaint），而且雙邊運算元也很快。

演算法大體分為四步：

1.歸一化每一幅單幅圖像，去除不同的曝光和對比度設置帶來的變化；

2.計算一個粗粒度的基於塊的匹配，對於參考圖像中的每一個非交疊的32*32大小的塊，在相鄰圖像256*64區域內，暴力搜索它的最佳亞像素級的匹配塊；

3.上採樣這個逐塊的光流場形成逐像素的光流場，同時生成一幅逐像素的置信度測量，置信度反映每個對應像素光流的可信度；

4.將上述計算得到的光流和置信度估計輸入到一個時域一致的雙邊運算元中，它會在置信度高的地方尋找一個最佳的相似的輸入流，同時儘可能的保持雙邊平滑（保護邊緣不被模糊的時空區域平滑）。

參考圖像I0,鄰接圖像I1,對於Google jump系統，左向兩兩鄰接的圖像計算16次光流，右向兩兩鄰接的圖像計算16次光流，總計32次。

對I0I1進行歸一化，減去均值，除以方差,形成新的I0",I1"。為加速計算，只對灰度圖像做。

給定這些歸一化後的圖像，對I0"中非交疊的每一個32*32大小的tile,在I1"中對應位置水平方向運動[0,224]垂直方向運動[-16,16]區域執行一個暴力搜索以尋找最匹配的tile。

對每一個tile T0",計算一個224*32的平方差之和（SSD）距離圖像D(u,v),這個過程可以使用滑動窗口濾波和FFTs加速，在Lewis 1995年的論文中歸一化的互相關（normalized cross-correlation）已經做了了。

我們使用Halide實現上述演算法，進一步提高了性能。

下一步我們從D(u,v)提取亞像素級的光流估計，這是通過在D(u,v)的極小值附近3*3窗口區域內擬合一個二次方程，然後在這個方程中再求其極小值實現的。

同樣的，我們也可以用這個方程生成一個關於該tile Ti"光流計算的置信度Ci。如果兩個tiles匹配的非常好而且通過這種匹配計算的定位非常好，則Ci就應該大，反之亦然。

這些逐tile的光流和置信度估計｛Ui,Vi,Ci｝,下一步要經過一系列的針對模型假設（異常點，低紋理，重複紋理，目標邊界與tile邊界不對齊，前向後向對稱）的啟發式的變換。

然後把上述結果，Feed to 雙邊運算元中，生成平滑的光流估計，同時保持在視頻序列中的邊緣。

上述過程中第3步，通過逐塊tile的光流場和置信度生成逐像素的光流場與置信度，考慮到以下各種複雜的情況，進行了一系列的變換：

1.重複紋理

如果在相鄰圖像中有多個重複紋理，那對於一個特定的tile,在SSD圖像中可以找到多個局部極小值，它們和全局最小值差別不大。但在雙邊運算元濾波的階段，只能有一個最小值與一個tile對應，所以，我們需要降低這個tile的置信度。

假設di是全局最小值,di"是第二小，他們之間的距離最少相隔32像素，據公式（2）更新此tile對應的置信度Ci。

2.低方差tile（也就是沒有紋理）

計算tile T的方差var(T),並據此更新Ci。計算方差是在輸入圖像數值（0-255）之間。

3.異常tiles

正常的光流，鄰近tile的flow是相似的，對於一些tile如果其周邊的tile都與其不相似，則要降低它的置信度。

在4連通鄰tile中找到與其最相似的tile,計算他們歸一化後的距離，更新Ci。

4.考慮圖像特點的上採樣

最近鄰插值會出現成塊的光流場，沒有考慮到參考圖像的結構。雙線性和三線性插值會生成過平滑的假影。

這裡使用一種改進的最近鄰上採樣方法，用周圍四個tile所指示的(u,v),計算參考圖像像素點周圍8鄰域和這個四個方向所指示的圖像像素點周圍8鄰域之差，選擇最小的作為它的（u,v）。

其置信度要在與其較為匹配的tile的置信度的基礎上進行一定程度的衰減。

5.光流對稱性

圖像對中兩個對應點前向和後向光流應該是對稱的。計算一個評價某點前向和後向流對稱的標準，據此標準改變其置信度。

可以總結出上述變換基本都是在置信度場上做文章。

專利文本

https://patents.google.com/patent/US9342873B1/

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！