SCIENTIA SINICA Informationis, Volume 51 , Issue 8 : 1255(2021) https://doi.org/10.1360/SSI-2020-0360

Automatic $\rm~G_{~}^{1}$ arc spline approximation via sparse representation

More info
  • ReceivedNov 29, 2020
  • AcceptedMar 4, 2021
  • PublishedAug 3, 2021


Funded by




变换矩阵 $\mathcal{T}$ 和 $\mathcal{D}$ 的计算

变换矩阵 $\mathcal{T}$ 和 $\mathcal{D}$ 对于圆弧样条初始化非常重要, 这里给出详细的计算方法.

sect. 3.3 小节中, 曲率的离散公式 1 关于数据点已经是非线性的, 拟梯度变换矩阵 肯定更加复杂.

为了得到矩阵 $\mathcal{T}$ 的显式表达, 进而有效求解问题 eq:ASinitial, 输入点序列 $P$, ${P}=(x_1,~\ldots,~x_n,~y_1,~\ldots,~y_n)_{}^{\rm~T}$, 通过定义下面两个系数: \begin{equation}\begin{aligned} z_{i}^{x}&=\frac{x_{i+1}-x_{i}} {((x_{i+1}-x_{i})^2+(y_{i+1}-y_{i})^2)^{\frac{3}{2}}}, \\ z_{i}^{y}&=\frac{y_{i+1}-y_{i}} {((x_{i+1}-x_{i})^2+(y_{i+1}-y_{i})^2)^{\frac{3}{2}}}, \end{aligned} \tag{15}\end{equation}1 变成 \begin{equation*}\begin{aligned} \kappa({\boldsymbol p}_i)&=z_{i}^{x}(y_{i+1}-2y_{i}+y_{i-1})- z_{i}^{y}(x_{i+1}-2x_{i}+x_{i-1}) \\ &=-z_{i}^{y}x_{i-1}+2z_{i}^{y}x_{i}-z_{i}^{y}x_{i+1}+z_{i}^{x}y_{i-1}-2z_{i}^{x}y_{i}+z_{i}^{x}y_{i+1} \\ &=\mathcal{T}_{i}P, \end{aligned}\end{equation*} 将 $z_{i}^{x}$, $z_{i}^{y}$ 作为常值系数,很容易构造矩阵 $\mathcal{T}$, 第 $i$ 行非零元素 $\mathcal{T}_i$ 对应点 ${\boldsymbol~p}_i$: \begin{equation}(-z_{i}^{y}, 2z_{i}^{y}, -z_{i}^{y}, z_{i}^{x}, -2z_{i}^{x}, z_{i}^{x}). \tag{16}\end{equation} 实际上, 为了避免下标越界, 不考虑 ${\boldsymbol~p}_1$ 和 ${\boldsymbol~p}_2$ 两点, 最终矩阵 $\mathcal{T}_i$ 的大小为 $(n-2)\times~2n$, 对逼近结果没有影响.

类似地, 拟梯度为 \begin{equation}\begin{aligned} \bigtriangledown{\kappa_{i}^{{\boldsymbol p}}} &=\kappa({\boldsymbol p}_{i+1})-\kappa({\boldsymbol p}_{i}) \\ &=z_{i}^{y}x_{i-1}-(z_{i+1}^{y}+2z_{i}^{y})x_{i}+(2z_{i+1}^{y}+z_{i}^{y})x_{i+1}-z_{i+1}^{y}x_{i+2} \\ & -z_{i}^{x}y_{i-1}+(z_{i+1}^{x}-2z_{i}^{x})y_{i}-(2z_{i+1}^{x}+z_{i}^{x})y_{i+1}+z_{i+1}^{x}y_{i+2} \\ &=\mathcal{D}_{i}P, \end{aligned} \tag{17}\end{equation} 矩阵 $\mathcal{D}$ 第 $i$ 行非零元素 $\mathcal{D}_i$ 为 \begin{equation}( z_{i}^{y}, -z_{i+1}^{y}-2z_{i}^{y}, 2z_{i+1}^{y}+z_{i}^{y}, -z_{i+1}^{y}, -z_{i}^{x}, z_{i+1}^{x}-2z_{i}^{x}, -2z_{i+1}^{x}-z_{i}^{x}, z_{i+1}^{x}). \tag{18}\end{equation} 大小为 $(n-3)\times~2n$, 忽略 ${\boldsymbol~p}_1$, ${\boldsymbol~p}_2$ 和 ${\boldsymbol~p}_3$ 三点.

