18CSE390T- COMPUTER VISION 3rd/5th

Unit - 3
Image segmentation
Image segmentation is the task of finding groups of pixels that “go together”. In statistics, this
problem is known as cluster analysis.
Image segmentation is a commonly used technique in digital image processing and analysis to
partition an image into multiple parts or regions, often based on the characteristics of the
pixels in the image.
It involves:
➢ Separating foreground from background
➢ Clustering regions of pixels based on similarities in color or shape.
➢ For example, a common application of image segmentation in medical imaging is to
detect and label pixels in an image or voxels of a 3D volume that represent a tumor in
a patient’s brain or other organs.
➢ Traffic Control Systems
➢ Self Driving Cars
➢ Locating objects in satellite images

Image segmentation involves converting an image into a collection of regions of pixels

that are represented by a mask or a labeled image.

By dividing an image into segments, you can process only the important segments of the
image instead of processing the entire image.
There are various image segmentation techniques like:
Active contours, split & merge, watershed, region splitting, region merging, graph-based
segmentation, mean shift and model finding, and Normalized cut.
Applications:

• Content-based image retrieval[5]

• Machine vision
• Medical imaging
18CSE390T- COMPUTER VISION 3rd/5th

o Locate tumors and other pathologies[8][9]

o Measure tissue volumes[10][11]
o Diagnosis, study of anatomical structure[12]
o Surgery planning
• Object detection
o Pedestrian detection
o Face detection
o Brake light detection
o Locate objects in satellite images (roads, forests, crops, etc.)
• Recognition Tasks
o Face recognition
o Fingerprint recognition
o Iris recognition
o Prohibited Item at Airport security checkpoints
• Traffic control systems
• Video surveillance

Active contour

Contours are the boundaries that define the region of interest in an image.
Active contour is defined as an active model for the segmentation process.
Active contour is a segmentation method that uses energy forces and constraints to
separate the pixels of interest from a picture for further processing and analysis.

Active contours are the technique of obtaining deformable models or structures in an

image with constraints and forces for segmentation.
The primary use of active contours in image processing is:
To define smooth shapes in images and to construct closed contours for regions. It is
mainly used to identify uneven shapes in images.

➢ Active contours are used in a variety of medical image segmentation applications

like to segmentation of regions from different medical imagesbrain CT images, MRI
images of different organs, cardiac images and different images of regions in the
human body.
➢ In motion tracking and stereo tracking.

How it works?
18CSE390T- COMPUTER VISION 3rd/5th

The desired shape is obtained by defining the energy function.

A collection of points that locate a contour is used to describe contour deformation.
This shape corresponds to the desired image contour, which was defined by minimizing
the energy function.
Step 1: Initialize the boundary curve (the active contour) Automatically, Manually, or
Semi-automatically.
Step 2: The contour moves. “Active “contour looks like a wiggling “snake” .

Step 3: The contour stops moving .When many/most points on the contour line up with
edge pixels.

Snake Model
The snake model is a technique that is used to identify and outline the target object for
segmentation.
It requires some prior knowledge of the target object’s shape, especially for complicated
things.
Active snake model also called snakes generally configures by the application of spline
focussed to minimise energy followed by various forces governing the image.
Spline is a mathematical expression of a set of polynomials to derive geometric figures
like curves.
A simple snake model can be denoted by:

A set of n points, vi for i=0,….n-1, the internal elastic energy term EInternal and the external
edge-based energy term Eexternal.
The internal energy term’s aim is to regulate the snake’s deformations, while the exterior
energy term’s function is to control the contour’s fitting onto the image.
The external energy is typically a combination of forces caused by the picture Eimage and
constraint forces imposed by the user Econ.
The snake’s energy function is the total of its exterior and internal energy, which can be
written as below.

σ decides on how far the snake will be extended and the capacity of elasticity possible for
the snake. β decides on the rigidity level for the snake. The internal energy is given by:
18CSE390T- COMPUTER VISION 3rd/5th

External energy constraints are mainly used to define the snake near the required local
minimum. It may be described using high level interpretation and interaction.

where w1 is called the line efficient and w2 is called the edge efficient. According to the
higher values of w1 and w2, snake will align itself to darker pixel regions in the case of
positive value and it progresses towards the bright pixels when the value is negative.
Applications:

➢ In medical imaging include optic disc and cup segmentation to identify glaucoma
➢ Cell image segmentation
➢ Vascular region segmentation
➢ Several other regions segmentation for diagnosis and study of disorders or
anomalies.

Dynamic Snakes and Condensation

In many applications of active contours, the object of interest is being tracked from frame to
frame as it deforms and evolves.
In this case, it make sense to use estimates from the previous frame to predict and constrain
the new estimates. We can use Kalman filter for contouring .
Kalman Filtering and Kalman Snakes Kalman filter uses estimates from the previous frame
to predict and constrain the new estimates.

Kalman filtering is an algorithm that provides estimates of some unknown variables given the
measurements observed over time.
Kalman filter algorithm consists of two stages:
18CSE390T- COMPUTER VISION 3rd/5th

➢ Prediction (propagation)
➢ Update(corelation)

The Kalman Filter process model defines the evolution of the state from time t−1 to
time t as:

• xt: current state variable

• xt-1: previous state variable
• A: linear transition matrix
• w: noise vector, which is often modeled as a Gaussian

