Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts
Formulations of the Image Decomposition Problem as a Multicut Problem (MP) w.r.t. a superpixel graph have received considerable attention. In contrast, instances of the MP w.r.t. a pixel grid graph have received little attention, firstly, because the MP is NP-hard and instances w.r.t. a pixel grid graph are hard to solve in practice, and, secondly, due to the lack of long-range terms in the objective function of the MP. We propose a generalization of the MP with long-range terms (LMP). We design and implement two efficient algorithms (primal feasible heuristics) for the MP and LMP which allow us to study instances of both problems w.r.t. the pixel grid graphs of the images in the BSDS-500 benchmark. The decompositions we obtain do not differ significantly from the state of the art, suggesting that the LMP is a competitive formulation of the Image Decomposition Problem. To demonstrate the generality of the LMP, we apply it also to the Mesh Decomposition Problem posed by the Princeton benchmark, obtaining state-of-the-art decompositions.
Results
Data
We evaluate performance of our approach on the Berkeley Segmentation Data Set and Benchmarks 500 [1] test set. For each image of the test set we computed boundary probabilities using [2] at twice the original images' resolution to sample interpixel boundary probabilities. Original code outputs edge probabilities per pixel. The format of boundary images is PPM.
We also perform evaluation on the Princeton Segmentation Benchmark [3]. We computed curvatures (minimum, maximum, Gaussian and mean) at two different scales, shape diameter, and dihedral angle. The features are stored per face of the mesh.
You can find original images and meshes together with the corresponding ground truth and evaluation scripts on the benchmarks' web pages.
[1] P. Arbelaez, M. Maire, C. Fowlkes and J. Malik. Contour Detection and Hierarchical Image Segmentation. In TPAMI, 2011
[2] P. Dollar and C. L. Zitnick. Structured forests for fast edge detection. In ICCV, 2013
[3] X. Chen, A. Golovinskiy and Th. Funkhouser. A Benchmark for 3D Mesh Segmentation. In SIGGRAPH, 2009
Code
We base our implementation on the freely-available header-only graph library. The following code contains the latest (at the moment of publication) snapshot of the library and a bunch of command line tools to create, lift, solve, and visualize solutions of multicut problems. The project is organized using cmake and depends on hdf5 library only.
A sample workflow to segment an image as follows:
./boundary-probability-to-mp-image -i 100007.jpg_edges.ppm -o 100007.jpg_edges.h5 -b 0.5
./lift-mp-grid-graph -i 100007.jpg_edges.h5 -o 100007.jpg_edges_lifted.h5 -u 10
./solve-lmp-grid-graph -i 100007.jpg_edges_lifted.h5 -o 100007.jpg_edges_solution.h5 -m KL -I GAEC
./plot-solution-image -i 100007.jpg_edges_solution.h5 -s 100007_edges.svg -p 100007_nodes.ppm
A sample workflow to segment a mesh is as follows:
./boundary-probability-to-mp-mesh -i 2.bin -o 2.h5 -b 0.55
./lift-mp -i 2.h5 -o 2_lifted.h5 -u 70
./solve-lmp -i 2_lifted.h5 -o 2_solution.hdf5 -m KL -I GAEC
./plot-solution-mesh -i 2_solution.h5 -n 2.off -o 2.wrl
You can view the resulting *.wrl file in, for example, MeshLab.