Global motion estimation image coding and processing

• US 20050094852A1
• Filed: 09/01/2004
• Published: 05/05/2005
• Est. Priority Date: 09/05/2003
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Kumar, Sanjeev, Nguyen, Truong, Biswas, Mainak
• Granted Patent: US 7,349,583 B2
• Time in Patent Office: Days
• US Class Current: 382/107
• CPC Class Codes: H04N 19/521 for estimating the reliability of the determined motion vectors or motion vector field, e.g. for smoothing the motion vector field or for correcting motion vectors
• CPC Class Codes: H04N 19/527 Global motion vector estimation
• CPC Class Codes: H04N 19/53 Multi-resolution motion estimation; Hierarchical motion estimation
• CPC Class Codes: H04N 19/547 Motion estimation performed in a transform domain
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

The invention provides methods for global motion estimation, determining a coarse estimation, and refining a coarse estimation. Embodiments of the invention provide a fast and robust global motion estimation algorithm based on two-stage coarse-to-fine refinement strategy, which is capable of measuring large motions. An embodiment of the invention may be applied as a modification of any standard, e.g. MPEG-4 that uses the affine model of motion estimation. Embodiments of the invention may be used in the six parameter affine motion model, and other embodiments of the invention are applicable to the two parameter translation model, the four parameter RST model, and the eight parameter projective model. In a preferred embodiment, a coarse estimation is developed in a translation invariant domain, and then is refined in the spatial domain.

Claims

1. A method for estimating global motion between a reference image or a portion thereof and a current image or a portion thereof, the method comprising steps of:

computing translation invariant representations of the reference image or the portion thereof and the current image or the portion thereof, wherein the translation invariant representations preserve non-translational motion effects present in the reference image or the portion thereof and the current image or the portion thereof;

from the translational invariant representations, determining a coarse estimation of the effect of the non-translational motion between the reference and the current image or the portions thereof; and

determining a coarse estimation of the effect of translational motion from the coarse estimation of the effect of the non-translation motion and the current image or the portion thereof, wherein the effect of the non-translation motion and the effect the translation motion together constitute a coarse estimate of the global motion.

2. The method of claim 1, further comprising a step of using sparse motion measurements in the spatial domain, refining the coarse estimate of the global motion by model fitting.

3. The method of claim 2, further comprising a step of down-sampling prior to said step of computing translation invariant representations.

4. The method of claim 2, wherein said step of refining comprises:

selecting a plurality of promising blocks from corresponding parts of a warped version of the reference image or the portion thereof and from current image or the portion thereof;

determining corresponding local translation motion vectors for the plurality of promising blocks selected in said step of selecting;

classifying data points in the plurality of promising blocks as inlier data points or outlier data points;

using only inlier data points, fitting one of a set of lines, curves or planes to the location of each of the plurality of promising blocks selected in said step of selecting and the corresponding local translation motion vectors determined in said step of determining.

5. The method of claim 1 wherein said step of computing a translation invariant representation comprises computing a Fourier magnitude spectrum for each of the reference image or the portion thereof and the current image or the portion thereof.

6. The method of claim 5 further comprising conducting a Fast Fourier transform to compute the Fourier magnitude spectrum.

7. The method of claim 6, further comprising a step of down-sampling the reference image or the portion thereof and the current image or the portion thereof prior to said step of computing.

8. The method of claim 6, wherein said step of down-sampling comprises:

border blurring to reduce ‘

+’

shaped artifacts due to discontinuity at image borders in the periodic extension of images inherent in the Fast Fourier transform (FFT);

low pass filtering to reduce aliasing;

down-sampling conducted along horizontal and vertical dimensions of the reference image or the portion thereof and the current image or the portion thereof.

9. The method of claim 1, wherein said step of determining a coarse estimation includes a step of adaptively re-sampling the translation invariant representations of the reference image or the portion thereof and the current image or the portion thereof.

10. The method of claim 9, wherein said step of adaptively re-sampling comprises re-sampling an original image that is one of the reference image or the portion thereof or the current image or the portion thereof:

conducting no re-mapping where past motion parameters indicate small mean scaling and small mean rotation for the original image or the portion thereof;

conducting polar mapping where past motion parameters indicate small mean scaling and possibly large mean rotation for the original image or the portion thereof;

conducting log-log mapping where past motion parameters indicate small mean rotation and possibly large mean scaling for the original image or the portion thereof; and

