Digitization scheme that assures faithful reconstruction of plane figures
Digitization scheme that assures faithful reconstruction of plane figures
复制标题
确保平面图形忠实重建的数字化方案
DOI：
10.1016/j.patcog.2008.12.002
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
V. Brimkov
中科院分区：
文献类型：
--
作者：
V. Brimkov
在目前广泛的工作中，我们提出了一个数字化计划的一个广泛的类的平面图形。它包括任意多边形（可能是非凸的和有洞的）和边界由光滑曲线或直线段组成的平面集。我们的方法是基于一个适当的缩放原始连续的真实的对象，使获得的放大对象和它的（适当构造）数字化功能类似的几何属性。作为所提出的理论的双产品，我们证明了获得最优（即，具有最小数目的小平面）多面体重建，其中小平面是长方体或三角形。这一结果暗示了一般多面体重构问题的强NP-困难性，这是一个长期存在的公开问题。作为另一个主要的结果，我们表明，建议的数字化方案，可以忠实地重建所考虑的一般类的平面图形。重建集反映了原始物体的基本属性，如曲线段、直线段的位置以及边界的拐点。
In the present extensive work, 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.