Malen nach Zahlen

42

Sie erhalten ein Echtfarbenbild. Ihre Aufgabe ist es, eine Version dieses Bildes zu erstellen, die aussieht, als wäre es mit Hilfe von Malen nach Zahlen gemalt worden (die Aktivität der Kinder, keine Nonogramme). Zusammen mit dem Bild erhalten Sie zwei Parameter: P , die maximale Größe der Farbpalette (dh die maximale Anzahl der zu verwendenden Farben) und N , die maximale Anzahl der zu verwendenden Zellen . Ihr Algorithmus muss nicht alle P- Farben und N- Zellen verwenden, es darf jedoch nicht mehr verwendet werden. Das Ausgabebild sollte die gleichen Abmessungen wie das Eingabebild haben.

Eine Zelle ist als zusammenhängender Bereich von Pixeln definiert, die alle die gleiche Farbe haben. Pixel, die sich nur an einer Ecke berühren, werden nicht als zusammenhängend betrachtet. Zellen können Löcher haben.

Kurz gesagt, Sie müssen das Eingabebild mit nur N flach schattierten / einfarbigen Bereichen und P verschiedenen Farben approximieren.

Nur um die Parameter zu veranschaulichen, ist hier ein sehr einfaches Beispiel (für kein bestimmtes Eingabebild; zeige meine verrückten Malfähigkeiten). Das folgende Bild hat P = 6 und N = 11 :

Bildbeschreibung hier eingeben

Hier sind ein paar Bilder, mit denen Sie Ihren Algorithmus testen können (meistens unsere üblichen Verdächtigen). Klicken Sie auf die Bilder für größere Versionen.

Große Welle Korallenriff Regenbogen Sternenklare Nacht Fluss Braunbär Wasserfall Mandrill Krebsnebel Amerikanische Gotik Mona Lisa Schrei

Bitte geben Sie eine Handvoll Ergebnisse für verschiedene Parameter an. Wenn Sie eine große Anzahl von Ergebnissen anzeigen möchten , können Sie auf imgur.com eine Galerie erstellen , um die Größe der Antworten angemessen zu halten. Alternativ können Sie Thumbnails in Ihren Beitrag einfügen und diese wie oben beschrieben mit größeren Bildern verknüpfen. Sie können auch andere Testbilder verwenden, wenn Sie etwas Schönes finden.

Ich gehe davon aus, dass Parameter um N ≥ 500 , P ~ 30 den realen Paint-by-Number-Vorlagen ähneln.

Dies ist ein Beliebtheitswettbewerb, daher gewinnt die Antwort mit den meisten Netto-Stimmen. Die Wähler werden aufgefordert, die Antworten nach zu beurteilen

  • Wie gut sind die Originalbilder angenähert.
  • Wie gut der Algorithmus auf verschiedenen Arten von Bildern funktioniert (Bilder sind wahrscheinlich im Allgemeinen einfacher als Fotos).
  • wie gut der Algorithmus mit sehr restriktiven Parametern arbeitet.
  • wie organisch / glatt die Zellformen aussehen.

Ich werde das folgende Mathematica-Skript verwenden, um die Ergebnisse zu validieren:

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 war so nett, einen Verifizierer in Python 2 mit PIL zu schreiben, den Sie in diesem Pastebin finden .

Martin Ender
quelle
2
Nicht die effizienteste Sache, aber hier ist ein Python 2 PIL-Verifizierer .
Sp3000
Was für eine schöne Frage, aber ich hatte gehofft, wir würden auch die richtige Version "Malen nach Zahlen" sehen. Das ist mit Zahlen an Ort und Stelle, so dass ich die Antworten verwenden könnte :)
@Lembik Eigentlich wollte ich das mit einbeziehen, aber ich hatte das Gefühl, dass es vom interessanten Teil der Frage ablenkt. Es sollte jedoch nicht zu schwierig sein, die Ausgabe einer der Übermittlungen in eine Vorlage umzuwandeln.
Martin Ender
Dies ist ein faszinierender Beitrag. Hat jemand den zusätzlichen Schritt des Hinzufügens der Farbnummern wie ein tatsächliches Malen nach Zahlen gegangen?
B. Blair

