PatentDe  


Dokumentenidentifikation DE69610243T2 25.01.2001
EP-Veröffentlichungsnummer 0740263
Titel Verfahren zum Trainieren einer Erkennungsanlage mit Zeichenmustern
Anmelder Xerox Corp., Rochester, N.Y., US
Erfinder Kopec, Gary E., Belmont CA 94002, US;
Chou, Philip Andrew, Menlo Park CA 94025, US;
Niles, Leslie T., Palo Alto CA 94306, US
Vertreter Grünecker, Kinkeldey, Stockmair & Schwanhäusser, 80538 München
DE-Aktenzeichen 69610243
Vertragsstaaten DE, FR, GB
Sprache des Dokument EN
EP-Anmeldetag 25.04.1996
EP-Aktenzeichen 963028998
EP-Offenlegungsdatum 30.10.1996
EP date of grant 13.09.2000
Veröffentlichungstag im Patentblatt 25.01.2001
IPC-Hauptklasse G06K 9/62

Beschreibung[de]

Die Erfindung betrifft ein Verfahren und eine Maschine zum Trainieren eines Satzes von Zeichenschablonen zur Verwendung in einem Erkennungssystem.

Zeichenerkennungssysteme enthalten typischerweise einen Prozess, in dem das Erscheinungsbild eines isolierten (einzelnen) Eingabezeichenbildes (oder "Glyphs") analysiert und in einem Entscheidungsfindungsprozess als ein gesondertes Zeichen in einem vorbestimmten Zeichensatz klassifiziert wird. Der Ausdruck "Glyph" bezieht sich auf ein Bild, das ein realisiertes Beispiel eines Zeichens darstellt. Die Klassifizierungsanalyse enthält typischerweise den Vergleich von Charakteristiken einzelner Eingabeglyphs (z. B. seines Pixefinhalts oder anderer Charakteristiken) mit Einheiten von Referenzinformationen über Zeichen in dem Zeichensatz, wobei jede von ihnen Charakteristiken der "idealen" visuellen Darstellung eines Zeichens in seiner besonderen Größe, Schriftart (Font), und seinem Stil definiert, so als erschiene er in einem Bild, wenn es kein Rauschen oder keine Verzerrung gäbe, die von dem Bilderzeugungsprozess eingeführt werden. Die Einheit der Referenzinformationen für jedes Zeichen, üblicherweise mit ºZeichenschablone", "Schablone" oder "Prototyp" bezeichnet, enthält Identifikationsinformationen, auf die als "Zeichenlabel" Bezug genommen wird, die das Zeichen eindeutig als eines der Zeichen in dem Zeichensatz identifizieren. Das Zeichenlabel kann auch solche Informationen wie etwa den Zeichenfont, die Punktgröße und den Stil enthalten. Ein Zeichenlabel wird als die Identifikation des Eingabeglyphs ausgegeben, wenn die Klassifizierungsanalyse feststellt, dass eine hinreichende Übereinstimmung zwischen dem Glyph und den Referenzinformationen, die das Zeichenlabel angegeben, hergestellt worden ist.

Auf die Darstellung der Referenzinformationen, die eine Zeichenschablone umfassen, kann als ihr Modell Bezug genommen werden. Ein Typ des Zeichenschablonenmodells ist als Bitmapbild (oder binäres Bild) eines Zeichens bekannt. Innerhalb der Kategorie binärer Zeichenschablonenmodelle sind wenigstens zwei verschiedene Modelltypen definiert worden: ein Modell kann als "segmentierungsbasiertes" Modell bezeichnet werden und beschreibt eine Zeichenschablone als vollständig in einen rechteckigen Bereich passend, auf den als "Bounding-Box" Bezug genommen wird, und beschreibt das Kombinieren benachbarter Zeichenschablonen als "disjunkt", was bedeutet, dass das Kombinieren nichtüberlappender Bounding-Boxen erfordert. Die US-A-5,321,773 offenbart ein anderes binäres Zeichenschablonenmodell, das auf dem Sidebearing- Modell der Buchstabenformumrissbeschreibung und -positionierung basiert, die auf dem Gebiet der digitalen Typografie verwendet werden. Das Sidebearing-Modell, das unten bei der zu Fig. 1 gehörenden Diskussion genauer beschrieben wird, beschreibt das Kombinieren von Schablonen, um überlappende rechteckige Bounding-Boxen zuzulassen, solange die (z. B. typischerweise schwarzen) Vordergrundpixel einer Schablone nicht mit den Vordergrundpixeln einer benachbarten Schablone geteilt werden oder diese beiden gemeinsam sind; dies wird so beschrieben, dass die Schablonen im Wesentlichen "disjunkte Grundlagen (Supports)" haben müssen.

Das Trainieren von Zeichenschablonen ist der Prozess des Verwendens von Trainingsdaten, um die für den Erkennungsprozess verwendeten Schablonen zu erschaffen, zu erzeugen und auf den neuesten Stand zu bringen. Trainingsdaten können allgemein als eine Sammlung (Kollektion) von Zeichenbildproben definiert werden, jeweils mit einem zugewiesenen Zeichenlabel, das das Zeichen in dem Zeichensatz identifiziert, das es repräsentiert, wobei die Proben die Informationen bereitstellen, die notwendig sind, um Schablonen gemäß dem Zeichenschablonenmodell, das die Schablonen definiert, zu erzeugen. Trainingsdaten enthalten dann wenigstens zwei Komponenten: (1) eine Glyphprobe und (2) sein identifizierendes Zeichenlabel. Die Effektivität existierender Trainingsprozesse hängt direkt von der Qualität und Genauigkeit der Trainingsdaten ab, und insbesondere von der Qualität des Glyphproben, der korrekten Identifizierung der Zeichenlabel, die den Glyphproben zugewiesen werden sollen, und der Zuweisung korrekter Label an geeignete Glyphproben.

Glyphproben von guter Qualität sind solche, die im Wesentlichen unbeeinträchtigt sind von fehlenden oder überschüssigen Vordergrundpixeln, wenn sie in den Trainingsprozess eingegeben werden. Glyphproben, die von Bitmapbildern stammen, die von wohlbekannten Quellen wie etwa Abtast- und Faxprozessen erzeugt worden sind, sind einer Degradation durch Bildrauschen und -verzerrung unterworfen, die einen Beitrag zur Unbeständigkeit in dem tatsächlichen Erscheinungsbild des Bitmaps leisten.

Ein degradiertes Bitmaperscheinungsbild kann durch ein Originaldokument geringer Qualität verursacht sein, durch einen Abtastfehler, durch Bildversatz oder durch ähnliche Faktoren, die die digitalisierte Darstellung des Bilds beeinflussen. Besondere Probleme in diesem Zusammenhang sind die Tendenzen von Zeichen im Text zu verschmieren oder zu verschmelzen oder auseinanderzubrechen. Auf ein solches degradiertes Bild wird im Folgenden als "verrauschtes" Bild Bezug genommen. Das Erfordernis von Glyphproben guter Qualität als Eingabe in bestehende Trainingsprozesse hat allgemein zu der Beschränkung geführt, dass das Eingabebild, das als Quelle von Glyphproben verwendet wird, relativ rauschfrei sein muss, oder falls verrauschte Bilder zu verwenden gestattet ist, dass irgendein Prozess zum Entfernen oder anderweitigen Kompensieren des Rauschens in den Glyphproben vorgesehen ist.

Erkennungssysteme stellen typischerweise gesonderte Trainingssubsysteme zum Zwecke des Trainierens der Zeichenschablonen bereit. Trainingssysteme können "beaufsichtigt" oder "unbeaufsichtigt" sein. Unbeaufsichtigtes Trainieren beinhaltet im Allgemeinen einen Zweistufenprozess des Erkennens und Trainierens.

Im Zusammenhang dieser Hintergrunddiskussion wird existierendes beaufsichtigtes Training als ein Prozess beschrieben, in dem irgendein Aspekt der Trainingsdaten, zu einem gewissen Grad, speziell durch einen Benutzer für den Trainingsprozess vorbereitet ist. Dies kann entweder das Isolieren der Glyphproben, das Identifizieren der Zeichenlabel, die den Glyphproben zugewiesen werden sollen, oder die tatsächliche Zuweisung der Zeichenlabel an die Glyphproben einschließen, oder alle drei Aspekte. Beaufsichtigtes Trainieren sorgt für die Gelegenheit, neue oder existierende Schablonen unter Verwendung von Trainingsdaten zu trainieren, über die der Benutzer in gewissem Ausmaß eine Kontrolle bezüglich ihrer Qualität und Genauigkeit ausübt.

Bei einem Typ bestehender beaufsichtigter Trainingssysteme ist es erforderlich, dass eingegebene Glyphproben "segmentiert", also isolierte, individuelle und relativ rauschfreie Glyphproben sind, und dass sie mit dem passenden Zeichenlabel vor der Eingabe in den Trainingsprozess versehen sind. Typischerweise gestattet es Software mit einer Benutzerschnittstelle zur Trainingsdatenvorbereitung dem Benutzer, manuell Bounding-Boxen um Glyphproben in einem Bild zu ziehen und ihnen Label zuzuweisen, wobei dem Benutzer die vollständige Kontrolle über die Qualität und Genauigkeit der Trainingsdaten überlassen wird.

Einer oder mehrere der drei Aspekte der Vorbereitung der Trainingsdaten kann automatisiert werden, um das Ausmaß der direkten Benutzereinbeziehung zu reduzieren. Beispielsweise können die Segmentierung der Glyphproben und die Bestimmung von Bounding-Boxen ein automatischer Prozess sein, der auf ein ganzes Textdokumentenbild angewendet wird oder auf ein Bild einer Textzeile oder auf ein Wortbild. Der Benutzer kann Gelegenheit erhalten, die Ergebnisse der automatischen Segmentierung zu inspizieren, falsch segmentierte Proben zu korrigieren und die Zeichenlabel den Proben zuzuweisen.

Ein Bildmodell ist eine Charakterisierung oder Beschreibung des Satzes möglicher Eingabebilder, für die ein Erkennungssystem entworfen ist, in einer Form, die verwendet werden kann, um zu bestimmen, welches der möglichen Bilder zu einem gegebenen Eingabebild am besten passt. Ein Bildmodell stellt A-priori-Informationen über den Satz möglicher Eingabebilder dar und kann von Datenstrukturen unterschieden werden, die ein bestimmtes Eingabebild definieren oder die die Ergebnisse der Durchführung einer Analyse- und Erkennungsprozessierung auf einem bestimmten Bild enthalten.

Ein formales Bildmodell beschreibt einen Satz möglicher Bilder unter Verwendung einer formalen Beschreibungssprache wie etwa einer formalen Grammatik oder eines Finitzustandsübergangsnetzwerks. Eine formale Grammatik ist ein Satz von Regeln, der die zuzulassenden Formate (die Syntax) definieren, die Aussagen in einer bestimmten Sprache einhalten dürfen. Grammatiken können dem Typ nach als uneingeschränkt, kontextempfindlich, kontextfrei und regulär charakterisiert werden, und ein bestimmter Grammatiktyp kann mehr oder weniger für ein bestimmtes Bildmodell geeignet sein.

Das Design jedes Texterkennungssystems basiert auf entweder einem expliziten oder einem impliziten Bildmodell. Die zu treffende Unterscheidung ist die, ob das Bildmodell explizit und formal in einer Weise aufgestellt ist, die unabhängig von Prozessierungsalgorithmen ist, die das Modell verwenden, oder ob das Modell nur implizit dargestellt wird als ein Kodeblock, der Bildanalysevorgänge durchführt. Ein formales Bildmodell ist in diesem Zusammenhang analog zu einer formalen Grammatik in einem grammatikbasierten Zeichenstring-Parsingsystem, die als eine explizite Datenstruktur besteht, die unabhängig von dem Kode des Parsers ist, der sie verwendet.

Formale Bildmodelle können eine nulldimensionale (OD), eindimensionale (1 D) oder zweidimensionale (2D) Form annehmen.

H. S. Baird, "A Self-Correcting 100-Font Classifier", SPIE Bd. 2181 Document Recognition 1994, offenbart eine Möglichkeit des Trainierens von Merkmalsschablonen für eine Polyfont-Erkennung, die ein nulldimensionales Bildmodell verwendet. Baird offenbart ein Selbstkorrekturverfahren, in dem ein Polyfont-Klassifizierer, der jedes von 100 Schriftbildern mäßig gut erkennen kann, sich selbst automatisch auf das einzige aber ansonsten unbekannte Schriftbild spezialisieren kann, das er gerade liest. Das Verfahren erfordert einen Polyfont-Klassifizierer, der zwischen N Zeichenklassen (Symbolklassen) {ci}i=1,N über eine große Anzahl von Schriftbildern mit "vernünftig guter" Genauigkeit unterscheiden kann, und es erfordert weiterhin eine Klassifizierungstechnologie, die auf einzelne Proben-Zeichenbilder trainiert werden kann, die mit Klassenlabeln versehen sind. Bairds Schablonentrainingssystem ist eine Form unbeaufsichtigten Lernens, die es erfordert, dass die Bildproben vor der Eingabe in die Klassifizierungs- und Trainingsprozesse isoliert werden.

S. Kuo und O. E. Agazzi, "Keyword spotting in poorly printed documents using pseudo 2D hidden Markov models", IEEE Transactions on Pattern Analysis and Machine Intelligence, Bd. 16, Nr. 8, August 1994, Seiten 842-848 (im Folgenden: Kuo et al.) offenbart einen Algorithmus zur robusten Maschinenerkennung von Schlüsselwörtern, die in einem schlecht gedruckten Dokument eingebettet sind. Die Schablonen, auf die als Modelle Bezug genommen wird, stellen einen Satz von bekannten Schlüsselwörtern dar, auf die eine Anpassung zu erfolgen hat. Für jedes Schlüsselwortmodell werden zwei statistische Modelle, die als "Pseudo-2D-Hidden-Markov-Modelle" oder "PHHM" bezeichnet werden, zur Darstellung des aktuellen Schlüsselworts bzw. aller anderen überschüssigen Wörter erzeugt. In dem Kontext der hier vorgestellten Terminologie ist das PHHM, das eine Schlüsselwortschablone darstellt, ein formales 1D-Bildmodell.

Merkmalsbasiertes Schablonentraining im Zusammenhang eines 1D-Bildmodells zur Verwendung bei der Erkennung von Zeichenstrings (z. B. Wörtern) unabhängig von Zeichen-Boundary-Informationen ist in C. Bose und S. Kuo, "Connected and degraded text recognition using hidden Markov model", Proceedings of the International Conference on Pattern Recognition, Niederlande, Sept. 1992, Seiten 116-119 offenbart. Das darin offenbarte Erkennungsverfahren nimmt an, dass eine Verarbeitung auf Seitenebene unter Verwendung bekannter Algorithmen vor dem Trainingsschritt durchgeführt wird und dass isolierte Wort- oder Zeilenbilder der Erkennung zugeführt werden, die auf einem formalen 1 D-Modell basiert, das als ein Hidden-Markov-Modell ausgedrückt wird. Ein beaufsichtigter Trainingsprozess wird offenbart, der auf einem 0D- Modell des Trainierens individueller merkmalsbasierter Schablonen zu basieren scheint, die jeweils als ein Hidden-Markov-Modell ausgedrückt werden.

Die US-A-5,020,112 und die US-A-5,321,773 offenbaren Erkennungssysteme auf der Grundlage formaler 2D-BÜdmodelle. Die US-A-5,020,112 mit dem Titel "Image Recognition Using Two-Dimensional Stochastic Grammars", erteilt auf den Namen P. A. Chou, einen der vorliegenden Erfinder, offenbart ein Verfahren zum Identifizieren von Bitmapbildobjekten unter Verwendung eines 2D-Bildmodells basierend auf einer stochastischen, kontextfreien 2D-Grammatik. Die US-A-5,020,112 offenbart eine Objektschablonenlibrary (-Bilbliothek), die eine Anzahl von n x m Bitmapschablonen aller Bildobjekte, die möglicherweise von Interesse sind, enthält, von denen jede eine zugeordnete Wahrscheinlichkeit des Auftretens in dem Bild hat. Die Bildglyphs müssen im Wesentlichen segmentierbar sein in dem Sinne, dass ihre Bounding-Boxen nicht signifikant überlappen dürfen. Das formale 2D-Bildmodell ist als eine stochastische 2D- Grammatik mit Erzeugungsregeln dargestellt, die räumliche Beziehungen zwischen Objekten in dem Bild gemäß dieses rechteckigen Bildmodells definieren; die Grammatik wird zum Parsing (zur lexikalischen Analyse) der Objektliste verwendet, um den einen der möglichen Parsingbäume zu bestimmen, der dis größte Auftrittswahrscheinlichkeit hat. Der Trainingsprozess ist unbeaufsichtigt, wobei der Erkennungsprozess die zum Training zu verwendenden Bildproben aus dem originalen Eingabebild isoliert und Zeichenlabel den segmentierten Bildproben auf der Grundlage ihrer Klassifizierung durch die Erkennung zuweist. Da das Schablonenmodell im Zusammenhang der in dieser Diskussion verwendeten Terminologie ein segmentierungsbasiertes Modell ist, beschreibt das 2D-Bildmodell einen Satz möglicher Bilder, die jeweils im Wesentlichen segmentierbare Bildobjekte enthalten müssen, von denen jedes im Wesentlichen in einer nichtüberlappenden Bounding-Box enthalten sein können muss.

Die US-A-5,321,773 offenbart ein formales 2D-Bildmodell, das als ein stochastisches Finitzustandsübergangsnetzwerk dargestellt ist, das eine Bilderzeugung in Ausdrücken einer regulären Grammatik definiert, im Gegensatz zu der kontextfreien Grammatik, die in der US-A-5,020,112 verwendet wird. Das Schablonenmodell, das durch das 2D- Bildmodell beschrieben wird, definiert das Sidebearing-Modell der Buchstabenformumrissbeschreibung und -positionierung, die genauer bei der Diskussion zur Fig. 1 beschrieben wird.

Das in der US-A-5,321,773 verwendete Training der Zeichenschablonen enthält eine Abschätzung oder Berechnung spezifischer typografischer Charakteristiken oder Parameter, die für die richtige Schablonenpositionierung erforderlich sind; diese sind als Zeichen-Sidebearing und Grundlinientiefen bekannt, die zusammen Fontmetriken genannt werden. Der Umriss eines Glyphs ist in Ausdrücken eines lokalen Koordinatensystems definiert, das so ausgerichtet ist, dass der typografische Ursprung des Glyphs bei (0,0) liegt, was in Fig. 1 durch Kreuze 2, 5 und 6 gezeigt ist. Die "Zeichensatzbreite" eines Glyphs ist in Ausdrücken von Glyphursprungspositionen definiert und ist die Vektorverschiebung Δ = (Δx, Dy) von der Glyphursprungsposition eines ersten Glyphs zu dem Punkt, an dem der Ursprung eines zweiten benachbarten Glyphs normalerweise liegt, wenn aufeinanderfolgende Zeichen bildlich bearbeitet werden. In den meisten indogermanischen Alphabeten einschließlich des lateinischen sind Δx > 0 und Δy = 0. In Fig. 1 ist die Zeichensatzbreite des Buchstabens "e" durch die Verschiebung Δx bezeichnet. In anderen Schreibsystemen kann Δx jedoch negativ (z. B. im hebräischen) oder Δy von null verschieden sein (z. B. orientalische Glyphs). Wenn Δy = αΔx für irgendein α beträgt, sind die Glyphursprünge in einer Textzeile kolinear und definieren die Grundlinie 4 der Textzeile. Die Bounding-Box 3 eines Glyphs ist das kleinste Rechteck, das an den Zeichenkoordinatenachsen orientiert ist und den Glyph gerade einschließt. Es kann aus Fig. 1 ersehen werden, dass die Ursprungsposition eines typografischen Glyphbildes nicht notwendigerweise mit einer x,y-Position der Bounding-Box zusammenfällt; Fig. 1 zeigt die Ursprungsposition 5 des Glyphbildes für den Glyph "e" außerhalb der Bounding-Box 3 und die Ursprungsposition 6 des Glyphbildes für den Glyph "j" innerhalb der Bounding-Box 8. Das linke Sidebearing ist die horizontale Verschiebung λ vom Ursprung des Glyphs zum linken Rand der Bounding-Box. Entsprechend ist das rechte Sidebearing die horizontale Verschiebung p vom rechten Rand der Bounding-Box zum Ursprung des nächsten Glyphs. Einer oder beide Sidebearings können negativ sein.

Die US-A-5,321,773 offenbart das Trainieren von Zeichenschablonen in den Spalten 11 bis 17, und der Trainingsprozess ist weiterhin in G. Kopec, "Least-Squares Font Metric Estimation from Images", IEEE Transactions on Image Processing, Oktober 1993, Seiten 510-519 (im Folgenden "Kopec, Font Metric Estimation" genannt) beschrieben. Die offenbarte beaufsichtigte Trainingstechnik verwendete ein speziell vorbereitetes Eingabebild, das in Fig. 14 des Patents und in Fig. 3 von Kopec, Font Metric Estimation gezeigt ist, in dem die Glyphproben segmentierbar waren. Die Proben waren einem Vortrainingssegmentierungsschritt unterworfen, der auf Seite 516 in Kopec, Font Metric Estimation beschrieben ist, bei dem die Textzeilen und einzelnen Zeichen innerhalb jeder Zeile einer Fontprobenseite unter Verwendung einfacher verbundener komponentenbasierter Analyseprozeduren eines Textbildeditors extrahiert wurden. Jede Glyphprobe, die vom Textbildeditor isoliert wurde, wurde unter Verwendung einer manuell vorbereiteten Texttranskription der Probeseite, die geordnete Zeichenlabel enthielt, die die Proben identifizierten, mit Labeln versehen, paarweise auf einer Basis eins-zu-eins mit den Glyphproben in dem Eingabebild.

Die beaufsichtigte Trainingstechnik, die in US-A-5,321,773 und in Kopec, Font Metric Estimation offenbart ist, ist eine manuell intensive Prozedur. Sie erfordert, dass Glyphproben in der Bildquelle, in der sie auftreten, segmentierbar sind, während es das Schablonenmodell der Schablonen, die trainiert werden, erfordert, dass ein Paar benachbart positionierter Zeichenbilder der Schablonen nur im Wesentlichen disjunkte Grundlagen aufweisen muss. Es würde dann scheinen, dass einige Dokumentenbilder mit Zeichenbildern, gemäß des Sidebearing-Modells positioniert sind, ihrerseits nicht als Quellen von Glyphproben zum Training verwendet werden können, und Glyphproben zum Training müssten speziell vorbereitet werden. Ohne Glyphbildursprungspositionsdaten können die Fontmetriken unter Verwendung dieser Prozedur nur geschätzt werden, weil aus den Trainingsdaten Informationen, die x,y-Koordinatenglyphbildursprungspositionen der Probeglyphs, nicht direkt verfügbar sind, mit denen sie genauer gemessen werden könnten.

Es ist die Aufgabe der Erfindung, ein verbessertes Verfahren und eine Maschine zum Training eines Satzes von Zeichenschablonen bereitzustellen.

Diese Aufgabe wird durch die Gegenstände der unabhängigen Ansprüche 1, 4 und 8 gelöst.

Bevorzugte Ausgestaltungen sind in den abhängigen Ansprüchen definiert.

Die vorliegende Erfindung basiert auf der Prämisse, dass ein fontspezifisches Erkennungssystem beständig eine höhere Erkennungsgenauigkeit liefert als ein Polyfont-Erkennungssystem für Dokumente, die Zeichenbilder enthalten, die vorherrschend in einem spezifischen Font vorliegen. Um eine maximale Allgemeingültigkeit zu erhalten, versuchen Polyfont-Erkennungssysteme, die auch "Omni-Font"-Systeme genannt werden, typischerweise, die Erkennung unter Verwendung merkmalsbasierter Schablonen ohne besondere Sensitivität auf spezifische Schriftbilder, Fonts oder deren Schriftstilvariationen durchzuführen. Jedoch kann eine Font-Insensitivität die Genauigkeit reduzieren, wenn sie ein Erkennungssystem davon abhält, sich einem Text anzupassen, der vorherrschend oder vollständig in einem einzelnen Font vorliegt, und die Erkennungsgenauigkeit eines einzelnen Erkennungssystems kann in weitem Umfang für verschiedene Dokumente variieren, die jeweils einen verschiedenen Font haben, oder für ein einzelnes Dokument mit mehreren Fonts. Trotz ihres im Allgemeinen höheren Genauigkeitsgrades sind fontspezifische Erkennungssysteme jedoch als von begrenzter Brauchbarkeit und Allgemeinheit erkannt worden, hauptsächlich weil solche Systeme nicht leicht auf neue Fonts generalisierbar waren, was eine Konsequenz der Notwendigkeit des Trainings der Schablonen in jedem neuen Font und dann wieder der Notwendigkeit der beträchtlichen Benutzereinbeziehung bei der Vorbereitung der Trainingsarten für den Schablonentrainingsprozess war; die höhere Genauigkeit solcher Systeme wurde als von der verminderten Produktivität bei ihrer Benutzung aufgewogen wahrgenommen, wenn ein neuer Schablonensatz trainiert werden musste.

Die vorliegende Erfindung basiert auf der weiteren Prämisse, dass fontspezifische Erkennungssysteme eine lebensfähige Alternative zu Omni-Font-Erkennungssystemen sein könnten, wenn Schablonentrainingsverfahren und -systeme existieren würden, die Schablonen für spezifische Fonts genau trainieren könnten, während sie die Benutzerintervention oder -einbeziehung in den Schablonentrainingsprozess minimieren, ohne die Benutzerkontrolle über die Qualität und Genauigkeit der Trainingsdaten zu opfern.

Die vorliegende Erfindung minimiert die Einbeziehung des Benutzers in allen drei Aspekten der Vorbereitung von Trainingsdaten durch die Verwendung eines zweidimensionalen (2D-) Bildes eines Textdokuments als eine Quelle der Glyphproben, die zum Training verwendet werden sollen; durch die Verwendung einer unbeschränkten Form einer Transkription als eine Informationsquelle über das Versehen der Glyphproben mit Labeln; und durch die Verwendung eines formalen 2D-Bildmodells, das die Beziehung zwischen den Glyphproben in dem 2D-Bild definiert, als eine explizite Eingabe in den Trainingsprozess und der Informationen in der Transkription, so dass im Wesentlichen richtige Zeichenfabel den geeigneten Glyphproben zugewiesen werden. Tatsächlich kann die Trainingstechnik auf eine Weise implementiert werden, die im Wesentlichen jegliche Benutzereinbeziehung in die Trainingsdatenvorbereitung abgesehen von der Bereitstellung der 2D-Bildquelle der Glyphs und einer Transkription, die dem 2D-Bild zugeordnet ist, beseitigt, was effektiv dazu führt, dass die Schablonen automatisch erzeugt werden.

Die Verwendung eines formalen 2D-Bildmodells als eine explizite Eingabe in den Trainingsprozess sorgt für die Gelegenheit, Bilder existierender Textdokumente als eine Quelle von Glyphproben für das Schablonentraining zu verwenden und so die Notwendigkeit für einen Benutzer zu beseitigen, manuell ein spezifisches Bild von Proben zu entwerfen und vorzubereiten. Das formale 2D-Bildmodell stellt A-priori- Informationen über den Satz möglicher 2D-Eingabebilder dar, die als eine Eingabe in den Trainingsprozess akzeptiert werden. Ein wichtiger Gewinn bei der Verwendung eines expliziten formalen 2D-Bildmodells ist es, dass es für Flexibilität und Detailhaftigkeit bei der Beschreibung des Satzes möglicher 2D-Eingabebilder sorgt, aus denen Glyphproben zum Training erhalten werden, was andererseits bedeutet, dass eine breite Vielfalt existierender Textdokumentbilder zum Training verwendet werden können. Beispielsweise kann das Modell Beschreibungen von Nichtglyph-Abschnitten des Eingabebildes enthalten, die keine Glyphproben enthalten und folglich nicht am Trainingsprozess teilnehmen, wobei somit die Verwendung von Textdokument- Eingabebildern mit grafischen oder fotografischen Bildern gestattet wird oder von Bildteilen eines konstanten Inhalts, wie er etwa in Formularen zu finden ist. Ein signifikanter und einzigartiger Vorteil der Trainingstechnik der vorliegenden Erfindung gemessen an bestehenden Trainingstechniken ist, dass die Verwendung eines Textdokumentbilds als Quelle von Glyphproben zum Training die Notwendigkeit vorheriger Segmentierung oder Isolierung von Glyphproben oder Textzeilen in dem 2D- Eingabebild beseitigt. Der Trainingsprozess verwendet die von dem 2D-Bildmodell bereitgestellten Informationen, um die Positionen von Glyphproben in dem eingegebenen 2D-Bild zu lokalisieren, wodurch die Benutzereinbeziehung in die Trainingsdatenvorbereitung in beaufsichtigten Trainingssystemen reduziert wird, wo eine Glyphprobensegmentierung normalerweise manuell durch einen Benutzer aus einem Dokumentenbild durchgeführt wird.

Bei der Trainingstechnik der vorliegenden Erfindung bestimmt das formale 2D- Bildmodell, und insbesondere das Zeichenschablonenmodell für die im Training befindlichen Schablonen, ob die Textdokument-Bildquelle der Glyphproben segmentierbare Glyphproben enthalten muss. Wenn das formale 2D-Bildmodell das Schablonenmodell als ein segmentierungsbasiertes Modell beschreibt, beschreibt das 2D-Bildmodell eines Satz möglicher 2D-Eingabebilder, in denen die Glyphproben segmentierbar sind und bei denen Bounding-Boxen für die Glyphproben nicht überlappen dürfen. Wenn das formale 2D-Bildmodell das Schablonenmodell als nichtsegmentierungsbasiertes Modell wie etwa das oben beschriebene Sidebearing- Modell beschreibt, kann das 2D-Bildmodell einen Satz möglicher 2D-Eingabebilder beschreiben, in denen die Glyphproben nicht segmentierbar sein müssen und in denen Bounding-Boxen für die Glyphproben einander überlappen dürfen, wodurch weiterhin die Klasse existierender Textdokumentenbilder, die als mögliche Quellen der Glyphproben verwendet werden können, erweitert wird.

Ein weiterer Gewinn bei der Verwendung eines formalen 2D-Bildmodells, das explizit als eine Eingabe in die Trainingsprozedur definiert ist, liegt darin, dass der Typ (z. B. das strukturelle Erscheinungsbild) von Textdokumentenbildern, die als die Quelle von Glyphproben zum Training verwendet werden können, durch einfache Änderung des formalen 2D-Bildmodells geändert werden kann, um Informationen über einen neuen Bildtyp wiederzugeben; es gibt keine Notwendigkeit, die Anweisungen (Befehle) neu zu schreiben, die den Trainingsprozess ausführen, wenn der Typ des Eingabebildes wechselt. Die vorliegende Erfindung platziert die detaillierten Informationen über die eingegebene 2D-Bildquelle von Glyphproben in eine Eingabedatenstruktur, die in einer besonderen Implementierung für einen Benutzer zugreifbar gemacht werden kann.

Die Verwendung einer Transkription in einer flexibel definierten und unbeschränkten Form als eine Eingabe in den Trainingsprozess sorgt für die Gelegenheit für den Benutzer, eine explizite Kontrolle über das Versehen der Glyphproben, die beim Schablonentraining verwendet werden, mit Labeln auszuüben, ohne dass der Benutzer explizit eine spezifische Transkription vorbereiten oder explizit Zeichenlabel spezifischen Glyphproben zuweisen muss. Die Trainingstechnik kann auf eine solche Weise implementiert werden, dass es dem Benutzer gestattet ist, eine wörtliche Transkription vorzubereiten, die zu korrekten Zeichenlabeln führt, die spezifischen Glyphproben zugewiesen sind, jedoch kann die Technik auf eine viel allgemeinere Weise implementiert werden, so dass es dem Benutzer gestattet wird, eine geeignete Transkription lediglich auszuwählen, die die von dem formalen 2D-Bildmodell benötigten Informationen enthält, um Zeichenlabel auf Glyphproben abzubilden.

Ein anderer wichtiger Vorteil der Trainingstechnik der vorliegenden Erfindung gegenüber existierenden Trainingstechniken besteht darin, dass die vorliegende Erfindung für die Verwendung eines größeren Bereichs von Transkriptionstypen zu Trainingszwecken sorgt als die Eins-zu-eins-Abfolge von Zeichenlabeln, die in konventionellen beaufsichtigten Trainingssystemen verwendet wird. In ihrer einfachsten Form kann die Transkription ein String von Transkriptionslabeln sein, die jeweils ein Zeichenlabel angeben und von denen jedes jeweils mit einer Glyphprobe in dem 2D-Eingabebild in einer Eins-zu-eins-Paarung gepaart ist. Die Transkription kann auch Markup- Informationen, bekannt als Tags, enthalten, die strukturelle Teile des Dokuments für eine Dokumentenverarbeitung, Formatierung oder Textverarbeitungsanwendung identifizieren; auf diesen Transkriptionstyp wird im Folgenden als "Tag-Transkription" Bezug genommen.

Somit wird gemäß der vorliegenden Erfindung ein Verfahren zum Betreiben einer Maschine zum Trainieren einer Vielzahl von Zeichenschablonen bereitgestellt. Die von dem Verfahren betriebene Maschine enthält eine Speichereinrichtung zum Speichern von Daten einschließlich Anweisungsdaten und einen Prozessor, der zum Zugreifen auf in dem Speicher gespeicherte Daten und zum Ausführen der Anweisungen verbunden ist, um die Maschine zu betreiben. Das Verfahren verwendet als Eingabe eine Bilddefinitionsdatenstruktur, die eine zweidimensionale Bildquelle definiert, die eine Vielzahl von Glyphs enthält, auf die als 2D-Bildquelle von Glyphproben Bezug genommen wird, mit einer vertikalen Dimensionsgröße, die größer als eine einzelne horizontale Zeile ist. Jedes in der 2D-Bildquelle von Glyphproben enthaltene Glyph ist ein Bildbeispiel eines bestimmten Zeichens einer Vielzahl von Zeichen in einem Zeichensatz, auf den als ein Glyphprobenzeichensatz Bezug genommen wird. Jede Zeichenschablone der Vielzahl von Zeichenschablonen, die trainiert werden, stellt ein bestimmtes Zeichen der Vielzahl von Zeichen in dem Glyphprobenzeichensatz dar und wird durch ein Zeichenlabeldatenelement identifiziert, das das jeweilige Zeichen in dem Glyphprobenzeichensatz angibt. Das Verfahren verwendet auch als Eingabe eine zweidimensionale Bildquellenmodelldatenstruktur, auf die als ein 2D-Bildquelienmodell Bezug genommen wird, das als eine Grammatik die räumliche Bildstruktur eines Satzes von zweidimensionalen (2D-) Bildern modelliert. Die 2D-Bildquelle von Glyphproben ist ein Bild des Satzes von 2D-Bildern, die von dem 2D-Bildquellenmodell modelliert werden. Das 2D-Bildquellenmodell enthält räumliche Positionierungsdaten, die die räumliche Positionierung der Vielzahl von Glyphs modellieren, die in der 2D-Bildquelle von Glyphproben auftreten, und es enthält Abbildungsdaten (Mappingdaten), die ein bestimmtes Glyph, das in der 2D-Bildquelle von Glyphproben auftritt, auf das Glyphlabel abbilden, das das Zeichen in dem Glyphprobenzeichensatz angibt. Das Schablonentrainingsmodell verwendet weiterhin als Eingabe eine Transkriptionsdatenstruktur, auf die als eine Transkription Bezug genommen wird, die der 2D- Bildquelle von Glyphproben zugeordnet ist und eine geordnete Anordnung von Transkriptivnslabeldatenelementen enthält, auf die im Folgenden als Transkriptionslabel Bezug genommen wird. Das Verfahren umfasst das Betreiben des Prozessors, um wenigstens eine Glyphprobe zu bestimmen, die in der 2D-Bildquelle von Glyphproben auftritt, unter Verwendung der räumlichen Positionierungsdaten, die in dem 2D- Bildquellenmodell enthalten sind. Das Verfahren umfasst weiterhin das Betreiben des Prozessors, um ein Glyphlabeldatenelement zu erzeugen, auf das als ein Glyphlabel Bezug genommen wird, um mit der wenigstens einen Glyphprobe gepaart zu werden, die in der 2D-Bildquelle von Glyphproben auftritt, wobei das Glyphlabeldatenelement das jeweilige Zeichen in dem Glyphprobenzeichensatz angibt, das durch die gepaarte Glyphprobe repräsentiert wird; der Prozessor verwendet die Mappingdaten, die in dem 2D-Bildquellenmodell enthalten sind, und die Transkription, um das Glyphlabel mit der wenigstens einen Glyphprobe zu paaren. Das Verfahren enthält dann das Betreiben des Prozessors, um eine der Vielzahl von Zeichenschablonen zu erzeugen, das ein bestimmtes Zeichen in dem Glyphprobenzeichensatz angibt, unter Verwendung der wenigstens einen Glyphprobe, die in der 2D-Bildquelle von Glyphproben enthalten ist und von dem gepaarten Glyphlabel identifiziert wird, das zu dem Zeichenlabel der Bitmap-Zeichenschablone passt. Beispiele der mit Labeln versehenen Glyphproben, die von der vorliegenden Erfindung erzeugt worden sind, enthalten isolierte, mit Labeln versehene Zeichenbilder, Bounding-Boxen, die um die Glyphproben in Bildquellen herum spezifiziert und jeweils mit einem Zeichenlabel versehen sind, und 2D-Bereiche des Eingabebildes, die identifizierte Ursprungspositionen von Glyphproben aufweisen und jeweils mit einem Zeichenlabel versehen sind.

Gemäß einem anderen Aspekt der vorliegenden Erfindung wird eine Maschine zur Verwendung beim Training einer Vielzahl von Zeichenschablonen zur Verwendung in einem Erkennungsvorgang bereitgestellt, die eine erste Signalquelle zum Bereitstellen von Bilddefinitionsdaten umfasst, die ein erstes Bild definieren, eine Bildeingabeschaltung, die zum Empfangen der Bilddefinitionsdaten, die das erste Bild definieren, von der ersten Signalquelle verbunden ist, eine zweite Signalquelle zum Bereitstellen von Nichtbilddaten, eine Eingabeschaltung, die zum Empfangen der Nichtbilddaten von der zweiten Signalquelle verbunden ist, einen Prozessor, der zum Empfangen der Bilddefinitionsdaten, die das erste Bild definieren, von der Bildeingabeschaltung und zum Empfangen der Nichtbilddaten von der Eingabeschaltung verbunden ist, und einen Speicher zum Speichern von Daten. Die in dem Maschinenspeicher gespeicherten Daten enthalten Anweisungsdaten, die Anweisungen, die der Prozessor ausführen kann, angeben, und der Prozessor ist weiterhin zum Zugreifen auf die in dem Speicher gespeicherten Daten verbunden. Der Prozessor empfängt bei der Ausführung der im Speicher gespeicherten Anweisungen von der Bildeingabeschaltung eine Bilddefinitionsdatenstruktur, die die 2D-Bildquelle von Glyphproben, die vorher beschrieben worden ist, definiert, und er empfängt von der Eingabeschaltung die Transkriptionsdatenstruktur, die zuvor beschrieben worden ist. Der Prozessor empfängt von der Eingabeschaltung weiterhin bei der Ausführung der Anweisungen eine zweidimensionale Bildquellenmodelldatenstruktur, auf die als ein 2D- Bildquellenmodell Bezug genommen wird, das zuvor beschrieben worden ist. Der Prozessor führt weiterhin bei der Ausführung der Anweisungen Vorgänge aus, die die zuvor beschriebenen Verfahrensschritte zum Bestimmen der Vielzahl von Glyphproben, die in der 2D-Bildquelle von Glyphproben auftreten, und zum Erzeugen des Glyphlabeldatenelements ausführen, das mit jeder der Vielzahl von Glyphproben gepaart wird, die ein bestimmtes Zeichen der Zeichen in dem Glyphprobenzeichensatz angibt. Der Prozessor erzeugt dann weiterhin bei der Ausführung der Anweisungen die Vielzahl von Zeichenschablonen unter Verwendung der mit den jeweiligen Glyphlabeln gepaarten Glyphproben, wie zuvor beschrieben.

Ein wichtiger Vorteil der Trainingstechnik der vorliegenden Erfindung ist ihre spezifische Anwendung auf das Training von Zeichenschablonen, die durch ein Schablonenmodell definiert sind, wie etwa durch das Sidebearingmodell der Buchstabenformumrissbeschreibung und -positionierung, das die Identifizierung der Ursprungspositionen der Zeichenbilder zusätzlich zu oder anstelle von der Identifizierung der Bounding-Boxen der Zeichenbilder erfordert. Trainingszeichenschablonen auf der Basis des Sidebearingzeichenschablonenmodells können effektiv fertiggestellt werden bei Kenntnis nur der Bildursprungspositionen der Glyphproben, die in dem 2D-Bild auftreten, und brauchen auch nicht von der Bestimmung einer Bounding-Box um die Glyphprobe abzuhängen, um die Pixel zu identifizieren, die in einer bestimmten Zeichenschablone enthalten sein sollen. Eine Implementierung der Trainingstechnik der vorliegenden Erfindung ist folglich ein Zweistufenprozess. Die erste Stufe verwendet das formale 2D-Bildmodell und die Transkription, um die Bildursprungspositionen von Glyphproben in dem 2D-Eingabebild zu identifizieren und den Glyphprobenursprungspositionen Zeichenlabel zuzuweisen. Diese Implementierung bestimmt die Bildursprungspositionen der Glyphproben ohne jegliche Information vor dem Training darüber, wo die Glyphproben in dem 2D-Eingabebild auftreten.

In der zweiten Stufe dieser Implementierung werden die mit Labeln versehenen Glyphursprungspositionen, die die Ausgabe der ersten Stufen darstellen, dann in einen neuartigen Schablonenkonstruktionsprozess eingegeben, der die trainierten Schablonen erzeugt. In bestehenden Trainingssystemen, die binären Zeichenschablonen trainieren, ermöglicht die Segmentierung der Glyphproben mittels der Verwendung von Bounding- Boxen eine relativ geradlinige Bestimmung der Zeichenschablone aus vielfachen isolierten Proben des Zeichens, typischerweise unter Verwendung eines wohlbekannten Prozesses der Pixelmittelwertbildung. Bei der Trainingstechnik der vorliegenden Erfindung werden nur Glyphursprungspositionen der Glyphproben bestimmt und eine Segmentierung von Glyphproben in dem 2D-Eingabebild durch die Bestimmung von Bounding-Boxen um sie herum braucht nicht durchgeführt zu werden. Folglich können bestehende Bitmapmittelwertbildungstechniken, die von der Kenntnis von Glyphprobenrändern abhängen, nicht verwendet werden. Die Technik der vorliegenden Erfindung erzeugt eine binäre Zeichenschablone aus Informationen über nur die Bildursprungspositionen der Glyphproben unter Verwendung einer neuartigen Schablonenkonstruktionstechnik, die im Wesentlichen das funktionale Ergebnis der Glyphsegmentierung mit einer tatsächlichen Konstruktion der Bitmapschablonen kombiniert. Bei dieser Technik wird ein Feld (Array) von Schablonenpixelpositionen, als Schablonenbildbereich bezeichnet, mit vertikalen und horizontalen Dimensionen, die zum Speichern einer binären Zeichenschablone geeignet sind, für jede zu trainierende Zeichenschablone erzeugt und zur Bestimmung von Probenbildbereichen, die jeweils eine der Glyphproben für die jeweilige Zeichenschablone enthalten, in dem 2D- Eingabebild für jede Zeichenschablone verwendet. Ein Schablonenbildbereich enthält eine Schablonenpixelposition, die als die Schablonenursprungsposition bezeichnet wird, und es wird ein Probenbildbereich in dem 2D-Eingabebild, der eine Glyphprobe enthält, bezogen auf das lokale Koordinatensystem des Schablonenbildbereichs so bestimmt, dass die Bildursprungsposition einer Glyphprobe dieselbe relative Pixelposition in dem Probenbildbereich hat wie die Pixelposition der Schablonenursprungsposition in dem Schablonenbildbereich. Alle Probenbildbereiche, die jeweils dasselbe Zeichen der Zeichen in dem Glyphprobenzeichensatz angeben, werden als Kollektion von Probenbildbereichen bezeichnet, und jeder Probenbildbereich in der Kollektion wird auf alle anderen und auf die Schablone für dieses Zeichen an der Bildursprungsposition ausgerichtet. Die binären Zeichenschablonen werden dann im Wesentlichen gleichzeitig aus den Kollektionen der ausgerichteten Probenbildbereiche für jede Zeichenschablone dadurch erzeugt, dass Vordergrundpixelfarbwerte den Schablonenpixelpositionen in ausgewählten Schablonenbildbereichen zugewiesen werden, die auf der Grundlage von Schablonenbeitragsmaßen ausgewählt werden, die unter Verwendung von jeweils gepaarten ausgerichteten Probenpixelpositionen berechnet worden sind, die in Probenbildbereichen enthalten sind.

Es gibt mehrere Gewinne und Vorteile, die aus der Trainingstechnik der vorliegenden Erfindung resultieren, angewendet auf das Training von Zeichenschablonen, die durch ein Zeichenschablonenmodell beschrieben werden, das Zeichenbildursprungspositionen für die Zeichenpositionierung verwendet. Das explizite formale 2D-Bildmodell, das die Apriori-Informationen über die 2D-Eingabebildquelle von Glyphs bereitstellt, minimiert die Beeinträchtigung durch Rauschen in dem Eingabebild bei dem Prozess des Lokalisierens der Glyphbildursprungspositionen der Glyphproben. Darüber hinaus beseitigt die Eliminierung eines Segmentierungsschritts vor der Schablonenkonstruktion Segmentierungsfehler, die eingeführt werden, wenn Segmentierung auf einem verrauschten Bild durchgeführt wird, und sie erlaubt so die Verwendung von Bildern bestehender Textdokumente wechselnder Qualität als Quellen von Glyphproben. Der neuartige Schablonenkonstruktionsprozess behandelt erfolgreich verschmierte, gebrochene und verschmolzene Glyphproben, die in verrauschten Bildern auftreten, oder verschmolzene Glyphproben, die natürlicherweise in einem Font auftreten, in dem Zeichenbilder so entworfen worden sind, dass sie verbunden sind. Da der Schablonenkonstruktionsprozess viele Glyphproben verwendet, die in dem Text des 2D- Eingabebildes auftreten, und da er die Schablonen im Wesentlichen gleichzeitig erzeugt, beeinflussen überschüssige oder fehlende dunkle Pixel, die in einer oder zwei verschmierten, gebrochenen oder verschmolzenen Proben als Ergebnis von Rauschen in dem Bild auftreten, mit geringerer Wahrscheinlichkeit die Qualität der Zeichenschablonen, die trainiert werden, wenn diese niederqualitativen Proben mit anderen rauschfreien und hochqualitativen Proben verarbeitet werden. Da darüber hinaus dieses neuartige Schablonenkonstruktionsverfahren nicht erfordert, dass eine wirkliche Bounding-Box für jede Glyphprobe gefunden wird, kann ein potentiell größerer Bereich von Symbolsätzen, Alphabeten und Zeichenfonts von der Trainingstechnik der vorliegenden Erfindung fertiggestellt werden, die sich nicht leicht für eine Segmentierung eignen, was dann wieder die Verwendung einer breiten Vielzahl von Bildern bestehender Textdokumente als Quellen von Glyphproben erlaubt.

Bei einer Implementierung der Trainingstechnik der vorliegenden Erfindung wird das formale 2D-Bildmodell, das die Struktur eines Satzes möglicher Bilder beschreibt, die als die Quelle von Glyphproben für das Training dienen können, als eine Markov-Quelle dargestellt, die die Form eines Finitzustandsübergangsnetzwerkes aufweist, das eine Reihe von Knoten und Übergängen zwischen Knotenpaaren enthält. Jedem Übergang in dem Netzwerk sind Übergangsdatenelemente zugeordnet, die eine Zeichenschablone, einen Nachrichtenstring, eine Übergangswahrscheinlichkeit und eine Vektorverschiebung enthalten. Ein Satz von Transkriptionen, aus denen Informationen über die den Glyphproben zuzuweisenden Zeichenlabel abgeleitet werden können, wird auch als ein Finitzustandsübergangsnetzwerk dargestellt, in dem jeder Übergang einem möglichen Transkriptionslabel für die alternativen Transkriptionen entspricht. Ein oder mehrere Transkriptionslabel stehen in Bezug mit dem/den Nachrichtenstring(s), die dem Übergang/den Übergängen in dem formalen 2D-Bildmodell zugeordnet sind, so dass das formale 2D-Bildmodell zusammen mit dem eingegebenen Satz von Transkriptionen einen relativ kleinen Satz möglicher Eingabebilder beschreibt. Die Trainingstechnik verwendet das formale 2D-Bildmodell, und den Satz von Transkriptionen zu finden, die den besten Pfad durch das 2D-Bildmodell zeigen, wie durch den Satz von Transkriptionen erzwungen. Die Bildursprungsposition jeder Glyphprobe zusammen mit einem jeweiligen Zeichenlabel für diese Probe wird aus der Abfolge von Übergängen, die den besten Pfad bilden, identifiziert, und diese mit Labeln versehenen Glyphbildursprungspositionsdaten werden dann als Eingabe in den neuartigen Schablonenkonstruktionsprozess verwendet, der oben beschrieben worden ist.

Die vorliegende Erfindung wird an Beispielen unter Bezugnahme auf die beigefügten Zeichnungen weiter beschrieben werden, in denen:

Fig. 1 eine vereinfachte Version des Sidebearingmodells der Buchstabenformumrissbeschreibung und -positionierung verdeutlicht;

Fig. 2 ein 2D-Bild einer Vielzahl von Glyphs zur Verwendung als Quelle von Glyphproben zum Training von Zeichenschablonen gemäß der vorliegenden Erfindung verdeutlicht;

Fig. 3 ein Beispiel einer Zeichenschablonendatenstruktur verdeutlicht, die von der vorliegenden Erfindung erzeugt worden ist;

Fig. 4 ein Beispiel einer Transkriptionsdatenstruktur für das 2D-Bild der Fig. 2 verdeutlich, das geeignet zur Verwendung als Eingabe in die Trainingstechnik und das System der vorliegenden Erfindung ist;

Fig. 5 ein anderes Beispiel einer Transkriptionsdatenstruktur für einen Ausschnitt eines Wörterbuchs verdeutlicht, die geeignet zur Verwendung als eingegebene Transkription in die Trainingstechnik der vorliegenden Erfindung ist;

Fig. 6 das 2D-Bild der Wörterbuchseite zeigt, für die Fig. 6 die Transkription ist;

Fig. 7 einen Satz von Transkripitonsdatenstrukturen verdeutlicht, die alternative Transkriptionsnachrichten für das 2D-Bild von Fig. 2 darstellen;

Fig. 8 den in Fig. 7 gezeigten Satz von Transkriptionen verdeutlicht, dargestellt als ein Teil eines vereinfachten Finitzustandsübergangsnetzwerks;

Fig. 9 ein formales 2D-Bildquellenmodell verdeutlicht, das in seiner allgemeinen Form als ein vereinfachtes Finitzustandsübergangsnetzwerk dargestellt ist;

Fig. 10 ein vereinfachtes Blockdiagramm ist, das die eingegebenen und ausgegebenen Datenstrukturen der Trainingstechnik und des Systems der vorliegenden Erfindung verdeutlicht;

Fig. 11 ein Flussdiagramm ist, das die allgemeinen Schritte der Zeichenschablonentrainingstechnik der vorliegenden Erfindung verdeutlicht;

Fig. 12 ein vereinfachtes Blockdiagramm ist, das die eingegebenen und ausgegebenen Datenstrukturen eines Teiles einer verdeutlichten Softwareimplementierung der Trainingstechnik und des Systems der vorliegenden Erfindung verdeutlicht, der die Trainingsdaten, die der Schablonenkonstruktion eingegeben werden, erzeugt;

Fig. 13 ein Flussdiagramm ist, das die allgemeinen Schritte des Teils der verdeutlichten Implementierung der vorliegenden Erfindung verdeutlicht, der mit Labeln versehene Glyphbildursprungspositionen als Trainingsdaten erzeugt;

Fig. 14 ein Diagramm ist, das ein Finitzustandsübergangsnetzwerk verdeutlicht, das eine Klasse von 2D-Bildern mit einer räumlichen Struktur einer einzelnen Textspalte modelliert, wie etwa das 2D-Bild von Fig. 2, und das in der verdeutlichten Implementierung der Zeichenschablonentrainingstechnik der vorliegenden Erfindung verwendet wird;

Fig. 15 ein Diagramm ist, das einen vereinfachten Teil des Transkriptionsnetzwerks von Fig. 8 verdeutlicht, das in der verdeutlichten Implementierung der Zeichenschablonentrainingstechnik der vorliegenden Erfindung verwendet wird;

Fig. 16, 17, 18 und 19 schematisch das Verschmelzen des Finitzustandsübergangsnetzwerks von Fig. 14 mit dem Transkriptionsnetzwerks von Fig. 15 gemäß der verdeutlichten Implementierung der vorliegenden Erfindung verdeutlicht;

Fig. 20 ein Flussdiagramm ist, das den Dekodierungsschritt in dem Flussdiagramm von Fig. 13 als Viterbi-Dekoder gemäß der verdeutlichten Implementierung der vorliegenden Erfindung verdeutlich;

Fig. 21 die allgemeinen Schritte der Schablonenkonstruktionstechnik verdeutlicht, die in der verdeutlichten Implementierung der vorliegenden Erfindung verwendet wird;

Fig. 22 das Konzept eines Schablonenbildbereichs verdeutlicht, der zur Speicherung einer trainierten Schablone während der Schablonenkonstruktionstechnik verwendet wird, die in Fig. 21 verdeutlicht ist;

Fig. 23 die Probenbildbereiche verdeutlicht, die in der 2D-Bildquelle von Glyphproben identifiziert sind, mit denen die Schablonen gemäß der Schablonenkonstruktionstechnik trainiert werden, die in Fig. 21 verdeutlicht ist;

Fig. 24 ein schematisches Bild dreier Probenbildbereiche des 2D-Bildes von Fig. 2 ist, die über den Schablonenbildbereich von Fig. 22 gelegt sind, wodurch das Konzept der an Bildursprungspositionen der Glyphproben ausgerichteten Probenbildbereiche gemäß der verdeutlichten Implementierung der vorliegenden Erfindung verdeutlicht wird;

Fig. 25 ein Bild einer Kollektion von Probenbildbereichen zeigt, die aus dem 2D- Eingabebild zur Verwendung beim Training einer Schablone gemäß der verdeutlichten Implementierung der vorliegenden Erfindung ausgeschnitten worden sind;

Fig. 26 drei beispielhafte, jedoch unzufriedenstellende Schablonen zeigt, die unter Verwendung einer Technik erzeugt worden sind, die eine wichtige mathematische Beschränkung nicht beachtet, die Zeichenschablonen auferlegt ist;

Fig. 27 ein Flussdiagramm ist, das die Schritte zur gleichzeitigen Konstruktion aller Zeichenschablonen unter Verwendung von Schablonenbildbereichen der Fig. 22 und von ausgerichteten Probenbildbereichen von Fig. 24 und Fig. 25 gemäß der Schablonenkonstruktionstechnik der verdeutlichten Implementierung der vorliegenden Erfindung verdeutlicht;

Fig. 28 einen fertigen Satz trainierter Schablonen zeigt, die gemäß der neuartigen Schablonenkonstruktionstechnik erzeugt worden sind, die in Fig. 27 verdeutlicht worden ist;

Fig. 29 ein Diagramm ist, das ein Finitzustandsübergangsnetzwerk verdeutlicht, das einen Satz von Zeilenbildern mit einer räumlichen Struktur einer einzelnen Textzeile modelliert und Nachrichtenstrings, die zu einer beispielhaften Tag- Transkription konsistent sind, anpasst; und

Fig. 30 probenmäßige Zeilenbilder verdeutlicht, die von dem Finitzustandsübergangsnetzwerk von Fig. 29 modelliert worden sind.

Der Ausdruck "Daten" oder "Datenelement" bezieht sich vorliegend auf physikalische Signale, die Informationen angeben oder enthalten. Ein erstes Datenelement "gibt" ein zweites Datenelement "an", wenn das zweite Datenelement aus dem ersten Datenelement erlangt werden kann, wenn das zweite Datenelement unter Verwendung des ersten Datenelements zugreifbar sein kann, wenn das zweite Datenelement durch Dekodierung des ersten Datenelements erlangt werden kann oder wenn das erste Datenelement eine Identifizierung des zweiten Datenelements sein kann. Beispielsweise zeigt der gerichtete Pfeil 36 in Fig. 3, dass das Zeichenlabeldatenelement 28 in der Zeichenschablonendatenstruktur 20 die Zeichenschablone 22 angibt, die ein Bild des Zeichens "a" darstellt. Ein Datenelement "identifiziert" ein oder "ist eine Identifizierung von" einem Element eines Satzes von identifizierbaren Elementen, wenn das Datenelement ein Datenelement eines Satzes von Datenelementen ist, von denen jedes auf höchstens eines der identifizierbaren Elemente abgebildet werden kann.

Beispielsweise kann zu Fig. 3 gesagt werden, dass das Zeichenlabeldatenelement 28 die Zeichenschablone 22 identifiziert.

Auf Daten, die ein Bild definieren, kann als "Bilddefinitionsdaten" Bezug genommen werden. Beispielsweise kann ein zweidimensionales (2D-) Feld das gesamte oder irgendeinen Teil eines Bildes definieren, wobei jedes Datenelement in dem Feld einen Wert bereitstellt, der die Farbe eines bestimmten Ortes des Bildes angibt. Bei diesem Typ einer Bilddarstellung wird jeder solcher Bildort üblicherweise als "Bildelement" oder "Pixel" bezeichnet und stellt einen kleinen vereinheitlichten Bereich des Bildes dar. Typischerweise gibt in binären Schwarzweißbildern der Wert in einem Pixel Schwarz oder Weiß an, wobei Schwarz die Vordergrundfarbe ist und eine entsprechende Markierung oder aktive Position in dem Bild darstellen soll und Weiß die Hintergrundfarbe ist. Weil Schwarz die typische Farbe ist, die als Vordergrundpixelfarbe verwendet wird, wird in dieser Diskussion die Bezugnahme auf schwarze Pixel und Vordergrundpixel in austauschbarer Weise verwendet werden, falls nicht explizit anderweitig daraufhingewiesen wird. Auf ein Bild in einem prozessorgesteuerten System, das durch ein 2D-Feld von Datenelementen, die Pixel definieren, dargestellt wird, wird als "Bitmapbild" oder "Binärbild (binäres Bild)" Bezug genommen.

Der Begriff "Displaymerkmal" betrifft jede menschliche Wahrnehmung, die durch eine Displayeinrichtung erzeugt wird, und enthält ein einzelnes Displaymerkmal und kann auch mehrere Displaymerkmale enthalten, die zusammen ein Muster von Displaymerkmalen in einem Bild bilden. Ein "Displayobjekt" oder "Objekt" ist ein Displaymerkmal, das als kohärente Einheit wahrnehmbar ist. Ein Bild "enthält" ein Displaymerkmal oder ein Objekt, wenn die Darstellung des Bildes die Wahrnehmung des Merkmals oder Objekts erzeugen kann.

"Zeichen" in der vorliegenden Verwendung bedeutet ein einzelnes, diskretes und abstraktes Element oder Symbol. Beispielsweise kann ein Zeichen ein abstraktes Symbol enthalten, das in geschriebener oder gedruckter Form einer Sprache erscheint. Zeichen in einer Sprache können nicht nur alphabetische oder numerische Elemente sondern auch Satzzeichen, diakritische Zeichen, mathematische und logische Symbole, die in mathematischer Notation wie etwa in Gleichungen verwendet werden, und andere in geschriebener oder gedruckter Form der Sprache verwendete Elemente enthalten. Allgemeiner können Zeichen phonetische, ideografische oder piktografische Elemente zusätzlich zu alphanumerischen Elementen enthalten. Beispielsweise sind Symbole in piktografischen Sprachen und Symbole, die eine musikalische Notation darstellen, in dem Begriff des Zeichens enthalten. Alle Zeichen, die sich auf eine bestimmte Sprache oder auf eine andere Symbolnotation wie etwa auf Musik beziehen, umfassen einen "Zeichensatz".

Ein "Zeichenkode" ist ein Datenelement in einer prozessorgesteuerten Maschine oder einem System, das ein Zeichen (das abstrakte Symbol) für den Prozessor definiert oder repräsentiert. Die Kodierung eines Satzes von Zeichen wie etwa solchen, die zu einer Sprache gehören, beinhaltet die Definition eines Satzes von Zeichenkodes, der einen jeweiligen Zeichenkode für jedes Zeichen in dem Satz enthält. Ein Beispiel eines Satzes von Zeichenkodes ist der Satz von ASCII-Kodes für die Symbole, die die englische Sprache ausmachen.

Ein "Glyph" ist ein Einzelfall oder ein Beispiel eines Zeichens, das als ein Bild realisiert ist, beispielsweise auf einem Markierungsmedium wie etwa Papier oder auf einem Anzeigebildschirm. Da eine Vielzahl von Faktoren darauf Einfluss haben, wie ein Bild eines Zeichens erzeugt wird, wenn es gedruckt, gescannt, kopiert oder gefaxt wird, kann ein Glyph eines Zeichens in einem Textbild mit einem anderen Glyph desselben Zeichens in dem Textbild auch nichtidentisch sein.

Die Terminologie "Bilddefinitionsdaten, die eine eingegebene 2D-Bildquelle einer Vielzahl von Glyphs definieren" (im Folgenden als "2D-Bildquelle von Glyphproben", "2D-Bilddatenstruktur" oder einfach als "2D-Bild" benannt) betrifft eine Datenstruktur, die zur Speicherung in einer Speichereinrichtung einer prozessorgesteuerten Maschine geeignet ist und ein 2D-Bild definiert, in dem eine Vielzahl von Bitmapdarstellungen von Zeichen in dem 2D-Raum auftreten, der durch das Bild definiert ist. Die Organisation der 2D-Bilddatenstruktur ist solchermaßen, dass auf einzelne Pixelorte von dem Prozessor zugegriffen werden kann, dass aber die Pixel, die einen individuellen Glyph umfassen, nicht anfänglich als eine Dateneinheit identifiziert sind, die für den Prozessor zugreifbar ist, und dass für den Prozessor anfänglich keine Informationen darüber verfügbar sind, ob eine spezifische x,y-Koordinatenposition in dem 2D-Bild einen der in einem Glyph enthaltenen Pixel angibt. Die 2D-Bildquelle von Glyphproben ist die Eingabequelle von Glyphproben, die für das Training von Zeichenschablonen gemäß der vorliegenden Erfindung verwendet wird. Ein 2D-Bild ist konzeptionell analog zu einer Seite eines Dokuments und kann häufig ein Bild einer wirklichen physikalischen Seite darstellen, wobei Glyphs vertikal sowie horizontal in dem 2D-Raum verteilt sind. Das 2D-Bild ist nicht darauf beschränkt, nur Glyphs zu enthalten; andere Bildobjekte wie etwa grafische Objekte oder Umrisse, Bilder, Halbtonbilder, Linienzeichnungen, Fotografien, andere Bildelemente oder Bilder, die Rauschen ausmachen, können in der eingegebenen 2D- Bildquelle von Glyphs enthalten sein.

Fig. 2 verdeutlicht die 2D-Bilddatenstruktur 10, die Bitmapdarstellungen von Zeichen in dem Zeichensatz enthält, der die englische Sprache umfasst. In Fig. 2 ist jede diskrete Darstellung eines Zeichens der englischen Sprache in dem 2D-Bild 10 ein Glyph; die Glyphs 12 und 14 wurden vergrößert, um eine schematische Darstellung der einzelnen Pixel zu verdeutlichen, die ihre jeweiligen Bilder ausmachen. Das 2D-Bild 10 in Fig. 2 verdeutlicht einen Teil der Datenstruktur, der ein binäres Bild darstellt, das durch Abtastung (Scannen) eines Zeitungsartikels erzeugt worden ist und Pixel enthält, die ein Liniensegment 16, einen Nichtglyph, der in dem 2D-Bild enthalten ist, umfasst.

Eine "Schablone" oder "Zeichenschablone" ist eine Datenstruktur, die ein Bitmapbild eines Zeichens angibt. Die "Grundlage (Support)" einer Bitmap-Zeichenschablone ist der Satz von Pixelpositionen, an denen die Schablone vom Hintergrund verschieden ist. Ein "Zeichenlabel" ist ein Datenelement, das Informationen angibt, die eines der Zeichen in einem Zeichensatz in einheitlicher Weise identifizieren, wobei die jeweilige Zeichenschablone das Bitmapbild des Zeichens angibt. Ein Zeichenlabel kann einen Zeichenkode wie etwa eine ASCII-Kode angeben, um die Schablone zu identifizieren, oder es kann irgendwelche anderen Informationen angeben, die die Schablone als diejenige Schablone einheitlich identifizieren, die das Bitmapbild eines bestimmten Zeichens der Zeichen in einem Zeichensatz angibt, wie etwa fontidentifizierende Informationen, Größen- oder Schriftartstilinformationen. Ein "Satz von mit Labeln versehenen Zeichenschablonen" oder ein "Satz von Zeichenschablonen" ist eine Datenstruktur, die wenigstens eine Zeichenschablone und das jeweilige Zeichenlabel enthält, das die Zeichenschablone einheitlich identifiziert.

Fig. 3 verdeutlicht einen Satz 20 von mit Labeln versehenen Zeichenschablonen, die Zeichen in dem Zeichensatz der englischen Sprache darstellen. Die Zeichenschablonendatenstrukturen 22, 24 und 26 geben jeweils Zeichenlabeldatenelemente 28, 30 bzw. 32 an, wie beispielhaft durch den gerichteten Pfeil 34 von der Zeichenschablone 22 auf das Zeichenlabel 28 gezeigt. Identifizierungsinformationen in jedem der Zeichenlabeldatenelemente 28, 30 und 32 sind als ein Zeichen in Anführungszeichen gezeigt; diese Darstellung wird in den Figuren vorliegend verwendet, um einen bestimmten Zeichenkode anzugeben, der in dem Datenspeicher einer prozessorgesteuerten Maschine gespeichert ist, zur Unterscheidung von Pixeln, die ein Bild des Zeichens darstellen.

Die Verdeutlichung der Zeichenschablonen in Fig. 3 soll die Datenstruktur, die eine Zeichenschablone darstellt, nicht in irgendeiner Weise auf ein explizites 2D-Pixelfeld einschränken, das ein vollständiges Zeichen darstellt. Eine Schablone kann aus der Aneinanderfügung von Teilen von Bitmapzeichen konstruiert werden, wie etwa aus senkrechten Strichen, Verbindungen, Aufsteigern, Absteigern und Kurvenabschnitten.

Eine Schablone kann auch durch ein formales Modell dargestellt werden, das ein explizites 2D-Pixelfeld erzeugt, das als seine Ausgabe ein vollständiges Zeichen darstellt.

Eine "Transkriptionsdatenstruktur" oder "Transkription" in der vorliegenden Verwendung ist eine Datenstruktur, die einen einzigartigen Nachrichtenstring M angibt. Der Nachrichtenstring M enthält eine Vielzahl von Nachrichtensubstrings (Nachrichtenteilstrings) ml, m&sub2;, ..., mn, die jeweils wenigstens eines einer Vielzahl von Zeichen in einem Zeichensatz angeben. Ein Unterstring m; wird als "Transkriptionslabeldatenelement" oder einfach als "Transkriptionslabel" bezeichnet. Eine Transkription wird als einem formalen 2D-Bildquellenmodell (das unten definiert wird) "zugeordnet" beschrieben, wenn das formale 2D-Bildquellenmodell zusammen mit den Informationen, die von den Zeichen in der Transkription angegeben werden, eine Abbildung zwischen einem oder mehreren Glyphproben in einer eingegebenen 2D- Bildquelle von Glyphs und einem oder mehreren Zeichenlabeln etablieren, die Zeichenschablonen in dem Satz von zu trainierenden Zeichenschablonen angeben. Der Begriff "Abbilden (Mapping)" wird vorliegend in seiner mathematischen Bedeutung eines Bezugs auf eine Korrespondenzregel verwendet, die zwischen zwei Sätzen etabliert ist und jedes Mitglied des ersten Satzes einem einzelnen Mitglied des zweiten Satzes zuordnet. Transkriptionslabel haben keine implizierte oder abgeleitete Ordnung bzw. Reihenfolge mit Bezug aufeinander oder mit Bezug auf die Glyphproben in dem zugeordneten 2D-Bild, außer wenn die Transkription von einer Art ist, bei der die Ordnung der Transkriptionslabel durch die Definition des Transkriptionstyps explizit angegeben ist.

Eine Transkription wird als einer spezifischen eingegebenen 2D-Bildquelle von Glyphs "zugeordnet" bezeichnet, wenn die Transkriptionsdatenstruktur eine von zwei Bedingungen erfüllt: (1) Die Transkriptionsdatenstruktur ist die Ausgabe eines Erkennungsvorgangs, der auf dem eingegebenen 2D-Bild durchgeführt wird, oder kann aus dieser Ausgabe erzeugt werden. Der Erkennungsvorgang kann prozessorgesteuert sein, wie etwa eine computerimplementierte Erkennung oder ein Dekodierungsvorgang, der auf einem spezifischen 2D-Bild durchgeführt wird. Der Erkennungsvorgang kann aber auch von einem Benutzer unter Verwendung einer prozessorgesteuerten Maschine durchgeführt werden; beispielsweise kann ein Benutzer die Transkriptionsdatenstruktur dadurch erzeugen, dass er das 2D-Bild visuell inspiziert und Zeichenkodes unter Verwendung einer konventionellen Eingabeeinheit wie etwa einer Tastatur eingibt, die Signale erzeugt, die die Zeichenkodes angeben. (2) Die Transkriptionsdatenstruktur ist eine Datenstruktur, oder kann aus ihr erzeugt werden, die eine Eingabequelle für einen Bildbearbeitungsvorgang (ein Rendering) wie etwa einen Dokumentformatierungsvorgang ist, der das 2D-Bild erzeugt. Das eingegebene 2D-Bild, das einer Transkription zugeordnet ist, wird als "zugeordnetes 2D-Bild" bezeichnet.

Eine "wörtliche Transkription" ist ein Transkriptionstyp, der eine geordnete Abfolge von Transkriptionslabeln enthält, die jeweils ein Zeichenlabel für eine Zeichenschablone in dem Satz von gerade im Training befindlichen Schablonen angeben und von denen im Wesentlichen alle in der sequentiellen Reihenfolge ihres Auftretens in der Transkription durch visuelles Betrachten eines zugeordneten eingegebenen 2D-Bildes gepaart werden können mit jeweiligen einzelnen Glyphs, die in dem zugeordneten Bild auftreten und das die Zeichen darstellen, die von den jeweiligen Zeichenlabeln in der Transkription angegeben werden, wenn die Glyphs in einer Abfolge genommen werden, die mit der Lesereihenfolge für das zugeordnete 2D-Bild übereinstimmt. Fig. 4 verdeutlicht eine wörtliche Transkription 60, die einer 2D-Bildquelle von Glyphs 10 (Fig. 2) zugeordnet ist und eine einzelne geordnete Abfolge von Transkriptionslabeln enthält. Das Zeilenumschaltzeichen 62 ist ein Label, das angibt, dass die Zeichenlabel, die dem Zeilenumschaltzeichen folgen, gepaarte Glyphproben aufweisen, die in der nächsten Zeile des zugeordneten 2D-Bildes liegen; Zeilenumschaltzeichen werden gewöhnlicherweise in Datenstrukturen, die Text angeben, von Benutzern bei der Erstellung von Textdokumenten unter Verwendung eines Texteditors eingefügt.

Eine "nichtwörtliche Transkription" ist ein Transkriptionstyp, der einer eingegebenen 2D- Bildquelle von Glyphs zugeordnet und keine wörtliche Transkription ist. Eine nichtwörtliche Transkription kann beispielsweise ein Transkriptionslabel enthalten, das kein Fehler ist und das ein Zeichen angibt, das durch visuelles Betrachten nicht mit einem Glyph in dem zugeordneten 2D-Bild gepaart werden kann; auch können die Nichtzeichenlabeldaten Zeichen in einem Zeichensatz angeben, der ein anderer als der Zeichensatz ist, der von den im Training befindlichen Schablonen dargestellt wird. Beispielsweise kann ein Sonderzeichen, ein mathematisches Symbol oder eine Musiknotation, die als ein Glyph in einem zugeordneten eingegebenen 2D-Bild erscheint, in einem Transkriptionslabel als ein Zeichen in einem erweiterten Zeichensatz oder als ein String von einem oder mehreren ASCII-Zeichen dargestellt werden. Eine nichtwörtliche Transkription kann beabsichtigterweise Transkriptionslabel für einige Glyphs in einem zugeordneten 2D-Bild auslassen. Ein Beispiel dieses Transkriptionstyps ist eine solche Transkription, die einem 2D-Bild eines vorgedruckten Formulars zugeordnet ist, wobei die Transkription die Transkriptionslabel für die Informationen enthält, die in die Felder des Formulars eingefügt werden, jedoch Transkriptionslabel dafür weglässt, was als die auf dem Formular vorgedruckten Informationen erscheint, wie etwa die grafischen Elemente und die Glyphs, die Anweisungsinformationen bereitstellen.

Eine "Tag-Transkription" ist ein Typ nichtwörtlicher Transkription einer zugeordneten 2D- Bildquelle von Glyphs, bei der Nichtzeichenlabeldaten Informationen angeben, die mit "Tag" oder "Tag-Daten" benannt sind und Displaymerkmale erzeugen, wenn sie von einem Dokumentenverarbeitungsvorgang interpretiert werden, die in dem Format des zugeordneten 2D-Bildes oder als Teil des Glyphs in dem Bild wahrnehmbar sind. Tag- Daten enthalten informationen, die Formatcharakteristiken des 2D-Bildes identifizieren wie etwa Seiten-, Absatz- und Zeilenumbrüche und Zeilenabstände, die für die Lage eines Glyphs in dem 2D-Bild deterministisch sind; Informationen, die ein oder mehrere Erscheinungsbildattribute eines oder mehrerer Glyphs spezifizieren wie etwa den Font oder die Fontvariation, in der ein Glyph erscheint; oder Informationen, die zur Erzeugung von Glyphs in dem 2D-Bild führen, auf das kein explizites Transkriptionslabel in der Transkription abgebildet werden kann, wenn das Dokument formatiert ist. Die verschiedenen Typen von Informationen, die von einem Tag angegeben werden können, wird vorliegend allgemein als "Markup-Informationen" bezeichnet werden. Tag- Daten erscheinen typischerweise in Datenstrukturen, die als standardisierte Dokumentenaustauschformate zur Darstellung von Dokumentstruktur und Inhalt zwischen Dokumentenverarbeitungssystemen dienen sollen; solche Datenstrukturen werden typischerweise als die Ausgabe eines Vorganges erzeugt, der entweder eine eingegebene Dokumentendatenstruktur oder ein Eingabebild in eine Datenstruktur umwandelt, die das Dokument in der Standard-Austauschsprache darstellt. Beispiele solcher Sprachen enthalten SGML ("Standard Generalized Markup Language"), ODA ("Office Document Architecture") und HTML ("Hypertext Markup Language"). Tag-Daten erscheinen auch in Datenstrukturen, die von Dokumentspezifizierungs- und - formatierungssystemen, auch automatische Textlayoutsysteme genannt, verwendet oder erzeugt werden, die innerhalb der Datenstruktur Anweisungen über das Format und die logische Struktur eines Dokuments enthalten, wie dies in Dokumentendatenstrukturen zu finden ist, die unter Verwendung von Markup-Sprachen erzeugt worden sind. Beispiele solcher Dokumentenspezifizierungs- und -formatierungssysteme enthalten GML ("Generalized Markup Language"), TeX und LaTeX.

Fig. 5 verdeutlicht die Tag-Transkriptionsdatenstruktur 40 für eine Wörterbuchseite eines technischen Wörterbuches; der Tag-Transkription 40 ist das Bild der Wörterbuchseite zugeordnet, die in Fig. 6 als 2D-Bild 50 gezeigt ist. Die Tag-Transkription 40 enthält Transkriptionslabel 42, 44, 46 und 48, die Tag-Daten angeben, die die strukturellen Teile eines Eintrags, Namens, einer Kategorie bzw. des Hauptteils des Wörterbucheintrags identifizieren.

Die Fig. 5 und 6 verdeutlichen auch ein Beispiel von Tag-Daten, die zu der Erzeugung von Glyphs in dem 2D-Bild führen, auf das kein explizites Transkriptionslabel in der Transkription abgebildet werden kann. Das Bild 50 enthält jeweils linke und rechte Klammern 54 und 55 um eine Abfolge von Glyphs, die die Zeichen "electr" zeigen. Es ist zu sehen, dass die Tag-Transkription 40 keine Transkriptionslabel für linke und rechte Klammern 54 und 55 enthält, dass sie aber ein Transkriptionslabel 47 enthält, das angibt, dass der Nachrichtensubstring "electr" eine Kategorieinformation für den Worteintrag ist. Es kann gefolgert werden, dass der Nachrichtensubstring "category" rechte und linke Klammem 54 und 55 als Displayobjekte im Bild 50 erzeugt, wenn er als Formatierungsinformation von einem Dokumentenverarbeitungsvorgang interpretiert wird.

Ein "Satz von Transkription" bezieht sich auf wenigstens zwei Transkriptionen desselben Typs, denen jeweils ein einzelnes 2D-Bild zugeordnet ist. Mathematisch wird der Satz von Transkriptionsdatenstrukturen als ein regulärer Satz betrachtet. Fig. 7 verdeutlicht den direkten Fall einer einzelnen Transkriptionsnachricht, die ein alternatives Transkriptionslabel 72 von "F(rln)(omlorn)" für die Glyphs in der eingegebenen 2D- Bildquelle von Glyphs 10 (Fig. 2) liefert, die "From\n" darstellen, wodurch ein Satz von vier Transkriptionsdatenstrukturen 70 für das Bild 10 erzeugt wird.

Ein "formales Transkriptionsmodell" oder "Transkriptionsmodell" ist eine Datenstruktur, die den Nachrichtenstring der Transkription als einen regulären Satz darstellt, wie etwa als ein Finitzustandsübergangsnetzwerk oder eine Grammatik. Beispielsweise hat ein Finitzustandsübergangsnetzwerk eine Anzahl von Übergängen, von denen jeder Übergang einem Transkriptionslabel in der Transkription entspricht.

Ein Satz von Transkriptionen kann als formales Transkriptionsmodell dargestellt werden. Das Modell 800 in Fig. 8 verdeutlicht ein Beispiel eines Finitzustandübergangsnetzwerks für den Satz von Transkriptionen 70 in Fig. 7, wobei die Übergänge verdeutlicht werden, die für das Wort "From\n" in den Transkriptionen 70 auftreten.

Ein "formales zweidimensionales Bildquellenmodell" oder "formales 2D-Bildmodell" ist eine Datenstruktur, die eine Abbildung (ein Mapping) zwischen den Glyphpositionen der Glyphproben in dem 2D-Bild und Zeichenlabeln von Schablonen definiert, die die Glyphs als Proben der Zeichen identifizieren, die von jeweiligen Zeichenlabeln angegeben werden. Das formale 2D-Bildmodell ist eine explizite Eingabe in die Trainingstechnik und das System der vorliegenden Erfindung und enthält Anweisungen in der Form einer formalen Beschreibungssprache wie etwa einer formalen Grammatik oder eines Finitzustandsübergangsnetzwerks, die A-priori-Informationen kennzeichnen oder beschreiben einschließlich struktureller Merkmale und funktionaler Charakteristiken über den Satz möglicher 2D-Eingabebilder, für die ein Erkennungssystem entworfen worden ist, und einen Satz möglicher Transkriptionen, denen der Satz möglicher Bilder zugeordnet sein kann. Das formale 2D-Bildmodell beschreibt auch ein Zeichenschablonenmodell, das die zu trainierenden Schablonen modelliert, und es enthält einen Anfangssatz von Zeichenschablonen. Das formale 2D-Bildmodell ist analog zu einer formalen Grammatik in einem grammatikbasierten Zeichenstringparsingsystem, das als explizite Datenstruktur unabhängig von den Anweisungen (d. h. dem Kode) des Parsers existiert, den es verwendet.

Das formale 2D-Bildmodell versetzt die vorliegende Erfindung in die Lage, auf der Ebene von 2D-Bildern so zu arbeiten, dass keine Vortrainingsstufe einer Textzeilenisolierung oder Segmentierung einzelner Glyphs erforderlich ist. Strukturell definiert ein formales 2D-Bildmodell, das der zur Verwendung in der Trainingstechnik und dem System der vorliegenden Erfindung geeignete Modelltyp sein soll, Bildpositionsinformationen darüber, wie mögliche Bildobjekte (z. B. Glyphs, grafische Objekte, Fotografien etc.) in einem Bild, das in dem Satz möglicher 2D-Bilder enthalten ist, räumlich in dem 2D-Bild angeordnet sind. Häufig, aber nicht notwendigerweise, sind die durch das Modell definierten Glyphpositionsinformationen, wenn das Bild ein Dokument in englischer Sprache darstellt, zur konventionellen Lesereihenfolge für das Dokument konsistent, wenn das Dokument von einem Menschen gelesen wird. In dem unten beschriebenen veranschaulichten Ausführungsbeispiel werden Bilder einschließlich der eingegebenen 2D-Bildquelle von Glyphs 10 in Fig. 2 als rechteckig und ein Bildkoordinatensystem 13 (Fig. 2) aufweisend angenommen, in dem x nach rechts zunimmt, y nach unten zunimmt und die obere linke Ecke bei x = y = 0 liegt. Die Modellbeschreibung der Bildpositionsinformationen für Nichtglyphbildobjekte erlaubt die Eliminierung eines Abschnittes oder von Abschnitten eines gegebenen Eingabebildes als mögliche Bildpositionen von Glyphproben. Dieser Aspekt des Modells gestattet die Anpassung einer breiten Vielfalt von eingegebenen 2D-Bildern als Glyphprobenquellen, und das Modell kann zur Beschreibung irgendeiner einer Vielzahl von Klassen eingegebener 2D-Bilder konstruiert werden, einschließlich beispielsweise von Bildern gedruckter Musik, Bildern von Gleichungen und Bildern mit festgelegten und bekannten strukturellen Merkmalen wie etwa Geschäftsbriefen, Formularen und Telefonbranchenbüchern.

Das formale 2D-Bildmodell drückt Transkriptionslabelinformationen als den Satz von Regeln aus, der die Abbildung zwischen den von den Nachrichtensubstrings in der Transkription angegebenen Informationen und aktuellen Nachrichtensubstrings in Ausdrücken von Zeichenlabeln definieren, die in einem 2D-Bild erscheinen, und die für jeden Substring definieren, welches Erscheinungsbild er in dem Bild hat. Diese Abbildung etabliert wirksam eine Abbildung zwischen dem Satz möglicher 2D-Bilder, dem Satz möglicher Transkriptionen und dem Satz von Zeichenschablonen, wobei die Abbildung die Trainingstechnik in die Lage versetzt festzustellen, welches der möglichen 2D-Eingabebilder - das bedeutet, welche Abfolge von Zeichen in welcher Abfolge von Zeilen von Textstrings - am besten zu einem bestimmten 2D-Eingabebild passt, dem eine bestimmte Transkription zugeordnet ist. Mit dieser Information der besten Übereinstimmung ermöglicht es das Modell der Trainingstechnik, die Positionen der Glyphproben in dem 2D-Bild zu bestimmen und Zeichenlabel den Proben zuzuweisen.

Die spezifischen Positionsinformationen über die Glyphproben, die von der Trainingstechnik bestimmt werden müssen, sind eine Funktion des bestimmten Schablonenmodells, das die Zeichenschablonen definiert. Das Schablonenmodell definiert, wie Zeichenschablonen und folglich Glyphproben räumlich aufeinander bezogen in einem Bild angeordnet oder positioniert sind. Wenn die Schablone als ein segmentierungsbasiertes Modell definiert ist, muss die Trainingstechnik aus der Abbildung, die durch das formale Modell etabliert worden ist, Informationen erzeugen können, die Glyph Bounding-Boxen angeben. Wenn die Schablone als ein nichtsegmentierungsbasiertes Modell definiert ist, wie etwa als Sidebearing-Modell, muss die Trainingstechnik aus der vom formalen Modell etablierten Abb. Informationen erzeugen können, die Glyphursprungspositionen angeben.

Das Design des formalen 2D-Bildmodells, das als Eingabe in die Trainingsprozedur verwendet werden soll, wird von dem Typ und dem Inhalt der zu verwendenden Transkription beeinflusst und gestattet dem Benutzer so weiterhin eine Flexibilität bei der Bereitstellung von Trainingsdaten für die Trainingsprozedur. Die in dem formalen 2D-Bildmodell enthaltenen Informationen über die strukturellen und funktionellen Merkmale der Transkription sind nur solche Informationen, die von dem Modell benötigt werden, um die erforderliche Abbildung zwischen Glyphproben und Zeichenlabeln zu etablieren, was dann wieder die zusätzlichen Informationen sind, die von dem Modell benötigt werden, um ein bestimmtes Bild aus dem Satz möglicher Bilder zu spezifizieren, der von dem Modell definiert ist. Je weiter die Informationen in der Transkription von einer wörtlichen Transkription einer zugeordneten eingegebenen 2D- Bildquelle von Glyphs entfernt sind, desto mehr Informationen werden in dem 2D- Bildmodell benötigt, um die korrekte Abbildung zu etablieren.

Ein Beispiel für eine Implementierung des formalen 2D-Bildquellenmodells des zur Verwendung mit der vorliegenden Erfindung beabsichtigten Typs, der in der unten beschriebenen veranschaulichten Ausgestaltung verwendet wird, ist ein stochastisches Finitzustandsübergangsnetzwerk, das seine Erzeugungsregeln als eine reguläre Grammatik darstellt und explizit das Sidebearing-Modell der Buchstabenformumrissbeschreibung und -positionierung als ihr Zeichenschablonenmodell definiert. Eine vereinfachte allgemeine Veranschaulichung dieses Modells als Markov-Quelle ist schematisch als Modell 820 in Fig. 9 gezeigt und wird genauer unten bei der Diskussion einer bestimmten Implementierung der vorliegenden Erfindung beschrieben.

Der Zeichenschablonentrainingstechnik 200 der vorliegenden Erfindung, die in dem Blockdiagramm von Fig. 10 verdeutlicht wird, werden Eingaben der 2D-Bildquelle von Glyphproben 10, eines formalen Transkriptionsmodells 810 und eines Bildmodells 40 bereitgestellt, die alle oben definiert worden sind. Die Zeichenschablonentrainingstechnik 200 verwendet diese eingegebenen Datenquellen, um eine Zeichenschablonendatenstruktur 20 zu erzeugen, die einen Satz von Zeichenschablonen und ihre jeweiligen Zeichenlabeldatenelemente für einen bestimmten Zeichensatz enthält.

Die vorliegende Erfindung erkennt, dass die 2D-Bildquelle von Glyphproben typischerweise mehrere Probenbilder eines einzigen Zeichens in einem Zeichensatz in einem bestimmten Font enthält und dass eine trainierte Zeichenschablone für jedes einzelne Zeichen in dem 2D-Bild in dem spezifischen Font der Proben aus den Pixelfarben des Satzes von Pixeln erstellt werden könnte, die jede Glyphproben bilden, wenn Informationen, die die x,y-Koordinatenpositionen des 2D-Bildes angeben, und die Zeichenidentität jeder Probe bekannt wären. Die vorliegende Erfindung erkennt auch, dass eine dem 2D-Bild zugeordnete Transkription Identitäts- und Abfolgeinformationen für jeden der Glyphs in dem 2D-Eingabebild bereitstellt, die verwendet werden können, um das Zeichen einer jeweiligen Glyphprobe zu identifizieren. Das grammatikbasierte 2D-Bildquellenmodell, das explizit als eine Eingabe zu der Erfindung bestimmt ist, definiert räumliche Positionierungsinformationen über die Glyphs, die in der 2D- Bildquelle von Glyphproben auftreten, um die Glyphproben zu lokalisieren, und es definiert Mappingdaten, die eine Abbildung eines jeweiligen Glyphs, das in dem 2D-Bild vorkommt, auf ein Glyphlabel angeben, das das Zeichen in dem Glyphprobenzeichensatz angibt.

Die Zeichenschablonentrainingstechnik 200 kann eine mit Labeln versehene Zeichenschablone nur für solche Zeichen erzeugen, für die Glyphproben in dem 2D-Bild 10 vorkommen, und die Vollständigkeit des Zeichensatzes, für den Zeichenschablonen trainiert werden, hängt von der 2D-Bildquelle von Glyphproben 10 mit wenigstens einer Glyphprobe für jedes Zeichen in dem Zeichensatz ab. Da beispielsweise die englischen Buchstaben "j", "q", "x" und "z" in dem in Fig. 2 gezeigten Teil des 2D-Bildes 10 nicht erscheinen, wird die Zeichenschablonentrainingstechnik 200 diese Schablonen nicht erzeugen, wenn nur dieser Teil des 2D-Bildes 10 als Quelle von Glyphproben verwendet wird. Zur Vereinfachung wird im Folgenden auf den Zeichensatz, für den Zeichenschablonen trainiert werden, als "Glyphprobenzeichensatz" Bezug genommen, um seine Abhängigkeit von den Glyphproben anzugeben, die in der 2D-Bildquelle von Glyphproben 10 vorkommen. Die Qualität jeder trainierten Schablone hängt allgemein von der Zahl der in der 2D-Bildquelle von Glyphproben 10 für jedes Zeichen in dem Glyphprobenzeichensatz verfügbaren Glyphproben ab.

Die allgemeinen Schritte der Zeichenschablonentrainingstechnik 200, in Fig. 11 verdeutlicht, enthaltend in Schritt 220 die Bestimmung der Position jeder Glyphprobe im 2D-Bild 10 unter Verwendung der räumlichen Positionierungsinformationen, die durch das grammatikbasierte 2D-Bildquellenmodell 40 definiert sind, und die Bestimmung in Schritt 250 eines Glyphlabels für jede Glyphproben, die in dem 2D-Bild 10 liegt, unter Verwendung der Transkription 70 und der Mappingdaten, die durch das 2D- Bildquellenmodell 40 definiert sind und eine jeweilige Glyphproben, die im 2D-Bild 10 vorkommt, auf das Glyphlabel abbildet, das das Zeichen in dem Glyphprobenzeichensatz angibt, das von der Glyphprobe dargestellt wird. Das Ergebnis der Schritte 220 und 250 besteht darin, eine Datenstruktur zu erzeugen, die einen Satz von mit Labeln versehenen Glyphproben angibt, die die Trainingsdaten sind, aus denen Zeichenschablonen erzeugt werden können. Dann werden in Schritt 270 Zeichenschablonen unter Verwendung der Datenstruktur konstruiert, die den Satz von mit Labeln versehenen Glyphproben angeben. In einer besonderen Implementierung der Zeichenschablonentrainingstechnik 200 können Glyphproben und ihre Label gleichzeitig bestimmt werden und die Funktionen in den Schritten 220 und 250 könnten als kombiniert betrachtet werden, um die Trainingsdaten zu erzeugen, die zu dem Schritt 270 eingegeben werden; diese kombinierte Funktionalität ist in Fig. 11 durch die Prozedur 210 angezeigt, die die Schritte 220 und 250 in einem gestrichelten Kasten umschließt.

Die Organisation und der Inhalt der ausgegebenen Datenstruktur, die die Trainingsdaten angibt, die von den Schritten 220 und 250 erzeugt worden sind, können eine von mehreren Formen annehmen, die durch mehrere untereinander in Bezug stehende Faktoren bestimmt sind, die Aspekte der besonderen Implementierung der Zeichenschablonentrainingstechnik 200 wiederspiegeln.

Wenn das Zeichenschablonenmodell der Zeichenschablonen, die trainiert werden, das Sidebearing-Modell ist, muss die Prozedur 210 Trainingsdaten erzeugen, die mit Labeln versehene Glyphproben angeben, von denen jede durch eine x,y-Position in der 2D- Bildquelle von Glyphproben 10 identifiziert ist, die die Bildursprungsposition der Glyphprobe im 2D-Bild 10 angibt. Eine neuartige Schablonenkonstruktionstechnik, die detailliert beginnend mit der Diskussion zu Fig. 21 beschrieben wird, wird in Schritt 270 verwendet, um die binären Zeichenschablonen unter Verwendung einer Liste von mit Labeln versehenen Glyphbifdursprungspositionen zu konstruieren, die Bildursprungspositionen von Glyphproben im 2D-Bild 10 angeben.

Wenn das Zeichenschablonenmodell der Zeichenschablonen, die trainiert werden, ein segmentierungsbasiertes Modell ist, findet der Schritt 220 Bounding-Boxen für jede Glyphprobe im 2D-Bild 10 und erzeugt als Trainingsdaten eine Liste von mit Labeln versehenen Bounding-Box-Koordinaten oder einen Satz von mit Labeln versehenen isolierten Glyphproben, die aus dem 2D-Bild 10 extrahiert worden sind. Eine wohlbekannte Pixelmittelwertbildungs- und Schwellenwerttechnik kann dann in Schritt 270 verwendet werden, um die binären Zeichenschablonen aus den segmentierten oder isolierten Trainingsdaten zu erzeugen. Bei einer solchen Technik wird die Anzahl von Vordergrund- und Hintergrundpixeln für jede Pixelposition in jeder der Proben gezählt und durch die Gesamtzahl von Proben geteilt und ein Schwellenwert wird verwendet, um zu bewerten, ob der Mittelwert eine Vordergrund- oder eine Hintergrundbestimmung ergeben sollte.

