A novel early-accepted partial distortion algorithm for fast block motion estimation

The speed improvement of partial distortion search algorithms is always limited by the partition size taken for comparison. By normalizing the comparison between the accumulated partial distortion and the current minimum distortion, the normalized partial distortion search (NPDS) algorithm can virtually maximize the speed-up ratio under this theoretical limit. A novel early acceptance (EA) technique is first proposed to achieve further speed-up. Unlike most conventional algorithms that only reject impossible candidate motion vectors, our algorithm is capable of accepting potential minimum candidates at a very early stage. Simulation result shows that our EA technique can increase the speed-up ratio of NPDS up to 5.46 times more with only 0.04 dB PSNR degradation. With our new quality control at q=0.5, our early-accepted partial distortion search (EAPDS) algorithm provides a speed-up ratio of around 28.45-36.60 times while maintaining a small amount of PSNR degradation from 0.18-0.31 dB as compared to full search (FS). Experiments also prove that our algorithm out-performs NPDS in both speed and accuracy.