Optical Flow – Pyramid Lucas & Kanade Method

by allenlu2007

承前文 optical flow 中最常見的方法是 sparse optical flow + constant brightness.

本文主要參考 http://www.cs.ucf.edu/~gvaca/REU2013/p4_opticalFlow.pdf

 

2D motion constraint (Least Square)

NewImage

NewImage

 

Optical flow equation: fx u + fy v = – ft

NewImage

 

如果使用 3×3 window (小 pixel patch 有 uniform speed)

 

NewImage

 

Simple Lucas-Kandade Example

LK implementation and example 可以參考 UCF 的文章。

http://www.cs.ucf.edu/~gvaca/REU2013/p4_opticalFlow.pdf

Example 1: car1.jpg and car2.jpg

Animated 效果有以參考下文。

http://eric-yuan.me/coarse-to-fine-optical-flow/

不過此文對 Horn-Schunck method 的理解似乎有誤。HS method 是 global method. 

和 LK 的 local method 不同。最後 color motion field 的 HS 結果先存疑。

可以參考下文

http://www.icg.tugraz.at/courses/lv710.080/info/motion_estimation.pdf

 NewImage

Baker’s flow visualization code 如下。

NewImage

 

Simple LK 結果如下圖。這是 window size 設為 20 (-10 到 +10 for both x and y direction, 也就是 21×21)

NewImage 

如果設為 window size = 2, 也就是 3×3, 同時 flow_color normalization value = 6 如下

NewImage

可以看出雖然 local accuracy 比起 window size=21×21 要好。但 robustness 確比較差。

同時在移動車子的 texture-less 的部份 (車子引擎板) 會有 aperture 問題。

因為 LK 只是 local solution.  而非是 variational (integral) 的 optical flow global solution.

兩個 solution:  (1) 增加 window size 如 21×21.  有比較好; 但 trade-off 是比較 robust 但也比較模糊。

(2) pyramid LK 如下。 

 

Pyramid Image Processing

Simple LK 在數學上簡潔且有高效率的算法 (Least square, pinv in Matlab).

但有幾個問題。首先 simple LK 是 2D motion constraint. 對於 3D motion maps to 2D 只是近似。

第二是 accuracy vs. robustness 的 trade-off

第三是 aperture 問題。

 

Pyramid image representation 是一種 multi-scale image representation 如下。

L0 是 base or original layer.  L1 是 1/2×1/2 layer from L0.  L2 則是 1/2×1/2 layer from L1.

一般最多就到 L3 or L4.  可以參考 wiki Pyramid (image processing)

NewImage

 

可以參考本文解釋 Image pyramid representation.

其中 blue and subsampling 是由 (2) 產生。基本上是一個 spatial low pass filter for anti-aliasing purpose.

[1/4 1/2 1/4] x [1/4 1/2 1/4]’

NewImage

NewImage 

 

Pyramid + Lucas Kanade Optical Flow

如何結合 pyramid image 和 LK optical flow?

先從 top image Lm (最小的 image) 開始。用 LK algorithm 算出本層的 u(Lm).  

再用 u(Lm) 做為 initial guess, 算出 Lm-1 層。(避免算 pinv?)

當然因為 Lm-1 層的 displacement 會和 Lm 層有一些不同。因此要再加上 residue.

這個 residue 是用 LK method 算出。

 

最後的結果參考 reference:

NewImage

NewImage

 

其實 G 就是 (A’A);  b = A’f

所以 optical flow 也就是 LK method.   Pyramid 的好處在那裡?  似乎 Bouguet 提出他的論點如下。

在 LK method 中,window size (如上例 3×3 window size) 是需要 trade-off 的參數,between accuracy and robustness.

如果 window size 太小,accuracy 變好,但 robustness 變差。反之則 robustness 變好,但 accuracy 變差。使用 pyramid LK 似乎可以解決這個問題? 但仍需決定 ωx and ωy (window size)? 

The two key components to any feature tracker are accuracy and robustness. The accuracy component relates to the local sub-pixel accuracy attached to tracking. Intuitively, a small integration window would be preferable in order not to “smooth out” the details contained in the images (i.e. small values of ωx and ωy). That is especially required at occluding areas in the images where two patchs potentially move with very different velocities. The robustness component relates to sensitivity of tracking with respect to changes of lighting, size of image motion,… In particular, in oder to handle large motions, it is intuively preferable to pick a large integration window. Indeed, considering only equation 1, it is preferable to have dx ≤ ωx and dy ≤ ωy (unless some prior matching information is available). There is therefore a natural tradeoff between local accuracy and robustness when choosing the integration window size. In provide to provide a solution to that problem, we propose a pyramidal implementation of the classical Lucas-Kanade algorithm. An iterative implementation of the Lucas-Kanade optical flow computation provides sufficient local tracking accuracy.

 

Simple LK and Pyramid LK 的差異可以參考此文。

http://eric-yuan.me/coarse-to-fine-optical-flow/

Pyramid LK (或是 coarse-to-fine LK) 結果如下。

可以看出引擎板的表現如下。比起 LK 好不少。更進一步就是用 variational method (Horn & Schunck).

NewImage 

 

Advertisements