Lucas-Kanade 20 Years On: A Unifying Framework

Simon BakerIain Matthews

article2004IJCV3,524 citations

Establishes a unifying framework for Lucas-Kanade image alignment by proving the first-order equivalence of forward, inverse, additive, and compositional approaches, demonstrating that the inverse compositional Gauss-Newton algorithm achieves dramatic computational speedups without sacrificing accuracy.

Listen

The Lucas-Kanade algorithm, introduced in 1981, established image alignment as a core computer vision technique for tasks such as optical flow, tracking, motion estimation, mosaic construction, and face modeling. Over two decades, numerous variants and extensions appeared, differing in how they approximate the error surface, update the warp, and handle gradient descent, which created confusion about their relative merits and computational costs.

This paper develops a single framework that classifies these algorithms along two independent axes: whether they perform additive or compositional updates to the warp, and whether they operate in a forwards or inverse manner. It derives closed-form expressions for each combination, proves that the four principal variants reach the same first-order solution, and validates the equivalence through controlled experiments on affine and homography warps using thousands of random initializations.

The analysis shows that the inverse compositional algorithm is the only variant that shifts the dominant Hessian computation into a one-time pre-computation while remaining applicable to any set of warps that forms a group. Among gradient-descent approximations, the Gauss-Newton and Levenberg-Marquardt forms converge fastest and most reliably; steepest-descent and diagonal-Hessian approximations converge far more slowly and are sensitive to parameterization. Timing measurements confirm that the inverse compositional Gauss-Newton method reduces per-iteration cost from O(n²N + n³) to O(nN + n³).

These results matter because practitioners can now select an algorithm on the basis of required speed and expected noise distribution rather than ad-hoc trial. When the template is less noisy than the input image, the inverse compositional Gauss-Newton or Levenberg-Marquardt algorithm is the clear practical choice; when the template is noisier, a forwards variant may be preferable despite its higher cost.

The paper notes that its empirical comparisons are limited to affine and homography warps and that performance still varies with image content. It defers treatment of robust error norms, linear appearance variation, and parameter priors to subsequent papers in the series.

Carnegie Mellon University adaptive algorithms computer vision computer vision applications Lucas‑Kanade algorithm image alignment inverse compositional algorithm

Baker et al (2004).pdf

Paper: An Iterative Image Registration Technique with an Application to Stereo Vision, B. D. Lucas et al. (1981). Reading the original 1981 Lucas-Kanade paper is essential because the source paper builds directly upon its foundational image alignment formulation and gradient descent approximations.

Paper: RAFT: Recurrent All-Pairs Field Transforms for Optical Flow, Zachary Teed et al. (2020). This paper extends classical optical flow and alignment frameworks like Lucas-Kanade into deep learning with recurrent all-pairs field transforms.

Cover for Lucas-Kanade 20 Years On: A Unifying Framework

Abstract

Since the Lucas-Kanade algorithm was proposed in 1981 image alignment has become one of the most widely used techniques in computer vision. Applications range from optical flow and tracking to layered motion, mosaic construction, and face coding. Numerous algorithms have been proposed and a wide variety of extensions have been made to the original formulation. We present an overview of image alignment, describing most of the algorithms and their extensions in a consistent framework. We concentrate on the inverse compositional algorithm, an efficient algorithm that we recently proposed. We examine which of the extensions to Lucas-Kanade can be used with the inverse compositional algorithm without any significant loss of efficiency, and which cannot. In this paper, Part 1 in a series of papers, we cover the quantity approximated, the warp update rule, and the gradient descent approximation. In future papers, we will cover the choice of the error function, how to allow linear appearance variation, and how to impose priors on the parameters.

1. Introduction
2. Background: Lucas-Kanade
2.1. Goal of the Lucas-Kanade Algorithm
2.2. Derivation of the Lucas-Kanade Algorithm
2.3. Requirements on the Set of Warps
2.4. Computational Cost of the Lucas-Kanade Algorithm
3. The Quantity Approximated and the Warp Update Rule
3.1. Compositional Image Alignment
3.1.1. Goal of the Compositional Algorithm. The compositional algorithm, used most notably by Shum and Szeliski (2000), approximately minimizes:
3.2. Inverse Compositional Image Alignment
3.2.1. Goal of the Inverse Compositional Algorithm.
3.2.2. Derivation of the Inverse Compositional Algorithm. Performing a first order Taylor expansion on Eq. (31) gives:
3.2.3. Requirements on the Set of Warps. Besides the semi-group requirement of the forwards compositional algorithm the inverse compositional algorithm also requires that the incremental warp $\mathbf{W}(\mathbf{x}; \Delta \mathbf{p})$ be inverted before it is composed with the current estimate. The inverse compositional algorithm can therefore only be applied to sets of warps that form a group. Fortunately, most warps used in computer vision, including homographies and 3D rotations (Shum and Szeliski, 2000), do form groups. One notable exception are the piecewise affine warps used in Active Appearance Models
3.3. Inverse Additive Image Alignment
3.4. Empirical Validation
3.5. Summary
4. The Gradient Descent Approximation
4.1. The Gauss-Newton Algorithm
4.2. The Newton Algorithm
The Newton Inverse Compositional Algorithm
4.3. Steepest Descent
4.3.1. Derivation of the Steepest Descent Algorithm.
4.3.2. Computational Cost of the Gauss-Newton Steepest Descent Algorithm.
The GN Steepest Descent Inverse Compositional Algorithm
4.4. The Diagonal Approximation to the Hessian
The Diagonal Hessian Inverse Compositional Algorithm
4.5. The Levenberg-Marquardt Algorithm
4.5.1. Computational Cost of the Levenberg-Marquardt Inverse Compositional Algorithm.
4.6. Empirical Validation
4.7. Summary
4.8. Other Algorithms
5. Discussion
6. Matlab Code, Test Images, and Scripts
Appendix A: Inverse Compositional Derivations for the Homography
A.1. Gauss-Newton Inverse Compositional Algorithm
A.2. Newton Inverse Compositional Algorithm

