Beyond Pixels: A Comprehensive Survey from Bottom-up to Semantic Image Segmentation and Cosegmentation

• Perceptual grouping motivates segmentation by organizing low-level primitives into compact higher-level structures through principles including proximity, similarity, continuation, closure, and symmetry.Psychological studies also associate part boundaries with negative curvature minima and part salience with relative size, boundary strength, and protrusion.Source: §1 · pp. 2–3
• Image segmentation divides natural images into K non-overlapping meaningful entities and supports annotation, superpixels, recognition, scene parsing, correspondence, and other vision tasks.Superpixels transform millions of pixels into hundreds or thousands of homogeneous regions, reducing model complexity and improving speed or accuracy in several applications.Source: §1 · p. 2
• Defining a meaningful object is ambiguous because it may denote a thing, texture, stuff, or part of another object, while human interpretations can differ.These ambiguities make bottom-up segmentation ill-posed and require a principled definition of what constitutes a good segmentation.Source: §1 · pp. 2–3, Figure 1 · p. 3
• Low-level features such as color, texture, curvature, and convexity capture local properties, remain sensitive to lighting and perspective, and can cause over-segmentation of trivial regions.Fully supervised methods can learn higher-level global cues but are limited to a restricted number of object classes and require per-class labeling.Source: §1 · p. 3
• The survey addresses unresolved challenges in feature representation, model design, and optimization through a comprehensive review of bottom-up segmentation, superpixels, interactive methods, object proposals, semantic parsing, cosegmentation, datasets, metrics, and future directions.It covers these topics across Sections 2–9 because existing reviews are sparse and do not provide comparable breadth.Source: §1 · p. 4

2. Bottom-up methods

• Bottom-up methods group nearby pixels by local color, texture, or curvature homogeneity, using clustering, variational techniques, level sets, or graph partitioning [16][17] [19].The survey divides them into discrete methods operating on fixed image grids and continuous methods treating images as surfaces.Source: §2 · pp. 4–5

2.1. Discrete bottom-up methods

• Discrete methods include parametric K-means clustering, non-parametric mean shift, and watershed segmentation; K-means assumes known cluster counts or spherical distributions, whereas mean shift automatically determines cluster number and modes.Watershed can lead to serious over-segmentation because it associates each region with a local minimum.Source: §2.1 · pp. 5–7

2.2. Continuous methods

• Continuous methods model images as surfaces, including Mumford-Shah, active contours, snakes, level sets [19], and convex-relaxed models.They encourage within-region homogeneity and regular boundaries, but active-contour energies are non-convex and initialization-sensitive; convex relaxation can achieve desirable global optima.Source: §2.2 · pp. 10–11
• Because bottom-up methods rely only on low-level features, obtaining object regions is extremely challenging despite promising combinations of global statistics and convexified Potts modeling.Methods instead either seek object-like regions [10][50] or produce over-segmentation [3].Source: §2.1 · p. 7, §2.2 · p. 11

Motivation

• Superpixels are more perceptually meaningful than pixels, preserving color, texture, structure, and shape cues in homogeneous regions.They over-segment images into regions smaller than objects or their parts, addressing the ambiguity and noise sensitivity of local pixel cues.Source: §3 · p. 11
• Superpixel representations reduce parameters and computation while enabling discriminative region features and longer-range information propagation.Large spatial support facilitates color and texture histograms, while fewer regions ease training and inference compared with pixel-based methods.Source: §3 · p. 12

Superpixel generation paradigms

• Bottom-up methods can be adapted for superpixel over-segmentation by tuning parameters in Watersheds, Normalized Cut, Graph Based Merging, Mean-Shift, and Quick-Shift.The adaptations adjust cluster counts, region sizes, kernel sizes, or mode-drifting behavior.Source: §3 · p. 12
• Localized optimization methods improve speed by processing non-overlapping initial regions and adjusting boundaries toward salient contours; SLIC reaches 5Hz without GPU optimization.The reviewed methods include geometric and geodesic flows, graph-cut patch assignment, pseudo-boolean optimization, and SLIC’s localized K-means procedure.Source: §3 · p. 12

