摘要
凸包是计算几何的基本结构,在许多图形图像相关领域得到了广泛应用.本文提出了一种简单快速的平面点集凸包算法,使用了主成分分析法(Principle component analysis,PCA)对点集进行预处理,并研究了适用的排序规则和凸包边缘点判定原则.该算法已成功应用于一光栅投影三维形貌快速测量系统,对相位干涉图中密集残留点所形成的最小凸包进行提取.系统将提取的凸包区域进行掩码标记,从而避免密集残留点造成相位展开错误,保证了三维形貌重构的准确性.实验结果表明,该算法准确可靠,并且运行效率较高.
Convex hull is one of the basic structures in com- putational geometry, which is used in many fields of computer graphics and image. A novel algorithm of convex hull is pro- posed. Principle component analysis (PCA) is used to do the pretreatment on the planar point set. The applicable sort reg- ulation and determinant principle of edge points in convex hull are studied. The new algorithm is applied to a fast 3D mea- surement system based on digital fringe projection to extract the minimal convex hull formed by the intensive residual points in the phase interferogram. The system can avoid the phase unwrapping error caused by the residual points by masking the area of the extracted convex hull to guarantee the accuracy of three-dimensional shape reconstruction. Experimental results prove that the presented algorithm not only has high reliability, but also gets better operational efficiency.
出处
《自动化学报》
EI
CSCD
北大核心
2012年第8期1375-1379,共5页
Acta Automatica Sinica
关键词
凸包
平面点集
主成分分析
光栅投影
Convex hull, planar point set, principle compo- nent analysis (PCA), fringe projection