计算 canvas 中两个 "pixel blobs" 之间的最小距离

Question

我想计算两组像素之间的距离——为了便于说明，一组蓝色像素和一组红色像素。我想计算 x 方向、y 方向和任意方向上的最近距离（见图中的三个箭头）。通常，一种颜色的像素可能是不相连的块（如示例中的红色），但大多数情况下它们会相连，尽管它们可能有空洞（如示例中的蓝色）。

是否有任何库或算法已经以合理的方式解决了这个问题？想出一个解决方案并不是特别难——x 和 y 距离是一个 O(n) 问题，但对于任意距离，朴素的蛮力算法是 O(n²)。我有一种预感，有更好的方法。

Answer 1

如果你的集合没有特殊形状（如线段），你很难找到比 O(n²) 更好的解决方案。

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

如果你的例子是你集合的典型例子，你可以将集合转化为一组线段，然后计算它们之间的距离。

Answer 2

您可以在线性时间 O(n) 内计算任意形状斑点周围的全距离图（包括断开的），无论是曼哈顿还是欧几里得（其中 n 表示图像大小）。

当你有这张地图时，扫描其他 blob 以找到最小值也不会超过 O(n)。

看到这篇精彩文章：http://fab.cba.mit.edu/classes/S62.12/docs/Meijster_distance.pdf

Answer 3

使用 GPU

对于 canvas 2D API，您对 GPU 的访问权限有限，您可以利用它来发挥自己的优势。

如果这两种颜色是不同的通道（因为你有红色和蓝色）并且没有其他颜色可以搞砸，你可以使用 GPU 缩小图像以减少初始搜索。

创建工作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");

设置平滑和混合模式 copy

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

将原来的canvas减半

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

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

缩放由 GPU 完成。

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

然后 return 到原始 canvas 并细化在按比例缩小的像素数据中找到的候选者的接近度。

算不上是 O(n²) 的改进，但当您利用 GPU 提供的并行处理能力时，性能会大幅提升。

另请注意，当您减少每一步时，您有足够的 space 工作 canvas 来保持每次减少，这意味着您可以在优化候选区域时通过减少进行备份，甚至节省更多时间。

计算 canvas 中两个 "pixel blobs" 之间的最小距离

Calculate minimal distance between two "pixel blobs" in canvas

javascript

algorithm

geometry

euclidean-distance

html5-canvas

使用 GPU