Matrizen und digitale Bilder

fig_felix_the_cat_face

Abb. 1

Übersetzt von Kira Katzenberger und Bettina Rösken-Winter (Ruhr-Universität Bochum)

Bilder, die man auf Internetseiten sehen kann, und Fotos, die mit dem Handy gemacht wurden, sind Beispiele für digitale Bilder. Es ist möglich, diese Art von Bildern durch Matrizen darzustellen. Zum Beispiel kann das kleine Bild von Felix der Katze (Abb. 1) dargestellt werden durch eine 35 \times 35 -Matrix, deren Einträge aus den Zahlen 0 und 1 bestehen. Diese Nummern geben die Farbe jedes Pixels an (ein Pixel ist das kleinste Element eines digitalen Bildes, das nur eine Farbe gleichzeitig annehmen kann): Die Zahl 0 kennzeichnet die Farbe Schwarz, die Zahl 1 kennzeichnet die Farbe Weiß. Digitale Bilder, die nur zwei Farben verwenden, werden binäre Bilder oder boolesche Bilder genannt.

sample-matrix

Abb. 2: Die Matrix zu Felix, der Katze.

Graustufenbilder können auch durch Matrizen dargestellt werden. Jeder Eintrag der Matrix legt die Intensität des entsprechenden Pixels fest. Der Einfachheit halber nutzen die meisten aktuellen digitalen Dateien ganze Zahlen zwischen 0 (um Schwarz zu kennzeichnen, die Farbe der geringsten Intensität) und 255 (um Weiß zu kennzeichnen, die Farbe der höchsten Intensität), sodass es eine Gesamtmenge von insgesamt 256 = 2^8 verschiedenen Graustufen gibt. (Diese Anzahl verschiedener Graustufen genügt, um mit Bildern auf WEB-Seiten zu arbeiten. Allerdings gibt es bestimme spezielle Anwendungen, die mehr Graustufen benötigen, um ein Bild mit mehr Details wiederzugeben und um Rundungsfehler in numerischen Berechnungen zu vermeiden, wie im Fall medizinischer Bilder.)

Farbbilder wiederum können durch drei Matrizen dargestellt werden. Jede Matrix gibt die Menge an Rot, Grün und Blau an, die das Bild enthält. Dieses Farbsystem ist bekannt als RGB. (Es gibt viele andere Farbsysteme, die abhängig von der Anwendung genutzt werden: CMYK (zum Drucken), Y’IQ (für die analoge Übertragung von TV in NTSC), etc.). Die Elemente dieser Matrizen sind ganze Zahlen zwischen 0 und 255, und sie legen die Intensität der Pixel bezüglich der Farbe, welche die jeweilige Matrix liefert, fest. Demnach ist es im RGB-System möglich 2563= 224= 16777216 verschiedene Farben darzustellen.

c2g

Abb. 3: Originalbild, Rot-, Grün- und Blaukomponenten

Digitale Bildverarbeitung und Operationen mit Matrizen

Wenn digitale Bilder mit Hilfe von Matrizen dargestellt werden, können wir fragen, wie Operationen und Veränderungen der Matrizeneinträge das zugehörige Bild verändern. Wenn wir zum Beispiel das binäre Bild A (siehe Abb. 4) als Matrix A = (a_{i,j}) betrachten, dann gehört Bild B zu der transponierten Matrix von A, sprich B = (b_{i, j}) = (a_{j, i}) = A^{T}. Das Bild H gehört dann zum Beispiel zu der Matrix (a_{j, 35 - i + 1}). Versuchen Sie herauszufinden, in welcher Beziehung die anderen Bilder zur Matrix A stehen!

felix_the_cat_

Abb. 4: Matrixtransformationen

Ein anderes Beispiel: Wenn wir die arithmetischen Mittel der Matrizen der Rot-, Grün- und Blaukomponenten (R,G und B) eines Farbbildes A nehmen, bekommen wir eine Graustufenversion des Bildes (Werte nicht-ganzer Zahlen werden auf die nächste ganze Zahl gerundet):

