Image Processing Reference
In-Depth Information
set. The representation of a binary object using medial disks is called its MAT.
In this representation, individual disks are denoted by their centers and radii.
In this chapter we discuss the MAT of binary objects in 2-D and 3-D, and its
application to various geometric computation on images.
In chapter 2 (refer to Section 2.5), we illustrated the properties of digital
disks of some of the interesting classes of distance functions, in particular
the hyperspheres of octagonal distances [59]. In our discussion, we consider
these distance functions for variation in the shape of hyperspheres of different
octagonal distances, and the ease of computation of the distance transform
(refer to Section 6.1) using them.
6.1 Distance Transform
The distance transform [181][23][57] of a bilevel image provides the distance
to the nearest background point at every pixel of the image. The computation
of distances of the object points from the nearest background is performed by
a simple iterative approach. In this case for an image of N points it requires
O(N
2
) computation. However, this transform may e
ciently be computed in
O(N) by performing a fixed number of scans over the images, a process known
as chamfering, as discussed below. First we discuss the iterative algorithm for
computing the distance transform given an octagonal distance d(B), where B
is the sequence of m-neighbor types, say, {b(1),b(2),...,b(p)} (refer to Section
2.4.1 of Chapter 2). We denote distance of a point q from the background
in the distance transformed image as D(q;B). Let us represent foreground
pixels (object points) and background pixels of a digital image as Σ and Ψ,
respectively.
6.1.1 Distance Transform through Iterative Scan
In this technique, the computation of distance proceeds from the boundary
points of the object (Σ) and moves toward its inner layers iteratively. First,
the distance of an object point (∈ Σ) is set to 1, which has a neighboring
background pixel (∈ Ψ) and the point is also flagged for acting as the wavefront
at a distance 1 for the next iteration. In the subsequent kth iteration, distance
of any unflagged object point is computed, if it has a neighboring point in
the approaching wavefront flagged in the previous iteration (with a distance
value of k− 1) and its distance is set to k. The process continues till all the
object points are assigned a distance value. For an octagonal distance with
a neighborhood sequence B, neighborhood definitions change following the
periodic ordering of the neighborhood types. For example, in our notations,
the order of neighborhood types to be used are b(1), b(2), ..., b(p), b(1),
b(2), etc. The computation is explained in Fig. 6.1. The boundary points
