# Patent

## Title
Apparatus and method for object tracking

## Abstract

An object tracking device includes a short-term processing portion and a long short-term processing portion that are implemented by circuitry and work in a collaborative manner to track an object. The short-term processing portion includes a filter that tracks the object based on short-term memory and spatiotemporal consistency. The long short-term processing portion performs key-point matching-tracking and estimation based on a key-point database in order to track the object. A controller determines an output of the object tracking device based on the processing conducted by the short-term and long short-term processing portions of the tracking device, respectively.

## Background
FIELD OF DISCLOSURE
The present disclosure relates generally to object tracking. Specifically, the present disclosure relates to an object tracking device that employs a dual component approach for processing and tracking objects.
BACKGROUND
The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
Variations in the appearance of a tracked object, such as changes in geometry, photometry, camera viewpoint, illumination, or partial occlusion, pose a major challenge to object tracking. The object tracking devices developed thus far can primarily be classified into two categories: short-term tracking devices and long-term tracking devices, respectively.
Short-term tracking devices are based on a short-term memory model and employ techniques such as incremental learning of a low-dimensional subspace of the target representation and sparse representation of tracking. The short-term memory of the target appearance is modelled using a small set of target instances and discriminative techniques that consider both background and foreground information. Short-term tracking devices depend on spatiotemporal consistency of visual clues and tend to be inefficient in complex object tracking applications.
In contrast, long-term tracking devices employ a long-term memory model and can be differentiated based on their choice of appearance models and inference algorithms. A long term object tracker such as the tracking-learning and detection (TLD) tracker employs two experts to identify the false negatives and false positives in order to train the detector. Additionally, some long term trackers model target appearances using oversampled local features, whereas other long term trackers are based on self-paced learning schemes in which the target appearance is learned by selecting trustworthy frames. A drawback of the above long term trackers is that they update the appearance model in a rather conservative manner and are thus not able to handle fast appearance changes that occur in a short time period.
Accordingly, there is a requirement for an object tracking device that addresses the above stated drawbacks of object trackers and boosts tracking performance.
SUMMARY
An object tracking device according to an exemplary embodiment, boosts tracking performance and addresses problems of complex object tracking, wherein the object may become occluded or leave the field-of-view. Specifically, the present disclosure provides for an object tracking device that adapts to changes in object appearances during tracking. The object tracking device (referred to herein as a multi-store tracker) is based on the Atkinson-Shiffrin memory model. The multi-store tracker includes one short-term memory store component and one long-term memory store component, which collaboratively process the input image and track the object.
According to one embodiment, an integrated correlation filter (ICF) that stores short-term memory and depends on spatiotemporal consistency is employed in the short-term store to perform short-term tracking via a two-stage filtering process. Additionally, the multi-store tracker includes a long-term memory component that is based on key-point matching-tracking and random-sample-consensus (RANSAC) estimation. The long-term memory component interacts with a key-point feature database and controls the final output as well as the short-term memory states. Further, in order to maintain a reasonable size for the key-point feature database, the multi-store tracker updates the key-point feature database based on a forgetting curve model, thereby retaining only the useful object features.
The foregoing paragraphs have been provided by way of general introduction, and are not intended to limit the scope of the following claims. The described embodiments together, with further advantages, will be best understood by reference to the following detailed description taken in conjunction with the accompanying drawings.



BRIEF DESCRIPTION OF THE DRAWINGS
Various embodiments of this disclosure that are provided as examples will be described in detail with reference to the following figures, wherein like numerals reference like elements, and wherein:
FIG. 1 depicts an exemplary schematic diagram illustrating an Atkinson-Shiffrin memory model;
FIG. 2 depicts, according to an embodiment, a block diagram illustrating components of an object tracking device;
FIG. 3 illustrates an exemplary flowchart depicting the steps performed by the multi-store tracker to track an object;
FIGS. 4A and 4B depict exemplary graphs illustrating the performance of the multi-store tracker;
FIG. 5 depicts a graph illustrating a comparison of an F-score of the multi-store tracker and other trackers; and
FIG. 6 illustrates a block diagram of a computing device according to one embodiment.



