Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: How to speed up this For-Loop by a vector?
Date: Sat, 14 May 2011 03:33:04 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 42
Message-ID: <iqkt5g$nc$1@newscl01ah.mathworks.com>
References: <iqjen4$pr$1@newscl01ah.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: www-03-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: newscl01ah.mathworks.com 1305343984 748 172.30.248.48 (14 May 2011 03:33:04 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sat, 14 May 2011 03:33:04 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:726743

"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