Vectorisation sommes de différentes diagonales dans une matrice

Question

Je veux vectoriser le code suivant Matlab. Je pense que ce doit être simple, mais je trouve qu'il est source de confusion quand même.

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

Le code calcule un tableau de scores, S , pour un algorithme de programmation dynamique, d'une autre table de partition, C .
La sommation diagonale est de générer des scores pour les pièces individuelles des données utilisées pour générer C , pour toutes les pièces possibles (r) de la taille.

Merci d'avance pour toutes les réponses! Désolé si celui-ci devrait être évident ...

Remarque Le haut-conv2 avéré être plus rapide que convnfft, parce que mon oeil (r) est assez petit (5 <= r <= 20). Etats convnfft.m que r doit être> 20 pour tout avantage à se manifester.

Answer 1

Si je comprends bien, vous essayez de calculer la somme diagonale de chaque sous-tableau de C, où vous avez supprimé la dernière ligne et la colonne C (si vous ne devriez pas supprimer la ligne / colonne, vous devez boucle m-r + 1, et vous devez passer l'ensemble du réseau C à la fonction dans ma solution ci-dessous).

Vous pouvez effectuer cette opération via un convolution , comme suit:

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

Si C et R sont grandes, vous voudrez peut-être jeter un oeil à CONVNFFT de la Bourse de fichiers Matlab pour accélérer les calculs.

Answer 2

Basé sur l'idée de JS , et comme Jonas sur dans les commentaires pointu, cela peut se faire en deux lignes en utilisant IM2COL avec une certaine manipulation de tableau:

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

Fondamentalement B contient les éléments de tous les blocs coulissants de taille r par r sur la matrice C. Ensuite, nous prenons les éléments sur la diagonale de chacun de ces blocs B(1:r+1:end,:), calculer leur somme, et remodeler le résultat à la taille attendue.

---

compare à la solution à convolution par Jonas, cela ne fonctionne pas une multiplication matricielle, l'indexation ne ...

Answer 3

Je pense que vous pourriez avoir besoin de réorganiser C dans une matrice 3D avant de les additionner le long d'une des dimensions. Je vais poster une réponse sous peu.

EDIT

Je ne l'ai pas réussi à trouver un moyen de vectoriser il propre, mais j'ai trouvé la fonction accumarray, ce qui pourrait être d'une certaine aide. Je vais regarder plus en détail quand je suis à la maison.

EDIT # 2

Trouver une solution plus simple en utilisant l'indexation linéaire, mais cela pourrait être gourmand en mémoire.

A C (1,1), les indices que nous voulons somme 1+ sont [0, m + 1, m + 2 * 2, * 3 m + 3, 4 * m + 4, ...], ou (0: r-1) + (0: m: (r-1) * m)

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

créer S_offset, un par matrice de r, de telle sorte que S_offset (mr) de (nr) (:,:, 1) = 0, S_offset (:,:, 2) = m + 1, S_offset (:,:, 3) = 2 * m + 2, et ainsi de suite.

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

créer S_base, une matrice d'adresses de réseau de base à partir de laquelle le décalage sera calculé.

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

Enfin, l'utilisation S_base+S_offset pour répondre aux valeurs de C.

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

Vous pouvez, bien sûr, l'utilisation bsxfun et d'autres méthodes pour le rendre plus efficace; ici j'ai choisi de poser pour plus de clarté. Je n'ai pas encore de référence ceci pour voir comment il se compare avec la méthode à double boucle bien; Je dois la maison de la tête pour le dîner d'abord!

Answer 4

Est-ce que vous cherchez? Cette fonction ajoute les diagonales et les met eux dans un vecteur semblable à la façon dont la fonction « somme » ajoute toutes les colonnes dans une matrice et les met dans un vecteur.

function [diagSum] = diagSumCalc(squareMatrix, LLUR0_ULLR1)
% 
% Input: squareMatrix: A square matrix.
%        LLUR0_ULLR1:  LowerLeft to UpperRight addition = 0     
%                      UpperLeft to LowerRight addition = 1
% 
% Output: diagSum: A vector of the sum of the diagnols of the matrix.
% 
% Example: 
% 
% >> squareMatrix = [1 2 3; 
%                    4 5 6;
%                    7 8 9];
% 
% >> diagSum = diagSumCalc(squareMatrix, 0);
% 
% diagSum = 
% 
%       1 6 15 14 9
% 
% >> diagSum = diagSumCalc(squareMatrix, 1);
% 
% diagSum = 
% 
%       7 12 15 8 3
% 
% Written by M. Phillips
% Oct. 16th, 2013
% MIT Open Source Copywrite
% Contact mphillips@hmc.edu fmi.
% 

if (nargin < 2)
    disp('Error on input. Needs two inputs.');
    return;
end

if (LLUR0_ULLR1 ~= 0 && LLUR0_ULLR1~= 1)
    disp('Error on input. Only accepts 0 or 1 as input for second condition.');
    return;
end

[M, N] = size(squareMatrix);

if (M ~= N)
    disp('Error on input. Only accepts a square matrix as input.');
    return;
end

diagSum = zeros(1, M+N-1);

if LLUR0_ULLR1 == 1
    squareMatrix = rot90(squareMatrix, -1);
end

for i = 1:length(diagSum)
    if i <= M
        countUp = 1;
        countDown = i;
        while countDown ~= 0
            diagSum(i) = squareMatrix(countUp, countDown) + diagSum(i);
            countUp = countUp+1;
            countDown = countDown-1;
        end
    end
    if i > M
        countUp = i-M+1;
        countDown = M;
        while countUp ~= M+1
            diagSum(i) = squareMatrix(countUp, countDown) + diagSum(i);
            countUp = countUp+1;
            countDown = countDown-1;
        end
    end
end

Vive