Adaptive irregular pattern search with zero-motion prejudgement for fast block-matching motion estimation

A novel fast block matching algorithm, called adaptive irregular pattern search with zero-motion prejudgement (AIPS-ZMP), is proposed in this paper. The algorithm effectively exploits the spatial and temporal correlation existed among the motion vectors (MVs). In AIPS-ZMP, an adaptive irregular pattern (AIP) is dynamically formed for each block according to its spatial and temporal neighboring MVs to identify the most promising search center so that unnecessary intermediate searches and the risk of being trapped into local-minimum matching-error point are both avoided. The refined search is then performed from this center to find out the target MV. To further speed up the search, zero-motion prejudgement (ZMP) technique is embedded in the AIPS´s framework to detect static blocks before invoking any search. Consequently, fairly large amount of computational gain is obtained with little degradation on picture quality. Compared with the fast BMA adopted in MEG-4 Verification Model (VMS) - diamond search (SD), our proposed AIPS-ZMP method improves the average peak signal-to-noise ratio (PSNR) by up to 0.67 dB with computational gain in the range of 2.12∼5.14 times.