Computational Complexity of Image Segmentation algorithms

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

• Could you please be more specific? – Geoff Oxberry Jan 9 '12 at 22:20
• I edited my question. Isn't it specific yet? Thanks. – Bahar S Jan 10 '12 at 5:11
• 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.) – Geoff Oxberry Jan 10 '12 at 5:14
• 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. – dmckee Jan 10 '12 at 22:52

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.

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).

• 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). – aeismail Jan 10 '12 at 14:54
• Thanks, I have edited the question, could you please view it again? Thanks. – Bahar S Jan 10 '12 at 16:51

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.