15  霍夫变换

章节 14 的搜索线方法有一个不言自明的前提：你大致知道目标在哪里。先框一个 ROI，再布设搜索线——整套流水线建立在”一个 ROI 对应一个基元”的先验之上。可一旦这个前提不成立呢？图里有多条直线、多个圆，事先不知道各在何处；目标还可能断裂（虚线、反光造成的缺口）或被部分遮挡。这时搜索线无从布设，逐点跟踪也会在第一个缺口处断线。霍夫变换（Hough transform）换了一种问法：不去追问”这条线在哪”，而是让每一个边缘点为所有可能经过它的直线投票（voting），得票最多的参数组合自然胜出。本章用一幅 480×360 的合成场景（图 15.1）把这套投票机制完整跑一遍：场景里有 3 条直线——其中一条是缺口率约 47% 的虚线——和 2 个圆——其中一个被遮挡了 40%——外加 40 个杂散斑点和 σ=8 的高斯噪声。断裂、遮挡、杂点、噪声四种干扰齐备，正好把霍夫变换的全部价值逼出来。

图 15.1: 合成测试场景（480×360）：3 条直线（L1、L3 为实线，L2 为缺口率约 47% 的虚线）、2 个圆（C1 完整，C2 缺失 40% 圆弧）、40 个杂散斑点，叠加 σ=8 的高斯噪声。

15.1 参数空间与投票

要为直线投票，先得给直线一组合适的参数。霍夫变换采用法线式（normal form）参数化 (Duda 和 Hart 1972)：

\[ \rho = x\cos\theta + y\sin\theta, \]

其中 \(\theta\in[0^\circ,180^\circ)\) 是直线法线方向与 \(x\) 轴的夹角，\(\rho\) 是原点到直线的带符号距离。一对 \((\rho,\theta)\) 唯一确定一条直线，且两个参数都有界：\(|\rho|\) 不超过图像对角线长度，\(\theta\) 只需半个圆周。

为什么不用更熟悉的斜截式 \(y=kx+b\)？竖直线的斜率 \(k\to\infty\)，参数空间（parameter space）在 \(k\) 方向无界，没法离散成有限的格子；而且 \(k\) 的均匀划分对应的直线方向极不均匀（\(k\) 从 0 到 1 扫过 45°，从 10 到 11 只扫过约 0.5°）。法线式两个参数都有界、对方向均匀，是为投票量身定制的参数化。

法线式带来一个漂亮的对偶：把图像空间的一个点 \((x_0,y_0)\) 代入上式，让 \(\theta\) 取遍 \([0^\circ,180^\circ)\)，得到的 \(\rho(\theta)=x_0\cos\theta+y_0\sin\theta\) 是参数空间里的一条正弦曲线——它枚举了所有经过该点的直线。反过来，若一组点共线于 \((\rho^*,\theta^*)\)，它们各自的正弦曲线必然全部经过参数空间的同一点 \((\rho^*,\theta^*)\)。检测直线于是变成了找正弦曲线族的公共交点。

工程实现就是累加器（accumulator）：把 \((\theta,\rho)\) 平面离散成网格（如 1°×1 px），初始化为零；对每个边缘点，沿 \(\theta\) 扫一遍，算出对应的 \(\rho\)，给落到的格子加一票；所有点投完后，累加器里的峰值（peak）就是图中的直线——票数即落在这条直线上的边缘点数。一个全局的几何检测问题，被化简成了一次数组峰值搜索。

边缘点从哪里来？任何边缘检测器都行（系统的论述见 章节 13）——本章对 图 15.1 做 Sobel 梯度幅值阈值化（阈值 200，约为 σ=8 噪声水平的 7σ，按 章节 7 的思路把门槛锚定在噪声之上，几乎无虚警），得到 6677 个边缘点（图 15.2）。注意虚线的缺口和圆的缺弧都原样保留在了边缘图里——接下来投票要直面它们。

图 15.2: Sobel 幅值阈值化（阈值 200 ≈ 7σ）得到的边缘图，共 6677 个边缘点。虚线缺口、圆弧缺失与杂散斑点都如实保留。

15.2 读累加器

我们先不调 SDK，手工构建一个 180×1201 的累加器（\(\theta\) 方向 1°/格、\(\rho\) 方向 1 px/格，\(|\rho|\le 600\)），让 6677 个点逐一投票。结果见 图 15.3：横轴是 \(\theta\)，纵轴是 \(\rho\)，灰度经开方拉伸。图上能看到两层结构：铺满下半幅的正弦曲线族——每条淡淡的亮曲线就是一个（簇）边缘点的投票轨迹；以及曲线族中三个明显更亮的交点——三条直线的峰。40 个杂散斑点的票散落在各自的正弦曲线上，没有公共交点，哪里也聚不成峰。