Abb. 5: Arithmetisches Mittel der Komponentenmatrizen

Abb. 5: Arithmetisches Mittel der Komponentenmatrizen

Ein weiteres Beispiel: Wenn man die Operationen Multiplikation mit einem Skalar und Addieren von Matrizen ausführt, ist es möglich, einen Bildübergangseffekt zu erzeugen, wie er üblicherweise in PowerPoint{}^{\copyright}-Präsentationen und bei Diavorführungen genutzt wird. Genauer gesagt betrachtet man zwei Graustufenbilder derselben Größe, dargestellt durch die Matrizen A und Z. Für jeden Skalar (eine reelle Zahl) t aus dem Intervall [0,1] definieren wir  die Matrix

    \[M(t) = (1 - t) A + t Z.\]

Dann ist M(0) = A, M(1) = Z und für jedes t zwischen 0 und 1 liegen die Einträge der Matrix M(t) zwischen denen der Matrizen A und Z. Deshalb variiert die Matrix M(t) von A bis Z, wenn t Werte von 0 bis 1 durchläuft. Im Fall von Farbbildern muss die obige Transformation die Matrizen R, G und B betreffen, aus denen sich jedes Bild zusammensetzt.

Abb. 6: M(0)=A, M(0,13), M(0,25), M(0,38), M(0,50), M(0,63), M(0,75), M(0,88), M(1)=Z

Abb. 6: M(0)=A, M(0,13), M(0,25), M(0,38), M(0,50), M(0,63), M(0,75), M(0,88), M(1)=Z

Auch Matrizenmultiplikationen haben Anwendungen in der digitalen Bildverarbeitung. Obwohl unser nächstes Beispiel aufwändiger ist (mit einem Gegenstand, der fortgeschrittener mathematischer Techniken bedarf, die normalerweise nur in Linearer Algebra an Universitäten gelernt werden), glauben wir trotzdem, dass diese Anwendung für den Leser von Interesse ist. Dieses Beispiel bietet die Möglichkeit, eine erstaunliche Anwendung zu genießen, welche sich aus der Möglichkeit ergibt, eine Matrix zu zerlegen und als Produkt von Matrizen mit speziellen Strukturen darzustellen. Die weggelassenen Details können der Literatur [Lay, 2011] und [Poole, 2005] entnommen werden. Wir betrachten dafür eine Singulärwertzerlegung (SVD für singular value decomposition), die daraus besteht, eine Matrix als Produkt von drei Matrizen darzustellen:                      

    \[A_{m \times n}^{\vphantom{T}} = U_{m \times m}^{\vphantom{T}} S_{m \times n}^{\vphantom{T}} V_{n \times n}^{T},\]

wobei U und V orthogonale Matrizen sind (das heißt U^{T} U und V^{T}V sind m \times m bzw. n \times n Einheitsmatrizen) und S ist eine Matrix mit Einträgen s_{i, j}, die gleich Null sind für i \not= j und s_{1, 1} \geq s_{2, 2} \geq \cdots \geq s_{k, k} \geq 0, mit k = \min\{m, n\}. Es folgt ein Beispiel für eine Singulärwertzerlegung:

    \[A = \left[\begin{array}{rrr} -1 & 1 & 0 \\ 0 & -1 & 1 \end{array}\right] = U S V^{T}\]

    \[= \left[ \begin{array}{rr} \displaystyle -\frac{\sqrt{2}}{2} & \displaystyle \frac{\sqrt{2}}{2} \vspace*{0.5ex} \\ \displaystyle \frac{\sqrt{2}}{2} & \displaystyle \frac{\sqrt{2}}{2} \end{array} \right] \left[ \begin{array}{rrr} \sqrt{3} & 0 & 0 \\ 0 & 1 & 0 \end{array} \right] \left[ \begin{array}{rrr} \displaystyle \frac{\sqrt{6}}{6} & \displaystyle -\frac{\sqrt{2}}{2} & \displaystyle \frac{\sqrt{3}}{3} \vspace*{0.5ex} \\ \displaystyle -\frac{\sqrt{6}}{3} & 0 & \displaystyle \frac{\sqrt{3}}{3} \vspace*{0.5ex} \\ \displaystyle \frac{\sqrt{6}}{6} & \displaystyle \frac{\sqrt{2}}{2} & \displaystyle \frac{\sqrt{3}}{3} \end{array} \right]^{T}. $ } }\]

