Open Collections

A fast motion estimation algorithm for mobile devices

University of British Columbia

With increasing availability of camera-equipped cellular telephones, the demands for video transmissions over mobile networks are growing significantly. Third generation mobile networks such as lxEV-DO support data rates high enough for transmissions of compressed video, but reducing the power consumption of video compression in mobile devices is an ongoing challenge. The large number of computations required for motion estimation is the main cause for this consumption. In this research, we propose novel spatial and spatial-temporal based motion estimation methods, which sort the sums of absolute difference (SAD) according to specific threshold values to facilitate efficient searches for the local optimal motion vectors. The proposed methods drastically reduce the computation costs of the motion estimation process over the existing techniques. The proposed algorithm using only spatial correlation performs direct subtraction between the current and previous video frames to obtain a difference frame, which is then partitioned into macroblocks of 16x16 (256) pixels with each pixel having 256 grey levels. For each macroblock we compute the SAD by simply adding all grey levels of the 256 pixels. Next, the average and standard deviation of all macroblocks' SADs are calculated and all SADs are sorted in descending order. Based on thresholds calculated from the mean and standard deviation, the sorted SAD values are divided into three groups corresponding to different degrees of motion, and different computationally efficient scanning processes are applied to the respective macroblocks in each group to search for the motion vectors. To further reduce computations, only a subset of each macroblock is scanned. New types of subsets are proposed for this purpose. The proposed algorithm that uses both spatial and temporal correlations is similar to the above algorithm, except that the temporal correlations are taken into consideration in computing the difference frame, since each macroblock is highly correlated to the corresponding macroblock in the previous frame as well as the surrounding macroblocks in the same frame. Performance evaluations showed that, for the same picture quality, the proposed algorithms use only 0.5% of the computations of the full search method and are almost 19 times faster than 4SS, the best presently available conventional method. When compared to the most recently published non-conventional motion estimation method, which outperforms all the existing methods, our approach improves the computational speed by 7.5 times.

Text

2009-12-11

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/16534

Electrical and Computer Engineering

University of British Columbia

UBCV

DSpace