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

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]++;
    }
  }
}

我被困在映射和过滤上，这是根据文章:

1. 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).

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

3. 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.

4. 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);

5. ...

编辑

根据@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

你的角度是度数而不是Arc度!

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

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 之前，您需要将所有角度转换为Arc度。

在第一个循环中我得到了

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 使用rust 了(实际上不存在)，所以有更好的方法来进行转换，并且应该有一个常数，在某处具有 pi 的精确值。