Image Segmentation Algorithm- A Novel Approach

Image Segmentation Algorithm- A Novel Approach

Amandeep Kaur 1*, Neeru 2*

1 Research Scholar, Electronics & Communication, R.I.E.I.T Railmajra, SBS Nagar, India

2 Associate Professor, Electronics & Communication, R.I.E.I.T Railmajra, SBS Nagar,

Abstract

Image segmentation is the important step in image analysis and processing mechanism. Several proposed algorithms have faced the problem of oversegmentation. This paper is describing a novel approach to overcome the oversegmentation of an image. The proposed method consists of three parts. The first part is based on pre processing of test images, second part involves initial segmentation using watershed transformation and third part involves the breadth first search.

Keywords- Breadth first search (BFS), Image segmentation, Mean-shift, Region merging, Watershed.

1. Introduction

   Efficient and effective image segmentation is an important task in computer vision and object recognition. In particular, it is an essential process for many applications such as object recognition, target tracking, content-based image regeneration, and medical image processing [1].

   Although being a key research field in various domains, image segmentation is still on its research stage. Spectral-based segmentation treats image segmentation as a graph partitioning problem. These methods use the eigenvectors of a matrix representation of a graph to partition image into disjoint regions with pixels in the same region having high similarity and pixels in different regions having low similarity [2]. A common characteristic among these techniques is the idea of clustering/ separating pixels or other image elements using the dominant eigenvectors of a n × n matrix derived from the pair- wise similarities, as measure by one or more nodes, between pixels where n denotes the number of pixels

   in the image. It thus subdivides an image from a global point of view.

   The color and texture features in a natural image are very complex so that the fully automatic segmentation of the object from the background is very hard. The problem consists of partitioning an image into its fundamental regions, objects or labels. The level of division depends on the specific problem being solved. This separation is accomplished in such a way that the pixels belonging to homogeneous regions, regarding to one or more features (i.e., brightness, texture or color), share the same label, and regions of pixels with significantly different features have different labels [3],[4].

   The paper involves the section2 describing different techniques particularly used in the purpose for segmenting an image into different parts depending on the color, hue and texture. In section 3 describe the proposed method, in section 4 simulation results are shown and at the end we conclude the paper.

