A hierarchical block matching algorithm using partial distortion measure

Most of the fast block matching algorithms reduce computation by matching only some of the locations inside the search area. In this paper, we propose a novel algorithm-hierarchical partial distortion search (HPDS)-which reduces the computational complexity of each distortion measure instead of the number of searching locations by using partial distortion measure. The partial distortion is obtained by calculating the distortion between the decimated block of current frame and that of previous frame. The motion vector is found hierarchically by searching the candidate motion vectors found from previous level of search. Each higher level uses partial distortion functions with decreased ratio of decimation. Experimental results show that the proposed algorithm can give 5 times speed up compared with full search while maintaining the MSE performance very close to full search. Moreover, the algorithm can achieve 12 times speed up when the MSE performance is kept close to that of three-step search. The proposed algorithm is suitable for applications such as HDTV and MPEG-2 where motion estimation accuracy is important. It is also suitable for real-time applications such as video conferencing and H.263 where encoding speed are critical