位图上的并发腐蚀或扩展

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

通过膨胀/侵蚀,可以对像素周围的结构元素执行最大/最小操作。例如,如果您有一个5x5窗口,那么每个像素看25个像素,因此本质上每个像素看25次。因此,使用这种天真的方法,每个像素的计算复杂度与像素中结构元素的大小成正比。

使用更高效的形态学算子计算算法,您可以降低这种复杂性,甚至可以降低到恒定的复杂性(每像素),而不管结构元素的大小。关于这方面有很多文献,我最后包括了一些参考文献,他们也引用了其他论文并进行了比较。

我不知道你所处的环境,以及绩效的重要性。但并行化将是我正在做的最后一步。首先,无论性能如何,我都会让算法运行。一旦我对此感到满意(或者对运行时感到恼火,我愿意对此做些什么),我就会提高到一个更高效的解决者。如果最后,我仍然需要稍微推动运行时,我会并行化(或者考虑使用GPU是否有意义)。

如果现在进行并行化,可能会得到一些加速,但在提高性能的算法改进方面,您会有所损失。

现在,正如所承诺的,两篇关于高效形态滤波器的论文: 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 看起来也不错。我没有详细阅读,但我在我的研究领域认识罗恩·金梅尔,这可能是一本不错的书。

OpenMP是一种共享内存范例。如果可以保证所有不同的进程都将向相同的位置写入相同的值,那么让它们这样做就可以了。有比赛条件,但不会影响结果。

这为您提供了以下代码:

int* bitmap = ...;              // pointer to bitmap data with width and height

#pragma omp parallel for collapse(2)
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

如果不能做出这样的保证,可以使用关键部分来限制写访问:

int* bitmap = ...;              // pointer to bitmap data with width and height

#pragma omp parallel for collapse(2)
for(long iy=0; iy<height; iy++) 
for(long ix=0; ix<width; ix++) 
  if(write_pattern(ix,iy)) {
    #pragma omp critical
    apply_pattern(ix,iy, 0);   // writes "0" to bitmap, write only, no read      
  }

但是,如果你不能做出这样的保证,这是 令人不快的 并行性候选,因为每次运行代码时,不同的进程将在不同的时间到达位图的不同部分。也就是说,执行顺序是不确定的,因此您无法预测结果。假设只有一个正确的结果 必须 产生相同的输出。

同样,请确保您正在使用 apply_pattern() 更改原始数据以外的内容,或者您的结果将再次具有不确定性,因为一个线程可能会在另一个线程看到修改的部分之前或之后修改输入。

另一种策略是收集所有需要修改的地方,然后在以后连续编写它们。如果你的支票很贵,但你的书写很便宜,这可能是有道理的;比方说,如果您使用正则表达式进行检查并写出零。

int* bitmap = ...;              // pointer to bitmap data with width and height

typedef std::pair<long,long> gridloc;
std::vector<gridloc> patterns;

//Use a custom reduction operator, available in newer versions of OpenMP
#pragma omp declare reduction (merge : std::vector<gridloc> : omp_out.insert(omp_out.end(), omp_in.begin(), omp_in.end()))
#pragma omp parallel for collapse(2) reduction(merge:patterns)
for(long iy=0; iy<height; iy++) 
for(long ix=0; ix<width; ix++) 
  if(write_pattern(ix,iy)) {
    patterns.emplace_back(ix,iy)
  }

for(const auto &c: patterns)
  apply_pattern(c.first,c.second, 0);   // writes "0" to bitmap, write only, no read      

如果书写成本很高,您可以对 patterns 要合并写入,请消除冗余写入、对写入进行拓扑排序(&c