PatentDe  


Dokumentenidentifikation DE3486272T2 11.08.1994
EP-Veröffentlichungsnummer 0147657
Titel Verfahren und Anlage zur auf der Häufigkeit des Vorkommens der Zeichen gegründeten Zeichenerkennung.
Anmelder International Business Machines Corp., Armonk, N.Y., US
Erfinder Bednar, Gregory Martin, Matthews North Carolina 28105, US
Vertreter Teufel, F., Dipl.-Phys., Pat.-Ass., 71155 Altdorf
DE-Aktenzeichen 3486272
Vertragsstaaten CH, DE, FR, GB, IT, LI, NL, SE
Sprache des Dokument En
EP-Anmeldetag 30.11.1984
EP-Aktenzeichen 841144306
EP-Offenlegungsdatum 10.07.1985
EP date of grant 09.02.1994
Veröffentlichungstag im Patentblatt 11.08.1994
IPC-Hauptklasse G06K 9/62

Beschreibung[de]

Die vorliegende Erfindung betrifft die optische Zeichenerkennung und insbesondere ein Verfahren und eine Anlage zur Verarbeitung von Daten, die von einem optischen Scanner bezogen wurden, um die Zeichen oder Symbole zu identifizieren, die die Daten umfassen.

Anlagen und Verfahren zur optischen Zeichenerkennung (OCR, Optical Character Recognition), bestehen schon seit über 30 Jahren. Im Laufe dieser Zeit gingen Verbesserungen der Möglichkeiten und der Zuverlässigkeit der OCR sowie Kostensenkungen vorwiegend auf Verbesserungen der Ausrüstung zurück. Verfahren zur Verarbeitung von Daten für die OCR erkennen unbekannte Zeichen einer bekannten Zeichenmenge traditionell dadurch, daß sie alle Symbole für gleichermaßen wichtig erachten. Sie setzen im allgemeinen Techniken ein, die alle möglichen Symbole parallel anstatt seriell von allen anderen Symbolen unterscheiden.

Eine baumartige Entscheidungslogik nach dem Stand der Technik ist in Fig. 2 der beiliegenden Zeichnungen dargestellt. Diese Baumlogik nach dem Stand der Technik versucht, alle Symbole mit einer einzigen Erkennungslogik in einem einheitlichen Prozeß zu erkennen, unabhängig davon, wie häufig oder selten jedes einzelne Symbol im normalen Sprachgebrauch vorkommt. Genau genommen werden die Bilddaten jedes Zeichens progressiv anhand einer Reihe binärer Prüfungen geprüft, die einen Entscheidungsbaum bilden, wobei jede Prüfung als Knoten dargestellt wird und sich entweder auf einzelne Bild-Bits oder auf kollektive Bilddaten beziehen kann, die als Messungen oder Merkmale bezeichnet werden. Die Prüfungen werden fortgesetzt, bis ein bestimmtes Zeichen aus einer definierten Zeichenmenge eindeutig identifiziert ist, wie bei Knoten 27. Nicht identifizierte Daten werden den Prüfungen weiter unten im Baum unterzogen, bis sie identifiziert werden oder ein Rückweisungscode erzeugt wird, der anzeigt, daß die Daten nicht erkannt wurden. Weiter können dann umfassendere Prüfungen eingesetzt werden, um noch einmal zu versuchen, zwischen allen möglichen Zeichen zu unterscheiden.

Kosten und Komplexität der Gestaltung eines solchen Entscheidungsbaum-Logiksystems, des Verfahrens zur Verarbeitung der Daten und der Ausrüstung zur Verwirklichung eines solchen Verfahrens wachsen exponentiell mit Steigerungen der Erkennungsrate und der Erkennungsgenauigkeit. Ferner ist es ein inhärentes Merkmal der baumartigen Entscheidungslogik, daß sie auf die Merkmale der gesamten Zeichenpopulation zugeschnitten ist und nicht auf einzelne Teilmengen davon. Jede folgende Prüfung hängt von der vorhergehenden Prüfung ab, um alle Zeichen der Menge zu erkennen und nicht nur eine Teilmenge der Zeichen auf der Grundlage ihrer Vorkommenshäufigkeit. So wendet man womöglich unverhältnismäßig viel Rechenzeit oder eine unverhältnismäßig umfangreiche Ausrüstung auf, um zwischen Zeichen mit geringer Vorkommenshäufigkeit zu unterscheiden, was die Nutzungseffizienz der Maschine stark herabsetzt, ohne eine bedeutende Verbesserung der Erkennungsrate, -geschwindigkeit oder -leistung zu bringen. Ein Beispiel für eine solche baumartige Logik wird beschrieben in IBM Technical Disclosure Bulletin Bd. 23, Nr. 8, Januar 1981.

