Higher-Order Multicuts for Geometric Model Fitting and Motion Segmentation

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • Evgeny Levinkov - , Bosch Center for Artificial Intelligence (Author)
  • Amirhossein Kardoost - , University of Mannheim (Author)
  • Bjoern Andres - , Chair of Machine Learning for Computer Vision, Center for Systems Biology Dresden (CSBD) (Author)
  • Margret Keuper - , University of Siegen, Max Planck Institute for Informatics (Author)

Abstract

The minimum cost lifted multicut problem is a generalization of the multicut problem (also known as correlation clustering) and is a means to optimizing a decomposition of a graph w.r.t. both positive and negative edge costs. It has been shown to be useful in a large variety of applications in computer vision thanks to the fact 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 (as well as obtaining lower bounds) 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: 1) We define a geometric multiple model fitting, more specifically, a line fitting problem on all triplets of points and group points, that belong to the same line, together. 2) We formulate homography and motion estimation as a geometric model fitting problem where the task is to find groups of points that can be explained by the same geometrical transformation. 3) In motion segmentation our model allows to go from modeling translational motion to euclidean or affine transformations, which improves the segmentation quality in terms of F-measure.

Details

Original languageEnglish
Pages (from-to)608-622
Number of pages15
JournalIEEE transactions on pattern analysis and machine intelligence : TPAMI
Volume45
Issue number1
Publication statusPublished - 7 Feb 2022
Peer-reviewedYes

External IDs

Scopus 85124765427
Mendeley bc4377b9-c524-3724-9314-61064426b25c
unpaywall 10.1109/tpami.2022.3148795
dblp journals/pami/LevinkovKAK23
WOS 000899419900037
ORCID /0000-0001-5036-9162/work/143781898

Keywords

Keywords

  • Combinatorial optimization, Computational modeling, Computer vision, Costs, Data models, Geometric modeling, Motion segmentation, Task analysis, geometric model fitting, higher-order multicut, local search algorithm, motion segmentation, Higher-order multicut, Geometric model fitting, Local search algorithm

Library keywords