One-pass computation-aware motion estimation with adaptive search strategy

A computation-aware motion estimation algorithm is proposed. Its goal is to find the best block matching results in a computation-limited and computation-variant environment. Our new features are one-pass flow and adaptive search strategies. The prior scheme allocates more computation to the macroblock with the highest distortion in the entire frame step by step. This implies that random access of macroblocks is inevitable, and the search pattern must be determined in advance. The random access flow requires a huge size of memory for all macroblocks to store the up-to-date minimum distortions, best motion vectors, and searching steps. In contrast, the one-pass flow can not only significantly reduce the memory size but also effectively use the context information of neighboring macroblocks to achieve faster convergence and better quality. Moreover, to improve video quality when computation resource is still sufficient, the search strategy is allowed to change adaptively from diamond search to three step search, and then to full search. Last but not least, traditional block matching speedup methods are combined to provide much better computation-distortion curves.