JP-A-56 149 676 beschreibt ein Zeichenerkennungssystem, bei dem zu erkennende Zeichen gescannt und Daten über die Eigenschaften jedes gescannten Zeichens in einem Eigenschaftsspeicher gespeichert sind. Das System umfaßt einen Wörterbuchspeicher, in dem Wörterbucheinträge gespeichert sind, die eingegebenen Mustern entsprechen. In dem einzigen angegebenen Beispiel handelt es sich bei den gespeicherten Wörterbucheinträgen um die Ziffern 0 bis 9, die beim Scannen der Ziffernzeichen verwendet werden sollten. Zu jedem Wörterbucheintrag gibt es gespeicherte Daten, die die Eigenschaften des Eintrags angeben. Die Daten in dem Eigenschaftsspeicher werden mit Hilfe eines Entscheidungsschaltkreises mit den Daten im Wörterbuchspeicher verglichen, um das gescannte Zeichen zu identifizieren.

Für jedes gescannte Zeichen erfolgt reihum ein Vergleich mit jedem Wörterbucheintrag, und die Reihenfolge, in der die Wörterbucheinträge verglichen werden, wird von den Daten bestimmt, die in einen Prioritätsspeicher eingegeben werden. Dieser Speicher enthält als Daten die Startadressen der Wörterbucheinträge "mit höherer Priorität". Der Vergleich mit den Eigenschaften der eingegebenen Daten beginnt mit den Wörterbucheinträgen "mit höherer Priorität". Der Ausdruck "mit höherer Priorität" bezieht sich auf eine "Prioritätsrangfolge", die von den Daten im Prioritätsspeicher bestimmt wird. Der Prioritätsspeicher definiert die Prioritätsrangfolge als 1, 2, 0, 5, . . . , und in dieser Reihenfolge werden die Vergleichsoperationen für jede Menge von Eigenschaften eingegebener Daten durchgeführt.

US-A-3 755 780 betrifft ein Verfahren und eine Anlage zur Erkennung unbekannter Muster in einem Dokument und umfaßt die Klassifikation oder Gruppierung von Zeichen, die erkannt werden sollen, anhand der Anzahl gemeinsamer Merkmale und nicht anhand ihrer Vorkommenshäufigkeit in irgendeinem Dokument.

Das Ziel der vorliegenden Erfindung ist es, ein Verfahren und eine Anlage zur Verarbeitung von Daten zur Erkennung unbekannter Zeichen einer bekannten Zeichenmenge vorzustellen, die die Wirksamkeit der Zeichenerkennung durch Verbesserungen bei der Genauigkeit und der Durchsatzgeschwindigkeit verbessern.

Die vorliegende Erfindung betrifft ein Verfahren zur Verarbeitung von Daten zur Erkennung unbekannter Zeichen einer bekannten Zeichenmenge, die zum Teil auf der Vorkommenshäufigkeit der Zeichen beruht. Das Verfahren umfaßt folgende Schritte: Scannen der unbekannten Zeichen und Erzeugen von Bilddaten, die die unbekannten Zeichen repräsentieren, Speichern der Bilddaten, Anwenden einer ersten Stufe einer ersten Menge unterscheidender logischer Prüfungen auf die gespeicherten Bilddaten zur Identifizierung der gespeicherten Bilddaten, wobei die erste Menge unterscheidender logischer Prüfungen der Identifizierung von Daten dient, die eine erste Teilmenge der bekannten Zeichenmenge repräsentieren, und die erste Teilmenge aus Zeichen besteht, die die höchste Vorkommenshäufigkeit aufweisen; Anwenden einer ersten Stufe einer zweiten Menge unterscheidender logischer Prüfungen zur Identifizierung von Daten, die eine zweite Teilmenge der bekannten Zeichenmenge repräsentieren; und ist dadurch gekennzeichnet, daß eine zweite Stufe unterscheidender logischer Prüfungen auf die gespeicherten Bilddaten angewendet wird, die durch frühere logische Prüfungen nicht identifiziert wurden, wobei die zweite Stufe unterscheidender logischer Prüfungen dazu dient, weiter zu versuchen, Daten zu identifizieren, die Zeichen repräsentieren, die zu den Teilmengen der bekannten Zeichenmenge gehören, die in der ersten Stufe nicht identifiziert wurden, und wobei die zweite Stufe logischer Prüfungen getrennt von der ersten Stufe der ersten Menge logischer Prüfungen ist.

Die Erfindung betrifft ferner auch eine Anlage zur Durchführung des obigen Verfahrens, die in den Ansprüchen 7 bis 12 definiert ist.

