Sobel Normalisierungsschritt

[Atlunch]

Hallo zusammen,

gerade bin ich dabei einen Sobel selber zu programmieren!
Leider bin ich bis jetzt nicht wirklich schlau aus den codes geworden die hier im Forum sind und hab mich deshalb an den Grundformeln orientiert.

Generell geht es auch nur noch um den letzten Schritt. Den Normalisierungsschritt.

Nachdem ich Gx und Gy bestimmt hab muss ich ja den gesamten Gradienten G mit =sqrt(Gx^2+Gy^2) berechnen.

Diese Formel wird dann für jeden Pixel ja einzelnd durchlaufen. Was mache ich nun wenn der G Wert nicht im Bereich 0 - 255 liegt! Im Internet wird dabei vom Normalisierungsschritt gesprochen.

Kann mir einer erklären wie ich von einem bestimmten G Wert in den Wertebereich 0 - 255 komme?

Viele Grüße
Atlunch

[Michael II]

Hast du

http://www.delphipraxis.net/127020-sobel-operator.html

gesehen?


Zum "Normalisieren". Du kannst dir überlegen, welche maximalen Werte Gx und Gy durch die Sobel Operatoren erreichen können. Dann kennst du das mögliche Maximum von G und kannst jede Berechnung linear skalieren. Beispiel: Wenn max(G)=9*255, dann müsstest du jeden berechneten Wert /9 teilen.

[Wenn du dein "Sobel-Resultatbild" nicht mit anderen vergleichen musst, für dein Bild die Werte von G zwischen m und M liegen, und du die Kanten u.U. "überzeichnet" (bei geringen Ableitungen im Quellbild) darstellen willst, dann kannst du natürlich auch so normalisieren: für G=M norm(G)=255, norm(G)= 256*(G-m) div (M-m) sonst]

[Michael II]

Hallo Atlunch,

da der von mir verlinkte Code auf DP bei mir nicht funktioniert und zudem etwas langsam ist, habe ich hier rasch einen "Sobelcode" geschrieben. [Man könnte den Code - auch ohne asm - noch optimieren. Siehe Link "Sperarierbarkeit" https://de.wikipedia.org/wiki/Sobel-Operator Für ein 1150x1150 Bild werden auf meiner langsamen Kiste nur 65ms benötigt.]

Dieses Beispiel funktioniert für Graustufenbilder. Den Vorprozess für "Farbbilder als Quelle", hast du ja sicher bereits.

Im Beispiel unten nutze ich für jedes Bild den ganzen Graustufenraum [0..255], indem ich mir den maximalen Gradient merke und diesem 255 zuweise (für den minimalen Wert nehme ich 0 an, da es praktisch in jedem Bild einen Punkt mit 8 Umgebungspixel mit Ableitung 0 gibt). Falls dein Grafiksystem mehr Grauwerte hergibt, dann kannst du den Code (siehe //normieren) leicht anpassen.

Wenn du mehrere "Sobelbilder" miteinander vergleichen möchtest, dann willst du pro Bild eventuell nicht den gesamten Graustufenraum ausnutzen [damit du Unterschiede erkennen kannst]. In diesem Fall müsstest du berechnen wie gross g^2 = gx^2+gy^2 werden kann. Ich glaube du kannst dir überlegen, dass zum Beispiel folgendes Umgebungspixel-Muster maximales g liefert:

Delphi-Quellcode:

Für gx:
S - W
S - W
S - W

Für gy:
S S S
- - -
W W W

Für den Punkt unten links könnte a=W oder a=S oder ein Zwischenwert gut sein, für den Punkt oben rechts könnte b=S oder b=W oder ein Zwischenwert optimal sein.

Du hast also eine Funktion g(a,b), welche du maximieren musst. Zwei Lösungen: 1. a=W und b=S und 2. a=S und b=W

Wenn ich richtig gerechnet habe ist max(g^2) = 1300500 oder max(g) = 1140.4.
Du müsstest als g normieren mittels norm(g) = g*256 div 1141, um Werte zwischen 0 und 255 zu erhalten.

Falls ich mich verrechnet habe, dann möge man diese Meldung für immer löschen :-).


Hier der Sobelcode mit Ausnutzung des ganzen Graustufenbereichs
(Wie erwähnt könntest du auch gnorm := (grauwerte[x,y] shl 8) div 1141 verwenden.)

Delphi-Quellcode:

type
  TRGB32 = packed record
    B, G, R, A: Byte;
  end;
  TRGB32Array = packed array[0..0] of TRGB32;
  PRGB32Array = ^TRGB32Array;

procedure SobelSL_GRAU( graubit , sobelbit : TBitMap );
var gnorm, ming, maxg, gw, g, gx, gy, x, y : integer;
    Line_m1, line, line_p1 : PRGB32Array;
    grauwerte : array of array of integer;

begin
  ming := maxint;
  maxg := 0;

  setlength( grauwerte, graubit.Width, graubit.Height );

  for y := 1 to graubit.height-2 do
  begin
      line_m1 := graubit.ScanLine[y-1];
      line := graubit.ScanLine[y];
      line_p1 := graubit.ScanLine[y+1];

      for x := 1 to graubit.Width-2 do
      begin
          gx := -line_m1[x-1].R - 2*line[x-1].R - line_p1[x-1].R
                +line_m1[x+1].R + 2*line[x+1].R + line_p1[x+1].R;

          gy := -line_m1[x-1].R - 2*line_m1[x].R - line_m1[x+1].R
                +line_p1[x-1].R + 2*line_p1[x].R + line_p1[x+1].R;

          g := round(sqrt( gx*gx + gy*gy ));

          if g > maxg then maxg := g;
          if g < ming then ming := g;
          grauwerte[x,y] := g;
      end;
  end;

  // normieren:
  for y := 1 to graubit.height-2 do
  begin
      line := sobelbit.ScanLine[y];
      for x := 1 to graubit.Width-2 do
      begin
        gnorm := (grauwerte[x,y] shl 8) div maxg;
        if gnorm=256 then gnorm := 255;
        line[x].R := gnorm;
        line[x].G := gnorm;
        line[x].B := gnorm;
      end;
  end;
end;


procedure SobelFromFile( const fileQuelle, fileZiel : string );
var quelle, ziel : TBitMap;
begin
      quelle := TBitMap.Create;
      ziel := TBitMap.Create;
    try
      quelle.LoadFromFile( fileQuelle );
      quelle.PixelFormat := pf32bit;

      ziel.PixelFormat := pf32bit;
      ziel.SetSize( quelle.Width, quelle.Height );

      SobelSL_GRAU( quelle, ziel );
      ziel.SaveToFile( fileZiel );
    finally
      quelle.Free;
      ziel.Free;
    end;
end;

[Medium]

In der ersten Antwort hier wird ein Maximalwert von 1530 nach Sobeloperation auf einem 8-Bit Graustufenbild genannt. (Und auch auf das Problem hingewiesen, dass diesen zu ermitteln gar nicht so einfach ist, da Sobel nicht gleichzeitig in X und Y Richtung maximale Ausprägung annehmen kann, und man daher auch nicht einfach 2xMax(Sobel) nehmen kann.)

Was ich allerdings auch noch zu bedenken geben möchte ist, dass man gerade bei Fotos eher selten Werte in ca. den oberen 2/3 bekommt. Praktisch nur bei S/W-Zeichnungen mit 100% harten Kanten. Daher kann es sein, dass man nach Skalierung mit 1530 ein relativ dunkles Ergebnis bekommt, vor allem aber auch viel Detail kaputt macht.
Je nach dem was du nachher mit dem Ergebnis vor hast, könnte es sich daher auch lohnen non-linear zu skalieren. Ob du das machen kannst hängt aber komplett von deinem Einsatzzweck ab.

[Michael II]

Hallo Medium

Die Angabe im von dir zitierten Artikel ist falsch.


Mein Programm und die Angaben des möglichen Maximums von g beziehen sich auf den "üblichen" "3x3 Sobel".
Der Gradient g ist ein Vektor im R^2; g hat also eine x Komponente gx und eine y Komponente gy.

Die Länge von g (das Mass für die Helligkeitsänderung) ist nicht wie im von dir verlinkten Artikel behauptet abs(gx)+abs(gy) [das Maximum dieser Funktion ist effektiv 255-a+510+b+255-b+510+a=1530; aber das nützt uns nix, da der Ansatz falsch ist].

Die Länge von g ist sqrt(gx*gx+gy+gy). Du musst also wie weiter oben beschrieben wird (gx*gx+gy+gy)(a,b) maximieren, d.h. ableiten nach a und b und Nullstellen suchen. Lösungen nach kurzer Rechnung
(a,b)=(0,255) und (a,b)=(255,0), Maximum berechnen durch Einsetzen der Lösungen in (gx*gx+gy*gy) ergibt ein Maximum von max(g^2)=1300500 oder max(g) = 1140.4.

[BrightAngel]

Hallo zusammen :)

