DE69817916T2

DE69817916T2 - Ordnen von Textgruppen in einem Bild

Info

Publication number: DE69817916T2
Application number: DE69817916T
Authority: DE
Inventors: Jacob Cupertino Stolin
Original assignee: Adobe Systems Inc
Current assignee: Adobe Inc
Priority date: 1997-05-29
Filing date: 1998-04-30
Publication date: 2004-07-15
Anticipated expiration: 2018-05-01
Also published as: DE69817916D1; EP0881591A1; US6175844B1; EP0881591B1

Description

Papierdokumente können abgetastet und in einem Computer als Bilder gespeichert werden. Texterkennungstechniken, wie beispielsweise die optische Zeichenerkennung (OCR), können dann verwendet werden, um Text in diesen Bildern in ein Computer-editierbares Format, wie beispielsweise ASCII-Zeichen, umzuwandeln. Abgetastete Bilder können Text enthalten, der in mehrere, verschiedene Blöcke (z. B. mehrere Textspalten, Überschriften, Bildunterschriften, Fußnoten, Fußzeilen) strukturiert ist. Die Textblöcke können ferner durch relativ große Gebiete von Leerstellen und grafische Objekte (Linien, Bilder u. s. w.) getrennt sein. Text kann auch von einem Rahmen umgeben sein oder Einfügungen enthalten, welche den Text weiter in Blöcke trennen. Obwohl eine Person, welche die Seite liest, in der Lage sein kann, die richtige Reihenfolge der Textblöcke in dem Bild zu erkennen, kann es für ein OCR-Programm schwierig sein, den Text zu identifizieren (durch Aussondern der Nicht-Text-Komponenten, wie beispielsweise Leerräume und grafische Objekte) und den Text dann in der richtigen Lesereihenfolge zu gruppieren.
Beispiele für dem Stand der Technik entsprechende Anordnungen werden diskutiert in ITO et al.:, Field segmentation and classification in document image', Berichte der 6. Int. Konf. über Mustererkennung, München, Deutschland, 19. bis 22 Oktober 1982, Seiten 492–495, Bd. 1, 1982, IEEE New York, New York, USA, und BALESTRI et al.: ,A method for the correct ordering of typewritten lines', Signalverarbeitung: Theorien und Anwendungen, Grenoble, 5. bis B. September 1988, Bd. 3, Nr. Konf. 4. und 5. September 1988, Seiten 1609–1611.
ZUSAMMENFASSUNG
Gemäß der vorliegenden Erfindung wird ein Computerimplementiertes Verfahren zum Ordnen von Text in einem in einem Computer gespeicherten Bild bereitgestellt, wobei der Text in mehrere Blöcke gruppiert ist. Das Verfahren umfaßt:
Gruppieren des Textes in mehrere Gebiete;
Darstellen der Textgebiete als einen Graphen mit Knoten und Rändern,
Definieren jedes Textgebiets als Knoten in dem Graphen;
Definieren von Rändern zwischen den Knoten in dem Graphen;
Zuweisen von Gewichten zu den Rändern; und
Berechnen eines kürzesten Hamilton-Pfades durch die Knoten entsprechend den Randgewichten; und
Ordnen der Textgebiete gemäß der durch den berechneten kürzesten Hamilton-Pfad definierten Reihenfolge.
Ebenfalls gemäß der vorliegenden Erfindung wird ein auf einem Computer-lesbaren Medium befindliches Programm zum Ordnen von Text in einem in einem Computer gespeicherten Bild bereitgestellt, wobei das Programm Befehle enthält, die den Computer veranlassen:
den Text in mehrere Gebiete zu gruppieren;
die Textgebiete als Graphen mit Knoten und Rändern darzustellen;
jedes Textgebiet als Knoten in dem Graphen zu definieren;
Ränder zwischen den Knoten in dem Graphen zu definieren;
Gewichte den Rändern in dem Graphen zuzuweisen; und
einen kürzesten Hamilton-Pfad durch die Knoten entsprechend den Rändergewichten zu berechnen; und
die Textgebiete gemäß der durch den berechneten kürzesten Hamilton-Pfad definierten Reihenfolge zu ordnen.
Ferner wird gemäß der vorliegenden Erfindung eine Einrichtung zum Erkennen von Text in einem Bild bereitgestellt, welche aufweist: ein Speichermedium zum Speichern des Bildes; und einen betriebsmäßig mit dem Speichermedium gekoppelten Prozessor, der konfiguriert ist, um:
den Text in mehrere Gebiete zu gruppieren;
die Textgebiete in einem Graphen mit Knoten und Rändern darzustellen;
jedes Textgebiet als Knoten in dem Graphen zu definieren;
die Ränder zwischen den Knoten in dem Graphen zu definieren;
den Rändern in dem Graphen Gewichte zuzuweisen; und
einen kürzesten Hamilton-Pfad durch die Knoten in Übereinstimmung mit den Rändergewichten zu berechnen; und
die Textgebiete in Übereinstimmung mit der durch den berechneten kürzesten Hamilton-Pfad definierten Reihenfolge zu ordnen.
Ebenso wird gemäß der vorliegenden Erfindung ein in einem Computer implementiertes Verfahren zum Ordnen von Text in einem in einem Computer gespeicherten Bild bereitgestellt, wobei das Verfahren umfaßt:
Identifizieren einer Menge von Textblöcken; Aufteilen der Menge von Textblöcken in einzelne Untermengen von Textblöcken;
Darstellen der Textblöcke als Knoten in einem Graphen in jeder Untermenge;
Definieren gerichteter Ränder zwischen den Knoten in jeder Untermenge;
Zuweisen von Gewichten zu den gerichteten Rändern;
Berechnen eines kürzesten Hamilton-Pfades durch den Graphen in jeder Untermenge in Übereinstimmung mit den Randgewichten;
Ordnen der Textblöcke in jeder Untermenge in Übereinstimmung mit der durch den berechneten kürzesten Hamilton-Pfad definierten Reihenfolge; und
Verketten der Ordnung der Textblöcke in den Untermengen zu einer Endreihenfolge.
Die Erfindung hat einen oder mehrere der folgenden Vorteile. Die richtige Reihenfolge von mehreren, unterschiedlichen Textblöcken in einem erfaßten Bild kann durch ein Texterfassungsprogramm zuverlässig bestimmt werden.
Andere Merkmale und Vorteile der Erfindung werden aus der folgenden Beschreibung und aus den Ansprüchen deutlich.
KURZBESCHREIBUNG DER ZEICHNUNGEN
1 ist ein Flußdiagramm eines Texterfassungs- und Textordnungsprogramms in Übereinstimmung mit der vorliegenden Erfindung.
2a ist eine grafische Darstellung von Text in einem Bild, das in Blöcke eingeteilt ist.
2b ist eine grafische Darstellung von Knoten, welche die Textblöcke von 2a darstellen.
3 ist ein Graph, der die Knoten entsprechend den Textblöcken von 2a zusammen mit orientierten Paaren von Rändern enthält, die an zwei beliebige Knoten angrenzen.
4 ist eine grafische Darstellung eines optimalen Hamilton-Pfades durch die Knoten in dem Graphen von 3.
5 ist eine grafische Darstellung eines Textblocks.
6 ist ein Flußdiagramm eines Prozesses für die Unterteilung einer Seite in einzelne Teile.
7, 8 und 9 sind grafische Darstellungen von Textblöcken in Seitenteilen.
10 ist eine Blockdarstellung eines Computersystems.
DETALIIERTE BESCHREIBUNG
Es wird auf 1 Bezug genommen; es wird ein Computerimplementiertes Texterfassungsprogramm beschrieben, das die richtige Reihenfolge von Text, der in mehrere, unterschiedliche Blöcke in einem Bild gruppiert ist, zuverlässig identifizieren kann. Zuerst erfaßt und speichert das Programm ein Bild (Schritt 102). Als Nächstes identifiziert das Programm basierend auf herkömmlichen Seiten-Layout-Analysen die Textblöcke auf der Seite (Schritt 104). Beispielsweise kann das Bild als Dichte-Histogramme dargestellt werden, wobei sehr dichte Gebiete Nicht-Text-Objekte anzeigen, wie beispielsweise grafische Objekte, und Bereiche sehr geringer Dichte Zwischenräume anzeigen. Alternativ kann die Identifizierung der Textblöcke auch auf solchen Faktoren wie Nähe der Textblöcke zueinander, Schriftgröße und Vorhandensein von Leerzeichentrenn elementen und Blöcken grafischer Objekte basieren. So können beispielsweise Textzeichen auf einer Seite, obwohl sie horizontal ausgerichtet sind, durch einen breiten Zwischenraum getrennt sein, was anzeigt, daß die Zeichen in zwei verschiedenen Spalten angeordnet sind. Außerdem kann die Abschnittsüberschrift für die Textseite eine andere, größere Schriftart als der übrige Text aufweisen. Die Textzeichen können auch durch grafische Objekte getrennt sein, die auf der gesamten Seite verteilt sind.
Nachdem die Textblöcke in dem Bild identifiziert worden sind, unterteilt das Programm – wenn möglich – die Textblöcke in einzelne Untermengen oder Teile der Seite (Schritt 106). Viele Seiten können in kleinere Teile eingeteilt werden, die durch bestimmte Typen von Trennelementen getrennt sind. Diese einzelnen Teile können von dem Programm separat verarbeitet werden, wodurch die Komplexität der Feststellung der Reihenfolge der Textblöcke auf einer Seite reduziert wird. Schritte 108–116 in 1 werden für jeden identifizierten einzelnen Teil der Seite separat ausgeführt.
Um die Komplexität der Feststellung der Reihenfolge der Textblöcke in jedem Teil der Seite weiter zu reduzieren, kombiniert das Programm – wo es möglich ist – als Nächstes Textblöcke (Schritt 108). Häufig gibt es nur eine Möglichkeit, um zwei oder mehr Textblöcke zu ordnen. In derartigen Fällen können die Blöcke zu einem neuen einzigen Textgebiet kombiniert werden.
In dem beispielhaften Teil 200 einer Seite in 2a entsprechen die dunkler gefärbten Kästchen 202 und 204 den Nicht-Text-Objekten, wie beispielsweise grafischen Objekten. Ferner unterteilt eine vertikale Teilungslinie 206 den Text. In diesem Bild sind die identifizierten Textblöcke als Textblöcke 1– 8 gekennzeichnet. In jedem Teil der Seite bezeichnet dann das Programm jedes Textgebiet (ein Gebiet kann ein Textblock oder eine Gruppe von kombinierten Textblöcken sein) als einen Knoten eines Graphen (Schritt 110). In 2a können die Textblöcke 1 und 2 zu einem Textgebiet 12 kombiniert werden und die Textblöcke 6 und 7 können zu einem Textgebiet 67 kombi niert werden. Somit sind in 2b die Knoten V₁₂, V₃, V₄, V₅, V₆, und V₈ für die Textgebiete in 2a bestimmt. Die Positionen der Knoten sind nicht notwendigerweise geometrisch bezogen auf die Lage der Textblöcke 1-8 in dem Bild 200.
Als Nächstes definiert das Programm gerichtete Ränder (v_i, V_j) und (V_j, V_i) für jedes Knotenpaar V_i und V_j (Schritt 112) . Ein Paar gerichteter oder orientierter Ränder wird zwischen zwei beliebigen Knoten definiert, da die Möglichkeit besteht, daß – wie zwischen zwei beliebigen Textgebieten – ein Textgebiet vor dem anderen Textgebiet kommen kann. Die Knoten V₁₂, V₃, V₄, V₅, V₆₇ und V₈ zusammen mit den gerichteten Rändern zwischen jedem der Knoten definieren einen gerichteten oder orientierten Graphen G, wie in 3 gezeigt.
Das Verhältnis zwischen den Knoten V wird dann definiert (Schritt 114), indem den gerichteten Rändern (V_i, v_j) und (V_j, V_i) basierend auf einer Reihe von Faktoren Randlängen (oder Gewichte) zugewiesen werden. Zu diesen Faktoren gehören der Abstand zwischen zwei beliebigen Textblöcken, die Charakteristika (z. B. Zeilenanzahl, Schriftgröße, Zeilenabstand) der zwei Textblöcke und das Vorhandensein von Trennelementen (wie beispielsweise leerem Raum oder anderen Nicht-Text-Objekten) zwischen den Textblockpaaren. Die Randlängen basieren auf der Wahrscheinlichkeit, daß ein Knoten V_i vor seinem benachbarten Knoten V_j kommt. Je höher die Wahrscheinlichkeit, daß das Textgebiet i vor Textgebiet j kommt, desto geringer das Gewicht des Randes (V_i, v_j), und umgekehrt.
So ist beispielsweise in 3 das dem Rand (V₁₂, V₃) zugewiesene Gewicht viel geringer als das dem Rand (V₃, V₁₂) zugewiesene Gewicht, weil es viel wahrscheinlicher ist, daß Textgebiet 12 vor Textgebiet 3 kommt.
Als Nächstes findet das Programm unter Verwendung der für die Ränder des Graphen bestimmten Gewichte einen optimalen Hamilton-Pfad durch die Knoten V₁₂, V₃, V₄, V₅, V₆₇, V₈, indem „rohe Gewalt" (für kleine Graphen) oder herkömmliche heuristische Verfahren oder Näherungsverfahren verwendet werden, die ein Problem des Handlungsreisenden lösen (Schritt 116). Ein identifizierter optimaler Hamilton-Pfad wird in 4 ge zeigt, wobei der Pfad bei V₁₂ beginnt und nacheinander zu den Knoten V₃, V₄, V₅, V₆, und V₈ fortgesetzt wird. Als Nächstes kombiniert das Programm Teilreihenfolgen, die für die entsprechenden Teile der Seite gefunden wurden, zu einer Endreihenfolge π (Schritt 118).
Das folgende mathematische Modell wird für die Ausführung des Textordnungsprozesses definiert. Es wird auf 5 Bezug genommen; für ein Textgebiet A mit den Koordinaten (T,B,L,R) in einem zweidimensionalen X-Y-Raum sei Top (A) = T, Bot (A) = B, Lft (A) = L, (G1.1) Rgt (A) = R,und CntrX (A) = (L + R)/2, CntrY (A) = (T + B)/2, (G1.2)wobei L und R auf der X-Achse und T und B auf der Y-Achse liegen. Der Abstand zwischen zwei beliebigen Textgebieten A1 und A2 wird definiert als
Für jedes Paar von Textgebieten A_i, A_j wird eine Vorrangfunktion f(Ai,Aj) gebildet, so daß der Wert von f(Ai,Aj) um so geringer ist, je höher die Wahrscheinlichkeit ist, daß Ai Aj vorausgeht. Für K Textgebiete werden die Vorrangfunktionen f(Ai,Aj), i = 1 – K, j = 1 – K, i ≠ j, berechnet, welche zur Berechnung der Randlängen oder Gewichte zwischen den Knoten verwendet werden.
Bevor jedoch die Vorrangfunktionen f(Ai,Aj) gebildet werden, wird die Komplexität des Problems reduziert, indem (1) die Seite in verschiedene Teile unterteilt wird und (2) Textblöcke zu Gebieten kombiniert werden, wo es möglich ist.
Es wird auf 6 Bezug genommen; es wird der Schritt des Einteilens der Seite in mehrere Teile beschrieben. Eine Seite kann in unabhängige Teile eingeteilt werden, indem der fol gende rekursive Algorithmus angewendet wird. Das Programm erzeugt eine Menge SP von Seitenteilen P_i und initiiert sie durch Definieren der gesamten Seite als das Element der Menge SP (Schritt 300). Für jedes Element in SP sucht das Programm ein Teilungstrennelement, das durch das vorhandene Element verläuft (Schritt 302), wobei ein Teilungstrennelement als jedes beliebige Nicht-Text-Gebiet definiert werden kann, mit Ausnahme einer dünnen vertikalen Linie, welche ein Spaltentrennelement sein könnte. Wenn kein Teilungstrennelement gefunden wird (Schritt 304), wird der Prozeß gestoppt. Wenn ein Teilungstrennelement gefunden wird, wird das aktuelle Element in 2 neue Unterelemente geteilt, indem es entlang des ausgewählten Trennelements geteilt wird (Schritt 306). Das aktuelle Element wird von zwei neuen Unterelementen ersetzt und Schritte 302–306 werden wiederholt. Die Unterelemente bilden die Teile P_i der Seite . Somit SP = {P₁, P₂, ..., P_π} , und der Textordnungsprozeß wird an jedem Teil P_i einzeln ausgeführt, wobei die Ergebnisse für jeden Teil am Ende kombiniert werden, um die Endreihenfolge π zu bestimmen.
Um die Komplexität in jedem Seitenteil zu reduzieren, können zwei oder mehr Textblöcke oder Gebiete kombiniert werden (Schritt 108), wenn sie „horizontal verbunden" oder „vertikal verbunden" sind. Zwei Textgebiete A1, A2 werden als horizontal verbunden (siehe 7) bezeichnet, wenn die folgenden Bedingungen zutreffen:

