Automatic machine embroidery image color analysis system,part II: Application of the genetic algorithm in search of a repetitive pattern image

Abstract

This series of studies proposed an automatic machine embroidery image color analysis system. Based on the machine embroidery image color separation system proposed in part I of this series of papers (Kuo CFJ, Jian BJ and Wu HC. Automatic machine embroidery image color analysis system, part I: using Gustafson-Kessel clustering algorithm in embroidery fabric color separation. Textil Res J 2011, submitted for publication), this paper presents an automatic repetitive pattern image recognition algorithm for machine embroidery. Firstly, the image pre-processing is implemented to eliminate image acquisition noise and smooth the texture of machine embroidery. After the completion of image pre-processing, the genetic algorithm (GA) is applied to obtain the color image of repetitive patterns. The novel fitness function proposed in this paper can increase the calculation of the color entropy value to improve the measurement block accuracy of color similarity in previous literature. When applied to the GA, the system can accurately identify and cut out images of repetitive patterns. In addition, since the proposed fitness function has been normalized, it can accurately calculate the optimal target function, indicating that the proposed algorithm can automatically and accurately identify and cut out the images of repetitive patterns in machine embroidery.

Keywords

genetic algorithm entropy value repetitive pattern

Introduction

Machine embroidery techniques are generally used for large-scale fabric production, and repetitive patterns are used to enrich the colors of the fabric. To recognize repetitive patterns in drafting, the images of repetitive patterns are usually judged by human eyes, and then separated; however, because embroidery products vary, recognition of patterns requires professionals, and is a time-consuming and laborious process. Hence, automatic computerized recognition of repetitive patterns and image separation is an important topic. This paper explored the algorithm for the automatic cutting of machine embroidery repetitive pattern images.

At present, template matching and the genetic algorithm (GA) are the main methods for the recognition of repetitive patterns in images. Template matching¹ can effectively recognize the repetitive patterns. Mattoccia et al.² proposed the baseband domain fast template matching method by using the enhanced bounded correlation coefficient to recognize the repetitive patterns. However, template matching requires the manual setting of the template, which makes it unsuitable for automatic acquisition of repetitive pattern images. Kuo et al.³^–⁵ and Kuo and Shih⁶ used the GA to find images of repetitive patterns of color similarity and area ratio characteristic without setting up the matching template. However, this may sometimes lead to misjudgment despite the above-mentioned advantage. This paper used the GA to determine the images of repetitive patterns. To overcome the problem of misjudgment of the GA in recognition of repetitive patterns, this paper proposed a novel fitness function that can be effectively applied in the automatic separation of machine embroidery repetitive patterns.

Research framework

The architecture of this paper is as shown in Figure 1. The experimental equipment included a Model EPSON PERFECTION 1650 scanner for image acquisition and MATLAB 7.12.0 and Visual C++ 6.0 software for hybrid compilation of programming, Visual C++ for writing the GA and MATLAB for operational image display. Firstly, a scanner was used to acquire the image of the embroidery fabric, and the image pre-processing method proposed in part I⁷ was applied to eliminate image noise and smooth the texture of the fabric. Next, this paper used the GA to determine the repetitive patterns, and proposed a novel fitness function to compare with the traditional fitness function for search of the repetitive images³^–⁶ in terms of repetitive pattern segmentation results.

Research method

Hue, saturation and intensity color system

The traditional fitness function for search of repetitive images³^–⁶ adopts the hue, saturation and intensity (HSI) color system of 113 colors by quantification in color similarity measurement. The HSI color system can be converted from the red, green, blue (RGB) color system,⁸ as shown below:

(1)

(2)

(3)

(4)

where H is hue, S is saturation and I is intensity.

Hue, saturation and value color system

The color similarity measurement of the novel fitness function for the GA proposed in this paper uses the hue, saturation and value (HSV) color system of 256 colors by quantification. The HSV color system is similar to the HSI color system, as shown in Figure 2, with the difference of changing intensity I into the color value. The HSV color system can be converted from the RGB color system, and its hue H and saturation S are the same with those of the HSI color system. The conversion of color value V is expressed as

(5)

Color similarity measurement

