Abstract:
A collaborative distance metric leaning method and apparatus for visual tracking utilizes a distance metric to match the target with the best candidate. A collaborative distance metric learning algorithm is used for visual tracking by fusing two distance metrics learnt for different representations of the target. To further improve the performance of the trained distance metrics, a sample selection mechanism is also used that exploits the intrinsic structure of dense sampling.

Description:
BACKGROUND 
     Visual tracking is a fundamental problem in computer vision, with many applications involved in various fields, such as motion analysis, human computer interaction, robot perception and traffic monitoring, etc. While much progress has been made in recent years, there still exist many challenges in designing a robust visual tracking algorithm, which are mainly caused by varying illumination, camera motion, occlusions, pose variation and rotation. 
     One of the issues in visual tracking is to match the target&#39;s visual appearances over consecutive video frames. Similar to many other computer vision problems such as image retrieval and object recognition, the matching process is largely stipulated by the coaction of the appearance model of the target that describes the target with unpredictable variations due to complex and dynamic scenes and the distance metric that determines the matching relations, e.g., the candidates with the target in visual tracking, or the whole image set with the query image in image retrieval domain. 
     Distinct from those retrieval or recognition tasks, a tracking problem holds a uniqueness that the appearance model and distance metric are both required to be adaptive to the changes of target as well as background over video frames. 
     The appearance model of the target plays a big role in visual tracking. In other words, if a strong appearance model can be constructed which is invariant to illumination changes and local deformation, discriminative from the background, and capable of handling occlusions, even simple and fixed distance metric like the Euclidean distance results in favorable matching performance. However, respectable difficulties arise to obtain a good appearance model which is able to handle the difficulties mentioned above. Although many excellent models are designed to describe the target in recent years, few algorithms can deal with various challenges at once. They usually only focus on solving certain tracking issues. When strong appearance model cannot be easily accessed, the choice of distance metrics for visual tracking becomes particularly critical. Many recent researches explored single distance metric learning in tracking problem and obtained pleasant results. 
     Recently, more and more tracking algorithms in collaborative framework achieve satisfactory performances. These approaches are all based on a simple motivation that single description of the object has its limitation in object representation and may lose helpful discriminative information for matching. 
     SUMMARY 
     One aspect of the present method includes (1) a distance metric fusion framework for visual tracking and (2) an effective samples selection mechanism in a distance metric learning process. 
     The method includes tracking a target object in sequential frames of images containing the target object including determining a target image depicting a first tracking position associated with a target object in one frame of an image sequence; generating, by a processor, a plurality of sample windows about the first tracking position of the target object by using sliding windows; classifying, by the processor, image targets in the sliding windows by Gaussian Kernel Regularized Least Square; collecting all sub-windows; computing sub-window scores; creating, by the processor, a negative sample set; creating two weight graphs of the template and target candidates with node links; calculating, by the processor, a distance metric fusion by cross diffusion; and tracking an object to the sequential frames of images using a collaborative distance metric. 
     The step of collecting all sub-windows can be performed by a sliding window process. 
     The step of computing sub-windows scores can include selecting samples with a higher response score. 
     The step of generating a distance metric fusion by cross diffusion includes generating, by the processor, two finite weighted graphs with target candidates and the template as vertices and links between pairs of nodes as edges; and fusing two graphs by cross diffusion. 
     The method further includes constructing an affinity matrix using K nearest neighbors method where K is a constant. 
     The method can further include constructing, by the processor, a weighted identity matrix, a plurality of status matrices; and choosing the arithmetic average of two status matrices generated in the last iteration as a final decision matrix. 
     The step of tracking with a collaborative distance metric uses a RGB-doublet-SVM to project a RGB histogram to a doublet-SVM distance metric state. 
     The method further includes training a doublet-SVM distance metric and a max-pooling distance metric by positive and negative samples. 
     The method can include selecting a candidate in the decision matrix having the largest value as a final tracking result of the target object in the current image frame. 
     An apparatus for tracking an object over a plurality of sequential image frames includes an image sensor generating a plurality of sequential image frames of a target object in a field of view of the image sensor and outputting the sequential image frames by a processor receives the sequential image frames from the image sensors. The processor executes program instructions for determining a target image depicting a first tracking position associated with a target object in one frame of an image sequence; generating, by the processor, a plurality of sample windows about the first tracking position of the target object by using sliding windows; classifying, by the processor, image targets in sliding windows by Gaussian Kernel Regularized Least Square; collecting all sub-windows; computing sub-window scores; creating, by the processor, a negative sample set; creating two weight graphs of the template and target candidates with node links; calculating, by the processor, a district metric fusion by cross diffusion; and tracking an object to the sequential frames of images using a collaborating distance metric. 
     The processor can collect all sub-windows by a sliding window process. 
     The processor can compute sub-windows scores including selecting samples with a higher score. 
     The processor generates a distance metric fusion by cross diffusion including generating, by the processor, two finite weighted graphs with the template and target candidates as vertices and links between pairs of nodes as edges, and fusing two graphs by cross diffusion. 
     The processor constructs an affinity matrix using a K nearest neighbors method where K is a constant. 
     The processor constructs a weighted identity matrix, a plurality of status matrices, and chooses the arithmetic average of two status matrices generated in the last iteration as a final decision matrix. 
     The processor tracks a collaborative distance metric using a RGB-doublet-SVM to project a RGB histogram to a doublet-SVM distance metric state. 
     The processor trains a doublet-SVM distance metric and a max-pooling distance metric by positive and negative samples. 
     The processor selects a candidate in the decision matrix having the largest value as a final tracking result of the target object in the current image frame. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWING 
       The various features, advantages and other uses of the present method and apparatus will become more apparent by referring to the following detailed description and drawing in which: 
         FIG. 1  is a pictorial representation of the present method and apparatus tracking one or more detected vehicles in the path of a viewing vehicle; 
         FIG. 2  is a block diagram of a computing device for implementing the disclosed method and forming part of the disclosed apparatus; 
         FIG. 3  is a flow chart depicting the method sequence; 
         FIGS. 4A-4E  are sequential image frames captioned by an image sensor; 
         FIGS. 5A and 5B  are images of sample target windows in one image frame; 
         FIG. 6  is a pictorial representation of the application of sliding windows to image frames; 
         FIG. 7  is a graph depicting image classifications; 
         FIG. 8  is a pictorial representation of the application of sub-windows to an image frame; 
         FIG. 9  is a weight graph; 
         FIG. 10A  is another example of a weighted identity matrix; 
         FIG. 10B  is a pictorial representation of an affinity matrix based on the weighted identity matrix shown in  FIG. 10A ; 
         FIG. 11A  is a pictorial representation of one image frame; 
         FIG. 11B  is an RGB Histogram of the image shown in  FIG. 11A ; and 
         FIG. 11C  is a graph depicting a max-pooling metric using the RGB histogram of  FIG. 11B . 
     
    
    
     DETAILED DESCRIPTION 
     Referring now to the drawing, and to  FIGS. 1-3  in particular, there is depicted an object tracking apparatus useful in implementing an object tracking method using comparative distance metric learning. 
     The apparatus, which can be mounted, for example, on a moving vehicle  80 , includes an image sensor or camera  82 . By way of example, the camera  82  may be a high definition video camera with a resolution of 1024 pixels per frame. 
     The camera  82 , in addition to possibly being a high definition camera  82 , for example, can also be a big-picture/macro-view (normal or wide angle) or a telephoto camera. Two types of cameras, one having normal video output and the other providing a big-picture/macro-view normal or wide angle or telephoto output, may be employed on the vehicle  80 . This would enable one camera to produce a big-picture/macro view, while the other camera could zoom in on parts of the target. 
     The apparatus, using the image sensor or camera  82  and the control system described hereafter and shown in  FIG. 2 , detects an object, such as vehicle  84 , and/or vehicle  85 , described hereafter as detected objects by example, on a roadway  86  to the front, side or even, in some applications, to the rear of the vehicle  80  within the field of view  88  of the camera  82 . 
     The method can be implemented by the apparatus which includes a computing device  100  shown in a block diagram form in  FIG. 2 . The computing device  100  can be any type of computing device, including a handheld, desktop, or other form of single computing device, or it can be formed of multiple computing devices. A CPU  102  in the computing device  100  can be a conventional central processing unit or any other type of device, or multiple devices, capable of manipulating or processing information. A memory  104  in the computing device  100  can be a Random Access Memory device (RAM) or any other suitable type of storage device. The memory  104  can include data  106  that is accessed by the CPU  102  using a bus  108 . The memory  104  can also include an operating system  110  and installed applications  112 . The installed applications  112  include programs that permit the CPU  102  to perform the object tracking method described herein. 
     The computing device  100  can also include secondary, additional, or external storage  114 , for example, a memory card, flash drive, or other forms of computer readable medium. The installed applications  112  can be stored in whole or in part in the secondary storage  114  and loaded into the memory  104  as needed for processing. 
     The computing device  100  can be mounted on the vehicle  80  or situated remote from the vehicle  80 . In the latter case, remote communication will be used between the camera  82  and the computing device  100 . 
     The computing device  100  receives an input in the form of sequential video frame image data  116  from the image sensor or camera  82  mounted on the vehicle  80 . The video image data  116  may be stored in the memory  104  and/or the secondary storage  114 . 
     Using a high definition output  116  from the camera  82 , the target will have a reasonable size, as shown in  FIGS. 4A-4E , to enable the segmentation of meaningful parts from the vehicles  84  or  85  with a reasonable size to implement tracking. 
       FIGS. 4A-4E  are successive image frames showing the continued movement of objects or vehicles  84  and  85  across the front of the viewing vehicle  80 . For example, if a license plate is segmented as one part and tracked, the license plate can provide a unique identification of the vehicle  84  or  85  as long as it has enough resolution to be successfully tracked. As another example, many vehicles can be tracked by relying on their unique shapes or styling features, such as front grills, lights, manufacture logos, etc. 
     The presently disclosed object tracking method and apparatus uses an algorithm where a matching process plays a role in which the performance relies on the selected distance metric for matching one-step further. The matching process in a tracking problem is formulated as:
 
