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:
|
| 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) |
 |
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:
where d∞ the distance of Chebyshev and KεN*.
| Table 2: |
Neighborhood in 2D space. with K = 2 |
 |
| Table 3: |
Statistics of connected components based on fuzzy neighborhoods
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.
|
| 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:
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.
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:
The inside contrast of a region Ri is:
The outside contrast of a region Ri is:
where Fi is the boundary of Ri and li the length of Fi.
The contrast of Ri is:
The global contrast is finally:
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.
|
| Fig. 3: |
Segmentation results of 24-bit 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.
Subscribe Today