Die vorliegende Erfindung beschreibt ein neues Verfahren und eine neue Anlage zur Verarbeitung von Daten, wobei die am häufigsten auftretenden Symbole als die wichtigsten gelten. Eine geordnete Folge von Erkennungsschritten wird auf die Daten angewandt, die die unbekannten Zeichen repräsentieren, um zuerst nur die Zeichen einer Gruppe zu erkennen, die eine höhere Vorkommenshäufigkeit aufweisen. Gruppen von Zeichen mit niedrigerer Vorkommenshäufigkeit werden später erkannt. Es handelt sich um ein ideales Verfahren zur Durchführung mit einem Mikroprozessor, da sich dasselbe Erkennungsergebnis mit weniger Schritten erreichen läßt, indem die Zeichen in mehrere kleine Zeichenmengen anstelle einer vollständigen Zeichenmenge eingeteilt werden. Indem beispielsweise zuerst eine kleine Menge von Zeichen erkannt wird, die die größte Vorkommenswahrscheinlichkeit oder -häufigkeit aufweisen, wird die durchschnittliche Zahl der Erkennungsschritte erheblich reduziert. Dieses Verfahren und diese Anlage eignen sich besonders für die Erkennung von Zeichensätzen, die eine große Zahl von Symbolen enthalten, wie zum Beispiel Texte in japanischem Katakana oder in Englisch.

Die Erfindung nutzt eine neuartige geordnete Folge von erkennungslogischen Mengen anstelle der parallelen Anordnung, die sich in der typischen baumartigen Entscheidungslogik findet. Jede logische Menge ist eindeutig maßgeschneidert, um nur die Merkmale einer ausgewählten Population oder Teilmenge aller Zeichen zu erkennen. So hängt eine Menge von Prüfungen jeweils nicht von der vorhergehenden Menge von Prüfungen ab und muß nicht alle Eigenschaften der gesamten Zeichenpopulation berücksichtigen. Dies optimiert sowohl die Erkennungsleistung als auch die Verarbeitungszeit.

Außerdem stellen das Verfahren und die Anlage der Erfindung bei Zeichenmengen mit einer großen Anzahl von Symbolen ein günstiges Mittel zur Zerlegung der Erkennungsprobleme in Teilmengen kleinerer Probleme dar, woraus sich ein optimaler Nutzen ziehen läßt. Durch die kleineren Erkennungsmengen wird das Erkennungsproblem auch für den Gestalter der Erkennungslogik eine leichter zu handhabende Aufgabe, und die Zahl der Erkennungsschritte sinkt dramatisch. Das Verfahren und die Anlage erlauben die Anwendung einer Vielzahl zeichenerkennungslogischer Mengen, die speziell zur Identifizierung kontrollierter Teilmengen der gesamten Zeichenmenge angepaßt sind. Dadurch ist es möglich, die Nutzung der Ausrüstung und der Verarbeitungszeit zu optimieren, um eine höhere Erkennungsrate der häufiger vorkommenden Zeichen in kürzerer Zeit zu erzielen. Indem die Erkennungslogik von den Einschränkungen befreit wird, die ihr von der baumartigen Entscheidungslogik nach dem Stand der Technik auferlegt werden, wird der Umfang der Logik minimiert, während der Erkennungsaufwand auf die am häufigsten vorkommenden Zeichen konzentriert wird. Darüber hinaus werden Erkennungsgenauigkeit und Durchsatz ohne Erhöhung des Speicherplatzes erhöht. Weitere Vorteile sind unter anderem die Verwendung einfacherer und getrennter erkennungslogischer Mengen anstelle einer scheinbar endlosen und unzusammenhängenden Menge kaskadenartig gestaffelter Prüfungen. Es ist daher möglich, die verschiedenen logischen Mengen so zu optimieren, daß sie unterschiedliche Teilmengen erkennen und den größten Teil des Aufwands dabei auf diejenigen Zeichen konzentrieren, die am häufigsten vorkommen. Beispielsweise läßt sich die Genauigkeit der Erkennungsrate für die häufiger vorkommenden Zeichen verbessern, indem zusätzliche Prüfungen durchgeführt werden, bei denen es nicht notwendig oder erwünscht ist, daß sie die Genauigkeit der Erkennungsrate für die weniger häufig vorkommenden Zeichen verbessern.

Weitere Vorteile sind unter anderem die Möglichkeit, das Verarbeitungsverfahren für bestimmte Anforderungen maßzuschneidern. Während etwa die Buchstaben X, Y und Z zu den am wenigsten häufig vorkommenden Zeichen gehören, wenn die englische Sprache für die Alltagskommunikation verwendet wird, gehören sie in wissenschaftlichen oder mathematischen Anwendungen unter Umständen zu den am häufigsten verwendeten. Das Verfahren der vorliegenden Erfindung besitzt die Flexibilität, solche Veränderungen zu berücksichtigen. Um das Verfahren und die Anlage der vorliegenden Erfindung noch weiter zu verbessern, kann die Verkettung der erkennungslogischen Mengen in horizontaler oder vertikaler Richtung oder in beiden Richtungen erfolgen.

Um die Erfindung leichter verständlich zu machen, wird im folgenden ein Ausführungsbeispiel der Erfindung unter Bezugnahme auf die beiliegenden Zeichnungen beschrieben:

Fig. 1 ist ein Blockdiagramm, das eine typische Zeichenerkennungsanlage darstellt, die die Erfindung und die Schrittfolge zur Verarbeitung der Daten verkörpert.

Fig. 2 stellt eine typische baumartige Entscheidungslogik dar, wie sie nach dem Stand der Technik zu finden ist und die so gestaltet ist, daß sie alle Symbole unabhängig von ihrer Vorkommenshäufigkeit erkennen soll.

Fig. 3 stellt ein Verfahren und eine Anlage zur Verarbeitung von Daten nach der vorliegenden Erfindung dar und zeigt die verschiedenen Stufen und Gruppen, die zur Erkennung der Daten sequentiell angeordnet sind.

Fig. 4 ist eine Tafel, die die Vorkommenshäufigkeit japanischer Katakana-Zeichen darstellt.

In Fig. 1 zeigt ein schematisches Diagramm des Verfahrens und der Anlage der vorliegenden Erfindung die Erzeugung von Daten, die die unbekannten Zeichen repräsentieren, durch einen optischen Scanner. Die Konstruktion und die Funktionsweise des Scanners sind bekannt. Typischerweise scannt der Scanner ein Dokument 1 mit unbekannten Zeichen parallel zur Leserichtung. Fig. 1 zeigt das horizontale Scannen einer Zeile mit Zeichen. Der Scanner 2 prüft das Dokument in seiner gesamten Länge, indem er entweder das Dokument oder den Scannermechanismus bewegt, und in seiner gesamten Breite, indem er ein Blickfeld von entsprechender Breite wählt. Die erzeugten Scan-Daten werden an einen Zeichenpuffer 3 übergeben, der sie speichert und an die Zeichenerkennungsanlage 4 überträgt.

Die Zeichenerkennungsanlage wendet die verschiedenen geordneten Folgen unterscheidender logischer Prüfungen an, um die Scan-Daten als einzelne Zeichen zu erkennen. Die Ausgabe 5 der Zeichenerkennungsanlage zeigt typischerweise an, daß die Bilddaten, die ein bestimmtes Zeichen repräsentieren, erkannt wurden oder daß die Information nicht erkannt werden konnte, wodurch ein Rückweisungs- oder Fehlercode erzeugt wird.

In Fig. 2 ist ein Teil einer typischen baumartigen Entscheidungslogik nach dem Stand der Technik dargestellt. Die Bilddaten, die ein unbekanntes Zeichen repräsentieren, werden an die Spitze der Baumlogik übergeben, also an Knoten 11, und es wird eine Reihe logischer Prüfungen durchgeführt, wie durch die Knoten 11-30 repräsentiert wird. (Nur eine repräsentative Auswahl von Knoten ist bezeichnet.) Wie bereits erläutert wurde, führt eine solche Logik genügend unterscheidende Prüfungen durch, die die Bilddaten auswerten, um deren Eigenschaften auf ein mögliches Ausgabezeichen zu beziehen, das sich von allen anderen möglichen Zeichen in der bekannten Zeichenmenge unterscheidet. Die Zahl der benötigten Prüfungen ist eine exponentielle Funktion der Zahl der möglichen Ausgabezeichen, zwischen denen unterschieden werden muß. Dadurch wird viel Verarbeitungszeit und Energie aufgewendet, um jedes unbekannte Zeichen von allen anderen Kandidaten zu unterscheiden, damit Zeichen unterschieden werden können, die nur selten vorkommen.

Fig. 2 zeigt auch, wie im Hinblick auf die Erkennung aller Zeichen in der Menge anstelle der Erkennung einer bloßen Teilmenge der Zeichen auf der Grundlage ihrer Vorkommenshäufigkeit jede nachfolgende Entscheidung von der vorhergehenden Entscheidung abhängt. Die Punkte zeigen die Fortsetzung der Entscheidungslogik an, die die "Zweige" des Entscheidungsbaumes bildet. Nur die untersten Zweige sind mit einer Fortsetzung gekennzeichnet, doch die Abbildung ist so zu verstehen, daß alle Zweige bei Bedarf fortgesetzt werden können.