Tut mir leid, wenn ich jetzt auch noch Unruhe stifte und mitmischen möchte :oops:

Zitat:

Zitat von Atlunch (Beitrag 1370573)

Kann mir einer erklären wie ich von einem bestimmten G Wert in den Wertebereich 0 - 255 komme?

Kurz: Da beide Wertebereiche als Untergrenze 0 haben, musst du nur durch die Obergrenze des bestimmten G-Wertebereich teilen und mit der Obergrenze gewünschten Wertebereichs (255) multiplizieren.

Falls das Folgende für mehr Verwirrung sorgt, als dass es hilft, dann bitte ich darum diesen Post einfach zu ignorieren :? Ich fange nochmal an jeden einzelnen Schritt zu beleuchten, um ganz explizit die Wertebereiche zu nennen. Danach gehe ich auf die Normierung ein. Ich nehme vereinfachend an, dass Quell- und Zielvariablen immer 8 Bit Auflösung halten und die tatsächlichen Wertebereiche dazwischen, also im Intervall [0, 255] variieren. Auch wenn ich nur auf den 3x3 Bildkernel eingehe, so lässt sich das Prinzip auf andere (größere) Kernel anwenden.

Stichwort Bildkernel: Bei vielen Bildkerneln werden die Summe der Einträge (sprich die Faktoren mit denen die einzelnen Pixel multipliziert werden) im Bildkernel normalerweise so skaliert, dass die Zielintervalle wieder voll abgedeckt werden. (Beispiel: 3x3 Einheitsmatrix würde durch 3 geteilt, da das Maximum Spur(I) = 3*255 auf das Zielinterval [0, 255] gebracht werden sollen).
Beim (separierten) Sobelfilter fällt auf, dass die Kernel (hier nur der X-Achsenkernel)

Code:

[[ +1,  0, -1],
 [ +2, 0, -2],
 [ +1, 0, -1]]

so gebaut sind, dass sich die "Seiten" gegenseitig aufheben, wenn beide Spalten identisch sind (also die "übliche" Skalierung auf Eins nicht erfolgt!). Das ist bewusst so gewählt (weil das eben grade den Gradienten im Diskreten darstellt). Das impliziert nun aber Folgendes für den 3x3 Kernel in Anwendung:

Delphi-Quellcode:

Max(SobelX(P)) = 4*255 = 1020

&

Delphi-Quellcode:

Min(SobelX(P)) = -4 * 255 = -1020

, wobei SobelX(P) die Anwendung des Sobelfilters um die Pixelumgebung des Punktes P bedeutet (SobelY analog).

Würden wir auf den entstandenen Wertebereich [-1020, 1020] jetzt in ein 8 Bit Graustufenbild schreiben wollen (hypothetisch), müssten wir also auf 0 verschieben und skalieren:

Delphi-Quellcode:

Pixel[P] = round((SobelX(P) + 1020) / 2040 * 255)

. Jetzt haben wir den Wertebereich auf das Intervall [0, 255] gebracht.

Da wir die Ergebnisse von X und Y Achse aber richtungsunabhängig kombinieren und dabei quadrieren, entfallen die negativen Intervallabschnitte und es bildet sich das Zielintervall wie folgt:

Delphi-Quellcode:

Sobel(P) = sqrt(SobelX(P) * SobelX(P) + SobelY(P) * SobelY(P))

, wobei das Maximum wieder

Delphi-Quellcode:

Max(Sobel(P)) = sqrt(1020^2 + 1020^2) = sqrt(2080800) ≈ 1442.497833620557

ergibt (Genauigkeit wurde so gewählt, dass IEEE754 Double Präzision am Besten ausgereizt wird). Das Minimum ist trivialerweise immer 0. Wir befinden uns jetzt also im Interval [0, 144.497833620557].
Daraus folgt die allgemeine Skalierung für Pixel P:

Delphi-Quellcode:

Pixel[P] = round(Sobel(P) / 1442.497833620557 * 255)

. Ich runde erst jetzt für maximale Genauigkeit. Somit ist das gewünschte Zielinterval [0, 255] erreicht.

[Edit]
Michael II: Bin jetzt auch bei dir angekommen. :oops: Hatte vergessen, dass das Bild ja den beiden Kerneln Abhängigkeiten "aufzwingt". Michael II hat also korrekt gerechnet. Meine Formel oben stimmt trotzdem von der Herleitung, allerdings kann man die Skalierung am Ende besser wählen:

Delphi-Quellcode:

Pixel[P] = round(Sobel(P) / 1140.4 * 255)

.
[/Edit]

Das war jetzt mal meine Herleitung zur normalen naiven Berechnung. Korrekturen gerne willkommen.
Jetzt kann man noch das völlig unabhängig betrachtbare Problem der Vorverarbeitung/heuristischen Betrachtung dazuziehen;

Zitat:

Zitat von Medium (Beitrag 1371085)

Ob du das machen kannst hängt aber komplett von deinem Einsatzzweck ab.

Wenn du weitere Schritte einfügst, die sich auf das ganze Bild beziehen, so wirst du auf jeden Fall einmal mehr durch das Bild durchgehen. Entweder einmal am Anfang, um zu Detektieren oder am Ende beim Schreiben. Ich neige bei zum Beispiel Skalierung auf Maxiumum/Minimum zu ersterem, weil ich mir die Schreibzugriffe auf den Hauptspeicher sparen kann und dann auch auf ein Array mit den Zwischenergebnissen verzichten kann: Anfangs einmal alle Pixel anschauen und Maximum und Minimum in lokaler Variable merken. Die jeweilige Skalierung kann man dann oben in die Formel integrieren (wenn dich das genauer interessiert, kann ich gerne weiterhelfen ;)). (alternativ würde man beim Lesen schonmal bis zum letzten Schritt berechnen und dann in ein Zwischenzielarray speichern; muss dann aber danach nochmal über alle Werte darüber. Mir fällt grade spontan kein Anwendungsfall ein, bei dem ich das mal präferiert hatte...)

Man kann das Bild auch anderweitig "vorverarbeiten": Es gibt zum Beispiel die Histogrammnormalisierung. Mir hat für meine Anwendungszwecke bisher immer die Maximum/Minimumbetrachtung ausgereicht. Vor allem weil nicht lineares Verzerren manchmal zusätzlich Information auslöscht (wie "stark" war die Kante), wenn sie nicht geschickt angewendet wird. :)

Gruß, Brighty :D


Disclaimer: Ich musste leider grade ohne meine Codebasis das aus dem Kopf heraus rekonstruieren. Ganz besonders möchte ich anmerken, dass ich mich zugunsten des Verständnisses dafür entschieden hatte Werte innerhalb der Berechnungen implizit von Flieskomma- und Ganzzahlen zu konvertieren. Obwohl ich die Zahlen nachgerechnet habe, kann es sein, dass ich irgendwo noch etwas vergessen/nicht ganz deutlich in diesem Text herausgearbeitet habe. :roll:

[Michael II]

Hallo Brighty

deine Berechnung ist nicht korrekt.

Du hast übersehen, was ich weiter oben gepostet habe: Gx^2 und Gy^2 können nicht beide gleichzeitig maximal sein.


Noch einmal:

Zitat:

In den folgenden beiden 3x3 Pixelbildern ist S=schwarz=0 und w=weiss=255.

gx wird (wie du korrekt schreibst) maximal, wenn es um Pixel P so aussieht:
S - W
S P W
S - W

gy wird maximal, wenn es um Pixel P so aussieht:
S S S
- P -
W W W

Wie du korrekt feststellst gilt max(gx) = 1020 und für max(gy)=1020. [bzw. min(gx)=-1020, min(gy)=-1020]

Wenn du die beiden 3x3 Pixelbilder oben betrachtest, dann siehst du, dass das Pixel unten links S sein muss für gx maximal und weiss sein muss für gy. Das kann nicht gleichzeitig der Fall sein.
Ebenso für das Pixel oben rechts: Für gx maximal müsste es weiss sein, für gy maximal aber schwarz. Auch das kann nicht gleichzeitig der Fall sein.

