Avoiding FOR loops to select a region in matrix and minimise computation time

Hello,

     I am trying to write a cross-correlation script where I need to slide my template across all rows and columns in the subject. Currently I am using nested FOR loops to select rows and columns every time I do a search. However, the computational time is quite high and I wanted to minimise it by avoiding FOR loops by any mean possible. For obvious reasons, I cannot publish my code yet. However, I can provide a pseudo code:

T = imread('template.png')
S = imread('subject.png')
[rowT, columnT] = size(T);

[rowS,columnS] = size(S);

coeff = zeros(size(S));  

for ii=0:(rowS-rowT)
    for jj = 0:(columnS - columnT)       

          ss = S(ii+1:rowT+ii,jj+1:columnT+jj);
          .
          .
          . 
          coeff(ii+1,jj+1) = (lambdaRo^2)*(lambdaGamma^2); 

      end
  end

Is there any way to avoid using for loops to select region of my subject image and speed the calculation time up? From my limited experience in Mathematics and MATLAB (compared to what the community users' experience is) I don't see how it is possible. Please help me out!!

Kind Regards,

[Björn]

Yes there is, you have to vectorize your script. I can show you how, but can you post the whole script? (at least including the complete for-loops)

[Mohammed Manna]

*Bjorn,

     Thanks for the response. Here is my script:*

    close all, clear all;
    clc;

    T = imread('T:/P7668/Manna/testTemplates/template_centred_1.png');
    % T = impyramid(T,'reduce');

    S = imread('T:/P7668/Manna/ssr_main_barrier/barrier_snapshot_1.png');  

    if size(S,3) > 1
        S = rgb2gray(S);
    end

    if size(T,3) > 1
        T = rgb2gray(T);
    end

    [rowT, columnT] = size(T);

    [rowS,columnS] = size(S);

    coeff = zeros(size(S));

    for ii=0:(rowS-rowT)
        for jj = 0:(columnS - columnT)        

            ss = S(ii+1:rowT+ii,jj+1:columnT+jj);

            rowProjectionS = sum(ss,2)/columnT;
            columnProjectionS = sum(ss,1)/rowT;

            rowProjectionT = sum(T,2)/columnT;
            columnProjectionT = sum(T,1)/rowT;

            meanT = mean(T(:));
            meanS = mean(ss(:));

            numeratorLambdaRo = sum((rowProjectionT-meanT).*(rowProjectionS - meanS));
            denominatorLambdaRo = sqrt( sum((rowProjectionT-meanT).^2) * sum((rowProjectionS-meanS).^2));
            lambdaRo = numeratorLambdaRo/denominatorLambdaRo;

            numeratorLambdaGamma = sum((columnProjectionT-meanT).*(columnProjectionS - meanS));
            denominatorLambdaGamma = sqrt( sum((columnProjectionT-meanT).^2) * sum((columnProjectionS-meanS).^2));
            lambdaGamma = numeratorLambdaGamma/denominatorLambdaGamma;

            coeff(ii+1,jj+1) = (lambdaRo^2)*(lambdaGamma^2); 

        end

    end

[Björn]

Ok, I do run into one little problem: I can't really find a way to create ss without a for-loop. The other calculations I can take outside the loop. But in order for making it faster that way, you must be sure that you will have enough RAM left. How much percent of your RAM is used while executing this script? If there is in total less then 50MB RAM left during the calculations, then that is the problem of the duration of your simulation. In that case you can easily solve it by converting your matrices to single-valued or maybe even 16- or 32-bit integers.

[Mohammed Manna]

how taking the cumulative sum of the columns and rows? And then using them to select a region? Does this sound sane? The reason I am saying this because I consulted a colleague of mine who says that this may be possible. But I rejected the idea simply because it didn't make sense to me. Does it make any sense for you?

I am getting really frustrated because I know that it will be simply 1-2 line changes in the code and everything will be hey presto! But I am really bad at Maths and trying to solve this problem since yesterday. thanks for your effort Bjorn :)

[Image Analyst]

Again, why not use xcorr2()? Though, I admit I didn't study your code. Do you have some kind of unusual custom correlation that doesn't do the same thing as the built-in function?

[Mohammed Manna]

Actually better!! I have got my own correlation implementation that is computationally a) cheap b) faster. I use cross-sectional histogram that is O(2n) rather than O(n^2). compared to normxcorr2 or xcorr2, it is about %20 faster...

Answer 1

[Image Analyst]

Why not use xcorr2()?