Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Journal Article

Higher-Order Multicuts for Geometric Model Fitting and Motion Segmentation


Keuper,  Margret
Computer Vision and Machine Learning, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Supplementary Material (public)
There is no public supplementary material available

Levinkov, E., Kardoost, A., Andres, B., & Keuper, M. (2023). Higher-Order Multicuts for Geometric Model Fitting and Motion Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1), 608-622. doi:10.1109/TPAMI.2022.3148795.

Cite as: https://hdl.handle.net/21.11116/0000-0009-F784-B
Minimum cost lifted multicut problem is a generalization of the multicut problem and is a means to optimizing a decomposition of a graph w.r.t. both positive and negative edge costs. Its main advantage is that multicut-based formulations do not require the number of components given a priori; instead, it is deduced from the solution. However, the standard multicut cost function is limited to pairwise relationships between nodes, while several important applications either require or can benefit from a higher-order cost function, i.e. hyper-edges. In this paper, we propose a pseudo-boolean formulation for a multiple model fitting problem. It is based on a formulation of any-order minimum cost lifted multicuts, which allows to partition an undirected graph with pairwise connectivity such as to minimize costs defined over any set of hyper-edges. As the proposed formulation is NP-hard and the branch-and-bound algorithm is too slow in practice, we propose an efficient local search algorithm for inference into resulting problems. We demonstrate versatility and effectiveness of our approach in several applications: geometric multiple model fitting, homography and motion estimation, motion segmentation.