MATLAB Central Newsreader - Re: HOWTO: Accelerate processing algorithm

Re: HOWTO: Accelerate processing algorithm

Jose Antonio — Sun, 05 Jul 2009 14:06:21 -0400

Ok, I think this makes it

S = accumarray(y(:)+1,v(:), [], @mean)

Re: HOWTO: Accelerate processing algorithm

Bruno Luong — Sun, 05 Jul 2009 14:25:02 -0400

Jose Antonio <juriguen@gmail.com> wrote in message <14646834.75779.1246802812202.JavaMail.jakarta@nitrogen.mathforum.org>...
> Ok, I think this makes it
>
> S = accumarray(y(:)+1,v(:), [], @mean)

Jose,

I believe the above might be not the fastest, this could be even faster:

yp1 = y(:)+1;
S = accumarray(yp1,v(:))./accumarray(yp1,1);

accumarray likes to work with 'sum'. Just a though

Bruno

Re: HOWTO: Accelerate processing algorithm

Jose Antonio — Sun, 05 Jul 2009 14:55:47 -0400

Very good point Bruno

It does actually perform much faster. Using @mean I increased from 2s to 4s, and with your new advice, again back to 2.5s

Thans!

Re: HOWTO: Accelerate processing algorithm

Rune Allnor — Sun, 05 Jul 2009 15:48:19 -0400

On 5 Jul, 16:25, "Bruno Luong" <b.lu...@fogale.findmycountry> wrote:

> yp1 = y(:)+1;
> S = accumarray(yp1,v(:))./accumarray(yp1,1);
>
> accumarray likes to work with 'sum'. Just a though

I tried to figure out what ACCUMARRAY does, but let's
say the documentation leaves more questions than it
answers.

Exactly what does the lines above do? In as plain English
as possible, please.

Rune

Re: HOWTO: Accelerate processing algorithm

Bruno Luong — Sun, 05 Jul 2009 16:04:02 -0400

Rune,

In short, ACCUMARRAY does for nd-array what SPARSE does for sparse matrix. It accumulates the vector elements (second input argument) depending on where they are located on a 'cell' (defined by the first input argument of subindexes).

The subindex/vector might come in random order and arbitrary length. ACCUMARRAY just add them together on each cell. The sum result is then retuned as the array, each element corresponds to a 'cell'.

The "adding" behavior can be changed by passing a use function handle (such as @mean).

Bruno

Re: HOWTO: Accelerate processing algorithm

Jose Antonio — Sun, 05 Jul 2009 16:17:45 -0400

Hi!

This
S = accumarray(yp1, v(:))./accumarray(yp1,1);

Is equivalent to
S = accumarray(yp1, v(:), [], @mean)

Regarding the documentation, I have to admit it is also quite weird to me.

What I wanted to do was to obtain an array, S, whose indices are specified by yp1, formed as the average of the values in v which are equal to the indices.

For that purpose
accumarray([1 1 3 2 2 5].', [1 2 3 4 5 6].')
1 -> 1 + 2
2 -> 4 + 5
3 -> 3
4
5 -> 6

And if you specify @fun, it performs any operation with the grouped elements
accumarray([1 1 3 2 2 5].', [1 2 3 4 5 6].', [], @fun)
1 -> fun(1,2)
2 -> fun(4,5)
3 -> fun(3)
4
5 -> fun(6)

The final suggestion by Bruno basically performs the mean of the groups, because it gathers on one hand the elements of v and on the other all 1s, and sums the contents.
accumarray([1 1 3 2 2 5].', [1 2 3 4 5 6].')
accumarray([1 1 3 2 2 5].', [1 1 1 1 1 1].')
1 -> 1 + 2 1 + 1
2 -> 4 + 5 1 + 1
3 -> 3 1
4 0
5 -> 6 1

It has worked fine for me, but explaining it to you now I have just realized that there might be a problem with 0/0.

Hope it helps!
Jose

Re: HOWTO: Accelerate processing algorithm

Bruno Luong — Sun, 05 Jul 2009 16:28:01 -0400

Here is a code to show what ACCUMARRAY does:

% Generate test data
m = 10;
nd = 3;
sidx=ceil(4*rand(m,3)); % must be integers
v=rand(m,1);

% ACCUMARRAY DOES THIS
sz = max(sidx,[],1);
res = zeros(sz);
for k=1:m
    sk = sidx(k,:);
    sk = num2cell(sk);
    res(sk{:}) = res(sk{:}) + v(k,1);
end

% Check
isequal(accumarray(sidx, v), res) % OK 1

% Bruno

Re: HOWTO: Accelerate processing algorithm

Jose Antonio — Sun, 05 Jul 2009 16:28:15 -0400

Ok, easy enough

S(isnan(S)) = 0

solves the problem, and allows to get the same result returned by @mean, but much faster!

Jose

Re: HOWTO: Accelerate processing algorithm

Bruno Luong — Sun, 05 Jul 2009 16:33:01 -0400

> I have just realized that there might be a problem with 0/0.

You can specify the default value; if you prefer the accumarray-mean to return 0 for empty set; then call

S = accumarray(yp1,v(:))./accumarray(yp1,1,[],[],1);

Personally I prefer NaN for such case.

% Bruno

Re: HOWTO: Accelerate processing algorithm

Jose Antonio — Sun, 05 Jul 2009 16:57:20 -0400

Thanks again!

It always appears to be an easier / faster way to do things than I find out! :) Jaja

Re: HOWTO: Accelerate processing algorithm

Rune Allnor — Sun, 05 Jul 2009 18:15:41 -0400

On 5 Jul, 18:04, "Bruno Luong" <b.lu...@fogale.findmycountry> wrote:
> Rune,
>
> In short, ACCUMARRAY does for nd-array what SPARSE does for sparse matrix. It accumulates the vector elements (second input argument) depending on where they are located on a 'cell' (defined by the first input argument of subindexes).

So the OP's code essentially builds a histogram
from the images? If so, I tested a couple of variants
of building histograms some time ago:

http://groups.google.no/group/comp.soft-sys.matlab/msg/0b6492cb37b5d7fd?hl=no

If you do things 'properly', you can easily speed things
up a factor >10, using C++ instead of ACCUMARRAY.

If this is a 'naive' grey-scale histogram, things might
be simplified a lot more, with maybe another factor 5-10
faster.

Rune