# A Six-Point Variant on the Lane-Riesenfeld Algorithm

Authors: Pakeeza Ashraf; Ghulam Mustafa; Jiansong Deng
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We apply six-point variant on the Lane-Riesenfeld algorithm to obtain a new family of subdivision schemes. We also determine the support, smoothness, Hölder regularity, magnitude of the artifact, and the shrinkage effect due to the change of integer smoothing parameter that characterizes the members of the family. The degree of polynomial reproduction also has been discussed. It is observed that the proposed schemes have less shrinkage effect and as a result better preserve the shape of control polygon.


---

## Body

## 1. Introduction

The Lane-Riesenfeld algorithm [1] is a competent subdivision algorithm for subdividing uniform B-splines. To subdivide a B-spline curve, the algorithm is composed of two phases. The first phase doubles the control point by simply taking each control point twice. This step is followed by a sequence of smoothing operators which is midpoint averaging. By applying this subdivision process recursively, a sequence of piecewise linear curves is generated that in the limit converges to the uniform B-spline defined by the original control points. We may refer the articles [2–4] to the readers for further insight about subdivision schemes. However, for smoothness of the schemes, we may refer to [5–7].In literature, there are different variants which are applied on the Lane-Riesenfeld algorithm. For example, Schaefer et al. [8] replaced the linear smoothing operator by nonlinear averaging rule in the Lane-Riesenfeld algorithm. They replaced the arithmetic mean with geometric mean to produce a subdivision scheme. Hormann and Sabin [9] offered a family of subdivision schemes by the convolution of uniform B-spline withkernel. Schaefer and Goldman [10] presented an algorithm for subdividing nonuniform B-splines of arbitrary degree in a manner similar to the Lane-Riesenfeld subdivision algorithm for uniform B-splines of arbitrary degree. Cashman et al. [11] presented generalized Lane-Riesenfeld algorithm; they used same operator to define the refine and each smoothing stage. They applied four-point [12] variant on the Lane-Riesenfeld algorithm to introduce new family of schemes.The best choice of smoothing operator is the one which keep the sense of balance among different properties of the schemes. For example, some of the smoothing operators give high degree of smoothness but very low degree of polynomial reproduction. So, choosing smoothing operator is a challenging task. One of the advantages of the proposed smoothing operator in this paper is that it keeps the balance among different properties of the schemes.In this paper, we apply six-point variant on the Lane-Riesenfeld algorithm to introduce family of subdivision schemes. Proposed family of schemes comprises two stages, that is,refine andsmoothing,similar to the Lane-Riesenfeld algorithm, but the only difference is that we have usedrefine stage to introduce new points in the same way as eachsmoothing stage. We also show how the support, smoothness, Hölder regularity, magnitude of the artifact, and the shrinkage effect change with the change of integer smoothing parameter that categorizes the members of the family. Moreover, we find that each member of the family has quintic polynomial reproduction. We have the following findings.(i)
The proposed smoothing operator keeps a balance among different properties of the schemes. It also gives best degree of polynomial reproduction.
(ii)
For the fixed number of control points, the number of smoothing stages is reciprocal to the magnitude of the artifacts.
(iii)
Level of continuity of the schemes does not increase in general by increasing the smoothing stage. However, there are upper and lower bounds on Hölder continuity which grow gradually with the increase of smoothing stage.
(iv)
The proposed schemes have less shrinkage effect and as a result better preserve the shape of control polygon.
(v)
The smoothing stages affect the shrinkage in the limit curve while refine stages are not the factor of this effect.


## 2. Theq-Schemes

