Improving Speed and Reducing Memory Consumption with Creation of 2D Sparse Convolution Matrix

1 次查看（过去 30 天）
Royi Avital
Royi Avital 2019-1-22
评论： Royi Avital 2019-1-23
In a previous question of mine, Creating Convolution Matrix of 2D Kernel for Different Shapes of Convolution, among answers of the great Matt I came up with the following code:
function [ mK ] = CreateConvMtx2DSparse( mH, numRows, numCols, convShape )
CONVOLUTION_SHAPE_FULL = 1;
CONVOLUTION_SHAPE_SAME = 2;
CONVOLUTION_SHAPE_VALID = 3;
numColsKernel = size(mH, 2);
numBlockMtx = numColsKernel;
cBlockMtx = cell(numBlockMtx, 1);
for ii = 1:numBlockMtx
cBlockMtx{ii} = CreateConvMtxSparse(mH(:, ii), numRows, convShape);
end
switch(convShape)
case(CONVOLUTION_SHAPE_FULL)
% For convolution shape - 'full' the Doubly Block Toeplitz Matrix
% has the first column as its main diagonal.
diagIdx = 0;
numRowsKron = numCols + numColsKernel - 1;
case(CONVOLUTION_SHAPE_SAME)
% For convolution shape - 'same' the Doubly Block Toeplitz Matrix
% has the first column shifted by the kernel horizontal radius.
diagIdx = floor(numColsKernel / 2);
numRowsKron = numCols;
case(CONVOLUTION_SHAPE_VALID)
% For convolution shape - 'valid' the Doubly Block Toeplitz Matrix
% has the first column shifted by the kernel horizontal length.
diagIdx = numColsKernel - 1;
numRowsKron = numCols - numColsKernel + 1;
end
vI = ones(min(numRowsKron, numCols), 1);
mK = kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{1});
for ii = 2:numBlockMtx
diagIdx = diagIdx - 1;
mK = mK + kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{ii});
end
end
The code is running pretty fast.
But I think there might be ways to improve it farther, specifically in the following lines:
vI = ones(min(numRowsKron, numCols), 1);
mK = kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{1});
for ii = 2:numBlockMtx
diagIdx = diagIdx - 1;
mK = mK + kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{ii});
end
This code snippet basically creates a block matrix form the sparse matrices in the cell array cBlockMtx. Where the diagonal of the first element in cBlockMtx is defiend by diagIdx.
Is there a more efficient way to generate this matrix? The main issue is that each time generating kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{ii}) requires a lot of memory.
  2 个评论
Royi Avital
Royi Avital 2019-1-23
Well, I tried this:
function [ mK ] = CreateConvMtx2DI( mH, numRows, numCols, convShape )
CONVOLUTION_SHAPE_FULL = 1;
CONVOLUTION_SHAPE_SAME = 2;
CONVOLUTION_SHAPE_VALID = 3;
numColsKernel = size(mH, 2);
numBlockMtx = numColsKernel;
cBlockMtx = cell(numBlockMtx + 1, 1);
for ii = 1:numBlockMtx
cBlockMtx{ii} = CreateConvMtx1D(mH(:, ii), numRows, convShape);
end
cBlockMtx{numBlockMtx + 1} = sparse([], [], [], size(cBlockMtx{numBlockMtx}, 1), size(cBlockMtx{numBlockMtx}, 2), 0);
switch(convShape)
case(CONVOLUTION_SHAPE_FULL)
% For convolution shape - 'full' the Doubly Block Toeplitz Matrix
% has the first column as its main diagonal.
diagIdx = 0;
numRowsKron = numCols + numColsKernel - 1;
case(CONVOLUTION_SHAPE_SAME)
% For convolution shape - 'same' the Doubly Block Toeplitz Matrix
% has the first column shifted by the kernel horizontal radius.
diagIdx = floor(numColsKernel / 2);
numRowsKron = numCols;
case(CONVOLUTION_SHAPE_VALID)
% For convolution shape - 'valid' the Doubly Block Toeplitz Matrix
% has the first column shifted by the kernel horizontal length.
diagIdx = numColsKernel - 1;
numRowsKron = numCols - numColsKernel + 1;
end
vC = (numBlockMtx + 1) * ones(numRowsKron, 1);
vR = (numBlockMtx + 1) * ones(numCols, 1);
vC(1:(numBlockMtx - diagIdx)) = (diagIdx + 1):numBlockMtx;
vR(1:(diagIdx + 1)) = (diagIdx + 1):-1:1;
mK = cell2mat(cBlockMtx(toeplitz(vC, vR)));
end
Namely I replaced:
vI = ones(min(numRowsKron, numCols), 1);
mK = kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{1});
for ii = 2:numBlockMtx
diagIdx = diagIdx - 1;
mK = mK + kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{ii});
end
With:
vC = (numBlockMtx + 1) * ones(numRowsKron, 1);
vR = (numBlockMtx + 1) * ones(numCols, 1);
vC(1:(numBlockMtx - diagIdx)) = (diagIdx + 1):numBlockMtx;
vR(1:(diagIdx + 1)) = (diagIdx + 1):-1:1;
mK = cell2mat(cBlockMtx(toeplitz(vC, vR)));
It turned out to be slower (x2 slower). So I will be happy to have another idea...

请先登录，再进行评论。

请先登录，再回答此问题。

回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Creating and Concatenating Matrices 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by