| Graph-based cognitive swarms for object group recognition -> Monitor Keywords |
|
|
  Graph-based cognitive swarms for object group recognitionUSPTO Application #: 20070183670Title: Graph-based cognitive swarms for object group 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. (end of abstract)
Agent: Tope-mckay & Associates - Malibu, CA, US Inventors: Yuri Owechko, Swarup Medasani USPTO Applicaton #: 20070183670 - Class: 382224000 (USPTO) Related Patent Categories: Image Analysis, Pattern Recognition, Classification The Patent Description & Claims data below is from USPTO Patent Application 20070183670. Brief Patent Description - Full Patent Description - Patent Application Claims
PRIORITY CLAIM [0001] This patent application is a Continuation-in-Part application, claiming the benefit of priority of U.S. Non-Provisional patent application Ser. No. 10/918,336, filed on Aug. 14, 2004, entitled, "Object Recognition System Incorporating Swarming Domain Classifiers." BACKGROUND OF INVENTION [0002] (1) Field of Invention [0003] The present invention relates to an object group recognition and tracking system, and more particularly, to a object recognition and tracking system that utilizes graph-matching to identify and track groups of objects. [0004] (2) Related Art [0005] Typical approaches to graph matching include different tree search algorithms such as sequential tree searches and branch and bound searches. Such techniques are described by L. Shapiro and R. M. Haralick, in "Structural description and inexact matching," IEEE PAMI 3(5), 504-519, 1981, and by W. H. Tsai and K. S. Fu, in "Error-correcting isomorphism of attributed relational graphs for pattern analysis," IEEE MSC, 9, 757-768, 1979. [0006] Other approaches define an objective function and solve a continuous optimization problem to find the global minima. Such techniques were described by 3. S. Gold and A. Rangarajan, in "A graduated assignment algorithm for graph matching," IEEE PAMI, 18, 309-319, April 1996, and by S. Medasani and R. Krishnapuram, in "Graph Matching by Relaxation of Fuzzy Assignments," IEEE Transactions on Fuzzy Systems, 9(1), 173-183, February 2001. [0007] Additionally, in a publication by A. D. J Cross, R. C. Wilson, and E. R. Hancock, entitled, "Inexact graph matching using genetic search," Pattern Recognition, 30(6), 953-970, 1997, the authors have shown that using genetic search methods for inexact matching problems outperforms conventional optimization methods such as gradient descent and simulated annealing. [0008] Furthermore, in a publication by K. G. Khoo and P. N. Suganthan, entitled, "Structural Pattern Recognition Using Genetic Algorithms with Specialized Operators," IEEE Trans. On Systems, Man, and Cybernetics-Part B, 33(1), February 2003, the authors attempt to improve genetic algorithm (GA) based graph-matching procedures leading to more accurate mapping and faster convergence. The population solutions are represented by integer strings indicating the mapping between source and target graphs. [0009] Graphs of various types have been widely used as representational tools in many applications such as object recognition, knowledge representation and scene description. Fuzzy attributed relational graphs (FARGs) are a powerful way to model the inherent uncertainty in several of the above domains. FARGs have been described by R. Krishnapuram, S. Medasani, S. Jung and Y. Choi, in "FIRST--A Fuzzy Information Retrieval System," IEEE Trans. On Knowledge and Data Engineering, October 2004, and in the article entitled, "Graph Matching by Relaxation of Fuzzy Assignments." The computational complexity of graph isomorphism is still an open question, i.e., whether it belongs to the Polynomial (P) or Nondeterministic-Polynomial (NP) class of problems. However, the problem of sub-graph isomorphism and inexact graph matching is known to be a member of the NP-complete class for which it is widely believed that only exponentially complex deterministic solutions exist. [0010] A need exists to solve this hard combinatorial problem non-deterministically by using ideas from evolutionary systems. Most of the previous approaches use a single solution that is altered heuristically by minimizing an objective function or stochastically modifying the solution. Therefore, a need further exists to employ a population of potential solutions that interact to find the optimum solution for the particular problem at hand. The present invention solves such a need by using a population of agents that search the solution space and cooperatively find the optimum solution. SUMMARY OF INVENTION [0011] The present invention relates to a graph-based object group recognition system incorporating swarming domain classifiers. The system comprises a processor having a plurality of software agents. The software agents are configured to operate as a cooperative swarm to classify an object group in a domain. Each agent's position in a multi-dimensional solution space represents a graph having N-nodes. Each node N represents an object in the group having K object attributes. Further, 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. Additionally, each agent is configured to perform at least one iteration. The iteration is 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). 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 concentrate on the vicinity of the object group and classify the object group when a classification level exceeds a preset threshold. [0012] In another aspect, the processor is further configured to create a query graph that corresponds to a user-defined query, where the query graph has N-nodes. The processor also represents the query graph as a point in a high-dimensional space solution space. Each of the N-nodes in the query graph provides K-dimensions resulting in the KN-dimensional solution space. The processor is further configured to initialize 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. The N-node graph that corresponds to an agent's position represents a group of objects. Additionally, a position of the agent in the KN-dimensional solution space defines attributes in the domain of the objects in the group. 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. By converging to a location that best matches the user-defined query, the agents identify user-defined object groups. [0013] In another aspect, the processor is further configured to calculate a fitness function value for a particular agent. The fitness function value is a graph matching score between the query graph and the graph corresponding to the particular agent. [0014] The graphs have node attributes and edge attributes and the processor is further configured to calculate the fitness function value using a fitness function. 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. Additionally, 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. [0015] In another aspect, 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. [0016] In another aspect, the cumulative measure is combined using fuzzy aggregation operators to provide a score between 0 and 1 for the fitness function. [0017] In yet another aspect, 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. In this aspect, the processor is configured to represent the query graph as a point in a 3N-dimensional solution space, and initialize 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. Each node represents an object and the degrees of freedom for each node are x, y, and scale. The N-node graph that corresponds to an agent's position represents a group of objects with spatial relationships. A position of the agent in the 3N-dimensional solution space defines locations and sizes in the domain of the objects in the group. Therefore, 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. [0018] Finally, as can be appreciated by one in the art, the present invention also includes a method and computer program product for causing a computer to carrying out the operations of the invention described herein. BRIEF DESCRIPTION OF THE DRAWINGS [0019] The objects, features, and advantages of the present invention will be apparent from the following detailed descriptions of the various aspects of the invention in conjunction with reference to the following drawings, where: [0020] FIG. 1 is an illustration of an exemplary object recognition using a cognitive swarm of classifier agents; Continue reading... Full patent description for Graph-based cognitive swarms for object group recognition Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Graph-based cognitive swarms for object group recognition patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Graph-based cognitive swarms for object group recognition or other areas of interest. ### Previous Patent Application: Methods for finding and characterizing a deformed pattern in an image Next Patent Application: Multi-view cognitive swarm for object recognition and 3d tracking Industry Class: Image analysis ### FreshPatents.com Support Thank you for viewing the Graph-based cognitive swarms for object group recognition patent info. IP-related news and info Results in 13.99249 seconds Other interesting Feshpatents.com categories: Novartis , Pfizer , Philips , Polaroid , Procter & Gamble , |
||