Antworten:

39

Python 2 mit PIL ( Galerie )

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)

Updatezeit! Dieses Update enthält einen einfachen Glättungsalgorithmus, mit dem Bilder weniger unscharf wirken. Wenn ich erneut aktualisiere, muss ich allerdings einen angemessenen Teil meines Codes überarbeiten, da er unordentlich wird und ich einen Fehler behebe.

Ich habe auch Farben mit einem Gewicht von k-means basierend auf der Zellgröße erstellt, wodurch einige Details für restriktivere Parameter (z. B. die Mitte des Nebels und die Heugabel der amerikanischen Gotik) verloren gehen, aber die Farbauswahl insgesamt schärfer und schöner wird. Interessanterweise verliert es den gesamten Hintergrund für Raytrace-Kugeln für P = 5.

Algorithmuszusammenfassung:

  1. Konvertieren Sie die Pixel in den CIELAB-Farbraum : CIELAB approximiert das menschliche Sehen besser als RGB. Ursprünglich verwendete ich HSL (Farbton, Sättigung, Helligkeit), aber dies hatte zwei Probleme: Der Farbton Weiß / Grau / Schwarz ist undefiniert, und der Farbton wird in Grad gemessen, die sich umschließen, was die Verwendung von k-means erschwert.
  2. Teilen Sie das Bild mithilfe der Überfüllungsfunktion in gleichfarbige Zellen: Wählen Sie ein Pixel aus, das sich nicht in einer Zelle befindet, und füllen Sie es mit einer festgelegten Toleranz. Um den Abstand zwischen zwei Farben zu messen, verwende ich die euklidische Norm. Kompliziertere Formeln finden Sie in diesem Wiki-Artikel .
  3. Kleine Zellen mit ihren Nachbarn zusammenführen : Die Überflutungsfüllung generiert eine Menge von 1 oder 2 Pixel-Zellen - Zellen mit einer bestimmten Größe werden mit der benachbarten Zelle mit den am nächsten gelegenen Pixeln zusammengeführt. Dies reduziert die Anzahl der Zellen erheblich und verbessert die Laufzeit für spätere Schritte.
  4. Zusammenführen ähnlich gefärbter Bereiche : Gehen Sie die Zellen in abnehmender Reihenfolge durch. Wenn eine benachbarte Zelle eine mittlere Farbe aufweist, die weniger als einen bestimmten Abstand entfernt ist, führen Sie die Zellen zusammen. Gehen Sie weiter durch die Zellen, bis keine weiteren mehr zusammengeführt werden können.
  5. Zusammenführen, bis weniger als 1,5 N Zellen vorhanden sind (N-Zusammenführen) : Zusammenführen von Zellen unter Verwendung einer auf der Zellgröße und dem Farbunterschied basierenden Bewertung, bis höchstens 1,5 N Zellen vorhanden sind. Wir lassen etwas Spielraum, da wir uns später wieder zusammenschließen.
  6. Zusammenführen, bis weniger als P Farben vorhanden sind, unter Verwendung von K-Mitteln (P-Zusammenführen) : Verwenden Sie den K-Mittel-Clustering-Algorithmus einige Male, um Clustering von Zellenfarben zu generieren, wobei die Gewichtung auf der Zellengröße basiert. Bewerten Sie jedes Clustering anhand einer Variation des Davies-Bouldin-Index und wählen Sie das beste zu verwendende Clustering aus.
  7. Ungefähre Gaußsche Glättung : Verwenden Sie mehrere lineare Unschärfen, um die Gaußsche Unschärfe zu approximieren ( Details hier ). Wählen Sie dann für jedes Pixel die Farbe aus sich selbst und seinen Nachbarn im vorverwischten Bild aus, die der Farbe im verwischten Bild am nächsten kommt. Dieser Teil kann bei Bedarf zeitlicher optimiert werden, da ich den optimalen Algorithmus noch nicht implementiert habe.
  8. Führen Sie eine weitere Überflutung durch, um die neuen Regionen zu ermitteln : Dies ist erforderlich, da im vorherigen Schritt möglicherweise mehr Zellen generiert werden.
  9. Führen Sie einen weiteren Durchlauf zum Zusammenführen kleiner Zellen durch
  10. Führen Sie einen weiteren N- Merge -Durchlauf durch : Dieses Mal gehen wir zu N Zellen anstatt zu 1,5 N.

