Motion estimation techniques for digital TV: a review and a new contribution
---
paper_title: Multigrid block matching motion estimation for generic video coding

paper_content:

Motion estimation and compensation techniques have shown their efficiency to reduce temporal redundancies in video coding applications. Motion estimation analyzes the movement of objects in the scene. The resulting motion information allows to improve interframe predictive coding. This work deals with the study of motion estimation algorithms in the framework of image sequence coding. The desired features of a motion estimation algorithm in order to achieve high performances are the following. First, the algorithm provides an accurate motion compensated prediction. Second, it requires a low overhead information. Third, it leads to a smooth motion field close to the true motion in the scene. However, it is straightforward that more precise motion vectors need a higher overhead information, and vice versa. Consequently, a trade-off on the motion estimation complexity has to be found in order to optimally balance these two conflicting features. The motion estimation algorithm developed in this dissertation takes into account the above remarks. Block matching techniques are a promising approach for motion estimation in image sequence coding. In this framework, the classical full-search algorithm is widely used due to its simplicity and ease of hardware implementation. Nevertheless, it suffers serious drawbacks. In particular, it performs poorly on moving edges and introduces block artifacts in the motion compensated frame. Furthermore, it tends to produce noisy motion fields. Finally, it requires a high computational complexity. In this study, we aim at overcoming the above drawbacks in order to fulfill all the above desired features of a motion estimation algorithm. In this dissertation, we propose a locally adaptive multigrid block matching motion estimation technique. The motion vectors are iteratively refined on a set of grids with different resolution. Due to this multigrid structure, the algorithm produces a low energy prediction error and a robust motion field close to the true motion in the scene. Furthermore, the computation complexity is greatly reduced. Introducing a locally varying grid size allows to improve the motion vectors accuracy on moving edges and to reduce the overhead information in uniform areas. Therefore, the locally adaptive multigrid block matching motion estimation outperforms the full-search technique in terms of motion vectors accuracy and smoothness, amount of overhead information, coding performances, visual quality of the reconstructed sequences, and computational complexity. In order to avoid the block artifacts related to the block matching techniques, a VQ-based segmentation of the motion field is proposed. Blocks which contain several objects moving in different directions are segmented by means of VQ and a different motion vector is assigned to each of the resulting regions. The method improves motion compensated prediction along moving edges, resulting in higher coding performances and enhanced visual quality. In a further stage, an entropy criterion is introduced to control the motion estimation procedure. By evaluating the transmission cost of both the prediction error and the overhead motion information, it achieves an optimization of the motion estimation and compensation. More precisely, it leads to the optimal trade-off on the motion estimation complexity given an allotted bandwidth. This method is applied in both the locally adaptive multigrid block matching technique and the VQ-based segmentation of the motion field. Finally, a generic video coding system is presented. It supports a wide range of applications and is suitable for multimedia services. Simulation results show good coding performances and high visual quality.
---
paper_title: Entropy criterion for optimal bit allocation between motion and prediction error information

paper_content:

Motion estimation and compensation techniques are widely used in video coding. This paper addresses the problem of the trade-off between the motion and the prediction error information. Under some realistic hypotheses, the transmission cost of these two components can be estimated. Therefore, we obtain a criterion which controls the motion estimation process in order to optimize its performance. As a particular application, this criterion is applied to the split procedure of an adaptive multigrid block matching technique. Simulation results are presented, showing the significant improvements due to the method.
---
paper_title: An iterative image registration technique with an application to stereo vision

paper_content:

Image registration finds a variety of applications in computer vision. Unfortunately, traditional image registration techniques tend to be costly. We present a new image registration technique that makes use of the spatial intensity gradient of the images to find a good match using a type of Newton-Raphson iteration. Our technique is taster because it examines far fewer potential matches between the images than existing techniques Furthermore, this registration technique can be generalized to handle rotation, scaling and shearing. We show how our technique can be adapted tor use in a stereo vision system.
---
paper_title: Motion-compensated television coding: Part I

paper_content:

We present methods of estimating displacements of moving objects from one frame to the next in a television scene and using such displacements for frame-to-frame prediction. Displacement is estimated by a recursive algorithm which seeks to minimize a functional of the prediction error. Several simplifications of the algorithm are presented which make it attractive for hardware implementation. Performance of the algorithm is evaluated by computer simulations on two sequences of moving images containing various amounts and types of motion. In both cases, the use of displacement-based (or motion-compensated) prediction results in bit rates that are 22 to 50 percent lower than those obtained by simple “frame-difference” prediction, which is used commonly in the interframe coders.
---
paper_title: Advances in picture coding

paper_content:

This paper presents a review of the advances in digital coding of video signals during the last four years. Displacement estimation algorithms for coding applications are compared first and the relationship between the algorithms is pointed out. The developments in predictive and transform coding are described and discussed with view to broadcast television and video-conferencing applications. One chapter summarizes the first promising results of motion adaptive frame interpolation. Some problems to be solved in the future are pointed out in the conclusions.
---
paper_title: Displacement Measurement and Its Application in Interframe Image Coding

paper_content:

A new technique for estimating interframe displacement of small blocks with minimum mean square error is presented. An efficient algorithm for searching the direction of displacement has been described. The results of applying the technique to two sets of images are presented which show 8-10 dB improvement in interframe variance reduction due to motion compensation. The motion compensation is applied for analysis and design of a hybrid coding scheme and the results show a factor of two gain at low bit rates.
---
paper_title: Motion segmentation and qualitative dynamic scene analysis from an image sequence

paper_content:

This article deals with analysis of the dynamic content of a scene from an image sequence irrespective of the static or dynamic nature of the camera. The tasks involved can be the detection of moving objects in a scene observed by a mobile camera, or the identification of the movements of some relevant components of the scene relatively to the camera. This problem basically requires a motion-based segmentation step. We present a motion-based segmentation method relying on 2-D affine motion models and a statistical regularization approach which ensures stable motion-based partitions. This can be done without the explicit estimation of optic flow fields. Besides these partitions are linked in time. Therefore, the motion interpretation process can be performed on more than two successive frames. The ability to follow a given coherently moving region within an interval of several images of the sequence makes the interpretation process more robust and more comprehensive. Identification of the kinematic components of the scene is induced from an intermediate layer accomplishing a generic qualitative motion labeling. No 3-D measurements are required. Results obtained on several real-image sequences corresponding to complex outdoor situations are reported.
---
paper_title: An iterative image registration technique with an application to stereo vision

paper_content:

Image registration finds a variety of applications in computer vision. Unfortunately, traditional image registration techniques tend to be costly. We present a new image registration technique that makes use of the spatial intensity gradient of the images to find a good match using a type of Newton-Raphson iteration. Our technique is taster because it examines far fewer potential matches between the images than existing techniques Furthermore, this registration technique can be generalized to handle rotation, scaling and shearing. We show how our technique can be adapted tor use in a stereo vision system.
---
paper_title: Hierarchical model-based motion estimation

paper_content:

This paper describes a hierarchical estimation framework for the computation of diverse representations of motion information. The key features of the resulting framework (or family of algorithms) are a global model that constrains the overall structure of the motion estimated, a local model that is used in the estimation process, and a coarse-fine refinement strategy. Four specific motion models: affine flow, planar surface flow, rigid body motion, and general optical flow, are described along with their application to specific examples.
---
paper_title: Motion-compensated television coding: Part I

paper_content:

We present methods of estimating displacements of moving objects from one frame to the next in a television scene and using such displacements for frame-to-frame prediction. Displacement is estimated by a recursive algorithm which seeks to minimize a functional of the prediction error. Several simplifications of the algorithm are presented which make it attractive for hardware implementation. Performance of the algorithm is evaluated by computer simulations on two sequences of moving images containing various amounts and types of motion. In both cases, the use of displacement-based (or motion-compensated) prediction results in bit rates that are 22 to 50 percent lower than those obtained by simple “frame-difference” prediction, which is used commonly in the interframe coders.
---
paper_title: Advances in picture coding

paper_content:

This paper presents a review of the advances in digital coding of video signals during the last four years. Displacement estimation algorithms for coding applications are compared first and the relationship between the algorithms is pointed out. The developments in predictive and transform coding are described and discussed with view to broadcast television and video-conferencing applications. One chapter summarizes the first promising results of motion adaptive frame interpolation. Some problems to be solved in the future are pointed out in the conclusions.
---
paper_title: Displacement Measurement and Its Application in Interframe Image Coding

paper_content:

A new technique for estimating interframe displacement of small blocks with minimum mean square error is presented. An efficient algorithm for searching the direction of displacement has been described. The results of applying the technique to two sets of images are presented which show 8-10 dB improvement in interframe variance reduction due to motion compensation. The motion compensation is applied for analysis and design of a hybrid coding scheme and the results show a factor of two gain at low bit rates.
---
paper_title: Image segmentation based on object oriented mapping parameter estimation

paper_content:

Abstract A hierarchically structured segmentation algorithmis presented, which is based on the hypothesis, that an area to be segmented is defined by a set of uniform motion and position parameters denoted as mapping parameters. Here, eight parameters are used, which can describe any arbitrary three-dimensional motion of planar rigid objects. In a first step, a change detector initializes the segmentation distinguishing between temporally changed and unchanged regionsof two successive fields. Each changed image region is interpreted as one object. The motion and position of each object is described by one set of mapping parameters. Based on the mapping parameters and the temporally preceeding field, a reconstruction of the temporally subsequent field can be achieved. In the next step of hierarchy, those regions of the image, which are not correctly described in their mappings are again detected by a change detector and treated according to the changed parts of the first step of hierarchy. Experimental results confirm, that the presented segmentation technique separates moving objects from uncovered and covered image regions, detects moving objects in front of moving objects and tracks their motion.
---
paper_title: Object-oriented motion estimation and segmentation in image sequences

paper_content:

Abstract This contribution presents a method for segmenting video scenes hierarchically into several differently moving objects and subobjects. To this end, both contour and texture information from the single images and information from successive images is used to split up a scene into various objects. Furthermore, each of these objects is characterized by a transform h ( x,T ) with a parameter vector T which implicitely describes the surface shape and the three-dimensional motion of the objects in the scene. In order to estimate T of these transforms, an efficient algorithm is introduced. Thus, we obtain an object-oriented segmentation and a prediction of the image contents from one image to the next, which can be used in low bit-rate image coding.
---
paper_title: Object-oriented analysis-synthesis coding based on moving two-dimensional objects

paper_content:

Abstract An object-oriented analysis-synthesis coder is presented which encodes arbitrarily shaped objects instead of rectangular blocks. The objects are described by three parameter sets defining their motion, shape and colour. Throughout this contribution, the colour parameters denote the luminance and chrominance values of the object surface. The parameter sets of each object are obtained by image analysis based on source models of moving 2D-objects and coded by an object-dependent parameter coding. Using the coded parameter sets an image can be reconstructed by model-based image synthesis. In order to cut down the generated bit-rate of the parameter coding, the colour updating of an object is suppressed if the modelling of the object by the source model is sufficiently exact, i.e., if only a relatively small colour update information would be needed for an errorless image synthesis. Omitting colour update information, small position errors of objects denoted as geometrical distortions are allowed for image synthesis instead of quantization error distortions. Tolerating geometrical distortions, the image area to be updated by colour coding can be decreased to 4% of the image size without introducing annoying distortions. As motion and shape parameters can efficiently be coded, about 1 bit per pel remains for colour updating in a 64 kbit/s coder compared to about 0.1 bit per pel in the standard reference coder (RM8) of the CCITT. Experimental results concerning the efficient coding of motion and shape parameters are given and discussed. The coding of the colour information will be dealt with in further research.
---
paper_title: Motion and region overlapping estimation for segmentation-based video coding

paper_content:

In object-based video coding systems, the scenes are described in terms of three dimensional objects, which can be coded as textures and contours. However, in order to achieve high compression ratios, the redundancy in the temporal dimension must be exploited using motion compensation. In this context, motion compensation can take advantage of the description of the scene as three dimensional regions. In this paper we present a motion estimation method which finds, in a fast and computationally simple manner, the affine parameters for every region of the scene. These parameters correspond to the motion of the texture. An ordering between regions is established in order to have the right compensation of contours. >
---
paper_title: An iterative image registration technique with an application to stereo vision

paper_content:

Image registration finds a variety of applications in computer vision. Unfortunately, traditional image registration techniques tend to be costly. We present a new image registration technique that makes use of the spatial intensity gradient of the images to find a good match using a type of Newton-Raphson iteration. Our technique is taster because it examines far fewer potential matches between the images than existing techniques Furthermore, this registration technique can be generalized to handle rotation, scaling and shearing. We show how our technique can be adapted tor use in a stereo vision system.
---
paper_title: Motion-compensated television coding: Part I

paper_content:

We present methods of estimating displacements of moving objects from one frame to the next in a television scene and using such displacements for frame-to-frame prediction. Displacement is estimated by a recursive algorithm which seeks to minimize a functional of the prediction error. Several simplifications of the algorithm are presented which make it attractive for hardware implementation. Performance of the algorithm is evaluated by computer simulations on two sequences of moving images containing various amounts and types of motion. In both cases, the use of displacement-based (or motion-compensated) prediction results in bit rates that are 22 to 50 percent lower than those obtained by simple “frame-difference” prediction, which is used commonly in the interframe coders.
---
paper_title: Applying mid-level vision techniques for video data compression and manipulation

paper_content:

