Вам дано истинное цветное изображение. Ваша задача - создать версию этого изображения, которая выглядит так, как будто она была нарисована с использованием рисования по номерам (детская деятельность, а не нонограммы). Наряду с изображением вам задаются два параметра: P - максимальный размер цветовой палитры (т.е. максимальное количество используемых цветов) и N - максимальное количество используемых ячеек . Ваш алгоритм не должен использовать все цвета P и N ячеек, но он не должен использовать больше, чем это. Выходное изображение должно иметь те же размеры, что и входное.

Клетка определяются как непрерывная область пикселей , которые все имеют один и тот же цвет. Пиксели, соприкасающиеся только с углом, не считаются смежными. Клетки могут иметь отверстия.

Короче говоря, вы должны аппроксимировать входное изображение только N плоскими / сплошными областями и P различными цветами.

Просто для наглядности параметров, вот очень простой пример (без какого-либо конкретного входного изображения; демонстрируя мои безумные навыки рисования). Следующее изображение имеет P = 6 и N = 11 :

Вот несколько изображений для проверки вашего алгоритма (в основном наши обычные подозреваемые). Нажмите на картинку для увеличения.

Пожалуйста, включите несколько результатов для различных параметров. Если вы хотите показать большое количество результатов, вы можете создать галерею на imgur.com , чтобы размер ответов был разумным. В качестве альтернативы, поместите миниатюры в свой пост и сделайте их ссылками на большие изображения, как я делал выше. Кроме того, не стесняйтесь использовать другие тестовые изображения, если вы найдете что-то хорошее.

Я предполагаю, что параметры около N ≥ 500 , P ~ 30 будут аналогичны реальным шаблонам рисования по номерам.

Это конкурс популярности, поэтому победит ответ с наибольшим количеством голосов. Избирателям предлагается судить ответы по

• насколько хорошо исходные изображения являются приблизительными.
• насколько хорошо алгоритм работает на разных видах изображений (картины, как правило, проще, чем фотографии).
• насколько хорошо алгоритм работает с очень строгими параметрами.
• как органично / гладко выглядят клеточные формы.

Я буду использовать следующий скрипт Mathematica для проверки результатов:

image = <pastedimagehere> // ImageData;
palette = Union[Join @@ image];
Print["P = ", Length@palette];
grid = GridGraph[Reverse@Most@Dimensions@image];
image = Flatten[image /. Thread[palette -> Range@Length@palette]];
Print["N = ", 
 Length@ConnectedComponents[
   Graph[Cases[EdgeList[grid], 
     m_ <-> n_ /; image[[m]] == image[[n]]]]]]

Sp3000 был достаточно любезен, чтобы написать верификатор в Python 2, используя PIL, который вы можете найти на этой вставке .

Python 2 с PIL ( Галерея )

from __future__ import division
from PIL import Image
import random, math, time
from collections import Counter, defaultdict, namedtuple

"""
Configure settings here
"""

INFILE = "spheres.png"
OUTFILE_STEM = "out"
P = 30
N = 300
OUTPUT_ALL = True # Whether to output the image at each step

FLOOD_FILL_TOLERANCE = 10
CLOSE_CELL_TOLERANCE = 5
SMALL_CELL_THRESHOLD = 10
FIRST_PASS_N_RATIO = 1.5
K_MEANS_TRIALS = 30
BLUR_RADIUS = 2
BLUR_RUNS = 3

"""
Color conversion functions
"""

X = xrange

# http://www.easyrgb.com/?X=MATH    
def rgb2xyz(rgb):
 r,g,b=rgb;r/=255;g/=255;b/=255;r=((r+0.055)/1.055)**2.4 if r>0.04045 else r/12.92
 g=((g+0.055)/1.055)**2.4 if g>0.04045 else g/12.92;b=((b+0.055)/1.055)**2.4 if b>0.04045 else b/12.92
 r*=100;g*=100;b*=100;x=r*0.4124+g*0.3576+b*0.1805;y=r*0.2126+g*0.7152+b*0.0722
 z=r*0.0193+g*0.1192+b*0.9505;return(x,y,z)
def xyz2lab(xyz):
 x,y,z=xyz;x/=95.047;y/=100;z/=108.883;x=x**(1/3)if x>0.008856 else 7.787*x+16/116
 y=y**(1/3)if y>0.008856 else 7.787*y+16/116;z=z**(1/3)if z>0.008856 else 7.787*z + 16/116
 L=116*y-16;a=500*(x-y);b=200*(y-z);return(L,a,b)
def rgb2lab(rgb):return xyz2lab(rgb2xyz(rgb))
def lab2xyz(lab):
 L,a,b=lab;y=(L+16)/116;x=a/500+y;z=y-b/200;y=y**3 if y**3>0.008856 else(y-16/116)/7.787
 x=x**3 if x**3>0.008856 else (x-16/116)/7.787;z=z**3 if z**3>0.008856 else(z-16/116)/7.787
 x*=95.047;y*=100;z*=108.883;return(x,y,z)
def xyz2rgb(xyz):
 x,y,z=xyz;x/=100;y/=100;z/=100;r=x*3.2406+y*-1.5372+z*-0.4986
 g=x*-0.9689+y*1.8758+z*0.0415;b=x*0.0557+y*-0.2040+z*1.0570
 r=1.055*(r**(1/2.4))-0.055 if r>0.0031308 else 12.92*r;g=1.055*(g**(1/2.4))-0.055 if g>0.0031308 else 12.92*g
 b=1.055*(b**(1/2.4))-0.055 if b>0.0031308 else 12.92*b;r*=255;g*=255;b*=255;return(r,g,b)
def lab2rgb(lab):rgb=xyz2rgb(lab2xyz(lab));return tuple([int(round(x))for x in rgb])

"""
Stage 1: Read in image and convert to CIELAB
"""

total_time = time.time()

im = Image.open(INFILE)
width, height = im.size

if OUTPUT_ALL:
  im.save(OUTFILE_STEM + "0.png")
  print "Saved image %s0.png" % OUTFILE_STEM

def make_pixlab_map(im):
  width, height = im.size
  pixlab_map = {}

  for i in X(width):
    for j in X(height):
      pixlab_map[(i, j)] = rgb2lab(im.getpixel((i, j)))

  return pixlab_map

