Improved,Spectral,Clustering,Clothing,Image,Segmentation,Algorithm,Based,on,Sparrow,Search,Algorithm

HUANG Wenan(黄文谙) ， QIAN Suqin(钱素琴)*

1 College of Information Science and Technology, Donghua University, Shanghai 201620, China

2 Engineering Research Center of Digitized Textile & Fashion Technology, Ministry of Education, Donghua University, Shanghai 201620, China

Abstract: In the process of clothing image researching, how to segment the clothing quickly and accurately and retain the clothing style details as much as possible is the basis of subsequent image analysis. Spectral clustering clothing image segmentation algorithm is a common method in the process of clothing image extraction. However, the traditional model requires high computing power and is easily affected by the initial center of clustering. It often falls into local optimization. Aiming at the above two points, an improved spectral clustering clothing image segmentation algorithm is proposed in this paper. The Nystrom approximation strategy is introduced into the spectral mapping process to reduce the computational complexity. In the clustering stage, this algorithm uses the global optimization advantage of the particle swarm optimization algorithm and selects the sparrow search algorithm to search the optimal initial clustering point, to effectively avoid the occurrence of local optimization. In the end, the effectiveness of this algorithm is verified on clothing images in each environment.

Key words: clothing segmentation; spectral clustering; particle swarm optimization algorithm; intelligent fashion design

In the development of clothes industry, due to the progress of digital technology, the field of fashion design is moving towards intelligent integration. How to quickly and effectively obtain clothing information in image samples and create preconditions for subsequent image processing is a hot spot in the field of intelligent fashion design. Image segmentation technology is an important method to obtain clothing information effectively. Clothing image segmentation technology could effectively filter useless information through specific means. Joukovskyetal.[1]proposed a deep learning based method to perform semantic segmentation of clothes from RGB-depth map images. Jietal.[2]proposed a semantic locality-preserving segmentation model based on the deformable convolutions to extract the non-rigid geometry-aware features for clothing images. De Souza Incio and Lopes[3]proposed a framework for clothing segmentation based on the single shot multibox detector (SSD) and the feature pyramid network (FPN) with the EfficientNet model as the backbone. Traditional image segmentation techniques include segmentation based on graph theory which is using the theoretical methods in the field, and image segmentation is transformed into vertex division. Freire-Obregónetal.[4]introduced a new clothing segmentation method based on the application of the GrabCut technique over a trixel mesh. Yaoetal.[5]proposed a new method to automatically segment and re-color the clothing based on background subtraction. Granaetal.[6]proposed a color based skin detection method to realize clothing region segmentation. As a segmentation method based on graph theory, the spectral clustering algorithm[7]is widely used in clothing images. Compared with the traditional clustering algorithm, the spectral clustering algorithm has obvious advantages and can be applied to arbitrary shape sample space, breaking the limitation thatk-means algorithm can only cluster in convex ball sample space. However, the spectral clustering algorithm also has the following disadvantages: time complexity and space complexity are large, and thus computational cost is high; in the clustering stage, it is greatly affected by the initial value and is easy to fall into local optimization. In view of the above two points, this paper proposes an improved spectral clustering clothing image segmentation algorithm based on the sparrow search algorithm, which is effectively verified by clothing images in different environments.

Spectral clustering algorithm is an algorithm evolved from graph theory. Its basic idea is to treat data as multiple points in space which are connected by undirected edges with different weights. Then the graph composed of all data points is cut to make the sum of weight among different sets as low as possible and the sum in each set as high as possible, so as to achieve the purpose of dividing the whole data points into different sets. Taking Ng-Jordan-Weiss(NJW) cutting algorithm[8]as an example, its basic steps are as follows.

(1)Construct the similarity matrix according to the requirements. The similarity matrix is usually constructed by a full connection method. In the full connection method, the weight between two points is defined by kernel function. Gaussian kernel function is commonly used, so for a given sampleX={x1,x2…,xn},the similarity matrixWis

(1)

whereωijis the weight between samplesxiandxj;σis a given parameter.

(2)Construct Laplace matrix. The Laplace matrixLis

L=D-W，

(2)

whereDis a diagonal matrix and its elementdiiis

(3)

The normalized Laplace matrixLnoris

(4)

(3)Calculate the firstklargest eigenvectors, standardize the matrix composed of their corresponding eigenvectors according to rows, and finally form the matrixF.

(4)Each row inFis taken as a sample, which is divided byk-means clustering, and the pixels corresponding to each row are also divided into this category.

By analyzing advantages and disadvantages of the traditional spectral clustering algorithm, it is summarized that the spectral clustering algorithm is limited by the number of samples and is greatly affected by the initial value. On this basis, this paper will optimize the traditional spectral clustering algorithm from two aspects: Nystrom approximation strategy and improving the clustering process combined with sparrow search algorithm.

2.1 Nystrom approximation strategy

With the development of technology, image data are becoming more and more huge. The similarity matrix of an image withP2pixels isp2, which seriously increases the computational load of the computer in the traditional spectral clustering algorithm. It adds many limitations to the application of the spectral clustering algorithm. In order to reduce the complexity of matrix calculation, a new method to solve the eigenvector of similarity matrix was proposed in Ref. [9]. The basic idea is to randomly select samplenfrom population sample and use the similarity between selected samplenand unselected samplemto estimate the similarity between unselected samples. According to this idea, Nystrom strategy to solve the problem of complex calculation process of the traditional spectral clustering algorithm was introduced in Ref. [10]. The specific steps are as follows.

