随机化Hough变换

Hough变换是用于物体检测的技术，是计算机视觉或图像数据挖掘的许多实现中的关键步骤。

具体来说，随机Hough变换是经典Hough变换的一个概率变体，通常用于检测曲线（直线、圆、椭圆等）。

Hough变换（HT）的基本思想是对图像中所有潜在的曲线实施投票程序，在算法终止时，图像中确实存在的曲线会有相对较高的投票分数。

随机Hough变换（RHT）与HT不同，它试图通过利用分析性曲线的几何特性，避免对图像中的每个非零像素进行计算昂贵的投票过程，从而提高时间效率，减少原始算法的存储需求。

尽管Hough变换（HT）已被广泛用于曲线检测，但它有两个主要缺点。

首先，对于图像中的每个非零像素，现有曲线的参数和多余的参数都要在投票过程中积累。

第二，累积器阵列（或Hough空间）是以启发式的方式预定的。需要的精度越高，参数分辨率就应该定义得越高。

这两个需求通常会导致实际应用的大量存储需求和低速度。因此，RHT是为了解决这个问题而提出的。

与HT相比，RHT利用了一些分析曲线可以由曲线上一定数量的点完全确定的事实。例如，一条直线可以由两个点决定，而一个椭圆（或一个圆）可以由三个点决定。椭圆检测的案例可以用来说明RHT的基本思想。

整个过程一般包括三个步骤。用随机选择的点来拟合椭圆；更新累加器阵列和相应的分数；输出分数高于某个预定阈值的椭圆。

椭圆拟合一个定义椭圆的一般方程式是。xxx步是找到这三个点的切线。它们可以通过使用最小二乘法技术对相邻像素的一个小窗口拟合出一条直线来找到。

下一步是找到切线的交点。这可以通过解决上一步找到的直线方程来轻松完成。

同样，相交点的坐标可以通过解直线方程来确定，为了简洁起见，这里跳过了详细的过程。

有了前一阶段确定的椭圆参数，累积器阵列就可以相应地更新。与经典的Hough变换不同的是，RHT不保留桶的网格作为累积器阵列。

相反，它首先计算新检测到的椭圆和已经存储在累积器阵列中的椭圆之间的相似性。可以用不同的指标来计算相似度。

只要相似度超过某个预定的阈值，就用两个椭圆的平均值替换累加器中的那个椭圆，并在其分数上加1。否则，将这个椭圆初始化为累加器中的一个空位置，并赋予1的分数。

一旦一个候选椭圆的分值超过了第三个候选椭圆的分值，就会终止。