An Efficient Fusion Move Algorithm for the Minimum Cost Lifted Multicut Problem
Many computer vision problems can be cast as an optimization problem whose feasible solutions are decompositions of a graph. The minimum cost lifted multicut problem is such an optimization problem. Its objective function can penalize or reward all decomp
- PDF / 5,370,304 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 94 Downloads / 210 Views
I/IWR, University of Heidelberg, Heidelberg, Germany {thorsten.beier,ullrich.koethe,fred.hamprecht}@iwr.uni-heidelberg.de 2 Computer Vision and Multimodal Computing, Max Planck Institute for Informatics, Saarbr¨ ucken, Germany [email protected]
Abstract. Many computer vision problems can be cast as an optimization problem whose feasible solutions are decompositions of a graph. The minimum cost lifted multicut problem is such an optimization problem. Its objective function can penalize or reward all decompositions for which any given pair of nodes are in distinct components. While this property has many potential applications, such applications are hampered by the fact that the problem is NP-hard. We propose a fusion move algorithm for computing feasible solutions, better and more efficiently than existing algorithms. We demonstrate this and applications to image segmentation, obtaining a new state of the art for a problem in biological image analysis.
1
Introduction and Related Work
In 2011, Andres et al. [1], Bagon and Galun [2], Kim et al. [3,4] and Yarkony et al. [5] independently proposed formulating the image segmentation problem [6] as a minimum cost multicut problem [7,8] on a suitable graph. Given, for every pair of neighboring nodes, a cost or reward (negative cost) to be paid if these nodes are assigned to distinct components, the minimum cost multicut problem consists in finding a decomposition of the graph with minimal sum of costs. In 2015, Keuper et al. [9], using a construction from [10], proposed the minimum cost lifted multicut problem, a generalization with an identical feasible set whose objective function can assign a cost or reward to every pair of nodes, not just neighboring ones. These non-local interactions are represented in the graph by “lifted” edges which are subjected to slightly different constraints than the regular edges. The introduction of lifted edges is appealing for image segmentation, because non-local interactions can now be added without losing two key advantages of the multicut: (i) Every feasible solution of the optimization problem corresponds to a decomposition of the graph, i.e. to a consistent segmentation. (ii) No assumptions on the number or size of segments are made, making the method applicable in the typical and important scenario where such prior knowledge is not available. Since standard and lifted multicut are both NPhard integer linear programming problems [7,8] – even for planar graphs [11,12] c Springer International Publishing AG 2016 B. Leibe et al. (Eds.): ECCV 2016, Part II, LNCS 9906, pp. 715–730, 2016. DOI: 10.1007/978-3-319-46475-6 44
716
T. Beier et al.
– this paper proposes a new family of efficient heuristics inspired by [13,14] and on the basis of fusion moves [14,15]. So far, the computer vision community has studied three classes of algorithms addressing optimization problems of this type: (i) branch-and-cut algorithms [1,16,17] that converge to an optimal integer solution but do not admit polynomial time complexity bounds and are too slow
Data Loading...
