Non-stationary Subdivision Schemes: State of the Art and Perspectives

Abstract

This paper reviews the state of the art of non-stationary subdivision schemes, which are iterative procedures for generating smooth objects from discrete data, by repeated level dependent linear refinements. In particular the paper emphasises the potentiality of these schemes and the wide perspective they open, in comparison with stationary schemes based on level-independent linear refinements.

1 Introduction

Subdivision schemes were created originally to design geometrical models (see [4, 6, 30, 35],) but very soon they were recognised as methods for approximation (see [5, 36]). They are iterative methods for the generation of sets of points based on refinement rules that can be easily and efficiently implemented on a computer.

Since the 90s, subdivision schemes attracted many scientists for both the simplicity of their basic ideas and the mathematical elegance emerging in their analysis: they are defined by repeatedly applying simple and local refinement rules which have been extended to refine other objects such as vectors, matrices, manifold data, sets of points, curves, nets of functions. Therefore, the domain of application of subdivision is vast and they emerge in different contexts ranging from computer animation [31] to motion analysis [57].

The most studied subdivision schemes are linear and stationary (level independent). A nice aspect of linear subdivision schemes is that many of their properties can be translated into algebraic properties of Laurent polynomials. This makes their analysis easy and efficient. Moreover, since these schemes can be viewed as repeated multiplication by matrices, many analysis tools are based on linear algebra such as the “joint spectral radius” of two matrices (see [61]). Linear subdivision schemes are the subject of this survey paper. First we review the stationary schemes, and then in more details the non-stationary ones.

Stationary schemes are characterised by repeatedly applying the same simple and local refinement rule while the non-stationary (or level dependent) schemes apply a different rule in each level of refinement. Yet, changing rules with the levels is not a big difference from an implementation point of view, also in consideration that, realistically, only few subdivision iterations are executed. Contrary, from a theoretical point of view, non-stationary schemes are certainly more difficult to analyse. Level-dependent schemes were introduced to augment the class of limit functions defined through stationary schemes. For example, they allow the definition of C ^∞ compactly supported functions like the Rvachev function (see, e.g. [39]) or exponential B-splines.

This type of limits shows that non-stationary schemes alleviate the limitations of stationary schemes that the smoothness of their limits of minimal compact support is bounded by the size of that support.

The non-stationary schemes are essentially different from the stationary ones: non-stationary schemes are able to generate conic sections, or to deal with level-dependent tension parameters for modifying the shape of a subdivision limit, while the stationary ones are not. An example of level-dependent subdivision schemes is given by Hermite schemes that allow to model curves and surfaces involving their gradient fields. They are interesting both in geometric modelling and biological imaging [1, 2, 14, 24, 65]. Additionally, non-stationary subdivision schemes play a role in the construction of non-stationary wavelet and framelets whose adaptivity makes them more flexible (see [13, 26, 42, 46, 67]). Last, but not least, level-dependent rules have the potential to overcome the standard limitations of subdivision surfaces such as artefacts and low regularity at extraordinary vertices/faces (see [64] for the limitations).

The paper is organised as follows: Sect. 2 provides a general description of the subdivision ideas together with classical examples of univariate and bivariate linear and stationary subdivision schemes. Also, the section presents a short description of the main subdivision applications and a review of the analysis tools of stationary linear schemes. Then, in Sect. 3 non-stationary subdivision schemes are discussed with emphasis on the motivation for their use. Section 4 is devoted to the analysis tools specific for non-stationary subdivision schemes, while the closing Sect. 5 presents open problems in the non-stationary setting.

2 Classical Subdivision Schemes

Subdivision schemes are efficient iterative methods for generating limit objects from discrete sets of data: Given $\mathcal {D}_0$—an initial set of data—the procedure iteratively defines a sequence of denser and denser sets of data $\{\mathcal {D}_k\}_{k\ge 0}$

$$\displaystyle \begin{aligned}{\mathcal D}_0 \ \ \underbrace{\longrightarrow}_{\mathsf{{ref. \, rule}}} \ \ {\mathcal D}_1 \ \ \ \underbrace{\longrightarrow}_{\mathsf{{ref. \, rule}}}\ \ {\mathcal D}_2 \ \ \cdots \ \ \ \underbrace{\longrightarrow}_{\mathsf{{ref. \, rule}}} \ \ {\mathcal D}_{k}\end{aligned}$$

by suitable refinement rules which can be linear or non-linear, level dependent or level independent, given by a formula or a geometric construction, just to mention some possibilities. Whenever $\lim _{k \rightarrow \infty } \, \mathcal {D}_k$ exists, in a sense to be explained later, it is the subdivision limit generated by the scheme.

At the early stage of the study of subdivision schemes, the initial set $\mathcal {D}_0$ consisted mainly of points, but in the last 30 years, subdivision was extended to more abstract settings, such as vector fields, manifold valued data, matrices, sets, curves or nets of functions. Examples of different possibilities are shown in the next figures after three refinement steps of a point subdivision scheme, a net subdivision scheme and a mesh subdivision scheme, respectively (Figs. 1, 2, 3).

Fig. 1

Example of refinement of real values with limit a bivariate function

Fig. 2

Example of refinement of nets of curves with limit a surface

Fig. 3

Example of refinement of meshes with limit a surface

2.1 Binary, Linear, and Stationary Subdivision Schemes

The classical schemes are binary, linear, and stationary. We start with univariate schemes refining sequences of real values or of points in $\mathbb {R}^d$. The extension to the refinement of real values or of points given at the vertices of a regular mesh is the first step towards the bivariate case, which is of great importance for the generation of smooth surfaces.

Given a mask consisting of a finite set of real coefficients $\mathbf {a}=\{a_i, i\in I\},\ I\subset \mathbb {Z}, |\, I\, |<\infty$, the associated linear subdivision operator transforming a sequence p of points in $\mathbb {R}$ into a refined sequence of points in $\mathbb {R}$ is

$$\displaystyle \begin{aligned} {\mathcal{S}}_{\mathbf{a}}: \ell(\mathbb{Z})\rightarrow \ell(\mathbb{Z})\qquad ({\mathcal{S}}_{\mathbf{a}}(\mathbf{p}))_i:=\sum_{j\in \mathbb{Z}}a_{i-2j}p_j,\quad j\in \mathbb{Z}. \end{aligned} $$

(1)

The refinement rule (1) encompasses two rules, one for the even indices, and one for the odd indices

$$\displaystyle \begin{aligned}({\mathcal{S}}_{\mathbf{a}}(p))_{2i}:=\sum_{j\in \mathbb{Z}}a_{2j}p_{i-j},\quad ({\mathcal{S}}_{\mathbf{a}}(p))_{2i+1}:=\sum_{j\in \mathbb{Z}}a_{2j+1}p_{i-j},\quad j\in \mathbb{Z}. \end{aligned}$$

In the following, without loss of generality, we assume that I = {0, …, N}, for some $N\in \mathbb {N}$.

The subdivision scheme is simply the repeated application of the subdivision operator starting from an initial sequence of points p ^[0]:

