Method for region tracking in an image sequence using a two-dimensional mesh

• US 5,982,909 A
• Filed: 04/23/1996
• Issued: 11/09/1999
• Est. Priority Date: 04/23/1996
• Status: Expired due to Fees

• Current Assignee: Eastman Kodak Company
• Original Assignee: Eastman Kodak Company
• Inventors: Toklu, Candemir, Erdem, A. Tanju
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US08/636,622
• Time in Patent Office: 1,295 Days
• Field of Search: 382/103, 382/241, 382/236, 382/238, 382/107, 348/169, 348/699, 348/416
• US Class Current: 382/103
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 7/251 involving models

Abstract

A method for tracking a predetermined, two-dimensional portion of an image throughout a sequence of images, the method comprises the steps of selecting a reference frame; selecting the predetermined, two-dimensional portion within the reference frame by choosing a polygon that defines the boundary of the predetermined portion; fitting a reference mesh having at least three corner nodes and an inside node to the reference polygon; tracking the reference polygon in subsequent or previous image frames by tracking the corner nodes; mapping the reference mesh into the tracked polygon in the subsequent or previous image frames; and refining locations of the inside and corner nodes in the subsequent or previous image frames for tracking local and global motion of the predetermined portion.

Claims

1. A method for tracking a first predetermined, two-dimensional portion of an image throughout a sequence of images, the method comprising the steps of:

(a) selecting a reference frame;

(b) selecting the predetermined, two-dimensional portion within the reference frame by choosing a reference polygon having at least three comers that defines the boundary of the first predetermined region;

(c) fitting a reference mesh having corner nodes at the comers of the reference polygon and at least one inside node inside the reference polygon;

(d) predicting the reference polygon in subsequent or previous image frames by independently tracking the comers of the reference polygon;

(e1) dividing the reference polygon and the tracked polygon into a minimum number of triangles so that each triangle in the reference polygon respectively corresponds to a triangle in the tracked polygon;

(e2) finding parameters of affine transformation between each corresponding pair of triangles; and

(e3) mapping nodes in each triangle of the reference polygon into the respective triangle in the tracked polygon using the parameters of the corresponding affine transformation used for the triangle in which the node is located;

(f) refining locations of the inside and corner nodes of the corresponding mesh for tracking local and global motion of the first predetermined portion, wherein the steps (c) to (f) are implemented in a hierarchy of spatial resolutions;

(g) refining the location of boundary nodes on the reference mesh for tracking the local motion around the boundary of the first predetermined portion;

(h) tracking illumination changes that occurred between the reference frame and a previous or subsequent frame; and

(i) replacing the first predetermined portion with a second predetermined portion throughout a portion of the sequence of images so that the second predetermined portion undergoes the same global and local motion as the first predetermined portion;

wherein the corner, inside and boundary nodes divide the reference mesh into either triangular or rectangular patches or a combination of both triangular and rectangular patches;

wherein step (d) includes;

(d1) selecting a motion model for the corner nodes;

(d2) assigning a cost polygon to each corner node; and

(d3) estimating parameters of the motion model for each cost polygon and (d4) mapping the corner nodes with the estimated motion parameters.

2. The method as in claim 1, wherein step (d3) further includes defining a maximum range for estimating the parameters of the motion model.

3. The method as in claim 2, further comprising the step of refining the location of boundary nodes on the tracked polygon.

4. The method as in claim 3 further comprising the step of fitting a mesh to the second predetermined portion that corresponds in nodes and patches to the mesh in the reference polygon.

5. The method as in claim 4 further comprising the steps of finding parameters of affine transformation between each corresponding pair of patches in the second predetermined portion and the tracked polygon in the previous and subsequent image frames.

6. The method as in claim 5 further comprising the step of mapping pixels in each patch in the second predetermined portion into the corresponding patch in the tracked polygon using the parameters of the corresponding affine transformation.

7. An article of manufacture comprising:

a computer usable medium having computer readable program means embodied therein for causing tracking of a first predetermined, two-dimensional portion of an image throughout a sequence of images, the computer readable program code means in said article of manufacture comprising;

(a) computer readable program means for causing the computer to effect selecting a reference frame;

(b) computer readable program means for causing the computer to effect selecting the first predetermined, two-dimensional portion within the reference frame by choosing a reference polygon having at least three comers that defines the boundary of the first predetermined portion;

