Lucas–Kanade method

<h2 id="concept">Concept</h2>
<p>The Lucas–Kanade method assumes that the displacement of the image contents between two nearby instants (frames) is small and approximately constant within a neighborhood of the point 
  
    
      
        p
      
    
    {\displaystyle p}
  
 under consideration. Thus the <a href="/facts/Optical_flow/ju6d82wz">optical flow equation</a> can be assumed to hold for all pixels within a window centered at 
  
    
      
        p
      
    
    {\displaystyle p}
  
. Namely, the local image flow (velocity) vector 
  
    
      
        (
        
          V
          
            x
          
        
        ,
        
          V
          
            y
          
        
        )
      
    
    {\displaystyle (V_{x},V_{y})}
  
 must satisfy
</p><p>
  
    
      
        
          
            
              
                
                  I
                  
                    x
                  
                
                (
                
                  q
                  
                    1
                  
                
                )
                
                  V
                  
                    x
                  
                
                +
                
                  I
                  
                    y
                  
                
                (
                
                  q
                  
                    1
                  
                
                )
                
                  V
                  
                    y
                  
                
              
              
                
                =
                −
                
                  I
                  
                    t
                  
                
                (
                
                  q
                  
                    1
                  
                
                )
              
            
            
              
                
                  I
                  
                    x
                  
                
                (
                
                  q
                  
                    2
                  
                
                )
                
                  V
                  
                    x
                  
                
                +
                
                  I
                  
                    y
                  
                
                (
                
                  q
                  
                    2
                  
                
                )
                
                  V
                  
                    y
                  
                
              
              
                
                =
                −
                
                  I
                  
                    t
                  
                
                (
                
                  q
                  
                    2
                  
                
                )
              
            
            
              
              
                
                 
                ⋮
              
            
            
              
                
                  I
                  
                    x
                  
                
                (
                
                  q
                  
                    n
                  
                
                )
                
                  V
                  
                    x
                  
                
                +
                
                  I
                  
                    y
                  
                
                (
                
                  q
                  
                    n
                  
                
                )
                
                  V
                  
                    y
                  
                
              
              
                
                =
                −
                
                  I
                  
                    t
                  
                
                (
                
                  q
                  
                    n
                  
                
                )
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}I_{x}(q_{1})V_{x}+I_{y}(q_{1})V_{y}&=-I_{t}(q_{1})\\I_{x}(q_{2})V_{x}+I_{y}(q_{2})V_{y}&=-I_{t}(q_{2})\\&\;\ \vdots \\I_{x}(q_{n})V_{x}+I_{y}(q_{n})V_{y}&=-I_{t}(q_{n})\end{aligned}}}

</p><p>where 
  
    
      
        
          q
          
            1
          
        
        ,
        
          q
          
            2
          
        
        ,
        …
        ,
        
          q
          
            n
          
        
      
    
    {\displaystyle q_{1},q_{2},\dots ,q_{n}}
  
 are the pixels inside the window, and 
  
    
      
        
          I
          
            x
          
        
        (
        
          q
          
            i
          
        
        )
        ,
        
          I
          
            y
          
        
        (
        
          q
          
            i
          
        
        )
        ,
        
          I
          
            t
          
        
        (
        
          q
          
            i
          
        
        )
      
    
    {\displaystyle I_{x}(q_{i}),I_{y}(q_{i}),I_{t}(q_{i})}
  
 are the partial derivatives of the image 
  
    
      
        I
      
    
    {\displaystyle I}
  
 with respect to position 
  
    
      
        x
        ,
        y
      
    
    {\displaystyle x,y}
  
 and time 
  
    
      
        t
      
    
    {\displaystyle t}
  
, evaluated at the point 
  
    
      
        
          q
          
            i
          
        
      
    
    {\displaystyle q_{i}}
  
 and at the current time. 
</p><p>These equations can be written in <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix</a> form 
  
    
      
        A
        v
        =
        b
      
    
    {\displaystyle Av=b}
  
, where

