Pulse or digital communications – Bandwidth reduction or expansion
Reexamination Certificate
1998-05-05
2002-04-16
Kelley, Chris (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
C382S239000, C382S166000, C358S539000
Reexamination Certificate
active
06373890
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to compressing color video data and, more specifically, to varying the degree of compression as a function of the color characteristics of the video data being compressed.
Color video animations or videotapes of images or scenes can be used to enhance the realism and/or usefulness of computer generated displays and graphics. These video images are typically stored as a stream of digital color video data on a storage device such as a CD-ROM disk in a retrievable format. When desired by the viewer, or when directed by the software program, the color video data representing the video image is retrieved from the storage device and displayed on a display device, such as a video monitor. In practice, the video data is not displayed continuously, but is divided into a series of frames. Each frame of video data comprises the necessary information to display a single screen, or “snapshot” of the video on the display device. Displaying a sequential series of frames in rapid succession can create the illusion of moving pictures.
The quality and realism of the displayed image is a function of the resolution of the display device and the number of colors that the display device is capable of displaying. Typically, reasonable image resolution can be achieved with a display device that displays an image where the image consists of 480 horizontal lines of 640 pixels, or picture elements, per line, although images suitable for some video games may be displayed on devices having resolutions as low as 240 horizontal lines of 320 pixels. Recently, higher resolution display devices capable of displaying 1024 lines of 1280 pixels per line have become commonly available. Where only a simple, two-tone monochrome image is desired, each pixel can be represented by a single bit of video data, since the pixel is either illuminated or dark, depending on the image. Typically, however, monochrome images are displayed using eight bits of data to represent each pixel, allowing each pixel of the image to be displayed in one of a possible 256 shades of a single color. Images displayed in color are much more exciting and visually pleasing than monochrome images, especially when used to enhance the realism of video games and simulations. Substantially more information in the form of digital video color data, however, is required to reproduce color images. In the simplest case, at least three times as much digital data must be used to define a color to be displayed by an individual pixel, since each color consists of a combination of the primary colors red, blue and green, and each of these colors must be defined by digital data. Current display devices, using the RGB (red-blue-green) format are capable of providing as many as 16,777,216 colors by using 24 bits of color video data to define each pixel.
Where relatively static images are to be displayed, the amount of color video data required is not a critical factor in the performance of the software program. However, where a video animation or moving image is desired, the video will appear jerky, unnatural and unrealistic if the video data is not displayed at a rate of at least 30 frames per second, the NTSC television standard. A single video clip lasting one minute must thus be composed of at least 1800 frames of video color data. This enormous amount of video color data must be stored on and retrieved from a CD-ROM or other device having enough storage space to hold all the video color data for the video clip.
A further problem is that storage devices such as CD-ROMs have limited data transfer rates, typically a maximum of about 600,000 bits per second. Where the data cannot be retrieved and displayed rapidly enough, the formation of the video image may stall momentarily while the color video data is being transferred from the storage device to the display device, and detracts from the realism of the displayed video images. In order to increase the effective speed of such storage devices and decrease the wait time for generating a moving color video display, numerous compression and decompression techniques to reduce the amount of color video data that must be stored and retrieved have been proposed. Some compression techniques divide a picture or image into a matrix of blocks, each of which is in turn divided into a matrix of picture elements or pixels. The picture or image can be converted into digital data which can then be used to generate a video display of the original picture, wherein certain information must be encoded for every pixel of every block. The amount of data required per pixel and the quality in detail of the picture that can be generated from the data are important characteristics of any compression system. In some instances, the data is compressed in a uniform manner block-by-block or frame-by-frame. In this way, m bits of compressed data are used to represent each n×n block of pixel data. Other systems utilize an adaptive compression method wherein color video data is examined block-by-block, and the type of compression to be used is then determined for each block. In one known system, two diverse colors for each block are determined by averaging the colors that are above and below the mean luminance for the block. These two computed colors may then be compared to a threshold value in order to determine the number of colors to be stored for the block.
Another method of compressing and decompressing a stream of video data is disclosed in U.S. Pat. No. 5,625,759. In this patent, each frame of video is broken up into blocks of pixels, and then the number of colors in the block is minimized by collapsing colors which are not substantially different from the colors of neighboring pixels into the color of the neighboring pixel.
While each of the methods described above usefully compress video data where the color data consists of “eight-bit” data, the use of such data may lead to unwanted artifacts during playback. Such artifacts can be readily observed in background scenes, such as where a plane is silhouetted against a cloudy sky. In such a visual scene, compression of the colors may cause streaking or banding of the colors in the scene.
It is well known that many of the visual artifacts observed in scenes created using compressed eight-bit color data can be suppressed using color data wherein the colors are described using twenty-bit or higher color definitions. However, until now, the use of such higher data definitions negated any advantage obtained in compressing the color data, since, for example, twenty-four bit color data requires three times as much data storage as does eight-bit color data.
What is needed in the art is a method of compressing and decompressing color video data so that the recreated video image accurately reflects the colors of the original video image while reducing the amount of data necessary so as to produce moving color images in real time from storage devices having a fixed data rate. In particular what has been needed is a method of compressing color video data consisting of higher resolution color data, such as twenty-bit (or more) color data, such that the storage space required for the resulting compressed color data is approximately the same as that required for previously available compressed eight-bit color data. Using such a method, the video stream should be capable of producing essentially artifact-free visual scenes without incurring a penalty of increased storage resources. Moreover, the increased resolution and freedom from artifacts is obtained without lagging behind the video display. The present invention meets these needs.
SUMMARY OF THE INVENTION
The present invention is directed towards a method for compressing color video data for storage using the colors of the original video image.
In an embodiment of the invention, the method of compressing color video data comprises the steps of dividing a color video frame into blocks of color video data; determining the colors present in a block; calculating a minimum number of colors
An Shawn S.
Fulwider Patton Lee & Utecht LLP
Kelley Chris
NovaLogic, Inc.
LandOfFree
Video compression and playback process does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Video compression and playback process, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Video compression and playback process will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2840260