Fast two-dimensional convolution for DSP

Question

I want to implement some image processing algorithms that are designed to run on a beagleboard . These algorithms make extensive use of convolution. I am trying to find a good C implementation for two-dimensional convolution (possibly using Fast Fourier Transform). I also want the algorithm to work on the big DSP platform, because I heard that the DSP is optimized for these kinds of operations (with instructions for multiplying accumulations).

I don’t have a background in the field, so I think it would be inappropriate to implement convolution (I probably won’t do it as well as someone who understands all the math behind it). I believe that a good C-convolution implementation for DSP exists somewhere, but I could not find it?

Can anyone help?

EDIT:. It turns out that the core is quite small. Its sizes are 2X2 or 3X3. Therefore, I think I'm not looking for an implementation based on FFT. I searched the convolution on the Internet to see its definition so that I could implement it in a straightforward manner (I really don't know what a convolution is). All I found is something with multiplied integrals, and I don’t know how to do this with matrices. Can someone give me a snippet of code (or pseudocode) for a 2X2 kernel case?

Answer 1

What are the sizes of the image and the core? If the core is large, then you can use FFT-based convolution, otherwise for small kernels just use direct convolution.

Perhaps the DSP is not the best way to do this, because it has a MAC instruction does not mean that it will be more efficient. Does the ARM processor on the Beagle board have NEON SIMD? If so, then this may be the way to go (and more fun too).

For a small kernel, you can do a direct convolution as follows:

// in, out are mxn images (integer data) // K is the kernel size (KxK) - currently needs to be an odd number, eg 3 // coeffs[K][K] is a 2D array of integer coefficients // scale is a scaling factor to normalise the filter gain for (i = K / 2; i < m - K / 2; ++i) // iterate through image { for (j = K / 2; j < n - K / 2; ++j) { int sum = 0; // sum will be the sum of input data * coeff terms for (ii = - K / 2; ii <= K / 2; ++ii) // iterate over kernel { for (jj = - K / 2; jj <= K / 2; ++jj) { int data = in[i + ii][j +jj]; int coeff = coeffs[ii + K / 2][jj + K / 2]; sum += data * coeff; } } out[i][j] = sum / scale; // scale sum of convolution products and store in output } } 

You can change this to maintain even K values ​​- for this you need to take a little care of the upper / lower bounds for the two inner loops.

Answer 2

I know this may be off topic, but due to the similarities between C and JavaScript, I find this to be useful. PS: Inspired by @Paul R.'s answer

Two-dimensional 2D convolution algorithm in JavaScript using arrays

 function newArray(size){ var result = new Array(size); for (var i = 0; i < size; i++) { result[i] = new Array(size); } return result; } function convolveArrays(filter, image){ var result = newArray(image.length - filter.length + 1); for (var i = 0; i < image.length; i++) { var imageRow = image[i]; for (var j = 0; j <= imageRow.length; j++) { var sum = 0; for (var w = 0; w < filter.length; w++) { if(image.length - i < filter.length) break; var filterRow = filter[w]; for (var z = 0; z < filter.length; z++) { if(imageRow.length - j < filterRow.length) break; sum += image[w + i][z + j] * filter[w][z]; } } if(i < result.length && j < result.length) result[i][j] = sum; } } return result; } 

You can check out the full blog post at http://ec2-54-232-84-48.sa-east-1.compute.amazonaws.com/two-dimensional-convolution-algorithm-with-arrays-in-javascript/