Finding a map between two matrices that minimises distance differences of neighbors

Question

Given two binary matrices of the same size with the same element counts, how can we find a map mapping ones to ones such that the sum of differences of distances of all pairs of neighbors is minimised, where the distance of each cell is the number of steps it needs to walk horizontally, vertically or diagonally to reach where the mapping sent it?

For example, given $A= \begin{bmatrix} 1& 1 & 1\\ 1& 0& 0\\ 0& 0& 0 \end{bmatrix} B= \begin{bmatrix} 0& 0 & 0\\ 0& 0& 1\\ 1& 1& 1 \end{bmatrix} $

The function $\psi$ mapping the ones of $A$ to the ones of $B$ by $\psi(1,1) = (3,1), \psi(1,2) = (3,2),\psi(1,3) = (3,3), \psi(2,1) = (2,3)$ gives all the ones of $A$ the same distance of 2, which gives the sum of all differences of distances of neighbors the minimal value possible of zero.

How can we generally approach this problem efficiently?

The motivation is creating smooth animation between simple binary black and white images of shapes such as circle and square. Combining this approach with also minimising the total distance covered by the pixels will help finding the path each pixel makes along the frames to make the animation smooth. It is for practical usage having typical input size of about $500 \times 500$ with relatively small amount of black pixels (ones) of about 500.

Answer 1

I expect that solving the problem exactly might be NP-hard. However, here is an approach that I expect will probably be good enough for practical purposes.

It uses a subroutine to solve the following problem: given an integer range $[\ell,u]$, find a mapping $\psi$ such that $\ell \le \text{dist}(p,\psi(p)) \le u$ for all one-pixels $p$, or report that no such mapping exists. You can implement such a subroutine using an algorithm for bipartite matching: build a bipartite graph with one left-vertex for each one-pixel in the left matrix, one right-vertex for each one-pixel in the right matrix, and an edge between two vertices if the distance between their corresponding pixels falls in $[\ell,u]$.

Given such a subroutine, you can search over all $O(n^2)$ possible ranges, and call the subroutine for each, and keep the "narrowest" range, i.e., one where $u-\ell$ is minimal. Generally, the smaller the value of $u-\ell$, the better it is likely to be by your metric. (Here I assume each matrix is $n\times n$.)

Or, more efficiently, you can search over all $2n$ possibilities for $\mu$, where $1 \le \mu \le n$ and $\mu$ is an integer or half an integer; then for each $\mu$, use binary search over $s$ to find the smallest $s$ such that there is a mapping for the interval $[\mu-s,\mu+s]$. Note that there are only $O(n)$ possibilities for $s$, so this requires only $O(n \log n)$ invocations of the subroutine.

Each invocation of the subroutine can be implemented in $O(n^3)$ time using the Hopcroft-Karp algorithm, for a total running time of $O(n^4 \log n)$.