在2D坐标系中实现Hough变换线检测

Question

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

给出一个3×3矩阵是这样的：

X X X 
X X X 
- - - 

我想检测线起点在0,0要2,0。我将坐标系表示为一个简单的元组数组，元组中的第一项是x，第二项是y，第三项是点（画布或线）的类型。

我认为使用Hough来检测这条线会比较容易，因为边缘检测基本上只是一个二元决策：元组是类型行，或者不是。

我鲁斯特执行以下程序：

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

这实际上是相当多的，因为我只想检测一行。我的执行很明显是错误的，但我不知道在哪里看，我的数学-fu不够高，无法进一步调试。

我认为第一部分，实际Hough变换，似乎有点正确的，因为链接的文章说：

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. 在霍夫空间的每个点由角度和距离r给出。使用这些值，线的单个点p（x，y）可以通过下式计算：px = r * cos（角度） py = r * sin（角度）。

2. 行的最大长度受sqrt（imagewidth2 + imageheight2）的限制。

3. 点p，线的角度α和最大线长度'maxLength'可以用来计算线的其他两点。这里的最大长度确保这两个要计算的点位于实际图像之外，导致如果在这两个点之间画出一条线，则该线从图像边界到图像边界无论如何也不会被裁剪图像内的某处。

4. 这两个点p1和p2的计算公式如下： 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

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

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

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(); 

我是锈锈（实际上不存在的），所以有是进行转换的更好的方法，并且在某处应该有一个与pi的确切值相同的常量。

Answer 2

霍夫变换原理是搜索所有通过每个考虑点的线，并计数这些线发生感谢累加器。

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

问题来自于这种离散化。角度离散化需要与图像大小相关。在这里，计算180度角的半径是过度计算，因为图像只能生成9个像素，并且此图像中任何线的可能角度都被限制为十几个值。

所以在这里，对第一点（0,0），对于每一个角，所述相关联的半径为r = 0

对于第二（1,0），相关联的半径为r = COS（角）

对于第三（2,0），相关联的半径为r = 2 cos（角度）

随着舍入，许多值将具有0相关联的半径为相同的角度，并且它导致过检测。离散化导致霍夫累加器的扩散。

因此需要根据图像大小计算半径和角度离散。这里，一个30°的台阶，所以一个7 * 3的累加器就足以检测一条线。