System and method for probabilistic exemplar-based pattern tracking

• US 7,035,431 B2
• Filed: 02/22/2002
• Issued: 04/25/2006
• 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): Wu, Jingge
• Assistant Examiner(s): MACKOWEY, ANTHONY M
• Application Number:
  US10/080,449
• Publication Number:
  US 20030161500A1
• Time in Patent Office: 1,523 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 system for automatic probabilistic pattern tracking comprising:

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 system of claim 1 wherein clustering of exemplars is achieved using an iterative k-medoids clustering process based on a computed distance between the representative exemplar at the center of each cluster and each of the exemplars clustered with that exemplar.

3. The system of claim 1 wherein generating the observation likelihood functions comprises using a multidimensional scaling process to estimate a dimensionality of each exemplar cluster.

4. The system of claim 1 wherein the training data is image data, and wherein contour-based exemplars are extracted from the training data using conventional edge detection techniques to process the training data.

5. The system of claim 4 wherein the contour-based exemplars are used for probabilistically tracking at least one object in a sequence of images.

6. The system of claim 1 wherein the training data is image data, and wherein image patches representing target objects of interest are extracted as exemplars from the training data.

7. The system of claim 6 wherein the image patch-based exemplars are used for probabilistically tracking at least one object in a sequence of images.

8. The system of claim 1 wherein the observation likelihood functions are iteratively updated while tracking patterns in the target data.

9. The system of claim 2 wherein the exemplars are contour-based exemplars, and wherein the computed distance between exemplars is a chamfer distance.

10. The system of claim 2 wherein the exemplars are image patch-based exemplars, and wherein the computed distance between exemplars is a shuffle distance.

11. The system of claim 1 wherein the target data is space-based data, and wherein probabilistically tracking at least one pattern in the target data comprises tracking at least one pattern in a space-domain.

12. The system 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.

13. The system of claim 1 wherein the target data is frequency-based data, and wherein probabilistically tracking at least one pattern in the target data comprises tracking at least one pattern in a frequency-domain.

14. A method for generating a set of observation likelihood functions from a set of exemplars comprising using a computer to:

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

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

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

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

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

15. The method of claim 14 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.

16. The method of claim 14 wherein the training data is image data.

17. The method of claim 16 wherein the exemplars are contour-based exemplars.

18. The method of claim 17 wherein the computed minimum distances are computed by a chamfer distance function.

19. The method of claim 16 wherein the exemplars are image-patch exemplars.

20. The method of claim 19 wherein the computed minimum distances are computed by a shuffle distance function.

21. The method of claim 14 further comprising aligning exemplars prior to iteratively clustering the exemplars.

22. The method of claim 14 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.

23. A computer-implemented process for tracking patterns, comprising using a computer to:

extract a set of exemplars from training data;

cluster the exemplars based on a minimization of a maximum distance between exemplars, and wherein each cluster includes a representative exemplar at the center of each cluster;

estimate a dimensionality for each exemplar cluster;

generate a likelihood function for each exemplar cluster using the estimated dimensionality;

provide the likelihood function, exemplar clusters, and target data to a tracking function; and

track at least one pattern in the target data using the tracking function in combination with the likelihood function and exemplar clusters.

24. The computer-implemented process of claim 23 wherein extracting exemplars from training data comprises extracting parameters from the training data that are statistically representative of at least one target pattern.

25. The computer-implemented process of claim 23 wherein clustering the exemplars comprises using a k-medoid clustering process to cluster similar exemplars.

26. The computer-implemented process of claim 23 wherein estimating a dimensionality for each cluster of exemplars comprises fitting a chi-squared 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.

27. The computer-implemented process of claim 23 wherein estimating a dimensionality for each cluster of exemplars comprises fitting 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.

28. The computer-implemented process of claim 23 wherein estimating a dimensionality for each cluster of exemplars comprises using multidimensional scaling of distances from the representative exemplar at the center of each cluster to each of the other exemplars in that cluster to estimate the dimensionality for each cluster.

29. The computer-implemented process of claim 23 wherein each exemplar is represented by an unparameterized curve, and wherein the distance between exemplars is a chamfer distance.

30. The computer-implemented process of claim 23 wherein each exemplar is represented by an image patch, and wherein the distance between exemplars is a shuffle distance.

31. The computer-implemented process of claim 23 wherein exemplars are geometrically transformed in Euclidian space in order to align the exemplars prior to clustering the exemplars.

32. A computer-readable medium having computer executable instructions for automatically tracking patterns in a set of tracking data, said computer executable instructions comprising:

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.

33. The computer-readable medium of claim 32 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.

34. The computer-readable medium of claim 32 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.

35. The computer-readable medium of claim 32 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.

36. The computer-readable medium of claim 32 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.

37. The computer-readable medium of claim 32 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.

38. The computer-readable medium of claim 32 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.