2D Subquadratic Separable Distance Transformation for Path-Based Norms

18th International Conference on Discrete Geometry for Computer Imagery September 2014

Abstract

In many applications, separable algorithms have demon- strated their efficiency to perform high performance volumetric com- putations, such as distance transformation or medial axis extraction. In the literature, several authors have discussed about the conditions on the metric to be considered in a separable approach. In this article, we present generic separable algorithms to efficiently compute Voronoi maps and distance transformations for a large class of metrics. Focusing to path based norms (chamfer masks, neighborhood sequences, …), we detail a subquadratic algorithm to compute such volumetric transformations in dimension 2. More precisely, we describe a O(log2 m · N^2) algorithm in dimension 2 for shapes in a N × N domain with chamfer norm of size m.

Type

Conference paper

Publication

18th International Conference on Discrete Geometry for Computer Imagery

Caption: VoronoiEdgeWedge and VoronoiEdge: (a) initial problem, we want to compute the intersection between S and the Voronoi edge of a and b (in red). (b) an internal step of VoronoiEdgeWedge to reduce the set of directions of M at a (here the next recursive call will be on (v^i, v^mid)).(c) final step of VoronoiEdge where both wedges have been obtained and thus e can be computed.

@inproceedings{dcoeurjo_DGCI14_subquad,
      author = {David Coeurjolly},
      booktitle = {18th International Conference on Discrete Geometry
for Computer Imagery},
      language = {en},
      month = {September},
      pages = {75-87},
      publisher = {Springer},
      title = {2D Subquadratic Separable Distance Transformation for Path-Based Norms},
      url = {http://liris.cnrs.fr/publis/?id=6698},
      year = {2014}
}