FFT-based Line Smoothing

With a jagged or noisy signal, Fourier filtering can be pretty useful for cleaning up the unwanted noise. Line drawings can be considered signals just as easily as time-varying signals, so let’s get ready for some Fourier transforms!

The basic idea of smoothing (with length scale L) a polyline with a Fourier transform:

1. Re-sample along the polyline to have points that are uniform spaced (with distance dL) along its length.
2. Take an FFT of the x and y coordinates separately (yielding X, Y).
3. Zero-out the portions of X and Y at frequencies higher than 1/L
4. Inverse Fourier transform the new versions of X and Y, yielding the smoothed coordinates.

Simple, right? Well, mostly. This assumes that the polyline is a loop, since the Fourier transform assumes a periodic input. The first row of the next image shows what happens when you use this smoothing on a closed loop. The second row tries the naive smoothing on an open shape, and wrongly tries to close it! The third row shows the corrected version, which I’ll explain shortly.

Since the Fourier transform assumes periodicity, it assumes that the start point is right next to the end point. To fix that, we need to “pad” the input. The simplest method would be to prepend (add to the start) a bunch of entries of the initial position, and to append a bunch of entries of the end position. This gives OK results, but doesn’t match the slope of the lines at the end. Instead, we can treat the path as locally odd at the start and end, and connect them into a loop. Then after filtering, we trim off the padding and give a nice smooth result. The padding for the above filtering is shown below, with the original path in black.