Auf Rückkopplung basierte Fuzzy-Algorithmen zur Bildanalyse

Josef Richardt, Gesellschaft zur Förderung angewandter Informatik (GFaI), Berlin

1 Einleitung

Unter einem Algorithmus wird nachfolgend nicht nur eine "Berechnungsvorschrift" verstanden (dies ist die klassische Definition), sondern ein Algorithmus ist hier eine C++-Klasse: er umfaßt sowohl die Daten, ohne die er nicht definiert werden kann, als auch mehrere Funktionen, welche einzelne Berechnungsprozeduren, d.h. Teilschritte im Rahmen des gesamten Algorithmus darstellen. Da die rückkopplungsbasierten Modelle Iterationsverfahren beinhalten, gibt es immer ein Zusammenspiel mehrerer Berechnungsschritte, während derer man Steuerparameter ändern kann. Insofern existiert in der Tat, was den prozeduralen Ablauf eines Algorithmus betrifft, kein fester Algorithmus. Fest definiert sind die einzelnen Berechnungsschritte, deren Zusamenspiel im Rahmen der Behandlung von Anwendungsdaten ist aber variierbar. Diese Variierbarkeit ist sogar eine von der Anwendung mit Nachdruck geforderte Eigenschaft, denn die Algorithmen sollen "adaptiv" sein, d. h. seine Steuerparameter sollen abhängig von den Besonderheiten der Anwendungsdaten änderbar sein. Aus den genannten Gründen wurde in der Entwicklungsarbeit des GFaI/Fuzzy-Projektes die objektoriente Methode gewählt. Sie erlaubt es, eine Hierarchie von Algorithmen aufzubauen, indem zunehmend komplizierte Algorithmen auf einfacheren aufbauen. Die Konzepte der Vererbung und der Klassentemplates bieten hierfür eine wesentliches Instrumentarium. Das Aufbauen einer Hierarchie von Algorithmen hat mit der prozeduralen Auffassung von Algorithmen nur noch wenig zu tun.

2 Fuzzy C-Means-Verfahrens (FCM) für die Bildanalyse

Als erster Schritt wurde der FCM-Algorithmus in der Form implementiert, wie er aus der Fuzzy- Datenanalyse bekannt ist. Seine Daten sind eine Menge von Merkmalsvektoren, denen bestimmte Gewichte zugeordnet sind. Ziel ist eine Klassifikation dieser Merkmalsvektoren entsprechend einer Zielfunktion [3,4]. Da die Dimension und der Datentyp der Vektoren (Byte, Integer, Float) variierbar ist, wurden die grundlegenden Berechnungsschritte als Klassentemplate formuliert. Mit diesem einheitlichen Template, das die mathematischen Berechnungsschritte ausdrückt, wird der Algorithmus für alle Datentypen gemeinsam formuliert. Das Template wird dann in der Anwendung auf einen konkreten Datentyp instanziiert. Abhängig vom Kontext wird dieser Grundalgorithmus immer wieder auf eine andere Art eingesetzt.

In der nächsten Ausbaustufe wurde eine globale Parametersteuerung implementiert. Diese führt einen weiteren Typ von Rückkopplung ein: zwischen dem zuvor abgebildeten Iterationsverfahren und der dazugehörigen Parametersteuerung, die abhängig von Diagnoseparametern, d. h. einer Bewertung des erreichten Zustandes, neue Steuerparameter (z. B. für die Unschärfesteuerung) einführt .

Das damit gegebene Grundschema läßt sich über die konkreten Formeln des FCM hinausgehend einführen als ein allgemeines Verfahren der Bildanalyse. Diese Verallgemeinerungen sind der Sinn der nachfolgend zu erläuternden Punkte. Dabei stellen die Merkmale M zu detektierende Merkmale eines Bildes dar und die Zugehörigkeiten Z(p) sind z. B. Zugehörigkeiten der Pixel (denen sich auch lokale Merkmalsvektoren zuordnen lassen, siehe dazu 4). Diese beiden Seiten stehen in der Realität immer in einer Wechselbeziehung.

3 Anwendung des FCM auf Histogramme (Farbklassifikation)

In der Farbklassifikation bedeuten die zu klassifizierenden Merkmalsvektoren dreidimensionale Vektoren aus dem RGB-Farbraum; die ihnen zugeordneten Gewichte bedeuten die Häufigkeit des Auftretens im Bild. Diese Datenstruktur ist ein Farbhistogramm. Man erhält ein Grauwert-Histogramm, wenn man sich auf Grauwertbilder beschränkt (die Dimension der Farbvektoren ist hier nicht 3, sondern 1). Für beide Fälle wurde der FCM implementiert und getestet. Dabei wurde die dem Verfahren immanente Unschärfesteuerung so eingesetzt, daß die Eindeutigkeit der Klassifikation (Zuordnung der Pixel zu den Farbklassen) stetig reguliert werden kann. Im Falle eines Grauwertbildes bewirkt dies eine Kontrastmodifikation. Beim Farbbild wird mit der Unschärfesteuerung der Übergang vom Ursprungsbild zu einem Bild, das nur noch eine bestimmte Zahl k >= 2 von Farben enthält, in stetiger Weise modifizierbar.

4 Anwendung des FCM auf bildinterne, lokale Merkmalsvektoren

Der Fall der Farbklassifikation war der einführende, einfachste Algorithmustyp (der sich auch schon praktisch nutzen läßt). Dies gehört aus der Sicht der Bildverarbeitung in das Gebiet der "Punktoperationen": Jeder Bildpunkt wird unabhängig vom Ort seines Auftretens verarbeitet. Natürlich ist dies ein Modell, daß sich erweitern läßt, indem auch räumliche Nachbarschaften beachtet werden. Der nächste Schritt war, jedem Bildpunkt einen lokalen Merkmalsvektor zuzuordnen, wobei dieser Merkmalsvektor in der Nachbarschaft des Bildpunktes gewonnen wird und diese Nachbarschaft sozusagen bewertet. Der allgemeine FCM-Algorithmus wurde dann auf diese Merkmalsvektoren angewendet. Erreicht wird damit eine Klassifikation der Bildpixel, in der bereits Wissen über Punktnachbarschaften einfließt. Hierbei sind - abhängig von der Anwendung - letztlich beliebig viele Merkmalsextraktoren möglich, die dem Algorithmus geeignete Daten zur Klassifikation anbieten. Getestet wurde das Verfahren zunächst mehrere Formen von lokalen Grauwert-Histogrammen.

5 Vergleich von Histogrammen mit Fuzzy-Histogrammen

Das genannte Verfahren wurde untersucht an von Testbildern, in denen sich verschiedene Bildregionen unsichtbar für das menschliche Auge nur durch das lokale Histogramm unterscheiden. Dabei ließen sich diese Regionen sehr präzise detektieren, wenn Fuzzy-Histogramme als lokale Merkmalsvektoren benutzt wurden. Die Fuzzy-Histogramme waren den konventionellen Histogrammen eindeutig überlegen. Das läßt sich auf ihr Verhalten bei der Datenreduktion zurückführen. Die Datenreduktion aller Grauwerte im Bereich eines Bytes 0...255 kann z. B. vier gleichlange Segmente bilden (0...63, 64...127, 128...191, 192...255), in die jeder beliebige Grauwert eingeordnet wird. Bei einer scharfen Zuordnung der Grauwerte in genau eines dieser Segmente entstehen an den Segmentgrenzen große Kachelungseffekte. Das heißt, eine nur kleine Verschiebung des Histogrammes (etwa vom Grauwert 62 nach 64) kann einen großen Sprung im vergröberten, auf vier Werte reduzierten Histogramm bewirken. Das Fuzzy-Histogramm dient dazu, eine solche Unstetigkeit zu vermeiden. Hier würden also die Grauwerte 62 und 64 beiden Segmenten, zu denen sie eine hohe Nähe haben, anteilig zugeordnet. Dies wird modelliert durch Fuzzy-Zugehörigkeitsfunktionen. Es handelt sich hierbei nur um einen Sonderfall des allgemeinen Multiresolutions-Prinzips. Dieses wird nicht nur bei einer vergröberten Abtastung des Wertebereiches 0...255 angewendet, sondern bei der Abtastung der ganzen Bildebene in x,y-Koordinaten. Einerseits ist dabei eine Datenreduktion aus Effektivitätsgründen unbedingt nötig , das heißt, der Wertebereich muß auf wenige Stützstellen reduziert werden. Andererseits muß diese Datenreduktion das enthalten, was intendiert ist: ein unscharfes Abtasten des Wertebereiches.

