Given a contour outlining the edges of an 'S' shape in OpenCV/Python, what methods can be used to trace a curve along the center of the shape?

Question

Given a contour outlining the edge of the letter S (in comic sans for example), how can I get a series of points along the spine of this letter in order to later represent this shape using lines, cubic spline or other curve-representing technique? I want to process and represent the shape using 30-40 points in Python/OpenCV.

Morphological skeletonization could help with this but the operation always seems to produce erroneous branches. Is there a better way to collapse the contour into just the 'S' shape of the letter?

In the example below you can see the erroneous 'serpent's tongue' like branches that are produced by morphological skeletonization. I don't know if it's fair to say they are erroneous if that's what the algorithm is supposed to be doing, but for me I would not like them to be there.

Below is the comic sans alphabet:

Another problem with skeletonization is that it is computationally expensive, but if you know a way of making it robust to forming 'serpent's tongue' like branches then I will give it a try.

Icecap

Do you mean you want to "vectorize the characters"? or "represent the skeletons using spline" ? – Merwyn

either would be helpful! from what I understand bezier curves are used in vector graphics to make bezier splines. I think that for some of the characters above representing using a single cubic spline could be difficult - that's why I started the question with the letter "S". Even a poly-line would work in the beginning... – Icecap

There are some easy tricks in graph-thinning. After forming a graph of the above you can decimate away nodes that don't reach a n-furcation (n>2) before a certain distance. – Endorse

I am no expert, but couldn't the distance transform (see docs.opencv.org/2.4.7/modules/imgproc/doc/…) be helpful for what you want to do ? – Seibold

@AldurDisciple, I have tried that, but it seems need further processing since the result is not connected curve. – Merwyn

Answer 1

Actually vectorizing fonts isn't trivial problem and quite tricky. To properly vectorize fonts using bezier curve you'll need tracing. There are many library you can use for tracing image, for example Potrace. I'm not knowledgeable using python but based on my experience, I have done similar project using c++ described below:

A. Fit the contour using cubic bezier

This method is quite simple although a lot of work should be done. I believe this also works well if you want to fit skeletons obtained from thinning.

1. Find contour/edge of the object, you can use OpenCV function findContours()
2. The entire shape can't be represented using a single cubic bezier, so divide them to several segments using Ramer-Douglas-Peucker (RDP). The important thing in this step, don't delete any points, use RDP only to segment the points. See colored segments on image below.
3. For each segments, where S is a set of n points S = (s0, s1,...Sn), fit a cubic bezier using Least Square Fitting

Illustration of least square fitting:

B. Resolution Resolution Independent Curve Rendering

This method as described in this paper is quite complex but one of the best algorithms available to display vector fonts:

1. Find contour (the same with method A)
2. Use RDP, differently from method A, use RDP to remove points so the contour can be simplified.
3. Do delaunay triangulation.
4. Draw bezier curve on the outer edges using method described in the paper

Merwyn

thanks for the answer - i will give these a try. rdp could be a very useful algorithm so i will try to implement in python. – Icecap

Answer 2

The following simple idea might be usefull.

1. Calculate Medial axis of the outer contour. This would ensure connectivity of the curves.

2. Find out the branch points. Depending on its length you can delete them in order to eliminate "serpent's tongue" problem.

Hope it helps.

Risner