Method and apparatus for tracking a moving object

• US 5,280,530 A
• Filed: 09/05/1991
• Issued: 01/18/1994
• Est. Priority Date: 09/07/1990
• Status: Expired due to Term

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Trew, Timothy I. P., Seeling, Gabriele C.
• Primary Examiner(s): Razavi, Michael T.
• Assistant Examiner(s): KLOCINSKI, STEVEN
• Application Number:
  US07/755,384
• Time in Patent Office: 866 Days
• Field of Search: 382/1, 382/48, 382/30, 382/16, 382/34, 382/36, 382/42, 358/105, 358/125, 342/64, 364/510, 395/152
• US Class Current: 382/103
• CPC Class Codes: G01S 3/7864 T.V. type tracking systems
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30201 Face
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: G06T 7/248 involving reference images or patches
• CPC Class Codes: G06V 10/62 relating to a temporal dimension, e.g. time-based feature extraction; Pattern tracking
• CPC Class Codes: G06V 40/161 Detection; Localisation; Normalisation
• CPC Class Codes: G06V 40/168 Feature extraction; Face representation
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/543 using regions
• CPC Class Codes: H04N 7/141 between two video terminals, e.g. videophone telephonic communication systems combined with television receiver for reception of entertainment or information matter H04M11/085

Abstract

A method of tracking a moving object in a scene, for example the face of a person in videophone applications, comprises forming an initial template of the face, extracting a mask outlining the face, dividing the template into a plurality (for example sixteen) sub-templates, searching the next frame to find a match with the template, searching the next frame to find a match with each of the sub-templates, determining the displacements of each of the sub-templates with respect to the template, using the displacements to determine affine transform coefficients and performing an affine transform to produce an updated template and updated mask.

Claims

1. A method of tracking the movement of a three dimensional object in a scene over a series of two dimensional picture frames, the method comprising the steps of

a) forming an initial template in an initial frame of the series, said initial template including the moving object to be tracked;

b) dividing said initial template into a plurality of sub-templates which are not associated with specific features of said object;

c) searching a subsequent frame of said series to locate a first region of said subsequent frame which matches said initial template and determining a first displacement in position between said initial template and said first region of said subsequent frame;

d) searching said subsequent frame of said series to locate respective sub-regions of said subsequent frame of said series which match respective sub-templates of the initial template and determining respective additional displacements in position between each sub-template and its respective matched sub-region of said subsequent frame;

e) determining from the first displacement and the additional displacements, a relative displacement in position between said first region of said subsequent frame and said respective sub-regions of said subsequent frame;

f) using said relative displacement to determine coefficients for a bivariate transform capable of mapping said first and additional displacements in position; and

g) performing said bivariate transform to produce an updated initial template.

2. A method as claimed in claim 1 comprising the further steps of:

a) extracting a mask from the initial frame outlining said object;

b) producing an updated mask using said bivariate transform; and

c) determining the boundary of said updated initial template using said updated mask.

3. A method as claimed in claim 1 or claim 2 in which the search for each of the sub-regions is restricted to a limited area with respect to said first region.

4. A method as claimed in claim 2 comprising the further step of:

setting the luminance of each pixel within the mask to a first constant value and setting the luminance of each pixel outside the mask to a second constant value.

5. A method as claimed in claim 1, comprising the further step of

discarding each sub-template in which the object to be tracked occupies less than a given portion of that subtemplate'"'"'s area.

6. A method as claimed in claim 1 comprising the further steps of:

discarding any sub-template for which a respective sub-region cannot be found,

determining whether a minimum number of sub-templates remain, and if so

using their respective additional displacements to calculate said coefficients.

7. A method as claimed in claim 6 in which when less than the minimum number of sub-templates remain, the search area for matching the initial template is increased for the subsequent frame.

8. A method as claimed in claim 2 comprising the further steps of:

a) comparing the updated initial template with a second region of the subsequent frame corresponding to said updated mask, and

b) using the results of the comparison to control the gain correction term of a Kalman filter.

9. A method as claimed in claim 2 in which the bivariate transform is an affine transform.

10. An apparatus for tracking the movement of a three dimensional object in a scene over a series of two dimensional picture frames, said apparatus comprising in combination:

a) means for forming an initial template in an initial frame of the series, said initial template including the moving object to be tracked;

b) means for dividing said initial template into a plurality of sub-templates which are not associated with specific features of said object;

c) means for searching a subsequent frame of said series to locate a first region of said subsequent frame which matches said initial template and determining a first displacement in position between said initial template and said first region of said subsequent frame;

d) means for searching said subsequent frame of said series to locate respective sub-regions of said subsequent frame of said series which match respective sub-templates of the initial template and determining respective additional displacements in position between each sub-template and its respective matched sub-regions of said subsequent frame;

e) means for determining from the first displacement and the additional displacements, a relative displacement in position between said first region of said subsequent frame and said respective sub-regions of said subsequent frame;

f) means for determining coefficients for a bivariate transform capable of mapping said first and additional displacements in position using said relative displacement; and

g) means for performing said bivariate transform to produce an updated initial template.

11. The apparatus as claimed in claim 10, further comprising:

a) means for extracting a mask from the initial frame outlining said object;

b) means for producing an updated mask using said bivariate transform; and

c) means for determining the boundary of said updated initial template using said updated mask.

12. Apparatus as claimed in claim 11 further comprising means for comparing the updated initial template with a second region of the subsequent frame corresponding to said updated mask and using the results of the comparison to control the gain correction term of a Kalman filter.

13. Apparatus as claimed in claim 10 further comprising means for discarding any sub-template for which a respective sub-region cannot be found, means for determining whether a minimum number of sub-templates remain, and means for, where a minimum number remain, using their respective additional displacements to calculate the coefficients.