Device for and method of estimating motion in video encoder

• US 20040114688A1
• Filed: 12/08/2003
• Published: 06/17/2004
• Est. Priority Date: 12/09/2002
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kang, Jung-Sun
• Granted Patent: US 7,362,808 B2
• Time in Patent Office: Days
• US Class Current: 375/240.12
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation

Abstract

A motion estimator and an estimation method for a video encoder to reduce power consumption by reducing the computational complexity of the motion estimator. In an upper step, a full search for a ±4 pixel search region for a 4×4 pixel block is performed at ¼ video resolution, to detect two motion vector candidates. In a medium step, a partial search for two vector candidates selected in the upper step and one vector candidate using a spatial correlation is performed for a 8×8 block within a ±1 or ±2 search region, to decide one motion vector candidate. In a lower step, a partial search for the ±1 or ±2 search region on 16×16 block is performed at full resolution, and a half pixel search for a motion vector candidate obtained in the lower step is performed to estimate a final motion vector. A ±4 pixel search region is operatively divided into four search regions, and the estimator sequentially searches the four ±2 pixel search regions to sequentially output SAD values.

Claims

1. A motion estimator of a video encoder, comprising:

a search region data memory for storing video data of a previous video frame;

a macroblock data memory for storing macroblock data of a current video frame;

a first sub sampling circuit for sub-sampling by ratio M;

1 the video data of a previous frame read from the search region data memory in response to a sub-sampling rate control signal;

a data array circuit for arraying video data outputted from the first sub-sampling circuit so that motion vector estimation candidates can be outputted sequentially a second sub-sampling circuit for sub-sampling, by ratio M;

1, current video frame data read from the macroblock data memory in response to the sub-sampling rate control signal;

a search region deciding circuit for outputting a search region decision signal;

a processing element (PE) array network for sequentially calculating a SAD (sum of absolute differences) value of the data outputted from the first sub-sampling circuit and the search region data outputted from the data array circuit, according to a designation of the search region decided by the search region deciding circuit, to sequentially output a plurality of SAD values;

a motion vector comparator for receiving the plurality of SAD (sum of the absolute differences) values sequentially outputted from the PE array network, and comparing the SAD value with a previous SAD value, to detect a minimum SAD value as a motion vector value.

2. The motion estimator as claimed in 1, further comprising:

a macroblock measure circuit for receiving the current frame video data read from the macroblock data memory to calculate the sum of absolute differences between a mean intensity of a macroblock and an intensity of each pixel of the macroblock; and

wherein

the search region deciding circuit is adapted to output the search region decision signal based upon the sum (A) of absolute differences between a mean intensity of a macroblock and the intensity of each pixel of the macroblock as calculated by the macroblock measure circuit.

3. The motion estimator as claimed in 2, further comprising a comparator for selecting an intermode or an intramode based upon a comparison of the sum (A) of the absolute differences between the mean intensity of the macroblock and the intensity of each pixel of the macroblock, with a predetermined threshold value.

4. The estimator as claimed in 2, further comprising:

a controller for generating a sub-sampling rate control signal per each of upper, medium and lower steps to obtain a motion estimation, and an address to read and write the macroblock data and the search region data, and for receiving a motion vector value detected per each of the upper, medium and lower steps to output a motion estimation candidate designation signal;

wherein the sub-sampling rate control signal of the upper step is a signal causing a 4;

1 sub-sampling ratio.

5. The estimator as claimed in 2, further comprising:

a controller for generating a sub-sampling rate control signal per each of upper, medium and lower steps to obtain a motion estimation, and an address to read and write the macroblock data and the search region data, and for receiving a motion vector value detected per each of the upper, medium and lower steps to output a motion estimation candidate designation signal;

wherein the sub-sampling rate control signal of the medium step is a signal for causing a 2;

1 sub-sampling ratio.

6. The estimator as claimed in 2, wherein the macroblock measure circuit comprises:

an AVG_MB calculating circuit for receiving current frame macroblock data and calculating the mean intensity value of the macroblock; and

a sum (A) calculating circuit for receiving the current frame macroblock data and calculating the sum (A) of the absolute differences between the mean intensity of the macroblock and the intensity of each pixel of the macroblock.