Swain and Ballard⁹ proposed the histogram intersection method by using a histogram to calculate the number of pixels of colors to obtain histogram. With anti-rotation and anti-translation characteristics, it can be used to measure the color similarity of two images. After Shih¹⁰ used the HSI color system to calculate and measure color similarity by segmentation of 113 blocks, where I of the HSI color system of a pure color is equal to the lightness of a medium gray-white. In order to naturally describe the embroidery color, this paper proposed using the HSV color system to completely express the embroidery color, where the V of HSV of pure color is equal to the brightness of white.⁸ This paper attempted to use the HSV color system for the calculation and measurement of color similarity by quantitative interval segmentation into 256 blocks of 16 grades of H-component, 4 grades of S-component and 4 grades of V-component. The 256 blocks were numbered 1–256. The histogram of each image was obtained by the color membership block. Finally, the histogram intersection method was applied in the color similarity measurement and calculation. The value of color similarity was defined as

(6)

where CS is the value of color similarity (range 0–1, higher similarity when the value is approaching 1),

H (I_{Q}, j)

is the j th bar value of the sub-image histogram

(I_{Q})

H (I_{D}, j)

is the j th bar value of the original image histogram

(I_{D})

and n is the total number of color encodings.

Image entropy value theory

The information theory to define the information change level proposed by Shannon¹¹ is termed the information entropy. The information theory is applied to a gray-scale image and the image information can be expressed by the following:¹²

(7)

where N_i is the number of image pixels of strength at i and N_s is the total number of image pixels. The RGB component is input into the above equation to obtain the color image entropy value by the average of the calculation additional results. The entropy value can represent the average information amount of the color image. This paper uses the color image entropy value as the eigenvalue for parameters of GA fitness function, with which we expect to more accurately locate and determine image repetitive patterns.

Genetic algorithm

Proposed by John Holland,¹³ the GA is a function optimization method based on biological evolution procedure. The general optimal solution finding methods include the traditional method of point method and the random method.¹⁴ The point method tests all possible solutions to find the optimal solution. As a modification of the point method, the random method randomly produces possible solutions and finds the possible solutions by relevant information before determining the optimal solution. This paper uses the GA to determine repetitive patterns. The procedure is as shown in Figure 1. To effectively improve the recognition rate of repetitive patterns, this paper proposes the novel fitness function for the GA, and compares it with the fitness functions discussed in previous literature³^–⁶ in order to verify the accuracy of applying the novel fitness function in the recognition of repetitive patterns.

Figure 1.

Research framework.

Figure 2.

Hue, saturation and value (HSV) color system.

Gene encoding and decoding

The processing of GA parameter variables requires the encoding of the range of parameter setting to facilitate follow-up reproduction mechanism, crossover mechanism and mutation mechanism. After the computation of the GA, the decoding should be conducted. This paper uses the binary encoding and decoding to set the variables of the repetitive pattern images in the X and Y axes as Coordinate_X and Coordinate_Y. After the encoding, the coordinates transfer from decimal to binary: Coordinate_X and Coordinate_Y occupy nine bits each. The width and height of the original image of repetitive patterns are set as Width_X and Height_Y and the coordinates transfer from decimal to binary: the Width_X and Height_Y occupy seven bits each. Then repetitive pattern images of position, length and width are combined into a gene encoding set; hence, the gene encoding of each species has 32 codes;⁶ the gene encoding set is as shown in Figure 3. The gene decoding is converted from binary back to decimal.

Figure 3.

The gene encoding set.

Fitness function

The fitness function is the performance indicator of the GA. The performance of each generation after the change in genes is measured by fitness function calculation. In general, a higher fitness value represents better species quality and a higher chance of being selected. On the contrary, a lower fitness function value represents a greater opportunity of being eliminated. Shih¹⁰ used the fitness function in search of a repetitive pattern image with the following equation:

(8)

where E is the fitness function, CS is the color similarity of the two images by histogram intersection of HIS histogram of 113 colors and P is the area ratio of the original image divided by the sub-image.

This paper proposed a novel fitness function for the application in the GA to search for the repetitive patterns of machine embroidery, and the equation is as follows:

(9)

where

{CS}_{new}

is the color similarity of the two images obtained from the histogram intersection by using the HSV histogram of 256 colors. SI_Q is the original image area (in pixels), SI_D is the sub-image area (in pixels), EI_Q is the entropy value of the original color image and EI_D is the entropy value of the color sub-image. The numerical analysis of the novel fitness function proposed in this paper can be divided into three steps.

Step 1: the numerical analysis of color similarity, and the maximal and minimal value range of color similarity can be known as [0, 1].

Step 2: the numerical analysis of image area ratio. The division of the original image area by the area of sub-image is the area ratio. The minimal area ratio is 1 when the original image area equals the area of the sub-image, and the area ratio is the maximal when the sub-image area is 1. Hence, the maximal value of area ratio equals the original image area. To ensure that the results fall in the range of [0, 1], the following maximal and minimal normalization equation is used:

(10)

where

