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:
- die Klassifikation lokaler Merkmalsvektoren (z. B. Farbvektoren) entsprechend Punkt 4
- die Identifikation von Ausreißerpunkten im Sinne von Merkmals- und Ortsraum
- 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