Image Anal Stereol 2004;23:23-31 Original Research Paper AUTOMATIC MULTILEVEL IMAGE SEGMENTATION BASED ON FUZZY REASONING Liang Tang1, Wei-Xin Xie2 and Jian-Jun Huang2 1School of Electronical Engineering, Xidian University, Xi’an, 710071, CHINA; 2School of Information Engineering, ShenZhen University ShenZhen, 518060, CHINA e-mails: tang_liangcn@hotmail.com, huangjin@szu.edu.cn (Accepted December 24, 2003) ABSTRACT An automatic multilevel image segmentation method based on sup-star fuzzy reasoning (SSFR) is presented. Using the well-known sup-star fuzzy reasoning technique, the proposed algorithm combines the global statistical information implied in the histogram with the local information represented by the fuzzy sets of gray-levels, and aggregates all the gray-levels into several classes characterized by the local maximum values of the histogram. The presented method has the merits of determining the number of the segmentation classes automatically, and avoiding to calculating thresholds of segmentation. Emulating and real image segmentation experiments demonstrate that the SSFR is effective. Keywords: automatic multilevel image segmentation, histogram, sup-star fuzzy reasoning. INTRODUCTION Image segmentation is one of the oldest and most difficult problems in the field of image processing or analysis, which consists of subdividing an image into its nonoverlapping constituent parts and extracting these parts of interest (objects). A great variety of segmentation algorithms have been developed in the last few decades (Zhang, 2001). One of the most frequently used methods in image segmentation is thresholding technique based on histogram because of its simplicity and efficiency (Glasbey, 1993). The presented methods in this field, such as P-tile method, Ostu method, Maximum Entropy Criterion (MEC), and Maximum Correlation Criterion (MCC) etc., focus mostly on one-dimensional (1-D) histogram and identify the different homogeneous regions of an image by gray-level thresholding. But, the number of classes that the gray-levels should be classified into is difficult to decide and usually is given by supervision (Chang and Wang, 1997; Pei and Xie, 1999). Although Yen et al. (1995) proposed a criterion for multilevel thresholding, named as Automatic Thresholding Criterion (ATC), to overcome this problem, there still remains a problem of how to select the weighting parameter used in ATC. On the other hand, information included in 1-D histogram is imperfect, as we can easily construct two images consisting of different objects and background with the same histogram. Especially, when image is polluted by noise, thresholding techniques based on 1-D histogram would give rise to many meaningless small patches. So, considering the spatial information in images, researchers have followed some two dimensional (2-D) histogram-based segmentation methods (Brink, 1992; Chen et al., 1994). Pixels having the same intensity but different spatial features can be distinguished in the second dimension (e.g., local average gray level) of the 2-D histogram, which enhances the capability of segmentation. However, besides increasing computational complexity, 2-D threshold also makes a problem of how the classifying function (line of demarcation) is defined in the 2-D plane. In this paper, considering the fuzziness suffered naturally by image processing, we advocate for a new sup-star fuzzy reasoning method (SSFR) based segmentation algorithm, which performs multilevel image segmentation with classification number determined automatically and does not calculate any threshold. Emulating and real image segmentation experiments will demonstrate its effectiveness. The rest of this paper is organized as follows. First, we introduce the philosophy of our method in Section 2. Next, the procedure of the SSFR automatic multilevel image segmentation method is described in Section 3. Section 4 presents some experimental results and discussions. Section 5 gives the conclusion. 23 Tang L et al: Fuzzy reasoning multilevel image segmentation AUTOMATIC MULTILEVEL IMAGE SEGMENTATION USING SSFR It is generally believed that image processing bears some fuzziness in nature due to following factors (Cheng et al, 1997): (a) information loss while mapping 3-D objects into 2-D images, (b) ambiguity and vagueness in some definitions (such as edges, boundaries, regions, textures, etc.), (c) ambiguity and vagueness in interpreting low-level image processing results. Therefore, the fuzzy set theory has been successfully applied to many image processing areas, so did in image segmentation (Pei and Xie, 1999; Cheng et al, 2000; Bonnet et al, 2002). Ideally, each class in an image should take on an approximately identical gray-level, and its histogram should have several narrow and independent peaks. But in real world, many reasons make gray-levels of each class diffusing to some extent, and peaks in their histogram spread. However, in the opinion of the statistic theory, gray- levels of one and the same class would establish a local maximum in the histogram. In other words, it is likely that a local maximum (peak) in histogram corresponds to a class and represents the original gray-level of this class, and other gray-levels in each class are scattering around the local maximum. So, most of the histogram-based thresholding technique applied themselves to search peaks and calculate threshold value corresponding to valley between two adjacent peaks. In this paper, because of the reasons mentioned in the previous paragraph, we do this work in the fuzzy mode. In the sight of fuzzy theory, it can be seen in some sense that each value in normalized histogram expresses the fuzzy degree of a gray-level corresponding to a class. Peaks have bigger fuzzy degrees than their surrounding gray-levels. It is a kind of global information. As for each unique gray-level, it may belong to the class characterized by itself, or may belong to the class characterized by an adjacent local maximum. This possibility has a typical local ambiguity. If the global information implying in histogram and the local possibility are incorporated, these ambiguities would be clarified and the segmentation would be achieved. Suppose there is a gray-level (or gray-level pair in 2-D case, the same below) G in an image, whose local possibility of class attribute is represented by a fuzzy set G . The argument domain of G is the range of gray-levels in image, and its core element (with grade of membership be 1) is G itself (this means that, in local sense, G belongs to the class characterized by itself with biggest possibility). The grade of membership jiq of each remaining element is inversely proportional to distance from it to the core element. Accumulating all the gray-level fuzzy sets of pixels in the image, we get a fuzzy histogram H (1-D or 2-D). The grade of membership fig expresses the global probability of a gray-level corresponding to a class, with local ambiguities taken into account. To reason out which class each gray-level is belonging to, the global information (grade of membership /ig) and the local information (grade of membership //g) should be taken into account synthetically. To do so, we set up a fuzzy reasoning rule, with its formation described as below: If gray-level G belongs to class C, locally, and class C j exists globally, then G belongs to Q globally. j = 1, • • •, number of elements in G , where a class is represented by its center gray-level Cj. In this rule, the confidence level of the first antecedent is denoted by membership function /Hq(Cj), and the second is denoted by //#(C,-). According to the fuzzy reasoning mechanism, the confidence level of G globally belonging to a class Q is given by: fiG\c ,j=fi~(C ,)*fi~(C ¦), j = 1, — , number of elements in G (1) where star (*) denotes t-norm operator which can be selected as minimum or product. The global and local information are combined by this operator. With local ambiguity, G may belong to many classes, so that many sentences are generated in the form of the reasoning rule, while different sentence is accompanied with different confidence level. In order to make sure which class G is indeed belonging to, the sup-star fuzzy reasoning algorithm is adopted. Namely, the class Cj, which makes Supremum value of fiG in Eq. 1, is the class that G belongs to with the most possibility. We can write it as: C G argsupui-fC ¦ C j G )*jU~(C, ;) (2) where the sup operator ensures that G is assigned to the class characterized by the local maximum. By the sup-star fuzzy reasoning, we reason out which class a gray-level G is belonging to. Thereby, spread gray-levels of a class are aggregated and merged into the class characterized by the local maximum gray-level, which is the most representative gray-level of this class. Consequently, multilevel 24 Image Anal Stereol 2004;23:23-31 image segmentation is achieved. In this process, the number of classes in image is not predefined, and no thresholds are computed. At the same time, segmented image is displayed by the most representative gray-levels of classes. Thus, the bits needed to store the image are reduced, as well as the intensity information of original image can be preserved preferably. DESCRIPTION OF THE PROCEDURE 1-D histogram is the most fundamental statistical information of gray image. It is also one of the simplest image information with the result that 1-D histogram based techniques are straightforward and effective. The SSFR multilevel segmentation algorithm based on 1-D histogram consists of four steps as below: Based on its gray-level G,-, all pixels /,- of image / are fuzzified as fuzzy sets Gi=ljHQ(gj)lgj g j e [0,255] where J denotes the union of elements. //£ renders the local possibility of class contribution of Gt with ftö(Gi) = 1 and the membership of remaining elements inversely proportional to \gj -Gj\. In this paper, the Gaussian membership function is adopted, so we have: ju~ (g) = exp j {gj-Gjf2v2] (3) where a is the deviation of Gaussian function. step 1 Supposing the number of pixels in / is M the fuzzy 1-D histogram, H = J. fig (gj )/gj, g j e [ 0,255 ] , can be calculated as: (g ) j M ~ 7 (g ) M i=1 Gj (4) E S.i"^ (g j ) 255 M 7=07=1 Gt M h (g j) renders the global possibility of g} corresponding to a class. step 2 Compute class CGi. which G,- is belonging to according to Eq. 2, with * selected as minimum operator: C G =argsup\min 1 C . C e [0,255] fi~ (C),ju~(C) ,¦ ~ V (5) Then, replace all pixels taking gray-level G,- in original image with class gray-level CGj. Consequently, we can get a new histogram H' described as Eq. 6, where s() denotes the Dirac function: H'(k) = M ( 255 M f (6) ke [0,255] step 3 After operating as mentioned above, the most gray-levels of original image have been merged into some classes characterized by several distinct and isolated peaks. But, there may be few pixels, whose gray-levels are still scattering around peaks. Because of that the noise occurs and gray-levels of some classes spread widely. In order to overcome this problem, step 1~3 can be repeated till all the gray-levels are merged into their classes and the histogram does not change anymore. Lastly, the original image is segmented. The suggested procedure is illustrated in Fig. 1, through a noised emulational image (Gaussian noise with variance of 65.535) with four classes. Figs. 1a-c display the original gray-level image, its gray-level histogram and the fuzzy histogram with a = 6 empirically. Fig. 1d gives the segmentation result by the proposed method, and Fig. 1e is the histogram after 1-D SSFR segmentation. It can be seen that, through the SSFR procedure, gray-levels spread in the histogram of original image are aggregated into four distinct and isolated peaks, corresponding to four classes. For comparison, Figs. 1f-g display the segmented images resulted in the ATC (Yen et al., 1995), which can also determine the classification number automatically, and its improved version (Sezgin and Tasaltìn, 2000). The result of 1-D SSFR are 48 misclassified pixels while ATC and improved ATC gave 1440 and 1030 misclassified pixels. 25 Tang L et al: Fuzzy reasoning multilevel image segmentation a) slightly noised test image b) histogram c) fuzzy histogram d) segmentation by SSFR e) histogram of Fig. 1d f) segmentation by ATC g) segmentation by improved ATC h) segmentation by 2-D SSFR Fig 1 Illustration of the SSFR segmentation procedure through a slightly noised emulational test image (Gaussian noise with variance of 65 535) of four classes. Parameter a = 6 for SSFR. As mentioned previously 2-D histogram catches more image information than 1-D histogram so that it can give rise to more favorable segmentation result. The SSFR method can be extended to 2-D case straightforwardly A simple and typical 2-D histogram is constructed by gray-level of pixel and its local average gray-level. These two kinds of gray-levels compose a gray-level pair Pi for each pixel. By analogy with 1-D case (e.g. Eq. 3), Pi is fuzzified as a 2-D fuzzy set Pi = j , k juP ~ i (g j,fk)(g j,fk), LI P (g j ,f k ) exp -\gj-gi)2 2a exp -ifk-fi) 2 /, 2 2cr (7) g j f^[0,255], whose Sequentially the fuzzy 2-D histogram is computed, and SSFR is performed till the 2-D histogram is merged into several distinct and isolated peaks and does not change anymore Lastly the original image is displayed by several gray-levels locating on the 2-D peaks and the segmented image is gained It is noticeable that in this process no 2-D threshold . is calculated so that the problem of definition of 2-D classify function is avoided. Using 2-D SSFR to segment the test image Fig. 1a (cr = 6), the result 26 Image Anal Stereol 2004;23:23-31 is shown in Fig. 1h, with only 1 pixel misclassified. To exhibit the advantages of 2-D SSFR further, an experiment on a severely noised (Gaussian noise with variance of 655.35) test image (Fig. 2a) is displayed in Fig. 2. It can be seen from Fig. 2b that the four classes of the image are totally mixed up in its 1-D histogram, that is, it is almost impossible to segment this image based only on its 1-D histogram. However, four peaks are visible in its 2-D histogram (Fig. 2c), which means that segmentation based on 2-D histogram would be promising. Figs. 2d-e display the segmented image and its 2-D histogram resulted in 2D SSFR. The four classes have been partitioned favorably even in this difficult condition. In this test, 429 pixels have been misclassified. EXPERIMENTAL RESULTS AND DISCUSSION To demonstrate the effectiveness of the proposed SSFR method for automatic multilevel segmentation, some experimental results are given in this section (s= 3 for all the experiments in this section). First, to examine the exactness of SSFR segmentation algorithm, an aerial image of a ground track field is segmented by 1-D SSFR. Figs. 3a-b display the original image and its histogram. The field is composed of four regions (grass court, running path, bleachers, and awning), and four peaks are generated in its histogram. Fig. 3c shows the segmented result, which is favorable with the four regions partitioned distinctly. In Fig. 3d, fuzzy histogram of the original image and histogram of the segmented image are depicted together. It can be seen that the proposed method aggregates all the gray-levels into classes characterized accurately by four local maxima, so that the segmented image is displayed by the most representative gray-levels of the classes. Therefore, the intensity information of the original image is preserved preferably. a) severely noised test image b) 1-D histogram c) 2-D histogram d) segmentation by 2-D SSFR e) 2-D histogram of Fig. 2d Fig. 2. Severely noised test image (Gaussian noise with variance of 655.35) and its segmentation by 2-D SSFR. Parameter s= 6. 27 Tang L et al: Fuzzy reasoning multilevel image segmentation Fig. 4 indicates a segmentation experiment on an infrared ship image. The original infrared ship image and its histogram are shown in Figs. 4a-b. Figs. 4c-d display the segmented image using SSFR and its histogram. For comparison, the results of the ATC and the improved ATC are shown simultaneously, in Figs. 4e-f, respectively. The uniformity measure (Levine and Nazif, 1985) is used to make the quantitative evaluation of the methods and to test the performance. It indicates the degree of spread of the segmented regions from the mean. The uniformity measure of a region is inversely proportional to the variance of the values evaluated at those pixels belonging to that region. A well-segmented image will have uniformity measure close to 1. Class numbers C and uniformity measures UM of this experiment are listed in Table 1. Obviously, this image should be partitioned into three regions: ship, sky, and ocean. As we can see, the results of 1-D SSFR are the best either in visual impression or in quantitative evaluation, ATC takes is second best, while the improved ATC computes a wrong class number. a) ground track field b) 1-D histogram c) segmentation by 1-D SSFR d) fuzzy histogram of Fig. 3a and histogram of Fig. 3c Fig. 3. Original “ground track field” image and automatic multilevel segmentation results of 1-D SSFR. In Fig. 3d the curve denotes the fuzzy histogram of the original image and the four vertical lines denote the histogram of segmented image resulted in 1-D SSFR. 28 Image Anal Stereol 2004;23:23-31 a) Infrared ship b) 1-D histogram c) segmentation by 1-D SSFR d) histogram of Fig. 4c e) segmentation by ATC f) segmentation by improved ATC Fig. 4. “Infrared ship” image and automatic multilevel segmentation results of different methods. Table 1. Number of classes of segmented images (C) and uniformity measure (UM). 1-D SSFR ATC Improved ATC 2-D SSFR Fig. 4 C UM 33 4 0.9429 0.8629 0.8621 Fig. 5 C UM 33 33 0.9230 0.7163 0.7163 0.9281 In order to examine the effectiveness of 2-D SSFR, an artificially noised (Gaussian noise with variance of 65.535) infrared ship image is used. Figs. 5a-b display the noised image and its histogram. Figs. 5c-f show the segmented image resulted in 1-D SSFR, ATC, improved ATC, and 2-D the SSFR, respectively. Class numbers and uniformity measures of this experiment are also listed in Table 1. It can be observed that all the methods compute the right class number automatically, but the results of ATC and improved ATC have many misclassified patches, while 1-D SSFR achieves a better segmentation. However, the image resulted in 2-D SSFR takes the best segmentation with few misclassified small patches and the optimal uniformity measure. Namely, this consideration of spatial information in the image enhances the antinoise capability of the 2-D histogram based algorithm. 29 Tang L et al: Fuzzy reasoning multilevel image segmentation a) Noised infrared ship b) 1-D histogram c) segmentation by 1-D SSFR d) segmentation by ATC e) segmentation by improved ATC f) segmentation by 2-D SSFR Fig. 5. Noised “Infrared ship” image (Gaussian noise with variance of 65.535) and automatic multilevel segmentation results of different methods. CONCLUSION An automatic multilevel image segmentation algorithm is presented. The main point of this method is that, in terms of sup-star fuzzy reasoning, it combines the global statistical information implied in the 1-D or 2-D histogram with the local information represented by the fuzzy sets of gray-levels, and aggregates scattering gray-levels into the representative gray-levels of classes. 1-D and 2-D based SSFR segmentation methods determine the appropriate number of classes automatically, and do not calculate any threshold or classifying function. The experimental results prove that the presented methods have improved performance in contrast with respect to other approaches. ACKNOWLEDGEMENTS This research is supported by the National Natural Science Foundation of China (No. 60172066). We are grateful to the reviewers for their helpful comments and valuable suggestions to improve the presentation of this paper. "The preliminary form of this paper was originally presented at the XIth International Congress for Stereology-Beijing Conference, Beijing, China, 4-8 November 2003." REFERENCES Bonnet N, Cutrona J, Herbin M (2002). A “No-Threshold” Histogram-Based Image Segmentation Method. Pattern Recogn 35:2319-22. Brink AD (1992). Thresholding of Digital Images Using Two-Dimentional Entropics. Pattern Recogn 25: 803-8. Chang CC, Wang LL (1997). A Fast Multilevel Thresholding Method Based on Lowpass and Highpass Filtering. Pattern Recogn Lett 18:1469-78. Chen WT et al. (1994). A Fast Two-Dimentional Entropic Thresholding Algorithm. Pattern Recogn 27:885-93. Cheng HD, Chen JR, Li JG (1997). Threshold Selection Based on Fuzzy C-Patition Entropy Approach. Pattern Recogn 31(7):857-70. Cheng HD, Chen YH, Jiang XH (2000). Thresholding Using Two-Dimentional Histogram and Fuzzy Entropy Principle. IEEE Trans. On Image Processing 9(4):732-5. 30 Image Anal Stereol 2004;23:23-31 Glasbey CA (1993). An Analysis of Histogram-Based Thresholding Algorithms. CVGIP 55(6):532-7. Levine MD, Nazif AM (1985). Dynamic measurement of computer generated image segmentation. IEEE Trans. On Pattern Analysis and Machine Intelligence 7(2): 155-64. Pei JH, Xie WX (1999). Adaptive Multi Thresholds Images Segmentation Based on Fuzzy Restrained Histogram FCM Clustering (in Chinese). Acta Electronica Sinica 27(10):38-42. Sezgin M, Tasaltìn R (2000). A New Dichotomization Technique to Multilevel Thresholding Devoted to Inspection Applications. Pattern Recogn Lett 21:151-61. Yen JC, Chang FJ, Chang S (1995). A New Criterion for Automatic Multilevel Thresholding. IEEE Trans. On Image Processing 4(3):370-8. Zhang YJ (2001). Image Segmentation (in Chinese). Beijing, China: Publishing House of Science.