Abstract
Image alignment refers to finding the best transformation from a fixed reference image to a new image of a scene. This process is often guided by similarity measures between images, computed based on the image data. However, in time-critical applications state-of-the-art methods for computing similarity are too slow. Instead of using all the image data to compute similarity, one can use a subset of pixels to improve the speed, but often this comes at the cost of reduced accuracy. This makes the problem of image alignment a natural application domain for deliberation control using anytime algorithms. However, almost no research has been done in this direction. In this paper, we present anytime versions for the computation of two common image similarity measures: mean squared difference and mutual information. Off-line, we learn a performance profile specific to each measure, which is then used on-line to select the appropriate amount of pixels to process at each optimization step. When tested against existing techniques, our method achieves comparable quality and robustness with significantly less computation.
Introduction
Image alignment, or registration, is a foundational task in medical imaging, remote sensing, and computer vision, involving the identification of the optimal spatial transformation to overlay two images. "Direct" alignment methods typically calculate similarity measures, such as Mutual Information (MI), across every pixel. While accurate, these methods are computationally intensive and often too slow for time-critical applications like surgery or real-time video tracking.
Commonly, researchers employ random pixel subsets to accelerate the process. However, this is usually done using an arbitrary, fixed percentage. This "one-size-fits-all" approach is problematic: insufficient pixels lead to alignment failure, while excessive pixels waste computational resources. This paper introduces a principled framework to navigate this speed-vs-accuracy trade-off by treating similarity measures as "anytime algorithms."
Methodology: Deliberation Control
The proposed framework utilizes anytime algorithms—algorithms that can be stopped at any point to return a valid result, with quality improving over time.
- Anytime Similarity Measures: Standard measures, specifically Mean Squared Difference (MSD) and Mutual Information (MI), are reformulated to be computed incrementally using pixels in a random order.
- Performance Profiles: The system is trained off-line by sampling image pairs to learn the relationship between accuracy, the amount of data used ($p$), and the current state of optimization (gradient magnitude). This results in a lookup table predicting expected accuracy for various computation levels.
- On-line Deliberation: During alignment, the steepest descent optimizer queries the performance profile to determine the minimum number of pixels required to reach a target accuracy (e.g., 90%) for the current step. This allows the algorithm to process fewer pixels when far from the goal and increase precision as it converges.
Experimental Setup
The approach was evaluated across diverse image modalities to ensure generalizability:
- Digital Photos (DP): Standard scenes (e.g., boats, graffiti) for self-alignment and affine transformations.
- Medical Imaging (M1 & M2): T1 and T2 weighted MRI slices and Computed Tomography (CT) scans.
- Earth Observation (EO): Multi-modal patches from Landsat 7 and Radarsat imagery.
Key Insights
A critical finding is the "curved" data requirement: the amount of data needed varies by optimization stage. When images are far apart (high gradient), as little as 1% of pixels can provide sufficient direction. Computational costs for higher pixel density are only necessary during final refinement.
Furthermore, different modalities exhibit different "floors." For instance, MI on medical images requires at least 30% of pixels for reliability, whereas digital photos require much less. The learned performance profiles allow the algorithm to adapt to these inherent differences and avoid the "failure cliffs" associated with fixed-subset methods.
Results and Discussion
Anytime Gradient Descent (AGD) consistently outperformed full-pixel computation in speed. In MI tasks on digital photos, AGD reduced processing time from ~115 seconds to ~15 seconds. In complex satellite data alignment, AGD maintained a low failure rate (~10%), whereas fixed-subset methods (30-50% pixels) saw failure rates between 34% and 51%. AGD effectively combines the speed of sparse sampling with the accuracy of dense sampling.
Conclusion
While the method requires offline training and currently focuses on steepest descent optimizers, it demonstrates significant potential for high-speed, robust image registration. Future work includes extending the framework to 3D volumetric data and real-time surgical navigation.
Summary updated