11
$\begingroup$

I know this question may not be very relevant to programming, but if I don't understand the theory behind image processing I'll never be able to implement something in practice.

If I got it right Gaussian filters are convolved with an image for noise reduction since they compute a weighed average of a pixel's neighborhood and they are very useful in edge-detection, since you can apply a blur and derive the image at the same time by simply convolving with the derivative of a Gaussian function.

But can anyone explain me, or give me some references on how are they computed?

E.g. Canny's edge detector talks about a 5x5 Gaussian filter, but how did they get those particular numbers? And how did they go from a continuous convolution to a Matrix multiplication?

$\endgroup$
3
$\begingroup$

For this operation to work, you need to imagine that your image is reshaped as a vector. Then, this vector is multiplied on its left by the convolution matrix in order to obtain the blurred image. Note that the result is also a vector the same size as the input, i.e., an image of the same size.

Each row of the convolution matrix corresponds to one pixel in the input image. It contains the weight of the contributions of all the other pixels in the image to the blurred counterpart of the considered pixel.

Let's take an example: box blur of size $3 \times 3$ pixels on an image of size $6 \times 6$ pixels. The reshaped image is a column of 36 elects, while the blur matrix has size $36 \times 36$.

  • Let's init this matrix to 0 everywhere.
  • Now, consider the pixel of coordinates $(i,j)$ in the input image (not on its border for simplicity). Its blurred counterpart is obtained by applying a weight of $1/9$ to itself and each of its neighbours at the positions $(i-1,j-1); (i-1,j), (i-1,j+1),\ldots,(i+1,j+1)$.
  • In the column vector, the pixel $(i,j)$ has the position $6*i + j$ (assuming lexicographic ordering). we report the weight $1/9$ in the $(6i+j)$-th line of the blur matrix.
  • Do the same with all other pixels.

A visual illustration of a closely related process (convolution + subtraction) can be found on this blog post (from my personal blog).

$\endgroup$
  • $\begingroup$ a link is dead. $\endgroup$ – gauteh Sep 4 '15 at 11:31
2
$\begingroup$

For applications to images or convolution networks, to more efficiently use the matrix multipliers in modern GPUs, the inputs are typically reshaped into columns of an activation matrix that can then be multiplied with multiple filters/kernels at once.

Check out this link from Stanford's CS231n, and scroll down to the section on "Implementation as Matrix Multiplication" for details.

The process works by taking all the local patches on an input image or activation map, the ones that would be multiplied with the kernel, and stretching them into a column of a new matrix X through an operation commonly called im2col. The kernels are also stretched to populate the rows of a weight matrix W so that when performing the matrix operation W*X, the resulting matrix Y has all the results of the convolution. Finally, the Y matrix must be reshaped again by converting the columns back into images by an operation typically called cal2im.

$\endgroup$
  • 1
    $\begingroup$ This is a very good link, thanks! However it is good practice to add the important extracts from the link into the answer, this way the answer is valid even if the link breaks. Please consider editing your answer to get it accepted! $\endgroup$ – Matteo Feb 23 '17 at 18:27
1
$\begingroup$

Convolution in Time domain equals matrix multiplication in the frequency domain and vice versa.

Filtering is equivalent to convolution in the time domain and hence matrix multiplication in the frequency domain.

As for the 5x5 maps or masks, they come from discretizing the canny/sobel operators.

$\endgroup$
  • 2
    $\begingroup$ I don't agree with the fact that filtering is a convolution in the frequency domain. The kind of filters we are talking about here are convolutions in the spatial domain (that is to say, element-wise multiplication by the filter response in the frequency domain). $\endgroup$ – pichenettes Mar 16 '13 at 16:51
  • $\begingroup$ Thanks for correcting what I wrote. I made a subsequent edit. I guess I should double-check my answers before posting. However, the majority of my answer still stands. $\endgroup$ – Naresh Mar 17 '13 at 4:15
  • $\begingroup$ The Fourier transform does indeed turn convolutions into multiplications (and vice versa). However, they are pint wise multiplications, while the question is about matrix-vector multiplications that are obtained by reshaping the images. $\endgroup$ – sansuiso Mar 17 '13 at 16:34
  • $\begingroup$ I did mention how discretizing the operators is the reason for the 5x5 matrices obtained for the canny/sobel operators. $\endgroup$ – Naresh Mar 17 '13 at 17:49
1
$\begingroup$

I wrote a function which solves this in my StackOverflow Q2080835 GitHub Repository (Have a look at CreateImageConvMtx()).
Actually the function can support any convolution shape you'd like - full, same and valid.

The code is as following:

function [ mK ] = CreateImageConvMtx( mH, numRows, numCols, convShape )

CONVOLUTION_SHAPE_FULL  = 1;
CONVOLUTION_SHAPE_SAME  = 2;
CONVOLUTION_SHAPE_VALID = 3;

