Vectorizing to polylines instead of paths

Question

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 defined by contour segments. According to the paper, such segments can be defined 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?

Answer 1

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.