c++ - 在位图上并发腐 eclipse 或膨胀

Question

我需要对位图进行形态学操作(膨胀/腐 eclipse 的特殊版本)。 为了加速，我正在使用 openmp 来并行化该过程:

  int* bitmap = ...;              // pointer to bitmap data with width and height
#pragma omp parallel for
   for(long iy=0; iy<height; iy++) 
      for(long ix=0; ix<width; ix++) 
         if(write_pattern(ix,iy)) 
            apply_pattern(ix,iy, 0);   // writes "0" to bitmap, write only, no read

这意味着在某些位置，常量值的模式被写入输出位图中。由于“模式”可能跨越多行，因此很明显多个线程同时将相同的值写入相同的内存位置。它似乎有效，但看起来有点阴暗。

这样可以吗，或者推荐的方法是什么？

Answer 1

我不太介意并行化，但我想指出并行化膨胀/腐 eclipse 不是我在这里选择的第一选择。

通过膨胀/腐 eclipse ，您可以对像素周围的结构元素执行最大/最小操作。例如，如果您查看一个 5x5 的窗口，则每个像素会查看 25 个像素，因此实际上您会查看每个像素 25 次。因此，使用这种朴素的方法，每个像素的计算复杂度与以像素为单位的结构元素的大小成正比。

使用计算形态运算符的更有效算法，您可以降低这种复杂性，甚至可以降低复杂性(每个像素)，而不管结构元素的大小如何。有很多这方面的文献，我在最后包括了一些引用文献，他们也引用了其他论文并进行了比较。

我不知道您的工作环境，也不知道性能有多重要。但并行化将是我要做的最后一步。首先，无论性能如何，我都会让算法运行。一旦我对此感到满意(或者对运行时感到非常恼火，我愿意为此做点什么)，我就会改进为一个更高效的求解器。如果最后，我仍然需要稍微插入运行时，我会并行化(或者考虑使用 GPU 是否有意义)。

如果您现在进行并行化，您可能会获得一些加速，但您会失去提高性能的算法改进。

现在，正如所 promise 的那样，两篇关于高效形态滤波器的论文: Petr Dokládal, Eva Dokladalova. Computationally efficient, one-pass algorithm for morphological filters. Journal of Visual Communication and Image Representation, Elsevier, 2011 ，这个提出了一个 O(1) 算法在结构元素方面，并比较/引用了经典的高效算法。 Joseph Gil, Ron Kimmel. Efficient Dilation, Erosion, Opening and Closing Algorithms也显得不错。我没有详细阅读它，但我从我的研究领域了解 Ron Kimmel，这可能是一本好书。