Higher-Order Ratio Cycles for Fast and Globally Optimal Shape Matching
Authored by Paul Roetzer, Viktoria Ehm, Daniel Cremers, Zorah Lähner, Florian Bernard
Published in IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2025
Abstract
In this work we address various shape matching problems that can be cast as finding cyclic paths in a product graph. This involves for example 2D-3D shape matching, 3D shape matching, or the matching of a contour to a graph. In this context, matchings are typically obtained as the minimum cost cycle in the product graph. Instead, inspired by related works on model-based image segmentation (Schonemann 2009), we consider minimum ratio cycles, which we combine with the recently introduced conjugate product graph in order to allow for higher-order matching costs. With that, on the one hand we avoid the bias of obtaining matchings that involve fewer/shorter edges, while on the other hand being able to impose powerful geometric regularisation, e.g. to avoid zig-zagging. In our experiments we demonstrate that this not only leads to improved matching accuracy in most cases, but also to significantly reduced runtimes (up to two orders of magnitude, depending on the setting).
Resources
Bibtex
@inproceedings{ roetzer2025ratio,
author = { Paul Roetzer and Viktoria Ehm and Daniel Cremers and Zorah Lähner and Florian Bernard },
title = { Higher-Order Ratio Cycles for Fast and Globally Optimal Shape Matching },
booktitle = { IEEE Conference on Computer Vision and Pattern Recognition (CVPR) },
year = { 2025 },
}