Despite its complexity, the minimum cost lifted multicut problem has found a wide range of applications in recent years, such as image and mesh decomposition or multiple object tracking. Its solutions are decompositions of a graph into an optimal number of segments which are optimized w.r.t. a cost function defined on a superset of the edge set. While the currently available solvers for this problem provide high quality solutions in terms of the task to be solved, they can have long computation times for more difficult problem instances. Here, we propose two variants of a heuristic solver (primal feasible heuristic), which greedily generate solutions within a bounded amount of time. Evaluations on image and mesh segmentation benchmarks show the high quality of these solutions.
Codes:
Code for creating "Lifted Multicut Problem"[1]
Solvers:
BEC,
BEC-cutIf you are using these solvers, please cite our paper.
Results:
Image Decomposition [2]
Mesh Segmentation [3]
ISBI 2012 Challenge [4], [5]
References
[1] Keuper, M., Levinkov, E., Bonneel, N., Lavou´e, G., Brox, T., Andres, B.:Efficient decomposition of image and mesh graphs by lifted multicuts. 2015 IEEE Internationa lConference on Computer Vision (ICCV) (2015) 1751-1759
[2] Arbelaez, P., Maire, M., Fowlkes, C., Malik, J.: Contour detection and hierarchical image segmentation. IEEE TPAMI 33(5) (2011)
[3] Chen, X., Golovinskiy, A., Funkhouser, T.: A benchmark for 3D mesh segmentation. ACM Transactions on Graphics (Proc. SIGGRAPH) 28 (2009)
[4] Cardona, A., Saalfeld, S., Preibisch, S., Schmid, B., Cheng, A., Pulokas, J., Tomancak, P., Hartenstein, V.: An integrated micro- and macroarchitectural analysis of the drosophila brain by computer-assisted serial section electron microscopy. PLOS Biology 8 (2010) 1-17
[5] Carreras, I., Turaga, S., Berger, D., San, D., Giusti, A., Gambardella, L., Schmidhuber, J., Laptev, D., Dwivedi, S., Buhmann, J., Liu, T., Seyedhosseini, M., Tasdizen, T., Kamentsky, L., Burget, R., Uher, V., Tan, X., Sun, C., Pham, T., Bas, E., Uzunbas, M., Cardona, A., Schindelin, J., Seung, H.: Crowdsourcing the creation of image segmentation algorithms for connectomics. Frontiers in Neuroanatomy 9 (2015) 1-13