Method for generating a graph lattice from a corpus of one or more data graphs

• US 8,872,828 B2
• Filed: 09/16/2010
• Issued: 10/28/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): Merouan, Abderrahim
• Application Number:
  US12/883,464
• Publication Number:
  US 20120069024A1
• Time in Patent Office: 1,503 Days
• Field of Search: 345/440, 345/420, 345/419, 345/39, 382/154, 382/190, 382/167, 382/186, 707/100, 707/755, 707/793, 707/803, 707/797
• 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 at least one processing device, candidate graph lattice nodes from accepted graph lattice nodes, the accepted graph lattice nodes being graph lattice nodes within the graph lattice, and the accepted and candidate graph lattice nodes each including a subgraph mapping to a data graph of the corpus, the subgraph being of degree i and formed from a subgraph of an accepted graph lattice node of degree i−

1 and a primitive, wherein the generating includes;

selecting one of the accepted graph lattice nodes;

identifying an extension of the of the selected graph lattice node from the mapping of the selected graph lattice node, the extension being a subgraph mapping to a data graph of the corpus and formed from a primitive added to the subgraph of the selected graph lattice node; and

generating a candidate graph lattice including the extension;

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

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

,

d) repeating, by the at least one 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 each of the generated candidate graph lattice nodes is linked to an accepted graph lattice node by a strut.

4. The method of claim 3, 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.

5. 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.

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

7. The method according to claim 1, wherein the subgraph is formed from one or more primitives, and wherein the degree of the subgraph is the number of primitives forming the subgraph.

8. The method according to claim 1, wherein the primitive is one of a fixed number of primitive types, and wherein the selecting includes selecting one of the candidate graph lattice nodes with a highest diversity of primitive types.

9. The method according to claim 8, wherein the primitive types are line art junctions.

10. A method for generating a graph lattice from a corpus of one or more data graphs, said method comprising:

a) generating by a at least one processing device candidate graph lattice nodes from accepted graph lattice nodes, the accepted graph lattice nodes being graph lattice nodes within the graph lattice, and the accepted and candidate graph lattice nodes each including a subgraph mapping to a data graph of the corpus, the subgraph being of degree i and formed from a subgraph of an accepted graph lattice node of degree i−

1 and a primitive, the primitive being one of a fixed number of primitive types, the primitive types being line art junctions;

b) selecting, by the at least one processing device, one or more of the candidate graph lattice nodes having a highest diversity of primitive types;

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

,

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

11. A method for mapping a graph lattice to a data graph, wherein the graph lattice is comprised of a graph of related subgraphs, said method comprising:

mapping, by a at least one processing device, subgraphs of degree 1 of the graph lattice to the data graph, the subgraphs of degree 1 being primitives; and

,

iteratively mapping, by the at least one processing device, subgraphs of degree i>

1 of the graph lattice to the data graph, each subgraph of degree i>

1 being formed from a subgraph of degree i−

1 and a primitive, wherein mappings of the subgraphs of degree i>

1 to the data graph are incremental extensions of mappings of the subgraphs of degree i−

1 to the data graph, wherein the iterative mapping includes;

selecting one of the subgraphs of degree i>

1;

receiving a previously determined mapping to the data graph of the subgraph of degree i−

1 forming the selected subgraph; and

extending the received mapping by mapping the primitive forming the selected subgraph to the data graph.

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

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

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

1 is linked to a subgraph of degree i−

1 by a strut.

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

1, and a primitive.

16. The method of claim 11, wherein the graph lattice is formed before performing the method.

17. The method of claim 16, wherein the graph lattice is formed from a corpus of one or more data graphs, the corpus excluding the data graph to which the graph lattice is being mapped.

18. The method of claim 16, wherein the graph lattice is formed by:

a) generating candidate graph lattice nodes from accepted graph lattice nodes, wherein the accepted graph lattice nodes are graph lattice nodes within the graph lattice, wherein each of the accepted and candidate graph lattice nodes includes a subgraph mapping to a data graph of a corpus of one or more data graphs, and wherein the generating includes;

selecting one of the accepted graph lattice nodes;

identifying an extension of the of the selected graph lattice node from the mapping of the selected graph lattice node, the extension being a subgraph mapping to the data graph of the corpus and formed from a primitive added to the subgraph of the selected graph lattice node; and

generating a candidate graph lattice including the extension;

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

c) promoting the selected graph lattice nodes to accepted graph lattice nodes; and

,

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

19. The method of claim 18, wherein the selection criteria selects candidate graph lattice nodes having a highest diversity of primitive types, the primitive types being line art junctions.

20. The method according to claim 11, wherein the primitive is one of a fixed number of primitive types, the primitive types being line art junctions.