%0 Journal Article %1 Levinkov2022-nm %A Levinkov, Evgeny %A Kardoost, Amirhossein %A Andres, Bjoern %A Keuper, Margret %D 2022 %I Institute of Electrical and Electronics Engineers (IEEE) %J IEEE Trans. Pattern Anal. Mach. Intell. %K from:scadsfct topic_visualcomputing %N 1 %P 608--622 %R 10.1109/TPAMI.2022.3148795 %T Higher-order multicuts for geometric model fitting and motion segmentation %V 45 %X 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.

@article{Levinkov2022-nm, abstract = {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.}, added-at = {2024-11-29T12:20:24.000+0100}, author = {Levinkov, Evgeny and Kardoost, Amirhossein and Andres, Bjoern and Keuper, Margret}, biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/26080fa97ef4211a5e390b9af9d0283e9/scads.ai}, copyright = {https://creativecommons.org/licenses/by/4.0/legalcode}, doi = {10.1109/TPAMI.2022.3148795}, interhash = {bad608fdb42f7d174a6796bc15f66fe6}, intrahash = {6080fa97ef4211a5e390b9af9d0283e9}, journal = {IEEE Trans. Pattern Anal. Mach. Intell.}, keywords = {from:scadsfct topic_visualcomputing}, language = {en}, month = feb, number = 1, pages = {608--622}, publisher = {Institute of Electrical and Electronics Engineers (IEEE)}, timestamp = {2024-11-29T12:20:24.000+0100}, title = {Higher-order multicuts for geometric model fitting and motion segmentation}, volume = 45, year = 2022 }