(c) computer readable program means for causing the computer to effect fitting a reference mesh having corner nodes at the comers of the reference polygon and at least one inside the reference polygon;

(d) computer readable program means for causing the computer to effect predicting the reference polygon in subsequent or previous image frames by independently tracking the corner of the reference polygon;

(e) computer readable program means for dividing the reference polygon and the tracked polygon into a minimum number of triangles so that each triangle in the reference polygon respectively corresponds to a triangle in the tracked polygon;

for finding parameters of affine transformation between each corresponding pair of triangles; and

for mapping nodes in each triangle of the reference polygon into the respective triangle in the tracked polygon using the parameters of the corresponding affine transformation used for the triangle in which the node is located;

(f) computer readable program means for causing the computer to effect refining locations of the inside and corner nodes of the corresponding mesh for tracking local and global motion of the first predetermined portion;

(g) means for causing the computer to effect defining the location of boundary nodes on the reference mesh for tracking the local motion around the boundary of the predetermined portion;

(h) means for causing the computer to effect tracking illumination changes that occurred between the reference frame and a previous or subsequent frame;

(i) means for causing said (c), (d), (e) and (f) computer readable program means to be implemented in a hierarchy of spatial resolutions;

(j) means for causing the computer to effect replacing the first predetermined portion with a second predetermined portion throughout a portion of the sequence of images so that the second predetermined portion undergoes the same global and local motion as the first predetermined portion, wherein the corner, inside and boundary nodes divide the reference mesh into either triangular or rectangular patches or a combination of both triangular and rectangular patches; and

(k) means for selecting a motion model for the corner nodes;

for assigning a cost polygon to each corner node;

for estimating parameters of the motion model for each cost polygon; and

for mapping the corner nodes with the estimated motion parameters.

8. The article of manufacture as in claim 7 further comprising computer readable program means for defining a maximum range for estimating the parameters of the motion model.

9. The article of manufacture as in claim 8 further comprising computer readable program means for refining the location of boundary nodes on the tracked polygon.

10. The article of manufacture as in claim 9 further comprising computer readable program means for fitting a mesh to the second predetermined portion that corresponds in nodes and patches to the mesh in the reference polygon.

11. The article of manufacture as in claim 10 further comprising computer readable program means for finding parameters of affine transformation between each corresponding pair of patches in the second predetermined portion and the tracked polygon in the previous and subsequent image frames.

12. The article of manufacture as in claim 11 further comprising computer readable program means for mapping pixels in each patch in the second predetermined portion into the corresponding patch in the tracked polygon using the parameters of the corresponding affine transformation.

13. A method for tracking a first predetermined, two-dimensional portion of an image throughout a sequence of images, the method comprising the steps of:

(a) selecting a reference frame;

(b) selecting the predetermined, two-dimensional portion within the reference frame by choosing a reference polygon having at least three corners that defines the boundary of the first predetermined region;

(c) fitting a reference mesh having corner nodes at the corners of the reference polygon and at least one inside node inside the reference polygon;

(d) predicting the reference polygon in subsequent or previous image frames by independently tracking the comers of the reference polygon;

(e) predicting a corresponding mesh in the subsequent or previous image frames by mapping the reference mesh into the tracked polygon using a plurality of different affine transformations;

(f) refining locations of the inside and corner nodes of the corresponding mesh for tracking local and global motion of the first predetermined portion;

wherein the steps (c) to (f) are implemented in a hierarchy of spatial resolutions;

(g) refining the location of boundary nodes on the reference mesh for tracking the local motion around the boundary of the first predetermined portion;

(h) tracking illumination changes that occurred between the reference frame and a previous or subsequent frame;

(i) replacing the first predetermined portion with a second predetermined portion throughout a portion of the sequence of images so that the second predetermined portion undergoes the same global and local motion as the first predetermined portion;

wherein the corner, inside and boundary nodes divide the reference mesh into either triangular or rectangular patches or a combination of both triangular and rectangular patches; and

wherein step (d) includes;

(d1) selecting a motion model for the corner nodes;

(d2) assigning a cost polygon to each corner node; and

(d3) estimating parameters of the motion model for each cost polygon and (d4) mapping the corner nodes with the estimated motion parameters.