電腦視覺中特徵點的光流與追蹤 Optical Flow & Tracking

本文為讀了 An Invitation to 3-D Vision 書中 4.3 Matching point features 的筆記。

Brightness Consistency Constraint

考慮一個場景在時間 $t$ 與 $t + \Delta t$ 的關係，由於物體是相同的，因此他們投影在圖片上的像素值應該也要是相同的，也就是 $$I(x(t), t) = I(x(t+\Delta t), t+\Delta t )$$ 而如果 $\Delta t$ 很小的話我們可以直接近似 $x(t + \Delta t) = x(t) + \mathbf{u} \Delta t$，將此式代入上式再求泰勒展開式以後可得： $$I(x(t), t) = I(x(t), t) + \triangledown I(x(t),t)^T\mathbf{u} + I_t(x(t),t)$$ 其中 $\triangledown I(x(t),t)$ 為 I 的 x, y 兩個方向的梯度，I_t(x(t), t) 為對 I 時間的微分（也就是 $t + \Delta t$ 時刻的 I 減去 $t$ 時刻的 I）。而 Brightness Consistency Constraint 的式子即為： $$\triangledown I(x(t),t)^T\mathbf{u} + I_t(x(t),t) = 0$$

Optical flow 與 Feature tracking 的差別

書中的原文是這樣寫的：「The only difference is where the vector $\mathbf{u}(x,t)$ is computed: in optical flow it is computed at a fixed location in the image, whereas in feature tracking it is computed at the point x(t).」

計算 $\mathbf{u}$

從上式中可看出一個式子裡面要求兩個未知數 $(\mathbf{u}_x, (\mathbf{u}_y$。因此我們得靠一個 local window $W(x)$ 把附近的點聚集起來，並且假設 $(\mathbf{u}$ 是常數才能寫成以下 loss function： $$L(\mathbf{u}) = \sum_{W(x)}[\triangledown I(x(t),t)^T\mathbf{u} + I_t(x(t),t)]^2$$ 取導數為零來解： $$\triangledown L(\mathbf{u}) = 2 \sum \triangledown I(\triangledown I^T\mathbf{u} + I_t) \\ = 2 \sum ( \begin{bmatrix} I_x^2 & I_x I_y\\ I_x I_y & I_y^2 \end{bmatrix} \mathbf{u} + \begin{bmatrix} I_xI_t\\ I_yI_t \end{bmatrix} ) = 0$$ 也可以寫成矩陣式子 $G \mathbf{u} + \mathbf{b} = 0$，其中： $$G = \begin{bmatrix} I_x^2 & I_x I_y\\ I_x I_y & I_y^2 \end{bmatrix}\\ b = \begin{bmatrix} I_xI_t\\ I_yI_t \end{bmatrix}$$ 此方程式的解為： $$\mathbf{u} = -G^{-1}\mathbf{b}$$ 這個解得考慮一件事情：矩陣 G 是否存在反矩陣。當此 local window 的像素值都很接近時（$I_x = I_y = 0$），或是只存在一個方向的梯度時（$I_x=0$ or $I_y = 0$），G 的反矩陣不存在（也就是 aperture 及 blank wall 的問題），因此要求 $\mathbf{u}$ 的另一個前提是 local window 內要有足夠的 texture。

SSD & NCC criterion

SSD (sum of squared differences) 的精神是找到 $\Delta \mathbf{x}=(dx, dy)$ 來讓此 loss function 最小： $$E_t(dx, dy) = \sum_{W(x,y) [I(x+dx, y+dy, t+dt) = I(x,y,t)]^2}$$ 用這種演算法跟前面計算 $\mathbf{u}$ 的方法等價，但是不需要計算 $I(x,y,t)$ 的微分（及梯度）值。SSD 的缺點是無法處理像素值的 scaling 及 shift，因此 NCC (normalized cross-correlation) 可以用來解決此問題： $$NCC(h) = \frac{\sum_{W(x)}(I_1(x)-\overline{I}_1)(I_2(h(x))-\overline{I}_2)}{\sqrt{\sum_{W(x)}(I_1(x)-\overline{I}_1)^2 \sum_{W(x)}(I_2(h(x))-\overline{I}_2)^2}}$$ 其中 $h$ 為 transform，$\overline{I}$ 為 $I$ 的 local window $W(x)$ 中的平均像素值。 

Corner & Edge detector 

1. 基本的 corner detector：計算上面式子矩陣 G 的 eigenvalue，當最小的 eigenvalue 大於一個 threshold 時此點即為一個 feature point。
2. Harris corner detector：計算 $C(G) = det(G) + k \times trace^2(G) = (1+2k) \sigma_1 \sigma_2 + k(\sigma_1^2 + \sigma_2^2)$
3. Canny edge detector：先對圖片作高斯模糊去除雜訊，再計算梯度 $\triangledown I = [I_x, I_y]^T$，再求此梯度向量的 norm，訂一個 threshold 決定是否為 edge pixel。