PatentDe  


Dokumentenidentifikation DE69419809T2 25.11.1999
EP-Veröffentlichungsnummer 0623915
Titel Bilddokumentdekodierung mit modifizierten Verzweigungs- und Verbindungsmethoden
Anmelder Xerox Corp., Rochester, N.Y., US
Erfinder Kopec, Gary E., Belmont, California 94002, US;
Kam, Anthony C., Cambridge, MA 02139, US;
Chou, Philip A., Menlo Park, California 94025, US
Vertreter Grünecker, Kinkeldey, Stockmair & Schwanhäusser, Anwaltssozietät, 80538 München
DE-Aktenzeichen 69419809
Vertragsstaaten DE, FR, GB
Sprache des Dokument En
EP-Anmeldetag 06.05.1994
EP-Aktenzeichen 943032813
EP-Offenlegungsdatum 09.11.1994
EP date of grant 04.08.1999
Veröffentlichungstag im Patentblatt 25.11.1999
IPC-Hauptklasse G06K 9/00

Beschreibung[de]

Die vorliegende Erfindung betrifft Bilddecodier- und -erkennungsverfahren und speziell solche Verfahren, bei denen stochastische (Markowsche) Endzustands- Quellenmodelle zur Anwendung kommen.

Automatische Spracherkennungssysteme, die auf verdeckten Markowschen Modellen (hidden Markov models - HMMs) und anderen stochastischen Syntax-Rahmen beruhen, sind bekannt. Beispiele dafür sind in US-A-5,199,077 beschrieben und als Verweis [5] im beiliegenden Anhang angegeben. Darüber hinaus sind HMMs bei Originalbilderkennungsproblemen zur Anwendung gekommen. Der weitgehendste dieser Versuche, die sogenannte Originalbilddecodierung (document image decoding - DID), basiert auf einer expliziten Kommunikationstheorie über die Dokumenterkennung (siehe auch EP-A-0,546,843, veröffentlicht vom EPO am 16.06.93, und Verweis [6, 7, 8, 9, 10] im Anhang). Wie aus Fig. 1 von EP-A-0,546,843 hervorgeht, wählt bei dem DID-Modell eine stochastische Nachrichtenquelle eine endliche Zeichenfolge M entsprechend einer vorherigen Wahrscheinlichkeitsverteilung aus einem Satz zur Auswahl stehender Zeichenfolgen aus. Der Imager wandelt die Nachricht in ein ideales binäres Bild Q um. Der Kanal bildet das ideale Bild in einem beobachteten Bild Z ab, indem Verzerrungen infolge des Druckens und Scannens eingeführt werden, wie z. B. Schrägverzerrungen, Stör- und zusätzliche Geräusche. Schließlich empfängt der Decoder das Bild Z und erzeugt eine Schätzung der Originalnachricht in Übereinstimmung mit einem Maximum-a-posteriori-(MAP)- Entscheidungskriterium.

Wie in Fig. 1 zu sehen ist, läßt sich der Aufbau der Nachrichtenquelle und des Imagers formal durch eine Nachbildung der Bilderzeugung mit einer Markowschen Quelle darstellen. Das Decodieren eines Bildes im Hinblick auf eine Markowsche Quelle umfaßt das Auffinden des besten (MAP-) Pfades durch ein dreidimensionales (3D)-Decodiergitter hindurch, das durch die Knoten des Modells und die Koordinaten der Bildebene indexiert ist. Ein einfacher Ansatz zur MAP-Decodierung besteht in der Verwendung einer zweidimensionalen Form eines segmentären Viterbi-Algorithmus zum Berechnen eines Satzes rekursiv definierter Wahrscheinlichkeitsfunktionen an jedem Punkt der Bildebene. Die zeitliche Komplexität der Viterbi-Bilddecodierung läßt sich mit O ( β · H · W) beschreiben, wobei β die Anzahl von Verzweigungen (branches) im Quellenmodell ist und H und W die Bildhöhe und -breite in Pixel angeben. Wenngleich die Berechnung lediglich linear mit der Bildgröße zunimmt, so kann sie absolut doch unannehmbar werden. Zum Beispiel benötigt ein einfaches Dreizustandsmodell für eine Textspalte in einer einzigen bekannten Schriftart etwa 45 Minuten für ein Bild mit einer Größe von 8,5 in · 11 in, das mit einer Auflösung von 300 dpi gescannt wird. Folglich sind Verfahren zum Verkürzen der erforderlichen Berechnungszeit ausschlaggebend, wenn das DID ein praktischer Ansatz für die Originalbildanalyse werden soll.

Im Falle der Textspalten-Transkription nimmt die Komplexität der Bilddecodierung zu, weil jede Reihe des Bildes als mögliche Textzeile gewertet wird. So erfolgt bei einem Bild (300 dpi · 11 in) die Zeilendecodierung 3300 Mal. Bei konventionellen Originalerkennungsverfahren wird versucht, dieses Problem dadurch zu umgehen, daß die Texterkennung nur an den tatsächlichen Textzeilen einer Spalte ausgeführt wird, deren Anzahl normalerweise unter 50 liegt. Dabei werden einfache Segmentierungsalgorithmen verwendet, wie beispielsweise die horizontale Pixelprojektion, um die Textzeilen vor der Erkennung zu erfassen und lokalisieren (siehe Verweis [2] des Anhangs).

Genauso gut ließen sich vor der Bilddecodierung konventionelle Segmentierungsalgorithmen anwenden, und zwar analog zu ihrer Verwendung bei 1D HMM- basierten Verfahren der Texterkennung (siehe Verweise [4, 5] aus dem Anhang). Allerdings kann die Vordecodierungs-Segmentierung unzuverlässig sein, insbesondere bei besonders schlechten (verrauschten) Bildern. Da zudem konventionelle Segmentierungsalgorithmen nicht auf einem rigorosen Wahrscheinlichkeitsansatz beruhen, würden bei ihrer Anwendung viele der theoretischen Vorteile des DID negiert werden.

Ein Ziel der Erfindung besteht daher in der Schaffung eines verbesserten DID- Systems.

Die vorliegende Erfindung schafft ein Bilderkennungsverfahren gemäß einem der beiliegenden Ansprüche.

Die Erfindung ermöglicht die Senkung der Berechnungskosten der Bilddecodierung, ohne daß der optimale Nutzen der einfachen Viterbi-Prozedur eingebüßt wird. Nach einem ersten Aspekt der Erfindung verwendet das Bilddecodiersystem einen Informed-Best-First-Suchalgorithmus, den sogenannten Iterated Complete Path (ICP) Algorithmus, welcher dem Branch-and-Bound-Verfahren, A*, und dazugehörigen heuristischen Such- und Optimierungsverfahren ähnlich ist (siehe Verweis [12] im Anhang). Bei ICP handelt es sich um einen Decodieralgorithmus für eine Klasse von Markowschen Quellenmodellen, nämlich den zerlegbaren Modellen. Grob gesagt, von einer zerlegbaren Quelle spricht man, wenn sie in ein Produkt aus 1D-Modellen zerlegt werden kann, die den horizontalen bzw. vertikalen Aufbau darstellen. Genauer ausgedrückt, ist ein zerlegbares Modell eine Ansammlung von benannten Markowschen Teilquellen, die einem rekursiven Übergangsnetz ähneln (siehe Verweis [3] im Anhang). Zu einigen der Knoten des Modells gehören Positionsschranken (constraints), die den Knoteneintritt auf bestimmte Bereiche der Bildebene beschränken. Die oberste Teilquelle ist ein vertikales Modell, dessen Knoten sämtlich eng auf spezifische horizontale Positionen eingeschränkt sind.

Das erfindungsgemäße Decodieren mit einem zerlegbaren Modell umfaßt das Auffinden des besten Pfades durch das 2D-Decodiergitter, welches durch die Knotenpunkte des obersten Modells und die vertikale Dimension des Bildes definiert ist. Einige der Verzweigungen des vertikalen Modells sind mit horizontalen Modellen gekennzeichnet. Der Match-Score für eine solche Verzweigung wird berechnet, indem das horizontale Modell an der entsprechenden Reihe des Bildes ausgeführt wird. Die Gesamtdecodierzeit für ein zerlegbares Modell wird von der Zeit bestimmt, die für den Lauf der horizontalen Modelle benötigt wird. Der ICP verringert die Anzahl der Läufe der horizontalen Modelle, indem die vollständige Decodierung der meisten horizontalen Reihen durch die Berechnung einer einfachen Obergrenze der Scores ersetzt wird. Diese oberen Grenzen werden heuristische Funktionen genannt.

Nach einem zweiten Aspekt der Erfindung werden zwei Arten von parametrisierten heuristischen Funktionen vorgestellt, die sich für zerlegbare Modelle von textartigen Bildern eignen. Eine Art entspricht der weit verbreiteten Verwendung der horizontalen Pixelprojektion zur Ortsbestimmung von Textzeilen. Die zweite Heuristik begrenzt den Score für eine bestimmte Reihe mit dem Score einer benachbarten Reihe. Ein wichtiges Merkmal dieser beiden heuristischen Prinzipien besteht darin, daß ihre Parameter automatisch aus dem Quellenmodell gefolgert werden können.

Zerlegbare Quellen sind Sonderformen von rekursiven beschränkten Quellen, die wiederum ermittelt werden, indem Knotenpositionsschranken in die zuvor eingeführte Klasse einfacher Quellen eingeführt werden (siehe Verweis [8] im Anhang). Nach einem dritten Aspekt der Erfindung beschreiben wir eine Prozedur zum Umwandeln bestimmter beschränkter Quellen in eine zerlegbare Form. Ein wichtiger Bestandteil der Zerlegungsprozedur ist ein Algorithmus zur Ausbreitung anwenderorientierter Positionsschranken, die im typischen Fall für eine kleine Teilmenge der Knoten vorgegeben sind, zu den übrigen Knotenpunkten des Modells.

Zusammenfassend läßt sich sagen, daß die Erfindung ein Decodiersystem für textartige Bilder sowie ein Verfahren mit einem schnellen heuristischen Suchalgorithmus schafft, bei dem stochastische zerlegbare (Markowsche) Endzustands-Quellenmodelle in Form von HMMs zur Anwendung kommen. Der neue Suchalgorithmus (ICP), der nach hinlänglich bekannten Branch-and-Bound-Verfahren strukturiert ist, verringert die Komplexität und erhöht die Geschwindigkeit der HMM-Bilddecodierung beträchtlich, ohne daß die optimalen Eigenschaften des einfachen DID-Verfahrens eingebüßt werden. Unter "textartigen Bildern" sind alle Arten künstlicher Bilder zu verstehen, deren Satz mit Hilfe von textartigen Vorlagen (templates) erfolgt; dazu gehören - aber nicht ausschließlich - Texte, Gleichungen und Noten. Beispiele für Dokumente mit textartigen Bildern sind Geschäftsbriefe, technische Zeitschriften, Patente und Patentanmeldungen, Notenblätter und technische Zeichnungen.

Lediglich als Beispiele werden nachstehend erfindungsgemäße Ausführungsformen anhand der beiliegenden Zeichnungen beschrieben, wobei:

Fig. 1 ein einfaches Markowsches Quellenmodell für die Bilderzeugung darstellt.

Fig. 2 zeigt eine eingeschränkte Markowsche Quelle.

Fig. 3 zeigt eine rekursive Markowsche Quelle mit einer rekursiven Verzweigung in der obersten Teilquelle G&sub0;. Die Teilquellen können ebenfalls einfache Verzweigungen und Positionsschranken aufweisen.

Fig. 4 zeigt die Erweiterung eines rekursiven Übergangs. (a) Ursprünglicher Übergang. (b) Ergebnis des Austausches von t durch eine Kopie der Teilquelle St.

Fig. 5 zeigt eine einfache Textspaltenquelle. Zum leichteren Verständnis wurden Übergangswahrscheinlichkeiten, Vorlagen und Nachrichten weggelassen.

Fig. 6 zeigt eine von der Quelle in Fig. 5 abgeleitete zerlegbare Textspaltenquelle.

Fig. 7 zeigt eine Form des grundlegenden erfindungsgemäßen Iterated Complete Path (ICP) Algorithmus.

Fig. 8 zeigt eine Projektionsgewichtungsfunktion hi für 12 pt Times Roman.

Fig. 9 zeigt ein Beispiel eines Textseitenbildes in 12pt Adobe Times Roman.

Fig. 10 zeigt eine Form einer erfindungsgemäßen gewichteten Projektionsheuristik Hwp (Strichlinie) und Funktionen (durchgezogene Linie) von Ist-Werten F für das Bild aus Fig. 9.

Fig. 11 zeigt eine erfindungsgemäße Form der Konversion einer eingeschränkten Quelle in eine zerlegbare Form.

Fig. 12 zeigt ein einfaches Beispiel für eine eingeschränkte Ausbreitung.

Fig. 13 zeigt das Ergebnis des Splittens von Knoten n aus Fig. 12 für eine nach vorn beschränkte Ausbreitung.

Fig. 14 ist einen Graph für die Ausbreitung unterer Grenzen der Vorwärtsschranken. Schranken werden durch das Auffinden von Pfaden mit minimaler Verschiebung von ns fortgepflanzt.