6 Integration des Fuzzy-Filter-Prinzips im Merkmalsraum

Der Fuzzy-Filter ist ein Verfahrensprinzip, welches darauf basiert, mit Hilfe von Fuzzy- Zugehörigkeiten die Punkte auszufiltern, die bei der Detektion von Merkmalen aus dem Rahmen fallen, d. h. Ausreißerpunkte sind. Das Rückkopplungsprinzip ist vom Schema her ähnlich wie beim FCM. Dieses Rückkopplungsprinzip wurde mit dem FCM-Verfahren in einem gemeinsamen Verfahren vereinigt. Das heißt, die Klassifikation von Punkten als Störung wurde unmittelbar aus dem FCM gewonnen: Ausreißer sind die Punkte, die zu weit von den Merkmalen, die der FCM benutzt (Klassenmittelpunkte) entfernt sind. Im Resultat ergab sich ein deutlich verbessertes FCM-Verfahren. Zum Beispiel wurden bei der Farbklassifikation die Farbklassen genauer als bisher bestimmt (sie werden nämlich nicht mehr von Störungen abgefälscht, wenn die Störungen aus dem Verfahren eliminiert werden). Allerdings tritt bei diesem Ansatz nun eine neue Klasse von Punkten auf: die als "Störung" klassifizierten Punkte. Der Mensch erkennt solche Punkt mit dem Auge. Es ist durchaus angemessen und im Sinne der Anwendung erwünscht, daß sie bei einer Bildanalyse eliminiert werden. Wenn z. B. in einer braunen Bildregion vereinzelte gelbe Punkte auftreten, dann ändern letztere nichts daran, daß es sich um eine braune Bildregion handelt.

7 Integration des Fuzzy-Filters im Ortsraum (Segmentierung)

Das zuletzt genannte Beispiel bezieht sich bereits auf den Ortsraum: Bildpunkte können im Sinne des Merkmalsraumes oder des Ortsraumes klassifiziert werden. Sobald beides gleichzeitig beachtet wird, betritt man das Gebiet der Segmentierung. Hierzu wurde das zuvor geschriebene Verfahren um eine neue Ausbaustufe erweitert, indem nun folgende Kriterien in einem Algorithmus vereinigt wurden:
  1. die Klassifikation lokaler Merkmalsvektoren (z. B. Farbvektoren) entsprechend Punkt 4
  2. die Identifikation von Ausreißerpunkten im Sinne von Merkmals- und Ortsraum
  3. die Zuordnung der Ausreißerpunkte entsprechend ihrer örtlichen Nähe.
Wenn dieser Algorithmus auf Farbvektoren angewendet wird, ergibt sich eine Farbsegmentierung. Dieser Algorithmus führte bei einer Reihe von Bildbeispielen zu Segmentierungsergebnissen, in denen sich zeigt, daß sich mit Hilfe des Rückkopplungsprinzips in der Tat eine höhere Adaptivität von Bildanalyse-Algorithmen erreichen läßt.

8 Literatur

[1] Richardt, J.: Neue Möglichkeiten durch das Konzept des nichtlinearen Fuzzy-Filters. In:: Anwendersymposium "Fuzzy Technologien und neuronale Netze" (Erfurt 13.-15-Dez. 1995), erschienen bei MIT-Management Intelligenter Technologien GmbH, Aachen, 232-237.
[2] Richardt, J.; Karl, F.; Müller, C.; Klette, R.: The Fuzzy Local-Global Duality inDetecting Pictorial Patterns. Pattern Recognition Letters 17, 1996, 187-195 .
[3] Richardt, J.; Nicklisch-Franken, J.; Klette, R.: A Generalized Fuzzy C-Means Algorithm with Applications to Contrast Modification and Binarization of Images. Computers and AI 15, 1996, 483-507.
[4] Richardt, J.; Karl, F.; Müller: Connections between Fuzzy Theory, Simulated Annealing, and Convex Duality. Fuzzy Sets and Systems: to appear 1998.

Das Projekt wird gefördert vom BMBF unter Reg.-Nr. 13N7003.



Udo Schwarz
Mon Mar 16 13:24:33 MET 1998