Efficient Distance Transformation for Path-based Metrics


In many applications, separable algorithms have demonstrated their efficiency to perform high performance volumetric processing of shape, such as distance transformation or medial axis extraction. In the literature, several authors have discussed about 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 on path-based norms (chamfer masks, neighborhood sequences…), we propose efficient algorithms to compute such volumetric transformation in dimension $n$. We describe a new $O(n· N^n·łogN·(n+łog f))$ algorithm for shapes in a $N^n$ domain for chamfer norms with a rational ball of $f$ facets (compared to $O(f^łfloorfracn2f̊loor· N^n)$ with previous approaches). Last we further investigate an even more elaborate algorithm with the same worst-case complexity, but reaching a complexity of $O(n· N^n·łogf·(n+łog f))$ experimentally, under assumption of regularity distribution of the mask vectors.

Caption: Chamfer masks and rational balls: in dimension 2, generator vectors for the mask $mathcalM_3-4$ $(a)$, its rational ball $(b)$. Generator vectors for $mathcalM_5-7-11$ $(c)$ and its rational ball $(d)$. In dimension 3, rational ball of a chamfer mask obtained using generator vectors $(x,y,z) ın [![-3,3]!]^3$. For such chamfer norms in dimension $n$, we propose an efficient separable algorithm to compute the distance transformation of a digital shape in a domain $N^n$.

      author = {Coeurjolly, David and Sivignon, Isabelle},
      hal_id = {hal-02000339},
      hal_version = {v1},
      institution = {CNRS},
      month = {January},
      note = {Technical Paper},
      title = {Efficient Distance Transformation for Path-based Metrics},
      url = {https://hal.archives-ouvertes.fr/hal-02000339},
      year = {2019}