Shulou(Shulou.com)06/01 Report--

Editor to share with you how python uses genetic algorithms for picture fitting. I hope you will get something after reading this article. Let's discuss it together.

Introduction

Algorithm idea

Suppose we have a population of creatures whose gene fragments are triangles (that is, only three dots and color information), and the traits shown by each individual are superimposed by several triangles. Suppose we have a picture that can be used as the most adaptable trait of this biological population, that is, those who look more like this picture are more adaptable to the environment, and those who are less like this picture are more likely to be eliminated.

Of course, as a normal biological population, he should also have normal reproduction to produce new individuals. In the process of producing a new individual, the genes from the father and mother will be cross-exchanged and mutated, and the variation can include the increase of gene fragments, the reduction of gene fragments and the sequence exchange of gene fragments in different locations.

However, a population cannot reproduce indefinitely, and we assume that environmental resources can only accommodate a limited population size, so after we produce enough offspring, we have to put them into the population to compete with the population for elimination. In this way, through continuous elimination, the group will become more and more like the pictures we have given. This is the basic idea of the algorithm.

Flow chart

Let's take a look at the implementation process. In order to facilitate interpretation, we will combine python to establish a function similar to pseudo-code for interpretation, which cannot be run directly. The specific runnable code can be downloaded directly and refer to the complete code encapsulated by the final class.

Preparatory knowledge and preparatory work to open the picture

We use imread in imageio to open the picture, here to facilitate the subsequent use of our OpenImg function, return the open image img (format for array), picture format (to facilitate the preservation of later pictures), picture size: row and col (in preparation for later painting).

From imageio import imreaddef OpenImg (imgPath): img = imread (imgPath) row, col = img.shape [0], img.shape [1] return img, imgPath.split (".") [- 1], row, col randomly generate biological populations

We assume that the maximum number of organisms in a population is max_group, the population is represented by groups, g is the biological individual in the population, and the individual is randomly generated by random number.

