基于概念格因子分解的零件三维CAD模型检索

吴强; 董雁; 吴域西; 谢丽萍

doi:10.16383/j.aas.c170205

基于概念格因子分解的零件三维CAD模型检索

doi: 10.16383/j.aas.c170205

吴强^1,,
董雁^2,,
吴域西^3, ,,
谢丽萍^4,

1.
绍兴文理学院计算机科学与工程系绍兴 312000
2.
绍兴文理学院机电工程系绍兴 312000
3.
上海民族乐器一厂上海 201101
4.
绍兴文理学院机电学院绍兴 312000

基金项目:

国家自然科学基金 51275311

国家自然科学基金 51675346

详细信息

作者简介:
吴强  绍兴文理学院计算机科学与工程系副教授.2008年获得上海大学计算机学院控制理论与控制工程专业博士学位.主要研究方向为智能数据处理, 知识表示与知识发现.E-mail:cswq@usx.edu.cn

董雁  绍兴文理学院机电工程系教授.2005年获浙江大学机械工程专业博士学位.主要研究方向为三维模型检索.E-mail:zsdongyan@tom.com

谢丽萍  绍兴文理学院机电学院讲师.2008年获得东北师大管理系学士学位.主要研究方向为数据挖掘.E-mail:Lpxie@usx.edu.cn

通讯作者:
吴域西上海民族乐器一厂技术员, 2017年获得上海大学数码学院硕士学位.本文通信作者.E-mail:Kiriwu@hotmail.com

计量
- 文章访问数: 2508
- HTML全文浏览量: 222
- PDF下载量: 416
- 被引次数: 0
出版历程
- 收稿日期: 2017-04-17
- 录用日期: 2018-03-16
- 刊出日期: 2019-02-20

Concept Lattice Factorization Based 3D Model Retrieval of Mechanical Parts

WU Qiang^1
,,
DONG Yan^2
,,
WU Yu-Xi^{3
, ,},
XIE Li-Ping^4
,

1.
Department of Computer Science and Engineering, Shaoxing University, Shaoxing 312000
2.
Department of Mechanical Engineering, Shaoxing University, Shaoxing 312000
3.
Shanghai National Musical Instrument Factory, Shanghai 201101
4.
College of Mechanical and Electrical Engineering, Shaoxing University, Shaoxing 312000

Funds:

National Natural Science Foundation of China 51275311

National Natural Science Foundation of China 51675346

More Information

Author Bio:
Associate professor in the Department of Computer Science and Engineering, Shaoxing University. He received his Ph. D. degree from Shanghai University in 2008. His research interest covers intelligent data processing, knowledge representation and discovery

Professor in the Department of Mechanical Engineering, Shaoxing University. He received his Ph. D. degree from Zhejiang University in 2005. His research interest covers 3D model retrieval and intelligent design

Lecturer at College of Mechanical Electrical Engineering, Shaoxing University. She received her bachelor degree from Northeast Normal University in 2008. Her main research interest is data mining

Corresponding author: WU Yu-Xi Technician at the Shanghai National Musical Instrument Factory. She received her master degree from Shanghai University in 2017. Corresponding author of this paper

摘要

摘要: 针对影响概念格应用的重要问题—即使是一个小规模数据集也会产生大量的形式概念，文中提出了可以满足关系覆盖的用对象（属性）概念分解形式背景对应的布尔矩阵的新方法.用这种方法原对象属性间的二元关系可以用数量在对象（属性）概念个数以内的概念表达出来，成为概念格因子.文中给出了概念格因子生成的基本原理及其算法.通过分析三维CAD零件模型功能表面间的关系构建零件工程图结构模型，并将其映射为形式背景，从而完成概念格因子到零件关键结构的应用.最后，实例演示了概念格因子在基于零件工程图结构模型的零件CAD模型检索中的运用.
- 概念格 /
- 对象(属性)概念 /
- 布尔矩阵 /
- 因子分解 /
- 零件工程图结构模型 /
- 关键结构
Abstract: A small set of data can result in a very large number of formal concepts. With regard to this important topic, we propose an objects (attributes) concept based approach to factor Boolean matrix for the formal context in this paper. We show that the original binary relations between objects and attributes can be represented by the objects (attributes) concept matrices whose total number of concepts (factors) does not exceed the number of objects (attributes) concepts. We propose an algorithm to generate the factors. This method relies on the fundamental finite factorization property of binary matrix factorization which we proposed and proved. After analyzing the function relation between the surfaces of the 3D CAD part models, building up the engineering drawing structure model, and mapping it to the formal context, we apply concept lattice factorization to the key parts structures. Experiments on parts CAD model retrieval have shown the competency and effectiveness of the concept lattice factorization.
- Concept lattice /
- objects (attributes) concept /
- Boolean matrix /
- factorization /
- structure model of parts engineering drawing /
- key structures
注释:

1) 本文责任编委刘跃虎

HTML全文

图 1 几个常用零件功能表面的视图表达

Fig. 1 View expression of functional surfaces of several common parts

下载: 全尺寸图片幻灯片

图 2 零件工程图结构模型

Fig. 2 The structural model of part engineering drawing

下载: 全尺寸图片幻灯片

图 3 零件工程结构模型图 1(a)的概念格

Fig. 3 The concept lattice of part engineering structure model Fig. 1(a)

下载: 全尺寸图片幻灯片

图 4 零件工程结构模型图 1(b)的概念格

Fig. 4 The concept lattice of the part engineering structure model Fig. 1(b)

下载: 全尺寸图片幻灯片

图 5 零件工程结构模型图 1(c)的概念格

Fig. 5 The concept lattice of the part engineering structure model Fig. 1(c)

下载: 全尺寸图片幻灯片

图 6 模型一:连杆

Fig. 6 Model 1: connecting rod

下载: 全尺寸图片幻灯片

图 7 模型二:箱体

Fig. 7 Model 2: box

下载: 全尺寸图片幻灯片

图 8 波导开关转子关键结构

Fig. 8 The key structure of waveguide switch rotor

下载: 全尺寸图片幻灯片

图 9 不同概念节点数的查准率{查全率曲线

Fig. 9 Precision rate-recall (precision-recall) curves of the number of difierent conceptual nodes

下载: 全尺寸图片幻灯片

图 10 $n-k$曲线图

Fig. 10 The $n-k$ curve

下载: 全尺寸图片幻灯片

表 1 一个形式背景

Table 1 An example of formal context

	$a$	$b$	$c$	$d$	$e$
1	$\times$	$\times$
2	$\times$	$\times$			$\times$
3	$\times$	$\times$	$\times$	$\times$
4	$\times$				$\times$

下载: 导出CSV

表 2 功能表面二元领域关系(1)

Table 2 Two-dimensional domain relation of functional surface (1)

同轴, 平行
关系含义	分离	相遇	重叠	共点
字母标记	$s$	$m$	$o$	$c$
图示

下载: 导出CSV

表 3 功能表面二元领域关系(2)

Table 3 Two-dimensional domain relation of functional surface (2)

同轴, 平行
关系含义	分离	相遇	重叠	共点
字母标记	$s$	$m$	$o$	$c$
图示

下载: 导出CSV

表 4 零件工程图模型图 1(a)的形式背景

Table 4 The formal context of the part engineering drawing model Fig. 1(a)

	$l\parallel m$	$1\perp b$	$!\perp b$	$0\odot m$	$\sharp\odot s$
$C_{1} $	0	$1$	1	1	0
$C_{2}$	0	1	0	1	0
$C_{3} $	0	0	1	0	0
$P_{1}$	0	0	0	1	1
$P_{2}$	0	0	0	1	1
$P_{3}$	1	1	0	0	0
$P_{4}$	0	1	0	0	0
$H$	1	0	0	0	0

下载: 导出CSV

表 5 模型库中部分零件与模型一的相似度值

Table 5 Similarity value of part and model 1 in the model base

表 6 模型库中部分零件与模型二的相似度值

Table 6 Similarity value of part and model 2 in the model base

表 7 在模型库中搜索的与模型一相似的零件与耗时

Table 7 The parts and time consuming that are similar to model 1 in the model base

表 8 在模型库中搜索的与模型二相似的零件与耗时

Table 8 The parts and time consuming that are similar to model 2 in the model base

参考文献(49)

[1]	Belohlavek R, Macko J. Selecting important concepts using weights. In:Proceedings of the 2011 ICFCA. LNCS (LNAI), Heidelberg:Springer, 2011, 6628:65-80
[2]	Rice M D, Siff M. Clusters, concepts, and pseudometrics. Electronic Notes in Theoretical Computer Science, 2001, 40:323-346 doi: 10.1016/S1571-0661(05)80060-X
[3]	Kumar C A, Srinivas S. Concept lattice reduction using fuzzy K-Means clustering. Expert Systems with Applications, 2010, 37(3):2696-2704 http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0218648021/
[4]	Li J H, Kumar C A, Mei C L, Wang X Z. Comparison of reduction in formal decision contexts. International Journal of Approximate Reasoning, 2017, 80:100-122 doi: 10.1016/j.ijar.2016.08.007
[5]	陈雪, 魏玲, 钱婷.基于AE-概念格的决策形式背景属性约简.山东大学学报:理学版, 2017, 52(12):95-103 http://d.old.wanfangdata.com.cn/Periodical/sddxxb201712015 Chen Xue, Wei Ling, Qian Ting. Attribute reduction in formal decision contexts based on AE-concept lattices. Journal of Shandong University (Natural Science), 2017, 52(12):95-103 http://d.old.wanfangdata.com.cn/Periodical/sddxxb201712015
[6]	Singh P K, Ch A K. A note on constructing fuzzy homomorphism map for a given fuzzy formal context. In:Proceedings of the 3rd International Conference on Soft Computing for Problem Solving. New Delhi, India:Springer, 2013. 845-855
[7]	Shao M W, Leung Y, Wang X Z, Wu W Z. Granular reducts of formal fuzzy contexts. Knowledge-Based Systems, 2016, 114(15):156-166 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=e9ab4c8384f60c9c0741d7cad48f0179
[8]	Konecny J, Krupka M. Block relations in formal fuzzy concept analysis. International Journal of Approximate Reasoning, 2016, 73:27-55 doi: 10.1016/j.ijar.2016.02.004
[9]	Dias S M, Vieira N J. A methodology for analysis of concept lattice reduction. Information Sciences, 2017, 396:202-217 doi: 10.1016/j.ins.2017.02.037
[10]	Konecny J. On attribute reduction in concept lattices:methods based on discernibility matrix are outperformed by basic clarification and reduction. Information Sciences, 2017, 415-416:199-212 doi: 10.1016/j.ins.2017.06.013
[11]	Singh P K, Cherukuri A K, Li J H. Concepts reduction in formal concept analysis with fuzzy setting using Shannon entropy. International Journal of Machine Learning and Cybernetics, 2017, 8(1):179-189 doi: 10.1007/s13042-014-0313-6
[12]	Babin M A, Kuznetsov S O. Approximating concept stability. In:Proceedings of the 10th International Conference on Formal Concept Analysis. Leuven, Belgium:Springer, 2012. 7-15
[13]	Dias S M, Vieira N J. Applying the JBOS reduction method for relevant knowledge extraction. Expert Systems with Applications, 2013, 40(5):1880-1887 doi: 10.1016/j.eswa.2012.10.010
[14]	Li J L, He Z Y, Zhu Q L. An entropy-based weighted concept lattice for merging multi-source geo-ontologies. Entropy, 2013, 15(6):2303-2318 http://d.old.wanfangdata.com.cn/OAPaper/oai_doaj-articles_ba198225a414207ba74504f7a21ccc9d
[15]	Kang X P, Li D Y, Wang S G, Qu K S. Formal concept analysis based on fuzzy granularity base for different granulations. Fuzzy Sets and Systems, 2012, 203:33-48 doi: 10.1016/j.fss.2012.03.003
[16]	Li C P, Li J H, He M. Concept lattice compression in incomplete contexts based on K-medoids clustering. International Journal of Machine Learning and Cybernetics, 2016, 7(4):539-552 doi: 10.1007/s13042-014-0288-3
[17]	Martin T P, Rahim N H A, Majidian A. A general approach to the measurement of change in fuzzy concept lattices. Soft Computing, 2013, 17(12):2223-2234 doi: 10.1007/s00500-013-1095-6
[18]	Singh P K, Cherukuri A K, Li J H. Knowledge representation using interval-value fuzzy formal concept lattice. Soft Computing, 2016, 20(4):1485-1502 doi: 10.1007/s00500-015-1600-1
[19]	Aswani Kumar Ch., Dias S M, Vieira N J. Knowledge reduction in formal contexts using non-negative matrix factorization. Mathematics and Computers in Simulation, 2015, 109:46-63 doi: 10.1016/j.matcom.2014.08.004
[20]	Keprt A, Snášel V. Binary factor analysis with help of formal concepts. In:Proceedings of the 2004 International Workshop on Concept Lattices and their Applications. Ostrava, Czech Republic:CLA, 2004. 27-36
[21]	Belohlavek R, Vychodil V. Discovery of optimal factors in binary datavia a novel method of matrix decomposition. Journal of Computer and System Sciences. 2010, 76(1):3-20 http://www.sciencedirect.com/science/article/pii/S0022000009000415
[22]	张运超, 陈靖, 王涌天.一种融合重力信息的快速海量图像检索方法.自动化学报, 2016, 42(10):1501-1511 http://www.aas.net.cn/CN/abstract/abstract18937.shtml Zhang Yun-Chao, Chen Jing, Wang Yong-Tian. Large-scale image retrieval based on a fusion of gravity aware orientation information. Acta Automatica Sinica, 2016, 42(10):1501-1511 http://www.aas.net.cn/CN/abstract/abstract18937.shtml
[23]	姚拓中, 左文辉, 宋加涛, 应宏微.结合物体先验和空域约束的室内空域布局推理.自动化学报, 2017, 43 (8):1402-1411 http://www.aas.net.cn/CN/abstract/abstract19114.shtml Yao Tuo-Zhong, Zuo Wen-Hui, Song Jia-Tao, Ying Hong-Wei. Estimating spatial layout of cluttered rooms by using object prior and spatial constraints. Acta Automatica Sinica, 2017, 43(8):1402-1411 http://www.aas.net.cn/CN/abstract/abstract19114.shtml
[24]	Huang L, Guo S S, Tang H T, Li L, Ding K. Design of automatic parting in calibrator CAD for plastic profile extrusion dies via feature recognitions. International Journal of Advanced Manufacturing Technology, 2017, 88(5-8):1319-1331 doi: 10.1007/s00170-016-8852-5
[25]	Tao S Q. 3D CAD model retrieval based on the softassign quadratic assignment algorithm. Multimedia Tools Applications. 2018, 77(13):16249-16265 doi: 10.1007/s11042-017-5197-5
[26]	张开兴, 杭晟煜, 赵秀艳, 王金星, 宋正河, 刘贤喜.面向设计重用的三维CAD模型局部结构检索方法.农业机械学报, 2017, 48(7):405-412, 375 http://d.old.wanfangdata.com.cn/Periodical/nyjxxb201707052 Zhang Kai-Xing, Hang Sheng-Yu, Zhao Xiu-Yan, Wang Jin-Xing, Song Zheng-He, Liu Xian-Xi. Effective subpart retrieval method of 3D CAD models for design reuse. Transactions of the Chinese Society for Agricultural Machinery, 2017, 48(7):405-412, 375 http://d.old.wanfangdata.com.cn/Periodical/nyjxxb201707052
[27]	林昕. 三维CAD模型的形状特征提取与检索[博士学位论文]. 中国科学技术大学, 中国, 2017 Lin Xin. The Shape Feature Extraction and Retrieval of Three Dimensional CAD Models[Ph.D. dissertation], Zhejiang University, China, 2017
[28]	潘翔, 王学成, 张三元.基于等距二分图的三维模型局部对齐.计算机辅助设计与图形学学报, 2016, 28(3):480-487 doi: 10.3969/j.issn.1003-9775.2016.03.014 Pan Xiang, Wang Xue-Cheng, Zhang San-Yuan. 3D partial correspondence based on isometric bipartite graph. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(3):480-487 doi: 10.3969/j.issn.1003-9775.2016.03.014
[29]	白静.基于扩展特征树的三维CAD模型相似评价.计算机集成制造系统, 2014, 20(2):267-275 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201402005 Bai Jing. 3D CAD model similarity assessment based on extended feature tree. Computer Integrated Manufacturing Systems, 2014, 20(2):267-275 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt201402005
[30]	徐静, 董雁.零件工程图结构检索方法.机械工程学报, 2011, 47 (20):191-198 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201120029 Xu Jing, Dong Yan. Structure retrieval method for part engineering drawing. Journal of Mechanical Engineering, 2011, 47(20):191-198 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb201120029
[31]	朱文博, 吴新仁, 甘屹.基于形状拆分的机械零件三维模型检索.图学学报, 2015, 36(1):35-40 doi: 10.3969/j.issn.2095-302X.2015.01.007 Zhu Wen-Bo, Wu Xin-Ren, Gan Yi. 3D model retrieval of mechanical parts based on shape split. Journal of Graphics, 2015, 36(1):35-40 doi: 10.3969/j.issn.2095-302X.2015.01.007
[32]	皇甫中民, 张树生, 闫雒恒.鱼群启发的三维CAD模型聚类与检索.计算机辅助设计与图形学学报, 2016, 28(8):1373-1382, 1392 doi: 10.3969/j.issn.1003-9775.2016.08.020 Huangfu Zhong-Min, Zhang Shu-Sheng, Yan Luo-Heng. 3D CAD model clustering and retrieval inspired by fish swarm. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(8):1373-1382, 1392 doi: 10.3969/j.issn.1003-9775.2016.08.020
[33]	刘志文, 王耀侦, 庞枫骞, 李衡.基于自适应视距投影和类词典的三维模型检索.计算机工程与设计, 2016, 37(10):2744-2749 http://d.old.wanfangdata.com.cn/Periodical/jsjgcysj201610031 Liu Zhi-Wen, Wang Yao-Zhen, Pang Feng-Qian, Li Heng. Adaptive visual distance rendering and class vocabularies based 3D model retrieval. Computer Engineering and Design, 2016, 37(10):2744-2749 http://d.old.wanfangdata.com.cn/Periodical/jsjgcysj201610031
[34]	Gao S M, Shah J J. Automatic recognition of interacting machining features based on minimal condition subgraph. Computer-Aided Design, 1998, 30(9):727-739 doi: 10.1016/S0010-4485(98)00033-5
[35]	El-Mehalawi M, Miller R A. A database system of mechanical components based on geometric and topological similarity. Part Ⅱ:indexing, retrieval, matching, and similarity assessment. Computer-Aided Design, 2003, 35(1):95-105 http://www.sciencedirect.com/science/article/pii/S0010448501001786
[36]	Ma L J, Huang Z D, Wang Y W. Automatic discovery of common design structures in CAD models. Computers & Graphics, 2010, 34(5):545-555 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=36953e1b1ebf35c3bd15af03a21fc627
[37]	Zhang J, Xu Z J, Li Y, Jiang S S, Wei N N. Generic face adjacency graph for automatic common design structure discovery in assembly models. Computer-Aided Design, 2013, 45(8-9):1138-1151 doi: 10.1016/j.cad.2013.04.003
[38]	Tao S Q, Huang Z D, Zuo B Q, Peng Y P, Kang W R. Partial retrieval of CAD models based on the gradient flows in Lie group. Pattern Recognition, 2012, 45(4):1721-1738 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=f36f1ca331c79851af297ccd4721a77f
[39]	Chu C H, Hsu Y C. Similarity assessment of 3D mechanical components for design reuse. Robotics and Computer-Integrated Manufacturing, 2006, 22(4):332-341 doi: 10.1016/j.rcim.2005.07.005
[40]	徐静, 董雁.基于区域分割的零件三维模型检索方法.计算机辅助设计与图形学学报, 2017, 29(5):929-938 doi: 10.3969/j.issn.1003-9775.2017.05.018 Xu Jing, Dong Yan. 3D part model retrieval method based on surface region decomposition. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(5):929-938 doi: 10.3969/j.issn.1003-9775.2017.05.018
[41]	Tao S Q, Wang S T, Chen A H. 3D CAD solid model retrieval based on region segmentation. Multimedia Tools and Applications, 2017, 76(1):103-121 doi: 10.1007/s11042-015-3033-3
[42]	Sun Y, Ye S W, Sun Y, Kameda T. Improved algorithms for exact and approximate Boolean matrix decomposition. In:Proceedings of the 2015 IEEE International Conference on Data Science and Advanced Analytics. Paris, France:IEEE, 2015. 1-14
[43]	Ganter B, Wille R. Formal Concept Analysis:Mathematical Foundations. Springer-Verlag New York, Inc. 1999.
[44]	Belohlavek R, Vychodil V. Discovery of optimal factors in binary data via a novel method of matrix decomposition. Journal of Computer and System Sciences, 2010, 76(1):3-20 doi: 10.1016/j.jcss.2009.05.002
[45]	Belohlavek R, Vychodil V. Factorization of matrices with grades. Fuzzy Sets and Systems, 2015, 292:85-97 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=b5b67c6c3412da38e901fd2daea0788a
[46]	Belohlavek R, Trnecka M. From-below approximations in Boolean matrix factorization:geometry and new algorithm. Journal of Computer and System Sciences, 2015, 81(8):1678-1697 doi: 10.1016/j.jcss.2015.06.002
[47]	董雁, 徐静.基于装配结构相似的零件三维模型检索方法.机械工程学报, 2009, 45(4):273-280 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb200904047 Dong Yan, Xu Jing. Part 3D model retrieval method based on assembly structure similarity. Journal of Mechanical Engineering, 2009, 45(4):273-280 http://d.old.wanfangdata.com.cn/Periodical/jxgcxb200904047
[48]	王瑞霞, 彭国华.基于黎曼流形稀疏编码的图像检索算法.自动化学报, 2017, 43(5):778-788 http://www.aas.net.cn/CN/abstract/abstract19055.shtml Wang Rui-Xia, Peng Guo-Hua. An image retrieval method with sparse coding based on Riemannian manifold. Acta Automatica Sinica, 2017, 43(5):778-788 http://www.aas.net.cn/CN/abstract/abstract19055.shtml
[49]	石俊飞, 刘芳, 林耀海, 刘璐.基于深度学习和层次语义模型的极化SAR分类.自动化学报, 2017, 43 (2):215-226 http://www.aas.net.cn/CN/abstract/abstract19010.shtml Shi Jun-Fei, Liu Fang, Lin Yao-Hai, Liu Lu. Polarimetric SAR image classification based on deep learning and hierarchical semantic model. Acta Automatica Sinica, 2017, 43(2):215-226 http://www.aas.net.cn/CN/abstract/abstract19010.shtml