Hungarian algorithm for matching without repeats

Matching tile candidates to tiles is an assignment problem, where the "cost" is the distance between colors. The Hungarian algorithm solves the linear assignment problem in O(N^3). For our application, N is the number of images in the tile candidate pool.

There is a pure Python solution (Apache-licensed) on PyPI called munkres. It solves a 100x100 matrix in about two seconds on my laptop. For good tile pools, N~1000, and it is quite slow. (And incidentally, the munkres implementation seems to scale significantly worse than N^3.) It might be interesting to try speeding it up with numba.

Another thought: to relax "no repeats" to "up to M repeats," represent each tile candidate in the assignment matrix M times, with its cost inflated on each repetition. This would make the matrix M times bigger than the assignment correspondingly slower, so it may not be practical.

This snippet integrates monkres with photomosaic. It's so slow for reasonably-sized mosaics that I don't think it's worth submitting as a PR in this form.

from collections import OrderedDict
import munkres
import numpy as np
from skimage.data import chelsea
from skimage import img_to_float

# boilerplate setup
pool = pm.make_pool('SOME_DIRECTORY_WITH_25_IMAGES_IN_IT/*.png')
img = img_to_float(chelsea())
converted_img = pm.perceptual(img)
adapted_img = pm.adapt_to_pool(converted_img, pool)
# using a *very* course tile grid here so it runs in reasonable time
scaled_img = pm.rescale_commensurate(adapted_img, grid_dims=(5, 5))
tiles = pm.partition(scaled_img, grid_dims=(5, 5))
tile_colors = [np.mean(adapted_img[tile].reshape(-1, 3), 0) for tile in tiles]

def hungarian_match(pool, tile_colors):
    pool = OrderedDict(pool)  # lock iteration order
    pool_colors = np.asarray(list(pool.values()))
    margin = len(pool_colors) - len(tile_colors)
    if margin < 0:
        raise NotImplementedError("This matcher uses each pool image only "
                                  "once, so it requires that the number of "
                                  "tiles be less than or equal to the number "
                                  "of images in the pool.")
    bigdiff = np.subtract.outer(pool_colors, np.asarray(tile_colors))
    # subtract.outer is fast but actually does more work than we need. It
    # subtracts every channel against every other channel. Take a diagonal
    # slice through it to get channels subtracted from corresponding channels.
    num_channels = pool_colors.shape[-1]
    diff = np.stack([bigdiff[:, i, :, i] for i in range(num_channels)])

    distance = np.sqrt(np.sum(diff**2, 0))
    # A row per pool color, a column per tile color; each entry their distance.

    # Zero-pad the matrix to make it square.
    print('disatnce.shape', distance.shape)
    square_matrix = np.pad(distance, [(0, 0), (0, margin)], mode='constant')
    print('square_matrix.shape', square_matrix.shape)

    # Assign tiles to pool images uses Hungarian algorithm.
    indexes = munkres.Munkres().compute(square_matrix)

    # Sort result by column (tile).
    sorted_indexes = sorted(indexes, key=lambda key: key[1])
    pool_keys = list(pool.keys())
    matches = [pool_keys[row] for row, columns in sorted_indexes]
    return matches

matches = hungarian_match(pool, tile_colors)

# boilerplate mosaic-drawing
canvas = np.zeros_like(scaled_img)  # black canvas
mos = pm.draw_mosaic(canvas, tiles, matches)

danielballan / photomosaic

Hungarian algorithm for matching without repeats #16