Schwellenwertverfahren

Die Schwellenwertverfahren 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 Schwellenwertverfahren kann man in einfachen Situationen entscheiden, welche Bildpunkte gesuchte Objekte darstellen und welche deren Umgebung angehören. Schwellenwertverfahren führen zu Binärbildern.

Einführung

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

Wie bei allen Segmentierungsverfahren werden auch bei den Schwellenwertverfahren 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 Schwellenwert 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 Schwellenwertverfahren ein so genanntes pixelorientiertes Segmentierungsverfahren.

Schwellenwertverfahren 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. Schwellenwertverfahren 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 (beispielsweise Schwellenwertverfahren) → 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. Schwellenwertverfahren 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 Schwellenwertverfahren 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 Schwellenwertverfahren 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 Schwellenwert t (englisch threshold bedeutet „Schwellenwert“). 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_{\text{global}}$ lautet:

T_{\text{global}}(g)={\begin{cases}0&{\text{falls }}g<t\\1&{\text{falls }}g\geq t\end{cases}}

Die Schwellenwertverfahren 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 Schwellenwertverfahren 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 Schwellenwertes stark schwanken.

Varianten

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

Beim globalen Schwellenwertverfahren wird ein Schwellenwert 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.

Schwellenwertverfahren 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 Schwellenwerte lässt sich das globale Verfahren so variieren, dass die Segmentierung mehr als zwei Segmente liefert. Für n Segmente werden dabei (n-1) Schwellenwerte t_i benötigt:

T_{{\text{global}}_{n}}(g)={\begin{cases}0&{\text{falls }}g<t_{1}\\1&{\text{falls }}t_{1}\leq g<t_{2}\\\vdots &\vdots \\n&{\text{falls }}g\geq t_{n-1}\end{cases}}

Beim lokalen Schwellenwertverfahren wird das Ausgangsbild in Regionen eingeteilt und der Schwellenwert für jede Region getrennt festgelegt. Das bedeutet, dass in jeder Bildregion R_i ein passender Schwellenwert 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_{\text{lokal}}(x,y)={\begin{cases}0&{\text{falls }}g(x,y)<t_{i}\\1&{\text{falls }}g(x,y)\geq t_{i}\end{cases}}\quad \forall (x,y)\in {\text{Region }}R_{i}

Gegenüber dem globalen Schwellenwertverfahren 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 Schwellenwert zu wählen. Ein automatisches Verfahren zur Wahl des Schwellenwertes ist daher ratsam.

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

T_{\text{dynamisch}}(x,y)={\begin{cases}0&{\text{falls }}g(x,y)<t(N(x,y))\\1&{\text{falls }}g(x,y)\geq 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 Schwellenwert berechnet wird.

Beispiel

Rauschbild
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 Schwellenwertes 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 Schwellenwertverfahren segmentiert, zur Demonstration des Verfahrens wurde das Ergebnisbild für vier verschiedene Schwellenwerte 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 Schwellenwert wurden schwarz eingefärbt, alle Pixel mit Grauwerten größer oder gleich dem Schwellenwert dementsprechend weiß.

Segmentierung mit unterschiedlichem Schwellenwert
Schwellenwert 30
Schwellenwert 52
Schwellenwert 204
Schwellenwert 230

Bei seiner Segmentierung mit dem Schwellenwert 30 werden mehrere dem Objekt zugehörigen Pixel weiß eingefärbt, also zum Hintergrund segmentiert. Der Schwellenwert wurde also zu niedrig gewählt.

Mit den beiden Schwellenwerten 52 und 204 ergeben sich recht ordentliche Ergebnisse. Dies gilt auch für alle Schwellenwerte zwischen diesen beiden Werten. Der Unterschied ist darin erkennbar, dass das Objekt mit zunehmendem Schwellenwert leicht größer wird. Die Wahl des Schwellenwertes 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 Schwellenwert 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 Schwellenwertes

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

Sowohl zur manuellen als auch zur automatischen Festlegung eines Schwellenwertes ist das Histogramm das wichtigste Hilfsmittel. Lokale Maxima weisen auf die Grauwerte oder 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 Schwellenwert zu wählen. Eine weitere, einfache Herangehensweise ist es, den Grauwert des Minimums zwischen den Maxima als Schwellenwert 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 Schwellenwert auf alle diese Bilder anwenden.

Eines der etwas anspruchsvolleren Verfahren zur automatischen Bestimmung von Schwellenwerten 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 Schwellenwertes 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 Schwellenwert, 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 Schwellenwert gesucht, bei dem dieser möglichst groß (maximal) wird.

Mathematische Darstellung

Als Ausgangspunkt dienen zwei Klassen von Punkten ( $K_{0}(t)$ und $K_{1}(t)$ ), die aufgrund des gesuchten Schwellenwertes $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 Schwellenwert (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_{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 Schwellenwert) 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 Schwellenwert $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 Schwellenwert bestimmt wird, so teilt dieser die Punktmengen entsprechend der Varianz in optimale Klassen.

Probleme

Helligkeitsprobleme
Das Bild mit einem Helligkeitsverlauf, …
… das zugehörige Histogramm (lineare Skalierung)…
… und das Ergebnis der Segmentierung mit dem Schwellenwert 127.

Das globale Schwellenwertverfahren 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 Schwellenwert 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 Schwellenwertverfahren 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 Schwellenwerte falsch berechnet werden. Wenn es beispielsweise drei Objekte (und den Hintergrund) im Bild zu erkennen gibt, werden drei Schwellenwerte gewählt, um die vier Klassen voneinander zu trennen. Tauchen in einer Region aber nur zwei der drei Objekte auf, dann kann der dritte Schwellenwert 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 Schwellenwertverfahren nicht automatisch zusammenhängende Segmente, bei stärkerem Rauschen werden fast immer einzelne Pixel heraussegmentiert.

Die Schwellenwertverfahren nutzen immer nur eindimensionale Bildinformationen (üblicherweise einen Intensitätswert oder 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 Schwellenwertverfahren eignen sich sehr gut zur schnellen Binarisierung (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, ImageJ und IrfanView.

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

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. 5. Auflage. Springer, Berlin 2002, ISBN 3-540-41260-3.
Rafael C. Gonzalez, Richard E. Woods: Digital Image Processing. Addison-Wesley, Reading MA 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 (PDF; 900 kB)

Einzelnachweise

↑ Survey over image thresholding techniques (Memento des Originals vom 23. Juni 2006 im Internet Archive) Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2 (englisch; PDF; 3,0 MB)

[Schwellenwertbestimmung-1] Survey over image thresholding techniques (Memento des Originals vom 23. Juni 2006 im Internet Archive) Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2 (englisch; PDF; 3,0 MB)

[1]