Outlier-Robust Multi-Model Fitting on Quantum Annealers
Saurabh Pandey1,2 Luca Magri3 Federica Arrigoni3 Vladislav Golyanik1 1Max Planck Institute for Informatics, Saarland Informatics Campus 2Saarland University 3Politechnico di Milano CVPR 2025 Workshop on Image Matching (IMW) paper video code dataset
Abstract: Multi-model fitting (MMF) presents a significant challenge in Computer Vision, particularly due to its combinatorial nature. While recent advancements in quantum computing offer promise for addressing NP-hard problems, existing quantum based approaches for model fitting are either limited to a single model or consider multi-model scenarios within outlier-free datasets. This paper introduces a novel approach, the robust quantum multi-model fitting (R-QuMF) algorithm, designed to handle outliers effectively. Our method leverages the intrinsic capabilities of quantum hardware to tackle combinatorial challenges inherent in MMF tasks, and it does not require prior knowledge of the exact number of models, thereby enhancing its practical applicability. By formulating the problem as a maximum set coverage task for adiabatic quantum computers (AQC), R-QuMF outperforms existing quantum techniques, demonstrating superior performance across various synthetic and real-world 3D datasets. Our findings underscore the potential of quantum computing in addressing the complexities of MMF, especially in real-world scenarios with noisy and outlier-prone data.
Overview of the proposed RQuMF method. a multi-model fitting approach that is robust to outliers and admissible to modern quantum annealers. We first sample models that along with the data define the preference matrix P . Next, a QUBO problem is prepared that can be minimised by quantum annealing (after a minor embedding of the logical problem on quantum hardware) or other solvers. Finally, the best solution is selected. R-QuMF outperforms previous quantum-admissible model fitting approaches
This paper addresses the challenge of outlier handling in multi-model fitting and tailors for quantum annealers a new multi-model fitting approach, which we call Robust Quantum Multi-Model Fitting (R-QuMF); In contrast to previous quantum work [1], it accounts for outliers explicitly in the formulation, resulting in a more general approach while exhibiting superior results on real data. Another advantage of our method is that it does not require any prior information about the optimal number of models explaining the data.
- Robustness: R-QuMF, a new approach for outlier-robust fitting of multiple models.
- Quantum Admissible: A formulation compatible with quantum annealers that accounts for outliers explicitly.
- Practical Advantage: Our method does not need any post-processing steps or a number of optimal models in advance as input, which are highly advantageous properties in practice.
[1] Farina et al. "Quantum multimodel fitting", In CVPR, 2023
To gain robustness against outliers, we generalize the QUBO formulation of QuMF[1] by revisiting the maximum set coverage (MSC) problem, allowing adaptive model selection while directly identifying inliers and outliers without requiring a fixed number of models.
- We reformulate the MSC objective from previous MMF approaches, treating uncovered data points as outliers.
- The problem is cast as an integer linear program, aiming to cover as many points as possible using a subset of models.
- This reformulation yields a more flexible and robust objective that is naturally suited for QUBO solvers and quantum annealing
[1] Farina et al. "Quantum multimodel fitting", In CVPR, 2023
Datasets
Fundamental AdelaideRMF real multi-model data
- The fundamental dataset from [2] contains 15 image pairs for fundamental fitting (with atleast two moving objects).
- Only multi-model sequences are evaluated; single-model fitting cases are excluded.
- Sequences have atleast 30% outliers, making the dataset particularly challenging.
Homography AdelaideRMF real multi-model data
- The homography dataset from [2] contains 16 image pairs for homography fitting (with multiple planes).
- Only multi-model sequences are evaluated; single-model fitting cases are excluded.
- Sequences have up to 68% outliers, making the dataset particularly challenging.
Synthetic Polygon Data
- The synthetic dataset consists of five lines arranged in a pentagon, with each line fitting instance containing 30 data points.
- Points are split into inliers (on the lines) and outliers (uniformly distributed).
- Inliers are evenly distributed across the five lines and perturbed with Gaussian noise (standard deviation = 0.01).
Plane Fitting
(on 3D point cloud)
- 3D point cloud obtained from image-based 3D reconstruction.[3]
- The dataset contains 10,812 points.
- Focus is on planar structures within the point cloud.
[2] Wong et al. "Dynamic and hierarchical multi-structure geometric model fitting", ICCV 2011
[3] 3dflow srl. Samantha. https://www.3dflow.net/, 2024.
[3] 3dflow srl. Samantha. https://www.3dflow.net/, 2024.
The experimental evaluation highlights the robustness and scalability of the proposed methods, particularly De-RQuMF, across varying outlier percentages, problem sizes, and deployment settings. In robustness tests where the outlier ratio increases from 0% to 50% while keeping 30 data points and 40 sampled models fixed, QuMF and De-QuMF—being not designed for outlier resistance—show a steep decline in accuracy, often misclassifying outliers as part of weakly supported models. In contrast, RanSaCov, RQuMF, and especially De-RQuMF maintain strong performance under increasing outlier presence, validating their design for robustness.
In scalability experiments with a fixed outlier ratio of 17% and the number of sampled models increasing from 20 to 1000, R-QuMF's misclassification error grows as the problem becomes more complex, while De-RQuMF leverages its decomposition strategy to remain stable and outperform earlier quantum methods. On actual quantum hardware using 30 data points and a model count ranging from 20 to 140 (equivalent to 50 to 120 qubits), RQuMF fails to maintain accuracy beyond 80 models, with error rates exceeding 50%, whereas De-RQuMF consistently keeps error rates below 10%, demonstrating its robustness even on resource-limited quantum systems.
In scalability experiments with a fixed outlier ratio of 17% and the number of sampled models increasing from 20 to 1000, R-QuMF's misclassification error grows as the problem becomes more complex, while De-RQuMF leverages its decomposition strategy to remain stable and outperform earlier quantum methods. On actual quantum hardware using 30 data points and a model count ranging from 20 to 140 (equivalent to 50 to 120 qubits), RQuMF fails to maintain accuracy beyond 80 models, with error rates exceeding 50%, whereas De-RQuMF consistently keeps error rates below 10%, demonstrating its robustness even on resource-limited quantum systems.
Robustness
Scalability
The real-world evaluation on the AdelaideRMF[4] dataset, which includes challenging multi-model fitting tasks involving fundamental matrices and homographies with high outlier rates (often exceeding 30% and reaching up to 68%), further confirms the robustness of RQuMF-based methods.
In outlier-free scenarios, QuMF performs strongly as expected due to its design for clean data, outperforming RQuMF. However, when outliers are present, QuMF’s performance significantly drops, while RQuMF remains robust, demonstrating the necessity of explicit outlier modeling. Post-processing strategies—such as selecting the top k models and assigning unmatched points as outliers—can improve QuMF’s performance but still fail to match RQuMF.
Furthermore, this post-processing relies on knowledge of the true number of models, which is often unavailable in real applications. In contrast, RQuMF naturally infers the appropriate number of models, frequently outperforming other methods in these scenarios.
In outlier-free scenarios, QuMF performs strongly as expected due to its design for clean data, outperforming RQuMF. However, when outliers are present, QuMF’s performance significantly drops, while RQuMF remains robust, demonstrating the necessity of explicit outlier modeling. Post-processing strategies—such as selecting the top k models and assigning unmatched points as outliers—can improve QuMF’s performance but still fail to match RQuMF.
Furthermore, this post-processing relies on knowledge of the true number of models, which is often unavailable in real applications. In contrast, RQuMF naturally infers the appropriate number of models, frequently outperforming other methods in these scenarios.
Fundamental Matrix Fitting
Homography Matrix Fitting
[4] Wong et al. Dynamic and hierarchical multi-structure geometric model fitting. In ICCV, 2021
Finally, the versatility and real-world applicability of the proposed approach are demonstrated through a 3D plane fitting experiment on a large-scale point cloud derived from image-based 3D reconstruction, containing 10,812 points. To target planar structures, 2,000 models were sampled with an inlier threshold of 0.5, and the simulated annealing (SA) solver was employed. The decomposed method, De-RQuMF, successfully identifies multiple distinct planes within the point cloud, showcasing its effectiveness in extracting meaningful geometric primitives in complex 3D environments. While the method shows lower accuracy in fitting non-planar regions, such as cylindrical surfaces, this behavior aligns with its design, which is restricted to planar model sampling. This experiment highlights the method's potential for practical applications in 3D scene understanding and reconstruction tasks.
Plane fitting
Narrated Video
@inproceedings{pandey2025,
title={Outlier-Robust Multi-Model Fitting on Quantum Annealers},
author={Pandey, Saurabh and Magri, Luca and Arrigoni, Federica and Golyanik, Vladislav},
booktitle={Computer Vision and Pattern Recognition (CVPR) Workshops},
year={2025}
}
Saurabh Pandey
saurabh.pandey@mpi-inf.mpg.de
Vladislav Golyanik
golyanik@mpi-inf.mpg.de