Problem 44832. Generate Convolution Matrix of 2D Kernel with Different Convolution Shapes (Full, Same, Valid)

Created by Royi Avital

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>In this problem the challenge is to build the Matrix Form equivalent of the function `conv2()` of MATLAB.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The function to be built will generate a sparse matrix `mK` which is the convolution matrix of the 2D Kernel 'mH' (Which is an input to the function). The input to the function is the 2D Kernel and dimensions of the image to apply the convolution upon and the shape of the convolution ('full', 'same', 'valid' as in 'conv2()').</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The output sparse matrix should match the output of using 'conv2()' on the same image using the same convolution shape.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For instance:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[CONVOLUTION_SHAPE_FULL = 1;\nCONVOLUTION_SHAPE_SAME = 2;\nCONVOLUTION_SHAPE_VALID = 3;\n\nnumRowsImage = 100;\nnumColsImage = 80;\n\nnumRowsKernel = 7;\nnumColsKernel = 5;\n\nmI = rand(numRowsImage, numColsImage);\nmH = rand(numRowsKernel, numColsKernel);\n\nmaxThr = 1e-9;\n\n%%Full Convolution\n\nconvShape = CONVOLUTION_SHAPE_FULL;\n\nnumRowsOut = numRowsImage + numRowsKernel - 1;\nnumColsOut = numColsImage + numColsKernel - 1;\n\nmORef = conv2(mI, mH, 'full');\nmK = CreateImageConvMtx(mH, numRowsImage, numColsImage, convShape);\nmO = reshape(mK * mI(:), numRowsOut, numColsOut);\n\nmE = mO - mORef;\nassert(max(abs(mE(:))) < maxThr);]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The test case will examine all 3 modes. Try to solve it once with very clear code (No vectorization tricks) and then optimize.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A good way to build the output sparse function is using:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[mK = sparse(vRows, vCols, vVals, numElementsOutputImage, numElementsInputImage);]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Look for the documentation of `sparse()` function for more details.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

In this problem the challenge is to build the Matrix Form equivalent of the function `conv2()` of MATLAB.The function to be built will generate a sparse matrix `mK` which is the convolution matrix of the 2D Kernel 'mH' (Which is an input to the function). 
The input to the function is the 2D Kernel and dimensions of the image to apply the convolution upon and the shape of the convolution ('full', 'same', 'valid' as in 'conv2()').The output sparse matrix should match the output of using 'conv2()' on the same image using the same convolution shape.For instance:<pre class="language-matlab">CONVOLUTION_SHAPE_FULL = 1;
CONVOLUTION_SHAPE_SAME = 2;
CONVOLUTION_SHAPE_VALID = 3;
</pre><pre class="language-matlab">numRowsImage = 100;
numColsImage = 80;
</pre><pre class="language-matlab">numRowsKernel = 7;
numColsKernel = 5;
</pre><pre class="language-matlab">mI = rand(numRowsImage, numColsImage);
mH = rand(numRowsKernel, numColsKernel);
</pre><pre class="language-matlab">maxThr = 1e-9;
</pre><pre class="language-matlab">%% Full Convolution
</pre><pre class="language-matlab">convShape = CONVOLUTION_SHAPE_FULL;
</pre><pre class="language-matlab">numRowsOut = numRowsImage + numRowsKernel - 1;
numColsOut = numColsImage + numColsKernel - 1;
</pre><pre class="language-matlab">mORef = conv2(mI, mH, 'full');
mK = CreateImageConvMtx(mH, numRowsImage, numColsImage, convShape);
mO = reshape(mK * mI(:), numRowsOut, numColsOut);
</pre><pre class="language-matlab">mE = mO - mORef;
assert(max(abs(mE(:))) &lt; maxThr);
</pre>The test case will examine all 3 modes.
Try to solve it once with very clear code (No vectorization tricks) and then optimize.A good way to build the output sparse function is using:<pre class="language-matlab">mK = sparse(vRows, vCols, vVals, numElementsOutputImage, numElementsInputImage);
</pre>Look for the documentation of `sparse()` function for more details.

Solve

Solution Stats

13 Solutions
3 Solvers

Last Solution submitted on Jan 21, 2019

Last 200 Solutions

Problem Recent Solvers3

Problem Tags

Problem 44832. Generate Convolution Matrix of 2D Kernel with Different Convolution Shapes (Full, Same, Valid)

Solution Stats

Last 200 Solutions

Problem Recent Solvers3

Suggested Problems

Problem Tags

Players