在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的累加器就足以檢測一條線。