Evolving object-based coding standards, such as MPEG-4, introduce radically different functionalities at the expense of increased computational complexity, and there exists a demand for greater compression to permit communication over widely available low bandwidth channels, for example in mobile multimedia communications. Current developments which permit arbitrary-shaped objects to be encoded and decoded as separate video object planes (VOPs) have largely adopted existing coding techniques and then modified and optimised the methods for an object-based framework. Fixed size block matching (FSBM) has remained the preferred approach to motion estimation due to its backward compatibility with previous standards. The main aim of this project was to develop efficient motion estimation and shape coding techniques specifically designed for object-based video coding.

Investigations showed that a variable size block matching (VSBM) motion compensation approach can offer significant coding efficiency improvements over FSBM, while maintaining the simplicity of implementation and computational complexity of FSBM. The technique was extended to produce a modified VSBM (MVSBM) motion compensation strategy that exploits irregularly shaped areas of uniform motion within small objects. Both VSBM and MVSBM utilise a quad-tree for the representation of the irregular motion segmentation structure, which is predictively coded and transmitted with the motion compensation information. Since the arbitrary areas are a composition of 4 x 4 blocks, the whole structure can be encoded using a quad-tree, where multiple blocks undergoing the same motion form a single area. While a motion vector per block representation would normally be very expensive to transmit, a motion vector redundancy coding (MVRC) scheme has proved ideally suited to producing compact descriptions of MV structures exhibiting high spatial redundancy. Additionally, a temporal quad-tree coding (TQC) scheme was developed that exploits any temporal redundancies between successive quad-tree structures, using a differential coding mechanism. In comparison with conventional motion information coding schemes, the combined algorithms provide bit coding reductions of up to 21% for the same PSNR.

A shape coding strategy which adapts the MPEG-4 arbitrary shape coding techniques to a variable block size framework has been developed. It successfully integrates the shape and quad-tree coding requirements of VSBM and MVSBM in a unified structure while minimising temporal redundancies. The coding efficiency of the combined MVSBM motion compensation and shape coding cost is compared with the MPEG-4 motion vector and shape coding requirements. For the same quality prediction, the new scheme shows a bit coding reduction of up to 15%. The shape coding strategy was further improved, making it appropriate for small video objects undergoing fast shape changes due to either rapid object movement or camera focal length changes. Compared with conventional motion and shape coding, the new technique provides notable bit coding improvements for the same PSNR.

The combined motion compensation and shape coding algorithms have been implemented in a hybrid video object codec which employs shape adaptive DCT texture coding. Evaluations on a wide selection of test sequences confirm the quoted coding efficiency gains for the same PSNR and perceptual quality of the reconstructed images. Additionally, the techniques developed are shown to be appropriate for the coding of multiple video objects, and are readily scalable.

More details are available through the MCG website.

The aim of this project is to provide a realistic route to improved motion estimation for moving picture compression by utilising the increasing power of parallel processing. An existing optical flow technique will be improved, so that it can be used to generate unambiguous areas of uniform motion within an image sequence; this technique is computationally intensive, but is amenable to parallel implementation. The performance of the new estimation method can then be compared with conventional block matching. The results of this work should be immediately applicable and can be used within the scope of existing coding standards such as MPEG.

Improved methods of efficiently coding moving area information will also be investigated. This will be a `bottom-up' approach driven by pixel level motion vector information derived by the optical flow method. Parallel implementation strategies will be considered at several stages of algorithm development. Parallel implementations on relatively coarse and fine grain distributed systems and more tightly coupled shared memory machines will be investigated. The project will have access to all three of these platforms, and as they are industry standards the software products should be widely usable.

More details are available through the MCG website.

Storage and transmission of digital video information necessitates the use of compression techniques in order to satisfy the bandwidth limitations of current technology. Most video coding techniques achieve compression by minimising statistical and perceptual redundancies in the three dimensional video signal. The nature of video sequences usually implies a high degree of temporal correlation between successive frames, a property most commonly exploited through motion compensation (MC). Most video coding standards employ fixed size block-matching (FSBM) motion compensation, a technique where a prediction for the frame being coded is constructed from fixed size blocks of a reference frame, assumed to undergo simple translational motion. The latter is rarely true for natural video sequences, although it becomes more valid as the block size decreases.

This thesis concentrates on MC techniques that address the deficiencies introduced by the regular block structure while maintaining the simplicity of implementation and the computational complexity of FSBM. A frame-based variable size block-matching (VSBM) strategy is developed and the problem of compactly coding the variable block structure and the motion vector information is addressed. VSBM is shown to achieve a significant improvement in terms of coding efficiency over FSBM, for the same quality prediction.

The frame-based VSBM techniques are further extended to address the problem of motion compensation and motion vector coding, in an object-based video coding framework, where the video scene is composed of a collection of arbitrary shaped objects. A scheme that removes motion vector spatial redundancy is described. Additionally, a modified VSBM (MVSBM) technique is developed, that can identify arbitrary areas undergoing uniform motion. MVSBM is better suited to small objects with high degrees of disparate motion. The coding efficiency of both object-based MC coding schemes, is further improved by a temporal quad-tree coding strategy, and by the integration of shape and motion information. The new techniques are shown to significantly improve coding efficiency when compared to object-based FSBM approaches.

The main aim of this dissertation is to consider how large scale parallelism in the form provided by general purpose parallel computers can be used in computer graphics and more specifically 3D visualisation. We look into the facilities provided by the Parsytec Supercluster and investigate the theoretical and practical limitations of distributed memory systems and message-passing communication networks. We prove that for parallel systems with a single output,I/O bound systems can achieve an optimal performance that is only dependent on the ratio of calculation to communication times.

A comparative study of different 3D visualisation algorithms is presented, the key points concentrating on the parallel aspects of such algorithms and how they can be used on our system. The final goal is the implementation of a generic graphics library that provides the necessary scalable framework for further investigation into parallel visualisation.