PatentDe  


Dokumentenidentifikation DE4495111C2 21.10.1999
Titel Verfahren zur Bestimmung einer Menge von charakteristischen Merkmalen im Rahmen einer Objekterkennung
Anmelder Verovenko, Olga Olegovna, Moskau, RU
Erfinder Verovenko, Olga Olegovna, Moskau, RU
Vertreter v. Füner Ebbinghaus Finck Hano, 81541 München
DE-Anmeldedatum 30.06.1994
DE-Aktenzeichen 4495111
WO-Anmeldetag 30.06.1994
PCT-Aktenzeichen RU9400141
WO-Veröffentlichungsnummer 9502868
WO-Veröffentlichungsdatum 26.01.1995
Date of publication of WO application in German translation 07.12.1995
Veröffentlichungstag der Patenterteilung 21.10.1999
Veröffentlichungstag im Patentblatt 21.10.1999
IPC-Hauptklasse G06K 9/66

Beschreibung[de]

Die Erfindung betrifft ein Verfahren zur Bestimmung einer Menge von charakteristischen Merkmalen im Rahmen einer Objekterkennung zu identifizierender Objekte gemäß dem Oberbegriff des Patentanspruchs. Sie kann bei der Schaffung von mit modernen Computern arbeitenden Erkennungssystemen und bei der Modellierung von Erkennungsverfahren unter Ausnutzung moderner Computer sowie auch bei der Vorbereitung von Texteditoren, bei der Fremdsprachenausbilung usw. eingesetzt werden.

Verfahren zur Objekterkennung finden in den letzten Jahren immer größere Anwendung bei der Lösung verschiedener wissenschaftlicher und praktischer Aufgaben.

So ist z. B. aus der EP 0 191 407-A2 ein Verfahren zur Klassifikation und Identifikation von Mustern in einem System bekannt. Das System weist eine Eingabeeinrichtung zur Eingabe eines Eingangssignals auf, das jedes Eingabemuster als einen Ort in einem mehrdimensionalen Musterraum repräsentiert. Ferner enthält das System eine Einrichtung zur Informationsspeicherung und einen Computer, der mit der Informationsspeichereinrichtung und der Eingabeeinrichtung verbunden ist. Das Verfahren der EP 0 191 407-A2 besteht darin, daß in der Speichereinrichtung mehrere Prototypen innerhalb des mehrdimensionalen Musterraums gespeichert werden und dann ein durch das genannte Signal repräsentiertes Eingabemuster mit jedem der gespeicherten Prototypen verglichen wird, um zu bestimmen, ob das Eingabemuster in einen Einflußbereich mindestens eines der genannten Prototypen fällt.

Aus der Druckschrift H. NIEMANN "Methoden der Mustererkennung", Akademische Verlagsgesellschaft Frankfurt am Main, 1974, Seite 224, Abschnitt 3.2.5. ist ein Verfahren zum entscheidungsüberwachten Lernen einer Maschine bekannt. Dabei steht für den Lernvorgang eine klassifizierte Stichprobe zur Verfügung. Außerdem werden der Maschine neue, unklassifizierte Muster zugeführt, die dann ebenfalls zum Lernen herangezogen werden, wobei so getan wird, als gehörten sie zu der Klasse, für die sich die Maschine entschieden hat. Die "neuen Muster" werden der Maschine ungeordnet vorgehalten. Bei diesem Verfahren besteht die Gefahr, daß der ganze Lernprozeß divergiert, weil die Klassencharakteristika zu oft mit falschen Daten "aufgefrischt" werden.

Aus dem Buch Zdor S. E.; Sirokov V. B.: Optische Suche und Erkennung - Verlag: Nauka, Moskau 1973, S. 135-141, ist ein Verfahren zur Bestimmungen von charaktistischen Merkmalen im Rahmen einer Objekterkennung zu identifizierender Objekte mit folgenden Schritten bekannt:

  • a) Festlegen von Merkmalen zu identifizierender Objekte,
  • b) Abtasten einer Informationsmenge durch eine Erkennungsvorrichtung,
  • c) Bestimmen in der Informationsmenge enthaltener Merkmale von Objekten,
  • d) Vergleichen der in Schritt c) bestimmten Merkmale mit den in Schritt a) festgelegten Merkmalen, und
  • e) Identifizieren solcher Objekte, die die charakteristischen Merkmale aufweisen.

