[GIL] 2D Convolution/Correlation Proposal for gsoc 2021

From: Gaurav kumar (g.kumar2520_at_[hidden])
Date: 2021-03-12 22:04:32

Hi,
I am Gaurav Kumar; I have been working on the Boost.GIL library for the
past month.
 I would like to work on the 2D convolution/Correlation project.
The ideas for the project are as follows:

1.   Separable Kernels <http://www.dspguide.com/ch24/3.htm>:
Most of the standard kernels (e.g. Gaussian, Sobel) can be separated into
2 or more 1D filters.
For a  N x N kernel, separating it into two 1D filters,
the number of computations required would now be proportional to 2*N
instead of N*N for the naive implementation.
This implementation would also favor code reusability as this would
only require a kernel separating function and driver code for a group of 1D
filters.

2. Generic Implementation for 2D convolution:
There are more generic kernels that are non-separable (e.g. Laplacian
operator).
In this case, the naive approach has already been implemented.
The main task would be to provide the same set of functions as in the
1D convolution/correlation implementation.

One potential idea for optimization of 2D convolution is to use the Im2col
<https://www.programmersought.com/article/6306124604/> operation,
in which the input image is converted into a row of column vectors, where
each column vector represents an image block for which
convolution/correlation
operation is to be performed.
The kernel can also be flattened out in a similar manner, resulting in a 1D
array.
This results in the convolution operation being reduced to matrix
multiplication,
which can be handled efficiently by BLAS libraries
<https://en.wikipedia.org/wiki/Basic_Linear_Algebra_Subprograms> (
Boost.uBLAS ).

Please share any suggestions you would have, related to the ideas
presented above, or regarding 2D convolutions in general.

I am looking for a mentor to guide me through this project.

Best Regards,
Gaurav Kumar
Github handle: https://github.com/gkumar28