节点文献
基于高效图匹配的三维CAD模型相似评价
Similarity Assessment of 3D CAD Models Based on Efficient Graph Matching
【作者】 唐韦华;
【作者基本信息】 浙江大学 , 计算机应用, 2010, 硕士
【摘要】 在CAD领域,三维CAD模型的相似评价技术可以有效地支持对三维CAD模型的检索,达到重用已有设计,大幅缩短产品开发周期,降低产品开发成本的目的,近年来成为了大家关注的热点。同时,由于三维CAD模型具有拓扑结构、几何形状、高层语意等方面具有丰富的信息,因此往往选用能携带大量结构信息和属性信息的属性图作为三维CAD模型在计算机里的表征。然而,传统图匹配是NP完全问题,其复杂度为指数级,无法达到人们的实际应用要求,因此以高效图匹配为基础的三维CAD模型相似评价受到研究人员的关注,本文正是在这一背景下对基于高效图匹配的三维CAD模型相似评价展开研究。本文的主要工作包括以下几个方面:提出一种基于改进的随机漫步图匹配的三维零件模型相似评价。该相似评价在保持传统随机漫步图匹配高效性的基础上将其推广到三维零件模型的特征依赖图,有效地支持三维零件模型的快速检索。该方法通过图转换函数消除特征依赖图的末端节点;通过概率归一化函数消除特征间的不合理干扰;通过对节点进行分类缩小匹配空间,提升效率。提出一种基于树图匹配的三维装配体模型相似评价。该相似评价综合考虑了装配体模型装配构成关系、装配约束关系和零件本身属性三方面的信息,以树匹配和小规模的图匹配代替大规模的图匹配实现了对三维装配体模型的高效相似评价。该方法通过装配构成树表征装配体的装配构造关系;通过装配约束图表征装配体的装配约束关系;通过零件节点的属性表征零件本身的属性;通过装配构成树的匹配结果指导装配约束图的匹配,提高匹配效率。基于以上研究成果,本文在本研究小组的面向设计重用的三维CAD模型检索原型系统ZD-DRCMRS(ZheDa Design Reuse Oriented 3D CAD Model RetrievalSystem)中以功能模块的形式实现了上述算法,并通过实验初步证实了其合理性和可行性。
【Abstract】 The similarity assessment of three-dimensional CAD models can effectively support the retrieval of three-dimensional CAD model and thus reuse existing designs significantly, shorten product development cycles and reduce product development costs. Because of the topology, geometry and high-level semantics information contained by three-dimensional CAD models, attributed graphs are often used as the representation of three-dimensional CAD models. However, the traditional graph matching is NP-complete problem and their complexity is exponential, can not meet the practical application requirements. Therefore how to evaluate the similarity between three-dimensional CAD models efficiently based on graph matching is an imperative task for design knowledge reuse. In this thesis, the approach to assessing the similarity between two three-dimensional CAD models based on efficient graph matching is discussed.The main contents are presented as follows:A new similarity assessment method for three-dimensional models based on enhanced random-walks graph matching is proposed. In this approach, the traditional random-walk graph matching is extended to the feature dependency graph whereas its efficiency is maintained. Graph translation function is used to eliminate the sink nodes in feature dependency graph. Probability normalization function is used to eliminate the unreasonable disturbance among features. Classification of nodes is used to reduce the matching space and improve the efficiency.A new three-dimensional assembly model similarity assessment based on tree-graph matching is proposed. In this approach assembly construct relationship, assembly constraint relationship and parts attribute are all considered. A tree and a smaller graph are provided to instead the large graph of traditional JNC representation. Assembly construct tree is used to represent assembly construct relationship. Assembly constraint graph is used to represent assembly constraint relationship. The nodes attributes are used to represent the parts attribute. Assembly constraint graph matching efficiency is improved by the guidance provided by assembly construct tree matching results.Based on above results, a similarity assessment function module is implemented and embedded into the design reuse-oriented three-dimensional CAD model retrieval prototype system ZD-DRCMRS (ZheDa Design Reuse Oriented 3D CAD Model Retrieval System) developed by our research team. Some tests on this function module with some CAD models are conducted, and the results show the validity and the efficiency of the proposed approaches.