# Unsupervised classification of pixels in color images by hierarchical analysis of bi-dimensional histograms

Alain Clément, Bertrand Vigouroux

► To cite this version:

Alain Clément, Bertrand Vigouroux. Unsupervised classification of pixels in color images by hierarchical analysis of bi-dimensional histograms. IEEE International Conference on Systems Man and Cybernetics, 2002, Hammamet, Tunisia. 10.1109/ICSMC.2002.1173390. hal-02114072

HAL Id: hal-02114072

https://hal.science/hal-02114072

Submitted on 24 Aug 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Unsupervised classification of pixels in color images by hierarchical analysis of bi-dimensional histograms

Alain Clément, Bertrand Vigouroux

Laboratoire d'Ingénierie des Systèmes Automatisés

Institut Universitaire de Technologie

BP 42018 - ANGERS CEDEX - France

bertrand.vigouroux@univ-angers.fr

**Abstract** – This paper presents an ew unsupervised algorithm for classifying pixels in color images, by means of a hierarchical analysis of color bi-dimensional histograms. The algorithm proceeds in two steps : a learning step and a decision step. It provides a number of classes which is function of an adjustable parameter (threshold S) depending on the precision required in terms of differenciation between colors.

**Index terms** – color image, unsupervised classification, hierarchical classification, bi-dimensional histogram.

## I - INTRODUCTION

A pixel in a color image can be considered as a three-dimensional (3D) vector whose components depend on the color space used (RGB, HSV, ...). Due to this vectorial nature, the pixel classification algorithms based on histogram analysis can be divided in three categories : (i) marginal algorithms in which the monodimensional (1D) histogram of each color plane is handled separately [1-5] ; (ii) full vectorial algorithms working on the color 3D-histogram ; and (iii) intermediate algorithms using bi-dimensional (2D) histograms by projection onto two of the three color planes. The first type (i) inherits all the existing work on monochrom images, but it does not take into account the correlation between color planes [6], unlike the second type (ii). However, handling a color 3D-histogram is not an easy task, due to the huge required memory space [7]. The difficulty can be overcome by requantifying each color component on a lower level number [8]. The third way (iii) has not been explored very much to date [9, 10]. We propose here a new unsupervised algorithm for classifying pixels in color images, based on the hierarchical analysis of 2D-histograms (section 2). The results are illustrated by applying the algorithm to the so-called image peppers (section 3).

## II - CLASSIFICATION

The objective is to merge into distinct classes the pixels that present similar colorimetric characteristics in a color image, in an unsupervised way. The algorithm works in two steps : a learning step and a decision step. It makes use of one of the three 2D-histograms of the color image.

A 2D-histogram of a color image I maps p(x₁,x₂), the number of pixels in I presenting the colorimetric components (x₁,x₂). If each colorimetric axis of I is quantified on Q bits, the 2D-histogram can be represented by an image J whose spatial resolution is equal to 2Qx2Q. The value p_n(x₁,x₂) of the pixel of coordinates (x₁,x₂) in J is obtained by a linear dynamic contraction of the histogram between 1 and M = min(p_max,255):

$$p_n(x_1, x_2) = \text{round} \left[ \frac{(M-1)p(x_1, x_2) - M p_{\min} + p_{\max}}{p_{\max} - p_{\min}} \right]$$

where p_m and p_max are respectively the minimum and maximum values of p. Thanks to this representation, the 2D-histogram analysis can be carried out with the tools developed for 8 bits gray level images.

### A - Learning step

It consists in a hierarchical decomposition of gray levels in J. For each gray level p_n peaks P_i are identified by labelling the connected components of J whose pixel values are greater than or equal to p_n. Each peak is then iteratively decomposed into narrower peaks, from gray level 0 to gray level 255. A peak is labelled as significant if it represents a population greater than or equal to a threshold S (expressed in percent of the total population in image I). The procedure is illustrated on figure 1 (drawn in one dimension for clarity). We shall name kernels K_i the peaks corresponding to circled leaves on the right of the figure. In other words, kernels are significant peaks (part a of figure 1) without descendants in the hierarchical decomposition tree (part b of figure 1) (e.g., figure 1 shows five significant peaks P_i (i = 0 to 4) and three kernels K_i (i = 2, 3, 4)).
<figure><img src="image_2.png" /><figcaption>Figure 1: An example of hierarchical decomposition. The circled leaves (part b) correspond to significant peaks as obtained at the end of the iterative decomposition (part a), whereas leaves marked <S (part b) correspond to insignificant peaks (dotted lines in part a).</figcaption></figure>

The number of classes $N_c$ is taken equal to the number of kernels (the class corresponding to kernel $K_i$ is noted $C_i$). Therefore $N_c$ depends on the threshold $S$, i.e. on the precision the image colors are analyzed with.

### B - Decision step

The mass center $\mu(K_i)$ of each kernel $K_i$ can be calculated in the color 2D-space. Let us design by $\beta$ the color corresponding to the point of coordinates $(x_1,x_2)$ in the color 2D-space. Two cases happen : if $(x_1,x_2)$ belongs to $K_i$, color $\beta$ is attributed to class $C_i$ ; if not, let us design by $P_k$ the peak $(x_1,x_2)$ belongs to; color $\beta$ is attributed to class $C_i$ corresponding to kernel $K_i$, son of $P_k$, such that $d[\mu(K_i), (x_1,x_2)]$ is minimum, where $d[a,b]$ is the distance between a and b. Many choices of distances are possible (e.g. Euclidean distance, Mahalanobis distance, ...).

Finally, the classification results are shown by allocating to each class the color corresponding to its mass center (see figures 9 and 10).

## III - RESULTS

By way of example, the algorithm has been applied to the RGB image *peppers* (figure 2), presenting a 512x512 resolution. The distance $d$ used was the Mahalanobis distance.

<figure><img src="image_3.png" /><figcaption>Figure 2: Image peppers.</figcaption></figure>

The thresholds $S$ to be explored range from $S_{min}$ to $S_{max}$, where $S_{max}$ is the minimum threshold leading to one class only (no classification) and $S_{min}$ is the maximum threshold corresponding to the detection of the less populated class. Since class contains one pixel at least, we have in our case :

$$S_{min} \geq \left[ \frac{100}{512 \times 512} \right] = 0.00038\%$$

Table 1 gives the values of $S_{max}$, $S_{min}$ and $N_c^{max}$ (the maximum number of classes, obtained for $S = S_{min}$), when the image *peppers* is classified from its RG-, RB- and GB-histograms respectively.

<table><caption>Table 1: Threshold ranges and maximum number of classes for image *peppers* classified from its RG-, RB- and GB-histograms.</caption><thead><tr><th></th><th>S<sub>max</sub> (%)</th><th>S<sub>min</sub> (%)</th><th>N<sub>c</sub><sup>max</sup></th></tr></thead><tbody><tr><td>RG-histogram</td><td>23</td><td>0.00038</td><td>28355</td></tr><tr><td>RB-histogram</td><td>23</td><td>0.00038</td><td>22942</td></tr><tr><td>GB-histogram</td><td>13</td><td>0.00038</td><td>17528</td></tr></tbody></table>

If all the allowed colors in the RG (or RB, or GB) space were present, the maximum number of classes would be $256^2 = 65536$. It is never the case in practice
[7], leading to much lower values of $N_c^{max}$ (last column of table 1).

The variation of the number of classes $N_c$ as a function of the threshold $S$ is presented on figures 3 to 5 (for thresholds such that $N_c$ is lower than 100).

<figure><img src="image_4.png" /><figcaption>Figure 3: Number of classes as a function of $S$ (RG-histogram).</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 4: Number of classes as a function of $S$ (RB-histogram).</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 5: Number of classes as a function of $S$ (GB-histogram).</figcaption></figure>

Whatever the 2D-space used (RG, RB or GB), $N_c$ increases when $S$ decreases. Obtaining a given number of classes is insensitive to $S$ on a range $\Delta S$ which tends to decrease as $S$ decreases. For example, one obtains two classes for $S$ ranging from 13% to 23% (classification by RG-histogram, see figure 3), or for $S$ ranging from 9% to 23% (classification by RB-histogram, see figure 4).

<figure><img src="image_7.png" /><figcaption>Figure 6: RG-histogram (image peppers).</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 7: RB-histogram (image peppers).</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 8: GB-histogram (image peppers).</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>(a) 2 classes, S = 16%</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(b) 3 classes, S = 10%</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(c) 4 classes, S = 4%</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(d) 10 classes, S = 1%</figcaption></figure>

<caption>Figure 9: Classification from the RG-histogram (image peppers, B-component forced to zero).</caption>

The starting image (figure 2) provides the 2D-histograms shown on figures 6 to 8. The results of the classification obtained from the RG-histogram are shown on figures 9a to 9d, for thresholds leading respectively to 2, 3, 4 and 10 classes (since the classification is operated from the RG-histogram, the component B has been forced to zero on figures 9a to 9d).

Operating with the RB-histogram provides similar results in terms of class numbers, as can be seen by comparing the curves N_c(S) on figures 3 and 4. This follows from the fact that the RG-histogram (figure 6) and the RB-histogram (figure 7) are similar for the image *peppers*. Moreover, in the case where two classes are detected, the classification is practically the same, whatever the 2D-space used (RG or RB). This can be seen by comparing figure 9a (two classes in

RG-space) and figure 10 (two classes in RB-space, G component forced to zero). The pixels corresponding to unidentical classes on figures 9a and 10 are represented by black points on figure 11. This corresponds to a classification difference as weak as 3.3% of the total number of pixels.

Working in GB-space provides quite different results (figures 5), due to the particular shape of the GB-histogram (see figure 8).

IV - CONCLUSION

The unsupervised classification algorithm presented here is based on a hierarchical decomposition of color 2D-histograms. It allows to obtain different class numbers N_c by adjustment of one parameter (threshold S) in the learning step (the lower is S, the greater is
$N_c$). The algorithm makes use of a distance term in the decision step. It would be interesting to know the influence of the distance nature (Euclidean distance, Mahalanobis distance, etc.) on the classification. This work is in progress, and will be reported in a forthcoming communication.

<figure><img src="image_14.png" /><figcaption>Figure 10: Two classes obtained in the RB-space ($S = 16\%$, G component forced to zero).</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Figure 11: Image of pixels (black points) attributed to different classes on figures 9a (RG-space) and 10 (RB-space).</figcaption></figure>

REFERENCES

[1] R. Ohlander, K. Price, D.R. Reddy. *Picture segmentation using a recursive region splitting method*. Computer Graphics and Image Processing, vol. 8, p. 313-333, 1978.

[2] Y. Ohta, T. Kanade, T. Sakai. *Color information for region segmentation*. Computer Graphics and

Image Processing, vol. 13, p. 222-241, 1980.

[3] S. Tominaga. *A Color Classification Method for Color Images Using a Uniform Color Space*. Proceedings of the International Conference on Pattern Recognition, vol. 1, p. 803-807, 1990.

[4] Y.W. Lim, S.U. Lee S.U. *On the color image segmentation algorithm based on the thresholding and the fuzzy c-means techniques*. Pattern Recognition, vol. 23, n° 9, p. 935-952, 1990.

[5] R. Schettini. *A segmentation algorithm for color images*. Pattern Recognition Letters, vol. 14, p. 449-506, 1993.

[6] T. Uchiyama, M. Arbib. *Color image segmentation using competitive learning*. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, n°12, p. 1197-1206, 1994.

[7] A. Clément, B. Vigouroux. *Un histogramme compact pour l'analyse d'images multi-composantes*. Actes du 18e Colloque GRETSI'01 sur le Traitement du Signal et des Images, Toulouse, France, tome 1, p. 305-307, 2001.

[8] G. Xuan, P. Fisher P. *Maximum likelihood clustering method based on color features*. Proceedings of the First International Conference on Color in Graphics and Image Processing, Saint-Etienne, France, p. 191-194, 2000.

[9] P. Schmid. *Segmentation of Digitized Dermatoscopic Images by Two-Dimensional Color Clustering*. IEEE Transactions on Medical Imaging, vol. 18, n°2, p. 164-171, 1999.

[10] F. Kurugollu, B. Sankur, A.E. Harmanci. *Color image segmentation using 2-dimensional histogram multithresholding and fusion*. Proceedings of the First International Conference on Color in Graphics and Image Processing, Saint-Etienne, France, p. 152-157, 2000.