🤖 AI

Lipschitz Optimization for Formal Verification of Homographies

This paper introduces a formal verification framework that derives tight linear bounds on pixel values under 3D camera motion perturbations by leveraging Lipschitz optimization and piecewise continuity of homographies, thereby enabling the first rigorous robustness guarantees for vision neural networks in planar scenes without relying on complex simulations or surrogate models.

Original authors: Jean-Guillaume Durand, Panagiotis Kouvaros, Maxime Gariel, Alessio Lomuscio

Published 2026-05-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jean-Guillaume Durand, Panagiotis Kouvaros, Maxime Gariel, Alessio Lomuscio

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to drive a car or land a plane. You've given it a "brain" (a neural network) trained to recognize things like stop signs, road markings, or runways. But there's a problem: these brains are fragile. If you slightly change the lighting, the color, or the angle of the photo, the robot might suddenly think a stop sign is a speed limit sign, or that a runway is just grass.

To make sure these robots are safe, we need to prove mathematically that they won't make mistakes, even when things get a little wobbly. This paper introduces a new, super-precise way to do that proof, specifically for when the camera moves around in 3D space.

Here is the breakdown of their work using simple analogies:

1. The Problem: The "Rubber Sheet" vs. The "Real World"

Most current safety checks for AI are like stretching a rubber sheet over a picture. They assume that if you wiggle the pixels a little bit (like changing the brightness or adding static noise), the AI will still work. This is called an " $\ell_p$ -norm" check.

But in the real world, the camera doesn't just wiggle pixels; it moves. If you turn your head (yaw), tilt it (pitch), or move forward, the image changes in a complex, geometric way.

The Paper's Analogy: Imagine a flat piece of paper with a drawing on it. If you just add noise, it's like sprinkling pepper on the paper. But if you move the camera, it's like looking at that paper from a different angle. The drawing gets distorted, stretched, and squashed. The old "rubber sheet" safety checks are too loose; they try to cover this distortion with a giant, fuzzy cloud that includes impossible images (like a stop sign turning into a pizza). This makes the safety check useless because it can't prove the AI is safe.

2. The Solution: The "Magic Map" (Homography)

The authors realized that for many things robots care about—like flat road signs, the ground, or a runway—the distortion caused by moving the camera follows a specific, predictable mathematical rule called a homography.

The Analogy: Think of the camera moving as a magic map. If you know exactly how the camera moved (e.g., "turned 5 degrees to the left"), you can draw a perfect, closed-form map that tells you exactly where every single pixel in the new image came from in the old image. It's not a guess; it's a precise geometric recipe.

3. The Method: "Lipschitz Optimization" (The Speed Limit)

Now that they have the magic map, they need to prove the AI won't get confused. The challenge is that the map is non-linear (it curves and twists), making it hard to calculate the exact limits.

They used a technique called Lipschitz Optimization.

The Analogy: Imagine you are hiking up a mountain (the pixel values) and you want to know the highest point you could possibly reach within a certain area. You don't need to climb every single inch. Instead, you know the mountain has a speed limit (the Lipschitz constant). You know that no matter how steep the path is, you can't climb faster than a certain rate.
By sampling a few points on the mountain and knowing the "speed limit" of the terrain, they can mathematically guarantee that the peak of the mountain (the worst-case pixel value) cannot exceed a certain height. This allows them to draw a tight, accurate box around all possible distorted images.

4. The Results: Faster and Tighter

The team built a tool to do this math automatically.

Speed: They made it 89% faster than previous methods. It's like upgrading from a bicycle to a sports car for these safety checks.
Precision: Their "safety box" is 7% tighter. This means they aren't wasting time checking impossible scenarios. They are checking exactly what can happen.
Discovery: When they tested this on standard AI benchmarks (like recognizing digits or traffic signs), they found that many AI models are very fragile to 3D camera movements. For example, a model trained to recognize traffic signs might fail completely if the camera just tilts slightly, even though it passes all the old "noise" tests.

5. Real-World Test: The Runway

To show this works in a real safety-critical situation, they tested it on a system designed to tell a pilot if a runway is visible.

The Result: The system was found to be very fragile. Under small camera movements (like a slight bump or turn), the system could not guarantee it would correctly identify the runway. This highlights a real vulnerability that needs to be fixed before such AI can be certified for use in aviation.

Summary

In short, this paper says: "Stop guessing how camera movement affects AI. We found a precise mathematical map for it, and we used a 'speed limit' rule to prove exactly how much an AI can be confused by moving cameras. We found that current AI is much more fragile to movement than we thought, and we built a faster, better tool to prove it."

This work is a crucial step toward getting AI certified for safety-critical jobs like flying drones, driving cars, or landing planes, where a wrong guess isn't just an error—it's a disaster.

Technical Summary: Lipschitz Optimization for Formal Verification of Homographies

1. Problem Statement

The deployment of deep neural networks (DNNs) in safety-critical domains such as autonomous driving, aerospace, and healthcare requires formal robustness guarantees. Current formal verification methods primarily focus on $\ell_p$ -norm bounded perturbations (e.g., noise, contrast changes) that act directly on pixel space. However, these approaches fail to adequately model perturbations originating in the physical 3D world, such as camera motion, viewpoint changes, or scene geometry shifts.

While $\ell_p$ -balls can theoretically encompass the resulting images of physical perturbations, they over-approximate the true manifold of perturbed images, leading to loose, uninformative bounds that often fail to prove network robustness. Existing methods for 3D robustness are limited to statistical approaches (weaker guarantees), 2D affine transforms (unable to model perspective effects), or complex simulations requiring explicit 3D scene models. There is a critical gap in formally verifying projective geometry transforms, specifically homographies, which describe the plane-to-plane mapping between different views of a planar surface under 3D camera motion.

