c - 在 C 中如何将 X、Y 点转换为 Rho、Theta 以进行霍夫变换？

Question

所以我正在尝试在 C 上编写霍夫变换代码。我有一个二值图像并从图像中提取了二值值。现在要进行霍夫变换，我必须将图像中的 [X,Y] 值转换为 [rho,theta] 以进行形式的参数化变换

rho=xcos(θ)+ysin(θ)

不太明白它到底是怎么改造的，看网上其他代码。任何解释算法的帮助以及如何根据 [X,Y] 完成 [rho,theta] 值的累加器将不胜感激。提前致谢。 :)

Answer 1

您的问题暗示您认为您需要将图像中的每个 (X,Y) 兴趣点映射到 Hough 中的 ONE (rho, theta) vector 空间。

事实上，图像中的每个点都映射到一个曲线，即霍夫空间中的SEVERAL 个 vector 。每个输入点的 vector 数量取决于您决定的某些“任意”分辨率。例如，对于 1 度分辨率，您将在霍夫空间中获得 360 个 vector 。

对于 (rho, theta) vector 有两种可能的约定:要么使用 [0, 359] 度范围作为 theta，在这种情况下 rho 始终为正，或者使用 [0,179] 度作为 theta 和允许 rho 为正或负。后者通常用于许多实现。

一旦你理解了这一点，累加器只不过是一个二维数组，它覆盖了 (rho, theta) 空间的范围，并且每个单元格都用 0 初始化。它是用于计算输入中不同点的各种曲线共有的 vector 数。

因此，该算法为输入图像中的每个兴趣点计算所有 360 个 vector (假设 θ 的分辨率为 1 度)。对于这些 vector 中的每一个，在将 rho 舍入到最接近的整数值之后(取决于 rho 维度的精度，例如，如果我们每个单位有 2 个点，则为 0.5)它在累加器中找到相应的单元格，并增加该单元格中的值.
当对所有兴趣点都完成此操作后，该算法将搜索累加器中具有高于选定阈值的值的所有单元格。这些单元格的 (rho, theta)“地址”是 Hough 算法已识别的线(在输入图像中)的极坐标值。

现在，请注意，这为您提供了线 方程，通常剩下的就是找出有效属于输入图像的这些线的段。

上面的一个非常粗略的伪代码“实现”

Accumulator_rho_size = Sqrt(2) * max(width_of_image, height_of_image)
                          * precision_factor  // e.g. 2 if we want 0.5 precision
Accumulator_theta_size = 180  // going with rho positive or negative convention
Accumulator = newly allocated array of integers
    with dimension  [Accumulator_rho_size, Accumulator_theta_size]
Fill all cells of Accumulator with 0 value.

For each (x,y) point of interest in the input image
   For theta = 0 to 179
       rho = round(x * cos(theta) + y * sin(theta),
                   value_based_on_precision_factor)
       Accumulator[rho, theta]++

Search in Accumulator the cells with the biggest counter value
(or with a value above a given threshold) // picking threshold can be tricky

The corresponding (rho, theta) "address" of these cells with a high values are
the polar coordinates of the lines discovered in the the original image, defined
by their angle relative to the x axis, and their distance to the origin.

Simple math can be used to compute various points on this line, in particular
the axis intercepts to produce a  y = ax + b equation if so desired.

总的来说，这是一个相当简单的算法。复杂性主要在于与单位保持一致，例如用于度数和弧度之间的转换(大多数数学库的三角函数都是基于弧度的)，以及用于输入图像的坐标系。