Selective learning for growing a graph lattice

• US 9,053,579 B2
• Filed: 06/19/2012
• Issued: 06/09/2015
• 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): Drennan, Barry
• Assistant Examiner(s): WOLDEMARIAM, AKLILU K
• Application Number:
  US13/527,071
• Publication Number:
  US 20130335422A1
• Time in Patent Office: 1,085 Days
• Field of Search: 382/124, 382/155, 382/159, 382/225, 382/116, 382/187, 382/195, 382/217, 706/11, 706/20, 706/21, 706/55
• US Class Current: 1/1
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

A system and method generate a graph lattice from exemplary images. At least one processor receives exemplary data graphs of the exemplary images and generates graph lattice nodes of size one from primitives. Until a termination condition is met, the at least one processor repeatedly: 1) generates candidate graph lattice nodes from accepted graph lattice nodes; 2) selects one or more candidate graph lattice nodes preferentially discriminating exemplary data graphs which are less discriminable than other exemplary data graphs using the accepted graph lattice nodes; and 3) promotes the selected graph lattice nodes to accepted status. The graph lattice is formed from the accepted graph lattice nodes and relations between the accepted graph lattice nodes.

Claims

1. A system for generating a graph lattice from exemplary images, said system comprising:

at least one processor programmed to;

receive exemplary data graphs of the exemplary images, wherein nodes of the exemplary data graphs are formed from primitives;

generate graph lattice nodes of size one from the primitives;

until a termination condition is met, repeatedly;

generate candidate graph lattice nodes from accepted graph lattice nodes, including the graph lattice nodes of size one and promoted graph lattice nodes, and the exemplary data graphs;

select one or more candidate graph lattice nodes, the selected candidate graph lattice nodes preferentially discriminating exemplary data graphs which are less discriminable than other exemplary data graphs using the accepted graph lattice nodes, wherein the selection of the one or more candidate graph lattice nodes includes a scoring operation where a high score indicates that a particular exemplary data graph is mapped to by many subgraphs of accepted graph lattice nodes that are not mapped to many other exemplary data graphs, indicating there are many discriminating subgraph features for the particular exemplary data graph, and a low score indicates the particular exemplary data graph is not mapped to by unique or highly discriminative features, and is more confusable with other exemplary data graphs, wherein each graph lattice node, including the accepted graph lattice nodes and the candidate graph lattice nodes, includes a subgraph, a vote weight, and at least one mapping of the subgraph to the exemplary data graphs, and wherein the scoring operation includes;

scoring each candidate graph lattice node according to a scoring function, the scoring function including a ratio, wherein a numerator of the ratio is based on the vote weight of the candidate graph lattice node, and wherein a denominator of the ratio is a summation of vote weights of accepted graph lattice nodes mapping to exemplary data graphs the candidate graph lattice node maps to; and

,

the selection of the one or more candidate graph lattice nodes further includes selecting most highly scored candidate graph lattice nodes according to selection criteria; and

,

promote the selected graph lattice nodes to accepted status;

wherein the graph lattice is formed from the accepted graph lattice nodes and relations between the accepted graph lattice nodes.

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

3. The system according to claim 1, wherein the termination condition is at least one of:

the number of accepted graph lattice nodes at a level exceeds a predetermined threshold;

the number of accepted graph lattice nodes exceeds a predetermined threshold; and

,

promotion of all of the candidate graph lattice nodes.

4. The system according to claim 1, wherein nodes of size 1 of the graph lattice correspond to the 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 primitives.

5. The system according to claim 1, wherein the vote weight is 1/M, wherein M is the number of exemplary data graphs the subgraph maps to.

6. The system according to claim 1, wherein the vote weight is 1/M, wherein M is the number of exemplary data graphs the subgraph maps to.

7. The system according to claim 1, wherein the numerator of the ratio is zero in response to the candidate graph lattice node mapping to less than a predetermined number of exemplary data graphs, and the numerator is the vote weight of the candidate graph lattice node otherwise.

8. The system according to claim 1, wherein the selection criteria is at least one of:

select candidate graph lattice nodes with scores exceeding a predetermined threshold;

select candidate graph lattice nodes with scores falling within a top predetermined percentile; and

,

select a predetermined number of the most highly scored candidate graph lattice nodes.

9. The system according to claim 1, wherein the processor is further programmed to:

receive a test data graph of a test image, wherein nodes of the test data graph are formed from the primitives, and wherein the exemplary images correspond to classes, including a class of the test image;

map the subgraphs of the accepted graph lattice nodes to the test data graph;

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

,

determine the class of the test image from the weighted votes, the class of the test image being the class of the exemplary data graph with the highest weighted vote.

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

