Abstract:
The invention discloses a new multi-target tracking method for video surveillance. The main steps include obtaining target state from previous frame, detecting target in current frame (observation), computing cost matrix between all existing targets and observations and solving the assignment problem by EMD (earth movers distance) algorithm. As have obtained correspondence between all existing objects and observations, then track them separately. The proposed method includes 4 modules: target state maintaining module, used to save all target&#39;s state in previous frame, object detection module, used to detect all objects in current frame, EMD algorithm module, using EMD algorithm to solve correspondence problem for multi-target tracking, object processing module, which using the result of EMD algorithm to process all existing and new objects. Experiments demonstrated the effectiveness of this method, which improves the accuracy for multi-target tracking.

Description:
TECHNICAL FIELD 
       [0001]    In this invention, a multi-target tracking method for video surveillance is proposed, which belongs to smart video surveillance domain. 
       BACKGROUND 
       [0002]    Multi-target tracking is one of most important step for smart video surveillance, for dense targets, it&#39;s still a challenge. The key point of multi-target tracking is data association, existing solutions include local nearest neighbor association, global nearest neighbor association, multi-hypothesis tracking, and joint probability data association, which are widely used in radar and sonar target tracking. 
         [0003]    As the complexity of information, all existing methods are not able to handle multi-target tracking problem effectively in computer vision domain. 
       SUMMARY 
       [0004]    In order to track multi-target accurately for smart video surveillance, a new multi-target tracking algorithm is proposed. 
         [0005]    The method comprises the following steps: 
         [0006]    Obtain all existing target&#39;s state in previous frame; 
         [0007]    Detect all objects in current frame and get their observation value; 
         [0008]    Construct cost matrix from target sate and observation, solve it using EMD algorithm and get the assignment matrix; 
         [0009]    Process the assignment matrix and track each target separately, including new target. 
         [0010]    The details of obtain target state are as follow: 
         [0011]    Process each existing target using non-linear filter, predict their position and size in current frame. 
         [0012]    Detect all objects in current frame, 
         [0013]    Compute cost matrix from target state and observations, details are as follow: 
         [0014]    Compute position distance, size distance, and histogram distance between each existing target and detected observation. Sum these distance, thus form the element of cost matrix. 
         [0015]    Solve cost matrix using EMD algorithm and get the assignment matrix. 
         [0016]    Use the assignment matrix to track each existing and new target separately. All objects are classified as new target, disappeared target, occluded and isolated one. 
         [0017]    The method to handle new target entry is as follow: 
         [0018]    Find the maximum element for each column in assignment matrix, and compare it with a user defined threshold, if it is greater than the threshold value, it&#39;s a new object, and initialize state. 
         [0019]    The method to handle target exit is as follow: 
         [0020]    Find the maximum element for each row in assignment matrix, if the element is less than a user defined threshold, then increment the disappear count. If it&#39;s disappear count is greater than a threshold, delete the target. 
         [0021]    The method to handle target occlusion is as follow: 
         [0022]    Compute the number of element which is greater than a threshold; 
         [0023]    If the number is 1, update the state of target using the corresponding observation; 
         [0024]    If the number is greater than 1, the occlusion occurs, and update target state using these corresponding observations. 
         [0025]    A multi-target tracking method for video surveillance, the main steps include: 
         [0026]    Target acquisition module, used to obtain target state in previous frame; 
         [0027]    Object detection module, used to detect all targets in current frame and get their state; 
         [0028]    Correspondence computation module, which uses target state and observation state to construct cost matrix, solves it using EMD algorithm and the result is an assignment matrix; 
         [0029]    Recognition module, used to handle each target separately from the assignment matrix. 
         [0030]    Additionally, the method includes following modules: 
         [0031]    Prediction module, used to predict the state of existing target in current time, including position, size and color histogram. 
         [0032]    Correspondence computation module computes position distance and size distance, histogram distance between each existing target and detected observation. Sum these distances, thus form the element of cost matrix. 
         [0033]    Use assignment matrix to handle new object entry, target exit, and target occlusion. 
         [0034]    The method to handle new target entry is as follow: 
         [0035]    Find the maximum element for each column in assignment matrix, and compare it with a user defined threshold. If it is greater than the threshold value, it&#39;s a new object, and initialize state for it. 
         [0036]    The method to handle target exit is as follow: 
         [0037]    Find the maximum element for each row in assignment matrix, if the element is less than the threshold, increment the disappear count. If it&#39;s disappear count is greater than a threshold, delete the target. 
         [0038]    The method to handle target occlusion is as follow: Compute the number of element which is greater than a threshold value; 
         [0039]    If the number is 1, update the state of target using the corresponding observation; 
         [0040]    If the number is greater than 1, occlusion occurs, update target state using these corresponding observations. 
         [0041]    The proposed method detects target in each frame, computes cost matrix for them, and establishes correspondences of target between adjacent frames using EMD algorithm. Experiments demonstrated the effectiveness of the method, which improves the accuracy of tracking considerately. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS  
         [0042]      FIG. 1  is a flowchart of a multi-target tracking method for video surveillance in accordance with an embodiment of the present invention. 
           [0043]      FIG. 2  is a flowchart of a method for constructing cost matrix from target sate and observation and solving the cost matrix using EMD algorithm to get an assignment matrix. 
           [0044]      FIG. 3  is a flowchart for processing disappearance of the target in current frame according to elements in the assignment matrix in accordance with the embodiment of the present invention. 
           [0045]      FIG. 4  is a flowchart for processing occurrences of the occlusion of the target in current frame according to elements in the assignment matrix in accordance with the embodiment of the present invention. 
           [0046]      FIG. 5  is a schematic diagram of the structure of multi-target tracking device for video surveillance in accordance with the embodiment of the present invention. 
           [0047]      FIG. 6  is a schematic diagram of the structure of multi-target tracking device for video surveillance in accordance with another embodiment of the present invention. 
           [0048]      FIG. 7  is a schematic diagram of the structure of computing module in accordance with the embodiment of the present invention. 
           [0049]      FIG. 8  is a schematic diagram of the structure of recognition module in accordance with the embodiment of the present invention. 
           [0050]      FIG. 9  is a schematic diagram of the structure of recognition module in accordance with another embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0051]    As shown in  FIG. 1 , the multi-target tracking algorithm includes the following steps: 
         [0052]    Step S 110  obtains all existing target&#39;s state in current frame, including position, size and color state. 
         [0053]    The details of step S 110  are as follow: 
         [0054]    For each existing target, using non-linear filter to predict their state, in current implementation, particle filter is used. 
         [0055]    The target state includes position (x, y), size (w, h), and color histogram. 
         [0056]    In step S 130 , detect all targets in current frame. The candidate object detection schemes include motion based methods, such as Gaussian mixture model, classifier based methods, such as Haar and Adaboost method, histograms of oriented gradients and support vector machine method, and so on. As has detected all targets, state is computed, the state is called observation, including position, size and color histogram. However, there exists missed detection and false alarm. 
         [0057]    In step S 150 , compute cost matrix from target state and observation, and solve it using EMD algorithm, the result is assignment matrix, which represents correspondence between each existing target and observation. 
         [0058]    The details of step S 150  are as follow: 
         [0059]    Step S 151  uses each existing target and observation&#39;s position, size, and color histogram to compute their distance. 
         [0060]    In the method, the state of existing target includes (x prev , y prev , w prev , h prev ) i , and hist prev,i , (x prev , y prev ) i  is ith target&#39;s position, (w prev , h prev ) i  is size, hist prev,i  is color histogram. 
         [0061]    The observation representing state of target in current frame includes (x cur , y cur , w cur , j cur ) j  and hist cur,j , identically (x cur , y cur ) j  is jth target&#39;s position, (w cur , h cur ) j  is size, and hist cur,j  is color histogram. 
         [0062]    The position distance between ith target and jth observation is defined as: 
         [0000]        D   pos ( i, j )=√{square root over (( x   prev,i   −x   cur,j ) 2 +( y   prev,i   −y   cur,j ) 2 )}{square root over (( x   prev,i   −x   cur,j ) 2 +( y   prev,i   −y   cur,j ) 2 )}
 
         [0063]    Similarly, the size distance is defined as: 
         [0000]        D   size ( i, j )=√{square root over (( w   prev,i   −w   cur,j ) 2 +( h   prev,i   −h   cur,j ) 2 )}{square root over (( w   prev,i   −w   cur,j ) 2 +( h   prev,i   −h   cur,j ) 2 )}
 
         [0064]    Color distance is defined as: 
         [0000]    
       
         
           
             
               
                 D 
                 hist 
               
                
               
                 ( 
                 
                   i 
                   , 
                   j 
                 
                 ) 
               
             
             = 
             
               
                 1 
                 - 
                 
                   
                     ∑ 
                     
                       k 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     
                       h 
                       
                         i 
                         , 
                         k 
                       
                     
                     · 
                     
                       h 
                       
                         j 
                         , 
                         k 
                       
                     
                   
                 
               
             
           
         
       
     
         [0065]    Where n is the size of color histogram, h i,k  is normalized component. 
         [0066]    In step S 153 , sum position distance, size distance, and histogram distance, the result is the element of cost matrix. 
         [0067]    If the number of existing in previous frame is m, the number of observation in current is n, a m×n cost matrix are constructed, and is used by EMD algorithm, which is defined as: 
         [0000]        M   i,j   =αD   pos ( i, j )+β D   size ( i, j )+γ D   hist ( i, j )
 
         [0068]    Where α, β and γ are used defined Coefficients between [0, 1], and the sum of them is 1. 
         [0069]    In step S 155 , the method uses the distance value to form cost matrix. 
         [0070]    Solve the cost matrix by EMD algorithm and got a assignment matrix f, the element f i, j  represents the correlation between ith target and jth observation, which is between [0, 1]. 
         [0071]    In step S 170 , process each target and observation separately. 
         [0072]    In some surveillance scenes, targets split, merge, and occlude frequently. Using assignment matrix, these problems are solved accurately. 
         [0073]    In order to process new targets, find the maximum element for each column in assignment matrix, and compare it with a user defined threshold t new , if it is greater than t new , it&#39;s a new object, and initialize state. 
         [0074]    In step S 171 , the method to handle target exit is as follow: 
         [0075]    Firstly, find the maximum element for each row in assignment matrix, if the element is less than the threshold t exist , increment the disappear count. If the disappear count is greater than a threshold, delete the target, this is implemented in step S 173 . 
         [0076]    As shown in  FIG. 4 , the method to handle target occlusion is as follow: 
         [0077]    Step S 175 : compute the number of element which is greater than a threshold t; 
         [0078]    Step S 176 : If the number is 1, update the state of target using the corresponding observation. The histogram is updated as follow: 
         [0000]      hist new (1−α)hist prev +α·hist cur  
 
         [0079]    Where hist prev  is the histogram in previous frame, hist cur  is the histogram of observation in current frame, hist new  is new histogram, α is a user defined value which between [0, 1]. 
         [0080]    Step S 177 : if the number is greater than 1, occlusion occurs, update target state using these corresponding observations. 
         [0081]    If the elements greater than threshold are f i,1 , . . . , f i,s , normalize them and got w 1 , . . . , w s , then use their corresponding observation j 1 , . . . , j s  to update target state. The histogram is updated as follow: 
         [0000]    
       
         
           
             
               hist 
               new 
             
             = 
             
               
                 
                   ( 
                   
                     1 
                     - 
                     α 
                   
                   ) 
                 
                  
                 
                   hist 
                   prev 
                 
               
               + 
               
                 α 
                 · 
                 
                   hist 
                   
                     cur 
                      
                     _ 
                      
                     mean 
                   
                 
               
             
           
         
       
       
         
           
             
               hist 
               
                 cur 
                  
                 _ 
                  
                 mean 
               
             
             = 
             
               
                 ∑ 
                 
                   i 
                   = 
                   1 
                 
                 s 
               
                
               
                   
               
                
               
                 
                   w 
                   i 
                 
                 · 
                 
                   hist 
                   
                     cur 
                     , 
                     i 
                   
                 
               
             
           
         
       
     
         [0082]    Where hist cur,i  is the histogram of ith observation, w i  is normalized match factor. 
         [0083]    Using EMD algorithm, the method handles new target entry, target exit, target occlusion conveniently, 
         [0084]    As shown in  FIG. 5 , the tracking algorithm includes obtaining module  110 , object detection module  130 , computation module  150 , and recognition module  170 . 
         [0085]    The obtaining module  110  is used to obtain target state in previous frame and predict it in current frame. The state includes position, size, and color information. 
         [0086]    As shown in  FIG. 6 , the algorithm also includes module  210 , the prediction module. 
         [0087]    Module  210  is used to predict all existing target&#39;s state in current frame, including position, size and color histogram. 
         [0088]    In current implementation, particle filter is used. As a predictor, particle filter predict the position and size of each target, Position is represented as a point (x, y) in image coordinate, size is represented as (w, h), where w is width and h is height. Color histogram is used to describe the appearance of target. 
         [0089]    Object detection module  130  is used to detect all objects in current frame and get their state. 
         [0090]    In current implementation, different scheme are be used, such as motion based methods (for example, Gaussian mixture background model), classifier based methods (for example, Haar Adaboost and HOG SVM). The output of object detector is a list of rectangles, from these rectangles, the method gets the position, size and color histogram for each object. However, there exists problem such as missing detection, false alarm for all methods. 
         [0091]    Computation module  150  is used to construct cost matrix from target state and observation and solve it by EMD algorithm. 
         [0092]    Module  150  includes distance computation unit  151 , element computation unit  153 , and matrix construction unit  155 . 
         [0093]    Distance computation unit  151  is used to compute distance between each target and observation. In the method, it includes position distance, size distance, and histogram distance. 
         [0094]    The state of ith target is represented as (x prev , y prev , w prev , h prev ) i  and hist prev,i , where (x prev , y prev ) i  is position predicted in current frame, (w prev , h prev ) i  is size, and hist prev,i  is histogram. 
         [0095]    The jth observation in current is represented as (x cur , y cur , w cur , h cur ) j  and hist cur,j , identically, (x cur , y cur ) j , (w cur , h cur ) j , hist cur,j  are position, size and histogram respectively. 
         [0096]    Unit  151  computes position distance as follow: 
         [0000]        D   pos ( i, j )=√{square root over (( x   prev,i   −x   cur,j ) 2 +( y   prev,i   −y   cur,j ) 2 )}{square root over (( x   prev,i   −x   cur,j ) 2 +( y   prev,i   −y   cur,j ) 2 )}
 
         [0097]    Size distance is computed as: 
         [0000]        D   size ( i, j )=√{square root over (( w   prev,i   −w   cur,j ) 2 ⇄( h   prev,i   −h   cur,j ) 2 )}{square root over (( w   prev,i   −w   cur,j ) 2 ⇄( h   prev,i   −h   cur,j ) 2 )}
 
         [0098]    Histogram distance is computed as: 
         [0000]    
       
         
           
             
               
                 D 
                 hist 
               
                
               
                 ( 
                 
                   i 
                   , 
                   j 
                 
                 ) 
               
             
             = 
             
               
                 1 
                 - 
                 
                   
                     ∑ 
                     
                       k 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     
                       h 
                       
                         i 
                         , 
                         k 
                       
                     
                     · 
                     
                       h 
                       
                         j 
                         , 
                         k 
                       
                     
                   
                 
               
             
           
         
       
     
         [0099]    Where n is the size of histogram, h i,k  is normalized component. 
         [0100]    Unit  153  constructs distance from the output of unit  151 , the distance is defined as: 
         [0000]        M   i,j   =αD   pos ( i, j )+β D   size ( i, j )+γ D   hist ( i, j )
 
         [0101]    Where M i,j  is the distance between ith target and jth observation, also, it&#39;s the element of cost matrix in row i and column j. And α, β and γ are used defined Coefficients between [0, 1], and the sum of them is 1. The construction of matrix is implemented by unit  155 . 
         [0102]    The cost matrix is solved using EMD algorithm and the output is the assignment matrix, all elements of which are between [0, 1]. These elements represent Matching Degree between target and observation. 
         [0103]    Recognition module  170  is used to track each target separately from assignment matrix. In order to tack each target correctly, target split, merge, and occlusion must be handled. Additionally, the method should recognize new target entry and target exit. 
         [0104]    the method to handle target exit is as follow: 
         [0105]    In order to process new targets, find the maximum element for each column in assignment matrix, and compare it with a user defined threshold t new , if it is greater than t new , it&#39;s a new object, and initialize state. 
         [0106]    The method to handle target exit is as follow: 
         [0107]    Firstly, find the maximum element for each row in assignment matrix, if 
         [0108]    the element is less than the threshold t exist , increment the disappear count. If it&#39;s disappear count is greater than a threshold, delete the target. 
         [0109]    Disappear count is implemented by unit  171  and deletion of target is implemented by unit  173 . 
         [0110]    The method to handle target occlusion is as follow: 
         [0111]    Unit  175 : compute the number of element which is greater than a threshold t; 
         [0112]    Unit  176 : If the number is 1, update the state of target using the 
         [0113]    corresponding observation. The histogram is updated as follow: 
         [0000]      hist new =(1−α)hist prev +α·hist cur  
 
         [0114]    Where hist prev  is the histogram in previous frame, hist cur  is the histogram of observation in current frame, hist new  is new histogram, α is a user defined value which between [0, 1]. 
         [0115]    Unit  177 : if the number is greater than 1, occlusion occurs, we update target state using these corresponding observations. 
         [0116]    If the elements greater than threshold are f i,1 , . . . , f i,s , normalize them and the normalized value is w 1  . . . , w s , then use their corresponding observation j 1 , . . . , j s  to update target state. The histogram is updated as follow: 
         [0000]    
       
         
           
             
               hist 
               new 
             
             = 
             
               
                 
                   ( 
                   
                     1 
                     - 
                     α 
                   
                   ) 
                 
                  
                 
                   hist 
                   prev 
                 
               
               + 
               
                 α 
                 · 
                 
                   hist 
                   
                     cur 
                      
                     _ 
                      
                     mean 
                   
                 
               
             
           
         
       
       
         
           
             
               hist 
               
                 cur 
                  
                 _ 
                  
                 mean 
               
             
             = 
             
               
                 ∑ 
                 
                   i 
                   = 
                   1 
                 
                 s 
               
                
               
                   
               
                
               
                 
                   w 
                   i 
                 
                 · 
                 
                   hist 
                   
                     cur 
                     , 
                     i 
                   
                 
               
             
           
         
       
     
         [0117]    Where hist cur,i  is the histogram of ith observation, w i  is normalized match factor. 
         [0118]    The method described above resolve new target entry, target exit and occlusion accurately, through assignment matrix constructed by EMD algorithm. 
         [0119]    The proposed method uses object detection algorithm to detect target in video frame, and EMD algorithm to solve the data association problem. Compared with existing association method, EMD algorithm handle target occlusion more effectively, so it&#39;s suitable for target tracking in video surveillance, especially dense targets. 
         [0120]    The person skilled in this art can understand that all the steps or parts of the steps of the method of the above described invention are realized by the relative hardwares controlled by computer program. The program is stored in a computer readable storage medium, when the program is implemented, the flowchart of the method described above is includes. Wherein the readable storage medium can be magnetic disk, compact disk, read-only memory (ROM), or random access memory (RAM). 
         [0121]    The above described examples are only a few embodiments of the present invention, and the descriptions are detailed, but it should not be understood that they are not intended to limit the invention to these embodiments. It should be noted that, to the person skilled in this art, the alternatives, modifications and equivalent to the embodiments may be included within the spirit and scope of the invention. Therefore, the extent of protection of the present invention shall be determined by the attached claims.