On digital distance transforms in three dimensions

Digital distance transforms in 3D have been considered for more than 10 years. However, not all of the complexities involved have been unravelled. In this paper the complete geometry and equations for 3D transforms based on a 3 x 3 x 3 neighborhood of local distances are given. A new type of valid distance transforms (DTs) have been discovered. The optimal solutions are computed, where optimality is defined as minimizing the maximum difference from the true Euclidean distance, thus making the DTs as direction independent as possible. The well-known (3, 4, 5) DT is confirmed as the most practical weighted DT, where the distance is set to 3 between neighbors sharing an area, 4 between neighbors sharing an edge, and 5 between neighbors sharing a point. (C) 1996 Academic Press, Inc.