Graph lattice method for image clustering, classification, and repeated structure finding

• US 8,724,911 B2
• Filed: 09/16/2010
• Issued: 05/13/2014
• 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
• Primary Examiner(s): DULANEY, KATHLEEN YUAN
• Application Number:
  US12/883,503
• Publication Number:
  US 20120070091A1
• Time in Patent Office: 1,335 Days
• Field of Search: 382/225, 382/194, 382/202, 382/204, 382/218, 382/306, 707/729
• 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 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, wherein the graph lattice is a lattice of nodes, and wherein each node corresponds to a subgraph representing image primitives and relations, and each graph lattice node is configured to provide descriptive information about the subgraph to which the graph lattice node corresponds;

using the graph lattice to generate feature vectors for the plurality of data graphs;

clustering the plurality of data graphs according to similarity between the generated feature vectors, wherein the method is performed using at least one digital processor; and

a strut consisting of a parent graph lattice node at level N, a primitive, and a child graph lattice node at level N+1 which is the subgraph consisting of the parent graph lattice node subgraph plus the primitive linked to the perimeter of the parent graph lattice node subgraph.

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 4, wherein the common minus difference measure compares absolute magnitudes on an element-by-element basis.

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

7. The method according to claim 1, wherein each level of the graph lattice acts as a base for a next layer.

8. The method of claim 1, wherein the strut maintains a junction index mapping between the parent graph lattice node and the child graph lattice node and indicates the primitive type, placement on the parent, and links for a junction that constructs the child from the parent.

9. The method of claim 1, wherein the primitives include a plurality of distinct primitives having distinct junctions.

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

generating 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 the graph lattice to generate feature vectors for the plurality of data graphs; and

,

clustering the plurality of data graphs according to similarity between the generated feature vectors, 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 the each of the plurality of data graphs best-matching cluster;

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

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

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

wherein the method is performed using at least one digital processor.

11. The method of claim 10, 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.

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

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

generating 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, wherein the graph lattice is a lattice of nodes, and wherein each node is at level N and corresponds to a subgraph representing image primitives and relations, the subgraph being a subgraph corresponding to a parent graph lattice node at level N−

1 plus a primitive linked to the perimeter of the subgraph corresponding to the parent graph lattice node, and wherein each graph lattice node is configured to provide descriptive information about the subgraph to which the graph lattice node corresponds;

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

comparing the generated feature vectors for the data graph and the exemplars of the first category;

categorizing the data graph as a member of the first category if similarity between the feature vectors of an image and the exemplars exceeds a threshold, wherein the method is performed using at least one digital processor; and

, a strut consisting of the parent graph lattice node at level M, the primitive, and a child graph lattice node at level M+1 which is the subgraph consisting of the parent graph lattice node subgraph plus the primitive linked to the perimeter of the parent graph lattice node subgraph.

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

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

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

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

18. The method of claim 13, wherein the graph lattice is generated from the data graph.

19. A system carried on a non-transitory readable medium capable of being read by at least one electronic processor, including steps for clustering a plurality data graphs, wherein the plurality of data graphs are comprised of primitives and relations, said system comprising:

generating 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 the graph lattice to generate feature vectors for the plurality of data graphs; and

,

clustering the plurality of data graphs according to similarity between the generated feature vectors, 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 the each of the plurality of data graphs best-matching cluster;

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

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

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

wherein the system is performed using at least one digital processor.