$$\displaystyle \begin{aligned} \left\{ \begin{array}{ll} \mbox{Input}\quad \mathbf{a}, \ \ {p}^{[0]}&\\ \mbox{For}\quad k=0,1,\dots &\\ \qquad \quad {p^{[k+1]} }:= S_{\mathbf{a}}{p}^{[k]} \end{array} \right. \end{aligned} $$

(2)

The points in the sequence ${\mathbf {p}}^{[k]}=\{p_i^{[k]}\}_{i\in \mathbb {Z}}$ are attached to the parametrization $\{t_i^{[k]}\}_{i\in \mathbb {Z}}$ ($t_i^{[k]}<t_{i+1}^{[k]},\ i\in \mathbb {Z}$), namely $p_i^{[k]}$ is attached to the parameter value $t_i^{[k]}$.

The scheme defined in (2), also denoted by S _a, is called convergent if for any p ^[0] there exists a continuous function $f_{{\mathbf {p}}^{[0]}}$, such that

$$\displaystyle \begin{aligned} \lim_{k\rightarrow \infty}\sup_{i\in \mathbb{Z}}|\ f_{{\mathbf{p}}^{[0]}}( t_i^{[k]})-p^{[k]}_i\ |=0, \end{aligned} $$

(3)

with $f_{{\mathbf {p}}^{[0]}}\not \equiv 0$ for at leat one initial sequence p ^[0]≢0. The limit is also denoted by ${\mathcal { S}}^\infty _{\mathbf {a}}({\mathbf {p}}^{[0]})$. In case the limit function $f_{{\mathbf {p}}^{[0]}}$ is a $\mathcal {C}^\ell$ function for any p ^[0] the scheme is said to be $\mathcal {C}^\ell$-regular.

We will restrict our attention to non singular subdivision schemes, i.e. convergent schemes such that

$$\displaystyle \begin{aligned} {\mathcal{S}}^\infty({\mathbf{p}}^{[0]})\equiv 0\quad \Leftrightarrow \quad p^{[0]}_i=0\quad \mbox{for all}\quad i\in \mathbb{Z}. \end{aligned}$$

The limit obtained starting with the delta-sequence $\boldsymbol {\delta }=\{\delta _{0,i}\}_{i\in \mathbb {Z}}$, $\phi _{\mathbf {a}}:=\mathcal { S}_{\mathbf {a}}^\infty (\boldsymbol {\delta })$, usually called the basic limit function of the scheme, is of great importance. Indeed, by the linearity of the operator $\mathcal {S}_{\mathbf {a}}$ we have that

$$\displaystyle \begin{aligned} f_{{\mathbf{p}}^{[0]}}=\sum_{j\in \mathbb{Z}}p^{[0]}_j\phi_{\mathbf{a}}(\cdot-j). \end{aligned} $$

(4)

Thus, the smoothness of the scheme S _a is the smoothness of its basic limit function.

Most classical subdivision schemes are either primal or dual. In the primal case at each iteration the scheme retains or modifies the ‘old’ points and creates a ‘new’ point situated in the sequence in between two consecutive ‘old’ ones. In the dual case, S _a discards all given points after creating two new ones in between any pair of consecutive ‘old’ points. Algebraically, this is related to the choice of the parameters to which we attach the points generated by the scheme: the primal parametrization is such that $t_{i}^k=i\,2^{-k}$ for k ≥ 1 and $t_{i}^{[0]}=i,\ i\in \mathbb {Z}$, while in the dual one $t_{i}^{[k]}=(i-\frac {1}{2})\, 2^{-k}$ for k ≥ 1 and $t_{i}^{[0]}=i,\ i\in \mathbb {Z}$. To unify the primal and the dual cases, we here consider the parameter values $t_{i}^{[k]}=(i+\tau )\, 2^{-k}$ for k ≥ 1 and $t_{i}^{[0]}=i,\ i\in \mathbb {Z}$ and call τ the parametric shift of the scheme. Note that in view of (1) and the parametrizations of the primal and dual cases, the support of ϕ _a is contained in [0, N] (see e.g. [39]).

The parameterization is important for example when considering reproduction capabilities of subdivision schemes, discussed next.

A convergent subdivision scheme S _a with parameter shift τ reproduces a function space $\mathcal V$, if for any $g \in \mathcal {V}$, the initial sequence

$$\displaystyle \begin{aligned} {\mathbf{p}}^{[0]}:=\lbrace g(j+\tau)\in \mathbb{R}\rbrace_{j \in \mathbb{Z}} \end{aligned} $$

(5)

guarantees that ${\mathcal {S}}^\infty _{\mathbf {a}}({\mathbf {p}}^{[0]})\equiv g$. Moreover it stepwise reproduces $\mathcal V$ if at each step k, the refined sequence p ^[k] is of the form

$$\displaystyle \begin{aligned} {\mathbf{p}}^{[k]}=\lbrace g((j+\tau)\, 2^{-k})\rbrace_{j \in \mathbb{Z}},\quad \mbox{for all}\quad k\ge 1. \end{aligned} $$

(6)

From the above it obviously follows that stepwise-$\mathcal V$-reproduction implies $\mathcal V$-reproduction in case convergence is guaranteed.

Reproduction of polynomials of degree less or equal to n, namely corresponding to $\mathcal {V}\equiv \varPi _n$, is closely related to the approximation order of the subdivision scheme $\mathcal {S}_{\mathbf {a}}$. The approximation order measures the rate by which the limit functions generated by $\mathcal {S}_{\mathbf {a}}$ (from initial data sampled from a sufficiently smooth function f) get closer to f as the sampling density tends to zero. In other words, the approximation order of $\mathcal {S}_{\mathbf {a}}$ is the largest exponent r such that for all $f\in \mathcal {C}^r$

$$\displaystyle \begin{aligned}\|f-{\mathcal{S}}^\infty_{\mathbf{a}}({\mathbf{f}}^{[0]})(\frac{\cdot}{h})\|{}_\infty\le c\, h^r,\quad \mbox{for}\quad {\mathbf{f}}^{[0]}=\{f(ih)\}_{i\in \mathbb{Z}}, \end{aligned}$$

with c a constant independent of h.

It is easy to prove that subdivision schemes that reproduces Π _n have approximation order r = n + 1 (see the proof in [37] for the 4-point scheme).

A weaker notion of reproduction is the notion of generation of a function space $\mathcal {V}$: It guarantees that for any $g \in \mathcal {V}$ and initial sequence (5)

$$\displaystyle \begin{aligned} {\mathcal{S}}_{\mathbf{a}}({\mathbf{p}}^{[0]})\in \mathcal{V}. \end{aligned} $$

(7)

The generation of Π _n by $\mathcal {S}_a$ is a necessary condition for the scheme to be C ⁿ-regular when ϕ _a is L _∞-stable (see [39, Theorem 4.16 and (4.20)]), namely when $C_1 \|b\|{ }_{L_\infty }\le \|\sum _{\alpha \in \mathbb {Z}}b_\alpha \phi _a(\cdot -\alpha ) \|{ }_{L_\infty }\le C_2\|b\|{ }_{L_\infty }$ with C ₁, C ₂ positive constants independent of $b=\{b_\alpha \}_{\alpha \in \mathbb {Z}}$.

Extension of the univariate case to dimensions s ≥ 2 is straightforward when the topology is that of the regular mesh $\mathbb {Z}^s$. Here we consider the case d = 2.

Bivariate linear, stationary and binary subdivision operators for regular meshes are defined similarly to (1) as

$$\displaystyle \begin{aligned} {\mathcal{S}}_{\mathbf{a}}: \ell(\mathbb{Z}^2)\rightarrow \ell(\mathbb{Z}^2)\qquad ({\mathcal{S}}_{\mathbf{a}}(\mathbf{p}))_\alpha=\sum_{\beta\in \mathbb{Z}^2}a_{\alpha-2\beta}p_\beta,\quad \alpha\in \mathbb{Z}^2. \end{aligned} $$

(8)

In (8) there are four different refinement rules determined by the parity of the indices $\alpha =(\alpha _1,\alpha _2)\in \mathbb {Z}^2$. Hence, an equivalent form of (8) is

$$\displaystyle \begin{aligned}({\mathcal{S}}_{\mathbf{a}}(\mathbf{p}))_{2\alpha+\epsilon}=\sum_{\beta\in \mathbb{Z}^2}a_{2\beta+ {\boldsymbol\epsilon}}p_{\alpha-\beta},\quad \alpha\in \mathbb{Z}^2, \quad {\boldsymbol\epsilon}\in \varXi_2,\end{aligned}$$

where

$$\displaystyle \begin{aligned}\varXi_2=\{0,1\}^2=\{(0,0),\ (0,1),\ (1,0),\ (1,1)\}, \end{aligned} $$

(9)

is the set of representative indices of a binary scheme. The subdivision limit is still a linear combination of shifts of its bivariate basic limit function

$$\displaystyle \begin{aligned}f_{{\mathbf{p}}^{[0]}}=\sum_{\beta \in \mathbb{Z}^2}p^{[0]}_\beta\phi_{\mathbf{a}}(\cdot-\beta),\quad \mbox{for}\quad \phi_{\mathbf{a}}:=\mathcal{S}_{\mathbf{a}}^\infty(\boldsymbol{\delta}),\end{aligned} $$

(10)

with $\boldsymbol {\delta }=\{\delta _{0,\alpha },\ \alpha \in \mathbb {Z}^2\}$ a bivariate sequence. The notions of convergence, regularity, generation, reproduction and approximation order are essentially the same as in the univariate case.

2.2 Examples of Subdivision Schemes

A famous example of univariate subdivision scheme is the Chaikin scheme [6] based on the simple rules

$$\displaystyle \begin{aligned} p_{2i}^{[k+1]}=\frac{1}{4}p_{i-1}^{[k]} + \frac{3}{4}p_i^{[k]}\quad p_{2i+1}^{[k+1]}=\frac 34 p_i^{[k]} + \frac 14 p_{i+1}^{[k]},\quad i\in \mathbb{Z}, \end{aligned} $$

(11)

corresponding to the mask

$$\displaystyle \begin{aligned} \mathbf{a}=\{\frac{1}{4},\ \frac{3}{4},\ \frac{3}{4},\ \frac{1}{4}\}. \end{aligned} $$

(12)

Figures 4 and 5 show the application of the rules in (11) to the initial δ-sequence and the component-wise application of the same rules to 2D initial points. A ‘corner cutting’ effect is evident.

Fig. 4

Three steps of the subdivision in (11) with initial points (in magenta)

Fig. 5

Application of Chaikin scheme to 2D-initial points

The Chaikin scheme is a quadratic spline subdivision scheme. Indeed, any degree-n spline with integer knots and smoothness C ⁿ⁻¹ can be obtained as the limit of a subdivision scheme based on the rules

$$\displaystyle \begin{aligned} p_{2i}^{[k+1]}=\sum_{j\in \mathbb{Z}}\frac{1}{2^n}\binom{n+1}{2j}p_{i-j}^{[k]}, \qquad p_{2i+1}^{[k+1]}=\sum_{j\in \mathbb{Z}}\frac{1}{2^n}\binom{n+1}{2j+1} p_{i-j}^{[k]} , \quad i\in \mathbb{Z}. \end{aligned} $$

(13)

The rules in (13) correspond to the masks

$$\displaystyle \begin{aligned} {\mathbf{a}}^n=\{\frac{1}{2^n}\binom{n+1}{i},\ i=0,\dots, n\}, \end{aligned} $$

(14)

and reduce for n = 2 to (11) while (14) reduces to (12). For odd n the schemes are primal and for even n they are dual.

The regularity, polynomial reproduction and approximation order of spline subdivision schemes are known to be ${\mathcal {C}}^{n-1}$, Π ₀ and r = 1, respectively. Note that, placing the masks of the primal spline schemes symmetric relative to the origin, namely $a_{-i}=a_i, \ i=0,\cdots , \frac {n+1}{2}$ the schemes produce Π ₁, hence their approximation order is r = 2.

Important examples of subdivision schemes are interpolatory schemes where, for all k, p ^[k] is contained in p ^[k+1], so that the limit function is interpolating the input points. In contrast, the other types of schemes are called approximating.

A popular univariate example is the interpolatory 4-point scheme with rules

$$\displaystyle \begin{aligned} p^{[k+1]}_{2i} = p^{[k]}_i, \quad p^{[k]}_{2i+1} = -\frac{1}{16}p^{[k]}_{i-2}+\frac{9}{16}p^{[k]}_{i-1}+\frac{9}{16}p^{[k]}_{i}-\frac{1}{16}p^{[k]}_{i+1},\ i\in \mathbb{Z}, \end{aligned} $$

(15)

corresponding to the mask

$$\displaystyle \begin{aligned} \mathbf{a}=\{-\frac{1}{16},\ 0,\ \frac{9}{16},\ 1,\ \frac{9}{16},\ 0, -\frac{1}{16}\}. \end{aligned} $$

(16)

The four point scheme reproduces the polynomial space Π ₃, is C ¹ and has approximation order r = 4. It is a special instance of the family of 4-point schemes with tension parameter (see [37]) corresponding to $w=\frac {1}{16}$ and of the family of the interpolatory 2n + 2-point schemes proposed by Dubuc-Deslauriers in [32] corresponding to n = 1. The schemes in the latter family (DD-family) have the refinement rules

$$\displaystyle \begin{aligned} p^{[k+1]}_{2i} {=} p^{[k]}_i, \ \ p^{[k]}_{2i{+}1} {=}\sum_{j=-n-1}^n\frac{(-1)^{j}(n+1)}{2^{4n+1}(2j+1)}\binom{2n+1}{n}\binom{2n+1}{n+j{+}1}\, p^{[k]}_{i-j},\ i\in \mathbb{Z}, \end{aligned} $$

(17)

with mask

$$\displaystyle \begin{aligned} \begin{array}{ll} {\mathbf{a}}^n=&\{\frac{(-1)^n(n+1)}{2^{4n+1}(2n+1)}\binom{2n+1}{n},\ \cdots,\ 0,\ \frac{n+1}{2^{4n+1}}\binom{2n+1}{n}\binom{2n+1}{n},\ 1, \\ \\ &\frac{n+1}{2^{4n+1}}\binom{2n+1}{n}\binom{2n}{n},\ 0,\ \cdots, \ \frac{(-1)^n(n+1)}{2^{4n+1}(2n+1)}\binom{2n+1}{n} \}. \end{array} \end{aligned} $$

(18)

It is easy to conclude from (17), that the scheme is based on n + 1 points corresponding to the n + 1 consecutive integer parameters on each side of $i+\frac {1}{2}$.

The DD 2(n + 1)-point scheme reproduces the polynomial space Π _2n+1 and has approximation order r = 2n + 2.

Figures 6 and 7 show the application of the rules in (15) to the δ initial sequence and the component-wise application of the same rules to the same 2D-initial points as in Fig. 5. The ‘interpolation’ effect is evident.

Fig. 6

Three steps of the scheme with rules (15) with initial points δ (in magenta)

Fig. 7

One application of the 4-point scheme to 2D-initial points

In the bivariate setting, two well known approximating subdivision schemes are the Doo-Sabin scheme and the Loop scheme. In the regular situation, namely when the meshes are $2^{-k}\mathbb {Z}^2,\ k\ge 0$, the first one is a tensor product of the Chaikin scheme while the second one is associated with the three direction box-splines defined by the directions (1, 0), (0, 1), (1, 1) repeated twice. The masks of these two schemes are respectively given in terms of the matrices as

(19)

Figures 8 and 9 show the first and the second iteration of the rules based on the masks in (19) to the initial δ-sequence.

Fig. 8

Second and third iteration of Doo-Sabin scheme applied to the bivariate δ

Fig. 9

Second and third iteration of Loop scheme applied to the bivariate δ

A bivariate interpolatory subdivision scheme related to the four point scheme is the butterfly scheme. The mask of the butterfly scheme is

(20)

Figure 10 shows the first and the second iteration of the Butterfly scheme applied to the bivariate δ. More complicated examples of interpolatory subdivision schemes can be found in [25], for example.

Fig. 10

Second and third iteration of the Butterfly scheme applied to the initial sequence δ

2.3 Main Applications

Subdivision schemes have a vast variety of applications. The most known is certainly in geometric modelling and computer aided geometric design (CAGD) where they are used for the design of smooth curves and smooth surfaces of arbitrary topology. As already mentioned, other applications include construction of refinable functions, multiresolution and wavelets, image analysis through the generation of active contours and active surfaces, computer animation, isogeometric analysis and multigrid.

In the next two subsections we will briefly sketch the first two domains of application while application to image analysis is the subject of Sect. 3.3.

2.3.1 Geometric Modelling and CAGD

In the examples of Sect. 2.2 univariate subdivision schemes generate curves from an initial set of 2D points. Passing from curves to surfaces the setup becomes much more complicated since the topological relations between the data are richer than in the curve case (i.e., in the univariate case). In the surface case, a subdivision scheme deals with refinement of meshes consisting of vertices, faces and edges. The vertices are points in 3D, the edges are pairs of vertices, and the faces are cyclic sets of edges (see Fig. 11).

Fig. 11

A schematical representation of a mesh

Therefore, each subdivision scheme for surface generation in based on two refinement rules. A topological refinement rule describing the modification of the connectivity of the mesh with the added vertices and geometric refinement rules that describe where the new vertices, are located in 3D. In a mesh faces and vertices are classified by the so-called vertex and face valence: The valence of a face counts the number of edges that delimit it whereas the valence of a vertex is the number of edges incident to it. Quadrilateral meshes consist of faces with valence 4 and regular vertices are of valence 4. In a triangular mesh all faces are triangles, and the regular vertices have valence 6. In a mesh with most faces and vertices of valence 4, the rest of the faces and vertices are the irregular ones. Similarly, in a mesh with most faces triangles and vertices of valence 6, the rest of the faces and vertices are the irregular ones. A mesh/region is called a regular mesh/region where all vertices and faces are regular. Non-regular vertices/faces are extraordinary and a mesh containing them is said to be irregular. It is important to note that irregular meshes are necessary for the generation of surfaces of arbitrary topology.

The presence of an irregular element requires the definition of specific rules depending on the valence of the irregular element. The Doo-Sabin scheme and the Loop scheme provide rules for irregular vertices as well as the Catmull-Clark scheme (a tensor product cubic spline scheme in irregular regions). For details about subdivision schemes for surfaces we refer to the books [64, 68].

2.3.2 Generation of Refinable Functions and Wavelets

The link between subdivision schemes and wavelets is in the refinability property of basic limit functions. Indeed, any $\phi _{\mathbf {a}}={\mathcal {S}}^\infty _{\mathbf {a}}(\boldsymbol {\delta })$ is refinable namely it satisfies the refinement equation

$$\displaystyle \begin{aligned} \phi_{\mathbf{a}}=\sum_{\alpha\in \mathbb{Z}^s}a_\alpha\phi_{\mathbf{a}}(2\cdot-\alpha),\quad s\in \{1,2\},\end{aligned} $$

(21)

with $\{a_\alpha \}_{\alpha \in \mathbb {Z}^s}$ the elements of the mask a. Equation (21) follows from $(S_a\boldsymbol {\delta })_\alpha =a_\alpha ,\ \alpha \in \mathbb {Z}^s$ and from (4) and (10) for s = 1, 2, respectively.

Equation (21) is the crucial ingredient to generate multiresolution analysis and wavelets even if, in most cases, the explicit expression of ϕ _a is unknown. Nevertheless, several numerical procedures are possible for its computation. For example, in the univariate case (s = 1) using the refinement equation (21) k-times we easily see that

$$\displaystyle \begin{aligned}\phi_{\mathbf{a}}=\sum_{i\in \mathbb{Z}}a^{[k]}_i\phi_{\mathbf{a}}(2^k\cdot-i),\quad \mbox{where}\quad {\mathbf{a}}^{[0]}:=\mathbf{a}\ \ \mbox{and}\ \ {\mathbf{a}}^{[\ell]}:=\mathcal{S}_{\mathbf{a}}{\mathbf{a}}^{[\ell-1]},\ \ell=1,\cdots,k.\end{aligned} $$

Therefore, the computation of ϕ _a at the dyadic points $j2^{-k},\ j\in \mathbb {Z}$ is simply the convolution of the sequence a ^[k] with values of ϕ _a. Note that ϕ _a(i) ≠ 0 only for i = 1, …N − 1 since the support of ϕ _a is contained in [0, N] assuming that a = {a ₀, …, a _N})and ϕ _a is continuous. Therefore, for v = [ϕ _a(1), …, ϕ _a(N − 1)], we have

