Calculate minimal distance between two "pixel blobs" in canvas

Question

I want to calculate the distance between two sets of pixels – for illustration purposes, a blue set and a red set of pixels. I want to calculate the closest distance in x direction, y direction and arbitrary direction (see the three arrows in the image). In general, the pixels of one color might be unconnected patches (like red in the example), but most of the time they will be connected, though they can have holes (like blue in the example).

Are there any libraries or algorithms out there that already solve this in a sensible way? It's not particularly hard to come up with a solution – x and y distance are an O(n) problem, but for arbitrary distance, the naive brute-force algorithm is O(n²). I have a hunch that there are better approaches.

score 3 · Accepted Answer · 2020-03-24T19:46:58.420

3

You can compute a full distance map around a blob of arbitrary shape (including disconnected) in linear time O(n), be it Manhattan or Euclidean (where n denotes the image size).

When you have this map, scanning the other blob(s) to find the minimum will also require no more than O(n).

See this wonderful article: http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

edited Mar 24 '20 at 19:46

answered Mar 24 '20 at 19:41

I have no idea why anybody would downvote this. This is a great and elegant solution and there even is an implementation available via `npm install distance-transform`. Dependencies are a little overkill – I'm looking forward to an occasion to really understand why the math works and implement my own version as a fun project. This mathematical kind of solutions really appeals to me. Many thanks! – Thomas W Mar 25 '20 at 07:45
@ThomasW: this is a kind of sweepline procedure. You compute the shortest distance along a single row and maintain it when moving from a row to the next. The theory for the Manhattan distance is easy. That for Euclidean is less. Note that removing inner points would be counter-productive. – Mar 25 '20 at 08:06

score 2 · Answer 2 · edited Mar 24 '20 at 17:49

2

If your sets are of no special shape (like line-segments) you will hardly find a better solution than O(n²).

But you can add a pre-processing step to reduce n. Remove all inner points of the sets. That (depending on the sets) may reduce the n significantly. In your example, I estimate that would reduce the size of n by half.

If your example is a typical example for your sets, you can transform the sets to a set of line segments and then calculate the distances between them.

edited Mar 24 '20 at 17:49

Drew Pesall

179
3
12

answered Mar 24 '20 at 17:41

MrSmith42

9,961
6
38
49

Yes, removal of pixels is definitely a good thing to do. But there might be O(n log n) solutions. I found [this question](/questions/3700983#3701870) that points to [this paper](http://www-cgrl.cs.mcgill.ca/~godfried/publications/mindist.pdf). Have to check if it's actually covering my problem, though. – Thomas W Mar 24 '20 at 18:39

score -1 · Answer 3 · edited Jun 20 '20 at 09:12

USE the GPU

With the canvas 2D API you have limited access to the GPU which you can leverage to your advantage.

If the two colors are separate channels (as you have red and blue) and there are no other colors to mess things up, you can use the GPU to scale the image down to reduce the initial search.

Create a working canvas

const can = document.createElement("canvas");
var w = can.width = ctx.canvas.width;
var h = can.height = ctx.canvas.height;
const ctxW = can.getContext("2d");

Set smoothing on and blend mode copy

ctxW.imageSmoothingEnabled = true;
ctxW.globalCompositeOperation = "copy";

Reduce the original canvas in half steps

// first step move original to working canvas
w /= 2;
h /= 2;
ctxW.drawImage(ctx.canvas, 0, 0, w, h);

// Reduce again drawing onto its self
ctxW.drawImage(ctxW.canvas, 0, 0, w, h, 0, 0, w / 2, h / 2);
w /= 2;
h /= 2;
ctxW.drawImage(ctxW.canvas, 0, 0, w, h, 0, 0, w / 2, h / 2);

const imgData = ctxW.getImageData(0, 0, w / 2, h / 2); // 1/64th as many pixels

At this point the scaled down canvas is 1/8th the size, better yet it has 8² less pixels to crunch.

The scaling is done by the GPU.

You can then search these pixels via the brute force method, creating a list of candidates. Note that if red and blue are closer than 8 pixel they will now occupy the same pixel in some instances.

Then return to the original canvas and refine the proximity of the candidates found in the scaled down pixel data.

Not really an improvement on O(n²) but a massive performance gain as you exploit the power of parallel processing that the GPU provides.

Also note that when you reduce each step you have enough space on the working canvas to keep each reduction meaning you can work back up through the reductions as you refine candidate areas, saving even more time.

Calculate minimal distance between two "pixel blobs" in canvas

3 Answers3

USE the GPU