Weighted feature voting for classification using a graph lattice

• US 8,831,339 B2
• Filed: 06/19/2012
• Issued: 09/09/2014
• Est. Priority Date: 06/19/2012
• 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): MARIAM, DANIEL G
• Application Number:
  US13/527,032
• Publication Number:
  US 20130336580A1
• Time in Patent Office: 812 Days
• Field of Search: None
• US Class Current: 382/159
• CPC Class Codes: G06V 30/1988 Graph matching graphical image representation G06V30/18181

Abstract

A system and method classify a test image. At least one processor receives a data graph computed from the test image. Further, a graph lattice is received. The graph lattice includes a plurality of nodes, each including a subgraph, a weight and at least one mapping of the subgraph to data graphs of a plurality of training images. The training images correspond to a plurality of classes. The data graph of the test image is mapped by the subgraphs of the nodes. Mappings between the graph lattice and the data graphs of the training images are compared with mappings between the graph lattice and the data graph of the test image to determine weighted votes of similarity between the data graphs of the training images and the data graph of the test image. The class of the test image is determined from the weighted votes.

Claims

1. A system for classifying a test image, said system comprising:

at least one processor programmed to;

receive a data graph of the test image;

receive a graph lattice, the graph lattice including a plurality of nodes, each of the plurality of nodes including a subgraph, a weight and at least one mapping of the subgraph to data graphs of a plurality of training images, the plurality of training images corresponding to a plurality of classes;

map the data graph of the test image by the subgraphs of the plurality of nodes;

compare mappings between the graph lattice and the data graphs of the training images with mappings between the graph lattice and the data graph of the test image to determine, for each of the training images, a weighted vote of similarity between the data graph of the training image and the data graph of the test image, the weighted vote based on the weights of the plurality of nodes; and

,

determine a class of the test image from the weighted votes of the training images, the class of the test image being the class of the training image with the highest weighted vote above a threshold number of votes.

2. The system according to claim 1, wherein the data graph of the test image and the data graphs of the plurality of training images represent the corresponding images using primitives, the primitives corresponding to data graph nodes.

3. The system according to claim 2, wherein the primitives include junction types of rectilinear line art.

4. The system according to claim 1, wherein the graph lattice is a sparsely populated graph lattice generated from the training images.

5. The system according to claim 1, wherein nodes of size 1 of the graph lattice correspond to one of a plurality of primitives and nodes of size i>

1 of the graph lattice each include a subgraph comprised of a subgraph of a node of size i−

1 and one of the plurality of primitives.

6. The system according to claim 1, wherein the comparison includes:

for each mapping between a node of the graph lattice and the data graph of the test image;

for each mapping between the node of the graph lattice and the data graphs of the training images;

comparing the mapping of the test image with the mapping of the training image to determine a level of similarity; and

,

in response to the level of similarity exceeding a predetermined level, add a weighted vote for the training image corresponding to the mapping of the training images to a vote accumulator;

wherein the class of the test image is determined using the vote accumulator.

7. The system according to claim 6, wherein the comparing the mapping of the test image with the mapping of the training images includes:

comparing a geometric arrangement of a subgraph of the test image corresponding to the mapping of the test image with a subgraph of the training images corresponding to the mapping of the training images.

8. The system according to claim 1, wherein the weighted votes of similarity of the training images are based on geometric similarity between subgraphs of the test image and subgraphs of the training images.

9. The system according to claim 1, wherein the weight decreases as the number of times the subgraph maps to the data graphs of the training images increases.

10. The system according to claim 1, wherein the mapping includes mapping the subgraphs of the plurality of nodes to the data graph of the test image.

11. A method for classifying a test image, said method comprising:

receiving by at least one processor a data graph of the test image;

receiving by the at least one processor a graph lattice, the graph lattice including a plurality of nodes, each of the plurality of nodes including a subgraph, a weight and at least one mapping of the subgraph to data graphs of a plurality of training images, the plurality of training images corresponding to a plurality of classes;

mapping by the at least one processor the data graph of the test image by the subgraphs of the plurality of nodes;

comparing by the at least one processor mappings between the graph lattice and the data graphs of the training images with mappings between the graph lattice and the data graph of the test image to determine, for each of the training images, a weighted vote of similarity between the data graph of the training image and the data graph of the test image, the weighted vote based on the weights of the plurality of nodes; and

,

determining by the at least one processor a class of the test image from the weighted votes of the training images, the class of the test image being the class of the training image with the highest weighted vote above a threshold number of votes.

12. The method according to claim 11, wherein the data graph of the test image and the data graphs of the plurality of training images represent the corresponding images using primitives, the primitives corresponding to data graph nodes.

13. The method according to claim 12, wherein the primitives include junction types of rectilinear line art.

14. The method according to claim 11, wherein the graph lattice is a sparsely populated graph lattice generated from the training images.

15. The method according to claim 11, wherein nodes of size 1 of the graph lattice correspond to one of a plurality of primitives and nodes of size i>

1 of the graph lattice each include a subgraph comprised of a subgraph of a node of size i−

1 and one of the plurality of primitives.

16. The method according to claim 11, wherein the comparison includes:

for each mapping between a node of the graph lattice and the data graph of the test image;

for each mapping between the node of the graph lattice and the data graphs of the training images;

comparing the mapping of the test image with the mapping of the training images to determine a level of similarity; and

,

in response to the level of similarity exceeding a predetermined level, add a weighted vote for the training image corresponding to the mapping of the training images to a vote accumulator;

wherein the class of the test image is determined using the vote accumulator.

17. The method according to claim 16, wherein the comparing the mapping of the test image with the mapping of the training images includes:

comparing a geometric arrangement of a subgraph of the test image corresponding to the mapping of the test image with a subgraph of the training images corresponding to the mapping of the training images.

18. The method according to claim 11, wherein the weighted votes of similarity of the training images are based on geometric similarity between subgraphs of the test image and subgraphs of the training images.

19. The method according to claim 11, wherein the weight decreases as the number of times the subgraph maps to the data graphs of the training images increases.

20. A system for classifying a test image, said system comprising:

at least one processor programmed to;

receive a data graph of the test image;

receive a graph lattice, the graph lattice including a plurality of nodes, each of the plurality of nodes including a subgraph, a weight and at least one mapping of the subgraph to data graphs of a plurality of training images, the plurality of training images corresponding to a plurality of classes;

map the subgraphs of the plurality of nodes to the data graph of the test image;

for each mapping between a node of the graph lattice and the data graph of the test image, compare the mapping of the test image with each mapping between the node of the graph lattice and the data graphs of the training images;

based on the comparisons, determine, for each of the training images, a weighted vote of similarity between the data graph of the training image and the data graph of the test image, the weighted vote based on the weights of the plurality of nodes; and

,

determine the class of the test image from the weighted votes of the training images, the class of the test image being the class of the training image with the highest weighted vote above a threshold number of votes.