%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 %N 1 %P 608--622 %T Higher-order multicuts for geometric model fitting and motion segmentation %V PP %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-09-10T11:56:37.000+0200}, author = {Levinkov, Evgeny and Kardoost, Amirhossein and Andres, Bjoern and Keuper, Margret}, biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/24084956e7302fdc5d5a565b0e3ea7eff/scadsfct}, copyright = {https://creativecommons.org/licenses/by/4.0/legalcode}, interhash = {bad608fdb42f7d174a6796bc15f66fe6}, intrahash = {4084956e7302fdc5d5a565b0e3ea7eff}, journal = {IEEE Trans. Pattern Anal. Mach. Intell.}, keywords = {}, language = {en}, month = feb, number = 1, pages = {608--622}, publisher = {Institute of Electrical and Electronics Engineers (IEEE)}, timestamp = {2024-09-10T15:15:57.000+0200}, title = {Higher-order multicuts for geometric model fitting and motion segmentation}, volume = {PP}, year = 2022 }