Adjustable partial distortion search algorithm for fast block motion estimation

The quality control for video coding usually absents from many traditional fast block motion estimators. A novel block-matching algorithm for fast motion estimation named the adjustable partial distortion search algorithm (APDS) is proposed. It is a new normalized partial distortion comparison method capable of adjusting the prediction accuracy against searching speed by a quality factor k. With adjustability, APDS could act as the normalized partial distortion search algorithm (NPDS) when k is equal to 0, and the conventional partial distortion search algorithm (PDS) when k is equal to 1. In addition, it uses a halfway-stop technique with progressive partial distortions (PPD) to increase early rejection rate of impossible candidate motion vectors at very early stages. Simulations with PPD reduce computations up to 38 times with less than 0.50-dB degradation in PSNR performance, as compared to the full-search algorithm (FS). Experimental results show that APDS could provide peak signal-to-noise ratio performance very close to that of FS with speedup ratios of 7 to 16 times, and close to that of NPDS from 22 to 32 times, respectively, as compared to FS.