2. Methodology

The authors propose a formal verification framework that targets robustness against 3D motion perturbations of the capturing camera, specifically for scenes with predominantly planar structures (e.g., road markings, traffic signs, ground planes).

2.1. Closed-Form Homography Derivation

The method begins by establishing a closed-form mapping from camera pose perturbations to pixel values.

Geometric Modeling: Assuming a pinhole camera model and a planar scene feature (e.g., $z=0$ in the world frame), the authors derive the homography matrix $H(\kappa)$ induced by 6-DOF camera pose perturbations (roll, pitch, yaw, and translation).
Parameterization: The homography is parameterized by a vector $\kappa$ representing the delta in pose relative to a reference camera. For specific scenarios (e.g., pure yaw rotation), the authors derive explicit analytical expressions for $H(\kappa)$ and its inverse $H^{-1}(\kappa)$ .
Pixel Value Function: The value of a transformed pixel $G(\kappa)$ is computed by mapping the transformed coordinates back to the original image via $T^{-1}(\kappa)$ and applying bilinear interpolation. This results in a non-linear function $G(\kappa) = I \circ T^{-1}(\kappa)$ .

2.2. Piecewise-Linear (PWL) Approximation and Lipschitz Optimization

To verify the network, the non-linear function $G(\kappa)$ must be over-approximated by linear bounds that can be propagated through the verifier.

Piecewise-Linear Bounds: The parameter space $B$ is partitioned into subdomains. Within each subdomain, the function $G(\kappa)$ is approximated by linear bounds ($LB$ and $UB$) derived from sampled points, following the approach of Batten et al. [7].
Lipschitz Continuity: To ensure the bounds are sound (i.e., they strictly contain the true function values), the authors analyze the Lipschitz continuity of $G(\kappa)$ . They derive analytical upper bounds for the Lipschitz constant $L$ by computing the gradient of the inverse transform $T^{-1}(\kappa)$ .
Handling Discontinuities: The authors address the non-continuity of the homography inverse at critical angles (where the denominator approaches zero). They define the domain of differentiability $Diff(B)$ and identify candidate locations for maximum gradients (boundaries and specific arctangent values) to compute valid Lipschitz constants.
Optimization: Using Lipschitz optimization, the algorithm iteratively refines the bounds. It evaluates the function at sample points and uses the Lipschitz constant to bound the global maximum of the bound violation. If the bound violation exceeds a threshold $\epsilon$ , the subdomain is split, and the process repeats until convergence.

2.3. Implementation

The method is implemented as a front-end that generates linear bounds for any downstream verifier. The authors adapted the VENUS verifier to handle these piecewise-linear bounds, enhancing its bound-propagation framework to derive pre-activation bounds from linear input constraints rather than fixed intervals.

3. Key Contributions

Formal Verification of Projective Transforms: The paper derives closed-form homographies induced by 6-DOF pose perturbations and demonstrates their compatibility with piecewise-linear constraints and Lipschitz optimization. This enables provably tight bounds on pixel values under non-affine (projective) transforms.
Efficient Implementation: The authors provide an efficient implementation that improves upon the existing PWL algorithm [7]. Enhancements include half-pixel corrections for exact gradients, inclusion of omitted parameter values in the Lipschitz candidate set, dichotomy on the parameter space, and pixel-level parallelization.
Benchmarking and Case Study: The method is evaluated on VNN-COMP benchmarks (MNIST, CIFAR-10, GTSRB) and a real-world runway visibility classifier.

4. Results

Performance Improvements: Compared to a re-implementation of the PWL algorithm [7], the proposed method achieves up to an 89% speedup in runtime and 7% tighter bounds on complex pixel curves. On small transforms, Branch-and-Bound (BaB) iterations were reduced by more than 71%.
Vulnerability Discovery: Evaluation on VNN-COMP benchmarks reveals that networks trained with standard data augmentation (including $\ell_p$ -norm attacks) exhibit systematic weaknesses to 3D geometric perturbations. For instance, GTSRB (autonomous driving) models showed 0% certified robustness to 3D perturbations (roll, pitch, yaw, and translation). Even MNIST and CIFAR models showed significantly lower robustness to pitch, yaw, and translation compared to $\ell_p$ -norm perturbations.
Real-World Case Study: Applied to a runway visibility classifier trained on the LARD dataset, the method certified robustness for only 16% of test images under 10 cm translations and 1% under 1° rotations, highlighting practical vulnerabilities in safety-critical perception systems.
Sensitivity Analysis: The study confirms that certified robustness decreases as the amplitude of the transform increases (e.g., yaw angle), a known challenge in formal verification that requires domain splitting.

5. Significance and Claims

The paper claims to present the first formal verification framework for projective geometry transforms that does not rely on complex simulations, surrogate networks, or explicit image-formation models. By leveraging the analytical tractability of homographies for planar scenes, the authors bridge the gap between 2D affine verification and full 3D scene modeling.

The significance lies in:

Regulatory Compliance: Providing the mathematical guarantees required for certifying AI in safety-critical industries (aviation, autonomous vehicles) where camera motion is a primary source of uncertainty.
Methodological Advancement: Extending Lipschitz optimization and PWL techniques to handle non-affine, perspective-distorting transforms, which were previously considered analytically intractable for formal verification.
Practical Insight: Demonstrating that current state-of-the-art networks are brittle to realistic 3D perturbations, suggesting that robustness training or verification must evolve beyond $\ell_p$ -norm constraints to address physical-world variations.

The authors maintain a modest tone, acknowledging that large transforms exacerbate non-linearities and that the method is currently best suited for predominantly planar scenes with limited parallax and occlusion. They position their work as a principled middle ground for verifying a vast array of use cases in robotics and computer vision.