Video object tracking using a hierarchy of deformable templates

• US 6,574,353 B1
• Filed: 02/08/2000
• Issued: 06/03/2003
• Est. Priority Date: 02/08/2000
• Status: Expired due to Term

• Current Assignee: Washington University In St Louis
• Original Assignee: University of Washington
• Inventors: Chalana, Vikram, Haynor, David, Kim, Yongmin, Schoepflin, Todd
• Primary Examiner(s): Chang, Jon
• Assistant Examiner(s): KIM, CHONG R
• Application Number:
  US09/500,403
• Time in Patent Office: 1,211 Days
• Field of Search: 382/103, 382/107, 382/236, 382/215, 348/169, 348/413.1, 348/414.1, 348/416.1, 348/417.1
• US Class Current: 382/103
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06V 10/62 relating to a temporal dimension, e.g. time-based feature extraction; Pattern tracking
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching

Abstract

A hierarchy of deformation operations is implemented to deform a template and match the deformed template to an object in a video frame. At each level, the constraints on the template deformations are relaxed, while the spatial range of the object boundary search is narrowed. At a highest level, an initial template is translated, rotated and scaled to coarsely locate the object within a given image frame. At a middle level, an affine transformation is implemented, globally or locally, to deform the template. For a local affine transformation process, a sup-portion, such as an articulation or appendage portion of the template is deformed. The middle level refines the template to get the template boundary close to the actual object boundary within a given frame. At the lowest level, a local segmentation algorithm is applied to deform the now close boundary to finely match the object boundary.

Claims

1. A method for tracking an object among a plurality of image frames, comprising the steps of:

altering an initial template using a first set of deformation constraints and searching for a boundary of the object within a first spatial range of a first image frame of the plurality of image frames to coarsely locate the object within the first image frame, wherein a first deformed template is achieved from the initial template to coarsely locate the object;

deforming the first deformed template over a second spatial range using a second set of deformation constraints which are more relaxed than the first set of deformation constraints and searching for the boundary of the object to more accurately locate the object within the first image frame, wherein the second spatial range is narrower than the first spatial range, wherein a second deformed template is achieved from the first deformed template to more accurately locate the object; and

in which the step of deforming the first deformed template using a second set of deformation constraints, comprises applying an affine transformation of the first deformed template, wherein the affine transformation is applied globally to the first deformed template, and the step of applying the affine transformation achieves an interim deformed template, and wherein the step of deforming the first deformed template using a second set of deformation constraints, further comprises applying a local affine transformation to a sub-portion of the interim deformed template to alter the sub-portion.

2. The method of claim 1, further comprising the step of

deforming the second deformed template over a third spatial range using a third set of deformation constraints which are more relaxed than the second set of deformation constraints and searching for the boundary of the object to finely locate the object within the first image frame, wherein the third spatial range is narrower than the second spatial range, wherein a third deformed template is achieved from the second deformed template to finely locate the object,

in which the third deformed template becomes the initial template for processing a second image frame of the plurality of image frames, and wherein each step recited in claim 1 is repeated for locating the object within the second image frame.

3. The method of claim 1, in which the step of altering the initial template using a first set of deformation constraints, comprises any one or more of translating, rotating and scaling the initial template.

4. The method of claim 1, in which the step of deforming the first deformed template using a second set of deformation constraints, comprises applying a local affine transformation to a boundary of a sub-portion of the first deformed template to alter the boundary of the sub-portion.

5. The method of claim 4, further comprising, prior to the step of deforming the initial template, the step of identifying an articulating portion of the object in an initial image frame, and defining a sub-portion of the initial template which corresponds to the articulating portion of the object.

9. The method of claim 2, in which the step of deforming the second deformed template using a third set of deformation constraints comprises applying a local segmentation algorithm to deform the second deformed template within the third spatial range.

6. A method for tracking an object among a plurality of image frames, comprising the steps of:

altering an initial template using a first set of deformation constraints and searching for a boundary of the object within a first spatial range of a first image frame of the plurality of image frames to coarsely locate the object within the first image frame, wherein a first deformed template is achieved from the initial template to coarsely locate the object;

deforming the first deformed template over a second spatial range using a second set of deformation constraints which are more relaxed than the first set of deformation constraints and searching for the boundary of the object to more accurately locate the object within the first image frame, wherein the second spatial range is narrower than the first spatial range, wherein a second deformed template is achieved from the first deformed template to more accurately locate the object; and

in which the step of deforming the first deformed template using a second set of deformation constraints, comprises

defining and updating a set of affine parameters;

using the updated set of affine parameters to test a boundary deformation of the first deformed template;

deriving an energy value for the boundary deformation being tested using the updated set of affine parameters;

testing the energy value against a minimum energy value;

when the minimum energy value is greater than the tested energy value, accepting the tested energy value as the minimum energy value and the set of affine parameters as a best set of affine parameters; and

repeating the steps of defining, using, deriving, testing and accepting for a number of iterations resulting in one best set of affine parameters and one minimum energy value which are subsequently used to redefine said boundary.

7. The method of claim 6, in which the boundary deformation to test is a global boundary deformation.

8. The method of claim 6, in which the boundary deformation to test is a local boundary deformation of a sub-portion of the boundary of the first deformed template.

10. A method for tracking an object among a plurality of image frames, comprising the steps of:

selecting an object to be tracked;

defining a template from the selected object;

defining a boundary of sub-portion of the template which is smaller than the template;