7. The estimator as claimed in 1, wherein a ±

4 pixel search region for a 4×

4 pixel block is operatively divided into four ±

2 pixel search regions, and the PE array network sequentially searches the four ±

2 pixel search regions to sequentially output the SAD values for the 4×

4 pixel block within the ±

4 pixel search region.

8. The estimator as claimed in 1, wherein for performing a search for a 8×

8 pixel block within a ±

2 pixel search region, the 8×

8 pixel block is operatively divided into four 4×

4 pixel sub-blocks, and the PE array network sequentially searches for each of the 4×

4 sub-blocks within the ±

2 pixel search region and sequentially outputs four SAD values for each one of the 25 search points within the ±

2 pixel search region.

9. The estimator as claimed in 1, wherein for performing a search for a 16×

16 pixel macroblock within a search region, the 16×

16 pixel macroblock is operatively divided into sixteen 4×

4 pixel sub-blocks, and the PE array network sequentially searches for each of the 4×

4 sub-blocks within the search region and sequentially outputs sixteen SAD values for each one of the search points within the search region.

10. A motion estimation method of a video encoder, comprising:

a first step of performing a full search within a ±

4 pixel search region in a first video frame for a 4×

4 pixel block of a second video frame, wherein both of the resolution of first frame and the second frame are reduced by sub-sampling to ¼

resolution of the original video frames, to detect two motion vector candidates.

11. The method as claimed in claim 10, wherein the ±

4 pixel search region is operatively divided into four ±

2 pixel search regions, and wherein the full search within a ±

4 pixel search region is performed by sequentially performing a full search within each of the four 2 pixel search regions for the 4×

4 pixel block.

12. The method as claimed in claim 10, further comprising

a second step of calculating the sum (A) of absolute differences between the mean intensity of a 16×

16 pixel macroblock of the current video frame and the intensity of each pixel of the macroblock, at the original video resolution; and

if the sum A value calculated in the second step is smaller than a predetermined threshold value, then at least one of;

a third step of performing a partial search within a ±

1 pixel search region for a 8×

8 pixel macroblock, wherein the video data is reduced to ½

the resolution of the original video frames, to detect a motion vector candidate; and

a fourth step of performing a partial search within a ±

1 search region for a 16×

16 pixel macroblock in the original video resolution, to detect a final motion vector.

13. The method as claimed in claim 12, further comprising:

a ninth step of comparing the sum (A) of the absolute differences between the mean intensity of the macroblock and the intensity of each pixel of the macroblock, with the predetermined reference value, to select an intermode or intramode.

14. The method as claimed in claim 10, further comprising a tenth step of performing a partial search within a ±

1 pixel search region for a 8×

8 block of current video frame data at ½

of the original video resolution, to detect a motion vector candidate, if it is decided that a prediction result of an optimum candidate of an upper step and a candidate determined using spatial correlation has no motion, if the intensity variation value of the macroblock is greater than a determined reference value.

15. The method as claimed in claim 10, further comprising an eleventh step of performing a partial search within a ±

1 search region for a 16±

16 pixel macroblock of current video frame data at the original video resolution, to detect a motion vector candidate, if it is decided that the prediction result of the optimum candidate of the upper step and a candidate determined using spatial correlation has no motion, if the intensity variation value of the macroblock is greater than the a reference value.

16. A motion estimation method of a video encoder, comprising:

a first step of performing a search for a N×

N pixel block within a search region containing a plurality (S) of search points, wherein the N×

N pixel block is operatively divided into 4^P sub-blocks, wherein P is an integer, and wherein the search for the N×

N pixel macroblock is effectively performed by performing one full search within the search region for each one of the 4^P sub-blocks.

17. The method as claimed in claim 16, wherein the full searches performed within the search region for each one of the 4^P sub-blocks generates a plurality of motion vector candidates.

18. The method as claimed in claim 16, wherein N equals 16, and S is at least 9, and P is equal to one.

19. The method as claimed in claim 16, wherein N equals 16, and S is at least 9, and P equals two.

20. The method as claimed in claim 16, wherein N equals 8, and S is at least 25, and P equals one.