A fuzzy approach to texture segmentation

A Fuzzy Approach to Texture Segmentation

Madasu Hanmandlu

Dept. of Electrical Engineering, I.I.T. Delhi, New Delhi-110016, India.

mhmandlu@ee.iitd.ernet.in

Vamsi Krishna Madasu

School of ITEE, University of Queensland,

QLD 4072, Australia.

madasu@itee.uq.edu.au

Shantaram Vasikarla

IT Department, American InterContinental University, Los Angeles, CA90066,USA

svasikarla@la.aiuniv.edu

Abstract: The texture segmentation techniques are diversified by the existence of several approaches. In this paper, we propose fuzzy features for the segmentation of texture image. For this purpose, a membership function is constructed to represent the effect of the neighboring pixels on the current pixel in a window. Using these membership function values, we find a feature by weighted average method for the current pixel. This is repeated for all pixels in the window treating each time one pixel as the current pixel. Using these fuzzy based features, we derive three descriptors such as maximum, entropy, and energy for each window. To segment the texture image, the modified mountain clustering that is unsupervised and Fuzzy C-means clustering have been used. The performance of the proposed features is compared with that of fractal features.

Keywords: Texture, fractal dimension, modified mountain clustering, potential, validity, segmentation.

1. Introduction

Image segmentation is the process of grouping homogeneous pixels into one region. The homogeneity of the image pixels can be characterized by the spatial arrangement of the gray levels. An image has inherent fuzziness in the gray levels over spatial regions. We use fuzzy logic framework to derive texture features for segmenting the image such that each segment contains a similar texture distinct from its neighbors.

Texture features can be based on the three approaches:

(1) Statistical approach (2) Structural approach and (3) Spectral approach. In statistical approach, moments of different order in a localized window represent smooth, coarse, grainy, etc. textures [1], co-occurrence statistics can also be used [2], [3]. In structural approach, spatial structure descriptors are used to identify geometric primitives and their arrangement in an image. Some techniques using this approach are: local interaction models like auto regressive moving average model [4], the Gauss - Markov random field model [5] and the fractal model [6]. Mandelbrot and Van Ness [14] and

Voss [15] have pointed out that different textures may have the same fractal dimension (FD). This may be due to combined differences in coarseness and directionality (dominant orientation and degree of anisotropy). The spectral approach is the transform domain approach that is used to detect global periodicity in an image by finding high energy, narrow peaks in the spectrum.

This approach is not popular due to high computational cost. However, a combination of spectral and spatial approaches such as Gabor filters [7], and wavelet transform [8] are becoming popular.

In this paper, we present a fuzzy approach for the characterization of texture. This approach is spurred by the fact that a Texel has an ambiguity in the spatial arrangement of gray levels of pixels. Moreover, all the pixels do not have the same property and there is uncertainty in the property as well. Here, we explore the possibility of using interaction type model to evolve texture features. Next, these features are utilized to cluster the image. We will use modified mountain clustering [10, 16] and fuzzy C-means clustering [9].

The organization of this paper is as follows: Section 2 gives the extraction of fuzzy features and Section 3 gives the descriptors. Section 4 deals with the clustering of texture image on the basis of these features using both modified mountain clustering and fuzzy C-means clustering techniques. Results of clustering are presented in Section 5 on different texture images.

Finally, conclusions are given in Section 6.

2. Extraction of Fuzzy Features

Here, the spatial arrangement of gray levels over a window is considered. The choice of the window size is made such that the texture pattern or texel must exist in the window. Since we do not know a priori how the gray levels are distributed to form texture, we need to consider each pixel with its relative response over all the neighboring pixels in the specified window. A membership function to this effect is defined by the Gaussian type function.

» »

¼ º

« «

¬ ª

¿ ¾

½

¯ ®

­

)

2

( ) exp (

)

