  The distance transform (DT) and its many variations are ubiquitous tools for
image processing and analysis. In many imaging scenarios, the images of
interest are corrupted by noise. This has a strong negative impact on the
accuracy of the DT, which is highly sensitive to spurious noise points. In this
study, we consider images represented as discrete random sets and observe
statistics of DT computed on such representations. We, thus, define a
stochastic distance transform (SDT), which has an adjustable robustness to
noise. Both a stochastic Monte Carlo method and a deterministic method for
computing the SDT are proposed and compared. Through a series of empirical
tests, we demonstrate that the SDT is effective not only in improving the
accuracy of the computed distances in the presence of noise, but also in
improving the performance of template matching and watershed segmentation of
partially overlapping objects, which are examples of typical applications where
DTs are utilized.
