PatentDe  


Dokumentenidentifikation DE69423607T2 09.11.2000
EP-Veröffentlichungsnummer 0674794
Titel VERFAHREN ZUM KLASSIFIZIEREN VON BILDERN MIT AUSGABEABBILDUNGEN
Anmelder AT & T Corp., New York, N.Y., US
Erfinder BAIRD, Spalding, Henry, Maplewood, US;
HO, Kam, Tin, Cedar Grove, US
Vertreter Blumbach, Kramer & Partner GbR, 65187 Wiesbaden
DE-Aktenzeichen 69423607
Vertragsstaaten DE, FR, GB
Sprache des Dokument EN
EP-Anmeldetag 13.10.1994
EP-Aktenzeichen 949307854
WO-Anmeldetag 13.10.1994
PCT-Aktenzeichen US9411714
WO-Veröffentlichungsnummer 9510820
WO-Veröffentlichungsdatum 20.04.1995
EP-Offenlegungsdatum 04.10.1995
EP date of grant 22.03.2000
Veröffentlichungstag im Patentblatt 09.11.2000
IPC-Hauptklasse G06K 9/62
IPC-Nebenklasse G06K 9/46   

Beschreibung[de]
Gebiet der Erfindung

Die Erfindung bezieht sich im Allgemeinen auf die automatische Interpretation oder Auswertung von Bildern und insbesondere auf die Klassifizierung oder Erkennung von Bildern aus maschinengedruckten oder handgeschriebenen Symbolen.

Beschreibung des Standes der Technik

Ein wichtiger Bereich der Bildauswertung ist die optische Zeichenerkennung (optical character recognition OCR), bei welcher Bilder von Symbolen automatisch in Binärcodes übertragen werden, welche die Symbole darstellen. Ein Hauptproblem bei der optischen Zeichenerkennung ist die Unterscheidung ähnlich geformter Symbole, deren Bilder verrauscht sind, d. h. Bilder, die an Qualitätsverlust, Verzerrung oder Defekten leiden. Diese Bilddefekte können aus verschiedenen Gründen vorkommen, einschließlich Änderungen des handgeschriebenen Stils des Schriftbildes und der Größe des Textes, sowie Besonderheiten der räumlichen Abtastrate, der optischen Verzerrung und weiterer Effekte aufgrund der Natur des Druckens und Abbildens.

Die Komplexität dieses Effektes hat bis vor kurzem Versuche vereitelt, diese erschöpfend und quantitativ zu beschreiben. Daher können die wahren klassenbedingten Verteilungen von Bildern nicht detailliert analytisch vorhergesagt werden, auch nicht bei perfektem Wissen der idealen Symbolformen. In der Praxis wurden diese Verteilungen nur in Form von finiten Datensätzen aus Bildern empirisch zugänglich gemacht, gesammelt und mit beträchtlichem Aufwand gekennzeichnet. Diese Datensätze sind, auch wenn diese in die Millionen gehen, spärlich verglichen mit der Vielzahl von Bildern, welche in der Praxis vorkommen können.

Ein bekanntes automatisch trainierbares Verfahren klassifiziert im Allgemeinen ein unbekanntes Eingangsbild durch Vergleichen einer Merkmalsgruppe, die aus dem Eingangsbild ermittelt wird, mit einer Gruppe oder Verteilung von Merkmalswerten, die einer gegebenen Klasse zugeordnet sind. In diesem Zusammenhang ist ein Merkmal eine Funktion, welche eine reale Zahl zeitigt, wenn diese auf ein Bild angewandt wird. Die jeder Bildklasse zugeordnete Gruppe oder Verteilung von Merkmalswerten wird durch Anwenden der Merkmale auf eine Trainingsgruppe gebildet, d. h. eine Gruppe von Bildern, wobei jedes Bild mit dessen wahrer Klasse gekennzeichnet ist.

Die Merkmale schwanken in der Komplexität. Beispielsweise beschreibt W. W. Bledsoe et al. früh in dem Werk "Pattern Recognition and Reading by Machine", 1959 Proceedings of the Eastern Joint Computer Conference, Academic Press (1959) 174 bis 181, welche Merkmale auf zufällig ausgewählten Pixelpaaren basierten. Die möglichen numerischen Werte für jedes Pixel sind die vier Binärwerte 00, 01, 10, 11, die den möglichen logischen Zuständen dieser Paare entsprechen. Dieses Verfahren war zur Verwendung in einem praktischen optischen Zeichenlesern nicht genau genug.

Auch sehr neue Klassifizierungsverfahren, die die komplexen Merkmale verwenden, erzielen oftmals enttäuschend geringe Genauigkeit bei Erkennungsproblemen mit isolierten Zeichen. In diesen Fällen ist selten klar, ob die Ungenauigkeit durch Makel der Klassifizierungsmethode (z. B. schlecht gewählten Merkmalen), aufgrund schlechter Güte der Trainingsgruppen (z. B. zu wenige Abtastwerte) oder aufgrund von beidem verursacht wird. Bei Vorgabe dieser Unsicherheit und dem Aufwand beim Gewinnen großer und repräsentativer Trainingsgruppen hat sich der Großteil der OCR Forschung in den letzten Jahrzehnten auf die Heuristik zum Schätzen der verfügbaren spärlichen Trainingsgruppen unter Verwendung einer breiten Vielzahl von Verfahren zur Interpolation, Glättung und analytischen Modellierung der Merkmalsverteilungen konzentriert. Dazu wurden viele vereinfachende Annahmen notwendigerweise aufgestellt, die die Form der Verteilungen, z. B. daß diese einfach verbunden, unimodal, konvex, analytisch oder parametrisch (z. B. multidimensional Gaußmethode) sind, betreffen.

Jedoch weisen viele der Merkmale, die sich als wirkungsvoll erwiesen haben, Verteilungen auf, die sehr komplex sind und nur schwer nachgebildet werden können, wenn diese vereinfachenden Annahmen gemacht werden. Als Ergebnis können diese vereinfachenden Annahmen zu Ungenauigkeiten führen, welche die Stabilität der Bildklassifizierer verringern.

Bei einer alternativen Strategie, welche manchmal als "nächster Nachbar" Strategie bezeichnet wird, werden nur wenige Prototypbilder je Klasse gespeichert und eine feste globale Bildmetrik D(x, y) ≥ 0 (die Abstandsfunktion zwischen je zwei Bildpaaren x und y) wird in der Hoffnung verwendet, von dieser spärlichen Gruppe auf die wahre Verteilung zu verallgemeinern. Dieser Ansatz ist nicht gänzlich gewünscht, weil kein Grund dazu besteht, zu glauben, daß jede einzelne globale Abstandsfunktion die Komplexität aller Klassenverteilungen fehlerfrei nachbildet.

Daher haben Fachleute auf diesem Gebiet bisher keine praktische Bildklassifizierungsmethode gefunden, welche markante Merkmale (d. h. Merkmale, welche mit hoher Wahrscheinlichkeit erheblich unterschiedliche Werte aufweisen, wenn diese mit Bildern bewertet werden, die aus wenigstens zwei verschiedenen Klassen ausgewählt werden) mit der Genauigkeit vereinigen können, welche von der realistischen Darstellung der Merkmalsverteilung herrührt.

Ein Verfahren, wie im Oberbegriff des Anspruchs 1 beschrieben, wird von H. S. Baird in Computer Vision, Graphics and Image Processing, Band 42, Nr. [3], Seiten 318 bis 333 (1988) "Feature Identification for Hybrid Structural/Statistical Pattern Classification" beschrieben.

Zusammenfassung der Erfindung

Erfindungsgemäß bilden wir eine Familie von Klassenmetriken dc(x) ≥ 0, und zwar eine für jede Klasse c, wobei jede einen Abstand von einem unbekannten Bild x zur bestimmten Klasse c berechnet. Wenn eine Familie von perfekten (oder nahezu perfekten) Metriken vorgegeben ist, kann die Klassifizierung gemäß dem minimalen Abstand durchgeführt werden: die Klasse c, für welche dc(x) das Minimum ist, wird als bevorzugte Klasse für x zurückgegeben.

Wir sagen, daß eine Klassenmetrik dc(x) ≥ 0 perfekt ist, wenn für jedes Bild x und jede Klasse c dc(x) = 0 ist, und zwar dann und zwar nur dann, wenn x sich in der Klasse c befindet. Eine perfekte Metrik verhält sich wie eine "ideale Hinweisfunktion" für die Klasse, und zwar ist sie Null in deren Verteilung und streng positiv außerhalb dieser. In der Praxis selbstverständlich sind diese Metriken nicht konstant perfekt; sie können jedoch diesem Zustand sehr nahe kommen. Unser Klassifizierungsverfahren kann mit diesen vollkommenen oder nahezu vollkommenen Metriken verwendet werden. Als Ergebnis kann unser Verfahren eine hohe Genauigkeit (wenigstens so gut wie die klassischen vergleichbaren Verfahren), ein ausgezeichnetes Zurückweisungsverhalten, das einige bekannte konkurrierende Verfahren übertrifft, und eine schnelle Konvergenz während des Trainings erreichen, die ein sofortiges erneutes Training und eine automatische Spezialisierung ermöglicht.

Erfindungsgemäß erstellen wir für jede Klasse eine detaillierte jedoch raumsparende Darstellung der empirischen klassenbedingten Verteilung der Merkmalswerte, welche wir als Verteilungsliste bezeichnen. Bei einer beispielhaften Verteilungsliste kann jeder Wert von jedem Merkmal durch ein Bit dargestellt werden, welches auf Eins gesetzt wird, dann und nur dann, wenn dieser Merkmalswert in den Trainingsdaten für diese Klasse vorkommt.

Im Einsatz vergleicht ein erfindungsgemäßer Bildklassifizierer eine Testliste basierend auf Merkmalen, die aus einem Eingangsbild ermittelt werden, mit mehreren Klassenverteilungslisten basierend auf einer Gruppe von Trainingsbildern. Das Eingangsbild wird der Klasse der Klassenverteilungsliste mit dem kleinsten Abstand zur Testliste zugeordnet. Bei einer beispielhaften Ausführungsform ist die Verteilungsliste mit dem kleinsten Abstand zur Testliste diejenige Verteilungsliste, welche die größte Anzahl von Merkmalswerten mit der Testliste gemeinsam hat.