Knowls

Knowl 1 — Gauss-Newton Inverse Compositional Image Alignment Algorithm
algorithm
The Gauss-Newton Inverse Compositional algorithm registers an input image $I(\mathbf{x})$ to a reference template image $T(\mathbf{x})$ by iteratively optimizing warp parameters $\mathbf{p} = (p_1, \dots, p_n)^T \in \mathbb{R}^n$ governing a parameterized coordinate transformation $\mathbf{W}(\mathbf{x}; \mathbf{p})$ . The coordinate $\mathbf{x} = (x, y)^T$ ranges over all $N$ pixels in the coordinate frame of $T$ , and $\mathbf{W}(\mathbf{x}; \mathbf{0}) = \mathbf{x}$ represents the identity transformation.

All computationally demanding steps—spatial template gradients $\nabla T$ , warp Jacobians evaluated at zero $\left.\frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right|_{(\mathbf{x}; \mathbf{0})}$ , steepest descent images, and the $n \times n$ Gauss-Newton Hessian matrix $H$ along with its inverse $H^{-1}$ —are computed once during a pre-computation stage. Each iteration requires only image warping, image subtraction, image dot products to form the parameter gradient update vector, matrix multiplication with the precomputed $H^{-1}$ , and warp parameter composition via the inverse increment $\mathbf{W}(\mathbf{x}; \Delta \mathbf{p})^{-1}$ .
Input: Template image $T(\mathbf{x})$ , input image $I(\mathbf{x})$ , initial warp parameters $\mathbf{p}$ , convergence threshold $\epsilon > 0$
Output: Converged warp parameters $\mathbf{p}$
Pre-computation:
Evaluate gradient $\nabla T(\mathbf{x}) = \left(\frac{\partial T}{\partial x}, \frac{\partial T}{\partial y}\right)$ for all pixels $\mathbf{x}$ in $T$
Evaluate warp Jacobian $\frac{\partial \mathbf{W}}{\partial \mathbf{p}}$ at $(\mathbf{x}; \mathbf{0})$
Compute steepest descent images $\nabla T \frac{\partial \mathbf{W}}{\partial \mathbf{p}}$ for all pixels $\mathbf{x}$
Compute Hessian matrix $H = \sum_{\mathbf{x}} \left[\nabla T \frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right]^T \left[\nabla T \frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right]$
Compute inverse Hessian $H^{-1}$
Iteration:
repeat
    Warp input image $I$ to compute $I(\mathbf{W}(\mathbf{x}; \mathbf{p}))$
    Compute error image $E(\mathbf{x}) = I(\mathbf{W}(\mathbf{x}; \mathbf{p})) - T(\mathbf{x})$
    Compute steepest descent parameter updates $\mathbf{v} = \sum_{\mathbf{x}} \left[\nabla T \frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right]^T E(\mathbf{x})$
    Compute parameter update $\Delta \mathbf{p} = H^{-1} \mathbf{v}$
    Invert incremental warp $\mathbf{W}(\mathbf{x}; \Delta \mathbf{p})$ to obtain $\mathbf{W}(\mathbf{x}; \Delta \mathbf{p})^{-1}$
    Update current warp $\mathbf{W}(\mathbf{x}; \mathbf{p}) \leftarrow \mathbf{W}(\mathbf{x}; \mathbf{p}) \circ \mathbf{W}(\mathbf{x}; \Delta \mathbf{p})^{-1}$
until $\|\Delta \mathbf{p}\| \le \epsilon$
return $\mathbf{p}$
The pre-computation has time complexity $O(n^2 N)$ . Each iteration has time complexity $O(nN + n^2)$ (or $O(nN + n^3)$ if $H^{-1}$ is multiplied explicitly rather than pre-factored), representing a substantial speedup over classical Lucas-Kanade whose per-iteration complexity is $O(n^2 N + n^3)$ .
Knowl 2 — Objective Function and Warp Update of the Inverse Compositional Formulation
equation
The Inverse Compositional image alignment formulation reverses the roles of the template $T(\mathbf{x})$ and the input image $I(\mathbf{x})$ in the optimization objective by warping the template with an incremental warp $\mathbf{W}(\mathbf{x}; \Delta \mathbf{p})$ :

$\min_{\Delta \mathbf{p}} \sum_{\mathbf{x}} \left[ T(\mathbf{W}(\mathbf{x}; \Delta \mathbf{p})) - I(\mathbf{W}(\mathbf{x}; \mathbf{p})) \right]^2$

