2.1.

Color Space Transformation and Color Features

It is known that the performance of a color segmentation method highly depends on the choice of the color space.²⁴ The RGB color space is the most widely used in the literature for image segmentation tasks, where a particular color is specified in terms of the intensities of three additive colors: red, green, and blue.²⁵ Although the RGB space is the most used in the literature, this representation does not permit the emulation of the higher-level processes that allow the perception of color in the human visual system.²⁶ Different studies have been oriented to the determination of the best-suited color representation for a given segmentation approach.^24,27–30 Some of them have found that the so-called perceptual color spaces (e.g., $\mathrm{CIE}Lab$) are the most appropriate when the resemblance to the human visual system is desirable.

Given that the perceptual color space transformations are applied to the $\mathrm{CIE}XYZ$ space, the transformation of the original RGB image to the $\mathrm{CIE}XYZ$ space must be carried out. The color representation CIE 1931 $XYZ$,³¹ best known as $\mathrm{CIE}XYZ$, is one of the first color spaces obtained from a mathematical model of human color perception, developed by the Commission Internationale de l’Éclairage (CIE). The transformation equations are included here for clarity’s sake. First, $XYZ$ values are obtained as shown in Eq. (1).

The CIE 1976 ($L^{*}$, $a^{*}$, $b^{*}$) color space, better known as $\mathrm{CIE}Lab$, is derived from the $\mathrm{CIE}XYZ$ color space. The transformation equations to obtain the $Lab$ channels from the $XYZ$ components are defined in Eqs. (2)–(5).

The main advantage of the $\mathrm{CIE}Lab$ color representation is that the Euclidean distance between two points is proportional to the difference perceived by a human between the two colors represented by these points. This ability to express color difference of human perception by Euclidean distance is very important³² because any direct comparison can be performed based on geometric separation. Whereas this representation matches the perception of human eyes,³³ the RGB does not show such property. For this reason, RCT uses the color in terms of a perceptually uniform space using the components $a$ and $b$ from the $\mathrm{CIE}Lab$ color space.

2.2.

Standard Deviation Map as Texture Feature

Because the pixels in textured regions of an image show more intensity variations than the pixels in homogeneous regions, a measure of those variations may be used to determine the boundaries of such textured regions, e.g., the standard deviation. Moreover, because different textures have different variations in intensity, this measure also allows to distinguish between different textures. In this regard, a standard deviation map, or image $T$, is obtained as follows: for each pixel in the image, the standard deviation $\sigma$ of the pixel intensities in a neighborhood is calculated. This neighborhood consists of a square region containing $k={(2d+1)}^2$ pixels and centered at the current pixel position. The parameter $d$ is the number of pixels from the central pixel to a side of the window. Equations (6) and (7) are used to obtain $\sigma$.

Special considerations are required for those pixels close to the image edges, where the corresponding neighborhood extends beyond the image boundaries. If the pixels outside the image are considered to be of intensity zero, false texture variations appear at the edges of the standard deviation map. To reduce these artifacts, the intensity of the pixels outside the image are matched to the intensity of the pixels inside the image that are located at the same distance from the edge. This mirroring procedure preserves the texture characteristics of the regions near to the image edges.

Examples of the resulting standard deviation maps using a $d=10$ are shown in Fig. 2. Notice that the different texture regions are shown in different gray levels. The near-black regions correspond to regions of homogeneous intensity in the original image, while the different levels of gray are in function of the intensity variations of the texture. These examples show that this feature is powerful enough to distinguish between textured regions within an image.

Fig. 2

Examples of the resulting standard deviation maps with a $d=10$.

2.3.

Rough Set–Based Segmentation Process

Rough-set theory is one of the most recent approaches for modeling imperfect knowledge. This theory was proposed by Pawlak¹⁷ as an alternative to fuzzy sets and tolerance theory. A rough set is a representation of a vague concept using a pair of precise concepts, called lower and upper approximations. The lower approximation of a rough set can be interpreted as a crisp set in classical set theory, which is conformed by the universe of objects that share a common feature and are known with certainty. On the other hand, the upper approximation is generated by the objects that possibly belong to the lower set but with no complete certainty. In the context of image segmentation, Mohabey and Ray¹⁶ have developed the idea of the histon, considered as the upper approximation of a rough set; the regular histogram is considered as the lower approximation.

