Variable length coding

Details Variable length coding Variable length coding

2002-03-22

2004-02-24

Wamsley, Patrick (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from variable length codes

C375S240230, C382S246000

Reexamination Certificate

active

06696993

ABSTRACT:

FIELD OF THE INVENTION
The invention concerns the variable length coding of data symbols. More specifically, the invention relates to a method of variable length coding suitable for application in the coding of digital video.
BACKGROUND OF THE INVENTION
Digital video sequences, like ordinary motion pictures recorded on film, comprise a sequence of still images, the illusion of motion being created by displaying the images one after the other at a relatively fast rate, typically 15 to 30 frames per second. Because of the relatively fast display rate, images in consecutive frames tend to be quite similar and thus contain a considerable amount of redundant information. For example, a typical scene may comprise some stationary elements, such as background scenery, and some moving areas, which may take many different forms, for example the face of a newsreader, moving traffic and so on. Alternatively, the camera recording the scene may itself be moving, in which case all elements of the image have the same kind of motion. In many cases, this means that the overall change between one video frame and the next is rather small.
Each frame of an uncompressed digital video sequence comprises an array of image pixels. For example, in a commonly used digital video format, known as the Quarter Common Interchange Format (QCIF), a frame comprises an array of 176×144 pixels, in which case each frame has 25,344 pixels. In turn, each pixel is represented by a certain number of bits, which carry information about the luminance and/or colour content of the region of the image corresponding to the pixel. Commonly, a so-called YUV colour model is used to represent the luminance and chrominance content of the image. The luminance, or Y, component represents the intensity (brightness) of the image, while the colour content of the image is represented by two chrominance or colour difference components, labelled U and V.
Colour models based on a luminance/chrominance representation of image content provide certain advantages compared with colour models that are based on a representation involving primary colours (that is Red, Green and Blue, RGB). The human visual system is more sensitive to intensity variations than it is to colour variations and YUV colour models exploit this property by using a lower spatial resolution for the chrominance components (U, V) than for the luminance component (Y). In this way, the amount of information needed to code the colour information in an image can be reduced with an acceptable reduction in image quality.
The lower spatial resolution of the chrominance components is usually attained by sub-sampling. Typically, each frame of a video sequence is divided into so-called ‘macroblocks’, which comprise luminance (Y) information and associated chrominance (U, V) information that is spatially sub-sampled.
FIG. 3
illustrates one way in which macroblocks can be formed.
FIG. 3
a
shows a frame of a video sequence represented using a YUV colour model, each component having the same spatial resolution. Macroblocks are formed by representing a region of 16×16 image pixels in the original image (
FIG. 3
b
) as four blocks of luminance information, each luminance block comprising an 8×8 array of luminance (Y) values and two spatially corresponding chrominance components (U and V) which are sub-sampled by a factor of two in the x and y directions to yield corresponding arrays of 8×8 chrominance (U, V) values (see
FIG. 3
c
). According to certain video coding recommendations, such as International Telecommunications Union (ITU-T) recommendation H.26L, the block size used within the macroblocks can be other than 8×8, for example 4×8 or 4×4. (See ITU-T Q.15/SG16 “H.26L Test Model Long Term Number 5 (TML-5) draft 0”, Doc. Q15-K-59, October 2000, Section 2.3).
A QCIF image comprises 11×9 macroblocks. If the luminance blocks and chrominance blocks are represented with 8 bit resolution (that is by numbers in the range 0 to 255), the total number of bits required per macroblock is (16×16×8)+2×(8×8×8)=3072 bits (assuming that the two chrominance components are divided into 8×8 blocks). The number of bits needed to represent a video frame in QCIF format is thus 99×3072=304,128 bits. This means that the amount of data required to transmit/record/display an uncompressed video sequence in QCIF format, represented using a YUV colour model, at a rate of 30 frames per second, is more than 9 Mbps (million bits per second). This is an extremely high data rate and is impractical for use in video recording, transmission and display applications because of the very large storage capacity, transmission channel capacity and hardware performance required.
If video data is to be transmitted over a fixed line network such as an ISDN (Integrated Services Digital Network) or a conventional PSTN (Public Switched Telephone Network), the available data transmission bandwidth is typically of the order of 64 kbits/s. In mobile video telephony, where transmission takes place at least in part over a radio communications link, the available bandwidth can be as low as 20 kbits/s. This means that a significant reduction in the amount of information used to represent video data must be achieved in order to enable transmission of digital video sequences over low bandwidth communication networks. For this reason, video compression techniques have been developed which reduce the amount of information transmitted, while retaining an acceptable image quality.
Video compression methods are based on reducing the redundant information in video sequences. The redundancy in video sequences can be categorised into spatial, temporal and spectral redundancy. ‘Spatial redundancy’ is the term used to describe the correlation (similarity) between neighbouring pixels within a frame. The term ‘temporal redundancy’ expresses the fact that objects appearing in one frame of a sequence are likely to appear in subsequent frames, while ‘spectral redundancy’ refers to the correlation between different colour components of the same image.
Sufficiently efficient compression cannot usually be achieved by simply reducing the various forms of redundancy in a given sequence of images. Thus, most current video encoders also reduce the quality of those parts of the video sequence that are subjectively the least important. In addition, the redundancy of the compressed video bit-stream itself is reduced by means of efficient loss-less encoding. Generally, this is achieved using a technique known as entropy coding, which will be described in greater detail later in the text.
There is often a significant amount of spatial redundancy between the pixels that make up each frame of a digital video sequence. In other words, the value of any pixel within a frame of the sequence is substantially the same as the value of other pixels in its immediate vicinity. Typically, video coding systems reduce spatial redundancy using a technique known as ‘block-based transform coding’, in which a mathematical transformation is applied to the pixels of an image, on a macroblock-by-macroblock basis. Transform coding translates the image data from a representation comprising pixel values to a form comprising a set of coefficient values, each of which is a weighting factor (multiplier) for a basis function of the transform in question. By using certain mathematical transformations, such as the two-dimensional Discrete Cosine Transform (DCT), which transforms the image data from the pixel value domain to a spatial frequency representation, the spatial redundancy within a frame of a digital video sequence can be significantly reduced, thereby producing a more compact representation of the image data.
Frames of a video sequence which are compressed using block-based transform coding, without reference to any other frame within the sequence, are referred to as INTRA-coded or I-frames. Additionally, and where possible, blocks of INTRA-coded frames are predicted from previ

Affiliated with

Also associated with

Rating

Variable length coding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Variable length coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable length coding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3277182