A simple question

I was trying to speed up my code. In general, I am working with big images but to explain my problem, I will take a simple example. First, I executed the following code:

clc;
saturation_map = [ 12 53 65 23; 32 54 65 122; 75 36 587 122 ];
gray_image =     [  6 34 54 11; 21 45 30   4; 21  2 500  10];
index_list = [ 1 2 3 4 5 7 9 10 11];
max_stretch_ratio = 65535; 
num_pixels = length(index_list);

tic;
for i = 1:num_pixels
  pixel_ratio = saturation_map( index_list(i) ) /gray_image( index_list(i));
   if (pixel_ratio < max_stretch_ratio)
       max_stretch_ratio = pixel_ratio;
   end
end
toc

As for loops decrease the speed of the code, I replaced the for loop with:

pixel_ratio = saturation_map(index_list) ./ gray_image(index_list); 
if isempty(index_list)
  pixel_ratio = 65535;
end

max_stretch_ratio = min( pixel_ratio) ;

This runs slower than the first one!! Can anyone rectify the problem?

Answer 1

[Jan]

If the saturation_map, gray_image and index_list are large, the creation of the temporary arrays is time-consuming. A total of 3 temporary arrays is needed:

1. temp1 = saturation_map(index_list)
2. temp2 = gray_image(index_list)
3. temp3 = temp1 ./ temp2

Then the FOR loop can be faster.

[EDITED]

#include "mex.h"

void mexFunction(int nlhs, mxArray *plhs[], 
                 int nrhs, const mxArray *prhs[])
{
  mwSize n_index, i, k;
  double *saturation_map, *gray_image, *index_list, m = 65535.0, t;

    saturation_map = mxgetPr(prhs[0]);
    gray_image     = mxGetPr(prhs[1]);
    index_list     = mxGetPr(prhs[2]);
    n_index        = mxGetNumberOfElements(prhs[2]);

    for (i = 0; i < n_index; i++) {
      k = (mwSize) index_list[i];
      t = saturation_map[k] / gray_image[k];
      if (t < m) {
        m = t;
      }
    }

    plhs[0] = mxCreateDoubleScalar(m);

    return;
  }

Save this as YourFcn.c, compile it using mex, then call it as:

m = YourFcn(saturation_map, gray_image, index_list);

If you find that it is fast enough, be suree to add checks for the type and number of inputs. Otherwise this function let your Matlab session crash in case of a wrong calling style.

[Saurabh]

My saturation_map, gray_image and index_list are very large. Does that mean that its better to use a for loop in this case ? In other words, speed can not be increased?

[Jan]

Most likely a C-Mex function will be faster. Do you have a C-compiler inatalled?

Please define "vey large" quantitatively. In this forum this term is used for 100kB and 4GB images.

[Andrei Bobrov]

+1

Answer 2

[Andrei Bobrov]

max_stretch_ratio = min(reshape(saturation_map./gray_image,[],1));

[Saurabh]

I only need to calculate this ratio for the indices specified in the index_list. If I do:

max_stretch_ratio = min(reshape(saturation_map(index_list) ./gray_image(index_list) ,[ ],1));

It takes even more time.

[Andrei Bobrov]

please see Jan's answer

[Saurabh]

I'll just reiterate the question to Jan: My saturation_map, gray_image and index_list are very large. Does that mean that its better to use a for loop in this case ? In other words, speed can not be increased?

[Andrei Bobrov]

try

max_stretch_ratio = min(saturation_map(index_list) ./gray_image(index_list));

[Saurabh]

I also did that :) It takes more time than the for loop

[Saurabh]

Time taken by for loop: 0.000003 sec

Time taken by our approach : 0.000011 sec (which is the same as my second approach in gthe original question)