Horn–Schunck 演算法簡介

在眾多光流估計方法中，Horn–Schunck演算法是最為早期的演算法之一，與之前介紹過的Lucas-Kanade演算法同樣是非常經典、具有代表性的演算法。關於光流法的整體介紹、分類、以及某些演算法的簡介可以在過往的科普文章中找到，本文將要介紹的是Horn–Schunck演算法的概念、推導過程、以及其在光流法領域中的重要意義。

稀疏光流法VS稠密光流法

　　稀疏光流法只對影像中的部分特徵點（如角點或邊緣）進行光流估計，也就是對特徵點的追蹤，時常與角點偵測演算法配合使用，常用於物體追蹤或動作辨識等需要追蹤物體位置的應用場景，其特色有速度快、計算量小。

　　稠密光流場則是對畫面中的每個像素都進行光流估計的運算，能形成一個完整的向量場，計算量較大，常用於需要整體場景分析的任務，例如影片穩定、運動分割、景深估計等。稠密光流通常整體連貫、平滑，但可能使畫面中某些細節無法被偵測到。

　　許多在提出時是稀疏的演算法在後來也有被延伸出稠密版本或使用通用的技巧來稠密化，而Horn–Schunck演算法的特殊之處在於，它在提出時就是一種稠密光流法、也是最早的稠密光流法。

基本假設

　　Horn–Schunck演算法有兩項基本假設：亮度不變和平滑的向量場。這兩項假設在之後的許多研究中也很常見，但需要注意的是，Horn–Schunck演算法對後者的要求較為嚴格，或者說較為重視，因為它是此演算法的重要組成部分。

能量函數

　　能量函數（energy function，也稱為cost function）是光流法中時常出現的概念，透過制定一個適當的能量函數，找出使該值為最小的u、v（光流在x方向和y方向的分量），就是為在該位置計算出的光流結果。

　　Horn–Schunck演算法的能量函數是：

$$E=\int \int [(I_{x}u+I_{y}v+I_{t})^{2}+\alpha ^{2}(\left\| \bigtriangledown u\right\|^{2}+\left\| \bigtriangledown v\right\|^{2})]dxdy$$

　　乍看之下有些複雜，讓我們一步一步將其拆解解釋。首先是最外層，這個雙重積分其實指的就是某一個參考區域（window），只要對區域內每個像素位置都進行裡面的計算再加起來就可以了。

　　有看過之前文章的讀者應該對左半部分並不陌生，因為它其實就是經典光流方程式$I_{x}u_{x}+I_{y}v_{y}+I_{t}=0$，而最小平方法（矩陣運算解聯立）其實就是在沒有右半部分時的一個Energy Function。因此，左半部分也被稱為數據項。

　　右半部分則被稱為平滑項，顧名思義它與平滑向量場的假設有關。前面說過，$u、v$是光流的分量，倒三角形符號▽是向量微分算子，所以右半部分就是在說光流場的變化程度。左右兩者同時出現在Energy Function裡就意味著，此演算法不僅要求灰度值的吻合、同時也要求向量場的平滑。$\alpha$則是用來調整兩者之間的權重，$\alpha$越大代表越平滑。

求解過程

　　將能量函數對 u, v 變分，可以得到兩條偏微分方程：

$$I_{x}(I_{x}u+I_{y}v+I_{t})-\alpha ^{2}\Delta u=0$$

$$I_{y}(I_{x}u+I_{y}v+I_{t})-\alpha ^{2}\Delta v=0$$

一般來說這是一個沒有解析解的情況，所以需要用迭代（iterative）的方式來找出它的數值解。

　　上式中的Laplace算子是二階偏微分，其在非連續的圖像上可以被近似為：

$$\Delta u(x,y)=(\overline{u}(x,y)-u(x,y))$$

也就是u在x, y位置的值和以x, y為中心的區域的加權平均之間的差。於是，之前的微分方程式可以被寫成如下的線性形式：

$$(I_{x}^{2}+\alpha ^{2})u+I_{x}I_{y}v=\alpha ^{2}\overline{u}-I_{x}I_{t}$$

$$I_{x}I_{y}u+(I_{y}^{2}+\alpha ^{2})v=\alpha ^{2}\overline{v}-I_{y}I_{t}$$

　　乍看之下可解，但由於區域加權平均的存在，每當一個像素位置的u, v被計算出來，周圍區域也會受到影響，需要去做更新。

$$u^{k+1}=\overline{u}^k-\frac{I_{x}(I_{x}\overline{u}^{k}+I_{y}\overline{v}^{k}+I_{t})}{\alpha ^{2}+I_{x}^{2}+I_{y}^{2}}$$

$$v^{k+1}=\overline{v}^k-\frac{I_{y}(I_{x}\overline{u}^{k}+I_{y}\overline{v}^{k}+I_{t})}{\alpha ^{2}+I_{x}^{2}+I_{y}^{2}}$$

依照此方法進行迭代，直到Energy Function小到某個程度（收斂），那麼Horn–Schunck演算法的計算就完成了。

結語

　　Horn–Schunck演算法（的最初版本）有一些缺點例如對noise敏感和細節丟失的問題，在實際運用場景中不算強大，但其開創了有別於Lucas-Kanade的另一個光流法類別（不需要warping），對後來的許多光流法研究起到啟發或奠基的作用，可說是具有足以被稱為經典之一的重要地位。

撰稿人：劉徹

參考資料：Horn, B. K., & Schunck, B. G. (1981). Determining optical flow. Artificial Intelligence.

Volume 17, Issues 1–3, 1981, Pages 185-203, ISSN 0004-3702,

https://doi.org/10.1016/0004-3702(81)90024-2