Keywords

1 Introduction

Mathematical Morphology (MM) is very resourceful when providing ways to design morphological filters [27, 31]. Such filters compound a family of image operators which are increasing and idempotent. In particular, openings compound a very well known class of anti-extensive morphological filters which is the basis (with their dual counterparts, the closings - which are extensive) for the design of several morphological operators, such as the alternating sequential filters [31] and the openings and closings by reconstruction [27]. The last ones are also classified as connected filters.

Connected operators belong to a category of MM operators whose property is the reduction of regions of an image while not introducing new borders [20]. A common characteristic of some operators is the fact that a simplified image has a reduced number of flat zones (regions with a constant grayscale value). Such property is very useful in frameworks such as compression, segmentation or even in pattern recognition, in the reduction of the image statistics and in the simplification of the number of samples required in such techniques. Reconstruction operators, levelings [25] and area openings [34] are among well known connected operators.

By now, it is worth mentioning the area opening operator [34]. Let us consider, as a connected component, a flat zone valued one in a binary image. Given a binary image and a non-negative numerical thresholding value as input parameters, this operator removes from the binary image all connected components whose areas (defined by its number of pixels) are lower than the numerical parameter. As a result, well defined connected component are usually preserved while possible noisy components are discarded. This filter can be extended to grayscale case by the application of the thresholding decomposition [34]: After the decomposition of a grayscale image (with k graylevels) in k binary image slices - each slice given by a simple thresholding with the threshold value ranging from 0 to k - the binary case is applied to each slice and, then, the slices are recombined to compose the filtered image.

In the last example, we may consider area as a filtering criterion and the non-negative numerical parameter as a thresholding value assigned to that criterion. This concept is generalized by the attribute opening [6], a particular connected operator that removes connected components according to an increasing criterion (when the criterion is not increasing, the operator is an attribute thinning). Among the increasing criteria, we cite the area measurement [32, 33]. Again, through thresholding decomposition, authors extend attribute operators from binary case to the grayscale one. Besides the cited generalization for filtering/processing images according to given criteria, attribute operators are applied to solve several problems such as image compression, segmentation of medical images and structural analysis of ore [6].

As stated above, the extension of attribute filtering from binary to grayscale images is straightforward. However, such extension to color images is not natural or straightforward, due the lacking of a natural complete lattice representation for such images [27]. Literature presents several strategies to extend MM to color images [2, 4, 7,8,9, 15,16,17,18, 21, 27, 29].

The goal of this paper is to propose an extension of attribute operators to color images. This extension is based on the thresholding decomposition of a color gradient of the input color image. The gradient valleys give a good representation, in grayscale, of the objects in the color image, preserving characteristics such as size and shape. In this way, color images may be analyzed by the application of classical attribute operators to the color gradient valleys.

A strong motivation to propose the extension to color images is, although attribute operators are well known for their application to the structural analysis of objects, to allow the use of a color feature or statistic as criteria for analysis. Two criteria based on unsupervised segmentation evaluation methods [37] are applied to improve the quality of a color segmentation of the input gradient.

This paper is organized as follows: Sect. 2 reviews some preliminary concepts. Section 3 introduces the extension of attribute operators to color images. Section 4 describes how average color error and entropy may be used as a homogeneity criterion for a color attribute operator. Section 5 demonstrate the application of average color error and entropy criterion to image segmentation. And, Sect. 6 concludes the paper with the final remarks.

2 Preliminary Concepts

Let \(E\subset \mathbb {Z}\times \mathbb {Z}\) be a rectangular finite subset of points. A binary image may be denoted by a subset \(X\subseteq E\). Let the power set \(\mathcal {P}(E)\) be the set of all binary images.

Let \(K=[0,k]\) be a totally ordered set. Denote by Fun[E, K] the set of all functions \(f :E\rightarrow K\). A graylevel image is one of these functions.

Let \(Fun[E,\mathbf {C}]\) be the set of all functions \(\mathbf {f} : E\rightarrow \mathbf {C}\), where \(\mathbf {C}=\{\mathbf {c}_1,\mathbf {c}_2,\mathbf {c}_3\}\) and \(\mathbf {c}_i\in \mathbb {Z} : 0 \le \mathbf {c}_i \le k\). \(Fun[E,\mathbf {C}]\) denotes the set of all color images.

Let A and B be two image sets, as described in the last three paragraphs. An image operator (operator, for simplicity) is a mapping \(\psi :A\rightarrow B\).

