Re: Video Compression

Michael Sattler, San Francisco (msattler@jungle.com)
Wed, 21 Sep 1994 01:17:04 -0400


At 17:26 9/20/94, Laha, Subhasis wrote:
>
>I am interested in finding out the algorithms that are used for video
>compression on CU-SEEME. I would appreciate if somebody
>could provide me some details of the compression algorithms
>and the video data-stream.

A while ago (Wed 10 Aug 1994) Tim Dorcey <T.Dorcey@cornell.edu> (Hi Tim!)
posted this description of CU-SeeMe's compression algorithm (which he said
he extracted from a yet earlier posting):

The first step in the CU-SeeMe video encoding, is to represent the
video image using 4 bits/pixel (16 shades of gray). The image is then
subdivided into 8x8 pixel squares, which are treated as independent units.
When a new frame of video is acquired, a square is transmitted if it
differs sufficiently from the version of that square that was most recently
transmitted i.e., if it differs from what the recipients are currently
displaying (assuming no packet loss). The index used to determine how
different a square must be in order to trigger updating is roughly the sum
of the absolute values of all 64 pixel differences in an 8x8 square, with a
multiplicative penalty for differences that occur near each other within
the square. The cut-off value can be adjusted by the "Tolerance" control
under "Compression" controls, and should be set as high as possible without
corrupting the picture too much.
Since CU-SeeMe uses an unreliable ("best-effort") transport mechanism
(UDP), squares are sent on a periodic basis even if they haven't changed,
insuring that a lost update won't corrupt the picture indefinitely. How
often this forced update occurs is controlled by the "Refresh Rate"
control, which specifies the number of frames that will be allowed to pass
before a square is updated.
Once the decision to transmit a square has been made, a locally
developed lossless compression algorithm is applied to each individual
square. The algorithm is designed to exploit spatial reduncancy in the
vertical direction i.e., works well if each row in the square is not too
different from the one above it. Based on informal observations, the
algorithm averages around a %60 compression rate (compressed size is about
60% of the original).
The main objective in designing these algorithms was to be fast enough
for operation on average Macintosh computers. This is achieved by
operating on rows of 8 4-bit pixels as 32-bit words throughout the
algorithms, achieving a degree of parallelism, in effect. Written down in
mathematical terms with respect to individual pixels, the algorithms look
rather goofy, but become appealing when represented in 680x0 assembly
language.
As with any compression algorithm, your mileage will vary depending on
the nature of the data to compress. In the case of CU-SeeMe, the most
important factor is the amount of motion in the video.

> 2) What kind of bandwidth is required for fluid motion?

This is a tough question, because the answer depends so much on the content
of the video, and also on a subjective evaluation of what is "fluid
motion." For an average talking head, I would say around 100 kbits/sec.
At the other extreme, there are 75 kbits in an uncompressed 120 x 160
frame, which would translate to about 45 kbits/frame with the lossless
spatial compression. Then, if you're willing to call 15 frames/sec fluid
motion, and every frame was completely different from the previous frame,
you'd need 675 kbits/sec.
But, really, since the software is free, the best thing to do is try it
out on the sorts of video you have in mind.

> 3) Can you connect directly to another PC via modem and SLIP without
> the reflector software?

As long as you have IP service between 2 machines, you should be able to
connect them without a reflector. You cannot involve more than 2 machines
without a reflector, however.

> 4) Is the source code available? ( nondisclosure statement?)
> If the software is publically funded, why is the source not available?

The source code is not currently available, but will be, once we get it
cleaned up and make some decisions about what usage restrictions should be
imposed. The main reason source is not available is that it is not
finished (for any value of "finished"). Though it's not especially
relevant to this question, it's worth mentioning that much of the code was
developed without public funding.

---------------------------------------------------------------------------
Michael Sattler <msattler@wco.ftp.com>, FTP Software, West Coast Operations
Quality Assurance Manager
WWW = http://www.wco.ftp.com/~msattler/
Don't try to teach a pig to sing; it's a waste of time & it annoys the pig.