Superpixel MRF Image Segmentation

Foreground/background image segmentation using a binary pairwise Markov Random Field defined over a SLIC superpixel graph.

The project demonstrates core probabilistic graphical model concepts, including posterior factorization, unary and pairwise factors, conditional independence, exact MAP inference, approximate marginal inference, uncertainty analysis, Markov blankets, and variable-elimination fill-in.

Key Features

• SLIC superpixel generation and region-adjacency graph construction
• Binary random variable for each superpixel
• Gaussian unary factors based on foreground and background seed colours
• Strong but finite seed constraints
• Contrast-sensitive Potts pairwise factors
• Shared-boundary-length weighting
• Optional boundary-gradient pairwise feature
• Exact MAP estimation using submodular s-t min-cut
• Mean-field approximate marginals
• Boundary-confidence analysis and confidence maps
• Independent superpixel-model comparison
• Non-graph pixelwise colour baseline
• Sensitivity analysis for $\lambda$ and superpixel count
• Colour-only versus colour-plus-gradient feature comparison
• Markov blanket, graph sparsity, and symbolic fill-in analysis
• Automated tests for model correctness and reproducibility
• Strict separation between model construction and ground-truth evaluation

Model

The set of superpixel labels is:

$$X=\{X_1,X_2,\ldots,X_K\}, \qquad X_k\in\{0,1\}.$$

Here, $X_k=0$ denotes background and $X_k=1$ denotes foreground.

Given the input image $I$ and foreground/background seeds $S$, the conditional distribution is factorized as:

$$P(X\mid I,S) = \frac{1}{Z(I,S)} \prod_{k=1}^{K}\phi_k(X_k;I,S) \prod_{(k,l)\in E}\psi_{kl}(X_k,X_l;I).$$

where:

• $\phi_k$ is the unary factor of superpixel $k$
• $\psi_{kl}$ is the pairwise factor between neighbouring superpixels
• $E$ is the region-adjacency edge set
• $Z(I,S)$ is the normalization constant

The equivalent segmentation energy is:

$$E(X) = \sum_{k=1}^{K}D_k(X_k) + \lambda \sum_{(k,l)\in E} w_{kl}\,\mathbb{I}[X_k\neq X_l].$$

where:

• $D_k(X_k)$ is the unary cost derived from seeds and colour features
• $w_{kl}$ is the contrast-sensitive similarity weight between neighbouring superpixels
• $\lambda$ controls the strength of spatial smoothness
• $\mathbb{I}[X_k\neq X_l]$ penalizes different labels on neighbouring regions

The unary terms use Gaussian colour models in the Lab colour space. Seeded superpixels receive strong finite penalties for violating their supplied labels.

The pairwise weights combine shared-boundary length and standardized colour difference:

$$w_{kl} = \frac{L_{kl}}{\widetilde{L}} \exp\left( -\frac{d_{kl}^{2}} {2\sigma_{\mathrm{edge}}^{2}+\epsilon} \right).$$

Because the binary Potts weights are non-negative, the energy is submodular. Therefore, the MAP assignment

$$X^\star = \arg\max_X P(X\mid I,S) = \arg\min_X E(X)$$

is computed exactly using an s-t minimum cut.

Approximate marginal probabilities are estimated using mean-field inference:

$$q_k \approx P(X_k=1\mid I,S).$$

These probabilities are used to generate confidence maps and boundary-confidence statistics.

Installation

python3 -m pip install -r requirements.txt

The project was tested with the pinned package versions in requirements.txt.

Usage

Run the complete experiment:

python3 run.py \
  --data_dir data \
  --config configs/default.yaml \
  --output_dir outputs

The complete pipeline performs:

• image and seed loading
• SLIC superpixel construction
• region-adjacency graph construction
• unary and pairwise factor construction
• exact graph-cut MAP inference
• independent-model inference
• pixelwise colour-baseline inference
• mean-field marginal approximation
• confidence analysis
• $\lambda$ sensitivity experiments
• superpixel-count sensitivity experiments
• pairwise-feature comparisons
• structural PGM analysis
• final evaluation and visualization

A faster run without sensitivity sweeps is available:

python3 run.py \
  --data_dir data \
  --config configs/default.yaml \
  --output_dir smoke_outputs \
  --skip_sweeps

Evaluation masks are loaded only after all segmentation outputs have been generated.

Data Structure

data/
├── images/
│   └── <image_id>.png
├── seeds/
│   └── <image_id>_seeds.json
└── evaluation/
    └── masks/
        └── <image_id>_mask.png

Evaluation masks are used only for final IoU and Dice calculations. They are not used for superpixel generation, seed selection, factor construction, parameter selection, MAP inference, mean-field inference, or sensitivity analysis.

Tests

python3 -m pytest -q tests/

The tests verify:

• image, seed, and configuration handling
• seed validation and superpixel mapping
• Gaussian unary-factor construction
• effective-sample-size correction
• Potts submodularity
• graph-cut MAP correctness
• unary-cost shifting
• mean-field probability bounds and convergence
• boundary-confidence calculations
• Markov blanket and symbolic fill-in analysis
• separation of model construction from evaluation
• reproducible output generation

Project Structure

src/
├── data_io.py
├── superpixels.py
├── factors.py
├── inference_map.py
├── inference_marginal.py
├── baseline_color.py
├── pgm_structural.py
├── metrics.py
├── visualize.py
├── report_plots.py
└── pipeline.py

configs/
└── default.yaml

tests/
├── test_core.py
└── test_pgm_and_reproducibility.py

run.py
requirements.txt

Outputs

The program generates:

• final MRF segmentation masks and overlays
• independent-model masks and overlays
• pixelwise colour-baseline masks and overlays
• superpixel visualizations
• region-adjacency graph visualizations
• mean-field confidence maps
• Markov blanket visualizations
• $\lambda$ sensitivity plots
• superpixel-count sensitivity plots
• feature-set comparison plots
• graph-sparsity summaries
• symbolic fill-in analysis
• runtime and graph-size statistics
• machine-readable metrics in outputs/metrics.csv

Output directories:

outputs/
├── metrics.csv
├── run_log.txt
├── run_manifest.json
├── report_numbers.json
├── summary_figs/
└── <image_id>/

Reports

• report-English.md: complete English report
• report-Persian.md: complete Persian report

Limitations

The model uses a single Gaussian colour model for each class and may struggle when foreground and background have similar colours, multimodal colour distributions, complex textures, weak boundaries, shadows, reflections, or poorly aligned superpixels.

All pixels inside one superpixel receive the same label. Therefore, an incorrectly placed superpixel boundary cannot be repaired by graph-cut inference alone.

The mean-field marginals are approximate and may underestimate posterior uncertainty. A high confidence value represents confidence under the model assumptions and does not guarantee that the predicted label is correct.

The model uses local colour, boundary, and adjacency information. It does not include semantic object recognition, learned deep features, high-order shape factors, or automatic seed generation.