基于区域分割的点云骨架提取算法

doi:10.3969/j.issn.1000-3428.2017.10.037

计算机工程

基于区域分割的点云骨架提取算法

晁莹,耿国华,张雨禾,张靖

(西北大学信息科学与技术学院,西安 710127)

收稿日期:2016-06-30 出版日期:2017-10-15 发布日期:2017-10-15
作者简介:晁莹(1993—),女,硕士研究生,主研方向为图形图像处理、可视化技术;耿国华,教授、博士生导师;张雨禾,博士研究生;张靖,硕士研究生。
基金项目:
国家自然科学基金(61373117);高等学校博士学科点专项科研基金(20136101110019)。

Point Cloud Skeleton Extraction Algorithm Based on Region Segmentation

CHAO Ying,GENG Guohua,ZHANG Yuhe,ZHANG Jing

(School of Information and Technology,Northwest University,Xi’an 710127,China)

Received:2016-06-30 Online:2017-10-15 Published:2017-10-15

摘要/Abstract

摘要： 针对L1中值骨架提取方法存在迭代次数较多、相邻区域较紧密时骨架易跨越区域等问题,提出一种分区提取骨架的算法。结合点云区域的连通性及局部相关性,采用马尔科夫随机场模型,将给定点云分割成不同区域。在相同标号的区域根据区域大小和点集数自适应地计算不同的初始收缩邻域尺度,用L1中值不断收缩迭代提取各区域的骨架分支,通过主成分分析及连接角判定骨架连接方式,并根据该连接方式将骨架分支连接成完整的点云骨架。实验结果表明,该算法能够自适应地提取点云骨架,减少点云收缩的迭代次数,保持模型原有的拓扑结构,对于含有区域紧密度不均匀的模型有较好的效果。

关键词: 点云模型, 马尔科夫随机场, 区域分割, 属性信息, 骨架提取

Abstract: In order to solve the problem that the L1 median skeleton extraction method involves many iterations and the skeleton easily crosses the region of the tight adjacent region,an algorithm for extracting skeleton after segmentation is proposed.According to the connectivity of the region of point cloud and the local correlation characteristics,the point cloud can be segmented into different regions using the Markov Random Field(MRF) model.Different initial contraction neighborhood scales are adaptively calculated in terms of region size and number of points in the same labeled region.The skeleton branches of each region are extracted by L1 median iteration.The skeleton connection is determined by Principal Component Analysis(PCA) and connection angle.Then the skeleton branch is connected to a complete point cloud skeleton according to the connection mode.Experimental results show that the algorithm can adaptively extract the skeleton of the points cloud and reduce the number of iterations to contract points cloud.It not only can keep the original topological structure of the model,but also has a good effect on the model with uneven region tightness.

Key words: point cloud model, Markov Random Field(MRF), region segmentation, attribute information, skeleton extraction

中图分类号:

TP391.4

晁莹,耿国华,张雨禾,张靖. 基于区域分割的点云骨架提取算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2017.10.037.

