Cat dengan Angka

42

Anda diberi gambar warna yang benar. Tugas Anda adalah membuat versi gambar ini, yang terlihat seperti dicat menggunakan angka-angka (aktivitas anak-anak, bukan nonogram). Seiring dengan gambar, Anda diberi dua parameter: P , ukuran maksimum palet warna (yaitu jumlah maksimum warna berbeda untuk digunakan), dan N , jumlah sel maksimum untuk digunakan. Algoritme Anda tidak harus menggunakan semua warna P dan sel N , tetapi tidak boleh menggunakan lebih dari itu. Gambar output harus memiliki dimensi yang sama dengan input.

Sebuah sel didefinisikan sebagai daerah perbatasan dari pixel yang semua memiliki warna yang sama. Piksel yang menyentuh hanya di sudut tidak dianggap bersebelahan. Sel mungkin memiliki lubang.

Singkatnya, Anda harus memperkirakan gambar input dengan hanya N bidang teduh / warna solid dan P warna berbeda.

Hanya untuk memvisualisasikan parameter, berikut adalah contoh yang sangat sederhana (tanpa gambar input tertentu; memamerkan keterampilan Cat gila saya). Gambar berikut memiliki P = 6 dan N = 11 :

masukkan deskripsi gambar di sini

Berikut adalah beberapa gambar untuk menguji algoritme Anda (sebagian besar tersangka kami biasa). Klik gambar untuk versi yang lebih besar.

Gelombang Besar Batu karang Pelangi Malam berbintang Sungai Beruang coklat Air terjun Mandrill Nebula kepiting American Gothic Mona lisa Berteriak

Harap sertakan beberapa hasil untuk parameter yang berbeda. Jika Anda ingin menunjukkan sejumlah besar hasil, Anda dapat membuat galeri di imgur.com , agar ukuran jawaban tetap masuk akal. Atau, letakkan gambar kecil di pos Anda dan buat tautan ke gambar yang lebih besar, seperti yang saya lakukan di atas. Juga, jangan ragu untuk menggunakan gambar uji lain, jika Anda menemukan sesuatu yang bagus.

Saya berasumsi bahwa parameter sekitar N ≥ 500 , P ~ 30 akan mirip dengan templat cat-by-number yang asli.

Ini adalah kontes popularitas, jadi jawabannya dengan suara terbanyak menang. Pemilih didorong untuk menilai jawaban oleh

  • seberapa baik gambar aslinya diperkirakan.
  • seberapa baik algoritma bekerja pada berbagai jenis gambar (lukisan mungkin umumnya lebih mudah daripada foto).
  • seberapa baik algoritma bekerja dengan parameter yang sangat ketat.
  • bagaimana organik / menghaluskan bentuk sel terlihat.

Saya akan menggunakan skrip Mathematica berikut, untuk memvalidasi hasil:

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 cukup baik untuk menulis verifier di Python 2 menggunakan PIL, yang Anda temukan di pastebin ini .

Martin Ender
sumber
2
Bukan hal yang paling efisien, tapi inilah verifier Python 2 PIL .
Sp3000
Sungguh pertanyaan yang indah, tetapi saya berharap kita juga akan melihat versi "paint by numbers" yang tepat. Itu dengan angka di tempat sehingga saya bisa menggunakan jawaban :)
@Lembik Awalnya saya ingin memasukkan itu, tapi saya merasa itu mengalihkan perhatian dari bagian yang menarik dari pertanyaan. Seharusnya tidak terlalu sulit untuk mengambil output dari salah satu kiriman dan mengubahnya menjadi templat.
Martin Ender
Ini adalah pos yang menarik. Adakah yang melakukan langkah tambahan untuk menambahkan nomor warna seperti Paint by Number yang sebenarnya?
B. Blair

Jawaban:

39

Python 2 dengan PIL ( Galeri )

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)

Perbarui waktu! Pembaruan ini menampilkan algoritme penghalusan sederhana untuk membuat gambar terlihat lebih kabur. Jika saya memperbarui lagi saya harus mengubah sedikit kode saya, karena itu menjadi berantakan & saya hd 2 glf a fw thngs 2 mke t char lim.

Saya juga membuat warna berat k-means berdasarkan ukuran sel, yang kehilangan beberapa detail untuk parameter yang lebih ketat (misalnya pusat nebula dan garpu rumput Amerika Gothic) tetapi membuat pilihan warna keseluruhan lebih tajam dan lebih bagus. Menariknya, ia kehilangan seluruh latar belakang untuk bidang raytraced untuk P = 5.

Ringkasan algoritma:

  1. Konversikan piksel ke ruang warna CIELAB: CIELAB mendekati penglihatan manusia yang lebih baik daripada RGB. Awalnya saya menggunakan HSL (rona, saturasi, cahaya) tetapi ini memiliki dua masalah - rona putih / abu-abu / hitam tidak terdefinisi, dan rona diukur dalam derajat yang membungkus, membuat k-sarana sulit digunakan.
  2. Membagi gambar menjadi sel-sel berwarna seperti menggunakan mengisi banjir: Pilih piksel tidak dalam sel dan lakukan mengisi banjir menggunakan toleransi yang ditentukan. Untuk mengukur jarak antara dua warna saya menggunakan norma Euclidean standar. Rumus yang lebih rumit tersedia di artikel wiki ini .
  3. Menggabungkan sel-sel kecil dengan tetangganya : Isi banjir menghasilkan banyak sel 1 atau 2 piksel - menggabungkan sel kurang dari ukuran yang ditentukan dengan sel tetangga dengan piksel paling berdekatan. Ini sangat mengurangi jumlah sel, meningkatkan waktu berjalan untuk langkah selanjutnya.
  4. Gabungkan bersama-sama daerah berwarna sama : Pergi melalui sel agar ukuran berkurang. Jika ada sel tetangga memiliki warna rata-rata kurang dari jarak tertentu, gabungkan sel. Terus sel-sel sampai tidak ada lagi yang bisa digabungkan.
  5. Gabungkan hingga kami memiliki kurang dari sel 1,5N (penggabungan N) : Gabungkan sel bersama, menggunakan penilaian berdasarkan ukuran sel dan perbedaan warna, hingga kami memiliki paling banyak sel 1,5N. Kami mengizinkan sedikit kelonggaran karena kami akan bergabung lagi nanti.
  6. Gabungkan hingga kami memiliki kurang dari P warna, menggunakan k-means (P-penggabungan) : Gunakan algoritma pengelompokan k-means beberapa kali berapa kali untuk menghasilkan pengelompokan warna sel, pembobotan berdasarkan ukuran sel. Skor setiap pengelompokan berdasarkan variasi indeks Davies-Bouldin dan pilih pengelompokan terbaik untuk digunakan.
  7. Perkiraan Gaussian smoothing : Gunakan beberapa blur linier untuk memperkirakan Gaussian blurring ( detail di sini ). Kemudian untuk setiap piksel, ambil warna dari dirinya sendiri dan tetangganya dalam gambar pra-buram yang paling dekat dengan warna dalam gambar buram. Bagian ini dapat dioptimalkan lebih hemat waktu jika perlu karena saya belum mengimplementasikan algoritma yang optimal.
  8. Lakukan pass pengisian banjir lain untuk mengerjakan daerah baru : Ini perlu karena langkah sebelumnya sebenarnya dapat menghasilkan lebih banyak sel.
  9. Apakah lulus penggabungan sel kecil lainnya
  10. Lakukan lagi N-merging pass : Kali ini kita turun ke sel N daripada 1.5N.

Waktu pemrosesan untuk setiap gambar sangat tergantung pada ukuran dan kerumitannya, dengan waktu mulai dari 20 detik hingga 7 menit untuk gambar uji.

Karena algoritme menggunakan pengacakan (mis. Penggabungan, k-means), Anda bisa mendapatkan hasil berbeda pada proses yang berbeda. Berikut adalah perbandingan dua run untuk gambar bear, dengan N = 50 dan P = 10:

F M.


Catatan: Semua gambar di bawah ini adalah tautan. Sebagian besar gambar ini langsung dari jalankan pertama, tetapi jika saya tidak suka output saya membiarkan diri saya hingga tiga upaya untuk bersikap adil.

N = 50, P = 10

L. M. Sebuah r k d Hai w n g Hai l

N = 500, P = 30

