Automatic user interaction correction via Multi-label Graph cuts

Antonio Hernández-Vela, Carlos Primo, Sergio EscaleraWorkshops @ ICCV 2011 · OpenReview

Abstract

Most applications in image segmentation require user interaction to achieve accurate results. However, users aim to minimize manual labeling effort. This work extends the standard multi-label $\alpha$-expansion Graph Cut algorithm by analyzing user interaction to modify the object model and improve final segmentation. The approach addresses the fact that fast user interactions often introduce pixel errors that confuse object and background models. Results on a multi-label human limb segmentation problem demonstrate high performance compared to the classical $\alpha$-expansion algorithm, even with significant input errors.

Introduction

Interactive segmentation tools, such as "Magic Wand" or "GrabCut," rely on user-provided "seeds"—strokes or points that define foreground and background regions. Traditionally, these algorithms treat seeds as absolute truth, a constraint known as "clamping." In complex scenarios, such as segmenting 14 distinct body parts, user fatigue leads to errors. A single stroke accidentally crossing into the background can corrupt the color model, causing the entire segmentation to fail. This research introduces a "sanity check" within the Multi-label Graph Cut framework to automatically identify and remove these erroneous strokes.

User interaction strokes providing initial seeds for segmentation.

Methodology

The proposed method extends the multi-label $\alpha$-expansion Graph Cut algorithm with an "Interaction Correction" step:

  1. Initial Modeling: Gaussian Mixture Models (GMMs) are constructed for each label based on the user's initial strokes.
  2. Fitness Check: For every labeled pixel, the algorithm calculates the probability of it belonging to its assigned label versus all others.
  3. Pruning: If a pixel's probability of belonging to its assigned label is significantly lower than another label (based on a threshold $\tau$), it is flagged as a likely error and removed from the seed set.
  4. Refinement: GMMs are re-trained using only the "trusted" pixels, and the final segmentation is performed using standard energy minimization.

By relaxing the "clamping" constraint on suspicious pixels, the system allows the optimization phase to re-label them correctly.

Experimental Results

The approach was evaluated using the Human Limb dataset, consisting of 227 images of 25 individuals. The 14 original body part labels were grouped into four categories: upper-body, lower-body, head/hands, and background.

Final multi-label segmentation result after interaction correction.

The correction method was compared against the original Graph Cut algorithm under varying error rates:

  • Perfect Interaction: With zero errors, the proposed method maintains high accuracy (~96.7%), comparable to the original (97.4%).
  • High Error (25%): The proposed method significantly outperforms the original. While the standard algorithm fails due to forced inclusion of noisy pixels, the correction method successfully ignores the noise to maintain quality.
  • Qualitative Performance: Visually, the system successfully ignores "shortcuts" in user strokes, such as background pixels captured between a subject's legs, resulting in cleaner masks.

Discussion and Conclusion

While robust, the system faces limitations at extreme error rates (e.g., 45%), where initial GMMs become too corrupted to distinguish signal from noise. Additionally, the reliance on color-based GMMs makes the system vulnerable to low-contrast or camouflaged environments. Future work could integrate spatial priors or shape information to enhance the fitness check. By acknowledging user fatigue and treating seeds as suggestions rather than absolute constraints, this framework provides a more practical and resilient approach to interactive image segmentation.

Summary updated

Abstract

Most applications in image segmentation requires from user interaction in order to achieve accurate results. However, user wants to achieve the desired segmentation accuracy reducing effort of manual labelling. In this work, we extend standard multi-label α-expansion Graph Cut algorithm so that it analyzes the interaction of the user in order to modify the object model and improve final segmentation of objects. The approach is inspired in the fact that fast user interactions may introduce some pixel errors confusing object and background. Our results with different degrees of user interaction and input errors show high performance of the proposed approach on a multi-label human limb segmentation problem compared with classical α-expansion algorithm.
BibTeX
@inproceedings{hernandezvela2011automatic,
  author = {Antonio Hernández-Vela and Carlos Primo and Sergio Escalera},
  title = {{Automatic user interaction correction via Multi-label Graph cuts}},
  booktitle = {Workshops @ ICCV},
  year = {2011},
  url = {https://openreview.net/forum?id=XfSx5Mu-V0s},
}
Figure