Stellen Sie sich einen kontinuierlichen zweidimensionalen Pfad vor, der nur nach links, rechts oder gerade verlaufen kann, sich nicht selbst schneiden kann und ein rechteckiges Raster wie das Pixelraster in einem Bild ausfüllen muss. Wir werden diese Art von Pfad eine Schlange nennen .

Dieses vergrößerte Beispiel zeigt einen Schlangenpfad in einem 10 × 4-Raster, der rot beginnt und bei jedem Schritt den Farbton um etwa 2% erhöht, bis er violett ist. (Die schwarzen Linien sollen nur die Richtung betonen, in die sie weisen.)

Tor

Das Ziel dieses Beliebtheitswettbewerbs ist es, einen Algorithmus zu schreiben, der versucht, ein bestimmtes Bild mit einer einzelnen Schlange wiederherzustellen, deren Farbe sich kontinuierlich in kleinen Mengen ändert.

Ihr Programm muss ein Echtfarbenbild beliebiger Größe sowie einen Gleitkommawert zwischen 0 und 1 einschließlich der Toleranz aufnehmen .

Toleranz definiert den maximalen Betrag, den die Farbe der Schlange in jedem Pixelschritt ändern darf. Wir definieren den Abstand zwischen zwei RGB-Farben als den euklidischen Abstand zwischen den beiden RGB-Punkten, wenn diese auf einem RGB-Farbwürfel angeordnet sind . Der Abstand wird dann normalisiert, sodass der maximale Abstand 1 und der minimale Abstand 0 beträgt.

Farbabstand-Pseudocode: (Angenommen, alle Eingabewerte sind ganze Zahlen im Bereich [0, 255]; Ausgabe ist normalisiert.)

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

Wenn das Ergebnis des Aufrufs dieser Funktion für die aktuelle Farbe der Schlange und eine andere Farbe größer als die angegebene Toleranz ist, ändert sich die Schlange möglicherweise nicht in diese andere Farbe.

Wenn Sie es vorziehen, können Sie eine andere Farbabstandsfunktion verwenden. Es muss etwas genaues und gut dokumentiertes sein, wie es unter http://en.wikipedia.org/wiki/Color_difference aufgeführt ist . Du musst es auch normalisieren, um in dir zu sein[0, 1] , dh die maximal mögliche Entfernung muss 1 und die minimale 0 sein. Teilen Sie uns in Ihrer Antwort mit, ob Sie eine andere Entfernungsmetrik verwenden.

Bilder testen

Sie sollten natürlich Ihre Ausgabebilder veröffentlichen (und sogar Animationen der Schlange, wenn Sie möchten). Ich schlage vor, eine Vielzahl dieser Bilder mit unterschiedlichen niedrigen Toleranzen (etwa 0,005 bis 0,03) zu veröffentlichen.

(Größere große Welle)

Gewinnkriterien

Wie gesagt, dies ist ein Beliebtheitswettbewerb. Die am höchsten bewertete Antwort gewinnt. Antworten, die die genaueste und ästhetisch ansprechendste Darstellung der eingegebenen Bilder auf dem "Schlangenpfad" liefern, sollten bewertet werden.

Jeder Benutzer, der in böswilliger Absicht Bilder einsendet, die keine echten Schlangen sind, wird für immer disqualifiziert.

Anmerkungen

• Es darf nur ein Schlangenpfad verwendet werden, der das Bild vollständig ausfüllen muss, ohne dass dasselbe Pixel zweimal berührt wird.
• Die Schlange kann an einer beliebigen Stelle im Bild beginnen und enden.
• Die Schlange kann in jeder Farbe beginnen.
• Die Schlange muss im Bild bleiben. Die Grenzen sind nicht zyklisch.
• Die Schlange kann sich nicht diagonal oder mehr als ein Pixel gleichzeitig bewegen.

Python

Ich erstelle einen dynamischen Pfad, um die Farbveränderungen auf dem Weg der Schlange zu minimieren. Hier sind einige Bilder:

Toleranz = 0,01

Zyklische Farbpfade für die obigen Bilder (blau bis rot, wird bei Wiederholungen grüner):

Der Pfad wird erzeugt, indem mit einem Anfangspfad begonnen und dann 2x2 Schleifen hinzugefügt werden, bis das Bild gefüllt ist. Der Vorteil dieser Methode ist, dass die Schleifen überall auf dem Pfad hinzugefügt werden können, sodass Sie sich nicht in eine Ecke malen können und mehr Freiheit haben, den gewünschten Pfad zu erstellen. Ich verfolge die möglichen Schleifen neben dem aktuellen Pfad und speichere sie auf einem Haufen, gewichtet durch die Farbänderung entlang der Schleife. Ich löse dann die Schleife mit der geringsten Farbänderung und füge sie dem Pfad hinzu und wiederhole dies, bis das Bild gefüllt ist.

Ich verfolge die Schleifen tatsächlich alleine ('DetourBlock' im Code) und rekonstruiere dann den Pfad. Dies war ein Fehler, da es einige Sonderfälle für ungerade Breite / Höhe gibt und ich mehrere Stunden damit verbracht habe, die Rekonstruktionsmethode zu debuggen. Naja.

Die Metrik für die Pfadgenerierung muss optimiert werden, und ich habe auch eine Idee für eine bessere Einfärbung, aber ich dachte, ich würde dies zuerst herausholen, da es recht gut funktioniert. Abgesehen von diesem, der auf einigen der festgelegten Pfade besser zu sein scheint:

Hier ist der Python-Code, mit Entschuldigungen für meine schrecklichen Codierungsgewohnheiten:

# 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()

Und noch ein paar Bilder mit einer sehr geringen Toleranz von 0,001 :

Und auch den tollen Wellenweg, weil er ordentlich ist:

BEARBEITEN

Die Pfaderzeugung scheint besser zu sein, wenn der Farbabstand zwischen den Durchschnittsfarben benachbarter Blöcke minimiert wird, als die Summe der Farbabstände zwischen ihren benachbarten Pixeln zu minimieren. Es hat sich außerdem herausgestellt, dass Sie die Farben von zwei toleranzkonformen Schlangenpfaden mitteln und einen anderen toleranzkonformen Schlangenpfad erhalten können. Ich gehe also beide Wege und mittle sie, wodurch viele Artefakte ausgeglichen werden. Zombie Lena und Scary Hands Mona sehen viel besser aus. Endgültige Versionen:

Toleranz 0,01 :

Toleranz 0,001 :

Java

Mein Programm generiert einen Schlangenpfad für eine bestimmte Breite und Höhe, wobei ein Algorithmus verwendet wird, der dem Algorithmus ähnelt, der die Hilbert-Kurve generiert.

(kleines Spiel: im obigen Bild beginnt die Schlange in der oberen linken Ecke. Kannst du herausfinden, wo sie endet? Viel Glück :)

Hier sind die Ergebnisse für verschiedene Toleranzwerte:

Toleranz = 0,01

Toleranz = 0,05

Toleranz = 0,1

Toleranz = 0,01

Mit 4x4 Pixelblöcken & Pfad sichtbar

Berechnung des Schlangenpfades

Ein Schlangenpfad wird in einem ganzzahligen Array mit doppelter Dimension gespeichert. Die Schlange betritt das Gitter immer an der oberen linken Ecke. Es gibt 4 grundlegende Operationen, die mein Programm auf einem bestimmten Schlangenpfad ausführen kann:

• Erstellen Sie einen neuen Schlangenpfad für ein Raster mit der Breite 1 oder Höhe 1. Der Pfad ist nur eine einfache Linie, die je nach Fall von links nach rechts oder von oben nach unten verläuft.

• Erhöhen Sie die Gitterhöhe, indem Sie oben einen Schlangenpfad von links nach rechts hinzufügen und dann das Gitter spiegeln (die Schlange muss immer über die obere linke Ecke in das Gitter eintreten).

• Erhöhen Sie die Gitterbreite, indem Sie links einen Schlangenpfad von oben nach unten hinzufügen und dann das Gitter umdrehen (die Schlange muss immer durch die obere linke Ecke in das Gitter eintreten).

• Verdoppeln Sie die Dimension des Gitters mit einem "Hilbert-Stil" -Algorithmus (siehe Beschreibung unten)

Unter Verwendung einer Reihe dieser atomaren Operationen ist das Programm in der Lage, einen Schlangenpfad beliebiger Größe zu erzeugen.

Der folgende Code berechnet (in umgekehrter Reihenfolge), welche Operationen erforderlich sind, um eine bestimmte Breite und Höhe zu erhalten. Einmal berechnet, werden die Aktionen einzeln ausgeführt, bis wir einen Schlangenpfad der erwarteten Größe erhalten.

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
    }

Verdoppelung der Schlangenpfadgröße:

Der Algorithmus, der die Größe verdoppelt, funktioniert wie folgt:

Betrachten Sie diesen Knoten, der mit RECHTS und UNTEN verknüpft ist. Ich möchte seine Größe verdoppeln.

 +-
 |

Es gibt zwei Möglichkeiten, die Größe zu verdoppeln und die gleichen Ausgänge beizubehalten (rechts und unten):

 +-+- 
 |
 +-+
   |

oder

+-+
| |
+ +-
|

Um zu bestimmen, welche zu wählen ist, muss ich für jede Knotenrichtung einen "Verschiebungs" -Wert behandeln, der angibt, ob die Ausgangstür nach links / rechts oder oben / unten verschoben ist. Ich folge dem Pfad, wie es die Schlange tun würde, und aktualisiere den Verschiebungswert entlang des Pfades. Der Verschiebungswert bestimmt eindeutig, welchen erweiterten Block ich für den nächsten Schritt verwenden muss.

Python

Hier ist ein sehr einfacher Algorithmus, mit dem Sie loslegen können. Es beginnt oben links im Bild und dreht sich im Uhrzeigersinn nach innen, um die Farbe so nah wie möglich an der Farbe des nächsten Pixels zu bringen, während die Toleranz eingehalten wird.

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'

Es dauert ein oder zwei Minuten, um die größeren Bilder auszuführen, obwohl ich sicher bin, dass die Spirallogik erheblich optimiert werden könnte.

Ergebnisse

Sie sind interessant, aber nicht wunderschön. Erstaunlicherweise führt eine Toleranz über 0,1 zu ziemlich genau aussehenden Ergebnissen.

Die Große Welle mit einer Toleranz von 0,03:

Mona Lisa bei einer Toleranz von 0,02:

Lena bei einer Toleranz von 0,03, dann 0,01, dann 0,005, dann 0,003:

Verschiedenes mit einer Toleranz von 0,1, dann 0,07, dann 0,04 und dann 0,01:

Kobra

@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

Füllt das Bild mit einer Schlange wie:

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

Dies ermöglicht eine viel schnellere Farbanpassung als nur Linien in wechselnden Richtungen, wird jedoch nicht so blockartig wie eine 3-breite Version.

Selbst bei sehr geringen Toleranzen sind die Bildränder noch sichtbar (obwohl bei kleineren Auflösungen der Detailverlust auftritt).

0,01

0,1

0,01

0,01

0,1

0,03

0,005

C #

Die Schlange beginnt am oberen linken Pixel mit der Farbe Weiß und wechselt von links nach rechts und dann von rechts nach links im Bild.

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);
            }

        }
    }
}

Ergebnisbildtoleranz = 0,1