Graph Cut Image Segmentation

A complete image segmentation pipeline using Graph Cut energy minimization, Gaussian Mixture Models (GMMs), and PyMaxflow for interactive foreground/background segmentation.

Course: CSL7360: Computer Vision

Overview

This pipeline implements a robust image segmentation system with the following components:

• Interactive Scribble Annotation: GUI-based foreground/background marking
• GMM-based Color Modeling: Separate Gaussian Mixture Models for foreground and background
• Graph Construction: 4-connected graph with unary (data term) and pairwise (smoothness) terms
• Min-Cut / Max-Flow Optimization: Using PyMaxflow (Boykov–Kolmogorov algorithm)
• Iterative Refinement: Automatic GMM updates based on current segmentation
• Post-Processing: Morphological operations and intensity consistency corrections
• Baseline Comparisons: Otsu thresholding and K-Means segmentation included
• Comprehensive Visualization: Energy convergence plots and segmentation overlays

---

Installation

Prerequisites

• Python 3.8+
• pip or conda

Dependencies

pip install -r requirements.txt

Key packages:

• numpy — Numerical computing
• opencv-python — Image I/O and GUI
• scikit-learn — Gaussian Mixture Models
• pymaxflow — Max-flow/min-cut algorithm
• matplotlib — Visualization
• pillow — Image processing

---

Usage

Basic Command Format

python graph_cut_segmentation.py --images <image_paths> [optional_arguments]

Arguments

Argument	Type	Default	Description
--images	str(s)	Required	Paths to input images (space-separated if multiple)
--output	str	outputs	Output directory for results
--iterations	int	3	Number of iterative GMM refinement steps
--gmm-components	int	5	Number of Gaussian components per GMM model (FG/BG)
--gamma	float	50.0	Smoothness weight (higher = more smoothness)
--max-dim	int	400	Maximum image dimension (preserves aspect ratio)
--auto	flag	—	Enable automatic annotation (no GUI)
--no-interactive	flag	—	Disable interactive GUI entirely

---

Examples

1. Interactive Mode (Recommended for best results)

Open a GUI window to manually annotate foreground/background:

python graph_cut_segmentation.py --images image1.jpg image2.jpg image3.jpg

Controls:

• Left Click + Drag → Mark foreground (green scribbles)
• Right Click + Drag → Mark background (red scribbles)
• 'q' or Enter → Complete annotation and run segmentation
• 'r' → Reset scribbles

---

2. Automatic Mode (Headless, no GUI)

Use automatic center/border annotations instead of manual marking:

python graph_cut_segmentation.py --images image1.jpg --auto

---

3. Custom Parameters

Fine-tune the segmentation with custom settings:

python graph_cut_segmentation.py --images photo.jpg \
    --iterations 5 \
    --gmm-components 7 \
    --gamma 80 \
    --max-dim 1800

Parameter Tuning Guide:

• --iterations: More iterations = better GMM refinement (slower)

  • 2-3: Quick preview
  • 5-7: Balanced quality and speed
  • 10+: High-quality segmentation (slow)

• --gmm-components: More components = better color modeling (trade-off with stability)

  • 3-5: Simple, uniform color regions
  • 5-7: Complex textures
  • 8+: Detailed but may overfit

• --gamma: Controls edge smoothness

  • 10-30: Allow rough boundaries
  • 30-70: Balanced smoothness
  • 70+: Very smooth, contour-like boundaries

• --max-dim: Process speed vs. detail

  • 200-400: Fast (for testing)
  • 600-1200: Balanced
  • 1500+: High-resolution detail (slow)

---

4. Batch Processing Multiple Images

python graph_cut_segmentation.py --images img1.jpg img2.jpg img3.jpg img4.jpg \
    --output segmentation_results \
    --iterations 4 \
    --gamma 60

---

5. High-Quality Segmentation (Resource-Intensive)

python graph_cut_segmentation.py --images image.jpg \
    --max-dim 2000 \
    --iterations 8 \
    --gmm-components 8 \
    --gamma 100 \
    --output high_quality_results

---

Output Structure

Results are saved in the outputs/ directory (or custom --output path):

