A Semi-Vectorial Hybrid Morphological Segmentation of Multicomponent Images Based on Multithreshold Analysis of Multidimensional Compact Histogram

Adles Kouassi^1,2,3, Sié Ouattara^1,2, Jean-Claude Okaingni^1,2, Wognin J. Vangah^1,2, Alain Clement⁴

¹Laboratory of Signals and Electrical Systems (L2SE), Institut National Polytechnique Houphouët Boigny, Yamoussoukro, Côte d’Ivoire.
²Institut National Polytechnique Houphouët Boigny (INPHB), Yamoussoukro, Côte d’Ivoire.
³Ecole Supérieure des Technologies de l’Information et de la Communication (ESATIC), Abidjan, Côte d’Ivoire.
⁴Institut Universitaire de Technologie d’Angers (IUT), Angers, France.

DOI: 10.4236/ojapps.2017.711043                

Abstract

In this work, we propose an original approach of semi-vectorial hybrid morphological segmentation for multicomponent images or multidimensional data by analyzing compact multidimensional histograms based on different orders. Its principle consists first of segment marginally each component of the multicomponent image into different numbers of classes fixed at K. The segmentation of each component of the image uses a scalar segmentation strategy by histogram analysis; we mainly count the methods by searching for peaks or modes of the histogram and those based on a multi-thresholding of the histogram. It is the latter that we have used in this paper, it relies particularly on the multi-thresholding method of OTSU. Then, in the case where i) each component of the image admits exactly K classes, K vector thresholds are constructed by an optimal pairing of which each component of the vector thresholds are those resulting from the marginal segmentations. In addition, the multidimensional compact histogram of the multicomponent image is computed and the attribute tuples or ‘colors’ of the histogram are ordered relative to the threshold vectors to produce (K + 1) intervals in the partial order giving rise to a segmentation of the multidimensional histogram into K classes. The remaining colors of the histogram are assigned to the closest class relative to their center of gravity. ii) In the contrary case, a vectorial spatial matching between the classes of the scalar components of the image is produced to obtain an over-segmentation, then an interclass fusion is performed to obtain a maximum of K classes. Indeed, the relevance of our segmentation method has been highlighted in relation to other methods, such as K-means, using unsupervised and supervised quantitative segmentation evaluation criteria. So the robustness of our method relatively to noise has been tested.

Keywords

Morphological Segmentation, Vectorial Orders, Semi-Vectorial Segmentation, Multidimensional Compact Histogram, Multi-Thresholds, Fusion Inter-Class, Classification

1. Introduction

With the advancement of electronics and computing, image has become a fundamental vector of computing and communication [1] .

In view of the technological advances of the sensors and the storage memory capacity, multicomponent images (color, multispectral, hyperspectral and multimodal) are more and more solicited in relation to scalar images (gray levels) because of their richness to characterize a given scene [2] .

The new challenge facing experts in various fields is the processing of this mass of images in order to extract useful information for the purpose of making decisions [3] .

In the field of image processing, segmentation plays a leading role because it is undoubtedly the task which mobilizes more effort [4] .

Conceptually, segmentation consists of extracting from the image primitives, either of contour type or of region type [3] [4] . These primitives will be exploited later to perform pattern recognition, registration, matching, compression, etc.

There are several types of approaches to segmentation. These approaches can be grouped into two large families [3] [4] : region and contour. The contour search approach delineates the regions of the image [5] . A contour is a set of pixels forming a boundary in two or more neighboring regions, it is defined by a rapid variation of the characteristic gray level, color or texture. The search for contours in an image has been studied since the origin of the work on digital imaging [6] . The regions approach aims to partition the image into related subsets of connected pixels. For the implementation of this approach we are confronted with the definition of the criterion of homogeneity intervening in the process of the segmentation [7] [8] . There are four types of methods: regions growth, division of regions, division/fusion, segmentation by classification. The main idea of regions growth method is to start from a starting point or point of origin and extend it by adding the boundary points that satisfy the criterion of homogeneity. Regions division methods consist in dividing the image in a recursive manner as long as a criterion of homogeneity over the region is not verified. These methods successively combine a method of dividing the image into small homogeneous regions such as that described above and a method of fusion of the connected regions and the like in the sense of a grouping predicate.

Classification segmentation involves partitioning a set of pixels of vector attributes into k disjoint classes. Each class groups pixels with characteristics as similar as possible. Obviously the pixels of two distinct classes have very different attributes. In contrast to the previous approaches, this approach only considers the characteristic vectors. To conclude, segmentation into regions requires a pixel connectivity analysis in the labeled image.

In addition, those based on the thresholding of monodimensional (1D) histograms have shown their efficiency in terms of speed of execution and segmentation quality [9] [10] [11] . Thresholding techniques can be divided into two categories: binary thresholding and multi-thresholding. In binary thresholding, the image is segmented into two class regions. Indeed, pixels with gray values greater than a certain value (threshold) T are classified as object pixels, and others with gray values less than T are classified as background pixels. In multiple thresholding, the image is segmented into several classes. Several contributions have been made in the literature, as is the case of P. Campadelli et al. which proposed a method of segmentation of color images of size M × N using the method of Scale-space filtering [12] . Also note that Tominaga has segmented color images with thresholds also by analysis of scalar histograms, but it works only in a fixed color space [13] .

Unfortunately, the vectorial aspect of multicomponent images makes it difficult to apply directly to scalar methods, particularly those based on multivariate histogram analysis for the following reasons: i) order on vectors and ii) topology of connectivity in a discrete multidimensional space.

Indeed, the approach of vectorial morphological segmentation by analysis of multidimensional (nD) compact histograms [14] that we propose in this paper is an extension of the segmentation by classification. It is based on a multi-thresholding of the monodimensional compact histograms resulting from the modal components of the multivariate image and a morphological order of the attributes vectors of its nD compact histogram with respect to constructed threshold vectors resulting from the multi-thresholding. Moreover, our method of morphological vectorial segmentation allows the use of different types of order for the classification of tuples and presents an optimal algorithmic complexity and a proven speed of execution. The multi-thresholding segmentation approach used in this work is inspired by the work of Otsu and other authors [8] [9] [10] [11] .

To facilitate the manipulation of nD histograms, the nD compact histogram [14] is used. It has the advantage of being computed quickly from the multicomponent image, of having a compactness of the attribute vectors and of occupying a reduced memory space.

The application of a complete lattice to the attributes vectors or “colors” to the compact histogram makes it possible to order the vectors and render the histogram nD compact scalar by substituting the tuples for their order number [15] [16] .

Thus, this paper presents an original method of semi-vectorial hybrid morphological segmentation of multicomponent images based on multi-thresholding analysis of compact multidimensional histograms.

For the understanding of this work, the rest of the document is organized as follows: in section 2, we present the principle and the algorithm of the proposed approach, then in section 3, a theoretical and experimental validation of our approach is presented. We conclude with some prospects for future work.

2. Principle and Algorithm of the Proposed Semi-Vectorial Morphological Segmentation Method

2.1. Principle

Let I, a P-component image (P ≥ 2). The principle is declined in several steps (see the flowchart in Figure 1).

a) We first construct the compact histogram related to the image I in order to solve the problem of coding and manipulation of nD histograms. Indeed, the compact histogram stores only the E cells actually occupied in clear it removes the empty cells. For an image with P components, a table of size E × P for storing the tuples in the lexicographic morphological order and a table of size E × 1 corresponding to the number of associated pixels (the number of tuples).

Let Hc be the nD compact histogram of the image I containing only the tuples

Figure 1. The flow chart of the proposed hybrid semi-vectorial morphological segmentation of multicomponent images.

and i a fixed row of Hc.

Let j describing the number of planes of the image varying from 1 to P. A tuple in the nD compact histogram can be described by the triplet $\left(i,H{c}^i,E_i\right)$ where $E_i=card\left(H{c}^i\right)$ represents the cardinal or the number of a tuple at the row i in $Hc$ .

Let $\text{I}=\left[{\text{I}}_{\text{1}},\cdot \cdot \cdot ,{\text{I}}_{\text{j}},\cdot \cdot \cdot ,{\text{I}}_{\text{P}}\right]$ and $H{c}_j^i$ the j^th multimodal component of the tuple located at row i of Hc, with I_j the j^th component of the image.

b) Then we segment each component (I_j) of the image I by multi-thresholding into a fixed number of classes K (K ≥ 2).

Let $K^j=K_{\max }^j$ be the number of classes obtained for the component I_j of the image I. Let be H_j the marginal monodimensionnal compact histogram of the j^th component of the image I(I_j) and Ni the number of pixels of a gray level of H_j at the row i.

To generalize, let us call $H_j^i$ the gray level at the row i of the j^th 1D compact histogram of the image I(I_j) and by $N_j^i$ the number of pixels associated.

The multi-thresholding used here is inspired by the Otsu method applied to the compact marginal 1D histograms H_j. Thus, for a given component j, it produces $K^j-1$ thresholds denoted $\left[t_1^j,t_2^j,\dots \dots .,t_{Kmax-1}^j\right]=T^j$ ordered in ascending order for a partition of the image into K classes $\left[C_1^j,C_2^j,\cdot \cdot \cdot ,C_K^j\right]$ where $K=K_{\max }=K^j$ . They take their values in H_j. Here, we denotes $T^j$ the vector of the segmentation thresholds of the component I_j.

The thresholds are obtained by the optimization of Equation (1) in which σ_Intra defines the standard deviation intra-classes whose expression is explicitly given by Equation (2) and other parameters defined by Equations ((3) and (4)).

$\left\{t_1^j,t_2^j,\cdot \cdot \cdot ,t_{K-1}^j\right\}=\arg \left\{\underset{t\in H_j}{\max }{\sigma }_{Intra}^2\left\{t_1^j,t_2^j,\cdot \cdot \cdot ,t_{K-1}^j\right\}\right\}$ (1)

${\sigma }_{Intra}^2={\displaystyle {\sum }_{n=1}^K{w}_n\left({\mu }_n-{\mu }_T\right)}$ (2)

$w_n={\displaystyle {\sum }_{m=t_{n-1}^j}^{t_n^j}{P}_m}$ (3)

${\mu }_n={\displaystyle {\sum }_{m=t_{n-1}^j}^{t_n^j}\raisebox{1ex}{$m.P_m$}\!\left/ \!\raisebox{-1ex}{$w_n$}\right.}$ (4)

where P_m and µ_T are respectively the probability of a gray level pixel m and the total average of the gray levels of the j^th component of the image I.

c) On the basis of the thresholds calculated on each component of the image, if $K^1=K^2=\cdot \cdot \cdot =K^j=\cdot \cdot \cdot .=K-1$ then we construct $K-1$ threshold vectors S_k with k varying from 1 to K − 1, such that the threshold vector of rank k (S_k) has the scalar thresholds of rank k ( $t_k^j$ ) from each component of the image I, with $S_k=\left(t_k^1,t_k^2,\cdot \cdot \cdot t_k^P\right)$ .

In the contrary case, a cross product combination of the partitions of the components of the image is realized.

d) In the first case where the number of classes is fixed and equal to K, the tuples of the nD compact histogram (Hc) are first ordered with respect to the vector thresholds S_k according to a vectorial order of choice and then the K partitions are created. In the case of a complete order, all tuples are immediately assigned to the different classes, otherwise the remaining pixels are assigned to the nearest class. In the second case where the number of classes is variable by class, an over-segmentation is performed and then an interclass fusion is applied to obtain at a maximum the K desired classes.

Note that in this paper, we used the marginal vectorial order, the lexicographic vectorial order and the hybrid vectorial order.

2.2. Algorithm

[Iseg]=Fonction FonctSegMorphologiqSemiVectorial (I, K)

// I : Multicomponent image

// K : Number of classes

// Iseg : Segmented image into K classes

P = FonctNberComponents (I) // Return the number of components of I

Hc_nD = FonctHistoCompactnD (I) // Return the nD compact histogram of I

For j =1 to P

H(j).Histo_1D = HistoCompactnD (Ij) // return the 1D compact histogram of components of I

T(j).T = FonctSegMultiThresold (H(j).Histo_1D) // Multi-thresholding of Histo_1D

K(j).K = FonctNberComponents (T(j).T) // Return the number of threshold of Hj

End

If ( K(1).K = K(2).K =….= K − 1 ) then

For k =1 to K − 1

S(k).S = FonctVectorsThresold(T(j).T) // Construction of threshold vectors (K-uplets)

End

H = [Hc_nD ; S(1 à K − 1).S] // concatenation of Hc_nD tuples and threshold vectors

H_ord =FonctOrdonnement (H, ChoiceOrder) // Order tuples according to ChoiceOrder

Classes.C=FonctConstructionClasses (H_ord, S(1 à K − 1).S ) // Classification into K classes

Iseg=FonctImageSegmentée (I, Classes.C) // Image segmentée

Else

ClassesSurSegmente.C=FonctCombinatorial (H_ord, S(1 à K − 1).S ) // over-segmentation

Classes.C=FonctFusionInterClasses (ClassesSurSegmente.C) // Fusion interclasses into K classes

Iseg=FonctImageSegmentée (I, Classes.C) // Segmented image

End

3. Segmentation Results and Evaluation of the Proposed Approach

In this section, we first present some segmentation results on synthetic and real images from our proposed segmentation method using some vectorial orders and compared with those of the K-means method [17] . Then a quantitative evaluation through supervised evaluation methods and unsupervised evaluation of the quality of the segmentation through different vectorial orders with respect to K-means is performed. We conclude this section with an assessment of the robustness of our approach to noise.

3.1. Segmentation Results

In order to highlight the relevance of the proposed approach, segmentations have been performed on natural images using marginal order, lexicographic order and hybrid order with absolute referent. Some original images and their segmentation results by the proposed method and the K-means method are presented in Figures 2-4 by varying the number of classes from 2 to 4. Moreover, a series of images of forsythia of which we have the ground truths (reference

Figure 2. Segmentation into 2 classes by the proposed method and K-means.

Figure 2. Segmentation into 2 classes by the proposed method and K-means.

Figure 3. Segmentation into 3 classes by the proposed method and K-means.

Figure 3. Segmentation into 3 classes by the proposed method and K-means.

Figure 4. Segmentation into 4 classes by the proposed method and K-means.

Figure 4. Segmentation into 4 classes by the proposed method and K-means.

Figure 5. Segmentation of Forsythia images into 2 classes by the proposed method and K-means.

Figure 5. Segmentation of Forsythia images into 2 classes by the proposed method and K-means.

expert segmentations from [18] ) have been segmented into two classes as shown in Figure 5.

These segmentation results clearly show the visual relevance of our approach through its various variants. However, a quantitative evaluation is required to validate our method, hence the following section.

3.2. Evaluation of Segmentation Results

Different assessment methods exist in the literature and can be grouped into two classes: supervised methods and unsupervised methods. In this work, on the one hand for the supervised evaluation, we used Vinet’s criterion [14] which calculates the rate of conformity errors of the segmentation maps by an optimal matching; this criterion has been applied to the series of images of Forsythia, of which we have ground truths. On the other hand, for the unsupervised evaluation, we have retained the Levine-Nazif Intra-region criterion and the Zeboudj criterion [14] because they are commonly used and also because of their relevance.

The Levine-Nazif Intra-region criterion favors segmentation with homogeneous classes and relies on intra-class energy. However, Zeboudj’s criterion takes into account intra-class energy and inter-class energy, thus favoring segmentations with homogeneous and well-separated classes.

The latter two criteria give the best score to the best segmentation. The evaluation results of our segmentation approach and those of K-means are presented in the tables below with an accuracy of 10⁻⁴.

In Table 1, we present some results of supervised evaluation by the criterion of Vinet, in green the best segmentation and in red the second best segmentation. The values recorded in the table correspond to the error rate between the segmented image and the ground truth. It appears that the proposed method presents better segmentations globally than K-means. On the three variants of the proposed method, vectorial morphological segmentation in hybrid order is the best, then comes the lexicographic order.

Table 2 presents the unsupervised evaluation of natural images by the Levine-Nazif criterion. This table shows that for k varying from 2 to 3 the vectorial morphological segmentation in marginal order and K-means have the same performances and are the best on all the images processed. When the number of classes k ≥ 4, the three variants converge to the same interclass fusion giving identical segmentations and a performance identical to K-means.

Table 3 illustrates the non-supervised evaluation by the Zeboudj criterion. It is found that for this criterion, the proposed approach gives better results and inversely, it is the case of the images House and Lena.

Consequently, it could be said that the relevance of the segmentation methods is related to the content of the image and the criterion used.

3.3. Performance at Noise

In order to demonstrate the robustness to the noise of our approach, we first added Gaussian noise of different average powers Pb to the synthetic image Savoise [15] . An example of adding noise is illustrated in Figure 6. Then, the noisy images have been segmented into different number of classes k varying

Table 1. Supervised evaluation of a series of Forsythia color images.

Table 2. Evaluation of natural color images by the Levine-Nazif intra-region criterion.

Table 3. Evaluation of natural color images by the Zeboudj criterion.

Figure 6. Original Savoise image, noisy Savoise images and their segmentations into 3 classes by the proposed method and K-means.

Table 4. Robustness of the proposed semi-vector morphological segmentation and K-means with respect to Gaussian noise.

from 2 to 5, an illustration of which is given in Figure 6.

Indeed, an evaluation of the relevance of the segmented images is presented in Table 4 where the best segmentation is the one whose criterion value is the smallest and indicated in green. Moreover, when the value of the criterion is less than 5%, the segmentation is qualified as good. On the whole of the images processed, it can be seen through this table, for some, that the proposed method is robust to the noise K-means and inversely. This could be related to the content of the image.

4. Conclusion

In this paper, we have developed a semi-vectorial morphological segmentation strategy with different variants capable of segmenting color images and more generally multicomponent images. The performance of our approach was evaluated and demonstrated its relevance to K-means through quantitative criteria for supervised and unsupervised evaluation of segmentation. On the other hand, the robustness to the Gaussian noise of the proposed segmentation method was highlighted. We also find that the relevance of the quality of a segmentation is on the one hand to the evaluation criterion used and on the other hand to the content of the image. In perspective, we plan to develop a purely vectorial morphological segmentation method.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Bitam Abdelmadjid, (2013) Multispectral Image Analysis and Segmentation: Application to MSG Images. PhD Thesis, Mouloud Mammeri University of Tizi-Ouzou, Tizi-Ouzou, Algerie.
[2]	Ouattara, S. (2009) Multicomponent Image Segmentation Strategies by Analyzing Multidimensional Histograms: Application to Color Images of Histological Sections. PhD Thesis, University of Angers, Angers, France.
[3]	Philip, S. and Cocoquevez, J.P. (1995) Image Analysis and Segmentation. Masson, Paris.
[4]	Ouardia, A. (2011) Segmentation of Images by Bidimensional Histogram Thresholds. Memory of Magister, Mouloud Mammeri University of Tizi-Ouzou, Tizi-Ouzou, Algerie.
[5]	Busin, L. (2003) Segmentation of Color Images by Analysis of Histogram Monodimensional Colors. Memory of DEA, University of Science and Technology of Lille and Central School of Lille, Lille, France.
[6]	Herbulot, A. (2007) Non-Parametric Statistical Measurements for the Segmentation of Images and Videos and Minimization by Active Contours. Ph.D. Thesis, The University of Nice-Sophia Antipolis, Nice.
[7]	El Merabet, Y. (2014) Segmentation of Color Images by Combination LPE-Regions/ LPE-Contours and Fusion of Regions. Application to the Segmentation of Roofs from Orthophotoplans. Ph.D. Thesis, University of Technology Belfort Montonberliard, Belfort.
[8]	Ghandour, A. (2010) Segmentation of Color Images by Mathematical Morphology: Application to Images Microscopies. Ph.D. Thesis, The University of Toulouse, Toulouse.
[9]	Madhava Raja, N.Sri, Rajinikanth, V. and Latha, K. (2014) Otsu Based Optimal Multilevel Image Thresholding Using Firefly Algorithm. Modelling and Simulation in Engineering, 2, Article ID: 794574. https://doi.org/10.1155/2014/794574
[10]	Rajinikanth, V., Aashiha, J.P. and Atchay, A. (2014) Gray-Level Histogram based Multilevel Threshold Selection with Bat Algorithm. International Journal of Computer Applications (IJCA), 93, 1-8. https://doi.org/10.5120/16296-6035
[11]	Arora, S., Acharya, J., Verma, A. and Panigrahi, P.K. (2008) Multilevel Thresholding for Image Segmentation through a Fast Statistical Recursive Algorithm. Pattern Recognition Letters, 29, 119-125. https://doi.org/10.1016/j.patrec.2007.09.005
[12]	Campadelli, P., Medici, D. and Schettini, R. (1997) Color Image Segmentation Using Hopfield Networks. Image and Vision Computing, 15, 161-166. https://doi.org/10.1016/S0262-8856(96)01121-3
[13]	Tominaga, S. (1992) Color Classification of Natural Color Images. Color Research and Application, 17, 230-239. https://doi.org/10.1002/col.5080170405
[14]	Ouattara, S., Loum, G.L. and Clément, A. (2011) Unsupervised Segmentation Method of Multicomponent Images Based on Fuzzy Connectivity Analysis in the Multidimensional Histograms. Engineering, 3, Article ID: 4141.
[15]	Ouattara, S., Kouassi, A., Okaingni, J.C., Koffi, A., Loum, G. and Clement, A. (2016) A New Hybrid Order Approach to Morphological Color Image Processing Based on Reduced Order with Adaptive Absolute Reference. Engineering, 8, 633-645. https://doi.org/10.4236/eng.2016.89057
[16]	Kouassi, A.F., Ouattara, S., Okaingni, J.-C., Koné, A., Vangah, W.J., Loum, G. and Clement, A. (2017) A New Vectorial Order Approach Based on the Classification of Tuples Attribute and Relative Absolute Adaptive Referent: Applications to Multicomponent Images. Journal of Software Engineering and Applications, 10, 546-563. https://doi.org/10.4236/jsea.2017.106030
[17]	Wang, X. and Bai, Y. (2016) The Global Minmax k-Means Algorithm. Springerplus, 5, 1665-1679. https://doi.org/10.1186/s40064-016-3329-4
[18]	Clément, A. and Vigouroux, B. (2003) Unsupervised Segmentation of Scenes Containing Vegetation (Forsythia) and Soil by Hierarchical Analysis of Bi-Dimensional Histograms. Pattern Recognition Letters, 24, 1951-1957. https://doi.org/10.1016/S0167-8655(03)00034-5