Canny edge algorithmus und Sobel Matrix

[Gutelo]

Hallo Medium,

der Code ist in dem Zip-file des vorletzten Posts

Gutelo

[Medium]

Oh, dachte da wäre die NMS noch nicht bei gewesen. Scusi! Werde ich heute und vermutlich auch morgen aber nicht mehr zu kommen leider

[Gutelo]

Kein Problem, ich poste es hier auch noch mal:

Delphi-Quellcode:

// ############################################################################
// Build pixel array of gradient directions
// ############################################################################

Procedure MakeEdgeDirections(PA_Sx, PA_Sy : TPixelArray; var PA_Out : TPixelArray);
//
var rows, cols : Integer;
    Th : Double;         // Angle Theta
//
begin
   // Set dimensions of output pixel array
   SetLength(PA_Out, Length(PA_Sx));
   For rows := 0 to High(PA_Out) do SetLength(PA_Out[rows], Length(PA_Sx[0]));
   // calculate output pixel array:
   For rows := 0 to High(PA_Sx) do
   For cols := 0 to High(PA_Sx[0]) do
   begin
      Th := (180/Pi) * ArcTan2(PA_Sy[rows,cols],PA_Sx[rows,cols]);
      // write output pixel array
      PA_Out[rows,cols] := Round(Th);
   end;
end;

Function FMod(x,y : Double) : Double;
begin
   If y = 0 then
   begin
     Showmessage('Error in function FMod: Cannot divide through 0');
     FMod := 0;
   end
   else
   begin
     FMod := x-Int(x/y)*y;
   end;
end;

// ############################################################################
// Perform Non-maximum Suppression (quantisized way)
// ############################################################################

// Symmetry => 180 degree cover the four main directions: 0,45,90,and 135 deg
// Corresponding equivalent directions: 180,225,270,and 315 deg

// Divide the 180 degree region into four quadrant sections
//  (0) to (Pi/8) and (Pi-(Pi/8)) to (Pi)  <= quadrant around 0 (or symmetry equivalent
//                                                               180 deg,respectively)
//  (1*Pi/4) +- Pi/8    <= quadrant around  45 deg
//  (2*Pi/4) +- Pi/8    <= quadrant around  90 deg
//  (3*Pi/4) +- Pi/8    <= quadrant around 135 deg

// Introduce 'dir' value: dir := (FMod(PA_ED[rows,cols]+180, 180) /180) * 8
// Used to classify the member quadrant for a particular gradient direction
//
// How 'dir' works:
// Example: Input angle at point (x,y) : PA_ED[x,y] = -135
//          Shift to get positive angle: PA_ED[x,y] + 180 = 45
//          Value on 'dir' scale: (FMod(45,180)/180)*8= (45/180)*8 = 2
//
// Integer 'dir' values correspond to the following angles:
//         dir = 0  <=> Th =   0           = 0      { center of 1st quadrant
//         dir = 1  <=> Th =   Pi/8        = 1*Pi/8 <= border from 1st to 2nd quadrant
//         dir = 2  <=> Th =   Pi/4        = 2*Pi/8 { center of 2nd quadrant
//         dir = 3  <=> Th =   Pi/4 + Pi/8 = 3*Pi/8 <= border from 2nd to 3rd quadrant
//         dir = 4  <=> Th =   Pi/2        = 4*Pi/8 { center of 3rd quadrant
//         dir = 5  <=> Th =   Pi/2 + Pi/8 = 5*Pi/8 <= border from 3rd to 4th quadrant
//         dir = 6  <=> Th = 3*Pi/4        = 6*Pi/8 { center of 4th quadrant
//         dir = 7  <=> Th = 3*Pi/4 + Pi/8 = 7*Pi/8 <= border from 4th to 1st quadrant
//         dir = 8  <=> Th =   Pi          = 8*Pi/8 { center of 1st quadrant

Procedure MakeNMS(PA_SO, PA_ED : TPixelArray; var PA_Out : TPixelArray);
//
var dir : Double;
    rows, cols : Integer;
//
begin
   // Set dimensions of output pixel array
   SetLength(PA_Out, Length(PA_SO));
   For rows := 0 to High(PA_Out) do SetLength(PA_Out[rows], Length(PA_SO[0]));
   // Calculate output pixel array:
   For rows := 1 to High(PA_SO)-1 do
   For cols := 1 to High(PA_SO[0])-1 do
   begin
      // Calculate 'dir' value to determine the right quadrant
      dir := (FMod(PA_ED[rows,cols]+180, 180) /180) * 8;
      //
      // Check membership in quadrant, keep maxima,or suppress minima
      //
      // 0 degree quadrant (EE <-> WW)
      If  ((dir <= 1) or (dir > 7))
          and (PA_SO[rows,cols] > PA_SO[rows,cols+1])  // EE
          and (PA_SO[rows,cols] > PA_SO[rows,cols-1])  // WW
      then PA_Out[rows,cols] := PA_SO[rows,cols]
      //
      else
      // 45 degree quadrant (NW <-> SE)
      If  ((dir > 1) or (dir <= 3))
          and (PA_SO[rows,cols] > PA_SO[rows-1,cols-1]) // NW
          and (PA_SO[rows,cols] > PA_SO[rows+1,cols+1]) // SE
      then PA_Out[rows,cols] := PA_SO[rows,cols]
      //
      else
      // 90 degree quadrant (NN <-> SS)
      If  ((dir > 3) or (dir <= 5))
          and (PA_SO[rows,cols] > PA_SO[rows-1,cols]) // NN
          and (PA_SO[rows,cols] > PA_SO[rows+1,cols]) // SS
      then PA_Out[rows,cols] := PA_SO[rows,cols]
      //
      else
      // 135 degree quadrant (NE <-> SW)
      If  ((dir > 5) or (dir <= 7))
          and (PA_SO[rows,cols] > PA_SO[rows-1,cols+1]) // NE
          and (PA_SO[rows,cols] > PA_SO[rows+1,cols-1]) // SW
      then PA_Out[rows,cols] := PA_SO[rows,cols]
      //
      else
      // If no maximum -> Suppress Value
          PA_Out[rows,cols] := 0;
   end;
end;

Also ein Copy+Paste Fehler ist schonmal, dass es

If ((dir > 1) and (dir <= 3))
If ((dir > 3) and (dir <= 5))
((dir > 5) and (dir <= 7))

heissen muss. Da es alles verschlimmert stimmt wohl auch irgendwas mit den Richtungen nicht.

[Gutelo]

Medium, bist du dir denn sicher, dass du dieses Problem nicht auch im code hast?

Bei grossen Bildern faellt es nicht besonders auf, vorallem wenn die meisten Kanten verdreht sind gegenueber der horizontalen oder vertikalen Richtung. Probier mal das Testbild im Anhand (Cross.bmp) mit deinem Code aus.

Ich habe im Internet bei einigen Implementationen einen Kommentar gefunden ala "Problem mit vertikalen und horizontalen Kanten korrigiert"

Zitat:

"Du beachtest aber, dass du senkrecht zu den tatsächlichen Gradientenrichtungen vorgehen musst? "

Das verstehe ich nicht. Die Gradientenrichtung steht schon senkrecht auf der Kante und das ist genau die Richtung in die zusaetzliche Pixel entfernt werden muessen.

Gutelo

[Medium]

Das wirklich tragische ist gerade, dass ich mein Projekt nicht mehr finde. Ist ja auch nur meine Bachelorarbeit, die in >1 Jahr als Leidenschaftsprojekt erstellt wurde . Ich glaube fast, dass mir der liebe Ukash Virus Anfang des Jahres die letzte Sicherung davon geschrottet hat. Ich hoffe meine Eltern haben die CD noch, ich glaube denen hatte ich die gegeben. Wie ärgerlich

Edit: Das mit dem senkrecht vergiss übrigens gleich wieder, da hatte ich akuten Hirnknoten. Irgendwas war damit beim Tracing der Kanten in meiner Arbeit, das habe ich wohl vermischt gestern.

[Gutelo]

Oh das ist nicht gut. Hast du in der Uni keine Kopie hinterlassen?

Ich vermute dass der Atan2 probleme macht. Das Richtungsbild sieht etwas komisch aus um die horizontale Kante.

[Gutelo]

Am Atan2 liegt es nicht. Das Problem ist dass man die Aenderungen bei der NMS am Original durchführen muss. Blöder Fehler. Kann man sich auch einfach überlegen: Angenommen es liegen bei einer horizontalen linie zwei maxima senkrecht übereinander. Beide Pixel würden unterdrückt da der Wert nicht grösser ist als die nord und süd pixel. Ändert man jedoch am Original so ist der eine bereits unterdrückt und der zweite wird behalten.

