【泡泡图灵智库】基于径向基函数的三维物体重建与表示

标题：Reconstruction and Representation of 3D Objects with Radial Basis

作者：J. C. Carr; R. K. Beatson

来源：SIGGRAPH 2001

编译：郑帅康    

审核：万应才，李鑫

摘要

  大家好，今天为大家带来的文章是 --Reconstruction and Representation of 3D Objects with Radial Basis

该文章发表于2001 SIGGRAPH 。

    本文使用径向多谐基函数(RBFs)从点云数据重建光滑的流形表面并修复不完整的网格。物体表面被隐式定义为通过表面数据拟合的RBF零集。快速拟合和评估RBFs的方法使我们能够通过一个RBF来建模包含数百万个表面点的大型数据集，这在以前是不可能完成的。贪心算法在拟合过程中减少了表示一个曲面所需的RBF中心的数量，从而获得了显著的压缩和进一步的计算优势。多谐样条曲线的能量最小化特性使得插值表达式更加平滑。这种尺度无关的特征非常适合从非均匀采样数据重建曲面。孔被平滑地填满，表面被平滑地外推。当数据有噪声时，我们使用非插值近似。函数表示实际上是一个实体模型，这意味着梯度和表面法线可以通过分析确定。这有助于生成均匀的网格，我们证明了RBF表示在网格简化和网格重划分应用方面的优势。

主要贡献

    1)描述了新的快速拟合和评价RBF模型的计算优势。介绍了隐式曲面模型的RBF中心简约，这将显著提高数据压缩率和计算速度。

    2)介绍了用RBF逼近法从噪声数据中重建光滑曲面的方法。将RBFs应用于网格修补（孔填充）和点云表面拟合问题。证明了对非常大的数据集和拓扑复杂的对象建模是可能的。

算法流程

1.曲面隐函数拟合

    我们希望将整个对象建模为一个连续可导的函数。拟合曲面就是找到一个函数满足下式：

    可以使用符号距离函数寻找f，如图2，非平面点(off -surface points)可以沿表面法线投影产生，d可由非表面点到最近表面点(on-surface points)距离确定。

    实验表明用两个非表面点增强一个表面点效果更好。对于无序的点云来说，可以利用局部近似平面估计法线方向，利用一致性或扫描器位置等附加信息描述法线意义。对于模糊的局部点，将其设置为平面上的零点以约束表达函数。

    给定表面法线后，投影非表面点时需要确保其不会与表面其他部分相交，并且其最近表面点为产生它的表面点。此时，重构曲面对投影距离d相对不敏感。

2.径向基函数插值

    在BL空间选取插值s满足：

    BL空间由具有旋转不变性的半范数定义，半范数为函数能量或平滑度的度量，越小越平滑。因此最平滑的插值即寻找最小的s半范数，可以简写为RBF的特殊形式。RBF的一般表达为：

    其中p为低次多项式，为系数，为基函数。如果p阶次为m，则有：

    以c为p的系数，则式3、7可以写成矩阵形式：

    解这个线性系统可以确定和c，然后得到插值s。但B随着数据点的增多约束条件通常变差，经常得不到可靠解，并且需要巨大的存储空间。因此此前RBF通常不适于几千个点以上的问题。

3. 快速方法

  可以利用FMM(Fast Multipole Method)算法进行加速估计。FMM采用近似法，对于RBF即是远场和近场扩展，近似生成分层聚集的中心，因为中心在一个特定的点集中。近似评价离评价点较远的点集和直接评价较近的点集可以使RBF达到预定的精度，并且时间显著减少。如图5，FMM引入拟合精度和评价精度两个参数。拟合精度指定拟合RBF值与插补节点上指定值的最大允许偏差，需要时可以在每个数据点指定不同精度；评价精度指定对拟合RBF进行评估的精度。评价精度小于拟合精度，由此得到光滑连续的RBF。

4.减少RBF中心

    通常近似RBF需要使用所有的输入点以供插补即作为RBF中心，但实际上可以用较少的中心点达到相同的精度。这里使用贪心算法，首先选择一个子集进行拟合RBF，如果所有点的残差满足要求则完成拟合，否则加入新的中心继续拟合，直到精度满足要求。

5.噪声数据RBF近似

    数据含有噪声时，式3则过于严格。为了获得更平滑的拟合，将优化目标改为如下形式：

    参数ρ可以平衡保真度和平滑性，此时式8化为如下形式，仍然可以利用快速方法求解：

5.表面估计

    本文中利用不断扩展的四面体变体优化表面跟随。扩展平面的波前从种子点扩散到整个表面，直到相交或到边界。图10中红色部分表示波阵面。设计中，许多中心将位于或非常接近表面，在非表面点时利用RBF梯度搜索最近的零交点。在表面附近因为梯度近似不变所以收敛速度很快。表面跟随策略不需要3D阵列，可以最小化RBF评估的数量。计算成本随着分辨率的平方而非立方增加，并且节约了内存。由于具有分析评价RBF的能力，可以轻易解决表面模糊问题。

主要结果

   快速方法使得用RBFs表示任意拓扑的复杂对象在计算上成为可能。多谐样条曲线具有尺度无关性和光滑性的插值特性，这使得RBFs特别适合于拟合非均匀采样点云和包含大型不规则孔洞的部分网格的表面。得到了与输入数据最一致、最光滑的曲面。如果充分采样，则可以解析细节。RBF表示的功能特性为曲面配准算法、网格简化、压缩和平滑算法提供了新的可能性。

    图11展示了RBF自动填充空洞的效果，表3对比了RBF与派生网格的内存占用。由于本文为早期开创性文章，重在方法说明，实验结果不再一一展示。

Abstract 

    We use polyharmonic Radial Basis Functions (RBFs) to reconstruct smooth, manifold surfaces from point-cloud data and to repair incomplete meshes. An object’s surface is defined implicitly as the zero set of an RBF fitted to the given surface data. Fast methods for fitting and evaluating RBFs allow us to model large data sets, consisting of millions of surface points, by a single RBF—previously an impossible task. A greedy algorithm in the fitting process reduces the number of RBF centers required to represent a surface and results in significant compression and further computational advantages. The energy-minimisation characterisation of polyharmonic splines result in a “smoothest” interpolant. This scale-independent characterisation is well-suited to reconstructing surfaces from nonuniformly sampled data. Holes are smoothly filled and surfaces smoothly extrapolated. We use a non-interpolating approximation when the data is noisy. The functional representation is in effect a solid model, which means that gradients and surface normals can be determined analytically. This helps generate uniform meshes and we show that the RBF representation has advantages for mesh simplification and remeshing applications. Results are presented for real-world rangefinder data.