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. Der Grauwert eines Pixels ist sein reiner Helligkeitswert, ohne Berücksichtigung weiterer Farbinformationen. 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

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

Die Szene stellt dabei das reale beobachtete Objekt dar. Mit geeigneten Sensoren wird nun ein Bild aufgenommen. Das bedeutet üblicherweise, dass eine Fotografie gemacht wird, aber auch Radarabtastungen oder Röntgenbilder sind üblich. So oder so entsteht aus dem Schritt der Bildaufnahme ein Bild. Wenn die Aufnahme nicht in digitaler Form vorliegt, muss sie noch eingescannt werden, damit sie im Rechner weiterverarbeitet werden kann. Bei der Bildvorverarbeitung wird die Aufnahme verbessert, damit die folgenden Schritte effektiver durchgeführt werden können. Dies kann zum Beispiel eine Helligkeitskorrektur bedeuten, es könnten der Kontrast verbessert oder die Kanten geschärft werden. Welche Vorverarbeitung günstig ist, hängt von den konkreten Verfahren in den folgenden Schritten ab. Das Schwellwertverfahren beispielsweise ist anfällig für Helligkeitsänderungen im Bild, ein Helligkeitsausgleich kann daher günstig sein. Im Segmentierungsschritt werden die Pixel des Bildes in zusammengehörige Gruppen (Segmente) eingeteilt. Das Schwellwertverfahren ist eines dieser Segmentierungsverfahren. Bei der Merkmalsextraktion werden nun für diese Segmente bestimmte Eigenschaften bestimmt, beispielsweise Fläche, Exzentrizität der Form (eher rund oder eher länglich), mittlerer Farbwert oder andere. Mithilfe dieser Eigenschaften und einem vorher bestimmten Regelwerk kann nun in der Klassifikation jedes Segment in eine von mehreren Klassen eingeordnet werden. Durch eine Interpretation dieses Ergebnisses kann nun eine Aussage getroffen werden, zum Beispiel in der Texterkennung "Bei dem abgebildeten Objekt handelt es sich um den Buchstaben 'f' und keinen anderen".

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). Das Histogramm wird bestimmt, indem man die Häufigkeit jedes einzelnen Farbwertes bestimmt und durch eine entsprechend hohe Linie angibt. Als Legende ist daher unten ein Balken mit den verschiedenen Grauwerten zu sehen, darüber ist dann jeweils durch die Höhe der Linie die Anzahl der Auftritte des jeweiligen Grauwertes angegeben.

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. 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.

Das Verfahren von Otsu bestimmt einen Schwellwert, bei dem die Streuung innerhalb der dadurch bestimmten Klassen möglichst klein, zwischen den Klassen gleichzeitig aber möglichst groß ist. Dazu wird der Quotient zwischen den beiden Varianzen gebildet und ein Schwellwert gesucht, bei dem dieser möglichst groß (maximal) wird.

Es folgt eine mathematischere Darstellung des Algorithmus.

Als Ausgangspunkt dienen 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. Im folgenden wird nach dem Verfahren von Otsu ein Maß bestimmt, nach dem der Schwellwert (und damit die Klassen) optimiert werden kann.

Es 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 der 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)

Das 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. Daraus ergibt sich folgender Quotient:

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 das gesuchte Maß. Wenn durch die Maximierung des Quotienten ein Schwellwert bestimmt wird, 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 das 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