Intra compression of pixel blocks using predicted mean

Details Intra compression of pixel blocks using predicted mean Intra compression of pixel blocks using predicted mean

1997-05-05

2003-05-27

Tran, Phuoc (Department: 2621)

Image analysis

Image compression or coding

Interframe coding

C375S240130

Reexamination Certificate

active

06571016

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method and apparatus for compression of multimedia data. More specifically, the present invention relates to a method and apparatus for predictive compression of video frames.
2. Description of the Related Art
The creation of pictures or images has been a human activity since the beginning of humanity. However, until recent history viewing of an image required the viewer to be physically present at the image. This was geographically cumbersome. Photography, both still and motion, broke this geographic constraint by allowing pictures to be captured and transported independent of the physical images they represented. Television enhanced transmission of images, by sending images, recorded or live, to any geographic location capable of receiving a radio signal. But, for the most part, viewers of television can only view images that are scheduled for transmission, rather than selecting images at will.
With the development of computers, and more specifically computers that are linked across a network, images stored on one computer may be demanded by a viewer, and almost instantaneously provided to the viewer's computer over the computer network. One computer network that is increasingly being used is the Internet, the well-known international computer network that links various military, government, education, nonprofit, industrial and financial institutions, commercial enterprises, and individuals.
Images are typically of two types: 1) single pictures; or 2) moving pictures. Single pictures include photographs, computer art, faxes and web pages. Moving pictures typically include a number of single images or frames organized into a particular sequence. Within a computer network, images are captured and stored on one computer, and then transmitted over the network to another computer for viewing. An example of this is provided in
FIG. 1
, to which reference is now made.
FIG. 1
illustrates a computer system
100
that includes a server
102
connected to a number of mass storage devices
104
. The mass storage devices
104
are used to store a number of video frames
120
. The video frames
120
could be still images, or could be combined into sequences to create moving pictures, as described above. The sequences reside on the mass storage devices
104
, and upon request, may be transmitted by the server
102
to other computers
108
via a network
106
. In addition, the video frames
120
may be transferred to remote computers, such as the computer
112
, via a network
116
, using a router
110
and/or a modem
114
. One skilled in the art should appreciate that the network
116
could be a dedicated connection, or a dial-up connection, and could utilize any of a number of network protocols such as TCP/IP or Client/Server configurations.
In operation, a user sitting at any of the computers
108
,
112
would request video frames
120
from the server
102
, and the server would retrieve the video frames
120
from the mass storage devices
104
, and transmit the frames
120
over the network
106
. Upon receipt of the video frames
120
, the computers
108
,
112
would display the images for the requester.
It should be appreciated that the computers
108
,
112
may be positioned physically close to the server
102
, or may be thousands of miles away. The computers
108
,
112
may be connected to the server
102
via a direct LAN connection such as Ethernet or Token Ring, or may utilize plain old telephone service (POTS), ISDN or ADSL, depending on the availability of each of these services, their cost, and the performance required by the end user. As is typically of computer equipment and services, higher performance means more cost.
In most cases, the amount of data required to represent a video frame, or more specifically a sequence of video frames
120
is significant. For example, a color image or frame is typically represented by a matrix of individual dots or pixels, each having a particular color defined by a combination of red, green and blue intensities (RGB). To create a palette of 16 million colors (i.e., true color), each of the RGB intensities are represented by an 8-bit value. So, for each pixel, 24-bits are required to define a pixel's color. A typical computer monitor has a resolution of 1024 pixels (across) by 768 pixels (down). So, to create a full screen image for a computer requires 1024×768×24 bits=18,874,368 bits, or 2,359,296 bytes of data to be stored. And that is just for one image.
If a moving picture is to be displayed, a sequence of images are grouped, and displayed one after another, at a rate of approximately 30 frames per second. Thus, a 1 second, 256 color, full screen movie could require as much as 60 megabytes of data storage. With present technology, even very expensive storage systems, and high speed networks would be overwhelmed if alternatives were not provided. By way of example, as the resolution and the frame rate requirements of a video increase, the amount of data that is necessary to describe the video also increases.
One alternative to reducing the amount of data required to represent images or moving pictures is to simply reduce the size of frames that are transmitted and displayed. One popular frame size is 320 pixels in width and 240 pixels in height, or 320×240. Thus, a 256 color frame of this size requires 320×240×24=1,843,200 bits, or 230 kilobytes of data. This is significantly less ({fraction (1/10)}
th
) than what is required for a full screen image. However, as frames are combined into moving pictures, the amount of data that must be transmitted is still significant.
An additional solution to reducing the amount of storage space required for video frames involves compressing the data. The extent to which data is compressed is typically measured in terms of a compression ratio or a bit rate. The compression ratio is generally the number of bits of an input value divided by the number of bits in the representation of that input value in compressed code. Higher compression ratios are preferred over lower compression ratios. The bit rate is the number of bits per second of compressed data required to properly represent a corresponding input value.
There are three basic methods involved in any data compression scheme: 1) transformation, 2) reduced precision (quantization), and 3) minimization of number of bits (encoding). Each of these methods may be used independently, or may be combined with the other methods to obtain optimum compression. Although the number of scheme combinations is large, typically compression is accomplished by a sequential process of transformation, precision reduction, and coding. Coding is always the final stage of the process, but there are sometimes several transformation and precision reduction iterations. This process is summarized in
FIG. 2
, to which attention is now directed.
In
FIG. 2
, a block
202
is shown to illustrate the step of transformation, a block
204
is shown to illustrate the step of quantization, and a block
206
is shown to illustrate the step of coding. The transformation block
202
transforms a data set into another equivalent data set that is in some way smaller than the original. Some transformations reduce the number of data items in a set. Other transformations reduce the numerical size of data items that allow them to be represented with fewer binary digits.
To reduce the number of data items in a set, methods are used that remove redundant information within the set. Examples of such methods include Run-Length-Encoding (RLE) and LZW encoding. RLE is a pattern-recognition scheme that searches for the repetition of identical data values in a list. The data set can be compressed by replacing the repetitive sequence with a single data value and a length value. Compression ratios obtainable from RLE encoding schemes vary depending on the type of data to be encoded, but generally range from 2:1 up to 5:1. LZW encoding replaces rep

Affiliated with

Also associated with

Rating

Intra compression of pixel blocks using predicted mean does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Intra compression of pixel blocks using predicted mean, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Intra compression of pixel blocks using predicted mean will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3036046