工程物体线图的计算机解释new

工程物体线图的计算机解释储珺收稿日期：2006-3 基金项目：江西省自然科学基金(0311018),南昌航空工业学院测试技术与控制工程研究中心基金（2003-013）作者简介：储珺(1967-)，中国科学院国家天文台月球与深空探测科学应用中心博士后，南昌航空工业学院副教授，主要从事计算机图形图像研究。,2，高满屯3，鲁宇明1，徐卫平1(1. 南昌航空工业学院，江西 南昌 330034；2. 中科院国家天文台 北京 1001013. 西北工业大学, 陕西 西安 710072)摘要：在Sugihara方法的基础上提出一种计算机自动解释工程物体线图的迭代方法。该方法根据线图中隐含的几何元素间的约束关系，从有误差的工程物体画隐线图恢复平面立体的三维参数，并对画隐线图中有误差的节点位置进行校正，使得修正后的线图是一个工程物体的投影线图，并且尽量和原输入线图一致。实验结果表明该方法是有效的。关键词：线图，迭代，解释中图法分类号:TP391.4文献标识码: A0 引言计算机自动解释线图是计算机视觉和智能CAD系统的一个重要问题。尽管计算机辅助设计系统得到了迅速的发展，但在产品设计阶段，设计人员更倾向用手工草图来描述物体1，特别是在产品设计的初级阶段，即概念设计阶段。因此从工程物体单幅草图重建物体的三维信息是非常必要的。人理解一幅场景的投影草图非常容易，有许多证据证明2,3人类理解线图的这种能力是可以学习和模拟的。所以如果把这种人类理解线图的能力转换为计算机的算法，则计算机就能够像人类一样，可以自动地解释工程物体的线图。文献4,5,6介绍了早期关于计算机解释线图的研究状况，Wang6描述和评估了计算机解释线图的17种方法。计算机解释线图按求解方法可分成线性系统方法、优化方法、梯度空间方法等几种。线性系统方法4,7-9是线图解释的主要方法。Sugihara4提出的代数方法就是一种线性系统方法，算法主要依据平面立体上顶点与平面间的从属关系建立一个线性系统，把判别线图正确性问题降低为检查一个线性等式与不等式解的存在性问题，从理论上解决了判定线图正确与否的问题。 Sugihara算法的缺点是约束条件太过严格，线图中顶点的位置只要有一点微小的扰动，就会得出线图是不正确的结果。但在实际问题中，由于环境中噪声的干扰，所输入的线图都不可避免地存在误差。本文在Sugihara算法的基础上进行改进，提出一种解释有误差线图的迭代方法。该方法可以从有误差画隐线图恢复工程物体的三维模型，并能够对线图中有误差的节点进行校正。假设本文线图是工程物体的正轴测投影，在线图中工程物体不可见轮廓的投影用虚线表示。算法要求工程物体顶点的投影对应于线图中的节点，棱边的投影对应于线图中的直线段，物体上平面的投影对应于线图中的区域。1 线图的约束给定一幅工程物体的投影线图，线图的平面结构和空间结构10分别为和。在一幅画隐线图的完整平面结构D中，V是线图中节点的集合，每一个节点都是平面立体上一个顶点的投影。F是线图中区域的集合，这些区域的边线可以是实线、虚线或者既有实线又有虚线，识别了面后，它们就是线图中面的集合，每一个面都是平面立体上一个平面的投影。是从V到的映射，表示的位置即节点v的坐标参数。表示的是线图中面与节点的从属关系，是有序的一对F和V的元素集合，的元素表示节点是在面的边界上。H表示直线段的类型，即标记线段的8种情况：线段的虚实及（，）。从线图的平面结构可以推出线图的空间结构，在线图的空间结构中，是平面立体上顶点的集合，的元素是顶点坐标；线图空间结构中的和线图平面结构中的满足点的投影方程。是平面立体上表面的集合，的元素是平面参数；是顶点和平面的从属关系，表示顶点在平面上。是有序的3元的集合，其中, ，。在正轴测投影下，平面立体上的平面不能平行于Z轴，所以平面fj的方程可写为： 设，的元素表示顶点位于平面上，因而有：利用点的正轴测投影方程：，上式可写为： (1)每一个的元素可以提供一个方程，将所有这些方程联立起来，就可获得一个线性方程组： (2)其中，是一个大小为的常数矩阵。从CVF的元素可得： (3a)从CVF的元素可得： (3b)每一个CVF的元素可以提供上述两种不等式中的一个，把所有这些不等式联立起来可得一个线性不等式组： (4)其中是一个大小为的常数矩阵。定理1：一幅有一致标记的画隐线图平面结构为，空间结构为，则它是一个平面立体的正轴测投影，当且仅当由方程组(2)和不等式组(4)组成的线性系统有解。该定理的证明见文献4。2过约束问题根据定理1，定量恢复画隐线图D所对应的平面立体实际上就是求解向量W，使得W满足方程组(2)和(4)。因方程组(2)和(4)中已知的A和B是画隐线图上节点的坐标，故当节点的位置有误差时，就可能导致方程组(2)和(4)无解。但是有这样一些线图，当节点位置随意变动时，对应的方程组(2)和(4)仍可有解，例如图1(a)中所示的线图，当节点V1,V2,V3,V4变动时，并不影响方程组(2)和(4)解的存在，这类线图称为位置自由的。显然图1(b)中的线图不是位置自由的。(a) (b) (c)图1 过约束问题位置自由的线图对噪声不敏感，当线图有误差时，不影响求解过程。非位置自由的线图对噪声敏感，其原因主要是这类线图中关联结构过多，即FV中元素过多，相互制约了顶点和棱线的位置和方向。FV中一个关系对应方程组AW0中的一个方程，矩阵A的大小为，当FV中元素过多时，系数矩阵A的行向量就过多，而A中各行向量的系数是线图上对应节点的坐标，若线图上节点存在误差，则引起A中行向量的系数变化，使得线性相关的行向量变为线性无关，导致方程组AW0无解。Sugihara提出从FV中删除一些关系。设余下的关系组成集合，令是一新的平面结构，其中分别为可见顶点和可见平面的子集，中顶点和中平面的关系包含在中。设顶点集和平面集对应的线图为，是D的一个子图。若是位置自由的，将由建立的方程组设为，则方程组可解。求方程组的解，将结果扩充到原线图D上。如何在FV中找到一个最大子集，使得所对应的线图是位置自由的？Sugihara给出一个定理：定理2：设是画隐线图的一个平面结构，若它所对应的平面立体上任意3个共顶点的平面都没有一条公共交线，则是位置自由的，当且仅当对于任何有其中是X中顶点集，是X中点面关系集。该定理的证明见4。如1(b)所示画隐线图，设其平面结构为，从线图中删去平面上的顶点，即取。据定理2，删除后的子图位置自由，求解所对应的方程组和不等式组获得平面参数。由平面,和求解顶点的校正点及属于它的棱线，如图1(c)所示的虚线部分。但对节点和线段较多的线图，要从FV中找到一个最大子集，并使得所对应的线图是位置自由的，这不是一件容易的事情，为此本文提出一种迭代算法来解决线图中的这种过约束问题。3有误差线图解释的迭代方法方程组(2)是一个超定齐次线性方程组，当输入的画隐线图存在误差时，它只有零解，因此利用方程组(2)不能从有误差画隐线图恢复平面立体的三维结构参数（包括顶点坐标和平面参数）。基于点面关系从单幅画隐线图恢复平面立体的自由度最少为4。设画隐线图的自由度为k，当给出平面立体的k个独立参数后，可以将齐次线性方程组(2)转化为非齐次线性方程组： (5)求上述线性方程组的最小二乘解：与给出的平面立体k个独立参数组合为W，W包含恢复的平面立体所有结构参数（包括平面立体上顶点z坐标和平面坐标A,B,C）。当线图存在误差时，不是线性方程组(5)的精确解，只是一个最优解，以W为参数的顶点和平面不能构成一个正确的平面立体。为了解决这个问题，本文采用一种迭代方法逐步校正线图中的误差，使校正后的线图是一个平面立体的正确投影，并且尽可能与原输入线图一致。设平面立体上属于顶点有个平面：，顶点应位于这个平面上。当线图存在误差时，从W和线图节点得到的顶点将不满足这个平面的方程。本文采用最小二乘法从这个平面方程求出顶点的新坐标，把投影回投影面得新投影，将新投影与旧投影进行加权平均，作为下次迭代的节点坐标：其中m为迭代次数。设在平面上有m个顶点，拟合这m个顶点获得一个新平面。以平面参数建立一个三维空间，称为对偶空间。根据对偶原理，设平面，在对偶空间的对应点分别为和。若线图中节点的位置没有误差，则在对偶空间中点与应是重合的；但若线图中节点的位置存在误差，则在对偶空间中点与将不重合。为此定义函数为迭代终止目标函数，当函数的值小于给定的阈值时，迭代终止。画隐线图的外围轮廓线确定了场景中物体的大致范围，在边缘提取过程中误差也较小，因此本文主要校正画隐线图中内部节点的位置。4 实验实验1为了验证算法的有效性，我们对一幅工程物体的正确投影线图（如图2(a)所示）加高斯噪声。因为物体的灰度图像外部轮廓处灰度变化比较大，所以在边缘提取的过程中外部轮廓位置比较准确。对物体的投影画隐线图加高斯噪声时只对线图内部节点坐标加入高斯噪声(0,5)，加噪后的画隐线图如图2(b)所示。将图2(b)看作是一幅正轴测投影画隐线图时，用迭代方法恢复的平面立体如图2(c)所示，无误差线图（蓝色细线条）、恢复的平面立体重投影线图（红色粗线条）和加噪后线图（黑色中粗线条）同时画在图2(d)中，以进行比较。实验共迭代20次。从图2(d)可以看出，本文提出的解释有误差画隐线图的迭代方法是可行有效的。 (a) (b) (c) (d)图2解释有误差画隐线图的迭代方法。(a)无误差画隐线图；(b)加入高斯噪声(0,5)后的画隐线图；(c)正轴测投影下恢复的平面立体；(d)正轴测投影下无误差线图（蓝色细线条）、恢复平面立体重投影线图（红色粗线条）和加噪后线图（黑色中粗线条）的比较；实验2 输入一个工程物体的灰度图像，如图3(a)所示，通过边缘提取得到物体的边缘线图，如图3(b)所示，显然，从所示的灰度图像进行边缘提取得到的线图中存在噪声，图中虚线按画隐线图标记和补线原理得到。采用本文提出的迭代方法恢复出的物体模型见图3(c)。为了验证恢复得到的立体就是边缘线图描述的物体，我们把恢复得到的立体按照正投影原理重新投影到投影面，得到的投影线图与提取的边缘线图进行比较(见图3(d)，效果比较理想。图3(a)、(b)所示图像坐标系为屏幕坐标系，图3(d)所示线图坐标系为用户坐标系，故三维物体投影的姿态不一致，屏幕坐标系和用户坐标系的变换关系为： (a) (b) (c) (d)图3 实验2。(a)平面立体的灰度图像；(b)从图像抽取获得的线图，图中的虚线按画隐线图标记和补线原理得到。(c)恢复的平面立体；(d)恢复的平面立体重投影（红色细线条）与输入线图（蓝色粗线条）比较；5 结论在Sugihara方法的基础上提出了一种解释有误差画隐线图的迭代方法。研究工作表明，采用这一迭代方法可以从有误差画隐线图恢复平面立体的三维参数，并能够对画隐线图中有误差的节点进行校正，用灰度图像和加噪后的投影线图进行实验，实验结果表明该方法是有效的。但算法要求提取的边缘图像直线段在节点处相交，这个问题在我们其他的研究中能解决这个问题。Interpreting line drawing of objects in engineeringChujun1,2 Gao Mantun3 Lu Yuming1 Xu Weiping1 (1. Nanchang Institute of Aeronautic Technology, Nanchang 330034,China2. National Astronomical Observatories Chinese Academy of Sciences,Beijing 1001013. Northwestern Polytechnical University, Xian 710072, China) This paper outlines a new iterative approach for automatic interpreting line drawing of objects in engineering. The method is based on Sugiharas algorithm. Models of objects are reconstructed from a single line drawing with noise by using iterating technology, and the line drawings with noise are corrected at the same time. Two experimentations are accomplished by using image and line drawing. The results show that our algorithm is effective.Key words: line drawing, iterative, interpreting参考文献1 D.L.Kenkins. The Automatic Interpretation of Two-Dimensional Freehand SketchesD. University of Wales College of Cardiff, 19922 H.Lipson. Computer Aided 3D Sketching for Conceptual Design D. Haifa : Technion-Israel Institute for Technology, 19983 P.A.C.Varley. automatic creation of boundary-representation models from single line drawingsD. Cardiff University, 2003 4 K. Sugihara. Machine Interpretation of Line DrawingsM. USA :The MIT Press,19865 I. V. Nagendra and U. G. Gujar. 3-D objects from 2-D orthographic views - a surveyJ. Computer & Graphics, 1988, 12(1): 111-1146 W. Wang and G. G. Grinstein. A survey of 3D solid reconstruction from 2D projection line drawingsJ. Computer Graphics Forum, 1993, 12(2): 137-1587 Beom-Soo Oh and Chang-Hun Kim. Progressive reconstruction of 3D objects from a single free-hand line drawing J. Computers & Graphics, 2003, 27(4): 581-5928 Beom-Soo Oh and Chang-Hun Kim. Self-correctional 3D shape reconstruction from a single freehand line drawing C/Proceedings of International Conference Computational Science and Its Applications. Montreal:Canada, Springer, 2003, Part III, Lecture Notes in Computer Science, 2003: 528-538 9 H. Suzuki, H. Ando and F. Kimura. Geometric constraints and reasoning for geometrical CAD systems. Computing and Graphics, 1990, 14(2): 211-22410 Chu Jun. Recovering 3D structure of planar bbject from a single line drawing with hidden-parts-drawnD. Xian: Northwestern Polytechnical University，2005 (in Chinese)（储珺，从单幅画隐立体线图回复平面立体三维结构的研究博士学位论文，西安：西北工业大学，2005）作者简介：储珺，女，1967年生，中国科学院国家天文台月球与深空探测科学应用中心博士后，南昌航空工业学院副教授，主要从事计算机图形图像研究。本文由江西省自然科学基金（0311018），南昌航空工业学院测试技术与控制工程研究中心基金（2003013）资助。作者联系方式：联系地址：北京市朝阳区大屯路风林绿洲12-4-2B联系电话：13466581967邮 编：100101E-mail: mailto:chujun996028