Objective

2

The Markov random field (MRF) model for variational optical flow computing is a robust one. The MRF variational energy function includes the data and smooth terms. Brief propagation (BP) is a highly effective global method that minimizes the MRF energy function by iteratively transmitting messages from one pixel to the next in four directions. However

its computational cost remains high. The computational complexity of the BP method with a 3-level data pyramid is O(

$$ N$$

×

$$ L$$

2

×(10.5

$$T$$

+ 2))

where

$$ N$$

is the number of pixels in the image

$$ T$$

is the iterative time and

$$ L$$

is the width of spatial sampling. We proposed a new MRF model to calculate optical flow and a parallel method to minimize the MRF energy function

which can dramatically reduce computational time.

Method

2

The data term in the proposed MRF variational energy function for optical flow computing is derived from the optical flow constraint equation from the brightness constancy assumption proposed by Horn. The term is smoothed by a non-square penalty function to reduce the boundary effect. To realize parallel computing on the CUDA platform

we proposed an optimal parallel BP method to minimize the MRF energy function. This optimal method used a 3D grid

with four levels to perform the parallel method. At varying levels

the message was transmitted along different directions in the neighborhood. At each level

we assigned

$$ L$$

threads to one pixel and used the parallel dimension reduction method to calculate the message to be transmitted. Thus

we dramatically reduced the computational load of one thread and computational time. The dimension reduction method transforms the 2D energy function into two independent 1D energy functions and uses a low parabola envelope-based method to calculate the 1D energy function

whose computational complexity is O(4

$$L $$

2

). The parallel dimension reduction method simultaneously calculates the MRF energy functions of the different rows (or columns) in the label region of optical flow

whose size is

$$L $$

×

$$ L$$

by allowing each thread to correspond to a row (or column) in the region. Thus

the computational complexity of the proposed parallel dimension reduction method is reduced to O(4

$$ L$$

). All parallel processing steps were completed on the CUDA platform for general parallel computing on GPU. The first step is calculating the data term by assigning

$$ N$$

threads and letting each thread correspond to a pixel in the image. The corresponding computational complexity is O(

$$L $$

2

). The second step is the use of the proposed parallel dimension reduction method to calculate the message and transmit it to up

down

left

and right for

$$ T$$

times from the first to the third level in the data pyramid with three levels by assignin

g 4

$$L $$

threads to a pixel in the image. The corresponding computational complexity is O(3×4×

$$ L$$

×

$$T $$

). The last step is outputting the optical flow corresponding to the minimal message in each pixel by assigning

$$ N$$

threads and letting each thread correspond to a pixel in the image. The corresponding computational complexity is O(

$$L $$

2

). Thus

the entire computational complexity of this method is only O(2

$$ L$$

2

+ 12

$$ L$$

×

$$ T$$

) with three-level data pyramid.

Result

2

In the experiment for rotational sphere image sequence

the computational time was only 0.27 s

and corresponding computational time of the conventional method was 85 s. The computational efficiency of the proposed method was 314 times more than that of the conventional method. Our proposed method performed as rapidly as the Horn method

and faster than the Weickert (6 s) and Grauer-Gray (0.68 s) methods but slower than the Hossen method (0.01 s). In comparative experiments on errors with the Horn

Weickert

Hossen

and Grauer-Gray methods by using three image sequences (sphere image sequence with rotational moving

the Yosemite Valley image sequence with high change of brightness

and RubberWhale image sequence with many moving objects)

the proposed method achieved the lowest average endpoint error (AEE) (0.13

0.55

and 0.34

respectively) on all testing image sequences.

Conclusion

2

This paper proposed a novel parallel computing strategy of variational optical flow based on the MRF model by using a 3D grid with four levels to simultaneously transmit the message in the BP method along four directions

where multi-threads were assigned to one pixel for calculating the message to be transmitted. The results indicate that our proposed model has high computational efficiency and can obtain accurate optical flow from image sequences with rotational moving

high change of brightness and many moving objects. However

our proposed method requires a substantial amount of memory

which limits the width of spatial sampling. Therefore

our proposed method is unsuitable for calculating optical flows with large displacement from image sequences with high resolution.