PRISE: Demystifying Deep Lucas-Kanade with Strongly Star-Convex Constraints for Multimodel Image Alignment

Yiqing Zhang, Xinming Huang, Ziming Zhang

Abstract: The Lucas-Kanade (LK) method is a classic iterative homography estimation algorithm for image alignment, but often suffers from poor local optimality especially when image pairs have large distortions. To address this challenge, in this paper we propose a novel Deep Star-Convexified Lucas-Kanade (PRISE) method for multimodel image alignment by introducing strongly star-convex constraints into the optimization problem. Our basic idea is to enforce the neural network to approximately learn a star-convex loss landscape around the ground truth give any data to facilitate the convergence of the LK method to the ground truth through the high dimensional space defined by the network. This leads to a minimax learning problem, with contrastive (hinge) losses due to the definition of strong star-convexity that are appended to the original loss for training. We also provide an efficient sampling based algorithm to leverage the training cost, as well as some analysis on the quality of the solutions from PRISE. We further evaluate our approach on benchmark datasets such as MSCOCO, GoogleEarth, and GoogleMap, and demonstrate state-of-the-art results, especially for small pixel errors.

Introduction

Image alignment—specifically estimating the homography (transformation matrix) between two images—is a cornerstone of computer vision. While the classic Lucas-Kanade (LK) algorithm is explainable and efficient, it is notoriously sensitive to local minima. If the initial guess is slightly off or the images have large distortions, LK often gets "stuck" in the wrong place. This problem is amplified in multimodal alignment, such as matching a satellite photo to a stylized map. Recent "Deep LK" approaches have attempted to solve this by mapping images into a shared feature space, but these methods often rely on heuristics to ensure the optimization landscape is well-behaved. PRISE (Deep Star-Convexified Lucas-Kanade) demystifies these heuristics by providing a mathematically grounded way to reshape the loss landscape for guaranteed convergence.

Reshaping the Loss Landscape with Star-Convexity

The core innovation of PRISE is the introduction of Strongly Star-Convex Constraints into the deep learning objective. A function is star-convex if its global minimum is "visible" from every other point via a straight, downhill path. While weaker than global convexity, star-convexity is more achievable in high-dimensional neural networks and still guarantees that gradient descent (or the iterative LK solver) will find the optimum.

Conceptual illustration of a star-convex loss landscape where the global minimum $\omega^*$ is reachable from any point $\omega$ via a monotonic path.

PRISE uses a Siamese neural network to transform source and target images into feature maps. The network's primary job is to reshape the math of the problem so that the LK solver cannot fail. This is achieved through two specific geometric constraints implemented as hinge losses:

  1. Condition 1: Forces the loss landscape to have a quadratic "lower envelope" centered at the ground truth.
  2. Condition 2: Imposes strong convexity on all paths connecting any point in the landscape to the ground truth.

Minimax Training and Implementation

To enforce these constraints, the authors employ a sampling-based adversarial training strategy. The model "probes" the area around the ground truth to find points that violate star-convexity rules and penalizes the network accordingly. Ablation studies revealed that Condition 1 (the quadratic envelope) is the most critical regularizer, preventing the network from overfitting to "bumpy" landscapes with multiple local pits. This approach ensures that the neural network learns to produce a smooth, monotonic "sink" toward the correct alignment.

Experimental Results

The authors evaluated PRISE on three challenging benchmarks: MSCOCO (natural images), GoogleEarth (multi-temporal satellite imagery), and GoogleMap (multimodal satellite-to-map alignment).

Performance comparison on the GoogleMap dataset. PRISE (red) significantly outperforms DeepLK (orange) and other variants, particularly at high-precision thresholds (Pixel Error < 1).

PRISE achieved state-of-the-art (SOTA) results across all datasets, with the most dramatic gains in high-precision metrics. On the difficult GoogleMap task, PRISE achieved a success rate of 56.93% at a threshold of Pixel Error (PE) < 1, compared to only 16.80% for the previous SOTA, DeepLK. On MSCOCO, PRISE reached a success rate of 97.29% for PE < 1, compared to 92.81% for DeepLK. These results highlight PRISE's superior ability to "fine-tune" alignment to sub-pixel levels.

Conclusion

By creating a star-convex "bowl" around the ground truth, PRISE ensures that simple iterative solvers like Lucas-Kanade can reliably find the optimal transformation. While the sampling-based training adds some overhead, it does not affect inference speed. The authors suggest that this "star-convexification" framework could generalize to other non-convex optimization problems in vision, such as 3D point cloud registration or optical flow estimation.

Summary updated

Abstract

The Lucas-Kanade (LK) method is a classic iterative homography estimation algorithm for image alignment, but often suffers from poor local optimality especially when image pairs have large distortions. To address this challenge, in this paper we propose a novel Deep Star-Convexified Lucas-Kanade (PRISE) method for multimodel image alignment by introducing strongly star-convex constraints into the optimization problem. Our basic idea is to enforce the neural network to approximately learn a star-convex loss landscape around the ground truth give any data to facilitate the convergence of the LK method to the ground truth through the high dimensional space defined by the network. This leads to a minimax learning problem, with contrastive (hinge) losses due to the definition of strong star-convexity that are appended to the original loss for training. We also provide an efficient sampling based algorithm to leverage the training cost, as well as some analysis on the quality of the solutions from PRISE. We further evaluate our approach on benchmark datasets such as MSCOCO, GoogleEarth, and GoogleMap, and demonstrate state-of-the-art results, especially for small pixel errors. Code can be downloaded from https://github.com/Zhang-VISLab.
BibTeX
@inproceedings{zhang2023prise,
  author = {Yiqing Zhang and Xinming Huang and Ziming Zhang},
  title = {{PRISE: Demystifying Deep Lucas-Kanade with Strongly Star-Convex Constraints for Multimodel Image Alignment}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2023},
  url = {https://openreview.net/forum?id=gTm8Fh4YwZ},
}
Figure