(1) A1 und A2 sind horizontal ausgerichtet, das heißt, max (Top(A1), Top(A2)) < min(CntrY(A1), CntrY(A2)), und min(Bot(A1), Bot(A2)) > max(CntrY(A1), CntrY(A2));
(2) kein anderes Gebiet überlappt eine gemeinsame Begrenzungsbox von A1 und A2;
(3) A1 und A2 sind am oberen Ende blockiert, was bedeutet, es gibt keine Gebiete über A1 und A2 oder das nächstgelegene Gebiet A3 über A1 und A2 ist ein Sperrgebiet, das heißt Lft (A3) ≤ min(Lft (A1), Lft (A2) ), und Rgt (A3) ≤ max (Rgt (A1), Rgt (A2)); und
(4) A1 und A2 sind am unteren Ende blockiert, das heißt, es gibt keine Gebiete unter A1 und A2 oder das nächstgelegene Gebiet A3 unter A1 und A2 ist ein Sperrgebiet.

Wenn die Gebiete A1, A2 horizontal verbunden sind, ist ihre Teilreihenfolge von links nach rechts (von A1 zu A2 in
7) .
Zwei Textgebiete A1, A2 werden als vertikal verbunden (siehe 8) bezeichnet, wenn die folgenden Bedingungen zutreffen:

(1) A1 und A2 sind vertikal ausgerichtet, das heißt, max (Lft(A1), Lft(A2)) < min(CntrX(A1), CntrX(A2)), und min(Rgt(A1), Rgt(A2)) > max(CntrX(A1), CntrX(A2));
(2) kein anderes Gebiet überlappt ihre gemeinsame Begrenzungsbox;
(3) A1 und A2 sind an der linken Seite blockiert, das heißt, es gibt keine Gebiete an der linken Seite oder das nächstgelegene Gebiet A3 an der linken Seite ist ein Sperrgebiet, das heißt Top (A3) ≤ min (Top (A1), Top(A2)), und Bot(A3) ≥ max(Bot(A1), Bot(A2)); und
(4) A1 und A2 sind an der rechten Seite blockiert, das heißt, es gibt keine Gebiete an der rechten Seite oder das nächstgelegene Gebiet A3 an der rechten Seite ist ein Sperrgebiet.

Wenn die Gebiete A1, A2 vertikal verbunden sind, ist ihre Teilreihenfolge von oben nach unten (von A1 zu A2 in 8). Wenn ein Paar von (horizontal oder vertikal) verbundenen Gebieten A1, A2 gefunden wird, werden die Gebiete zu dem einzelnen Textgebiet A12 kombiniert. Die Begrenzungsbox des neuen Gebiets ist das kleinste Rechteck, das sowohl A1 als auch A2 umfaßt, so daß Top(A) = min (Top(A1), Top(A2)), Lft (A) = min (Lft (A1), Lft (A2)), Rgt (A) = max (Rgt (A1), Rgt (A2)), und Bot (A) = max (Bot(A1), Bot(A2)). (G1.4) Andere Parameter (wie beispielsweise Schriftgröße und Zeilenabstand) für das kombinierten Gebiet könnten aus dem größeren der Gebiete A1, A2 übertragen werden.
Der Kombinierungsprozeß kann wiederholt werden, bis keine weiteren verbundenen Gebiete gefunden werden.
In einigen Fällen kann die Reihenfolge der Textgebiete in einem Seitenteil einfach durch fortlaufendes Kombinieren verbundener Textgebiete identifiziert werden. Beispielsweise könnte in dem in 9 gezeigten Seiten-Layout die Lösung gefunden werden, indem die Textgebiete wie folgt kombiniert werden:
Kombinieren A5 und A6 zu A56;
Kombinieren A56 und A7 zu A567;
Kombinieren A2 und A567 zu A2567;
Kombinieren A2567 und A8 zu A25678;
Kombinieren A1 und A25678 zu A125678;
Kombinieren A125678 und A3 zu A1256783;
Kombinieren A1256783 und A4 zu A12567834.
Die resultierende Reihenfolge der unkombinierten Textblöcke ist dann A1, A2, A5, A6, A7, A8, A3 und A4.
Nachdem alle verbundenen Textgebiete kombiniert worden sind, wenn mehr als ein Textgebiet in einem Seitenteil übrig bleibt, wird die Reihenfolge der Gebiete bestimmt, indem der optimale Hamilton-Pfades eines Graphen G gelöst wird, der Knoten V enthält, die die unkombinierten Textgebiete repräsentieren.
Für K Textgebiete wird dies ausgeführt, indem zuerst die Vorrangfunktionen f(Ai,Aj), i ≠ j, i = 1 – K, j = 1 – K, für alle Textgebiete gebildet werden. Die Vorrangfunktionen werden verwendet, um den Rändern E_ij zwischen Knoten V_i und V_j Längen oder Gewichte zuzuweisen.
Die Vorrangfunktion wird definiert als
wobei K_loc die relative Lage der zwei Textgebiete Ai und Aj bewertet, K_dif die Ähnlichkeit (in Zeilenanzahl, Schriftgröße und Zeilenabstand) von Textgebieten bewertet und K_sep den Beitrag zur Funktion f aufgrund des Vorhandenseins eines trennenden Nicht-Text-Gebiets, sofern vorhanden, zwischen Ai und Aj widerspiegelt . Wie K_loc, K_dif und K_sep abgeleitet werden, wird nachstehend beschrieben.
Ein Graph G, der einem Seitenteil zugeordnet ist, wird wie folgt definiert: G ist ein gerichteter Graph mit K Knoten V₁, V₂, ..., V_k; jedes Knotenpaar V_i, V_j, i ≠ j , ist durch einen gerichteten Rand E_ij verbunden; eine nicht-negative Zahl W(E_ij) (als Gewicht oder Länge des Randes Eij bezeichnet) wird jedem Rand E_ij zugewiesen: W(Eij) = f(Ai, Aj), (G1.6)wobei F die durch G1. 5 definierte Vorrangfunktion ist.
Für eine gegebene Reihenfolge π (welche eine Permutation der Zahlen 1, 2, ..., k) ist, ist ein Hamilton-Pfad P(π) in dem Graphen G eine geordnete Menge von Knoten P(π) = {Vπ(1), Vπ(2), ..., Vπ(k)}. (G1.7)
Die Länge des Pfades P(π) wird definiert als:
Der kürzeste Hamilton-Pfad ist ein Hamilton-Pfad mit dem Minimalwert L (π) .
Jeder Hamilton-Pfad P(π) in dem zugeordneten Graphen G definiert eine Reihenfolge von Textgebieten in dem entsprechenden Seitenteil. Wie aus der Definition der Vorrangfunktion f folgt, ist die Wahrscheinlichkeit, daß π die richtige logische Reihenfolge der Textgebiete ist, um so größer, je kürzer der Hamiltonpfad P(π) ist. Daher stellt der kürzeste Hamilton-Pfad P(π) in dem Graphen G die Lösung bereit, um die Reihenfolge π der Textgebiete in einem Seitenteil zu finden.
Um den kürzesten Hamilton-Pfad zu finden, kann das Standardverfahren zu dessen Reduzierung auf das Problem des Handlungsreisenden angewendet werden. Zuerst wird ein zusätzlicher Knoten V₀ zu dem Graphen G hinzugefügt, wobei der Knoten V₀ durch die Ränder E_0j und E_j0 mit jedem Knoten V_j verbunden ist. Die Länge jedes Randes E_0j und E_j0 ist 0, d. h. W(E_0j) = W(E_j0) = 0. Als Nächstes wird eine kürzeste geordnete Schleife bzw. ein kürzester geordneter Zyklus C in dem Graphen G berechnet, indem ein Standardalgorithmus für die Lösung des Problems des Handlungsreisenden angewendet wird. Der kürzeste Hamilton-Pfad wird dann aus dem Zyklus C extrahiert, indem der zusätzliche Knoten V₀ aus dem Zyklus entfernt wird.
Wenn die logischen Reihenfolgen πj für die unabhängigen Teile P₁,..., P_k auf der Seite identifiziert worden sind, werden die Pfade πj, j = 1 – π, verkettet: π = (π1, π2, ..., πn) (G1. 9)
Da die Teile P unabhängig sind, spielt es keine Rolle, wie die Reihenfolgen π verkettet werden. Eine Alternative ist jedoch das Sortieren der Teile P in ansteigender Reihenfolge von y und dann x, wobei (x, y) die obere linke Ecke jedes Seitenteils ist.
In der verketteten Reihenfolge π werden kombinierte Textblöcke in Textgebieten herausgetrennt und in der richtigen Reihenfolge in eine Endreihenfolge π' angeordnet. Wenn somit π beispielsweise {12, 3, 7, 56, 4} ist, wird es modifiziert zu π' = {1, 2, 3, 7, 5, 6, 4}, um die Reihenfolge der Textblöcke A1– A7 zu definieren.
Die Endreihenfolge π' stellt somit eine Lösung für das Identifizieren der Reihenfolge von Textblöcken auf einer Seite bereit.
Wie in G1.5 dargelegt, werden die Vorrangfunktionen f(Ai,Aj), i ≠ j, i = 1 – k, j = 1 – k, basierend auf den Werten K_loc(Ai, Aj), K_dif(Ai, Aj) und K_sep(Ai, Aj) für k Textgebiete berechnet.
Ein Zeilenvorrang oder ein Spaltenvorrang kann ausgewählt werden. Wenn ein Zeilenvorrang ausgewählt wird, dann begünstigt das Textgebietsordnen das Ordnen in der X-Richtung. Wenn ein Spaltenvorrang ausgewählt wird, dann begünstigt das Textgebietsordnen das Ordnen in der Y-Richtung. Für die Gebiete A1 = (Tl,B1,L1,R1) und A2 = (T2,B2,L2,R2) wird die Komponente K_loc, welche einen wert hat, der von den relativen Koordinaten der Gebiete A1 und A2 abhängt, für Zeilen- und Spaltenvorrang unterschiedlich berechnet. Da K_loc von den relativen Lagen von A1 und A2 abhängig ist, wird K_loc(A1, A2) anders als K_loc(A2, A1) berechnet, wobei K_loc(A1, A2) verwendet wird, um f(A1, A2) zu berechnen, und K_loc(A2, A1) verwendet wird, um f(A2, A1) zu berechnen. Im Allgemeinen ist – aufgrund der Unterschiede bei der Berechnung von K_loc(A1, A2) und K_loc(A2, A1) – f(A1, A2) normalerweise nicht gleich f(A2, A1), weil ein Textgebiet vor dem anderen Textgebiet kommen wird. Die Berechnung von K_loc(A1, A2) oder K_loc(A2, A1) wird nachstehend für drei mögliche Fälle dargelegt. Da gemäß Definition zwei separate Gebiete einander nicht überlappen, ist der Fall, in welchem min(R1, R2) ≥ max(L1, L2) und min(B1, B2) ≥ max(T1, T2) nicht möglich und wird daher nicht berücksichtigt.
In einem ersten Fall überlappen die Textgebiete A1 und A2 einander in der X- oder Y-Achse nicht und A1 liegt links von und unter A2; das heißt: R1 < L2 und T1 > B2.
In diesem Fall wird der Wert K_loc, wenn der Spaltenvorrang ausgewählt wird, definiert als: Kloc(A1, A2) = Q1*|CntrX(A1) – CnrtX(A2)|, (G1.10)wobei Q1 ein einstellbarer Parameter mit einem Vorgabewert von 1 ist; und Kloc(A2, A1) = Q2*|A1, A2|, (G1.11) wobei Q2 ein einstellbarer Parameter mit einem Vorgabewert von 2 ist. Somit hat K_loc(A1, A2) einen geringeren wert als K_loc(A2, A1), welcher tendenziell A1 gegenüber A2 begünstigt, was mit dem ausgewählten Spaltenvorrang übereinstimmt.
Im ersten Fall wird der Wert K_loc, wenn der Zeilenvorrang ausgewählt wird, definiert als: Kloc(A1, A2) = Q3*|A1, A2|, (G1.12)wobei Q3 ein einstellbarer Parameter mit einem Vorgabewert von 4 ist; und Kloc(A2, A1) = Q4*|A1,A2|, (G1.13)wobei Q4 ein einstellbarer Parameter mit einem Vorgabewert von 1 ist. K_loc(A1, A2) hat einen größeren Wert als K_loc(A2, A1), welcher tendenziell A2 gegenüber A1 begünstigt, wenn im ersten Fall der Zeilenvorrang ausgewählt wird.
In einem zweiten Fall überlappen sich die Begrenzungen der Textgebiete A1 und A2 nicht in der X-Achse, aber sie überlappen sich in der Y-Achse, und das Gebiet A1 liegt links von dem Gebiet A2; das heißt: R1 < L2 und T1 ≤ B2.
In diesem Fall wird der Wert K_loc, wenn der Spaltenvorrang ausgewählt wird, definiert als: Kloc(A1, A2) = Q1*|CntrX(A1) – CnrtX (A2)|, (G1.14)und Kloc(A1, A2) = M1, (G1.15)wobei M1 ein großer Wert ist, welcher eingestellt werden kann auf M1 = 10*maxij|Ai, Aj|. (G1.16)
M1 ist somit als das Zehnfache des maximal möglichen Abstands zwischen zwei beliebigen Textgebieten in einem betrach teten Teil der Seite definiert. Im Allgemeinen begünstigt dies A1 gegenüber A2 bei der Berechnung von Kloc beträchtlich.
Im zweiten Fall wird der Wert K_loc, wenn der Zeilenvorrang ausgewählt wird, definiert als: Kloc (A1, A2) = Q4*|A1, A2|, und (G1.17) Kloc(A2, A1) = M1, (G1.18)wobei Q4 mit einem Vorgabewert von 1 einstellbar ist. Erneut wird A1 gegenüber A2 im Allgemeinen stark begünstigt.
In einem dritten Fall überlappen sich die Begrenzungen der Textgebiete nicht in der Y-Achse, aber sie überlappen sich in der X-Achse, und A1 liegt über A2; das heißt B1 < T2 und min(R1, R2) ≥ max(L1, L2) .
In diesem Fall wird der Wert K_loc sowohl für den Spaltenvorrang als auch für den Zeilenvorrang definiert als: Kloc(A1, A2) = Q5*|A1, A2|, (G1.19) undK_loc (A2, A1) = M1, (G1.20)wobei Q5 ein einstellbarer Parameter mit einem Vorgabewert von 1 ist. Im Allgemeinen begünstigen diese Berechnungen A1 gegenüber A2 beträchtlich.
Die Funktion K_dif(A1, A2) wird definiert als
wobei ml die Anzahl der Textzeilen in Gebiet Ai, s₁ die Textpunktgröße für das Gebiet Ai, l₁ der Abstand zwischen aufeinander folgenden Zeilen in Ai und Q6 ein einstellbarer Parameter (Vorgabewert ist 10) ist. Konkret repräsentieren s₁und l₁ die Höhe (in der Y-Richtung) einer Zeile. K_dif(A2, A1) entspricht K_dif(A1,A2).
Die Funktion K_sep(A1, A2) wird relativ zu einem Trennelement (Nicht-Text-Gebiet) B definiert und wird in Form eines horizontalen Extrusionsparameters E_hor(A, B) und eines vertikalen Extrusionsparameters E_vert(A, B) berechnet. Für ein Textgebiet A und ein Trennelement B wird der horizontale Extrusionsparameter E_hor(A, B) definiert als
Somit ist E_hor(A, B) größer als Null, wenn jeder der linken oder rechten Ränder des Textgebiets A in den von den linken und rechten Rändern des Trennelements B definierten Gebiet fällt.
In ähnlicher Weise wird ein vertikaler Extrusionsparameter E_vert(A, B) definiert als
Die Funktion K_sep(A1, A2) wird für die folgenden zwei möglichen Fälle wie folgt definiert.
In einem ersten Fall sind die Textgebiete A1, A2 vertikal getrennt; das heißt, die Gebiete A1, A2 überlappen sich nicht in der Y-Achse, definiert durch min(Bot(A1, Bot(A2)) < max(Top(A1), Top(A2)). In diesem Fall:
wobei Q7 ein einstellbarer Parameter (Vorgabe kann 10 sein) ist und die Summe Fa alle Trennelemente zwischen A1 und A2 enthält; d. h.: Top (B) > min (Bot (A1), Bot (A2)), undBot (B) < max (Top (A1), Top (A2)).
In einem zweiten Fall sind die Textgebiete horizontal getrennt; das heißt, die Gebiete A1, A2 überlappen sicht nicht in der x-Achse, wie definiert durch min(Rgt(A1,Rgt(A2)) < max (Lft(A1), Lft(A2)). In diesem Fall:
wobei die Summe Fa alle Trennelemente zwischen A1 und A2 enthält; d. h. Lft (B) > min (Rgt(A1), Rgt(A2)), undRgt (B) < max (Lft(A1), Lft(A2)).
Wenn K_loc, K_dif und K_sep für alle Kombinationen von A1, A2, ..., Ak berechnet worden sind, können die Vorrangfunktionen f(Ai,Aj), i ≠ j, i = 1 – k, j = 1 – k, gebildet und verwendet werden, um die Längen der verschiedenen Permutationen der Pfade P(π) zu finden, um den kürzesten Hamilton-Pfad P(π) zu identifizieren.
Es wird auf 10 Bezug genommen; das Texterfassungs- und -Ordnungsprogramm kann in digitalen elektronischen Schaltungen oder in Computer-Hardware, Firmware, Software oder in Kombinationen derselben, wie beispielsweise in einem Computersystem, implementiert werden. Das Computersystem enthält eine zentrale Verarbeitungseinheit (CPU) 502, die mit einem internen Systembus 504 verbunden ist. Die Speichermedien in dem Computersystem umfassen einen Hauptspeicher 506 (welcher mit dynamischen Speichereinrichtungen mit wahlfreiem Zugriff implementiert werden kann), ein Festplattenlaufwerk 508 zur Massenspeicherung und einen nicht-flüchtigen Speicher (NVRAM) 510. Der Hauptspeicher 506 und der NVRAM 510 sind mit dem Bus 504 verbunden, und das Festplattenlaufwerk 508 ist über eine Festplattenlaufwerksteuereinrichtung 512 mit dem Bus 504 gekoppelt.
Die Einrichtung der Erfindung kann in einem Computerprogramm-Produkt implementiert werden, das in einer maschinenlesbaren Speichereinrichtung (wie beispielsweise in dem Festplattenlaufwerk 508, dem Hauptspeicher 506 oder dem NVRAM 510) real enthalten ist, damit es von der CPU 502 ausgeführt werden kann. Geeignete Prozessoren sind beispielsweise sowohl Mehrzweck- als auch Spezial-Mikroprozessoren. Im Allgemeinen empfängt ein Prozessor Befehle und Daten von dem Nur-Lese-Speicher 510 und/oder dem Hauptspeicher 506. Speichereinrichtungen, die für real enthaltene Computerprogrammbefehle geeignet sind, umfassen alle Formen von nicht-flüchtigen Speichern, zu welchen beispielsweise Halbleiter-Speichereinrichtungen, wie zum Beispiel EPROM-, EEPROM- und Flash-Speichereinrichtungen, gehören; Magnetplatten, wie beispielsweise das interne Festplattenlaufwerk 508 und über eine Steuereinrichtung 526 gekoppelte wechselbare Platten und Disketten 528; magnetooptische Platten; und CD-ROM-Platten. Jede der vorhergehenden Einrichtungen kann durch speziell ausgeführte ASICs (anwendungsspezifische integrierte Schaltungen) ergänzt oder in diese einbezogen werden.
Das Computersystem enthält ferner eine Eingabe/Ausgabe (I/O)-Steuereinrichtung 514, die mit dem Bus 504 verbunden ist, und welche eine Tastatur-Schnittstelle 516 zur Verbindung mit einer externen Tastatur, eine Maus-Schnittstelle 518 zur Verbindung mit einer externen Maus oder einer anderen Zeigereinrichtung und eine Parallel-Port-Schnittstelle 520 zur Verbindung mit einem Drucker bereitstellt. Außerdem ist der Bus 504 mit einer Videosteuereinrichtung 522 verbunden, welche mit einem externen Computermonitor oder einer Anzeige 524 verbindet. Daten, die mit einem Bild zur Anzeige auf einem Computermonitor 524 verknüpft sind, werden über den Systembus 504 durch Anwendungsprogramme an die Videosteuereinrichtung 522 durch das Betriebssystem und den entsprechenden Gerätetreiber bereitgestellt.
Andere Ausführungsbeispiele liegen im Schutzbereich der folgenden Ansprüche. Beispielsweise kann von Fachleuten die Reihenfolge der erfindungsgemäßen Schritte verändert werden und es können weiterhin die gewünschten Ergebnisse erreicht werden. Es können andere Techniken verwendet werden, um einen optimalen Pfad zwischen Knoten eines Graphen zu identifizieren, welche Textblöcke oder -gebiete in einem Bild repräsentieren. Obwohl bestimmte Gleichungen und Parameter offenbart worden sind, um Variable zu bestimmen, die zur Feststellung einer optimalen Reihenfolge der Textblöcke oder -gebiete verwendet werden, können derartige Gleichungen und Parameter verändert werden.
Es wird beansprucht:

Claims

Ein Computer-implementiertes Verfahren zum Ordnen von Text in einem in einem Computer gespeicherten Bild, wobei der Text in mehrere Blöcke gruppiert ist, wobei das Verfahren umfaßt Gruppieren des Texts in mehrere Gebiete; Darstellen der Textgebiete als Graph mit Knoten und Rändern (110); Definieren jedes Textgebietes als Knoten in dem Graph; Definieren von Rändern zwischen den Knoten in dem Graph (112); wobei das Verfahren gekennzeichnet ist durch die Schritte: Zuweisen von Gewichten zu den Rändern (114); und Berechnen eines kürzesten Hamilton-Pfades durch die Knoten entsprechend den Rändergewichten (116); und Ordnen der Textgebiete gemäß der durch den berechneten kürzesten Hamilton-Pfad definierten Reihenfolge.
Das Verfahren nach Anspruch 1, wobei orientierte Paare von Rändern zwischen zwei beliebigen Knoten definiert werden.
Das Verfahren nach Anspruch 1, wobei der Schritt des Berechnens eines kürzesten Hamilton-Pfades (116) umfaßt: Hinzufügen eines virtuellen Knotens und virtueller orientierter Ränder zu dem Graphen; Gewinnen einer kürzesten geordneten Schleife in dem Graphen durch Lösen eines Handelsreisenden-Problems an dem Graphen; und Gewinnen des kürzesten Hamilton-Pfades durch Entfernen des virtuellen Knotens aus der kürzesten geordneten Schleife.
Das Verfahren nach Anspruch 1, wobei die den Rändern zwischen den Knoten zugewiesenen Gewichte auf dem Abstand zwischen zugehörigen Textgebieten basieren.
Das Verfahren nach Anspruch 1, wobei die den Rändern zwischen den Knoten zugewiesenen Gewichte auf den Textcharakteristiken der zugehörigen Textgebiete basieren.
Das Verfahren nach Anspruch 5, wobei die Textcharakteristiken eine Font-Gröfle und eine Anzahl von Zeilen des Textes enthalten.
Das Verfahren nach Anspruch 1, wobei die den Rändern zwischen den Knoten zugewiesenen Gewichte auf dem Vorhandensein von Nicht-Text-Trennelementen zwischen Textgebietpaaren basieren.
Das Verfahren nach Anspruch 8, wobei die Trennelemente grafische Objekte enthalten.
Das Verfahren nach Anspruch 1, ferner umfassend: Identifizieren von Textblöcken, die kombiniert werden können; und Kombinieren der Textblöcke zu einem Textgebiet.
Das Verfahren nach Anspruch 9, wobei zwei Textblöcke kombiniert werden können, wenn sie vertikal verbunden sind.
Das Verfahren nach Anspruch 9, wobei zwei Textblöcke kombiniert werden können, wenn sie horizontal verbunden sind.
Das Verfahren nach Anspruch 1, ferner umfassend: anfängliches Trennen des Bildes in unabhängige Teile, wobei jeder Teil seine eigene Menge von Textgebieten enthält; und unabhängiges Ausführen der Aktionen des Gruppierens, Darstellen, Definierens, Zuweisens, Berechnens und Ordnens an den Textgebieten in jedem Teil.
Das Verfahren nach Anspruch 12, wobei das Bild aufgeteilt wird, indem vorgegebene Arten von Nicht-Text-Trennelementen identifiziert werden.
Das Verfahren nach Anspruch 12, ferner umfassend: Verketten der Ordnung der Textgebiete, die für die verschiedenen Teile identifiziert sind.
Ein auf einem Computer-lesbaren-Medium befindliches Programm zum Ordnen von Text in einem in einem Computer gespeicherten Bild, wobei das Programm Befehle aufweist, die den Computer veranlassen, den Text in mehrere Gebiete zu gruppieren; die Textgebiete als Graphen mit Knoten und Rändern darzustellen (110); jedes Textgebiet als Knoten in dem Graphen zu definieren; Ränder zwischen den Knoten in dem Graphen zu definieren (112); wobei das Programm dadurch gekennzeichnet ist, daß es Befehle aufweist, die den Computer veranlassen, Gewichte den Rändern in dem Graphen zuzuweisen (114); und einen kürzesten Hamilton-Pfad durch die Knoten entsprechend den Rändergewichten zu berechnen (116); und die Textgebiete gemäß der durch den berechneten kürzesten Hamilton-Pfad definierten Reihenfolge zu ordnen (118).
Das Programm nach Anspruch 15, wobei die den Rändern zwischen den Knoten zugewiesenen Gewichte auf dem Abstand zwischen zugehörigen Textblöcken und den Charakteristiken jedes Blocks basieren.
Das Programm nach Anspruch 15, wobei die den Rändern zwischen den Knoten zugewiesenen Gewichte auf dem Vorhandensein von Trennelementen zwischen den Textblockpaaren basieren.
Das Programm nach Anspruch 15, wobei das Programm Befehle aufweist, die den Computer ferner veranlassen: Blöcke des Textes zu identifizieren, die kombiniert werden können; und die Textblöcke in ein Textgebiet zu kombinieren.
Das Programm nach Anspruch 15, wobei das Programm Befehle aufweist, um den Computer ferner zu veranlassen: anfänglich das Bild in unabhängige Teile aufzuteilen, wobei jeder Teil seine eigene Menge von Textgebieten enthält; und die Aktionen des Gruppierens, Darstellens, Definierens, Zuweisens, Berechnens und Ordnens der Textgebiete in jedem Teil unabhängig auszuführen.
Das Programm nach Anspruch 19, wobei das Programm Befehle aufweist, um den Computer ferner zu veranlassen, die Ordnung der Textgebiete zu verketten, die für die unabhängigen Teile identifiziert sind.
Einrichtung zum Erkennen von Text in einem Bild, aufweisend: ein Speichermedium zum Speichern des Bildes; und einen betriebsmäßig mit dem Speichermedium gekoppelten Prozessor, der konfiguriert ist, um: den Text in mehrere Gebiete zu gruppieren; die Textgebiete in einem Graphen mit Knoten und Rändern darzustellen (110); jedes Textgebiet als Knoten in dem Graphen zu definieren; Ränder zwischen den Knoten in dem Graphen zu definieren (112); wobei der Prozessor dadurch gekennzeichnet ist, daß er konfiguriert ist, um: den Rändern in dem Graphen Gewichte zuzuweisen (114); und einen kürzesten Hamilton-Pfad durch die Knoten in Übereinstimmung mit den Rändergewichten zu berechnen (116); und die Textgebiete in Übereinstimmung mit der durch den berechneten kürzesten Hamilton-Pfad definierten Reihenfolge zu ordnen (118).
Die Einrichtung nach Anspruch 21, wobei die den Rändern zwischen den Knoten zugewiesenen Gewichte auf dem Abstand zwischen zwei beliebigen Textgebieten basieren.
Die Einrichtung nach Anspruch 21, wobei die den Rändern zwischen den Knoten zugewiesenen Gewichte ferner auf dem Vorhandensein von Trennelementen zwischen Textblockpaaren basieren.
Ein in einem Computer implementiertes Verfahren zum Ordnen von Text in einem in dem Computer gespeicherten Bild, wobei das Verfahren umfaßt: Identifizieren einer Menge von Textblöcken (104); Aufteilen der Menge von Textblöcken in unabhängige Untermengen von Textblöcken (106); Darstellen der Textblöcke als Knoten in einem Graphen in jeder Untermenge (110); Definieren gerichteter Ränder zwischen den Knoten in jeder Untermenge (112); wobei das Verfahren gekennzeichnet ist durch die Schritte: Zuweisen von Gewichten zu den gerichteten Rändern (114); Berechnen eines kürzesten Hamilton-Pfads durch den Graphen in jeder Untermenge in Übereinstimmung mit den Rändergewichten (116); Ordnen der Textblöcke in jeder Untermenge in Übereinstimmung mit der durch den berechneten kürzesten Hamilton-Pfad definierten Reihenfolge (118); und Verketten der Ordnung der Textblöcke in den Untermengen zu einer Endreihenfolge.