2. Compression and Digital Video
A great deal of research has gone into image and video compression and indeed
it is quite difficult to invent something new in this field. A diagram
showing the many compression techniques are shown in figure 2.1. The assumption
is that the input is always a PCM digitised signal in colour components. The
output of the compression process is a bitstream. Lets consider each
technique briefly :
Figure 2.1 - Compression Techniques
Simple Compression Techniques
Various techniques exist, including :
- Truncation
Reduces data by reducing the number of bits per pixel. This
suffers from contouring (resolution loss) but has the advantage that processing
is simple.
- Colour Lookup Table (CLUT)
Pixel values represent an index into a table
of colours. The processing for this is non-trivial.
- Run length coding
Blocks of repeated pixels are replaced with a pixel
value and a count. This works well on images with blocks of single colours
and can achieve a high compression ratio. However it not effective if images
contain no repetitive areas.
Interpolative Techniques
This technique aims to send a subset of the pixels and use interpolation
to reconstruct the intervening pixels. This technique is particularly useful
for motion sequences, as certain frames are compressed by still compression
; the frames between these are compressed by doing an interpolation between
the other frames and sending only the data needed to correct the
interpolation.
Predictive Techniques
This relies on the fact that there is nearly always some redundancy between
frames in a sequence. There are two common methods :
- DPCM (Differential Pulse Code Modulation)
This operates at the pixel
level and sends only the difference between successive pixels. Since there
is likely to be very little difference between adjacent pixels we can
encode the value into smaller data widths. This technique suffers from
slope-overload which causes smearing at high contrast edges in an image.
- ADPCM (Adaptive DPCM)
This tries to reduces the slope-overload by
using smaller steps for the difference values.
Transform Coding Techniques
A transform is a process that converts data into an alternate form which is
more convenient for some particular purpose. Transforms are ordinarily designed
to be reversible. Useful transforms typically operate on large blocks of data
and perform some complex calculations. In general transform coding becomes
more useful with larger blocks. The Discrete Cosine Transform (DCT) is
especially important for video compression.
The DCT
The DCT is performed on a block of horizontally and vertically adjacent pixels
(typically an 8 by 8 block of pixels). The outputs represent amplitudes of two
dimensional spatial frequency components. These are called DCT coefficients.
The coefficient for zero spatial frequency is called the DC coefficient
and it is the average value of all the pixels in the block. The rest of
the coefficients represent progressively higher horizontal and vertical
spatial frequencies in the block.
Since adjacent pixel values tend to be similar or vary slowly from one to
another, the DCT processing provides opportunity for compression by
forcing most of the energy into lower spatial frequency components.
In most cases, many of the higher frequency coefficients will have zero or
new-zero values and therefore can be ignored.
The decoder performs the reverse process, but due to the transcendental
nature of the DCT the reverse process can only be approximated and
hence some loss takes place. The trick is to use some cunning methods of
keeping coefficients so that the loss is minimally visible.
Statistical Coding (or Entropy Coding)
This takes advantage of the statistical distribution of the pixel values.
Some data values can occur more frequently then others and therefore we can
set up a coding technique that use less bits for these values. One
widely used form of this coding is Huffman encoding. This technique has the
overhead that a syntax has to be pre-defined or sent for the decoder to work.
Motion Compensation
Consider the case of a video sequence where nothing is moving in the scene.
Each frame of the video should be exactly the same as the previous one.
In a digital system, it should be clear that, we only need to send one
frame and a repetition count. Consider now, a dog walking across the same
scene. The scene is the same throughout the sequence, but only the dog
moves. If we could find a way of only sending the motion of the dog, then
we can save a lot of storage space. This is an oversimplified case of motion
video, but it reveals two of the most difficult problems in motion
compensation :
- How can we tell if an image is stationery ?
- How do we extract the part of the image that moves ?
We can try to answer these questions by some form of comparison between
adjacent frames of the sequence. We can assume that the current and previous
frames are available for the comparison. The simple comparison technique is
too simple and is like a frame-by-frame DPCM. This has a few problems :
- The pixel compare will rarely produce a zero difference, due to quantisation
noise in the system (this can be overcome with a threshold).
- Images are rarely stationery.
Therefore, more sophisticated techniques are needed. This problem is usually
addressed by dividing the image into blocks. Each block is examined for
motion. If a block is found to contain no motion, a code is sent to the
decompresser to leave the block the same as the previous one.
If enough processing power is available, still more powerful techniques may
be applied. For examples, blocks may be compared to previous block to see
if there is a difference between the two. Only this difference (motion
vector) is sent.
Need for Compression
Compression is needed to simply reduce the amount of space that video would
otherwise take to store. There are many factors to consider when choosing
a compression technique :
- Real-Time / Non-Real-Time
This refers to capturing, compressing,
decompressing and playing back all in real time with no delays. The requirement
is to have sufficient frame rate (frames per second)to make sure that there is no jerky motion.
- Symmetrical / Asymmetrical
Symmetrical implies capturing, storing, and
playback at the same rate. Asymmetrical uses more time to compress and hence
may have an advantage for playback speed.
- Compression Ratio
The compression ratio relates the numerical
representation of the original video in comparison to the compressed video.
Generally the higher the compression ratio the poorer the video quality.
- Lossless / Lossy
The loss factor determines whether there is a loss of
quality between the original image and the image after it has been compressed
and played back (decompressed). Again this is affected by the amount of
compression.
- Inter-frame / Intra-frame
Inter-frame compresses each frame of the
sequence as a discrete picture. Intra-frame is a more powerful method
which uses a predictive technique.
Compared to traditional analogue video, digital video provides the following
advantages :
- There is no copy from copy loss
- Picture does not get fuzzy
- Signal-to-Noise ratio goes down slowly
- Editing, storage and retrieval is simpler, quicker and cheaper
When dealing with digital video a number of points have to be kept in mind :
- Frame Rate
How many frames are displayed per second, also the method
of frame display : progressive - each line of video is shown one
after the other; interlaced - odd lines (fields) are shown then
the even fields.
- Colour Resolution
This refers to the number of colours
displayed at any one time. There are also various colour formats :
RGB and YUV are two common formats. Colour depth is the maximum number
of colours displayed.
- Spatial Resolution
This deals with the size of the picture.
- Image quality
Does the final sequence match the requirements of the application.
Video 'Standards'
With so many techniques, you would expect many companies to be
competing for a position in the market place. This is in-fact the case
and there are many competing technologies.
The above discussion of techniques and decisions introduced the building
blocks available for creating algorithms. An actual algorithm consists
of one or more techniques which operate on the raw digitised images to create
a compressed bitstream. The number of algorithms possible is nearly
infinite. However, practical applications (see below) require that all users
who wish to interchange compressed video must use exactly the same algorithm
choice. Further sophisticated algorithms will benefit from the development
of special hardware. All this expresses the need for standards to allow
the orderly growth of markets which utilise video compression technology.
Driven by these needs, there has been a strong effort to develop
international standards for motion video compression algorithms, underway
for several years in the International Standards Organisation (ISO) and
the International Electrotechnical Commission (IEC). It is the
Motion Pictures Expert Group (MPEG) which considers algorithms for
motion video compression.
3. MPEG : The Standard
The MPEG committee began life in late 1988 by
the hand of Leonardo Chairigloione and Hiroshi Yasuda with the immediate goal of
standardising video and audio for compact discs. A meeting between the
International Standards Organisation (ISO) and the International Electrotechnical
Commission (IEC) in 1992 resulted in a standard for audio and video coding,
known as MPEG-1. MPEG-2 became a bone fide standard in 1994 after a five day
meeting of ISO and ITC in Singapore. The technology behind MPEG-1 and 2
are inherently the same.
The MPEG system consists of two layers :
- System Layer (timing information to synchronise video and audio)
- Compression Layer (includes audio and video streams)
Only the MPEG-1 standard will be described in detail here.
Objectives
The MPEG standard is designed to be generic, meaning that it will support the
needs of many applications. The objectives include :
- Delivery of acceptable video quality at compressed data rates in excess of
1.0 Mbits/s
- Support both symmetric and asymmetric compression/decompression applications.
- Random access playback should be possible
- Fast-play and fast reverse in addition to normal playback should be supported
- Audio video synchronisation should be maintained.
- Data errors should not be catastrophic
- The processing requirements should not preclude the development of low-cost
semiconductor based implementation which may encode in real time.
Figure 3.1 - The MPEG data hierarchy
Architecture
The MPEG standard is primarily a bitstream specification, although it also specifies
a typical decoding process to assist in interpreting the bitstream specification.
This approach supports data interchange, but does not restrict innovation in the
means for creating or decoding that bitstream. The bitstream specification
is based on a data hierarchy, shown in figure 2. The data hierarchy is
pretty self-explaining and is useful for the following reasons :
- Groups of pictures allow random access into a sequence
- Slices aid error recovery, in that if one slice contains an error then
it can be skipped.
The bitstream architecture is based on a sequence of pictures, each of
which contains the data needed to create a single display-able image. There
are four different kinds of picture, depending on how each picture is to
be decoded :
- I-Picture
These are intra-coded, which means they are coded
independent of any other pictures.
- P-Picture
These are predicted pictures and are coded using motion
compensation from previous I or P-pictures.
- B-Picture
These are interpolated pictures, which are coded by
interpolating between a previous and a future I or P-picture. This process
is called bi-directional prediction.
- D-Picture
These pictures are a special format and are used
to implement sequence searches.
The above description of MPEG has been very terse and a lot of detail has
had to be left out. However MPEG is not the only compression technique on
the market, there are many algorithms available. The next section presents a
brief overview of the competitors to MPEG and looks at the advantages and
disadvantages for each method.
4. Contendors in the Compression Market
There are several popular digital video formats (or CODECS) in use
today.
- Apple QuickTime
This was a milestone for digital video. This is a software only playback scheme
that requires no special hardware. This format supports scalability in
that some quality loss can be sacrificed for the sake of synchronisation.
- Intel Indeo
Shortly after Apples' QuickTime was released, Intel introduced Indeo. This
also allows scalability. This format is well supported by all the major
software vendors in the world and hardware version exist.
- Radius Cinepak
This is another software only CODEC and again is well supported.
When choosing a particular format, it is worthwhile bearing in mind the following
points :
- Is is easy to convert the source format (eg. Video tape)
- Will the format handle the source content
- What is the quality of the encoding system
With this in mind, the following table outlines the advantages and disadvantages
of each digital format.
