bbbradsmith/serrator.py

## serrator.py
#!/usr/bin/env python3

# serrator
#
# Explanation: https://www.patreon.com/posts/serrator-game-109214047
#
# Inspired by the way the background images in Sierra games drew in progressively.
# Usually too fast to really see, but on a very slow computer, or artificially slowed,
# the draw-in process was quite fascinating to watch:
#   https://twitter.com/PixelArtSierra
#   https://www.youtube.com/@PixelArtSierra
#
# This program attempts to synthesize the effect from finished bitmap images.
# It won't quite look like how an artist would draw it in the way the hand-made
# Sierra examples might, but it gives a bit of that flavour of a progressive draw.
#
# Place PNG images in the same folder as this script and run it.
# FORCE_EGA can force images to use the EGA palette,
# which is recommended if the images are already using that colour set,
# but otherwise the image should have a maximum of 256 colours,
# though this works much better and faster on images with fewer colours,
# and it is best if the image already has its own palette.
# The BG parameter is important for choosing the starting colour of the screen,
# but if the image does not have its own palette the choice may not be predictable.
#
# This can be used on the command line, use -h or --help for details.
#
# It may take a few minutes for each image. You can turn on PRINT_STEPS if you'd
# like a crude progress indicator.
#
# The process tries to progressively simplify the image, eliminating the smallest detail
# one at a time until it reduces to simpler and larger shapes. Once the entire image has
# been eliminated, it reassembles it in reverse to create the animation.
#
# Brad Smith, 2024
# https://rainwarrior.ca

# Requires Pillow library:
#   https://pillow.readthedocs.io/en/stable/installation/basic-installation.html

import PIL.Image
import os.path
import random
import argparse

#
# Parameters
# These can all be set from the command line. Use -h or --help to print usage info.
#

INFILE = None # process a single image instead of a directory
INDIR = "."
BG = 0 # background colour (index to palette)
FORCE_EGA = False # use 16-colour EGA palette instead of the PNG's palette

# image decomposition parameters
FILL_MIN = 50 # minimum pixels for a fill step
SURROUND_RATIO = 2.5 # only use border fill-in when the region will increase in size significantly, otherwise fill-in with background colour
DITHER_MIN = 10 # minimum pixels for dither step (includes both colours)
STROKE_TIES = 40 # strokes within this number of pixels should tiebreak with positional coherency first

# reconstruction animation
STROKE_SAMPLES = 10 # random sampling for drawing in (lower = more dithered, higher = more ordered)
FRAME_MIN = 300 # minimum pixels per frame (add steps until this is met)
FRAME_MAX = 500 # maximum pixels per frame (break up any single step longer than this)
FRAME_TIME = 20 # ms per frame
FRAME_LAST = 3000 # ms on final frame

# skip saving STEPDIR or OUTDIR preview images
PRINT_STEPS = False
PREVIEW_STEP = False
PREVIEW_OUT = False
STEPDIR = "step"
OUTDIR = "out"

#
# parse command line
#

if __name__ == "__main__":
    ap = argparse.ArgumentParser()
    ag = ap.add_argument_group("Input")
    ag.add_argument("-INFILE",help="Single input file",metavar="file")
    ag.add_argument("-INDIR",help="Input directory, all PNG files used",metavar="dir")
    ag.add_argument("-BG",type=int,help="Background colour index, default %d" % BG,metavar="c")
    ag.add_argument("-FORCE_EGA",action="store_const",const=True,help="Force the image to use the standard 16-colour EGA palette")
    ag = ap.add_argument_group("Decomposition")
    ag.add_argument("-FILL_MIN",type=int,help="Minimum pixels to generate a fill step, default %d" % FILL_MIN,metavar="n")
    ag.add_argument("-SURROUND_RATIO",type=float,help="Ratio required for surrounding colour to replace the removed step, instead of the background colour, default %s" % str(SURROUND_RATIO),metavar="r")
    ag.add_argument("-DITHER_MIN",type=int,help="Minimum pixels to generate a dither step (includes both colours), default %d" % DITHER_MIN,metavar="n")
    ag.add_argument("-STROKE_TIES",type=int,help="Strokes within this number of pixels should break ties by favouring closer strokes first, default %d" % STROKE_TIES,metavar="n")
    ag = ap.add_argument_group("Animation")
    ag.add_argument("-STROKE_SAMPLES",type=int,help="Random sampling for drawing in (lower = more dithered, higher = more ordered), default %d" % STROKE_SAMPLES,metavar="n")
    ag.add_argument("-FRAME_MIN",type=int,help="Minimum pixels per frame (adds steps until this is met), default %d" % FRAME_MIN,metavar="n")
    ag.add_argument("-FRAME_MAX",type=int,help="Maximum pixels per frame (breaks up any single step longer than this), default %d" % FRAME_MAX,metavar="n")
    ag.add_argument("-FRAME_TIME",type=int,help="Milliseconds per frame (GIF standard minimum is 20), default %d" % FRAME_TIME,metavar="n")
    ag.add_argument("-FRAME_LAST",type=int,help="Milliseconds on final frame, default %d" % FRAME_LAST,metavar="n")
    ag = ap.add_argument_group("Breakdown")
    ag.add_argument("-PRINT_STEPS",action="store_const",const=True,help="Print details of each step to console")
    ag.add_argument("-PREVIEW_STEP",action="store_const",const=True,help="Save a PNG to STEPDIR for each decomposed step")
    ag.add_argument("-PREVIEW_OUT",action="store_const",const=True,help="Save a PNG to OUTDIR for each animated output step")
    ag.add_argument("-STEPDIR",help="Directory output for PREVIEW_STEP, default %s" % STEPDIR,metavar="dir")
    ag.add_argument("-OUTDIR",help="Directory output for PREVIEW_OUT, default %s" % OUTDIR,metavar="dir")
    args = ap.parse_args()
    for (k,v) in args.__dict__.items():
        if v != None:
            #print("ARG: "+k+": "+str(v))
            globals()[k] = v

