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:
Optimize this matrix process (alternative to sub2ind)

Subject: Optimize this matrix process (alternative to sub2ind)

From: Louis

Date: 16 Oct, 2010 16:30:07

Message: 1 of 7

Hello guys,

I thought my problem below is solved using sub2ind however it appears to be time consuming. It cost me 10 sec :S

Here is the bunch of the code that shows how many times sub2ind i am using. Based on the profile report, each line is iterated for about 59000 times. Also A in my case is a matrix of size 24x24...

Hence using this code, these sub2ind lines take around 10 seconds :S:S

Any help in optimizing this code is highly appreciated

A=[1 2 3 4 5;
   6 7 8 9 10;
   11 12 13 14 15;
   16 17 18 19 20];

x=[1;2;3]; % some desired 'x' index of matrix A
y=[2;4;4]; % some desired 'y' index of matrix A

fy = floor(y);
cy = ceil(y);
rx = round(x);
ry = round(y);
fx = floor(x);
cx = ceil(x);

ANDED=[1;0;1]; % obtained using some operation
% what I need is when ANDED=1, take the pixel of A(x,y) and do the operation and when
% ANDED=0, take the corresponding A(x,y) and do other operation

N(ANDED==1)=A(sub2ind(size(A),ry(ANDED==1),rx(ANDED==1)));
     
N(ANDED==0) = A(sub2ind(size(A),fy(ANDED==0),fx(ANDED==0))) + ...
               A(sub2ind(size(A),fy(ANDED==0),cx(ANDED==0))) + ...
               A(sub2ind(size(A),cy(ANDED==0),fx(ANDED==0))) + ...
               A(sub2ind(size(A),cy(ANDED==0),cx(ANDED==0)));


p.s. sorry for re-posting this question but it was blended in my previous post :)

regards,

Louis

Subject: Optimize this matrix process (alternative to sub2ind)

From: Roger Stafford

Date: 16 Oct, 2010 17:50:04

Message: 2 of 7

"Louis " <wlouis@ryerson.ca> wrote in message <i9cjuf$7qf$1@fred.mathworks.com>...
> Hello guys,
>
> I thought my problem below is solved using sub2ind however it appears to be time consuming. It cost me 10 sec :S
>
> Here is the bunch of the code that shows how many times sub2ind i am using. Based on the profile report, each line is iterated for about 59000 times. Also A in my case is a matrix of size 24x24...
>
> Hence using this code, these sub2ind lines take around 10 seconds :S:S
>
> Any help in optimizing this code is highly appreciated
>
> A=[1 2 3 4 5;
> 6 7 8 9 10;
> 11 12 13 14 15;
> 16 17 18 19 20];
>
> x=[1;2;3]; % some desired 'x' index of matrix A
> y=[2;4;4]; % some desired 'y' index of matrix A
>
> fy = floor(y);
> cy = ceil(y);
> rx = round(x);
> ry = round(y);
> fx = floor(x);
> cx = ceil(x);
>
> ANDED=[1;0;1]; % obtained using some operation
> % what I need is when ANDED=1, take the pixel of A(x,y) and do the operation and when
> % ANDED=0, take the corresponding A(x,y) and do other operation
>
> N(ANDED==1)=A(sub2ind(size(A),ry(ANDED==1),rx(ANDED==1)));
>
> N(ANDED==0) = A(sub2ind(size(A),fy(ANDED==0),fx(ANDED==0))) + ...
> A(sub2ind(size(A),fy(ANDED==0),cx(ANDED==0))) + ...
> A(sub2ind(size(A),cy(ANDED==0),fx(ANDED==0))) + ...
> A(sub2ind(size(A),cy(ANDED==0),cx(ANDED==0)));
>
>
> p.s. sorry for re-posting this question but it was blended in my previous post :)
>
> regards,
>
> Louis
- - - - - - - - -
  I would compute in advance as many quantities as possible before calculating N. There is no point in recomputing the same quantities over and over again. Also replace 'sub2ind' calls as done here.

 % When the size of A is known do this
 n = size(A,1);
 fxa = n*(fx-1);
 rxa = n*(rx-1);
 cxa = n*(cx-1);

 % When ANDED is introduced do this:
 t1 = ANDED==1; t0 = ANDED==0;
 N(t1) = A(ry(t1)+rxa(t1));
 fxa0 = fxa(t0); cxa0 = cxa(t0); fy0 = fy(t0); cy0 = cy(t0);
 N(t0) = A(fy0+fxa0)+A(fy0+cxa0)+A(cy0+fxa0)+A(cy0+cxa0);

