# Segmentation of the Fabric Pattern Based on Improved Fruit Fly Optimization Algorithm

Authors: Gang Ding; Xiaoyuan Pei; Yang Yang; Boxiang Huang
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

In order to improve the segmentation performance of the printed fabric pattern, a segmentation criterion based on the 3D maximum entropy which is optimized by an improved fruit fly optimization algorithm is designed. The triple is composed of the gray value of the pixel, the average gray values of the diagonal, and the nondiagonal pixels in the neighbourhood. According to the joint probability of the triple, the 3D entropy of the object and the background areas could be designed. The optimal segmentation threshold is resolved by maximizing the 3D entropy. A hybrid fruit fly optimization algorithm is designed to optimize the 3D entropy function. Chaos search is used to enhance the ergodicity of the fruit fly search, and the crowding degree is introduced to enhance the global searching ability. Experiment results show that the segmentation method based on maximizing the 3D entropy could improve the segmentation performance of the printed fabric pattern and the pattern information could be reserved well. The improved fruit fly algorithm has a higher optimization efficiency, and the optimization time could be reduced to 30 percent of the original algorithm.


---

## Body

## 1. Introduction

Printed fabric pattern segmentation is one of the key technologies in printing and dyeing process [1–3]. It has a direct impact on the accuracy of drawing, hemming, and cloth printing [4]. In actual production, new patterns can be formed by colouring the split pattern, so as to enrich the variety of fabric products [5–8]. At present, there are many common image segmentation methods, for example, segmentation methods based on the edge-extraction operators of Canny and Sobel and segmentation methods based on the clustering analysis of mean shift [9–12]. These methods have been widely used in practical industrial production. However, due to the complex texture structure of the fabric itself, many common image segmentation methods are not ideal in the application of printed fabric pattern segmentation [13]. For example, texture noise will lead to a large number of false edges in segmentation results based on edge extraction, leading to inaccurate segmentation. In addition, due to the spatial distribution of pixels is not fully utilized, the segmentation method based on clustering will lead to wrong segmentation in the case of lack of prior knowledge. The image segmentation method which based on maximum entropy has the advantages of simple implementation and relatively stable segmentation performance. It has been effectively applied in various image-processing fields [14–16]. However, due to the insufficient description of pixel distribution information by one-dimensional entropy, the antinoise performance is poor. Especially, in printed fabric pattern segmentation, it is easy to produce false segmentation because of it is sensitive to texture noise.The performance of image segmentation can be improved by constructing 2D entropy which introduces the average gray value of neighbouring pixels [17, 18]. However, with the increase of information entropy dimension, the calculation of maximum entropy also increases rapidly. It causes the calculation time of segmentation threshold to be too long. It can improve the operation speed by combining intelligent optimization algorithm to solve the maximum entropy. Intelligent optimization algorithms, such as genetic algorithm [19], ant colony algorithm [20], and fish swarm algorithm [21] can be used to solve complex functions. However, the implementation of this kind of optimization method is slightly complex, and there are many parameters to be set in the algorithm, which reduces the convenience of the algorithm. In contrast, the fruit fly algorithm has been widely used in many optimization problems because of its low complexity and small computation. However, the fruit fly algorithm is easy to be precocious and fall into local minima because of its optimization mechanism is too simple. In addition, although the 2D entropy considers the distribution information of pixels and their neighbours, the use of more detailed direction information in neighbourhood pixels is insufficient, which reduces the accuracy of feature description of target and background pixels [22]. The texture noise of the image has some influence on the segmentation result.Compared with the 2D maximum entropy method, the 3D maximum entropy method has better segmentation quality, but the complexity of the algorithm is greatly increased. However, the calculation of entropy still uses the logarithm operation with low efficiency, so the efficiency of the algorithm still has room to rise. In order to improve the segmentation performance of the printed fabric pattern. Based on the 2D entropy of the image, 3D entropy is constructed by integrating the direction information of neighbouring pixels. Fabric pattern segmentation based on maximizing the 3D entropy criterion could improve the segmentation performance of the printed fabric pattern. An improved fruit fly optimization algorithm is designed to optimize the 3D entropy function. This method reduces the computation and increases the image edge. The optimal energy function of the entropy penalty factor is adopted to reduce the loss of effective information. With the help of image segmentation technology of the improved Drosophila optimization algorithm, fabric pattern information can be quickly extracted from the fabric image, which improves the calculation speed and design efficiency of fabric pattern segmentation. Compared with other similar algorithms, this algorithm improves the accuracy of image retrieval and preserves the fabric pattern information more completely.


