[IntroPR] Diskrete Faltung

Master / Vertiefung LS 5: Mustererkennung
1

Foliensatz 7: Filtering: noise suppression

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

[IntroPR] Diskrete Faltung
Hallo,

im Foliensatz 7 finden wir die Definition der Indizes etwas verwirrend.

Auf Folie 7-22 hat das Bild [m]f[/m] die Größe [m]Mx * My[/m] und der Filter [m]g[/m] die Größe [m]mx * my[/m].
Auf der nächsten Folie 7-23 steht, dass das Ergebnis der Faltung von [m]f[/m] und [m]g[/m] die Größe [m](Mx + mx - 1)(My + my + 1)[/m][m](Mx + mx - 1)(My + my - 1)[/m] hat. Nach dem Filtern ist das Ergebnis also größer als die Eingabe.

Sagen wir [m]f[/m] habe die Größe 1010, also [m]Mx = My = 10[/m], und der Filter [m]g[/m] habe die Größe 33, also [m]mx = my = 3[/m]. Dann hat das Ergebnis [m]h[/m] die Größe 1212.
Wenn man [m]h[/m] berechnet mit der unteren Formel auf Folie 7-23, kommt man beim letzten Element zu [m]h[11, 11] = f[11, 11] * g[0, 0] + f[11, 10] * g[0, 1] + … + f[9, 9] * g[2, 2][/m].
[m]f[/m] hat aber nur die Größe 1010 und die rechte untere Ecke von [m]f[/m] wäre [m]f[9, 9][/m]. Wird hier implizit davon ausgegangen, dass die Größe von [m]f[/m] angepasst wurde, z.B. durch zeropadding um jeweils eine Zeile und Spalte an allen Seiten?

Auf Folie 7-33 gibt es noch ein Beispiel zum Mean Filter mit leicht anderen Indizes. Nach dieser Formel wäre das erste Element [m]h[0, 0] = f[1, 1] * g[0, 0] + f[1, 0] * g[0, 1] + … + f[-1, -1] * g[2, 2][/m].
Das sieht danach aus, dass das Ausgabebild die gleiche Größe wie das Eingabebild haben soll. Kann jemand bestätigen, ob wir das richtig geschlossen haben?

3

typo.

Würde ich auch so sehen, bzw. dass convolution-Schritte, die auf nicht-existente Pixel zugreifen, in der Summe weggelassen werden - was durch das Produkt auf das selbe wie zero-padding raus läuft. Das ist standard so.

Das ist auch, was man in der Praxis meistens will.

Was die Prüfung angeht: Die ist ja mündlich und die Randbehandlung ist natürlich etwas, worüber ihr als Programmierer entscheiden müsst. Also wenn das zur Sprache kommt, einfach die möglichen Varianten und vor-/nachteile parat haben.

Bildgröße:

  • So viel größer machen, dass man wirklich auf M_x + m_x - 1 kommt (*)
  • Gleich lassen (praktisch)
  • Es ist auch denkbar, alle Pixel weg zu lassen, bei denen man über den Rand hinaus kommt. Bei einem 3x3 Bild verliert man dann einen Pixel. (Vorteil: Pixel basiert nur auf 100% gültigen Daten.)

Padding:

  • Zero Padding, Nachteil: Durch die effektiv kleinere Anzahl Summanden werden die Pixelwerte bei Mittelungsfiltern (mean / gauss) am Bildrand immer kleiner. Bei gradientenartigen Filtern wie dem Sobel-Filter ist das noch problematischer und man verwendet lieber…
  • Nearest Neighbor Extrapolation, sprich einfach den Rand-Wert wiederholen: Einfach zu implementieren, indem man den Index-Zugriff minimal 0 und maximal M_x groß macht, Randwerte haben aber dann einen großen Einfluss. (Beim Sobel wird aus der central difference eine forward bzw. backward difference, also passt eigentlich die Pixelposition nicht ganz.)
  • Normalisierung anpassen. Meist wählt man seine Filtergewichte ja so, dass sie sich zu 1 addieren. Wenn man am Rand nicht alle Filterelemente nutzt, kann man die übrigen Filterelemente passend hochskalieren. Nachteil: Am aufwendigsten, mit gradientenartigen Filtern ist das wieder blöd.

Abgesehen von Zero Padding, wo man das Ergebnis entsprechend kleiner skaliert, ist das Endergebnis natürlich immer etwas mehr noisy, weil es ja auf weniger Werten basiert.

(*) Ein Spezialfall der mir einfällt wann das sinnvoll sein könnte (für die Prüfung würde ich mich jetzt nicht damit beschäftigen): Man kann einen 3x3 Gauss Filter durch 2x 2x2 mean filtern berechnen (einfach mal die convolution von zwei mean filtern berechnen, dann sieht man das, nach der ersten convolution liegen die Pixel zwischen den Ursprungspixeln, nach der zweiten passt es wieder), dann muss man nach dem ersten mean Filter das Bild einen Pixel größer machen, damit man beim zweiten mean Filter alle Bildpixel berechnen kann. Interessant ist das v.a. bei größeren Filtern, weil die Filtergröße ja quadratisch zum Rechenaufwand beiträgt und irgendwann 2x filtern effizienter wird. Mit Caches geht das auch sehr effizient (vgl. temporal-blocking in PTfS :-p).

4

Die “richtige” Herangehensweise hängt hier von der Anwendung ab. Bei einigen Filtern macht es durchaus Sinn, dass das Ausgabebild kleiner wird als das Eingabebild. Ein Beispiel wären Kantenfilter. Macht man hier Zero-Padding, dann holt man sich am Rand künstliche Kanten.

Bei einem Glättungsfilter sieht es schon anders aus, hier will man nicht einfach Information verlieren. Daher dann die verschiedenen Methoden, die L. F. Ant genannt hat. Anfügen möchte ich hierzu noch das Mirror Padding, hier wird das Bild entspr. gespiegelt wiedergegeben, das kann je nach Filterart bei größeren Filtern gefragt sein, und ist ebenso einfach zu implementieren. Auch kann periodisch angefügt werden (also Indizierung via Modulo Bildbreite/-höhe), dies macht Sinn wenn man die Fourier-Transformation als Faltung implementiert (die Fourier-Transformation erwartet ein periodisches Eingangssignal).