基于最大权团的曲面粗匹配算法  

Surface Rough Matching Algorithm Based on Maximum Weight Clique

作　　者：王坚[1] 周来水[1] 

机构地区：[1]南京航空航天大学江苏省精密与微细制造技术重点实验室,南京210016

出　　处：《计算机辅助设计与图形学学报》2008年第2期167-173,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60273097);教育部高等学校优秀青年教师教学科研奖励计划

摘　　要：提出一种将曲面匹配问题转化为图论中的最大权团搜索问题、将最优的点对应关系用最大权团表示的曲面粗匹配算法,该算法分为点匹配、点对应图构造和最大权团生成等3个阶段.点匹配使用高曲率点和均匀采样点作为候选点,通过自旋图进行匹配计算,构造初始点对应集合;点对应图构造使用距离约束、法矢约束和唯一性约束构造图的边,并使用自旋图相关系数为顶点赋权值;最大权团生成使用基于分支限界的团搜索算法,从对应点图中提取出代表最优对应的最大权团.实验结果表明,文中算法稳定、有效、可扩展,能够进行部分曲面匹配,并且适用于欠特征曲面.A surface rough matching algorithm is presented. The algorithm converts surface matching problem into maximum weight clique searching problem in graph theory, and the optimal point correspondence set is represented by the maximum weight clique. The algorithm includes point matching, point correspondence graph construction, and maximum weight clique generation. In point matching stage, both high curvature points and uniform sampling points are selected as the candidate points, then we do point matching by spin-image method, and get the initial point correspondence set. In point correspondence graph construction stage, we construct graph edges by compatibility constraints including distance constraint, normal constraint and uniqueness constraint, and construct the vertex weight by correlation coefficient of spin-images. In maximum weight clique generation stage, we use branch and bound based clique searching algorithm to find the maximum weight clique representing the optimal correspondences. Experimental result demonstrates the algorithm is robust, effective and extensible, and capable of dealing with partial surface matching problem and featureless surface matching problem.

关 键 词：曲面粗匹配 最大权团 点匹配 相容性约束 分支限界 部分曲面匹配 欠特征曲面匹配 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]