New pixel-decimation patterns for block matching in motion estimation

This paper presents a boundary-based approach towards pixel decimation with applications in block-matching algorithms (BMAs). The proposed approach is based on the observation that new objects usually enter macroblocks (MBs) through their boundaries. The MBs are selected based on boundary region matching only. The boundary-based patterns can be used to speed up motion estimation with marginal loss in image quality. Different decimation levels for image quality trade-off with computational power have been presented. The mathematical intuition in support of the proposed patterns has been discussed. Apart from the boundary-based approach, the novelty in our contribution also lies in performing a genetic algorithm (GA)-based search to find optimal M  -length patterns in an N×NN×N block. The resultant patterns are found to have better values of spatial homogeneity and directional coverage metrics, as compared to the recently proposed NN-queen decimation lattices. Subsequently, we obtain new pixel-decimation patterns by combining the proposed boundary-based patterns with NN-queen patterns and the GA-based patterns. Experimental results demonstrate considerably improved coding efficiency and comparable prediction quality of these new patterns as compared to existing decimation lattices.