# Trajectory Estimation for Exponential Parameterization and Different Samplings

Ryszard Kozera, Lyle Noakes, Piotr Szmielew

► To cite this version:

Ryszard Kozera, Lyle Noakes, Piotr Szmielew. Trajectory Estimation for Exponential Parameterization and Different Samplings. 12th International Conference on Information Systems and Industrial Management (CISIM), Sep 2013, Krakow, Poland. pp.430-441, 10.1007/978-3-642-40925-7_40. hal-01496089

HAL Id: hal-01496089

https://inria.hal.science/hal-01496089

Submitted on 27 Mar 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Trajectory Estimation for Exponential Parameterization and Different Samplings

Ryszard Kozera¹, Lyle Noakes² and Piotr Szmielew¹

¹ Warsaw University of Life Sciences - SGGW
Faculty of Applied Informatics and Mathematics
Nowoursynowska str. 159, 02-776 Warsaw, Poland

² Department of Mathematics and Statistics
The University of Western Australia
35 Stirling Highway, Crawley W.A. 6009, Perth, Australia

ryszard_kozera@sggw.pl lyle.noakes@maths.uwa.edu.au
p.szmielew@ieee.org

**Abstract.** This paper discusses the issue of fitting reduced data $Q_m = \{q_i\}_{i=0}^m$ with piecewise-quadratics to estimate an unknown curve $\gamma$ in Euclidean space. The interpolation knots $\{t_i\}_{i=0}^m$ with $\gamma(t_i) = q_i$ are assumed to be unknown. Such non-parametric interpolation commonly appears in computer graphics and vision, engineering and physics [1]. We analyze a special scheme aimed to supply the missing knots $\{\hat{t}_i^\lambda\}_{i=0}^m \approx \{t_i\}_{i=0}^m$ (with $\lambda \in [0, 1]$) - the so-called exponential parameterization used in computer graphics for curve modeling. A blind uniform guess, for $\lambda = 0$ coupled with more-or-less uniform samplings yields a linear convergence order in trajectory estimation. In addition, for $\varepsilon$-uniform samplings ($\varepsilon \ge 0$) and $\lambda = 0$ an extra acceleration $\alpha_\varepsilon(0) = \min\{3, 1+2\varepsilon\}$ follows [2]. On the other hand, for $\lambda = 1$ cumulative chords render a cubic convergence order $\alpha(1) = 3$ within a general class of admissible samplings [3]. A recent theoretical result [4] is that for $\lambda \in [0, 1)$ and more-or-less uniform samplings, sharp orders $\alpha(\lambda) = 1$ eventuate. Thus no acceleration in $\alpha(\lambda) < \alpha(1) = 3$ prevails while $\lambda \in [0, 1)$. Finally, another recent result [5] proves that for all $\lambda \in [0, 1)$ and $\varepsilon$-uniform samplings, the respective accelerated orders $\alpha_\varepsilon(\lambda) = \min\{3, 1+2\varepsilon\}$ are independent of $\lambda$. The latter extends the case of $\alpha_\varepsilon(\lambda = 0) = 1+2\varepsilon$ to all $\lambda \in [0, 1)$. We revisit here [4] and [5] and verify their sharpness experimentally.

**Keywords:** Interpolation, numerical analysis, computer graphics and vision

## 1 Introduction

The sampled data points $Q_m = \{q_i\}_{i=0}^m$ with $\gamma(t_i) = q_i \in \mathbb{R}^n$ define the pair $(\{t_i\}_{i=0}^m, Q_m)$ commonly coined as non-reduced data. We also require here that $t_i < t_{i+1}$ and $q_i \neq q_{i+1}$ hold. Moreover, assume that $\gamma: [0, T] \to \mathbb{R}^n$ (with $0 < T < \infty$) is sufficiently smooth (specified later) and that it defines a regular curve $\dot{\gamma}(t) \neq 0$. In order to estimate the unknown curve $\gamma$ with an arbitrary interpolant $\tilde{\gamma}: [0, T] \to \mathbb{R}^n$ it is necessary to assume that $\{t_i\}_{i=0}^m \in V_G^m$, i.e. that the following admissibility condition is satisfied:

$$ \lim_{m \to \infty} \delta_m = 0, \quad \text{where} \quad \delta_m = \max_{0 \le i \le m-1} (t_{i+1} - t_i). \qquad (1) $$
We omit here the subscript *m* in $\delta_m$ by setting $\delta = \delta_m$. In this paper, two substantial subfamilies of $V_G^m$ are discussed.

The first one $V_{mol}^m \subset V_G^m$ includes more-or-less uniform samplings [6], [7]:

$$ \beta\delta \le t_{i+1} - t_i \le \delta, \qquad (2) $$

for some $\beta \in (0, 1]$. The left inequality in (2) excludes samplings with distance between consecutive knots smaller than $\beta\delta$. The right inequality follows from (1). Condition (2), as shown in [6], can be replaced by the equivalent condition (3) holding for each $i = 0, 1, \dots, m-1$ and some constants $0 < K_1 \le K_2$:

$$ \frac{K_1}{m} \le t_{i+1} - t_i \le \frac{K_2}{m}. \qquad (3) $$

The second subfamily $V_\epsilon^m \subset V_G^m$ is that of $\epsilon$-uniform samplings [2]:

$$ t_i = \phi\left(\frac{iT}{m}\right) + O\left(\frac{1}{m^{1+\epsilon}}\right), \qquad (4) $$

where $\epsilon \ge 0$, $\phi: [0, T] \to [0, T]$ is smooth and $\dot{\phi} > 0$ (so that $t_i < t_{i+1}$). Clearly, the smaller $\epsilon$ gets, the bigger distortion of uniform distribution occurs (modulo $\phi$). The case when $\epsilon = 0$ needs a special attention so that the inequality $t_i < t_{i+1}$ holds. However, the latter is asymptotically guaranteed for all $\epsilon$ positive. Note that each $\epsilon$-uniform sampling with $\epsilon > 0$ is also more-or-less uniform [6].

