GRAPH LATTICE METHOD FOR IMAGE CLUSTERING, CLASSIFICATION, AND REPEATED STRUCTURE FINDING

• US 20120070091A1
• Filed: 09/16/2010
• Published: 03/22/2012
• Est. Priority Date: 09/16/2010
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Saund, Eric
• Granted Patent: US 8,724,911 B2
• Time in Patent Office: Days
• US Class Current: 382/225
• CPC Class Codes: G06V 30/1988 Graph matching graphical image representation G06V30/18181
• CPC Class Codes: G06V 30/412 Layout analysis of documents structured with printed lines or input boxes, e.g. business forms or tables

Abstract

A document recognition system and method, where images are represented as a collection of primitive features whose spatial relations are represented as a graph. Useful subsets of all the possible subgraphs representing different portions of images are represented over a corpus of many images. The data structure is a lattice of subgraphs, and algorithms are provided means to build and use the graph lattice efficiently and effectively.

Claims

1. A method for clustering a plurality data graphs, wherein the plurality of data graphs are comprised of primitives and relations, said method comprising:

generating, by a processing device, a graph lattice comprised of a graph of related subgraphs, wherein subgraphs of degree 1 are the primitives and each subgraph of degree i>

1 is comprised of a subgraph of degree i−

1 and one of the primitives;

using, by a processing device, the graph lattice to generate feature vectors for the plurality of data graphs; and

,

clustering, by a processing device, the plurality of data graphs according to similarity between the generated feature vectors.

2. The method of claim 1, wherein the feature vectors are determined using junction-normalized mapping counts.

3. The method of claim 1, wherein a junction-normalized mapping count is a subgraph matching count reweighted by junction mapping counts.

4. The method of claim 1, wherein the similarity between the generated feature vectors is determined using a common minus difference measure.

5. The method of claim 1, wherein the common minus difference measure compares absolute magnitudes on an element-by-element basis.

6. The method of claim 1, wherein the clustering includes:

finding a best-matching cluster for each of the plurality of data graphs using the feature vectors;

determining a similarity score for the each of the plurality of data graphs based on its best-matching cluster;

grouping the each of the plurality of data graphs with its best-matching cluster if its similarity score exceeds a first threshold;

grouping the each of the plurality of data graphs in a new cluster if its similarity score is less than a second threshold;

grouping the each of the plurality of data graphs in an unknown cluster if its similarity score is between the first threshold and the second threshold.

7. The method of claim 6, wherein the best-matching cluster for the each of the plurality of data graphs is determined by examining data graphs within existing clusters to find a cluster having a data graph with a feature vector most similar to the each of the plurality of data graphs.

8. The method of claim 6, wherein data graphs in the unknown cluster are re-clustered when all of the plurality of data graphs are clustered.

9. The method of claim 1, wherein the graph lattice is generated from the plurality of data graphs.

10. A method for categorizing a data graph, wherein the data graph is comprised of primitives and relations, said method comprising:

generating, by a processing device, a graph lattice comprised of a graph of a related subgraphs, wherein subgraphs of degree 1 are the primitives and each subgraph of degree i>

1 is comprised of a subgraph of degree i−

1 and one of the primitives;

using, by a processing device, the graph lattice to generate feature vectors for the data graph and exemplars of a first category;

comparing, by a processing device, the generated feature vectors for the data graph and the exemplars of the first category; and

,

categorizing, by a processing device, the data graph as a member of the first category if similarity between the feature vectors of the image and the exemplars exceeds a threshold.

11. The method of claim 10, wherein the feature vectors are determined using junction-normalized mapping counts.

12. The method of claim 11, wherein a junction-normalized mapping count is a subgraph matching count reweighted by junction mapping counts.

13. The method of claim 10, wherein the similarity between the feature vectors is determined using a common minus difference measure.

14. The method of claim 13, wherein the common minus difference measure compares absolute magnitudes on an element-by-element basis.

15. The method of claim 10, wherein the graph lattice is generated from the data graph.