Musteranalyse

Musteranalyse ist ein Teilgebiet der Mustererkennung. Unter Musteranalyse wird die automatische Generierung einer Beschreibung aus dem Signal, dem Muster, verstanden. Beispiele für Muster sind Bilder, oder Bildfolgen und Sprachsignale. In der Musteranalyse wird nach Algorithmen und Systemansätzen für diese Problemstellung geforscht.

Im Gegensatz zu den Klassifikationsverfahren der Musterklassifikation, welche einem Muster als Ganzes eine von endlich vielen Klassen zuweist, wird in der Musteranalyse ein Muster in Untermuster zerteilt und diesen Untermustern und deren Beziehungen untereinander eine symbolische Beschreibung zugewiesen. Dies entspricht einer Abbildung aus der Menge der Untermuster in die unendliche Menge aller möglichen symbolischen Beschreibungen.

Typische Musteranalysesysteme

Im Gegensatz zum häufig homogenen Aufbau von Musterklassifikationssystemen, Spracherkennern oder Bilderkennern sind Musteranalysesysteme heterogen aufgebaut. Dennoch sind einige Basiskomponenten vorhanden, die meisten Systeme unterscheiden sich nur in deren Zusammenspiel.

Methoden

Unter der Methodenkomponente werden speziell auf die Verarbeitung von beispielsweise Sprachsignalen oder Bildern zugeschnittene Methoden, z. B. Kalman-Filter oder Snakes bei Bildern, zusammengefasst.

Qualitative Wissensrepräsentation

Um Wissen über die Anwendungsdomäne in einem automatischen Musteranalysesystem in einer effizienten und zugleich adäquaten Art und Weise zu repräsentieren, werden häufig Techniken aus der künstlichen Intelligenz eingesetzt, z. B. semantische Netze, Frames, PL1 etc. Dieses Wissen ist oft mehrdeutig, weshalb die Methoden eine gewisse Fehleranfälligkeit besitzen.

Erklärungskomponente

Beispiel aus der Medizin: Wird aus medizinischen Eingabedaten wie z. B. Röntgenbildern von einem Musteranalysesystem eine symbolische Ausgabe der Form „Patient X benötigt dringend Operation Y“ generiert, stellt sich dem Arzt (und dem Patienten) die Frage, warum diese Operation nötig ist und wie das Musteranalysesystem auf diese Antwort gekommen ist. Hier sind also Zwischenschritte gefragt. Diese Zwischenschritte und die nötigen Erklärungen, warum welcher Zwischenschritt erfolgte, werden durch die Erklärungskomponente geliefert.

Lernen

Die meisten Wissensbasen werden in aufwändiger und teurer Handarbeit menschlicher Experten erstellt und sind somit fehleranfällig. Unterschiedliche Experten generieren unterschiedliche Wissensbasen. Maschinelles Lernen ist somit durchaus angebracht, aber oft in der Realität nicht möglich.

Kontrollkomponente

Die Kontrollkomponente liefert die Kontrollstrategie, mit welcher das repräsentierte Wissen in der Wissensbasis verarbeitet wird. Bei der Verarbeitung kommen die speziellen Methoden aus der Methodenkomponente zum Einsatz. Die Strategie liegt oft in Form von Suche in Graphen, Bäumen oder andersartigen Suchräumen vor, beispielsweise mit dem A*-Algorithmus.

Beispiele zu Musteranalysesystemen

Ein komplettes Bildanalysesystem

