Interactive Image Segmentation: From Graph-based Algorithms to Feature-Space Annotation

  • Jordão Bragantini Chan Zuckerberg Biohub
  • Alexandre Xavier Falcão UNICAMP


In recent years, machine learning algorithms that solve problems from a collection of examples (i.e. labeled data), have grown to be the predominant approach for solving computer vision and image processing tasks. These algorithms’ performance is highly correlated with the abundance of examples and their quality, especially methods based on neural networks, which are significantly data-hungry. Notably, image segmentation annotation requires extensive effort to produce high-quality labeling due to the fine-scale of the units (pixels) and resorts to interactive methodologies to provide user assistance. Therefore, improving interactive image segmentation methodologies with the goal of improving data labeling problems is of paramount importance to advance applications of computer vision methods. With this in mind, we investigated the existing literature on interactive image segmentation, contributing to it by introducing novel algorithms that perform the segmentation from markers, contours, and finally proposing a new paradigm for image annotation at scale.


Y. LeCun, L. Bottou, et al., "Gradient-based learning applied to document recognition," Proceedings of the IEEE, vol. 86, no. 11, pp. 2278-2324, 1998.

A. Krizhevsky, I. Sutskever, et al., "Imagenet classification with deep convolutional neural networks," Communications of the ACM, vol. 60, no. 6, pp. 84-90, 2017.

K. He, X. Zhang, et al., "Deep residual learning for image recognition," in IEEE CVPR, 2016, pp. 770-778.

J. Deng, W. Dong, et al., "Imagenet: A large-scale hierarchical image database," in IEEE CVPR, IEEE, 2009, pp. 248-255.

A. Gupta, P. Dollar, et al., "Lvis: A dataset for large vocabulary instance segmentation," in IEEE CVPR, 2019, pp. 5356-5364.

M. Everingham, L. Van Gool, et al., "The pascal visual object classes (voc) challenge," International Journal of Computer Vision, vol. 88, no. 2, pp. 303-338, 2010.

F. Perazzi, J. Pont-Tuset, et al., "A benchmark dataset and evaluation methodology for video object segmentation," in IEEE CVPR, 2016, pp. 724-732.

A. X. Falcão, J. K. Udupa, et al., "User-steered image segmentation paradigms: Live wire and live lane," Graphical models and image processing, vol. 60, no. 4, pp. 233-260, 1998.

A. X. Falcão, J. Stolfi, et al., "The image foresting transform: Theory, algorithms, and applications," IEEE TPAMI, vol. 26, no. 1, pp. 19-29, 2004.

C. Rother, V. Kolmogorov, et al., "Grabcut: Interactive foreground extraction using iterated graph cuts," in ACM Trans. on Graphics, vol. 23, 2004, pp. 309-314.

C. Couprie, L. Grady, et al., "Power watershed: A unifying graph-based optimization framework," IEEE TPAMI, vol. 33, no. 7, pp. 1384-1399, 2011.

L. Castrejon, K. Kundu, et al., "Annotating object instances with a polygon-rnn," in IEEE CVPR, 2017, pp. 5230-5238.

N. Xu, B. Price, et al., "Deep interactive object selection," in IEEE CVPR, 2016, pp. 373-381.

J. Bragantini, S. B. Martins, et al., "Graph-based image segmentation using dynamic trees," in Iberoamerican Congress on Pattern Recognition, Springer, 2018, pp. 470-478.

Z. Li, Q. Chen, et al., "Interactive image segmentation with latent diversity," in IEEE CVPR, 2018, pp. 577-585.

W.-D. Jang and C.-S. Kim, "Interactive image segmentation via backpropagating refinement scheme," in IEEE CVPR, 2019, pp. 5297-5306.

K. Sofiiuk, I. Petrov, et al., "F-brs: Rethinking backpropagating refinement for interactive segmentation," in IEEE CVPR, 2020, pp. 8623- 8632.

T. Kontogianni, M. Gygli, et al., "Continuous adaptation for interactive object segmentation by learning from corrections," in IEEE ECCV, Springer, 2020, pp. 579-596.

S. Zhang, J. H. Liew, et al., "Interactive object segmentation with inside-outside guidance," in IEEE CVPR, 2020, pp. 12 234-12 244.

Z. Lin, Z. Zhang, et al., "Interactive image segmentation with first click attention," in IEEE CVPR, 2020, pp. 13 339-13 348.

J. Bragantini, B. Moura, et al., "Grabber: A tool to improve convergence in interactive image segmentation," Pattern Recognition Letters, vol. 140, pp. 267-273, 2020.

J. Bragantini, A. Falcão, et al., "Rethinking interactive image segmentation: Feature space annotation," Pattern Recognition, 2022.

N. Sofroniew, T. Lambert, et al., Napari/napari: 0.4.12rc2, version v0.4.12rc2, Oct. 2021. DOI: 10.5281/zenodo.5587893. [Online]. Available:

J. Bragantini, "Interactive image segmentation: From graph-based algorithms to feature-space annotation," M.S. thesis, Universidade Estadual de Campinas, Instituto de Computação, 2021.

C. Allène, J.-Y. Audibert, et al., "Some links between extremum spanning forests, watersheds and min-cuts," Image and Vision Computing, vol. 28, no. 10, pp. 1460-1471, 2010.

K. C. Ciesielski and et al., "Path-value functions for which dijkstra's algorithm returns optimal mapping," Journal of Mathematical Imaging and Vision, vol. 60, no. 7, pp. 1-12, 2018.

