一个C米通信
研究突出了
距离计算的热法
从表面上一个点到的测地线距离。热法允许为新的源点或曲线快速更新距离。
图片来源:斯坦福计算机图形实验室
我们介绍热方法用于解决平面和曲面域上的单源或多源最短路径问题。一个关键的见解是，距离计算可以分为两个阶段:首先找到距离增加的方向，然后计算距离本身。热方法健壮、高效、实现简单，因为它是基于求解一对标准稀疏线性系统。这些系统可以因式分解一次，然后在近线性时间内求解，大大降低了平摊成本。真实的性能比最先进的方法快一个数量级，同时保持相当的精度水平。该方法可以应用于任何维度，任何允许梯度和内积的域，包括规则网格、三角形网格和点云。数值结果表明，该方法在求精范围内收敛到精确的距离;我们还探索了适合于需要更大规律性的应用的距离的平滑近似。
1.简介
多源最短路径问题求的是从域的每个点到给定子集中最近点的距离;这个问题的不同版本是计算机科学和计算数学中大量问题的基础。解至少可以追溯到Dantzig对线性规划的研究35；典型的问题是用加权图来表述的，就像Dijkstra的算法一样。然而，人们通常希望在连续定义域上捕捉距离;一个关键的例子在图1(左)图的距离会高估直线欧氏距离，无论网格变得多么精细。在2D中，一个重要的发展是“精确”算法的制定，其中路径可以穿过三角剖分的面8，27；大量后续工作都集中在制作这些O（n2)算法适用于大型数据集。40，46然而，对于数据分析和科学计算中的问题，并不清楚精确算法的成本和复杂性是否总是合理的，因为三角剖分本身只是真实域的近似图4)．
图1。与沿着图计算最短路径的算法(左)相比，热方法计算的是到连续弯曲区域上点的距离(右)。该方法的一个关键优点是，它是基于稀疏线性方程，可以有效地预分解，从而大大降低了平摊成本。
另一种截然不同的方法是用偏微分方程(PDEs)来表述问题，这种方法可以通过诸如传统的有限元分析来理解域近似误差。然而，连续公式的特定选择对计算有很大的影响。的热方法是受到了瓦拉罕在微分几何上的经典结果的启发42将热扩散和测地距离它测量的是区域内最短、最直的曲线的长度，而不是空间中的直线。我们的关键观察是可以将距离计算分解为两个阶段:首先确定距离增加的方向，然后恢复距离本身。此外，由于每个阶段相当于数值线性代数中的一个标准问题，人们可以利用现有的算法和软件来提高距离计算的效率和鲁棒性。虽然这种方法原则上可以用于图的距离，但它的真正用途在于逼近连续的曲面域上的距离。这种方法已被证明在计算神经科学、几何建模、医学成像、计算设计和机器学习(第2节)的各种应用中都是有效的，并且最近激发了我们原始方法的更精确的变化。3.
1.1.配方
想象一下用一根滚烫的针触碰表面上的一个点。随着时间的推移，热量扩散到区域的其余部分，可以用一个函数来描述kt x（y)称为热内核它测量从热源传递的热量x到达目的地y又一次t。众所周知，热量和距离之间的关系是Varadhan的公式，42也就是说任意两点之间的距离x，y在曲面上可以通过简单的热核点变换得到:
这种行为背后的直觉源于这样一个事实:热扩散可以被建模为大量热粒子的随机移动集合，从x:任何到达遥远点的粒子y过了一小段时间t几乎没有时间偏离最短的可能路径。然而，在此之前，这种关系并没有被计算距离的数值算法所利用。
为什么瓦拉罕的公式在这种情况下被忽视了?主要的原因可能是，它需要精确的热核的数值重建，这是很难得到的公式仅仅是近似kt x不能产生正确的结果，如图2而且8．热法通过使用更广泛的输入类别来规避这个问题，即任何梯度与真距离函数的梯度平行的函数。然后我们可以将计算分为两个阶段:首先找到梯度，然后恢复距离本身。
图2。给定热核的精确重建(左上)，瓦拉罕公式可以用于恢复测地线距离(左下)，但在近似或数值误差(中，右)的存在下失败，如图中一维点源所示。热法的鲁棒性源于这样一个事实:它只依赖于方向梯度的。
与现有算法相比，热法有两个主要优点。首先，它几乎可以应用于任何类型的几何离散化，包括规则网格、多边形网格和点云。其次，它只涉及稀疏线性系统，可以预先分解一次，并快速求解多次。对于需要在固定几何域上重复查询距离的应用程序，这一特性大大降低了平摊成本。此外，由于热法是建立在科学计算中广泛使用的标准线性pde基础上的，它可以立即利用数值线性代数和并行化的新发展。
图3。热法计算到给定定义域子集的最短距离。灰色曲线表示距离函数的等值线。
2.相关工作
距离计算的主流方法是求解程函方程
取决于边界条件/在定义域的某个子集上(如点或曲线)= 0。直观地看，这个方程说的很简单:当我们远离原点时，距离函数必须以“每米一米”的速率变化。然而，在计算上，这个公式是非线性和双曲的，使得它很难直接求解。通常情况下，人们会采用一种迭代松弛方案，如gauss - seidel特殊的更新顺序快速行进而且快速扫，这是在规则网格上计算距离的一些最流行的算法37三角形曲面。19这些算法也可以用于隐式曲面，25点云,26还有多边形汤，7但这只是间接的:距离是在近似原始域的简单网格或规则网格上计算的。由于需要非钝角三角剖分(这是众所周知的难以获得的)，或者需要迭代展开过程来保持解的单调性，在简单网格上实现快速推进具有挑战性;此外，这些问题没有在大于两个维度上得到很好的研究。的渐近复杂度O（n日志n),O（n)，但扫描往往较慢，因为需要大量的扫描以获得准确的结果。16
图4。单位球上距离近似对平均边长的收敛性作为比较的基准，我们使用解析解(x，y) = cos－1（xy)．请注意，即使有一个漂亮的镶嵌，沿着多面体的确切距离只收敛于沿着它所近似的球体的真实距离的二次方。(线性收敛和二次收敛用虚线表示，以供参考。)
这些方法的一个缺点是它们不能重用信息:每次到不同源集的距离必须完全从头计算。还要注意的是，扫描和移动都对并行化提出了挑战:优先队列本质上是串行的，而不规则网格缺乏自然的扫描顺序。
在另一项研究中，米切尔等人。27给出一个O（n2日志n)算法，用于计算从单个源到三角形曲面所有其他顶点的精确多面体距离。Surazhsky等人。40在实践中证明了该算法在次二次元时间内运行，并给出了近似解O（n日志n)有保证误差界的算法版本;庞姆斯和狗头带4将算法扩展到多边形源。类似于快速推进，这些算法使用优先队列以波前顺序传播距离信息，再次使它们难以并行化。更重要的是，这些算法(在许多不同的源子集上)的平摊代价比heat方法要大得多，因为它们不重用从一个子集到下一个子集的信息。最后,尽管40这些算法极大地简化了原始公式，但实现起来仍然具有挑战性，并且不能立即推广到除三角形网格以外的领域。
图5。热方法已被应用于各种需要重复测地线距离查询的任务。这里，测地距离驱动差分增长模型(左)，用于计算设计(右)。图片由神经系统/Jesse Louis-Rosenberg提供。
与我们的方法最接近的是Rangarajan和Gurumoorthy最近的方法，32他们似乎并不知道瓦拉达恩的公式，而是在距离函数和与时间无关的Schrödinger方程的解之间推导出类似的关系;这个推导只适用于平坦的欧几里得空间，而不适用于一般的曲面域。此外，他们使用快速傅里叶变换计算解，这将计算限制在规则网格。
对热方法的轻微修改允许我们计算平滑的距离函数，这在急剧不连续可能导致后续数值困难的情况下非常有用。以前的平滑距离近似提供了这种规律性，代价是真实几何长度的近似很差10，14，21，33；参见3.3节进行比较。
图6。加热法的三步。(我)热u允许扩散一段时间(左)。(二)温度梯度u(中左)归一化并负，得到单位向量场X(中右)指向测地线。(三)函数它的梯度X恢复最终距离(右)。
最近，热方法促进了计算科学和数据分析中的各种任务。例如，Huth等人。15利用快速距离查询优化皮质组织的概率模型van Pelt等人。41运用热法辅助脑动脉瘤评估;邹等人。47使用热法进行有效的刀具路径规划;所罗门等人。38利用我们的方法有效地解决几何域上的最优输运问题;Lin等人。20.将这种方法应用到向量值数据的流形学习环境中。图5展示了基于差分生长的热法的实际设计应用。对原始算法也进行了各种改进;例如，de Goes等人。13杨和科恩45描述了将该方法推广到精确计算各向异性距离的两种不同方法;它也被改编为体素化6C1有限的元素,29再细分曲面。12最后是Belyaev和Fayolle3.提供我们的方法的变分解释，观察到更精确的结果可以通过迭代热方法，或通过应用更复杂的下降策略。
3.加热法
热法的一个有用的特点是，基本算法可以用纯连续的设置来描述(即，用曲面来表示，或者更一般地说，光滑的曲线)，而不是离散的数据结构和算法。换句话说，在这一点上，人们不应该想象我们已经选择了一个特定的数据结构(三角形网格、网格、点云等)或甚至维度(2D、3D等)。相反，我们关注一个通用的原则，它可以应用于不同维度的许多不同领域。稍后我们将探讨空间和时间离散化的几种特殊选择(第3.1和3.2节);在最近的文献中探索了进一步的替代方法。13，29，45
图7。在平面上的一个区域(左)或空间上的一个曲面(右)的边界上的距离是通过沿着边界曲线简单地放置热量来实现的。
一般来说，热法可以应用于任何情况，只要有梯度算子，散度算子，拉普拉斯算子=·向量演算的标准导数，可能推广到弯曲域。用这些运算符表示，加热法包括三个基本步骤:
函数近似于一个给定的源集的距离，接近于真实的距离t趋于0(公式1)。例如，恢复到一个点的距离x我们使用初始条件u0= (x)，即编码热量“无限峰值”的狄拉克δ。更一般地，我们可以通过让得到到任意子集的距离u0是广义狄拉克分布42本质上是一个指标函数;看到图3而且7．注意，由于(III)的解只确定到一个加性常数，最终值被移动，使最小距离为零。
热法的动机如下。考虑一个近似ut固定时间内的热流t。除非ut显示了精确的衰变速率，瓦拉罕的转变
将产生真实测地线距离的糟糕近似值，因为它对幅度的误差高度敏感(见图2而且8)．热法要求一些不同的东西:它只要求梯度ut指向正确的方向，即平行于。幅度可以被安全地忽略，因为我们知道(从eikonal方程)真距离函数的梯度有单位长度。因此我们计算归一化梯度场X＝ut/|ut|，通过最小化求最接近的标量势
，或者等价地，通过求解相应的欧拉-拉格朗日方程=·X。36整个过程描述在图6．
图8。左:瓦拉丹公式。对的;加热法。即使对于非常小的值t，简单地应用Varadhan公式并不能提供测地线距离的精确近似值(左上);的大值t间距变得更加不均匀(左下)。将梯度归一化可以得到更精确的解，如均匀间隔的等值线(右上)所示，并且在构造平滑的距离函数(右下)时也很有价值。
这个过程被用作离散算法家族的起点，如第3.13.3节所述。请注意，有些细节从这个手稿中被省略了，可以在Crane等人的书中找到。11
3.1.时间离散化
为了将我们的连续过程(算法1)转化为离散算法，我们必须用合适的近似替换空间和时间上的导数。算法1第1步的热方程可以用一个固定时间的反向欧拉步骤在时间上离散化t实际上，这意味着我们只需解线性方程
在整个定义域米，其中id表示标识运算符。注意，在这一点上，我们仍然没有离散化空间;空间离散化在第3.2节中讨论。通过考虑椭圆边值问题，我们可以更好地理解式(3)的解
对于点源，哪一个能得到解t等于ut直到一个乘法常数。正如Varadhan在他对式(1)的证明中所建立的，t也与距离有着密切的关系，即
这种关系确保了步骤II和III的有效性，因为转换应用于t保留渐变的方向。
3.2.空间离散化
在这里，我们详细介绍了heat方法在三角形网格、多边形网格和点云上的几种可能的实现。注意，热方法也可以用于任何维数的平坦欧几里得域，只需在规则网格上应用标准有限差分即可;Belyaev和Fayolle3.在四面体(3D)网格上的大纲实现。
图9。由于热法是基于像拉普拉斯算子这样的成熟的离散算子，它很容易适应各种几何域。上图:由高度非平面(有时非凸)多边形面组成的河马的距离。
三角形网格。让u|v|在有顶点的三角曲面上指定分段线性函数V,边E，以及面孔F。拉普拉斯算子在顶点处的标准离散化我由
在哪里一个我是否三分之一是所有三角形在顶点上的面积我，对所有相邻顶点求和j,ij，ij是对应边的对角。23我们可以用一个矩阵来表示这个运算l＝米－1lC,在那里米|v|×|v|是否包含顶点区域和的对角矩阵lC|v|×|v|是cotan运营商表示剩下的和。然后可以通过求解对称正定系统来计算热流
在哪里是克罗内克函数(或指示函数)除以。给定三角形的梯度可以简洁地表示为
在哪里一个f是三角形的面积，N它的外单位是否正常，e我是我边向量(逆时针方向)，和u我的值u在相反的顶点。与顶点相关的积分散度我可以写成
对入射三角形的和j每个都有一个向量Xj，e1,e2这是三角形的两个边向量吗j包含我,1，2是对角。如果我们让b|v是归一化向量场的(积分)散度的向量X，然后通过求解对称泊松问题计算最终距离函数
如3.1节所述，第1步的解是一个随距离呈指数衰减的函数。幸运的是，小值的归一化不是问题，因为浮点除法只涉及整数指数的算术;同样，由于梯度计算是局部的，所以幅度的大范围并不会对精度产生不利影响。对于本身的计算，我们主张使用双精度的直接(Cholesky)求解器;经验上，我们观察到在整个域上大致一致的点相对误差。
图10。热法可以直接应用于散点云。左:带孔和噪声的人脸扫描。右图:小猫表面连通性被移除。黄色的点靠近光源。
多边形网格。曲面通常用既非平面也非凸的多边形来描述;尽管这样的多边形当然可以被三角化，但这样做会对现有的计算管道产生不利影响。相反，我们利用Alexa和Wardetzky的多边形拉普拉斯矩阵1要在多边形网格上直接实现热方法，在这种设置中唯一的挑战是，对于非平面多边形，梯度向量不再具有明确的几何意义。注意到我们只需要大小|，这个问题就解决了u梯度的|;参见Crane等人，11详见第3.2.2节。图9演示在不规则多边形网格上计算的距离。
点云。原始几何数据通常表示为离散点样本Pn光滑的表面M。我们不需要将这些数据转换成多边形网格，而是可以使用Liu等人的点云拉普拉斯式直接实现热法，22这扩展了Belkin等人之前的研究。2梯度和散度的计算由Crane等描述，113.2.3节。其他离散化当然是可能的(例如，参见罗等人的工作)。23）;我们选择了一个在任何维度上都易于实现的方法。特别有趣的是，热法的成本主要取决于内在维度n的米，而基于快速推进的方法需要相同维度的网格米作为环境空间25这种区别在像机器学习这样的环境中尤为重要米可能明显大于n。
选择时间步长。热法的准确性部分取决于时间步长t。在光滑设置下，式(5)表明，的值越小t产生较好的测地线距离近似值。相反，在离散条件下，我们观察到(3)式的极限解只依赖于数量对顶点之间的边，独立于我们如何尝试将边的长度合并到我们的公式中，参见Crane等人，11因此，在一个固定的网格上递减的值t不一定提高精度，即使在精确算术中，为了提高精度我们也必须同时细化网格并相应地降低t。而且，非常大的值t产生测地线距离的过平滑近似(第3.3节)。因此，对于一个固定网格，我们寻求一个最佳的时间步长t＊它既不太大也不太小。
图11。斯坦福兔正面的光源会导致对面不光滑的尖端。通过运行热流逐步延长持续时间t，我们得到了测地线距离的平滑近似(右)。
的最优值t＊由于涉及切割轨迹分析的复杂性，难以获得。28相反，我们使用一个在实践中很有效的简单估计，即t＝mh2在哪里h相邻节点之间的平均间距是米> 0是一个常数。这个估计是基于这样一个事实h2在规模和细化方面是不变的;数值实验表明米= 1对于各种各样的问题产生接近最佳的准确性。本文研究的是时间步长
因此，在所有测试和示例中统一使用，除非我们明确寻求距离的平滑近似，如3.3节所述。对于高度不均匀的网格，可以设置h到最大间距，提供一个更保守的估计。数值下溢在理论上可以发生在非常小的情况下t，虽然我们在实践中没有遇到这个问题。
图12。第一行:我们对测地线距离(左)和双谐波距离(中)的平滑近似都缓解了在精确距离(右)中发现的尖锐“尖”，但我们的近似提供了更均匀的等等值线间距。下一排:双谐距离(中间)倾向于在源附近显示椭圆水平线，而我们的平滑距离(左边)保持各向同性的圆形轮廓，就像在精确距离(右边)中看到的那样。
数字。如在图10，18,19，不需要特别好的网格或点云就可以得到合理的距离函数。然而，与任何数值方法一样，解的精度和其他性质可能受到网格质量的影响。例如，在某些应用中，人们可能希望避免“伪极小值”，即不出现在真(平滑)距离函数中的局部极大值或极小值。目前，包括精确多面体格式在内的任何数值格式都不能保证任意网格上不存在伪极小值。17然而，根据经验，我们观察到热法产生的伪极小值比快速推进法或双谐距离法都要少图20)，部分原因是来自霍奇步骤(步骤III)的正则化。在希望完全避免伪极小值的情况下，我们主张使用德劳内网格。
3.3.平滑的距离
测地线距离在点处不能平滑切位点，即没有唯一最短路径到达源的点，这些点在距离函数的水平线上表现为尖点。对于需要对距离函数求导的应用程序(例如，水平集方法)，非光滑性可能导致数值上的困难，或者可能只是在美学上不受欢迎。
图13。Neumann(左上)、Dirichlet(右上)和平均值(左下)边界条件对平滑距离的影响。平均边界条件模拟没有边界的同一表面的行为。
一些距离的设计考虑到了平滑性，包括扩散距离，10通勤时间距离,14和双谐距离21(有关更详细的讨论，请参阅最后的参考资料)。这些距离满足许多重要的性质(平滑性，等距不变性，等)，但是真实测地线距离的差近似值，如等值线的不均匀间距所示(见图12、中)。它们的计算成本也很高，需要为每个顶点求解一个线性系统，或者计算拉普拉斯矩阵的大量特征向量(实际上是150到200)。
图14。对于路径规划，测地线的行为可以通过边界条件和时间步长来控制t。左上:诺伊曼条件鼓励边界粘连。右上:狄利克雷条件鼓励回避。的小值t屈服标准直线测地线。的大值t产生更自然的轨迹。
相反，我们可以通过简单地对的大值应用热法来快速构建测地线距离的平滑近似t（图11)．的计算代价保持不变，等值线是均匀间隔的t由于归一化(步骤II);解是等距不变的，因为它只依赖于本征算子。对于时间步长t＝mh2，有意义的价值米都在1 - 10的范围内6过了这一点，这个术语t主导，导致很少可见的变化。
3.4.边界条件
为了解第1步和第2步的方程，我们必须定义边界附近导数的行为。直观地说，我们的距离近似的行为不应该受到边界形状(图13)，例如，切掉凸域的一个角应该不会影响剩余点的距离。对于精确的距离计算，我们可以采用标准zero-Neumann或zero-Dirichlet边界条件，因为这个选择不影响光滑极限解的行为(参见Renesse44推论2和Norri，30.定理1.1)。然而，边界条件确实会改变我们平滑距离的行为。尽管对于这个光滑函数没有定义明确的“正确”行为，我们主张使用通过取诺伊曼解的平均值获得的边界条件uN和狄利克雷解uD，即，
．这种行为背后的直觉又来源于随机漫步者的解释:零狄利克雷条件吸收热量，导致漫步者“跌落”定域边缘。诺伊曼条件防止热量流出定域，有效地“反映”随机行走者。平均条件模拟无边界域的行为:离开的步行者数量等于返回的步行者数量。图14显示边界条件如何影响测地线的行为在一个路径规划方案。
4.评价
4.1.性能
热法的一个关键优点是第I步和第III步中的线性系统可以被预先分解。我们的实现使用了稀疏的Cholesky分解，9对于泊松型问题，哪一个保证了次二次元复杂度，但在实践中伸缩性更好5；此外，有强有力的证据表明，由椭圆偏微分方程产生的稀疏系统可以在非常接近线性的时间内求解。34，39独立于这些问题，具有大量右侧的问题的平摊代价大致是线性的，因为反向替换可以在基本上线性的时间内应用。在我们的实现中，见插入的相对成本的分解;势是在第三步中计算右手边的时间。
表1。与快速行进和精确多面体距离的比较
在实践中，许多因素影响热方法的运行时间，包括空间离散化、离散拉普拉斯和几何数据结构的选择。作为一个典型的例子，我们将三角形网格截面的方案与Kimmel和Sethian的一阶快速推进方法进行了比较19和Mitchell等人的精确算法，27使用最先进的快速推进实现Peyré和Cohen31以及对基尔萨诺夫的精确执行。40热法是在ANSI C中使用一个顶点-面邻接表实现的双精度。单线程性能是在2.4 GHz Intel Core 2 Duo (表1)．注意，即使是在单距离计算中，热法也优于快速行进法;更重要的是，新子集的更新距离始终比快速推进和精确算法快一个数量级(或更多)。
图15。使用的网格表1．从左到右:兔子，伊希斯，马，宾巴，阿芙罗狄蒂，狮子，拉美西斯。
4.2.精度
我们检查了热法的误差，快速推进法，19多面体距离，27相对于平均边长h在三角曲面上。快速推进法和热法都表现出线性收敛性;有趣的是，即使是精确的多面体距离也只能提供二次收敛。记住这个事实，表1使用多面体距离作为基线，以比较更复杂的几何图形max是最大误差的百分比，网格直径和平均是平均相对误差在每个顶点。注意，快速推进往往获得更小的最大误差，而热法平均做得更好。图16给出了一个可视化的精度比较;唯一值得注意的差异是在尖尖处有轻微的平滑，这可能解释了较大的最大误差。图17表明平滑不干扰切割轨迹的提取，在这里我们可视化值||高于一个固定的阈值。总的来说，热方法显示出与快速推进相同的顺序和量级的误差(在较低的计算成本下)，因此适用于目前使用快速推进的应用;参见Crane等人。11要进行更广泛的比较。
图16。视觉比较的准确性。左:精确多面体距离。使用默认参数，热法(中)和快速推进(右)都产生了相当精度的结果，这里在不到1%的多面体距离内表1以便进行更详细的比较。
图17。平假名字母“a”的中轴通过阈值二阶导数提取到边界的距离。左:快速行进。右:加热法。
热方法的最新实现通过使用不同的空间离散化来提高精度，29或者通过迭代更新解决方案。3.的选择决定了快速推进方案的精度更新规则已经为规则网格开发了许多高度精确的规则(例如，HJ WENO)18)，但在三角形网格等不规则域上可用的选项很少，主要的选择是Kimmel和Sethian的一级更新。19最后，Surazhsky等人的近似算法。40提供了一种有趣的比较，因为在相同的计算成本下，它往往产生比快速推进更准确的结果。然而，精度是相对于测量多面距离而不是光滑的测地线距离的近似曲面。与快速行军一样，Surazhsky的方法没有利用预计算的优势，因此显示出明显高于热方法的平摊代价;它也仅限于三角形网格。
图18。光滑的测地线距离在极差的三角剖分与显著的噪声音符，小的孔基本上被忽略。还要注意，即使是在鼻子上的细条上，距离也很接近。
图19所示。鲁棒性测试。左:我们平滑的距离(米= 104)在不同分辨率的网格上表现相似。右图:即使对于有严重噪声的网格(上)，我们在原始表面上恢复了距离函数的良好近似(下，在无噪声网格上可视化)。
图20。在任何基于有限元近似的方法中，网格质量都会影响解的质量。然而，由于热法是基于求解低阶椭圆方程(而不是高阶或双曲方程)，它通常产生较少的数值伪影。例如，在这里，我们强调了由快速推进法(左)、双谐距离(中)和热法(右)在急性德劳内网格(上)和严重简并网格(下)上产生的距离函数(即局部极大值和极小值)中的伪极值。插图显示了底部图的等值线的特写视图。
4.3.鲁棒性
两个因素有助于热方法的鲁棒性，即(1)使用无条件稳定的时间离散化和(2)椭圆而不是双曲线公式(即相对稳定的局部平均与更敏感的全局波前传播)。图19验证热方法即使在离散性差或被大量噪声(这里建模为应用于顶点坐标的均匀高斯噪声)破坏的网格上也能继续良好工作。在本例中，我们使用较大的值t为了研究我们平滑距离的行为;类似的行为观察到小t值。图18说明了该方法在含有许多小孔和长条子三角形表面上的鲁棒性。
5.结论
热法是一种简单的、通用的方法，可以很容易地合并到一大类算法中。然而，还有大量的问题需要进一步研究，包括可选空间离散化的进一步研究，以及精化下收敛性的形式化分析。进一步探索参数t还为未来的工作提供了一种途径(特别是在可变间距的情况下)，但应该注意到，就平均误差而言，现有的估计已经优于快速行进(表1)．另一个自然的问题是，类似的变换是否可以应用于更大的一类汉密尔顿-雅可比方程;将类似的原理应用于与连续域不直接相似的域(如加权图)上的距离计算，同样是诱人的。
致谢
这项工作由谷歌博士奖学金和Fraunhofer Gesellschaft的拨款资助。感谢Michael Herrmann的鼓舞人心的讨论。提供网格由斯坦福计算机图形实验室，AIM@Shape库，Luxology LLC和Jotero GbR (http://www.evolution-of-genius.de/)．
参考文献
1.Alexa, M.， Wardetzky, M.广义多边形网格上的离散拉普拉斯算子。ACM反式。图30， 4(2011)， 102:1102:10。
2.贝尔金，孙娟，王勇。基于点云的拉普拉斯算子构造Rd．在离散算法第二十届ACM-SIAM年会论文集，SODA'09(纽约，2009)。工业与应用数学学会，费城，PA，美国，10311040。
3.Belyaev, A, Fayolle, p。基于变分和pde的距离函数逼近。第一版。图。论坛34， 8(2015)， 104118。
4.庞梅斯，科贝尔特，L.三角形网格上多边形曲线测地线距离场的精确计算。在视觉、建模和可视化研讨会论文集(VMV)(Saarbrücken，德国，2007年11月79日)，151160。
5.Botsch, M.， Bommes, D.， Kobbelt, L.网格处理的有效线性系统求解器。在IMA曲面数学会议， R.R.马丁，贝兹阁下和M.A.萨宾主编。3604卷计算机科学课堂讲稿(2005)。施普林格,6283年。
6.卡萨尔德，科乔利，D，盖斯，P。用于数字几何工具和算法库的离散外部微积分包(2015)
7.Campen, M.， Leif K.在破碎的网格上行走:容错测地线距离和参数化。第一版。图。论坛30， 2(2011)， 623632。
8.陈建军，韩勇。多面体上的最短路径。Sympos。第一版。几何学。在第六届计算几何年会论文集SCG'90(美国加利福尼亚州伯克利，1990年)。ACM，美国纽约360369。
9.Chen Y.， Davis, T.A, Hager, W.W, Rajamanickam, S.算法887:CHOLMOD，超节点稀疏chololesky分解和更新/下修。ACM反式。数学。Softw 35。， 3(2008年10月)，14页，第22条。
10.Coifman, r.r.， Lafon, s扩散图。达成。第一版。哈蒙。21肛门。(2006), 530。
11.K. Crane, Weischedel, C. Wardetzky, M.热测地线:基于热流计算距离的新方法。ACM反式。图32。， 5(2013)， 152:1152:11。
12.德戈斯，德布伦，梅耶，德罗斯，t。几何处理的细分外部微积分。ACM反式。图。35,4(2016)。
13.de Goes, F.， Liu, B.， Budninskiy, M.， Tong, Y.， Debrun, M.三角剖分上的离散2张量场。第一版。图。论坛33， 5(2014)， 1324。
14.弗斯，F，皮罗特，A，渲染，j - m。，米arco, S. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation.IEEE反式。"。数据工程师19， 3(2007)， 355369。
15.胡斯，格里菲思，特尼森，葛朗，实用主义:皮质铺地区域的概率和生成模型。arXiv: 1504.03622(2015)。
16.eikonal方程:数值效率vs.算法复杂度。在算法学报(2005)。布拉茨斯拉维亚索尔瓦克大学，布拉茨斯拉维亚，2231。
17.解冻:在曲面的三角剖分上近似切割轨迹的工具。13 .数学， 3(2004)， 309325。
18.姜国强，彭。HamiltonJacobi方程的加权ENO格式。SIAM J. science。第一版21(1997), 21262143。
19.Kimmel, R, Sethian, J.A.三角域上的快速推进方法。自然科学学报95(1998), 83418435。
20.林斌，季勇，何晓霞，叶杰。基于矢量场热流的测地线距离函数学习。在第31届国际机器学习会议论文集，ICML 2014(北京，中国，2014年6月2126)国际米兰。相依马赫。学习。(2014), 145153。
21.利普曼，鲁斯塔莫夫，r.m.，芬克豪瑟，T.A.双谐距离。ACM反式。图29。第27条，第3(2010年7月)，11页。
22.刘勇，Prabhakaran, B.，郭欣。基于点的流形谐波。IEEE反式。粘度第一版。图18。， 10(2012)， 16931703。
23.罗振华，萨法，吴晓明，吴晓明。基于扩散度量的网格和点云近似梯度。第一版。图。论坛28， 5(2009)， 14971508。
24.用电网络方法求解偏微分方程。加州理工学院博士论文(1949年)。
25.隐式超曲面上加权距离函数和测地线的快速计算。j .第一版。phy。173(2001), 730764。
26.的子流形上的距离函数和测地线d还有点云。应用。65年数学。， 4(2005)， 12271260。
27.Mitchell, J.， Mount, D.， Papadimitriou, C.离散测地线问题。16 .康普特， 4(1987)， 647668。
28.尼尔，斯特洛克，D.通过热核分析切割轨迹。测量员Diff. Geom(2004), 337349。
29.阮涛，卡尔乔斯卡斯，K。C1二维和三维流形的非张量积有限元。达成。数学。第一版。(2016)。
30.李普希茨黎曼流形中的热核渐近和距离函数。数学学报179， 1(1997)， 79103。
31.Peyré， G.， Cohen, L.D.章测地线计算用于快速和精确的曲面重网格和参数化。在非线性微分方程及其应用研究进展。第63卷(2005)。施普林格,157171年。
32.兰加拉扬，A.， Gurumoorthy, K.一个快速Eikonal方程求解器使用Schrödinger波动方程。技术报告REP-2011-512。CISE，佛罗里达大学，2011年。
33.R.鲁斯塔莫夫，利普曼，Y.芬克豪瑟，T.用重心坐标计算的内部距离。第一版。图。几何处理专题讨论会， 5(2009年7月)，12791288。
34.在二维一般网格上求解椭圆问题的快速直接求解器。j .第一版。phy。231， 4(2012)， 13141338。
35.关于最短路径问题的历史。Docum。数学。1(2012), 155167。
36.施瓦兹,G。Hodge分解:求解边值问题的一种方法。施普林格，柏林，1995。
37.Sethian,正当水平集方法和快速推进方法:计算几何、流体力学、计算机视觉和材料科学中的进化界面。剑桥大学出版社，剑桥，1996。
38.Solomon, J.， de Goes, F.， Peyré， G.， culturi, M.， Butscher, A.， Nguyen, A.， Du, T.， gu, L.卷积Wasserstein距离:几何域上的高效最优运输。ACM反式。图34。， 4(2015)， 66:166:11。DOI:http://dx.doi.org/10.1145/2766963．
39.斯皮尔曼，地方检察官，滕，s.h ..图划分、图稀疏化和求解线性系统的近线性时间算法。在ACM符号。理论第一版。(获得STOC ' 04)(2004)。ACM, 8190年。
40.Surazhsky, V.， Surazhsky, T.， Kirsanov, D.， Gortler, S.J.， Hoppe, H.网格上的快速精确和近似测地。ACM反式。图24。， 3(2005)， 553560。
41.van Pelt, R, Gasteiger, R, Lawonn, K, Meuschke, M, Preim, B.脑动脉瘤治疗评估的比较血流可视化。第一版。图。论坛33， 3(2014)， 133140。DOI:http://dx.doi.org/10.1111/cgf.12369
42.变系数热方程基本解的性质。Comm. Pure应用。数学。202(1967)， 431455。
43.随机几何中的几何测度理论方法。博士论文。Università degli Studi di Milano(2006)。
44.冯·瑞内斯，m.k。曲率下有界的Alexandrov空间的热核比较。Poten。21肛门。， 2(2004)， 151176。
45.杨福，科恩，L.通过图像和表面上各向同性和各向异性热方程的测地线距离和曲线。j .数学。影像可见15,2(2015), 210228。
46.颖，X，欣，s - q。，He, Y. Parallel Chen-Han (PCH) algorithm for discrete geodesics.ACM反式。图33。， 1(2014)， 9:19:11。DOI:http://dx.doi.org/10.1145/2534161．
数字图书馆是由计算机协会出版的。版权所有©2017 ACM, Inc.
没有找到条目