How to smooth a 3D path using convolution

In image processing, a kernel, convolution matrix, or mask is just a small matrix (is more than this description but to simplify). It is employed for blurring, sharpening, embossing, edge detection, and more. This is accomplished by performing a convolution between a kernel and an image.

Then, the convolution process consists of using a kernel of certain size to extract certain features from an input array. Also, it could be defined as a process of adding each element of the input array to its local neighbors, weighted by the kernel. For this post, we only focus on smoothing process, however, there are others such as edge detection, sharpening, and more.

via GIPHY

In 1D, the kernel K is slid across an array A and multiplied with the input such that the output is enhanced in a certain desirable manner. Observe this in action below:

It is significant to note that the convolutional process is chiefly utilized on images (2D and 3D). In this post, I will talk indistinctly about the window size or kernel size, just to simplify things.

To understand better the idea, let's employ concrete numbers!

9 numbers convoluted by a kernel of size 3 — Example of 1D convolution

In the figure, A = [13, 10, 6, 5, 6, 8, 20, 1, 5], with a kernel of size 3. The operation performed is the average in the window size. for instance, the 1st windows contain the first 3 elements 13, 10, and 6, for an average of 9.6 for the 1st position of the convolved array (output). Notice that the output size is less than the original one.

Ok, that's fine but, show me the code

The previous explanation is based on a 1D array. However, this could be applied to 2D and 3D geometries. In this case, the goal is to smooth a path composed of 3D points. These 3D points represent a path to follow, being capture in time by a robot (like the Roomba vacuum cleaner).

Like so, the idea is to get a better representation of these points to establish a path with lesser peaks. I know there are several ways to solve this; I will show you a single one: 1D convolution (Ms. obvious)

To begin with, we require the points stored in an array/list or any structure present in the programming language. In this case, I will use C++ with the library OpenGL Mathematics (GLM). GLM is a header only C++ mathematics library for graphics software based on the OpenGL Shading Language (GLSL) specifications.

Given the points in the array vecPoints, size of windows stored in iWindow, the following function takes these parameters as input to compute the average for each sliding window. The sliding window starts in position iWindow and finishes in the last position minus iWindow (reducing the number of points as the window' size):

/// Function to apply an average convolutional (box blur)
/// 
/// @param vecPoints input 3D points to process
/// @param iWindow size of the kernel
/// @return smooth vecPoints of size vecPoints.size() - iWindow + 1
std::vector<glm::dvec3> smoothPoint(std::vector<glm::dvec3> vecPoints, int iWindow) {
  std::vector<glm::dvec3> vecOutput;

  int iHalfWindow = iWindow / 2;  // iWindow >> 1 also works
  for (int iIndex = iHalfWindow; iIndex < vecPoints.size() - iHalfWindow; iIndex++)
  {
    int iStart = iIndex - iHalfWindow;
    int iEnd = iIndex + iHalfWindow;
    
    // compute the average
    glm::dvec3 vecSum = std::accumulate(vecPoints.begin() + iStart, vecPoints.begin() + iEnd, 
                        glm::dvec3(0), [](const auto& a, const auto& b) {return a + b; });
    vecSum /= (iEnd - iStart);
    
    vecOutput.push_back(vecSum);
  }
  return vecOutput;
}

Note that the result is returned in the variable vecOutput, and the total accumulated sum is computed with the STL function std::accumulate, defined in the header <numeric>.

To this point, we already have the points smoothed. However, I love seeing the results. To visualize it, I used the graphics library VTK using spheres (with Glyph3D). I draw two paths: the white path is the original one, and the red is the smoothed one. Here some images:

There are several ways to smooth a set of points such Catmull-Rom, Ramer–Douglas–Peucker,Kochanek, parametric splines or others. Also, it is possible applying smooth operators for meshes: Laplace, Taubin, and more.