From random import choicefor i in range (max_group): G = [] for j in range (features): tmp = [choice (np.linspace (0, row, features)), choice (np.linspace (0, col) Features)] for x in range (3)] tmp.append ("#" + '.join (choice (' 0123456789ABCDEF') for x in range (6)) g.append (tmp.copy ()) groups.append (g.copy ()) draws pictures according to biological traits

We use PIL to draw, first we create a blank canvas, and then draw individual features (triangles) on the map.

From PIL import Image, ImageDrawdef to_image (g): array = np.ndarray ((img.shape [0], img.shape [1], img.shape [2]), np.uint8) array [:,:, 0] = 255array [:,:, 1] = 255array [: 2] = 255newIm1 = Image.fromarray (array) draw = ImageDraw.Draw (newIm1) for d in g: draw.polygon ((d [0] [0], d [0] [1], d [1] [0], d [1] [1], d [2] [0], d [2] [1]), d [3]) return newIm1 compares the similarity between the individual and the target image

Use structural_similarity to compare the similarity between two images. At this time, both images should be of array type.

From skimage.metrics import structural_similaritydef getSimilar (g)-> float: newIm1 = to_image (g) ssim = structural_similarity (np.array (img), np.array (newIm1), multichannel=True) return ssim saves the picture

Call the to_image function we established earlier to convert the individual into an image, and then save the image.

Def draw_image (g, cur, imgtype): image1 = to_image (g) image1.save (os.path.join (str (cur) + "." + imgtype)) algorithm body crossover

Considering the increase and decrease of gene fragments in the later stage, it should be divided into two steps, one is the cross-swap of the coincident position, and the cross-swap of the extra tail, we determine the number of digits according to the random random_rate and the length of the coincident position min_locate. Then we use sample to select several locations to swap. Swap the tail after the exchange is over.

Random_rate = random () def exchange (father, mother)-> []: # Exchange # randomly generated swap number min_locate = min (len (father), len (mother)) n = randint (0, int (random_rate * min_locate)) # multiple positions selected = sample (range (0, min_locate)) N) # Exchange internal for s in selected: father [s], mother [s] = mother [s], father [s] # Exchange tail locat = randint (0 Min_locate) fhead = father [: locat] .copy () mhead = mother [: locat] .copy () ftail = father [locat:] .copy () mtail = mutation of fhead.extend (mtail) father = fhead mhead.extend (ftail) mother = mhead return [father, mother] gene

The principle and purpose of random selection is similar to the above, where we regard the information of regenerating a gene fragment as a genetic mutation.

Random_rate = random () def mutation (gen): # mutation # number of randomly generated variants n = int (randint (1,100) / 1000 * len (gen)) selected = sample (range (0, len (gen), n) for s in selected: tmp = [choice (np.linspace (0,row, 100)), choice (np.linspace (0, col) ] for x in range (3)] tmp.append ("#" + '.join (choice (' 0123456789ABCDEF') for x in range (6) gen [s] = tmp return gen gene fragment translocation

Gene fragments are randomly selected within the individual genome for position swapping.

Def move (gen): # Translocation exchage = int (randint (1,100) / 1000 * len (gen)) for e in range (exchage): sec1 = randint (0, len (gen)-1) sec2 = randint (0, len (gen)-1) gen [sec1], gen [sec2] = gen [sec2] Gen [sec1] return gen increases gene fragments

Randomly generated gene fragments can be added directly to the back of the individual genome.

Features = 100def add (gen): # add n = int (randint (1,100) / 1000 * len (gen)) for s in range (n): tmp = [choice (np.linspace (0, row,features)), choice (np.linspace (0, col)) Features)] for x in range (3)] tmp.append ("#" + '.join (choice (' 0123456789ABCDEF') for x in range (6) gen.append (tmp) return gen reduction gene fragment

Randomly reduce some gene fragments of individuals

Def cut (self, gen): # minus n = int (randint (1,100) / 1000 * len (gen)) selected = sample (range (0, len (gen)), n) g = [] for gp in range (len (gen)): if gp not in selected: g.append (Geng [GP]) return g variation

In order to invoke the above mutation, translocation, addition and reduction of gene fragments that produce four states.

Def variation (gen): # mutation gen = mutation (gen.copy ()) gen1 = move (gen.copy ()) gen2 = add (gen1.copy ()) gen3 = cut (gen2.copy ()) return [gen, gen1, gen2, gen3] Propagation

The reproductive process includes cross-exchange and mutation, which can be directly called by the previously constructed function.

Def breeds (father, mother): new1, new2 = exchange (father.copy (), mother.copy ()) # variant new3, new4, new5, new6 = variation (father.copy ()) new7, new8, new9, new10 = variation (mother.copy ()) return [new1, new2, new3, new4, new5, new6, new7, new8, new9, new10] out

Establish the mapping relationship between the individual and its similarity with the target, and sort it according to the similarity, and then remove the individuals with low similarity until the number of remaining biological individuals is max_group. In this function, we also return the similarity of an optimal individual to facilitate monitoring.

Def eliminated (groups): group_dict = dict () for gp in range (len (groups)): group_ [GP] = getSimilar (groups [GP]) group_dict = {key: value for key, value in sorted (group_dict.items (), key=lambda item: item [1]) Reverse=True)} g = [] for key in list (group_dict.keys ()) [: max_group]: g.append (groups [key] .copy () groups = g.copy () return groups, list (group_dict.values ()) [0] fitting

The fitting process requires several times of reproduction, and in order to ensure the number of individuals per reproduction, we stipulate that it should select at least half of the maximum number of individuals to reproduce, and the individuals after reproduction are added to the population as if they were eliminated together with the individuals in the previous population. Through this process, we will eliminate the individuals with the biggest gap from the target each time we are eliminated.

Def breeds (father, mother): new1, new2 = exchange (father.copy (), mother.copy ()) # variant new3, new4, new5, new6 = variation (father.copy ()) new7, new8, new9, new10 = variation (mother.copy ()) return [new1, new2, new3, new4, new5, new6, new7, new8, new9, new10] sample display

When fitting, it is recommended to choose a picture with low resolution. If you choose a picture with a high resolution, you can use the following code to reduce the image resolution.

Lower picture resolution from imageio import imreadfrom PIL import ImageimgPath = input ("enter picture path") img = imread (imgPath) img = img [:: 2,: 2,: 2,:] img = Image.fromarray (img) img.save (imgPath) original image

We take fitting a little bluebird and a heart as an example to show the fitting process.

Fitting process display

Code implementation (the duplicate image has been deleted here)

Import osimport mathimport matplotlib.pyplot as pltimport matplotlib.image as imagepath = ". / xl" length = len (os.listdir (path)) row = col = math.ceil (math.sqrt (length)) x = 1lst = [] for d in os.listdir (path): lst.append (int (d.split ('.) [0]) lst = sorted (lst) for l in lst: img = image.imread (os.path.join (path) Str (l) + '.png') plt.xticks ([]) plt.yticks ([]) plt.subplot (row, col, x) plt.imshow (img) plt.xticks ([]) plt.yticks ([]) plt.title (str (l)) x + = 1plt.savefig (path) plt.show ()

Effect.

After reading this article, I believe you have a certain understanding of "how to use genetic algorithm for picture fitting in python". If you want to know more about it, you are welcome to follow the industry information channel. Thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.