Die Verarbeitungszeit für jedes Bild hängt in hohem Maße von seiner Größe und Komplexität ab. Für die Testbilder liegen die Zeiten zwischen 20 Sekunden und 7 Minuten.

Da der Algorithmus eine Randomisierung verwendet (z. B. Zusammenführen, k-Means), können Sie bei verschiedenen Läufen unterschiedliche Ergebnisse erzielen. Hier ist ein Vergleich von zwei Läufen für das Bärenbild mit N = 50 und P = 10:

F M


Hinweis: Alle Bilder unten sind Links. Die meisten dieser Bilder stammen aus dem ersten Durchgang, aber wenn mir die Ausgabe nicht gefallen hat, habe ich mir bis zu drei Versuche erlaubt, fair zu sein.

N = 50, P = 10

L M ein r k d O w n G O l

N = 500, P = 30

f . . . : ( ein ein ein ein ein ein

Aber ich bin ziemlich faul, wenn es darum geht, nach Farben zu malen, also nur zum Spaß ...

N = 20, P = 5

ein ein ein ein ein ein ein ein ein ein ein ein

Außerdem ist es amüsant zu sehen, was passiert, wenn Sie versuchen, 1 Million Farben in N = 500, P = 30 zu quetschen :

ein

Hier ist eine schrittweise Anleitung für den Algorithmus für das Unterwasserbild mit N = 500 und P = 30 in animierter GIF-Form:

ein


Ich habe auch eine Galerie für die vorherigen Versionen des Algorithmus gemacht hier . Hier sind einige meiner Favoriten aus der letzten Version (aus der Zeit, als der Nebel mehr Sterne hatte und der Bär pelziger aussah):

ein ein

Sp3000
quelle
Wenn jemand eine Ausnahme bekommt, wenn das Programm versucht, Pixel zu entpacken, wird dies im = im.convert("RGB")anscheinend für einige Bilder benötigt. Ich werde das hinzufügen, nachdem ich den Code ein wenig umstrukturiert habe.
Sp3000
15

Python 2 mit PIL

Auch eine Python-Lösung und wahrscheinlich eine in Arbeit befindliche:

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)

Der Algorithmus folgt einem anderen Ansatz als der von SP3000, wobei zuerst mit den Farben begonnen wird:

  • Suchen Sie eine Farbpalette mit P- Farben durch k-means Clustering und malen Sie das Bild in dieser reduzierten Palette.

  • Wenden Sie einen leichten Medianfilter an, um Rauschen zu beseitigen.

  • Machen Sie eine Liste aller monochromatischen Zellen und sortieren Sie sie nach Größe.

  • Führe die kleinsten Zellen mit ihrem jeweils größten Nachbarn zusammen, bis nur noch N Zellen übrig sind.

In Bezug auf Geschwindigkeit und Qualität der Ergebnisse gibt es durchaus Verbesserungspotenzial. Insbesondere der Zellzusammenführungsschritt kann bis zu vielen Minuten dauern und liefert bei weitem keine optimalen Ergebnisse.


P = 5, N = 45

P = 5, N = 45P = 5, N = 45

P = 10, N = 50

