Comparison Of Automatic And Interactive Image Segmentation Methods

Comparison Of Automatic And Interactive Image Segmentation Methods

Renjini H

Amrita School of Engineering, Department of CSE, Coimbatore, Tamil Nadu, India.

P Bagavathi Sivakumar Assistant Professor Department of CSE,

Amrita School of Engineering, Coimbatore, Tamil Nadu, India.

Abstract

Image segmentation is a challenging research topic and a fundamental problem in the field of image processing. Image segmentation is the process of dividing an image into homogeneous regions. There are two approaches for segmentation: Automatic and Interactive. In Automatic image segmentation there is no need of user interaction whereas in interactive image segmentation it requires a minimal user interaction and can achieve better results than automatic segmentation. This work aims at the study, comparison and implementation of automatic and interactive image segmentation. In this work, different algorithms for segmentation are applied after obtaining the user inputs. Level set algorithm, watershed algorithm and Gaussian mixture model is used. Performance of different segmentation algorithms are evaluated and compared.

Keywords: Interactive image segmentation, Gaussian Mixture Model, Support Vector Machine.

1. Introduction

Image segmentation is described as the process that subdivides an image into its constituent parts and extracts objects. It is the most important task in image analysis. The segmentation results will affect all the subsequent process of image analysis, such as object representation, extracting features, object classification and scene interpretation. There are two approaches for segmentation: Automatic and Interactive. In Automatic image segmentation there is no need of user interaction whereas in interactive image segmentation it requires a minimal user interaction and can achieve better results than automatic segmentation. Automatic segmentation is not appropriate in all cases. Even after the

segmentation there will be presence of anomalies. Human interactions are required to overcome these anomalies and limitations. Automatic segmentation is still a open research area due to a wide variety of foreground and background object combinations. Another approach of segmentation is interactive segmentation where human interactions are required and extract objects from background using the user knowledge. This work aims at the study, comparison and implementation of automatic and interactive image and video segmentation. In this work, different algorithms for segmentation are applied after obtaining the user inputs. Automatic segmentation algorithms such as Level set algorithm, watershed algorithm and interactive segmentation algorithms like Gaussian mixture model, Support vector machine are used. Performance of different segmentation algorithms are evaluated and compared.

Image segmentation can be used to divide an image into several regions that are homogeneous, or have some semantic meaning. After segmentation, we can derive geometric features, shape features, texture features, and contextual features from segmented regions. When developing a model in which image segmentation is an integral part, the choice of algorithm used can directly affect the performance of the model. For example, if the segmentation module in an object recognition system fails, then the shape features that will be derived will be wrong which leads the recognition to fail. Choosing the appropriate segmentation algorithms for a particular system is therefore very important.

1. Literature Survey

   Image segmentation is the process that divides an image into its constituent parts and extracts each part. There are so many ways to categorize a segmentation method. One such category is automatic and interactive segmentation. Interactive segmentation requires user inputs or user guidance whereas automatic segmentation doesnt take user inputs. Example of automatic segmentation is active contour[20], level Set, watershed methods. Interactive segmentation methods[1],[2] are Graph Cuts[4],[5],[17], Region growing, Gaussian mixture model[3] etc. Another category is contour or region based segmentation. The segmentation algorithms either define a contour around the object(Level Set, Snake) and the deform it to object boundary or segment the image into several regions as foreground or background(Region growing).Another way to categorize segmentation technique is based on intensity or texture. The basic information for segmentation can be either the intensity or the color. It is also common to create a feature vector to each pixel and to segment them. The segmentation based on texture proves better when coming to segment a highly textured image. An example for algorithms that use intensity and texture information are methods like Grab Cut and Lazy Snapping and textured-base Graph Cuts. Another example is Level Sets and Geodesic Active Contours (GAC) to texture-based variants.

   Segmentation Techniques

   Image segmentation is one of the primary steps in any of the image analysis task. The main aim is to recognize homogeneous regions within an image. There are several issues related to image segmentation. One of the common problems in image segmentation is choosing a suitable approach for separating objects from the background. The segmentation doesnt perform well if the grey levels of different objects or regions are similar.

   Histogram based segmentation

   Ohlander et al. in [7] proposed a thresholding technique based on histogram for segmenting outdoor color images. it is based on constructing color and hue histograms. The image is thresholded at separated peak.

   The process continues for each segmented part of image and stops when no separate peaks are found.

   Edge based segmentation

   Ahuja et al. in [8] proposed a method for segmentation based on edges. In this method the pixel neighbourhood elements are used for segmentation. The neighbours of each pixel is first find out and then a vector of average grey level is determined. After that a weight matrix is identified and multiplied with vector to get a value that classifies the pixel in one of two classes.

   Clustering based segmentation

   By clustering [6] image pixels in an image the segmentation can be done effectively. In clustering the data is partitioned into meaningful groups and then it is applied for classification or segmentation. Clustering analysis [9] requires the user to provide the user input as seeds for each area that has to be segmented. Clustering is commonly used for segmentation and unsupervised learning.

   Neural network based segmentation

   Campbell et al. in [10] proposed an automatic segmentation and classification method for outdoor images using neural networks. The images are segmented using Self-Organising Feature Maps (SOFM) based on texture and color information. From each region 28 features is extracted. Using a Multi Layer Perceptron with 28 input nodes and 11 output nodes classification is performed. 80% regions were correctly classified using Learning Vector Quantization and 91.9% regions were correctly classified using the Multi Layer Perceptron.

   Region Growing segmentation

   Region growing algorithms [11] take one or more pixels and grow the regions around them based upon a criteria. If the adjacent pixels are similar to the seed, they are merged with them. The process iterates until all the pixels in the image are assigned to one or more regions. Seeds can be automatically or manually selected. Their automated selection can be based on finding pixels that are of interest. On the other hand, seeds can also be slected manually for every object present in the image. In paper [13] they studied the effectiveness of seeded region growing approach for

   image segmentation of greyscale images where the seeds are manually selected.

   t Ct 0

   (2)

2. Segmentation Algorithms

In this paper automatic segmentation algorithms like

Let F be the speed in which the contour propagates in the direction normal to the curve. Hence

Level Set, Watershed and interactive segmentation algorithms like Gaussian Mixture Model, Support Vector Machine are used. After applying each algorithm on image the results are compared and evaluated by subjective evaluation by user.

a) Level Set Method

Level Set is a PDE based method which can be used to

Where

F Ct n

n

(3)

(4)

solve the major drawbacks of Snakes Algorithm. The major drawbacks of the Snakes algorithm are the

Therefore equation (2) becomes:

inability to handle topological changes, need to initialize or push the snake be close to edge and the

t F 0

(5)

inability to deal with protrusions and sharp or thin structures. Level Set was first introduced by Osher and Sethian [15] and applying it to image segmentation was suggested by Casseles et al [14] and Malladi and Sethian [16]. Level Set [18] is also called as geometrical Active Contour Models.

Embedding a curve:

The aim is to embed the planar-curve in a 2D scalar function (x, y,t) . When z=0 on the plane, the

extracted contour is called zero-level-set . For the rest

Thus we get PDE on with an initial condition

(C,t 0) and this equation can be solved using finite differences approximations [11].

Choosing function:

Malladi et al. and Sethian et al. [11] suggested a curvature dependant speed F F(k), for example, F k (concave points go faster in the normal direction. To get an inflation force we add a

constant term F :

of the plane (x, y,t) is defined to get the distance 0

between the plane and the surface. The distance is

signed distance and the sign is defined to be positive for points outside the curve and negative for points

F(k) F0 k

(6)

inside the curve. Then move the surface-function

(x, y,t) with respect to the xy plane and retrieve the

The authors then multiply the above speed by the

function:

new contour. This approach enables topological changes to occur naturally in the 2D plane. The

evolving front C(t) is a zero level set of the scalar function for every time t, then for the evolving

g(x, y)

1

1 G I (x, y)

(7)

contour:

This function behaves as an inverse of a gradient

detector. Smoothing by a Gaussian filter helps skipping weak edges. Putting it all together in (5) we get:

(C(t),t) 0

(1)

t g(x, y)(F0

k) 0

(8)

Derivation with respect to t, using the chain rule we get

Incorporating the equation for the curvature k:

2 2

2

P(Cj|X)=P(X|Cj).P(Cj)/P(X) (11)

k div(

) yy x

x y xy

xx y

( 2 2 )3 2

Where P(X | C ) is the PDF of class j, evaluated at X, P(

x y (9)

and changing the sign F0 we get the final Level Set flow as a PDE:

j

Cj ) is the prior probability for class j, and P(X) is the overall PDF, evaluated at X.

The Gaussian mixture model estimates P(X | Cj) as a weighted average of multiple Gaussians:

t g(x, y)

(F0

div( ))

(10)

Nc

P(X|Cj)= wk Gk

k 1

(12)

Level Set algorithm:

1. Initialize the function

   Each Gaussian component is defined as:

2. Calculate t

3. Evolve locally, using former and t

   Gk =

   1

   (2 )n/ 2 | V |1/ 2

   . e[1/2( X Mk ) VK ( X Mk )]

   T 1

   T 1

   (13)

4. go to step b.

5. When there is no advancement find final curve.

b) Watershed Method

Watershed image segmentation [22] is based on the theory of Mathematical Morphology. The idea for building the watershed is using a geographical analogy. The image can be interpreted as topographic surface with both mountains and valleys. Three types of points can be considered: Points belonging to regional minimum, Points at which a drop of water if placed at the location of any of those points would fall to single minimum-catchment basins, Points at which water would be equally likely to fall to more than one such

minimum-watershed lines. Assume that there is a hole

Where Mk is the mean of the Gaussian and Vk is the covariance matrix of the Gaussian.

a) Gaussian Mixture Training:

1. Initialize the initial Gaussian means i, i=1,G using the K means clustering algorithm

2. Initialize the covariance matrices, Vi, to the distance to the nearest cluster.

3. Initialize the weights i =1 / G so that all Gaussian are equally likely.

4. Present each pattern X of the training set and model each of the classes K as a weighted sum of Gaussians:

   G

   in each minima and the surface is immersed into a lake.

   p( X | s ) i p( X | Gi )

   (14)

   The water will enter through the holes at the minima

   Where G is the

   i1

   ber of Gaussians, the s are the

   and flood the surface. To avoid the water coming from

   two different minima to meet, a dam is build whenever there would be a merge of water. Finally the only thing visible of the surface would be the dams. These dam

   walls are called watershed lines.

   weights, and

   p( X | Gi )

   num

   1

   i

   i

   (2 )d / 2 | V |1/ 2

   i

   e[1/ 2( X i )T Vi1 ( X i )]

   Where Vi is the covariance matrix.

   1. Gaussian Mixture Model

      The Gaussian mixture [1],[19] architecture estimates probability density functions (PDF) for each class, and then performs classification based on Bayes rule:

5. Compute:

   ip = P(Gi|X) =

   i p( X | Gi , Ck )

   =

   p( X )

   region into the image. If we want an unsupervised classification the neural networks or the Support Vector

   i p( X | Gi , Ck )

   Machines [21] can be used. In SVM [12] the classification task is reduced to find a decision frontier

   G

   G

   p( X | , C )

   that divide the data into the groups that we want to

   i j k

   j 1

   (16)

   separate. The simplest case is when the data can be divided into two groups. In the simplest decision

6. Iteratively update the weights, means and covariances:

Nc

problem we have a number of vectors divided into two sets, and find the optimal decision frontier to divide these sets. This optimal election will maximizes the

distance from the decision frontier to the data. In two

i(t+1)=1/Nc

ip (t)

p1

(17)

dimensional case, the frontier will be a line, in a multidimensional space the frontier will be an

hyperplane. In the training phase an observer will take

1

1

Nc

i(t 1)

i p1

i p1

Nc (t) ip

1 Nc

(t) Xp

(18)

some pieces of image and label them according to pixel intensities. Then find the function that separate the training data. The information that we get is support vectors and can be applied on image other than that

T used in training. It can be repeated until good results

Vi (t 1)

i p (t)(( X p i (t))(X p i (t)) )

N (t)

N (t)

c i p1

(19)

are obtained.

5. Results

Automatic segmentation algorithms such as watershed,

1. Recompute ip using the new weights, means and covariances. Stop trainin if

   i p i p (t 1) i p (t) threshold

   (20)

   Or the number of iterations reach the specified value. Otherwise, continue the iterative updates (repeat step 4 to 7).

2. Present each input pattern X and compute the confidence for each class j:

level set algorithms and interactive segmentation algorithms like GMM and SVM are applied and their performance is compared based on subjective evaluation by user. Fig 1 shows the results of automatic segmentation and fig 2 shows the result of interactive segmentation.

P(Cj)P( X | x,Cj)

(21)

Fig.1. a) Input image, b) segmentation result using Level Set method,

Where P(Cj)=Nci/N is the prior probability of class Cj estimated by counting the number of training patterns. Classify pattern X as the class with the highest confidence.

1. Support Vector Machine

The segmentation can be seen as a classification procedure where the pixels into an image are classified between two or more classes. Each class represents a

c) segmentation result using watershed method.

Fig.2. a) Input image with brush strokes, b) segmentation result using GMM, c) segmentation result using SVM

By comparing the segmentation results, the interactive methods give good results than automatic segmentation methods. Fig.3 and Fig.4 shows the results after applying GMM and SVM interactive segmentation methods. In case of Fig.2 GMM give good results, whereas in case of Fig.3 and Fig.4 where the user mark only the red chillies as foreground SVM gives better results than GMM. So in cases where the user wants only some objects in foreground to be segmented SVM gives better results.

Fig.3. a) Input image with brush strokes, b) Segmentation result using GMM

Fig.4.a) Input image with brush strokes, b) Segmentation result using SVM

Fig 5.a) Input image with brush strokes,b) Segmentation result using GMM, c)Segmentation result using SVM

Fig 6.a) Input image with brush strokes , b)Segmentation result using level set, c)Segmentation result using Watershed, d) Segmentation result using GMM, e)Segmentation result using SVM

Fig 7.a) Input image with brush strokes , b)Segmentation result using levelset, c)Segmentation result using Watershed, d) Segmentation result using GMM, e)Segmentation result using SVM

Fig 8.a) Input image with brush strokes , b)Segmentation result using levelset, c)Segmentation result using Watershed, d) Segmentation result using GMM, e)Segmentation result using SVM

The segmentation results by each algorithm is evaluated by a group of people. Each user gave score for each result according to their opinion. According to the scores given by users we analyse

the algorithm and find out the best one. The table below shows the average scores given by users for the above 4 figures.

Sl. No	Level set	Watershed	GMM	SVM
1	30%	10%	85%	75%
2	40%	20%	80%	85%
3	50%	70%	90%	85%
4	30%	40%	90%	90%

From the above table interactive segmentation algorithms GMM and SVM got the higher score. Interactive segmentation algorithms give better results compared to automatic segmentation algorithms.

1. Conclusion

   A study and implementation of interactive image segmentation using different algorithms is proposed. Interactive segmentation algorithms provide solution by the help of a human operator. This user provides the information required to detect and extract semantic objects through a series of interactions. The users indicate or mark areas of the image as object or background, and the algorithm updates the segmentation using the new information. By providing more interactions, the user can refine the segmentation. An automatic segmentation method called level set was implemented which will set a level set function and then minimize the energy function to get the segmented region. The second method used was watershed segmentation using markers, which will

   indicate foreground and background. The 3rd

   algorithm that was used is interactive segmentation using Gaussian mixture model which would learn the likelihood of each pixel. Then using the learnt likelihoods segmentation is done. The 4th algorithm used was segmentation using SVM that will separate the data into classes by finding a decision frontier. Out of the four algorithms, interactive segmentation gives a better result than others.

   As of now the system just compares the interactive and automatic segmentation. As a part of future work dataset of complex color distribution

   [1] can be used. Interactive segmentation algorithms can also be applied for video

   segmentation. The performance of interactive algorithms can be improved by using learnt likelihoods as a segmentation cue. This may result in a better performance.

2. References

1. Fan Zhong, Xueying Qin,Qunsheng Peng, Robust image segmentation against complex color distribution. In: Proceedings of International Conference on Computer Vision (ICCV), pp. 707-716 (2011)

2. Bai, X., Sapiro, G, A geodesic framework for fast interactive image and video segmentation and matting. In: Proceedings of International Conference on Computer Vision (ICCV), pp. 18 (2007)

3. Blake, A., Rother, C., Brown, M., Perez, P., Torr, P, Interactive image segmentation using an adaptive GMMRF model. In: Proceeding of EuropeanConference on Computer Vision (ECCV), pp. 428441 (2004)

4. Boykov, Y., Veksler, O., Zabih, R, Efficient approximate energy minimization via graph cuts, IEEE Transaction on Pattern Analalysis and Machine Intelligence, 20(12), 12221239 (2001)

5. Yuri Boykov and Vladimir Kolmogorov, An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transaction on Pattern Analalysis and Machine Intelligence, 26(9):11241137, 2004.

6. Ng, Y.A., Jordan, M.I., Weiss, Y. On spectral clustering: analysis and an algorithm. In: Advances in Neural Information Processing Systems (NIPS), pp. 849856 (2002)

[7]. R.B. Ohlander, Analysis of natural scenes, PhD Thesis, Carnegie Institute of Technology, Dept. of Computer Science, Carnegie -Mellon University,

Pittsburgh, PA, 1975

[8]. N. Ahuja, A. Rosenfeld and R.M. Haralick, Neighbour gray levels as features in pixel classification, Pattern Recognition, vol. 12, pp. 251-260, 1980.

1. A.K Jain and R.C. Dubes, Algorithms for clustering data, Prentice Hall, Englewood Cliffs,

   N.J., 1988

2. N.W. Campbell, B.T. Thomas and T. Troscianko, Automatic segmentation and classification of outdoor images using neural networks, International Journal of NeuralSystems, vol. 8, no. 1, pp. 137-144, 1997a.

3. Y.L. Chang and X. Li, Adaptive image region growing, IEEE Transactions on Image Processing, vol. 3, no. 6, pp. 868-873, 1994.

4. H. Gomez-moreno, P. Gil-jimenez, S. Lafuente-arroyo, R. Vicen-bueno, R. Sanchez- montero, Color image segmentation using Support Vector Machine.

[13]. R. Adams and L. Bischof, Seeded region growing, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, no. 6, 1994.

1. V Caselles, F. Catte, T. Coll, and F. Dibos., A geometric model for active contours . Numerische Mathematik, 66:131, 1993.

2. S. Osher, and J.A. Sethian, Fronts Propagating with Curvature Dependent speed: Algorithms Based on Hamilton-Jacobi Formulation, Journal of Computational Physics, Vol. 79, pp. 12-49, 1988.

3. R. Malladi, J.A. Sethian, an B. Vemuri, Shape modeling with front propagation: A level set approach," IEEE Transactions on Pattern Analysis and Machine Intelligence 17(2), pp. 158{175, 1995

4. Shi, J., Malik, J., Normalized cuts and image segmentation, IEEE Transaction on Pattern Analysis and Machine Intelligence, 22(8),888- 905(2000)

5. J. A. Sethian. Level Set Methods and Fast Marching Methods. Cambridge Monograph on Applied and Computational Mathematics. Cambridge University Press, 1999.

6. Celik, T. and Tjahjadi, T., Automatic Image Equalization and Contrast Enhancement Using Gaussian Mixture Modeling, Transactions on Image Processing, IEEE, Vol. 21, No. 1, pp. 145- 156,2012.

7. M. Kass, A. Witkin, and D. Terzopoulos. Snakes: Active contour models. International Journal of Computer Vision, 1(4):321331, 1987. 179.

[21 ] N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines and Other Kernel-Based Methods. Cambridge University Press, Cambridge, U.K., 2000.

[22] Ashraf A. Aly1, Safaai Bin Deris2, Nazar Zaki, Research Review For Digital Image Segmentation Techniques, International Journal of Computer Science & Information Technology (IJCSIT) Vol 3, No 5, Oct 2011