IMAGE SEGMENTATION AVAILABLE TECHNIQUES, OPEN ISSUES AND REGION GROWING ALGORITHM

GHULE A.G.¹*, DESHMUKH P.R.²*
¹M.E., Sipna’s COET, Amravati, MS, India.
²Computer & IT Department, Sipna’s COET, Amravati, MS, India.
* Corresponding Author : pr_deshmukh@yahoo.com

Received : 21-02-2012     Accepted : 15-03-2012     Published : 19-03-2012
Volume : 3     Issue : 1       Pages : 71 - 75
J Signal Image Process 3.1 (2012):71-75

In areas such as computer vision and mage processing, image segmentation has been and still is a relevant research area due to its wide spread usage and application. This paper provides a survey of achievements, problems being encountered, and the open issues in the research area of image segmentation and usage of the techniques in different areas.. We considered the techniques under the following three groups: Threshold-based, Edge-based and Region-based. Region Growing is an approach to image segmentation in which neighboring pixels are examined and added to a region class if no edges are detected. This process is iterated for each boundary pixel in the region. If adjacent regions are found, a region-merging algorithm is used in which weak edges are dissolved and strong edges are left in tact. Region Growing offers several advantages over conventional segmentation techniques. Unlike gradient and Laplacian methods, the borders of regions found by region growing are perfectly thin (since we only add pixels to the exterior of our region) and connected. The algorithm is also very stable with respect to noise.

Image Segmentation, Region Growing.

The main goal of image segmentation is domain independent partitioning of an image into a set of disjoint regions that are visually different, homogeneous and meaningful with respect to some characteristics or computed property such as grey level, texture or colour to enable easy image analysis. Image segmentation is a useful tool in many realms including industry, health care, astronomy, and various other fields. Segmentation in concept is a very simple idea. Simply looking at an image, one can tell what regions are contained in a picture. Is it a building, a person, a cell, or just simply background? Visually it is very easy to determine what is a region of interest and what is not. Doing so with a computer algorithm on the other hand is not so easy. How do you determine what defines a region? What features distinguish one region from another? What determines how many regions you have in a given image? Discontinuity and similarity/homogeneity are two basic properties of the pixels in relation to their local neighborhood used in many segmentation methods. The segmentation methods that are based on discontinuity property of pixels are considered as boundary or edges based techniques and that are based on similarity or homogeneity are region based techniques. We have intentionally separated thresholding technique from region based due the usage of histogram and its simplicity. Image segmentation would have been easy if not because of;
• Image noise
• Weak object boundaries
• Inhomogeneous object region
• Weak contrast and
• Many others that affect images

Thresholding based image segmentation aims to partition an input image into pixels of two or more values through comparison of pixel values with the predefined threshold value T individually. Failure to find the most suitable algorithm to determine the threshold value(s) T the result might be one or all of the following
• The segmented region might be smaller or larger than the actual.
• The edges of the segmented region might not be connected.
• Over or under-segmentation of the image (arising of pseudo edges or missing edges).

Edge based segmentation is the location of pixels in the image that correspond to the boundaries of the objects seen in the image.It is then assumed that since it is a boundary of a region or an object then it is closed and that the number of objects of interest is equal to the number of boundaries in an image. For precision of the segmentation, the perimeter of the boundaries detected must be approximately equal to that of the object in the input image. For instance, these methods have problems with images that are:
• Edge-less
• Very noisy
• Boundary that are very smooth
• Texture boundary
Other problems of these techniques emanate from the failure to adjust/calibrate gradient function accordingly thus produces undesirable results as:
• The segmented region might be smaller or larger than the actual.
• The edges of the segmented region Might not be connected.
• Over or under-segmentation of the image (arising of pseudo edges or missing edges).

The region based segmentation is partitioning of an image into similar/homogenous areas of connected pixels through the application of homogeneity/similarity criteria among candidate sets of pixels. Each of the pixels in a region is similar with respect to some characteristics or computed property such as colour, intensity and/or texture.
Failure to adjust the homogeneity/similarity criteria accordingly will produce undesirable results. The following are some of them:
• The segmented region might be smaller or larger than the actual.
• Over or under-segmentation of the image (arising of pseudo objects or missing objects).
• Fragmentation.
Region growing is a simple region-based image segmentation method. It is also classified as a pixel-based image segmentation method since it involves the selection of initial seed points. This approach to segmentation examines neighboring pixels of initial “seed points” and determines whether the pixel neighbors should be added to the region. The process is iterated on, in the same manner as general data clustering algorithms. The fundamental drawback of histogram-based region detection is that histograms provide no spatial information (only the distribution of gray levels). Region-growing approaches exploit the important fact that pixels which are close together have similar gray values.
Region growing approach is the opposite of the split and merge approach.
• An initial set of small areas are iteratively merged according to similarity constraints.
• Start by choosing an arbitrary seed pixel and compare it with neighbouring pixels.
• Region is grown from the seed pixel by adding in neighbouring pixels that are similar, increasing the size of the region.
• When the growth of one region stops we simply choose another seed pixel which does not yet belong to any region and start again.
• This whole process is continued until all pixels belong to some region.
Region growing methods often give very good segmentations that correspond well to the observed edges

