给定 3d 高度图（来自激光扫描仪），我如何找到鞍点？
即给出这样的东西：
我正在寻找曲率在一个方向上为正而在另一个方向上为负的所有点。
（这些方向不应该与X和Y轴对齐。我知道如何检查X方向的曲率是否与Y方向的曲率具有相反的符号，但这并不涵盖所有情况。更糟糕的是, X 中的分辨率与 Y 中的分辨率不同)
理想情况下，我正在寻找一种可以容忍一定量噪声并且只标记“重要”鞍点的算法。
问问题
1395 次
2 回答
3
我一直在探索计算拓扑类的类似问题，并通过下面概述的方法取得了一些成功。
首先，您需要一个比较函数，该函数将评估两个输入点的高度，并为任何输入返回 < 或 >（不等于）。一种方法是，如果这些点的高度相等，则使用一些基于位置或随机索引来找到更大的点。您可以将其视为在高度上添加了一个无穷小的扰动。
现在，对于每个点，您将比较所有周围邻居的高度（在 2D 矩形网格上将有 8 个邻居）。一个点的较低链接将是高度小于该点的所有邻居的集合。
如果所有相邻值都在较低的链接中，则您处于局部最大值。如果没有一个点位于较低的链接中，则您处于局部最小值。否则，如果下连杆是单个连通集，则您位于斜坡上的常规点。但是，如果下面的链接是两个不相连的集合，那么您就处于劣势。
在 2D 中，您可以在要检查的点周围按循环顺序构建 8 个相邻点的列表。根据您的比较函数，您为每个邻居分配一个 +/-1 的值。然后，您可以逐步浏览该列表（记住比较两个端点）并计算符号更改的次数以确定下部链接中连接组件的数量。
确定哪些鞍座是“重要的”是一个更困难的分析。您可能希望查看以下内容：http ://www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Gyulassy08.pdf以获得一些指导。
-迈克尔
于 2013-05-02T19:32:57.880 回答
2
（来自对数学的猜测而不是实践经验）
在每个候选点周围的小块中将二次拟合到曲面，例如使用最小二乘法。补丁的大小是控制噪声的一种方法，您可以通过加权点来获得，具体取决于它们与候选点的距离。在矩阵表示法中，您可以将二次方程表示为 x'Ax + b'x + c，其中 A 是对称的。
二次方程在 x = (A^-1)b/2 处的梯度为零。如果这不在补丁中，请将其丢弃。
如果 A 同时具有 +ve 和 -ve 特征值，则您在 x 处有一个鞍点。由于 A 只有 2x2 并且最多有两个特征值，因此您可以忽略它为零特征值的情况，因此您无法在前一阶段将其反转。
于 2012-08-08T17:58:26.950 回答