## 2 Problem Formulation and Motivation

We say that the family $F_\delta: [0, T] \to \mathbb{R}^n$ satisfies $F_\delta = O(\delta^\alpha)$ if $\|F_\delta\| = O(\delta^\alpha)$, where $\|\cdot\|$ denotes the Euclidean norm. Another words there are constants $K > 0$ and $\delta_0 > 0$ such that $\|F_\delta\| \le K\delta^\alpha$, for all $\delta \in (0, \delta_0)$ and $t \in [0, T] - [8]$.

A standard result for non-reduced data ($\{t_i\}_{i=0}^m, Q_m$) for piecewise r-degree polynomial $\tilde{\gamma} = \tilde{\gamma}_r$ reads [6], [9]:

**Theorem 1.** Let $\gamma \in C^{r+1}$ be a regular curve $\gamma: [0, T] \to \mathbb{R}^n$ with knot parameters $\{t_i\}_{i=0}^m \in V_G^m$ given. Then a piecewise r-degree Lagrange polynomial interpolation $\tilde{\gamma}_r$ used with $\{t_i\}_{i=0}^m$ known, yields a sharp estimate:

$$ \tilde{\gamma}_r = \gamma + O(\delta^{r+1}). \qquad (5) $$

By (5) piecewise-quadratics (-cubics) $\tilde{\gamma}_2$ ($\tilde{\gamma}_3$) yield cubic (quartic) order error terms.

In many applications in computer graphics and computer vision, engineering or physics, the so-called reduced data $Q_m$ are encountered (see e.g. [1], [10], [11], or [12]), where the knots $\{t_i\}_{i=0}^m$ are unknown and have to be first guessed somehow. A family of the so-called exponential parameterization $\{\hat{t}_i\}_{i=0}^m \approx \{t_i\}_{i=0}^m$ is commonly used for curve modeling [11], [13]:

$$ \hat{t}_0 = 0, \quad \hat{t}_{i+1} = \hat{t}_i + \|q_{i+1} - q_i\|^\lambda, \qquad (6) $$
where $0 \le \lambda \le 1$ and $i = 0, 1, \dots, m-1$. The cases when $\lambda \in \{1, 0.5, 0\}$, yield cumulative chords, centripetal or blind uniform parameterizations, respectively.

We call a piecewise $r$-degree polynomial based on (6) and $Q_m$ as $\hat{\gamma} = \hat{\gamma}_r : [0, \hat{T}] \to \mathbb{R}^n$, where $\hat{T} = \sum_{i=0}^{m-1} \|q_{i+1} - q_i\|^\lambda$. Note that in case of any reduced data $Q_m$ for asymptotics estimation of $\gamma$ by $\hat{\gamma}_r$, a re-parameterization $\psi : [0, T] \to [0, \hat{T}]$ synchronizing both domains of $\gamma$ and $\hat{\gamma}_r$, needs to be defined (see e.g. [6]).

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Interpolating three points $Q_2 = \{(0,0), (0,0.05), (1,0)\}$ with $\hat{\gamma}_2$, for $\lambda = 0, 1/3, 1/2, 5/6, 1 \in [0,1]$</figcaption></figure>

*Example 1.* Figure 1 shows different $\hat{\gamma}_2$ passing through $Q_2$ with various $\lambda \in \{0, 1/3, 1/2, 5/6, 1\}$ set in (6). Such curves' fluctuation given different knots and interpolation schemes is commonly exploited for sparse data in 2D and 3D computer graphics in the context of curve modeling - see [10], [11], or [12]. □

*Example 2.* Another application, elucidating the influence of knots selection on interpolation stems from the computer vision field. Figure 2 shows the image of the same knee joint section. The goal is to isolate from such image the kneecap and to find its area, amounting here to $A = 5237$ pixels. The interpolation points $Q_m$ positioned on the boundary are selected e.g. by the physician (here $m = 5$). Of course, the internal parametrization of the kneecap boundary (i.e. some curve $\gamma$) remains unknown. Upon invoking $\hat{\gamma}_2$ (with three quadratic segments) coupled with guessed knots in accordance with (6) we obtain different estimates of $\gamma$ by $\hat{\gamma}_2$ and consequently various kneecap area $A_\lambda$ approximations. Namely for $\lambda \in \{0, 1/4, 1/2, 3/4, 1\}$ the following $A \approx A_\lambda \in \{5197, 5209, 5234, 5293, 5376\}$ (in pixels) hold, respectively. The centripetal parameterization (i.e. for $\lambda = 1/2$) on this specific sparse data $Q_m$ yields the best result. □

More *real data examples* emphasizing the importance of the knots' selection for a given interpolation scheme in *computer graphics* (light-source motion estimation or image rendering), *computer vision* (image segmentation or video compression), *geometry* (trajectory, curvature or area estimation) or in *engineering and physics* (fast particles' motion estimation) can be found e.g. in [1].
<figure><img src="image_3.png" /><figcaption>Fig. 2. Isolating the kneecap with $\hat{\gamma}_2$, for a) $\lambda = 0$, b) $\lambda = 0.5$, c) $\lambda = 1$</figcaption></figure>

## 2.1 Uniform Parameterization - $\lambda = 0$

The case when $\lambda = 0$, transforms (6) into to blind uniform knots' guesses $\hat{t}_i = i$. For $r = 2$ and $\lambda = 0$ in (6) the following holds [2]:

**Theorem 2.** Let the unknown $\{t_i\}_{i=0}^m$ be sampled $\varepsilon$-uniformly, where $\varepsilon > 0$ and $\gamma \in C^4$. Then there is a uniform piecewise-quadratic Lagrange interpolant $\hat{\gamma}_2 : [0, \hat{T} = m] \to \mathbb{R}^n$, calculable in terms of $Q_m$ (with $\hat{t}_i = i$) and piecewise $C^\infty$ re-parameterization $\psi : [0, T] \to [0, \hat{T}]$ such that sharp estimates hold:

$$ \hat{\gamma}_2 \circ \psi = \gamma + O(\delta^{\min\{3,1+2\varepsilon\}}). \qquad (7) $$

Th. 2 with $\alpha_{\varepsilon>0}(0) = \min\{3, 1+2\varepsilon\}$ extends to $\varepsilon = 0$ provided $\{t_i\}_{i=0}^m$ satisfies $t_i < t_{i+1}$ and falls also into more-or-less uniformity (2). The latter renders linear convergence order $\alpha_{\varepsilon=0}(0) = 1$ - see [6]. Evidently, for $\varepsilon$-uniform samplings there is an acceleration from $\alpha_{\varepsilon=0}(0) = 1$ via $\alpha_{0<\varepsilon<1}(0) = 1+2\varepsilon$ to $\alpha_{\varepsilon\ge 1}(0) = 3$.

## 2.2 Cumulative Chords - $\lambda = 1$

The opposite case when $\lambda = 1$ in (6) renders cumulative chords [11], [12]. This choice of $\{t_i\}_{i=0}^m$ uses the geometry of $Q_m$ and gives better trajectory estimation (at least for $r = 2, 3$) as opposed to $\lambda = 0$ and (7) [3]:

**Theorem 3.** Let $\gamma$ be a regular $C^k$ curve in $\mathbb{R}^n$, where $k \ge r+1$ and $r = 2, 3$ sampled according to (1). Let $\hat{\gamma}_r : [0, \hat{T} = \sum_{i=0}^{m-1} \|q_{i+1} - q_i\|] \to \mathbb{R}^n$ be the cumulative chord piecewise-quadratic(-cubic) interpolant defined by $Q_m$ and $\lambda = 1$ in (6). Then there is a piecewise-$C^r$ re-parameterization $\psi : [0, T] \to [0, \hat{T}]$, with

$$ \hat{\gamma}_r \circ \psi = \gamma + O(\delta^{r+1}). \qquad (8) $$

The asymptotics from Th. 2 and Th. 3 are sharp - see [3] and [6]. For $r = 2$ and $\lambda = 1$, formula (8) yields the cubic order $\alpha(1) = 3$ which not only improves (7) but also matches the non-reduced data case (5) (with $r = 2, 3$).
## 2.3 Exponential Parameterization - $\lambda \in [0, 1]$

Recent research by [4] extends the results from Th. 2 (where $\lambda = 0$) and Th. 3 (where $\lambda = 1$ with $r = 2$) to the remaining cases of exponential parameterization (6) i.e. to $\lambda \in [0, 1]$. As proved in [4], for more-or-less uniform samplings (2), (6) and $r = 2$ any choice of $\lambda \in [0, 1)$ does not improve the asymptotics for $\gamma$ approximation. In fact, for all $\lambda \in [0, 1)$ we have $\alpha(\lambda) = 1$. Indeed we obtain [4]:

**Theorem 4.** Suppose $\gamma$ is a regular $C^3$ curve in $\mathbb{R}^n$ sampled more-or-less uniformly (2). Let $\hat{\gamma}_2 : [0, \hat{T}] = \sum_{i=0}^{m-1} \|q_{i+1} - q_i\|^\lambda \to \mathbb{R}^n$ be the piecewise-quadratic interpolant defined by $Q_m$ and (6) (with $\lambda \in [0, 1]$). Then there is a piecewise-$C^\infty$ re-parameterization $\psi : [0, T] \to [0, \hat{T}]$, such that for $\lambda \in [0, 1)$ we have:

$$ \hat{\gamma}_2 \circ \psi = \gamma + O(\delta). \qquad (9) $$

In addition, for either $\{t_i\}_{i=0}^m$ uniform or $\lambda = 1$ used with samplings (1) the following holds:

$$ \hat{\gamma}_2 \circ \psi = \gamma + O(\delta^3). \qquad (10) $$

Both (9) and (10) are sharp (proved analytically). Th. 4 underlines discontinuity of $\alpha(\lambda)$ at $\lambda = 1$ with the jump by 2 in respective convergence orders. Another unexpected fact comes from the proof of Th. 4. Namely, a natural candidate for a re-parameterization, i.e. a Lagrange quadratic $\psi_i : [t_i, t_{i+2}] \to [\hat{t}_i, \hat{t}_{i+2}]$ satisfying $\psi_i(t_{i+j}) = \hat{t}_{i+j}$ (for $j = 0, 1, 2$) can be a non-injective function [4].

The most recent result [5] shows that for $\varepsilon$-uniform samplings (4) (with $\varepsilon > 0$) the asymptotics established in Th. 4 improves from $\alpha(\lambda) = 1$ to $\alpha_{\varepsilon>0}(\lambda) = \min\{3, 1 + 2\varepsilon\}$, for each $\lambda \in [0, 1)$. Indeed the following holds [5]:

**Theorem 5.** Suppose $\gamma$ is a regular $C^4$ curve in $\mathbb{R}^n$ sampled according to the $\varepsilon$-uniformity condition (4) with $\varepsilon > 0$. Let $\hat{\gamma}_2 : [0, \hat{T}] = \sum_{i=0}^{m-1} \|q_{i+1} - q_i\|^\lambda \to \mathbb{R}^n$ be the piecewise-quadratic interpolant defined by $Q_m$ and (6) (with $\lambda \in [0, 1]$). Then there is a piecewise-$C^\infty$ re-parameterization $\psi : [0, T] \to [0, \hat{T}]$, such that:

$$ \hat{\gamma}_2 \circ \psi = \gamma + O(\delta^{\min\{3,1+2\varepsilon\}}). \qquad (11) $$

By Th. 4, formula (11) extends to $\varepsilon = 0$ (with $\lambda \in [0, 1)$) if extra condition (2) on 0-uniform sampling is imposed. The case $\lambda = 1$ by Th. 4 yields $\hat{\gamma}_2 \circ \psi = \gamma + O(\delta^3)$.

Again (11) is proved analytically to be sharp. Clearly, by Th. 5 an extra acceleration (11) in convergence rates for all $\lambda \in [0, 1]$ and (4) with $\varepsilon > 0$ occurs. The latter coincides with Th. 2 holding for $\lambda = 0$. The formula (11) is only dependent on $\varepsilon$, not on $\lambda$. It should be pointed out that by [5], for each $\varepsilon > 0$ the quadratic $\psi_i$ defines a genuine re-parameterization of $[t_i, t_{i+2}]$ into $[\hat{t}_i, \hat{t}_{i+2}]$.

## 2.4 Aim of this Research

In this paper we verify experimentally the sharpness of asymptotics for trajectory estimation claimed by Th. 4 and Th. 5. By sharpness we understand the
existence of at least one curve $\gamma \in C^r([0, T])$ (with $r$ set accordingly) sampled with some admissible samplings $\{t_i\}_{i=0}^m \in V_G^m$ for which the asymptotic estimates in question are exactly matched. The tests conducted herein are confined merely to the planar and spatial curves. It should, however be emphasized that all quoted herein Theorems 1-5 admit regular curves in $\mathbb{R}^n$. Some motivation standing behind the applications of interpolating reduced data is also here presented. More examples of real reduced $n$-dimensional data $Q_m$ which can be fitted with piecewise-quadratics $\hat{\gamma}_2$ or any other interpolation schemes based on exponential parameterization (6) can be found e.g. in [1].

# 3 Experiments

All tests presented in this paper are performed in *Mathematica 9.0* [14] on a 2.4GHZ Intel Core 2 Duo computer with 8GB RAM. Note that since $T = \sum_{i=1}^m (t_{i+1} - t_i) \le m\delta$ the following holds $m^{-\alpha} = O(\delta^\alpha)$, for $\alpha > 0$. Hence, the verification of any asymptotics expressed in terms of $O(\delta^\alpha)$ can be performed by examining the claims of Th. 4 or Th. 5 in terms of $O(1/m^\alpha)$ asymptotics.

Note that for a parametric regular curve $\gamma : [0, T] \to \mathbb{R}^n$, $\lambda \in [0, 1]$ and $m$ varying between $m_{min} \le m \le m_{max}$ the $i$-th component of the error for $\gamma$ estimation is defined here as follows:

$$E_m^i = \sup_{t \in [t_i, t_{i+2}]} \|(\hat{\gamma}_{2,i} \circ \psi_i)(t) - \gamma(t)\| = \max_{t \in [t_i, t_{i+2}]} \|(\hat{\gamma}_{2,i} \circ \psi_i)(t) - \gamma(t)\|,$$

as $\tilde{E}_m^i(t) = \|(\hat{\gamma}_{2,i} \circ \psi_i)(t) - \gamma(t)\| \ge 0$ is continuous over each compact subinterval $[t_i, t_{i+2}] \subset [0, T]$. The maximal value $E_m$ of $\tilde{E}_m(t)$ (the track-sum of $\tilde{E}_m^i(t)$), for each $m = 2k$ (here $k = 1, 2, 3, \dots, m/2$) is found by using *Mathematica* optimization built-in functions: *Maximize* or *FindMinimum* (the latter applied to $-\tilde{E}_m(t)$). From the set of *absolute errors* $\{E_m\}_{m=m_{min}}^{m=m_{max}}$, the numerical estimate $\bar{\alpha}(\lambda)$ of genuine order $\alpha(\lambda)$ is subsequently computed by using a *linear regression* applied to the pair of points $(\log(m), -\log(E_m))$ (see also [6]). Since piecewisely $\deg(\hat{\gamma}_2) = 2$ the number of interpolation points $\{q_i\}_{i=0}^m$ is odd i.e. $m = 2k$ as in-dexing runs over $0 \le i \le m$. The *Mathematica* built-in functions *LinearModelFit* renders the coefficient $\bar{\alpha}(\lambda)$ from the computed regression line $y(x) = \bar{\alpha}(\lambda)x + b$ based on pairs of points $\{(\log(m), -\log(E_m))\}_{m=m_{min}}^{m=m_{max}}$. Finally, recall that as justified in Th. 5 any $\varepsilon$-uniform sampling with $\varepsilon > 0$ gives asymptotically $\psi_i$ as re-parameterization of $[t_i, t_{i+2}]$ into $[\hat{t}_i, \hat{t}_{i+2}]$. Once $\varepsilon = 0$, one may apply a simple computational test (for $m = m_{max}$) by verifying whether either $\psi_i^{(1)}(t_i) \ge 0$ and $\psi_i^{(1)}(t_{i+2}) > 0$ or $\psi_i^{(1)}(t_i) > 0$ and $\psi_i^{(1)}(t_{i+2}) \ge 0$ hold over each subinterval $[t_i, t_{i+2}]$. The latter combined with the linearity of $\psi_i^{(1)}$ guarantees that $\psi_i$ is a re-parameterization. More discussion on the issue of enforcing $\psi_i$ to be a re-parameterization can be found in [5].

## 3.1 Fitting Reduced Data for Planar Curves

The testing commences with the simplest possible curve, i.e. a straight line.
Example 3. Consider a regular straight line: $\gamma_l(t) = (t/\sqrt{5}, 2t/\sqrt{5}) \subset \mathbb{R}^2$ for $t \in [0, 1]$, sampled with $\delta_1 = i/m$ according to $\varepsilon$-uniform sampling (4) (with $\varepsilon > 0$):