Lane-Riesenfeld algorithm performs on an input sequenceP
=
{
p
i
}
i
∈
Z by using a refine stage W followed by m smoothing stages S. A subdivision step Q is therefore Q
=
S
m
W, where W
=
W
L is defined as refine stage in which each control point is doubled. S
=
S
L is the smoothing stage in which midpoint averaging is used to compute new control points; that is,
(1)
(
S
L
p
)
i
=
1
2
{
p
i
+
p
i
+
1
}
.
The 6-point scheme [13] samples a local quintic interpolant to every 6 adjacent values just like the Lane-Riesenfeld smoothing operator S
L which samples a local linear interpolant between every two adjacent values. This offers smoothing operator as
(2)
(
S
q
p
)
i
=
1
256
{
3
p
i
-
2
-
25
p
i
-
1
+
150
p
i
+
150
p
i
+
1
WW
-
25
p
i
+
2
+
3
p
i
+
3
}
.
The new algorithm uses refine stage
(3)
(
W
q
p
)
2
i
=
p
i
,
(
W
q
p
)
2
i
+
1
=
1
256
{
3
p
i
-
2
-
25
p
i
-
1
+
150
p
i
+
150
p
i
+
1
WWWWWWWi
-
25
p
i
+
2
+
3
p
i
+
3
}
.
So, the subdivision operator for new family of schemes is given by
(4)
Q
q
=
S
q
m
W
q
,
where refine stage W
q is pursued by m smoothing stages S
q. We call this family of schemes as the q-schemes. When we take 0th smoothing stage, then it reduces to the novel six-point scheme [13]. By increasing the number of smoothing stages, that is, m, we get new subdivision schemes. We can easily derive mask of the q-schemes for different values of m as follows.The factored form of the smoothing operatorS
q and refine stage W
q can be written as
(5)
W
q
(
z
)
=
(
1
+
z
2
)
6
(
3
z
-
2
-
18
z
-
1
+
38
-
18
z
+
3
z
2
4
)
,
S
q
(
z
)
=
(
1
+
z
2
)
(
3
z
-
2
-
28
z
-
1
+
178
-
28
z
+
3
z
2
128
)
.
So, it is clear from (4) that the symbol of the q-schemes with m smoothing stages can be written as
(6)
a
(
z
)
=
(
1
+
z
2
)
m
+
6
e
(
z
)
,
with
(7)
e
(
z
)
=
c
(
z
)
m
d
(
z
)
,
where
(8)
c
(
z
)
=
1
128
{
3
z
-
2
-
28
z
-
1
+
178
-
28
z
+
3
z
2
}
,
d
(
z
)
=
1
4
{
3
z
-
2
-
18
z
-
1
+
38
-
18
z
+
3
z
2
}
.
In Table 1, we present the mask α
m
N and complexity of the proposed schemes corresponding to m
=
0,1
,
2 and 3.Table 1
Complexity, support, and mask of theq-schemes corresponding to different values of m, and here N shows complexity of the schemes (i.e., 6-, 8-, 11-, and 13-point schemes) and S stands for support width.
m
N
S
Mask
0
6
10
α
6
0
=
1
256
[3,  0, −25,  0,  150,  256,  150,  0,  −25,  0,  3]
1
8
15
α
8
1
=
1
25
6
2
[9,  −75,  375,  1075,  −3375,  −6723,  17175,  57075,  57075,  17175,  −6723,  −3375,   1075,  375,  −75,  9]
2
11
20
α
11
2
=
1
25
6
3
[
27
,
-
450
,
4350
,
-
16050
,
7775
,
283608
,
-
135000
,
1798600
,
399750
,
9920100
,
16223412,  9920100,  399750,  1798600,  −135000,  283608,  7775,  −16050,  4350,  −450,  27]
3
13
25
α
13
3
=
1
25
6
4
[81,  −2025,  28350,  −220350,  1008900,  −1087220,  −8846550,  42100950,  68212925,     −277340325,  −404933940,  1216712500,  3659334000,  3659334000,  1216712500,  −404933940,    −277340325,  68212925,  42100950,  −8846550,  −1087220,  1008900,  −220350,  28350,  −2025,  81]Remark 1 (support of theq-schemes).
The basis function is the map from positions in the domain to the limit curve of the refinement corresponding to a single old vertex having a unit value and all the others zero.
Since the smoothing operatorS
q makes use of six adjacent values to insert a new one, the number of nonzero entries in the mask of S
q is 6 and the number of nonzero entries in the mask of refine stage W
q is 11; therefore, by following [14], we conclude that support width of basis limit function for S
q and W
q is 5 and 10, respectively.
Since the mask ofq-schemes is obtained by applying refine stage W
q on initial data followed by m smoothing stages S
q, then the support width of basis limit function for the q-schemes is 5
m
+
10. In Table 1, we present supports of some of the q-schemes. By applying the algebraic condition (14) and Lemma 4.2 of [15] on the symbol of q-schemes (6), we can prove that the degree of polynomial reproduction of each q-scheme is quintic.


