Schwellenwertverfahren

Die Schwellwertverfahren sind eine Gruppe von Algorithmen zur Segmentierung von digitalen Bildern. Das zu segmentierende Bild ist hierbei in Form von Zahlenwerten (Farbwerten pro Bildpunkt) gegeben. Grundsätzlich wird hierbei die Zugehörigkeit eines Bildpunktes zu einem Segment durch den Vergleich des Grauwertes (oder eines anderen eindimensionalen Merkmals) mit einem Schwellwert entschieden. Da diese Operation für jeden Pixel einzeln angewendet wird, ist das Schwellwertverfahren ein pixelorientiertes Segmentierungsverfahren. Schwellwertverfahren gehören zu den ältesten Methoden in der digitalen Bildverarbeitung, das unten beschriebene Verfahren von Otsu wurde im Jahr 1979 von Nobuyuki Otsu publiziert.

Einordnung

Das Schwellwertverfahren ist ein Verfahren zur Segmentierung. Segmentierung ist im Prozess des maschinellen Sehens üblicherweise der erste Schritt der Bildanalyse und kommt nach der Bildvorverarbeitung. Hier der Ablauf:

Szene -> Bildaufnahme -> Bildvorverarbeitung -> Segmentierung (z.B. Schwellwertverfahren) -> Merkmalsextraktion -> Klassifizierung -> Aussage

Eigenschaften

Üblicherweise binarisiert das Schwellwertverfahren das Ausgangsbild, das heißt es werden genau zwei Segmente gebildet (normalerweise Hintergrund und Objekte). Will man mehr als zwei Segmente erzeugen, muss man mehrere Schwellwerte verwenden.

Das Schwellwertverfahren bildet nicht zwangsläufig zusammenhängende Segmente. Im Einzelfall können durchaus einzelne Pixel heraussegmentiert werden. Die Größe der segmentierten Objekte kann je nach Wahl des Schwellwertes stark schwanken.

Verfahren

Das grundlegende Prinzip des Schwellwertverfahrens kann auf verschiedene Art angewendet werden. Beim globalen Schwellwertverfahren wird der Schwellwert (oder die Schwellwerte) global für das gesamte Bild gewählt. Dieses Verfahren ist am einfachsten, ist jedoch auch sehr anfällig für Helligkeitsveränderungen im Bild. Beim lokalen Schwellwertverfahren wird das Ursprungsbild in Regionen eingeteilt und der Schwellwert für jede Region neu gewählt. Als Weiterentwicklung lässt sich das dynamische Schwellwertverfahren ansehen, das für jeden Bildpunkt eine Umgebung festlegt, und auf dieser Umgebung den passenden Schwellwert aussucht.

Beispiel

Das Beispielbild ist ein verrauschtes Graustufenbild mit unscharfen Kanten, wie auf der linken Seite zu sehen. Unscharfe Kanten bedeutet hier, dass die Kanten nicht klar sind, sondern einen Übergang vom weißen Hintergrund zum schwarzen Objekt durchlaufen und dabei die Pixel im Randbereich verschiedene Grautöne annehmen.

Bei statistischen Analyse des Bildes hilft das das zugehörige Histogramm (auf der rechten Seite). Es sind klar zwei Maxima zu erkennen: Das dunkle Objekt und der helle Hintergrund. Auch zwischen den beiden Maxima gibt es für jeden Grauwert eine Reihe von Bildpunkten, dies wird durch den weichen Objektrand verursacht. Dort nehmen die Pixel schrittweise die verschiedenen Graustufen von Weiß bis Schwarz an.

Dieses Ausgangsbild wurde nun mit dem globalen Schwellwertverfahren segmentiert. Als Programm wurde dazu Gimp benutzt, dieses hat das Schwellwertverfahren eingebaut. Zur Demonstration des Verfahrens wurden vier verschiedene Schwellwerte ausprobiert. Jeweils wurde das Bild binarisiert, also zwei Segmentgruppen gebildet. Jedes Pixel wurde entsprechend seiner Zuordnung zu dem einen oder anderen Segment schwarz oder weiß eingefärbt. Genauer: Alle Pixel mit Grauwerten kleiner als der Schwellwert wurden schwarz eingefärbt, alle Pixel mit Grauwerten größer als der Schwellwert dementsprechend weiß.

Datei:Rauschbild-38.png segmentiert mit einem Schwellwert von 38	segmentiert mit einem Schwellwert von 52
segmentiert mit einem Schwellwert von 204	Datei:Rauschbild-222.png segmentiert mit einem Schwellwert von 222

Wird das Bild mit einem Schwellwert von 38 segmentiert, dann werden in dem Objekt mehrere Pixel weiß eingefärbt, also zum Hintergrund segmentiert. Der Schwellwert wurde also zu niedrig gewählt.