To use the histon in the context of a histogram-based segmentation, let $I(m,n,c_i)$ be an image of $M\times N\text{pixels}$ size, where $m$, $n$ are the image coordinates $m\in [0,M-1]$ and $n\in [0,N-1]$. The parameter $c_i$ denotes the feature channels with $i>0$ used in the image representation. In this study, $i\in \{1,2,3\}$, each channel having $L_i$ possible values. Therefore, $I(m,n,c_i)\in [0,L_i-1]$ is the intensity value for the component $i$ of the image at the coordinates $(m,n)$.

The histogram of an image $I$ is a representation of the frequency distribution of all the intensities that occur in the image. The histogram of a given color channel $i$ is computed as in Eq. (8).

As mentioned above, the histogram-based segmentation methods identify each object in the image by a peak in the histogram, making the assumption that the features on the surface of the objects are unvarying. Unfortunately, such assumption is not always true and variations in the features are commonly found, making the identification of peaks a challenging task. Addressing these issues, the histon associates pixels that are similar and possibly belong to one specific object in the image. Such association is not limited to feature similarity; it also includes the spatial relationship of the pixels and their neighbors.

Considering the histon as the upper approximation of a rough set, let us define the similarity between a reference pixel and its neighbors as the weighted Euclidean distance $d(m,n)$ presented in Eq. (9).

In order to process the pixels at the boundaries of the image in the matrix $X$, pixel values in the edge are mirrored outside the image instead of using zero values. This operation enables to properly process the whole image under test.

The histon $H_i$ is computed using Eq. (11).

The histon, in analogy to the histogram, records the frequency of occurrence of pixels that are similar to its neighbors. For each pixel that is similar in features to its neighbors, the corresponding bin $g$ in its intensity channel $i$ is incremented twice. This double increment in the histon results in the heightening of peaks, corresponding to locally uniform intensities. The main advantage of using the histon instead of the regular histogram is that the histon is able to capture the local similarity, resulting in a representation tolerant to small intensity variations. Furthermore, since the peaks are heightened, their detection is easier.

In the rough-set theory, the lower and upper sets may be correlated using the concept of roughness index.¹⁸ The roughness index is a representation of the granularity, or accuracy, of an approximation set. In our scope, the roughness index is the relationship of the histogram and the histon for each intensity level $g$, and it is defined as shown in Eq. 12.

To achieve good segmentation results using rough set–based methods, the selection of peaks and thresholds from the roughness index is very important. In the methods proposed by Mushrif and Ray,^18,23 the selection of peaks is carried out on the roughness index for each color component in the RGB color space. The criteria used for the selection of the significant peaks is based on two rules, empirically determined. The first criterion establishes a specific height and the other specifies a minimum distance between two peaks. The height of a significant peak must be above the 20% of the average value of the roughness index for all the pixel intensities, and the distance between two potential significant peaks has to be higher than 10 intensity units. Because the optimal peaks are dependent on the image content, it is desirable to use adaptive criteria in the selection of height and distance thresholds.

The overall description of the RCT segmentation process is shown in Fig. 3. First, the computation of the histogram $h$, the histon $H$, and the roughness index array $\rho$ is carried out. After that, the array $\rho$ is filtered in order to diminish small variations. The adaptive selection of the significant peaks in the roughness index for each feature channel is performed and, finally, a multithreshold segmentation is accomplished. More details are given in the following paragraphs.

Fig. 3

Overall description of the rough set–based segmentation process.

The reduction of small variations in the roughness index array ${\rho }_i(g)$ for each color component $i$ is achieved by filtering them using the averaging kernel shown in Eq. (13).

The set of significant peaks for each image is estimated by computing the minimum height $T_h$ of a peak and the minimum distance $T_d$ between two peaks. First, the set of all local maxima $P=\{p_1,p_2,\dots ,p_k\}$ is obtained from the filtered roughness measure ${\rho }^{\prime }$, where a local maximum $p_k$ is

After obtaining the $k$ local maxima, the mean and the standard deviation of their corresponding heights $({\mu }_h,{\sigma }_h)$ and distances $({\mu }_d,{\sigma }_d)$ are computed. The set of significant peaks contains all the peaks above the height threshold $T_h={\mu }_h-{\sigma }_h$ that also have a distance to the next peak higher than $T_d={\mu }_d-{\sigma }_d$. After the set of significant peaks is computed, each threshold is determined as the minimum of the values found between two peaks. For each feature channel, a multithreshold segmentation process is carried out and the presegmented image is obtained with the union of such segmented feature channels.

2.4.

Region Merging

The final step in the RCT segmentation framework is the reduction of possible oversegmentation issues. This is accomplished by a region merging process that fuses small regions with the most appropriate neighbor segments. The fusion criteria for the merging step varies from method to method. Usually, the region merging is based on both feature space and the spatial relation between pixels, simultaneously. Nonetheless, some methods^18,23,34 only consider color similarity to decide if two regions are fused, ignoring the spatial relationship of the different segments.

