Hungarian algorithm for matching without repeats

[danielballan]

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]

Scipy added an implementation of this recently: https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html