Segmentation: Principles and Basic Techniques (Part II)

Thresholding

• Object of interest has different intensity values than background.
• Segmentation $s$ of image $f$ by threshold $t$ at pixel/voxel $v$.
• Interactive thresholding allows separation into different regions with multiple thresholds.
• Connected Component Analysis (CCA) labels foreground regions to identify the object of interest.
• Automatic thresholding assumes bimodal histogram with threshold between peaks; noise can cause local maxima/minima.

Otsu’s Method

• Iterative procedure to find optimal threshold $t$ for normalized histogram $h$.
• Maximizes ratio $\lambda(t) = qb(t)/qw (t)$, where $qb$ is between-class scatter and $qw$ is within-class scatter.
• Computes within-class scatter $qw(t)$ from gray-level variances $\sigma^2<em>0(t)$ and $\sigma^2</em>1(t)$.
• Calculates between-class scatter $qb(t)$ using weighted sum of variances of expected values.
• Optimal threshold found by exhaustive search.

Zack’s Algorithm

• Threshold defined where the distance of a curve through the histogram from a line through the two maxima is maximum.
• Algorithm:
  1. Compute a line between the two local maxima of the two distributions.
  2. Compute the distance $dL(h)$ for each entry $h$ of the histogram to this line.
  3. Convolve $dL$ with a smoothing kernel to remove the effects from noise.
  4. The threshold is $h<em>{max}$ for which $dL(h</em>{max})$ is maximum.

Shading and Noise Effects

• Shading and noise can adversely affect thresholding.
• Morphological postprocessing (opening or closing) can remove artifacts.

Relation Labeling

• Corrects segment labels using a certainty measure of segment membership.
• Initial reliabilities $p$ and $q$ are computed for each pixel $v$ based on threshold $t$.

Multichannel Functions

• Requires specifying a region in multidimensional feature space, making thresholding more complex.

Conclusion for Thresholding Methods

• Simple, fast, easy to implement and understand.
• Can separate multiple classes in images with multimodal histograms.
• May become unstable when differentiating between true and false local maxima in the histogram becomes difficult.

Homogeneity-Based Segmentation

• Uses local intensity homogeneity rather than absolute thresholds.
• Aims to separate image into the smallest number of segments that fulfill a homogeneity criterion.

Homogeneity Criteria Examples

• Variance of pixel values.
• Maximum deviation between pixel intensities.
• Probability that all pixels belong to the same probability distribution.

Basic Segmentation Algorithms

• Region merging algorithm.
• Split-and-merge algorithm.
• Neither guarantees an optimal result.

Region Merging Algorithm

1. Each pixel is considered its own region.
2. Map regions to a region adjacency graph (RAG).
3. Compute the homogeneity value for each edge.
4. As long as there exists at least one edge of which the homogeneity value fulfills the homogeneity criterion:
   • Merge the two most similar regions.
   • Update the RAG.

Split-and-Merge Algorithm

• Starts with the complete image as a single region and splits until each region meets the homogeneity criterion.
• Splits regions into four quarters (2D) or eight subvolumes (3D).
• Documents splits in a quadtree or octtree.
• Merges regions that were accidentally split using a RAG.

Watershed Transform

• Uses edge information to separate segments, especially when intensity variation from shading exists.
• Carried out on gradient lengths of the intensity gradient.
• Equal to defining segment boundaries by the zero crossings of the Laplacian of the intensity function.

WST Steps

1. Treat the scene as a landscape where gradient length represents height.
2. Each local minimum is a basin.
3. Watersheds are boundaries separating regions draining into different sinks.

Marker-based WST

• Adds information about objects to be segmented by replacing local minima with pre-specified marker positions.

Seeded Regions

• Combines data-driven constraints with interactively added domain knowledge.

Seeded Regions Steps:

1. User specifies a seed point in the object.
2. A homogeneity criterion characterizes the region's appearance.
3. Region growing detects reachable pixels/voxels from the seed point that meet the homogeneity criterion.

Adaptive Region Growing

• User places seed point in the center of the foreground object.
• Neighborhood order is changed randomly to produce a random walk.

Live Wire

• Defines boundary with interactive input when a homogeneity criterion is impossible to define.

Live Wire Steps

• User selects a start point on the boundary.
• Minimum cost paths are computed to all other points.
• User selects the most appropriate endpoint.
• This becomes the start point for the next contour segment; procedure continues until the boundary is closed.

Node Costs Formula

• $c(i,j) = | f(i,j) - \bar{g} |$

Matlab Implementation

• imbinarize(): Applies different threshold segmentation techniques to an image.
• watershed(A): Applies watershed segmentation to an image.