Adaptive Motion Estimation

• US 20110019879A1
• Filed: 05/03/2010
• Published: 01/27/2011
• Est. Priority Date: 07/14/2002
• Status: Active Grant

• Current Assignee: Hsi-Jung Wu, Roger Kumar, Thomas Pun, Xiaochun Nie
• Original Assignee: Hsi-Jung Wu, Roger Kumar, Thomas Pun, Xiaochun Nie
• Inventors: Wu, Hsi-Jung, Pun, Thomas, Kumar, Roger, Nie, Xiaochun
• Granted Patent: US 8,254,459 B2
• Time in Patent Office: Days
• US Class Current: 382/107
• CPC Class Codes: H04N 19/533 Motion estimation using multistep search, e.g. 2D-log search or one-at-a-time search [OTS]
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

Some embodiments of the invention provide a method for adaptively performing motion estimation. In some embodiments, the method initially performs a first motion estimation operation. It then determines whether the estimated error in the result of the first motion estimation is greater than a particular threshold. If not, the method uses the results of the first motion estimation operation. Otherwise, the method selects another motion estimation operation. The method continues in this manner until it performs a motion estimation operation that results in an acceptable estimated error, or until it tries all the motion estimation operations at its disposal. When the method cannot identify a motion estimation operation that produces results with an acceptable estimated error, the method selects the result of the motion estimation operation that produced the best results.

Claims

1-20. -20. (canceled)

21. A computer readable medium storing a computer program that when executed by at least one processor performs motion estimation for an image array obtained from a current image in a sequence of video images, the computer program comprising sets of instructions for:

performing a first motion estimation process to obtain a first estimate of a motion of the image array between the current image and a reference image in the sequence of video images, and to obtain a first error estimate for the first estimate of the motion of the image array;

when the first error estimate is greater than a threshold value, performing a second motion estimation process to obtain a second estimate of the motion of the image array between the current image and the reference image, and to obtain a second error estimate for the second estimate of the motion of the image array; and

when the second error estimate is greater than the threshold value, performing a third motion estimation process to obtain a third estimate of the motion of the image array between the current image and the reference image.

22. The computer readable medium of claim 21, wherein the computer program further comprises a set of instructions for specifying the first estimate of the motion of the image array as a final estimate of the motion of the image array when the first error estimate is less than or equal to the threshold value.

23. The computer readable medium of claim 21, wherein the set of instructions for performing the first motion estimation process comprises sets of instructions for:

comparing the image array obtained from the current image with a set of different reference image arrays that are obtained from the reference image, wherein the image array obtained from the current image is a current-image array and each image array obtained from the reference image is a reference-image array;

identifying a particular reference-image array that is least different from the current-image array based on the comparison; and

identifying a motion vector based on a position of the current-image array in the current image and a position of the particular reference-image array in the reference image.

24. The computer readable medium of claim 23, wherein the computer program further comprises a set of instructions for computing the first error estimate by aggregating an absolute value of a difference between corresponding image values in the current-image array and the particular reference-image array.

25. The computer readable medium of claim 23, wherein the set of instructions for comparing the current-image array and the set of different reference-image arrays comprises a set of instructions for aggregating an absolute value of a difference between corresponding image values in the current-image array and the particular reference-image array.

26. The computer readable medium of claim 21, wherein the image array specifies image values for a two-dimensional set of pixels in the current image.

27. The computer readable medium of claim 26, wherein the set of pixels is a macroblock that has a width of 16 pixels and a height of 16 pixels.

28. The computer readable medium of claim 21, wherein the computer program further comprises a set of instructions for specifying the second estimate of the motion of the image array as a final estimate of the motion of the image array when the second error estimate is less than or equal to the threshold value.

29. The computer readable medium of claim 21, wherein each of the motion estimation processes performs at least one search in at least one reference image to obtain the corresponding estimate of the motion of the image array.

30. The computer readable medium of claim 21, wherein the set of instructions for performing the first motion estimation process comprises a set of instructions for identifying a first motion vector by performing a first search algorithm to search for an image array in the reference image, wherein the set of instructions for performing the second motion estimation process comprises a set of instructions for identifying a second motion vector by performing a second search algorithm, different from the first search algorithm, to search for an image array in the reference image.

31. The computer readable medium of claim 21, wherein the motion estimation processes are sorted from an expected fastest to an expected slowest, wherein the computer program further comprises sets of instructions for iteratively selecting each of the motion estimation processes according to the sorted order to obtain the corresponding estimate of the motion of the image array and to obtain the corresponding error estimate.

32. The computer readable medium of claim 31, wherein the set of instructions for performing the third motion estimation process comprises a set of instructions for obtaining a third error estimate for the third estimate of the motion of the image array, wherein the computer program further comprises a set of instructions for specifying the third estimate of the motion of the image array as a specified estimate of the motion of the image array when the third error estimate is less than or equal to the threshold value.

33. The computer readable medium of claim 31, wherein the computer program further comprises a set of instructions for selecting a lowest error estimate from each of the error estimates produced from performing each of the motion estimation processes as a selected estimate of the motion of the image array when none of the error estimates is less than or equal to the threshold value.

34. A computer readable medium storing a computer program that when executed by at least one processor performs motion-estimation for a video, the computer program comprising sets of instructions for:

iteratively;

selecting a particular motion-estimation searching process from a list of at least three motion-estimation searching processes that are sorted from an expected fastest to an expected slowest; and

performing the particular motion-estimation searching process to identify a motion-estimation error, the iterative selecting and performing terminated when the identified motion-estimation error meets a same threshold.

35. The computer readable medium of claim 34, wherein each particular motion-estimation searching process produces a motion estimation, wherein the computer program further comprises a set of instructions for defining a particular motion estimation that meets the same threshold as a specified estimate of a motion of a set of pixels in an image of the video.

36. The computer readable medium of claim 34, wherein the set of instructions for selecting the particular motion-estimation searching process comprises a set of instructions for selecting, during each iteration, an expected-fastest motion-estimation searching process in the list that has not been selected.

37. The computer readable medium of claim 34, wherein the list of motion-estimation searching processes comprises first, second, and third motion-estimation searching processes.

38. The computer readable medium of claim 37, wherein the first motion-estimation searching process is designated as a faster process than the second motion-estimation searching process, and the second motion-estimation searching process is designated as a faster process than the third motion-estimation searching process.

39. A method of performing motion estimation for an image array obtained from a current image in a sequence of video images, the method comprising:

performing a first motion estimation process to obtain a first estimate of a motion of the image array between the current image and a reference image in the sequence of video images, and to obtain a first error estimate for the first estimate of the motion of the image array;

when the first error estimate is greater than a threshold value, performing a second motion estimation process to obtain a second estimate of the motion of the image array between the current image and the reference image, and to obtain a second error estimate for the second estimate of the motion of the image array; and

when the second error estimate is greater than the threshold value, performing a third motion estimation process to obtain a third estimate of the motion of the image array between the current image and the reference image.

40. The method of claim 39, wherein the first motion estimation process is designated as a faster process than the second motion estimation process, and the second motion estimation process is designated as a faster process than the third motion estimation process.

41. The method of claim 39 further comprising receiving a sorted list comprising a plurality of motion estimation processes, the sorted list comprising the first motion estimation process that, based on prior analysis, is expected to be a fastest process in the plurality of motion estimation processes and a last motion estimation process that, based on the prior analysis, is expected to be a slowest process in the plurality of motion estimation processes, wherein performing the motion estimation processes comprises iteratively performing one or more of the plurality of motion estimation processes according to the sorted list.