Abstract: This survey focuses on a class of methods for image alignment based on a global, iterative optimization. We synthetically describe the existing methods (included the recent Efficient Second Order Method), compare their theoretical aspects, computational costs and implementation issues, and finally present an example of application to 3D tracking, involving a complex, non-linear warp.
Introduction: The Challenge of Dense Alignment
Image alignment is the fundamental process of finding the optimal transformation (warp) that maps a "template" image onto a target "input" image. While many modern computer vision systems rely on "sparse" methods—detecting and matching specific keypoints like corners—dense methods utilize every single pixel in the region of interest.
Dense methods are indispensable when dealing with low-texture surfaces or repetitive patterns where distinct features are scarce. However, they present a significant computational challenge: they require solving non-linear optimization problems over thousands or millions of pixels. This paper clarifies the landscape of these algorithms, comparing their efficiency and accuracy, and extends them to complex 3D scenarios where the warp represents a perspective projection of a 3D object.
Taxonomy of Alignment Methods
The paper categorizes alignment algorithms based on two main criteria: how parameters are updated (Additive vs. Compositional) and the direction of the warp (Forward vs. Inverse).
- Forward Additive (FA): This is the classic Lucas-Kanade approach. While intuitive, it is computationally expensive because the "Hessian" matrix—which guides the optimization—must be recomputed at every iteration as the parameters change.
- Inverse Compositional (IC): Recognized as the efficiency champion, the IC method swaps the roles of the template and the input image. By applying the incremental update to the template rather than the image, the most computationally intensive components (like the Jacobian and Hessian) can be pre-computed once, drastically accelerating the tracking loop.
- Efficient Second-order Method (ESM): A more recent addition to the taxonomy, ESM utilizes a second-order (quadratic) approximation for faster convergence. Remarkably, it achieves second-order accuracy using only first-order derivatives by averaging the Jacobians of the template and the warped image.
- 3D Tracking Warp: The authors extend these concepts beyond 2D homographies to a 3D projective model. This allows for tracking complex 3D objects by estimating the camera's 6-degree-of-freedom pose relative to a known 3D model.
Key Insights and Theoretical Equivalence
- First-Order Equivalence: A major theoretical contribution of the paper is demonstrating that FA, Forward Compositional (FC), and IC algorithms are mathematically equivalent to the first order. Despite different computational costs, they essentially take the same optimization steps.
- The "Inverse" Trick: The realization that warping the template instead of the image makes real-time dense tracking feasible. It transforms a per-iteration bottleneck into a one-time setup cost.
- ESM’s "Free" Accuracy: ESM proves that the benefits of a second-order Taylor expansion can be gained without the cost of second derivatives, simply by averaging gradients from both the template and the image.
Comparative Results
The evaluation focuses on the trade-offs between speed and convergence:
- Speed: The Inverse Compositional (IC) method is the fastest per iteration, with a complexity of $O(nN + n^2)$, where $n$ is the number of parameters and $N$ is the number of pixels.
- Convergence: ESM typically requires the fewest iterations to reach a solution due to its superior quadratic approximation, though each iteration is more computationally demanding ($O(n^2N + n^3)$).
- Robustness: ESM's gradient averaging helps mitigate the influence of image noise, improving overall tracking stability.
Limitations and Future Directions
While powerful, these dense methods have specific requirements. The 3D tracking application depends on a pre-existing 3D model of the scene. Furthermore, the mathematical advantages of ESM rely on certain warp properties that hold perfectly for homographies but only approximately for complex 3D projections. Finally, handling occlusions remains a challenge, as the warp is not continuous near object boundaries, potentially introducing errors if "badly warped" pixels are not filtered.
Summary updated