Unter Bezugnahme auf Fig. 12 sind das 2D-Bildquellenmodell 830, das als stochastisches Finitzustandsübergangsnetzwerk ähnlich dem im US-Patent 5,321,773 offenbarten repräsentiert ist, und das Finitzustandstranskriptionsnetzwerk 850 Eingaben in den Netzwerkverschmelzungsprozess 300, der ein verschmolzenes Finitzustandsnetzwerk erzeugt, das Transkriptionsbildnetzwerk 870 genannt wird. Dieses verschmolzene Netzwerk wird dann verwendet, um die 2D-Bildquelle von Glyphproben 10 unter Verwendung eines Viterbi-Dekodierungsprozesses 330 zu dekodieren, der eine beste Abfolge von Übergängen, oder einen Pfad, durch das verschmolzene Netzwerk erzeugt. Ein anfänglicher Satz von Zeichenschablonen 500 wird während dieses Dekodierungsprozesses verwendet; die gestrichelte Linie 832 gibt an, dass der anfängliche Satz von Zeichenschablonen 500 Teil des Finitzustandsübergangsnetzwerks 830 ist, da, wie weiter oben angemerkt, Zeichenschablonen Attribute zu Übergängen im Netzwerk 830 sein können. Der Prozess 374 identifiziert die Übergänge und deren entsprechende Bildursprungspositionen im 2D-Bild 10, die den besten Pfad durch das Transkriptionsbildnetzwerk 870 zusammensetzen, wie er vom Viterbi-Dekodierungsprozess 330 erzeugt worden ist. Der Prozess 380 bestimmt dann die Bildursprungspositionen und Nachrichtenstrings aus den Übergängen, die von Null verschiedene Zeichenschablonenattribute aufweisen; diese Bildursprungspositionen geben geschätzte Lagen von Glyphproben im 2D-Bild 10 an. Die Trainingsdaten, d. h. die mit Labeln versehenen Glyphbildursprungspositionen 390, sind die Ausgabe dieser Abfolge von Prozessen.

Das Flussdiagramm in Fig. 13 verdeutlicht die Schritte einer Implementierung des Zeichenschablonentrainings von Fig. 11, das das Finitzustandsübergangsnetzwerk 830 als das formale 2D-Bildquellenmodell und das Transkriptionsnetzwerk 850 verwendet, um die Transkription zu repräsentieren. Der Dekodierungsschritt 330 verwendet einen aktuellen Satz von Schablonen, um den besten Pfad durch das Transkriptionsbildnetzwerk 870 zu bestimmen. Für die anfängliche Iteration der Dekodierung kann ein anfänglicher Satz von Zeichenschablonen mit willkürlichem Inhalt vom Prozessor zur Zuordnung zu den Übergängen im Transkriptionsbildnetzwerk 870 erzeugt werden. Die Schritte des Dekodierens, Extrahieren von Trainingsdaten, Konstruierens von Schablonen und Bestimmens der Zeichensatzbreite in den Schritten 330, 380, 400 und 490 werden iteriert, bis eine Beendigungsbedingung erfüllt ist, die in Schritt 384 geprüft wird, und der im Dekodierungsschritt 330 während der auf die anfängliche Iteration folgenden Iterationen verwendete Satz von Schablonen ist der aktuelle Satz von Schablonen, der als die Ausgabe des Schablonenkonstruktionsschritts 400 erzeugt wird. Die Trainingsdatenextraktion aus dem besten Pfad, der durch die Dekodierung des 2D- Bildes 10 erzeugt worden ist, ist in Fig. 12 als Prozesse 374 und 380 verdeutlicht und in Fig. 13 als kombinierter Prozess 380 gezeigt. Die Prozesse 300, 330 und 380 werden nun genauer beschrieben.

Unter Bezugnahme auf Fig. 9 wird die Struktur eines Satzes von Bildern formal durch die Modellierung der Bilderzeugung als Bildquellenmodell 820 erfasst, das auch Markov- Quelle genannt wird. Eine Markov-Quelle besteht aus einem finiten Satz von Zuständen (Knoten, Scheitelpunkten) N und einem Satz gerichteter Übergänge (Zweige, Kanten) B. Jeder Übergang t verbindet ein Paar von Zuständen Lt und Rt, die Vorgängerzustand (links) bzw. Folgezustand (rechts) von t genannt werden. Zwei unterschiedliche Mitglieder von N sind der Anfangszustand n&sub1;, der mit Bezugszeichen 822 bezeichnet ist, und der Endzustand nF, der mit Bezugszeichen 824 bezeichnet ist. Es wird angenommen, dass kein Übergang nF als seinen Vorgänger hat, so dass der Endzustand ein Einfangzustand ist. Jedem Übergang t ist ein Vierertupel von Attributen 826 (Qt, mt, at, At) zugeordnet, wobei Qt die Schablone, mt der Nachrichtenstring, at die Übergangswahrscheinlichkeit und Δt mit dem Bezugzeichen 828 die Vektorverschiebung von t analog der Satzbreite für Zeichen ist (siehe die obige Diskussion zu Fig. 1 über eine Beschreibung der Zeichensatzbreite). In der verdeutlichten Implementierung können einige dieser Attribute für bestimmte Übergänge null sein, wobei angenommen wird, dass jeder Übergangsnachrichtenstring mt des Bildquellenmodells 820 entweder ein leerer String E ist oder andernfalls ein einzelnes Zeichen enthält, und wobei die Vektorverschiebung 828 skalare Komponentenwerte aufweisen kann, die negativ, null oder positiv sind. Die Schablone Qt ist über die gesamte Bildebene Q definiert, obwohl normalerweise ihre Grundlage (ein Satz von von Null verschiedenen Vordergrundpixeln) innerhalb eines kleinen Bereiches nahe dem Ursprung des lokalen Schablonenkoordinatensystems gelegen sein wird.

Ein "Pfad" in einer Markov-Quelle ist eine Abfolge von Übergängen t&sub1;... tp, für die LtI = nI und

Rti = Lti+1

für i = 1, ..., P - 1 gilt. Ein "vollständiger Pfad" ist ein Pfad, für den RtP = nF gilt. Ein "Zyklus" oder eine "Schleife" ist eine Abfolge von Übergängen t&sub1;... tp, für die Lt1 = Rtp gilt. Jedem π ist eine zusammengesetzte Nachricht oder ein Nachrichtenstring

Mπ = mti ... mt (2)

zugeordnet, die durch Aneinanderfügen der Nachrichtenstrings der Übergänge des Pfades gebildet wird. Ein Nachrichtenstring in diesem Zusammenhang ist ein anderer Ausdruck für die Transkription und die Ausdrücke Nachricht, Nachrichtenstring, Transkription und Transkriptionsstring werden in der Diskussion der verdeutlichten Implementierung austauschbar verwendet. Der durch vollständige Pfade durch eine Markov-Bildquelle erzeugte Satz von Transkriptionen ist eine reguläre Sprache und das Quellenmodell selbst ist ein Finitzustandsautomat, der diese Sprache akzeptiert. Ein Markov-Bildquellenmodell definiert eine Wahrscheinlichkeitsverteilung auf vollständigen Pfaden durch

Pr{π} = ati (3)

und bewirkt eine Wahrscheinlichkeitsverteilung auf Nachrichten durch

Pr{M} = Pt{π} (4)

wobei Mπ die einem Pfad r zugeordnete Nachricht ist.

Ebenfalls jedem Pfad 7r zugeordnet sind eine Abfolge von Vektorbildpixelpositionen x1 Xp+1

x&sub1; = 0 (5)

xi+1 = xi + Δti, (6)

wobei Xp+1 der Einfachheit halber eingeführt worden ist, und ein zusammengesetztes Bild Q, das durch

Qπ = Qti{xi} (7)

definiert ist, wobei Q[x] eine Bezeichnung für Q ist, das so verschoben worden ist, dass der Ursprung seines lokalen Koordinatensystems bei x liegt, und wobei die Vereinigung von zwei Schablonenbildern ein Bild ist, das Vordergrundpixel dort aufweist, wo eines der beiden Schablonenbilder einen Vordergrundpixel hat. Für einen Pfad π wird

Δp = xP+1 - x1 = Δti

als die Verschiebung des Pfades definiert und Δxπ und Δyπ bezeichnen die x- bzw. y- Komponenten von Δπ. Ein Paar (xi, t&sub1;), das aus einer der durch (5) oder (6) definierten Positionen besteht, und der entsprechende Übergang der Markov-Quelle wird "mit einem Label versehene Übergangsbildursprungsposition" genannt werden. Der Satz all solcher durch einen vollständigen Pfad definierter Paare wird der Satz von mit Labeln versehenen Übergangsbildursprungspositionen des Pfades genannt. Für jeden Übergang t sei Ni die Bezeichnung der Anzahl von Übergangsbildursprungspositionen des Pfades, die mit dem Label t versehen sind, und die entsprechenden Übergangsbildursprungspositionen seien mit x ... x bezeichnet. Somit gilt

Basierend auf der Prämisse, dass Fonts üblicherweise so entworfen werden, dass die Vordergrundpixel der Zeichenglyphs in Textstrings nicht überlappen (d. h. dieselben Vordergrundpixel miteinander teilen), ist es erforderlich, dass Bildquellenmodelle des in Fig. 9 und in der vorliegenden verdeutlichten Implementierung verdeutlichten Typs so entworfen werden, dass die Vereinigung der Pixel einer an (x1, t) gelegenen Schablone mit den Pixeln einer an (x1, t) gelegenen Schablone die leere Menge

Qti[xi] Qti[xi] = (10)

für 1 ≠ j für jeden Pfad π ist. Dieses in (10) ausgedrückte Erfordernis kann als "Schablonendisjunktheitszwang" benachbarter Schablonengrundlagen bezeichnet werden.

Das Bildquellenmodell 820 (Fig. 9) definiert eine Beziehung oder eine Abbildung, die bidirektional ist, zwischen Nachrichtenstrings und Bildern über einen zugrundeliegenden Pfad und (2) und (7).

Ein Bildquellenmodell definiert einen Finitzustandsakzeptor für die Sprache von Nachrichten, die von dem Modell erzeugt worden sind. Somit läßt sich bei einem gegebenen Nachrichtenstring M problemlos feststellen, ob es einen vollständigen Pfad π gibt, für den Mπ = M gilt, und ein solcher Pfad finden, wenn er existiert. Das durch (7) definierte Bild Qπ ist dann ein Bild von M. Wenn das Bildquellenmodell einen deterministischen Akzeptor für die Nachrichtensprache definiert, lässt der Prozess der Nachrichtenbildverarbeitung unter Verwendung des Bildquellenmodells eine einfache prozedurale Interpretation zu. Man stelle sich einen Bilderzeugungsautomaten (bezeichnet "Bilderzeuger (Imager)") vor, der unter der Steuerung eines eingegebenen Nachrichten-"Programms" zeichnet, was ein "ideales" Bild in einer Ausgabebildebene genannt werden kann. Die Struktur des Bilderzeugers ist durch ein Finitzustandsbildquellenmodell des in Fig. 9 verdeutlichten Typs definiert. Der Bildererzeuger beginnt am Ort (0, 0) der Ausgabebildebene im internen Zustand n&sub1;. Der Bilderzeuger überprüft das erste Zeichen in der Eingabenachricht, vergleicht es mit den Nachrichtenlabeln auf den Übergängen von n&sub1; und wählt den Zweig aus, dessen Nachricht mit dem Eingabezeichen übereinstimmt. Wenn die dem ausgewählten Zweig zugeordnete Schablone nicht null ist, zeichnet der Bilderzeuger eine Kopie der Schablone auf der Ausgabebildebene, wobei der Schablonenursprung an der gegenwärtigen Bildposition des Bilderzeugers ausgerichtet ist. Der Bilderzeuger inkrementiert dann seine Bildposition um die Zweigverschiebung und erneuert seinen internen Zustand auf den Nachfolgeknoten des ausgewählten Zweiges. Dieser Prozess wird für jedes Zeichen der Eingabenachricht wiederholt, bis das ideale Bild Qπ- und ein Pfad durch das Netzwerk vom Anfangsknoten n&sub1; bis zum Endknoten nF - vervollständigt ist.

Als Bilddekodierer kann das Bildquellenmodell 820 verwendet werden, um einfache Textstrings aus dem betrachteten Bild zu extrahieren, um eine wörtliche Texttranskription des Bildes zu erzeugen (d. h., eine Transkription ohne Formatierung oder logische Strukturtags). Dieses Textstrings werden aus dem Nachrichtenstringattribut extrahiert, das jedem in einem Pfad enthaltenen Übergang zugeordnet ist, der durch das Modell 820 identifiziert ist, wenn das betrachtete Bild dekodiert wird. Das Bildquellenmodell 830 in Fig. 14 modelliert einen Satz von 2D- Bildern, die die gemeinsame räumliche Struktur einer einfachen Textspalte aufweisen, und das Modell wird verwendet werden, um den Prozess der Bilddekodierung genauer zu erläutern. Eine einfache Textspalte besteht aus einer vertikalen Abfolge von Textzeilen, die sich mit weißem Raum (Hintergrund) abwechseln. In horizontaler Richtung ist eine Textzeile eine Abfolge von Zeichen, die gemäß des in Fig. 1 gezeigten Sidebearing-Modells gesetzt sind. Die 2D-Bildquelle von Glyphproben 10 ist ein repräsentatives Bild des vom Bildquellenmodell 830 modellierten Typs. Das Modell 830 modelliert einen Pfad durch ein 2D-Bild einer einzelnen Textspalte, die der konventionellen Leseordnung für einen Text in englischer Sprache folgt, wobei angenommen wird, dass der Pfad durch das Bild an der oberen linken Ecke des Bildes startet und sich zu der unteren rechten Ecke fortsetzt und dass er sich in wiederholten 1 D-Zeilensequenzen von der linken Seite des Bildes zu der rechten Seite fortsetzt. Jeder Übergang t zwischen Knoten in dem Netzwerk besitzt das in Fig. 14 in der Reihenfolge [at] (Δt), mt, Qt gezeigte zugeordnete Vierertupel von Attributen, wobei der Nachrichtenstring mt das durch die Schablone dargestellte Zeichen identifiziert, wenn einer Schablone Qt ein Übergang zugeordnet ist. Es ist ersichtlich, dass einige dieser Attribute für einige Übergänge null sind.

Wird nun auf Fig. 14 Bezug genommen, entspricht Zustand n&sub1; der Erzeugung vertikalen weißen Raumes. Jedes Mal, wenn t&sub1; überquert wird, bewegt sich der Bilderzeuger eine Reihe nach unten, ohne irgendetwas auf der Ausgabebildebene zu zeichnen, da t&sub1; keine Bildschablone zugeordnet ist. An irgendeinem Punkt erreicht der Bilderzeuger das obere Ende einer Textzeile und folgt dem Zweig t&sub2;. Die Verschiebung (0, B) von t&sub2; bewegt den Cursor nach unten auf die Textgrundlinie; B ist die Fonthöhe über der Grundlinie. Der Zustand n&sub2; stellt die Erzeugung einer horizontalen Textzeile dar. Die Selbstübergänge von n&sub2; auf n&sub2; sind von zwei Typen. Die F-Übergänge ti, die gemäß Bildschablonen Qi und Einzelzeichennachrichtenstrings "ci" mit Labeln versehen sind, werden verwendet, um einzelne Glyphs auf der Ausgabebildebene zu zeichnen. Die jedem dieser Zweige zugeordnete horizontale Verschiebung ist die Zeichensatzbreite Wti. Die Zweige t&sub3; und t&sub4; haben leere Schablonen, die ihnen zugeordnet sind und weißen Raum darstellen. Der Zweig t&sub3; stellt einen weißen Raum einer minimalen Breite (1 Pixel) dar und wird zur genauen Abstandsjustierung verwendet. Der Zweig t&sub4; entspricht einem wirklichen Leerzeichen der fontabhängigen Breite WS und ist mit einer Leerzeichennachricht " " als Label versehen. Am Ende einer Textzeile überquert der Bilderzeuger t&sub5; ("Zeilenvorschub") und betritt den "Wagenrücklauf"-Zustand n&sub3;. Die Nachricht auf t&sub5; ist das Zeilenwechselzeichen "n". Die t&sub5; zugeordnete vertikale Verschiebung ist die Fonttiefe D. Jede Überquerung des Zweiges te bewegt den Bilderzeuger um eine Pixel nach links. Schließlich lässt der Übergang t7 den Bilderzeuger zum Zustand n, zurückkehren und der Prozess wird für die nächste Textzeile wiederholt. Nachdem die letzte Textzeile erzeugt worden ist, überquert der Bilderzeuger t8 zu Endzustand ni.

Die Transkriptionsdatenstruktur 70, die einen Satz möglicher, der 2D-Bildquelle von Glyphproben 10 zugeordneter Übergänge darstellt, wird auch als ein Finitzustandsnetzwerk dargestellt, das im Folgenden als "Transkriptionsnetzwerk" bezeichnet wird. Das Transkriptionsnetzwerk 850 ist eine vereinfachte Form eines Finitzustandsbildquellenmodells des in Fig. 9 verdeutlichten Typs, in dem jedem Übergang ein Nachrichtenstring mt, jedoch keine anderen Attribute zugeordnet ist. Fig. 15 zeigt ein einfaches Beispiel eines Teiles 852 des Transkriptionsnetzwerks 850 für die Transkription 70 und stellt den Satz dar, der die zwei Transkriptionsstrings "orn\n" und "om\n" enthält, wobei das Symbol "in" das Zeilenwechselzeichen darstellt. In der verdeutlichten Implementierung, wie im Fall mit dem Bildquellenmodell 830, wird jeder Übergangsnachrichtenstring mt des Transkriptionsnetzwerks 850 entweder als Leerstring E oder andernfalls als ein einzelnes Zeichen enthaltend angenommen. Die Datenstruktur, die das Transkriptionsnetzwerk 850 darstellt, wird in Schritt 292 als eine Eingabe in das Schablonentrainingsverfahren der erläuterten Ausgestaltung empfangen und gespeichert. Das Transkriptionsnetzwerk 850 kann aus der Transkriptionsdatenstruktur 70 durch einen vorherigen manuellen oder automatischen Prozess erzeugt werden, wie etwa durch einen Prozess, der konventionelle Mittel zum Erzeugen von Finitzustandsstringgrammatiken und Übergangsnetzwerken verwendet.

Das Bildquellenmodell 830 und das Transkriptionsnetzwerk 850 definieren zusammen ein ideales Bild, das eine räumliche Anordnung von Kopien von Zeichenschablonen ist, die an bestimmten Bildpositionen in dem idealen Bild gelegen sind und gemäß einem Nachrichtenstring ausgewählt werden, der mit der Transkription übereinstimmt, und dieses ideale Bild ist eine Approximation des wirklichen 2D-Eingabebildes, das der Transkription zugeordnet ist. Es folgt daraus, dass das Dekodieren des 2D-Bildes 10 unter Verwendung des Bildquellenmodells 830 am effizientesten wäre, wenn die Dekodierung gezwungen werden könnte, nur ideale Bilder und folglich Pfade, die mit den Pfaden übereinstimmen, und folglich Nachrichtenstrings, die vom Transkriptionsnetzwerk 850 erzeugt werden, zu erzeugen. Eine solche Beschränkung kann dem Dekodierungsprozess, der das Bildquellenmodell 830 verwendet, auferlegt werden durch das Verschmelzen des Bildquellenmodells 830 mit dem Transkriptionsnetzwerk 850.

Die Eingaben in den Netzwerkverschmelzungsschritt 300 (Fig. 12 und 13) sind das 2D- Bildquellenmodell 830 und das Transkriptionsnetzwerk 850. Die Ausgabe dieses Schritts ist ein zweites Markov-Bildquellenbild des in Fig. 9 verdeutlichten Typs und wird Transkriptionsbildnetzwerk 870 genannt. Das Transkriptionsbildnetzwerk 870 wird durch die folgenden zwei Eigenschaften definiert: (a) für jeden vollständigen Pfad π in dem Transkriptionsbildnetzwerk gibt es einen vollständigen Pfad in dem Bildquellenmodell 830, der denselben Transkriptionsstring und dasselbe Bild wie π hat; und (b) wenn für jeden vollständigen Pfad π in dem Bildquellenmodell 830 die Transkription von π in dem Satz von Transkriptionen liegt, der vom Transkriptionsnetzwerk 850 erzeugt wird, dann gibt es einen vollständigen Pfad im Transkriptionsbildnetzwerk 870, der denselben Transkriptionsstring und dasselbe Bild wie π hat. Der Satz von Transkriptionen, der von dem Transkriptionsbildnetzwerk erzeugt wird, ist die Überschneidung des Satzes von Transkriptionen, die vom Bildquellenmodell 830 erzeugt worden sind, und des Satzes von Transkriptionen, die vom Transkriptionsnetzwerk 850 erzeugt worden sind. Die idealen Bilder, die vom Transkriptionsbildnetzwerk erzeugt werden und eine gegebene Transkription aufweisen, sind dieselben wie die vom Bildquellenmodell 830 erzeugten, die diese Transkription aufweisen.

Der Netzwerkverschmelzungsschritt 300 ist im Wesentlichen befasst mit der Konstruktion von Übergängen zwischen Paaren von Bildquellen- und Transkriptionsnetzwerkzuständen in dem verschmolzenen Transkriptionsbildnetzwerk, so dass das Transkriptionsbildnetzwerk die beiden oben definierten Eigenschaften (a) und (b) erfüllt. Diese Übergänge werden gemäß der folgenden drei Schritte konstruiert.

1. Für jeden Übergang t des Bildquellenmodells 830, für den mt = E gilt (d. h. die t zugeordnete Nachricht der Nullstring ist), und für jedes j = 0... T-1: Füge zu dem Transkriptionsbildnetzwerk einen Übergang vom Knoten (Lt, sj) zum Knoten (Rt, sj) hinzu. Die jedem solchen Übergang des Transkriptionsbildnetzwerks zugeordnete Nachricht, Schablone und Verschiebung sind dieselben wie diejenigen von t.

2. Für jeden Übergang t des Bildquellenmodells 830, für den mt + E gilt (d. h. die t zugeordnete Nachricht ein Einzelzeichenstring ist), und für jeden Übergang t' des Transkriptionsnetzwerks 850, für den mt' = mt gilt: Füge zu dem Transkriptionsbildnetzwerk einen Übergang von Knoten (L = Lt) zum Knoten (R~ Rv) hinzu. Die jedem solchen Übergang des Transkriptionsbildnetzwerks zugeordnete Nachricht, Schablone und Verschiebung sind dieselben wie diejenigen von t.

3. Für jeden Übergang t' des Transkriptionsnetzwerks 850, für den mt' = E gilt, und für jedes i = 0... N-1: Füge zu dem Transkriptionsbildnetzwerk einen Übergang vom Knoten (n; Lt) zum Knoten (n; Rt~) hinzu. Die jedem solchen Übergang des Transkriptionsbildnetzwerks zugeordnete Nachricht und Schablone sind beide leer und die Verschiebung ist der Vektor 0.

Die Konstruktion eines Teils des Transkriptionsbildnetzwerks 870 ist schematisch in den Fig. 16, 17, 18 und 19 unter Verwendung des Bildquellenmodells 830 von Fig. 14 für eine einfache Textspalte und des in Fig. 15 gezeigten Teils 852 des Transkriptionsnetzwerks 850 verdeutlicht. Fig. 16 verdeutlicht die Knoten des Transkriptionsbildnetzwerks, das durch den Netzwerkverschmelzungsprozess 300 konstruiert worden ist, als Punkte in einem zweidimensionalen (2D-) Güter 860, wobei Bildquellenmodellknoten 862 horizontal und Transkriptionsnetzwerkknoten 864 vertikal im 2D-Gitter 860 positioniert sind. Die Gitterpunkte 866 und 868 für den Anfangszustand (n&sub1; sI) bzw. den Endzustand (nF sF) sind jeweils mit einem Kreis um einen Punkt herum dargestellt. Fig. 17 zeigt das Transkriptionsbildnetzwerk, nachdem Übergänge in dem Transkriptionsbildnetzwerk gemäß Schritt (1) der oben beschriebenen Prozedur konstruiert worden sind. Zur Vereinfachung sind Übergangswahrscheinlichkeiten nicht gezeigt. Fig. 18 zeigt die Übergänge von Fig. 17, die in Schritt (1) des Netzwerkverschmelzungsprozesses hinzugefügt worden sind, als gestrichelte Linien und die Übergänge, die zu dem Transkriptionsbildnetzwerk im Schritt (2) der obigen Prozedur hinzugefügt worden sind, als durchgezogene Linien. Wiederum werden Übergangswahrscheinlichkeiten und Verschiebungen nicht gezeigt. Da das Übergangsnetzwerk 850 in Fig. 15 keine Übergänge mit leeren Nachrichtenstrings enthält, wird Schritt (3) der obigen Prozedur zum Konstruieren von Übergängen in diesem Beispiel nicht angewendet.