Intelligent Scissors
Intelligent Scissors allow objects within digital images to be extracted quickly and accurately
using simple gesture motions with a mouse. When the gestured mouse position comes in
proximity to an object edge, a live-wire boundary “snaps” to, and wraps around the object of
interest.
18CSE390T- COMPUTER VISION 3rd/5th

Intelligent Scissors is the “live-wire” path selection tool. The live-wire tool allows the user to
interactively select the desired optimal path from the entire collection of optimal paths (one
for each pixel in the image) generated from a specified seed point. The optimal path from each
pixel is determined at interactive speeds
Intelligent Scissors boundary detection formulates discrete dynamic programming (DP) as a
two-dimensional graph searching problem”

Part 1: Image Processing

Step 1: Convert Image into pixel values
Step 2: Assign scores to pixel values :
➢ Greater the probability of being an edge point, the lower the score - Apply Soble
filters (Sx, Sy).
➢ Calculate Gradient Magnitude (G)

Putting it all together -The gradient is scaled and inverted so high gradients
produce low costs and vice-versa. Thus, the gradient component function is:

Step 3: Assign Weights to vertex

➢ Compute using filters

➢ Cost Function
Cost= (max-|filter response|)*length
Cost function will be applied to each pixel once.

Part 2: Dynamic Programming

Algorithm: Live-Wire 2-D DP graph search.
18CSE390T- COMPUTER VISION 3rd/5th
18CSE390T- COMPUTER VISION 3rd/5th

Split & Merge

Split and merge segmentation is an image processing technique used tosegment an image.

The image is successively split into quadrants based on a homogeneity criterion and similar
regions are merged to create the segmented result

Algorithm:

➢ Define the criterion to be used for homogeneity

For a grey level image, say, a region is said to be statistically homogeneous if the standard
deviation of the intensity less than some threshold value, where the standard deviation is
given by,

and is the mean intensity of the N pixels in the region. Whereas splitting is quite simple,
merging is more complex. Different algorithms are possible, some use the same test for
homogeneity but others use the difference in average values.

➢ Split the image into equal size regions

➢ Calculate homogeneity for each region
➢ If the region is homogeneous, then merge it with neighbors
➢ process is repeated until all regions pass the homogeneity test..

Mean shift and mode finding Segmentation

 The Mean Shift segmentation is a local homogenization technique that is very useful
for damping shading or tonality differences in localized objects.

 Versatile technique for clustering-based segmentation of image data.

Algorithm
18CSE390T- COMPUTER VISION 3rd/5th

 The image data is converted into feature space.

(color, gradients, texture, etc.)

 Search windows are distributed over the feature space.

 Mean-Shift iterations:

1.) The MEANs of the data samples within each window are computed.

2.) The windows are shifted to locations equal to their previously computed means.
3.) Repeat Step-1 & Step-2 until convergence, i.e., all windows have settled on final
locations.
 The windows that end up on the same locations are merged.

 The data is clustered according to the window traversals.

Mean Shift Pros and Cons

Pros

✓ Good general-practice segmentation

✓ Flexible in number and shape of regions
✓ Robust to outliers

Cons
✓ Have to choose kernel size in advance.
✓ Not well suited for high-dimensional features

Normalized cut
The normalized cut is a graph partitioning segmentation technique which segments the graph
by measures both the total dissimilarity between the different groups as well as the total
similarity within the groups.
18CSE390T- COMPUTER VISION 3rd/5th

Normalized cut computes the cut cost as a fraction of the total edge connections to all the
nodes in the graph.
The set of points in an arbitrary feature space can be represented as a weighted undirected
complete graph G = (V, E), where the nodes of the graph are the points in the feature space.
The weight wi,jof an edge (i,j) belongs to E is a function of the similarity between the
nodes i and j .

Normalized cuts
Let G = (V, E, w) be a weighted graph. Let A and B be two subsets of vertices.
Let:

Algorithm:

 Given a set of features, construct a weighted graph by computing weight on each edge
and then placing the data into W(a symmetric matrix) and D(diagonal matrix).
 Solve (D-W)x=λDx for eigenvectors with the smallest eigen values.
 Use the eigenvector corresponding to the second smallest eigen value to bipartition
the graph into two groups.
 Recursively repartition the segmented parts if necessary.
18CSE390T- COMPUTER VISION 3rd/5th

Graph cuts and energy-based Segmentation

 In normal boundary segmentation, if we restrict the boundary measurements to be
between immediate neighbors and compute region membership statistics by summing
over pixels, then this as a classic pixel-based energy function using either a variational
formulation .
 The energy corresponding to a segmentation problem can be written as
 E(f) = ∑ i,j Er(i, j) + Eb(i, j),
where the region term Er(i, j) is the negative log likelihood that pixel intensity (or
color) I(i, j) is consistent with the statistics of region R(f(i, j))
the boundary term Eb(i, j)) measures the inconsistency between neighbors modulated
by local horizontal and vertical smoothness.
We use Binary Markov random field (MRF) Technique for energy based segmentation.
Binary Markov random field (MRF) Technique:
1. The pixels in the background and foreground regions are delineate .
2. These pixels then become the seeds that tie nodes in the S–T graph to the source and sink.
3. The capacities of the other edges in the graph are derived from the region and boundary
energy terms.
4. Minimum-cut/maximum-flow problem has been applied.
5. Pixels on either side of the computed cut are labeled according to the source or sink to which
they remain connected.