Oil painting algorithm based on aesthetic criteria of genetic algorithm during COVID-19
Abstract
Under the influence of novel coronavirus pneumonia, the traditional manual oil painting creation has put forward higher requirements. The disadvantages of traditional hand drawing are very obvious: tedious, inconvenient to modify and save, slow speed of painting, which can no longer meet the requirements of social development. In this paper, the fitness of oil painting function is discussed. Through the analysis of the experimental results, it is found that this method has important reference value for optimizing algorithm and improving traditional hand drawing during COVID-19.
1Introduction
On February 17, 2020, the Chinese Center for Disease Control and Prevention (CDC) released the largest epidemiological analysis of new corona virus pneumonia to date. Under the influence of novel corona virus pneumonia epidemic, the traditional manual oil painting creation has put forward higher requirements. Graph is a very widely used data structure, which can directly and accurately represent all kinds of complex system models. Among them, the vertex represents the elements of the system, and the edge represents the relationship between the elements [1]. It has important theoretical significance and practical application value to draw the graph structure beautifully and neatly into a limited area of two-dimensional or three-dimensional space [2, 3]. It is used in information visualization and graphic users Interface design, software engineering, VLSI layout, circuit wiring, network management and so on are widely used [4]. Generally, the graph structure can be divided into tree, plane graph, general undirected graph and general directed graph. There are many graph drawing algorithms for various graph structures, among which plane graph drawing algorithm is one of the important algorithms, which has been studied deeply by many scholars, However, the existing algorithms of plane graph are complex and hard to understand [5–7]. It is an urgent problem to find a simple and efficient algorithm of plane graph drawing. In recent years, some people use genetic algorithm to draw trees and general undirected graph, but the references of domestic and foreign genetic algorithm to draw plane graph are rare. In this paper, genetic algorithm is used to realize automatic plane graph drawing [8].
In addition, the study of drawing algorithm can avoid the disadvantages of traditional manual drawing. On the one hand, it can draw a variety of images with complex structure orderly and aesthetically, especially to deal with some edges and corners accurately [9, 10]. On the other hand, it can greatly save time and energy and improve drawing efficiency. By constructing the framework of genetic algorithm and determining the coding scheme, a complete set of operation scheme is designed. The experimental results show that this method is easy to realize, and the drawing is more beautiful, with the advantages of high standard and high efficiency.
2The research status of drawing problems
In recent years, drawing has attracted more and more attention. Since 1992, there has been an international academic seminar on drawing held every year [11]. In the past ten years, the research on drawing has made great progress in drawing algorithm, system and application [12]. A large number of academic papers on drawing algorithm have been published. Document is a good overview of drawing. More than 300 references have been listed in the paper, and many research and commercial automatic drawing tools and systems have also emerged [13]. The main concerns are:
(1) What factors affect whether the effect of drawing is satisfactory.
(2) How to draw a picture automatically and aesthetically.
(3) The application of drawing technology in practical engineering.
The study of drawing can be divided into two aspects: Theory and application. The theoretical research mainly includes:
(1) In this paper, we study the combinatorial properties and representation of graphs. Strictly speaking, the study of the characteristics of a graph does not belong to the category of drawing, but it is necessary to study it. First, we have said that graph is the direct abstraction of information, and drawing is the representation of information. If the graph itself can not accurately reflect the information, even if the graph is drawn well, it is meaningless; secondly, when designing the drawing algorithm, we need to consider the characteristics and uses of the graph. Generally speaking, different drawings have different aesthetic requirements. And even for the same structure, different drawing methods are needed to meet the special requirements of their own applications. There is an interactive relationship between drawing and drawing.
Some scholars have done some research in this field and put forward some new graph structures, such as combination graph, cluster graph and so on. The characteristic of composite graph is that it contains two types of edges: the edge of containing relation and the edge of adjacent relation; the characteristic of cluster graph is that there are big differences in the internal structure between the components of graph, so it is not suitable to use the overall aesthetic criteria to guide the drawing. In view of these new drawing structures, some new drawing ideas are put forward. For example, for cluster graph, there are meta drawing methods.
(2) Analyze people’s aesthetic psychology and study what kind of aesthetic standards or painting methods can better meet people’s needs. We have mentioned that the aesthetic criteria is the goal of the drawing algorithm. Therefore, before we start to design the algorithm, we must first make clear which aesthetic criteria to meet. It’s not easy to choose a set of appropriate aesthetic criteria. One is that it’s difficult to abstract the appropriate graph structure model from the specific application problems. The other is that it’s a very subjective problem about “what kind of graph is more beautiful”. Different applications have different aesthetic requirements. For example, in the study of graph theory, the vertex of a graph is generally drawn as a circle or an ellipse. Therefore, according to the purpose of application, it is the premise of designing effective drawing algorithm to formulate appropriate aesthetic criteria.
(3) According to the characteristics and aesthetic criteria of the drawing, an effective drawing algorithm is designed. This is the main task of drawing. Generally speaking, there are different drawing algorithms for different types of graphs, such as tree drawing, plane drawing, directed drawing and undirected drawing. In each class of graphs, there are different algorithms according to the characteristics of graphs and the corresponding aesthetic criteria. In order to design a good drawing algorithm, it is necessary to consider not only the type of drawing, drawing standards and aesthetic criteria, but also the time efficiency of the algorithm. It is very difficult to design a fast and good algorithm for drawing. Sometimes, we need to make a trade-off between the time efficiency of the algorithm and the drawing effect.
In the aspect of application, we mainly use drawing algorithm to develop a practical drawing tool or system with human-computer interaction function. The biggest difference between the development system and the pure research of drawing algorithm is that the system allows people to participate in the process of drawing interactively, in order to draw a better picture. Therefore, the research of “dynamic drawing algorithm” based on human-computer interaction technology also came into being.
At present, people have developed some drawing systems, some of which have simple functions, some of which have powerful functions, some of which are specially developed for specific fields, and some of which have a wide range of application fields.
3Basic terms
Set G = <V, E > It is a undirected graph. If G can draw any two edges on a plane so that they do not intersect except for the endpoints, it is called a plane graph. A plane straight line drawing method of plane graph G is such a drawing method, which maps the vertices in G to the points on a plane, and the edges in G to the straight lines connected with two endpoints on a plane, so that the images of any two edges do not intersect except for the endpoints. For example figure G1 shown in Fig. 1(a) is a plan, and its plan line drawing method is shown in Fig. 1(b).
Fig. 1
Setting for the figure template.
When people draw pictures, they often need to consider certain aesthetic criteria. The commonly used aesthetic criteria are as follows:
(4) Maximizing the minimum angle of an edge associated with the same vertex.
(5) Minimize the number of intersections between edges.
(6) Too large or too small aspect ratio is not good.
(7) Try to make the sides as long as possible.
(8) On the premise that the distance between any two vertices of the drawn graph is not less than the specified minimum value, the sum of the lengths of all edges in the graph is minimized.
(9) On the premise that the distance between any two vertices of the drawn graph is not less than the specified minimum value, the area of the graph is minimized.
(10) the internal symmetry of graph.
The graph drawing algorithm in this paper will design the objective function according to the criteria (1) - (5), but the results of the algorithm also basically meet the criteria (6) and (7).
4Drawing algorithm of plane straight line based on genetic algorithm
Genetic algorithm is widely used in function optimization and other fields. The method of drawing plane with genetic algorithm is to convert the drawing problem into the constrained optimization problem, that is, to calculate a certain area with The minimum or maximum value of the function of the constraint condition. Obviously, the constraint condition here is that any two edges of the graph drawn to the plane are not intersected (except the common ends of the two edges, the same below), that is, the drawing method must be a plane straight line drawing method. Let G = <V,E>have n vertices and m edges, (xi, yi) represents the coordinates of the vertices numbered I in the plan area, the same below. To solve the drawing problem, the first step is to find the mapping point of the vertices in the plan area, i.e. the coordinate point, and then connect the corresponding mapping points in the plan with straight line segments according to the connection between the vertices in the figure to get the plan straight line drawing method. Therefore, the algorithm is based on the above aesthetic criteria (1) - (5) the objective function f (x1, y1, x2, y2, . . . , xn, yn) is designed so that the function f (x1, y1,x2,y2,...,xn,yn) has the maximum value when the drawing method conforms to these aesthetic criteria and is a plane straight line drawing method. The definition of the objective function is given later. The following discussion is carried out according to the steps of designing genetic algorithm.
4.1Determine coding scheme
Let the vertex sequence of plane graph G be v1, v2, ddotsvn, its coordinates are (x1, y1), (x2, y2),...,(xn, yn) respectively, and the algorithm uses a real number string (x1, y1, x2, y2,...,xn, yn) of length 2n,)To represent the solution of the problem, we can directly carry out genetic operation on the representation of the solution.
4.2Design fitness function
According to the aesthetic criteria (1) - (5), the algorithm designs the following objective functions and directly takes them as fitness functions:
(1)
(2)
(3)
(4)
(5)
(6)
The constraints are:
(7)
(The common ends of two line segments are not included in the intersection points, the same below) and a ⩽ xi ⩽ b, c ⩽ yi ⩽ d where a, b, c, d represent the lower bound and upper bound of x coordinate and y coordinate on the plane area respectively.
The objective function is explained as follows: in factor (1), Cmax is a constant large enough, pi is the image of vertex vi in the plane, |pi - pj| is the distance between vertex pi and pj, and
According to the coordinates of the end points of line
4.3Determination of selection strategy
In order to prevent precocity, the adaptive value f(i) of individual i is transformed by Sigma scale transformation technology. Firstly, the following formula is used for transformation:
4.4The design of genetic operators
The genetic operations used in this algorithm include crossover, mutation and inversion. For the crossover operator, the algorithm adopts partial arithmetic crossover, that is, first select a part of the component in the parent solution vector, such as all components after the k-th component, and then generate 2n-k (0,1) interval random numbers a1, a2, . . . , an, and set the parent as:
The following inconsistent mutation operators are used for mutation operator algorithm: If S = (v1, v2, . . . , v2n) is a parent solution and component vk is selected for variation, and its value range is [ak, bk], then the solution after variation is
Here, RND(2) is the result of the positive integer module 2 that will be generated randomly and uniformly. t is the current evolution algebra, and Δ (t, y) = y (1 - r(1-t/T)) λ), where R is a random number on [0,1], T is the maximum evolution algebra, and λ is a parameter that determines the degree of inconsistency. It plays a role in adjusting the local search area, and its value is generally 2 to 5. Obviously, the value range of Δ (t, y) is [0, y] When t approaches T, Δ (t, y) approaches 0, which indicates that the range of variation is relatively large in the early stage of evolution, but smaller and smaller as evolution progresses, which plays a role of local fine-tuning of evolution system.
In addition, the algorithm performs the inversion operation with probability PI (inversion probability) before the cross operation. It first randomly selects two points in the parent vector, and truncates the vector at these two points, and reverses the truncated part to obtain its offspring. For example, set the parent vector as
If the two inversion sites are i and j, the offspring vector is
4.5Design and implementation of genetic algorithm
Genetic algorithm embodies the characteristics of evolutionary computation. Next, we will give a detailed introduction to genetic algorithm. Through the introduction of genetic algorithm, we can know that the whole genetic algorithm has a certain understanding.
4.5.1Framework of genetic algorithm
The flow chart of genetic algorithm is shown in Fig. 2: the formal description of genetic algorithm can be represented by an 8-tuple:
Fig. 2
Flow chart of genetic algorithm.
Among:
C——Individual coding method;
E——Individual fitness evaluation function;
P0——Initial group;
M——Group size;
F——Selection operator;
G——Hybrid operator;
ψ——Mutation operator;
T——Termination conditions of genetic operators.
4.5.2Coding and initialization
In genetic algorithm, how to describe the feasible solution of a problem, that is, how to transform the feasible solution of a problem from its solution space to the search space processed by genetic algorithm, is called coding. The relationship between coding space and solution space is shown in Fig. 3. At the beginning of the algorithm, a set of randomly generated initial solutions is provided to the algorithm, which is called “initial population gas”.
Fig. 3
Solution space and coding space.
Code: Coding method not only determines the arrangement of individual chromosomes, but also determines the decoding method. It can be seen that coding method largely determines how to carry out population genetic evolution operation and the efficiency of genetic evolution operation, a good coding method may make the genetic operations such as crossover operation and mutation operation easy to realize and execute. However, a differential coding method may make the genetic operations such as crossover operation and mutation operation difficult to realize, and may also produce many individuals without corresponding feasible solutions in the feasible solution set, which are represented by the solutions after decoding It is called invalid solution. Although sometimes some invalid solutions are not completely harmful, but in most cases it is one of the main factors that affect the efficiency of genetic algorithm.
Aiming at a specific application problem, how to design a perfect coding scheme has always been one of the application difficulties of genetic algorithm, and also an important research direction of genetic algorithm. It can be said that there is not a set of strict and complete guiding theory and evaluation criteria to help us design coding scheme. As a reference, DeJong has proposed two practical coding principles with strong operability (also known as coding rules):
Coding principle 1 (meaningful building block coding principle): coding scheme with low order and short defined length pattern that is easy to generate related to the problem to be solved shall be used;
Coding principle 2 (minimum character set coding principle): the coding scheme with minimum coding character set that can make the problem get natural representation or description shall be used.
For the basic genetic algorithm, coding is to use binary coding method. However, due to the wide application of genetic algorithm, so far many different coding methods have been proposed. We will introduce two of the most important: binary coding and floating-point coding.
(1) Binary code
Binary coding method is the most commonly used coding method in genetic algorithm. It uses binary symbol set 0,1 composed of binary symbols 0 and 1. Its individual genotype is a binary coding symbol string.
(2) Floating point coding method
For some multi-dimensional, high-precision continuous function optimization problems, there will be some disadvantages when using binary code to represent individuals. In order to improve the shortcomings of binary coding method, an individual floating-point model is proposed.
Initialization: One of the characteristics of genetic algorithm is that it searches for many points in the solution space at the same time, so first there must be a group of randomly generated initial solutions, called “initial population”. Generally speaking, the size of the population should be determined according to the specific problems and experiments. The randomly generated chromosomes may be illegal. In order to make all the chromosomes in the initial population legal, one method is to check the legality of each chromosome in the randomly generated place. If it is illegal, it will be discarded until the legitimate chromosomes are generated. Although this method is simple, it is not easy to the efficiency is not high.
If we can make any randomly generated chromosome legal without legitimacy check, it will undoubtedly greatly improve the efficiency of generating initial population. This method requires us to first find out the characteristics of the legitimate chromosomes according to the specific problems, and then carefully design the algorithm according to this law, so as to ensure that the randomly generated chromosomes are legitimate. In this paper, we will discuss the directed graph point stratification algorithm based on genetic algorithm, which uses this method to generate the initial population.
5Experimental results and analysis
Figure G2 in Fig. 1 is calculated by the method in this paper. The experimental parameter values are shown in Table 1 and the experimental results are shown in Fig. 4(a). Figure 4(b) is the experimental results of the method in this paper. The experiment is carried out on a computer with a memory of 128M and a speed of 1.7 GHz.
Table 1
The parameter setting
| Parameter | Value |
| Group size | 20 |
| Number of generations | 1000 |
| Hybridization rate | 0.75 |
| Variation rate | 0.15 |
| Inversion rate | 0.20 |
Fig. 4
Results of Figure G2.
In addition, the genetic algorithm in this paper is compared with the standard genetic algorithm. In which average evolution algebra refers to the average value of evolution algebra obtained by running two kinds of genetic algorithms 20 times respectively for figure G2 in Fig. 5, while average convergence time is the average value of convergence time obtained by running two kinds of genetic algorithms 20 times respectively, which can be found from the data in the table, Under the same conditions, compared with the standard genetic algorithm, the convergence times and speed of the genetic algorithm in this paper are increased.
Fig. 5
The experimental results.
The following Fig. 5 is some legends of the plane graph with 4–7 vertices drawn according to the above algorithm.
6Conclusions
Under the influence of novel coronavirus pneumonia, the traditional manual oil painting creation has put forward higher requirements. In this paper, a plane line drawing algorithm based on genetic algorithm is proposed. The advantages of the new algorithm are: the method is simple, easy to implement, and the drawing is beautiful. The experimental results show that the graph drawn by this algorithm is more beautiful than that drawn by traditional algorithm, and its convergence is higher than that of standard genetic algorithm. On the basis of this algorithm, the drawing of convex polygon and other drawing methods are further studied. This method has been applied to the COVID-19 period and achieved good results.
References
[1] | Takaki H. , Takeda M. , Tahara M. , et al., The MyD88 Pathway in Plasmacytoid and CD4+ Dendritic Cells Primarily Triggers Type I IFN Production against Measles Virus in a Mouse Infection Model, The Journal of Immunology 191: (9) ((2013) ), 4740–4747. |
[2] | Gong D. , Chen J. , Sun X. , et al., Evaluating individuals in interactive genetic algorithms using variational granularity, Soft Computing 19: (3) ((2015) ), 621–635. |
[3] | Coley D.A. and Winters D. , Genetic algorithm search efficacy in aesthetic product spaces, Complexity 3: (2) ((1997) ), 23–27. |
[4] | Poirson E. , Petiot J.-F. , Boivin L. , et al., Eliciting User Perceptions Using Assessment Tests Based on an Interactive Genetic Algorithm, Journal of Mechanical Design 135: (3) ((2013) ), 31–34. |
[5] | Heather T. , Mortgage Borrowers Scramble as Rates Jump, American Journal of Physical Anthropology 15: (3) ((2005) ), 509–519. |
[6] | Hekmatfar M. , Ghomi S.M.T.F. and Karimi B. , Two stage reentrant hybrid flow shop with setup times and the criterion of minimizing makespan, Applied Soft Computing 11: (8) ((2011) ), 4530–4539. |
[7] | Furuta H. , Hase H. , Watanabe E. , et al., Applications of genetic algorithm to aesthetic design of dam structures, Advances in Engineering Software 25: (2-3) ((1996) ), 185–195. |
[8] | Flynn R. and Sherman P.D. , Multicriteria optimization of aircraft panels: Determining viable genetic algorithm configurations, International Journal of Intelligent Systems 10: (11) ((1995) ), 987–999. |
[9] | Yi T.H. , Li H.N. and Gu M. , Optimal Sensor Placement for Health Monitoring of High-Rise Structure Based on Genetic Algorithm, Mathematical Problems in Engineering 2011: (Pt.1) ((2011) ), 54.1–54.12. |
[10] | Wang W.C. , Cheng C.T. , Chau K.W. , et al., Calibration of Xinanjiang model parameters using hybrid genetic algorithm based fuzzy optimal model, Journal of Hydroinformatics 14: (3) ((2012) ), 784. |
[11] | Naik G.N. , Gopalakrishnan S. and Ganguli R. , Design optimization of composites using genetic algorithms and failure mechanism based failure criterion, Composite Structures 83: (4) ((2008) ), 354–367. |
[12] | Coley D.A. and Winters D. , Genetic algorithm search efficacy in aesthetic product spaces, Complexity 3: (2) ((1997) ), 23–27. |
[13] | Tsai H.C. and Chou J.R. , Automatic design support and image evaluation of two-coloured products using colour association and colour harmony scales and genetic algorithm, 39: (9) ((2007) ), 818–828. |