(Du nimmst aber in deiner Berechnung an, dass Pixel unten links gleichzeitig schwarz und weiss sein kann. Dito für das Pixel oben rechts: Es kann nicht schwarz und gleichzeitig auch weiss sein. )


=> Du musst also herausfinden für welche Wahl von a und b, der Gradient g^2(a,b) = gx^2(a,b) + gy^2(a,b) maximal wird. (siehe oben)

Zitat:

S S b
S P W
a W W

Wegen deinen Nachkommastellen. Wenn du letztendlich Resultate mit 3 Stellen ermittelst (du ermittelst ja Grauwerte von 0..255), reicht es, wenn deine Zahlen auf insgesamt 4-5 (Vor- und Nachkomma) Stellen genau sind.

[BrightAngel]

Zitat:

Zitat von Michael II (Beitrag 1371260)

deine Berechnung ist nicht korrekt.

korrekt! :oops:

Zitat:

Zitat von Michael II (Beitrag 1371260)

Du hast übersehen, was ich weiter oben gepostet habe: Gx^2 und Gy^2 können nicht beide gleichzeitig maximal sein.

Wahr. Mir war das kurz vor deinem Post auch aufgefallen. Kennst du das Gefühl was vergessen zu haben? Deswegen saß ich auch so lange in dem Thread :lol: Habe es dann noch gekennzeichnet und auf dich verwiesen :roll:

Zitat:

Zitat von Michael II (Beitrag 1371260)

[...]
=> Du musst also herausfinden für welche Wahl von a und b, der Gradient g^2(a,b) = gx^2(a,b) + gy^2(a,b) maximal wird. (siehe oben)

Zitat:

S S b
S P W
a W W

Genau und für a = 0 und b = 255 oder umgekehrt ist der Wert eben maximal (=1300500)

Zitat:

Zitat von Michael II (Beitrag 1371260)

Wegen deinen Nachkommastellen. Wenn du letztendlich Resultate mit 3 Stellen ermittelst (du ermittelst ja Grauwerte von 0..255), reicht es, wenn deine Zahlen auf insgesamt 4-5 (Vor- und Nachkomma) Stellen genau sind.

Das ist ein Tick von mir: Für den Rechner macht es keinen Unterschied und ich mag exakte Ergebnisse. Ich weiß nie, ob die Skalierung sich nicht doch mal ändert (weil man vielleicht gar nicht mehr auf 255 skaliert, sondern direkt z.B. in nem Integerarray damit zaubert)

Ich hatte mich vorhin eingemischt, weil ich eigentlich dich nur dazwischen noch durch Erklärungen stützen wollte, und dann kam ich auf ein anderes Ergebnis :oops::twisted:

Brighty

[Michael II]

Zitat:

Kennst du das Gefühl was vergessen zu haben? Deswegen saß ich auch so lange in dem Thread Habe es dann noch gekennzeichnet und auf dich verwiesen

Ja dieses Gefühl kenne ich nur allzu gut. Nach meiner Antwort auf deine, dachte ich (als ich draussen die Katze suchte, welche wieder einmal partout nicht reinkommen will, obschon ich für 72h weg müsste und ein Katzentüre fehlt), ich hätte Mist geantwortet und habe gleich noch einmal gerechnet.

Aber es stimmt. Kurz, was man tun muss:

G(a,b) = 2a^2 + 2b^2 - 4ab + 2*765^2 maximieren.

Nun sieht man entweder, dass G(a,b) = 2(a-b)^2 + 2*765^2 und somit (a-b)^2 maximal, wenn a=255, b=0 bzw. a=0, b=255 oder man rechnet:

G abgleitet nach a:
dG(a,b)/da = 4a-4b = 0
und nach b:
dG(a,b)/db = 4b-4a = 0

Also a=b. Nun muss man noch untersuchen, ob man ein Minimum oder ein Maximum getroffen hat. Es ist ein Minimum. Die maximalen Werte für G(a,b) müssen also am Rand von [0..255]x[0..255] liegen. Und man findet leicht nach kurzer Rechnung (oder indem man G(a,b) betrachtet auch ohne ;-)), dass a=255 und b=0 oder umgekehrt maximale Werte für G(a,b) liefert.

Gruss
M