Improved partial distortion search algorithm for rapid block motion estimation via dual-halfway-stop

Block motion estimation is a critical, yet computationally intensive, task for video encoding. Many fast block matching algorithms have been developed. Partial distortion search (PDS) algorithms generally produce less video quality degradation of the predicted images than those of conventional fast block matching algorithms (BMAs). However, the speedup gain of PDS algorithms is usually limited. We present an enhancement over a normalized PDS (NPDS) algorithm to reduce block matching motion estimation complexity further and improve video fidelity. The novelty of our algorithm is that, in addition to the halfway-stop technique in NPDS, a dual-halfway-stop (DHS) method, which is based on a dynamic threshold, is proposed so that block matching is not performed against all searching points. The dynamic threshold is obtained via a linear model utilizing already computed distortion statistics. An adaptive search range mechanism based on inter block distortion further constrains the searching process. Simulation results show that the proposed algorithm has a remarkable computational speedup. Particularly, it requires 92.0-99.4% less computation than full search (FS) and 8.0-91.0% less than NPDS. It encounters an average of 0.07 dB video degradation in PSNR performance compared to FS whereas it gains 0.01-0.12 dB over the NPDS algorithm.