A Compendium of Image Segmentation Approaches

A Compendium of Image Segmentation Approaches

Evangeline D

Assistant Professor : Department of ISE, M S Ramaiah Institute of Technology Bangalore, India

Abstract Image Segmentation is a very significant process in Image processing and is widely used in tumor identification, object recognition, assisted surgeries, etc., There are a plenty of image segmentation techniques. In this paper, we present a review on algorithms used in Image Processing, particularly in Image Segmentation over the past two decades.

Keywords Image Segmentation, Thresholding, Snakes, Optimization

I. INTRODUCTION

Image Segmentation, a prime operation in Image Processing and Computer Vision focuses on dividing the digital image into two or more non- overlapping segments. There are many significant approaches to accomplish the task of segmentation. Histogram-based Image Segmentation methods focus on classifying the image pixels based on its distribution of intensities. The peaks and valleys of the histogram assist in determining the clusters of the image. The most widely adopted Image Segmentation technique is thresholding. In bi-level thresholding, determination of single specific intensity value to divide the image pixels into two classes is done. But multi- level thresholding focuses on finding a set of threshold intensity values to classify the pixels into multiple distinct regions. While bi-level thresholding plays a significant role in extraction of background from foreground, multi-level thresholding intends to segregate many complex objects from the background.

Region Growing approach to segmentation focuses on grouping pixels into regions on basis of morphological features like intensity and texture. This approach is broadly classified into two categories Seeded Region Growing (SRG) and Unseeded Region Growing methods. Seeded Region Growing relies on the appropriate choice of initial seed pixels and estimation of similarity between the seed and its surrounding neighbours usually based on the range of difference between the intensity of seed and neighbours. This approach may yield wrong results (over- segmentation) due to bad choice of initial seeds if the seed pixel is in the edge region in case of noisy images. But un-seeded region growing methods commence with identification of a region comprising a single pixel and few such regions. Each pixel, neighbours of these regions but not recognised as similar pixel to these regions are tested by computing the difference in intensity between the unallocated pixel and the mean intensity of the current regions. The unallocated pixel that has the minimum intensity difference with any of these regions and with intensity not exceeding the pre-defined threshold t is selected as a pixel belonging to that corresponding region. The process is repeated until all unallocated pixels fall into some region. It is evident that the

results of SRG vary based on the order of processing the pixels. To improve seeded region growing algorithm, several approaches like Scan order optimization, Automatic seed selection and Temporal seed tracking may be adopted [22].

Existing literature on Un-seeded Region Growing reveals that the initial region does not influence the results of segmentation. Region splitting and merging is familiar Region Growing method consisting of two major approaches Region Splitting, a top-down approach to divide image into many dissimilar parts and Region Merging, a bottom-up approach to combine similar results at each stage of Region Splitting.

Edge-based image segmentation methods focus on identifying discontinuities in the image. Usually, Roberts, Prewitts, Sobel and Canny edge operators are employed in such deductions. Active Contour Models (ACMs) or Snakes help in identification of the contours of the object on basis of internal energy that prevents deformation and external energy that fits the contour into the image boundaries.The basic classification of image segmentation techniquesh has been presented in Figure 1.

Image Segmentation

Thresholding Based

Edge Based Based

Active Contour Model

Thresholding Based

Edge Based Based

Active Contour Model

Histogram Clustering Entropy

Object attribute Spatial methods Local methods

Prewitt Sobel Roberts Canny

Histogram Clustering Entropy

Object attribute Spatial methods Local methods

Prewitt Sobel Roberts Canny

Figure 1 Image Segmentation Approaches – Classification

I. THRESHOLDING BASED SEGMENTATION Image thresholding [10] can be done using one of the

following methods:

1. Histogram shape based The peaks and valleys of the smoothed histogram are analysed.

2. Clustering based Gray level samples are grouped together as foreground and background or modelled as a mixture of two Gaussians.

3. Entropy based Optimization of the entropy of foreground and background regions is done.

4. Object attribute based Similarity between binarized and grey images is estimated.

5. Spatial methods Correlation between pixels is focused.

6. Local methods Different threshold values are selected for every pixel of the image.

Since image segmentation focuses on maximizing the dissimilarity of pixels belonging to different regions and minimizing the dissimilarity of pixels of the same region, entropy, a measure of randomness in the region is adopted for the task of image segmentation naturally.

In case of bi-level thresholding, the objective function of Kapurs entropy criterion [8] can be formulated as:

max () = 0 + 1

Where the entropies 0 1 can be computed as follows:

0 ,

Thresholding can be applied either locally or globally. Different threshold may be applied to every part of the image

0 =

ln (

)

in local thresholding whereas a single threshold value is estimated in global thresholding. To find a suitable threshold intensity of an image, either a parametric or non-parametric approach may be adopted. While the former deals with determination of statistical parameters with greater greater

=0 0

1 ,

1

0

computational expense, the latter selectively chooses optimal intensity values by maximizing certain constraints.

Generally, the two regions estimated using bi-level thresholding is stated as:

0 = {(, ) |0 (, ) 1}

1 = {(, ) | (, ) 1}

where 0 and 1 are two regions of image F with pixels ranging in the interval [0,L) classified based on threshold t . Likewise, the regions estimated using multi- level thresholding can be stated as:

0 = {(, ) |0 (, ) 1 1}

And,

1 =

=+1

0 =

=0

1

1 =

=+1

()

=

1

ln ( )

1

1 = {(, ) |1 (, ) 2 1}

= {(, ) | (, ) +1 1}

= {(, ) | (, ) 1}

where is the probability of occurrence of each gray level i (0 1). t, L and N indicate the threshold intensity

value, total number of gray levels and total number of pixels in the image respectively. If multi- level thresholding needs to be performed, the objective function is reformulated as:

max (0, 1, , ) = 0 + 1 + . +

With entropies computed as:

0

One such well-known thresholding method is Otsus

0 =

ln (

)

threshlding technique wherein the between-class variance is maximized or intra-class variance is minimized. If bi-level

=0 0

1

0

thresholding needs to be performed, then the objective function

=

ln (

)

is stated as:

min 112 + 222

1

=0+1

2

1

1

max ( )2

2 =

=1+1

2

ln ( )

2

1 2 1 2

1

where 1 and 2are the weights of the two classes, and

12 and 22 represent the variances of those classes and 1 and

2 indicate the mean of those classes. This maximization or minimization can be done using Adaptive Bacterial Foraging Algorithm [16].

Where,

=

=+1

ln ( )

0

0 =

=0

1

1 =

=0+1

2

2 =

=1+1

1

=

=+1

where t0, t1, , tn indicate the threshold intensity values.

Since [8] focuses on identifying facial regions of an image, IHLS (Intensity Hue Luminance Saturation color space) is used to distinguish regions comprising human skin. This conversion of RGB (Red, Green and Blue color model) to IHLS color space is given by:

1

= ( + + ) 3

, = max(, , ) min (, , )

3 ( )

, = arctan ( ) 2

In [8], Kapurs entropy is maximized using Bacterial Foraging Optimization. Likewise, the objective function of Tsallis entropy criterion for bi-level thresholding is formulated as given below

max () = () + () + (1 ) ()()

[12] employs Harmonic Search algorithm, a metaheuristic approach known for its searching efficiency and simplicity to determine multiple threshold levels that maximize Kapurs Entropy. Such kind of optimization of Tsallis Entropy is implemented using Cuckoo Search Algorithm [13], Particle Swarm Optimization [14] and Artificial Bee Colony [15].

II. EDGE BASED SEGMENTATION

Edges are discontinuities of an image that can be estimated using certain operators. The widely used operators include Edison, Rothwell, SUSAN, Roberts, Prewitt, Sobel and Canny [23]. Of all the operators, Canny edge detection is superior since it can recognize edges of different characteristics. It detects spurious edges and detects potential edges.

Detection of edges can be done by applying the foraging behavior of E.coli bacteria as in Bacterial Foraging Optimization. [23] focuses on driving bacteria through edge pixels by moving in a direction determined using direction probability matrix developed from transition probability matrix, a function of heuristic factor and amount of pheromone discharged by ants on the path in Ant Colony Optimization.

III. ACTIVE CONTOUR MODELS

Active contours are methods which commence with initial boundary shapes in the structure of curves that shrink or expand based on the image constraints. These shrink and expand operations are termed contour evolution that includes optimization of energy functions or simulation of Partial Differential Equations (PDE) [21]. Mathematically speaking, these active contours may be categorized as Snakes and Level Sets.

Broken edges can be connected to frame a perfect edge by utilizing Hough Transform [17] or by application of Ant Colony Optimization [18] or Bacterial Foraging Optimization [19]. In [20], it is attempted to classify mammographic images as benign or malignant using Artificial Neural Network

,

1

( )

(ANN). Thresholds are computed using ANN and Seeded Region. Growing is performed. Feature extraction is done using Genetic Algorithm. Also, an alternative method for

() =

,

=1

1

automated image segmentation is suggested wherein templates may be produced from mammographic images using ANN. Segmentation may be performed based on these templates using Cellular Neural Networks (CNN).

Type of Segmentation Approach	Literature
Thresholding based	[8],[10], [12], [13], [14], [15], [16]
Edge Based	[23]
Active Contour Models	[17],[18],[19],[20],[21]

Type of Segmentation Approach	Literature
Thresholding based	[8],[10], [12], [13], [14], [15], [16]
Edge Based	[23]
Active Contour Models	[17],[18],[19],[20],[21]

() =

1

1

=1

( )

TABLE 1 SUMMARY OF SEGMENTATION TECHNIQUES

1

=

=0

1

=

=

where t, S, q and L represent the threshold intensity, Tsallis Entropy, entropic index indicating the degree of non- extensitivity of a system and total number of gray levels respectively.

Optimization algorithm	Literature
Adaptive Bacterial Foraging	[16]
Bacterial Foraging	[8], [23], [19]
Harmonic Search Algorithm	[12]
Cuckoo Search Algorithm	[13]
Particle Swarm Optimization	[14]
Artificial Bee colony	[15]
Ant Colony Optimization	[18]

Optimization algorithm	Literature
Adaptive Bacterial Foraging	[16]
Bacterial Foraging	[8], [23], [19]
Harmonic Search Algorithm	[12]
Cuckoo Search Algorithm	[13]
Particle Swarm Optimization	[14]
Artificial Bee colony	[15]
Ant Colony Optimization	[18]

TABLE 2 SUMMARY OF OPTIMIZATION ALGORITHMS USED FOR IMAGE SEGMENTATION

IV. DISCUSSION

The segmentation techniques discussed in this paper has been summarized in Table 1. It can be seen widely in thresholding techniques that optimization algorithms have been implemented for improving the results. Such optimization algorithms have also been tabulated in Table 2. Neural networks were also employed in Active Contour Models.

V. CONCLUSION

In this paper, summary on the widely used techniques for image segmentation used over the past two decades was presented. The algorithms discussed here are mostly a combination of Image Processing approaches and optimization algorithms. In future, more segmentation techniques will be taken into account and wide comparisons even with respect to the tuning parameters in optimization will also be considered. And a broad analysis with respect to the applications in the literature will also be done. Apart from these trends, there are many topics including new research involving deep learning.

REFERENCES

[1] Guyon I, Elisseeff A. An introduction to variable and feature selection. J Mach Learn Res 2003; 3: 1157-1182.

[2] Izadpanahi S, Özçnar Ç, Anbarjafari G, Demirel H. Resolution enhancement of video sequences by using discrete wavelet transform and illumination compensation. Turk J Elec Eng & Comp Sci 2012; 20: 1268-1276.

[3] Haupt RL, Haupt SE. Practical Genetic Algorithms. 2nd ed. New York, NY, USA: Wiley, 2004.

[4] Kennedy J, Eberhart R. Swarm Intelligence. San Diego, CA, USA: Academic Press, 2001.

