An efficient parallel algorithm for motion estimation in very low bit-ratevideo coding systems

Motion estimation is widely used in video coding schemes in order to reduce the inherent temporal redundancy among the frames of a video stream. In pa rticular, low and very low bit rate video coding schemes need sophisticated motion models which usually require a large number of arithmetic operation s. In this paper we present a parallel algorithm for the most practical of these models. Specifically we implement the affine motion model on a hyperc ube-based multiprocessor This model covers the most usual kinds of motion a nd requires only a modest number of arithmetic operations. Also, the hyperc ube network can efficiently handle the non-regular data flow resulting from the parallel implementation of this model. In addition, we assume that our multiprocessor is fine grained, in contrast to most programmable architect ures used in video coding, where processors usually have large local memory . Apart from its practicality, the constraint of limited local memory makes the algorithm design more challenging and thus more theoretically interest ing. Finally, with regard to other proposals in the literature, our scheme is more general: whereas our scheme covers all kinds of motion supported by the affine motion model, the rest of the proposals deal only with a subset of these kinds. Copyright (C) 2000 John Wiley & Sons, Ltd.