Unknown pattern set recognition

• US 8,116,566 B2
• Filed: 08/28/2007
• Issued: 02/14/2012
• Est. Priority Date: 08/28/2006
• Status: Expired due to Fees

• Current Assignee: Colorado State University Research Foundation (Colorado State University System)
• Original Assignee: Colorado State University Research Foundation (Colorado State University System)
• Inventors: Kirby, Michael Joseph, Beveridge, James Ross, Chang, Jen-Mei, Draper, Bruce Anthony, Kley, Holger Philipp, Peterson, Christopher Scott
• Primary Examiner(s): ZARKA, DAVID PETER
• Application Number:
  US11/846,486
• Publication Number:
  US 20080175446A1
• Time in Patent Office: 1,631 Days
• Field of Search: 382/181
• US Class Current: 382/181
• CPC Class Codes: G06F 18/21375 involving differential geometry, e.g. embedding of pattern manifold
• CPC Class Codes: G06V 10/60 relating to illumination properties, e.g. using a reflectance or lighting model
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 40/173 face re-identification, e.g. recognising unknown faces across different face tracks

Abstract

A pattern recognition system compares a set of unlabeled images (or other patterns) having a variation of state in a set-by-set comparison with individual data sets of multiple labeled images (or other patterns) also having a variation of state. The individual data sets are each mapped to a point on a parameter space (e.g., a Grassmannian manifold, a Stiefel manifold, a flag manifold, etc.), and the set of unlabeled images is mapped to a point in the same parameter space. If the point associated with the set of unlabeled images satisfies a distance criterion on the parameter space with regard to one of the points on the parameter space, the data set of unlabeled images is assigned to the class attributed to that point.

Claims

1. A method comprising:

mapping, using a processor, each data set of a collection of data sets of labeled patterns to a point on a parameter space, the parameter space being one of a Grassman manifold, a Stiefel manifold, a Flag manifold, and a product of manifolds, each labeled pattern having a variation of state distinguishing the labeled pattern from other labeled patterns in the data set;

mapping a data set of unlabeled patterns to a point on the parameter space, each unlabeled pattern having a variation of state distinguishing the unlabeled pattern from other unlabeled patterns in the data set;

if a distance, computed on the parameter space, between the point mapped from the data set of unlabeled patterns and one of the points mapped from the data set of labeled patterns satisfies a distance criterion evaluated on the parameter space, attributing the label of the data set of the labeled pattern mapped to the point satisfying the distance criterion to the data set of unlabeled patterns.

2. The method of claim 1 wherein the distance criterion includes weighting parameters that are determined a priori.

3. The method of claim 1 wherein the distance criterion includes weighting parameters that are adapted over multiple iterations.

4. The method of claim 1 wherein at least one point mapped to the parameter space is identified as a subspace of an ordered set of orthonormal vectors.

5. The method of claim 1 wherein at least one point mapped to the parameter space is identified as a subspace of a fixed vector space.

6. The method of claim 1 wherein at least one point mapped to the parameter space is identified as a nested sequence of subspaces of fixed dimensions.

7. The method of claim 1 wherein each pattern represents a region of connected data points in a corresponding base pattern.

8. The method of claim 1 wherein each pattern represents a plurality of projections to fiducial data points within a corresponding base pattern.

9. The method of claim 1 wherein each pattern represents a plurality of arbitrary data points selected from a corresponding base pattern.

10. The method of claim 1 wherein the distance criterion includes a condition seeking a minimum distance between two points on the parameter space.

11. The method of claim 10 wherein the distance criterion further includes a condition that the minimum distance between the two points not exceed a distance threshold.

12. One or more computer readable storage media storing computer executable instructions for executing a computer process classifying a data set of related unlabeled patterns on a computing system, the computer process comprising:

mapping each data set of a collection of data sets to a point on a parameter space, the parameter space being one of a Grassman manifold, a Stiefel manifold, a Flag manifold, and a product of manifolds, each data set of the collection containing labeled patterns, each labeled pattern having a variation of state distinguishing the labeled pattern from other labeled patterns in the data set;

mapping the data set of unlabeled patterns to a point on the parameter space, each unlabeled pattern having a variation of state distinguishing the unlabeled pattern from other unlabeled patterns in the data set;

if a distance computed on the parameter space between the point mapped from the data set of unlabeled patterns and one of the points mapped from the data set of labeled patterns satisfies a distance criterion evaluated on the parameter space, attributing the label of the data set of the labeled pattern mapped to the point satisfying the distance criterion to the data set of unlabeled patterns.

13. The one or more computer-readable media of claim 12 wherein at least one point mapped to the parameter space is identified as a subspace of a set of ordered orthonormal vectors.

14. The one or more computer-readable media of claim 12 wherein at least one point mapped to the parameter space is identified as a subspace of a fixed vector space.

15. The one or more computer-readable media of claim 12 wherein at least one point mapped to the parameter space is identified as a nested sequence of subspaces of fixed dimensions.

16. The one or more computer-readable media of claim 12 wherein the distance criterion includes a condition seeking a minimum distance between two points on the parameter space.

17. The one or more computer-readable media of claim 16 wherein the distance criterion further includes a condition that the minimum distance between the two points not exceed a distance threshold.

18. A method comprising:

receiving a collection of data sets of labeled images, each labeled image of a data set having a variation of illumination distinguishing the labeled image from other labeled images in the data set;

mapping, using a processor, each data set of the collection of data sets to a point on a Grassmann manifold;

mapping a data set of unlabeled images to a point on the Grassmann manifold, each unlabeled image having a variation of illumination distinguishing the unlabeled image from other unlabeled images in the data set;

computing, on the Grassmann manifold, a similarity measure between the point mapped from the data set of unlabeled images and each point mapped from the data sets of labeled images;

if a similarity measure computed on the Grassmann manifold between the point mapped from the data set of unlabeled images and one of the points mapped from the data set of labeled images satisfies a similarity criterion evaluated on the Grassmann manifold, attributing the label of the data set of the labeled pattern mapped to the point satisfying the similarity criterion to the data set of unlabeled images.

19. The method of claim 18 wherein the similarity criterion includes a condition seeking a minimum distance between two points on the parameter space.

20. The method of claim 19 wherein the similarity criterion further includes a condition that the minimum distance between the two points not exceed a distance threshold.