## 3. Continuity Analysis of theq-Schemes

In this section, we make use of Laurent polynomial (symbol) formalism [16] to calculate integer class continuity of the q-schemes. Lower bounds on Hölder continuity are computed by using the following theorem and upper bounds are calculated by using Rioul's method [7]. Moreover, exact upper bounds on Hölder continuity can also be derived by using Floater and Muntingh algorithm [5].Theorem 2.
The lower bound on the Hölder continuity of the limit curves produced by theq-schemes with m smoothing stages is
(9)
(
m
+
6
)
-
log
⁡
2
(
1
+
10
(
15
8
)
m
)
.Proof.
Since by (6)
(10)
a
(
z
)
=
(
1
+
z
2
)
m
+
6
e
(
z
)
,
then by Rioul [7] the Hölder continuity of the limit curves is bounded from below by
(11)
(
m
+
6
)
-
log
⁡
2
∥
e
∥
.
Since c
(
z
) and d
(
z
) both are alternating symbols (i.e., its even coefficients are nonnegative and its odd coefficients are nonpositive), then e
(
z
)
=
c
(
z
)
m
d
(
z
) is also alternating and
(12)
∥
e
∥
=
max
⁡
(
e
e
,
e
o
)
,
where e
e and e
o are sum of even and odd coefficients of e
(
z
), respectively. Since by [11]
(13)
(
e
e
e
o
)
=
(
c
e
c
o
c
o
c
e
)
m
(
d
e
d
o
)
,
then
(14)
(
e
e
e
o
)
=
(
23
16
-
7
16
-
7
16
23
16
)
m
(
11
-
9
)
.
By eigenvalue decomposition, we have
(15)
(
e
e
e
o
)
=
1
2
(
-
1
1
1
1
)
(
15
8
0
0
1
)
m
(
-
1
1
1
1
)
(
11
-
9
)
.
This implies that
(16)
(
e
e
e
o
)
=
(
1
+
10
(
15
8
)
m
1
-
10
(
15
8
)
m
)
.
Thus, we have
(17)
∥
e
∥
=
1
+
10
(
15
8
)
m
.
Consequently, the Hölder continuity of the limit curves produced by the q-schemes with m smoothing stages is bounded from below by
(18)
(
m
+
6
)
-
log
⁡
2
(
1
+
10
(
15
8
)
m
)
.Table2 summarizes the continuity analysis of the q-schemes. We observe that the order of continuities achieved by q-schemes is reasonable, but it does not increase by increasing smoothing stages. However, there are upper and lower bounds on Hölder continuity which grow gradually with m.Table 2
Comparison of continuity of theq-schemes.
m
Continuity
Hölder continuity
Lower bound
Upper bound
0
2
2.540
2.830
1
3
2.696
3.246
2
3
2.823
3.649
3
3
2.935
4.040
4
3
3.038
4.421
5
4
3.137
4.795Remark 3.
Actually, the anonymous reviewer’s suggested smoothing operatorS
q
=
(
(
1
+
z
)
/
2
)
(
(
1
+
z
)
/
2
)
2
(
(
z
-
1
+
3
+
z
)
/
5
) significantly improve the smoothness of the schemes. That is, we get C
2, C
6, C
8, and C
8 smoothness for m
=
0,  1,  2, and 3, respectively, but with only linear degree of polynomial reproduction. While by using our proposed smoothing operator, we get up to quintic degree of reproduction with C
2,  C
3,  C
3, and C
3 smoothness for m
=
0,  1,  2, and 3, respectively.


## 4. Analysis of the Limit Curve

In this section, we present limit behavior, artifact analysis, and shrinkage effect of theq-schemes.


### 4.1. Limit Behavior of theq-Schemes