Mathematische Grundlagen für die vorgehend beschriebenen Verfahren finden sich in dem Buch Liedtke C.-E.; Ender M.: Wissensbasierte Bildverarbeitung. - Springer-Verlag, Berlin, Heidelberg, New York, London, Paris, Tokyo, Hong Kong 1989, S. 84 bis 89.

Die Unterschiede zwischen den genannten Verfahren beruhen im wesentlichen auf der Ausnutzung verschiedener Vorgehensweisen bei der Objektklassifikation. So liegt zum Beispiel der metrischen Vorgehensweise das Festlegen einer Gesamtheit von Eichmaßen und die Ausführung einer Diskretisierung von Objekten zugrunde, wobei das Diskretisieren einerseits nicht zu einer redundanten Beschreibung führen soll und andererseits ein Ursprungsobjekt beim Vergleich mit dem Eichmaß möglichst genau wiedergegeben werden soll. Grundlage der Vorgehensstruktur bei der Objekterkennung ist das Festlegen einer bestimmten Gesamtheit von Elementarmerkmalen. Als Elementarmerkmale werden normalerweise solche Merkmale wie "Winkel", "Kreuzung" usw. benutzt.

Ein Nachteil dieser Verfahren besteht erstens darin, daß diese einen begrenzten Verwendungsbereich haben, da determinierte Gesamtheiten von Merkmalen, die mit den Erkennungsobjekten übereinstimmen, in einigen Fällen, wie zum Beispiel bei differenzierter Erkrankungsdiagnostik, nicht vorhanden sind. Zweitens ist die Effektivität der Informationsverarbeitung mit Hilfe der bekannten Verfahren nicht groß, da es notwendig ist, bei der Ausführung der Erkennung jedes Objektes ein Suchverfahren, das alle angegebenen Merkmalsgesamtheiten einschließt, zu verwirklichen und die Gesamtheit, die mit dem Erkennungsobjekt übereinstimmt, zu wählen.

Der Erfindung liegt die Aufgabe zugrunde, ein Verfahren zur Bestimmung einer Menge von charakteristischen Merkmalen im Rahmen einer Objekterkennung zu identifizierender Objekte bereitzustellen, das aufgrund des Inhalts und der Organisation seiner Verfahrensschritte eine besonders hohe Effektivität aufweist und deshalb zur Bearbeitung von großen Informationsblöcken, die mehrere komplizierte Informationsthemen betreffende Objekte enthalten, besonders geeignet ist.

Erfindungsgemäß wird diese Aufgabe gelöst durch ein Verfahren zur Bestimmung einer Menge von charakteristischen Merkmalen im Rahmen einer Objekterkennung zu identifizierender Objekte mit folgenden Schritten:

  • a) Festlegen von Merkmalen zu identifizierender Objekte,
  • b) Abtasten einer Informationsmenge durch eine Erkennungsvorrichtung,
  • c) Bestimmen in der Informationsmenge enthaltener Merkmale von Objekten,
  • d) Vergleichen der in Schritt c) bestimmten Merkmale mit den in Schritt a) festgelegten Merkmalen, und
  • e) Identifizieren solcher Objekte, die die charakteristischen Merkmale aufweisen,
gekennzeichnet durch folgende Schritte:

  • a) Bilden zweier Gruppen von Objektstichproben, wobei jede einzelne Stichprobe mindestens ein zu identifizierendes Objekt aufweist und die Stichproben der ersten Gruppe als Lehrstichproben und die Stichproben der zweiten Gruppe als Prüfungsstichproben dienen,
  • b) Ordnen der einzelnen Stichproben innerhalb jeder der beiden Stichprobengruppen nach aufsteigender Kompliziertheit der Identifikation der zu identifizierenden Objekte, wobei ihrer Nummer in der jeweiligen Ordnung nach einander entsprechende Stichproben jeweils gleiche Kompliziertheit aufweisen,
  • c) Durchführen von Schritt a) indem eine erste Lehrstichprobe abgetastet und, auf der Basis der dabei gewonnenen Daten, allgemeine Elementarmerkmale des zu identifizierenden Objektes festgelegt werden,
  • d) Überprüfen der Brauchbarkeit der gewonnenen allgemeinen Elementarmerkmale zur Identifikation des zu identifizierenden Objektes anhand des Abtastens von Prüfungsstichproben, deren Kompliziertheit nicht kleiner ist als die Kompliziertheit der letztgenannten Lehrstichprobe, sukzessive nach aufsteigender Kompliziertheit der Prüfungsstichproben, wobei für jede hierbei betrachtete Prüfungsstichprobe die Schritte b) bis e) und eine Überprüfung des Identifizierungserfolgs durchgeführt werden,
    • 1. v)- falls sich bei einer Prüfungsstichprobe die aktuell in Betracht gezogenen Elementarmerkmale des zu identifizierenden Objektes als unbrauchbar erweisen: Abtasten der Lehrstichprobe, deren Nummer der Nummer der letztgenannten Prüfungsstichprobe entspricht, und, auf der Basis der dabei gewonnenen Daten, Modifizieren der allgemeinen Elementarmerkmale des zu identifizierenden Objekts und Fortsetzen des Verfahrens bei Schritt iv),
    • 2. sobald die Prüfungsstichprobe mit der höchsten Kompliziertheit abgetastet und dabei die aktuell in Betracht gezogenen Elementarmerkmale für brauchbar befunden wurden: Anerkennen der letztgenannten Elementarmerkmale als Menge der charakteristischen Merkmale.

