Video object segmentation using active contour modelling with global relaxation

• US 6,546,117 B1
• Filed: 06/10/1999
• Issued: 04/08/2003
• Est. Priority Date: 06/10/1999
• Status: Expired due to Term

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Sun, Shijun, Kim, Yongmin
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): MILLER, MARTIN E
• Application Number:
  US09/323,501
• Time in Patent Office: 1,398 Days
• Field of Search: 382/103, 382/199, 382/224, 382/294, 382/215, 345/442, 600/443
• US Class Current: 382/103
• CPC Class Codes: G06T 7/254 involving subtraction of images
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns
• CPC Class Codes: G06V 10/34 Smoothing or thinning of the pattern; Morphological operations; Skeletonisation
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G06V 10/62 relating to a temporal dimension, e.g. time-based feature extraction; Pattern tracking
• CPC Class Codes: G06V 10/755 Deformable models or variational models, e.g. snakes or active contours

Abstract

A system for image object tracking and segmentation, includes (i) a modified adaptive resonance theory-2 (M-ART2) model for detecting changes of scenes, (ii) a two-dimensional correlative autopredicitve search (2D CAPS) method for object tracking, (iii) a derivation of contour energy for use in modelling an object edge, and (iv) an active contour model with global relaxation for defining optimal image object boundaries. The modelled object boundary is derived from an edge potential energy calculation and a set of current edge points. For each edge point, several candidate data points are also selected. Rather than calculate an energy value for each potential contours, a solution is achieved by comparing energy differences along a travel path. The selected contour is built in steps. An optimal path is selected from the potential paths.

Claims

1. A method for modelling a desired contour of an image object comprising:

receiving a first set of data points corresponding to the image object and a contour of the image object;

selecting a second set of N data points corresponding to an initial estimate of the contour;

for each one data point among said second set of data points, selecting a corresponding plurality of M candidate data points from the first set of data points, the second set of data points and the corresponding plurality of candidate data points forming an array of (M+1) by N data points;

selecting a starting set of M+1 data points, which includes a data point among the second set of data points and its corresponding plurality of M candidate data points;

for each data point among the starting set of M+1 data points, selecting an optimal object contour path to derive M+1 optimal object contour paths which estimate the contour of the image object, in which each one optimal contour path is selected segment by segment, wherein a next segment is added to said each one optimal object contour path by selecting one data point among an adjacent set of M+1 data points, the adjacent set of M+1 data points including a data point from the second set of data points and its corresponding plurality of candidate data points, the selected one data point for said next segment being selected by calculating an energy difference relative to the initial estimate of the contour for each one data point among said adjacent set of M+1 data points; and

selecting one of the M+1 optimal object contour paths.

2. The method of claim 1, further comprising the step of deriving edge potential energy for the first set of data points.

3. The method of claim 2, in which the step of selecting a corresponding plurality of M candidate data points from the first set of data points, comprises, for each one data point among said second set of data points:

grouping into M groups the data points in the vicinity of said one data point of the second set of data points, in which each one of the M groups includes a plurality of data points; and

selecting as a candidate data point, the data point from each one of the M groups which has the optimal edge potential energy.

4. The method of claim 1, in which the desired contour is tracked and modelled within a scene sequence of image frames, the method further comprising:

determining for a current image frame whether there has been a change of scene.

5. The method of claim 4, further comprising:

where there has not been a change in scene, searching the current image frame for presence of the image object; and

identifying said first set of data points corresponding to the image object where presence of the image object has been found.

6. The method of claim 1, in which the desired contour is tracked and modelled within a scene sequence of image frames, the method further comprising prior to said step of receiving:

searching the current image frame for presence of the image object; and

where presence of the image object has been found, identifying said first set of data points corresponding to the image object.

7. A method for tracking an image object within a sequence of frames and modelling a desired contour of the image object, the method comprising:

determining for a current image frame whether there has been a change of scene;

where there has not been a change in scene, searching the current image frame for presence of the image object;

where presence of the image object has been found, identifying a first set of data points corresponding to the image object and a second set of N data points corresponding to an initial estimate of the desired contour of the image object, wherein said second set of data points define a current object contour, the first set of data points including at least the second set of data points;

deriving edge potential energy for the first set of data points;

for each one data point among said second set of data points, selecting a corresponding plurality of M candidate data points from the first set of data points, the second set of data points and the corresponding plurality of candidate data points forming an array of (M+1) by N data points;

selecting a starting set of M+1 data points, which includes a data point among the second set of data points and its corresponding plurality of M candidate data points;

for each data point among the starting set of M+1 data points, selecting an optimal object contour path to derive M+1 optimal object contour paths which estimate the contour of the image object, in which each one optimal contour path is selected segment by segment, wherein a next segment is added to said each one optimal object contour path by selecting one data point among an adjacent set of M+1 data points, the adjacent set of M+1 data points including a data point from the second set of data points and its corresponding plurality of candidate data points, the selected one data point for said next segment being selected by calculating an energy difference relative to the current object contour for each one data point among said adjacent set of M+1 data points; and

