Vectorizing sums of different diagonals in a matrix

Question

I want to vectorize the following MATLAB code. I think it must be simple but I'm finding it confusing nevertheless.

r = some constant less than m or n
[m,n] = size(C);
S = zeros(m-r,n-r);
for i=1:m-r+1
    for j=1:n-r+1
        S(i,j) = sum(diag(C(i:i+r-1,j:j+r-1)));
    end
end

The code calculates a table of scores, S, for a dynamic programming algorithm, from another score table, C.
The diagonal summing is to generate scores for individual pieces of the data used to generate C, for all possible pieces (of size r).

Thanks in advance for any answers! Sorry if this one should be obvious...

Note
The built-in conv2 turned out to be faster than convnfft, because my eye(r) is quite small ( 5 <= r <= 20 ). convnfft.m states that r should be > 20 for any benefit to manifest.

Answer 1

I would think you might need to rearrange C into a 3D matrix before summing it along one of the dimensions. I'll post with an answer shortly.

EDIT

I didn't manage to find a way to vectorise it cleanly, but I did find the function accumarray, which might be of some help. I'll look at it in more detail when I am home.

EDIT#2

Found a simpler solution by using linear indexing, but this could be memory-intensive.

At C(1,1), the indexes we want to sum are 1+[0, m+1, 2*m+2, 3*m+3, 4*m+4, ... ], or (0:r-1)+(0:m:(r-1)*m)

sum_ind = (0:r-1)+(0:m:(r-1)*m);

create S_offset, an (m-r) by (n-r) by r matrix, such that S_offset(:,:,1) = 0, S_offset(:,:,2) = m+1, S_offset(:,:,3) = 2*m+2, and so on.

S_offset = permute(repmat( sum_ind, [m-r, 1, n-r] ), [1, 3, 2]);

create S_base, a matrix of base array addresses from which the offset will be calculated.

S_base = reshape(1:m*n,[m n]);
S_base = repmat(S_base(1:m-r,1:n-r), [1, 1, r]);

Finally, use S_base+S_offset to address the values of C.

S = sum(C(S_base+S_offset), 3);

You can, of course, use bsxfun and other methods to make it more efficient; here I chose to lay it out for clarity. I have yet to benchmark this to see how it compares with the double-loop method though; I need to head home for dinner first!

Answer 2

If I understand correctly, you're trying to calculate the diagonal sum of every subarray of C, where you have removed the last row and column of C (if you should not remove the row/col, you need to loop to m-r+1, and you need to pass the entire array C to the function in my solution below).

You can do this operation via a convolution, like so:

S = conv2(C(1:end-1,1:end-1),eye(r),'valid');

If C and r are large, you may want to have a look at CONVNFFT from the Matlab File Exchange to speed up calculations.

Answer 3

Based on the idea of JS, and as Jonas pointed out in the comments, this can be done in two lines using IM2COL with some array manipulation:

B = im2col(C, [r r], 'sliding');
S = reshape( sum( C(B(1:r+1:end,:)) ), size(C)-r+1 );

Basically B contains the indices of all sliding blocks of size r-by-r over the matrix C. Then we take the elements on the diagonal of each of these blocks C( B(1:r+1:end,:) ), compute their sum, and reshape the result to the expected size.

---

Comparing this to the convolution-based solution by Jonas, this does not perform any matrix multiplication, only indexing...