图 15.3: 手工累加器（180×1201，θ 横轴、ρ 纵轴，开方灰度拉伸）。每个边缘点贡献一条正弦投票轨迹；共线点的轨迹交于一点，形成三个亮峰，分别对应 L1、L2、L3。

峰值是否落在该落的位置？由三条线段的真值端点可以预测各自的 \((\rho,\theta)\)；从累加器提取三大峰值（取全局最大 + 邻域抑制，并用 5×5 加权重心做亚格精化），再与 SDK FindHoughLines 的检出结果对照：

表 15.1: 三条真值直线：预测峰位 vs 手工累加器实测峰 vs SDK 检出
直线 预测 \((\rho,\theta)\) 累加器峰 \((\rho,\theta,\text{票数})\) SDK 检出 \((\rho,\theta)\)
L1（实线） (119.79, 15.00°) (120.77, 15.30°, 291 票) (121.04, 15.01°)
L2（虚线，47% 缺口） (9.15, 104.25°) (9.11, 104.25°, 190 票) (9.22, 104.01°)
L3（实线） (378.55, 47.60°) (377.31, 48.05°, 260 票) (379.19, 48.02°)

三条线全部验证通过：\(\theta\) 偏差不超过半度，\(\rho\) 偏差不超过 1.3 px。这 1.3 px 不是误差的下限玄学，而有明确出处：场景中线条的笔画宽约 2.8 px，Sobel 在笔画两侧各检出一排边缘点，两排点各自共线、相距约 2.8 px，投票后的峰是两排票的妥协，落点便在两侧之间游移——累加器的峰永远忠实于边缘点的几何，而边缘点的几何由笔画宽度决定。

表中最值得盯住的是 L2：虚线缺了 47% 的笔画，票数从实线的约 290 掉到 190，但峰的位置纹丝不动、依然清晰可辨。这就是霍夫变换的灵魂——断裂免疫。投票只问”这个点在不在这条直线上”，从不问”它与邻点是否相连”：缺口只是按比例削减票数，不会移动峰、更不会让峰消失。与之相对，任何依赖局部连续性的方法（边缘跟踪、轮廓链接）走到第一个 14 px 的缺口就断了。全局证据积累与局部连续性跟踪，是两种世界观；当目标天生断裂时，只有前者还站着。

15.3 多实例与稳健性

如果不用投票，直接把”找直线”交给最熟悉的最小二乘会怎样？做一个反面实验：对全部 6677 个边缘点整体拟合一条总体最小二乘直线，得到 \(\rho=180.04\)、\(\theta=93.76°\)，全点 RMS 距离 82.6 px——图 15.4 中那条横贯图像的白线，与 L1、L2、L3 哪一条都不沾边。这不是实现失误，而是提问方式错了：最小二乘假设所有点服从同一个模型，而这里的点分属三条线、两个圆和 40 个杂点；“全体点的最优单线”是一个不存在的对象的折中，它只能落在所有结构的质心附近、方向取散布最大的主轴——一条谁也不是的”平均线”。

图 15.4: 反面实验：对全部 6677 个边缘点做单直线总体最小二乘拟合，结果 ρ=180.04、θ=93.76°、全点 RMS=82.6 px（白线）——多实例数据上”全体最优”是无意义的折中。

霍夫变换天然没有这个困境：每个实例在累加器里聚自己的峰，互不干扰——L1 的 291 票、L2 的 190 票、L3 的 260 票各居其位；不属于任何直线的圆弧点与杂点，票散布在各处，成不了峰。多实例分离与对杂点的稳健性是同一个机制的两面：聚票的赢，散票的输。图 15.5 是 SDK FindHoughLines 的检出结果：三条直线全部命中（白线），包括那条虚线。

图 15.5: SDK FindHoughLines 检出的 3 条直线（白线，无限长直线裁剪到图像边界）。虚线 L2 在 47% 缺口下照常检出；圆与杂点未产生虚警。

霍夫与 章节 14 的稳健拟合（Huber、RANSAC）如何分工？稳健拟合处理的是”一个实例 + 少数离群点”，前提仍是 ROI 已把目标大致圈住，回报是亚像素精度；RANSAC 虽可”找到一个、剔除内点、再找下一个”地处理多实例，但实例一多便低效。霍夫处理的是”不知道几个实例 + 大量无关结构”，不需要任何位置先验，代价是精度受累加器量化限制。经验法则：有 ROI、要精度——搜索线 + 稳健拟合；无先验、要找全——霍夫。