A
        =
        
          
            [
            
              
                
                  
                    I
                    
                      x
                    
                  
                  (
                  
                    q
                    
                      1
                    
                  
                  )
                
                
                  
                    I
                    
                      y
                    
                  
                  (
                  
                    q
                    
                      1
                    
                  
                  )
                
              
              
                
                  
                    I
                    
                      x
                    
                  
                  (
                  
                    q
                    
                      2
                    
                  
                  )
                
                
                  
                    I
                    
                      y
                    
                  
                  (
                  
                    q
                    
                      2
                    
                  
                  )
                
              
              
                
                  ⋮
                
                
                  ⋮
                
              
              
                
                  
                    I
                    
                      x
                    
                  
                  (
                  
                    q
                    
                      n
                    
                  
                  )
                
                
                  
                    I
                    
                      y
                    
                  
                  (
                  
                    q
                    
                      n
                    
                  
                  )
                
              
            
            ]
          
        
        
        
        
        v
        =
        
          
            [
            
              
                
                  
                    V
                    
                      x
                    
                  
                
              
              
                
                  
                    V
                    
                      y
                    
                  
                
              
            
            ]
          
        
        
        
        
        b
        =
        
          
            [
            
              
                
                  −
                  
                    I
                    
                      t
                    
                  
                  (
                  
                    q
                    
                      1
                    
                  
                  )
                
              
              
                
                  −
                  
                    I
                    
                      t
                    
                  
                  (
                  
                    q
                    
                      2
                    
                  
                  )
                
              
              
                
                  ⋮
                
              
              
                
                  −
                  
                    I
                    
                      t
                    
                  
                  (
                  
                    q
                    
                      n
                    
                  
                  )
                
              
            
            ]
          
        
      
    
    {\displaystyle A={\begin{bmatrix}I_{x}(q_{1})&I_{y}(q_{1})\\[10pt]I_{x}(q_{2})&I_{y}(q_{2})\\[10pt]\vdots &\vdots \\[10pt]I_{x}(q_{n})&I_{y}(q_{n})\end{bmatrix}}\quad \quad \quad v={\begin{bmatrix}V_{x}\\[10pt]V_{y}\end{bmatrix}}\quad \quad \quad b={\begin{bmatrix}-I_{t}(q_{1})\\[10pt]-I_{t}(q_{2})\\[10pt]\vdots \\[10pt]-I_{t}(q_{n})\end{bmatrix}}}

</p><p>This system has more equations than unknowns and thus it is usually over-determined. The Lucas–Kanade method obtains a compromise solution by the <a href="/facts/Linear_least_squares_(mathematics)/dKctFUCV">least squares</a> principle. Namely, it solves the 
  
    
      
        2
        ×
        2
      
    
    {\displaystyle 2\times 2}
  
 system

A
          
            T
          
        
        A
        v
        =
        
          A
          
            T
          
        
        b
      
    
    {\displaystyle A^{T}Av=A^{T}b}
  
 or

v
        
        =
        (
        
          A
          
            T
          
        
        A
        
          )
          
            −
            1
          
        
        
          A
          
            T
          
        
        b
      
    
    {\displaystyle \mathrm {v} =(A^{T}A)^{-1}A^{T}b}

where 
  
    
      
        
          A
          
            T
          
        
      
    
    {\displaystyle A^{T}}
  
 is the <a href="/facts/Transposed_matrix/8wmsagGS">transpose</a> of matrix 
  
    
      
        A
      
    
    {\displaystyle A}
  
. That is, it computes

