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.