1
$\begingroup$

I have an Nx3 matrix of poses (x, y, theta) that I need to apply an algorithm on which will cause the trajectory to be smoothed. I am interested in performance and so would like to improve efficiency by describing multiple convolutions as a single convolution.

I am using an averaging kernel matrix as described here that has the dimensions 4x1. I apply this to the x and y coordinates of the computed robot trajectory to smooth it out. The thing is, this is repeated numerous times on the same data. This is best illustrated with some pseudo code.

void ConvolutionCaller(std::vector<signal_element> x_coordinates)
{
    const unsigned int KERNEL_ROWS = 4;
    const unsigned int KERNEL_COLS = 1;

    kernel_type kernel(AVERAGING, KERNEL_ROWS, KERNEL_COLS); // not a real function, for illustration only

    for(unsigned int i = 0; i < x_coordinates.size()/2; i++)
    {
        unsigned int start = i;
        unsigned int end = x_coordinates.size() - i;
        Convolve(x_coordinates, kernel, start, end);
    }
}

After each iteration, the points on the ends of the array get removed from the next calculation.

To illustrate this, consider the following points. Each level represents the points that are being convolved.

1:    A B C D E F G H I J K
2:      B C D E F G H I J
3:        C D E F G H I
4:          D E F G H
5:            E F G
6:              F

The length of the incoming array is variable. Is there a way that I can describe these series of convolutions as a single convolution?

$\endgroup$
  • $\begingroup$ Define "interested in performance": memory, code size, or CPU performance, and on which platform? Hint: google "fast convolution FFT". $\endgroup$ – Marcus Müller Mar 10 '17 at 10:10
  • $\begingroup$ Interested in CPU performance. Code size and memory are not an issue. I've read about "fast convolution FFT" while writing this question actually. It seems that FFT works on problem sets with certain characteristics. I don't know if it is relevant to this case. Though, I would still have to describe the convolution in the algorithm I've provided. That's that part I'm having difficulty with, but yes, CPU performance is my goal. $\endgroup$ – Klik Mar 10 '17 at 17:33
  • $\begingroup$ The fast convolution is really mathematically a convolution. No "restriction to a specific problem set". $\endgroup$ – Marcus Müller Mar 10 '17 at 19:40
  • $\begingroup$ I didn't mean that it was restricted, but rather that it is useful in certain cases. At least that's what I gathered from reading the Wiki. If one sequence is much longer than the other, zero-extension of the shorter sequence and fast circular convolution is not the most computationally efficient method available. FFT aside, is it possible to describe the given operations as a single convolution? I haven't been able to come up with a convolution such that the middle part of the array experiences more blurring. $\endgroup$ – Klik Mar 10 '17 at 22:09

Your Answer

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

Browse other questions tagged or ask your own question.