Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1997-05-30
2002-01-15
Le, Vu (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C348S699000
Reexamination Certificate
active
06339616
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to the field of data compression and decompression. More specifically, the invention relates to compression and decompression of still image and/or motion video data.
2. Background Information
A frame of still or motion video typically comprises a number of frame elements referred to as pixels (e.g., a 640×480 frame comprises over 300,000 pixels). Each pixel is represented by a binary pattern that describes that pixel's characteristics (e.g., color, brightness, etc.). Motion video data usually consists of a sequence of frames that, when displayed at a particular frame rate, will appear as “real-time” motion to a human eye. Given the number of pixels in a typical frame, storing and/or transmitting data corresponding to every pixel in a frame or still or motion video data requires a relatively large amount of computer storage space and/or bandwidth. Additionally, in several motion video applications, processing and displaying a sequence of frames must be performed fast enough to provide real-time motion (typically, between 15-30 frames per second). For example, a system using a frame size of 640×480 pixels, using 24 bits to represent each pixel, and using a frame rate of 30 frames-per-second would be required to store and/or transmit over 14 megabytes of data per second.
Techniques have been developed to compress the amount of data required to represent images, making it possible for more computing systems to process video data. Compression techniques may compress video data based on either individual pixels (referred to as pixel compression) or blocks or regions of pixels (referred to as block compression) or a combination of both. Typically, pixel compression techniques are relatively easier to implement and provide higher quality than block compression techniques. Although pixel compression techniques generally provide relatively high quality and resolution for a restored image than block compression techniques, pixel compression techniques suffer from lower compression ratios (e.g., large encoding bit rates) because pixel compression techniques consider, encode, transmit, and/or store individual pixels.
One prior art block compression technique is based on compressing motion video data representing pixel information for regions (or blocks) in each frame of a motion video sequence without using information from other frames (referred to as INTRAframe or spatial compression) in the motion video frame sequence.
One type of intraframe compression involves transform coding (e.g., discrete cosine transform). Transform encoded data requires less bits to represent than original data for a frame region, and typically provides relatively high quality results. Unfortunately, transform encoding requires a relatively substantial amount of computation. Thus, transform coding is performed only when necessary (e.g., when another compression technique cannot be performed) in block compression techniques.
Another type of block compression technique typically used in conjunction with intraframe (or transform) encoding for the compression of motion video data is referred to as INTERframe or temporal compression. Typically, one or more regions (blocks) of pixels in one frame will be the same or substantially similar to regions in another frame. The primary aim of temporal compression is to eliminate the repetitive (INTRAframe) encoding and decoding of substantially unchanged regions between successive frames in a sequence of motion video frames. By reducing the amount of intraframe encoding, temporal compression generally saves a relatively large amount of data storage and computation.
When using intraframe compression in conjunction with temporal compression, the first frame in a sequence of frames is intraframe (e.g., DCT) encoded. Once encoded, the first frame becomes the “base frame” for encoding the next “new” frame (i.e., the second frame) in the sequence of frames. Thus, the frame currently being encoded is referred to as the new frame, and the frame preceding the new frame is referred to as the base (or old) frame (which is assumed to have been previously been encoded and stored).
To perform intraframe/temporal compression on a new frame, the first steps performed in nearly all temporal compression systems are frame decomposition and pixel classification. One prior art technique initially decomposes the new frame in a sequence of motion video frames into non-overlapping regions (or blocks) of a predetermined size. Next, each pixel in each region of the new frame is compared to a corresponding pixel (i.e., at the same spatial location) in the base frame to determine a “pixel type” for each pixel in the new frame. (“Corresponding” region or pixel is used herein to refer to a region or pixel in one frame, e.g., the base frame, that is in the same spatial location of a frame as a region or pixel in another frame, e.g., the new frame.) Based on a set of predetermined temporal difference thresholds, each pixel in the new frame is classified as new (non-static) or old (static).
Based primarily on the classification of pixels, it is determined if each region in the new frame is substantially similar to the corresponding region at the same spatial location in the base frame. If a region in the new frame does not contain at least a predetermined threshold number of new pixels, then that region is considered to be substantially similar to the corresponding region in the base frame and is classified as “static.” Static regions are encoded by storing data indicating that the region has already been encoded as part of the base frame. The data required to indicate that a region is already encoded is substantially less than the data required to represent an uncompressed or intraframe encoded region. Thus, entire (static) regions do not need to be repeatedly intraframe encoded, stored/transmitted, and decoded, thereby saving a relatively substantial degree of computation and storage.
In addition to classifying regions as “static”, temporal compression techniques typically also perform motion estimation and compensation. The principle behind motion estimation and compensation is that the best match for a region in a new frame may not be at the same spatial location in the base frame, but may be slightly shifted due to movement of the image(s) in the motion video. By determining that a region in a new frame is substantially the same as another region in the base frame within a predetermined threshold distance of the region in the base frame at the same spatial location, an indication, referred to as a motion compensation (MC) vector, can be generated to indicate the change of location of the region in the new frame relative to the base frame. Thus, a static region can be considered as an MC region with a zero-magnitude MC vector. Since the region in the base frame corresponding to the MC region in the new frame has already been encoded, stored/transmitted, and decoded, the entire MC region does not have to be repeatedly intraframe encoded, stored/transmitted, and decoded. Again, by using an indication (e.g., an MC vector) to identify in a new frame a previously encoded and stored region of a base frame that is substantially the same as a region of a new frame (but spatially displaced), repeated encoding and storage can be avoided, thereby saving a relatively substantial amount of computation and storage expense.
Thus, region(s) in the new frame in the sequence of frames may be temporally encoded if found to be similar (within a predetermined temporal difference threshold) as a region in the already encoded base frame. Once the new frame is encoded, the encoded data from the new frame is used to update the base frame, and the updated base frame then becomes the base frame for the next “new” frame in the sequence of frames as the process is repeated.
By considering regions of pixels and determining temporal differences between such regions, block compression techniques generally provide higher compression ratios tha
Alaris Inc.
Blakely , Sokoloff, Taylor & Zafman LLP
Le Vu
LandOfFree
Method and apparatus for compression and decompression of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for compression and decompression of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for compression and decompression of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2824726