Mit den beiden Schwellwerten 52 und 204 ergeben sich recht ordentliche Ergebnisse. Dies gilt auch für alle Schwellwerte zwischen diesen beiden Werten. Der Unterschied ist darin erkennbar, dass das Objekt immer größer wird. Die Wahl des Schwellwertes hat also nicht nur Einfluss auf die Qualität der Segmentierung an sich, sondern auch auf die segmentierte Fläche. Dies sollte beachtet werden. Wenn die Flächenberechnung als nächster Verarbeitungsschritt wichtig ist, dann sollte ein anderes Verfahren als das Schwellwertverfahren gewählt werden. Grund für das Wachstum der Fläche sind die Pixel im Randbereich, die die Grauwerte von weiß nach schwarz schrittweise abdecken.

Mit dem Wert 222 wurde der Schwellwert zu groß gewählt, und auch Hintergrundpixel wurden daher als zum Objekt zugehörig segmentiert.

Wahl des Schwellwertes

Der springende Punkt bei allen Schwellwertverfahren ist die Wahl eines geeigneten Schwellwertes. Hierzu wird das Histogramm zu Rate gezogen. Durch lokale Maxima erkennt man die Grauwerte, bei denen die verschiedenen Segmente liegen. Optimalerweise ist das Histogramm bimodal, das heißt, es lassen sich zwei klar voneinander getrennte Maxima erkennen. Man kann nun den Schwellwert als Mittelwert zwischen diesen beiden Maxima wählen. Eine andere Herangehensweise ist, den Schwellwert auf das lokale Minimum zwischen diesen Maxima zu legen. Hiermit wird wahrscheinlich eine bessere Trennung erreicht. Bearbeitet man immer wieder Bilder aus der gleichen Quelle, kann man oftmals einen einmal gewählten Schwellwert auf alle diese Bilder anwenden. Für eine automatische Bestimmung eines geeigneten Schwellwertes kann man auch das Verfahren von Otsu anwenden.

Verfahren von Otsu

Das Verfahren von Otsu verwendet statistische Hilfsmittel, um das Problem eines möglichst guten Schwellwerts zu lösen, insbesondere wird von der Varianz Gebrauch gemacht. Die Varianz ist ein Maß für die Streuung von Werten. In diesem Fall geht es um die Streuung der Grauwerte.

Beim Verfahren von Otsu werden zunächst die statistischen Varianzen der Grauwerte aller Punkte oberhalb (Teilmenge 1) und unterhalb (Teilmenge 2) des Schwellwertes gebildet. Daneben werden die Varianzen der Grauwerte der beiden Teilmengen zum arithmetischen Gesamtbildmittelwert berechnet. Der Schwellwert wird dann so gewählt, dass der Quotient aus der Summe der Varianzen zum Gesamtbild und der Summe der Einzelvarianzen (jeweils gewichtet mit der Größe der jeweiligen Teilmenge) möglichst groß (maximal) wird.

Es folgt eine mathematischere Darstellung des Algorithmus.

Als Grundlage betrachten wir zwei Klassen von Punkten ( $K_{0}(t)$ und $K_{1}(t)$ ), die aufgrund des gesuchten Schwellwertes $t$ voneinander getrennt werden. $t$ ist hierbei die gesuchte Variable, die beiden Klassen sind das gewünschte Ergebnis. Wir bestimmen nun im weiteren ein Maß, nach dem wir den Schwellwert (und damit die KLassen) optimieren wollen.

Weiterhin sei $p(g)$ die Auftrittswahrscheinlichkeit des Grauwertes 0 < g < G (G ist der maximale Grauwert). Dann ergibt dich die Wahrscheinlichkeit des Auftretens von Pixeln der beiden Klassen mit:

K_{0}

:

P_{0}(t)=\sum _{g=0}^{t}p(g)

und

K_{1}

:

P_{1}(t)=\sum _{g=t+1}^{G}p(g)=1-P_{0}(t)

Bei unserer Annahme von zwei Klassen (also einem Schwellwert) ist die Summe dieser beiden Wahrscheinlichkeiten natürlich 1.

Wenn ${\overline {g}}$ das arithmetische Mittel der Grauwerte innerhalb des gesamten Bildes ist, und ${\overline {g_{0}}}$ und ${\overline {g_{1}}}$ die Mittelwerte innerhalb der einzelnen Klassen, dann ergeben sich die Varianzen innerhalb der beiden Klassen als:

\sigma _{0}^{2}(t)=\sum _{g=0}^{t}(g-{\overline {g_{0}}})^{2}p(g)

und

\sigma _{1}^{2}(t)=\sum _{g=t+1}^{G}(g-{\overline {g_{1}}})^{2}p(g)

Unser Ziel ist nun, die Varianz der Grauwerte in den einzelnen Klassen möglichst gering zu halten, während die Varianz zwischen den Klassen möglichst groß werden soll. Wir bestimmen daher einen Quotienten mit:

Q(t)={\frac {\sigma _{zw}^{2}(t)}{\sigma _{in}^{2}(t)}}

Dabei ist die Varianz zwischen den Klassen:

\sigma _{zw}^{2}(t)=P_{0}(t)\cdot ({\overline {g_{0}}}-{\overline {g}})^{2}+P_{1}(t)\cdot ({\overline {g_{1}}}-{\overline {g}})^{2}

Die Varianz innerhalb der Klassen ergibt sich aus der Summe der beiden Einzelvarianzen:

\sigma _{in}^{2}(t)=P_{0}(t)\cdot \sigma _{0}^{2}(t)+P_{1}(t)\cdot \sigma _{1}^{2}(t)

Der Schwellwert $t$ wird nun so gewählt, dass der Quotient $Q(t)$ maximal wird. $Q(t)$ ist also unser Maß. Wenn wir durch die Maximierung des Quotienten einen Schwellwert bestimmt haben, so teilt dieser die Punktmengen entsprechend der Varianz in optimale Klassen.

Probleme

Das Bild mit einem Helligkeitsverlauf, ...

... und das Ergebnis der Segmentierung mit dem Schwellwert 127.

Das globale Schwellwertverfahren ist sehr anfällig für Helligkeitsänderungen über das Bild. Die drei Bilder demonstrieren dieses Problem. Zuerst wurde unser Anfangsbild mit einer variierenden Helligkeit versehen. Im Histogramm kann man schon das Problem erkennen: Es ist nicht mehr bimodal, wie am Anfang, es lassen sich keine zwei klar voneinander getrennten Maxima ausmachen, diesmal sind es deutlich mehr. Das Ergebnis der Segmentierung zeigt sich dann uneinheitlich: Links oben werden Hintergrundpixel zum Objkt segmentiert, während rechts unten das Objekt als Hintergrund erkannt wird. Nur in der Mitte stimmt die Segmentierung in etwa.

Das lokale oder sogar das dynamische Schwellwertverfahren helfen dort schon ein wenig. Allerdings sind diese deutlich rechenaufwändiger. Außerdem muss man darauf achten, dass in jeder Region alle zu segmentierenden Objekte auftauchen, ansonsten könnten die automatisch gewählten Schwellwerte falsch berechnet werden. Wenn es beispielsweise drei Objekte (und den Hintergrund) im Objekt zu erkennen gibt, werden drei Schwellwerte gewählt, um die vier Klassen voneinander zu trennen. Tauchen in einer Region aber nur zwei der drei Objekte auf, dann kann der dritte Schwellwert dort nicht korrekt bestimmt werden. Das Ergebnis der Segmentierung aus dieser Region wird also nicht gut mit den Ergebnissen der anderen Regionen zusammenpassen. Eine andere Lösung wäre es, die Helligkeit in einem Preprocessing-Schritt auszugleichen, beispielsweise mit einer Shading-Korrektur.

Auch andere Bildfehler, die zu Problemen mit der Segmentierung führen können, kann man durch geeignetes Preprocessing beseitigen oder reduzieren. Man könnte beispielsweise das Bild entrauschen oder Kanten schärfen. Auch eine Nachbearbeitung kann Segmentierungsprobleme beseitigen helfen. So könnte man falsch segmentierte Pixel nachkorrigieren.

Das Schwellwertverfahren ergibt nicht automatisch zusammenhängende Segmente, bei stärkerem Rauschen wird man fast immer einzelne Pixel heraussegmentieren.

Das Schwellwertverfahren nutzt immer nur eindimensionale Bildinformationen (beispielsweise den Grauwert). Zusätzliche Informationen (verschiedene Farbkanäle) werden nicht ausgewertet.

Einige Probleme kann man vermeiden, indem man andere, teilweise komplexere, Verfahren zur Segmentierung nutzt.

Anwendungen

Das Schwellwertverfahren eignet sich sehr gut zur schnellen Binarisierung (Trennung von Objekten und Hintergrund) von gleichmäßig ausgeleuchteten Bildern (Scans). Dies bedeutet beispielsweise eine gute Eignung für den ersten Schritt einer Schrifterkennung.

Als Bearbeitungsfunktion ist es in viele Bildbearbeitungsprogramme eingearbeitet, so z. B. in GIMP und IrfanView.

Referenzen

Literatur

Thomas Lehmann, Walter Oberschelp, Erich Pelikan, Rudolf Repges: Bildverarbeitung für die Medizin, Springer-Verlag Berlin Heidelberg, 1997, ISBN 3-540-61458-3
Bernd Jähne: Digitale Bildverarbeitung, 5., überarbeitete und erweiterte Auflage, Springer-Verlag, 2002, ISBN 3-540-41260-3
Rafael C. Gonzalez, Richard E. Woods: Digital Image Processing, Addison-Wesley Publishing Company, 1992, ISBN 0-201-50803-6 (englisch)
N. Otsu, "A threshold selection method from grey level histograms", IEEE Trans. System Man and Cybernetics, Vol. 9,1979

Weblinks