点云模型分割与融合关键技术研究
|
摘要
随着经济的发展和市场竞争的激烈，产品的生命周期不断缩短，用户对产品的需求日趋个性化。逆向工程是实现产品快速开发的途径之一，而通过逆向工程扫描测量获得的首先是点云模型，点云的分割与融合是基于点云模型进行产品快速与个性化设计的重要手段。“分割”是将产品局部细节数据从点云模型中分离提取出来，“融合”是将一个点云数据与其它点云数据拼接形成新的产品造型。本文研究点云模型分割与融合关键技术，主要的研究内容和成果如下：
为了建立点云中点的局部拓扑关系，研究了点的邻域搜索技术，提出了一种基于立方体栅格的点云模型K邻域搜索算法。采用“直接搜索最外层栅格”对现有的逐层搜索算法进行改进，采用“动态缩小空间球半径”对现有的空间球算法进行改进，并引入“点数阈值”对这两种改进算法进行了组合，确保了栅格边长取不同值时K邻域搜索算法都具有较高的效率。
点云的法矢对点云的分割和融合具有重要影响，为了得到全局一致（朝外）的法矢，提出了基于改进最小生成树的法矢调整及其奇异情况处理算法，确保了法矢调整结果的正确性，提高了法矢调整效率。在遍历方式和扩散方式上对传统最小生成树的生成过程进行了改进，提高了生成效率。奇异情况处理包含了对垂直法向和相邻曲面的处理，垂直法向的处理方法是增加邻域范围，相邻曲面的处理方法是剔除歧义邻域点。在剔除歧义邻域点时，给出邻域增长法、法向剔除法和组合法三种方法，其中组合法综合了邻域增长法和法向剔除法的优势，剔除效果最佳。
为了获得点云模型中的特征分割线，提出了一种基于Snake的点云模型分割边界提取算法。创建点云Snake的气球力模型，将气球力由二维图像Snake推广到三维点云Snake中，用于设计点云Snake的外部能，确保初始轮廓远离目标轮廓时能够正确收敛。通过分步、分段、参数设定等方法提高了Snake的收敛效果。算法解决了点云Snake模型对初始位置敏感、受噪声影响以及受其它特征影响等问题，为点云Snake模型的进一步研究打下了基础。
应用改进最小生成树实现了分割区域内部点的提取。在提取前，为了确保最小生成树能正确终止，算法将分割边界由线状扩展为带状。提取后，算法将带状边界拆分到各个区域中。算法能够有效避免过分割和欠分割，能够生成光顺分割边界，与已有分割算法Level Set相比具有较高的效率。
研究了点云模型的融合技术，提出了一种点云模型融合过渡算法。采用径向基函数生成过渡曲面；利用基于Snake和改进最小生成树的区域分割算法提取过渡区域点云，操作简单且能进行精确分割；采用局部优化投影法对过渡区域进行均匀重采样；分析了影响过渡区域效果的因素并给出相应的处理方法。
With the development of economy and the drastical competition in the market, lifecycle ofproduct is shorter and user demands are more personal. Reverse engineering is one of the methodsachieving rapid product development. Point cloud is original result got by reverse engineeringscanning. Point cloud segmentation and fusion is one important mehod for rapid and personal productdevelopment. Segmentation means extracting details from point cloud, and fusion refers to combiningone point cloud with others into new product model. Both technologies are studied. The main researchachievements are as follows:
In order to establish the topology relations of local points, a K-nearest neighbors searchingtechnology based on cubes is researched. The layer-by-layer search method and the spatial spheremethod are improved by searching outermost layer directly and reducing the radius of spatial spheredynamically respectlvely. Then a threshold of point number in one cube is applied to synthesize thesetwo improved search methods and ensure the high efficiency for different cube side lengths.
The normal vector of point cloud has great influence on point cloud segmentation and fusion. Inorder to get global consistent outward normal vector, a normal adjustment algorithm based onimproved minimum spanning tree and singular handling is proposed to adjust normal correctly andincrease efficiency. Minimum spanning tree is improved in traversal patterns and spread patterns toget higher efficiency. Two singular cases, which mean perpendicular normals and close-by surfaces,are considered. Increasing the neighbors region is used to handle perpendicular normals and removingambiguous neighbors is used to handle close-by surfaces. Three methods, which refer to neighborsincreasing method, normal points removing method and combination method, are given to removeambiguous neighbors. Among these, combination method takes advantages of other two methods andthus achieves best remove effect.
For the purpose of getting feature segment line, the Snake model of point cloud is proposed andapplied to extract segmentation boundary of point cloud. The application of balloon force is extendedfrom2D image to3D point cloud in Snake to design external energy. Snake model can convergecorrectly even if the initial contour is far away from the target contour when using balloon force.Substep Snake, subsection Snake and parameter setting are involved to get better convergence effect.The proposed model is insensitive to initial position and can be less affected by noises and otherfeatures. It lays the foundation for further studies.
Improved Minimum Spanning Tree realizes extraction of interior points. For proper finish ofimproved Minimum Spanning Tree, segment line is expanded towards both sides to bandedsegmentation boundary before extraction. After extraction, banded segmentation boundary is split tosingle regions. The algorithm can avoid over segmentation or under segmentation and generatesmooth segmentation boundaries. Compared with the Level Set segmentation algorithm, the algorithmof this paper can segment point cloud more efficiently.
The transition surface creation algorithm is presented to research point cloud fusion technology.Radial basis function is adopted to construct transition surface. Transition region, the desired part oftransition surface, is generated by the point cloud segmentation algorithm based on Snake model andimpromved Minimum Spanning Tree. Not only is it easy to operate, but also the segmentation result isaccurate. The locally optimal projection algorithm is applied to uniform resample for transition region.Factors affecting transition region are analyzed to get corresponding dealing methods.
为了建立点云中点的局部拓扑关系，研究了点的邻域搜索技术，提出了一种基于立方体栅格的点云模型K邻域搜索算法。采用“直接搜索最外层栅格”对现有的逐层搜索算法进行改进，采用“动态缩小空间球半径”对现有的空间球算法进行改进，并引入“点数阈值”对这两种改进算法进行了组合，确保了栅格边长取不同值时K邻域搜索算法都具有较高的效率。
点云的法矢对点云的分割和融合具有重要影响，为了得到全局一致（朝外）的法矢，提出了基于改进最小生成树的法矢调整及其奇异情况处理算法，确保了法矢调整结果的正确性，提高了法矢调整效率。在遍历方式和扩散方式上对传统最小生成树的生成过程进行了改进，提高了生成效率。奇异情况处理包含了对垂直法向和相邻曲面的处理，垂直法向的处理方法是增加邻域范围，相邻曲面的处理方法是剔除歧义邻域点。在剔除歧义邻域点时，给出邻域增长法、法向剔除法和组合法三种方法，其中组合法综合了邻域增长法和法向剔除法的优势，剔除效果最佳。
为了获得点云模型中的特征分割线，提出了一种基于Snake的点云模型分割边界提取算法。创建点云Snake的气球力模型，将气球力由二维图像Snake推广到三维点云Snake中，用于设计点云Snake的外部能，确保初始轮廓远离目标轮廓时能够正确收敛。通过分步、分段、参数设定等方法提高了Snake的收敛效果。算法解决了点云Snake模型对初始位置敏感、受噪声影响以及受其它特征影响等问题，为点云Snake模型的进一步研究打下了基础。
应用改进最小生成树实现了分割区域内部点的提取。在提取前，为了确保最小生成树能正确终止，算法将分割边界由线状扩展为带状。提取后，算法将带状边界拆分到各个区域中。算法能够有效避免过分割和欠分割，能够生成光顺分割边界，与已有分割算法Level Set相比具有较高的效率。
研究了点云模型的融合技术，提出了一种点云模型融合过渡算法。采用径向基函数生成过渡曲面；利用基于Snake和改进最小生成树的区域分割算法提取过渡区域点云，操作简单且能进行精确分割；采用局部优化投影法对过渡区域进行均匀重采样；分析了影响过渡区域效果的因素并给出相应的处理方法。
With the development of economy and the drastical competition in the market, lifecycle ofproduct is shorter and user demands are more personal. Reverse engineering is one of the methodsachieving rapid product development. Point cloud is original result got by reverse engineeringscanning. Point cloud segmentation and fusion is one important mehod for rapid and personal productdevelopment. Segmentation means extracting details from point cloud, and fusion refers to combiningone point cloud with others into new product model. Both technologies are studied. The main researchachievements are as follows:
In order to establish the topology relations of local points, a K-nearest neighbors searchingtechnology based on cubes is researched. The layer-by-layer search method and the spatial spheremethod are improved by searching outermost layer directly and reducing the radius of spatial spheredynamically respectlvely. Then a threshold of point number in one cube is applied to synthesize thesetwo improved search methods and ensure the high efficiency for different cube side lengths.
The normal vector of point cloud has great influence on point cloud segmentation and fusion. Inorder to get global consistent outward normal vector, a normal adjustment algorithm based onimproved minimum spanning tree and singular handling is proposed to adjust normal correctly andincrease efficiency. Minimum spanning tree is improved in traversal patterns and spread patterns toget higher efficiency. Two singular cases, which mean perpendicular normals and close-by surfaces,are considered. Increasing the neighbors region is used to handle perpendicular normals and removingambiguous neighbors is used to handle close-by surfaces. Three methods, which refer to neighborsincreasing method, normal points removing method and combination method, are given to removeambiguous neighbors. Among these, combination method takes advantages of other two methods andthus achieves best remove effect.
For the purpose of getting feature segment line, the Snake model of point cloud is proposed andapplied to extract segmentation boundary of point cloud. The application of balloon force is extendedfrom2D image to3D point cloud in Snake to design external energy. Snake model can convergecorrectly even if the initial contour is far away from the target contour when using balloon force.Substep Snake, subsection Snake and parameter setting are involved to get better convergence effect.The proposed model is insensitive to initial position and can be less affected by noises and otherfeatures. It lays the foundation for further studies.
Improved Minimum Spanning Tree realizes extraction of interior points. For proper finish ofimproved Minimum Spanning Tree, segment line is expanded towards both sides to bandedsegmentation boundary before extraction. After extraction, banded segmentation boundary is split tosingle regions. The algorithm can avoid over segmentation or under segmentation and generatesmooth segmentation boundaries. Compared with the Level Set segmentation algorithm, the algorithmof this paper can segment point cloud more efficiently.
The transition surface creation algorithm is presented to research point cloud fusion technology.Radial basis function is adopted to construct transition surface. Transition region, the desired part oftransition surface, is generated by the point cloud segmentation algorithm based on Snake model andimpromved Minimum Spanning Tree. Not only is it easy to operate, but also the segmentation result isaccurate. The locally optimal projection algorithm is applied to uniform resample for transition region.Factors affecting transition region are analyzed to get corresponding dealing methods.
引文
[1]邹万红.大规模点云模型几何造型技术研究,[博士学位论文].浙江：浙江大学，2007
[2] Rusinkiewicz S, Levoy M. QSplat: A multiresolution point rendering system for large meshes[C].In: Proceedings of the SIGGRAPH,2000:343~352
[3] Zwicker M, Pfister H, Baar J V, et al. Surface splatting[C]. In: Proceedings of the SIGGRAPH,2001:371~378
[4]董何俊,葛红,王玉峰.图像分割算法研究综述.计算机工程与科学,2009,31(12):58-61
[5]董洪伟.三角网格分割综述.中国图象图形学报,2010,15(2):181-193
[6]欧新良,匡小兰,倪问尹.三维散乱点云分割技术综述.湖南工业大学学报,2010,24(5):45-49.
[7] Woo H, Kang E, Wang S Y, et al. A New Segmentation Method for Point Cloud Data.International Journal of Machine Tools and Manufacture,2002,42(2):167-178.
[8]董明晓,郑康平,姚斌.曲面重构中点云数据的区域分割研究.中国图象图形学报,2005,10(5):575-578.
[9]柯映林，单东日.基于边特征的点云数据区域分割.浙江大学学报(工学版)，2005,39(3):377-396.
[10]莫堃，尹周平.基于3D活动轮廓模型的缺陷点云分割方法.华中科技大学学报(自然科学版),2011,39(1):82~85
[11] Rabbani T，Van den Heuvel F A, Vosselman M G.. Segmentation of Point Clouds UsingSmoothness Constraint International Archives of Photogrammetry. Remote Sensing and SpatialInformation Sciences,2006,36(5):248-253.
[12]吴世雄，王成勇.散乱噪声点云的数据分割.机械工程学报,2007,43(2):230-233
[13]傅欢，梁力，王飞等,采用局部凸性和八叉树的点云分割算法.西安交通大学学报,2012,46(10):60~65.
[14] Fransens J, van Reeth F. Hierarchical PCA decomposition of point cloud[C].//Proceedings ofthe3rd International Symposium on3D Data Processing, Visualization, and Transmission.Washington D C: IEEE Computer Society Press,2006:591-598
[15]邹万红，陈志扬，潘翔等.多分辨率层次点模型分片.计算机辅助设计与图形学学报,2008,20(1):1~5
[16] Besl P, Jain R. Segmentation and Classification of Range Images. IEEE Transactions on PatternAnalysis and Machine Intelligence,1987,9(5):608-620.
[17] Yamauchi H，Lee S, Lee Y, et al. Feature sensitive mesh segmentation with mean shift[C]. ShapeModeling International2005:236-243.
[18]史桂蓉，邢渊，张水清.用神经网络进行散乱点的区域分割.上海交通大学学报，2001,35(7):1093-1096.
[19]马腾，龙翔，冯路等.点云模型的谱聚类分割.计算机辅助设计与图形学学报，2012,24（12）：1549-1558
[20] Duda R O, Hart P E, Stork D G. Pattern Classification(2nd Ed.). Wiley Interscience, October2000
[21] Zhao J H, Li D R, Wang Y M. Ancient architecture point cloud data segmentation based onmodified fuzzy c-means clustering algorithm[C].//Proceedings of SPIE, Bellingham, UnitedStaes: SPIE Press,2008:7285
[22] Yokoya N, Levine M D. Range Image Segmentation Based on Differential Geometry: AHybrid Approach. IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,11(6):643-649.
[23]肖春霞,冯结青,缪永伟等.基于Level Set方法的点采样曲面测地线计算及区域分割.计算机学报,2005,28(2):250-258.
[24] Hoscheck J, Lasser D. Fundamentals of Computer Aided Geometric Design[M]. A.k. Peters,Natick, Massachusetts,1993
[25] Yang P H, Qian X P. Direct Boolean intersection between acquired and designed geometry. CADComputer Aided Design,2009,41(2):81-94
[26]杨振羽，郑文庭，彭群生.一般点模型的交互式布尔运算.计算机辅助设计与图形学学报，2005,17(5):954-961
[27] Xiaogang Jin, Juncong Lin, Charlie C L. et al. Mesh fusion using functional blending ontopologically incompatible sections. The Visual Computer,2006,22(4):266~275
[28] Tsai M, Lu T. A rapid mesh fusion method to create3D Virtual characters in Games[C].//In:Foruth International Conference on Computer Sciences and Convergence InformationTechnology.2009:393~398
[29] Museth K, Breen D E, Whitaker R T, et al. Level set surface editing operators. ACMTransactions on Graphics,2012,21(3):330~338
[30] Kanai T, Suzuki H, Mitani J, et al. Interactive mesh fusion based on local3D metamorphosis[C].Proc. of Graphics Interfaces,1999:148~156
[31]刘刚，金小刚，冯结青等.蒙太奇网格融合.软件学报，2003,14(8):1425~1432
[32] Biermann H, Martin I, Bernardini F, et al. A cut-and-paste editing of multiresolution surfaces.ACM Transactions on Graphics,2002,21(3):330~338
[33] Yu Y, Zhou K, Xu D, et al. Mesh editing with Poisson-based gradient field manipulation. ACMTransactions on Graphics,2004,23(3):664~651
[34] Sorkine O, Lipman Y, Cohen-Or D, et al. Laplacian surface editing[C]. Proc. ofEUROGRAPHICS/ACM SIGGRAPH Symposium on Geometry Processing,2004:179~188
[35]林俊聪.结合隐式曲面的网格融合,[博士学位论文].浙江：浙江大学，2008.
[36] Singh K, Parent R. Joining polyhedral objects using implicitly defined surfaces. The VisualComputer,2001,17(7):415~428
[37]万华根，金小刚，刘刚等.基于变分隐式曲面的网格融合.软件学报，2005,16（11）：2000~2007
[38] Lin J C, Jin X G, Wang C C L. Sketch based mesh fusion[C]. Computer Graphics International，2006,：90~101
[39]王卫红，秦绪佳.一种网格融合算法.小型微型计算机系统，2011,(6):1113~1117
[40]缪永伟.点模型的几何处理和形状编辑,[博士学位论文].杭州：浙江大学,2007.
[41] Goodsell G. On finding p-th nearest neighbors of scattered points in two dimensions for small p.Computer Aided Geometric Design,2000,17(4):387~392.
[42] Amenta N, Bern M, Kamvysselis M. A new voronoi-based surface reconstruction algorithm[C].//Proc of SICGRAPH98, New York: ACM,1998:415~421.
[43]周儒荣,张丽艳,苏旭,等.海量散乱点的曲面重建算法研究.软件学报,2001,12(2):249~255.
[44] Piegl L A, Tiller W. Algorithm for finding all k nearest neighbors. Computer Aided Design,2002,34(2):167~172.
[45]熊邦书,何明一,俞华璟.三维散乱数据的K个最近邻域快速搜索算法.计算机辅助设计与图形学学报,2004,16(7):909~911
[46]平雪良,徐荣礼,孔俊,等.基于空间划分的海量数据K邻域新算法.华南理工大学学报:自然科学版，2007,35(5):65~69.
[47]卫炜,张丽艳,周来水.一种快速搜索海量数据集K-近邻空间球算法.航空学报,2006,9(5):944~948
[48]赵俭辉，龙成江，丁乙华,等.一种基于立方体小栅格的K邻域快速搜索算法.武汉大学学报（信息科学版），2009,34(5):615~618
[49]刘越华，廖文和，刘浩.逆向工程中散乱点云的K邻域搜索算法研究.机械设计与制造,2012,(3):256~258
[50] Sankaranarayanan J, Samet H, varshney A. A fast all nearest neighbor algorithm for applicationinvolving large point clouds. Computers&Graphics,2007,31:157~174.
[51] Bentley J L. Kd Trees for Semidynamic Point Sets[C].//The6th Annual ACM Symposium onComputational Geometry, New York: ACM,1990:187~197.
[52] Pauly M, Gross M. Spectral processing of point-sampled geometry[A].//Proceedings of the28thAnnual Conference on Computer Graphics and Interactive Techniques[C], New York: ACMPress,2001:379~386.
[53] Arya S, Mount D M. Approximate nearest neighbor queries in fixed dimension[C].//Proc.4thannual. ACM-SIAM Symposium on Discrete Algorithms (SODA'93), PA, USA: Society forIndustrial and Applied Mathematics Philadelphia,1993:271~280.
[54] Hoppe H, DeRose T, Duchamp T, et al. Surface Reconstruction from Unorganized Points.Computer Graphics,1992,26(2):71-78.
[55] Pauly M, Keiser R, Kobbelt L P, et al. Shape modeling with point-sampled geometry. ACMTrans. Graph,2003,22(3):641~650
[56] Levin D. The approximation power of moving least-squares. Mathematics of Computation.1998,67(224):1517~1531
[57] Alexa M, Behr J, Cohen-or D, Fleishman S, Levin D, Silva C.T. Computing and rendering pointset surfaces. IEEE Transactions on Visualization and Compute Graphics,2003,9(1):3~15
[58] Oztireli A C, Guennebaud G, Gross M H. Feature preserving point set surfaces based onnon-linear kernel regression. Comput. Graph.2009,28(2):493~501
[59] Nina A, Marshall B. Surface reconstruction by voronoi filtering[C]. In SCG’98: Proceedingsof the fourteenth annual symposium on computational geometry,1998:39~48.
[60] Nina A, Marshall B, Manolis K. A new voronoi-based surface reconstruction algorithm[C]. InSIGGRAPH’98: Proceedings of the25th annual conference on computer graphics andinteractive techniques,1998:415~421.
[61] Alliez P, Cohen-Steiner D, Tong Y, et al. Voronoi-based variational reconstruction of unorientedpoint sets[C]. In SGP’07: Proceedings of the fifth Eurographics Symposium on GeometryProcessing, Barcelona, Spain, Eurographics Association,2007:39~48
[62] Li B, Schnabel R, Klein R, et al. Robust normal estimation for point clouds with sharp feature.Computers&Graphics,2010,34(2):94~106
[63] Boulch A, Marlet R. Fast and robust normal estimation for point clouds with sharp features.Computer Graphics Forum,2012,31(5):1765~1774.
[64]杜佶.径向基函数在逆向工程中的应用研究,[硕士学位论文].南京:南京航空航天大学,2005
[65]贺美芳.基于散乱点云数据的曲面重建关键技术研究，[博士学位论文].南京:南京航空航天大学,2006
[66]孟祥林，何万涛，赵灿等.逆向工程中点云邻域搜索及法矢估算相关算法研究.制造技术与机床,2009(2):44-47
[67] Sun J，Smith M, Farooq A. Examining the uncertainty of the recovered surface normal in threelight photometric stereo. Image and Vision Computing,2007,25(7)：1073-1079.
[68] Ma W C, Hawkin T, Peers P, et al. Rapid acquisition of specular and diffuse normal maps frompolarized spherical gradient illumination[C].//Eurographics symposium on rendering, Grenoble,France: The Eurographics Association2007,2007:183-194.
[69] Huang H, Li D, Zhang H, et al. Consolidation of Unorganized Point Clouds for SurfaceReconstruction. ACM Transactions on Graphics,2009,28(5)：176-183
[70] Liu S J, Charlie C W. Orienting Unorganized Points for Surface Reconstruction. Computers&Graphics,2010,34(3)：209-218.
[71]曾峰，钟治初，杨通等.基于SOM的散乱点云法矢计算.计算机工程,2012,38(8)：287-290.
[72] Mullen P, Degoes F, Desbrun M, et al. Signing the unsigened: Robust surface reconstructionfrom raw pointsets. Comput. Graph,2010,29(5):1733~1741
[73] Wang J, Yang Z W, Chen F L. A variational model for normal computation for point clouds. VisComput,2012,28:163~174.
[74]缪永伟.点模型的几何处理和形状编辑,[博士学位论文].杭州：浙江大学,2007
[75]吴勃英.数值分析原理.北京：科学出版社,2003:247~250
[76] Pauly M, Keiser R, Gross M. Multi-scale feature extraction on point-sampled surfaces.Computer Graphics Forum,2003,22(3):281~290.
[77]刘胜兰.逆向工程中自由曲面与规则曲面重建关键技术研究,[博士学位论文].南京:南京航空航天大学，2004
[78]蒋长锦.科学计算和C程序集[M].合肥:中国科学技术大学出版社，1998
[79] Ohtake Y, Belyaev A, Seidel H P.3D scattered data interpolation and approximation withmultilevel compactly supported RBFs. Graphical Models,2005,67(3):150-165
[80] Kass M, Witkin A, Terzopoulos D. Snakes: active contour models. International Journal ofComputer Vision,1988,1(4):321-331
[81] AminiA A, W eymouth T E, Jain R C. Using dynamic programming for solving variationalproblem in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence,1990,12(9):855-867
[82]黄辉，关履泰，龚永义等.基于动态规划的方向蛇模型.计算机工程与应用,2006,42(27):31~32
[83] Williams D J, Shab M. A fast algorithm for active contours and curvature estimation.CVGIP: Image Understanding,1992,55(1):14~26
[84] Cohen L D.. On active contour models and balloons. CVGIP: Image Understanding,1991,53(2):211-218
[85] Xu C Y, Jerry L P. Snake, shapes and gradient vector flow. IEEE Trans. on Image Processing,1998,7:359-369.
[86]徐牧，王润生.一种组合主动轮廓线模型算法.计算机工程与科学,2004,26(12):38-41
[87]龚永义，罗笑南，黄辉等.基于单水平集的多目标轮廓提取.计算机学报，2007,30(1)：120-128
[88] Menet S, Saint M P, Medion G B. Snakes: implementation and application to stereo[C].//Fua P, Hansan A J eds Proceedings of the DARPA Image Understanding Workshop. Pittsburgh,Pennsylanis: IEEE Computer Society Press,1990:720-726.
[89] Marsousi M, Efte khari A, Kocharian A, et al. Endocardial boundary extraction in left ventricularechocardiographic images using fast and adapt B-spline Snake algorithm. International Journalof Computer Assisted Radiology and Surgery,2010,5(5):501~513
[90]单昊.基于几何小波的多目标图像分割与地震去噪[博士学位论文].北京:清华大学，2010
[91] Wang X N. FengENG Y J, FengENG Z R. Snakes ant colony optimization for imagesegmentation[C]. IEEE. Trans. Guangzhou,The Fourth International Conference on MachineLearning and Cybernetics,2005(1):5355-5360
[92] Li D, Zang G, Wu Z, et al. An edge embedded marker-based watershed algorithm for high spatialresolution remote sensing image segmentation. IEEE Transactions on Image Processing,2010,19(10):2781~2787
[93]兰红，张璐.分水岭优化的Snake模型肝脏图像分割.中国图象图形学报,2012,17(7):873~879
[94] Lee Y and Lee S. Geometric Snakes for triangular meshes. Computer Graphics Forum(Eurographics2002),2002,21(3):229-238
[95] Milroy M J, Bradley C, Vickers G W. Segmentation of a wrap-around model using an activecontour. Computer Aided Design,1997,29(4):.299-320
[96] Cheng L T, Burchard P. Merriman B, et al. Motion of curves constrained on surfaces using alevet-set approach. Journal of Computational Physics,2002,175:604-644
[97] Liu S L, Martin R R, Langbein F C, et al. Segmenting reliefs on triangle meshs[C].//Proceedings SPM2006-ACM Symposium on Solid and Physical Modeling.2006:7-16
[98] Jung M，Kim H. Snaking across3D meshes[C].//Proceedings of the Computer Graphics andApplications.2004:87-93
[99] Liu S B, Niu W G. A modified algorithm for generation of3D GVF field from point cloud[C].Proc. SPIE8335,2012:83351O
[100] Liu S B, Ye Y S. Point cloud segmentation using gradient vector flow snake[C].Intrenational Conference on Information Science and Technology,2011:1114~1118
[101] Boyko A, Funkhouser T. Extracting roads from dense point clouds in large scale urbanenvironment. Journal of Photogrammetry and Remote Sensing,2011，66(6):2~12
[102]李启翮.基于蛇模型的图像分割与目标轮廓跟踪研究[博士学位论文].北京:清华大学，2008.
[103] He Y, Luo Y, Hu D. Semi-automatic initialization of gradient vector flow Snakes. Journal ofElectronic Imaging,2006,15(4):043006
[104] Cohen L D, Cohen I. Finite-element methods for active models and balloons for2-D and3-D images. IEEE Transactions on Pattern Analysis and Machine Intelligence,1993,15(11):1131-1147
[105] Park H K, Chung M J. External force of snake: virtual electric field. Electronics Letters,2002,38(24):1500-1502
[106] Li B, Acton S T. Active contour external force using vector field convolution for imagesegmentation. IEEE Transaction on Image Processing,2007,16(8):2096-2106
[107] Li Q H, Luo Y P, Xiao D Y. Adaptive pressure force---a new external force for the snakemodel. Optical Engineering，2008,47(5):057006.
[108] Hubeli A, Gross M. Multiresolution feature extraction for unstructured meshes[C].//Proceedings of the IEEE Visualization Conference,2001:287-294
[109] Zou Wanhong, Ding Zhan, Ye xiuzi, et al. Interactive point cloud blending by drag-and-drop.Journal of Zhejiang University SCIENCE A,2007,8(10):1633-1641
[110]王仁芳.点模型数字几何处理若干技术研究,[博士学位论文].浙江：浙江大学，2007.
[111] Carr J, Beatson R, Cherrie J, et al. Reconstruction and representation of3D objects withbasis functions[C].SIGGRAPH’01Conference Proceedings, Los Angeles, California,2001:67~76
[112] Buhmann M D. Radial basis functions: theory and implementation [M]. London, CambridgeUniversity Press,2003.
[113] Wendland H. Piecewise polynomial: Positive definite and compactly supported radialfunctions of minimal degree. Advances in Computational Mathematics,1995,4:389~396
[114] Kojekine N, Hagiwara I， Savchenko V. Software tools using CSRBFs for processingscattered data. Computers&Graphics,2003,27(2):311~319
[115] Ohtake Y, Belyaev A, Seidel H P. A multi-scale approach to3D scattered data interpolationwith compactly supported radial basis functions[C]. Proceeding of Shape Modeling International,2003:1~9
[116] Bryan S M, Terry S Y, Penny R, et al. Interpolating implicit surface from scattered surfacedata using compactly supported radial basis functions[C]. Proceedings of the InternationalConference on Shape Modeling and Applications,2001:89~98
[117] Lorensen W E, Cline H E. Marching Cubes: A High Resolution3D Surface ConstructionAlgorithm. Computer&Graphics,1987,21(4):163~169
[118]孙伟，张彩明，杨兴强. Marching Cubes算法研究现状.计算机辅助设计与图形学学报，2007,19(7):947~952
[119] Lipman Y, Cohen-Or D, Levin D, et al. Parameterization-free projection for geometryreconstruction. ACM Transactions on Graphics,2007,26(3):1~6
[120] Witkin A P, Heckbert P S. Using particles to sample and control implicit surfaces[C]. Proc.of ACM SIGGRAPH,1994:269~278
[2] Rusinkiewicz S, Levoy M. QSplat: A multiresolution point rendering system for large meshes[C].In: Proceedings of the SIGGRAPH,2000:343~352
[3] Zwicker M, Pfister H, Baar J V, et al. Surface splatting[C]. In: Proceedings of the SIGGRAPH,2001:371~378
[4]董何俊,葛红,王玉峰.图像分割算法研究综述.计算机工程与科学,2009,31(12):58-61
[5]董洪伟.三角网格分割综述.中国图象图形学报,2010,15(2):181-193
[6]欧新良,匡小兰,倪问尹.三维散乱点云分割技术综述.湖南工业大学学报,2010,24(5):45-49.
[7] Woo H, Kang E, Wang S Y, et al. A New Segmentation Method for Point Cloud Data.International Journal of Machine Tools and Manufacture,2002,42(2):167-178.
[8]董明晓,郑康平,姚斌.曲面重构中点云数据的区域分割研究.中国图象图形学报,2005,10(5):575-578.
[9]柯映林，单东日.基于边特征的点云数据区域分割.浙江大学学报(工学版)，2005,39(3):377-396.
[10]莫堃，尹周平.基于3D活动轮廓模型的缺陷点云分割方法.华中科技大学学报(自然科学版),2011,39(1):82~85
[11] Rabbani T，Van den Heuvel F A, Vosselman M G.. Segmentation of Point Clouds UsingSmoothness Constraint International Archives of Photogrammetry. Remote Sensing and SpatialInformation Sciences,2006,36(5):248-253.
[12]吴世雄，王成勇.散乱噪声点云的数据分割.机械工程学报,2007,43(2):230-233
[13]傅欢，梁力，王飞等,采用局部凸性和八叉树的点云分割算法.西安交通大学学报,2012,46(10):60~65.
[14] Fransens J, van Reeth F. Hierarchical PCA decomposition of point cloud[C].//Proceedings ofthe3rd International Symposium on3D Data Processing, Visualization, and Transmission.Washington D C: IEEE Computer Society Press,2006:591-598
[15]邹万红，陈志扬，潘翔等.多分辨率层次点模型分片.计算机辅助设计与图形学学报,2008,20(1):1~5
[16] Besl P, Jain R. Segmentation and Classification of Range Images. IEEE Transactions on PatternAnalysis and Machine Intelligence,1987,9(5):608-620.
[17] Yamauchi H，Lee S, Lee Y, et al. Feature sensitive mesh segmentation with mean shift[C]. ShapeModeling International2005:236-243.
[18]史桂蓉，邢渊，张水清.用神经网络进行散乱点的区域分割.上海交通大学学报，2001,35(7):1093-1096.
[19]马腾，龙翔，冯路等.点云模型的谱聚类分割.计算机辅助设计与图形学学报，2012,24（12）：1549-1558
[20] Duda R O, Hart P E, Stork D G. Pattern Classification(2nd Ed.). Wiley Interscience, October2000
[21] Zhao J H, Li D R, Wang Y M. Ancient architecture point cloud data segmentation based onmodified fuzzy c-means clustering algorithm[C].//Proceedings of SPIE, Bellingham, UnitedStaes: SPIE Press,2008:7285
[22] Yokoya N, Levine M D. Range Image Segmentation Based on Differential Geometry: AHybrid Approach. IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,11(6):643-649.
[23]肖春霞,冯结青,缪永伟等.基于Level Set方法的点采样曲面测地线计算及区域分割.计算机学报,2005,28(2):250-258.
[24] Hoscheck J, Lasser D. Fundamentals of Computer Aided Geometric Design[M]. A.k. Peters,Natick, Massachusetts,1993
[25] Yang P H, Qian X P. Direct Boolean intersection between acquired and designed geometry. CADComputer Aided Design,2009,41(2):81-94
[26]杨振羽，郑文庭，彭群生.一般点模型的交互式布尔运算.计算机辅助设计与图形学学报，2005,17(5):954-961
[27] Xiaogang Jin, Juncong Lin, Charlie C L. et al. Mesh fusion using functional blending ontopologically incompatible sections. The Visual Computer,2006,22(4):266~275
[28] Tsai M, Lu T. A rapid mesh fusion method to create3D Virtual characters in Games[C].//In:Foruth International Conference on Computer Sciences and Convergence InformationTechnology.2009:393~398
[29] Museth K, Breen D E, Whitaker R T, et al. Level set surface editing operators. ACMTransactions on Graphics,2012,21(3):330~338
[30] Kanai T, Suzuki H, Mitani J, et al. Interactive mesh fusion based on local3D metamorphosis[C].Proc. of Graphics Interfaces,1999:148~156
[31]刘刚，金小刚，冯结青等.蒙太奇网格融合.软件学报，2003,14(8):1425~1432
[32] Biermann H, Martin I, Bernardini F, et al. A cut-and-paste editing of multiresolution surfaces.ACM Transactions on Graphics,2002,21(3):330~338
[33] Yu Y, Zhou K, Xu D, et al. Mesh editing with Poisson-based gradient field manipulation. ACMTransactions on Graphics,2004,23(3):664~651
[34] Sorkine O, Lipman Y, Cohen-Or D, et al. Laplacian surface editing[C]. Proc. ofEUROGRAPHICS/ACM SIGGRAPH Symposium on Geometry Processing,2004:179~188
[35]林俊聪.结合隐式曲面的网格融合,[博士学位论文].浙江：浙江大学，2008.
[36] Singh K, Parent R. Joining polyhedral objects using implicitly defined surfaces. The VisualComputer,2001,17(7):415~428
[37]万华根，金小刚，刘刚等.基于变分隐式曲面的网格融合.软件学报，2005,16（11）：2000~2007
[38] Lin J C, Jin X G, Wang C C L. Sketch based mesh fusion[C]. Computer Graphics International，2006,：90~101
[39]王卫红，秦绪佳.一种网格融合算法.小型微型计算机系统，2011,(6):1113~1117
[40]缪永伟.点模型的几何处理和形状编辑,[博士学位论文].杭州：浙江大学,2007.
[41] Goodsell G. On finding p-th nearest neighbors of scattered points in two dimensions for small p.Computer Aided Geometric Design,2000,17(4):387~392.
[42] Amenta N, Bern M, Kamvysselis M. A new voronoi-based surface reconstruction algorithm[C].//Proc of SICGRAPH98, New York: ACM,1998:415~421.
[43]周儒荣,张丽艳,苏旭,等.海量散乱点的曲面重建算法研究.软件学报,2001,12(2):249~255.
[44] Piegl L A, Tiller W. Algorithm for finding all k nearest neighbors. Computer Aided Design,2002,34(2):167~172.
[45]熊邦书,何明一,俞华璟.三维散乱数据的K个最近邻域快速搜索算法.计算机辅助设计与图形学学报,2004,16(7):909~911
[46]平雪良,徐荣礼,孔俊,等.基于空间划分的海量数据K邻域新算法.华南理工大学学报:自然科学版，2007,35(5):65~69.
[47]卫炜,张丽艳,周来水.一种快速搜索海量数据集K-近邻空间球算法.航空学报,2006,9(5):944~948
[48]赵俭辉，龙成江，丁乙华,等.一种基于立方体小栅格的K邻域快速搜索算法.武汉大学学报（信息科学版），2009,34(5):615~618
[49]刘越华，廖文和，刘浩.逆向工程中散乱点云的K邻域搜索算法研究.机械设计与制造,2012,(3):256~258
[50] Sankaranarayanan J, Samet H, varshney A. A fast all nearest neighbor algorithm for applicationinvolving large point clouds. Computers&Graphics,2007,31:157~174.
[51] Bentley J L. Kd Trees for Semidynamic Point Sets[C].//The6th Annual ACM Symposium onComputational Geometry, New York: ACM,1990:187~197.
[52] Pauly M, Gross M. Spectral processing of point-sampled geometry[A].//Proceedings of the28thAnnual Conference on Computer Graphics and Interactive Techniques[C], New York: ACMPress,2001:379~386.
[53] Arya S, Mount D M. Approximate nearest neighbor queries in fixed dimension[C].//Proc.4thannual. ACM-SIAM Symposium on Discrete Algorithms (SODA'93), PA, USA: Society forIndustrial and Applied Mathematics Philadelphia,1993:271~280.
[54] Hoppe H, DeRose T, Duchamp T, et al. Surface Reconstruction from Unorganized Points.Computer Graphics,1992,26(2):71-78.
[55] Pauly M, Keiser R, Kobbelt L P, et al. Shape modeling with point-sampled geometry. ACMTrans. Graph,2003,22(3):641~650
[56] Levin D. The approximation power of moving least-squares. Mathematics of Computation.1998,67(224):1517~1531
[57] Alexa M, Behr J, Cohen-or D, Fleishman S, Levin D, Silva C.T. Computing and rendering pointset surfaces. IEEE Transactions on Visualization and Compute Graphics,2003,9(1):3~15
[58] Oztireli A C, Guennebaud G, Gross M H. Feature preserving point set surfaces based onnon-linear kernel regression. Comput. Graph.2009,28(2):493~501
[59] Nina A, Marshall B. Surface reconstruction by voronoi filtering[C]. In SCG’98: Proceedingsof the fourteenth annual symposium on computational geometry,1998:39~48.
[60] Nina A, Marshall B, Manolis K. A new voronoi-based surface reconstruction algorithm[C]. InSIGGRAPH’98: Proceedings of the25th annual conference on computer graphics andinteractive techniques,1998:415~421.
[61] Alliez P, Cohen-Steiner D, Tong Y, et al. Voronoi-based variational reconstruction of unorientedpoint sets[C]. In SGP’07: Proceedings of the fifth Eurographics Symposium on GeometryProcessing, Barcelona, Spain, Eurographics Association,2007:39~48
[62] Li B, Schnabel R, Klein R, et al. Robust normal estimation for point clouds with sharp feature.Computers&Graphics,2010,34(2):94~106
[63] Boulch A, Marlet R. Fast and robust normal estimation for point clouds with sharp features.Computer Graphics Forum,2012,31(5):1765~1774.
[64]杜佶.径向基函数在逆向工程中的应用研究,[硕士学位论文].南京:南京航空航天大学,2005
[65]贺美芳.基于散乱点云数据的曲面重建关键技术研究，[博士学位论文].南京:南京航空航天大学,2006
[66]孟祥林，何万涛，赵灿等.逆向工程中点云邻域搜索及法矢估算相关算法研究.制造技术与机床,2009(2):44-47
[67] Sun J，Smith M, Farooq A. Examining the uncertainty of the recovered surface normal in threelight photometric stereo. Image and Vision Computing,2007,25(7)：1073-1079.
[68] Ma W C, Hawkin T, Peers P, et al. Rapid acquisition of specular and diffuse normal maps frompolarized spherical gradient illumination[C].//Eurographics symposium on rendering, Grenoble,France: The Eurographics Association2007,2007:183-194.
[69] Huang H, Li D, Zhang H, et al. Consolidation of Unorganized Point Clouds for SurfaceReconstruction. ACM Transactions on Graphics,2009,28(5)：176-183
[70] Liu S J, Charlie C W. Orienting Unorganized Points for Surface Reconstruction. Computers&Graphics,2010,34(3)：209-218.
[71]曾峰，钟治初，杨通等.基于SOM的散乱点云法矢计算.计算机工程,2012,38(8)：287-290.
[72] Mullen P, Degoes F, Desbrun M, et al. Signing the unsigened: Robust surface reconstructionfrom raw pointsets. Comput. Graph,2010,29(5):1733~1741
[73] Wang J, Yang Z W, Chen F L. A variational model for normal computation for point clouds. VisComput,2012,28:163~174.
[74]缪永伟.点模型的几何处理和形状编辑,[博士学位论文].杭州：浙江大学,2007
[75]吴勃英.数值分析原理.北京：科学出版社,2003:247~250
[76] Pauly M, Keiser R, Gross M. Multi-scale feature extraction on point-sampled surfaces.Computer Graphics Forum,2003,22(3):281~290.
[77]刘胜兰.逆向工程中自由曲面与规则曲面重建关键技术研究,[博士学位论文].南京:南京航空航天大学，2004
[78]蒋长锦.科学计算和C程序集[M].合肥:中国科学技术大学出版社，1998
[79] Ohtake Y, Belyaev A, Seidel H P.3D scattered data interpolation and approximation withmultilevel compactly supported RBFs. Graphical Models,2005,67(3):150-165
[80] Kass M, Witkin A, Terzopoulos D. Snakes: active contour models. International Journal ofComputer Vision,1988,1(4):321-331
[81] AminiA A, W eymouth T E, Jain R C. Using dynamic programming for solving variationalproblem in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence,1990,12(9):855-867
[82]黄辉，关履泰，龚永义等.基于动态规划的方向蛇模型.计算机工程与应用,2006,42(27):31~32
[83] Williams D J, Shab M. A fast algorithm for active contours and curvature estimation.CVGIP: Image Understanding,1992,55(1):14~26
[84] Cohen L D.. On active contour models and balloons. CVGIP: Image Understanding,1991,53(2):211-218
[85] Xu C Y, Jerry L P. Snake, shapes and gradient vector flow. IEEE Trans. on Image Processing,1998,7:359-369.
[86]徐牧，王润生.一种组合主动轮廓线模型算法.计算机工程与科学,2004,26(12):38-41
[87]龚永义，罗笑南，黄辉等.基于单水平集的多目标轮廓提取.计算机学报，2007,30(1)：120-128
[88] Menet S, Saint M P, Medion G B. Snakes: implementation and application to stereo[C].//Fua P, Hansan A J eds Proceedings of the DARPA Image Understanding Workshop. Pittsburgh,Pennsylanis: IEEE Computer Society Press,1990:720-726.
[89] Marsousi M, Efte khari A, Kocharian A, et al. Endocardial boundary extraction in left ventricularechocardiographic images using fast and adapt B-spline Snake algorithm. International Journalof Computer Assisted Radiology and Surgery,2010,5(5):501~513
[90]单昊.基于几何小波的多目标图像分割与地震去噪[博士学位论文].北京:清华大学，2010
[91] Wang X N. FengENG Y J, FengENG Z R. Snakes ant colony optimization for imagesegmentation[C]. IEEE. Trans. Guangzhou,The Fourth International Conference on MachineLearning and Cybernetics,2005(1):5355-5360
[92] Li D, Zang G, Wu Z, et al. An edge embedded marker-based watershed algorithm for high spatialresolution remote sensing image segmentation. IEEE Transactions on Image Processing,2010,19(10):2781~2787
[93]兰红，张璐.分水岭优化的Snake模型肝脏图像分割.中国图象图形学报,2012,17(7):873~879
[94] Lee Y and Lee S. Geometric Snakes for triangular meshes. Computer Graphics Forum(Eurographics2002),2002,21(3):229-238
[95] Milroy M J, Bradley C, Vickers G W. Segmentation of a wrap-around model using an activecontour. Computer Aided Design,1997,29(4):.299-320
[96] Cheng L T, Burchard P. Merriman B, et al. Motion of curves constrained on surfaces using alevet-set approach. Journal of Computational Physics,2002,175:604-644
[97] Liu S L, Martin R R, Langbein F C, et al. Segmenting reliefs on triangle meshs[C].//Proceedings SPM2006-ACM Symposium on Solid and Physical Modeling.2006:7-16
[98] Jung M，Kim H. Snaking across3D meshes[C].//Proceedings of the Computer Graphics andApplications.2004:87-93
[99] Liu S B, Niu W G. A modified algorithm for generation of3D GVF field from point cloud[C].Proc. SPIE8335,2012:83351O
[100] Liu S B, Ye Y S. Point cloud segmentation using gradient vector flow snake[C].Intrenational Conference on Information Science and Technology,2011:1114~1118
[101] Boyko A, Funkhouser T. Extracting roads from dense point clouds in large scale urbanenvironment. Journal of Photogrammetry and Remote Sensing,2011，66(6):2~12
[102]李启翮.基于蛇模型的图像分割与目标轮廓跟踪研究[博士学位论文].北京:清华大学，2008.
[103] He Y, Luo Y, Hu D. Semi-automatic initialization of gradient vector flow Snakes. Journal ofElectronic Imaging,2006,15(4):043006
[104] Cohen L D, Cohen I. Finite-element methods for active models and balloons for2-D and3-D images. IEEE Transactions on Pattern Analysis and Machine Intelligence,1993,15(11):1131-1147
[105] Park H K, Chung M J. External force of snake: virtual electric field. Electronics Letters,2002,38(24):1500-1502
[106] Li B, Acton S T. Active contour external force using vector field convolution for imagesegmentation. IEEE Transaction on Image Processing,2007,16(8):2096-2106
[107] Li Q H, Luo Y P, Xiao D Y. Adaptive pressure force---a new external force for the snakemodel. Optical Engineering，2008,47(5):057006.
[108] Hubeli A, Gross M. Multiresolution feature extraction for unstructured meshes[C].//Proceedings of the IEEE Visualization Conference,2001:287-294
[109] Zou Wanhong, Ding Zhan, Ye xiuzi, et al. Interactive point cloud blending by drag-and-drop.Journal of Zhejiang University SCIENCE A,2007,8(10):1633-1641
[110]王仁芳.点模型数字几何处理若干技术研究,[博士学位论文].浙江：浙江大学，2007.
[111] Carr J, Beatson R, Cherrie J, et al. Reconstruction and representation of3D objects withbasis functions[C].SIGGRAPH’01Conference Proceedings, Los Angeles, California,2001:67~76
[112] Buhmann M D. Radial basis functions: theory and implementation [M]. London, CambridgeUniversity Press,2003.
[113] Wendland H. Piecewise polynomial: Positive definite and compactly supported radialfunctions of minimal degree. Advances in Computational Mathematics,1995,4:389~396
[114] Kojekine N, Hagiwara I， Savchenko V. Software tools using CSRBFs for processingscattered data. Computers&Graphics,2003,27(2):311~319
[115] Ohtake Y, Belyaev A, Seidel H P. A multi-scale approach to3D scattered data interpolationwith compactly supported radial basis functions[C]. Proceeding of Shape Modeling International,2003:1~9
[116] Bryan S M, Terry S Y, Penny R, et al. Interpolating implicit surface from scattered surfacedata using compactly supported radial basis functions[C]. Proceedings of the InternationalConference on Shape Modeling and Applications,2001:89~98
[117] Lorensen W E, Cline H E. Marching Cubes: A High Resolution3D Surface ConstructionAlgorithm. Computer&Graphics,1987,21(4):163~169
[118]孙伟，张彩明，杨兴强. Marching Cubes算法研究现状.计算机辅助设计与图形学学报，2007,19(7):947~952
[119] Lipman Y, Cohen-Or D, Levin D, et al. Parameterization-free projection for geometryreconstruction. ACM Transactions on Graphics,2007,26(3):1~6
[120] Witkin A P, Heckbert P S. Using particles to sample and control implicit surfaces[C]. Proc.of ACM SIGGRAPH,1994:269~278