Method for estimating velocity vector fields from a time-varying image sequence

• US 5,241,608 A
• Filed: 12/20/1990
• Issued: 08/31/1993
• Est. Priority Date: 11/25/1988
• Status: Expired due to Term

• Current Assignee: Eastman Kodak Company
• Original Assignee: Eastman Kodak Company
• Inventors: Fogel, Sergei V.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/631,750
• Time in Patent Office: 985 Days
• Field of Search: 382/16, 382/37, 382/56, 382/54, 364/565, 364/570, 364/715.02, 364/421, 364/174, 358/105, 358/136
• US Class Current: 382/107
• CPC Class Codes: G06T 7/207 for motion estimation over a hierarchy of resolutions multi-resolution motion estimation or hierarchical motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/53

Abstract

Changes in successive images from a time-varying image sequence of a scene are characterized by velocity vector fields. As estimate of the velocity vector field is determined as a compromise in the attempt to satisfy the following two sets of constraints in addition to a regularization constraint: the optical flow constraints which relate to the values of the time-varying images function at corresponding points of the successive image of the sequence, and the directional smoothness constraints, which relate the values of the neighboring velocity vectors. To achieve such a compromise, a system of nonlinear equations of the unknown estimate of the velocity vector field is used. A stable iterative method is used to solve this system. The optical flow and smoothness constraints are selectively suppressed in the neighborhoods of the occlusion boundaries. The last is accomplished by attaching a weight to each constraint. The spatial variations in the values of the time-varying image function near corresponding points of the successive images of the sequence, with the correspondence specified by a current estimate of the velocity vector field, and variation in the current estimate of the velocity vectors themselves are implicitly used to adjust the weighting function.

Claims

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

a. estimating a velocity vector field from a time-varying image sequence, said step of estimating including;

i. forming a matrix of image irradiance function values for each image of a time-varying image sequence;

ii. forming a multilevel resolution pyramid for each image of a time-varying image sequence by correlating on each level the matrix of image irradiance function values with a matrix of weights obtained by sampling a measurement function corresponding to that level and then by sampling on each level the function that resulted from the correlation at specific image locations;

iii. defining these specific images locations of each coarser level of the resolution pyramid by subsampling the specific image locations of the preceding finer level;

iv. selecting an initial estimate of the velocity vector field for the coarsest level of said multilevel pyramid and determining an improved estimate of the velocity vector field based on the initial estimate of the velocity vector;

v. projecting the improved estimate of the velocity vector field from the coarsest level of said multilevel pyramid to the next finer level of said multilevel resolution pyramid to obtain the initial estimate for that level and determining the improved estimate of the velocity vector of this level based on the initial estimate of the velocity vector;

vi. continuing the projection and determining step for each of the remaining levels of the multilevel resolution pyramid; and

vii. utilizing the improved estimate of the velocity vector field from the finest level of said multilevel resolution pyramid as the determined estimate of the velocity vector field; and

;

b. applying the determined estimate to modify at least one image in the time-varying sequence.

2. The method for estimating a velocity vector field from a time-varying image sequence according to claim 1 wherein the number of levels of said multilevel resolution pyramid are selected as a function of the degree of accuracy and the range with which the initial estimate of the velocity vector field can deviate from the unknown velocity vector field.

3. The method for estimating a velocity vector field from a time-varying image sequence according to claim 1 wherein at each level of said multilevel resolution pyramid, image functions and their first-order partial derivatives are computed from given successive digital images of the time-varying image sequence and the improved estimate of the velocity vector field is obtained by an iterative process applied to the initial estimate of the velocity vector field.

4. The method for estimating a velocity vector field from a time-varying image sequence according to claim 3 wherein each successive improvement of the initial estimate of the velocity vector field is obtained by adding an increment of the velocity vector field to the preceding improvement of the initial estimate of the velocity vector field with such increment being equal to a scaled factor of a solution of a system of linear equations.

5. The method for estimating a velocity vector field from a time-varying image sequence according to claim 1 wherein the measurement function of step ii is an infinitely differentiable function that is equal to zero at all points that are outside of a closed bounded subset of an image irradiance function.

