Canny edge algorithmus und Sobel Matrix

[Gutelo]

Soderle, hab es jetzt mal umgeschrieben. Funktioniert soweit so gut -> Siehe angehaengte Bilder.
Als naechstes nehme ich NMS, Hysteresis und Hough in Angriff.


Falls jemand etwas Aehnliches machen moechte, hier mein Code bis hierhin. An einigen Stellen sicher noch etwas suboptimal und verbesserungsfaehig (z.B. dass das gesammte Array extra Durchlaufen wird um die minimalen und maximalen Werte zu bestimmen.)

Delphi-Quellcode:

unit Canny;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, Graphics,  LCLIntf, Dialogs, Math;

type // type to store a filter
     TFilter = Array of Array of Integer;
     // types for fast access to TBitmap image pixels
     TRGB = Array[1..3] of Byte;
     PixArray = Array[1..MaxInt div SizeOf(TRGB)-1] of TRGB;
     PPixArray = ^PixArray;
     PixArray2D = Array of PPixArray;
     // type to store the pixels of grayscale TBitmaps in an Array
     // and to perform filter operations on the array values
     TPixelArray = Array of Array of integer;


// Export
Procedure ConvertToGrayScale(ImgIn : TBitmap; var ImgOut : TBitmap);
Procedure CalcSobel(ImgIn : TBitmap; var ImgOut : TBitmap);

implementation

// ############################################################################
// Convert Color Image to Grayscale Image
// ############################################################################

Procedure ConvertToGrayScale(ImgIn : TBitmap; var ImgOut : TBitmap);
//
var ImgIn2D : PixArray2D;     // Access to ImgIn Pixels
    ImgOut2D : PixArray2D;    // Access to ImgOut Pixels
    rows,cols : Integer;      // rows and cols of an image
    GrayShade : Byte;         // Gray value
//
begin
   // Build 2D Arrays via 'scanline' to speed up pixel operations
   // access pixels: Img[a]^[b][c] , a=line, b=col, c: 3=R,2=G,or 1=B
   // Input Image:
   SetLength(ImgIn2D,ImgIn.Height);
   For rows := 0 to ImgIn.Height-1 do ImgIn2D[rows] := ImgIn.ScanLine[rows];
   // Output Image:
   SetLength(ImgOut2D,ImgOut.Height);
   For rows := 0 to ImgOut.Height-1 do ImgOut2D[rows] := ImgOut.ScanLine[rows];
   // Convert to grayscale:
   for rows := 0 to ImgIn.Height-1 do
   for cols := 0 to ImgIn.Width-1 do
    begin
      GrayShade := Round(  0.3 * ImgIn2D[rows]^[cols][3]
                         + 0.6 * ImgIn2D[rows]^[cols][2]
                         + 0.1 * ImgIn2D[rows]^[cols][1]);
      ImgOut2D[rows]^[cols][1] := GrayShade; // B-value
      ImgOut2D[rows]^[cols][2] := GrayShade; // G-value
      ImgOut2D[rows]^[cols][3] := GrayShade; // R-value
    end;
end;

// ############################################################################
// Make Gauss Filter Matrix
// ############################################################################

Procedure MakeGaussFilter(var Filter : TFilter);
//
var i : Integer;
//
begin
   // Set dimensions of filter array
   SetLength(Filter,5);
   for i := 0 to High(Filter) do SetLength(Filter[i],5);
   // Define Gauss filter matrix
   //   2  4  5  4 2
   //   4  9 12  9 4
   //   5 12 15 12 5
   //   4  9 12  9 4
   //   2  4  5  4 2
   // first Line
   Filter[0,0] := 2; Filter[0,1] := 4; Filter[0,2] := 5;
   Filter[0,3] := 4; Filter[0,4] := 2;
   // second Line
   Filter[1,0] := 4; Filter[1,1] := 9; Filter[1,2] := 12;
   Filter[1,3] := 9; Filter[1,4] := 4;
   // third Line
   Filter[2,0] := 5;  Filter[2,1] := 12; Filter[2,2] := 15;
   Filter[2,3] := 12; Filter[2,4] := 5;
   // fourth Line
   Filter[3,0] := 4; Filter[3,1] := 9; Filter[3,2] := 12;
   Filter[3,3] := 9; Filter[3,4] := 4;
   // fifth Line
   Filter[4,0] := 2; Filter[4,1] := 4; Filter[4,2] := 5;
   Filter[4,3] := 4; Filter[4,4] := 2;
