Efficient multi-block motion estimation for video compression

• US 20060002474A1
• Filed: 06/27/2005
• Published: 01/05/2006
• Est. Priority Date: 06/26/2004
• Status: Abandoned Application

• Current Assignee: Hong Kong University of Science and Technology
• Original Assignee: Hong Kong University of Science and Technology
• Inventors: Au, Oscar Chi-Lim, Chang, Andy
• Application Number:
  US11/168,232
• Publication Number:
  US 20060002474A1
• Time in Patent Office: Days
• US Class Current: 375/240.160
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
• CPC Class Codes: H04N 19/57 Motion estimation characterised by a search window with variable size or shape

Abstract

A novel method, system, and apparatus for efficient multi-block motion estimation in a digital signal compression and coding scheme. This invention selects only a few representative block sizes for motion estimation when certain favourable conditions occur, rather than using all available block sizes. This invention produces significantly reduced computational costs with virtually no sacrifice in visual quality and in bit-rate.

Claims

1. In a data compressing scheme for matching between frames of images in which each frame is divided into a predetermined number of macroblocks, a method of choosing the best mode for dividing a candidate macroblock from among the predetermined number of macroblocks for motion estimation, said method comprising:

defining a motion vector for a search point in a research region within the candidate macroblock;

constructing a hierarchy of modes for subdividing the candidate macroblock into one or more subblocks wherein the modes are enumerated such that a mode M comprises subblocks with smaller area than or equal to sublocks of a mode N if M>

N;

selecting a lowest mode L and performing an elaborate search with respect to a mismatch measure for the mode L;

choosing the mode M for dividing the candidate macroblock if the mismatch measure is smaller than a threshold; and

performing a relatively simple search for higher modes if the mismatch is not smaller than a threshold.

2. The method of claim 1 wherein the mismatch measure comprises sum of absolute difference (SAD).

3. The method of claim 2 wherein the threshold comprises a weighted average of minimum SADs from among neighbouring blocks.

4. The method of claim 3 wherein the threshold comprises a non-linear function of a weighted average of SADs.

5. The method of claim 1 wherein the elaborated search for the mode L has integer-pixel precision.

6. The method of claim 5 further comprising performing a sub-pixel motion estimation.

7. The method of claim 1 wherein performing the relatively simple search for the higher modes if the mismatch is not smaller than the threshold comprises performing the relatively simple search for a subset of the higher modes in the hierarchy of modes for subdividing the candidate macroblock.

8. The method of claim 1 wherein an elaborate search comprises a search which exhaustively searches candidate motion vectors.

9. The method of claim 1 wherein a relatively simple search comprises a local search which searches candidate motion vectors only within a small neighbourhood of a motion vector from lower modes.

10. The method of claim 1 wherein the mode L comprises one 16×

16 subblock in the candidate macroblock.

11. The method of claim 10 further comprising performing a half-pixel motion estimation for a mode 2 with two 16×

8 subblocks and a mode 3 with two 8×

16 subblocks around a best integer-pixel motion vector from the mode L if a smallest mismatch measure of the best integer-pixel motion vector in the mode L is larger than the threshold.

12. The method of claim 11 further comprising choosing the mode 2 if a sum of the two 16×

8 sub-blocks is smaller than a sum of the two 8×

16 sub-blocks of mode 3 with a corresponding best sub-pixel motion vector.

13. In a data compressing scheme for matching between frames of images in which each frame is divided into a predetermined number of macroblocks, a method of choosing the best mode for dividing a candidate macroblock from among the predetermined number of macroblocks for motion estimation, said method comprising:

defining a motion vector for a search point in a research region within the candidate macroblock;

constructing a hierarchy of modes for subdividing the candidate macroblock into one or more subblocks wherein the modes are enumerated such that a mode M comprises subblocks with smaller area than or equal to sublocks of a level N if M>

N;

selecting a highest mode H and performing an elaborate search with respect to a mismatch measure for the mode H; and

performing a relatively simple search for modes lower than H.

14. The method according to claim 13 wherein the mode H comprises mode 4 and the candidate macroblock comprises a 16×

