用于直线形式点模式识别的霍夫变换算法

Question

大家好，我目前正在研究不同的算法，这些算法可以为我提供对齐单元格组内的直线图案。

我来解释一下：

假设我们有一个 XY 平面，其值为 200(x)/30(y)。

我得到了一堆标记细胞中心（以 xy 坐标表示）的点，我的任务是获得通过这些细胞形成直线的点模式。

放置在 xy 平面上的点

图案必须是一组 8 个点：[[point1],[point2],[point3],...[point8]] 或一组 4 个点（如果没有可配对的组）。

穿过点的可能直线的图案

直线只能有 -50° 到 50° 的梯度。

例如：

命中的Y坐标：

[0.65, 0.65, 0.65, 0.65, 0.65, 1.9500000000000002, 1.9500000000000002, 1.9500000000000002, 1.9500000000000002, 3.25, 3.25, 3.25, 3.25, 3.25, 4.550000000000001, 4.550000000000001, 4.550000000000001, 4.550000000000001]

命中的X坐标：

[77.7, 107.1, 191.1, 195.3, 123.9, 79.80000000000001, 109.2, 193.2, 126.00000000000001, 77.7, 111.3, 195.3, 123.9, 128.1, 79.80000000000001, 109.2, 197.4, 126.00000000000001]

积分将是

[77.7,0.65],[107.1,0.65]

...等等

所以我的第一个想法是实现某种霍夫变换，它会给我一个累加器，其中包含有更多“投票”的点的 rho 和 theta 值。

这是代码：

puntos_y=[0.65, 0.65, 0.65, 0.65, 0.65, 1.9500000000000002, 1.9500000000000002, 1.9500000000000002, 1.9500000000000002, 3.25, 3.25, 3.25, 3.25, 3.25, 4.550000000000001, 4.550000000000001, 4.550000000000001, 4.550000000000001]
puntos_x=[77.7, 107.1, 191.1, 195.3, 123.9, 79.80000000000001, 109.2, 193.2, 126.00000000000001, 77.7, 111.3, 195.3, 123.9, 128.1, 79.80000000000001, 109.2, 197.4, 126.00000000000001]

#ANGLE VALUES (50º MAX )
thetas = np.deg2rad(np.arange(-50,50))
#PLANE WIDTH,HEIGHT XY
width, height = 200,30
#DIAG FOR ACCUMULATOR
diag_len = float(np.ceil(np.sqrt(width * width + height * height)))  # max_dist
#LINSPACE DE RHOS
rhos = np.linspace(-diag_len, diag_len, int(2*diag_len))

# STORE SOME VALUES
cos_t = np.cos(thetas)
sin_t = np.sin(thetas)
num_thetas = len(thetas)
num_rhos = len(rhos)

#  ACcumulador (ARRAY THETA VS RHO)
accumulator = np.zeros((int(2*diag_len), num_thetas))

#POINTS
y_idxs, x_idxs = puntos_y, puntos_x

# ACCUMULATOR VOTES
for i in range(len(x_idxs)):
    x = x_idxs[i]
    y = y_idxs[i]

    for t_idx in range(num_thetas):
        # START CALCULATING RHO VALUES. DIAG_LEN FOR POSITIVE INDEX
        rho = round(x * cos_t[t_idx] + y * sin_t[t_idx] + diag_len )
        accumulator[int(rho), int(t_idx)] += 1





def votos_max(accumulator, thetas, rhos):
    #FINDS MAX VOTES IN ACCUMULATOR
    idx = np.argmax(accumulator)
    rho = rhos[int(idx / accumulator.shape[1])]
    theta = thetas[idx % accumulator.shape[1]]

    return idx, theta, rho

#FINDS GRADIENT FOR A THETA
def sacar_pendiente(theta):
    return np.cos(theta) / np.sin(theta)

#FINDS Y WHEN X=0
def sacar_n(theta, rho):
    return rho / np.sin(theta)

这段代码为我提供了一个累加器数组，其中包含列表中每个点的 senoid。这些点相交的地方是每组点的直线梯度相同的地方。

霍夫积分累加器

问题是：如您所见，点并不能形成精确的直线。它们排列在 xy 平面上几乎对齐但不完全对齐，这就是为什么您可以在累加器中看到各种高度投票的点，而不是每 2 组点中只有一个。

所以当我看到这样的图形时，我可以想象出这种模式：

已识别模式

我很想找到某种方法来改进这个累加器，也许是某种改变阈值的方法，这样在累加器中，每组点都被视为一个大点（我不知道我是否解释得很好）就像你还是个孩子，把点弄大了，这样线就可以适合了。

考虑每组 4 个点，就像它们完全对齐一样，降低直线到程序点的精度，这当然会导致在程序中只有一个“投票最多”（RHO，THETA）点累加器数组，然后我就可以提取它的坐标并轻松创建模式。

有什么办法可以改善这个问题吗？ 也许我应该尝试其他类型的算法作为点和直线的模式识别器？

PD：抱歉，如果我没有正确解释自己。

Answer 1

霍夫空间中的峰值检测

在使用霍夫变换时，您面临着一个众所周知的问题（例如，参见1991年的文章Kiryati等人的“概率霍夫变换”），即离散化和噪声使峰值分布在累加器。这就是为什么您必须搜索的不是最好的细胞，而是最好的细胞组。

在实践中，线路检测分两步完成：

1. 构建累加器
2. 使用峰值检测功能

例如，

scikit-image

包具有用于第一个的

hough_line

函数和用于第二个的

hough_line_peaks

函数。这里有一个指向文档的链接，可以查看它是如何工作的，还有一个指向第二个函数的代码。具体来说，

hough_line_peaks

“识别相隔一定距离的最显着特征。在图像的第一维和第二维中分别应用不同尺寸的非极大值抑制来识别峰值。”.

注意您的代码

霍夫变换通常以图像作为输入。您可以使用 bin 将 2D 点云转换为图像。看来 0.1 的 bin/pixel 大小适合您的情况：

import numpy as np

pointcloud_size = np.array([200, 300])
pixel_size = 0.1
img_size = (pointcloud_size/pixel_size).astype(int)
img = np.zeros(img_size)

x = [77.7, 107.1, 191.1, 195.3, 123.9, 79.8, 109.2, 193.2, 126.0, 77.7, 111.3,
     195.3, 123.9, 128.1, 79.8, 109.2, 197.4, 126.0]
y = [0.65, 0.65, 0.65, 0.65, 0.65, 1.95, 1.95, 1.95, 1.95, 3.25, 3.25, 3.25, 
     3.25, 3.25, 4.55, 4.55, 4.55, 4.55]
points = np.array([x, y]).T

active_pixels = (points//pixel_size).astype(int)
img[active_pixels] = 1.

霍夫变换的替代方案

RANSAC 是 2D 线检测的一个很好的替代方案。 RANSAC 维基百科页面中提供了伪代码，甚至是 Python 实现的示例。