用coarse to fine的技巧提升光流計算的準確度

在光流計算中，coarse to fine是一種很常被使用的手段，又稱pyramid（金字塔），主要用於解決光流長度（位移）較大時計算結果失準的問題。要想了解為何這個問題會產生，我們先快速回顧一下基本光流方程式的推導：(式一)

式一

在推導過程的該步驟中，使用了泰勒級數來展開函數I，然後取第一項作為近似。雖然取更多項能增加近似的準確度，但會大大增加演算法的複雜性和耗時，同時只取一項的近似在光流長度較小（一個像素長度以下）時表現足夠良好，因此大部分光流演算法都使用了只取第一項的近似（不過最近也有研究者開始發展取很多項的光流演算法）。至於為什麼光流長度大時近似會變得不準的原因，其實就和經典的「用直線近似曲線」問題類似。參考圖一，如果只看曲線的一小段，它就像直線一樣，所以近似是準的，而如果取比較大段，直線的近似就不準了。

圖一、一個簡單的例子，用直線近似曲線。

在不取更多項近似的前提下，為了處理光流長度大的情況，早期的研究者已經想出了coarse to fine的核心精神：透過降低圖像的解析度，使得光流長度對像素長度的比值降低，從而進入可以良好近似的範圍。舉例來說，如果原本圖像的解析度是200X200像素、有長度2像素的光流，當解析度降低到100X100時，光流長度就會變為1像素。當然，用低解析度的圖像算出的光流肯定不如高解析度細緻，所以還需要再用高解析度圖像算一次，但高解析度會有光流長度太大的問題，這時候就要利用剛剛算出的低解析度光流，對高解析度的圖像做一個變換（就是後面會提到的warping），使得剩下需要算的光流長度變小。這個做法其實就像是我們日常生活中也常常運用的「先走大步，再走小步」的道理，如圖二。

圖二、先走大步再走小步。藍色箭頭代表低解析度光流，紅色箭頭代表高解析度光流。

以下將說明如何具體進行coarse to fine的計算。假設我們有兩個連續幀的圖像，分別稱為frame1和frame2，求frame1到frame2的光流：

--首先要做的是決定如何把frame1、frame2降解析度（down sampling）。如果想要把解析度變成一半（指圖像邊長，以下同），常見的做法是先把圖像劃分成許多2X2的小格子，再來可以選擇要固定取某個位置（例如左上角）、或者取灰度值最大、最小、中值、或取平均等等。

--然後就是用某種已知的光流演算法為低解析度圖像計算光流。coarse to fine的技巧適用於大多數的演算法。

--接下來要把低解度的光流（向量場）變成和高解析度圖像相同的尺寸，常見做法有複製或內插。這個步驟有時也被稱為升解析度（up sampling）。

--下一個步驟叫做warping，就是對於frame1中的每個像素，依據該位置的光流向量移動到新的位置，組成一張新的圖像，稱為frame1.5

--最後，再次使用光流演算法對frame1.5和frame2計算光流，再把低解析度、高解析度的光流相加，即得最終答案。

圖三是coarse to fine的流程圖。降解析度的操作也可以做不只一次，層層遞進，這就是別名pyramid（金字塔）的由來。

圖三、coarse to fine的流程圖。

不過，到這裡還有一些問題沒解決，那就是warping具體來說如何操作。讀者不妨先觀察看看圖四中一個極度簡化的3X1的warping例子。

圖四、一個簡單的warping例子。

從圖四中可以看出幾個問題。第一個問題是：由於光流往往不會剛好是整數，移動的目的地也就不會是座標格子點，然而用來儲存資料的陣列只有整數的位置。要解決這個問題需要做splatting。Splatting其實就像是逆向的加權平均。以圖四舉例，左邊的像素0經過變換來到右邊的0.4，這時就要把它的灰度值乘以0.6加到右邊的0位置、乘以0.4加到右邊的1位置。而右邊的座標格子點經過splatting的「餵食」後難免會有某些點吃得很撐、某些點吃得很少，這就需要統計該點總計得到了多少權重、然後除以總權重，使大家都變為１。不過這又產生了一個新問題是：統計權重會需要額外的儲存空間和計算複雜度，為了解決這個問題需要改為使用反向的warping。

圖五、反向的warping

Warping和反向的warping就像是等人來餵食和主動去覓食的差別。以圖五為例，右邊的像素0經過變換來到左邊的0.4，這代表右邊的像素0的灰度值就等於左邊像素0乘以0.6加上左邊像素1乘以0.4，不需要去管誰得到了多少權重。同時，反向warping也可以確保右邊每個格子點都得到灰度值。綜上所述，解決warping的問題之後coarse to fine的方法就可以順利運作了。

撰稿人：劉徹

參考資料：

1. Brox, T., Bruhn, A., Papenberg, N., Weickert, J. (2004). High Accuracy Optical Flow Estimation Based on a Theory for Warping. In: Pajdla, T., Matas, J. (eds) Computer Vision - ECCV 2004. ECCV 2004. Lecture Notes in Computer Science, vol 3024. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24673-2_3

2. Shah, S.T.H., Xuezhi, X. Traditional and modern strategies for optical flow: an investigation. SN Appl. Sci. 3, 289 (2021). https://doi.org/10.1007/s42452-021-04227-x

3. First Principles of Computer Vision https://www.youtube.com/@firstprinciplesofcomputerv3258