Load the image file.

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 *

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

--Extract the target representative color as a frequent color. The area is filled with the representative color. --In order to paint the area with the resulting color, I will once paint the area with an easy-to-understand color (red is 0, green is 1, blue is the area number). --First, set G (green) of RGB = (0,1,?) Color to 0. --Fill the representative color area with RGB = (0,1, serial number). --Wide the boundaries a little ――Randomly select a point, and if the color is an area and there is no area next to it by 1 pixel, make it that area.

python

#Representative color(Most frequently used colors)Extract
cc = sorted([(v, k) for k, v in Counter(im.getdata()).items()])[-1][1]

# RGB=(0,1,?)Eliminate the color of
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)

#RGB representative color area=(0,1,serial number)Fill with
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

#Widen the border a little
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)

Create a graph with areas as points and pixels between adjacent areas as edges.

python

#Graphs whether they are next to each other
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])

Formulate and solve.

python

#Solve the 4-color problem
r4 = range(4)
m = LpProblem() #Mathematical model
#Whether to make area i color 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 colors
rr = [int(value(lpDot(r4, i))) for i in v] #result
for y, x in product(range(im.height-1), range(im.width-1)):
    c = im.getpixel((x, y))
    if c[:2] == (0, 1): #If it is an area, paint with the result
        ImageDraw.floodfill(im, (x, y), co[rr[c[2]]])
im.save('result.png')

When I actually tried it, it was OK.

that's all