我可以使用什么算法来识别此散点图中的线？

这是一个有趣的问题,但它一直很安静.也许这个答案会引发更多的活动.

为了识别具有任意斜率的线和在点集合内的截距,霍夫变换将是一个好的起点.但是,对于音频应用,看起来斜率应始终为1,因此您不需要Hough变换的完整通用性.

相反,您可以将问题视为聚类差异之一x - y,其中x和y是保持点的x和y坐标的向量.

一种方法是计算直方图x - y.接近于具有斜率1的同一行中的点将在直方图中的相同仓中具有差异.具有最大计数的仓对应于近似对齐的最大点集合.在这种方法中要处理的一个问题是选择直方图箱的边界.一个糟糕的选择可能导致应该组合在一起的点被拆分成相邻的箱.

一种简单的蛮力方法是想象一个具有给定宽度的对角窗口,在(x,y)平面上从左向右滑动.线条的最佳候选对应于包含最多点的窗口的位置.这类似于直方图x - y,但不是有一组不相交的箱子,而是有重叠的箱子,每个点一个.所有箱子都具有相同的宽度,每个点确定箱子的左边缘.

count_diag_groups下面的代码中的函数执行该计算.对于每个点,它计算当窗口的左边缘在该点上时对角线窗口中有多少个点.一条线的最佳候选者是得分最多的窗口.这是脚本生成的图.顶部是数据的散点图.瓶底是相同的散点图,突出显示最佳候选点.

这种方法的一个很好的特点是只有一个参数,窗口宽度.一个不太好的功能是它具有时间复杂度O(n**2),其中n是点数.肯定有时间复杂度更高的算法可以做类似的事情; 您链接的文章讨论了这一点.然而,要判断替代品的质量,将需要更具体的规范,以确定线路识别必须"良好"或稳健.

import numpy as np
import matplotlib.pyplot as plt


def count_diag_groups(x, y, width):
    """
    Returns a list of arrays.  The length of the list is the same
    as the length of x.  The k-th array holds the indices into x
    (and y) of a set of points that are in a "diagonal" window with
    the given width whose left edge includes the point (x[k], y[k]).
    """
    d = x - y
    result = []
    for i in range(d.size):
        delta = d - d[i]
        neighbors = np.where((delta >= 0) & (delta <= width))[0]
        result.append(neighbors)
    return result


def generate_demo_data():
    # Generate some data.
    np.random.seed(123)
    xmin = 0
    xmax = 100
    ymin = 0
    ymax = 25
    nrnd = 175
    xrnd = xmin + (xmax - xmin)*np.random.rand(nrnd)
    yrnd = ymin + (ymax - ymin)*np.random.rand(nrnd)
    n = 25
    xx = xmin + 0.1*(xmax - xmin) + ymax*np.random.rand(n)
    yy = (xx - xx.min()) + 0.2*np.random.randn(n)
    x = np.concatenate((xrnd, xx))
    y = np.concatenate((yrnd, yy))
    return x, y


def plot_result(x, y, width, selection):
    xmin = x.min()
    xmax = x.max()
    ymin = y.min()
    ymax = y.max()

    xsel = x[selection]
    ysel = y[selection]
    # Plot...
    plt.figure(1)
    plt.clf()
    ax = plt.subplot(2,1,1)
    plt.plot(x, y, 'o', mfc='b', mec='b', alpha=0.5)
    plt.xlim(xmin - 1, xmax + 1)
    plt.ylim(ymin - 1, ymax + 1)

    plt.subplot(2,1,2, sharex=ax, sharey=ax)
    plt.plot(x, y, 'o', mfc='b', mec='b', alpha=0.5)
    plt.plot(xsel, ysel, 'o', mfc='w', mec='w')
    plt.plot(xsel, ysel, 'o', mfc='r', mec='r', alpha=0.65)
    xi = np.array([xmin, xmax])
    d = x - y
    yi1 = xi - d[imax]
    yi2 = yi1 - width
    plt.plot(xi, yi1, 'r-', alpha=0.25)
    plt.plot(xi, yi2, 'r-', alpha=0.25)
    plt.xlim(xmin - 1, xmax + 1)
    plt.ylim(ymin - 1, ymax + 1)

    plt.show()

if __name__ == "__main__":
    x, y = generate_demo_data()

    # Find a selection of points that are close to being aligned
    # with a slope of 1.
    width = 0.75
    r = count_diag_groups(x, y, width)

    # Find the largest group.
    sz = np.array(list(len(f) for f in r))
    imax = sz.argmax()
    # k holds the indices of the selected points.
    selection = r[imax]

    plot_result(x, y, width, selection)