Эффективное внедрение эродирования/расширения

Question

Таким образом, обычно и очень неэффективно фильтр min/max реализуется с использованием четырех циклов.

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

Однако этот подход не эффективен, поскольку он снова проверяет ранее проверенные значения. Поэтому мне интересно, какие методы существуют для реализации этого с использованием ранее проверенных значений на следующей итерации?

Могут быть сделаны любые предположения относительно размера или размера элемента структурирующего элемента.

Update: Я особенно заинтересован, чтобы знать какие-либо идеи того или вида реализации: http://dl.acm.org/citation.cfm?id=2114689

Answer 1

теоретический способ повышения сложности будет поддерживать BST для пикселей KxK, удалить previsous KX1 пикселей и добавьте к нему следующие пиксели Kx1. Стоимость этой операции будет 2K log K, и она будет повторяться NxN раз. В целом время вычислений станет NxNxKxlog K из NxNxKxK

Answer 2

Единственный подход, о котором я могу думать, - это буферизация максимальных значений пикселей и строк, в которых они найдены, так что вам нужно только выполнить полную итерацию по размеру ядра строка/столбец, когда максимум больше не находится под ним.
В следующем псевдокоде C-like я предположил, что целые числа со знаком, 2d строковых массивов для источника и назначения и прямоугольное ядро ​​над [& 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

Я задал этот вопрос в течение некоторого времени, надеясь, что кто-то напишет ответ сглаживания, так как я обдумываю ту же проблему.

Вот моя собственная попытка; Я не тестировал это, но я думаю, что вы можете делать повторную дилатацию и эрозию с любым элементом структурирования, только дважды обращаясь к каждому пикселю:

Предположения. Предположим, что структурирующий элемент/ядро ​​является прямоугольником KxL, а изображение является Прямоугольник NxM. Предположим, что K и L нечетны.

Основной подход, который вы наметили, имеет четыре для петель и принимает O(K*L*N*M) времени для завершения.

Часто вы хотите размножаться повторно одним и тем же ядром, поэтому время снова умножается на необходимое количество разведений.

У меня есть три основных идей для ускорения дилатации:

1. дилатации на ядре K равно дилатацию по KX1 ядра с последующим растяжением на ядре 1XL.Вы можете сделать оба этих растяжений только три для петель, в O (K N M) и O (L N M)

2. Однако вы можете сделать дилатации с KX1 ядра намного быстрее: Вы требуется только один раз получить доступ к каждому пикселю. Для этого вам нужна конкретная структура данных, поясняемая ниже. Это позволяет делать одиночную дилатацию в O (N * M), независимо от размера ядра

3. Повторная дилатация ядра Kx1 равна единице дилатации большим ядром. Если вы расширяете P раз ядром Kx1, это равно одной дилатации с ядром ((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)); 
    } 
} 

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

вы сотрудничаете uld получают O (N * M) в 2D. Решение HugoRune намного проще и, вероятно, быстрее (хотя, вероятно, это можно было бы улучшить).