点云中的局部最大值 [英] Local maxima in a point cloud

问题描述

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

I have a point cloud C, where each point has an associated value. Lets say the points are in 2-d space, so each point can be represented with the triplet (x, y, v).

我想找到局部最大值的点的子集.也就是说，对于某个半径R，我想找到C中的点S的子集，使得对于S中的任何点Pi(​​值为vi)，在Pi的R距离内C中的点Pj都不存在，其值vj为大于vi.

I'd like to find the subset of points which are local maxima. That is, for some radius R, I would like to find the subset of points S in C such that for any point Pi (with value vi) in S, there is no point Pj in C within R distance of Pi whose value vj is greater that vi.

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

I see how I could do this in O(N^2) time, but that seems wasteful. Is there an efficient way to do this?

注意事项:

• 此问题的根源是我试图在稀疏矩阵中找到局部最大值，因此在我的情况下，x，y是有序整数索引-如果这简化了问题，请告诉我！
• 如果解决方案仅适用于曼哈顿距离之类的事情，我会感到非常高兴.
• 我在python中，所以如果有某种很好的矢量化numpy方法来做到这一点，那就太好了.

推荐答案

按照伊夫的建议，以下是答案，该答案使用scipy的

Following up on Yves' suggestion, here's an answer, which uses scipy's 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]

这篇关于点云中的局部最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！