Fig. 15 ist ein Blockdiagramm einer Form eines Bildsynthetisierers.

Fig. 16 zeigt ein Beispiel eines endlichen Übergangsnetzes, wie es im Synthetisierer aus Fig. 15 verwendet wird.

Fig. 17 veranschaulicht die Funktionsweise des Netzes aus Fig. 16 an einer Muster- Zeichenfolge.

Fig. 18 zeigt den schrittweisen Aufbau des entstehenden Ausgabebild-Bitmaps für die Zeichenfolge aus Fig. 17.

Fig. 19 ist ein Blockdiagramm einer Form eines Recognizers, die erfindungsgemäß zum Decodieren eines Bild-Bitmaps genutzt werden könnte, um die Zeichenfolge zu rekonstruieren, aus der es entstanden ist.

Fig. 20 ist ein Fließbild eines Beispiels einer Algorithmenform, welche der Node- Score-und-Backpointer-Prozessor aus Fig. 19 verwenden kann.

Fig. 21 ist ein Fließbild, welches die im Schritt 616 des Prozesses aus Fig. 20 ausgeführten Berechnungen darstellt.

Fig. 22 ist ein Fließbild einer Form von Algorithmus, den der Backtrace-Prozessor aus Fig. 19 verwenden kann.

Fig. 23 zeigt eine Form der gewichteten Projektionsheuristik.

Fig. 24 zeigt eine Form der Heuristik für die benachbarte Reihe.

Fig. 25 zeigt eine Form der Zerlegungsprozedur für die eingeschränkte Quelle.

In US-A-5,199,077 ist ein HMM-basiertes Worterkennungssystem beschrieben, welches eine Viterbi-Suche mit teilweisem Traceback ausführt. Hierbei sei auf die darin erfolgte Beschreibung des HMM-Modellerstellungsprozeß und der Auswertungsverfahren verwiesen.

EP-A-0,546,843 offenbart einen optimalen allgemeinen Ansatz für die Bilddecodierung und -erfassung, die ebenfalls mit Hilfe des HMM-Modelling erfolgt und auf die hiermit verwiesen wird.

Im Hinblick auf den gegenwärtigen Stand der Technik wird der Leser weiterhin auf die ausgezeichnete Vorlesung von L. R. Rabiner über HMMs hingewiesen, die in PIEEE, Band 77, Nr. 2, Seiten 257-285, Februar 1989, erschienen ist.

Kurz zusammengefaßt, EP-A-0,546,843 beschreibt einen Decodierprozeß, welcher ein Bildquellenmodell, ein Kanalmodell und einen Decoder erfordert. Bei dem verwendeten Quellenmodell handelt es sich um ein Markowsches Quellenmodell mit einem endlichen Netz, welches aus einer Reihe von Knoten und einem Satz gerichteter Übergänge in jeden Knoten besteht. Das Netz ist von einem Anfangs- und einem Endzustand gekennzeichnet. Jeder Übergang hat vier Attribute: eine Vorlage (template), eine Label- oder Nachrichten-Zeichenfolge, eine Übergangswahrscheinlichkeit und eine 2-dimensionale ganzzahlige Vektorverschiebung. Beim Decodieren wird der wahrscheinlichste Pfad durch das Netz vom Anfangs- zum Endzustand bestimmt. Ist dies erfolgt, werden die zu den Übergängen des wahrscheinlichsten Pfades gehörenden Nachrichten-Zeichenfolgen zu einer Beschreibung des decodierten Bildes verkettet. Zudem kann jede Nachrichten-Zeichenfolge zur Rekonstruktion einer Version des eingegebenen Bildes durch Überlappen der zu den Übergängen des wahrscheinlichsten Pfades gehörenden Vorlagen verwendet werden.

Da im typischen Fall viele Übergänge in jeden Knoten vorhanden sind, kann ein Suchalgorithmus auf der Grundlage eines Viterbi-Algorithmus zum Bestimmen des wahrscheinlichsten Pfades verwendet werden, wie in der übergeordneten Patentanmeldung erläutert ist, indem über jeder Bildposition und jedem Übergang in sämtliche Knoten Iterationen ausgeführt werden und die Wahrscheinlichkeit des besten Pfades berechnet wird, der nach Passieren des Übergangs am Knoten und an der Bildposition endet. Ein Teil dieser Berechnung schließt das Berechnen der Wahrscheinlichkeit ein, mit der die Vorlage des Übergangs einem Bereich des Bildes entspricht, der in der Nähe des Bildpunktes decodiert wird.

Die vorliegende Erfindung betrifft eine Verbesserung im Suchalgorithmus und zeigt konkret, wie die Ergebnisse für eine reduzierte Menge an Übergängen in jeden Knoten berechnet werden, wobei die reduzierte Anzahl an Übergängen wesentlich kleiner als die Zahl aller möglichen Übergänge in den Knoten ist. Da die Berechnung sehr gleichmäßig erfolgt, führt die Reduzierung der Anzahl an Übergangs-Berechnungen auch zu einer wesentlichen, fast proportionalen Senkung der zum Decodieren benötigten Berechnungszeit. Die Anzahl der Iterationen wird mit Hilfe einer oder mehrerer heuristischer Funktionen verkleinert, wodurch die Auswertung der Übergänge eingegrenzt wird. Anders ausgedrückt, es können bestimmte Übergänge aufgegeben werden, die wahrscheinlich nicht den besten Pfad enthalten, wodurch die Berechnungszeit verkürzt wird.

Wie aus den Darlegungen zum Stand der Technik deutlich wird, erfolgt bekanntlich eine vollständige Decodierung aller Übergänge, um den wahrscheinlichsten Pfad zu bestimmen. Bei der Erfindung kann hingegen durch die Verwendung der als zerlegbare Modelle bezeichneten Klasse von Markowschen Quellenmodellen und durch die Decodierung mittels ICP-Algorithmus zusammen mit geeigneten heuristischen Funktionen die vollständige Decodierung jedes Übergangs durch eine kürzere Berechnung einer einfachen Obergrenze der Übergänge ersetzt werden. Dadurch kann ein großer Teil der möglichen Übergänge außer acht gelassen werden, so daß eine vollständige Decodierung mit ausführlicherer Berechnung nur bei einer viel kleineren Zahl möglicher Übergänge ausgeführt zu werden braucht. Durch die kürzeren heuristischen Score-Berechnungen anstelle der vielen langen Übergangs- Score-Berechnungen kommt es zu dieser beträchtlichen Senkung der Gesamtberechnungszeit bei einem erfindungsgemäßen Verfahren, in einem Beispielfall um den Faktor 11 und in einem anderen um einen Faktor 19, wie später noch beschrieben wird.

Die vorliegende Erfindung baut auf den in EP-A-0,546,843 beschriebenen optimalen Verfahren auf, und zum besseren Verständnis für den Leser ist es angebracht, eine Beschreibung des Synthetisier- und Decodierprozeß aus jenem Dokument aufzunehmen.

Nunmehr wird eine Möglichkeit - die jedoch keine Einschränkung darstellt - der Anwendung des Systems aus EP-A-0,546,843 genauer beschrieben, bei der stochastische endliche Bildgeneratoren zum Einsatz kommen, die sich auf diesem und dem verwandten Gebiet der Sprachbearbeitung durchgesetzt haben.

Fig. 15 zeigt ein Verfahren, das zur Bildsynthese verwendet wird. Ein Bildsynthetisierer 110 (a. k. a.-Imager) nimmt als Eingabe eine Beschreibung einer Klasse von Bildern, ausgedrückt als ein Bildnetz 120, eine Bibliothek aus Bildvorlagen 130, von denen jede eine Liste von Parametern eines typographischen Modells eines bestimmen Zeichens, wie in Fig. 3 von EP-A-0,546,843 angegeben, und eine Zeichenfolge 100 enthält, die zur genauen Angabe eines bestimmten Bildes aus der vom Bildnetz beschriebenen Klasse genutzt wird. Von dem mager 110 wird ein Bitmap-Bild 140 ausgegeben, welches durch Anordnung eines Satzes von vorhandenen Bildern aus der Vorlagenbibliothek 130 gebildet wird. Dies ist analog zu dem Stapel Folien zu sehen, welcher früher zur Erläuterung des Abbildungsprozesses verwendet wurde. Die Identitäten und räumlichen Positionen der Teilbilder werden gemeinsam durch die eingegebene Zeichenfolge 100 und das Bildnetz 120 bestimmt.

Fig. 16 zeigt ein Beispiel 200 eines Bildnetzes 120, das einem endlichen Übergangsnetz ähnelt, wie es üblicherweise zur Darstellung einer endlichen Syntax verwendet wird. Das Bildnetz 200 besteht aus einem Satz Knotenpunkte, z. B. 205, 210, die durch gerichtete Verzweigungen, z. B. 235, 240, miteinander verbunden sind. So soll die Verzweigung 235 beispielsweise vom Knoten 205 aus- und in den Knoten 210 hineingehen. Mitunter werden die Knotenpunkte als Zustände oder Scheitelpunkte bezeichnet und die Verzweigungen manchmal als Übergänge oder Ränder. Zwei verschiedene Zustände des Netzes sind der Anfangszustand 205 und der Endzustand 220, gekennzeichnet mit /H/ni und /H/nF. Jeder Übergang ist durch vier Attribute markiert: eine Nachricht bzw. in diesem Fall der Name eines Zeichens, z. B. 236, 241, den Namen einer Bildvorlage, z. B. 237, 242, einen zweidimensionalen Verschiebungsvektor, z. B. 238, 243, der aus einer horizontalen und einer vertikalen Verschiebung dx bzw. dy besteht, und eine Übergangswahrscheinlichkeit, z. B. 239, 244. Das Zeichen-Label oder die Bildvorlage kann ein Null-Zeichen sein, wie bei dem Zeichen 251 der Verzweigung 250 oder die Vorlage 247 der Verzweigung 245. Die Übergangswahrscheinlichkeiten werden während der Bilddecodierung verwendet, nicht jedoch bei der Bildsynthese. Aus einer bestimmten Eingabe-Zeichenfolge und einem Bildnetz erzeugt der Imager ein Ausgabebild, welches die Verzweigungen des Bildnetzes durchquert, während zugleich ein Bildpositionszeiger fortgeschrieben und Vorlagen aus der Vorlagenbibliothek in die Ausgabebild-Matrix kopiert werden, wie nachfolgend dargestellt.

Im Anfangszustand 205 setzt der Imager den Bildpositionszeiger in Gang, der auf die Koordinaten (0, 0) der Ausgabebild-Matrix initialisiert wird. Das erste Zeichen der Eingabe-Zeichenfolge wird mit den Zeichen-Labels 281, 236 und 286 an den Verzweigungen 280, 235 und 285 verglichen, die vom Knoten 205 ausgehen. Wenn eines der Verzweigungs-Labels mit dem Eingabezeichen übereinstimmt, dann wählt der Imager die entsprechende Verzweigung aus und führt die folgenden Aktionen aus. Zu Darstellungszwecken wird angenommen, daß das erste Zeichen der Eingabe-Zeichenfolge ein 'b' ist. In diesem Fall wählt der Imager die Verzweigung 235, da 'b' mit dem Zeichen-Label 236 übereinstimmt. Ist die Verzweigung 235 gewählt, dann zieht der Imager eine Kopie der zur Verzweigung 235 gehörenden Bildvorlage 237 in die Ausgabematrix, wobei der Nullpunkt der Vorlage an der aktuellen Bildposition, (0), ausgerichtet wird. Anschließend wird die aktuelle Bildposition schrittweise um die zu der Verzweigung 235 gehörende Verschiebung 238 erhöht und wird zu (1 0). Schließlich bewegt sich der Imager über die gewählte Verzweigung 235 zum Knoten 210. Am Knoten 210 wiederholt der Imager diesen Vorgang noch einmal. Er untersucht das zweite Zeichen der Eingabe-Zeichenfolge und vergleicht es mit den Labels 241 und 246 an den Verzweigungen, die von dem Knoten 210 ausgehen, und wählt die passende Verzweigung aus. Wenn beispielsweise das zweite Zeichen ein 'a' ist, dann wird die Verzweigung 240 ausgewählt. In jenem Fall wird eine Kopie der Vorlage 242 für die Verzweigung 240 an die aktuelle Bildposition in der Ausgabebild-Matrix gezogen, die (1 0) ist. Die aktuelle Bildposition wird daraufhin um die Verschiebung 243 erhöht und wird zu (2 1), und der mager bewegt sich wieder zum Knoten 210.

Dieser Prozeß dauert solange an, bis alle Zeichen der Ausgabe-Zeichenfolge verarbeitet worden sind. An diesem Punkt sollte der Imager den Endzustand 220 erreicht haben oder den Endzustand erreichen können, indem die Verzweigungen mit Null-Zeichen-Labels ausgewählt werden. Ein Fehler tritt dann auf, wenn der Imager den Endzustand 220 nicht dann erreichen kann, wenn die Eingabe- Zeichenfolge aufgebraucht ist. Darüber hinaus liegt ein Fehler vor, wenn an einer Stelle des Prozesses keine Verzweigung zu dem aktuellen Eingabezeichen paßt. Ein Problem tritt auch immer dann auf, wenn mehr als eine Verzweigung zu dem aktuellen Zeichen passen. Verfahren zur Verallgemeinerung der obigen Prozeßbeschreibung, um diese oder andere Ausnahmesituationen zu bewältigen, sind in der Literatur über endliche Sprachen hinlänglich bekannt.

Die Fig. 17 und 18 verdeutlichen den vollständigen Prozeß für das Bildnetz 200 aus Fig. 16 und die Eingabe-Zeichenfolge "baa$" 310. In Fig. 17 ist das Bild 320 zu sehen, das entsteht, wenn die Zeichenfolge 310 entsprechend dem Netz 200 verarbeitet wird. Die Schritte 1-5 des Syntheseprozesses sind in der Tabelle aus Fig. 18 genau angegeben. Vor dem Schritt 1 befindet sich der Imager im Anfangszustand 205 an der Position (0 0) der Ausgabematrix, die eine Leerstelle ist. Im Schritt 1 vergleicht der Imager das erste Eingabezeichen 311 mit den Labels der drei Verzweigungen 280, 235, 285, die von dem Knoten 205 ausgehen. Das Eingabezeichen stimmt mit dem Label 236 an der Verzweigung 235 überein. Der Imager zieht eine Kopie 411 der zur Verzweigung 235 gehörenden Vorlage 237, in diesem Fall ein Bild von einem 'b', in die Ausgabematrix an der Stelle (0 0) und bewegt sich weiter zum Knoten 210 und zur Bildposition (1 0). Bei diesem Beispiel wird davon ausgegangen, daß der Ausrichtpunkt jeder Vorlage die linke untere Ecke der Vorlage ist. In der Bildspalte aus Fig. 18 ist die Bildstelle am Anfang von Schritt 1 im Bild 410 mit einem Punkt "." 412 angegeben. Die Bildstelle am Ende von Schritt 1 wird mit einem "X" 414 angegeben. Genauso sind die Bilder 420, 430, 440 und 450 für die Schritte 2-5 markiert.

In Schritt 2 vergleicht der Imager das zweite Eingabezeichen 312 mit den Zeichen 241 und 246 an den Verzweigungen 240 und 245, die von dem Knoten 210 ausgehen. Das Eingangszeichen 'a' paßt zu dem Label 241 der Verzweigung 240, so daß der Imager eine Kopie 421 der Vorlage 242 - in diesem Fall ein Bild von einem a' - an der aktuellen Stelle (1 0) ablegt, die aktuelle Stelle durch Verschiebung 243 zu (2 1) vorrückt und sich wieder zum Zustand 210 bewegt.

In Schritt 3 wird der Vorgang für das dritte Eingabezeichen 313 wiederholt. Der Imager wählt die Verzweigung 240, legt eine Kopie 431 der Vorlage 242 an der Stelle (2 1) ab, schreibt die aktuelle Bildstelle auf (3 2) fort und bewegt sich wieder zum Knoten 210.

In Schritt 4 wird das vierte Eingabezeichen 314 verarbeitet, und der Imager folgt der Verzweigung 245 bis zum Knoten 215. Der Bildstellenzeiger wird nicht verändert, da die zur Verzweigung 245 gehörende Verschiebung 248 (0 0) ist, und es wird keine Vorlage in die Ausgabematrix kopiert, da das Vorlagen-Label 247 der Verzweigung 245 die Null-Vorlage angibt.

Zu Beginn von Schritt S hat der Imager die Eingabe-Zeichenfolge verbraucht. Da allerdings das Zeichen-Label 251 der Verzweigung 250 das Null-Zeichen angibt, kann die Verzweigung 250 ausgewählt werden. Eine Kopie 451 der Vorlage 252 für die Verzweigung 250 - ein Bild 'm' - wird an der aktuellen Bildposition (3 2) abgelegt, der Imager bewegt sich zum Zustand 220, und die Bildposition wird auf (4 0) fortgeschrieben. An diesem Punkt befindet sich der Imager im Endzustand 220, und es liegen keine weiteren Eingabezeichen zur Verarbeitung vor, so daß der Bildbearbeitungsprozeß erfolgreich abgeschlossen ist. An diesem Beispiel wird auch deutlich, daß es keine Eins-zu-Eins-Übereinstimmung zwischen den Eingabe-Zeichenfolgen- Symbolen und dem entstehenden Bitmap-Bild geben muß. Zum Beispiel könnte die abzubildende Zeichenfolge Informationen enthalten, welche codierten Anmerkungen entsprechen, die nicht in dem Bitmap eingeschlossen sein sollen. Genauso könnte der Recognizer in seinen Ausgabesignalen Informationen über das Bitmap (beispielsweise seine Quelle) einschließen, die nicht in dem Bitmap an sich vorliegen. Ebenso könnten sich die Bitmap-Symbole von den Zeichenfolgen-Symbolen unterscheiden (beachte '$' in der Zeichenfolge und 'm' im Bitmap), und es braucht kein Symbol im Bitmap vorhanden zu sein, wenn der Recognizer unter bestimmten vorgegebenen Bedingungen automatisch ein Zeichen erzeugt.

In Fig. 19 ist der umgekehrte Prozeß dargestellt, nämlich die Verwendung eines Bildnetzes zum Decodieren eines Eingabe-Bitmaps 510 zum Erzeugen einer Ausgabe-Zeichenfolge 590. Hierbei handelt es sich um den Teil des Systems, der durch die vorliegende Erfindung verbessert wird. Für das Beispiel aus Fig. 17 würde das gleiche Bildnetz 200 zum Einsatz kommen. Der Vorlagen-Matcher (template matcher) 520 vergleicht jedes Element der Vorlagenbibliothek 530 (die gleiche wie die Vorlagenbibliothek 130 im Imager aus Fig. 15) mit dem Eingabebild 510 mit Hilfe einer Abgleichfunktion, welche wie im Ausgabefall definiert L(Z Q) berechnet. Der Vorlagen-Matcher gibt einen Satz von Score-Matrizen 540 aus, eine für jede Vorlage aus der Bibliothek, welche den numerischen Match-Score für die Vorlage an jeder Stelle des Eingabebildes enthält. Der Node-Score-und-Backpointer-Prozessor 550 berechnet eine Score-Array und eine Backpointer-Array 570 für jeden Knoten des Bildnetzes 560. Der Score für einen Knoten enthält den numerischen Match-Score L(n; ), der im Ausgangsfall für jenen Knoten definiert ist, der an jeder Stelle des Eingabebildes ausgerichtet ist. Die Backpointer Array für einen Knoten identifiziert die wahrscheinlichste Verzweigung in den Knoten, das heißt die Verzweigung an jeder Bildstelle, an der der Score am größten ist. Die Eingaben in den Node-Score- und-Backpointer-Prozessor 550 sind die Vorlagen-Match-Scores 540 für den Vorlagen-Matcher und ein Decoder-Schedule 555 aus dem Bildnetz 560, bei dem es sich um das gleiche Bildnetz 120 wie bei dem Imager aus Fig. 15 handelt. Schließlich verwendet der Backtrace-Prozessor 580 die Backpointer-Array 570 zum Erzeugen eines Pfades durch das Bildnetz 560, und aus diesem Pfad wird eine Ausgabe- Zeichenfolge 590 gebildet, indem die Zeichen-Labels der Pfadverzweigungen verkettet werden. Dadurch wird für das Beispiel aus Fig. 17 die Zeichenfolge "baa$" rekonstruiert.

Eine Algorithmusform, die bei Abarbeitung durch den Node-Score-und-Backpointer- Prozessor 550 die Arrays 570 wie oben beschrieben erstellt, ist in Fig. 20 genauer dargestellt. Der Prozessor 550 trägt die Node-Score-und-Backpointer-Arrays 570 nacheinander für die Reihen ein - zuerst werden alle Werte für die erste Reihe berechnet, danach für die zweite Reihe und so weiter, bis alle Reihen fertig sind. Die Berechnung für jede Reihe ist wiederum als eine Serie von "Durchläufen" organisiert. Bei jedem Durchlauf wird eine Reihe für jede Array einer Teilmenge der Score- und Backpointer Arrays berechnet. Eine Reihe wird entweder von links nach rechts - bei größer werdender x-Position - oder von rechts nach links - bei kleiner werdender x- Position - berechnet, auch hier wie durch den Schedule angegeben. Einen Durchlauf von links nach rechts nennt man einen "Vorwärts-"Durchlauf und einen Durchlauf von rechts nach links einen "Rückwärts"-Durchlauf. An jeder x-Position innerhalb eines Durchlaufs werden die Scores und Backpointers für eine bestimmte Knoten- Teilmenge des Bildnetzes in vorgegebener Reihenfolge berechnet.

Bei dem Algorithmus aus Fig. 20 handelt es sich um eine verschachtelte Iteration mit 4 Ebenen. Die äußerste Ebene, die Schritte 602 bis 632, führen die Iteration über Reihen aus. Schritt 602 initialisiert den Reihenzähler y auf 1. In Schritt 630 wird der Reihenzähler mit der Anzahl der Reihen im Bild, H, verglichen. Wenn noch nicht alle Reihen berechnet wurden, wird der Reihenzähler in Schritt 632 stufenweise erhöht, und die nächste Reihe wird verarbeitet. Die zweite Ebene, die Schritte 604 bis 628, führen die Iteration über Durchläufen aus. Der Durchlaufzähler wird in Schritt 604 initialisiert, in Schritt 626 mit der Gesamtanzahl an Durchläufen K verglichen und in Schritt 628 stufenweise erhöht. Die dritte Ebene, die Schritte 605 bis 624, führt die Iteration über der horizontalen Position innerhalb der vom Reihenzähler y angegebenen Reihe aus. Drei horizontale Positionszeiger werden gleichzeitig aufrecht erhalten. Der Zeiger /XF/ gibt die horizontale Position für die Vorwärtsdurchläufe an. In Schritt 605 wird XF auf 1 initialisiert, in Schritt 624 stufenweise erhöht und in Schritt 622 mit der Anzahl an Positionen innerhalb einer Reihe W verglichen. Der Zeiger XR gibt die horizontale Position für die Rückwärtsdurchläufe an. Er wird in Schritt 605 auf W initialisiert und in Schritt 624 stufenweise verkleinert. Der Zeiger X wird in Schritt 608, 610 und 612 auf XF bzw. XR eingestellt, je nachdem, ob der aktuelle Durchlauf ein Vorwärts- oder ein Rückwärtsdurchlauf ist. Die vierte Iterationsebene, die Schritte 614 bis 620, berechnet den Score L(n,x,y) und den Backpointer B(n,x,y) für jeden Knoten n des Durchlaufs, der vom Durchlaufzähler an der Reihe y und an der horizontalen Position x bestimmt ist. Die eigentliche Berechnung des Score L(n,x,y) und des Backpointers B(n,x,y) erfolgt in Schritt 616, der in Fig. 21 beschrieben ist.

Fig. 21 beschreibt ein Beispiel der Berechnung des Knoten-Score L(n,x,y) und des Backpointers B(n,x,y) für einen bestimmten Knoten n und die Bildposition (x y). Dieser Algorithmus ist eine zweidimensionale Verallgemeinerung des standardmäßigen eindimensionalen, dynamischen Programmierschrittes, der in der Spracherkennung mit verdeckten Markowschen Modellen verwendet wird. Zu der Berechnung gehört das Auffinden jener Verzweigung unter allen Verzweigungen, die in den konkreten Knoten n eintreten, welcher den Score des Knotens an der angegebenen Bildposition (x y) maximiert. Der maximale Score und die Identifizierung der entsprechenden besten Verzweigung werden in Schritt 770 als L(n,x,y) und B(n,x,y) zurückgeführt. Im Verlaufe der Berechnung enthalten die Variablen Bestscore und Bestbranch, die in Schritt 710 initialisiert wurden, den besten Score und die entsprechende Verzweigung, die bislang festgestellt wurden.

Die Schritte 715 bis 765 führen die Iteration über den Verzweigungen aus, die in den Knoten n gelangen. Schritt 715 initialisiert den Verzweigungs-Index t als die erste Verzweigung in n hinein; und die Schritte 760 und 765 wiederholen die Iteration solange, bis alle Verzweigungen von n berücksichtigt worden sind. In den Schritten 720, 725 und 730 werden die zur Verzweigung t gehörende Vorlage Q, die Verschiebung (dx dy) und die Übergangswahrscheinlichkeit herausgesucht. Diese entsprechen den Attributen der Verzweigungen bzw. Übergänge, die in Fig. 16 dargestellt sind. Schritt 735 sucht den Vorlagen-Match-Score für die Vorlage Q an der Bildposition (x-dx y-dy) aus den Vorlagen-Score-Arrays heraus, die zuvor als Eingabe 540 in den Node-Score-und-Backpointer-Prozessor 550 eingegeben wurden. Schritt 540 sucht die Kennung des Knotens R heraus, von dem die Verzweigung t ausgeht, und Schritt 742 sucht den Wert des Knoten-Score L(n,x,y) für den Knoten R an der Bildposition (x-dx, y-dy) heraus. Dieser Wert wurde während einer früheren Ausführung des Algorithmus aus Fig. 21 berechnet; der Decoder-Schedule 555 sollte sicherstellen, daß sämtliche Knoten-Score-Werte, die zum Berechnen von L(n,x,y) während der aktuellen Berechnung erforderlich sind, durch vorherige Berechnungen bereitgestellt wurden. Schritt 745 berechnet den in Frage kommenden Knoten-Score für die aktuelle Verzweigung. Schließlich werden in Schritt 750 und 755 der Bestscore und Bestbranch fortgeschrieben, wenn der in Frage kommende Score, welcher in Schritt 745 berechnet wurde, größer als der bisherige Wert des Bestscore ist.