Ein besonderer Vorteil des erfindungsgemäßen Verfahrens besteht darin, daß ein mit diesem Verfahren arbeitendes Erkennungssystem seine Variante der Menge von charakteristischen Merkmalen, die jedem konkreten Erkennungsobjekt entsprechen, als Ergebnis der Analyse einer endlichen Folge von Stichproben der ersten Gruppe, die Merkmale des Erkennungsobjekts enthalten, festlegt. Es erfolgt, mit anderen Worten, eine Anpassung des Lexikons und der Logik des Erkennungssystems zur Erkennung des angegebenen Objektes. Dieser Umstand ermöglicht die Verwendung des erfindungsgemäßen Verfahrens im Rahmen einer Objekterkennung zu idenfizierender Objekte, deren Merkmale im voraus nicht definiert sind. Dabei kann das erfindungsgemäße Verfahren sowohl in mit moderenen Computern arbeitenden Erkennungssystemen als auch bei der Ausbildung von Operatoren verwendet werden.

Die Figur zeigt ein Flußdiagramm, das einer Verwirklichungsmöglichkeit des erfindungsgemäßen Verfahrens entspricht. In einem Erkennungssystem wird ein Informationsträger an einen Eingang eines Abtastblocks 1 geführt. Ein Ausgang des Abtastblocks 1 ist an einen ersten Eingang 2 eines Analysators 3 angeschlossen. Ein Ausgang des Analysators 3 ist direkt mit einem Registrierblock 4 und über eine Reihenschaltung eines logischen Blocks 6 und eines Programmblocks 7 mit einem zweiten Eingang 5 des Analysators 3 verbunden. Der logische Block 6 ist auch an einen Speicherblock 8 angeschlossen.

Das erfindungsgemäße Verfahren wird folgendermaßen durchgeführt: Zunächst wird eine erste Gruppe von Stichproben gebildet. Dabei enthält jede Stichprobe Beispiele des Erkennungsobjekts. Das Erkennungsobjekt muß in jedem in einer Stichprobe befindlichen Beispiel irgendwie gekennzeichnet worden sein. Welches Verfahren zum Aussondern des Erkennungsobjekts gewählt wird, hängt von den Konstruktionsbesonderheiten des Abtastblocks ab. Im Prinzip kann jedes der bekannten Verfahren zum Aussondern des geforderten Informationsumfangs benutzt werden. Außerdem wird eine andere Gruppe von (Prüfungs-) Stichproben gebildet. Dabei enthält jede Prüfungsstichprobe Beispiele desselben Erkennungsobjekts. Allerdings wird in diesen Beispielen die das Erkennungsobjekt betreffende Information nicht speziell ausgezeichnet. Die Information, die jede Stichprobe betrifft, wird auf einen geeigneten Träger aufgenommen. Danach werden die den Stichproben der ersten und der anderen Gruppe entsprechenden Träger in aufsteigender Reihenfolge bezüglich wachsender Kompliziertheit der darauf aufgenommenen Informationen angeordnet. Damit ist der Vorbereitungsschritt zu Ende.

