Graph-based cognitive swarms for object group recognition in a 3N or greater-dimensional solution space

• US 7,672,911 B2
• Filed: 05/12/2006
• Issued: 03/02/2010
• Est. Priority Date: 08/14/2004
• Status: Expired due to Fees

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Owechko, Yuri, Medasani, Swarup
• Primary Examiner(s): Vincent; David R
• Assistant Examiner(s): Rifkin; Ben M
• Application Number:
  US11/433,159
• Publication Number:
  US 20070183670A1
• Time in Patent Office: 1,390 Days
• Field of Search: 706/14
• US Class Current: 706/14
• CPC Class Codes: G06F 18/2111 by using evolutionary computational techniques, e.g. genetic algorithms
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data
• CPC Class Codes: G06V 10/771 Feature selection, e.g. selecting representative features from a multi-dimensional feature space
• CPC Class Codes: G06V 10/809 of classification results, e.g. where the classifiers operate on the same input data
• CPC Class Codes: G06V 40/103 Static body considered as a whole, e.g. static pedestrian or occupant recognition

Abstract

An object recognition system is described that incorporates swarming classifiers. The swarming classifiers comprise a plurality of software agents configured to operate as a cooperative swarm to classify an object group in a domain. Each node N represents an object in the group having K object attributes. Each agent is assigned an initial velocity vector to explore a KN-dimensional solution space for solutions matching the agent'"'"'s graph. Further, each agent is configured to search the solution space for an optimum solution. The agents keep track of their coordinates in the KN-dimensional solution space that are associated with an observed best solution (pbest) and a global best solution (gbest). The gbest is used to store the best solution among all agents which corresponds to a best graph among all agents. Each velocity vector thereafter changes towards pbest and gbest, allowing the cooperative swarm to classify of the object group.

Claims

1. A graph-based object group recognition system incorporating swarming domain classifiers, the system comprising:

A processor having a plurality of software agents configured to operate as a cooperative swarm to classify an object group in a domain, where each agent'"'"'s position in a multi-dimensional solution space represents a graph having N-nodes, where each node N represents an object in the group having K object attributes, where K>

=3, and where each agent is assigned an initial velocity vector to explore a KN-dimensional solution space for solutions matching the agent'"'"'s graph such that each agent has positional coordinates as it explores the KN-dimensional solution space, where each agent is configured to perform at least one iteration, the iteration being a search in the solution space for an optimum solution where each agent keeps track of its coordinates in the KN-dimensional solution space that are associated with an observed best solution (pbest) that the agent has identified, and a global best solution (gbest) where the gbest is used to store the best solution among all agents which corresponds to a best graph among all agents, with each velocity vector thereafter changing towards pbest and gbest, allowing the cooperative swarm to concentrate on the vicinity of the object group and classify the object group when a classification level exceeds a preset threshold.

2. A graph-based object group recognition system as set forth in claim 1, wherein the processor is further configured to perform operations of:

creating a query graph that corresponds to a user-defined query, the query graph having N-nodes;

representing the query graph as a point in a high-dimensional space solution space, where each of the N-nodes in the query graph provides K-dimensions resulting in the KN-dimensional solution space; and

initializing the cooperative swarm in the KN-dimensional solution space such that each agent in the KN-dimensional solution space corresponds to an N-node graph with K degrees of freedom for each node, where each node represents an object, and where the N-node graph that corresponds to an agent'"'"'s position represents a group of objects, and where a position of the agent in the KN-dimensional solution space defines attributes in the domain of the objects in the group, and where the agents explore the KN-dimensional solution space and converge to a location in the KN-dimensional solution space that corresponds to the graph that best matches the query graph, thereby converging to a location that best matches the user-defined query, whereby by converging to a location that best matches the user-defined query, the agents identify user-defined object groups.

3. A graph-based object group recognition system as set forth in claim 2, wherein the processor is further configured to calculate a fitness function value for a particular agent, where the fitness function value is a graph matching score between the query graph and the graph corresponding to the particular agent.

