DE69029188T2

DE69029188T2 - Auf Wahrscheinlichkeitclusterbildung gestützte Schriftzeichenerkennung

Info

Publication number: DE69029188T2
Application number: DE69029188T
Authority: DE
Inventors: Lawrence A Spitz; Lynn D Wilcox
Original assignee: Xerox Corp
Current assignee: Xerox Corp
Priority date: 1989-10-25
Filing date: 1990-10-25
Publication date: 1997-03-20
Anticipated expiration: 2010-10-26
Also published as: EP0425290B1; EP0425290A2; EP0425290A3; JPH03144875A; US5075896A; JP2991473B2; DE69029188D1

Description

Die vorliegende Erfindung bezieht sich auf Techniken zum Erkennen von Zeichen. Genauer gesagt bezieht sich die Erfindung auf Techniken, die einen Satz Wahrscheinlichkeitszeichen-Idenditäten verwenden, um ein unbekanntes Eingangszeichen zu erkennen.
Kundu, A., und Bahl, P., "Recognition of Handwritten Script: A Hidden Markov Model Based Approach", International Conference on Acoustics, Speech, and Signal Processing, New York, April 1988, Seiten 928-931, beschreiben eine auf Buchstaben basierende Worterkennungseinrichtung, deren Ausgang entweder das korrekt erkannte Wort oder ein kleiner Satz von Wörtern ist, der das korrekte Wort als eine seiner Hypothesen umfaßt. Seite 929 beschreibt einen Satz von Merkmalen, für die, mit Abtastbuchstaben, optimale Symbole erzeugt werden, und zwar unter Verwendung eines Vektor-Quantisier- Algorithmus und eines ungewichteten, euklidischen Abstands als die Abstandsmessung. Die Merkmalsvektoren jedes Buchstabens werden dann als eines der Symbole gemaß einem minimalen Abstandskriterium, der nahesten Nachbarregel, klassifiziert, und eine Wahrscheinlichkeit wird dann in Bezug auf das Symbol bestimmt. Diese Symbole werden dann zur Erkennung in Verbindung mit einem verdeckten Markov-Model verwendet. Goshtasby, A., und Ehrich, R.W., "Contextual Word Recognition Using Probabilistic Relaxation Labeling", Pattern Recoanition, Vol 21, No. 5,1988, Seiten 455462, beschreiben eine textabhängige Worterkennungstechnik, die eine wahrscheinlichkeitsmäßige Relaxationskennzeichnung verwendet. Wie in Bezug auf Fig. 1 dort beschrieben ist, umfaßt ein textabhängiges Worterkennungssystem ein Zeichenerkennungseinrichtungsmodul, das jedem Eingabezeichen 26 Zahlen zuordnet, die die Annahmen darstellen, daß das Zeichen in dem Eingang Kennzeichnungen von a bis z besitzt. Die Annahmen werden dann zu Wahrscheinlichkeiten transformiert. Der Ausgang der Zeichenerkennungseinrichtung ist tatsächlich eine Sequenz aus Sätzen, die als Substitutionssätze bezeichnet werden, wobei jeder davon die Alternativen für ein bestimmtes Zeichen mit einer Nicht-Null-Wahrscheinlichkeit enthält. Alle möglichen Worte würden durch Auswahl eines Zeichens von jedem der Substitutionssätze erhalten werden, allerdings ist nur eines der Worte, die von den Substitutionssätzen gebildet werden können, das korrekte Wort. Ein Nach-Prozessor identifiziert das korrekte Wort von der Sequenz der Substitutionssätze unter Verwendung textabhängiger Informationen aus der Sprache. Abschnitt 2, der auf Seite 456 beginnt, betrachtet die Haupt-Nach-Verarbeitungstechniken. Die Abschnitte 3 und 4 führen in Ergebnisse ein und beschreiben sie, die durch einen vorgeschlagenen Nach-Prozessor produziert sind, der Übergangswahrscheinlichkeiten von Zeichen verwendet, um die Kennzeichnungswahrscheinlichkeiten in einem Wort iterativ zu verbessern, bis die Wahrscheinlichkeiten konvergieren und ein einziges Wort bestimmen. Fig. 5 stellt dar, wie der Nach-Prozessor auf Ähnlichkeitsmessungen eines Eingabeworts arbeitet, die Messungen mit geringer Ähnlichkeit auf Null setzen und die verbleibenden Ähnlichkeiten zu Wahrscheinlichkeitswerten transformieren, auf die ein Relaxations-Prozeß iterativ angewandt wird, bis die am meisten konsistente Kennzeichnung erhalten ist.
Die US-A 4,773,099 beschreibt Musterklassifikationstechniken, die unbekannte Eingabezeichen klassifizieren. Während einer Vorverarbeitungsphase werden Referenzdaten analysiert, um "Ringcluster" für jede Klasse von Eingangsdaten zu bilden. Wenn die Eingangsdaten Zeichen sind, wird ein Satz Ringcluster jeder Zeichenklasse zugeordnet. Diese Ringcluster werden so gebildet, daß sie später während der Klassifikation eines unbekannten Eingabezeichens verwendet werden können. Wie in Bezug auf die Fig. 12-13 und den darauffolgenden Figuren dargestellt und beschrieben ist, produziert das Klassifikationsmodul einen Möglichkeitssatz, der eine Liste von Zeichen ist, die die unbekannten Zeichen sein könnten, mit zugeordneten Mnahmen. Wie zu Beginn in Spalte 23, Zeile 32, beschrieben ist, kann ein Möglichkeitssatz, der keine Zeichen-Kandidaten umfaßt, für eine Nachverarbeitung zu einem Buchstabierkorrekturmodul geschickt werden, das textabhängige Informationen verwendet, um es mit einem einzelnen Zeichen- Kandidaten zu ersetzen. Ein Möglichkeitssatz, der mehr als einen Zeichen-Kandidaten umfaßt, kann weiter zu anderen Modulen geschickt werden, wie beispielsweise eine Unterlinienprüfeinrichtung und ein Kontextmodul, so daß nur ein Zeichen-Kandidat in dem Möglichkeitssatz, nachdem diese Nachverarbeitung vervollständigt ist, verbleibt. Die Annahmen können dazu verwendet werden, um Zeichen zu kennzeichnen, die nicht mit Sicherheit wiedererkannt wurden, so daß sie durch einen Wortverarbeitungsoperator geprüft werden können. Die Annahmewerte können auch durch die Nachverarbeitungsmodule verwendet werden, um beim Auswählen eines der Zeichen-Kandidaten zu unterstützen.
Die US-A 3V969,698 beschreibt ein Clusterspeichergerät für eine Nachbehandlungsfehlerkorrektur in einer Zeichen- und Phonem-Wiedererkennung. Wie in Bezug auf Fig. 6 dargestellt und beschrieben ist, gibt ein Clusterspeichergerät Gruppen von gültigen Alpha-Worten als potentielle Kandidaten für die korrekte Form eines fehlerkannten Worts aus. Eine Übertragungsfunktion wird gemessen, um die Neigung für eine Fehllesung zu bestimmen und wird als eine Reihe von Gleichungen ausgedrückt wobei jede eine Wahrscheinlichkeit eines Zeichens darstellt, daß es zu einem falschen Ausgabezeichen verwechselt ist. Wie in Bezug auf Fig. 7 dargstellt und beschrieben ist, liefert ein Clusterspeichergerät eine Gruppe korrekter Worte, die dieselbe Wahrscheinlichkeit dahingehend besitzt, daß sie mit einem ungültigen Wort zu einem regionalen Kontextgerät verwechselt worden ist. Das regionale Kontextgerät führt eine konditionsmäßige Wahrscheinlichkeitsanalyse aus, um zu bestimmen, welches der korrekten Worte am ehesten dem ungültigen Wort entspricht.
Kahan, 5., Pavlidis, T., und Baird, H.S., "On the Recognition of Printed Characters of Any Font and Size", IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol PAMI-9, No. 2, März 1987, Seiten 274-288, beschreiben eine Omnifont-Zeichenerkennung mit variabler Größe. Abschnitt III beschreibt einen primären Klassifizierer, der ein Zeichen von einer strukturellen Beschreibung mit einem statistischen Bayesian-Klassifizierer erkennt, der binäre Merkmale benutzt. Ein Merkmal definierende Bereiche in einem Parameterraum werden durch einen automatischen Clusterbildungsalgorithmus ausgewählt, der Cluster produziert, wie dies in Fig. 5 dargestellt ist. Die Cluster werden zu etwa 100 Clustern mit bestimmtem Hub gestrichen bzw. gestrafft, wobei 30 davon in Fig. 8 dargestellt sind. Der Ausgang des primären Klassifizierers ist eine kurze Liste von Klassifikationen, in abfallender Reihenfolge einer geschätzten a posterion Wahrscheinlichkeit. Abschnitt I, beschreibt, wie eine Konturanalyse auch verwendet wird, wenn das Ergebnis einer Klassifikation in eine von wenigen suspekten Konfusionsgruppen fällt.
Abschnitt VI beschreibt eine Feldanordnung von Strukturen, wobei jede aus einer Bondingbox und den ersten k-Auswahlen des Klassifizierers besteht, wobei jede Auswahl aus einem Namen und einer Figur einer Übertragungsgüte proportional zu dem Logarithmus der Posterior-Wahrscheinlichkeit besteht. Ein Layout-Kontext und ein linguistischer Kontext werden dann verwendet, um eine eindeutige Aussage zu machen, wobei der linguistische Kontext Buchstabierungs-Grammatik- und Punktuationsregeln umfaßt. Abschnitt VII beschreibt eine Buchstabierkorrektur falsch buchstabierter Worte.
Nagy, G., "Optical Character Recognition--Theory and Practice" in Krishnaiah, P.R., und Kanal, L.N., eds., Handbook of Statistics. Vol 2, North-Holland, 1982, Seiten 621 und 633-643, präsentieren eine Übersicht von Zeichenerkennungstechniken. Die Seiten 634-639 beschreiben verschiedene Maßnahmen für eine Zeichenklassifikation und besprechen die konditionsmäßigen Wahrscheinlichkeitsfunktionen P(v/ak) eines Beobachtens des Signals v, wenn die Klasse des Musters, die betrachtet wird, ak ist. Seite 634 erwähnt die Möglichkeit einer Zurückweisung eines Zeichens, d.h. ein Nichtzuordnen von diesem zu irgendeiner Klasse, wie dies in Fig. 5 dargestellt ist, als eine "Zurückweisungs-" Entscheidung; Seite 634 erwähnt auch, daß die optimale Entscheidung aus einer Auswahl der Klasse ak besteht, für die eine a posterion Wahrscheinlichkeit P(ai/v) die größte ist, und liefert eine Baye'sche Formel zur Berechnung der a posterion Klassenwahrscheinlichkeiten. Die Seiten 639-643 beschreiben Erkennungstechniken, die textabhängige Informationen verwenden.
Bozinovic, R., und Srihari, S.N:, "Knowledge-based Cursive Script Interpretation". Seventh International Conference on Pattern Recognition. Montreal. Canada. July 30-August 2.1984. Proceedings, Vol 2, Seiten 774-776, beschreiben eine auf einer Kenntnis basierende Maßnahme für eine Wortniveau-Offline-Kursiv- Schriftart-Erkennung. Wie in Abschnitt I in Bezug auf Fig. 1 dargestellt und beschrieben ist, umfaßt der Gesamtprozeß eine Vorsegmentierung, eine Lexikon-Durchsicht und ein Buchstabenhypothesieren und führt zu einem ASCII-Wort. Abschnitt III beschreibt eine Vorsegmentierung, eine Buchstaben-Hypothesierung und eine lexikale Darstellung, wobei das Lexion in der Form eines Baums organisiert ist.
Die US-A-3,643,215 beschreibt eine Mustererkennungsvorrichtung, in der ein Muster, das zur Klassifizierung präsentiert ist, anfänglich gesucht wird und Deskriptoren produziert werden, wie dies in Bezug auf die Fig. 1 und 3 dargestellt und beschrieben ist. Die Deskriptoren werden dazu verwendet, eine Liste aus Merkmalsnamen zu erhalten, und um daraufhin eine Klassennamen-Vorhersage zu erhalten. Der Klassenname wird dann verwendet, ein Merkmal vorherzusagen. Ein Annahmekoeffizient bzw. -pegel wird gemäß dem Erfolg der Vorhersagen variiert, bis er einen Akzeptanzschwellwert übersteigt, wobei in diesem Fall der Klassenname geliefert wird, wie dies in Bezug auf die Fig. 2 und 3 dargestellt und beschrieben ist.
Burton, D.K., Shore, J.E. und Buck, J.T., "Isolated-Wort Speech Recognition Using Multisection Vector Quantization Codebooks", IEEE Transactions on Acoustics. Speech. and Signal Processing, Vol ASSP-33, No. 4, August 1985, Seiten 837-849, beschreiben eine Maßnahme für eine Spracherkennung isolierter Worte unter Verwendung einer Vektor-Quantisierung (VQ). Seite 837 beschreibt eine frühere Maßnahme, in der ein VQ-Codebuch für jedes Wort in dem Erkennungsvokabular durch Anwenden einer iterativen Clustertechnik zu einer Trainingssequenz erzeugt wird, die verschiedene Wiederholungen des Vokabularworts enthält. Der Clusterprozeß stellt jedes Vokabularwort als einen Satz unabhängiger Spektren dar. Das neue Verfahren beschreibt in dem Artikel eingearbeitete Zeitsequenzinformationen mittels einer Sequenz der VQ-Codebücher, die als Multisektions-Codebücher bezeichnet sind, was in weiterem Detail auf Seite 839 beschrieben ist. Wie auf Seite 838 beschrieben ist, werden neue Worte unter Durchführen einer VQ und eines Auffindens des Vielfachabschnitt-Codebuchs, das die kleinste durchschnittliche Verzerrung erreicht, klassifiziert.
Die US-A-4,783,804 beschreibt die Verwendung von Markow-Modellsprachmusterschablonen in einer Spracherkennung. Die Fig. 4-6 stellen Schritte bei der Formation von Markov-Modellschablonen dar und Fig. 5 stellt Schritte beim Separieren von Rahmenmerkmalssignalen in Clustern dar.
Die US-A-4,837,831 beschreibt Techniken zum Erzeugen und zum Verwenden von Vielfachwortklangmodellen in einer Spracherkennung. Ein Bereich einer akustischen Beschreibung einer Aussprache wird gegen Clustermodelle, die ähnliche Klänge von unterschiedlichen Worten darstellen, bewertet. Die sich ergebende Bewertung für jedes Cluster wird dazu verwendet, eine Wortbewertung für jedes Wort zu berechnen, das durch dieses Cluster dargestellt ist. Ein Untersatz von Vokabular-Worten wird für einen längeren Vergleich gegenüber der Aussprache ausgewählt.
Die vorliegende Erfindung liefert Techniken zum Erkennen eines Zeichen-Kandidaten basierend auf einer Zwischenerkennung eines Clusters aus Zeichenwahrscheinlichkeiten. Weiterhin schafft die Erfindung Techniken zum Verwenden einer Zeichenwahrscheinlichkeits-Clusteridentifiziereinrichtung bei einer Erkennung. Zum Beispiel kann die Clusteridentifiziereinrichtung dazu verwendet werden, nach Daten zu suchen, die Zeichenwahrscheinlichkeiten eines Clusters definieren.
Gemäß einem Aspekt der Erfindung wird ein Verfahren zum Identifizieren, welches verschiedener Zeichenwahrscheinlichkeitscluster am nahesten zu einem Zeichen-Kandidaten ist, geschaffen, wobei der Zeichen-Kandidat ein Teil eines Textes ist und separat zur Identifikation präsentiert wird, wobei das Verfahren die Schritte aufweist: Erhalten eines Satzes Wahrscheinlichkeitswerte für einen Zeichen-Kandidaten, wobei der Satz Wahrscheinlichkeitswerte einen jeweiligen Wahrscheinlichkeitswert für jeden eines Satzes von Zeichen-Typen umfaßt, wobei jeder Wahrscheinlichkeitswert eines Zeichen-Typs eine Wahrscheinlichkeit anzeigt, daß der Zeichen-Kandidat ein Fall des Zeichen-Typs ist; und Verwenden des Satzes Wahrscheinlichkeitswerte, um zu identifizieren, welcher einer Zahl Zeichenwahrscheinlichkeitscluster am nahesten zu dem Kandidaten ist, wobei die Zeichenwahrscheinlichkeitscluster-Bereiche eines Raums sind, wobei die Zeichen- Kandidaten in Bezug auf ihren Wahrscheinlichkeitswert für jeden Zeichen-Typ die Position des Zeichen-Kandidaten in der Dimension des Zeichen-Typs anzeigen, so daß der Satz der Wahrscheinlichkeitswerte die Position des Zeichen-Kandidaten in dem Zeichenwahrscheinlichkeitsraum definiert.
Gemäß einem anderen Aspekt der Erfindung wird ein System zum Verarbeiten von Daten geschaffen, das aufweist: einen Klassifizierer zum Liefern eines Satzes Wahrscheinlichkeitswerte für einen Zeichen-Kandidaten, wobei der Zeichen-Kandidat ein Teil eines Textes ist und separat zur Identifizierung präsentiert wird, wobei der Satz Wahrscheinlichkeitswerte einen jeweiligen Wahrscheinlichkeitswert für jeden eines Satzes Zeichen- Typen umfaßt, wobei jeder Wahrscheinlichkeitswert eines Zeichen-Typs eine Wahrscheinlichkeit anzeigt, daß der Zeichen-Kandidat ein Fall des Zeichen-Typs ist; eine Wahrscheinlichkeitscluster-Identifiziereinrichtung zum Verwenden des Satzes Wahrscheinlichkeitswerte, um Daten zu produzieren, die identifizieren, welcher einer Anzahl Zeichenwahrscheinlichkeitscluster am nahesten zu dem Zeichen-Kandidaten ist, wobei die Zeichenwahrscheinlichkeitscluster Bereiche eines Raums sind, wobei der Raum eine jeweilige Dimension für jeden der Zeichen-Typen umfaßt, wobei der jeweilige Wahrscheinlichkeitswert des Zeichen-Kandidaten für jeden Zeichen-Typ die Position des Zeichen-Kandidaten in der Dimension des Zeichen-Typs anzeigt, so daß der Satz Wahrscheinlichkeitswerte die Position des Zeichen-Kandidaten in dem Raum definiert; und eine Einschränkungs-Erfüllungseinrichtung zum Liefern von Daten, die einen Zeichen-Typ des Zeichen-Kandidaten basierend auf den das Cluster identifizierenden Daten von der Wahrscheinlichkeitscluster-Identifiziereinrichtung identifizieren.
Die Erfindung basiert auf der Erkennung eines fundamentalen Problems bei herkömmlichen Maßnahmen für eine Zeichen- und Phonemerkennung. Jeder Zeichen-Kandidat wird typischerweise als ein Fall eines einzelnen Zeichen-Typs klassifiziert; von einer kurzen Liste von Zeichen- oder Phonem-Typen, entweder einer festgelegten Länge oder die Wahrscheinlichkeiten besitzen, die einen festgelegten Schwellwert übersteigen; oder als ein fragwürdiges Zeichen, ein Zeichen, bei dem eine Schlußfolgerung nicht erreicht werden kann, da vielleicht keine der Möglichkeiten einen festgelegten Schwellwert übersteigt. Das Ergebnis einer Klassifikation wird zu einer Nachklassifiziereinrichtung oder einem Nachprozessor übertragen, bevor zu dem nächsten Kandidat in der Sequenz fortgefahren wird. Allerdings rangiert eine Klassifizierung auf diese Art und Weise nutzlos Informationen über andere Zeichen-Typen aus, die auf den Kandidaten angewandt werden können, Informationen, die oftmals bei der Erkennung nützlich sind. Die Erfindung basiert weiterhin auf der Erkenntnis, daß dieses Problem durch Heranziehen einer unterschiedlichen Maßnahme gelöst werden kann. Im Gegensatz zu einem Klassifizieren jedes Kandidaten als ein Fall eines einzelnen, wahrscheinlichsten Typs oder einer kurzen Liste wahrscheinlichster Typen identifiziert eine Technik gemäß der Erfindung, welcher eine einer Anzahl von Zeichenwahrscheinlichkeitsclustern am nahesten zu dem Kandidaten kommt, und zwar basierend auf einem vollständigen Satz von Wahrscheinlichkeiten für den Kandidaten. Die Wahrscheinlichkeitscluster werden in einem Zeichenwahrscheinlichkeitsraum definiert, wobei jeder Cluster eine jeweilige Wahrscheinlichkeit für jeden Zeichen-Typ in einem Satz von Zeichen-Typen besitzt. Deshalb liefert eine Identifizierung, welcher Cluster am nahesten zu einem Kandidaten kommt, relativ akkurate Informationen über seine Wahrscheinlichkeit für irgendeinen Typ.
Ein anderer Aspekt der Erfindung basiert auf der Erkennung eines fundamentalen Problems in der Architektur herkömmlicher Zeichenerkennungssysteme. Solche Systeme halten herkömmlich alle Informationen über einen Kandidaten zurück, bis der Kandidat als ein Fall eines einzelnen, wahrscheinlichsten Typs oder eines einer kleinen Zahl von wahrscheinlichsten Typen klassifiziert ist. Daten, die den wahrscheinlichsten Typ oder die Typen anzeigen, können dann zu einer Nachklassifiziereinrichtung oder einem Nachprozessor geliefert werden. Um vollständige Informationen über einen Kandidaten zwischen Prozessen oder Prozessoren zu übertragen, würde eine höhere Bandbreite erfordern, die mit der herkömmlichen, niedrigen Bandbreitenverbindung zwischen einer Klassifiziereinrichtung und einer Nachklassifiziereinrichtung in Wechselwirkung treten würde, die für eine Modularisierung notwendig ist. Eine Modularisierung ist wichtig, da sie ermöglicht, daß unterschiedliche Nachklassifiziereinrichtungen mit einer gegebenen Klassifiziereinrichtung verwendet werden können, und ermöglicht auch, daß unterschiedliche Klassifiziereinrichtungen mit einer gegebenen Nachklassifiziereinrichtung verwendet werden können. Kurz gesagt ist es schwierig, ein System zu schaffen, das modular ist und das vollständige Informationen zu einer Nachklassifiziereinrichtung oder einem Nachprozessor liefert.
Dieser Aspekt basiert weiterhin auf der Erkenntnis, daß die Verbindung mit geringer Bandbreite zwischen Modulen eines Erkennungssystems nicht die Übertragung relativ vollständiger Informationen über jeden Kandidaten ausschließt. Anders ausgedrückt kann ein eingangsseitiges Modul eines Erkennungssystems relativ vollständige Informationen über jeden Kandidaten zu einem ausgangsseitigen Modul liefern, das eine weitere Verarbeitung durchführt.
Diese Lösung kann durch Vorsehen, und zwar für jeden Kandidaten, von Daten, die einen Wahrscheinlichkeitscluster identifizieren, der am nahesten zu dem Kandidaten in dem Zeichenwahrscheinlichkeitsraum ist und der eine jeweilige Wahrscheinlichkeit für jeden Erkennungstyp besitzt, ausgeführt werden. Die Datenidentifizierung jedes Clusters (nachfolgend hier als ein "Cluster"ID" bezeichnet) kann selbst dazu verwendet werden, um Daten zu erhalten, die einen Zeichen-Typ (nachfolgend als ein "Zeichen-ID" bezeichnet) über irgendeine geeignete Einschränkungs-Erfüllungstechnik identifizieren. Falls es notwendig ist, eine Übereinstimmung zu erzielen, kann das Cluster-ID dazu verwendet werden, eine jeweilige Wahrscheinlichkeit des Clusters für irgendeinen oder mehrere Typen zu suchen, geeignete Daten über die Wahrscheinlichkeiten, die während einer vorherigen Trainingsphase für ein Suchen während einer darauffolgenden Identifikationsphase gespeichert sind.
Diese Ausführung ermöglicht eine Modularität zwischen einer Wahrscheinlichkeitscluster-Identifiziereinrichtung und einer Einschränkungs-Erfüllungseinrichtung, und zwar mit einer Verbindung einer niedrigen Bandbreite zwischen ihnen zum Übertragen von Cluster-ID's. Während einer Trainingsphase speichert die Clusteridentifiziereinrichtung Daten über die Zeichenwahrscheinlichkeiten für jedes Cluster und während einer Identifikationsphase kann die Einschränkungs-Erfüllungseinrichtung ein Cluster-ID verwenden, um die entsprechenden Wahrscheinlichkeitsdaten zu suchen. Ein Vorteil dieser Lösung ist derjenige, daß während einer Identifikation die Einschränkungs-Erfüllungseinrichtung von der Wahrscheinlichkeitscluster-Identifiziereinrichtung nur abhängt, um eine Sequenz aus Cluster-ID's zu liefern. Als Folge kann die Einschränkungs-Erfüllungseinrichtung über einen willkürlich großen Kontext mit relativ vollständigen Informationen über jeden Kandidaten innerhalb dieses Kontextes arbeiten, wobei die Informationen in einer kompakten Form von den Cluster-ID's erhalten werden. Die Wahrscheinlichkeitscluster-Identifiziereinrichtung und die Einschränkungs-Erfüllungseinrichtung können unabhängig auf einem einzelnen Prozessor arbeiten oder können auf parallelen Prozessoren arbeiten, und in jedem Fall wird die Verwendung von Cluster-ID's eine relativ niedrige Bandbreiten-Verbindung zwischen den Prozessen ermöglichen.
Die vorliegende Erfindung wird nun beispielhaft unter Bezugnahme auf die beigefügten Zeichnungen beschrieben werden, in denen:
Fig. 1 zeigt ein schematisches Blockdiagramm, das einige funktionale Komponenten eines Erkennungssystems gemäß der Erfindung darstellt;
Fig. 2 zeigt ein Flußdiagramm, das Schritte darstellt, die durch eine Wahrscheinlichkeitscluster-Identifiziereinrichtung und eine Einschränkungs-Erfüllungseinrichtung der Fig. 1 durchgeführt werden;
Fig. 3 zeigt ein Flußdiagramm, das Schritte darstellt, die während einer Trainingsphase einer Wahrscheinlichkeitscluster-Identifiziereinrichtung durchgeführt werden;
Fig. 4 zeigt ein Flußdiagramm, das Schritte darstellt, die während einer Identifikationsphase durch eine Wahrscheinlichkeitscluster-Identifiziereinrichtung durchgeführt werden, und
Fig. 5 zeigt ein schematisches Diagramm, das die Komponenten eines Systems darstellt, das die Schritte in den Fig. 3 und 4 durchführen kann.

A. Konzeptmäßiger Aufbau

Der folgende, konzeptmäßige Aufbau ist zum Verstehen der Erfindung hilfreich und die Ausdrücke, die nachfolgend definiert sind, besitzen Bedeutungen, die durch diese Beschreibung hinweg angegeben sind, einschließlich der Ansprüche.
Ein "Wort" ist die kleinste Einheit einer Bedeutung in einer Sprache. "Geschriebene Worte" bedeutet Worte, die in der Form von diskreten Elementen, wie beispielsweise alphabetische, numerische oder piktogrammartige Elementen, aufgezeichnet sind. "Gesprochene Worte" oder "Sprache" bedeuten Worte, die in einer kontinuierlichen Form wie beispielsweise als Äußerung eines Sprechers, aufgenommen werden. Worte, die in kontinuierlicher Form aufgezeichnet sind, wie beispielsweise eine aufgezeichnete Sprache, sind deshalb nicht geschriebene Worte, sondern gespochene Worte, wenn sie abgespielt werden. Ein "isoliert gesprochenes Wort" ist ein gesprochenes Wort, das von irgendwelchen vorhergehenden oder nachfolgenden Worten diskret empfangen wird. Ein "Text" ist eine Anordnung von geschriebenen Worten, gewöhnlich eine Sequenz. Ein Text kann demzufolge Null oder mehr Worte umfassen, jedes mindestens mit einem diskreten Element.
Ein "Zeichen" bedeutet ein diskretes Element, das in einem Text erscheint. Zeichen können demzufolge nicht nur alphanumerische Elemente umfassen, sondern auch Punktuations-Markierungen, diakritische Zeichen und andere Elemente, die in einem Text enthalten sind. Ein "Zeichen-Typ" ist eine Kategorie, aus der ein Zeichen ein Fall sein kann, wie beispielsweise ein Buchstaben oder eine Zahl.
Ein "Zeichen-Kandidat" ist irgendein Teil eines Textes, der separat einem System zur Klassifikation oder Identifikation präsentiert wird. In typischen Zeichenerkennungssystemen ist ein Zeichen-Kandidat ein Teil des Textes, der auf der Basis von Kriterien segmentiert worden ist, die anzeigen, daß der Zeichen-Kandidat ein Zeichen ist. Ein "Kandidat" bedeutet ein Zeichen-Kandidat.
Ein "Zeichenwahrscheinlichkeitsraum", ist ein mathematischer Raum, in dem jede Dimension die Wahrscheinlichkeit anzeigt, daß ein Kandidat ein Fall eines spezifischen Zeichen-Typs ist.
Ein "Zeichenwahrscheinlichkeitscluster" ist ein statistisch definierter Bereich eines Zeichenwahrscheinlichkeitsraums, in dem Zeichen oder Zeichen-Kandidaten auftreten. Ein Zeichenwahrscheinlichkeitscluster kann zum Beispiel mittels der Wahrscheinlichkeiten der Zeichen und Zeichen-Kandidaten definiert werden, die in ihm oder durch ein anderes statistisches Maß seiner Mitte auftreten. Es könnte weiterhin durch die Varianz der Wahrscheinlichkeiten der Zeichen und Kandidaten definiert werden, die in ihm auftreten, oder durch ein anderes statistisches Maß seiner Form oder Größe.
Ein "Cluster" bedeutet ein Zeichenwahrscheinlichkeitscluster.
Ein "Cluster-ID" sind Daten, die einen eines Satzes von Clustern anzeigen. Ein "Zeichen-ID" sind Daten, die einen eines Satzes von Zeichen-Typen anzeigen. Der "Abstand" zwischen einem Cluster und einem Kandidaten kann durch den euklidischen Abstand zwischen Kandidatenwahrscheinlichkeiten oder irgendeinem anderen statistischen Maß eines Abstands definiert werden. Einer einer Zahl von Clustern ist "am nächsten" zu einem Kandidat, wenn der Abstand zwischen dem Cluster und dem Kandidaten kleiner als der Abstand zwischen irgendeinem der anderen Cluster und dem Kandidaten ist.
Eine "Einschränkungs-Erfüllungseinrichtung" ist irgendeine Komponente eines Systems, die bestimmt, ob Daten, die ihr präsentiert sind, einen Satz von Einschränkungen erfüllen. Eine Einschränkungs-Erfüllungseinrichtung könnte ein Prozeß, ein Prozessor oder irgendeine andere Komponente sein, die zum Bestimmen geeignet ist, ob Daten Einschränkungen erfüllen. Sie könnte die Einschränkungen in irgendeiner geeigneten Form handhaben, einschließlich Regeln oder Mustern oder irgendeiner Kombination von Regeln und Mustern.

B. Allgemeine Merkmale

Allgemeine Merkmale der Erfindung können anhand der Fig. 1 und 2 verstanden werden. Fig. 1 stellt einige Komponenten eines Systems, das Merkmale der Erfindung umsetzt, dar. Fig. 2 stellt Schritte dar, die durch Komponenten des Systems der Fig. 1 durchgeführt werden.
Fig. 1 stellt einige Komponenten eines Zeichenerkennungssystems 10 dar. Das System 10 kann auch andere, herkömmliche Komponenten, die nicht dargestellt sind, umfassen, wie beispielsweise eine Komponente, die Daten über einen Text, dessen Zeichen erkannt werden sollen, in Zeichen-Kandidaten segmentiert, und eine Komponente, die Daten enthält, die sich auf jeden Kandidaten bezieht, umfassen. Die Wahrscheinlichkeitscluster-Identifiziereinrichtung 12 empfängt Daten über jeden Kandidaten in einer Sequenz und die Daten, die sie empfängt, könnten, wie dargestellt ist, Wahrscheinlichkeitsdaten sein, die, für jeden erkennbaren Zeichen-Typ, die Wahrscheinlichkeit anzeigen, daß der Kandidat von diesem Typ ist. Die Identifiziereinrichtung 12 bestimmt, welcher einer Zahl von Clustern am nahesten zu jedem Kandidat ist, und die Cluster können Zeichenwahrscheinlichkeitscluster sein, wie dies vorstehend definiert ist. Unter Bestimmung, daß ein gegebenes Cluster am nahesten zu einem Kandidat ist, liefert die Identifiziereinrichtung 12 das entsprechende Cluster-ID als sein Ausgang.
Die Einschränkungs-Erfüllungseinrichtung 14 empfängt die Cluster-ID's von der Identifiziereinrichtung 12 und sucht nach relevanten Daten aus dem Speicher 16. Der Speicher 16 speichert illustrativ Regeln/Muster-Daten 181 die sich auf Regeln und Muster beziehen,die die Einschränkungs-Erfüllungseinrichtung 14 zum Bestimmen verwenden kann, ob eine Sequenz der Cluster-ID's relevante Beschränkungen erfüllt. Der Speicher 16 speichert auch Zeichen/Wahrscheinlichkeitsdaten 20, auf die basierend auf einem Cluster-ID zugegriffen werden kann, um die jeweilige Wahrscheinlichkeit eines spezifischen Zeichen-Typs für diesen Cluster zu erhalten. Basierend auf den gesuchten Daten und den Cluster-ID's erhält die Einschränkungs-Erfüllungseinrichutng 14 eine Sequenz von Zeichen-ID'S, die sie als ihren Ausgang liefert. Die Einschränkungs-Erfüllungseinrichtung 14 könnte alternativ Wort-Identifizierer als ihren Ausgang liefern.
Fig. 2 stellt Schritte dar,die durch die Wahrscheinlichkeitscluster-Identifiziereinrichtung 12, angezeigt durch die Buchstaben "CI" und die Einschränkungs-Erfüllungseinrichtung 14, angezeigt durch die Buchstaben "CS", durchgeführt werden.
In dem Kasten 30 empfängt die Identifiziereinrichtung 12 Daten für den nächsten Kandidaten, wie beispielsweise Wahrscheinlichkeitsdaten für die Zeichen-Typen,wie dies vorstehend besprochen ist. In dem Kasten 32 wird das naheste Cluster identifiziert und in dem Kasten 34 wird seine Cluster-ID ausgegeben, bevor zurückgekehrt wird, um Daten für den nächsten Kandidaten in dem Kasten 30 zu empfangen.
In dem Kasten 40 empfängt die Einschränkungs-Erfüllungseinrichtung 14 das nächste Cluster-ID von der Identifiziereinrichtung 12. In dem Fall eines Durchführens einer Einschränkungs-Erfüllung wird die Verzweigung in dem Kasten 42 basierend darauf, ob Daten über die jeweilige Wahrscheinlichkeit eines spezifizierten Zeichen-Typs in Bezug auf das Cluster-ID benötigt werden, durchgeführt. Falls dies der Fall ist, sucht der Schritt in dem Kasten 44 die erforderlichen Wahrscheinlichkeiten. Die Verzweigung in dem Kasten 46 hängt davon ab, ob eine Einschränkungs-Erfüllung erfolgreich ist; falls dies der Fall ist, liefert die Einschränkungs-Erfüllungseinrichtung 14 die identifizierten Zeichen- ID's als Ausgang in dem Kasten 48; falls dies nicht der Fall ist, kehrt sie zurück, um das nächste Cluster-ID in dem Kasten 40 zu empfangen.

C. Eine Ausführung

Die Erfindung könnte in einer Vielfalt von Arten und Weisen ausgeführt werden. Die Fig. 3-5 stellen eine Ausführung dar, die für einen einzelnen,seriellen Prozessor geeignet ist. Fig. 3 stellt Schritte in der Trainingsphase der Clusteridentifiziereinrichtung dar und Fig. 4 stellt Schritte in deren Identifikationsphase dar. Fig. 5 stellt Komponenten eines Systems dar, das die Schritte in den Fig. 3 und 4 ausführt.
Die Trainingsphase in Fig. 3 folgt allgemein den Schritten des Isodata-Algorithmus, der in Tou, J.T., und Gonzalez, R.C., Pattern Recognition Principles, Addison-Wesley, London, 1974, Seiten 97-100, beschrieben ist. Wie dort angemerkt ist, ist der Isodata-Algorithmus ähnlich im Prinzip zu einer K-Bedeutungsclusterbildung. Eine K-Bedeutungsclusterbildung oder irgendein anderer geeigneter Algorithmus könnten in der Trainingsphase verwendet werden, vorausgesetzt, daß das Ergebnis einen Satz von Clustern in einem Zeichen- oder Phonem-Wahrscheinlichkeitsraum ist, jeder mit einem jeweiligen Satz Wahrscheinlichkeiten und einem Cluster-ID. Die Koordinaten der Bedeutung oder einer anderen statistischen Mitte jedes Clusters können zum Beispiel als seine Wahrscheinlichkeiten dienen.
In dem Schritt im Kasten 100 wählt der Benutzer Anfangswahrscheinlichkeitsclusterzentren und -parameter, wie im Schritt I, des Isodata-Algorithmus aus. Diese Anfangsclusterzentren könnten zufällig ausgewählt werden. Die Zahl der Clusterzentren die erwünscht ist, könnte dreimal der Zahl der erkennbaren Zeichen sein. Die minimale Zahl der Proben pro Cluster könnte fünf sein. Die Standardabweichungsparameter könnten auf die minimale Komponente der Abtaststandardabweichung für alle Trainingsdaten eingestellt sein. Der Klumpenbildungsparameter könnte auf ein Drittel des Standardabweichungsparameters eingestellt werden. Die maximale Zahl der Paare der Clusterzentren, die zusammengeballt werden können, könnte auf zwei eingestellt werden. Die Zahl der Iterationen, die zugelassen ist, könnte anfänglich auf 100 eingestellt werden, abhängig davon, daß sie erhöht werden, wie dies eine Konvergenz und Computerzeit zuläßt.
Der Schritt in dem Kasten 102 dustert dann einen Satz Abtastwahrscheinlichkeitslisten und führt darauf bezogene Berechnungen durch, wie in den Schritten 2 bis 6 des Isodata-Algorithmus. Die Abtastwahrscheinlichkeitslisten sollten von demselben Klassifizierer erhalten werden,wie derjenige, der in der Identifikationsphase verwendet wird. Der Klassifizierer kann ein Entscheidungsbaum oder irgendein anderer, herkömmlicher Klassifizierer sein, der eine vollständige Wahrscheinlichkeitsliste für einen Kandidaten liefert. Um die Abtastwahrscheinlichkeitslisten für ein Clustern in dem Kasten 102 zu liefern, sollte der Klassifizierer auf einem Text oder einer Sprache arbeiten, die völlig für den Text oder die Sprache, die in der Identifikationsphase identifiziert werden soll, repräsentativ ist. Das Ergebnis eines Clusterns wird ein neuer Satz von Clusterzentren sein, jeder mit einem entsprechenden Zentrum, dessen Koordinaten eine vollständige Wahrscheinlichkeitsliste definieren.
Wenn eine Clusterbildung abgeschlossen ist, verzweigt sich die Trainingsphase in einen Kasten 110, basierend darauf, ob die abschließende Iteration durchgeführt worden ist. Falls dies nicht der Fall ist, spaltet der Schritt in dem Kasten 112 die Clusterzentren auf, klumpt Clusterzentren, falls geeignet, zusammen, ermöglicht dem Benutzer, neue Parameter einzustellen, und führt darauf bezogene Berechnungen, wie in den Schritten 7-13 des Isodata-Algorithmus, durch. Dann kehrt die Trainingsphase zurück, um die Abtastwahrscheinlichkeitslisten wieder zu dustern, und zwar in dem Kasten 102. Wenn die abschließende Iteration durchgeführt worden ist, speichert der Schritt in dem Kasten 114 für jedes abschließende Cluster sein ID und die Koordinaten seines Zentrums, die eine entsprechende Wahrscheinlichkeitsliste definieren. Dies vervollständigt die Trainingsphase.
Die Identifikationsphase in Fig. 4 beginnt in einem Kasten 120 durch Empfangen eines Satzes von Kandidatenwahrscheinlichkeitslisten zur Identifikation. Diese Wahrscheinlichkeitslisten sollten durch denselben Klassifizierer geliefert werden, der die Abtastwahrscheinlichkeitslisten liefert, die in dem Kasten 102 in Fig. 3 zusammengeklumpt wurden, und könnten asynchron von dem Klassifizierer durch einen Puffer oder eine pufferende Datenstruktur empfangen sein.
Der Schritt in dem Kasten 122 beginnt eine iterative Schleife, die jede der Kandidatenwahrscheinlichkeitslisten von dem Puffer in Folge handhabt. Der Schritt in dem Kasten 124 vergleicht die nächste Kandidatenwahrscheinlichkeitsliste mit den Wahrscheinlichkeitslisten der abschließenden Cluster, wie sie in dem Kasten 114 in Fig. 3 gespeichert sind, um das naheste Cluster zu finden. Dieser Vergleich könnte mit einem euklidischen Abstand oder mit einem Mahalanolis-Abstand vorgenommen werden. Wenn das naheste Cluster gefunden ist, wird sein Cluster-ID in dem Kasten 126 ausgegeben, und die Identifikationsphase kehrt dann zu dem Schritt in dem Kasten 122 zurück, was fortfährt, bis keine Kandidaten, die gehandhabt werden müssen, verbleiben, wobei zu diesem Zeitpunkt die Identifiaktionsphase abgeschlossen ist.
Die Schritte in Fig. 4 entsprechen den Schritten, die durch die Clusteridentifiziereinrichtung in Fig. 2 durchgeführt werden. Der Kasten 120 entspricht dem Kasten 30; der Kasten 124 entspricht dem Kasten 32 und der Kasten 126 entspricht dem Kasten 34.
Fig. 5 stellt ein System 150 zum Durchführen der Schritte in den Fig. 3 und 4 dar. Das System 150 umfaßt einen Prozessor 152, eine Workstation-CPU oder einen anderen geeigneten Prozessor. Der Prozessor 152 empfängt Eingänge über Eingabevorrichtungen 154, die eine Text-Abtasteinrichtung, eine Sprachempfangseinrichtung, ein Tastenfeld mit einer Maus und andere geeignete Vorrichtungen umfassen können. Der Prozessor 152 liefert Ausgänge über die Ausgabevorrichtung 156, die eine CRT oder eine andere Anzeige umfassen kann. Der Prozessor greift auch auf einen Speicher 158 während seiner Betriebsweisen zu.
Der Speicher 158 umfaßt erläuternd einen Programmspeicher 160 und einen Datenspeicher 170, obwohl der Speicher 158 in irgendeiner geeigneten Art und Weise gehandhabt werden könnte. Der Programmspeicher 160 umfaßt einen Klassifizierer 162, ein Clusteridentifiziereinrichtungs-Trainingsprogramm 164, das so ausgeführt werden könnte, wie in Fig. 3, ein Cluster-Identifikationsprogramm 166, das so ausgeführt werden könnte, wie in Fig. 4, und eine Einschränkungs-Erfüllungseinrichtung 168. Der Datenspeicher 170 umfaßt Regel/Muster-Daten 172 für die Einschränkungs-Erfüllungseinrichtung 168, Trainingsabtastungen 174 und Traningsparameter 176 für das Trainingsprogramm 164, Clusterwahrscheinlichkeitslisten/ID's 178, die durch das Trainingsprogramm 164 gespeichert sind und auf die durch das Identifikationsprogramm 166 zugegriffen wird, und einen zusätzlichen, temporären Speicher für Daten, wie beispielsweise den Kandidatenwahrscheinlichkeitslistenpuffer. Der Datenspeicher 170 umfaßt auch irgendwelche Daten, die durch den Klassifizierer 162 erforderlich sind, und kann deshalb Bit-Tafeln, Schablonen bzw. Modelle oder andere Darstellungen von Kandidatenzeichen umfassen.
Die Ausführung der Fig. 5 umfaßt eine Komponente entsprechend jeder der Komponenten in Fig. 1. Das Identifikationsprogramm 166 entspricht der Clusteridentifiziereinrichtung 12; die Einschränkungs-Erfüllungseinrichtung 168 entspricht der Einschränkungs- Erfüllungseinrichtung 14; die Regeln/Musterdaten 172 entsprechen den Regeln/Musterdaten 18; und die Clusterwahrscheinlichkeitslisten/ID's 178 entsprechen den Zeichen/Wahrscheinlichkeitsdaten 20. Die Einschränkungs-Erfüllungseinrichtung 168 kann demzufolge ein Cluster-ID verwenden, um auf eine entsprechende Wahrscheinlichkeitsliste in den Clusterwahrscheinlichkeitslisten/ID's 178 zuzugreifen, falls dies notwendig ist, um ein Zeichen zu erkennen.

D. Verschiedenes

Die Erfindung könnte auf viele andere Arten und Weisen ausgeführt werden.
Die vorstehend beschriebene Ausführung könnte so modifiziert werden, um einen optimalen Gebrauch von der verfügbaren Bandbreite zwischen der Wahrscheinlichkeitscluster-Identifiziereinrichtung und der Einschränkungs-Erfüllungseinrichtung zu machen Eine mögliche Einstellung ist diejenige, die Zahl der Wahrscheinlichkeitscluster so auszuwählen, daß die Cluster-ID's einer gegebenen, fixierten Länge verwendet werden können. Eine andere Einstellung ist diejenige, kurze Cluster-ID's für Hochfrequenzcluster und längere Cluster-ID's für Niederfrequenzcluster vorzusehen.
Eine Einschränkungs-Erfüllungseinrichtung zur Verwendung in der Erfindung könnte irgendeine einer breiten Vielfalt von Formen annehmen. Allgemein könnte eine auf eine Anwendung zugeschnittene Vielfachfach-Kontext- oder dynamische Kontext-Kenntnis dazu gebracht werden, sich auf einen Erkennungsprozeß durch die Einschränkungs-Erfüllungseinrichtung zu beziehen. Vielfachbedeutungsprüfer könnten für vielfache Sprachen verwendet werden. Eine für ein Formfeld spezifische Grammatik, die Buchstabierbzw. Bedeutungszeichen steuert, könnte auch verwendet werden. Prozesse, die dazu geeignet sind, den Vorteil einer minimalen Redundanz in einer spezialisierten Eingabe wahrzunehmen, wie beispielsweise Finanz-, zeitorientierte oder Teilelisteninformationen, könnten verwendet werden. Zusätzlich zu einer Zeichenerkennung könnte die Einschränkungs-Erfüllungseinrichtung eine Worterkennung und eine Schrifttypenerkennung anwenden, um einen Inhalt der Cluster-ID's zu extrahieren.
Die Ausführung, die vorstehend beschrieben ist, setzt einen einzelnen, seriellen Prozessor für eine Wahrscheinlichkeitsclusteridentifikation und für eine Einschränkungs-Erfüllung ein. Diese Funktionen könnten allerdings gleichzeitig durch parallele Prozessoren oder in irgendeiner anderen geeigneten Art und Weise durchgeführt werden und jede Funktion könnte ähnlich auf einem Multiprozessor oder irgendeiner anderen, geeigneten Archtitektur ausgeführt werden. Weiterhin könnten, wenn ein einzelner, serieller Prozessor verwendet wird, herkömmliche Techniken, wie beispielsweise ein Multitasking, angewandt werden.

Claims

1. Verfahren zum Identifizieren, welches verschiedener Zeichenwahrscheinlichkeitscluster am nahesten zu einem Zeichen-Kandidaten ist, wobei der Zeichen- Kandidat ein Teil eines Textes ist und separat zur Identifikation präsentiert wird, wobei das Verfahren die Schritte aufweist:

Erhalten eines Satzes Wahrscheinlichkeitswerte für einen Zeichen-Kandidaten, wobei der Satz Wahrscheinlichkeitswerte einen jeweiligen Wahrscheinlichkeitswert für jeden eines Satzes von Zeichen-Typen umfaßt, wobei jeder Wahrscheinlich keitswert eines Zeichen-Typs eine Wahrscheinlichkeit anzeigt, daß der Zeichen- Kandidat ein Fall des Zeichen-Typs ist; und

Verwenden des Satzes Wahrscheinlichkeitswerte, um zu identifizieren, welcher einer Zahl Zeichenwahrscheinlichkeitscluster am nahesten zu dem Kandidaten ist wobei die Zeichenwahrscheinlichkeitscluster Bereiche eines Raums sind, wobei der Raum eine jeweilige Dimension für jeden der Zeichen-Typen besitzt, wobei der jeweilige Wahrscheinlichkeitswert des Zeichen-Kandidaten für jeden Zeichen-Typ die Position des Zeichen-Kandidaten in der Dimension des Zeichen-Typs anzeigt, so daß der Satz der Wahrscheinlichkeitswerte die Position des Zeichen-Kandidaten in dem Zeichenwahrscheinlichkeitsraum anzeigt.

2. Verfahren nach Anspruch 1, das weiterhin einen Schritt eines Speicherns jeweiliger Wahrscheinlichkeitsdaten für jedes der Zeichenwahrscheinlichkeitscluster vor dem Schritt einer Verwendung des Satzes der Wahrscheinlichkeitswerte aufweist.

3. Verfahren nach Anspruch 2, wobei der Speicherschritt eine Clusterbildung von Abtastwahrscheinlichkeitsdaten aufweist, um die Zeichenwahrscheinlichkeitscluster zu erhalten.

4. Verfahren nach Anspruch 2 oder 3, das weiterhin einen Schritt eines Erkennens des Kandidaten basierend auf den jeweiligen Wahrscheinlichkeitsdaten für das identifizierte, naheste Wahrscheinlichkeitscluster aufweist.

5. Verfahren nach einem der Ansprüche 2 bis 4, wobei die jeweiligen Wahrscheinlichkeitsdaten jedes Clusters ein Satz von Wahrscheinlichkeitswerten ist, wobei der Satz Wahrscheinlichkeitswerte einen jeweiligen Wahrscheinlichkeitswert für jeden eines Satzes erkennbarer Zeichen-Typen umfaßt.

6. Verfahren nach einem vorhergehenden Anspruch, wobei der Schritt einer Verwendung des Satzes Wahrscheinlichkeitswerte einen Unterschritt eines Erhaltens von Daten, die das naheste Wahrscheinlichkeitscluster identifizieren, aufweist, wobei das Verfahren weiterhin den Schritt eines Erhaltens von Daten aufweist, die einen Zeichen-Typ des Kandidatenzeichens identifizieren, und zwar basierend auf den Daten, die das naheste Cluster identifizieren.

7. System zum Verarbeiten von Daten, das aufweist:

einen Klassifizierer zum Liefern eines Satzes Wahrscheinlichkeitswerte für einen Zeichen-Kandidaten, wobei der Zeichen-Kandidat ein Teil eines Textes ist und separat zur Identifizierung präsentiert wird, wobei der Satz Wahrscheinlichkeitswerte einen jeweiligen Wahrscheinlichkeitswert für jeden eines Satzes Zeichen-Typen umfaßt, wobei jeder Wahrscheinlichkeitswert eines Zeichen-Typs eine Wahrscheinlichkeit anzeigt, daß der Zeichen-Kandidat ein Fall des Zeichen-Typs ist;

eine Wahrscheinlichkeitscluster-Identifiziereinrichtung (12) zum Verwenden des Satzes Wahrscheinlichkeitswerte, um Daten zu produzieren, die identifizieren, welcher einer Anzahl Zeichenwahrscheinlichkeitscluster am nahesten zu dem Zeichen-Kandidaten ist, wobei die Zeichenwahrscheinlichkeitscluster Bereiche eines Raums sind, wobei der Raum eine jeweilige Dimension für jeden der Zeichen-Typen umfaßt, wobei der jeweilige Wahrscheinlichkeitswert des Zeichen-Kandidaten für jeden Zeichen-Typ die Position des Zeichen-Kandidaten in der Dimension des Zeichen-Typs anzeigt, so daß der Satz Wahrscheinlichkeitswerte die Position des Zeichen-Kandidaten in dem Raum definiert; und

eine Einschränkungs-Erfüllungseinrichtung (14) zum Liefern von Daten, die einen Zeichen-Typ des Zeichen-Kandidaten basierend auf den das Cluster identifizierenden Daten von der Wahrscheinlichkeitscluster-Identifiziereinrichtung identifizieren.

8. System nach Anspruch 7, das weiterhin gespeicherte Wahrscheinlichkeitsdaten aufweist, die jeweilige Wahrscheinlichkeitsdaten für jedes der Zeichenwahrscheinlichkeitscluster umfassen, wobei die Einschränkungs-Erfüllungseinrichtung die das Cluster identifizierenden Daten verwendet, um auf jeweilige Wahrscheinlichkeitsdaten des identifizierten, nahesten Clusters zuzugreifen.

9. System nach Anspruch 8, wobei die jeweiligen Wahrscheinlichkeitsdaten für jedes Cluster einen jeweiligen Satz von Wahrscheinlichkeitswerten für das Cluster umfassen, wobei jeder jeweilige Satz von Clustern der Wahrscheinlichkeitswerte einen jeweiligen Wahrscheinlichkeitswert für jeden der Zeichen-Typen umfaßt.

10. System nach Anspruch 7 bis 9, wobei die Klassifiziereinrichtung auch jeweilige Wahrscheinlichkeitsdaten für einen Satz von Abtastzeichen liefert; und wobei das System weiterhin einen Trainer zum Speichern der jeweiligen Wahrscheinlichkeitsdaten für jedes der Zeichenwahrscheinlichkeitscluster basierend auf jeweiligen Wahrscheinlichkeitsdaten für die Abtastzeichen aufweist.

11. System nach Anspruch 10, wobei der Trainer dazu geeignet ist, die Zeichenwahrscheinlichkeitscluster und die jeweiligen Wahrscheinlichkeitsdaten für jedes der Cluster durch Clusterbildung der Wahrscheinlichkeitsdaten für die Abtastzeichen zu erhalten.