Online Image Segmentation using Сredibilistic Fuzzy Clustering

Abstract

Computational intelligence methods are widely used to solve many complex problems, including, of course, traditional: Data Mining and such new directions as Dynamic Data Mining, Data Stream Mining, Big Data Mining, Web Mining, Text Mining, etc. In the paper was proposed new adaptive on-line methods of fuzzy robust clustering-segmentation of data streams based on probabilistic, possibilistic and credibilistic approaches. Using proposed approach, it's possible to solve clustering task in on-line mode when data are fed to processing sequentially, possible in real time.

Keywords

• 1 Segmentation
• clustering
• data stream
• credibilistic approach
• fuzzy image segmentation

-

1. Introduction The current state of technological development is inextricably linked with the development of computerized tools, which, in turn, are dependent on the mathematical apparatus and practical algorithms that use it. The development of computer tools, in particular hardware, acts as a catalyst for the development of existing and the emergence of new scientific fields, such as Data Science. Modern capabilities of computing environments allow the implementation of algorithmically sufficiently complex methods that are the basis of intellectual analysis. And this should become an impetus for the development of new hardware and software systems based on the theoretical principles of artificial intelligence.

Recently, in the tasks of analyzing and processing non-stationary signals of an arbitrary nature under conditions of uncertainty, computational intelligence methods are increasingly being used, among which hybrid neural networks can be distinguished.

By the task of data segmentation, we will understand the division of the data sample into homogeneous homomorphic segments based on the analysis of changes in the internal properties of the data. Currently, several segmentation methods are known, namely using wavelet analysis [1], fractal-wavelet technologies [2], neuro-fuzzy technologies [3-5], etc.

Depending on the specifics of the problem being solved, two main types of forecasting and segmentation methods can be applied: real-time and batch.

Many neural network architectures, including hybrid structures, are used to solve this kind of problems, but these systems are either cumbersome in their architecture or not sufficiently adapted for real-time learning. In most cases, the activation functions of such networks are sigmoidal functions, splines, polynomials, and radial basis functions. 2. Credibilistic fuzzy clustering Traditionally, the initial information for the clustering problem is a sample of observations consisting of N n - dimensional feature vectors:

X = {x( 1 ), x( 2 ),..., x(k ),..., x(N )}, x(k ) =),..., ( x1(k xn (k ))T ∈ Rn , k = 1, 2, …, N, and the result of the algorithm is the distribution of the initial data set into mclasses with a certain level wj(k) belonging to the k-th feature vector of the j-th cluster.

At the same time, there is a wide class of problems when the initial information comes not in vector, but in matrix form, i.e.

x(k ) = {xi1i2 (k )}; where i1 = 1, 2, …, n1, i2 = 1, 2, …, n2, k = 1, 2, …, N. Such situation is characteristic, for example, in image processing [6], when the initial (N1 × N2)-matrix is divided into N = N1N2(n1n2)-1 (n1 × n2) fragment matrices that are subject to clustering, because of which the homogeneous in some sense segments of this image. Traditionally, this problem is solved by preliminary vectorization of fragments and the use of already known procedures, the most popular of which is the method of clustering fuzzy C-means [6, 7].

To process matrix data, it is necessary to introduce matrix methods of clusteringsegmentation, for which it is advisable to introduce into consideration the matrix method of fuzzy C - means, which is a generalization of FCM. This method will avoid unnecessary vectorizationdevectorization operations when processing data given in the form of two-dimensional arrays and provides information processing in online mode.

So, let the sample of observations be given

x(k ) ={xi1i2 (k )}∈ Rn1×n2 , k = 1, 2,..., N , at the same time, for the convenience of further processing, these data are pre-centered relative to the average: and normalized to its spherical norm (Frobenius norm): x = 1 N

∑ x(k )

N k=1 x(k ) = Tr ( x(k )xT (k )).

The matrix probabilistic criterion is used as the objective function of clustering: E(wj (k ), c j )

N m =∑∑ wβj (k )D2 (x(k ), c j ) k=1 j=1

N m =∑∑ wβj (k )Tr ((x(k ) − c j )(x(k ) − c j )T ), k=1 j=1 in presence of constraints m m m ∑ wj (k ) = 1 ∨ ∑ wj (k ) −1 = 0, k = 1, 2,..., N , 0 < ∑ wj (k ) < N , j = 1, 2,..., m.

j =1 j =1 j =1 By introducing the Lagrange function:

L(wj (k ), c j , λ(k ))

N m N  m  =wβj(k ∑ ∑ )D2 (x(k ), c j ) + ∑ λ(k )  ∑ wj (k ) −1 k=1 j=1 k=1  j=1  =

N  m  m   =wβj(k ∑  ∑ )D2 (x(k ), c j ) + λ(k )  ∑ wj (k ) −1 , k =1 j =1  j =1   ( 1 ) ( 2 ) ( 3 ) ( 4 )  ∂L(wj (k ), c j , λ(k ))  ∂wj (k )   ∂L(wj (k), c j , λ(k ))   ∂λ j (k) = βwβj−1(k )D2 (x(k ), c j ) + λ(k ) = 0;

m =∑wj (k ) −1 =0;

j=1 where λ(k) – uncertain Lagrange multiplier, and solving the system of Kuhn-Tucker equations:  ∂L(wj (k), c j , λ(k))  N  ∂c j (k)  =−2 ∑k=1 wβj (k)(x(k) − c j ) =O,  ∂L(wj (k ), c j , λ(k ))  where  ∂c j (k )  ∂L(wj (k ), c j , λ(k )) ∂c ji1i2 – (n1 × n2 ) matrix formed from partial derivatives ; Ο – matrix of the same dimension formed by zeros, thus, we arrive at the final form of the algorithm:  1  (D2 (x(k ), c j ))1−β wj (k ) = ∑lm=1 (D2 (x(k), cl ))1−1β ; λ(k) ∑=N−wβj∑l(m=k1)xβ(Dk)2 (x(k), cl )1−1β 1−β ; c j = k=1∑kN=1 wβj (k ) .

The resulting system gives rise to a wide class of clustering procedures. Thus, if we set β = 2, we get a simple and effective matrix clustering algorithm [8], which is a generalization of the popular procedure of J. Bezdek [6]:  (Tr(x(k ) − c j )(x(k ) − c j )T )−1 wj (k ) = m  N ∑l=1 (Tr(x(k ) − cl )(x(k ) − cl )T )−1  ∑ w2j (k )x(k ) c j = k=1 N ,  ∑ u 2j (k )  k=1 ; where Tr – matrix trace symbol.

The main difference between probabilistic and possibilistic approaches is that probabilistic algorithms use relative similarities between objects and clusters, while probabilistic algorithms use absolute similarities.

Instead of the fuzzy partition matrix in the fuzzy C-means algorithm, the possible C-means algorithm uses a (N × m) - matrix of possibilities or typicality matrix T = {tj(k)}, where tj(k) ∈ [0, 1] – the possibility that the object x(k) belongs to cluster j. ( 5 ) ( 6 ) The possibilistic matrix has only the following limitations:

m 0 < ∑t j (k) ≤ m, k =1, 2,…, N.

j=1

This means that an object can have a feature vector that contains only values close to zero (usually such objects are considered noise) or only ones.

Krishnapuram, Keller et al proposed the probabilistic C-means (PCM) algorithm and two algorithms that combine probabilistic and possibilistic approaches: the probabilistic-possibilistic C-means algorithm (FPCM) and the possibilistic-probabilistic C-means algorithm (PFCM) [9-11].

In the PCM algorithm, formula ( 6 ) was replaced by the expression:  t j (k ) =        c j = k=1      ∑Nt βj (k ) x (k ) ∑Nt βj (k ) k=1 , 1 γ j 1 +  Tr ( x (k ) − c j )( x (k ) − c j )T β−1   1 ; ( 7 ) ( 8 ) where γj > 0 – a constant determined empirically. It can be seen that the calculation of the cluster prototype in formulas ( 6 ) and ( 8 ) is identical, with the only difference that the matrix of fuzzy partitioning is changed to the matrix of possibilities. The calculation of the possibility of an object belonging to a cluster in formula ( 8 ) can be justified as a bell-shaped function presented in Figure 1. Keller and Krishnapuram suggested choosing the parameter γj in the form: γ j =K k=1

N T ∑ wβj (k )Tr ( x (k ) − c j )( x (k ) − c j )

N ∑ wβj (k ) k=1 where K > 0 (most often K = 1). But calculations γj by formula ( 9 ) requires memory to store the fuzzy partition matrix, as well as time for its use.

The PCM algorithm does a good job of suppressing interference and can usually be applied when it is necessary to improve the results obtained with the help of other algorithms. Also, this algorithm can merge close clusters into one, from which it follows that the initial number of clusters that was set in advance is too large (at the same time, the PCM algorithm can merge clusters that should be separated).

The FPCM and PFCM algorithms use both a fuzzy partition matrix and a feature matrix, trying to take advantage of both approaches.

The FPCM algorithm uses the following formulas:   wj (k ) =

1 (Tr ( x (k ) − c j )( x (k ) − c j )T )1−β m 1 ; ∑(Tr ( x (k ) − cl )( x (k ) − cl )T )1−β l=1     t j (k ) =     N  ∑( wβj (k ) + t ηj (k )) x(k) c j = k=1 N  ∑k=1 ( wβj (k ) + t ηj (k ))

1 (Tr ( x (k ) − c j )( x (k ) − c j )T )1−η N 1 ; ∑(Tr ( x (l ) − c j )( x (l ) − c j )T )1−η l=1 , where η > 0 (in most cases η = 2).

The FPCM algorithm uses the standard procedure for calculating the fuzzy partition matrix, but the possibility matrix is calculated using a new formula. Cluster prototypes are calculated using the sum of both matrices.

The PFCM method uses a standard procedure for calculating the fuzzy partition matrix (as in formula ( 6 )). The procedure for calculating the possibility matrix was taken from PCM ( 8 ) and slightly modified. Centroids are calculated as in the FPCM algorithm, but both matrices have their own weights: ( 10 ) ( 11 )   wj (k ) =      t j (k ) =

1 (Tr ( x (k ) − c j )( x (k ) − c j )T )1−β m 1 ; ∑(Tr ( x (k ) − cl )( x (k ) − cl )T )1−β l=1 1

1 ;     ∑N(awβj (k ) + bt ηj (k )) x(k) c j = k=1∑kN=1 (awβj (k ) + bt ηj (k )) 1 +  b Tr ( x (k ) − c j )( x (k ) − c j )T β−1  γ j  where a > 0, b > 0. The constants a and b determine the relative importance of the fuzzy partition matrix and the capability matrix in the centroid calculation function. By setting a = 0, algorithm ( 11 ) goes to PCM, and by setting b = 0, algorithm ( 11 ) goes to FCM.

Analyzing all the presented methods, several conclusions can be drawn. First, the membership function of the FCM algorithm with its limitations is too "strong", allowing outlier objects to be assigned to one or more clusters, which, in turn, can greatly affect the underlying structure of the data set. On the other hand, the PCM method's constraint on the features is too weak – it allows to refer to a cluster independently of the rest of the data. Also, PCM is very sensitive to the initialization of the capability matrix. The PFCM method is an efficient combination of the two approaches, and the clustering results depend on the parameter setting a, b, β, η.

Algorithm ( 6 ) can be extended to the case when data for processing are received sequentially in on-line mode. To do this, by applying the Arrow-Hurwitz-Uzawa saddle point search procedure to the Lagrangian ( 4 ), when the (k+1)th observation is received, the estimates of the membership levels and centroids can be refined using recurrence relations [12]  1  (D2 (x(k + 1), c j (k ))1−β ) wj (k + 1) =∑lm=1 (D2 (x(k + 1), cl (k ))1−1β ) ;   c j (k + 1) =c j (k ) − η(k )  ∂L(wj (k + 1), c j , λ(k + 1))  =   ∂c j  =c j (k ) + η(k )wβj (k + 1)(x(k + 1) − c j (k )), for an arbitrary value of the fuzzifier β and  (Tr(x(k + 1) − c j (k ))(x(k + 1) − c j (k ))T )−1 wj (k + 1) =m  ∑ (Tr(x(k + 1) − cl (k ))(x(k + 1) − cl (k ))T )−1  l=1 c j (k + 1) =c j (k ) + η(k )w2j (k + 1)(x(k + 1) − c j (k )), ; for β = 2.

It is easy to see that the expression ( 13 ) is an adaptive version of the procedure ( 4 ), and ( 13 ) is, accordingly, ( 6 ).

The matrix credibility criterion is used as the objective function of clustering:

E (Cred j (k ), c j )

N m =∑Cred ∑ βj (k )D2 ( x(k ), c j ) k=1 j=1

N m =∑Cred ∑ βj (k )Tr ((x(k ) − c j )(x(k) − c j )T ) ( 14 ) k=1 j=1 in presence of constraints 0 ≤ Cred j (k ) ≤ 1∀j, k,  sup Cred j (k ) ≥ 0,5∀k, Cred j (k ) + sup Credl (k ) =1 where Cred j (k ) - level of observation x(k ) credibility.

In the procedures of credibilistic fuzzy clustering, the level of membership is determined by the membership functions [13]: wj (k) =ϕ j ( D ( x(k), c j )) =ϕ jTr ((x(k) − c j )(x(k) − c j )T ) ( 12 ) ( 13 ) ( 15 )

It is easy to see that membership level ( 16 ) using the distance is based on similarity measure [14]. As such a measure in [15], it was proposed to use a function: wj (k) =

1 1 + Tr ((x(k) − c j )(x(k) − c j )T ) .

Thus, if the fuzzy clustering algorithm in a batch form can be written as [16]:

1 1 + Tr ((x(k) − c j )(x(k) − c j )T ) ,

wj (k) sup wl (k)

,  wj (k) =   w∗j (k) =   Cred j (k) = w∗j (k) + 1 − sup wl∗ (k)

,    c j = k=1 N  ∑Cred βj (k)  k=1

N ∑Cred βj (k)x(k) 2 , in the online mode this procedure ( 18 ) has the form (19):

m  1 −1 =∑Tr ((x(k + 1) − c j )(x(k + 1) − c j )T )1−β  , ll≠=1j   (Tr ((x(k +1) − c j )(x(k +1) − c j )T ))β −1 −1

 , σ 2j (k + 1)    σ 2j (k + 1)    wq (k + 1) = 1 +      

wj (k +1) w∗j (k +1) = ,  sup wl (k +1)  1 Cred j (k +1) =( w∗j (k +1) +1 − sup wl∗ (k +1)),  2 c j (k + 1) =c j (k) +η (k + 1)Cred βj (k + 1)( x(k + 1) − c j (k)) or in case when β = 2 ( 17 ) ( 18 ) (19) 

It is easy to see that the recurrent fuzzy clustering algorithm is not more complex than the online modifications of probabilistic, possibilistic, and robust procedures [17, 18]. 3. Experimental research Digital images, including satellite images of the city of Kharkiv, were used to test the implemented matrix credibilistic modifications of the clustering algorithm. Samples have no missing attributes and are numeric.

The result of the algorithm is the final fuzzy partition matrix for all sample objects and class prototypes.

When processing digital images, objects (matrices or vectors of the same dimensions) are formed from fragments of this image, and each pixel from the RGB (Red-Green-Blue) color model is converted to the Grayscale model, where the brightness of a pixel is expressed as a scalar value from the interval [0,1]. The conversion from the RGB model to the Grayscale model is performed according to the formula:

Y = (0.299R + 0.587G + 0.114B) / 255 , where Y is the brightness of the pixel glow, R, G, B are the brightness of the glow of red, green, and blue tones, respectively, the values of which are in the interval [0, 255].

Observation sets formed from digital images are processed according to the same principle as standard quantitative samples. After image processing, each cluster is assigned the colors of the Grayscale model, and each object is colored in the color of the nearest cluster.

To evaluate the quality of the algorithm, the following criteria were used: Partition Coefficient (PC), Classification Entropy (CE), Partition Index (PI) with the same initialized fuzzy partition matrix U0.

Table 1 shows the results of the accuracy and speed of the clustering algorithms on the Iris sample, and Table 2 shows the results of the satellite digital image of the city of Kharkiv. The time given is an average for one iteration, considering the vectorization-devectorization operation.

On Figure 2 show the initial image, the resampled sample (20% of objects) and the result of the cluster analysis and the process of the algorithm.

On Figure 3 shows the result of digital image clustering by the adaptive matrix mrthod of fuzzy credibilistic clustering. The work is supported by the state budget scientific research project of Kharkiv National University of Radio Electronics "Deep hybrid systems of computational intelligence for data stream mining and their fast learning" (state registration number 0119U001403).

References

[1] Chan , K. Efficient time series matching by wavelets , in: Proceedings of 15th IEEE Int. Conf. on Data Engineering , 1999 , pp. 126 - 133 .

[2] Ruspini , Enrique H. , James C. Bezdek , James M. Keller, Fuzzy clustering: A historical perspective , in: IEEE Computational Intelligence Magazine 14.1 , 2019 , pp. 45 - 55 .

[3] J.C. Bezdek , Pattern Recognition with Fuzzy Objective Function Algorithms , N.Y.: Plenum Press, 1981 .

[4] Oyewole , Gbeminiyi John , and George Alex Thopil, Data clustering: application and trends , Artificial Intelligence Review 56.7 , 2023 , pp. 6439 - 6475 .

[5] Agrawal , Anurag Vijay , et al. "A probability-based fuzzy algorithm for multi-attribute decision-analysis with application to aviation disaster decision-making." Decision Analytics Journal 8 ( 2023 ): 100310 .

[6] Wongkhuenkaew , Ritipong , et al. "Fuzzy K-nearest neighbor based dental fluorosis classification using multi-prototype unsupervised possibilistic fuzzy clustering via cuckoo search algorithm." International Journal of Environmental Research and Public Health 20.4 ( 2023 ): 3394 .

[7] Bodyanskiy , Yevgeniy, Valentyna Volkova , and Mark Skuratov . "Matrix Neuro-Fuzzy SelfOrganizing Clustering Network." Computer Science ( 1407 - 7493 ) 50 ( 2011 ).

[8] Zhang, Yong , et al. "Possibilistic c-means clustering based on the nearest-neighbour isolation similarity . " Journal of Intelligent & Fuzzy Systems 44.2 ( 2023 ): 1781 - 1792 .

[9] Hashemi , Seyed Emadedin , Fatemeh Gholian-Jouybari, and Mostafa Hajiaghaei-Keshteli. "A fuzzy C-means algorithm for optimizing data clustering . " Expert Systems with Applications 227 ( 2023 ): 120377 .

[10] Zhang , Yong , et al. "Possibilistic c-means clustering based on the nearest-neighbour isolation similarity . " Journal of Intelligent & Fuzzy Systems 44.2 ( 2023 ): 1781 - 1792 .

[11] Hussain , Ishtiaq, Kristina P. Sinaga , and Miin-Shen Yang . "Unsupervised multiview fuzzy cmeans clustering algorithm . " Electronics 12 .21 ( 2023 ): 4467 .

[12] Yang , Miin-Shen , and Josephine BM Benjamin. "Sparse possibilistic c-means clustering with Lasso." Pattern Recognition 138 ( 2023 ): 109348 .

[13] Bodyanskiy Ye , Shafronenko A. , Mashtalir S. , Online robust fuzzy clustering of data with omissions using similarity measure of special type , Lecture Notes in Computational Intelligence and Decision Waking-Cham: Springer, 2020 , pp. 637 - 646 .

[14] Young F.W. , Hamer R.M. Theory and Applications of Multidimensional Scaling- Hillsdale , N.J.: Erlbaum, 1994 .

[15] Dahiya , Sonika, and Anjana Gosain . "DOIFCM: An Outlier Efficient IFCM." Computational Intelligence in Analytics and Information Systems . Apple Academic Press, 2023 . 135 - 149

[16] Kyrychenko , O. , Ostapov , S. , & Malyk , I. , Cluster Analysis of Information in Complex Networks , in: International Journal of Computing , 22 ( 4 ), 2023 , pp. 515 - 523 . https://doi.org/10.47839/ijc.22.4. 3360

[17] Linan , M. N. , B. Gerardo , and R. Medina . "Modified weight initialization in the self-organizing map using Nguyen-Widrow initialization algorithm . " Journal of Physics: Conference Series . Vol. 1235 . No. 1 . IOP Publishing , 2019 . https://doi.org/10.47839/ijc.19.1. 1694

[18] Sirola , Martti, and John Einar Hulsund. "Machine-learning methods in prognosis of ageing phenomena in nuclear power plant components." International Scientific Journal of Computing 20.1 ( 2021 ): 11 - 21 .https://doi.org/10.47839/ijc.20.1.2086