16 block.

15. The method according to claim 14, further comprising:

Performing integer level motion estimation on mode 4 subblocks;

Obtaining four motion vectors MV1, MV2, MV3, MV4 one for each of the mode 4 subblocks; and

Selecting mode 1 with MV1 if MV1, MV2, MV3 and MV4 are equal.

16. The method according to claim 14, further comprising:

Performing integer level motion estimation on mode 4 subblocks;

Obtaining four motion vectors MV1, MV2, MV3, MV4 one from each of the mode 4 subblocks; and

Selecting mode 1 with MV1 If only MV1, MV2 and MV3 are equal and MV4 is within a threshold distance.

17. The method of claim 16 wherein the threshold distance comprises 1 integer distance.

18. The method according to claim 14, further comprising:

Performing integer level motion estimation on mode 4 subblocks;

Obtaining four motion vectors MV1, MV2, MV3, MV4 one from each of the mode 4 subblocks; and

Selecting mode 1 if MV1, MV2, MV3 and MV4 have a magnitude smaller than a first threshold magnitude, have the same direction, and a collocated macroblock of the candidate macroblock in a previous frame is mode 1.

19. The method according to claim 18 wherein the first threshold magnitude comprises 1.

20. The method according to claim 14, further comprising:

Performing integer level motion estimation on mode 4 subblocks;

Obtaining four motion vectors MV1, MV2, MV3, MV4 one from each of the mode 4 subblocks; and

Selecting mode 1 if x-components or y-components of MV1, MV2, MV3, and MV4 are larger than a second threshold magnitutde.

21. The method according to claim 20 wherein the second threshold magnitude comprises 3.

22. A method for fast multi-block motion estimation, comprising:

a. selecting a macroblock in a current frame and obtaining a motion vector;

b. constructing a hierarchy of levels for subdividing the macroblock into one or more smaller non-overlapping sub-blocks wherein the levels are enumerated such that a level M has sub-blocks with smaller area than or equal to those of a level N for M>

N;

c. performing a relatively elaborate search with respect to a mismatch measure for a level L around a middle in the hierarchy of levels for subdivision of the macroblock; and

d. performing a relatively simple search for levels higher and lower than the level in the hierarchy of levels.

23. A method for fast mult-block motion estimation, comprising:

a. performing a full search with respect to a candidate block;

b. performing a complicated motion estimation on the candidate block; and

c. performing a simplified search on blocks larger than the candidate block using motion vectors from the candidate block as a predictor

24. The method according to claim 23, wherein the search with respect to the candidate block comprises a full search.

25. The method according to claim 23, wherein the search with respect to the candidate block comprises a fast search.

26. A computer-readable storage medium tangibly embodying computer-executable instructions for choosing a best mode for dividing a candidate macroblock from among the predetermined number of macroblocks for motion estimation in matching between frames of images, the program instructions including instructions operable for causing a computer to:

define a motion vector for a search point in a research region within the candidate macroblock;

construct a hierarchy of modes for subdividing the candidate macroblock into one or more subblocks wherein the modes are enumerated such that a mode M comprises subblocks with smaller area than or equal to sublocks of a mode N if M>

N;

select a lowest mode L and perform an elaborate search with respect to a mismatch measure for the mode L;

choose the mode M for dividing the candidate macroblock if the mismatch measure is smaller than a threshold; and

perform a relatively simple search for higher modes if the mismatch is not smaller than a threshold.

27. The computer-readable storage medium of claim 26 wherein the mismatch measure comprises sum of absolute difference (SAD).

28. The computer-readable storage medium of claim 27 wherein the threshold comprises a weighted average of minimum SADs from among neighbouring blocks.

29. The computer-readable storage medium of claim 28 wherein the threshold comprises a non-linear function of a weighted average of SADs.

30. The computer-readable storage medium of claim 26 wherein performing the relatively simple search for the higher modes if the mismatch is not smaller than the threshold comprises performing the relatively simple search for a subset of the higher modes in the hierarchy of modes for subdividing the candidate macroblock.

31. The computer-readable storage medium of claim 26 wherein an elaborate search comprises a search which exhaustively searches candidate motion vectors.