pixlab_map = make_pixlab_map(im)

print "Stage 1: CIELAB conversion complete"

"""
Stage 2: Partitioning the image into like-colored cells using flood fill
"""

def d(color1, color2):
  return (abs(color1[0]-color2[0])**2 + abs(color1[1]-color2[1])**2 + abs(color1[2]-color2[2])**2)**.5

def neighbours(pixel):
  results = []

  for neighbour in [(pixel[0]+1, pixel[1]), (pixel[0]-1, pixel[1]),
            (pixel[0], pixel[1]+1), (pixel[0], pixel[1]-1)]:

    if 0 <= neighbour[0] < width and 0 <= neighbour[1] < height:
      results.append(neighbour)

  return results

def flood_fill(start_pixel):
  to_search = {start_pixel}
  cell = set()
  searched = set()
  start_color = pixlab_map[start_pixel]

  while to_search:
    pixel = to_search.pop()

    if d(start_color, pixlab_map[pixel]) < FLOOD_FILL_TOLERANCE:
      cell.add(pixel)
      unplaced_pixels.remove(pixel)

      for n in neighbours(pixel):
        if n in unplaced_pixels and n not in cell and n not in searched:
          to_search.add(n)

    else:
      searched.add(pixel)

  return cell

# These two maps are inverses, pixel/s <-> number of cell containing pixel
cell_sets = {}
pixcell_map = {}
unplaced_pixels = {(i, j) for i in X(width) for j in X(height)}

while unplaced_pixels:
  start_pixel = unplaced_pixels.pop()
  unplaced_pixels.add(start_pixel)
  cell = flood_fill(start_pixel)

  cellnum = len(cell_sets)
  cell_sets[cellnum] = cell

  for pixel in cell:
    pixcell_map[pixel] = cellnum

print "Stage 2: Flood fill partitioning complete, %d cells" % len(cell_sets)

"""
Stage 3: Merge cells with less than a specified threshold amount of pixels to reduce the number of cells
     Also good for getting rid of some noise
"""

def mean_color(cell, color_map):
  L_sum = 0
  a_sum = 0
  b_sum = 0

  for pixel in cell:
    L, a, b = color_map[pixel]
    L_sum += L
    a_sum += a
    b_sum += b

  return L_sum/len(cell), a_sum/len(cell), b_sum/len(cell)

def remove_small(cell_size):
  if len(cell_sets) <= N:
    return

  small_cells = []

  for cellnum in cell_sets:
    if len(cell_sets[cellnum]) <= cell_size:
      small_cells.append(cellnum)

  for cellnum in small_cells:
    neighbour_cells = []

    for cell in cell_sets[cellnum]:
      for n in neighbours(cell):
        neighbour_reg = pixcell_map[n]

        if neighbour_reg != cellnum:
          neighbour_cells.append(neighbour_reg)

    closest_cell = max(neighbour_cells, key=neighbour_cells.count)

    for cell in cell_sets[cellnum]:
      pixcell_map[cell] = closest_cell

    if len(cell_sets[closest_cell]) <= cell_size:
      small_cells.remove(closest_cell)

    cell_sets[closest_cell] |= cell_sets[cellnum]
    del cell_sets[cellnum]

    if len(cell_sets) <= N:
      return

for cell_size in X(1, SMALL_CELL_THRESHOLD):
  remove_small(cell_size)

if OUTPUT_ALL:
  frame_im = Image.new("RGB", im.size)

  for cellnum in cell_sets:
    cell_color = mean_color(cell_sets[cellnum], pixlab_map)

    for pixel in cell_sets[cellnum]:
      frame_im.putpixel(pixel, lab2rgb(cell_color))

  frame_im.save(OUTFILE_STEM + "1.png")
  print "Saved image %s1.png" % OUTFILE_STEM

print "Stage 3: Small cell merging complete, %d cells" % len(cell_sets)

"""
Stage 4: Close color merging
"""

cell_means = {}

for cellnum in cell_sets:
  cell_means[cellnum] = mean_color(cell_sets[cellnum], pixlab_map)

n_graph = defaultdict(set)

for i in X(width):
  for j in X(height):
    pixel = (i, j)
    cell = pixcell_map[pixel]

    for n in neighbours(pixel):
      neighbour_cell = pixcell_map[n]

      if neighbour_cell != cell:
        n_graph[cell].add(neighbour_cell)
        n_graph[neighbour_cell].add(cell)

def merge_cells(merge_from, merge_to):
  merge_from_cell = cell_sets[merge_from]

  for pixel in merge_from_cell:
    pixcell_map[pixel] = merge_to

  del cell_sets[merge_from]
  del cell_means[merge_from]

  n_graph[merge_to] |= n_graph[merge_from]
  n_graph[merge_to].remove(merge_to)

  for n in n_graph[merge_from]:
    n_graph[n].remove(merge_from)

    if n != merge_to:
      n_graph[n].add(merge_to)

  del n_graph[merge_from]

  cell_sets[merge_to] |= merge_from_cell
  cell_means[merge_to] = mean_color(cell_sets[merge_to], pixlab_map)

# Go through the cells from largest to smallest. Keep replenishing the list while we can still merge.
last_time = time.time()
to_search = sorted(cell_sets.keys(), key=lambda x:len(cell_sets[x]), reverse=True)
full_list = True

while len(cell_sets) > N and to_search:
  if time.time() - last_time > 15:
    last_time = time.time()
    print "Close color merging... (%d cells remaining)" % len(cell_sets)

  while to_search:
    cellnum = to_search.pop()
    close_cells = []

    for neighbour_cellnum in n_graph[cellnum]:
      if d(cell_means[cellnum], cell_means[neighbour_cellnum]) < CLOSE_CELL_TOLERANCE:
        close_cells.append(neighbour_cellnum)

    if close_cells:
      for neighbour_cellnum in close_cells:
        merge_cells(neighbour_cellnum, cellnum)

        if neighbour_cellnum in to_search:
          to_search.remove(neighbour_cellnum)

      break

  if full_list == True:
    if to_search:
      full_list = False

  else:
    if not to_search:
      to_search = sorted(cell_sets.keys(), key=lambda x:len(cell_sets[x]), reverse=True)
      full_list = True

if OUTPUT_ALL:
  frame_im = Image.new("RGB", im.size)

  for cellnum in cell_sets:
    cell_color = cell_means[cellnum]

    for pixel in cell_sets[cellnum]:
      frame_im.putpixel(pixel, lab2rgb(cell_color))

  frame_im.save(OUTFILE_STEM + "2.png")
  print "Saved image %s2.png" % OUTFILE_STEM

print "Stage 4: Close color merging complete, %d cells" % len(cell_sets)

"""
Stage 5: N-merging - merge until <= N cells
     Want to merge either 1) small cells or 2) cells close in color
"""

# Weight score between neighbouring cells by 1) size of cell and 2) color difference
def score(cell1, cell2):
  return d(cell_means[cell1], cell_means[cell2]) * len(cell_sets[cell1])**.5

n_scores = {}

for cellnum in cell_sets:
  for n in n_graph[cellnum]:
    n_scores[(n, cellnum)] = score(n, cellnum)

last_time = time.time()

while len(cell_sets) > N * FIRST_PASS_N_RATIO:
  if time.time() - last_time > 15:
    last_time = time.time()
    print "N-merging... (%d cells remaining)" % len(cell_sets)

  merge_from, merge_to = min(n_scores, key=lambda x: n_scores[x])

  for n in n_graph[merge_from]:
    del n_scores[(merge_from, n)]
    del n_scores[(n, merge_from)]

  merge_cells(merge_from, merge_to)

  for n in n_graph[merge_to]:
    n_scores[(n, merge_to)] = score(n, merge_to)
    n_scores[(merge_to, n)] = score(merge_to, n)

if OUTPUT_ALL:
  frame_im = Image.new("RGB", im.size)

  for cellnum in cell_sets:
    cell_color = cell_means[cellnum]

    for pixel in cell_sets[cellnum]:
      frame_im.putpixel(pixel, lab2rgb(cell_color))

  frame_im.save(OUTFILE_STEM + "3.png")
  print "Saved image %s3.png" % OUTFILE_STEM

del n_graph, n_scores

print "Stage 5: N-merging complete, %d cells" % len(cell_sets)

"""
Stage 6: P merging - use k-means
"""

def form_clusters(centroids):
  clusters = defaultdict(set)

  for cellnum in cell_sets:
    # Add cell to closest centroid.
    scores = []

    for centroid in centroids:
      scores.append((d(centroid, cell_means[cellnum]), centroid))

    scores.sort()
    clusters[scores[0][1]].add(cellnum)

  return clusters

def calculate_centroid(cluster):
  L_sum = 0
  a_sum = 0
  b_sum = 0

  weighting = 0

  for cellnum in cluster:
    # Weight based on cell size
    color = cell_means[cellnum]
    cell_weight = len(cell_sets[cellnum])**.5

    L_sum += color[0]*cell_weight
    a_sum += color[1]*cell_weight
    b_sum += color[2]*cell_weight

    weighting += cell_weight

  return (L_sum/weighting, a_sum/weighting, b_sum/weighting)

def db_index(clusters):
  # Davies-Bouldin index
  scatter = {}

  for centroid, cluster in clusters.items():
    scatter_score = 0

    for cellnum in cluster:
      scatter_score += d(cell_means[cellnum], centroid) * len(cell_sets[cellnum])**.5

    scatter_score /= len(cluster)
    scatter[centroid] = scatter_score**2 # Mean squared distance

  index = 0

  for ci, cluster in clusters.items():
    dist_scores = []

    for cj in clusters:
      if ci != cj:
        dist_scores.append((scatter[ci] + scatter[cj])/d(ci, cj))

    index += max(dist_scores)

  return index

best_clusters = None
best_index = None

for i in X(K_MEANS_TRIALS):  
  centroids = {cell_means[cellnum] for cellnum in random.sample(cell_sets, P)}
  converged = False

  while not converged:
    clusters = form_clusters(centroids)
    new_centroids = {calculate_centroid(cluster) for cluster in clusters.values()}

    if centroids == new_centroids:
      converged = True

    centroids = new_centroids

  index = db_index(clusters)

  if best_index is None or index < best_index:
    best_index = index
    best_clusters = clusters

del cell_means
newpix_map = {}

for centroid, cluster in best_clusters.items():
  for cellnum in cluster:
    for pixel in cell_sets[cellnum]:
      newpix_map[pixel] = centroid

if OUTPUT_ALL:
  frame_im = Image.new("RGB", im.size)

  for pixel in newpix_map:
    frame_im.putpixel(pixel, lab2rgb(newpix_map[pixel]))

  frame_im.save(OUTFILE_STEM + "4.png")
  print "Saved image %s4.png" % OUTFILE_STEM

print "Stage 6: P-merging complete"

"""
Stage 7: Approximate Gaussian smoothing
     See http://blog.ivank.net/fastest-gaussian-blur.html
"""

# Hindsight tells me I should have used a class. I hate hindsight.
def vec_sum(vectors):
  assert(vectors and all(len(v) == len(vectors[0]) for v in vectors))
  return tuple(sum(x[i] for x in vectors) for i in X(len(vectors[0])))

def linear_blur(color_list):
  # Can be made faster with an accumulator
  output = []

  for i in X(len(color_list)):
    relevant_pixels = color_list[max(i-BLUR_RADIUS+1, 0):i+BLUR_RADIUS]
    pixsum = vec_sum(relevant_pixels)
    output.append(tuple(pixsum[i]/len(relevant_pixels) for i in X(3)))

  return output

def horizontal_blur():
  for row in X(height):
    colors = [blurpix_map[(i, row)] for i in X(width)]
    colors = linear_blur(colors)

    for i in X(width):
      blurpix_map[(i, row)] = colors[i]

def vertical_blur():
  for column in X(width):
    colors = [blurpix_map[(column, j)] for j in X(height)]
    colors = linear_blur(colors)

    for j in X(height):
      blurpix_map[(column, j)] = colors[j]

blurpix_map = {}