Es kann gezeigt werden, dass jede Matrix eine Singulärwertzerlegung besitzt ([Lay, 2011], [Poole, 2005]). Außerdem existieren Algorithmen, die es uns ermöglichen, solche Zerlegungen mit Hilfe eines Computers zu berechnen. Der entscheidende Punkt unseres Beispiels ist, zu betrachten, dass, wenn \textbf{u}_{1}, \textbf{u}_{2}, \ldots, \textbf{u}_{m} die Spalten der Matrix U und \textbf{v}_{1}, \textbf{v}_{2}, \ldots, \textbf{v}_{n} die Spalten der Matrix V sind, dann ist

    \[A = USV^{T} = s_{1, 1} \textbf{u}_{1} \textbf{v}_{1}^{T} + s_{2, 2} \textbf{u}_{2} \textbf{v}_{2}^{T} + \cdots + s_{k, k} \textbf{u}_{k} \textbf{v}_{k}^{T}.\]

Warum geht man so vor? Angenommen A, ein Graustufenbild der Größe 1000 \times 1000, muss von einem Satelliten zu einem Labor auf der Erde übertragen werden. Im Prinzip müsste der Satellit eine Millionen Zahlen (eine für jedes Pixel) senden. Da typischerweise nur die ersten Einträge s_{i,i} der Matrix S der Singulärwertzerlegung von A bedeutend sind (die anderen sind „klein“), genügt es demnach, dass der Satellit, sagen wir, die ersten 20 Spalten von U und V sendet sowie die 20 ersten Einträge s_{i,i} (insgesamt müssen also nur 20 \cdot 1000 + 20 \cdot 1000 + 20 = 40020 Zahlen gesendet werden). Aufgrund dieser Daten berechnet das Labor auf der Erde die Matrix s_{1, 1} \textbf{u}_{1} \textbf{v}_{1}^{T} + s_{2, 2} \textbf{u}_{2} \textbf{v}_{2}^{T} + \cdots + s_{20, 20} \textbf{u}_{20} \textbf{v}_{20}^{T}, die eine Approximation des Originalbildes ermöglicht.

Betrachten wir ein Beispiel: Das Bild des Mathematikers Christian Felix Klein(1849-1925) (siehe Abb. 7), hat 720 \times 524 =377280 Pixel.

klein_524

Abb. 7: Felix Klein

Aus der Singulärwertzerlegung der zugehörigen Matrix des Bildes können wir die Matrizen s_{1, 1} \textbf{u}_{1} \textbf{v}_{1}^{T} + s_{2, 2} \textbf{u}_{2} \textbf{v}_{2}^{T} + \cdots + s_{r, r} \textbf{u}_{r} \textbf{v}_{r}^{T} für r = 1, 5, 10 und 20 berechnen. Diese Matrizen erzeugen Approximationen des Originalbildes, wie in den folgenden Bildern zu sehen ist. Beachten Sie, dass das Originalbild zu dem Wert r = 524 gehört. Das Ergebnis ist ziemlich eindrucksvoll, nicht wahr?

Abb. 8: Bilder für r=1, 5, 10 und 20

Abb. 8: Bilder für r=1, 5, 10 und 20

Weitere Anwendungen

