Abstract:
A tracking system having a video detector for associating observations of blobs and objects and deriving objects&#39; or blobs&#39; paths. Hypotheses may be computed by the system for merging, splitting and reacquisition of the observations. There may be objects tracked among the observations, and best paths selected as trajectories of corresponding objects. The observations may be placed in a sliding window containing a series of observations inferred from a collection of frames for improving the accuracy of the tracking (or data association). The processed observations and data may be represented graphically.

Description:
[0001]    The present application claims the benefit of U.S. Provisional Application No. 60/804,761, filed Jun. 14, 2006. U.S. Provisional Application No. 60/804,761, filed Jun. 14, 2006, is hereby incorporated by reference. 
         [0002]    The present application is a continuation-in-part application of U.S. patent application Ser. No. 11/548,185, filed Oct. 10, 2006. U.S. patent application Ser. No. 11/548,185, filed Oct. 10, 2006, is hereby incorporated by reference. 
         [0003]    The present application is a continuation-in-part application of U.S. patent application Ser. No. 11/562,266, filed Nov. 21, 2006. U.S. patent application Ser. No. 11/562,266, filed Nov. 21, 2006, is hereby incorporated by reference. 
     
    
     BACKGROUND 
       [0004]    The present invention pertains to tracking and data association particularly to tracking and associating targets including those that may be temporarily occluded, merged, stationary, and the like. More particularly, the invention pertains to implementing techniques in tracking and data association. 
       SUMMARY 
       [0005]    The invention is a tracking system which that incorporates several hypotheses. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWING 
         [0006]      FIG. 1  is a diagram of detected observations versus time; 
           [0007]      FIGS. 2   a  and  2   b  show additional graph information for merge and split hypotheses, respectively; 
           [0008]      FIGS. 3   a ,  3   b  and  3   c  are pictures showing tracking results for merge, slit and reacquisition operations, respectively; 
           [0009]      FIGS. 4   a  and  4   b  show a tracking of targets using ground plane information; 
           [0010]      FIG. 5  is a diagram of an example tracking system; 
           [0011]      FIG. 6  is a diagram of a multiple hypotheses module of the tracking system; 
           [0012]      FIG. 7  is a diagram of a moving window used in the tracking system; and 
           [0013]      FIG. 8  is a diagram of example paths of tracked objects. 
       
    
    
     DESCRIPTION 
       [0014]    Multiple target tracking and association is a key component in visual surveillance. Tracking may provide a spatio-temporal description of detected moving regions in the scene. Such low-level information may be critical for recognition of human actions in video surveillance. In the present visual tracking approach, the observations are the detected moving blobs, or detected stationary or moving objects (e.g., faces, people, vehicles . . . ). These observations may be referred to herein as blobs. An issue related to visual tracking may come from incomplete observations, occlusions and noisy foreground segmentation. The assumption that one detected blob corresponds to one moving object is not always true. Several factors may be needed to be considered for a good tracking algorithm as follows. A single moving object (e.g., one person) may be detected as multiple moving blobs, and thus the tracking algorithm should “merge” the detected blobs. Similarly, one detected blob may be composed of multiple moving objects; in this case, the tracking algorithm should “split” and segment the detected blob. A detected blob could be a false alarm due to erroneous motion or object detection. Here, the tracking algorithm should filter these observations. In the presence of static or dynamic occlusions of the moving objects in the scene, one may often observe a partial occlusion where the appearance information gets affected, or have a total occlusion where no observation on the object is available. The lack of observation may also correspond to a stop-and-go motion since the observation may come from motion detection. Also, the number of objects in the scene may vary as new objects enter and leave the field-of-view of a camera, or detection mechanism or module. 
         [0015]    A graph representing observations over time may be adopted. A multiple-target tracking approach may be formulated as finding the best multiple paths in the graph. To use the visual observations from an image sequence, both motion and appearance models may be introduced. Given these models, one may associate a weight to each edge defined between two nodes of the graph. Due to noisy foreground segmentation, one target may report foreground regions, and one foreground region may correspond to multiple targets. To deal with the various issues, several types of operations, including merge, split and reacquisition (by appearance), may be introduced. If a prediction of one track at time t+1 has enough spatial overlapping with more than one observation at time t+1, a merge operation may generate a new observation. When an observation at time t+1 is the best child of more than one track, this may incur a split operation, which splits a node into several new observations. A reacquisition operation may be used to handle misdetection. New hypotheses may carry a hypothesis proposed by merge, split or reacquisition operation. A final decision about tracking may be made by considering all of the observations in the graph. 
         [0016]    The present multiple-target tracking algorithm may be widely used in a visual surveillance application. An input for the tracking algorithm may include the foreground regions and original image sequences, or detected objects in the image. A foreground region usually can be provided by a motion detection procedure. An observation graph may be constructed, which contains all of the observations within a time period. An edge between nodes may be weighted by a joint motion and appearance likelihood. The motion likelihood may be computed with a Kalman Filter. The appearance likelihood may be the KL distance between two non-parametric appearance models. Next, one may perform an optimal path selection in the graph to find the best temporal and spatial trajectories of the targets. 
         [0017]    Multiple-target tracking may be considered as a maximum a posterior (MAP) problem. To make full use of the visual observations from the image sequence, both motion and appearance likelihood may be introduced. The graph representation of all observations over time may be adopted. A final decision of the trajectories of the targets may be delayed until enough observation is obtained. 
         [0018]    The observations may be expanded with hypotheses added by merge, split and reacquisition operations, which are designed to deal with noisy foreground segmentation due to occlusion, foreground fragment and missing detection. These added hypotheses may be validated during a MAP estimate. A MAP formulation of multiple target tracking approach and the motion and appearance likelihoods may be noted. 
         [0019]    In a multiple-target tracking approach, an objective is to track multiple target trajectories over time given noisy measurements provided by a motion detection algorithm. The targets&#39; positions and velocities may be automatically initialized and should not require operator interaction, or could be provided by the operator. The detector may usually provide image blobs which contain the estimated location, size and the appearance information as well. Within any arbitrary time span [1, T], there may be K unknown number of targets in the monitored scene. y t ={y t   i :i=1, . . . , n t } may denote the observations at time t t  and Y=∪ tε{1, . . . , T} y t  may be the set of all the observations within the duration [1, T]. The multiple target tracking can be formulated as finding the set of K best paths {τ 1 , τ 2  . . . , τ K } in the temporal and spatial space, where K is unknown. Let τ k  denote a track by the set of its observations: τ k ={τ k (1), τ k (2), . . . , τ k (T)} where τ k (t)εy t  represents the observation of track τ k  at time t. 
         [0020]    A graph representation G=&lt;V,E&gt; of all measurements within time [1, T] may be utilized. The graph is a directed graph that consists of a set of nodes V={y t   k :t=1, . . . T, k=1, . . . , K}. Considering missing detections, one special measurement of y t   0  may represent the null measurement at time t. A directed edge, (y t     1     i , y t     2     j )εE,t 1 &lt;t 2 , may be defined between two nodes in consecutive frames based on proximity and similarity of the corresponding detected blobs. In each time instant, there may be m t  observations. The shaded node  12 , which does not belong to any track, may represent a false alarm. The white node  13  may represent a missing observation, as inferred by the tracking. 
         [0021]      FIG. 2   a  shows a hypothesis added by a merge operation. Node  15  is prediction on the left at t+1. Node  16  is a new node added to the graph on the right at t+1.  FIG. 2   b  shows a hypothesis added by a split operation. Best edges  17  are on the left from a measurement. New nodes  18  are added to the graph on the right. 
         [0022]    The multiple target tracking may be formulated as a maximum a posterior (MAP) problem, given the observations over time, to find K best paths τ* 1, . . . , K  through the graph of measurements in  FIG. 1  as 
         [0000]      τ* 1, . . . , K =arg max( P (τ* 1, . . . , K   |Y )).  (1) 
         [0000]    The posterior of the K best paths may be represented as the observation likelihood of the K paths and the prior of the K paths. A prior distribution model of P(τ k :k=1, . . . , K) may be represented as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       P 
                        
                       
                         ( 
                         
                           τ 
                           
                             1 
                             , 
                             … 
                              
                             
                                 
                             
                             , 
                             K 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∏ 
                         
                           i 
                           = 
                           1 
                         
                         T 
                       
                        
                       
                           
                       
                        
                       
                         
                           
                             
                               p 
                               d 
                               
                                 T 
                                 m 
                                 i 
                               
                             
                              
                             
                               ( 
                               
                                 1 
                                 - 
                                 
                                   p 
                                   d 
                                 
                               
                               ) 
                             
                           
                           
                             K 
                             - 
                             
                               T 
                               m 
                               i 
                             
                           
                         
                          
                         
                           p 
                            
                           
                             ( 
                             
                               F 
                               m 
                               i 
                             
                             ) 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where T m   i  is the number of measurements associated to the tracks and F m   i  is the number of measurements not associated to the tracks. p(F m   i ) may be a Poisson distribution of F m   i , and p d  denotes the detection rate which may be estimated from the prior knowledge of the detection procedure. By introducing this prior information, the posterior of the unknown K paths may be represented as 
         [0000]      P(τ 1, . . . , K |Y)∝P(Y|τ 1 . . . K )P(τ 1, . . . , K ).  (2) 
         [0000]    The K paths multiple target tracking may be extended to a MAP estimate as 
         [0000]      τ* 1, . . . K =arg max( P ( Y|τ   1 . . . , K ) P (τ 1, . . . , K )).  (3) 
         [0023]    Since the measurements are image blobs, besides position and dimension (width and height) information, an appearance model may be considered in the tracking approach. To make full use of the visual cues of the observations, both motion and appearance may be considered as likelihood measures. By assuming each target is moving independently, the joint likelihood of the K paths over time [1, T] may be represented as 
         [0000]    
       
         
           
             
               
                 
                   
                     P 
                      
                     
                       ( 
                       
                         Y 
                         | 
                         
                           τ 
                           
                             1 
                             , 
                             … 
                              
                             
                                 
                             
                             , 
                             K 
                           
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∏ 
                       
                         k 
                         = 
                         1 
                       
                       K 
                     
                      
                     
                         
                     
                      
                     
                       
                         
                           P 
                           motion 
                         
                          
                         
                           ( 
                           
                             
                               
                                 τ 
                                 k 
                               
                                
                               
                                 ( 
                                 1 
                                 ) 
                               
                             
                             , 
                             … 
                              
                             
                                 
                             
                             , 
                             
                               
                                 τ 
                                 k 
                               
                                
                               
                                 ( 
                                 T 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                        
                       
                         
                           
                             P 
                             color 
                           
                            
                           
                             ( 
                             
                               
                                 
                                   τ 
                                   k 
                                 
                                  
                                 
                                   ( 
                                   1 
                                   ) 
                                 
                               
                               , 
                               … 
                                
                               
                                   
                               
                               , 
                               
                                 
                                   τ 
                                   k 
                                 
                                  
                                 
                                   ( 
                                   T 
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0000]    A joint probability may be defined by a product of the appearance and motion probabilities. This probability maximization approach may be inferred by using a Viterbi™ algorithm (see Kang et al., “Continuous tracking within and across camera streams”, IEEE, Conference on CVPR 2003, Madison, Wis., which is hereby incorporated by reference). Other algorithms may be utilized. 
         [0024]    A constant velocity motion model in a 2D image plane and 3D ground plane may be considered. x t   k , may denote the state vector of the target k at time t to be [l x , l y , w, h, i x , i y , l gx , l gy ] (position, width, height and velocity in 2D image, position on the ground plane). One may consider a linear kinematic model, 
         [0000]        x   t+1   k   =A   k   x   t   k   +w   t   k ,  (5) 
         [0000]    where x t   k  is the state vector for target k at time t. w t   k  may be assumed to have a normal probability distribution, w k ˜N(0, Q k ). A k  may be a transition matrix. A constant velocity motion model may be used. The observation y t   k =[u x ,u y ,w,h,u gx ,u gy ] may contain a measurement of a target position and size in a 2D image plane and position on a 3D ground plane. Since observations often contain false alarms, the observation model may be represented as 
         [0000]    
       
         
           
             
               
                 
                   
                     y 
                     t 
                     k 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 H 
                                 k 
                               
                                
                               
                                 x 
                                 t 
                                 k 
                               
                             
                             + 
                             
                               v 
                               t 
                               k 
                             
                           
                         
                         
                           
                             if 
                              
                             
                                 
                             
                              
                             from 
                              
                             
                                 
                             
                              
                             target 
                           
                         
                       
                       
                         
                           
                             δ 
                             t 
                           
                         
                         
                           
                             
                               false 
                                
                               
                                   
                               
                                
                               alarm 
                             
                             , 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where y t   k  represents the measurement which may arise either from a false alarm or from the target. δ t  may be the false alarm rate at time t. The H k  matrix may serve also to take into account the ground plane as one could use it to map 2D observations to 3D measurements. A measurement may be provided as a linear model of a current state if it is from a target otherwise is modeled as a false alarm δ t , which is assumed to be a uniform distribution. 
         [0025]    {circumflex over (τ)} k (t i ) and {circumflex over (P)} t (τ k ) may denote a posterior state estimate and a posterior estimate of the error covariance matrix τ k  at time t. Along a track τ k , the motion likelihood of one edge τ k (t 1 ), τ k (t 2 ))εE, t 1 &lt;t 2 , may be represented as P motion (τ k (t 2 )|{circumflex over (τ)} k (t 1 )). Given the transition and observation model in a Kalman filter, the motion likelihood may then be written as 
         [0000]    
       
         
           
             
               
                 
                   
                     P 
                     motion 
                   
                   = 
                   
                     ( 
                     
                       
                         
                           
                             
                               τ 
                               k 
                             
                              
                             
                               ( 
                               
                                 t 
                                 2 
                               
                               ) 
                             
                           
                           | 
                           
                             
                               
                                 τ 
                                 ^ 
                               
                               k 
                             
                              
                             
                               ( 
                               
                                 t 
                                 1 
                               
                               ) 
                             
                           
                         
                         = 
                         
                           
                             1 
                             
                               
                                 
                                   ( 
                                   
                                     2 
                                      
                                     
                                         
                                     
                                      
                                     π 
                                   
                                   ) 
                                 
                                 
                                   3 
                                   / 
                                   2 
                                 
                               
                                
                               
                                 det 
                                 ( 
                                 
                                   
                                     
                                       P 
                                       ^ 
                                     
                                     
                                       t 
                                       2 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       τ 
                                       k 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                            
                           
                             exp 
                             ( 
                             
                               
                                 
                                   - 
                                   
                                      
                                     T 
                                   
                                 
                                  
                                 
                                   
                                     
                                       P 
                                       ~ 
                                     
                                     
                                       t 
                                       2 
                                     
                                     
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       τ 
                                       k 
                                     
                                     ) 
                                   
                                 
                                  
                                  
                               
                               2 
                             
                             ) 
                           
                         
                       
                       , 
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where e=y t   k −HA{circumflex over (τ)} k (t 1 ) and {tilde over (P)} t     2   (τ k ) may be computed recursively by a Kalman filter as {tilde over (P)} t     2   (τ k )=H(A{circumflex over (P)} t     2     −1 (τ k )A T +Q)H T +R. {circumflex over (P)} t     2     −1 (τ k ) is the state posterior estimate which can be computed from the Kalman filter. 
         [0026]    The tracking of each region may rely on the kinematic model, described herein, as well as on an appearance model. The appearance of each detected region may be modeled using a non-parametric histogram. All RGB bins may be concatenated to form a one dimension histogram. The appearance likelihood between two image blobs, τ k (t 1 ), τ k (t 2 ))εE, t 1 &lt;t 2 , in track k, may be measured using a symmetric Kullback-Leibler (KL) divergence defined in the following. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       P 
                       color 
                     
                     ( 
                     
                       
                         
                           τ 
                           k 
                         
                          
                         
                           ( 
                           
                             t 
                             2 
                           
                           ) 
                         
                       
                       | 
                       
                         
                           
                             τ 
                             ^ 
                           
                           k 
                         
                          
                         
                           ( 
                           
                             t 
                             1 
                           
                           ) 
                         
                       
                     
                     ) 
                   
                   = 
                   
                     
                       1 
                       2 
                     
                      
                     
                       
                         ∑ 
                         
                           
                             c 
                             = 
                             r 
                           
                           , 
                           g 
                           , 
                           b 
                         
                         
                             
                         
                       
                        
                       
                         
                           ( 
                           
                             
                               
                                 P 
                                 i 
                               
                                
                               
                                 ( 
                                 c 
                                 ) 
                               
                             
                             - 
                             
                               
                                 P 
                                 j 
                               
                                
                               
                                 ( 
                                 c 
                                 ) 
                               
                             
                           
                           ) 
                         
                          
                         
                             
                         
                          
                         
                           log 
                            
                           
                             ( 
                             
                               
                                 
                                   P 
                                   i 
                                 
                                  
                                 
                                   ( 
                                   c 
                                   ) 
                                 
                               
                               
                                 
                                   P 
                                   j 
                                 
                                  
                                 
                                   ( 
                                   c 
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0000]    other appearance models may be used by the present framework also. 
         [0027]    Given the motion and appearance models, one may associate a weight to each edge defined between two nodes of the graph. This weight may combine the appearance and motion likelihood models presented herein. 
         [0028]    In equations (7) and (9), one may assume the state of the target at time t as determined by the previous state at time t−1 and the observation at time t as a function of the state at time t alone, i.e., a Markov condition. Also one may assume the motion and appearance of different targets is independent. Thus, the joint likelihood of K paths in equation (5) may be factorized as in the following. 
         [0000]    
       
         
           
             
               
                 
                   
                     P 
                      
                     
                       ( 
                       
                         Y 
                         | 
                         
                           τ 
                           
                             1 
                             , 
                             
                               … 
                                
                               
                                   
                               
                                
                               K 
                             
                           
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       ∏ 
                       
                         k 
                         = 
                         1 
                       
                       K 
                     
                      
                     
                         
                     
                      
                     
                       
                         ∏ 
                         
                           
                             ( 
                             
                               
                                 t 
                                 1 
                               
                               , 
                               
                                 t 
                                 2 
                               
                             
                             ) 
                           
                           ∈ 
                           
                             τ 
                             k 
                           
                         
                         T 
                       
                        
                       
                           
                       
                        
                       
                         
                           
                             P 
                             motion 
                           
                            
                           
                             ( 
                             
                               
                                 
                                   τ 
                                   k 
                                 
                                  
                                 
                                   ( 
                                   
                                     t 
                                     1 
                                   
                                   ) 
                                 
                               
                               | 
                               
                                 
                                   
                                     τ 
                                     ^ 
                                   
                                   k 
                                 
                                  
                                 
                                   ( 
                                   
                                     t 
                                     2 
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                          
                         
                           
                             P 
                             color 
                           
                            
                           
                             ( 
                             
                               
                                 
                                   τ 
                                   k 
                                 
                                  
                                 
                                   ( 
                                   
                                     t 
                                     1 
                                   
                                   ) 
                                 
                               
                               | 
                               
                                 
                                   
                                     τ 
                                     ^ 
                                   
                                   k 
                                 
                                  
                                 
                                   ( 
                                   
                                     t 
                                     2 
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
         [0029]    An augmented graph representation for a multiple hypothesis tracker may be provided. Many multiple target tracking algorithms assume that no two paths pass through the same observation. This assumption appears reasonable when considering punctual observations. However, this assumption may often be violated in the context of a visual tracking situation, where the targets are not regarded as points and the inputs to the tracking algorithm are usually image blobs. A framework may be presented to handle split and merge behavior in estimating the best paths. 
         [0030]    Merge and split hypotheses may be considered. Merge and split behaviors may correspond to a recursive association of new observations, given estimated trajectories. At a given time instant t, one may obtain K best paths which are denoted as [τ 1   t , . . . , τ K   t ]. Using the estimated tracks, one may evaluate how the m t+1  observations {y t+1   i :i=1, . . . , m t+1 } at time t+1 fit the estimated tracks which end at time t. The spatial overlap between an estimate state at instant time t and a new observation may be considered as a primary cue. Several cases may be noted. First, if a prediction of  τ   k   t (t+1) has sufficient spatial overlap with more than one observation at time t+1, this may trigger a “merge” operation which merges the observations at time t+1 into one new observation. This new observation carrying the merge hypothesis may be added to the graph of  FIG. 1  but for illustrative purposes is shown separately in  FIG. 2   a.    
         [0031]    Second, if the predicted positions and shapes of more than one track spatially overlap within one observation y* t+1  at time t+1, then the set of candidate tracks may be κ,|κ|&gt;1. The “split” operation may proceed as in the following. For each track τ k   t  in κ whose prediction has sufficient overlap with y* t+1 , one may change the predicted size and location at time t+1 to find the best appearance score s k =P color (  τ   k   t (t+1), y* t+1 ); provide a new observation mode for the track with the largest s k  which may be added to the graph of  FIG. 1 ; and reduce the confidence of the area occupied by the newly added node and recompute the score s k  for each track left in κ. One may iterate this approach until all of the candidate tracks in κ that overlapped with the observation y* t+1  are tested. Even though the new observation carrying the merge hypothesis may be added to the graph of  FIG. 1 , for illustrative purposes, it is shown separately in  FIG. 2   b.    
         [0032]    A reacquisition hypothesis may be considered. Noisy segmentation of foreground regions often provides incomplete observations not suitable for a good estimation of the position of the tracked objects. Indeed, moving objects are often fragmented, several objects may be merged into a single blob, and thus regions are not necessarily detected in a case of stop-and-go motion. 
         [0033]    Additional information may be incorporated from the images for improving appearance-based tracking. Since the appearance histogram of each target has been maintained at each time t, the reacquisition operation may be introduced to keep track of the appearance distribution when the blob does not provide good enough input. The reacquisition approach may be regarded as a mode-seeking approach and be successfully applied to a tag-to-track situation. Often the central module of the tracker may be doing reacquisition iterations to find the most probable target position in the current frame according to the previous target appearance histogram. In the present multiple target tracking situation, if a reliable track is not associated with a good observation at time t, due to a fragmented detection, non-detection or a large mismatch in size, one may instantiate a reacquisition algorithm to propose the most probable target position given the appearance of the track. One may note that the histogram used by the reacquisition algorithm may be established using past observations along the path (within a sliding window), instead of using only the latest one. Using a predicted position from the reacquisition, a new observation may be added to the graph. The final decision may be made by considering all of the observations in the graph. To prevent reacquisition tracking from tracking a target after it leaves the field of view, the reacquisition hypothesis may be considered only for trajectories where the ratio of the real node to the total number of observations along the track is larger than a certain threshold. 
         [0034]    In use of the present system, a sliding temporal window of 45 frames may be used to implement the present algorithm as an online algorithm. The graph may contain observations between time t and t+45. When new observations are added to the graph, the observations older than t may be removed from the graph. 
         [0035]    The present tracking algorithm may be tested and used on both indoor and outdoor data sets. The data considered may be collected inside of a laboratory, and around parking lots and other facilities. In the considered data set, a large number of partial or complete occlusions between targets (pedestrians and vehicles) may be observed. In conducted tests, the input considered for the tracking algorithm may include the foreground regions and the original image sequence. One may test the accuracy of the present tracking algorithm and compare it to the classical approaches without the added merge, split and reacquisition hypotheses. 
         [0036]      FIGS. 3   a - 3   c  show data sets with tracking results overlaid and the foreground detected. Due to noisy foreground segmentation, the input foreground for one target could have multiple fragment regions, as shown in  FIG. 3   a . This Figure shows a tracking result with a merge operation when the foreground regions fragment. 
         [0037]    The case where two or more moving objects are very close to each other, one may have a single moving blob for all of the moving objects, as shown in  FIG. 3   b . This Figure shows a tracking result with a split operation when the foreground regions merge. 
         [0038]    In the case where the targets merge into the background is shown in  FIG. 3   c . This Figure shows a tracking result with a reacquisition operation when a missing detection happens. 
         [0039]    Given the homography between the ground plane and the image plane, the targets may be tracked on the 3D ground plane, as shown in  FIGS. 4   a  and  4   b . These Figures show tracking targets using ground plane information. In  FIG. 4   a , estimated trajectories are plotted in the 2D image. In  FIG. 4   b , the positions of moving people in the scene are plotted on the ground plane. 
         [0040]    The present approach may be used for multiple targets tracking in video surveillance. If the application scenarios are partitioned into easy, medium and difficult cases, many tracking algorithms may handle the easy cases rather well. However, for the medium and difficult cases, multiple targets could be merged into one blob especially during the partial occlusion and one target could be split into several blobs due to noisy background subtraction. Also, missed detections may happen often in the presence of stop-and-go motion, or when one is unable to distinguish foreground from background regions without adjusting the detection parameters to each sequence considered. 
         [0041]    The mechanism introduced here is based on multiple hypotheses which expand the solution space. The present formulation of multiple-target tracking as a maximum posterior (MAP) and the extended set of hypotheses by considering merge, split and reacquisition operations is very robust. It may deal with noisy foreground segmentation due to occlusion, foreground fragments and missing detections. It shows good performance on various data sets. 
         [0042]      FIG. 5  is a diagram of a multiple tracking system  10 . A detection module  51  may provide video images of a scene with blobs detected or objects to be tracked. The detection may be based on images of blobs or objects or on motion of these blobs or objects. An output of the detection module  51  may go to a multiple-object tracking mechanism  52 . The image data from the detection module  51  may proceed on to a data representation mechanism or module  53  that represents the data in the form of a graph as illustrated in  FIGS. 1 ,  2   a  and  2   b . The data representation may proceed on to a sliding window module  54 , which may provide a delay or other shift in time to a frame of data being processed. The results of the tracking module  54  may go to a graph updating module  55  which provides updates of tracking to the graph maintained by module  53 . This updating may be incremented in terms of frame of blob or object tracking. Results of the tracking module  53  may go to an algorithm module  56  for processing the results according to the various hypotheses of merge, split and reacquisition. The algorithm may be that of the Viterbi™ algorithm noted herein, or another appropriate algorithm. The tracks module  57  may receive an output from the algorithm module which results in tracks determined from the video information of the detection module  51 . 
         [0043]      FIG. 6  is a diagram revealing further detail of the operation of a portion of system  10 . Module  59  may provide observations or blobs to a multiple hypothesis module  58 . Blob, merge, split and reacquisition operation data may be provided to algorithm  56  from module  58 . 
         [0044]      FIG. 7  shows a sliding window approach  20 . The approach may provide a series of frames. The frames may contain occurrences of contained information according to time. Frame  63  at time t may be the one being processed at that time. The frames prior to the frame  63  may include frame  61  which goes back to the beginning of the series of sliding window  20 , and include frame  65  which goes forward in time, along with frames  62  and  64  between the frames  61  and  65 . There may be 22 frames prior to frame  63  in time, and 22 frames after frame  63  in time. Frames  62  and  64  are merely representative of the frames between frames  61  and  63  and frames  61  and  65 , respectively. Frame  61 , the first frame of the sliding window  30  may be at time t−w. The “−w” may represent the time of the 22 frames prior to the “present” frame  63  at time t. Frame  65 , the last frame of the sliding window  20 , may be at t+w. The“+w” may represent the time of the 22 frames after the “present” frame  63  at time t. The total number of frames of the sliding window approach  20  is 2*w+1. 
         [0045]      FIG. 8  is a diagram of tracks T 1 , T 2 , T 3 , and so on, of objects. The tracks  71 ,  72 , and  73  of objects  66 ,  67  and  68 , respectively, relative to the paths may be noted. The sliding window  20  may have 45 frames; although for clarity, just frames  1 - 3  and  42 - 45  are shown. The direction and the numbering order of the frames could in some circumstances be arbitrarily selected. It may be noted that objects  66  and  67  appear to start out on tracks that follow an apparently straight-line like path. However, the present tracking mechanism may note a cross-over of paths by objects  66  and  67 , which may be detected through the operation of one or more hypotheses of merge, split and reacquisition, on the data in one or more of the 45 frames of window  20 . On a display screen connected to a processor of the system  10 , one may mouse click on an object or blob of interest to individually track its movement. 
         [0046]    In the present specification, some of the matter may be of a hypothetical or prophetic nature although stated in another manner or tense. 
         [0047]    Although the invention has been described with respect to at least one illustrative example, many variations and modifications will become apparent to those skilled in the art upon reading the present specification. It is therefore the intention that the appended claims be interpreted as broadly as possible in view of the prior art to include all such variations and modifications.