Image Processing Reference
In-Depth Information
Chapter 6
Medial Axis Transform
6.1
Distance Transform .............................................. 190
6.1.1
Distance Transform through Iterative Scan ............. 190
6.1.2
Chamfering Algorithm ................................... 191
6.1.2.1
Designing Masks ........................... 192
6.1.3
Forward and Reverse Scans ............................. 192
6.1.4
Euclidean Distance Transform .......................... 193
6.2
Medial Axis Transform (MAT) ................................. 196
6.2.1
MAT from the Distance Transform ..................... 197
6.2.2
Reduced Centers of Maximal Disks (RCMD) ........... 198
6.3
Skeletonization Using MAT ...................................... 200
6.4
Geometric Transformation ....................................... 203
6.4.1
Approximate Transformation by Euclidean Disks ...... 204
6.5
Computation of Normals at Boundary Points of 2-D Objects .. 205
6.5.1
Algorithm for Normal Computation .................... 206
6.5.2
Use of Octagonal Distances ............................. 206
6.5.3
Quality of Computation ................................. 208
6.6
Computation of Cross-Sections of 3-D Objects .................. 212
6.6.1
Computation with MAT ................................. 215
6.6.2
The Algorithm ........................................... 216
6.6.3
Using Euclidean Approximation ......................... 218
6.7
Shading of 3-D Objects .......................................... 219
6.8
Summary ......................................................... 220
Exercises ......................................................... 222
The Medial Axis Transform (MAT) [21] is an attractive representation scheme
for spatial occupancy of objects in 2-D and 3-D. In its lowest form, an object is
represented as a set of points in an integral coordinate space that it occupies.
We know that a point in this form of representation is called pixel in 2-D and
voxel in 3-D. The MAT of these objects provides a relatively higher level of
structural description, as it represents the object as a set of disks (circles in
2-D and spheres in 3-D). To reduce the number of such circles (or spheres), in
this representation, only those are considered that are not totally contained
in any one of them. These are called medial disks (or centers of maximal disks
(CMD)) of the pattern or object. However, even with these medial disks, there
is a scope of redundancy in the set. The disks may be overlapping. Moreover a
medial disk may be contained by more than one member from the remaining
189