where $\mathbf{x} = (x, y)^T$ ranges over all pixels in the template $T$ , $\mathbf{p} = (p_1, \dots, p_n)^T$ is the vector of current warp parameters, $\Delta \mathbf{p} = (\Delta p_1, \dots, \Delta p_n)^T$ is the vector of incremental parameter updates, and $\mathbf{W}(\mathbf{x}; \mathbf{0}) = \mathbf{x}$ is the identity warp.

Performing a first-order Taylor series expansion of $T(\mathbf{W}(\mathbf{x}; \Delta \mathbf{p}))$ around $\Delta \mathbf{p} = \mathbf{0}$ yields the closed-form Gauss-Newton solution:

$\Delta \mathbf{p} = H^{-1} \sum_{\mathbf{x}} \left[ \nabla T \frac{\partial \mathbf{W}}{\partial \mathbf{p}} \right]^T \left[ I(\mathbf{W}(\mathbf{x}; \mathbf{p})) - T(\mathbf{x}) \right]$

where $\nabla T = \left(\frac{\partial T}{\partial x}, \frac{\partial T}{\partial y}\right)$ is the gradient of the template, $\frac{\partial \mathbf{W}}{\partial \mathbf{p}}$ is the $2 \times n$ warp Jacobian evaluated at $(\mathbf{x}; \mathbf{0})$ , and the $n \times n$ Gauss-Newton Hessian matrix is independent of $\mathbf{p}$ and defined by:

$H = \sum_{\mathbf{x}} \left[ \nabla T \frac{\partial \mathbf{W}}{\partial \mathbf{p}} \right]^T \left[ \nabla T \frac{\partial \mathbf{W}}{\partial \mathbf{p}} \right]$

The warp estimate is updated by inverting the incremental warp and composing it with the current warp estimate:

$\mathbf{W}(\mathbf{x}; \mathbf{p}) \leftarrow \mathbf{W}(\mathbf{x}; \mathbf{p}) \circ \mathbf{W}(\mathbf{x}; \Delta \mathbf{p})^{-1}$
Knowl 3 — First-Order Equivalence of Image Alignment Formulations
theoretical result
The four fundamental gradient-descent image alignment algorithms—Forwards Additive (classical Lucas-Kanade), Forwards Compositional (Shum-Szeliski), Inverse Additive (Hager-Belhumeur), and Inverse Compositional (Baker-Matthews)—are mathematically equivalent to first order in the parameter update $\Delta \mathbf{p}$ . Specifically, in each iteration, all four algorithms make identical updates to the parameterized warp $\mathbf{W}(\mathbf{x}; \mathbf{p})$ up to $O(\|\Delta \mathbf{p}\|^2)$ .

This equivalence holds under the following conditions:
1. The set of allowed warps forms a mathematical group (satisfying identity $\mathbf{W}(\mathbf{x}; \mathbf{0}) = \mathbf{x}$ , closure under composition $\mathbf{W}(\mathbf{x}; \mathbf{p}_1) \circ \mathbf{W}(\mathbf{x}; \mathbf{p}_2) \in \mathcal{W}$ , and invertibility $\mathbf{W}(\mathbf{x}; \mathbf{p})^{-1} \in \mathcal{W}$ ).
2. The current parameter estimate $\mathbf{p}$ is in the neighborhood of convergence such that the intensity discrepancy between the template and warped image satisfies $T(\mathbf{x}) - I(\mathbf{W}(\mathbf{x}; \mathbf{p})) = O(\|\Delta \mathbf{p}\|)$ .
3. For the Inverse Additive formulation, the warp Jacobian product must additionally satisfy the factorization condition $\left(\frac{\partial \mathbf{W}}{\partial \mathbf{x}}\right)^{-1} \frac{\partial \mathbf{W}}{\partial \mathbf{p}} = \Gamma(\mathbf{x}) \Sigma(\mathbf{p})$ .

Knowl 4 — Taxonomy, Algebraic Requirements, and Complexity of Image Alignment Approaches

model/method

Image alignment algorithms can be systematically classified along two orthogonal axes: parameter update style (Additive vs. Compositional) and image-template role (Forwards vs. Inverse).

Algorithm	Primary Reference	Pre-computation	Per-Iteration Cost	Warp Set Requirement
Forwards Additive	Lucas and Kanade (1981)	None	$O(n^2 N + n^3)$	Any differentiable warp
Forwards Compositional	Shum and Szeliski (2000)	$O(nN)$	$O(n^2 N + n^3)$	Semi-group containing identity
Inverse Additive	Hager and Belhumeur (1998)	$O(k^2 N)$	$O(nN + kN + k^3)$	Factorable Jacobians
Inverse Compositional	Baker and Matthews (2001)	$O(n^2 N)$	$O(nN + n^3)$	Lie group / group of warps

Here $n$ denotes the number of warp parameters, $N$ is the number of template pixels, and $k \ge n$ is the column dimension of the factorized spatial matrix $\Gamma(\mathbf{x})$ in the Inverse Additive formulation.

The Forwards Additive and Forwards Compositional methods recompute the Hessian at every iteration because image gradients must be evaluated on the warped input image. The Inverse Additive and Inverse Compositional methods achieve efficiency by evaluating gradients on the fixed template image, allowing the Hessian to be computed once. While the Inverse Additive formulation is restricted to a small family of warps where Jacobians factor analytically (such as 2D translations, similarity, and affine warps), the Inverse Compositional algorithm generalizes to any set of warps that form a group, including homographies and 3D projective transformations.

