Back to search

University of British Columbia

A fast motion estimation algorithm for mobile devices

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Applied Science - MASc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor dc:publisher
University of British Columbia
Year dc:date
2005

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Lee, Ho-Jae

Rights

dc:rights
Statement dc:rights
  • 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.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/16534

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Lee, Ho-Jae. A fast motion estimation algorithm for mobile devices. master's thesis, University of British Columbia, 2005. http://hdl.handle.net/2429/16534