#
# Global data
#

src = None
img = None

# create preview directories if needed
if PREVIEW_STEP and not os.path.exists(STEPDIR):
    os.makedirs(STEPDIR)
if PREVIEW_OUT and not os.path.exists(OUTDIR):
    os.makedirs(OUTDIR)

#
# EGA palette
#

PALETTE = [
    (0x00,0x00,0x00),
    (0x00,0x00,0xAA),
    (0x00,0xAA,0x00),
    (0x00,0xAA,0xAA),
    (0xAA,0x00,0x00),
    (0xAA,0x00,0xAA),
    (0xAA,0x55,0x00),
    (0x55,0x55,0x55), # swapped greys so that < is darker (usually)
    (0xAA,0xAA,0xAA),
    (0x55,0x55,0xFF),
    (0x55,0xFF,0xFF),
    (0x55,0xFF,0x55),
    (0xFF,0x55,0x55),
    (0xFF,0x55,0xFF),
    (0xFF,0xFF,0x55),
    (0xFF,0xFF,0xFF)]

# closest-match remap of img to RGB palette
def img_remap(img, palette):
    ims = img.convert("RGB")
    imp = PIL.Image.new("P",ims.size,color=0)
    for y in range(ims.size[1]):
        for x in range(ims.size[0]):
            p = ims.getpixel((x,y))
            mag = ((255**2)*3)+1
            mat = 0
            for i in range(len(palette)):
                m = sum([(a-b)**2 for (a,b) in zip(p,palette[i])])
                if m < mag: # better match
                    mat = i
                    mag = m
                    if m == 0: break # perfect match
            imp.putpixel((x,y),mat)
    imp.putpalette([p for tup in palette for p in tup[0:3]])
    return imp

#
# decompose into steps
#

# each draw step is a set of pixel coordinates (area),
# optionally a set of edge pixel coordinates (edge),
# the colour of the area+edge pixels (cs),
# the colour they should be drawn on top of (cr),
# and a draw type:
DITHER = 0 # checkerboard dithering (no edge)
FILL   = 1 # 4-way connected region: draw edge first, then area
STROKE = 2 # region connected up to 2 pixels away (no edge)
TNAMES = ["dither","fill","stroke"]

# adding a step "undoes" that step from the image by replacing it an underlying colour
steps = []
def add_step(area,edge,cs,cr,t):
    global steps
    global img
    assert(cr != cs)
    index = len(steps)
    steps.append((area,edge,cs,cr,t))
    for (x,y) in area:
        img.putpixel((x,y),cr)
    for (x,y) in edge:
        img.putpixel((x,y),cr)
    if PREVIEW_STEP:
        img.save(os.path.join(STEPDIR,"%05d.png" % index))
    if PRINT_STEPS:
        print("%05d: %s (%d pixels) %d -> %d" % (index,TNAMES[t],len(area)+len(edge),cr,cs))

# dither step identification:
# - scan for 3x3 areas with dither colour pairs
# - flood-fill each identified area to find its full extent
# - use the candidate with the most pixels first
# - repeat
def add_dithers():
    (w,h) = img.size
    while True:
        best = None
        visited = set()
        for y in range(0,h-2):
            for x in range(0,w-2):
                if (x,y) in visited: continue
                # find pair of colours
                c = (img.getpixel((x+0,y+0)),
                     img.getpixel((x+1,y+0)))
                if c[0] == c[1]: continue
                if ((x ^ y) & 1) != 0: # swap if on an odd pixel
                     c = (c[1],c[0])
                begin = True
                for ty in range(0,3):
                    for tx in range(0,3):
                        cd = c[(tx ^ ty) & 1]
                        if cd != img.getpixel((x+tx,y+ty)):
                            begin = False
                            break
                    if not begin: break
                if not begin: continue
                # found a 3x3 area, flood fill search
                area = set()
                queue = [(x,y)]
                while len(queue) > 0:
                    (dx,dy) = queue.pop(0)
                    if (dx,dy) in visited: continue
                    if dx < 0 or dy < 0 or dx >= w or dy >= h: continue
                    cd = c[(dx ^ dy) & 1]
                    if cd != img.getpixel((dx,dy)): continue
                    visited.add((dx,dy))
                    area.add((dx,dy))
                    queue.append((dx+1,dy))
                    queue.append((dx-1,dy))
                    queue.append((dx,dy+1))
                    queue.append((dx,dy-1))
                candidate = (area, c)
                if best == None or len(area) > len(best[0]):
                    best = candidate
        if best == None: break
        (area,c) = best
        if len(area) < DITHER_MIN: break
        dither_area = set()
        keep = 0
        t = DITHER
        if c[1] > c[0]: keep = 1 # dither a lighter colour on top of a darker region
        if (c[keep^1] == BG): keep ^= 1 # exception: don't dither on top of BG
        for (x,y) in area:
            if ((x^y) & 1) == keep:
                dither_area.add((x,y))
        add_step(dither_area,{},c[keep],c[keep^1],t)

