有效实施侵蚀/扩张

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

提高了复杂性将保持为KXK像素的BST，删除previsous KX1像素的理论方法并添加下一个Kx1像素。这个操作的成本是2K log K，它会重复NxN次。总的来说，计算时间将变为NxNxKxlog K from NxNxKxK

Answer 2

我能想到的唯一方法是缓冲最大像素值及其找到的行，以便您只需对内核大小进行完整迭代行/列当最大值不再在它下面时。
在下面的类C的伪代码中，我假设符号整数，第2行主阵列用于源和目的地和通过矩形内核[＆plusmn; DX，＆plusmn; DY]。

//initialise the maxima and their row positions 
for(x=0; x < nx; ++x) 
{ 
    row[x] = -1; 
    buf[x] = 0; 
} 

for(sy=0; sy < ny; ++sy) 
{ 
    //update the maxima and their row positions 
    for(x=0; x < nx; ++x) 
    { 
    if(row[x] < max(sy-dy, 0)) 
    { 
     //maximum out of scope, search column 
     row[x] = max(sy-dy, 0); 
     buf[x] = src[row[x]][x]; 
     for(y=row[x]+1; y <= min(sy+dy, ny-1); ++y) 
     { 
     if(src[y][x]>=buf[x]) 
     { 
      row[x] = y; 
      buf[x] = src[y][x]; 
     } 
     } 
    } 
    else 
    { 
     //maximum in scope, check latest value 
     y = min(sy+dy, ny-1); 
     if(src[y][x] >= buf[x]) 
     { 
     row[x] = y; 
     buf[x] = src[y][x]; 
     } 
    } 
    } 

    //initialise maximum column position 
    col = -1; 

    for(sx=0; sx < nx; ++sx) 
    { 
    //update maximum column position 
    if(col<max(sx-dx, 0)) 
    { 
     //maximum out of scope, search buffer 
     col = max(sx-dx, 0); 
     for(x=col+1; x <= min(sx+dx, nx-1); ++x) 
     { 
     if(buf[x] >= buf[col]) col = x; 
     } 
    } 
    else 
    { 
     //maximum in scope, check latest value 
     x = min(sx+dx, nx-1); 
     if(buf[x] >= buf[col]) col = x; 
    } 

    //assign maximum to destination 
    dest[sy][sx] = buf[col]; 
    } 
} 

当源从右下方左到最小的顶部的最大顺利，迫使一个完整的行或列扫描在每个步骤（尽管它仍比更有效时会发生最坏情况下的性能原始嵌套循环）。
虽然我认为平均情况下性能会好得多，因为包含增加值（包括行和列）的区域将在需要扫描前更新最大值。这就是说，没有经过实际测试，我建议你运行一些基准测试，而不是相信我的直觉。

Answer 3

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

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

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

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

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

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

1. 扩张由K×L个内核是由KX1内核来扩张由1XL内核等于扩张。你可以只用三为循环做这两个胀缩的，为O（K ñ M）和O（L ñ M）

2. 但是你可以做一个KX1内核扩张更快：你只需要访问每个像素一次。为此，您需要一个特定的数据结构，如下所述。这允许您在O（N * M）中执行单个扩展，而不管内核大小如何

3. Kx1内核的重复扩展等于较大内核的单个扩展。如果用Kx1内核扩展P次，则这与使用内核的单个扩展相等。 因此，您可以在O（N * M）时间内以单遍的任何内核大小进行重复扩展。

---

现在对于步骤2.
的详细描述你需要一个队列具有以下属性：

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

如何构建这样的队列在这个计算器的回答中描述：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)); 
    } 
} 

Answer 4

相同种类的优化可以用作“非最大抑制”算法 http://www.vision.ee.ethz.ch/publications/papers/proceedings/eth_biwi_00446.pdf

Answer 5

在1D中，使用形态小波为O变换（N）：

https://gist.github.com/matovitch/11206318

您共在2D中获得O（N * M）。 HugoRune解决方案更简单，可能更快（尽管可能会改进这一点）。