有效地实现侵蚀/扩张 [英] Efficiently implementing erode/dilate
问题描述
所以通常且非常低效最小值/最大值滤波器是通过使用四个用于循环来实现。
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.
更新：我特别想知道这还是一种实现的任何见解：的 http://dl.acm.org/citation.cfm?id=2114689
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:
-
扩张由KXL内核是由KX1内核来扩张由1XL内核等于扩张。你可以只用for循环三要这两个次扩张中，在O（K * N * M）和O（L * N * M）
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));
}
}
这篇关于有效地实现侵蚀/扩张的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