( b

i x j i x

P

j (1)

where x(i) is the gray level of current pixel with respect to which gray levels of all the neighboring pixels x(j) are compared and b is the fuzzifier which is taken to be the size of the window. Note that

1 ) ( i

P

j when

x ( j ) x ( i )

for

i j

(2) That is, response is maximum if the gray level of current pixel is treated as that of the neighboring pixel.

Next, we obtain the cumulative response of the current pixel by the weighted sum method. This is defined by

¦ ¦

˜

n

j n

j j j

i i x i i

y

1 1

) (

) ( ) ) (

(

P

P

(3)

This is the defuzzified response of the current pixel.

This process is repeated for all pixels in the window, giving rise to a texture subimage consisting of defuzzified values. If the image is of size MxM, it is partitioned into sub images of size wxw where w << M.

We have used the texture sub image of each window to evolve representative texture features. For convenience of notation, we designate the texture of sub image formed from y(i) by a matrix D of size wxw. Now, the content of D must be characterized via representative texture features called descriptors.

3. Descriptors

If we use all the elements of D, we would be bogged down with the computational problem. Instead, we derive descriptors that capture the essence of the texture sub image. There is an underling structure that must be brought out through a few descriptors. For example, maximum value of D would represent the highest response of a pixel in a window. We can use the entropy to represent the information content in the texture of image. Likewise, other descriptors are aimed at describing different concept such as uniformity, the arrangement of texture with response to the diagonal of D. There are many such descriptors running into hundreds. However to limit our analysis, we are using three descriptors as defined in the following:

Descriptor 1: The maximum value of D computed on windows of size wxw is designated as

^ ` ^{D i j w}

f

₁

max

_ij

1 ,

(4)

where

D

_ijis the element in matrix

D

. This descriptor gives the strongest response of the pixel.

Descriptor 2: Entropy

¦¦

w

i w

j

Dij

f

1 1

2

2 (5)

This descriptor is a measure of randomness present in the neighborhood of current pixel. It also gives the information content as mentioned above. A high value of f2 indicates that all elements of D are equal.

Descriptor 3:Uniformity; this is the lowest when all elements of D are equal. It is computed as:

¦¦

^w

i w

j

Dij

f

1 1

2

3 (6)

The effectiveness of the above descriptors in the segmentation will be ascertained after clustering.

4. Modified Mountain Clustering

Yager and Filev [11] proposed a grid based clustering algorithm, in which computation grows exponentially with the dimension of hyperspace, for estimating the number and location of cluster centers. In the n dimensional hyperspace with m number of grid lines in each dimension, the number of grid points that must be evaluated is

m

ⁿ.

We present a modified form of Yager and Filev’s method called modified mountain clustering [10, 16].

We assume that each data point has potential to become a cluster center instead of grid points. This modification makes the computation complexity independent of the dimension, because the number of grid points is equal to the number of data points. The second advantage of this modification is that it eliminates the need to specify a grid resolution, in which a compromise between accuracy and computational complexity must be struck.

The procedure of the modified method is as follows:

Let us define the jth data in hyperspace xas follows:

^

^{x j x j x}n ^j

`

^{j M}

jp ₁ , ₂ ,..., 1,...,

x

(7) where,

p 1 , 2 ... n

is the feature space and

M

is the number of data samples . Without loss of generality, we normalize each dimension p of hyperspace, so that data

points are bounded by hypercube. The normalized data point x_jpare found as:

_{max min}

min

.

_{jp jp}

jp jp

jp

x x x x

x {

(8)

where,

¿¾

½

¯®

­

n M j M

j M

jp j x x x

2 1 1 1

min min1 , min , . . . , min

x

(9) and

¿ ¾

½

¯ ®

­

n M j M

j M

jp j

x x x

2 1 1 1

max

max

1

, max , . . . , max

x

(10) Treating each data point as a cluster center, we define a measure of potential, which is a mountain function, of data point _xrpas a function of distance

rp jp rp

jp rp

jp

^c

d

²

x , x x x Q x x

between

x

_rp and all other data points given as

M d r

P d

M

j

jp rp

r , 1,2,...,

exp

1

2 1 2 1

,

»»

¼ º

««

¬ ª

¸¸

¹

·

¨¨

© §

¦

^{x x}

(11) where, Qis a

n¹u n¹

positive definite matrix and

d1 is the positive constant defining the neighborhood of data point. Data points outside radial distance d₁ have a little influence on the potential. It is evident from the mountain function that potential value of datum is an approximation of the density of data point (cardinality) in the vicinity of datum. The higher the potential value of each of the data points in hypercube the higher the chance of being a cluster center. The first cluster center is selected with the highest value of _Pr,1 as follows:

1 1 1 1

1 max _r,

M p r

p x  P P

c (12)

For the selection of second cluster center, the potential value of each data point is revised in order to remove the effect of mountain function around the first cluster center as follows:

M d r

P d P

P_{r r r} ^rp, ^p 1,2,...,

exp ₂

2 1 2 1

, 1 , 2

,

»»

¼ º

««

¬ ª

¸¸

¹

·

¨¨

© §

x c

(13)

where, d₂ is the positive constant defining the neighborhood of cluster center. It is evident from (11) that the data points near the first cluster center have greatly reduced potential value and is unlikely to be selected as the next cluster center. After revision of potential value of each data point, second cluster center is selected with the highest value of _Pr,2 as under:

2

2 1 2

2 max _r,

M p r

p x  P P

c (14)

Similarly, for the selection of k^th cluster center, revision of potential value for each data point is done as:

M r

d P d

P

P_{rk rk rk} ^{rp k p} 12

2 2

1 2 1

1 , , ,...,

, exp

,

,

»»

¼ º

««

¬ ª

¸¸

¹

·

¨¨

©

§

c x

(15) and k^th cluster center is selected with the highest value of _Pr,k as under

1 rk M k r kp

kp

x

 P

max P

_,

c

(16)

The optimum number of clusters for the data set

^ `

t t^M

M x 1

D is decided by the validity function S which is the ratio of compactness and separation [12]:

min

²

1 1

2 2 ,

jp j ip

i m

k M

r

kp rp k r

M S

c c

c x

z

¦¦ ^P

(17)

where, the membership function P_r,k represents the degree of association of r^thdata to the k^th cluster center and is defined as:

2 2 2

» »

¼ º

« «

¬ ª

¸ ¸

¹

·

¨ ¨

©

§

d

d

_{rp kp}

k r

c exp x

P

, (18)

We note that S has a tendency to decrease eventually when the number of cluster centers is very large. So, the value of S is meaningless when number of cluster centers gets close to M . The number of clusters is decided by a validity function in (17).

It is observed that in modified mountain clustering, clusters are identified one after another. Inclusion of a new cluster does not pose any problem in this clustering approach as against fuzzy C- means clustering where

the clustering has to be done all over again. Also unlike modified mountain clustering, in fuzzy C-means, the number of clusters has to be specified in advance.

Determination of d1 and d2

In each window, we determine the normalized feature which is the minimum among all. Then from all these minima of windows, the following empirical formula is found to yield consistent clusters.

¦ ¦

_°^°

¿

°°¾

½

°°

¯

°°®

­

N

j

i i i

f f d N

d

1

3

1 2

1

) min(

2

1 (19)

where, N is the number of windows that span the image.

5. Results of Segmentation

For testing we have constructed composite texture images of size (256x256) by combining Brodatz primitive textures [13]. The texture images are shown in Figs.1 and 6. The selection of window size depends on the size of the repetitive texture pattern in the texture image. A smaller window size may not provide representative texture features (descriptors) while a large window results in a high computational cost. We have considered a window size of 16x16as a compromise between the computational cost and the effective features. The image is partitioned into 16 sub images of size 16x16. Each window gives rise to 3 descriptors. Thus we have 16 feature vectors each of dimension 3. These features vector are used in clustering the texture image.

We have implemented both modified mountain clustering (MMC) and fuzzy C-means (FCM) clustering. In MMC, each feature vector is considered as a potential cluster center. A mountain function, which is a measure of potential of the chosen point with respect to the neighboring points, is computed. The Euclidean distance between the chosen point and all other points is evaluated to find the point with the highest potential value. The cluster center is declared as the point yielding the highest potential value. In our study we have used Q to be the unity matrix for want of Euclidean distance between the chosen point and all other points. The distance d₁ has been found to be 0.44.

For the selection of second cluster center the potential value of each cluster center is revised by removing the effect due to the first cluster. The above procedure is repeated to find the maximum potential value, which yields the second cluster center. The optimum number of the clusters is then decided by the validity function, which is the ratio of compactness to the separation. The

compactness is related to the closeness of all other points with respect to a cluster center whereas the separation indicates the distance between the cluster centers.

We have compared the results of the texture representation using both types of clustering. The segmentation results of 4-texture, and 6-texture are shown in Figs. 2-5, Figs.7-10 respectively. Figures 2 and 7 correspond to segmentation by MMC, whereas Figs.3 and 8 correspond to segmentation by FCM. We note here that MMC is better than FCM since there is a problem with one edge in FCM. We have used alternative fractal features using FD described in Appendix A. Segmentation of fractal features by MMC is shown in Figs. 4 and 9 and by FCM in Figs. 5 and 10.

These figures demonstrate the superiority of MMC over FCM.

It can be observed that fuzzy features are comparable in performance to fractal features. However, the fuzzy feature selection has to be improved by using run lengths instead of simply gray values. The fuzzy features are not as effective as fractal features for large number of textures even though they are comparable for small number of textures. The choice of parameters in respect of MMC has been arrived at empirically. One more study to be conducted relates to the choice of b in the fuzzification function. This has been fixed at 16, the window size. Instead it should be calculated by using certain criteria. The present work has opened up different ways of evolving fuzzy features for texture segmentation. We advocate the fuzzy based segmentation for the simplicity of computation and analysis

The various texture parameters for image in Fig.1 are listed in Table 1 and Table 2.

6. Conclusions

This paper presents a fuzzy approach for texture image segmentation. We have devised new fuzzy features by taking the cumulative response of neighboring pixels on a current pixel. This response is defined by a Gaussian type membership function. For the purpose of extracting features, the given image is partitioned into sub-images of size wuw and is replaced with texture features.

From these features, we have constructed three descriptors from each of the windows, which are then used in clustering. Out of the two clustering techniques, the modified mountain clustering fares well in terms of performance. Moreover, it does not need the specification of number of clusters such as in the case of Fuzzy C-means clustering. The performance of the proposed fuzzy based descriptors is comparable to fractal descriptors.

References

1. S.G. Carlton and O.R. Mitchell, “Image segmentation using texture and gray level, Proceedings of the. IEEE Conference on Pattern Recognition and. Image Processing, 1977.

2. T. Pavlidis and P. C. Chen, “Segmentation by texture using co-occurance matrix and split-and- merge algorithm,” Computer Graphics and Image Processing, vol. 10, pp. 172-182, 1979.

3. A.Baraldi and F. Parmiggiani, “An Investigation of the Textural Characteristics Associated with Gray Level Cooccurance matrix Statistical Parameters,”

IEEE Transactions on Geoscience and Remote Sensing, vol.33, no.2, pp.293-304, Mar. 1995.

4. R. W. Conners, M. M. Trivedi and C. A. Harlow,

“Segmentation of a high resolution urban scene using texture operators,” Computer Vision Graphics and Image Processing, vol. 25, pp. 273- 310, 1984.

5. S. Chatterjee and R. Chellappa, “Maximum likelihood texture segmentation using Gaussian Markov random field models,” Proceedings of the.

IEEE Conference on Computer, Vision, Graph, Pattern Recog., 1985.

6. B. B. Chaudhuri, N. Sarkar and P. Kundu, “An Improved Fractal Geometry based Texture Segmentation Technique,” Proc. IEE-part E, pp.

140, 223-241, 1993.

7. K. Jain and F. Farrokhnia, “Unsupervised texture segmentation using gabor filters,” Pattern Recognition, vol. 24, pp. 1167-1186, 1991.

8. C.Bouman and B.Liu,”Multiple Resolution Segmentation of Textured Images,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.13, no.2, pp.99-113, Feb. 1991.

9. R. Wilson and M. Spann, “Efficient Implementation of the Fuzzy C-Means Clustering Algorithms,” IEEE Trans. on Pattern Anal. And Machine Intell., vol. 8, no.2, pp. 248-255, 1986.

10. M. F. Azeem, M. Hanmandlu, N. Ahmad,

“Modified Mountain clustering and dynamic fuzzy modeling”, 2^nd Int. Conf. Inform. Technol.,

Bhubaneshwar, India, Dec.20-23, pp.63-68.

11. Ronald R. Yager and Dimitar P. Filev, Essential of Fuzzy Modeling and Control, John Wiley & Sons, pp. 246-261, 1994

12. Xuanli Lisa Xie and Gerardo Beni, "A Validity Measure for Fuzzy Clustering", IEEE Transactions on Pattern Analysis Machine Intelligence, Vol.13, No.8, pp. 841-847, August 1987.

13. P. Brodatz, Texture: A Photographic Album for artists and designers, Dover, New York 1966.

14. B. Mandelbrot and J. Van Ness, “Fractional Brownian Motion, fractional noise and applications,” SIAM Review, vol. 10, 1968.

15. R. Voss, “Random Fractals: characterization and measurement,” Scaling Phenomena and Disordered Systems, 1986.

16. M.F. Azeem, M. Hanmandlu and N. Ahmad,

“Structure Identification of generalized adaptive neuro-fuzzy systems”, IEEE Transactions on Fuzzy Systems, Vol.11, No.5, pp. 666-681, October 2003.

APPENDIX A: Fractal features

The concept of self-similarity can be used to estimate the fractal dimension. A bounded set A in Euclidian n- space is self-similar if A is the union of N_r distinct (non-overlapping) copies of itself scaled up or down by a ratio

r

. The following relation gives the fractal dimension D of A:

) 1 log(

) 1 log(

r D N

r

N_r ˜ ^D Ÿ ^r (A.1)

There exist several approaches to estimate the FD of an image. We use the Differential Box Counting (DBC) method in [6] for deriving the fractal features.

Equation (A.1) is the basis of estimating the FD by the DBC approach. Here, N_r is determined in the following way. Assume that the image of size

M u M

pixels is scaled down to a size sus with 1

2tst

M , r s M and s is an integer. Consider the image as a 3D space with

( x , y )

denoting 2D position and the third coordinate

z

denoting gray-level.

The

( x , y )

space is partitioned into grids of sizesus. On each grid there is a column of boxes of sizesusus. Let the minimum and the maximum gray level of the image in the

( i , j )

th grid fall in the kth and the lth box, respectively. Then,

1 )

,

(i j lk

n_r (A.2)

is the contribution of the Nr in the

( i , j )

th grid. Taking contributions from all grids, we have

¦

i j r

r

n i j

N

,

) ,

(

(A.3) Nr is counted for different values of

r

(i.e. different values ofs). Then using (A.1) we can estimate

D

, the fractal dimension, from the least squares linear fit of log Nrvs. log(1r). Because of the differential nature of

) , (i j

n_r , this method is called the Differential Box Counting (DBC) method. In actual implementation, a random placement of boxes is applied in order to reduce quantization effects.

Feature selection

Here, we use five features in order to discriminate the texture. They are based on the FD of:

x the original image

x the high gray-valued image x the low gray-valued image x the horizontally smoothed image x the vertically smoothed image For any feature value

f

, we have f 

> @

^0,1 _.

Feature 1: The FD of the original image I1 is computed on overlapping windows of size

) 1 2 ( ) 1 2

( W u W

. Thus, at point

( i , j )

the first feature value F₁(i, j) is defined as

^

^{i l j k}

`

^{w l k w}

FD j

i

F₁(, ) ( ),( ) d , d (A.4) where FD is the fractal dimension.

Since2dF₁(i, j)d3, we define the normalized feature as f₁(i, j) F₁(i, j)2 so that

1 ) , (

0d f₁ i j d .

Features 2-3: Consider two modified images called the high and low gray-valued images I2 and I3

respectively, defined as

1 1

1 1

2(i, j) I (i, j) L if I (i, j) L

I !

otherwise

0 (A.5)

) 255 ( ) , ( 255

) ,

(

_{1 1 2}

3

i j L if I i j L

I !

otherwise j

i

I₁(, ) (A.6) where L₁ g_min av 2 and

L

₂

g

_max

av 2

while g_max, g_min and av denote the maximum, minimum and the average gray value in I1, respectively. If two images have the same FD, their high gray-valued images do not have an identical roughness and their FDs would be different. The normalized features f2 and f3 are computed from I2 and I3 .

Features 4-5: The FD of an image is related to its roughness and hence by the gray value smoothing. For a highly oriented texture, the FD will be affected least if the texture is smoothed along the direction of its dominant orientation. But if the smoothing direction is perpendicular, the FD will be substantially reduced.

We take images smoothed in their horizontal and vertical direction and compute their FD as the fourth and the fifth feature. Horizontally and vertically smoothed versions of the image are defined as:

¦

w

w k

k j i w I

j i

I ( , )

) 1 2 ( ) 1 ,

4

(

(A.7)

¦

w

w k

j k i w I

j i

I ( , )

) 1 2 ( ) 1 ,

5

(

(A.8)

The normalized FD features f4 and f5 are computed from I4 and

I

₅ respectively.

Table 1. Fuzzy Feature Range

Feature 1 Feature 2 Feature 3 Texture 1 0.3320-0.9922 0.0-0.5201 0.0-0.6890 Texture 2 0.3516-0.9961 0.0-0.4856 0.0-0.8250 Texture 3 0.6484-0.9961 0.0-0.5787 0.0-0.2270 Texture 4 0.6172-0.9961 0.0-0.2847 0.0-0.6584

Table 2. Intermediate Values for 4-Texture Image

Texture 1 Texture 2 Texture 3 Texture 4

Potential (P) 1.0e+019* -9.979 -7.3597 -9.6867 -9.9712

Cluster Center (C) 0.3555 0.9922 0.6094 0.5923

d 0.4688 1.3468 0.6248 0.7571

Separation 0.0084 1.10E-03 1.58E-04 0.1084

Compactness 0.2569 0.2641 0.3469 0.3105

Validity (S) 0.1202 0.914 8.5839 0.0112

Fig. 1 Fig. 2 Fig. 3

Fig. 4 Fig. 5 Fig. 6

Fig.7 Fig.8

Fig.9 Fig.10