$$\displaystyle \begin{aligned}A v=v,\quad \mbox{with}\quad A_{i,j}=a_{2i-j},\ i,j=1,\ldots,N-1.\end{aligned}$$

An alternative method for the computation of ϕ _a is the so called cascade algorithm, involving the repeated application of the operator $\mathcal {T}_{\mathbf {a}}$,

$$\displaystyle \begin{aligned}\mathcal{T}_{\mathbf{a}} g=\sum_{\alpha\in \mathbb{Z}^s}a_\alpha g(2\cdot-\alpha),\quad s\in \{1,2\}. \end{aligned}$$

Choosing as initial ‘guess’ any continuous compactly supported function ψ ₀ satisfying $\sum _{\alpha \in \mathbb {Z}^s}\psi _0(x-1)\equiv 1$, the cascade algorithm generates the sequence {ψ _k}_k≥0 by repeated application of $\mathcal {T}_{\mathbf {a}}$, namely $\psi _{k+1}=\mathcal {T}_{\mathbf {a}} \psi _{k},\ k\ge 0$, and it converges to ϕ _a.

We remark that the operator $\mathcal {T}_{\mathbf {a}}$ is adjoint of $\mathcal {S}_{\mathbf {a}}$ in the following sense:

$$\displaystyle \begin{aligned}\sum_{\alpha\in \mathbb{Z}^s}(\mathcal{S}_{\mathbf{a}}(\mathbf{p}))_\alpha f(2\cdot-\alpha)=\sum_{\alpha\in \mathbb{Z}^s}p_\alpha(\mathcal{ T}_{\mathbf{a}}(f)(\cdot-\alpha), \end{aligned}$$

for any continuous and compactly supported function f and for any finitely supported sequence p.

We can also calculate the Fourier transform $\hat \phi _{\mathbf {a}}$. Indeed, taking the Fourier transform of the refinement equation (21) we find

$$\displaystyle \begin{aligned} \hat \phi_{\mathbf{a}}(\xi)=\mathcal{H}_{\mathbf{a}}(\frac{\xi}{2})\hat \phi_{\mathbf{a}}(\frac{\xi}{2}), \end{aligned} $$

(22)

where $\mathcal {H}_{\mathbf {a}}(\xi )=\frac {1}{2^s} \displaystyle {\sum _{\alpha \in \mathbb {Z}^s}a_\ell e^{2\pi i\, \ell \xi }}$ is a trigonometric polynomial, due to the finite support of the mask a. By repeated application of (22), we arrive at

$$\displaystyle \begin{aligned} \hat \phi_{\mathbf{a}}(\xi)=\prod_{k=1}^\infty\mathcal{H}_{\mathbf{a}}(\frac{\xi}{2^k}). \end{aligned} $$

(23)

Orthonormal wavelets are derived from refinable functions whose integer shifts are orthonormal. Such refinable functions are defined by subdivision schemes with masks having special properties. These masks are closely related to masks of interpolating schemes. In particular the mask of the DD family are related to Daubechies orthonormal wavelets of compact support [27].

2.4 Analysis Tools

In this section we shortly review analysis tools for linear stationary subdivision schemes. As it can be observed in this section, in spite of the simplicity of the subdivision idea, analyzing convergence and regularity can be difficult. Indeed, even if the linearity of the operators allow for the use of linear algebra, e.g. joint spectral radius or eigen-analysis, these problems can be NP hard. On the contrary, the analysis of polynomial reproduction, approximation order and smoothing factors are based on elementary algebraic tools and are much simpler.

Certainly, an advantage of the uniform framework (i.e. dealing with uniformly distributed data) characterising ‘classical’ subdivision schemes, is that we can make use of standard mathematical tools of signal processing (e.g. discrete-time Fourier transform and z-transform) which simplify all formulations and derivations considerably. Indeed, a special role is played by the subdivision symbol, the Laurent polynomial with coefficients the elements of the mask a, i.e.

$$\displaystyle \begin{aligned} \mathcal{A}(\mathbf{z})=\sum_{\alpha\in \mathbb{Z}^s}a_\alpha {\mathbf{z}}^\alpha,\quad \mathbf{z}\in \mathbb{C}^s\setminus\{0\},\quad s=\{1,2\}. \end{aligned} $$

(24)

With the symbols the kth subdivision step reads as

$$\displaystyle \begin{aligned}\mathcal{P}^{[k+1]}(\mathbf{z})=\mathcal{A}(\mathbf{z})\mathcal{P}^{[k]}({\mathbf{z}}^2),\quad \mbox{where}\quad \mathcal{ P}^{[k]}(\mathbf{z})=\sum_{\alpha\in \mathbb{Z}^s}p^{[k]}_{\alpha}{\mathbf{z}}^\alpha,\quad k\ge 0. \end{aligned}$$

Polynomial generation and reproduction translate into algebraic conditions on the subdivision symbol and its derivatives at the points of

$$\displaystyle \begin{aligned} \varXi_s^{\prime}=\{e^{-i\pi\, {\boldsymbol\epsilon}},\ {\boldsymbol\epsilon}\in \varXi_s\}\equiv \{-1,1 \}^s,\quad s\in \{1,2\}. \end{aligned} $$

(25)

With the help of the auxiliary polynomials

$$\displaystyle \begin{aligned} q_{\mathbf{0}}(\mathbf{z}):=1,\quad q_{\mathbf{j}}(\mathbf{z}):=\prod_{i=1}^s \prod_{\ell_i=0}^{j_i-1}(z_i-\ell_i), \quad \mathbf{j}\in \mathbb{N}^s_0,\quad s\in \{1,2\}, \end{aligned} $$

(26)

the polynomial generation/reproduction results are stated in the following proposition (see [8] for details). To state the proposition, we introduce the notion of a non-singular subdivision scheme, which is a scheme that generates zero limits if and only if the initial data is a zero sequence.

Proposition 1 ([8, Theorem 2.6])

Let S _a be a convergent and non-singular subdivision scheme with mask a and symbol $\mathcal {A}(\mathbf {z})$ . It generates polynomials of degree up to n, $n\in \mathbb {N}_0$ , if and only if

$$\displaystyle \begin{aligned} \mathcal{A}({\mathbf{1}}_s)=2^s,\quad \bigl(D^{\mathbf{j}} \mathcal{A}\bigr)({\boldsymbol\epsilon})=0 \quad \mathit{\mbox{for}} \quad {\boldsymbol\epsilon}\in \varXi_s^{\prime}\setminus {\mathbf{1}}_s,\quad |\mathbf{j}| \le n\,, \end{aligned} $$

(27)

where D ^j is the j -th directional derivative ( $\mathbf {j}\in \mathbb {Z}^s$ ) and ${\mathbf {1}}_s=(1,\cdots ,1)\in \mathbb {Z}^s$.

Moreover, for a given parameter shift $\boldsymbol {\tau } \in \mathbb {R}^s$ , it reproduces polynomials of degree up to k if and only if

$$\displaystyle \begin{aligned}\bigl(D^{\mathbf{j}} \mathcal{A}\bigr)({\mathbf{1}}_s)= 2^s q_{\mathbf{j}}(\boldsymbol{\tau}) \quad \mathit{\mbox{and}} \quad \bigl(D^{\mathbf{j}} \mathcal{ A}\bigr)({\boldsymbol\epsilon})=0 \quad \mathit{\mbox{for}} \quad {\boldsymbol\epsilon}\in \varXi^{\prime}_s\setminus{\mathbf{1}}_s,\quad |\mathbf{j}| \le n\,.\end{aligned}$$

Also, Π _n -reproduction implies approximation order n + 1.

We remark that the algebraic conditions (27) are also called sum rules of order n or zero-conditions (see e.g. [47]) and [18], respectively).