end;

// ############################################################################
// Make Sobel-X Filter Matrix
// ############################################################################

Procedure MakeSobelXFilter(var Filter : TFilter);
//
var i : integer;
//
begin
   // Set dimensions of filter array
   SetLength(Filter,3);
   for i := 0 to High(Filter) do SetLength(Filter[i],3);
   // Define Sobel-X filter matrix
   //   -1  0  1
   //   -2  0  2
   //   -1  0  1
   // first Line
   Filter[0,0] := -1; Filter[0,1] := 0; Filter[0,2] := 1;
   // second Line
   Filter[1,0] := -2; Filter[1,1] := 0; Filter[1,2] := 2;
   // third Line
   Filter[2,0] := -1; Filter[2,1] := 0; Filter[2,2] := 1;
end;

// ############################################################################
// Make Sobel-Y Filter Matrix
// ############################################################################

Procedure MakeSobelYFilter(var Filter : TFilter);
//
var i : integer;
//
begin
   // Set dimensions of filter array
   SetLength(Filter,3);
   for i := 0 to High(Filter) do SetLength(Filter[i],3);
   // Define Sobel-Y filter matrix
   //    1   2   1
   //    0   0   0
   //   -1  -2  -1
   // first Line
   Filter[0,0] :=  1; Filter[0,1] :=  2; Filter[0,2] :=  1;
   // second Line
   Filter[1,0] :=  0; Filter[1,1] :=  0; Filter[1,2] :=  0;
   // third Line
   Filter[2,0] := -1; Filter[2,1] := -2; Filter[2,2] := -1;
end;

// ############################################################################
// Convert "Image -> Pixel Array" and "Pixel Array -> Image"
// ############################################################################

Procedure ImgToPixArray(ImgIn : TBitmap; var PixArr : TPixelArray);
//
var H,W : Integer;
    ImgIn2D : PixArray2D;
    rows, cols : Integer;
//
begin
  // Store height and width of input image
  H := ImgIn.Height;
  W := ImgIn.Width;
  // Fast access to input image:
  SetLength(ImgIn2D,H);
  For rows := 0 to H-1 do ImgIn2D[rows] := ImgIn.ScanLine[rows];
  // Set dimensions of pixel array
  SetLength(PixArr,H);
  For rows := 0 to H-1 do SetLength(PixArr[rows],W);
  // Copy pixel values of input image to pixel array
  For rows := 0 to H-1 do
  For cols := 0 to W-1 do
  begin
    PixArr[rows,cols] := ImgIn2D[rows]^[cols][1];
  end;
end;

Procedure PixArrayToImg(PixArr : TPixelArray; var ImgOut : TBitmap);
//
var H,W : Integer;
    ImgOut2D : PixArray2D;
    rows, cols : Integer;
    MinVal, MaxVal : integer;
    Pixel : Integer;
//
begin
   // Store height and width of input image
   H := Length(PixArr);
   W := Length(PixArr[0]);
   // Initialize output image
   ImgOut := TBitmap.Create;
   ImgOut.Width := W;
   ImgOut.Height := H;
   // Fast access to output Image:
   SetLength(ImgOut2D,H);
   For rows := 0 to H-1 do ImgOut2D[rows] := ImgOut.ScanLine[rows];
   // Determine minimum and maximum values in pixel array
   MinVal := PixArr[0,0];
   MaxVal := PixArr[0,0];
   For rows := 0 to H-1 do
   For cols := 0 to W-1 do
   begin
      if PixArr[rows,cols] < MinVal then MinVal := PixArr[rows,cols];
      if PixArr[rows,cols] > MaxVal then MaxVal := PixArr[rows,cols];
   end;
   // Rescale value range to 0..255 and copy values to output image
   For rows := 0 to H-1 do
   For cols := 0 to W-1 do
   begin
     // only scale if necessary
     if (MinVal < 0) or (MaxVal > 255)
     then
         Pixel := Round(255*((PixArr[rows,cols] - MinVal)/ (MaxVal-MinVal)))
     else
         Pixel := PixArr[rows,cols];
     // Copy values to output image
     ImgOut2D[rows]^[cols][1] := Pixel;
     ImgOut2D[rows]^[cols][2] := Pixel;
     ImgOut2D[rows]^[cols][3] := Pixel;
   end;