The limit behavior of the subdivision scheme can be analyzed by examining the eigenstructure of subdivision matrixM. For a nondefective matrix M, if there is n linearly independent eigenvectors ν
j corresponding to the eigenvalues μ
j, then it is possible to diagonalize M by transforming it by the eigenvectors and their inverse; that is, M
=
R
A
R
-
1. If the subdivision curve is C
0 (i.e., if all the rows of M sum to one, then M will have one eigenvector consisting of all ones and at least one eigenvalue must be one. If 1
=
μ
0
>
μ
j, then subdivision scheme is C
0.), then all the vertices in the local neighborhood P
∞ will shrink to the same point and thus we obtain limit stencil of the subdivision scheme mathematically
(19)
P
∞
=
lim
⁡
j
→
∞
P
j
=
M
∞
P
0
=
R
A
∞
R
-
1
P
0
.
The subdivision matrices for the q-schemes corresponding to the masks α
6
0,  α
8
1,  α
11
2, and α
13
3 presented in Table 1 have order 11,  15,  21, and 23, respectively. The limit stencils of these q-schemes for some smoothing stages are presented in Table 3. By applying limit stencil on consecutive control points in local neighborhood, we get limit position of the central one. Moreover, these stencils are useful to compute the magnitude of artifacts presented in the polygon.Table 3
Limit stencils of theq-schemes.
m
Limit stencils
0
l
0
= [
1
]
1
l
1 =  [0.00000012323, −0.00000041069, −0.000039800, −0.00088283, 0.016736, −0.10701, 0.59120, 0.59120, −0.10701, 0.016736, −0.00088283, −0.000039800, −0.00000041069, 0.00000012323]
2
l
2 = [0.000000000000026, 0.00000000044399, 0.000000023348, −0.0000024738, 0.00023116, 0.00086974, −0.0097205, 0.027417, 0.96241, 0.027417, −0.0097205, 0.00086974, 0.00023116, −0.0000024738, 0.000000023348, 0.000000023348, 0.00000000044399, 0.000000000000026]
3
l
3  =  [−0.000000000003485, 0.0000000011645, 0.00000031630, 0.000014667, 0.000074973, −0.0020474,  0.020295, −0.11208, 0.59374, 0.59374, −0.11208, 0.020295, −0.0020474, 0.000074973, 0.000014667,  0.00000031630, 0.0000000011645, −0.000000000003485]


### 4.2. Artifact Analysis of theq-Schemes

