curvature-segmented-arc-line-vectorization

Vectorize a black-on-white line drawing PNG into a sequence of drawing-robot commands (line, spin, arc).

Pipeline

The pipeline implements the recipe sketched out earlier:

1. Skeletonize the binary image (skimage.morphology.skeletonize).
2. Trace the skeleton into polylines via a graph walk. Adjacent degree-≥3 pixels are merged into a single "super-junction" so thick junctions in the skeleton don't spawn spurious 2-pixel polylines.
3. Pre-segment by curvature. Each polyline is resampled to uniform arc-length spacing, smoothed with a Gaussian, and cut at peaks of |κ|. Constant-curvature regions become single segments.
4. Per-segment classification. Each segment is fit as a line (TLS / SVD) and as a circular arc (algebraic / Kåsa-style fit). The arc is chosen only if its residual is meaningfully better than the line's and its radius is reasonable for the segment's spatial scale (a giant-radius arc is indistinguishable from a line and is drawn as a line).
5. Stroke ordering. Greedy nearest-neighbour over stroke endpoints, with reversal when the far end is closer to the cursor.
6. Command emission. Robot state (position, heading) is tracked; each primitive emits a spin (if the heading needs to change) followed by the line or arc itself. Pen-up traversal between strokes is spin + line(penDown=False).

Files

• draw_robot/types.py — TypedDicts mirroring your TS discriminated union, plus internal LinePrimitive / ArcPrimitive dataclasses.
• draw_robot/vectorize.py — the full PNG-to-commands pipeline.
• draw_robot/render.py — replays a command list and writes an SVG, with drawn primitives coloured by draw order (rainbow hue ramp). Pen-up traversals are shown as faint dashed grey lines for sanity-checking.
• example_cat.py / example_fish.py — synthetic test inputs end-to-end.

Dependencies

pip install scikit-image numpy scipy pillow

Conventions

• Coordinates are pixel-space (x right, y down).
• Angles use the math convention in this frame (CCW = positive). Because y points down, "CCW in image space" looks visually clockwise on screen, but this is consistent with SVG, so the renderer round-trips correctly. If your robot operates in a y-up world, negate the sign of every degrees field after generation.
• For arcs: radius is always positive; the sign of degrees indicates direction (positive = curve to the left of current heading; negative = to the right). A full closed circle is emitted as a single arc with degrees = ±360.

Quickstart

from draw_robot import vectorize_png, commands_to_svg
import json

cmds = vectorize_png("input.png")
with open("commands.json", "w") as f:
    json.dump(cmds, f, indent=2)

# Visualize the resulting plan
commands_to_svg(cmds, "preview.svg")

The same module also exposes every pipeline stage individually (png_to_skeleton, trace_skeleton, segment_at_corners, fit_line, fit_arc, classify_segment, polyline_to_stroke, order_strokes, strokes_to_commands) so you can swap in your own version of any stage.

Known limitations / next steps

The current implementation deliberately stops at "good single-pass" quality. A few obvious extensions, in roughly increasing complexity:

• Merge adjacent collinear lines / cocircular arcs. When the skeleton is split at a junction, two arcs that lie on the same circle are emitted separately. A post-pass that detects "same circle within tolerance" and fuses them would noticeably reduce command count on shapes like the cat face's circle (currently 2 arcs because whisker crossings split it).
• Sequential RANSAC cleanup pass. For each polyline that has a suspiciously high line residual, run a small RANSAC with line and arc models scored by coherent (contiguous-run) inlier count. This handles noisy / hand-drawn input where curvature alone is unreliable.
• Curvature scale space (multigrid). Smooth the polyline at multiple σ values; at the coarsest scale fit dominant primitives (these capture global structure even when locally distorted), commit them, subtract their support, then refine at finer scales. Mokhtarian & Mackworth's CSS framework.
• Global multi-model fitting via PEARL (Isack & Boykov 2012). Replace the greedy classify-segment-by-segment with a graph-cut energy minimization over (line, arc, …) labels with an MDL-flavoured label cost. This trades off model count vs fit quality globally and handles the cat-face-with-whiskers case correctly.
• Better stroke ordering. Greedy NN is fine but suboptimal for many strokes; an Or-Opt / 2-opt pass on the resulting tour would cut pen-up travel by 10-30% on dense drawings.