Image Processing Reference
In-Depth Information
of the polygonal object in the figure are computed using the neighborhood
definition of type b(1) and they are set at a distance of 1. In the figure, these
are shown by the color red. Its immediate neighbors with the neighborhood
type b(2) are set at a distance of 2 and they are shown by the color blue. The
process continues with changing neighborhood definitions following B till the
distance values of all the object points are computed. The algorithm runs in
O(D
max
N) times where D
max
is the maximum distance of an object point
from the background and N is the number of points in an image. As D
max
could be of O(N), it has a quadratic time complexity.
FIGURE 6.1: Computation of DT using iterative scan from boundary points.
(See color insert.)
6.1.2 Chamfering Algorithm
Borgefors [22] discussed a linear time algorithm for computing the distance
transform of an object. In this technique, an extended neighborhood mask enu-
merating the distance values from its center using the distance function under
consideration, is scanned by placing its center at every pixel and the distance
values of the pixel (from the background) is updated by observing distances of
its neighboring pixels, visited before. This computation is performed by two
scans following the forward and reverse ordering of scans. The nature of the
scan depends upon the dimension of image. For example, in 2-D, the forward
scan involves an ordering from left to right and top to bottom of the image
array, while the reverse scan goes in an ordering from right to left and bot-
tom to top. Similarly, in 3-D we have another added dimension imposing an
ordering of object planes from front to back. So in this case, the forward scan
involves an ordering from left to right, top to bottom, and front to back. The
reverse order is also similarly defined as it is done for the case 2-D. Borgefors