以图 1 中圆弧样条上的采样点为例, 矩阵 $\mathcal{T}$ 和 $\mathcal{D}$ 的有效性如图 1 所示.


[1] Bolton K M. Biarc curves. Comput-Aided Des, 1975, 7: 89-92 CrossRef Google Scholar

[2] Chen X D, Yong J H, Zheng G Q. Automatic G1 arc spline interpolation for closed point set. Comput-Aided Des, 2004, 36: 1205-1218 CrossRef Google Scholar

[3] Walton D J, Meek D S. Approximation of quadratic Bézier curves by arc splines. J Comput Appl Math, 1994, 54: 107-120 CrossRef Google Scholar

[4] Yeung M K, Walton D J. Curve fitting with arc splines for NC toolpath generation. Comput-Aided Des, 1994, 26: 845-849 CrossRef Google Scholar

[5] Yong J H, Hu S M, Sun J G. Bisection algorithms for approximating quadratic Bézier curves by G1 arc splines. Comput-Aided Des, 2000, 32: 253-260 CrossRef Google Scholar

[6] Maier G. Optimal arc spline approximation. Comput Aided Geometric Des, 2014, 31: 211-226 CrossRef Google Scholar

[7] Zongben Xu , Jian Sun . Image Inpainting by Patch Propagation Using Patch Sparsity. IEEE Trans Image Process, 2010, 19: 1153-1165 CrossRef PubMed ADS Google Scholar

[8] Elad M. Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. New York: Springer, 2010. Google Scholar

[9] Parkinson D B, Moreton D N. Optimal biarc-curve fitting. Comput-Aided Des, 1991, 23: 411-419 CrossRef Google Scholar

[10] Meek D S, Walton D J. Approximation of discrete data by G1 arc splines. Comput-Aided Des, 1992, 24: 301-306 CrossRef Google Scholar

[11] Meek D S, Walton D J. Approximating quadratic NURBS curves by arc splines. Comput-Aided Des, 1993, 25: 371-376 CrossRef Google Scholar

[12] Ong C, Wong Y, Loh H. An optimization approach for biarc curve-fitting of B-spline curves. Comput-Aided Des, 1996, 28: 951-959 CrossRef Google Scholar

[13] Held M, Eibl J. Biarc approximation of polygons within asymmetric tolerance bands. Comput-Aided Des, 2005, 37: 357-371 CrossRef Google Scholar

[14] Meek D S, Walton D J. The family of biarcs that matches planar, two-point G1 Hermite data. J Comput Appl Math, 2008, 212: 31-45 CrossRef Google Scholar

[15] Ahn Y J, Kim H O, Lee K Y. G1 arc spline approximation of quadratic Bézier curves. Comput-Aided Des, 1998, 30: 615-620 CrossRef Google Scholar

[16] Marciniak K, Putz B. Approximation of spirals by piecewise curves of fewest circular arc segments. Comput-Aided Des, 1984, 16: 87-90 CrossRef Google Scholar

[17] Meek D S, Walton D J. An arc spline approximation to a clothoid. J Comput Appl Math, 2004, 170: 59-77 CrossRef Google Scholar

[18] Yang X. Efficient circular arc interpolation based on active tolerance control. Comput-Aided Des, 2002, 34: 1037-1046 CrossRef Google Scholar

[19] Kim T, Kim Y, Suh J. Internal energy minimization in biarc interpolation. Int J Adv Manuf Technol, 2009, 44: 1165-1174 CrossRef Google Scholar

[20] Yang X N. Approximating NURBS curves by arc splines. In: Proceedings of Geometric Modeling and Processing, 2000. 175--183. Google Scholar

[21] Piegl L A, Tiller W. Data Approximation Using Biarcs. Eng Comput, 2002, 18: 59-65 CrossRef Google Scholar