switch(convShape)
    case(CONVOLUTION_SHAPE_FULL)
        % Code for the 'full' case
        convShapeString = 'full';
    case(CONVOLUTION_SHAPE_SAME)
        % Code for the 'same' case
        convShapeString = 'same';
    case(CONVOLUTION_SHAPE_VALID)
        % Code for the 'valid' case
        convShapeString = 'valid';
end

mImpulse = zeros(numRows, numCols);

for ii = numel(mImpulse):-1:1
    mImpulse(ii)    = 1; %<! Create impulse image corresponding to i-th output matrix column
    mTmp            = sparse(conv2(mImpulse, mH, convShapeString)); %<! The impulse response
    cColumn{ii}     = mTmp(:);
    mImpulse(ii)    = 0;
end

mK = cell2mat(cColumn);


end

I also created a function to create a Matrix for Image Filtering (Similar ideas to MATLAB's imfilter()):

function [ mK ] = CreateImageFilterMtx( mH, numRows, numCols, operationMode, boundaryMode )
%UNTITLED6 Summary of this function goes here
%   Detailed explanation goes here

OPERATION_MODE_CONVOLUTION = 1;
OPERATION_MODE_CORRELATION = 2;

BOUNDARY_MODE_ZEROS         = 1;
BOUNDARY_MODE_SYMMETRIC     = 2;
BOUNDARY_MODE_REPLICATE     = 3;
BOUNDARY_MODE_CIRCULAR      = 4;

switch(operationMode)
    case(OPERATION_MODE_CONVOLUTION)
        mH = mH(end:-1:1, end:-1:1);
    case(OPERATION_MODE_CORRELATION)
        % mH = mH; %<! Default Code is correlation
end

switch(boundaryMode)
    case(BOUNDARY_MODE_ZEROS)
        mK = CreateConvMtxZeros(mH, numRows, numCols);
    case(BOUNDARY_MODE_SYMMETRIC)
        mK = CreateConvMtxSymmetric(mH, numRows, numCols);
    case(BOUNDARY_MODE_REPLICATE)
        mK = CreateConvMtxReplicate(mH, numRows, numCols);
    case(BOUNDARY_MODE_CIRCULAR)
        mK = CreateConvMtxCircular(mH, numRows, numCols);
end


end


function [ mK ] = CreateConvMtxZeros( mH, numRows, numCols )
%UNTITLED6 Summary of this function goes here
%   Detailed explanation goes here

numElementsImage    = numRows * numCols;
numRowsKernel       = size(mH, 1);
numColsKernel       = size(mH, 2);
numElementsKernel   = numRowsKernel * numColsKernel;

vRows = reshape(repmat(1:numElementsImage, numElementsKernel, 1), numElementsImage * numElementsKernel, 1);
vCols = zeros(numElementsImage * numElementsKernel, 1);
vVals = zeros(numElementsImage * numElementsKernel, 1);

kernelRadiusV = floor(numRowsKernel / 2);
kernelRadiusH = floor(numColsKernel / 2);

pxIdx       = 0;
elmntIdx    = 0;

for jj = 1:numCols
    for ii = 1:numRows
        pxIdx = pxIdx + 1;
        for ll = -kernelRadiusH:kernelRadiusH
            for kk = -kernelRadiusV:kernelRadiusV
                elmntIdx = elmntIdx + 1;

                pxShift = (ll * numCols) + kk;

                if((ii + kk <= numRows) && (ii + kk >= 1) && (jj + ll <= numCols) && (jj + ll >= 1))
                    vCols(elmntIdx) = pxIdx + pxShift;
                    vVals(elmntIdx) = mH(kk + kernelRadiusV + 1, ll + kernelRadiusH + 1);
                else
                    vCols(elmntIdx) = pxIdx;
                    vVals(elmntIdx) = 0; % See the accumulation property of 'sparse()'.
                end
            end
        end
    end
end

mK = sparse(vRows, vCols, vVals, numElementsImage, numElementsImage);


end


function [ mK ] = CreateConvMtxSymmetric( mH, numRows, numCols )
%UNTITLED6 Summary of this function goes here
%   Detailed explanation goes here

numElementsImage    = numRows * numCols;
numRowsKernel       = size(mH, 1);
numColsKernel       = size(mH, 2);
numElementsKernel   = numRowsKernel * numColsKernel;

vRows = reshape(repmat(1:numElementsImage, numElementsKernel, 1), numElementsImage * numElementsKernel, 1);
vCols = zeros(numElementsImage * numElementsKernel, 1);
vVals = zeros(numElementsImage * numElementsKernel, 1);

kernelRadiusV = floor(numRowsKernel / 2);
kernelRadiusH = floor(numColsKernel / 2);

pxIdx       = 0;
elmntIdx    = 0;

for jj = 1:numCols
    for ii = 1:numRows
        pxIdx = pxIdx + 1;
        for ll = -kernelRadiusH:kernelRadiusH
            for kk = -kernelRadiusV:kernelRadiusV
                elmntIdx = elmntIdx + 1;

                pxShift = (ll * numCols) + kk;

                if(ii + kk > numRows)
                    pxShift = pxShift - (2 * (ii + kk - numRows) - 1);
                end

                if(ii + kk < 1)
                    pxShift = pxShift + (2 * (1 -(ii + kk)) - 1);
                end

                if(jj + ll > numCols)
                    pxShift = pxShift - ((2 * (jj + ll - numCols) - 1) * numCols);
                end

                if(jj + ll < 1)
                    pxShift = pxShift + ((2 * (1 - (jj + ll)) - 1) * numCols);
                end

                vCols(elmntIdx) = pxIdx + pxShift;
                vVals(elmntIdx) = mH(kk + kernelRadiusV + 1, ll + kernelRadiusH + 1);

            end
        end
    end
end

mK = sparse(vRows, vCols, vVals, numElementsImage, numElementsImage);


end


function [ mK ] = CreateConvMtxReplicate( mH, numRows, numCols )
%UNTITLED6 Summary of this function goes here
%   Detailed explanation goes here

numElementsImage    = numRows * numCols;
numRowsKernel       = size(mH, 1);
numColsKernel       = size(mH, 2);
numElementsKernel   = numRowsKernel * numColsKernel;

vRows = reshape(repmat(1:numElementsImage, numElementsKernel, 1), numElementsImage * numElementsKernel, 1);
vCols = zeros(numElementsImage * numElementsKernel, 1);
vVals = zeros(numElementsImage * numElementsKernel, 1);

kernelRadiusV = floor(numRowsKernel / 2);
kernelRadiusH = floor(numColsKernel / 2);

pxIdx       = 0;
elmntIdx    = 0;

for jj = 1:numCols
    for ii = 1:numRows
        pxIdx = pxIdx + 1;
        for ll = -kernelRadiusH:kernelRadiusH
            for kk = -kernelRadiusV:kernelRadiusV
                elmntIdx = elmntIdx + 1;

                pxShift = (ll * numCols) + kk;

                if(ii + kk > numRows)
                    pxShift = pxShift - (ii + kk - numRows);
                end

                if(ii + kk < 1)
                    pxShift = pxShift + (1 -(ii + kk));
                end

                if(jj + ll > numCols)
                    pxShift = pxShift - ((jj + ll - numCols) * numCols);
                end

                if(jj + ll < 1)
                    pxShift = pxShift + ((1 - (jj + ll)) * numCols);
                end

                vCols(elmntIdx) = pxIdx + pxShift;
                vVals(elmntIdx) = mH(kk + kernelRadiusV + 1, ll + kernelRadiusH + 1);

            end
        end
    end
end

mK = sparse(vRows, vCols, vVals, numElementsImage, numElementsImage);


end


function [ mK ] = CreateConvMtxCircular( mH, numRows, numCols )
%UNTITLED6 Summary of this function goes here
%   Detailed explanation goes here

numElementsImage    = numRows * numCols;
numRowsKernel       = size(mH, 1);
numColsKernel       = size(mH, 2);
numElementsKernel   = numRowsKernel * numColsKernel;

vRows = reshape(repmat(1:numElementsImage, numElementsKernel, 1), numElementsImage * numElementsKernel, 1);
vCols = zeros(numElementsImage * numElementsKernel, 1);
vVals = zeros(numElementsImage * numElementsKernel, 1);

kernelRadiusV = floor(numRowsKernel / 2);
kernelRadiusH = floor(numColsKernel / 2);

pxIdx       = 0;
elmntIdx    = 0;

for jj = 1:numCols
    for ii = 1:numRows
        pxIdx = pxIdx + 1;
        for ll = -kernelRadiusH:kernelRadiusH
            for kk = -kernelRadiusV:kernelRadiusV
                elmntIdx = elmntIdx + 1;

                pxShift = (ll * numCols) + kk;

                if(ii + kk > numRows)
                    pxShift = pxShift - numRows;
                end

                if(ii + kk < 1)
                    pxShift = pxShift + numRows;
                end

                if(jj + ll > numCols)
                    pxShift = pxShift - (numCols * numCols);
                end

                if(jj + ll < 1)
                    pxShift = pxShift + (numCols * numCols);
                end

                vCols(elmntIdx) = pxIdx + pxShift;
                vVals(elmntIdx) = mH(kk + kernelRadiusV + 1, ll + kernelRadiusH + 1);

            end
        end
    end
end

mK = sparse(vRows, vCols, vVals, numElementsImage, numElementsImage);


end

The code was validated against MATLAB imfilter().

Full code is available in my StackOverflow Q2080835 GitHub Repository.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.