## 2. Pattern Segmentation of 3D Maximum Entropy

The Gray binary groupi,j is composed of the gray level of the pixel itself and the average gray level of its neighbourhood, and its frequency is expressed as fij. Thus, the 2D entropy can be calculated. According to the principle of maximum entropy, the segmentation threshold can be determined. However, the average gray value of the neighbourhood only reflects the basic spatial distribution information of the pixels, it lacks accurate direction information. Especially, the information description of image edge points is not accurate enough. Texture information mostly has the attributes of edge information. The segmentation criteria based on the 2D maximum entropy have limited ability to suppress texture noise of the fabric pattern. Therefore, considering the neighbourhood direction information, the 3D entropy is designed to realize the automatic segmentation of the fabric pattern.Taking the 3 × 3 neighbourhood as an example, the gray value of the pixel pointx,y and its neighbourhood gray value can be expressed as shown in Table 1.Table 1
Pixel distribution.
g
x
−
1
,
y
−
1
g
x
,
y
−
1
g
x
+
1
,
y
−
1
g
x
−
1
,
y
g
x
,
y
g
x
+
1
,
y
g
x
−
1
,
y
+
1
g
x
,
y
+
1
g
x
+
1
,
y
+
1
Note.gx,y represents the gray value of the pixel point x,y.According to the pixel distribution shown in Figure1, the average gray value in the diagonal direction of the neighbourhood of the pixel x,y is defined as(1)g′x,y=14gx−1,y−1+gx+1,y+1+gx−1,y+1+gx+1,y−1.Figure 1
3D space schematic diagram of the triple.The average gray value of the nondiagonal neighbourhood of a pixelx,y is defined as(2)g″x,y=14gx−1,y+gx+1,y+gx,y−1+gx,y+1.Set the gray level of the image isL and the gray level of g′ and g″ is L too. The gray value of each pixel, the neighbourhood diagonal average gray value, and the neighbourhood nondiagonal average gray value form a gray triple group i,j,andk. The frequency of its occurrence is recorded as fijk. Define the joint probability pijk as(3)pijk=fijkN,where N is the total number of pixels in the image. pijk can be regarded as the normalized 3D histogram in 3D space of pixel gray, neighbourhood diagonal average gray, and neighbourhood nondiagonal average gray which are composed of three-dimensional variables of ij, and k. Let the 3D variable’s value of ij, and k be s, t, and r, respectively, and the 3D space schematic diagram of the triple is shown in Figure 1.The 3D space shown in Figure1 is divided into eight regions. There are two areas on the main diagonal which are A11 and A22. The space range corresponding to the area A11 is 0≤i<s, 0≤j<t, and 0≤k<r. The space range corresponding to the area A22 is s≤i<L, t≤j<L, and r≤k<L. Therefore, areas A11 and A22 can be regarded as the target (or background) area and background (or target) area, respectively.For segmentation thresholdss,t,andr, the probability of areas A11 and A22 can be expressed as(4)P11=∑i=0s−1∑j=0t−1∑k=0r−1pijk,P22=∑i=sL−1∑j=tL−1∑k=rL−1pijk.The entropy ofA11 and A22 can be defined as(5)H11=∑i=0s−1∑j=0t−1∑k=0r−1pijkP11lnpijkP11,H22=∑i=sL−1∑j=tL−1∑k=rL−1pijkP22lnpijkP22.Therefore, the 3D entropy can be defined as(6)Hs,t,r=H11+H22.The threshold segmentation method based on the maximum 3D entropy is used to get the best segmentation thresholds∗, t∗, and r∗. In this way, the 3D entropy H of the target and background region of the image can be maximized.With the increase of dimension, the computational complexity of solving the 3D entropy of image increases. In order to meet the needs of fast solution, this paper proposes an improved fruit fly algorithm to solve the 3D entropy function of the above image.


