# What is a low-pass filter for a sequence of tuples?

I am currently reading SEGMENTATION AND RECOGNITION OF SYMBOLS WITHIN HANDWRITTEN MATHEMATICAL EXPRESSIONS. There is one sentence I don't understand:

The preprocessing stage is subdivided into three steps:

• smoothing the input data by lowpass-filtering.

In this context your data usually looks like this:

[[(x1, y1), (x2, y2), ...],
[(x12, y12), ...],
...
]


So you have list of coordinates that are ordered by time. Each sublist is exactly one line or a single point.

I've only heard of low-pass filters in the context of acoustics / electronics so far (I don't know much about these topics). In those contexts it's obvious what it means to let low frequencies pass / cut high frequencies.

So what is a low-pass filter in the context of handwritten symbol recogntion?

• I think you'd just treat the X and Y as separate data streams and low-pass filter each, to remove any high-frequency wiggles. You'd probably want to use zero-phase filters for this, to avoid shifting them around – endolith Jun 3 '14 at 17:33
• @endolith: I really don't have any experience in this area. What is a zero-phase filter? How do you convert the lists of coordinates to frequencies? – Martin Thoma Jun 3 '14 at 17:40
• You don't convert them to frequencies. You'd take the x values out of each tuple, in order, then process them with a zero-phase filter and put them back into the tuples, then do the same for the y values. A zero-phase filter is either an FIR filter that's symmetrical about 0, or an IIR filter run forwards and then backwards over the data, so there's no phase-shift. A simple zero-phase lowpass FIR filter would be a moving average x_new[i] = 1/3*(x_old[i-1] + x_old[i] + x_old[i+1]) – endolith Jun 3 '14 at 18:08
• @endolith: What's the effect of that filter? I think it "smoothes" the line. Is that correct? If it only smoothes the line(s), wouldn't it be better to use the Ramer–Douglas–Peucker algorithm? – Martin Thoma Jun 3 '14 at 18:54
• Yes, a low-pass filter smooths the data. It keeps slow changes while removing fast changes. The R-D-P algorithm reduces the number of samples, according to Wikipedia, so it behaves as both a smoothing lowpass filter and a decimator. I've never heard of it before, but yes it's probably a better choice for this application than a generic filter. The FIR filter would smooth the sample positions without changing the number of samples. It would move the points around based on their neighbors, and what I've described might behave much differently than what you want. – endolith Jun 3 '14 at 19:40

'Frequency' for a sequence of values is the measure of how sharp the values in that sequence change.

For example, the sequence $x_1(n)=[\begin{array}[cccccccc]&\cdots &1, &1, &1, &1, &\cdots\end{array}]$ has a frequency 0 but the $x_2(n)=[\begin{array}[cccccccc] &\cdots &1 &1 &7 &1 &\cdots\end{array}]$ is a higher frequency signal since there is a sharp change in sequence value (1 to 7 and 7 to 1).

A low pass filter is a system which attenuates the high frequency components. OR it reduces the sharpness (or introduces blur) in case of an image. OR a low pass filter does not allow sudden changes in values and smoothens these changes. Figure below shows low passing various sequences ($\style{color:blue}{blue:input}$ $\style{color:red}{red:output}$).

Consider a system whose output is a sequence $y(n)$ where n$^{th}$ value in $y(n)$ is the average of n$^{th}$, (n-1)$^{th}$ and (n+1)$^{th}$ value of input sequence is a simple low pass filter. If $x_2(n)$ is fed as input to this filter, then output, will be $[\begin{array}[cccccccc] &\cdots &1 &3 &3 &3 &1 &\cdots\end{array}]$ and it is clear that the magnitude of change between consecutive values are reduced. or the high frequency components are attenuated.

Since you have a tuple, you have to separate it into two sequences ([x1,x2,....] and [y1,y2,....]). The low pass filtering should be done on these sequences separately.

In character recognition algorithms, low pass filtering is used in pre-processing to remove noises or unwanted small dots, having a width of one or two pixels. see an example of low pass filtering used for noise removal in image processing.

• That's a great answer (accept and +1)! But how can a moving average remove noise? Doesn't it simply blur noise? What filter was applied to the last two images? – Martin Thoma Jun 4 '14 at 14:06
• @moose I took the last image from Google search result. But I think its median filter. – nidhin Jun 4 '14 at 14:42
• @moose Low pass filter need not be an averaging filter. A lot of linear and non-linear operations can perform low pass filtering or noise removal. I have tried to explain how moving average filter can remove noise with a small example. This example applies to binary images. see the updated answer. – nidhin Jun 4 '14 at 17:36
• This is not about image processing, though; it's essentially about processing vector artwork, not raster, with strokes defined by a sequence of coordinates. – endolith Jun 4 '14 at 17:57
• @endolith Is it?! sorry I didn't read that paper. I just found that he is having a confusion between spatial filters and normal filters. So I was just trying to solve that. – nidhin Jun 4 '14 at 18:03