1. MMC
  2. All Volumes and Issues
  3. Volume 12, Number 4, 2025
  4. Interactive Image Segmentation Using Dominant Sets and Pairwise Constraints

Interactive Image Segmentation Using Dominant Sets and Pairwise Constraints

MMC.
2025;
Volume 12, Number 4
: pp. 1415–1420
Received: May 24, 2025
Revised: December 11, 2025
Accepted: December 18, 2025

Mansouri A., Aouragh M. D.  Interactive Image Segmentation Using Dominant Sets and Pairwise Constraints.  Mathematical Modeling and Computing. Vol. 12, No. 4, pp. 1415–1420 (2025)

Authors:
  1. A. Mansouri
  2. M. D. Aouragh
1
AM2CSI Group, MSISI Laboratory, FST Errachidia, Moulay-Ismaïl University of Meknès
2
AFAA Group, EST Meknès, Moulay-Ismaïl University of Meknès

Image segmentation remains a challenging problem in computer vision.  Among the various techniques, graph-based methods have become increasingly popular, with modern approaches often incorporating some form of user interaction.  Following this trend, we propose a new approach to interactive image segmentation based on dominant sets, which generalize the concept of maximal cliques to edge-weighted graphs.  In particular, we extend this framework to handle pairwise constraints.  By expressing the user-provided scribbles as must-link and cannot-link constraints, we are able to accurately extract the object of interest.  Experimental results demonstrate that our method achieves higher segmentation accuracy and lower computational time compared to previous approaches.

dominant set
interactive image segmentation
pairwise constraints
superpixels
  1. Rother C., Kolmogorov V., Blake A.  "Grabcut": interactive foreground extraction using iterated graph cuts.  ACM Transactions on Graphics.  23 (3), 309–314 (2004).
  2. Lempitsky V. S., Kohli P., Rother C., Sharp T.  Image segmentation with a bounding box prior.  2009 IEEE 12th International Conference on Computer Vision.  277–284 (2009).
  3. Li Y., Sun J., Tang C.-K., Shum H.-Y.  Lazy snapping.  ACM Transactions on Graphics.  23 (3), 303–308 (2004).
  4. Protiere A., Sapiro G.  Interactive image segmentation via adaptive weighted distances.  IEEE Transactions on Image Processing.  16 (4), 1046–1057 (2007).
  5. Boykov Y. Y., Jolly M.-P.  Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images.  Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001.  105–112 (2001).
  6. Bai X., Sapiro G.  A Geodesic Framework for Fast Interactive Image and Video Segmentation and Matting.  2007 IEEE 11th International Conference on Computer Vision.  1–8 (2007).
  7. Mortensen E. N., Barrett W. A.  Interactive Segmentation with Intelligent Scissors.  Graphical Models and Image Processing.  60 (5), 349–384 (1998).
  8. Peng B., Zhang L., Zhang D.  A survey of graph theoretical approaches to image segmentation.  Pattern Recognition.  46 (3), 1020–1038 (2013).
  9. Grady L.  Random Walks for Image Segmentation.  IEEE Transactions on Pattern Analysis and Machine Intelligence.  28 (11), 1768–1783 (2006).
  10. Pavan M., Pelillo M.  Dominant Sets and Pairwise Clustering.  IEEE Transactions on Pattern Analysis and Machine Intelligence.  29 (1), 167–172 (2007).
  11. Pavan M., Pelillo M.  A new graph-theoretic approach to clustering and segmentation.  2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.  145–152 (2003).
  12. Pavan M., Pelillo M.  Unsupervised texture segmentation by dominant sets and game dynamics.  12th International Conference on Image Analysis and Processing, 2003. 302–307 (2003).
  13. Wagstaff K., Cardie C., Rogers S., Schroedl S.  Constrained k-means clustering with background knowledge.  ICML '01: Proceedings of the Eighteenth International Conference on Machine Learning.  577–584 (2001).
  14. Chew S. E., Cahill N. D.  Semi-Supervised Normalized Cuts for Image Segmentation.  2015 IEEE International Conference on Computer Vision (ICCV). 1716–1723 (2015).
  15. Shi J., Malik J.  Normalized cuts and image segmentation.  IEEE Transactions on Pattern Analysis and Machine Intelligence.  22 (8), 888–905 (2000).
  16. Noma A., Graciano A. B. V., Cesar R. M., Consularo L. A., Bloch I.  Interactive image segmentation by matching attributed relational graphs.  Pattern Recognition.  45 (3), 1159–1179 (2012).
  17. Vincent L., Soille P.  Watersheds in digital spaces: an efficient algorithm based on immersion simulations.  IEEE Transactions on Pattern Analysis and Machine Intelligence.  13 (6), 583–598 (1991).
  18. Ning J. F., Zhang L., Zhang D., Wu C.  Interactive image segmentation by maximal similarity based region merging.  Pattern Recognition.  43 (2), 445–456 (2010).
  19. Liu D., Pulli K., Shapiro L. G., Xiong Y.  Fast interactive image segmentation by discriminative clustering.  MCMC '10: Proceedings of the 2010 ACM multimedia workshop on Mobile cloud media computing.  47–52 (2010).
  20. Comaniciu D., Meer P.  Mean shift: a robust approach toward feature space analysis.  IEEE Transactions on Pattern Analysis and Machine Intelligence.  24 (5), 603–619 (2002).
  21. Achanta R., Shaji A., Smith K., Lucchi A., Fua P., Süsstrunk S.  SLIC Superpixels Compared to State-of-the-Art Superpixel Methods.  IEEE Transactions on Pattern Analysis and Machine Intelligence.  34 (11), 2274–2282 (2012).