在3d heightmap中查找鞍点

Question

给定3d高度图(来自激光扫描仪)，我如何找到saddle points

例如，给定如下内容：

​

​

我正在寻找曲率在一个方向上为正，在另一个方向上为负的所有点。

(这些方向不需要与X和Y轴对齐。我知道如何检查X方向的曲率是否与Y方向的曲率具有相反的符号，但这并不包括所有情况。更糟糕的是，X的分辨率与Y的分辨率不同)

​

​

理想情况下，我正在寻找一种算法，可以容忍一定数量的噪音，并只标记“重要”鞍点。

Answer 1

我一直在探索一个计算拓扑类的类似问题，并使用下面列出的方法取得了一些成功。

首先，您将需要一个比较函数，该函数将计算两个输入点的高度，并为任何输入返回<或>(不等于)。一种方法是，如果点的高度相等，则使用基于位置的索引或随机索引来找到较大的点。你可以认为这是在高度上增加了一个无穷小的微扰。

现在，对于每个点，您将比较所有周围邻居的高度(二维矩形网格上将有8个邻居)。一个点的较低连接将是其高度小于该点的所有邻居的集合。

如果所有相邻的值都在较低的链路中，则您处于局部最大值。如果没有一个点在较低的链接中，则处于局部最小值。否则，如果较低的连接是单个连接的集合，则您位于坡度上的规则点。但是，如果下面的链接是两个未连接的集合，那么您就处于一个马座上。

在2D中，您可以围绕您正在检查的点以循环顺序构建8个邻接点的列表。您可以根据您的比较函数为每个邻居指定值+/-1。然后，您可以遍历该列表(请记住比较两个端点)，并计算符号更改的次数，以确定较低链接中连接的组件的数量。

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

-Michael

Answer 2

(来自数学上的猜测，而不是实际经验)

在每个候选点周围的小块中将二次曲面拟合到曲面上，例如，使用最小平方。面片有多大是控制噪波的一种方法，您可以根据点与候选点的距离对点进行加权。在矩阵表示法中，您可以将二次表示为x‘A+ b'x + c，其中A是对称的。

二次曲线在x= (A^-1)b/2处的梯度为零。如果这不在面片内，则丢弃它。

如果A有+ve和-ve特征值，你在x有一个鞍点。因为A只有2x2，所以最多有两个特征值，你可以忽略当它是零特征值时的情况，所以你不能在前一阶段求逆它。