Probabilistic exemplar-based pattern tracking

• US 7,167,578 B2
• Filed: 12/09/2005
• Issued: 01/23/2007
• Est. Priority Date: 02/22/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Toyama, Kentaro, Blake, Andrew
• Primary Examiner(s): Mehta; Bhavesh M.
• Assistant Examiner(s): MACKOWEY, ANTHONY M
• Application Number:
  US11/298,798
• Publication Number:
  US 20060093188A1
• Time in Patent Office: 410 Days
• Field of Search: 382/103, 382/224, 382/225, 382/228
• US Class Current: 382/103
• CPC Class Codes: G06F 18/28 Determining representative reference patterns, e.g. by averaging or distorting; Generating dictionaries
• CPC Class Codes: G06T 7/277 involving stochastic approaches, e.g. using Kalman filters
• CPC Class Codes: G06V 10/62 relating to a temporal dimension, e.g. time-based feature extraction; Pattern tracking

Abstract

The present invention involves a new system and method for probabilistic exemplar-based tracking of patterns or objects. Tracking is accomplished by first extracting a set of exemplars from training data. The exemplars are then clustered using conventional statistical techniques. Such clustering techniques include k-medoids clustering which is based on a distance function for determining the distance or similarity between the exemplars. A dimensionality for each exemplar cluster is then estimated and used for generating a probabilistic likelihood function for each exemplar cluster. Any of a number of conventional tracking algorithms is then used in combination with the exemplars and the probabilistic likelihood functions for tracking patterns or objects in a sequence of images, or in a space, or frequency domain.

Claims

1. A method for automatic probabilistic pattern tracking comprising steps for:

automatically learning a set of exemplars from at least one set of training data;

clustering the exemplars into more than one cluster of exemplars, with each cluster having a representative exemplar at a cluster center;

generating an observation likelihood function for each exemplar cluster based on a computed distance between the exemplars in each cluster;

providing the exemplar clusters, observation likelihood functions, and target data to a probabilistic tracking function; and

probabilistically tracking at least one pattern in the target data by using the exemplar clusters, observation likelihood functions, and target data to predict at least one target state.

2. The method of claim 1 wherein generating the observation likelihood functions comprises steps for estimating a dimensionality of each exemplar cluster.

3. The method of claim 1 wherein the training data is image data, and further comprising steps for extracting contour-based exemplars from the training data.

4. The method of claim 3 further comprising steps for using the contour-based exemplars for probabilistically tracking at least one object in a sequence of images.

5. The method of claim 1 further comprising steps for iteratively updating the observation likelihood functions while tracking patterns in the target data.

6. The method of claim 1 wherein the target data is space-based data, and wherein the steps for probabilistically tracking at least one pattern in the target data further comprises steps for tracking at least one pattern in a space-domain.

7. The method of claim 1 wherein the target data is a sequence of images, and wherein probabilistically tracking at least one pattern in the target data comprises tracking at least one pattern in the sequence of images.

8. The method of claim 1 wherein the target data is frequency-based data, and wherein the steps for probabilistically tracking at least one pattern in the target data further comprises steps for tracking at least one pattern in a frequency-domain.

9. A computer-readable medium having computer executable instructions for generating a set of observation likelihood functions from a set of exemplars, said computer executable instructions comprising:

deriving more than one exemplar from at least one set of training data to create a set of exemplars;

randomly selecting more than one exemplar from the set of exemplars;

iteratively clustering similar exemplars from the set of exemplars around the randomly selected exemplars to form an exemplar cluster for each of the randomly selected exemplars;

estimating a dimensionality for each of the exemplar clusters based on the computed minimum distances between exemplars in each exemplar cluster; and

computing an observation likelihood function for each exemplar cluster based on the dimensionality of each exemplar cluster.

10. The computer-readable medium of claim 9 wherein a similarity between exemplars is determined by computing a minimum distance between exemplars in the set of exemplars and each of the randomly selected exemplars.

11. The computer-readable medium of claim 9 wherein the training data is image data.

12. The computer-readable medium of claim 9 further comprising aligning exemplars prior to iteratively clustering the exemplars.

13. The computer-readable medium of claim 9 further comprising probabilistically tracking at least one pattern in target data by using the exemplar clusters, observation likelihood functions and target data to predict at least one target state.

14. A system for automatically tracking patterns in a set of tracking data, comprising using a computing device for:

generating at least one set of clustered exemplars from a set of training data;

for each exemplar cluster, computing a distance between a representative exemplar at a center of each cluster and each of the other exemplars in that cluster;

using the computed distance to estimate an observation likelihood function for each cluster of exemplars; and

using the observation likelihood function for each cluster of exemplars to probabilistically track at least one pattern in at least one set of tracking data.

15. The system of claim 14 wherein generating at least one set of clustered exemplars comprises extracting exemplars statistically representative a target pattern from the training data, and then using a k-medoids process to cluster the exemplars into a predefined number of clusters.

16. The system of claim 14 wherein computing a distance between the representative exemplar at the center of each cluster and each of the other exemplars in that cluster comprises using a distance function to compute the distance.

17. The system of claim 14 wherein estimating an observation likelihood function for each cluster of exemplars comprises fitting either of a chi-squared distribution and a gamma distribution to a distribution of distances from the representative exemplar at the center of each cluster to each of the other exemplars in that cluster to estimate a dimensionality and an exponential constant for the observation likelihood function.

18. The system of claim 14 wherein probabilistically tracking at least one pattern in at least one set of tracking data comprising tracking at least one pattern in a space-domain.

19. The system of claim 14 wherein probabilistically tracking at least one pattern in at least one set of tracking data comprising tracking at least one pattern in a sequence of images.

20. The system of claim 14 wherein probabilistically tracking at least one pattern in at least one set of tracking data comprising tracking at least one pattern in a frequency-domain.