New formulations

• SEED achieves real-time superpixel segmentation at 30Hz using multi-resolution grids, entropy-based objectives, hill-climbing, and boundary refinement.By contrast, Liu et al.’s entropy-rate graph method improves boundary recall but takes about 2.5s on a 480x320 image.Source: §3 · p. 13

4. Interactive methods

• User inputs such as bounding boxes, polygons, contours, or scribbles provide constraints that help segment objects accurately when bottom-up methods lack prior assumptions.Interactive segmentation alternates between user input, algorithmic segmentation, and further user constraints until results are satisfactory; desirable methods minimize manipulation while supporting refinement.Source: §4 · pp. 13–14

4.1. Contour based interactive methods

• Contour-based methods evolve user-placed contours toward salient boundaries using edge functions, shortest paths, global energies, or level sets to handle ambiguous, complex, and fragmented objects.Live-Wire / Intelligent Scissors uses a weighted pixel graph and Dijkstra’s method, while convex active contours and level-set refinement address boundary and topology challenges.Source: §4.1 · pp. 14–15

4.2. Label propagation based methods

• Label-propagation methods spread user-provided labels through global or local optimization, with GraphCut and RandomWalk forming major frameworks.GraphCut models pixel labels in a Markov Random Field, whereas RandomWalk assigns unmarked pixels probabilities based on random-walker reachability from marked nodes; constrained RandomWalk supports hard and soft user constraints.Source: §4.2 · pp. 15, 17
• Segmentation methods incorporate geodesic, convexity, and connectivity priors, while cost-volume filtering achieves comparable or better results with real-time performance and better capture of weak-boundary edges.GrabCut derives unary potentials from foreground and background Gaussian Mixture Models but favors short boundaries; LazySnap adds superpixels and weak-boundary adjustment, while higher-order CRFs capture thin details.Source: §4.2 · pp. 15, 16, 18

Object Proposals

• Object proposals seek a pool of regions likely to cover objects rather than deterministically segmenting each object, distinguishing shaped “things” from homogeneous or patterned “stuff.”This reframing addresses the still-unsolved problem of automatically and precisely segmenting objects.Source: §5 · p. 18

Class-specific object proposals

• Class-specific methods combine detectors such as DPM or Poselets with segmentation refinement, but apply only to limited object classes and cannot scale to thousands of ImageNet categories.Examples include CRF refinement of bounding boxes by Larlus and Jurie and hierarchical regions for detection by Gu et al..Source: §5 · pp. 18–19

Class-independent object proposals

• Class-independent proposals exploit appearance or geometry cues separating objects from background, often generating bottom-up regions and ranking them with pretrained classifiers.CPMC and Category Independent Object Proposal extend GrabCut with different seed-sampling strategies and classifier-based reranking.Source: §5 · p. 19
• Efficiency-focused methods accelerate or replace expensive GrabCut computations using dynamic graph cuts or geodesic distances in GOP, though learned seed placement provides little improvement.GOP uses superpixels, selects seeds by geodesic distance, and applies RankSVM for seed placement.Source: §5 · p. 20

Diversified region proposals

• Diversified region proposal methods generate multi-scale candidate regions through varied hand-crafted strategies without classifier reranking, as in SelectiveSearch and randomized-tree merging by Manen et al..SelectiveSearch varies superpixel initialization and merging similarities, including RGB, intensity, and texture.Source: §5 · p. 20

Overview

• Semantic image parsing divides images into non-overlapping regions belonging to predefined classes and parses the whole scene into “thing” and “stuff” categories.Learned models can predict similar regions in new images, distinguishing semantic parsing from interactive methods and object-region proposals.Source: §6 · p. 21

CRF formulation and pipeline

• Most parsing systems seek the most probable pixel or region labeling in an MRF or CRF, typically combining unary appearance terms, neighborhood pairwise terms, and MAP inference.A common pipeline extracts patch features, trains an appearance model, uses classifier scores as unary terms, defines 4- or 8-connected pairwise terms, and performs graph inference.Source: §6 · pp. 21–22

