Parallelisation of Block Matching Motion Estimation Algorithms   M.K. Steliaros & R.A. Packwood & G.R. Martin.    University of Warwick Research Report RR320, January, 1997, 12pp.    Abstract: Block matching motion estimation accounts for a high computational overhead in most low bit-rate video coders intended for video-conferencing and multimedia applications. Conventional fixed size block matching (FSBM) and more sophisticated variable size block matching (VSBM) algorithms are profiled to determine how parallelism can be applied to increase efficiency. Three parallel implementations are considered: a homogeneous workstation network using PVM; a Parsytec Super-Cluster, 128-node T800 transputer-based MIMD machine; and a shared memory multiprocessor, using a `threads' programming model. It is shown that significant improvements in computational performance can be made, even on commonly available computing platforms. Using an MPEG-4 image test sequence, detailed evaluation of a POSIX-conformant threads implementation resulted in near-theoretical maximum speedups being obtained.