二次元座標系でのハフ変換線検出の実装

Question

簡単な座標系で線検出を実装したいと思います。私はおおよそthe Hough Transformの実装方法に関する記事をたどったが、私が得た結果は私が望むものからかなり離れている。私は2,0に行く0,0で始まる行を検出したい

X X X 
X X X 
- - - 

：

は、このような3×3行列を考えます。私はタプルの単純な配列として座標系を表し、タプルの最初の項目はx、2番目はy、3番目はポイント（キャンバスまたはライン）のタイプです。

私は、エッジ検出が基本的に単なるバイナリの決定であるため、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 
... 

。私の実装ははっきりと間違っていますが、見た目がわからないので、私のmaths-fuはそれ以上デバッグするのに十分ではありません。

私は最初の部分を考えて、実際のハフ変換、リンク先の記事は言うので、一種の正しいようだ：、私はマッピングおよびフィルタリングにこだわっている

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で与えられます。これらの値を用いて、直線の1つの点p（x、y）は、 px = r * cos（angle） py = r * sin（angle）によって計算することができる。

2. 行の最大長は、sqrt（imagewidth2 + imageheight2）によって制限されます。

3. 点p、線の角度aおよび最大線長 'maxLength'を使用して、線の他の2つの点を計算することができます。ここで最大の長さは、両方の点が実際の画像の外側にあることを保証します。その結果、これらの2点間に線が引かれると、線は画像境界から画像境界に移動し、決して切り取られません画像のどこかにある。

4. これらの2つの点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. ...

EDIT

@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 

I座標系上の線をプロットすると、線は私が期待する線から非常に遠く離れています。私は、ポイントへの変換がまだオフであるのだろうかと思います。

Answer 1

あなたの角度はラジアンではなく度です。

他のプログラミング言語と同様に、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()); 

を実行すると、あなたがcosとsinを呼び出す前にラジアンにすべてのあなたの角度を変換する必要が結果

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

を与えます。私は

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ピクセルしか作成しないため、このイメージの任意の線に対する可能な角度は12値に制限されています。そこでここでは、最初の点（0,0）のための

は、各角度に対して、関連半径は第（1,0）の場合、R = 0

で、関連する半径は、r = COS（角度であります関連半径は丸めで= 2つのcos（角度）

Rである））2,0（第3について

、多数の値が同じ角度0の関連する半径を有し、それの原因となります過剰検出。離散化はHough Accumulatorの拡散を引き起こします。

したがって、画像のサイズに応じて半径と角度の離散化を計算する必要があります。ここでは30°ステップなので、7×3のアキュムレータでラインを検出するのに十分です。