Implementierung der Hough-Transformationserkennung im 2D-Koordinatensystem

Question

Ich möchte die Linienerkennung in einem einfachen Koordinatensystem implementieren. Ich folgte grob einem Artikel darüber, wie man the Hough Transform implementiert, aber die Ergebnisse, die ich bekomme, sind ziemlich weit weg von dem, was ich will.

X X X 
X X X 
- - - 

ich die Linie ab 0,0 gehen 2,0 erkennen wollen:

eine 3 x 3-Matrix wie folgt gegeben. Ich stelle das Koordinatensystem als ein einfaches Array von Tupeln dar, das erste Element im Tupel ist x, das zweite ist y, das dritte ist der Typ des Punktes (Leinwand oder Linie).

Ich dachte, es wäre relativ einfach, die Linie mit Hough zu erkennen, weil die Kantenerkennung im Grunde nur eine binäre Entscheidung ist: Entweder ist das Tupel vom Typ Linie, oder nicht.

ich das folgende Programm in Rust umgesetzt:

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 
} 

Das Ergebnis ist so etwas wie:

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

die eigentlich ziemlich viel, gegeben ist, dass ich möchte nur eine einzige Zeile erfassen. Meine Implementierung ist eindeutig falsch, aber ich weiß nicht, wo ich hinschauen soll, mein Mathe-Fu ist nicht hoch genug, um weiter zu debuggen.

denke ich, der erste Teil, der eigentliche Hough-Transformation, scheint Art richtig, weil der verlinkten Artikel sagt:

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

Ich bin bei Mapping und Filtern stecken, die gemäß der Artikel:

1. Jeder Punkt in Hough-Raum durch den Winkel a und den Abstand r gegeben ist. Mit diesen Werten kann ein einzelner Punkt p (x, y) der Linie berechnet werden durch px = r * cos (Winkel) py = r * sin (Winkel).

2. Die maximale Länge einer Zeile ist begrenzt durch sqrt (imagewidth2 + imageheight2).

3. Der Punkt p, der Winkel a der Linie und die maximale Linienlänge 'maxLength' können verwendet werden, um zwei andere Punkte der Linie zu berechnen. Die maximale Länge stellt dabei sicher, dass beide zu berechnenden Punkte außerhalb des eigentlichen Bildes liegen, was dazu führt, dass bei einer Linie zwischen diesen beiden Punkten die Linie von Bildgrenze zu Bildgrenze in jedem Fall verläuft und niemals beschnitten wird irgendwo im Bild.

4. Diese beiden Punkte p1 und p2 werden wie folgt berechnet: p1_x = px + maxLength * cos (angle); p1_y = py + maxLength * sin (Winkel); p2_x = px - maxLength * cos (Winkel); p2_y = py - maxLength * sin (Winkel);

5. ...

EDIT

aktualisierte Version, die die Bildgröße berücksichtigt, wie

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 
} 

von @RaymoAisla vorgeschlagen

Der gemeldete Ausgabe ist jetzt:

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 zeichnete die Linien auf einem Koordinatensystem, die Linien sind sehr weit von der Linie entfernt, die ich erwarten würde. Ich frage mich, ob die Umstellung auf Punkte noch aus ist.

Answer 1

Ihre Winkel sind in Grad und nicht im Bogenmaß!

Rust verwendet wie alle anderen Programmiersprachen das Radiant für seine Trigonometriefunktionen.

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

Laufen gibt die Ergebnisse

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

Sie müssen alle Ihre Winkel in Radiant konvertieren, bevor cos und sin aufrufen.

In der ersten Schleife I

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

und in der zweiten haben, wo Sie die Punkte auf den Linien

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

Mein Rust ist rostig (eigentlich nicht existent), so gibt berechnen ist eine bessere Möglichkeit, die Konvertierung durchzuführen, und es sollte irgendwo eine Konstante mit dem genauen Wert von pi geben.

Answer 2

Das Hough-Transform-Prinzip besteht darin, alle Linien zu durchsuchen, die durch jeden betrachteten Punkt gehen, und diese Linienvorkommen durch den Akkumulator zu zählen.

Wir können jedoch nicht alle diese Zeilen bestimmen, weil ihre Anzahl unendlich ist. Außerdem ist das Bild diskretisiert, so dass die Berechnung aller Zeilen keinen Sinn ergibt.

Und das Problem kommt von dieser Diskretisierung. Die Winkeldiskretisierung muss für die Bildgröße relevant sein. Hier ist die Berechnung des Radius für 180 Winkel eine Überberechnung, da das Bild nur 9 Pixel macht und die möglichen Winkel für jede Linie in diesem Bild auf ein Dutzend Werte beschränkt sind.

So hier, für den ersten Punkt (0,0), für jeden Winkel, der zugehörige Radius r = 0

Für die zweite (1,0), wird der zugehörige Radius r = cos (Winkel)

für den dritten (2,0), r = 2 cos (Winkel) der zugehörige Radius haben

Mit der Abrundung zahlreiche Werte eine zugehörige Radius von 0 für den gleichen Winkel, und es Ursache Überdetektion. Diskretisierung verursacht eine Verbreitung von Hough Accumulator.

Also muss der Radius und die Winkeldiskretisierung abhängig von der Bildgröße berechnet werden. Hier ist ein 30 ° -Schritt, also ein 7 * 3-Akku reicht aus, um eine Linie zu erkennen.