Let \(B_c\) be the structuring element that defines a connectivity [27]. A connected component of E is a subset \(X\subset E\) such that, \(\forall x,y\in X\), there is a path \(P(x,y)=(p_0,p_1,...,p_t)\), \(p_i\in X\), such that \(p_0=x\), \(p_t=y\) and \(\forall i\in [0,t-1], \exists b\in B_c : p_i + b = p_{i+1}\).

2.1 Color Gradient

Literature presents several ways to compute color gradients [10, 23]. They are usually designed taking into account the analysis of each color component image under a certain color space model. For instance, color gradients may be designed under RGB [10, 13], HSL [29] or L\(^*\)a\(^*\)b\(^*\) [30]. In this work, the color gradient is computed under the L\(^*\)a\(^*\)b\(^*\) color space model. In this perceptual model, the Euclidean distance may be applied to evaluate the perceptual distance between two colors.

Let \(\mathbf {f}\in Fun[E,\mathbf {C}]\) be a color image under the L\(^*\)a\(^*\)b\(^*\) color space model [10]. Let \(D(\mathbf {a},\mathbf {b})\) be the Euclidean distance between two colors \(\mathbf {a},\mathbf {b}\in \mathbf {C}\), under the L\(^*\)a\(^*\)b\(^*\) color space. The color gradient \(\nabla _{B_{\mathtt {grad}}} : Fun[E,\mathbf {C}]\rightarrow Fun[E,\mathbb {R}_+]\) is given by, \(\forall x\in E\),

$$\begin{aligned} \nabla _{B_c}(\mathbf {f})(x)=\bigvee _{b_1, b_2\in B_c} D(\mathbf {f}(x+b_1),\mathbf {f}(x+b_2)). \end{aligned}$$
(1)

In order to apply the thresholding decomposition, the color gradient needs to be converted to an image \(\overline{\nabla }(\mathbf {f})\in Fun[E,K]\), as follows:

  1. 1.

    Normalize \(\nabla _{B_{\mathtt {grad}}}(\mathbf {f})\) from the interval \([\min \{\nabla _{B_{\mathtt {grad}}}(\mathbf {f})\},\cdots ,\max \{\nabla _{B_{\mathtt {grad}}}(\mathbf {f})\}]\) to \([0, \cdots , k]\) (rounding it down);

  2. 2.

    Image \(\overline{\nabla }(\mathbf {f})\in Fun[E,K]\) is given by the negation of the normalized gradient. This is done because objects are represented by valleys in the color gradient, and the negation of such valleys makes them sliceable by the thresholding decomposition.

2.2 Thresholding Decomposition

Let \(\mathbf {thr} : Fun[E,K]\times K\rightarrow \mathcal {P}(E)\) be the thresholding function, given by, \(\forall f\in Fun[E,K]\), \(\forall t\in K\),

$$\begin{aligned} \mathbf {thr}(f,t) = \{x\in E : f(x) \ge t\}. \end{aligned}$$
(2)

Let \(f_{bin} : \mathcal {P}(E)\rightarrow Fun[E,k]\) be the mapping that gives a numerical representation of a binary image \(X\subseteq E\), such that, \(\forall x\in E\),

