Schwellwert-Algorithmus

Die Schwellwertverfahren sind eine Gruppe von Algorithmen zur Segmentierung digitaler Bilder. Segmentierung allgemein kann ein wichtiger Schritt zur Bildanalyse sein, beispielsweise um Objekte im Bild zu erkennen. Mit Hilfe von Schwellwertverfahren kann man in einfachen Situationen entscheiden, welche Bildpunkte gesuchte Objekte darstellen und welche deren Umgebung angehören. Schwellwertverfahren führen zu Binärbildern.

Einführung

Motivation für die Verwendung von Binärbildern ist meist die Verfügbarkeit schneller Binärbild-Algorithmen, z. B. zur Blobanalyse; die Speicherplatzersparnis spielt in Bildverarbeitungsanwendungen heute eine geringere Rolle.

Wie bei allen Segmentierungsverfahren werden auch bei den Schwellwertverfahren Bildpunkte – die so genannten Pixel – verschiedenen Gruppen – den so genannten Segmenten – zugeordnet. Das zu segmentierende Bild liegt dabei in Form von Zahlenwerten (ein oder mehrere Farbwerte pro Pixel) vor. Die Zugehörigkeit eines Pixels zu einem Segment wird durch den Vergleich des Grauwertes oder eines anderen eindimensionalen Merkmals mit einem Schwellwert entschieden. Der Grauwert eines Pixels ist sein reiner Helligkeitswert, weitere Farbinformationen werden nicht berücksichtigt. Da diese Operation meistens für jedes Pixel unabhängig angewendet wird, ist das Schwellwertverfahren ein so genanntes pixelorientiertes Segmentierungsverfahren.

Schwellwertverfahren gehören zu den ältesten Methoden in der digitalen Bildverarbeitung. Das bekannte, im gleichnamigen Abschnitt beschriebene Verfahren von Otsu wurde im Jahr 1979 von Nobuyuki Otsu publiziert. Es gibt jedoch noch ältere Publikationen zu diesem Thema. Schwellwertverfahren lassen sich aufgrund ihrer Einfachheit schnell implementieren und Segmentierungsergebnisse können mit geringem Aufwand berechnet werden. Die Qualität der Segmentierung ist im Allgemeinen jedoch schlechter als bei komplexeren Verfahren.

Einordnung

Eine Bildsegmentierung ist im Prozess des Maschinellen Sehens üblicherweise der erste Schritt der Bildanalyse und erfolgt nach der Bildvorverarbeitung. Der typische Ablauf in einem Bildverarbeitungssystem stellt sich folgendermaßen dar:

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

Die Szene stellt dabei ein oder mehrere reale, beobachtete Objekte dar. Mit geeigneten Sensoren wird ein Bild der Szene erzeugt, üblicherweise eine Fotografie oder eine Videoaufzeichnung. Im Prinzip kann aber jedes bildgebende Verfahren als Bildquelle dienen, so dass beispielsweise auch Radarabtastungen oder Röntgenaufnahmen in Frage kommen. Sollte das Bild nicht in digitaler Form vorliegen, so muss es zum Beispiel durch Scannen zuvor digitalisiert werden, um es im Rechner weiterverarbeiten zu können.

Bei der Bildvorverarbeitung wird das Bild dahingehend verbessert, dass 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 Vorverarbeitungsoperationen günstig sind, hängt von den konkreten Verfahren in den folgenden Schritten ab. Schwellwertverfahren sind im Allgemeinen anfällig für Helligkeitsänderungen im Bild, ein Helligkeitsausgleich kann daher von Vorteil sein.

Im Segmentierungsschritt werden die Pixel des Bildes in Segmente eingeteilt, wofür beispielsweise ein Schwellwertverfahren zum Einsatz kommt. Bei der darauf folgenden Merkmalsextraktion werden für jedes Segment bestimmte Eigenschaften – die so genannten Merkmale – bestimmt. Welche Merkmale das sind, hängt sehr stark vom Einzelfall ab. Als Beispiele seien die Fläche, die Exzentrizität der Form oder der mittlere Farbwert genannt.

Mithilfe der Merkmale und einem vorher bestimmten Regelwerk oder einem bereits zuvor trainierten Klassifikator kann nun bei der Klassifikation jedes Segment in eine von mehreren Klassen eingeordnet werden. Durch eine Interpretation dieses Ergebnisses kann abschließend 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 binarisieren die Schwellwertverfahren ein Ausgangsbild, das heißt es werden genau zwei Segmente gebildet – im wohl häufigsten Anwendungsfall für diese Verfahren idealerweise der Hintergrund und die gesuchten Objekte. Die Zuordnung zu den beiden Segmenten (0 und 1) erfolgt aufgrund eines Vergleiches des Grauwerts g des betrachteten Pixels mit dem zuvor festgelegten Schwellwert t (englisch threshold bedeutet „Schwellwert“). Das Ergebnisbild lässt sich also mit sehr geringem Rechenaufwand berechnen, da pro Pixel nur eine einfache Vergleichsoperation durchgeführt werden muss. Die zugehörige Berechnungsvorschrift der Abbildung T_global lautet:

$T_{global}(g) = \begin{cases} 0& \mbox{falls } g < t \\ 1& \mbox{falls } g \ge t \end{cases}$

Die Schwellwertverfahren sind so genannte vollständige Segmentierungsverfahren, das heißt jedes Pixel wird zwingend einem Segment zugeordnet. Ebenso sind sie überdeckungsfrei, es wird also kein Pixel mehreren Segmenten zugeordnet. Im Gegensatz zu vielen anderen Segmentierungsverfahren bilden die Schwellwertverfahren keine zusammenhängenden Segmente. Es ist durchaus vorstellbar und oft auch gewollt, dass mehrere räumlich getrennte Objekte im Bild, die einen ähnlichen Helligkeitswert aufweisen, zu einem Segment zusammengefasst werden. In der Praxis kommt es auch regelmäßig zu Falschsegmentierungen einzelner Pixel inmitten von Objekten, was beispielsweise auf Bildrauschen im Ausgangsbild zurückzuführen ist. Die Größe der segmentierten Objekte kann je nach Wahl des Schwellwertes stark schwanken.

Varianten

Unabhängig von der Wahl des Schwellwertes (wie im gleichnamigen Abschnitt weiter unten beschrieben) kann das grundlegende Prinzip der Schwellwertverfahren auf verschiedene Arten angewendet werden.

Beim globalen Schwellwertverfahren wird ein Schwellwert global für das gesamte Bild gewählt. Die zugehörige Berechnungsvorschrift wurde bereits im Abschnitt Eigenschaften weiter oben angegeben. Das Verfahren ist am einfachsten zu berechnen, aber auch sehr anfällig für Helligkeitsveränderungen im Bild.

Schwellwertverfahren mit globaler Schwelle werden deshalb in Industrieanwendungen nur bei kontrastreichen Bildern erfolgreich eingesetzt. Solche Bilder entstehen beispielsweise beim Abtasten von Schriftvorlagen oder bei Bildaufnahmen im Durchlicht.

Durch die Festlegung mehrerer Schwellwerte lässt sich das globale Verfahren so variieren, dass die Segmentierung mehr als zwei Segmente liefert. Für n Segmente werden dabei (n-1) Schwellwerte t_i benötigt:

$T_{global_n}(g) = \begin{cases} 0& \mbox{falls } g < t_1 \\ 1& \mbox{falls } t_1 \le g < t_2 \\ \vdots& \vdots \\ n& \mbox{falls } g \ge t_{n-1} \end{cases}$

Beim lokalen Schwellwertverfahren wird das Ausgangsbild in Regionen eingeteilt und der Schwellwert für jede Region getrennt festgelegt. Das bedeutet, dass in jeder Bildregion R_i ein passender Schwellwert t_i gewählt werden kann, ohne dass dies die Qualität der Segmentierung in anderen Regionen beeinflusst. Die Berechnungsvorschrift für jedes Pixel (x,y) lautet:

$T_{lokal}(x,y) = \begin{cases} 0& \mbox{falls } g(x,y) < t_i \\ 1& \mbox{falls } g(x,y) \ge t_i \end{cases} \quad \forall (x,y) \in \mbox{Region } R_i$

Gegenüber dem globalen Schwellwertverfahren steigt die Komplexität nur unwesentlich, das lokale Verfahren lässt sich daher ebenfalls mit geringem Rechenaufwand berechnen. Die Anfälligkeit gegenüber Helligkeitsveränderungen sinkt, allerdings kann es an den Grenzen der Regionen zu Versatz kommen. Abhängig von der Anzahl der Regionen kann der Aufwand schon zu hoch sein, durch einen Menschen für jede Region den passenden Schwellwert zu wählen. Ein automatisches Verfahren zur Wahl des Schwellwertes ist daher ratsam.

Als Weiterentwicklung des lokalen Verfahrens lässt sich das dynamische Schwellwertverfahren ansehen, das für jedes Pixel eine Nachbarschaft N betrachtet und auf Basis dieser Nachbarschaft einen passenden Schwellwert t(N) berechnet. Hierbei ist ein automatisches Verfahren zur Wahl des Schwellwertes zwingend notwendig. Die entsprechende Berechnungsvorschrift für jedes Pixel (x,y) lautet:

$T_{dynamisch}(x,y) = \begin{cases} 0& \mbox{falls } g(x,y) < t(N(x,y)) \\ 1& \mbox{falls } g(x,y) \ge t(N(x,y)) \end{cases}$

Die dynamische Variante ist recht stabil gegenüber lokalen Helligkeitsänderungen. Der Rechenaufwand steigt hier aber erheblich, da für jeden Bildpunkt ein neuer Schwellwert berechnet wird.

Beispiel

Ausgangsbild ...

... und das zugehörige Histogramm (logarithmische Skala).

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 der Wahl des zum Bild passenden Schwellwertes hilft das zugehörige Histogramm (auf der rechten Seite). In einem Histogramm wird die Häufigkeit jedes einzelnen Grauwertes durch eine entsprechend hohe Linie angegeben. Als Legende ist daher an der horizontalen Koordinatenachse ein Balken mit den verschiedenen Grauwerten abgebildet, darüber ist dann jeweils durch die Höhe der Linie die relative Häufigkeit des Vorkommens des jeweiligen Grauwertes angegeben.

Im Histogramm sind deutlich zwei Maxima zu erkennen: Das dunkle Objekt (linkes Maximum) und der helle Hintergrund (rechtes Maximum). Auch jeder Grauwert zwischen den beiden Maxima kommt offensichtlich im Bild vor, was durch das Rauschen im Bild und die weichen Objektränder verursacht wird, wo die Pixel schrittweise die verschiedenen Graustufen von Weiß bis Schwarz annehmen.

Das Ausgangsbild wurde mit dem globalen Schwellwertverfahren segmentiert, zur Demonstration des Verfahrens wurde das Ergebnisbild für vier verschiedene Schwellwerte berechnet. In den resultierenden Binärbildern mit je zwei Segmentgruppen wurde jedes Pixel entsprechend seiner Zuordnung zum Objekt oder zum Hintergrund schwarz (0) oder weiß (1) eingefärbt. Genauer: Alle Pixel mit Grauwerten kleiner als der Schwellwert wurden schwarz eingefärbt, alle Pixel mit Grauwerten größer oder gleich dem Schwellwert dementsprechend weiß.

Segmentierung mit Schwellwert 30

Segmentierung mit Schwellwert 52

Segmentierung mit Schwellwert 204

Segmentierung mit Schwellwert 230

Bei seiner Segmentierung mit dem Schwellwert 30 werden mehrere dem Objekt zugehörigen 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 mit zunehmendem Schwellwert leicht größer wird. Die Wahl des Schwellwertes hat also nicht nur Einfluss auf die Qualität der Segmentierung an sich, sondern auch auf die Größen der segmentierten Flächen. Grund für das Wachstum der Fläche sind die Pixel im Randbereich, die die Grauwerte von weiß nach schwarz schrittweise abdecken.

Der Schwellwert 230 segmentiert auch einige Hintergrundpixel als zum Objekt zugehörig. Das ist ein Anzeichen dafür, dass er zu groß gewählt wurde.

Wahl des Schwellwertes

Der springende Punkt bei allen Schwellwertverfahren ist die Wahl eines geeigneten Schwellwertes. Dieser kann durch einen menschlichen Bearbeiter sinnvoll gewählt werden. Da beim lokalen und dynamischen Schwellwertverfahren aber eine größere Anzahl an Schwellwerten benötigt wird, bietet es sich an, ein automatisches Verfahren zur Bestimmung der Schwellwerte einzusetzen. Natürlich kann auch der Schwellwert beim globalen Schwellwertverfahren automatisch bestimmt werden. Es gibt eine große Anzahl an konkreten Verfahren zur Wahl eines geeigneten Schwellwertes. ^[1]

Sowohl zur manuellen als auch zur automatischen Festlegung eines Schwellwertes ist das Histogramm das wichtigste Hilfsmittel. Lokale Maxima weisen auf die Grauwerte bzw. Grauwertbereiche hin, die im Bild vom Hintergrund oder von größeren Objekten angenommen werden. Im Idealfall ist das Histogramm bimodal, das heißt, es lassen sich zwei deutlich voneinander getrennte Maxima erkennen. Ein einfacher, aber auch fehleranfälliger Ansatz ist es, den Mittelwert zwischen den beiden Maxima als Schwellwert zu wählen. Eine weitere, einfache Herangehensweise ist es, den Grauwert des Minimums zwischen den Maxima als Schwellwert festzulegen. Hiermit würde wahrscheinlich schon eine etwas 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.

Eines der etwas anspruchsvolleren Verfahren zur automatischen Bestimmung von Schwellwerten ist das Verfahren von Otsu, das sich als Standard etabliert hat und im Folgenden vorgestellt werden soll.

Verfahren von Otsu

Das Verfahren von Otsu nach Nobuyuki Otsu aus dem Jahr 1979 verwendet statistische Hilfsmittel, um das Problem eines möglichst guten Schwellwertes zu lösen. Insbesondere wird von der Varianz Gebrauch gemacht, die ein Maß für die Streuung von Werten ist – 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.