W. P. Amorim, A. X. Falcão, et al., "Improving semi-supervised learning through optimum connectivity," Pattern Recognition, vol. 60, pp. 72-85, 2016.

Y. Boykov, O. Veksler, et al., "Fast approximate energy minimization via graph cuts," IEEE TPAMI, vol. 23, no. 11, pp. 1222-1239, 2001.

L. Grady, "Random walks for image segmentation," IEEE TPAMI, vol. 28, no. 11, pp. 1768-1783, 2006.

J. Cousty, G. Bertrand, et al., "Watershed cuts: Thinnings, shortest path forests, and topological watersheds," IEEE TPAMI, vol. 32, no. 5, pp. 925-939, 2010.

M. Tang, L. Gorelick, et al., "Grabcut in one cut," in IEEE CVPR, 2013, pp. 1769-1776.

Y. Boykov and V. Kolmogorov, "An experimental comparison of mincut/max-flow algorithms for energy minimization in vision," IEEE TPAMI, vol. 26, no. 9, pp. 1124-1137, 2004.

P. A. V. Miranda and L. A. C. Mansilla, "Oriented image foresting transform segmentation by seed competition," IEEE TIP, vol. 23, no. 1, pp. 389-398, 2014.

C. L. Demario and P. A. Miranda, "Relaxed oriented image foresting transform for seeded image segmentation," in IEEE ICIP, IEEE, 2019, pp. 1520-1524.

A. X. Falcão and F. P. G. Bergo, "Interactive volume segmentation with differential image foresting transforms," IEEE Transactions on Medical Imaging, vol. 23, no. 9, pp. 1100-1108, 2004.

J. Cousty, G. Bertrand, et al., "Watershed cuts: Minimum spanning forests and the drop of water principle," IEEE TPAMI, vol. 31, no. 8, pp. 1362-1374, 2009.

W. Casaca, J. P. Gois, et al., "Laplacian coordinates: Theory and methods for seeded image segmentation," IEEE TPAMI, 2020.

F. Andrade and E. V. Carrera, "Supervised evaluation of seed-based interactive image segmentation algorithms," in Sym. on Signal Processing, Images and Computer Vision, 2015, pp. 1-7.

D. H. Douglas and T. K. Peucker, "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature," Cartographica: the Int. Journal for Geographic Info. and Geovisualization, vol. 10, pp. 112-122, 1973.

D. Martin, C. Fowlkes, et al., "A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics," in IEEE ICCV, IEEE, vol. 2, 2001, pp. 416-423.

K. McGuinness and N. E. O'connor, "A comparative evaluation of interactive segmentation algorithms," Pattern Recognition, vol. 43, no. 2, pp. 434-444, 2010.

R. Benenson, S. Popov, et al., "Large-scale interactive object segmentation with human annotators," in IEEE CVPR, 2019, pp. 11 700-11 709.

D. Acuna, H. Ling, et al., "Efficient interactive annotation of segmentation datasets with polygon-rnn++," in IEEE CVPR, 2018, pp. 859-868.

H. Ling, J. Gao, et al., "Fast interactive object annotation with curvegcn," in IEEE CVPR, 2019, pp. 5257-5266.

J.-J. Liu, Q. Hou, et al., "A simple pooling-based design for real-time salient object detection," in IEEE CVPR, 2019, pp. 3917-3926.

J. Cousty, L. Najman, et al., "Hierarchical segmentations with graphs: Quasi-flat zones, minimum spanning trees, and saliency maps," Journal of Mathematical Imaging and Vision, vol. 60, no. 4, pp. 479-502, 2018.

L. McInnes, J. Healy, et al., "Umap: Uniform manifold approximation and projection for dimension reduction," arXiv preprint arXiv:1802.03426, 2018.

K. Q. Weinberger and L. K. Saul, "Distance metric learning for large margin nearest neighbor classification.," JMLR, vol. 10, no. 2, 2009.

D. Batra, A. Kowdle, et al., "Interactively co-segmentating topically related images with intelligent scribble guidance," International Journal of Computer Vision, vol. 93, no. 3, pp. 273-292, 2011.

X. Sun, C. M. Christoudias, et al., "Free-shape polygonal object localization," in IEEE ECCV, Springer, 2014, pp. 317-332.

A. Bearman, O. Russakovsky, et al., "What's the point: Semantic segmentation with point supervision," in IEEE ECCV, Springer, 2016, pp. 549-565.

M. Cordts, M. Omran, et al., "The cityscapes dataset for semantic urban scene understanding," in IEEE CVPR, 2016, pp. 3213-3223.

A. X. Falcão and J. Bragantini, "The role of optimum connectivity in image segmentation: Can the algorithm learn object information during the process?" In Int. Conf. on Discrete Geometry for Computer Imagery, 2019, pp. 180-194.

S. B. Martins, T. V. Spina, et al., "A multi-object statistical atlas adaptive for deformable registration errors in anomalous medical image segmentation," in SPIE on Medical Imaging: Image Processing, 2017, 101332G-101332G.
BRAGANTINI, Jordão; FALCÃO, Alexandre Xavier. Interactive Image Segmentation: From Graph-based Algorithms to Feature-Space Annotation. In: WORKSHOP DE TESES E DISSERTAÇÕES - CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 35. , 2022, Natal/RN. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 48-54. DOI: