Subscribe Now Subscribe Today
Research Article
 

Full 3D Compact Histogram Segmentation of Color Images



S. Ouattara, A. Clement and B. Vigouroux
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

In this study we present a fast unsupervised segmentation method of color images based on the 3D compact histograms. In order to resolve the problems of handling 3D histograms and to palliate the defects of the marginal and bi-marginal approaches, the use of the 3D compact histogram to accomplish classification in the color space RGB proved to be necessary. The interest of this study is based on the use of compact histogram which is a structure with reduced volume of colors without loss of data of the classical histogram and favouring a fast segmentation of color images. Knowing that there is no universal method of segmentation, our aim is to realize an acceptable segmentation that is the most relevant in the sense of a criterion of evaluation of segmentation. The relevance of the choice of peaks is not evident generally and is complexified when the dimension of the space increases; because of the integration of fuzzy neighborhood associated with an algorithm of connected components labeling in our algorithm of classification establishes the first approach of segmentation. The second approach consists in re-quantifying the colors of the histogram before making the classification, this limit the time consuming of segmentation and the effects of over-segmentation; this also the purpose of the first approach. A stage of performance appraisal of segmentation allows bringing to light the relevance of both methods and a comparison of both approaches is so discussed.

Services
Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

S. Ouattara, A. Clement and B. Vigouroux, 2011. Full 3D Compact Histogram Segmentation of Color Images. Asian Journal of Scientific Research, 4: 42-52.

DOI: 10.3923/ajsr.2011.42.52

URL: https://scialert.net/abstract/?doi=ajsr.2011.42.52
 
Received: May 23, 2010; Accepted: July 28, 2010; Published: October 12, 2010



INTRODUCTION

Image segmentation is an essential step in image analysis because it determines the quality of future interpretation of the component image and substantially influences the decision. It is a major problem, difficult and for which there is no universal solution. Several methods of segmentation of color images give very good results and can be classified into two families according to whether or not using the spatio-colorimetric.

Pixel classification, apart from the clustering methods (Saidur et al., 2008), other methods when working on the concept of color face the problem of data dimension. Therefore a comprehensive analysis of articles (Clement and Vigouroux, 2003; Tremeau et al., 2004; Lezoray and Charrier, 2009; Haidar et al., 2010; Yuan et al., 2010) allow us to distinguish five color segmentation approaches: the scalar approach, the marginal approach, bi-marginal approach, the approach bi-scalar and vector approach. The scalar approach is to first merge the components into a single color and then segmenting it or choose the plan most appropriate to perform the segmentation. The approach makes a marginal segment on each color component and then merges the segmentation maps into one (Busin et al., 2004). The bi-marginal approach segments colorimetric matching components, or RG, RB and GB in the RGB space and then merges the segmentation maps (Lezoray and Charrier, 2009; Xue et al., 2003; Kurugollu et al., 2001). The bi-scalar approach is to choose a couple of plans to conduct a colorimetric or principal component analysis and then choose the two largest components of energy to perform the segmentation. The segmentation approach vector segmented image directly using a vector information (Geraud et al., 2001; Park et al., 1998). The main disadvantage of marginal and scalar approaches is not taking into account the inter-color correlation component. Their advantage is that it is generally simpler and faster than the vector methods. Faced with the increasing development of microprocessor performance and optimization techniques, vectorial approaches of segmentation can be developed. In this study, we present a 3D method for unsupervised hierarchical clustering based on the analysis of 3D compact histogram incorporating a fuzzy neighborhood concept for the extraction of peaks. One advantage of the method is conditioned by the speed advantages of compactness of the histogram as representing optimal and flexible use of classical histogram which is a reminder that the next section. A second advantage of the method is the appearance vector which takes into account the correlation between the components of the image. The difficulty of the analysis of 3D histogram for the extraction of the peaks is generally related to the volume of data, the dimension of space, 3D in our study which must be added a fourth axis which is the population of colors. An adequate extraction of the peaks means taking into account the dispersion of colors in the 3D space (Xuan and Fisher, 2007) and their staff to resolve problems of over-segmentation and relevance of the choice peaks and thus the integration of a process of labeling connected components by fuzzy neighborhoods in the process of looking for peaks of histogram improves the quality of segmentation. In a second phase to solve the problem of dispersion of colors that can bias the choice of the best peaks we do a re-quantization of color prior to extraction of peaks and classification, a comparison of two approaches and is discussed through a step evaluation of segmentation results. Our two methods are compared with K-means which is a famous method, powerful and widely used in image processing and statistics. Part of this project was realized during my PhD thesis at the University of Angers in France and aure part within the framework of my research activity to the INPHB since 2006 until now.

Compact multidimensional histograms: The histogram of a color image has a data volume of 128 MB, this amount of data poses difficulties of manipulation, making it prohibitive implementation of many methods of segmentation based on color histogram analysis and 3D.

To solve the problem of multidimensional histograms, (Clement and Vigouroux, 2001) was proposed an algorithm for computing a compact multidimensional histogram to reduce considerably without loss of information storage space occupied by the classical histogram, it contains only the colors actually present in the color image, an example of compact (3D) color histogram is shown in Fig. 1. For example for a color image of size MxN, the compact 3D histogram reduces the volume of the compact histogram by a factor a:

Image for - Full 3D Compact Histogram Segmentation of Color Images
Fig. 1: Advantage of compact 3D histogram, M = N = 256 and Q = 8 bits per component

Table 1: An example of compact 3D histogram of a color image in RGB space (8 bits per plane)
Image for - Full 3D Compact Histogram Segmentation of Color Images

Image for - Full 3D Compact Histogram Segmentation of Color Images
(1)

where Q is the number of bits which is encoded on each color plane and C = MxN. An illustration of the advantages of compact 3D histogram is shown in Table 1.

Connected component labeling and fuzzy neighborhoods: The Connected Component Labeling (CCL) play an important role because it allows the master data spread in the topological space considered, in image analysis this step is important because it guides and facilitates the segmentation of images. The choice of a neighborhood as defined by Rosenfeld for labeling data in the images affects the result of segmentation by Ouattara and Clément (2007), we chose the full-connectivity for the labeling of tuples in a multidimensional space, but this neighborhood is also limited in a way usually, it is for this reason that we propose in this study using fuzzy neighborhoods in an attempt to improve the quality of the segmentations produced by our algorithm segmentation proposed in the next section. Many studies (Udupa et al., 2002; Herman and Carvalho, 2001; Miyamoto and Hayakawa, 2006) carried out on fuzzy connectedness or connectivity have shown their effectiveness in the segmentation by a rational choice of the membership function of proximity, similarity and affinity. The membership function of fuzzy neighborhood considered here is classic because of its use in current approaches to fuzzy segmentation (Miyamoto and Hayakawa, 2006; Bloch, 2005). Let P, a 3D color of histogram and Q that any color of histogram, fuzzy neighborhood with respect to P is the following:

Image for - Full 3D Compact Histogram Segmentation of Color Images
(2)

where d the distance of Chebyshev and KεN*.

Table 2: Neighborhood in 2D space. with K = 2
Image for - Full 3D Compact Histogram Segmentation of Color Images

Table 3: Statistics of connected components based on fuzzy neighborhoods of color images
Image for - Full 3D Compact Histogram Segmentation of Color Images

The neighborhood set corresponds to a set of fuzzy neighborhoods because K varies, which can appreciate the color dispersion in the topological space in the 3D connected component labeling. Table. 2 shows an example of fuzzy neighborhood for K = 2 needed to achieve labeling.

The algorithm for labeling Connected Components (CC) realized by Ouattara and Clément (2007) remains valid for the neighborhoods defined by Eq. 2. In (Ouattara and Clément, 2007) was treated the case K = 1, there is widespread labeling component for K>1. The difficulty of this generalization lies in the search for neighboring fuzzy due to the fact of non-linearity of the histogram compact. The complexity of the labeling algorithm is at worst in Θ (N2), with N the number of colors in the 3D histogram compact. Table 3 shows some statistics of connected components of color images for different values of K.

Unsupervised hierarchical 3D color classification and state of the art of evaluating results of Segmentation: The absolute similarity between two colors is something very complex and difficult to model using a mathematical model, however, we may refer to the work of MacAdam (1981). Many works are based on the definition of a fuzzy model (Miyamoto and Hayakawa, 2006), hence the interest of the definition of a fuzzy model of neighborhoods in this study.

The dimension of color space creates an over-segmentation generated by the classification methods (Lezoray and Charrier, 2009). To solve the problem of the color dispersion, we have also implemented a second approach consisting in re-quantify colors and performing the classification for K = 1 (classical CC). This second approach can be considered as dual to the concept of fuzzy neighborhood. A comparison of two approaches is discussed.