min i   d   2 ( t,c   i )  (1)
 
     where t is the target&#39;s appearance model and c i  is the i th  target candidate&#39;s appearance model in the current image frame. d(•, •) is the distance function measured by the distance metric. Here, the form of Mahalanobis distance is used to represent the distance function as following by introducing a measure matrix M:
 
 d   2 ( t,c   i )=∥ t−c   i ∥ M≧0   2 =( t−c   i ) T   M ( t−c   i )  (2)
 
     Since M is symmetric and positive semi-definite, the Eq. 2 can be rewritten as:
 
 d   2 =( t−c   i ) T   AA   T ( t−c   i )  (3)
 
where M=A T A represents the distance metric matrix, and A T  is the projection matrix.
 
     Supervised distance metric learning methods instead of the unsupervised ones are used because the tracker can utilize information attained from the tracking process which is more valid. During supervised distance metric learning process, sufficient samples are collected to guarantee a good result. Unfortunately, it has become a computational burden that directly conflicts with real-time requirements. 
     In most cases, sample-selection methods tend to conduct random sampling as a sacrifice to obtain efficiency. A fast frequency domain sample-selection method is used to supervise distance metric training process as a solution that takes all samples into computation. 
     The positive and negative samples x are collected with label y as +1 and −1 respectively, and used to train a ridge regression to obtain the parameter z:
 
