Home | About | Journals | Submit | Contact Us | Français |

**|**Adv Appl Bioinforma Chem**|**v.3; 2010**|**PMC3170003

Formats

Article sections

- Abstract
- Introduction
- Theoretic aspects
- Entropy
- Algorithms
- Results and discussion
- Discussion of experimental results
- Verification of results
- Conclusion
- References

Authors

Related links

Adv Appl Bioinforma Chem. 2010; 3: 67–73.

Published online 2010 September 13. doi: 10.2147/AABC.S11918

PMCID: PMC3170003

Correspondence: R Rodríguez, Digital Signal Processing Group, Institute of Cybernetics, Mathematics, and Physics, Calle 15 No. 551 entre, B y C, CP 10 400, Havana, Cuba, Tel +537 832 4085, Fax +537 833 3373, Email uc.fni.fmci@mrr

Copyright © 2010 Rodríguez and Hernández, publisher and licensee Dove Medical Press Ltd.

This is an Open Access article which permits unrestricted noncommercial use, provided the original work is properly cited.

Many segmentation techniques have been published, and some of them have been widely used in different application problems. Most of these segmentation techniques have been motivated by specific application purposes. Unsupervised methods, which do not assume any prior scene knowledge can be learned to help the segmentation process, and are obviously more challenging than the supervised ones. In this paper, we present an unsupervised strategy for biomedical image segmentation using an algorithm based on recursively applying mean shift filtering, where entropy is used as a stopping criterion. This strategy is proven with many real images, and a comparison is carried out with manual segmentation. With the proposed strategy, errors less than 20% for false positives and 0% for false negatives are obtained.

Image segmentation is a fundamental process in many image, video, and computer vision applications. It is often used to partition an image into separate clusters or regions, which ideally correspond to different real-world objects. The definition of suitable similarity and homogeneity measures is a fundamental task in many important applications, ranging from geology and remote sensing to biology and medicine in the determination of the homogeneity of an organ. Image segmentation is a critical step towards visual pattern recognition and image understanding.

For years, image segmentation has been used in a supervised and an unsupervised way.1–7 However, unsupervised methods, which do not assume any prior scene knowledge in order to help the segmentation process, are obviously more challenging than supervised methods. In this paper, an unsupervised approach will be proposed which does not depend strongly on previously acquired information. The aim of such an unsupervised strategy is to find an appropriate segmentation process in difficult image scenes, just as is done for biomedical images.

It is known that biomedical images are often corrupted by noise and sampling artifacts, which can cause considerable difficulties when applying rigid methods. However, segmented biomedical images are now used routinely in a multitude of different applications, including diagnosis, treatment planning, localization of pathology, study of anatomic structure, and computer-integrated surgery. Thus, it is important to obtain robust segmentation methods for these types of images.

Nevertheless, in spite of the most complex algorithms developed until the present, segmentation continues to be very dependent on the application used, and there is no single method that can solve the multitude of present problems.

An example of the unsupervised segmentation method is mean shift. In this paper, we present an unsupervised strategy for biomedical image segmentation using an algorithm based on recursively applying mean shift filtering, where entropy is used as a stopping criterion.

Mean shift is a robust technique which has been used in many computer vision tasks. This is a nonparametric procedure and is an extremely versatile tool for feature analysis and can provide reliable solutions in many applications. 8,9 Mean shift was proposed in 1975 by Fukunaga and Hostetler,10 and largely forgotten until Cheng’s paper11 rekindled interest in it.

The term entropy is not a new concept in the field of information theory. Entropy has been used in image restoration, edge detection, and recently, as an objective evaluation method for image segmentation.12

The results obtained with the proposed algorithm are compared with manually segmented images. Our interest and main motivation for this research was to determine the robustness of our algorithm for biomedical images, while segmenting some types of lesions in an unsupervised way. In this work, lesions are the important information to be extracted from these images.

The basic concept of the mean shift algorithm is as follows. Let *x** _{i}* be an arbitrary set of

$$f(x)=\frac{1}{{nh}^{d}}\sum _{i=1}^{n}K\left(\frac{x-{x}_{i}}{h}\right)$$