In Fig. 3 verwenden das Verfahren und die Anlage zur Verarbeitung von Daten gemäß der vorliegenden Erfindung eine Verkettung getrennter Mengen logischer Prüfungen. Wie dargestellt umfaßt das Verfahren die serielle Anwendung getrennter "Mengen" logischer Prüfungen. Eine horizontale Reihe von Mengen kann als "Stufe" bezeichnet werden, eine vertikale Spalte von Mengen als "Gruppe". Das Mittel zur Anwendung einer Menge unterscheidender logischer Prüfungen kann die Anwendung einer unterscheidenden binären Baumlogik und die anschließende Anwendung einer Verifikationslogik zur Bestätigung der Ausgabe umfassen.

Die einzelnen logischen Mengen innerhalb einer Stufe sind in sequentieller Reihenfolge nach der Häufigkeit der von den einzelnen Mengen erkannten Zeichenteilmengen angeordnet. Die Menge 1,1 zum Beispiel erkennt nur die am häufigsten vorkommenden Symbole der Zeichenmenge. Die Menge 2,1 erkennt nur die Symbole, die mit der nächstgeringeren Häufigkeit vorkommen. Auf ähnliche Weise erkennen nachfolgende Mengen wie etwa die Menge 1,1 Symbole mit geringerer Vorkommenshäufigkeit. Dies kann sich fortsetzen, bis alle Zeichen erfaßt sind. Nachfolgende Teilmengen können mindestens einige Zeichen enthalten, die nicht in vorangegangenen Teilmengen enthalten waren. Die Bilddaten, die die unbekannten Zeichen repräsentieren, werden an die Menge 1,1 übergeben, und die unterscheidenden Prüfungen der Menge 1,1 werden auf die Daten angewandt. Ein optionaler Verifikator kann nach Bedarf oder Wunsch verwendet werden, um die von den Prüfungen erzeugte Ausgabe zu bestätigen. Die Prüfungen stellen fest, ob die Bilddaten eine erste Gruppe von Zeichen mit höherer Vorkommenshäufigkeit repräsentieren, und erkennen die Bilddaten als Repräsentation einzelner Zeichen. Die Daten, die erkannte Zeichen repräsentieren, scheiden bei ERK. aus, und die Daten, die nicht erkannte Zeichen repräsentieren, scheiden bei N. ERK. aus und werden an die Menge 2,1 weitergeleitet. Zu den Daten, die nicht erkannte Zeichen repräsentieren, gehören Daten, die Zeichen repräsentieren, die hätten erkannt werden können, jedoch wegen Rauschens oder ähnlichem nicht erkannt wurden, sowie Daten, die Zeichen repräsentieren, die durch nachfolgende Mengen zu identifizieren sind, aber nicht durch die vorliegende Menge.

Bei der Menge 2,1 wird auf die nicht erkannten Bilddaten eine Abfolge von unterscheidenden Prüfungen angewandt, die von den Prüfungen der Menge 1,1 unabhängig sind. Diese Prüfungen stellen fest, ob die nicht erkannten Daten eine zweite Gruppe von Zeichen repräsentieren, die eine geringere Vorkommenshäufigkeit aufweisen als die erste Gruppe von Zeichen, und erkennen die Daten als Repräsentation einzelner Zeichen. Wie zuvor scheiden die Daten, die erkannte Zeichen repräsentieren, bei ERK. aus, und die Daten, die nicht erkannte Zeichen repräsentieren, scheiden bei N. ERK. aus und werden weitergeleitet. Diese sequentielle Anwendung unterscheidender Prüfungen kann nach Bedarf oder Wunsch fortgesetzt werden. So ist es zum Beispiel möglich, in Stufe 1 eine Reihe von Mengen einzubeziehen, die zur Erkennung aller Zeichen einer bestimmten Zeichenmenge ausreicht.

Das obengenannte Verfahren und die Anlage haben mehrere Vorteile. Erstens scheiden die Zeichen, die in Schritt 1,1 erkannt werden, aus dem Erkennungsverfahren und der Anlage in kürzester Zeit aus. Da es sich hierbei um die am häufigsten vorkommenden Zeichen handelt, minimiert dies die Nutzung des Mikroprozessors oder der sonstigen Anlage und optimiert zugleich die Erkennungsrate. Zweitens lassen sich die Erkennungsleistung und -genauigkeit der Menge 1,1 steigern, da die Menge 1,1 so maßgeschneidert werden kann, daß sie mehr Erkennungslogik pro Symbol enthält als die Mengen für weniger häufig vorkommende Zeichen. Da diese Menge die am häufigsten vorkommenden Zeichen erkennt, wird die Gesamterkennungsrate der gesamten Struktur optimiert. Drittens ist nur soviel Rechenaufwand nötig, wie für die Erkennung der Bilddaten für ein einzelnes Zeichen erforderlich ist, und es wird nicht versucht, alle anderen möglichen Zeichen zu erkennen, die die Bilddaten repräsentieren könnten.