min z   [J ( y,h   z ( x ))+μ∥ z∥   2   2 ],
 
where J(y, h z (x))=[y−k(z,x)] 2  and
 
               k   ⁡     (     z   ,   x     )       =     exp   ⁡     (     -              z   -   x          2       2   ⁢     σ   2           )             
is a Gaussian kernel.
 
     The parameter z, is known. The Gaussian kernel regularized least square classifies input image x i  as:
 
 y=k ( z,x   i ).
 
This is a response score for each input image; the score with large value is more likely to be the positive samples.
 
     In  FIG. 5A , a sample window  120  is generated about vehicle or object  85  in a first frame to establish a first target image of object  85  depicting a first tracking position associated with the target object  85  in one frame of the image sequence. Next, as shown in  FIG. 5B , the plurality of sample windows  122 ,  124 ,  125 ,  126  and  128 , for example are created by the processor CPU  102  about the target image  85 . Next, as shown in  FIG. 6 , the sub-windows  130  are circulated by a sliding window approach in the direction of the arrows  131 ,  132  in  FIG. 6  over the image frame. 
     A pre-process includes two steps. In step one, a simple classifier in the current frame is trained; then this classifier is used to compute classification score of all the sub-windows around target in the next step. By utilizing a circulated structure of sub-windows  130  in  FIG. 6 , a closed-form solution is obtained, which significantly cuts the computational complexity. 
     First, all sub-windows are collected by sliding window approach denoted by W=(w 1 , w 2 , . . . , w M ), w i ε             r×c  with the same size as the target in the current frame, which can be divided into positive and negative sets as
 
 W =( W   +   ,W _)  (4)
 
