有效實施侵蝕/擴張

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解決方案更簡單，可能更快（儘管可能會改進這一點）。