$$t_{i+1} - t_i = \delta_1(1 + \delta_1^\varepsilon) \quad \text{and} \quad t_{i+2} - t_i = \delta_1(1 - \delta_1^\varepsilon), \qquad (12)$$

where $t_0 = 0$ and $t_m = 1$. The plot of $\gamma_l$ sampled by (12), with $\varepsilon = 0.5$ and $m = 12$ is shown in Figure 3. Recalling (1), note that here $\delta = \delta_1(1 + \delta_1^\varepsilon)$. As

<figure><img src="image_4.png" /><figcaption>Fig. 3. The plot of the line $\gamma_l$ sampled as in (12), for $m = 12$ and $\varepsilon = 0.5$</figcaption></figure>

$\varepsilon > 0$, the quadratic $\psi_i$ is a re-parameterization [5]. The linear regression applied to $m_{min} = 100 \le m \le m_{max} = 120$ yields the estimates for $\bar{\alpha}_\varepsilon(\lambda) \approx \alpha_\varepsilon(\lambda) = \min\{3, 1+2\varepsilon\}$ which are presented in Table 1. An inspection of Table 1 confirms the sharpness or nearly sharpness of Th. 5. $\square$

<table><caption>Table 1. Computed $\bar{\alpha}_\varepsilon(\lambda) \approx \alpha_\varepsilon(\lambda) = 1 + 2\varepsilon$ for $\gamma_l$ and sampling (12) interpolated by $\hat{\gamma}_2$ with some discrete values $\lambda \in [0, 1)$ and $\varepsilon \in (0, 1]$</caption><thead><tr><th>λ</th><th>ε = 0.1</th><th>ε = 0.33</th><th>ε = 0.5</th><th>ε = 0.7</th><th>ε = 0.9</th><th>ε = 1</th></tr></thead><tbody><tr><th>α<sub>ε</sub>(λ)</th><td>1.20</td><td>1.66</td><td>2.00</td><td>2.40</td><td>2.80</td><td>3.00</td></tr><tr><th>0.00</th><td>1.47</td><td>1.80</td><td>2.10</td><td>2.46</td><td>2.85</td><td>3.04</td></tr><tr><th>0.10</th><td>1.45</td><td>1.80</td><td>2.10</td><td>2.46</td><td>2.85</td><td>3.04</td></tr><tr><th>0.33</th><td>1.42</td><td>1.80</td><td>2.10</td><td>2.46</td><td>2.85</td><td>3.04</td></tr><tr><th>0.50</th><td>1.39</td><td>1.80</td><td>2.10</td><td>2.46</td><td>2.85</td><td>3.04</td></tr><tr><th>0.70</th><td>1.37</td><td>1.79</td><td>2.10</td><td>2.47</td><td>2.85</td><td>3.04</td></tr><tr><th>0.90</th><td>1.36</td><td>1.79</td><td>2.10</td><td>2.47</td><td>2.85</td><td>3.04</td></tr></tbody></table>

We pass now to the next example involving a spiral curve in $\mathbb{R}^2$.

Example 4. Consider now the following regular spiral curve $\gamma_{sp1}: [0, 1] \to \mathbb{R}^2$: $\gamma_{sp1}(t) = ((t + 0.2)\cos(\pi(1 - t)), (t + 0.2)\sin(\pi(1 - t)))$, sampled according to
the following $\varepsilon$-uniform sampling (4):

$$t_i = \frac{i}{m} + \frac{(-1)^{i+1}}{m^{1+\varepsilon}}, \qquad (13)$$

with $t_0 = 0$ and $t_m = 1$. Figure 4 shows $\gamma_{sp1}$ (a dashed line) and $\hat{\gamma}_2$ (a continuous line) sampled by (13) with $\varepsilon = 0.7$, $m = 12$ and $\lambda \in \{0, 1\}$. The difference between both $\hat{\gamma}_2$ and $\gamma_{sp1}$ on sparse data $Q_{12}$ is minor as they both overlap.

<figure><img src="image_5.png" /><figcaption>**Fig. 4.** The plot of the spiral $\gamma_{sp1}$ sampled as in (13) (a dashed line) and interpolant $\hat{\gamma}_2$ (a continuous line), for $m = 12$ and $\varepsilon = 0.7$ with either a) $\lambda = 0$ or b) $\lambda = 1$</figcaption></figure>

The Th. 5, for $\varepsilon > 0$ yields $\psi_i : [t_i, t_{i+2}] \to [\hat{t}_i, \hat{t}_{i+2}]$ as a re-parameterization. The case of $\varepsilon = 0$ renders (13) as more-or-less uniform (3) with $K_1 = 1/3$ and $K_2 = 5/3$. Sufficient conditions for $\psi_i$ to be a re-parameterization are formulated in [5]. The latter enables to verify the validity of Th. 4 also for $\varepsilon = 0$. The linear regression applied to $m = 100 \le m \le m_{max} = 120$ renders computed $\bar{\alpha}_{\varepsilon}(\lambda) \approx \alpha_{\varepsilon}(\lambda) = \min\{3, 1 + 2\varepsilon\}$ ($\varepsilon \ge 0$), which are listed in Table 2. Visibly, the sharpness or nearly sharpness of Th. 4 and Th. 5 is confirmed in Table 2. $\square$