CHAO Ying,GENG Guohua,ZHANG Yuhe,ZHANG Jing. Point Cloud Skeleton Extraction Algorithm Based on Region Segmentation[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2017.10.037.

参考文献

参考文献［1］张义宽,张晓鹏,查红彬,等.三维点云的拓扑结构表征与计算技术［J］.中国图象图形学报,2008,13(8):1576-1587. ［2］BLUM H.Biological Shape and Visual Science(PartⅠ)［J］.Journal of Theoretical Biology,1973,38(2):205-287. ［3］SHINAGAWA Y,KUNII T L.Constructing a Reeb Graph Automatically from Cross Sections［J］.IEEE Computer Graphics & Applications,1991,11(6):44-51. ［4］HILAGA M,SHINAGAWA Y,KOHMURA T,et al.Topology Matching for Fully Automatic Similarity Estimation of 3D Shapes［C］//Proceedings of Conference on Computer Graphics and Interactive Techniques.New York,USA:ACM Press,2001:203-212. ［5］AUJAY G,GOIRE,TROY F,et al.Harmonic Skeleton for Realistic Character Animation［C］//Proceedings of ACM SIGGRAPH/Eurographics Symposium on Computer Anima-tion.New York,USA:ACM Press,2007:151-160. (下转第233页) (上接第227页) ［6］DEY T K,ZHAO W.Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee［J］.Algorithmica,2004,38(1):179-200. ［7］ZHOU Y,TOGA A W.Efficient Skeletonization of Volumetric Objects［J］.IEEE Transactions on Visualization & Computer Graphics,1999,5(3):196-209. ［8］NIBLACK C W,GIBBONS P B,CAPSON D W.Generating Skeletons and Centerlines from the Distance Transform［J］.CVGIP:Graphical Models and Image Processing,1992,54(5):420-437. ［9］曹嘉.三维点云模型骨架提取算法的研究与实现［D］.北京:北京交通大学,2015. ［10］BESL P J,JAIN R C.Segmentation Through Variable-order Surface Fitting［J］.IEEE Transactions on Pattern Analysis & Machine Intelligence,1988,10(2):167-192. ［11］LONGJIANG E,WASEEM S,WILLIS A.Using a MAP-MRF Model to Improve 3D Mesh Segmentation Algorithms［C］//Proceedings of IEEE SoutheastCon.Washington D.C.,USA:IEEE Press,2013:1-7. ［12］LAVOU G,WOLF C.Markov Random Fields for Improving 3D Mesh Analysis and Segmentation［C］//Proceedings of Eurographics Conference on the 3d Object Retrieval.［S.l.］:Eurographics Association,2008:25-32. ［13］HUANG Hui,WU Shihao,Cohen-Or D,et al.L1-medialSkeleton of Point Cloud［J］.ACM Transactions on Graphics,2013 ,32(4):1-8. ［14］卢孝新.基于马尔科夫随机场的三维网格模型分割算法研究［D］.哈尔滨:哈尔滨工业大学,2010. ［15］LI G,MA W,BAO H.A New Interpolatory Subdivision for Quadrilateral Meshes［J］.Computer Graphics Forum,2010,24(1):3-16. ［16］GANDER W,GOLUB G H,STREBEL R.Least-squares Fitting of Circles and Ellipses［J］.Bit Numerical Mathematics,1994,34(4):558-578. 编辑刘冰

[1]	赵琪琪, 马慧芳, 刘海姣, 贾俊杰. 融合节点属性与结构信息的子空间异常社区检测方法[J]. 计算机工程, 2020, 46(6): 94-102.
[2]	李鹏, 陈嘉琦, 马味敏, 叶方跃. Contourlet域下基于多尺度特征的声呐图像分割[J]. 计算机工程, 2019, 45(9): 253-259.
[3]	周天祥, 董红斌, 周雯. 基于区域分割的混合地震预测算法[J]. 计算机工程, 2019, 45(9): 310-315.
[4]	史聪伟, 赵杰煜, 常俊生. 基于中轴变换的骨架特征提取算法[J]. 计算机工程, 2019, 45(7): 242-250.
[5]	王冰,刘浩,李康达,孙晓帆,张鑫生. 基于迭代自适应终止的马尔科夫错误隐藏算法[J]. 计算机工程, 2018, 44(9): 230-235.
[6]	刘正铭,马宏,刘树新,杨奕卓,李星. 一种融合节点文本属性信息的网络表示学习算法[J]. 计算机工程, 2018, 44(11): 165-171.
[7]	王汉博,孙启霖. 基于路径特征的复杂本体匹配[J]. 计算机工程, 2017, 43(2): 227-233,240.
[8]	范政昂，赵饮虹，刘济全，龚向阳，孙德宇，王彬，段会龙. 基于MRI的开颅手术仿真系统设计[J]. 计算机工程, 2014, 40(7): 7-12.
[9]	张惊雷, 王艳姣. 基于图像区域分割和置信传播的立体匹配算法[J]. 计算机工程, 2013, 39(7): 257-260,278.
[10]	王威, 李元垒, 梁方, 张连峰. 一种基于区域分割的地面飞机目标识别方法[J]. 计算机工程, 2013, 39(6): 214-218.
[11]	杨庆海, 卢波, 颜子夜, 黄沈滨, 王海洁. 基于马尔科夫随机场的粘连字符串切分算法[J]. 计算机工程, 2013, 39(4): 258-262.
[12]	徐伟，王建，杨新. 一种心脏运动补偿算法的GPU实现[J]. 计算机工程, 2013, 39(11): 19-23,30.
[13]	任新宇, 范勇, 肖德成, 原飞, 张劲峰. 基于体素标号法的空间球粒体分布测量[J]. 计算机工程, 2012, 38(19): 274-276,280.
[14]	吴颖斌, 耿国华, 贺毅岳. 基于DWT的3D点云模型数字水印算法[J]. 计算机工程, 2012, 38(06): 151-152.
[15]	黄新, 郝矿荣, 丁永生. 基于矢状面和神经网络的三维人体骨架提取[J]. 计算机工程, 2012, 38(04): 14-16.

基于区域分割的点云骨架提取算法

Point Cloud Skeleton Extraction Algorithm Based on Region Segmentation

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10