Danach wird an den Eingang des Abtastblocks 1 ein Träger geführt, auf dem die erste Stichprobe aus der ersten Gruppe aufgenommen ist, und die auf dem Träger aufgenommene Information wird abgetastet (abgelesen). Die in der ersten Stichprobe als Folge von z. B. elektrischen Signalen enthaltene Information wird vom Ausgang des Abtastblocks 1 an den ersten Eingang 2 des Analysators 3 geleitet. Mit dem Analysator 3 wird die Bearbeitung der Information, die jedes Beispiel der ersten Stichprobe enthält, durchgeführt. Es ist möglich, die Bearbeitung der in der ersten Stichprobe eingesetzten Beispiele entweder nacheinander oder parallel durchzuführen. Welche Bearbeitungsmöglichkeit zum Einsatz kommt, ist im wesentlichen von den technischen Möglichkeiten des Analysators 3 abhängig.

In jedem Beispiel des Erkennungsobjekts wird das Aussondern der gekennzeichneten Elementarmerkmale durchgeführt. Das beinhaltet auch das Feststellen ihrer gegenseitigen Anordnung und der Anordnung des Erkennungsobjekts in bezug auf andere im entsprechenden Beispiel eingesetzte Objekte. Die in jedem Beispiel ausgesonderten Merkmale werden mit Hilfe des logischen Blocks 6 untereinander verglichen und im Ergebnis in Gruppen von "ähnlichen" oder "gleichen" aufgeteilt. Die Anzahl der ausgesonderten Gruppen von Merkmalen definiert die erste Variante der Menge von Merkmalen, die dem Erkennungsobjekt entsprechen.

Auf diese Weise wird aus der in die Struktur des Analysators 3 eingeführten Merkmalsmenge mit Hilfe des logischen Blocks 6 das Aussondern der Merkmalsteilmenge durchgeführt, die dem Erkennungsobjekt entspricht. Mit Hilfe des Programmblocks 7, auf dessen Eingang die Signale aus dem Ausgang des logischen Blocks 6 geleitet werden, erfolgt die Abstimmung des Analysators 3 auf die Objektklassifikation gemäß der festgelegten Menge von Merkmalen. Gleichzeitig wird diese Variante der festgelegten Menge von Merkmalen in den Speicherblock 8 eingeführt.

Um die "Ausbildungsergebnisse" des Erkennungssystems zu prüfen, wird an den Eingang des Abtastblocks 1 ein Träger geführt, auf dem die erste Stichprobe aus der anderen (Prüfungs-) Stichprobengruppe aufgenommen ist. Danach erfolgt das Aussondern der Merkmale aller Objekte, die in jedem Beispiel der analysierten Prüfungsstichprobe enthalten sind, und ein Vergleich der Merkmale der zur Erkennung gestellten Objekte mit der festgelegten Menge von Merkmalen. Auf der Grundlage dieses Vergleiches wird das Objekt, welches die festgelegte Menge von Merkmalen aufweist, ausgesondert. Die Erkennungsergebnisse werden auf den Registrierblock 4 geleitet. Ist ein bei der Bearbeitung der ersten Prüfungsstichprobe erhaltener Kennwert für die Richtigkeit des Erkennungsobjektes nicht kleiner als ein erforderlicher entsprechender Wert, wird an den Eingang des Abtastblocks 1 ein Träger geführt, auf dem eine zweite, Merkmale des Erkennungsobjekts enthaltende Stichprobe aus der ersten Stichprobengruppe aufgenommen ist. Dabei werden die Ausgänge des logischen Blocks 6, die an den Programmblock 7 angeschlossen sind, auf Null gesetzt, und der Analysator 3 wird in einen solchen Betriebsmodus umgeschaltet, der der Bearbeitung der ersten Stichprobe aus derselben Stichprobengruppe entspricht.

Die in der zweiten Stichprobe enthaltene Information wird in der oben dargestellten Reihenfolge bearbeitet, und man erhält eine Merkmalsteilmenge, die dem Erkennungsobjekt entspricht. Dabei sind im Prinzip zwei Varianten möglich: Entweder fällt die erhaltene Merkmalsteilmenge mit der bei der Bearbeitung der ersten Lehrstichprobe erhaltenen Merkmalsteilmenge zusammen, oder die erhaltene Merkmalsteilmenge fällt teilweise nicht mit der bei der Bearbeitung der ersten Lehrstichprobe erhaltenen Merkmalsteilmenge zusammen.

