Abstract:
A real-time, semi-automatic method for discriminant track initialization in thermal imagery is very critical for tracking since it determines what to track for the tracker. Therefore, any insignificant or false information may result in redundant features or deceptive appearance that can cause premature track losses. To achieve long-term tracking, a real-time, semi-automatic track initialization methodology for images is proposed which takes a single image coordinate as input, then generates target bounding box for the most salient segment. The present invention is designed for real-time applications in which erroneous user input is unavoidable. Therefore, error compensation capability of present invention both introduces many practical advantageous together with performance boost. Low computational cost and requirement of only a point coordinate as input in the vicinity of the target make this approach preferable in real-time tracking applications.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is the national phase entry of International Application No. PCT/TR2014/000158, filed on May 8, 2014, the entire contents of which are incorporated herein by reference. 
     
    
     TECHNICAL FIELD 
       [0002]    The present invention relates to a biologically inspired, semi-automatic track initialization method for real-time applications using IR imagery that takes an image coordinate as input, then generates target bounding box for the tracker as track window. The present invention is capable of compensating erroneous user input, generates exactly same target bounding box even if the click input scatters, and also designed to boost tracker performance by initializing tracker with more discriminative targets. By requesting nothing but a click input, the present invention becomes both semi-automatic and appropriate for real-time applications. 
       BACKGROUND 
       [0003]    Target tracking is a classical problem, so diverse set of algorithms exist in the literature. However, most of the tracking algorithms assume predetermined target location and size for track initialization. Hence, in many applications, target size and location are required as input from human-users. Obviously, track initialization can drastically change tracker performance, since it determines for the tracker what to track, i.e. features, appearance, contours. Thus, any insignificant or false information may result in mislearning of target appearance. 
         [0004]    Request for target bounding box for track initialization may be answered by the user if there is not any time constraint for target selection. However, for many real-time applications drawing bounding box around the target manually is inappropriate since target should be marked instantly. Therefore, in real time applications, erroneous input is usually provided by the user due to time restriction. Moreover, system delays are also unavoidable in such systems which also increase possibility of false track initialization. Indeed, erroneous user input results in suboptimal tracking performance and yields premature track losses. If long-term tracking performance is desired, this erroneous input should be compensated. Moreover, even in the case that user provides a perfect bounding box for object, depending on the appearance of the target; this initialization may not always be preferred. For example, if track window is given as in (b) of  FIG. 9 , it may result in redundant features or deceptive appearance depending on the type of tracker, due to high resemblance between target and background, and may not provide long-term tracking. Hence, in order to achieve longer tracks, the proposed method selects the most salient (distinctive) segment from background as target as illustrated in (c) of  FIG. 9 . 
         [0005]    China patent document CN101329767 discloses an automatic inspection method of a significant object sequence based on studying videos. In the method of the invention, first static significant features then dynamic significant features are calculated and self-adaptively combined according to the space continuity of each image of frame and the time continuity of significant objects in neighboring images. Since this method generally takes several seconds to process an image, it is not appropriate for real-time applications. 
         [0006]    United States patent document US2012288189, an application in the state of the art, discloses an image processing method which includes a segmentation step that segments an input image into a plurality of regions by using an automatic segmentation algorithm, and a computation step that calculates a saliency value of one region of the plurality of segmented regions by using a weighted sum of color differences between the one region and all other regions. Accordingly, it is possible to automatically analyze visual saliency regions in an image, and a result of analysis can be used in application areas including significant object detection, object recognition, adaptive image compression, content-aware image resizing, and image retrieval. However, change in image resolution result in change in processing time which may exceed real-time application limits. 
         [0007]    United States patent document US2008304740, an application in the state of the art, discloses methods for detecting a salient object in an input image are described. For this, the salient object in an image may be defined using a set of local, regional, and global features including multi-scale contrast, center-surround histogram, and color spatial distribution. These features are optimally combined through conditional random field learning. The learned conditional random field is then used to locate the salient object in the image. The methods can also use image segmentation, where the salient object is separated from the image background. However, obviously it is not proper for the real time usage. 
         [0008]    United States patent document US20120294476, an application in the state of the art, discloses methods for detecting a salient object in an input, image are described. To find the salient objects, a computing device determines saliency measures for locations in the image based on costs of composing the locations from parts of the image outside of those locations. In the beginning of the process, input image is segmented into parts then saliency measures are calculated based on appearance and spatial distances for locations defined by sliding windows. In conclusion, this system cannot be proper for the real time usage. 
         [0009]    The PCT application document 8058-143 is also intended to achieve the same goal by using center-surround histogram differences and a suboptimal thresholding methodology together with the same saliency map generation. Although both methodologies use geodesic saliency as discrimination measure, the present invention uses completely different initial window selection mechanism together with an optimal thresholding methodology that yields superior track initialization performance with improved error compensation and time efficiency. Moreover, initial window correction step is introduced in the present invention which improves the robustness directly together with thermal core alignment step. 
       REFERENCES 
       [0000]    
       
         [1] Nobuyoki Otsu, “A threshold selection method from gray-level histograms”, IEEE Trans. Sys. Man., Cyber. 9, 1979(1), 62-66. doi:10.1109/TMSC.1979.4310076 
         [2] Y. Wei, F. Wen. W. Zhu and J. Sun, “Geodesic Saliency Using Background Priors”, IEEE, ICCV, 2012. 
       
     
       SUMMARY OF THE INVENTION 
       [0012]    Objective of the present invention is to provide track initialization framework which takes a single image coordinate from the user and returns the most discriminant region bounding box in the neighborhood. The proposed framework includes two outstanding features which are also proven. Firstly, it is robust to user input error meaning that exactly same track initialization can be achieved even if the given coordinate scatters in a neighborhood in the vicinity of the target as illustrated in  FIG. 10 . Secondly, since track initialization is based on visual saliency, it results in more discriminative targets with respect to background and provides long-term tracking even in trackers that claim to deal with discrimination problem during tracking. Although, redetection is merit of tracker itself, this feature also boost redetection performance since better discriminative targets are in consideration. Another important prosperity of the present invention is its suitability of real-time systems due to its low computational cost. 
         [0013]    The present invention goes through the following stages to achieve discriminant track initialization: First, initial window containing the actual target and its immediate background is selected ( 102 ); second visual saliency method by Y. Wei et.al., “Geodesic saliency using background priors”, 2012, ECCV, is exploited in the window and saliency map is obtained ( 103 ) and then it is binarized ( 104 ). After then, a validation procedure for initial window selection is utilized ( 105 ) by using heuristics on validity of saliency map; since the resulting saliency map and initial window selection is closely related. If the validation procedure defines window as invalid initial window alteration ( 106 ) is achieved. Finally, the connected component having maximum total saliency with minimum distance to the click input ( 101 ) is selected as target ( 107 ). All the concepts that are mentioned here will be explained in detail in the following section. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]    A system and method realized to fulfill the objective of the present invention is illustrated in the accompanying figures, in which: 
           [0015]      FIG. 1  shows the flowchart of the overall system. 
           [0016]      FIG. 2  shows the steps of initial window selection procedure. 
           [0017]      FIG. 3  shows the steps of polarity estimation procedure. 
           [0018]      FIG. 4  shows the steps of thermal core alignment procedure. 
           [0019]      FIG. 5  shows the steps of intensity slice analysis procedure. 
           [0020]      FIG. 6  shows the steps for binarization of saliency map. 
           [0021]      FIG. 7  shows the steps of initial window validation procedure. 
           [0022]      FIG. 8  shows the steps of bounding box generation for the selected target. 
           [0023]      FIG. 9  shows the input image (a), initialization with whole target (b) and initialization via present invention (c) which results in better discriminability due to high resemblance between target and background. 
           [0024]      FIG. 10  shows the output, selected target bounding box, with scattered user inputs. 
           [0025]      FIG. 11  shows the thermal core alignment (a), intensity slice analysis procedures (b), and resultant initial window selection (c). 
           [0026]      FIG. 12  shows the effect of initial window selection (left column) on saliency map (middle column), and binarization (right column). 
       
    
    
     DETAILED DESCRIPTION 
       [0027]    Hereinafter, present invention will be described in more detail with reference to attached drawings. The following embodiments are presented only for the purpose of describing the present invention, and are not intended to limit the scope of the present invention. 
         [0028]    The track initialization method proposed in the present. invention is said to be semi-automatic and appropriate for real-time applications since it requests nothing but a click input. In addition, the system can be said to be robust and user friendly since exactly same track initialization can be achieved even if the given coordinate scatters in a neighborhood and it is suitable for long-term tracking since it boosts performance of tracker by achieving better discrimination between the target and background. The details of the present invention, illustrated in  FIG. 1 , are explained in this part in four sections. First, utilization of the initial window selection ( 102 ) method,  FIG. 2 , which comprises three subsections, namely target polarity estimation ( 201 ), thermal core alignment ( 202 ) and intensity slice analysis ( 203 ) will be explained. Second, the method suggested by Wei et al., 2012 which is used for saliency map calculation ( 103 ) will be mentioned in brief. Then, utilization of the initial window validation procedure ( 105 ) together with initial window alteration step ( 106 ).  FIG. 7 , will be clarified by also explaining the reasoning for used heuristics on validity of saliency map; the resulting saliency map and initial window selection are closely related. Finally, binarization procedure of the saliency map ( 104 ).  FIG. 6 , and the target bounding box generation procedure ( 107 ).  FIG. 8 , is explained. The whole procedure is started by user with a click (marking) input ( 101 ) which is the single point coordinate in the vicinity of the target. These steps are extensively analyzed in this chapter. 
       Initial Window Selection 
       [0029]    To calculate saliency map correctly, assumptions of saliency calculation methodology should be satisfied by providing a proper initial window. A proper window should contain entire object, which is roughly centralized, together with its immediate surroundings and is achieved in three steps: target polarity estimation, thermal core alignment, and intensity slice analysis. 
         [0030]    Target Polarity Estimation 
         [0031]    Target polarity is a strong cue for target localization and should be estimated if it is not explicitly known. For this purpose a simple thresholding method is used. First, an image patch is extracted with predetermined sized centralized at the click input and this image patch is normalized to the range [0,255] ( 301 ). Then, using the normalized image patch, soft-histogram of ROI is calculated with the weights from a 2D-Gaussian whose mean is at user input ( 302 ). Whenever target pixels dominate the soft-histogram, its expected value, which is calculated in step ( 303 ), will be shifted to the half zone of the contrast range close to target pixels. Hence, polarity is estimated by comparing expected value with polarity threshold ( 306 ) which is decided to be the average of minimum and maximum intensities in the ROI found in step or to be 128 according to contrast stretch in the ROI ( 304 , 305 ). Note that, variance of the Gaussian is important to ensure domination of target pixels in the ROI. If variance is too high, estimation may be dominated by background. On contrary, if it is too small, marking error tolerance will be very limited. So, we decided to select √12 times of minimum object size to correspond 68% energy of the gaussian, 1σ, which ensures the domination of target pixels with click error smaller than 0.2 times of minimum object size in the worst case. Although, it seems very limited; practically better error compensation is achieved since worst case, background composed full of minimum/maximum intensity, is not much likely to occur. All the mentioned steps are summarized in the  FIG. 3 . 
         [0032]    This phase can be considered to be optional since polarity can be a direct input. Actually in this case, the given additional information relaxes the main restriction on error compensation, and increases overall system performance. 
         [0033]    Thermal Core Alignment 
         [0034]    According to heat distribution law; heat diffuses from hottest/coldest point, namely thermal core, to other segments smoothly. Actually, this inherently implies that thermal core must be definitely inside of the object. Thus, disclosure of thermal core yields rough centralization of object in the initial window and can be achieved by following heat (intensity) transition. However, due to noise or any imperfection monotonous transition to thermal core is not guaranteed. Hence, rather than tracing smooth transition path, jumping through local extrema iteratively becomes a possible way to locate closest thermal core. First, the local extremum is located ( 401 ) in a predetermined sized window which is centralized at the click input. Then, center of the window is shifted to new local extremum until extremum is found to be the center pixel. To be clearer, the condition to break iterations is to query if the extrema is located at the centre or to check whether maximum number of iterations is readied ( 402 ). If there are multiple extrema, having same intensity; closest is selected. After all iterations latest local extrema is selected to be the thermal core ( 403 ). Thermal core alignment is not only used for centralization of foreground but also for error compensation; since erroneous inputs scattering in the vicinity of target would possibly converge to the same thermal core as shown in (a) of  FIG. 11 . All the steps required by the thermal core alignment are summarized in  FIG. 4 . 
         [0035]    Intensity Slice Analysis 
         [0036]    To fulfill the assumptions of saliency calculation method, initial window should be limited in a size including whole target and its immediate surroundings, but avoiding similar objects or new layer of background. Actually, it is equivalent to search for a window size resulting in maximization of dissimilarity between target and back round however our knowledge about target and background is limited to three facts: thermal core stands inside of the target, it is a local extrema, and new background layer can start from anywhere in image space outside of the target. Since our knowledge is based on only intensity values and all directions are in need of search, intensity slices are decided to be used to measure similarity by using in Eqn. 1. Initial point of each slice is arranged to be thermal core and they extend out ( 501 ). Note that, a simple low-pass filtering is applied to intensity slices to smooth out the noise ( 502 ). In (b) of  FIG. 11 , middle, an example is given with 16 slices. In this case, 5 slices in resolution of 22.5° is used in each quarter to limit each of four direction of initial window; e.g. slices from 3 to 7 for top, from 7 to 11 for left and so on. Obviously, more slices yields better spatial resolution with the cost of increase in computational complexity. 
         [0000]      Energy quarter =Σ i=Slices in the quarter Slice i   n   (1)
 
         [0037]    According to Eqn. 1 first increase of each energy quarter is achieved, ( 503 ), either at a sharp increase in one slice, possibly encountering with an object like pixel; or relatively smaller increase in multiple slices, possibly entering a new layer of background. Therefore, keeping these pixels clear of the initial window yields maximum dissimilarity so first increases are selected as limits ( 504 ). The power, n, in the energy function stands for contrast stretching as in power-law transformation and should be selected properly. If n is too high, initial window may be cropped even within the target boundary since it responds to very strict contrast difference. On the contrary, choosing n very small may cause very large initial window which is not also desired. So, window selection may fail due to improper level of contrast stretching which generally corrected in the initial window validation phase. An exemplary result of initial window selection is given in (c) of  FIG. 11  which includes target (car) and its immediate surrounding (road). Note that similar object and the outer background layers are prevented to be in the initial window. The necessary steps for the intensity slice analysis are shown in  FIG. 5 . 
       Saliency Map Calculation 
       [0038]    After selection of initial window, to extract the shape of the target saliency map of the initial window is calculated. This calculation is utilized by a recently proposed last saliency extraction method (Wei et al., 2012) in which the saliency problem is tackled from different perspective by focusing on background more than the object. Although, this method is capable of extracting a saliency map within few milliseconds; it has two basic assumptions for the input image that should be guaranteed, namely boundary and connectivity. The boundary assumption conies from a basic tendency that photographer/cameraman do not crop salient objects among the frame. Therefore, the image boundary is usually background. The second assumption, connectivity, comes from the fact that background regions are generally tend to be large and homogenous, i.e. sky, grass. In other words, most image patches can be easily connected to each other piece wisely. 
         [0039]    Considering these two priors, the salient regions are assumed to be the patches that are extracted by downscaling or by any super pixel extraction algorithm, with high geodesic distance from the boundaries of the image which are assumed to correspond to piecewise-connected background regions. The geodesic saliency of a patch p is the accumulated edge weights along the shortest path from p to virtual background node b in an undirected weighted graph p∈{υ, 68  }, 
         [0000]        S ( p )=min p   =p,p     2     , . . . ,p     n     =b Σ i=1   n−1 weight( p   i   ,p   i+1 ), s.t. ( p   i   ,p   i+1 )∈ε,  (2)
 
         [0040]    Note that, since patches close to the center of the image requires a longer path in order to reach the background, accumulations of weights tend to be larger in the center patches. Therefore, this method also favors the center image regions as more salient which is reasonable since salient regions tend to occur around the center of image. 
         [0041]    In the proposed method, these two assumptions are fulfilled with initial window selection method by roughly centralizing the target and including the immediate surrounding which both prevents target to be cropped among the frame and reduces target and background resemblance. 
       Initial Window Validation 
       [0042]    Initial window selection guarantees rough centralization of target; however it may not always achieve successful window size due to improper level of Contrast Stretching which is caused by inappropriate selection of n in Eqn. 1. Guaranteeing rough centralization yields center of binarized saliency map to be denser than its boundary. In this sense, large initial window sizes may be tolerated; however, when the object is cropped, object itself partly stands in the background which violates the boundary assumption and initial window should be corrected. In such cases, higher saliency is observed not in the middle but among border of the object. Therefore, density comparison between center and borders is used for validity check. Firstly, the binarized image is partitioned into five sections four of which is on the border and area of each is approximately twice of the center partition and then border and center densities are calculated ( 701 , 702 ). If the total density of borders is higher than twice of center density, ( 703 ), the initial window size is enlarged until the condition is dissatisfied which means a valid initial window ( 704 ). Note that, it is not enlarged in both directions simultaneously; but only in direction where boundary partitions are sparser, ( 705 , 706 , 707 ). In  FIG. 12 , effect of initial window (left) selection on saliency map (middle) and binarization (right) is visualized. Note that first initial window selection (first row) is altered and the after initial window alterations target shown in the last row of  FIG. 12  is selected. In this particular case, horizontal enlargement is achieved since resultant saliency acknowledges that target is cropped horizontally. 
       Binarization of Saliency Map &amp; Target Bounding Box Generation 
       [0043]    Although minimum computational cost is desired in each step, using static threshold or suboptimal methods for binarization may be problematic. Thus, Otsu&#39;s method is used with slight refinement. The method of Otsu, can be either defined as an exhaustive search for the threshold that either minimizes the within-class variance or maximizes between-class variance. The between-class variance is often calculated as given in Eqn.3: 
         [0000]      σ B   2   =w   b   w   f (μ b −μ f ) 2   (3)
 
         [0000]    where w b , w f  is referred as class probabilities and μ b, μ f,  are class means. After some manipulations. Eqn.3 can be written as in Eqn.4. 
         [0000]      σ B   2   =w   b μ b   2   +w   f μ f   2 −μ 2   (4)
 
         [0000]    Where μ is the mean value of the histogram. Since the purpose is to calculate the optimal threshold value T that maximizes σ B   2 , the problem can be solved by either inserting Eqn. 3 or Eqn. 4 into the Eqn. 5. 
         [0000]      {circumflex over (T)}=argmax{σ B   2 }  (5)
 
         [0044]    Note that using Eqn. 3 and Eqn. 4 directly results in Eqn. 6 and Eqn. 7 respectively; 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       T 
                       ^ 
                     
                     = 
                     
                       argmax 
                        
                       
                         { 
                         
                           
                             ( 
                             
                               
                                 Σ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 T 
                               
                                
                               
                                 f 
                                 i 
                               
                             
                             ) 
                           
                            
                           
                             ( 
                             
                               
                                 Σ 
                                 
                                   i 
                                   = 
                                   
                                     T 
                                     + 
                                     1 
                                   
                                 
                                 L 
                               
                                
                               
                                 f 
                                 i 
                               
                             
                             ) 
                           
                            
                           
                             
                               ( 
                               
                                 
                                   
                                     
                                       Σ 
                                       
                                         i 
                                         = 
                                         2 
                                       
                                       T 
                                     
                                      
                                     
                                       if 
                                       i 
                                     
                                   
                                   
                                     
                                       Σ 
                                       
                                         i 
                                         = 
                                         1 
                                       
                                       T 
                                     
                                      
                                     
                                       f 
                                       i 
                                     
                                   
                                 
                                 - 
                                 
                                   
                                     
                                       Σ 
                                       
                                         i 
                                         = 
                                         
                                           T 
                                           + 
                                           2 
                                         
                                       
                                       L 
                                     
                                      
                                     
                                       if 
                                       i 
                                     
                                   
                                   
                                     
                                       Σ 
                                       
                                         i 
                                         = 
                                         
                                           T 
                                           + 
                                           1 
                                         
                                       
                                       L 
                                     
                                      
                                     
                                       f 
                                       i 
                                     
                                   
                                 
                               
                               ) 
                             
                             2 
                           
                         
                         } 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
             
               
                 
                   
                     T 
                     ^ 
                   
                   = 
                   
                     argmax 
                      
                     
                       { 
                       
                         ( 
                         
                           
                             
                               
                                 ( 
                                 
                                   
                                     Σ 
                                     
                                       i 
                                       = 
                                       1 
                                     
                                     T 
                                   
                                    
                                   
                                     if 
                                     i 
                                   
                                 
                                 ) 
                               
                               2 
                             
                             
                               
                                 Σ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 T 
                               
                                
                               
                                 f 
                                 i 
                               
                             
                           
                           + 
                           
                             
                               
                                 ( 
                                 
                                   
                                     Σ 
                                     
                                       i 
                                       = 
                                       
                                         T 
                                         + 
                                         2 
                                       
                                     
                                     L 
                                   
                                    
                                   
                                     if 
                                     i 
                                   
                                 
                                 ) 
                               
                               2 
                             
                             
                               
                                 Σ 
                                 
                                   i 
                                   = 
                                   
                                     T 
                                     + 
                                     1 
                                   
                                 
                                 L 
                               
                                
                               
                                 f 
                                 i 
                               
                             
                           
                         
                         ) 
                       
                       } 
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where the number of pixels with gray level i1≦i≦L is given with f i .( 601 ) As it can be seen using Eqn. 4 becomes slightly advantageous since constant μ term is dropped out. This slight modification results in one less multiplication in Eqn. 7 than Eqn. 6 which results in L less multiplication in exhaustive search used in Otsu&#39;s methodology. Therefore, in order to achieve binarization threshold Eqn. 7 is preferred ( 602 ) and then the saliency map is binarized by using the obtained threshold ( 603 ). The binarization procedure is summarized in  FIG. 6 . 
         [0045]    After thresholding the saliency map, first a connected component analysis is executed ( 801 ). Then, the connected component maximizing the regularization energy given by Eqn. 8, i.e. the most salient region with minimum distance to the center, is selected as the target ( 802 ). 
         [0000]    
       
         
           
             
               
                 
                   argmax 
                    
                   
                       
                   
                    
                   
                     c 
                     i 
                   
                    
                   
                     
                       
                         c 
                         i 
                         T 
                       
                        
                       s 
                     
                     
                       
                         w 
                         d 
                       
                       * 
                       
                         sqrt 
                          
                         
                           ( 
                           
                             
                               
                                 ( 
                                 
                                   
                                     x 
                                     i 
                                   
                                   - 
                                   
                                     x 
                                     c 
                                   
                                 
                                 ) 
                               
                               2 
                             
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     y 
                                     i 
                                   
                                   - 
                                   
                                     y 
                                     c 
                                   
                                 
                                 ) 
                               
                               2 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where Ci is the vectorized form obtained by raster scanning the 2D label matrix with values 1 and 0 as foreground and background respectively, S is the saliency map vectorized similarly, w d  determines the weight of distance in calculation, and (xi,yi), (xc,yc) are the centers of each connected component and the initial window respectively. Finally, bounding box of the selected target is reported ( 803 ). Target selection procedure is summarized in  FIG. 8 .