What is Image segmentation?

Segmentation is the process of partitioning an image into a set of meaningful regions for further analysis

One of the oldest and most widely studied problems in computer vision

Region properties to facilitate image segmentation

• Regions should be uniform / homogeneous in some characteristics

• Region interiors should be simple and without holes or missing parts

• Adjacent regions should have significantly different values in terms of the characteristics in which individually they are uniform

• Boundaries of each region should be smooth and spatially accurate

Different levels of region identification and segmentation

Segmentation approaches

• Region based

• Contour based

• Template matching based

• Splitting and merging based

• Global optimisation based

Issues and challenges

• So far there is no single segmentation method working well for all problems

• Special domain knowledge of the application is typically essential for the development of successful computer vision methods for segmentation
• Even within an application domain images may vary widely

Thresholding

Problematic if regions have overlapping intensity distributions

K-Means Clustering

May work if the number of clusters is known a priori

Problematic if the number of clusters is not known a priori

Feature Based Classification

Segmentation by sliding-window patch-wise feature extraction and then classification… requires many examples for training

Region Splitting and Merging

Basic computational approach

• Recursively split the whole image into pieces based on region statistics

• Recursively merge regions together in a hierarchical fashion

• Combine splitting and merging sequentially

Region Splitting and Merging

• The simplest possible technique

– Apply thresholding and then compute connected components

– Rarely sufficient due to lighting and intra-object statistical variations

Connected Components Algorithm

• First pass

N4

N8

– Check each pixel (top-left to bottom-right)

– If an object pixel, check its neighbors (𝑁𝑁 4 or 𝑁𝑁 8 )

– If no neighbors have labels, assign a new label

– If neighbors do have labels, assign the smallest

– Record label equivalences while assigning

Equivalence sets {1,2,6} {3,4,5}

• Second pass

– Check each pixel (top-left to bottom-right)

– Replace each label with its smallest equivalent

– All background pixels default to the zero-label

Region Splitting

• Clustering in the measurement space

– Assume homogeneous regions in the image appear as clusters in measurement space (simple example: the histogram)

– Optimise metrics of intra-region similarity and inter-region dissimilarity

– Clustering can be accomplished by finding the valleys in the space and declaring the intervals between them as the clusters

– Segmentation is mapping the clusters back to the image domain

– Connected components of the cluster labels constitute the segments

Merging by region growing

– Define a similarity measure

– Start from one seed pixel for the region

– Add neighbouring pixels to the region if they are similar

– Repeat previous step until no more pixels are similar

Watershed Segmentation

Based on the analogy of immersion of a topographic surface

Meyer’s flooding algorithm

1) Choose a set of markers to start the flooding. These could be, for example, all local minima. Give each a different label.

2) Put neighbouring pixels of each marker into a priority queue. A pixel with more similar gray value has higher priority.

3) Pop the pixel with the highest priority level from the queue. If the neighbours of the popped pixel that have already been labelled all have the same label, then give the pixel that same label. Put all non-labelled neighbours that have never been in the queue into the queue.

4) Repeat step 3 until the queue is empty.

The resulting non-labelled pixels are the watershed lines

Maximally Stable Extremal Regions

• Basics of maximally stable extremal regions (MSER)

– Connected components characterised by almost uniform intensity surrounded by contrasting background

– Constructed through a process of trying multiple thresholds and analyzing the shape of the connected components

– Selected regions are connected components whose shape remains virtually unchanged over a large set of thresholds.