for i in X(width):
  for j in X(height):
    blurpix_map[(i, j)] = newpix_map[(i, j)]

for i in X(BLUR_RUNS):
  vertical_blur()
  horizontal_blur()

# Pixel : color of smoothed image
smoothpix_map = {}

for i in X(width):
  for j in X(height):
    pixel = (i, j)
    blur_color = blurpix_map[pixel]
    nearby_colors = {newpix_map[pixel]}

    for n in neighbours(pixel):
      nearby_colors.add(newpix_map[n])

    smoothpix_map[pixel] = min(nearby_colors, key=lambda x: d(x, blur_color))

del newpix_map, blurpix_map

if OUTPUT_ALL:
  frame_im = Image.new("RGB", im.size)

  for pixel in smoothpix_map:
    frame_im.putpixel(pixel, lab2rgb(smoothpix_map[pixel]))

  frame_im.save(OUTFILE_STEM + "5.png")
  print "Saved image %s5.png" % OUTFILE_STEM

print "Stage 7: Smoothing complete"

"""
Stage 8: Flood fill pass 2
     Code copy-and-paste because I'm lazy
"""

def flood_fill(start_pixel):
  to_search = {start_pixel}
  cell = set()
  searched = set()
  start_color = smoothpix_map[start_pixel]

  while to_search:
    pixel = to_search.pop()

    if start_color == smoothpix_map[pixel]:
      cell.add(pixel)
      unplaced_pixels.remove(pixel)

      for n in neighbours(pixel):
        if n in unplaced_pixels and n not in cell and n not in searched:
          to_search.add(n)

    else:
      searched.add(pixel)

  return cell

cell_sets = {}
pixcell_map = {}
unplaced_pixels = {(i, j) for i in X(width) for j in X(height)}

while unplaced_pixels:
  start_pixel = unplaced_pixels.pop()
  unplaced_pixels.add(start_pixel)
  cell = flood_fill(start_pixel)

  cellnum = len(cell_sets)
  cell_sets[cellnum] = cell

  for pixel in cell:
    pixcell_map[pixel] = cellnum

cell_colors = {}

for cellnum in cell_sets:
  cell_colors[cellnum] = smoothpix_map[next(iter(cell_sets[cellnum]))]

print "Stage 8: Flood fill pass 2 complete, %d cells" % len(cell_sets)

"""
Stage 9: Small cell removal pass 2
"""

def score(cell1, cell2):
  return d(cell_colors[cell1], cell_colors[cell2]) * len(cell_sets[cell1])**.5

def remove_small(cell_size):  
  small_cells = []

  for cellnum in cell_sets:
    if len(cell_sets[cellnum]) <= cell_size:
      small_cells.append(cellnum)

  for cellnum in small_cells:
    neighbour_cells = []

    for cell in cell_sets[cellnum]:
      for n in neighbours(cell):
        neighbour_reg = pixcell_map[n]

        if neighbour_reg != cellnum:
          neighbour_cells.append(neighbour_reg)

    closest_cell = max(neighbour_cells, key=neighbour_cells.count)

    for cell in cell_sets[cellnum]:
      pixcell_map[cell] = closest_cell

    if len(cell_sets[closest_cell]) <= cell_size:
      small_cells.remove(closest_cell)

    cell_color = cell_colors[closest_cell]

    for pixel in cell_sets[cellnum]:
      smoothpix_map[pixel] = cell_color

    cell_sets[closest_cell] |= cell_sets[cellnum]
    del cell_sets[cellnum]
    del cell_colors[cellnum]

for cell_size in X(1, SMALL_CELL_THRESHOLD):
  remove_small(cell_size)

if OUTPUT_ALL:
  frame_im = Image.new("RGB", im.size)

  for pixel in smoothpix_map:
    frame_im.putpixel(pixel, lab2rgb(smoothpix_map[pixel]))

  frame_im.save(OUTFILE_STEM + "6.png")
  print "Saved image %s6.png" % OUTFILE_STEM

print "Stage 9: Small cell removal pass 2 complete, %d cells" % len(cell_sets)

"""
Stage 10: N-merging pass 2
     Necessary as stage 7 might generate *more* cells
"""

def merge_cells(merge_from, merge_to):
  merge_from_cell = cell_sets[merge_from]

  for pixel in merge_from_cell:
    pixcell_map[pixel] = merge_to

  del cell_sets[merge_from]
  del cell_colors[merge_from]

  n_graph[merge_to] |= n_graph[merge_from]
  n_graph[merge_to].remove(merge_to)

  for n in n_graph[merge_from]:
    n_graph[n].remove(merge_from)

    if n != merge_to:
      n_graph[n].add(merge_to)

  del n_graph[merge_from]

  cell_color = cell_colors[merge_to]

  for pixel in merge_from_cell:
    smoothpix_map[pixel] = cell_color

  cell_sets[merge_to] |= merge_from_cell

n_graph = defaultdict(set)

for i in X(width):
  for j in X(height):
    pixel = (i, j)
    cell = pixcell_map[pixel]

    for n in neighbours(pixel):
      neighbour_cell = pixcell_map[n]

      if neighbour_cell != cell:
        n_graph[cell].add(neighbour_cell)
        n_graph[neighbour_cell].add(cell)

n_scores = {}

for cellnum in cell_sets:
  for n in n_graph[cellnum]:
    n_scores[(n, cellnum)] = score(n, cellnum)

last_time = time.time()

while len(cell_sets) > N:
  if time.time() - last_time > 15:
    last_time = time.time()
    print "N-merging (pass 2)... (%d cells remaining)" % len(cell_sets)

  merge_from, merge_to = min(n_scores, key=lambda x: n_scores[x])

  for n in n_graph[merge_from]:
    del n_scores[(merge_from, n)]
    del n_scores[(n, merge_from)]

  merge_cells(merge_from, merge_to)

  for n in n_graph[merge_to]:
    n_scores[(n, merge_to)] = score(n, merge_to)
    n_scores[(merge_to, n)] = score(merge_to, n)

print "Stage 10: N-merging pass 2 complete, %d cells" % len(cell_sets)

"""
Stage last: Output the image!
"""

test_im = Image.new("RGB", im.size)

for i in X(width):
  for j in X(height):
    test_im.putpixel((i, j), lab2rgb(smoothpix_map[(i, j)]))

if OUTPUT_ALL:
  test_im.save(OUTFILE_STEM + "7.png")
else:
  test_im.save(OUTFILE_STEM + ".png")

print "Done! (Time taken: {})".format(time.time() - total_time)

Время обновления! Это обновление имеет простой алгоритм сглаживания, чтобы сделать изображение менее размытым. Если я обновлюсь снова, мне придется переделывать значительную часть моего кода, хотя, потому что он становится грязным, и я собираюсь изменить его.

Я также сделал весовые коэффициенты k-средних на основе размеров ячеек, что приводит к потере некоторых деталей для более ограничительных параметров (например, центра туманности и вил американской готики), но делает общий выбор цветов более четким и приятным. Интересно, что он теряет весь фон для трассированных лучей сфер при P = 5.

Краткое изложение алгоритма:

1. Преобразуйте пиксели в цветовое пространство CIELAB: CIELAB приближает человеческое зрение лучше, чем RGB. Первоначально я использовал HSL (оттенок, насыщенность, яркость), но у него были две проблемы - оттенок белого / серого / черного не определен, а оттенок измеряется в градусах, которые обертывают вокруг, что затрудняет использование k-средних.
2. Разделите изображение на ячейки одинакового цвета, используя заливку. Выберите пиксель, находящийся не в ячейке, и выполните заливку, используя заданный допуск. Для измерения расстояния между двумя цветами я использую стандартную евклидову норму. Более сложные формулы доступны в этой статье вики .
3. Объединение небольших ячеек с их соседями : заливка заливки генерирует много ячеек размером в 1 или 2 пикселя - объединяет ячейки меньше указанного размера с соседней ячейкой с наибольшим количеством смежных пикселей. Это значительно уменьшает количество ячеек, улучшая время выполнения для последующих шагов.
4. Объедините области одинакового цвета : пройдите по клеткам в порядке уменьшения размера. Если любая соседняя ячейка имеет средний цвет менее чем на определенном расстоянии, объедините ячейки. Продолжайте проходить через ячейки, пока больше не сможете объединиться.
5. Объединяйте до тех пор, пока у нас не будет меньше 1,5N ячеек (N-объединение) : объединяйте ячейки вместе, используя оценку, основанную на размерах ячеек и разнице в цвете, до тех пор, пока мы не получим не более 1,5N ячеек. Мы даем немного свободы, так как мы снова слиться позже.
6. Объединяйте до тех пор, пока у нас не будет меньше P цветов, используя k-means (P-merging) : Используйте алгоритм кластеризации k-средних несколько раз определенное количество раз, чтобы генерировать кластеризации цветов ячеек, взвешивая на основе размера ячеек. Оцените каждую кластеризацию на основе вариации индекса Дэвиса-Болдина и выберите лучшую кластеризацию для использования.
7. Приблизительное сглаживание по Гауссу : используйте несколько линейных размытий, чтобы приблизить размытие по Гауссу ( подробности здесь ). Затем для каждого пикселя выберите цвет самого себя и его соседей на предварительно размытом изображении, ближайший к его цвету на размытом изображении. Эта часть может быть оптимизирована с точки зрения времени, если это необходимо, поскольку мне еще предстоит реализовать оптимальный алгоритм.
8. Сделайте еще один проход заливки, чтобы проработать новые регионы : это необходимо, так как предыдущий шаг может фактически генерировать больше ячеек.
9. Сделайте еще один маленький проход ячейки слияния
10. Сделайте еще один проход N-слияния : на этот раз мы опустимся до N клеток, а не до 1,5N.

Время обработки каждого изображения в значительной степени зависит от его размера и сложности, а время для тестовых изображений составляет от 20 секунд до 7 минут.

Поскольку алгоритм использует рандомизацию (например, слияние, k-средних), вы можете получить разные результаты на разных прогонах. Вот сравнение двух серий для изображения медведя с N = 50 и P = 10:

Примечание: все изображения ниже являются ссылками. Большинство этих изображений прямо с первого запуска, но если мне не понравился результат, я позволил себе до трех попыток быть честным.

N = 50, P = 10

N = 500, P = 30

Но я довольно ленив, когда дело доходит до рисования цветами, так что просто для удовольствия ...

N = 20, P = 5

Кроме того, забавно видеть, что происходит, когда вы пытаетесь сжать 1 миллион цветов в N = 500, P = 30:

Вот пошаговое пошаговое руководство по алгоритму для подводного изображения с N = 500 и P = 30 в анимированной форме GIF:

Я также сделал галерею для предыдущих версий алгоритма здесь . Вот некоторые из моих любимых из последней версии (с того момента, когда на туманности было больше звезд, а медведь выглядел более меховым):

Python 2 с PIL

Также решение Python и, вероятно, очень много в стадии разработки:

from PIL import Image, ImageFilter
import random

def draw(file_name, P, N, M=3):
    img = Image.open(file_name, 'r')
    pixels = img.load()
    size_x, size_y = img.size

    def dist(c1, c2):
        return (c1[0]-c2[0])**2+(c1[1]-c2[1])**2+(c1[2]-c2[2])**2

    def mean(colours):
        n = len(colours)
        r = sum(c[0] for c in colours)//n
        g = sum(c[1] for c in colours)//n
        b = sum(c[2] for c in colours)//n
        return (r,g,b)

    def colourize(colour, palette):
        return min(palette, key=lambda c: dist(c, colour))

    def cluster(colours, k, max_n=10000, max_i=10):
        colours = random.sample(colours, max_n)
        centroids = random.sample(colours, k)
        i = 0
        old_centroids = None
        while not(i>max_i or centroids==old_centroids):
            old_centroids = centroids
            i += 1
            labels = [colourize(c, centroids) for c in colours]
            centroids = [mean([c for c,l in zip(colours, labels)
                               if l is cen]) for cen in centroids]
        return centroids

    all_coords = [(x,y) for x in xrange(size_x) for y in xrange(size_y)]
    all_colours = [pixels[x,y] for x,y in all_coords]
    palette = cluster(all_colours, P)
    print 'clustered'

    for x,y in all_coords:
        pixels[x,y] = colourize(pixels[x,y], palette)
    print 'colourized'

    median_filter = ImageFilter.MedianFilter(size=M)
    img = img.filter(median_filter)
    pixels = img.load()
    for x,y in all_coords:
        pixels[x,y] = colourize(pixels[x,y], palette)
    print 'median filtered'

    def neighbours(edge, outer, colour=None):
        return set((x+a,y+b) for x,y in edge
                   for a,b in ((1,0), (-1,0), (0,1), (0,-1))
                   if (x+a,y+b) in outer
                   and (colour==None or pixels[(x+a,y+b)]==colour))

    def cell(centre, rest):
        colour = pixels[centre]
        edge = set([centre])
        region = set()
        while edge:
            region |= edge
            rest = rest-edge
            edge = set(n for n in neighbours(edge, rest, colour))
        return region, rest

    print 'start segmentation:'
    rest = set(all_coords)
    cells = []
    while rest:
        centre = random.sample(rest, 1)[0]
        region, rest = cell(centre, rest-set(centre))
        cells += [region]
        print '%d pixels remaining'%len(rest)
    cells = sorted(cells, key=len, reverse=True)
    print 'segmented (%d segments)'%len(cells)

    print 'start merging:'
    while len(cells)>N:
        small_cell = cells.pop()
        n = neighbours(small_cell, set(all_coords)-small_cell)
        for big_cell in cells:
            if big_cell & n:
                big_cell |= small_cell
                break
        print '%d segments remaining'%len(cells)
    print 'merged'

    for cell in cells:
        colour = colourize(mean([pixels[x,y] for x,y in cell]), palette)
        for x,y in cell:
            pixels[x,y] = colour
    print 'colorized again'

    img.save('P%d N%d '%(P,N)+file_name)
    print 'saved'

draw('a.png', 11, 500, 1)

Алгоритм следует другому подходу, нежели SP3000, начиная с цветов:

• Найдите цветовую палитру P цветов с помощью k-средних кластеров и раскрасьте изображение в этой уменьшенной палитре.

• Примените небольшой средний фильтр, чтобы избавиться от шума.

• Составьте список всех монохроматических ячеек и отсортируйте их по размеру.

• Объединяйте наименьшие ячейки с соответствующими соседями, пока не останется только N ячеек.

Существует достаточно возможностей для улучшения, как с точки зрения скорости, так и качества результатов. Особенно этап слияния клеток может занимать много минут и дает далеко не оптимальные результаты.

P = 5, N = 45

P = 10, N = 50

P = 4, N = 250

P = 11, N = 500

Mathematica

В данный момент для этого требуется количество цветов и гауссов радиус, которые будут использоваться в фильтре Гаусса. Чем больше радиус, тем больше размытие и слияние цветов.

Поскольку он не позволяет вводить количество ячеек, он не соответствует одному из основных требований задачи.

Вывод включает в себя количество ячеек для каждого цвета, а также общее количество ячеек.

quantImg[img_,nColours_,gaussR_]:=ColorQuantize[GaussianFilter[img,gaussR],nColours,
Dithering-> False]

colours[qImg_]:=Union[Flatten[ImageData[qImg],1]]

showColors[image_,nColors_,gaussR_]:=
   Module[{qImg,colors,ca,nCells},
   qImg=quantImg[image,nColors,gaussR];
   colors=colours[qImg];
   ca=ConstantArray[0,Reverse@ImageDimensions[image]];
   nCells[qImgg_,color_]:=
   Module[{r},
   r=ReplacePart[ca,Position[ImageData@qImg,color]/.{a_,b_}:> ({a,b}->1)];
   (*ArrayPlot[r,ColorRules->{1\[Rule]RGBColor[color],0\[Rule]White}];*)
   m=MorphologicalComponents[r];
   {RGBColor@color,Max[Union@Flatten[m,1]]}];
   s=nCells[qImg,#]&/@colors;
   Grid[{
    {Row[{s}]}, {Row[{"cells:\t\t",Tr[s[[All,2]]]}]},{Row[{"colors:\t\t",nColors}]},
    {Row[{"Gauss. Radius: ", gaussR}]}},Alignment->Left]]

Обновить

quantImage2позволяет указать желаемое количество ячеек в качестве входных данных. Он определяет лучший радиус Гаусса, просматривая сценарии с большими радиусами, пока не будет найдено близкое соответствие.

quantImage2 выходы (изображение, запрошенные ячейки, использованные ячейки, ошибка, использованный радиус Гаусса).

Это, однако, очень медленно. Чтобы сэкономить время, вы можете начать с начального радиуса, значение по умолчанию которого равно 0.

gaussianRadius[img_,nCol_,nCells_,initialRadius_:0]:=
Module[{radius=initialRadius,nc=10^6,results={},r},
While[nc>nCells,(nc=numberOfCells[ape,nColors,radius]);
results=AppendTo[results,{nColors,radius,nc}];radius++];
r=results[[{-2,-1}]];
Nearest[r[[All,3]],200][[1]];
Cases[r,{_,_,Nearest[r[[All,3]],nCells][[1]]}][[1,2]]
]

quantImg2[img_,nColours_,nCells1_,initialRadius_:0]:={ColorQuantize[GaussianFilter[img,
g=gaussianRadius[img,nColours,nCells1,initialRadius]],nColours,Dithering->False],
nCells1,nn=numberOfCells[img,nColours,g],N[(nn-nCells1)/nCells1],g}

Пример, для которого мы указываем желаемое количество ячеек в выводе.

Пример запроса 90 ячеек с 25 цветами. Решение возвращает 88 клеток, ошибка 2%. Функция выбрала радиус Гаусса 55. (много искажений).

Примеры, для которых ввод включает в себя радиус Гаусса, но не количество ячеек.

25 цветов, гауссов радиус 5 пикселей

nColors = 25;
gR = 5;
quantImg[balls, nColors, gR]

Три цвета, радиус 17 пикселей

nColors=3;gaussianRadius=17;
showColors[wave,nColors,gaussianRadius]
quantImg[wave,nColors,gaussianRadius]

Двадцать цветов, радиус 17 пикселей

Мы увеличили количество цветов, но не фокус. Обратите внимание на увеличение количества клеток.

Шесть цветов, радиус 4 пикселя

nColors=6;gaussianRadius=4;
showColors[wave,nColors,gaussianRadius]
quantImg[wave,nColors,gaussianRadius]

nColors = 6; gaussianRadius = 17;
showColors[ape, nColors, gaussianRadius]
quantImg[ape, nColors, gaussianRadius]

nColors = 6; gaussianRadius = 3;
showColors[ape, nColors, gaussianRadius]
quantImg[ape, nColors, gaussianRadius]

Звездная ночь

Всего 6 цветов и 60 ячеек. Существует несоответствие цветов в цветах, которые showColorsон использует. (Желтый не появляется среди 5 цветов, но он используется на рисунке.) Я посмотрю, смогу ли я понять это.

Python 2 с PIL

Это все еще в стадии разработки. Кроме того, приведенный ниже код представляет собой ужасный беспорядок спагетти, и его не следует использовать в качестве вдохновения. :)

