计算科学 - 图像分割算法的计算复杂度 - 吾爱随笔录

图像分割算法的计算复杂度

计算科学复杂图像处理

2021-12-04 01:44:56

我有个问题。我需要计算图像分割算法的计算复杂度。谁能帮帮我吗？例如，我有一张屏幕大小的白色背景图片，其中包含 k 个随机定位的黑色对象，这些对象具有随机大小（在 90*90 到 110*110 之间）。我将计算一台快速的当前计算机需要多长时间来分割我图像中的所有黑色项目。例如，使用连接组件标签来分割组件：http ://en.wikipedia.org/wiki/Connected-component_labeling

One-Pass(Image)
            [M, N]=size(Image);
            Connected = zeros(M,N);
            Mark = Value;
            Difference = Increment;
            Offsets = [-1; M; 1; -M];
            Index = [];
            No_of_Objects = 0; 

   for i: 1:M :
       for j: 1:N:
            if(Image(i,j)==1)            
                 No_of_Objects = No_of_Objects +1;            
                 Index = [((j-1)*M + i)];           
                 Connected(Index)=Mark;            
                 while ~isempty(Index)                
                      Image(Index)=0;                
                      Neighbors = bsxfun(@plus, Index, Offsets');
                      Neighbors = unique(Neighbors(:));                
                      Index = Neighbors(find(Image(Neighbors)));                                
                      Connected(Index)=Mark;
                 end            
                 Mark = Mark + Difference;
            end
      end
  end

3个回答

从您链接的维基百科页面计算两遍算法的复杂性是一种直接的方式：首先，一个从左上角到右下角遍历所有像素，并为每个像素分配一个初步标签，同时保持等价关系图为标签。这需要对每个像素进行四次检查。在第二遍中，根据等价关系检查标记的组件并替换初步标记。

图像的复杂性 $N$ 像素， $M$ 其中是“前景”： $4N$ 第一次，最多 $M$ 第二遍。

如果你对算法有详细的描述（最好是伪代码），那么计算复杂度只是简单地通过它和计数操作的问题。如果您想提供一些伪代码，我们可以为您提供更多帮助。

大多数关于科学计算的介绍性书籍都包含一些计算不同算法中操作次数的示例。 Trefethen & Bau有一些带图片的详细示例（应用不同，但过程相同）。

如果您有正在实现的算法的伪代码，确定渐近计算复杂度的一个关键是观察嵌套循环（for 循环、while 循环等）。如果您嵌套的 for 循环仅包含在常数时间内计算的操作（或至少以常数为界），那么渐近复杂度取决于循环调用的迭代总数。例如：

for i=1 to n  
    for j=1 to n  
        DO STUFF... (all constant time operations)  
    endfor  
endfor

该算法将运行在 $\Theta({n}^{2})$ 时间因为指令“DO STUFF ...”发生 $n^{2}$ 次。另一方面，如果您有 while 循环或 if-then 语句，那么问自己是否对最佳情况、最坏情况或平均情况感兴趣变得更重要，因为每种情况可能不同。

其它你可能感兴趣的问题

上一篇在 PETSc 中编译和运行“hello world”程序下一篇请求葡萄牙语或英语的有限差分方法参考