Approximate an image with a fixed number of tiles

tiler.py

import numpy as np

# By stkptr 2025
# Unlicense/CC0
# Public domain

# scoring function
def difference(a, b):
    return np.abs(a - b).sum()

# this breaks the image into the tiles
# it only works on square images, I don't want to fix it
def chunk(a, dims):
    img = []
    for y in range(0, a.shape[1], dims[1]):
        img.append([])
        for x in range(0, a.shape[0], dims[0]):
            img[-1].append(a[y:y+dims[1],x:x+dims[0]])
    return img

# takes in a chunked image and returns a flat list consisting of the tiles
# each followed by a list of where they occur
def label(tiles):
    o = []
    for iy, y in enumerate(tiles):
        for ix, x in enumerate(y):
            o.append((x, [(ix, iy)]))
    return o

# this picks some middle point between two tiles
# this can be a lot of different potential functions
# in this case it randomly picks pixels between the two tiles
def combine(a, b):
    picker = np.random.default_rng().integers(0, 2, a.shape)
    return np.choose(picker, [a, b])


# these are the constant tiles
fixed = [
    np.array([
        [1, 1, 1, 1],
        [1, 1, 1, 1],
        [1, 1, 1, 1],
        [1, 1, 1, 1],
    ]),
    np.array([
        [0, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0],
    ]),
    np.array([
        [1, 0, 0, 0],
        [0, 1, 0, 0],
        [0, 0, 1, 0],
        [0, 0, 0, 1],
    ]),
    np.array([
        [0, 0, 0, 1],
        [0, 0, 1, 0],
        [0, 1, 0, 0],
        [1, 0, 0, 0],
    ]),
]

dims = fixed[0].shape

def optimize(i, fixed=fixed, dims=dims, threshold=4, max=16):
    tiles = label(chunk(i, dims))
    palette = [(f, []) for f in fixed]
    available = max - len(palette)
    remove = []
    # remove any tiles which are close enough to the constant ones
    for it, t in enumerate(tiles):
        errors = [difference(t[0], p[0]) for p in palette]
        if min(errors) < threshold:
            pidx = np.argmin(errors)
            palette[pidx][1].append(t[1][0])
            remove.append(it)
    for i in reversed(remove):
        tiles.pop(i)
    # compute the difference table
    score_table = np.array([
        [difference(t[0], o[0]) for o in tiles] for t in tiles
    ])
    # make the self similarity scores impossibly high
    err_max = dims[0] * dims[1] + 1
    score_table += np.eye(*score_table.shape, dtype=int) * err_max
    while len(tiles) > available:
        # find the tiles with the smallest relative error
        best = np.argmin(score_table)
        best_coord = np.unravel_index(best, score_table.shape)
        from_t = best_coord[0]
        to_t = best_coord[1]
        # then merge the two tiles into one
        middle = combine(tiles[from_t][0], tiles[to_t][0])
        # actually reflect this merger in the tile list
        tiles[from_t] = (middle, tiles[from_t][1] + tiles[to_t][1])
        # remove one of them
        tiles.pop(to_t)
        # including from the score table
        score_table = np.delete(score_table, to_t, 0)
        score_table = np.delete(score_table, to_t, 1)
        # recalculate the error
        error = [difference(middle, o[0]) for o in tiles]
        # ensure the self error is impossibly high
        error[from_t] = err_max
        # then reassign the differences to the score table
        score_table[from_t, ...] = error
        score_table[..., from_t] = error
    return palette + tiles

# for display purposes
def ascii(a, on='#', off=' '):
    s = ''
    for y in a:
        for x in y:
            s += on if x else off
        s += '\n'
    return s


# random bit image
i = np.random.default_rng().integers(0, 2, (dims[0] * 4, dims[1] * 4))

print(ascii(i))

palette = optimize(i, max=8)

# reconstruct from palette
# this creates a grid for the tile indices
block = [[None for x in range(i.shape[1] // 4)] for y in range(i.shape[0] // 4)]

# then this puts the correct tile in each spot
for p in palette:
    for c in p[1]:
        block[c[1]][c[0]] = p[0]

# and this merges it into a final image
remade = np.block(block)

print('After tiling')

print(ascii(remade))