2
$\begingroup$

I have a question. I need to calculate the computational complexity of image segmentation algorithms. Can anyone please help me? For example, I have a screen-size picture with white background containing k randomly-positioned black objects with random sizes (between 90*90 to 110*110) in it. I am going to calculate how long it takes for a rapid current computer to segment all black items in my image. For example, use connected component labeling to segment the components: 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
Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Could you please be more specific? $\endgroup$
    – Geoff Oxberry
    Commented Jan 9, 2012 at 22:20
  • $\begingroup$ I edited my question. Isn't it specific yet? Thanks. $\endgroup$
    – Bahar S
    Commented Jan 10, 2012 at 5:11
  • $\begingroup$ There are many image segmentation algorithms. Which one(s) are you interested in? (I am not an expert in these algorithms, but perhaps someone else is, and they may be better able to assist you.) $\endgroup$
    – Geoff Oxberry
    Commented Jan 10, 2012 at 5:14
  • 1
    $\begingroup$ This would appear to be a special case of clustering, so the worst case would be O(I log I) in the number of "on" points using a strategy analogous to that of DBSCAN once you have a list of those "on" points which is O(N*M). Best strategy may depend on how the data comes to you. $\endgroup$
    – dmckee --- ex-moderator kitten
    Commented Jan 10, 2012 at 22:52

3 Answers 3

Reset to default
2
$\begingroup$

It's kind of straight forward to calculate the complexity of the two-pass algorithm from the Wikipedia page you linked: First, one iterates from upper left to lower right over all pixels and assigns a preliminary label to each pixel while maintaining a map of equivalence relations for the labels. This needs four checks for every pixel. In the second pass one goes over the labeled components and replaces the preliminary labels according to the equivalence relation.

Complexity an image with $N$ pixels, $M$ of which are "foreground": $4N$ for the first pass and at most $M$ for the second pass.

Improve this answer
$\endgroup$
1
$\begingroup$

If you have a detailed description of the algorithm (preferably pseudocode), then calculating the complexity is simply a matter of going through it and counting operations. If you'd like to provide some pseudocode, we could help you more.

Most introductory books on scientific computing include some examples of counting the number of operations in different algorithms. Trefethen & Bau has some detailed examples with pictures (the application is different, but the process is the same).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Another useful source would be Introduction to Algorithms by Cormen et al., and used as the basis for the course of the same name at MIT (offered as part of their OpenCourseWare platform). $\endgroup$
    – aeismail
    Commented Jan 10, 2012 at 14:54
  • $\begingroup$ Thanks, I have edited the question, could you please view it again? Thanks. $\endgroup$
    – Bahar S
    Commented Jan 10, 2012 at 16:51
0
$\begingroup$

If you have a pseudocode for the algorithm that you are implementing, one key to determining the asymptotic computational complexity is to observe the nested loops (for loops, while loops, etc...). If you have nested for loops which contain only operations that are computed in constant time (or at least, bounded by a constant), then the asymptotic complexity rests in the total number of iterations invoked by the loops. For example: 

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

This algorithm would run in $\Theta({n}^{2})$ time because the instructions "DO STUFF..." occur $n^{2}$ times. If, on the other hand, you had while loops or if-then statements, then it becomes more important to ask yourself whether you are interested in the best case, worst case, or average case scenario, since each may be different.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.