[5] Poore JH, Lin , Eschbach R, Bauer T. Automated statistical testing for embedded systems. In: Zander J, Schieferdecker I, Mosterman PJ, editors. Model-Based Testing for Embedded Systems. Boca Raton, FL, USA: CRC Press, 2012. pp. 111-146.

[6] Li RTH, Chung SH. Digital boundary controller for single-phase grid- connected CSI. In: IEEE 2008 Power Electronics Specialists Conference; 1519 June 2008; Rhodes, Greece. New York, NY, USA: IEEE. pp. 4562-4568.

[7] Boynukaln Z. Emotion analysis of Turkish texts by using machine learning methods. MSc, Middle East Technical University, Ankara, Turkey, 2012.

[8] Mohamad Amin Bakshali, Mousa Shamsi. Facial Skin Segmentation using Bacterial Foraging Optimization Algorithm. Journal of Medical Signals and Sensors 2012; 2(4) : 203-210.

[9] Xiaoli Zhang, Xiongfei Li, Yuncong Feng. A medical image segmentation algorithm based on bi-directional region growing. Optik 2015; 126: 2398-2404.

[10] Mehmet Sezgin, B lent Sankur. Survey over image thresholding techniques and quantitative performance evaluation. J Electron Imaging 2004; 13(1) : 146-165

[11] Sridhar. Digital Image Processing. 1st ed. India: Oxford University Press, 2011.

[12] Diego Oliva, Erik Cuevas, Gonzalo Pajares, Daniel Zalvidar, Marco Perez Cisneros. Multilevel Thresholding Segmentation Based on Harmony Search Optimization. Hindawi Journal of Applied Mathematics 2013; Article ID 575414, 24 pages

[13] Sanjay Agrawal, Rutuparna Panda, Sudipta Bhuyan, B.K.Panigrahi. Tsallis entropy based optimal multilevel thresholding using cuckoo search algorithm. Swarm and Evolutionary Computation 2013; 11:16-30

[14] Peng-Yeng Yin. Multi-level minimum cross-entropy threshold selection based on particle swarm optimization. Applied Mathematics and Computation 2007; 184:503-513.

[15] Yudong Zhang, Lenan Wu. Optimal Multi-Level Thresholding based on Maximum Tsallis Entropy via An Artificial Bee Colony Approach 2011; 4: 841-859

[16] P.D.Sathya, R.Kayalvizhi. Optimal segmentation of brain MRI based on adaptive bacterial foraging algorithm. NEUROCOMPUTING 2011; 2299-2313

[17] Rafael C Gonzalez, Richard E Woods. 1st ed. India: Pearson Prentice Hall, 2002.

[18] De Sian-Lu, Chien-Chang Chen. Edge Detection Improvement by Ant Colony Optimization. PATTERN RECOGN 2008; 29:416-425

[19] Diego Oliva, Valentín Osuna-Enciso, Erik Cuevas, Gonzalo Pajares, Marco Pérez- Cisneros, Daniel Zaldívar. Improving segmentation velocity using an evolutionary method. EXPERT SYST APPL 2015; 42: 5874 5886.

[20] Rahimeh Rouhi, Mehdi Jafari, Shohreh Kasaei, Peiman Keshavarzian. Benign and malignant breast tumors classification based on region growing and CNN segmentation. EXPERT SYST APPL 2015; 42: 990- 1002.

[21] C.P.Lee. Robust image segmentation using Active Contours : Level set approaches. Department of Electrical and Computer Engineering, North Carolina State University, USA, 2005.

[22] Jianping Fan, Guihua Zeng, Mathurin Body, Mohand-Said Hacid. Seeded region growing: an extensive and comparative study. PATTERN RECOGN LETT 2005; 26: 1139-1156

[23] Om Prakash Verma, Madasu Hanmandlu, Puneet Kumar, Sidharth Chabra, Akhil Jindal. A novel bacterial foraging technique for edge detection. PATTERN RECOGN LETT 2011; 32: 1187-1196

[24] Hongyoon Choi, Kyong Hwan Jin. Fast and robust segmentation of the striatum using deep convolutional neural networks. Journal of Neuroscience Methods 2016; 274: 146-153.