Image analysis – Color image processing – Compression of color images
Reexamination Certificate
1998-05-14
2002-05-28
Couso, Yon J. (Department: 2623)
Image analysis
Color image processing
Compression of color images
C382S235000, C348S391100
Reexamination Certificate
active
06396948
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to compression and decompression of data. More specifically, the present invention relates to a good quality video codec implementation that achieves a good compression ratio for low bit rate video.
BACKGROUND OF THE INVENTION
A number of important applications in image processing require a very low cost, fast and good quality video codec (coder/decoder) implementation that achieves a good compression ratio. In particular, a low cost and fast implementation is desirable for low bit rate video applications such as video cassette recorders (VCRs), cable television, cameras, set-top boxes and other consumer devices.
One way to achieve a faster and lower cost codec implementation is to attempt to reduce the amount of memory needed by a particular compression algorithm. Reduced memory (such as RAM) is especially desirable for compression algorithms implemented in hardware, such as on an integrated circuit (or ASIC). For example, it can be prohibitively expensive to place large amounts of RAM into a small video camera to allow for more efficient compression of images. Typically, smaller amounts of RAM are used in order to implement a particular codec, but this results in a codec that is less efficient and of less quality.
Although notable advances have been made in the field, and in particular with JPEG and MPEG coding, there are still drawbacks to these techniques that could benefit from a better codec implementation that achieves a higher compression ratio using less memory. For example, both JPEG and motion JPEG coding perform block-by-block compression of a frame of an image to produce compressed, independent blocks. For the most part, these blocks are treated independently of one another. In other words, JPEG coding and other similar forms of still image coding end up compressing a frame at a time without reference to previous or subsequent frames. These techniques do not take full advantage of the similarities between frames or between blocks of a frame, and thus result in a compression ratio that is not optimal.
Other types of coding such as MPEG coding use interframe or interfield differencing in order to compare frames or fields and thus achieve a better compression ratio. However, in order to compare frames, at least one full frame must be stored in temporary storage in order to compare it to either previous or subsequent frames. Thus, to produce the I, B, and P frames necessary in this type of coding, a frame is typically received and stored before processing can begin. The amount of image data for one frame can be prohibitive to store in RAM, and makes such codec implementations in hardware impractical due to the cost and the size of the extra memory needed. In particular, these codec implementations on an integrated circuit or similar device can be simply to expensive due to the amount of memory required.
Previous efforts have attempted to achieve better compression ratios. For example, the idea of performing operations in the DCT transform domain upon a whole frame has been investigated before at UC Berkeley and at the University of Washington for a variety of applications such as pictorial databases (zooming in on an aerial surface map with a lot of detail).
Thus, it would be desirable to have a technique for achieving an improved compression ratio for video images while at the same time reducing the amount of storage needing to be used by the technique. In particular, it would be desirable for such a technique to reduce the amount of memory needed for an implementation on an integrated circuit.
Boundaries between blocks also present difficulties in compression of video images. A brief background on video images and a description of some of these difficulties will now be described.
FIG. 1
illustrates a prior art image representation scheme that uses pixels, scan lines, stripes and blocks. Frame
12
represents a still image produced from any of a variety of sources such as a video camera, a television, a computer monitor etc. In an imaging system where progressive scan is used each image
12
is a frame. In systems where interlaced scan is used, each image
12
represents a field of information. Image
12
may also represent other breakdowns of a still image depending upon the type of scanning being used. Information in frame
12
is represented by any number of pixels
14
. Each pixel in turn represents digitized information and is often represented by 8 bits, although each pixel may be represented by any number of bits.
Each scan line
16
includes any number of pixels
14
, thereby representing a horizontal line of information within frame
12
. Typically, groups of 8 horizontal scan lines are organized into a stripe
18
. A block of information
20
is one stripe high by a certain number of pixels wide. For example, depending upon the standard being used, a block may be 8×8 pixels, 8×32 pixels, or any other in size. In this fashion, an image is broken down into blocks and these blocks are then transmitted, compressed, processed or otherwise manipulated depending upon the application. In NTSC video (a television standard using interlaced scan), for example, a field of information appears every 60th of a second, a frame (including 2 fields) appears every 30th of a second and the continuous presentation of frames of information produce a picture. On a computer monitor using progressive scan, a frame of information is refreshed on the screen every 30th of a second to produce the display seen by a user.
FIG. 2
illustrates an image
50
that has been compressed block-by-block and then decompressed and presented for viewing. Image
50
contains blocks 52-58 having borders or edges between themselves 62-68. Image
50
shows block boundaries 62-68 having ghosts or shadows (blocking artifacts). For a variety of prior art block-by-block compression techniques, the block boundaries 62-68 become visible because the correlation between blocks is not recognized. Although the block boundaries themselves may not be visible, these blocking artifacts manifest themselves at the block boundaries presenting an unacceptable image.
One technique that is useful for compressing an image block-by-block is to use a 2-6 Biorthogonal filter to transform scan lines of pixels or rows of blocks. A 2-6 Biorthogonal filter is a variation on the Haar transform. In the 2-6 Biorthogonal filter sums and differences of each pair of pixels are produced as in the Haar transform, but the differences are modified (or “lifted”) to produce lifted difference values along with the stream of sum values. In the traditional 2-6 Biorthogonal filter, the stream of sum values are represented by the formula: s
i
=x
2i
+x
2i+1
, the x values representing a stream of incoming pixels from a scan line. Similarly, the stream of difference values are represented by the formula: d
i
=x
2i
−x
2i+1
. The actual lifted stream of difference values that are output along with the stream of sum values are represented by the formula w
i
=d
i
−s
i−1
/8+s
i+1
/8. The 2-6 Biorthogonal filter is useful because as can be seen by the formula for the lifted values “w”, each resultant lifted value “w” depends upon a previous and a following sum of pairs of pixels (relative to the difference in question). Unfortunately, this overlap between block boundaries makes the compression of blocks dependent upon preceding and succeeding blocks and can become enormously complex to implement. For example, in order to process the edges of blocks correctly using the above technique a block cannot be treated independently. When a block is removed from storage for compression, part of the succeeding block must also be brought along and part of the current block must also be left in storage for the next block to use. This complexity not only increases the size of the memory required to compress an image, but also complicates the compression algorithm.
Prior art techniques have attempted to treat blocks independently
Arrighi William J.
Hoover D. Robert
Kolarov Krasimir D.
Lynch William C.
Beyer Waever & Thomas LLP
Couso Yon J.
Interval Research Corporation
LandOfFree
Color rotation integrated with compression of video signal does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Color rotation integrated with compression of video signal, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Color rotation integrated with compression of video signal will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2847600