Efficiency-Complexity curve based method for evaluating adaptive search range algorithms in motion estimation

The well known Rate-Distortion (RD) curve and the average Peak Signal to Noise Ratio (PSNR) difference between two RD curves (Delta PSNR) are frequently and widely used for evaluating how well a fast motion estimation (ME) algorithm performs in encoding efficiency. Besides this one for encoding efficiency, there usually exists another parameter, such as ME executing time or average search point number for processing one macroblock (ASP/MB), to evaluate the complexity of this fast ME algorithm. In the other hand, adaptive search range (ASR) ME algorithms are proved to be more fundamental, regular and controllable than normal fixed search pattern (FSP) ME algorithms. Thus for especially evaluating ASR ME algorithms, an Efficiency-Complexity (EC) curve based method is proposed and discussed in this paper.