4. A graph-based object group recognition system as set forth in claim 3, wherein the graphs have node attributes and edge attributes and the processor is further configured to calculate the fitness function value using a fitness function, where the fitness function is a function of compatibilities between the node attributes in the graphs as well as compatibilities between the edge attributes of the graphs, and where the fitness function value is equal to the sum of the compatibilities of the nodes in the query and graph corresponding to a particular agent.

5. A graph-based object group recognition system as set forth in claim 4, wherein the processor is further configured to determine the compatibility between a pair of nodes in the two graphs as a cumulative measure using the actual node compatibilities as well as the compatibilities of all incident edges and the nodes connected to the edges.

6. A graph-based object group recognition system as set forth in claim 5, wherein the cumulative measure is combined using fuzzy aggregation operators to provide a score between 0 and 1 for the fitness function.

7. A graph-based object group recognition system as set forth in claim 6, wherein K equals three such that the KN-dimensional solution space is a 3N-dimensional solution space with the object attributes being spatial attributes x, y, and h, such that x and y are coordinates of an object in the domain and h is the scale of the object in the domain, and wherein the processor is further configured to perform operations of:

representing the query graph as a point in a high-dimensional space solution space, where each of the N-nodes in the query graph provides three-dimensions, resulting in a 3N-dimensional solution space; and

initializing the cooperative swarm in the 3N-dimensional solution space such that each agent in the 3N-dimensional solution space corresponds to an N-node graph with three degrees of freedom for each node, where each node represents an object and the degrees of freedom for each node are x, y, and scale, and where the N-node graph that corresponds to an agent'"'"'s position represents a group of objects with spatial relationships, and where a position of the agent in the 3N-dimensional solution space defines locations and sizes in the domain of the objects in the group, and where the agents explore the 3N-dimensional solution space and converge to a location in the 3N-dimensional solution space that corresponds to the graph that best matches the query graph, thereby converging to a location that best matches the user-defined query;

wherein each agent represents a three-node fuzzy attributed relational graph.

8. A graph-based object group recognition system as set forth in claim 1, wherein the processor is further configured to calculate a fitness function value for a particular agent, where the fitness function value is a graph matching score between the query graph and the graph corresponding to the particular agent.

9. A graph-based object group recognition system as set forth in claim 8, wherein the graphs have node attributes and edge attributes and the processor is further configured to calculate the fitness function value using a fitness function, where the fitness function is a function of compatibilities between the node attributes in the graphs as well as compatibilities between the edge attributes of the graphs, and where the fitness function value is equal to the sum of the compatibilities of the nodes in the query and graph corresponding to a particular agent.

10. A graph-based object group recognition system as set forth in claim 9, wherein the processor is further configured to determine the compatibility between a pair of nodes in the two graphs as a cumulative measure using the actual node compatibilities as well as the compatibilities of all incident edges and the nodes connected to the edges.

11. A graph-based object group recognition system as set forth in claim 10, wherein the cumulative measure is combined using fuzzy aggregation operators to provide a score between 0 and 1 for the fitness function.

12. A graph-based object group recognition system as set forth in claim 1, wherein K equals three such that the KN-dimensional solution space is a 3N-dimensional solution space with the object attributes being spatial attributes x, y, and h, such that x and y are coordinates of an object in the domain and h is the scale of the object in the domain, and wherein the processor is further configured to perform operations of:

representing the query graph as a point in a high-dimensional space solution space, where each of the N-nodes in the query graph provides three-dimensions, resulting in a 3N-dimensional solution space; and

initializing the cooperative swarm in the 3N-dimensional solution space such that each agent in the 3N-dimensional solution space corresponds to an N-node graph with three degrees of freedom for each node, where each node represents an object and the degrees of freedom for each node are x, y, and scale, and where the N-node graph that corresponds to an agent'"'"'s position represents a group of objects with spatial relationships, and where a position of the agent in the 3N-dimensional solution space defines locations and sizes in the domain of the objects in the group, and where the agents explore the 3N-dimensional solution space and converge to a location in the 3N-dimensional solution space that corresponds to the graph that best matches the query graph, thereby converging to a location that best matches the user-defined query.

13. A method for graph-based object group recognition incorporating swarming domain classifiers, the method comprising an act of:

Configuring a plurality of software agents to be initialized by a processor such that when initialized, the software agents cooperate as a cooperative swarm to classify an object group in a domain, where each agent'"'"'s position in a multi-dimensional solution space represents a graph having N-nodes, where each node N represents an object in the group having K object attributes, where K>

=3, and where each agent is assigned an initial velocity vector to explore a KN-dimensional solution space for solutions matching the agent'"'"'s graph such that each agent has positional coordinates as it explores the KN-dimensional solution space, where each agent is configured to perform at least one iteration, the iteration being a search in the solution space for an optimum solution where each agent keeps track of its coordinates in the KN-dimensional solution space that are associated with an observed best solution (pbest) that the agent has identified, and a global best solution (gbest) where the gbest is used to store the best solution among all agents which corresponds to a best graph among all agents, with each velocity vector thereafter changing towards pbest and gbest, allowing the cooperative swarm to concentrate on the vicinity of the object group and classify the object group when a classification level exceeds a preset threshold.

14. A method as set forth in claim 13, further comprising acts of:

creating a query graph that corresponds to a user-defined query, the query graph having N-nodes;

representing the query graph as a point in a high-dimensional space solution space, where each of the N-nodes in the query graph provides K-dimensions resulting in the KN-dimensional solution space; and

initializing the cooperative swarm in the KN-dimensional solution space such that each agent in the KN-dimensional solution space corresponds to an N-node graph with K degrees of freedom for each node, where each node represents an object, and where the N-node graph that corresponds to an agent'"'"'s position represents a group of objects, and where a position of the agent in the KN-dimensional solution space defines attributes in the domain of the objects in the group, and where the agents explore the KN-dimensional solution space and converge to a location in the KN-dimensional solution space that corresponds to the graph that best matches the query graph, thereby converging to a location that best matches the user-defined query, whereby by converging to a location that best matches the user-defined query, the agents identify user-defined object groups.

15. A method as set forth in claim 14, further comprising an act of calculating a fitness function value for a particular agent, where the fitness function value is a graph matching score between the query graph and the graph corresponding to the particular agent.

16. A method as set forth in claim 15, wherein the graphs have node attributes and edge attributes, and further comprising an act of calculating the fitness function value using a fitness function, where the fitness function is a function of compatibilities between the node attributes in the graphs as well as compatibilities between the edge attributes of the graphs, and where the fitness function value is equal to the sum of the compatibilities of the nodes in the query and graph corresponding to a particular agent.

17. A method as set forth in claim 16, further comprising an act of determining the compatibility between a pair of nodes in the two graphs as a cumulative measure using the actual node compatibilities as well as the compatibilities of all incident edges and the nodes connected to the edges.

18. A method as set forth in claim 17, further comprising an act of combining the cumulative measure using fuzzy aggregation operators to provide a score between 0 and 1 for the fitness function.

19. A method as set forth in claim 18, wherein in the act of configuring the plurality of software agents such that each agent is assigned an initial velocity vector to explore a KN-dimensional solution space, the agents are configured such that K equals three where the KN-dimensional solution space is a 3N-dimensional solution space with the object attributes being spatial attributes x, y, and h, such that x and y are coordinates of an object in the domain and h is the scale of the object in the domain, and further comprising acts of:

representing the query graph as a point in a high-dimensional space solution space, where each of the N-nodes in the query graph provides three-dimensions, resulting in a 3N-dimensional solution space; and

initializing the cooperative swarm in the 3N-dimensional solution space such that each agent in the 3N-dimensional solution space corresponds to an N-node graph with three degrees of freedom for each node, where each node represents an object and the degrees of freedom for each node are x, y, and scale, and where the N-node graph that corresponds to an agent'"'"'s position represents a group of objects with spatial relationships, and where a position of the agent in the 3N-dimensional solution space defines locations and sizes in the domain of the objects in the group, and where the agents explore the 3N-dimensional solution space and converge to a location in the 3N-dimensional solution space that corresponds to the graph that best matches the query graph, thereby converging to a location that best matches the user-defined query;

wherein each agent represents a three-node fuzzy attributed relational graph.