Wiederum in Fig. 3 kann das Verarbeitungsverfahren die Anwendung mehrerer Stufen logischer Prüfungen in geordneter Folge umfassen, wobei jede Stufe eine Reihe von Mengen umfaßt. Jede Stufe wendet sequentiell logische Prüfungen an, die sich von denen unterscheiden, die in der ersten oder in der vorangegangenen Stufe angewandt wurden, und die Prüfungen oder Mengen der einzelnen Stufen können so maßgeschneidert werden, daß zuerst die Zeichen erkannt werden, die nach der Anwendung aller Mengen von Prüfungen in Stufe 1 die höchste Nichterkennungshäufigkeit aufweisen. Wird zum Beispiel davon ausgegangen, daß Stufe 1 I Mengen umfaßt, können die I Mengen gemeinsam alle Zeichen einer Zeichenmenge identifizieren. Alle Mengen der ersten Stufe können so gestaltet werden, daß sie bestimmte Techniken zur Erkennung dieser Zeichen nutzen. Da es wahrscheinlich ist, daß manche Daten oder Zeichen noch immer unerkannt sind, nachdem sie die gesamte Stufe durchlaufen haben, werden die Daten dann an eine zweite Stufe sequentieller Prüfungen weitergeleitet, also an die Menge 1,2, Menge 2,2 . . . Menge 1,2, um abermals zu versuchen, die Zeichen aus den Bilddaten zu identifizieren. Die Mengen unterscheidender logischer Prüfungen in Stufe 2 sind speziell so gestaltet, daß sie die nicht erkannten Zeichenmuster aus Stufe 1 erkennen, und können eine Logik mit unterschiedlichem Ansatz verwenden, um die Erkennung der von diesen Daten repräsentierten Zeichen zu optimieren. Wie in Fig. 3 weiter dargestellt ist, kann die Zahl der Stufen nach Bedarf oder Wunsch schwanken, um ein gewünschtes Erkennungsziel zu erreichen. Die Mengen und Stufen können somit optimiert werden, um die gewünschte Erkennungsrate zu erhalten und dennoch die Beschränkungen der Erkennungskosten und der Ausrüstung einzuhalten. Weitere Vorteile sind unter anderem die Flexibilität und die Möglichkeit, jede Stufe und Menge maßzuschneidern, um bestimmte Zeichen zu identifizieren, oder völlig unabhängige Ansätze zu verwenden, um ein Zeichen zu identifizieren, das in einer früheren Menge oder Stufe oder Gruppe nicht erkannt wurde.

In Fig. 4 ist die kollektive Vorkommenshäufigkeit der Gruppierungen japanischer Katakana-Zeichen auf der Grundlage ihres Gebrauchs in japanischen Namen dargestellt. Dabei ist zu bedenken, daß zwar hier japanische Katakana-Zeichen dargestellt sind, die vorliegende Erfindung jedoch mit jedem Alphabet oder jeder definierten Zeichenmenge eingesetzt werden kann. Gruppe 1 umfaßt 14 Zeichen, die gemeinsam eine kollektive Frequenz von 60 Prozent aufweisen. Gruppe 2 umfaßt 13 Zeichen, die eine kollektive Frequenz von 18 Prozent haben. Gruppe 3 umfaßt 15 Zeichen, die eine kollektive Frequenz von 14 Prozent haben. Gruppe 4 umfaßt 36 Zeichen, die eine kollektive Frequenz von 8 Prozent haben. Indem das Verfahren zur Verarbeitung optimiert wird, um die Erkennungsrate der am häufigsten vorkommenden Zeichen zu verbessern, also der Zeichen in Gruppe 1, kann die effektive Erkennungsleistung mit geringsten Auswirkungen auf die Kosten gesteigert werden. Darüber hinaus ist dies unabhängig von den Mengen unterscheidender logischer Prüfungen möglich, die zur Identifizierung der japanischen Zeichen in den Gruppen 2, 3 und 4 verwendet werden. Dies wird anhand einer angenommenen Erkennungsrate für die einzelnen Gruppen in folgender Tabelle illustriert:

Gruppe Zahl der Zeichen Erkennungsrate Frequenz Effektive Leistung Gesamt

Hieraus ergibt sich insgesamt ein Erkennungsprozentsatz von (87·0,6) + (84·0,18) + (78·0,14) + (60·0,08) = 83 Prozent. Durch die Verbesserung der Erkennungsrate der Zeichen in der Gruppe 1 läßt sich eine bedeutendere Verbesserung in der effektiven Erkennungsleistung erzielen als durch eine Verbesserung der Erkennungsrate der Zeichen in Gruppe 4.

