Image analysis – Image compression or coding – Interframe coding
Reexamination Certificate
2000-02-28
2003-02-25
Patel, Jayanti K. (Department: 2621)
Image analysis
Image compression or coding
Interframe coding
C348S396100, C375S340000
Reexamination Certificate
active
06526174
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of data compression.
2. Background Art
Compression is a scheme for reducing the amount of information required to represent data. Data compression schemes are used, for example, to reduce the size of a data file so that it can be stored in a smaller memory space. Data compression may also be used to compress data prior to its transmission from one site to another, reducing the amount of time required to transmit the data. To access the compressed data, it is first decompressed into its original form. A compressor/decompressor (codec) is typically used to perform the compression and decompression of data. One measure of the performance or efficiency of a codec is its “compression ratio”. Compression ratio refers to the ratio of number of bits of uncompressed data to the number of bits of compressed data. Compression ratios may be 2:1, 3:1, 4:1 etc.
Data compression may also be required when the input/output rate of a particular data receiver is less than the data rate of the transmitted data. This can occur when providing video data to computer systems. Video data of frame size 320×240 is provided at rates approaching 7 megabytes per second. This rate is greater than the rate of commonly used I/O subsystems of personal computers. Some representative rates of common I/O subsystems found on personal computers (PC) are:
Serial Communications
1-2 kilobytes/sec;
ISDN
8-16 kilobytes/sec;
Ethernet/CD-ROM
150-300 kilobytes/sec;
SCSI Disk
0.5-2 megabytes/sec.
Another measure of video codec compression ratio is the average compressed bits-per-pixel. This measure is useful in describing video compression because different conventions are used for calculating the size of uncompressed video, i.e., some use 24 bits-per-pixel RGB and others use 4:2:2 subsampled YUV (16-bits per pixel). The averaging accounts for potentially different strategies employed for frames in a sequence. The bandwidth requirements for a sequence of frames is calculated by multiplying the average compressed bits-per-pixel and the number of frames per second, and dividing the resulting product by the number of pixels in each encoded frame.
Nearly all video compression techniques are lossy, i.e., information is inevitably discarded in the compression process. A measure of quality is how much this information is noticed by a human observer. However, there is not a consistent, objective model of human perception that can be applied. A simple, concrete, quality metric that is frequently used is the Mean-Squared-Error (MSE) that measures the error on a per-pixel basis from the uncompressed original.
Most compression algorithms are computationally complex, which limit their application since very complex algorithms often require expensive hardware to assist in the compression. A useful number to measure computational complexity of software-based compression algorithms is MIPS per megapixels/sec, i.e., essentially instructions/pixel. For example, an algorithm just capable of compressing 320×240 pixels per frame at 30 frames per second on a 40 MIPS machine has a computational complexity of 40,000,000/(320×240×30)≡17 instructions/pixel.
Symmetry refers to the ratio of the computational complexity of compression to that of decompression. Codec's are frequently designed with a greater computational load on the compressor than the decompressor, i.e., they are asymmetric. While this may be a reasonable strategy for “create-once, play-many” video sequences, it limits the range of applications for the codecs. Asymmetric compression techniques are not suitable for teleconferencing, for example, since teleconferencing requires essentially real-time processing and substantially equivalent compression and decompression rates.
Block Transform Coding Example (IPEG)
In the prior art, a class of image compressors called Block Transform Coding (BTC) is used. This is a fundamentally symmetric, image-compression technique that is used in (MPEG) and (JPEG) compression algorithms. In BTC, an image is divided into small blocks, the blocks are transformed using an invertible, two dimensional (2-D) mathematical transform, the transformed image is quantized, and the quantized result is losslessly compressed. This process forms the core of JPEG and MPEG compression, which use 8×8 blocks and a Discrete Cosine Transform (DCT) to perform the 2-D transform.
FIG. 1
is a diagram illustrating computational blocks of a prior art system for performing JPEG still-image, compression. Input image
102
is provided to the color-space conversion and subsampling block
110
. The output of the color-space conversion and subsampling block
110
is provided to block
112
for dividing each image plane into 8×8 blocks. The output of block
114
is provided to the Discrete Cosine Transform block
114
. Block
114
provides DC terms
116
to quantization block
120
, which quantizes the DC terms
116
using differential pulse code modulation (DPCM). Block
114
provides AC terms
118
to block
122
, which scalar quantizes the AC terms
118
by frequency. The outputs of blocks
120
and
122
are provided to the Huffman block
124
, which compresses the quantized values using variable length codes to provide output
126
.
Digital images
102
are typically stored in an RGB format, where each pixel is represented as a tuple of red (R), green (G), and blue (B) samples. While RGB format is suited towards most digital color input and output devices, it is not particularly efficient for the human visual system, or natural scenes. For example, in natural scenes the R, G, and B components of colors are highly correlated because most natural colors are very close to shades of gray, where R=G=B (i.e., saturated colors are rare). In other words, with respect to information coding,.the correlation between RGB signals means that there is redundant information stored in the R, G, and B channels. To account for this redundant information, color-space conversion and subsampling block
110
transforms the colors of input image
102
into a color space with an explicit brightness, or luminance, dimension prior to compression. More bits are typically used to precisely specify the brightness while relatively fewer bits are used to specify the chrominance.
Broadcast television (TV) uses YUV color space to better utilize the bandwidth of TV's. The YUV color space is essentially a rotation of the RGB basis vectors so that the luminance axis (Y) of YUV color space is aligned with the gray diagonal of RGB color space, which extends from RGB coordinates (0, 0, 0) to (1, 1, 1). The transformation for converting RGB color values to YUV space is expressed by Equation (1):
[
Y
U
V
]
=
[
0.161
0.315
0.061
-
0.079
-
0.155
0.234
0.330
-
0.227
-
0.053
]
[
R
G
B
]
.
(
1
)
Reduction of redundant information can be achieved using the YUV color-space representation obtained using Equation (1). The human eye is much less sensitive to spatial detail in the U and V channels than it is in the Y channel because receptors in the eye for brightness (Y) are more numerous than those for chrominance (U, V). Using this fact, the U and V components can be sampled at a lower resolution. In JPEG compression, the U and V components are frequently subsampled by a factor of 2 in both x- and y-directions. For example, four Y samples and one sample each of U and V are produced for each 2×2 block of an input image. For 8-bit samples per channel, this effectively produces a 2:1 compression factor. Thus, color-space conversion and subsampling block
110
converts an input image
102
from RGB color space to YUV color space using the transformation of Equation (1) and subsamples the input image
102
to reduce redundant information.
Once block
110
converts the input image
102
to YUV color space and subsamples the U and V planes, the prior art JPEG system of
FIG. 1
treats the resulting three image planes (Y, U, and V) independently and codes them
NeXT Computer, Inc.
Patel Jayanti K.
The Hecker Law Group
LandOfFree
Method and apparatus for video compression using block and... 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 video compression using block and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for video compression using block and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3133374