Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Vectorization of Nested For Loop

Subject: Vectorization of Nested For Loop

From: Pallavi

Date: 3 Aug, 2011 07:47:08

Message: 1 of 6

Hi Everyone

I would really be grateful if someone could tell me how do i vectorize the code below, I am working with very large images due to which its taking hours together for me to get the output in matlab.

The code below is basically needs to be optimized how should i do it

Thanks in advance


I=imread('image1.bmp') % image size 512X512
[row col byt]=size(I); % finding size of the image

block_col=im2col(I,[bs bs], 'Sliding'); % divding the image into blocks
[rowB colB]=size(block_col);

% converting the blocks of the image into a array named block_array
k=1;
l=1;
block_array=zeros([3500 70]);
% NESTED FOR LOOP WHICH I NEED TO VECTORIZE SO THAT IT GIVES ME FASTER %OUTPUT

for i=1:colB
    l=1;
    for j=1:rowB
        block_array(k,l)= block_col(j,i);
        l=l+1;
    end
    k=k+1;
end

row_block_array=k-1;
col_block_array=l-1;

% storing the index positions of each block in the array named block_array
z=1;
for i=1:row-bs+1
    for j=1:col-bs+1
        block_array(z,col_block_array+1)=i;
        block_array(z,col_block_array+2)=j;
        z=z+1;
    end
end

Subject: Vectorization of Nested For Loop

From: Scott

Date: 3 Aug, 2011 14:59:29

Message: 2 of 6

"Pallavi " <pallavi.halarnkar@gmail.com> wrote in message <j1auds$373$1@newscl01ah.mathworks.com>...
> Hi Everyone
>
> I would really be grateful if someone could tell me how do i vectorize the code below, I am working with very large images due to which its taking hours together for me to get the output in matlab.
>
> The code below is basically needs to be optimized how should i do it
>
> Thanks in advance
>
>
> I=imread('image1.bmp') % image size 512X512
> [row col byt]=size(I); % finding size of the image
>
> block_col=im2col(I,[bs bs], 'Sliding'); % divding the image into blocks
> [rowB colB]=size(block_col);
>
> % converting the blocks of the image into a array named block_array
> k=1;
> l=1;
> block_array=zeros([3500 70]);
> % NESTED FOR LOOP WHICH I NEED TO VECTORIZE SO THAT IT GIVES ME FASTER %OUTPUT
>
> for i=1:colB
> l=1;
> for j=1:rowB
> block_array(k,l)= block_col(j,i);
> l=l+1;
> end
> k=k+1;
> end
>
> row_block_array=k-1;
> col_block_array=l-1;
>
> % storing the index positions of each block in the array named block_array
> z=1;
> for i=1:row-bs+1
> for j=1:col-bs+1
> block_array(z,col_block_array+1)=i;
> block_array(z,col_block_array+2)=j;
> z=z+1;
> end
> end

Pallavi,

That looks like it could be vectorized but my current understanding is that loops are just as fast as vectorized code due to the just-in-time (JIT) accelerator. I am not sure you will realize any additional speed.

Scott

Subject: Vectorization of Nested For Loop

From: Michael

Date: 3 Aug, 2011 16:03:28

Message: 3 of 6


> for i=1:colB
> l=1;
> for j=1:rowB
> block_array(k,l)= block_col(j,i);
> l=l+1;
> end
> k=k+1;
> end
>
> row_block_array=k-1;
> col_block_array=l-1;
>


Accessing arrays with the index in the wrong order is extremely slow on most systems. Can you rearrange the problem so that block_array is accessed along its inner dimension (k in this case) rather then its outer dimension (j)?

Subject: Vectorization of Nested For Loop

From: arich82

Date: 3 Aug, 2011 18:07:26

Message: 4 of 6

"Pallavi " <pallavi.halarnkar@gmail.com> wrote in message <j1auds$373$1@newscl01ah.mathworks.com>...

> I=imread('image1.bmp') % image size 512X512
> [row col byt]=size(I); % finding size of the image
>
> block_col=im2col(I,[bs bs], 'Sliding'); % divding the image into blocks
> [rowB colB]=size(block_col);
>
> % converting the blocks of the image into a array named block_array
> k=1;
> l=1;
> block_array=zeros([3500 70]);
> % NESTED FOR LOOP WHICH I NEED TO VECTORIZE SO THAT IT GIVES ME FASTER %OUTPUT
>
> for i=1:colB
> l=1;
> for j=1:rowB
> block_array(k,l)= block_col(j,i);
> l=l+1;
> end
> k=k+1;
> end


Maybe I'm misunderstanding something, but isn't this the same as saying 'l' grows exactly like 'j', and resets for each new 'i', and 'k' grows exactly like 'i'. The first loop should be equivalent to:
>> block_array(i,j)= block_col(j,i);
which is trivially 'vectorized' by the transpose function, correct?

block_array = block_col.';
block_array(3500, 70) = 0; % if zero padding is needed


Can row_block_array and col_block_array ever be anything different from colB and rowB, respectively?

The next loop appears to append two columns to your results, but again, 'z' is just the linear index for 'i' and 'j', so

m = (row-bs+1);
n = (col-bs+1);

I = [1:m];
I = I(ones(n, 1), :); %repmat;

J = [1:n];
J = J(ones(m, 1), :).'; % note transpose

block_array([1:m*n], [(rowB+1):(rowB+2)]) = [I(:), J(:)];


My guess is 'im2col' is actually the bottle (check the profiler), so eliminating the loops might not gain you much. Let me know if this works for you, however.


--Andy

Subject: Vectorization of Nested For Loop

From: Florin Neacsu

Date: 3 Aug, 2011 18:13:28

Message: 5 of 6

"Pallavi " <pallavi.halarnkar@gmail.com> wrote in message <j1auds$373$1@newscl01ah.mathworks.com>...
> Hi Everyone
>
> I would really be grateful if someone could tell me how do i vectorize the code below, I am working with very large images due to which its taking hours together for me to get the output in matlab.
>
> The code below is basically needs to be optimized how should i do it
>
> Thanks in advance
>
>
> I=imread('image1.bmp') % image size 512X512
> [row col byt]=size(I); % finding size of the image
>
> block_col=im2col(I,[bs bs], 'Sliding'); % divding the image into blocks
> [rowB colB]=size(block_col);
>
> % converting the blocks of the image into a array named block_array
> k=1;
> l=1;
> block_array=zeros([3500 70]);
> % NESTED FOR LOOP WHICH I NEED TO VECTORIZE SO THAT IT GIVES ME FASTER %OUTPUT
>
> for i=1:colB
> l=1;
> for j=1:rowB
> block_array(k,l)= block_col(j,i);
> l=l+1;
> end
> k=k+1;
> end
>
> row_block_array=k-1;
> col_block_array=l-1;
>
> % storing the index positions of each block in the array named block_array
> z=1;
> for i=1:row-bs+1
> for j=1:col-bs+1
> block_array(z,col_block_array+1)=i;
> block_array(z,col_block_array+2)=j;
> z=z+1;
> end
> end

Hello,

> % NESTED FOR LOOP WHICH I NEED TO VECTORIZE SO THAT IT GIVES ME FASTER %OUTPUT
>
> for i=1:colB
> l=1;
> for j=1:rowB
> block_array(k,l)= block_col(j,i);
> l=l+1;
> end
> k=k+1;
> end

Am I missing something or you are doing just a transpose?
in that case
>block_array=block_col';
should be enough.

Regards,
Florin

Subject: Vectorization of Nested For Loop

From: Pallavi

Date: 4 Aug, 2011 07:29:11

Message: 6 of 6

Thank you very much for the reply, cant believe the code has really helped me in reducing the time

pls if u dont mind there is another bottleneck in the code given below can u pls help me in removing the same

i m calculating phase correlation of two arrays and the size of the array is so large that its taking a long time

Thanks once again

% code follows
[rowA colA]=size(blockA);
[rowB colB]=size(blockB);

blockA=double(blockA);
blockB=double(blockB);

m=1;
flag=0;
blockC=zeros([500 4]);

for i=1:rowA
    for j=1:rowB
   
 fi = fft2(blockA(i,1:bs*bs));
 fr = fft2(blockB(j,1:bs*bs));
% perform phase correlation (amplitude is normalized)
 fc = fi .* conj(fr);
 fcn = fc ./ abs(fc);
 c1 = real(ifft2(fcn));
 
 % find the peak in the correlation plane
 [v index] = max(c1(:));

 if v>0.7
     blockC(m,1)=blockB(j,bs*bs+1);
     blockC(m,2)=blockB(j,bs*bs+2);
     blockC(m,3)=v;
     blockC(m,4)=2;
     flag=1;
     m=m+1;
  end
 
  end
    if flag==1
     blockC(m,1)=blockA(i,bs*bs+1);
     blockC(m,2)=blockA(i,bs*bs+2);
     blockC(m,3)=v;
     blockC(m,4)=1;
     m=m+1;
    flag=0;
    end

"arich82" wrote in message <j1c2ou$h2o$1@newscl01ah.mathworks.com>...
> "Pallavi " <pallavi.halarnkar@gmail.com> wrote in message <j1auds$373$1@newscl01ah.mathworks.com>...
>
> > I=imread('image1.bmp') % image size 512X512
> > [row col byt]=size(I); % finding size of the image
> >
> > block_col=im2col(I,[bs bs], 'Sliding'); % divding the image into blocks
> > [rowB colB]=size(block_col);
> >
> > % converting the blocks of the image into a array named block_array
> > k=1;
> > l=1;
> > block_array=zeros([3500 70]);
> > % NESTED FOR LOOP WHICH I NEED TO VECTORIZE SO THAT IT GIVES ME FASTER %OUTPUT
> >
> > for i=1:colB
> > l=1;
> > for j=1:rowB
> > block_array(k,l)= block_col(j,i);
> > l=l+1;
> > end
> > k=k+1;
> > end
>
>
> Maybe I'm misunderstanding something, but isn't this the same as saying 'l' grows exactly like 'j', and resets for each new 'i', and 'k' grows exactly like 'i'. The first loop should be equivalent to:
> >> block_array(i,j)= block_col(j,i);
> which is trivially 'vectorized' by the transpose function, correct?
>
> block_array = block_col.';
> block_array(3500, 70) = 0; % if zero padding is needed
>
>
> Can row_block_array and col_block_array ever be anything different from colB and rowB, respectively?
>
> The next loop appears to append two columns to your results, but again, 'z' is just the linear index for 'i' and 'j', so
>
> m = (row-bs+1);
> n = (col-bs+1);
>
> I = [1:m];
> I = I(ones(n, 1), :); %repmat;
>
> J = [1:n];
> J = J(ones(m, 1), :).'; % note transpose
>
> block_array([1:m*n], [(rowB+1):(rowB+2)]) = [I(:), J(:)];
>
>
> My guess is 'im2col' is actually the bottle (check the profiler), so eliminating the loops might not gain you much. Let me know if this works for you, however.
>
>
> --Andy

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us