Nachdem festgelegt wurde, welche Zeichendaten zur Erkennung durch welche Stufe oder Menge geprüft werden, liegt die Aufgabe der Entwicklung der erforderlichen unterscheidenden Prüfungen durchaus in den Möglichkeiten eines Fachmanns für Computerprogrammierung oder optische Zeichenerkennung. Sie umfaßt den Einsatz bekannter Techniken zur Unterscheidung der Daten, die ein Zeichen repräsentieren, von Daten, die ein anderes Zeichen repräsentieren.

Die Anlage zur Durchführung der Erfindung kann einen Mikroprozessor oder einen anderen Computer umfassen, der in der Lage ist, logische Entscheidungen durchzuführen.

In den Zeichnungen und der Beschreibung wurde ein exemplarisches Ausführungsbeispiel der Erfindung dargelegt. Dabei ist zu bedenken, daß der Gebrauch spezifischer Fachausdrücke nur eine generische und deskriptive Verwendung darstellt und nicht der Einschränkung dient.


Anspruch[de]

1. Ein Verfahren zur Verarbeitung von Bilddaten zur Identifizierung unbekannter Zeichen einer bekannten Zeichenmenge, das folgende Schritte umfaßt:

Scannen der unbekannten Zeichen und Erzeugen von Bilddaten, die die unbekannten Zeichen repräsentieren;

Speichern der Bilddaten;

Anwenden einer ersten Stufe einer ersten Menge unterscheidender logischer Prüfungen auf die gespeicherten Bilddaten zur Identifizierung der gespeicherten Bilddaten, wobei die erste Menge unterscheidender logischer Prüfungen zur Identifizierung von Daten dient, die eine erste Teilmenge der bekannten Zeichenmenge repräsentieren, und die erste Teilmenge aus Zeichen besteht, die die höchste Vorkommenshäufigkeit aufweisen;

Anwenden einer ersten Stufe einer zweiten Menge unterscheidender logischer Prüfungen auf gespeicherte Bilddaten, die von der ersten Stufe der ersten Menge logischer Prüfungen nicht identifiziert wurden, wobei die zweite Menge unterscheidender logischer Prüfungen zur Identifizierung von Daten dient, die eine zweite Teilmenge der bekannten Zeichenmenge repräsentieren; und gekennzeichnet ist durch das

Anwenden einer zweiten Stufe unterscheidender logischer Prüfungen auf gespeicherte Bilddaten, die von früheren logischen Prüfungen nicht identifiziert wurden, wobei die zweite Stufe logischer Prüfungen dazu dient, weiter zu versuchen, Daten zu identifizieren, die Zeichen repräsentieren, die zu den Teilmengen der bekannten Zeichenmenge gehören, die in der ersten Stufe nicht erkannt wurden, und wobei die zweite Stufe logischer Prüfungen getrennt von der ersten Stufe logischer Prüfungen ist.

2. Ein Verfahren nach Anspruch 1, wobei die erste Stufe der Prüfungen mindestens eine zusätzliche Menge unterscheidender logischer Prüfungen für gespeicherte Daten enthält, die durch frühere logische Prüfungen nicht identifiziert wurden, und jede zusätzliche Menge unterscheidender logischer Prüfungen dazu dient, gespeicherte Daten zu identifizieren, die zusätzliche Teilmengen der bekannten Zeichenmenge repräsentieren, und jede nachfolgende zusätzliche Teilmenge aus Zeichen besteht, die eine niedrigere Vorkommenshäufigkeit aufweisen als die in vorangegangenen Teilmengen, wobei die zweite Stufe der Prüfungen nach Abschluß der ersten Stufe beginnt.

3. Ein Verfahren nach einem beliebigen der Ansprüche 1 oder 2, ferner umfassend den Schritt der Anwendung jeweils mindestens einer zusätzlichen Stufe jeder Menge unterscheidender logischer Prüfungen auf gespeicherte Bilddaten, die nicht durch frühere logische Prüfungen identifiziert wurden, wobei jede zusätzliche Stufe logischer Prüfungen dazu dient, Daten in einer jeweiligen Teilmenge der bekannten Zeichenmenge zu identifizieren, und getrennt von einer früheren Stufe einer jeweiligen Menge logischer Prüfungen ist.

4. Ein Verfahren nach einem beliebigen der Ansprüche 2 oder 3, wobei die zweiten und alle folgenden Mengen unterscheidender logischer Prüfungen weniger Erkennungsschritte pro Zeichen aufweisen als die frühere Menge logischer Prüfungen, wodurch die zweite und alle folgenden Mengen unterscheidender logischer Prüfungen eine geringere Erkennungsrate aufweisen als die frühere Menge.