[22] Piegl L A, Tiller W. Biarc approximation of NURBS curves. Comput-Aided Des, 2002, 34: 807-814 CrossRef Google Scholar

[23] Maier G, Pisinger G. Approximation of a closed polygon with a minimum number of circular arcs and line segments. Comput Geometry, 2013, 46: 263-275 CrossRef Google Scholar

[24] Wright J, Ma Y, Mairal J. Sparse Representation for Computer Vision and Pattern Recognition. Proc IEEE, 2010, 98: 1031-1044 CrossRef Google Scholar

[25] Bishop C M. Pattern Recognition and Machine Learning. Berlin: Springer, 2006. Google Scholar

[26] Kaufmann M. Data Mining Practical Machine Learning Tools and Techniques. San Francisco: Morgan Kaufmann, 2005. Google Scholar

[27] Mallat S. A Wavelet Tour of Signal Processing: The Sparse Way. Burlington: Academic, 2008. Google Scholar

[28] Bruckstein A M, Donoho D L, Elad M. From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images. SIAM Rev, 2009, 51: 34-81 CrossRef ADS Google Scholar

[29] Waydo S, Kraskov A, Quian Quiroga R. Sparse representation in the human medial temporal lobe.. J Neuroscience, 2006, 26: 10232-10234 CrossRef PubMed Google Scholar

[30] Rinberg D. Sparse odor coding in awake behaving mice.. J Neuroscience, 2006, 26: 8857-8865 CrossRef PubMed Google Scholar

[31] Vapnik V N. An overview of statistical learning theory.. IEEE Trans Neural Netw, 1999, 10: 988-999 CrossRef PubMed Google Scholar

[32] Vapnik V. The Nature of Statistical Learning Theory. New York: Springer, 2013. Google Scholar

[33] Hastie T, Tibshirani R, Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. New York: Springer, 2009. Google Scholar

[34] Xu L, Wang R, Zhang J. Survey on sparsity in geometric modeling and processing. Graphical Model, 2015, 82: 160-180 CrossRef Google Scholar

[35] Digne J, Chaine R, Valette S. Self-similarity for accurate compression of point sampled surfaces. Comput Graphics Forum, 2014, 33: 155-164 CrossRef Google Scholar

[36] Avron H, Sharf A, Greif C. ACM Trans Graph, 2010, 29: 1-12 CrossRef Google Scholar

[37] He L, Schaefer S. ACM Trans Graph, 2013, 32: 1-8 CrossRef Google Scholar

[38] Wang R, Yang Z, Liu L. ACM Trans Graph, 2014, 33: 1-12 CrossRef Google Scholar

