在二维坐标系下实现霍夫变换直线检测

Question

我想在一个简单的坐标系中实现直线检测。我大致按照一篇关于如何实现的文章the Hough Transform，但我得到的结果与我想要的相差甚远

给定一个像这样的 3 x 3 矩阵：

X X X
X X X
- - -

我想检测从 0,0 开始到 2,0 的行。我将坐标系表示为一个简单的元组数组，元组中的第一项是 x，第二项是 y，第三项是点的类型（canvas 或线）。

我认为使用 Hough 检测线会相对容易，因为边缘检测基本上只是一个二元决定：元组是否为线类型。

我用 Rust 实现了以下程序：

use std::f32;

extern crate nalgebra as na;
use na::DMatrix;

#[derive(Debug, PartialEq, Clone)]
enum Representation {
   Canvas,
   Line,
}

fn main () {
    let image_width = 3;
    let image_height = 3;

    let grid = vec![
        (0, 0, Representation::Line), (1, 0, Representation::Line), (2, 0, Representation::Line),
        (0, 1, Representation::Canvas), (1, 1, Representation::Canvas), (2, 1, Representation::Canvas),
        (0, 2, Representation::Canvas), (1, 2, Representation::Canvas), (2, 2, Representation::Canvas),
    ];

    //let tmp:f32 = (image_width as f32 * image_width as f32) + (image_height as f32 * image_height as f32);
    let max_line_length = 3;
    let mut accumulator = DMatrix::from_element(180, max_line_length as usize, 0);

    for y in 0..image_height {
        for x in 0..image_width {
            let coords_index = (y * image_width) + x;
            let coords = grid.get(coords_index as usize).unwrap();

            // check if coords is an edge
            if coords.2 == Representation::Line {
                for angle in 0..180 {
                    let r = (x as f32) * (angle as f32).cos() + (y as f32) * (angle as f32).sin();
                    let r_scaled = scale_between(r, 0.0, 2.0, -2.0, 2.0).round() as u32;

                    accumulator[(angle as usize, r_scaled as usize)] += 1;
                }
            }
        }
    }

    let threshold = 3;

    // z = angle
    for z in 0..180 {
        for r in 0..3 {
            let val = accumulator[(z as usize, r as usize)];

            if val < threshold {
                continue;
            }

            let px = (r as f32) * (z as f32).cos();
            let py = (r as f32) * (z as f32).sin();

            let p1_px = px + (max_line_length as f32) * (z as f32).cos();
            let p1_py = py + (max_line_length as f32) * (z as f32).sin();

            let p2_px = px - (max_line_length as f32) * (z as f32).cos();
            let p2_py = px - (max_line_length as f32) * (z as f32).cos();

            println!("Found lines from {}/{} to {}/{}", p1_px.ceil(), p1_py.ceil(), p2_px.ceil(), p2_py.ceil());
        }
    }
}

fn scale_between(unscaled_num: f32, min_allowed: f32, max_allowed: f32, min: f32, max: f32) -> f32 {
    (max_allowed - min_allowed) * (unscaled_num - min) / (max - min) + min_allowed
}

结果类似于：

Found lines from -1/4 to 1/1
Found lines from 2/4 to 0/0
Found lines from 2/-3 to 0/0
Found lines from -1/4 to 1/1
Found lines from 1/-3 to 0/0
Found lines from 0/4 to 1/1
...

考虑到我只想检测一行，这实际上很多。我的实现显然是错误的，但我不知道从哪里看，我的数学功底还不够高，无法进一步调试。

我认为第一部分，即实际的霍夫变换，似乎是正确的，因为链接的文章说：

for each image point p 
{
  if (p is part of an edge)
  {
    for each possible angle
    {
     r = x * cos(angle) + y * sin(angle);
     houghMatrix[angle][r]++;
    }
  }
}

我被困在映射和过滤上，根据文章：

Each point in Hough space is given by angle a and distance r. Using these values, one single point p(x,y) of the line can be calculated by px = r * cos(angle) py = r * sin(angle).

The maximum length of a line is restricted by sqrt(imagewidth2 + imageheight2).

The point p, the angle a of the line and the maximum line length 'maxLength' can be used to calculate two other points of the line. The maximum length here ensures that both points to be calculated are lying outside of the actual image, resulting in the fact that if a line is drawn between these two points, the line goes from image border to image border in any case and is never cropped somewhere inside the image.

These two points p1 and p2 are calculated by: p1_x = px + maxLength * cos(angle); p1_y = py + maxLength * sin(angle); p2_x = px - maxLength * cos(angle); p2_y = py - maxLength * sin(angle);

...

编辑

根据@RaymoAisla

的建议，将图像大小考虑在内的更新版本

use std::f32;

extern crate nalgebra as na;
use na::DMatrix;