The main goal of segmentation is to partition an image into regions. Some segmentation methods such as "Thresholding" achieve this goal by looking for the boundaries between regions based on discontinuities in gray levels or color properties. Region-based segmentation is a technique for determining the region directly.

The first step in region growing is to select a set of seed points. Seed point selection is based on some user criterion (for example, pixels in a certain gray-level range, pixels evenly spaced on a grid, etc.). The initial region begins as the exact location of these seeds.
The regions are then grown from these seed points to adjacent points depending on a region membership criterion. The criterion could be, for example, pixel intensity, gray level texture, or color.
Since the regions are grown on the basis of the criterion, the image information itself is important. For example, if the criterion were a pixel intensity threshold value, knowledge of the histogram of the image would be of use, as one could use it to determine a suitable threshold value for the region membership criterion.

Then we can conclude several important issues about region growing are:
1. The suitable selection of seed points is important.
2. More information of the image is better.
3. The value, “minimum area threshold”.
4. The value, “Similarity threshold value“.

We briefly conclude the advantages and disadvantages of region growing.

1. Region growing methods can correctly separate the regions that have the same properties we define.
2. Region growing methods can provide the original images which have clear edges the good segmentation results.
3. The concept is simple. We only need a small numbers of seed point to represent the property we want, then grow the region.
4. We can determine the seed point and the criteria we want to make.
5. We can choose the multiple criteria at the same time.
6. It performs well with respect to noise.

1. The computation is consuming, no matter the time or power.
2. Noise or variation of intensity may result in holes or oversegmentation.
3. This method may not distinguish the shading of the real images.
We can conquer the noise problem easily by using some mask to filter the holes or outlier. Therefore, the problem of noise actually does not exist.

There are a few main points that are important to consider when trying to segment an image. You must have regions that are disjoint because a single point cannot be contained in two different regions. The regions must span the entire image because each point has to belong to one region or another. To get regions at all, you must define some property that will be true for each region that you define. To ensure that the regions are well defined and that they are indeed regions themselves and not several regions together or just a fraction of a single region, that property cannot be true for any combination of two or more regions. If these criteria are met, then the image is truly segmented into regions. This paper discusses two different region determination techniques: one that focuses on edge detection as its main determination characteristic and another that uses region growing to locate separate areas of the image.
The region growing techniques took on a variety of aspects the block diagram below illustrates the potential sequences of processes that can lead to segmentation using region growing.
Block Diagram of Region Growing Algorithms.

Uniform blocking is the first step in any of our algorithms. This step involves dividing the images into uniform blocks for processing. We typically used 2x2 blocks if region growing was to be employed directly or 16x16 blocks if the merge-split algorithm was to be used. It shouldn't matter what block size is fed into the merge-split routine, but picking an intermediate value enhances the speed for most images.

The merge-split routine is an optional stage of our region growing based segementation scheme. It requires a threshold as an input. This threshold determines which blocks can be merged into a single block and which blocks can be split into smaller blocks based on the difference between the maximum and minimum intensities in each block. If the max-min difference of a block is close to the max-min difference of its neighbors (i.e., difference between blocks is within the threshold), then the blocks are merged into a single block. A block is split in half if the max-min difference of the block exceeds the threshold. The merge-split mechanism is a quadtree structure, meaning that the merging and splitting of blocks goes from 4 to 1 and 1 to 4 respectively. This process is done recursively until, no blocks satisfy the criteria to be split or merged. Thus a block whose max-min difference exceeds the threshold will continue to be split until the max-min difference of the subsequent block(s) are within the threshold or the block size reaches one pixel, in which case the max-min difference is zero. There is also a minimum block size argument which allows the user to specify the smallest block size that can be generated through splitting. This allows the user to force the segmenting algorithm to end up with a small number of regions by ensuring that the output of the merge-split algorithm has blocks that are no smaller than a specified size. Without this feature there is a potential for the merge-split routine to return many small blocks. If these blocks are not successfully merged by the region growing algorithm, undesirable results are likely.

Region growing is done by examining properties of each block and merging them with adjacent blocks that satisfy some criteria. We used one of two criteria. One criteria is to look at the max-min difference and combine adjacent regions whose max-min difference is within a tolerance of the seed block's. The new region is now the seed and the process is repeated, examining adjacent regions, comparing max-min differences, and adding blocks that are within the tolerance specified by the user. This tolerance does not have to be the same as the threshold used in the merge-split algorithm. Alternatively, the mean values of the blocks can be used to determine which blocks should be merged.

The dissove algorithm works in conjunction with the mean-based region growing to merge regions that are less than a specified size into the adjacent region with the closest mean value. This process helps give a segmented image that corresponds more to the segmentation that a human would do by hand. The number of regions is reduced by eliminating the less significant regions, avoiding an excessive amount of segmentation.