[
            
              
                
                  
                    V
                    
                      x
                    
                  
                
              
              
                
                  
                    V
                    
                      y
                    
                  
                
              
            
            ]
          
        
        =
        
          
            
              [
              
                
                  
                    
                      ∑
                      
                        i
                      
                    
                    
                      I
                      
                        x
                      
                    
                    (
                    
                      q
                      
                        i
                      
                    
                    
                      )
                      
                        2
                      
                    
                  
                  
                    
                      ∑
                      
                        i
                      
                    
                    
                      I
                      
                        x
                      
                    
                    (
                    
                      q
                      
                        i
                      
                    
                    )
                    
                      I
                      
                        y
                      
                    
                    (
                    
                      q
                      
                        i
                      
                    
                    )
                  
                
                
                  
                    
                      ∑
                      
                        i
                      
                    
                    
                      I
                      
                        y
                      
                    
                    (
                    
                      q
                      
                        i
                      
                    
                    )
                    
                      I
                      
                        x
                      
                    
                    (
                    
                      q
                      
                        i
                      
                    
                    )
                  
                  
                    
                      ∑
                      
                        i
                      
                    
                    
                      I
                      
                        y
                      
                    
                    (
                    
                      q
                      
                        i
                      
                    
                    
                      )
                      
                        2
                      
                    
                  
                
              
              ]
            
          
          
            −
            1
          
        
        
          
            [
            
              
                
                  −
                  
                    ∑
                    
                      i
                    
                  
                  
                    I
                    
                      x
                    
                  
                  (
                  
                    q
                    
                      i
                    
                  
                  )
                  
                    I
                    
                      t
                    
                  
                  (
                  
                    q
                    
                      i
                    
                  
                  )
                
              
              
                
                  −
                  
                    ∑
                    
                      i
                    
                  
                  
                    I
                    
                      y
                    
                  
                  (
                  
                    q
                    
                      i
                    
                  
                  )
                  
                    I
                    
                      t
                    
                  
                  (
                  
                    q
                    
                      i
                    
                  
                  )
                
              
            
            ]
          
        
      
    
    {\displaystyle {\begin{bmatrix}V_{x}\\[10pt]V_{y}\end{bmatrix}}={\begin{bmatrix}\sum _{i}I_{x}(q_{i})^{2}&\sum _{i}I_{x}(q_{i})I_{y}(q_{i})\\[10pt]\sum _{i}I_{y}(q_{i})I_{x}(q_{i})&\sum _{i}I_{y}(q_{i})^{2}\end{bmatrix}}^{-1}{\begin{bmatrix}-\sum _{i}I_{x}(q_{i})I_{t}(q_{i})\\[10pt]-\sum _{i}I_{y}(q_{i})I_{t}(q_{i})\end{bmatrix}}}

where the central matrix in the equation is an <a href="/facts/Invertible_matrix/fPqXk3V8">Inverse matrix</a>. The sums are running from 
  
    
      
        i
        =
        1
      
    
    {\displaystyle i=1}
  
 to 
  
    
      
        n
      
    
    {\displaystyle n}
  
.
</p><p>The matrix 
  
    
      
        
          A
          
            T
          
        
        A
      
    
    {\displaystyle A^{T}A}
  
 is often called the <a href="/facts/Structure_tensor/FyyELa9n">structure tensor</a> of the image at the point 
  
    
      
        p
      
    
    {\displaystyle p}
  
.
</p>
<h2 id="weighted-window">Weighted window</h2>
<p>The plain least squares solution above gives the same importance to all 
  
    
      
        n
      
    
    {\displaystyle n}
  
 pixels 
  
    
      
        
          q
          
            i
          
        
      
    
    {\displaystyle q_{i}}
  
 in the window. In practice it is usually better to give more weight to the pixels that are closer to the central pixel 
  
    
      
        p
      
    
    {\displaystyle p}
  
. For that, one uses the weighted version of the least squares equation,

A
          
            T
          
        
        W
        A
        v
        =
        
          A
          
            T
          
        
        W
        b
      
    
    {\displaystyle A^{T}WAv=A^{T}Wb}

v
        
        =
        (
        
          A
          
            T
          
        
        W
        A
        
          )
          
            −
            1
          
        
        
          A
          
            T
          
        
        W
        b
      
    
    {\displaystyle \mathrm {v} =(A^{T}WA)^{-1}A^{T}Wb}

where 
  
    
      
        W
      
    
    {\displaystyle W}
  
 is an 
  
    
      
        n
        ×
        n
      
    
    {\displaystyle n\times n}
  
 <a href="/facts/Diagonal_matrix/tjIAHrE6">diagonal matrix</a> containing the weights 
  
    
      
        
          W
          
            i
            i
          
        
        =
        
          w
          
            i
          
        
      
    
    {\displaystyle W_{ii}=w_{i}}
  
 to be assigned to the equation of pixel 
  
    
      
        
          q
          
            i
          
        
      
    
    {\displaystyle q_{i}}
  