15.4 霍夫圆

圆有三个参数 \((c_x,c_y,r)\)，累加器随之从二维升到三维：一个边缘点的投票轨迹不再是正弦曲线，而是参数空间里的一个圆锥面（圆心离该点越远，所需半径越大）。直接实现的内存与计票开销都比直线高一个量级，所以实用算法几乎都借助梯度方向加速：边缘点的梯度方向指向（或背向）圆心，于是只需沿梯度射线给可能的圆心投票——三维问题退化为”二维圆心累加 + 一维半径直方图”两步，这正是主流实现（包括 OpenCV 与多数工业库）采用的 2-1 霍夫策略。

量级感受：480×360 的图、半径搜索范围 40 px，朴素三维累加器有 480×360×40 ≈ 690 万个格子，每个边缘点要在每个半径层画一整圈投票；梯度方向加速后，每点只沿一条射线投出几十票。没有这一步，霍夫圆在产线节拍内跑不动。

实验沿用同一场景（图 15.6）：FindHoughCircles 恰好检出两个圆。完整圆 C1 真值 \((150,230,50)\)，检出 \((151.0,231.0,50.2)\)——圆心误差 1.41 px、半径误差 0.20 px；缺失 40% 圆弧的 C2 真值 \((380,270,60)\)，检出 \((377.0,267.0,57.8)\)——圆心误差 4.24 px、半径误差 2.20 px。两组数字合起来是一句话：遮挡之下精度退化，但检测不失败。退化的原因与直线的 ρ 偏移同源而更甚：圆的三个参数相互耦合，缺弧让票的重心偏向尚存的弧段，峰被轻微拉偏；但 60% 的弧仍贡献了足够聚成峰的票——这正是断裂免疫在圆上的重演。

图 15.6: SDK FindHoughCircles 的检出结果（白圈与十字为检出的圆与圆心）。完整圆 C1 误差 1.41/0.20 px；缺失 40% 圆弧的 C2 误差 4.24/2.20 px——遮挡下精度退化但不失败。

还要看清精度的本质上限：实测该 SDK 的圆心被量化到 2 px 网格、半径以约 0.2 px 步进——这是累加器格子尺寸的直接体现，再多的票也投不出格子以下的分辨率。所以工业上的标准套路是两段式：霍夫粗定位，搜索线精测——先用霍夫在全图把每个圆找出来（无先验、抗遮挡），再以检出的圆心半径为先验构造环形 ROI，交给 章节 14 的径向搜索线 + 稳健拟合做亚像素精测。霍夫负责”在哪里”，搜索线负责”准到多少”——两章方法不是竞争关系，而是流水线的上下游。

15.5 SciVision 实现

霍夫直线由 SCIMV::SciSvHoughLines 提供，内部含 Canny 边缘提取，直接吃灰度图：

SCIMV::SciSvHoughLines houghL;
SciPointArray term;
SciVarArray lineAng, lineLen;
long rc = houghL.FindHoughLines(src, fullROI, /*cannyLow*/ 60, /*cannyHigh*/ 120,
    /*accumThreshold*/ 65, /*minAngle*/ -90, /*maxAngle*/ 90,
    /*AngleGap*/ 5, /*DistGap*/ 10, /*maxNum*/ 6, /*AngleCheck 范围内*/ false,
    &term, &lineAng, &lineLen);

cannyLow/cannyHigh 是内部 Canny 的双阈值；accumThreshold=65 是票数门槛——低于 65 票的峰不报告；minAngle/maxAngle 限定接受的直线角度范围；AngleGap=5、DistGap=10 是峰值去重的邻域（角度差 <5° 且距离差 <10 px 的峰合并为一条）；maxNum=6 限制最多返回的直线数。本例允许返回 6 条而恰好只检出 3 条真值线，说明参数下无虚警。

