Method for generating a graph lattice from a corpus of one or more data graphs
AssigneePalo Alto Research Center Incorporated
InventorEric Saund
Life of this patent
Estimating the term…
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.
Claims24
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.
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.
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.
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.
Dependencies are inferred from the claim text.