Demgemäß ist die Erfindung in einem weiten Sinne ein Bildklassifizierer zum Empfangen eines Eingangsbildes und zum Zuordnen des Eingangsbildes zu einer Vielzahl von Bildklassen durch Vergleichen des Eingangsbildes mit einer Trainingsgruppe von Trainingsbildern. Der Bildklassifizierer umfaßt eine Vielzahl von Klassenverteilungslisten. Jede dieser Listen basiert auf einer Vielzahl von Merkmalen, welche aus Trainingsbildern ermittelt werden, und jede Liste stellt diese Merkmalswerte dar, die wenigstens einmal in der Trainingsgruppe für Trainingsbilder vorkommen, die zu der entsprechenden Klasse gehören.

Der Bildklassifizierer umfaßt ferner eine Einrichtung zum Bilden einer Testliste durch Bestimmen der Vielzahl von Merkmalen aus dem Eingangsbild und eine Einrichtung zum Vergleichen der Testliste mit den Klassenverteilungslisten, um zu identifizieren, welche der Klassenverteilungslisten den geringsten Abstand zur Testliste aufweist.

Im wesentlichen ist wenigstens eines der Merkmale gemäß einer Regel definiert, welche sich auf die Formen der Bilder aus wenigstens einer Bildklasse bezieht.

Kurze Beschreibung der Zeichnungen

Fig. 1 zeigt ein Flußdiagramm eines beispielhaften Trainingsvorgangs, das in Verbindung mit der Erfindung nützlich ist.

Fig. 2 zeigt ein Flußdiagramm eines beispielhaften erfindungsgemäßen Prüfvorgangs.

Fig. 3 zeigt eine beispielhafte Klassenverteilungsliste.

Fig. 4 zeigt eine beispielhafte Berechnung eines Abstandes zwischen einer Testliste und der Klassenverteilungsliste nach Fig. 3.

Fig. 5 und 6 zeigen eine mögliche Prozedur zum Erzeugen eines neuen Merkmales, z. B. aus einer Eingangsdarstellung eines Trainingsbildes. Der Einfachheit halber weist der durch Fig. 5 dargestellte Raum lediglich zwei Dimensionen auf.

Fig. 7 zeigt eine beispielhafte Verteilungsliste für ein einzelnes Muster, welches ein chinesisches Zeichen darstellt.

Fig. 8 zeigt eine Gruppe von drei Verteilungslisten für jeweilige Klassen von chinesischen Zeichen.

Detaillierte Beschreibung einer bevorzugten Ausführungsform

Wir haben erkannt, daß es wünschenswert ist, Trainingsgruppen durch pseudo-zufällige Simulation realistischer Modelle von Bilddefekten zu bereichern oder zu erzeugen. Beispielsweise beschreibt H. S. Baird, in "Document Image Defect Models", in H.5. Baird et al., Eds., Structured Document Image Analysis, Springer-Verlag (1992) ein parametrisiertes Modell von Bilddefekten. Das Modell beschreibt eine Parameterverteilung, die einen Verzerrungsalgorithmus bestimmt, der mit Prototypbildern hoher Qualität betrieben wird, welcher sich der Natur des Drucks und der Bilderfassung annähert. Durch pseudo-zufällige Abtastung der Verteilung können Trainings- und Testgruppen unbeschränkter Größe erzeugt werden. Daher bestehen für die Größe der Trainingsgruppen keine Grenzen, außer denen, welche durch unsere Computerumgebung auferlegt sind. Und da sowohl die Trainings- als auch Testgruppen aus der gleichen Verteilung zufällig gewählt sind, ist die Trainingsgruppe durch den Aufbau dargestellt.

Eine große Freiheit besteht bei der Auswahl geeigneter Metrikmerkmale. Wir haben jedoch erkannt, daß viele Merkmale, die auf dem Gebiet der optischen Zeichenerkennung (OCR) bekannt sind, sich in einem perfekten Metrikansatz, wie dem erfindungsgemäßen Verfahren, ausführen lassen. (Typische Merkmale sind niederwertige Polynomfunktionen der Bildpixelwerte.) Darüberhinaus haben wir erkannt, daß Algorithmen zum automatischen Bilden von Merkmalen wirkungsvoll zum Auffinden kleiner Merkmalsgruppen sind, welche hochgenaue Klassifizierungen unterstützen.

Wie erwähnt, wird eine gewisse Unterscheidung durch Merkmale genauso einfach wie durch zufällig ausgewählte Pixelpaare erreicht (siehe Bledsoe, vorstehend zitiert). Wir haben jedoch erkannt, daß die Genauigkeit stark verbessert wird, wenn wenigstens ein Merkmal gemäß einer Regel definiert wird, die sich auf die Bildformen von wenigstens einer Bildklasse beziehen. D. h., ein höchst wirkungsvolles Merkmal ist im Allgemeinen eines, welches a priori so ausgewählt wird, weil es bekannt ist, eine gewisse Unterscheidung zwischen wenigstens einem Paar von Bildklassen bereitzustellen (wie z. B. in der Trainingsgruppe dargestellt). Beispielsweise können Merkmale aus einer Liste bekannter Merkmale gemäß deren Leistungsfähigkeit aus der Trainingsgruppe ausgewählt werden. Alternativ können Merkmale in Bezug auf die Trainingsgruppe gebildet werden. (Ein beispielhaftes Verfahren zum Bilden von Merkmalen ist nachfolgend beschrieben).

Daher können Merkmale am Anfang manuell spezifiziert werden, während der Prüfung der Trainingsgruppe automatisch gebildet werden, oder beides. In jedem Fall wird eine Zahl M von Merkmalen ultimativ gewählt. Erforderlich ist, daß der Bereich jedes Merkmales aus mindestens V verschiedenen Werten besteht.

Wir stellen jedes Bild, ob in der Trainingsgruppe oder in der Testgruppe (zu klassifizieren) als einen Vektor von M Merkmalswerten dar.

Wir entwerfen eine Verteilungsliste für jede Klasse. Bei bevorzugten Verteilungsliste wird jeder Wert jedes Merkmals durch ein Bit dargestellt, welches auf Eins gesetzt wird, dann und nur dann, wenn der Wert des Merkmales in den Trainingsdaten für diese Klasse vorkommt. Jede Klassenverteilungsliste enthält M * N Bits.

Während der Erkennung wird ein Eingangsbild beispielhaft wie folgt klassifiziert:

a) Berechnen des Vektors der Merkmalswerte für das Eingangsbild,

b) Berechnen eines nicht negativen ganzzahligen Abstandes für jede Klasse durch Addieren von Eins zum Klassenabstand für jedes Merkmal, dessen Eingangswert nicht in der Verteilungsliste dieser Klasse vorkommt.

c) Zuordnen der Klasse, für welche dieser Abstand minimal ist, zum Eingangsbild,

d) optionales Zurückweisen oder Kennzeichnen von Bildern, als "mehrdeutig" für welche ein Zusammenhang zwischen einem und mehreren Abständen besteht,

e) optionales Zurückweisen oder Kennzeichnen von Bildern, als "mehrdeutig" für welche die Lücke zwischen dem minimalen Abstand und dem nächstkleineren kleiner als ein gegebener Schwellenwert ist, und

f) optionales Zurückweisen von Bildern, für welche der minimale Abstand einen gegebenen Schwellenwert überschreitet.

Beispielsweise nimmt der im Flußdiagramm nach Fig. 1 dargestellte Trainingsprozess als Eingangssignal Umrißbeschreibungen der Zeichenform für eine vorbestimmte Anzahl F verschiedener Schrifttypen und N Symbole (die jeweils einer anderen Klasse entsprechen), welche in jeder der F Schrifttypen dargestellt sind. Das Eingangssignal umfaßt ferner eine Gruppe von Parameterwerten, die ein vorbestimmtes Defektmodell beschreiben. Das Ausgangssignal des Prozesses ist eine Verteilungsliste. Zusätzlich zu F und N umfassen numerische Konstanten die Anzahl M numerischer Merkmale, den maximalen ganzzahligen Wert V der (normalisierten) Merkmale und die Anzahl D verzerrter Muster, welche für jedes Symbol-Schrifttypenpaar zu erzeugen sind.

Für jedes Symbol in jedem Schrifttyp wird die Umrißformbeschreibung gelesen (Schritt A) und D verzerrte Musterbilder werden gemäß einem vorbestimmten Defektmodell (Schritt B) erzeugt. Für jedes verzerrte Bild werden M numerische Merkmale gewonnen (Schritt C). Der Wert jedes dieser Merkmale wird zu einem Wert v normiert, der innerhalb des Bereichs 1-V liegt (Schritt D), wobei das entsprechende Bit auf eine logische Eins in der Verteilungsliste gesetzt (Schritt E) wird.

Ferner nimmt beispielhaft der im Flußdiagramm nach Fig. 2 dargestellte Prüfvorgang als Eingangssignal eine Verteilungsliste und ein Bild unbekannter Klasse an. Das Ausgangssignal dieses Prozesses besteht aus einer Liste von Paaren der Form (Klassenindex, Abstand), die in aufsteigender Abstandsreihenfolge geordnet sind.

M numerische Merkmale werden aus dem Eingangsbild gewonnen (Schritt F). Jedes Merkmal wird wie vorstehend beschrieben normiert (Schritt G); dies führt zu einem normierten Merkmalswert v. Für jedes Merkmal wird das Bit b in der Eingangsverteilungsliste, welche der aktuellen Klassen-Merkmals-Wertekombination entspricht, abgefragt (Schritt H). Wenn das Bit AUS ist, wird das Element des Abstandsfeldes, welches der aktuellen Klasse entspricht, um Eins inkrementiert (Schritt I). Nachdem die Elemente des Abstandsfeldes alle bewertet worden sind, werden diese in aufsteigender Reihenfolge geordnet (Schritt J). Dieses geordnete Feld führt unmittelbar zum Ausgangssignal des Prüfvorgangs.

