2D-Faltung in der Bildverarbeitung

Dieser Artikel gibt einen Einblick in die zweidimensionale Faltung und das Zero-Padding im Hinblick auf die digitale Bildverarbeitung.

In meinem vorherigen Artikel „Besserer Einblick in DSP: Lernen über Faltung“ habe ich die Faltung und ihre zwei wichtigen Anwendungen im Bereich der Signalverarbeitung besprochen. Dort wurden die Signale vermutlich als eindimensional im räumlichen Bereich betrachtet. Der Prozess der Faltung kann jedoch auch bei mehrdimensionalen Signalen durchgeführt werden.

In diesem Artikel werden wir versuchen, den Prozess und die Folgen der zweidimensionalen Faltung, die im Bereich der Bildverarbeitung weit verbreitet ist, besser zu verstehen.

Die Definition der 2D-Faltung

Faltung mit eindimensionalen Signalen wird als 1D-Faltung oder einfach als Faltung bezeichnet. Wird die Faltung dagegen zwischen zwei Signalen durchgeführt, die sich über zwei zueinander senkrechte Dimensionen erstrecken (d. h., wenn die Signale zweidimensional sind), dann wird sie als 2D-Faltung bezeichnet. Dieses Konzept kann auf mehrdimensionale Signale ausgedehnt werden, wodurch eine mehrdimensionale Faltung möglich wird.

Im digitalen Bereich wird die Faltung durch Multiplikation und Akkumulation der Momentanwerte der sich überschneidenden Abtastwerte durchgeführt, die zwei Eingangssignalen entsprechen, von denen eines umgedreht wird. Diese Definition der 1D-Faltung gilt auch für die 2D-Faltung, mit der Ausnahme, dass im letzteren Fall eines der Eingangssignale zweimal gespiegelt wird.

Diese Art von Operation wird häufig im Bereich der digitalen Bildverarbeitung verwendet, wobei die 2D-Matrix, die das Bild darstellt, mit einer vergleichsweise kleineren Matrix, dem sogenannten 2D-Kernel, gefaltet wird.

Ein Beispiel für eine 2D-Faltung

Lassen Sie uns versuchen, den Pixelwert des Ausgangsbildes zu berechnen, der sich aus der Faltung der 5×5 großen Bildmatrix x mit dem Kernel h der Größe 3×3 ergibt, wie in Abbildung 1 gezeigt.

Abbildung 1: Eingabematrizen, wobei x für das Originalbild und h für den Kernel steht. Bild erstellt von Sneha H.L.

Um dies zu erreichen, wird im Folgenden das schrittweise Verfahren skizziert.

Schritt 1: Matrixinversion

Dieser Schritt beinhaltet die Umkehrung des Kerns entlang der Zeilen, gefolgt von einer Umkehrung entlang der Spalten, wie in Abbildung 2 dargestellt.

Abbildung 2: Bildliche Darstellung der Matrixinversion. Bild erstellt von Sneha H.L.

Als Ergebnis wird jedes (i,j)-te Element des ursprünglichen Kerns zum (j,i)-ten Element in der neuen Matrix.

Schritt 2: Gleiten Sie den Kernel über das Bild und führen Sie die MAC-Operation zu jedem Zeitpunkt durch

Überlappen Sie den invertierten Kernel über das Bild, indem Sie Pixel für Pixel vorgehen.

Berechnen Sie für jeden Fall das Produkt der sich gegenseitig überlappenden Pixel und berechnen Sie deren Summe. Das Ergebnis ist der Wert des Ausgangspixels an dieser bestimmten Stelle. In diesem Beispiel wird davon ausgegangen, dass nicht überlappende Pixel einen Wert von „0“ haben. Wir werden dies im nächsten Abschnitt über „Zero Padding“ ausführlicher besprechen.

Im vorliegenden Beispiel beginnen wir damit, den Kernel spaltenweise zu verschieben und bewegen uns dann entlang der Zeilen vorwärts.

Pixel Zeile für Zeile

Zunächst überspannen wir die erste Zeile vollständig und bewegen uns dann zur zweiten vor, und so weiter und so fort.

Bei diesem Vorgang würde die erste Überschneidung zwischen dem Kernel und den Bildpixeln entstehen, wenn das Pixel unten rechts im Kernel auf den ersten Pixelwert oben links in der Bildmatrix fällt. Diese beiden Pixelwerte sind in Abbildung 3a hervorgehoben und in dunkelroter Farbe dargestellt. Der erste Pixelwert des Ausgabebildes ist also 25 × 1 = 25.

Als Nächstes schieben wir den Kernel entlang derselben Zeile um ein einziges Pixel weiter. In diesem Stadium überschneiden sich zwei Werte der Kernelmatrix (0, 1 – in dunkelroter Schrift dargestellt) mit zwei Pixeln des Bildes (25 und 100 in dunkelroter Schrift dargestellt), wie in Abbildung 3b gezeigt. Der resultierende Ausgangspixelwert ist also 25 × 0 + 100 × 1 = 100.

Abbildung 3a, 3b. Faltungsergebnisse für die Ausgangspixel an den Positionen (1,1) und (1,2). Bild erstellt von Sneha H.L.

Abbildung 3c, 3d: Faltungsergebnisse für die Ausgangspixel an den Positionen (1,4) und (1,7). Bild erstellt von Sneha H.L.

Wenn man in ähnlicher Weise vorgeht, können alle Pixelwerte der ersten Zeile im Ausgangsbild berechnet werden. Zwei solche Beispiele, die den vierten und siebten Ausgabepixeln der Ausgabematrix entsprechen, sind in den Abbildungen 3c und 3d dargestellt.

Wenn wir den Kernel weiter entlang derselben Zeile verschieben, überschneidet sich keines der Pixel im Kernel mit denen im Bild. Das bedeutet, dass wir in dieser Zeile fertig sind.

Vertikal nach unten schieben, horizontal vorrücken

Der nächste Schritt wäre, vertikal um ein einziges Pixel nach unten zu schieben, bevor wir wieder mit der horizontalen Bewegung beginnen. Die erste Überschneidung, die dann auftritt, ist in Abbildung 4a dargestellt, und wenn wir die MAC-Operation darüber ausführen, erhalten wir das Ergebnis 25 × 0 + 50 × 1 = 50.

Danach können wir den Kernel in horizontaler Richtung verschieben, bis es keine Werte mehr gibt, die sich zwischen dem Kernel und den Bildmatrizen überschneiden. Ein solcher Fall, der dem sechsten Pixelwert der Ausgangsmatrix (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200) entspricht, ist in Abbildung 4b dargestellt.

Abbildung 4a, 4b. Faltungsergebnisse für die Ausgangspixel an den Positionen (2,1) und (2,6). Bild erstellt von Sneha H.L.

Dieser Prozess der Bewegung um einen Schritt nach unten, gefolgt von einer horizontalen Abtastung, muss bis zur letzten Zeile der Bildmatrix fortgesetzt werden. Drei zufällige Beispiele für die Pixelausgaben an den Stellen (4,3), (6,5) und (8,6) sind in den Abbildungen 5a-c dargestellt.

Abbildung 5a. Faltungsergebnisse für die Ausgangspixel bei (4,3). Bild erstellt von Sneha H.L.

Abbildung 5b. Faltungsergebnisse für die Ausgangspixel bei (6,5). Bild erstellt von Sneha H.L.

Abbildung 5c. Faltungsergebnisse für die Ausgangspixel bei (8,6). Bild erstellt von Sneha H.L.

Schritt

Die resultierende Ausgabematrix ist also:

Abbildung 6. Die resultierende Ausgabematrix unseres Beispiels. Bild erstellt von Sneha H.L.

Zero Padding

Die mathematische Formulierung der 2-D-Faltung ist gegeben durch

$$ y\left=\sum_{m=-\infty}^\infty\sum_{n=-\infty}^\infty h\left \cdot x\left $$

wobei, x die Eingangsbildmatrix darstellt, die mit der Kernelmatrix h gefaltet wird, um eine neue Matrix y zu erhalten, die das Ausgangsbild darstellt. Die Indizes i und j beziehen sich auf die Bildmatrizen, die Indizes m und n auf die des Kerns. Beträgt die Größe des an der Faltung beteiligten Kernels 3 × 3, so liegen die Indizes m und n im Bereich von -1 bis 1. Für diesen Fall, ergibt eine Erweiterung der vorgestellten Formel:

$$ y\left=\sum_{m=-\infty}^\infty h\left \cdot x\left + h\left \cdot x\left \\\ + h\left \cdot x\left $$

$$ y\left= h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left \\\ + h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left \\cdot x\left + h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left $$

Das bedeutet, dass für jedes Ausgabepixel, 9 Multiplikationen durchgeführt werden müssen, deren Faktoren die sich überschneidenden Pixelelemente des Bildes und des Kernels sind. Bei der Berechnung des Wertes für unser erstes Ausgabepixel haben wir jedoch nur eine einzige Multiplikation durchgeführt (Abbildung 3a, die als Abbildung 7a wiedergegeben wird). Was hat dies zu bedeuten? Bedeutet es eine Unstimmigkeit mit der Gleichungsform der 2D-Faltung?

Nein, eigentlich nicht. Denn das Ergebnis, das man durch die Addition von neun Produkttermen erhält, kann gleich dem Produkt eines einzigen Terms sein, wenn die Gesamtwirkung der anderen acht Produktterme gleich Null ist. Eine solche Möglichkeit ist der Fall, in dem jedes Produkt der anderen acht Terme sich selbst zu Null auswertet. Im Kontext unseres Beispiels bedeutet dies, dass alle Produktterme, die den nicht überlappenden (zwischen Bild und Kern) Pixeln entsprechen, zu Null werden müssen, damit die Ergebnisse der Formelberechnung mit denen der grafischen Berechnung übereinstimmen.

Aus unseren elementaren Kenntnissen der Mathematik wissen wir, dass, wenn mindestens einer der an der Multiplikation beteiligten Faktoren Null ist, auch das resultierende Produkt Null ist. Mit dieser Analogie können wir sagen, dass wir in unserem Beispiel für jeden nicht überlappenden Pixel der Kernelmatrix einen Bildpixel mit dem Wert Null benötigen. Eine bildliche Darstellung dieses Sachverhalts ist in Abbildung 7b zu sehen. Wichtig ist, dass das Hinzufügen von Nullen zum Bild das Bild in keiner Weise verändert, außer in seiner Größe.

Abbildung 7: Null-Padding für das erste Pixel des Bildes (von mir gezeichnet)

Dieses Hinzufügen zusätzlicher Nullen wird als Null-Padding bezeichnet und muss immer dann erfolgen, wenn sich keine Bildpixel mit den Kernel-Pixeln überschneiden. In unserem Beispiel müssen alle Pixel in den ersten beiden Zeilen und Spalten sowie die Pixel in den letzten beiden Zeilen und Spalten mit Nullen aufgefüllt werden (diese Pixel sind in Abbildung 8 in blauer Schrift dargestellt). Im Allgemeinen ist die Anzahl der Zeilen oder Spalten, die auf jeder Seite des Eingabebildes mit Nullen aufgefüllt werden müssen, gegeben durch (Anzahl der Zeilen oder Spalten im Kernel – 1).

Abbildung 8

Ein wichtiger Punkt, der erwähnt werden sollte, ist die Tatsache, dass das Auffüllen mit Nullen nicht die einzige Möglichkeit ist, mit den durch die Faltung verursachten Randeffekten umzugehen. Andere Padding-Techniken sind Replicate Padding, periodische Erweiterung, Spiegelung usw. (Digital Image Processing Using Matlab 2E, Gonzalez, Tata McGraw-Hill Education, 2009).

Zusammenfassung

Dieser Artikel zielt darauf ab, die grafische Methode der 2-D-Faltung und das Konzept des Zero Padding in Bezug auf die digitale Bildverarbeitung zu erklären.