Graph lattice method for image clustering, classification, and repeated structure finding
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.
Claims15
A method for clustering a plurality data graphs, wherein the plurality of data graphs are comprised of primitives and relations, said method comprising:
- generating, by a processing device, 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, by a processing device, the graph lattice to generate feature vectors for the plurality of data graphs;
- and,
- clustering, by a processing device, the plurality of data graphs according to similarity between the generated feature vectors.
A method for categorizing a data graph, wherein the data graph is comprised of primitives and relations, 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 the primitives and each subgraph of degree i>1 is comprised of a subgraph of degree i−1 and one of the primitives;
- using, by a processing device, the graph lattice to generate feature vectors for the data graph and exemplars of a first category;
- comparing, by a processing device, the generated feature vectors for the data graph and the exemplars of the first category;
- and,
- categorizing, by a processing device, the data graph as a member of the first category if similarity between the feature vectors of the image and the exemplars exceeds a threshold.
Dependencies are inferred from the claim text.