Image Processing Reference
In-Depth Information
(a)
(b)
(c)
FIGURE 6.4: (a) An object (set-square) (b) distance transform using {112},
(c) Euclidean distance transform using 8SED algorithm [53].
[53], which is based on local propagation of distance values and uses a scheme
similar to chamfering. Danielsson reported this algorithm in the early eight-
ies. Subsequently, other researchers [133, 170] reported many variations and
improvements of this scheme.
In the computation of EDT, initially all the object points are assigned to
a large distance value and all the background points are set to zeroes. How-
ever, in the representation of Euclidean distance at an object point, a two-
dimensional element such as (a,b) is used, where the distance is expressed
as
√
a
2
+ b
2
. The final distance-transformed array for the object contains
these elements. The technique follows a vectorial propagation scheme from the
neighborhood of a point. In [53], two different propagation schemes based on
4-neighbors and 8-neighbors were proposed. The first technique was referred
to as the 4SED algorithm and the latter was named the 8SED algorithm. As
the 8SED algorithm provides better approximation of the EDT, it is discussed
here. Similar to the chamfering scheme, in this algorithm, the computation
involves two scans, one in the forward directions (from left to right and top
to bottom), and the other in the reverse directions (from right to left and top
to bottom). Each scan uses three masks for computing the minimum distance
value at a pixel from the distances of its neighbors by adding the propagated
distance toward it. For example, for each column of the forward scan, the mask
of Fig. 6.5(a) is used, followed by the other two masks in Figs. 6.5(b) and (c),
respectively. Similarly, in the reverse scan, each column first uses the mask
of Fig. 6.5(d). Then the values are further updated by scanning of the masks
of Figs. (e) and (f), respectively. In the figure, the coordinate convention is
shown by x and y axes. The example of EDT obtained using this algorithm
is shown in Fig. 6.4. We observe that the result appears to be similar to what
was obtained from the octagonal distance {112} (refer Fig. 6.4(b)).
