US 7,599,894 B2Grant

Object recognition using a cognitive swarm vision framework with attention mechanisms

Issue Date:2009-10-06

•30 Claims

•9 Drawing Sheets

Abstract

An object recognition system is described that incorporates swarming classifiers with attention mechanisms. The object recognition system includes a cognitive map having a one-to-one relationship with an input image domain. The cognitive map records information that software agents utilize to focus a cooperative swarm's attention on regions likely to contain objects of interest. Multiple agents operate as a cooperative swarm to classify an object in the domain. Each agent is a classifier and is assigned a velocity vector to explore a solution space for object solutions. Each agent records its coordinates in multi-dimensional space that are an observed best solution that the agent has identified, and a global best solution that is used to store the best location among all agents. Each velocity vector thereafter changes to allow the swarm to concentrate on the vicinity of the object and classify the object when a classification level exceeds a preset threshold.

Metadata

Assignee

HRL Laboratories, LLC

Inventors

Yuri Owechko
Swarup Medasani

Application Information

Application Number:US 11/367,755

Filing Date:2006-03-04

Priority Date:2005-03-04

Art Unit:2129

Classifications

IPC:

G06F15/18G06K9/00G06K9/62

Patent Drawings (9 sheets)

Description

Priority Claim

[0001] This patent application is Continuation-in-Part application, claiming the benefit of priority to U.S. Provisional Application No. 60/658,942, filed Mar. 4, 2005, entitled, “Object Recognition Using a Cognitive Swarm Vision Framework with Attention Mechanism,” and also claiming the benefit of prior to U.S. Non-Provisional patent application Ser. No. 10/918,336, filed on Aug. 14, 2004, entitled, “Object Recognition Using Swarming Image Classifiers.”

Field of Invention

[0002] The present invention relates to an object recognition system and, more particularly, to an object recognition system that uses swarming image classifiers with cognitive swarms for visual recognition of an object in an image.

Background of Invention

[0003] Typically, classification of objects in an image is performed using features extracted from an analysis window which is scanned across the image. This sequential scanning search can be very computationally intensive, especially if a small window is used since a classification must be performed at each window position. Conventional approaches to reducing the computational load are based on reducing the search space by using another sensor such as radar to cue the vision system and measure the range of the object. Limitations of the radar approach include high cost, false alarms, the need to associate radar tracks with visual objects, and overall system complexity. Alternatively, previous vision-only approaches have utilized motion-based segmentation using background estimation methods to reduce the search space by generating areas of interest (AOI) around moving objects and/or using stereo vision to estimate range in order to reduce searching in scale. These methods add cost and complexity by requiring additional cameras and computations. Motion-based segmentation is also problematic under challenging lighting conditions or if background motion exists, as is the case for moving host platforms.

[0004] Motion-based systems form models of the static background in order to detect moving objects as “blobs” or silhouettes that do not match the background model. The performance will degrade, however, if the background contains high motion elements or if the camera is paning, zooming, or moving on a vehicle or aircraft or being carried by the user. Motion-based video analysis systems are also “brittle” in that the user must define rules for classifying the motion blobs that are specialized for each installation. These systems do not work well “out of the box” and require substantial setup and customization for each installation.

[0005] Additionally, there have been attempts to use genetic and evolutionary algorithms for object detection. Genetic algorithms (GAs) have been used before for decreasing the search space in vision systems. The GA systems employ a population of individual solutions that use crossover and mutation to maximize the fitness function. Other efforts have used GAs for training and adapting neural networks to recognize objects. The chromosome representation of solutions and cross-over operation in GA often result in large changes in the solution occurring as a result of small changes in the representation. This results in a “noisy” evolution of solutions and longer time to convergence.

[0006] Simulated annealing has also been used for optimization problems with discontinuous solution spaces with many local optima. However, the annealing schedule results in many more classifier evaluations than is necessary for cognitive swarms, making it impractical for real-time applications in computer vision.

[0007] Thus, a continuing need exists for an effective and efficient object recognition system for classifying objects in an image.

Summary of Invention

[0008] The present invention relates to an object recognition system, and more particularly, to an object recognition system that incorporates swarming domain (e.g., image) classifiers for visual recognition of an object in an image. The system comprises at least one cognitive map having a one-to-one relationship with an input image domain. The cognitive map is capable of recording information that software agents utilize to focus a cooperative swarm's attention on regions in the domain most likely to contain objects of interest. A plurality of software agents are included that operate as a cooperative swarm to classify an object in the domain. Each agent is a complete classifier and is assigned an initial velocity vector to explore a solution space for object solutions. Additionally, each agent is configured to perform at least one iteration as influenced by the recorded information of the cognitive map. The iteration is a search in the solution space for a potential solution optima where each agent keeps track of its coordinates in multi-dimensional 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 location among all agents with each velocity vector thereafter changing towards pbest and gbest, thereby allowing the cooperative swarm to concentrate on the vicinity of the object and classify the object when a classification level exceeds a preset threshold.

[0009] Additionally, the cognitive map is a map selected from a group consisting of a ground surface map, an interest map, an object map, and a saliency map.

[0010] The ground surface map is configured to store expected object height in pixels at each image location. The ground surface map also constrains an analysis window to an appropriate size at each domain location. Additionally, the ground surface map implements space-variant initialization of the cooperative swarm.

[0011] In another aspect, using the ground surface map, the system calculates a vertical coordinate of y of an imaged object using a pinhole imaging model. The vertical coordinate of y is calculated according to the following:

[0012]

y = - f \tan α - \frac{f (z - z_{c}) (\tan^{2} α + 1)}{Y - (z - z_{c}) \tan α},

where z is the height of the object, z_cis the camera height, Y is the distance of the object from the camera, α is the camera tilt angle, and ƒ is the camera focal length.

[0013] In yet another aspect, the interest map is configured to store swarm attracting/repelling pheromones at each domain location. Attracting pheromones have positive values and are stored to attract swarms to high saliency regions and to regions more likely to contain objects based on previous detection results or external inputs. Repelling pheromones have negative values and are stored to repel swarms away from regions that do not contain objects or which have already been explored, thereby preventing clustering of agents on low confidence regions.

[0014] In operation, the interest map is configured to run and maintain a sorted list for gbest and pbest, along with the associated F_Avalues. F_Ais an objective function and is calculated according to the following:
F_A=μ(Q₊−Q₋)+(1−μ)F_C,
where Q₊denotes an attracting pheromone and Q₋denotes a repelling pheromone, and where μ is a nonnegative weighting factor, and F_Cis an object classifier confidence value. Additionally, the interest map is updated at each iteration of the swarm and F_Ais updated for each entry in the sorted list, whereby the swarm is modified by the interest map in such a way as to focus attention on regions of increased saliency.

[0015] In yet another aspect, using the object map, the system is configured to perform multiple operations. For example, the system stores information at each domain location on previously detected objects. Additionally, the system prevents unnecessary classifier evaluations and initializes swarms only in regions where objects have not yet been detected. Furthermore, the system initializes swarms in regions more likely to contain objects based on previous detection results. The system is also configured to recognize object groups and behaviors.

[0016] In yet another aspect, system is further configured to track an object in multiple input images. In doing so, the system receives a first current input image. A global swarm is then initialized to search for objects within the input image. Local swarms are assigned to objects identified by the global swarm. A next input image is received, where the next input image is deemed the current input image and a previous current input image is deemed the previous input image. The local swarms are then initialized to search for and identify objects in the current input image. Local swarms are then deleted that lost their identified objects between the current and previous input images. Next, the global swarm is initialized to search for new objects in the current input image. Local swarms then assigned to new objects identified in the current input image. The above operations are then repeated for subsequent next images.

[0017] Finally, as can be appreciated by one in the art, the present invention also includes a method and computer program product. The method comprises acts of the operations described herein. Additionally, the computer program product comprises instruction means stored on a computer-readable medium for causing a computer to carry out the operations of the present invention.

Brief Description of the Drawings

[0018] 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:

[0019] FIG. 1 is an illustration of exemplary object recognition using a cognitive swarm of classifier agents or particles;

[0020] FIG. 2 is an illustration of exemplary multiple object recognition by a cognitive swarm consisting of human classifier agents using local image erasure;

[0021] FIG. 3 is an illustration of an overview of an attention-based cognitive swarm framework according to the present invention;

[0022] FIG. 4 is a flowchart illustrating multiple object recognition and tracking using global and local cognitive swarms;

[0023] FIG. 5 is an exemplary demonstration of pedestrian recognition and racking using global and local cognitive swarms;

[0024] FIG. 6 is an exemplary demonstration of multiple human recognition using an object map, a ground surface map, and window diversity of the attention based cognitive swarm framework according to the present invention;

[0025] FIG. 7 illustrates a component diagram depicting components of a data process system according to the present invention; and

[0026] FIG. 8 illustrates a diagram of a computer program product according to the present invention.

Detailed Description

[0027] The present invention relates to an object recognition system and, more particularly, to an object recognition system that uses swarming image classifiers with cognitive swarms for visual recognition of an object in an image. The following description is presented to enable one of ordinary skill in the art to make and use the invention and to incorporate it in the context of particular applications. Various modifications, as well as a variety of uses in different applications will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to a wide range of embodiments. Thus, the present invention is not intended to be limited to the embodiments presented, but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

[0028] In the following detailed description, numerous specific details are set forth in order to provide a more thorough understanding of the present invention. However, it will be apparent to one skilled in the art that the present invention may be practiced without necessarily being limited to these specific details. In other instances, well-known structures and devices are shown in block diagram form, rather than in detail, in order to avoid obscuring the present invention.

[0029] The reader's attention is directed to all papers and documents which are filed concurrently with this specification and which are open to public inspection with this specification, and the contents of all such papers and documents are incorporated herein by reference. Additionally, the process for object recognition using swarming image classifiers draws material from the process shown and described in U.S. patent application Ser. No. 10/918,336, of which the entire disclosure is hereby incorporated by this reference as though fully set forth herein. All the features disclosed in this specification, (including any accompanying claims, abstract, and drawings) may be replaced by alternative features serving the same, equivalent or similar purpose, unless expressly stated otherwise. Thus, unless expressly stated otherwise, each feature disclosed is one example only of a generic series of equivalent or similar features.

[0030] Furthermore, any element in a claim that does not explicitly state “means for” performing a specified function, or “step for” performing a specific function, is not to be interpreted as a “means” or “step” clause as specified in 35 U.S.C. Section 112, Paragraph 6. In particular, the use of “step of” or “act of” in the claims herein is not intended to invoke the provisions of 35 U.S.C. 112, Paragraph 6.

[0031] Before describing the invention in detail, first a glossary of terms used in the description and claims is presented. Second, a description of various principal aspects of the present invention is provided. Third, an introduction is provided to provide the reader with a general understanding of the present invention. Fourth, a description of various aspects of the present invention is provided to give an understanding of the specific details.

[0032] (1) Glossary

[0033] Before describing the specific details of the present invention, a glossary is provided in which various terms used herein and in the claims are defined. The glossary provided is intended to provide the reader with a general understanding for the intended meaning of the terms, but is not intended to convey the entire scope of each term. Rather, the glossary is intended to supplement the rest of the specification in more accurately explaining the terms used.

[0034] Domain—The term “domain” refers to any searchable dimension in the solution space, non-limiting examples of which include spatial coordinates, scale, frequency, time, Doppler shift, time delay, wave length, and phase.

[0035] Instruction Means—The term “instruction means” as used with respect to this invention generally indicates a set of operations to be performed on a computer, and may represent pieces of a whole program or individual, separable, software modules. Non-limiting examples of “instruction means” include computer program code (source or object code) and “hard-coded” electronics (i.e. computer operations coded into a computer chip). The “instruction means” may be stored in the memory of a computer or on a computer readable medium such as a floppy disk, a CD-ROM, and a flash drive.

[0036] Large Core—The term “large core” refers to a relatively large volume in the solution space in which all points have classification confidence values above a given threshold. Objects tend to generate large cores.

[0037] PPSO—The term “PPSO” refers to a possibilistic particle swarm optimization algorithm that allows different groups of software agents (i.e., particles) to work together with different temporary search goals that change in different phases of the algorithm.

[0038] PSO—The term “PSO” refers to a particle swarm optimization (PSO) algorithm that searches a multi-dimensional solution space using a population of software agents (i.e., particles) in which each agent has its own velocity vector. The success of each agent in finding good solutions has an influence on the dynamics of other members of the swarm.

[0039] Sequential Niching—The term “sequential niching” refers to a method for searching a domain, where once the software agents identify and classify an object in the domain, the object is erased from the domain so that the swarm can continue searching the domain for additional objects without being distracted by the previously identified object.

[0040] Small Core—The term “small core” refers to a relatively small volume in the solution space in which all points have classification confidence values above a given threshold. Non-object false alarms tend to generate small cores.

[0041] Software Agent—The term “software agent” refers to a self-contained computer program that operates autonomously, although its behavior may be affected by the actions of other agents. The term “software agent” is also to be used interchangeable with the word “particle.”

[0042] Window—The term “window” refers to an analysis window determined by each agent's location in the image spatial coordinates and scale coordinates. The analysis window is the image region processed by the agent to determine if an object is located there.

[0043] (2) Principal Aspects

[0044] The present invention has three “principal” aspects. The first is an object recognition system using swarming domain classifiers, typically in the form of software and/or manual operations, operated using a data processing system (e.g., computer). When in the form of software, it is typically in the form of software modules configured to perform the operations described herein. The second principal aspect is a method for object recognition, the method operating using a computer system. The third principal aspect is a computer program product. The computer program product generally represents computer readable code (either source or object code) stored on a computer readable medium such as an optical storage device, e.g., a compact disc (CD) or digital versatile disc (DVD), or a magnetic storage device such as a floppy disk or magnetic tape. Other, non-limiting examples of computer readable media include hard disks, read only memory (ROM), and flash-type memories. These aspects will be described in more detail below.

[0045] (3) Introduction

[0046] A previous application by the same applicant, U.S. patent application Ser. No. 10/918,336, entitled, “Object Recognition System Incorporating Swarming Domain Classifiers,” describes a new method called “cognitive swarms.” The cognitive swarms are used for visual recognition of objects in an image which combines feature-based object classification with efficient search mechanisms based on swarm intelligence. Cognitive swarms consist of groups of object classifier agents that both cooperate and compete to find objects such as pedestrians or vehicles in video data using particle swarm optimization (PSO). As described in the previous application, a single large swarm detects and recognizes objects in images very efficiently. The present invention expands on the cognitive swarm idea by adding an attention-based framework for incorporating image saliency, past experience, and constraints on possible object positions to help guide the swarm in locating objects. The framework also includes methods for further reducing false alarms by using spatial, size, and symmetry diversity.

[0047] The method of cognitive swarms described in the previous application is a much more efficient method for finding objects in an image compared to searching based on scanning the image or using gradient information, especially if the scale of the object is not known beforehand. Both theoretical analysis and experimental results show orders of magnitude speedup over scanning or gradient-based search. The number of false alarms per image is also greatly reduced, which is very important for practical applications. The attention-based framework described in the present invention further improves the performance of cognitive swarms by allowing the classifier agents to be guided by additional information such as image saliency, past experience of the swarm, and a priori constraints on possible object positions in the image. The framework of the present invention also provides a natural way to incorporate expectations based on previous recognition results or externally-supplied rules. For example, if a vehicle has been detected, a pedestrian cognitive swarm could be made to focus its attention near the vehicle to “catch” people exiting or entering.

[0048] The attention-based cognitive swarm framework is also well-suited to analyzing video imagery with large amounts of extraneous background motion which can cause false alarms for systems that use motion as the central defining feature for recognizing objects. Unlike motion-based commercial video analysis systems such as Active Video and Object Video, the cognitive swarm framework recognizes objects using appearance-based statistical models that do not require the user to define recognition rules for each situation. Motion-based systems form models of the static background in order to detect moving objects as “blobs” or silhouettes that do not match the background model. The performance will degrade, however, if the background contains high motion elements or if the camera is panning, zooming, or moving on a vehicle or aircraft or being carried by the user. Motion-based video analysis systems are also “brittle” in that the user must define rules for classifying the motion blobs that are specialized for each installation. These systems of the prior art do not work well “out of the box” and require substantial setup and customization for each installation. Compared with the present invention, the cognitive swarm framework, however, has much greater generality. The same object classifier can be used for a wide range of installations, situations, lighting conditions, and imaging wavelengths. For example, the same pedestrian classifier can be used for both visible and infrared imagery as well as both static and moving cameras with high motion backgrounds. This is made possible by the fact that the cognitive swarm framework does not use motion to classify objects, although motion can be used as an attention mechanism to cue the system.

[0049] Instead, recognition is based on the general appearance of objects, such as the distribution of edges and textures, which is closer to how the human visual system perceives objects. Appearance-based recognition is more powerful than motion-based recognition because motion silhouettes do not preserve the internal details of objects, and information about object shapes can be lost through the smearing distortions of motion segmentation. For example, it would be useful to recognize an individual carrying a high-power weapon which can be roughly modeled as a long tube. If the tube is rotated, an appearance-based model can be matched to the rotated tube by simply rotating the model. Motion does not remove information in an appearance-based framework.

[0050] A motion-based segmentation of the tube, on the other hand, will vary drastically depending on the orientation of the motion relative to the tube. The silhouette can be longer or thinner than the tube, or disappear entirely if it stays motionless long enough to become part of the background model. In addition, appearance-based recognition can be performed at longer ranges than motion-based recognition because more information is preserved, which allows classification with fewer pixels on target. Demonstrations utilizing the present invention have yielded reliable pedestrian recognition with pedestrian heights of fewer than twenty (20) pixels. Finally, motion-based recognition tends to group adjacent moving objects together as one silhouette, making it difficult to recognize multiple pedestrians in a crowd or perform recognition by parts such as first recognizing a pedestrian and then recognizing the high-power weapon he is carrying. Appearance-based recognition is much less prone to such merging of objects.

[0051] Accordingly, the present invention describes a new object recognition framework which consists of mechanisms for modulating the attention of appearance-based cognitive swarms using imaging geometry, saliency, and experience-based cues. Saliency can consist of various factors such as motion, texture, or other features. These cues are used to direct the attention of the cognitive swarm but they are not used in the classification of the object. This is a critical distinction because it allows the cognitive swarm to be both more accurate and much less prone to false alarms while still taking advantage of saliency cues to speed up the detection of objects.

[0052] The cognitive swarm framework differs from other vision algorithms in its use of swarm intelligence at the classifier level. Optimization is performed in a solution space consisting of object location, scale, and classifier parameter dimensions, as well as possibly other dimensions. The particles swarm in this space in order to find the local optima which correspond to objects in the image. The classifier details are not visible at the abstraction level of the swarm. The approach of the present invention is substantially different from the previous work in that each particle from the population is a unique classifier. As the population swarms around the solution space, the classifiers adjust parameters to best detect the objects in the scene.

[0053] Currently, there are no existing object recognition methods that use particle swarms in which each particle is a complete object classifier. However, there have been attempts to use genetic and evolutionary algorithms for object detection. Genetic algorithms (GAs) have been used before for decreasing the search space in vision systems. These systems employ a population of individual solutions that use crossover and mutation to maximize the fitness function. Other efforts have used GAs for training and adapting neural networks to recognize objects.

[0054] The approach of the present invention is substantially different from the previous work in that each particle from the population is a unique classifier. As the swarm travels around the solution space, each classifier agent adjusts its velocity based on the best locations it and the swarm as a whole have found. This causes the swarm to condense on the region containing the best solution found thus far. This in turn increases the density of agents which increases the probability of finding a better solution.

[0055] Use of the present invention has shown that the localization volume decreases exponentially with time. An advantage of cognitive swarms over GA solutions is the natural and continuous mapping from the representation space to the solution space. The chromosome representation of solutions and cross-over operation in GA often result in large changes in the solution, which occurs as a result of small changes in the representation. This results in a “noisy” evolution of solutions and longer time to convergence. Due the cooperative nature of cognitive swarms, the cognitive swarm converges much more quickly on good regions of the solution space.

[0056] Simulated annealing has also been used for optimization problems with discontinuous solution spaces with many local optima. However, the annealing schedule results in many more classifier evaluations than is necessary for cognitive swarms, making it impractical for real-time applications in computer vision.

[0057] (4) Description

[0058] To provide the reader with a clear understanding of the present invention, first a summary is provided of the cognitive swarm method for object recognition that was described in the previous application, U.S. patent application Ser. No. 10/918,336. Next, the attention-based framework for cognitive swarms that is the subject of the present invention will be described in detail.

[0059] (4.1) Cognitive Swarm Method for Object Recognition

[0060] Cognitive swarms combine feature-based object classification with efficient search mechanisms based on particle swarm optimization. Objects in a visual scene need to be located and classified so they can be tracked effectively for automotive safety, surveillance, perimeter protection, and a variety of other government, and commercial applications. Typically, classification of objects in an image is performed using features extracted from an analysis window which is scanned across the image. This brute force search can be very computationally intensive, especially if a small window is used since a classification must be performed at each window position. Conventional approaches to reducing the computational load are based on reducing the search space by using another sensor such as scanning radar to cue the vision system and measure the range of the object. Limitations of the radar approach include high cost, false alarms, the need to associate radar tracks with visual objects, and overall system complexity.

[0061] Alternatively, previous vision-only approaches have utilized motion-based segmentation using background estimation methods to reduce the search space by generating areas of interest (AOI) around moving objects and/or using stereo vision to estimate range in order to reduce searching in scale. Two novel search mechanisms are described that can efficiently find multiple instances of multiple object classes in a scene without the need for ancillary sensors or brute force searching. This approach utilizes the particle swarm optimization (PSO) algorithm, a population based evolutionary algorithm, which is effective for optimization of a wide range of functions. The algorithm models the exploration of multi-dimensional solution space by a population of individuals where the success of each individual has an influence on the dynamics of other members of the swarm. One of the novel aspects of this approach is that two of the dimensions are used to locate objects in the image, while the rest of the dimensions are used to optimize the classifier and analysis window parameters.

[0062] PSO is a relatively simple optimization method that has its roots in artificial life in general, and to bird flocking and swarming theory in particular. Conceptually, it includes aspects of genetic algorithms and evolutionary programming. Each potential solution is assigned a randomized velocity vector and the potential solutions called particles then “fly” through the space in search of the function optima. (These particles should not be confused with particle filters, which estimate probability distributions for tracking and localization applications.) The particles are self-contained agents that classify local image patches as belonging to one of a set of classes. Each particle keeps track of its coordinates in a multi-dimensional space that are associated with the best solution (pbest) it has observed so far. A global best parameter (gbest) is used to store the best location among all particles. The velocity of each particle is then changed towards pbest and gbest in a probabilistic way according to the following update equations:
vⁱ(t)=wvⁱ(t−1)+c₁*rand( )*(pbest−xⁱ(t−1))+c₂*rand( )*(gbest−xⁱ(t−1))
xⁱ(t)=xⁱ(t−1)+vⁱ(t),
where xⁱ(t) and vⁱ(t) are the position and velocity vectors at time t of the i-th particle and c₁and c₂are parameters that weight the influence of their respective terms in the velocity update equation. w is a decay constant which allows the swarm to converge to a solution more quickly. The rand( ) function generates a random number between 0 and 1 with a uniform distribution.

[0063] The above dynamics reflect a socio-psychological model where individual particles change their beliefs in accordance with a combination of their own experience and the best experience of the group (this is in contrast to other models of cognition where an individual changes his beliefs to become more consistent with his own experience). The random element introduces a source of noise which enables an initial random search of the solution space. The search then becomes more directed after a few iterations as the swarm starts to concentrate on more favorable regions.

[0064] This type of search is much more efficient than a brute force search or gradient based search methods. It is similar to genetic algorithms in that it can be used for discontinuous and noisy solution spaces since it only requires an evaluation of the function to be optimized at each particle position, with no gradient information being used. Unlike the chromosome string representation of potential solutions used in genetic algorithms, the PSO particles do not undergo cross-over or mutation operations, they just travel to a different position, calculate the solution at that position, and compare it with their own and global previous best positions in order to update their velocity vectors. The evolution of good solutions is stable in PSO because of the way solutions are represented, e.g. small changes in the representation result in small changes in the solution, which results in improved convergence properties compared to GAs. PSO relies on the fact that in most practical problems the optimum solution usually has better than average solutions (i.e., good solution) residing in a volume around it. These good solutions tend to attract the particles to the region where the optimum lies. The swarm becomes more and more concentrated until the optimum is found (e.g., gbest no longer changes). PSO has been applied to a wide variety of optimization problems. It has been found experimentally that the number of particles and iterations required scale weakly with the dimensionality of the solution space. The total number of function evaluations is very small compared to the size of the solution space, as was shown in the previous patent application. Basic PSO searches only for a single optimum in the solution space, but various approaches have been described for finding multiple local optima or “niches.”

[0065] The basic cognitive swarm concept described in the previous application is shown in FIG. 1. As shown in FIG. 1, a swarm of classifier agents 100 (i.e., particle swarm optimization (PSO) particle), each of which is a self-contained image classifier, searches for objects 102 in a combined image 104/classifier 106 parameter solution space 108. Additionally, each agent 100 both competes and cooperates with other agents 100 using simple dynamics to find objects 102 in the scene by optimizing the classifier outputs. Furthermore, analysis and experimental results show that cognitive swarms can both improve the detection/false alarm operating point and improve update rates by orders of magnitude over conventional search methods. It should be noted that the words agent and particle are used interchangeably herein.

[0066] The objective is to find multiple instances of an object class in an input image 104. The PSO particles 100 move in a solution space 108 where two of the dimensions represent the x 110 and y 112 coordinates in the input image 104. The key concept in this approach is that each particle 100 in the PSO swarm is a self-contained object classifier which outputs a value representing the classification confidence that the image distribution in the analysis window 114 associated with that particle 100 is or is not a member of the object class. All particles implement the same classifier, only the classifier parameters vary as the particle 100 visits different positions in the solution space 108. Two of the solution space dimensions represent the location of the analysis window 114 on the input image 104. A third dimension represents the size or scale of the analysis window 114 in order to match the unknown size of objects in the image 104. Additional dimensions can be used to represent other classifier parameters such as, for example, the rotation angle of the object or the wavelength band of the image.

[0067] The method described herein differs from other vision algorithms which use swarm intelligence in that the other methods use swarms to build up features using ant colony pheromone-based ideas. In the method of the present invention, swarming is done at the classifier level in a space consisting of object location, scale, and other classifier parameter dimensions, where each particle is a complete classifier. The particles swarm in this space in order to find the local optima which correspond to objects in the image. The classifier details are not visible at the abstraction level of the swarm.

[0068] One can imagine a multidimensional surface of classifier confidence (a type of saliency map) that can be generated if the classifier is scanned across all of the dimensions. The classifier confidence map for an image can be discontinuous and noisy, with many isolated false alarms where the classifier responds incorrectly to patterns in the image. Thus, using gradient-based methods to find objects in an image is problematic, which is why an exhaustive search is usually used. By generating classifier confidence maps for many images, it has been found experimentally that objects in the scene tend to have large “cores” of high confidence values. Many false alarms tend to be isolated with small cores. Since the probability of a particle landing in or near a core is greater for a larger core, the particles are attracted more to larger cores and the number of false alarms in a image are reduced using PSO compared to exhaustive searching. In an exhaustive search, all of the false alarms in an image will be detected so the classifier must be biased towards very low false alarm rates in order to keep the overall false alarm rate low, which also has the side effect of reducing the detection rate.

[0069] In summation, the previous application described how a single large cognitive swarm can be used to recognize multiple objects in the scene through “sequential erasing” in which a detected object is erased with a gaussian distribution before reinitializing the swarm to search for additional objects. The previous application also described a “possibilistic” clustering approach for detecting multiple objects.

[0070] For illustrative purposes, exemplary results of detecting multiple objects using sequential erasure are shown in FIG. 2. As shown, the agents 100 are searching for actual objects in a combined image 104/classifier 106 parameter solution space 108.

[0071] (4.2) Attention-Based Framework for Cognitive Swarms

[0072] The present invention describes a new attention-based framework for cognitive swarm detection and recognition of objects. The framework consists of a set of “cognitive maps” that are added to the basic cognitive swarm object recognition framework described above. As shown in FIG. 3, the maps 300 have the same dimensions as the input image 104 and are in one-to-one registration with it. The maps 300 are used to record additional information that the classifier agents 100 or particles can use to improve performance and implement new capabilities. As non-limiting examples, the additional information can come from user inputs, models of the environment, image saliency cues, externally-driven expectation, or experience of other swarms. By serving as intermediaries for communication between an agent and another agent, swarm, or external input, the maps 300 improve performance by helping to focus the swarm's attention on the regions most likely to contain objects of interest. Four non-limiting examples of cognitive maps include a Ground Surface (plane) Map 302, an Interest Map 304, an Object Map 306, and a Saliency Map (the general framework is not necessarily limited to these four). FIG. 3 illustrates the logical relationship between the input image 104, cognitive maps 300, and the classifier swarm (individual agents depicted as element 100) which together form the attention framework. For further illustration, each cognitive map and various aspects of the present invention are described in further detail below.

[0073] (4.2.1) Ground Surface Map

[0074] The ground surface map 302 is used for reducing the search space of the classifier swarm when information on the location of the ground in the image 104 is available and the objects of interest can be assumed to be tied to the ground. The ground surface map is used to constrain an analysis window 114 to an appropriate size at each image location, and to implement space-variant initialization of the swarm.

[0075] The ground surface map 302 specifies the expected height of the object in pixels at every location in the image 104. This eliminates the need for searching along the dimension of object scale and reduces the number of classifier evaluations necessary for convergence. In addition, by distributing the particles 100 in inverse proportion to the expected object size at each location, more particles 100 can be initialized near the horizon where the expected object size is smaller and objects are harder to detect.

[0076] If the ground surface is a plane and a pinhole imaging model is used, a model for vertical coordinate y of an imaged object is given by:

[0077]

y = - f \tan α - \frac{f (z - z_{c}) (\tan^{2} α + 1)}{Y - (z - z_{c}) \tan α},

where z is the height of the object, z_cis the camera height, Y is the distance of the object from the camera, α is the camera tilt angle, and f is the camera focal length. The height of the object image and hence the analysis window height as a function of position in the image can be calculated from the above expression.

[0078] (4.2.2) Interest Map

[0079] The Interest Map 304 stores information on the “saliency” at each point in the input image. Saliency is defined as a measure of the degree of interest the system should have in various regions of the input image 104. It is well-known that the human visual system does not pay equal attention to all parts of the visual field. Very low level processing occurs to find salient regions which are unusual in some sense with respect to the rest of the visual field. These salient regions can consist of regions with textures, colors, motions, or other low level features that are “different” from the background. Since the saliency features are low-level and local, it is efficient to use them to direct the attention of higher level cognitive recognition processes that use the high resolution but small central field of the human visual system.

[0080] Similarly, the Interest Map 304 enables saliency measures to direct the attention of the cognitive swarm. It does this through a modification of the objective function used by the cognitive swarm to modify each particle-agent's velocity at every iteration using the previously described update equations. Previously, the objective function consisted of the object classifier confidence value F_C. The new modified objective function is given by:
F_A=μ(Q₊−Q₋)+(1−μ)F_C,

[0081] where Q₊ and Q₋ are nonnegative quantities describing the level of “positive” (attraction) and “negative” (repulsion) pheromones and μ is a nonnegative weighting factor.

[0082] Pheromones are chemicals secreted by various animals and deposited at physical locations to communicate with other animals by marking paths (attracting pheromones) or territories (repelling pheromones). Here the concept of pheromones are used as a metaphor for providing variable direction of attention for the cognitive swarm. The Interest Map 304 is a map of the net pheromone level Q₊−Q₋at each spatial location in the input image 104. The dynamic update equation for each swarm particle modifies the particle's velocity according to pbest and gbest values calculated using the new F_Aobjective function. By varying μ, the relative attraction of high pheromone points can be balanced against the attraction of high classifier confidence values.

[0083] The addition of pheromone-based spatially-varying attraction/repulsion is useful for modulating the behavior of the swarm in response to the encountered environment. For example, it can be used to focus the attention of the swarm on high saliency regions, prevent premature convergence on low confidence regions, and modulate the swarm's attention based on user input or object recognition results. It is important to note that while the Interest Map 304 can cause the swarm to focus on image regions with high saliency, the actual classification decision is made using the classifier alone. The pheromone levels are used to modulate the swarm dynamics (e.g., the swarm's spatial focus), but they do not affect the object classification. Positive pheromones generated by saliency cues such as motion or texture are used to attract the swarm towards regions of high motion and texture. However, if a classifier particle determines a position in the image has low classifier confidence, a negative pheromone is deposited at that location to counteract the effects of the positive pheromone and to force the swarm to concentrate on unexplored regions.

[0084] Positive pheromones can also be used to concentrate the swarm in certain regions based on operator inputs or the results of other object classifications. As a non-limiting example, it can be used to attract a pedestrian detection swarm to a virtual tripwire in the image in order to quickly detect pedestrians moving across it. Or, if a car-detection swarm finds a car, positive pheromone can be deposited to attract a pedestrian-detection swarm and detect people exiting or entering the car. The spatially-distributed pheromones can be reset every time a new image is acquired, or a decay constant can be used.

[0085] In order for the Interest Map 304 to properly modulate the attention of the swarm, a running sorted list must be kept for the global best position (i.e., gbest) and for each particle's best position (i.e., pbest), along with the associated F_Avalues. As the Interest Map 304 is updated at each iteration of the swarm, F_Ais updated for each entry in the list and different previously visited positions may become the current gbest and pbest values for each particle. In this way, the swarm dynamics are modified by the Interest Map 304 in such a way as to focus attention on more salient regions 308. Once particles get close enough to an object for F_Cto dominate, then the swarm will converge on that region until the classifier decision conditions are met and the object is recognized or the maximum number of iterations is exceeded.

[0086] In other words, the new objective function allows the particles in the swarm to use both the previous classifier response as well as a new difference between the positive and negative pheromone values. A weighted combination of these two values determines the new objective function value. The best particle in the swarm is then the particle with the highest value using the new objective function criteria. The velocity and position update equations remain the same. What actually changes is the particle in the swarm that has the best objective function value. Once the best particle in the swarm in an iteration is ascertained, all particles in the swarm move a random distance towards the best particle. For example, assume that the swarm particles in earlier iterations had deposited a lot of negative pheromone in a certain region of the image and a false alarm is detected in the current frame (i.e., high objective function value using the old objective function criteria). However, the new objective function criteria would diminish the objective function value (since it is combined with the pheromone difference score) and therefore prevent the detection of the false alarm.

[0087] (4.2.3) Object Map

[0088] The Object Map 306 serves to keep track of whether an object has been detected at each spatial location in the input image 104 by marking a rectangular object region 310 corresponding to the recognized size of the object. The Object Map 306 is useful for preventing unnecessary classifier evaluations for particles that “land” in regions where objects have already been detected. It is also useful for initializing the particle positions where objects have not yet been detected and in regions more likely to contain objects based on previous detection results. By avoiding the object regions 310, all of the particles can be initialized in regions where objects have not yet been detected.

[0089] (4.2.4) Local Swarms

[0090] A component of the new framework is the use of “local” and “global” swarms working together to recognize and track objects. A global swarm which searches the entire image (but modulated by the cognitive maps) is used to first detect an object which enters the field of view. A local swarm consisting of only a few particles is then initialized in the next image in a small area centered on the previously detected position of the object. The local swarm is used to define restricted areas that global swarms do not search. If the object has not moved substantially, it can be tracked using the local swarm with much fewer classifier evaluations. A tracker, such as a Kalman tracker, can also be used to predict the position of the object in the next image so that the local swarm can be initialized at the predicted position. A flow chart for this process is shown in FIG. 4.

[0091] Exemplary experimental results for global swarm acquisition and local swarm recognition and tracking of pedestrians are shown in FIG. 5. First, a global swarm 500 is initialized to search for objects 502 in an input image 104. Next, a local swarm 504 is assigned to the identified objects 502. In another image, the local swarms 504 attempt to find their corresponding assigned objects 502. Local swarms 504 that lost their objects are deleted. The global swarm 500 then searches for new objects 502, with a local swarm 504 thereafter assigned to the new objects 502.

[0092] (4.2.5) Analysis Window Diversity

[0093] A true object should be recognized by the classifier even if the analysis window varies in size slightly. In addition, a mirror image of the object should also be recognized. Therefore, the false alarm rate can be improved by performing a mini operation on classifier confidence values obtained for different sizes and mirror images of the analysis window and using the result as the final classifier confidence value. Exemplary experimental results for the attention-based cognitive swarm framework are shown in FIG. 6. As shown in FIG. 6, the analysis window 114 is formed to represent objects 502 in the input image 104.

[0094] (4.2.6) Object Recognition System Components

[0095] A block diagram depicting the components of object recognition system of the present invention is provided in FIG. 7. The object recognition system 700 comprises an input 702 for receiving an input image. Note that the input 702 may include multiple “ports.” Typically, input is received from at least one sensor, non-limiting examples of which include video image sensors. An output 704 is connected with the processor for providing information regarding the presence and/or identity of object(s) in the scene to other systems in order that a network of computer systems may serve as an image processing system. Output may also be provided to other devices or other programs; e.g., to other software modules, for use therein. The input 702 and the output 704 are both coupled with a processor 706, which may be a general-purpose computer processor or a specialized processor designed specifically for use with the present invention. The processor 706 is coupled with a memory 708 to permit storage of data and software to be manipulated by commands to the processor.

[0096] (4.2.7) Computer Program Product

[0097] An illustrative diagram of a computer program product embodying the present invention is depicted in FIG. 8. The computer program product 800 is depicted as an optical disk such as a CD or DVD. However, as mentioned previously, the computer program product generally represents computer readable code stored on any compatible computer readable medium.

Claims

What is claimed is:

1. An object recognition system incorporating swarming domain classifiers, comprising:

at least one cognitive map stored in memory having a one-to-one relationship with an input image domain, the cognitive map being capable of recording information in the memory that software agents utilize to focus a cooperative swarm's attention on regions in the domain most likely to contain objects of interest;

a plurality of software agents executing on a processor configured to operate as a cooperative swarm to classify an object in the domain, where each agent is a complete classifier and is assigned an initial velocity vector to explore a solution space for object solutions, where each agent is configured to perform at least one iteration as influenced by the recorded information of the cognitive map, the iteration being a search in the solution space for a potential solution optima where each agent keeps track of its coordinates in multi-dimensional 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 location 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 and classify the object when a classification level exceeds a preset threshold;

the cognitive map is a map selected from a group consisting of a ground surface map, an interest map, an object map, and a saliency map; and

the interest map stored in the memory is configured to run on the processor and maintain a sorted list for gbest and pbest, along with the associated F_Avalues, where F_Ais an objective function and is calculated according to the following:

F_A=μ(Q₊−Q₋)+(1−μ)F_C,

where Q₊ denotes an attracting pheromone and Q₋ denotes a repelling pheromone, and where m is a nonnegative weighting factor, and F_C is an object classifier confidence value; and

the interest map is updated in the memory at each iteration of the swarm and F_A is updated for each entry in the sorted list, whereby the swarm is modified by the interest map in such a way as to focus attention on regions of increased saliency.

2. An object recognition system as set forth in claim 1, wherein using the ground surface map, the system is configured to:

store expected object height in pixels at each image location;

constrain an analysis window to an appropriate size at each domain location; and

implement space-variant initialization of the cooperative swarm.

3. An object recognition system as set forth in claim 2, wherein using the ground surface map, the system is further configured to calculate a vertical coordinate of y of an imaged object using a pinhole imaging model, the vertical coordinate of y is calculated according to the following:

y = - f \tan α - \frac{f (z - z_{c}) (\tan^{2} α + 1)}{Y - (z - z_{c}) \tan α},

where z is the height of the object, z_cis the camera height, Y is the distance of the object from the camera, α is the camera tilt angle, and ƒ is the camera focal length.

4. An object recognition system as set forth in claim 3, wherein the interest map is configured to store swarm attracting/repelling pheromones at each domain location, with attracting pheromones having positive values and being stored to attract swarms to high saliency regions and to regions more likely to contain objects based on previous detection results or external inputs, and with repelling pheromones having negative values and being stored to repel swarms away from regions that do not contain objects or which have already been explored, thereby preventing clustering of agents on low confidence regions.

5. An object recognition system as set forth in claim 4, wherein using the object map, the system is configured to perform at least one of the operations of:

storing information at each domain location on previously detected objects;

preventing unnecessary classifier evaluations;

initializing swarms only in regions where objects have not yet been detected;

initializing swarms in regions more likely to contain objects based on previous detection results; and recognizing object groups and behaviors.

6. An object recognition system as set forth in claim 5, wherein the system is further configured to track an object in multiple input images by performing operations of:

receiving a first current input image;

initializing a global swarm to search for objects within the input image;

assigning local swarms to objects identified by the global swarm;

receiving a next input image, where the next input image is deemed the current input image and a previous current input image is deemed the previous input image;

initializing the local swarms to search for and identify objects in the current input image;

deleting local swarms that lost their identified objects between the current and previous input images;

initializing the global swarm to search for new objects in the current input image;

assigning local swarms to new objects identified in the current input image; and

repeating the acts of receiving a next input image, initializing, deleting, initializing, and assigning for subsequent next images.

7. An object recognition system as set forth in claim 1, wherein using the ground surface map, the system is further configured to calculate a vertical coordinate of y of an imaged object using a pinhole imaging model, the vertical coordinate of y is calculated according to the following:

y = - f \tan α - \frac{f (z - z_{c}) (\tan^{2} α + 1)}{Y - (z - z_{c}) \tan α},

where z is the height of the object, z_cis the camera height, Y is the distance of the object from the camera, α is the camera tilt angle, and ƒ is the camera focal length.

8. An object recognition system as set forth in claim 1, wherein the interest map is configured to store swarm attracting/repelling pheromones at each domain location, with attracting pheromones having positive values and being stored to attract swarms to high saliency regions and to regions more likely to contain objects based on previous detection results or external inputs, and with repelling pheromones having negative values and being stored to repel swarms away from regions that do not contain objects or which have already been explored, thereby preventing clustering of agents on low confidence regions.

9. An object recognition system as set forth in claim 1, wherein using the object map, the system is configured to perform at least one of the operations of:

storing information at each domain location on previously detected objects;

preventing unnecessary classifier evaluations;

initializing swarms only in regions where objects have not yet been detected;

initializing swarms in regions more likely to contain objects based on previous detection results; and

recognizing object groups and behaviors.

10. An object recognition system as set forth in claim 1, wherein the system is further configured to track an object in multiple input images by performing operations of: