A bottom-up algorithm for finding principal curves with applications to image skeletonization

This paper proposes a new method for finding principal curves from data sets. Motivated by solving the problem of highly curved and self-intersecting curves, we present a bottom-up strategy to construct a graph called a principal graph for representing a principal curve. The method initializes a set of vertices based on principal oriented points introduced by Delicado, and then constructs the principal graph from these vertices through a two-layer iteration process. In inner iteration, the kernel smoother is used to smooth the positions of the vertices. In outer iteration, the principal graph is spanned by minimum spanning tree and is modified by detecting closed regions and intersectional regions, and then, new vertices are inserted into some edges in the principal graph. We tested the algorithm on simulated data sets and applied it to image skeletonization. Experimental results show the effectiveness of the proposed algorithm.     

改进主曲线及在手写体数字骨架化中应用研究

针对主曲线算法初始化步骤效果差,导致后面所得结果不能正确反映数据的拓扑结构,对其进行改进,用连通k近邻代替第一主成分线找到数据的初始拓扑结构。将改进后的算法应用于脱机手写体数字骨架化,实验证明改进的算法克服了上面提到的缺点,能更好的找到数据的拓扑结构,在时间复杂度、连通性、参数等各方面都优于其他改进算法。改进算法适于具有“连通性”的数据。     

Piecewise linear approximation of plane curves by perimeter optimization

A method for the piecewise linear approximation of a plane curve is described. An approximate curve is obtained by choosing a certain number of points from a set of sampled points of the original curve. A “point choice function” that represents the relation between the original points and the chosen points is formulated. The approximation is performed by the dynamic programming principle searching for the optimal point choice function that attains the minimal error about arc length of the curve. Evaluation of the global approximate error provides efficient curve approximations, irrespective of shape complexity, number of sampled points, and irregularity of sampling interval.     

利用改进的主图形算法提取指纹骨架

在传统的指纹识别系统中,一般使用指纹细化图对指纹信息进行描述。尝试使用主曲线代替指纹细化图,并对主曲线的主图形算法进行了较大改进,使其能够得到更好的指纹骨架。实验结果表明,主曲线骨架比细化图有着光滑性强、准确性高、抗噪音和信息量大的优点;而改进的主图形算法在指纹骨架提取的效率和效果上比原算法也都有一定提高。     

Piecewise linear optimization

Two methods for solving an optimization problem with piecewise linear, convex, and continuous objective function and linear restrictions are described. The first one represents a generalization of the ordinary Simplex-Algorithm by Dantzig, the second one an adaptation of the Reduced Gradient Method by P. Wolfe to the discussed problem. Contrary to the usually employed algorithms, both methods have the advantage of working without an increase of the number of variables or restrictions. An algorithmic presentation and deliberations on the appropriateness of different versions of the methods are provided.     

Piecewise linear quadratic optimal control

The use of piecewise quadratic cost functions is extended from stability analysis of piecewise linear systems to performance analysis and optimal control. Lower bounds on the optimal control cost are obtained by semidefinite programming based on the Bellman inequality. This also gives an approximation to the optimal control law. An upper bound to the optimal cost is obtained by another convex optimization problem using the given control law. A compact matrix notation is introduced to support the calculations and it is proved that the framework of piecewise linear systems can be used to analyze smooth nonlinear dynamics with arbitrary accuracy     

Learning and design of principal curves

Principal curves have been defined as “self-consistent” smooth curves which pass through the “middle” of a d-dimensional probability distribution or data cloud. They give a summary of the data and also serve as an efficient feature extraction tool. We take a new approach by defining principal curves as continuous curves of a given length which minimize the expected squared distance between the curve and points of the space randomly chosen according to a given distribution. The new definition makes it possible to theoretically analyze principal curve learning from training data and it also leads to a new practical construction. Our theoretical learning scheme chooses a curve from a class of polygonal lines with k segments and with a given total length to minimize the average squared distance over n training points drawn independently. Convergence properties of this learning scheme are analyzed and a practical version of this theoretical algorithm is implemented. In each iteration of the algorithm, a new vertex is added to the polygonal line and the positions of the vertices are updated so that they minimize a penalized squared distance criterion. Simulation results demonstrate that the new algorithm compares favorably with previous methods, both in terms of performance and computational complexity, and is more robust to varying data models     

Geometric modeling of curves using weighted linear and circular segments

This paper presents a method for geometric modeling of curves. Linear and circular segments with weight functions are used for curve design. Similar weight functions are used for smoothing and interpolation. The curve can be composed of consecutive linear and circular segments with smoothing at knots. If an interpolating curve is necessary, then weighted linear and circular segments are used for blending. Smoothness of the designed curve depends on the chosen weight function. It is possible to design the curve of variable smoothness using different weight functions.     

Piecewise linear aggregation functions based on triangulation

We introduce a method to construct piecewise linear binary aggregation functions on the unit interval, based on a triangulation of the unit square with one additional vertex. We derive conditions under which such piecewise linear aggregation functions possess additional interesting properties, such as idempotence, symmetry, Lipschitz continuity and 2-monotonicity. This construction method can also be used to approximate binary aggregation functions. In this way, copulas and quasi-copulas are approximated by singular copulas.     

Piecewise linear controller improving its own reliability

Although the capability of neural networks in nonlinear dynamics modelling is well-established, the reliability of the output heavily depends on the training data. The reliability is a serious problem in applying it to real problems. In this paper, we propose a radial basis functions network (RBFN) which evaluates its own reliability and improves itself recursively. This network approximates the input-output relationships with a piecewise linear regression. An adaptive internal model control algorithm in which the reliability of the model is used to tune the controller performance, is also proposed.     

