Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2001-03-30
2004-04-13
Philippe, Gims (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C382S252000, C348S425200
Reexamination Certificate
active
06721362
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to video compression, and more particularly to error detection in corrupted video streams.
When high-quality sound and video were added to personal computers, an explosion in demand occurred for multimedia PC's. Today's wireless devices such as personal digital assistants (PDA's) have very limited graphics abilities and are thus similar to the early PC's. When high-quality video is added to such wireless devices, a demand explosion similar to the one that occurred for multimedia PC's is possible.
Adding video to such wireless devices is challenging in many aspects. Transmission over a wireless link or network can introduce bit errors to the video stream. Large data rates are needed to transmit even simple video, and various compression techniques are needed to squeeze video into limited wireless bandwidth.
Various compression standards have emerged for video stream. One standard that is well-suited for wireless video is the motion-picture-experts group MPEG-4 standard. The MPEG standard breaks each video frame (or video object plane VOP) into macroblocks. Each macroblock has 16×16 pixels, and is itself divided into four 8×8 blocks.
During MPEG compression, searches are made of surrounding pixels in a frame for a similar or identical image to that of each macroblock. When a close match is found, the difference in location of the macroblock in different frames is transmitted as a motion vector. When a motion vector is transmitted, the many pixels in the macroblock do not have to be re-transmitted; thus compression occurs. When the macroblock differ slightly, an error term or difference in pixels in the macroblock can be transmitted along with the motion vector.
FIG. 1
is a flowchart of prior-art MPEG compression of an 8×8 block in a macroblock. Each video frame in a sequence of frames is divided into macroblocks. A search of previous frames is made for the same image in the block or macroblock, and when successful a motion vector is generate for the macroblock, perhaps with an error term of pixel differences. When the search is unsuccessful, and for initial frames in a new image sequence, all pixels in the macroblock are transmitted.
The pixels in one 8×8 block in the macroblock, or the pixel-error terms and motion vector, are sent to the compression engine, or stored in a buffer memory. The compression engine reads these pixels or error terms, step
102
.
A discrete cosine transform (DCT) is executed on the 64 pixels in the block, or on the error terms, step
104
. This generates 8×8 DCT coefficients. The DCT coefficients are then divided by a factor Q_SCALE, step
106
. This is known as quantization, as the results are rounded. Many small DCT coefficients are quantized to zero. These small coefficients represent small error terms or high-frequency image components such as sharp edges. Since many of the less-visibly-relevant high-frequency image components are truncated, compression occurs as less data is used to represent the image of the block.
A variable-length code is then used to encode the quantized DCT coefficients, step
108
. The variable-length code replaces input coefficients with variable-length codewords. More common values of coefficients are encoded with shorter codewords while less frequent coefficient values are coded with longer codewords. Compression occurs since the more common values are coded with fewer bits of codeword than are less common values. The compressed 8×8 block is then output to a buffer memory or the transmitter, step
110
.
FIG. 2
is a flowchart for prior-art MPEG decompression of a block. After de-framing and de-packetization of the bitstream, each macroblock is identified and each 8×8 block within a macroblock is decompressed. An 8×8 block is read from a buffer memory or the incoming bitstream, step
112
. The variable-length code is used to convert the variable-length codewords back to the fixed-length coefficients, step
114
. These coefficients are the quantized DCT coefficients for the 8×8 block.
The quantized DCT coefficients are de-quantized or scaled by the factor Q_SCALE, step
116
. The factor Q_SCALE is multiplied by each quantized DCT coefficients to generate the DCT coefficients. This process is known as de-quantization.
An inverse discrete cosine transform is executed on the DCT coefficients, step
118
, to recover the pixel data. Since the compression was lossy, some differences can exist between the original pixel data and the decompressed pixel data; however, these differences should be minor and not outstandingly visible. The pixel data is either all 64 pixels in the 8×8 block, or the pixel-error terms for the block. The error terms can be used to generate the pixels for the block from a block in a previous frame. The pixels then be stored in a buffer memory or displayed, step
120
.
While MPEG compression and decompression are quite useful, when compressed MPEG video bitstreams are transmitted over a wireless network, errors are introduced into the bitstream. These errors can result in visible image distortions that can be quite noticeable. Detection of these bitstream errors is desirable. However, parity or other error-detection codes are not included in the MPEG standard, so error detection by such traditional methods is not possible. Indeed, adding parity bits would increase the amount of data transmitted in the bitstream, and would thus defeat the purpose of compression.
What is desired is an error detection method for video bitstreams. Error detection that is integrated with MPEG compression and decompression is desirable. Error detection that does not significantly increase the amount of data that is transmitted in the bitstream is desirable.
REFERENCES:
patent: 5111463 (1992-05-01), Zook
patent: 5455629 (1995-10-01), Sun et al.
patent: 5563887 (1996-10-01), Harasaki
patent: 5734755 (1998-03-01), Ramchandran et al.
patent: 5771081 (1998-06-01), Lee
patent: 6029265 (2000-02-01), Itoi et al.
patent: 6031914 (2000-02-01), Tewfik et al.
patent: 6141448 (2000-10-01), Khansari et al.
patent: 6154571 (2000-11-01), Cox et al.
patent: 6170074 (2001-01-01), Kondo et al.
patent: 6404817 (2002-06-01), Saha et al.
patent: 6498809 (2002-12-01), Dean et al.
Fukunaga et al., “MPEG-4 Video Verification Model version 13.3”, ISO/IEC JTC1/SC29/WG11, MPEG99/4960. 10/99, pp. 1-18,75-80,105,115-140,160-193.
Lin Tao
Molloy Stephen
Auvinen Stuart T.
Philippe Gims
RedRock Semiconductor, Ltd.
LandOfFree
Constrained discrete-cosine-transform coefficients for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Constrained discrete-cosine-transform coefficients for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constrained discrete-cosine-transform coefficients for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3251450