Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-04-16
2001-02-27
Kelley, Chris S. (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06195389
ABSTRACT:
CROSS REFERENCE TO RELATED PATENT APPLICATIONS
Background of the Invention
1. Field of the Invention
The invention concerns encoding sequences of digital pictures generally and more specifically concerns the motion estimation operations performed while encoding a sequence of digital pictures.
2. Description of the Prior Art
The following Description of the Prior Art first discusses compression of digital pictures generally, then motion estimation as currently practiced, and finally, the problems of the current techniques.
Compression of Digital Pictures
Digital pictures are originally represented in the memory of a computer system as arrays of picture elements or pixels. Each pixel represents a single point in the picture. The pixel itself is an item of data and the contents of the item of data determine how the point represented by the pixel will appear in the digital picture. The quality of a digital picture of course depends on the number of pixels in the picture and the number of bits in the pixels. The more pixels there are in the picture, the finer the resolution, and the more bits in each pixel, the more information it can store about the point in the image represented by the pixel. For instance, the more bits in the pixel, the more shades of color it can represent.
Because this is the case, the arrays of pixels used to originally represent high-quality digital pictures are very large and require large amounts of memory. The size of the arrays is particularly troublesome when the digital pictures in question are part of a sequence of pictures that when seen in the proper order and with the proper timing make a moving picture. The apparatus that is displaying the sequence of pictures must be able not only to store them but also to read and display them quickly enough so that the timing requirements for the moving pictures are met.
The problems of timing and storage are particularly severe where the sequence of digital pictures is distributed by means of a medium with limited bandwidth to a receiver with limited storage. Examples where this is the case are digital television, videoconferencing, or videotelephony. In these applications, the sequence of pictures must be transmitted by means of a broadcast or cable television channel, a telephone line, or a computer network to a relatively low-cost consumer device such as a television set, video telephone, or personal computer with limited amounts of memory to store the pictures. These applications are consequently economically practical only if some way is found to compress the digital pictures and thereby to reduce the bandwidth required to transmit the pictures and/or the storage required to store them at their destinations.
The art has developed many different techniques for compressing sequences of digital pictures. One example of these techniques is the MPEG-2 standard for compressing digital video, described in Background Information on MPEG-1 and MPEG-2 Television Compression, which could be found in November 1996 at the URL http://www. cdrevolution. com/text/mpeginfo. htm. All of these techniques take advantage of the fact that a sequence of digital pictures contains a great deal of redundant information. One type of redundancy is spatial: in any picture, pixels that are spatially close to each other tend to have similar characteristics. Since that is the case, it is often possible to describe a picture as a set of regions of spatially-adjacent pixels. Regions may of course overlap. Where the regions are rectangular, they are referred to as blocks. Where a given area of the picture strongly resembles another area of the picture but is not identical to the other area, it is possible to replace the pixels in the given area with a representation that describes the given area in terms of the difference between it and the given area.
The other type of redundancy in a sequence of pictures is temporal; very often, a given picture in the sequence is very similar in appearance to an earlier or later picture in the sequence; it is consequently possible to compress the given picture by making a representation of the given picture that represents the differences between regions in the given picture and regions in an earlier or later picture, termed herein the reference picture, and using this representation in place of the representation as an array of pixels.
One way of expressing the difference between the given picture and the reference picture is shown in FIG.
1
. Digital reference picture
101
is represented in memory as an array of pixels
105
. The picture is further divided into blocks
103
, each of which is typically 16 pixels square. An object
107
in reference picture
101
is contained in four adjacent blocks
103
: blocks
103
(m,n), (m+1,n), (m,n+1), and (m+1,n+1), where m and n denote the x and y coordinates of the upper left-hand corner of the block. In given picture
109
, object
107
is in a different position, namely blocks
103
(b,s), (b+1,s), (b,s+1), and (b+1,s+1), but object
107
otherwise has substantially the same appearance as in reference picture
101
. Since that is the case, object
107
can be described in the compressed representation of given picture
109
in terms of its differences from object
107
in reference image
101
. There are two kinds of differences:
the change of location of object
107
in given picture
109
; and
any change of appearance of object
107
in given picture
109
.
The first kind of difference can be described in terms of an offset of object
107
in picture
109
from its position in reference picture
101
. The second kind can be described in terms of the difference between the appearance of object
107
in picture
109
and the appearance of object
107
in reference picture
101
. The changed appearance can be caused by factors such as varied illumination incident on object
107
or warping or shearing of the object due to rotation about the x axis, the y axis, or the z axis perpendicular to the plane of the picture.
The use of compression techniques such as the ones just described permit the creation of compressed representations of sequences of digital pictures which are small enough to satisfy the bandwidth and memory constraints typical of commercial digital television, digital teleconferencing, and digital videotelephony. The production of a compressed representation of a digital picture from a pixel representation of the digital picture is termed herein encoding the picture.
In hybrid video coding methods, temporal redundancies are typically removed by predicting block data in the picture that is undergoing encoding (i.e., the current picture) from the data in one or more reference pictures. At the point in time that an encoder engine (that is, encoding software or microcode executing on a processor) is compressing the current picture, such reference pictures have already been compressed and possibly transmitted. However, since those pictures are destined to be used as reference pictures for the compression of subsequent pictures, while the encoder engine is compressing such reference pictures, it reconstructs and retains them in memory so that it can later retrieve them and use them as reference pictures. By reconstructing the compressed reference pictures in memory, the encoder engine simulates a decoder engine that is able to decode pictures encoded by the encoder engine. This is because a decoder engine would be part of a receiver for the digital pictures and would not have access to the original pictures but only to their reconstructed versions that inherently exhibit signal loss (i.e., degradation) as a result of compression.
Motion Estimation and Block Matching Criteria
Since a video signal can exhibit high motion, exploitation of the temporal redundancy is best achieved by using motion estimation/compensation techniques to allow blocks of the same size at different spatial offsets in the reference picture(s) to predict the block's data in the current picture. Although not optimal, for practical reason
Patel Neilesh R.
Rodriguez Arturo A.
Simerly Timothy W.
Gardner Kelly A.
Kelley Chris S.
Massaroni Kenneth M.
Scientific-Atlanta, Inc.
West John Eric
LandOfFree
Motion estimation system and methods does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Motion estimation system and methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Motion estimation system and methods will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2597369