# Vectorizing to polylines instead of paths

I am trying to implement a shape matching algorithm for vector images discussed in a paper.

The input to the algorithm is a model of 2D shapes deﬁned by contour segments. According to the paper, such segments can be deﬁned as polylines, obtained for example by vectorizing the output of an edge detector like Canny.

I am trying to vectorize a tiff image using Inkscape's bitmap tracing feature. The svg image I got from it has a path node with many attribute values, but that is not what the algorithm wants:

How can I vectorize to polylines instead of paths?

• Why not just take the curves that Inkscape outputs and convert them to poly lines? It's fairly simple to convert a Bezier curve to a poly line. Commented Apr 13, 2017 at 5:34
• Why specifically a polyline? It's a much worse approximation to a curve than a Bezier spline. Regardless, I don't think you'll find a tool that will give you a "clean" polyline output without needing any manual tweaking. Commented Apr 13, 2017 at 7:16
• Section 4 of the paper mentions that polylines can clearly define the contour segments. Those segments are used to compute the local Shape Context descriptors. Commented Apr 14, 2017 at 14:00
• I couldn't link the paper in my question because I am new. Here it is: cg.tuwien.ac.at/research/publications/2014/Guerrero-2014-TPS Commented Apr 14, 2017 at 14:00
• I've added an answer explaining how it would work. Commented Apr 17, 2017 at 6:13

If you look at chapter 8 of the SVG Specification, it describes how to parse a path element. The short version is that you'll want to find the d attribute of the element. That element should be a string describing the curve. It will contain the following commands:

• m - Moveto command
• l - Lineto command
• c, s, q, & a - Curve commands
• z - close path

Simple lines will just be combinations of m and l sequences. The curves will be either circular arcs, quadratic bezier or cubic beziers.

To convert a Bezier curve into line segments, you can do the following:

const float kNumPolyLines = 10; // <- change this to make more lines per bezier segment
const float kDeltaT = 1.0 / kNumPolyLines;
Point c0;
Point c1;
Point c2;
Point c3;
GetBezierControlPoints(&c0, &c1, &c2, &c3); // <- get the 3 or 4 control points for the next bezier segment
Point prevPoint = c0;
Point currentPoint;
for (float t = kDeltaT; t <= 1.0; t += kDeltaT)
{
currentPoint = CalculateBezier(c0, c1, c2, c3, t);

// Now you have the next line segment in your poly line.
// It goes from prevPoint to currentPoint. Store it or draw it,
//or whatever you need

// Get ready for the next iteration
prevPoint = currentPoint;
}


You can find the formula for both quadratic and cubic bezier curves on Wikipedia.

• Thank you! Could you also tell me if this is possible to do in MATLAB? If so, how? Commented Apr 17, 2017 at 6:46
• I haven't used MATLAB in like 20 years, so I'm not really the one to ask. However, you can probably ask MATLAB questions on Stack Overflow. Commented Apr 17, 2017 at 16:11
• Ok. What platform is the SVG DOM interface implemented on? I can't decide what to use for this project. Also I don't think what you're suggesting will work for the kind of path I have. I have many curves and control points in one single d attribute. Commented Apr 17, 2017 at 17:11
• Sorry, I mean many curves and move to commands in a single d atrribute Commented Apr 17, 2017 at 17:19
• It should work just fine for many curves and move to commands. Each bezier can be handled as above to turn it into poly lines. they will connect with the next one in the sequence. As for which platform to use, that's not something I can answer. I've done SVG parsing using a standard XML parser in Objective-C (Apple's NSXMLParser), but it could be done in any language for which you have an XML parsing library. Good luck! Commented Apr 18, 2017 at 2:02