DE3485953T2

DE3485953T2 - Verfahren und anlage zur on-line-erkennung handgeschriebener muster.

Info

Publication number: DE3485953T2
Application number: DE8484116399T
Authority: DE
Inventors: Kotaro Hirasawa; Soshiro Kuzunuki; Hiroshi Shojima
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1983-12-26
Filing date: 1984-12-27
Publication date: 1993-04-29
Anticipated expiration: 2004-12-28
Also published as: EP0151316B1; US4653107A; EP0151316A2; JPH0139154B2; EP0151316A3; DE3485953D1; JPS60136892A

Description

Die Erfindung betrifft ein Verfahren und eine Vorrichtung zur Erkennung eines handgeschriebenen Musters und insbesondere ein Verfahren und eine Vorrichtung zur Eingabe graphischer Daten, die für ein On-line-Herstellungssystem für handgeschriebene Dokumente anwendbar sind.
Da ein Großcomputersystem weit verbreitet ist und die Leistungsfähigkeit einer informationsverarbeitenden Terminal- Ausrüstung verbessert worden ist, haben die Anwender der Computer rasch zugenommen, und eine Eingabevorrichtung für handgeschriebene Muster hat die öffentliche Aufmerksamkeit als eine Eingabevorrichtung für den Computer gefunden.
Eine Eingangsinformation wird klassifiziert in Schriftzeichen und Graphik. Beispiele entsprechend dem Stand der Technik werden nachfolgend beschrieben.

Beispiel 1 (Stand der Technik)

Eine allgemeine Beschreibung der On-Line-Erkennung eines handgeschriebenen Zeichens findet sich in Nikkei Electronics, 1973, Nr. 5-7, Seiten 46 bis 59. Ein Verfahren zur Erkennung eines handgeschriebenen Zeichens durch Darstellung des handgeschriebenen Zeichens durch eine Serie von kurzen Linien und deren Vergleich mit einem Muster in einem Verzeichnis wird nachfolgend erläutert.
Die Fig. 1 zeigt ein Glättungsverfahren für ein handgeschriebenes Muster. P&sub0;-P&sub1;-P&sub2;-P&sub3; stellen ein Eingabemuster dar. Der Punkt P&sub0;, bei dem der Stift zum ersten Mal abgesenkt wurde, wird als erster Abtastpunkt S&sub0; bezeichnet und ein Kreis mit dem Mittelpunkt S&sub0; mit einem vorbestimmten Radius (z. B. 5) wird gezeichnet, um einen nächsten Punkt P&sub1; zu suchen, der außerhalb des Kreises liegt. Die Distanz zwischen den Punkten P&sub0; und P&sub1; wird im Verhältnis von n/m (z. B. 3/1) geteilt und der Teilungspunkt wird als neuer Abtastpunkt S&sub1; bezeichnet. Ein Kreis mit Mittelpunkt bei S&sub1; mit Radius 5 wird gezeichnet, um den nächsten Punkt P&sub2; zu suchen, der außerhalb des Kreises liegt. Die Distanz zwischen den Punkten P&sub1; und P&sub2; wird im Verhältnis 3/1 geteilt und der Teilungspunkt wird als neuer Abtastpunkt S&sub2; bezeichnet.
Der vorstehende Prozeß wird fortgesetzt, bis der Zeichenstift abgehoben wird, um die Abtastpunkte S&sub0;, S&sub1;, S&sub2; und S&sub3; zu bestimmen. Wenn ein Winkel zwischen dem Liniensegment S&sub0;S&sub1; und dem Liniensegment S&sub1;S&sub2; kleiner als ein vorbestimmter Winkel ist, dann wird die Linie S&sub0;S&sub2; als ein gerades Liniensegment S&sub0;S&sub2; betrachtet. Der vorstehende Prozeß wird wiederholt, so daß handgeschriebene Muster durch Segmente angenähert ist.
Die Segment-Daten, die das handgeschriebene Muster annähern, werden durch einen Schriftzeichen-Erkennungsbaum als ein spezielles Schriftzeichen erkannt.
Dieses Verfahren wird ein Richtungsschlüssel-Verfahren genannt. Die im Glättungsprozeß abgetasteten Punkte S&sub0; bis S&sub3; werden hintereinander verbunden, um das handgeschriebene Muster in mehrere Segmente aufzuteilen. Wenn das handgeschriebene Muster aus kurzen Abschnitten besteht (z. B. KANJI-Schriftzeichen), sind dem eingegebenen Zeichen geringfügige mechanische Schwankungen überlagert ("Zittern") und es kann effektiv in ein gerades Segment umgewandelt werden, aber wenn das Muster einen langen Strich aufweist, wird es wegen des Zitterns des Striches nicht in einen geraden Abschnitt umgewandelt. Es genügt nicht, die Zittererscheinungen zu dämpfen, die auftreten, wenn ein Muster mit einem langen Strich mit Hand geschrieben ist. Um die Störungen zu dämpfen, ist es erforderlich, den Segmentierungsschritt einige Male zu wiederholen.
Da dieses Beispiel die Anzahl der Striche als einen Faktor zur Klassifizierung des Schriftzeichens verwendet, braucht man eine andere Methode zur Erkennung eines ununterbrochen geschriebenen Schriftzeichens.

Beispiel 2 (Stand der Technik)

