Method of modifying a time-varying image sequence by estimation of velocity vector fields

• US 5,991,459 A
• Filed: 01/22/1992
• Issued: 11/23/1999
• Est. Priority Date: 01/22/1992
• Status: Expired due to Fees

• Current Assignee: Eastman Kodak Company
• Original Assignee: Eastman Kodak Company
• Inventors: Fogel, Sergei Valentinovich
• Primary Examiner(s): Kelley, Christopher S.
• Application Number:
  US07/823,723
• Time in Patent Office: 2,862 Days
• Field of Search: 364/516, 364/560, 364/565, 364/571.05, 358/105, 358/107, 382/16, 382/1
• US Class Current: 382/264
• CPC Class Codes: G06T 7/269 using gradient-based methods

Abstract

A method of modifying a time-varying image sequence in which a parametric velocity vector field that characterizes changes in successive images of the image sequence is estimated. The estimating includes combining optical flow constraints, directional smoothness constraints and regularization constraints in a functional of the estimate of the parametric velocity vector field such that the weighting coefficients of the functional are functions of the parametric velocity vector field to be estimated. A system of nonlinear equations that arise from the optimality criterion of the functional are then solved. Once the system of nonlinear equations is solved, the estimate of the parametric velocity vector field is applied to modify at least one image in the image sequence.

Claims

1. A method of modifying a time-varying image sequence comprising the steps of:

a. estimating a parametric velocity vector field that characterizes changes in successive images of the image sequence, said step of estimating including;

i. combining optical flow constraints, directional smoothness constraints and regularization constraints in a functional of the estimate of the parametric velocity vector field such that weighting coefficients of the functional are functions of the parametric velocity vector field to be estimated; and

ii. solving a system of nonlinear equations that arise from optimality criterion of the functional;

b. applying the estimate of the parametric velocity vector field to modify at least one image in the image sequence.

2. The method of claim 1, wherein the step of solving the system of nonlinear equations includes the steps of selecting a finite sequence of parameter values, and successively solving the system of nonlinear equations starting with a parameter value where the solution of the system of nonlinear equations is equal to a given vector constant and proceeding in a direction decreasing with respect to the parameter values using the solution of the system of nonlinear equations obtained for the preceding parameter value as the initial estimate.

3. The method of claim 1, wherein the solution of the system of nonlinear equations is smooth with respect to a parameter value.

4. The method of claim 1, wherein the system of nonlinear equations is such that a quadratic form associated with a Jacobian of an operator forming the system of nonlinear equations is not positive definite near the occluding boundaries and is asymmetric.

5. The method of claim 4, further comprising approximating the Jacobian with a symmetric and positive definite linear operator.

6. The method of claim 5, further comprising deriving a parametric system of linear equations from the Jacobian.

7. The method of claim 6, further comprising performing a preconditioned iterative process for solving the system of linear equations.

8. The method of claim 7, wherein the iterative process is a conjugate gradient acceleration.

9. The method of claim 7, wherein the iterative process is a Chebyshev polynomial acceleration.

10. The method of claim 2, wherein the successive solving of the system of nonlinear equations includes performing a finite-difference discretization of the system of nonlinear equations.

11. The method of claim 1, wherein the system of nonlinear equations that are solved is:

##EQU67## where the parameters appearing in this system of nonlinear equations variables are defined as follows;

σ

δ

(σ

) are smoothing parameters;

u.sup.σ

is a horizontal component of the estimate of the velocity vector, v.sup.σ

is a vertical component of the estimate of the velocity vector;

G₁ is a set of optical flow constraints;

r, p, q, ρ

(g₁), g₁ .di-elect cons.G₁ are constant parameters specifying the part of the system of nonlinear equations representing the optical flow constraints;

∥

∇

u.sup.σ

∥

is a norm of the gradient of the horizontal component of the estimate of the velocity vector;

∥

∇

v.sup.σ

∥

is a norm of the gradient of the vertical component of the estimate of the velocity vector, g₁.sup.σ

, g₁ .di-elect cons.G₁ is an optical flow constraint;

g_1u.sup.σ

, g₁ .di-elect cons.G₁ is a derivative of the optical flow constraint g₁.sup.σ

with respect to the horizontal component u.sup.σ

of the estimate of the velocity vector;

g_1v.sup.σ

, g₁ .di-elect cons.G₁ is a derivative of the optical flow constraint g₁.sup.σ

with respect to the vertical component v.sup.σ

of the estimate of the velocity vector;

S is a set of directions used in the directional smoothness constraints;

a,c,b,ρ

_s,s.di-elect cons.S are constant parameters specifying the part of the system of nonlinear equations representing the directional smoothness constraints;

b² (s,σ

'"'"'g₁.sup.σ

)² is a weighted average of the squares of the directional derivatives of the optical flow constraints in the direction s;

(s∇

u.sup.σ

) is a directional derivative of the horizontal component u.sup.σ

of the estimate of the velocity vector in the direction s;

(s,∇

v.sup.σ

) is a directional derivative of the vertical component v.sup.σ

of the estimate of the velocity vector in the direction s;

γ

.sup.σ

is the constant parameter.

12. A method of modifying a time-varying image sequence comprising the steps of:

a. estimating a parametric velocity vector field that characterizes changes in successive images of the image sequence, said step of estimating including;

i. combining optical flow constraints, directional smoothness constraints and regularization constraints in a functional of the estimate of the parametric velocity vector field such that weighting coefficients of the functional are functions of the parametric velocity vector field to be estimated;

ii. providing a dual feed-back interaction between the optical flow constraints and the directional smoothness constraints;

iii. solving a system of nonlinear equations that arise from optimality criterion of the functional;

b. applying the estimate of the parametric velocity vector field to modify at least one image in the image sequence.

13. The method of claim 12, wherein the step of providing dual feed-back interaction includes selectively applying variation to the optical flow constraints and to the directional smoothness constraints and not to the weighting coefficients, to thereby permit using unknown estimates of the velocity vectors as part of variable in the weighting coefficients.

14. The method of claim 12, wherein the step of solving the system of nonlinear equations includes the steps of selecting a finite sequence of parameter values, and successively solving the system of nonlinear equations starting with a parameter value where the solution of the system of nonlinear equations is equal to a given vector constant and proceeding in a direction decreasing with respect to the parameter values using the solution of the system of nonlinear equations obtained for the preceding parameter value as the initial estimate.

15. The method of claim 12, wherein the solution of the system of nonlinear equations is smooth with respect to a parameter value.

16. The method of claim 12, wherein the system of nonlinear equations is such that a quadratic form associated with a Jacobian of an operator forming the system of nonlinear equations is not positive definite near the occluding boundaries and is asymmetric.

17. The method of claim 16, further comprising approximating the Jacobian with a symmetric and positive definite linear operator.

18. The method of claim 17, further comprising deriving a parametric system of linear equations from the Jacobian.

19. The method of claim 18, further comprising performing a preconditioned iterative process for solving the system of linear equations.

20. The method of claim 19, wherein the iterative process is a conjugate gradient acceleration.

21. The method of claim 19, wherein the iterative process is a Chebyshev polynomial acceleration.

22. The method of claim 14, wherein the successive solving of the system of nonlinear equations includes performing a finite-difference discretization of the system of nonlinear equations.

23. The method of claim 12, wherein the system of nonlinear equations that are solved is:

##EQU68## where the parameters appearing in this system of nonlinear equations variables are defined as follows;

σ

δ

(σ

) are smoothing parameters;

u.sup.σ

is a horizontal component of the estimate of the velocity vector, v.sup.σ

is a vertical component of the estimate of the velocity vector;

G₁ is a set of optical flow constraints;

r, p, q, ρ

(g₁), g₁ .di-elect cons.G₁ are constant parameters specifying the part of the system of nonlinear equations representing the optical flow constraints;

∥

∇

u.sup.σ

∥

is a norm of the gradient of the horizontal component of the estimate of the velocity vector;

∥

∇

v.sup.σ

∥

is a norm of the gradient of the vertical component of the estimate of the velocity vector, g₁.sup.σ

, g₁ .di-elect cons.G₁ is an optical flow constraint;

g_1u.sup.σ

, g₁ .di-elect cons.G₁ is a derivative of the optical flow constraint g₁.sup.σ

with respect to the horizontal component u.sup.σ

of the estimate of the velocity vector;

g_1v.sup.σ

, g₁ .di-elect cons.G₁ is a derivative of the optical flow constraint g₁.sup.σ

with respect to the vertical component v.sup.σ

of the estimate of the velocity vector;

S is a set of directions used in the directional smoothness constraints;

a,c,b,ρ

_s,s.di-elect cons.S are constant parameters specifying the part of the system of nonlinear equations representing the directional smoothness constraints;

b² (s,σ

'"'"'g₁.sup.σ

)² is a weighted average of the squares of the directional derivatives of the optical flow constraints in the direction s;

(s∇

u.sup.σ

) is a directional derivative of the horizontal component u.sup.σ

of the estimate of the velocity vector in the direction s;

(s,∇

v.sup.σ

) is a directional derivative of the vertical component v.sup.σ

of the estimate of the velocity vector in the direction s;

γ

.sup.σ

is the constant parameter.

24. A method of modifying a time-varying image sequence comprising the steps of:

a. digitizing images of the time-varying image sequence;

b. estimating a parametric velocity vector field that characterizes changes in successive digitized images of the image sequence, said step of estimating including;

i. treating the digitized images as generalized functions;

ii. obtaining a specific subset of a set of testing functions by introduction of a scaling factor into one of the testing functions that is a measurement function;

iii. treating derivatives of the digitized images as generalized derivatives observed on the specific subset of the set of testing functions; and

iv. sequentially solving with a progressively lower degree of measurement blue a system of nonlinear equations corresponding to the testing functions;

b. applying the estimate of the parametric velocity vector field to modify at least one image in the image sequence.