. That is, it computes

[
            
              
                
                  
                    V
                    
                      x
                    
                  
                
              
              
                
                  
                    V
                    
                      y
                    
                  
                
              
            
            ]
          
        
        =
        
          
            
              [
              
                
                  
                    
                      ∑
                      
                        i
                      
                    
                    
                      w
                      
                        i
                      
                    
                    
                      I
                      
                        x
                      
                    
                    (
                    
                      q
                      
                        i
                      
                    
                    
                      )
                      
                        2
                      
                    
                  
                  
                    
                      ∑
                      
                        i
                      
                    
                    
                      w
                      
                        i
                      
                    
                    
                      I
                      
                        x
                      
                    
                    (
                    
                      q
                      
                        i
                      
                    
                    )
                    
                      I
                      
                        y
                      
                    
                    (
                    
                      q
                      
                        i
                      
                    
                    )
                  
                
                
                  
                    
                      ∑
                      
                        i
                      
                    
                    
                      w
                      
                        i
                      
                    
                    
                      I
                      
                        x
                      
                    
                    (
                    
                      q
                      
                        i
                      
                    
                    )
                    
                      I
                      
                        y
                      
                    
                    (
                    
                      q
                      
                        i
                      
                    
                    )
                  
                  
                    
                      ∑
                      
                        i
                      
                    
                    
                      w
                      
                        i
                      
                    
                    
                      I
                      
                        y
                      
                    
                    (
                    
                      q
                      
                        i
                      
                    
                    
                      )
                      
                        2
                      
                    
                  
                
              
              ]
            
          
          
            −
            1
          
        
        
          
            [
            
              
                
                  −
                  
                    ∑
                    
                      i
                    
                  
                  
                    w
                    
                      i
                    
                  
                  
                    I
                    
                      x
                    
                  
                  (
                  
                    q
                    
                      i
                    
                  
                  )
                  
                    I
                    
                      t
                    
                  
                  (
                  
                    q
                    
                      i
                    
                  
                  )
                
              
              
                
                  −
                  
                    ∑
                    
                      i
                    
                  
                  
                    w
                    
                      i
                    
                  
                  
                    I
                    
                      y
                    
                  
                  (
                  
                    q
                    
                      i
                    
                  
                  )
                  
                    I
                    
                      t
                    
                  
                  (
                  
                    q
                    
                      i
                    
                  
                  )
                
              
            
            ]
          
        
      
    
    {\displaystyle {\begin{bmatrix}V_{x}\\[10pt]V_{y}\end{bmatrix}}={\begin{bmatrix}\sum _{i}w_{i}I_{x}(q_{i})^{2}&\sum _{i}w_{i}I_{x}(q_{i})I_{y}(q_{i})\\[10pt]\sum _{i}w_{i}I_{x}(q_{i})I_{y}(q_{i})&\sum _{i}w_{i}I_{y}(q_{i})^{2}\end{bmatrix}}^{-1}{\begin{bmatrix}-\sum _{i}w_{i}I_{x}(q_{i})I_{t}(q_{i})\\[10pt]-\sum _{i}w_{i}I_{y}(q_{i})I_{t}(q_{i})\end{bmatrix}}}

</p><p>The weight 
  
    
      
        
          w
          
            i
          
        
      
    
    {\displaystyle w_{i}}
  
 is usually set to a <a href="/facts/Gaussian_distribution/UapjjPyQ">Gaussian function</a> of the distance between 
  
    
      
        
          q
          
            i
          
        
      
    
    {\displaystyle q_{i}}
  
 and 
  
    
      
        p
      
    
    {\displaystyle p}
  
.
</p>
<h2 id="use-conditions-and-techniques">Use conditions and techniques</h2>
<p>In order for equation 
  
    
      
        
          A
          
            T
          
        
        A
        v
        =
        
          A
          
            T
          
        
        b
      
    
    {\displaystyle A^{T}Av=A^{T}b}
  
 to be solvable, 
  
    
      
        
          A
          
            T
          
        
        A
      
    
    {\displaystyle A^{T}A}
  
 should be invertible, or 
  
    
      
        
          A
          
            T
          
        
        A
      
    
    {\displaystyle A^{T}A}
  