Features and spatial support

• Feature and spatial-support variants replace hand-crafted pixel features with region, image-level, spatial-layout, or deep learned features, while superpixels reduce variables and lessen noise sensitivity.Superpixel methods also support multiple segmentations, neighbor retrieval, and higher-order consistency between superpixels and their underlying pixels.Source: §6 · pp. 22–23

Context and top-down/bottom-up combination

• Context and top-down cues extend basic CRF smoothness by modeling label co-occurrence, spatial adjacency, appearance, object detectors, and transferred shape masks.Bottom-up information captures homogeneous stuff classes, whereas detectors better capture thing classes; combining them supports holistic scene understanding.Source: §6 · pp. 23–24

Top-down and bottom-up combination

• Tighe et al. transferred training-image masks using exemplar SVMs and achieved state-of-the-art scene parsing results.Their method uses transferred masks as a shape potential for test images.Source: §6 · p. 24

Inference and data-driven parsing

• Inference variants include GraphCut, Belief-Propagation, Primal-Dual methods, fully connected CRFs with fast filtering, and higher-order terms, while data-driven approaches retrieve training images or superpixels instead of retraining classifiers.Retrieval-based methods support open-universe datasets; Tighe et al. reported performance comparable to Liu et al..Source: §6 · p. 24

7. Image Cosegmentation

• Cosegmentation extracts common objects across image sets without pixel- or image-level object annotations, but varying foregrounds, difficult optimization, and diverse application requirements remain central challenges.Its weak shared-object prior enables large-scale dataset segmentation and practical applications, while models must handle multiple images, foreground variation, and scenarios including video and web imagery.Source: §7 · pp. 24–25

7.1. Cosegmentation by extending single-image segmentation models

• Single-image cosegmentation extends conventional single-image segmentation by combining a per-image energy Es, which promotes smooth foreground-background distinction, with Eg, which measures consistency among foregrounds.MRF-based models use varied cosegmentation terms and minimization methods, including submodular-supermodular approximation, squared ℓ2 evaluation, high-order graph matching, and interactive scribble refinement; GraphCut is used for some formulations.Source: §7.1 · pp. 26–27

7.2. New cosegmentation models

• New cosegmentation models formulate shared-object extraction as clustering, graph-based proposal selection, discriminative part or shape learning, composition matching, or low-entropy foreground representation.Examples include spectral and discriminative clustering, graph selection with belief propagation or dynamic programming, latent-SVM part detectors, coskech shape templates, and consensus scoring.Source: §7.2 · pp. 27–28

7.3. New cosegmentation problems

• Emerging problems extend cosegmentation to large-scale, web, classification, multiple-foreground, and recognition settings, using heat diffusion, semi-supervised learning, retrieval, noise rejection, object detectors, and high-order CRFs.Multiple foreground recognition and cosegmentation integrates pixel, contour, and detector cues in a high-order CRF and achieves state-of-the-art performance for MFRC, while later human identification uses geodesic and joint-bilateral shape priors.Source: §7.3 · pp. 29–31

8.1. Datasets

• Crowdsourcing has enabled datasets with millions of images and labels, overcoming the historically high labeling cost that limited datasets to hundreds of images.The survey covers datasets from bottom-up segmentation through holistic scene understanding.Source: §8.1 · p. 31

8.1.1. Single image segmentation datasets

• BSDS provides 200 training, 100 validation, and 200 testing images with annotations from at least three subjects, remaining difficult because of pose variation and background clutter.MSRC-interactive instead contains 50 images with binary ground truth and simulated lasso or rectangle inputs for interactive segmentation.Source: §8.1.1 · p. 31

8.1.2. Cosegmentation datasets

• FlickrMFC is the only dataset for multiple-foreground cosegmentation, comprising 14 manually labeled image groups with 10–20 images each and strong occlusion, lighting, scale, pose, and background variation.Source: §8.1.2 · p. 32

8.1.3. Video segmentation/cosegmentation datasets