20. A method as set forth in claim 13, further comprising an act of calculating a fitness function value for a particular agent, where the fitness function value is a graph matching score between the query graph and the graph corresponding to the particular agent.

21. A method as set forth in claim 20, wherein the graphs have node attributes and edge attributes, and further comprising an act of calculating the fitness function value using a fitness function, where the fitness function is a function of compatibilities between the node attributes in the graphs as well as compatibilities between the edge attributes of the graphs, and where the fitness function value is equal to the sum of the compatibilities of the nodes in the query and graph corresponding to a particular agent.

22. A method as set forth in claim 21, further comprising an act of determining the compatibility between a pair of nodes in the two graphs as a cumulative measure using the actual node compatibilities as well as the compatibilities of all incident edges and the nodes connected to the edges.

23. A method as set forth in claim 22, further comprising an act of combining the cumulative measure using fuzzy aggregation operators to provide a score between 0 and 1 for the fitness function.

24. A method as set forth in claim 13, wherein in the act of configuring the plurality of software agents such that each agent is assigned an initial velocity vector to explore a KN-dimensional solution space, the agents are configured such that K equals three where the KN-dimensional solution space is a 3N-dimensional solution space with the object attributes being spatial attributes x, y, and h, such that x and y are coordinates of an object in the domain and h is the scale of the object in the domain, and further comprising acts of:

representing the query graph as a point in a high-dimensional space solution space, where each of the N-nodes in the query graph provides three-dimensions, resulting in a 3N-dimensional solution space; and

initializing the cooperative swarm in the 3N-dimensional solution space such that each agent in the 3N-dimensional solution space corresponds to an N-node graph with three degrees of freedom for each node, where each node represents an object and the degrees of freedom for each node are x, y, and scale, and where the N-node graph that corresponds to an agent'"'"'s position represents a group of objects with spatial relationships, and where a position of the agent in the 3N-dimensional solution space defines locations and sizes in the domain of the objects in the group, and where the agents explore the 3N-dimensional solution space and converge to a location in the 3N-dimensional solution space that corresponds to the graph that best matches the query graph, thereby converging to a location that best matches the user-defined query.

25. A computer program product for graph-based object recognition, the computer program product comprising computer-readable instruction means stored computer-readable medium that are executable by a computer for causing the computer to:

Initialize a plurality of software agents to cooperate as a cooperative swarm to classify an object group in a domain, where each agent'"'"'s position in a multi-dimensional solution space represents a graph having N-nodes, where each node N represents an object in the group having K object attributes, where K>

=3, and where each agent is assigned an initial velocity vector to explore a KN-dimensional solution space for solutions matching the agent'"'"'s graph such that each agent has positional coordinates as it explores the KN-dimensional solution space, where each agent is configured to perform at least one iteration, the iteration being a search in the solution space for an optimum solution where each agent keeps track of its coordinates in the KN-dimensional solution space that are associated with an observed best solution (pbest) that the agent has identified, and a global best solution (gbest) where the gbest is used to store the best solution among all agents which corresponds to a best graph among all agents, with each velocity vector thereafter changing towards pbest and gbest, allowing the cooperative swarm to concentrate on the vicinity of the object group and classify the object group when a classification level exceeds a preset threshold.

26. A computer program product as set forth in claim 25, further comprising instruction means for causing the computer to perform operations of:

creating a query graph that corresponds to a user-defined query, the query graph having N-nodes;

representing the query graph as a point in a high-dimensional space solution space, where each of the N-nodes in the query graph provides K-dimensions resulting in the KN-dimensional solution space; and

initializing the cooperative swarm in the KN-dimensional solution space such that each agent in the KN-dimensional solution space corresponds to an N-node graph with K degrees of freedom for each node, where each node represents an object, and where the N-node graph that corresponds to an agent'"'"'s position represents a group of objects, and where a position of the agent in the KN-dimensional solution space defines attributes in the domain of the objects in the group, and where the agents explore the KN-dimensional solution space and converge to a location in the KN-dimensional solution space that corresponds to the graph that best matches the query graph, thereby converging to a location that best matches the user-defined query, whereby by converging to a location that best matches the user-defined query, the agents identify user-defined object groups.