The result of image segmentation is a set of segments that collectively cover the entire image, or a set of contours extracted from the image (see edge detection). Each of the pixels in a region are similar with respect to some characteristic or computed property, such as color, intensity, or texture. Due to the importance of image segmentation a number of algorithms have been proposed but based on the image that is inputted the algorithm should be chosen to get the best results. In this paper the author gives a study of the various algorithms that are available for color images, text and gray scale images [4] .
The algorithm described here is for integrating edges and regions. Firstly, the edge map of image is obtained by using canny edge operator. Then the edge region is grown. Very small regions are removed by merging. Thus the effect of noise is completely eliminated. The two types of seeds (pixels) hot and cold are obtained in the edge region and according to the type of data being analyzed and application area, the image is segmented into background and foreground objects [5] .
Ultrasound prenatal screening has been proposed as a most effective technique for trisomy 21 early assessment. The current practice using B mode conventional ultrasonic images are restricted inter and intra observer variability. Therefore, we proposed three dimensional segmentation techniques for ultrasound marker, nuchal translucency (NT), as a replacement method to existing manual two dimensional NT thickness measurements. The developed generic computing algorithms are integrated with VTK and ITK open-sources libraries. Region growing was implemented with growth criteria and rendered by reconstructed multiplanar view. The findings have proven that the developed algorithm was able to produce consistent three dimensional NT segmentation [6]
In this paper we present a fully automated scheme for detection of abnormal masses by anatomical segmentation of Breast Region of Interest (ROI). We are using medio-lateral oblique (MLO) view of mammograms. We have proposed a new homogeneity enhancement process namely Binary Homogeneity Enhancement Algorithm (BHEA), followed by an innovative approach for edge detection (EDA). Then obtain the breast boundary by using our proposed Breast Boundary Detection Algorithm (BBDA). After we use our proposed Pectoral Muscle Detection Algorithm (PMDA) to suppress the pectoral muscle thus obtaining the breast ROI, we use our proposed Anatomical Segmentation of Breast ROI (ASB) algorithm to differentiate various regions within the breast. After segregating the different breast regions we use our proposed Seeded Region Growing Algorithm (SRGA) to isolate normal and abnormal regions in the breast tissue. If any abnormalities are present it gets accurately highlighted by this algorithm thus helping the radiologists to further investigate these regions. This composite method have been implemented and applied on all mammograms with abnormalities in mini-MIAS database. The algorithms proposed are fully autonomous, and are able to isolate different types of abnormalities, if present, a task very few existing mammogram segmentation algorithms can claim [7] .
In this work we present the development of an algorithm for region growing in binary images using CPLDs and FPGAs devices. Generally, gray-level images with spherical objects present undesired effects when they are captured by a vision system, because such images will present holes when they are converted to the binary format. Thus, the proposed algorithm in this work solves this kind of drawback [8] .

The merge-split algorithm due to its use of a criteria based on the difference between the maximum and minimum pixel values within the region tends to act like an edge detection algorithm. In smooth (no noise or textures) and low gradient images, edges are the only areas where large differences in pixel values tend to occur. As a result near edges, the merge-split algorithm tends to split blocks down to individual pixels. Larger merged blocks appear in the interiors. So for this class of images, merge-splitting is an effective first stage in segmentation, and region growing can take place faster. For images with complex subregions, fine detail, patterns, and gradients such as the plane, merge-splitting with a max-min criteria doesn't buy you that much. Too low a merge split threshold creates too many small pixel size regions. Too high a merge split threshold creates too many large blocky regions. Using merge splitting prior to region growing tends to result in sharper edges. Unfortunately it also results in blockiness in the final image. On the other hand, region growing without merge-splitting generated images with blurry edges.
It is difficult to say which of the region growing algorithms worked better in general. The two algorithms each had difficulties dealing with various image features. The max-min algorithm did a better job of preserving edges and handled some textures better than the mean algorithm. The mean algorithm did better on images with speckle. In the end the choice of the algorithm really depends on the image you are dealing with. Neither algorithm, with or without merge splitting, is really optimal for segmenting diverse image types, but then again what is? Effective segmentation of an image requires some level of global analysis and understanding of the image features. Neither of these algorithms performs any sort of high level spatial correlation, so it is understandable that they fail for complex images consisting of complex regions.

[1] Polak M., Zhang H. and PI M. (2009) Image and Vision Computing, 27(8):1223-1227.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[2] Rein A., Hamida A.B. and Benjelloun M. (2009) International Journal of Signal Processing, 5(1).  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[3] Varshney S.S., Rajah N. and Purwar R. (2009) International Conference on Methods and Models in Computer Science.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[4] Krishna Kant Singh and Akansha Singh (2010) IJCSI International Journal of Computer Science Issues, 7(5).  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[5] Singh R., Singh J., Sharma P. and Sharma S. (2011) IJCTA.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[6] Lai Khin Wee, Hum Yan Chai and Eko Supriyanto (2011) International Journal of the Physical Sciences, 6(15), 3704-3710.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[7] Maitra I.K., Nag S. and Bandyopadhyay S.K. (2011) Indian Journal of Computer Science and Engineering (IJCSE).  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[8] Pedrino E.C., Saito J.H., Roda V.O. and Marcelo Marinho(2010) 17th International Conference on Systems, Signals and Image PA.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

	Fig. 1-
	Fig. 2-