Solving Curve Completion Problems With Discrete Invariants

摘要

We demonstrate a novel method for solving the curve completion problem which is a subproblem of the much more complex inpainting problem [3] [4j. We use classical mathematical techniques borrowed from physics: we consider the missing part of the curve to minimise an analogue of the action principle, known as a Lagrangian, normally used to obtain the motion of physical bodies or paths of light rays (for example). In our case, the action principle is chosen on aesthetic grounds rather than from a physical model. Since the curve completion problem is equivariant with respect to translation and rotation, we need the action principle to be invariant under the natural action of the Euclidean group on curves on the plane or in space. Further, since the curves in practice will be approximate or even themselves digital curves, we consider a discrete analogue of the mathematics involved, in particular we compose our action principle using discrete Euclidean invariants. In this paper we model the curves using B-splines using data from the given portion of the curve to obtain the boundary conditions, but many other discrete models are amenable to these techniques. Action principles for smooth curves with Euclidean symmetries involve second order and higher derivatives, and these are highly sensitive to noise [1] [2]. We show that, by contrast, relatively simple discrete action principles offer excellent results for the curve completion problem. We note that the methods we develop for the discrete curve completion problem are general and can be used to solve other discrete variational problems for B-spline curves.