Eine Prüf-Gittermethode wird nun erläutert. (Vgl. zum Beispiel "On-line Recognition Algorithm for Hand-Sketched Flowchart by Candidate Lattice Method", Papers of Institute of Electronics and Communications of Japan, '83/6, Vol. J66-D, No. 6, S. 675-681, oder "On-line Recognition Algorithms for Handwritten Chinese Characters and Hand-sketched Line Figures", Institute of Television of Japan, Vol. 6, No. 44 (1983), S. 43-48, Mushashino Communication Laboratory.)
Die Fig. 2 zeigt ein Flußdiagramm der Prüf-Gittermethode.

Prüfmusterextraktion (Schritt 1)

Anfangs- und Endkoordinaten P eines eingegebenen Striches werden mit den charakteristischen Punkten eines Symbols G (auf das alle Muster in einem Verzeichnis 10 anwendbar sind) verglichen ("kollationiert") und mehrere Sätze von Einstrich-Folgen (Prüfstrichfolgen) werden erzeugt, von denen jede durch alle charakteristischen Punkte Pi (i = 1 bis n, n ist die Anzahl der charakteristischen Punkte des Symbols G) geht. Wenn die Eingangsstrichfolge und der erzeugte Prüfstrich sich nicht unterscheiden, dann wird das Symbol G als ein Prüfmuster Gc ausgewählt. Auf diese Weise können die Muster des Verzeichnisses klassifiziert werden, während Abänderungen und Störungen des handgeschriebenen Musters absorbiert werden können.

Differenzberechnung (Schritt 2)

Die Prüf-Gittermethode wendet eine dynamische Programmier- Abgleichmethode (DP-Abgleich) an, die nicht nur die Euklidische Distanz zwischen dem charakteristischen Punkt und dem Strich auswertet, sondern auch die Richtung einer Tangente an den Strich entsprechend dem charakteristischen Punkt. Die Differenz ist gegeben durch
wobei (xm, ym) die Eingangsstrichkoordinaten bedeuten, (x'u(m), y'u(m)) die Prüf-Koordinaten α: Konstante
Der erste und der zweite Term in () auf der rechten Seite der Gleichung (1) stellen die Euklidische Distanz zwischen dem Endpunkt des eingegebenen Striches und dem charakteristischen Punkt des Musterverzeichnisses dar, und der dritte Term stellt eine Differenz zwischen den Tangenten des eingegebenen Striches und des Prüfstriches beim charakteristischen Punkt (x'm, y'm) dar.

Aufsuchen des Prüfergitters (Schritt 3)

Die Differenz im Schritt (2) wird für jedes im Schritt (1) extrahierte Muster berechnet und in einer Tabelle zusammengefaßt.
Ein Muster, das die kleinste Summe der Differenzen aufweist, wird von den Mustern, die von der Tabelle abgeleitet sind, ausgewählt. Ein Prüfmuster, das nach Beurteilung einer Verbindungsregel 11 für einen eingegebenen Strich zu einem anderen nicht vorhanden sein kann, wird eliminiert, sogar dann, wenn es sich nur geringfügig vom eingegebenen Strich unterscheidet.
Mit den Schritten (1) bis (6) kann das handgeschriebene Muster ohne Berücksichtigung der Anzahl der Striche und der Reihenfolge der Striche und der Segmentierung erkannt werden. Jedoch, es sind keine Mittel vorhanden 1) für das fortlaufende Schreiben von zwei Mustern, und 2) für die Drehung eines Musters. Daher sind solche Muster schwer zu erkennen.
In TECHNOLOGY AND SCIENCE OF INFORMATICS, Vol. 1, Nos. 1- 6, 1983, Seiten 121-134, Oxford, GB; A BELAID et al: "Segmentation of line drawings for recognition and interpretation", ist ein Segmentierungsprozeß für Strich-Zeichnungen beschrieben, der in drei Stufen arbeitet. Eine erste Abtaststufe eliminiert unbedeutende Punkte in der Zeichnung, um den Bestand an Punkten zu kontrollieren und um die Aufteilung (Segmentierung) in Grundformen zu vereinfachen. Die zweite Stufe eliminiert Verschmierungen, die durch das graphische Tablett erzeugt sind, und Ungenauigkeiten, die dem Benutzer zuzuschreiben sind. Die Identifizierung der Grundformen bildet die dritte Stufe. Jedoch im Gegensatz zur vorliegenden Erfindung ist ein Erkennungsprozeß nicht angegeben.
Im Hinblick auf die vorstehenden Ausführungen ist es Aufgabe der vorliegenden Erfindung, ein On-line-Erkennungsverfahren und eine On-line-Vorrichtung für handgeschriebene Muster anzugeben, die automatisch die Muster trennen, die nicht von der Reihenfolge der Striche abhängen, von der Anzahl der Striche und von der Neigung (der Drehung) des Musters und die mit großer Geschwindigkeit arbeiten.
Entsprechend einem Aspekt wird diese Aufgabe der Erfindung durch die Merkmale gelöst, die im Anspruch 1 angegeben sind, und entsprechend einem weiteren Aspekt durch die Merkmale, die im Anspruch 9 angegeben sind.
Die Elemente eines Musters sind Segmente, und mehrere Segmente bilden ein Muster.
Andererseits wird ein Muster, das von einem Tablett eingegeben wird, in einem Computer als Abtastpunktfolge in Serie eingelesen.
Bei der vorliegenden Erfindung wird ein charakteristisches Datum, das von der Abtastpunktfolge hergeleitet ist, und eine Linie, die zwei Abtastpunkte verbindet, verwendet, um die Abtastpunktfolge in Segmente zu zerlegen, während es wirkungsvoll das Zittern des handgeschriebenen Musters dämpft. Die Vielzahl der Segmente werden als Datengrundeinheiten verwendet, wie das in einem Ausführungsbeispiel der Erfindung beschrieben ist, so daß die Grenze zwischen den Mustern automatisch erkannt wird, ohne von der Anzahl der Striche, der Reihenfolge der Striche und der Drehung des Musters abhängig zu sein.
Dieses und weitere Aufgaben, Merkmale und Vorteile der vorliegenden Erfindung werden aus der folgenden detaillierten Beschreibung zusammen mit den beigefügten Zeichnungen hervorgehen, in denen:
Fig. 1 zeigt ein Verfahren zum Glätten nach dem bekannten Stand der Technik;
Fig. 2 zeigt ein Flußdiagramm eines Prüf-Gitterverfahrens nach dem Stand der Technik für die Erkennung handgeschriebener Muster;
Fig. 3 zeigt ein Ausführungsbeispiel der vorliegenden Erfindung für eine On-line-Vorrichtung zur Erkennung handgeschriebener Muster;
Fig. 4 ist ein Flußdiagramm eines Ausführungsbeispiels der vorliegenden Erfindung für ein On-line-Verfahren zur Erkennung handgeschriebener Muster;
Fig. 5 ist ein Flußdiagramm des Erkennungsverfahrens der vorliegenden Erfindung;
Fig. 6 zeigt einen Richtungsschlüssel;
Fig. 7a, 7b, 7c und 7d zeigen die Segmentierung eines handgeschriebenen Musters bei der vorliegenden Erfindung (Flächenverfahren);
Fig. 8a und 8b veranschaulichen die Normierung eines Musters;
Fig. 9 zeigt eine Verbindungsliste;
Fig. 10 veranschaulicht Kode-wrapping;
Fig. 11 zeigt ein Flußdiagramm zur Analogie-Berechnung;
Fig. 12 veranschaulicht die Berechnung einer Differenz;
Fig. 13a und 13b zeigen die Rekonfiguration von Elementen;
Fig. 14a, 14b, 14c und 14d zeigen Beispiele erkannter Muster;
Die Fig. 3 zeigt eine On-line-Vorrichtung zur Erkennung handgeschriebener Muster nach der vorliegenden Erfindung. Ein Benutzer zeichnet ein Muster auf ein Tablett 100 unter Verwendung eines Stiftes 101. Das Tablett 100 tastet periodisch die Koordinaten des handgeschriebenen Musters ab und sendet ein Koordinatensignal zum Mustererkennungsapparat 200.
Der Mustererkennungsapparat 200 umfaßt eine Tablett-Dateneingabeeinheit 201, die aufeinanderfolgend das Koordinatensignal für jeden Strich (von der Stift-Ab- bis zur Stift- Aufbewegung) einliest, eine Segmentierungseinheit 202 zur Umwandlung der Tablett-Daten in geradlinige und gekrümmte Liniensegmente, eine Quantisierungseinheit 203 zur Quantisierung eines Winkels einer Linie, die den Start- und Endpunkt jedes Segments durch Richtungsschlüssen (z. B. 32 Richtungsschlüssel) verbindet, eine Normierungseinheit 204 zur Normierung der Segmentierungsdaten von der Segmentierungseinheit 202 zu einem Quadrat mit einer Seitenlänge von 100, eine Folgesteuerungseinheit 205 zum Aufstellen der quantisierten Daten in eine eindimensionale Eingangsdatenfolge in Übereinstimmung mit den normierten Daten und Umformung einer Standardmusterinformation, die von einem Speicher 300 ausgelesen wurde, in eine eindimensionale Standarddatenfolge, eine Differenzberechnungseinheit 206 zum Vergleich der eindimensionalen Eingabedatenfolge mit der eindimensionalen Standarddatenfolge, um eine Differenz zwischen beiden zu berechnen, eine Übereinstimmungseinheit 207 zur Feststellung einer Übereinstimmung der Eingabedaten und der Standarddaten, die vom Speicher 300 ausgelesen wurden, durch Vergleich der berechneten Differenz mit einem vorgegebenen Wert, eine Musterausgabeeinheit 208 zur Ausgabe der Standardmusterdaten bei Feststellung der Übereinstimmung durch die Übereinstimmungsfeststellungseinheit 207, in einem Bitmusterspeicher (nicht gezeigt) als ein erkanntes Zeichen und zu dessen Darstellung auf einer Kathodenstrahlröhre CRT 400 durch ein Videosignal, und eine Segmentanzahländerungseinheit 209 zur Verringerung der Anzahl der Segmente des vorliegenden Strichs oder zur Addition der Tabletteingangsdaten des nächsten mit dem Standardmuster zu vergleichenden Striches, wenn keine Übereinstimmung durch die Übereinstimmungsfeststellungseinheit 207 festgestellt wird, um den Erkennungsprozeß zu wiederholen. Diese Schritte werden durch die CPU 210 ausgeführt. Die Musterausgabeeinheit 208 gibt den Inhalt des Bitmusterspeichers zu einem Drucker 500 aus, um eine Kopie des erkannten Musters anzufertigen. Wenn das über die Tabletteingabeeinheit 201 eingegebene handgeschriebene Muster an der CRT 400 wiedergegeben werden soll, können die Tabletteingabedaten zur Ausgabeeinheit 208 gesendet werden, wie das durch eine gestrichelte Linie in Fig. 3 gezeigt ist.
Ein Flußdiagramm eines Programms, das durch die CPU 210 im Mustererkennungsapparat 200 der Fig. 3 ausgeführt wird, ist in Fig. 4 gezeigt. Die Schritte in Fig. 4 werden später im Detail beschrieben und nur eine kurze Erläuterung wird davon hier gegeben.
Im Schritt 10 werden Arbeitsbereiche, die für die folgenden Schritte erforderlich sind, vorbereitet (initialisiert) und vom Benutzer werden bestimmte Werte gesetzt. Im Schritt 20 wird die Koordinatenpunktfolge P vom Tablett 100 abgetastet durch Anwendung einer Distanz zwischen den Koordinatenpunkten als Schwellenwert und die Koordinatendaten werden im Speicher 300 gespeichert. Der Schritt 20 dauert an, bis der Stift 101 vom Tablett abgehoben wird. Ein Koordinatenursprung wird am linken unteren Rand der CRT 400 angeordnet, wobei die CRT 400 eine Auflösung von 1700 Punkten in der horizontalen und 2300 Punkten in der vertikalen Richtung hat, und der Koordinatenwert stimmt mit den Punkten auf dem Schirm der CRT 400 überein.
Im Schritt 30 wird eine Linie, die den Start- und den Endpunkt der Koordinatenfolge für einen Strich (von Stift-Abbis Stift-Aufbewegung), die im Speicher 300 sich befindet, definiert und eine Fläche A, die von dieser Linie und den Segmenten, die die betreffenden Punkte der Datenfolge umschließen, wird bestimmt, um die Datenfolge in Segmentdaten umzuwandeln. Wenn die Fläche A kleiner als ein vorbestimmter Grenzwert ATH (z. B. 100) ist, dann wird die Segmentfolge durch die Linie ersetzt, die den Start- und den Endpunkt der Datenfolge verbindet. Wenn A > Ath ist, wird die Datenfolge in mehrere Segmentdaten umgewandelt mittels eines Mittelpunktsverfahrens, das im Detail erläutert wird. Wenn ein absoluter Wertwechsel oder die Differenz eines Winkels zwischen benachbarten Segmenten kleiner als ein vorbestimmter Winkel (z. B. 12 Grad) ist und dessen Vorzeichen gleich der des Wechsels oder der Differenz zwischen unmittelbar vorangehenden zwei Segmenten und ein Längenverhältnis innerhalb eines vorbestimmten Bereiches ist (z. B. 0,5 bis 2,0), werden diese zwei Segmente als Teil einer Kurve betrachtet. Der vorstehende Prozeß wird für alle Segmentdaten durchgeführt, so daß die Datenfolge in Serien- und/Kurvensegmentdaten umgewandelt wird. Da dieser Prozeß die Flächenmethode bei der Segmentierung anwendet, kann das Zittern wirkungsvoll absorbiert werden durch die zutreffende Wahl des Schwellenwertes Ath.
In Schritt 40 werden die Winkel eines jeden geraden Liniensegments und der Winkel der Linie, die den Start- und den Endpunkt eines jeden gekrümmten Liniensegments verbindet, durch Richtungskodes quantisiert, z. B. durch 32 Richtungswerte. Für das gekrümmte Segment, um es vom geraden Liniensegment zu unterscheiden, wird "32" hinzuaddiert, wenn die Segmentdrehung im Uhrzeigersinn ist (linksgerichtete Ausdehnung) und "64" wird addiert, wenn die Drehrichtung gegen den Uhrzeigersinn ist (rechtsgerichtete Ausdehnung), jeweils zum Richtungsschlüssel der Linie.
Im Schritt 50 werden die Segmentdaten für einen Strich normiert auf ein Quadrat mit einer Seitenlänge von z. B. 100, um die Verbindungsbeziehung der Segmente bei den Segmentdaten zu prüfen, die im Schritt 30 gebildet wurden. Wenn die Distanz zwischen den Endpunkten von zwei Segmenten kürzer als eine vorgegebene Länge ist (z. B. 5), dann wird festgestellt, daß sie in der Verbindungsbeziehung stehen und die Information über Start- und Endpunkte, Bestimmungssegmentnummer und die Information über Start- und Endpunkte des Bezugssegments werden in der Verbindungsliste registriert.
Im Schritt 60 werden die Segmentdaten in einer ansteigenden Reihenfolge der x-Koordinaten der Endpunkte der Segmente sortiert, um eine Segmentrichtungskodefolge in einer vorbestimmten Vorwärtsrichtung zu schaffen aufgrund der quantisierten Daten, die im Schritt 40 gebildet wurden, und der Verbindungsliste, die im Schritt 50 geschaffen worden ist, wobei die Richtungskodes aufeinanderfolgend miteinander verbunden sind, beginnend vom ersten Segment in der sortierten Liste aufgrund der Verbindungsliste, um eine Datenfolge zu bilden, die dann gespeichert wird.
Im Schritt 70 wird eine Differenz zwischen der im Schritt 60 gebildeten Datenfolge und einem im Speicher 300 befindlichen Standardmuster GST bestimmt.
Im Schritt 80 wird die Differenz F des Schritts 70 mit einem vorgegebenen Schwellenwert F&sub0;(z. B. 10) verglichen, um die Übereinstimmung zu bewerten, und falls F ≤ F&sub0; wird das zu prüfende Muster GST, das zur Differenz F führte, als erkanntes Muster Gr ausgegeben. Andererseits, wenn F > F&sub0; ist, scheitert die Erkennung und der Prozeß wird mit dem Schritt 90 fortgesetzt.
Im Schritt 90 wird das Segment mit einer niedrigen Segmentnummer oder das mit der letzten Segmentnummer entfernt, um für die dynamische Programmierung (DP) der segmentierten Daten neu segmentierte Daten zu bilden. Dann geht der Prozeß weiter zu Schritt 50. Die vorstehenden Schritte werden wiederholt und, wenn die zu entfernenden Daten nicht mehr vorhanden sind, werden alle Segmentdaten wieder hergestellt (recovered), und der Prozeß wird im Schritt 20 weitergeführt, wo neue Segmentdaten addiert werden.
Durch die Schritte 10 bis 90 werden die Anzahl der Striche und die Teilung des Eingabemusters voneinander unabhängig gemacht, und die Mensch-Maschine-Dialogfähigkeit ist gegenüber dem Mustereingabeverfahren nach dem Stand der Technik bedeutsam verbessert.
Da die Verarbeitung des On-line-Apparats 200 von Fig. 3 im Echtzeitbetrieb erfolgt, arbeitet der vorliegende Apparat als ein On-line-Apparat zur Erkennung handgeschriebener Muster.
Um die Beschränkungen hinsichtlich der Anzahl der Striche, der Reihenfolge der Striche, der Drehung und der Grenzen des über das Tablett 100 eingegebene Muster zu beseitigen, ist die vorliegende Erfindung unter der Voraussetzung konstruiert, daß die Elemente des Musters Segmente sind und daß die Folge der Muster durch die Reihenfolge der Verbindungen der Segmente und der Winkeldifferenzen bestimmt ist.
Die Anzahl der Striche ist gleich derjenigen, die erforderlich ist, um ein Muster zu zeichnen, wobei jeder Strich durch die Stiftab- und Stiftaufbewegung definiert ist, und die Reihenfolge der Striche ist diejenige beim Zeichnen des Musters, die Drehung ist ein Winkel des eingegebenen Musters bezüglich des Standardmusters und die Grenze ist eine Angabe einer Fläche entsprechend dem Muster in den eingegebenen Strichen, verglichen mit dem Muster im Verzeichnis.
Zwei charakteristische Teile der vorliegenden Erfindung sind aus dem Flußdiagramm der Fig. 4 entnommen und sind in Fig. 5 separat gezeigt. Diese sind ein Segmentierungsschritt 600 zur Bestimmung der Übereinstimmung mit dem Muster des Verzeichnisses und ein eindimensionaler dynamischer Programmierschritt 700 zur Erkennung des Musters aus den eingegebenen Strichen.
Der Segmentierungsschritt 600 umfaßt einen Teilsegmentierungsschritt 610 zur Segmentierung der Striche in Grundeinheiten für die Verarbeitung, einen Schlüsselumhüllungsschritt 620 zur Führung des Musters, um es zur Schaffung einer Kodeliste zu umhüllen ("to wrap"), und einen Differenzberechnungsschritt 630 durch einen Wechsel der Winkeldifferenz unabhängig von der Drehung des eingegebenen Musters.
Bei der vorliegenden Erfindung behebt der Schritt 600 die Beschränkungen bezüglich der Anzahl der Striche und der Drehung und der eindimensionale DP-Segmentierungsschritt 700 rekonfiguriert die Elemente, um die Einschränkungen bezüglich der Grenze zu beheben.