end;

// ############################################################################
// Apply Filter on Pixel Array
// ############################################################################

Procedure ApplyFilterOnPixArray(PA_In : TPixelArray; var PA_Out : TPixelArray; Filter : TFilter; DoWeight : Boolean);
//
var H,W : Integer;        // Height and width of ImgIn
    rows,cols : Integer;  // rows and cols in the image
    weight : Integer;     // Weight for Filter Matrix
    FilterBT : Integer;   // Border Thickness of Filter around central element
    x, y : Integer;       // Variables for Convolution
    PixelSum : Integer;   // Convolution Value
    Pixel : Integer;      // Final Pixel Value
//
begin
   // Border thickness of filter around central matrix element:
   // Examples: 3x3 Matrix -> BT=1 , 5x5 Matrix -> BT=3
   FilterBT := Round(0.5 * (Length(Filter)-1));
   // Store height and width of input pixel array (PA_In):
   H := Length(PA_In);
   W := Length(PA_In[0]);
   // Set dimensions of output pixel array (PA_Out), "removes Filter Border":
   SetLength(PA_Out, H-(2*FilterBT));
   For rows := 0 to High(PA_Out) do SetLength(PA_Out[rows],W-(2*FilterBT));
   // Determine filter matrix weight:
   weight := 0;
   For y := 0 to High(Filter[0]) do
   For x := 0 to High(Filter) do
   begin
      weight := weight + Abs(Filter[x,y]);
   end;
   // Calculate filtered Image, i.e. perform convolution of Filter and PA_In -> PA_Out
   For rows := FilterBT to High(PA_In)-FilterBT do
   For cols := FilterBT to High(PA_In[0])-FilterBT do
   begin
      // Perform convolution
      PixelSum := 0;
      For y := -FilterBT to FilterBT do
      For x := -FilterBT to FilterBT do
      begin
        PixelSum := PixelSum + Filter[x+FilterBT,y+FilterBT]* PA_In[rows+y,cols+x];
      end;
      // Apply weight when required
      if DoWeight then Pixel := Round(PixelSum/weight)
                  else Pixel := PixelSum;
      // write output pixel array
      PA_Out[rows-FilterBT,cols-FilterBT] := Pixel;
   end;
end;

// ############################################################################
// Make final Sobel pixel array based on Sobel-X and Sobel-Y
// ############################################################################

Procedure MakeSobel(PA_Sx, PA_Sy : TPixelArray; var PA_Out : TPixelArray);
//
var rows, cols : Integer;
    Sx, Sy : Integer;
//
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
      Sx := PA_Sx[rows,cols];
      Sy := PA_Sy[rows,cols];
      // write output pixel array
      PA_Out[rows,cols] := Round(sqrt(Sx*Sx + Sy*Sy));
   end;
end;

// ############################################################################
// Procedure to perform complete Sobel calculation
// ############################################################################

Procedure CalcSobel(ImgIn : TBitmap; var ImgOut : TBitmap);
var ImgGray : TBitmap;
    PA_Gray, PA_Gauss, PA_SobelX, PA_SobelY, PA_Sobel : TPixelArray;
    GaussFilter, SobelX, SobelY : TFilter;
begin
  ImgGray := TBitmap.Create;
  ImgGray.Width := ImgIn.Width;
  ImgGray.Height := ImgIn.Height;
  // Convert color input image (ImgIn) to grayscale image (ImgGray)
  // and convert ImgGray to pixel array format (PA_Gray)
  ConvertToGrayScale(ImgIn,ImgGray);
  ImgToPixArray(ImgGray, PA_Gray);
  // Apply Gauss smoothening filter to PA_Gray -> PA_Gauss
  MakeGaussFilter(GaussFilter);
  ApplyFilterOnPixArray(PA_Gray, PA_Gauss, GaussFilter, true);
  // Apply SobelX filter to PA_Gauss -> PA_SobelX
  MakeSobelXFilter(SobelX);
  ApplyFilterOnPixArray(PA_Gauss, PA_SobelX, SobelX, false);
  // Apply SobelY filter to PA_Gauss -> PA_SobelY
  MakeSobelYFilter(SobelY);
  ApplyFilterOnPixArray(PA_Gauss, PA_SobelY, SobelY, false);
  // Combine PA_SobelX and PA_SobelY -> PA_Sobel
  MakeSobel(PA_SobelX, PA_SobelY, PA_Sobel);
  // Convert PA_Sobel to output image (ImgOut)
  PixArrayToImg(PA_Sobel, ImgOut);