An artifact is defined to be any characteristic which is undesirable and cannot be separated by movement of control points which means that the curve holds spatial frequencies above the Shannon limit [17] relative to the density of the control polygon because features of the spatial frequency below this limit are removable by movements of the control points [18]. By definition, spatial frequency is the reciprocal of the number of control points per cycle and artifact magnitude is the function of the spatial frequency. We measure the amount of artifact presented in the polygon after the first subdivision level by using the following strategy. First, take the product of symmetric mask/symbol with symmetric limit stencil/symbol and then represent this product as polynomial in σ
=
(
1
+
z
)
/
2
z
1
/
2. Then, the magnitude of artifact can be calculated by substituting sin
(
π
ω
/
2
) for σ in that polynomial, where ω is the spatial frequency. The magnitude of the artifact presented in the limit curve is given by G
(
ω
)
=
(
1
/
2
)
H
(
sin
(
π
ω
/
2
)
) with the understanding that the data is sampled from a sinusoid with k
=
1
/
ω samples per cycle, where k is the number of control points.Theorem 4.
The amount of artifact presented in the limit curve produced by the 6-point binary scheme (i.e.,m
=
0) is
(20)
G
(
ω
)
=
1
2
{
12
η
10
-
30
η
8
+
20
η
6
}
,
where η
=
sin
(
π
ω
/
2
).Proof.
By substitutingm
=
0 in (6) and (7), we get 6-point binary scheme whose symbol in symmetric form can be written as
(21)
a
(
z
)
=
1
256
{
3
z
-
5
-
25
z
-
3
+
150
z
-
1
+
256
WW
+
150
z
-
25
z
3
+
3
z
5
}
.
This can be manipulated as
(22)
a
(
z
)
=
1
256
{
3
(
1
+
z
)
10
z
5
-
30
(
1
+
z
)
8
z
4
+
80
(
1
+
z
)
6
z
3
}
.
Since the symbol of the limit stencil l
0 (as given in Table 3) of 6-point binary scheme is l
0
(
z
)
=
1
z
0, this implies that
(23)
a
(
z
)
=
a
(
z
)
l
0
(
z
)
=
1
256
{
3
(
1
+
z
)
10
2
10
2
10
z
5
-
30
(
1
+
z
)
8
2
8
2
8
z
4

+

80
(
1
+
z
)
6
2
6
2
6
z
3
}
.
By representing it as polynomial in σ
=
(
1
+
z
)
/
2
z
1
/
2, we get
(24)
H
(
σ
)
=
12
σ
10
-
30
σ
8
+
20
σ
6
.
Since the magnitude of the artifact presented in the limit curve is given by G
(
ω
)
=
(
1
/
2
)
H
(
sin
(
π
ω
/
2
)
), then, by substituting sin
(
π
ω
/
2
) for σ in above polynomial, we get
(25)
G
(
ω
)
=
1
2
{
12
η
10
-
30
η
8
+
20
η
6
}
,
where η
=
sin
(
π
ω
/
2
), ω
=
(
1
/
k
), and k is the number of control points of the polygon.Similarly, we can prove the following theorems.Theorem 5.
The amount of artifact presented in the limit curve produced by the 8-point binary scheme (i.e.,m
=
1) is
(26)
G
(
ω
)
=
1
2
{
0.00454
η
28
-
0.04505
η
26
+
0.11351
η
24
Wi
+
0.16850
η
22
+
0.9078
η
20
-
17.721
η
18
Wi
+
82.710
η
16
-
199.84
η
14
+
281.50
η
12
W
-
220.79
η
10
+
75.003
η
8
}
.Theorem 6.
The amount of artifact presented in the limit curve produced by the 11-point binary scheme (i.e.,m
=
2) is(27)
G
(
ω
)
=
1
2
{
0.0000000028754
η
36
+
0.000012238
η
34
Wi
+
0.0000061307
η
32
-
0.0053021
η
30
Wi
+
0.15761
η
28
-
1.3285
η
26
+
5.6356
η
24
Wi
-
13.040
η
22
+
14.009
η
20
+
1.8945
η
18
Wi
-
8.3782
η
16
-
49.664
η
14
+
147.25
η
12
W
-
156.89
η
10
+
62.358
η
8
}
.Theorem 7.
The amount of artifact presented in the limit curve produced by the 13-point binary scheme (i.e.,m
=
3) is
(28)
G
(
ω
)
=
1
2
{
-
0.00000014453
η
42
+
0.000014495
η
40
Wi
+
0.00060407
η
38
-
0.0017688
η
36
Wi
-
0.042638
η
34
+
0.36221
η
32
-
0.76351
η
30
Wi
-
4.8648
η
28
+
45.306
η
26
-
191.67
η
24
Wi
+
534.46
η
22
-
1071.8
η
20
+
1583.8
η
18
Wi
-
1708.5
η
16
+
1288.1
η
14
-
611.30
η
12
W
+
137.94
η
10
}
.Similarly, we can determine the amount of artifact presented in the limit curves for other values ofm. The amount of artifacts of the q-schemes for four (i.e., m
=
0,1
,
2,3) smoothing stages S
q is shown in Figure 1. The magnitude of the artifact in the limit curve is plotted against the number of control points k. It is noticed that when the smoothing stages increase the magnitude of the artifact decreases for the same number of control points.Figure 1
Artifact behavior of theq-schemes.


### 4.3. Shrinkage Effect of theq-Schemes

