基于群体智能的三维碎片全局最优匹配方法

doi:10.11772/j.issn.1001-9081.2016.01.0266

计算机应用 ›› 2016, Vol. 36 ›› Issue (1): 266-270.DOI: 10.11772/j.issn.1001-9081.2016.01.0266

基于群体智能的三维碎片全局最优匹配方法

孙家泽¹, 耿国华²

1. 西安邮电大学计算机学院, 西安 710121;
2. 西北大学信息科学与技术学院, 西安 710127

收稿日期:2015-06-24 修回日期:2015-09-01 出版日期:2016-01-10 发布日期:2016-01-09
通讯作者: 孙家泽(1980-),男,河南南阳人,副教授,博士,CCF会员,主要研究方向:智能优化算法、三维模型
作者简介:耿国华(1955-),女,山东莱西人,教授,博士生导师,博士,CCF杰出会员,主要研究方向:智能信息处理、可视化分析。
基金资助:
国家自然科学基金资助项目(61203311,611721701);陕西省教育厅基金资助项目(15JK1672,15JK1678);西安市科技计划项目(CXY1516(4))。

Global optimal matching method for 3D fragments based on swarm intelligence

SUN Jiaze¹, GENG Guohua²

1. School of Computer Science and Technology, Xi'an University of Posts and Telecommunications, Xi 'an Shaanxi 710121, China;
2. School of Information Science and Technology, Northwest University, Xi'an Shaanxi 710127, China

Received:2015-06-24 Revised:2015-09-01 Online:2016-01-10 Published:2016-01-09
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61203311, 611721701), the Science Foundation of Education Ministry of Shaanxi Province (15JK1672, 15JK1678) and the Science Foundation of Xi'an City (CXY1516(4)).

摘要/Abstract

摘要： 针对传统三维碎片整体匹配过程中误差积累的问题,提出了一种基于群体智能的全局最优匹配方法。该方法对破碎物体的三维多碎片全局匹配建立全局整体碎片匹配的数学模型,将碎片的整体最优匹配求解问题转换为求满足一定约束条件的最优匹配矩阵的组合优化问题,通过将自然社会认知优化算法进行离散化来求解该NP问题。典型实例分析验证了所提方法全局优化能力强,与初始位置无关,有较强的鲁棒性,为三维碎片整体匹配提供一个有效的方法。

关键词: 群体智能, 三维模型, 全局匹配, 组合优化, 社会认知优化

Abstract: Aiming at the error accumulation problem in the process of the traditional global matching of the three-dimensional (3D) models, a global optimal matching method based on swarm intelligences was proposed. The global matching process for multiple 3D fragments was abstracted, and then a mathematic model of the global optimal matching was set up, the solution of the optimal matching for multiple 3D fragments was converted to satisfy certain constraint conditions of the optimal match matrix of combinatorial optimization problem. A discretization algorithm based on hybrid social cognitive optimization algorithm was proposed to solve the NP (Non-deterministic Polynomial) problem. Finally, the classical example analyses verified that the proposed algorithm has global optimization ability and strong robustness without the initial position, and it provides an efficient method for global matching of the 3D fragments.

Key words: swarm intelligence, three-dimensional model, global matching, combinatorial optimization, Social Cognitive Optimization (SCO)

中图分类号:

TP319
TP18

孙家泽, 耿国华. 基于群体智能的三维碎片全局最优匹配方法[J]. 计算机应用, 2016, 36(1): 266-270.

SUN Jiaze, GENG Guohua. Global optimal matching method for 3D fragments based on swarm intelligence[J]. Journal of Computer Applications, 2016, 36(1): 266-270.

参考文献

[1] HUANG Q, FLORY S, GELFAND N, et al. Reassembling frac-tured objects by geometric matching [J]. ACM transactions on graphics, 2006, 25(3): 569-578.
[2] 李群辉,周明全,耿国华.破碎刚体三角网格模型的断裂面分割[J].计算机应用,2011,31(8):2204-2205.(LI Q H, ZHOU M Q, GENG G H. Fractured surface segmentation of triangular mesh of fragments for solid reconstruction [J]. Journal of computer applications, 2011, 31(8): 2204-2205.)
[3] PAPAIOANNOU G, KARABASSI E-A, THEOHARIS T. Recon-struction of three-dimensional objects through matching of their parts [J]. IEEE transactions on pattern analysis and machine intelligence, 2002, 24(1): 114-124.
[4] ITSKOVICH A, TAL A. Surface partial matching and application to archaeology [J]. Computers & graphics, 2011, 35(2): 334-341.
[5] WINKELBACH S, WAHL F M. Pairwise matching of 3D fragments using cluster trees [J]. International journal of computer vision, 2008, 78(1): 1-13.
[6] 王坚,周来水.基于最大权团的曲面粗匹配算法[J].计算机辅助设计与图形学学报,2008,20(2):167-173.(WANG J, ZHOU L S. Surface rough matching algorithm based on maximum weight clique [J]. Journal of computer-aided design and computer graphics, 2008, 20(2): 167-173.)
[7] 陈旭瑾,徐大川,张国川.组合优化若干经典问题新进展[J].运筹学学报,2014,18(1):149-158.(CHEN X J, XU D C, ZHANG G C. New perspectives of several fundamental problems in combinatorial optimization [J]. Operations research transactions, 2014, 18(1): 149-158.)
[8] XIE X, ZHANG W, YANG Z, et al. Social cognitive optimization for nonlinear programming problems [C]// Proceedings of the First International Conference on Machine Learning and Cybernetics. Piscataway, NJ: IEEE, 2002: 779-783.
[9] 陈俊风,吴铁军.群体智能算法搜索策略的性质及对停滞现象的影响[J].系统工程理论实践,2013,33(6):1587-1595.(CHEN J F, WU T J. The property of search strategies of swarm intelligent algorithms and their influences on stagnation [J]. Systems engineering—theory & practice, 2013, 33(6): 1587-1595.)
[10] 郭鑫,孙丽杰,李光明,等.离散自由搜索算法[J].计算机应用,2013,33(6):1563-1570.(GUO X, SUN L J, LI G M, et al. Discrete free search algorithm [J]. Journal of computer applications, 2013, 33(6): 1563-1570.)
[11] SUN J, GENG G, WANG S, et al. Hybrid social cognitive optimization algorithm for constrained nonlinear programming [J]. The journal of China universities of posts and telecommunications, 2012, 19(3): 91-99.
[12] SUN J, GENG G, PAN X. DS algorithm based on SCO for matc-hing fragments [J]. Applied mechanics and materials, 2013, 411/412/413/414: 1876-1879.

[1]	赵秋云, 魏乐, 舒红平. 面向制造任务的云制造虚拟车间构造方法[J]. 计算机应用, 2021, 41(7): 2003-2011.
[2]	王宇, 刘燕丽, 陈劭武. 基于顶点冲突学习的最大公共子图算法[J]. 计算机应用, 2021, 41(6): 1756-1760.
[3]	王泽昆, 贺毅朝, 李焕哲, 张发展. 基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题[J]. 计算机应用, 2021, 41(2): 461-469.
[4]	李章洪, 梁晓磊, 田梦丹, 周文峰. 求解排列组合问题的解空间动态缩减策略[J]. 计算机应用, 2020, 40(7): 2016-2020.
[5]	裴焱栋, 顾克江. 基于内容和语义的三维模型检索综述[J]. 计算机应用, 2020, 40(7): 1863-1872.
[6]	杨云亭, 王鹏. 求解旅行商问题的多尺度量子自由粒子优化算法[J]. 计算机应用, 2020, 40(5): 1278-1283.
[7]	杨艳, 刘生建, 周永权. 贪心二进制狮群优化算法求解多维背包问题[J]. 计算机应用, 2020, 40(5): 1291-1294.
[8]	曹小威, 曲志坚, 徐玲玲, 刘晓红. 基于胶囊网络的三维模型识别[J]. 计算机应用, 2020, 40(5): 1309-1314.
[9]	赵吉, 程成. 演化信息协助的动态协同随机漂移粒子群优化算法[J]. 计算机应用, 2020, 40(11): 3119-3126.
[10]	黄一航, 江虹, 韩宾. 基于室内动静结合分割的射线跟踪加速方法[J]. 计算机应用, 2020, 40(10): 3006-3012.
[11]	张志强, 鲁晓锋, 孙钦东, 王侃. 增强开发能力的改进人工蜂群算法[J]. 计算机应用, 2019, 39(4): 949-955.
[12]	任帅, 徐振超, 王震, 贺媛, 张弢, 苏东旭, 慕德俊. 基于多融合态的低密度三维模型信息隐藏算法[J]. 计算机应用, 2019, 39(4): 1100-1105.
[13]	袁小平, 蒋硕. 基于分层自主学习的改进粒子群优化算法[J]. 计算机应用, 2019, 39(1): 148-153.
[14]	张鑫, 邹德旋, 沈鑫. 含交叉项的混合二范数粒子群优化算法[J]. 计算机应用, 2018, 38(8): 2148-2156.
[15]	戚攀, 包开阳, 马皛源. 基于模糊C均值聚类及群体智能的WSN分层路由算法[J]. 计算机应用, 2018, 38(7): 1974-1980.

基于群体智能的三维碎片全局最优匹配方法

Global optimal matching method for 3D fragments based on swarm intelligence

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics