Comparison between Large Displacement Optical Flow Algorithms

Background

Large Displacement

Optical flow has been considered an almost solved problem with the algorithm suggested by Lucas and Kanade[1]. However, due to the intrinsic property of the algorithm based on constant brightness assumption in neighbor pixels often the conventional algorithm[1,2] fails when there is a large displacement due to fast movement of the object, camera motion or occlusions.

Large Displacement Optical Flow Algorithm

Brox and Malik proposed an optical flow algorithms that adapts variational approach combining it with descriptor matching[3]. The idea of their work is to find the corresponding region using sparse SIFT[4] descriptor. Their method can be described like following as a formula.

Energy

The algorithm suggested by Brox and Malik[3] mainly consists of three parts; Data term(color and gradient constancy), smoothness term and descriptor matching term.

Methods - Deep Flow and Deep Matching

Deep Flow

In [5], Deep Flow has been suggested that uses Deep Matching in descriptor matching. In spirit, Deep Flow is similar to Brox and Malik's work[3] in several aspects that Deep Flow also uses variational flow in their energy minimization and incorporated descriptor matching to find the corresponding regions, but it is different in that Optical flow has been considered an almost solved problem with the algorithm suggested by Lucas and Kanade(Lucas and Kanade, 1981). However, due to the intrinsic property of the algorithm based on constant brightness assumption in neighbor pixels often the conventional algorithm(Lucas and Kande, 1981 & Horn Schunck, 1981) fails when there is a large displacement due to fast movement of the object, camera motion or occlusions.

Large Displacement Optical Flow Algorithm

Brox and Malik proposed an optical flow algorithms that adapts variational approach combining it with descriptor matching(Brox and Malik, 2009). The idea of their work is to find the corresponding region using sparse SIFT(Lowe, 1999) descriptor. Their method can be described like following as a formula.

Bilinear/Bicubic

A linear combination of the nearest N neighbors in any direction for N = 1 (bilinear) or N = 3 (bicubic). For a given matrix of known values R(x,y), the interpolated set of values r(x,y) can be computed:

$r(x,y)=\sum _{u,v=-N}^N{h}_r(u,v)R(x-u,y-v)$

where h_r is the 2-D kernel containing interpolation weights based on relative neighbors of a given pixel.

$h_1=\frac{1}{4}\left[\begin{array}{ccc}0& 1& 0\\ 1& 4& 1\\ 0& 1& 0\end{array}\right],h_3=\frac{1}{256}\left[\begin{array}{ccccccc}0& 0& 0& 1& 0& 0& 0\\ 0& 0& -9& 0& -9& 0& 0\\ 0& -9& 0& 81& 0& -9& 0\\ 1& 0& 81& 256& 81& 0& 1\\ 0& -9& 0& 81& 0& -9& 0\\ 0& 0& -9& 0& -9& 0& 0\\ 0& 0& 0& 1& 0& 0& 0\end{array}\right]$

Smooth Hue Transition

Operates on the assumption that the hue of a natural image (chrominance/luminance, or red/green and blue/green) changes smoothly in local regions of that image. In order to calculate this, the green channel is first interpolated using bilinear interpolation. A missing red point r(x,y) is calculated from known red values R(x,y) and green values G(x,y).

$r(x,y)=G(x,y)*\frac{1}{2}(\frac{R(x-1,y)}{G(x-1,y)}+\frac{R(x+1,y)}{G(x+1,y)})$

The sum shown above is valid for when the interpolation pixel has two adjacent pixels in the same row. The equation is altered slightly for two adjacent pixels in the same column, or when there are four adjacent pixels in the corners. The missing blue pixels are calculated in the same way.

Detecting Forgeries

Regardless of the type of interpolation used in a given image, the estimated pixels should exhibit a strong correlation, or dependence, on their surrounding pixels. If one can categorize each pixel as either correlated or independent with respect to other pixels, one should see a periodic pattern that mimics the CFA used to construct the image. Even if an altered image does not have any visual cues that point to its forgery, inspecting the correlation of pixels to one another can potentially expose which parts of an image were altered. It is important to note that, even if an image has been altered, the mentioned correlations may still be kept intact. In this way, detecting forgeries through CFA interpolation is one tool out of many used to detect forgeries.

References

1. B. D. Lucas and T. Kanade. An iterative image registration technique with an application to stereo vision. In proceedings of the 7th International Joint Conference on Artificial Intelligence, 1981.
2. B. Horn and B. Schunck. Determining optical flow. Artificail Intelligence, 17:185-203, 1981.
3. T. Brox, C. Bregler, and J. Malik. Large displacement optical flow. In IEEE Conference on Computer Vision and Pattern Recognition(CVPR), 2009.
4. D. Lowe. Distintive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2):91-110, 2004.