5. Ein Verfahren nach einem beliebigen der vorangegangenen Ansprüche, wobei die Schritte zur Anwendung einer Menge unterscheidender logischer Prüfungen die Anwendung einer unterscheidenden binären Baumlogik und die anschließende Anwendung einer Verifikationslogik umfassen.

6. Ein Verfahren nach einem beliebigen der vorangegangenen Ansprüche, wobei die zweite Teilmenge der bekannten Zeichenmenge mindestens einige Zeichen enthält, die nicht in der ersten Teilmenge der bekannten Zeichen enthalten sind.

7. Anlage zur Verarbeitung von Bilddaten zur Identifizierung unbekannter Zeichen einer bekannten Zeichenmenge, umfassend:

Mittel (2) zum Scannen der unbekannten Zeichen und zum Erzeugen von Bilddaten, die die unbekannten Zeichen repräsentieren;

Mittel (3) zum Speichern der Bilddaten;

Mittel zum Anwenden einer ersten Stufe einer ersten Menge unterscheidender logischer Prüfungen auf die gespeicherten Bilddaten zur Identifizierung der gespeicherten Bilddaten, wobei die erste Menge unterscheidender logischer Prüfungen zur Identifizierung von Daten dient, die eine erste Teilmenge der bekannten Zeichenmenge repräsentieren, und die erste Teilmenge aus Zeichen besteht, die die höchste Vorkommenshäufigkeit aufweisen;

Mittel zum Anwenden einer ersten Stufe einer zweiten Menge unterscheidender logischer Prüfungen auf gespeicherte Bilddaten, die von der ersten Stufe der ersten Menge logischer Prüfungen nicht identifiziert wurden, wobei die zweite Menge unterscheidender logischer Prüfungen zur Identifizierung von Daten dient, die eine zweite Teilmenge der bekannten Zeichenmenge repräsentieren; und gekennzeichnet durch

Mittel zum Anwenden einer zweiten Stufe unterscheidender logischer Prüfungen auf gespeicherte Bilddaten, die von früheren logischen Prüfungen nicht identifiziert wurden, wobei die zweite Stufe logischer Prüfungen dazu dient, weiter zu versuchen, Daten zu identifizieren, die Zeichen repräsentieren, die zu den Teilmengen der bekannten Zeichenmenge gehören, die in der ersten Stufe nicht erkannt wurden, und wobei die zweite Stufe logischer Prüfungen getrennt von der ersten Stufe logischer Prüfungen ist.

8. Anlage nach Anspruch 7, ferner umfassend Mittel zum Anwenden einer ersten Stufe mit mindestens einer zusätzlichen Menge unterscheidender logischer Prüfungen auf gespeicherte Daten, die durch frühere logische Prüfungen nicht identifiziert wurden, wobei jede zusätzliche Menge unterscheidender logischer Prüfungen dazu dient, gespeicherte Daten zu identifizieren, die zusätzliche Teilmengen der bekannten Zeichenmenge repräsentieren, und jede nachfolgende zusätzliche Teilmenge aus Zeichen besteht, die eine niedrigere Vorkommenshäufigkeit aufweisen als die in vorangegangenen Teilmengen.

9. Anlage nach nach einem beliebigen der Ansprüche 7 oder 8, ferner umfassend Mittel zur Anwendung jeweils mindestens einer zusätzlichen Stufe jeder Menge unterscheidender logischer Prüfungen auf gespeicherte Bilddaten, die nicht durch frühere logische Prüfungen identifiziert wurden, wobei jede zusätzliche Stufe logischer Prüfungen dazu dient, Daten in einer jeweiligen Teilmenge der bekannten Zeichenmenge zu identifizieren, und getrennt von einer früheren Stufe einer jeweiligen Menge logischer Prüfungen ist.

10. Anlage nach einem beliebigen der Ansprüche 8 oder 9, wobei die zweiten und alle folgenden Mengen unterscheidender logischer Prüfungen weniger Erkennungsschritte pro Zeichen aufweisen als die frühere Menge logischer Prüfungen, wodurch die zweite und alle folgenden Mengen unterscheidender logischer Prüfungen eine geringere Erkennungsrate aufweisen als die frühere Menge.

11. Anlage nach einem beliebigen der Ansprüche 8 bis 10, wobei das Mittel zur Anwendung einer Menge unterscheidender logischer Prüfungen die Anwendung einer unterscheidenden binären Baumlogik und die anschließende Anwendung einer Verifikationslogik umfaßt.

12. Anlage nach einem beliebigen der Ansprüche 8 bis 11, wobei die zweite Teilmenge der bekannten Zeichenmenge mindestens einige Zeichen enthält, die nicht in der ersten Teilmenge der bekannten Zeichen enthalten sind.







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

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

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