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:
How to speed up this For-Loop by a vector?

Subject: How to speed up this For-Loop by a vector?

From: Alex

Date: 13 May, 2011 14:20:20

Message: 1 of 5

Hi all,

i want to speed up a code, where i calculate a local standard deviation within another matrix.

e.g.:

mat1 = magic(100);
mat2 = zeros(100,100);

for i = 8:93
   for j = 8:93
    mat2(i,j) = std2(i-7:i+7,j-7:j+7)

   end
end

the code does exactly what i want, but is very slow. thats why im looking for a fast replacement.

i know how to adress the indices in a fast way an give them a fixed value
(
mat2(8:(size1-7),8:(size1-7)) = 5
)

but i dont know how to make a fast, dynamic, calculation depending on the position.

hope you may help me

thanks a lot

alex

Subject: How to speed up this For-Loop by a vector?

From: alistair templeton

Date: 13 May, 2011 15:14:05

Message: 2 of 5


>
> i want to speed up a code, where i calculate a local standard deviation within another matrix.

i don't know if it's any faster since i don't have std2, but you can express your standard deviation as a convolution:

mat1 = magic(100);
kernel = ones(15);

mat2 = sqrt(conv2(mat1.^2,kernel,'same'));



(double check this, it could be totally wrong)

Subject: How to speed up this For-Loop by a vector?

From: someone

Date: 13 May, 2011 15:33:05

Message: 3 of 5

"Alex" wrote in message <iqjen4$pr$1@newscl01ah.mathworks.com>...
> Hi all,
>
> i want to speed up a code, where i calculate a local standard deviation within another matrix.
>
> e.g.:
>
> mat1 = magic(100);
> mat2 = zeros(100,100);
>
> for i = 8:93
> for j = 8:93
> mat2(i,j) = std2(i-7:i+7,j-7:j+7)
>
> end
> end
>
> the code does exactly what i want, but is very slow. thats why im looking for a fast replacement.
>
> i know how to adress the indices in a fast way an give them a fixed value
> (
> mat2(8:(size1-7),8:(size1-7)) = 5
> )
>
> but i dont know how to make a fast, dynamic, calculation depending on the position.
>
> hope you may help me
>
> thanks a lot
>
> alex

I don't have the Image Processing Toolbox,
but the documentation says:

std2(A) computes the standard deviation of the array A using std(A(:))

If properly used (i.e., preallocation), for loops
are not NECESSARILY slower than vectorized code.
(It depends on many factors such as size of arrays, available memory, etc.)
Aside frrom the obvious typo in the above code:
mat2(i,j) = std2(i-7:i+7,j-7:j+7)
should be (I assume something like):
mat2(i,j) = std2(mat1(i-7:i+7),mat1(j-7:j+7)); % note the semicolon at the end
You could try moving some calculations from
from the inner loop to the outer loop
(something like):

for i = 8:93
   mat3 = mat1((i-7:i+7);
   for j = 8:93
    mat4 = mat1(j-7:j+7);
    mat2(i,j) = std([mat3(:);mat4(:)]); % note std instead of std2
   end
end

Just a thought

Subject: How to speed up this For-Loop by a vector?

From: Roger Stafford

Date: 14 May, 2011 03:33:04

Message: 4 of 5

"Alex" wrote in message <iqjen4$pr$1@newscl01ah.mathworks.com>...
> Hi all,
>
> i want to speed up a code, where i calculate a local standard deviation within another matrix.
>
> e.g.:
>
> mat1 = magic(100);
> mat2 = zeros(100,100);
>
> for i = 8:93
> for j = 8:93
> mat2(i,j) = std2(i-7:i+7,j-7:j+7)
> end
> end
> .........
> alex
- - - - - - - - - - - -
  What strikes me as inefficient is not your nested for-loops, but the fact that large portions of the standard deviation computation over the moving 15 by 15 square are being needlessly repeated in that method. That is, two adjacent 15 x 15 squares have 210 out of a total of 225 elements in common in their overlap area, and it is surely a waste of time to compute the standard deviation of each set of 225 independently of the other. Of course doing so will require a somewhat different, though equivalent, formula for the standard deviation.

  The following computes both the sums of elements (xs) and the sums of their squares (x2s) in the moving 15 x 15 square. By taking appropriate differences of 'cumsum', only a little more than four additions and four subtractions are required per 15 x 15 square in attaining the sums in these squares of their elements and their squares. The line computing 's' below gives the alternate standard deviation formula used with these two quantities.

 % The original data
 n = 100; % The size of the original square matrix
 m = 15; % Defines the m x m moving square within it
 x = randn(n); % Or whatever data you wish

 % The standard deviation computation
 t1 = cumsum([zeros(1,n);x],1);
 t2 = cumsum([zeros(n-m+1,1),t1(m+1:n+1,:)-t1(1:n-m+1,:)],2);
 xs = t2(:,m+1:n+1)-t2(:,1:n-m+1); % The sums of x over each square
 t1 = cumsum([zeros(1,n);x.^2],1);
 t2 = cumsum([zeros(n-m+1,1),t1(m+1:n+1,:)-t1(1:n-m+1,:)],2);
 x2s = t2(:,m+1:n+1)-t2(:,1:n-m+1); % The sums of x^2 over each square
 s = sqrt((x2s-xs.^2/m^2)/(m^2-1)); % Compute stan. dev. from xs & x2s

  The above only produces the nonzero 86 x 86 interior of mat2. To get your actual result in mat2, add on the following:

 mat2 = zeros(n);
 mat2(8:93,8:93) = s;

Roger Stafford

Subject: How to speed up this For-Loop by a vector?

From: Alex

Date: 14 May, 2011 08:54:20

Message: 5 of 5

Thanks to all.
I will test the code later and reply you then.

Best regards,

Alex

Tags for this Thread

No tags are associated with 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