's eigenvalues satisfy 
  
    
      
        
          λ
          
            1
          
        
        ≥
        
          λ
          
            2
          
        
        >
        0
      
    
    {\displaystyle \lambda _{1}\geq \lambda _{2}>0}
  
. To avoid noise issue, usually 
  
    
      
        
          λ
          
            2
          
        
      
    
    {\displaystyle \lambda _{2}}
  
 is required to not be too small. Also, if 
  
    
      
        
          λ
          
            1
          
        
        
          /
        
        
          λ
          
            2
          
        
      
    
    {\displaystyle \lambda _{1}/\lambda _{2}}
  
 is too large, this means that the point 
  
    
      
        p
      
    
    {\displaystyle p}
  
 is on an edge, and this method suffers from the <a href="/facts/Aperture_problem/kShuo6b8">aperture problem</a>. So for this method to work properly, the condition is that 
  
    
      
        
          λ
          
            1
          
        
      
    
    {\displaystyle \lambda _{1}}
  
 and 
  
    
      
        
          λ
          
            2
          
        
      
    
    {\displaystyle \lambda _{2}}
  
 are large enough and have similar magnitude. This condition is also the one for <a href="/facts/Corner_detection/19pSbRDe">corner detection</a>. This observation shows that one can easily tell which pixel is suitable for the Lucas–Kanade method to work on by inspecting a single image.
</p><p>One main assumption for this method is that the motion is small (less than 1 pixel between two images for example). If the motion is large and violates this assumption, one technique is to reduce the resolution of images first and then apply the Lucas–Kanade method.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p><p>In order to achieve <a href="/facts/Video_tracking/nVh8FB3E">motion tracking</a> with this method, the flow vector can be iteratively applied and recalculated, until some threshold near zero is reached, at which point it can be assumed that the image windows are very close in similarity.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> By doing this to each successive tracking window, the point can be tracked throughout several images in a sequence, until it is either obscured or goes out of frame.
</p>
<h2 id="improvements-and-extensions">Improvements and extensions</h2>
<p>The least-squares approach implicitly assumes that the errors in the image data have a Gaussian distribution with zero mean. If one expects the window to contain a certain percentage of "<a href="/facts/Outlier/VBhIzGbx">outliers</a>" (grossly wrong data values, that do not follow the "ordinary" Gaussian error distribution), one may use statistical analysis to detect them, and reduce their weight accordingly.
</p><p>The Lucas–Kanade method per se can be used only when the image flow vector 
  
    
      
        
          V
          
            x
          
        
        ,
        
          V
          
            y
          
        
      
    
    {\displaystyle V_{x},V_{y}}
  
 between the two frames is small enough for the differential equation of the optical flow to hold, which is often less than the pixel spacing. When the flow vector may exceed this limit, such as in stereo matching or warped document registration, the Lucas–Kanade method may still be used to refine some coarse estimate of the same, obtained by other means; for example, by <a href="/facts/Extrapolation/wggUrqjF">extrapolating</a> the flow vectors computed for previous frames, or by running the Lucas–Kanade algorithm on reduced-scale versions of the images. Indeed, the latter method is the basis of the popular <a href="/facts/Kanade%25E2%2580%2593Lucas%25E2%2580%2593Tomasi_feature_tracker/9G833MWt">Kanade–Lucas–Tomasi (KLT)</a> feature matching algorithm.
