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

所以通常和非常低效的最小/最大过滤器是通过使用四个 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

最佳答案

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

到目前为止，这是我自己的尝试；我尚未对此进行测试，但是我认为您可以通过仅访问每个像素两次来对任何结构元素进行重复的扩张和腐 eclipse :

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

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

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

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

KxL 内核的

扩张等于 Kx1 内核的扩张，然后是 1xL 内核的扩张。你可以只用三个 for 循环来完成这两个膨胀，在 O(KNM) 和 O(LNM)

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

由 Kx1 内核进行的重复扩张等于由较大内核进行的单次扩张。如果使用 Kx1 内核扩展 P 次，则这等于使用 ((K-1)*P + 1) x 1 内核进行一次扩展。
因此，您可以在 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));
    }
}

关于algorithm - 有效地实现侵 eclipse /扩张，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21854594/