DIPlib Documentation - ©1995-2013 Quantitative Imaging Group, Delft University of Technology.

# GreyWeightedDistanceTransform

Grey weighted distance transform

## SYNOPSIS

`#include "dip_distance.h"`

dip_Error dip_GreyWeightedDistanceTransform ( in, seed, out, distance, chamfer, neighborhood, metric )

## DATA TYPES

`in`: integer, float

`seed`: binary

## FUNCTION

`GreyWeightedDistanceTransform` determines the grey weighted distance transform of the object elements in the `in` image and returns the result in the `out` image. The implemented algorithm uses a heap sort for sorting the pixels to be processed.

The images `in` and `seed` must have the same dimensions. The `out` image will be converted to a `sfloat` typed image. The `seed` image defines the elements that are part of the object for which the GDT is determined. It can be any type of image where all image elements not equal to 0 are considered to be part of the object(s). Those elements that are neighboring an object element in the output image are considered seeds. Before any seeds are detected the borders of the `out` image are set to 0. The size of the border is determined by the chamfer metric size (see below). In case of a 3 by 3 chamfer metric the image border is one element, in case of a 5 by 5 chamfer it is 2 elements. Elements in the border are not considered seeds. If no valid seeds are found the routine will terminate with an Illegal value error code.

The chamfer metric is defined by two parameters: `neighborhood` and `metric`. `neigborhood` should supply the different relative addresses of the neighboring elements according to the chamfer metric. The first element `neighborhood[0]` contains the number of elements in the chamfer neighborhood. The next three elements contain the maximum number of elements a chamfer metric exceeds the central element. The rest of the elements (starting from the fifth element) contain addresses of the different chamfer elements relative to the central element. The `metric` array contains the corresponding chamfer metric value. An example of a 3x3 neighborhood array with the corresponding metric is:

              neighborhood[0] = 8 (number of elements)
              neighborhood[1] = 1 (x-border size)
              neighborhood[2] = 1 (y-border size)
              neighborhood[3] = 0 (z-border size)
              neighborhood[4] = -imagewidth - 1,    metric[0] = 7
              neighborhood[5] = -imagewidth,        metric[1] = 5
              neighborhood[6] = -imagewidth + 1,    metric[2] = 7
              neighborhood[7] = -1,                 metric[3] = 5
              neighborhood[8] = 1,                  metric[4] = 5
              neighborhood[9] = imagewidth - 1,     metric[5] = 7
              neighborhood[10] = imagewidth,        metric[6] = 5
              neighborhood[11] = imagewidth + 1,    metric[7] = 7

where `imagewidth` represents the width of the image in image pixels. If both `neighborhood` and `metric` pointers are `NULL`, the `chamfer` variable can be set to either 1 (indicating a 3x3 or 3x3x3 chamfer using only 4 or 6 direct neighbors), 3 (indicating a 3x3 or 3x3x3 chamfer, using all neighbors) or 5 (indicating a 5x5 or 5x5x5 chamfer). In these cases a preset `neighborhood` and `metric` arrays will be used.

## ARGUMENTS

Data type | Name | Description
`dip_Image` | `in` | Input image
`dip_Image` | `seed` | Seed image
`dip_Image` | `out` | Integrated grey-value over least-resistance path (output image)
`dip_Image` | `distance` | Metric distance over least-resistance path (output image)
`dip_int` | `chamfer` | Chamfer distance metric
`dip_IntegerArray` | `neighborhood` | Neighborhood
`dip_FloatArray` | `metric` | Metric

## LITERATURE

"An efficient uniform cost algorithm applied to distance transforms", B.J.H. Verwer, P.W. Verbeek, and S.T. Dekker, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 4, 1989, 425-429.

"Shading from shape, the eikonal equation solved by grey-weighted distance transform", P.W. Verbeek and B.J.H. Verwer, Pattern Recognition Letters, vol. 11, no. 10, 1990, 681-690.

"Local distances for distance transformations in two and three dimensions", B.J.H. Verwer, Pattern Recognition Letters, vol. 12, no. 11, 1991, 671-682.

"Distance Transforms, Metrics, Algorithms, and Applications", B.J.H. Verwer, Ph.D. thesis Delft University of Technology, Delft University Press, Delft, 1991.

"3-D Texture characterized by Accessibility measurements, based on the grey weighted distance transform", K.C. Strasters, A.W.M. Smeulders, and H.T.M. van der Voort, BioImaging, vol 2, no. 1, 1994, p. 1-21.

"Quantitative Analysis in Confocal Image Cytometry", Karel C. Strasters, Delft University Press, Delft, 1994. ISBN 90-407-1038-4, NUGI 841

## KNOWN BUGS

`GreyWeightedDistanceTransform` works only on 2 or 3-dimensional images. It will not work if any of the images has different strides.

`GreyWeightedDistanceTransform` produces incomplete results in a 2-pixel border around the edge (4 for `chamfer` = 5). If this is an issue, consider adding 2 pixels on each side of your image. Make sure that `in` has high grey values in the border to avoid unexpected output.

The function `GrowRegionsWeighted` produces a grey-weighted distance transform without these limitations and with some other possibilities.

## AUTHOR

Karel C. Strasters, adapted to DIPlib by Geert M.P. van Kempen

## SEE ALSO

`GrowRegionsWeighted`, `EuclideanDistanceTransform`, `VectorDistanceTransform`