Der Vorlagen-Matcher 520 berechnet L(Z Q) für jede Vorlage Q, ausgerichtet an jeder Bildstelle. Die Implementierung ist einfach.

Der Scheduler 565 erstellt aus dem Bildnetz 560 einen Schedule 555. Der Schedule legt die Reihenfolge fest, in der die Einträge in die Node-Score-und-Backpointer- Arrays 570 berechnet werden, und sollte gewährleisten, daß die Datenabhängigkeiten beachtet werden.

Mit Hilfe der Algorithmen, von denen ein Beispiel in Fig. 25 beschrieben ist, berechnet der Backtrace-Prozessor 580 die Ausgabe-Zeichenfolge 590 aus den Node- Score-und-Backpointer-Arrays 570. Der Backtrace-Prozessor führt eine Rückverfolgung vom Endknoten nF an der Bildposition (W H) aus, indem er solange nacheinander den in der Backpointer Array identifizierten Verzweigungen folgt, bis der Anfangsknoten nI erreicht ist. Die Zeichen-Labels an den Verzweigungen, denen während der Rückverfolgung begegnet wurde, werden verkettet und bilden so die Ausgabe-Zeichenfolge 590.

Schritt 810 initialisiert die aktuelle Bildposition (x y) auf (W H), den aktuellen Knoten n auf den Endknoten nF und die Ausgabe-Zeichenfolge m auf die Null-Zeichenfolge. Schritt 820 setzt t auf die Verzweigung B(n,x,y), die zuvor vom Node-Score-und- Backpointer-Prozessor 550 berechnet wurde. Das Zeichen-Label 'c' für die Verzweigung t wird in Schritt 830 herausgesucht und in Schritt 840 an den Beginn der Zeichenfolge geschoben. Schritt 850 aktualisiert n auf den Knoten, von dem die Verzweigung t ausgeht, und Schritt 860 sucht die Verschiebung (dx dy) für die Verzweigung t heraus. In Schritt 870 wird die aktuelle Bildposition (x y) durch Subtrahieren der Verschiebung (dx dy) aktualisiert. Der neue, in Schritt 850 ermittelte Wert des Knotens n wird dann in Schritt 850 mit nI, dem Anfangsknoten des Bildnetzes, verglichen. Wurde nI erreicht, endet die Rückverfolgung in Schritt 890 und führt die Zeichenfolge m zurück. Andernfalls wird der Prozeß ab Schritt 820 wiederholt.

Zum besseren Verständnis der Erfindung für den Leser sind die nachfolgenden Abschnitte der Beschreibung wie folgt gegliedert.

Abschnitt 1 definiert die Klasse der zerlegbaren Markowschen Quellen und der verwandten Klassen eingeschränkter oder rekursiver Quellen. In Abschnitt 2 wird der erfindungsgemäße Iterated Complete Path Algorithmus (ICP) beschrieben. Abschnitt 3 definiert die parametrisierte horizontale Projektion und erfindungsgemäße heuristische Funktionen für die benachbarten Reihen. In Abschnitt 4 wird ein Algorithmus zum Testen eingeschränkter Quellen im Hinblick auf die Zerlegbarkeit und Durchführung der Konversion, wenn diese erfindungsgemäß möglich sind, erörtert. In diesem Abschnitt wird auch die Ausbreitung anwenderorientierter Bedingungen vor der Zerlegung erörtert. Und zum Schluß stellt Abschnitt 5 experimentelle Ergebnisse vor, die die Beschleunigungsmöglichkeiten mit Hilfe von ICP und den heuristischen Funktionen verdeutlichen.

1. Zerlegbare Markowsche Quellen

In diesem Abschnitt wird der Begriff einer zerlegbaren Quelle entwickelt, auf den sich der ICP gründet. Zu Beginn geben wir einen Überblick über die Bildmodelle, die in [8] aus dem Anhang vorgestellt werden und die wir als einfache Markowsche Quellen bezeichnen. Anschließend werden die einfachen Quellen zu eingeschränkten Quellen verallgemeinert, indem Schranken im Hinblick auf die Knotenposition eingeführt werden, und zu rekursiven Quellen, indem ermöglicht wird, daß eine Quelle eine andere "aufruft". Danach werden zerlegbare Modelle als eine Sonderklasse von rekursiven Quellen definiert. Am Schluß des Abschnitts werden Beispiele von Quellenmodellen und Schranken für eine einfache Textspalte in einer Schriftart angegeben.

1.1 Einfache Markowsche Quelle

Eine einfache Markowsche Quelle G, in Fig. 1 dargestellt, ist ein gerichteter Graph, der aus einer endlichen Reihe von Zuständen N (Knoten, Scheitel)

N = {n&sub1; ... nN} (1)

und aus einem Satz gerichteter Übergängen B (Verzweigungen, Ränder)

β = {t&sub1; ... tB} (2)

besteht.

Jeder Übergang t verbindet ein Zustandspaar, Lt und Rt, die als Vorgängerzustand (links) und Nachfolgezustand (rechts) von t bezeichnet werden. Zwei verschiedene Zustände sind der Anfangszustand nI und der Endzustand nF. Zu jedem Übergang gehören vier Attribute (Qt, mt, at, t), wobei Qt die Vorlage, mt die Nachrichten- Zeichenfolge, at die Übergangswahrscheinlichkeit und r = (Δxt, Δyt) die zweidimensionale ganzzahlige Vektorverschiebung ist. Die Art des Übergangs in einer einfachen Markowschen Quelle wird einfacher Übergang genannt.

Ein Pfad π einer Markowschen Quelle ist eine Folge von Übergängen t&sub1; ... tp, bei der

Rti = Lti+1 (3)

bei i = 1, ..., P-1. Ein vollständiger Pfad ist ein Pfad, bei dem L = nI und Rtp = nF Ein Zyklus bzw. eine Schleife ist eine Abfolge von Übergängen t&sub1; ... tp, bei der L = Rtp ist.

Zu jedem Pfad π gehört eine zusammengesetzte Nachricht

Mπ = mt&sub1; ... mtp (4)

die durch Verkettung der Nachrichten-Zeichenfolgen der Pfadübergänge gebildet wird. Eine einfache Markowsche Quelle definiert eine Wahrscheinlichkeitsverteilung auf vollständigen Pfaden durch

Pr{π} = ati (5)

und weist eine Wahrscheinlichkeitsverteilung an Nachrichten auf:

Pr{M} = Pr{π} (6)

wobei die Summierung über vollständigen Pfaden vorgenommen wird.

Zu jedem Pfad π gehört zudem eine Abfolge von Positionen 0... p, welche rekursiv definiert werden durch

wobei 0, eine Anfangsposition ist, normalerweise . Grob ausgedrückt, l ist die Position des Graphik-Cursors nach dem i. Pfadübergang. Ein Pfad definiert ein zusammengesetztes Bild Q durch

Oπ = Qti[ i-1] (8)

wobei Q[ ] Q bezeichnet, welches derart verschoben ist, daß sich der Nullpunkt seines örtlichen Koordinatensystems bei befindet. Für einen Pfad π definieren wir

welches die Verschiebung des Pfades ist und Δxπ und Δxπ die x- bzw. die y-Komponente von π angeben.

Dabei ist zu beachten, daß P und ti Funktionen von π sind und daß l und Qπ ebenfalls von 0 abhängig sind. Auf diese Abhängigkeit wird nur dann explizit hingewiesen, wenn eine Zweideutigkeit vermieden werden soll; dann schreiben wir beispielsweise l(π; 0).

Die MAP-Decodierung schließt das Auffinden eines vollständigen Pfades (und damit ein, das die Pfadwahrscheinlichkeitsfunktion maximiert, welche definiert ist durch:

L(π) L(Z Qπ) + log Pr{π} = [L(Z Qti[ i-1]) + log ati] (10)

wobei L(Z Q[ ]) der Vorlagen-Match-Score für Q ist, ausgerichtet an der Position x, und von dem Kanalmodell abhängt. Die MAP-Decodierung kann durch Berechnen der Wahrscheinlichkeitsfunktion

an jedem (n, ) N · Ω erfolgen, wobei Ω das ganzzahlige Gitter [O, W]·[O, H] ist.

Diese Beschreibung verwendet ein Bildkoordinatensystem, bei dem x nach rechts zunimmt, y nach unten und sich die obere linke Ecke bei x = y = 0 befindet. Der Ausdruck

(nI; 0) (n; ) (12)

stellt die Schranke dar, nach der π ein Pfad vom Knoten n&sub1; an der Bildposition 0 zum Knoten n bei ist.

Die Wahrscheinlichkeiten L(n; ) fassen sich mit Hilfe eines segmentären (dynamischen Programmier-) Viterbi-Algorithmus rekursiv errechnen durch:

Normalerweise wird der vorstehende Wahrscheinlichkeits-Term log Pr{π} in (10) von dem Beobachtungsausdruck ..(Z Qπ) dominiert - mit Ausnahme von qualitativ sehr schlechten Bildern. Daher kann er als praktische Annäherung oft weggelassen werden. Die Wahrscheinlichkeitsfunktion L(n , ) hängt implizit vom Startknoten nI, der Anfangspfadposition 0, und dem Quellenmodell G ab. Wenn es notwendig ist, diese explizit anzugeben, dann schreiben wir L(n, nI, 0; G).

1.2 Eingeschränkte Markowsche Quellen

Viele Aspekte der Dokumentgestaltung, wie beispielsweise die Position von Spaltenbegrenzungen, Seitenzahlen und Fußnoten, können natürlich als Schranken im Hinblick auf die absoluten Positionen von Bildmerkmalen ausgedrückt werden. Eingeschränkte Markowsche Quellen schaffen einen Rahmen für das Ausdrücken und Ausnutzen solcher Schranken innerhalb des Dokumentdecodierparadigmas. Wie in Fig. 2 zu erkennen, ist eine eingeschränkte Markowsche Quelle eine einfache Quelle, bei der einige oder alle Knoten x- und/oder y Positionsschranken aufweisen. Anders ausgedrückt, eine Positionsschranke gibt die unteren und oberen Grenzen von x und y an, wenn ein Pfad einen Knoten durchquert. Formell ausgedrückt, falls bei einem Übergang ti eines Pfades in einer eingeschränkten Quelle R = n ist, dann

i Cn {χnl, χnu} · [ψnl, ψnu] (14)

Falls χnl = χnu = Xn ist, sagen wir, daß der Knoten bei x enge Schranken aufweist; genauso weist ein Knoten enge Schranken bei y auf, wenn ψnl = ψnu. Im typischen Fall weisen der Anfangs- und Endknoten einer Quelle sowohl bei x als auch y enge Schranken auf, wobei Xn = Ψn = 0 und Xnp = W und ΨnF = H.

Eine eingeschränkte Quelle definiert eine Wahrscheinlichkeitsverteilung an zugelassenen vollständigen Pfaden durch

Pr{π} = γ ati (15)

wobei γ ein Standardisierungsfaktor ist, der zur Vereinheitlichung der Summe von Wahrscheinlichkeiten eingeführt wurde. Da es sich bei γ um eine pfadunabhängige Konstante handelt, geht sie nicht in die Decodier-Berechnung ein. Bei einer eingeschränkten Quelle wird (11) abgewandelt, indem die Maximierung auf jene Pfade beschränkt wird, welche die Schranken einhalten, so daß aus (13) die folgende Formel wird:

die eine einfache Abwandlung des Decodier-Algorithmus darstellt. Aus praktischen Gründen werden wir gewöhnlich die Schranke im Hinblick auf x weglassen und schreiben (16) einfach als (13).

Wie aus (16) hervorgeht, besteht der Berechnungseffekt einer Positionsschranke darin, das Gitter für einen Knoten zu einer Teilmenge der Bildebene zu decodieren. Somit sind durch die Positionsschranken oft wesentlich weniger Berechnungsvorgänge erforderlich, wenn sie bei einer standardmäßigen Viterbi-Decodierung zum Einsatz kommen.

1.3 Rekursive Markowsche Quellen

Die Entwicklung eines großen Quellenmodells, wie beispielsweise das Gelbseitenspaltenmodell, welches in Verweis [8] aus dem Anhang beschrieben ist und nahezu 6500 Verzweigungen und 1800 Knoten enthält, wird durch das hierarchische Beschreiben des Modells erleichtert. Die formelle Grundlage für die hierarchische Beschreibung ist die rekursive Markowsche Quelle, dargestellt in Fig. 3. Eine rekursive Quelle ist eine Ansammlung benannter Teilquellen G&sub0;, G&sub1;, ... Gk, von denen jede einer eingeschränkten Markowschen Quelle ähnlich ist, außer daß sie eine zusätzliche Art Übergang aufweisen kann. Eine rekursive Verzweigung ist mit einer Übergangswahrscheinlichkeit at und dem Namen einer der Teilquellen St gekennzeichnet. Unter einer rekursiven Verzweigung versteht man eine Kopie der benannten Teilquelle. Eine der Teilquellen wird als die oberste Teilquelle der rekursiven Quelle bezeichnet und mit dem Label G&sub0; versehen. Der Anfangs- und der Endknoten einer rekursiven Quelle werden als jene von G&sub0; definiert.

Die Teilquellen einer rekursiven Quelle lassen sich als Knoten in einem gerichteten Abhängigkeitsgraphen mit einer Verzweigung von einer Teilquelle zur anderen betrachten, falls die erste Teilquelle eine rekursive Verzweigung enthält, die mit dem Name der zweiten gekennzeichnet ist. Wenn der Abhängigkeitsgraph einer rekursiven Quelle azyklisch ist, ist die Quelle äquivalent zu einer eingeschränkten Markowschen Quelle, die durch das wiederholte Ersetzen jeder rekursiven Verzweigung t in G&sub0; durch eine Kopie von St solange abgeleitet wird, bis keine rekursiven Verzweigungen mehr übrig bleiben. Fig. 4 stellt einen Schritt der Expansion dar. Der Expansionsprozeß endet, wenn der Abhängigkeitsgraph azyklisch ist; die entstehende "abgeflachte" Quelle, als gekennzeichnet, enthält nur einfache Übergänge. Enthält der Abhängigkeitsgraph einen Zyklus, dann ist die rekursive Quelle nicht zu einer eingeschränkten Quelle äquivalent, sondern entspricht dem rekursiven Übergangsnetz einer kontextfreien Syntax (siehe Verweis [3] aus dem beiliegenden Anhang). In der vorliegenden Arbeit gehen wir davon aus, daß die Abhängigkeitsgraphen azyklisch sind.

Als Decodieren eines Bildes mit einer rekursiven Quelle ist seine Decodierung in bezug auf die äquivalente eingeschränkte Quelle definert, so daß beispielsweise bei n G&sub0;

Da wir letztendlich nur an der Wahrscheinlichkeit des Endknotens ..(nP; W,H) interessiert sind, reicht es aus, L(n; ) nur für jene Knoten in der obersten Teilquelle G&sub0; explizit zu berechnen. Betrachtet man Fig. 4 und die Definition von L(n, ) als maximalen Pfad-Score, dann ist unschwer zu erkennen, daß (16) im Hinblick auf Übergänge in G&sub0; als

geschrieben werden könnte, wobei wir für einfache Übergänge definieren:

Die verschachtelte Maximierung über &sub1;, wird eingeführt, da sich rekursive Verzweigungen über Bildregionen variabler Größe erstrecken können.

1.4 Zerlegbare Markowsche Quellen

Es wird davon ausgegangen, daß eine rekursive Quelle G eine konstante y-Verschiebung aufweist, wenn Δyπ bei jedem vollständigen Pfad π in gleich ist. Hat die zu einem rekursiven Übergang gehörende Teilquelle eine konstante y-Verschiebung Δyπ, dann definieren wir die y-Verschiebung des Übergangs in Analogie zur Verschiebung einer einfachen Verzweigung als Δyπ. Man bezeichnet eine rekursive Quelle als zerlegbar, wenn jeder Knoten von G&sub0; bei x enge Schranken aufweist und wenn St eine konstante Verschiebung für jede rekursive Verzweigung t in G&sub0; hat.

Falls g zerlegbar ist, verringert sich die Maximierung über &sub1; in (18) auf den Wert bei &sub1; = (XLt, y - Δyt), da Lt enge Schranken in x aufweist und St eine konstante y-Verschiebung hat. Weil zudem jeder n G&sub0; bei x (18) enge Schranken aufweist, erfolgt eine weitere Reduzierung zu

wobei die x- und y-Koordinaten explizit dargestellt sind. Wenn die festgelegten Parameter in (20) als Funktionsargumente weggelassen werden und wir

F(t; y) L(nF(St); χRt, y nI(St); χLt, y - Δyt; t) (21)

definieren, dann vereinfacht sich (20) weiter zu

was als eine eindimensionale segmentäre Viterbi-Rekursion bei y interpretiert werden kann, wobei Segment-Scores mit F(t; y) angegeben werden.

Falls t ein einfacher Übergang ist, dann ist F(t: y) der Match-Score zwischen dem Eingabebild und der Vorlage Qt an der Bildposition (χRt, y). Handelt es sich bei t hingegen um einen rekursiven Übergang, dann wird F(t; y) errechnet, indem der beste Pfad in St vom Knoten nI(St) an der Bildposition (XnI(St), y - Δyt) zum Knoten nF(St) bei (XnI(St), y)ermittelt wird. Da jeder vollständige Pfad in t die gleiche y-Verschiebung hat, so folgt daraus, daß die Verschiebung eines Pfades in t von nI(St) zu einem anderen Knoten n lediglich von n abhängt. Daher kann bei der Berechnung von F(t; y) für einen gegebenen Wert y davon ausgegangen werden, daß die Knoten von t im Hinblick auf y eng beschränkt sind und sich die Berechnung auf eine eindimensionale Rekursion in x reduziert. Dementsprechend besteht die gesamte Decodierberechnung für eine zerlegbare Quelle aus einem Satz unabhängiger horizontaler Rekursionen, welche den Wert von F(t; y) errechnen, gefolgt von einer einzelnen vertikalen Rekursion zur Berechnung von (22).

1.5 Textspaltenbeispiel

In Fig. 5 ist ein einfaches Quellenmodell für eine Textspalte in 12pt Adobe Times Roman abgebildet, welches dem in Verweis [8] aus dem beiliegenden Anhang beschriebenen ähnlich ist. Zur Veranschaulichung der Konzepte und Algorithmen werden wir dieses Beispiel über die gesamte Beschreibung hinweg anwenden. Die Operation der Textspaltenquelle kann mit Hilfe eines Imager-Automats erläutert werden, der sich, vom Quellenmodell gesteuert, über die Bildebene bewegt. Im Zustand n&sub1; erzeugt der Imager einen vertikalen Abstand; jede Durchquerung des Eigenübergangs bewegt den Imager eine Reihe weiter nach unten. An einem bestimmten Punkt erreicht der Imager die Oberseite einer Textzeile und tritt in den Zustand n&sub2; ein, der die Schaffung einer horizontalen Textzeile darstellt. Durch die Verschiebung (0, 34) des Übergangs in n&sub2; hinein bewegt sich der Imager nach unten zur Textzellen-Grundline; 34 ist die Schrifthöhe über der Grundlinie. Die Eigenübergänge bei n&sub2; entsprechen den einzelnen Zeichen der Schrift und den horizontalen Zwischenräumen. Am Ende einer Textzeile bewegt sich der Imager um die Schrifttiefe unter die Grundlinie 13 und tritt in n&sub3; ein. An diesem Punkt geht der Imager entweder in den Endzustand über oder tritt in den Zustand "Wagen zurück" n&sub4; ein, wodurch er in Vorbereitung auf die nächste Textzeile zum linken Rand zurückgefahren wird.

Tabelle 1 zeigt einen Satz von Knotenpositionsschranken für die Textspaltenquelle aus Fig. 5. Die mit Cn gekennzeichneten Spalten enthalten die anwenderspezifischen Schranken; die übrigen Spalten betreffen die Ausbreitung der Schranken, wie später noch ausgeführt wird. Wie dieses Beispiel verdeutlicht, sind der Anfangs- und der Endzustand gewöhnlich eng beschränkt auf die obere linke bzw. die untere rechte Ecke der Bildebene. Durch die x-Schranken bei n&sub1; und n&sub3; wird jede Textzeile (einschließlich des Leerraums vor und nach dem eigentlichen Text) gezwungen, die gesamte Breite der Spalte zu überspannen. Zur Vereinheitlichung werden alle Knoten mit Schranken versehen. Dort, wo keine explizite Schranke vorgegeben ist, wird [-∞, +∞] angenommen.

Tabelle 1: Anfängliche (anwenderspezifische) und fortgepflanzte Schranken für die Textspaltenquelle aus Fig. 5. (a) Schranken bei x. (b) Schranken bei y.

Fig. 6 zeigt ein rekursives Textspalten-Quellenmodell, welches äquivalent zu der eingeschränkten Quelle aus Fig. 5 und Tabelle 1 ist. Dieses Modell wurde automatisch mit Hilfe der Separationsprozedur erstellt, die später beschrieben wird. Die Teilquelle G&sub1; bildet die Erzeugung einer einzelnen Zeile horizontalen Textes nach, einschließlich der vertikalen Verschiebungen vom oberen Rand der Zeile bis zur Grundlinie und von der Grundlinie bis zum unteren Rand der Zeile. Bei der Teilquelle G&sub2; handelt es sich um die Wagenrückführung von rechts nach links.

Jeder Knoten der obersten Quelle G&sub0; ist bei x sehr eng beschränkt, wie mit Tabelle 1(a) überprüft werden kann. Darüber hinaus hat jeder vollständige Pfad durch G&sub1; eine y-Verschiebung 47 und jeder Pfad durch G&sub2; eine y-Verschiebung 0. Folglich ist die Textspaltenquelle zerlegbar.

2. Iterated-Complete-Path-(ICP)-Algorithmus

Ein direkter Ansatz der Decodierung mit einer zerlegbaren Quelle besteht darin, zuerst einmal F(t; y) für jedes t G&sub0; und y [O, H) zu berechnen und anschließend (22) anzuwenden. Ein solches Vorgehen entspricht effektiv der Viterbi-Decodierung und ermöglicht somit Einsparungen bei Rechenvorgängen.

Der erfindungsgemäße Iterated-Complete-Path-(ICP)-Algorithmus geht auf die Beobachtung zurück, daß nur die Werte von F(t; y) für (t; y) auf dem besten Pfad tatsächlich für die Wiederherstellung (recovery) von relevant sind und die übrigen Werte weitgehend berechnet werden, um nachzuweisen, daß wirklich der beste Pfad ist. Der ICP strebt an, die gesamte Decodierberechnung zu reduzieren, indem er F(t; y) so wenig wie möglich für (t; y) evaluiert, wenn sich letzterer nicht an befindet.

Der ICP basiert auf dem folgenden Lemma, dessen Nachweis einfach ist. Angenommen, U ist eine Funktion, die F einen oberen Grenzwert zuweist, so daß für jedes t und y gilt:

U(t; y) ≥ F(t; y) (23)

Für jeden Pfad π wird U(π) definiert durch:

U(π) [U(ti; ξi) + log ati](24)

und F(π) analog dazu. Dabei ist zu beachten, daß F(π) lediglich die Pfadwahrscheinlichkeit L(π) ist, angegeben durch (10). Angenommen, ist ein vollständiger Pfad, welcher U maximiert, so daß für jedes π gilt: U( ) ≥ U(π). Wenn dann

U( ) = F( ) (25)

ist es einfach zu zeigen, daß auch F und somit L maximiert.

Der ICP findet eine Sequenz vollständiger Pfade auf, die eine Sequenz von U Funktionen maximiert. Zu Anfang wird U durch eine obere Grenzfunktion H angegeben, als eine Heuristik bezeichnet, bei der davon ausgegangen wird, daß sie sich berechnungsseitig viel weniger aufwendig evaluieren läßt als F. Bei der weiteren Abarbeitung des ICP wird U neu definiert, indem einige der H-Werte durch F-Werte ersetzt werden, die durch das eigentliche Decodieren von Bildreihen berechnet werden. Der ICP endet, wenn bei jedem Übergang in U( i; j) = F( i; j) ist.

In Fig. 7 ist die grundlegende ICP-Prozedur dargestellt. Die Eingaben in den ICP sind die oberste Teilquelle G&sub0; einer zerlegbaren Markowschen Quelle, eine Prozedur, die zum Berechnen von F(t; y) für jedes beliebige t und y aufgerufen werden kann, und eine Prozedur, die H(t; y) berechnen kann. Die ICP-Prozedur erhält zwei interne Daten-Matrizen aufrecht, die als (t; y) indexiert sind. Die Elemente der Matrix U werden mit den Werten von H initialisiert, bevor die Iteration beginnt. Wie bereits erwähnt, werden im Verlauf der Iteration einige der Elemente von U mit Ist-Werten von F aktualisiert. Jedes Element der Matrix A ist ein boolesches Flag, welches angibt, ob das entsprechende Element von U ein oberer Grenzwert (H) oder ein tatsächlicher (F)-Score ist; A(t; y) = ist wahr, wenn U(t; y) = F(t; y).

Bei jedem Iterationslauf wird (22) durch die dynamische Programmierung mit Hilfe von U anstelle von F errechnet und der beste Pfad ermittelt. Bei jedem Übergang wird i , falls das Matrixelement U( i; l) ein oberer Grenzwert ist, durch F( i; l) ersetzt und A( i; ξl) fortgeschrieben. Die Iteration wird solange fortgesetzt, bis U( i; ξj) für jedes i ein Ist-Score ist. Das frühere Lemma gewährleistet, daß das abschließende äquivalent zu dem Ergebnis einer vollständigen Viterbi- Decodierung ist.

Der grundlegende ICP-Algorithmus kann erweitert werden, indem fortgeschriebene Werte von U( i; ξj) die verfeinerten Obergrenzen auf die nahegelegenen Matrixelemente fortpflanzen dürfen; ein Beispiel dafür wird im nächsten Abschnitt angegeben.

3. Heuristische ICP-Funktionen

Eine heuristische Funktion im ICP ist eine Obergrenze H(t; y) für den Ist-Score

F(t; y) L(nF; χnF, y nI; χnI, y - Δyt; t)

für jeden rekursiven Übergang t, an dem n&sub1; und nF den Anfangs- bzw. den Endknoten von St bilden. In diesem Abschnitt werden zwei Arten von heuristischen Funktionen entwickelt. Die gewichtete Projektionsheuristik ist eine Obergrenze an F(t; y) im Hinblick auf das horizontale Projektionsprofil , wobei z&sub1; die Anzahl von 1' in Reihe i des beobachteten Bildes Z ist. Die Heuristik der angrenzenden Reihe ist eine Obergrenze an F(t; y) im Hinblick auf F(t; y-1) oder F(t; y+1). Sie kann am Ende jedes Durchlaufs im ICP zum Fortschreiben von Einträgen in U genutzt werden, die sich neben den neuberechneten Werten von F( i; l) befinden.

Allgemein hängt die Form einer heuristischen Funktion vom Kanalmodell ab. Im vorliegenden Abschnitt wird davon ausgegangen, daß ein asymmetrischer Bit-Flip- Kanal ist, in dem jedes Pixel des Idealbildes Q während der Entstehung des beobachteten Bildes Z unabhängig perturbiert wird. Die Wahrscheinlichkeit, mit der ein Vordergrund-Pixel (schwarz, 1) in Q als 1 in Z weiterbesteht, ist gleich α&sub1;. Ebenso ist die Wahrscheinlichkeit, daß eine 0 als 0 beobachtet wird, α&sub0;. Man geht davon aus, daß die Geräuschparameter über das Bild hinweg konstant sind. Mit diesen Annahmen können wir zeigen, daß

wobei Q die Anzahl von 1 in Q und Q Λ Z das bitmäßige UND von Q und Z[8] ist. Normalerweise ist α&sub0; ≥ 0,5 und α&sub1; ≥ 0,5, was auch unserer Annahme im vorliegenden Fall entspricht.

Da jedes Pixel von Q unabhängig vom Kanal perturbiert wird, folgt daraus, daß Q Λ Z für ein feststehendes Q eine binomisch verteilte Zufallsvariable mit einem Mittelwert α&sub1; Q und einer Varianz α&sub1;(1-α&sub1;) Q ist. Die heuristischen Funktionen in diesem Abschnitt beruhen auf einer Annäherung dieser Verteilung mit einer normalen Verteilung.

3.1 Gewichtete Projektionsheuristik

Bei der gewichteten Projektionsheuristik handelt es sich um eine strenge probalistische Formulierung eines gewöhnlichen ad hoc-Ansatzes zum Erfassen von Textzeilen. Da Pr{π} ≤ 1 und Q Λ Z ≤ Q , folgt aus (10) und (27), daß

wobei der beste vollständige Pfad in t ist, der bei (XnI(St),y) endet, und der Einfachheit halber wird Q als Q geschrieben. Die gewichtete Projektionsheuristik verwendet die rechte Seite von (28) als H(t; y) mit einer Schätzung der maximalen Wahrscheinlichkeit (maximum likelihood - ML) von Q , die aus dem horizontalen Projektionsprofil des beobachteten Bildes errechnet wird.

Wenn das horizontale Projektionsprofil des zugrundeliegenden Vorlage Q bezeichnet, dann

Q = qi (29)

und W - q&sub1; ist die Anzahl von 0 in der Reihe i von Q. Die gewichtete Projektionsheuristik basiert auf der Annahme, daß das Projektionsprofil für jedes Q aus einer gegebenen Quelle die gleiche Form hat, so daß

qi = hi Q (30)

wobei h ein quellenabhängiger Vektor aus nichtnegativen Konstanten ist, die zusammen Eins ergeben. Bei einfachen Textzeilenquellen kann das Profil als eine lineare Kombination der Profile der einzelnen Zeichenvorlagen berechnet werden, gewichtet nach der relativen Zeichenhäufigkeit.

Da jedes Vorlagenpixel unabhängig vom Kanal perturbiert wird, folgt daraus, daß die Komponenten von bei gegebenem Q unabhängig und binomisch verteilt sind und Mittelwerte

ui = (α&sub1; + α&sub0; - 1)hi Q + (1 - α&sub0;)W (31)

und Varianzen

σi² = (α&sub1; + α&sub0; - i)(α&sub0; - α&sub1;)hi Q + α&sub0;(1 - α&sub0;)W (32)

aufweisen.

Wenn die binomischen Verteilungen wie normal angenähert werden, dann:

Die ML-Schätzung von Q , als , bezeichnet, findet man mit Hilfe des Logarithmus aus (33), der in bezug auf Q differenziert und mit Null gleichgesetzt wird. Nimmt man an, daß der Kanal annähernd symmetrisch ist, so daß α&sub0; α&sub1; ist, dann läßt sich der entstehende Schätzwert wie folgt vereinfachen:

Der zweite Term des Zählers ist ein konstanter positiver Bias-Term. Darüber hinaus ist der Nenner positiv, da α&sub0; und α&sub1; laut Annahme größer als 0,5 sind. Da wir an einer oberen Grenze interessiert sind, kann (34) weiter vereinfacht werden, indem der zweite Term des Zählers weggelassen wird, wodurch ein Schätzwert entsteht, der eine lineare Kombination von Reihenprojektionen zi darstellt. Die gewichtete Projektionsheuristik ergibt sich aus der Substituierung dieses linearen Schätzwertes in (28), woraus sich die folgende Gleichung ergibt:

Hwp(t; y) = κwp hizi (35)

wobei

eine Konstante ist.

Fig. 23 ist ein Pseudocode, der zeigt, wie die gewichtete Projektionsheuristik berechnet werden kann.

Zwar definiert (36) κWP als eine Funktion der Kanalparameter, doch es könnten auch andere Verfahren zum Bestimmen eines geeigneten Wertes zur Anwendung kommen, wie beispielsweise die manuelle Optimierung oder Folgerungen aus Probedaten.

3.2 Nachbarreihen-Heuristik

Durch die Nachbarreihen-Heuristik wird die Beobachtung in eine Formel gebracht, daß F(t; y) sich normalerweise von einer Reihe zur nächsten nicht sehr verändert. Folglich können die während eines ICP-Laufs berechneten F-Werte dazu verwendet werden, Obergrenzen an benachbarten Werten abzuleiten, die enger als die anfänglichen Grenzen in U sein können.

Die Nachbarreihen-Heuristik geht davon aus, daß der bei y-1 endende beste Pfad durch t identisch mit dem besten Pfad ist, der bei y endet, d. h.

(y - 1) = (y)(37)

Somit ist Pr{ (y)} = Pr{ (y-1)} und

Q (y - 1) = Q (y)[(0, -1)] (38)

was einer einfachen vertikalen Verschiebung der zusammengesetzten Vorlage Q (y) entspricht. Wenn wir

ΔF F(t; y) - F(t; y - 1) (39)

definieren, so erhalten wir

ΔF = L(Z Q (y)) - L(Z Q (y)[(0, -1)]) (40)

welche mit (27) kombiniert und wie folgt vereinfacht werden kann:

ΔF = κ&sub1; [ Q¹&sup0; Λ Z - Q&sup0;¹ Λ Z ] (41)

wobei,

und

die Menge an Vordergrundpixeln an der unteren Grenze von Q sind, und

die Menge Hintergrundpixel an der Obergrenze von Q bildet.

Da jedes Element von Q&sup0;¹ einem 0 → 1-Übergang in Richtung eines größer werdenden y entspricht und jedes Element von Q¹&sup0; einem 1 → 0-Übergang entspricht, so folgt daraus, daß Q&sup0;¹ = Q¹&sup0; . Wir nehmen an, daß die Bildquelle ergodisch ist, so daß

Q¹&sup0; = p&sub1;&sub0; Q (45)

wobei

p&sub1;&sub0; Pr {q(x, y + 1) = 0 q(x, y) = 1} (46)

= 1 - p&sub1;&sub1; (47)

eine Eigenschaft der Quelle ist, die von Q unabhängig ist.

Nunmehr sind Q¹&sup0; Λ Z und Q&sup0;¹ Λ Z statistisch unabhängig und binomisch verteilt, wobei sie Mittelwerte α&sub1;p&sub1;&sub0; Q bzw. (1 - α&sub0;)p&sub1;&sub0; Q und Varianzen α&sub1;(1 - α&sub1;)p&sub1;&sub0; Q bzw. α&sub0;(1 - α&sub0;)p&sub1;&sub0; Q aufweisen. Somit ist der Mittelwert von ΔF

uΔF = κ&sub1;p&sub1;&sub0; Q (α&sub1; + α&sub0; - 1) (48)

und die Varianz

σΔF² = κ&sub1;²p&sub1;&sub0; Q [α&sub1;(1 - α&sub1;) + α&sub0;(1 - α&sub0;)] (49)

Bei der normalen Annäherung kann δ&sub1; so gewählt werden, daß

ΔF ≤ uΔF + δ&sub1;σΔF (50)

mit hoher Wahrscheinlichkeit gewährleistet ist. Wenn beispielsweise δ&sub1; = 3, dann liegt die Wahrscheinlichkeit von (50) bei 0,9987. Nach dem Kombinieren mit (48) und (49) und dem Umstellen wird aus (50):

ΔF ≤ κ&sub1;p&sub1;&sub0; Q α&sub1; + α&sub0; - 1)(1 + &sub1;) (51)

wobei

Bei ausreichend großem Q kann &sub1; durch eine konstante Obergrenze ersetzt oder vollkommen weggelassen werden.

Als nächstes ermitteln wir mit Hilfe von (27) eine Obergrenze für Q für F(f, y). Da Q Λ Z einen Mittelwert α&sub1; Q und eine Varianz α&sub1;(1 - α&sub1;) Q hat, läßt sich die normale Annäherung auf die Untergrenze L(Z Q) anwenden mit Hilfe von

wobei

und δ&sub2; wird entsprechend gewählt. Wie schon zuvor, kann auch &sub2; bei großem Q durch eine konstante Obergrenze ersetzt werden. Wenn der Beitrag von log Pr{ } zu F(t; y) vernachlässigt wird, erhalten wir

F(t; y) L(Z Q) (55)

ein Ausdruck, der mit (53) kombiniert werden kann und damit

ergibt, wobei

κ&sub2; log + κ&sub1;α&sub1;(1 - &sub2;) (57)

Letztendlich können (51) und (56) kombiniert und umgestellt werden, wodurch sich

F(t; y) ≤ κarF(t; y - 1) (58)

ergibt, wobei

Wenn &sub1; und &sub2; weggelassen werden, vereinfacht sich der Ausdruck weiter zu

und aus der Nachbarreihen-Heuristik wird

Har(t; y) = κarF(t; y - 1) (61)

Fig. 24 ist ein Pseudocode, der angibt, wie die Nachbarreihen-Heuristik errechnet werden kann.

Zwar begrenzt (61) F(t; y) in bezug auf F(t; y - 1), doch es ist klar, daß ähnliche Grenzen auch bei F(t; y ±i) für andere Werte von i abgeleitet werden können. Wie bereits erwähnt, können beim Einstellen von κar auch Verfahren, wie die manuelle Optimierung und das Folgern aus Daten, als Alternativen zu (59) zum Einsatz kommen.

3.3 Textspaltenbeispiel

In Fig. 8 ist die Projektionsgewichtungsfunktion h&sub1; für die horizontale Textzeilen- Teilquelle G&sub1; aus Fig. 6 dargestellt. Die Funktion wurde berechnet, indem die Einzelzeichen-Projektionsfunktionen für die Teilmenge der 12pt Adobe Times Roman Schrift, welche aus Groß- und Kleinbuchstaben, den Ziffern und 8 Interpunktionssymbolen besteht, übereinandergelegt wurden. Die übereinandergelegten Projektionen wurde nach der relativen Häufigkeit des Vorkommens in einem zufällig gewählten Textstück gewichtet.

In Fig. 9 ist ein Bild zu sehen, welches 10 Zeilen eines zufällig gewählten Times Roman-Textes enthält. Die entsprechenden Werte der gewichteten Projektionsheuristik Hwp und der tatsächliche Score F für die Teilquelle G&sub1; sind in Fig. 10 als Funktionen der y-Koordinate der Bildreihe dargestellt.

4. Konvertierung der rekursiven Quellen in eine zerlegbare Form