(1) Ausführung der Verarbeitung

Das eingegebene handgeschriebene Muster wird in Übereinstimmung mit dem Flußdiagramm in Fig. 5 verarbeitet. Hauptschritte der vorliegenden Erfindung werden nachfolgend beschrieben.

1. Teilsegmentierung des Striches (Schritt 610)

Das vom Tablett 100 eingegebene handgeschriebene Muster wird als Satz von Abtastpunkten für jeden Strich gelesen. Es muß in mehr als ein Segment umgewandelt werden.
Die Richtung des Segments vom Start- zum Endpunkt wird durch die Richtungskodes, die in Fig. 6 gezeigt sind, quantisiert.

2. Schlüsselumhüllung (Schritt 620)

Aufgrund der Verbindungsinformation der Endpunkte der Segmentierungsdaten, die in 1. entnommen worden sind, wird eine Kodeliste (Schlüsselliste) L&sub4; (Fig. 10) mit den Richtungskodes erstellt. Die Segmentierungsdaten werden nachgeführt, um das eingegebene Muster zu umhüllen.

3. Berechnung der Differenz durch Winkelwechsel

Die Muster des Verzeichnisses (klassifiziert durch die Anzahl der Segmente), die in 1. teilsegmentiert worden sind, werden vom Speicher 300 ausgelesen und eine Kodeliste (L&sub5;) der Muster des Verzeichnisses wird durch die Verarbeitung in 2. erstellt, und eine Differenz zwischen zwei angrenzenden Richtungskodes in der Kodeliste L&sub4; wird mit der in der Kodeliste L&sub5; verglichen. fi stellt eine Einheitsdifferenz dar.
worin i = 2, 3, . . . n und ist die Anzahl der Segmente von L&sub5;. Ein Mittelwert von fi wird als Differenz F als handgeschriebenes Muster definiert. Im Idealfall, wenn F = 0, wird angenommen, daß das eingegebene Muster mit dem Muster des Verzeichnisses übereinstimmt.
Der Wert von F liegt jedoch gewöhnlich zwischen 0 und 10 und ein Mindestwert von F, der durch die Differenzen zwischen dem eingegebenen Muster und dem Muster des Verzeichnisses erhalten wird, wird für ein erkanntes Muster verwendet.

4. Umordnung der Elemente (Schritt 700, "Rekonfiguration der Elemente")

Wenn das eingegebene Muster eine Fortsetzung des Musters und die Verbindungslinie enthält, wird die Übereinstimmung zwischen dem eingegebenen Muster und dem Muster des Verzeichnisses nicht erzielt, weil die Muster im Verzeichnis Muster für Muster registriert sind. Folglich sollte eine Kombination von Elementen entsprechend dem Muster verglichen werden, nachdem das handgeschriebene Muster segmentiert worden ist. Die Bestimmung der Reihenfolge der zu entfernenden Elemente im Extraktionsprozeß beeinflußt unmittelbar die Anzahl der Wiederholungen des Erkennungsprozesses und damit auch die Verarbeitungszeit. Eine wirkungsvolle Extraktion ist daher erforderlich.
Der Extraktionsprozeß verwendet üblicherweise ein Verfahren mit allen Kombinationen der Segmente. Da jedoch eine große Anzahl von Verarbeitungen erforderlich ist, um das Muster zu extrahieren, wird bei der vorliegenden Erfindung das eindimensionale dynamische Programmierverfahren (DP) angewendet, das von einer Besonderheit des handgeschriebenen Musters Gebrauch macht. Als Ergebnis wird die Anzahl der Operationen zur Extrahierung des Musters um einen Faktor von zehn oder mehr im Vergleich mit dem Verfahren mit allen Kombinationen verringert. Die extrahierten Elemente werden in Übereinstimmung mit dem oben beschriebenen Erkennungsprozeß verarbeitet.

(2) Beschreibung des Prozesses

Der grundlegende Algorithmus zur Mustererkennung der unter (1) beschrieben worden ist, wird nachfolgend im einzelnen erläutert.

Teilsegmentierung der Striche (Fig. 7a bis 7f)

Die Daten der Abtastpunktkoordinate S&sub1; des am Tablett 100 eingegebenen handgeschriebenen Musters werden für jeden Strich (von Stiftab- bis zu Stiftaufbewegung) eingelesen.
Wie in Fig. 7a gezeigt ist, wird ein Bereich von einem Startpunkt SP&sub1; zu einem Endpunkt SPn der abgetasteten Punktkoordinatendaten S&sub1;, abgeleitet vom handgeschriebenen Muster, als eine nichtidentifizierte Fläche (UA) bezeichnet, der Anfangspunkt SP&sub1; wird als ein Startpunkt (UAS) der nichtidentifizierten Fläche bezeichnet, und ein Endpunkt SPn wird als ein Endpunkt (UAE) einer nichtidentifizierten Fläche bezeichnet.
Dann wird, wie in Fig. 7b gezeigt, eine Fläche A bestimmt, die begrenzt ist von der handgeschriebenen Linie S und einer Linie L, die den Start- und den Endpunkt der Linie S miteinander verbindet. Die Fläche A kann ohne weiteres durch ein graphisches Verfahren bestimmt werden.
Wenn die berechnete Fläche A kleiner als eine vorbestimmter Schwellenwert Ath ist, dann wird die handgeschriebene Linie S als gerade Linie betrachtet und die Registrierung des Segments wird ausgeführt.
Wenn die Fläche A größer als der Schwellenwert Ath ist, wird der Endpunkt zur Mitte zwischen dem UAS-Punkt und dem UAE- Punkt, wie in Fig. 7c gezeigt, geschoben und die Fläche A' wird berechnet.
Die Fläche A' wird wiederum mit dem Schwellenwert Ath verglichen, und wenn A' < Ath ist, wird der laufende Endpunkt als ein neuer UAS-Punkt gewählt und eine neue Linie L wird gezogen. Wenn A' ≥ Ath ist, dann wird der gegenwärtige Endpunkt als neuer UAE-Punkt, wie in Fig. 7e gezeigt, gewählt und eine Fläche A'' wird berechnet.
Der vorstehende Prozeß wird solange fortgesetzt, bis UA erschöpft ist, d. h. der UAE-Punkt erreicht den UAS-Punkt. Dann wird der Startpunkt bis zum Endpunkt als eine Linie betrachtet und die Registrierung des Segments wird durchgeführt. Dieses Verfahren wird als Mittelpunktverfahren bezeichnet.
Im Segmentregistrierungsschritt wird der Endpunkt des registrierten Segments als neuer Startpunkt gesetzt und der UAS-Punkt und der Endpunkt der handgeschriebenen Linie S wird als neuer Endpunkt UAE gesetzt.
Die Koordinaten SPj und SPk des Start- und Endpunktes des Segments L, der Auf-/Ab-Status des Stiftes STj und STk werden bei jedem Punkt und ein Winkel Rj,k der Linie, die den Start- und den Endpunkt verbindet, in der Segmentliste registriert, wie das in der Fig. 7f gezeigt ist. Diese Schritte werden fortgesetzt, bis alle handgeschriebenen Striche S registriert sind.

Schlüssel-Umhüllung ("code wrapping")

Bei diesem Prozeß ist es notwendig, eine Verbindungsbeziehung der Start- und der Endpunkte der Elemente des Segments zu prüfen. Die Normierung des eingegebenen Musters und die Erstellung der Verbindungsliste werden erläutert.
Die Fig. 8a und 8b veranschaulichen die Normierung des Eingabemusters (z. B. eines Dreiecks). Wie in Fig. 8a gezeigt, wird eine größere Ausdehnung (li) in x-Richtung und eine Ausdehnung in y-Richtung des Eingabemusters vergrößert oder verkleinert zu einer normierten Größe (ln). Daher wird, wie in Fig. 8b gezeigt, der Startpunkt und der Endpunkt in der Segmentliste L&sub1; mit einem Faktor ln/li vergrößert, um eine normierte Segmentliste L&sub2; zu erstellen.
Die Erstellung der Verbindungsinformation der Endpunkte der Segmente wird nun mit Bezug auf Fig. 9 erläutert. Die Fig. 9(a) zeigt ein normiertes Eingabemuster (Dreieck).
Wie in Fig. 9(b) gezeigt ist, werden 5 bis 10% der normierten Größe ln als Verbindungsdistanz der Endpunkte der Segmentelemente gesetzt. Wenn die Distanz zwischen den Endpunkten der Segmente kürzer als die Verbindungsdistanz ist, wird angenommen, daß die zwei Endpunkte in Verbindung stehen. Diese Information wird in eine Verbindungsliste L&sub3;, wie in Fig. 9(c) gezeigt, eingeschrieben. Im gezeigten Beispiel hat das Segmentelement 1 zwei Verbindungsinformationen, "der Startpunkt ist in Verbindung mit dem Startpunkt des Segmentelements 3" und "der Endpunkt ist in Verbindung mit dem Startpunkt des Segmentelements 2".
Die Schlüsselumhüllung ("code wrapping") mittels der Segmentverbindungsliste L3 und der normierten Segmentliste L&sub2; wird mit Bezug auf Fig. 10 erklärt.
Der Startpunkt der Umhüllung der Segmentelemente kann bei jedem beliebigen Segmentelement liegen. In Fig. 10 werden die Segmentelemente im Uhrzeigersinn verfolgt, angefangen vom äußersten linken Endpunkt.
1. In Fig. 10(a) wird das Segmentelement bestimmt, das den äußersten linken Punkt aufweist.
2. Der in 1. bestimmte Endpunkt wird als neuer Startpunkt bestimmt und ein Segmentelement (Element 1), das der y-Richtung am nächsten kommt, wird vom Segmentelement gewählt, das den Startpunkt aufweist, und die Segmentelemente, die mit dem Startpunkt verbunden sind, und ein Richtungsschlüssel (4 in diesem Fall, siehe Fig. 6), vom Startpunkt aus betrachtet, wird in der Kodeliste L&sub4; registriert.
3. Es ist aus der Segmentverbindungsliste L&sub3; (Fig. 9(c)) ersichtlich, daß der Startpunkt des Segmentelements 1 in Verbindung mit dem Segmentelement 3 ist. Deshalb wird ein Richtungsschlüssel (28), in Verfolgungsrichtung gesehen, in der Kodeliste L&sub4; registriert.
4. Die Kodeliste L&sub4; wird auf die gleiche Weise erstellt wie die in 3. Wenn es ein Eingabesegmentelement gibt, das noch nicht für die Umhüllung verwendet worden ist, wird der Prozeß mit Start bei 1. wiederholt. Wenn kein solches Element vorliegt, wird der Prozeß beendet. Durch diesen Prozeß wird eine Kodeliste L&sub4; mit Eintragungen im Uhrzeigersinn, bezogen auf das Eingabemuster, erstellt, wie das in Fig. 10(d) gezeigt ist.
Ein Verfahren zur Berechnung der Differenz zwischen dem Eingabemuster und dem Muster im Verzeichnis wird erläutert.
Die Fig. 11 zeigt ein Flußdiagramm für die Differenzberechnung durch Wechsel des Winkels. Im Schritt 651 wird die Differenz ΔR' zwischen den Richtungskodes von zwei benachbarten Segmenten des eingegebenen Musters, berechnet aufgrund der Kodeliste L&sub4;. Im Schritt 652 wird eine Differenz ΔR zwischen den Richtungskodes des Musters des Verzeichnisses, ausgelesen vom Speicher 300, berechnet. Im Schritt 653 wird ein Absolutwert der Differenz zwischen den Richtungskodes des eingegebenen Musters und der Differenz zwischen den Richtungskodes des Musters des Verzeichnisses berechnet. Im Schritt 654 wird ein Mittelwert der absoluten Werte für alle Richtungskodedifferenzen berechnet, um eine Differenz F zu bestimmen. Im Schritt 655 wird die Differenz F mit einem vorbestimmten Wert verglichen, und wenn die Differenz gleich oder kleiner als der vorbestimmte Wert ist, dann wird festgestellt, daß das eingegebene Muster mit dem aus dem Verzeichnis ausgelesenen Muster übereinstimmt, und der Differenzberechnungsschritt 630 wird beendet. Wenn andererseits die Differenz F größer als der vorbestimmte Wert ist, wird festgestellt, daß das eingegebene Muster nicht mit dem aus dem Verzeichnis ausgelesenen Muster übereinstimmt, und der Prozeß geht zurück zum Schritt 651, bei dem die Differenzen der Richtungskodes des Musters im Verzeichnis umgeordnet werden und die Differenzberechnung wiederholt wird.
Mit Bezug auf Fig. 12 wird die Differenzberechnung speziell erklärt.

Differenzberechnung durch Wechsel des Winkels

Aufgrund der Kodeliste L&sub4;, die im Kodeumhüllungsprozeß erstellt wurde, wird die Übereinstimmungsfeststellung mit dem Muster im Verzeichnis durchgeführt.
Zuerst werden die folgenden drei Winkeldifferenzdaten aus der Kodeliste L&sub4; entnommen.
Ra = L&sub4;(2) - L&sub4;(1)
Rb = L&sub4;(3) - L&sub4;(2)
Rc = L&sub4;(4) - L&sub4;(3)
Für die Winkeldifferenzen Ra bis Rc des in Fig. 12(a) gezeigten Eingabemusters und die Winkeldifferenzdaten R&sub1; bis R&sub3; oder R&sub1;' bis R&sub3;' des Musters im Verzeichnis werden Summen f&sub1;, f&sub2;, . . . der absoluten Werte der Differenzen zwischen den entsprechenden Daten berechnet, wie in Fig. 12(b) gezeigt. Wie in Fig. 12(c) gezeigt, wird das Muster des Verzeichnisses, das den minimalen Wert fi für das eingegebene Muster ergibt, bestimmt und als erkanntes Muster (Fig. 12(d)) ausgegeben.
Wenn in Fig. 12 angenommen wird, daß
Ra = 24, Rb = -12, Rc = -12,
R&sub1; = 23, R&sub2; = -12, R&sub3; = -11
R&sub1;' = 20, R&sub2;' = -8, R&sub3;' = -12
dann ist f&sub1; = 2 für das Muster A und f&sub2;= 8 für das Muster B. Durch Mittelwertbildung von f&sub1; und f&sub2; mit der Anzahl der Segmentelemente erhalten wir
f&sub1;/3 = 0,67 für das Muster A und f&sub2;/3 = 2,67 für das Muster B.
Somit ist das erkannte Muster das Muster A.

Rekonfiguration der Segmentelemente

