无序散乱点云的表面重建

无序散乱点云的表面重建摘要：我们描述并且说明一个算法，它需要输入一组无序的三维点云数据，这组点运数据在这个未知的流行M上或者附近，输出一个简单的近似于M的曲面。无论是存在边界的拓扑结构，还是M的几何形状都被认为是5提前已知的，所有这些信息都是从数据中自动推断出来的。这个问题自然出现在各种实际情况中，如从多个视角深度扫描一个对象，用二维切片恢复生物的形状，交互式曲面绘制。附加关键：几何建模，曲面拟合，三维形状恢复，深度数据分析。1简介一般来说,我们感兴趣的问题可以表示如下:基于未知的表面的部分信息，尽可能构造表面的完整表示。这类重建问题发生在不同的科学和工程应用领域中,包括：来自深度数据的曲面:由激光深度扫描系统采集的数据通常是从传感器到被扫描对象的距离矩形网格。如果传感器和目标对象是固定的,只要目标对象是“可视”的，那么可以全数字化采集。更复杂的系统,比如那些由控件实验室生产的产品,有能力通过旋转传感器或扫描对象来实现数字化圆柱形物体。然而,拓扑结构更复杂对象的扫描,包括那些简单的有把手的咖啡杯(1属表面),或者如图1a所示的物体(3属表面),不能通过这两种方法完成。为了适当的扫描这些对象,必须使用多个视图点进行扫描。合并来自多个视图点扫描生成的数据点重建一个多面体并非是一项简单的任务。从轮廓的表面:在许多医学研究中很常见的用切片机将生物标本切成薄层。将感兴趣的结构的轮廓数字化。问题是用这些二维轮廓重建三维结构。虽然这个问题已经受到了大量关注,但是当前方法仍然存在着严重的局限性。也许其中最重要的是自动处理分支结构的困难。交互式表面绘制:许多研究人员,包括施耐德和埃森曼,研究二维曲线的产物，通过跟踪笔尖或鼠标的路径作为用户绘制所需的形状。Sachs等人描述一个系统,称为3-Draw,这个系统允许创建三维自由曲线，通过记录笔尖的运动来模拟传感器。这个可以扩展到自由曲面的设计通过忽略这些被记录位置的顺序,允许用户在曲面上任意反复的移动笔尖。问题是重建的曲面要符合无序点的集合。重建算法涉及的这些具有代表性的问题被精心的制作（具体情况具体分析），利用数据中的局部结构。例如,算法解决来自轮廓的曲面的问题大量利用了数据被组织成轮廓的事实(例如封闭多边形),并且这些轮廓位于平行平面上。同样的,专门的算法对于重建来自多个角度深度数据的曲面可能利用每个视角中的数据点的邻接关系。相比之下,我们的方法是构建统一的普遍问题,它不假设在数据点上有任何结构。这种方法具有理论和实践价值。在理论方面,从普遍问题中抽象出来往往揭示了真正问题的关键方面。在实践方面,这个算法可以解决普遍问题可以成为解决特殊问题的实例。1.1术语表面是指“紧凑,连接,可定向的二维流形,可能有边界,被嵌入到三维中”。一个没有边界的曲面被叫做闭合曲面。如果我们想要强调一个表面具有非空的边界,我们将称之为有边的曲面。一个有多个用三角面的分段线性表面将称为简单曲面。我们使用||x||表示向量x的欧式距离,并且我们使用d(X，Y)表示点集X和Y之间的豪斯多夫距离(豪斯多夫距离仅仅是点集X和Y的两个最接近的点之间的距离)。从点集X={x1,x2,x3,……xn}中抽取在或者临近未知曲面M的点。在大多数采样过程中捕获误差,我们假设点集X中的每个点xi都是xi=yi+ei的形式,yi是未知曲面M上的点，并且ei是一个三维的误差向量。我们称这样的样本为X，ξ为噪声，如果对于全部的i,||ei||ξ。ξ的值可以在大多数应用程序中被估计(例如激光扫描仪的精度)。M矩阵的特征与ξ相比之下是很小的，不容易恢复。在发生抽样不足的区域恢复M的特征也是不可能的。特别地,如果M是一个有边界曲面,如一个圆盘删除的球体,是不可能区分是曲面本身的孔洞还是抽样产生的孔洞。为了捕捉采样密度的直觉概念,我们需要另一个定义:令Y={y1，y2，y3，......yn}∈M是一个(没有噪声)表面为M样品。样品Y据说是ρ密集的，如果有球体半径ρ和中心在M中，包含至少一个在Y中的样本点。一个曲面M的有ξ噪声的样品{x1,x2,x3,....xn}∈R据说是ρ密集的，如果存在一个无噪声ρ密集的样品{y1,y2,...yn}属于M，例如xi=yi+ei,||ei||=ξ,i=1,...,n。1.2问题陈述表面重建的目标是确定曲面M(参见图2f),它近似于一个未知的表面M(图1a),使用一个示例X(图1b)和关于抽样过程的信息,例如,噪声等级ξ和采样密度ρ。我们正在努力完善条件关于原始表面M和样例X以至于允许M更可靠地重建。工作仍然只是初步的,我们不能给保证这里给出的算法。然而,该算法在实践中应用得很好,结果可以与原始表面进行对照(见第4节)。2相关工作2.1曲面重建表面重建方法可以根据他们所代表的重建的表面的不同方式进行分类。隐式重建方法试图找到一个光滑函数f:IR3-IR例如{x1,x2,...,xn}是接近零集Z(f)。相对于f的形式和近似的方法他们是不同的。普拉特和Taubin采用平方和最小化豪斯多夫的距离，即从数据点到一个有三个变量的多项式的零集。Muraki将f引入到一个线性组合的三维高斯内核中，使用不同手段和传播技巧。他的拟合优度函数衡量f的密切值在近似于零的数据点上,以及f的零组的单位法线与数据的估计法线的匹配程度。摩尔和沃伦拟合了一个递归地分段多项式,然后连续性使用一种他们称之为“自由形式混合”的技术。与隐式重建技术相比,参数重建技术代表了重建表面作为一个从二维参数域A到IR3的拓扑嵌入f(A)。先前的工作集中在简单拓扑的空间区域,例如平面空间和球面空间。文献9中的黑斯蒂和Stuetzle以及文献26、17中的Vemuri讨论重建表面通过从一个平面区域A到IR3的拓扑嵌入f(A)。文献22、23中的Schudy和巴拉德以及文献4中的布林克利考虑轻微变形球的表面曲面重建问题,因此选择将A变成一个球体。文献24中的Sclaroff和Pentland描述混合隐式/参数法使用变形的超二次曲面将一组点拟合成一个变形的球体。与上面提到的技术相比,我们的方法有几个优点:它只需要一个无组织的在曲面上或接近的点集。不需要额外的信息(如Muraki使用的方法需要的法线信息)。与上述提到的参数曲面重建方法不同,它可以重建任意拓扑结构的表面。与上述提到的隐士曲面重建方法不同,它以自然的方式处理边界,并且它不产生虚假的没有得到数据支持的表面组件。2.2表面重建与函数重建像“曲面拟合”这样的术语出现涉及到两个不同的类的问题:曲面重建和函数重建。曲面重建的目的如前面所陈述的。而函数重建的目标可能如下所述:给定一个表面M,一组点集{xi∈M},和另一组点集{yi∈R},确定一个函数f:M-R,例如f(xi)≈yi。曲面M的区域最常见的是一个嵌入到IR3中的平面,在这种情况下,问题是一个标准在近似理论中被考虑。情况是M被普遍的认为是一个球体。在曲面这个标题下最近的一些关于曲面处理的工作，当M是一般曲面，例如飞机的表面。功能重建的方法可用于曲面简单重建,在特殊情况下,粗略地讲曲面重建是基于一个已知表面M的函数的曲线图。认识到这些特殊情况有多么局限是很重要的——例如,不是每个曲面同胚的球体是球函数的图形。我们想做点是函数重建不能被误解为可以解决一般表面重建问题。3算法描述3.1综述我们的曲面重建算法由两个阶段组成。在第一阶段,我们定义一个函数f:D-R，D∈R3是数据点附近的一个区域,f的估计为到未知的表面M的有符号的几何距离。零集Z(f)是我们对M的估计。在第二阶段中,我们使用一个轮廓线算法通过一个简单表面近似Z(f)。虽然无符号距离函数|f|更容易估计,零不是一个常规的|f|的值。然而,零是常规的f值,因此近似隐函数定理保证了我们近似的Z(f)是流行。对于定义有符号距离函数的关键是关联与每一个数据点所在的又向平面。这些切线平面作为平面的局部线性近似。虽然切平面的结构相对简单,它们方向的选择,给曲面定义一个全局一致的方向是算法面临的主要障碍之一。如图2b所示,切线平面没有直接定义曲面,因为他们的并集可能有复杂的非流行的结构。相反,对于这些曲面我们使用切平面去定义有符号的距离函数。一个简单曲面通过绘制有符号的距离函数的零组来获得的例子，如图2所示。接下来的几个部分将更详细的说明算法的连续步骤。3.2切平面的估计为了定义一个有符号的距离函数第一步计算每个数据点有方向切平面。与切平面Tp(xi)有联系德尔数据点xi被表示为中心点oi,连同单位法向量ni。任意点P∈R3对于切平面的Tp(xi)有符号距离函数被定义为disti(p)=n(p-oi).n。Tp(xi)的中心与法线是由X中与Xi最接近的k个点的集合所决定的,这组点集用Nbhd(xi)来表示，并且被称为xi的k个最近邻。（我们目前认为k是一个指定的参数,虽然在第五节中我们提出一个方法来自动确定k值。）中心和单位法线被计算,这样平面{disti(p)=0}对于Nbhd(xi)来说是最佳最小二乘拟合平面。即中心oi被采集为Nbhd(xi)的质心,并且法线ni使用主成分分析来确定。为了计算ni，构建Nbhd(xi)的协方差矩阵。这是3*3半正定对称矩阵。⊕表示向量运算的外积。如果λ1=λ2=λ3表示CV的特征值与单位特征向量vi1vi2vi3,我们分别选择ni为vi3或-vi3。选择决定切平面的方向,但是它必须这么做,使得附近平面“统一调整方向”。3.3t统一切平面方向假设两个数据点xi,xj∈X在几何上接近。理想情况下,当数据是很密集而且曲面光滑时,相应的切平面Tp(xi)=(oi，ni)和Tp(xj)=(oj，nj)是近似平行的,即nj*nj≈+-1。如果这些平面方向是一致的,那么ni*nj=+1;否则,ni或者nj应该有一个被翻转。很难找到一个一致的全局的方向,使所有成对的“足够接近”数据点都应该有一致的方向。我们可以模拟这些问题作为图表的最优化。这个图包含每切平面Tp(xi)的一个节点Ni,和在Ni与Nj之间的边(i,j),如果切平面中心oi和oj是充分接近的(我们将更精确关于我们所说的尽量足够接近)。边(i,j)编码消耗程度,Ni和Nj是一致的方向并且被看做ni*nj。对于选择切平面统一的方向的问题是最大化图形的总成本。不幸的是,这个问题可以被证明是np困难问题通过对MAXCUT的简化。因此为了有效解决方向问题,我们必须采取一个近似算法。在描述我们使用的近似算法之前,我们必须决定何时这些节点在图中被连接。由于表面被假设的是由单个连接分支组成的,图应该被连接。对于一组点一个简单连通图往往是连相邻的点是欧几里得最小生成树(EMST)。然而,对于我们的目的，切平面中心{o1，...，on}(图1c)的欧几里得最小生成树在边缘位置是不够致密的。因此,我们通过添加边的数量来填充它。具体来说,我们添加边(i,j)如果oi是oj的k个紧邻,或者oj是oi的k个紧邻(k个紧邻被定义为{o1，..，on}对于X)。结果图(图1d)称为黎曼图,因此构建一个连通图,它的编码几何近似切平面的中心。结果图(图1d),称为黎曼图,因此构建一个连通图,它编码了切平面的中心的几何近似。一个相对简单的算法来确定平面的方向是先任意的为一些平面选择一个方向,然后“传递”方向给在黎曼图中相邻的平面。在实践中,我们发现传递方向的顺序是很重要的。图3b显示了可能的结果,在几何近似的基础上唯一的传播方向；正确重建结果如3c所示。直观地说,我们想要选择传播的顺序,支持从Tp(xi)到Tp(xj)的传播，如果无向的平面是近似平行的。通过分配到在黎曼图中的每个边(i,j)的消耗是1-|ni*nj|这些可以被完成。除了非负之外,这个任务属性消耗很小,如果这些无方向的切面是近似平行的。因此，良好的传播秩序可以被实现，通过遍历结果图的最小生成树(MST)。这顺序是有利的,因为它的传播方向往往沿数据曲率最低的方向,从而在很大程度上避免遇到模棱两可的情况，当试图在锐利的边缘上传播方向时(如在图3b中猫耳朵尖的位置)。在图2a所示的最小