Subdivision schemes are used to generate smooth curves or surfaces by iteratively refining an initial control polygon or mesh. We focus on univariate, linear, binary subdivision schemes, where the vertices of the refined polygon are computed as linear combinations of the current neighbouring vertices. In the classical stationary setting, there are just two such subdivision rules, which are used throughout all subdivision steps to construct the new vertices with even and odd indices, respectively. These schemes are well understood and many tools have been developed for deriving their properties, including the smoothness of the limit curves. For non-stationary schemes, the subdivision rules are not fixed and can be different in each subdivision step. Non-uniform schemes are even more general, as they allow the subdivision rules to be different for every new vertex that is generated by the scheme. The properties of non-stationary and non-uniform schemes are usually derived by relating the scheme to a corresponding stationary scheme and then exploiting the fact that the properties of the stationary scheme carry over under certain proximity conditions. In particular, this approach can be used to show that the limit curves of a non-stationary or non-uniform scheme are as smooth as those of a corresponding stationary scheme. In this paper we show that non-uniform subdivision schemes have the potential to generate limit curves that are smoother than those of stationary schemes with the same support size of the subdivision rule. For that, we derive interpolatory 2-point and 4-point schemes that generate C1 and C2 limit curves, respectively. These values of smoothness exceed the smoothness of classical interpolating schemes with the same support size by one.

Subdivision is a well-known and established method for generating smooth curves and surfaces from discrete data by repeated refinements. The typical input for such a process is a mesh of vertices. In this work we propose to refine 2D data consisting of vertices of a polygon and a normal at each vertex. Our core refinement procedure is based on a circle average , which is a new non-linear weighted average of two points and their corresponding normals. The ability to locally approximate curves by the circle average is demonstrated. With this ability, the circle average is a candidate for modifying linear subdivision schemes refining points, to schemes refining point-normal pairs. This is done by replacing the weighted binary arithmetic means in a linear subdivision scheme, expressed in terms of repeated binary averages, by circle averages with the same weights. Here we investigate the modified Lane–Riesenfeld algorithm and the 4-point scheme. For the case that the initial data consists of a control polygon only, a naive method for choosing initial normals is proposed. An example demonstrates the superiority of the above two modified schemes, with the naive choice of initial normals over the corresponding linear schemes, when applied to a control polygon with edges of significantly different lengths.

We present a new image coding algorithm, the geometric piecewise polynomials (GPP) method, that draws on recent developments in the theory of adaptive multivariate piecewise polynomials approximation. The algorithm relies on a segmentation stage whose goal is to minimize a functional that is conceptually similar to the Mumford-Shah functional except that it measures the smoothness of the segmentation instead of the length. The initial segmentation is "pruned" and the remaining curve portions are lossy encoded. The image is then further partitioned and approximated by low order polynomials on the subdomains. We show examples where our algorithm outperforms state-of-the-art wavelet coding in the low bit-rate range. The GPP algorithm significantly outperforms wavelet based coding methods on graphic and cartoon images. Also, at the bit rate 0.05 bits per pixel, the GPP algorithm achieves on the test image Cameraman, which has a geometric structure, a PSNR of 21.5 dB, while the JPEG2000 Kakadu software obtains PSNR of 20 dB. For the test image Lena, the GPP algorithm obtains the same PSNR as JPEG2000, but with better visual quality at 0.03 bpp.

A new interpolatory subdivision scheme for surface design is presented. The new scheme is designed for a general triangulation of control points and has a tension parameter that provides design flexibility. The resulting limit surface is C 1 for a specified range of the tension parameter, with a few exceptions. Application of the butterfly scheme and the role of the tension parameter are demonstrated by several examples.