Beim ICP ist es erforderlich, daß das Bildquellenmodell zerlegbar ist. In bestimmten Situationen mag das von einem Anwender erzeugte Modell zerlegbar sein, woraufhin der ICP direkt angewendet werden kann. Oft führt jedoch der natürliche Aufbau einer Klasse von Bildern zu einem Modell, das rekursiv, aber nicht zerlegbar ist. Dabei ist zu beachten, daß die Zerlegbarkeit ein Attribut der Form eines Modells ist und keine inhärente Eigenschaft der Bildquelle. Daher ist es möglich, daß eine gegebene nicht zerlegbare, rekursive Quelle äquivalent zu einer bestimmten zerlegbaren Quelle ist und zudem die Umwandlung in eine zerlegbare Form algorithmisch erfolgen kann. Der vorliegende Abschnitt beschreibt eine erfindungsgemäße einfache Prozedur zur Umwandlung rekursiver Quellen in eine zerlegbare Form. Bei jeder mittels Algorithmus erzeugten zerlegbaren Form ist gewährleistet, daß sie dem ursprünglichen Modell entspricht.

Der erste Schritt der Prozedur ist einfach und besteht aus dem Abflachen der rekursiven Eingangsquelle G zu der äquivalenten eingeschränkten Quelle , wie bereits beschrieben. Anschließend versucht der Algorithmus, eine zerlegbare Quelle zu erstellen, die äquivalent zu ist. Ein Schlüsselfaktor, der die Separabilität einer eingeschränkten Quelle bestimmt, ist die Anzahl von Knoten, die bei x eng beschränkt sind. Im typischen Fall werden die Positionsschranken vom Anwender für eine kleine Teilmenge von Knoten vorgegeben. Der zweite Schritt der Konvertierungsprozedur, deren Durchführung freigestellt ist, breitet die anwenderspezifischen Schranken auf die anderen Knoten des Modells aus. Der letzte Schritt der Prozedur ist die eigentliche Separation der eingeschränkten Quelle.

Zuerst werden wir die Separation und anschließend die eingeschränkte Ausbreitung erläutern.

4.1 Konvertierung von eingeschränkten Quellen in eine zerlegbare Form

Fig. 11 faßt die Struktur der vom Algorithmus erzeugten zerlegbaren Quelle zusammen. Dabei soll eine eingeschränkte Markowsche Quelle sein und NTC die Menge an Knoten, die bei x eng beschränkt sind. Aus den Knoten in NTC werden Knoten der obersten Teilquelle G&sub0;. Der Anfangs- und der Endknoten von G&sub0; werden als jene von genommen, und wie bereits erwähnt, befinden sich diese Knoten typischerweise in NTC. Aus den Übergängen von , welche Knoten in NTC verbinden, werden einfache Übergänge in G&sub0;.

Bei jedem Knotenpaar (ni, nf) NTC · NTC soll (ni, nf) den Teilgraphen von kennzeichnen, der durch Entfernen aller Knoten von NTC mit Ausnahme von ni und nf, aller mit den entfernten Knoten verbundenen Verzweigungen, aller Verzweigungen, die zu ni gelangen, aller Verzweigungen, die von nf ausgehen, und aller Verzweigungen von ni zu nf gebildet werden. Wenn ein Pfad in (ni; nf) von ni zu nf vorhanden ist, dann umfaßt G&sub0; einen rekursiven Übergang von ni zu nf, wobei die zu jenem Übergang gehörende Teilquelle G(ni; nf) der Teilgraph von (ni; nf) ist, der sowohl mit ni als auch mit nf verbunden ist. Der Anfangs- und der Endknoten von G(ni; nf) sind Kopien von ni und nf. Einfach ausgedrückt, G(ni; nf) stellt die Pfade in von ni zu nf dar, die nicht in einen eng begrenzten Knoten eintreten, ehe sie an nf enden.

Wenn jedes G(ni; nf) eine konstante Verschiebung hat, dann bildet G&sub0; plus der Satz von G(ni; nf)-Teilquellen eine zerlegbare Quelle. Andernfalls ist das Ergebnis eine rekursive Quelle, die nicht zerlegbar ist.

Die obige Konstruktion erzeugt eine zerlegbare Quelle, bei der G&sub0; rekursive Übergänge enthält und wo jede Teilquelle von einem einzelnen rekursiven Übergang aufgerufen wird. Das Modell läßt sich vereinfachen, indem G(ni; nf) in Sätze von äquivalenten Teilquellen untergliedert wird und nur ein Element aus der Äquivalenzklasse zurückbehalten wird. Wir haben festgestellt, daß die Viterbi-Decodierung mit dieser vereinfachten zerlegbaren Quelle of wesentlich schneller als mit der ursprünglichen eingeschränkten Quelle ist. Damit kann die Abflachung, gefolgt von der Separation, sogar dann von Vorteil sein, wenn der ICP nicht angewendet wird.

4.2 Ausbreitung von Knotenpositionsschranken

Das vorrangige Ziel der Fortpflanzung von Schranken besteht darin, aus den vom Anwender vorgegebenen Zwangsbedingungen einen Satz implizierter Schranken für die übrigen Knoten des Modells abzuleiten. Wie nachfolgend noch deutlich wird, gibt es auch ein zweites Ergebnis, welches darin besteht, daß einige der vom Anwender vorgegebenen Schranken infolge der Schrankenausbreitung von anderen Knoten eingeengt werden. Zur Vereinheitlichung können wir annehmen, daß jeder Knoten eine anwenderspezifische Schranke hat und das Ziel darin besteht, diese einzuengen. Falls keine Schranke explizit angegeben ist, geht man von Cn[-∞,+∞] aus. Die Positionsschranken für x und y werden getrennt fortgepflanzt.

Zur Vereinfachung wird der bereits eingeführte Begriff für Vektormengen in dem vorliegenden Abschnitt verwendet, um die skalaren Koordinaten und Schranken anzugeben. So bezeichnet beispielsweise Cn ein Schranken-Intervall (und kein Rechteck), ξ bezeichnet eine skalare Pfadposition (und keinen Vektor), die Verzweigungs-Verschiebungen werden Skalare sein, usw.

Fig. 12 zeigt ein einfaches Beispiel, welches die Prinzipien der eingeschränkten Schrankenausbreitung verdeutlicht. Nimmt man, die Knoten n&sub1;, n und n&sub2; haben vom Anwender vorgegebene Schranken C&sub1;, Cn bzw. C&sub2; und betrachtet man die Auswirkungen dieser Schranken auf die möglichen Werte der Pfadposition ξ am Knoten n., so bedeutet die explizite Schranke bei n in erster Linie, daß

χnl ≤ ξ ≤ Xnu (62)

für jeden zugelassenen Pfad halten muß. Da allerdings ein Pfad, der in n eintritt, gerade erst n&sub1; verlassen haben muß, erfüllt ξ aufgrund der Schranke bei n&sub1; auch die folgende Bedingung:

χ&sub1;l + Δx&sub1; ≤ ξ ≤ χ&sub1;u + Δx&sub1; (63)

Und weil genauso alle Pfade, die n verlassen, sofort in n&sub2; eintreten, wird auch

χ&sub2;l - Δx&sub2; ≤ ξ ≤ χ&sub2;u - Δx&sub2; (64)

anhalten.

nl = max(χ&sub1;l + Δx&sub1;, χ&sub2;l - Δx&sub2;, χnl,) (65)

nu = min(χ&sub1;u + Δx&sub1;, χ&sub2;u - Δx&sub2;, χnu) (66)

oder in Set-Notation

wobei

nf = C&sub1; Δx&sub1; (68)

als vorwärts fortgepflanzte Schranke bezeichnet wird,

nr = C&sub2; Δx&sub2; (69)

die Rückwärts-Schranke ist und und die Operatoren sind, die ein Intervall um eine spezifische skalare Verschiebung translatieren. Schranke n kann weiter eingeschränkt werden, indem beachtet wird, daß C&sub1; und C&sub2; in (68) und (69) durch &sub1; und &sub2; ersetzt werden können. Schließlich verallgemeinern sich (68) und (69) bei Knoten mit mehreren Eingabe- und Ausgabeverzweigungen zu:

bzw.

Die Fortpflanzung von Positionsschranken schließt das Lösen der Gleichungen (67), (70) und (71) für jedes n ein, welches der Grenzbedingung unterliegt, daß die Lösungen für den Start- und Endknoten bestimmte Intervalle aufweisen. Typische Grenzbedingungen sind nI = [0, 0] und wF = [W, W], wobei W die Bildbreite ist. Das Lösen der Schrankengleichungen ist kompliziert, weil die Vorwärts- und die Rückwärts-Schranken durch (67) gekoppelt werden und Zyklen in der Quelle zu rekursiven Abhängigkeiten führen. Eine Möglichkeit, diese Schwierigkeit einzudämmen, besteht darin, die Forderung weniger streng zu handhaben, daß die berechneten Schranken so eng wie möglich sein müssen. Solange die anwenderspezifischen Schranken erfüllt sind, ist die einzige Konsequenz, daß das Decodiergitter größer als nötig sein wird und/oder nicht eng genug eingeschränkte Knoten identifiziert werden, um die Quelle zu separieren. Daher schauen wir uns nach Abwandlungsmöglichkeiten für die Schrankengleichungen um, durch welche sich die Lösungsintervalle vergrößert werden. Konkret führen wird Substitutierungen für Lt und Rt auf der rechten Seite von (70) und (71) durch.

Aus (67) ergeben sich dann die folgenden Beziehungen:

n nf (72)

n Cn(73)

n nr (74)

Wir modifizieren (70) durch Ersetzung von Lt mit , definiert durch

falls Cn ein endliches Intervall ist, ansonsten (75)

wodurch sich

ergibt.

Genauso wird aus (71)

wobei nr¹ analog definiert ist. Primär wird durch diese Substituierungen bewirkt, daß die Vorwärts- und Rückwärtsschranken entkoppelt und einzeln fortgepflanzt werden können. Wir werden hier näher auf die Ausbreitung von Vorwärtsschranken eingehen. Die Ausbreitung von Rückwärtsschranken ist ähnlich und reduziert sich darauf, Vorwärtsschranken in der Transponierten von G fortzupflanzen, die durch Richtungsumkehr jedes Übergangs und Ersetzen jeder Verzweigungsverschiebung durch ihre negative entstehen.

Wenn n endlich ist (d. h. der Anwender tatsächlich eine Schranke für den Knoten n) angegeben hat, dann erscheint nf nicht auf der rechten Seite von (76). Dadurch ist die Ausbreitung der Vorwärtsschranke in G äquivalent zur Fortpflanzung in der modifizierten Quelle G', die durch Aufspaltung jedes endlich eingeschränkten Knotens n in zwei Knoten ni und nº abgeleitet wurde, wobei ni die eingehenden Verzweigungen von n und nº erbt und nº die ausgehenden Verzweigungen sowie die Schranke n erbt. Als Beispiel ist die Aufspaltung des Knotens n aus Fig. 12 in Fig. 13 dargestellt.

Der Vorteil des Aufspaltens der eingeschränkten Knoten besteht darin, daß die Fortpflanzung von Vorwärtsschranken in G' äquivalent zum Auffinden von Pfaden mit einer minimalen und maximalen Verschiebung bei Graphen ist, die einfache Ableitungen von G' sind. Die oberen und unteren Grenzen von n = [ , ] werden separat ermittelt. Die unteren Grenzen werden mit Hilfe des Graphen aus Fig. 14 berechnet, bei dem aus den anwenderspezifischen unteren Grenzen Verschiebungen an den Verzweigungen werden, die von ns ausgehen. Fortgepflanzt werden die unteren Grenzen durch Auffinden der minimalen Pfadverschiebung von ns zu jedem Knoten von G'. Wenn der Knoten n gespalten wurde, ist die minimale Verschiebung zu ni; ansonsten ist die minimale Verschiebung zu n. Die oberen Grenzen nf werden ähnlich aufgefunden, indem die maximalen Pfadverschiebungen ermittelt werden, wenn die von n&sub5; ausgehenden Verschiebungen der Verzweigungen die oberen Grenzen von nf sind.

Beim Auffinden von Pfaden mit minimaler oder maximaler Verschiebung von einem Knoten mit nur einem Graphen handelt es sich um ein Standard-Graphenproblem (siehe Verweis [1] aus dem beiliegenden Anhang). In der vorliegenden Situation entsteht ein kleines Problem dahingehend, daß G' möglicherweise Zyklen einer Totalverschiebung ungleich Null enthalten kann, wodurch eine oder beide fortgepflanzte Schranken-Grenzen für einige Knoten unendlich sein kann bzw. können. Pfadfindungsalgorithmen zum Erkennen solcher Zyklen sind aber auch hinlänglich bekannt (siehe Verweis [1]).

Fig. 25 ist eine Darstellung eines Pseudocodes, die die Arbeitsschritte der Zerlegungsprozedur einer eingeschränkten Quelle aufzeigt.

4.3 Textspaltenbeispiel

In Tabelle 1 sind für jeden Knoten der Textspaltenquelle aus Fig. 5 die Werte von nf, nr, und n aufgezeigt, die mit Hilfe des Schrankenausbreitungsalgorithmus' berechnet wurden.

Wie bereits erwähnt, gibt Fig. 6 die Ergebnisse der Anwendung des Zerlegungsalgorithmus auf die eingeschränkte Textspaltenquelle an.

5. Experimentelle Ergebnisse

