Digitale Filter - Bildoperatoren


 
Digitale Filter können mehr als Punktoperatoren. Mit ihnen kann man Bilder schärfen oder Kanten innerhalb eines Bildes finden. Damit sind diese sogenannten "lokalen Operatoren" auch für den Bau von autonomen Robotern von interesse, denn um z.b. Hindernissen auszuweichen, müssen diese zuvor ersteinmal erkannt werden.

Die Abschnitte Grundlagen der Bildverarbeitung und Farbbild - Graubild - Binärbild, welche bisher betrachet wurden, hatten eines gemeinsam: sie nahmen ein Bildpunkt aus dem Orginalbild und veränderten (transformierten) ihn. Der veränderte Bildpunkt ersetzte dann entweder den alten originalen Bildpunkt oder wurde in ein neues (leeres) Bild geschrieben. Diese Bildoperation bezeichnet man als Punktoperation.

 


 

Punktoperator  
Ein einzelner Pixel (Bildpunkt) wird gelesen und verändert (transformiert). Der Punktoperator wird auch als lokaler Operator bezeichnet.

Wenn ein Bild z.B. weich gezeichnet oder aber geschärft werden soll, reicht die Auswertung lediglich eines Bildpunktes nicht mehr aus. Die nächste Erweiterung ist dann, das mehrere Bildpunkte die sich in der Nachbarschaft des zu veränderten Bildpunktes befinden herangezogen werden, um zum gewünschten Ergebnis zu kommen. Diesen Typ von Bildoperation nennt man lokale Operation. Die Theorie hinter diesen Transformation heißt "digitale Filter". Darum soll es in diesem Abschnitt gehen.

3x3 Filter

 Wir betrachten 3x3 Filter, d.h., der Filter besitzt 9 Werte. Im Orginal-Bild werden dazu der zu verändernde Bildpunkt und seine 8 Nachbarpunkte herangezogen.

 
  
  
    

 Orginal-Bild (Quelle, I = Input)

   3x3 Filter-Matrix (M=Maske)
   Ziel-Bild (Senke, O = Output)

Der zu verändernde Bildpunkt befindet sich in der Mitte, umgeben von 8 Nachbarpixeln, welche auch ausgewertet werden müssen. Der zentrale Punkt mit seinen 8 Nachbarn werden wir mit "lokalen Bildbereich" bezeichnen.

 

Der Filter besitzt 9 Werte. Filter und Orginalbild werden miteinander verknüpft. Die Verknüpfung bezeichnet man als Faltung. Die mathematischen Prinzipien, die der Faltung zu Grunde liegen, gehören nicht zur Schulmathematik und werden hier deshalb nicht aufgeführt.

  Der Original-Bildpunkt mit seinen Nachbarn wurde zusammen mit einem Filter kombiniert. Das Ergebnis ist der hier Rot dargestellte Bildpunkt.

 

O =  I * M  (Faltung)

mit 

O = Output (Ziel)
I = Input (Orginal-Bild)
* = Symbol für die mathematische Operation der Faltung

Der beschriebene Prozess berechnet den Wert eines Pixels und muss deshalb wiederholt angewandt werden, um für alle Pixel eines Bildes ein vollständiges Bild liefern zu können.

lokale Operation  
Ein Filter ist ein lokaler Operator. Ein Bildbereich I und eine Maske M werden verknüpft, um den Wert eines neuen Pixels (Bildpunkt, O ) zu berechnen. Die Operation O = I * M bezeichnet man als Faltung.

 

Die Faltung im Detail

Es wird jetzt gezeigt, wie, ausgehend von einem lokalen Bildbereich und einer Maske, ein neuer Bildpunkt berechnet wird. In späteren Abschnitten wird im wesentlichen nur noch die Maske verändert, die vorgehensweise bleibt aber immer dieselbe.

  • Der Wert jedes Pixels im Bildbereich wird mit dem entsprechenden Wert der Maske multipliziert. Auf diese Weise ergeben sich 9 Terme.
  • Alle 9 Terme werden addiert.
  • Der so ermittelte Wert ist der Wert des neuen Bildpunktes.

  •  Dieses Beispiel berechnet für den Bildpunkt 5 einen neuen Wert:

 \[ I= \begin{pmatrix} 1 & 2 &3 \\  4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}\]

\[ M= \begin{pmatrix} 1 & 2 & 1 \\  2 & 3 & 2 \\1 & 2 & 1 \end{pmatrix}\]

  • I und M werden komponentenweise multipliziert: \[ I + M =\begin{pmatrix} 1 & 4 & 3 \\ 8 & 15 & 12 \\ 7 & 16 & 9 \end{pmatrix} \]
  • Summe über alle Terme bilden:  1 +4 +3 +8 +15 +12 +7 +16 + 9 = 75
  • Der neue Bildpunkt hat einen Wert von 75.

Der selbe Formalismus ein wenig formaler 

Der Umgang mit dem Summenzeichen ist im Downloadbereich Mathematische Grundlagen  beschrieben.