end;

end.

Verwendung aus Hauptprogramm:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var ImgIn, ImgOut : TBitmap;
begin
  ImgIn := TBitmap.Create;
  ImgOut := TBitmap.Create;
  ImgIn.LoadFromFile('Test.bmp');
  CalcSobel(ImgIn, ImgOut);
  Image3.Picture.Bitmap := ImgOut;
end;

Gutelo

[Medium]

Das sieht doch schon sehr richtig aus! Nett.

Darf man fragen, was du mit den Kanten nachher vor hast? So von Nachtschwärmer zu Nachtschwärmer

[Gutelo]

Jepp

Ich schreib ein Programm welches folgendes machen soll:

1.) Mittels Kamera ein Dokument auf einem Tisch aufnehmen (Webcam oder Handy)
2.) Perspektivische Verzerrung rausrechnen, so dass quasi eine Aufnahme "von oben" erhalten wird
3.) Einlesen von Zahlen mittels OCR

1. und 2. sind soweit fertig.

Den Canny+Hough brauche ich um die Eckpunkte des Dokuments im verzerrten Bild automatisch zu finden.

Fuer die OCR werde ich wohl ein einfaches Pixel-matching verwenden: Einmal perfekt mit Flachbettscanner einscannen und fuer jede Zahl von 0 bis 9 eine Referenz anfertigen. Dann die gescannten Zahlen ueber die Referenzen durchschieben und den maximalen Match bestimmen. Das sollte eigentlich ganz gut funktionieren wenn man Hoehe/Breite (Pixelaufloesung) einigermassen waehlt. Vielleicht kommen auch Neuronale Netze in Frage, obwohl mich die Treffsicherheit der simplen OCR Implementationen mittels NN die ich im Internet gefunden habe nicht wirklich ueberzeugt haben.

Eigentlich kam mir bei der ganzen Canny Geschichte folgendes in den Sinn bezueglich der OCR: Man koennte doch ueber jede gescannte Zahl den Canny laufen lassen und anschliessend die Gradientenrichtungen (Statistik ueber Gradienten in 0,45,90,.. Grad Richtung) der Kannten benutzen um die Zahl zu bestimmen. Was haelst du von dieser Idee? Koennte man auch mit dem Pixel-matching kombinieren.

Gutelo

Warum das in der urpruenglichen Version nicht funktioniert hat ist mir aber immer noch raetselhaft, da ich dort im Grunde ja das gleiche mache bis zu den Sx und Sy. Ich glaube aber dass es eventuell an der Normierung liegt. Wenn ich bei der aktuellen Version bereits die Pixel Arrays der Sx und Sy normiere, dann ist der Effekt nicht ganz so stark ausgepraegt als wenn ich erst am Ende nach dem Sobel normiere. Ein anderes Problem der alten Version ist der nicht behandelte Rand. Dieser verfaelscht die Skala. In der neuen Version werden die Raender abgeschnitten nach der Filteranwendung.

[Medium]

Das klingt verdammt spannend! Und beeindruckend oben drauf.
Bei OCR bin ich nicht so sehr im Thema, aber die Idee das anhand der "Winkellisten" zu vergleichen finde ich zumindest schon mal höchst kreativ - und gar nicht mal so abwegig. Da könnte es dann spannend werden einen Vergleichsmechanismus zu finden, der 2 Listen potenziell unterschiedlicher Länge ein geeignetes Ähnlichkeitsmaß zuordnet. Das wirklich interessante bei dem Ansatz ist vor allem, dass man im Prinzip ohne ROI auskommen kann. Einfach alle Gradientenlisten durchgehen und gut. Fies wird es da allerdings wohl bei Zahlen, die in mehere Listen zerfallen können. Also die beiden, die gekreuzte Linien haben können: 4 und 8. Da müsste man sich was überlegen.

Zum Sobel bzw. dessen Nicht-Funktion vorher: Da ich nicht so ganz durch deine Normierungsmethode steige gerade, weiss ich auch nicht genau was da schief lief. Grundsätzlich bin ich aber wegen solchen potenziellen Problemen eher dazu geneigt, die Container den Daten anzupassen als umgekehrt

[Gutelo]

Oh ich dachte eigentlich nur an ein Haufigkeitsdiagram, also Häufigkeit über Richtung. Aber deine "Liste" ist noch viel besser. Man nimmt einfach die äusserste Kante die zusammenhängend die Zahl umschliesst und läuft die Kannte Pixel fûr Pixel ab und macht ein Array mit den Gradientrichtungen. Die Sprûnge in den Richtungen und die Länge der Liste sind charakteristisch für die Zahl. Probleme mit 4 und 8 gibt es dann auch nicht. Gute Idee.

Wofür steht ROI?

Edit: ah. Region of interest. Das Problem auch die Zahlen zu separieren liegt nicht an der Kreuzung sondern dass 4 und 8 mehrere geschlossene Kanten haben. Aber die Zahlen zu separieren ist nicht so wild, das hab ich schon fertig.

[Medium]

Ha, in dieser Form hatte ich an die Listen jetzt auch nicht gedacht Aber das klingt gut, im Grunde eine Hüllkurvenauswertung. Könnte nur bei 6, 8 und 9 je nach Font knifflig werden, aber ausprobierenswert. Vor allem wenn du die Separierung schon hast - das ist der wichtigste Schritt überhaupt. Alles danach lässt sich dann ja recht einfach ausprobieren und verfeinern.

[Gutelo]

Mit 8 und 6/9 sollte es kein Problrm geben. 6 und 9 haben etwa gleiche Aenderungen. Hier muss man dann einen festen Startpunkt wählen, z.B. immer beim nördlichsten Punkt anfangen.

Ich muss erst noch die NMS, Hysteresis und Hough fertig machen dann kümmer ich mich um die OCR idee. Halte dich auf dem Laufenden

[Gutelo]

Hallo,

Non-Maximum Suppression (NMS) und Hysteresis arbeiten jetzt auch. Ich haenge ein kleines Demo-Projekt fuer Lazarus an dieses Post. Laeuft alles schnell genug, kann aber auch noch reichlich optimiert werden. Soll nur als ein Grundgeruest dienen fuer Leute die Aehnliches vor haben. Ich habe den Code reichlich kommentiert. Das Binary ist leider elendig gross geworden (28mb). Lazarus scheint noch mehr aufzublaehen als Delphi. Ferner nicht wundern wenn nach dem Verlassen des kompilierten Programms der Debugger meckert. Ein leidiges Lazarus Problem bei Verwendung von OpenDialog. Am besten einmal kompilieren und dann das Program ausserhalb der IDE aufrufen.

WICHTIG: >>> geht NUR mit *.bmp bitmaps, keine jpg, keine gif, ... <<<

Naechste Schritte:

1) Ich muss alle kurzen Kanten entfernen und nur die Langen ueberleben lassen, d.h. Kannten reduzieren.
2) Ich brauche Hough um Geraden und Ecken zu identifizieren.

Gutelo

[Gutelo]

Mist gerade bei Hough gemerkt, dass etwas nicht 100% stimmt.

Erstmal muss in Canny.pas der Typ PixArray mit dem Array bei 0 beginnen und nicht bei 1. Bis zum Sobel ist alles okay.

Die NMS Berechnung und/oder Berechnung der Kantenrichtungen sind fehlerhaft. Bei exakt horizontalen Kanten verschwinden die Kanten fast komplett aus dem Bild bei der NMS Berechnung. Woran kann das liegen? An definition von Atan2 ?

Gleiches Problem bei exakt vertikalen Kanten.

Gutelo

[Medium]

Ohne den Code zu deiner NMS (inkl. der Richtungsbestimmungen, falls die ausgelagert sein sollte) zu sehen schwer zu sagen. Ich hatte da eigentlich kein Problem. Du beachtest aber, dass du senkrecht zu den tatsächlichen Gradientenrichtungen vorgehen musst? Das würde mir so ad hoc als schnell gemachter Fehler einfallen.