DETAILED DESCRIPTION OF EMBODIMENTS
Exemplary embodiments are illustrated in the referenced Figures of the drawings. It is intended that the embodiments and Figures disclosed herein are to be considered illustrative rather than restrictive. No limitation on the scope of the technology and of the claims that follow is to be imputed to the examples shown in the drawings and discussed herein.
Humans respond quickly to visual information by recognizing temporal consistency and memorizing useful visual features to recover from tracking failures when the target leaves the field-of-view. Memory is one of the most powerful, but least well understood, functions of the human brain. With the sophisticated memory system, humans are capable of adapting to complex environments and behaving stably and consistently when facing temporal issues. Accordingly, the present disclosure exploits the principles of biological memory to design a solution that address the problem faced in object tracking. Specifically, the object tracking device of the present disclosure is based on the Atkinson-Shiffrin's memory model.
An aspect of the present disclosure provides an object tracking device comprising: a first tracker implemented by circuitry configured to: determine and extract features, of a candidate image patch from an input image frame, evaluate the candidate image patch and cyclically shifted image patches of the candidate image patch to determine a location of a tracked object, resize and extract features from a predetermined number of image patches surrounding the determined location, to determine a first instance of the tracked object. Further, the object tracking device comprises a second tracker implemented by circuitry that is configured to: detect a plurality of key-points from the input image frame, classify, based on a key-point database, each detected key-point as one of a matched target key-point, a matched background key-point, and an unmatched key-point, compute, based on consecutive input image frames, an active set of key-points, and estimate, based on the computed active set of key-points and the matched target key-points, a set of inlier key-points included in a target bounding box that corresponds to a second instance of the tracked object. The object tracking device also includes a controller that is configured to generate a tracked object based on consistency of the first instance of the tracked object and the second instance of the tracked object.
According to one embodiment, is provided a method of object tracking. The method includes: determining, and extracting features of a candidate image patch, from an input image frame, evaluating by circuitry, the candidate image patch and cyclically shifted image patches of the candidate image patch, to determine a location of a tracked object; resizing, and extracting features, from a predetermined number of image patches surrounding the determined location to obtain a first instance of the tracked object; detecting a plurality of key-points from the input image frame, classifying, based on a key-point database, each detected key-point as one of a matched target key-point, a matched background key-point, and an unmatched key-point, computing by circuitry, based on consecutive input image frames, an active set of key-points, estimating, based on the computed active set of key-points and the matched target key-points, a set of inlier key-points included in a target bounding box that corresponds to a second instance of the tracked object; and generating by circuitry, a tracked object based on consistency of the first instance of the tracked object and the second instance of the tracked object.
According to one embodiment is provided a non-transitory computer readable medium having stored thereon a program that when executed by a computer causes the computer to execute a method to track an object. The method includes: determining, and extracting features of a candidate image patch, from an input image frame, evaluating the candidate image patch and cyclically shifted image patches of the candidate image patch, to determine a location of a tracked object; resizing, and extracting features, from a predetermined number of image patches surrounding the determined location to obtain a first instance of the tracked object; detecting a plurality of key-points from the input image frame, classifying, based on a key-point database, each detected key-point as one of a matched target key-point, a matched background key-point, and an unmatched key-point, computing based on consecutive input image frames, an active set of key-points, estimating, based on the computed active set of key-points and the matched target key-points, a set of inlier key-points included in a target bounding box that corresponds to a second instance of the tracked object; and generating a tracked object based on consistency of the first instance of the tracked object and the second instance of the tracked object.
Turning to FIG. 1, a schematic diagram illustrating the Atkinson-Shiffrin's memory model (ASMM) 100 is depicted according to an exemplary embodiment. The ASMM 100 is also referred to herein as a multi-store memory model. The ASMM 100 includes a sensory memory register 103, a short-term memory 105, and a long-term memory 107. Initially, environmental input signals 101 are delivered to the sensory memory register 103, at which point the original input signals are transformed into chemical and physical signals for processing within the biological system. The sensory memory register 103 includes environmental signals 101 that are transformed into auditory information, visual information, haptic information and the like.
The input information from the sensory register 103 is further transferred to the short-term memory 105, wherein the information undergoes the processes of encoding, rehearsing, retrieving, and responding, after which the memory model 100 can output a reasonable and appropriate response 110. The short-term memory 105 does not retain information for an extended period of time. Accordingly, a long-term memorizing of the information is performed in the long-term memory 107. Specifically, if a particular pattern is received repeatedly, the long-term memory 107 is activated and the pattern information is retained therein. Once memorized, the pattern is maintained for a certain period of time but forgotten if not reinforced. As a result, the information inside the long-term memory 107 is a stable and consistent representation of current event sequences.
By combining short-term processing (performed in the short term memory 105) and long-term maintenance (performed in the long term memory 107), the memory model 100 produces sensitive and stable responses to complex inputs. For instance, when the external environment is continuous and steady, the processing performed in the short-term memory 105 is fast and the multi-store memory model 100 produces immediate responses. On the other hand, if the memory model 100 encounters a sudden change in input, information remembered by the long-term memory 107 is retrieved, which helps to stabilize the output 110. In such a manner, the cooperation between the short-term memory 105 and the long-term memory 107 allows humans to take reasonable actions in response to different and changing environments. Further, it should be appreciated that the ASMM 100 as depicted in FIG. 1 includes processing nodes (and their connections) in the short-term memory 105 and long-term memory 107 that correspond to possible structures of a neural network within a human brain. The processing nodes included in the short-term memory 105 and the long-term memory 107 collaboratively process the input image in order to track the object.
FIG. 2 depicts a block diagram illustrating components of an object tracking device (referred to herein as a multi-store tracker) 200 according to an exemplary embodiment. The multi-store tracker 200 is based on the ASMM shown in FIG. 1. As shown in FIG. 2, the framework of the multi-store tracker 200 can be divided into five portions, which include an external input, a sensory register, a shot-term store (i.e., a short term memory component), a long-term store (i.e., a long-term memory component), and an output response portion. Thus, the framework of the multi-store tracker 200 is based on the ASMM model depicted in FIG. 1. Further, as shown in FIG. 2, the processing of input image frames performed by the multi-store tracker 200 can be divided into a short-term processing portion 250 and a long short-term processing portion 260, which collaboratively process the sequential input image frames 201 in order to track an object and generate the output frames 270. According to an embodiment, the functions of the short-term processing portion 250 and the long short-term processing portion 260 may be implemented by one or more processing circuits. A processing circuit includes a programmable processor (described later with reference to FIG. 6).
The short-term processing portion 250 includes a feature extraction circuit 203, filtering circuit 205, and a short-term updating circuit 207. The feature extraction circuit 203 is configured to extract certain features (such as histogram of oriented gradient and color attribute features) that are further processed by the filtering circuit 205, in order to track an object included in the image. According to one embodiment, the filtering circuit 205 may include an integrated correlation filter (ICF) that performs short-term processing via a two-stage filtering process and tracks the target (i.e., object to be tracked) based on short-term memory and spatiotemporal consistency. In a relatively stable environment, the ICF performs accurate object tracking.
The multi-store tracker 200 also includes a long short-term processing portion 260 that performs image processing based on keypoint matching-tracking and random sample consensus (RANSAC) estimation. The long short-term processing portion 260 of the multi-store tracker 200 includes a key-point detection circuit 209, matching circuit 211, a keypoint tracking circuit 213, a RANSAC estimation circuit 215, a long-term updating circuit 219, and a key-point database 220. As described below, the matching circuit 211, key-point tracking circuit 213, and the RANSAC estimation circuit 215 are configured to conduct long short-term processing of the image on the fly. The matching circuit 211, the key-point tracking circuit 213, and the RANSAC estimation circuit 215 perform key-point matching, key-point tracking, RANSAC estimation, and further interact with the short-term memory using a forward-backward tracking technique. Further, the matching circuit 211, the key-point tracking circuit 213, and the RANSAC estimation circuit 215 retrieve the long term memory for matching (from the key-point database 220) and update (via the long-term updating circuit 219) the long-term memory based on the RANSAC estimation results and a forgetting curve model.
According to an embodiment of the present disclosure, during tracking, the outputs of both the short-term processing portion 250 and the long short-term processing portion 260 are transmitted to a controller 217 that is implemented by circuitry and configured to determine the final output frames 270 of the multi-store tracker 200. The controller 217 is further configured to update parameters of the filtering circuit 205 in an interpolating manner with a predetermined learning rate. The controller 217 updates the filter parameters via the short-term updating circuit 207. Specifically, the filtering circuit 205 that is included in the short-term store is reset when the output of the short-term processing portion 250 is highly inconsistent with the output of the long short-term processing portion 260. In doing so, the multi-store tracker 200 of the present disclosure is provided with an advantageous ability of recovering short-term tracking after dramatic appearance changes such as severe occlusion, the object leaving field-of-view, object rotation and the like.
In what follows, a detailed description of the operation of the multi-store tracker 200 is provided. Specifically, the operation of the short-term processing portion 250 and the long short-term processing portion 260, as well as the collaboration thereof in order to track the object is provided.
The processing conducted in the short-term processing portion 250 includes a two stage filtering process performed by the filtering circuit 205. The processing conducted in the long short-term processing portion 260 includes the processing of key-points by the matching circuit 211, the key-point tracking circuit 213, and the RANSAC estimation circuit 215. Further, the key-point database 220 is updated via the long-term updating circuit 219 based on a forgetting curve model. Additionally, the operation of the controller 217 in updating the filtering circuit 205 (via the short-term updating circuit 207), as well as in determining the output of the multi-store tracker 200 is provided.
The short-term processing portion 250 of the multi-store tracker 200 can be used to provide instant responses to the input image frames based on short-term memory. For accurate and efficient short-term processing performance, Integrated Correlation Filters (ICFs), which are based on the Kernelized Correlation Filters (KCFs) and Discriminative Scale Space Correlation Filter (DSSCF) are employed in the short-term processing portion 250 of the multi-store tracker 200. The ICF includes a two-stage filtering process that performs translation estimation and scale estimation, respectively. Specifically, the ICF serves as a short-term component of the multi-store tracker 200, wherein the short-term memory of ICF includes the coefficients and templates for the filters.
The KCF is defined by a classifier f(x)=w, φ(x), that is trained on a M×N image patch x, centered by the center of a target bounding box BT and is p times larger than BT. According to one embodiment, instead of using dense sliding windows to extract training samples, the classifier considers xi, which are all the cyclic shift versions of x, for training, where iε{0, 1, 2, . . . , M−1}×{0, 1, 2, . . . , N−1}. Each example xi is assigned a regression score yiε[0, 1] that is generated by a Gaussian function in terms of the shifted distance. The classifier is trained by minimizing the regression error:




  
    
      
        
          
            min
            w
          
          ⁢
          
            
              
                Σ
                i
              
              ⁡
              
                (
                
                  
                    〈
                    
                      w
                      ,
                      
                        ∅
                        ⁡
                        
                          (
                          
                            x
                            i
                          
                          )
                        
                      
                    
                    〉
                  
                  -
                  
                    y
                    i
                  
                
                )
              
            
            2
          
        
        +
        
          λ
          ⁢
          
            
              
              w
              
            
            2
          
        
      
    
    
      
        (
        1
        )
      
    
  