Jeder Knoten, der nicht auf einem vollständigen Pfad liegen kann, kann vvn dem kombinierten Transkriptionsbildnetzwerk vor dessen Verwendung beim Dekodieren gelöscht werden, wie dies auch bei allen Übergängen möglich ist, die einen gelöschten Knoten betreten oder ihn verlassen. Fig. 19 zeigt den Abschnitt 872 des kombinierten Transkriptionsbildnetzwerks, der übrigbleibt, nachdem diese Vereinfachung durchgeführt worden ist. Es ist zu beachten, dass dieses vereinfachte, oder verschmolzene, Netzwerk wesentlich weniger Zustände und Übergänge enthält als das kombinierte Transkriptionsbildnetzwerk von Fig. 18. Somit führt die Netzwerkvereinfachung oder Verschmelzung üblicherweise zu einer schnelleren Dekodierung der Eingabequelle von Glyphproben.

Der Dekodierungsprozess 330 (Fig. 13) kann unter Verwendung irgendeines Typs eines software- oder hardwareimplementierten Dekoders vollzogen werden, der zum Dekodieren des 2D-Bildes 10 unter Verwendung des verschmolzenen Transkriptionsbildnetzwerks geeignet ist, um die mit Labeln versehenen Glyphbildursprungspositionen zu erzeugen, die die Glyphproben im 2D-Bild 10 angeben. Insbesondere ist ein auf einem dynamischen Programmierungsalgorithmus basierender Dekoder, der die Fehlerwahrscheinlichkeit zwischen dem ursprünglichen eingegebenen 2D-Bild und einem idealen Ziel-2D-Bild Qn minimiert, wahrscheinlich der geeignetste, für eine bestimmte Implementierung zu verwendende Dekodierungsprozess.

Allgemein wird ein Dekodierungsprozess des zur Verwendung mit der vorliegenden Erfindung geeigneten Typs einige oder alle der vollständigen Transkriptionsbildpfade durch das Transkriptionsbildnetzwerk identifizieren, von denen jeder ein ideales Ziel-2D- Bild Qn angibt, und er wird bestimmen, welcher der identifizierten Pfade der beste Pfad ist, indem er feststellt, welches ideale Ziel-2D-Bild mit der 2D-Bildquelle von Glyphproben gemäß eines definierten Übereinstimmungskriteriums am besten übereinstimmt. Der beste Pfad durch das Netzwerk ist der Transkriptionsbildpfad, der das am besten passende ideale Ziel-2D-Bild angibt; Transkriptionsbildursprungspositionen in der 2D-Bildquelle von Glyphproben können aus den Übergängen berechnet werden, die diesen besten Pfad bilden, und Glyphbildursprungspositionen und deren Label sind dann wieder von ausgewählten Übergängen und deren Übergangsbildursprungspositionen verfügbar. Das Übereinstimmungskriterium kann jedes geeignete Bildmaß sein; typischerweise wird das Übereinstimmungskriterium die Optimierung einer Pixelübereinstimmungszahl (eines "Scores") für das ideale Zielbild verglichen mit der 2D-Bildquelle von Glyphproben enthalten.

Der Dekodierungsprozess 330 (Fig. 13) in der verdeutlichten Implementierung findet den MAP-Pfad (MAP = "maximum a posteriori") durch das Transkriptionsbildnetzwerk unter Verwendung des angenommenen asymmetrischen Bitflipkanalmodells. Der Zweck des Viterbi-Dekodierers ist es, eine rekursive MAP-Entscheidungsfunktion über alle · vollständigen Pfade durch das Transkriptionsbildnetzwerk zu maximieren, um den wahrscheinlichsten Pfad durch das Netzwerk zu bestimmen. Wie oben bei der Diskussion des Dekodierens unter Verwendung des Bildquellenmodells 830 angemerkt, entspricht jeder vollständige Pfad durch das Transkriptionsbildnetzwerk einem idealen Bild, das während des Dekodierens erzeugt wird. Somit stellt der Viterbi-Dekodierer fest, welches ideale Bild der möglichen idealen Bilder, die aus vollständigen Pfaden durch das Netzwerk erzeugt werden, im (pixelmäßigen) Erscheinungsbild dem Eingabebild am nächsten ist, das dekodiert wird, d. h. dem 2D-Bild 10. Er tut dies, indem er ein Wahrscheinlichkeitsmaß, oder eine Wahrscheinlichkeitszahl, für einen Pfad, der ein ideales Bild definiert, berechnet, also die Summe der Ergebniszahlen (Scores) für einzelne Übergänge in dem Pfad.

Fig. 20 ist ein Flussdiagramm, das die Abfolge von Schritten verdeutlicht, die den Viterbi-Dekodierer des Dekodierungsprozesses 330 der verdeutlichten Ausgestaltung implementieren. Die Viterbi-Bilddekodierung beinhaltet die Pfadfindung in einem dreidimensionalen Dekodierungsgitter, das auch Dekodierungs-Trellis genannt wird. Das Dekodierungsgitter ist aus Knoten zusammengesetzt, die als einen Stapel von Bildebenen bildend betrachtet werden können, eine Ebene für jeden Knoten oder Zustand des Quellenmodells. Es gibt eine Eins-zu-eins-Entsprechung zwischen den Zuständen und Pfaden in dem Transkriptionsbildnetzwerk und Knoten und Pfaden in dem Gitter, und entsprechende Übergänge zwischen Knoten in dem Gitter haben dieselben Attributinformationen wie Übergänge zwischen Zuständen in dem Transkriptionsbildnetzwerk. Somit ist in Schritt 334 das Transkriptionsbildnetzwerk 870 zunächst in einer Datenstruktur als das Dekodierungsgitter dargestellt. Als nächstes muss in Schritt 338 die Reihenfolge bestimmt werden, in der Ergebniszahlen für die Knoten in dem Gitter berechnet werden müssen; dies wird dadurch vollzogen, dass ein Zahlberechnungsplan für die Rekursion erzeugt wird, der angibt, in welcher Reihenfolge die Knoten des Gitters besucht und folglich in welcher Reihenfolge die Knotenzahlen berechnet werden müssen. Dann werden die maximalen Wahrscheinlichkeitszahlen für jeden Knoten in der durch den Plan vorgeschriebenen Reihenfolge im Schritt 340 berechnet. Für jeden Knoten wird der Übergang in diesen Knoten, der die Wahrscheinlichkeitszahl maximiert, identifiziert und gespeichert. Die Schritte des Dekodierungsprozesses 330 wurden als in einer bestimmten Abfolge durchgeführt verdeutlicht, zu Zwecken der Beschreibung der Funktionen, die während der Dekodierung gemäß der verdeutlichten Implementierung durchgeführt werden; sie können in einer tatsächlichen Softwareimplementierung gleichzeitig durchgeführt werden und werden dies gewöhnlich auch.

Bei Abschluss der Dekodierung, nachdem die Wahrscheinlichkeitszahl für die nF- Bildebene in dem Dekodierungsgitter berechnet worden ist, wird der vom Viterbi- Dekoder gefundene wahrscheinlichste vollständige Pfad in Schritt 380 durch Zurückverfolgen über die gespeicherten Übergänge vom Endknoten zum Anfangsknoten in dem Dekodierungsgitter wiedergewonnen, um die Übergänge zu identifizieren, die den besten Pfad bilden, und um die Übergangsbildursprungspositionen (xi, ti) im 2D-Bild 10 unter Verwendung der obigen Gleichungen (5) und (6) zu berechnen. Jeder Übergang des besten Pfads definiert eine Übergangsbildursprungsposition. Jedoch sind nicht alle diese Bildpositionen im 2D-Bild 10 von Interesse; ein Filterungsschritt identifiziert die Übergänge, die geschätzte Glyphbildursprungspositionen im 2D-Bild 10 angeben (d. h. die Übergänge, die als Attribute von Null verschiedene Zeichenschablonen für Zeichen in dem Glyphprobenzeichensatz enthalten), extrahiert diese Bildursprungspositionen aus allen identifizierten Übergangsbildursprungspositionen und paart diese Bildursprungspositionen mit jeweiligen Zeichenlabeln des Schablonenattributs auf jedem der identifizierten Übergänge.

Die Dekodierung liefert einen Schätzwert der Bildursprungsposition einer Glyphprobe im 2D-Bild 10, liefert aber nicht Informationen über die Ausdehnung oder Größe der Glyphprobe in dem Bild. Die Bildursprungspositionen werden als Schätzwerte von Positionen von Glyphproben in dem Eingabebild betrachtet, weil die Dekodierung nichtperfekte Ergebnisse erzielen kann, wie beispielsweise, wenn eine fehlerhafte Transkription oder ein verrauschtes 2D-Bild 10 einer Eingabe in die Trainingsprozedur ist.

Der Zeichenschablonenkonstruktionsprozess 270 (Fig. 11) wurde als neuartige Schablonenkonstruktionstechnik 400 in Fig. 13 implementiert und erzeugt einen Satz trainierter, mit Labeln versehener Zeichenschablonen ohne vorherige Segmentierung der Trainingsdaten in isolierte Glyphproben und ohne die Identifizierung von Bounding- Boxen für die Proben. Die Schablonenkonstruktionstechnik 400 identifiziert jede Glyphprobe in den Trainingsdaten unter Verwendung nur der x,y-Koordinatenposition in der 2D-Bildquelle von Glyphs 10, die eine Bildursprungsposition angibt, und des Labels, das das Zeichen identifiziert, das von der an der jeweiligen Bildursprungsposition gelegenen Glyphprobe dargestellt wird.

Unter Bezugnahme auf Fig. 21 besteht der erste Schritt bei der Schablonenkonstruktion darin, einen Schablonenbildbereich in Schritt 410 zur Speicherung jeder aus den Trainingsdaten zu erzeugenden binären Zeichenschablone zu erzeugen. Jede Pixelposition in jedem Schablonenbildbereich gibt anfänglich einen Hintergrundpixelfarbwert an. Im Prinzip erstreckt sich der Schablonenbildbereich für jedes Zeichen über eine vollständige Bildebene, die in allen Richtungen unbeschränkt ist. Jedoch ist die Grundlage einer Schablone typischerweise auf einen relativ schmalen Bereich lokalisiert, der den Ursprungspixelort der Schablone umgibt, so dass der Schablonenbildbereich als irgendein beschränkter Bildbereich ausgewählt wird, der kleiner als die gesamte Bildebene jedoch groß genug ist, um die gesamte Grundlage einer Schablone zu enthalten. Fig. 22 verdeutlicht einen beispielhaften Schablonenbildbereich 502, der der Annahme unterliegt, dass die Grundlage jeder Schablone Qt innerhalb eines Rechtecks einer Höhe H und Breite W liegt. Auf den Schablonenbildbereich 502 wird auch als "Canvas" ("Leinwand") der Schablone Bezug genommen werden. Der Umriss des Schablonencanvas ist grundsätzlich willkürlich und wird typischerweise auf der Grundlage von Annahmen über den Zeichensatz, für den Schablonen trainiert werden, und über die Proben in den Trainingsdaten ausgewählt.

Die Auswahl der vertikalen und horizontalen Größendimensionen des Canvas, d. h. der Canvasparameter der Höhe H und Breite W, erfolgt auf der Grundlage zweier Faktoren, die Gebrauch machen von Informationen über die Zeichen in dem Zeichensatz, der trainiert wird. Zunächst werden H- und W-Canvasparameter ausgewählt, so dass der resultierende erzeugte Bildbereich groß genug ist, um die Grundlage einer einzelnen Schablone vollständig zu enthalten; tatsächlich spiegelt die Auswahl der H- und W- Canvasparameter die Entscheidung wider, dass Pixel außerhalb des Canvas nicht als Teil der Schablone angenommen werden und dass angenommen wird, dass sie die Hintergrundfarbe (weiß) sind. Die Auswahl der H- und W-Canvasparameter wird auch so vollzogen, dass der resultierende erzeugte Bildbereich in dem 2D-Eingabebild groß genug ist, um wenigstens eine einzige Glyphprobe vollständig zu enthalten.