outputs/
├── image1_segmentation/
│   ├── raw_mask.png              # Unprocessed graph cut result
│   ├── refined_mask.png           # Post-processed mask
│   ├── overlay.png                # Segmentation overlay on original
│   ├── extracted_foreground.png   # Extracted foreground object
│   ├── iteration_energy.png       # Energy convergence graph
│   ├── comparison_otsu.png        # Otsu thresholding baseline
│   ├── comparison_kmeans.png      # K-Means clustering baseline
│   └── annotations_used.png       # Visualization of input scribbles
└── image2_segmentation/
    └── ...

---

Example Results

Image 14 Segmentation Example

Sample segmentation output demonstrating the pipeline's effectiveness:

Segmentation Results: Complete segmentation results showing raw mask, refined mask, and overlay

Refined Mask & Overlay: Final segmentation overlay on the original image

Raw vs Refined Mask:

Energy Convergence: Energy function convergence across iterative refinement steps

---

How It Works

Pipeline Steps

1. Image Loading & Resizing

   • Load image, respect aspect ratio, resize to --max-dim

2. Annotation

   • Interactive: User draws scribbles (or automatic center/border marking)
   • Initialize FG/BG pixel sets from annotations

3. Initial GMM Training

   • Fit separate Gaussian Mixture Models for foreground and background colors
   • Uses pixel colors from annotated regions

4. Graph Construction

   • Create 4-connected graph with pixels as nodes
   • Unary terms: -log(P(color|FG)) and -log(P(color|BG))
   • Pairwise terms: Smoothness weights between adjacent pixels

5. Min-Cut Optimization

   • Use PyMaxflow (Boykov–Kolmogorov) to compute minimum cut
   • Assigns each pixel to either FG or BG

6. Iterative Refinement (repeat --iterations times)

   • Re-estimate GMM parameters from current segmentation
   • Reconstruct graph with updated models
   • Recompute min-cut
   • Track best iteration (lowest energy)

7. Post-Processing

   • Morphological closing (fill small holes)
   • Boundary smoothing
   • Intensity consistency correction

8. Visualization & Comparison

   • Generate overlay, extracted object, and baseline comparisons
   • Plot energy convergence across iterations

---

Algorithm Details

Energy Function

$$E(x) = \sum_{p} D_p(x_p) + \sum_{(p,q)} V_{pq}(x_p, x_q)$$

• $D_p(x_p)$: Data term (negative log-likelihood from GMMs)
• $V_{pq}(x_p, x_q)$: Smoothness term (weighted by color difference and gamma)

Smoothness Weight

$$V_{pq} = \gamma \cdot e^{-||c_p - c_q||^2}$$

• Higher --gamma → stronger smoothness preference
• Color-aware: small difference → high smoothness weight

---

Requirements

See requirements.txt:

numpy
opencv-python
scikit-learn
pymaxflow
matplotlib
pillow

---

System Requirements

• CPU: Multi-core recommended for faster convergence
• RAM: 1-2 GB typically sufficient
• Disk: ~20 MB per high-res image for outputs

Performance Notes

• Interactive mode: Real-time annotation
• Processing time: 10-60 seconds per image (depends on resolution and iterations)
• Headless/auto mode: Fully automated, no user input required

---

Troubleshooting

Issue: Poor segmentation quality

Solutions:

• Increase --iterations (e.g., 5-8)
• Adjust --gamma based on object complexity
• Increase --gmm-components for textured regions
• Draw more/better scribbles covering color variation

Issue: Slow processing

Solutions:

• Reduce --max-dim (e.g., 400-600)
• Decrease --iterations (defaults to 3)
• Use --auto mode (faster than interactive)

Issue: GUI window not opening (headless environment)

Solution:

python graph_cut_segmentation.py --images image.jpg --auto

---

References

• Boykov, Y., & Kolmogorov, V. (2004). "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision"
• Rother, C., Kolmogorov, V., & Blake, A. (2004). "'GrabCut': Interactive Foreground Extraction using Iterated Graph Cuts"
• GMM implementation: scikit-learn
• Max-flow engine: PyMaxflow (Boykov–Kolmogorov)