2. Literature techniques

   Indefinite image segmentation approaches have been proposed in the literature [5-8] and can be broadly grouped into the following categories.

   1. Mean Shift Image Segmentation

      Mean shift was first proposed by Fukunaga et al. [9] and later adapted by Cheng [10]. The purpose of image analysis is more recently extended by Comaniciu et al. [11] to low-level vision problems. Mean shift is a strong and able to adapt different situations. However it can be too time consuming for larger images or applications where processing time is very crucial. The main idea behind mean shift is to treat the points in the d-dimensional feature space as an empirical probability density function where dense

      region in the feature space corresponds to the local maxima or modes of the underlying distribution [12]. The meanshift algorithm segments the image by grouping together all pixels that are closer than the spatial bandwidth in spatial domain. In the multiscale segmentation, class labels for all pixels are available for building the relationships between different levels of segmentation results. An optional step of eliminating spatial regions containing less than M pixels is another approach to performing multistage segmentation [13]. As the mean shift algorithm partition the image into several segments rather than separating a foreground object from the background, typical estimation features based on the well-known true/false positive negative notification cannot be used for the validation purpose.

   2. Watershed Technique

      Different watershed lines may be computed in the image processing. The watershed lines can be defined on the nodes, edges, hybrid lines on nodes. This method includes three main steps [14]:

      1. Calculated gradient image values.

      2. Using watershed algorithm step.

      3. Merging steps.

      Watersheds may also be defined in the continuous field. There are also many different algorithms to calculate the watersheds. The user can apply different approach to use the watershed principle for image segmentation.

      Markers may be the local minima of gradient, but this case produced over- segmentation and region merging is considered as second step [15].

      Watershed transformation based on marker use the specific marker positions which have been determined automatically with morphological operators or clearly determined by user [16].

   3. Histogram-Based Techniques

      The image is assumed to be composed in a well- separated background of a number of constant intensity objects. The image histogram is considered as the sample probability density function of a Gaussian mixture and, hence, the segmentation problem is reformulated as one of parameter

      estimation followed by pixel classification. There are four segmentation techniques: the manual technique (user inspects an image and its histogram manually), histogram peak technique (uses the peaks of the histogram), histogram valley technique (uses the peaks of the histogram, but concentrates on the valley between them), and an adaptive technique (uses the peaks of the histogram in a first pass and adapts itself to the objects found in the image in a second pass). For simplicity, the image of interest has two regions, object and background region, each of which has the same histograms locally (e.g. clutter features). The histogram restricted on a small region (neighborhood histogram) is similar to either the object histogram or the background histogram [17]. However, these methods work well only under very harsh conditions, such as small noise variance or few and nearly equal size regions. Another problem is the determination of the number of classes, which is usually assumed to be known. Better results have been obtained by the application of spatial smoothness constraints.

   4. Edge-Based Techniques

      The image edges are detected and then grouped (linked) into contours/surfaces that represent the boundaries of image objects [18]. Most techniques use a differentiation filter in order to approximate the firstorder image gradient or the image Laplacian. Then, candidate edges are extracted by thresholding the gradient or Laplacian magnitude. During the edge grouping stage, the detected edge pixels are grouped in order to form continuous, one-pixel wide contours as expected. A very successful method was proposed by Canny according to which the image is first convolved by the Gaussian derivatives, the candidate edge pixels are isolated by the method of nonmaximum suppression and then they are grouped by hysteresis thresholding. The method has been quickening by the use of recursive filtering and extended successfully to 3D images [19]. However, the edge grouping process presents serious difficulties in producing connected, one-pixel wide contours/ surfaces.

   5. Region-Based Techniques

      The goal is the detection of regions (connected sets of pixels) that satisfy certain predefined homogeneity criteria. In region-growing or merging techniques, the input image is first inset into a set of homogeneous primitive regions. Then, using an iterative merging process, similar neighboring regions are merged according to a certain decision rule. In splitting techniques, the entire image is initially considered as

      one rectangular region. In each step, each heterogeneous image region of the image is divided into four rectangular segments and the process is terminated when all regions are homogeneous. In split-and-merge techniques, after the splitting stage a merging process is applied for unifying the resulting similar neighboring regions [20]. However, the splitting technique tends to produce boundaries consisting of long horizontal and vertical segments (i.e., distorted boundaries). The heart of the above techniques is the region homogeneity test, usually formulated as a hypothesis testing problem [20], [21].

3. Proposed technique

   Proposed work involved region merging criteria. Region merging is the process of merging the two similar regions. Similarity is based on color, texture, grey level etc. The region-merging algorithm starts with an initial segmentation [22]. The initial segmentation stage involves the watershed transformation, which produces the oversegmented image. Next stage, involves the implementation of breadth first search (BFS) on the oversegmented image produced by initial segmentation stage. Breadth first search is the variant of search that is guided by a queue. The search starting at some vertex, say v, of a graph G first visits the v, then their neighbors and so on. The parameter measured is standard deviation. It is the most common measure of variability that is given by

   = (1)

   where X denotes the individual score, M mean of all scores and n is number of scores.

4. Simulation Results:

   The results have been calculated on various images of size 256×256. The results for the proposed method are shown in the Figure 1. The oversegmentation has been overcome giving a good segmented image. Also, the values of standard deviation for different test image are shown in Table 1.

   Table 1. Calculated standard deviation for different test images

   Sr. No.	Image	Standard deviation
   1.	Flower	0.2293
   2.	Boat	0.2484
   3.	Bridge	0.2944
   4.	Butterfly	0.2817
   5.	Bird	0.2769

   Figure 1. Segmentation results for test images are shown using proposed method.

5. Conclusion

The proposed method using BFS showed to be an efficient segmentation approach. It has overcome the problem of oversegmentation. The image is initially segmented by watershed transformation and the users only need to roughly indicate the main features of the object and background by using some strokes, which are called markers. Since the object regions will have high similarity to the marked object regions and so do the background regions, a unique maximal similarity based region merging mechanism may be used to extract the object. This scheme is simple and is content adaptive.

