Fast motion estimation for wavelet-based video coding

Multi-resolution motion estimation (MRME) has to be done in the wavelet domain for wavelet-based video coding. MRME tries to use the motion vectors obtained in the highest resolution level as an initial estimate and performs refinement in the remaining subbands in the lower levels. Based on a simple analysis, we have found that the pixel matching errors with similar magnitudes tend to appear in clusters for natural video sequences in the spatial domain and wavelet domain. In this paper, we report that the clustering property also exists in the wavelet domain which can significantly improve the efficiency of the partial distortion search (PDS) algorithm. This clustering characteristic appears in the hierarchical structure of the wavelet pyramid. A new wavelet based motion estimation technique is proposed, which makes use of the hierarchical structure of the wavelet pyramid into a new clustered pixel matching error partial distortion search (CPME-PDS). The computational time can be reduced substantially. This proposed algorithm is suitable for multi-resolution applications including DTV, HDTV and mobile videos standards.