How to avoid nested for loops in matlab?

I am constructing an adjacency list based on intensity difference of the pixels in an image. The code snippet in Matlab is as follows:

m=1;
len = size(cur_label, 1);
for j=1:len
  for k=1:len
      if(k~=j)    % avoiding diagonal elements
          intensity_diff = abs(indx_intensity(j)-indx_intensity(k));     
                 %intensity defference of two pixels.

            if intensity_diff<=10     % difference thresholded by 10
                adj_list(m, 1) = j;   % storing the vertices of the edge
                adj_list(m, 2) = k;
                m = m+1;
            end
        end
    end
end
y = sparse(adj_list(:,1),adj_list(:,2),1);       % creating a sparse matrix from the adjacency list

How can I avoid these nasty nested for loops? If the image size is big, then its working just as disaster. If anyone have any solution, it would be a great help for me.

Ratna

Answer 1

[Jan]

While the loops are not evil by design, a missing pre-allocation is.

m = 0;   % Easier to start at 0
len = size(cur_label, 1);
adj_list = zeros(len * len, 2);   % Maximum possible length
for j=1:len
  for k=1:len
    if k~=j                       % avoiding diagonal elements
        intensity_diff = abs(indx_intensity(j)-indx_intensity(k));     
        if intensity_diff<=10     % difference thresholded by 10
            m = m + 1;
            adj_list(m, 1) = j;   % storing the vertices of the edge
            adj_list(m, 2) = k;
        end
      end
   end
end
y = sparse(adj_list(1:m, 1), adj_list(1:m, 2), 1);

In the next step, try if a vectorization is faster. Note that this is not necessarily faster, so a comparison with real data is required:

m = 0;   % Easier to start at 0
len = size(cur_label, 1);
adj_list = zeros(len * len, 2);   % Maximum possible length
for j=1:len
  intensity_diff    = (abs(indx_intensity(j) - indx_intensity(:)) <= 10);
  intensity_diff(j) = false;
  index             = find(intensity_diff);
  n                 = m + length(index) - 1;
  adj_list(m:n, 1)  = j;   % storing the vertices of the edge
  adj_list(m:n, 2)  = index(:);
  m                 = m + n + 1;
end
y = sparse(adj_list(1:m-1, 1), adj_list(1:m-1, 2), 1);

Please test this - I cannot run it currently.

Vectorizing the outer loop also would create a large temporary array. In many cases accessing large memory sections is much slower than processing the problem ich chunks, which match in the processor cache. So I expect, that a full vectorization is slower. Better try a parfor loop.

If this works, please post some timings with real data. Thanks!