Knowl 5 — Classical Forwards Additive Lucas-Kanade Algorithm
algorithm
The classical Lucas-Kanade algorithm minimizes the sum of squared differences between a template image $T(\mathbf{x})$ and an input image $I(\mathbf{x})$ warped by parameter vector $\mathbf{p} \in \mathbb{R}^n$ :

$\min_{\Delta \mathbf{p}} \sum_{\mathbf{x}} \left[ I(\mathbf{W}(\mathbf{x}; \mathbf{p} + \Delta \mathbf{p})) - T(\mathbf{x}) \right]^2$
Input: Template image $T(\mathbf{x})$ , input image $I(\mathbf{x})$ , initial warp parameters $\mathbf{p}$ , convergence threshold $\epsilon > 0$
Output: Converged warp parameters $\mathbf{p}$
repeat
    Warp input image $I$ to compute $I(\mathbf{W}(\mathbf{x}; \mathbf{p}))$
    Compute error image $E(\mathbf{x}) = T(\mathbf{x}) - I(\mathbf{W}(\mathbf{x}; \mathbf{p}))$
    Warp image gradient to template frame $\nabla I = \left.\left(\frac{\partial I}{\partial x}, \frac{\partial I}{\partial y}\right)\right|_{\mathbf{W}(\mathbf{x}; \mathbf{p})}$
    Evaluate warp Jacobian $\frac{\partial \mathbf{W}}{\partial \mathbf{p}}$ at $(\mathbf{x}; \mathbf{p})$
    Compute steepest descent images $\nabla I \frac{\partial \mathbf{W}}{\partial \mathbf{p}}$
    Compute Hessian matrix $H = \sum_{\mathbf{x}} \left[\nabla I \frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right]^T \left[\nabla I \frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right]$
    Compute steepest descent parameter updates $\mathbf{v} = \sum_{\mathbf{x}} \left[\nabla I \frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right]^T E(\mathbf{x})$
    Compute parameter update $\Delta \mathbf{p} = H^{-1} \mathbf{v}$
    Update warp parameters $\mathbf{p} \leftarrow \mathbf{p} + \Delta \mathbf{p}$
until $\|\Delta \mathbf{p}\| \le \epsilon$
return $\mathbf{p}$
Because the gradient $\nabla I$ is evaluated at the moving coordinates $\mathbf{W}(\mathbf{x}; \mathbf{p})$ and the Jacobian $\frac{\partial \mathbf{W}}{\partial \mathbf{p}}$ depends on $\mathbf{p}$ , the Hessian $H$ must be computed and inverted in every iteration, resulting in a per-iteration cost of $O(n^2 N + n^3)$ .
Knowl 6 — Forwards Compositional Image Alignment Algorithm
algorithm
The Forwards Compositional algorithm (Shum and Szeliski) updates warp estimates by composing an incremental warp $\mathbf{W}(\mathbf{x}; \Delta \mathbf{p})$ with the current warp $\mathbf{W}(\mathbf{x}; \mathbf{p})$ , solving:

$\min_{\Delta \mathbf{p}} \sum_{\mathbf{x}} \left[ I(\mathbf{W}(\mathbf{W}(\mathbf{x}; \Delta \mathbf{p}); \mathbf{p})) - T(\mathbf{x}) \right]^2$
Input: Template image $T(\mathbf{x})$ , input image $I(\mathbf{x})$ , initial warp parameters $\mathbf{p}$ , convergence threshold $\epsilon > 0$
Output: Converged warp parameters $\mathbf{p}$
Pre-computation:
Evaluate warp Jacobian $\frac{\partial \mathbf{W}}{\partial \mathbf{p}}$ at $(\mathbf{x}; \mathbf{0})$
Iteration:
repeat
    Warp input image $I$ to compute $I(\mathbf{W}(\mathbf{x}; \mathbf{p}))$
    Compute error image $E(\mathbf{x}) = T(\mathbf{x}) - I(\mathbf{W}(\mathbf{x}; \mathbf{p}))$
    Compute spatial gradient of warped image $\nabla I(\mathbf{W}) = \frac{\partial I(\mathbf{W}(\mathbf{x}; \mathbf{p}))}{\partial \mathbf{x}}$
    Compute steepest descent images $\nabla I(\mathbf{W}) \frac{\partial \mathbf{W}}{\partial \mathbf{p}}$
    Compute Hessian matrix $H = \sum_{\mathbf{x}} \left[\nabla I(\mathbf{W}) \frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right]^T \left[\nabla I(\mathbf{W}) \frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right]$
    Compute steepest descent parameter updates $\mathbf{v} = \sum_{\mathbf{x}} \left[\nabla I(\mathbf{W}) \frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right]^T E(\mathbf{x})$
    Compute parameter update $\Delta \mathbf{p} = H^{-1} \mathbf{v}$
    Update warp $\mathbf{W}(\mathbf{x}; \mathbf{p}) \leftarrow \mathbf{W}(\mathbf{x}; \mathbf{p}) \circ \mathbf{W}(\mathbf{x}; \Delta \mathbf{p})$