实测中这个 API 有三处与直觉（或文档）相悖、必须如实记录的行为。其一，头文件未注明 AngleCheck 的取值含义：实测 false 才是”找角度范围内的直线”，true 是找范围外的——传 true 配全范围 [-90,90]，会直接得到”找不到合适直线”的错误码 122408001。其二，默认 Canny 阈值 20/40 在本场景失效：σ=8 的噪声下虚警边缘点过多，真实直线的票数被噪声票淹没，累加器里冒出贯穿全图的幻影对角线；阈值提高到 60/120 起结果才稳定——Canny 门槛必须锚定在噪声水平之上，这与 小节 15.1 中手工边缘图取 7σ 阈值是同一个道理。其三，返回值的语义：term 里的”端点”并非线段端点，而是无限长直线与图像边界的交点（图 15.5 中白线全部贯穿图像即是此故），lineLenth 是裁剪后的长度；lineAng 返回的角度是 \(90^\circ-\theta\)（直线方向角而非法线角），换算时别弄反。

霍夫圆由 SCIMV::SciSvHoughCircles 提供：

SCIMV::SciSvHoughCircles houghC;
SciPointArray centers;
SciVarArray radii;
rc = houghC.FindHoughCircles(src, fullROI, /*minDist*/ 100, /*edgeThreshold*/ 160,
    /*accumThreshold*/ 65, /*minRadius*/ 35, /*maxRadius*/ 75, /*maxNum*/ 4,
    &centers, &radii);

minDist=100 是两圆圆心的最小间距（去重）；edgeThreshold 是内部边缘提取的强度门槛；accumThreshold=65 是圆心累加器的票数门槛；minRadius/maxRadius 划定半径搜索带 35～75 px。这里同样有一个坑：默认 edgeThreshold=80 偏低，噪声边缘会聚出半径紧贴 maxRadius 的幻影圆（大半径圆周长，路过的噪声点多，天然占票数便宜）；提高到 160 并配合 accumThreshold=65 后，即便放开 maxNum=4 也只检出两个真值圆。最后再次提醒输出的量化粒度：圆心落在 2 px 网格上、半径约 0.2 px 步进——拿到结果就该知道它是”粗定位”，精测交给下游。生成本章全部图像与数字的完整工程位于 code/hough_transform/。

工业案例：料盘上的引脚计数

某 IC 料盘检测工位要清点每格芯片的引脚数：金属引脚在环形光下反光，成像为一组断断续续的短亮线——每根引脚断成两三截，数量随芯片型号变化。模板匹配不适用（引脚数不定、外观随反光变化），搜索线也无从布 ROI。霍夫直线恰好对路：引脚方向已知（与芯片体垂直），把 minAngle/maxAngle 收窄到该方向 ±10° 的角度带，无关方向的反光直接出局；断裂的几截亮线在累加器里为同一个峰凑票——断裂免疫让”几截”自动归并为”一根”；最后用票数门槛滤掉零星反光，检出的峰数就是引脚数。调参的重心与本章实验完全一致：先量产线图像的噪声水平，把内部 Canny 阈值锚定在噪声之上，幻影线一旦出现，计数就不可信。

15.6 小结

  • 霍夫变换把几何检测变成投票：法线式 \(\rho=x\cos\theta+y\sin\theta\) 下，图像点对偶于参数空间的正弦曲线，共线点的曲线交于一点；离散累加器计票，峰即直线。
  • 断裂免疫是霍夫的灵魂：投票只看”在不在线上”、不看”连不连续”，缺口只削票数不移峰——47% 缺口的虚线以 190 票照常成峰，40% 遮挡的圆照常检出。
  • 多实例分离与杂点稳健是同一机制：每个实例聚自己的峰，散票聚不成峰；反面实验里对 6677 点做单线最小二乘，得到 RMS 82.6 px 的”平均线”——多实例数据上全体最优是无意义的折中。
  • 霍夫的精度受累加器量化封顶（本例圆心 2 px 网格、半径 0.2 px 步进；直线 ρ 偏差还受笔画两侧投票影响），工程套路是”霍夫粗定位 + 搜索线精测”，与 章节 14 构成上下游。
  • 参数要锚定噪声、语义要实测验证：内部 Canny 阈值低于噪声水平会产生幻影线/幻影圆；本章 SDK 的 AngleCheck 语义与文档相反、返回端点是边界裁剪点、角度是 \(90^\circ-\theta\)——关键语义一律用已知真值的合成图验证后再上线。

霍夫变换的原始文献是 Duda 与 Hart 的经典论文 (Duda 和 Hart 1972)；把它从直线推广到任意形状的，是 Ballard 的广义霍夫变换 (Ballard 1981)，而 Illingworth 与 Kittler 的综述系统梳理了各类变体与计算策略 (Illingworth 和 Kittler 1988)。关于其与几何测量流水线的衔接，可进一步阅读 Steger 等人的著作 (Steger, Ulrich, 和 Wiedemann 2018)。