Image analysis – Image compression or coding – Interframe coding
Reexamination Certificate
1999-09-29
2002-07-16
Moore, David (Department: 2624)
Image analysis
Image compression or coding
Interframe coding
C382S232000, C382S240000, C375S240110, C375S240170
Reexamination Certificate
active
06421466
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to digital-video compression, and more particularly to motion estimation for video compression.
BACKGROUND OF THE INVENTION
Digital video is the format commonly used with personal computers, digital-video cameras, and other electronic systems. Since a huge amount of memory or storage space is required to fully store all 30 or more frames per second of video, the images are usually compressed. Often sequential images in the video sequence differ only slightly. The difference from a previous (or following) image in the sequence can be detected and encoded, rather than the entire picture. Such lossy compression techniques are widely used, such as MPEG encoding.
During compression or encoding, each frame or image is divided into a grid of macroblocks. Each macroblock contains 16×16 pixels. A macroblock from a current frame or picture is compared to a range of macroblocks in a previous picture in the video sequence. Often a match or near-match is found at a different location. The difference in locations is known as a motion vector, since it indicates the movement of the macroblock between the two pictures. The motion vector rather than the entire macroblock can then be encoded for the new picture, saving storage space.
FIG. 1
illustrates motion estimation for a pair of digital-video pictures. A current picture
10
is compared to an old picture
12
in a video sequence. Old picture
10
could occur either before or after current picture
10
in the sequence when backward and forward estimation are used.
Macroblock
16
in current picture
10
is selected and compare to all macroblocks within search range
14
in old picture
12
. A match or near-match is found with macroblock
16
′. because of movement of subjects in the pictures, macroblock
16
′ from old picture
12
has moved to a new location in current picture
10
. The difference in locations of macroblocks
16
,
16
′ is indicated by motion vector
18
.
Rather than store all 16×16 pixels of macroblock
16
in the encoded video stream, only motion vector
18
and an identifier for macroblock
16
′ need to be included. This reduces or compresses the size of the video stream.
Although the video stream is compressed, large number of calculations are needed for motion estimation. The various macroblocks within a search range are usually evaluated by a sum of the absolute difference (SAD) method. The macroblock
16
′ with the smallest SAD is the closest match to the macroblock
16
being searched.
For a search range of +/−127 and +/−63 pixels, a total of 32K macroblocks are evaluated, requiring 32K SAD operations. Each SAD operation requires 256 (16×16) subtractions, 256 absolute-value operations, and 255 2-input additions, a total of 767 arithmetic operations. A full search for one macroblock thus requires 32K×767 or about 24M calculations.
A 720×480-pixel picture has 1350 macroblocks, each of which may move independently and thus must be motion-estimated. So a total of 1350×24M or 32 G calculations are needed per picture. For a video having 30 frames per second, about 1 trillion operations per second are needed (1 T ops/sec). Thus full motion estimation requires large computing resources.
Hierarchical Motion Estimation—
FIG. 2
Computing requirements can be reduced by using a pyramid or hierarchical motion-estimation search. Pixels are averaged together to reduce the number of pixels in the picture, so that smaller search ranges and smaller macroblocks are used. This reduces the number of calculations.
FIG. 2
shows pyramid motion estimation. The term “pyramid” is used since successively smaller pictures are used for motion estimation searches. These smaller pictures are at higher levels of the “pyramid”. For example, picture
22
represents the full-size picture of 720×480 pixels. The next level (level-
2
) of the pyramid is a reduced-size picture having only 360×240 pixels, about ¼ the size of full picture
22
. Level-
2
picture
24
is generated from full-size picture
22
by averaging each 2×2 square of 4 pixels into a single pixel. The top of the pyramid is level-
3
picture
26
, which is created by 2×2 averaging of level-
2
picture
24
. Level-
3
picture
26
has 180×120 pixels, only {fraction (1/16)}
th
of full-size picture
22
.
The macroblock size also becomes smaller with each higher level of the pyramid. For example, the 16×16 macroblock
20
of full picture
22
is reduced to an 8×8 macroblock in level-
2
24
, and reduced further to a 4×4 macroblock in level-
3
26
. The image
20
′ in the selected macroblock from the old picture also becomes smaller with each higher level.
The search ranges are also reduced from +/−127, 63 to +/−63, 31 in level-
2
, and to +/−31, 15 in level-
3
. The smaller search ranges and the smaller macroblocks in higher levels require fewer arithmetic operations during a search within a higher level picture. For example, a search of the +/−31, 15 range of level-
3
requires comparison of a 4×4 macroblock. Each SAD operation of a 4×4 macroblock requires 16 subtractions, 16 absolute-value operations, and 15 2-input adds, a total of only 47 operations (rather than 767). Only 63×31 (1953) SAD operations are required for the reduced search range at level-
3
. Thus a total of about 91K operations are needed for the level-
3
search.
Multi-Level Search—
FIG. 3
FIG. 3
shows multiple levels of motion-estimation search. A full-resolution picture
22
of a current frame is compared to a full-resolution picture
22
′ of a prior (old) frame using multi-level searching.
The full picture
22
is reduced by 2×2 pixel averaging by reducer
32
to produce level-
2
picture
24
, which is one-quarter the size of full picture
22
. This level-
2
picture
24
is again reduced by 2×2 pixel averaging by reducer
33
to produce level-
3
picture
26
. Level-
3
picture
26
is one-sixteenth the size of full picture
22
.
Similar pixel-averaging operations occurred when the old picture was being processed, and the full, quarter, and sixteenth-size pictures
22
′,
24
′,
26
′ were saved.
First, a coarse motion estimation search is performed at the top level by motion estimator
38
. Motion estimator
38
selects a 4×4 macroblock in current level-
3
picture
26
and compares it to all 4×4 pixel groupings in the search range of level-
3
old picture
26
′. The best four matches are sent to the next lower level, to motion estimator
36
. The best four matches rather than the single-best match are sent to improve accuracy, allowing for averaging distortions. Rather than 4, the best n matches, where n is typically between 2 and 4, can be sent to the next lower level.
Motion estimator
36
then compares the selected macroblock for level-
2
pictures
24
,
24
′. Rather than search over the entire search range, only the four best-match macroblocks for the level-
3
search and their nearest neighbors are compared. Thus a search range of only 9 macroblocks for each of the 4 best-fit vectors from level-
3
are compared. A total of 9×4 or 36 macroblocks are compared by level-
2
motion estimator
36
. Less than 7K operations are required by level-
2
motion estimator
36
per selected macroblock.
Finally, the best 4 motion vectors from level-
2
motion estimator
36
are sent to level-
1
motion estimator
34
. Motion estimator
34
then compares each of the four best-match macroblocks and their 8 surrounding neighbors, or 9×4 macroblocks. These are 16×16 macroblocks, so a total of 27K operations are required by level-
1
motion estimator
34
. The motion vector for the best-fit macroblock is then output as the motion vector for that selected macroblock. Then the motion estimation can continue for other selected macroblocks in the current picture until all macroblocks have been processed.
Th
Auvinen Stuart T.
Do Anh Hong
Moore David
NeoMagic Corp.
LandOfFree
Hierarchical motion estimation with levels of varying bit... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hierarchical motion estimation with levels of varying bit..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical motion estimation with levels of varying bit... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2901164