Each sub-window in W +  has a label +1, while that in W_has a label −1.

     A Gaussian Kernel Regularized Least Square (GK-RLS) is chosen as the classifier, which has the form
 
 h   z ( x )=κ             z,x                 (5)

     Where κ           •,•          is the Gaussian Kernel functioning on classifier parameter z and input data x.
     Since there is a need to handle non-linear data, the Kernel Trick is used for this problem. 
     The parameter z of GK-RLS classifier can be obtained by solving the minimization problem of ridge regression:
 
min z   [J ( y,h   z ( x ))+μ∥ z∥   2   2 ]  (6)
 
     where y is the label vector. In Eq. 6, the former term is the loss function and μ∥z∥ 2   2  is the regularization term with μ being the weight. This is shown graphically in  FIG. 7 . The simple closed form solution is obtained and transformed to frequency-domain by Fast Fourier Transform (FFT) and Inverse Fast Fourier Transform (IFFT). The solution is: 
     
       
         
           
             
               
                 
                   
                     ⁢ 
                     ⁢ 
                     ⁢ 
                     
                       ( 
                       z 
                       ) 
                     
                   
                   = 
                   
                     
                       ⁢ 
                       ⁢ 
                       ⁢ 
                       
                         ( 
                         y 
                         ) 
                       
                     
                     
                       
                         ⁢ 
                         ⁢ 
                         ⁢ 
                         
                           ( 
                           
                             κ 
                             ⁡ 
                             
                               ( 
                               
                                 x 
                                 , 
                                 x 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                       + 
                       μ 
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
     where FFT is Fast Fourier Transform and K(x, x) is the Gaussian Kernel. Especially for the problem, Eq. 7 is specified to 
                     ⁢   ⁢   ⁢     (   z   )       =       ⁢   ⁢         ⁢   ⁢     (     κ   ⁡     (       [       W   +     ,     W   -       ]     ,     [       W   +     ,     W   -       ]       )       )       +   μ               (   8   )               
where [1,−1] is the label vector corresponding to positive and negative set.
 
     The trained classifier conducts the second step. In the next image frame, the sub-windows are created by the sliding windows in the area around the target. The large target area is shown by the square  134  in  FIG. 8 , with the target depicted by box  122 . All the sub-windows denoted as S=(s 1 , s 2 , . . . , s M ), s i ε             r×c  are collected. The score of each sub-window can be computed by:
 
response= h   z ( S )=κ( z,S )  (9)

     which can also be transformed into frequency domain to obtain an efficient solving as
 
                               (response)=                             ( K )⊙                             ( z )  (10)

     where K is the vector with elements of K( z , S). 
     Next, the samples are selected with higher response score but not occluded with tracking result of last frame as negative samples. This is because including the occluded samples with the target will let the distance metric mistake the foreground as background. 
     A finite weighted graph G=(V,E), See  FIG. 9 , with target candidates as vertices V and links between pairs of nodes as edges E is constructed. The weighted graph W: 
     Candidate nodes in a feature: x 1   (a) , . . . , x n   (a)    
     Template node in a feature: x n+1   (a)    
     Edges weight in a feature: 
                   w     (   a   )       ⁡     (     i   ,   j     )       =     exp   ⁡     (     -       ϕ   ⁡     (       x   i     (   a   )       ,     x   j     (   a   )         )         μσ   2         )         ,         
where i,j=1, . . . , n+1 and φ(•,•) is the distance measured by the learned metric between nodes.
 
     Because the weights of the edges encode nodal affinity such that nodes connected by an edge with high weight are considered to be strongly connected and edges with low weights represent nearly disconnected nodes. The weight can be viewed as a similarity measure between vertices, so it is also nonnegative and symmetric. In this work, the weight of the edge e ij  between nodes i and j is defined as
 
 w   ij   =e   −d     ij       2     /σ     2     (11)
 
where d ij  represents the distance between nodes i and j and a is a constant that controls the strength of the weight. Usually features and operators are chosen as representations. The normalization of the weight matrix P=D −1 ×W can be interpreted as a natural kernel acting on functions on V, so that the sum of each P&#39;s row is all 1, where D=diag (Σw ij ), W=[w ij ] The weighted identity matrix
 
                 ρ   ⁢           ⁢   I     =       ρ   ⨯     (         1       0       …       0       0           0       1       0       0       0           ⋮       ⋮       ⋱       ⋮       ⋮           0       0       0       1       0           0       0       …       0       1         )       =     (         ρ       0       …       0       0           0       ρ       0       0       0           ⋮       ⋮       ⋱       ⋮       ⋮           0       0       0       ρ       0           0       0       …       0       ρ         )         ;         
The status matrix P is the normalized weighted graph W (W=[w ij ]), i.e. P=D −1 W, where D=diag(Σ j w ij ).
 
The final decision matrix D f  is the arithmetic mean of two status matrix after it steps cross diffusion: D f =½×(P (1)   it+1 +P (2)   it+1 ).
 
     With the assumption of that local similarities with high values are more reliable than far-away ones, an affinity matrix is constructed using K nearest neighbors (KNN) method, denoted as A with elements: 
     
       
         
           
             
               
                 
                   
                     a 
                     
                       i 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       j 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               w 
                               
                                 i 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 j 
                               
                             
                           
                           
                             
                               j 
                               ∈ 
                               
                                 N 
                                 ⁡ 
                                 
                                   ( 
                                   i 
                                   ) 
                                 
                               
                             
                           
                         
                         
                           
                             1 
                           
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 i 
                               
                               = 
                               j 
                             
                           
                         
                         
                           
                             0 
                           
                           
                             otherwise 
                           
                         
                       
                       , 
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
     where N(i) represents node i&#39;s k nearest neighborhood. The corresponding natural kernel becomes:
 
 Q=R   −1   ×A   (13)
 
     where R=diag (Σ j a ij ) It is concluded that W is a fully connected graph, so that P encodes the full information about the similarity of each vertex to all the others, whereas Q only carries the similarity between adjacent nodes and becomes a sparsely connected graph. 
       FIGS. 10A and 10B  show a simple example to illustrate the relation between W and A. 
     
       
         
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 w 
                 x 1   
                 x 2   
                 x 3   
                 x 4   
                 x 5   
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 x 1   
                 1 
                 0.050 
                 0.067 
                 0.025 
                 0.060 
               
               
                   
                 x 2   
                 0.050 
                 1 
                 0.018 
                 0.011 
                 0.004 
               
               
                   
                 x 3   
                 0.067 
                 0.018 
                 1 
                 0.223 
                 0.005 
               
               
                   
                 x 4   
                 0.025 
                 0.011 
                 0.223 
                 1 
                 0.008 
               
               
                   
                 x s   
                 0.060 
                 0.004 
                 0.005 
                 0.008 
                 1 
               
               
                   
                   
               
             
          
         
       
     
     
       
         
               
               
               
               
               
               
               
             
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 A 
                 x 1   
                 x 2   
                 x 3   
                 x 4   
                 x 5   
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 x 1   
                 1 
                 0.050 
                 0 
                 0 
                 0.060 
               
               
                   
                 x 2   
                 0.050 
                 1 
                 0.018 
                 0 
                 0 
               
               
                   
                 x 3   
                 0 
                 0.018 
                 1 
                 0.223 
                 0 
               
               
                   
                 x 4   
                 0.025 
                 0 
                 0.223 
                 1 
                 0 
               
               
                   
                 x 5   
                 0.060 
                 0 
                 0 
                 0.008 
                 1 
               
               
                   
                   
               
             
          
         
       
     
     Two graphs of different metrics are fused by cross diffusion process. Let V (i) =[V (i)     1   , V (i)     2   , V (i)     l   ] be the vertices of Graph G (i) ), where. i=1,2 represents the i th  similarity measure method between data nodes. Therefore the W (i)  and A (i)  matrix is obtained by using Eq. 11 and Eq. 12 respectively. Then by row normalization, P (i)  and Q (i)  are obtained as well. In the diffusion process, the algorithm starts from P (i)  as initial status matrix and Q (i)  is used as the kernel matrix. 
     As different perspectives of representing data have complementarity and single description cannot achieve satisfactory performance because of the loss of completeness. Intuitively, fusion of complement representations can offer better result. 
     In this process, just two different methods are used to measure similarity between data nodes, to different weight matrix, affinity matrix and also their corresponding normalization matrix, denoted by W (1)  and W (2) , also P (1)  and P (2) , A (1)  and A (2) , Q (1)  and Q (2) . The fusion process is defined as:
 
 P   (1)   it+1   =Q   (1)   ×P   (2)   it   ×P   (1)   T   +ρI  
 
 P   (2)   it+1   =Q   (2)   ×P   (1)   it   ×Q   (2)   T   +ρI   (14)
 
where i t =0,1, . . . is the iteration times, and P (1)   0 =P (1) , P (2)   0 =P (2)  as the initial states. ρI is a weighted identity matrix to guarantee self-similarity. This process will finally converge and the two-status matrix will become almost the same, so that the decision matrix Df is obtained by computing the arithmetic mean value of two converged status matrix:
 
 D   f =½×( P   (1)   it+1   +P   (2)   it+1 )  (15)
 
     Either status matrix can be chosen as the final decision matrix as well without a large difference. Since in every iteration status matrix of one measure is modified by the kernel matrix corresponding to the other measure&#39;s KNN graph and the KNN processing can reduce noise between instances, the decision matrix has robust performance. The decision matrix is used to match target and candidate and obtain better performance than either measure method alone. 
     Two similarity measure approaches are used; each of them is a feature projecting to a distance metric space model. One is RGB-doublet-SVM, which is to project RGB histogram feature, see  FIGS. 11A and 11B  to doublet-SVM [ 16 ] distance metric space. The doublet-SVM metric is chosen mainly because it can achieve better performance using significant less time. This algorithm is about 2000 times faster in average than the most efficient method ITML among several state-of-the-art distance metric learning algorithms including LDML, MCML, LMNN and NCA. The other similarity measure is SC-MP, which uses sparse coding coefficient as the feature which can handle occlusion challenges, and let the max-pooling act as the distance metric. Because max-pooling process is able to select the most significant dimensions of the feature which has the same function as a distance metric. 
     Let W=(W + , W_)={(w l ,y l )|l=1, . . . , L} be the samples set obtained by samples selection mechanism introduced in proceeding parts, where y l  is the label having value +1 in W +  and −1 in W —  and L is the number of samples. Then according to the pair constraints, doublets D are constructed for doublet-SVM distance metric learning by extracting any two samples from W
 
 D ={( w   m   ,w   n   ,z   l )| m,n= 1, . . . , L,m≠n}   (16)
 
where z l =+1 when y m =y n  and z l =−1 when y m ≠y n . By defining a kernel of doublet
         D i =(w i1 , w i2 , z i ) and D j =(w j1 , w j2 , z j ) as
 
κ d ( D   i   ,D   j   =tr [( w   i1   −w   i2 )( w   i1   −w   i2 ) T ( w   j1   −w   j2 )( w   j1   −w   j2 ) T ]  (17)
       

     A kernel SVM is learned that classifies the training samples best. The doublet-SVM is defined as: 
                 min     M   ,   c   ,   ξ       ⁢     h   ⁢       ∑   l     ⁢     ξ   l           +       1   2     ⁢            M   1          F   2               z   l [( w   l1   −w   l2 ) T   M   1 ( w   l1   −w   l2 )+ c]≧ 1−ξ l   (18)
 
     Where ∥•∥ F  denotes the Frobenius norm, c is the bias, h is the weight of hinge loss penalty and ξ l  is a slack variable. In Eq. 18, M 1  represents the doublet-SVM distance metric to be learnt and according to the Mahalanobis metric definition,
 
 M   1 =Σ i λ i   z   i ( w   i2   −w   i2 )( w   i1   −w   i2 ) T   (19)
 
     with λ i  being the weight. Then the first constraint condition in Eq. 18 becomes
 
 z   l [( w   l1   −w   l2 ) T   M   1 ( w   l1   −w   l2 )+ c]≧ 1−ξ l ═&gt;Σ i λ i   z   i   z   l   κd ( D   l   ,D   i )+ z   l   c≧ 1−ξ l   (20)
 
     which is the common kernel SVM form. In addition, many existing SVM solvers such as LibSVM [20] can easily solve the Lagrange dual form of Eq. 18. 
     Let C=[c1, c2, . . . , cl] be representation of the candidates set in the current frame generated by particle filter, where l is the number of particles and ciεR M*N . T represents the target in the last frame; T is also an M×N matrix. Then the vertices for graph construction is to concatenate the templates and candidates, which is V=[T,C]=[T, c1, c2, . . . , cl]. To compute the similarity between nodes, we first extract two kinds of features from the vertices:
 
 F   1   =RGB ( V )  (21)
 
 F   2   =SC ( V )  (21)
 
     where RGB is RGB histogram approach and SC is to extract sparse coding coefficient from each node as a feature. Then two corresponding distance metrics doublet-SVM and Max-Pooling, see  FIGS. 11B and 11C , are trained by samples selected using method described above they are denoted by M 1  and M 2 . So far, it is possible to obtain the similarity between the template and target candidates as the form of Mahalanobis distance:
 
 D   s ( i,j )=[ F   s ( i )− F   s ( j )] M   s   [F   s ( i )− F   s ( j )] T   (22)
 
     where s=1,2 correspond to the two features and distance metrics. By utilizing fusion process described above the decision matrix D f  is obtained. Then the target candidate corresponding to the largest value in the first row of Df is chosen as the final tracking result of the current frame, because the first row denotes the similarities between the target and target candidates. 
     Accordingly, the apparatus and method perform the following sequence of steps including sampling a target image containing a plurality of sample windows by a sliding window approach in step  140  in  FIG. 3 . Next, the targets in the sliding windows are classified by Gaussian Kernel Regularized Least Square process in step  142 . 
     Next, in step  144 , the processor collects all sub-windows and, in step  146 , computes scores for all of the sub-windows. 
     The processor creates a negative sample set in step  148  and then computes two weighted graphs of the template and target candidates with node lengths in step  150 . The processor chooses two graphs by a distance metric fusion using cross diffusion in step  152  to track a target object across a sequence of an image frame using a collaborative distance metric in step  154 .