Mathematische Darstellung

Als Ausgangspunkt dienen zwei Klassen von Punkten (K₀(t) und K₁(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 sich die Wahrscheinlichkeit des Auftretens von Pixeln der beiden Klassen mit:

K₀: $P_0(t)=\sum_{g=0}^t p(g)$ und K₁: $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})^2p(g)$ und $\sigma_1^2(t) = \sum_{g = t + 1}^{G}(g - \overline{g_1})^2p(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, ...

... das zugehörige Histogramm (lineare Skalierung)...

... 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: Das Ausgangsbild (links) wurde mit einem Helligkeitsverlauf versehen. Das Histogramm (mittleres Bild) ist nicht mehr bimodal, wie im Beispiel weiter oben, es lassen sich keine zwei deutlich voneinander getrennten Maxima ausmachen, sondern es gibt wesentlich mehr, recht kleine lokale Maxima. Das Ergebnisbild (rechts) der Segmentierung mit dem Schwellwert 127 zeigt sich uneinheitlich: Links oben werden ganze Hintergrundbereiche als Objekt segmentiert, während rechts unten das Objekt als Hintergrund erkannt wird. Nur im mittleren Bildbereich stimmt die Segmentierung in etwa.

Die Anwendung des lokalen oder sogar des dynamischen Schwellwertverfahren könnte hier das Segmentierungsergebnis verbessern. Allerdings ist besonders letzteres deutlich rechenaufwändiger. Außerdem muss darauf geachtet werden, dass in jeder Region alle zu segmentierenden Objekte vorkommen, ansonsten könnten die automatisch gewählten Schwellwerte falsch berechnet werden. Wenn es beispielsweise drei Objekte (und den Hintergrund) im Bild 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 alternative Lösung wäre es, die Helligkeit in einem Vorverarbeitungs-Schritt auszugleichen, beispielsweise mit einer Shading-Korrektur oder durch Verrechnung eines Referenzbildes.

Neben Helligkeitsverläufen können auch andere Bildfehler, die zu Problemen bei der Segmentierung führen können, bereits durch geeignete Bildvorverarbeitung beseitigt oder reduziert werden. Häufig eingesetzt werden das Entrauschen von Bildern oder das Schärfen von Kanten. Auch eine Nachbearbeitung kann Segmentierungsprobleme beseitigen helfen. So können falsch segmentierte Pixel durch Menschen oder durch geeignete Filterungen nachkorrigiert werden.

Im Gegensatz zu vielen anderen Segmentierungsverfahren ergeben sich bei den Schwellwertverfahren nicht automatisch zusammenhängende Segmente, bei stärkerem Rauschen werden fast immer einzelne Pixel heraussegmentiert.

Die Schwellwertverfahren nutzen immer nur eindimensionale Bildinformationen (üblicherweise einen Intensitätswert bzw. Grauwert). Zusätzliche Informationen, zum Beispiel verschiedene Farbkanäle, werden nicht ausgewertet.

Einige dieser Probleme können vermieden werden, indem andere, teilweise komplexere, Verfahren zur Segmentierung eingesetzt werden.

Anwendungen

Die Schwellwertverfahren eignen sich sehr gut zur schnellen Binärisierung (Trennung von Objekten und Hintergrund) von gleichmäßig ausgeleuchteten Bildern, beispielsweise Scans. Dies bedeutet beispielsweise eine gute Eignung für den ersten Schritt einer Texterkennung.

Als Bearbeitungsfunktion ist es in vielen Bildbearbeitungsprogrammen enthalten, so zum Beispiel in GIMP und IrfanView.

Schwellwertverfahren stellen auch Standardverfahren in der digitalen Bildverarbeitung dar und sind in jeder Programmbibliothek in diesem Bereich enthalten.

Quellenangaben

1. ↑ Survey over image thresholding techniques (englisch)

Literatur

• Thomas Lehmann, Walter Oberschelp, Erich Pelikan, Rudolf Repges: Bildverarbeitung für die Medizin. Springer, Berlin/Heidelberg 1997. ISBN 3-540-61458-3
• Bernd Jähne: Digitale Bildverarbeitung. Springer, Berlin ⁵2002. ISBN 3-540-41260-3
• Rafael C. Gonzalez, Richard E. Woods: Digital Image Processing. Addison-Wesley, Reading Mass 1992. ISBN 0-201-50803-6 (englisch)
• Nobuyuki Otsu: A threshold selection method from grey level histograms. In: IEEE Transactions on Systems, Man, and Cybernetics. New York 9.1979, S.62–66. ISSN 1083-4419

Weblinks

• Seminarvortrag zur Segmentierung