where φ(x) is a mapping to a Hilbert space, and λ≧0 is a regularization parameter that controls the simplicity of the tracker. Further, by employing a kernel κ(x, x′)=φ(x), φ(x′) the classifier can be derived as f(x)=Σiαiκ(xi, x), where α is the dual variable of w. For sake of simplicity, the Discrete Fourier transform (DFT) of a vector is represented with a hat “^” notation, e.g., {circumflex over (α)}=(α), and its complex conjugate is represented as {circumflex over (α)}*. Thus, if the kernel is shift invariant, for instance an RBF kernel, {circumflex over (α)}* can be computed based on the properties of circulant matrices:





  
    
      
        
          
            α
            ^
          
          *
        
        =
        
          
            y
            ^
          
          
            
              
                k
                ^
              
              xx
            
            +
            
              λ
              ′
            
          
        
      
    
    
      
        (
        2
        )
      
    
  




where kxx is a vector whose ith element is (xi, x). In particular, for image data with C feature channels, a concatenation x=[x1; . . . ; xC] can be constructed, and the kernel correlation kxx based on a Gaussian kernel can be efficiently computed by element-wise products and summation over the feature channels in the Fourier domain:





  
    
      
        
          k
          
            xx
            ′
          
        
        =
        
          exp
          ⁡
          
            (
            
              
                -
                
                  1
                  
                    α
                    2
                  
                
              
              ⁢
              
                (
                
                  
                    
                      
                      x
                      
                    
                    2
                  
                  +
                  
                    
                      
                      
                        x
                        ′
                      
                      
                    
                    2
                  
                  -
                  
                    2
                    ⁢
                    
                      
                        F
                        
                          -
                          1
                        
                      
                      ⁡
                      
                        (
                        
                          
                            Σ
                            
                              c
                              =
                              1
                            
                            c
                          
                          ⁢
                          
                            
                              
                                x
                                ^
                              
                              c
                            
                            ⊙
                            
                              
                                (
                                
                                  
                                    
                                      x
                                      ′
                                    
                                    ^
                                  
                                  c
                                
                                )
                              
                              *
                            
                          
                        
                        )
                      
                    
                  
                
                )
              
            
            )
          
        
      
    
    
      
        (
        3
        )
      
    
  




where the dot operator denotes element-wise products, and c denoted the index of the feature channels.

As stated previously, the ICF includes two stages of filtering: a first stage filtering that performs translation estimation and a second stage filtering that performs scale estimation. According to an embodiment, translation estimation is defined herein as an estimate of the translation location of the target, assuming no scale change. During the first-stage filtering for translation estimation, given a M×N candidate image patch z as the search space, all the cyclic patches of z can be evaluated as:

f(z)=−1(({circumflex over (k)}xz)*⊙{circumflex over (α)})  (4)

where f(z) is the filtering response for all the cyclic versions of z, and the translation is estimated by finding the location with the highest response. The candidate image patch z can be centered using the tracking result Bo of the last frame. Further, in order to adapt to the short-term appearance changes of the target, the filter coefficients α and the target template x are updated in an interpolating manner with a learning rate γ. Note that the target template is initialized (when the short-term component is rest) as an image patch x centered by the center of the target bounding box.

According to an embodiment, the multi-store tracker employs a 31-dimensional histogram of oriented gradients (HOG) as feature descriptors to detect the target. Specifically, the HOGs count occurrences of gradient orientation in localized portions of the image. Additionally, for color image sequences, additional 10-dimensional color attributes can be extracted to serve as complementary features, which are combined with the HOG descriptors to boost performance.
Thus, in order to perform translation estimation, the ICF determines a candidate image patch from the current image frame and extracts the HOG and color attributes features from the candidate patch. Note that the candidate patch is selected as the patch that is centered by the center of the target bounding box determined in the previous image frame. Further, upon determining the candidate image patch, the ICF evaluates the candidate image patch as well as all the cyclically shifted versions of the candidate image patch by using equation (4). Upon filtering the candidate image patch and its cyclic image patch versions, the position shift in the target (i.e., translation estimation) is performed by determining the location that has the highest filter response (i.e. a highest regression score).
Further, in order to address the scale-change issue of the detected target (object), a one-dimensional DSSCF can be trained to perform the second-stage filtering for scale estimation. According to one embodiment, a DSSCF is employed to perform scale estimation. Specifically, S image patches that are centered around the location found by the KCF filter are cropped from the image. Each of the cropped image patches has a size of asMT×asNT, where MT×NT is the current size of the target, a is a scalar factor, and sε




  
    {
    
      
        -
        
          
            S
            -
            1
          
          2
        
      
      ,
      ...
      ⁢
      
        
      
      ,
      
        
          S
          -
          1
        
        2
      
    
    }
  
  .




Further, all the S image patches are resized to the template size for feature extraction. The final output Bs from the short-term processing portion of the multi-store tracker is the image patch with the highest filtering response. It should be appreciated that similar to KCF, the model parameters of the DSSCF are also updated in an interpolating manner with a learning rate of μ.

One goal of the long-term processing portion 260 of the multi-store tracker 200 can be to conservatively learn the appearance of the target and to refresh the short-term memory when a mistake made by the short-term processing portion 250 of the multi-store tracker is detected. Further, Local Scale-Invariant Features (LSIFs), also referred to herein as key-points are used in the long-term processing portion of the multi-store tracker. Specifically, the long-term processing portion of the multi-store tracker performs key-point matching-tracking and RANSAC estimation in order to take advantage of the flexibility and shape generalizability of the key-point based appearance models.
The long-term memory of the target appearance can be modeled by a total feature database M=Γ∪B, that includes a foreground (target) feature database Γ and a background feature database B:

Γ={(di,pio)}i=1Nτ;B={di}i=1NB  (5)

Here, diεR128 is a 128-dimensional Scale-invariant Feature Transform (SIFT) descriptors of the key-points. NΓ and NB are the respective numbers of descriptors. Each target descriptor {di}εΓ is also associated with the corresponding coordinates pioεR2 that remember the keypoint location in the original target template, and can be used for estimating the transformation of target state. The background feature database enables a reduction in erroneous matching of target key-points and can help to detect the occlusions as described later.
In addition to the filtering function of ICF, another short-term procedure which can be conducted in the short-term store is to consecutively process the key-points by retrieving the long-term memory stored in Mand the short-term memory stored in an active set. In each frame, a SIFT detector that is based on the difference of Gaussians, is applied to an image search area to extract a set of key-points with large responses. The set of detected key-points associated with their SIFT descriptors is denoted as PD={(dk, pk)}k=1ND, where pkεR2 is the coordinates of the key-point.
The multi-store tracker 200 can perform key-point matching by searching the total memory database M for the nearest neighbors of each dkεPD, based on the Euclidean distance. A matching confidence of dk and its nearest neighbor dk1N is defined herein as the Cosine similarity C (dk, dk1N) between the two descriptors. The candidate matching keypoint can be found if the matching confidence is larger than a predefined threshold, denoted as θT for matching of target points and θB for matching of background points. Different threshold settings can be used to control the different recalls for the matching of foreground and background key-points. However, it should be appreciated that the matching of target points is significant since they are used to estimate the current state of the target. Thus, it is important to reject outliers during target point matching.
In order to further reject outliers, the multi-store tracker 200 can employ the distinct non-parametric nearest neighbor classifier by computing a ratio of the distances:




  
    
      
        
          r
          ⁡
          
            (
            
              d
              k
            
            )
          
        
        =
        
          
            d
            
              (
              
                
                  d
                  k
                
                ,
                
                  d
                  k
                  
                    1
                    ⁢
                    N
                  
                
              
              )
            
          
          
            d
            
              (
              
                
                  d
                  k
                
                ,
                
                  d
                  k
                  
                    2
                    ⁢
                    N
                  
                
              
              )
            
          
        
      
    
    
      
        (
        6
        )
      
    
  