f . . . : ( Sebuah Sebuah Sebuah Sebuah Sebuah Sebuah

Tapi saya cukup malas dalam hal melukis dengan warna, jadi hanya untuk bersenang-senang ...

N = 20, P = 5

Sebuah Sebuah Sebuah Sebuah Sebuah Sebuah Sebuah Sebuah Sebuah Sebuah Sebuah Sebuah

Selain itu, lucu melihat apa yang terjadi ketika Anda mencoba memeras 1 juta warna menjadi N = 500, P = 30:

Sebuah

Berikut langkah-langkah penelusuran algoritma untuk gambar bawah laut dengan N = 500 dan P = 30, dalam bentuk animasi GIF:

Sebuah


Saya juga membuat galeri untuk versi algoritma sebelumnya di sini . Inilah beberapa favorit saya dari versi terakhir (dari saat nebula memiliki lebih banyak bintang dan beruang tampak lebih berbulu):

Sebuah Sebuah

Sp3000
sumber
Jika ada yang mendapatkan Pengecualian ketika program mencoba membongkar piksel, sepertinya im = im.convert("RGB")diperlukan untuk beberapa foto. Saya akan memasukkannya setelah saya merestrukturisasi kode sedikit.
Sp3000
15

Python 2 dengan PIL

Juga solusi Python dan mungkin sangat banyak pekerjaan yang sedang berjalan:

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)

Algoritme mengikuti pendekatan yang berbeda dari SP3000, dimulai dengan warna terlebih dahulu:

  • Temukan palet warna warna P dengan k-means clustering dan cat gambar dalam palet yang diperkecil ini.

  • Gunakan sedikit filter median untuk menghilangkan noise.

  • Buat daftar semua sel monokromatik dan urutkan berdasarkan ukuran.

  • Gabungkan sel terkecil dengan tetangga terbesar masing-masing hingga hanya ada sel N yang tersisa.

Ada cukup ruang untuk perbaikan, baik dalam hal kecepatan dan kualitas hasil. Terutama langkah penggabungan sel dapat memakan waktu hingga beberapa menit dan memberi jauh dari hasil yang optimal.


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
sumber
Saya pertama kali mencoba untuk menggunakan tentang pendekatan yang sama (mencoba melakukannya dalam Javascript pada sebuah canvs) tetapi akhirnya menyerah karena terlalu lama, jadi sangat bagus untuk melihat seperti apa itu, kerja bagus!
flawr
Kerja yang sangat bagus. Saya suka beruang dengan 20 sel.
DavidC
15

Mathematica

Saat ini, ini membutuhkan jumlah warna dan jari-jari Gaussian untuk digunakan dalam filter Gaussian. Semakin besar radius, semakin besar buram dan penggabungan warna.

Karena tidak memungkinkan untuk input jumlah sel, itu tidak memenuhi salah satu persyaratan dasar dari tantangan.

Output mencakup jumlah sel untuk setiap warna dan juga jumlah total sel.

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

Memperbarui

quantImage2memungkinkan untuk menentukan jumlah sel yang diinginkan sebagai input. Ini menentukan Radius Gaussian terbaik dengan perulangan melalui skenario dengan jari-jari yang lebih besar sampai ditemukan kecocokan yang dekat.

quantImage2 output (gambar, sel yang diminta, sel yang digunakan, kesalahan, Radius gaussian digunakan).

Namun, ini sangat lambat. Untuk menghemat waktu, Anda dapat mulai dengan radius awal, nilai defaultnya adalah 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}

Contoh yang kami tentukan jumlah sel yang diinginkan dalam output.

Contohnya meminta 90 sel dengan 25 warna. Solusi mengembalikan 88 sel, 2% kesalahan. Fungsi memilih jari-jari Gaussian 55. (Banyak distorsi).

Kera X


Contoh yang inputnya termasuk jari-jari Gaussian, tetapi bukan jumlah sel.

25 Warna, radius Gaussian 5 piksel

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

bola


Tiga Warna, radius 17 piksel

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

gelombang 3 17


Dua puluh warna, radius 17 piksel

Kami meningkatkan jumlah warna tetapi tidak fokus. Perhatikan peningkatan jumlah sel.

gelombang 2


Enam Warna, jari-jari 4 piksel

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

gelombang3


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

kera 1


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

kera 2


Malam berbintang

Dengan hanya 6 warna dan 60 sel. Ada ketidakcocokan warna dalam warna showColorsklaim yang digunakannya. (Kuning tidak muncul di antara 5 warna tetapi digunakan dalam gambar.) Saya akan melihat apakah saya bisa mengetahuinya.

malam berbintang 1