## 3. Improved Fruit fly Algorithm

At present, the optimization calculation method develops rapidly, including genetic algorithm, ant colony algorithm, fish swarm algorithm, and fruit fly algorithm. All of these algorithms belong to the population optimization algorithm and have strong optimization computing ability. The difference is that the heuristic search mechanism used by various methods is different. For example, the genetic algorithm is used to use genetic operations such as “copy, select, cross, and mutation” in the genetic process to achieve optimal calculation. The ant colony algorithm is based on the principle of pheromone positive feedback in the process of ant foraging. The fish swarm algorithm is based on the behaviour of “foraging, tail chasing, and clustering” in the process of fish foraging. The algorithm of fruit fly is based on the heuristic mechanism of foraging.Although the heuristic mechanism of different optimization algorithms is different, there is a common problem that the algorithm is prone to the premature phenomenon. That is to say, the algorithm is easy to fall into local minima, resulting in the decline of global optimization ability. In order to improve the global optimization performance, a hybrid optimization method with combining the optimization methods of different mechanisms to construct the complementary optimization mechanism is proposed in this paper.In the algorithm of fruit fly, fruit fly individuals can quickly gather to the optimal individual through visual search. The random search near the optimal individual is realized by using olfactory search. The two search methods can be used alternately, and finally the fruit fly can gather to the food source. The concentration evaluation function in the algorithm is the function to be optimized, that is, the 3D entropy corresponding to formula (6). The location of the optimized individual in the ant colony algorithm and fish swarm algorithm is the optimal solution. However, the position of fruit fly does not directly correspond to the optimization solution in the fruit fly algorithm. Its concentration value corresponds to the optimization solution of the optimization function.The fruit fly algorithm is simple in mechanism, small in calculation, and easy to realize. In addition, the population can approach the optimal individual quickly, so as to ensure the algorithm has fast convergence. However, due to the fruit fly individuals concentrated in the vicinity of the optimal individuals for random search, it will lead to the premature phenomenon of the algorithm, thus reducing the global optimization ability of the algorithm. In this paper, an improved fruit fly hybrid optimization algorithm is designed based on the fruit fly algorithm and combined with chaos search and the optimization mechanism of the fish swarm algorithm.In the fruit fly algorithm, the fruit fly individual searches randomly near the optimal individual, and the search direction and position are generated by the random number generator. Random search is easy to produce the phenomenon of repeated search, which will reduce the search efficiency. Chaos search has the characteristics of ergodic search [18], which can directly overcome the shortcomings of random search. Therefore, this paper proposes an improved strategy of chaos search instead of individual random search of fruit fly.In addition, all the fruit flies in the algorithm have the same behaviour criterion and gather near the food source, which reduces the global optimization performance of the algorithm. In the fish swarm algorithm, artificial fish has similar behaviour in the process of foraging. However, the concept of crowding degree is set in the fish swarm algorithm, that is, the artificial fish cannot gather in the same place too much to prevent the algorithm from converging too fast. In this paper, the concept of crowding degree in the artificial fish swarm algorithm is introduced into the fruit fly algorithm which makes fruit fly no longer have a single behaviour criterion, but choose to search near the optimal individual with a large probability, and search globally with a small probability, so as to improve the global optimization performance of the algorithm.The above improved algorithm is described as follows:Step 1: Initialize parameters.Initialize the parameters involved in the fruit fly optimization algorithm, including maximum number of iterationsMaxGen, population size of fruit fly Size, and initial optimal position of fruit fly x_best and y_best, and set the initial congestion probability value p.Step 2: Set up the mechanism of chaos.There are many kinds of chaos-generating functions; among which, thelogistic map is one of the most commonly used functions, which is simple in form and easy to realize. In this paper, the logistic map is chosen as the mechanism of chaos sequence:(7)zxn+1=μ⋅zxn⋅1−zxn,(8)zyn+1=μ⋅zyn⋅1−zyn.Whenμ = 4, the above mapping is a chaotic full mapping. After the initial value is selected, the value after 2000 iterations of formula (7) and formula (8) is obtained as the initial value of chaos in the fruit fly algorithm so that the effect of the initial value of chaos generation mechanism on search process can be eliminated.Step 3: Set the random search direction of fruit fly.Theith fruit fly in the population has two search directions. The random number r between 0,1 is generated by the random number generator.Ifr<p, then initialize x_axis and y_axis randomly and set the chaos search direction of the ith fruit fly near the x_axis andy_axis position; that is,(9)xi=x_axis+γzx−0.5,yi=y_axis+γzy−0.5,wherezx and zy are chaotic variables generated by formula (7) and formula (8) and γ is the coefficient of search range.Ifr≥p, set the random search direction of the ith fruit fly near the x_best andy_best position; that is,(10)xi=x_best+γzx−0.5,yi=y_best+γzy−0.5.Step 4: Calculate the concentration judgment value. The distanceDisti between the position of ith fruit fly and the origin is calculated:(11)Disti=xi2+yi2.Calculate the concentration judgment valueSi according to the distance:(12)Si=1Disti.Step 5: Calculate concentrationSmelli of the ith fruit fly. The concentration function fit is the optimization function, so the concentration value of the ith fruit fly is(13)Smelli=fitSi.Step 6: Keep the current optimal individual. Keep the fruit fly with the highest odor concentration as the current optimal individual:(14)bestSmell,bestindex=minSmelli,wherebestindex is the index number of the optimal individual and bestSmell is the concentration value of the optimal individual.Step 7: Save the optimal concentration and coordinates. Save the concentration valuebestSmell of the optimal individual and its location coordinate. Command the fruit flies to fly to this position quickly by visual perception:(15)Smell_best=bestSmell,x_best=xbestindex,y_best=ybestindex.x_best andy_best is considered as the optimal initial position for the next optimization. And reduce the probability of congestion:(16)p=λ⋅p,whereλ is the probability attenuation coefficient of crowding degree (0<λ<1).Step 8: Iterative optimization. Repeat steps 3 to 6 and determine whether the current optimal concentration has been updated.If yes, perform step 7; if no, repeat steps 3 to 6 directly until the specified number of iterations is reached or the algorithm converges.The improved fruit fly algorithm proposed in this paper combines chaos ergodic search and the concept of crowding degree of the fish swarm algorithm. It can overcome the shortcomings of the traditional fruit fly algorithm, such as low efficiency of random search, the fruit fly individuals are all concentrated in the optimal individuals, and it is easy to fall into local minima, which is conducive to improving the global optimization performance of the algorithm. In the improved algorithm, the initial stage of crowding probability can be set to a larger probability value, so as to ensure that individual fruit flies can conduct sufficient random search, try to find the best position in the global range, increase the dispersion of individual flies, and help to overcome the premature phenomenon of the population. At the same time, chaos search mechanism can improve the ergodicity of algorithm search, reduce the number of repeated searches, and improve the search efficiency. With the progress of the search process, the probability of crowding degree decreases gradually, the probability of fruit fly individual swarm to the optimal location increases, and the number of searches near the optimal location increases, which can ensure that the algorithm has good convergence characteristics and stability.When the fruit fly algorithm is used to determine the threshold value of image segmentation, the three threshold variables ofs, t, and r are encoded to determine the corresponding concentration value. The 3D entropy of formula (6) is used as the evaluation function of the concentration. After iterative calculation, the optimal solution of the maximum entropy can be completed.