(1)Take 1% randomly fromNsamples, and record it asn.

(2)Calculate the similarity matrixAbetween the selected samplesn. Then calculate the similarity matrixBbetween the selected samples and the unselected samples. Then the final similarity matrixWis

(5)

whereCis the similarity matrix between unselected samples.

(3)Since it is still complex to calculate the similarity between unselected samples,AandBcan be used to estimateC. According toAandB, the approximate estimation of the similarity matrixWis

(6)

2.2 Clustering based on sparrow search algorithm

After calculating the eigenvalues and eigenvectors, the key step is to cluster the characteristic matrix. Traditional spectral clustering usually adoptsk-means clustering algorithm. Its basic idea is to randomly select several samples from the samples as the clustering center, and classify the samples into the nearest cluster according to the distance between each sample and all clustering centers. Then the center of each cluster is calculated according to the samples in the cluster, and the above steps are repeated. This clustering result depends heavily on the selection of the initial clustering center. If the initial clustering center is not selected well, it is often easy to fall into local optimization. Particle swarm optimization algorithm has the characteristics of global optimization. Covic and Lacevic[11]designed a novel global optimization algorithm―wingsuit flying search (WFS), inspired by the popular extreme sport―wingsuit flying. Arora and Singh[12]proposed butterfly optimization algorithm (BOA) that mimiced food search and mating behavior of butterflies to solve global optimization problems. Arora and Anand[13]proposed a new meta-heuristic algorithm which was grasshopper optimization algorithm (GOA). This algorithm introduced chaos theory into the optimization process of GOA so as to accelerate its global convergence speed. Because of the ability of global optimization, these algorithms are also introduced into the field of image segmentation[14-17].

In order to optimize the clustering effect and reduce the dependence on the initial clustering center, sparrow search algorithm is introduced in this paper. Sparrow search algorithm is a new swarm intelligence optimization algorithm in 2020 by simulating the foraging process of sparrows to search the optimization direction[18]. Its foraging process is a kind of discoverer follower models, and a reconnaissance and early warning mechanism is added. In this model, each sparrow represents a solution and has the following three possible behaviors. It can be a discoverer, a participant, or an alarm. The identities of discoverers and followers change dynamically, but the proportion of discoverers and followers in the whole population remains unchanged. Discoverers usually have high energy reserves and are responsible for searching areas with rich food in the population to provide direction for the population. Its energy reserve depends on the fitness value of individual sparrow. In order to obtain higher fitness value, participants will search the location of the discoverer and follow the predator. In the process of predation, some sparrows are randomly selected as scouts to guard. When the danger approaches, they will give up their food. Whether the sparrow is a discoverer or a follower, they will give up their current food and move to a new position.

The location update formula for each generation of discoverers is

(7)

The position update formula of each generation of followers is

(8)

The Scout position is updated as

(9)

Therefore, the process is simplified as follows.

(1)Initialize the population, the number of iterations, the discoverer and the participant ratio.

(2)Calculate the fitness value and sort it.

(3)Use the formula to update the positions of discoverers, entrants and alarm.

(4)Calculate the fitness value and update the sparrow position.

(5)Check whether the exit conditions are met. If not, jump to (2).

On the basis of the sparrow algorithm, the cluster center can be used as the optimization variable of sparrow algorithm, and the fitness function is set as

(10)

whereCiis the clusteri;uiis the center point of the clusteri;kis the number of clusters to be clustered.

The fitness function is consistent with the minimum loss function ofk-means clustering. The sparrow search algorithm is used to find the minimum loss points, and these points are used as the initial clustering points. The specific steps are as follows.

(1)Each row of the characteristic matrix is regarded as a sample.

(2)Randomly sample the data points to be classified as sparrow search clustering candidate points.

(3)The sparrow search algorithm is used to search the cluster points with the minimum loss.

(4)Take these cluster points as the initial cluster points ofk-means clustering.

(5)Usek-means clustering to obtain the final cluster points.

In order to verify the effectiveness of this algorithm, this algorithm and the traditional spectral clustering algorithm are applied to segment the image in the field of clothing and medical images respectively, and the segmentation effect and the performance are compared. In the experiment, the scale parameters were set to be 70, 70, and 30, respectively.

In order to verify the effectiveness of the algorithm, three groups of experiments are designed in Fig. 1. The environment involved in first group is a T-stage show picture under complex light, a dress picture and a static picture. The image segmentation of the algorithm under complex conditions and the effect of preserving style details are investigated, respectively. It can be found by comparing with the traditional spectral clustering algorithm. When the light is complex and the contrast is not strong, this algorithm can still retain some line details, which provides feasibility for contour extraction. In the second group of experiments, the algorithm retains the image information more completely. In the third group of experiments, the algorithm effectively retains the details without obvious contrast, for example the collar, and the segmentation effect is more detailed.

Fig. 1 Experimenton: (a) original image; (b) segmentation result of traditional spectral clustering algorithm; (c) the segmentation result of this proposed algorithm

Based on the study of the traditional spectral clustering algorithm, this paper provides a new clothing segmentation algorithm to deal with the huge data information and get rid of the dependence on the initial value. Nystrom approximation strategy is adopted in the spectral mapping stage to greatly reduce the complex of calculation. Sparrow search algorithm is introduced in the clustering stage to get rid of the dependence on the initial value. Experiments show that this algorithm has stronger stability.

How to improve the similarity matrix, introduce texture location information and eliminate the interference of parameters on the experimental results is the focus of the next work.