PatentDe  


Dokumentenidentifikation DE69330021T2 31.10.2001
EP-Veröffentlichungsnummer 0602932
Titel Verbessertes System zur Mustererkennung für Sonar und andere Anwendungen
Anmelder Raytheon Co., El Segundo, Calif., US
Erfinder Holmberg, Bart A., Bellevue, Washington 98005, US
Vertreter Kuhnen & Wacker Patentanwaltsgesellschaft mbH, 85354 Freising
DE-Aktenzeichen 69330021
Vertragsstaaten DE, FR, GB
Sprache des Dokument EN
EP-Anmeldetag 14.12.1993
EP-Aktenzeichen 933100661
EP-Offenlegungsdatum 22.06.1994
EP date of grant 14.03.2001
Veröffentlichungstag im Patentblatt 31.10.2001
IPC-Hauptklasse G06K 9/62

Beschreibung[de]
Hintergrund der Erfindung Gebiet der Erfindung

Die vorliegende Erfindung betrifft Mustererkennungssysteme. Genauer gesagt betrifft die vorliegende Erfindung Techniken zum Aufbau von Klassifizierern für Mustererkennungssysteme.

Beschreibung der einschlägigen Technik

In vielen Anwendungsfällen besteht Bedarf bezüglich der Fähigkeit, Muster in Datenproben zu erkennen. Beispielsweise besteht bei Sonaranwendungen über große Entfernungen die Notwendigkeit, Zielobjekte in einer Umgebung mit Hintergrundrauschen zu erkennen. Da eine Mustererkennung mit herkömmlichen, sequentiell arbeitenden Prozessoren schwierig zu erreichen ist, werden für diesen Anwendungsfall typischerweise Prozessoren mit neuralen Netzwerken (net) eingesetzt. Künstliche neurale Netzwerke verwenden eine Gruppe von verhältnismäßig einfachen Prozessoren in Parallelanordnung in großer Ähnlichkeit mit dem Gehirn. Die Prozessoren mit zugehörigen Nichtlinearitäten und Verbindungsgewichtungen bilden einen Klassifizierer, der einen Klassifizierungsalgorithmus verwirklichen kann. Der Klassifizierer bestimmt, von welcher Datenklasse eine Datenprobe mit größter Wahrscheinlichkeit gekommen ist. Zu diesem Zwecke muß der Klassifizierer trainiert oder geschult werden. Das Trainieren bedingt die Anwendung bekannter Daten auf einen Algorithmus, der die Klassifizierergewichtungen modifiziert.

Für viele Anwendungsfälle ist das Trainieren einer Klassifizierungseinrichtung schwierig, kritisch und teuer. Bei der Anwendung in aktiven Sonar-Systemen für große Entfernungen umfaßt beispielsweise das Trainieren der Klassifizierungsseinrichtung typischerweise die Verfolgung eines bekannten Zielobjektes, beispielsweise eines Unterseebootes, das Positionsdaten zu dem Verfolgungssystem überträgt. Diese Information bezüglich der Position des Zielobjektes dient zur Verarbeitung der von dem Sonar-Empfänger empfangenen Daten, wodurch Datenmerkmale entsprechend dem Hintergrundrauschen extrahiert werden. Diese extrahierten Datenmerkmale dienen zum Trainieren der Klassifizierungseinrichtung. Das Anpassen oder Trainieren der Klassifizierungseinrichtung macht es erforderlich, daß eine Bedienungsperson eine Darstellung des Zielobjektes über ein empfangenes dargestelltes Bild legt und von Hand Datenproben dahingehend klassifiziert, ob sie aus der Zielobjektklasse oder aus der Rauschsignalklasse kommen. Bei Tausenden von Datenpunkten für ein einziges Datenformat ist dieser Vorgang typischerweise zeitraubend und ziemlich teuer. In jedem Falle werden dann die so erhaltenen Daten dazu verwendet, die Klassifizierungseinrichtungen in den Sonar-Datenverarbeitungssystemen zahlreicher anderer Unterseeboote oder anderer mitgeführter Gruppensysteme in dem Flottenverband zu trainieren.

Während diese teurere Verfahrensweise in Anwendungsfällen annehmbar sein kann, in denen die Statistiken der unbekannten Datenklasse stationär sind, ist das Verfahren sehr beschränkt, wenn nicht sogar unbrauchbar, wenn die Statistiken extrem dynamisch sind, wie dies bei Anwendungsfällen von Sonar-Systemen für große Entfernungen der Fall ist.

Der herkömmliche Lösungsversuch bzgl. des Trainierens von Klassifizierungseinrichtungen für Mustererkennungssysteme ist daher durch die Notwendigkeit von Statistiken sowohl bei der bekannten Datenklasse als auch bei der unbekannten Datenklasse und durch die Notwendigkeit eines stationären statistischen Modells der Daten der unbekannten Datenklasse beschränkt.

Es besteht daher ein Bedarf auf diesem Gebiet der Technik an einer automatisierten Technik für den Aufbau von Klassifizierungseinrichtungen für nichtstationäre Datenklassen. Es besteht weiter Bedarf auf diesem Gebiet an einem Verfahren zum Trainieren einer Klassifizierungseinrichtung, welches nicht durch die Notwendigkeit von mehr als einer Datenklasse beschränkt ist.

Zusammenfassung der Erfindung

Der genannte Bedarf auf diesem Gebiet der Technik wird durch die vorliegende Erfindung befriedigt, durch welche ein verbessertes Mustererkennungssystem sowie ein entsprechendes Verfahren geschaffen werden, wie dies in den anliegenden Ansprüchen beansprucht ist. Die Erfindung arbeitet mit einer Mehrzahl von. Merkmalsvektoren aus einer einzigen Klasse von Datenproben. Das erfindungsgemäße System schätzt einen Umgrenzungsradius für die Merkmalsvektoren in der einzelnen Klasse von Datenproben ab und erzeugt daraus eine Austauschklasse, basierend auf dem geschätzten Umgrenzungsradius. Dieser Umgrenzungsradius dient zum Trainieren einer Klassifizierungseinrichtung, der seinerseits die Erkennung eines Datenmusters in Rohdaten erleichtert. Der Umgrenzungsradius wird basierend auf laufenden Ergebnissen von der Klassifizierungseinrichtung angepaßt.

Die Erfindung genügt dem dargestellten Bedarf auf diesem Gebiet der Technik durch Schaffung eines automatisierten Verfahrens zum Trainieren von Klassifizierungseinrichtungen für nichtstationäre Umgebungen, wobei das Verfahren nicht durch die Notwendigkeit von mehr als zwei Datenklassen begrenzt ist.

Kurze Beschreibung der Zeichnungen

Fig. 1 ist eine Darstellung zweier Unterseeboote, die bei einer herkömmlichen Trainingsübung für Klassifizierungseinrichtungen zusammenwirken.

Fig. 2 ist ein Blockschaltbild eines Sonar-Systems, das mit einem herkömmlichen Mustererkennungssystem ausgerüstet ist.

Fig. 3 zeigt ein Diagramm von Eingangs-Merkmalsdaten, welches für die Erläuterung der Wirkungsweise einer herkömmlichen Klassifizierungseinrichtung nützlich ist.

Fig. 4 ist ein Diagramm, das die Umgrenzungsausbildung einer herkömmlichen Klassifizierungseinrichtung darstellt.

Fig. 5 ist ein Blockdiagramm eines Sonar-Systems mit einem verbesserten Mustererkennungssystem nach der vorliegenden Erfindung.

Fig. 6a zeigt ein Blockdiagramm eines Traniningssystems nach der Erfindung für eine Klassifizierungseinrichtung in einem Trainingsmodus des Betriebes zum Auffinden von Klassifizierungsgewichtungen.

Fig. 6b zeigt ein Blockdiagramm eines Trainingssystems nach der vorliegenden Erfindung für eine Klassifizierungseinrichtung im Betrieb als adaptive Klassifizierungseinrichtung in der Anwendung für große Entfernungsbereiche.

Fig. 7a zeigt ein Diagramm eines zweidimensionalen Merkmalsraumes, wobei dieses Diagramm der Darstellung der vorliegenden Verfahrensweise dient.

Fig. 7b ist ein Diagramm eines zweidimensionalen Merkmalsraumes, wobei der Umgrenzungsradius und der mittlere Abstand zum nächsten Nachbarn gleich sind, da die Variante Null ist.

Fig. 7c ist ein Diagramm eines zweidimensionalen Merkmalsraumes, wobei der Umgrenzungsradius gleich dem mittleren Abstand zum nächsten Nachbarn plus einer Standardabweichung ist.

Fig. 8 ist ein Diagramm von Eingangs-Merkmalsdaten zur Erläuterung der vorteilhaften Wirkungsweise des Systems nach der vorliegenden Erfindung.

Fig. 9 ist ein Diagramm der Merkmalsdaten nach einer ersten Anzahl von statistischen Darstellungen von Eingangsdaten der Klassifizierungseinrichtung nach der vorliegenden Erfindung.

Fig. 10 ist ein Diagramm von Merkmalsdaten nach einer zweiten Anzahl von statistischen Darstellungen von Eingangsdaten für die Klassifizierungseinrichtung nach der vorliegenden Erfindung.

Beschreibung der Erfindung

Erläuternde Ausführungsbeispiele und Anwendungsbeispiele seien nun unter Bezugnahme auf die begleitenden Zeichnungen beschrieben, um die vorteilhaften Techniken gemäß der vorliegenden Erfindungen darzulegen.

Das herkömmliche Sonarsystem für große Entfernungen macht die Verwendung eines Mustererkennungssystems notwendig, um Zielobjektdaten von Hintergrunddaten unterscheiden zu können. Die Mustererkennung wird durch eine Klassifizierungseinrichtung erleichtert, welche die Daten entsprechend vorbestimmten Merkmalen längs einer Umgrenzung aussondert. Zu diesem Zwecke muß die Klassifizierungseinrichtung zuerst trainiert werden. Die herkömmliche Klassifizierer- Trainingstechnik sieht den Empfang von einer unbekannten Klasse (Hintergrundrauschen) und den Empfang von Daten einer bekannten Klasse (Zielobjektdaten) vor. In herkömmlicher Weise werden Daten von einer bekannten Klasse durch die Aussendung von Positionsdaten durch ein bekanntes Zielobjekt zu dem Verfolgungssystem hin erzeugt, während gleichzeitig Daten der unbekannten Klasse empfangen werden. In dem Anwendungsfall eines aktiven Sonar-Systems für große Entfernungen bedeutet dies beispielsweise den Einsatz von zwei Unterseebooten, wobei das eine Unterseeboot eine Verfolgung des anderen Unterseebootes vornimmt.

Fig. 1 ist eine Darstellung, welche zwei Unterseeboote zeigt, die sich bei einer Übung zum Trainieren einer herkömmlichen Klassifizierungseinrichtung befinden. Das verfolgenden U-Boot 1 sendet eine Sonarsignal aus, das von dem verfolgten U-Boot 2 zu dem verfolgenden U-Boot hin zurückgeworfen wird. Das verfolgte U-Boot 2 erhält seine Position beispielsweise von einem Satelliten 3 eines GPS-Systems und sendet seine Position zu dem verfolgenden U-Boot I entweder unmittelbar oder über eine nicht dargestellte Relaisverbindung. Das verfolgende U-Boot 1 empfängt die Sonar- Echosignale zusammen mit Echos von zahlreichen anderen Orten einschließlich der Meeresoberfläche 4 und des Meeresbodens 5. Diese Echos repräsentieren das Hintergrundrauschen für den Sonar-Empfänger des verfolgenden U-Bootes.

Fig. 2 ist ein Blockdiagramm des Sonar-Systems 10 des verfolgenden U-Bootes 1, wobei dieses System mit einem herkömmlichen Mustererkennungssystem ausgerüstet ist. Das System 10' enthält einen Sonar-Sender 11' und einen Sonar-Empfänger 12'. Der Empfänger 12' enthält eine phasengesteuerte Gruppe (phased array) von Sonar- Empfangselementen 14' sowie ein Strahlformungsnetzwerk 16', wie dies auf diesem Gebiet der Technik bekannt ist. Der Ausgang des Strahlformungsnetzwerkes 16' stellt ein Signal entsprechend dem erzeugten Strahl dar. Das Signal wird von einer Signalverarbeitungseinrichtung 18' verarbeitet, um Merkmalsrohdaten zu erzeugen. Die Signalverarbeitungseinrichtung 18' enthält typischerweise eine Reihe angepaßter Filter, Detektorschaltungen und Normalisierungsschaltungen. Ein Merkmalsextrahierer 20', der mit einer Klassifizierungseinrichtung (nicht dargestellt) ausgerüstet ist, wirkt auf die Merkmalsrohdaten ein, identifiziert Merkmale (Merkmalsvektoren) in den Datenproben und klassifiziert die Merkmale entsprechend einer Merkmalsumgrenzung oder einer Fläche in einer mehrdimensionalen Ebene. Die klassifizierten Merkmale werden in einen Diskriminator 22' eingegeben, der bemüht ist, Muster in den eingegebenen Daten zu erkennen. Die Merkmalsfläche wird anfänglich entsprechend bestimmten Parametern angelegt. Danach wird die Merkmalsfläche durch das herkömmliche Klassifizierer- Trainiersystem 24' aktualisiert. Das herkömmliche Klassifizierer-Trainiersystem 24' enthält eine Datenverarbeitungseinrichtung 26', welche Daten eines Musters von dem Diskriminator 22' und Positionsdaten von dem verfolgten U-Boot 2 (in der Zeichnung als "Quelle bekannter Datenklasse" 28' bezeichnet) empfängt und beide Daten auf einer Anzeigeeinrichtung 30' zur Darstellung bringt.

Gemäß der herkömmlichen technischen Lehre trainiert eine Bedienungsperson die Klassifizierungseinrichtung durch Prüfung der Darstellung und durch manuelles Klassifizieren der Daten in und um den bekannten Klassifizierungsraum. Die in dieser Weise trainierte Klassifizierungseinrichtung wird dann dazu verwendet, die Klassifizierungseinrichtungen anderer U-Boote zu trainieren.

Fig. 3 ist ein Diagramm von Eingangs-Merkmalsdaten, welches für die Erläuterung der Wirkungsweise einer herkömmlichen Klassifizierungseinrichtung bzw. einer herkömmlichen Klassifizierung nützlich ist. Die zwei Klassen sind "*" und "o", worin "o" die Klasse bekannter Daten repräsentiert. Beide Daten sind gleich, gleichförmig und statistisch innerhalb der optimalen und zunächst unerkannten kreisförmigen Umgrenzungen verteilt, wie dies in der Zeichnung dargestellt ist. Es sind 800 Probenvektoren von jeder Klasse vorhanden. Die größeren Kreise 34, 36 und 38 repräsentieren die Merkmalsvektoren von der bekannten Klasse und die kleineren Kreise 40, 42, 44 und 46 repräsentieren die Merkmalsvektoren von der unbekannten Klasse. Unter der Voraussetzung der beiden Klassen soll zur Erleichterung einer Mustererkennung eine Umgrenzung gefunden werden, welche die Klassen trennt.

Fig. 4 ist ein Diagramm, welches eine Umgrenzungsbildung der herkömmlichen Klassifizierungseinrichtung nach 560.000 ihr präsentierten simulierten Eingangs- Merkmalsdaten von Fig. 3 wiedergibt. Die Proben unterhalb der Begrenzung 48 wurden als in einer ersten Klasse liegend klassifiziert und die Proben oberhalb der Begrenzung 48 wurden als in der zweiten Klasse liegend klassifiziert. Es ist offenbar, daß in der Simulation die zu Erläuterungszwecken betrachtete herkömmliche Klassifizierungseinrichtung Merkmalsvektoren in den Umgrenzungskreisen 40 und 42 fehlklassifiziert hat. In diesem Beispiel bedeutet dies eine Fehlerrate der Klassifizierung bis zu 50%.

Zusätzlich zu der Empfindlichkeit bezüglich einer Fehlklassifizierung ist dieser herkömmliche Trainingsvorgang für Klassifizierungseinrichtungen ziemlich teuer, nachdem er es erforderlich macht, daß Daten einer bekannten Klasse erzeugt werden, nämlich durch Untersuchung und Verfolgung eines zweiten U-Bootes, und daß eine manuelle Klassifizierung der Merkmalsvektoren erfolgt. Demgemäß ist es besonders ungünstig, daß die Daten typischerweise nichtstationär sind. Dies hat zur Folge, daß die Klassifizierungseinrichtungen, die gemäß der bekannten Technik trainiert worden sind, oft nach dem Ablauf einer verhältnismäßig kurzen Zeitdauer stark ungenau werden. Folglich besteht Bedarf in der Technik an einer automatischen Verfahrensweise zum Trainieren von Klassifizierungseinrichtungen für nichtstationären Datenklassen, wobei das Verfahren nicht durch die Notwendigkeit von mehr als einer Klasse von Daten eine Beschränkung erleidet.

Diesem Bedarf genügt die vorliegende Erfindung, durch welche ein verbessertes Mustererkennungssystem geschaffen wird, welches mit einer Mehrzahl von Merkmalsvektoren von einer einzigen Klasse von Datenproben arbeitet. Das erfindungsgemäße System schätzt einen Umgrenzungsradius für die Merkmalsvektoren in der einzigen Klasse von Datenproben ab und erzeugt eine Austauschklasse daraus, basierend auf dem abgeschätzten Umgrenzungsradius. Dieser Umgrenzungsradius wird zum Trainieren einer Klassifizierungseinrichtung verwendet, die ihrerseits die Erkennung eines Datenmusters in Rohdaten erleichtert. Der Umgrenzungsradius wird auf der Basis gegenwärtiger Ergebnisse von der Klassifizierungseinrichtung angepaßt.

Fig. 5 ist ein Blockdiagramm eines Sonar-Systems mit dem verbesserten Mustererkennungssystem nach der vorliegenden Erfindung. Wie bei dem herkömmlichen System 10' enthält das erfindungsgemäße System 10 einen Sonar- Sender 11, einen Sonar-Empfänger 12, eine Signaleverarbeitungseinrichtung 18, einen Merkmalsextrahierer 20 und einen Diskriminator 22. Das erfindungsgemäße System unterscheidet sich jedoch von dem herkömmlichen System dadurch, daß der Trainierer 24' für die Klassifizierungseinrichtung ebenso entfällt, wie die Notwendigkeit einer Quelle von einer zweiten Klasse bekannter Daten und die Notwendigkeit einer Einwirkung einer Bedienungsperson. Der Trainer 24' für die Klassifizierungseinrichtung des herkömmlichen Mustererkennungssystem 10' entfällt aufgrund der Verwendung des neuartigen Klassifizierer-Trainingssystems nach der Erfindung.

Die erfindungsgemäße Klassifizierungseinrichtung verwirklicht ein binäres Klassifizierer-Trainingsverfahren.

Fig. 6a ist ein Blockschaltbild eines Trainingssystems für einen Klassifizierer nach der Erfindung im Trainingsbetrieb zum Auffinden von Klassifizierungsgewichtungen.

Das neuartige Klassifizierer-Trainingssystem 100 enthält eine Umgrenzungsradius-Abschätzeinrichtung 110, einen Austauschklassepgenerator 120, einen Rückausbreitungstrainer 130 und eine Klassifizierungseinrichtung 140. Fig. 6a zeigt, in welcher Weise die erfindungsgemäße Klassifizierungseinrichtung an einer einzigen Klasse von Merkmalen trainiert wird, um die Klassifizierungsgewichtungen aufzufinden.

Fig. 6b ist ein Blockschaltbild des Klassifizierer-Trainingssystems nach der vorliegenden Erfindung im Betrieb als adaptive Klassifizierungseinrichtung bei der Anwendung für große Entfernungen.

Das Verfahren zum Betrieb des Klassifizierer-Trainingssystems 100 umfaßt zwei Hauptteile. Der erste Teil umfaßt die Auswahl derjenigen der beiden Klassen, welche am leichtesten zu erhalten ist. Die andere Klasse wird dann durch eine Austauschklasse repräsentiert. Die Austauschklasse besteht aus zufälligen oder statistischen Merkmalsvektoren, welche von einer gleichförmigen Verteilung abgeleitet werden. Jedes Element der Austauschklasse besteht aus statistischen Merkmalsvektoren, welche von einer gleichförmigen Verteilung extrahiert werden. Jedes Element des Austauschklassenvektors ist dann eine statistische Variable, welche gleichförmig über den Bereich möglicher Werte des betreffenden Merkmals verteilt ist (beispielsweise, ein Merkmal n ist der Ausgang eines Photodetektors, dessen maximaler Ausgang 0,1 Volt ist).

Der zweite Teil umfaßt die Modifizierung der vollständig statistischen Austauschklasse mit der in der bekannten Klasse enthaltenen Information. Die Modifikation besteht in der Subtraktion des Raumes, der die bekannte Klasse enthält, von der Austauschklasse. Das Verfahren zur Durchführung dieses Schrittes umfaßt die Löschung sämtlicher Vektoren, welche von der Austauschklasse extrahiert worden sind, die sich in einer Hypersphäre eines Radius H einer Probe der bekannten Klasse befinden.

Die Statistik des Vorgangs der Löschung der Austauschvektoren, welche in den Raum der bekannten Klasse fallen, von der gleichförmigen Austauschklasse, wird für diese Problem unter der Annahme einer gleichförmigen, unabhängigen Statistik der bekannten Klasse abgeleitet. Diese geschieht anhand des Hypersphären-Radius H. Für Anwendungen in der reellen Welt ist die Annahme der Gleichförmigkeit und Unabhängigkeit bezüglich der bekannten Klassenverteilung möglicherweise nicht sehr genau. Da die Statistiken nicht für realistischere Modelle abgeleitet worden sind (beispielsweise ein gemeinschaftliches Gaus< sches Modell), ist ein arbeitshypothetisches Verfahren zur Bestimmung des Abstandes H folgendermaßen anzugeben.

Der Umgrenzungsradius H ist in Fig. 7a als der mittlere Abstand zwischen Tastungsproben in der bekannten Klasse dargestellt. Der Umgrenzungsradius kann nach einer von zwei Methoden bestimmt werden. Die erste Methode ist eine statistische Methode, durch welche der Radius H durch die Wahrscheinlichkeit des Auftretens einer Probe der Austauschklasse in dem Raum der bekannten Klasse ausgedrückt wird. Diese Technik benutzt starke Annahmen bezüglich der Art der Klassenverteilung und der Kenntnis darüber. Das zweite Verfahren macht keine Annahmen über die zugrundeliegenden Verteilungen, liefert aber keine schöne Beziehung zwischen dem Umgrenzungsradius und der Wahrscheinlichkeit des Hereinfallens einer Probe der Austauschklasse in den Raum der bekannten Klasse. Es hat jedoch einigen arbeitshypothetischen Reiz. Es sei auch bemerkt, daß ein Verlust an Umgrenzungsradius H auftritt. Wird dieser zu klein gemacht, dann bleiben Proben der Austauschklasse in dem Raum der bekannten Klasse. Wird H zu groß, dann paßt die Umgrenzungslinie, die die Klassifizierungseinrichtung auffindet nicht genau um den Raum der bekannten Klasse für Verteilungen des Gleichförmigkeitsfalles oder für eine Gauss'sche Verteilung; die Umgrenzung begünstigt den Raum der bekannten Klasse.

Das erste Verfahren zur Bestimmung des Umgrenzungsradius ist folgendermaßen anzugeben. Zuerst werden die folgenden Annahmen gemacht:

1) Der Umfang der Verteilung der bekannten Klasse ist bekannt oder kann abgeschätzt werden, und 2) die Verteilung der bekannten Klasse ist über ihren Umfang gleichförmig.