Im ersten Fall werden die Träger mit den aufgenommenen Prüfungsstichproben nacheinander an den Eingang des Abtastblocks 1 geführt. Wird bei der Bearbeitung einer der Prüfungsstichproben ein Kennwert für die Richtigkeit des Erkennungsobjektes erhalten, der kleiner als ein erforderlicher entsprechender Wert ist, so wird an den Eingang des Abtastblocks 1 ein Träger mit einer darauf aufgenommenen Stichprobe aus der ersten Gruppe geleitet, wobei die Nummer dieser Stichprobe gleich der Nummer der Prüfungsstichprobe sein muß, bei deren Bearbeitung der zu niedrige Kennwert erhalten worden war. Im Ergebnis dessen wird eine präzisierte Teilmenge von dem Erkennungsobjekt entsprechenden Merkmalen erhalten. Damit entsteht eine Situation, die oben als die andere Variante angegeben wurde.

In dieser anderen Variante wird mit dem logischen Block 6 eine erweiterte Merkmalsteilmenge festgelegt. Diese Teilmenge enthält Merkmale der Teilmengen, die bei der Bearbeitung der beiden Stichproben aus der ersten Stichprobengruppe erhalten worden waren. Danach wird an den Eingang des Abtastblocks 1 ein Träger geführt, auf den eine andere Prüfungsstichprobe aufgenommen ist. Diese andere Prüfungsstichprobe wird mit dem auf die erweiterte Teilmenge abgestimmten Analysator 3bearbeitet. Die Anzahl der Lehrstichproben und ihnen entsprechender Prüfungsstichproben wird von der Kompliziertheit des Erkennungsproblems und auch von der a-priori-Information über das Erkennungsobjekt bestimmt.


Anspruch[de]
  1. 1. Verfahren zur Bestimmung einer Menge von charakteristischen Merkmalen im Rahmen einer Objekterkennung zu identifizierender Objekte mit folgenden Schritten:
    1. a) Festlegen von Merkmalen zu identifizierender Objekte,
    2. b) Abtasten einer Informationsmenge durch eine Erkennungsvorrichtung,
    3. c) Bestimmen in der Informationsmenge enthaltener Merkmale von Objekten,
    4. d) Vergleichen der in Schritt c) bestimmten Merkmale mit den in Schritt a) festgelegten Merkmalen, und
    5. e) Identifizieren solcher Objekte, die die charakteristischen Merkmale aufweisen,
    gekennzeichnet durch folgende Schritte:
    1. a) Bilden zweier Gruppen von Objektstichproben, wobei jede einzelne Stichprobe mindestens ein zu identifizierendes Objekt aufweist und die Stichproben der ersten Gruppe als Lehrstichproben und die Stichproben der zweiten Gruppe als Prüfungsstichproben dienen,
    2. b) Ordnen der einzelnen Stichproben innerhalb jeder der beiden Stichprobengruppen nach aufsteigender Kompliziertheit der Identifikation der zu identifizierenden Objekte, wobei ihrer Nummer in der jeweiligen Ordnung nach einander entsprechende Stichproben jeweils gleiche Kompliziertheit aufweisen,
    3. c) Durchführen von Schritt a) indem eine erste Lehrstichprobe abgetastet und, auf der Basis der dabei gewonnenen Daten, allgemeine Elementarmerkmale des zu identifizierenden Objekts festgelegt werden,
    4. d) Überprüfen der Brauchbarkeit der gewonnenen allgemeinen Elementarmerkmale zur Identifikation des zu identifizierenden Objekts anhand des Abtastens von Prüfungsstichproben, deren Kompliziertheit nicht kleiner ist als die Kompliziertheit der letztgenannten Lehrstichprobe, sukzessive nach aufsteigender Kompliziertheit der Prüfungsstichproben, wobei für jede hierbei betrachtete Prüfungsstichprobe die Schritte b) bis e) und eine Überprüfung des Identifizierungserfolgs durchgeführt werden,
      1. 1. v)- falls sich bei einer Prüfungsstichprobe die aktuell in Betracht gezogenen Elementarmerkmale des zu identifizierenden Objekts als unbrauchbar erweisen: Abtasten der Lehrstichprobe, deren Nummer der Nummer der letztgenannten Prüfungsstichprobe entspricht, und, auf der Basis der dabei gewonnenen Daten, Modifizieren der allgemeinen Elementarmerkmale des zu identifizierenden Objekts und Fortsetzen des Verfahrens bei Schritt iv),
      2. 2. sobald die Prüfungsstichprobe mit der höchsten Kompliziertheit abgetastet und dabei die aktuell in Betracht gezogenen Elementarmerkmale für brauchbar befunden wurden: Anerkennen der letztgenannten Elementarmerkmale als Menge der charakteristischen Merkmale.






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

  Patente PDF

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