Global motion estimation image coding and processing

• US 7,349,583 B2
• Filed: 09/01/2004
• Issued: 03/25/2008
• 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
• Primary Examiner(s): Bella; Matthew C.
• Assistant Examiner(s): PERUNGAVOOR, SATHYANARAYA V
• Application Number:
  US10/931,473
• Publication Number:
  US 20050094852A1
• Time in Patent Office: 1,301 Days
• Field of Search: 382/294
• US Class Current: 382/294
• 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 of the translation motion together constitute a coarse estimate of the global motion, 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;

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.

2. 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 coordinate of a pixel in the current image or the portion thereof and is related to coordinate of corresponding pixel in the reference image or the portion thereof X by a matrix

$A=\left[\begin{array}{cc}{s}_x<br><br>\cos <br><br><br><br>{\mathrm{\theta <br><br>}}_x& s_x<br><br>\sin <br><br><br><br>{\mathrm{\theta <br><br>}}_x\\ -s_y<br><br>\sin <br><br><br><br>{\mathrm{\theta <br><br>}}_y& s_y<br><br>\cos <br><br><br><br>{\mathrm{\theta <br><br>}}_y\end{array}\right]$

multiplication plus a translational vector B, the method comprising steps of;

in the frequency domain, determining a coarse estimate of the matrix according to

$A=\left[\begin{array}{cc}{s}_m<br><br>\mathrm{ds}<br><br>\left(\cos <br><br>\left({\mathrm{\theta <br><br>}}_m+d<br><br><br><br>\mathrm{\theta <br><br>}\right)\right)& s_m<br><br>\mathrm{ds}<br><br>\left(\sin <br><br>\left({\mathrm{\theta <br><br>}}_m+d<br><br><br><br>\mathrm{\theta <br><br>}\right)\right)\\ -\frac{s_m}{\mathrm{ds}}<br><br>\sin <br><br>\left({\mathrm{\theta <br><br>}}_m-d<br><br><br><br>\mathrm{\theta <br><br>}\right)& \frac{s_m}{\mathrm{ds}}<br><br>\cos <br><br>\left({\mathrm{\theta <br><br>}}_m-d<br><br><br><br>\mathrm{\theta <br><br>}\right)\end{array}\right],$

, wherein S_m=mean scaling

ds=differential scaling

θ

_m=mean rotation

dθ

=differential rotation;

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;

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

in the spatial domain, refining the coarse global parameters

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 wherein N_f is less than N_i and other ones of the N_i blocks are discarded; 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;

wherein said step of determining a coarse estimate includes a step of adaptively re-sampling translation invariant representations of the reference image or the portion thereof and the current image or the portion thereof;

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.

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

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

5. The method of claim 2, 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.

6. 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, wherein the promising blocks comprise blocks of high activity;

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;

wherein the coarse estimation is determined at least by adaptively re-sampling translation invariant representations of the reference image or the portion thereof and the current image or the portion thereof;

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.

7. The method of claim 6, wherein said step of refining comprises random sampling based model fining.

8. 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 is defined by the relationship X′

=AX+B, where X′

is coordinate of a pixel in the current image or the portion thereof and is related to coordinate of corresponding 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;

wherein the coarse estimate is determined at least by adaptively re-sampling translation invariant representations of the reference image or the portion thereof and the current image or the portion thereof;

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;

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, wherein N_f is less than N_i and other ones of the N_i blocks are discarded; 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.

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

10. The method of claim 8, wherein said step of refining comprises model fining.

11. 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;

wherein the coarse estimate is determined at least by adaptively re-sampling translation invariant representations of the reference image or the portion thereof and the current image or the portion thereof;

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;

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, wherein N_f is less than N_i and other ones of the N_i blocks are discarded; 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.

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

13. The method of claim 11, further comprising model fitting.