$$\begin{aligned} f_{bin}(X)(x) = {\left\{ \begin{array}{ll} 1, &{} \text {if}\ x\in X, \\ 0, &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$
(3)

Let \(f\in Fun[E,K]\). The thresholding decomposition is given by,

$$\begin{aligned} f = \sum _{t = 1}^{k}f_{bin}(\mathbf {thr}(f,t)). \end{aligned}$$
(4)

In other words, a grayscale image f may be decomposed as a stack of binary images, each one provided by the thresholding of f by a distinct graylevel \(k\in K\). The “addition” of all binary images in that stack returns image f.

Thresholding decomposition is a way to extend some operators - designed for binary images - to the grayscale context [6]. Formally, the extension of \(\psi : \mathcal {P}(E)\rightarrow \mathcal {P}(E)\) to \(\varPsi : Fun[E,K]\rightarrow Fun[E,K]\) is given by,

$$\begin{aligned} \varPsi (f) = \sum _{t = 1}^{k}f_{bin}(\psi (\mathbf {thr}(f,t))). \end{aligned}$$
(5)

2.3 Attribute Operators

Attribute operators are applied to remove all structures that do not fit into a given criterion [6]. Such criterion is usually tied to a measurement and a comparison to a numerical parameter p. For instance, an image structure must be removed if its area is not greater than p - this is the criterion for area opening.

Let \(X\in \mathcal {P}(E)\) be a binary image. Let \(C\subseteq X\) be a connected component. The trivial operator \(\mathrm {\Gamma }_T : \mathcal {P}(E)\rightarrow \mathcal {P}(E)\) evaluates if C satisfies a criterion T [6]:

$$\begin{aligned} \mathrm {\Gamma }_T(C) = {\left\{ \begin{array}{ll} C, &{} \text {if } C \text { satisfies criterion } T,\\ \varnothing , &{} \text {otherwise,} \end{array}\right. } \end{aligned}$$
(6)

where \(\mathrm {\Gamma }_T(\varnothing ) = \varnothing \).

The attribute operator is given by, for all \(X\in \mathcal {P}(E)\),

$$\begin{aligned} \mathrm {\Gamma }^T(X) = \bigcup _{C\subseteq X} \mathrm {\Gamma }_T(C), \end{aligned}$$
(7)

where C is a connected component of X. Note that this is the binary case - the extension of Eq. 7 to grayscale case is given by thresholding decomposition (see Eq. 5).

For detailed information about attribute openings and thinnings, see [6]. Notice that only structural criteria are mentioned in that paper.

3 Color Attribute Operators

This section introduces an extension of the attribute operators to color images. The proposed framework allows the choice and application of criteria based on color information for attribute filtering of color images. Analysis of local morphological structures from a color gradient provides regions where information is collected from the color input image. And, such morphological structures are filtered in function of the collected color information.

Let \(\overline{\mathrm {\Gamma }}_T:\mathcal {P}(E)\times Fun[E,\mathbf {C}]\rightarrow \mathcal {P}(E)\) denote the color trivial operator. It is similar to Eq. 6, but \(\overline{\mathrm {\Gamma }}_T(C,\mathbf {f})\) may also take into account local color information given by \(\{\mathbf {f}(x):x\in C\}\), if a criterion T involves color features or statistics.

Connected component C is enough for assessment when criterion T is structural, like in graylevel version [6]. For criteria based on color features or statistics, we cite average color error [5, 36], color harmony [28] and entropy [12]. In this paper, we apply the color entropy criterion and the average color error (see Sect. 4).

The computation of the color attribute operator \(\overline{\mathrm {\Gamma }}^T:Fun[E,\mathbf {C}]\rightarrow Fun[E,K]\) is described in Algorithm 1. Note that, except for the application of the color trivial operator \(\overline{\mathrm {\Gamma }}_T(C,\mathbf {f})\), the color attribute operator is computed like the grayscale version [6].

figure a

The use of the filtered image \(\overline{\mathrm {\Gamma }}^T(\mathbf {f})\) depends on the application of the method. For instance, one can use the residue of \(\overline{\mathrm {\Gamma }}^T(\mathbf {f})\) [14]. Another approach is to apply the watershed operator [3, 27] to the negation of \(\overline{\mathrm {\Gamma }}^T(\mathbf {f})\) in order to compute a hierarchical segmentation [26] of \(\mathbf {f}\). This approach is adopted in this work.

4 Criteria: Unsupervised Segmentation Evaluation Methods

Haralick and Shapiro [19] affirmed that good segmentations provides homogeneous regions. Indeed, unsupervised evaluation methods for segmentation quality assessment usually have a component to measure this aspect [37]. We propose to use a homogeneity metric in a color attribute operator with the objective of obtaining a segmentation with homogeneous regions.

In order to evaluate the regions for segmentation we decided to modify the trivial operator to not just evaluate the elements of the connected component but also the elements of it’s influence zone.

Let \(G_t\) be a set of connected components of \(\overline{\nabla }(\mathbf {f})\) given a threshold t. Let \(W_t\) be a watershed of the inverse of \(\overline{\nabla }(\mathbf {f})\) using \(G_t\) as markers. Let \(C \in G_t\) be a connected component. Let \(R_w\) be the region generated by C in \(W_t\).

We define a operator based on average color error as it has already been used to evaluate homogeneity of segmentations [5, 22]. The trivial average color error operator is given by the sum of the euclidean distance between the color information of each element of the connected component and the mean value of the color information of the region:

$$\begin{aligned} e(R, f) = \sum _{x \in R} D(f(x), \mu (R, f)), \end{aligned}$$
(8)

where \(\mu \) returns the mean value of the color information in the region.

The average color error criterion \(T_e\) is defined by \(T_e = (e(R, f) \ge t)\). In other words, average color error of e(R, f) must be greater than or equal to t.

We also define a operator based on entropy which was used in the function E [36] as a component evaluating homogeneity of the regions of a segmentation. The trivial entropy operator is given by the entropy of the color information of the elements of the region:

$$\begin{aligned} S(R, f) = -\sum _{x \in R} p(f(x)) \log _2 p(f(x)), \end{aligned}$$
(9)

where p returns the probability of the color information in the region.

The entropy criterion \(T_S\) is defined by \(T_S = (S(R, f) \ge t)\). In other words, entropy of S(R, f) must be greater than or equal to t.

5 Improvements for Color Segmentation

We use the watershed on the negation of \(\overline{\mathrm {\Gamma }}^T(\mathbf {f})\) to obtain a segmentation. Varying the threshold value results in a sequence of segmentation ranging from a image with just one region (when only a minimum remains) to the supersegmentation (when no minima is removed). This enables to control a trade-off between the number of regions and the attribute of the regions.

5.1 Experimental Results

In our experiment we used the Berkeley Segmentation Dataset and Benchmark 300 [24]. The experiments were implemented using SDC Morphological Toolbox for python [11] and scikit-image [35].

For each image we applied each operator described in the session 5 sliding the attribute value which resulted in a sequence of segmentations, varying from a coarse to a fine segmentation.

Then we confronted the color attributes with the structural ones (namely the area, height and volume) using the same framework and also with the Simple Linear Iterative Clustering (SLIC) [1]. For each resulting segmentation we obtained a comparison segmentation with the same number of regions.

Figure 1 illustrates some of the segmentations obtained during the experiment on sample “138078”. Observe how this paper’s operators are sensible to details in the same time of identifying large homogeneous regions.

Fig. 1.
figure 1

(b), (c), (d), (e), (f) and (g) are segmentations of (a) with 8 regions.

Full size image

The analysis was made by measuring the segmentations using E evaluation method proposed by Zhang et al. [36]. It uses a combination of entropy to evaluate intra-region uniformity and a layout entropy to evaluate inter-region uniformity. The former decreases as the segmentation becomes finer while the latter increases. A good segmentation finds more homogeneous regions without increasing too much complexity.

For balancing the intra and inter components of Zhang’s function, we used 22/S(f) as a weight for the first component. The division by the maximum entropy has a role of evening the weight for images with different color diversity. The constant was found empirically running the experiment several times. There was no need for a specific weight on the second component as the images have the same number of pixels.

A graphic was plotted for each image on the base. These graphics contain a curve for each method and show how it performed based on the number of regions. As we consider that is more important to analyze segmentation with fewer regions, we plotted the regions’ dimension in a log scale.

To measure how our methods performed against another we calculated a score based on the area between the two curves as the proportion of this area where our method’s curve was below. An ordered bar graphic was generated containing results of all images, when a bar is greater than 50% it means our method outperformed the other for that image.

Figure 2 shows an example of the curves generated for the sample “138078”. It is relevant to highlight that the score can reach 100% even if it was just slightly better on all of the number of regions evaluated.

Fig. 2.
figure 2

Curves from sample “138078”

Full size image
Fig. 3.
figure 3

(a), (b), (c), (d), (e), (f), (g), and (h) shows how better a method was in relation to another.

Full size image

Figure 3 shows all the bar graphics obtained in the experiment. The average color error was better in 80%, 83%, 87% and 75% of the images with an average score of 74.33%, 81.10%, 75.23% and 72.04% in relation to the area, height, volume and SLIC, respectively. Also, the entropy was better in 77%, 86.33%, 71.67% and 78% of the images with a an average score of 69.78%, 82.83%, 66.07% and 72.34% in relation to the same methods, respectively.

The results shows that, though not for every case, the color operators where able to find good segmentations and also in finding segmentations that looked quite different.

6 Conclusion

This paper proposes an extension of the attribute operators to color images. This extension is supported by two pillars: (i) the processing of a color gradient by thresholding decomposition; and (ii) the choice of color criteria such as color features or statistics, in addition to well known structural ones.

Objects are well represented by valleys in the color gradient. This gradient is thresholded in a set of binary slices and their connected components are measured and assessed according to the chosen operator criterion. Connected components that do not satisfy the criterion are discarded; the remaining ones are added together to compose the operator result.

This paper also shows the application of two color attribute operators to improve the image segmentation of color images. It allows the homogeneity of the resulting regions to be decreased in expense of increasing their numbers by adjusting a threshold value. In an experiment our methods provided better segmentation in most of the images.

Besides attribute operators were extended to color images, they became more versatile with the extension of criteria to color information. Color attribute operators have been also applied to solve image compression. In [14], entropy from local color information [12] were applied to improve entropy encoding of color images for data compression.

Future works include the proposal of improvements to the implementation of color attribute operators and the proposal of new color criteria for attribute color processing.