Skeletonizing: raster lineart into single strokes
✅ verified
What this section is for
Raster lineart is pixels: a line is several pixels wide, and where two lines cross there is a tangle. Painting needs curves: where a stroke starts, where it ends, and how it bends in between. This section turns the white-on-black image into cubic beziers – pare each line down to a one-pixel skeleton, count its endpoints and junctions, walk the skeleton into polylines, and fit those shaky polylines into smooth curves.
Concepts
Skeleton: paring a thick line inward from both sides until only a one-pixel medial axis is left. The paring must not break the line, and must not shorten it at its endpoints.
Endpoints and junctions: every pixel of the skeleton looks at its eight neighbours. One neighbour is an endpoint, two is the middle of a line, three or more is a junction – except that counting neighbours does not hold on a diagonal, for the reason below.
Interpolation and approximation: an interpolating curve passes through every point, so it shakes when the points do; an approximating curve only promises to stay within a tolerance of each point, which absorbs the shake. A stroke wants approximation.
Left: a thick raster line. Middle: the skeleton, with endpoints in green and junctions in red (by crossing number). Right: counting neighbours instead, where every stair on the diagonal becomes a false junction.
How it works
Thinning. Zhang-Suen: each round has two passes, and each pass deletes the boundary pixels that meet its conditions. Write \(P_1\) for the current pixel, \(P_2 \dots P_9\) for its eight neighbours clockwise, \(B(P_1)\) for how many neighbours are foreground, and \(A(P_1)\) for how many 0-to-1 transitions there are going round. The first pass deletes a pixel that satisfies all of
\[ \begin{gathered} 2 \le B(P_1) \le 6, \quad A(P_1) = 1, \\ P_2 \cdot P_4 \cdot P_6 = 0, \quad P_4 \cdot P_6 \cdot P_8 = 0 \end{gathered} \]
and the second pass replaces the last two with \(P_2 P_4 P_8 = 0\) and \(P_2 P_6 P_8 = 0\). \(A = 1\) guarantees that deleting it cannot break the line, the range on \(B\) keeps endpoints and interior pixels, and the last two conditions make the two passes pare from opposite directions so that the skeleton lands on the medial axis. This repeats until no pixel can be deleted.
Pruning whiskers. The short spurs thinning leaves are pruned one pixel per round: remove every endpoint pixel with a single neighbour, three rounds of it, and then thin once more.
Endpoints and junctions, by crossing number. Go round the eight neighbours and count the 0-to-1 transitions:
\[ X(P) = \tfrac12 \sum_{i=1}^{8} |P_{i+1} - P_i|, \quad P_9 = P_1. \]
\(X = 1\) is an endpoint, \(X = 2\) the middle of a line, and \(X \ge 3\) a real junction. Why counting neighbours fails: a stair pixel on a diagonal has three neighbours (the one before, the one after, and the corner), so it is taken for a junction and the diagonal shatters into segments a dozen pixels long. The crossing number counts how many lines leave this pixel, and a stair pixel has only two 0-to-1 transitions going round.
Walking and joining. Start at an endpoint and walk the skeleton to the next endpoint or junction to get a polyline; a closed loop nothing reached starts anywhere. Two segments meeting at a junction whose end directions differ by less than 60 degrees are joined into one – an artist’s stroke passes through a crossing rather than stopping at it. Two segments whose endpoints are within 8 px and whose directions differ by less than 35 degrees are joined too (thinning occasionally breaks a line in two).
Assigning a line layer. A line goes to the line layer of whichever sub-part owns most of the pixels beneath it; anything falling outside the subject is discarded.
Fitting. The polyline’s points \(p_1 \dots p_n\) are first Gaussian-smoothed along arc length with sigma = 1.5, and then fitted into cubic beziers by Schneider’s least squares: the two endpoints and their tangent directions are fixed, every point on the segment is given a parameter \(t_i\) (initially by arc length), and the control points’ distances from the endpoints \(\alpha_1, \alpha_2\) are solved from
\[ \min_{\alpha_1, \alpha_2} \sum_i \big\| B(t_i) - p_i \big\|^2 \]
, a linear least-squares problem in two unknowns. Newton-Raphson then moves each \(t_i\) to the parameter on the curve nearest \(p_i\) and it is solved again; if the largest error still exceeds the tolerance \(\varepsilon\), the polyline is cut in two at the point of greatest error and each half recurses. The tolerance is 1.2 px. Adjacent segments share a tangent direction at their join, so the whole thing is one G1-continuous stroke.
Why smoothing comes first: the fit is controlled by the maximum error, so when the tolerance is below three standard deviations of the noise no segment can contain that noise and it splits all the way down, turning one edge into dozens of segments. Smoothing pushes the noise below the tolerance, and one edge becomes one or two segments.
Breaking at corners. A join where the tangents of two adjacent segments differ by more than 70 degrees is broken – an artist lifts the brush at a corner.
A ruler for smoothness. A curve’s curvature is
\[ \kappa(t) = \frac{x^{\prime} y^{\prime\prime} - y^{\prime} x^{\prime\prime}}{\big((x^{\prime})^{2} + (y^{\prime})^{2}\big)^{3/2}}, \]
Count how many times the curvature changes sign along the curve, divide by its length and multiply by 100, and that is “sign changes per 100 px”. A line a person drew has one or two; a shaky polyline has ten or twenty. It is the smoothness score in arbitration and the ruler for lines at acceptance.
The same shaky points: on the left, interpolation through every one of them; on the right, smoothing followed by a least-squares fit, three segments, with the joins circled.
The method
- Binarize the raster lineart at a threshold and keep only the pixels inside the subject.
- Thin it to one pixel wide, prune whiskers for three rounds, and thin once more.
- Identify endpoints and junctions by crossing number.
- Walk the lines, join them at junctions by direction, and bridge small gaps.
- Give each line to the line layer of whichever sub-part owns most of the pixels beneath it.
- Smooth, fit, break at corners; drop anything shorter than 12 px.
- The width is three tenths of the median line width along it (clamped to 0.35-0.75), and the colour is the darkest pixel beneath the line, darkened.
The candidates come out marked with source “raster lineart” and go into arbitration.
Common problems
| symptom | cause | what to change |
|---|---|---|
| the lines all shatter into a dozen pixels each | junctions were identified by neighbour count, and every stair on a diagonal became one | use the crossing number, which is what it does now |
| one edge becomes dozens of segments | it was not smoothed before fitting, or the tolerance is below the noise | leave the smoothing sigma at 1.5; do not take the tolerance below 1 |
| one stroke through a crossing breaks into two | the angle threshold for joining at a junction is too strict | loosen it beyond 60 degrees |
| thin lines are not caught | the binarization threshold is too high | lower thr |
Further reading
- Code: appendix B, under
lineart– building the AI candidates, the crossing number, tracing and joining at junctions; thinning and fitting are in the geometry layer. - References: T. Y. Zhang and C. Y. Suen, A Fast Parallel Algorithm for Thinning Digital Patterns, Communications of the ACM, 1984, https://dl.acm.org/doi/10.1145/357994.358023; P. J. Schneider, An Algorithm for Automatically Fitting Digitized Curves, Graphics Gems, 1990, with code at https://github.com/erich666/GraphicsGems/tree/master/gems/FitCurves; Ramer-Douglas-Peucker, https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm; the Catmull-Rom spline, https://en.wikipedia.org/wiki/Centripetal_Catmull%E2%80%93Rom_spline.