Method and apparatus for motion estimation using variable block size of hierarchy structure

• US 20050114093A1
• Filed: 11/12/2004
• Published: 05/26/2005
• Est. Priority Date: 11/12/2003
• Status: Abandoned Application

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Cha, Sang-chang, Ahn, Jong-hak
• Application Number:
  US10/986,384
• Publication Number:
  US 20050114093A1
• Time in Patent Office: Days
• US Class Current: 702/189
• CPC Class Codes: H04N 19/109 among a plurality of temporal predictive coding modes
• CPC Class Codes: H04N 19/139 Analysis of motion vectors, e.g. their magnitude, direction, variance or reliability
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation
• CPC Class Codes: H04N 19/57 Motion estimation characterised by a search window with variable size or shape
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

Disclosed is a method and apparatus for a motion estimation using a variable block size of a hierarchy structure. The method includes: calculating each of a motion vector of a desired minimum unit variable block; determining a similarity of the calculated motion vectors between the minimum unit variable blocks in a higher hierarchy including the minimum unit variable block; establishing a mode of the variable block according to the determined similarity; and deciding a motion vector with respect to the mode established variable block. The complexity of the method of compressing a motion picture of a hierarchy structure having a plurality of block sizes can be reduced by selecting a mode of the optimal block size on the basis of a motion vector with respect to the minimum unit and the cost occurred at that time without performing the motion estimation with respect to each mode each time.

Claims

1. A method for a motion estimation using a variable block size of a hierarchy structure, the method comprising:

a first step of calculating motion vectors of minimum unit variable blocks;

a second step of determining similarities of the calculated motion vectors between minimum unit variable blocks in a higher hierarchy;

a third step of establishing a mode of a variable block according to the determined similarities; and

a fourth step of deciding a motion vector with respect to the mode established variable block.

2. The method according to claim 1, wherein the first step comprises;

calculating costs for the motion vectors of the minimum unit variable blocks; and

storing the calculated motion vectors and costs.

3. The method according to claim 2, wherein the second step comprises;

grouping the minimum unit variable blocks in an order of decreasing stored costs as grouped blocks; and

determining similarities of motion vectors between the grouped blocks.

4. The method according to claim 3, wherein when the motion vectors between the grouped blocks are similar as a result of the determining the similarities of the motion vectors between the grouped blocks, the second step further includes determining similarities of the motion vectors between the grouped blocks and other adjacent blocks having the same sizes as the grouped blocks, each of the grouped blocks being used as a unit.

5. The method according to claim 4, wherein, in the determination of the similarities of the motion vectors between the grouped blocks and other adjacent blocks, the motion vectors between the grouped blocks and other adjacent blocks are determined as similar when a vector difference of the motion vectors of variable blocks that are subjects of the determination of the similarities of the motion vectors between the grouped blocks and other adjacent blocks, is less than or equal to a desired threshold.

6. The method according to claim 1, wherein the third step is a step of establishing the mode of the variable block according to the determined similarities starting from a highest hierarchy to lower hierarchies.

7. The method according to claim 1, wherein the fourth step is a step of deciding the motion vector of the mode of the variable block established in the third step using the motion vectors of lower hierarchy blocks constructing the variable block established in the third step.

8. The method according to claim 7, wherein the fourth step is a step of deciding the motion vector of the mode of the variable block established in the third step using an intermediate value of the motion vectors of the lower hierarchy blocks constructing the variable block established in the third step.

9. The method according to claim 1 wherein the method for a motion estimation to calculate the motion vector is a method for a high-speed motion estimation.

10. An apparatus for a motion estimation using a variable block size of a hierarchy structure, comprising:

motion vector calculating means for calculating motion vectors of minimum unit variable blocks;

variable block mode establishment means for determining similarities of the calculated motion vectors between minimum unit variable blocks in a higher hierarchy, and establishing a mode of a variable block according to the determined similarities; and

motion vector decision means for deciding the motion vector with respect to the mode established variable block.

11. The apparatus according to claim 10, wherein the motion vector calculating means calculates costs for the motion vectors of the minimum unit variable blocks and stores the calculated motion vectors and costs.

12. The apparatus according to claim 11, wherein the variable block mode establishment means makes a grouping of the minimum unit variable blocks in an order of decreasing stored costs as grouped blocks, and determines similarities of motion vectors between the grouped blocks.

13. The apparatus according to claim 12, wherein the variable block mode establishment means determines the similarities of the motion vectors between the grouped blocks and other adjacent blocks having the same sizes as the grouped blocks when the motion vectors between the grouped blocks are similar as a result of determining the similarities of the motion vectors between the grouped blocks, each of the grouped blocks being used as a unit.

14. The apparatus according to claim 13, wherein, in the determination of the similarities of the motion vectors between the grouped blocks and other adjacent blocks, the motion vectors between the grouped blocks and other adjacent blocks are determined as similar when a vector difference of the motion vectors of variable blocks that are subjects of the determination of the similarities of the motion vectors between the grouped blocks and other adjacent blocks, is less than or equal to a desired threshold.

15. The apparatus according to claim 10, wherein the variable block mode establishment means establishes the mode of the variable block according to the determined similarities starting from a highest hierarchy to lower hierarchies.

16. The apparatus according to claim 10, wherein the motion vector decision means decides the motion vector of the mode of the variable block established in the variable block mode establishment means using the motion vectors of lower hierarchy blocks constructing the variable block established in the variable block mode establishment means.

17. The apparatus according to claim 16, wherein the motion vector decision means decides the motion vector of the mode of the variable block established in the variable block mode establishment means using an intermediate value of the motion vectors of the lower hierarchy blocks constructing the variable block established in the third step.