Hough Transformation c++

[goaran (Gast)]

Hallo.

benötige eine c++ Funktion die mir von einem Bild die Hough 
transformation macht,(will linien finden)
gibt es sowas irgendwo schon fertig ??

danke schon mal-

[Jörg (Gast)]

Es gibt sicherlich fertige Code-Fragmente zu Hough-Transformationen,
speziell für Linien-Erkennung. Aber selber eine Funktion/Modul zu
schreiben, sollte nicht so schwer sein. Das Prinzip Hough-Transformation
(nicht nur für Linien, sondern auch für kreise etc.) ist relativ einfach
zu verstehen. Berechne Für jeden Punkt alle Linien (oder Kreise etc), 
die
urch den Punkt laufen. Parametrisiere diese Linien (z.B. per Winkel und
Radius), und addiere dann für jeden Treffer eine "eins" im
Winkel-Radius-Array. Linien erkennst Du daran, dass in diesem Array ein
lokales Maximum mit einer gewissen Grösse (z.B. grösser Resolution/2)
vorliegt.
Speziell für Linien ergibt sich z.B. für einen Punkt:

  int px =  50      -- Punkt p = (x,y)
  int py =  70

  int wn = 128
  int wr = 128

  int wra(128,128) = {0,0,...}

  for wi = 0 to wn-1
   w = wi*2*PI/wn
   dx = cos(w);
   dy = sin(w);
   r = dx*px + dy*py      -- berechnet Radius
   ri = r*wr/sqrt(2)      -- berechnet Index

   wra(wi,ri) =  wra(wi,ri) + 1    -- inkrementiert Array-Wert

  next wi

(nur Pseudo-Code), sin/cos kann in Tabellen abgespeichert werden,
was die Berechnung erheblich beschleunigt. Falls Du Dich ein wenig
in z.B. Direct3D oder CUDA auskennst, kannst Du die Berechnungen um
Faktoren 50..100 beschleunigen.

Gruss,

Jörg

[kayar (Gast)]

ich hatte im rahmen meiner Dipl. Arbeit selber mit der hough 
transformation geraden in einem bild erkannt. ist eigentlich ganz 
simpel.

gehe über jeden pixel in deinem bild (am besten binärbild, um es zu 
vereinfachen) mit der formel

r = x * cos (phi) + y * sin (phi)

für phi von 0 ... 180°

und trage es in einen neuen Raum, wegen mir array, mit phi als x achse 
und y als r achse ein

als ergebnis für jeden punkt erhält man sinoide Kurven (sinuskurven :))

wenn man jetzt waagerechte geraden ermitteln will, geht man in den r,phi 
raum und schaut sich den bereich um 90° an und sucht dort die maximas, 
da sich die sinoiden kurven jeweils schneiden, wenn sie auf einer 
geraden liegen, bei waagerechten geraden schneiden sich dann die 
sinuskurven im r,phi raum bei rund 90°
der jeweilige r wert ergibt zurück auf das x,y bild transformierte bild 
die pixelreihe an

[goaran (Gast)]

Hallo, erst mal danke fuer die Antworten, ich habe das jetzt so geamcht:

xsize=obj_xsize_get(o);   //bildgrösse ermitteln

ysize=obj_ysize_get(o);

obj_alloc_byte(o2,180,2048,1024);   //neues objekt  erzeugen 




for(x=1;x<xsize;x++)

{

   for(y=1;y<ysize;y++)  

  {

  pixel=obj_pixel_get(o,x,y);

  if(pixel=1)

    {

    for(phi=1;phi<180;phi++)

      {

        r = x * cos (phi) + y * sin (phi);

        pixel=obj_pixel_get(o2,phi,r);

        neuwert=pixel+1;

        obj_pixel_set(o2,phi,r,neuwert);

        

      }

    }

  

  }

}

ist das so prinzipiell richtig oder ??
das problem ist, dass das so ewig duaert 2024 x 2024 pixel x 180 °  geht 
das nicht irgdnwei schneller mit ner anderen methode ?? bin für alle 
tipps dankbar ( sinuse sind schon tabelliert)

[Jörg (Gast)]

Im Prinzip richtig, aber schreib vieleicht nicht immer in der innersten
Schleife den Wert "neuwert" per

    obj_pixel_set(o2,phi,r,neuwert);

zurück. Ordne vieleicht mal die Schleifen neu an mit dem Ziel, möglichst
wenige Befehle/Speicherzugriffe in der innersten Schleife zu haben.

Bei 1024 X 2048 wird's aber immer lange dauern, solche Transformationen
sind immer sehr rechenintensiv; selbst wenn Du eine Fast-Hough
Transformation benutzt (ich gehe mal davon aus, dass das ganze nicht
auf einem uC laufen soll, der braucht dafür zu lange).

Ich habe mal vor zwei Jahren ein Algorithmus geschrieben, allerdings
nicht auf der CPU laufend, sondern per Graphik-Karte (Direct3D-SDK)
beschleunigt => 50 Bilder und mehr je Sekunde bei glaube ich 1024 X 
1024. Heutige Graphik-Karten schaffen sicherlich weit mehr als 100
Transformationen je Sekunde.

Gruss

Jörg

[goaran (Gast)]

nee das läuft auf nem normaln rehcner, nicht auf nem uC , wegen der FHT 
werde ich mich mal erkundigen, das hört sich ganz gut an..
das ganze muss auch nicht in echtzeit laufen, wenn es ein paar sekunden 
dauert ist es ok, aber gerade braucht es eher n paar minuten.. leigt 
vielciht auch an diesen makro-befehlen ( das ganze wird bis jetzt als 
makro in nem c++ programm eingebunden), muss ich wohl mal "richtig" 
einbauen.
mit grafikkartenprogrammierung kenn ich mich leider überhaupt nicht 
aus.. :(

[_matze (Gast)]

Auch wenn der Thread nicht mehr aktuell ist... die OpenCV-Library bietet 
auch Funktionen zur Hough-Transformation (cvHough...), die auch keine 
Minuten brauchen. ;)