DavidC
sumber
Ini sangat cantik, dan bekerja sangat baik untuk parameter yang membatasi. Adakah peluang untuk mengubah jumlah sel menjadi parameter? (Saya kira Anda selalu dapat menemukan beberapa perkiraan untuk jari-jari dari jumlah sel, menerapkannya, dan kemudian menggabungkan sel-sel kecil sampai Anda di bawah batas.)
Martin Ender
Dimungkinkan untuk membuat Tabel showColors, memutar melalui berbagai jumlah warna dan jari-jari dan memilih kombinasi yang paling mendekati jumlah sel yang diinginkan. Tidak yakin apakah saya punya gas untuk melakukan itu saat ini. Mungkin nanti.
DavidC
Tentu, beri tahu saya jika Anda melakukannya. (Saya juga ingin melihat beberapa hasil untuk gambar lainnya. :))
Martin Ender
2
Tidak apa-apa. Terima kasih telah bermain sesuai aturan. ;)
Martin Ender
1
Saya menyukai bola! Mereka bagus dan bulat
Sp3000
9

Python 2 dengan PIL

Ini masih agak dalam proses. Juga, kode di bawah ini adalah kekacauan spaghetti yang mengerikan, dan tidak boleh digunakan sebagai inspirasi. :)

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

Bagaimana itu bekerja

Program ini membagi kanvas menjadi beberapa Pwilayah, yang masing-masing terdiri dari sejumlah sel tanpa lubang. Awalnya, kanvas hanya dibagi menjadi kotak perkiraan, yang secara acak ditugaskan ke daerah. Kemudian, wilayah ini "cacat" dalam proses berulang, di mana piksel yang diberikan dapat mengubah wilayahnya jika

  1. perubahan akan mengurangi jarak RGB piksel dari warna rata-rata wilayah yang berisi itu, dan
  2. itu tidak merusak atau menggabungkan sel atau membuat lubang di dalamnya.

Kondisi terakhir dapat ditegakkan secara lokal, sehingga prosesnya sedikit seperti otomat seluler. Dengan cara ini, kita tidak perlu melakukan pathfinding atau semacamnya, yang mempercepat prosesnya. Namun, karena sel-sel tidak dapat dipecah, beberapa dari mereka berakhir sebagai "filamen" yang membatasi sel-sel lain dan menghambat pertumbuhan mereka. Untuk mengatasinya, ada proses yang disebut "potongan filamen", yang kadang-kadang memecah sel berbentuk filamen menjadi dua, jika ada kurang dari Nsel pada waktu itu. Sel juga bisa menghilang jika ukurannya 1, dan ini membuat ruang untuk memotong filamen.

Proses berakhir ketika tidak ada piksel yang memiliki insentif untuk beralih wilayah, dan setelah itu, setiap wilayah hanya diwarnai dengan warna rata-rata. Biasanya akan ada beberapa filamen yang tersisa di output, seperti yang dapat dilihat pada contoh di bawah ini, terutama di nebula.

P = 30, N = 500

Mona lisa Babon Bola warna-warni Nebula

Lebih banyak gambar nanti.

Beberapa sifat menarik dari program saya adalah bahwa itu probabilistik, sehingga hasilnya dapat bervariasi di antara berbagai proses, kecuali jika Anda menggunakan seed pseudorandom yang sama tentunya. Keacakan tidak penting, meskipun, saya hanya ingin menghindari artefak disengaja yang mungkin dihasilkan dari cara tertentu Python melintasi seperangkat koordinat atau sesuatu yang serupa. Program cenderung menggunakan semua Pwarna dan hampir semua Nsel, dan sel tidak pernah mengandung lubang dengan desain. Juga, proses deformasi cukup lambat. Bola berwarna membutuhkan waktu hampir 15 menit untuk diproduksi di mesin saya. Pada terbalik, Anda menghidupkanGRAPHICAL_LOGGINGopsi, Anda akan mendapatkan serangkaian gambar keren dari proses deformasi. Saya membuat yang Mona Lisa menjadi animasi GIF (menyusut 50% untuk mengurangi ukuran file). Jika Anda melihat dari dekat ke wajah dan rambutnya, Anda dapat melihat proses pemotongan filamen.

masukkan deskripsi gambar di sini

Zgarb
sumber
Wow, hasil ini terlihat sangat indah (meskipun tidak seperti itu dilukis oleh angka, tetapi masih sangat bagus :)).
Martin Ender