Fig. 7a ist ein Diagramm eines zweidimensionalen Merkmalsraumes, wobei dieses Diagramm nützlich für die Darlegung der Lehre nach der Erfindung ist. Die Verteilungen A, B und C sind dahingehend definiert, daß sie Umfänge oder Volumen VA, bzw. VB bzw. VC haben. Die Punktdichten λA, λB und λC sind gleich N/V definiert, worin N die Anzahl der Probenpunkten und V das Volumen sind. Das Ereignis C ist definiert als Anordnung einer Hypersphäre des Volumens VV beliebig innerhalb des Raumes, der durch Va eingenommen ist, wobei keine Probenpunkte von der Verteilung B in das Volumen VC fallen. Aus der Annahme der gleichförmigen Verteilung und dem Poisson'schen pdf ist die Wahrscheinlichkeit des Ereignisses oder Events C folgendermaßen anzugeben:

Pr{Event C} = e-λBVC [1]

Das Ereignis oder Event L ist als Anordnung von M Hypersphären vom Volumen VC in Zufallsverteilung innerhalb des Raumes definiert, der durch VB bestimmt ist. Keine der Sphären ist leer. Durch M-maligen Bernouilli'schen Ansatz erhält man:

Pr{Event L} = Pr{Event C}&sup0;(1-Pr(Event C))M [2]

Durch Vereinfachung erhält man:

Pr{Event L} = (l-e-λBVC)M [3]

Der Parameter M ist die erwartete Zahl von Austausch- Verteilungsprobenvektoren, welche in den Raum VB fallen. Daher ist M = λAVB.

Definiert man Pr(Event L) = α, dann kann das Volumen oder der Umfang der Hypersphäre in α ausgedrückt werden.

Der Umgrenzungsradius der Hypersphäre für den zweidimensionalen Fall ist also folgender:

H = (-log(1-elog(α)/(λAVB))/λBπ)1/2 [5]

Dies legt nahe, daß α auf eine hohe Wahrscheinlichkeit (d. h. 90%) eingestellt werden sollte, um sicherzustellen, daß sämtliche Proben der Austauschverteilung von dem Volumen der Verteilung A umgrenzt werden. Wenn irgendeine der Annahmen für die erste Methode nicht zutrifft (d. h., die zweite Annahme ist für Daten der realen Welt höchstwahrscheinlich ungültig), dann muß ein anderes Verfahren zur Bestimmung des Umgrenzungsradius verwendet werden. Das zweite Verfahren zur Bestimmung des Umgrenzungsradius macht keine Annahmen bezüglich der zugrundeliegenden Verteilungen und liefert keine direkte Beziehung zwischen dem Umgrenzungsradius H und der Wahrscheinlichkeit des Fehlens einer Austauschklassenprobe innerhalb einer Verteilung der Bekannten Klasse. Die zweite Methode zur Bestimmung des Umgrenzungsradius ist also folgende.

Zunächst sei Vk der k-te Merkmalsvektor der bekannten Verteilung. In der bekannten Probenverteilung gibt es N Merkmalsvektoren. Der Abstand zum nächsten Nachbar ist:

dk = min[ vk - vL ] [6]

für L = 1 bis M, ausgenommen für L = k. Der Probenmittelwert für den Abstand zum nächsten Nachbar ist:

Die Probenveränderung des Abstandes zum nächsten Nachbarn ist:

Für Darstellungszwecke sei angenommen, daß H = D und daß der Merkmalsraum zweidimensional ist. Weiter sei angenommen, daß die Proben der bekannten Verteilung an Gitterpunkten gelegen und beabstandet sind, wie in Fig. 7b und 7c gezeigt. Fig. 7b ist ein zweidimensionaler Merkmalsraum, bei welchem der Umgrenzungsradius und der mittlere Abstand zum nächsten Nachbarn gleich sind, da die Veränderung σD Null ist. In diesem Falle bleibt keine Fläche durch die Kreise unabgedeckt, die um die Punkte bekannter Proben gezogen sind. Die Kreise sind tatsächlich nur zu Darstellungszwecken eingezeichnet. Wenn alle Kreise um jeden Punkt in dem Gitter eingezeichnet werden, würden die Punkte mindestens durch zwei Kreise getroffen. Für eine statistische Verteilung von Punkten bekannter Proben ist die Veränderung oder Abweichung irgendeine positive Zahl. Begreiflicherweise sollte der Umgrenzungsradius um so größer sein, je größer die Veränderung ist. Um dies zu erreichen kann man den Umgrenzungsradius H gleich D + σ D setzen, wie dies in Fig. 7c gezeigt ist. Fig. 7c ist ein Diagramm eines zweidimensionalen Merkmalsraumes, wobei der Umgrenzungsradius gleich dem mittleren Abstand zum Nachbarn D plus der Standardabweichung σ D ist.

Es sei nun wieder Fig. 6a betrachtet. Nachdem der Umgrenzungsradius bestimmt ist, verwendet der Austauschklassengenerator 120 den Umgrenzungsradius, um eine Austauschklasse zu erzeugen. Die Austauschklasse von Daten ist gleichförmig über den Merkmalsraum verteilt, wobei der Raum der bekannten Klasse entfernt ist. Das Verfahren zur Erzeugung der gleichförmigen Austauschklasse und des Wegsubtrahierens des Raumes der bekannten Klasse verläuft folgendermaßen. Zuerst wird eine N-dimensionale Austauschklasse erzeugt. Dies kann mit einem Generator zur gleichförmigen Erzeugung von Zufallszahlen erreicht werden. Der Zufallszahlengenerator würde unabhängige Proben für jedes Merkmal, verteilt über den möglichen Bereich jedes Merkmals, erzeugen. Ist dies bewerkstelligt, so müssen diejenigen Austauschklassen-Probenvektoren beseitigt werden, die in den Raum der bekannten Klasse fallen. Dies erreicht man durch Beseitigen all derjenigen Proben aus der Austauschklasse, welche in den Umgrenzungsradius H für jeden Probenvektor in der bekannten Klassen fallen.

