Pulse or digital communications – Bandwidth reduction or expansion
Reexamination Certificate
1999-03-01
2002-04-23
Rao, Andy (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
C375S240160
Reexamination Certificate
active
06377623
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a super high-speed motion estimating method for real time moving image coding. More particularly, the invention relates to a motion estimating method for reducing the complexity of calculating a motion vector by lowering the resolution for motion picture coding and determining a plurality of motion vector candidates under the lowered resolution. The motion vector candidates may be determined by using motion vector correlation of neighborhood blocks. After the candidates are determined, search areas are selected having a plurality of motion vector as centers, and a final motion vector is calculated based on the search areas. Also, an apparatus for performing the method is provided.
2. Description of the Related Art
Motion compensation coding for removing a temporal duplication of a moving image is used in order to obtain a high data compression rate. Such coding plays an important role in International Video Coding Standards such as the MPEG-1, 2, and 4 Standards or the H-263 Standard.
The motion compensation coding predicts an image that is the most similar to a received image based on information of a previous frame of the image. Specifically, motion compensation coding uses motion estimation and conversion codes and obtains a subtraction image by subtracting an estimated image from the received image. The subtraction image is processed and encoded so that it represents a compressed version of the moving image.
A general apparatus that employs moving image coding is shown in FIG.
1
.
As shown in the figure, the apparatus includes a frame memory
102
, motion estimators
104
and
106
, a motion compensator
108
, a subtracter
110
, a discrete cosine transformer
112
, a quantizer
114
, an inverse quantizer
116
, an inverse discrete cosine transformer
118
, an adder
120
, a frame delay
122
, a forward analysis and coding rate controller
124
, a variable length encoder
126
, and a buffer
128
.
A received image is input in units of a frame and is stored in the frame memory
102
. Then, the image frame is output to the first motion estimator
104
is which calculates a first motion vector based on the image, and the motion vector has units of an integer number of pixels. The second motion estimator
106
calculates a second motion vector based using the first motion vector generated by the first motion estimator
104
, the image frame received from the frame memory
102
, and information of a previous frame of the image received from the frame delay
122
. The second motion vector has units of a half-pixel.
The motion compensator
108
inputs the motion vector from the second motion estimator
106
and the information of the previous frame from the frame delay
122
, performs a motion compensation operation based on such inputs, and outputs an estimated image frame with respect to a current frame of the image. The subtracter
110
inputs the current image frame from the frame memory
102
and the estimated image frame from the motion compensator
108
and subtracts the estimated image frame from the current image frame to produce a subtracted image frame. As a result, the subtracted image frame is frame in which the temporal duplication of the moving image is removed.
The above motion estimating and compensating processes are performed in units of a 16×16 block, and such a block is generally referred to as a macro block. After the subtraction image is generated, it output to the discrete cosine transformer
112
and subjected to a discrete cosine transformation. Then, the image is output to the quantizer
114
and quantized. As a result, any remaining spatial duplication of the subtraction image is removed. The motion vectors and the quantized subtraction image are encoded by the variable length encoder
126
and are transferred in a bit stream pattern through the buffer
128
.
The quantized subtraction image is also interpolated and restored by the inverse quantizer
116
and the inverse discrete cosine transformer
118
. The restored image is added to the estimated image generated by the motion compensator
108
via the adder
120
and the resultant signal is stored in the frame delay
122
and delayed by one frame. The image stored in the frame delay
122
corresponds to the previous image frame of an image that immediately precedes the current image frame output by the frame memory
102
. The previous image frame stored in the frame delay
122
is output to the second motion estimator
106
and the motion compensator
108
as described above.
The forward analysis and coding rate controller
124
inputs the current image frame from the frame memory
102
and controls the coding rate of the variable length coder
126
.
Currently, a method for estimating and compensating the motion of a moving image in units of a frame and a method for estimating and compensating the motion of a moving image in units of a field are known to those skilled in the art. Therefore, a description of such methods is omitted in the present specification for the sake of brevity.
One conventional method for estimating motion is called a full-scale block matching analysis (“FSBMA”). In such analysis, a two-dimensional motion vector of each block is estimated by dividing a current frame into blocks having a uniform size. Then, the respective blocks are compared with all the blocks in a search region of a reference frame according to a given matching standard, and the position of an optimal matching block is determined. A mean absolute difference (“MAD”) is a relatively simple calculation and is used as a matching standard for determining the optimal matching block in such a conventional block matching method. The MAD is calculated using Equation 1.
MAD
(
i
,
j
)
=
1
N
2
∑
k
=
1
N
∑
l
=
1
N
&LeftBracketingBar;
f
t
(
k
,
l
)
-
f
t
-
1
(
k
+
i
,
l
+
j
)
&RightBracketingBar;
(
1
)
wherein, f
t
(k,l) is the brightness value of a pixel in a position (k, l) of the current frame, and f
t−1
(k+i,l+j) is the brightness value of a pixel in a position offset from the position (k, l) by a distance (i, j).
In such a block matching method, the maximum motion estimation scope is determined by considering the motion of real images when the coding is performed. The FSBMA estimates the motion vector by comparing all the blocks in the motion estimation scope with current blocks and has the highest performance considering an estimated gain. However, an excessive amount of calculation is required to perform the FSBMA. For example, when the maximum movement displacement in a frame is ±p (a pulse/a frame) with respect to a block having a size of M×N, the size of the search region is (M+2p)×(N+2p) in a reference frame. Since the number of candidate blocks to be compared with all of the blocks in the region is (2p+1)
2
, it becomes more difficult to accurately perform real time moving image encoding as p becomes larger.
Another conventional method for solving such a problem is provided in “A Fast Hierarchical Motion Vector Estimation Algorithm Using Mean Pyramid”, K. M. Nam, J. S. Kim, R. H. Park, Y. S. Shim, IEEE Trans. of Circuits & Systems for Video Technology, 1995, 5, (4), pp. 344-351 and “Accuracy Improvement And Cost Reduction of 3-step Search Region Matching Algorithm for Video Coding”, IEEE Trans. Circuits & Systems for Video Technology, 1994, 4, (1), pp. 88-90. In the above documents, high-speed hierarchical search methods that use a plurality of candidates and that can replace the FSBMA are described.
Such methods of using a plurality of candidates can solve the problem of a local minimum value which occurs due to a hierarchical search. However, a large amount of calculation is still required in order to achieve a performance comparable to the performance of the FSBMA. Also, since the methods are based on a three-step hierarchical searching method, they are not suitable for estimating a motion in a wide searc
Choi Geon-young
Lim Kyoung-won
Ra Jong-beom
Rao Andy
Samsung Electronics Co,. Ltd.
Sughrue & Mion, PLLC
LandOfFree
High speed motion estimating method for real time moving... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High speed motion estimating method for real time moving..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed motion estimating method for real time moving... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2874407