References

[1]. D. A. Forsyth and J. Ponce (2002), Computer Vision: A Modern Approach. Englewood Cliffs, NJ: Prentice- Hall.

[2]. Vicente, S., Rother, C., and Kolmogorov, V (2011). Object cosegmentation, In Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR '11, Washington, DC, USA. IEEE Computer Society, pages 2217-2224.

[3]. Abraham Duarte a, A´ ngel Sa´nchez, Felipe Ferna´ndez, Antonio S. Montemayor (2006), Improving image segmentation quality through effective region merging using a hierarchical social metaheuristic, Pattern Recognition Letters 27 pp. 12391251.

[4]. N. Pal and S. Pal (1993), A review on image segmentation techniques, Pattern Recognition. vol. 26, pp. 12771294.

[5]. Gonzalez, R.C., Woods, R., (2002). Digital Image Processing, second ed. Prentice Hall, Englewood Clis, NJ.

[6]. Parker, J.R., (1996). Algorithms for Image Processing and Computer Vision, John Wiley, New York.

[7]. Sonka, M. et al., (1999). Image processing, analysis and machine vision, second ed. PWS.

[8]. Sarkar, A., Biswas, M.K., Sharma, K.M.S., (2000). A simple unsupervised MRF model based image segmentation approach, IEEE Trans. Image Process. 9 (5), pp. 801811.

[9]. Fukunaga, K. & Hostetler, L. (1975). The estimation of the gradient of a density function, with applications in pattern recognition, IEEE Transactions on Information Theory, 21(1), pp. 3240.

[10]. Cheng, Y. (1995). Mean shift, mode seeking, and clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(8), pp. 790799.

[11]. Dorin Comaniciu and Peter Meer (2002), Mean Shift: A Robust Approach Toward Feature Space Analysis, IEEE Trans. Pattern Anal. Mach. Intell., vol. 24, no. 5, pp. 603619.

[12]. K.-L. Wu and M.-S. Yang (2007), Mean shift-based clustering, Pattern Recognit., vol. 40, no. 11, pp. 3035

3052.

[13]. Balázs Varga et al. (2011), High-resolution image segmentation using fully parallel mean shift, Varga and Karacs EURASIP Journal on Advances in Signal Processing, 2011:111.

[14]. Salman N. and Liu C. Q. (2003), Image Segmentation and Edge Detection Based on Watershed Techniques, International Journal of Computers and Applications, vol. 25, no. 4, pp. 258-263.

[15]. S.Jehan-Besson, M.Barlaud, G.Aubert, O.Faugeras (2003), Shape Gradients for Histogram Segmentation Using Active Contours, In Proceedings Int. Conf. Computer Vision, Nice, France, pp.408-415.

[16]. Salman N. and Liu C. Q. (2003), Image Segmentation and Edge Detection Based on Watershed Techniques, International Journal of Computers and Applications, vol. 25, no. 4, pp. 258-263.

[17]. J. H. Hwang, J. W. Kim, and J. U. Choi (2006). A

reversible watermarking based on hisgogram shifting, In IWDW 2006, LNCS 4283, pages 348361. Springer- Verlag.

[18]. V. Nalwa (1993), A Guided Tour of Computer Vision, Reading, MA: Addison-Wesley.

[19]. O. Monga, R. Deriche, G. Malandain, and J. P. Cocquerez (1991), Recursive filtering and edge tracking: Two primary tools for 3D edge detection, Image Vis. Comput., vol. 9, pp. 203214.

[20]. S. Chen, W. Lin, and C. Chen (1991), Split-and- merge image segmentation based on localized feature analysis and statistical tests, CVGIP: Graph. Models Image Process. vol. 53, pp. 457475.

[21]. Z. Wu (1993), Homogeneity testing for unlabeled data: A performance evaluation, CVGIP: Graph. Models Image Process, vol. 55, pp. 370380.

[22]. Bo Peng, Lei Zhang and David Zhang (2011), Automatic Image Segmentation by Dynamic Region Merging, IEEE Transactions on Image Processing, Vol. 20, No. 12.