Separable algorithms for distance transformations on irregular grids

详细信息    查看全文

• 作者：Antoine Vacavant^a ; ^{antoine.vacavant@iut.u-clermont1.fr"" rel=""nofollow} ; David Coeurjolly^b ; ^c ; Laure Tougne^b ; ^d
• 关键词：Squared Euclidean distance transformation ; Irregular grids ; Quadtree ; Voronoi diagrams
• 刊名：Pattern Recognition Letters
• 出版年：2011
• 出版时间：1 July 2011
• 年：2011
• 卷：32
• 期：9
• 页码：1356-1364
• 全文大小：1675 K

文摘

In this article, we propose to investigate two extensions of the E²DT (squared Euclidean Distance Transformation) on irregular isothetic grids (or ), such as quadtree/octree or run-length encoded d-dimensional images. We enumerate the advantages and drawbacks of the , based on the cell centres, and the ones of the , 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 distance transformations in the two-dimensional case, and we show that they can be easily extended to higher dimensions.