Image clustering with metric, local linear structure, and affine symmetry

• US 20050141769A1
• Filed: 11/15/2004
• Published: 06/30/2005
• Est. Priority Date: 11/13/2003
• Status: Active Grant

• Current Assignee: Honda Motor Company
• Original Assignee: Honda Motor Company
• Inventors: Lim, Jongwoo, Yang, Ming-Hsuan, Ho, Jeffrey
• Granted Patent: US 7,248,738 B2
• Time in Patent Office: Days
• US Class Current: 382/225
• CPC Class Codes: G06F 18/21375 involving differential geometry, e.g. embedding of pattern manifold
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts

Abstract

A system and a method are disclosed for clustering images of objects seen from different viewpoints. That is, given an unlabelled set of images of n objects, an unsupervised algorithm groups the images into N disjoint subsets such that each subset only contains images of a single object. The clustering method makes use of a broad geometric framework that exploits the interplay between the geometry of appearance manifolds and the symmetry of the 2D affine group.

Claims

1. A computer-based method for grouping objects within a set of digital images, wherein each image of the set of digital images includes a first object having an identity, the method comprising the steps of:

identifying a plurality of nearest neighbors of each of the set of digital images within an image space defined by the set of digital images;

determining a local linear structure for one or more of the set of digital images using said nearest neighbors of each of the set of digital images; and

determining distances between said nearest neighbors and each digital image based upon said local linear structure.

2. The method of claim 1, further comprising the step of applying a spectral clustering algorithm to said distances between said nearest neighbors and each digital image.

3. A computer system for grouping objects within a set of digital images, wherein each image of the set of digital images includes a first object having an identity, the system comprising:

means for identifying a plurality of nearest neighbors of each of the set of digital images within an image space defined by the set of digital images;

means for determining a local linear structure for one or more of the set of digital images using said nearest neighbors of each of the set of digital images; and

means for determining distances between said nearest neighbors and each digital image based upon said local linear structure.

4. The computer system of claim 3, further comprising means for applying a spectral clustering algorithm to said distances between said nearest neighbors and each digital image.

5. An image processing computer system for grouping objects within a set of digital images, comprising:

an input module for receiving data representative of the set of digital images, each digital image representative of an object;

a memory device coupled to said input module for storing said data representative of the set of digital images;

a processor coupled to said memory device for retrieving said data representative of the set of digital images, the processor configured to;

identify a plurality of nearest neighbors of each of the set of digital images within an image space defined by the set of digital images;

determine a local linear structure for one or more of the set of digital images using said nearest neighbors of each of the set of digital images;

determine distances between said nearest neighbors and each digital image based upon said local linear structure.

6. The image processing computer system of claim 5, further configured to apply a spectral clustering algorithm to said distances between said nearest neighbors and each digital image.