Самый быстрый способ вычисления суммы подматрицы

Question

Какой самый быстрый способ вычисления суммы подматрицы? В настоящее время я буду об этом следующим образом:

x = [1  2  3  4 
    1  2  3  4 
    1  2  3  4 
    1  2  3  4] 

>> y = x(1:2, 1:2); 
>> y 

y = 

    1  2 
    1  2 

>> sum(y(:)) 

ans = 

    6 

>> 

Как я могу вычислить сумму всех подматриц x?

Редактировать

В каждой точке (х, у) в матрице, я хочу, чтобы вычислить сумму для окна размером 2M + 1. Например, если у меня есть матрица 4x4, я хочу вычислить суммы для окон 3x3 в каждой точке, где это возможно (например, было бы невозможно для краев, потому что окно вытекло из матрицы)

for i = M:ncols-M 
    for j=M:nrows-M 

    end 
end 

Пример Для матрицы 4х4 с размером окна 3, я хотел бы эти суммы:

суммы центрированной в точке (2,2)

+ + + x 
+ + + x 
+ + + x 
x x x x 

суммы с центром в точке (3,2)

x + + + 
x + + + 
x + + + 
x x x x 

сумма с центром в точке (2,3)

x x x x 
+ + + x 
+ + + x 
+ + + x 

сумма с центром в точке (3,3)

x x x x 
x + + + 
x + + + 
x + + + 

Answer 1

Этот ответ был создан до разъяснений ОП. Предполагается, что подматрицы не перекрываются!

---

Если у вас есть Image Processing Toolbox вы можете использовать blockproc:

A = blockproc(x,[2 2],@(k) sum(k.data(:))) 

Если вы не имеете его, вы можете использовать accumarray:

n = 2;    %// number of elements per block in row direction 
N = size(x,1)/n; %// number of blocks in row direction 
m = 2;    %// number of elements per block in column direction 
M = size(x,2)/m; %// number of blocks in column direction 

idx = repelem(reshape(1:(N*M),N,M),n,m) 
B = reshape(accumarray(x(:),idx(:)), N, M) 

Некоторые тяжелые изменения формы также будут работать:

C = reshape(sum(reshape(permute(sum(reshape(x,n,m,[])),[2,3,1]).',n,[])),n,[]).' 

---

A = B = C = 

    6 14 
    6 14 

Answer 2

Вы смотрите на вычисление summed area table. Проще говоря, каждый элемент в строке i и столбец j - (i,j) - на выходе есть сумма подматрицы, ограниченной от верхнего левого угла до интересующего пункта (i,j), который служит в нижнем правом углу.

Это очень просто с cumsum:

y = cumsum(cumsum(x, 1), 2); 

Пример:

>> x = repmat(1:4, 4, 1); %// your example 
>> x 

x = 

    1  2  3  4 
    1  2  3  4 
    1  2  3  4 
    1  2  3  4 

... и выход:

>> y = cumsum(cumsum(x, 1), 2) 

y = 

    1  3  6 10 
    2  6 12 20 
    3  9 18 30 
    4 12 24 40 

Таким образом, для примера, сумма подматрицы от верхнего левого угла до (i,j) = (2,2) равен 6.

Answer 3

x = repmat(1:4, 4, 1); %// your example 
[A,B] = size(x); 
kk=1; 
for ii = 1:2:A 
    for jj = 1:2:B 
     subsummed(kk) = sum(sum(x(ii:ii+1,jj:jj+1))); 
     kk = kk+1; 
    end 
end 

Моя петлевая версия, если вы имеете в виду «подматрицу» в случае четырех матриц 2x2, которые составляют ваш полный.

Answer 4

Если под "подматрицы" вы имеете в виду скольжения 2D-окно фиксированного размера, что в сущности 2D-свертка:

x = [1  2  3  4 
    1  2  3  4 
    1  2  3  4 
    1  2  3  4]; 
m = 2; n = 2; %// submatrix size 
result = conv2(x, ones(m, n), 'valid'); 

В этом примере

result = 
    6 10 14 
    6 10 14 
    6 10 14