Definitions.

From a binary image I made of an object O and its background O', a distance transformation [132] makes an image, the distance map D (Fig. ), in which the value of any pixel is the distance from this pixel to the object O, i.e. the distance to the nearest pixel of O.

$$D(p)=min\{dist_M(p,q), q \in O\}$$ (2.1)

  

Figure 2.1: Example of a distance transformation using the dist_E metric. Left: original image. Center: distance map. Right: Voronoi diagram.

The following notations are used in this text. Letters p,q,r are used for pixels, with indexes p_i where needed. In the original image, those pixels belong either to the object O or the background O' of the image. The coordinates of pixel p are (p_x,p_y). dist_M(p,q) is the distance between pixels p and q using the metric M. The following metrics are considered:

 

dist₄(p,q)=|p_x-q_x|+|p_y-q_y| (2.2)

$$dist_{8}(p,q)=\max\{\vert p_x-q_x\vert,\vert p_y-q_y\vert\}$$ (2.3)

 

$$A.\max\{\vert p_x-q_x\vert,\vert p_y-q_y\vert\} +$$ dist_cha(A:B)(p,q) = (2.4)

$$dist_e(p,q)=\sqrt{(p_x-q_x)^2+(p_y-q_y)^2}$$ (2.5)

 

dist_E(p,q)=(p_x-q_x)²+(p_y-q_y)² (2.6)

They are called the city block (), chess board (), chamfer (), Euclidean () and squared Euclidean metric (), respectively. In what follows, when we speak of a Euclidean distance transformation, we usually mean a DT computed using the dist_E metric. Indeed, it is equivalent to dist_e but can be computed using integer operations only since pixels are located on integer locations.

In the above definitions, the only relevant information is of course the relative location of pixels p and q, i.e. dp=p-q. Therefore we often used the simpler notation

 

dist_M(dp)=dist_M(p,q) (2.7)

For instance, we have

 

dist_E(dp)=dp_x²+dp_y² (2.8)

An important related concept is that of the Voronoi diagram. It divides the plane into tiles surrounding each object pixel. VP(p) is the Voronoi Polygon surrounding a pixel p of the object. For every pixel $p \in O$, VP(p) is the part of image I that satisfies

$$VP(p)=\{ q \in I \; \vert \; \forall \, r \in O \, , \, dist_M(p,q) \leq dist_M(q,r) \}$$ (2.9)

Finally, image processing operations are usually defined locally, i.e. pixels are only influenced by their neighborhood. We write N(p) the set of neighbors of p, i.e.

$$N(p)=\{q=p+n \, \vert \, n \in N\}$$ (2.10)

N=N((0,0)) is called a neighborhood. The neighborhoods considered here are balls, i.e. neighborhoods such that

$$N=B_d=\{ n \, \vert \, dist_M(n,(0,0)) < d\}$$ (2.11)

with some metric M. Of particular interest are the 4-direct and 8-direct neighborhoods defined as

  

$$\{ n \, \vert \, dist_{4}(n,(0,0)) = 1 \}$$ N₄ =

$$\{ (1,0), (-1,0), (0,1), (0,-1) \}$$ = (2.12)

$$\{ n \, \vert \, dist_{8}(n,(0,0)) = 1 \}$$ N₈ =

$$N_4 \cup \{ (1,1), (1,-1), (-1,1), (-1,-1) \}$$ = (2.13)