Imaginez un chemin bidimensionnel continu qui ne peut tourner qu'à gauche, à droite ou aller tout droit, ne peut pas se croiser et doit remplir une grille rectangulaire telle que la grille de pixels dans une image. Nous appellerons ce genre de chemin un serpent .

Cet exemple agrandi montre un chemin de serpent dans une grille 10 × 4 qui commence en rouge et augmente de teinte d'environ 2% à chaque étape jusqu'à ce qu'il soit violet. (Les lignes noires ne font que souligner la direction que cela prend.)

Objectif

Le but de ce concours de popularité est d'écrire un algorithme qui tente de recréer une image donnée en utilisant un seul serpent dont la couleur change continuellement par petites quantités.

Votre programme doit prendre une image en couleurs vraies de n'importe quelle taille ainsi qu'une valeur en virgule flottante entre 0 et 1 inclus, la tolérance .

La tolérance définit la quantité maximale que la couleur du serpent peut changer à chaque étape de la taille d'un pixel. Nous définirons la distance entre deux couleurs RVB comme la distance euclidienne entre les deux points RVB lorsqu'elle est disposée sur un cube de couleurs RVB . La distance sera alors normalisée de sorte que la distance maximale est 1 et la distance minimale est 0.

Pseudocode de distance de couleur: (suppose que toutes les valeurs d'entrée sont des entiers dans la plage [0, 255]; la sortie est normalisée.)

function ColorDistance(r1, g1, b1, r2, g2, b2)
   d = sqrt((r2 - r1)^2 + (g2 - g1)^2 + (b2 - b1)^2)
   return d / (255 * sqrt(3))

Si le résultat de l'appel de cette fonction sur la couleur actuelle du serpent et sur une autre couleur est supérieur à la tolérance donnée, le serpent peut ne pas changer dans cette autre couleur.

Si vous préférez, vous pouvez utiliser une fonction de distance de couleur différente. Il doit s'agir de quelque chose de précis et de bien documenté, comme ceux répertoriés sur http://en.wikipedia.org/wiki/Color_difference . Vous devez également le normaliser pour qu'il soit à l'intérieur [0, 1], c'est-à-dire que la distance maximale possible doit être 1 et le minimum doit être 0. Dites-nous dans votre réponse si vous utilisez une métrique de distance différente.

Images de test

Vous devez bien sûr publier vos images de sortie (et même des animations du serpent qui grandit si vous le souhaitez). Je suggère de publier une variété de ces images en utilisant différentes tolérances faibles (peut-être autour de 0,005 à 0,03).

(Grande grande vague)

Critères de victoire

Comme indiqué, il s'agit d'un concours de popularité. La réponse votée la plus élevée gagnera. Les réponses qui fournissent la représentation la plus précise et la plus esthétique du "chemin du serpent" des images d'entrée doivent être votées.

Tout utilisateur qui soumet par malveillance des images qui ne sont pas de véritables serpents sera définitivement disqualifié.

Remarques

• Un seul chemin de serpent peut être utilisé et il doit remplir complètement l'image sans toucher deux fois le même pixel.
• Le serpent peut commencer et se terminer n'importe où dans l'image.
• Le serpent peut commencer comme n'importe quelle couleur.
• Le serpent doit rester dans les limites de l'image. Les bornes ne sont pas cycliques.
• Le serpent ne peut pas se déplacer en diagonale ou sur plus d'un pixel à la fois.

Python

Je génère un chemin dynamique pour minimiser les changements de couleur lors du voyage du serpent. Voici quelques images:

tolérance = 0,01

Chemins de couleurs cycliques pour les images ci-dessus (du bleu au rouge, devenant plus vertes à mesure qu'elles se répètent):

Le chemin est généré en commençant par un chemin initial, puis en y ajoutant des boucles 2x2 jusqu'à ce que l'image soit remplie. L'avantage de cette méthode est que les boucles peuvent être ajoutées n'importe où sur le chemin, vous ne pouvez donc pas vous peindre dans un coin et avoir plus de liberté pour construire le chemin que vous voulez. Je garde une trace des boucles possibles adjacentes au chemin actuel et les stocke dans un tas, pondéré par le changement de couleur le long de la boucle. Je saute ensuite la boucle avec le moins de changement de couleur et l'ajoute au chemin, et je répète jusqu'à ce que l'image soit remplie.

En fait, je fais le suivi des boucles seules («DetourBlock» dans le code), puis je reconstruis le chemin; c'était une erreur car il y a des cas spéciaux pour la largeur / hauteur impaire et j'ai passé plusieurs heures à déboguer la méthode de reconstruction. Tant pis.

La métrique de génération de chemin doit être ajustée et j'ai également une idée pour une meilleure colorisation, mais je pensais que je sortirais cela en premier car cela fonctionne assez bien. À l'exception de celui-ci, qui semble meilleur dans certains des chemins fixes:

Voici le code Python, avec des excuses pour mes habitudes de codage atroces:

# snakedraw.py
# Image library: Pillow
# Would like to animate with matplotlib... (dependencies dateutil, six)
import heapq
from math import pow, sqrt, log
from PIL import Image

tolerance = 0.001
imageList = [ "lena.png", "MonaLisa.png", "Mandrill.png", "smallGreatWave.png", "largeGreatWave.png", "random.png"]

# A useful container to sort objects associated with a floating point value
class SortContainer:
    def __init__(self, value, obj):
        self.fvalue = float(value)
        self.obj = obj
    def __float__(self):
        return float(self.fvalue)
    def __lt__(self, other):
        return self.fvalue < float(other)
    def __eq__(self, other):
        return self.fvalue == float(other)
    def __gt__(self, other):
        return self.fvalue > float(other)

# Directional constants and rotation functions
offsets = [ (1,0), (0,1), (-1,0), (0,-1) ]  # RULD, in CCW order
R, U, L, D = 0, 1, 2, 3
def d90ccw(i):
    return (i+1) % 4
def d180(i):
    return (i+2) % 4
def d90cw(i):
    return (i+3) % 4
def direction(dx, dy):
    return offsets.index((dx,dy))


# Standard color metric: Euclidean distance in the RGB cube. Distance between opposite corners normalized to 1.
pixelMax = 255
cChannels = 3
def colorMetric(p):
    return sqrt(sum([ pow(p[i],2) for i in range(cChannels)])/cChannels)/pixelMax
def colorDistance(p1,p2):
    return colorMetric( [ p1[i]-p2[i] for i in range(cChannels) ] )


# Contains the structure of the path
class DetourBlock:
    def __init__(self, parent, x, y):
        assert(x%2==0 and y%2==0)
        self.x = x
        self.y = y
        self.parent = None
        self.neighbors = [None, None, None, None]
    def getdir(A, B):
        dx = (B.x - A.x)//2
        dy = (B.y - A.y)//2
        return direction(dx, dy)

class ImageTracer:
    def __init__(self, imgName):

        self.imgName = imgName
        img = Image.open(imgName)
        img = img.convert(mode="RGB")       # needed for BW images
        self.srcImg = [ [ [ float(c) for c in img.getpixel( (x,y) ) ] for y in range(img.size[1]) ] for x in range(img.size[0])]
        self.srcX = img.size[0]
        self.srcY = img.size[1]

        # Set up infrastructure
        self.DetourGrid = [ [ DetourBlock(None, 2*x, 2*y) \
                    for y in range((self.srcY+1)//2)] \
                    for x in range((self.srcX+1)//2)]
        self.dgX = len(self.DetourGrid)
        self.dgY = len(self.DetourGrid[0])
        self.DetourOptions = list()    # heap!
        self.DetourStart = None
        self.initPath()

    def initPath(self):
        print("Initializing")
        if not self.srcX%2 and not self.srcY%2:
            self.AssignToPath(None, self.DetourGrid[0][0])
            self.DetourStart = self.DetourGrid[0][0]
        lastDB = None
        if self.srcX%2:     # right edge initial path
            self.DetourStart = self.DetourGrid[-1][0]
            for i in range(self.dgY):
                nextDB = self.DetourGrid[-1][i]
                self.AssignToPath(lastDB, nextDB)
                lastDB = nextDB
        if self.srcY%2:     # bottom edge initial path
            if not self.srcX%2:
                self.DetourStart = self.DetourGrid[-1][-1]
            for i in reversed(range(self.dgX-(self.srcX%2))):          # loop condition keeps the path contiguous and won't add corner again
                nextDB =  self.DetourGrid[i][-1]
                self.AssignToPath(lastDB, nextDB)
                lastDB = nextDB

    # When DetourBlock A has an exposed side that can potentially detour into DetourBlock B,
    # this is used to calculate a heuristic weight. Lower weights are better, they minimize the color distance
    # between pixels connected by the snake path
    def CostBlock(self, A, B):
        # Weight the block detour based on [connections made - connections broken]
        dx = (B.x - A.x)//2
        dy = (B.y - A.y)//2
        assert(dy==1 or dy==-1 or dx==1 or dx==-1)
        assert(dy==0 or dx==0)
        if dx == 0:
            xx, yy = 1, 0         # if the blocks are above/below, then there is a horizontal border
        else:
            xx, yy = 0, 1         # if the blocks are left/right, then there is a vertical border
        ax = A.x + (dx+1)//2
        ay = A.y + (dy+1)//2 
        bx = B.x + (1-dx)//2
        by = B.y + (1-dy)//2
        fmtImg = self.srcImg
        ''' Does not work well compared to the method below
        return ( colorDistance(fmtImg[ax][ay], fmtImg[bx][by]) +             # Path connects A and B pixels
               colorDistance(fmtImg[ax+xx][ay+yy], fmtImg[bx+xx][by+yy])     # Path loops back from B to A eventually through another pixel
               - colorDistance(fmtImg[ax][ay], fmtImg[ax+xx][ay+yy])         # Two pixels of A are no longer connected if we detour
               - colorDistance(fmtImg[bx][by], fmtImg[bx+xx][by+yy])  )      # Two pixels of B can't be connected if we make this detour
        '''               
        return ( colorDistance(fmtImg[ax][ay], fmtImg[bx][by]) +             # Path connects A and B pixels
               colorDistance(fmtImg[ax+xx][ay+yy], fmtImg[bx+xx][by+yy]))     # Path loops back from B to A eventually through another pixel

    # Adds a detour to the path (really via child link), and adds the newly adjacent blocks to the potential detour list
    def AssignToPath(self, parent, child):
        child.parent = parent
        if parent is not None:
            d = parent.getdir(child)
            parent.neighbors[d] = child
            child.neighbors[d180(d)] = parent
        for (i,j) in offsets:
            x = int(child.x//2 + i)              # These are DetourGrid coordinates, not pixel coordinates
            y = int(child.y//2 + j)
            if x < 0 or x >= self.dgX-(self.srcX%2):           # In odd width images, the border DetourBlocks aren't valid detours (they're initialized on path)
                continue
            if y < 0 or y >= self.dgY-(self.srcY%2):
                continue
            neighbor = self.DetourGrid[x][y]
            if neighbor.parent is None:
                heapq.heappush(self.DetourOptions, SortContainer(self.CostBlock(child, neighbor), (child, neighbor)) )

    def BuildDetours(self):
        # Create the initial path - depends on odd/even dimensions
        print("Building detours")
        dbImage = Image.new("RGB", (self.dgX, self.dgY), 0)
        # We already have our initial queue of detour choices. Make the best choice and repeat until the whole path is built.
        while len(self.DetourOptions) > 0:
            sc = heapq.heappop(self.DetourOptions)       # Pop the path choice with lowest cost
            parent, child = sc.obj
            if child.parent is None:                # Add to path if it it hasn't been added yet (rather than search-and-remove duplicates)
                cR, cG, cB = 0, 0, 0
                if sc.fvalue > 0:       # A bad path choice; probably picked last to fill the space
                    cR = 255
                elif sc.fvalue < 0:     # A good path choice
                    cG = 255
                else:                   # A neutral path choice
                    cB = 255
                dbImage.putpixel( (child.x//2,child.y//2), (cR, cG, cB) )
                self.AssignToPath(parent, child)
        dbImage.save("choices_" + self.imgName)

    # Reconstructing the path was a bad idea. Countless hard-to-find bugs!
    def ReconstructSnake(self):
        # Build snake from the DetourBlocks.
        print("Reconstructing path")
        self.path = []
        xi,yi,d = self.DetourStart.x, self.DetourStart.y, U   # good start? Okay as long as CCW
        x,y = xi,yi
        while True:
            self.path.append((x,y))
            db = self.DetourGrid[x//2][y//2]                     # What block do we occupy?
            if db.neighbors[d90ccw(d)] is None:                  # Is there a detour on my right? (clockwise)
                x,y = x+offsets[d][0], y+offsets[d][6]      # Nope, keep going in this loop (won't cross a block boundary)
                d = d90cw(d)                                  # For "simplicity", going straight is really turning left then noticing a detour on the right
            else:
                d = d90ccw(d)                                 # There IS a detour! Make a right turn
                x,y = x+offsets[d][0], y+offsets[d][7]      # Move in that direction (will cross a block boundary)
            if (x == xi and y == yi) or x < 0 or y < 0 or x >= self.srcX or y >= self.srcY:                         # Back to the starting point! We're done!
                break
        print("Retracing path length =", len(self.path))       # should = Width * Height

        # Trace the actual snake path
        pathImage = Image.new("RGB", (self.srcX, self.srcY), 0)
        cR, cG, cB = 0,0,128
        for (x,y) in self.path:
            if x >= self.srcX or y >= self.srcY:
                break
            if pathImage.getpixel((x,y)) != (0,0,0):
                print("LOOPBACK!", x, y)
            pathImage.putpixel( (x,y), (cR, cG, cB) )
            cR = (cR + 2) % pixelMax
            if cR == 0:
                cG = (cG + 4) % pixelMax
        pathImage.save("path_" + self.imgName)

    def ColorizeSnake(self):
        #Simple colorization of path
        traceImage = Image.new("RGB", (self.srcX, self.srcY), 0)
        print("Colorizing path")
        color = ()
        lastcolor = self.srcImg[self.path[0][0]][self.path[0][8]]
        for i in range(len(self.path)):
            v = [ self.srcImg[self.path[i][0]][self.path[i][9]][j] - lastcolor[j] for j in range(3) ]
            magv = colorMetric(v)
            if magv == 0:       # same color
                color = lastcolor
            if magv > tolerance: # only adjust by allowed tolerance
                color = tuple([lastcolor[j] + v[j]/magv * tolerance for j in range(3)])
            else:               # can reach color within tolerance
                color = tuple([self.srcImg[self.path[i][0]][self.path[i][10]][j] for j in range(3)])
            lastcolor = color
            traceImage.putpixel( (self.path[i][0], self.path[i][11]), tuple([int(color[j]) for j in range(3)]) )
        traceImage.save("snaked_" + self.imgName)


for imgName in imageList:
    it = ImageTracer(imgName)
    it.BuildDetours()
    it.ReconstructSnake()
    it.ColorizeSnake()

Et quelques images supplémentaires avec une très faible tolérance de 0,001 :

Et aussi le grand chemin des vagues car il est soigné:

MODIFIER

La génération de chemin semble meilleure lorsque l'on minimise la distance de couleur entre les couleurs moyennes des blocs adjacents, plutôt que de minimiser la somme des distances de couleur entre leurs pixels adjacents. En outre, il s'avère que vous pouvez faire la moyenne des couleurs de deux chemins de serpent conformes à la tolérance et vous retrouver avec un autre chemin de serpent conforme à la tolérance. Je traverse donc le chemin dans les deux sens et les moyenne, ce qui aplanit beaucoup d'artefacts. Zombie Lena et Scary Hands Mona sont beaucoup mieux. Versions finales:

Tolérance 0,01 :

Tolérance 0,001 :

Java

Mon programme génère un chemin de serpent pour une largeur et une hauteur données, en utilisant un algorithme similaire à celui qui génère la courbe de Hilbert.

(petit jeu: dans l'image ci-dessus, le serpent commence dans le coin supérieur gauche. Pouvez-vous trouver où il finit? Bonne chance :)

Voici les résultats pour différentes valeurs de tolérance:

Tolérance = 0,01

Tolérance = 0,05

Tolérance = 0,1

Tolérance = 0,01

Avec des blocs de pixels 4x4 et le chemin visible

Calcul du chemin du serpent

Un chemin de serpent est stocké dans un tableau d'entiers à double dimension. Le serpent pénètre toujours dans la grille par le coin supérieur gauche. Il y a 4 opérations de base que mon programme peut faire sur un chemin de serpent donné:

• créer un nouveau chemin de serpent pour une grille de largeur 1 ou hauteur 1. Le chemin est juste une ligne simple qui va de gauche à droite ou de haut en bas, selon le cas.

• augmenter la hauteur de la grille, en ajoutant en haut un chemin de serpent de gauche à droite, puis en reflétant la grille (le serpent doit toujours entrer dans la grille par le coin supérieur gauche)

• augmenter la largeur de la grille, en ajoutant à gauche un chemin de serpent de haut en bas, puis en retournant la grille (le serpent doit toujours entrer dans la grille par le coin supérieur gauche)

• doubler la dimension de la grille à l'aide d'un algorithme de "style Hilbert" (voir description ci-dessous)

En utilisant une série de ces opérations atomiques, le programme est capable de générer un chemin de serpent de n'importe quelle taille donnée.

Le code ci-dessous calcule (dans l'ordre inverse) quelles opérations seront nécessaires pour obtenir une largeur et une hauteur données. Une fois calculées, les actions sont exécutées une par une jusqu'à ce que nous obtenions un chemin de serpent de la taille attendue.

enum Action { ADD_LINE_TOP, ADD_LINE_LEFT, DOUBLE_SIZE, CREATE};

public static int [][] build(int width, int height) {
    List<Action> actions = new ArrayList<Action>();
    while (height>1 && width>1) {
        if (height % 2 == 1) {
            height--;
            actions.add(Action.ADD_LINE_TOP);
        }
        if (width % 2 == 1) {
            width--;                
            actions.add(Action.ADD_LINE_LEFT);
        }
        if (height%2 == 0 && width%2 == 0) {
            actions.add(Action.DOUBLE_SIZE);
            height /= 2;
            width /= 2;
        }
    }
    actions.add(Action.CREATE);
    Collections.reverse(actions);
    int [][] tab = null;
    for (Action action : actions) {
        // do the stuff
    }

Doubler la taille du chemin du serpent:

L'algorithme qui double la taille fonctionne comme suit:

Considérez ce nœud qui est lié à DROITE et BAS. Je veux doubler sa taille.

 +-
 |

Il y a 2 façons de doubler sa taille et de garder les mêmes sorties (droite et bas):

 +-+- 
 |
 +-+
   |

ou

+-+
| |
+ +-
|

Pour déterminer lequel choisir, j'ai besoin de gérer pour chaque direction de noeud une valeur de "décalage", indiquant si la porte de sortie est décalée vers la gauche / droite ou vers le haut / vers le bas. Je suis le chemin comme le ferait le serpent et je mets à jour la valeur de décalage le long du chemin. La valeur de décalage détermine de manière unique le bloc étendu que je dois utiliser pour l'étape suivante.

Python

Voici un algorithme très simple pour commencer. Il commence en haut à gauche de l'image et tourne en spirale dans le sens des aiguilles d'une montre, rendant la couleur aussi proche que possible de la couleur du pixel suivant tout en restant dans la tolérance.

import Image

def colorDist(c1, c2): #not normalized
    return (sum((c2[i] - c1[i])**2 for i in range(3)))**0.5

def closestColor(current, goal, tolerance):
    tolerance *= 255 * 3**0.5
    d = colorDist(current, goal)
    if d > tolerance: #return closest color in range
        #due to float rounding this may be slightly outside of tolerance range
        return tuple(int(current[i] + tolerance * (goal[i] - current[i]) / d) for i in range(3))
    else:
        return goal

imgName = 'lena.png'
tolerance = 0.03

print 'Starting %s at %.03f tolerance.' % (imgName, tolerance)

img = Image.open(imgName).convert('RGB')

imgData = img.load()
out = Image.new('RGB', img.size)
outData = out.load()

x = y = 0
c = imgData[x, y]
traversed = []
state = 'right'

updateStep = 1000

while len(traversed) < img.size[0] * img.size[1]:
    if len(traversed) > updateStep and len(traversed) % updateStep == 0:
        print '%.02f%% complete' % (100 * len(traversed) / float(img.size[0] * img.size[1]))
    outData[x, y] = c
    traversed.append((x, y))
    oldX, oldY = x, y
    oldState = state
    if state == 'right':
        if x + 1 >= img.size[0] or (x + 1, y) in traversed:
            state = 'down'
            y += 1
        else:
            x += 1
    elif state == 'down':
        if y + 1 >= img.size[1] or (x, y + 1) in traversed:
            state = 'left'
            x -= 1
        else:
            y += 1
    elif state == 'left':
        if x - 1 < 0 or (x - 1, y) in traversed:
            state = 'up'
            y -= 1
        else:
            x -= 1
    elif state == 'up':
        if y - 1 < 0 or (x, y - 1) in traversed:
            state = 'right'
            x += 1
        else:
             y -= 1
    c = closestColor(c, imgData[x, y], tolerance)

out.save('%.03f%s' % (tolerance, imgName))
print '100% complete'

Il faut une minute ou deux pour exécuter les images plus grandes, bien que je sois sûr que la logique de spirale pourrait être largement optimisée.

Résultats

Ils sont intéressants mais pas magnifiques. Étonnamment, une tolérance supérieure à 0,1 produit des résultats d'aspect assez précis.

La Grande Vague avec une tolérance de 0,03:

Joconde à 0,02 tolérance:

Lena à 0,03 tolérance, puis 0,01, puis 0,005, puis 0,003:

Divers à 0,1 tolérance, puis 0,07, puis 0,04, puis 0,01:

Cobra

@number float
use System.Drawing
class Program
    var source as Bitmap?
    var data as List<of uint8[]> = List<of uint8[]>()
    var canvas as List<of uint8[]> = List<of uint8[]>()
    var moves as int[] = @[0,1]
    var direction as bool = true
    var position as int[] = int[](0)
    var tolerance as float = 0f
    var color as uint8[] = uint8[](4)
    var rotated as bool = false
    var progress as int = 0
    def main
        args = CobraCore.commandLineArgs
        if args.count <> 3, throw Exception()
        .tolerance = float.parse(args[1])
        if .tolerance < 0 or .tolerance > 1, throw Exception()
        .source = Bitmap(args[2])
        .data = .toData(.source to !)
        .canvas = List<of uint8[]>()
        average = float[](4)
        for i in .data
            .canvas.add(uint8[](4))
            for n in 4, average[n] += i[n]/.source.height
        for n in 4, .color[n] = (average[n]/.source.width).round to uint8
        if .source.width % 2
            if .source.height % 2
                .position = @[0, .source.height-1]
                .update
                while .position[1] > 0, .up
                .right
            else
                .position = @[.source.width-1, .source.height-1]
                .update
                while .position[1] > 0, .up
                while .position[0] > 0, .left
                .down
        else
            if .source.height % 2
                .position = @[0,0]
                .update
            else
                .position = @[.source.width-1,0]
                .update
                while .position[0] > 0, .left
                .down
        .right
        .down
        while true
            if (1-.source.height%2)<.position[1]<.source.height-1
                if .moves[1]%2==0
                    if .direction, .down
                    else, .up
                else
                    if .moves[0]==2, .right
                    else, .left
            else
                .right
                if .progress == .data.count, break
                .right
                .right
                if .direction
                    .direction = false
                    .up
                else
                    .direction = true
                    .down
        image = .toBitmap(.canvas, .source.width, .source.height)
        if .rotated, image.rotateFlip(RotateFlipType.Rotate270FlipNone)
        image.save(args[2].split('.')[0]+'_snake.png')

    def right
        .position[0] += 1
        .moves = @[.moves[1], 0]
        .update

    def left
        .position[0] -= 1
        .moves = @[.moves[1], 2]
        .update

    def down
        .position[1] += 1
        .moves = @[.moves[1], 1]
        .update

    def up
        .position[1] -= 1
        .moves = @[.moves[1], 3]
        .update

    def update
        .progress += 1
        index = .position[0]+.position[1]*(.source.width)
        .canvas[index] = .closest(.color,.data[index])
        .color = .canvas[index]

    def closest(color1 as uint8[], color2 as uint8[]) as uint8[]
        d = .difference(color1, color2)
        if d > .tolerance
            output = uint8[](4)
            for i in 4, output[i] = (color1[i] + .tolerance * (color2[i] - _
            color1[i]) / d)to uint8
            return output
        else, return color2

    def difference(color1 as uint8[], color2 as uint8[]) as float
        d = ((color2[0]-color1[0])*(color2[0]-color1[0])+(color2[1]- _
        color1[1])*(color2[1]-color1[1])+(color2[2]-color1[2])*(color2[2]- _
        color1[2])+0f).sqrt
        return d / (255 * 3f.sqrt)

    def toData(image as Bitmap) as List<of uint8[]>
        rectangle = Rectangle(0, 0, image.width, image.height)
        data = image.lockBits(rectangle, System.Drawing.Imaging.ImageLockMode.ReadOnly, _
        image.pixelFormat) to !
        ptr = data.scan0
        bytes = uint8[](data.stride*image.height)
        System.Runtime.InteropServices.Marshal.copy(ptr, bytes, 0, _
        data.stride*image.height)
        pfs = Image.getPixelFormatSize(data.pixelFormat)//8
        pixels = List<of uint8[]>()
        for y in image.height, for x in image.width
            position = (y * data.stride) + (x * pfs)
            red, green, blue, alpha = bytes[position+2], bytes[position+1], _
            bytes[position], if(pfs==4, bytes[position+3], 255u8)
            pixels.add(@[red, green, blue, alpha])
        image.unlockBits(data)
        return pixels

    def toBitmap(pixels as List<of uint8[]>, width as int, height as int) as Bitmap
        image = Bitmap(width, height, Imaging.PixelFormat.Format32bppArgb)
        rectangle = Rectangle(0, 0, image.width, image.height)
        data = image.lockBits(rectangle, System.Drawing.Imaging.ImageLockMode.ReadWrite, _
        image.pixelFormat) to !
        ptr = data.scan0
        bytes = uint8[](data.stride*image.height)
        pfs = System.Drawing.Image.getPixelFormatSize(image.pixelFormat)//8
        System.Runtime.InteropServices.Marshal.copy(ptr, bytes, 0, _
        data.stride*image.height)
        count = -1
        for y in image.height, for x in image.width 
            pos = (y*data.stride)+(x*pfs)
            bytes[pos+2], bytes[pos+1], bytes[pos], bytes[pos+3] = pixels[count+=1]
        System.Runtime.InteropServices.Marshal.copy(bytes, 0, ptr, _
        data.stride*image.height)
        image.unlockBits(data)
        return image

Remplit l'image d'un serpent comme:

#--#
   |
#--#
|
#--#
   |

Cela permet un réglage des couleurs beaucoup plus rapide que les lignes dans des directions alternées, mais ne devient pas aussi polyédrique qu'une version à 3 larges.

Même à des tolérances très faibles, les bords d'une image sont toujours visibles (bien qu'à la perte de détails dans des résolutions plus petites).

0,01

0,1

0,01

0,01

0,1

0,03

0,005

C #

Snake commence au pixel supérieur gauche avec la couleur blanche et alterne de gauche à droite puis de droite à gauche dans l'image.

using System;
using System.Drawing;

namespace snake
{
    class Snake
    {
        static void MakeSnake(Image original, double tolerance)
        {
            Color snakeColor = Color.FromArgb(255, 255, 255);//start white
            Bitmap bmp = (Bitmap)original;
            int w = bmp.Width;
            int h = bmp.Height;
            Bitmap snake = new Bitmap(w, h);

            //even rows snake run left to right else run right to left
            for (int y = 0; y < h; y++)
            {
                if (y % 2 == 0)
                {
                    for (int x = 0; x < w; x++)//L to R
                    {
                        Color pix = bmp.GetPixel(x, y);
                        double diff = Snake.RGB_Distance(snakeColor, pix);
                        if (diff < tolerance)
                        {
                            snakeColor = pix;
                        }
                        //else keep current color
                        snake.SetPixel(x, y, snakeColor);
                    }
                }
                else
                {
                    for (int x = w - 1; x >= 0; x--)//R to L
                    {
                        Color pix = bmp.GetPixel(x, y);
                        double diff = Snake.RGB_Distance(snakeColor, pix);
                        if (diff < tolerance)
                        {
                            snakeColor = pix;
                        }
                        //else keep current color
                        snake.SetPixel(x, y, snakeColor);
                    }
                }
            }

            snake.Save("snake.png");
        }

        static double RGB_Distance(Color current, Color next)
        {
            int dr = current.R - next.R;
            int db = current.B - next.B;
            int dg = current.G - next.G;
            double d = Math.Pow(dr, 2) + Math.Pow(db, 2) + Math.Pow(dg, 2);
            d = Math.Sqrt(d) / (255 * Math.Sqrt(3));
            return d;
        }

        static void Main(string[] args)
        {
            try
            {
                string file = "input.png";
                Image img = Image.FromFile(file);
                double tolerance = 0.03F;
                Snake.MakeSnake(img, tolerance);
                Console.WriteLine("Complete");
            }
            catch(Exception e)
            {
                Console.WriteLine(e.Message);
            }

        }
    }
}

Tolérance de l'image résultante = 0,1