Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1999-01-28
2001-04-24
Le, Vu (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C348S416100, C348S699000
Reexamination Certificate
active
06222883
ABSTRACT:
TECHNICAL FIELD
This invention relates in general to an apparatus and method for encoding digital visual images including spatial (intra-picture) and temporal (inter-picture) compression, that is reducing both redundancy within a picture and redundancy between pictures. Redundancy within pictures is reduced, or even eliminated, by the use of the discrete cosine transform, quantization, and variable length encoding. Redundancy between pictures is reduced, or even eliminated, through the use of motion vectors. This invention is more particularly directed to an encoder with an enhanced search range for motion estimation and compensation, without adversely impacting chip performance or design criteria.
BACKGROUND OF THE INVENTION
The Moving Picture Experts Group (MPEG) MPEG-2 Standard is a compression/decompression standard for video applications. The standard describes an encoded and compressed data stream that has substantial bandwidth reduction. The compression is a subjective lossly compression. The encoded, compressed digital video data is subsequently decompressed and decoded in an MPEG-2 Standard compliant decoder.
The MPEG-2 Standard is described in, e.g., C. A. Gonzales and E. Viscito, “Motion Video Adaptive Quantization In The Transform Domain,” IEEE Trans Circuits Syst Video Technol, Volume 1, No. 4, December 1991, pp. 374-378, E. Viscito and C. A. Gonzales, “Encoding of Motion Video Sequences for the MPEG Environment Using Arithmetic Coding,” SPIE, Vol. 1360, pp. 1572-1576, (1990), D. LeGall, “MPEG: A Video Compression Standard for Multimedia Applications,” Communications of the ACM, Vol. 34, No. 4, (April 1991), pp. 46-58, S. Purcell and D. Galbi, “C Cube MPEG Video Processor,” SPIE, v. 1659, (1992) pp. 24-29, and D. J. LeGall, “MPEG Video Compression Algorithm,” Signal Process Image Commun, v.4, n. 2, (1992), pp. 129-140, among others.
The MPEG-2 Standard specifies a data stream format and a decoder for a very high compression technique that achieves overall image data stream compression not achievable with either intraframe coding alone or interframe coding alone, while preserving the random access advantages of pure intraframe coding. The combination of block based frequency domain intraframe encoding and interpolative/predictive interframe encoding of the MPEG-2 Standard results in a balance between intraframe encoding alone and interframe encoding alone.
The MPEG-2 Standard exploits temporal redundancy for motion compensated interpolative and predictive encoding. That is, the assumption is made that “locally” the current picture can be modeled as a translation of the picture at a previous and/or future time. “Locally” means that the amplitude and direction of the displacement are not the same everywhere in the picture.
The MPEG-2 Standard specifies predictive and interpolative interframe encoding and frequency domain intraframe encoding. It has block based motion compensation for the reduction of temporal redundancy, and block based Discrete Cosine Transform based compression for the reduction of spatial redundancy. Under the MPEG-2 Standard, motion compensation is achieved by predictive coding, interpolative coding, and Variable Length Coded motion vectors. The information relative to motion is based on a 16×16 array of pixels and is transmitted with the spatial information. Motion information is compressed with Variable Length Codes, such as Huffman codes.
The motion compensation unit under the MPEG-2 Standard is the Macroblock unit. The MPEG-2 Standard Macroblocks are 16×16 pixels. Motion information consists of vectors for forward predicted macroblocks, vectors for backward predicted macroblocks, and vectors for bidirectionally predicted macroblocks. The motion information associated with each macroblock is coded differentially with respect to the motion information present in the previous macroblock. In this way a macroblock of pixels is predicted by a translation of a macroblock of pixels from a past or future picture.
The difference between the source pixels and the predicted pixels is included in the corresponding bit stream. The decoder adds a correction term to the block of predicted pixels to produce the reconstructed block.
In a typical block matching search for video encoding motion estimation, the reference search area is rectangular in shape. The width and height of this rectangle is referred to as the search range, as it represents a portion of the reference frame around the position of the macroblock to be coded in which a best match result is sought to compensate for motion between the current and reference frames. The larger the search range, the better the chance to find a nearly identical macroblock to the one being encoded. With a good match, fewer bits are needed to encode the macroblock since all that is required is the vector showing the displacement from the current macroblock, and the small differences between the macroblocks.
High definition video requires large search ranges due to its higher resolutions. The full size of a high definition television (HDTV) frame makes encoding the entire picture by a single encoder prohibitive. Conventionally, multiple encoders are employed, with each encoder encoding a portion of the picture. The portions are then stitched together to create one encoded stream. Motion searching needs to overlap at the seams (i.e., the borders of each encoder's portion of the whole picture), to minimize visual artifacts.
Increasing the search range by simply increasing the maximum size of the rectangle is one possible solution, but may have an adverse effect on encoder performance. Generally, the larger the search range, the more time it takes to perform the search. Increasing the maximum rectangle also entails adding more data storage capability on chip, which will increase encoder size and power consumption.
In view of the above, and in order to establish commercial advantage, a novel approach is needed for performing macroblock match searching during video encoding motion estimation, particularly for high definition video.
DISCLOSURE OF THE INVENTION
Briefly summarized, the invention comprises in one aspect a macroblock matching search method for video encoding motion estimation. The method includes: defining from a reference frame a diamond-shaped search window about a current position of the macroblock; partitioning the diamond-shaped search window into multiple search regions and reassembling the multiple search regions into a rectangular search area; and using the rectangular search area to search within the diamond-shaped search window for a best matching reference macroblock to the current macroblock.
In another aspect, a macroblock matching search method for video encoding motion estimation within a video encoding system is provided. This method includes: providing a rectangular search area comprising a partitioned and reassembled diamond-shaped search window containing macroblocks of a reference frame; and searching within the diamond-shaped search window for a best matching reference macroblock for the current macroblock using the rectangular search area, the searching including selecting a starting position and traversing the rectangular search area stepwise horizontally and vertically to identify the best matching reference macroblock.
In still another aspect, a system for performing motion estimation within a digital video encoder is provided. The system includes means for defining from a reference frame a diamond-shaped search window about a current position of a macroblock being encoded. The system also includes means for partitioning the diamond-shaped search window into multiple search regions and for reassembling the multiple search regions into a rectangular search area, as well as means for using the rectangular search area to search the diamond-shaped search window for a best matching reference macroblock for the current macroblock.
In a further aspect, an article of manufacture is provided which includes a computer program product having computer usable medium with computer r
Murdock John A.
Ngai Agnes Y.
Westermann Edward F.
Heslin & Rothenberg, P.C.
International Business Machines - Corporation
Le Vu
LandOfFree
Video encoding motion estimation employing partitioned 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 Video encoding motion estimation employing partitioned and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Video encoding motion estimation employing partitioned and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2453561