OCR: Convert edge into a vector path

Answer 1

How are the contours currently stored?

You might try first getting the contours as series of straight-line segments then attempt to fit smooth curves to portions of the straight line segment series. For example the 'one' would probably turn into an edge ring of 4 straight lines and 3 circular arcs.

You'll have to develop some heuristics as to what constitutes a 'good' fit.

But yes this is a pretty difficult problem. You should look up some research papers on character recognition. That's probably the best place to get ideas.

EDIT

I'll assume that you're only interested in closed contours. To extract a straight-line representation you can construct a geometric graph from the bitmap representation. Each pixel in the contour is a node and contour pixels from the bitmap that are touching (or within a specified tolerance) are connected by an edge. Each node retains the pixel's position. Extracting the maximal edge ring from each connected graph will give you the contours as straight lines.

Extracting the edge ring is fairly straightforward. Start with the farthest left node. Sort the connected edges clockwise around the node (where 12-o'clock is minimum). Take the last edge (e) from the sorted list. Add e to the ring you are building. Traverse the edge e to its connected node n and remove e from the graph. Repeat the sorting process at n where e is now the minimum for sorting the edges clock-wise. Select the last edge in the sorted list, add it to your ring, traverse it and remove it from the graph as you did for the last node. Repeat this process until you wrap back around to the starting node.

The edges in your ring are your closed contour. Because the pixels are so close together you'll have to post-process the ring to remove collinear edges and probably snap them to some larger grid to collapse points. But the general approach is sound.

From a geometric standpoint this is like walking around the outside of a large building keeping your left-hand against the wall. You don't know what the exact boundary of the building is but if you keep your left-hand to the wall you're guaranteed to traverse the entire (and only) outer boundary.

It has the benefit of being reasonably fast (basically linear with the number of pixels in the contour).

Just let me know if anything is unclear or you have any questions and I'll try to clear it up.

Answer 2

This is in general a very difficult problem. Which is why, for example, you don't see good code to generate vector font descriptions from bitmapped fonts, let alone OCR results.

I you have a lot of constraints on the text you will see, etc, you can certainly fit spline curves to them, but this is always going to be a bit fiddly. The more complicated your situation becomes, the more likely your algorithm will fall apart and need parameter twiddling etc. from a user. As long as you are ok with fairly rough results (and it sounds like you would be) you should be able to do something.

Fitting a polygon to the contours first will probably be a good way to get started.

Answer 3

In general, vectorizing a raster image is very difficult.

However, in your case, your target space is quite constrained: it is a set of font glyphs. If you know the font, or can reasonably guess, you can build an set of approximate curves and then use some kind of error-distance or pattern-matching algorithm to pick the best matching glyph out of the font and use its curve descriptions as your set of vectors.

Answer 4

Chaincode might be the solution to your problem

---

• Chaincode might be the useful as your images are binary (Black & White). Each individual chaincode representing a single character (disjoint chars i & j may require 2 chaincodes, unless provided with a workaround).

  http://en.wikipedia.org/wiki/Chain_code

• You might be interested in looking through the following example :

  http://stackoverflow.com/questions/2661452/need-help-understanding-this-matlab-function-implementation

GoodLUCK!!