Die Beschreibung der Teilsegmentierung der Striche zur Berechnung der Differenz (Segmentierungsschritt 600 in Fig. 5) beruht auf der Annahme, daß ein Teilmuster unabhängig von mehreren handgeschriebenen Mustern entnommen werden kann.
Es ist jedoch häufig der Fall, daß dann, wenn ein handgeschriebenes Flußdiagramm eingegeben wird, wie in Fig. 13(a) gezeigt, eine Verbindungslinie und ein Muster mit einem Strich zusammen gezeichnet werden.
Die Musterextrahierung durch den eindimensionalen Segment- DP-Schritt 700 von Fig. 5, die das dynamische Programmierverfahren (DP) verwendet, wird nun erklärt.
Die Musterextrahierung beruht auf dem Umstand, daß das handgeschriebene Muster in einer von drei Eingabereihenfolgen eingegeben wird:
(i) Verbindungslinie → Muster, (ii) Muster → Verbindungslinie, (iii) Verbindungslinie → Muster → Verbindungslinie. Es ist nämlich höchstwahrscheinlich, daß das für die Mustererkennung nicht erforderliche Segment als erstes oder letztes eingegeben wird. Folglich werden das erste eingegebene Segment und das letzte eingegebene Segment aus den vielen eingegebenen Eingabesegmenten entfernt, so daß das Musterteil rationell extrahiert wird.
Der vorstehende Prozeß wird speziell mit Bezug auf die Fig. 13a und 13b erklärt.
Die Fig. 13a zeigt ein teilsegmentiertes Eingangsmuster. Bei diesem Beispiel sollte das Element 1 entfernt werden. Die Fig. 13b zeigt die Rekonfiguration der Segmentelemente nach der eindimensionalen Segment-DP-Methode.
Zuerst werden die Segmentelemente 1 bis 4 eingegeben. Im ersten Schritt wird nur das zuletzt eingegebene Segmentelement entfernt. Im zweiten Schritt wird das zuerst eingegebene Segmentelement entfernt und die Extraktion erfolgt. Im dritten und den nachfolgenden Schritten beträgt die Anzahl der entfernten Segmentelemente zwei und das Muster kann nicht extrahiert werden, welche Elemente auch immer entfernt werden.
Auf diese Weise werden das erste und/oder das letzte Segmentelement von den eingegebenen Segmentelementen entfernt und die Extrahierung wird für das Muster ausgeführt, das eine hohe Erfolgsaussicht hat. Folglich wird das Muster rationell extrahiert.
In Übereinstimmung mit der vorliegenden Erfindung wird das handgeschriebene Muster in mehrere Segmente aufgeteilt in Übereinstimmung mit den charakteristischen Daten, die von der Linie, die zwei aus vielen Abtastpunkten des handgeschriebenen Musters verbindet, hergeleitet werden. Folglich kann (1) das Zittern im handgeschriebenen Zeichen wirkungsvoll absorbiert werden, und (2) das handgeschriebene Muster mit jeder beliebigen Anzahl von Strichen wird in Segmente aufgeteilt, so daß die Mustererkennung unabhängig von der Anzahl der Striche erfolgt. Folglich wird die Mensch- Maschine-Interaktion wirkungsvoll verbessert.
Ganz besonders, wie in Fig. 14a bis 14d gezeigt ist, sind die Beschränkungen bezüglich der Anzahl von Strichen, die Beschränkungen in der Reihenfolge der Striche, die Beschränkungen bezüglich der Drehung und der Grenze bedeutsam aufgehoben.
Zum Beispiel, wie in Fig. 14a gezeigt, was immer die Anzahl der Striche des eingegebenen Musters sein mag, das Muster wird in Segmente aufgeteilt und die Erkennung der Muster ist somit unabhängig von der Anzahl der Striche.
Wie in Fig. 14b gezeigt, wo immer der Startpunkt des Musters sein mag, die Segmente werden durch die Kodeumhüllungsmethode im Uhrzeigersinn angeführt, die Mustererkennung ist daher unabhängig von der Reihenfolge der Striche.
Sogar wenn das eingegebene Muster geneigt ist, wird die Differenz durch die Winkeldifferenz zwischen zwei anschließenden Segmenten bewertet. Folglich ist die Mustererkennung unabhängig von der Drehung des eingegebenen Musters (Fig. 14c).
Ferner, da das Musterteil aus den vielen Segmenten extrahiert werden kann (durch die eindimensionale Segment-DP- Methode) kann das Muster mit der Verbindungslinie ohne Grenze eingegeben werden (Fig. 14d).

Claims

1. Verfahren zur On-line-Erkennung eines handgeschriebenen Musters mit folgenden Schritten:

Aufeinanderfolgendes Abtasten (20) der Koordinaten-Information der Striche eines handgeschriebenen Musters;

Aufteilung (30) der Koordinaten-Information eines Striches in Linienabschnitte, die mindestens aus geraden Linien- oder gekrümmten Linienabschnitten bestehen;

Quantisierung (40) der Abschnitte durch Hinzufügung von Richtungs-Kode-Werten zu den Abschnitten, so daß die Richtung der Linie, die die Anfangs- und Endpunkte jedes Abschnittes verbindet, so klassifiziert ist, daß sie innerhalb eines von vorbestimmten Bereichen von Winkeln mit der X-Achse liegt; dadurch gekennzeichnet, daß das Verfahren die weiteren Schritte aufweist:

- Normalisierung (50) des eingegebenen Musters, das aus den quantisierten Abschnitten besteht und Anfertigung einer normalisierten Abschnittsliste (L2), die die normalisierten Anfangs- und Endpunkte der Abschnitte und deren Richtungs- Kodes enthält;

- Auffinden des Vorhandenseins oder des Fehlens von Verbindungen zwischen Anfangs- oder Endpunkten der Abschnitte und Anfertigung einer Verbindungsliste (L3), die diese Verbindungen angibt;

- Umformung (60) der Reihenfolge der aufeinanderfolgend quantisierten Linienabschnitte durch Auswählen eines Abschnittes, der den niedrigsten Endpunkt-X-Koordinaten-Wert der aufgelisteten Abschnitte besitzt und Aufstellen der Reihenfolge der quantisierten Daten, beginnend in einer Richtung von dem Endpunkt des ausgewählten Abschnittes und fortlaufendes Verfolgen der Grenze aufgrund der Verbindungsliste (L3) bei gleichzeitiger Anfertigung einer Kode-Liste (L4);

- Auslesen eines Musters aus einem Verzeichnis, das bereits in einem Speicher (300) gespeichert ist; und

- Berechnen (70, 80) eines Unterschied-Grades zwischen dem Eingabe-Muster und dem ausgelesenen Muster des Verzeichnisses durch Vergleichen beider aufgrund der Richtungs-Kodes und der umgeformten Reihenfolge der quantisierten Linienabschnitte in der Kode-Liste (L4), um dadurch das Eingabe-Muster zu erkennen.

2. Verfahren nach Anspruch 1, das ferner aufweist, daß nach der Berechnung des Unterschied-Grades (70) ein Schritt zur Änderung (90) der Anzahl der Linienabschnitte zur Fortsetzung der Erkennungsverarbeitung vorgesehen ist, wenn nicht Übereinstimmung (80) festgestellt wird.

3. Verfahren nach Anspruch 2, bei dem im Schritt zur Änderung der Anzahl der Linienabschnitte (90) der erste oder der letzte eingegebene Abschnitt entfernt wird, um die Muster-Erkennungs- Verarbeitung fortzusetzen.

4. Verfahren nach Anspruch 2, bei dem im Schritt zur Änderung der Anzahl der Linienabschnitte (90) die Koordinaten-Information eines nächsten Striches zur Koordinaten-Information des gegenwärtigen Striches addiert wird, um die Muster-Erkennungs- Verarbeitung fortzuführen.

5. Verfahren nach Anspruch 1, bei dem im Schritt zur Aufteilung (30) die Aufteilung durch Berechnung einer Fläche (A), die begrenzt ist durch eine Umhüllungslinie, die nacheinander die Koordinatenpunkte der Koordinateninformation eines Striches verbindet, und einer Linie, die den Anfangskoordinatenpunkt und den Koordinatenendpunkt der Koordinateninformation miteinander verbindet.

