Higher-Order Multicuts for Geometric Model Fitting and Motion Segmentation

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

  • Evgeny Levinkov - , Bosch Center for Artificial Intelligence (Autor:in)
  • Amirhossein Kardoost - , Universität Mannheim (Autor:in)
  • Bjoern Andres - , Professur für Maschinelles Lernen für Computer Vision, Zentrum für Systembiologie Dresden (CSBD) (Autor:in)
  • Margret Keuper - , Universität Siegen, Max-Planck-Institut für Informatik (Autor:in)

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

OriginalspracheEnglisch
Seiten (von - bis)608-622
Seitenumfang15
FachzeitschriftIEEE transactions on pattern analysis and machine intelligence : TPAMI
Jahrgang45
Ausgabenummer1
PublikationsstatusVeröffentlicht - 7 Feb. 2022
Peer-Review-StatusJa

Externe 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

Schlagworte

Schlagwörter

  • 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

Bibliotheksschlagworte