• Video datasets progress from restrictive synthetic CVC sequences [146] to SegTrack’s six occluded, deformable, camera-moving videos and MPI’s 11 multi-class videos with around 520 labeled frames.MPI additionally includes lighting, motion-blur, and image-condition variations.Source: §8.1.3 · pp. 32–33

8.1.4. Static scene parsing datasets

• Static scene-parsing datasets span MSRC’s 23 classes and 591 images, PASCAL VOC’s 20 classes and 6,929 segmentations, and COCO’s 328K images with 91 classes.Other resources include LabelMe/SUN, SIFT Flow’s 2,688 labeled images and 33 labels, Stanford background, NYU RGB-depth scenes [151], and class-imbalanced annotations.Source: §8.1.4 · pp. 33–34

8.2. Evaluation metrics

• Evaluation compares algorithm outputs with human-labeled segmentations using boundary matching, region covering, and Variation of Information.Boundary precision is sensitive to over-segmentation, recall to under-segmentation, and boundary evaluation to human-label granularity.Source: §8.2 · pp. 34–35
• Region covering can yield zero error for pixel-level or whole-image segments, while VI’s perceptual meaning and multi-ground-truth use remain unclear and PRI has a small dynamic range [48, 50].Replacing the region-covering minimum with a maximum alleviates the zero-error issue but does not encourage finer segmentation detail.Source: §8.2 · pp. 35–36

9.1. Design flavors

• Segmentation design should be selected according to application needs, after weighing the pros and cons of commonly used alternatives.The review cautions that choices such as using superpixels or additional images depend on the specific setup.Source: §9.1 · pp. 36–37
• Superpixels improve boundary recall, execution time, and feature complexity, but can introduce structure errors; object proposals offer larger support yet retain roughly 60% recall.Pixel or hybrid methods better preserve boundaries, whereas region-based methods favor localization accuracy; multiple over-segmentations or edge-aware filtering can reduce superpixel errors.Source: §9.1 · p. 37
• Extrinsic cues from multiple images can add semantics by reinforcing recurring patterns, but algorithms should prioritize geometric or spatiotemporal constraints and handle noise in heterogeneous data.Such cues include multiview images, video sequences, and large related-image datasets.Source: §9.1 · pp. 37–38
• Hand-crafted features remain a practical first choice, while learned features can improve performance when labelled data are available but require task-specific annotation for transfer.Learned features capture longer-range context and higher-order co-occurrence, whereas hand-crafted features are training-free but may generalize poorly across tasks.Source: §9.1 · p. 38

9.2. Promising future directions

• Future segmentation should exploit motion, depth, 3D geometry, and related images or datasets beyond a single image, including video and depth-camera data.These sources provide complementary internal structures and cross-image information for scene understanding.Source: §9.2 · p. 38
• Instance-aware segmentation should determine how many same-category objects exist, building on detector-CRF methods and instance-labelled Microsoft COCO.Existing methods commonly assign one label to all pixels of a category, limiting instance-level understanding.Source: §9.2 · p. 39
• Holistic systems should combine segmentation with detection, classification, context, geometry, attributes, or language, despite higher inference cost.Combining related tasks has produced more robust and accurate scene analysis than monotone single-task systems.Source: §9.2 · p. 39
• Deep learned multi-layer features have achieved state-of-the-art results across vision tasks, motivating their application to more complex segmentation problems.They may address the limited cross-task generalization of hand-crafted features.Source: §9.2 · p. 39

• The review covers classic bottom-up methods, interactive methods, object region proposals, semantic parsing, and image cosegmentation.Source: §10 · p. 39
• The authors discuss the pros and cons of different methods and suggest design choices and future directions for further exploration.Source: §10 · p. 40
• Despite substantial progress and commercialization in Adobe and Microsoft products, segmentation still lacks the robustness and efficiency required for general practical deployment.Source: §10 · p. 40
• Performance can drop significantly under strong illumination changes, noise corruption, or rain, motivating more effective and robust methods through collaboration across engineering and science communities.Source: §10 · p. 40