Résolvez le problème des 4 couleurs grâce à l'optimisation des combinaisons

Résolvez le problème des 4 couleurs

Optimisation de combinaison peut également être utilisé pour résoudre des problèmes de 4 couleurs. Ici, lisons le problème automatiquement à partir de l'image. Le problème vient de Nikori-sama.

Formulation

Il existe plusieurs zones et les zones adjacentes sont peintes de différentes couleurs.

$ \ mbox {variables} $ $ v_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ Zone i La couleur est-elle j? (1)
$ \ mbox {sujet à} $ $ \ sum_j {v_ {ij}} = 1 ~ \ forall i $ Choisissez une couleur ( 2)
Les zones adjacentes doivent être de couleurs différentes (3)

Résoudre avec Python

Chargez le fichier image.

python


import networkx as nx
from urllib import request
from PIL import Image, ImageDraw
from collections import Counter
from itertools import product
from random import seed, shuffle
from pulp import *

#Lecture de fichiers image
with request.urlopen('https://dl.dropboxusercontent.com/u/35689878/tmp/4c.png') as fd:
    im = Image.open(fd)

4c.png

  • Extraire la couleur représentative cible comme couleur fréquente. La zone est remplie de la couleur représentative.
  • Afin de peindre la zone avec la couleur résultante, je peindrai une fois la zone avec une couleur facile à comprendre (le rouge est 0, le vert est 1, le bleu est le numéro de la zone).
  • Tout d'abord, définissez G (vert) de RVB = (0,1 ,?) Couleur sur 0. --Remplissez la zone de couleur représentative avec RVB = (0,1, numéro de série).
  • Élargissez un peu les limites --Sélectionnez un point au hasard, et si la couleur est une zone et qu'il n'y a pas de zone à côté de 1 pixel, faites-en cette zone.

python


#Couleur représentative(Couleurs les plus fréquemment utilisées)Extrait
cc = sorted([(v, k) for k, v in Counter(im.getdata()).items()])[-1][1]

# RGB=(0,1,?)Élimine la couleur de
for y, x in product(range(im.height), range(im.width)):
    R, G, B = im.getpixel((x, y))[:3]
    if (R, G) == (0, 1):
        im.putpixel(0, 0, B)

#Zone de couleur représentative RVB=(0,1,numéro de série)Remplir avec
n = 0
for y, x in product(range(im.height), range(im.width)):
    if im.getpixel((x, y)) != cc:
        continue
    ImageDraw.floodfill(im, (x, y), (0, 1, n))
    n += 1

#Élargissez un peu la frontière
seed(1)
dd = [(-1, 0), (0, -1), (0, 1), (1, 0)]
for h in range(1):
    l = list(product(range(1, im.height-1), range(1, im.width-1)))
    shuffle(l)
    for y, x in l:
        c = im.getpixel((x, y))
        if c[:2] == (0, 1):
            for i, j in dd:
                if im.getpixel((x+i, y+j))[:2] != (0, 1):
                    im.putpixel((x+i, y+j), c)

Créez un graphique avec des zones sous forme de points et des pixels entre les zones adjacentes sous forme d'arêtes.

python


#Montrer graphiquement s'ils sont côte à côte
g = nx.Graph()
for y, x in product(range(im.height-1), range(im.width-1)):
    c1 = im.getpixel((x, y))
    if c1[:2] != (0, 1):
        continue
    c2 = im.getpixel((x+1, y))
    c3 = im.getpixel((x, y+1))
    if c2[:2] == (0, 1) and c1[2] != c2[2]:
        g.add_edge(c1[2], c2[2])
    if c3[:2] == (0, 1) and c1[2] != c3[2]:
        g.add_edge(c1[2], c3[2])

Formulez et résolvez.

python


#Résolvez le problème des 4 couleurs
r4 = range(4)
m = LpProblem() #Modèle mathématique
#Faire ou non la zone i couleur j(1)
v = [[LpVariable('v%d_%d'%(i, j), cat=LpBinary) for j in r4] for i in g.nodes()]
for i in g.nodes():
    m += lpSum(v[i]) == 1 # (2)
for i, j in g.edges():
    for k in r4:
        m += v[i][k] + v[j][k] <= 1 # (3)
m.solve()
co = [(97, 132, 219), (228, 128, 109), (255, 241, 164), (121, 201, 164)] #4 couleurs
rr = [int(value(lpDot(r4, i))) for i in v] #résultat
for y, x in product(range(im.height-1), range(im.width-1)):
    c = im.getpixel((x, y))
    if c[:2] == (0, 1): #S'il s'agit d'une zone, peignez avec le résultat
        ImageDraw.floodfill(im, (x, y), co[rr[c[2]]])
im.save('result.png')

result.png

Quand je l'ai essayé, ça allait.

cong.png

c'est tout

Recommended Posts