python實(shí)現(xiàn)使用遺傳算法進(jìn)行圖片擬合

更新時(shí)間：2022年03月11日 11:23:05 作者：艾醒

最近做項(xiàng)目需要圖像擬合，本文主要介紹了python實(shí)現(xiàn)使用遺傳算法進(jìn)行圖片擬合，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

引言

算法思路

假設(shè)我們有這樣一個(gè)生物族群，他們的每個(gè)基因片段都是一個(gè)個(gè)三角形（即只含三個(gè)點(diǎn)和顏色信息），他們每個(gè)個(gè)體表現(xiàn)出的性狀就是若干個(gè)三角形疊加在一起。假設(shè)我們有一張圖片可以作為這種生物族群最適應(yīng)環(huán)境的性狀，即長(zhǎng)得越像這張圖片的越能適應(yīng)環(huán)境，越不像這張圖片的越容易被淘汰。

當(dāng)然作為一個(gè)正常的生物族群，他應(yīng)該也會(huì)有正常的繁衍以產(chǎn)生新個(gè)體。產(chǎn)生新個(gè)體的過(guò)程中來(lái)自父親和母親的基因會(huì)進(jìn)行交叉互換和變異，變異又可以有增加基因片段、減少基因片段以及不同位置的基因片段順序互換。

但是一個(gè)族群不能夠無(wú)限的繁殖，我們假設(shè)環(huán)境資源只能容納有限的生物族群規(guī)模，所以我們?cè)诋a(chǎn)生足夠多的后代之后就要把他們放到族群里與族群內(nèi)部進(jìn)行競(jìng)爭(zhēng)淘汰。這樣一來(lái)，通過(guò)不斷地淘汰，這個(gè)族群就會(huì)越來(lái)越像我們給定的圖片。這就是算法的基本思路。

流程圖

在這里插入圖片描述

下面我們來(lái)看一下實(shí)現(xiàn)過(guò)程，為了方便解釋，我們會(huì)結(jié)合python建立類似于偽代碼的函數(shù)進(jìn)行解釋，不能直接運(yùn)行，具體可運(yùn)行的代碼可直接下載參照最后的類封裝的完整代碼

預(yù)備知識(shí)及準(zhǔn)備工作

打開圖片

我們使用imageio中的imread打開圖片，這里為了方便后續(xù)使用我們建立OpenImg函數(shù)，返回打開的圖片img（格式為array），圖片的格式（方便后期圖片的保存），圖片的大?。簉ow和col（為后期畫圖做準(zhǔn)備）。

from imageio import imread

def OpenImg(imgPath):
	img = imread(imgPath)
    row, col = img.shape[0], img.shape[1]
    return img, imgPath.split(".")[-1], row, col

隨機(jī)生成生物族群

我們假設(shè)一個(gè)族群的最大生物個(gè)數(shù)為max_group，用groups來(lái)表示族群，g為族群內(nèi)的生物個(gè)體，運(yùn)用隨機(jī)數(shù)隨機(jī)產(chǎn)生個(gè)體。

from random import choice

for 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())

按照生物性狀畫圖

我們使用PIL畫圖，首先我們建立一個(gè)空白的畫布，然后再將個(gè)體的特征（三角形）畫到圖上。

from PIL import Image, ImageDraw

def to_image(g):
	array = np.ndarray((img.shape[0], img.shape[1], img.shape[2]), np.uint8)
	array[:, :, 0] = 255
	array[:, :, 1] = 255
	array[:, :, 2] = 255
	newIm1 = 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

對(duì)比生物個(gè)體和目標(biāo)圖片的相似度

使用structural_similarity對(duì)比兩個(gè)圖片的相似度，此時(shí)兩個(gè)圖片都應(yīng)該是array類型

from skimage.metrics import structural_similarity

def getSimilar(g) -> float:
	newIm1 = to_image(g)
    ssim = structural_similarity(np.array(img), np.array(newIm1), multichannel=True)
    return ssim

保存圖片

調(diào)用我們之前建立好的to_image函數(shù)先將個(gè)體轉(zhuǎn)換成圖片，然后將圖片保存即可。

def draw_image(g, cur, imgtype):
    image1 = to_image(g)
    image1.save(os.path.join(str(cur) + "." + imgtype))

算法主體

交叉互換

考慮到后期的基因片段的增添和減少，所以應(yīng)該分為兩步，其一是相重合的位置進(jìn)行交叉互換，以及對(duì)于多出來(lái)的尾部進(jìn)行交叉互換，我們按照隨機(jī)率random_rate和重合位置長(zhǎng)度min_locate來(lái)確定交換的位數(shù)。然后我們使用sample選出若干位置進(jìn)行互換。交換結(jié)束后再對(duì)尾部進(jìn)行互換