# flood-fill and stroke step identification
# - scan for contiguous areas
#   - flood-fill is 4-way connected
#   - stroke is connected up to 2 pixels away
# - remove the smallest group and replace with its surrounding colour if appropriate
#   - smallest-first allows small details to be filled-in by surrounding colour
# - repeat
def add_floodstrokes():
    (w,h) = img.size
    while True:
        best = None
        best_pixels = 0
        visitedf = set()
        visiteds = set()
        for y in range(0,h):
            for x in range(0,w):
                c = img.getpixel((x,y))
                if c == BG:
                    visitedf.add((x,y))
                    visiteds.add((x,y))
                    continue
                # flood candidate at this pixel
                area = set()
                edges = set()
                if (x,y) not in visitedf:
                    queue = [(x,y)]
                    while len(queue) > 0:
                        (dx,dy) = queue.pop(0)
                        if (dx,dy) in visitedf: continue
                        if dx < 0 or dy < 0 or dx >= w or dy >= h: continue
                        if c != img.getpixel((dx,dy)): continue
                        visitedf.add((dx,dy))
                        queue.append((dx+1,dy))
                        queue.append((dx-1,dy))
                        queue.append((dx,dy+1))
                        queue.append((dx,dy-1))
                        # separate edges
                        if (dx > 0 and c != img.getpixel((dx-1,dy))) or \
                           (dy > 0 and c != img.getpixel((dx,dy-1))) or \
                           ((dx+1) < w and c != img.getpixel((dx+1,dy))) or \
                           ((dy+1) < h and c != img.getpixel((dx,dy+1))):
                            edges.add((dx,dy))
                            continue
                        # keep interior
                        area.add((dx,dy))
                # stroke candidate at this pixel
                strokearea = set()
                strokeedges = set()
                if (x,y) not in visiteds:
                    queue = [(x,y)]
                    while len(queue) > 0:
                        (dx,dy) = queue.pop(0)
                        if (dx,dy) in visiteds: continue
                        if dx < 0 or dy < 0 or dx >= w or dy >= h: continue
                        if c != img.getpixel((dx,dy)): continue
                        visiteds.add((dx,dy))
                        queue.append((dx+1,dy))
                        queue.append((dx-1,dy))
                        queue.append((dx,dy+1))
                        queue.append((dx,dy-1))
                        queue.append((dx+2,dy)) # 2 pixels away
                        queue.append((dx-2,dy))
                        queue.append((dx,dy+2))
                        queue.append((dx,dy-2))
                        queue.append((dx+1,dy+1)) # corners
                        queue.append((dx-1,dy+1))
                        queue.append((dx+1,dy-1))
                        queue.append((dx-1,dy-1))
                        if (dx > 0 and c != img.getpixel((dx-1,dy))) or \
                           (dy > 0 and c != img.getpixel((dx,dy-1))) or \
                           ((dx+1) < w and c != img.getpixel((dx+1,dy))) or \
                           ((dy+1) < h and c != img.getpixel((dx,dy+1))):
                            strokeedges.add((dx,dy))
                            continue
                        strokearea.add((dx,dy))
                # best of either stroke or flood
                pixels = len(area) + len(edges)
                strokepixels = len(strokearea) + len(strokeedges)
                candidate = (area, edges, c, FILL)
                if (pixels < 1) or (len(area) < FILL_MIN) or (strokepixels > 0 and strokepixels < pixels):
                    pixels = strokepixels
                    candidate = (strokearea, strokeedges, c, STROKE)
                if best == None or (pixels > 0 and pixels < best_pixels):
                    best = [candidate]
                    best_pixels = pixels
                elif pixels == best_pixels:
                    best.append(candidate)
        if best == None: break
        invalid_c = set()
        best_type = best[0][3]
        for (area,edges,c,t) in best:
            if c in invalid_c: continue # any groups using a previous replacement colour are now invalid
            if t != best_type: continue # can't mix flood and stroke in a single pass
            cr = BG
            # use surrounding colour as replacement
            surround = []
            for (dx,dy) in edges:
                def add_surround(x,y):
                    if x < 0 or x >= img.width or y < 0 or y >= img.height: return
                    r = img.getpixel((x,y))
                    if r == c: return
                    while r >= len(surround):
                        surround.append(0)
                    surround[r] += 1
                add_surround(dx-1,dy)
                add_surround(dx+1,dy)
                add_surround(dx,dy-1)
                add_surround(dx,dy+1)
            best_cr = 0
            for i in range(len(surround)):
                if surround[i] > best_cr:
                    best_cr = surround[i]
                    cr = i
            # count pixels in replacement region, if not above ratio just use background to replace instead
            imt = img.copy()
            coord = None
            for a in area: imt.putpixel(a,cr)
            for e in edges: imt.putpixel(e,cr)
            visited = set()
            queue = list(area) + list(edges)
            count = 0
            while len(queue) > 0:
                (dx,dy) = queue.pop(0)
                if (dx,dy) in visited: continue
                visited.add((dx,dy))
                if dx < 0 or dy < 0 or dx >= w or dy >= h: continue
                if cr != imt.getpixel((dx,dy)): continue
                count += 1
                queue.append((dx-1,dy))
                queue.append((dx+1,dy))
                queue.append((dx,dy-1))
                queue.append((dx,dy+1))
            if (count / best_pixels) < SURROUND_RATIO:
                cr = BG # fall to background instead
            # add as fill if over a certain size, otherwise stroke
            if t == FILL and len(area) >= FILL_MIN:
                add_step(area,edges,c,cr,FILL)
            else:
                add_step(area.union(edges),{},c,cr,STROKE)
            invalid_c.add(cr) # any other strokes/fills using c/cr are now invalid

#
# rebuild the image with animation
#

last_px = 0
last_py = 0
last_c = BG
frame_pixels = 0
frames = []

def do_frame():
    global frame_pixels
    global frames
    index = len(frames)
    if PRINT_STEPS: print("%05d: %d pixels (%d steps remain)" % (index,frame_pixels,len(steps)))
    if PREVIEW_OUT:
        img.save(os.path.join(OUTDIR,"%05d.png" % (index)))
    frames.append(img.copy())
    frame_pixels = 0

def do_pixel(x,y,c):
    global frame_pixels
    global last_px
    global last_py
    global last_c
    global img
    last_px = x
    last_py = y
    last_c = c
    frame_pixels += 1
    img.putpixel((x,y),c)
    if (frame_pixels >= FRAME_MAX):
        do_frame()

def do_area(area,cs):
    for (x,y) in area:
        do_pixel(x,y,cs)

def do_horizontal(area,cs,minx,maxx,mx,fallback=False):
    global src
    d = 1
    if ((maxx - mx) < (mx - minx)): # right to left (trying to start with densest area)
        d = -1
    while len(area) > 0:
        if (len(area) < STROKE_SAMPLES):
            do_area(area,cs)
            return
        s = random.sample(list(area),STROKE_SAMPLES)
        (x,y) = s[0]
        for ss in s[1:]:
            if (ss[0] * d) < (x * d):
                (x,y) = ss
        if fallback: cs = src.getpixel((x,y)) # if in fallback use reveal the original image instead
        do_pixel(x,y,cs)
        area.remove((x,y))