6. The method for estimating a velocity vector field from a time-varying image sequence according to claim 4 and further comprising the step of:

using a basic iterative method to obtain the solution of the system of the linear equations.

7. The method for estimating a velocity vector field from a time-varying image sequence according to claim 4 and further comprising the step of:

using a conjugate gradient polynomial acceleration iterative method to obtain the solution of the system of linear equations.

8. The method for estimating a velocity vector field from a time-varying image sequence according to claim 4 and further comprising the step of:

using a Chebyshev polynomial acceleration iterative method to obtain the solution of the system of linear equations.

9. The method for estimating a velocity vector field from a time-varying image sequence according to claim 8 comprising the step of:

preconditioning the linear function arising from the system of linear equations.

10. The method for converting a time-varying image sequence from a first frame rate to a second frame rate comprising:

a. digitizing a time-varying image sequence taken at a first frame rate;

b. estimating a velocity vector field from the time-varying image sequence, said step of estimating including the steps of;

i. forming a matrix of image irradiance function values for each image of the time-varying image sequence;

ii. forming a multilevel resolution pyramid for each image of a time-varying image sequence by correlating on each level the matrix of image irradiance function values with a matrix of weights obtained by sampling a measurement function corresponding to that level and then by sampling on each level the function that resulted from the correlation at specific image locations;

iii. defining these specific image locations of each coarser level of the resolution pyramid by subsampling the specific image locations of the preceding finer level;

iv. selecting an initial estimate of the velocity vector field for the coarsest level of said multilevel pyramid and determining an improved estimate of the velocity vector field based on the initial estimate of the velocity vector;

v. projecting the improved estimate of the velocity vector field from the coarsest level of said multilevel pyramid to the next finer level of said multilevel resolution pyramid to obtain the initial estimate for that level and determining the improved estimate of the velocity vector of this level based on the initial estimate of the velocity vector;

vi. continuing the projection and determining step for each of the remaining levels of the multilevel resolution pyramid; and

vii. utilizing the improved estimate of the velocity vector field from the finest level of said multilevel resolution pyramid as the determined estimate of the velocity vector field;

c. predicting from two successive frames of the time-varying image sequence at least one intermediate frame from the determined estimate of the velocity vector field for the two successive frames; and

d. modifying the time-varying image sequence to include the intermediate frame.

11. A method for converting a time-varying image sequence from a first frame rate to a second frame rate comprising:

a. digitizing a time-varying image sequence taken at a first frame rate;

b. estimating a velocity vector field from the time-varying image sequence, said step of estimating including the steps of;

i. forming a matrix of image irradiance function values for each image of the time-varying image sequence;

ii. forming a multilevel resolution pyramid for each image of a time-varying image sequence by correlating on each level the matrix of image irradiance function values with a matrix of weights obtained by sampling a measurement function corresponding to that level and then by sampling on each level the function that resulted from the correlation at specific image locations;

iii. defining these specific image locations of each coarser level of the resolution pyramid by subsampling the specific image locations of the preceding finer level;

iv. selecting an initial estimate of the velocity vector field for the coarsest level of said multilevel pyramid and determining an improved estimate of the velocity vector field based on the initial estimate of the velocity vector;

v. projecting the improved estimate of the velocity vector field from the coarsest level of said multilevel pyramid to the next finer level of said multilevel resolution pyramid to obtain the initial estimate for that level and determining the improved estimate of the velocity vector of this level based on the initial estimate of the velocity vector;

vi. continuing the projection and determining step for each of the remaining levels of the multilevel resolution pyramid; and

vii. utilizing the improved estimate of the velocity vector field from the finest level of said multilevel resolution pyramid as the determined estimate of the velocity vector field;

c. deleting frames of the time-varying image sequence;

d. modifying the remaining frames of the time-varying image sequence based on the determined estimate of the velocity vector field to account for the deleted frames.

12. A method for enhancing a time-varying image sequence comprising:

a. digitizing a time-varying image sequence;

b. estimating a velocity vector field from the time-varying image sequence, said step of estimating including the steps of;

i. forming a matrix of image irradiance function values for each image of the time-varying image sequence;