A control polygon is a sequence of points in space that is commonly used to manage the shape of an object. We apply subdivision scheme on closed control polygons to create visually smooth limit curves. Figure2 shows limit curves generated by the q-schemes with different number of smoothing stages. Note that, as we increase the number of smoothing stages, final limit curve has larger distance from the control polygon. Since this shrinkage effect is only due to the smoothing stages, it is clear that the refine stage is not a factor of this effect. Therefore, we can measure this shrinkage effect by only examining smoothing stage. We can represent smoothing stage for a closed k-point polygon as the matrix(29)
1
256
(
-
25
150
150
-
25
3
0
⋯
0
0
3
3
-
25
150
150
-
25
3
⋯
0
0
0
0
3
-
25
150
150
-
25
⋯
0
0
0
⋮
⋱
⋱
⋱
⋱
⋱
⋱
⋮
-
25
3
0
0
0
0
⋯
-
25
150
150
150
-
25
3
0
0
0
⋯
3
-
25
150
150
150
-
25
3
0
0
⋯
0
3
-
25
)
∈
ℝ
k
×
k
.Since the above matrix is circulant, by [19], its eigenvalues are
(30)
μ
j
=
1
256
(
-
25
+
150
e
2
π
i
j
/
k
+
150
e
4
π
i
j
/
k
-
25
e
6
π
i
j
/
k
WW
+
3
e
8
π
i
j
/
k
+
3
e
-
2
π
i
j
/
k
)
,
where j
=
0,1
,
…
,
k
-
1.Limit curves generated by theq-scheme by applying 0, 1, 2, and 3 smoothing stages.
(a)
(b)Here, we can determine that the dominant eigenvalueμ
0
=
1 and its corresponding eigenvector is also a column vector consisting of all ones. This shows a dominant behavior that as we increase the smoothing stages, say m
→
∞, the whole configuration falls down towards barycenter of the original control polygon.The subdominant eigenvaluesμ
1 and μ
k
-
1 are complex conjugate of each other and shrinkage of the polygon towards its barycenter as well as a phase shift is decided by them. Disregarding this rotation, the rate of shrinkage for each smoothing stage is |
μ
1
|
=
|
μ
k
-
1
|. We plot this rate of shrinkage against the number of smoothing stages m in Figure 3. From Figure 3, it is apparent that the q-schemes bear less shrinkage when the number of smoothing stages increases and as a result better preserve the shape of control polygon as compared to C-schemes [11].Rate of shrinkage plotted for theC-schemes [11] and proposed q-schemes against the number of smoothing stages m, for polygons having 4, 8, and 16 points.
(a)
C-schemes [11]
(b)
proposedq-schemes


## 4.1. Limit Behavior of theq-Schemes

The limit behavior of the subdivision scheme can be analyzed by examining the eigenstructure of subdivision matrixM. For a nondefective matrix M, if there is n linearly independent eigenvectors ν
j corresponding to the eigenvalues μ
j, then it is possible to diagonalize M by transforming it by the eigenvectors and their inverse; that is, M
=
R
A
R
-
1. If the subdivision curve is C
0 (i.e., if all the rows of M sum to one, then M will have one eigenvector consisting of all ones and at least one eigenvalue must be one. If 1
=
μ
0
>
μ
j, then subdivision scheme is C
0.), then all the vertices in the local neighborhood P
∞ will shrink to the same point and thus we obtain limit stencil of the subdivision scheme mathematically
(19)
P
∞
=
lim
⁡
j
→
∞
P
j
=
M
∞
P
0
=
R
A
∞
R
-
1
P
0
.
The subdivision matrices for the q-schemes corresponding to the masks α
6
0,  α
8
1,  α
11
2, and α
13
3 presented in Table 1 have order 11,  15,  21, and 23, respectively. The limit stencils of these q-schemes for some smoothing stages are presented in Table 3. By applying limit stencil on consecutive control points in local neighborhood, we get limit position of the central one. Moreover, these stencils are useful to compute the magnitude of artifacts presented in the polygon.Table 3
Limit stencils of theq-schemes.
m
Limit stencils
0
l
0
= [
1
]
1
l
1 =  [0.00000012323, −0.00000041069, −0.000039800, −0.00088283, 0.016736, −0.10701, 0.59120, 0.59120, −0.10701, 0.016736, −0.00088283, −0.000039800, −0.00000041069, 0.00000012323]
2
l
2 = [0.000000000000026, 0.00000000044399, 0.000000023348, −0.0000024738, 0.00023116, 0.00086974, −0.0097205, 0.027417, 0.96241, 0.027417, −0.0097205, 0.00086974, 0.00023116, −0.0000024738, 0.000000023348, 0.000000023348, 0.00000000044399, 0.000000000000026]
3
l
3  =  [−0.000000000003485, 0.0000000011645, 0.00000031630, 0.000014667, 0.000074973, −0.0020474,  0.020295, −0.11208, 0.59374, 0.59374, −0.11208, 0.020295, −0.0020474, 0.000074973, 0.000014667,  0.00000031630, 0.0000000011645, −0.000000000003485]


## 4.2. Artifact Analysis of theq-Schemes

An artifact is defined to be any characteristic which is undesirable and cannot be separated by movement of control points which means that the curve holds spatial frequencies above the Shannon limit [17] relative to the density of the control polygon because features of the spatial frequency below this limit are removable by movements of the control points [18]. By definition, spatial frequency is the reciprocal of the number of control points per cycle and artifact magnitude is the function of the spatial frequency. We measure the amount of artifact presented in the polygon after the first subdivision level by using the following strategy. First, take the product of symmetric mask/symbol with symmetric limit stencil/symbol and then represent this product as polynomial in σ
=
(
1
+
z
)
/
2
z
1
/
2. Then, the magnitude of artifact can be calculated by substituting sin
(
π
ω
/
2
) for σ in that polynomial, where ω is the spatial frequency. The magnitude of the artifact presented in the limit curve is given by G
(
ω
)
=
(
1
/
2
)
H
(
sin
(
π
ω
/
2
)
) with the understanding that the data is sampled from a sinusoid with k
=
1
/
ω samples per cycle, where k is the number of control points.Theorem 4.
The amount of artifact presented in the limit curve produced by the 6-point binary scheme (i.e.,m
=
0) is
(20)
G
(
ω
)
=
1
2
{
12
η
10
-
30
η
8
+
20
η
6
}
,
where η
=
sin
(
π
ω
/
2
).Proof.
By substitutingm
=
0 in (6) and (7), we get 6-point binary scheme whose symbol in symmetric form can be written as
(21)
a
(
z
)
=
1
256
{
3
z
-
5
-
25
z
-
3
+
150
z
-
1
+
256
WW
+
150
z
-
25
z
3
+
3
z
5
}
.
This can be manipulated as
(22)
a
(
z
)
=
1
256
{
3
(
1
+
z
)
10
z
5
-
30
(
1
+
z
)
8
z
4
+
80
(
1
+
z
)
6
z
3
}
.
Since the symbol of the limit stencil l
0 (as given in Table 3) of 6-point binary scheme is l
0
(
z
)
=
1
z
0, this implies that
(23)
a
(
z
)
=
a
(
z
)
l
0
(
z
)
=
1
256
{
3
(
1
+
z
)
10
2
10
2
10
z
5
-
30
(
1
+
z
)
8
2
8
2
8
z
4

+

80
(
1
+
z
)
6
2
6
2
6
z
3
}
.
By representing it as polynomial in σ
=
(
1
+
z
)
/
2
z
1
/
2, we get
(24)
H
(
σ
)
=
12
σ
10
-
30
σ
8
+
20
σ
6
.
Since the magnitude of the artifact presented in the limit curve is given by G
(
ω
)
=
(
1
/
2
)
H
(
sin
(
π
ω
/
2
)
), then, by substituting sin
(
π
ω
/
2
) for σ in above polynomial, we get
(25)
G
(
ω
)
=
1
2
{
12
η
10
-
30
η
8
+
20
η
6
}
,
where η
=
sin
(
π
ω
/
2
), ω
=
(
1
/
k
), and k is the number of control points of the polygon.Similarly, we can prove the following theorems.Theorem 5.
The amount of artifact presented in the limit curve produced by the 8-point binary scheme (i.e.,m
=
1) is
(26)
G
(
ω
)
=
1
2
{
0.00454
η
28
-
0.04505
η
26
+
0.11351
η
24
Wi
+
0.16850
η
22
+
0.9078
η
20
-
17.721
η
18
Wi
+
82.710
η
16
-
199.84
η
14
+
281.50
η
12
W
-
220.79
η
10
+
75.003
η
8
}
.Theorem 6.
The amount of artifact presented in the limit curve produced by the 11-point binary scheme (i.e.,m
=
2) is(27)
G
(
ω
)
=
1
2
{
0.0000000028754
η
36
+
0.000012238
η
34
Wi
+
0.0000061307
η
32
-
0.0053021
η
30
Wi
+
0.15761
η
28
-
1.3285
η
26
+
5.6356
η
24
Wi
-
13.040
η
22
+
14.009
η
20
+
1.8945
η
18
Wi
-
8.3782
η
16
-
49.664
η
14
+
147.25
η
12
W
-
156.89
η
10
+
62.358
η
8
}
.Theorem 7.
The amount of artifact presented in the limit curve produced by the 13-point binary scheme (i.e.,m
=
3) is
(28)
G
(
ω
)
=
1
2
{
-
0.00000014453
η
42
+
0.000014495
η
40
Wi
+
0.00060407
η
38
-
0.0017688
η
36
Wi
-
0.042638
η
34
+
0.36221
η
32
-
0.76351
η
30
Wi
-
4.8648
η
28
+
45.306
η
26
-
191.67
η
24
Wi
+
534.46
η
22
-
1071.8
η
20
+
1583.8
η
18
Wi
-
1708.5
η
16
+
1288.1
η
14
-
611.30
η
12
W
+
137.94
η
10
}
.Similarly, we can determine the amount of artifact presented in the limit curves for other values ofm. The amount of artifacts of the q-schemes for four (i.e., m
=
0,1
,
2,3) smoothing stages S
q is shown in Figure 1. The magnitude of the artifact in the limit curve is plotted against the number of control points k. It is noticed that when the smoothing stages increase the magnitude of the artifact decreases for the same number of control points.Figure 1
Artifact behavior of theq-schemes.


## 4.3. Shrinkage Effect of theq-Schemes

A control polygon is a sequence of points in space that is commonly used to manage the shape of an object. We apply subdivision scheme on closed control polygons to create visually smooth limit curves. Figure2 shows limit curves generated by the q-schemes with different number of smoothing stages. Note that, as we increase the number of smoothing stages, final limit curve has larger distance from the control polygon. Since this shrinkage effect is only due to the smoothing stages, it is clear that the refine stage is not a factor of this effect. Therefore, we can measure this shrinkage effect by only examining smoothing stage. We can represent smoothing stage for a closed k-point polygon as the matrix(29)
1
256
(
-
25
150
150
-
25
3
0
⋯
0
0
3
3
-
25
150
150
-
25
3
⋯
0
0
0
0
3
-
25
150
150
-
25
⋯
0
0
0
⋮
⋱
⋱
⋱
⋱
⋱
⋱
⋮
-
25
3
0
0
0
0
⋯
-
25
150
150
150
-
25
3
0
0
0
⋯
3
-
25
150
150
150
-
25
3
0
0
⋯
0
3
-
25
)
∈
ℝ
k
×
k
.Since the above matrix is circulant, by [19], its eigenvalues are
(30)
μ
j
=
1
256
(
-
25
+
150
e
2
π
i
j
/
k
+
150
e
4
π
i
j
/
k
-
25
e
6
π
i
j
/
k
WW
+
3
e
8
π
i
j
/
k
+
3
e
-
2
π
i
j
/
k
)
,
where j
=
0,1
,
…
,
k
-
1.Limit curves generated by theq-scheme by applying 0, 1, 2, and 3 smoothing stages.
(a)
(b)Here, we can determine that the dominant eigenvalueμ
0
=
1 and its corresponding eigenvector is also a column vector consisting of all ones. This shows a dominant behavior that as we increase the smoothing stages, say m
→
∞, the whole configuration falls down towards barycenter of the original control polygon.The subdominant eigenvaluesμ
1 and μ
k
-
1 are complex conjugate of each other and shrinkage of the polygon towards its barycenter as well as a phase shift is decided by them. Disregarding this rotation, the rate of shrinkage for each smoothing stage is |
μ
1
|
=
|
μ
k
-
1
|. We plot this rate of shrinkage against the number of smoothing stages m in Figure 3. From Figure 3, it is apparent that the q-schemes bear less shrinkage when the number of smoothing stages increases and as a result better preserve the shape of control polygon as compared to C-schemes [11].Rate of shrinkage plotted for theC-schemes [11] and proposed q-schemes against the number of smoothing stages m, for polygons having 4, 8, and 16 points.
(a)
C-schemes [11]
(b)
proposedq-schemes


## 5. Summary

In this paper, we have applied 6-point variant on Lane-Riesenfeld algorithm [1] to generate a new family of schemes, which we call the q-schemes. Furthermore, we have evaluated the relation among support, smoothness, Hölder continuity, and number of smoothing stages. The degree of polynomial reproduction also has been discussed. We have evaluated the rate of shrinkage of limit curve from original control polygon at different number of smoothing stages and make comparison with C-schemes [11]. Artifact and limit stencil analysis of proposed schemes is also carried out.



---

*Source: 628285-2014-05-08.xml*