A comparative discussion of distance transforms and simple deformations in digital image processing

• Autorzy: Klette G.
• Języki publikacji: EN

Abstrakty

EN

The paper discusses algorithms for extracting essential properties of binary objects in digital images which are either based on distance transforms defined by different metrics or algorithms based on simple shape deformations. Thinning algorithms define one-way simple deformations. Two-way simple deformations transfer object points into background points and vice versa, without destroying the image topology. This article reviews contributions in this area with respect to properties of algorithms and characterizations of simple points, and informs about a few new results. A main intention of this article is the comparative discussion of experimental results and theoretical equivalences.

Słowa kluczowe

EN

shape simplification; skeletonization; thinning; distance transform

• Wydawca: Institute of Information Technology of the Warsaw University of Life Sciences – SGGW
• Czasopismo: Machine Graphics and Vision
• Rocznik: 2003
• Tom: Vol. 12, No. 2
• Strony: 235--256
• Opis fizyczny: Bibliogr. 28 poz, rys., tab.

Twórcy

autor

Klette G.

• CITR Tamaki, University of Auckland, Tamaki Campus, Building 731, Auckland, New Zealand

Bibliografia

• [1] Listing J. B.: Der Census räumlicher Complexe oder Verallgemeinerungen des Euler'schen Satzes von den Polyëdern. Abhandlungen der Mathematischen Classe der Königlichen Gesellschaft der Wissenschaften zu Göttingen, 10, 97-182. 1862.
• [2] Rosenfeld A., Pfaltz J. L.: Sequential operations in digital picture processing. Comm. ACM, 13, 471-494. 1966.
• [3] Blum H.: A transformation for extracting new descriptors of shape. Models for the Perception of Speech and Visual Form, Wathen-Dunn W.(Ed.), MIT Press, Cambridge, Mass., 362-380. 1967.
• [4] Pfaltz J. L., Rosenfeld A.: Computer representation of planar regions by their skeletons. Comm. ACM, 10, 119-122. 1966.
• [5] Montanari U.: A method of obtaining skeletons using a quasi-Euclidean distance. Comm. ACM, 15, 600-624. 1968.
• [6] Hilditch C. J.: Linear skeletons from square cupboards. Machine Intelligence, 4, (Meltzer B., Mitchie D., Eds.), Edinburgh University Press, 403-420. 1968.
• [7] Rosenfeld A.: Connectivity in digital pictures . Comm. ACM, 17, 146- 60. 1970.
• [8] Rosenfeld A.: Adjacency in digital pictures. Information and Control, 26, 24-33. 1974.
• [9] Arcelli C., Cordella L., Levialdi S.: Parallel thinning of binary pictures. Electron. Lett., ll, 148-149. 1975.
• [10] Rosenfeld A.: A characterization of parallel thinning algorithms. Information and Control, 29, 286-291. 1975.
• [11] Yokoi S., Toriwaki J. I., Fukumura T.: An analysis of topological properties of digitized binary pictures using local features. CGIP, 4, 63-73. 1975.
• [12] Pavlidis T.: A thinning algorithm for discrete binary images. CGIP, 13, 142-157. 1980.
• [13] Serra J.: Image Analysis and Mathematical Morphology. 2, AP, NY. 1982.
• [14] Zhang T. Y., Suen C. Y.: A fast parallel algorithm for thinning digital patterns. Comm. ACM, 27, 236-239. 1984.
• [15] Ronse C.: A topological characterization of thinning. Theoretical Computer Science, 43, 31-41. 1986.
• [16] Hall R.W.: Fast parallel thinning algorithms: parallel speed and connectivity preservation. Comm. ACM, 32, 124-131. 1989.
• [17] Lam L., Lee S., Suen C.: Thinning methodologies - a comprehensive survey. IEEE PAMI, 14, 869-885. 1992.
• [18] Sanniti di Baja G.: Well-shaped, stable and reversible skeletons from the (3,4)-distance transform. J. Visual Comm. Image Repres, 5, 107-115. 1994.
• [19] Kong T. Y.: On topology preservation in 2-D and 3-D thinning. Int. J. for Pattern Recognition and Artificial Intelligence, 9(5), 813-844. 1995.
• [20] Latecki L., Eckhardt U., Rosenfeld A.: Well-composed sets. CVIU, 61, 70-83. 1995.
• [21] Arcelli C., Sanniti di Baja G.: Skeletons of planar patterns. Topological Algorithms for Digital Image Processing, Kong T. Y., Rosenfeld A. (Eds .), North-Holland, 99-143. 1996.
• [22] Hall R.W.: Parallel Connectivity-Preserving Thinning Algorithms. Topological Algorithms for Digital Image Processing, (Kong T. Y., Rosenfeld A., Eds.), Elsevier Science B. V. 145-179. 1996.
• [23] Rutovitz D.: Pattern recognition. J. Royal Statist. Soc., 129, 504-530. 1996.
• [24] Rosenfeld A., Kong T. Y., Nakamura A.: Topology-preserving deformations of two-valued digital pictures. GMIP, 60, 24-34.1998.
• [25] Kovalevsky V.: Algorithms and data structures for computer topology. t Digital and Image Geometry, (G. Bertrand, A. Imiya, R. Klette, Eds.), LNCS, 2243, Springer, Berlin Heidelberg, 38-58. 2001.
• [26] Gonzalez R. C., Woods R. E.: Digital Image Processing. Prentice-Hall, Inc., Upper Saddle River, New Jersey, 519-566. 2002
• [27] Klette G.: Characterizations of Simple Pixels in Binary Images. Proc. Image and Vision Computing New Zealand, 227-232. 2002.
• [28] Rosenfeld A., Klette R.: Topologies for binary or multi-level images - A review. Keynote, 6th Joint Conf. Inform. Sciences, March 8-13, Research Triangle Park, North Carolina, (to appear).