ALGORITHMS FOR PROCESSING CONNECTED COMPONENTS WITH GRAY VALUES - Fundamentals of Three-Dimensional Digital Image Processing - page 189

8

π +

π -

Fig. 6.1. Illustration of the gray weighted distance transformation of a gray-tone
image with the background. Find a path to minimize the weight |π| (= the sum
of density values on a path) among paths {π 1 ,π 2 ,...} to a point P from a border
surface and give the minimum weight to a point P.

| is called weight of a path π . The name of gray weighted comes from this

fact. A path that gives g ijk

π |

is called a minimal path to ( i, j, k ) (Fig. 6.1).

Algorithms to calculate the 6-, 18-, and 26-neighborhood GWDT are ob-
tained by straightforward extension of algorithms for a 2D image. The basic
idea is the same as in a 2D image, that is, to find a path such that the total
sum of distance values along a path (= the weight of a path) is minimized.
The extension of the Euclidean DT to a gray-tone image is not a com-
plicated concept. That is, it is defined as the minimization of the total sum
of density values along an arbitrary path in continuous space. This is not re-
alized easily on a digitized image, because it is almost impossible to find a
minimal path as a sequence of voxels. This is why an algorithm to perform
the Euclidean GWDT has not been reported yet.

6.1.2 An example of algorithm

Let us discuss an example of the sequential algorithm of the 6-, 18-, and the
26-neighborhood GWDT.

Algorithm 6.1 (GWDT of a gray-tone image sequential type).
F = { f ijk } : Input image (gray-tone image with the background) (size L ×

M × N )

G = { g ijk } : Output image (= GWDT)

W = { w ijk } : Work array