Optical Flow Estimation With Horn-Schunck Method

Mar 25, 2015

Contents

Introduction

Estimating the motion of every pixel in a sequence of images is a problem with many applications in computer vision, such as image segmentation, object classification, and driver assistance.

In general, optical flow describes a dense vector field, where a displacement vector is assigned to each pixel, which points to where that pixel can be found in another image. An example is shown as below.

l5qMbq.md.jpg

This project is a solution for Assignment 3 Optical Flow Estimation of the course Image Processing and Computer Vision (ENGG 5104, CUHK, 2015 Spring). In this project, I implement an algorithm solving the optical flow map (u,v) between two image frames using Horn-Schunck Method.

Horn-Schunck Method

Horn-Schunck method is a classical optical flow estimation algorithm. It assumes smoothness in the flow over the whole image. Thus, it tries to minimize distortions in flow and prefers solutions which show more smoothness. In this assignment, we will implement the modern version of Horn-Schunck method, using pyramid-based coarse-to-fine scheme to achieve better performance, similar to that of Lucas-Kanade method. Many current optical flow algorithms are built upon its framework.

The objective is formulated as a global energy functional which is then minimized. Let the image be p = (x,y) and the underlying flow field be w(p) = (u(p),v(p), 1), where u(p) and v(p) are the horizontal and vertical components of the flow field, respectively. Under the brightness constancy assumption, the pixel value should be consistent along the flow vector, and the flow field should be piecewise smooth. This results in an objective function in the continuous spatial domain

l57TG4.jpg

where ∇ is the gradient operator, λ weights the regularization, I1 and I2 are two corresponding images.

Variational Framework

To solve Eq. (1), we use an iterative flow framework. It assumes that an estimate of the flow field is w, and one needs to estimate the best increment dw(dw=(du,dv)), to update w. The objective function in Eq. (1) is then changed to

l57Hz9.jpg

Let

l57Ls1.jpg

With first-order Taylor expansion:

l577RJ.jpg

In the above equation we add variable p into du and dv to index du and dv in images.

For easy computation, we vectorize u, v, du, dv into U, V, dU, dV, and Dx, Dy to denote derivative filters in x and y direction. The continuous function E(du,dv)in Eq. (2) can be discretized as E(dU,dV).

Optimization

The main idea to solve the above equation is to find dU,dV so that the gradient

l575IU.jpg

We can derive

l57Oqx.jpg

L is a Laplacian filter defined as

l57jZ6.jpg

The term of dU in gradient is derived similarly. Therefore, solving the gradient equation can be performed in the following linear system

l57vdK.jpg

Evaluation

Having built the pyramids and solve Eq. (8) in each level iteratively, the result in the finest level is obtained. We evaluate optical flow results by two measures: Average Angle Error (AAE) and End Point Error (EPE). They are defined by comparing flow result with the ground truth flow. The lower the AAE and EPE are, the better the optical flow performance is. Also we can visually estimate your result from visualization of the flow map (using flowToColor function).

Algorithm Flowchart

Input: frame1,frame2,λ
Build image pyramid;
Initialize flow = 0;
For i= numPyramidLevel:1
    Initialize flow from previous level;
    Build gradient matrix and Laplacian matrix;
    For j=1:maxWarpingNum
        Warp image using flow vector;
        Compute image gradient Ix, Iy, and Iz;
        Build linear system to solve HS flow;
        Solve linear system to compute the flow;
        Use median filter to smooth the flow map;
    EndFor
EndFor
Output: flow

Experimental Results

Five pairs of images are tested, the results as execution time are shown below:

Evaluation measure of picture above: AAE 9.669 average EPE 1.010.

l5bVXR.md.jpg

l5bA1J.jpg
</p> Evaluation measure of picture above: AAE 4.901 average EPE 0.456.

l5bD3Q.md.jpg l5bw4S.jpg Evaluation measure of picture above: AAE 9.812 average EPE 0.297.

l5bB9g.md.jpg

l5bcBq.jpg

Evaluation measure of picture above: AAE 4.673 average EPE 0.250.

l5b4CF.md.jpg

l5bf4U.jpg

Evaluation measure of picture above: AAE 12.257 average EPE 1.312.

Some regions in the image groups with visible changes are circled to show that the Warped Image is more similar to frame 1 than frame 2, which indicates that the estimated optical flow is considerately accurate, since the the Warped Image representing frame2 warped to frame1 accroding to the estimated optical flow.

License (CC) BY-NC-SA | Subscribe RSS | Email hi@fzheng.me