In dem erläuternden Ausführungsbeispiel können die Abschätzeinrichtung 110 für den Umgrenzungsradius und der Austauschklassengenerator 120 durch Software verwirklicht werden. Das folgende ist ein MATLAB M-File (Code) zum Auffinden des Umgrenzungsradius und der Austauschklasse:

Beispiel für einen Code für die Austauschklasse und den Umgrenzungsradius

Funktion y = get_radius (clut);

%

% Ergibt Abstand zum nächsten Nachbarn zwischen Merkmalsvektoren in x. x is N mal M-dimensional, worin N die Anzahl der Merkmale ist.

[lenx, wx] = size (clut)

für k = 1:lenx

i = 1;

für 1 = [1:k-1), (k+1): lenx]

diff = clut (k,:9)-clut(1,:);

d(i) = diff*diff;

i = I + 1;

Ende; % für

dis(k) = min(d);

wenn (rem(k,10)=),k,Ende;

Ende; % für

y = dis. (1/2);

Funktion y = cut_target (clut, num_targ, radius);

%

% Für jeden Rauschechopunkt oder Clutterpurikt wird, wenn irgendein Targetpunkt oder Zielobjektpunkt innerhalb eines Abstandes L liegt, dieser aus dem Eingang entfernt. Die Targets werden als gleichförmig über den Merkmalsraum verteilt definiert.

%

% clut - Clutter-Punkte

% num_targ - Zahl der Zielobjekte zur Erzeugung des Radius - Umgrenzungsradius für Hypersphäre

%

rand ("uniform")

rand ("seed", 1042345624);

num_vec = min(size(clut));

targets = ;

während Länge (targets) < num_targ;

t_targ = rand (roiund (num_targ/10), num_vec);

für k = 1:length (clut)

für 1 = 1:length (t_targ)

d1 = clut (k,:)-t_targ (1,1) = -inf; end;

wenn dl*dl' < (radius 2); t_targ(1,1) = -inf; Ende;

Ende; % für

Ende; % für