<table><caption>**Table 2.** Estimated $\bar{\alpha}_{\varepsilon}(\lambda) \approx \alpha_{\varepsilon}(\lambda) = 1 + 2\varepsilon$ for $\gamma_{sp1}$ and sampling (13) interpolated by $\hat{\gamma}_2$ with $\lambda \in [0, 1]$ and $\varepsilon \in [0, 1]$</caption><thead><tr><th>λ</th><th>ε = 0.0</th><th>ε = 0.1</th><th>ε = 0.33</th><th>ε = 0.5</th><th>ε = 0.7</th><th>ε = 0.9</th><th>ε = 1.0</th></tr></thead><tbody><tr><th>α<sub>ε</sub>(λ)</th><td>1.000</td><td>1.200</td><td>1.660</td><td>2.000</td><td>2.400</td><td>2.800</td><td>3.000</td></tr><tr><th>0.00</th><td>0.981</td><td>1.286</td><td>1.716</td><td>2.023</td><td>2.419</td><td>2.96</td><td>3.004</td></tr><tr><th>0.10</th><td>0.983</td><td>1.282</td><td>1.718</td><td>2.029</td><td>2.435</td><td>2.97</td><td>3.005</td></tr><tr><th>0.33</th><td>0.985</td><td>1.277</td><td>1.726</td><td>2.051</td><td>2.496</td><td>2.93</td><td>3.016</td></tr><tr><th>0.50</th><td>0.988</td><td>1.276</td><td>1.740</td><td>2.081</td><td>2.584</td><td>3.01</td><td>3.017</td></tr><tr><th>0.70</th><td>0.995</td><td>1.283</td><td>1.778</td><td>2.178</td><td>2.782</td><td>2.94</td><td>3.030</td></tr><tr><th>0.90</th><td>1.036</td><td>1.354</td><td>2.051</td><td>2.271</td><td>3.005</td><td>2.89</td><td>3.031</td></tr><tr><th>α<sub>ε</sub>(1)</th><td>3.000</td><td>3.000</td><td>3.000</td><td>3.000</td><td>3.000</td><td>3.000</td><td>3.000</td></tr><tr><th>1.00</th><td>3.057</td><td>2.990</td><td>2.996</td><td>3.007</td><td>3.016</td><td>2.88</td><td>3.031</td></tr></tbody></table>

The last example involving curve in $\mathbb{R}^2$ refers to another spiral.

*Example 5.* Let a planar regular convex spiral $\gamma_{sp} : [0, 5\pi] \to \mathbb{R}^2$: $\gamma_{sp}(t) = ((6\pi - t)\cos(t), (6\pi - t)\sin(t))$ be sampled according to (13) (rescaled by factor
$5\pi$) with $t_0 = 0$ and $t_m = 5\pi$. Figure 5 illustrates $\gamma_{sp}$ (a dashed line) and $\hat{\gamma}_2$ (a continuous line) coupled with (13), for $\varepsilon = 0.33$, $m = 22$ and $\lambda \in \{0, 1\}$. The difference between $\gamma_{sp}$ and $\hat{\gamma}_2$ on reduced data $Q_{22}$ is transparent (at least for $\lambda = 0$). As explained previously, the sampling (13) enforces $\psi_i$ to be a re-

<figure><img src="image_6.png" /><figcaption>**Fig. 5.** The plot of the spiral $\gamma_{sp}$ sampled as in (13) (a dashed line) and interpolant $\hat{\gamma}_2$ (a continuous line), for $m = 22$ and $\varepsilon = 0.33$ with either a) $\lambda = 0$ or b) $\lambda = 1$</figcaption></figure>

parameterization for $\varepsilon > 0$. For $\varepsilon = 0$ one needs to resort to the sufficient conditions for $\psi_i^{(1)} > 0$ to hold (see [5]). In order to estimate the relevant coefficients $\alpha_{\varepsilon}(\lambda)$ a linear regression is again applied to $100 = m_{min} \le m \le m_{max} = 120$. The numerical results are listed in Table 3. Some computed $\alpha_{\varepsilon}(\lambda)$ from Table 3 exceed convergence orders claimed by Th. 5. However, the first column in Table 3 shows the sharpness of Th. 4. $\square$

<table><caption>**Table 3.** Estimated $\bar{\alpha}_{\varepsilon}(\lambda) \approx \alpha_{\varepsilon}(\lambda) = 1 + 2\varepsilon$ for $\gamma_{sp}$ and sampling (13) interpolated by $\hat{\gamma}_2$ with $\lambda \in [0, 1]$ and $\varepsilon \in [0, 1]$</caption><thead><tr><th>λ</th><th>ε = 0.0</th><th>ε = 0.1</th><th>ε = 0.33</th><th>ε = 0.5</th><th>ε = 0.7</th><th>ε = 0.9</th><th>ε = 1.0</th></tr></thead><tbody><tr><td>α<sub>ε</sub>(λ)</td><td>1.000</td><td>1.200</td><td>1.660</td><td>2.000</td><td>2.400</td><td>2.800</td><td>3.000</td></tr><tr><td>0.00</td><td>0.990</td><td>1.303</td><td>1.799</td><td>2.223</td><td>2.851</td><td>2.986</td><td>3.008</td></tr><tr><td>0.10</td><td>0.990</td><td>1.299</td><td>1.812</td><td>2.342</td><td>2.911</td><td>2.986</td><td>3.007</td></tr><tr><td>0.33</td><td>0.991</td><td>1.296</td><td>1.872</td><td>2.252</td><td>2.966</td><td>3.011</td><td>3.024</td></tr><tr><td>0.50</td><td>0.995</td><td>1.303</td><td>1.989</td><td>2.711</td><td>2.995</td><td>3.020</td><td>3.022</td></tr><tr><td>0.70</td><td>1.013</td><td>1.355</td><td>2.377</td><td>2.930</td><td>3.020</td><td>3.024</td><td>3.023</td></tr><tr><td>0.90</td><td>1.291</td><td>2.092</td><td>2.986</td><td>2.043</td><td>3.033</td><td>3.033</td><td>3.024</td></tr><tr><td>α<sub>ε</sub>(1)</td><td>3.000</td><td>3.000</td><td>3.000</td><td>3.000</td><td>3.000</td><td>3.000</td><td>3.000</td></tr><tr><td>1.00</td><td>3.000</td><td>2.866</td><td>2.901</td><td>2.938</td><td>2.976</td><td>2.995</td><td>3.000</td></tr></tbody></table>
## 3.2 Fitting Reduced Data for Spatial Curves

The next example deals with the reduced data $Q_m$ obtained by sampling the regular spatial curve in $\mathbb{R}^3$.

*Example 6.* We verify now the sharpness of Th. 4 and Th. 5 for a quadratic elliptical helix: $\gamma_h(t) = (2\cos(t), \sin(t), t^2)$, with $t \in [0, 2\pi]$ and sampled $\varepsilon$-uniformly (4) (here $\phi = id$) according to:

$$ t_i = \begin{cases} \frac{2\pi i}{m} & \text{if } i \text{ even,} \\ \frac{2\pi i}{m} + \frac{2\pi}{2m^{1+\varepsilon}} & \text{if } i = 4k + 1, \\ \frac{2\pi i}{m} - \frac{2\pi}{2m^{1+\varepsilon}} & \text{if } i = 4k + 3. \end{cases} \qquad (14) $$

The last knot $t_m$ is set to $2\pi$. Figure 6 illustrates the curve $\gamma_h$ sampled in accordance with (14) for $\varepsilon = 0.5$ and $m = 22$. For $\varepsilon > 0$, by Th. 5 each quadratic

<figure><img src="image_7.png" /><figcaption>Fig. 6. The plot of the helix $\gamma_h$ sampled as in (14), for $m = 22$ and $\varepsilon = 0.5$</figcaption></figure>

$\psi_i : [t_i, t_{i+2}] \to [\hat{t}_i, \hat{t}_{i+2}]$ is a re-parameterization. Note that $\varepsilon = 0$ in (14) yields also more-or-less uniform sampling (3) with $K_1 = \pi$ and $K_2 = 3\pi$. The latter is stipulated by Th. 4. The sufficient conditions for $\{t_i\}_{i=0}^m$ to yield $\psi_i$ as re-parameterization are specified in [5]. The linear regression is used here for $m_{min} = 100 \le m \le m_{max} = 120$. The corresponding computed estimates $\bar{\alpha}_\varepsilon(\lambda) \approx \alpha_\varepsilon(\lambda) = \min\{3, 1+2\varepsilon\}$ are shown in Table 4. The experiments are consistent with the asymptotics from Th. 5. Thus the sharpness of (11) is also generically herein confirmed. Note also that the estimated convergence orders $\bar{\alpha}_\varepsilon=0(\lambda)$ are substantially faster than those claimed by Th. 4. $\square$

The linear regression is used to estimate the asymptotic convergence rates $\alpha_\varepsilon(\lambda)$ for sufficiently large $m$. The estimates may sometimes be misleading when $m$ is not sufficiently large.
<table><caption>**Table 4.** Estimated $\bar{\alpha}_{\varepsilon}(\lambda) \approx \alpha_{\varepsilon}(\lambda) = 1 + 2\varepsilon$ for $\gamma_h$ and sampling (14) interpolated by $\hat{\gamma}_2$ with $\lambda \in [0, 1]$ and $\varepsilon \in [0, 1]$</caption><thead><tr><th>λ</th><th>ε = 0.0</th><th>ε = 0.1</th><th>ε = 0.33</th><th>ε = 0.5</th><th>ε = 0.7</th><th>ε = 0.9</th><th>ε = 1.0</th></tr></thead><tbody><tr><th>α<sub>ε</sub>(λ)</th><td>1.00</td><td>1.20</td><td>1.66</td><td>2.00</td><td>2.40</td><td>2.80</td><td>3.00</td></tr><tr><th>0.10</th><td>2.99</td><td>1.26</td><td>1.74</td><td>2.09</td><td>2.54</td><td>2.97</td><td>3.01</td></tr><tr><th>0.33</th><td>2.85</td><td>1.24</td><td>1.72</td><td>2.07</td><td>2.93</td><td>2.93</td><td>2.95</td></tr><tr><th>0.50</th><td>3.24</td><td>1.23</td><td>1.70</td><td>2.06</td><td>3.01</td><td>3.01</td><td>3.04</td></tr><tr><th>0.70</th><td>3.21</td><td>1.20</td><td>1.64</td><td>2.94</td><td>2.94</td><td>2.94</td><td>3.19</td></tr><tr><th>0.90</th><td>3.21</td><td>1.15</td><td>2.89</td><td>2.89</td><td>2.89</td><td>2.89</td><td>3.22</td></tr><tr><th>α<sub>ε</sub>(1)</th><td>3.00</td><td>3.00</td><td>3.00</td><td>3.00</td><td>3.00</td><td>3.00</td><td>3.00</td></tr><tr><th>1.00</th><td>3.21</td><td>2.89</td><td>2.91</td><td>2.92</td><td>2.93</td><td>2.88</td><td>3.21</td></tr></tbody></table>

# 4 Conclusions

In this paper we discussed the problem of trajectory estimation via piecewise-quadratic interpolation based on reduced data $Q_m$. In particular, the exponential parameterization (6) which depends on parameter $\lambda \in [0, 1]$ is herein examined. The latter is commonly used in computer graphics for curve modeling - see e.g. [9], [10], [11] or [12]. Special cases of (6) with $\lambda = 0$ (see e.g. [2]) or $\lambda = 1$ (see e.g. [3] or [6]) have been studied in the literature. Recent results from [4] and [5] with full mathematical proofs analyze the asymptotics in question for the remaining cases of $\lambda \in (0, 1)$.

Th. 4 claims that the if $\{t_i\}_{i=0}^m$ is more-or-less uniform (2) there is no acceleration in trajectory estimation once $\lambda$ varies within the interval $[0, 1)$. The convergence orders are constant, i.e. $\alpha(\lambda) = 1$ for all $\lambda \in [0, 1)$. In addition, there is a discontinuity at $\lambda = 1$ with a jump to $\alpha(1) = 3$ (valid for the general class of admissible samplings (1)).