from PIL import Image, ImageFilter
from math import sqrt
from copy import copy
from random import shuffle, choice, seed

IN_FILE = "input.png"
OUT_FILE = "output.png"

LOGGING = True
GRAPHICAL_LOGGING = False
LOG_FILE_PREFIX = "out"
LOG_FILE_SUFFIX = ".png"
LOG_ROUND_INTERVAL = 150
LOG_FLIP_INTERVAL = 40000

N = 500
P = 30
BLUR_RADIUS = 3
FILAMENT_ROUND_INTERVAL = 5
seed(0) # Random seed

print("Opening input file...")

image = Image.open(IN_FILE).filter(ImageFilter.GaussianBlur(BLUR_RADIUS))
pixels = {}
width, height = image.size

for i in range(width):
    for j in range(height):
        pixels[(i, j)] = image.getpixel((i, j))

def dist_rgb((a,b,c), (d,e,f)):
    return (a-d)**2 + (b-e)**2 + (c-f)**2

def nbors((x,y)):
    if 0 < x:
        if 0 < y:
            yield (x-1,y-1)
        if y < height-1:
            yield (x-1,y+1)
    if x < width - 1:
        if 0 < y:
            yield (x+1,y-1)
        if y < height-1:
            yield (x+1,y+1)

def full_circ((x,y)):
    return ((x+1,y), (x+1,y+1), (x,y+1), (x-1,y+1), (x-1,y), (x-1,y-1), (x,y-1), (x+1,y-1))

class Region:

    def __init__(self):
        self.points = set()
        self.size = 0
        self.sum = (0,0,0)

    def flip_point(self, point):
        sum_r, sum_g, sum_b = self.sum
        r, g, b = pixels[point]
        if point in self.points:
            self.sum = (sum_r - r, sum_g - g, sum_b - b)
            self.size -= 1
            self.points.remove(point)
        else:
            self.sum = (sum_r + r, sum_g + g, sum_b + b)
            self.size += 1
            self.points.add(point)

    def mean_with(self, color):
        if color is None:
            s = float(self.size)
            r, g, b = self.sum
        else:
            s = float(self.size + 1)
            r, g, b = map(lambda a,b: a+b, self.sum, color)
        return (r/s, g/s, b/s)

print("Initializing regions...")

aspect_ratio = width / float(height)
a = int(sqrt(N)*aspect_ratio)
b = int(sqrt(N)/aspect_ratio)

num_components = a*b
owners = {}
regions = [Region() for i in range(P)]
borders = set()

nodes = [(i,j) for i in range(a) for j in range(b)]
shuffle(nodes)
node_values = {(i,j):None for i in range(a) for j in range(b)}

for i in range(P):
    node_values[nodes[i]] = regions[i]

for (i,j) in nodes[P:]:
    forbiddens = set()
    for node in (i,j-1), (i,j+1), (i-1,j), (i+1,j):
        if node in node_values and node_values[node] is not None:
            forbiddens.add(node_values[node])
    node_values[(i,j)] = choice(list(set(regions) - forbiddens))

for (i,j) in nodes:
    for x in range((width*i)/a, (width*(i+1))/a):
        for y in range((height*j)/b, (height*(j+1))/b):
            owner = node_values[(i,j)]
            owner.flip_point((x,y))
            owners[(x,y)] = owner

def recalc_borders(point = None):
    global borders
    if point is None:
        borders = set()
        for i in range(width):
            for j in range(height):
                if (i,j) not in borders:
                    owner = owner_of((i,j))
                    for pt in nbors((i,j)):
                        if owner_of(pt) != owner:
                            borders.add((i,j))
                            borders.add(pt)
                            break
    else:
        for pt in nbors(point):
            owner = owner_of(pt)
            for pt2 in nbors(pt):
                if owner_of(pt2) != owner:
                    borders.add(pt)
                    break
            else:
                borders.discard(pt)

def owner_of(point):
    if 0 <= point[0] < width and 0 <= point[1] < height:
        return owners[point]
    else:
        return None

# Status codes for analysis
SINGLETON = 0
FILAMENT = 1
SWAPPABLE = 2
NOT_SWAPPABLE = 3

def analyze_nbors(point):
    owner = owner_of(point)
    circ = a,b,c,d,e,f,g,h = full_circ(point)
    oa,ob,oc,od,oe,of,og,oh = map(owner_of, circ)
    nbor_owners = set([oa,oc,oe,og])
    if owner not in nbor_owners:
        return SINGLETON, owner, nbor_owners - set([None])
    if oc != oe == owner == oa != og != oc:
        return FILAMENT, owner, set([og, oc]) - set([None])
    if oe != oc == owner == og != oa != oe:
        return FILAMENT, owner, set([oe, oa]) - set([None])
    last_owner = oa
    flips = {last_owner:0}
    for (corner, side, corner_owner, side_owner) in (b,c,ob,oc), (d,e,od,oe), (f,g,of,og), (h,a,oh,oa):
        if side_owner not in flips:
            flips[side_owner] = 0
        if side_owner != corner_owner or side_owner != last_owner:
            flips[side_owner] += 1
            flips[last_owner] += 1
        last_owner = side_owner
    candidates = set(own for own in flips if flips[own] == 2 and own is not None)
    if owner in candidates:
        return SWAPPABLE, owner, candidates - set([owner])
    return NOT_SWAPPABLE, None, None

