A Fast PDE Algorithm Using Improved Uniform Sub-block Matching Scan

Full search motion estimation in real-time video coding requires large amount of computations. Reducing computational cost for full search motion estimation is critical research issue for enabling fast real-time video coding such as MPEG-4 advanced video coding. In this paper, we propose a fast partial distortion algorithm using normalized dithering matching scan to get uniform distribution of partial distortion. Our algorithm is based on normalized dithering order matching scan and calibration of threshold error using LOG value for each sub-block continuously for efficient elimination of unlike candidate blocks fast while keeping the same prediction quality compared with the full search algorithm. Our algorithm reduces about 65% of computations for block matching error compared with conventional PDE (partial distortion elimination) algorithm without any prediction quality.