[39] Xu L, Wang R, Yang Z. Surface approximation via sparse representation and parameterization optimization. Comput-Aided Des, 2016, 78: 179-187 CrossRef Google Scholar

  • Figure 1

    (Color online) The sparsity in arc spline.(a) $\rm~G_{}^{1}$ continuous arc spline (curve) and sampling points (black points);(b) curvatures of sampling points;(c) the quasi gradients of the sampling points, where the nonzero values correspond to joint points

  • Figure A1

    (Color online) The effectiveness of transformation matrix. (a) Theoretical curvature values of sampling points. (b) Theoretical quasi gradient values of curvatures. (c) Approximate curvature values calculated by transformation matrix $\mathcal{T}$. (d) Approximate quasi gradient values of curvatures calculated by transformation matrix $\mathcal{D}$. Except for a few redundant points, the approximate values are consistent with the theoretical values. In the actual optimization process, the redundant points are processed according to the method described in Figure 5without affecting the approximation results

  • Figure 2

    (Color online) Arc spline approximation based on sparse representation. Given an ordered data set (a), the optimization aims for as few arcs (b) as possible to approximate (a). $A_j$ is the $j$-th arc corresponding to two joint points ${\boldsymbol~s}_{j}$ and ${\boldsymbol~s}_{j+1}$. $P({\boldsymbol~s}_{j},{\boldsymbol~s}_{j+1})$ indicates the data points in $P$ between ${\boldsymbol~s}_{j}$ and ${\boldsymbol~s}_{j+1}$

  • Figure 3

    (Color online) The sparsity of curvature radiuses at sampling points on the arc spline in Figure 1(a). (a) Curvature radiuses of sampling points; (b) quasi gradients of curvature radiuses

  • Figure 4

    (Color online) The flow chart of automatic $\rm~G_{}^{1}$ continuous arc spline approximation based on sparse representation.Given a set of data points (a), the global $\ell_1$ sparse optimization problem eq:ASinitialautomatically segments (a) to initialize the arc spline (b), coupled with the local modification of joint points (c), the $\rm~G_{}^{1}$ continuous arc spline is obtained

  • Figure 5

    (Color online) S explanation of $\ell_1$ sparse optimization problem. Input the sampling points of leaf curve (Figure 4(a)), (a) is the approximation point set by solving problem eq:ASinitial. Its curvature (b) and quasi gradient (c) are computed respectively with transformations $\mathcal{T}$ and $\mathcal{D}$. Compared with the theoretical performance in Figure 1, there are a few redundant points which will be grouped to any neighboring arc

  • Figure 6

    (Color online) The trend of the optimization error of the leaf line (Figure 4)

  • Figure 7

    (Color online) The approximation results of Bézier curves in bisection algorithm [5]using our method. protectłinebreak (a) Bézier curve 1; (b) Bézier curve 2

  • Figure 8

    (Color online) Approximation results of more types of curves. (a) B-spline 1; (b) B-spline 2;(c) polynomial; (d) plum line; (e) loop line; (f) section contour of Eight model

  • Table 1   The approximation data comparison of our method and the bisection algorithm
    Bézier curves$N_{\rm~Arc}$$e$
    Our method Bisection algorithm [5] Our method Bisection algorithm [5]
    Bézier curve 1 5 10 $5.0159\times10^{-7}$ $1.0000\times10^{-3}$
    Bézier curve 2 2 14 $6.4544\times10^{-5}$ $9.6696\times10^{-5}$

    Algorithm 1 Sparse arc spline approximation

    Require:Sampling points $P$ of curves;

    Step 1. Global sparse arc spline approximation;

    Read the sampling points $P$ and calculate $C$, $R$, $\{i_l\}_{l=1}^{m+1}$ by eq:ASinitial;

    Step 2. Local modification;

    Modify joint points $S$ and $\{C,R\}$ using Gauss-Seidel method;

    Step 2.1. Fix $\{C,R\}$ and solve $S$-subproblem;

    Update $\{i_l\}_{l=1}^{m+1}$ by finding the subscript of the closest point according to the location of the joint point;

    Step 2.2. Fix $S$ and introduce auxiliary variable $U$; $U$ and $\{C,R\}$ are solved after three iterations;

    Update the center and radius of each arc according to the new joint points.

    After Steps 2.1 and 2.2 iterate about 8 times, the algorithm converges and outputs;Output: Centers $C$, radiuses $R$, subscripts $\{i_l\}_{l=1}^{m+1}$ of joint points, approximation error $e$.

  • Table 2   Experimental data $^{\rm~a)}$
    Curves $N_P$ $\varepsilon$ $N_{\rm~Arc}$ $e$ $t$ (s)
    Bézier curve 1 1000 0.0001 5 $5.0159\times10^{-7}$ 15.0975
    Bézier curve 2 1000 0.0005 2 $6.6544\times10^{-5}$ 12.3846
    Leaf line 1000 0.0001 7 $4.7171\times10^{-7}$ 16.9222
    B-spline 1 1000 0.0008 9 $5.8841\times10^{-6}$ 16.7884
    B-spline 2 1000 0.0008 11 $8.7299\times10^{-6}$ 22.1343
    Polynomial 2000 0.0001 8 $2.8000\times10^{-3}$ 20.1243
    Plum line 4700 0.00008 30 $2.9000\times10^{-3}$ 76.8150
    Loop line 1000 0.0008 7 $1.3867\times10^{-5}$ 13.3155
    Section contour of Eight model 1000 0.0001 20 $3.3010\times10^{-8}$ 32.7293



Contact and support