Distance transform in images and connected plane graphs

Abstract

The distance transform (DT) serves as a crucial operation in numerous image processing and pattern recognition methods, finding broad applications in areas such as skeletonization, map-matching robot self-localization, biomedical imaging, and analysis of binary images. The concept of DT computation can also be extended to non-grid structures and graphs for the calculation of the shortest paths within a graph. This paper introduces two distinct algorithms: the first calculates the DT within a connected plane graph, while the second is designed to compute the DT in a binary image. Both algorithms demonstrate parallel logarithmic complexity of {\$}{\$}{\backslash}mathcal{\{}O{\}}(log(n)){\$}{\$}O(log(n)), with n representing the maximum diameter of the largest region in either the connected plane graph or the binary image. To attain this level of complexity, we make the assumption that a sufficient number of independent processing elements are available to facilitate massively parallel processing. Both methods utilize the hierarchical irregular pyramid structure, thereby retaining topological information across regions. These algorithms operate entirely on a local level, making them conducive to parallel implementations. The GPU implementation of these algorithms showcases high performance, with memory bandwidth posing the only significant constraint. The logarithmic complexity of the algorithms boosts execution speed, making them particularly suited to handling large images.