Digitization scheme that assures faithful reconstruction of plane figures. (English) Zbl 1182.68330
Summary: We propose a digitization scheme for a broad class of plane figures. It includes arbitrary polygons (possibly, non-convex and with holes) and plane sets whose boundary consists of smooth curves or straight segments. Our approach is based on an appropriate scaling of the original continuous real object so that the obtained magnified object and its (appropriately constructed) digitization feature analogous geometric properties. As a bi-product of the presented theory we prove the strong NP-hardness of the problem of obtaining an optimal (i.e., with a minimal number of facets) polyhedral reconstruction in which the facets are trapezoids or triangles. This result implies the strong NP-hardness of the general polyhedral reconstruction problem, which was a long-standing open problem. As another major result, we show that the proposed digitization scheme allows faithful reconstruction of plane figures from the considered general class. The reconstructed set features the basic properties of the original object, such as location of curve and straight segments and inflection points of its boundary.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68T10 | Pattern recognition, speech recognition |
Keywords:
digital geometry; lattice polygon; scaling factor; polyhedral reconstruction; NP-hard problem; object reconstructionReferences:
| [1] | E. Andres, Modélization Analytique Discrète d’Objets Géométriques, L’Habilitation a Diriger des Rescherches, Université de Poitiers, 2001.; E. Andres, Modélization Analytique Discrète d’Objets Géométriques, L’Habilitation a Diriger des Rescherches, Université de Poitiers, 2001. |
| [2] | Andres, E., Discrete analytical objects: the standard model, Graphical Models, 65, 1-3, 92-111 (2003) · Zbl 1039.68139 |
| [3] | E. Andres, I. Debled-Renesson, C. Sibata, R. Acharya, K. Shin, Linear contour segmentation and its application to the computation of stereotactic radiosurgery dose distribution, in: SPIE Medical Imaging 1996, vol. 2710, SPIE, New Port Beach, California, USA, 1996.; E. Andres, I. Debled-Renesson, C. Sibata, R. Acharya, K. Shin, Linear contour segmentation and its application to the computation of stereotactic radiosurgery dose distribution, in: SPIE Medical Imaging 1996, vol. 2710, SPIE, New Port Beach, California, USA, 1996. |
| [4] | Asano, Ta.; Asano, Te.; Imai, H., Partitioning a polygonal region into trapezoids, Journal of the ACM, 33, 290-312 (1986) |
| [5] | Bresenham, J. E., Algorithm for computer control of a digital plotter, IBM System Journal, 1, 4, 25-30 (1965) |
| [6] | V.E. Brimkov, Discrete volume polyhedrization: complexity and bounds on performance, in: Tavares, et al. (Eds.), Computational Modelling of Objects Represented in Images: Fundamentals, Methods and Applications, Proceedings of the Internat. Symposium CompIMAGE’06, Coimbra (Portugal), October 21-22, 2006, Taylor & Francis Group Pu., London/Leiden/New York/Philadelphia/Singapore, 2007, pp. 117-122.; V.E. Brimkov, Discrete volume polyhedrization: complexity and bounds on performance, in: Tavares, et al. (Eds.), Computational Modelling of Objects Represented in Images: Fundamentals, Methods and Applications, Proceedings of the Internat. Symposium CompIMAGE’06, Coimbra (Portugal), October 21-22, 2006, Taylor & Francis Group Pu., London/Leiden/New York/Philadelphia/Singapore, 2007, pp. 117-122. |
| [7] | Brimkov, V. E., Scaling of plane figures that assures faithful digitization, (Brimkov, V. E.; Barneva, R. P.; Hauptman, H. A., Combinatorial Image Analysis, Lecture Notes in Computer Science, vol. 4958 (2008), Springer: Springer Berlin), 87-98 |
| [8] | Brimkov, V. E.; Andres, E.; Barneva, R. P., Object discretizations in higher dimensions, Pattern Recognition Letters, 23, 6, 623-636 (2002) · Zbl 1006.68117 |
| [9] | Chaselle, B.; Dobkin, D. P., Decomposing a polygon into its convex parts, (Proceedings of the 11th Annual ACM Symposium on Theory of Computing (1979)), 38-48 |
| [10] | Coeurjolly, D.; Gérard, Y.; Reveillès, J.-P.; Tougne, L., An elementary algorithm for digital arc segmentation, Discrete Applied Mathematics, 139, 31-50 (2004) · Zbl 1077.68107 |
| [11] | Debled-Renesson, I.; Reveillès, J.-P., A linear algorithm for segmentation of digital curves, International Journal of Pattern Recognition and Artificial Intelligence, 9, 4, 635-662 (1995) |
| [12] | De Vieilleville, F.; Lachaud, J.-O.; Feschet, F., Convex digital polygons, maximal digital straight segments and convergence of discrete geometric estimators, Journal of Mathematical Imaging and Vision, 27, 2, 139-156 (2007) · Zbl 1478.68421 |
| [13] | Feschet, F.; Tougne, L., On the min DSS problem of closed discrete curves, Discrete Applied Mathematics, 151, 1-3, 138-153 (2005) · Zbl 1101.68904 |
| [14] | Garey, M.; Johnson, D., Computers and Intractability (1979), W.H. Freeman & Company: W.H. Freeman & Company San Francisco · Zbl 0411.68039 |
| [15] | Hersch, R. D., Descriptive contour fill of partly degenerated shapes, IEEE Computer Graphics and Applications, 6, 7, 61-70 (1986) |
| [16] | Klette, R.; Rosenfeld, A., Digital Geometry—Geometric Methods for Digital Picture Analysis (2004), Morgan Kaufmann: Morgan Kaufmann San Francisco · Zbl 1064.68090 |
| [17] | J.-O. Lachaud, A. Vialard, F. de Vieilleville, Analysis and comparative evaluation of discrete tangent estimators, in: Proceedings of DGCI’05, Lecture Notes in Computer Science, vol. 3429, Springer, Berlin, 2005, pp. 240-251.; J.-O. Lachaud, A. Vialard, F. de Vieilleville, Analysis and comparative evaluation of discrete tangent estimators, in: Proceedings of DGCI’05, Lecture Notes in Computer Science, vol. 3429, Springer, Berlin, 2005, pp. 240-251. · Zbl 1118.68705 |
| [18] | Lachaud, J.-O.; Vialard, A.; de Vieilleville, F., Fast, accurate and convergent tangent estimation on digital contours, Image and Vision Computing, 25, 10, 1572-1587 (2007) |
| [19] | Latecki, L. J.; Conrad, C.; Gross, A., Preserving topology by a digitization process, Journal of Mathematical Imaging and Vision, 8, 2, 131-159 (1998) · Zbl 0895.68138 |
| [20] | Latecki, L. J.; Eckhardt, U.; Rosenfeld, A., Well-composed sets, Computer Vision and Image Understanding, 8, 61-70 (1995) |
| [21] | Latecki, L. J.; Rosenfeld, A., Recovering a polygon from noisy data, Computer Vision and Image Understanding, 86, 1-20 (2002) |
| [22] | A. Lingas, The power of non-rectilinear holes, in: Proceedings of the Ninth International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, vol. 140, Springer, Berlin, 1982, pp. 369-383.; A. Lingas, The power of non-rectilinear holes, in: Proceedings of the Ninth International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, vol. 140, Springer, Berlin, 1982, pp. 369-383. · Zbl 0487.68033 |
| [23] | Pavlidis, T., Scan-conversion of regions bounded by parabolic splines, IEEE Computer Graphics and Applications, 5, 6, 47-53 (1985) |
| [24] | Preparata, F. P.; Shamos, M. I., Computational Geometry: An Introduction (1985), Springer: Springer New York · Zbl 0759.68037 |
| [25] | J.-P. Reveillès, Géométrie discrète, calcul en nombres entiers et algorithmique, Thèse d’État, Univ. Louis Pasteur, Strasbourg, 1991.; J.-P. Reveillès, Géométrie discrète, calcul en nombres entiers et algorithmique, Thèse d’État, Univ. Louis Pasteur, Strasbourg, 1991. · Zbl 1079.51513 |
| [26] | Serra, J., Image Analysis and Mathematical Morphology (1982), Academic Press: Academic Press New York · Zbl 0565.92001 |
| [27] | Stelldinger, P.; Latecki, L. J.; Siqueira, M., 3D object digitization: topological equivalence between a 3D object and the reconstruction of its digital image, IEEE Transactions on Pattern Analysis and Machine Intelligence, 29, 1, 126-140 (2007) |
| [28] | Van Wyk, C. J., Clipping to the boundary of a circular-arc polygon, Computer Vision, Graphics, and Image Processing, 25, 383-392 (1984) |
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.
