How can I eliminate as many loops as possible from the following code?

The following source code uses 4 loops at a time. My program is deadly slow.

How can I eliminate as many loops as possible from the following code?

main.m

      % iterate through each pixel in the 
      % line mask from left to right
      for y=1:height%yyy
          for x=1:width%xxx
              if(mask(y,x))
                  pR = [x, y];
                  t_k_sqr = old_thickness * old_thickness;
                  vvv = w1_ .* old_var_k + w2_ .* t_k_sqr;
                  new_var_k = max(vvv, k_min);   

                  up = 1;
                  [dotted_image, top_y] = rg_traverse(dotted_image, pR, dS, dimension, up, new_var_k); 
                  down = -1;
                  [dotted_image, bottom_y] = rg_traverse(dotted_image, pR, dS, dimension, down, new_var_k);

                  old_thickness = abs(bottom_y - top_y);

                  old_var_k = new_var_k;                
              end
          end
      end

rg_traverse.m

function [output_image, y] = rg_traverse(input_image, pR, dS, dimension, direction, var_k)
    threshold = 0.1;
    white = 255;    

      output_image = input_image;

      pI_previous = pR;%(x, y) %tested
      pI_present = [pR(1), pR(2)-direction];
      pI_present_x = pI_present(1);
      pI_present_y = pI_present(2);

      [height, ~] = size(input_image);

      max_sim_value = 0.2;

      y=pI_present_y+direction;
      while (1)        
          % calculate (x,y) from direction
          x = pI_present_x;
          y = y-direction;
          pI_present = round([x, y]);

          % get 5 neighboring points
          pTx5 = rg_get_5_up_ptr(input_image, pI_present);

          % find the point with max similarity value
          [max_point, max_sim_value] = rg_max_similarity(input_image, pR, pTx5, dS, pI_previous, dimension, var_k);

          % set pixel to white/black at that point
          if (max_sim_value>=threshold)
              output_image = image_set(output_image, max_point(1), max_point(2), white);
          end

          pI_previous = pI_present;

         str = {num2str(pI_present), num2str(max_point), num2str(max_sim_value)};        
         write_string('rg_traverse_up.txt', str);

          if  max_sim_value<threshold
              break
          end

          if(direction==1)
              if y==1
                  break
              end
          elseif(direction==-1)
              if y==height
                  break
              end
          end
      end
  end

Answer 1

[Jan]

I think you cannot get rid of any of the loop. In the loops of the main function, you call rg_traverse. To omit the loops, it would be required to vectorize rg_taverse. But there the function rg_get_5_up_ptr, rg_max_similarity, image_set and write_string are called. It is not clear, what these functions do, but obviously the while(1) loop show, that this is an iterative process. And in consequence a vectorization is impossible: You do not know in advnace how many iterations are needs. So how could you porcess this as a vector?

Most likely the vectorization is not your goal at all, but you want to accelerate the code. Then use the profiler to find the piece of code, which takes the most time to run. Concentrate on these line or lines only. It is not worth to accelerate a part of the code, which takes 1% of the total runtime - if you improve the speed by a factor of 2, the total code is only 0.5% faster.

[Ba Ba Black Sheep!]

Profiler indicates if(mask(y,x)) to be the most time-consuming.

[Jan]

Really? This means, that the mask is huge and contains only a very small number of true elements. Then replace:

for y=1:height%yyy
  for x=1:width%xxx
     if(mask(y,x))
         pR = [x, y];
         ...

by:

[i1, i2] = find(mask);
for k = 1:numel(i2)
  pR = [i2(k), i1(k)];
  ...

Does this help?