Ziel ist es, die folgende Formel herzuleiten, wie sie in jedem Buch über Digitale Bildverarbeitung zu finden ist.

\[ O = I * M \] mit

\[ O(i,j)  = \sum_{y=-1}^1 \sum_{x=-1}^1 M(x,y) \cdot I(i+x,j+y) \]

Die Formel kann direkt aus dem obigen Beispiel hergeleitet werden, indem statt konkreter Zahlen verallgemeinerte Koordinaten und Gewichte verwendet werden. O(i,j) bedeutet, dass der Filter M  auf den Bildpunkt mit den Koordinaten i,j angewandt wird. O(i,j) ist der neue Grauwert. Wir beschränken uns hier auf die Auswertung von Graubildern, d.h jeder Bildpunkt ist eindeutig durch eine Zahl beschrieben.

 

\[ I(x,y) = \begin{pmatrix} w1 & w2 & w3 \\  w4 & w5 & w6 \\ w7 & w8 & w9 \end{pmatrix}\]

\[ M(x,y) = \begin{pmatrix} m1 & m2 & m3 \\  m4 & m5 & m6 \\ m7 & m8 & m9 \end{pmatrix}\]

  • Beispiele für I(x,y) und M(x,y): Während I(x,y) relative Angaben enthält, um verschiedene Bildpunkte zu repräsentieren, beschreibt M(x,y) konstante Werte. I(7,8) ist demnach der Bildpunkt mit den Koordinaten (7 | 8 ) während M(1,1) den Eintrag in der zweiten Zeile und zweiten Spalte (m9) darstellt.
    • I(x,y) = w5 (Wert an der Position x,y)
    • I(x-1,y-1) = w1 (Wert an der Position x-1,y-1)
    • M(1,-1) = m3 (Filterwert an der Stelle  x+1,y-1)
    • M(0,0) = m5
    • M(1,1) = m9

 Nach dem obigen Beispiel gilt dann:

 \[ \begin{split} O(i,j) =  m1\cdot w1 + m2\cdot w2 + m3\cdot w3\\ + m4\cdot w4 + m5\cdot w5 +  m6\cdot w6 \\+ m7\cdot w7 + m8\cdot w8 + m9\cdot w9 \end{split} \]

(Die Werte für I werden eingesetzt)

\[ \begin{split} = m1\cdot I(i-1,j-1) + m2\cdot I(i,j-1) + m3\cdot I(i+1,j-1) \\+ m4 \cdot I(i-1,j) + m5\cdot I(i,j)+ m6\cdot I(i+1,j) \\ + m7\cdot I(i-1,j+1) + m8\cdot I(i,j+1) + m9\cdot I(i+1,j+1) \end{split} \]

(Die Werte für M werden eingesetz)

\[ \begin{split} = M(-1,-1) \cdot I(i-1,j-1) + M(0,-1)\cdot I(i,j-1) + M(1,-1)\cdot I(i+1,j-1) \\+ M(-1,0) \cdot I(i-1,j) + M(0,0)\cdot I(i,j)+ M(1,0)\cdot I(i+1,j) \\ + M(-1,1)\cdot I(i-1,j+1) + M(0,1)\cdot I(i,j+1) + M(1,1)\cdot I(i+1,j+1) \end{split} \]

(Summenzeichen für die erste Komponente benutzen - Laufvariable heißt x)

\[ \begin{split} = \sum_{x=-1}^1 \{ M(x,-1) \cdot I(i+x,j-1)  \\+ M(x,0) \cdot I(i+x,j)  \\ + M(x,1)\cdot I(i+x,j+1) \} \end{split} \]

(Summenzeichen auch für die zweite Komponente benutzen - Laufvariable heißt y)

\[ \begin{split} = \sum_{y=-1}^1  \sum_{x=-1}^1 M(x,y) \cdot I(i+x,j+y)  \end{split} \]

Das war es, diese Formel ist mit der Eingangsformel identisch.

Zusammenfassung

Um einen digitalen Filter anzuwenden, sind folgende Schritte abzuarbeiten:

  • Ein digitaler 3x3-Filter muss zur Verfügung stehen
  • Der Filter wird über ein Bildbereich gelegt (Faltung) und ein neuer Bildpunkt wird berechnet. Dieser Bildpunkt wird zwischengespeichert bzw. in ein neues Bild geschrieben.
  • Der Filter wird über den nächsten Bildbereich gelegt, sodass der nächste Bildpunkt berechnet werden kann. Auf diese Weise werden alle neuen Bildpunkte berechnet und in ein neues Bild geschrieben.

Da die Filter-Matrix an den Bildrändern nicht überstehen darf und in diesem Fall nur ein nicht Randpunkt neu berechnet werden kann, ist das erzeugte Bild immer etwas kleiner als das Orginal-Bild. (Dieses Randproblem greifen wir später noch einmal auf, vorerst begnügen wir uns damit, dass das erzeugte Bild um zwei Pixel schmaler in Höhe und Breite wird).