The Mathematics of Bézier Curves in Vectorization: Schneider's Algorithm & Bernstein Polynomials

1. Parametric Definition of Cubic Bézier Curves

A parametric Bézier curve is a polynomial function defined by an ordered set of control points. While linear Bézier curves represent straight line segments and quadratic curves (used in TrueType fonts) define parabolic arcs, cubic Bézier curves (degree $n = 3$) are the universal standard for modern vector formats including SVG, PostScript, PDF, and OpenType CFF.

A cubic Bézier curve $B(t)$ is formally defined over the normalized parameter range $t \in [0, 1]$ by four control points: start anchor $P_0$, first directional handle $P_1$, second directional handle $P_2$, and end anchor $P_3$:

Where $b_{i,3}(t)$ are the Bernstein basis polynomials of degree 3:

• b_{0,3}(t) = (1 - t)^3
• b_{1,3}(t) = 3(1 - t)^2 t
• b_{2,3}(t) = 3(1 - t) t^2
• b_{3,3}(t) = t^3

Expanding the summation yields the explicit parametric equation for any coordinate $(x(t), y(t))$ on the curve:

2. Essential Geometric Properties

The mathematical formulation of Bézier curves grants them unique characteristics indispensable for computational graphics:

3. Philip J. Schneider's Curve Fitting Algorithm

In raster-to-vector conversion, the input is a sequence of discrete digitized contour points $D = \{d_0, d_1, d_2, \dots, d_m\}$ extracted from pixel boundary polygons. The core challenge is: How do we fit a minimal number of cubic Bézier segments that approximate these points within a user-defined error threshold $\epsilon$?

Pix2Vector implements an enhanced variation of Philip J. Schneider's algorithm (published in Graphics Gems I, Academic Press, 1990):

1. Chord-Length Parameterization: Each digitized point $d_k$ is assigned an initial parameter $u_k \in [0, 1]$ proportional to the cumulative Euclidean distance along the polyline:
   u_k = \frac{\sum_{i=1}^{k} ||d_i - d_{i-1}||}{\sum_{i=1}^{m} ||d_i - d_{i-1}||}
2. Least-Squares Handle Fitting: Anchors $P_0 = d_0$ and $P_3 = d_m$ are fixed. We estimate unit tangent vectors $\hat{v}_1$ and $\hat{v}_2$ at the endpoints and solve for distances $\alpha_1, \alpha_2$ such that:
   P_1 = P_0 + \alpha_1 \hat{v}_1, \quad P_2 = P_3 + \alpha_2 \hat{v}_2
   The scalar distances $\alpha_1, \alpha_2$ are derived by setting the partial derivatives of the sum-of-squared errors $\sum ||B(u_k) - d_k||^2$ with respect to $\alpha_1, \alpha_2$ to zero.
3. Maximum Deviation Check: We find the point $d_k$ with the largest Euclidean distance to the fitted curve:
   E_{max} = \max_{k} ||B(u_k) - d_k||
   If $E_{max} \le \epsilon$, the segment is accepted!
4. Recursive Subdivision: If $E_{max} > \epsilon$, the algorithm splits the point sequence at the index of maximum deviation and recursively fits two separate Bézier curves to each half, guaranteeing $G^1$ continuity at the split junction.

4. Geometric Continuity: G0, G1, and G2

When joining two consecutive Bézier curves $A(t)$ and $B(t)$, the visual smoothness is governed by geometric continuity:

• $G^0$ (Positional Continuity): The end of curve $A$ touches the start of curve $B$ ($A_3 = B_0$). This allows sharp corners and acute architectural angles.
• $G^1$ (Tangential Continuity): The control points $A_2$, $A_3=B_0$, and $B_1$ are collinear. The velocity vectors point in the same direction, eliminating sharp kinks and creating smooth curves.
• $G^2$ (Curvature Continuity): The radius of curvature is continuous across the junction point. This is the hallmark of luxury automotive surfacing and typography, preventing jarring optical reflections.