Clustering images using an image region graph

• US 8,243,988 B1
• Filed: 07/31/2008
• Issued: 08/14/2012
• Est. Priority Date: 07/31/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Buddemeier, Ulrich
• Primary Examiner(s): Wang, Claire X
• Application Number:
  US12/183,613
• Time in Patent Office: 1,475 Days
• Field of Search: 382/103, 382/219, 382/154
• US Class Current: 382/103
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/5866 using information manually generated, e.g. tags, keywords, comments, manually generated location and time information
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06V 10/7625 Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms
• CPC Class Codes: G06V 10/7635 based on graphs, e.g. graph cuts or spectral clustering
• CPC Class Codes: G06V 20/30 in albums, collections or shared content, e.g. social network photos or video

Abstract

Methods for grouping images from image corpora using graph clustering are presented. In one embodiment, a method is presented where grouping of images from a collection of digital images is done by: representing regions of images as vertices in a graph; connecting each pair of matching-vertices with a matching-edge; connecting each pair of overlap-vertices with an overlap-edge; assigning weights to each said matching-edge and to each said overlap-edge; clustering the graph, wherein clustering generates one or more vertex-clusters; and grouping the digital images into visual-clusters based on the vertex-clusters. Corresponding systems and computer program products are also presented.

Claims

1. A computer-implemented method for grouping images from a collection of digital images, comprising:

(a) representing, using a processor, regions of images as vertices in a graph, wherein the images are from the collection of digital images;

(b) connecting, using the processor, each pair of matching-vertices with a matching-edge in the graph, wherein two vertices are matching-vertices if they represent corresponding regions in two images;

(c) connecting, using the processor, each pair of overlap-vertices with an overlap-edge in the graph, wherein two vertices are overlap-vertices if they represent regions of the same image;

(d) assigning, using the processor, weights to each said matching-edge and to each said overlap-edge;

(e) organizing, using the processor, the graph into visual-clusters; and

(f) outputting, using the processor, one or more signals corresponding to the visual-clusters.

2. The computer-implemented method of claim 1, wherein each visual-cluster comprises images containing regions corresponding to all vertices in a vertex-cluster.

3. The computer-implemented method of claim 1, wherein each region includes an area on an image that is defined by interest-points and that has a corresponding area in another image.

4. The computer-implemented method of claim 1, wherein each weight assigned to a matching-edge is based on a level of confidence in a corresponding match.

5. The computer-implemented method of claim 4, wherein the level of confidence is based on the probability that a match between corresponding regions is a false positive.

6. The computer-implemented method of claim 1, wherein each weight assigned to an overlap-edge is based on a level of corresponding region overlap.

7. The computer-implemented method of claim 6, wherein the level of corresponding region overlap is based on a distance between centers-of-gravity of corresponding regions.

8. The computer-implemented method of claim 7, wherein the level of corresponding region overlap is further based on the size of each corresponding region.

9. The computer-implemented method of claim 8, wherein the size of each region is based on the average distance of points in the region to the center of gravity of the region.

10. The computer-implemented method of claim 1, wherein organizing the graph into visual-clusters comprises:

(i) clustering the graph, wherein clustering generates one or more vertex-clusters, and wherein each vertex-cluster includes a subgraph of the graph; and

(ii) grouping said digital images into the visual-clusters, wherein the grouping is based on said vertex-clusters.

11. The computer-implemented method of claim 10, wherein clustering the graph comprises:

(A) generating a minimum spanning tree of the graph; and

(B) forming the vertex-clusters based on the minimum spanning tree.

12. The computer-implemented method of claim 10, wherein clustering the graph includes using a hierarchical-clustering algorithm to generate the vertex clusters.

13. The computer-implemented method of claim 12, wherein the hierarchical-clustering algorithm includes hierarchical-agglomerative clustering.

14. The computer-implemented method of claim 12, wherein the clustering is performed on a pruned version of the graph.

15. The computer-implemented method of claim 1, further comprising:

(g) removing redundant images before organizing;

the graph into visual-clusters, wherein an image in the graph is redundant if it is similar to another image in the graph.

16. The computer-implemented method of claim 1, further comprising:

(h) selecting representative images for a visual-cluster, wherein the representative images include one or more images in the visual-cluster having the most matching-edges relative to other images in same visual cluster.

23. The computer-implemented method of claim 1, wherein the visual clusters include both matching-edges and overlap-edges.

17. A system for grouping images, comprising:

a processor;

an interface, wherein the interface connects to a collection of digital images; and

a visual clustering module that groups images from the collection of digital images, the visual clustering module comprising;

a graph generator module configured to generate a graph, wherein vertices of the graph represent regions in an image, wherein matching-edges connect regions to corresponding regions in different images, wherein overlap-edges connect regions in the same image, wherein matching-edges are assigned weights based on the probability that the match between the corresponding regions is a false positive, and wherein overlap-edges are assigned weights based on the center-of-gravity and size of corresponding regions; and

a graph organizer module, configured to organize the graph into visual-clusters;

wherein the visual clustering module embodied as computer program code is executed by the processor, and the visual clustering module is configured to access the collection of digital images through said interface.

18. The system of claim 17, further comprising:

a database module configured to manage the visual-clusters.

19. The system of claim 17, wherein the graph organizer module further comprises:

an image clusterer module, configured to generate one or more vertex-clusters from the graph, and wherein each vertex-cluster includes a subgraph of the graph; and

an image grouper module configured to group images into the visual-clusters, wherein the grouping is based on said vertex-clusters.

20. A computer program product comprising a computer usable medium having computer program logic recorded thereon for causing a processor to group images from a collection of digital images, said computer program logic comprising:

a first computer program that causes the processor to represent regions of images as vertices in a graph, wherein the images are from the collection of digital images;

a second computer program that causes the processor to connect each pair of matching-vertices with a matching-edge in the graph, wherein two vertices are matching-vertices if they represent corresponding regions in two images;

a third computer program that causes the processor to connect each pair of overlap-vertices with an overlap-edge in the graph, wherein two vertices are overlap-vertices if they represent regions of the same image;

a fourth computer program that causes the processor to assign weights to each said matching-edge and to each said overlap-edge;

a fifth computer program that causes the processor to organize the graph into visual-clusters; and

a sixth computer program that causes the processor to output one or more signals corresponding to the visual-clusters.

21. The computer program product of claim 20, wherein the fifth computer program further causes the processor to:

cluster the graph generating one or more vertex-clusters, and wherein each vertex-cluster includes a subgraph of the graph; and

group said digital images into the visual-clusters, wherein the grouping is based on said vertex-clusters.

22. The computer program product of claim 20, the computer program logic further comprising:

a seventh computer program product that causes the processor to select representative images for a visual-cluster, wherein the representative images include one or more images in the visual-cluster having the most matching-edges relative to other images in same visual cluster.