关键点选取的最小二乘渐进迭代逼近

作者:Zhou Yaqing; Zhang Li*; Wang Jirong; Long Qimeng; Huang Xin; Wu An
来源:Journal of Image and Graphics, 2020, 25(1): 148-157.
DOI:10.11834/jig.190148

摘要

Objective: The progressive-iterative approximation (PIA) method is a widely used data interpolation method in computer-aided design. The algorithm is simple and flexible, and it has an intuitive geometric meaning. The approximation curve can be obtained by continuously iterating and adjusting the control vertices of the curve. Compared with the classical PIA method, the recently given least-squares progressive iterative approximation (LSPIA) method not only inherits the relevant advantages of the original algorithm but also flexibly fits large-scale data points. The method mostly determines the initial control point in the form of uniform parameterization or chord length parameterization. Although good results are obtained, when processing complex curves, the iterative speed is relatively slow and the error precision does not necessarily reach the expected set value. To improve the fitting precision, we present the LSPIA method of gradually increasing the node, and obtain the smaller fitting error by continuously subdividing the nodes. Even if the new fitting procedure can start from the last fitting result, a large number of calculations are still needed. By reasonable selection of the initial control points, the quality of the convergence curve can be improved. To decrease the number of control points and accelerate the convergence, this study proposes a least-squares asymptotic iterative approximation method based on the key points. Specifically, the key points include two categories: local curvature maximum point and extreme curvature point. Considering the curvature information of the data point set to select the initial control vertex, and combining with the uniform selection control point, we retain the flexibility of selecting the number of control points. Method: First, the data points are parameterized, the discrete curvatures of all the data points are calculated based on the discrete curvature calculation formula, and the maximum point of the local curvature is selected. Then, the mean average (avg) of the discrete curvatures of all the data points are found, a suitable initial lower limit of curvature c is set, and the point where the curvature value is greater than c by avg; that is, the extreme curvature point is found. However, in the practice process, the effect of fitting with key points is not good. Careful analysis indicates that for the place where the curve changes drastically, the key points are concentrated and the fitting effect is good. For the smooth part, because extremely few control points are used (certain places have no control points at all), these parts have larger errors. Therefore, we combine two types of control points (uniform control points and key points). Then, because the drawing of the splines is sequential (that is, based on the order in which the control points are arranged), the two sets of control points are often selected separately, resulting in the ordering within the two control point groups, but. However, the merged groups are disordered, and based on the sorting algorithm, the key points and uniformly selected control points are sequentially ordered based on the parameters. Finally, the two types of control points are used as the initial control points of the iteration, and the data points are fitted by the LSPIA method. If the error does not satisfy the previously set value, then the iteration is continued. When the iteration does not satisfy the given precision after reaching a certain number of repetitions, we can increase the initial control points by decreasing the interval of the uniform control points or reducing the lower limit of the key point curvature to improve the fitting accuracy. This method can further decrease the selection of control points, and also compensate for the defects of insufficient fitting of uniform points. For the LSPIA method of gradually increasing the nodes, we continuously refine the nodes based on the error distribution, and we add new nodes and control points by using the incremental algorithm. The results of the previous iteration continue to be iterated using the LSPIA method until the predetermined error accuracy is reached or the number of control points set in advance is reached. Result: We apply our method to the fitting of complex image contours, including deer, bauhinia, cock, and lotus. The LSPIA and key point-based LSPIA methods are used to fit the same set of data points; the method in this study achieves better error precision and improves the convergence speed several times before iteration. Under the same number of control points and compared with the LSPIA algorithm, the proposed method and the step-by-step increase of the LSPIA of the node all improve the error precision to a certain extent, but the method of this study has a smaller calculation amount. Finally, we fit the method to the data point set of ancient paintings. For graphs with many details and high data volume, our method has achieved a good fitting effect. Conclusion: In this study, the key point selection idea is introduced into the LSPIA method, and a least-squares asymptotic iterative approximation method based on key point selection is proposed, thereby improving the selection of initial control vertices and the iterative efficiency. This method is suitable for more complex curves; based on the selection of key points of curvature distribution, the geometric information of the curve can be reflected effectively. Numerical examples show that the LSPIA algorithm combined with the key point screening strategy improves the computational efficiency and achieves an improved fitting effect. This method can be adopted in the case in which the iterative efficiency requirement is relatively high in real life. ? 2020, Editorial and Publishing Board of Journal of Image and Graphics. All right reserved.

全文