Der Prüfprozess ist ferner in Bezug auf die Fig. 3 und 4 dargestellt. Die aus einem Testbild gewonnenen Merkmale weisen die in Zeile 10 nach Fig. 4 aufgelisteten Werte auf. Eine Null wird in Zeile 20 derselben Figur für jeden Merkmalswert eingegeben, der ferner in der entsprechenden Spalte der Klassenverteilungsliste nach Fig. 3 vorkommt. Eine Eins wird für jeden Merkmalswert eingegeben, welcher nicht in der entsprechenden Spalte der Klassenverteilungsliste vorkommt. Für die durch die Liste nach Fig. 3 dargestellte Klasse wird das entsprechende Element des Abstandsfeldes durch Summieren der Einträge in Zeile 20 nach Fig. 4 bewertet.

Wünschenswert ist, Trainingsdaten hoher Güte zu haben, d. h. Daten, welche wirklich repräsentativ und von mehr als geeigneter Größe sind. Aus diesem Grund sollte die kleinste Trainingsgruppe wenigstens k * V Muster/Klassen enthalten, wobei k eine ganze Zahl größer als 1 ist. Bevorzugt ist k wenigstens 10, weil Trainingsgruppen, welche wesentlich weniger als 10 · V Muster je Klasse aufweisen, keine Merkmalswerte mit beträchlichen Häufigkeitsraten aufweisen können.

Wenn die Trainingsgruppe zufällig aus einer guten Näherung zur wahren Defektverteilung ausgewählt worden ist, hilft dieses Kriterium der minimalen Größe sicherzustellen, daß jeder Merkmalswert, welcher in der wahren Verteilung vorkommen kann, mit hoher Wahrscheinlichkeit auch in der Trainingsgruppe vorkommt.

Erwähnt sei, daß beim beispielhaften Erkennungsprozess jedes Merkmal eine Null oder Eins zum End- "Abstand", der von jeder klassischen Metrik berechnetet wird, beitragen kann. D. h., jedes Merkmal trägt den gleichen Abzug bei einer Nichtübereinstimmung bei, auch wenn der Bereich mancher Merkmale (die Anzahl verschiedener Merkmalswerte) größer als der andere sein kann.

Die Wahl von V kann für den Erfolg kritisch sein. Wenn V klein ist (beispielsweise kleiner als 5) nehmen wir an, daß es unwahrscheinlich ist, daß sich die Merkmale gut unterscheiden. Wenn V groß ist (beispielsweise größer als 500), dann sind die Verteilungslisten unerwünscht groß und die Anzahl der erforderlichen Trainingsdaten ist übermäßig groß. Daher liegt ein bevorzugter Bereich für V zwischen 5 und 500. Wir bezeichnen diesen Bereich als "mäßig grobe Quantisierung" der Merkmalswerte.

In dieser Hinsicht sei erwähnt, daß die Anzahl von Merkmalen nicht vorher festgelegt werden muß. Statt dessen kann diese während des Trainings unter Ansprechen auf die Trainingsgruppenstatistiken wachsen.

Konstruktionsmerkmale für perfekte Metriken

Nachfolgend ist mit Bezug auf die Fig. 5 und 6 ein Verfahren zum Auswählen von Merkmalen aus einer bestimmten Familie von Funktionen beschrieben. Dieses Verfahren garantiert eine maximale Unterscheidung. Dieses Verfahren beseitigt fortlaufend Mehrdeutigkeiten in der Trainingsgruppe durch Hinzufügen neuer Merkmale. Gewährleistet ist, daß dieses abgeschlossen wird, wenn alle Klassen sich unterscheiden oder nur eine intrinsische Mehrdeutigkeit übrigbleibt.

Das Verfahren nähert sich der Reihe nach an jede Klasse c an. Bei jeder Iteration werden alle Trainingsmuster in zwei Gruppen S&sub1; und 8S&sub2; aufgeteilt, wobei S&sub1; Bilder der Klasse c (in der Figur durch schwarze Punkte dargestellt) und S&sub2; Bilder aller anderen Klassen (in der Figur durch weiße Punkte dargestellt) enthält. Der Mustermittelwert 30, 40 jeder Gruppe wird berechnet. Eine Gerade 50, welche durch die Mustermittelwerte verläuft, ist eingezeichnet. Alle Muster werden dann auf diese Gerade projiziert. (Mehrere beispielhafte Projektionen sind als unterbrochene Linien in · Fig. 5 gezeigt.) Der Projektionsbereich wird dann gleichmäßig in eine feste Anzahl von Segmenten geteilt, wie in Fig. 6 gezeigt. Ein Segment ist mit "EIN" für eine Klasse gekennzeichnet, wenn die Projektion eines Musters dieser Klasse auf diesem Segment liegt. Die Gerade 50 wird als "Merkmal" betrachtet (im vorstehend beschriebenen Sinn) und die Indizes der Segmente sind die Werte, welche dieses Merkmal annehmen kann. Die gekennzeichneten Segmente bilden eine Verteilungsliste für dieses Merkmal. Wenn kein Segment für S&sub1; und S&sub2; gekennzeichnet ist, haben wir ein Unterscheidungsmerkmal für alle Bilder in S&sub1; erzielt und das Verfahren wird beendet (für die Klasse c). Anderenfalls wird S&sub1; entfernt und nur die Muster, die mit S&sub2; überlappen, bleiben übrig. (Beispielsweise ist das Segment 2 nach Fig. 6 sowohl für S&sub1; als auch für S&sub2; gekennzeichnet.) Das Verfahren wird dann unter Verwendung des entfernten S&sub1; und aller Bilder in S&sub2; wiederholt. In dem Fall, daß alle Muster in S&sub1; mit denen von S&sub2; überlappen, wird S&sub1; in zwei Hälften geteilt und das Verfahren wird auf jede Hälfte angewandt. Dies wird fortgesetzt, bis entweder S&sub1; leer ist oder es unmöglich ist, S&sub1; und S&sub2; durch eine Projektion zu trennen (z. B. wenn alle Bilder in S&sub1; und S&sub2; identisch sind).

