Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2001-01-29
2004-02-10
Le, Vu (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C348S699000
Reexamination Certificate
active
06690730
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a motion estimator, and more particularly, to a motion estimator capable of performing fast motion estimation during compression of a moving picture. The present application is based on Korean Patent Application No. 00-4049, which is incorporated herein by reference.
2. Description of the Related Art
Motion estimation is used for increasing compression efficiency by removing temporal redundancy of input video data in a video coder. General standards for compressing a moving picture are mostly based on block-based coders. Such block-based coders use a block matching algorithm. The block matching algorithm performs block-based motion estimation. According to the block matching algorithm, a block most similar to a certain block in a current frame is selected from candidate blocks positioned within a search area of a previous frame. Here, the relative local difference between the block to be processed in the current frame and the most similar candidate block in the previous frame is referred to as a motion vector (MV). Generally, the sum of absolute differences (SAD) is calculated for motion estimation. When motion estimation is performed in 16×16 block units, the SAD and the MV are calculated by Equation (1) and Equation (2), respectively.
SAD
(
u
,
v
)
=
∑
i
=
0
15
∑
j
=
0
15
&LeftBracketingBar;
C
(
i
,
j
)
-
P
(
i
+
u
,
j
+
v
)
&RightBracketingBar;
(
1
)
MV=arg
(u,v)
min
SAD
(
u,v
) (2)
Here, c(i,j) is block data of a current frame, P(i+u,j+v) is candidate block data of a previous frame, and (u,v) is a motion vector candidate.
When a motion estimator is actually designed based on such calculation, the performance and the amount of operation of motion estimation should be considered. For motion estimation, most of the amount of operation is for calculation of the SAD. In other words, subtraction, calculation of an absolute value and a cumulative operation should be performed to calculate the single SAD. In particular, the amount of such calculation is proportional to the size of a block to be processed. According to a conventional motion estimation method, it takes much time to estimate motion because the amount of operation is large.
To solve this problem, a hierarchical motion estimation method has been proposed.
FIG. 1
is a diagram illustrating this hierarchical motion estimation method. According to the hierarchical motion estimation method illustrated in
FIG. 1
, an image of a lower layer is subsampled, thereby generating a subsampled image of a middle layer and a subsampled image of an upper layer. Next, the SAD is calculated with respect to the subsampled image of the upper layer to select initial search area candidates from the image of the middle layer. Then, more search area candidates are selected from the image of the middle layer using the interrelation between peripheral macro blocks. The SADs are calculated with respect to the selected initial search area candidates, and a final MV at a position having a minimum SAD is obtained for the image of the lower layer.
Such a method does not decrease the performance and achieves fast processing compared to a full search method. However, faster motion estimation is still desired.
SUMMARY OF THE INVENTION
To solve the above problems, it is an object of the present invention to provide a motion estimator for performing fast motion estimation.
Accordingly, to achieve the above object of the invention, there is provided a motion estimator for performing motion estimation to compress an image data frame. The motion estimator includes a first memory comprising a previous search area memory having a plurality of memory areas for storing previous search area data by lines and a current process area memory for storing current process area data by lines; a previous search area data provider for shifting and outputting the previous search area data output from the plurality of memory areas in circles; a first switching part for selecting the previous search area data output from the previous search area data provider; a second switching part for selecting the current process area data output from the current process area memory by rows; a calculator comprising a plurality of sum of absolute differences (SAD) calculators connected in parallel, the plurality of SAD calculators calculating SADs of the selected previous process area data and the current process area data; and a shift register for receiving and shifting SAD data output from a series of SAD calculators of the calculator and adding the shifted data and SAD data output from another series of SAD calculators, thereby outputting a partial SAD.
It is preferable that when the size of a search area is set to p, the calculator includes p SAD calculators connected in parallel, and the shift register includes 2p+1 shift registers.
The motion estimator preferably further includes a buffer for buffering input data; a 25-shift register for 25-shifting data output from the buffer; an adder for adding the partial SAD and data output from the 25-shift register, thereby outputting a SAD; a SAD comparison and motion vector generation unit for generating a motion vector using the SAD output from the adder; and a 20-shift register for 20-shifting the motion vector and outputting the result to the SAD comparison and motion vector generation unit.
Preferably, the motion estimator further includes a 22-shift register for performing a 22-shifting operation to additionally obtain an initial search point using the interrelation between motion vectors of peripheral macro blocks in a middle layer, when hierarchical motion estimation using 3 layers is performed.
The motion estimator preferably further includes a DMA controller for controlling the current process area data and the previous search area data to be separately stored in the first memory and for providing data to the calculator depending on the process of a motion estimation controller; the motion estimation controller for controlling motion estimation in response to a control signal output from the DMA controller; and a second memory for storing the calculated partial SAD.
The first memory is divided into the previous search area memory having three areas and the current process area memory, the calculator comprises first, second, third and fourth SAD calculators for calculating SADs using the previous search area data and the current process area data. The shift register includes a first 9-shift register for 9-shifting and outputting SAD data output from the first SAD calculator; a first adder for adding output data from the first 9-shift register and output data from the second SAD calculator; a second 9-shift register for 9-shifting and outputting SAD data output from the second SAD calculator; a second adder for adding output data from the second 9-shift register and output data from the third SAD calculator; a third 9-shift register for 9-shifting and outputting SAD data output from the third SAD calculator; and a third adder for adding output data from the third 9-shift register and output data from the fourth SAD calculator.
Preferably, each of the first through fourth SAD calculators comprises registers and subtracters, one input port of each of the subtracters being connected to the output port of a respective register, and the other input port of each of the subtracters being connected to a respective switch.
Preferably, the motion estimator further includes an interpolator for performing interpolation on the previous search area data and outputting the resulting data of the interpolation.
The motion estimator further includes a DMA controller for discriminating between the previous search area data and the current process area data and controlling data to be provided to the previous search area data provider and the calculator depending on a processing state.
REFERENCES:
patent: 5706059 (1998-01-01), Ran et al.
patent: 6118901 (2000-09-01), Chen et al.
patent
Le Vu
Samsung Electronics Co,. Ltd.
Sughrue & Mion, PLLC
LandOfFree
Motion estimator 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 estimator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Motion estimator will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3311703