where dk2N is the second nearest neighbor of dk. The matched point dk1N is classified as an inlier if the ratio of distances r(dk) is smaller than a threshold θr. Thus, the detected feature points (dk, pk)εPD, can be classified into one of the three following sets: the matched target key-points PT, the matched background key-points PB and unmatched key-points PN, as shown below:





  
    
      
        {
        
          
            
              
                
                  
                    p
                    k
                  
                  ∈
                  
                    P
                    T
                  
                
                ,
                
                  d
                  k
                  
                    1
                    ⁢
                    N
                  
                
              
            
            
              
                
                  ∈
                  
                    
                  
                  ⁢
                  Γ
                
                ,
                
                  
                    C
                    ⁡
                    
                      (
                      
                        
                          d
                          k
                        
                        ,
                        
                          d
                          k
                          
                            1
                            ⁢
                            N
                          
                        
                      
                      )
                    
                  
                  >
                  
                    θ
                    τ
                  
                
                ,
              
            
            
              
                
                  r
                  ⁡
                  
                    (
                    
                      d
                      k
                    
                    )
                  
                
                <
                
                  θ
                  τ
                
              
            
          
          
            
              
                
                  
                    p
                    k
                  
                  ∈
                  
                    
                  
                  ⁢
                  
                    P
                    B
                  
                
                ,
                
                  d
                  k
                  
                    1
                    ⁢
                    N
                  
                
              
            
            
              
                
                  ∈
                  
                    
                  
                  ⁢
                  B
                
                ,
                
                  
                    C
                    ⁡
                    
                      (
                      
                        
                          d
                          k
                        
                        ,
                        
                          d
                          k
                          
                            1
                            ⁢
                            N
                          
                        
                      
                      )
                    
                  
                  >
                  
                    θ
                    B
                  
                
              
            
            
              
                
              
            
          
          
            
              
                
                  
                    p
                    k
                  
                  ∈
                  
                    P
                    N
                  
                
                ,
              
            
            
              
                otherwise
                .
              
            
            
              
                
              
            
          
        
      
    
    
      
        (
        7
        )
      
    
  




The multi-store tracker, upon matching the target key-points (dk, Pk)εPT, extracts their corresponding coordinates pko from the original template and adds them to PT in order to obtain the complete form i.e., PT={(dk, pko, pk)}k=1Nm.
As stated previously, the multi-store tracker performs key-point matching-tracking and RANSAC estimation in the long short-term processing portion 260 of the multi-store tracker 200. The long short-term processing portion 260 interacts with a short-term memory of the multi-store tracker 200 using a forward-backward tracking technique. Specifically, the tracker maintains an active set of key-points PAt−1={(pi0, pit−1)}i=1NA, where pit−1 is the coordinates of the point in the t−1 frame and pio is the corresponding coordinates of pit−1 in the original template. Note that the active set of key-points can be regarded as the short-term memory of the multi-store tracker that provides additional information for performing the long short-term processing.
In order to obtain the coordinates of pit−1 in frame It, the multi-store tracker can employ the Lucas-Kanade (LK) method to determine the optical flow. Further, to increase robustness, the multi-store tracker can employ a Forward-Backward (FB) tracker to obtain a set of key-points with reliable tracking results. In the FB tracker, the forward optical flow from pit−1 to pit and the backward optical flow from pit to p∝it−1 are computed using two consecutive frames: It−1 and It. The displacement d(pit−1, p∝it−1) between pit−1 and p′it−1 is used to identify any tracking failures. Note that the displacement d(pit−1, p∝it−1) should be small if the tracking is successful. Accordingly, in one embodiment, for a predetermined threshold θfb, a failure in tracking is detected if d(pit−1, p∝it−1)>θfb. Thus, the multi-store tracker maintains a set of active key-points (PAt={(pio, pit)}pi=1N′A) that are successfully tracked by the FB tracker.
Once the matched and tracked key-points are obtained, a candidate set PC can be formed that includes key-points in PT and PAt. This set is used to estimate the state of the target. In estimating the state of the target, only similarity transformation is applied as it is more reliable than homography transformation for tracking generic objects. For the case of similarity transformation, the state of the target can be defined as st={xt; yt; st; βt}, which are the parameters of translations, scale, and rotation angle, respectively. To predict the target state st, a transformation Fst(pio)→pi can be estimated using PC={(pio, pi)}i=1NC. In order to avoid mistakes in matching and tracking key-points that may occur due to factors such as background clutter, rapid change in background, and the like, a RANSAC estimator is employed to compute the transformation. Specifically, according to one embodiment, the RANSAC estimator computes the transformation Fst by randomly proposing putative solutions and identifying inliers and outliers. Additionally, the MLESAC estimator that works by maximizing the likelihood, rather than just the number of inliers can also be used.
Upon estimating the resulting transformation Fst, a target bounding box Bl defined by the current state can be computed. A set of inlier key-points PI={(pi)}i=1NI, can also be obtained, where the number of inliers is important as they are evidence of a successful tracking operation. Specifically, the more inliers included in Fst, the more confident the result. Accordingly, a binary variable GC that indicates the tracking success can be set as:




  
    
      
        
          G
          C
        
        =
        
          {
          
            
              
                
                  True
                  ,
                
              
              
                
                  
                    N
                    I
                  
                  >
                  
                    θ
                    I
                  
                
              
            
            
              
                
                  False
                  ,
                
              
              
                
                  otherwise
                  ,
                
              
            
          
        
      
    
    
      
        (
        8
        )
      
    
  




where θl is a predefined threshold controlling recall strictness.

In an exemplary embodiment of the multi-store tracker of the present disclosure, the long-term memory is progressively updated on the fly. Thus, it is important to consider cases of occlusion, wherein the entire target cannot be tracked successfully. Accordingly, the multi-store tracker can be configured to compute a set P(Bl) which includes the key-points inside target bounding box Bl, and the set PO of occluding key-points, defined herein as the matched background key-points lying inside Bl, i.e., PO=P(Bl)∩PB.
If there is no occlusion, then the number of occluding points NO=|PO| is small i.e., close to zero. In contrast, when the target is occluded, the number of occluding key-points, NG=|PG|, is likely to be high and close to the number of key-points belonging to the target. In that case, the multi-store tracker computes the ratio of NO and NG and defines a binary variable GO that indicates occlusion occurrence as follows:




  
    
      
        
          G
          O
        
        =
        
          {
          
            
              
                
                  True
                  ,
                
              
              
                
                  
                    
                      N
                      O
                    
                    /
                    
                      N
                      G
                    
                  
                  >
                  
                    θ
                    o
                  
                
              
            
            
              
                
                  False
                  ,
                
              
              
                
                  otherwise
                  ,
                
              
            
          
        
      
    
    
      
        (
        9
        )
      
    
  




where PG=P(Bl)∩PT are the matched target key-points inside the region of Bl.

The active set PAt that stores the short-term memory can be updated at each image frame. It should be appreciated that the tracking of key-points when an occlusion is detected is detrimental as the key-points may gradually lock onto occluding objects or the background. Therefore, according to one embodiment, the multi-store tracker sets PAt=Φ (i.e., a null set) if GO is True, else it sets the active set PAt=Pl, which are the inliers found by the RANSAC estimator. However, when the target is stable or moving slowly, most of the key-points in the active set should be successfully tracked and identified as inliers, and meanwhile matched target key-points should be continually added to PAt.
In doing so, the active set PAt may be very large and thus prove to be computationally inefficient. Therefore, according to one embodiment, the multi-store tracker determines redundant points in PAt and lets the candidate set of RANSAC PC=PT ∪(PAt\PR), wherein PR denotes the set of redundant key-points. The redundant points can be found using the quantization IDs. Specifically, a virtual grid can be built upon the original target template, and each target key-point can be assigned a quantization ID according to its corresponding coordinates pio in the original template. Finally, the redundant points in PA can be determined by searching the repetitive quantization IDs in PT.
The use of key-points as the appearance model provisions for natural handling of in-plane rotation. However, it is important to update on the fly the appearance model to handle out-of-plane rotation, severe scale changes, and appearance variations of the target. To maintain relatively reliable memory of the target appearance, the memory database M is updated conservatively only when the short-term processing is confident about the result (i.e., GC=True) and claims there is no occlusion (GO=False). Note that both the target keypoint database r and the background keypoint database B need to be updated. Accordingly, in one embodiment, the multi-store tracker considers the unmatched points that are important for capturing any changes in visual structure. Specifically, during the update, the unmatched key-points that lie inside Bl are added to Γ, and the key-points that lie outside Bl are added to B, as follows:

Γ=Γ∪(PN∩P(Bl))

B=B∪(PN∩(PD\P(Bl))  (10)

Similar to the human brain that is good at remembering, as well as forgetting, the remembering-forgetting interplay helps the multi-store tracker to effectively manage the valuable and finite memory capacity when handling massive quantities of input signals. In order to avoid the unbounded growth of the memory database M, a certain capacity is set for Γ and B, and the features are forgotten over time. Specifically, according to one embodiment, a forgetting curve model is employed to maintain M and forget unimportant features according to the retention of features.
The forgetting curve hypothesizes a decline in memory retention and shows how information is lost over time when there is no attempt to retain it. The memory retention r over time can be modeled using an exponential function:




  
    
      
        r
        =
        
          exp
          ⁡
          
            (
            
              -
              
                τ
                
                  φ
                  ⁢
                  
                    
                  
                  ⁢
                  h
                
              
            
            )
          
        
      
    
    
      
        (
        11
        )
      
    
  




where h is the relative strength of the memory, τ is the relative period of forgetting, and φ is a constant controlling the scale of the timespan.

Note that the speed of decline in memory retention is decided by the relative strength h. Further, for information with high relative strength h, the decline in memory retention becomes slow and it is increasingly more possible to be remembered over time. The relative strength of information can be increased using techniques such as repetitive retrieving. According to one embodiment, in the multi-store tracker, each feature in diεM is assigned a set of memory variables (ri; τi; hi), where the memory retention ri of features can be updated according to their corresponding τi and hi values.
In order to model the process of forgetting, during each update term, all relative periods τi of diεM are increased by 1. Moreover, for the retrieved background features dk1N εB where dkεPB, and foreground features dk1N εT where dk εPT ∩Pl, the corresponding relative strength hi is increased by 1 and the relative period τi is set to 0. In doing so, the recalled features are renewed and strengthened in memory, while frequently recalled features obtain a high relative strength and are thus hard to forget. Once the number of features in the respective databases exceed a predefined memory capacity, NT>ΘT or NB>ΘB, the features with low retention are removed and completely forgotten by the multi-store tracker.
Upon completing the processing procedures performed in the short-term processing portion and the long short-term processing portion of the multi-store tracker, the results of filtering Bs (short-term processing portion) and the result of the long short-term processing Bl, together with the state variables GC and GO can be obtained by a controller. As stated previously, short-term filtering is accurate in relatively stable scenarios. Therefore, if the results of Bs and Bl are to some extent consistent (indicating that the long-term memory agrees with the output of the short term tracker), or the long-term component is not confident about the result (GC=False), or an occlusion is detected (GC=True), the tracking result Bo is output as Bo=Bs, and the short-term filters are updated using Bo and the predefined learning rates μ=μo and γ=γo.
If the results of Bs and Bl are inconsistent, the tracking result is output as Bo=R(Bl), where R(.) is a function for rotating a bounding box along its center and in the same orientation as Bs. Moreover, the short-term memory is refreshed using Bo to update the short-term filters and the learning rates for γ and μ are set at 1. In doing so, the multi-store tracker cleans up all the previous short-term memory stored in the filters. In particular, according to one embodiment, the inconsistency of Bs and Bl are detected by the Intersection Over Union (IOU) metric




  
    U
    ⁡
    
      (
      
        
          B
          s
        
        ,
        
          B
          l
        
      
      )
    
  
  =
  
    
    
      
        
          B
          s
        
        ⋂
        
          B
          l
        
      
      
        
          B
          s
        
        ⋃
        
          B
          l
        
      
    
    
  




with a threshold of θU. The IOU metric may be defined to have a value in the range from (0-1). Furthermore, the output of the short term processing portion and the output of the long short-term processing portion may be determined to be inconsistent when the computed IOU metric is below the threshold θU.

FIG. 3 illustrates an exemplary flowchart depicting the steps performed by the multi-store tracker to track an object. The multi-store tracker includes a first object tracker and a second object tracker, which are respectively implemented by circuitry and work in a collaborative fashion to track the object. Specifically, the multi-store tracker includes a first tracker that is implemented in the short-term processing portion (denoted as 250 in FIG. 2) and a second tracker that is implemented in the long short-term processing portion (260 in FIG. 2) of the multi-store tracker framework.
In step S310, an input image frame is processed by the first tracker, wherein image features based on HOG descriptors (and color attributes) are extracted from a candidate image patch of the current image frame. The function of extracting the HOG descriptors from the image patches can be performed by the feature extraction circuit (block 203) of FIG. 2.
The first tracker evaluates the candidate image patch as well as cyclically shifted versions (image patches) of the candidate image patch. Further, the tracker evaluates the filtering response of the image patches in order to determine a location that has the highest filtering response. For instance, an integrated correlation filter (ICF), depicted as filtering circuitry (block 205 in FIG. 2) can be used to perform the filtering operation.
Subsequently, in step S320, the first tracker performs scale estimation of the tracked object. For instance, as stated previously, a DSSCF can be used for resizing a predetermined number of image patches that surround the location of the object as determined in step S310. Further, the first tracker outputs a first instance of the tracked object that is included in an image patch with the highest filtering response evaluated by the DSSCF.
The process further proceeds to step S330 wherein, a plurality of key-points from an input image frame are detected. According to an embodiment of the present disclosure, the key-points can be detected by the key-point detection circuit (block 209 in FIG. 2) included in the long short-term processing portion of the multi-store tracker. Further, the key-points may be characterized by SIFT descriptors that describe local features of the image.
In step S340, the detected key-points of step S330 are classified into one of a matched target key-point, matched background key-point, and an unmatched key-point. According to an embodiment of the present disclosure, the function of classification of the key-points can be performed by the matching circuit (block 211 in FIG. 2). Specifically, the classification of the key-points is performed based on a key-point database that includes a foreground (target) database and a background database. The foreground and background key-points are stored in the foreground database and background database, respectively.
Further, a detected key-point can be classified as a matched target key-point when a matching confidence of the detected key-point and a first nearest neighbor (included in the foreground database) of the detected key-point is above a predetermined threshold. In addition to the matching confidence, a ratio of distances parameter can be used to classify the detected key-point as a matched target key-point. Specifically, when the ratio of distances parameter (defined herein as a ratio of Euclidean distance of the detected key-point and the first nearest neighbor to the Euclidean distance of the detected key-point and the second nearest neighbor) is below a predetermined threshold, then the detected key-point can be classified as a matched target key-point. It should be appreciated that similar to the mechanism of classifying a detected foreground key-point, a detected background key-point can be classified as a matched background key-point as shown in equation (7).
The process then proceeds to step S350, wherein the key-point tracking circuit (block 213 in FIG. 2) computes an active set of key-points. The active set of key-points is computed based on consecutive input image frames. Specifically, the active set of key-points includes key-points whose coordinate displacement between the consecutive image frames is less than a predetermined threshold.
Upon computing the active set of key-points (step S350) and the matched target key-points (step S340), a RANSAC estimation circuit (block 215 in FIG. 2) determines inlier key-points that lie in a target bounding box (step S360). Note that the target bounding box corresponds to the tracked object as determined by the second tracker.
The process in step S370 generates an output response for object tracking. Specifically, the controller (block 217 in FIG. 2), that is implemented by circuitry, determines an output of the multi-store tracker (i.e., a tracked object), based on the consistency of the tracked object as determined by the first tracker and the second tracker, respectively. The process terminates after generating the tracked object. It must be appreciated that the steps of the flowchart as depicted in FIG. 3 are in no way restricted to be performed in a sequential manner. Specifically, according to an embodiment, the circuitry may perform the functions depicted in steps S310-S320, and the functions depicted in steps S330-S370 in a parallel manner.
Additionally, the circuitry of the multi-store tracker can be configured to update (for each input image frame) the active set of key-points that is used by the long short-term processing portion of the multi-store tracker. Specifically, the active set of key-points is updated by computing a redundant set of key-points based on quantization ID's and removing the computed redundant set from the active set of key-points.
Further, the circuitry of the multi-store tracker can be configured to update the key-point database when the number of inlier key-points (as estimated by the RANSAC estimator) is above a predetermined threshold and the number of matched background key-points lying within the target bounding box is close to zero i.e., there is no object occlusion.
The performance of the multi-store tracker can be determined by simulating the multi-store tracker on a computer system. The computer system may include special purpose logic devices (e.g., application specific integrated circuits (ASICs)) or configurable logic devices (e.g., simple programmable logic devices (SPLDs), complex programmable logic devices (CPLDs), and field programmable gate arrays (FPGAs)). The computer system may be configured to execute software such as Matlab, C++ and the like.
In one instance, the parameters for the multi-store tracker were set as follows: θU=0, the learning rate μo and γo for the ICF are set to 0.01 and 0.02 respectively, and the padding size p in KCF is set to 1. The thresholds for matching key-points are set as θT=0.8, θB=0.9, θr=0.85, and θl/=8. The threshold θfb for FB Tracker is set to 4. The parameter φ in the forgetting curve model is set to 10, while the memory capacities ΘT and ΘB of the keypoint databases are both set to 2000.
The multi-store tracker can be evaluated on the Online Object Tracking Benchmark (OOTB): CVPR2013. The performance of the multi-store tracker is compared to a plurality of trackers (described below). The robustness of the trackers is compared based on two different metrics: the precision plot and the success plot. The precision plot corresponds to the percentage of successfully tracked frames on which the Center Location Error (CLE) of a tracker is within a given threshold TC. Further, a representative precision score at TC=20 is used for ranking the trackers. The success plot counts the percentage of successfully tracked frames, by measuring the Intersection Over Union (IOU) metrics for trackers on each frame. In one embodiment, for the success plot, the threshold of IOU is varied from 0 to 1, and the ranking of trackers is based on an Area Under Curve (AUC) score.
The performance of the multi-store tracker can be compared to twenty-nine (29) trackers whose performance results are available in OOTB. Specifically, the performance of the multi-store tracker (referred to herein as MUSTer) is compared to trackers such as: Structured output tracking with kernels (STRUCK), tracking learning detection (TLD), Sparsity based collaborative model tracker (SCM), Adaptive structural local sparse appearance model tracker (ASLA), visual tracking decomposition tracker (VTD), tracking by sampling trackers (VTS) and Multiple expert entropy minimization tracker (MEEM). Further, the performance of MUSTer can also be compared to correlation filter-based trackers CN, KCF, and DSST, as well as an integrated correlation filter (ICF) tracker so as to demonstrate the importance of the long-term tracking component in MUSTer.
FIGS. 4A and 4B depict graphs illustrating performance of the multi-store tracker compared to other trackers. Specifically, FIG. 4A illustrates a graph depicting precision plots of the trackers and FIG. 4B illustrates a graph depicting success plots of the trackers that correspond to the percentage of successfully tracked frames.
In FIG. 4A, the curve 400 corresponds to the performance of MUSTer while curves 420-428 correspond to the performance of MEEM, ICF, KCF, DSST, CN, Struck, SCM, TLD, and VTS trackers, respectively. In FIG. 4B, the curve 450 corresponds to the performance of MUSTer, while curves 460-468 correspond to the performance of MEEM, ICF, DSST, KCF, SCM, Struck, CN, TLD, and ASLA trackers, respectively. Note that as stated previously, the performance of MUSTer is compared to the performance of twenty-nine (29) trackers that are available in OOTB. However, for the sake of clarity, only the performance of the top ten trackers is depicted in FIGS. 4A and 4B.
FIGS. 4A and 4B indicate that MUSTer achieves the overall best performance using both the metrics (precision and success plot), and significantly outperforms the second best tracker (MEEM) with an 11% performance gain using the metric of the AUC score. The AUC scores of the trackers for the precision plot and success plot are depicted below in Tables I and II, respectively. It should be appreciated that the AUC score that measures the overall performance in a success plot is more accurate than the precision score at one threshold of a precision plot. Accordingly, the results as depicted in FIGS. 4A and 4B clearly demonstrate the superior performance of MUSTer. Additionally, MUSTer also significantly outperforms the baseline short-term component ICF tracker, other correlation filter based trackers (DSST and KCF), and the long-term tracker TLD, thereby validating the important role of the long-term component in MUSTer and the effectiveness of the MUSTer framework that is based on ASMM. In other words, FIGS. 4A and 4B illustrate the benefit of incorporating a short-term, as well as a long term component in the MUSTer framework that collaboratively process the input image to track the object.







TABLE I







Performance score for quantitative comparison of precision (TC = 20).
















MUSTer
MEEM
ICF
KCF
DSST
CN
Struck
SCM
TLD
VTS





0.865
0.835
0.767
0.740
0.737
0.661
0.656
0.649
0.608
0.575
















TABLE II







Performance score for quantitative comparison of success plots (AUC).
















MUSTer
MEEM
ICF
DSST
KCF
SCM
Struck
CN
TLD
ALSA





0.641
0.576
0.572
0.554
0.514
0.499
0.474
0.453
0.437
0.434









The performance of MUSTer was also evaluated on the ALOV++ (Amsterdam Library of Ordinary Videos) platform. ALOV++ includes fourteen (14) challenge subsets, and a total of three hundred fifteen (315) sequences that are used to systematically evaluate a trackers' robustness for a large variety of situations including light changes, low contrast, occlusion and the like. In order to evaluate the performance of the trackers, a survival score that is based on an F-score is computed in order to evaluate the trackers' robustness. To obtain the survival score of a tracker, the F-score for each video is computed as:

F=2(precision×recall)/(precision+recall)  (12)

wherein, the parameters precision and recall are computed as: precision=ntp/(ntp+nfp), and recall=ntp/(ntp+nfn), and ntp, nfp, nfn respectively denote the number of true positives, false positives and false negatives in a video. Note that the survival curve shows the performance of a tracker on all videos in the dataset.

The performance of MUSTer was compared to the performance of nineteen (19) trackers. FIG. 5 depicts the performance (F-score) of the MUSTer compared to the following nine (9) trackers: MEEM tracker, a foreground-background texture discriminating (FBT) tracker, VTS tracker, TLD tracker, L1O tracker (i.e., an L1 tracker with occlusion detection), normalized cross-correlation tracker (NCC), multiple instance learning (MIL) tracker, and L1T tracker (i.e., a tracker employing sparse representation). Note that in the graph of FIG. 5, for the sake of clarity, only the performance of the top 10 trackers is depicted.
In FIG. 5, curve 500 depicts the performance of MUSTer, while curves 510-518 depict the performance of the Struck, MEEM, FBT, VTS, TLD, L1O, NCC, MIL, and L1T tracker's, respectively. The results depicted in FIG. 5 indicate that MUSTer achieves the best overall performance as compared to the other trackers. Further, as depicted in Table III below, the average F-score of MUSTer on ALOV++ is 0.73, which is significantly better than Struck (0.66), MEEM (0.65), TLD (0.61) and the other trackers.







TABLE III







Average F-scores of trackers over 315 video sequences.
















MUSTer
Struck
MEEM
FBT
VTS
TLD
L10
NCC
MIL
L1T





0.73
0.66
0.65
0.64
0.62
0.61
0.60
0.57
0.57
0.56









Each of the functions of the described embodiments may be implemented by one or more processing circuits. A processing circuit includes a programmable processor (for example, processor 603 in FIG. 6). A processing circuit also can be embodied as an application-specific integrated circuit (ASIC) and conventional circuit components arranged to perform the recited functions.
The various features discussed above may be implemented by a computer system (or programmable logic). FIG. 6 illustrates such a computer system 601. The computer system 601 of FIG. 6 may be a general-purpose computer or a particular, special-purpose machine. In one embodiment, the computer system 601 is a particular, special-purpose machine when the processor 603 is programmed to perform object tracking.
The computer system 601 includes a disk controller 606 coupled to the bus 602 to control one or more storage devices for storing information and instructions, such as a magnetic hard disk 607, and a removable media drive 608 (e.g., floppy disk drive, read-only compact disc drive, read/write compact disc drive, compact disc jukebox, tape drive, and removable magneto-optical drive). The storage devices may be added to the computer system 601 using an appropriate device interface (e.g., small computer system interface (SCSI), integrated device electronics (IDE), enhanced-IDE (E-IDE), direct memory access (DMA), or ultra-DMA).
The computer system 601 may also include special purpose logic devices (e.g., application specific integrated circuits (ASICs)) or configurable logic devices (e.g., simple programmable logic devices (SPLDs), complex programmable logic devices (CPLDs), and field programmable gate arrays (FPGAs)).
The computer system 601 may also include a display controller 609 coupled to the bus 602 to control a display 610, for displaying information to a computer user. The computer system includes input devices, such as a keyboard 611 and a pointing device 612, for interacting with a computer user and providing information to the processor 603. The pointing device 612, for example, may be a mouse, a trackball, a finger for a touch screen sensor, or a pointing stick for communicating direction information and command selections to the processor 603 and for controlling cursor movement on the display 610.
The processor 603 executes one or more sequences of one or more instructions contained in a memory, such as the main memory 604. Such instructions may be read into the main memory 604 from another computer readable medium, such as a hard disk 607 or a removable media drive 608. One or more processors in a multi-processing arrangement may also be employed to execute the sequences of instructions contained in main memory 604. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions. Thus, embodiments are not limited to any specific combination of hardware circuitry and software.
As stated above, the computer system 601 includes at least one computer readable medium or memory for holding instructions programmed according to any of the teachings of the present disclosure and for containing data structures, tables, records, or other data described herein. Examples of computer readable media are compact discs, hard disks, floppy disks, tape, magneto-optical disks, PROMs (EPROM, EEPROM, flash EPROM), DRAM, SRAM, SDRAM, or any other magnetic medium, compact discs (e.g., CD-ROM), or any other optical medium, punch cards, paper tape, or other physical medium with patterns of holes.
Stored on any one or on a combination of computer readable media, the present disclosure includes software for controlling the computer system 601, for driving a device or devices for implementing the features of various embodiments described herein, and for enabling the computer system 601 to interact with a human user. Such software may include, but is not limited to, device drivers, operating systems, and applications software. Such computer readable media further includes the computer program product of the present disclosure for performing all or a portion (if processing is distributed) of the processing performed in implementing any portion of the invention.
The computer code devices of the present embodiments may be any interpretable or executable code mechanism, including but not limited to scripts, interpretable programs, dynamic link libraries (DLLs), Java classes, and complete executable programs. Moreover, parts of the processing of the present embodiments may be distributed for better performance, reliability, and/or cost.
The term “computer readable medium” as used herein refers to any non-transitory medium that participates in providing instructions to the processor 603 for execution. A computer readable medium may take many forms, including but not limited to, non-volatile media or volatile media. Non-volatile media includes, for example, optical, magnetic disks, and magneto-optical disks, such as the hard disk 607 or the removable media drive 608. Volatile media includes dynamic memory, such as the main memory 604. Transmission media, on the contrary, includes coaxial cables, copper wire and fiber optics, including the wires that make up the bus 602. Transmission media also may also take the form of acoustic or light waves, such as those generated during radio wave and infrared data communications.
Various forms of computer readable media may be involved in carrying out one or more sequences of one or more instructions to processor 603 for execution. For example, the instructions may initially be carried on a magnetic disk of a remote computer. The remote computer can load the instructions for implementing all or a portion of the present disclosure remotely into a dynamic memory and send the instructions over a telephone line using a modem. A modem local to the computer system 601 may receive the data on the telephone line and place the data on the bus 602. The bus 602 carries the data to the main memory 604, from which the processor 603 retrieves and executes the instructions. The instructions received by the main memory 604 may optionally be stored on storage device 607 or 608 either before or after execution by processor 603.
The computer system 601 also includes a communication interface 613 coupled to the bus 602. The communication interface 613 provides a two-way data communication coupling to a network link 614 that is connected to, for example, a local area network (LAN) 615, or to another communications network 616 such as the Internet. For example, the communication interface 613 may be a network interface card to attach to any packet switched LAN. As another example, the communication interface 613 may be an integrated services digital network (ISDN) card. Wireless links may also be implemented. In any such implementation, the communication interface 613 sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.
The network link 614 typically provides data communication through one or more networks to other data devices. For example, the network link 614 may provide a connection to another computer through a local network 615 (e.g., a LAN) or through equipment operated by a service provider, which provides communication services through a communications network 616. The local network 614 and the communications network 616 use, for example, electrical, electromagnetic, or optical signals that carry digital data streams, and the associated physical layer (e.g., CAT 5 cable, coaxial cable, optical fiber, etc.). The signals through the various networks and the signals on the network link 614 and through the communication interface 613, which carry the digital data to and from the computer system 601 may be implemented in baseband signals, or carrier wave based signals.
The baseband signals convey the digital data as unmodulated electrical pulses that are descriptive of a stream of digital data bits, where the term “bits” is to be construed broadly to mean symbol, where each symbol conveys at least one or more information bits. The digital data may also be used to modulate a carrier wave, such as with amplitude, phase and/or frequency shift keyed signals that are propagated over a conductive media, or transmitted as electromagnetic waves through a propagation medium. Thus, the digital data may be sent as unmodulated baseband data through a “wired” communication channel and/or sent within a predetermined frequency band, different than baseband, by modulating a carrier wave. The computer system 601 can transmit and receive data, including program code, through the network(s) 615 and 616, the network link 614 and the communication interface 613. Moreover, the network link 614 may provide a connection through a LAN 615 to a mobile device 617 such as a personal digital assistant (PDA) laptop computer, or cellular telephone.
While aspects of the present disclosure have been described in conjunction with the specific embodiments thereof that are proposed as examples, alternatives, modifications, and variations to the examples may be made. It should be noted that, as used in the specification and the appended claims, the singular forms “a,” “an,” and “the” include plural referents unless the context clearly dictates otherwise.

## Claims

1. An object tracking device comprising:
a first tracker implemented by circuitry, the circuitry configured to:
determine and extract features, of a candidate image patch from an input image frame,
evaluate the candidate image patch and cyclically shifted image patches of the candidate image patch, to determine a location of a tracked object;
resize and extract features from a predetermined number of image patches surrounding the determined location to obtain a first instance of the tracked object;

a second tracker implemented by circuitry, the circuitry configured to:
detect a plurality of key-points from the input image frame,
classify, based on a key-point database, each detected key-point as one of a matched target key-point, a matched background key-point, and an unmatched key-point,
compute, based on consecutive input image frames, an active set of key-points,
estimate, based on the computed active set of key-points and the matched target key-points, a set of inlier key-points included in a target bounding box that corresponds to a second instance of the tracked object; and

a controller implemented by circuitry, the circuitry being configured to generate a tracked object based on a comparison of the first instance of the tracked object and the second instance of the tracked object.

2. The object tracking device of claim 1, wherein the determined location of the tracked object has a highest filtering score, and the first instance of the tracked object is included in an image patch having a highest filter response.

3. The object tracking device of claim 2, wherein the circuitry is further configured to:
update the filter coefficients and an object template in an interpolating fashion at a predetermined update rate.

4. The object tracking device of claim 1, wherein the extracted features are based on a histogram of oriented gradient descriptors and color attributes, and the detected key-points are characterized by scale-invariant-feature-transform descriptors.

5. The object tracking device of claim 1, wherein the circuitry of the controller is configured to classify the detected key-point as a matched target key-point based on a matching confidence of the detected key-point and a first neighbor of the detected keypoint that belongs to the key-point database being above a first threshold.

6. The object tracking device of claim 5, wherein the circuitry of the controller is further configured to classify the detected key-point as a matched target key-point based on a ratio of distance parameter being below a second threshold, the ratio of distance parameter being a ratio of the Euclidean distance between the detected key-point and the first nearest neighbor to the Euclidean distance between the detected key-point and the second nearest neighbor.

7. The object tracking device of claim 5, wherein the matching confidence is a cosine similarity between the detected key-point and the first nearest neighbor of the detected key-point.

8. The object tracking device of claim 1, wherein the active set of key-points includes key-points whose displacement between the consecutive input image frames is less than a predetermined threshold.

9. The object tracking device of claim 1, wherein the circuitry of the controller is further configured to
compute an intersection-over-union (IOU) of the first instance of the tracked object and the second instance of the tracked object; and
determine whether the first instance of the tracked object and the second instance of the tracked object are consistent based on the computed IOU and a predetermined consistency threshold.

10. The object tracking device of claim 1, wherein the circuitry of the controller is further configured to:
update the active set of key-points for each input image frame by determining a redundant set of key-points within the active set of key-points, the redundant set of key-points being computed based on quantization ID's of the key-points; and
update the key-point database based on a number of inlier key-points being greater than a predetermined threshold and a number of matched background key-points lying within the target bounding box being zero.

11. The object tracking device of claim 10, wherein a timespan corresponding to an amount of time the key-points are maintained in the key-point database is exponentially distributed based on a relative strength parameter of the key-point database, a period of a forgetting parameter, and a scale of a timespan parameter.

12. A method of object tracking comprising:
determining, and extracting features of a candidate image patch, from an input image frame;
evaluating by circuitry, the candidate image patch and cyclically shifted image patches of the candidate image patch, to determine a location of a tracked object;
resizing, and extracting features, from a predetermined number of image patches surrounding the determined location to obtain a first instance of the tracked object;
detecting a plurality of key-points from the input image frame;
classifying, based on a key-point database, each detected key-point as one of a matched target key-point, a matched background key-point, and an unmatched key-point,
computing by circuitry, based on consecutive input image frames, an active set of key-points;
estimating, based on the computed active set of key-points and the matched target key-points, a set of inlier key-points included in a target bounding box that corresponds to a second instance of the tracked object; and
generating by circuitry, a tracked object based on a comparison of the first instance of the tracked object and the second instance of the tracked object.

13. The method of object tracking of claim 12, wherein the determined location of the tracked object has a highest filtering score, and the first instance of the tracked object is included in an image patch having a highest filter response.

14. The method of object tracking of claim 12, further comprising:
updating the filter coefficients and an object template in an interpolating fashion at a predetermined update rate.

15. The method of object tracking of claim 12, wherein the circuitry is configured to classify the detected key-point as a matched target key-point based on a matching confidence of the detected key-point and a first neighbor of the detected keypoint that belongs to the key-point database being above a first threshold.

16. The method of object tracking of claim 15, wherein the circuitry is further configured to classify the detected key-point as a matched target key-point based on a ratio of distance parameter being below a second threshold, the ratio of distance parameter being a ratio of the Euclidean distance between the detected key-point and the first nearest neighbor to the Euclidean distance between the detected key-point and the second nearest neighbor.

17. The method of object tracking of claim 12, further comprising:
computing by circuitry, an intersection-over-union (IOU) of the first instance of the tracked object and the second instance of the tracked object; and
determining whether the first instance of the tracked object and the second instance of the tracked object are consistent based on the computed IOU and a predetermined consistency threshold.

18. A non-transitory computer readable medium having stored thereon a program that when executed by a computer causes the computer to execute a method to track an object, the method comprising:
determining, and extracting features of a candidate image patch, from an input image frame;
evaluating the candidate image patch and cyclically shifted image patches of the candidate image patch, to determine a location of a tracked object;
resizing and extracting features, from a predetermined number of image patches surrounding the determined location to obtain a first instance of the tracked object;
detecting a plurality of key-points from the input image frame;
classifying, based on a key-point database, each detected key-point as one of a matched target key-point, a matched background key-point, and an unmatched key-point;
computing based on consecutive input image frames, an active set of key-points;
estimating, based on the computed active set of key-points and the matched target key-points, a set of inlier key-points included in a target bounding box that corresponds to a second instance of the tracked object; and
generating a tracked object based on a comparison of the first instance of the tracked object and the second instance of the tracked object.

19. The non-transitory computer readable medium of claim 18, wherein the determined location of the tracked object has a highest filtering score, and the first instance of the tracked object is included in a first image patch having a highest filter response.

20. The non-transitory computer readable medium of claim 18, the method further comprising:
computing an intersection-over-union (IOU) of the first instance of the tracked object and the second instance of the tracked object; and
determining whether the first instance of the tracked object and the second instance of the tracked object are consistent based on the computed IOU and a predetermined consistency threshold.

21. The object tracking device of claim 1, wherein each image patch of the predetermined number of image patches surrounding the determined location has a unique size.