在3D高度图中查找鞍点

Question

如果给定一个三维高度图（来自激光扫描仪），我该如何找到鞍点？

也就是说，如果有这样的数据：

我正在寻找曲率在一个方向上为正，在另一个方向上为负的所有点。（这些方向不需要与X和Y轴对齐。我知道如何检查X方向上的曲率是否与Y方向上的曲率符号相反，但这并不涵盖所有情况。更糟糕的是，X和Y方向上的分辨率不同。）

理想情况下，我正在寻找一种算法，它能够容忍一定程度的噪声，并且只标记“显著”的鞍点。

- HugoRune

Answer 1

我一直在为计算拓扑课程探索类似问题，并已经成功地使用下面概述的方法。

首先，您需要一个比较函数，该函数将评估两个输入点的高度，并返回“<”或“>”（不相等）。一种方法是，如果点具有相同的高度，则使用基于位置或随机索引来查找更大的点。您可以将其视为向高度添加无穷小扰动。

现在，对于每个点，您将比较所有周围邻居的高度（2D矩形网格上将有8个邻居）。点的较低链接将是所有高度小于该点的邻居的集合。

如果所有相邻值都在较低链接中，则您处于局部最大值。如果没有点在较低链接中，则您处于局部最小值。否则，如果较低链接是单个连接集，则您处于斜坡上的常规点。但是，如果较低链接是两个不连通的集合，则您处于鞍点。

在2D中，您可以按顺时针顺序构造8个相邻点列表以围绕正在检查的点。根据您的比较函数为每个邻居分配+/-1的值。然后，您可以通过该列表（记得比较两个端点）并计算符号更改的次数来确定较低链接中连接组件的数量。

确定哪些鞍点是“重要”的更难分析。您可能希望查看此内容：http://www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Gyulassy08.pdf以获得一些指导。

-迈克尔

- Michael Homel

Answer 2

（从数学猜测而非实际经验中得出）在每个候选点周围的小区域内拟合二次曲面，例如最小二乘法。控制噪声的一种方法是确定区域大小，并且您可能会根据候选点与其距离加权。在矩阵符号表示中，您可以将二次曲线表示为x'Ax + b'x + c，其中A是对称的。

这个二次曲面在x =（A ^ -1）b / 2处具有零梯度。如果不在此区域内，则舍弃它。

如果A具有+ve和-ve特征值，则在x处有一个鞍点。由于A只是2x2，因此最多只有两个特征值，当它具有零特征值时，您可以忽略该情况，因此无法在前一阶段反转它。

- mcdowella