最近工作需要用到最遠點采樣fps算法, 找了一些blog學習學習, 寫了個原型:

def distance(p1, p2):
    return np.sqrt(np.sum((p1 - p2)**2))

def FPS(sample, num, center_idx: int = 0):
    '''sample:采樣點云數(shù)據(jù),
    num:需要采樣的數(shù)據(jù)點個數(shù)'''
    n = sample.shape[0]
    select_p = [center_idx]  # 儲存采集點索引
    L = np.full(n, 1e20, dtype=np.float64)
    for i in range(num - 1):
        for p in range(n):
            d = distance(sample[select_p[-1]], sample[p])
            if d < L[p]:
                L[p] = d
        select_p.append(np.argmax(L).item())
    return select_p

測試一下, 跑的沒問題, 但是速度感人

所有點的歐氏距離計算做個向量化優(yōu)化:

def fps(points, n_samples, first_idx: int = 0):
    """
    points: (N, D) array of points
    n_samples: number of points to sample
    first_idx: index of first point to sample
    """
    N = points.shape[0]
    selected_indices = [first_idx]
    distances = np.full(N, np.inf)

    for _ in range(n_samples - 1):
        # 計算所有點到最新選擇點的距離
        last_selected = points[selected_indices[-1]]
        dist = np.sum((points - last_selected) ** 2, axis=1)

        # 更新最小距離
        distances = np.minimum(distances, dist)

        # 選擇距離最大的點
        new_idx = np.argmax(distances).item()
        selected_indices.append(new_idx)

        distances[new_idx] = 0

    return selected_indices

這一下子快了100多倍, 能用了
找了個開源基于rust實現(xiàn)核心的python接口包: https://github.com/leonardodalinky/fpsample

對比了一下結(jié)果, 是沒問題的, 但是他比我這個快個4,5倍
最后借助ai優(yōu)化一下:

def fps_optimized(points, n_samples, first_idx: int = 0):
    """
    Optimized FPS implementation
    points: (N, D) array of points
    n_samples: number of points to sample
    first_idx: index of first point to sample
    """
    N = points.shape[0]
    selected_indices = np.zeros(n_samples, dtype=np.int64)
    distances = np.full(N, np.inf)
    selected_indices[0] = first_idx

    # 預計算點的平方和，避免重復計算
    point_squares = np.sum(points ** 2, axis=1)

    for i in range(1, n_samples):
        last_selected = points[selected_indices[i - 1]]

        # 使用廣播來計算距離，避免創(chuàng)建臨時數(shù)組
        # ||a-b||^2 = ||a||^2 + ||b||^2 - 2<a,b>
        dist = point_squares + np.sum(last_selected ** 2) - 2 * np.dot(points, last_selected)

        # 更新最小距離
        np.minimum(distances, dist, out=distances)

        # 選擇距離最大的點
        new_idx = np.argmax(distances)
        selected_indices[i] = new_idx
        distances[new_idx] = 0

    return selected_indices.tolist()

又快了6,7倍, 中小規(guī)模點云用這個看起來就沒啥問題了
后面如果有超大規(guī)模的需求或許可以關(guān)注fpsample作者的另一個repo: https://github.com/leonardodalinky/pytorch_fpsample