- Region growing
Region growing is one of the simplest region-based
image segmentationmethods and it can also be classified as one of the pixel-based image segmentations because it involves the selection of initial seed points.
This approach to segmentation examines the neighboring pixels of the initial “
seed points” and determines if the pixel should be added to the seed point or not. The process is iterated as same as data clustering. We describe the algorithm as below.
The main goal of segmentation is to partition an image into regions. Some segmentation methods such as "Thresholding", achieve the goal by looking for the boundaries between regions based on discontinuities in
gray levels or colorproperties. Region-based segmentationis a technique finding the region directly. Here are the basic formulation for Region-Based Segmentation:
is a logical predicate defined over the points in set and is the null set. (a) indicates that the segmentation must be complete; that is, every pixel must be in a region.
(b) requires that points in a region must be connected in some predefined sense.
(c) indicates that the regions must be disjoint.
(d) deals with the properties that must be satisfied by the pixels in a segmented region-for example if all pixels in have the same gray level.
And the condition (e) indicates that region and are different in the sense of predicate .
Basic Concept of Seedpoints
First of all, we choose a set of seed points. And the initial region now is the exact location of these seeds.
Then the regions are grown from these seed points to adjacent points depending on a threshold or criteria we make. The threshold could be made by user. It could be intensity, gray level texture, or color.
Since the regions are grown on the basis of the threshold, the image information is important for us. For example, getting to know the
histogramof the image would help us a lot since we can take it as a reference to choose the threshold.
There is a very simple example followed below. Here we use
4-connected neighborhoodto grow from the seed points. We can also choose 8-connected neighborhoodfor our pixels adjacent relationship. And the criteria we make here is the same pixel value. That is, we keep examining the adjacent pixels of seed points. If they have the same intensity value with the seed points, we classify them into the seed points. It is a iterated process until there are no change in two successive iterative stages. Of course, we can make other criteria, but the main goal is to classify the similarity of the image into regions.
ome Important Issues
Then we can conclude several important issues about
1.The suitable selection of seed points is important. The selection of
seed pointsis depending on the users. For example, in a gray-levellightning image, we may want to segment the lightning from the background. Then probably, we can examine the histogramand choose the seed points from the highest range of it.
2.More information of the image is better.
Obviously, the connectivity or pixel adjacent information is helpful for us to determine the threshold and
3.The value, “minimum area threshold”.
No region in
region growingmethod result will be smaller than this threshold in the segmented image.
4.The value, “Similarity threshold value“.
If the difference of pixel-value or the difference value of average
gray levelof a set of pixels less than “Similarity threshold value”, the regions will be considered as a same region.
The criteria of similarities or so called homogeneity we choose are also important. It usually depends on the original image and the segmentation result we want.
Here are some criteria we often use："
Gray level"(average intensity or variance), " color", and " texture" or "shape".
Here we show a simple example for
Figure. 1 is the original image which is a
gray-scalelightning image. The gray-scalevalue of this image is from 0 to 255. The purpose we apply region growingon this image is that we want to mark the strongest lightning part of the image and we also want the result is connected without being splitted apart. Therefore, we choose the points having the highest gray-scalevalue which is 255 as the seed pointsshowed in the Figure. 2.
After determining the
seed points, we have to determine the range of threshold. Always keeps in mind that the purpose we want to do is to mark the strongest light in the image. The third figure is the region growingresult from choosing the threshold between 225 and the value of seed points(which is 255). It means we only want to mark out the points whose gray-scalevalues are above 225.
If we make the range of threshold wider, we will get a result having a bigger area of the lightning region show as the Figure. 3 and the Figure. 4.
We can observe the difference between the last two figures which have different threshold value showed above.
Region growingprovides the ability for us to separate the part we want connected.
As we can see in Figure. 3 to Figure. 5, the segmented result in this example are seed-oriented connected. That means the result grew from the same seed points are the same regions. And the points will not be grown without connected with the seed points in the beginning.Therefore, we can mention that there are still lots of points in the original image having the
gray-scalevalue above 155 which are not marked in Figure. 5.This characteristic ensures the reliable for the segmentation and provides the ability to resist from noise. For this example, this characteristic prevents us marking out the non-lightning part in the image because the lightning is always connected as one part.
The Advantages and Disadvantages of Region Growing
We briefly conclude the advantages and disadvantages of region growing.
Region growingmethods can correctly separate the regions that have the same properties we define.
Region growingmethods 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 pointto represent the property we want, then grow the region.
4. We can determine the
seed pointsand 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 or noise actually does not exist. In conclusion, it is obvious that the most serious problem of region growing is the power and time consuming.
* Jian-Jiun Ding, The class of "Time-Frequency Analysis and Wavelet Transform", the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2007.
* Jian-Jiun Ding, The class of "Advanced Digital Signal Processing", the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2008.
* W. K. Pratt, "Digital Image Processing 4nd Edition", John Wiley & Sons, Inc., Los Altos, California, 2007
* M. Petrou and P. Bosdogianni, "Image Processing the Fundamentals", Wiley, UK, 2004.
* R. C. Gonzalez and R.E. Woods, "Digital Image Processing 2nd Edition", Prentice Hall, New Jersey, 2002.
Wikimedia Foundation. 2010.