Euler arc splines for curve completion

Abstract

This paper introduces a special arc spline called an Euler arc spline as the basic form for visually pleasing completion curves. It is considered as an extension of an Euler curve in the sense that the points in the Euler curve are replaced by arcs. A simple way for specifying it, which is suitable for shape completion, is presented. It is shown that Euler arc splines have several properties desired by aesthetics of curves, in addition to computational simplicity and NURBS representation. An algorithm is proposed for curve completion using Euler arc splines. The development of the algorithm involves two optimization processes, which are converted into a single minimization problem in two variables solved by the Levenberg–Marquardt algorithm. Compared to previous methods, the proposed algorithm always guarantees the interpolation of two boundary conditions.

Introduction

This paper deals with the problem of curve completion, which is a process of completing contours beyond occlusions or across gaps [1]. It is also known as shape completion or gap completion, which is related to visual completion—a fundamental skill for human vision system [2]. Referring to Fig. 1, for example, when an object is partially occluded by others, human can automatically fill the gap by completing its contour; when an object is illusory, human can also consciously generate a subjective completed boundary. However, for a computer, this is a nontrivial task. Shape completion has wide applications in computer graphics such as shape transition or repairing for CAD [3], [4] and in computer vision such as inpainting for objects with smooth curvilinear shapes [1].

The process of shape completion is actually to find an optimal curve through two specified endpoints with associated orientations, which we call point-orientation pairs. There exist many possible curves that meet the conditions of point-orientation pairs. The problem is under-specified despite the appeal of our vision intuition for an optimal solution [1]. The solution really depends on the criteria regarding what constitutes the most “likely” or the most “pleasing” curve [1], [5]. In this paper we provide a new solution by presenting an appropriate curve representation and its associated construction algorithm.

Since two given points with associated orientations provide the first order geometric Hermite data, a straightforward approach to shape completion is to use cubic Hermite interpolation [4]. Hermite interpolation is simple to construct and compute, but it does not always provide satisfactory results as shown in [3]. It is pointed out in [6] that one reason for Hermite interpolation to produce undesired shapes is unsuitable magnitudes of the given tangent vectors. Therefore Yong and Cheng present a new class of curves called optimized geometric Hermite curves for which the magnitudes of the endpoint tangent vectors in the Hermite interpolation process are optimized to make the strain energy of the curves be minimized [6].

Ullman suggests several criteria for completion curves [7]. That is, the curves should be invariant to rigid transformation, at least differentiable once, extensible, and minimize total curvature. Based on these criteria, he then proposes to use biarcs that minimize total square curvature as completion curves. However, it is later found that in many cases biarc completions have less pleasing appearance than the cubic polynomial completions [8] and Ullman's biarc completion curve is generally not extensible [9]. Knuth considers the shape representation and construction of letters or symbols in typography from a collection of points [10], which is a problem similar to shape completion. He proposes six criteria, somewhat similar to Ullman's, which the most “pleasing” curve through a set of specified points should satisfy. These criteria are known as similar transformation invariance, symmetry, extensibility, locality, smoothness, and roundedness [10], [1]. Since the last four criteria cannot be simultaneously satisfied, Knuth gives up the extensibility and roundedness properties but insists in the locality property, which leads to a cubic spline interpolation solution. This is the base of Knuth's METAFONT system. However, psychological studies have indicated that splines may not be a satisfactory primitive for shape completion [11].

A lot of work on aesthetic curve design proposes some energy functional and defines the curve as a solution to the problem of minimizing the energy functional. Elastica is one of such examples, in which the energy functional is the integral of a linear combination of the square curvature and the arc-length [12], [13], [14], [15]. Elastica is extensible, but not scale-invariant or rounded. On the other hand, it is argued that the energy functional capturing the elusive nature of the “most pleasing” curve should penalize curvature variation, but not necessarily curvature proper as in Elastica. In particular, minimizing the integral of the square of the derivative of curvature with respect to arc-length requires the curvature to be linear in arc-length, which leads to an Euler curve. Euler curves are also known as “Cornu spirals” or “Clothoid”. They have been used in various applications including highway and railroad design, computer aided design, and computer arts. 2D Euler curves have been generalized to 3D such that the curvature and torsion of the curve are linear with arc-length [16], [3] or to piecewise Euler spirals [17]. Since Euler curves are defined by complicated transcendental functions, some work devotes to approximating Euler curves by some simple representations such as Bézier curves and arc splines [18], [19], [20], [21], [22].

Kimia et al. [1] show that Euler curves are a suitable primitive for shape completion and various practical advantages of using Euler curve interpolation are examined. An algorithm for shape completion using Euler curves is described, which finds the completion curve by solving two nonlinear equations in two unknowns involving Fresnel integrals. A biarc fitting is used for producing an initial guess and then the algorithm performs iteratively. Walton and Meek [23] improve the work by formulating the problem into two nonlinear equations with only one unknown each, which gives a faster and more accurate algorithm.

This paper is inspired by Kimia et al.'s work of using Euler curves for shape completion [1]. Psychological studies show that Euler curves have good fit to the way that the human eyes complete curves [11]. However, there are some drawbacks with Euler curves for shape completion. First, due to complicated transcendental function representation of Euler curves, it is difficult or expensive to compute with Euler curves. In particular, for rendering purpose, Euler curves are often approximated by line segments or arc segments. Second, Kimia et al.'s algorithm finds the solution by a numerical approach that minimizes the distance between the second given point and the last point of the Euler curve. Sometimes the numerical approach might not converge or the approximate solution is not good enough. As a consequence, the resulting Euler curve will not pass through the second point. This will violate the aesthetics of shape completion since human perception is sensitive to gaps. Third, Euler curves are not compatible with nonuniform rational B-splines (NURBS) which are an industry standard in CAD/CAM.

These limitations motivate us to explore new completion curve models and shape completion algorithms. It is observed by Horn [12] that in the optimal multi-arcs that approximate the “smoothest” curve arcs tend to be of equal length and curvature changes more or less linearly along the curve. Therefore in this paper, we propose a special arc spline called an Euler arc spline as the completion curve primitive for shape completion. The Euler arc spline consists of G¹ continuous arcs of the same length with curvature changing linearly from one arc to another. It is a good approximation to an Euler curve. We identify and analyze the parameters needed to specify an Euler arc spline in Section 2 and show that Euler arc spline curves exhibit similar properties as Euler curves. Meanwhile, Euler arc spline curves are simple for computation, rendering and other geometric processing such as offsetting and distance query. They are nonuniform rational B-spline curves, facilitating the use with standard graphics packages. Another arc spline similar to an Euler arc spline has been introduced in [21], which is called discrete clothoid where the first and last arcs are half the length of the others. The approximation properties of discrete clothoid are analyzed. Particularly, if a clothoid is approximated by a discrete clothoid of n arcs, the approximation error is of order $O(1/n^2)$. However, no algorithm is provided to construct a discrete clothoid for shape completion.

We also propose a curve completion algorithm using the proposed Euler arc splines in Section 3. We reduce the construction of completion curve from two point-orientation pairs to minimizing the sum of squares of nonlinear functions in two unknowns, which is then solved by the Levenberg–Marquardt algorithm. The underlying idea of our approach is to distribute the approximate error between the second given point and the last point of the completion curve to all the arcs and an optimization procedure is performed to minimize the errors. Consequently, the interpolation of two given point-orientation pairs with our completion curve is always guaranteed, which overcomes the drawback of Kimia et al.'s algorithm.