The region merging step in RCT takes into account both feature similarity and spatial relationship among regions. First, we identify the small segments whose number of pixels is less than a given threshold. From the experiments, we have found that the oversegmentation is considerably reduced by merging segments that have a number of pixels below 0.2% of the whole image size. Once we have identified all the small regions, they are fused with the most appropriate neighbor region. Such a region is one that is more similar in features and shares the greatest number of connected pixels. An example of this process is illustrated in Fig. 4.

Fig. 4

Initial regions (a) and the final segmentation map after the region merging process (b) using the two criteria of feature similarity and spatial connectivity.

In Fig. 5, an example of the resultant images in each step of our method and the final segmented image are presented. In Figs. 5(a)–5(c), we can see the images of the feature channels using $a$, $b$ and $T$, respectively. The presegmented image is shown in Fig. 5(d). Such an image is the result of the rough set–based segmentation, before the submission to the merging process. In this image, the borders of the segments detected are superimposed to the original image and we can observe that many small regions are present. The Fig. 5(e) shows the resultant segmentation of RCT after the merging process, where the oversegmentation issues were significantly reduced. In this image, we can see that the pixels of the flower petals are associated in one segment despite the intensity differences of the red color. Moreover, the RCT method is able to clearly separate the red petals of the flower from the yellow center and the green background.

Fig. 5

Resulting images of the inner process. Feature components (a) $a$, (b) $b$, and (c) $T$, respectively. (d) The presegmented image before the region merging process and (e) the final-segmented image.

3.1.

Experimental Setup and RCT Parameter Selection

For the evaluation of the RCT method, the scenario described by Yang et al.³⁵ is replicated for the assessment of segmentation approaches. For these experiments, the Berkeley segmentation data set (BSD)³⁶ is used. Such a data set is an empirical basis for segmentation algorithms evaluation. For each image, a ground-truth is available and may be used to quantify the reliability of a given method. Moreover, the diversity of content of this data set, including landscapes, animals, buildings, and portraits, is a challenge for any segmentation algorithm.

For a quantitative evaluation, four widely used metrics are adopted for the assessment of segmentation algorithms: Probabilistic Rand Index (PRI),³⁷ Variation of Information (VoI),³⁸ Global Consistency Error (GCE),³⁶ and the Boundary Displacement Error (BDE).³⁹ These measures provide a value obtained from the comparison of a segmented image and the corresponding ground-truth. For the estimation of these measures, we have used the MATLAB® source code made publicly available by Yang et al.³⁵ Other performance measures for segmentation algorithms may be consulted in Table 1 of the article by Ilea and Whelan.³

Table 1

Performance estimation of the RCT using different combinations of the parameters Ex and W. The performance is evaluated using the probabilistic Rand index (PRI).

The BDE measures the average displacement error between the boundary pixels of the segmented image and the closest boundary pixels in the ground-truth segmentations. The GCE evaluates the extent to which a segmentation map can be considered as a refinement of another segmentation. The VoI metric calculates conditional entropies between class labels distributions. The PRI counts the number of pixel pairs whose labels are consistent, both for the ground truth and for the segmentation result. If the test image and the ground truth images have no matches, the PRI is zero, its minimum value. The maximum value of 1 is achieved if the test image and all the segmentation references are identical. This measure is considered the most important in our evaluation because, as pointed out by Yang et al.,³⁵ there is a good correlation between the PRI and human perception through the hand-labeled segmentations. For the PRI, the segmentation is considered better if the resulting value is closer to 1. For the other measures, the segmentation is superior if the values are closer to 0. Additionally to these widely used metrics, we have included the Normalized Probabilistic Rand index (NPR).³⁷ The NPR, as it name indicates, is the normalization of the PRI in the range of $[-1,1]$. Its importance lies in the fact that it considers the differences among multiple ground-truth images through a nonuniform weighting of pixel pairs as a function of the variability in the ground-truth set. Moreover, the NPR value is more sensitive to variations and it has a higher range of values than the PRI.

As was previously mentioned, the parameters of a rough set–based segmentation method are $(W,\mathrm{Ex})$. In the approaches previously proposed^18,23 using the RGB color space, the best couple of parameters according to the authors is (3, 100). In contrast, because the feature space used in this study has a different shape compared with the RGB color space, the most suitable parameters need to be estimated. The evaluation of the best combination of parameters is carried out using the 300 images taken from the BSD and quantitatively assessed using the PRI measure. We have exhaustively searched for the best window size $W$ in the set $\{3,5,7,9,11\}$ and the expanse Ex in the set of $\{\mathrm{50,100,150},\dots ,400\}$.

The influence of the fundamental parameters $(W,\mathrm{Ex})$ on the performance of the RCT method is given in Table 1. The evaluations presented in this table are measured using the PRI. The expanse Ex is the similarity tolerance among the features used and $W$ is the size of the neighborhood to analyze. The value of Ex has influence on the dilatation or contraction of the boundary region between the histogram and the histon, and therefore, on the value of the roughness index. If Ex is high, the association of similar pixels becomes more flexible, leading to undersegmentation issues. If Ex is small, the association becomes more rigid, making highly similar pixels to be considered as different regions, resulting in an oversegmentation. The parameter $W$ has a direct impact on the computation time of the histon, since it defines the neighborhood size of the analysis for each pixel. It can be seen in Table 1 that the performance remains stable when Ex is small and the PRI starts to decrease when $\mathrm{Ex}\ge 200$. This decrement in the performance is caused by the fact that the ground-truth images from the BSD are, in general, undersegmented. Such fact has been also observed by Ilea and Whelan.¹⁵ The lowest PRI value of 0.7480 is obtained with the parameters (9, 350) and the best performance, $\mathrm{PRI}=0.7856$, is found for (7, 150). Other parameters, like the value of $d$ for the texture extraction and the weights in the Eq. (9), were also obtained in such exhaustive search. The window size $d$ for the texture extraction was searched in the set $d=\{1,2,\dots ,20\}$ and the weights ${\omega }_i$ in the set ${\omega }_i=\{0,0.1,\dots ,1\}$. A window size of $21\times 21\text{pixles}$, meaning a $d=10$, and the set of weights ${\omega }_i=\{0.2,0.2,0.6\}$ have been found to provide the best results.

3.2.

Performance Evaluation

A quantitative evaluation of the RCT using the 300 images from the BSD was carried out. The distribution of the four quantitative measures PRI, VoI, GCE, and BDE are presented in Fig. 6. This figure shows the frequency that the RCT records a given value in each quantitative measure. For the PRI distribution [Fig. 6(a)], it is noteworthy the leaning of the PRI distribution to the maximum value of 1. This means that a high number of images achieve high PRI values, implying that the RCT method has a correspondence with the ground-truth. This figure also shows the tendency of the GCE [Fig. 6(c)] and BDE [Fig. 6(d)] distributions, where the tendency toward a error of zero is noticeable. The corresponding mean performance and the standard deviation for each quantitative measure PRI, VoI, GCE, and BDE are shown in Table 2, where we have also added the NPR results.

Fig. 6

Distribution of the resulting values of the four measures for the Berkeley data set. For (a), a higher value is better, and for (b), (c), and (d), a small value is better.

Table 2

Performance analysis of the RCT method using the five measures.

After the study of the performance of RCT, a comparison was conducted against other recent and similar approaches. The first comparison is carried out against the color-based technique using A-IFS histon.²³ As previously mentioned, this method uses the RGB color representation. In the original A-IFS histon-based article, the average performance is assessed using only the PRI measure. The average performance reported for the A-IFS method is 0.7706, which is lower than the 0.785 index achieved by our RCT. This implies that the image representation in perceptual color spaces and the inclusion of texture information improves the performance of rough set–based methodologies.

A comparison with three other state-of-the-art algorithms that use both color and texture features was carried out in our evaluation: the J-image segmentation (JSEG) method proposed by Deng andManjunath,⁴⁰ the compression-based texture merging (CTM) approach introduced by Yang et al.,³⁵ and the Clustering-based image Segmentation by Contourlet transform (CSC) presented by An and Pun.⁴¹

The average performance of each method using the four quantitative measures, PRI, BDE, GCE, and VoI, is presented in Table 3. For the JSEG and the CTM approaches, the source codes provided at their web pages were downloaded and executed with the 300 BSD images. For the CSC method, the source code is not available; hence, the quantitative results presented in the original article are taken. It is important to highlight that the CSC evaluation, as mentioned in the original article,⁴¹ has been carried out using only a subset of 100 images from the complete set of 300 images from the BSD. This table shows that the best results for the GCE and the BDE measures are achieved by the proposed RCT method. The lowest value for the VoI measure is obtained by the CTM approach with $\gamma =0.2$. This means that our method is more accurate in relation to the ground-truth segmentations.

Table 3