Der Schablonencanvas 502 hat ein ihm zugeordnetes lokales Koordinatensystem, in dem x nach rechts zunimmt, y nach unten zunimmt und der Ursprung 506 des Koordinatensystems bei (x, -w) bezogen auf die untere linke Ecke 508 des Canvas 502 liegt; somit hat die untere linke Ecke 508 des Canvas 502 Koordinaten bei (-x, 'v) bezogen auf das lokale Koordinatensystem, wobei 0 ≤ χ < W und 0 ≤ ψ < H. Das Canvasrechteck 502 ist mit C benannt, so dass

C = [-χ, -χ + W - 1] · [ψ -H + 1, ψ] (1)

gilt. Die Canvasparameter H, W, χ und ψ brauchen nicht für alle Schablonen vereinheitlicht zu sein und können um die bestimmte Zeichenschablone, die gespeichert wird, abweichen; es ist üblicherweise bequemer, dieselben Canvasparameter für jede Schablone zu verwenden, die trainiert wird.

Jede Zeichenschablone enthält eine Pixelposition, die als der Ursprung der Schablone ausgewählt worden ist, der als innerhalb des Canvas 502 liegend angenommen wird. Die Schablonenursprungspixelposition ist in Fig. 22 als Schablonenursprung 506 verdeutlicht. Die Auswahl des Schablonenursprungs 506 innerhalb des Canvasrechtecks 502 ist willkürlich und unterliegt dem Zwang bzw. der Beschränkung, dass die im Canvasrechteck 502 zu speichernde Schablone vollständig im Canvasrechteck 502 enthalten sein muss, wenn ihr Ursprung auf den ausgewählten Schablonenursprung 506 gelegt wird. Bei der verdeutlichten Ausgestaltung wurden zufriedenstellende Ergebnisse erzielt, wenn der Schablonenursprung 506 als Pixelposition links und unterhalb einer zentralen Pixelposition im Canvasrechteck 502 ausgewählt worden ist.

In Fig. 21 besteht der nächste Schritt in der Schablonenkonstruktionsprozedur der vorliegenden Erfindung in Schritt 430 darin, einen Probenbildbereich in der 2D- Bildquelle von Glyphs 10 für jede mit Labeln versehene Glyphbildursprungsposition zu bestimmen, die in den Trainingsdaten enthalten ist, die als Ausgabe des oben beschriebenen Netzwerkverschmelzungs- und -dekodierungsprozesses erzeugt worden sind. Der Schablonenbildbereich 502 wird als Muster oder Führung bei der Bestimmung zweier wichtiger Charakteristiken für jeden dieser Probenbildbereiche verwendet: erstens weist der Probenbildbereich im 2D-Bild 10 für jede mit Labeln versehene Glyphbildursprungsposition in den Trainingsdaten vertikale und horizontale Größendimensionen auf, die mit den vertikalen und horizontalen Größendimensionen des Canvasrechtecks 502 (den H- und W-Canvasparametern) identisch sind; zweitens ist die Glyphbildursprungsposition der Glyphprobe in dem Probenbildbereich an einer Pixelposition gelegen, die mit der Pixelposition im Canvasrechteck 502 übereinstimmt oder mit ihr jeweils gepaart ist, die als Schablonenursprungsposition 506 ausgewählt worden ist. Das Ergebnis der Identifizierung der Probenbildbereiche auf diese Weise besteht in der Produktion einer Kollektion von Probenbildbereichen im 2D-Bild 10 für jedes einzelne Zeichen, das durch die Glyphlabel identifiziert wird, die den Glyphbildursprungspositionen in den Trainingsdaten zugeordnet sind.

Fig. 23 verdeutlicht drei Probenbildbereiche 80, 82 und 84, die für Glyphbildursprungspositionen 85, 87 und 89 im Bildbereich 18 des 2D-Bildes 10 identifiziert worden sind, von denen jedes ein Glyphlabel hat, das das Zeichen "r" angibt. Jeder Probenbildbereich hat dieselbe Höhe H und Breite W des Canvasrechtecks 502, was durch die H- und W-Benennung am Rand des Probenbildbereichs 84 gezeigt ist. Jeder Probenbildbereich hat ein lokales Koordinatensystem mit an der Glyphbildursprungsposition ausgerichtetem Ursprung, wie dies in Fig. 23 durch den Ursprung 85 des repräsentativen Probenbildbereichs 80 verdeutlicht ist. Die Glyphbildursprungspositionen 85, 87 und 89 liegen an Pixelpositionen in den Probenbildbereichen 80, 82 und 84, die x- und y-Verschiebungen von den jeweiligen Ecken links unten der Probenbildbereiche aufweisen, die mit den x- und y- Verschiebungen des Schablonenursprungs 506 von der Ecke 508 links unten des Schablonericanvasrechtecks 502 identisch sind.

Die Identifizierung des Probenbildbereichs für eine mit Labeln versehene Glyphursprungsposition kann wie folgt zusammengefasst werden: Wenn der Vektor z = (xi, yi) eine Glyphursprungsposition innerhalb eines Textbildes ist, wird der entsprechende Glyphprobenbildbereich als der Teil des Textbildes innerhalb des Bereichs definiert, der durch xi - χ ≤ x < xi - χ + W und yi + ψ - H < y < yi + ψ definiert ist. Das bedeutet, dass das Glyphprobenbild für eine Glyphposition dieser Teil des Textbildes innerhalb des Schablonencanvas ist, wenn der Schablonenursprung mit dem Glyphursprung übereinstimmt.

Der Ausdruck "ausgerichtete Probenbildbereiche" wird eingeführt, um die Eigenschaft jedes Probenbildbereichs zu benennen, dass die Bildursprungsposition der Glyphprobe an einer Pixelposition in dem Probenbildbereich liegt, die x- und y-Verschiebungen von der links unten liegenden Ecke des Probenbildbereichs aufweist, die mit den x- und y- Verschiebungen des Schablonenbildursprungs 506 von der links unten liegenden Ecke 508 des Schablonencanvasrechtecks 502 identisch sind. Das Konzept ausgerichteter Probenbildbereiche wird in Fig. 24 verdeutlicht, die Probenbildbereiche 80, 82 und 84 des 2D-Bildes 10 aus Fig. 23 in Schichten über dem Canvasrechteck 502 gestapelt zeigt, einer über dem anderen. Die jeweiligen Bildursprungspositionen 85, 87 und 89 der Probenbildbereiche 80, 82 und 84 sind untereinander und bezüglich der Schablonenursprungsposition 506 entlang der gestrichelten Linienachse 88 "vertikal" ausgerichtet. Die Ausrichtung von Probenbildbereichen gleicher Größe an jeweiligen Bildursprungspositionen auf diese Weise erzeugt eine räumliche Beziehung, oder Paarung, zwischen jedem jeweiligen Pixelort in jedem der Probenbildbereiche bezogen auf das lokale Koordinatensystem des Probenbildbereichs und erzeugt dieselbe räumliche Beziehung oder Paarung zwischen dem Satz gepaarter Pixelorte in der Kollektion von Probenbildbereichen und einer Pixelposition im Canvasrechteck 502 bezogen auf das Schablonenkoordinatensystem. Jeder Satz von Pixeln in ausgerichteten Probenbildbereichen, die auf diese Weise im Bezug stehen, wird als "jeweils gepaarte Pixel" oder "ausgerichtete Pixel" bezeichnet.

Alle Probenbildbereiche, die im 2D-Bild 10 für ein bestimmtes Zeichen im Zeichensatz identifiziert worden sind, für das Schablonen trainiert werden, werden als eine "Kollektion" von Probenbildbereichen bezeichnet. In der verdeutlichten Implementierung wird die Kollektion der Probenbildbereiche in einer separaten Datenstruktur von Probenbildbereichen dargestellt, die untereinander und bezogen auf den Schablonenbildbereich 502 an der Bildursprungsposition ausgerichtet sind. Die Fig. 25 verdeutlicht die Datenstruktur 90, die die Kollektion von Probenbildbereichen für das Zeichen "a" in dem gesamten abgetasteten Zeitungsartikel ist, der das vom 2D-Bild 10 dargestellte Bild ist. Die Datenstruktur 90 ist in Fig. 25 in Reihen und Spalten von aneinander angefügten, ausgerichteten Probenbildbereichen gezeigt, die aus dem 2D- Bild 10 gemäß dem vom Canvasrechteck 502 bereitgestellten Muster abgeschnitten worden sind; die Probenbildbereiche sind zu Zwecken der Verdeutlichung mit Rändern gezeigt.

Wird wieder auf Fig. 21 Bezug genommen, so besteht der nächste Schritt in der Schablonenkonstruktionsprozedur der vorliegenden Erfindung im Schritt 450 darin, Vordergrundpixelfarbwerte den Pixeln in jedem Canvasrechteck 502 für jede zu erzeugende Zeichenschablone auf der Basis der Pixelfarbwerte in den Probenbildbereichen zuzuweisen. Die Schablonenkonstruktionsprozedur der vorliegenden Erfindung konstruiert einen Satz von Zeichenschablonen im Wesentlichen gleichzeitig durch Zuweisung einer Farbe zu jedem Pixel in einem Satz von Zeichenschablonen, wobei ein Kollektion von Glyphprobenbildern für jedes dieser Zeichen gegeben ist. Anders als in der herkömmlichen Praxis ist es einem Glyphprobenbild bei der Technik der vorliegenden Erfindung gestattet, Teile benachbarter Glyphs zu enthalten, wie in Fig. 25 gezeigt. Die Schablonenkonstruktionsprozedur der vorliegenden Erfindung stellt während der Konstruktion der Zeichenschablonen effektiv fest, welche der Vordergrundpixel innerhalb eines Glyphprobenbildes zu dem zentralen Glyph (d. h. dem Glyph, dessen Ursprung nach dem Schablonenursprung ausgerichtet ist) und welche zu benachbarten Glyphs gehören.

Die Farbe des Pixels an der Position x der Schablone Qt sei mit qt(x) bezeichnet, wobei t B ein Übergang der Markov-Bildquelle ist. Eine Vordergrundpixeliarbe wird durch einen Bitwert von 1 (eins) und eine Hintergrundpixelfarbe durch einen Bitwert von 0 (null) dargestellt. Das Ziel der Schablonenkonstruktion besteht darin, einen Wert der Größe qt(x) für jeden Übergang t E B und für jedes x E C zuzuweisen, wobei ein Satz von mit Labeln versehenen Glyphbifdursprungspositionen (x1, ta), i = 1... P gegeben ist.

Die Schablonenkonstruktion gemäß der vorliegenden Erfindung basiert auf einem Kriterium maximaler Wahrscheinlichkeit (ML). Die Schablonenkonstruktion unter Verwendung des Kriteriums maximaler Wahrscheinlichkeit schließt die Zuweisung von Werten zu qc(x) ein, um (25) zu maximieren, vorbehaltlich des Schablonendisjunktheitszwangs.

Wenn der Schablonendisjunktheitszwang ignoriert wird, wird die Schablonenkonstruktion unter Verwendung des ML-Kriteriums unkompliziert und besteht in der separaten Maximierung jedes Terms auf der rechten Seiten von Gleichung (2). Da qc(x) E {0, 1 }, lautet die ML-Entscheidungsregel

wobei

St(x; Z) γ z(x+xi(t)) + βNt

Der Grund für die explizite Benennung der Abhängigkeit der Größe St(x; Z) von Z wird in Kürze aus der folgenden Diskussion deutlich. Die Bedingung St(x; Z) > 0 kann als

1/Nt z(x + xi(t)) > -β/γ

mit der folgenden Interpretation geschrieben werden: die linke Seite von (5) ist der Anteil der Pixel am Ort x, die schwarz sind (d. h. Vordergrundpixel), in der Kollektion ausgerichteter Probenbildbereiche für Qt. Somit kann auf St(x; Z) als "ausgerichtete Pixelzahl (-Score)" oder "Schablonenbeitragsmaß" am Ort x für die Schablone Qt Bezug genommen werden. Die ML-Entscheidungsregel (3) schreibt vor, dass der Schablonenpixel bei x schwarz sein sollte, wenn der Anteil schwarzer Pixel am Ort x in den ausgerichteten Probenbildbereichen einen Schwellenwert überschreitet. Wenn der Schablonendisjunktheitszwang ignoriert wird, kann jede ML-Schablone einfach unabhängig durch Mittelwertbildung und Schwellenwertbehandlung der Kollektion ausgerichteter Probenbildbereiche für die Schablone pixelweise berechnet werden.

Fig. 26 zeigt drei Schablonen 94, 96 und 98, die aus einem Satz von Schablonen ausgewählt und aus Kollektionen von Probenbildbereichen für die Zeichen "e", "a" bzw. "r" unter Verwendung der Entscheidungsregel (3) ohne Beachtung des Schablonendisjunktheitszwang konstruiert worden sind. Die verwendeten Probenbildbereiche waren denen von Fig. 25 ähnlich und wurden aus dem abgetasteten Bild einer Zeitungsspalte ähnlich dem 2D-Bild (10) extrahiert. Es ist ersichtlich, dass die Schablonen 94, 96 und 98 deutlich die "korrekten" Schablonenbilder 93, 95 und 97 enthalten, ausgerichtet an dem Ursprung jeden Canvasrechtecks (mit "±" angegeben). Jedoch ist auch ersichtlich, dass jeder Schablonencanvas schwarze Pixel enthält, die deutlich nicht zu der Schablone gehören. Diese zusätzlichen schwarzen Pixel treten in den Schablonen auf, wenn die Mittelwertsbildungs- und Schwellenwertbehandlungsvorgänge der Entscheidungsregel (3) an benachbarten Glyphs in jedem der Probenbildbereiche in der Kollektion für eine Schablone durchführt werden. Die zusätzlichen Pixel treten deutlich als Ergebnis der Verwendung von Probenbildbereichen auf, die mehrere Glyphs enthalten, im Gegensatz zu einem einzelnen, isolierten Glyph. Wenn die Probenbildbereiche nur den zentralen Glyph, der von Interesse ist, enthalten hätten, wie dies z. B. bei herkömmlichen Schablonenkonstruktionstechniken erforderlich ist, würden die zusätzlichen Pixel fehlen.

Die Maximierung der Gleichung (2) vorbehaltlich des Schablonendisjunktheitszwangs ist ein bezüglich der Berechnung schwieriges Problem im formalen Sinn der NP- Vollständigkeit. Eher als die Verwendung eines exponentiellen Algorithmus zur exakten Lösung des beschränkten ML-Schablonenkonstruktionsproblems liefert die Schablonenkonstruktionstechnik der vorliegenden Erfindung eine approximative aber effektive Lösung, die Schablonen erzeugt, die im Wesentlichen den Schablonendisjunktheitszwang beachten. Diese Lösung wird in Form eines Flussdiagramms in Fig. 27 gezeigt, wobei die Details von Schritt 450 in Fig. 21 verdeutlicht werden.

Eher als die Anwendung von Gleichung (3) unabhängig auf jeden in einer einzelnen Schablone enthaltenen Schablonenpixel auf einer pixelweisen Grundlage wird jedem Schablonenpixel in jeder Schablone, für die St(x; Z) > 0 gilt, in einer sequentiellen Reihenfolge ein Wert von 1 zugewiesen, wodurch zugewiesene Schablonenpixel erzeugt werden. Nach jeder solcher Zuweisung wird das betrachtete Bild Z - d. h. die aus der 2D-Bildquelle von Glyphproben in der verdeutlichten Ausgestaltung abgeschnittenen Probenbildbereiche - durch Setzen aller ausgerichteten Probenpixel auf Null (0) an Orten modifiziert, die mit dem neuzugewiesenen Schablonenpixel gepaart sind oder übereinstimmen. Es werde beispielsweise angenommen, dass der Schablonenpixel qs(w) = 1 gerade zugewiesen worden ist. Dann werden die Pixel von Z den Orten w + xi(s), i = 1... NS auf 0 gesetzt, bevor die nächste Schablonenpixelzuweisung an einen verbleibenden, nicht zugewiesenen Schablonenpixel erfolgt. Die Wirkung des Setzens von Probenpixeln in dem betrachteten Bild auf Null, nachdem eine übereinstimmende Schablonenzuweisung durchgeführt worden ist, was als "Löschen von Pixeln von Z" bezeichnet werden kann, besteht in der Reduktion des Wertes von St(x; Z) für nachfolgende Berechnungen von St(x; Z) für überlappende Schablonenpixel, die noch nicht auf 1 gesetzt worden sind, wodurch die Wahrscheinlichkeit reduziert wird, dass die überlappenden Pixel nachfolgend auf 1 gesetzt werden. Die sequentielle Zuweisung setzt sich so fange fort, wie Sc(x; Z) > 0 für irgendeinen nicht zugewiesenen Schablonenpixel gilt. Das Nettoergebnis der Schablonenkonstruktionstechnik der vorliegenden Erfindung besteht in der gleichzeitigen Erzeugung eines vollständigen Satzes von trainierten Zeichenschablonen, wobei keine einzige Schablone vollständig ist, bis kein positives St(x; Z) übrigbleibt.

Es wird auf Fig. 27 Bezug genommen. Nach der Initialisierung von Pixelzahlen (Scores) oder Schablonenbeitragsmaßen St(x; Z), die jeder Pixetposition in jedem Schablonencanvas zugeordnet sind, auf irgendeinen Wert größer gleich Null in Schritt 452 wird in Schritt 456 die Größe St(x; Z) für jeden nichtzugewiesenen Schablonenpixel in jeder Schablone mit einer gegenwärtig positiven Pixelzahl berechnet, wobei die jeweils gepaarten ausgerichteten Probenpixelpositionen in der Kollektion ausgerichteter Probenbildbereiche für diese Schablone verwendet werden. Die Pixelzahlen werden dann in Schritt 460 überprüft und, wenn irgendeine der berechneten Pixelzahlen größer als Null ist, fährt die Prozedur mit Schritt 470 fort, wo in irgendeiner Schablone der Schablonenpixel mit der höchsten positiven Pixelzahl ausgewählt und ein Vordergrundfarbwert diesem ausgewählten Schablonenpixel zugewiesen wird. Die Farbwerte der ausgerichteten Pixel in der Kollektion ausgerichteter Probenbildbereiche, die mit dem ausgewählten Schablonenpixel gepaart sind, werden dann auf Null (d. h. auf den Hintergrundfarbwert) in Schritt 480 gesetzt. Die Verarbeitung kehrt dann zu Schritt 456 zurück, wo Pixelzahlen wieder für verbleibende, nicht zugewiesene Schablonenpixel berechnet werden.

Fig. 28 zeigt die Ergebnisse der Anwendung des Schablonenpixelfarbzuweisungsalgorithmus auf dieselben Glyphprobenbilddaten, die zur Erzeugung der in Fig. 26 gezeigten Schablonen verwendet wurden. Der Satz von Schablonen 510 in Fig. 28 ist angeordnet in der Reihenfolge "Leerzeichen", Kleinbuchstaben, Großbuchstaben, Ziffern und Satzzeichen. Wenn ein Zeichen in dem Eingabebild nicht vorkommt, wird seine Schablone als ausgefülltes schwarzes Quadrat angegeben. Verglichen mit Fig. 26 enthalten die Schablonen 510 in Fig. 28 deutlich weniger zusätzliche schwarze Pixel, was die Wirkung des "Z-Pixellöschungs"-Schritts des Algorithmus widerspiegelt. Insbesondere wurden die Schablonen 516, 514 und 518, die die Zeichen "e", "a" bzw. "r" darstellen, zum Zwecke des Vergleiches mit den Schablonen 94, 96 und 98 von Fig. 26 hervorgehoben. Wie in (27) angemerkt, erfordert die Berechnung von Pixelzahlen die Verwendung der Faktoren γ und β, wobei γ > 0 und β < 0 ist. In der verdeutlichten Ausgestaltung, die die in Fig. 26 gezeigten Schablonen erzeugt hat, waren die für diese Faktoren verwendeten Werte 2,237 bzw. -1,629 entsprechend den Kanalrauschparametern α&sub0; = 0,9 und α&sub1; = 0,51.

Jeder Übergang t zwischen Knoten in dem Finitzustandsbildmodellnetzwerk hat das zugeordnete Vierertupel von Attributen, das in Fig. 14 in der Reihenfolge [at], (Δt), mt, Qt gezeigt ist. Wenn eine Schablone Qi einem Übergang t zugeordnet ist, wie etwa die in Fig. 14 mit den F-Übergängen t verdeutlichten, ist die horizontale Verschiebung Δi, die diesem Übergang zugeordnet ist, die Zeichensatzbreite wti der Schablone. Die Zeichensatzbreite ist die Vektorverschiebung von der Glyphursprungsposition zu dem Punkt, an dem der Ursprung des nächsten Glyphs normalerweise liegt, wenn aufeinanderfolgende Zeichen eines Wortes einer Bildverarbeitung unterzogen werden. Die Zeichensatzbreite ist eine der Fontmetriken, die zur vollständigen Beschreibung einer Zeichenschablone notwendig sind, die durch das Sidebearing-Modell der Buchstabenformumrissbeschreibung und -positionierung modelliert wird. Folglich ist es zusätzlich zur Konstruktion der Zeichenschablonen gemäß der Schablonenkonstruktionsprozedur 400 auch notwendig, die Zeichensatzbreiten für die konstruierten Schablonen zu bestimmen.

Die Zeichensatzbreite jeder binären Schablone wird unter Verwendung der Kollektion von Probenbildbereichen bestimmt, die für diese Schablone identifiziert sind. Da das Identifizieren von Glyphbildursprungspositionen von Glyphproben in dem 2D- Eingabebild ein Schätzprozess ist, ist es wahrscheinlich, dass wenigstens einige der identifizierten Proben ungenaue Bildursprungspositionen identifiziert haben werden. Jedoch kann die Satzbreite jeder Glyphprobe, die in einem Probenbildbereich enthalten ist, aus der Kenntnis der Bildursprungsposition der nächsten benachbarten Glyphprobe in dem 2D-Bild berechnet werden. Folglich enthält die Berechnung einer Satzbreite für eine Schablone die Berechnung der Satzbreite für jede Probe, die für diese Schablone identifiziert ist, unter Verwendung der Kollektion von Probenbildbereichen und der Verschiebung von jeder Bildursprungsposition in jeder Probe zu der Bildursprungsposition des nächsten benachbarten Glyphs in dem 2D-Bild. Die Kollektion berechneter Satzbreiten für die Glyphproben wird dann verwendet, um zu einer Satzbreite für die Schablone zu gelangen; beispielsweise kann der Durchschnitts- oder Mittelwert der Satzbreite für alle Proben als die Satzbreite der Schablone bestimmt werden. Oder aber, die minimale Satzbreite, die unter Verwendung der Proben berechnet worden ist, kann als die Satzbreite der Schablone verwendet werden.

Fig. 13 zeigt diesen Schritt der Bestimmung der Zeichensatzbreiten als Schritt 490 nach der Schablonenkonstruktionsprozedur 400. Jedoch wird, wie gerade beschrieben, in der verdeutlichten Implementierung die Satzbreite jeder Schablone unter Verwendung der Kollektionen von Probenbildbereichen und nicht aus der Verwendung der konstruierten Schablonen bestimmt. Folglich hängt die Bestimmung der Zeichensatzbreiten nicht von der Beendigung der Schablonenkonstruktion ab und kann zu jedem Zeitpunkt stattfinden, nachdem die Dekodierungs- und Zurückverfolgungsschritte die mit Labeln versehenen Glyphbildursprungspositionen für die Glyphproben in dem 2D-Eingabebild erzeugen. Zusätzlich zeigt Fig. 13 diesen Schritt als in einer iterativen Verarbeitungsschleife enthalten, die die Dekodierungs-, Zurückverfolgungs- und Schablonenkonstruktionsschritte 330, 380 bzw. 400 wiederholt. Das bevorzugte Verfahren zur Berechnung der Satzbreite besteht darin, die minimale Satzbreite aus den für die Kollektion von Probenbildbereichen berechneten Satzbreiten zu bestimmen und dann einen Prozentwert, z. B. 90 Prozent dieses Minimums als die Satzbreite der Schablone zu nehmen, um sicherzustellen, dass die Satzbreiten, die zur Zeichenpositionierung während nachfolgender Iterationen des Dekodierungsprozesses verwendet werden, stets kleiner als die tatsächlichen Satzbreiten werden, die zur Positionierung der Glyphs im eingegebenen 2D-Eingabebild verwendet werden.

Die verdeutlichte Ausgestaltung der Zeichenschablonentrainingstechnik 200 ist von der Grundlage her ein iterativer Prozess, da, wie zuvor angemerkt worden ist, die Bilddekodierung eines betrachteten 2D-Bildes unter Verwendung von 2D- Bildquellenmodellen des in den Fig. 9, 14 und 19 verdeutlichten Typs die Verwendung eines Anfangssatzes von Zeichenschablonen annimmt. Wenn ein Anfangssatz von Schablonen nicht verfügbar ist, wie dies in der Trainingssituation typischerweise vorliegt, enthält die verdeutlichte Ausgestaltung vor dem Dekodierungsschritt 330 eine Verarbeitung zur Erzeugung einer Zeichenschablonendatenstruktur, die einen Anfangssatz von Zeichenschablonen zur Verwendung während der Dekodierung angibt. Jede Schablone in diesem Anfangssatz von Zeichenschablonen kann irgendeinen willkürlichen Pixelinhalt haben, der von praktischem Nutzen durch den Dekodierungsprozess 330 ist, und in der verdeutlichten Ausgestaltung hat jede Schablone den willkürlichen Anfangspixelinhalt eines gefüllten schwarzen rechteckigen Bildes und verfügt nicht über spezifische Pixelinformationen über das Zeichen, das es darstellt. Ist ein solcher Anfangssatz von Schablonen rechteckiger schwarzer Bilder gegeben, kann davon ausgegangen werden, dass die Dekodierungs- und Zurückverfolgungsschritte 330 bzw. 380 verbesserte Schätzwerte von mit Labeln versehenen Glyphbildursprungspositionen von Glyphproben im 2D-Bild 10 mit jeder nachfolgenden Iteration unter Verwendung der Zeichenschablonen erzeugen, die in der vorherigen Iteration konstruiert worden sind.

Die Beendigungsbedingung, die zur Steuerung der Beendigung der Zeichenschablonenkonstruktion verwendet wird, kann heuristisch bestimmt oder eine Funktion eines oder mehrerer Verarbeitungsparameter sein, In der verdeutlichten Ausgestaltung ist die Beendigungsbedingung eine feste Anzahl von Iterationen, die sich erfahrungsgemäß als die Anzahl von Iterationen erwiesen hat, die die Schablonen höchster Qualität erzeugt und nach der nachfolgende beobachtbare Verbesserungen der Schablonen von geringer oder keiner Bedeutung sind. Die Beendigungsbedingung kann auch auf einem Schwellenwert basieren, der in Beziehung zur maximalen Wahrscheinlichkeitszahl steht, die während der Dekodierung berechnet wird.

Die Flexibilität, die darin besteht, dass sowohl das 2D-Bildquellenmodell als auch die Transkription als formale Modelle dargestellt sind und dass das 2D-Bildquellenmodell als eine explizite Eingabe in die Trainingsprozedur dargestellt ist, erweitert das Konzept dessen, was traditionellerweise als der für das Training von Schablonen geeignete Transkriptionstyp angesehen wird - nämlich die wörtliche Transkription - darauf, dass eine breite Vielzahl anderer Nachrichtenstrings eingeschlossen wird. Beispielsweise kann eine Situation auftreten, in der die 2D-Eingabebildquelle von Glyphproben, die zum Training verwendet werden, stets ein Dokument eines Satzes bestimmter Dokumente mit bekannten, festgelegten Transkriptionen ist. Transkriptionsnetzwerke oder Transkriptionsbildnetzwerke, die diese vorbestimmten Transkriptionen modellieren, können für jede dieser spezifischen Transkriptionen vor dem Training erzeugt und gespeichert werden, und was der Benutzer als "Transkription" eingibt, ist tatsächlich ein Name, der die spezifische Transkription identifiziert, die der 2D-Bildquelle von Glyphproben zuzuordnen ist, die beim Training verwendet werden soll.

In einem anderen Beispiel kann auch eine verfügbare Datenstruktur, die Markup-Label oder Tags enthält, die die logische Struktur und Formatierungsinformationen für die Zeichenkodes in einem 2D-Bild angeben, als die eingegebene Transkription verwendet werden, ohne dass der Benutzer die Tags manuell herausziehen und die Datenstruktur in eine wörtliche Transkription umwandeln muss. Wenn diese Markup-Datenstrukturen in Dokumentenaufbewahrungsorten zusammen mit deren Dokumentenbildern verfügbar sind, erlaubt die Trainingstechnik der vorliegenden Erfindung das Training der Zeichenschablonen unter Verwendung irgendeines solchen Dokumentbildes und seiner zugeordneten Tag-Transkription.

Die Verwendung von mit Tags versehenen Transkriptionen bei der Schablonentrainingstechnik der vorliegenden Erfindung erfordert keine funktionellen Modifikationen an den Bildmodellen, die bis jetzt beschrieben worden sind, weil die Anpassung von Tags im Wesentlichen die Behandlung der Nachrichtenstrings in dem Bildquellennetzwerk beinhaltet und die allgemeine Form des in Fig. 9 angegebenen Markov-Bildquellenmodells die unabhängige Spezifizierung des Nachrichtenstrings und der Schablone für jeden Übergang gestattet. Darüber hinaus können die Nachricht und/oder die Schablone aus einem Übergangsattributsatz weggelassen werden. Somit können Tags ohne Modifikation an dem Modelfierungsgerüst (dem Framework) angepasst werden, wie dies unten verdeutlicht werden wird.

Fig. 29 zeigt ein Zeilenbildquellenmodell 770, das einfache Textzeilen, die tiefergelegten Text enthalten, bildlich verarbeitet. Die Übergangswahrscheinlichkeiten wurden aus diesem Modell weggelassen. Die durch das Modell 770 definierten Zeilenbilder bestehen vollständig aus Glyphs des Zeichens "a" mit verschiedenen Beträgen des Raumes zwischen den Zeichen. Die Zustände und ihre Übergänge im Modell 770 zeigen, dass Glyphs entweder auf der Grundlinie liegen können oder 5 Pixel darunter, um tiefergelegten Text zu simulieren. Aus den im Modell 770 gezeigten Übergangsattributen kann ersehen werden, dass der Zustand n&sub2; und seine Selbstübergänge 777 und 778 nachfolgende Schablonen des Zeichens "a" bildlich verarbeiten, die auf der Hauptgrundlinie ausgerichtet sind, und dass sie Nachrichtenstrings aus "a" erzeugen. Es ist aus dem Verschiebungsvektor beim Übergang 778 auch ersichtlich, dass die Satzbreite von "a" in der horizontalen x- Richtung als 25 gegeben ist. Das Modell 770 erlaubt die Bildverarbeitung von Glyphs auf einer tiefergelegten Grundlinie durch den Übergang vom Zustand n&sub1; auf den Zustand n&sub4;, der als Übergangsattribute eine positive y-Verschiebung von 5, die die gegenwärtige Bildverarbeitungsposition in der Bildebene nach unten bewegt, und den Nachrichtenstring 772 "{", jedoch keine Schablone zeigt. Der Zustand n&sub4; und seine Selbstübergänge 779 und 780 unterwerfen nachfolgende Schablonen des Zeichens "a", die auf einer tiefergelegten Grundlinie ausgerichtet sind, einer Bildverarbeitung und sie erzeugen auch Nachrichtenstrings aus "a". Der Übergang vom Zustand n&sub4; auf den Zustand n&sub3; bringt die gegenwärtige Bildverarbeitungsposition auf die Hauptgrundlinie zurück, wie durch die Verschiebung 776 gezeigt; dieser Übergang besitzt ebenfalls das Nachrichtenstringattribut 774 "}" und keine Schablone. Wegen des Übergangs von n&sub3; auf n&sub1; kann eine Zeile jede Anzahl von tiefergelegten Strings abwechselnd mit auf der Hauptgrundlinie liegenden Strings enthalten. (Da das Modell 770 einen Satz von Bildern modelliert, die Text enthalten, der unterhalb einer Haupttextgrundlinie bildlich verarbeitet wird, werden alle Zweigverschiebungen als zweidimensionale Vektoren spezifiziert. Jedoch ist es einfach zu verifizieren, dass alle vollständigen Pfade durch das Modell 770 eine y-Verschiebung von null haben, d. h. Δyπ = 0, wenn π ein vollständiger Pfad ist. Somit genügt das Modell der Definitionsbedingung, dass es ein Zeilenmodell ist, d. h. jeder vollständige Pfad hat dieselbe y-Verschiebung.)

Fig. 30 zeigt mehrere Beispiele von Zeilenbildern 712, 714 und 716, die in dem Satz von Zeilenbildern enthalten sind, die vom Zeilenbildquellenmodell 770 modelliert worden sind. Zu Zwecken der Verdeutlichung ist die vertikale Verschiebung der tiefergelegten Textstellen in Fig. 30 stark übertrieben dargestellt und die gestrichelten Linien, wie etwa Linie 718, werden gezeigt, um die Haupttextgrundlinie zu verdeutlichen. In seinem Dekodierungsmodus dekodiert das Modell 770 die Zeilenbilder 712, 714 und 716 als die Nachrichtenstrings (Transkriptionen) "aaa{aa}a", "a{a}aa{a}a" bzw. "a{a}a". Oder umgekehrt: die Zeilenbilder 712, 714 und 716 könnten als Zeilenbilder betrachtet werden, die das Modell 770 in seinem Bildsynthesemodus erzeugt, wenn die Eingabenachrichtenstrings "aaa{aa}a", "a{a}aa{a}a" bzw. "a{a}a" gegeben sind. Jedenfalls können die wirklichen Nachrichtenstrings "{"und"}" nicht mit Glyphs in irgendeiner der Zeilenbilder 712, 714 und 716 in Fig. 30 visuell gepaart werden, ein Umstand, der durch die fehlenden Schablonen der Übergänge vom Zustand n&sub1; auf den Zustand n&sub4; und vom Zustand n&sub4; auf den Zustand n&sub3; gestützt ist. Wenn die Nachrichtenstrings "{"und"}" im Modell 770 auftreten, geben sie einen wahrnehmbaren Wechsel in der Bildverarbeitung eines oder mehrerer Glyphs in einem durch das Modell erzeugten Bild an. Die Nachrichtenstrings "{"und"}" funktionieren somit als Tags, die Text zwischen ihnen als einen Formatierungswechsel oder einen logischen Wechsel bei der Bildverarbeitung aufweisend markieren gegenüber Text, der ihnen vorangeht oder folgt; im vorliegenden Fall markieren sie Text, der als tiefergelegter Text interpretiert und gesetzt werden soll.

Das Verschmelzen eines Bildquellenmodells, das Tag-Nachrichtenstrings mit einem mit Tags versehenen Transkriptionsnetzwerk anpasst, fährt bei der Verschmelzung von 2D- Netzwerken und Zeilennetzwerken in derselben Weise wie vorher beschrieben fort. Die funktionalen Eigenschaften des verschmolzenen Tag-Transkriptionsbildnetzwerkes sind dieselben wie die zuvor im Zusammenhang mit der 2D-Implementierung dargelegten (auf die dort als Netzwerkeigenschaften (a) und (b) Bezug genommen worden ist). Die Netzwerkverschmelzung erzeugt ein modifiziertes Bildquellenmodell, das auf die Erzeugung nur von Transkriptionen aus dem Satz von Transkriptionen beschränkt ist, die durch das Tag-Transkriptionsnetzwerk definiert sind. Der Verschmelzungsprozess folgt den drei Schritten für das Hinzufügen von Übergängen auf die Zustände in dem Zeilenbildmodell, die oben beschrieben worden sind.

Die Verwendung einer mit Tags versehenen Transkription als Eingabequelle von Glyphlabeln für die Trainingsdaten, die für die Schablonentrainingsprozedur erzeugt worden sind, wird vollständig dadurch gehandhabt, wie das Bild und die Transkriptionsmodelle definiert und verschmolzen werden, und sie erfordert keine Modifikationen des Dekodierungsprozesses oder der Glyphbildursprungspositionsextraktion aus dem besten Pfad; der Rest der Schablonentrainingsprozedur fährt wie oben beschrieben fort unter Verwendung des Tag-Transkripitonsbildnetzwerks, um die Glyphbildursprungspositionen der Glyphs, die in einem eingegebenen Zeilenbild enthalten sind, für die Schablonenkonstruktionsprozedur bereitzustellen.


Anspruch[de]

1. Verfahren zum Trainieren eines Satzes (20) von Zeichenschablonen (22, 24, 26) zur Verwendung in einem Erkennungssystem; wobei jede Zeichenschablone ein jeweiliges Zeichen einer Vielzahl von Zeichen in einem Zeichensatz repräsentiert und durch eine Zeichenlabel identifiziert wird, das das jeweilige Zeichen angibt; wobei das Verfahren zum Betreiben einer Maschine ist, die einen Prozessor und eine damit verbundene Speichereinrichtung enthält, wobei die Speichereinrichtung Instruktionsdaten speichert, die der Prozessor ausführt; wobei das Verfahren die folgenden Schritte umfasst:

Empfangen eines zweidimensionalen Quellenbildes (10, 50), das eine Vielzahl von Glyphproben (12, 14) enthält; wobei jede Glyphprobe ein Bildbeispiel eines jeweiligen Zeichens der Vielzahl von Zeichen in dem Zeichensatz ist; wobei das Quellenbild eine vertikale Dimensionsgröße hat, die größer als die Höhe einer einzelnen Zeile von Glyphproben ist;

Empfangen einer Transkriptionsdatenstruktur (40, 60, 70), die dem Quellenbild zugeordnet ist und eine geordnete Anordnung von Transkriptionslabeln (42, 44, 46, 47, 48, 62, 64, 66, 68, 72) enthält;

Bestimmen (220) einer Glyphpixelposition jeder Glyphprobe;

Erzeugen (250) eines Glyphlabels, das ein jeweiliges Zeichen in dem Zeichensatz angibt, für jede Glyphprobe und Paaren (250) derselben mit der jeweiligen Glyphpixelposition; und

Erzeugen (270, 400) des Satzes von Zeichenschablonen unter Verwendung der Paare von Glyphpixelpositionen und Glyphlabeln und unter Verwendung der Glyphproben an den Glyphpixelpositionen als Trainingsdatenproben für eine jeweilige Zeichenschablone,

dadurch gekennzeichnet, dass

die Speichereinrichtung weiterhin ein zweidimensionales Bildquellenmodell (820, 830, 770) zum Modellieren einer räumlichen Bildstruktur eines Satzes zweidimensionaler Bilder als eine Grammatik speichert; wobei das Bildquellenmodell räumliche Positionierungsdaten zum Modellieren einer räumlichen Positionierung einer Vielzahl von in einem Bild enthaltenen Glyphs und Mappingdaten zum Abbilden eines jeweiligen Glyphs auf ein das Zeichen in dem Zeichensatz angebendes Glyphlabel enthält; wobei das Quellenbild ein Bild des Satzes von Bildern ist;

der Schritt des Bestimmens der Glyphpixelpositionen die räumlichen Positionierungsdaten verwendet; und

der Schritt des Erzeugens und Paarens der Glyphlabel die Mappingdaten und die Transkriptionsdatenstruktur verwendet.

2. Verfahren nach Anspruch 1, weiterhin dadurch gekennzeichnet, dass jede Glyphpixelposition eine einzelne Ursprungsposition der jeweiligen Glyphprobe ist und der Schritt des Erzeugens (270, 400) des Satzes von Zeichenschablonen die folgenden Schritte enthält:

Bestimmen (430) von Bereichen in dem Quellenbild, wobei jeder Bereich eine Vielzahl von Probenpixelpositionen enthält und groß genug ist, so dass zwei der Probenpixelpositionen die Ursprungspositionen zweier Glyphproben sind; und

Zuweisen (450) von Pixelfarbwerten zu Schablonenpixelpositionen, die in jeweiligen Zeichenschablonen enthalten sind, unter Verwendung von durch die Probenpixelpositionen angegebenen Pixelfarbwerten, auf der Grundlage von Kriterien, die bestimmen, welche Probenpixelpositionen in welchen Bereichen verwendet werden, um einen Pixelfarbwert für eine Schablonenpixelposition zu bestimmen, so dass alle Zeichenschablonen ein Zeichenschablonenmodell beachten, wonach zwei benachbarte Zeichenschablonen, die voneinander um eine Zeichensatzbreite verschoben sind, überlappende Bounding-Boxen aber im Wesentlichen nichtüberlappende Vordergrundpixel haben können, wobei jede Bounding-Box eine Zeichenschablone vollständig enthält.

3. Verfahren nach Anspruch 1 oder 2, weiterhin dadurch gekennzeichnet, dass die Transkriptionsdatenstruktur eine Tag-Transkriptionsdatenstruktur ist, die wenigstens ein nichtwörtliches Tag-Transkriptionslabel enthält, das wenigstens einen Zeichenkode angibt, der ein Zeichen repräsentiert, mit dem keine Glyphprobe in dem Quellenbild durch visuelles Betrachten desselben gepaart werden kann; wobei der wenigstens eine Zeichenkode Markup-Informationen über das Quellenbild angibt; wobei die Markup-Informationen bei ihrer Interpretierung durch einen Dokumentenverarbeitungsvorgang wenigstens ein in dem Quellenbild enthaltenes Displaymerkmal erzeugen können, das als visuelle Formatierungscharakteristik wahrnehmbar ist; und wobei der Schritt des Erzeugens (250) des Glyphlabels die räumlichen Positionierungsdaten über die Vielzahl von Glyphproben verwendet, um wenigstens eine Glyphprobe zu identifizieren, die mit der Tag-Datenstruktur in Beziehung steht, und wobei der Schritt des Paarens (250) die Tag-Datenstruktur zum Paaren verwendet.

4. Verfahren zum Trainieren eines Satzes von Zeichenschablonen zur Verwendung in einem Erkennungssystem; wobei jede Zeichenschablone ein jeweiliges Zeichen einer Vielzahl von Zeichen in einem Zeichensatz repräsentiert; wobei das Verfahren zum Betreiben einer Maschine ist, die einen Prozessor und eine damit verbundene Speichereinrichtung enthält; wobei die Speichereinrichtung Instruktionsdaten speichert, die der Prozessor ausführt; wobei das Verfahren die folgenden Schritte umfasst:

Empfangen und Speichern (290) eines zweidimensionalen Quellenbildes, das eine Vielzahl von Glyphproben enthält; wobei jede Glyphprobe ein Bildbeispiel eines jeweiligen Zeichens der Vielzahl von Zeichen in dem Zeichensatz ist; wobei das Quellenbild eine vertikale Dimensionsgröße hat, die größer als die Höhe einer einzelnen Zeile von Glyphproben ist;

Empfangen und Speichern (292) eines Finitzustandstranskriptionsnetzwerks (800, 850, 852), das dem Quellenbild zugeordnet ist und eine geordnete Anordnung von Transkriptionslabeln als wenigstens einen Transkriptionspfad durch das Transkriptionsnetzwerk enthält;

Dekodieren (330) des Quellenbildes;

Erlangen (380) einer Position und eines damit gepaarten Glyphlabels für jede Glyphprobe in dem Quellenbild; und

Erzeugen (400) des Satzes von Zeichenschablonen unter Verwendung des Quellenbildes und der Paare von Positionen und Glyphlabeln und unter Verwendung der Glyphproben, die durch die Glyphlabel identifiziert werden, zum Training der Zeichenschablonen,

dadurch gekennzeichnet, dass

der Speicher weiterhin ein zweidimensionales stochastisches Finitzustandsbildquellennetzwerk (830) zum Modellieren einer räumlichen Bildstruktur eines Satzes zweidimensionaler Bilder als eine Grammatik speichert, wobei jedes Bild eine Vielzahl von Glyphs enthält; wobei ein erstes Bild des Satzes von Bildern als wenigstens ein Pfad durch das Bildquellennetzwerk modelliert wird, der ein ideales Bild angibt, das zu der räumlichen Bildstruktur des ersten Bildes konsistent ist; wobei der wenigstens eine Pfad Pfaddatenelemente angibt, die ihm zugeordnet sind; wobei die Pfaddatenelemente Positionen und damit gepaarte Glyphlabel jeweiliger Glyphs der Vielzahl von in dem ersten Bild enthaltenen Glyphs angeben; wobei das Quellenbild ein Bild des Satzes von Bildern ist;

das Verfahren weiterhin einen Schritt des Verschmelzens (300) des Bildquellennetzwerkes mit dem Transkriptionsnetzwerk umfasst, um ein Transkriptionsbildnetzwerk (870, 872) zu erzeugen, wobei, wenn die Transkription dem ersten Bild zugeordnet ist, das Transkriptionsbildnetzwerk das erste Bild als wenigstens einen vollständigen Transkriptionsbildpfad durch das Transkriptionbildnetzwerk modelliert, der ein ideales Bild angibt, das zu der räumlichen Bildstruktur des ersten Bildes konsistent ist; wobei der wenigstens eine vollständige Transkriptionsbildpfad die Pfaddatenelemente und eine Abfolge von Nachrichtenstrings angibt, die zu der geordneten Anordnung der Transkriptionslabel konsistent ist;

der Schritt des Decodierens das Transkriptionsbildnetzwerk verwendet, um wenigstens einen vollständigen Transkriptionsbildpfad zu erzeugen, der ein ideales Bild angibt, das zu der räumlichen Bildstruktur des Quellenbildes konsistent ist; und

der Schritt des Erlangens die Pfaddatenelemente verwendet, die dem wenigstens einen vollständigen Transkriptionsbildpfad zugeordnet sind.

5. Verfahren nach Anspruch 4, weiterhin dadurch gekennzeichnet, dass

jede Zeichenschablone auf einem Sidebearing-Modell der Zeichenbildpositionierung zweier benachbarter Zeichenbilder basiert, die voneinander um eine Zeichensatzbreite verschoben sind; wobei das Sidebearing- Modell erfordert, dass die Zeichenbilder im Wesentlichen nichtüberlappende Vordergrundpixel haben, wenn zwei rechteckige Bounding-Boxen, die jeweils eines von zwei Zeichenbildern enthalten, überlappen; und wobei der Schritt des Erzeugens (400) des Satzes von Zeichenschablonen den Schritt des Bestimmens (490), für jede Zeichenschablone, einer Zeichensatzbreite derselben unter Verwendung der Paare von Positionen und Glyphlabeln enthält; oder dass

jede der Zeichenschablonen auf einem segmentierungsbasierten Modell der Zeichenbildpositionierung zweier benachbarter Zeichenbilder basiert, von denen jedes vollständig in einer von zwei im Wesentlichen nichtüberlappenden rechteckigen Bounding-Boxen enthalten sein kann.

6. Verfahren nach Anspruch 4, weiterhin dadurch gekennzeichnet, dass das Transkriptionsnetzwerk wenigstens ein Paar von Transkriptionslabeln enthält, die wenigstens erste und zweite abwechselnde Nachrichtenstrings für einen einzelnen Bildteil des Quellenbildes angeben; wobei das Transkriptionsnetzwerk eine Reihe von Transkriptionsknoten und eine Abfolge von Übergängen zwischen Paaren der Knoten enthält; wobei jeder Übergang ein ihm zugeordnetes Transkriptionslabel hat; wobei das Transkriptionsnetzwerk das wenigstens eine Paar von Transkriptionslabeln als wenigstens erste und zweite abwechselnde Abfolgen von Übergängen zwischen einem der Paare der Knoten modelliert; wobei jede der wenigstens ersten und zweiten abwechselnden Sequenzen von Übergängen einen der wenigstens ersten und zweiten abwechselnden, ihr zugeordneten Nachrichtenstrings hat; oder dass

das Transkriptionsnetzwerk eine Tag-Transkription angibt, die wenigstens ein nichtwörtliches Tag-Transkriptionslabel enthält, das wenigstens einen Zeichenkode angibt, der ein Zeichen repräsentiert, mit dem ein jeweiliges Glyph in dem Quellenbild nicht durch visuelle Betrachtung desselben gepaart werden kann; wobei der wenigstens eine Zeichenkode Markup-Informationen über das Quellenbild angibt; wobei die Markup-Informationen bei ihrer Interpretation durch einen Dokumentenverarbeitungsvorgang wenigstens ein in dem Quellenbild enthaltenes Displaymerkmal erzeugen können, das als eine visuelle Formatierungscharakteristik wahrnehmbar ist; und wobei der Schritt des Verschmelzens (300) den Schritt des Bezeichnens der Transkriptionslabel als Nachrichtenstrings enthält, die in dem Transkriptionsbildnetzwerk enthalten sind; wobei das Tag-Transkriptionslabel als ein Nachrichtenstring bezeichnet ist, so dass das Transkriptionsbildnetzwerk eine Beziehung zwischen dem Tag- Transkriptionslabel und wenigstens einem Glyph modelliert; oder dass

der wenigstens eine vollständige Transkriptionsbildpfad durch eine Abfolge von Übergängen zwischen Knoten, die in dem Transkriptionsbildnetzwerk enthalten sind, definiert ist; wobei die ihm zugeordneten Pfaddatenelemente jedem Übergang zugeordnet sind und einen Nachrichtenstring, eine Zeichenschablone und eine Bildverschiebung enthalten; und wobei der Schritt des Erlangens (380) den Schritt des Bestimmens, für jeweilige Übergänge mit ihnen zugeordneten, von Null verschiedenen Zeichenschablonen, der Positionen jeweiliger Glyphs durch die Verwendung der Bildverschiebungen, die den jeweiligen Übergängen zugeordnet sind, und weiterhin des Bestimmens des mit jeder jeweiligen Position gepaarten Glyphlabels unter Verwendung eines Zeichenlabels enthält, das durch die von Null verschiedene Zeichenschablone angegeben ist, die dem jeweiligen Übergang zugeordnet ist; wobei das Zeichenlabel ein Zeichen in dem Zeichensatz angibt.

7. Verfahren nach Anspruch 4, weiterhin dadurch gekennzeichnet, dass der Schritt des Dekodierens (330) die folgenden Schritte enthält:

Durchführen (334, 338, 340) eines auf dynamischer Programmierung basierenden Dekodierungsvorgangs, um an jedem einer Vielzahl von Gitterknoten in einem Dekodierungsgitter, das das Transkriptionsnetzwerk repräsentiert, einen optimalen Score zu berechnen; wobei der Dekodierungsvorgang für jeden Gitterknoten ein optimierendes Übergangsidentifikationsdatenelement als Ergebnis der Berechnung des optimalen Scores erzeugt, das Element speichert und einen einer Vielzahl möglicher Übergänge in einen jeweiligen Gitterknoten angibt, der den Score für den jeweiligen Gitterknoten optimiert; und

Zurückverfolgen (380), um eine Abfolge von Übergängen wiederzugewinnen, die einen Dekodierungsgitterpfad angibt; wobei der Zurückverfolgungsvorgang mit einem Endgitterknoten beginnt und mit einem ersten Gitterknoten in dem Dekodierungsgitterpfad endet; wobei die Abfolge von Übergängen unter Verwendung des Datenelements wiedergewonnen wird; wobei der Dekodierungsgitterpfad den wenigstens einen vollständigen Transkriptionsbildpfad durch das Transkriptionsbildnetzwerk angibt.

8. Maschine zum Trainieren eines Satzes von Zeichenschablonen zur Verwendung in einem Erkennungsvorgang, umfassend:

eine erste Signalquelle zum Bereitstellen eines ersten Bildes;

eine Bildeingabeschaltung zum Empfangen des Bildes von der ersten Bildquelle;

eine zweite Signalquelle zum Bereitstellen von Nichtbilddaten;

eine Eingabeschaltung zum Empfangen der Nichtbilddaten von der zweiten Signalquelle;

einen Speicher zum Speichern von Daten, die Instruktionen enthalten, die ein Prozessor ausführen kann; und

den Prozessor zum Empfangen des Bildes von der Bildeingabeschaltung und zum Empfangen der Nichtbilddaten von der Eingabeschaltung und zum Zugreifen auf die in dem Speicher gespeicherten Daten; wobei der Prozessor zum Durchführen der folgenden Schritte bei der Ausführung der Instruktionen eingerichtet ist:

Empfangen eines zweidimensionalen Quellenbildes (10, 50), das eine Vielzahl von Glyphproben enthält, von der Bildeingabeschaltung; wobei die Bildquelle eine vertikale Dimensionsgröße hat, die größer als eine einzelne Zeile von Glyphproben ist; wobei jede Glyphprobe ein Bildbeispiel eines jeweiligen Zeichens einer Vielzahl von Zeichen in dem Zeichensatz ist; wobei der Satz von Zeichenschablonen jeweilige Zeichen der Vielzahl von Zeichen in dem Zeichensatz repräsentiert;

Empfangen einer Transkriptionsdatenstruktur (40, 60, 70), die dem Quellenbild zugeordnet ist und eine geordnete Anordnung von Transkriptionslabeln (42, 44, 46, 47, 48, 62, 64, 66, 68, 72) enthält, von der Eingabeschaltung;

Bestimmen einer Glyphpixelposition für jede Glyphprobe;

Erzeugen eines mit jeder jeweiligen Glyphpixelposition gepaarten Glyphlabels; und

Erzeugen des Satzes von Zeichenschablonen unter Verwendung des Quellenbildes und der Glyphpixelpositionen und der jeweils gepaarten Glyphlabel; wobei jede Zeichenschablone durch eine Zeichenlabel identifiziert ist;

wobei jedes Paar von Glyphpixelpositionen und Glyphlabeln eine Trainingsdatenprobe für eine jeweilige Zeichenschablone identifiziert, wenn das jeweils gepaarte Glyphlabel zu dem jeweiligen Zeichenlabel passt,

dadurch gekennzeichnet, dass

der Speicher weiterhin ein zweidimensionales Bildquellenmodell (820, 830, 770) zum Modellieren einer räumlichen Bildstruktur eines Satzes zweidimensionaler Bilder als eine Grammatik speichert; wobei das Bildquellenmodell räumliche Positionierungsdaten für eine Vielzahl von Glyphs enthält, die in einem ersten Bild auftreten, das in dem Satz von Bildern enthalten ist; wobei das Bildquellenmodell Mappingdaten zum Abbilden einer jeweiligen Glyphprobe, die in dem ersten Bild auftritt, auf ein Glyphlabel angibt, das ein Zeichen in einem Zeichensatz angibt; wobei das Quellenbild in dem Satz von Bildern enthalten ist; und

der Prozessor weiterhin eingerichtet ist, um die räumlichen Positionierungsdaten zur Bestimmung der Glyphpixelpositionen zu verwenden und um die Mappingdaten und die geordnete Anordnung von Transkriptionslabeln zur Erzeugung der gepaarten Glyphlabel zu verwenden.

9. Maschine nach Anspruch 8, weiterhin dadurch gekennzeichnet, dass

die erste Signalquelle eine Abtasteinrichtung ist; wobei die Bildeingabeschaltung eine Abtastschaltung ist, die ein Bild von einem Abtastvorgang empfangen kann, der auf einem physikalischen Dokument durchgeführt wird, das Markierungen zeigt, die das Bild angeben; wobei der Prozessor eingerichtet ist zum Empfangen des Quellenbildes von der Abtastschaltung; und/oder dass

die zweite Signalquelle eine Benutzereingabeeinrichtung zum Empfangen von Signalen von einem Benutzer enthält; wobei die Eingabeschaltung zum Empfangen der Signale von der Benutzereingabeeinrichtung verbunden ist; und

wobei der Prozessor zum Empfangen der Transkriptionsdatenstruktur von der Eingabeschaltung eingerichtet ist; und/oder dass

das Bildquellenmodell ein stochastisches Finitzustandsnetzwerk repräsentiert ist, das eine reguläre Grammatik angibt und die Mappingdaten, die eine jeweilige Glyphpixelposition in dem Quellenbild auf eine Glyphlabel abbilden, als einen Pfad durch das Bildquellennetzwerk repräsentiert; wobei der Pfad ihm zugeordnete Pfaddatenelemente angibt und vom Prozessor zugreifbar ist; wobei die Pfaddatenelemente Positionen und jeweils gepaarte Glyphlabel jeweiliger in dem Quellenbild enthaltener Glyphs angeben; und

die Transkriptionsdatenstruktur als ein Finitzustandsnetzwerk (800, 850, 852) repräsentiert wird, das eine Transkription als einen Transkriptionspfad durch das Transkriptionsnetzwerk modelliert, der eine geordnete Anordnung von Transkriptionslabeln angibt; und

der Prozessor eingerichtet ist, um bei der Bestimmung der Glyphpixelpositionen und der Erzeugung jeweils gepaarter Glyphlabel die folgenden Schritte durchzuführen:

Verschmelzen des Bildquellennetzwerks mit dem Transkriptionsnetzwerk, um ein Transkriptionsbildnetzwerk (870, 872) zu erzeugen, das modifizierte Mappingdaten zum Abbilden eines jeweiligen Transkriptionslabels auf eine Glyphpixelposition eines jeweiligen in dem Quellenbild auftretenden Glyphs angibt; wobei die modifizierten Mappingdaten als wenigstens ein vollständiger Transkriptionsbildpfad durch das Transkriptionsbildnetzwerk repräsentiert ist; wobei der Transkriptionsbildpfad die Pfaddatenelemente angibt;

Dekodieren des Quellenbildes unter Verwendung des Transkriptionsbildnetzwerks, um den Transkriptionsbildpfad zu erzeugen; und

Erlangen der Glyphpixelposition jeder Glyphprobe und des damit gepaarten Glyphlabels unter Verwendung der Pfaddatenelemente, die durch den Transkriptionsbildpfad angegeben sind.

10. Maschine nach Anspruch 8, weiterhin dadurch gekennzeichnet, dass

die Transkriptionsdatenstruktur eine Tag-Transkriptionsdatenstruktur ist, die wenigstens ein nichtwörtliches Tag-Transkriptionslabel enthält, das wenigstens einen Zeichenkode angibt, der ein Zeichen repräsentiert, mit dem keine Glyphprobe durch visuelle Betrachtung derselben gepaart werden kann; wobei der durch das Tag-Transkriptionslabel angegebene Zeichenkode Markup- Informationen über das Quellenbild angibt; wobei die Markup-Informationen bei ihrer Interpretation durch einen Dokumentenverarbeitungsvorgang wenigstens ein in dem Quellenbild enthaltenes Displaymerkmal erzeugen, das als eine visuelle Formatierungscharakteristik wahrnehmbar ist; und

der Prozessor eingerichtet ist, um bei der Erzeugung der gepaarten Glyphlabel die räumlichen Positionierungsdaten zu verwenden, um wenigstens eine Glyphprobe zu identifizieren, die mit dem Tag-Transkriptionslabel in Beziehung steht, und um das Tag-Transkriptionslabel zu verwenden.







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

Anmelder
Datum

Patentrecherche

  Patente PDF

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