Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have an image encoded in the form of a list of points, like so:

335.0 2743.0 
335.0 2754.0 
325.0 2754.0 
304.0 2743.0 
304.0 2733.0 
283.0 2723.0 
273.0 2702.0 
273.0 2691.0 
273.0 2681.0 
273.0 2670.0 
283.0 2670.0 
294.0 2670.0 
304.0 2670.0 
325.0 2670.0 
335.0 2681.0 
346.0 2702.0 
346.0 2712.0 
356.0 2723.0 
346.0 2733.0 
346.0 2743.0 
346.0 2733.0 
346.0 2723.0 
356.0 2702.0 
356.0 2670.0 
356.0 2660.0 
367.0 2660.0 

There is a line drawn between each point to make the image - if you sketch the points above (I'd advise doing it programatically) you'll see a lower case 'a'. This is part of a project regarding online character recognition. I am currently investigating the effects of several pre-processing techniques that can be applied to such a recognition system, and one technique that many of the papers that I have read apply is to 'smooth' the image, usually via a Gaussian blur. Unfortunately, they all proclaim it as "easy", and therefore they neglect to mention how one goes about doing so.

I have been looking for quite some time now, but I find myself still unable to understand how I would take the idea and apply it to an image made up of a set of points like the one above. From the wikipedia article I have the function:

$G(X) = \frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{x^2}{2\sigma^2}}$

However, I have no idea how I actually apply that to my list of points to get a smoothed image. All of the examples online are both incredibly complicated and also for pixel-images, where every pixel in your image matters. Here, I only actually have the 20 or so points. So, what I am looking for is some explanation and advice regarding how I would apply a Gaussian blur in my way of representing the image - what do I apply $G(X)$ to (each co-ordinate?), how I calculate $\sigma^2$, etc.

The disclaimer: As stated, this is part of an assignment. However, this is not breaking any rules or 'cheating' in any form. The assignment is to investigate many features of online character recognition, not to magically know how to do one of the possible techniques for pre-processing the characters. Should I gain any knowledge of how to do the smoothing from this site, the site (and the individual, should they wish) will of course be credited in full.

I thank you for any help. I hope this question is placed correctly (I felt it was more mathematical than program-based, since it's more about the concept of Gaussian blurs rather than the implementation - I'm fairly sure I'll be able to handle that part) and that it is clear. If it is not, please just ask and I will clarify any points I can.

(I also apologise for the tag. I'm fairly sure it's inaccurate. But there's no 'Gaussian' tag. Tis odd.)

share|improve this question
1  
Applying Gaussian blur to a piecewise linear curve like yours is not usually a well-defined operation. But since you mention preprocessing for optical character recognition, it seems far more likely to me that Gaussian blur is applied to the input image to reduce noise, rather than to the outline of the character after segmentation. –  Rahul Oct 5 '10 at 0:20
1  
I agree with Rahul's comment, except that applying gaussian blur to a polygonal curve does have a natural interpretation: it's the probability density of X + tZ, where X is selected uniformly from the curve (w.r.t. 1-dimensional Hausdorff measure), and Z is standard normal and independent of X. (t is the parameter that controls the amount of blurring.) –  Darsh Ranjan Oct 5 '10 at 2:12
    
@Rahul: The problem is (and perhaps I do not make this clear enough), the input image is the above points. This is not OCR. This is online character recognition, where the characters are input via a tablet device and thus given to the system as a set of X,Y co-ordinates. I have read countless papers on this sort of system now, and almost every one of them uses smoothing (usually calling it 'Gaussian low-pass filtering') on the co-ordinate input. And yet every reply on this page claims I need a pixel-image. >_<. –  Stephen Oct 5 '10 at 10:01
    
I apologize; I didn't know there was a difference between "online character recognition" and "optical character recognition". Perhaps they mean treating the input as a signal from $[0,T]$ to $\mathbb{R}^2$ and convolving it with a Gaussian kernel, essentially averaging each point with its neighbours to remove noise. But it's difficult to say for sure without seeing the papers themselves; could you edit your question to add links to a few of them? –  Rahul Oct 5 '10 at 15:47
    
Although Justin's answer is phrased in terms of "pixels", what he describes is a 1d filter suitable for use on a list of values. You can apply such a filter to your X and Y values separately (considering the two dimensions as sampling independent functions of t) and the result will be a smoothed point list. –  walkytalky Oct 5 '10 at 16:34
add comment

2 Answers 2

up vote 2 down vote accepted

The industry standard way of doing this is is to calculate a "mask" of sorts, and apply it to each one.

By "mask", I mean, say, a function for the current point based on the points before and after. For example:

$f(x) = \frac{1}{9}[x-2] + \frac{2}{9}[x-1] + \frac{3}{9}[x] + \frac{2}{9}[x+1] + \frac{1}{9}[x+2] $

where $[p]$ is the value of the pixel at $p$.

So to find the new pixel value at, say, pixel $4$, you'd use $ \frac{1}{9}[2] + \frac{2}{9}[3] + \frac{3}{9}[4] + \frac{2}{9}[5] + \frac{1}{9}[6] $ (remembering that, say, $[3]$ is the value of pixel 3)

All that's left to do is then apply your mask to every pixel. (What should you use for pixels that are close to the edge? That's up to you.)

Note that to be a true blurring mask, your coefficients must add up to 1.

A "Gaussian Blur" is just applying a special mask based off of the Gaussian Curve to your pixels.

That is, you make the "coefficient" of each term a number based off of the Gaussian Curve at that point.

For example, wikipedia lists:

$f(x) = 0.00038771[x-3] + 0.01330373[x-2] + 0.11098164[x-1] + 0.22508352[x] + 0.11098164[x+1] + 0.01330373[x+2] + 0.00038771[x+2]$

as a mask with σ = 0.84089642 and a "cut-off" radius of 3, although you can pick your own standard deviation and cut-off radius to your liking.

share|improve this answer
add comment

The operation is better described in the Wikipedia article Gaussian Filter. First you need to convert your list of points to an image, in essence filling in the line between the points. If you use 8 bits, those cells will have darkness 255 while all others will be 0. Or perhaps you give the lines a thickness and calculate how much of each pixel is covered. Now the image is a large array of numbers. The value of sigma is yours to choose. From sigma you choose will calculate a small array that represents G(X). If sigma is one pixel, you can represent G(X) only over +-3 pixels, so it is 7x7. To calculate the blurred darkness of a pixel, you take the original darknesses of the 7x7 neighborhood of the pixel, multiply them by the G(X) array and add.

share|improve this answer
    
@user1827: It's possible to put hyperlinks in the answer (click on the "chain" icon above the text area). Anyway, here's the link: en.wikipedia.org/wiki/Gaussian_filter –  Hans Lundmark Oct 5 '10 at 6:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.