Separable algorithms for distance transformations on irregular grids

A. Vacavant, David Coeurjolly, L. Tougne

Pattern Recognition Letters January 2011

Abstract

In this article, we propose to investigate two extensions of the E2DT (squared Euclidean Distance Trans- formation) on irregular isothetic grids (or I-grids), such as quadtree/octree or run-length encoded d-dimensional images. We enumerate the advantages and drawbacks of the I-CDT, based on the cell cen- tres, and the ones of the I-BDT, which uses the cell borders. One of the main problem we mention is that no efficient algorithm has been designed to compute both transforms in arbitrary dimensions. To tackle this problem, we describe in this paper two algorithms, separable in dimension, to compute these dis- tance transformations in the two-dimensional case, and we show that they can be easily extended to higher dimensions.

Type

Journal article

Publication

Pattern Recognition Letters

Caption: Example of the VD of the background points to obtain the I-CDT of a simple I-grid (a) and the background/foreground frontier (dark segments) to obtain the I-BDT (b).

@article{dcoeurjo_vacavant_PRL2011,
      author = {A. Vacavant and David Coeurjolly and L. Tougne},
      doi = {10.1016/j.patrec.2010.11.010},
      journal = {Pattern Recognition Letters},
      pages = {1356-–1364},
      title = {Separable algorithms for distance transformations on irregular grids},
      volume = {32},
      year = {2011}
}