def do_vertical(area,cs,miny,maxy,my,fallback=False):
    global src
    d = 1
    if ((maxy - my) < (my - miny)): # bottom to top
        d = -1
    while len(area) > 0:
        if (len(area) < STROKE_SAMPLES):
            do_area(area,cs)
            return
        s = random.sample(list(area),STROKE_SAMPLES)
        (x,y) = s[0]
        for ss in s[1:]:
            if (ss[1] * d) < (y * d):
                (x,y) = ss
        if fallback: cs = src.getpixel((x,y))
        do_pixel(x,y,cs)
        area.remove((x,y))

def do_step(s,fallback=False):
    (area,edges,cs,cr,t) = s
    if (len(edges)>0):
        if not fallback: # do edges of fill as separate stroke first
            do_step((edges,{},cs,cr,STROKE),False)
        else: # don't do outline with fallback
            area = area.union(edges)
    if PRINT_STEPS: print("Step: %s %d pixels (%d -> %d)" % \
        (TNAMES[t] + (" (fallback)" if fallback else ""),len(area),cr,cs))
    # count horizontal edges, vertical edges, and compute average, min, max
    minx = img.width - 1
    miny = img.height - 1
    maxx = 0
    maxy = 0
    mx = 0
    my = 0
    ex = 0
    ey = 0
    for (x,y) in area:
        mx += x
        my += y
        if (x+1,y) not in edges: ex += 1
        if (x,y+1) not in edges: ey += 1
        minx = min(x,minx)
        miny = min(y,miny)
        maxx = max(x,maxx)
        maxy = max(y,maxy)
    mx = int(mx/len(area))
    my = int(my/len(area))
    # more horizontal edges = draw left to right, more vertical = top to bottom
    if (ey > ex): do_vertical(  area,cs,miny,maxy,my,fallback)
    else:         do_horizontal(area,cs,minx,maxx,mx,fallback)

def ready_step(s):
    (area,edges,cs,cr,t) = s
    for a in area:
        if img.getpixel(a) != cr:
            return False
    for a in edges:
        if img.getpixel(a) != cr:
            return False
    return True

def animate(outgif):
    global img
    global frames
    global last_px
    global last_py
    global last_c
    global frame_pixels
    img = src.copy()
    frames = []
    last_px = src.width / 2
    last_py = src.height / 2
    last_c = BG
    frame_pixels = 0
    # first frame is BG colour
    for y in range(img.height):
        for x in range(img.width):
            img.putpixel((x,y),BG)
    do_frame()
    # prioritize:
    # - largest dither not on BG where all pixels are ready
    # - largest unit of any kind that has all its pixels ready
    #   but break tie by:
    #   - stroke with same colour as last
    #   - stroke with point closest to last written pixel
    while len(steps) > 0:
        best = -1
        best_pixels = -1
        fallback = False
        # largest dither not on BG where all pixels are ready
        for i in range(len(steps)):
            if not ready_step(steps[i]): continue
            (area,edges,cs,cr,t) = steps[i]
            if t != DITHER: continue
            pixels = len(area) + len(edges)
            if (best < 0) or (pixels >= best_pixels):
                best = i
                best_pixels = pixels
        # largest ready flood fill or stroke
        if (best < 0):
            best_dist = -1
            best_color = BG
            for i in range(len(steps)):
                if not ready_step(steps[i]): continue
                (area,edges,cs,cr,t) = steps[i]
                pixels = len(area) + len(edges)
                if ((best < 0) or (pixels >= (best_pixels - STROKE_TIES))):
                    dist = -1
                    # compute closest distance to last pixel
                    for (x,y) in area:
                        d = abs(x-last_px) + abs(y-last_py)
                        if dist < 0 or d < dist:
                            dist = d
                    for (x,y) in edges:
                        d = abs(x-last_px) + abs(y-last_py)
                        if dist < 0 or d < dist:
                            dist = d
                    # break tie by: same colour as last pixel, then closest to last pixel
                    if pixels > best_pixels or \
                       (cs == last_c and best_color != last_c) or \
                       (best_dist < 0) or (dist < best_dist):
                        best = i
                        best_dist = dist
                        best_color = cs
                        best_pixels = max(pixels,best_pixels)
        # fallback to smallest group if nothing is ready
        if (best < 0):
            fallback = True
            for i in range(len(steps)):
                (area,edges,cs,cr,t) = steps[i]
                pixels = len(area) + len(edges)
                if (best < 0) or (pixels < best_pixels):
                    best_pixels = pixels
                    best = i
        # apply best step
        do_step(steps[best],fallback)
        if frame_pixels >= FRAME_MIN:
            do_frame()
        del steps[best]
    # finish
    if (frame_pixels > 0): do_frame()
    img = src.copy()
    do_frame()
    print("Finished animation.")
    frames[0].save(outgif,save_all=True,append_images=frames[1:],loop=0,duration=([FRAME_TIME]*(len(frames)-1))+[FRAME_LAST])
    print(outgif)

#
# create the animation from an image
#

def serrator(infile, outgif):
    global src
    global img
    src = PIL.Image.open(infile)
    print("Open: %s (%dx%d) %s" % (infile,src.width,src.height,src.mode))
    if FORCE_EGA:
        src = img_remap(src,PALETTE)
    elif src.mode != 'P':
        src = src.convert('P', dither=None, palette=PIL.Image.ADAPTIVE)
    img = src.copy()
    # decompose image
    global steps
    steps = []
    add_dithers()
    add_floodstrokes()
    # make animation
    animate(outgif)

worklist = []
if INFILE:
    worklist = [INFILE]
else:
    for f in os.listdir(INDIR):
        if (f.lower().endswith(".png")):
            worklist.append(os.path.join(INDIR,f))

