中文摘要：

针对图割曲面重建算法计算量过大的难题,根据代数多栅理论对图割计算过程进行多尺度分解,仅对最后一级进行最大流计算,其他级的标记值通过插值得到。首先,根据点云法向和重建曲面法向的一致性构建能量函数;其次,将能量函数映射到三维权重图的顶点和边上;然后,定义顶点间的一致性并由此构造抽取矩阵,以决定哪些图的顶点参与图割运算;之后,构造插值矩阵,将最后一级图割计算结果逐级插值到第一级;最后,利用步进立方体算法得到重建曲面的三角网格表示。实验结果表明,与窄带图割算法相比,本方法计算速度更快,当图的顶点数越多时速度提高得越多;对于不均匀采样的点云数据,重建效果更好;其他情况下两者效果相当。

英文摘要：

This paper proposed a novel scheme for surface reconstruction which was based on multi-scale graph-cuts.It ran max flow computation only in the last scale and got other scales＇ labels by interpolation.Firstly,it built an energy function for surface reconstruction based on consistency between point clouds normal and estimated surface normal.Secondly,it constructed the decimation matrices to decide which vertices in the 3D graph was needed in max flow computation.Then,it computed the interpolation matrices so as to approximate original 3D graph vertices＇ labels.Finally,it got the triangular mesh for reconstruction surface by marching cubes algorithm.The experimental results show that the improved algorithm raises the computational efficiency and reconstruction surface rendering effects of non-uniform sampling point clouds.