Image and Multimedia Data Science Laboratory (IMSCIENCE)
Image and Multimedia Data Science Laboratory (IMScience)

Towards Interactive Image Segmentation by Dynamic and Iterative Spanning Forest


Interactive image segmentation aims to partition the image into background and foreground objects by taking into account seeds inserted by users. Nowadays, many methods are capable of generating segmentations with few user interactions, especially region-based tech- niques. However, such methods are highly sensitive to seed displacement and quantity, and delineation errors are often propagated to the final segmentation result. Recently, a novel superpixel segmentation framework, named Dynamic and Iterative Spanning Forest (DISF), was proposed, which achieved top delineation performance while assessing many seed-based state-of-the-art methods’ drawbacks. In this work, we propose interactive DISF (iDISF), an interactive segmentation framework, by modifying each step of DISF to consider user-validated information. DISF uses the Image Foresting Transform (IFT) framework for computing an optimum-path forest rooted in a seed set in the delineation step. To consider path and image gradient variation, we propose three new connectivity functions for the IFT. Finally, we also propose two new seed removal strategies for detecting relevant seeds for subsequent iterations. Results show segmentation improvements for minimal user effort - i.e., a single click - and show theoretical advances that may benefit recent optimum-path-based interactive methods from scribbles.

Interactive DISF


From scribbles inside and outside the desired object, the Interactive DISF performs an oversampling of background seeds and calculates an optimum-path forest rooted at the seeds, removing the less relevant ones at each iteration. For seed removal, we propose two strategies, in which the first considers the distance from superpixels to the scribbles, and the second takes into account the superpixel position on the object’s border. Alongside this, we propose three connectivity functions with a dynamic trees approach considering the local gradient and the contrast of the image.

Experimental Setup

We evaluated our algorithm with the following methods:

Image Foresting Transform (IFT) with dynamic function Dynamic and Iterative Spanning Forest (DISF)
Bragantini et al. Graph-Based Image Segmentation Using Dynamic Trees Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, 2019. Belém et al. “Superpixel segmentation using dynamic and iterative spanning forest.” IEEE Signal Processing Letters, 2020.

We performed two experiments:

Minimal user effort Foreground and background scribbles
Private dataset, called Parasites, with 77 optical microscopy images of helminth eggs.
Images have background regions similar to eggs that may be connected to them.
Public dataset, called GeoStar, with 151 natural images and user-drawn scribbles.
Gulshan et al. “Geodesic star convexity for interactive image segmentation.” IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2010

We evaluated the methods using the following metrics:

For more details on these metrics, see: Pont-Tuset and Marques. “Measures and meta-measures for the supervised evaluation of image segmentation.” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2013.


Evaluation with scribbles

Qualitative results on GeoStar

Due to the background seed oversampling, iDISF increases the seed competition and, therefore, is capable of preventing major object and background leaks, and, therefore, achieving better delineation than the baseline. The images show that inclusion of gradient information can further improve delineation by preventing leakings.

Evaluation with minimal user effort

Quantitative results on Parasites

iDISF is capable of effectively separate the egg from its attached impurity, differently from DISF with a posteriori superpixel selection. As it can be seen in the table, both iDISF can be significantly more effective than DISF irrespective the initial number of grid samples.

Publication & Code


The iDISF implementation and a tool for interactive image segmentation are available in iDISF repository, on github.


If this work was useful for your research, please cite our paper:

  title={Towards Interactive Image Segmentation by Dynamic and Iterative Spanning Forest},
  author={Barcelos, Isabela Borlido and Bel{\'e}m, Felipe and Miranda, Paulo and Falc{\~a}o, Alexandre Xavier and do Patroc{\'\i}nio, Zenilton KG and Guimar{\~a}es, Silvio Jamil F},
  booktitle={International Conference on Discrete Geometry and Mathematical Morphology},
  publisher={Springer International Publishing},


Please, feel free to contact the authors for any unexpected behavior you might face (e.g., bugs). Moreover, if you’re interested in using our code, we appreciate if you cite this work in your project.