27. A computer program product as set forth in claim 26, further comprising instruction means for causing a computer to perform an operation of calculating a fitness function value for a particular agent, where the fitness function value is a graph matching score between the query graph and the graph corresponding to the particular agent.

28. A computer program product as set forth in claim 27, wherein the graphs have node attributes and edge attributes, and wherein the computer program product further comprises instruction means for causing a computer to perform an operation of calculating the fitness function value using a fitness function, where the fitness function is a function of compatibilities between the node attributes in the graphs as well as compatibilities between the edge attributes of the graphs, and where the fitness function value is equal to the sum of the compatibilities of the nodes in the query and graph corresponding to a particular agent.

29. A computer program product as set forth in claim 28, further comprising instruction means for causing a computer to perform an operation of determining the compatibility between a pair of nodes in the two graphs as a cumulative measure using the actual node compatibilities as well as the compatibilities of all incident edges and the nodes connected to the edges.

30. A computer program product as set forth in claim 29, further comprising instruction means for causing a computer to perform an operation of combining the cumulative measure using fuzzy aggregation operators to provide a score between 0 and 1 for the fitness function.

31. A computer program product as set forth in claim 30, further comprising instruction means for causing a computer to perform operations of:

representing the query graph as a point in a high-dimensional space solution space, where each of the N-nodes in the query graph provides three-dimensions, resulting in a 3N-dimensional solution space; and

initializing the cooperative swarm in the 3N-dimensional solution space such that each agent in the 3N-dimensional solution space corresponds to an N-node graph with three degrees of freedom for each node, where each node represents an object and the degrees of freedom for each node are x, y, and scale, and where the N-node graph that corresponds to an agent'"'"'s position represents a group of objects with spatial relationships, and where a position of the agent in the 3N-dimensional solution space defines locations and sizes in the domain of the objects in the group, and where the agents explore the 3N-dimensional solution space and converge to a location in the 3N-dimensional solution space that corresponds to the graph that best matches the query graph, thereby converging to a location that best matches the user-defined query;

wherein each agent represents a three-node fuzzy attributed relational graph.

32. A computer program product as set forth in claim 25, further comprising instruction means for causing a computer to perform an operation of calculating a fitness function value for a particular agent, where the fitness function value is a graph matching score between the query graph and the graph corresponding to the particular agent.

33. A computer program product as set forth in claim 32, wherein the graphs have node attributes and edge attributes, and wherein the computer program product further comprises instruction means for causing a computer to perform an operation of calculating the fitness function value using a fitness function, where the fitness function is a function of compatibilities between the node attributes in the graphs as well as compatibilities between the edge attributes of the graphs, and where the fitness function value is equal to the sum of the compatibilities of the nodes in the query and graph corresponding to a particular agent.

34. A computer program product as set forth in claim 33, further comprising instruction means for causing a computer to perform an operation of determining the compatibility between a pair of nodes in the two graphs as a cumulative measure using the actual node compatibilities as well as the compatibilities of all incident edges and the nodes connected to the edges.

35. A computer program product as set forth in claim 34, further comprising instruction means for causing a computer to perform an operation of combining the cumulative measure using fuzzy aggregation operators to provide a score between 0 and 1 for the fitness function.

36. A computer program product as set forth in claim 25, further comprising instruction means for causing a computer to perform operations of:

representing the query graph as a point in a high-dimensional space solution space, where each of the N-nodes in the query graph provides three-dimensions, resulting in a 3N-dimensional solution space; and

initializing the cooperative swarm in the 3N-dimensional solution space such that each agent in the 3N-dimensional solution space corresponds to an N-node graph with three degrees of freedom for each node, where each node represents an object and the degrees of freedom for each node are x, y, and scale, and where the N-node graph that corresponds to an agent'"'"'s position represents a group of objects with spatial relationships, and where a position of the agent in the 3N-dimensional solution space defines locations and sizes in the domain of the objects in the group, and where the agents explore the 3N-dimensional solution space and converge to a location in the 3N-dimensional solution space that corresponds to the graph that best matches the query graph, thereby converging to a location that best matches the user-defined query.