Adaptive double-layered initial search pattern for fast motion estimation

Multimedia communication relies on data compression technology to reduce the data bits of transmission. Motion compensation is the key function in exploiting temporal redundancy for compression in most video coding standards. For example, fixed search pattern motion estimation algorithms such as hexagonal search (HEXBS) usually spend extra search steps to confirm near-zero motion vectors. Divide and conquer methods such as the efficient three-step search (E3SS) are not optimized for the probability model of motion vectors. This paper proposes a pair of complementary double-layered (inner layer and outer layer) initial search patterns to reduce computational complexity. The inner-layer search is applied first and tests for small motion. Afterwards, the outer layer search serves as a guard line to catch large motion. It is used only when the inner search layer fails to find a good solution. Experimental results of motion estimation on various QCIF/CIF video sequences show that the proposed algorithm achieves image quality similar to diamond search but with the search point cost as low as cross-diamond-hexagonal search.