Fuzzy distance transform: Theory, algorithms, and applications

This paper describes the theory and algorithms of distance transform for fuzzy subsets, called fuzzy distance transform (FDT). The notion of fuzzy distance is formulated by first defining the length of a path on a fuzzy subset and then finding the infimum of the lengths of all paths between two points. The length of a path pi in a fuzzy subset of the n-dimensional continuous space R-n is defined as the integral of fuzzy membership values along pi. Generally, there are infinitely many paths between any two points in a fuzzy subset and it is shown that the shortest one may not exist. The fuzzy distance between two points is defined as the infimum of the lengths of all paths between them. It is demonstrated that, unlike in hard convex sets, the shortest path (when it exists) between two points in a fuzzy convex subset is not necessarily a straight line segment. For any positive number theta less than or equal to 1, the theta-support of a fuzzy subset is the set of all points in R-n with membership values greater than or equal to theta. It is shown that, for any fuzzy subset, for any nonzero theta less than or equal to 1, fuzzy distance is a metric for the interior of its theta-support. It is also shown that, for any smooth fuzzy subset, fuzzy distance is a metric for the interior of its theta-support (referred to as support). FDT is defined as a process on a fuzzy subset that assigns to a point its fuzzy distance from the complement of the support. The theoretical framework of FDT in continuous space is extended to digital cubic spaces and it is shown that for any fuzzy digital object, fuzzy distance is a metric for the support of the object. A dynamic programming-based algorithm is presented for computing FDT of a fuzzy digital object. It is shown that the algorithm terminates in a finite number of steps and when it does so, it correctly computes FDT. Several potential applications of fuzzy distance transform in medical imaging are presented. Among these are the quantification of blood vessels and trabecular bone thickness in the regime of limited special resolution where these objects become fuzzy. (C) 2002 Elsevier Science (USA).