It is known [2] that further acceleration can be achieved for $\varepsilon$-uniform samplings (4) (for $\varepsilon > 0$) and $\lambda = 0$ by reaching $\alpha_{\varepsilon}(0) = \min\{3, 1 + 2\varepsilon\}$. The most recent result by [5] extends the latter to arbitrary $\lambda \in [0, 1)$ and $\varepsilon \ge 0$. The case $\varepsilon = 0$ is also admitted provided the curve $\gamma$ is sampled according to (2). As established in Th. 5 the acceleration amounting to $\alpha_{\varepsilon}(\lambda) = \min\{3, 1 + 2\varepsilon\}$ is merely dependent on $\varepsilon$ (not on $\lambda \in [0, 1]$). Visibly the discontinuity in $\alpha_{\varepsilon}(\lambda)$ at $\lambda = 1$ is removed for $\varepsilon \ge 1$. It should also be emphasized that the proof of Th. 5 shows that the Lagrange quadratic $\psi_i : [t_i, t_{i+2}] \to [\hat{t}_i, \hat{t}_{i+2}]$ satisfying $\psi_i(t_{i+j}) = \hat{t}_{i+j}$ (for $j = 0, 1$) forms a genuine re-parameterization in case of $\varepsilon$-uniform samplings (with $\varepsilon > 0$). The above theorem also formulates sufficient conditions for admissible samplings (1) (including the case $\varepsilon = 0$) guaranteeing $\psi_i$ to render a re-parameterization.

We experimentally verify here the sharpness of the asymptotics established in [4] and [5]. Various numerical tests conducted in this paper confirm, at least for the examined curves in $\mathbb{R}^2$ or $\mathbb{R}^3$ and samplings (12), (13) or (14) the sharpness of asymptotics claimed by both Th. 4 (see (9) and (10)) and Th. 5 (see (11)). Though all discussed herein results refer to the dense reduced data $Q_m$, high
convergence orders yield in practice satisfactory approximation on sparse data. Thus as $\alpha(\lambda) = 3$ for either $\lambda = 1$ or $\varepsilon \ge 1$ and $\lambda \in [0, 1]$, we should expect for sufficiently sparse $Q_m$ (but not too dense) a good performance in $\gamma \approx \hat{\gamma}_2$.

A possible extension of this work is to study other smooth interpolation schemes [9] combined with reduced data $Q_m$ and exponential parameterization (6) - see [11]. Certain clues may be given in [15], where complete $C^2$ splines are dealt with for $\lambda = 1$, to obtain the fourth orders of convergence in length estimation. The analysis of $C^1$ interpolation for reduced data with cumulative chords (i.e. again with $\lambda = 1$) can additionally be found in [6] or [16]. More discussion on applications (including real data examples - see [1]) and theory of non-parametric interpolation can be found e.g. in [6], [10], [11] or [12].

## References

1. Janik, M., Kozera, R., Koziol, P.: Reduced data for curve modeling - applications in graphics, computer vision and physics. Advances in Science and Technology, 7(18), pp. 28-35 (2013)

2. Noakes, L., Kozera, R., Klette, R.: Length estimation for curves with $\varepsilon$-uniform samplings. In Digital Image Geometry, Eds. G. Bertrand, A. Imiya, and R. Klette, LNCS Springer-Verlag, Berlin Heidelberg 2243, pp. 339-351 (2001)

3. Noakes, L., Kozera, R.: Cumulative chords piecewise-quadratics and piecewise-cubics. In Geometric Properties of Incomplete Data, Eds. R. Klette, R. Kozera, L. Noakes and J. Weickert, Computational Imaging and Vision, Kluver Academic Publishers, The Netherlands 31, pp. 59-75 (2006)

4. Kozera, R., Noakes, L.: Piecewise-quadratics and exponential parameterization for reduced data. Applied Mathematics and Computation. In press

5. Kozera, R., Noakes, L.: Exponential parameterization and $\varepsilon$-uniformly sampled reduced data. Submitted

6. Kozera, R.: Curve modeling via interpolation based on multidimensional reduced data. Studia Informatica, 25(4B-61), pp. 1-140 (2004)

7. Noakes, L., Kozera, R.: More-or-less uniform samplings and lengths of curves. Quarterly of Applied Mathematics 61(3), pp. 475-484 (2003)

8. Ralston, A.: A First Course in Numerical Analysis. Mc-Graw Hill (1965)

9. de Boor, C.: A Practical Guide to Splines. Springer-Verlag, Berlin Heidelberg New York (2001)

10. Kocić, Lj.M., Simoncelli, A.C., Della Vecchia, B.: Blending parameterization of polynomial and spline interpolants, Facta Universitatis (NIŠ), Series Mathematics and Informatics, 5 pp. 95-107 (1990)

11. Kvasov, B.I.: Methods of Shape-Preserving Spline Approximation. World Scientific Publishing Company, Singapore (2000)

12. Piegl, L., Tiller, W.: The NURBS Book. Springer-Verlag, Berlin Heidelberg New York (1997)

13. Lee, E.T.Y.: Choosing nodes in parametric curve interpolation. Computer-Aided Design, 21(6), pp. 363-370 (1987)

14. Wolfram Mathematica 9, Documentation Center, URL link: reference.wolfram.com/mathematica/guide/Mathematica.html

15. Floater, M.S.: Chordal cubic spline interpolation is fourth order accurate. IMA Journal of Numerical Analysis, 26, pp. 25-33 (2006)

16. Kozera, R., Noakes, L.: $C^1$ interpolation with cumulative chord cubics. Fundamenta Informaticae 61(3-4), pp. 285-301 (2004)