本文介绍了有效地实现侵蚀/扩张的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

所以通常且非常低效最小值/最大值滤波器是通过使用四个用于循环来实现。

So normally and very inefficiently min/max filter is implemented by using four for loops.

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;
    }
}

然而,该方法是该死的低效的,因为它再次检查previously检查值。所以我想知道有哪些方式可以使用previously检查值的下一次循环来实现这一点?

However this approach is damn inefficient since it checks again previously checked values. So I am wondering what methods are there to implement this with using previously checked values on next iteration?

任何关于产地的结构元素尺寸/点设想可以。

Any assumptions regarding structuring element size/point of origin can be made.

更新:我特别想知道这还是一种实现的任何见解:的

Update: I am especially keen to know any insights of this or kind of implementation: http://dl.acm.org/citation.cfm?id=2114689

推荐答案

我一直在关注这个问题有一段时间了,希望有人会写一个充实出答案,因为我琢磨了同样的问题。

I have been following this question for some time, hoping someone would write a fleshed-out answer, since I am pondering the same problem.

下面是我自己的努力,到目前为止,我没有测试过这一点,但我认为你可以做反复膨胀和腐蚀与任何结构元素,只访问每个像素两次:

Here is my own attempt so far; I have not tested this, but I think you can do repeated dilation and erosion with any structuring element, by only accessing each pixel twice:

假设:假设构造要素/内核是一个KXL矩形和图象是一个N×M的矩形。假设K,L是奇数。

您介绍的基本方法有四个for循环,并采取 O(K * L * N * M)的时间才能完成。

The basic approach you outlined has four for loops and takes O(K*L*N*M) time to complete.

通常要与相同的内核反复扩张,所以时间再次乘以胀缩的期望数目

Often you want to dilate repeatedly with the same kernel, so the time is again multiplied by the desired number of dilations.

我有加快扩张三个基本思路:

I have three basic ideas for speeding up the dilation:

  1. 扩张由KXL内核是由KX1内核来扩张由1XL内核等于扩张。你可以只用for循环三要这两个次扩张中,在O(K * N * M)和O(L * N * M)

  1. dilation by a KxL kernel is equal to dilation by a Kx1 kernel followed by dilation by a 1xL kernel. You can do both of these dilations with only three for loops, in O(K*N*M) and O(L*N*M)

不过,你可以做一个扩张与KX1内核更快:你只需要访问的每个像素一次。为此,您需要一个特定的数据结构,解释如下。这允许你做O的单一的扩张(N * M),无论内核大小

However you can do a dilation with a Kx1 kernel much faster: You only need to access each pixel once. For this you need a particular data structure, explained below. This allows you to do a single dilation in O(N*M), regardless of the kernel size

由KX1内核重复扩张是一个大内核相当于一个单一的扩张。如果扩张P乘以一个KX1的内核,这相当于用一个扩张一个((K-1)* P + 1)×1 内核。所以你可以做重复的扩张与单通任何内核大小,O(N * M)的时间。

repeated dilation by a Kx1 kernel is equal to a single dilation by a larger kernel. If you dilate P times with a Kx1 kernel, this is equal to a single dilation with a ((K-1)*P + 1) x 1 kernel.So you can do repeated dilation with any kernel size in a single pass, in O(N*M) time.

现在的第2步
详细说明您需要具有以下属性队列:


Now for a detailed description of step 2.
You need a queue with the following properties:

  • 推的元件到队列的在固定时间内的背面。
  • 从在固定时间内的队列前面流行的元素。
  • 查询在固定的时间队列中的当前最小或最大的元素。

如何建立这样的队列在这个计算器的答案被描述:实现一个队列,其中push_rear(),pop_front()和get_min ()都是常量时间的操作的。遗憾的是没有太多的伪code,但基本的想法似乎声音。

How to build such a queue is described in this stackoverflow answer: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.Unfortunately not much pseudocode, but the basic idea seems sound.

使用这样的队列,就可以计算出在一个道次的KX1扩张:

Using such a queue, you can calculate a Kx1 dilation in a single pass:

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));
    }
}

这篇关于有效地实现侵蚀/扩张的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

07-27 20:26