canvas - 点到图像边缘的最短距离

Question

这可能在其他地方得到解决，但我在上面找不到任何东西。我试图找到图像上任意点与最近的透明像素之间的最短距离，更强调速度而不是准确性。

目前我正在做的是每 0.1 弧度检查一行中的每个像素，当它到达透明像素时停止并跟踪最短的。不过，这并不是特别快或准确。有没有更好的办法？也许人们用于这种事情的算法？

我正在使用 javascript/canvas 执行此操作。

Answer 1

一种方法是计算所有像素到最近的透明像素的距离（距离变换），这可以在原始图像的两遍中执行。计算完距离变换后，可以在常数时间 O(1) 内找到最近的透明像素。如果透明区域随时间缓慢变化，则此方法更为优越。

在透明区域快速变化的情况下，您可能会做得更好。

Answer 2

最快的准确算法是简单地围绕该点做圆圈。检查每个相邻像素，然后检查下一层，本质上是广度优先搜索，这将在 O(n) 时间内运行，其中 n 是像素数。现在你正在做的是一种更快的概率方法。

我认为使算法比您的算法更快的唯一方法是选择一个圆大小，例如 3 像素直径，并检查（例如）该圆上像素的 75%（最佳百分比取决于您对准确性的期望） . 如果找不到透明像素，则将圆圈的大小加倍。但是，根据图像的外观，这可能非常不准确，但它更喜欢速度而不是准确性。

否则，除非您可以根据周围的像素收集有关透明像素所在位置的数据，否则我并没有真正看到您的算法有所改进。然后，您可以更聪明地进行搜索。否则，您通过测试像素所学到的只是一个且唯一的像素是（或不）透明的。

如果您可以说您只是在寻找大于 x 像素的透明区域，并且想要准确地找到任何直径为 x 像素的区域，那么您可以调整圆圈的大小以增加 x-1，然后提高准确性您可以沿着透明像素朝向您的原点，直到找到最近的像素。