Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2001-04-24
2004-11-02
Vo, Tung T. (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06813315
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to digital video encoding, such as MPEG and AVI. More specifically, the present invention relates to methods of motion estimation for encoding digital images of a digital video stream.
2. Discussion of Related Art
Due to the advancement of semiconductor processing technology, integrated circuits (ICs) have greatly increased in functionality and complexity. With increasing processing and memory capabilities, many formerly analog tasks are being performed digitally. For example, images, audio and even full motion video can now be produced, distributed, and used in digital formats.
FIG.
1
(
a
) is an illustrative diagram of a digital video stream
100
. Digital video stream
100
comprises a series of individual digital images
100
_
0
to
100
_N, each digital image of a video stream is often called a frame. For full motion video a video frame rate of 60 images per second is desired. As illustrated in FIG.
1
(
b
), a digital image
100
_Z comprises a plurality of picture elements (pixels). Specifically, digital image
100
_Z comprises Y rows of X pixels. For clarity, pixels in a digital image are identified using a 2-dimensional coordinate system. As shown in FIG.
1
(
b
), pixel P(0,0) is in the top left corner of digital image
100
_Z. Pixel P(X−1,0) is in the top right corner of digital image
100
_Z. Pixel P(0,Y−1) is in the bottom left corner and pixel P(X−1, Y−1) is in the bottom right corner. Typical image sizes for digital video streams include 720×480, 640×480, 320×240 and 160×120.
FIG. 2
shows a typical digital video system
200
, which includes a video capture device
210
, a video encoder
220
, a video channel
225
, a video decoder
230
, a video display
240
, and an optional video storage system
250
. Video capture device
210
, typically a video camera, provides a video stream to video encoder
220
. Video encoder
220
digitizes and encodes the video stream and sends the encoded digital video stream over channel
225
to video decoder
230
. Video decoder
230
decodes the encoded video stream from channel
225
and displays the video images on video display
240
. Channel
225
could be for example, a local area network, the internet, telephone lines with modems, or any other communication connections. Video decoder
230
could also receive a video data stream from video storage system
250
. Video storage system
250
can be for example, a video compact disk system, a hard disk storing video data, or a digital video disk system.
A major problem with digital video system
200
is that channel
225
is typically limited in bandwidth. As explained above a full-motion digital video stream can comprise 60 images a second. Using an image size of 640×480, a full motion video stream would have 18.4 million pixels per second. In a full color video stream each pixel comprises three bytes of color data. Thus, a full motion video stream would require a transfer rate in excess of 52 megabytes a second over channel
225
. For internet application most users can only support a bandwidth of approximately 56 Kilobits per second. Thus, to facilitate digital video over computer networks, such as the internet, digital video streams must be compressed.
One way to reduce the bandwidth requirement of a digital video stream is to avoid sending redundant information across channel
225
. For example, as shown in
FIG. 3
, a digital video stream includes digital image
301
and
302
. Digital image
301
includes a video object
310
_
1
and video object
340
_
1
on a blank background. Digital image
302
includes a video object
310
_
2
, which is the same as video object
310
_
1
, and a video object
340
_
2
, which is the same as video object
340
_
1
. Rather then sending data for all the pixels of digital image
301
and digital image
302
, a digital video stream could be encoded to simply send the information that video object
310
_
1
from digital image
301
has moved three pixels to the left and two pixels down and that video object
340
_
1
from digital image
301
has moved one pixel down and four pixels to the left. Thus rather than sending all the pixels of image
302
across channel
225
, video encoder
220
can send digital image
301
and the movement information, usually encoded as a two dimensional motion vector, regarding the objects in digital image
301
to video decoder
230
. Video decoder
230
can then generate digital image
302
using digital image
301
and the motion vectors supplied by video encoder
220
. Similarly, additional digital images in the digital video stream containing digital images
301
and
302
can be generated from additional motion vectors.
However, most full motion video streams do not contain simple objects such as video objects
310
_
1
and
340
_
1
. Object recognition in real life images is a very complicated and time-consuming process. Thus, motion vectors based on video objects are not really suitable for encoding digital video data streams. However, it is possible to use motion vector encoding with artificial video objects. Rather than finding distinct objects in a digital image, the digital image is divided into a plurality of macroblocks. A macroblock is a number of adjacent pixels with a predetermined shape and size. Typically, a rectangular shape is used so that a rectangular digital image can be divided into an integer number of macroblocks.
FIG. 4
illustrates a digital image
410
that is divided into a plurality of square macroblocks. For clarity, macroblocks are identified using a 2-dimensional coordinate system. As shown in
FIG. 4
, macroblock MB(0,0) is in the top left corner of digital image
410
. Macroblock MB(X−1,0) is in the top right corner of digital image
410
. Macroblock MB(0,Y−1) is in the bottom left corner and macroblock MB(X−1, Y−1) is in the bottom right corner. As illustrated in FIG.
5
(
a
), a typical size for a macroblock
510
is eight pixels by eight pixels. As illustrated in FIG.
5
(
b
), another typical size for a macroblock is 16 pixels by 16 pixels. For convenience, macroblocks and digital images are illustrated with bold lines after every four pixels in both the vertical and horizontal direction. These bold lines are for the convenience only and have no bearing on actual implementation of embodiments of the present invention.
To encode a digital image using macroblocks and motion vectors, each macroblock MB(x, y) of a digital image is compared with the preceding digital image to determine which area of the preceding image best matches macroblock MB(x, y). For convenience, the area of the preceding image best matching a macroblock is called an origin block OB. Typically, an origin block has the same size and shape as the macroblock. To determine the best matching origin block, a difference measure is used to measure the amount of difference between the macroblock and each possible origin block. Typically, a value such as the luminance of each pixel in the macroblock is compared to the luminance of a corresponding pixel in the origin block. The sum of absolute differences (SAD) of all the values (such as luminance) is the difference measure. Other embodiments of the present invention may use other difference measures. For example, one embodiment of the present invention uses the sum of square differences as the difference measures. For clarity, only SAD is described in detail, those skilled in the art can easily adapt other difference measures for use with different embodiments of the present invention. The lower the difference measure the better the match between the origin block and the macroblock.
The motion vector for macroblock MB(x, y) is simply the two-dimensional vector which defines the difference in location of a reference pixel on the origin block with a corresponding reference pixel on the macroblock. For convenience, the reference pixel in the examples contained herein uses the top left pixel of the macroblo
Auyeung Cheung
Chen Sho Long
Siu Stanley H.
Bever Hoffman & Harms LLP
Mao Edward S.
Vweb Corporation
LandOfFree
Motion estimation using multiple search windows 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 using multiple search windows, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Motion estimation using multiple search windows will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3294181