until $\|\Delta \mathbf{p}\| \le \epsilon$
return $\mathbf{p}$
The warp Jacobian $\frac{\partial \mathbf{W}}{\partial \mathbf{p}}$ is evaluated at $(\mathbf{x}; \mathbf{0})$ and is precomputed in $O(nN)$ time. However, the image gradient $\nabla I(\mathbf{W})$ changes at each iteration as $\mathbf{p}$ changes, requiring the Hessian $H$ to be formed and inverted every iteration with per-iteration complexity $O(n^2 N + n^3)$ .
Knowl 7 — Inverse Additive Image Alignment (Hager-Belhumeur Method)
model/method
The Inverse Additive algorithm (Hager and Belhumeur) approximates parameter updates in an additive framework while using the fixed template gradient $\nabla T$ instead of the moving input gradient $\nabla I$ . Using the first-order approximation $\nabla I \frac{\partial \mathbf{W}}{\partial \mathbf{x}} \approx \nabla T$ , the linearized least-squares problem is:

$\min_{\Delta \mathbf{p}} \sum_{\mathbf{x}} \left[ T(\mathbf{x}) + \nabla T \left(\frac{\partial \mathbf{W}}{\partial \mathbf{x}}\right)^{-1} \frac{\partial \mathbf{W}}{\partial \mathbf{p}} \Delta \mathbf{p} - I(\mathbf{W}(\mathbf{x}; \mathbf{p})) \right]^2$

To avoid recomputing the Hessian when $\mathbf{p}$ changes, the method requires the Jacobian product to factor into template-dependent and parameter-dependent matrices:

$\left(\frac{\partial \mathbf{W}}{\partial \mathbf{x}}\right)^{-1} \frac{\partial \mathbf{W}}{\partial \mathbf{p}} = \Gamma(\mathbf{x}) \Sigma(\mathbf{p})$

where $\Gamma(\mathbf{x})$ is a $2 \times k$ matrix and $\Sigma(\mathbf{p})$ is a $k \times n$ matrix (with $k = n$ for affine warps). The constant modified Hessian matrix is defined and precomputed as:

$H_* = \sum_{\mathbf{x}} \left[ \nabla T \Gamma(\mathbf{x}) \right]^T \left[ \nabla T \Gamma(\mathbf{x}) \right]$

In each iteration, the parameter update vector is calculated in two steps:

$\Delta \mathbf{p}_* = H_*^{-1} \sum_{\mathbf{x}} \left[ \nabla T \Gamma(\mathbf{x}) \right]^T \left[ I(\mathbf{W}(\mathbf{x}; \mathbf{p})) - T(\mathbf{x}) \right]$

$\mathbf{p} \leftarrow \mathbf{p} - \Sigma(\mathbf{p})^{-1} \Delta \mathbf{p}_*$

This gives a per-iteration cost of $O(nN + kN + k^3)$ , but limits the algorithm to the restricted family of warps that satisfy the Jacobian factorization condition (such as 2D translations, similarity, and affine warps).
Knowl 8 — Inverse Compositional Levenberg-Marquardt Algorithm
algorithm
The Inverse Compositional Levenberg-Marquardt algorithm augments the Gauss-Newton inverse compositional algorithm with a diagonal damping factor $\delta > 0$ to dynamically adjust step size based on whether the alignment error improves.
Input: Template image $T(\mathbf{x})$ , input image $I(\mathbf{x})$ , initial warp parameters $\mathbf{p}$ , initial damping $\delta = 0.01$ , threshold $\epsilon > 0$
Output: Converged warp parameters $\mathbf{p}$
Pre-computation:
Warp $I$ with initial parameters to compute $I(\mathbf{W}(\mathbf{x}; \mathbf{p}))$
Compute initial error $e = \sum_{\mathbf{x}} [I(\mathbf{W}(\mathbf{x}; \mathbf{p})) - T(\mathbf{x})]^2$
Evaluate template gradient $\nabla T(\mathbf{x})$
Evaluate warp Jacobian $\frac{\partial \mathbf{W}}{\partial \mathbf{p}}$ at $(\mathbf{x}; \mathbf{0})$
Compute steepest descent images $\nabla T \frac{\partial \mathbf{W}}{\partial \mathbf{p}}$
Compute Gauss-Newton Hessian $H = \sum_{\mathbf{x}} \left[\nabla T \frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right]^T \left[\nabla T \frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right]$
Iteration:
repeat
    Compute parameter updates $\mathbf{v} = \sum_{\mathbf{x}} \left[\nabla T \frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right]^T [I(\mathbf{W}(\mathbf{x}; \mathbf{p})) - T(\mathbf{x})]$
    Form Levenberg-Marquardt Hessian $H_{LM} = H + \delta \sum_{\mathbf{x}} \operatorname{diag}\left(\left(\nabla T \frac{\partial \mathbf{W}}{\partial p_1}\right)^2, \dots, \left(\nabla T \frac{\partial \mathbf{W}}{\partial p_n}\right)^2\right)$
    Compute $\Delta \mathbf{p} = -H_{LM}^{-1} \mathbf{v}$
    Tentatively update warp $\mathbf{W}_{tent}(\mathbf{x}) = \mathbf{W}(\mathbf{x}; \mathbf{p}) \circ \mathbf{W}(\mathbf{x}; \Delta \mathbf{p})^{-1}$
    Warp image $I$ with $\mathbf{W}_{tent}$ and evaluate tentative error $e_{tent} = \sum_{\mathbf{x}} [I(\mathbf{W}_{tent}(\mathbf{x})) - T(\mathbf{x})]^2$
    if $e_{tent} < e$ then
         $\mathbf{W}(\mathbf{x}; \mathbf{p}) \leftarrow \mathbf{W}_{tent}(\mathbf{x})$
         $e \leftarrow e_{tent}$
         $\delta \leftarrow \delta / 10$
    else
         $\delta \leftarrow \delta \times 10$
