使用SDL在C中实现Hough Transform检测数独网格的疑问

一、累加器数组处理与阈值匹配 #

霍夫变换的累加器数组核心是统计每个极坐标对(ρ, θ)对应的边缘点数量——值越高，说明这条直线上的边缘点越密集，越可能是数独的网格线。处理步骤如下：

• 阈值筛选：设定一个合理阈值（可根据图像边缘点总数的比例调整，常规数独场景阈值设为50左右即可），遍历累加器数组，将值大于等于阈值的(ρ, θ)对筛选出来，作为候选直线。
• 去重优化：相近的(ρ, θ)可能对应同一条直线，需做去重处理——比如当两个直线的θ差值小于1度（转弧度后）、ρ差值小于5像素时，视为同一条直线，只保留一个。

示例代码（C语言）：

// 假设acc是离散化后的累加器数组，theta_step是θ的离散步长（如0.5度转弧度）
// max_rho是图像对角线长度的一半，用于将rho的离散索引转换为实际极径值
#define THRESHOLD 50

typedef struct {
    float theta;
    float rho;
} Line;

void filter_lines(int acc[][MAX_RHO], int theta_count, int rho_count, 
                  float theta_step, float rho_step, float max_rho, 
                  Line* detected_lines, int* line_count) {
    *line_count = 0;
    for (int i = 0; i < theta_count; i++) {
        for (int j = 0; j < rho_count; j++) {
            if (acc[i][j] >= THRESHOLD) {
                float theta = i * theta_step;
                float rho = (j * rho_step) - max_rho;
                // 此处可加入去重逻辑，避免重复直线
                detected_lines[(*line_count)++] = (Line){theta, rho};
            }
        }
    }
}

二、极坐标直线转SDL可绘制的两点形式 #

SDL的SDL_RenderDrawLine()需要两个端点坐标，而霍夫变换的直线是极坐标形式ρ = x·cosθ + y·sinθ，转换逻辑是找到直线在图像边界上的两个有效交点：

1. 利用极坐标公式，分别计算直线与图像左边界（x=0）、右边界（x=width-1）、上边界（y=0）、下边界（y=height-1）的交点。
2. 筛选出落在图像范围内的两个交点，作为SDL绘制的端点。
3. 特殊情况处理：当θ接近0或π时，直线垂直于x轴，直接取x=ρ，y从0到height-1。

示例代码（C语言）：

#include <math.h>
#include <SDL2/SDL.h>

typedef struct {
    float theta;
    float rho;
} Line;

// 辅助函数：限制数值在指定范围内
int clamp(int val, int min, int max) {
    if (val < min) return min;
    if (val > max) return max;
    return val;
}

void draw_hough_line(SDL_Renderer* renderer, Line line, int width, int height) {
    float theta = line.theta;
    float rho = line.rho;
    float cos_theta = cos(theta);
    float sin_theta = sin(theta);
    int x1, y1, x2, y2;

    if (fabs(sin_theta) > 1e-6) {
        // 先尝试左边界交点
        y1 = round((rho - 0 * cos_theta) / sin_theta);
        x1 = 0;
        if (y1 < 0 || y1 >= height) {
            // 左边界交点无效，尝试上边界
            y1 = 0;
            x1 = round((rho - y1 * sin_theta) / cos_theta);
            if (x1 < 0 || x1 >= width) {
                // 上边界无效，尝试下边界
                y1 = height - 1;
                x1 = round((rho - y1 * sin_theta) / cos_theta);
            }
        }
        // 找第二个端点，先尝试右边界
        y2 = round((rho - (width - 1) * cos_theta) / sin_theta);
        x2 = width - 1;
        if (y2 < 0 || y2 >= height) {
            // 右边界无效，尝试下边界
            y2 = height - 1;
            x2 = round((rho - y2 * sin_theta) / cos_theta);
            if (x2 < 0 || x2 >= width) {
                // 下边界无效，尝试上边界
                y2 = 0;
                x2 = round((rho - y2 * sin_theta) / cos_theta);
            }
        }
    } else {
        // 直线垂直于x轴
        x1 = x2 = round(rho);
        y1 = 0;
        y2 = height - 1;
    }

    // 确保坐标在图像范围内
    x1 = clamp(x1, 0, width - 1);
    y1 = clamp(y1, 0, height - 1);
    x2 = clamp(x2, 0, width - 1);
    y2 = clamp(y2, 0, height - 1);

    SDL_RenderDrawLine(renderer, x1, y1, x2, y2);
}

内容的提问来源于stack exchange，提问作者m1nds