Image Processing Reference
In-Depth Information
F. Hence, the distance at q from the background can be computed as follows:
D(q;B) = min
∀x∈F
(D(x;B) + d(x;B).)
(6.1)
*
*
3
3
3
*
*
*
*
3
3
3
*
*
*
3
3
2
3
3
*
*
3
3
2
3
3
*
3
3
2
1
2
3
3
3
3
2
1
2
3
3
3
2
1
0
1
2
3
3
2
1
0
1
2
3
3
3
2
1
2
3
3
3
3
2
1
2
3
3
*
3
3
2
3
3
*
*
3
3
2
3
3
*
*
*
3
3
3
*
*
*
*
3
3
3
*
*
(a)
(b)
FIGURE 6.3: Pixels of chamfering mask of {112} used in (a) forward scan,
and (b) reverse scan.
Similarly, in the reverse scan, while visiting the pixels in an order from bot-
tom to top and right to left, the unshaded zones of Fig. 6.3(b) are considered
for updating the distance values. Let the corresponding visited neighboring
pixels in the mask form the set R. In that case, at a pixel q, the distance value
from the background is updated as follows:
D(q;B) = min
∀x∈R
(D(x;B) + d(x;B)) .
(6.2)
Once these two scans are completed, we obtain the distance transform of the
image.
An example of the generalized octagonal distance transforms is shown
in Figure 6.4 (b) using the distance function {112}. Each distance value in
the distance-transformed image is taken as the gray-scale value. The brighter
color represents the larger distance and the darker color represents the smaller
distances.
6.1.4 Euclidean Distance Transform
There are algorithms [82] for computing distance transforms of digital im-
ages using Euclidean metrics. However, computation of Euclidean distance
transform (EDT) is a nontrivial problem. In this case, the Voronoi regions
[169] of background points may not be connected as explained in [51]. For
this property, local propagation of distance values, as followed for digital
distance transforms discussed in previous sections, is not recommended for
computing the EDT. There are algorithms for computing exact EDTs based
on e
cient computation of discrete Voronoi regions [185, 138] of background
points. However, all these algorithms are computationally costlier than digital
distance transforms. We discuss here an approximate computation of EDT