Digitale Bildverarbeitung hat viele Anwendungen, zum Beispiel bei der Fernerkundung, der Datenübermittlung, der Medizin, Robotern, Computer, der Filmindustrie, etc. In der Fernerkundung zum Beispiel, sind Bilder, die von Satelliten aufgenommen wurden, hilfreich, um natürliche Ressourcen etwa für geographische Kartierung, zur Analyse der Städteausdehnung und viele weitere ökologische Anwendungen zu erhalten. Bei der Bildübertragung gibt es zum Beispiel die Kommunikation via Fax, Netzwerke, das Internet oder Videoüberwachung. Zur medizinischen Anwendungen gehören die Entwicklung von Röntgenbildern, Projektionsbildern bei Computertomographien, Radiologie, Magnetresonanztomographien (MRT) und bei Ultraschalluntersuchungen.

Einige Methoden der Erfassung und Übertragung können Störungen in Bildern verursachen. Der Medianfilter ist eine Bildbearbeitungstechnik, die genutzt wird, um diese Störungen zu entfernen oder deren Effekte zu reduzieren: Für jeden Eintrag der Matrix betrachten wir die benachbarten Einträge und ordnen alle in einer Liste an. Der Medianfilter besteht daraus, dass der mittlere Wert der Liste ausgewählt und der zentrale Eintrag durch diesen Wert ersetzt wird.

Abb. 9: Der Medianfilter

Abb. 9: Der Medianfilter

Abb. 10: Bild mit Rauschen und Bild mit Medianfilter

Abb. 10: Bild mit Rauschen und Bild mit Medianfilter

Es gibt viele weitere Techniken in der Bildvearbeitung mit anderen Zielen. Die folgenden Bilder zeigen Beispiele für Kontrastregulierung, Kantenerkennung und Schwellenwertregulierung.

Abb. 11: Originalbild und dasselbe Bild mit Kontrastregulierung, Kantenerkennung und Schwellenwertregulierung.

Abb. 11: Originalbild und dasselbe Bild mit Kontrastregulierung, Kantenerkennung und Schwellenwertregulierung.

Abschlussbemerkung

Unser Ziel mit diesem Beitrag ist es, die für Lehrer und Schüler wenig bekannte Anwendung von Matrizen vorzustellen: Die Bearbeitung von digitalen Bildern. Es ist wichtig zu beachten, dass die mathematischen Werkzeuge, die mit diesem Thema in Verbindung stehen, weit über Matrizen hinaus reichen. Das Thema ist umfangreich, reichhaltig und zeitgemäß. Leider erlaubt uns die für diesen Artikel empfohlene Beschränkung auf wenige Seiten nicht, auf weitere Details einzugehen. Als Vertiefung für Leser, die motiviert sind mehr über das Thema herauszufinden, empfehlen wir die Bücher [Gonzales und Woods, 2007] und [Gomes und Velho, 2008].

 

Quellen

Auf dieser Website gibt es eine Reihe interaktiver Anwendungen, die es erlauben, die Beziehungen zwischen Matrizen und digitalen Bildern, die in diesem Text vorgestellt wurden, zu erkunden. Dort findet sich auch ein DOC-Dokument mit Aufgabenvorschlägen, die im Unterricht eingesetzt werden können.

 

Dies sind die im Text zitierten Quellen:

Gomes, J.; Velho, L. Image Processing for Computer Graphics and Vision. Springer-Verlag, 2008.

Gonzalez, R. C.; Woods, R. E. Digital Image Processing. Third Edition. Prentice Hall, 2007.

Lay, D. Linear Algebra and Its Applications. Forth Edition. Addison Wesley, 2011.

Poole, D. Linear Algebra: A Modern Introduction. Second Edition. Brooks Vole, 2005.

Das Foto der Mona Lisa in LEGO ist Eigentum von Marco Pece Udronotto, der freundlicherweise genehmigt hat, sein Werk in dieser Arbeit zu verwenden.

 

Andere Sprachen: Englisch, Französisch, Italienisch, Arabisch

PDF Creator    Send article as PDF   
This entry was posted in Vignettes. Bookmark the permalink.

Schreib einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *