Finding a minimum medial axis of a discrete shape is NP-hard. (English) Zbl 1160.68040
Summary: The medial axis is a classical representation of digital objects widely used in many applications. However, such a set of balls may not be optimal: subsets of the medial axis may exist without changing the reversivility of the input shape representation. In this article, we first prove that finding a minimum medial axis is an NP-hard problem for the Euclidean distance. Then, we compare two algorithms which compute an approximation of the minimum medial axis, one of them providing bounded approximation results.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68W25 | Approximation algorithms |
References:
| [1] | L.J. Aupperle, H.E. Conn, J.M. Keil, J. O’Rourke, Covering orthogonal polygons with squares, in: Proceedings of the 26th Annual Allerton Conf. Comm. Control Comput., 1988, pp. 97-106; L.J. Aupperle, H.E. Conn, J.M. Keil, J. O’Rourke, Covering orthogonal polygons with squares, in: Proceedings of the 26th Annual Allerton Conf. Comm. Control Comput., 1988, pp. 97-106 |
| [2] | Blum, H., A transformation for extracting new descriptors of shape, (Wathen-Dunn, W., Models for the Perception of Speech and Visual Form (1967), MIT Press: MIT Press Cambridge), 362-380 |
| [3] | Borgefors, G., Distance transformations in arbitrary dimensions, Computer Vision, Graphics and Image Processing, 27, 321-345 (1984) |
| [4] | Borgefors, G., Distance transformations in digital images, Computer Vision, Graphics, and Image Processing, 34, 3, 344-371 (1986) |
| [5] | G. Borgefors, I. Nyström, Quantitative shape analysis of volume images — reducing the set of centres of maximal spheres, in: Proc. SSAB Symposium on Image Analysis, Linköping, Sweden, 1995, pp. 5-8; G. Borgefors, I. Nyström, Quantitative shape analysis of volume images — reducing the set of centres of maximal spheres, in: Proc. SSAB Symposium on Image Analysis, Linköping, Sweden, 1995, pp. 5-8 |
| [6] | Borgefors, G.; Nyström, I., Efficient shape representation by minimizing the set of centers of maximal discs/spheres, Pattern Recognition Letters, 18, 465-472 (1997) |
| [7] | Breu, H.; Gil, J.; Kirkpatrick, D.; Werman, M., Linear time euclidean distance transform algorithms, IEEE Transactions on Pattern Analysis and Machine Intelligence, 17, 5, 529-533 (1995) |
| [8] | Coeurjolly, D.; Montanvert, A., Optimal separable algorithms to compute the reverse euclidean distance transformation and discrete medial axis in arbitrary dimension, IEEE Transactions on Pattern Analysis and Machine Intelligence, 29, 3, 437-448 (2007) |
| [9] | Cormen, T.; Leiserson, C.; Rivest, R., Introduction to Algorithms (1990), MIT Press · Zbl 1158.68538 |
| [10] | (Goodman, J. E.; O’Rourke, J., Handbook of Discrete and Computational Geometry (1997), CRC Press) · Zbl 0890.52001 |
| [11] | Hirata, T., A unified linear-time algorithm for computing distance maps, Information Processing Letters, 58, 3, 129-133 (1996) · Zbl 1023.68681 |
| [12] | Jansen, K.; Müller, H., The minimum broadcast time problem for several processor networks, Theoretical Computer Science, 147, 1-2, 69-85 (1995) · Zbl 0873.68009 |
| [13] | Nilsson, F.; Danielsson, P.-E., Finding the minimal set of maximum disks for binary objects, Graphical models and image processing, 59, 1, 55-60 (1997) |
| [14] | Pfaltz, J. L.; Rosenfeld, A., Computer representation of planar regions by their skeletons, Communications of ACM, 10, 119-125 (1967) |
| [15] | I. Ragnemalm, G. Borgefors, The Euclidean Distance Transform,, chapter Towards a minimal shape representation using maximal discs, Linköping Studies in Science and Technology. Dissertations No. 304., Linköping University, apr 1993, pp. 245-260; I. Ragnemalm, G. Borgefors, The Euclidean Distance Transform,, chapter Towards a minimal shape representation using maximal discs, Linköping Studies in Science and Technology. Dissertations No. 304., Linköping University, apr 1993, pp. 245-260 |
| [16] | Remy, E.; Thiel, E., Medial axis for chamfer distances: computing look-up tables and neighbourhoods in 2D or 3D, Pattern Recognition Letters, 23, 6, 649-661 (2002) · Zbl 1006.68140 |
| [17] | Remy, E.; Thiel, E., Exact Medial Axis with Euclidean Distance, Image and Vision Computing, 23, 2, 167-175 (2005) |
| [18] | Rosenfeld, A.; Pfaltz, J. L., Sequential operations in digital picture processing, Journal of the ACM, 13, 4, 471-494 (1966) · Zbl 0143.41803 |
| [19] | Saito, T.; Toriwaki, J.-I., Reverse distance transformation and skeletons based upon the euclidean metric for \(n\)-dimensional digital pictures, IECE Transactions on Informations & Systems, E77-D, 9, 1005-1016 (1994) |
| [20] | Tamassia, R., On embedding a graph in the grid with the minimum number of bends, SIAM Journal of Computing, 16, 3, 421-444 (1987) · Zbl 0654.68090 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
