霍夫变换（Hough Transform）是一种经典的图像处理与计算机视觉算法，广泛用于检测图像中的几何形状，例如直线、圆、椭圆等。其核心思想是将图像空间中的“点”映射到参数空间中的“曲线”，从而将形状检测问题转化为参数空间中的峰值检测问题。

---

一、霍夫变换基本思想

• 输入：边缘图像（如经过 Canny 边缘检测）

• 输出：一组满足几何模型的形状（如直线、圆）

• 关键思想：

  • 图像空间中的一个点 → 参数空间中的一个曲线
  • 参数空间中多个曲线的交点 → 图像中多个点共属于同一形状（如一条直线）

---

二、直线霍夫变换（Hough Line Transform）

1. 图像空间中的直线表达式（斜截式）：

$y=kx+b$

但当直线垂直时（$k\to \infty$），斜截式不适用，因此使用极坐标式更稳定。

---

2. 极坐标形式表达直线

任意一条直线可以表示为：

$$\rho =x\cos \theta +y\sin \theta$$

• $\rho$：点到原点的距离（直线法线长度）
• $\theta$：法线与 x 轴之间的夹角（直线方向）
• 对于图像中的每个边缘点 $(x_i,y_i)$，可以反推出所有可能的 $(\rho ,\theta )$

---

3. 从图像空间到参数空间

对于一个边缘点 $(x_0,y_0)$，代入：

$$\rho =x_0\cos \theta +y_0\sin \theta$$

• 固定点 $(x_0,y_0)$，变换成参数空间中一条曲线（通常为正弦曲线）
• 多个点落在一条直线上 ↔ 它们的曲线在参数空间中有交点（同一 $(\rho ,\theta )$）

---

4. 累加器（Accumulator）

• 构建一个二维数组 $[\rho ,\theta ]$ 作为投票累加器

• 对图像中每个边缘点：

  • 枚举所有可能的 $\theta$（通常 0°–180°）
  • 计算对应的 $\rho$，对累加器对应格子 $(\rho ,\theta )$ 加一

• 最终累加器中峰值即代表图像中可能存在的直线

---

霍夫变换算法步骤（直线）

1. 边缘提取：使用 Canny、Sobel 等提取边缘点
2. 参数空间映射：每个边缘点计算多个 $(\rho ,\theta )$ 对应累加器投票
3. 峰值检测：在累加器中找出局部最大值，表示图像中潜在直线
4. 反映射回图像空间：将 $(\rho ,\theta )$ 反推为图像中的线段或直线

---

公式推导与几何意义

对于每个点 $(x,y)$ 与一个方向 $\theta$，其对应的直线 $\rho =x\cos \theta +y\sin \theta$ 是点法式直线：

• 可以理解为：过点 $(x,y)$ 并垂直于向量 $(\cos \theta ,\sin \theta )$ 的所有直线
• 即该点能“支持”所有法线方向为 $\theta$ 的直线
• 多个点支持同一个 $(\rho ,\theta )$ → 说明它们共线

---

扩展到圆的霍夫变换（Hough Circle Transform）

圆的一般方程为：

$$(x-a{)}^2+(y-b{)}^2=r^2$$

参数空间为 $(a,b,r)$，每个边缘点投票所有可能的圆心与半径：

• 输入边缘图 + 梯度方向（可以限制圆心方向）
• 构建三维累加器 $(a,b,r)$
• 找出高投票值的 $(a,b,r)$ → 检测圆

---

三、纯 C++ 霍夫变换检测直线实现不依赖 OpenCV

核心函数：HoughLineTransform

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

constexpr double DEG2RAD = M_PI / 180.0;

struct Line {
    double rho;
    double theta;
    int votes;
};

