A fast motion estimation algorithm for an MPEG Video coder

Video compression is becoming increasingly important with the advent of the compression standards and broadband networks. Typical applications include high-definition television, multimedia communications, etc. There are two kinds of redundancies that exist in a video sequence, namely, temporal and spatial which are exploited to achieve compression. The spatial redundancies are removed by using techniques such as discrete cosine transform, vector quantization, etc. while the temporal redundancies are removed by the motion estimation/compensation techniques. Recently, several block based motion estimation algorithms have been reported in the literature. However, these algorithms are either computationally expensive or converge to a local optimum. In this paper, we propose a reduced complexity block-matching motion estimation algorithm for an MPEG video coder. This algorithm consists of a layered structure and hence does not converge to a local optimum. Most importantly, it employs a simple matching criterion, namely, the modified pixel difference classification (MPDC) and hence results in a reduced computational complexity. The MPEG video coder has been simulated using the proposed layered structure MPDC algorithm (LSA-MPDC). Simulation results indicate that the LSA-MPDC algorithm achieves a good performance for both slow and fast moving sequences. In addition, the hardware implementation of the LSA-MPDC algorithm is very simple because of the binary operations used in the matching criteria.