Image warping with heat map that "pulls" on pixels

Question

I am looking for an efficient image warping function $$f: (\text{image}\in \mathbb R ^{M\times N\times3}, \text{heatMap} \in \mathbb R ^{M\times N}) \to \text{warpedImage} \in \mathbb R ^{M\times N\times3}$$ that would "inflate" certain pixels in a base image, with the amount of inflation represented in a heat map that accompanies the image.

One way to think of this (maybe not the best) is that the heat map represents the amount of "mass" at each original pixel location. The mass "pulls" on the resampling (x', y') locations, and this pull is counteracted by the tendency of the samples to want to remain at their original (x, y) locations, and the resampling locations settle at the equilibrium point.

The image below gives a rough idea of what I'm looking for. I generated it using a really rough and very slow method, for generating resampling points which I feed into cv2.remap. Example code is in this gist.

My questions

• Is this a known transformation with a name?
• Is there an efficient (even if approximate) way to compute the resampling points?

Answer 1

Ok, I found what seems to be a decently principled and fast (roughly O(height*width)) solution - result here. I assume it has some pre-existing name in the literature, but until I find that name I'll call it the Weighted Warp Transform:

The idea is to start with a "coorinate image" $c \in \mathbb R^{H, W, 2}$ where $c_{ij} = (i, j)$, and then do a weighted filtering operation on this image, where the weights are given by the heatmap, to compute a "warped" pixel grid $c'$, such that:

$$ c'_{ij} = \frac {\displaystyle\sum_{i'=-K/2}^{K/2}\sum_{j'=-K/2}^{K/2}c_{i-i',j-j'}h_{i-i',j-j'}\kappa_{i',j'}} {\displaystyle\sum_{i'=-K/2}^{K/2}\sum_{j'=-K/2}^{K/2} h_{i-i',j-j'}\kappa_{i',j'}} $$

Where

• $h$ is the heatmap (you need to do some preprocessing on this to ensure numerical stability and no 'divide by zero's)
• $\kappa$ is a filter kernel of size K

Then you resample your original image at the coordinates c', using bilinear interpolation or simply nearest neighbour.

The above would have a runtime of O(HWKK) where K is the filter size, which is not terribly efficient for large filters, BUT.

• If you use a separable filter, this falls to O(HWK).
• If you use a box filter based on integral-image, it falls to O((H+K)(W+K))
• If you use an iterated box-filter, you get a more gaussian-like kernel with O((H+K*N)(W+K*N)) where N is the number of iterations.

A tensorflow implementation using an iterated box filter is in this gist, and was used to produce the above image.

Answer 2

You need to split the problem into two:

• Compute the motion (the velocity vectors, aka flow)
• Resample the image

I assume that computing the motion is expensive, and you want to do it on less pixels than the total image, while still obtaining a pixel-accurate result. If computing the motion is not expensive, you can do it at every pixel and just warp with it.

To reduce the cost of computing the motion, you can do it on an uniformly subsampled grid, or you may use some form of hierarchical decomposition (e.g. using a quadtree), such that you sample more finely where the motion changes more rapidly, until the motion sampling error falls below 1 pixel.

Once you have the motion on a subset of the pixels, you can use an interpolating spline to apply it to the entire image. For example, you could use a thin-plate spline