Back to articles
Volume: 33 | Article ID: art00014
A Polar Coordinate Perspective on Motion Search in Video Coding
  DOI :  10.2352/ISSN.2470-1173.2021.10.IPAS-260  Published OnlineJanuary 2021

Video coding heavily relies on motion compensated predictive coding to achieve its compression efficiency. As a central component, the block matching motion search exploits the tradeoff between encoder complexity and compression efficiency. The diamond search and its variants are widely used in video encoders. They typically start with the largest search step size and scale down the step size by half at each stage thereafter. To cover an N×N pixel search region, the diamond search class requires a search complexity of O(logN) check points. In this work, we view the motion search as a sampling problem around the initial reference point in polar coordinates. We modify the sampling pattern at each search stage to better approximate a circle. The search radius is scaled down by √2 between stages, in contrast to the factor of 2 used by the diamond search class, such that the sampling density is increased by a factor of 2 between stages. It retains a search complexity of O(logN) over an N×N pixel region, with a linear increment as compared to the diamond search. It is experimentally shown that the proposed search pattern provides compression gains at the expense of a modest increase in encoder complexity.

Subject Areas :
Views 24
Downloads 1
 articleview.views 24
 articleview.downloads 1
  Cite this article 

Jingning Han, Paul Wilkins, Yaowu Xu, "A Polar Coordinate Perspective on Motion Search in Video Codingin Proc. IS&T Int’l. Symp. on Electronic Imaging: Image Processing: Algorithms and Systems XIX,  2021,  pp 260-1 - 260-6,

 Copy citation
  Copyright statement 
Copyright © Society for Imaging Science and Technology 2021
Electronic Imaging
Society for Imaging Science and Technology
IS&T 7003 Kilworth Lane Springfield, VA 22151 USA