Beispiel

Wir haben einen Klassifizierer für die vier meistverwendeten Schrifttypen im gedruckten chinesisch gebildet: Song, Fang Song, Hei und Kai. Die Textgröße reicht von 7 Punkten bis 14 Punkten, bei einer räumlichen Abtastrate von 400 Pixel pro Inch. Die Experimente umfaßten sämtlich 3755 Zeichenklassen der Guoßiao-Kodierung GB2312-80, Stufe 1 (siehe Code of Chinese Graphic Character for Information Interchange, Primary Set (GB2312-80), National Standards Bureau, Peking, China 1980)). Wir wählen einige Merkmale, die in veröffentlichten chinesischen Erkennungssystemen (siehe S. Mori et al. "Research on Machine Recognition of Handprinted Characters", IEEE Trans. on Pattern Analysis and Machine Intelligence PAMI-6,4 (Juli 1984), 386-405) häufig verwendet werden. Das binäre Bild eines Eingangszeichen wurde zuerst durch einfaches Skalieren und Zentrieren in der Größe zu einer 48 · 48 binär bewerteten Pixelmatrix normiert. D. h., jedes Bild wurde auf einen Punkt in einem binär bewerteten Vektorraum mit 48 · 48 = 2304 Dimensionen abgebildet, welcher höchstens 2²³&sup0;&sup4; 10&sup6;&sup9;&sup4; verschiedene Punkte enthält.

Wir haben drei ganzzahlig-bewertete Merkmalsgruppen verwendet: senkrechte und waagerechte Projektionsprofile, Abstände von Außenlinien zur Begrenzungsbox oder zum Begrenzungsbereich und Verteilungen der gewählten Richtungen.

Die Projektionsmerkmale wurden wie folgt berechnet. Der Bildbereich wurde in eine obere und eine untere Hälfte unterteilt und ein senkrechtes Projektionsprofil (Zählen der Anzahl der schwarzen Pixel in jeder Spalte) wurde für jede Hälfte berechnet. In ähnlicher Weise wurden für die linke und rechte Hälfte zwei waagerechte Projektionsprofile erhalten, Diese vier Profile wurden dann aneinandergereiht, um einen Vektor mit 48 · 4 = 192 Dimensionen zu bilden, wobei jeder ganzzahlige Wert des Projektionsmerkmals im Bereich von [0,24] liegt.

Die Umrißmerkmale bilden Abstände von jedem der vier Ränder der Begrenzungsbox zur Außenlinie des Zeichens. Für jede Spalte berechneten wir den Abstand vom oberen Rand der Box zum ersten schwarzen Pixel der Spalte und vom unteren Rand zum letzten schwarzen Pixel. In ähnlicher Weise berechneten wir für jede Zeile den Abstand vom linken Rand zum äußerst links liegenden schwarzen Pixel und vom rechten Rand zum äußerst rechts liegenden schwarzen Pixel. Diese Abstände bildeten einen Vektor von 48 · 4 = 192 Dimensionen, wobei jeder ganzzahlige Wert des Umrißmerkmals im Bereich von [0,48] liegt.

Das Linien-Richtungsmerkmal wurde durch eine Strecken- Längen-Analyse (run length analysis) wie folgt berechnet. Von jedem schwarzen Pixel berechneten wir die Länge der schwarzen Strecken, welche dieses Pixel enthalten, wenn diese sich in vier Richtungen (waagerecht, nordost-südwest-diagonal, senkrecht und nordwest-südost-diagonal) erstrecken. Das Pixel wurde dann mit der Richtung gekennzeichnet, in welche die Streckenlänge maximal war. Dann teilten wir den Bildbereich in 16 (12 · 12) quadratische Bereiche und zählten die Anzahl von Pixeln von jedem der vier Typen in jedem Bereich. Diese Zählwerte wurden in einem Vektor von 16 · 4 = 64 Dimensionen gespeichert, wobei jeder ganzzahlige Wert des Linien- Richtungsmerkmals im Bereich [0,144] liegt.

Jedes Zeichenbild wurde auf einen Punkt in einem ganzzahligen Vektorraum von 192 + 192 + 64 = 448 Dimensionen abgebildet, der höchstens 25¹&sup9;² · 49¹&sup9;² · 145&sup6;&sup4; 10&sup7;³¹ verschiedene Punkte enthält.

Wir komprimierten die ganzzahligen Bereiche sowohl der Umfangsmerkmale als auch der Linien-Richtungsmerkmale, so daß diese im Bereich [0,24] lagen. Dies stimmt mit dem Bereich der Projektionsmerkmale überein. Wir erzeugten Trainingsgruppen mit 800 Mustern je Klasse, so daß wir für jedes Merkmal 32 mal mehr Muster als Merkmalswerte hatten.

Um die verzerrten Muster zu erzeugen, verwendeten wir ein explizites, quantitatives und parametrisches Modell für Druck-, Seh-, und Digitalisierungsdefekte sowie einen pseudozufälligen Bildgenerator, um das Modell zu implementieren. Die Modellparameter spezifizierten die nominale Textgröße des Ausgangssignals (in Punkteinheiten), die räumliche Ausgangsabtastrate (digitalisierte Auflösung in Pixel/Inch), die Punktaufweitungsfunktion (der Standardfehler des Gaußverbreiteten Kerns (blurring kernel) in der Einheit von Ausgangspixel), den digitalisierten Schwellenwert (in der Einheit der Intensität, wobei 0,0 weiß und 1,0 schwarz darstellt), die Empfindlichkeitsverteilung unter den Pixelsensoren (ein zum Schwellenwert addierter Rauschterm), die Schwankungsverteilung unter den Pixeln (d. h. die Unterschiede der Sensormitten von einem idealen Quadratgitter in der Einheit der Ausgangspixel), Drehung (schiefwinklig), Dehnfaktoren (sowohl waagerecht als auch senkrecht) und den Translationsversatz in Hinsicht auf das Pixelgitter.

Die nominalen Textgrößen der Trainingsgruppendaten betrugen 7, 9, 11 und 13 Punkte und für die Testgruppe 8, 10, 12 und 14 Punkte. Der Pseudo-Zufallsgenerator akzeptierte eine Verteilungsspezifikation dieser Parameter. Jeder Parameter wurde unabhängig und zufällig festgelegt. Die bei diesen Experimenten verwendeten Verteilungen waren wie folgt. Die digitale Auflösung wurde bei 400 Pixeln je Inch festgelegt. Der Standardfehler des Gaußverbreiteten Kerns änderte sich von Bild zu Bild normalerweise mit einem mittleren Wert von 0,7 und einem Standardfehler von 0,3 (Ausgangspixel). Der binäre Schwellenwert änderte sich von Bild zu Bild, normalerweise mit einem Mittelwert von 0,25 und einem Standardfehler von 0,04 (Intensität). Die Empfindlichkeit des Pixelsensors änderte sich von Pixel zu Pixel, normalerweise mit einem Mittelwert von 0,125 und einem Standardfehler von 0,04 (Intensität). Die Jitter änderten sich von Pixel zu Pixel, normalerweise mit einem Mittelwert von 0,2 und einem Standardfehler von 0,1 (Ausgangspixel). Der Winkel änderte sich von Bild zu Bild, normalerweise mit einem Mittelwert von 0 und einem Standardfehler von 0,7 Grad. Der die Breite beeinflussende multiplikative Faktor änderte sich gleichförmig im Intervall [0,85, 1,15] und der die Höhe beeinflussende multiplikative Faktor veränderte sich normalerweise mit einem Mittelwert von 1,0 und einem Standardfehler von 0,02. Der Translationsversatz wurde einheitlich im Bereich [0,1] gewählt, und zwar in der Einheit Ausgangspixel.

Für jeden Schrifttyp/Größe/Symboltripel wurden 50 Muster für eine gesamte Trainings-/Prüfgruppe von 200 für jeden Schrifttyp/Symbolpaar und dadurch 800 insgesamt für jedes Symbol erzeugt.

Die Merkmalsextraktoren wurden auf jedes Trainingsmuster angewendet. Wir können das Ergebnis entweder als ganzzahlig bewerten Vektor mit 448 Dimensionen oder gleichbedeutend als Binärwertvektor mit 448 · 25 = 11200 Dimensionen betrachten, der hierin als "Verteilungsliste» bezeichnet wird. Bei einer Verteilungsliste für ein einzelnes Muster ist jedes Merkmal durch 25 Bit dargestellt und für ein einzelnes Muster wird ein einzelnes Bit auf Eins gesetzt und kennzeichnet den Merkmalswert. Diese Verteilungsliste ist in Fig. 7 gezeigt.

