Wyobraź sobie ciągłą dwuwymiarową ścieżkę, która może tylko skręcać w lewo, w prawo lub iść prosto, nie może się przecinać i musi wypełniać prostokątną siatkę, taką jak siatka pikseli na obrazie. Nazwiemy tę ścieżkę wężem .

Ten powiększony przykład pokazuje ścieżkę węża na siatce 10 × 4, która zaczyna się na czerwono i zwiększa odcień o około 2% na każdym kroku, aż stanie się fioletowa. (Czarne linie mają jedynie podkreślać kierunek, w którym się porusza.)

Cel

Celem tego konkursu popularności jest napisanie algorytmu, który próbuje odtworzyć dany obraz za pomocą jednego węża, którego kolor zmienia się ciągle w niewielkich ilościach.

Twój program musi przyjmować obraz w prawdziwych kolorach o dowolnym rozmiarze, a także wartość zmiennoprzecinkową od 0 do 1 włącznie, z tolerancją .

Tolerancja określa maksymalną wielkość, którą kolor węża może zmieniać w każdym kroku wielkości piksela. Zdefiniujemy odległość między dwoma kolorami RGB jako odległość euklidesową między dwoma punktami RGB, gdy są ustawione na kostce kolorów RGB . Odległość zostanie następnie znormalizowana, więc maksymalna odległość wynosi 1, a minimalna odległość wynosi 0.

Pseudokod odległości kolorów: (Zakłada, że ​​wszystkie wartości wejściowe są liczbami całkowitymi w zakresie [0, 255]; dane wyjściowe są znormalizowane).

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

Jeśli wynik wywołania tej funkcji na bieżącym kolorze węża i innym kolorze jest większy niż podana tolerancja, wąż może nie zmienić się na inny kolor.

Jeśli wolisz, możesz użyć innej funkcji odległości kolorów. Musi to być coś dokładnego i dobrze udokumentowanego, takiego jak wymienione na stronie http://en.wikipedia.org/wiki/Color_difference . Musisz również znormalizować go, aby był w środku [0, 1], tj. Maksymalna możliwa odległość musi wynosić 1, a minimalna musi wynosić 0. Powiedz nam w odpowiedzi, jeśli używasz innej miary odległości.

Testuj obrazy

Powinieneś oczywiście opublikować swoje zdjęcia wyjściowe (a nawet animacje węża rosnącego, jeśli chcesz). Sugeruję opublikowanie różnych tych zdjęć przy użyciu różnych niskich tolerancji (może około 0,005 do 0,03).

(Większa wielka fala)

Wygraj kryteria

Jak wspomniano, jest to konkurs popularności. Najwyższa głosowana odpowiedź wygra. Odpowiedzi, które zapewniają najdokładniejsze i najbardziej estetyczne przedstawienie „ścieżki węża” obrazów wejściowych, powinny zostać poddane pod głosowanie.

Każdy użytkownik, który okaże się, że złośliwie przesyła obrazy, które nie są rzeczywistymi wężami, zostanie zdyskwalifikowany na zawsze.

Uwagi

• Można użyć tylko jednej ścieżki węża i musi ona całkowicie wypełnić obraz bez dwukrotnego dotknięcia tego samego piksela.
• Wąż może zaczynać się i kończyć w dowolnym miejscu obrazu.
• Wąż może zaczynać się w dowolnym kolorze.
• Wąż musi pozostać w granicach obrazu. Granice nie są cykliczne.
• Wąż nie może poruszać się po przekątnej ani więcej niż o jeden piksel na raz.

Pyton

Generuję ścieżkę dynamiczną, aby zminimalizować zmiany kolorów podczas podróży węża. Oto kilka zdjęć:

tolerancja = 0,01

Cykliczne ścieżki kolorów dla powyższych obrazów (od niebieskiego do czerwonego, coraz bardziej zielone w miarę powtarzania):

Ścieżka jest generowana, zaczynając od ścieżki początkowej, a następnie dodając do niej 2x2 pętle, aż obraz zostanie wypełniony. Zaletą tej metody jest to, że pętle można dodawać w dowolnym miejscu na ścieżce, dzięki czemu nie można pomalować się w kącie i mieć więcej swobody w budowaniu pożądanej ścieżki. Śledzę możliwe pętle przylegające do bieżącej ścieżki i przechowuję je w kupie, ważonej zmianą koloru wzdłuż pętli. Następnie zrywam pętlę z najmniejszą zmianą koloru i dodaję ją do ścieżki i powtarzam, aż obraz się zapełni.

Właściwie śledzę same pętle („DetourBlock” w kodzie), a następnie rekonstruuję ścieżkę; to był błąd, ponieważ istnieją specjalne przypadki nieparzystej szerokości / wysokości i spędziłem kilka godzin debugując metodę rekonstrukcji. No cóż.

Metryka generowania ścieżki wymaga dostrajania. Mam też pomysł na lepsze kolorowanie, ale pomyślałem, że najpierw to wyjdę, ponieważ działa całkiem dobrze. Z wyjątkiem tego, który wydaje się lepszy na niektórych stałych ścieżkach:

Oto kod Pythona z przeprosinami za moje okropne nawyki programistyczne:

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

I jeszcze kilka zdjęć przy bardzo niskiej tolerancji 0,001 :

