A Method for Obtaining Skeletons Using a Quasi-Euclidean Distance

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Method for Obtaining Skeletons Using a Quasi-Euclidean Distance

Full text

Pdf (1.38 MB)

Source

Journal of the ACM (JACM) archive
Volume 15 , Issue 4 (October 1968) table of contents

Pages: 600 - 624

Year of Publication: 1968

ISSN:0004-5411

Author

U. Montanari

Istituto per l'Elaborazione dell' Informazione, Consiglio Nazionale, Ricerche, Pisa, Italy and Politecnico di Milano, Istituto di Elettrotecnica ed Elettronica, Italy

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 79, Citation Count: 30

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321479.321486 What is a DOI?

ABSTRACT

The problem of obtaining the skeleton of a digitized figure is reduced to an optimal policy problem. A hierarchy of methods of defining the skeleton is proposed; in the more complicated ones, the skeleton is relatively invariant under rotation. Two algorithms for computing the skeleton are defined, and the corresponding computer programs are compared. A criterion is proposed for determining the most significant skeleton points.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BLUM, H. A transformation for extracting new descriptors of shape. In Wathen-Dunn, Weiant (Ed.), Symp. on Models for the Perception of Speech and Visual Form (Boston, Nov. 1964), M.I.T. Press, Cambridge, Mass.
	2	KoTELLY, J. A mathematical model of Blum's theory of pattern recoguition. Air Force Cambridge Res. Labs. Res. Rep. 63-164, April 1963 (AD 412437).
	3	CALABI , L. On the shape of plane figures. Air Force Cambridge IZles. labs. Res. Rep. St-1-60429, March 1965.
	4	----. A study of the skeleton of plane figures. Air Force Cambridge Res. Labs. Res. Rep. SR-2-60429, June 1965.
	5	Azriel Rosenfeld , John L. Pfaltz, Sequential Operations in Digital Picture Processing, Journal of the ACM (JACM), v.13 n.4, p.471-494, Oct. 1966 [doi>10.1145/321356.321357]
	6	John L. Pfaltz , Azriel Rosenfeld, Computer representation of planar regions by their skeletons, Communications of the ACM, v.10 n.2, p.119-122, Feb. 1967 [doi>10.1145/363067.363120]
	7	RAnESacHEa, H. Lectures on EIme'ntary Number Theory. B1Msdell, New York, 1964.
	8	Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
	9	BIONDI, E., DEFENEDER A., AND LUCCIO F. Cammini ottilni. In identificazione e otiimizzazioTe: Problemi e metodi, Collana di automatica, Vol. 2, Consiglio Nazionale delle Ricerehe, toma, 1967.
	10	LUCCIO, F. On some iterative methods for the determination of optimal paths through a network. CalcoZo 8, Fasc. 1 (1966), 31-48.
	11	LEDLEY, R. S. High-speed automatic analysis of biomedical pictures. Science 13 (1964), 219--233.

CITED BY 30

	Stanley M. Selkow, One-Pass Complexity of Digital Picture Properties, Journal of the ACM (JACM), v.19 n.2, p.283-295, April 1972
	Martin Rumpf , Alexandru Telea, A continuous skeletonization method based on level sets, Proceedings of the symposium on Data Visualisation 2002, May 27-29, 2002, Barcelona, Spain
	Louis Hodes, A programming system for the on-line analysis of biomedical images, Communications of the ACM, v.13 n.5, p.279-283, May 1970
	A. L. Fisher, Scan line array processors for image computation, ACM SIGARCH Computer Architecture News, v.14 n.2, p.338-345, June 1986
	R. Stefanelli , A. Rosenfeld, Some Parallel Thinning Algorithms for Digital Pictures, Journal of the ACM (JACM), v.18 n.2, p.255-264, April 1971
	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991
	Ugo Montanari, Continuous Skeletons from Digitized Images, Journal of the ACM (JACM), v.16 n.4, p.534-549, Oct. 1969
	Stina Svensson , Gunilla Borgefors, Digital distance transforms in 3D images using information from neighbourhoods up to 5 × 5 × 5, Computer Vision and Image Understanding, v.88 n.1, p.24-53, October 2002
	Azriel Rosenfeld, Picture Processing by Computer, ACM Computing Surveys (CSUR), v.1 n.3, p.147-176, Sept. 1969
	Sung Woo Choi , Hans-Peter Seidel, Linear onesided stability of MAT for weakly injective 3D domain, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
	Reinhard Klette , Azriel Rosenfeld, Digital straightness: a review, Discrete Applied Mathematics, v.139 n.1-3, p.197-230, 30 April 2004
	Frédéric Leymarie , Martin D. Levine, Simulating the Grassfire Transform Using an Active Contour Model, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.1, p.56-75, January 1992
	M. Milgram , T. de Saint Pierre, Boundary Detection and Skeletonization with a Massively Parallel Architecture, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.1, p.74-78, January 1990
	P.-O. Forsgren , P. Seideman, An Interobject Distance Measure Based on Medial Axes Retrieved from Discrete Distance Maps, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.4, p.390-397, April 1990
	George J. Grevera, The "Dead reckoning" signed distance transform, Computer Vision and Image Understanding, v.95 n.3, p.317-333, September 2004
	F. Chazal , R. Soufflet, Stability and Finiteness Properties of Medial Axis and Skeleton, Journal of Dynamical and Control Systems, v.10 n.2, p.149-170, April 2004
	Afonso Ferreira , Stéphane Ubéda, Computing the Medial Axis Transform in Parallel With Eight Scan Operations, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.3, p.277-282, March 1999
	Hüseyin Tek , Benjamin B. Kimia, Symmetry Maps of Free-Form Curve Segments via Wave Propagation, International Journal of Computer Vision, v.54 n.1-3, p.35-81, August-September 2003
	Sung Woo Choi , Hans-Peter Seidel, Linear One-Sided Stability of MAT for Weakly Injective Domain, Journal of Mathematical Imaging and Vision, v.17 n.3, p.237-247, November 2002
	Guodong Rong , Tiow-Seng Tan, Jump flooding in GPU with applications to Voronoi diagram and distance transform, Proceedings of the 2006 symposium on Interactive 3D graphics and games, March 14-17, 2006, Redwood City, California
	Gisela Klette, A comparative discussion of distance transforms and simple deformations in digital image processing, Machine Graphics & Vision International Journal, v.12 n.2, p.235-256, February 2003
	Xiaoli Wang , Gilles Bertrand, Some Sequential Algorithms for a Generalized Distance Transformation Based on Minkowski Operations, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.11, p.1114-1121, November 1992
	Hüseyin Tek , Benjamin B. Kimia, Boundary Smoothing via Symmetry Transforms, Journal of Mathematical Imaging and Vision, v.14 n.3, p.211-223, May 2001
	Robin Strand, Weighted distances based on neighbourhood sequences, Pattern Recognition Letters, v.28 n.15, p.2029-2036, November, 2007
	Weiguang Guan , Songde Ma, A List-Processing Approach to Compute Voronoi Diagrams and the Euclidean Distance Transform, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.7, p.757-761, July 1998
	Shigehiro Fukushima, Division-Based Analysis of Symmetry and Its Application, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.2, p.144-148, February 1997
	Robin Strand, Weighted distances based on neighborhood sequences for point-lattices, Discrete Applied Mathematics, v.157 n.4, p.641-652, February, 2009
	Ricardo Fabbri , Luciano Da F. Costa , Julio C. Torelli , Odemir M. Bruno, 2D Euclidean distance transform algorithms: A comparative survey, ACM Computing Surveys (CSUR), v.40 n.1, p.1-44, February 2008
	Nicolas Normand , Pierre Evenou, Medial axis lookup table and test neighborhood computation for 3D chamfer norms, Pattern Recognition, v.42 n.10, p.2288-2296, October, 2009
	R. S. Rosenberg , P. F. Rowat, Spatial problems for a simulated robot, Proceedings of the 7th international joint conference on Artificial intelligence, p.758-765, August 24-28, 1981, Vancouver, BC, Canada