Figure 1: Qualitative results of the proposed method for matching 100 FAUST shapes, with guaranteed cycle consistency.


Jointly matching multiple, non-rigidly deformed 3D shapes is a challenging, NP-hard problem. A perfect matching is necessarily cycle-consistent: Following the pairwise point correspondences along several shapes must end up at the starting vertex of the original shape. Unfortunately, existing quantum shape-matching methods do not support multiple shapes and even less cycle consistency. This paper addresses the open challenges and introduces the first quantum-hybrid approach for 3D shape multi-matching; in addition, it is also cycle-consistent. Its iterative formulation is admissible to modern adiabatic quantum hardware and scales linearly with the total number of input shapes. Both these characteristics are achieved by reducing the N-shape case to a sequence of three-shape matchings, the derivation of which is our main technical contribution. Thanks to quantum annealing, high-quality solutions with low energy are retrieved for the intermediate NP-hard objectives. On benchmark datasets, the proposed approach significantly outperforms extensions to multi-shape matching of a previous quantum-hybrid two-shape matching method and is on-par with classical multi-matching methods.

Quantum Annealing

The proposed approach in this paper introduces a novel iterative algorithm that employs a quantum annealer from D-Wave in each step to address the challenges of multi-matching non-rigidly deformed 3D shapes. The algorithm uses a metaheuristic method, quantum annealing, to efficiently search the energy landscape of the cost function. Current generation quantum annealer possess the ability to solve only quadratic unconstrained binary optimization (QUBO) problems. The proposed algorithm converts the Quadratic Assignment Problem with permutation constraints to a QUBO. This method offers a significant improvement over previous quantum-hybrid two-shape matching methods extended to multi-shape matching and is on par with classical multi-matching methods, making it a promising solution for the challenging task of matching multiple non-rigidly deformed 3D shapes.



Figure 2: This demonstrates the progression of point-wise correspondences using our approach. Specifically, we present the outcomes obtained from running the method on a 10 shape FAUST instance for a total of 198 iterations.
Please note that the video may only be supported in chrome.


Figure 3: Quantitative results on all three datasets (left) FAUST, (middle) TOSCA, and (right) SMAL. For each dataset, we match all shapes within a class and then plot the average PCK curve across classes. We plot classical methods with dashed lines as they are only for reference. HKS is our initialisation.

Ours Q-MatchV2-cc Q-MatchV2-nc IsoMuSH ZoomOut HKS
FAUST 0.989 0.886 0.879 0.974 0.886 0.746
TOSCA 0.967 0.932 0.940 0.952 0.864 0.742
SMAL 0.866 0.771 0.813 0.926 0.851 0.544

Table 1: AUC averaged over all classes of each dataset. For reference, we also include classical methods on the right.



BibTeX, 1 KB

  title = {CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes},
  author = {Bhatia, Harshil and Tretschk, Edith and Lähner, Zorah and Benkner, 
	Marcel and Möller, Michael and Theobalt, Christian and Golyanik, Vladislav },
  year = {2023},
  booktitle = {{IEEE Conference on Computer Vision and Pattern Recognition (CVPR)}},
  keywords = {Shape Analysis, Geometry Processing, Shape Correspondence, 
	Multi Shape Matching},


For questions, clarifications, please get in touch with:
Harshil Bhatia,
Vladislav Golyanik

This page is Zotero translator friendly. Page last updated Imprint. Data Protection.