Average performance and comparison with other methods. Within the parentheses is the number of images used by the authors for their evaluation.

For the PRI measure, the method RCT has obtained a 0.785 score, outperforming the JSEG (0.774) and CTM (0.761) approaches. The method that attains the highest PRI value is the CSC, reporting a result of 0.796 using only 100 images for the evaluation. Because mean results obtained by the RCT methodology and the CSC methodology are close to each other, a Student’s $t$-test was conducted to determine if the differences observed between the results are statistically significant. For a fair comparison between the two methods, we assume that both PRI distributions are normal and that there is not a significant difference between the standard deviations of the samples. However, no standard deviation is reported by CSC from the test samples. In this regard, the standard deviation from our results is used for both population samples. We also assume that the sample from CSC was selected randomly. Given those constrains, we calculate $t$ using Eq. (15),

Additionally to the Student’s $t$-test and in view that the authors of the CSC method do not define the selected subset of images used in their experiments, the tendency of the mean achieved by our RCT is analyzed for different subset sizes. For this analysis, we have taken the $K=\{1,2,\dots ,300\}$ images from the RCT results that achieve the best performance for the PRI measure. The PRI mean tendency is presented in Fig. 7, where it is shown that if the number of testing images is increased, the average performance decreases. In this figure, we can see that if 291 images are used, the RCT method achieves the mean performance of the CSC method of 0.796. Furthermore, if the best 100 images are taken for the RCT evaluation, our method achieves a mean PRI value of 0.8894, a much higher value than the 0.796 obtained by the CSC method that uses 100 images.

Fig. 7

Trend of the probabilistic Rand index measure mean achieved by the RCT method depending on the number of images taken from the Berkeley segmentation data set.

A qualitative comparison of the segmentation results is presented in Fig. 8, where the first column corresponds to the CTM outcomes, the second column shows the resultant images of the JSEG method, and our RCT segmentations are shown in the third column. We only present qualitative comparisons of the methods whose results are available. In these examples, the edges of the segments are overlaid on the original image. From this qualitative comparison, we can observe that the RCT method is in general able to associate pixels with similar color and texture in single segments. For example in Fig. 8(a), there are oversegmentation issues in the outcomes of the CTM and JSEG methods. In Fig. 8(b), a challenging image is shown, since the color of the cheetah and its background are very similar. For this case, only the CTM and the RCT methods are able to separate the differences in texture of this image. In Fig. 8(c), the ability of RCT is noticeable for the association of the different intensities of blue in the sky, while the other methods separate them in two [Fig. 8(c2)] or even in three different segments [Fig. 8(c1)]. This ability can be also appreciated in Fig. 8(d), where the RCT is able to merge the elephants in only one segment. In the case of Figs. 8(e) and 8(f), the performance of the three methods is very similar. The last example shows how the CTM and the RCT succeed in the association of the pixels of the kangaroo while the JSEG attains an oversegmentation.

Fig. 8

A qualitative comparison of seven out of 300 segmentation outcomes between the CTM (first column), JSEG (second column), and our RCT (third column). The segmentation borders are overlaid on the original image.

Other color-texture segmentation algorithms that attain a high performance have been proposed, and they deserve a special mention. This is the case of the MIS method proposed by Krinidis and Pitas¹² ($\mathrm{PRI}=0.79$), the GSEG proposed by Garcia Ugarriza et al.⁶ ($\mathrm{NPR}=0.49$), and the CTex method introduced by Ilea and Whelan¹⁵ ($\mathrm{PRI}=0.80$). Despite the quantitative results of these methods, they have not been considered in this assessment because of the differences in the technical foundations between them and the RCT. The MIS method is spatially guided based in energy minimization and it is iterative in two stages of the method. The GSEG approach is also iterative and spatially guided. It uses a region growing technique and a multiresolution merging strategy, which might result in a considerable processing time. The CTex algorithm, although it is the method that attains the highest PRI value in the literature, has computational requirements that are considerably high due to its multiple steps and to the large number of distributions that have to be calculated during the adaptive spatial clustering process.

The main attributes exhibited by our RCT are summarized. It is spatially blind: this means that it is not based on pixel-by-pixel agglomeration. In the RCT, the number of segments is automatically estimated without the need of a predefined number of clusters or seeds initialization. It is able to integrate different kinds of features. The use of a perceptual color representation and the addition of textural features in a rough-set strategy achieves better results than other methods that use only color cues. Additionally, the significant peaks selection, jointly with the merging strategy, allows better results in comparison with other state-of-the-art methods in terms of quantitative measures.