Presentation On Image Segmentation By S Ghosh

A PRESENTATION ON IMAGE SEGMENTATION

REUSABLE BASIC COMPONENTS • • • • •

VIDEO ACQUISITION IMAGE PREPROCESSING IMAGE SEGMENTATION DECISION SUPPORT SYSTEM DECISION MAKING SYSTEM

IMAGE SEGMENTATION Image segmentation is generally the first stage in any attempt to analyze or interpret an image automatically. Segmentation partitions an image into distinct regions that are meant to correlate strongly with objects or features of interest in the image. Segmentation can also be regarded as a process of grouping together pixels that have similar attributes .For segmentation to be useful, the regions or groups of pixels that we generate, should be meaningful. Segmentation is basically responsible for bridging the gap between the low level image processing that concerns itself with the manipulation of pixel gray level or color to correct defects or enhance certain characteristics of the image and the high level processing which involves the manipulation and analysis of groups of pixels that represent particular features of interest. The role of segmentation is crucial in tasks requiring image analysis. However, a reliable and accurate segmentation of an image is in general, very difficult to achieve by purely automatic means. Segmentation can be contextual or non-contextual. they basically differ in the sense that non contextual techniques ignore the relationships that exist between features in an image while contextual techniques exploit relationships between image features.

SOME APPLICATIONS OF IMAGE SEGMENTATION • • • • •

INDUSTRIAL INSPECTION OPTICAL CHARACTER RECOGNITION TRACKING OF OBJECTS IN A SEQUENCE OF IMAGES CLASSIFICATION OF TERRAINS VISIBLE IN SATELLITE IMAGES DETECTION AND MEASUREMENT OF BONE, TISSUE ,ETC IN MEDICAL IMAGES.

WATERSHED ALGORITHM The Watershed algorithm was proposed by Beucher in 1982 and improved with fast implementation methods by Vincent in 1991. It is a region based segmentation approach. It is a classic segmentation algorithm and has been widely used ever since. It combines many of the attributes of other techniques used in image segmentation like thresholding, region growing and edge detection and yields more stable results than them. It is usually guaranteed to yield continuous region boundaries. The concept of watersheds can be understood by visualizing an image in 3-D: two spatial coordinates versus gray levels. In such a ‘topographic’ interpretation, we could consider 3 types of points• Points belonging to a regional minimum • Points at which a drop of water , if placed at the location of any of those points would fall with certainty to a single minimum. • Points at which water would be equally likely to fall to more than one such minimum. For a particular regional minimum, the set of points satisfying (b) is called the catchment basin or watershed of that minimum and the points satisfying (c) form crest lines on the surface and called watershed lines.

WATERSHED ALGORITHM

WATERSHED ALGORITHM

The main aim of the watershed algorithm is to find the watershed lines. If a hole is punched in each regional minimum and the entire topography is flooded from below by letting water rise through the holes at a uniform rate. When the rising water in distinct catchment basins is about to merge, a dam is built to prevent the merging. The flooding eventually reaches a stage when only the tops of the dams are visible above the water line. These dam boundaries correspond to the divide lines of the watersheds. Thus, they are the continuous boundaries extracted by the algorithm.

WATERSHED ALGORITHM

The topographic surface In Different stages Of Flooding

IMPLEMENTATION OF THE ALGORITHM In this algorithm, initially the RGB information of the entire image was obtained. Using the given conversion equations, the color values were converted from RGB color space to L*a*b* space. lXl l0.412453 0.357580 0.180423l lRl lYl l0.212671 0.715160 0.072169l lGl lZl l0.019334 0.119193 0.950227l lBl X X/X0 where X0 = 0.950456 Z Z/Z0 where Z0 = 1.088754 L 116*(Y^1/3) for Y>0.008856 and L 903.3*Y for Y<= 0.008856 a 500 *(f(X) – f(Y)) + delta and b 200*(f(Y) – f(Z)) + delta where f(t) = t ^ 1/3 for t > 0.008856 and f(t) = 7.787*t + 16/116 for t<=0.008856 where delta = 128 for 8-bit images. On obtaining the output, 0
IMPLEMENTATION OF THE ALGORITHM

The L*a*b* values are calculated for each pixel. Thus, each set of these values basically indicates one point in the L*a*b* space. Next, we build a histogram for the input image, based on their L*a*b* values. Pixels with the same L*a*b* values are accumulated in order to build the histogram. The L*, a* and b* axes are quantized into u, v and w units which were chosen as 50,60,60 respectively. Thus we can get about 1.8*10^5 bins though the number of useful bins would be around 4.6*10^4 The watershed algorithm is very sensitive to image noise. Noise pixels will cause a large number of erroneous regions to be detected. It is thus necessary to smooth the image before the application of the algorithm. Here we have used a Gaussian filter to smooth the image before applying the watershed algorithm so that image noise can be eliminated as far as possible. The Gaussian filter is applied to the histogram to remove noise pixels.

IMPLEMENTATION OF THE ALGORITHM After filtering, we obtain the preprocessed histogram. The histogram is then reversed. Then all local minima are obtained in a neighborhood of 26 bins from the reverse histogram and are assigned labels consecutively1,23,…..and so on. The unlabelled bins are then labeled according to their neighbours. If there is more than one label in the neighbourhood, then the bin is labelled as a dam bin and is assigned the label 0. If otherwise, then the bin is labelled as its neighbour. This process is repeated until all the bins are labelled. Now, we map back the information obtained after processing the bins back to the image domain. •The pixels for whose L*a*b* values, the corresponding bins were labelled 0 are labelled 0 in the image domain. •If a bin has a value below a certain predefined threshold value, then it is labelled 0 and so the corresponding pixel is also labelled 0. •Then we obtain all 4 – neighbourhood regions with pixels whose bin labels are the same and assign them the same label . •Finally, the remaining unlabelled pixels are labelled as their bins. Thus, in the end, all the pixels of the image have been labelled.

A screenshot of the segmented video after watershed algorithm

THE NEXT STAGE….. A major issue in image segmentation is to explore information in both feature and image space and incorporate them together. Watershed algorithm usually fails to obtain the global colour distribution information. So this algorithm basically employs a technique in which watershed algorithm is first applied to extract clusters with irregular shapes and then use feature space analysis in image space to get the final result by minimizing a global energy function based on Markov random field theory. There are basically 2 methods of energy minimization which are the application of graph cuts or HCF algorithm. Here we have applied HCF algorithm because of certain advantages provided by it such as a better border. Also as the observation is determined by the attainment of continuous regions, it has more local information than a label in graph cuts. However graph cuts can find some salient small regions while HCF loses these regions because of the constraint of region continuity.

HIGHEST CONFIDENCE FIRST ALGORITHM In order to get coherent regions, image space analysis is used as the next step of image segmentation in order to refine the result from feature space analysis. Markov random field describes an image by local interactions between neighbouring pixels. Due to the local property of this theory, it is suitable to conduct the image space analysis in segmentation applications. Usually an initial state is required in order to start and many techniques have been developed to get an optimal solution of Markov random field by updating the labelling state. So, it is suitable to refine a coarse result and get a final result, with desirable property on both feature and image space. HCF algorithm is applied in which the pixels with the least stability in terms of energy are continuously updated. It is suitable for the case of assigning labels to pixels with unknown labels because it introduces an uncommitted label. A stability measurement is defined for each uncommitted pixel i.e. pixels with label 0. in each step a greedy algorithm is applied to update the label of the least stable uncommitted pixel to get the most energy reduction. It is a deterministic algorithm having good performance on minimizing the energy.

HIGHEST CONFIDENCE FIRST ALGORITHM For a pixel with label fs , potential energy can be defined as : Es(fs) = Ds(fs) + ∑ Vs,s’(fs,fs’) S’ € Ns

where V is the smoothness energy term and Ns is the set of neighbouring pixels of s. if even one pixel in the clique is uncommitted then V is 0. Ds is the distance function which is defined as: Ds(fs) = αρ^2(C(s),µ(fs)) where C(s) is the colour of the pixel and µ(fs) is the average colour of all pixels with label fs. Ρ is the Euclidean distance of two colours. Stability of a pixel is given by : Ss(fs) = - min

[ Es(l) – Es(l_min)] if fs = 0 l € L ,l ≠ l_min = min [ Es(l) – Es(l_min)] otherwise l € L ,l ≠ fs The stability of a pixel measures the potential energy reduction for updating the label of a committed pixel or a possible future potential energy reduction for labelling an uncommitted one

HIGHEST CONFIDENCE FIRST ALGORITHM

where l_min = arg min

Es(l)

l€L This is basically called the confidence for updating this pixel. Highest confidence first means that in each step , the pixel with the lowest stability value will be updated. At each step, only the least stable pixel will change its label or be committed . If k = arg min Ss(fs) is the least stable pixel, we update the label as shown: fk’ = arg min Ek(l) if fk = 0 l€L = arg min

[ Ek(l) – Ek(fk)] otherwise

l € L, l ≠ fk In each iteration step, we need to update the stability for related pixels (the updated pixel itself and the neighbouring pixels) .The iteration stops when a desired state is achieved.

IMPLEMENTATION OF THE HIGHEST CONFIDENCE ALGORITHM In the case of the algorithm implemented, after Watershed processing, a slight modification has been incorporated. • The label updating process is done only for uncommitted pixels since watershed algorithm has already obtained a satisfactory result and so there’s no need for updating committed pixels. Reduction of computation load is also required. • An uncommitted pixel can only be set to labels which appear in its neighbourhood. This is imposed in order to obtain continuous regions.

IMPLEMENTATION OF THE HIGHEST CONFIDENCE ALGORITHM

Compute the Stability value for All the Uncommitted pixels

Update the Energy for the pixels

Diagrammatic representation Of HCF algorithm Update the Uncommitted Pixel With lowest stability

Check if All pixels are Committed. If not continue

Update the stability for all The pixels

IMPLEMENTATION OF THE HIGHEST CONFIDENCE ALGORITHM

A screenshot of the segmented video after modified hcf algorithm application

ENERGY MINIMIZATION USING GRAPH CUTS The graph cuts algorithm used for the purpose of energy minimization was developed by Boykov in 2001. The basic principle of the algorithm is: For a given label state f and a label α, an α-expansion will allow any set of pixels to change their labels to α. This optimal expansion move can find the optimal labelling state in one expansion move. By using graph cuts, the optimal expansion move can be carried out very efficiently. The algorithm mainly consists of the following procedure: • For α = 1,2,..m; the label of sites is kept in S’ and for the sites with 0 label, the label is updated with α-expansion . • The previous step is repeated till the total energy converges. Here we make use of graph theory in order to find out the α-expansion. We can construct the graph by considering two terminal nodes- the source node and the sink node α and ã respectively and every pixel in the image represents one node in the graph and is connected to the two terminal nodes. P_l(l = 1,2,…m) represents the set of nodes corresponding to pixels with current label l. The nodes representing the neighbouring pixels with same label are connected by an edge. Auxiliary nodes are introduced for each pair of neighbouring nodes with different labels and they are connected to both of the correspondent neighbouring pixels and the sink node. Thus in this manner the graph is drawn .

ENERGY MINIMIZATION USING GRAPH CUTS Source node

tp

ts tq

e {a, q} a

p

q

b

r e {q, r}

e {p, α} ta

tr

tb

Sink node

An example of a graph structure

s

ENERGY MINIMIZATION USING GRAPH CUTS The next step in the process is assigning the capacities to the edges. This is found out by consulting a table. Capacities of edges between terminal node and nodes representing pixels are defined according to observation energy and capacities of other edges are based on the smoothness energy term.

Edge t (p α)

weight ∞

t (p α)

Dp (α)

t (p α)

∞

t (p α)

Dp (fp)

e {p, a}

V (fp, α)

e {a, q}

V (α, fq)

t (a α)

V (fp , fq)

e {p, q}

V (fp, α)

for p € S’ , fp ≠ α else p € P_α p € P_α {p,q} € N, fp ≠ fq

{p,q} € N, fp = fq

ENERGY MINIMIZATION USING GRAPH CUTS It was proved by Boykov that under the constraint of metric property of smoothness energy, graph cuts based on the displayed graph structure, correspondent to the optimal expansion move. A min-cut is applied on the graph. The min-cut optimization problem, defined for a weighted undirected graph, S = { V,E,W} consists of finding a bipartition of the set of vertices or nodes of the graph: V = {C,C’} such that the sum of the weights of edges with endpoints in different subsets is minimized. Every bipartition of the set of vertices V into C and C’(V = C U C’) is usually called a cutset and the sum of the weights of edges, with a vertex in C and the other vertex in C’ is called a cut weight between sets C and C’. For the considered min-cut optimization problem, the cut weight is given by: min_cut(S) = s(C,C’) =

∑

w(v,u) v €C , u €C’

After the min-cut, a pixel is assigned a label α if the cut separates this pixel from terminal α,otherwise, it just keeps it original label. If the optimal expansion move is applied iteratively on every label until there is no energy reduction after one round of labelling update, a suboptimal global energy within a known factor of the global optimum can be achieved. The energy usually converges after two to five rounds of labelling.

A COMPARISON BETWEEN HCF AND GRAPH CUTS ALGORITHM A direct comparison between graph cuts and HCF is difficult because the type of the problem and the important factors that need to be taken care of determine which algorithm must be chosen. HCF and graph cuts algorithm have different continuity constraints. HCF can provide a better border because the observation is determined by continuous regions and so it has greater information than a label in graph cuts . However graph cuts can find some small regions which HCF loses because of the strict constraints of region continuity. It is difficult to compare energy directly because both the algorithms use different orders of neighbouring system. However in terms of computational speed, the time taken by both the algorithms is almost similar. Graph cuts usually has 2-5 rounds of label updating while computational overload of HCF algorithm depends on the number of uncommitted pixels.

A screenshot after the application of HCF algorithm