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

• US 8,872,830 B2
• Filed: 05/31/2013
• 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:
  US13/906,757
• Publication Number:
  US 20130257874A1
• Time in Patent Office: 515 Days
• Field of Search: 345/440, 345/420, 345/419, 345/39, 345/633, 345/463, 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 retrieving one or more data graphs from a collection of data graphs given a search data graph, said method comprising:

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

determining, by the at least one processing device, mappings of the graph lattice to the search data graph;

using, by the at least one processing device, the mappings of the data graphs and the search data graph to identify data graphs of the collection sharing subgraphs with the search data graph, the identified data graphs mapping to those nodes of the graph lattice to which the search data graph maps;

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

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

2. The method of claim 1, wherein the data graphs of the collection correspond to documents.

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

4. The method of claim 1, wherein each subgraph of degree i>

1 is linked to a subgraph of degree i−

1 by a strut.

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

1, and a primitive.

6. The method of claim 1, wherein the generating includes determining mappings from the graph lattice to the data graphs of the collection.

7. The method of claim 6, further including:

storing the determined mappings from the graph lattice to the data graphs of the collection in a storage device for subsequent use in identifying data graphs of the collection sharing subgraphs with the search data graph.

8. A method for detecting repeated structure in a data graph, said method comprising:

generating, by a at least one processing device, a graph lattice 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;

for each of the related subgraphs, searching, by the at least one processing device, the graph lattice for subgraphs representing repeated structure of the related subgraph, the searching including;

determining the degree of the related subgraph;

for a subgraph of the graph lattice, determining the number of times the subgraph maps to the data graph without overlap and determining the degree of the subgraph; and

determining whether the determined degree of the subgraph is equal to the ratio of the determined degree of the related subgraph and the determined number of times the subgraph maps to the data graph, wherein the subgraph is repeated structure of the related subgraph when the determined degree of the subgraph is equal to the ratio.

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

1 is linked to a subgraph of degree i−

1 by a strut.

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

1, and a primitive.

11. The method of claim 8, wherein the graph lattice is generated from the data graph.

12. The method of claim 8, wherein the data graph corresponds to an image.

13. The method of claim 12, wherein the image is rectilinear line art.

14. The method of claim 8, wherein the graph lattice is generated before searching the graph lattice for subgraphs representing repeated structure.