如何在距离场中找到山谷和交叉点？

Question

我有一个代表高度的二维数组。它包含峰值，然后是峰值之间的线性梯度。

我根据峰的位置自己生成数组。梯度只是到最近峰值的距离。因此，实际阵列的分辨率高于发布图像的分辨率。

（本来我只发布了白色/蓝色的图像，其余的我保持原样）

原始图像（阵列的可视化）：

我想找到山谷及其交叉点，作为一组线段，如下所示。

我知道寻找最小值的各种方法，但没有办法明确地找出它们之间的确切交点和线段。

我已经为此工作了很长时间，但一无所获。我尝试过如下所示的操作（arr 是数组）：

minima = (arr != scipy.ndimage.minimum_filter(arr, size=10, mode='constant', cval=0.0))
modified_arr = np.where(minima, arr, 1500)

我还尝试使用与上面类似的代码分别显式地迭代行/列。这两种方法都是“参差不齐”的，它们在绘制时识别出很多山谷，但它们不是完全连接的线段。

至关重要的是，我还没有弄清楚如何定义交叉点的位置以及交叉点之间由山谷形成的线段。谁能帮我指出正确的方向？

如果可能的话，我还想知道交点的实际深度值。

从数学上讲，我知道交点是由距三个峰等距离的点定义的，而谷是由距两个峰等距离的点定义的。

TL;DR - 我想找到一组线段的交叉点/山谷，有人可以帮忙吗？

更新
我已经完成了一部分。这有点粗糙，但是下面确实找到了所有的交叉点和山谷，除了找到了额外的点。这是因为我发现能够始终如一地发现所有交叉点/山谷的唯一方法是留出余量。另外，左上角有一个额外的交叉点和山谷，我忘了在原始图片中指出这些，实际上在另一个山峰旁边有第二个山峰。 我必须玩弄顶部的“神奇数字”才能找到一个快乐点，其中找到所有交叉点/山谷，但不包含太多点。

我目前的前进想法是将 K 均值应用于交叉点以找到这些点的质心。对于山谷，我不太确定，可能会考虑定义附近山谷点相对于交叉点的角度，然后找到哪个交叉点位于同一角度。我还考虑将发现的山谷点限制在交叉点一定距离内的那些点，这可能使 K 均值也适用于这些点。

如果有人有什么要补充的，我将不胜感激。否则，当我到达那里时，我会发布进一步的结果。

max_int_diff = 0.85  # max intersection difference
max_valley_diff = 0.45  # max valley difference
max_edge_dist = 2  # max distance from edge of graph
intersections = []
valleys = []
for i in range(arr.shape[1]):
    for j in range(arr.shape[0]):
        dists = [(hypot((i - node.x), (j - node.y)), node) for node in peaks.values()]
        closest = sorted(dists, key=lambda _x: _x[0])
        # intersections
        diff_1_2 = abs(closest[0][0] - closest[1][0])
        diff_1_3 = abs(closest[0][0] - closest[2][0])
        diff_2_3 = abs(closest[1][0] - closest[2][0])
        if diff_1_3 <= max_int_diff and diff_2_3 <= max_int_diff and diff_1_2 <= max_int_diff:
            intersections.append((i, j))
        # edge of graph valleys bound the graph, so they are counted as intersections
        elif diff_1_2 <= max_valley_diff \
                and (i <= max_edge_dist or i >= array_size - max_edge_dist
                        or j <= max_edge_dist or j >= array_size - max_edge_dist):
            intersections.append((i, j))
        # valleys
        elif diff_1_2 <= max_valley_diff:
            valleys.append((i, j))

更新2
我现在已经成功地使用

ndimage.minimum_filter

准确地找到了大部分谷点:) 我结合了各个轴处理来获得以下结果。但仍然缺少一些要点。任何有关我如何改进这一点的想法将不胜感激。我尝试过向上/向下更改尺寸，但这是我能得到的最佳结果。
我目前找到缺失点的想法是再添加两个过滤器来查看两个 45 度轴，因为山谷的角度似乎会影响它。

# using scipy.ndimage.minimum_filter
minima_0 = (arr != minimum_filter(arr, axes=0, size=10, mode='constant', cval=20.0))
minima_1 = (arr != minimum_filter(arr, axes=1, size=10, mode='constant', cval=20.0))
# return a masked arr, where minima have been replaced with a value
arr_0 = np.where(minima_0, arr, 50)
arr_1 = np.where(minima_1, arr, 50)
mg = arr_0 + arr_1

Answer 1

如果您将此视为图像处理问题，我会研究以下算法：

首先使用山脊检测器找到山谷： 请参阅https://scikit-image.org/docs/stable/auto_examples/edges/plot_ridge_filter.html#sphx-glr-auto-examples-edges-plot-ridge-filter-py

接下来使用简单的阈值来获取二进制掩码。然后使用 skeletalize-functions 来获取底层网络。

https://scikit-image.org/docs/stable/auto_examples/edges/plot_sculpture.html

连接点有点棘手： 您可以检查骨架中每个像素的相邻像素数。交叉点位于有超过 2 个邻居的地方：

在 python opencv 中查找骨架图像的交集

或者，您可以尝试使用命中和错过策略来找到交叉点：

https://answers.opencv.org/question/103162/detection-of-contours-intersections/

https://docs.scipy.org/doc/scipy-0.14.0/reference/ generated/scipy.ndimage.morphology.binary_hit_or_miss.html