random_rate = random()

def exchange(father, mother)->[]:
	# 交換
	# 隨機(jī)生成互換個(gè)數(shù)
	min_locate = min(len(father), len(mother))
	n = randint(0, int(random_rate * min_locate))
	# 隨機(jī)選出多個(gè)位置
	selected = sample(range(0, min_locate), n)
	# 交換內(nèi)部
	for s in selected:
		father[s], mother[s] = mother[s], father[s]

  	# 交換尾部
	locat = randint(0, min_locate)
	fhead = father[:locat].copy()
	mhead = mother[:locat].copy()

	ftail = father[locat:].copy()
	mtail = mother[locat:].copy()

	# print(fhead, ftail, mhead, mtail)
	fhead.extend(mtail)
	father = fhead
	mhead.extend(ftail)
	mother = mhead
	return [father, mother]

基因突變

隨機(jī)選擇的原理和目的與上面類似，這里我們把重新生成某個(gè)基因片段的信息看作基因突變。

random_rate = random()

def mutation(gen):
	# 突變
	# 隨機(jī)生成變異個(gè)數(shù)
	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, 100))] for x in	range(3)]
		tmp.append("#" + ''.join(choice('0123456789ABCDEF') for x in range(6)))
		gen[s] = tmp

	return gen

基因片段易位

在個(gè)體的基因組內(nèi)隨機(jī)選擇基因片段進(jìn)行位置互換。

def move(gen):
	# 易位
	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

增加基因片段

直接在個(gè)體基因組后面添加隨機(jī)產(chǎn)生的基因片段即可。

features = 100
def add(gen):
	# 增加
	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

減少基因片段

隨機(jī)減少個(gè)體的若干基因片段

def cut(self, gen):
    # 減少
	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(gen[gp])

    return g

變異

以此調(diào)用以上的突變、易位、增添和減少產(chǎn)生4種狀態(tài)的基因片段

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

繁殖

繁殖過(guò)程包括交叉互換和變異，直接調(diào)用之前構(gòu)造的函數(shù)即可

def breeds(father, mother):
	new1, new2 = exchange(father.copy(), mother.copy())
	# 變異
	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]

淘汰

建立個(gè)體和其與目標(biāo)的相似度相關(guān)的映射關(guān)系，并按照相似度排序，然后去除相似度較低的個(gè)體，直到剩余生物個(gè)體的數(shù)量為max_group為止。在這個(gè)函數(shù)中我們還返回了一個(gè)最優(yōu)個(gè)體的相似度來(lái)方便監(jiān)測(cè)。

def eliminated(groups):
	group_dict = dict()
	for gp in range(len(groups)):
		group_dict[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]

擬合

擬合過(guò)程先要進(jìn)行若干次的繁殖，為了保證每次繁殖的個(gè)體數(shù)我們規(guī)定其至少選擇最大個(gè)體數(shù)的一半數(shù)量的次數(shù)進(jìn)行繁殖，繁殖之后的個(gè)體加入到種群當(dāng)作和之前種群中的個(gè)體一起進(jìn)行淘汰。通過(guò)這個(gè)過(guò)程我們每次淘汰都會(huì)將與目標(biāo)差距最大的個(gè)體淘汰。

def breeds(father, mother):
	new1, new2 = exchange(father.copy(), mother.copy())
	# 變異
	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]

示例展示

擬合時(shí)建議選擇分辨率低的圖片，如果選擇的圖片分辨率較高，可以使用以下代碼降低圖片分辨率

降低圖片分辨率

from imageio import imread
from PIL import Image

imgPath = input("輸入圖片路徑")
img = imread(imgPath)
img = img[::2, ::2, :]
img = Image.fromarray(img)
img.save(imgPath)

原圖

我們以擬合一個(gè)小藍(lán)鳥和一個(gè)心形為例來(lái)展示擬合過(guò)程

在這里插入圖片描述

擬合過(guò)程展示

代碼實(shí)現(xiàn)（這里已經(jīng)事先將重復(fù)圖片刪除了）

import os
import math
import matplotlib.pyplot as plt
import matplotlib.image as image

path = "./xl"
length = len(os.listdir(path))
row = col = math.ceil(math.sqrt(length))
x = 1


lst = []
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 += 1


plt.savefig(path)
plt.show()

效果

在這里插入圖片描述