数理解析研究所講究録
1111 巻 1999 年 157-164

157

A Note on
Invariant Three-Point Curvature Approximations
Alexander G. Belyaev
The University of Aizu
Aizu-Wakamatsu City, Fukushima 965-8580, Japan
belyaevhu-aizu. . jp$\mathrm{a}\mathrm{c}$Abstract
In this paper we consider Euclidean invariant three-point finite difference approximations of the curvature of a plane curve and study asymptotic properties of suchapproximations. The paper reveals interesting relations between certain three-point
curvature approximations and mechanical and wooden splines.

Discrete approximations of the curvature
Consider a smooth function $f(x)$ . A well-known three-point finite difference approximation of the second derivative of the function and asymptotic expansion of the approximation have the following form$f”(x) \approx\frac{2f(x-a)}{a(a+b)}-\frac{2f(x)}{ab}+\frac{2f(x+b)}{b(a+b)}=$a$=f^{N}(x)+ \frac{b-}{3}$ $f”’(x)+ \frac{a^{2}-ab+b^{2}}{12}f^{m/}(x)+\ldots$(1)$\ldots+\frac{2(b^{n-1}-(-a)^{n-1})}{(a+b)n!}f^{(n)}(x)+O(a, b)^{n+1}$The goal of this paper is to analyze asymptotic properties of various three-point finite difference approximations of the curvature. Since the curvature is a second-orderdifferential function, it turns out that asymptotic expansions of the three-point curvatureapproximations unaffected by the rigid motions are similar to (1).

Let us consider a smooth curveparameterized by arc length . Let $A,$ $O,$bethree successive points on the curve. The distances $a=|OA|,$ $b=|OB|$ are assumed to besmall and, therefore, so is $c=|AB|$ . Below we introduce discrete analogs of the curvature
at the central point based on three points approximations.
We study the approximations expanding them into Taylor series in and .
$\mathrm{r}(s)$

$B$

$s$

$O$

$a$

$b$

158

Let
$\mathrm{t}=\mathrm{r}’$be the Frenet basis at$O$,$\mathrm{n}=\mathrm{t}^{\perp}$. According to the Frenet formulas$\mathrm{t}’=k\mathrm{n}$Approximation via derivatives.
as follows,$\mathrm{n}’=-k\mathrm{t}$.

The first derivative of$\mathrm{r}(s)$at$O$

can be approximated$\mathrm{r}’=\mathrm{t}\approx\frac{\mathrm{r}(B)-\mathrm{r}(O)}{b}+\frac{\mathrm{r}(O)-\mathrm{r}(A)}{a}-\frac{\mathrm{r}(B)-\mathrm{r}(A)}{a+b}$

Expanding the right-hand side of of this formula into Taylor series expansion in
and using the Frenet formulas we obtain

and

$a$

$b$

$\mathrm{t}\approx\frac{\mathrm{r}(B)-\mathrm{r}(O)}{b}+\frac{\mathrm{r}(O)-\mathrm{r}(A)}{a}-\frac{\mathrm{r}(B)-\mathrm{r}(A)}{a+b}=$$=(1- \frac{ab}{8}k^{2}-\frac{ab(b-a)}{12}kk’+O(a, b)^{3})\mathrm{t}+(\frac{ab}{6}k’+\frac{ab(b-a)}{24}k’’+O(a, b)^{3})\mathrm{n}$.

(2)

See Appendix A of this paper for details.
at can be approximated as follows
The second derivative of$\mathrm{r}(s)$

$O$

(3)

$\mathrm{r}’’=\mathrm{t}’=k\mathrm{n}\approx\frac{2\mathrm{r}(A)}{a(a+b)}-\frac{2\mathrm{r}(O)}{ab}+\frac{2\mathrm{r}(B)}{(a+b)b}$

Expanding the right-hand side of (3) into Taylor series with respect tothe Frenet formulas we arrive at$a$and$b$