6. Verfahren nach Anspruch 5, bei dem der Schritt zur Aufteilung (30) die Teilschritte umfaßt:

- Vergleichen der berechneten Fläche (A) mit einem vorbestimmten Wert (Ath);

- die Linie, die den Anfangskoordinatenpunkt und den Endkoordinatenpunkt der Koordinateninformation verbindet, als einen angestrebten Linienabschnitt bezeichnen, wenn die berechnete Fläche kleiner als der vorbestimmte Wert ist; und

- die Umhüllungslinie in zwei Umhüllungslinien unterteilen, wenn die berechnete Fläche nicht kleiner als der vorbestimmte Wert ist, um den Schritt zur Aufteilung (30) weiterzuführen durch Vergleichen einer Fläche, die durch die unterteilte Umhüllungslinie und einer Linie, die den Anfangskoordinatenpunkt und den Endkoordinatenpunkt der unterteilten Umhüllungslinie verbindet, begrenzt ist, mit dem vorgegebenen Wert.

7. Verfahren nach Anspruch 5, bei dem im Schritt zur Aufteilung (30) zwei zusammenhängende Linienabschnitte als Teil einer Kurve behandelt werden, wenn die absolute Winkeldifferenz, gebildet durch die beiden Abschnitte, kleiner als ein vorbestimmter Winkel ist und deren Vorzeichen gleich dem der Winkeldifferenz zweier unmittelbar vorangehender Linienabschnitte ist und deren Längenverhältnis innerhalb eines vorbestimmten Bereiches liegt.

8. Verfahren nach Anspruch 1, bei dem beim Schritt zur Berechnung eines Unterschied-Grades (70) die Differenz der quantisierten Winkel von jeweils zwei in der umgeformten Reihenfolge aufeinanderfolgenden Linienabschnitten mit der entsprechenden Differenz des ausgelesenen Verzeichnis-Musters verglichen wird.

9. Eine Vorrichtung zur On-line-Erkennung handgeschriebener Muster zur Durchführung des Verfahrens nach Anspruch 1, mit:

- einem Lichtstift (101) zum Zeichnen eines zu erkennenden Musters auf einem Tablett (100);

- einer Koordinaten-Eingabeeinheit (201) zum Abtasten serieller Koordinaten-Information und der Lichtstift-Auf- und Abbewegungs-Information bei den Strichen eines handgeschriebenen Musters;

- einer Mustererkennungseinheit (200) zum Vergleichen der Eingabe-Information von der Eingabeeinheit für jeden eingegebenen Strich, angefangen mit der Lichtstift-Abbewegung und endend bei der Lichtstift-Aufbewegung, mit einer Standardmuster-Information, gespeichert in einem Speicher (300), zur Bestimmung einer Ähnlichkeit zwischen diesen;

- einer Muster-Erzeugungseinheit (400, 500) zur Bildung einer regenerierten Information des von der Mustererkennungs-Einheit erkannten Musters, dadurch gekennzeichnet, daß die Mustererkennungs-Einheit (200) umfaßt:

- Aufteilungsmittel (202) zur Umwandlung der eingegebenen Information von der Koordinaten-Eingabeeinheit in gerade und gekrümmte Linienabschnitte;

- Quantisierungs-Datenbildungsmittel (203) zur Quantisierung der Abschnitte durch Hinzufügung von Richtungs-Kode-Werten zu den Abschnitten, so daß die Richtung der Linie, die die Anfangs- und Endpunkte jedes Abschnittes verbindet, so klassifiziert ist, daß sie innerhalb eines von vorbestimmten Bereichen von Winkeln mit der X-Achse liegt;

- Normalisierungsmittel (204) zur Normalisierung des eingegebenen Musters, das aus den quantisierten Linienabschnitten besteht und zur Anfertigung einer normalisierten Abschnittsliste (L2), die die normalisierten Anfangs- und Endpunkte der Abschnitte und deren Richtungs-Kodes enthält;

- Mittel (210) zum Auffinden und Auflisten, bei einer Verbindungsliste (L3), das Vorhandensein oder des Fehlens von Verbindungen zwischen den Anfangs- und Endpunkten der Abschnitte;

- Mittel (205) zur Reihenfolgebildung zur Umformung der Reihenfolge der quantisierten Daten durch Auswählen eines Abschnittes, der den niedrigsten Endpunkt-X-Koordinaten-Wert der aufgelisteten Abschnitte besitzt, und zum Aufstellen der quantisierten Daten in einer vorbestimmten Reihenfolge, beginnend vom Endpunkt des ausgewählten Abschnitts, auf der Grundlage der Verbindungsliste (L3) der quantisierten Abschnitte bei gleichzeitiger Anfertigung einer Kode-Liste (L4);

- Unterschieds-Berechnungsmittel (206) zur Berechnung eines Unterschied-Grades zwischen der umgeformten quantisierten Daten-Reihenfolge mit einer Datenreihenfolge, abgeleitet von der Standardmuster-Information im Speicher (300);

- Übereinstimmungs-Erkennungseinheit (207) zur Erkennung einer Übereinstimmung der Eingabedaten und der Standarddaten durch Vergleichen des berechneten Unterschieds mit einem vorbestimmten Wert; und

- Abschnittsnummer-Änderungsmittel (209) zur Vergrößerung oder Verkleinerung der Anzahl der mit der Standardinformation zu vergleichenden Abschnitte, wenn der Unterschied größer als ein vorbestimmter Wert ist, um die Verarbeitung aufgrund der neu erstellten Daten fortzuführen, wenn Nichtübereinstimmung festgestellt wird.

10. Vorrichtung nach Anspruch 9, bei dem die Aufteilungsmittel (202) bestehen aus:

- Rechenmittel zur Berechnung einer Fläche, die begrenzt ist durch aufeinanderfolgende Verbindungspunkte des Abschnittmusters und einer Linie, die den Anfangs- und Endpunkt des Abschnittmusters verbindet;

- erste Entscheidungsmittel zur Bestimmung, ob das Abschnittmuster als gerade Linie oder nicht zu werten ist aufgrund der berechneten Fläche durch die Rechenmittel; und

- zweite Entscheidungsmittel zur Bestimmung, ob die durch die ersten Entscheidungsmittel als gerade Linien bestimmten Abschnitte ein Teil einer gekrümmten Linie sind.

11. Vorrichtung nach Anspruch 9, bei dem die Abschnitts-Änderungsmittel (209) einen Anfangszeiger und einen Endzeiger für die zu vergleichenden Abschnitte aufweisen, Mittel zur Vergrößerung oder Verkleinerung dieser Zeiger und Abschnitts-Fortschreibungsmittel zum Ersatz der Abschnitte durch neue Abschnitte, die durch diese Zeiger angezeigt werden.