until $\|\Delta \mathbf{p}\| \le \epsilon$
return $\mathbf{p}$
The algorithm retains the asymptotic per-iteration complexity of $O(nN + n^3)$ while interpolating between Gauss-Newton (when $\delta \ll 1$ ) and scaled steepest descent (when $\delta \gg 1$ ).
Knowl 9 — Second-Order Newton Approximation in Inverse Compositional Image Alignment
model/method
The full Newton Inverse Compositional algorithm uses a second-order Taylor series expansion of $G(\mathbf{x}; \Delta \mathbf{p}) = \frac{1}{2} [T(\mathbf{W}(\mathbf{x}; \Delta \mathbf{p})) - I(\mathbf{W}(\mathbf{x}; \mathbf{p}))]^2$ with respect to $\Delta \mathbf{p}$ . Evaluated at $\Delta \mathbf{p} = \mathbf{0}$ , the exact Newton Hessian is:

$\frac{\partial^2 G}{\partial \mathbf{p}^2} = \left( \left[ \frac{\partial \mathbf{W}}{\partial \mathbf{p}} \right]^T \frac{\partial^2 T}{\partial \mathbf{x}^2} \left[ \frac{\partial \mathbf{W}}{\partial \mathbf{p}} \right] + \nabla T \left[ \frac{\partial^2 \mathbf{W}}{\partial \mathbf{p}^2} \right] \right) \left[ T(\mathbf{x}) - I(\mathbf{W}(\mathbf{x}; \mathbf{p})) \right] + \left[ \nabla T \frac{\partial \mathbf{W}}{\partial \mathbf{p}} \right]^T \left[ \nabla T \frac{\partial \mathbf{W}}{\partial \mathbf{p}} \right]$

where $\frac{\partial^2 T}{\partial \mathbf{x}^2} = \begin{pmatrix} \frac{\partial^2 T}{\partial x^2} & \frac{\partial^2 T}{\partial x \partial y} \\ \frac{\partial^2 T}{\partial x \partial y} & \frac{\partial^2 T}{\partial y^2} \end{pmatrix}$ is the $2 \times 2$ spatial Hessian of template image $T$ , and $\frac{\partial^2 \mathbf{W}}{\partial \mathbf{p}^2}$ is the second derivative tensor of the warp function.

Because the first term contains the error image $T(\mathbf{x}) - I(\mathbf{W}(\mathbf{x}; \mathbf{p}))$ , which depends on the current parameter vector $\mathbf{p}$ , the full Newton Hessian cannot be precomputed. It must be recomputed in every iteration, raising the per-iteration complexity to $O(n^2 N + n^3)$ . In addition, the numerical noise introduced when estimating second spatial derivatives on real template images degrades empirical convergence compared to the first-order Gauss-Newton Hessian.
Knowl 10 — Empirical Performance of Gradient Descent Approximations in Image Alignment
empirical result
Comparing six gradient descent approximations (Gauss-Newton, Newton, Steepest Descent, Gauss-Newton Diagonal Hessian, Newton Diagonal Hessian, and Levenberg-Marquardt) on affine warps over 5000 random trials reveals substantial performance disparities:
1. Convergence Rate and Frequency: Gauss-Newton and Levenberg-Marquardt achieve the highest frequency of convergence (>90% for initial canonical point perturbations $\le 4.0$ pixels) and fastest convergence speed (converging in 5 to 15 iterations). Levenberg-Marquardt provides no empirical advantage over Gauss-Newton in rate or frequency of convergence.
2. Newton Approximation: The full Newton algorithm converges significantly slower than Gauss-Newton and fails to converge more often, because image noise amplified during second-derivative calculation overwhelms the theoretical benefits of the second-order model.
3. Steepest Descent and Diagonal Hessian: Steepest descent and diagonal Hessian approximations perform poorly when used with naive parameterizations, frequently oscillating or diverging due to poor step-size selection.
4. Sensitivity to Parameterization and Step-Size: Incorporating an explicit Gauss-Newton step-size estimation into diagonal approximations substantially improves convergence. Furthermore, switching from standard affine matrix parameters to a canonical point coordinate parameterization dramatically improves steepest descent and diagonal Hessian methods, whereas Gauss-Newton is essentially invariant to such linear re-parameterizations.
Knowl 11 — Sensitivity of Forwards and Inverse Image Alignment to Image and Template Noise
empirical result
When additive white Gaussian intensity noise (standard deviation $\sigma = 8.0$ gray levels) is introduced into the image data, the exact equivalence between forwards and inverse algorithms breaks down because the theoretical assumption $T(\mathbf{x}) \approx I(\mathbf{W}(\mathbf{x}; \mathbf{p}))$ is perturbed by noise:
1. Noise on the Input Image $I$ only: The inverse algorithms (Inverse Additive and Inverse Compositional) converge faster and with higher frequency than the forwards algorithms, because inverse methods compute spatial derivatives on the clean template $T$ rather than the noisy input image $I$ .
2. Noise on the Template $T$ only: The forwards algorithms (Forwards Additive and Forwards Compositional) outperform the inverse algorithms, because forwards methods compute image derivatives on the clean input image $I$ .
3. Equal Noise on both $I$ and $T$ : The forwards algorithms perform marginally better than the inverse algorithms due to higher-order Taylor series truncation error in the inverse formulation.
When the template $T$ is constructed offline by averaging across multiple aligned images (as in face modeling and active appearance models), the template has a much higher signal-to-noise ratio than the incoming video frames $I$ , making inverse compositional alignment more noise-robust in addition to being faster.
Knowl 12 — Warp Jacobian, Composition, and Inversion for Planar Homographies in Inverse Compositional Alignment
equation
A planar homography is parameterized by 8 parameters $\mathbf{p} = (p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8)^T$ mapping template coordinates $\mathbf{x} = (x, y)^T$ to:

$\mathbf{W}(\mathbf{x}; \mathbf{p}) = \frac{1}{1 + p_7 x + p_8 y} \begin{pmatrix} (1 + p_1)x + p_3 y + p_5 \\ p_2 x + (1 + p_4)y + p_6 \end{pmatrix}$

The $2 \times 8$ warp Jacobian evaluated at $\mathbf{p} = \mathbf{0}$ is:

$\left.\frac{\partial \mathbf{W}}{\partial \mathbf{p}}\right|_{(\mathbf{x}; \mathbf{0})} = \begin{pmatrix} x & 0 & y & 0 & 1 & 0 & -x^2 & -xy \\ 0 & x & 0 & y & 0 & 1 & -xy & -y^2 \end{pmatrix}$

The composition of current parameters $\mathbf{p}$ with incremental parameters $\Delta \mathbf{p}$ yields warp parameters $\mathbf{p}'$ for $\mathbf{W}(\mathbf{x}; \mathbf{p}') = \mathbf{W}(\mathbf{x}; \mathbf{p}) \circ \mathbf{W}(\mathbf{x}; \Delta \mathbf{p})$ with normalizer $K = 1 + p_7 \Delta p_5 + p_8 \Delta p_6$ given by:

$\mathbf{p}' = \frac{1}{K} \begin{pmatrix} p_1 + \Delta p_1 + p_1 \Delta p_1 + p_3 \Delta p_2 + p_5 \Delta p_7 - p_7 \Delta p_5 - p_8 \Delta p_6 \\ p_2 + \Delta p_2 + p_2 \Delta p_1 + p_4 \Delta p_2 + p_6 \Delta p_7 \\ p_3 + \Delta p_3 + p_1 \Delta p_3 + p_3 \Delta p_4 + p_5 \Delta p_8 \\ p_4 + \Delta p_4 + p_2 \Delta p_3 + p_4 \Delta p_4 + p_6 \Delta p_8 - p_7 \Delta p_5 - p_8 \Delta p_6 \\ p_5 + \Delta p_5 + p_1 \Delta p_5 + p_3 \Delta p_6 \\ p_6 + \Delta p_6 + p_2 \Delta p_5 + p_4 \Delta p_6 \\ p_7 + \Delta p_7 + p_7 \Delta p_1 + p_8 \Delta p_2 \\ p_8 + \Delta p_8 + p_7 \Delta p_3 + p_8 \Delta p_4 \end{pmatrix}$

The inverse warp $\mathbf{W}(\mathbf{x}; \mathbf{p})^{-1}$ is parameterized by $\mathbf{p}_{inv} = \frac{1}{\det \cdot [(1 + p_1)(1 + p_4) - p_2 p_3]} \mathbf{u}$ , where $\det = \det\begin{pmatrix} 1 + p_1 & p_3 & p_5 \\ p_2 & 1 + p_4 & p_6 \\ p_7 & p_8 & 1 \end{pmatrix}$ and:

$\mathbf{u} = \begin{pmatrix} 1 + p_4 - p_6 p_8 - \det \cdot [(1 + p_1)(1 + p_4) - p_2 p_3] \\ -p_2 + p_6 p_7 \\ -p_3 + p_5 p_8 \\ 1 + p_1 - p_5 p_7 - \det \cdot [(1 + p_1)(1 + p_4) - p_2 p_3] \\ -p_5 - p_4 p_5 + p_3 p_6 \\ -p_6 - p_1 p_6 + p_2 p_5 \\ -p_7 - p_4 p_7 + p_2 p_8 \\ -p_8 - p_1 p_8 + p_3 p_7 \end{pmatrix}$

Coverage note — Omitted material includes intermediate algebraic derivations of Taylor series expansions, the 2nd-derivative tensor formulas for homography Newton Hessians, and forward-looking discussions of planned companion papers (appearance models, prior distributions, robust error norms, and multi-scale pyramids).

References