Hier ist ein beispielhafter, kompletter Aufbau eines Bildverarbeitungs- und Analysesystems gegeben. Dieses ist grob in drei Teile geteilt: Bildverarbeitung, Bildklassifikation und Bildanalyse.

  1. Bildverarbeitung
    1. Quelle: Kamera (Digitalkamera, Camcorder), Scanner etc.
    2. digitalisiertes Bild: abgetastetes, quantisiertes Bild (z. B.: 1024×768 Grauwert Bild, Quantisierung: 8 Bit, also Grauwert 0 = schwarz und 255 = weiß)
    3. Vorverarbeitung: Normierung des Bildes, Anwendung von Filtern zur Rauschunterdrückung o. ä. (Bildrestaurierung).
    4. Segmentierung zur Unterteilung des Bildes in homogene Bereiche (gleiche Farbe, gleiche Textur etc.).
    5. Merkmalsextraktion: Zusammenfassen wichtiger Merkmale eines Bildes zu Merkmalsvektoren.
  2. Musterklassifikation
  3. Bildanalyse: Aufbauend auf der Musterklassifikation kann eine Bilderkennung (Relevant ist nur, was zu sehen ist, die Beziehungen der Objekte im Bild untereinander spielen keine Rolle) oder eine Bildinterpretation (nicht nur „Auto“ und „Mensch“ im Bild, sondern die Interpretation, dass das Auto den Menschen überfährt) stattfinden.

Das Bildverarbeitungssystem Optoluchs aus dem Jahr 1988 gehörte zu den ersten Systemen im Bereich Maschinelles Sehen.

Anwendungen von Bildanalyse

Ein komplettes Sprachanalysesystem

Hier ist ein beispielhafter, kompletter Aufbau eines Sprachverarbeitungs- und analysesystems gegeben. Dieses ist grob in zwei Teile geteilt: Spracherkennung und Sprachverarbeitung/Sprachanalyse/Sprachverstehen.

  1. Spracherkennung:
    1. Abtastung des analogen Sprachsignals meist mit 8 oder 16 kHz, 12 - 16 Bit Quantisierung pro Abtastwert.
    2. Vorverarbeitung: Rauschfilter, Entfernung von Abschnitten reiner Stille oder von Hintergrundgeräuschen o. ä.
    3. Merkmalsberechnung: Fensterbildung (per Fensterfunktion): Z. B. wird alle 10 ms ein 16 ms langes Fenster gebildet (Überlappung ist gewollt), auf welchem z. B. per cepstraler Analyse oder per Linearer Vorhersage (LPC, Linear Predictive Coefficients, siehe Lineare Vorhersage) Merkmale berechnet und zu Merkmalsvektoren zusammengefasst werden. Während der Merkmalsberechnung findet oft noch eine gehörrichtige Verzerrung des Signals statt (siehe Psychoakustik, MFCC, Mel-Skala, Bark-Skala und Ohr).
    4. Klassifikation und Suche: Zuordnung von Merkmalsvektorfolgen zu Polyphonen oder Wörtern per Hidden Markov Modelen (HMM). Es wird ein Wortgraph oder eine Liste der n-besten Wortketten erstellt.
    5. Spracherkennung: die eigentliche Spracherkennung, also die textuelle Repräsentation als Rekonstruktion des wirklich Gesagten, findet als Verbund von akustischem Modell (HMM) und Sprachmodell (oft N-Gramme) statt
  2. Sprachverarbeitung/Sprachanalyse:
    1. Prosodieerkennung: gibt Hinweise auf prosodische Merkmale der Sprache, wie Intonation, Akzent oder Rhythmus. Diese Informationen sind nützlich in weiteren, aufbauenden Analysen zur Auflösung von Mehrdeutigkeiten.
    2. syntaktische Analyse: liefert die geparste Äußerung (z. B. mittels LR-Parser).
    3. semantische Analyse: aufbauend auf der syntaktischen Struktur des Parsevorgangs, z. B. in Form eines Syntaxbaumes, findet eine Bedeutungsanalyse statt
    4. Pragmatik: Manchmal ist die Bedeutung eines Satzes nur unter Einbezug des Kontextes wirklich zu verstehen.
    5. Dialogsystem: Die interpretierte Äußerung kann nun einem Dialogsystem (z. B. eines Roboters) zugeführt werden, welcher dann fähig ist, per Sprachsynthese eine passende Antwort zu generieren.

Repräsentationmöglichkeiten von Wissen