Most image coding systems rely on signal processing concepts such as transforms, VQ, and motion compensation. In order to achieve significantly lower bit rates, it will be necessary to devise encoding schemes that involve mid-level and high-level computer vision. Model-based systems have been described, but these are usually restricted to some special class of images such as head-and-shoulders sequences. We propose to use mid-level vision concepts to achieve a decomposition that can be applied to a wider domain of image material. In particular, we describe a coding scheme based on a set of overlapping layers. The layers, which are ordered in depth and move over one another, are composited in a manner similar to traditional “cel” animation. The decompos ition (the vision problem) is challenging, but we have attained promising results on simple sequences. Once the decomposition has been achieved, the synthesis is straightforward.
---
paper_title: Object-oriented analysis-synthesis coding of moving images

paper_content:

Abstract An object-oriented analysis-synthesis coder is presented which encodes objects instead of blocks of N × N picture elements. The objects are described by three parameter sets defining the motion, shape and colour of an object. The parameter sets are obtained by image analysis based on source models of either moving 2D-objects or moving 3D-objects. Known coding techniques are used to encode the parameter sets. An object-depending parameter coding allows to introduce geometrical distortions instead of quantization errors. Using the transmitted parameter sets an image can be reconstructed by model-based image synthesis. Experimental results achieved with a first implementation of the coder are given and are discussed.
---
paper_title: Advances in picture coding

paper_content:

This paper presents a review of the advances in digital coding of video signals during the last four years. Displacement estimation algorithms for coding applications are compared first and the relationship between the algorithms is pointed out. The developments in predictive and transform coding are described and discussed with view to broadcast television and video-conferencing applications. One chapter summarizes the first promising results of motion adaptive frame interpolation. Some problems to be solved in the future are pointed out in the conclusions.
---
paper_title: Displacement Measurement and Its Application in Interframe Image Coding

paper_content:

A new technique for estimating interframe displacement of small blocks with minimum mean square error is presented. An efficient algorithm for searching the direction of displacement has been described. The results of applying the technique to two sets of images are presented which show 8-10 dB improvement in interframe variance reduction due to motion compensation. The motion compensation is applied for analysis and design of a hybrid coding scheme and the results show a factor of two gain at low bit rates.
---
paper_title: Multilevel Relaxation in Low-Level Computer Vision

paper_content:

Variational (cost minimization) and local constraint approaches are generally applicable to problems in low-level vision (e.g., computation of intrinsic images). Iterative relaxation algorithms are “natural” choices for implementation because they can be executed on highly parallel and locally connected processors. They may, however, require a very large number of iterations to attain convergence. Multilevel relaxation techniques converge much faster and are well suited to processing in cones or pyramids. These techniques are applied to the problem of computing optic flow from dynamic images.
---
paper_title: On the computation of motion from sequences of images-A review

paper_content:

Recent developments are reviewed in the computation of motion and structure of objects in a scene from a sequence of images. Two distinct paradigms are highlighted: (i) the feature-based approach and (ii) the optical-flow-based approach. The comparative merits/demerits of these approaches are discussed. The current status of research in these areas is reviewed and future research directions are indicated. >
---
paper_title: Performance of optical flow techniques

paper_content:

The performance of six optical flow techniques is compared, emphasizing measurement accuracy. The most accurate methods are found to be the local differential approaches, where nu is computed explicitly in terms of a locally constant or linear model. Techniques using global smoothness constraints appear to produce visually attractive flow fields, but in general seem to be accurate enough for qualitative use only and insufficient as precursors to the computations of egomotion and 3D structures. It is found that some form of confidence measure/threshold is crucial for all techniques in order to separate the inaccurate from the accurate. Drawbacks of the six techniques are discussed. >
---
paper_title: Multiple bit-rate video compression via progressive motion field coding

paper_content:

In most motion compensated video coding schemes, the compression factor deteriorates very rapidly as the signal to noise ratio (SNR) of the decoded data stream is increased. In this research, we propose an alternative approach to block based motion compensation in which both a dense motion vector field and the compensation residual are coded at different resolutions. The new approach offers several advantages over some of the well known compression techniques such as the MPEG. First, since the signal is coded at different resolutions, a low resolution signal can be extracted from the data stream without decoding the fine resolution signal. This scalable feature offers real time decoding by a wide range of different receivers with limited computational capabilities and fast forward preview at a full frame rate. Second, for moderately low SNR range, we obtain much better compression than is possible with the conventional techniques.© (1994) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Motion Analysis and Image Sequence Processing

paper_content:

Preface. 1. Hierarchical Model-Based Motion Estimation P. Anandan, J.R. Bergen, K.J. Hanna, R. Hingorani. 2. An Estimation Theoretic Perspective on Image Processing and the Calculation of Optical Flow T.M. Chin, M.R. Luettgen, W.C. Karl, A.S. Willsky. 3. Estimation of 2-D Motion Fields from Image Sequences with Application to Motion-Compensated Processing J. Konrad, E. Dubois. 4. Edge-Based 3-D Camera Motion Estimation with Application to Video Coding E. Zakhor, F. Lari. 5. Motion Compensation: Visual Aspects, Accuracy, and Fundamental Limits B. Girod. 6. Motion Field Estimators and their Application to Image Interpolation S. Tubaro, F. Rocca. 7. Subsampling of Digital Image Sequences using Motion Information R.A.F. Belfor, R.L. Lagendijk, J. Biemond. 8. Image Sequence Coding using Motion-Compensated Subband Decomposition A. Nicoulin, M. Mattavelli, W. Li, A. Basso, A. Popat, M. Kunt. 9. Vector Quantization for Video Data Compression R.M. Mersereau, M.J.T. Smith, C.S. Kim, F. Kossentini, K.K. Truong. 10. Model-Based Image Sequence Coding M. Buck, N. Diehl. 11. Human Facial Motion Analysis and Synthesis with Applications to Model-Based Coding K. Aizawa, C.s. Choi, H. Harashima, T.S. Huang. 12. Motion Compensated Spatiotemporal Kalman Filtering J.W. Woods, J. Kim. 13. Multiframe Wiener Restoration of Image Sequences M.K. Ozkan, M.I. Sezan, A.T. Erdem, A.M. Tekalp. 14. 3-D Median Structures for Image Sequence Filtering and Coding T. Viero, Y. Neuvo. 15. Video Compression for Digital ATV Systems J.G. Apostolopoulos, J.S. Lim. Index.
---
paper_title: An iterative image registration technique with an application to stereo vision

paper_content:

Image registration finds a variety of applications in computer vision. Unfortunately, traditional image registration techniques tend to be costly. We present a new image registration technique that makes use of the spatial intensity gradient of the images to find a good match using a type of Newton-Raphson iteration. Our technique is taster because it examines far fewer potential matches between the images than existing techniques Furthermore, this registration technique can be generalized to handle rotation, scaling and shearing. We show how our technique can be adapted tor use in a stereo vision system.
---
paper_title: Investigations of multigrid algorithms for the estimation of optical flow fieldsin image sequences

paper_content:

Abstract Optical flow fields are useful to describe the motion of objects relative to the observer of a scene. Smoothness requirements facilitate the estimation of optical flow fields even for areas with constant or only linearly sloping gray value distributions. Horn and Schunck (Artif. Intell. 17, 1981, 185–203) formulated the estimation of optical flow fields as a minimization problem. In order to avoid problems with the general smoothness constraint of Horn and Schunck (op. cit.), Nagel (in Proceedings, IJCAI, Karlsruhe, Aug. 1983, pp. 945–951) developed the “oriented smoothness constraint.” Here, a modified formulation of this “oriented smoothness constraint” will be compared to an earlier one. The differences between these formulations will be discussed analytically. Starting with an iterative solution approach for the system of nonlinear partial differential equations resulting from the “oriented smoothness constraint,” the iterative solution approach could be improved significantly using multigrid methods. Results obtained from experiments with real world image sequences will be presented.
---
paper_title: Motion-compensated television coding: Part I

paper_content:

We present methods of estimating displacements of moving objects from one frame to the next in a television scene and using such displacements for frame-to-frame prediction. Displacement is estimated by a recursive algorithm which seeks to minimize a functional of the prediction error. Several simplifications of the algorithm are presented which make it attractive for hardware implementation. Performance of the algorithm is evaluated by computer simulations on two sequences of moving images containing various amounts and types of motion. In both cases, the use of displacement-based (or motion-compensated) prediction results in bit rates that are 22 to 50 percent lower than those obtained by simple “frame-difference” prediction, which is used commonly in the interframe coders.
---
paper_title: Advances in picture coding

paper_content:

This paper presents a review of the advances in digital coding of video signals during the last four years. Displacement estimation algorithms for coding applications are compared first and the relationship between the algorithms is pointed out. The developments in predictive and transform coding are described and discussed with view to broadcast television and video-conferencing applications. One chapter summarizes the first promising results of motion adaptive frame interpolation. Some problems to be solved in the future are pointed out in the conclusions.
---
paper_title: Displacement Measurement and Its Application in Interframe Image Coding

paper_content:

A new technique for estimating interframe displacement of small blocks with minimum mean square error is presented. An efficient algorithm for searching the direction of displacement has been described. The results of applying the technique to two sets of images are presented which show 8-10 dB improvement in interframe variance reduction due to motion compensation. The motion compensation is applied for analysis and design of a hybrid coding scheme and the results show a factor of two gain at low bit rates.
---
paper_title: Motion-compensated television coding: Part I

paper_content:

We present methods of estimating displacements of moving objects from one frame to the next in a television scene and using such displacements for frame-to-frame prediction. Displacement is estimated by a recursive algorithm which seeks to minimize a functional of the prediction error. Several simplifications of the algorithm are presented which make it attractive for hardware implementation. Performance of the algorithm is evaluated by computer simulations on two sequences of moving images containing various amounts and types of motion. In both cases, the use of displacement-based (or motion-compensated) prediction results in bit rates that are 22 to 50 percent lower than those obtained by simple “frame-difference” prediction, which is used commonly in the interframe coders.
---
paper_title: New pel-recursive motion estimation algorithms based on novel interpolation kernels

paper_content:

Pel-recursive motion estimation algorithms are an attractive alternative to block-matching motion compensation algorithms for video coding because (a) they do not require that motion information by transmitted over the channel, and (b) they allow the reconstruction of continuously varying motion fields. Unfortunately, the high computational complexity of these algorithms and their difficulty in tracking varying motion fields, discontinuities in motion fields, and noisy image sequences have led most current video coding algorithms to use block- based rather than pel-recursive approaches to motion estimation and compensation. This paper presents a new, discrete formulation of pel-recursive motion estimates which allows more flexibility in trading off computational complexity for prediction accuracy, and which permits the design of hybrid motion-estimation algorithms sharing characteristics of both pel-recursive approaches and block-matching approaches. Using the discrete formulation, we defined three novel approaches to motion estimation, one in the form of a conventional pel-recursive algorithm and two incorporating various amounts of block-based motion information from the encoder. We present simulations comparing their performance with both standard pel- recursive and block-matching motion estimation algorithms, demonstrating significant improvements in prediction accuracy.© (1992) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Advances in picture coding

paper_content:

This paper presents a review of the advances in digital coding of video signals during the last four years. Displacement estimation algorithms for coding applications are compared first and the relationship between the algorithms is pointed out. The developments in predictive and transform coding are described and discussed with view to broadcast television and video-conferencing applications. One chapter summarizes the first promising results of motion adaptive frame interpolation. Some problems to be solved in the future are pointed out in the conclusions.
---
paper_title: New fast algorithms for the estimation of block motion vectors

paper_content:

Two algorithms for block motion estimation that produce performance similar to that of exhaustive search but with computation reduced by a factor of 8 or 16 are presented. The algorithms are based on motion-field and pixel subsampling. A subsampled motion field is first determined by estimating the motion vectors for a fraction of the blocks. The motion vectors for these blocks are determined by using only a fraction of the pixels at any searched location and by alternating the pixel subsampling patterns with the searched locations. The subsampled motion field is then interpolated so that a motion vector is determined for each block of pixels. The algorithms are more robust than previously proposed fast algorithms and both can easily be combined with a hierarchical search strategy. One of the algorithms is fully compatible with MPEG-I. >
---
paper_title: Multigrid block matching motion estimation for generic video coding

paper_content:

Motion estimation and compensation techniques have shown their efficiency to reduce temporal redundancies in video coding applications. Motion estimation analyzes the movement of objects in the scene. The resulting motion information allows to improve interframe predictive coding. This work deals with the study of motion estimation algorithms in the framework of image sequence coding. The desired features of a motion estimation algorithm in order to achieve high performances are the following. First, the algorithm provides an accurate motion compensated prediction. Second, it requires a low overhead information. Third, it leads to a smooth motion field close to the true motion in the scene. However, it is straightforward that more precise motion vectors need a higher overhead information, and vice versa. Consequently, a trade-off on the motion estimation complexity has to be found in order to optimally balance these two conflicting features. The motion estimation algorithm developed in this dissertation takes into account the above remarks. Block matching techniques are a promising approach for motion estimation in image sequence coding. In this framework, the classical full-search algorithm is widely used due to its simplicity and ease of hardware implementation. Nevertheless, it suffers serious drawbacks. In particular, it performs poorly on moving edges and introduces block artifacts in the motion compensated frame. Furthermore, it tends to produce noisy motion fields. Finally, it requires a high computational complexity. In this study, we aim at overcoming the above drawbacks in order to fulfill all the above desired features of a motion estimation algorithm. In this dissertation, we propose a locally adaptive multigrid block matching motion estimation technique. The motion vectors are iteratively refined on a set of grids with different resolution. Due to this multigrid structure, the algorithm produces a low energy prediction error and a robust motion field close to the true motion in the scene. Furthermore, the computation complexity is greatly reduced. Introducing a locally varying grid size allows to improve the motion vectors accuracy on moving edges and to reduce the overhead information in uniform areas. Therefore, the locally adaptive multigrid block matching motion estimation outperforms the full-search technique in terms of motion vectors accuracy and smoothness, amount of overhead information, coding performances, visual quality of the reconstructed sequences, and computational complexity. In order to avoid the block artifacts related to the block matching techniques, a VQ-based segmentation of the motion field is proposed. Blocks which contain several objects moving in different directions are segmented by means of VQ and a different motion vector is assigned to each of the resulting regions. The method improves motion compensated prediction along moving edges, resulting in higher coding performances and enhanced visual quality. In a further stage, an entropy criterion is introduced to control the motion estimation procedure. By evaluating the transmission cost of both the prediction error and the overhead motion information, it achieves an optimization of the motion estimation and compensation. More precisely, it leads to the optimal trade-off on the motion estimation complexity given an allotted bandwidth. This method is applied in both the locally adaptive multigrid block matching technique and the VQ-based segmentation of the motion field. Finally, a generic video coding system is presented. It supports a wide range of applications and is suitable for multimedia services. Simulation results show good coding performances and high visual quality.
---
paper_title: Affine models for image matching and motion detection

