Abstract
Skeleton representation of an object is a powerful shape descriptor that captures both boundary and region information of the object. The skeleton of a shape is a representation composed of idealized thin lines that preserve the connectivity or topology of the original shape. Although the literature contains a large number of skeletonisation algorithms, many open problems remain. In this paper, we present a new skeletonisation approach that relies on the Electrostatic Field Theory (EFT). Many problems associated with existing skeletonisation algorithms are solved using the proposed approach. In particular, connectivity, thinness and other desirable features of a skeleton are guaranteed. It also captures notions of corner detection, multiple scale, thinning, and skeletonisation all within one unified framework. The performance of the proposed EFT-based algorithm is studied extensively. Using the Hausdorf distance measure, the noise sensitivity of the algorithm is compared to two existing skeletonisation techniques. In addition, the experimental results also demonstrate the multiscale property of the proposed approach.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Maya N, Rajan VT. An efficient shape representation scheme using Voronoi skeletons. Pattern Recognition Letters 1995; 16: 147–160
Mokhtarian F, Mackworth AK, Scale-based description and recognition of planar curves and two-dimensional shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence 1986; 8(1): 34–43
Mokhtarian F, Mackworth AK. A theory of multiscale, curvature-based shape representation for planar curves. IEEE Transactions on Pattem Analysis and Machine Intelligence 1992; 14(8): 789–805
Blum H. A transformation for extracting new descriptors of shape. In Models fortthe Perception of Speech and Visual Form, Wathen-Dunn W. (ed). MIT Press, 1967
Vega OE, Yang YH. Default shape theory: with application to the computation of the direction of the light source, CVGIP: Image Understanding 1994; 60(3): 285–299
Lam L, Suen CY. Automatic evaluation of skeleton shapes. Proceedings 11th International Conference on Pattern Recognition, The Hague, The Netherlands 1992; 342–345
Lee SW, Lam L, Suen CY. Performance evaluation of skeletonization algorithms for document image processing. Proceedings 1st International Conference on Document Analysis and Recognition, St. Malo, France 1991; 260–271
Plamondon R, Suen CY. On the definition of reference skeletons for comparing thinning algorithms. Proceedings Vision Interface 1988, Edmonton, Canada, 1988; 70–75
Jaisimha MY, Haralick RM. A methodology for the characterization of the performance of thinning algorithms. Proceedings 2nd International Conference on Document Analysis and Recognition, Tsukuba, Japan 1993; 282–286
Haralick RM. Performance characterization in image analysis: thinning, a case in point. Pattern Recognition Letter 1992; 13: 5–12
Leymarie F, Levine MD. Simulating the grassfire transform using an active contour model. IEEE Transactions on Pattern Analysis and Machine Intelligence 1992; 14(1): 56–75
Abdel-Hamid, GH, Yang, YH. Electrostatic field-based detection of corners of planar curves. Proceedings of the 1993 Canadian Conference on Electrical and Computer Engineering, Vancouver, Canada 1993; 767–770
Shin FY, Mitchell OR. A mathematical morphology approach to Euclidean distance transformation. IEEE Transactions on Image Processing 1992; 1(2): 197–204
Arumugam A, Radhakrishnan T, Suen CY. A thinning algorithm based on the force between charged particles. International Journal of Pattern Recognition and Artificial Intelligence 1993; 7(5): 988–1008
Smith RW. Computer processing of line images: A survey. Pattern Recognition 1987; 20(1): 7–15
Lam L, Lee SW, Suen CY. Thinning methodologies-a comprehensive survey. IEEE Transactions on Pattern Analysis and Machine Intelligence 1992; 14(9): 869–885
Dill AR, Levine MD, Noble PB. Multiple resolution skeletons. IEEE Transactions on Pattern Analysis and Machine Intelligence 1987; 9: 495–504
Guo Z, Hall RW. Fast fully parallel thinning algorithms. CVGIP: Image Understanding 1992; 55(3): 317–328
Arcelli C. Pattern thinning by contour tracing. Computer Graphics Image Processing 1981; 17: 130–144
Martinez-Perez MP, Jimenez J, Navalon JL. A thinning algorithm based on contours. Computer Graphics and Image Processing 1987; 39: 186–201
Shapiro B, Pisa J, Sklansky J. Skeleton generation from x, y boundary sequences. Computer Graphics and Image Proceesing 1981; 15: 136–153
Brandt JW, Algazi VR. Continuous skeleton computation by Voronoi diagram. CVGIP: Image Understanding 1992; 55(3): 329–338
Ogniewicz R, Ilg M. Voronoi skeletons: theory and applications. Proceedings IEEE Conference on Computer Vision and Pattern Recognition, Champaign, IL, 1992; 63–69
Aurenhammer F. Voronoi diagrams: A survey of a fundamental geometric data. ACM Computing Surveys 1991; 23: 345–504
Arcelli C, Sanniti di Baja G. A one-pass two-operations process to detect the skeletal pixels on the 4-distance transform. IEEE Transactions on Pattern Analysis and Machine Intelligence 1989; 4: 411–414
Arcelli C, Sanniti di Baja G. A width independent fast thinning algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence 1985; 7: 463–474
Klein F, Kubler O. Euclidean distance transformation and model guided image interpretation. Pattern Recognition Letters 1987; 3: 19–30
Gauch J, Pizer S.. The intensity axis of symmetry and its application to image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 1992; 15(8): 753–770
Danielsson PE. Euclidean distance mapping. Computer Graphics and Image Processing 1980; 14: 227–248
Leymarie F. Tracking and describing deformable objects using active contour models. MSc thesis, McGill University, Montreal, Quebec, Canada, 1990
Ahuja N, Chuang JH. Shape representation using a generalized potential field model. IEEE Transactions on Pattern Analysis and Machine Intelligence 1997; 19: 169–176
Nussbaum A. Field Theory. Charles E. Merrill Books, 1967
Silvester P. Modem Electromagnetic Fields. Prentice-Hall, 1967
Mittra R, Lee SW. Analytical Techniques in The Theory of Guided Waves. McMillan, 1971; 4–11
Fuller AJB. Engineering Field Theory. Pergamon Press, 1973
Shin FY, Pu CC. A skeletonization algorithm by maxima tracking on Euclidean distance transform. Pattern Recognition 1995; 28(3): 331–341
Khoros, Krohos Research Inc., 1994
Pavlidis T. An asynchronous thinning algorithm. Computer Graphics and Image Processing 1982; 20: 133–157
Giardina CR, Dougherty E, Morphological Methods in Image and Signal Processing. Prentice-Hall, 1988
Haralick RM, Shapiro LG, Computer and Robot Vision. Addison-Wesley, 1992
Piech MA. Comment on fingerprints of two-dimensional edge models. Computer Vision, Graphics and Image Processing 1988; 42: 381–386
Nguyen T, Sklansky J. Reconstructing the 3-D medical axes of coronary arteries in single-view cineangiograms. IEEE Transactions on Medical Imaging 1994; 13(1): 61–73
Grigorishin T, Yang YH. Image segmentation: An electrostatic field based approach. Vision Interface 98, Vancouver, BC, June 18–20 1998
Grigorishin T, Yang YH. Form segmentation: An electrostatic field based approach. Technical Report, Department of Computer Sciences, University of Saskatchewan, 1997
Author information
Authors and Affiliations
Corresponding author
Additional information
Gamal Abdel-Hamid passed away on December 4 1994. Grigorishin and Yang would like to dedicate this paper in memory of Abdel-Hamid.
The aurthors would like to acknowledge financial support provided by NSERC through grant number OGP0000370.
Rights and permissions
About this article
Cite this article
Grigorishin, T., Abdel-Hamid, G. & Yang, Y.H. Skeletonisation: An electrostatic field-based approach. Pattern Analysis & Applic 1, 163–177 (1998). https://doi.org/10.1007/BF01259366
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01259366