Finding structures in multi-dimensional spaces using image-guided clustering

• US 7,519,227 B1
• Filed: 07/07/2008
• Issued: 04/14/2009
• Est. Priority Date: 01/08/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Syeda-Mahmood, Tanveer, Haas, Peter J., Lohman, Guy M., Lake, John M.
• Primary Examiner(s): Carter; Aaron W
• Application Number:
  US12/168,547
• Time in Patent Office: 281 Days
• Field of Search: 382224-228, 707 3- 6, 707/104.1
• US Class Current: 382/225
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method executed on a computer for determining a hierarchical clustering of a multidimensional dataset in a multidimensional image space comprises receiving a pyramid of multidimensional images of the multidimensional dataset in which the images of the pyramid representing a first multidimensional image of the multidimensional dataset at successively lower resolution levels; identifying data clusters at each resolution level of the pyramid by applying a set of perceptual grouping constraints; plotting a variation curve of a magnitude of data clusters identified at each resolution level of the pyramid as a function of resolution level; and generating a clustering hierarchy for the multidimensional dataset by identifying the resolution level at each salient bend in the variation curve as a level of the clustering hierarchy.

Claims

1. A method executed on a computer for determining a hierarchical clustering of a multidimensional dataset in a multidimensional image space, the method comprising:

using the computer to perform the following;

receiving a pyramid of multidimensional images of the multidimensional dataset, the images of the pyramid representing a first multidimensional image of the multidimensional dataset at successively lower resolution levels;

identifying data clusters at each resolution level of the pyramid by applying a set of perceptual grouping constraints;

plotting a variation curve of a magnitude of data clusters identified at each resolution level of the pyramid as a function of resolution level; and

generating a clustering hierarchy for the multidimensional dataset by identifying the resolution level at each salient bend in the variation curve as a level of the clustering hierarchy.

2. The method of claim 1, wherein the pyramid of multidimensional images of the multidimensional dataset is a Laplacian pyramid.

3. The method of claim 1, wherein identifying data clusters at each resolution level comprises identifying data clusters at a highest resolution level of the pyramid by applying the set of perceptual grouping constraints, and identifying data clusters at each successively lower resolution level of the pyramid by extracting data clusters identified at the previous resolution level and applying the set of perceptual grouping constraints.

4. The method of claim 1, wherein the set of perceptual grouping constraints comprises proximity, density, orientation similarity, and region contiguity.

5. The method of claim 1, wherein identifying the resolution level at each salient bend comprises identifying the resolution level at each zero crossing in a second derivative of the variation curve.