Notwendige Voraussetzung für Musteranalysesysteme ist die explizite Repräsentation von Wissen. Im Gegensatz zur Künstlichen Intelligenz treten jedoch die Probleme unsicherer Eingabedaten und konkurrierender Hypothesen auf, so dass die Steuerung der Systemaktivitäten von großer Bedeutung ist. Neben KI-Methoden werden auch Datenbanksysteme zur Organisation von Wissen und zur Speicherung von Zwischenergebnissen betrachtet. Zur Bewertung von Hypothesen werden verschiedene Kalküle wie Fuzzy Logic oder Bayes'sche Netze benutzt.

Qualitative relationale Repräsentationsmöglichkeiten

Allgemeine Repräsentationsformalismen

Allgemein werden häufig semantische Netze eingesetzt, weil sich mit ihnen intuitiv und übersichtlich Wissensbasen aufbauen lassen. Weiterhin kommen oft Wissensrepräsentationssprachen wie KL-ONE, Frames oder Prädikatenlogik zum Einsatz.

Sprachdatenanalyse

Im Bereich der Sprachdatenanalyse werden häufig formale Grammatiken und Automaten eingesetzt. Beispielsweise kann die syntaktische Struktur von textuell repräsentierter Sprache mit einem LR-Parser effizient auf Korrektheit bezüglich einer LR Grammatik überprüft werden, in Kombination mit Merkmalsstrukturen zugleich auch die Kongruenz von Satzfragmenten bezüglich Kasus, Genus und Numerus per Unifikation.

Bilddatenanalyse

Eine spezielle (Sprach-) und Bilddatenanalysemethode bietet die semantische Netzwerksprache.

In der Bildverarbeitung werden attributierte Graphen benutzt, um 2D bzw. 3D Objekte zu repräsentieren. Arbeitet man z. B. auf einer regionenbasierten Segmentierung, so kann man die segmentierten Regionen als Knoten und die Beziehungen zwischen Regionen als Kanten im Graphen darstellen. Als Knotenattribut käme z. B. der Farbwert der Region und als Kantenattribut die Lagerelation wie "unterhalb-von" etc. in Frage. Graphen zu schon bekannten Objekten heißen Modellgraphen, je nach Szenario existiert eine mehr oder weniger große Anzahl an Modellgraphen. Ziel der Objekterkennung ist es nun, eines oder mehrere dieser Modellgraphen im segmentierten Bild zu finden. Ist das segmentierte Bild als Graph repräsentiert, so transformiert sich die Aufgabe zu einem Vergleich aller Modellgraphen mit dem Eingabegraph. Ist im Eingabegraph als Teilgraph ein Modellgraph enthalten, war die Suche erfolgreich. Mathematisch gesehen ist dies die Suche nach Subgraphisomorphismus mit Fehlerkorrektur.

Quantitative Repräsentation von Wissen

Hier setzt man numerische Klassifikatoren, Markov Random Fields und Bayes’sche Netze ein.

Kontrollstrategien

  • Heuristische Suche im Und-Oder-Baum
  • Heuristische Suche im Zustandsgraph
  • A*

Siehe auch

Literatur

  • G. Sagerer: Automatisches Verstehen gesprochener Sprache. (= Reihe Informatik. Band 74). B.I.-Verlag, Mannheim 1990, ISBN 3-411-14391-6.
  • P. C. Lockemann, J. W. Schmidt (Hrsg.): Datenbank-Handbuch. Springer, 1987, ISBN 3-540-10741-X.
  • H. Niemann: Pattern Analysis and Understanding. (= Springer Series in Information Sciences. Band 4). Berlin 1990, ISBN 3-540-51378-7.
  • A. Pinz: Bildverstehen. (= Lehrbücher der Informatik). Springer, Wien 1994, ISBN 3-211-82571-1.

Einzelnachweise

  1. ↑ Mobiler Preisvergleich mit Bilderkennung/Barcodeleser