calculating a set of affine parameters for the sub-portion boundary, the set of affine parameters corresponding to a first deformation of the sub-portion boundary;

using the set of affine parameters to test the first deformation of the sub-portion boundary, the step of using comprising;

(i) deriving an energy value for the first deformation of the sub-portion boundary using the set of affine parameters;

(ii) testing the energy value against a minimum energy value; and

(iii) when the minimum energy value is greater than the tested energy value, accepting the tested energy value as the minimum energy value and the set of affine parameters as a best set of affine parameters;

repeating the steps of calculating and using for a number of deformations of the sub-portion boundary for a given image frame to be processed of the plurality of image frames, resulting in one best set of affine parameters and one minimum energy value which are subsequently used to redefine the sub-portion boundary.

11. The method of claim 10, further comprising the step of:

performing the steps of calculating, using and repeating for said plurality of image frames, in which the redefined sub-portion boundary for a given image frame among the plurality of image frames is used as the sub-portion boundary for which the set of affine parameters are calculated for a next image frame to be processed among the plurality of image frames.

12. The method of claim 10, further comprising the step of:

after the step of repeating applying a local segmentation algorithm to at least the redefined sub-portion boundary to estimate a location of a boundary of the object being tracked.

13. The method of claim 10, further comprising prior to the step of calculating, the step of adjusting an initial template corresponding to the selected object being tracked to coarsely estimate a location of the object being tracked in another image frame among the plurality of image frames, wherein the step of adjusting comprises any one or more of translating, rotating and scaling the initial template, including the sub-portion boundary.

14. A system for tracking an object among a plurality of image frames, comprising:

means for altering an initial template using a first set of deformation constraints and searching for a boundary of the object within a first spatial range of a first image frame of the plurality of image frames to coarsely locate the object within the first image frame, wherein a first deformed template is achieved from the initial template to coarsely locate the object;

means for deforming the first deformed template over a second spatial range using a second set of deformation constraints which are more relaxed than the first set of deformation constraints and searching for the boundary of the object to more accurately locate the object within the first image frame, wherein the second spatial range is narrower than the first spatial range, wherein a second deformed template is achieved from the first deformed template to more accurately locate the object;

wherein the means for deforming the first deformed template using a second set of deformation constraints, comprises means for applying an affine transformation to the first deformed template, in which the affine transformation is applied globally to the first deformed template, and the means for applying the affine transformation achieves an interim deformed template, and wherein the means for deforming the first deformed template using a second set of deformation constraints, further comprises means for applying a local affine transformation to a sub-portion of the interim deformed template to alter the sub-portion.

15. The system of claim 14, further comprising means for deforming the second deformed template over a third spatial range using a third set of deformation constraints which are more relaxed than the second set of deformation constraints and searching for the object to finely locate the object within the first image frame, wherein the third spatial range is narrower than the second spatial range, wherein a third deformed template is achieved from the second deformed template to finely locate the object;

in which the third deformed template becomes the initial template for processing a second image frame of the plurality of image frames, and wherein means for altering the initial template, the means for deforming the first deformed template and the means for deforming the second deformed template process the second image frame to track the object within the second image frame.

16. The system of claim 14, in which the means for altering the initial template using a first set of deformation constraints, comprises means for translating location of the initial template, means for rotating orientation of the initial template and means for scaling the initial template.

17. The system of claim 14, in which means for deforming the first deformed template using a second set of deformation constraints, comprises means for applying a local affine transformation to a boundary of a sub-portion of the first deformed template to alter the boundary of the sub-portion.

18. The system of claim 17, further comprising, means for identifying an articulating portion of the object in an initial image frame, and defining a sub-portion of the initial template which corresponds to the articulating portion of the object.

22. The system of claim 15, in which the means for deforming the second deformed template using a third set of deformation constraints comprises means for applying a local segmentation algorithm to deform the second deformed template within the third spatial range.

19. A system for tracking an object among a plurality of image frames, comprising:

means for altering an initial template using a first set of deformation constraints and searching for a boundary of the object within a first spatial range of a first image frame of and plurality of image frames to coarsely locate the object within the first image frame, wherein a first deformed template is achieved from the initial template to coarsely locate the object;

means for deforming the first deformed template over a second spatial range using a second set of deformation constraints which are more relaxed than the first set of deformation constraints and searching for the boundary of the object to more accurately locate the object within the first image frame, wherein the second spatial range is narrower than the first spatial range, wherein a second deformed template is achieved from the first deformed template to more accurately locate the object;

wherein the means for deforming the first deformed template using a second set of deformation constraints, comprises;

means for defining and updating a set of affine parameters;

means for using the updated set of affine parameters to test a boundary deformation of the first deformed template;

means for deriving an energy value for the boundary deformation being tested using the updated set of affine parameters;

means for testing the energy value against a minimum energy value;

means for accepting the tested energy value as the minimum energy value and the set of affine parameters as a best set of affine parameters when the minimum energy value is greater than the tested energy value;

wherein the means for defining, means for using, means for deriving, means for testing and means for accepting perform a number of iterations resulting in one best set of affine parameters and one minimum energy value which are subsequently used to redefine said boundary for a given image frame in which the object is being tracked.

20. The system of claim 19, in which the boundary deformation to test is a global boundary deformation.

21. The system of claim 19, in which the boundary deformation to test is a local boundary deformation of a sub-portion of the boundary of the first deformed template.