Detecting and segmenting local deformation in a tracked video object

• US 6,678,416 B1
• Filed: 02/08/2000
• Issued: 01/13/2004
• Est. Priority Date: 02/08/2000
• Status: Expired due to Fees

• Current Assignee: Washington University In St Louis
• Original Assignee: University of Washington
• Inventors: Sun, Shijun, Kim, Yongmin
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US09/500,116
• Time in Patent Office: 1,435 Days
• Field of Search: 348/384.1, 348/394--39, 348/400--40, 348/407--41, 348/420--42, 348/425.2, 348/430--43, 382/232, 382/233, 382/236, 382/238, 382/240, 382/242, 382/248, 382/250
• US Class Current: 382/235
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/149 involving deformable models, e.g. active contour models
• CPC Class Codes: G06T 7/251 involving models

Abstract

A coarsely estimated object boundary is formed by a sequence of edge boundary points. A local affine transformation along the estimated object boundary is identified by analyzing edge energy of a current image frame. A sequence of edge boundary points which have edge energy change ratios exceeding a threshold value is identified as a local affine transformation. A refined estimate of the object boundary is determined for the local affine transformation using a local segmentation process based on a key contour point search strategy. End points of the contour are assumed to be known. An initial key contour point is derived from the coarsely estimate object boundary. Candidate key points then are derived and corresponding curves analyzed to select a curve as the improved estimated boundary for the local affine transformation. The curve having a minimum average edge energy change ratio is selected.

Claims

1. A method for identifying a local affine deformation occurring along an estimate of an object boundary, in which the estimated object boundary corresponds to an object being tracked among a plurality of image frames, comprising:

calculating an edge energy change ratio for a plurality of edge points describing said estimated object boundary; and

identifying a portion of said object boundary less than an entire length of said object boundary as exhibiting a local affine deformation based upon said edge energy change ratio, wherein said step of identifying the portion of said object boundary comprises identifying a sequence of edge points among said plurality of edge points for which the calculated edge energy change ratio exceeds a prescribed threshold for each edge point in said sequence of edge points.

2. The method of claim 1, wherein a beginning edge point and an ending edge point of said sequence of edge points are identified in said step of identifying a sequence of edge points, and wherein said step of identifying the portion of said object boundary further comprises extending the sequence of edge points until the edge energy change ratio for preceding edge points describing the estimated object boundary no longer changes continuously.

3. The method of claim 2, wherein said step of extending the sequence further comprises extending the sequence of edge points until the edge energy change ratio for succeeding edge points describing the estimated object boundary no longer changes continuously.

4. A method for identifying a local affine deformation occurring along an estimate of an object boundary, comprising:

deriving edge information for the estimated object boundary;

identifying a portion of said object boundary less than an entire length of said object boundary as exhibiting a local affine deformation based upon said derived edge information; and

executing a local segmentation process on the identified portion of said object boundary exhibiting the local affine deformation to revise the estimated object boundary for the identified portion, said identified portion being a local affine portion of the estimated object boundary the local affine portion having a starting contour point and an ending contour point.

5. The method of claim 4, in which the step of executing comprises:

identifying a plurality of candidate key contour points within a search area;

for each one candidate key contour point of the plurality of candidate key contour points, deriving an associated candidate curve corresponding to said one candidate key contour point, wherein said associated candidate curve includes the starting contour point, the ending contour point and said corresponding one key contour point, wherein for said plurality of candidate key contour points a plurality of associated candidate curves are derived; and

selecting one of said plurality of associated candidate curves as a revised estimate of the object boundary for the local affine portion based upon an analysis of edge energy.

6. The method of claim 5, further comprising prior to the step of selecting, the step of deriving an average edge energy change ratio for each one of said plurality of associated candidate curves.

7. The method of claim 6, wherein the step of selecting comprises identifying the candidate curve among the plurality of associated candidate curves which has a minimum average edge energy change ratio and selecting the identified candidate curve as the revised estimate of the object boundary for the local affine portion.

8. The method of claim 5, wherein the step of deriving the associated candidate curve comprises:

deriving a set of local affine parameters based on the starting contour point, the ending contour point and said one candidate key contour point; and

modifying the local affine portion of the estimated object boundary based on the derived set of local affine parameters to achieve the associated candidate curve for said one candidate key contour point.

9. A method for revising an estimate of an object boundary for a local affine portion of the estimated object boundary, wherein the local affine portion has a starting contour point and an ending contour point, comprising the steps of:

identifying a plurality of candidate key contour points within a search area;

for each one candidate key contour point of the plurality of candidate key contour points, deriving an associated candidate curve corresponding to said one candidate key contour point, wherein said associated candidate curve includes the starting contour point, the ending contour point and said corresponding one key contour point, wherein for said plurality of candidate key contour points a plurality of associated candidate curves are derived; and

selecting one of said plurality of associated candidate curves as a revised estimate of the object boundary for the local affine portion based upon an analysis of edge energy.

10. The method of claim 9, further comprising prior to the step of selecting, the step of deriving an average edge energy change ratio for each one of said plurality of associated candidate curves.

11. The method of claim 10, wherein the step of selecting comprises identifying the candidate curve among the plurality of associated candidate curves which has a minimum average edge energy change ratio and selecting the identified candidate curve as the revised estimate of the object boundary for the local affine portion.

12. The method of claim 9, wherein the step of deriving the associated candidate curve comprises:

deriving a set of local affine parameters based on the starting contour point, the ending contour point and said one candidate key contour point; and

modifying the local affine portion of the estimated object boundary based on the derived set of local affine parameters to achieve the associated candidate curve for said one candidate key contour point.

13. The method of claim 9, further comprising prior to the step of identifying the plurality of candidate key contour points, the step of identifying an initial key contour point on the estimated object boundary which resides between the starting contour point and the ending contour point.

14. The method of claim 13, wherein the search area is defined based upon a distance function of the initial key contour point.

15. The method of claim 9, said revising said estimate of the object boundary for the local affine portion of the estimated object boundary is performed for a plurality of image frames, and wherein the step of identifying the plurality of candidate key contour points, comprises:

for each one image point of a plurality of image points within the search area, comparing edge energy of said one image point with edge energy of a final key contour point corresponding to the selected candidate curve for a previous image frame; and

identifying each image point of said plurality of image points within the search as a candidate key contour point for a current image frame when the edge energy of said image point is at least a prescribed percentage of the edge energy of the final key contour point.

16. An apparatus for identifying a local affine deformation occurring along an estimate of an object boundary, in which the estimated object boundary corresponds to an object being tracked among a plurality of image frames, comprising:

means for calculating an edge energy change ratio for a plurality of edge points describing said estimated object boundary, and means for identifying a portion of said object boundary less than an entire length of said object boundary as exhibiting a local affine deformation based upon said edge energy change ratio, wherein said means for identifying the portion of said object boundary comprises means for identifying a sequence of edge points among said plurality of edge points for which the calculated edge energy change ratio exceeds a prescribed threshold for each edge point in said sequence of edge points.

17. The apparatus of claim 16, wherein a beginning edge point and an ending edge point of said sequence of edge points are identified by said means for identifying the sequence of edge points, and wherein said means for identifying the portion of said object boundary further comprises means for extending the sequence of edge points until the edge energy change ratio for preceding edge points describing the estimated object boundary no longer changes continuously.

18. The apparatus of claim 17, wherein said means for extending the sequence further comprises means for extending the sequence of edge points until the edge energy change ratio for succeeding edge points describing the estimated object boundary no longer changes continuously.

19. An apparatus for identifying a local affine deformation occurring along an estimate of an object boundary, comprising:

means for deriving edge information for the estimated object boundary;

means for identifying a portion of said object boundary less than an entire length of said object boundary as exhibiting a local affine deformation based upon said derived edge information; and

means for executing a local segmentation process on the identified portion of said object boundary exhibiting the local affine deformation to revise the estimated object boundary for the identified portion, said identified portion being a local affine portion of the estimated object boundary the local affine portion having a starting contour point and an ending contour point.

20. The apparatus of claims 19, in which the executing means comprises:

means for identifying a plurality of candidate key contour points within a search area;

means for deriving, for each one candidate key contour point of the plurality of candidate key contour points, an associated candidate curve corresponding to said one candidate key contour point, wherein said associated candidate curve includes the starting contour point, the ending contour point and said corresponding one key contour point, wherein for said plurality of candidate key contour points a plurality of associated candidate curves are derived; and

means for selecting one of said plurality of associated candidate curves as a revised estimate of the object boundary for the local affine portion based upon an analysis of edge energy.

21. An apparatus for revising an estimate of an object boundary for a local affine portion of the estimated object boundary, wherein the local affine portion has a starting contour point and an ending contour point, comprising:

means for identifying a plurality of candidate key contour points within a search area;

means for deriving, for each one candidate key contour point of the plurality of candidate key contour points, an associated candidate curve corresponding to said one candidate key contour point, wherein said associated candidate curve includes the starting contour point, the ending contour point and said corresponding one key contour point, wherein for said plurality of candidate key contour points a plurality of associated candidate curves are derived; and

means for selecting one of said plurality of associated candidate curves as a revised estimate of the object boundary for the local affine portion based upon an analysis of edge energy.

22. The apparatus of claim 21, further comprising:

means for deriving an average edge energy change ratio for each one of said plurality of associated candidate curves.

23. The apparatus of claim 22, wherein the selecting means comprises means for identifying the candidate curve among the plurality of associated candidate curves which has a minimum average edge energy change ratio and selecting the identified candidate curve as the revised estimate of the object boundary for the local affine portion.

24. The apparatus of claim 21, wherein the means for deriving the associated candidate curve comprises:

means for deriving a set of local affine parameters based on the starting contour point, the ending contour point and said one candidate key contour point; and

means for modifying the local affine portion of the estimated object boundary based on the derived set of local affine parameters to achieve the associated candidate curve for said one candidate key contour point.

25. The apparatus of claim 21, further comprising means for identifying an initial key contour point on the estimated object boundary which resides between the starting contour point and the ending contour point.

26. The apparatus of claim 25, wherein the search area is defined based upon a distance function of the initial key contour point.

27. The apparatus of claim 21, wherein said the revising of said estimate of the object boundary for the local affine portion of the estimated object boundary is performed for a plurality of image frames, and wherein the means for the plurality of candidate key contour points, comprises:

means for comparing, for each one image point of a plurality of image points within the search area, edge energy of said one image point with edge energy of a final key contour point corresponding to the selected candidate curve for a previous image frame; and

means for identifying each image point of said plurality of image points within the search as a candidate key contour point for a current image frame when the edge energy of said image point is at least a prescribed percentage of the edge energy of the final key contour point.