Hough 变换

基于参数空间投票的几何形状检测方法

提出年份: 1962 年
提出者: Paul Hough
适用: 直线、圆、椭圆等

复杂度: O(N×Θ)
空间: O(Ρ×Θ)
变种: 概率 Hough、广义 Hough

核心原理：点 - 线对偶性

flowchart LR A[输入边缘图] --> B[初始化累加器] B --> C[遍历边缘点] C --> D[投票累加] D --> E[查找峰值] E --> F[提取直线参数] F --> G[绘制直线]

原理说明

点 - 线对偶性：图像空间中的一条直线对应参数空间中的一个点；图像空间中的一个点对应参数空间中的一条正弦曲线。共线的点在参数空间中表现为相交的正弦曲线，交点即为所求直线的参数。

直线极坐标表示

ρ = x · cos(theta) + y · sin(theta)

ρ (rho): 直线到原点的垂直距离
theta (theta): 垂线与 x 轴的夹角

ρ 范围: [0, sqrt(W2+H2)]
theta 范围: [0°, 180°]

算法流程

sequenceDiagram participant Input as 输入图像 participant Edge as 边缘检测 participant Init as 初始化累加器 participant Vote as 投票累加 participant Find as 寻找峰值 participant Convert as 参数转换 participant Output as 输出直线 Input->>Edge: Canny 边缘检测 Note over Edge: 获取边缘点集 Edge->>Init: 创建 A[ρ,theta]累加器 Note over Init: ρ和theta离散化 Init->>Vote: 遍历边缘点 loop 每个边缘点 (x,y) Vote->>Vote: 遍历所有theta Note over Vote: 计算ρ=x·costheta+y·sintheta Vote->>Vote: A[ρ,theta]++ end Vote->>Find: 寻找局部最大值 Note over Find: A[ρ,theta] > 阈值 Find->>Convert: 峰值转直线参数 Convert->>Output: 绘制检测直线

算法步骤详解

首先对输入图像进行边缘检测（通常使用 Canny 算子），获取边缘点集合。这些边缘点是后续 Hough 变换的输入。

flowchart LR A[原始图像] --> B[Canny 边缘检测] B --> C[二值边缘图] C --> D[边缘点坐标集] style D fill:#e8f5e9

将连续的参数空间离散化为累加器数组：

ρ 轴: 从 -ρ_max 到 +ρ_max，步长通常为 1 像素
theta 轴: 从 0°到 180°，步长通常为 1°

Python

# 参数空间大小
rho_max = sqrt(width2 + height2)
rho_bins = 2 * rho_max  # 步长为 1
theta_bins = 180  # 步长为 1 度
accumulator = zeros((rho_bins, theta_bins))

对每个边缘点，遍历所有可能的theta值，计算对应的ρ值，并在累加器中对应位置投票。

flowchart TD A[边缘点集] --> B{遍历每个点} B --> C[遍历theta∈[0°,180°]] C --> D[计算ρ=x·costheta+y·sintheta] D --> E[累加器 A[ρ,theta]++] E --> F{theta遍历完？} F -->|否 | C F -->|是 | G{点遍历完？} G -->|否 | B G -->|是 | H[累加器完成] style H fill:#e8f5e9

在累加器中寻找局部最大值点，这些峰值对应图像中的直线。只有超过阈值的峰值才被接受。

flowchart LR A[累加器] --> B[寻找局部最大值] B --> C{A[ρ,theta] > 阈值？} C -->|是 | D[记录直线参数] C -->|否 | E[忽略] style D fill:#e8f5e9 style E fill:#ffebee

投票过程可视化

flowchart TD subgraph 图像空间 P1[点 1 x₁,y₁] P2[点 2 x₂,y₂] P3[点 3 x₃,y₃] L[共线] end subgraph 参数空间 C1[正弦曲线 1] C2[正弦曲线 2] C3[正弦曲线 3] IP[交点 ρ₀,theta₀] end P1 --> C1 P2 --> C2 P3 --> C3 P1 & P2 & P3 --> L C1 & C2 & C3 --> IP style IP fill:#ff5722,color:#fff style L fill:#4caf50,color:#fff

三个共线点在参数空间中对应三条相交的正弦曲线，交点即为检测到的直线参数

算法可视化

算法流程图

flowchart LR A[边缘图] --> B[累加器] B --> C[投票] C --> D[找峰值] D --> E[提取直线] E --> F[绘制]

参数与特性

参数	说明	影响
ρ分辨率	距离量化精度	越小检测越精确
theta分辨率	角度量化精度	影响角度精度
阈值	最小投票数	决定直线检测灵敏度

Python 实现

Python

import cv2
import numpy as np
import matplotlib.pyplot as plt

def hough_line_transform(image_path, threshold=100):
    """
    使用 OpenCV 实现标准 Hough 变换
    :param image_path: 输入图像路径
    :param threshold: 累加器阈值
    :return: 原图和检测到直线的图像
    """
    # 读取图像
    img = cv2.imread(image_path)
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

    # 边缘检测
    edges = cv2.Canny(gray, 50, 150, apertureSize=3)

    # 使用 HoughLines 检测直线
    lines = cv2.HoughLines(edges, 1, np.pi/180, threshold)

    # 在原图上绘制检测到的直线
    img_with_lines = img.copy()
    if lines is not None:
        for rho, theta in lines[:, 0]:
            # 计算直线的起点和终点
            a = np.cos(theta)
            b = np.sin(theta)
            x0 = a * rho
            y0 = b * rho
            x1 = int(x0 + 1000 * (-b))
            y1 = int(y0 + 1000 * (a))
            x2 = int(x0 - 1000 * (-b))
            y2 = int(y0 - 1000 * (a))

            # 绘制直线
            cv2.line(img_with_lines, (x1, y1), (x2, y2), (0, 0, 255), 2)

    return img, img_with_lines

def probabilistic_hough_transform(image_path, threshold=50, 
                                   min_line_length=50, max_line_gap=10):
    """
    使用概率 Hough 变换检测直线
    :param image_path: 输入图像路径
    :param threshold: 累加器阈值
    :param min_line_length: 最小直线长度
    :param max_line_gap: 最大线段间隙
    :return: 原图和检测到直线的图像
    """
    # 读取图像
    img = cv2.imread(image_path)
    gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

    # 边缘检测
    edges = cv2.Canny(gray, 50, 150, apertureSize=3)

    # 使用概率 Hough 变换检测直线
    lines = cv2.HoughLinesP(edges, 1, np.pi/180, threshold, 
                           minLineLength=min_line_length, 
                           maxLineGap=max_line_gap)

    # 在原图上绘制检测到的直线
    img_with_lines = img.copy()
    if lines is not None:
        for x1, y1, x2, y2 in lines[:, 0]:
            cv2.line(img_with_lines, (x1, y1), (x2, y2), (0, 255, 0), 2)

    return img, img_with_lines

# 使用示例
if __name__ == "__main__":
    img, result = hough_line_transform('image.jpg', threshold=100)
    prob_img, prob_result = probabilistic_hough_transform('image.jpg', threshold=50)
    
    plt.figure(figsize=(15, 5))
    plt.subplot(1, 3, 1)
    plt.imshow(cv2.cvtColor(img, cv2.COLOR_BGR2RGB))
    plt.title('Original Image')
    plt.subplot(1, 3, 2)
    plt.imshow(cv2.cvtColor(result, cv2.COLOR_BGR2RGB))
    plt.title('Standard Hough')
    plt.subplot(1, 3, 3)
    plt.imshow(cv2.cvtColor(prob_result, cv2.COLOR_BGR2RGB))
    plt.title('Probabilistic Hough')
    plt.show()

算法优缺点

优点

对噪声具有一定的鲁棒性
能够检测不完整或断裂的直线
可以同时检测多条直线
参数化表示便于后续处理
可扩展到检测圆、椭圆等形状

缺点

计算复杂度较高，特别是对于大图像
需要合适的参数设置
对于密集的边缘图像，可能会产生虚假检测
内存消耗较大（需要累加器数组）

参数调节指南

参数	含义	调节建议	影响
rho	距离分辨率	通常为 1 像素	越小精度越高，计算越慢
theta	角度分辨率	通常为π/180 (1°)	越小精度越高，累加器越大
threshold	累加器阈值	根据图像大小调整	越高检测到的直线越少但越可靠
minLineLength	最小线段长度	仅用于 HoughLinesP	过滤短线段
maxLineGap	最大线段间隙	仅用于 HoughLinesP	连接断裂线段

应用场景

文档分析

检测表格线、文本行

车道线检测

自动驾驶中的车道识别

建筑分析

检测建筑结构线条

工业检测

产品缺陷检测

机器人视觉

导航和定位

形状检测

扩展到圆、椭圆检测

Hough 变换变种

变种	原理	优点	缺点
标准 Hough	遍历所有点和角度	检测精确	计算慢，内存大
概率 Hough	随机采样边缘点	速度快，输出线段	可能漏检
广义 Hough	使用 R 表存储形状	可检测任意形状	需要模板，复杂
圆 Hough	三维参数空间 (a,b,r)	可检测圆形	计算量更大

算法信息卡

提出年份: 1962 年
提出者: Paul Hough
适用: 直线、圆、椭圆等
时间复杂度: O(N×Θ)
空间复杂度: O(Ρ×Θ)
变种: 概率 Hough、广义 Hough

show_chartHough 变换

Hough 变换

lightbulb 核心原理：点 - 线对偶性

info 原理说明

直线极坐标表示

算法流程

算法步骤详解

步骤 1: 边缘检测

步骤 2: 参数空间离散化

步骤 3: 投票累加

步骤 4: 峰值检测

投票过程可视化

analytics 算法可视化

flowchart 算法流程图

table_chart 参数与特性

Python 实现

算法优缺点

thumb_up 优点

thumb_down 缺点

参数调节指南

应用场景

文档分析

车道线检测

建筑分析

工业检测

机器人视觉

形状检测

Hough 变换变种

算法信息卡

相关算法

Hough 变换

核心原理：点 - 线对偶性

原理说明

算法可视化

算法流程图

参数与特性

优点

缺点