US 7,742,525 B1Granted

Adaptive motion estimation

AssigneeApple Inc.

InventorsRoger Kumar, Thomas Pun, Xiaochun Nie, Hsi-Jung Wu

Life of this patent

Estimating the term…

Loading patent…

Abstract

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.

Claims19

Dependent claims

A computer-implemented method of performing motion estimation for an array of image values obtained from a current image, the method comprising:

analyzing a plurality of motion estimation searching processes to determine an expected amount of time to complete operations of each motion estimation searching process;
determining a sorted order for performing the plurality of motion estimation searching processes, the sorted order comprising a first motion estimation searching process that, based on the analysis, is expected to be the fastest process in the plurality of processes and a last motion estimation searching process that, based on the analysis, is expected to be the slowest process in the plurality of processes;
performing the first motion estimation searching process to obtain a first estimate of the motion of an image array between the current image and a reference image, and to obtain a first error estimate for the first motion estimate, wherein performing the first motion estimation searching process comprises identifying a first motion vector by performing a first search algorithm to search for the image array in the reference image;
when the first error estimate is larger than a particular threshold, performing a second motion estimation searching process that is the second fastest process in the sorted order to obtain a second estimate of the motion of the image array, and to obtain a second error estimate for the second motion estimate, wherein performing the second motion estimation process comprises identifying a second motion vector by performing a second search algorithm to search for the image array in the reference image, wherein the first and second search algorithms are different;
when the second error estimate is larger than the particular threshold, performing a third motion estimation searching process that is the third fastest process in the sorted order to obtain a third estimate of the motion of the image array, and to obtain a third error estimate for the third motion estimate;
selecting a motion vector produced by the motion estimation searching process with a smallest error estimate;
and
encoding said current image using the selected motion vector.

5 more elements

A computer-implemented method of performing motion estimation for an array of image values obtained from a current image, the method comprising:

analyzing a plurality of motion estimation searching processes to determine an expected amount of time to complete operations of each motion estimation searching process;
determining a sorted order for performing the plurality of motion estimation searching processes, the sorted order comprising a first motion estimation searching process that, based on the analysis, is expected to be the fastest process in the plurality of processes and a last motion estimation searching process that, based on the analysis, is expected to be the slowest process in the plurality of processes;
performing the first motion estimation searching process to obtain a first estimate of the motion of an image array between the current image and a reference image, and to obtain a first error estimate for the first motion estimate, wherein performing the first motion estimation searching process to obtain the first estimate of the motion of the image array between the current image and the reference image comprises:
comparing the image array obtained from the current image with different 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;
from the different reference-image arrays that are compared with the current-image array, identifying the reference-image array that is the least different from the current-image array;
identifying a motion vector based on the positions of the current-image array and the identified reference-image array in their respective images;
when the first error estimate is larger than a particular threshold, performing a second motion estimation searching process that is the second fastest process in the sorted order to obtain a second estimate of the motion of the image array, and to obtain a second error estimate for the second motion estimate;
when the second error estimate is larger than the particular threshold, performing a third motion estimation searching process that is the third fastest process in the sorted order to obtain a third estimate of the motion of the image array, and to obtain a third error estimate for the third motion estimate;
selecting a motion vector produced by the motion estimation searching process with a smallest error estimate;
and
encoding said current image using the selected motion vector.

8 more elements

A computer readable medium that stores a computer program for performing motion estimation for an array of image values obtained from a current image, the computer program comprising sets of instructions for:

analyzing a plurality of motion estimation searching processes to determine an expected amount of time to complete operations of each motion estimation searching process;
determining a sorted order for performing the plurality of motion estimation searching processes, the sorted order comprising a first motion estimation searching process that based on the analysis is expected to be the fastest process in the plurality of processes and a last motion estimation searching process that based on the analysis is expected to be the slowest process in the plurality of processes;
performing the first motion estimation searching process to obtain a first estimate of the motion of an image array between the current image and a reference image, and to obtain a first error estimate for the first motion estimate, wherein the set of instructions for performing the first motion estimation searching process comprises a set of instructions for identifying a first motion vector by performing a first search algorithm to search for the image array in the reference image;
when the first error estimate is larger than a particular threshold, performing a second motion estimation searching process that is the second fastest process in the sorted order to obtain a second estimate of the motion of the image array, and to obtain a second error estimate for the second motion estimate, wherein the set of instructions for said performing the second motion estimation process comprises a set of instructions for identifying a second motion vector by performing a second search algorithm to search for an image array in the reference image, wherein the first and second search algorithms are different;
and
when the second error estimate is larger than the particular threshold, performing a third motion estimation searching process that is the third fastest process in the sorted order to obtain a third estimate of the motion of the image array.

3 more elements

analyzing a plurality of motion estimation searching processes to determine an expected amount of time to complete operations of each motion estimation searching process;
determining a sorted order for performing the plurality of motion estimation searching processes, the sorted order comprising a first motion estimation searching process that based on the analysis is expected to be the fastest process in the plurality of processes and a last motion estimation searching process that based on the analysis is expected to be the slowest process in the plurality of processes;
performing the first motion estimation searching process to obtain a first estimate of the motion of an image array between the current image and a reference image, and to obtain a first error estimate for the first motion estimate, wherein the set of instructions for performing the first motion estimation searching process to obtain the first estimate of the motion of the image array between the current image and the reference image comprises sets of instructions for:
comparing the image array obtained from the current image with different 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;
from the different reference-image arrays that are compared with the current-image array, identifying the reference-image array that is the least different from the current-image array;
identifying a motion vector based on the positions of the current-image array and the identified reference-image array in their respective images;
when the first error estimate is larger than a particular threshold, performing a second motion estimation searching process that is the second fastest process in the sorted order to obtain a second estimate of the motion of the image array, and to obtain a second error estimate for the second motion estimate;
and
when the second error estimate is larger than the particular threshold, performing a third motion estimation searching process that is the third fastest process in the sorted order to obtain a third estimate of the motion of the image array.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/427,890Filed 30 Apr 2003 · us provisional application
Priority: 14 Jul 2002
Granted: 22 Jun 2010
Term ends: Not estimatedThe source records don’t support an estimate.

Classification3 codes

H04N 19/533
Motion estimation or motion compensation: motion estimation using multistep search, e.g. two-dimensional [2D]-log search or one-at-a-time search [OTS]
H04N 19/61
Using transform coding: in combination with predictive coding
H04N
Pictorial communication