otherwise conducting log-polar mapping.

11. A method for estimating global motion between a reference image or a portion thereof and a current image or a portion thereof, wherein the relationship between the reference image or the portion thereof and the current image or the portion thereof are defined by the relationship X′

=AX+B, where X′

is a coordinate of the pixel in the current image or the portion thereof and is related to a coordinate of a correspondence pixel in the reference image or the portion thereof X by a matrix A multiplication plus a translational vector B, the method comprising steps of;

in the frequency domain, determining a coarse estimate of the matrix A;

determining a coarse estimate of the vector B, by applying the coarse estimate of the matrix A to the reference image or the portion thereof and comparing to the current image or the portion thereof; and

combining the coarse estimate of the matrix A and the coarse estimate of the vector B as coarse global parameters.

12. The method of claim 11, further comprising a step of, in the spatial domain, refining the coarse global parameters.

13. The method of claim 12, wherein said step of refining comprises model fitting.

14. The method of claim 12, wherein said step of refining comprises:

applying the coarse estimate to the reference image or the portion thereof to produce a warped reference image;

selecting N_i corresponding blocks from the current image or the portion thereof and warped reference image;

selecting N_f blocks exhibiting the N_f highest levels of activity; and

determining the translation between each of the high activity N_f promising blocks in the current image or the portion thereof and its corresponding block in the warped reference image.

15. The method of claim 14, further comprising a step of sorting the N_i corresponding blocks based upon a level of activity.

16. The method of claim 14, wherein said step of determining the translation comprises phase-correlation.

17. The method of claim 14, wherein the level of activity is measured by one of the group consisting of sum of absolute difference from mean, variance or eigen values of windowed image second moment matrix.

18. A method of refining a coarse estimation of global motion between a reference image or a portion thereof and a current image or a portion thereof, the coarse estimation including an estimate of the effect of non-translation motion and an estimate of the effect of translational motion, the method comprising steps of:

selecting a plurality of promising blocks from corresponding parts of a warped version reference image or the portion thereof and from the current image or the portion thereof;

determining corresponding local translation motion vectors for the plurality of promising blocks selected in said step of selecting;

classifying data points in the plurality of promising blocks as inlier data points or outlier data points;

using only inlier data points, fitting one of a set of lines, curves or planes to the location of each of the plurality of promising blocks selected in said step of selecting and the corresponding local translation motion vectors determined in said step of determining.

19. The method of claim 18, wherein said step of refining comprises model fitting.

20. A method for refining a coarse estimate of global motion between a reference image or a portion thereof and a current image or a portion thereof, wherein the relationship between the reference image or the portion thereof and the current image or the portion thereof are defined by the relationship X′

=AX+B, where X′

is the coordinate of the pixel in the current image or the portion thereof and is related to the coordinate of the correspondence pixel in the reference image or the portion thereof X by a matrix A multiplication plus a translational vector B, and the coarse estimate provides a coarse estimate of the matrix A and the translational vector B, the method comprising steps of;

applying the coarse estimate to the reference image or the portion thereof to produce a warped reference image;

selecting N_i corresponding blocks from the current image or the portion thereof and warped reference image;

selecting N_f blocks exhibiting the N_f highest levels of activity; and

determining the translation between each of the high activity N_f promising blocks in the current image or the portion thereof and its corresponding block in the reference image or the portion thereof.

21. The method of claim 20, further comprising a step of sorting the N_i corresponding blocks based upon a level of activity.

22. The method of claim 20, wherein said step of refining comprises model fitting.

23. A method for refining a coarse estimate of global motion between a reference image of a portion thereof and a current image or a portion thereof wherein the relationship between the reference image or the portion thereof and the current image of the portion thereof is described by the two parameter translational model, the four parameter RST model or the eight parameter projective model, the method comprising steps of

applying the coarse estimate to the reference image or the portion thereof to produce a warped reference image;

selecting N_i corresponding blocks from the current image or the portion thereof and warped reference image;

selecting N_f promising blocks exhibiting the N_f highest levels of activity; and

determining the translation between each of the high activity N_f promising blocks in the current image or the portion thereof and its corresponding block in the reference image or the portion thereof.

24. The method of claim 23, further comprising a step of sorting the N_i corresponding blocks based upon a level of activity.

25. The method of claim 23, further comprising model fitting.