Hab auch noch einen anderen Fehler gefunden der dazu führte dass SobelX und SobelY vertauscht waren. Überarbeite alles und poste den code nochmal

Gutelo

Edit: Die Problematik ist doch etwas komplizierter. Es reicht auch nicht aus die NMS auf dem Originalbild auszufuehren, da dann andere Pixel stehen bleiben die eigentlich unterdrueckt werden muessen. Viele Implementationen im Internet aendern nicht am Original und haben das Problem dass horizontale oder vertikale Linien bei der NMS komplett unterdrueckt werden.

[Medium]

Ui, der fällt aber auch schon in die Kategorie "Muss man erstmal drauf kommen". Dann hat sich das Problem bei mir vermutlich nicht gezeigt, weil es bei Floats deutlich unwahrscheinlicher (wenn auch nicht unmöglich) ist genau gleiche Werte nebeneinander zu bekommen. (Ich habe nämlich auch in einen frischen Puffer gemalt und nicht im Original.) Dazu kommt noch, dass im Endprodukt zwei Mal gesobelt wird, weil ich die "Kanten der Kanten" haben wollte, mit einem kleinen Zwischenschritt (Potenzierung des 1. Gradienten), wodurch recht schmale Strukturen entstanden sind.

Freut mich, dass es jetzt läuft! Werde übers Wochenende sicherlich auch dazu kommen, mir das genauer anzuschauen!

[Gutelo]

Aaaaargs. Naetuerlich liegt es daran dass ich vorher runde. Ich Depp. Wahrscheinlich kann dieser Fall ohne Runden nicht auftreten. Falls doch muesste man zweimal durchlaufen:

1) Lese aus Original und Schreibe in Kopie. Loesche alle Pixel die einen kleineren Wert haben als mindestens einer von beiden Nachbarpixeln in Gradientenrichtung. -> Elimination aller Pixel die garantiert kein Maximum sind

2) Nehme Kopie und loesche dort alle Pixel die nicht groesser sind als ihre beiden Nachbarpixel in Gradientenrichtung. -> Eine breite Kante wird von einer Seite her ausgeduennt bis nur noch die letzte Pixelzeile uebrig bleibt.

Hoechstwahrscheinlich ist das aber nicht noetig wenn man vorher alles bei floats belaesst.

Danke Medium

Edit: Oh, anscheinend tritt das Problem auch gelegentlich auf wenn man mit floats arbeitet. Medium kannst du das mal checken? Einige horizontale Kanten verschwinden vollstaendig, andere ueberleben. Ich werde die oben beschriebene Methode implementieren die zweimal das Sobelbild durchgeht um diesen Effekt zu korrigieren bzw zu vermeiden.

[Medium]

Ich muss gestehen, dass ich das bei mir noch nicht beobachtet habe, kann es aber mangels Code auch nicht prüfen. Meine FH hat leider immer nur zu meinen Arbeitszeiten geöffnet und ist etwas weiter weg . Ich muss noch mal alle USB Sticks fein säuberlich durchgehen.
Da ich aber nach einem Sobel bei mir nicht aufhöre, sondern noch etliche Dinge daran anschließen bis zur NMS, müsste ich auch noch ein wenig umbauen. Mir fällt allerdings ein: Ich glaube, dass ich am Ende tatsächlich die Werte im Original auch auf Null gesetzt habe bei der NMS. Oder es war erst beim Tracing. Da bin ich gerade unsicher, ist aber ja nun auch 4-5 Jahre her =). Das war aber, soweit ich mich erinnere, nicht wegen Problemen mit Senk- und Waagerechten. Was genau weiss ich aber leider auch nicht mehr.
Ich schiebe zudem auch noch einen Schritt nach, der eine 8-Nachbarschaft mit exakt 3 Punkten pro 3x3 Fenster herstellt. Dabei könnten eventuell verbleibende Doppelkanten, die blieben wenn man nicht mit ">" sondern ">=" arbeitete, auch noch erodiert werden. Ich hab da so lange so viel verschiedenes ausprobiert... ich muss es wirklich sehen um sinnvoll antworten zu können fürchte ich