Still of algebraic type is the investigation of existence of ‘difference schemes’ and ‘smoothing factors’ useful for the smoothness analysis of the basic limit functions. In the univariate setting (s = 1), a symbol contains k smoothing factors if there exists a Laurent polynomial $\mathcal {B}(z)$ such that

$$\displaystyle \begin{aligned}\mathcal{A}(z)=\left(\frac{1+z}{2}\right)^k\mathcal{B}(z). \end{aligned}$$

The regularity of the scheme S _a is at least k, if the scheme associate with the symbol $\mathcal {B}(z)$ is convergent. A scheme S _a is convergent if and only if its symbol has the form $\mathcal {A}(z)=(1+z)\mathcal {B}(z)$ and the scheme S _b with symbol $\mathcal {B}(z)$ is contractive. A sufficient condition for that is (see e.g. [39])

$$\displaystyle \begin{aligned}\max\{\sum_{i\ \in \mathbb{Z}}|b_{2i}|,\ \sum_{i\ \in \mathbb{Z}}|b_{2i+1}|\}<1. \end{aligned}$$

In the bivariate situation, the construction of a difference scheme and the link between smoothing factors and smoothness of the limit is definitely more involved (see, [12], for example). To simplify, we can say that the existence of tensor-product type smoothing factors such as (1 + z ₁)(1 + z ₂), (1 + z ₁)(1 + z ₁ z ₂) or (1 + z ₂)(1 + z ₁ z ₂) plus contractivity of the difference scheme implies C ¹-regularity. For details we refer again to [39].

An apparently different approach to convergence and regularity analysis of subdivision schemes is given by the so called ‘JSR approach’. Essentially, we associate to the binary scheme 2^s matrices constructed from the subdivision mask and the reproduced space of polynomials. Then, we compute their joint spectral radius (JSR) whose magnitude indicates the Hölder regularity of the scheme as explained. The JSR of a collection of matrices extends the classical notion of spectral radius of a matrix in the following sense.

Definition 1

Given a finite collection of square matrices ${\mathcal {M}}$, the JSR is

$$\displaystyle \begin{aligned}\displaystyle{ \rho({\mathcal{M}}):=\lim_{m \rightarrow \infty} \max_{M_{1}, \ldots, M_m \in \mathcal{M}} \left\|\prod_{j=1}^m M_{j} \right\|{}^{1/m}.}\end{aligned}$$

First introduced by Rota and Strang in 1960 [61], the JSR was almost forgotten, and then rediscovered in 1992 by Daubechies and Lagarias [28] in the context of the analysis of refinable functions. In general, unfortunately, even the numerical approximation of the JSR is a very challenging task making the JSR approach not always applicable. But, recently, an algorithm for the computation of the JSR has been proposed in [45] (see also [52], for a different approach) and a Matlab code is now available in [51]. We also observe that even if the difference schemes approach and the JSR approach appear to be intrinsically different, they characterize the subdivision regularity in terms of the same quantity. As demonstrated in [7] the two approaches differ only by the numerical schemes they provide for the estimation of the same quantity.

A completely different approach for estimating the regularity of S _a is by its Fourier transform. Indeed, the equality (23) can be used to determine the regularity of the basic limit function ϕ _a (i.e. of the subdivision scheme S _a), by estimating the decay of its Fourier transform. The latter approach is the one used by many authors (see [27, 34], for example).

Remark 1

The analysis tools presented in this section apply to regular regions or away from irregular elements. In case of meshes containing irregular vertices/faces a different approach to the analysis of subdivision scheme is needed. The appropriate tool to analyze the regularity of the generated limits in the vicinity of an irregular element involves the so called characteristic map and the spectral analysis of the local subdivision matrix. For all details we refer the interested reader to [58, 63, 66] and references therein.

3 Motivation for Non-stationary Subdivision Schemes

From the previous section we easily understand that the subdivision idea can also be implemented in a level dependent way, that is to say by using different masks at different iterations. Indeed, at level k, the operator S _a in (2) can be replaced by $S_{{\mathbf {a}}^{[k]}}$ leading to the non-stationary variant of subdivision

$$\displaystyle \begin{aligned} \left\{ \begin{array}{ll} \mbox{Input}\quad \{ {\mathbf{a}}^{[k]}\}_{k\ge 0}, \ \ {\mathbf{p}}^{[0]}&\\ \mbox{For}\quad k=0,1,\cdots &\\ \qquad \quad {{\mathbf{p}}^{[k+1]} }:= S_{{\mathbf{a}}^{[k]}}{\mathbf{p}}^{[k]} \end{array} \right. \end{aligned} $$

(28)

Compared with the stationary ones, non-stationary subdivision schemes are not more complicated. Changing coefficients level by level is not a crucial implementation matter, considering that in practice, only few iterations are executed. Also, the definition of convergence and regularity as in (3) is not affected by the level dependence of the rules. Nevertheless, non-stationary subdivision schemes have different properties and enrich the class of subdivision limit functions. For example, applied to 2D-points they can generate circles, ellipses, or other conics. Also, they allow the user to modify the shape of a subdivision limit by the help of level-dependent tension parameters. In the univariate case, they can generate exponential B-splines [38], $\mathcal {C}^\infty$ functions with compact support as the Rvachev-type function [39], or B-spline like functions with higher smoothness relative to the support size, [10, 15].

The algebraic formalism associated with non-stationary schemes is as in the stationary situation. The only difference is that now we deal with a sequence of symbols

$$\displaystyle \begin{aligned} \mathcal{A}^{[k]}(\mathbf{z})=\sum_{\alpha\in \mathbb{Z}^s}a^{[k]}_\alpha {\mathbf{z}}^\alpha,\quad k\ge 0,\quad \mathbf{z}\in \mathbb{C}^s\setminus\{0\},\quad s=\{1,2\}. \end{aligned} $$

(29)

Thus, the k-th subdivision step can be written as

$$\displaystyle \begin{aligned}\mathcal{P}^{[k+1]}(\mathbf{z})=\mathcal{A}^{[k]}(\mathbf{z})\mathcal{P}^{[k]}({\mathbf{z}}^2),\quad \mbox{with}\quad \mathcal{ P}^{[k]}(\mathbf{z})=\sum_{\alpha\in \mathbb{Z}^s}p^{[k]}_{\alpha}{\mathbf{z}}^\alpha,\quad k\ge 0. \end{aligned}$$

The discussion on the use of the corresponding algebraic tools as well as of other associated tools like the JSR is postponed to Sect. 4. Here, we mention that in case the non-stationarity is characterized by the cyclic repetition of ℓ different masks the scheme is actually stationary with 2^ℓ-arity rather than 2. Indeed, for any k = r ⋅ ℓ, r > 0 we can consider ℓ steps simultaneously, and obtain

$$\displaystyle \begin{aligned}\mathcal{P}^{[k+\ell]}(\mathbf{z})=\tilde{\mathcal{A}}(\mathbf{z})\mathcal{P}^{[k]}({\mathbf{z}}^{2^\ell}), \ \mbox{where}\ \tilde{\mathcal{A}}(\mathbf{z}):=\mathcal{A}^{[\ell-1]}(\mathbf{z})\mathcal{A}^{[\ell-2]}({\mathbf{z}}^2)\cdots\mathcal{A}^{[0]}({\mathbf{z}}^{2^{\ell-1}}), \end{aligned}$$

implying that $\tilde {\mathcal {A}}(\mathbf {z})$ is the symbol of an arity-2^ℓ scheme that multiply by 2^ℓ the number of points at each step (see e.g.,[20]).

In the non-stationary case, when using the sequence of masks starting not with a ^[0] but with any a ^[m], m > 0, we get different results according to the starting mask a ^[m], where m varies from 0 to ∞. The subdivision scheme in this case is

$$\displaystyle \begin{aligned} \left\{ \begin{array}{ll} \mbox{Input}\quad \{ {\mathbf{a}}^{[k]}\}_{k\ge 0}, \ \ {\mathbf{p}}^{[0]}&\\ \mbox{For}\quad k=0,1, 2, \cdots &\\ \qquad \quad {{\mathbf{p}}^{[k+1]} }:= S_{{\mathbf{a}}^{[m+k]}}{\mathbf{p}}^{[k]} \end{array} \right. \end{aligned} $$

(30)

From the above we understand that in the level dependent case we have no longer a unique basic limit function but rather a sequence of basic limit functions {ϕ _m, m ≥ 0} each defined as

$$\displaystyle \begin{aligned} \phi_m=\lim_{k\rightarrow \infty}S_{{\mathbf{a}}^{[k+m]}}\cdots S_{{\mathbf{a}}^{[m]}}\boldsymbol{\delta}, \end{aligned} $$

(31)

where δ is the sequence with value 1 at the origin, and zero on $\mathbb {Z}^s\setminus \{0\}$. Due to linearity and uniformity of the operators, the sequence of basic limit functions satisfies a system of ‘generalized’ refinement equations,

$$\displaystyle \begin{aligned} \phi_m=\sum_{\alpha\in \mathbb{Z}^s}a^{[m]}_\alpha\phi_{m+1}(2\cdot-\alpha),\quad m\ge 0. \end{aligned} $$

(32)

The system of generalized refinement equations (32) is the base to the generation of non-stationary multiresolution and non-stationary wavelets [3, 42].

The next subsections show the capabilities of level-dependent schemes in applications, e.g., in geometric design and in approximation [49, 50], in biological imaging [29, 65] and in the generation of non-stationary wavelets [13, 42, 67].

3.1 Reproduction of Conics and Quadrics and Use of Level Dependent Tension Parameters in CAGD

It is well known that B-spline curves and surfaces are central tools in computer-aided geometric design but also in computer graphics, due to the properties of B-splines, which guarantee, for example, that the B-spline curves/surfaces are in the convex hull of their control polygons/meshes. B-splines, unfortunately, are not capable to reproduce in an exact way conic sections which are needed very often. This is why different B-spline generalizations, like NURBS, have been proposed. The rational nature of NURBS is the reason why it is difficult to integrate or differentiate them. With NURBS it is possible to exactly represent conic sections but not all transcendental curves. Therefore, researchers have started to consider ‘generalized B-splines’ that is bell-shaped functions piecewise defined with segments in other spaces than rational polynomials. By selecting spaces of trigonometric or hyperbolic functions, for example, with generalized B-splines it is possible to represent polynomial curves, conic sections or transcendental curves. What is relevant to this paper is that several instances of generalized B-splines with integer knots can be see as limit functions of non-stationary subdivision schemes.

The computation of limit surfaces by a subdivision scheme is much simpler than the modelling of surfaces with NURBS (B-splines) since, in the latter case, the complete surface consists of NURB (B-splines) patches with geometric continuity between the patches. For details on connecting smoothly patches see [55, Chapter 13].

Note that meshes for modelling surfaces of arbitrary topology have irregular regions, and the refinement rules have to be adapted to the vicinity of irregular elements.

As an example we can consider the following non-stationary subdivision scheme generating exponential splines with segments in

$$\displaystyle \begin{aligned}\mathop{\mathrm{span}}\nolimits\{e^{\theta\, t}, e^{-\theta\, t}, te^{\theta\, t}, te^{-\theta\, t} \},\quad \theta\in \mathbb{R}\cup \mathrm{ i}\mathbb{R},\end{aligned}$$

with θ a parameter to be chosen by the user (see [14] and [21]). These exponential splines are a special instance of L-splines (see [62]). The refinement rules are

$$\displaystyle \begin{aligned} \begin{array}{lll} p_{2i}^{[k+1]}&=&\displaystyle{ \frac{1}{2(v^{[k]}+1)^2} } p_{i-1}^{[k]} + {\frac{4(v^{[k]})^2+2}{2(v^{[k]}+1)^2}}p_i^{[k]} + { \frac{1}{2(v^{[k]}+1)^2} } p_{i+1}^{[k]}, \\ \\ p_{2i+1}^{[k+1]}&=&\displaystyle{\frac{2v^{[k]}}{(v^{[k]}+1)^2}} p_i^{[k]} + {\frac{2v^{[k]}}{(v^{[k]}+1)^2}} p_{i+1}^{[k]}, \end{array} \end{aligned} $$

(33)

where the non-stationary parameter v ^[k] is defined as

$$\displaystyle \begin{aligned}v^{[k]}=\frac{1}{2} \left(e^{\mathrm{i}\frac{\theta}{2^{k+1}}}+e^{-\mathrm{i}\frac{\theta}{2^{k+1}}} \right)=\sqrt{\frac{1+v^{[k-1]}}{2}},\quad k\ge 0,\quad v^{[-1]}=\cos{}(\theta)>-1.\end{aligned}$$

The effect of the parameter θ on the exponential B-spline shape obtained when starting the subdivision process from the δ sequence is illustrated in Fig. 12.

Fig. 12

Basic limit functions for the scheme in (33) with θ ∈ {i, 3i, 5i, 7i} (left) and θ ∈ {3, 2.5, 2, 0} (right) (from lower to taller functions). Initial control polygon represented by a dashed line

We remark that the above scheme is only generating exponential-polynomial spaces but is not reproducing them. Yet, in [19, 22, 40] and [54], exponential-polynomials reproducing schemes are provided. In the first two references, these schemes are shown to generate conics, cardiod, lemniscate, astroid or nephroid as shown in Fig. 13.

Fig. 13

Subdivision limit curves (full lines) and the initial control polygons (dashed line) connecting points from a circle, a nephroid a lemniscate and a quadrifolium

Similarly, bivariate non-stationary schemes reproducing quadrics are defined and investigated for example in [44, 48, 49, 53]. Since the corresponding refinement rules, in particular in case of extraordinary points, are non-trivial, we here simply present some of the pictures from [53] in Fig. 14.

Fig. 14

First line: initial meshes. Second line: results obtained by applying 5 steps of the non-stationary scheme in [53]

To conclude this section, we shortly discuss how non-stationary tension parameters and level dependent rules can influence the shape of the subdivision limits. Let us consider the interpolatory non-stationary scheme with the first two odd rules

$$\displaystyle \begin{aligned} p^{[k+1]}_{2i+1} = \frac{1}{2} p^{[k]}_{i-1}+\frac{1}{2} p^{[k]}_{i}, \quad k=0,1,\ i\in \mathbb{Z}, \end{aligned} $$

(34)

and then, for k > 1, for ω ^[k] chosen at random from the interval $[ \frac {3}{64} , \frac {1}{16}]$, the odd rules are given by

$$\displaystyle \begin{aligned} p^{[k]}_{2i+1} = -\omega^{[k]}p^{[k]}_{i-2}+(\frac{1}{2} +\omega^{[k]})p^{[k]}_{i-1}+(\frac{1}{2} +\omega^{[k]})p^{[k]}_{i}-\omega^{[k]}p^{[k]}_{i+1},\quad k\ge 2,\ i\in \mathbb{Z}. \end{aligned} $$

(35)

As shown in [10] by a JSR approach, the scheme based on (34) and (35) is $\mathcal {C}^1$-convergent with Hölder exponent $\alpha \ge -\log _2 \frac 38 \approx 1.4150$ and its basic limit function is supported in $[ -\frac {3}{2} , \frac {3}{2}]$ while in the classical four point case the scheme is known to be $\mathcal {C}^1$-convergent with Hölder exponent 2 − 𝜖 for any 𝜖 > 0 and the support is [−3, 3] (see [32]). Figure 15 compares the two basic limit functions.

Fig. 15

Basic limit function of the 4-point scheme (red, dashed line), and of the scheme (34)–(35) (blue, solid line)

The last example shows that with a non-stationary interpolatory scheme it is possible to obtain a C ¹ basic limit function of smaller support than in the stationary interpolatory case.

3.2 Non-stationary Wavelets and Non-stationary Interpolatory Subdivision Schemes

The construction of stationary orthonormal wavelets of compact support is closely related to the DD-family of subdivision schemes. Such a Daubechies wavelet is generated by the integer shifts of a refinable function, which is the basic limit function of a subdivision scheme. The mask of this scheme is derived from the mask of a corresponding DD-scheme, by taking an ‘almost square root’ of the symbol of the DD-scheme. This is possible since the symbols of the DD-schemes are non-negative on the unit circle (when z is replaced by exp(iθ), 0 ≤ θ < 2π) [27]. This construction has two analogues in the non-stationary setting.

The first analogoue is derived from interpolatory schemes that reproduce spaces of exponential polynomials of finite dimension. In [40] non-stationary interpolatory schemes reproducing spaces of 2n exponentials are shown to converge and their smoothness is shown to be at least as that of the stationary DD-scheme reproducing all polynomials of degree less than 2n. In [67] non-stationary wavelets are constructed from non-stationary interpolatory subdivision schemes by a similar procedure as in the stationary case, without a proof that this is indeed possible. These wavelets were already used in the analysis of signals that are better approximated by exponentials rather than by polynomials, such as signals that have their energy concentrated around specific frequencies. For example in neurophysiology, such wavelets are well-suited for the analysis of exponential pulses, corresponding to different neurons. Proofs that the above construction is possible are given in [42]. Also given, are proofs showing that the smoothness of the non-stationary wavelets related to spaces of real exponential polynomials is at least that of the corresponding stationary wavelets.

The second analogue is derived from non-stationary interpolatory subdivision schemes with masks of growing support. A simple example is the sequence of masks of the DD-schemes (17), with n the subdivision level (see Sect. 4.3). Following the construction in the stationary case, the basic limit function of the non-stationary scheme with masks ‘almost square root’ of the masks of the DD-schemes, is the ‘father’ wavelet. These wavelets, which are C ^∞ compactly supported, are suitable for representing very smooth functions [13].

3.3 Image Segmentation: Active Contours and Active Surfaces

This section describes the use of non-stationary subdivision schemes in biological imaging and relies on the work done by the group of M. Unser at EPFL, Switzerland. Active contours or snakes, are tools for the segmentation of biomedical images. They consist of an initial curve that progresses towards the boundary of the object of interest guided by the minimization of an appropriate energy term. Relevant to our discussion is that subdivision schemes can also be used to describe a contour by the iterative application of refinement rules staring from an initial finite set of control points. The discrete nature of the initial representation is convenient in practice. It implicitly yields a continuously defined model whose properties depend on the used subdivision scheme: its approximation order, its capability of reproducing circular, elliptical, or polynomial shapes, its interpolating or approximating nature. In particular, the capability of modelling ‘roundish’ objects is facilitated by non-stationary schemes.

Therefore, as an alternative to the traditional approaches, in [2] subdivision schemes are used to model a curve driven by a small set of ‘master’ points, called control points, and a set of ‘slave’ points (generated by a specific subdivision scheme) that describe the curve. The advantages of the use of subdivision schemes are their simplicity of implementation and their multiresolution nature, so that the contour of a shape can be represented at varying resolutions and result into a snake be optimized in a coarse-to-fine fashion.

Based on similar ideas is the use of subdivision for the generation of active surfaces, also called 3D deformable models used for the extraction of volumetric structures. They consist of deformable surfaces that, starting from an initial user-provided configuration, evolve toward the boundary of the 3D object. The deformation can be manual or automatic. Certainly, a reasonable deformable model must depend on a small number of control points (to reduce the complexity of the deformation and to improves robustness), and must reproduce or approximate ellipsoids. In [1] the authors propose a 3D deformable model obtained by applying a tailored non-stationary subdivision scheme to a suitable coarse mesh with few control points. The approach presents several advantages: First, surfaces of arbitrary topological type can be handled; second, by simple modifications of the control points, easy and localized interactions can be achieved; third, the implementation is easy and cheap in virtue of the discrete nature of the scheme.

4 Analysis Tools for Non-stationary Subdivision Schemes

In this section we consider analysis tools of non-stationary schemes and highlight similarities and differences with the stationary case.

4.1 Masks of Fixed Support

First we consider analysis tools of non-stationary schemes for the case that all the masks {a ^[k]}_k≥0 have bounded support {0, ..., N} for some positive integer N, which is the more common and studied situation. In this case the methods of analysis are related to the analysis of stationary cases via the notion of asymptotic similarity and asymptotic equivalence. We start by introducing the notion of asymptotic equivalence (see [38]).

Definition 2

Let $\ell \in \mathbb {N}$. The non-stationary schemes $\{S_{{\mathbf {a}}^{[k]}}\}_{k \ge 0}$ and $\{S_{{\mathbf {b}}^{[k]}}\}_{k \ge 0}$ are said asymptotically equivalent of order ℓ if they satisfy

$$\displaystyle \begin{aligned} \sum_{k=0}^\infty 2^{k \ell} \|S_{{\mathbf{a}}^{[k]}}-S_{{\mathbf{b}}^{[k]}}\|{}_\infty <\infty, \end{aligned} $$

(36)

where $\|S_{{\mathbf {a}}^{[k]}}\|{ }_\infty :=\max _{\varepsilon \in \varXi _s}\left \{\sum _{\alpha \in \mathbb {Z}^s}|a^{[k]}(2\alpha +\varepsilon )|\right \}$ and Ξ _s := {0, 1}^s.

Under an additional technical assumption on the schemes $\{S_{{\mathbf {a}}^{[k]}}\}_{k \ge 0}$ and $\{S_{{\mathbf {b}}^{[k]}}\}_{k \ge 0}$, the regularity of $\{S_{{\mathbf {a}}^{[k]}}\}_{k \ge 0}$ can be deduced from the known regularity of the asymptotically equivalent scheme $\{S_{{\mathbf {b}}^{[k]}}\}_{k \ge 0}$ with the method in [38]. Yet, in [38] only the convergence of non-stationary schemes is derived by asymptotic equivalence of order ℓ = 0 to a stationary scheme. The asymptotic equivalence of order ℓ ≥ 1 is too strong for analyzing smoothness. For that the notion of smoothing factors is introduced there.

Definition 3

Let the Laurent polynomials $\{\mathcal {A}^{[k]}(\mathbf {z})\}_{k \ge 0}$ be of the form

$$\displaystyle \begin{aligned} \mathcal{A}^{[k]}(\mathbf{z})=\frac{1}{2} (1+r_k {\mathbf{z}}^\lambda)\mathcal{B}^{[k]}(\mathbf{z}),\quad k\ge K\ge 0,\quad \lambda\in \mathbb{N}_0^s. \end{aligned} $$

(37)

The factors $\{\frac {1}{2} (1+r_k {\mathbf {z}}^\lambda )\}_{k\ge K}$ are termed ‘smoothing factors’ if

$$\displaystyle \begin{aligned}r_k=2^{\eta 2^{-k}}(1+\epsilon_k)\quad \mbox{with}\quad \eta\in \mathbb{R}\ \mbox{and }\ \sum_{k=K}^\infty|\epsilon_k|2^k<\infty.\end{aligned}$$

Theorem 1 ([38, Theorem 10])

In the notation of Definition 3 , if $\{\mathcal {B}^{[k]}(\mathbf {z})\}_{k \ge 0}$ corresponds to a $C^m(\mathbb {R}^s)$ non-stationary subdivision scheme then the basic limit functions of the non-stationary scheme with symbols $\{\mathcal { A}^{[k]}(\mathbf {z})\}_{k \ge 0}$ and their directional derivative in direction λ are also C ^m smooth in $\mathbb {R}^s$.

A direct consequence of Theorem 1 (see the remark below the statement of [38, Theorem 10]) is:

Corollary 1

Let $\{\mathcal {A}^{[k]}(\mathbf {z})=\prod _{i=1}^s\frac {1}{2} (1+r_{k,i} {\mathbf {z}}^\lambda _i)\mathcal { B}(\mathbf {z})\}_{k\ge 0}$ with s smoothing factors. If the stationary scheme corresponding to $\mathcal {B}(\mathbf {z})$ is $C^m(\mathbb {R}^s)$ and if λ ₁, ⋯ , λ _s are linearly independent vectors, then the basic limit functions of the non-stationary scheme corresponding to $\{\mathcal {A}^{[k]}(\mathbf {z})\}_{k\ge 0}$ is C ^m+1 smooth in $\mathbb {R}^s$.

In [41], the condition of asymptotical equivalence is weaken, in the univariate case, by requiring that the j-th derivatives of the symbols of the non-stationary scheme $\{S_{{\mathbf {a}}^{[k]}}\}_{k\ge 0}$ satisfy

$$\displaystyle \begin{aligned} |D^j \mathcal{A}^{[k]}(-1)| \le C 2^{-(\ell+1-j)k}, \quad j=0,\ldots,\ell, \quad \ell \ge 0,\quad C \ge 0. \end{aligned} $$

(38)

Moreover, they assume that the non-stationary scheme is asymptotically equivalent (of order 0) to some stationary scheme. The conditions in (38) are a generalization of the so-called sum rules in (27). In the stationary case, sum rules are known to be necessary for smoothness of subdivision (see e.g [5]), and also sufficient if the basic limit function of the scheme is L _∞-stable (see e.g. [39]).

In the spirit of (38) approximate sum rules are defined in [9]. They are a generalization of the notion of sum rules.

Definition 4

Let ℓ ≥ 0. The sequence of symbols $\{\mathcal {A}^{[k]}(\mathbf {z})\}_{k \ge 0}$ satisfies approximate sum rules of order ℓ + 1, if

$$\displaystyle \begin{aligned} \mu_k:=|\mathcal{A}^{[k]}({\mathbf{1}}_s)-2^s| \quad \mbox{and}\quad \delta_k\ :=\ \max_{|\eta| \le \ell} \max_{\epsilon \in \varXi' \setminus \{{\mathbf{1}}_s\}} |{2^{-k|\eta|} D^\eta \mathcal{A}^{[k]}(\epsilon)|} \end{aligned} $$

(39)

satisfy

$$\displaystyle \begin{aligned} \sum_{k=0}^{\infty} \mu_k < \infty \quad \mbox{and}\quad \sum_{k=0}^{\infty} m^{\, k\ell}\, \delta_k < \infty\,. \end{aligned} $$

(40)

Note that if the sequences {μ _k}_k≥0 and {δ _k}_k≥0 (called sum rule defects) are zero sequences, the corresponding non-stationary symbols satisfy sum rules of order ℓ + 1.

We continue by introducing a weaker relation than asymptotical equivalence termed asymptotic similarity (generalization of the one given in [16]) relating the properties of non-stationary subdivision schemes to the corresponding properties of certain stationary schemes.

Definition 5 ([9])

For the mask sequence {a ^[k]}_k≥0 we denote by $\mathcal {L}$ the set of masks which are accumulation points of this sequence,

$$\displaystyle \begin{aligned}\mathbf{a}\in \mathcal{L},\quad \mbox{if} \quad \exists \{k_n,\ n\in \mathbb{N} \}\ \ \mbox{such that}\ \ \lim_{n\rightarrow\infty}{\mathbf{a}}^{[k_n]}=\mathbf{a}\,. \end{aligned}$$

Definition 6

Two non-stationary schemes $\{S_{{\mathbf {a}}^{[k]}}\}_{k \ge 0}$ and $\{S_{{\mathbf {b}}^{[k]}}\}_{k \ge 0}$ are called asymptotically similar, if the corresponding sets of accumulation points coincide.

We already observed in Sect. 2.4 that in the stationary case, the rate of convergence of the corresponding subdivision scheme S _a and the Hölder regularity of the subdivision limits, can be given in terms of the joint spectral radius of the collection of certain matrices derived from the subdivision mask a and linked to the order of sum rules satisfied by the associated symbol $\mathcal {A}(\mathbf {z})$ (see also [52, 60]).

In the non-stationary setting the joint spectral radius has no straightforward generalization and is not directly applicable. Hence, in [9] a link between the stationary and non-stationary settings is established based on the sets of accumulation points $\mathcal {L}$ of {a ^[k]}_k≥0, and sufficient conditions for C ^ℓ-convergence and Hölder regularity of non-stationary schemes are provided. As in the level independent case, each mask in the set $\mathcal {L}$ determines a set of transition matrices. The restrictions of all these transition matrices to a certain finite dimensional difference subspace (denoted by V _ℓ) is denoted by $\mathcal {T}_{\mathcal {L}}|{ }_{V_\ell }$. Theorem 2 states that C ^ℓ-convergence and Hölder regularity of non-stationary schemes is obtained via the joint spectral radius $\rho _{\mathcal {L}}$ of the collection of matrices $\mathcal {T}_{\mathcal {L}}|{ }_{V_\ell }$.

Theorem 2 ([9, Theorem 2])

Let $\ell \in \mathbb {N}$ and let {δ _k}_k≥0 be defined in (39). Assume that the symbols of $\{ S_{{\mathbf {a}}^{(k)}}\}_{k \ge 0}$ satisfy approximate sum rules of order ℓ + 1 and that $\rho _{\mathcal {L}}:=\rho \left (\mathcal {T}_{\mathcal {L}}|{ }_{V_\ell }\right )<2^{-\ell }$ . Then the non-stationary scheme $\{ S_{{\mathbf {a}}^{[k]}}\}_{k \ge 0}$ is C ^ℓ -convergent and the Hölder exponent α of its limit functions satisfies

$$\displaystyle \begin{aligned}\alpha \ \ge \ \min \, \Bigl\{ -\log_2 \rho_{\mathcal{L}}\, , \,- \limsup\limits_{k \to \infty}\frac{\log_2 \delta_k}{k}\, \Bigr\}. \end{aligned}$$

In the univariate case more results are available. In [23] and also in [14], the link between approximate sum rules, generation/reproduction of exponential polynomials and approximation order is investigated, in the univariate case. In fact, the authors show that the property of reproducing N exponential polynomials implies approximate sum rules of order N and even approximation order N if asymptotic similarity to a convergent stationary scheme is assumed. Moreover, under asymptotic similarity to a convergent stationary scheme and reproduction of one exponential polynomial, the property of generating N exponential polynomials implies approximate sum rules of order N. The property of generating exponential polynomials guarantees the existence of difference operators exactly as in the stationary case. Moreover, approximate sum rules of order N and asymptotic similarity to a stationary C ^N−1 subdivision scheme provide sufficient conditions for C ^N−1 regularity of non-stationary subdivision schemes.

These results are stated in the next theorems where for $\varLambda \subset \mathbb {C}$ and $\varGamma (\varLambda )=\{\nu (\lambda ):\, \lambda \in \varLambda \}\subset \mathbb {N}_0$, the space EP _Γ(Λ),Λ, is defined as

$$\displaystyle \begin{aligned} EP_{\varGamma(\varLambda), \varLambda}:=\{x^j e^{\lambda\, x}\, :\ j=0,\ldots, \nu(\lambda)-1,\ \lambda\in \varLambda,\ \nu(\lambda)\in \varGamma(\varLambda) \}, \end{aligned} $$

(41)

and denoted as EP _Γ,Λ, for short. Obviously, its dimension is

$$\displaystyle \begin{aligned}\mbox{dim}\left(EP_{\varGamma, \varLambda}\right)=\sum_{\lambda\in \varLambda}\nu(\lambda).\end{aligned}$$

Theorem 3 ([23, Theorem 10])

Let $\{\mathcal {A}^{[k]}(z)\}_{k \ge 0}$ be the Laurent polynomials associated with a univariate non-stationary scheme which reproduces a space of univariate exponential polynomials EP _Γ,Λ . If $\mathit{\mbox{dim}}\left (EP_{\varGamma , \varLambda }\right )=N$ , then, for any ℓ = 0, ⋯ , N − 1, we have

$$\displaystyle \begin{aligned} | \mathcal{A}^{[k]}(1) -2|=O(2^{-kN}),\quad \left | \frac {d^\ell}{dz^\ell} \, \mathcal{A}^{[k]}(-1)\right | =O(2^{-k(N-\ell)}), \qquad k\to \infty. \end{aligned} $$

(42)

Theorem 4 ([23, Theorem 13])

Let $\{\mathcal {A}^{[k]}(z)\}_{k\ge 0}$ be the Laurent polynomials associated with a non-stationary subdivision scheme which generates the exponential polynomials space EP _Γ,Λ of dimension N, and reproduces one f ∈ EP _Γ,Λ . Moreover, let lim_k→∞ a ^[k] = a with S _a a convergent stationary subdivision scheme. Then, for any ℓ = 0, ⋯ , N − 1, we have

$$\displaystyle \begin{aligned} | \mathcal{A}^{[k]}(1) -2 | =O(2^{-k}),\quad \left | \frac {d^\ell}{dz^\ell} \mathcal{A}^{[k]}(-1)\right | =O(2^{-k(N-\ell)}), \qquad k\to \infty. \end{aligned} $$

(43)

Theorem 5 ([14, Theorem 4.3])

Assume that a convergent non-stationary scheme reproduces the exponential polynomials in the N-dimensional space EP _Γ,Λ . Assume further that lim_k→∞ a ^[k] = a with S _a a convergent stationary scheme. Then, for any initial data of the form ${\mathbf {f}}^{[0]}:=\{f(2^{-m}i)\}_{i\in \mathbb {Z}}$ for an integer m ≥ 0 with $f\in W^{\gamma }_\infty (\mathbb {R})$, $\gamma \in \mathbb {N}$ , the approximation error is bounded by

$$\displaystyle \begin{aligned} \|g_{{\mathbf{f}}^{[0]}} -f \|{}_\infty \leq c_f 2^{- \mathrm{min}(\gamma, N)m }\,, \end{aligned} $$

(44)

with c _f > 0 denoting a constant depending on f but not on m.

Extension of Theorems 3, 4 to the multivariate setting is still to be done. Some extension of Theorem 5 is in [53].

To conclude we recall the conditions non-stationary schemes need to satisfy to generate and reproduce (in the sense of (7) and (6)) exponential-polynomial functions, that is functions in the space

$$\displaystyle \begin{aligned}EP_{\varGamma, \varLambda}:=\{{\mathbf{x}}^{\boldsymbol\gamma} e^{\boldsymbol{\lambda} \cdot \mathbf{x}} : \ {\boldsymbol\gamma} \in \varGamma, \ \boldsymbol{\lambda} \in \varLambda \}, \quad \varGamma \subset \mathbb{N}_0^s, \quad \varLambda \subset \mathbb{C}^s. \end{aligned}$$

In fact, both generation and reproduction of exponential-polynomials can still be characterised in terms of algebraic conditions involving the parameter values

$$\displaystyle \begin{aligned}\{{\mathbf{t}}^{[k]}_{\alpha}=2^{-k}(\alpha+\boldsymbol{\tau}),\ \}_{\alpha\in \mathbb{Z}^s},\quad \mbox{with}\quad \boldsymbol{\tau}=(\tau_1,\tau_2)\ \ \mbox{in case}\ \ s=2.\end{aligned}$$

The conditions are in terms of the symbols $\{\mathcal {A}^{[k]}(\mathbf {z})\}_{k \ge 0}$ evaluated at

$$\displaystyle \begin{aligned}V_k{=}\{ (v_1, \ldots, v_s)^T : \ v_j{=} \epsilon_j e^{-(2^{-(k{+}1)}\boldsymbol{\lambda}_j)}, \ \boldsymbol{\lambda}{=}(\lambda_1,\ldots,\lambda_s) \in \varLambda, \ {\boldsymbol\epsilon} \in \{-1,1\}^s \ \}, \end{aligned}$$

and are collected in the following Theorem (taken from [11]) with the notation ${\mathbf {v}}^{\tau } = v_1^{\tau _1}\cdots v_s^{\tau _s}$ for $\gamma =(\gamma _1,\ldots ,\gamma _s\in \mathbb {N}_0^s$. There a non-singular scheme is a scheme generating limits identically equal to zero, only from zero initial data.’

Theorem 6 ([11, Theorem 4.7])

A non-singular subdivision scheme $\{S_{{\mathbf {a}}^{[k]}}\}_{k \ge 0}$ reproduces EP _Γ,Λ if and only if there exists a parameter $\boldsymbol {\tau } \in \mathbb {R}^s$ such that for all v ∈ V _k , k ≥ 0, ${\boldsymbol \gamma } \in \varGamma \subset \mathbb {N}_0$,

$$\displaystyle \begin{aligned} {\mathbf{v}}^{\boldsymbol\gamma} D^{\boldsymbol\gamma} \mathcal{A}^{[k]}(\mathbf{v})= \left\{ \begin{array}{ll} 2 \cdot {\mathbf{v}}^{\tau} q_{\boldsymbol\gamma}(\boldsymbol{\tau}), &\mathit{\mbox{for all}}\ \mathbf{v}\ \mathit{\mbox{corresponding to }}\ {\boldsymbol\epsilon}={\mathbf{1}}_s, \\ 0,& \mathit{\mbox{otherwise}}, \end{array} \right. \end{aligned} $$

(45)

where q _γ is the polynomial of degree |γ|, ${\boldsymbol \gamma } \in \mathbb {N}_0^s$ , given by

$$\displaystyle \begin{aligned} q_{\mathbf{0}}(\mathbf{z}):=1,\quad q_{\mathbf{j}}(z_1,\dots, z_s):=\prod_{i=1}^s \prod_{\ell_i=0}^{\gamma_i-1}(z_i-\ell_i), \quad {\boldsymbol\gamma}=(\gamma_1,\dots, \gamma_s). \end{aligned} $$

(46)

4.2 Non-stationary Schemes with Extraordinary Vertices/Faces

The analysis of a level-dependent subdivision scheme in the neighborhood of an irregular vertex/face is very challenging. The main difficulties are due to the fact that any approach based on the spectral analysis of the subdivision matrix and on the study of the characteristic map is not applicable. Indeed, no general tools to analyze non-stationary subdivision schemes at irregular vertices/faces were available till very recently. The only contributions to this analysis are the very recent paper [17] and the work of Jena et al. in [48], where a specific scheme is considered. In [17] a general procedure to check if a non-stationary subdivision scheme is convergent in the neighborhood of an extraordinary vertex/face is given. Moreover, sufficient conditions for the limit surface to be tangent plane continuous at the limit point of an extraordinary vertex/face are also given in that paper. Below we report both results.

We recall that the problem of extraordinary points occurs in the generation of surfaces that is in the case s = 2 and that we can restrict our analysis to meshes with a single extraordinary element surrounded by ordinary vertices (see [63]).

At each step, in the neighborhood of an irregular vertex/face, a subdivision algorithm relating the vertices of the k-th level mesh with those of the next level k + 1, can be conveniently encoded in the rows of a local subdivision matrix M _k whose dimension depends on the valency of the vertex. If the scheme is level-independent each step of the subdivision algorithm can be conveniently encoded in the rows of one local subdivision matrix M. The dimension of this matrix depends on the valency of the extraordinary vertex, too.

Theorem 7 ([17, Theorem 4.1])

Let ${\mathcal {S}}$ be a non-singular, non-stationary subdivision scheme whose action in an irregular region is described by a matrix sequence {M _k}_k≥0 . Let ${\mathcal {S}}$ be also rotationally symmetric. Moreover, let $\bar {\mathcal {S}}$ be a rotationally symmetric, stationary subdivision scheme associated with the matrix M in the same irregular region. If,

• (i) $\bar {\mathcal {S}}$ is convergent both in regular and irregular regions,

• (ii) ${\mathcal {S}}$ is asymptotically equivalent to $\bar {\mathcal {S}}$ in regular region,

• (iii) in the irregular regions, for all k ≥ 0, the matrices M _k and M satisfy

  $\|M_k-M\|{ }_{\infty } \leq \frac {{\mathcal {C}}}{\sigma ^k}$ with ${\mathcal {C}}$ a constant ( $0<{\mathcal {C}}<\infty$ ) and σ > 1,

then, for all initial data the non-stationary subdivision scheme ${\mathcal {S}}$ is convergent, both in regular regions and in the irregular one.

To understand the next result we recall from [17] that the iterated refinement of a surface subdivision scheme in the neighborhood of an irregular element generates a sequence of surface rings {R _k}_k≥1 corresponding to regular points which covers all of the surface except for the ‘central’ point which is the limit of the extraordinary vertex or face.

Theorem 8 ([17, Theorem 4.2])

Let ${\mathcal {S}}$ be as in Theorem 7 . Assume in the regular patch ring R _k+1 the action of ${\mathcal {S}}$ is described by a vector Φ _k+1(u, v) consisting of all the basic limit functions of $\mathcal {S}$ whose support intersect R _k+1 . Moreover, let $\bar {\mathcal {S}}$ be as in Theorem 7 associated with a matrix M in the same irregular region. Under the conditions:

• (i) $\bar {\mathcal {S}}$ is C ¹ -convergent in regular regions and its symbol $\mathcal {A}(\mathbf {z})$ contains the factor (1 + z ₁)(1 + z ₂);

• (ii) in regular regions ${\mathcal {S}}$ is defined by the symbols $\{\mathcal {A}^{(k)}(\mathbf {z})\}_{k \ge 0}$ where each $\mathcal {A}^{(k)}(\mathbf {z})$ contains the factor (1 + z ₁)(1 + z ₂);

• (iii) in regular regions ${\mathcal {S}}$ is asymptotically equivalent of order 1 to $\bar {\mathcal {S}}$;

• (iv) the eigenvalues of M are λ ₀ = 1, 0 < λ ₁ < 1, and the rest have absolute value less than λ ₁;

• (v) in the irregular regions, for all k ≥ 0, the matrices M _k and M satisfy, $\|M_k-M\|{ }_{\infty } \leq \frac {{\mathcal {C}}}{\sigma ^k}$ with ${\mathcal {C}}$ some constant ( $0<{\mathcal {C}}<\infty$ ) and $\sigma >\frac {1}{\lambda _1}>1$;

• (vi) the entries of Φ _k+1(u, v) sum up to 1;

the surface generated by ${\mathcal {S}}$ is normal continuous.

4.3 Masks of Growing Support

This section is devoted to a short description of non-stationary univariate subdivision schemes based on masks with growing supports. This is an important example of the potential strength of non-stationary schemes, since it allows for the generation of basic limit functions with high regularity and small support. For details concerning the analysis of these types of schemes and some of their applications we refer the reader to [13] and [33]. The analysis of smoothness of the schemes in these papers is based on the growing number of smoothing factors in their symbols and on Fourier analysis. The application is the generation of C ^∞ multiresolution analysis with high approximation order and the generation of C ^∞ compactly supported wavelets [13, 43].

The most famous example of a subdivision scheme of this type is given by the one based on the masks in (14) with n the subdivision level. As shown in [33], the basic limit function ϕ ₀ is the Rvachev’s up-function which is C ^∞ and supported on [0, 2], [56]. The first three steps of this scheme are depicted in the next Fig. 16.

Fig. 16

Three steps of the scheme with masks (14) with n the subdivision level (initial points in magenta)

A similar example of C ^∞ compactly-supported basic limit functions can be obtained if each $\mathcal {A}^{[k]}(\mathbf {z})$ is a product of k smoothing factors (see Definition 3). In this example the support is also [0, 2].

Another nice example is given by the interpolatory non-stationary scheme based on the masks (18) again with n the subdivision level (see [13, 33, 43]). The basic limit function ϕ ₀ is a function which is C ^∞ and supported in [−3, 3]. The first three steps of this scheme are shown in Fig. 17.

Fig. 17

Three steps of the scheme with masks (18) with n the subdivision level (initial points in magenta)

5 Open Problems in Non-stationary Subdivision

This closing section provides a short overview of open problems—specifically for non-stationary subdivision schemes—that are important to consider in the near future. Yet, due to space reasons, it will not be a detailed description as the one in the recent paper [59] related to the stationary case. Topics are listed in order of difficulty, with respect to the authors’ point of view.

• Bivariate results: from Sect. 4.1 it is evident that many results on convergence/regularity and approximation order are available in the univariate case only. Their extension to the bivariate setting is important. Also, construction of bivariate non-stationary interpolatory subdivision schemes and wavelets based on them is a topic that deserves further study;

• Applications: exponential reproducing non-stationary schemes could be used more extensively in image processing and highly smooth wavelets, as in [13], could be applied to real-world problems where the analysed functions are of high smoothness;

• Artefacts and unexpected behaviour of subdivision curves/surfaces: it would be important to better investigate the use of non-stationary tension parameters to tune and control subdivision surfaces;

• New tools for analysis of non-stationary schemes: we believe that to escape from the notions of asymptotic similarity or asymptotic equivalence would give a great impulse to non-stationary schemes;

• Increase the smoothness at extraordinary vertices of subdivision surfaces: we suppose that the possibility of changing the rule coefficients with the iterations can be crucial to overcome the limitation of stationary schemes that are limited to C ¹-smoothness at extraordinary vertices. The key idea for increasing the smoothness, is to allow the involvement of more and more points, i.e. the use of masks of growing support (see Sect. 4.3).