1.Baker, S. and Kanade, T. 2000. Limits on super-resolution and how to break them. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 372–379.
2.Baker, S. and Matthews, I. 2001. Equivalence and efficiency of image alignment algorithms. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, vol. 1, pp. 1090–1097.
3.Baker, S. and Matthews, I. 2002. Lucas-kande 20 years on: A unifying framework: Part 1. Technical Report CMU-RI-TR-02-16, Carnegie Mellon University Robotics Institute.
4.Bergen, J.R., Anandan, P., Hanna, K.J., and Hingorani, R. 1992. Hierarchical model-based motion estimation. In Proceedings of the European Conference on Computer Vision, pp. 237–252.
5.Black, M. and Jepson, A. 1998. Eigen-tracking: Robust matching and tracking of articulated objects using a view-based representation. International Journal of Computer Vision, 36(2):101–130.
6.La Cascia, M., Sclaroff, S., and Athitsos, V. 2000. Fast, reliable head tracking under varying illumination: An approach based on registration of texture-mapped 3D models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(6):322–336.
7.Christensen, G.E. and Johnson, H.J. 2001. Image consistent registration. IEEE Transactions on Medical Imaging, 20(7):568–582.
8.Cootes, T.F., Edwards, G.J., and Taylor, C.J. 1998. Active appearance models. In Proceedings of the European Conference on Computer Vision, vol. 2, pp. 484–498.
9.Dellaert, F. and Collins, R. 1999. Fast image-based tracking by selective pixel integration. In Proceedings of the ICCV Workshop on Frame-Rate Vision, pp. 1–22.
10.Gill, P.E., Murray, W., and Wright, M.H. 1986. Practical Optimization. Academic Press.
11.Gleicher, M. 1997. Projective registration with difference decomposition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 331–337.
12.Hager, G.D. and Belhumeur, P.N. 1998. Efficient region tracking with parametric models of geometry and illumination. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(10):1025–1039.
13.Lucas, B. and Kanade, T. 1981. An iterative image registration technique with an application to stereo vision. In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 674–679.
14.Press, W.H., Flannery, B.P., Teukolsky, S.A., and Vetterling, W.T. 1992. Numerical Recipes in C: The Art of Scientific Computing, 2nd edn., Cambridge University Press.
15.Sclaroff, S. and Isidoro, J. 1998. Active blobs. In Proceedings of the 6th IEEE International Conference on Computer Vision, pp. 1146–1153.
16.Shum, H.-Y. and Szeliski, R. 2000. Construction of panoramic image mosaics with global and local alignment. International Journal of Computer Vision, 16(1):63–84.
17.Szeliski, R. and Golland, P. 1998. Stereo matching with transparency and matting. In Proceedings of the 6th IEEE International Conference on Computer Vision, pp. 517–524.

Citation

MLA

Baker, S., and I. Matthews. “Lucas-Kanade 20 Years On: A Unifying Framework”. International Journal of Computer Vision, vol. 56, no. 3, 2004, pp. 221–55, https://doi.org/10.1023/B:VISI.0000011205.11775.fd.

APA

Baker, S., & Matthews, I. (2004). Lucas-Kanade 20 Years On: A Unifying Framework. International Journal of Computer Vision, 56(3), 221–255. https://doi.org/10.1023/B:VISI.0000011205.11775.fd

Chicago

Baker, S., and I. Matthews. 2004. “Lucas-Kanade 20 Years On: A Unifying Framework”. International Journal of Computer Vision 56 (3): 221–55. https://doi.org/10.1023/B:VISI.0000011205.11775.fd.

Harvard

Baker, S. and Matthews, I. (2004) “Lucas-Kanade 20 Years On: A Unifying Framework”, International Journal of Computer Vision, 56(3), pp. 221–255. Available at: https://doi.org/10.1023/B:VISI.0000011205.11775.fd.

Vancouver

1. Baker S, Matthews I (2004) Lucas-Kanade 20 Years On: A Unifying Framework. International Journal of Computer Vision 56:221–255

BibTeX

@article{Baker_2004, title={Lucas-Kanade 20 Years On: A Unifying Framework}, volume={56}, ISSN={1573-1405}, url={http://dx.doi.org/10.1023/B:VISI.0000011205.11775.fd}, DOI={10.1023/b:visi.0000011205.11775.fd}, number={3}, journal={International Journal of Computer Vision}, publisher={Springer Science and Business Media LLC}, author={Baker, Simon and Matthews, Iain}, year={2004}, month=Feb, pages={221–255} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Lucas-Kanade 20 Years On: A Unifying Framework

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Gauss-Newton Inverse Compositional Image Alignment Algorithm

Knowl 2 — Objective Function and Warp Update of the Inverse Compositional Formulation

Knowl 3 — First-Order Equivalence of Image Alignment Formulations

Knowl 4 — Taxonomy, Algebraic Requirements, and Complexity of Image Alignment Approaches

Knowl 5 — Classical Forwards Additive Lucas-Kanade Algorithm

Knowl 6 — Forwards Compositional Image Alignment Algorithm

Knowl 7 — Inverse Additive Image Alignment (Hager-Belhumeur Method)

Knowl 8 — Inverse Compositional Levenberg-Marquardt Algorithm

Knowl 9 — Second-Order Newton Approximation in Inverse Compositional Image Alignment

Knowl 10 — Empirical Performance of Gradient Descent Approximations in Image Alignment

Knowl 11 — Sensitivity of Forwards and Inverse Image Alignment to Image and Template Noise

Knowl 12 — Warp Jacobian, Composition, and Inversion for Planar Homographies in Inverse Compositional Alignment

References

Citation

BibTeX

Access the Paper