计算画布中两个“像素斑点”之间的最小距离

Question

我想计算两组像素之间的距离–出于说明目的，一组蓝色像素和一组红色像素。我想计算x方向，y方向和任意方向上的最接近距离（请参见图中的三个箭头）。通常，一种颜色的像素可能是未连接的色块（如示例中的红色），但是大多数时候它们将被连接，尽管它们可能有孔（如示例中的蓝色）。

是否有任何库或算法已经以明智的方式解决了这个问题？提出解决方案并不是特别困难– x和y距离是O（n）问题，但是对于任意距离，幼稚的蛮力算法是O（n²）。我预感有更好的方法。

Answer 1

您可以在线性时间O（n）中计算任意形状（包括不连续的）的斑点周围的完整距离图，它可以是Manhattan或Euclidean（其中n表示图像大小）。

[拥有此地图时，扫描其他斑点以查找最小值也将不超过O（n）。

参见此精彩文章：http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

Answer 2

如果您的集合没有特殊形状（例如线段），您将找不到比O（n²）更好的解决方案。

但是您可以添加预处理步骤以减少n。删除集合的所有内部点。这（取决于集合）可能会大大减少n。在您的示例中，我估计这会将n的大小减小一半。

如果您的示例是集合的典型示例，则可以将这些集合转换为一组线段，然后计算它们之间的距离。

Answer 3

使用GPU

使用canvas 2D API，您只能有限地访问GPU，而您可以利用GPU发挥自己的优势。

[如果两种颜色是单独的通道（因为您有红色和蓝色），并且没有其他颜色使事情变得混乱，则可以使用GPU缩小图像以减少初始搜索。

创建工作画布

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

设置平滑和混合模式copy

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

半步缩小原始画布

// 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 

此时，缩小的画布的大小是原来的1/8，但更好的是，它减少了8 ²个像素。

缩放由GPU完成。

然后您可以通过蛮力方法搜索这些像素，从而创建候选列表。请注意，如果红色和蓝色小于8像素，则在某些情况下它们现在将占据相同的像素。

然后返回到原始画布，并缩小像素数据中找到的候选对象的接近度。

并不是对O（n ²）的真正改善，而是在利用GPU提供的并行处理功能时获得了巨大的性能提升。

还请注意，当缩减每个步骤时，工作画布上有足够的空间来保留每个缩减，这意味着您可以在缩小候选区域的同时进行精简，从而节省更多时间。