A także świetna ścieżka fali, ponieważ jest schludna:

EDYTOWAĆ

Generowanie ścieżki wydaje się lepsze przy minimalizowaniu odległości między średnimi kolorami sąsiednich bloków, niż minimalizowaniu sumy odległości kolorów między sąsiadującymi pikselami. Okazuje się również, że można uśrednić kolory dowolnych dwóch ścieżek węża zgodnych z tolerancją i otrzymać inną ścieżkę węża zgodną z tolerancją. Przemierzam ścieżkę w obie strony i uśredniam je, co wygładza wiele artefaktów. Zombie Lena i Scary Hands Mona wyglądają znacznie lepiej. Ostateczne wersje:

Tolerancja 0,01 :

Tolerancja 0,001 :

Jawa

Mój program generuje ścieżkę węża dla danej szerokości i wysokości, używając algorytmu podobnego do tego, który generuje krzywą Hilberta.

(mała gra: na powyższym obrazku wąż zaczyna się w lewym górnym rogu. Czy możesz znaleźć, gdzie kończy się? Powodzenia :)

Oto wyniki dla różnych wartości tolerancji:

Tolerancja = 0,01

Tolerancja = 0,05

Tolerancja = 0,1

Tolerancja = 0,01

Z blokami pikseli 4x4 i widoczną ścieżką

Obliczanie ścieżki węża

Ścieżka węża jest przechowywana w podwójnej tablicy liczb całkowitych. Wąż zawsze wchodzi w siatkę w lewym górnym rogu. Istnieją 4 podstawowe operacje, które mój program może wykonać na danej ścieżce węża:

• utwórz nową ścieżkę węża dla siatki o szerokości 1 lub wysokości 1. Ścieżka jest prostą linią, która biegnie od lewej do prawej lub od góry do dołu, w zależności od przypadku.

• zwiększ wysokość siatki, dodając u góry ścieżkę węża od lewej do prawej, a następnie odbijając siatkę (wąż musi zawsze wchodzić do siatki w lewym górnym rogu)

• zwiększ szerokość siatki, dodając po lewej stronie ścieżkę węża od góry do dołu, a następnie odwracając siatkę (wąż musi zawsze wchodzić do siatki w lewym górnym rogu)

• podwoić wymiar siatki za pomocą algorytmu „stylu Hilberta” (patrz opis poniżej)

Korzystając z szeregu tych operacji atomowych, program jest w stanie wygenerować ścieżkę węża o dowolnym rozmiarze.

Poniższy kod oblicza (w odwrotnej kolejności), które operacje będą potrzebne do uzyskania danej szerokości i wysokości. Po obliczeniu akcje są wykonywane jeden po drugim, dopóki nie otrzymamy ścieżki węża o oczekiwanym rozmiarze.

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
    }

Podwojenie rozmiaru ścieżki węża:

Algorytm, który podwaja rozmiar działa w następujący sposób:

Rozważ ten węzeł, który jest powiązany z PRAWYM i DOLNYM. Chcę podwoić jego rozmiar.

 +-
 |

Istnieją 2 sposoby, aby podwoić jego rozmiar i zachować te same wyjścia (prawy i dolny):

 +-+- 
 |
 +-+
   |

lub

+-+
| |
+ +-
|

Aby określić, który wybrać, muszę dla każdego kierunku węzła obsługiwać wartość „przesunięcia”, wskazując, czy drzwi wyjściowe są przesunięte w lewo / prawo czy w górę / w dół. Podążam ścieżką, tak jak zrobiłby to wąż, i aktualizuję wartość przesunięcia wzdłuż ścieżki. Wartość przesunięcia określa jednoznacznie, którego rozwiniętego bloku muszę użyć w następnym kroku.

Pyton

Oto bardzo prosty algorytm na początek. Zaczyna się w lewym górnym rogu obrazu i spiralnie obraca się do wewnątrz, dzięki czemu kolor jest możliwie najbliższy kolorowi następnego piksela, pozostając w granicach tolerancji.

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'

Uruchomienie większych obrazów zajmuje minutę lub dwie, ale jestem pewien, że spiralna logika mogłaby zostać znacznie zoptymalizowana.

Wyniki

Są interesujące, ale nie wspaniałe. O dziwo, tolerancja powyżej 0,1 daje całkiem dokładne wyniki.

Wielka Fala przy tolerancji 0,03:

Mona Lisa przy tolerancji 0,02:

Lena z tolerancją 0,03, następnie 0,01, następnie 0,005, a następnie 0,003:

Różne rzeczy z tolerancją 0,1, następnie 0,07, następnie 0,04, a następnie 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

Wypełnia obraz wężem takim jak:

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

Pozwala to na znacznie szybsze dopasowanie kolorów niż tylko linie w naprzemiennych kierunkach, ale nie staje się tak blokowe, jak w przypadku wersji 3-szerokiej.

Nawet przy bardzo niskich tolerancjach krawędzie obrazu są nadal widoczne (chociaż przy utracie szczegółów w mniejszych rozdzielczościach).

0,01

0,1

0,01

0,01

0,1

0,03

0,005

DO#

Wąż zaczyna się od lewego górnego piksela w kolorze białym i zmienia się od lewej do prawej, a następnie od prawej do lewej w dół obrazu.

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

        }
    }
}

Wynikowa tolerancja obrazu = 0,1