</p><p>A similar technique can be used to compute differential <a href="/facts/Affine_mapping/BD7yDr10">affine</a> deformations of the image contents.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Optical_flow/ju6d82wz">Optical flow</a></li>
<li><a href="/facts/Horn%25E2%2580%2593Schunck_method/N5PcUc7n">Horn–Schunck method</a></li>
<li><a href="/facts/Shi%25E2%2580%2593Tomasi_corner_detection_algorithm/19pSbRDe">Shi–Tomasi corner detection algorithm</a></li>
<li><a href="/facts/Kanade%25E2%2580%2593Lucas%25E2%2580%2593Tomasi_feature_tracker/9G833MWt">Kanade–Lucas–Tomasi feature tracker</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.cs.cmu.edu/~kangli/code/Image_Stabilizer.html">The image stabilizer plugin for ImageJ</a> based on the Lucas–Kanade method</li>
<li><a href="http://www.mathworks.com/matlabcentral/fileexchange/24677">Mathworks Lucas-Kanade</a> Matlab implementation of inverse and normal affine Lucas-Kanade</li>
<li><a href="https://web.archive.org/web/20140506113705/http://onera-windtunnel.com/dtim-en/gpu-for-image/folkigpu.php">FolkiGPU:</a> GPU implementation of an iterative Lucas-Kanade based optical flow</li>
<li><a href="http://www.ces.clemson.edu/~stb/klt/">KLT</a>: An Implementation of the Kanade–Lucas–Tomasi Feature Tracker</li>
<li><a href="http://www.ri.cmu.edu/people/kanade_takeo.html">Takeo Kanade</a></li>
<li><a href="https://github.com/thomas-pegot/esp32-motion/blob/master/lucas_kanade_opitcal_flow.c">C example</a> using the Lucas-Kanade optical flow algorithm</li>
<li><a href="https://github.com/Itseez/opencv_attic/blob/master/opencv/samples/cpp/lkdemo.cpp">C++ example</a> using the Lucas-Kanade optical flow algorithm</li>
<li><a href="https://github.com/Itseez/opencv_attic/blob/a6078cc8477ff055427b67048a95547b3efe92a5/opencv/samples/python2/lk_track.py">Python example</a> using the Lucas-Kanade optical flow algorithm</li>
<li><a href="https://github.com/Itseez/opencv_attic/blob/a6078cc8477ff055427b67048a95547b3efe92a5/opencv/samples/python2/lk_homography.py">Python example</a> using the Lucas-Kanade tracker for homography matching</li>
<li><a href="http://www.mathworks.com/matlabcentral/fileexchange/48744-lucas-kanade-tutorial-example-1/content/LucasKanadeExample1/html/LKExample1.html">MATLAB quick example</a> of Lucas-Kanade method to show optical flow field</li>
<li><a href="http://www.mathworks.com/matlabcentral/fileexchange/48745-lucas-kanade-tutorial-example-2/content/LucasKanadeExample2/html/LKExample2.html">MATLAB quick example</a> of Lucas-Kanade method to show velocity vector of objects</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>B. D. Lucas and T. Kanade (1981), An iterative image registration technique with an application to stereo vision. Proceedings of Imaging Understanding Workshop, pages 121--130 <a href="http://www-cse.ucsd.edu/classes/sp02/cse252/lucaskanade81.pdf" target="_blank">http://www-cse.ucsd.edu/classes/sp02/cse252/lucaskanade81.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Bruce D. Lucas (1984) Generalized Image Matching by the Method of Differences (doctoral dissertation) <a href="http://www.ri.cmu.edu/pub_files/pub4/lucas_bruce_d_1984_1/lucas_bruce_d_1984_1.pdf" target="_blank">http://www.ri.cmu.edu/pub_files/pub4/lucas_bruce_d_1984_1/lucas_bruce_d_1984_1.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>J. Y. Bouguet, (2001) . Pyramidal implementation of the affine lucas kanade feature tracker description of the algorithm. Intel Corporation, 5. <a href="http://robots.stanford.edu/cs223b04/algo_affine_tracking.pdf" target="_blank">http://robots.stanford.edu/cs223b04/algo_affine_tracking.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>B. D. Lucas and T. Kanade (1981), An iterative image registration technique with an application to stereo vision. Proceedings of Imaging Understanding Workshop, pages 121--130 <a href="http://www-cse.ucsd.edu/classes/sp02/cse252/lucaskanade81.pdf" target="_blank">http://www-cse.ucsd.edu/classes/sp02/cse252/lucaskanade81.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

Lucas–Kanade method open-in-new

Lucas–Kanade method