paper_content:

A model is developed for detecting the displacement field in spatiotemporal image sequences. It allows for affine shape deformations of corresponding spatial regions and for affine transformations of the image intensity range. The model includes the block matching method as a special case. A least-squares algorithm is used to find the model parameters. It is experimentally demonstrated that the affine matching model performs better than other standard approaches. The resulting 2-D motion estimates are then used by a 3-D affine model and a least-squares algorithm that recover 3-D rigid body motion and depth from two perspective views. >
---
paper_title: Advances in picture coding

paper_content:

This paper presents a review of the advances in digital coding of video signals during the last four years. Displacement estimation algorithms for coding applications are compared first and the relationship between the algorithms is pointed out. The developments in predictive and transform coding are described and discussed with view to broadcast television and video-conferencing applications. One chapter summarizes the first promising results of motion adaptive frame interpolation. Some problems to be solved in the future are pointed out in the conclusions.
---
paper_title: Displacement Measurement and Its Application in Interframe Image Coding

paper_content:

A new technique for estimating interframe displacement of small blocks with minimum mean square error is presented. An efficient algorithm for searching the direction of displacement has been described. The results of applying the technique to two sets of images are presented which show 8-10 dB improvement in interframe variance reduction due to motion compensation. The motion compensation is applied for analysis and design of a hybrid coding scheme and the results show a factor of two gain at low bit rates.
---
paper_title: Motion-compensated television coding: Part I

paper_content:

We present methods of estimating displacements of moving objects from one frame to the next in a television scene and using such displacements for frame-to-frame prediction. Displacement is estimated by a recursive algorithm which seeks to minimize a functional of the prediction error. Several simplifications of the algorithm are presented which make it attractive for hardware implementation. Performance of the algorithm is evaluated by computer simulations on two sequences of moving images containing various amounts and types of motion. In both cases, the use of displacement-based (or motion-compensated) prediction results in bit rates that are 22 to 50 percent lower than those obtained by simple “frame-difference” prediction, which is used commonly in the interframe coders.
---
paper_title: An overlapped block motion compensation for high quality motion picture coding

paper_content:

An overlapped block motion compensation scheme, which is especially suitable for hybrid coding schemes combine with overlapped transforms, is described. Motion compensation is achieved using enlarged and overlapped blocks. When motion estimation is executed, a window function operates on the prediction error signals. The power of the resulting signal is calculated and used for motion vector evaluation. When motion-compensated prediction is executed, the same window function operates on the prediction signals. The total prediction signal is generated by summing up all the block signals obtained. With this scheme, prediction signals without blocking edges are obtained. The mean square error (MSE) of the prediction error signal is reduced about 19%, and FFT analysis results show that the coefficient power in the frequency domain is concentrated in the lower frequency part. This indicates higher coding efficiency for the overlapped transforms, and for conventional block based transforms as well. >
---
paper_title: Predictive motion field segmentation for image sequence coding

paper_content:

A method is described for improving block-based motion-compensation techniques by segmenting blocks into regions corresponding to objects moving with distinct velocities. The method uses standard block motion-estimation techniques and assumes that each distinct velocity within a block is approximated by one of the motion estimates in a neighborhood of that block. A multiresolution approach to segmenting each block is taken. It is based on a Markov random-field model of the segmentation field and incorporates additional constraints which reflect an assumption that the blocks are small relative to objects in the scene. In order to avoid transmitting the segmentation, the method computes the segmentation of previous frames at the receiver and transmitter and predicts the current segmentation from past ones. Experimental results show that the method eliminates most artifacts due to block motion compensation at edges of moving objects and achieves 30-50% reductions in displaced frame-difference energy in frames where reliable motion estimates are available. >
---
paper_title: Multigrid block matching motion estimation for generic video coding

paper_content:

Motion estimation and compensation techniques have shown their efficiency to reduce temporal redundancies in video coding applications. Motion estimation analyzes the movement of objects in the scene. The resulting motion information allows to improve interframe predictive coding. This work deals with the study of motion estimation algorithms in the framework of image sequence coding. The desired features of a motion estimation algorithm in order to achieve high performances are the following. First, the algorithm provides an accurate motion compensated prediction. Second, it requires a low overhead information. Third, it leads to a smooth motion field close to the true motion in the scene. However, it is straightforward that more precise motion vectors need a higher overhead information, and vice versa. Consequently, a trade-off on the motion estimation complexity has to be found in order to optimally balance these two conflicting features. The motion estimation algorithm developed in this dissertation takes into account the above remarks. Block matching techniques are a promising approach for motion estimation in image sequence coding. In this framework, the classical full-search algorithm is widely used due to its simplicity and ease of hardware implementation. Nevertheless, it suffers serious drawbacks. In particular, it performs poorly on moving edges and introduces block artifacts in the motion compensated frame. Furthermore, it tends to produce noisy motion fields. Finally, it requires a high computational complexity. In this study, we aim at overcoming the above drawbacks in order to fulfill all the above desired features of a motion estimation algorithm. In this dissertation, we propose a locally adaptive multigrid block matching motion estimation technique. The motion vectors are iteratively refined on a set of grids with different resolution. Due to this multigrid structure, the algorithm produces a low energy prediction error and a robust motion field close to the true motion in the scene. Furthermore, the computation complexity is greatly reduced. Introducing a locally varying grid size allows to improve the motion vectors accuracy on moving edges and to reduce the overhead information in uniform areas. Therefore, the locally adaptive multigrid block matching motion estimation outperforms the full-search technique in terms of motion vectors accuracy and smoothness, amount of overhead information, coding performances, visual quality of the reconstructed sequences, and computational complexity. In order to avoid the block artifacts related to the block matching techniques, a VQ-based segmentation of the motion field is proposed. Blocks which contain several objects moving in different directions are segmented by means of VQ and a different motion vector is assigned to each of the resulting regions. The method improves motion compensated prediction along moving edges, resulting in higher coding performances and enhanced visual quality. In a further stage, an entropy criterion is introduced to control the motion estimation procedure. By evaluating the transmission cost of both the prediction error and the overhead motion information, it achieves an optimization of the motion estimation and compensation. More precisely, it leads to the optimal trade-off on the motion estimation complexity given an allotted bandwidth. This method is applied in both the locally adaptive multigrid block matching technique and the VQ-based segmentation of the motion field. Finally, a generic video coding system is presented. It supports a wide range of applications and is suitable for multimedia services. Simulation results show good coding performances and high visual quality.
---
paper_title: Iterative motion estimation method using triangular patches for motion compensation

paper_content:

In order to overcome the drawback of the conventional block-based motion compensation, a new triangle-based method which utilizes triangular patches instead of blocks has recently been proposed. Compared to conventional methods which represent the motion of scene objects by translational displacements of blocks, the new method can cope with a wider range of motions since is allows for rotation and deformation of the triangular patches. In the block- based motion compensation, a simple local minimization algorithm (i.e., block matching) is applied to obtain the displacement vector of each block. However, it is inappropriate to apply this algorithm in the triangle-based motion compensation because of the complicated linkage between the deformation of the triangular patches and the displacement of the grid points (vertices of triangles). Consequently, the primary issue is to find an optimal way to estimate motion of the grid points. In this paper, we present a new motion estimation algorithm called hexagonal matching which iteratively refines the estimated displacement vectors. Simulation results show that the motion estimation algorithm produces less prediction error than the previously proposed triangle-based method or the block-based method. We also propose another algorithm with similar function but less computational complexity.© (1991) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Variable size block matching motion compensation with applications to video coding

paper_content:

Indexing term: Codes and decoding: Algorithms Abstract: In block matching type motion com- pensation schemes, the image is divided into blocks of the same size. For each block a search is conducted in the previous frame to locate the best correspondence. For the scheme to succeed an implicit assumption has to be made that the motion within each block is uniform, an assump- tion which may not necessarily be correct, and as a result the quality of the prediction suffers. In the paper, a new motion compensation scheme based on block matching is presented, where the size for each block is variable. The proposed algorithm adaptively divides the image into blocks of vari- able size to meet the assumption on uniform motion for all blocks. The scheme has been suc- cessfully applied to simple interframe video coding. It is shown that the proposed algorithm can be extended to form the basis of a complete and efficient codec with low complexity. The possibility of the combination of the scheme with novel hybrid coding techniques to form sophisti- cated systems with low bit-rate performance, that compare favourably with other existing schemes, is also demonstrated.
---
paper_title: Vector Quantization-Based Motion Field Segmentation under the Entropy Criterion

paper_content:

Abstract This paper proposes a segmentation of block-based motion fields under the constraint of the entropy criterion. The segmentation is performed by a vector quantization technique which associates the segmentation pattern to an element of a codebook. Optimization of the bit rate as a trade-off between motion and segmentation on the one hand and prediction error on the other hand is addressed. An estimation of the amount of information to code the displaced frame difference is derived, making it possible to control the segmentation process. Simulation results show the efficiency of the segmentation method combined with the entropy criterion in a video coding scheme.
---
paper_title: Entropy criterion for optimal bit allocation between motion and prediction error information

paper_content:

Motion estimation and compensation techniques are widely used in video coding. This paper addresses the problem of the trade-off between the motion and the prediction error information. Under some realistic hypotheses, the transmission cost of these two components can be estimated. Therefore, we obtain a criterion which controls the motion estimation process in order to optimize its performance. As a particular application, this criterion is applied to the split procedure of an adaptive multigrid block matching technique. Simulation results are presented, showing the significant improvements due to the method.
---
paper_title: Multigrid block-matching motion estimation with an adaptive local mesh refinement

paper_content:

Keywords: LTS1 Reference LTS-CONF-1992-005 Record created on 2006-10-27, modified on 2016-08-08
---
paper_title: A motion field segmentation to improve moving edges reconstruction in video coding

paper_content:

Block matching motion estimation techniques have shown their efficiency to reduce the temporal redundancy for video coding. However, they tend to introduce annoying block artifacts in the displaced frame difference due to their block-based model. In this paper, we propose a motion field refinement technique in order to overcome these artifacts. The method relies on vector quantization. The patterns to segment the motion field are derived by the LBG algorithm, the training being performed on segmented patterns obtained from natural images. Simulation results show a significant improvement due to the proposed method, in particular moving edges are much better motion compensated and the visual quality is greatly enhanced. >
---
paper_title: Multigrid block matching motion estimation for generic video coding

paper_content:

Motion estimation and compensation techniques have shown their efficiency to reduce temporal redundancies in video coding applications. Motion estimation analyzes the movement of objects in the scene. The resulting motion information allows to improve interframe predictive coding. This work deals with the study of motion estimation algorithms in the framework of image sequence coding. The desired features of a motion estimation algorithm in order to achieve high performances are the following. First, the algorithm provides an accurate motion compensated prediction. Second, it requires a low overhead information. Third, it leads to a smooth motion field close to the true motion in the scene. However, it is straightforward that more precise motion vectors need a higher overhead information, and vice versa. Consequently, a trade-off on the motion estimation complexity has to be found in order to optimally balance these two conflicting features. The motion estimation algorithm developed in this dissertation takes into account the above remarks. Block matching techniques are a promising approach for motion estimation in image sequence coding. In this framework, the classical full-search algorithm is widely used due to its simplicity and ease of hardware implementation. Nevertheless, it suffers serious drawbacks. In particular, it performs poorly on moving edges and introduces block artifacts in the motion compensated frame. Furthermore, it tends to produce noisy motion fields. Finally, it requires a high computational complexity. In this study, we aim at overcoming the above drawbacks in order to fulfill all the above desired features of a motion estimation algorithm. In this dissertation, we propose a locally adaptive multigrid block matching motion estimation technique. The motion vectors are iteratively refined on a set of grids with different resolution. Due to this multigrid structure, the algorithm produces a low energy prediction error and a robust motion field close to the true motion in the scene. Furthermore, the computation complexity is greatly reduced. Introducing a locally varying grid size allows to improve the motion vectors accuracy on moving edges and to reduce the overhead information in uniform areas. Therefore, the locally adaptive multigrid block matching motion estimation outperforms the full-search technique in terms of motion vectors accuracy and smoothness, amount of overhead information, coding performances, visual quality of the reconstructed sequences, and computational complexity. In order to avoid the block artifacts related to the block matching techniques, a VQ-based segmentation of the motion field is proposed. Blocks which contain several objects moving in different directions are segmented by means of VQ and a different motion vector is assigned to each of the resulting regions. The method improves motion compensated prediction along moving edges, resulting in higher coding performances and enhanced visual quality. In a further stage, an entropy criterion is introduced to control the motion estimation procedure. By evaluating the transmission cost of both the prediction error and the overhead motion information, it achieves an optimization of the motion estimation and compensation. More precisely, it leads to the optimal trade-off on the motion estimation complexity given an allotted bandwidth. This method is applied in both the locally adaptive multigrid block matching technique and the VQ-based segmentation of the motion field. Finally, a generic video coding system is presented. It supports a wide range of applications and is suitable for multimedia services. Simulation results show good coding performances and high visual quality.
---
paper_title: Variable size block matching motion compensation with applications to video coding

paper_content:

Indexing term: Codes and decoding: Algorithms Abstract: In block matching type motion com- pensation schemes, the image is divided into blocks of the same size. For each block a search is conducted in the previous frame to locate the best correspondence. For the scheme to succeed an implicit assumption has to be made that the motion within each block is uniform, an assump- tion which may not necessarily be correct, and as a result the quality of the prediction suffers. In the paper, a new motion compensation scheme based on block matching is presented, where the size for each block is variable. The proposed algorithm adaptively divides the image into blocks of vari- able size to meet the assumption on uniform motion for all blocks. The scheme has been suc- cessfully applied to simple interframe video coding. It is shown that the proposed algorithm can be extended to form the basis of a complete and efficient codec with low complexity. The possibility of the combination of the scheme with novel hybrid coding techniques to form sophisti- cated systems with low bit-rate performance, that compare favourably with other existing schemes, is also demonstrated.
---
paper_title: Compact motion representation based on global features for semantic image sequence coding

paper_content:

For dynamic scene analysis, numerous studied developed derivation methods of qualitative motion features from a dense apparent velocity vector field (optical flow). However, this qualitative information cannot be used for image sequence reconstruction because no explicit reconstruction criterion is introduced within the feature identification process itself. This study proposes a new algorithmic approach which tries to solve the crucial trade-off between a small amount of motion parameters--viewed as assistance data in a motion compensated interpolation scheme for image sequence coding--and high quality of reconstruction. This approach could be described as a tentative step towards semantic coding scheme using global--and thus compact-- motion labels which characterize a restricted class of 3-D physical motions even if no 3-D measurements are required. This paper is structured as follows: after a brief introduction where the general framework is described, we present a hierarchy of affine models for motion field representation and the explicit derivation of global motion features associated with a simplified version of a linear model. The identification procedure, essentially based on minimization techniques using steepest descent methods, is shown. After all these initial requirements, we introduce the more efficient and new algorithmic step; it is concerned with the use of a deterministic relaxation scheme to smooth the motion vector field and improve the accuracy of the motion estimator, especially within regions where large magnitudes of motion are located. We also introduce a temporal linking operator which appears quite natural in the framework of iterative estimation methods where initial values are required. Finally, results on real image sequences are given; performances are expressed in terms of convergence speed, reconstruction quality, compactness of the motion representation and qualitative or quantitative efficiency of the motion estimation scheme.© (1991) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Multigrid block-matching motion estimation with an adaptive local mesh refinement

paper_content:

Keywords: LTS1 Reference LTS-CONF-1992-005 Record created on 2006-10-27, modified on 2016-08-08
---
paper_title: Tree-structured scene adaptive coder

paper_content:

A new type of scene adaptive coder has been developed. It involves a quadtree mean decomposition of the motion-compensated frame-to-frame difference signal followed by a scalar quantization of the local means. As a fundamental property, the new coding algorithm treats the displacement estimation problem and the quadtree construction problem as a unit. The displacement vector and the related quadtree are jointly optimized in order to minimize the direct frame-to-frame update information rate (in bits), which turns up as a new and more adequate cost function in displacement estimation. This guarantees the highest possible data compression ratio at a given quality threshold. Excellent results have been obtained for coding of color image sequences at a rate of 64 kb/s. The quadtree concept entails a much lower computational complexity compared to the conventional motion-compensated transform coder while achieving a subjective image quality that is as good or better than that of the traditional transform-based counterpart. >
---
paper_title: Multigrid block matching motion estimation for generic video coding

paper_content:

Motion estimation and compensation techniques have shown their efficiency to reduce temporal redundancies in video coding applications. Motion estimation analyzes the movement of objects in the scene. The resulting motion information allows to improve interframe predictive coding. This work deals with the study of motion estimation algorithms in the framework of image sequence coding. The desired features of a motion estimation algorithm in order to achieve high performances are the following. First, the algorithm provides an accurate motion compensated prediction. Second, it requires a low overhead information. Third, it leads to a smooth motion field close to the true motion in the scene. However, it is straightforward that more precise motion vectors need a higher overhead information, and vice versa. Consequently, a trade-off on the motion estimation complexity has to be found in order to optimally balance these two conflicting features. The motion estimation algorithm developed in this dissertation takes into account the above remarks. Block matching techniques are a promising approach for motion estimation in image sequence coding. In this framework, the classical full-search algorithm is widely used due to its simplicity and ease of hardware implementation. Nevertheless, it suffers serious drawbacks. In particular, it performs poorly on moving edges and introduces block artifacts in the motion compensated frame. Furthermore, it tends to produce noisy motion fields. Finally, it requires a high computational complexity. In this study, we aim at overcoming the above drawbacks in order to fulfill all the above desired features of a motion estimation algorithm. In this dissertation, we propose a locally adaptive multigrid block matching motion estimation technique. The motion vectors are iteratively refined on a set of grids with different resolution. Due to this multigrid structure, the algorithm produces a low energy prediction error and a robust motion field close to the true motion in the scene. Furthermore, the computation complexity is greatly reduced. Introducing a locally varying grid size allows to improve the motion vectors accuracy on moving edges and to reduce the overhead information in uniform areas. Therefore, the locally adaptive multigrid block matching motion estimation outperforms the full-search technique in terms of motion vectors accuracy and smoothness, amount of overhead information, coding performances, visual quality of the reconstructed sequences, and computational complexity. In order to avoid the block artifacts related to the block matching techniques, a VQ-based segmentation of the motion field is proposed. Blocks which contain several objects moving in different directions are segmented by means of VQ and a different motion vector is assigned to each of the resulting regions. The method improves motion compensated prediction along moving edges, resulting in higher coding performances and enhanced visual quality. In a further stage, an entropy criterion is introduced to control the motion estimation procedure. By evaluating the transmission cost of both the prediction error and the overhead motion information, it achieves an optimization of the motion estimation and compensation. More precisely, it leads to the optimal trade-off on the motion estimation complexity given an allotted bandwidth. This method is applied in both the locally adaptive multigrid block matching technique and the VQ-based segmentation of the motion field. Finally, a generic video coding system is presented. It supports a wide range of applications and is suitable for multimedia services. Simulation results show good coding performances and high visual quality.
---
paper_title: Entropy criterion for optimal bit allocation between motion and prediction error information

paper_content:

Motion estimation and compensation techniques are widely used in video coding. This paper addresses the problem of the trade-off between the motion and the prediction error information. Under some realistic hypotheses, the transmission cost of these two components can be estimated. Therefore, we obtain a criterion which controls the motion estimation process in order to optimize its performance. As a particular application, this criterion is applied to the split procedure of an adaptive multigrid block matching technique. Simulation results are presented, showing the significant improvements due to the method.
---
paper_title: A High Quality Videophone Coder Using Hierarchical Motion Estimation And Structure Coding Of The Prediction Error

paper_content:

For the realization of a videophone for use with the ISDN at data rates as low as 64 kbit/s there is a demand for powerful coding algorithms. In this paper new concepts for motion estimation and residual error coding, which are the most important parts of an hybrid codec, are introduced: Fast motion estimation algorithms to be found in many approaches, assume a monotonous behavior of the matching criterion with respect to the displacement. This assumption does not hold in reality. Therefore a hierarchical block matching motion estimation algorithm is introduced, which approaches the performance of a full search at a fraction of the computational cost. The algorithm combines a full search with a vector quantization as a first stage. In a second stage a full search with sub-pel accuracy is performed only over the small region corresponding to the codeword of the first stage. By motion compensated prediction the image of the residual error is obtained. A statistical analysis of this image shows that methods for data compression of natural images, e.g. transform coding, are not suitable for coding of the prediction error images. Instead, a structure coding scheme is proposed: The special signal statistics of the error signal allows a coarse quantization in the original domain. Dominant block types are coded using a quadtree. The scheme offers the additional advantage of easy implementation, unlike the DCT. Computer simulations show an improved picture quality even for strong scene movement without the usual artifacts, like blocking for example.
---
paper_title: Multigrid block matching motion estimation for generic video coding

paper_content:

Motion estimation and compensation techniques have shown their efficiency to reduce temporal redundancies in video coding applications. Motion estimation analyzes the movement of objects in the scene. The resulting motion information allows to improve interframe predictive coding. This work deals with the study of motion estimation algorithms in the framework of image sequence coding. The desired features of a motion estimation algorithm in order to achieve high performances are the following. First, the algorithm provides an accurate motion compensated prediction. Second, it requires a low overhead information. Third, it leads to a smooth motion field close to the true motion in the scene. However, it is straightforward that more precise motion vectors need a higher overhead information, and vice versa. Consequently, a trade-off on the motion estimation complexity has to be found in order to optimally balance these two conflicting features. The motion estimation algorithm developed in this dissertation takes into account the above remarks. Block matching techniques are a promising approach for motion estimation in image sequence coding. In this framework, the classical full-search algorithm is widely used due to its simplicity and ease of hardware implementation. Nevertheless, it suffers serious drawbacks. In particular, it performs poorly on moving edges and introduces block artifacts in the motion compensated frame. Furthermore, it tends to produce noisy motion fields. Finally, it requires a high computational complexity. In this study, we aim at overcoming the above drawbacks in order to fulfill all the above desired features of a motion estimation algorithm. In this dissertation, we propose a locally adaptive multigrid block matching motion estimation technique. The motion vectors are iteratively refined on a set of grids with different resolution. Due to this multigrid structure, the algorithm produces a low energy prediction error and a robust motion field close to the true motion in the scene. Furthermore, the computation complexity is greatly reduced. Introducing a locally varying grid size allows to improve the motion vectors accuracy on moving edges and to reduce the overhead information in uniform areas. Therefore, the locally adaptive multigrid block matching motion estimation outperforms the full-search technique in terms of motion vectors accuracy and smoothness, amount of overhead information, coding performances, visual quality of the reconstructed sequences, and computational complexity. In order to avoid the block artifacts related to the block matching techniques, a VQ-based segmentation of the motion field is proposed. Blocks which contain several objects moving in different directions are segmented by means of VQ and a different motion vector is assigned to each of the resulting regions. The method improves motion compensated prediction along moving edges, resulting in higher coding performances and enhanced visual quality. In a further stage, an entropy criterion is introduced to control the motion estimation procedure. By evaluating the transmission cost of both the prediction error and the overhead motion information, it achieves an optimization of the motion estimation and compensation. More precisely, it leads to the optimal trade-off on the motion estimation complexity given an allotted bandwidth. This method is applied in both the locally adaptive multigrid block matching technique and the VQ-based segmentation of the motion field. Finally, a generic video coding system is presented. It supports a wide range of applications and is suitable for multimedia services. Simulation results show good coding performances and high visual quality.
---
paper_title: Arithmetic coding for data compression

paper_content:

The state of the art in data compression is arithmetic coding, not the better-known Huffman method. Arithmetic coding gives greater compression, is faster for adaptive models, and clearly separates the model from the channel encoding.
---

Title: Motion Estimation Techniques for Digital TV: A Review and a New Contribution

Section 1: Introduction
Description 1: Overview of video coding techniques focusing on motion estimation.

Section 2: Characterization of the Motion
Description 2: Clarification of the notion of motion in the context of image sequence processing and differentiation between displacement and velocity.

Section 2.1: Deterministic Versus Probabilistic and Nonparametric Versus Parametric
Description 2.1: Explanation of deterministic vs probabilistic motion models and nonparametric vs parametric approaches in motion estimation.

Section 2.2: Motion Models and Support for the Motion Estimation
Description 2.2: Discussion on various parametric motion models and their applications in motion estimation.

Section 3: Review of Motion Estimation Techniques
Description 3: Detailed review and comparison of classical motion estimation algorithms including gradient techniques, pel-recursive techniques, and block matching techniques.

Section 3.1: Pel-Recursive Techniques
Description 3.1: Overview of pel-recursive motion estimation techniques and their application in image sequence coding.

Section 3.2: Block Matching Techniques
Description 3.2: Examination of block matching algorithms for motion estimation and their advantages and drawbacks in video coding.

Section 3.3: Comparison Between Gradient, Pel-Recursive and Block Matching Motion Estimation Techniques
Description 3.3: Comparative analysis of the performance and efficiency of gradient, pel-recursive, and block matching motion estimation techniques in video coding.

Section 4: Locally Adaptive Multigrid Block Matching Motion Estimation
Description 4: Introduction and detailed explanation of the proposed locally adaptive multigrid block matching algorithm for motion estimation.

Section 4.1: Motion Estimation at Each Level
Description 4.1: Description of the motion estimation process at each multigrid level.

Section 4.2: Segmentation Decision Rule
Description 4.2: Explanation of the criteria and rules used for block segmentation during motion estimation.

Section 4.3: Down-Projection Operator
Description 4.3: Description of the down-projection operator used to map the motion field between different grid levels.

Section 4.4: Simulation Results
Description 4.4: Presentation and discussion of simulation results showcasing the performance of the proposed locally adaptive multigrid block matching algorithm.

Section 5: Conclusion
Description 5: Summarization of the findings and conclusion drawn from the reviewed techniques and the proposed new method.