targets = [targets; t_targ(find(t_targ(:,1)~= -inf),:);

Ende; % während

y = targets;

Nachdem die beiden Klassen (die bekannte Klasse und die Austauschklasse) aufgefunden sind, muß eine Klassifizierungseinrichtung verwendet werden, um die Grenze zwischen den zwei Verteilungen aufzufinden. Die einzige Forderung an die Klassifizierungseinrichtung besteht darin, daß sie ausreichend verfeinert ist, um die bekannte Verteilung zu enthalten.

Eine beispielsweise Ausführungsform der künstlichen neutralen Netzwerk- Klassifizierungseinrichtung 140 nach der vorliegenden Erfindung sieht folgendermaßen aus, die Klassifizierungseinrichtung wird durch Software verwirklicht, wobei herkömmliche Techniken verwendet werden. Die Klassifizierungseinrichtung 140 enthält eine Eingangsschicht, die keine Verarbeitung vornimmt, sowie drei Schichten von Knoten, wobei die letzte Schicht von Knoten als die Ausgangsschicht zu bezeichnen ist. Es sind zwei Eingänge vorhanden (einer für jedes Merkmal), dann folgen fünf Knoten in der nächsten Schicht, zehn Knoten in der darauffolgenden Schicht und zwei Knoten in der Ausgangsschicht. Die Systemgleichungen lauten folgendermaßen:

kU = kwka [9]

und

(k+1)a=f(kU) l≤k≤M [10]

worin:

kW die (l+k)N mal kN-Gewichtungsmatrix ist, worin iN die Anzahl von Knoten in der Schicht i ist; lN ist die Anzahl der Eingangs-Merkmale und MN ist die Anzahl der Ausgänge;

iU ist der Ausgangs-Spaltenvektor der Schicht i; und

ia ist der Aktivierungswert-Spaltenvektor, der den Eingang zur Schicht i bildet; somit ist ia der Eingangs-Merkmalsvektor und l+Ma ist der Ausgang des Netzwerkes.

Gleichung 10 liefert nicht eine spezifische Funktion. In dem erläuternden Ausführungsbeispiel ist diese Funktion die Sigmoid-Funktion.

Die Klassifizierungseinrichtung 140 wird trainiert, indem am Eingang ein Merkmalsvektor angeboten wird, der Eingang durch das Netzwerk geleitet wird und mit einem bekannten Ausgang verglichen wird. Der Fehler (die Differenz zwischen dem bekannten Ausgang und dem durchgeleiteten Eingang) wird dann verwendet, um die Netzwerkgewichtungen in solcher Weise zu modifizieren, daß der Fehler kleiner wird. Diese Funktion wird in dem erläuterndem Ausführungsbeispiel durch den Rückausbreitungstrainer 130 nach den Fig. 6a und 6b ausgeführt. Der Fachmann erkennt, daß andere Klassifizierungseinrichtungs-Trainierschemata ohne eine Abweichung von dem Grundgedanken der vorliegenden technischen Lehre eingesetzt werden können. Der Rückausbreitungstrainer 130 des als Beispiel gewählten Systems kann durch Software verwirklicht werden, um folgende Operationen auszuführen:

Hierin ist η der Lernkoeffizient und

Iw(n+1) = kw(n) - nδE/δkw [11]

E = ((M+1)a - t)² [12]

t ist ein Zielobjektwertevektor.

Darstellung:

kw(N+1) = kW(n) - kΔW(n) [13]

kΔW(n) = ηβ.(k+1)a(n) [14]

(Einige Darstellungen enthalten einen "Moment"-Ausdruck, der zu der Gleichung (14) den Ausdruck αΔw (n-1) addiert.

β = (k+l)a(n)·(1-(k+l)a(n))·kφ [15]

Mφ = ((M+l)a(n) - t(n)) [16]

i-lφ = iφiW' [17]

hierin ist 2≤i≤M-1.

Fig. 6b verdeutlicht die Wirkungsweise des Klassifizierungseinrichtungs- Trainiersystems nach der vorliegenden Erfindung in einer aktiven Sonar- Signalverarbeitungsumgebung bei großen Entfernungen, wobei die Klassifizierungseinrichtung adaptiv arbeitet. In diesem Betriebsmodus wird der Merkmalsvektoreingang einer Probe der Klasse A, wie in Fig. 6a gezeigt ist, durch Roh- Proben-Merkmalsvektoren von dem Merkmalsextrahierer 20 nach Fig. 5 ersetzt. Die Roh-Proben-Merkmalsvektoren dienen zur Anpassung des Umgrenzungsradius. Somit zieht die Umgränzungsradius-Abschätzeinrichtung ein statistisches Netz um die bekannte Klasse fest, während er mehr über die Umgebung erfährt. Danach definiert der Austauschklassengenerator eine Grenze zwischen den bekannten und den unbekannten Klassen mit der Austauschklasse.

Die Klassifizierungsrichtungen werden an Daten aus dem Zeitintervall [t-Δr, t] trainiert und Entscheidungen werden über Rohdaten-Probenvektoren zu Zeitintervallen [> t] getroffen.

Die Wahl von Δr wird durch zwei miteinander in Konflikt stehende Forderungen bestimmt. Die Zeit muß kleiner als die stationäre Zeit des statistischen Prozesses sein, aus welchem die Merkmalsvektoren die Proben sind und der Wert muß groß genug sein, um eine gute Abschätzung des Clutter-Merkmalsraumes zu ermöglichen. Die einzige Annahme, welche die Eingangsdaten betrifft, ist, daß das Verhältnis von Rauschecho oder Clutter zu Zielobjekt-Merkmalsproben groß genug ist, um nicht die Abschätzung des Clutter-Raumes zu belasten. Dies ist eine gute Annahme für aktives Sonar für große Entfernungen.

Die Fig. 8-10 erläutern die vorteilhafte Wirkungsweise der folgenden Erfindung.

Fig. 8 ist ein Diagramm von Eingangs-Merkmalsdaten, welches für die Erläuterung der vorteilhaften Wirkungsweise der Erfindung hilfreich ist. Die Figur entspricht der Darstellung von Fig. 3 dahingehend, daß sie ein Zielobjekt vor einem Hintergrund darstellt. Zweidimensionale Eingags-Probenvektoren werden sowohl für die bekannte Klasse "o" als auch die Austauschklasse "*" dargestellt. Es sei darauf hingewiesen, daß abweichend von Fig. 3 die Daten nur bezüglich einer bekannten Klasse dargestellt sind, nicht bezüglich zweier Klassen, wie dies bei Klassifizierer- Trainiersystemen bekannter Technik notwendig ist. In Fig. 8 ist die bekannte Datenklasse gleichförmig innerhalb der kreisförmigen Grenzen verteilt.

Die Fig. 9 und 10 sind Diagramme von Merkmalsdaten nach 160.000 Wiederholungen bzw. 560.000 Wiederholungen, d. h., nach 160.000 und 560.000 statistischen Darbietungen der Eingangsdaten an das System nach der Erfindung, mit M = 4. η = 0.9, und α = 0,1, sowie Anfangswerten für die Schichtgewichtungen, die Produkte eines Pseudo-Zufallszahlengenerators in gleichförmiger Verteilung zwischen +/- 0,1 sind. Die feine Linie ist die Entscheidungsgrenzlinie, welche nach den Wiederholungen erzeugt worden ist und die starke Linie ist die optimale Grenzlinie. Die Austauschklasse wurde aus der Kenntnis der "o"-Klassenproben erzeugt, wobei die zweite Methode zur Bestimmung des Umgrenzungsradius verwendet wurde, wie dies oben beschrieben wurde. Diese Simulationsergebnisse zeigen, daß ohne irgendeine Kenntnis über die Zielobjektverteilung eine Umgrenzung erlernt wird, welche eine Klassifizierung mit nahezu vollkommener Genauigkeit vornimmt.

Man sieht also, daß durch die vorliegende Erfindung ein verbessertes Mustererkennungssystem geschaffen wird, das auf eine Mehrzahl von Merkmalsvektoren von einer einzigen Klasse von Datenproben einwirkt. Das erfindungsgemäße System schätzt einen Umgrenzungsradius für die Merkmalsvektoren in der einzigen Klasse von Datenproben ab und erzeugt eine Austauschklasse daraus, basierend auf dem abgeschätzten Umgrenzungsradius. Dieser Umgrenzungsradius dient zum Trainieren einer Klassifizierungseinrichtung, die ihrerseits die Erkennung eines Datenmusters in Rohdaten erleichtert. Der Umgrenzungsradius wird auf der Basis von gegenwärtigen Ergebnissen von der Klassifizierungseinrichtung angepaßt.

Die vorliegende Erfindung wurde somit unter Bezugnahme auf eine bestimmte Ausführungsform für einen bestimmten Anwendungsfall erläutert. Der Fachmann auf diesem Gebiete, dem die vorliegende technische Lehre zugänglich ist, erkennt, daß zusätzliche Modifikationen, Anwendungsmöglichkeiten und Ausführungsformen innerhalb des Gedankens dieser technischen Lehre liegen. Beispielsweise ist die Erfindung nicht auf Sonar-Anwendungen beschränkt. Auch ist die Erfindung nicht auf eine bestimmte Klassifizierungseinrichtung oder einer bestimmten Klassifizierer oder auf eine besondere Klassifizierer-Trainiertechnik beschränkt. Weiterhin ist die Erfindung nicht auf die dargestellte Technik zur Bestimmung eines Umgrenzungsradius oder einer Austauschklasse beschränkt. Andere System und Techniken zur Definition dieser Parameter können angewendet werde, ohne daß der Grundgedanke der Erfindung hierdurch verlassen wird.

Demgemäß sollen die anliegenden Ansprüche jedwede und alle solche Anwendungen, Modifikationen und Ausführungsformen innerhalb des Prinzips der vorliegenden Erfindung umfassen.


Anspruch[de]

1. Verfahren zum Trainieren einer Klassifizierungseinrichtung (100), welches folgende Schritte enthält:

Erzeugen einer Mehrzahl von Merkmalsvektoren aus einer einzelnen Klasse von beispielsweisen, nichtstationären Datenproben;

Abschätzen (110) eines Umgrenzungsradius, basierend auf dem Abstand zwischen Proben in der genannten einzelnen Klasse für die genannten Merkmalsvektoren in dieser einzelnen Klasse nichtstationärer Datenproben, wobei der Umgrenzungsradius der radiale Abstand von jedem Merkmalsvektor ist, jenseits welchem ein unbekannter Merkmalsvektor, der für die Klassifizierung dargeboten wird, als ausserhalb der genannten einzelnen Klasse eingeordnet wird, wie sie durch den genannten bekannten Merkmalsvektor definiert wird;

Erzeugen (120) einer Austauschklasse von Datenproben aus der genannten einzelnen Klasse von Datenproben, basierend auf dem Umgrenzungsradius unter Erzeugung einer gleichförmigen Verteilung von statistischen Austausch- Vektorelementen, welche einen Gruppenraum für die genannte Austauschklasse von Datenproben einnehmen, wobei die Vektorelemente aus einer gleichförmigen Verteilung ausgewählt sind, sowie unter Löschung aller Vektorelemente innerhalb einer Hypersphäre des genannten Umgrenzungsradius eines Merkmalsvektors aus der genannten einzelnen Klasse zur Erzeugung der genannten Austauschklasse; und

Trainieren (130) der genannten Klassifizierungseinrichtung auf der Basis der beiden Klassen, welche durch den Umgrenzungsradius definiert sind, wobei das Trainieren die Bestimmung einer Mehrzahl von Klassifizierungsgewichtungen umfaßt.

2. Mustererkennungssystem (10) mit einer Klassifizierungseinrichtung, welche durch folgendes Verfahren trainiert wird:

Erzeugen einer Mehrzahl von Merkmalsvektoren aus einer einzelnen Klasse von beispielsweisen, nichtstationären Datenproben;

Abschätzen (110) eines Umgrenzungsradius, basierend auf dem Abstand zwischen Proben in der genannten einzelnen Klasse für die genannten Merkmalsvektoren in dieser einzelnen Klasse nichtstationärer Datenproben, wobei der Umgrenzungsradius der radiale Abstand von jedem Merkmalsvektor ist, jenseits welchem ein unbekannter Merkmalsvektor, der für die Klassifizierung dargeboten wird, als außerhalb der genannten einzelnen Klasse eingeordnet wird, wie sie durch den genannten bekannten Merkmalsvektor definiert wird;

Erzeugen (120) einer Austauschklasse von Datenproben aus der genannten einzelnen Klasse von Datenproben, basierend auf dem Umgrenzungsradius unter Erzeugung einer gleichförmigen Verteilung von statistischen Austausch- Vektorelementen, welche einen Gruppenraum für die genannte Austauschklasse von Datenproben einnehmen, wobei die Vektorelemente aus einer gleichförmigen Verteilung ausgewählt sind, sowie unter Löschung aller Vektorelemente innerhalb einer Hypersphäre des genannten Umgrenzungsradius eines Merkmalsvektors aus der genannten einzelnen Klasse zur Erzeugung der genannten Austauschklasse; und

Trainieren (130) der genannten Klassifizierungseinrichtung auf der Basis der beiden Klassen, welche durch den Umgrenzungsradius definiert sind, wobei das Trainieren die Bestimmung einer Mehrzahl von Klassifizierungsgewichtungen umfaßt.

3. Mustererkennungssystem (10), welches folgendes enthält:

eine Klassifizierungseinrichtung, welche gemäß Anspruch 2 trainiert wird, um Rohdaten jeweils als Mitglied einer von zwei Klassen zuordnen, um die Erkennung eines Musters in den Daten zu erleichtern; und Mittel zur Anpassung des genannten abgeschätzten Umgrenzungsradius und der Klassifizierungsgewichtungen auf der Basis von Ergebnissen von der genannten Klassifizierungseinrichtung.

4. Mustererkennungssystem nach Anspruch 3 in Anwendung auf die Erkennung von Mustern in einem Sonarsystem, wobei das Mustererkennungssystem weiter folgendes enthält:

Sendermittel (11) zur Erzeugung eines Sonarimpulses;

Ein Phased-Array-Strahlformungsnetzwerk (12) zum Empfang des Sonarimpulses zwecks Erzeugung eines Empfangssignales;

Signalverarbeitungsmittel (18) zum Detektieren des Empfangssignales und zum Extrahieren einer Mehrzahl von Datenproben daraus; und

Mittel (20) zum Extrahieren von Merkmalen der Datenproben.

5. Verfahren zur Erkennung eines Musters in Datenproben mit folgenden Schritten: Trainieren einer Klassifizierungseinrichtung gemäß Anspruch 1;

Klassifizieren (140) der Rohdaten jeweils als Mitglied einer von zwei Klassen zur Erleichterung der Erkennung eines Musters in den Daten; und

Anpassen des genannten abgeschätzten Umgrenzungsradius und der genannten Klassifizierungsgewichtungen auf der Basis laufender Ergebnisse aus dem Schritt der Klassifizierung der Rohdaten.

6. Verfahren nach Anspruch 5 in Anwendung auf Sonardaten mit folgenden weiteren Schritten:

Erzeugung (11) eines Sonarimpulses;

Empfang (12) der Sonarimpulse zur Erzeugung eines Empfangsignales;

Detektieren (18) des Empfangsignales und Extrahieren einer Mehrzahl von Datenproben daraus; und

Extrahieren (20) von Merkmalen in den Datenproben.

7. Fernbereichs-Sonarsystem mit verbesserter Mustererkennung zur Unterscheidung von Zielobjektdaten von Hintergrunddaten, wobei die genannten Hintergrunddaten eine Klasse nichtstationärer Störungsdaten bilden, mit einem Mustererkennungssystem nach Anspruch 3.

8. Verfahren zur Unterscheidung von Daten gegenüber Hintergrunddaten in einem Sonarsystem, wobei die Hintergrunddaten eine Klasse nichtstationärer Störungsdaten bilden, mit der Ausführung der Verfahrensschritte nach Anspruch 6.







IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com