Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2001-02-28
2003-12-23
Rao, Andy (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240170
Reexamination Certificate
active
06668020
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates in general to a method for motion estimation in video coding, and more particularly to a block-matching motion estimation method for motion compensated video coding.
2. Description of the Related Art
In conventional motion compensated video coding, when a current frame is to be processed, it involves computation of a motion vector by using a previous frame or a reference frame and then the current frame is processed. The motion vector is produced by a motion estimation technique. Among motion estimation techniques, a block matching motion estimation technique is frequently used, wherein the smallest estimation unit is a block of a frame.
Referring to
FIG. 1
, it illustrates a conventional motion compensated video coding. In
FIG. 1
, block
104
of frame
102
is coded as follows. First, it needs to determine a block, such as block
108
, which matches block
104
best and makes less difference to block
104
, by using a block matching motion estimation technique with a previous frame
106
. Then, a motion vector is obtained by computing the difference in coordinates between the pixels of block
104
in frame
102
and the pixels of block
108
in frame
106
. Next, this motion vector and the difference in image information between block
104
and block
108
are coded. In this way, for transmitting the image data of frame
102
, the data encoded by the technique above are actually transmitted and significantly reduced in quantity as compared with other technique in which block
104
is required to be coded entirely.
A conventional block matching motion estimation technique is the fill search technique. By the full search technique, a complete test is performed, resulting in the best-matching block for a current frame. Referring to
FIG. 2
, it illustrates the conventional full search motion estimation technique. When block
104
is to be coded, the method for searching the best-matching block in the previous frame
106
by using the full search technique is as follows.
First, determine search region
202
corresponding to frame
106
, where the size of search region
202
can be determined according to the characteristics of the image data of frames
102
and
106
. In search region
202
, there are M by M checking points, each of which corresponds to a block of frame
106
. For example, referring to
FIG. 2B
, it illustrates the relationship between checking points and their respective blocks. In
FIG. 2B
, checking points C, C
1
, and C
2
correspond to blocks
204
,
206
, and
208
of the previous frame
106
respectively. If checking point C moves right and upward by one pixel, it becomes checking point C
1
. In this way, when the region indicated by block
204
is shifted right and upward by one pixel, it results in the region indicated by block
206
.
Secondly, computation of the differences in image information of all pixels between the blocks corresponding to all checking points and block
104
of the current frame
102
is performed.
Next, a block match error is determined by summing the absolute values of the differences in image information for one block.
Then, it is to determine the block corresponding to the minimum block match error by using the block match errors determined, wherein the block determined to have the minimum block match error is the best-matching block in the previous frame
106
, such as block
108
in this example.
After that, a motion vector for block
104
is obtained by the checking point that corresponds to the best-matching block in the previous frame
106
, block
108
.
In the full search motion estimation technique, checking points are consecutively determined in a search region so that the arrangement of the blocks corresponding to the checking points is in consecutive order and two consecutive blocks overlap. In this way, when performing a full search for a best-matching block, many image data may be reused. Referring to
FIG. 2C
, it illustrates image data reuse when performing a full search. In
FIG. 2C
, three consecutive checking points in a row correspond to blocks
210
,
212
, and
214
. During performing computation on each pixel of block
212
, it only needs to load the image data of block
212
which correspond to the portion that does not overlap block
210
. Similarly, during performing computation on each pixel of block
214
, it is only required loading the image data of block
214
which correspond to the portion that does not overlap block
212
. Consequently, a small amount of data is loaded in computation for each block. By hardware design, the function of data reuse can be achieved. In this way, most media processors for performing video coding generally support speed-up hardware to improve the performance when performing full search motion estimation.
However, the full search motion estimation technique involves a huge amount of complex computation. It consumes time to perform and thus the performance is low. Therefore, for a better performance, many block matching motion estimation techniques have been developed. Referring to
FIG. 3
, it illustrates one block matching motion estimation technique called three step search (TSS) technique. First, nine checking points are taken, wherein eight of them form an 8×8 pixels square, such as square
302
, with the remaining checking point, such as checking point P, as the square's center point. Then, the block match errors for the blocks corresponding to all checking point of square
302
are calculated, and from the checking points taken from square
302
, the checking point corresponding to the minimum block match error calculated can be determined, such as checking point P
1
in square
302
. Next, from a 4-by-4-pixel square, such as square
304
, with checking point P
1
as its center point, eight checking points are taken and the checking point corresponding to the minimum block match error can be determined, such as checking point P
2
. Finally, from the eight checking points adjacent to checking point P
2
, the checking point that corresponds to the block with the minimum block match error is determined, such as checking point P
3
. In this way, a motion vector can be determined by using checking point P
3
.
In the three step search technique, the number of checking points employed in the process of determination of a motion vector is less than the full search technique so that the amount of computation in the three step search technique does as well. However, performance of the three step search technique is not completely accepted. By the three step search technique, the point check for obtaining the motion vector is determined through only three steps, it is probably that the checking point corresponding to the best-matching block cannot be found. Besides, as can be seen from the example above, the distribution of the checking points is non-uniform. Thus, it cannot be benefited from the hardware's speed-up, as the full search technique does, to speed up the processing rate.
In addition, another block matching motion estimation technique, called diamond search technique, has been widely used. Referring to
FIG. 4
, it illustrates the conventional diamond search technique. First, nine checking points are taken, wherein eight of them form a rhombus, such as rhombus
402
, with the remaining checking point such as D, as the rhombus's center point and the diagonals of the rhombus are of four pixels length. Second, the block match errors corresponding to all checking points taken from rhombus
402
are calculated and checking point D
1
is determined as the checking point corresponding to the minimum block match error. Since checking point D
1
is not the center point D
1
rhombus
402
, eight checking points are taken from rhombus
404
with checking point D
1
as the center point and with diagonals of four pixels length and, from the eight checking points from rhombus
404
, checking point D
2
is determined as the checking point corresponding to the minimum block match
Ma Shyh-Yih
Shen Chun-Fu
Rabin & Berdo P.C.
Rao Andy
Vivotek Inc.
LandOfFree
Method for motion estimation in video coding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for motion estimation in video coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for motion estimation in video coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3183417