Method and system for constraint-consistent motion estimation

• US 7,164,800 B2
• Filed: 02/19/2003
• Issued: 01/16/2007
• Est. Priority Date: 02/19/2003
• Status: Expired due to Fees

• Current Assignee: Eastman Kodak Company
• Original Assignee: Eastman Kodak Company
• Inventors: Sun, Zhaohui
• Primary Examiner(s): Do; Anh Hong
• Application Number:
  US10/369,967
• Publication Number:
  US 20040165781A1
• Time in Patent Office: 1,427 Days
• Field of Search: 382/154, 382/236, 382/107, 382/238, 382/201, 345/156, 345/427, 345/419, 375/240, 375/240.12, 375/240.16, 375/240.27, 700/29, 700/30, 700/31, 700/44, 348/699
• US Class Current: 382/236
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06T 7/579 from motion

Abstract

A method for determining motion vectors from one point in one image frame of a scene to corresponding points in at least two other image frames of the scene, wherein the frames are obtained in a capture process utilizing one or more cameras, wherein the method employs an iterative and hierarchical dense motion estimation that computes the geometry-consistent and appearance-consistent motion fields between three images simultaneously by enforcing both a trilinear constraint and a constant-brightness constraint. This method includes the steps of: providing first, second and third images of a scene under perspective projection with unconstrained motion of the camera, wherein points (x′,y′) and (x″,y″) in the second and third frames are projections of the same spatial points (x,y) in the first frame; specifying a system of trifocal tensors and optical flow equations that describe point correspondence across the three images; and applying both a geometric constraint of trilinearity and an appearance constraint of constant brightness, thereby utilizing a trilinear constraint and a constant brightness constraint to obtain the pointwise displacement between the three frames simultaneously.

Claims

1. A method for determining motion vectors from one point in one image frame of a scene to corresponding points in at least two other image frames of the scene, utilizing one or more cameras, said method comprising the steps of:

providing first, second, and third images of a scene under perspective projection with unconstrained motion of the one or more cameras, wherein points (x′

,y′

) and (x″

,y″

) in the second and third frames are projections of the same spatial points (x,y) in the first frame;

specifying a system of trifocal tensors and optical flow equations that describe point correspondence across the three images; and

applying both a geometric constraint of trilinearity and an appearance constraint of constant brightness, thereby utilizing a trilinear constraint and a constant brightness constraint to obtain the pointwise displacement between the three frames simultaneously;

wherein said providing further comprises capturing said first, second, and third images with said one or more cameras.

2. The method of claim 1 wherein the step of applying both a geometric constraint of trilinearity and an appearance constraint of constant brightness is comprised of the steps of:

(a) composing a system of trilinear equations and optical flow equations as an over-determined nonlinear system f(Λ

)=0, with Λ

=(x′

,y′

,x″

,y″

);

(b) linearizing constraints f(Λ

)=0 as JΔ

=ε

, with J as a Jacobian matrix, Δ

as an adjustment on Λ

, and ε

as a perturbation error;

(c) choosing a block with size bxb pixels around point (x,y) as a support region;

(d) computing the Jacobian J and the perturbation ε

;

(e) solving Δ

by the Levenberg-Marguardt method;

(f) updating the estimate Λ

_t=Λ

<sub>t−

1</sub>+Δ

;

(g) repeating steps (d) to (f) until the adjustment Δ

is small enough, or a pre-specified number of iterations has been reached;

(h) repeating steps (d) to (f) for regions around (x,y) until b=1 and the region contains one pixel; and

(i) using the final estimate of point correspondence Λ

=(x′

,y′

,x″

,y″

) to specify the pointwise displacement between the three frames.

3. The method of claim 1 wherein the constraints are from different modalities, geometry and appearance respectively, and are used in a single optimization for constraint-consistent motion estimation.

4. The method of claim 2 wherein four independent trilinear equations and two optical flow equations are integrated in an over-determined system at each point (x,y) for four unknown variables (x′

,y′

,x″

,y″

), thus alleviating aperture and motion blurring problems.

5. The method of claim 1 provides a manifold-plus-parallax approach to motion estimation, wherein the trilinear constraint specifies a manifold in R⁴ best approximating the corresponding points (x′

,y′

,x″

,y″

), and the constant-brightness constraint helps to alleviate the dependence on the initial points.

6. The method of claim 1 as being applicable to both 2-D and 3-D scenes under perspective projections, wherein 2-D motions include translational motion, affine motion, and perspective motion, and wherein a fundamental matrix based on epipolar geometry between two image frames can also be derived from the trifocal tensor between the three image frames.

7. The method of claim 1 wherein the camera is uncalibrated with unknown parameters, and the scene under imaging undergoes unconstrained rigid motion.

8. The method of claim 1 wherein three sets of trilinear constraints and three trifocal tensors T_i^jk(ψ

, ψ

′

, ψ

″

), U_k^ij(ψ

″

, ψ

, ψ

′

), and V_j^ki(ψ

′

, ψ

″

, ψ

) are employed in a single optimization to overcome potential system bias.

9. The method of claim 1 wherein color information is used in addition to the brightness or image intensity.

10. The method of claim 2 wherein the support region around (x,y) is used to capture large motion and alleviate error sensitivity of gradient estimates, especially in non-texture areas.

11. The method of claim 2 wherein the image coordinates (x,y), (x′

,y′

) and (x″

,y″

) are normalized such that an Euclidean distance of the image pixels to an image center is √

{square root over (2)}.

12. The method of claim 11 wherein the normalization is carried out to balance the contributions from geometry and appearance, such that no constraint always over-dominates the other.

13. The method of claim 2 wherein eigenvalues of a Hessian matrix are used to determine constraint emphasis.

14. The method of claim 2 wherein the nonlinear system is solved by an iterative scheme.

15. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 1.

16. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 2.

17. The method of claim 2, further comprising a hierarchical and multi-resolution dense motion estimation method to find geometric-consistent and appearance-consistent motion fields across the three images simultaneously, comprising the steps of:

(a) providing three input images I, I′

, and I″

;

(b) estimating the trifocal tensors between the three input images;

(c) constructing hierarchical and multi-resolution pyramid structures for the three images, wherein the resolution levels of the structures run from a coarse to a fine, or full, resolution level;

(d) beginning with a coarse level, normalizing image coordinates and intensities of the images;

(e) computing spatial gradients of the normalized images;

(f) selecting an initial point Λ

₀;

(g) given the point Λ

₀, solving for the point correspondence Λ

;

(h) repeating steps (d) to (g) for progressively finer resolutions until the full resolution is obtained in a coarse-to-fine sequence, wherein for each repetition of step (f) an initial point Λ

₀ is selected using the initial point result Λ

₀ from the previous level;

(i) finding the dense motion fields between three images on a specific pyramid level; and

(j) finding the dense motion fields between three images on the full resolution.

18. The method of claim 17 wherein the dense motion fields between the three image frames are computed simultaneously.

19. The method of claim 17 further comprising the steps of feature detection, feature tracking or matching, and outlier rejection, wherein the trifocal tensor is estimated from reliable feature correspondences obtained across the three images after application of the preceding steps of feature detection, feature tracking or matching, and outlier rejection.

20. The method of claim 17 wherein the three input images are selected from a digital image or video sequence.

21. The method of claim 17 wherein the three input images are selected from a digital image or video sequence in a bi-directional configuration.

22. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 17.

23. A system for determining motion vectors from one point in one image frame of a scene to corresponding points in at least two other image frames of the scene, wherein the frames are obtained in a capture process utilizing one or more cameras, said system comprising:

means for obtaining first, second and third images of a scene under perspective projection with unconstrained motion of the camera, wherein points (x′

,y′

) and (x″

,y″

) in the second and third frames are projections of the same spatial points (x,y) in the first frame; and

a processor for specifying a system of trifocal tensors and optical flow equations that describe point correspondence across the three images and for applying both a geometric constraint of trilinearity and an appearance constraint of constant brightness, thereby utilizing a trilinear constraint and a constant brightness constraint to obtain the pointwise displacement between the three frames simultaneously.

24. The system as claimed in claim 23 wherein the pointwise displacement obtained between the three frames is used for at least one of image alignment and registration, video filtering, video enhancement, motion compensation for video compression, image based rendering, and 3-D shape recovery.

25. The system of claim 23 wherein the three images are selected from a digital image or video sequence.

26. The system of claim 23 wherein the three images are selected from a digital image or video sequence in a bi-directional configuration.