A novel block motion estimation algorithm with controllable quality and searching speed

Quality control for real-time video applications, such as the very-low-bit-rate video conferencing or the high quality video entertainment, is usually absent from many traditional fast block motion estimators. A novel block-matching algorithm for fast motion estimation, named adjustable partial distortion search algorithm (APDS), is proposed. It is a new normalized partial distortion comparison method with adjustability on prediction accuracy against searching speed using a quality factor k. When k is set to 0, APDS could act as the normalized partial distortion search algorithm (NPDS). When k is set to 1, APDS perform as the conventional partial distortion search algorithm (PDS) and could give the best quality as obtained in the full search algorithm (FS). In addition, it uses a halfway-stop technique with progressive partial distortion (PPD) to increase the chance of rejection of impossible candidate motion vectors at very early stages. Simulations with PPD show that there is 24-62 times computational reduction with 0.31-0.83 dB PSNR performance degradation, as compared to the FS algorithm. Experimental results show that APDS could provide PSNR performance very close to the full search algorithm with speedup ratios of 18 times, and to NPDS with 32 times, respectively, as compared to the FS algorithm