Image Processing Reference
In-Depth Information
6.2.1 MAT from the Distance Transform
The MAT of an image can be obtained by the following theorem.
Theorem 6.1. Given a distance transform D of an image, its local maxima
form the set of medial points and one less than the distance value at that point
provides the radius of the medial disk.
€
For proving the above theorem, we prove that a digital disk with a radius
of k−1, where k is the distance value at a local maxima, is totally contained
in the foreground of the image, and it is not completely covered by any other
digital disk containing only foreground points. Let r(q) be the minimum dis-
tance of the point q ∈ Σ from the boundary. We consider the digital disk
H(q,r(q);B) and its boundary points S(q,r(q);B) at q in the metric space of
d(B), where B = {t(1),t(2),...,t(p)} is the neighborhood sequence. Clearly,
H(q,r(q);B) ⊂ Σ. Let N
t(i)
(q) be the set of neighbors of q of type t(i). Hence,
for any path from a point u ∈S(q,r(q);B) to q, the neighborhood type at q is
t(j) where j = (r(q)−1) mod p. Hence, clearly, ∀x∈ N
t(j)
(q),r(x) 6 r(q)+ 1.
It implies that if ∃x ∈ N
t(j)
(q) such that r(x) > r(q), then r(x) = r(q) + 1.
From this property, we can state that the local maximum in the distance
transform provides the center of the maximal block contained in the pattern
as given in the following theorem.
Theorem 6.2. If ∃x ∈ N
t(j)
(q),r(x) > r(q), then H(q,r(q);B) ⊂
H(x,r(x);B).
Proof: ∀z,z ∈S(q,r(q);B), d(z,q;B) = r(q) (by definition).
If ∃x ∈ N
t((r(q)−1) mod p)
(q), there exists a path from z ∈ S(q,r(q);B) to the
point x, whose length is r(q) + 1.
Therefore, ∀z ∈S(q,r(q);B),d(z,x) 6 r(q) + 1.
Now, H(x,r(x);B) = {y | d(y,x) 6 r(q) + 1}.
Therefore S(q,r(q);B) ⊂ H(x,r(x);B)).
Since the H(q,r(q);B) is convex (due to metricity) and the boundary
of H(q,r(q);B) is contained in H(x,r(x);B), all the internal points of
H(q,r(q);B) are contained in H(x,r(x);B).
Hence, H(q,r(q);B) ⊂H(x,r(x);B).
€
The algorithm [127] for the computation of the MAT of images is presented
below:
The above algorithm is presented for any arbitrary dimension. Typical
results of adaptation of these algorithms in 2-D and 3-D are shown in Figs.
6.7 (a)-(c), and Figs. 6.8 (b)-(d), respectively. The variations of the set of
medial points (also called centers of maximal disks (CMD)) are also observed
with the changes of metric space in 2-D and 3-D in those figures. In subsequent
sections, we discuss a few applications of MAT in image processing. We should
also note that the MAT from the EDT is a nontrivial problem. In the Euclidean
space, the extent of the neighborhood for searching the local maxima is not
precise. In [53], a local search method is proposed. In this case, a mapping