Image for - Full 3D Compact Histogram Segmentation of Color Images
Fig. 2: An example of hierarchical classification illustrated with a 1D Hcec

Principle of 3D hierarchical classification: Consider the compact 3D histogram denoted Hc of a color image. A second histogram denoted Hcec is produced from Hc by replacing the values of the population field with compact values. Thus, we count the number of different values of the population field that we denote NED. The compact values of the population field in Hcec vary from 1 to NED. The link between normal values and compact values is achieved by a correspondence table. From a geometrical point of view, the Hcec does not modify the choices of the peaks and the results of segmentation. Further, it speeds up the classification process (optimization of algorithmic complexity).

The hierarchical principle of classification based on the Hcec illustrated in Fig. 2 requires as input a population threshold (S), which sets the minimum population of a peak and a value of K for the considered fuzzy neighborhood. In the re-quantization approach, K is set to 1.

The nodes really built are indexed by numbers; The leaves surrounded by a circle correspond to the peaks recognized. In black, set the branches explored and the nodes or leaves unsuccessful due to a lower population than threshold S.

State of the art of evaluating results of segmentation: Many segmentation algorithms have been proposed in recent decades (Lezoray and Charrier, 2009; Freixenet et al., 2002; Gouiffes, 2005). They are based on different approaches: contour, region and texture.

With a multitude of methods proposed, the problem of assessing the quality of segmentation becomes paramount. Usually, the efficacy of a new algorithm is illustrated by presenting some results of segmentation, which allows only subjective conclusions. There is currently no method of absolute and generic to complete this assessment task, however, many studies dealing with this subject.

By Philipp-Foliguet and Guigues (2006) and Zhang et al. (2008) methods of assessment are grouped into two broad classes that are evaluating unsupervised and supervised evaluation: (1) The first group consists of assessment methods do not require any knowledge of the results segmentation to evaluate. Their principle is to estimate analytical criteria, or to estimate the quality of a segmentation result from statistics calculated on each region, detected contours and textures (Chabrier et al., 2006; Borsotti et al., 1998; Zeboudj, 1988). (2) The second contains the methods that assess the quality of a segmentation result by exploiting a priori knowledge (Vinet, 1991). This knowledge usually consist of a segmented image reference called ground-truth. It is directly accessible in the case of images, per account in the case of real images must be built by hand by an expert in the field of application: tracings made by physicians, geographers using computer tools drawings.

If you want to objectively compare methods, it is easier to use images, for which truth is well known, namely the segmentation was used to synthesize an image. The disadvantage of this approach is that these images do not represent all possible situations of real utilization.

Although, the assessment of real images is certainly more realistic, it raises other difficulties, the main one being that there is usually no single solution to the division of an image into regions relevant. Relevance of a region is indeed a concept highly dependent on the application. To evaluate the segmentation, we choose three methods as follows:

Vinet measure: This technique is a supervised evaluation method and therefore requires knowledge of reference segmentation, we consider here only the segmented images and segmentation of reference have the same number of classes. Let R, a segmentation consisting of regions Ri, i = 1,. .., M where M is the number of regions and V the reference segmentation consists of regions Vj such as j = 1,. .., M. The method of Vinet is to find pairs of regions Ck = Rik n Vjk with maximum coverage and it is defined by:

Image for - Full 3D Compact Histogram Segmentation of Color Images
(3)

Where A is the number of pixel in the image.

Levine and nazif criterion: For this criterion when the deviation (σk) of each region is zero, the value of this criterion is 1, it means that segmentation is ideal.

Image for - Full 3D Compact Histogram Segmentation of Color Images
(4)

Zeboudj criterion: Various studies have shown that this criterion is best suited to evaluate unsupervised segmentation (Chabrier et al., 2006). This index takes into account the inside contrast and the outside contrast regions measured on a neighborhood W (s) of the pixel s.

Consider the contrast between two pixels s and t, with f representing the intensity and L the maximum intensity defined by:

Image for - Full 3D Compact Histogram Segmentation of Color Images
(5)

The inside contrast of a region Ri is:

Image for - Full 3D Compact Histogram Segmentation of Color Images
(6)

The outside contrast of a region Ri is:

Image for - Full 3D Compact Histogram Segmentation of Color Images
(7)

where Fi is the boundary of Ri and li the length of Fi.

The contrast of Ri is:

Image for - Full 3D Compact Histogram Segmentation of Color Images
(8)

The global contrast is finally:

Image for - Full 3D Compact Histogram Segmentation of Color Images
(9)

The tests were performed on images of 24-bit color; it means 8 bits per color component. Regarding the re-quantization, each color component is recorded on q bits (q<8) with. The principle of the re-quantization is to keep the q bits of the 8 bits. However, the limit of q to 5 is justified by the fact that the visual quality of color images is generally preserved.

The segmentations were performed for K varying from 1 to 5 and q from 5 to 7 and the evaluation of segmentation in the following section recognizes that these values of K and q.

Figure 3 shows some results of image segmentation in Fig. 1 for the parameters K = {1, 3} and q = {5, 6}. Overall, the results are visually acceptable; an evaluation stage of segmentation results can highlight the interest of our segmentation approaches.

The evaluation of segmentation was performed on multiple images for different values of the parameters for the two segmentation approaches. Some images have been chosen to illustrate our results as shown in Fig. 4a-e.

Image for - Full 3D Compact Histogram Segmentation of Color Images
Fig. 3: Segmentation results of 24-bit color images

Image for - Full 3D Compact Histogram Segmentation of Color Images
Fig. 4: Evaluation of some segmentation results compared to K-means results (in bold the best segmentation by criterion)

From these results several remarks and discussions can be made:

From a general point of view, the introduction of fuzzy neighborhoods in the process of segmentation improved the quality of segmentation as indicated by one or more of three valuation methods
The second approach (re-quantization method) is also shown effectiveness in improving the quality of segmentation and also has the advantage of being fast
The difference between the two approaches feel better in real images because the merger generally involved the removal of certain peaks and changes in most cases the morphology of histograms, which influences the choice of the peaks of the hierarchical principle of method
An important note is that assessment methods do not converge to the same relevant segmentations
Fuzzy method is generally better than K-means and can thus be used in certain problems of segmentation
The poor performance of K-means are often due to arbitrary selection of centers of gravity of the classes and the non-convergence to the global minimum of the intra-class total energy, The performance can depend of evaluation criterion
The evaluation methods of evaluation do not converge to the same segmentation pertience, the choice of a method will depend on the set aim. In any rigor the criterion of Levine is advised

CONCLUSIONS

Taking into account inaccuracies in the images by using fuzzy neighborhoods and the dual approach to what the acoustic re-quantization improved the quality of segmentation compared to the classic account of a neighborhood (K = 1). However, the re-quantization approach has weaknesses on the segmentation of noisy images but has the advantage of being fast and produce coarse segmentation for q = 5.

One of the difficulties which the image processors are facing is the selection of the appropriateness of evaluation methods which do not converge to the same levels of classification for segmentation with the same number of classes due to higher segmentations with a number of different classes.

We have in view the integration of a fuzzy clustering approach in our classification.

Unlike the usual methods of segmentation, they can be used to segment textured images little less noisy. In addition they offer a range of possible segmentations whose best indicated by the endpoint considered.

REFERENCES

1:  Clement, A. and B. Vigouroux, 2003. Unsupervised segmentation of scenes containing vegetation (Forsythia) and soil by hierarchical analysis of bidimensional histograms. Pattern Recognition Lett., 24: 1951-1957.
CrossRef  |  Direct Link  |  

2:  Tremeau, A., C. Fernandez-Maloigne and P. Bonton, 2004. Image Numerique Couleur: De L`acquisistion au Traitement. Dunod Pulisher, Paris, France

3:  Clement, A. and B. Vigouroux, 2001. A compact histogram for the analysis of multicomponent images. Proc. Conf. GRETSI Signal Process., 1: 305-307.
Direct Link  |  

4:  Udupa, J.K., P.K. Saha and R.A. Lotufo 2002. Relative fuzzy connectedness and object definition, theory algorithms and applications in image segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 24: 1485-1500.
Direct Link  |  

5:  Herman, G.T. and B.M. Carvalho, 2001. Multiseeded segmentation using fuzzy connectedness. IEEE Trans. Pattern Anal. Mach. Intell., 23: 460-474.
Direct Link  |  

6:  Miyamoto, S. and S. Hayakawa, 2006. A fuzzy neighborhood model for clustering, classification and approximations. Rough Sets Curr. Trends Comput., 4259: 882-890.
Direct Link  |  

7:  Bloch, I., 2005. Fuzzy spatial relationship for image processing and interpretation: A review. Image Vision Comput., 23: 89-110.
CrossRef  |  

8:  Ouattara, S. and A. Clement, 2007. Labelling of compact multidimensional histograms for analysis of multicomponent images. Proceedings of the 21st conference GRETSI on the Image Processing, Sept. 11-14, Troyes, France, pp: 85-88
CrossRef  |  

9:  Vinet, L., 1991. Segmentation and mapping of areas of stereoscopic pairs of images. Ph.D. Thesis, University of Paris, Paris

10:  Lezoray, O. and C. Charrier, 2009. Color image segmentation using morphological clustering and fusion with automatic scale selection. Pattern Recognition Lett., 30: 397-406.
CrossRef  |  

11:  Freixenet, J., X. Munoz, D. Raba, J. Marti and X. Cufi, 2002. Yet another survey on image segmentation: Region and boundary information integration. Lecture Notes Comput. Sci., 2352: 21-25.
Direct Link  |  

12:  Gouiffes, M., 2005. Contributions of the color and the models of reflections for the extraction and the follow-up of the primitives. Ph.D. Thesis, University of Poitiers.

13:  Philipp-Foliguet, S. and L. Guigues, 2006. Evaluation of segmentation: State of the art, new indices and comparison. Signal Process., 23: 109-124.

14:  Zhang, H., J.E. Fritts and S.A. Goldman, 2008. Image segmentation evaluation: A survey of unsupervised methods. Comput. Vision Image Understand., 110: 260-280.
CrossRef  |  Direct Link  |  

15:  Chabrier, S., B. Emile, C. Rosenberger and H. Laurent, 2006. Unsupervised performance evaluation of image segmentation, special issue on performance evaluation in image processing. EURASIP J. Applied Signal Process., 2006: 1-12.
CrossRef  |  Direct Link  |  

16:  Borsotti, M., P. Campadelli and R. Schettini, 1998. Quantitative evaluation of color image segmentation results Pattern Recogn. Lett., 19: 741-747.
CrossRef  |  Direct Link  |  

17:  Zeboudj, R., 1988. Filtering, automatic thresholding, contrast and contours: The Pre-treatment with the image analysis. Ph.D. Thesis, University of Saint-Etienne, France.

18:  MacAdam, D.L., 1981. Color Measurement, Theme and Variation. Springer-Verlag, New York, pp: 228

19:  Yuan, X., C.X. Zhao and H.F. Zhang, 2010. Road detection and corner extraction using high definition lidar. Inform. Technol. J., 9: 1022-1030.
CrossRef  |  Direct Link  |  

20:  Haidar, S., B. Chebaro and B. Haidar, 2010. Video macrosegmentation using automatic analysis of similarity matrices. Inform. Technol. J., 9: 1003-1012.
CrossRef  |  Direct Link  |  

21:  Saidur, R., H.H. Masjuki, M. Hasanuzzaman and G.S. Kai, 2008. Investigation of energy performance and usage behavior of domestic refrigerator freezer using clustering and segmentation. J. Applied Sci., 8: 3957-3962.
CrossRef  |  Direct Link  |  

22:  Busin, L., N. Vandenbroucke, L. Macaire and J.G. Postaire, 2004. Color space selection for unsupervised color image segmentation by histogram multithresholding. Proceedings of the IEEE International Conference on Image Processing, (ICIP'04), Singapore, pp: 203-206

23:  Xue, H., T. Geraud and A. Duret-Lutz, 2003. Multi-band segmentation using morphological clustering and fusion application to color image segmentation. Proc. IEEE Int. Conf. Image Process., 1: 353-356.
CrossRef  |  

24:  Kurugollu, F., B. Sankur and A. Harmanci, 2001. Color image segmentation using histogram multithresholding and fusion. Image Vision Comput., 19: 915-928.
CrossRef  |  

25:  Geraud, T., P. Strub and J. Darbon, 2001. Color image segmentation based on automatic morphological clustering. IEEE Int. Conf. Image Process., 3: 70-73.
CrossRef  |  

26:  Park, S., I. Yun and S. Lee, 1998. Color image segmentation based on 3-D clustering: Morphological approach. Pattern Recognit., 31: 1061-1076.
CrossRef  |  

27:  Xuan, G. and P. Fisher, 2007. Maximum likelihood clustering method based on color features. Proceedings of the 1st International Conference on Color in Graphics and Image, (ICCGI'07), Saint-Etienne, France, pp: 191-194

©  2022 Science Alert. All Rights Reserved