Given two sets of (two-dimensional) points, say, $A=\{a_1,a_2,\ldots,a_{n_a}\}$ and (you guessed it) $B=\{b_1,b_2,\ldots,b_{n_b}\}$, and $d^2_{i,j}=\mid a_i-b_j\mid^{\ 2}$ the "matrix" (not necessarily square) of distances between them, I want to map $m:A\to B$ (i.e., with each $A$-point $a\in A$ associate a corresponding $B$-point $m(a)\in B$) such that the following...
The maximal point-to-point $d_{i,m(i)}$ distance should be minimal. And once you've accomplished that first $m:i\to m(i)$ correspondence, each set gets one point smaller, $A\to A\backslash\{a_i\}$ and $B\to B\backslash\{b_{m(i)}\}$. And now, the second point-to-point correspondence made by $m$ should similarly minimize the maximal distance on these one-point-smaller sets. And then iteratively. So, my question: what's an efficient algorithm for this? ($n_a,n_b\sim10^4$, way too large for brute force)
And it's not necessary that $n_a=n_b$. If $n_a\lt n_b$, discard any of the excess $n_b-n_a$ $B$-points you like such that the set of all those maximal distances is minimized. That is, just do the iteration, and when you're done, just discard the "unused" $B$-points. On the other hand, if $n_b\lt n_a$ just discard the $A$-points resulting from the first $n_a-n_b$ iteration steps (i.e., again minimize the set of maximal distances). At least, I think that's the right "discard" scheme, but please correct me if I'm wrong.
The "point" (sorry:) of all this is, as per the subject, to "morph" one bitmapped image into another, whereby each $A$-point denotes a source image pixel, and each $B$-point denotes a target image pixel (and if $n_b\gt n_a$, I'll just inconspicuously/randomly "pop" a few extra $B$-pixels into place during each frame of the morph). Since this kind of morphing is all over the place, I'd have thought I could easily google algorithms/code/etc. But I strangely couldn't get google to cough it up. So if you're familiar with this kind of stuff and can just point me in the right direction, that would be great, too. Thanks.
E d i t
-----------------
Thanks again, @LedHead and @BrunoLevy. It's been quite some time (better late
than never), but I finally got around to implementing this stuff, more or less
as originally intended. Here's an illustration, followed by some
explanatory remarks...
The interpolation's nearest neighbor as suggested by you, one-to-many if the source image has fewer pixels than the target (and vice-versa if vice-versa). But the path from source-->target pixel isn't a straight line. Instead, it's a bezier curve whose first control point is the source row,col and whose last control point is the target's. In-between control points determine the shape of the path. They're basically chosen randomly, but constrained within the row,col-bounds of the image. However, when specifying the gif, you can choose multipliers for those constraints. For the illustrated gif, I chose constraints keeping all control points near the center. And that's why, in this case, the morphing first contracts all the pixels inwards, and then expands them outwards.
By the way, bezier also includes straight-line interpolation between
nearest neighbors, simply by choosing just two control points, which
are then necessarily source coordinates and target coordinates. The exact
same gif, changed only in that way, looks like...
