algorithm - 有效地实现侵 eclipse /扩张

Question

所以通常情况下，最小/最大过滤器是通过使用四个 for 循环实现的，效率非常低。

for( index1 < dy ) { // y loop
    for( index2 < dx ) { // x loop
        for( index3 < StructuringElement.dy() ) { // kernel y
            for( index4 < StructuringElement.dx() ) { // kernel x
                pixel = src(index3+index4);
                val = (pixel > val) ? pixel : val; // max
            }
        }
        dst(index2, index1) = val;
    }
}

但是这种方法非常低效，因为它会再次检查以前检查过的值。所以我想知道有什么方法可以在下一次迭代中使用先前检查的值来实现这一点？

可以做出关于结构元素大小/原点的任何假设。

更新:我特别想知道对这种或某种实现的任何见解:http://dl.acm.org/citation.cfm?id=2114689

Answer 1

我关注这个问题有一段时间了，希望有人能写一个充实的答案，因为我也在思考同样的问题。

到目前为止，这是我自己的尝试；我没有对此进行测试，但我认为您可以对任何结构元素进行重复的膨胀和腐 eclipse ，只需访问每个像素两次:

假设:假设结构元素/内核是一个 KxL 矩形，图像是一个 NxM 矩形。假设 K 和 L 是奇数。

您概述的基本方法有四个 for 循环，需要 O(K*L*N*M) 时间才能完成。

通常你想用同一个内核重复扩张，所以时间再次乘以所需的扩张次数。

我有三个加速扩张的基本想法:

1. KxL 内核的扩张等于 Kx1 内核的扩张，然后是 1xL 内核的扩张。你可以只用三个 for 循环来完成这两个扩张，时间复杂度为 O(KNM) 和 O(LNM)

2. 但是，您可以更快地使用 Kx1 内核进行膨胀:您只需要访问每个像素一次。为此，您需要一个特定的数据结构，如下所述。这允许您在 O(N*M) 中进行一次扩张，而不管内核大小

3. Kx1 内核的重复扩张等于更大内核的单次扩张。如果您使用 Kx1 内核扩展 P 次，这等于使用 ((K-1)*P + 1) x 1 内核进行一次扩展。因此，您可以在 O(N*M) 时间内用任何内核大小在 O(N*M) 时间内重复扩张。

---

现在对步骤2进行详细说明。
您需要一个具有以下属性的队列:

• 在常数时间内将一个元素推到队列的后面。
• 在常数时间内从队列的前面弹出一个元素。
• 在常数时间内查询队列中当前最小或最大的元素。

这个 stackoverflow 答案中描述了如何构建这样一个队列:Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations .不幸的是伪代码不多，但基本思想似乎很合理。

使用这样的队列，您可以一次计算出 Kx1 膨胀:

Assert(StructuringElement.dy()==1);
int kernel_half = (StructuringElement.dx()-1) /2;

for( y < dy ) { // y loop

    for( x <= kernel_half ) { // initialize the queue 
        queue.Push(src(x, y));
    }

    for( x < dx ) { // x loop

        // get the current maximum of all values in the queue
         dst(x, y) = queue.GetMaximum();

        // remove the first pixel from the queue
        if (x > kernel_half)
            queue.Pop();

        // add the next pixel to the queue
        if (x < dx - kernel_half)
            queue.Push(src(x + kernel_half, y));
    }
}