Patent US6574353B1 successfully refreshed from Google Patents.
US6574353B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Video object tracking using a hierarchy of deformable templates
Assignee: WASHINGTON, University of
•
Filing: 2000-02-08
•
Granted: 2003-06-03
•
Expires: 2020-02-08
Abstract
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.
Inventors
- 👤 Todd Schoepflin
- 👤 Vikram Chalana
- 👤 David Haynor
- 👤 Yongmin Kim
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 10:48
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/20; G06T7/246; G06V; G06V10/00; G06V10/70; G06V10/74; G06V10/75; G06V10/754; G06V10/40; G06V10/62
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
243 words
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.
Claim 2
Independent Claim
243 words
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.
Claim 3
Dependent Claim
127 words
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.
Claim 4
Dependent Claim
35 words
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.
Claim 5
Dependent Claim
47 words
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.
Claim 6
Dependent Claim
49 words
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.
Claim 7
Independent Claim
296 words
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.
Claim 8
Independent Claim
296 words
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.
Claim 9
Dependent Claim
18 words
The method of claim 6 , in which the boundary deformation to test is a global boundary deformation.
Claim 10
Dependent Claim
29 words
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.
Claim 11
Dependent Claim
40 words
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.
Claim 12
Independent Claim
205 words
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.
Claim 13
Independent Claim
205 words
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.
Claim 14
Dependent Claim
71 words
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.
Claim 15
Dependent Claim
40 words
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.
Claim 16
Dependent Claim
70 words
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.
Claim 17
Independent Claim
247 words
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.
Claim 18
Independent Claim
247 words
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.
Claim 19
Dependent Claim
143 words
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.
Claim 20
Dependent Claim
46 words
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.
Claim 21
Dependent Claim
48 words
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.
Claim 22
Dependent Claim
39 words
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.
Claim 23
Independent Claim
324 words
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.
Claim 24
Independent Claim
324 words
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.
Claim 25
Dependent Claim
18 words
The system of claim 19 , in which the boundary deformation to test is a global boundary deformation.
Claim 26
Dependent Claim
29 words
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.
Claim 27
Dependent Claim
42 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-06-02 | 2006-12-02 | 2007-06-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-06-02 | 2010-12-02 | 2011-06-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-06-02 | 2014-12-02 | 2015-06-03 | $7700.00 | Window Closed / Lapsed |