for w in worklist:
    serrator(w,w+".gif")
	#!/usr/bin/env python3

	# serrator
	#
	# Explanation: https://www.patreon.com/posts/serrator-game-109214047
	#
	# Inspired by the way the background images in Sierra games drew in progressively.
	# Usually too fast to really see, but on a very slow computer, or artificially slowed,
	# the draw-in process was quite fascinating to watch:
	# https://twitter.com/PixelArtSierra
	# https://www.youtube.com/@PixelArtSierra
	#
	# This program attempts to synthesize the effect from finished bitmap images.
	# It won't quite look like how an artist would draw it in the way the hand-made
	# Sierra examples might, but it gives a bit of that flavour of a progressive draw.
	#
	# Place PNG images in the same folder as this script and run it.
	# FORCE_EGA can force images to use the EGA palette,
	# which is recommended if the images are already using that colour set,
	# but otherwise the image should have a maximum of 256 colours,
	# though this works much better and faster on images with fewer colours,
	# and it is best if the image already has its own palette.
	# The BG parameter is important for choosing the starting colour of the screen,
	# but if the image does not have its own palette the choice may not be predictable.
	#
	# This can be used on the command line, use -h or --help for details.
	#
	# It may take a few minutes for each image. You can turn on PRINT_STEPS if you'd
	# like a crude progress indicator.
	#
	# The process tries to progressively simplify the image, eliminating the smallest detail
	# one at a time until it reduces to simpler and larger shapes. Once the entire image has
	# been eliminated, it reassembles it in reverse to create the animation.
	#
	# Brad Smith, 2024
	# https://rainwarrior.ca

	# Requires Pillow library:
	# https://pillow.readthedocs.io/en/stable/installation/basic-installation.html

	import PIL.Image
	import os.path
	import random
	import argparse

	#
	# Parameters
	# These can all be set from the command line. Use -h or --help to print usage info.
	#

	INFILE = None # process a single image instead of a directory
	INDIR = "."
	BG = 0 # background colour (index to palette)
	FORCE_EGA = False # use 16-colour EGA palette instead of the PNG's palette

	# image decomposition parameters
	FILL_MIN = 50 # minimum pixels for a fill step
	SURROUND_RATIO = 2.5 # only use border fill-in when the region will increase in size significantly, otherwise fill-in with background colour
	DITHER_MIN = 10 # minimum pixels for dither step (includes both colours)
	STROKE_TIES = 40 # strokes within this number of pixels should tiebreak with positional coherency first

	# reconstruction animation
	STROKE_SAMPLES = 10 # random sampling for drawing in (lower = more dithered, higher = more ordered)
	FRAME_MIN = 300 # minimum pixels per frame (add steps until this is met)
	FRAME_MAX = 500 # maximum pixels per frame (break up any single step longer than this)
	FRAME_TIME = 20 # ms per frame
	FRAME_LAST = 3000 # ms on final frame

	# skip saving STEPDIR or OUTDIR preview images
	PRINT_STEPS = False
	PREVIEW_STEP = False
	PREVIEW_OUT = False
	STEPDIR = "step"
	OUTDIR = "out"

	#
	# parse command line
	#

	if __name__ == "__main__":
	ap = argparse.ArgumentParser()
	ag = ap.add_argument_group("Input")
	ag.add_argument("-INFILE",help="Single input file",metavar="file")
	ag.add_argument("-INDIR",help="Input directory, all PNG files used",metavar="dir")
	ag.add_argument("-BG",type=int,help="Background colour index, default %d" % BG,metavar="c")
	ag.add_argument("-FORCE_EGA",action="store_const",const=True,help="Force the image to use the standard 16-colour EGA palette")
	ag = ap.add_argument_group("Decomposition")
	ag.add_argument("-FILL_MIN",type=int,help="Minimum pixels to generate a fill step, default %d" % FILL_MIN,metavar="n")
	ag.add_argument("-SURROUND_RATIO",type=float,help="Ratio required for surrounding colour to replace the removed step, instead of the background colour, default %s" % str(SURROUND_RATIO),metavar="r")
	ag.add_argument("-DITHER_MIN",type=int,help="Minimum pixels to generate a dither step (includes both colours), default %d" % DITHER_MIN,metavar="n")
	ag.add_argument("-STROKE_TIES",type=int,help="Strokes within this number of pixels should break ties by favouring closer strokes first, default %d" % STROKE_TIES,metavar="n")
	ag = ap.add_argument_group("Animation")
	ag.add_argument("-STROKE_SAMPLES",type=int,help="Random sampling for drawing in (lower = more dithered, higher = more ordered), default %d" % STROKE_SAMPLES,metavar="n")
	ag.add_argument("-FRAME_MIN",type=int,help="Minimum pixels per frame (adds steps until this is met), default %d" % FRAME_MIN,metavar="n")
	ag.add_argument("-FRAME_MAX",type=int,help="Maximum pixels per frame (breaks up any single step longer than this), default %d" % FRAME_MAX,metavar="n")
	ag.add_argument("-FRAME_TIME",type=int,help="Milliseconds per frame (GIF standard minimum is 20), default %d" % FRAME_TIME,metavar="n")
	ag.add_argument("-FRAME_LAST",type=int,help="Milliseconds on final frame, default %d" % FRAME_LAST,metavar="n")
	ag = ap.add_argument_group("Breakdown")
	ag.add_argument("-PRINT_STEPS",action="store_const",const=True,help="Print details of each step to console")
	ag.add_argument("-PREVIEW_STEP",action="store_const",const=True,help="Save a PNG to STEPDIR for each decomposed step")
	ag.add_argument("-PREVIEW_OUT",action="store_const",const=True,help="Save a PNG to OUTDIR for each animated output step")
	ag.add_argument("-STEPDIR",help="Directory output for PREVIEW_STEP, default %s" % STEPDIR,metavar="dir")
	ag.add_argument("-OUTDIR",help="Directory output for PREVIEW_OUT, default %s" % OUTDIR,metavar="dir")
	args = ap.parse_args()
	for (k,v) in args.__dict__.items():
	if v != None:
	#print("ARG: "+k+": "+str(v))
	globals()[k] = v

	#
	# Global data
	#

	src = None
	img = None

	# create preview directories if needed
	if PREVIEW_STEP and not os.path.exists(STEPDIR):
	os.makedirs(STEPDIR)
	if PREVIEW_OUT and not os.path.exists(OUTDIR):
	os.makedirs(OUTDIR)

	#
	# EGA palette
	#

	PALETTE = [
	(0x00,0x00,0x00),
	(0x00,0x00,0xAA),
	(0x00,0xAA,0x00),
	(0x00,0xAA,0xAA),
	(0xAA,0x00,0x00),
	(0xAA,0x00,0xAA),
	(0xAA,0x55,0x00),
	(0x55,0x55,0x55), # swapped greys so that < is darker (usually)
	(0xAA,0xAA,0xAA),
	(0x55,0x55,0xFF),
	(0x55,0xFF,0xFF),
	(0x55,0xFF,0x55),
	(0xFF,0x55,0x55),
	(0xFF,0x55,0xFF),
	(0xFF,0xFF,0x55),
	(0xFF,0xFF,0xFF)]

	# closest-match remap of img to RGB palette
	def img_remap(img, palette):
	ims = img.convert("RGB")
	imp = PIL.Image.new("P",ims.size,color=0)
	for y in range(ims.size[1]):
	for x in range(ims.size[0]):
	p = ims.getpixel((x,y))
	mag = ((255*2)3)+1
	mat = 0
	for i in range(len(palette)):
	m = sum([(a-b)**2 for (a,b) in zip(p,palette[i])])
	if m < mag: # better match
	mat = i
	mag = m
	if m == 0: break # perfect match
	imp.putpixel((x,y),mat)
	imp.putpalette([p for tup in palette for p in tup[0:3]])
	return imp

	#
	# decompose into steps
	#

	# each draw step is a set of pixel coordinates (area),
	# optionally a set of edge pixel coordinates (edge),
	# the colour of the area+edge pixels (cs),
	# the colour they should be drawn on top of (cr),
	# and a draw type:
	DITHER = 0 # checkerboard dithering (no edge)
	FILL = 1 # 4-way connected region: draw edge first, then area
	STROKE = 2 # region connected up to 2 pixels away (no edge)
	TNAMES = ["dither","fill","stroke"]

	# adding a step "undoes" that step from the image by replacing it an underlying colour
	steps = []
	def add_step(area,edge,cs,cr,t):
	global steps
	global img
	assert(cr != cs)
	index = len(steps)
	steps.append((area,edge,cs,cr,t))
	for (x,y) in area:
	img.putpixel((x,y),cr)
	for (x,y) in edge:
	img.putpixel((x,y),cr)
	if PREVIEW_STEP:
	img.save(os.path.join(STEPDIR,"%05d.png" % index))
	if PRINT_STEPS:
	print("%05d: %s (%d pixels) %d -> %d" % (index,TNAMES[t],len(area)+len(edge),cr,cs))

	# dither step identification:
	# - scan for 3x3 areas with dither colour pairs
	# - flood-fill each identified area to find its full extent
	# - use the candidate with the most pixels first
	# - repeat
	def add_dithers():
	(w,h) = img.size
	while True:
	best = None
	visited = set()
	for y in range(0,h-2):
	for x in range(0,w-2):
	if (x,y) in visited: continue
	# find pair of colours
	c = (img.getpixel((x+0,y+0)),
	img.getpixel((x+1,y+0)))
	if c[0] == c[1]: continue
	if ((x ^ y) & 1) != 0: # swap if on an odd pixel
	c = (c[1],c[0])
	begin = True
	for ty in range(0,3):
	for tx in range(0,3):
	cd = c[(tx ^ ty) & 1]
	if cd != img.getpixel((x+tx,y+ty)):
	begin = False
	break
	if not begin: break
	if not begin: continue
	# found a 3x3 area, flood fill search
	area = set()
	queue = [(x,y)]
	while len(queue) > 0:
	(dx,dy) = queue.pop(0)
	if (dx,dy) in visited: continue
	if dx < 0 or dy < 0 or dx >= w or dy >= h: continue
	cd = c[(dx ^ dy) & 1]
	if cd != img.getpixel((dx,dy)): continue
	visited.add((dx,dy))
	area.add((dx,dy))
	queue.append((dx+1,dy))
	queue.append((dx-1,dy))
	queue.append((dx,dy+1))
	queue.append((dx,dy-1))
	candidate = (area, c)
	if best == None or len(area) > len(best[0]):
	best = candidate
	if best == None: break
	(area,c) = best
	if len(area) < DITHER_MIN: break
	dither_area = set()
	keep = 0
	t = DITHER
	if c[1] > c[0]: keep = 1 # dither a lighter colour on top of a darker region
	if (c[keep^1] == BG): keep ^= 1 # exception: don't dither on top of BG
	for (x,y) in area:
	if ((x^y) & 1) == keep:
	dither_area.add((x,y))
	add_step(dither_area,{},c[keep],c[keep^1],t)

	# flood-fill and stroke step identification
	# - scan for contiguous areas
	# - flood-fill is 4-way connected
	# - stroke is connected up to 2 pixels away
	# - remove the smallest group and replace with its surrounding colour if appropriate
	# - smallest-first allows small details to be filled-in by surrounding colour
	# - repeat
	def add_floodstrokes():
	(w,h) = img.size
	while True:
	best = None
	best_pixels = 0
	visitedf = set()
	visiteds = set()
	for y in range(0,h):
	for x in range(0,w):
	c = img.getpixel((x,y))
	if c == BG:
	visitedf.add((x,y))
	visiteds.add((x,y))
	continue
	# flood candidate at this pixel
	area = set()
	edges = set()
	if (x,y) not in visitedf:
	queue = [(x,y)]
	while len(queue) > 0:
	(dx,dy) = queue.pop(0)
	if (dx,dy) in visitedf: continue
	if dx < 0 or dy < 0 or dx >= w or dy >= h: continue
	if c != img.getpixel((dx,dy)): continue
	visitedf.add((dx,dy))
	queue.append((dx+1,dy))
	queue.append((dx-1,dy))
	queue.append((dx,dy+1))
	queue.append((dx,dy-1))
	# separate edges
	if (dx > 0 and c != img.getpixel((dx-1,dy))) or \
	(dy > 0 and c != img.getpixel((dx,dy-1))) or \
	((dx+1) < w and c != img.getpixel((dx+1,dy))) or \
	((dy+1) < h and c != img.getpixel((dx,dy+1))):
	edges.add((dx,dy))
	continue
	# keep interior
	area.add((dx,dy))
	# stroke candidate at this pixel
	strokearea = set()
	strokeedges = set()
	if (x,y) not in visiteds:
	queue = [(x,y)]
	while len(queue) > 0:
	(dx,dy) = queue.pop(0)
	if (dx,dy) in visiteds: continue
	if dx < 0 or dy < 0 or dx >= w or dy >= h: continue
	if c != img.getpixel((dx,dy)): continue
	visiteds.add((dx,dy))
	queue.append((dx+1,dy))
	queue.append((dx-1,dy))
	queue.append((dx,dy+1))
	queue.append((dx,dy-1))
	queue.append((dx+2,dy)) # 2 pixels away
	queue.append((dx-2,dy))
	queue.append((dx,dy+2))
	queue.append((dx,dy-2))
	queue.append((dx+1,dy+1)) # corners
	queue.append((dx-1,dy+1))
	queue.append((dx+1,dy-1))
	queue.append((dx-1,dy-1))
	if (dx > 0 and c != img.getpixel((dx-1,dy))) or \
	(dy > 0 and c != img.getpixel((dx,dy-1))) or \
	((dx+1) < w and c != img.getpixel((dx+1,dy))) or \
	((dy+1) < h and c != img.getpixel((dx,dy+1))):
	strokeedges.add((dx,dy))
	continue
	strokearea.add((dx,dy))
	# best of either stroke or flood
	pixels = len(area) + len(edges)
	strokepixels = len(strokearea) + len(strokeedges)
	candidate = (area, edges, c, FILL)
	if (pixels < 1) or (len(area) < FILL_MIN) or (strokepixels > 0 and strokepixels < pixels):
	pixels = strokepixels
	candidate = (strokearea, strokeedges, c, STROKE)
	if best == None or (pixels > 0 and pixels < best_pixels):
	best = [candidate]
	best_pixels = pixels
	elif pixels == best_pixels:
	best.append(candidate)
	if best == None: break
	invalid_c = set()
	best_type = best[0][3]
	for (area,edges,c,t) in best:
	if c in invalid_c: continue # any groups using a previous replacement colour are now invalid
	if t != best_type: continue # can't mix flood and stroke in a single pass
	cr = BG
	# use surrounding colour as replacement
	surround = []
	for (dx,dy) in edges:
	def add_surround(x,y):
	if x < 0 or x >= img.width or y < 0 or y >= img.height: return
	r = img.getpixel((x,y))
	if r == c: return
	while r >= len(surround):
	surround.append(0)
	surround[r] += 1
	add_surround(dx-1,dy)
	add_surround(dx+1,dy)
	add_surround(dx,dy-1)
	add_surround(dx,dy+1)
	best_cr = 0
	for i in range(len(surround)):
	if surround[i] > best_cr:
	best_cr = surround[i]
	cr = i
	# count pixels in replacement region, if not above ratio just use background to replace instead
	imt = img.copy()
	coord = None
	for a in area: imt.putpixel(a,cr)
	for e in edges: imt.putpixel(e,cr)
	visited = set()
	queue = list(area) + list(edges)
	count = 0
	while len(queue) > 0:
	(dx,dy) = queue.pop(0)
	if (dx,dy) in visited: continue
	visited.add((dx,dy))
	if dx < 0 or dy < 0 or dx >= w or dy >= h: continue
	if cr != imt.getpixel((dx,dy)): continue
	count += 1
	queue.append((dx-1,dy))
	queue.append((dx+1,dy))
	queue.append((dx,dy-1))
	queue.append((dx,dy+1))
	if (count / best_pixels) < SURROUND_RATIO:
	cr = BG # fall to background instead
	# add as fill if over a certain size, otherwise stroke
	if t == FILL and len(area) >= FILL_MIN:
	add_step(area,edges,c,cr,FILL)
	else:
	add_step(area.union(edges),{},c,cr,STROKE)
	invalid_c.add(cr) # any other strokes/fills using c/cr are now invalid

	#
	# rebuild the image with animation
	#

	last_px = 0
	last_py = 0
	last_c = BG
	frame_pixels = 0
	frames = []

	def do_frame():
	global frame_pixels
	global frames
	index = len(frames)
	if PRINT_STEPS: print("%05d: %d pixels (%d steps remain)" % (index,frame_pixels,len(steps)))
	if PREVIEW_OUT:
	img.save(os.path.join(OUTDIR,"%05d.png" % (index)))
	frames.append(img.copy())
	frame_pixels = 0

	def do_pixel(x,y,c):
	global frame_pixels
	global last_px
	global last_py
	global last_c
	global img
	last_px = x
	last_py = y
	last_c = c
	frame_pixels += 1
	img.putpixel((x,y),c)
	if (frame_pixels >= FRAME_MAX):
	do_frame()

	def do_area(area,cs):
	for (x,y) in area:
	do_pixel(x,y,cs)

	def do_horizontal(area,cs,minx,maxx,mx,fallback=False):
	global src
	d = 1
	if ((maxx - mx) < (mx - minx)): # right to left (trying to start with densest area)
	d = -1
	while len(area) > 0:
	if (len(area) < STROKE_SAMPLES):
	do_area(area,cs)
	return
	s = random.sample(list(area),STROKE_SAMPLES)
	(x,y) = s[0]
	for ss in s[1:]:
	if (ss[0] * d) < (x * d):
	(x,y) = ss
	if fallback: cs = src.getpixel((x,y)) # if in fallback use reveal the original image instead
	do_pixel(x,y,cs)
	area.remove((x,y))

	def do_vertical(area,cs,miny,maxy,my,fallback=False):
	global src
	d = 1
	if ((maxy - my) < (my - miny)): # bottom to top
	d = -1
	while len(area) > 0:
	if (len(area) < STROKE_SAMPLES):
	do_area(area,cs)
	return
	s = random.sample(list(area),STROKE_SAMPLES)
	(x,y) = s[0]
	for ss in s[1:]:
	if (ss[1] * d) < (y * d):
	(x,y) = ss
	if fallback: cs = src.getpixel((x,y))
	do_pixel(x,y,cs)
	area.remove((x,y))

	def do_step(s,fallback=False):
	(area,edges,cs,cr,t) = s
	if (len(edges)>0):
	if not fallback: # do edges of fill as separate stroke first
	do_step((edges,{},cs,cr,STROKE),False)
	else: # don't do outline with fallback
	area = area.union(edges)
	if PRINT_STEPS: print("Step: %s %d pixels (%d -> %d)" % \
	(TNAMES[t] + (" (fallback)" if fallback else ""),len(area),cr,cs))
	# count horizontal edges, vertical edges, and compute average, min, max
	minx = img.width - 1
	miny = img.height - 1
	maxx = 0
	maxy = 0
	mx = 0
	my = 0
	ex = 0
	ey = 0
	for (x,y) in area:
	mx += x
	my += y
	if (x+1,y) not in edges: ex += 1
	if (x,y+1) not in edges: ey += 1
	minx = min(x,minx)
	miny = min(y,miny)
	maxx = max(x,maxx)
	maxy = max(y,maxy)
	mx = int(mx/len(area))
	my = int(my/len(area))
	# more horizontal edges = draw left to right, more vertical = top to bottom
	if (ey > ex): do_vertical( area,cs,miny,maxy,my,fallback)
	else: do_horizontal(area,cs,minx,maxx,mx,fallback)

	def ready_step(s):
	(area,edges,cs,cr,t) = s
	for a in area:
	if img.getpixel(a) != cr:
	return False
	for a in edges:
	if img.getpixel(a) != cr:
	return False
	return True

	def animate(outgif):
	global img
	global frames
	global last_px
	global last_py
	global last_c
	global frame_pixels
	img = src.copy()
	frames = []
	last_px = src.width / 2
	last_py = src.height / 2
	last_c = BG
	frame_pixels = 0
	# first frame is BG colour
	for y in range(img.height):
	for x in range(img.width):
	img.putpixel((x,y),BG)
	do_frame()
	# prioritize:
	# - largest dither not on BG where all pixels are ready
	# - largest unit of any kind that has all its pixels ready
	# but break tie by:
	# - stroke with same colour as last
	# - stroke with point closest to last written pixel
	while len(steps) > 0:
	best = -1
	best_pixels = -1
	fallback = False
	# largest dither not on BG where all pixels are ready
	for i in range(len(steps)):
	if not ready_step(steps[i]): continue
	(area,edges,cs,cr,t) = steps[i]
	if t != DITHER: continue
	pixels = len(area) + len(edges)
	if (best < 0) or (pixels >= best_pixels):
	best = i
	best_pixels = pixels
	# largest ready flood fill or stroke
	if (best < 0):
	best_dist = -1
	best_color = BG
	for i in range(len(steps)):
	if not ready_step(steps[i]): continue
	(area,edges,cs,cr,t) = steps[i]
	pixels = len(area) + len(edges)
	if ((best < 0) or (pixels >= (best_pixels - STROKE_TIES))):
	dist = -1
	# compute closest distance to last pixel
	for (x,y) in area:
	d = abs(x-last_px) + abs(y-last_py)
	if dist < 0 or d < dist:
	dist = d
	for (x,y) in edges:
	d = abs(x-last_px) + abs(y-last_py)
	if dist < 0 or d < dist:
	dist = d
	# break tie by: same colour as last pixel, then closest to last pixel
	if pixels > best_pixels or \
	(cs == last_c and best_color != last_c) or \
	(best_dist < 0) or (dist < best_dist):
	best = i
	best_dist = dist
	best_color = cs
	best_pixels = max(pixels,best_pixels)
	# fallback to smallest group if nothing is ready
	if (best < 0):
	fallback = True
	for i in range(len(steps)):
	(area,edges,cs,cr,t) = steps[i]
	pixels = len(area) + len(edges)
	if (best < 0) or (pixels < best_pixels):
	best_pixels = pixels
	best = i
	# apply best step
	do_step(steps[best],fallback)
	if frame_pixels >= FRAME_MIN:
	do_frame()
	del steps[best]
	# finish
	if (frame_pixels > 0): do_frame()
	img = src.copy()
	do_frame()
	print("Finished animation.")
	frames[0].save(outgif,save_all=True,append_images=frames[1:],loop=0,duration=([FRAME_TIME]*(len(frames)-1))+[FRAME_LAST])
	print(outgif)

	#
	# create the animation from an image
	#

	def serrator(infile, outgif):
	global src
	global img
	src = PIL.Image.open(infile)
	print("Open: %s (%dx%d) %s" % (infile,src.width,src.height,src.mode))
	if FORCE_EGA:
	src = img_remap(src,PALETTE)
	elif src.mode != 'P':
	src = src.convert('P', dither=None, palette=PIL.Image.ADAPTIVE)
	img = src.copy()
	# decompose image
	global steps
	steps = []
	add_dithers()
	add_floodstrokes()
	# make animation
	animate(outgif)

	worklist = []
	if INFILE:
	worklist = [INFILE]
	else:
	for f in os.listdir(INDIR):
	if (f.lower().endswith(".png")):
	worklist.append(os.path.join(INDIR,f))

	for w in worklist:
	serrator(w,w+".gif")