From: haddadi@sipi.usc.edu (Navid Haddadi)
Newsgroups: comp.compression
Subject: Re: Motion Compensation?
Date: 18 Dec 1992 02:39:40 -0800
Organization: University of Southern California, Los Angeles, CA
NNTP-Posting-Host: sipi.usc.edu

In article <1992Dec18.003748.17601@cs.wayne.edu> bhh@isis.cs.wayne.edu (Bhaskar Holur) writes:
>Well, you did not mention the method of motion compensation used
>in MPEG Video Compression Standard. Although the MPEG does not specify
>any particular method for it, the main idea is block-based
>motion compensation.  The method is to search for  a best matching
>block in the reference frame within a predetermined search area (depending
>on the speed and type of motion in the frames) around the point
>corresponding to the target block in the current frame. The cost function
>or the matching function can be any one of : Mean Absolute Difference,
>MSE, or a correlation function, etc. There are fast search procedures
>to idendify the match in the search area, like the 3-step procedure.
>
>Note: for block based motion compensation, the frame is divided into
>non-overlapping square blocks of size 16x16 or application specific
>size.
>
>--Bascar
>bhh@cs.wayne.edu

True. However, the concept of block matching (not the computation)
is so tivial that there is not much to be said about it 
(although, some variations such as Anandon's work is by no means trivial).
If the size of image is 512x512 then it can be subsampled 16:1 to
create 32x32 images from which an optical flow can be computed in a fraction
of time required to perform block matching at 512x512 resolution. If one
is willing to tollerate a higher computational cost, then multiresolution
computation of optical flow based on Gradient Constraint Equation
(with appropriate constraints) provides a very reliable measure of motion
(even for 16x16 blocks) which minimizes prediction error (one-step in case
of two images) in a non-trivial way. Block matching methods whick seek
to minimize a measure of local error (such as sum-of-squared differences),
on the other hand, are too "greedy" in their search for an optimal solution.
In fact, block matching methods are only one way of computing the optical flow
(after all B.M. methods are also based on preservation of intensity). 
Token matching, Contour based matching (Hildreth, Butox, Waxman), 
spatio-temporal-frequency (Heeger) and phase (Fleet and Jepson) methods 
as well as the gradient based methods are among the more sophisticated
(both computationally and theoretically) methods of
estimation motion (This is of course my opinion). Correlation techniques
(such as Anandon's pyramid skim) can be made competitive at higher
computational cost when the first and second curvatures of the images are 
used to resolve conflicts in match probability. However, The true power of 
motionfield is that it computes motion of each pixel. If we find an 
efficient method of coding the resulting flow field, then we would almost 
certainly achieve much better compression than is possible with the protocols
of the MPGE's fixed block structure. We need a protocol in which different
block sizes can be used in the same frame. Here at SIPI (Signal and 
Image Processing Inst. at USC), we are currently working on such problems. 

Navid,
haddadi@sipi.usc.edu
Newsgroups: comp.compression