Piecewise linear mapping functions for image registration

A new approach to determination of mapping functions for registration of digital images is presented. Given the coordinates of corresponding control points in two images of the same scene, first the images are divided into triangular regions by triangulating the control points. Then a linear mapping function is obtained by registering each pair of corresponding triangular regions in the images. The overall mapping function is then obtained by piecing together the linear mapping functions.     

Piecewise linear constrained control for continuous-time systems

In the control of linear systems with nonsymmetrical input constraints, larger domains of initialization can be obtained by allowing slow initial dynamics of the system in closed loop and making it faster during its evolution. The positive invariance concept application leads to a piecewise linear constrained control using nonsymmetrical nested polyhedral sets     

Feature-varying skeletonization

Current skeletonization algorithms strive to produce a single centered result which is homotopic and insensitive to surface noise. However, this traditional approach may not well capture the main parts of complex models, and may even produce poor results for applications such as animation. Instead, we approximate model topology through a target feature size ω, where undesired features smaller than ω are smoothed, and features larger than ω are retained into groups called bones. This relaxed feature-varying strategy allows applications to generate robust and meaningful results without requiring additional parameter tuning, even for damaged, noisy, complex, or high genus models.     

Bootstrap confidence intervals for principal response curves

The principal response curve (PRC) model is of use to analyse multivariate data resulting from experiments involving repeated sampling in time. The time-dependent treatment effects are represented by PRCs, which are functional in nature. The sample PRCs can be estimated using a raw approach, or the newly proposed smooth approach. The generalisability of the sample PRCs can be judged using confidence bands. The quality of various bootstrap strategies to estimate such confidence bands for PRCs is evaluated. The best coverage was obtained with BC_a intervals using a non-parametric bootstrap. The coverage appeared to be generally good, except for the case of exactly zero population PRCs for all conditions. Then, the behaviour is irregular, which is caused by the sign indeterminacy of the PRCs. The insights obtained into the optimal bootstrap strategy are useful to apply in the PRC model, and more generally for estimating confidence intervals in singular value decomposition based methods.     

Fingerprint minutiae extraction based on principal curves

It is important to extract minutiae of a fingerprint for the implementation of an auto fingerprint identification system. In this paper, the principal graph algorithm proposed by Kegl is used to obtain principal curves, which can be served as the skeletons of a fingerprint. Based on the obtained principal curves, a minutiae extraction algorithm is proposed to extract minutiae of the fingerprint. The experimental results indicate that principal curves obtained from the principal graph algorithm are smoother than the ones obtained from thinning algorithm, and the minutiae extracted by the proposed algorithm are more efficient.     

Piecewise linear classification using seniority logic committee methods,with application to remote sensing

A committee classification technique based upon a form of seniority decision logic, and which implements piecewise linear decision surfaces, is proposed and a viable training algorithm is presented. The method determines automatically the number of committee members required and is not dependent upon user specified parameters. Examples are given to illustrate the effectiveness of the method using both model data and satellite remote sensing image data.     

Piecewise linear optimization: Duality and numerical results

The dual of an optimization problem with piecewise linear, convex, and continous objective function and linear restrictions is investigated. It is shown that the dual problem is of the same type as the primal and can be solved by the same methods as were proposed in a previous work of the author. Experiences arising from the application of different variants of these methods to solve a number of examples, where the primal as well as the dual version was employed, are reported.     

Piecewise linear mapping algorithm for SAR raw data compression

When the saturation degree （SD） of space-borne SAR raw data is high, the performance of conventional block adaptive quantization （BAQ） deteriorates obviously. In order to overcome the drawback, this paper studies the mapping between the average signal magnitude （ASM） and the standard deviation of the input signal （SDIS） to the A/D from the original reference. Then, it points out the mistake of the mapping and introduces the concept of the standard deviation of the output signal （SDOS） from the A/D. After that, this paper educes the mapping between the ASM and SDOS from the A/D. Monte-Carlo experiment shows that none of the above two mappings is the optimal in the whole set of SD. Thus, this paper proposes the concept of piecewise linear mapping and the searching algorithm in the whole set of SD. According to the linear part, this paper gives the certification and analytical value of k and for nonlinear part, and utilizes the searching algorithm mentioned above to search the corresponding value of k. Experimental results based on simulated data and real data show that the performance of new algorithm is better than conventional BAQ when raw data is in heavy SD.     

一种基于信息熵的时间序列分段线性表示方法

针对部分时间序列具有高维、大数据量及数据更新速度较快的特点, 导致在原始时间序列上难以进行数据挖掘的问题, 提出一种基于信息熵的时间序列分段线性表示方法——PLR_IE。该算法利用信息熵作为评判重要点数量的性能指标, 从序列中提取重要分段点的数量分布情况, 利用重要点组成的序列重新拟合原始时间序列, 为下一步数据挖掘提供基础。实验结果表明, 该方法能高效地提取出序列主要特征、拟合原始序列。     

Piecewise linear solution paths with application to direct weight optimization

Recently, pathfollowing algorithms for parametric optimization problems with piecewise linear solution paths have been developed within the field of regularized regression. This paper presents a generalization of these algorithms to a wider class of problems. It is shown that the approach can be applied to the nonparametric system identification method, Direct Weight Optimization (DWO), and be used to enhance the computational efficiency of this method. The most important design parameter in the DWO method is a parameter (λ) controlling the bias-variance trade-off, and the use of parametric optimization with piecewise linear solution paths means that the DWO estimates can be efficiently computed for all values of λ simultaneously. This allows for designing computationally attractive adaptive bandwidth selection algorithms. One such algorithm for DWO is proposed and demonstrated in two examples.