print("Calculating borders...")

recalc_borders()

print("Deforming regions...")

def assign_colors():
    used_colors = {}
    for region in regions:
        r, g, b = region.mean_with(None)
        r, g, b = int(round(r)), int(round(g)), int(round(b))
        if (r,g,b) in used_colors:
            for color in sorted([(r2, g2, b2) for r2 in range(256) for g2 in range(256) for b2 in range(256)], key=lambda color: dist_rgb(color, (r,g,b))):
                if color not in used_colors:
                    used_colors[color] = region.points
                    break
        else:
            used_colors[(r,g,b)] = region.points
    return used_colors

def make_image(colors):
    img = Image.new("RGB", image.size)
    for color in colors:
        for point in colors[color]:
            img.putpixel(point, color)
    return img

# Round status labels
FULL_ROUND = 0
NEIGHBOR_ROUND = 1
FILAMENT_ROUND = 2

max_filament = None
next_search = set()
rounds = 0
points_flipped = 0
singletons = 0
filaments = 0
flip_milestone = 0
logs = 0

while True:
    if LOGGING and (rounds % LOG_ROUND_INTERVAL == 0 or points_flipped >= flip_milestone):
        print("Round %d of deformation:\n %d edit(s) so far, of which %d singleton removal(s) and %d filament cut(s)."%(rounds, points_flipped, singletons, filaments))
        while points_flipped >= flip_milestone: flip_milestone += LOG_FLIP_INTERVAL
        if GRAPHICAL_LOGGING:
            make_image(assign_colors()).save(LOG_FILE_PREFIX + str(logs) + LOG_FILE_SUFFIX)
            logs += 1
    if max_filament is None or (round_status == NEIGHBOR_ROUND and rounds%FILAMENT_ROUND_INTERVAL != 0):
        search_space, round_status = (next_search & borders, NEIGHBOR_ROUND) if next_search else (copy(borders), FULL_ROUND)
        next_search = set()
        max_filament = None
    else:
        round_status = FILAMENT_ROUND
        search_space = set([max_filament[0]]) & borders
    search_space = list(search_space)
    shuffle(search_space)
    for point in search_space:
        status, owner, takers = analyze_nbors(point)
        if (status == FILAMENT and num_components < N) or status in (SINGLETON, SWAPPABLE):
            color = pixels[point]
            takers_list = list(takers)
            shuffle(takers_list)
            for taker in takers_list:
                dist = dist_rgb(color, owner.mean_with(None)) - dist_rgb(color, taker.mean_with(color))
                if dist > 0:
                    if status != FILAMENT or round_status == FILAMENT_ROUND:
                        found = True
                        owner.flip_point(point)
                        taker.flip_point(point)
                        owners[point] = taker
                        recalc_borders(point)
                        next_search.add(point)
                        for nbor in full_circ(point):
                            next_search.add(nbor)
                        points_flipped += 1
                    if status == FILAMENT:
                        if round_status == FILAMENT_ROUND:
                            num_components += 1
                            filaments += 1
                        elif max_filament is None or max_filament[1] < dist:
                            max_filament = (point, dist)
                    if status == SINGLETON:
                        num_components -= 1
                        singletons += 1
                    break
    rounds += 1
    if round_status == FILAMENT_ROUND:
        max_filament = None
    if round_status == FULL_ROUND and max_filament is None and not next_search:
        break

print("Deformation completed after %d rounds:\n %d edit(s), of which %d singleton removal(s) and %d filament cut(s)."%(rounds, points_flipped, singletons, filaments))

print("Assigning colors...")

used_colors = assign_colors()

print("Producing output...")

make_image(used_colors).save(OUT_FILE)

print("Done!")

Как это работает

Программа делит холст на Pобласти, каждая из которых состоит из некоторого количества ячеек без отверстий. Изначально холст просто делится на приблизительные квадраты, которые случайным образом назначаются регионам. Затем эти области «деформируются» в итеративном процессе, где данный пиксель может изменить свою область, если

1. изменение уменьшило бы расстояние RGB пикселя от среднего цвета области, которая его содержит, и
2. это не ломает или объединяет ячейки или вводит отверстия в них.

Последнее условие может быть применено локально, поэтому процесс немного напоминает клеточный автомат. Таким образом, нам не нужно выполнять поиск пути или что-то подобное, что значительно ускоряет процесс. Однако, поскольку клетки не могут быть разрушены, некоторые из них в конечном итоге становятся длинными "нитями", которые граничат с другими клетками и препятствуют их росту. Чтобы это исправить, существует процесс, называемый «разрезание нити», который иногда разбивает ячейку в форме нити на две части, если Nв это время клеток меньше . Клетки также могут исчезнуть, если их размер равен 1, и это освобождает место для порезов нитей.

Процесс заканчивается, когда ни у одного пикселя нет стимула для переключения областей, и после этого каждая область просто окрашивается своим средним цветом. Обычно на выходе остаются нити, как видно из приведенных ниже примеров, особенно в туманности.

P = 30, N = 500

Больше фотографий позже.

Некоторые интересные свойства моей программы заключаются в том, что она вероятностная, поэтому результаты могут отличаться в зависимости от разных прогонов, если, конечно, вы не используете одно и то же псевдослучайное начальное число. Случайность не является существенной, однако, я просто хотел избежать любых случайных артефактов, которые могут возникнуть в результате того, как Python пересекает набор координат или что-то подобное. Программа имеет тенденцию использовать все Pцвета и почти все Nячейки, и ячейки никогда не содержат отверстий по дизайну. Кроме того, процесс деформации довольно медленный. Цветные шары заняли почти 15 минут, чтобы произвести на моей машине. С другой стороны, вы включаетеGRAPHICAL_LOGGINGвариант, вы получите классную серию фотографий процесса деформации. Я сделал из Mona Lisa анимацию в формате GIF (уменьшил на 50%, чтобы уменьшить размер файла). Если вы присмотритесь к ее лицу и волосам, вы сможете увидеть процесс резки нитей в действии.