selecting one of the M+1 optimal object contour paths.

8. The method of claim 7, in which the step of selecting a corresponding plurality of M candidate data points from the first set of data points, comprises, for each one data point among said second set of data points:

grouping into M groups, the data points in the vicinity of said one data point of the second set of data points, in which each one of the M groups includes a plurality of data points; and

selecting as a candidate data point, the data point from each one of the M groups which has the optimal edge potential energy.

9. An apparatus for modelling a desired contour of an image object, the apparatus receiving a first set of data points corresponding to the image object and the desired contour, the apparatus comprising:

means for selecting a second set of N data points corresponding to an initial estimate of the contour;

means for selecting, for each one data point among said second set of data points, a corresponding plurality of M candidate data points from the first set of data points, the second set of data points and the corresponding plurality of candidate data points forming an array of (M+1) by N data points;

means for selecting a starting set of M+1 data points, which includes a data point among the second set of data points and its corresponding plurality of M candidate data points;

means for selecting, for each data point among the starting set of M+1 data points, an optimal object contour path to derive M+1 optimal object contour paths which estimate the contour of the image object, in which each one optimal contour path is selected segment by segment, wherein a next segment is added to said each one optimal object contour path by selecting one data point among an adjacent set of M+1 data points, the adjacent set of M+1 data points including a data point from the second set of data points and its corresponding plurality of candidate data points, the selected one data point for said next segment being selected by calculating an energy difference relative to the current object contour for each one data point among said adjacent set of M+1 data points; and

means for selecting one of the M+1 optimal object contour paths.

10. The apparatus of claim 9, further comprising means for deriving edge potential energy for the first set of data points.

11. The apparatus of claim 10, in which the means for selecting a corresponding plurality of M candidate data points from the first set of data points, comprises:

means for grouping into M groups, for each one data point among said second set of data points, the data points in the vicinity of said one data point of the second set of data points, in which each one of the M groups includes a plurality of data points; and

means for selecting as a candidate data point, the data point from each one of the M groups which has the optimal edge potential energy.

12. The apparatus of claim 9, in which the desired contour is tracked and modelled within a scene sequence of image frames, the apparatus further comprising:

means for determining for a current image frame whether there has been a change of scene.

13. The apparatus of claim 12, further comprising:

means for searching the current image frame for presence of the image object, where there has not been a change in scene; and

means for identifying the first set of data points corresponding to the image object where presence of the image object has been found.

14. The apparatus of claim 9, in which the desired contour is tracked and modelled within a scene sequence of image frames, the apparatus further comprising:

means for searching the current image frame for presence of the image object; and

means for identifying the first set of data points corresponding to the image object where presence of the image object has been found.

15. An apparatus for modelling a desired contour of an image object, the apparatus receiving a first set of data points corresponding to the image object and the desired contour, the apparatus comprising:

a processor which selects a second set of N data points corresponding to an initial estimate of the contour;

a processor which selects, for each one data point among said second set of data points, a corresponding plurality of M candidate data points from the first set of data points, the second set of data points and the corresponding plurality of candidate data points forming an array of (M+1) by N data points;

a processor which selects a starting set of M+1 data points, which includes a data point among the second set of data points and its corresponding plurality of M candidate data points;

a processor which selects, for each data point among the starting set of M+1 data points, an optimal object contour path to derive M+1 optimal object contour paths which estimate the contour of the image object, in which each one optimal contour path is selected segment by segment, wherein a next segment is added to said each one optimal object contour path by selecting one data point among an adjacent set of M+1 data points, the adjacent set of M+1 data points including a data point from the second set of data points and its corresponding plurality of candidate data points, the selected one data point for said next segment being selected by calculating an energy difference relative to the current object contour for each one data point among said adjacent set of M+1 data points; and

a processor which selects one of the M+1 optimal object contour paths.

16. The apparatus of claim 15, wherein all the processors are embodied in a common processor.

17. The apparatus of claim 15, further comprising a processor which derives edge potential energy for the first set of data points.

18. The apparatus of claim 15, in which the processor which selects a corresponding plurality of M candidate data points from the first set of data points, comprises:

processing means for grouping into M groups, for each one data point among said second set of data points, the data points in the vicinity of said one data point of the second set of data points, in which each one of the M groups includes a plurality of data points; and

processing means for selecting as a candidate data point, the data point from each one of the M groups which has the optimal edge potential energy.

19. The apparatus of claim 15, in which the desired contour is tracked and modelled within a scene sequence of image frames, the apparatus further comprising:

processing means for determining for a current image frame whether there has been a change of scene.

20. The apparatus of claim 15, in which the desired contour is tracked and modelled within a scene sequence of image frames, the apparatus further comprising:

processing means for searching the current image frame for presence of the image object; and

processing means for identifying the first set of data points corresponding to the image object where presence of the image object has been found.