32. The computer-readable storage medium of claim 26 wherein a relatively simple search comprises a local search which searches candidate motion vectors only within a small neighbourhood of a motion vector from lower modes.

33. The computer-readable storage medium of claim 26 wherein the mode L comprises one 16×

16 subblock in the candidate macroblock.

34. A computer-readable storage medium tangibly embodying computer-executable instructions for choosing a best mode for dividing a candidate macroblock from among the predetermined number of macroblocks for motion estimation in matching between frames of images, the program instructions including instructions operable for causing a computer to:

define a motion vector for a search point in a research region within the candidate macroblock;

construct a hierarchy of modes for subdividing the candidate macroblock into one or more subblocks wherein the modes are enumerated such that a mode M comprises subblocks with smaller area than or equal to sublocks of a level N if M>

N;

select a highest mode H and perform an elaborate search with respect to a mismatch measure for the mode H; and

perform a relatively simple search for modes lower than H.

35. The computer-readable storage medium of claim 34, wherein the mode H comprises mode 4 and the candidate macroblock comprises a 16×

16 block.

36. The computer-readable storage medium of claim 35, further comprising instructions operable for causing a computer to:

Perform integer level motion estimation on mode 4 subblocks;

Obtain four motion vectors MV1, MV2, MV3, MV4 one for each of the mode 4 subblocks; and

Select mode 1 with MV1 if MV1, MV2, MV3 and MV4 are equal.

37. The computer-readable storage medium of claim 35, further comprising instructions operable for causing a computer to:

perform integer level motion estimation on mode 4 subblocks;

obtain four motion vectors MV1, MV2, MV3, MV4 one from each of the mode 4 subblocks; and

select mode 1 with MV1 If only MV1, MV2 and MV3 are equal and MV4 is within a threshold distance.

38. The computer-readable storage medium of claim 37 wherein the threshold distance comprises 1 integer distance.

39. The computer-readable storage medium of claim 35, further comprising instructions operable for causing a computer to:

Perform integer level motion estimation on mode 4 subblocks;

Obtain four motion vectors MV1, MV2, MV3, MV4 one from each of the mode 4 subblocks; and

Select mode 1 if MV1, MV2, MV3 and MV4 have a magnitude smaller than a first threshold magnitude, have the same direction, and a collocated macroblock of the candidate macroblock in a previous frame is mode 1.

40. The computer-readable storage medium of claim 39 wherein the first threshold magnitude comprises 1.

41. The computer-readable storage medium of claim 35, further comprising instructions operable for causing a computer to:

Perform integer level motion estimation on mode 4 subblocks;

Obtain four motion vectors MV1, MV2, MV3, MV4 one from each of the mode 4 subblocks; and

Selecting mode 1 if x-components or y-components of MV1, MV2, MV3, and MV4 are larger than a second threshold magnitutde.

42. The computer-readable storage medium of claim 41, wherein the second threshold magnitude comprises 3

43. A computer-readable storage medium tangibly embodying computer-executable instructions for choosing a best mode for dividing a candidate macroblock from among the predetermined number of macroblocks for motion estimation in matching between frames of images, the program instructions including instructions operable for causing a computer to:

a. construct a hierarchy of levels for subdividing the macroblock into one or more smaller non-overlapping sub-blocks wherein the levels are enumerated such that a level M has sub-blocks with smaller area than or equal to those of a level N for M>

N;

b. perform a relatively elaborate search with respect to a mismatch measure for a level L around a middle in the hierarchy of levels for subdivision of the macroblock; and

c. perform a relatively simple search for levels higher and lower than the level in the hierarchy of levels.

44. A computer-readable storage medium tangibly embodying computer-executable instructions for choosing a best mode for dividing a candidate macroblock from among the predetermined number of macroblocks for motion estimation in matching between frames of images, the program instructions including instructions operable for causing a computer to:

a. perform a full search with respect to the candidate block;

b. perform a complicated motion estimation on the candidate block;

c. perform a simplified search on blocks larger than the candidate block using motion vectors from the candidate block as a predictor.