In Tabelle 2 sind die Ergebnisse eines einfachen Experiments zusammengefaßt, bei dem die Zeiten zum Decodieren einer Textseite mit Hilfe des Viterbi-Algorithmus und mit zwei ICP-Varianten verglichen werden. Die Probeseite war etwa 7 in · 10,5 in groß und enthielt einen zufällig gewählten Text, ähnlich wie in Fig. 9, der aus 45 Zeilen mit je 70 Zeichen bestand. Die Seite wurden mit 300 dpi gescannt, und die Abmessungen des binären Bildes waren W = 2134 und H = 3176. Anschließend wurde das Seitenbild mit den Times Roman-Textspaltenmodellen aus Fig. 5 (für die Viterbi-Decodierung) und aus Fig. 6 (für ICP) decodiert. Für ICP sind die Ergebnisse mit der gewichteten Projektionsheuristik Hwp und mit der Kombination aus Hwp und Nachbarreihen-Heuristik Har dargestellt. Die beobachtete ICP-Beschleunigung (in bezug auf Viterbi) lagen bei Hwp etwa bei 11 und bei der Kombination bei etwa 19.

Tabelle 2: Decodierzeit für eine Probe-Textseite mit Hilfe des Viterbi-Algorithmus und zwei ICP-Varianten.

Aus Tabelle 2 geht hervor, daß der ICP mit einer Heuristik eine große Beschleunigung der Decodierzeit ermöglicht, wohingegen der ICP mit beiden heuristischen Funktionen eine noch größere Zeitersparnis hervorruft.

Für den Leser ist es sicher auch hilfreich, die Funktionsweise des erfindungsgemäßen Decoders im Vergleich zum Viterbi-Algorithmus allein genau darzustellen. Für diesen Vergleich wird ein einfaches Beispiel herangezogen, bei dem eine zerlegbare Quelle, ähnlich jener aus Fig. 6, zum Decodieren eines kleinen, störungsfreien Bildes mit einer einzigen Textzeile, wie beispielsweise der ersten Zeile im Bild aus Fig. 9, verwendet wird. Da das Bild eine einzige Textzeile enthält, wird natürlich der beste Pfad durch die Quelle aus Fig. 6 die als G&sub1; gekennzeichnete rekursive Verzweigung genau einmal durchqueren. Damit reduziert sich die Bilddecodierung auf das Identifizieren der Bildreihe, an der diese Durchquerung stattfindet. Dies schließt wiederum das Ermitteln des Wertes von y ein, welcher F(t; y) für den G&sub1;-Übergang maximiert. In Tabelle 3 sind die hypothetischen Werte der gewichteten Projektionsheuristik Hwp (t; y) und der Ist-Score F(t; y) als Funktion des Reihen-Index y angegeben. Es wird davon ausgegangen, daß das Bild eine Höhe H = 10 aufweist. Aus der Tabelle wird deutlich, daß der maximale Wert von F(t; y) 1000 ist und bei y = 5 auftritt. Ein einfacher Viterbi-Decoder würde diesen Wert auffinden, indem er einfach alle 10 Werte von F(t; y) berechnet und sich den größten heraussucht. Das Ziel der heuristischen Suche besteht darin, die Anzahl von F(t; y)-Werten zu minimieren, die tatsächlich bei der Suche nach dem maximalen Wert berechnet werden.

Tabelle 3: Beispiele für gewichtete Reihenprojektionsheuristik-Scores HWp und Ist-Scores F

Die Arbeitsschritte des ICP-Algorithmus mit Hilfe der gewichteten Projektionsheuristik sind in Tabelle 4 zusammengefaßt. Jede Spalte der Tabelle unter "Iteration" steht für den Zustand der Score-Matrix U(t; y) zu Beginn der angegebenen Iteration. Anfangs werden die Elemente von U auf die Werte der heuristischen Scores Hwp eingestellt. Im Verlaufe des Algorithmus' werden einige Einträge durch Ist-Scores F(t; y) ersetzt. Diese Einträge sind in der Tabelle mit Sternchen '*' versehen.

Tabelle 4: Entwicklung von U(t; y) während des ICP mit gewichteter Reihenprojektionsheuristik. Die Sternchen kennzeichnen den Ist-Score.

Während der ICP-Iteration O ist der größte Wert von U(t; y) 1500, der bei y = 7 auftritt. Somit wird anfangs hypothetisch angenommen, daß der Text bei Reihe 7 vorliegt. Da der Wert 1500 ein heuristischer und kein Ist-Score ist, wird mit dem Quellenmodell G&sub1; eine vollständige Decodierung der Bildreihe bei y = 7 ausgeführt. Der entstehende Wert von F(t; 7), 700, wird als Ist-Score gekennzeichnet und in der U(t; y)-Matrix gespeichert.

Bei der Iteration 1 ist der größte Wert von U(t; y) 1300 und tritt bei y = 6 auf. Da es sich hierbei ebenfalls um einen heuristischen Score handelt, wird F(t; 6) berechnet und das Ergebnis, 900, in die Tabelle eingefügt. Der Vorgang dauert solange an, bis der größte Eintrag in der Tabelle einem tatsächlichen und keinem heuristischen Score entspricht. Es ist einfach, alle Schritte auszuführen und zu verifizieren, daß die größten Werte während der Iterationen 2-5 bei y = 8, 3, 5 bzw. 2 auftreten und sie sämtlich heuristische Scores sind. (Bei Gleichstand wird arbiträr die Reihe mit dem niedrigeren Wert y gewählt.) Und schließlich tritt während der Iteration 6 der größte Wert, 1000, bei y = 5 auf, bei dem es sich wiederum um einen Ist-Wert handelt. Damit ist der Algorithmus beendet. Beim Zählen der Sternchen in der letzten Spalte wird ersichtlich, daß 6 Werte von F(t; y) mittels ICP-Algorithmus berechnet wurden. Dies liegt unter den 10 Werten, die mit dem Viterbi-Decoder errechnet werden. In Tabelle 5 ist der ICP-Ablauf zusammengefaßt, wenn die Score-Heurisitik der Nachbarreihe zusätzlich zu der gewichteten Projektionsheuristik verwendet wird. Wie schon zuvor sind auch hier die anfänglichen Inhalte von U(t; y) die gewichteten Projektions-Scores, und der größte Wert während der Iteration beträgt 1500 und tritt bei y = 7 auf. Allerdings wendet der ICP nach dem Berechnen von F(t; 7) und Fortschreiben von U(t; 7) auf 700 als nächstes die Nachbarreihen-Heuristik bei y = 6 und y = 8 an. Bei diesem Beispiel nehmen wir an, daß der heuristische Koeffizient kar = 1,25 ist. Folglich liegt der heuristische Score für die Nachbarreihe bei 875 (1,25 · 700). Da dieser Wert niedriger als 1300 - der aktuelle Wert von U(t; 6) - ist und U(t; 6) ein heuristischer Score ist, wird der Wert von U(t; 6) auf 875 gesenkt. Genauso wird U(t; 8) von 1200 auf 875 reduziert. Dabei ist zu beachten, daß diese Werte noch immer heuristische Scores sind, daher sind sie nicht mit Sternchen versehen.

Tabelle 5: Entwicklung von U(t; y) während des ICP mit gewichteter Reihenprojektion und Score-Heuristik für die Nachbarreihen (kar = 1,25). Sternchen kennzeichnen den Ist-Score.

Während der Iteration 1 liegt der größte Wert von U(t; y) bei 1100 und tritt bei y = 3 auf. Wie schon zuvor, wird auch hier der Ist-Score F(t; 3) berechnet und U(t; 3) auf 600 aktualisiert. Der heuristische Score für die Nachbarreihe liegt bei 750. Dieser Wert ersetzt sowohl U(t; 2) als auch U(t; 4), da sie heuristische Scores sind, die größer als 750 (1000 bzw. 900) sind.

Während der Iteration 2 beträgt der größte Wert von U(t; y) 1100 und tritt bei y = 5 auf. Der Wert von F(t; 5) wird berechnet und U(t; 5) auf 1000 aktualisiert. In diesem Fall beträgt der heuristische Score für die Nachbarreihe 1250, was über den aktuellen Werten von U(t; 4) und U(t; 6) liegt. Dadurch werden diese angrenzenden Scores nicht modifiziert.

Zum Schluß beträgt der größte Wert von U(t; y) während der Iteration 3 1000 und tritt bei y = 5 auf. Da es sich bei ihm um einen Ist-Score handelt, ist der Algorithmus beendet. Zu beachten ist hierbei, daß nur 3 Werte von F(t; y) berechnet wurden. Dies ist weniger als bei dem Viterbi-Algorithmus, und auch weniger als bei dem ICP mit lediglich der gewichteten Projektionsheuristik.


Anspruch[de]

1. Erkennungsverfahren für textartige Bilder zum Zerlegen eines Bitmap-Bildes in eine Kombination aus Symbolvorlagen, die aus einer Vorlagenbibliothek auf der Grundlage von Pfaden ausgewählt werden, welche aus der Durchquerung eines Decodiergitters mit Hilfe von Markowschen Quellenmodellen und einer Viterbi- Decodierung ermittelt wurden, wobei die Viterbi-Decodierung einen 2-dimensionalen Viterbi-Algorithmus zum Berechnen eines Satzes von Wahrscheinlichkeitsfunktionen an jedem Punkt der Bildebene umfaßt, wobei jeder Punkt der Bildebene im Decodiergitter durch Knoten und Übergänge in jeden Knoten dargestellt wird und die Viterbi-Decodierung die Berechnung der Wahrscheinlichkeit des wahrscheinlichsten Pfades in jeden Knoten an jedem Punkt der Bildebene umfaßt und das Verfahren die folgenden Schritte umfaßt:

(a) Verwendung von zerlegbaren Quellenmodellen als Markowsches Quellenmodell,

(b) Identifizierung jener Bereiche des Decodiergitters, welche wahrscheinlich den besten Pfad enthalten, und

(c) Ausführung der vollständigen Viterbi-Decodierung nur in jenen Bereichen, die in Schritt (b) bestimmt wurden.

2. Verfahren gemäß Anspruch 1, wobei die Decodierung mittels ICP-Algorithmus durchgeführt wird, wie er in Abschnitt 2 der Beschreibung definiert ist.

3. Verfahren gemäß Anspruch 2, wobei der Schritt (b) ausgeführt wird, indem der Gesamtdecodier-Score mit zumindest einer heuristischen Funktion nach oben begrenzt wird.

4. Verfahren gemäß Anspruch 3, wobei eine erste heuristische Funktion verwendet wird, die auf den gewichteten Summen der Zählungen schwarzer und weißer Pixel in den Reihen des Bildes basiert.

5. Verfahren gemäß Anspruch 4, wobei eine zweite heuristische Funktion verwendet wird, die auf den vollständigen Decodier-Scores der benachbarten Reihen des Bildes beruht.

6. Verfahren gemäß einem der Ansprüche 1 bis 5, wobei das in Schritt (a) aus Anspruch 1 angewandte Markowsche Quellenmodell einem Umwandlungsprozeß unterzogen wird, um es so weit wie möglich in eine zerlegbare Form zu konvertieren, und das Ergebnis der Konvertierung verwendet wird.

7. Bilderkennungsprozeß auf der Grundlage eines Abbildungsmodells mit endlichen Zustandnetzen und eines gegebenen textartigen Eingabebildes, welches decodiert wird, und eines Bildnetzes mit einem Satz durch gerichtete Übergänge miteinander verbundener Knoten, mit einem Anfangs- und einem Endzustand und mit zu jedem Übergang gehörenden Attributen, welche ein Zeichen-Label, eine Bildvorlage und eine Übergangswahrscheinlichkeit umfassen, wobei ein das decodierte Bild darstellende Ausgabebild synthetisiert wird, indem die Verzweigungen des Bildnetzes durchquert werden und an jedem Knoten das zu jener spezifischen Verzweigung in jenen Knoten gehörende Vorlagenattribut, welches auf der Grundlage eines Maximal-Scores ausgewählt wird, der durch Auffinden des wahrscheinlichsten Pfades durch das von dem Abbildungsmodell und dem Eingabebild definierte Decodiergitter berechnet wird, in das Ausgabebild kopiert wird, wobei der Prozeß die folgenden Schritte umfaßt:

(a) Verwendung einer zerlegbaren Markowschen Quelle als Abbildungsmodell für die Netze,

(b) Unterteilen des Eingabebildes in Reihen,

(c) Bestimmung der Bildreihen, die dem besten Pfad durch die zerlegbare Markowsche Quelle entsprechen, wobei der Bestimmungsschritt umfaßt:

(i) Anwendung eines ICP-Algorithmus, wie er in Abschnitt 2 der Beschreibung definiert ist, mit einer gewichteten Reihen-Projektionsheuristik zum Erstellen einer Tabelle mit tatsächlichen und heuristischen Scores solange auf jene Reihen, die den höchsten heuristischen Scores entsprechen, bis der größte Eintrag in der Tabelle einem tatsächlichen Score entspricht.

8. Verfahren gemäß Anspruch 7, wobei Schritt (c)(i) zusätzlich mit einer Heuristik für die benachbarten Reihen ausgeführt wird.







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

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

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