(1)

Here, the Epanechnikov function is chosen as the kernel function. The Epanechnikov function is defined as:

$${K}_{E}\hspace{0.17em}(x)=\{\begin{array}{ll}1/{2}_{{c}_{d}^{-1}}(d+2)\hspace{0.17em}(1-{\left|\right|x\left|\right|}^{2})\hfill & if\left|\right|x\left|\right|<1\hfill \\ 0\hfill & otherwise\hfill \end{array}$$

(2)

The differential of *f*(*x*) is formulated as:

$$\widehat{\nabla}f(x)=\nabla \widehat{f}(x)=\frac{1}{{nh}^{d}}\sum _{i=1}^{n}\nabla K\left(\frac{x-{x}_{i}}{h}\right)$$

(3)

Therefore:

$$\begin{array}{l}\widehat{\nabla}{f}_{E}(x)=\frac{1}{n({h}^{d}{c}_{d})}\xb7\frac{d+2}{{h}^{2}}\sum _{{x}_{i}\in {S}_{h}(x)}({x}_{i}-x)\\ =\frac{{n}_{x}}{n({h}^{d}{c}_{d})}\xb7\frac{d+2}{{h}^{2}}\left(\frac{1}{{n}_{x}}\sum _{{x}_{i}\in {S}_{h}(x)}({x}_{i}-x)\right)\end{array}$$

(4)

where the region *S** _{h}*(

$$\begin{array}{l}{M}_{h,U}(x)=\frac{1}{{n}_{x}}\sum _{{x}_{i}\in {S}_{h}(x)}({x}_{i}-x)\\ =\frac{1}{{n}_{x}}\sum _{{x}_{i}\in {S}_{h}(x)}{x}_{i}-x\end{array}$$

(5)

The quantity *n** _{x}*/

$$\widehat{\nabla}{f}_{E}(x)={\widehat{f}}_{U}(x)\xb7\frac{d+2}{{h}^{2}}{M}_{h,U}(x)$$

(6)

which yields:

$${M}_{h,U}(x)=\frac{{h}^{2}}{d+2}\xb7\frac{\widehat{\nabla}\hspace{0.17em}{f}_{E}(x)}{{\widehat{f}}_{U}(x)}$$

(7)

Equation (7) shows that an estimate of the normalized gradient can be obtained by computing the sample mean shift in a uniform kernel centered on *x.* In addition, the mean shift has the direction of the gradient of the density estimate at *x* when this estimate is obtained with the Epanechnikov kernel. Since the mean shift vector always points towards the direction of the maximum increase in the density, it can define a path leading to a local density maximum, ie, to a mode of the density.

Other works have proven that, in the case of unimodal histograms, the mean shift vector points towards the mode.8–10 Another very interesting recent result, in the case of unimodal histogram, is also using the fractal dimension.13

In work by Comaniciu and Meer9 it was proven that the mean shift procedure, obtained by successively computing the mean shift vector *M** _{h}* (

Therefore, if the individual mean shift procedure is guaranteed to converge, a recursive procedure of the mean shift also converges. In other words, if one considers the recursive procedure as the sum of many procedures of the mean shift, and each individual procedure converges, the recursive procedure then converges as well. This claim has already been proven by Grenier et al.14 The open question is when to stop the recursive procedure. The answer lies in the use of entropy, as shown below.

From the point of view of digital image processing, the entropy of an image is defined as:

$$E(x)=-\sum _{x=0}^{{2}^{B}-1}p(x){log}_{2}p(x)$$

(8)

where *B* is the total quantity of bits of the digitized image and by agreement, *log** _{2}*(0) = 0;

The choice of entropy as a measure of goodness deserves several observations. Entropy reduces the randomness in corrupted probability density functions and tries to counteract noise. Then, following this analysis, because the segmented image is a simplified version of the original image, entropy of the segmented image should be smaller. Recently, it was found empirically that the entropy of the noise diminishes faster than that of the signal.12 Therefore, an effective threshold at which to stop would be when the relative rate of change of entropy, from one iteration to the next, falls below a given threshold. This is the essential part of this work.

In this section, two algorithms are given, one related to the filtering of the signal and the other related to the segmentation step.

Let *X** _{i}* and

- Initialize
*j*= 1 and*y*_{i}_{, 1}=*p*._{i} - Compute through the mean shift (see expression (5),
*y*), the mode where the pixel converges, ie, calculation of the mean shift is carried out until convergence,_{i, j+1}*y*=*y*._{i,c} - Store at
*Z*the component of the gray level of calculated value,_{i}*Z*=(_{i}*x*^{s},_{i}*y*^{r}), where_{i,c}*x*^{s}is the spatial component and_{i}*y*^{r}is the range component._{i,c}

Let *ent1* be the initial value of entropy of the first iteration. Let *ent2* be the second value of entropy after the first iteration. Let *errabs* be the absolute value of the difference of entropy between the first one and the second iteration. Let *edsEnt* be the threshold to stop the iterations, ie, this is the threshold to stop when the relative rate of change of entropy, from one iteration to the next, falls below this threshold. Then, the segmentation algorithm comprises the following steps:

- Initialize
*ent2*= 1*, errabs*= 1*, edsEnt*= 0.001. - While
*errabs*>*edsEnt*, then: - Filter image according to the steps of the previous algorithm, and store the filtered image in
*Z*^{[k]} - Calculate entropy from the filtered image according to expression (8), and store in
*ent1*. - Calculate the absolute difference with the entropy value obtained in the previous step;
*errabs*=*/ent1*–*ent2/.* - Update the value of the parameter;
*ent2*=*ent1; Z*=^{[k +1]}*Z*.^{[k]}

It is possible to observe that, in this case, the unsupervised segmentation algorithm is a direct extension of the filtering algorithm, which finishes when entropy reaches stability.

Christoudias et al15 state that the recursive application of the mean shift property yields a simple mode detection procedure. The modes are the local maxima of the density. Therefore, with the new segmentation algorithm, by recursively applying mean shift, convergence is guaranteed. Indeed, the proposed algorithm is a straightforward extension of the filtering process. Comaniciu8 has proven that the mean shift procedure converges. In other words, one can consider the new segmentation algorithm as a concatenated application of individual mean shift-filtering operations. Therefore, if we consider the whole event as linear, the recursive algorithm converges. As one can observe, this algorithm does not need any previous condition to carry out the segmentation process, therefore it is an unsupervised method.

Manual segmentation generally gives the best and most reliable results when identifying structures for a particular clinical task. At present, due to the lack of ground truth, the quantitative evaluation of a segmentation technique is difficult to achieve. An alternative is to use manual- segmentation results as the ground truth.

In order to evaluate the performance of the methods, we calculate the percentage of false negatives (FN [lesions], which are not found by the algorithm) and the false positives (FP, [noise], which are classified as lesions). These are defined according to the following expressions:

$$FP=\frac{{f}_{p}}{{V}_{p}+{f}_{p}}\times 100\mathrm{\hspace{0.17em}\u200a\u200a}\mathrm{\hspace{0.17em}\u200a\u200a}\mathrm{\hspace{0.17em}\u200a\u200a}FN=\frac{{f}_{n}}{{V}_{p}+{f}_{p}}\times 100$$

(9)

where *V** _{p}* is the actual number quantity of lesions identified by the physician,

In order to show more clarity of the lesions isolated and shown here, some details of the original images are given. Studied images were of arteries containing atherosclerotic lesions obtained from different parts of the human body. These arteries were contrasted with a special tint in order to accentuate the different lesions in the arteries. The arteries were digitalized directly from the working desk via the MADIP system with a resolution of 512 × 512 × 8 bit/pixels.16 For more details on the characteristics of these images, see the paper by Rodríguez and Pacheco.17 Another lesion type isolated is caused by glaucoma, a group of diseases of the visual system that can lead to damage of the optic nerve and result in blindness.

Figure 1 shows a first unsupervised segmentation example. Although another segmentation method was already applied to other atherosclerotic lesions,17 here one can observe the obtained result when applying an unsupervised strategy. In Figure 1, one can note that lesion Type IV that appears in the original image was isolated (see arrows in Figure 1a). According to the criteria of physicians, this is a good result, because the algorithm is able to isolate the lesion without any previous condition. In addition, one can also see that the segmented image with the mean shift algorithm is totally free of noise. This is another important aspect when the mean shift filtering is used. In Figure 2, another example of the application of our unsupervised strategy on an atherosclerosis image is shown. According to the criteria of physicians, the obtained results were good, and in particular for lesion Type II. However, in lesion Type III, a small area was generated, due to preparation of the samples.

(**A**) Original image and (**B**) unsupervised segmentation using our algorithm. The arrows mark the isolated lesions.

(**A**) Original image and (**B**) segmentation using our unsupervised strategy. The arrows indicate isolated lesions. The split arrow indicates a zone which is not a lesion.

Other examples of real images are shown in Figures 3 and and4.4. Here one can see the results obtained by applying our unsupervised segmentation strategy. According to the criteria of physicians, one can see that the unsupervised method is able to isolate atherosclerotic lesions effectively. Again, the segmented images with the mean shift algorithm were very clean of noise, which is very important in a segmentation process. However, some FP were generated (see split arrows). In practice, it is very difficult to eliminate the problem of FP completely in real images. FP can arise in the segmentation process due to bad preparation of the samples or abrupt changes in illumination. Another example is shown in Figure 5. In this case, the main objective is to isolate the oval from the vascular net of the eye (see arrow). This is of great importance for the study of glaucoma. According to the criteria of physicians, the discrimination of this area is of great importance in order to identify the stage of the disease. In this example, the zone is isolated effectively.

(**A**) Original image. (**B**) Segmentation by using our unsupervised strategy. The arrows indicate the isolated lesions. Note the quality of segmentation of the Type lesion in **(B)**.

(**A**) Original image and (**B**) segmentation using our unsupervised strategy. The arrows indicate the isolated lesions. The split arrows indicate zones which are not lesions.

(**A**) Original image and (**B**) segmentation using our unsupervised strategy. The arrow indicates the isolated lesion.

It is important to point out that in all segmentation experiments, we use the same parameters *hs* and *hr* when applying the mean shift filtering (*hr* = 15, *hs* = 12). The value of *hs* is related to the spatial resolution of the analysis, while the value *hr* defines the range resolution. It is necessary to note that the spatial resolution *hs* has a different effect on the output image when compared with the gray level resolution (*hr,* spatial range). Only features with large spatial support are represented in the segmented image with our algorithm when *hs* is increased. On the other hand, only features with high contrast survive when *hr* is large. Therefore, the quality of segmentation is controlled by the spatial value *hs* and the range (gray level) *hr*, with the resolution parameters defining the radii of the windows in the respective domains.

Because the main purpose of this work was to analyze the performance of our unsupervised segmentation strategy, it is important to compare the results of our approach with those of manual segmentation. Results have been confirmed by qualitative and quantitative comparisons of results obtained by the visual observations of physicians, from which FP and FN were selected. For this reason, we did not do a comparative study with other methods. The numeric results are summarized in the Table 1. We carried out this comparison with all images (n = 40), but all images are not shown due to space considerations. Five images are summarized in the Table 1, in which it can be observed that the error for FN was 0%, ie, all regions belonging to the lesions were detected. This denotes correct performance of our unsupervised strategy. This behavior was the same for all segmented images. In Figures 2b and and4b,4b, the FP are shown with arrows as indicated, according to the criteria of physicians. We verify that the number of FP is less than 20%. In other words, in Figures 2b and and4b4b (see arrows) it can be observed that the unsupervised segmentation process was not completely correct. FP may arise due to abrupt variation of illumination or can be created by a problem in preparation of samples. In practice, these problems are very difficult to eliminate completely in real images. Therefore, the result from the unsupervised segmentation process was presented to physicians for manual segmentation. With a few mouse clicks on the final result, the FP are completely eliminated. This unsupervised strategy applied to this type of lesion is part of a global image analysis process, which will be improved in future research. According to the criteria of physicians, the global performance of this unsupervised strategy can be considered suitable for these applications.

In this work, we propose an unsupervised strategy in order to isolate lesions in biomedical images. We have devised an algorithm which correctly identifies atherosclerotic and glaucomatous lesions. This unsupervised algorithm did not produce spike noise. We showed via experimentation using real-image data that this unsupervised strategy is robust for the type of images considered here. This strategy was tested, according to the criteria of physicians, where the percentage of FN was 0% and for FP less than 20%. In future work, this unsupervised strategy will be applied to these images with a finer stopping threshold. The unsupervised algorithm can be applied to other types of images, and it can be extended to other tasks of biomedical image analysis where methods of segmentation are required.

**Disclosure**

The authors report no conflicts of interest in this work.

1. Kenong W, Gauthier D, Levine MD. Live cell image segmentation. IEEE Trans Biomed Engineering. 1995;42(1):1–11. [PubMed]

2. Sijbers J, Scheunders P, Verhoye M, van der Linden A, van Dyck D, Raman E. Watershed-based segmentation of 3D MR data for volume quatization. Magn Reson Imaging . 1997;15(6):679–688. [PubMed]

3. Chin-Hsing C, Lee J, Wang J, Mao CW. Color image segmentation for bladder cancer diagnosis. Mathl Comput Modeling. 1998;27(2):103–120.

4. Rodríguez R, Alarcón T, Wong R, Sanchez L. Color segmentation applied to study of the angiogenesis. Part I. J Intell Robot Sys. 2002;34(1):83–97.

5. Schmid P. Segmentation of digitized dermatoscopic images by two-dimensional color clustering. IEEE Trans Med Imaging. 1999;18(2):164–171. [PubMed]

6. Koss JE, Newman FD, Johnson TK, Kirch DL. Abdominal organ segmentation using texture transforms and a hopfield neural network. IEEE Trans Med Imaging. 1999;18(7):256–264. [PubMed]

7. Braiek EB, Cheriet M, Dore V. SKCS – A separable kernel family with compact support to improve visual segmentation of handwritten data. Electronic Lett Computer Vision Image Anal. 2005;5(1):14–29.

8. Comaniciu DI. PhD thesis. New Brunswick, Rutgers: The State University of New Jersey; 2000. Jan, Nonparametric robust method for computer vision.

9. Comaniciu D, Meer P. Mean shift: A robust approach toward feature space analysis. IEEE Trans Patt Anal Mach Intell. 2002;24(5):602–619.

10. Fukunaga K, Hostetler LD. The estimation of the gradient of a density function. IEEE Trans Info Theory. 1975;21:32–40.

11. Cheng Y. Mean shift, mode seeking, and clustering. IEEE Trans Patt Anal Mach Intell. 1995;17(8):790–729.

12. Zhang H, Fritts JE, Goldman SA. An entropy-based objective evaluation method for image segmentation. Yeung M, Lienhart M, Rainer W, et al., editors. Storage and Retrieval Methods and Applications for Multimedia. Proceedings of The SPIE. 2003;20045307:38–49.

13. Salvatelli A, Caropresi J, Delrieux C, Izaguirre MF, Caso V. Cellular outline segmentation using fractal estimators. J Comp Sci Technol. 2007;7(1):14–22.

14. Grenier T, Revol-Muller C, Davignon F, Gimenez G. Hybrid approach for multiparametric mean shift filtering. Image Processing; IEEE International Conference; Oct 8–11; Atlanta, Georgia. 2006.

15. Christoudias CM, Georgescu B, Meer P. Synergism in low level vision. Proceedings of 16th International Conference on Pattern Recognition; Quebec City, Canada. 2002 Aug; pp. 150–155.

16. Rodríguez R, Alarcón T, Sánchez L. MADIP: Morphometrical analysis by digital image processing. Proceedings of the IX Spanish Symposium on Pattern Recognition and Image Analysis; 2001. pp. 291–298.

17. Rodríguez R, Pacheco O. A strategy for atherosclerosis image segmentation by using robust markers. J Intell Robot Sys. 2007;50(2):121–140.

Articles from Advances and Applications in Bioinformatics and Chemistry : AABC are provided here courtesy of **Dove Press**

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |