17-09-2012, 11:33 AM
Algorithms for Image Segmentation
Algorithms for Image.pdf (Size: 805.65 KB / Downloads: 179)
Abstract
In image analysis, segmentation is the partitioning of a digital image into
multiple regions (sets of pixels), according to some homogeneity criterion.
The problem of segmentation is a well-studied one in literature and there
are a wide variety of approaches that are used. Different approaches are
suited to different types of images and the quality of output of a particular
algorithm is difficult to measure quantitatively due to the fact that there
may be many “correct” segmentations for a single image. Here, a graphtheoretic
framework is considered by modeling image segmentation as a graph
partitioning and optimization problem using the normalized cut criterion.
Comparisons with other criteria shows that the results for normalized cut
are quite good although high computational complexity is a drawback.
Introduction
Depending on the image acquisition model, images can be classified into various
types; namely light intensity (visual) images, range or depth images,
magnetic resonance images, thermal images and so on. Light intensity images
represent the variation of light intensity on the scene and are the most
common types of images we encounter in our daily experience. A Range
image is a map of depth information at different points on the scene.
Segmentation is the process of partitioning an image into non-intersecting
regions such that each region is homogeneous and the union of no two adjacent
regions is homogeneous. Formally, it can be defined as follows.
Segmentation by Edge Detection
The edge-based methods make use of various edge operators to produce an
“edginess” value at each pixel. The values are then thresholded to obtain
the edges. The regions within connected edges can be considered as different
segments because they lack continuity with adjacent regions. The Sobel operator
was studied and implemented to find edges in images. The edges thus
found could also be used as aids by other image segmentation algorithms for
refinement of segmentation results.
In simple terms, the operator calculates the gradient of the image intensity
at each point, giving the direction of the largest possible increase from
light to dark and the rate of change in that direction. The result therefore
shows how “abruptly” or “smoothly” the image changes at that point, and
therefore how likely it is that that part of the image represents an edge, as
well as how that edge is likely to be oriented. In practice, the magnitude
(likelihood of an edge) calculation is more reliable and easier to interpret
than the direction calculation.
Minimum Cut
A graph can be partitioned into two disjoint sets by simply removing the
edges connecting the two parts. The degree of dissimilarity between these
two pieces can be computed as total weight of the edges that have been
removed. More formally, it is called the cut.
A Physical Interpretation
We can draw an analogy between a spring-mass system and the weighted
graph by taking graph nodes as physical masses and graph edges as springs
connecting each pair of nodes. Furthermore, we will define the graph edge
weight as the spring stiffness and the total edge weights connecting to a node
as its mass.
Imagine what would happen if we were to give a hard shake to this springmass
system, forcing the nodes to oscillate in the direction perpendicular to
the image plane. Nodes that have stronger spring connections among them
will likely oscillate together. As the shaking becomes more violent, weaker
springs connecting to this group of node will be overstretched. Eventually,
the group will “pop” off from the image plane. The overall steady state behavior
of the nodes can be described by its fundamental mode of oscillation.