算法:距离变换 - 任何更快的算法？

Question

我正在尝试解决距离变换问题(使用曼哈顿距离)。基本上，给出带有 0 和 1 的矩阵，程序必须将每个位置的距离分配给最近的 1。例如，对于这个

0000
0100
0000
0000

距离变换矩阵是

2123
1012
2123
3234

我脑海中可能的解决方案是:

最慢​​的(最慢是因为我试图实现它们——它们在非常大的矩阵上滞后):

1. 蛮力法 - 对于程序读取的每 1 个，从头到尾相应地改变距离。

2. 从 0 开始的广度优先搜索 - 对于每个 0，程序从里到外寻找最近的 1。

3. 与 2 相同，但从 1 的标记开始，从里到外每段距离。

4. 快得多(从别人的代码中读取)

   从 1 开始的广度优先搜索

   1. Assign all values in the distance matrix to -1 or very big value.
   2. While reading matrix, put all positions of 1's into queue.
   3. While queue is not empty
       a. Dequeue position - let it be x
       b. For each position around x (that has distance 1 from it)
           if position is valid (does not exceed matrix dimensions) then
               if distance is not initialized or is greater than (distance of x) + 1 then
                   I. distance = (distance of x) + 1
                   II. enqueue position into queue
   

我想问一下是否有更快的解决方案来解决这个问题。我试图搜索距离变换的算法，但大多数算法都在处理欧氏距离。

提前致谢。

Answer 1

广度优先搜索将执行 Θ(n*m) 操作，其中 n 和 m 是矩阵的宽度和高度。

您需要输出 Θ(n*m) 个数，因此从理论上讲，您无法获得比这更快的速度。

我假设您对涉及缓存和此类优化的讨论不感兴趣。

---

请注意，此解决方案适用于更有趣的情况。例如，想象同一个问题，但可能有不同的“来源”:

00000
01000
00000
00000
00010

使用 BFS，您将在相同的时间复杂度内获得以下距离最近的源:

21234
10123
21223
32212
32101

但是，对于单一来源，还有另一种解决方案可能在实践中具有稍微更好的性能(即使复杂性仍然相同)。

之前，让我们观察以下属性。

性质:如果源在(a, b)，那么点(x, y)有以下曼哈顿距离:

d(x, y) = abs(x - a) + abs(y - b)

这应该很容易证明。所以另一种算法是:

for r in rows
  for c in cols
    d(r, c) = abc(r - a) + abs(c - b)

非常简短。

---

除非您编写并测试它，否则没有简单的方法来比较这两种算法。假设有一个有效的有界队列实现(使用数组)，每个单元有以下主要操作:

• BFS:队列插入/删除，每个节点访问5次(邻居4次，出队1次)
• 直接公式:两个减法和两个if

这实际上取决于编译器及其优化以及特定的 CPU 和内存架构，以确定哪个性能更好。

也就是说，我建议您选择对您来说更简单的那个。但是请注意，对于多个源，在第二种解决方案中，您需要对数组进行多次传递(或一次传递中的多次距离计算)，并且对于足够多的源，这肯定比 BFS 的性能更差。