NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/comp/compress/3018

Text File | 1992-08-14 | 7.0 KB | 172 lines

Newsgroups: comp.compression
Path: sparky!uunet!gatech!destroyer!caen!nic.umass.edu!noc.near.net!gateway!pictel!garys
From: [e-mail] (Gary Sullivan)
Subject: Re: Comparison: BMA vs. PRA
Message-ID: <[e-mail]>
Organization: PictureTel Corporation
References: <[e-mail]>
Date: Fri, 14 Aug 1992 15:32:17 GMT
Lines: 161

In article <[e-mail]> [e-mail] (Hyung Chul Kim) writes:
>Hi folks,
>
>BMA(Block Matching Algorithm) and PRA(Pel Recursive Algorithm) are
>motion estimation algorithms for motion video compression.
>Anyone knows whether there is any comparison study about them from the point of
>view of speed and compression rate?
>If you have ever studied or have any information about it,
>please let me know.
>

Here is an excerpt from the LaTeX source of my motion compensation article in '91 ICASSP.

Reference: @inproceedings{sullivanCGI91conf,
    author = "G. J. Sullivan and R. L. Baker",
    title = "Motion Compensation for Video Compression using Control Grid Interpolation",
    booktitle = icassp,
    pages = "2713--2716",
    month = may,
    year = 1991}

I have included some lines of the original source that were commented out
(using "%") in the actual paper due to constraints on the length of the
paper, as I think these lines may be helpful in some cases.  However, the
text is not guaranteed to make sense with these lines included.  It is presumed
to make sense without them.

The summary of what is below is this:
(1) PRAs are fairly useless for low rate video compression, since they require
    sequential encoding, not block-oriented methods such as DCT or large-block VQ.
(2) PRAs are more normally more computationally complex than BMAs but can
    produce a better motion vector field estimation under some circumstances.

----------------- Included description below --------------------------
The dominant methods of motion compensation are {\em block matching
algorithms} (BMAs)~[1--3]\nocite{musmann85,rao85,MPEGSM3}.
In a BMA,
the input image is decomposed into a regular
grid of rectangular blocks.  One MV is found for each block, and all pels
in the block are displaced equally.  The chosen MVs
are entropy coded and sent to the receiver.
%The focus of much of the research to date on BMAs consists of
%various methods for efficiently searching for the best MV for each block.
A straightforward but computationally intense way of choosing these MVs is
called {\em full-search}, which consists of measuring the distortion for every
allowable MV value and choosing the best directly.
%Many methods for reducing the
%number of tested vectors have been proposed, each of which by construction
%has performance somewhat below that of full-search.

There are several well-known problems with BMAs.
%The borders of moving objects
%do not normally coincide with the borders of the blocks used for the BMA.
When objects undergoing different types of motion are found in the same block,
the use of the same MV for every pel in the block becomes
inappropriate.  Also, when adjacent blocks use different MVs, they
form a straight-line discontinuity in the prediction image.
Since the human visual system is very sensitive to straight lines, these
errors appear as {\em blocking artifacts}.  Since the motion vectors are
determined independently for each block, the motion vector field
is discontinuous, difficult to compress, and may have little relation to
true object motion.
Further, since each block can
undergo only translational motion, BMAs have difficulty with other types of
motion such as rotation and depth changes.  These problems
demonstrate the need for methods which operate on individual pels, rather
than large blocks.

The next most common class of methods for motion compensation is
{\em pel-recursive algorithms}
(PRAs)~\cite{musmann85}.
These operate on a pel basis and overcome
many of the problems associated with BMAs.
%They produce
%less distortion and have no blocking artifacts.
%In a PRA each individual pel or small block of pels
%has its own motion vector, which is
%calculated by an iterative method.  In their preferred implementation,
%PRAs do not send these motion vectors to the receiver,
%because to do so would require large
%amounts of side information.  Instead, they use
%previously decoded data from the current frame
%to find a MV that is appropriate for the area surrounding
%the next pel to be decoded.
%Since this requires that each pel be decoded individually, it
However, in their preferred implementation, PRAs require that each
pel be decoded sequentially, thus making them
incompatible with block coding methods, such as DCT or VQ.
%PRAs also have high complexity, since they involve an iterative
%optimization procedure for every pel.
%
Several other methods for motion compensation have been proposed.
Predictive segmentation uses a BMA and data
from prior frames to divide a block into regions having differing
MVs~\cite{orchard90}.  This method shows promise, but requires
extra rate to identify the segmentation.
%Also, since segmentation is
%a hard (rather than soft) decision, errors can produce large residuals.
Other methods based on object modeling may be useful in the future, but
have yet to be developed for real-time application to general, complex
scenes typical of videoconferencing or broadcast video.

In this paper, we describe a new class of motion compensation methods based on
control grid interpolation (CGI)~\cite{castle79}.
CGI is a spatial transformation method which can be used to create a smooth
interpolated motion field.
The authors are
unaware of any prior study of CGI in motion compensation.
We show that BMA is a special case of CGI, and
describe a new CGI algorithm that is compatible with nearly any BMA coding
system, yet
produces no blocking artifacts.  It uses the same or less rate
than the corresponding BMA, and has about the same mean-square distortion.
Nearly all of the theory developed for BMA searching and for encoding BMA
motion vector data is easily applied to the CGI system.

Citations:

@article{musmann85,
    author = "H. G. Musmann and P. Pirsch and H-J. Grallert",
    title = "Advances in Picture Coding",
    journal = procieee,
    volume = "73",
    number = 4,
    pages = "523--548",
    month = apr,
    year = 1985}

@article{rao85,
    author = "R. Srinivasan and K. R. Rao",
    title = "Predictive Coding Based on Efficient Motion Estimation",
    journal = ieeetransCOM,
    volume = "COM-33",
    pages = "888-896",
    month = aug,
    year = 1985}

@unpublished{MPEGSM3,
    author = "{MPEG Video Editorial Group}",
    title = "{MPEG} Video Simulation Model Three",
    month = aug,
    note = "Int. Standards Org.",
    year = 1990}

@inproceedings{orchard90,
    author = "M. T. Orchard",
    title = "Predictive Motion Field Segmentation for Image Sequence Coding",
    booktitle = icassp,
    month = apr,
    volume = "4",
    pages = "1977--1980",
    year = 1990}

@book{castle79,
    author = "K. R. Castleman",
    title = "Digital Image Processing",
    address = "Englewood Cliffs, NJ",
    publisher = "Prentice-Hall",
    year = 1979}
---------------------------------
Gary Sullivan  ([e-mail])