Method and apparatus for vector quantization for real-time playback on low cost personal computers

• US 5,467,413 A
• Filed: 05/20/1993
• Issued: 11/14/1995
• Est. Priority Date: 05/20/1993
• Status: Expired due to Term

• Current Assignee: Autodesk, Inc.
• Original Assignee: Radius, Inc. (Washington) (DXC Technology Company)
• Inventors: Barrett, Peter T.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Johns, Andrew W.
• Application Number:
  US08/064,843
• Time in Patent Office: 908 Days
• Field of Search: 382/56, 382/236, 382/239, 382/253, 358/432, 358/433, 348/399, 348/403, 348/404, 348/405, 348/420, 348/422, 348/438
• US Class Current: 382/236
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H04N 11/042 Codec means
• CPC Class Codes: H04N 19/80 Details of filtering operations specially adapted for video compression, e.g. for pixel interpolation H04N19/635, H04N19/86 take precedence
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 21/4143 embedded in a Personal Computer [PC]
• CPC Class Codes: H04N 5/781 on disks or drums
• CPC Class Codes: H04N 5/85 on discs or drums
• CPC Class Codes: H04N 9/8042 involving data reduction

Abstract

A vector quantization method and apparatus which processes signal vectors constructed from digital image data (such as a digital video stream). The digital video stream is treated as a sequence of images, each represented by a rectangular array of pixels. The pixels are processed in blocks (typically 4×4 blocks) of two types, known as smooth blocks and detail blocks. The detail blocks contain the original image pixels, while the smooth blocks contain pixels from a subsampled version of the image. The pixels in the blocks are formatted into image vectors, again in two types. Each type of image vector is separately compressed using a vector quantization coder and a separate code book for each type. Smooth image vectors are compressed using a smooth code book and detail image vectors compressed using a detail code book. The compressed data stream is specially constructed, as a stream of code words for smooth and detail image vectors, updates to the code books, and mask bits that select the type of each code word, to facilitate real time decompression on low cost microprocessors. The coding operation can include interframe coding in which the mask bits are additionally coded so that, in addition to selecting the type of each code word, they also indicate that a block does not change from the last frame and the corresponding code word has been omitted. The inventive compression technique results in a high quality video playback with a high compression ratio (typically about one bit per pixel). This allows high quality compressed video to be played back from conventional CD-ROMs or hard disks, and to be transmitted over communications channels with data rates of 1.5 Mbit/sec.

Claims

1. A vector quantization method for compressing image data, wherein the image data comprises frames and each of the frames comprises blocks of pixels, said method including the steps of:

(a) classifying the blocks into at least two types according to level of detail, said types including at least a first type and a second type, wherein the frames of the image data include a keyframe followed by an interframe, each of the blocks of the first type consists of four image vectors, and each of the image vectors comprises a number of YUV values;

(b) performing vector quantization encoding on blocks of the first type using a first dedicated code book, to generate first code words;

(c) performing vector quantization encoding on blocks of the second type using a second dedicated code book, to generate second code words;

generating a smooth frame for the keyframe, wherein the smooth frame is a reduced resolution version of the keyframe, wherein the smooth frame consists of smooth blocks, and wherein each of the smooth blocks comprises an image vector comprising said number of YUV values;

performing step (b) on each of the blocks in which variation among the pixels exceeds a selected threshold, to generate four first code words; and

for each of the blocks in which variation among the pixels does not exceed the selected threshold, performing step (c) on a corresponding one of the smooth blocks to generate one of the second code words.

2. The method of claim 1, including the steps of:

generating a smooth frame for the interframe, wherein the smooth frame is a reduced resolution version of the interframe, wherein the smooth frame consists of smooth blocks, and wherein each of the smooth blocks comprises an image vector comprising said number of YUV values;

comparing the blocks of the interframe to corresponding blocks of the keyframe;

for each of the blocks of the interframe matching a corresponding block of the keyframe, setting a skip bit rather than performing vector quantization encoding thereon;

performing step (b) on each of the blocks of the interframe which does not match a corresponding block of the keyframe, and in which variation among the pixels exceeds a selected threshold, to generate four first code words; and

for each of the blocks of the interframe which does not match a corresponding block of the keyframe, and in which variation among the pixels does not exceed the selected threshold, performing step (c) on a corresponding one of the smooth blocks to generate one of the second code words.

3. The method of claim 1, wherein said each of the image vectors consists of four Y values, a U value, and a V value.