10. A method for generating a graph lattice from exemplary images, said method comprising:

receive by at least one processor exemplary data graphs of the exemplary images, wherein nodes of the exemplary data graphs are formed from primitives;

generate by the at least one processor graph lattice nodes of size one from the primitives;

until a termination condition is met and by the at least one processor, repeatedly;

generate candidate graph lattice nodes from accepted graph lattice nodes, including the graph lattice nodes of size one and promoted graph lattice nodes, and the exemplary data graphs;

select one or more candidate graph lattice nodes, the selected candidate graph lattice nodes preferentially discriminating exemplary data graphs which are less discriminable than other exemplary data graphs using the accepted graph lattice nodes, wherein the selection of the one or more candidate graph lattice nodes includes a scoring operation where a high score indicates that a particular exemplary data graph is mapped to by many subgraphs of accepted graph lattice nodes that are not mapped to many other exemplary data graphs, indicating there are many discriminating subgraph features for the particular exemplary data graph, and a low score indicates the particular exemplary data graph is not mapped to by unique or highly discriminative features, and is more confusable with other exemplary data graphs, wherein each graph lattice node, including the accepted graph lattice nodes and the candidate graph lattice nodes, includes a subgraph, a vote weight, and at least one mapping of the subgraph to the exemplary data graphs, and wherein the scoring operation includes;

scoring each candidate graph lattice node according to a scoring function, the scoring function including a ratio, wherein a numerator of the ratio is based on the vote weight of the candidate graph lattice node, and wherein a denominator of the ratio is a summation of vote weights of accepted graph lattice nodes mapping to exemplary data graphs the candidate graph lattice node maps to; and

,

the selection of the one or more candidate graph lattice nodes further includes the selection of most highly scored candidate graph lattice nodes according to selection criteria; and

,

promote the selected graph lattice nodes to accepted status;

wherein the graph lattice is formed from the accepted graph lattice nodes and relations between the accepted graph lattice nodes.

12. The method according to claim 10, wherein the termination condition is at least one of:

the number of accepted graph lattice nodes at a level exceeds a predetermined threshold;

the number of accepted graph lattice nodes exceeds a predetermined threshold; and

,

promotion of all of the candidate graph lattice nodes.

13. The method according to claim 10, wherein the vote weight is 1/M, wherein M is the number of exemplary data graphs the subgraph maps to.

14. The method according to claim 10, wherein the numerator of the ratio is zero in response to the candidate graph lattice node mapping to less than a predetermined number of exemplary data graphs, and the numerator is the vote weight of the candidate graph lattice node otherwise.

15. The method according to claim 10, wherein the selection criteria is at least one of:

select candidate graph lattice nodes with scores exceeding a predetermined threshold;

select candidate graph lattice nodes with scores falling within a top predetermined percentile; and

,

select a predetermined number of the most highly scored candidate graph lattice nodes.

16. The system according to claim 10, wherein each graph lattice node, including the accepted graph lattice nodes and the candidate graph lattice nodes, includes a subgraph, a vote weight, and at least one mapping of the subgraph to the exemplary data graphs, and wherein the processor is further programmed to:

receive a test data graph of a test image, wherein nodes of the test data graph are formed from the primitives, and wherein the exemplary images correspond to classes, including a class of the test image;

map the subgraphs of the accepted graph lattice nodes to the test data graph;

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

,

determine the class of the test image from the weighted votes, the class of the test image being the class of the exemplary data graph with the highest weighted vote.

17. A system for generating a graph lattice from exemplary images, said system comprising:

at least one processor programmed to;

receive exemplary data graphs of the exemplary images, wherein nodes of the exemplary data graphs are formed from primitives;

generate graph lattice nodes of size one from the primitives;

until a termination condition is met, repeatedly;

generate candidate graph lattice nodes from accepted graph lattice nodes, including the graph lattice nodes of size one and promoted graph lattice nodes, and the exemplary data graphs, wherein each graph lattice node, including the accepted graph lattice nodes and the candidate graph lattice nodes, includes a subgraph, a vote weight, and at least one mapping of the subgraph to the exemplary data graphs;

score each candidate graph lattice node according to a scoring function, the scoring function including a ratio, wherein a numerator of the ratio is based on the vote weight of the candidate graph lattice node, and wherein a denominator of the ratio is a summation of vote weights of accepted graph lattice nodes mapping to exemplary data graphs the candidate graph lattice node maps to;

select most highly scored candidate graph lattice nodes according to selection criteria; and

,

promote the selected graph lattice nodes to accepted status;

wherein the graph lattice is formed from the accepted graph lattice nodes and relations between the accepted graph lattice nodes.