fn main () {
    let image_width = 3;
    let image_height = 3;

    let mut grid = DMatrix::from_element(image_width as usize, image_height as usize, 0);
    grid[(0, 0)] = 1;
    grid[(1, 0)] = 1;
    grid[(2, 0)] = 1;

    let accu_width = 7;
    let accu_height = 3;
    let max_line_length = 3;

    let mut accumulator = DMatrix::from_element(accu_width as usize, accu_height as usize, 0);


    for y in 0..image_height {
        for x in 0..image_width {
            let coords = (x, y);
            let is_edge = grid[coords] == 1;

            if !is_edge {
                continue;
            }

            for i in 0..7 {
                let angle = i * 30;

                let r = (x as f32) * (angle as f32).cos() + (y as f32) * (angle as f32).sin();
                let r_scaled = scale_between(r, 0.0, 2.0, -2.0, 2.0).round() as u32;

                accumulator[(i as usize, r_scaled as usize)] += 1;

                println!("angle: {}, r: {}, r_scaled: {}", angle, r, r_scaled);
            }
        }
    }

    let threshold = 3;

    // z = angle index
    for z in 0..7 {
        for r in 0..3 {
            let val = accumulator[(z as usize, r as usize)];

            if val < threshold {
                continue;
            }

            let px = (r as f32) * (z as f32).cos();
            let py = (r as f32) * (z as f32).sin();

            let p1_px = px + (max_line_length as f32) * (z as f32).cos();
            let p1_py = py + (max_line_length as f32) * (z as f32).sin();

            let p2_px = px - (max_line_length as f32) * (z as f32).cos();
            let p2_py = px - (max_line_length as f32) * (z as f32).cos();

            println!("Found lines from {}/{} to {}/{} - val: {}", p1_px.ceil(), p1_py.ceil(), p2_px.ceil(), p2_py.ceil(), val);
        }
    }
}

fn scale_between(unscaled_num: f32, min_allowed: f32, max_allowed: f32, min: f32, max: f32) -> f32 {
    (max_allowed - min_allowed) * (unscaled_num - min) / (max - min) + min_allowed
}

报告的输出现在是：

angle: 0, r: 0, r_scaled: 1
angle: 30, r: 0, r_scaled: 1
angle: 60, r: 0, r_scaled: 1
angle: 90, r: 0, r_scaled: 1
angle: 120, r: 0, r_scaled: 1
angle: 150, r: 0, r_scaled: 1
angle: 180, r: 0, r_scaled: 1
...
Found lines from 3/4 to -1/-1
Found lines from -3/1 to 2/2

我在坐标系上绘制了线条，这些线条与我期望的线条相距甚远。我想知道转换回积分是否仍然关闭。

Answer 1

霍夫变换的原理是搜索所有经过每个考虑点的线，并通过累加器计算这些线的出现次数。

但是，我们无法确定所有这些线，因为它们的数量是无限的。而且图像是离散化的，所以计算所有的线没有意义。

问题就出在这个离散化上。角度离散化需要与图像大小相关。这里计算180度角的半径是多算了，因为图片只有9个像素，而且这张图片中任何一条线可能的角度都限制在十几个值。

所以在这里，对于第一个点 (0,0)，对于每个角度，关联的半径为 r = 0

对于第二个 (1,0)，关联的半径为 r = cos(angle)

对于第三个 (2,0)，关联的半径为 r = 2 cos(angle)

四舍五入后，同一角度的多个值的关联半径为0，这会导致过度检测。离散化导致 Hough 累加器的扩散。

所以需要根据图片大小计算半径和角度的离散化。这里，30°的步长，所以一个7*3的累加器足以检测一条线。

Answer 2

你的角度是度数而不是弧度！

与所有其他编程语言一样，Rust 的三角函数使用弧度。运行

let ang_d = 30.0;
let ang_r = ang_d * 3.1415926 / 180.0;
println!("sin(30) {} sin(30*pi/180) {}", (ang_d as f32).sin(), (ang_r as f32).sin());

给出结果

sin(30) -0.9880316 sin(30*pi/180) 0.5

在调用 cos 和 sin 之前，您需要将所有角度转换为弧度。

在第一个循环中我得到了

let angle = (i as f32) * 30.0 * 3.1415926 / 180.0;
let r = (x as f32) * (angle as f32).cos() + (y as f32) * (angle as f32).sin();

在第二个计算线上的点

let ang = (z as f32) * 30.0 * 3.1415926 / 180.0;
let px = (r as f32) * (ang as f32).cos();
let py = (r as f32) * (ang as f32).sin();
let p1_px = px + (max_line_length as f32) * (ang as f32).cos();          
let p1_py = py + (max_line_length as f32) * (ang as f32).sin();
let p2_px = px - (max_line_length as f32) * (ang as f32).cos();
let p2_py = px - (max_line_length as f32) * (ang as f32).cos();

我的 Rust 生锈了（实际上不存在），所以有更好的方法来进行转换，并且应该有一个常数，在某处具有 pi 的精确值。

在二维坐标系下实现霍夫变换直线检测

Implementing Hough transform line detection in 2D coordinate system

algorithm

math

rust

ascii-art