v^{'}

is the value after normalization, v is the original value,

max_{A}

is the maximal value of v,

min_{A}

is the minimal value of v,

{new}_{max_{A}}

is the maximal value of the range after normalization and

{new}_{min_{A}}

is the minimal value after normalization. According to the area ratio characteristic, the maximal area ratio is the area of the original image and the minimal value is 1. The maximal value after normalization is 1 and the minimal value after normalization is 0. The calculation results of inputting them into the maximal and minimal normalization equations are included into the definition of fitness function as below:

(11)

Step 3: the inference from information theory to image. Since this paper stores the image color components by 8-bit codes, the maximal entropy value is 8 and the minimal value is 0. To obtain more accurately the detailed information of images to reflect different results by considering details and the entropy value of the original image, this paper uses the moderate entropy definition proposed by Zhang¹⁵ as below:

(12)

where E_C is the moderated entropy, E_N is the information entropy of the entire image and E_L is the information entropy of local image. In the above equation, the maximal E_C value is 8 and the minimal value is 0. This paper normalizes the range from [0, 8] to [0, 1] according to the principle of moderate entropy by replacing coefficient 2 with coefficient 0.25, as shown below:

(13)

By the numerical analysis of the above fitness function, we define the target function J as the reciprocal of the fitness function, as shown below:

(14)

Since the proposed fitness function is the result of normalization, the maximal value of the fitness function is 3 and the minimal value is 0, and the optimal target function value is 1/3.

Reproduction mechanism

The process of producing novel generations of strong vitality by selection is known as the reproduction mechanism. Proposed by Holland,¹³ roulette wheel selection regards each gene as a block of the roulette, and determines its reproduction probability according to the ratio of each individual’s fitness function value in the total addition of the fitness function value. As shown in Figure 4, the one with higher fitness function value has a higher probability of reproduction, and vice versa. The equation is as follows:

(15)

where N_i is the number of i th species that will be reproduced, f_i is the fitness function value of i th species, N is the total number of each species and

\sum f_{i}

is the addition of the overall species fitness function values.

Figure 4.

Roulette wheel selection method.

The competitive selection and roulette wheel selection methods are basically the same. However, the competitive selection method has an additional pair of individuals according to the roulette wheel selection for competition. The individuals of high fitness function values will be selected until satisfaction. The error of the competitive selection method will be smaller than that of the roulette wheel selection method. Hence, this paper uses the competitive selection algorithm to reduce the error of the roulette wheel selection method.

Crossover mechanism

The crossover mechanism randomly selects two gene series from the population for bit information exchange to produce new gene series. Namely, it randomly selects two parent populations to generate the offspring population by combination. The offspring population includes parts of the characteristics of the parental populations to get offspring populations of higher fitness function value. Hence, this paper adopts the single-point crossover method to randomly select from the populations two individuals as the parental gene series. Then, it randomly selects a point, and the gene series to the right of the point can exchange information to create new offspring. The single-point crossover is as shown in Figure 5.

Figure 5.

Single-point crossover.

Mutation mechanism

The mutation mechanism is mainly used to avoid the local optimal solution of the GA, and hence it has to produce new species. The mutation mechanism will carry out mutation by determining the individual gene bit according to probability. The single-point mutation is to randomly select a bit from the gene series and change it by supplemented operation, as shown in Figure 6.

Figure 6.

Random single-point mutation.

Experiment results and discussion

The purpose of this experiment is to verify and discuss the application of the proposed fitness function in the GA to obtain the repetitive patterns and compare them with the traditional fitness function for searching for repetitive images.³ This paper used two originally identical images with repetitive patterns of cherries (Sample 1) and penguins (Sample 2), as shown in Figures 7 and 8, respectively. The image pre-processing, as previously described, eliminated the image noise and smoothed the texture, as shown in Figures 9 and 10, to determine the color repetitive image performance by the GA for comparison.

Figure 7.

Original image of Sample 1, sized 600 × 346 pixels.

Figure 8.

Original image of Sample 2, sized 600 × 266 pixels.

Figure 9.

Pre-processed image (Sample 1).

Figure 10.

Pre-processed image (Sample 2).

Regarding the differences of the proposed novel fitness function and traditional fitness functions mentioned in related literature,³^–⁶ this paper adopted the HSV color system of 256 blocks to calculate the color similarity. The results showed that the method produced higher color accuracy than that of the HSI color system of 113 blocks. It also increased its image information entropy value to determine the image details to more accurately find the repetitive patterns. The gene convergence graphs based on the original fitness function in the GA of Sample 1 and Sample 2 are as shown in Figures 11 and 12, respectively. The gene convergence graphs of using the novel fitness function in the GA is as shown in Figures 13 and 14. The comparison of the gene convergence graphs indicates that the novel fitness function can converge faster, and find the repetitive patterns quicker. The search results on the repetitive patterns of Sample 1, as shown in Figures 15 and 16, indicate that the original fitness function cannot segment the entire cherry pattern. The proposed fitness function can effectively select the repetitive patterns and cut out the entire cherry pattern. The search results on the repetitive patterns of Sample 2, as shown in Figures 17 and 18, are similar to the results of Sample 1. The original fitness function cannot correctly cut out the entire penguin pattern, while the novel fitness function can effectively select the repetitive patterns and cut out the penguin pattern completely. The results confirm that the novel fitness function gives better performance.

Figure 11.

Original fitness function gene convergence graph (Sample 1).

Figure 12.

Original fitness function gene convergence graph (Sample 2).

Figure 13.

Novel fitness function gene convergence graph (Sample 1).

Figure 14.

Novel fitness function gene convergence graph (Sample 2).

Figure 15.

Repetitive patterns found by the original fitness function, sized 150 × 190 pixel (Sample 1).

Figure 16.

Repetitive patterns found by the novel fitness function, sized 253 × 190 pixels (Sample 1).

Figure 17.

Repetitive patterns found by the original fitness function, sized 150 × 190 pixels (Sample 2).

Figure 18.

Repetitive patterns found by the novel fitness function, sized 207 × 190 pixels (Sample 2).

Conclusions

This paper proposed a novel fitness function for the application in the GA to find the images of repetitive patterns, and discussed the effect of repetitive pattern image identification. The experimental results indicated that the traditional method of using the GA in identifying the repetitive pattern images requires longer convergence time. This paper used the competitive selection method of the GA to shorten calculation time and identify the images of repetitive images more accurately. Meanwhile, the novel fitness function has been normalized and, thus, it can calculate the results of the optimal target function more accurately, in order to avoid misjudgment of the GA in search of repetitive patterns. The machine embroidery automatic repetitive pattern image search system can be integrated with automatic manufacturing equipment to improve the automation of machine embroidery.

Footnotes

Funding

The research was supported by the National Science Council of the Republic of China (grant No. 97-2221-E-011-030-MY3).

References

Schalkoff

. Digital image processing and computer vision, 1st edn. New York: John Wiley & Sons Inc, 1989; 279–286.

Mattoccia

Tombari

Di Stefano

. Fast full-search equivalent template matching by enhanced bounded correlation. IEEE Trans Image Process 2008; 17: 528–538.

Kuo

CFJ

Huang

. Computerized color separation system for printed fabrics by using backward-propagation neural network. Fibers Polym 2007; 8: 529–536.

Kuo

CFJ

Huang

. Computerized color distinguishing system for color printed fabric by using the approach of probabilistic neural network. Polym Plast Technol Eng 2008; 47: 264–272.

Kuo

CFJ

Hsu

CTM

Shih

. Automatic pattern recognition and color separation of embroidery fabric. Textil Res J 2011; 81: 1145–1157.

Kuo

CFJ

Shih

. Printed fabric computerized automatic color separating system. Textil Res J 2010; 81: 706–713.

Kuo CFJ, Jian BJ, Wu HC and Peng KC. Automatic machine embroidery image color analysis system, part I: using Gustafson-Kessel clustering algorithm in embroidery fabric color separation. Textil Res J 2012, Accepted for publication. (DOI: 10.1177/0040517511435012).

Plataniotis

Venetsanopoulos

. Color image processing and applications, 1st edn. New York: Springer, 2000; 9–13.

Swain

Ballard

. Color indexing. Int J Comput Vision 1991; 7: 11–32.

10.

Shih CY. Polymer engineering, the automatic image analysis system for printed fabrics. PhD Thesis, National Taiwan University of Science and Technology, 2006.

11.

Shannon CE. A mathematical theory of communication. Bell system Technical Journal 1948; 27: 379–423.

12.

Hummel

. Histogram modification techniques. Comput Graph Image Process 1974; 4: 209–224.

13.

Holland

. Adaptation in natural and artificial systems. Ann Arbor, MI: The University of Michigan Press, 1975.

14.

Tsutsui

Ghosh

. Genetic algorithms with a robust solution searching scheme. IEEE Trans Evol Comput 1997; 1: 201–208.

15.

Zhang L. Signal and information processing, analysis of feature of target based on double infrared bands image and research of method of fusion. Master’s Thesis, North University of China, 2007.