std::vector<Line> HoughLineTransform(const std::vector<std::pair<int, int>>& edge_points,
                                     int width, int height,
                                     int theta_steps = 180, int threshold = 100) {
    const int diag_len = static_cast<int>(std::sqrt(width * width + height * height));
    const int rho_max = diag_len;
    const int rho_min = -diag_len;
    const int rho_range = 2 * diag_len;

    std::vector<std::vector<int>> accumulator(rho_range, std::vector<int>(theta_steps, 0));

    // 遍历每个边缘点
    for (const auto& p : edge_points) {
        int x = p.first;
        int y = p.second;
        for (int t = 0; t < theta_steps; ++t) {
            double theta = t * DEG2RAD;
            double rho = x * std::cos(theta) + y * std::sin(theta);
            int rho_idx = static_cast<int>(std::round(rho)) + diag_len;
            if (rho_idx >= 0 && rho_idx < rho_range) {
                accumulator[rho_idx][t]++;
            }
        }
    }

    // 提取票数超过阈值的结果
    std::vector<Line> detected_lines;
    for (int r = 0; r < rho_range; ++r) {
        for (int t = 0; t < theta_steps; ++t) {
            int votes = accumulator[r][t];
            if (votes > threshold) {
                detected_lines.push_back({
                    .rho = r - diag_len,
                    .theta = t * DEG2RAD,
                    .votes = votes
                });
            }
        }
    }

    return detected_lines;
}

---

使用示例（模拟图像中直线）

int main() {
    int width = 200, height = 200;

    // 模拟一条对角线 y = x 的边缘点
    std::vector<std::pair<int, int>> edge_points;
    for (int i = 0; i < 200; ++i) {
        edge_points.emplace_back(i, i);
    }

    auto lines = HoughLineTransform(edge_points, width, height, 180, 50);

    std::cout << "Detected Lines:" << std::endl;
    for (const auto& line : lines) {
        std::cout << "rho: " << line.rho << ", theta (deg): " << line.theta * 180 / M_PI
                  << ", votes: " << line.votes << std::endl;
    }

    return 0;
}

---

四、结果解读

• 输出的每一条线由 (ρ, θ) 表示
• 可将其反转换为图像直线：

// 点 (x0, y0) 在线上：
x0 = rho * cos(theta)
y0 = rho * sin(theta)
// 方向向量：
dx = -sin(theta), dy = cos(theta)
// 可绘制直线 (x0 ± dx * scale, y0 ± dy * scale)

---

五、OpenCV 中的霍夫变换示例

示例：检测图像中的直线

#include <opencv2/opencv.hpp>
#include <iostream>

int main() {
    cv::Mat img = cv::imread("line_image.png", cv::IMREAD_GRAYSCALE);
    if (img.empty()) return -1;

    // 1. 边缘检测
    cv::Mat edges;
    cv::Canny(img, edges, 50, 150, 3);

    // 2. 霍夫变换检测直线
    std::vector<cv::Vec2f> lines;
    cv::HoughLines(edges, lines, 1, CV_PI / 180, 100); // ρ=1像素, θ=1°, 阈值=100票

    // 3. 显示结果
    cv::Mat color_img;
    cv::cvtColor(img, color_img, cv::COLOR_GRAY2BGR);
    for (size_t i = 0; i < lines.size(); i++) {
        float rho = lines[i][0], theta = lines[i][1];
        double a = cos(theta), b = sin(theta);
        double x0 = a * rho, y0 = b * rho;
        cv::Point pt1(cvRound(x0 + 1000 * (-b)), cvRound(y0 + 1000 * (a)));
        cv::Point pt2(cvRound(x0 - 1000 * (-b)), cvRound(y0 - 1000 * (a)));
        cv::line(color_img, pt1, pt2, cv::Scalar(0, 0, 255), 2);
    }

    cv::imshow("Detected Lines", color_img);
    cv::waitKey(0);
    return 0;
}

---

六、霍夫变换优缺点

优点：

• 鲁棒性强：对噪声和缺失数据有较强容忍度
• 能检测任意参数化形状（只要有表达式）

缺点：

• 运算复杂度高（尤其是圆或椭圆，参数空间更大）
• 精度依赖累加器分辨率
• 峰值检测容易受离散投票影响

---

七、应用场景

• 路线检测（如自动驾驶中检测车道线）
• 医疗图像（如识别圆形细胞或器官轮廓）
• 工业检测（如 PCB 板中的直线或圆形元件）
• OCR 文字行分割

---