Roger Stafford

Subject: Optimize this matrix process (alternative to sub2ind)

From: Matt J

Date: 16 Oct, 2010 18:23:03

Message: 3 of 7

"Louis " <wlouis@ryerson.ca> wrote in message <i9cjuf$7qf$1@fred.mathworks.com>...
>>
> N(ANDED==1)=A(sub2ind(size(A),ry(ANDED==1),rx(ANDED==1)));
====

This part can be computed by interp1() with 'nearest' neighbour interpolation option. There are probably even faster implementations on the File Exchange

      
> N(ANDED==0) = A(sub2ind(size(A),fy(ANDED==0),fx(ANDED==0))) + ...
> A(sub2ind(size(A),fy(ANDED==0),cx(ANDED==0))) + ...
> A(sub2ind(size(A),cy(ANDED==0),fx(ANDED==0))) + ...
> A(sub2ind(size(A),cy(ANDED==0),cx(ANDED==0)));
=====


For this part, you might consider doing a pre-check to see which x,y are integers. When they are integers fy=cy,cx=fx and you and up doing a lot of computations twice.

If x and y are never (or rarely) integers, this looks like a very brute force way of doing 2x2 local summation of pixels. If A is a fixed and unchanging matrix (or maybe even if it isn't) it would then be worthwhile to pre-compute all 2x2 summations of A by convolution

A2x2summed=conv2([1,1],[1,1],A,'valid'); %Note conv2 is a fast built-in

and then just do lookup into this matrix

idx=~ANDED;
N(idx)=A2x2Summed(sub2ind(size(A),fy(idx),fx(idx)));

Subject: Optimize this matrix process (alternative to sub2ind)

From: Matt J

Date: 16 Oct, 2010 18:41:03

Message: 4 of 7

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i9cqi7$6uu$1@fred.mathworks.com>...
> "Louis " <wlouis@ryerson.ca> wrote in message <i9cjuf$7qf$1@fred.mathworks.com>...
> >>
> > N(ANDED==1)=A(sub2ind(size(A),ry(ANDED==1),rx(ANDED==1)));
> ====
>
> This part can be computed by interp1() with 'nearest' neighbour interpolation option. There are probably even faster implementations on the File Exchange
=====

Sorry, I meant interp2 here.

And by the way, are you sure that for ANDED==0, you're not just trying to do linear interpolation of the 2x2 local set of pixels? If so, that changes the whole game.

Subject: Optimize this matrix process (alternative to sub2ind)

From: Louis

Date: 18 Oct, 2010 12:17:04

Message: 5 of 7

Thank you very much Roger and Matt...

Matt: i am actually doing bilinear interpolation :), how could this change the whole game :)...

Thanks

Louis

Subject: Optimize this matrix process (alternative to sub2ind)

From: Cris Luengo

Date: 18 Oct, 2010 12:43:04

Message: 6 of 7

"Louis " <wlouis@ryerson.ca> wrote in message <i9hds0$roh$1@fred.mathworks.com>...
> Thank you very much Roger and Matt...
>
> Matt: i am actually doing bilinear interpolation :), how could this change the whole game :)...
>
> Thanks
>
> Louis

Try using 'interp2' instead.

Subject: Optimize this matrix process (alternative to sub2ind)

From: Matt J

Date: 18 Oct, 2010 13:37:03

Message: 7 of 7

"Cris Luengo" <cris.luengo@google.for.my.name.to.contact.me> wrote in message <i9hfco$79a$1@fred.mathworks.com>...
> "Louis " <wlouis@ryerson.ca> wrote in message <i9hds0$roh$1@fred.mathworks.com>...
> > Thank you very much Roger and Matt...
> >
> > Matt: i am actually doing bilinear interpolation :), how could this change the whole game :)...
>
> Try using 'interp2' instead.

Or, check the FEX for fast equivalents

http://www.mathworks.com/matlabcentral/fileexchange/?term=interpolation+interp2

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