METHOD FOR GENERATING A GRAPH LATTICE FROM A CORPUS OF ONE OR MORE DATA GRAPHS

• US 20120069024A1
• 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,872,828 B2
• Time in Patent Office: Days
• US Class Current: 345/440
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

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 generating a graph lattice from a corpus of one or more data graphs, said method comprising:

a) generating by a processing device candidate graph lattice nodes from accepted graph lattice nodes, wherein each of the generated candidate graph lattice nodes includes a subgraph mapping to a data graph of the corpus, wherein the subgraph of the each of the candidate graph lattice nodes is of degree i and is formed from a subgraph of an accepted graph lattice node of degree i−

1 and a primitive;

b) selecting, by a processing device, one or more of the candidate graph lattice nodes according to a selection criteria;

c) promoting, by a processing device, the selected graph lattice nodes to accepted graph lattice nodes; and

,

d) repeating, by a processing device, actions a) through c) until a termination condition is met, wherein the accepted graph lattice nodes at termination define the graph lattice.

2. The method of claim 1, wherein the accepted graph lattice nodes are initially comprised of primitives.

3. The method of claim 1, wherein the selection criteria is a maximum node type diversity criteria.

4. The method of claim 3, wherein the maximum node type diversity criteria selects candidate graph lattice nodes having a highest diversity of primitive types.

5. The method of claim 1, wherein the each of the generated candidate graph lattice nodes is linked to an accepted graph lattice node by a strut.

6. The method of claim 5, wherein a strut maintains a three-way relationship between a graph lattice node of degree i, a graph lattice node of degree i−

1, and a primitive.

7. The method of claim 1, wherein the termination condition is the graph lattice containing a threshold number of accepted graph lattice nodes at a given level and/or a threshold number of accepted graph lattice nodes in total.

8. The method of claim 1, wherein the termination condition is exhaustion of the candidate graph lattice nodes.

9. A method for retrieving one or more data graphs from a collection of data graphs given a search data graph, said method comprising:

generating, by a processing device, a graph lattice for the collection of data graphs, wherein the graph lattice is comprised of a graph of a related subgraphs mapping to the collection;

determining, by a processing device, mappings of the graph lattice to the search data graph;

using, by a processing device, the mappings to identify data graphs of the collection sharing subgraphs with the search data graph;

ranking, by a processing device, the identified data graphs according to a number of subgraphs shared with the search data graph;

selecting, by a processing device, a predetermined number of the most highly ranked data graphs from the collection.

10. The method of claim 9, wherein the data graphs of the collection correspond to documents.

11. The method of claim 9, wherein subgraphs of degree 1 are primitives and each subgraph of degree i>

1 is comprised of a subgraph of degree i−

1 and one of the primitives.

12. The method of claim 9, wherein each subgraph of degree i>

1 is linked to a subgraph of degree i−

1 by a strut.

13. The method of claim 12, wherein a strut maintains a three-way relationship between a subgraph of degree i, a subgraph of degree i−

1, and a primitive.

14. A method for detecting repeated structure in a data graph, 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 primitives and each subgraph of degree i>

1 is comprised of a subgraph of degree i−

1 and one of the primitives;

for each of the related subgraphs, searching, by a processing device, the graph lattice for subgraphs representing repeated structure of the each of the related subgraphs, wherein a subgraph represents repeated structure of a subgraph of degree L if the subgraph is of degree and maps R times to the data graph without overlap.

15. The method of claim 14, wherein each subgraph of degree i>

1 is linked to a subgraph of degree i−

1 by a strut.

16. The method of claim 15, wherein a strut maintains a three-way relationship between a subgraph of degree i, a subgraph of degree i−

1, and a primitive.

17. The method of claim 14, wherein the graph lattice is generated from the data graph.

18. The method of claim 14, wherein the data graph corresponds to an image.

19. The method of claim 18, wherein the image is rectilinear line art.

20. A method for mapping a graph lattice to a data graph, wherein the graph lattice is comprised of a graph of related subgraphs, wherein subgraphs of degree 1 are primitives and each subgraph of degree i>

1 is comprised of a subgraph of degree i−

1 and one of the primitives, said method comprising;

mapping, by a processing device, subgraphs of degree 1 to the data graph; and

,

iteratively mapping, by a processing device, subgraphs of degree i>

1 to the data graph, wherein mappings of the subgraphs of degree i>

1 are incremental extensions of mappings of the subgraphs of degree i−

1.

21. The method of claim 20, wherein the mapping of subgraphs of degree i>

1 includes;

for each subgraph of degree i>

2, selecting a parent subgraph of degree i−

1, wherein the subgraph of degree i>

2 is a combination of the parent subgraph of degree i−

1 and a primitive;

for each mapping of the selected parent subgraph, determining whether there is a valid link on the data graph to the primitive in correct proximity to the parent subgraph.

22. The method of claim 20, wherein the mapping of subgraphs of degree i>

1 includes;

identifying pairs of primitives forming subgraphs of degree 2;

for each mapping of a member of each pair of primitives, determining whether there is a valid link on the data graph to the other member in correct proximity to the member.

23. The method of claim 20, wherein each subgraph of degree i>

1 is linked to a subgraph of degree i−

1 by a strut.

24. The method of claim 23, wherein a strut maintains a three-way relationship between a subgraph of degree t, a subgraph of degree i−

1, and a primitive.