and using$k \mathrm{n}\approx\frac{2}{a+b}[\frac{\mathrm{r}(B)-\mathrm{r}(O)}{b}+\frac{\mathrm{r}(A)-\mathrm{r}(O)}{a}]=$$=( \frac{a-b}{4}k^{2}-\frac{a^{2}-ab+b^{2}}{6}kk’+O(a, b)^{3})\mathrm{t}+$$+$(a$k+ \frac{b-}{3}$ $k’+ \frac{a^{2}-ab+b^{2}}{12}k’’+O(a, b)^{3}$See Appendix A for details. Sinceby$k=k\mathrm{n}\cdot \mathrm{t}^{\perp}$$\mathrm{n}$

(4)
$O$

.

$[ \frac{\mathrm{r}(B)-\mathrm{r}(O)}{b}+\frac{\mathrm{r}(O)-\mathrm{r}(A)}{a}-\frac{\mathrm{r}(B)-\mathrm{r}(A)}{a+b}]^{\perp}$

Now (4), (2), and (5) yielda.

, we can approximate the curvature at$k \approx\overline{k}=\frac{2}{a+b}[\frac{\mathrm{r}(B)-\mathrm{r}(O)}{b}+\frac{\mathrm{r}(A)-\mathrm{r}(O)}{a}]$.

)$\overline{k}=k+\frac{b-}{3}$ $k’+[ \frac{2(b^{3}+a^{3})}{4!(a+b)}k’’-\frac{ab}{8}k^{3}]+O(a, b)^{3}$.

(5)

159

It follows from (1) thata$\overline{k}=k+\frac{b-}{3}$ $k’+[ \frac{2(b^{3}+a^{3})}{4!(a+b)}k’’-\frac{ab}{8}k^{3}]+\ldots+[\frac{2(b^{n+1}-(-a)^{n+1})}{(a+b)(n+2)!}k^{(n)}+\ldots]+O(a, b)^{n+1}$(6)

Circle approximation. Let us use the circle passing through the points $A,$ $O,$asan approximation to the osculating circle to the curve at , see Fig. 1. Then the inverse
$B$

$O$

Figure 1:

value of the radius can serve as an approximation of the curvature at . This curvatureapproximation was considered in [5, 3, 2]. Let denote the area of the triangle $AOB$ .
The discrete curvature at is given by
$O$

$S$

$O$

$\overline{k}=\frac{4S}{abc}$.

(7)

Using Taylor series manipulations it can be shown thata$\tilde{k}=k+\frac{b-}{3}$ $k’+ \frac{2(b^{3}+a^{3})}{4!(a+b)}k’’+[\frac{2(b^{4}-a^{4})}{5!(a+b)}k^{m}+\frac{3b^{3}-2ab^{2}-2a^{2}b-3a^{3}}{120}k^{2}k^{l}]+$$+[ \frac{2(b^{5}+a^{5})}{6!(a+b)}k^{\prime\prime\prime\prime}+\frac{]6a^{4}+16b^{4}-28a^{2}b^{2}-a^{3}b-ab^{3}}{1440}k^{J/}k^{2}+$$+ \frac{8a^{4}+8b^{4}-7a^{2}b^{2}+2a^{3}b+2ab^{3}}{360}k^{J2}k]+O(a, b)^{5}$.

(8)This expansion without the fourth order terms was obtained in(see also[3] for details). Our derivation of the expansion is similar to that proposed in $[2, 3]$ . It isoutlined in Appendix A of this paper.
$[2][\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{m}2.4]$

160

Angle approximation. Another idea to define the curvature of a polygonal line isbased on the definition of the curvature as the rate of change of the angle between thetangent and the positive direction of the -axis when we proceed along the curve. Let
denote the turn angle at (see Fig. 1). Following $[1, 6]$ let us define the discrete curvature
at as(9).
$x$$\varphi$

$O$

$O$

$\hat{k}=\frac{2\varphi}{a+b}$

Applying Taylor series expansions we get$\hat{k}=k+\frac{b-a}{3}k’+\frac{2(b^{3}+a^{3})}{4!(a+b)}(k’’+\frac{k^{3}}{2})+\frac{2(b^{4}-a^{4})}{5!(a+b)}(k^{m}+4k^{2}k’)+$$+ \frac{2(b^{5}+a^{5})}{6!(a+b)}(k^{\prime\prime\prime\prime}+\frac{31}{4}k’’k^{2}+13k^{;2}k+\frac{27}{16}k^{5})+O(a, b)^{5}$.

(10)The derivation is outlined in Appendix A.
General three-point curvature approximation. Note a similarity between (6), (8),(10). Let us consider a symmetric three-point curvature approximation and denote its
Taylor series expansion with respect to and by $(*)$ . Like (6), (8), (10) expansion $(*)$
must be scale invariant. It is clear that we can estimate the curvature using three curve
points but cannot estimate the curvature derivatives. Thus $(*)$ must start from
$b$

$a$

a

$k+ \frac{b-}{3}$ $k’+\ldots$

Similarly, if we set $a=b$ then $(*)$ starts from$k+ \frac{a^{2}}{12}(k’’+Ck^{3})+\ldots$,

where is a constant.
We can conclude that approximating a smooth plane curve by a polygonal line withequal links is preferable for accurate curvature estimation.
The nth term in $(*)$ has the form
$C$

$P_{n}(a, b)k^{(n)}+Q_{n}(a, b)k^{(n-1)}k+\ldots+R_{n}(a, b)k^{n+1}$, $R_{n}(a, b)$ are homogeneous polynomials of degree in andwhere $P_{n}(a, b),$ $Q_{n}(a, b),$. They are symmetric with respect to and if is even and antisymmetric if is odd.
Since changing the orientation alters the signs in $(*)$ , then $Q_{n}(a, b)\equiv 0$ .
The curvature is a second-order differential function which is unaffected by the rigidmotions. Therefore, any numerical approximation of the curvature requires six numbers,
for example, six coordinates of three points. Similarly, to estimate the nth derivative of,, one needs $n+6$ numbers. Thus,
cannot be estimated fromthe curvature,$k^{(n-1)}(O)$$k^{lN}(O),$$k”(O),$. Therefore, two different three-point
and $k’(O),$$n$$\ldots$$b$$a$$\mathrm{r}(B)$$\ldots,$$a$$n$$n$$k^{(n)}$$k^{(n)}$$\mathrm{r}(O),$$b$$\mathrm{r}(A)$161
curvature approximations have the same coefficients $P_{n}(a, b)$ in their expansions in. From (6) it follows that

$a$

and

$b$(11)$P_{n}(a, b)= \frac{2(b^{n+1}-(-a)^{n+1})}{(n+2)!(a+b)}$

and we have proved the following theorem.

Theorem 1 Let $A,$ $O,$
be three successive points on a smooth curve, with $|AO|=a$and $|OB|=b$ . Consider a symmetric three-point curvature approximation unaffected by
the rigid motions. Then the following expansion is valid$B$

a$k+ \frac{b-}{3}$ $k’+[ \frac{2(b^{3}+a^{3})}{4!(a+b)}k’’+R_{2}(a, b)k^{3}]+\ldots+[\frac{2(b^{n+1}-(-a)^{n+1})}{(n+2)!(a+b)}k^{(n)}+\ldots]+O(a, b)^{n+1}$$\iota$where $R_{2}(a, b)$ is a homogeneous symmetric quadratic polynomial in

$a$

and .
$b$

Remark. Let
be the angle between the segment $OA$ and the tangent at
andbe the angle between the segment $oB$ and the tangent at . If
is the angle$\psi_{A}(a)$$O$$\psi_{B}(b)$$\mathit{0}$$\mathrm{b}\mathrm{e}\mathrm{t}\mathrm{w}\mathrm{e}\mathrm{e}\mathrm{n}AO\mathrm{a}\mathrm{n}\mathrm{d}OB,\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}\varphi(a, b)=\psi_{B}(b)-\psi_{B}(-a)$.

polynomials in$a$

and$b$$\varphi(a, b)$’$\varphi(a, b)=\psi_{A}(a)+\psi_{B}(b)\mathrm{a}\mathrm{n}\mathrm{d}\psi_{A}(a)=-\psi_{B}(-a).\mathrm{H}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{e}\mathrm{F}\mathrm{r}\mathrm{o}\mathrm{m}\mathrm{t}\mathrm{h}\mathrm{i}\mathrm{s}\mathrm{d}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{f}\mathrm{o}11\mathrm{o}\mathrm{w}\mathrm{s}\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}\mathrm{a}11\mathrm{h}\mathrm{o}\mathrm{m}\mathrm{o}\mathrm{g}\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{o}\mathrm{u}\mathrm{s}$occurring in the Taylor series expansion of (9) are given by (11).

Mechanical and wooden splines
There are interesting relations between curvature approximations (7) and (9) and themechanical and wooden splines which are important for CAGD purposes [4].
A mechanical spline called also an elastica curve minimizes the bending energy$\frac{1}{2}\int k^{2}ds$

where$k$is the curvature and$s$,

is arclength. Along the mechanical splines$k”+ \frac{k^{3}}{2}=0$.

A wooden spline called also a Cornu spiral, or Euler spiral, or clothoid is characterized
by the equation$k”=0$ ,that means the curvature varies linearly with respect to arclength along the spline.
The next theorem follows from (8) and (10).

Theorem 2 Consider an approximation of a smooth plane curve by a polygonal line withsmall equal-length links.

,

162

$\bullet$$\bullet$Let us define the discrete curvature at a vertex of the polygonal line as the reciprocalof the radius of the circle passing through the vertex and two its neighboring vertices.
Consider a polygonal approximation of a wooden spline. The first error term in theapproximation of the curve curvature by the discrete curvature is of fourth orderwith respect to the length of the link.
Let us define the discrete curvature at a vertex of the polygonal line as the ratio of theturn angle at the vertex and length of the link. Consider a polygonal approximationof a mechanical spline. The first error term in the approximation of the curve
curvature by the discrete curvature is of fourth order with respect to the length ofthe link.

This theorem indicates that the relations between the four-parametric families of mechanical and wooden splines and approximations (8) and (10) respectively are similar tothe relation between the four-parametric family of cubic polynomials and (1).

Acknowledgments
It is my pleasure to acknowledge fruitful discussions with I. A. Bogaevski. Thanks also toMaple for its help in performing formal computations presented in the paper.

References[1] A. M. Bruckstein, R. J. Holt, and A. N. Netravali. Discrete elastica. In Discrete Geometry
for Computer Imagery, Lecture Notes in Computer Science 1176, pages 59-72, Lyon, Fkance,
November 1996.
[2] E. Calabi, P. J. Olver, C. Shakiban, A. Tannenbaum, and S. Haker. Differential and numerically invariant signature curves applied to object recognition. Int. J. Computer Vision,
26:107-135, 1998.
[3] E. Calabi, P. J. Olver, and A. Tannenbaum. Affine geometry, curve flows, and invariant
numerical approximations. Adv. Math., $124(1):154-196$ , 1996.
[4] J. Hoschek and D. Lasser. Fundamentals of Computer Aided Geometric Design. A K Peters,Ltd., 1993.
[5] H. P. Moreton. Minimum Curvature Variation Curves, Networks, and Surfaces for Fair
Free-Form Shape Design. PhD thesis, University of California at Berkeley, 1992.
[6] M. Nitzberg, D. Mumford, and T. Shiota. Filtering, Segmentation and Depth, Lecture Notes
in Compuier Science, Vol. 662. Springer, 1993.

Appendix ALet$\mathrm{r}(s)$be a plane curve parameterized by arclength parameter s. Consider three points

on the curveA$=\mathrm{r}(s-\alpha)$,O$=\mathrm{r}(s)$,B$=\mathrm{r}(s+\beta)$

163

with distances $a=|OA|$ and $b=|OB|$ between them. Let
the Frenet frame at . Denote by the angle between
and$\mathrm{r}’=\mathrm{t}$$AOarrow$$\mathit{0}$andcompose. See Fig. 2.
$\mathrm{n}=\mathrm{t}^{\perp}$$oBarrow$$\varphi$

Figure 2:

According to the Frenet formulas$\mathrm{t}’=k\mathrm{n}$,$\mathrm{n}’=-k\mathrm{t}$we have$\mathrm{r}’=\mathrm{t}$,$\mathrm{r}’’=\mathrm{t}’=k\mathrm{n}$,$\mathrm{r}’’’=(k\mathrm{n})’=k’\mathrm{n}-k^{2}\mathrm{t}$,$\mathrm{r}^{\prime\prime\prime\prime}=(k’\mathrm{n}-k^{2}\mathrm{t})’=(k^{n}-k^{3})\mathrm{n}-3kk’\mathrm{t}$Expanding$\mathrm{r}(s+\beta)$

into the Taylor series with respect to,yields$\beta$$OB= \mathrm{r}(s+\beta)-\mathrm{r}(s)=\beta \mathrm{r}’+\frac{\beta^{2}}{2}\mathrm{r}’’+\frac{\beta^{3}}{6}\mathrm{r}’’’+\frac{\beta^{4}}{24}\mathrm{r}^{\prime\prime\prime\prime}+O(\beta^{5})arrow=$$= \mathrm{t}[\beta-\frac{\beta^{3}}{6}k^{2}-\frac{\beta^{4}}{8}kk’+O(\beta^{5})]+\mathrm{n}[\frac{\beta^{2}}{2}k+\frac{\beta^{3}}{6}k’+\frac{\beta^{4}}{24}(k’’-k^{3})+O(\beta^{5})]$Thus$b^{2}= \beta^{2}-\frac{\beta^{4}}{12}k^{2}-\frac{\beta^{5}}{12}kk’+O(\beta^{6})$Inverting the Taylor series for$b$,$b= \beta-\frac{\beta^{3}}{24}k^{2}-\frac{\beta^{4}}{24}kk’+O(\beta^{5})$.

we obtain$\beta=b+\frac{b^{3}}{24}k^{2}+\frac{b^{4}}{24}kk’+O(b^{5})$.

It gives$\frac{OBarrow}{b}=\mathrm{t}[1-\frac{b^{2}}{8}k^{2}-\frac{b^{3}}{12}kk’+O(b^{4})]+\mathrm{n}[\frac{b}{2}k+\frac{b^{2}}{6}k’+\frac{b^{3}}{24}k’’+O(b^{4})]$

.

.

164

Performing similar calculations we arrive at$\frac{O\mathrm{A}arrow}{a}=\mathrm{t}[-1+\frac{a^{2}}{8}k^{2}-\frac{a^{3}}{12}kk’+O(a^{4})]++\mathrm{n}[\frac{a}{2}k-\frac{a^{2}}{6}k’+\frac{a^{3}}{24}k’’+O(a^{4})]$Since$\mathrm{t}\cross \mathrm{n}=1$

where$\cross$,$\mathrm{n}\cross \mathrm{t}=-1$.

,

stands for the cross product, then$\sin\varphi=-\frac{OAarrow}{a}\cross\frac{OBarrow}{b}=\frac{OBarrow}{b}\cross\frac{OAarrow}{a}=$$= \frac{a+b}{2}k+\frac{b^{2}-a^{2}}{6}k’+\frac{a^{3}+b^{3}}{24}k^{n}-\frac{a^{2}b+ab^{2}}{16}k^{3}+O(a, b)^{4}$and finally$\varphi=\frac{a+b}{2}k+\frac{b^{2}-a^{2}}{6}k’+\frac{a^{3}+b^{3}}{24}(k’’+\frac{k^{3}}{2})+O(a, b)^{4}$

We can define the discrete curvature at

$O$

as

$\hat{k}=\frac{2\varphi}{a+b}$

The Taylor series expansion of$\hat{k}$with respect toa.

.
$a$and$b$

has the form$\hat{k}=k+\frac{b-}{3}$ $k’+ \frac{(b-a)^{2}+ab}{12}(k’’+\frac{k^{3}}{2})+O(a, b)^{3}$.

Next terms can be obtained with help of computer algebra systems like MAPLE andMATHEMATICA.
Similar calculations can be done for , the discrete curvature defined as the inverse
value of the radius of the circle passing through the points $A,$ $O,$ $B$ .
$\tilde{k}$