Basic concepts

The aim of a distance transformation is to compute the distance from a point to an object, i.e. to a set of pixels. As illustrated at figure (left), the distance from point p to the object is the smallest distance from p to any point of the object. In other words, it is the distance from p to the nearest point q belonging to the object.

If one wants to know the distance from p to the object, one can apply the above definition, although it requires a large amount of computations when the object contains many points. When one needs to know this distance in several locations p, it is often faster to simply look it up in a distance map (figure ), i.e. an image where the distance to the object has been pre-computed in all locations.

The distance transformation (DT) is the operation that computes the distance map from the binary image representing the object. The key point of this thesis is that it is possible - although not necessarily easy - to implement distance transformations efficiently.

  

Figure 1.1: Left: distance from a point to an object. Right: distance map

There are several ways to define distances. In figure , the distance from p to the object is the distance from p to q. That means that the value of the distance map D in p, or D(p), is 5 when distances are computed with the usual Euclidean metric.

On the other hand, one could consider another type of metric. For instance, the city-block distance is defined as the shortest path with only vertical and horizontal steps. With that metric, D(p) is the distance along the dashed line, i.e. D(p)=|3|+|4|=7.

Another extension is what people call the ``signed'' distance. Instead of a simple scalar value, the signed distance transformation computes the relative location of p from its nearest object pixel q. In figure , the signed DT gives SD(p)=p-q=(3,-4). It is of course possible to compute the value of the unsigned distance from the value of the signed distance, but not the opposite.

The nearest neighbor transformation computes, at every location p, the nearest pixel q in the object. In figure , we have NN(p) = q = (11,7). Computing the nearest neighbor or the signed distance transformations is of course equivalent, with SD(p)=p-NN(p).

  

Figure 1.2: Unsigned DT, signed DT and Nearest neighbor transformation.