P = 10, N = 50P = 10, N = 50P = 10, N = 50P = 10, N = 50

P = 4, N = 250

P = 4, N = 250P = 4, N = 250

P = 11, N = 500

P = 11, N = 500P = 11, N = 500

Emil
quelle
Ich habe zuerst versucht, den gleichen Ansatz zu verwenden (ich habe versucht, ihn in Javascript auf einem Canv zu machen), aber ich habe aufgehört, weil es viel zu lange gedauert hat, also ist es wirklich schön zu sehen, wie es ausgesehen haben könnte, nette Arbeit!
Fehler
Sehr gute Arbeit. Ich habe den Bären mit 20 Zellen geliebt.
DavidC
15

Mathematica

Momentan werden die Anzahl der Farben und der Gaußsche Radius für den Gaußschen Filter benötigt. Je größer der Radius ist, desto stärker verschwimmen und verschmelzen die Farben.

Da die Anzahl der Zellen nicht eingegeben werden kann, wird eine der Grundanforderungen der Herausforderung nicht erfüllt.

Die Ausgabe enthält die Anzahl der Zellen für jede Farbe sowie die Gesamtzahl der Zellen.

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]]

Aktualisieren

quantImage2Ermöglicht die Angabe der gewünschten Anzahl von Zellen als Eingabe. Er ermittelt den besten Gaußschen Radius, indem er Szenarien mit größeren Radien durchläuft, bis eine enge Übereinstimmung gefunden wird.

quantImage2 Ausgänge (Bild, angeforderte Zellen, verwendete Zellen, Fehler, verwendeter Gaußscher Radius).

Es ist jedoch sehr langsam. Um Zeit zu sparen, können Sie mit einem Anfangsradius beginnen, dessen Standardwert 0 ist.

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}

Beispiel, für das wir die Anzahl der Zellen angeben, die in der Ausgabe gewünscht werden.

Beispiel für die Anforderung von 90 Zellen mit 25 Farben. Die Lösung liefert 88 Zellen, 2% Fehler. Die Funktion hat den Gaußschen Radius von 55 gewählt. (Viel Verzerrung).

Affe X.


Beispiele, bei denen die Eingabe den Gaußschen Radius, nicht jedoch die Anzahl der Zellen enthält.

25 Farben, Gaußscher Radius von 5 Pixeln

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

Bälle


Drei Farben, Radius von 17 Pixel

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

Welle 3 17


Zwanzig Farben, Radius von 17 Pixeln

Wir haben die Anzahl der Farben erhöht, aber nicht den Fokus. Beachten Sie die Zunahme der Anzahl der Zellen.

Welle 2


Sechs Farben, Radius von 4 Pixeln

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

wave3


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

Affe 1


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

Affe 2


Sternenklare Nacht

Mit nur 6 Farben und 60 Zellen. Es gibt eine Farbinkongruenz in den Farben, die von showColorsihm verwendet werden. (Gelb erscheint nicht unter den 5 Farben, aber es wird in der Zeichnung verwendet.) Ich werde sehen, ob ich das herausfinden kann.

Sternennacht 1

DavidC
quelle
Das ist absolut großartig und funktioniert sehr gut für restriktive Parameter. Gibt es eine Chance, die Anzahl der Zellen in einen Parameter umzuwandeln? (Ich nehme an, Sie könnten immer eine Schätzung für den Radius anhand der Anzahl der Zellen finden, diese anwenden und dann kleine Zellen zusammenführen, bis Sie unter dem Grenzwert sind.)
Martin Ender
Es ist möglich, eine Tabelle mit showColorseiner Reihe von Farben und Radien zu erstellen und die Kombination auszuwählen, die der gewünschten Anzahl von Zellen am nächsten kommt. Ich bin mir nicht sicher, ob ich das Gas dazu habe. Vielleicht später.
DavidC
Klar, lass es mich wissen, wenn du es tust. (Ich würde auch gerne mehr Ergebnisse für die anderen Bilder sehen. :))
Martin Ender
2
Das ist gut. Danke, dass du dich an die Regeln hältst. ;)
Martin Ender
1
Ich mag die Kugeln! Sie sind nett und rund
Sp3000
9

Python 2 mit PIL

Dies ist noch in Arbeit. Außerdem ist der folgende Code ein schreckliches Durcheinander von Spaghetti und sollte nicht als Inspiration verwendet werden. :)

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!")

Wie es funktioniert

Das Programm unterteilt die Zeichenfläche in PBereiche, die jeweils aus einer bestimmten Anzahl von Zellen ohne Löcher bestehen. Zunächst wird die Leinwand nur in ungefähre Quadrate unterteilt, die den Regionen zufällig zugewiesen werden. Dann werden diese Bereiche in einem iterativen Prozess "deformiert", wobei ein gegebenes Pixel seinen Bereich ändern kann, wenn

  1. Die Änderung würde den RGB-Abstand des Pixels von der Durchschnittsfarbe des Bereichs verringern, in dem es sich befindet
  2. Es werden keine Zellen zerbrochen, zusammengeführt oder Löcher in diese eingebracht.

Die letztere Bedingung kann lokal durchgesetzt werden, so dass der Prozess ein bisschen wie ein zellularer Automat ist. Auf diese Weise müssen wir keine Wegfindung oder Ähnliches durchführen, was den Prozess erheblich beschleunigt. Da die Zellen jedoch nicht aufgebrochen werden können, enden einige von ihnen als lange "Filamente", die an andere Zellen angrenzen und deren Wachstum hemmen. Um dies zu beheben, gibt es einen Prozess namens "Filamentschnitt", der gelegentlich eine fadenförmige Zelle in zwei Teile zerlegt, wenn Nzu diesem Zeitpunkt weniger als Zellen vorhanden sind . Zellen können auch verschwinden, wenn ihre Größe 1 ist, und dies schafft Platz für die Filamentschnitte.

Der Prozess endet, wenn kein Pixel den Anreiz hat, die Regionen zu wechseln, und danach wird jede Region einfach anhand ihrer Durchschnittsfarbe gefärbt. In der Regel verbleiben einige Filamente in der Ausgabe, wie in den folgenden Beispielen zu sehen ist, insbesondere im Nebel.

P = 30, N = 500

Mona Lisa Pavian Bunte Bälle Nebel

Mehr Bilder später.

Einige interessante Eigenschaften meines Programms sind, dass es probabilistisch ist, so dass die Ergebnisse zwischen verschiedenen Läufen variieren können, es sei denn, Sie verwenden natürlich den gleichen Pseudozufalls-Startwert. Die Zufälligkeit ist jedoch nicht wesentlich, ich wollte nur zufällige Artefakte vermeiden, die sich aus der Art und Weise ergeben, wie Python einen Satz von Koordinaten oder ähnliches durchläuft. Das Programm verwendet in der Regel alle PFarben und fast alle NZellen, und die Zellen enthalten keine Löcher. Auch der Verformungsvorgang ist ziemlich langsam. Die Herstellung der farbigen Kugeln auf meiner Maschine dauerte fast 15 Minuten. Auf der Oberseite schalten Sie das einGRAPHICAL_LOGGINGOption, erhalten Sie eine coole Serie von Bildern des Verformungsprozesses. Ich habe die Mona Lisa in eine GIF-Animation umgewandelt (um 50% verkleinert, um die Dateigröße zu verringern). Wenn Sie sich ihr Gesicht und ihre Haare genau ansehen, können Sie den Filamentschneidevorgang in Aktion sehen.

Bildbeschreibung hier eingeben

Zgarb
quelle
Wow, diese Ergebnisse sehen wirklich wunderschön aus (obwohl es nicht so aussieht, als wäre es mit Zahlen gemalt, aber immer noch sehr schön :)).
Martin Ender