ii. forming a multilevel resolution pyramid for each image of a time-varying image sequence by correlating on each level the matrix of image irradiance function values with a matrix of weights obtained by sampling a measurement function corresponding to that level and then by sampling on each level the function that resulted from the correlation at specific image locations;

iii. defining these specific image locations of each coarser level of the resolution pyramid by subsampling the specific image locations of the preceding finer level;

iv. selecting an initial estimate of the velocity vector field for the coarsest level of said multilevel pyramid and determining an improved estimate of the velocity vector field based on the initial estimate of the velocity vector;

v. projecting the improved estimate of the velocity vector field from the coarsest level of said multilevel pyramid to the next finer level of said multilevel resolution pyramid to obtain the initial estimate for that level and determining the improved estimate of the velocity vector of this level based on the initial estimate of the velocity vector;

vi. continuing the projection and determining step for each of the remaining levels of the multilevel resolution pyramid; and

vii. utilizing the improved estimate of the velocity vector field from the finest level of said multilevel resolution pyramid as the determined estimate of the velocity vector field;

c. averaging the determined estimate of the velocity vector field for three successive images in the time-varying image sequence and enhancing an intermediate image of the three successive images; and

d. repeating step c for each of the images in the time-varying image sequence and regenerating the time-varying image sequence with the enhanced images.

13. A method for motion compensated restoration of a time-varying image sequence comprising:

a. digitizing a time-varying image sequence;

b. estimating a velocity vector field from the time-varying image sequence, said step of estimating including the steps of;

i. forming a matrix of image irradiance function values for each image of the time-varying image sequence;

ii. forming a multilevel resolution pyramid for each image of a time-varying image sequence by correlating on each level the matrix of image irradiance function values with a matrix of weights obtained by sampling a measurement function corresponding to that level and then by sampling on each level the function that resulted from the correlation at specific image locations;

iii. defining these specific image locations of each coarser level of the resolution pyramid by subsampling the specific image locations of the preceding finer level;

iv. selecting an initial estimate of the velocity vector field for the coarses level of said multilevel pyramid and determining an improved estimate of the velocity vector field based on the initial estimate of the velocity vector;

v. projecting the improved estimate of the velocity vector field from the coarsest level of said multilevel pyramid to the next finer level of said multilevel resolution pyramid to obtain the initial estimate for that level and determining the improved estimate of the velocity vector of this level based on the initial estimate of the velocity vector;

vi. continuing the projection and determining step for each of the remaining levels of the multilevel resolution pyramid; and

vii. utilizing the improved estimate of the velocity vector field from the finest level of said multilevel resolution pyramid as the determined estimate of the velocity vector field;

c. determining from the determined estimate of the velocity vector field and a frame rate of the time-varying image sequence an amount of motion blur for an image in the time-varying image sequence; and

d. restoring said image using the determined amount of motion blur for said image.

14. A method for estimating velocity vector field from a time-varying image sequence, comprising for each velocity vector field the steps of:

a. forming a multi-level image resolution pyramid of image values utilizing the image irradiance values of at least a pair of images of a time-varying image sequence;

b. selecting an initial estimate of the velocity vector field for the first level of the image resolution pyramid;

c. forming a system of nonlinear equations utilizing the image values of the first level of the multi-level image resolution pyramid and the initial estimate of the velocity vector field for the first level of the multi-level image resolution pyramid;

d. taking the initial estimate as the current estimate of the velocity vector field for the first level of the multi-level image resolution pyramid;

e. forming a system of linear equations by linearizing the system of nonlinear equations about said current estimate;

f. determining an improved estimate of the velocity vector field for the first level of the multi-level image resolution pyramid by solving the system of linear equations of step e;

g. taking the improve estimate as the current estimate repeat steps e through g until the desired degree of improvement in the estimate of the velocity vector field for the first level of the multi-level image resolution pyramid is achieved;

h. projecting the resultant estimate of step g as the initial estimate of the next level of the multilevel image resolution pyramid and repeating steps c through g to obtain the resultant estimate for that level; and

i. repeating step h until the final level of the multi-level image resolution pyramid is reached with the resultant estimate being the desired estimate of the velocity vector field.