Research Article
An Image Segmentation Algorithm Research Based on Region Growth
School of Electrical and Information Engineering, Hunan International Economics University, Changsha, China
Image segmentation is the critical first steps of the image processing to image analysis, its goal is that the digital image is divided into several regions, which have certain common properties of disjoint regions, the target and background is separation, these provide the basis for subsequent processing of computer vision (Lin et al., 2005). Effective and reasonable image segmentation can provide and extract useful information for content-based image retrieval and image analysis, so that a higher level of image understanding is made as possible.
Color image contains are more useful information than the gray images and it is more in line with peoples visual experience. With the rapid increase in computer processing power, color image processing is being more and more attention. For color images, there are many segmentation algorithms, such as clustering methods (Khan et al., 2009), segmentation algorithms based on the boundary (Franchi et al., 2009), segmentation algorithms based on the region (Park and Lee, 2009), segmentation algorithms based on graph theory (Araujo and Costa, 2009; Ding et al., 2006), segmentation algorithms based on neural network (Wangenheima et al., 2009) and other methods. Because the region growing method has a direct effect on color space, the color distribution and spatial connectivity are taken into account in image segmentation process, the region growing method has become a hot research. But the region growing segmentation algorithms tend to be the selection of the initial seed point and the influence of the growing order, but also it is faced with how to automatically select seed and automatically to determine the number of growing areas and other issues.
For some of the problems occurring in the region growing method, a color image region growth algorithm is proposed based on local color histogram and local color image similarity. This method has the advantage of robustness to the initial seed point selection and growth of the order and the criteria of the automatic selection is given and the number of seed growing areas is automatically determined. The traditional region growing series of defects are overcome by the algorithm, to ensure consistency within the region. At the same time, it can be consistent with the human visual judgment, this is meaningful region segmentation.
Color space and local color histogram: Color space is the quantized coordinates in color space, specifically, there are RGB, CMY, LUV, HIS, etc., a variety of the color space is a quantitative description from different aspects of the color characteristics. RGB color space and a variety of other color spaces can be converted to each other, in the computer, color image storage, display generally use the RGB color space. Because RGB color space has three groups unified range, continuous within the space, it do not exist singularity, so the RGB color space is used in this study.
In order to get the local statistical characteristics of the pixel color changes, local color histograms are first established at each pixel p of RGB space. For a given pixel p, its close K neighborhood is:
where, p, q is the pixels in the image I, px, py denote p vertical and horizontal coordinates in the image. Obviously, there are (2K+1) 2 pixels in the total of Np. Local color histogram is defined at p poin of RGB space, the local color histogram is hist(p) = (histR, histG, histB), wherein histR, histG, histB denote R, G, B three sub-volume histograms within K close neighborhood Np in the RGB color space. Local color pixel p histogram hist(p) describes the number of statistical characteristics about the colors in the K-neighborhood of the point, which can reflect the statistical distribution of the local image color and basic color shades. Region growing algorithm is algorithm based on the expansion of the pixel spatial position, so the local color histogram is introduced in the region growing algorithm, it can effectively combine statistical characteristics of the pixel local color and spatial pixel location information.
Seed points selection and growing rules: In image segmentation, in order to achieve good segmentation results, the general requirements are that similarity of pixels in the same region is greater than the similarity between the different regions of pixels. Based on this criterion, seeds of the regional growth should meet highly similar features between the pixel and its neighboring pixels. The neighborhood compatibility factor was defined by the criteria Ding et al. (2008a) and the gray image segmentation algorithm was established based on connectivity compatibility tree, a good result was obtained on gray-scale image segmentation. Similarly, in this study, the neighborhood similarity index of local color histogram is defined for color images (neighbor similarity factor, NSF):
(1) |
where, Card (Ωp) represents the number of elements in the set Ωp, Ωp = {qεNp|d(hist(q))≤Q}, hist (p), hist (q) are the local color histograms at pixel p and q, d is the Euclidean distance, Q>0 is the threshold of pixel characteristic differences.
NSF defines the ratio of the neighborhood center similar pixels and the total number of pixels. When NSF≥0.5 in neighborhood, it means that pixel p surrounding color changes slowly, it belongs an target or internal background. On the contrary, it means that colors change vigorously around the pixel p, it is a transitional area between the target and the background. Therefore, if the definition of pixels meet NSF≥0.5, it is a seed point, so that in K-neighbors of the seed pixel domain, if the color difference is less than Q pixels, it will be classified as a class and seeds of different target will be isolated by the edge points of two objectives, it is not divided into a category.
Algorithm steps: Region growing algorithm is proposed in this study, seed points are first obtained based on the NSF value, all seeds have the ability to grow in the region K-neighbors, while other seeds within its K neighbors can continue to grow. By a similar way in reference Ding et al. (2008b), it can be proved that this simple multi-seeds growing algorithm can select arbitrary initial seed point and growth of any order can get the same segmentation results. The algorithm steps are as follows:
Step 1: | Initialization K, to calculate the average-knear and mean-knear, to determine the threshold value of Q |
Step 2: | NSF value is calculated for each pixel, generating seed collection |
Step 3: | To select one of the seed pixel and to start growth, in K neighbors of the seed pixel domain, if color similarity measure is not less than Q, the pixels are classified as a class and it grows class of new seeds, new growth is until no new pixels seeds, it is until completion of a class of growth |
Step 4: | Select a seed and begins to grow again in remaining seed collection, repeat Step 2, it is date until no seeds in seed collection, all classes of growth is completed |
Step 5: | The unclassified points are classified |
Comparison and evaluation of test results: Pieces of natural color images are randomly selected with a clear goal, segmentation experiments and comparisons are done with the proposed algorithm in this study area and with a classical growing segmentation algorithm-JSEG algorithm (Deng and Manjunath, 2001). There are the comparison of the image segmentation results in Fig. 1, in the segmentation results, the first row and 3rd row are the segmentation results of JSEG algorithm and the second row and fourth row is the segmentation results of our algorithm. As can be seen from the Fig. 1, the present segmentation algorithm is more in line with the guidelines of semantic segmentation, especially when the image background is more complex, textured goal is stronger, there is the more obvious advantages in our algorithm.
In target segmentation, in order to more objectively compare, based on the target areAraujoa with artificial segmentation accuracy (Alpert et al., 2007), the target segmentation accuracy is compared by the two methods. The correct rate is represented by F:
where, P is the percentage of total number of pixels in the target region of algorithm segmentation and the artificial division which is accounted for the target total number of pixels, R represents a percentage of the total number of pixels in the target area of algorithm divided region and the artificial division which is accounted for a total number of pixels in algorithm divided region, only when the P and R are a large value at the same time, the higher accuracy is obtained.
Fig. 1(a-d): | Comparison of the results of image segmentation, (a, c) JSEG algorithm results and (b, d) Our algorithm results |
Table 1: | Comparison of the value of R, P, F and running time of the images in Fig. 1 |
Table 1 is the compared results for the two algorithms to the image in Fig. 1, it can be seen that F-value of the proposed method is significantly higher than JSEG algorithm.
It is seen by the algorithm that the computational complexity of the algorithm is O (K2N), N is the total number of image pixels. Parameter K determines the size of neighboring domains and it is generally 2-5, so the basic algorithm is with linear complexity. Because JSEG algorithm needs color feature clustering, it reduces the number of colors (Deng et al., 1999), so that when the image pixel resolution increases, JSEG algorithm will become very slow. For example, when the image pixels is 600x800, JSEG algorithm needs more than 25 sec to calculate the completion (such as the last image 823684. Jpg) and the resolution of the proposed algorithm is less affected.
Parametric analysis: Algorithm has two main parameters K and Q, K represents a pixel size in a close neighborhood and it is generally from 2 to 5, it can be adjusted according to the image size; Q represents that two pixels is similar to the threshold, when the characteristic measure of the two pixels is smaller than Q, both of which belong to the same class. obviously, the key to the divided success in the proposed algorithm is the threshold value of Q. Due to changes in the image is very complicated, Q can not have a unified value, Q is made too small or too big, which often leads to under-segmentation or over-segmentation (Fig. 2).
It is inspired by grayscale image processing method in the literature (Ding et al., 2008a), the following thresholds are established for color images Q values strategy:
• | Calculate the average value of the difference between the characteristics of each pixel and the features of its close K-neighborhood pixel: |
(2) |
• | To calculation mean value and median of Average-K, they are recorded as average-knear and mean-knear, for most images, Q will be selected between the two values |
As can be seen from Table 2, in most of the images (13 images), the optimum Q value is taken between average-knear and mean-knear, there are three images in the vicinity of the two values, only the optimum Q value of two selected image does not meet the herein law, which is due to the two images of the target is small, the parameter Q value of such an image tends to take a relatively large value.
Fig. 2(a-d): | Influence of the results of segmentation on the value of Q, (a) K4Q12, (b) K4Q14, (c) K4Q16 and (d) K4Q17 |
Table 2: | Average-knear and mean-knear on the best value of Q |
In the beginning four steps of segmentation algorithm, the center points with feature clear characteristics will be classified, because its edge pixels are complicated, these pixels are not yet classified, these will be treated in detail in Step 5. By communicating the number of pixels, unclassified pixels can be divided into isolated point, a small partition (number of pixels in the sub-region is less than the threshold value in communication, 1/50 is taken as the image size in this study), large partition (number of partition communicating pixels is greater than the threshold value).
Outlier and small partition may be noise, there is no special meaning, consolidation method is used for their classification in general. For large partitions, their NSF value is greater than the threshold value, it is representative of a target texture, they can be classified into a new class, which increases the applicability of the algorithm.
Due to the complexity of natural color images, image segmentation algorithm has been well-known problems. In this study, the color histogram is established by using the pixel local features and thus the Neighborhood Similarity Factor (NSF) is defined between the color image pixels, image pixel is automatically divided into a seed point (with growth capacity) and edge points, a robust segmentation algorithm is established for the initial seed point selection and image sequence of growth, it is better to overcome shortcomings that the traditional growth method does not automatically select seed and growth order is fixed. By comparing the accuracy and computation time with JSEG segmentation algorithm, the proposed algorithm shows a clear advantage. Because the proposed segmentation algorithm is in line with peoples subjective perception, it reaches semantic segmentation criteria, so that in the future, it is considered that the algorithm is applied to the color image retrieval, object recognition, target matching based on the target. In addition, because this study only considers the local color feature pixel, it is difficult to achieve some of the complex texture image segmentation. The next step will take advantage of the texture features of the image (Gabor filters, LBP histogram), edge feature (Contourlet Transform), etc., the new features will be embedded into the algorithm in order to expand the scope of application of this algorithm.