三维点云处理（十七）：霍夫变换 (Hough Transform) 拟合
上一章介绍的最小二乘法（LSQ）在面对少量离群点时就会被严重扯偏。面对高噪声、多模型共存的三维点云场景，霍夫变换（Hough Transform） 引入了“对偶空间变换”与“参数空间投票（Voting）”机制，实现了对离群噪点极其鲁棒的几何基元提取。
本文系统梳理霍夫变换的对偶映射原理、极坐标参数化、圆与三维扩展，以及其在工程中的分辨率权衡与维度灾难。
一、 核心原理：对偶变换与累加器投票
霍夫变换的核心哲学是**“把几何检测问题转化为参数空间中的峰值寻找问题”**。
1.1 参数空间对偶性 (Duality)
- 点与线的对偶：
- 在二维欧氏空间 中，一条直线由参数 决定：；
- 如果固定点 ，将其看作常数，而将 看作变量，则方程变为：；
- 结论：图像/空间坐标系中的一个点 对应参数空间 中的一条直线。
1.2 投票机制 (Voting Mechanism)
- 共线判断：若欧氏空间中有多个点共线于 ，则在参数空间中，这些点对应的多条直线必交于同一个点 ；
- 网格离散与累加器：将参数空间离散化为网格（Bins / Accumulator Array）。每个数据点在其参数空间对应直线上经过的所有 Bins 里投上 1 票；
- 峰值检索：得票最多的 Bin（极峰 / Peak）所对应的参数 即为检测出的直线模型。
1.3 为什么霍夫变换对抗离群点极度鲁棒？
在上一章的最小二乘法 (LSQ) 中，算法致力于全局最小化所有点的残差平方和。这意味着哪怕只有一个极端的离群噪点，它产生的巨大残差也会如同“黑洞”一般将拟合直线强行扯偏。
而霍夫变换彻底抛弃了“最小化全局误差”的思路，采用了独立的民主投票制：
- 内点 (Inliers)：成百上千个共线的内点，它们在参数空间产生的曲线必然会在真实参数坐标 处发生相交干涉，迅速累加出一座高耸入云的“投票极峰”。
- 离群点 (Outliers)：一个随机的散粒噪点也会在参数空间产生一条曲线，并给沿途的网格投下 1 票。但由于噪点是随机分布的，它们产生的曲线在参数空间中只会杂乱无章地随机穿插。
- 结论：离群点仅仅只会轻微抬高参数空间全局的“背景底噪”，而绝对无法撼动和拉偏真实内点所聚拢成的那座极峰。只要内点数量足够形成绝对多数，霍夫变换就能在 50% 甚至更高比例的噪点中准确提取出目标模型。
二、 直线的极坐标参数化
2.1 斜截式 的缺陷
- 斜率无穷大：当直线垂直于 轴时，斜率 ，无法在有限网格内离散化；
- 非均匀分布：斜率 的分布非均匀，导致参数空间网格分配不公。
2.2 极坐标模型 ()
为了克服斜截式的缺陷，采用直线的法线极坐标表示：
其中：
- 是法线与 轴的夹角；
- 是原点到直线的垂直距离。
text
极坐标参数化几何示意
y ▲ / 直线 x cosθ + y sinθ = r
│ /
│ r /
│ ┌──────/
│ │ /│
│ │ / │
│ │ / │
│└─/────┼──────► x
│ / θ │
│/ │- 对偶曲线：在极坐标参数空间 中，欧氏空间的一个点 对应一条正弦波曲线：
- 相交极峰：共线的多个点对应的多条正弦曲线在 参数平面相交于一点，形成高密度投票峰值。
三、 霍夫变换算法完整步骤与工程细节
工程细节与优化：
- 分辨率权衡 (Resolution Tradeoff)：
- 网格粒度过粗：多个接近的模型混在同一个 Bin 中，精度下降；
- 网格粒度过细：投票被分散到多个相邻 Bin，且容易因噪声导致“模糊峰值 (Blurred Peak)”；
- 高斯平滑 (Gaussian Smoothing)：在寻找最大票数之前，对累加器数组进行平滑处理，能有效减轻噪点造成的模糊峰值干扰。
四、 霍夫变换的几何扩展：圆与 3D 基元
4.1 圆拟合 (Circle Fitting)
二维圆方程包含 3 个未知参数 ：
- 参数空间：变为三维网格空间 ；
- 几何映射：
- 若固定半径 ，每个点 在 平面上确定一个圆 ；
- 在全三维参数空间 中，欧氏空间中的一个点 对应一个三维圆锥面 (Cone)；
- 多个点对应的圆锥面在三维空间中交于圆心与半径对应的顶峰。
4.2 三维点云扩展 (3D Plane / Cylinder)
- 3D 平面拟合：法向量极坐标参数化 （3 维参数空间）；
- 3D 圆柱面/圆锥面：未知参数增加至 5 个（轴线方向 2、轴线上一点 2、半径 1）。
五、 总结与算法优缺点
| 维度 | 特性总结 |
|---|---|
| 算法优点 | 1. 对离群噪点（Outliers）极度鲁棒； 2. 对形状缺失、遮挡与断裂数据具有天然容错力； 3. 能在同一数据集里同时检测多个同类几何模型（多峰值检索）。 |
| 算法缺点 | 维度灾难（Dimension Curse）：参数空间维度增加时，累加器数组大小与计算复杂度呈指数级爆炸。通常仅适用于未知参数少于 3 个的模型（如 2D/3D 直线、平面、圆）。 |