libcornu

Download Link

GitHub

This package calculates completion curves derived from the Euler spiral (a.k.a Cornu spiral). These completions will be optimal with respect to the total change in curvature, a special case of elastica. Using Euler spirals for shape and contour completion was proposed by Kimia et. al. in their IJCV paper Euler Spiral for Shape Completion. This code was written for the paper Incorporating Topological Constraints within Interactive Segmentation and Contour Completion via Discrete Calculus by Xu et. al. to fill the need to calculate a very large number of Euler completions quickly as a subroutine in a branch-and-bound solver for salient contour completion.

Accordingly, this code incorporates a number of optimizations to calculate the spirals with computation time orders more than an order of magnitude less than the reference implementation by Kimia et. al. We implement the method of Walton & Meek, which poses the completion problem as a nonlinear system of equations (actually several such systems for different cases). This provides a route to calculate the parameters of the completion curve using numerical methods with better-characterized convergence than the evolution method of Kimia. et. al. The system of equations given by Walton & Meek is solved in this software by a hybrid of the bisection and Newton methods, providing both fast and stable convergence. The most expensive subroutine—the calculation of Fresnel integrals—is done using the method of Fleckner. This is further accelerated by using the entries of a precomputed table as a starting point. This table is generated at compile-time by the code included with this distribution.

Speed Trial: We run 100 batches of 4096 completions on a 3.40GHz Intel Core i7-2600, compiled with gcc 4.8.2 with -O3 -flto. The average time per completion is given below, with the standard deviation over the batches.

Implementation Time (± std dev)
Ours 14.25μs ± 0.2962μs
Reference 631.6μs ± 64.02μs

Distributed under the MIT License, except for the external subdirectly including code from Kimia et. al., which can only be redistributed noncommercially according to a license included with that source. This code was written to calculate Cornu spiral completions for Incorporating Topological Constraints within Interactive Segmentation and Contour Completion via Discrete Calculus by Xu et. al. Researchers who wish to cite this work should refer to that paper and the IJCV paper by Kimia et. al. below.

Prerequisites

Compile-time only, used in generating the precomputed table of Fresnel integrals: For included tests & demos:

References

  1. Jia Xu, Maxwell D. Collins, and Vikas Singh. Incorporating Topological Constraints within Interactive Segmentation and Contour Completion via Discrete Calculus. CVPR, June 2013.
  2. Benjamin B. Kimia, Ilana Frankel, and Ana-Maria Popescu. Euler spiral for shape completion. IJCV, 54,159-182, 2003. (Website)
  3. David Mumford. Elastica and computer vision. Algebraic Geometry and Its Applications, 491-506, 1994.
  4. Desmond J. Walton and Dereck S. Meek. G1 interpolation with a single Cornu spiral segment. Journal of Computational and Applied Mathematics, 223(1):86-96, 2009.
  5. Oscar L. Fleckner. A method for the computation of the fresnel integrals and related functions. Mathematics of Computation, 22(103):635-640, 1968.