Für jede Klasse wurden die Verteilungsliste für 800 Trainingsabtastwerte in einer Liste durch Berechnen von deren Boolschen Einheit verknüpft. Bei dieser Klassenverteilungsliste ist jeder Merkmalswert, der wenigstens einmal in der Trainingsgruppe vorkommt, durch ein Bit, welches auf Eins gesetzt ist, dargestellt, und mit Null bewertete Bits stellen Merkmalswerte dar, welche niemals vorkommen. Wir kombinierten die Trainingsdaten für alle vier Schrifttypen in einer einzelnen Gruppe von Klassenverteilungslisten. Die Verteilungslisten der ersten drei Klassen, die bei unseren Versuchen verwendet wurden, sind in Fig. 8 gezeigt. Der Klassifizierer ist vollständig durch die Gruppe aller 3755 Verteilungslisten beschrieben, und zwar insgesamt für 3755 · 11200 42,1 Mbits oder 5,26 Mbytes eines Speichers.

Während des Prüfens haben wir die Merkmale jedes Zeichenbildes gewonnen und passten die Merkmale dür jede Klasse an die Klassenverteilungsliste an. Dies wurde durch Berechnen eines 448-Bit-Vektors durchgeführt, in welchem das Bit, welches jedem Merkmalsbit entspricht zu Eins gesetzt wurde, dann und nur dann, wenn der Merkmalswert in der Klassenverteilungsliste vorkam. Zuletzt wurde der "Abstand" der Klasse als Hammingabstand dieses Vektors zu einem idealen Vektor, der alle Einsen umfaßt, verwendet.

Wir bewerteten die Leistungsfähigkeit des Klassifizierers für die 3755 Klassen in der gesamten GB2312- 80 Stufe 1. Der Klassifizierer wurde mit 800 Abtastwerten in allen 3755 Klassen trainiert und mit weiteren 800 Abtastwerten für jede Klasse geprüft. Eine Gesamtanzahl von 800 · 3755 = 3.004.000 Abtastwerten wurde geprüft. Die Tabelle 1 faßt die Klassifizierungsergebnisse zusammen. Die Tabelle 2 zeigt die Anzahl der Fehler und korrekter Raten in Nachbarschaft verschiedener Größen um die optimale Wahl herum. (Das heißt, es gibt eine "fehlerfreie" Zählung, wenn sich die fehlerfreie Klasse irgendwo innerhalb der gegebenen Nachbarschaft befindet.)

Tabelle 1
Schrifttyp
Tabelle 2 N: Größe der Nachbarschaft
N: Größe der Nachbarschaft


Anspruch[de]

1. Verfahren zur Zeichenerkennung, welches folgende Verfahrensschritte umfaßt:

Empfangen eines Eingabebildes eines Zeichens, das einer von mehreren Bildklassen (A & B) zuzuordnen ist;

Gewinnen eines jeweiligen numerischen Wertes (C) aus jedem von mehreren Merkmalen des Eingabebildes, wobei wenigstens eines der Merkmale gemäß einer Regel festgelegt wird, die sich auf die Bildformen wenigstens einer der Bildklassen bezieht,

Aufzeichnen der Merkmalswerte des Eingabebildes,

Bereitstellen einer Tabelle für diese Merkmalswerte, die in einem Trainingssatz auftreten, wobei:

der Trainingssatz für jede Bildklasse eine Mehrzahl von Trainingsbildern enthält, von welchen bekannt ist, daß diese zu dieser Klasse gehören, und wobei die Tabelle jedem tabellarisierten Merkmalswert eine entsprechende Klasse (D & E) zuordnet,

Vergleichen der Merkmalswerte des Eingabebildes mit wenigstens einigen der tabellarisierten Merkmalswerten des Trainingsbildes, und

Zuordnen des Eingabebildes zu einer der Bildklassen auf der Grundlage eines Ergebnisses des Vergleichsschrittes,

dadurch gekennzeichnet, daß

der Verfahrensschritt des Bereitstellens einer Tabelle das Bilden, einer jeweiligen Klassen verteilungskarte für jede Bildklasse umfaßt;

jede Klassen-Verteilungskarte für jedes der Merkmale eine Aufzeichnung jedes numerischen Wertes des Merkmales enthält, das durch wenigstens ein Trainingsbild der geeigneten Klasse dargestellt wird,

der Vergleichsschritt das Auswerten eines jeweiligen Klassenabstandes zwischen jeder Klassenverteilungskarte und einer Testkarte umfaßt, welche die jeweiligen Merkmalswerte des Eingabebildes tabellarisiert; daß

beim Zuordnungsschritt das Eingabebild der Klasse zugeordnet wird, welche die Klassenverteilungskarte mit dem geringsten Abstand aufweist, der im Vergleichsschritt ermittelt worden ist; daß

jeder Klassenabstand durch Zählen nicht übereinstimmender Merkmale bestimmt wird; daß

ein Merkmal nur dann als nicht übereinstimmend gezählt wird, wenn der numerische Wert des Merkmales, der aus dem Eingabebild bestimmt wird, nicht mit einem der numerischen Wert des Merkmals übereinstimmt, die in der geeigneten Klassenverteilungskarte tabellarisiert sind; und daß

beim Zählen der nicht übereinstimmenden Merkmale jedem Merkmal die gleiche Gewichtung zugewiesen wird.







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