## 4. Experimental Results and Analysis

The maximum 3D entropy proposed in this paper is used to segment the printed fabric pattern and is compared with the maximum 1D and 2D entropy. The segmentation result of a single pattern is shown in Figure2.Figure 2
Segmentation result of a single pattern. (a) Original image; (b) 1D maximum entropy; (c) 2D maximum entropyt2=175; (d) 3D maximum entropy t3=183.
(a)
(b)
(c)
(d)Figure2(a) shows the original image, the segmentation threshold t1=166 is obtained by maximum 1D entropy. The segmentation result is shown in Figure 2(b). The outline of pattern segmentation is incomplete, and a lot of basic information of the pattern is lost. The maximum 2D entropy is used to obtain the segmentation threshold t2=175, and the segmentation result is shown in Figure 2(c). Although the basic contour of the pattern can be preserved in the segmentation result, the contour is not complete. Especially, the segmentation result of the small cross in the figure has a large distortion. The maximum 3D entropy is used to obtain the segmentation threshold t3=183, and the segmentation result is shown in Figure 2(d). The result of pattern segmentation has been improved obviously, the contour information is complete, and the information of each part of the pattern can be displayed clearly.It can be seen that by expanding the dimension of image entropy and considering the direction information of pixel neighbourhood, the accuracy of feature description of target and background pixels can be improved, and the segmentation effect of printed fabric pattern can also be improved.The segmentation result of the combination pattern is shown in Figure3.Figure 3
Segmentation result of the combination pattern. (a) Original image; (b) 1D maximum entropyt1=164; (c) 2D maximum entropy t2=168; (d) 3D maximum entropy t3=204.
(a)
(b)
(c)
(d)Figure3(a) shows the original image, which is composed of six patterns, it makes the composition of the printed fabric pattern complex and increases the difficulty of threshold segmentation. Figure 3(b) shows the segmentation result obtained by using the maximum 1D entropy, and the segmentation threshold is t1=164. In the segmentation result, the segmentation effect of the second and third patterns is not ideal. The external edge information of the second pattern is lost to some extent, and the third pattern has obvious error segmentation. Figure 3(c) is the segmentation result obtained by using the maximum 2D entropy, and its segmentation threshold is t2=168. It can be seen from the segmentation results that the segmentation results of fabric patterns are improved when the distribution information of neighbouring pixels is taken into account. For example, the edge segmentation effect of the second pattern is improved, but the segmentation result of the third pattern is not obviously improved, and the main shape of the pattern cannot be segmented. Figure 3(d) shows the segmentation result obtained by using the maximum 3D entropy, and the segmentation threshold is t3=204. It can be seen from the segmentation results that the segmentation results of fabric patterns can be further improved when considering the direction distribution information of neighbouring pixels. The second pattern has a complete edge segmentation, while the third pattern can also segment the basic shape, and the overall pattern segmentation performance has been significantly improved.These algorithms, including the chaos optimization algorithm, fish swarm algorithm, fruit fly algorithm, and improved fruit fly algorithm, proposed in this paper can be used to optimize the threshold value of fabric pattern segmentation. The time comparison of various optimization algorithms is shown in Table2.Table 2
Time comparison of various optimization algorithms.
Fabric pattern
Chaos optimization (s)
Fish swarm algorithm (s)
Fruit fly algorithm (s)
Improved algorithm (s)
Single pattern
5.231
4.212
3.013
0.966
Combination pattern
5.692
5.028
3.742
1.023It can be seen from Table2 that since the chaos optimization algorithm belongs to the serial optimization algorithm, only one solution of optimization space can be searched in each iteration. Compared with the parallel population optimization algorithm, the efficiency is lower. Compared with the fruit fly algorithm, the fish swarm algorithm has more rules and less efficiency. On the basis of keeping the simple rules and high efficiency of the original algorithm, combined with chaos search mechanism, the improved fruit fly algorithm improves the ergodicity of individual search, combined with crowding degree restriction mechanism of fish swarm, improves the global search ability of fruit fly, so it has faster optimization efficiency, less than 30% of the original fruit fly algorithm.


## 5. Conclusions

Considering the direction information of the neighbourhood of the fabric image pixel, the 3D entropy is designed for the segmentation of the printed fabric pattern, and the threshold segmentation of the fabric pattern based on the maximum 3D entropy is realized. In order to improve the optimization efficiency of the maximum 3D entropy, combining the chaos search mechanism and the crowding degree strategy of the fish swarm algorithm, an improved fruit fly optimization algorithm is proposed, which improves the ergodicity and global optimization performance of the algorithm. The experimental results show that the improved optimization algorithm has higher search efficiency and can complete the threshold optimization of 3D maximum entropy. The result of the printed fabric pattern segmentation based on the maximum 3D entropy can realize the complete segmentation of the fabric pattern and can effectively suppress the influence of texture noise on the segmentation result.



---

*Source: 9534392-2020-05-18.xml*