点云中的局部最大值

Question

我有一个点云 C，其中每个点都有一个关联的值。假设这些点在二维空间中，所以每个点都可以用三元组 (x, y, v) 表示。

我想找到局部最大值点的子集。也就是说，对于某个半径 R，我想找到 C 中点 S 的子集，使得对于 S 中的任何点 Pi（具有值 vi），在距离 Pi 的 R 距离内，C 中没有点 Pj 的值 vj 为大于 vi。

我知道如何在 O(N^2) 时间内做到这一点，但这似乎很浪费。有没有一种有效的方法来做到这一点？

---

旁注：

• 这个问题的根源是我试图在一个稀疏矩阵中找到局部最大值，所以在我的例子中 x, y 是有序整数 indeces - 如果这简化了问题，请告诉我！
• 如果解决方案仅适用于曼哈顿距离或其他任何问题，我非常高兴。
• 我在 python 中，所以如果有某种很好的矢量化 numpy 方法来做到这一点，那就太好了。

Answer 1

跟进 Yves 的建议，这是一个使用 scipy 的KDTree的答案：

from scipy.spatial.kdtree import KDTree
import numpy as np

def locally_extreme_points(coords, data, neighbourhood, lookfor = 'max', p_norm = 2.):
    '''
    Find local maxima of points in a pointcloud.  Ties result in both points passing through the filter.

    Not to be used for high-dimensional data.  It will be slow.

    coords: A shape (n_points, n_dims) array of point locations
    data: A shape (n_points, ) vector of point values
    neighbourhood: The (scalar) size of the neighbourhood in which to search.
    lookfor: Either 'max', or 'min', depending on whether you want local maxima or minima
    p_norm: The p-norm to use for measuring distance (e.g. 1=Manhattan, 2=Euclidian)

    returns
        filtered_coords: The coordinates of locally extreme points
        filtered_data: The values of these points
    '''
    assert coords.shape[0] == data.shape[0], 'You must have one coordinate per data point'
    extreme_fcn = {'min': np.min, 'max': np.max}[lookfor]
    kdtree = KDTree(coords)
    neighbours = kdtree.query_ball_tree(kdtree, r=neighbourhood, p = p_norm)
    i_am_extreme = [data[i]==extreme_fcn(data[n]) for i, n in enumerate(neighbours)]
    extrema, = np.nonzero(i_am_extreme)  # This line just saves time on indexing
    return coords[extrema], data[extrema]