DE69425084T2

DE69425084T2 - Verfahren und Gerät zur Erkennung von Textzeilen, Wörtern und räumlichen Merkmalen von Zeichenzellen

Info

Publication number: DE69425084T2
Application number: DE69425084T
Authority: DE
Inventors: A. Lawrence Spitz
Original assignee: Xerox Corp
Current assignee: Xerox Corp
Priority date: 1993-04-19
Filing date: 1994-04-18
Publication date: 2000-11-09
Anticipated expiration: 2014-04-19
Also published as: DE69425084D1; JPH0713995A; US5384864A; EP0621554B1; KR970002420B1; EP0621554A3; EP0621554A2; KR940024625A

Description

Die vorliegende Erfindung betrifft ein Verfahren und eine Vorrichtung zur automatischen Dokumenterkennung und insbesondere ein Verfahren zum automatischen Bestimmen von Raummerkmalen von Zeilen, Wörtern und Zeichenzellen innerhalb eines Dokuments.
Die optische Zeichenerkennung und die Verwendung der optischen Zeichenerkennung zum Umwandeln von gescannten Bilddaten zu Textdaten, die für die Verwendung in einem digitalen Computer geeignet sind, ist wohlbekannt. Außerdem sind Verfahren zum Umwandeln von gescannten Bilddaten zu Textdaten sowie die von derartigen Verfahren erzeugten Fehlertypen wohlbekannt. Ein Problem beim Umwandeln von gescannten Bilddaten zu Textdaten besteht darin, die einzelnen Textzeilen des Texts voneinander unterscheiden zu können, die Wörtergruppierung innerhalb einer einzelnen Textzeile unterscheiden zu können, die vertikale und horizontale Erstreckung der Zeichenzellen innerhalb einer einzelnen Textzeile zu bestimmen sowie die Ligaturen oder Unterschneidungen zwischen verbundenen Komponenten in einer einzelnen Textzeile korrekt zu trennen.
In D1 = IEEE Transactions an Pattern Analysis and Machine Intelligence, Vol. 6, No. 12, auf den Seiten 552-559, XP 000136972 gibt der Artikel "Reading Chess" von Baird H S et al. in Übereinstimmung mit Punkt 4.1 des Amtsbescheids eine Eingabeeinrichtung, eine Einrichtung zum Erzeugen von verbundenen Komponenten, eine Einrichtung zum Erzeugen von Begrenzungsrechtecken und eine Einrichtung zum Bestimmen von Zeilenraummerkmalen wie der Basislinie an (Seite 555, Spalte 1, Zeilen 13 bis 16). Es ist eine Aufgabe der vorliegenden Erfindung, ein Verfahren zum automatischen Dokumentenerkennen mit einer verbesserten Leistung bezüglich der Effizienz und Zuverlässigkeit bei der Raummerkmalerkennung anzugeben.
Diese Aufgabe wird durch den Gegenstand der Ansprüche 1 und 7 gelöst.
Bevorzugte Ausführungsformen sind Gegenstand der abhängigen Ansprüche.
Vorzugsweise umfaßt der Schritt zum Erzeugen eines Vertikalprofils das Bestimmen der obersten und untersten Positionen jeder Zeile aus jeweils einer Maximalspitze und einer Minimalspitze des Vertikalprofils für jede Zeile.
Vorzugsweise umfaßt der Schritt zum Erzeugen eines Vertikalprofils einen Schritt zum Erzeugen eines Oberste-Position-Vertikalprofils der obersten Positionen der entsprechenden aus der Vielzahl von verbundenen Komponenten und eines Unterste-Position-Vertikalprofils der unteren Positionen der entsprechenden aus der Vielzahl von verbundenen Komponenten.
Vorzugsweise umfaßt der Schritt zum Erzeugen eines Vertikalprofils weiterhin das Bestimmen der Positionen der x-Linie und der Basislinie für jede Zeile aus einer Spitze des Oberste-Position- und des Unterste-Position-Vertikalprofils für jeweils eine Zeile.
Weiterhin umfaßt das Verfahren vorzugsweise das Bestimmen der Wortraumeigenschaften jeder Zeile.
Vorzugsweise umfaßt das Verfahren weiterhin folgende Schritte: (h) horizontales Spreizen von jeder wenigstens einen Zeile des nicht gespreizten Textteils; (i) Bestimmen der Zwischenraumbreiten des horizontal gespreizten Textteils zwischen benachbarten verbundenen Komponenten jeder Zeile; und (j) Erzeugen von wenigstens einer. Zeichenzelle für jede Zeile des nicht gespreizten Textteils auf der Basis des horizontal gespreizten Textes, wobei jede Zeichenzelle eine Gruppe von wenigstens einer vertikal ausgerichteten verbundenen Komponente des horizontal gespreizten Textteils umfaßt.
Vorzugsweise umfaßt der Schritt (h) folgende Schritte: (h1) Bestimmen einer modalen Anschlagbreite für jede wenigstens eine Zeile; (h2) Feststellen von breiten verbundenen Komponenten mit Breiten, die größer als ein vorbestimmtes Vielfaches der modalen Anschlagbreite für die entsprechende Zeile sind; (h3) Erzeugen einer Kostenverteilung für jede breite verbundene Komponente; (h4) Feststellen der Kostenminima innerhalb der Kostenverteilungen, wobei jede Kostenverteilung einem vorbestimmten Teil von einer der breiten verbundenen Komponenten entspricht; und (h5) Aufteilen von jeder breiten verbundenen Komponente, für welche wenigstens ein Kostenminimum festgestellt wird, in zwei unabhängige verbundene Komponenten.
Vorzugsweise ist das vorbestimmte Vielfache 3.
Vorzugsweise erstreckt sich der vorbestimmte Teil von jeder breiten verbundenen Komponente von einem ersten Punkt, der ein zweites vorbestimmtes Vielfaches der modalen Anschlagbreite rechts von einer linkesten Position der breiten verbundenen Komponente ist, zu einem zweiten Punkt, der das zweite vorbestimmte Vielfache der durchschnittlichen Anschlagbreite links von einer rechtesten Position der breiten verbundenen Komponente ist. Vorzugsweise ist das zweite vorbestimmte Vielfache 1,5.
Vorzugsweise ist das Minimum kleiner als ein vorbestimmter Wert. Vorzugsweise ist der vorbestimmte Wert gleich der modalen Anschlagbreite.
Vorzugsweise umfaßt der Schritt (h3) das UND-Verknüpfen von benachbarten Spalten des Begrenzungsrechtecks zu der breiten verbundenen Komponente.
Vorzugsweise umfaßt der Schritt (j) einen Schritt zum Bestimmen einer linkesten Position der entsprechenden Gruppe von wenigstens einer vertikal ausgerichteten verbundenen Komponente und einer rechtesten Position der entsprechenden wenigstens einen vertikal ausgerichteten verbundenen Komponente für jede Zeichenzelle, wobei die Grenzen jeder Zeichenzelle von jeder Zeile die linkesten und die rechtesten Positionen und die obersten und die untersten Positionen der entsprechenden Zeile umfassen.
Vorzugsweise umfaßt der Schritt (i) folgende Schritte: (i1) Bestimmen einer Zeilenanfangsposition und einer Zeilenendposition; (i2) Bestimmen der Größen der Zwischenräume zwischen verbundenen Komponenten jeder Zeile des gespreizten Texts; (i3) Bestimmen einer Verteilung der Zwischenraumgrößen; und (i4) Feststellen von wenigstens einer Spitze in der Zwischenraumgrößenverteilung.
Vorzugsweise umfaßt der Schritt (i) weiterhin folgende Schritte: (i5) Bestimmen, ob jede wenigstens eine Spitze für jede Zeile einen Zwischenraum zwischen Wörtern oder einen Zwischenraum innerhalb eines Wortes wiedergibt; und (i6) Bestimmen auf der Basis der entsprechenden Spitzenbestimmung, ob jeder wenigstens eine Zwischenraum in jeder Zeile einen Zwischenraum zwischen Wörtern oder einen Zwischenraum innerhalb eines Wortes wiedergibt.
Gemäß einer ersten Ausführungsform des Verfahrens und der Vorrichtung der vorliegenden Erfindung werden eine Vielzahl von Begrenzungsrechtecken erzeugt, die eine Vielzahl von verbundenen Komponenten eines Textteils eines Bildes eines Dokuments umgeben. Die Begrenzungsrechtecke und die verbundenen Komponenten werden dann in der vertikalen Richtung gespreizt, um Überlappungen zwischen den Begrenzungsrechtecken einer aktuellen Zeile und den Begrenzungsrechtecken der vertikal zu der aktuellen Zeile benachbarten Zeilen zu trennen. Ein Vertikalprofil der verbundenen Komponenten jeder Zeile wird erzeugt und die oberen und unteren Spitzen werden festgestellt. Individuelle Vertikalprofile für die obersten und untersten Positionen der verbundenen Komponenten werden erzeugt, um jeweils die Positionen der Basislinie und der x-Linie zu bestimmen (wenn möglich). Wenn jede Linie des Textteils identifiziert ist, werden die Begrenzungsrechtecke und die verbundenen Komponenten dann horizontal gespreizt, um Überlappungen der Begrenzungsrechtecke zu beseitigen. Für jede Zeile wird ein modaler Anschlagbreitenwert der verbundenen Komponenten dieser Zeile bestimmt. Die tatsächlichen Anschlagbreiten der verbundenen Komponenten werden mit dieser modalen Anschlagbreite verglichen. Wenn eine verbundene Komponente eine tatsächliche Anschlagbreite aufweist, die größer als ein vorbestimmtes Vielfaches der modalen Anschlagbreite ist, dann wird jede derart verbundene Komponente als eine mögliche Ligatur von zwei oder mehr unabhängigen verbundenen Komponenten betrachtet. In diesem Fall können die verbundenen Komponenten geteilt werden. Derartige Ligaturen werden rekursive geteilt, bis keine weiteren Teilungen mehr möglich sind. Wenn alle möglichen Teilungen vorgenommen wurden, werden die Zwischenräume zwischen benachbarten verbundenen Komponenten analysiert, um die Wort- und Zeichenabstände jeder Zeile zu bestimmen.
Wenn der Textteil des Bildes derart konditioniert ist, daß die verbundenen Komponenten vertikal und horizontal eindeutig von den umgebenden verbundenen Komponenten getrennt sind, dann wird jede Gruppe von verbundenen Komponenten, die zwischen den obersten und untersten Positionen jeder Zeile angeordnet und vertikal miteinander ausgerichtet sind, zusammen als ein Zeichen in einer Zeichenzelle gruppiert.
Wenn in einer zweiten bevorzugten Ausführungsform der Textteil des Dokuments in ein repräsentatives digitales Datensignal umgewandelt werden muß, dann wird das Dokument gescannt, und es werden alle Nicht-Textteile entfernt. Das resultierende Textbild wird dann auf Schrägstellung und andere Scannartefakte hin korrigiert (wenn erforderlich). Wenn das Dokumentenbild gescannt und gereinigt wurde, dann wird das Bild von einer Bitmap aus Pixeln mit jeweils bestimmten Positionen und Bilddichten zu einer Vielzahl von verbundenen Komponenten umgewandelt. Nach dem Erzeugen der verbundenen Komponenten wird ein Begrenzungsrechteck für jede verbundene Komponente erzeugt.
Die vorliegende Erfindung wird im folgenden mit Bezug auf die beigefügten Zeichnungen beschrieben:
Fig. 1 zeigt ein Blockdiagramm eines optischen Zeichenerkennungssystems,
Fig. 2 zeigt eine Textprobe und ein Vertikalprofil vor und nach dem vertikalen Spreizen,
Fig. 3 zeigt Begrenzungsrechtecke für jede verbundene Komponente des in Fig. 2 gezeigten Dokuments,
Fig. 4 zeigt eine Textkette, welche die relativen Positionen der Textzeile angibt,
Fig. 5 zeigt die Textprobe von Fig. 2 vor und nach dem horizontalen Spreizen und vor und nach dem Teilen der verbundenen Komponenten,
Fig. 6 ist ein Flußdiagramm des Raummerkmal-Bestimmungsverfahrens der vorliegenden Erfindung,
Fig. 7 zeigt den Probetext von Fig. 2 mit den Zeichenzellen und den Begrenzungsrechtecken.
Wie in Fig. 1 gezeigt, umfaßt das optische Zeichenerkennungssystem der vorliegenden Erfindung einen Scanner 110 mit einem CCD (Charge Coupled Device) oder ähnlichem. Der Scanner 110 scannt ein Dokument mit einem Bild 102 (siehe Fig. 2(a)), wobei das Bild 102 einen Textteil 104 in einer unbekannten Schrift und Sprache umfaßt. Der Scanner 110 gibt ein digitales Datensignal aus, das die Position und die Bilddichte von einer Vielzahl von Pixeln wiedergibt, die das Bild 102 des Originaldokuments 100 bilden. Dieses digitale Datensignal wird zu einem Speicher 112 gesendet, wo es temporär oder auf unbestimmt lange Zeit gespeichert wird. Wenn das digitale Datensignal aus dem Speicher 112 ausgegeben wird, wird es in einen Universalcomputer 114 eingegeben. Im Computer 114 wird das digitale Datensignal zuerst gereinigt, indem alle Nicht-Textteile des Bildes 102 entfernt werden, so daß nur der Textteil 104 übrigbleibt. Weiterhin werden Scannerartefakte in dem digitalen Datensignal wie etwa eine Schrägstellung oder ähnliches entfernt. Das gereinigte digitale Datensignal wird dann im Speicher 112 gespeichert oder in einem Speicher des Computers 114 gespeichert. Alternativ dazu kann der Scanner einen Teil der Vorverarbeitung wie etwa das Entfernen von Scannerartefakten vorsehen.
Wie in Fig. 1 gezeigt, umfaßt der digitale Universalcomputer 114 der vorliegenden Erfindung einen Speicher 22 zum Speichern eines Steuerprogramms, eine Eingabe/Ausgabe-Schaltung 24 zum Eingeben des digitalen Datensignals von dem Speicher 112 und zum Ausgeben eines Signals, das die bestimmten Zeichenzellen des Textteils 104 wiedergibt. Der Universalcomputer 114 umfaßt auch einen Bild-RAM 26 zum Speichern des digitalen Datensignals; eine Verbundene-Komponenten-Erzeugungseinrichtung 28 zum Erzeugen von verbundenen Komponenten aus dem digitalen Datensignal; eine Begrenzungsrechteck-Erzeugungseinrichtung 30 zum Bestimmen der Koordinaten des Begrenzungsrechtecks und der Pixel des digitalisierten Bildes innerhalb des Begrenzungsrechtecks für jede der verbundenen Komponenten; eine Vertikalspreizeinrichtung 32 zum vertikalen Spreizen des Textteils 104; eine Vertikalprofileinrichtung 34 zum Erzeugen eines Vertikalprofils des nicht gespreizten Textteils 104; eine Wortraummerkmal-Bestimmungseinrichtung 36 zum horizontalen Spreizen des Textteils 104; eine Zeichenzellen-Erzeugungseinrichtung 38 zum Gruppieren von verbundenen Komponenten zu Zeichenzellen und zum Identifizieren von Zeichen- und Wortteilungen. Die Vertikalprofileinrichtung 34 umfaßt eine Vertikalprofil-Erzeugungseinrichtung 342 zum Erzeugen von Vertikalprofilen des Textteils 104, von jeder Zeile des Textteils 104 und von Teilen jeder Zeile sowie eine Vertikalposition-Bestimmungseinrichtung 340 zum Bestimmen von wenigstens der obersten und untersten Positionen und der Positionen der Basislinie und möglicherweise der x-Linie jeder Zeile. Die Zeilenraummerkmal-Bestimmungseinrichtung 36 umfaßt eine Horizontalspreizeinrichtung 360 zum horizontalen Spreizen jeder Zeile des Textteils 104, eine Wortzwischenraum-Bestimmungseinrichtung 362 zum Bestimmen der Zwischenräume zwischen den Wörtern und innerhalb der Wörter von jeder Zeile des Textteils 104, eine Anschlagbreite-Bestimmungseinrichtung 364 zum Bestimmen der modalen Anschlagbreite jeder Zeile und der tatsächlichen Anschlagbreiten für jede verbundene Komponente des Textteils 104 sowie eine Zeileninhalt-Bestimmungseinrichtung (nicht gezeigt) zum Bestimmen, welche verbundenen Komponenten zu jeder Zeile es Textteils 104 gehören. Der Speicher 22 zum Speichern des Steuerprogramms kann entweder einen ROM 22a oder einen RAM 22b umfassen.
Im Betrieb wird das Dokument mit dem Bild 102 in den Scanner 110 gelegt und gescannt, um ein serielles oder paralleles digitales Datensignal zu erzeugen. Das digitale Datensignal umfaßt eine Vielzahl von Signalteilen, wobei jeder Teil ein entsprechendes Pixel des Originalbildes 102 wiedergibt. Jedes Pixel des Bildes 102 weist eine Position in dem Bild 102 und eine Bilddichte auf. Dementsprechend umfaßt jeder Signalteil des digitalen Datensignals Daten, welche die Position und die Bilddichte des entsprechenden Pixels wiedergeben.
Das durch den Scanner 110 ausgegebene digitale Datensignal wird dann im Speicher 112 gespeichert. Der Speicher 112 kann einen RAM, einen Flash-Memory, einen Plattenspeicher oder ähnliches umfassen. Unabhängig von dem Typ des Speichers 112 wird das digitale Datensignal in Reaktion auf die Positions- und Bilddichtedaten innerhalb jedes Signalteils im Speicher 112 gespeichert. Das digitale Datensignal kann natürlich auch direkt in den Universalcomputer 114 und nicht in den dazwischen angeordneten Speicher 112 eingegeben werden. Alternativ dazu kann der Speicher 112 in dem Universalcomputer 114 integriert sein. In jedem Fall wird der Speicher 112 verwendet, um ein langfristiges Speichern des Bildes 102 vorzusehen.
Wenn der Bediener das Eingeben von Dokumenten in den Scanner 110 oder das System abgeschlossen hat und bestimmt oder darüber informiert wird, daß das im Speicher 112 gespeicherte digitale Datensignal, welches das Bild 102 wiedergibt, zu Textdaten umgewandelt werden soll, dann wird das digitale Datensignal, welches das Bild 102 wiedergibt, aus dem Speicher 112 zu dem Universalcomputer 114 ausgegeben. Es kann natürlich auch ein digitaler Spezialcomputer oder eine Hardware-Logikschaltung anstelle des digitalen Universalcomputers 114 verwendet werden.
Das im Speicher 112 gespeicherte digitale Bilddatensignal wird zu dem Universalcomputer 114 ausgegeben, wo es über die Eingabe/Ausgabe-Einrichtung 24 zu einem Bildspeicher 26 ausgegeben wird. Wenn das digitale Datensignal vollständig im Bildspeicher 26 gespeichert wurde, dann wird das digitale Datensignal für die Verbundene-Komponenten-Erzeugungseinrichtung 28 verfügbar gemacht. Die Verbundene-Komponenten-Erzeugungseinrichtung 28 teilt das digitale Datensignal, welches das Bild 102 wiedergibt, in eine Vielzahl von verbundenen Komponenten, wobei jede verbundene Komponente einen oder mehrere Signalteile umfaßt. Jede verbundene Komponente umfaßt Signalteile, welche denjenigen Pixeln des Originalbildes 102 entsprechen, die eine bestimmte minimale Bilddichte aufweisen und einen kontinuierlichen Pfad bilden. Jedes Schriftzeichen entspricht allgemein einer verbundenen Komponente wie etwa dem "F" in "Fuji" oder mehr als einer verbundenen Komponente wie etwa dem "j" oder "i" in "Fuji". Die Liste der durch die Verbundene-Komponenten-Erzeugungseinrichtung 28 erzeugten verbundenen Komponenten wird in dem Bildspeicher 26 und/oder dem Speicher 112 gespeichert.
Wenn die Verbundene-Komponenten-Erzeugungseinrichtung 28 die Vielzahl von verbundenen Komponenten für das Bild 102 aus dem digitalen Datensignal erzeugt, werden das digitale Datensignal für das Bild 102, das in dem Bildspeicher 26 gespeichert ist, und die Liste der verbundenen Komponenten, die durch die Verbundene-Komponenten-Erzeugungseinrichtung 28 erzeugt werden, an die Begrenzungsrechteck-Erzeugungseinrichtung 30 ausgegeben.
Die Begrenzungsrechteck-Erzeugungseinrichtung 30 teilt erneut das digitale Datensignal, welches das Bild 102 wiedergibt, in eine Vielzahl von Begrenzungsrechtecken auf, wobei jedes Begrenzungsrechteck eine verbundene Komponente und null, einen oder mehr Signal teile des digitalen Datensignals enthält, die neben oder in der Nähe der Signalteile lokalisiert sind, welche die verbundene Komponente bilden. Diese zusätzlichen Signalteile, welche den Pixeln des Textteils entsprechen, umgeben jede verbundene Komponente. Die Dimensionen jedes Begrenzungsrechtecks werden durch die Positionsdaten der linkesten, rechtesten, obersten und untersten Signalteile der entsprechenden verbundenen Komponente bestimmt. Dementsprechend sind die Signalteile innerhalb des Begrenzungsrechtecks diejenigen Signalteile, welche die verbundene Komponente bilden, wobei diese Signalteile unabhängig von ihren Bilddichtedaten Positionsdaten aufweisen, welche sie innerhalb der Grenzen des Begrenzungsrechtecks plazieren. Wenn die Liste der Begrenzungsrechtecke und der Signalteile jedes Begrenzungsrechtecks durch die Begrenzungsrechteck-Erzeugungseinrichtung 30 gebildet wurde, wird die Liste der Begrenzungsrechtecke in den Bildspeicher 26 oder den Speicher 112 eingegeben. Die Listen der verbundenen Komponenten und der Begrenzungsrechtecke sowie die Vielzahl von Signalteilen werden zu einer Vertikalspreizeinrichtung 32 ausgegeben.
Die Vertikalspreizeinrichtung 32 spreizt den Textteil 104 vertikal, indem sie den Ursprung jedes Begrenzungsrechtecks in dem Textteil 104 verschiebt, um einen abnormal großen weißen Zwischenraum (Zeilenzwischenraum) zwischen vertikal miteinander ausgerichteten verbundenen Komponenten vorzusehen, ob ein derartiges Spreizen erforderlich ist oder nicht. Allgemein werden die Zeilen innerhalb eines Textteils eines Dokuments durch einen weißen Zwischenraum oder Zeilenzwischenraum mit einer variablen Größe getrennt, wobei der Zeilenzwischenraum als ein linearer horizontaler weißer Pfad zwischen Zeichen der aktuellen Zeile und den Zeichen der vertikal benachbarten Zeilen definiert ist.
Allgemein sind asiatische Schrifttypen praktisch zu handhaben, weil die verbundenen Komponenten keine Oberlängen oder Unterlängen aufweisen. Es ist dementsprechend möglich, Textzeilen in einem Dokument in einer asiatischen Schrift ohne Spreizen eindeutig zu lokalisieren. Im Gegensatz dazu sind europäische Schriften nicht so praktisch zu handhaben, weil sie gewöhnlich Oberlängen und Unterlängen aufweisen. Weil diese Oberlängen und Unterlängen häufig einander horizontal berühren oder überlappen, ist es manchmal schwierig, Textzeilen in Dokumenten in einer europäischen Schrift eindeutig zu lokalisieren, ohne die Textzeilen zuerst in der vertikalen Richtung zu spreizen.
Weil das Spreizen weder zeitaufwendig ist noch eine große Rechenleistung erfordert, ist es einfacher, unabhängig von dem Schrifttyp (und vorzugsweise ohne den Schrifttyp zuerst zu bestimmen) immer ein vertikales Spreizen vorzunehmen, als zuerst den Schrifttyp und/oder diejenigen Zeilen zu bestimmen, die ein Spreizen erfordern. Wenn natürlich die Kosten für das Spreizen höher sind, dann kann die vorliegende Erfindung einfach modifiziert werden, um eine Einrichtung zu umfassen, welche bestimmt, ob ein Spreizen des Textteils 104 erforderlich ist. Wie in Fig. 2, Teil (a) gezeigt, weist der Textteil 104 Oberlängen und Unterlängen auf, so daß das Vertikalprofil keinen weißen Zwischenraum zwischen den Zeilen aufweist. Wenn Cy die ursprüngliche Position auf der y-Achse des Ursprungs eines Begrenzungsrechtecks ist, das eine verbundene Komponente umgibt, und Cy' die endgültige Position auf der y-Achse des Ursprungs des Begrenzungsrechtecks nach dem Spreizen ist
C'y = f (Cy + Ch/2) - Ch/2 (1)
wobei Ch die Höhe der verbundenen Komponente und f() die Spreizfunktion ist. In der vorliegenden Ausführungsform ist f ein vorgewählten, konstanter Spreizfaktor f im Bereich von 1 < f < 5. Dabei sollte f jedoch nicht so groß sein, daß die Trennung zwischen vertikal benachbarten, zusammengehörigen Komponenten wie etwa zwischen den zwei Teilen des Zeichens "i" fälschlicherweise als Zeilenzwischenraum interpretiert wird. Vorzugsweise ist f = 1,2.
Fig. 2 zeigt in Teil (a) einen Probetextteil 104 mit Begrenzungsrechtecken, die jede verbundene Komponente des Probetextteils umgeben, sowie ein Vertikalprofil der Begrenzungsrechtecke. Aus dem Vertikalprofil wird deutlich, daß das Begrenzungsrechteck um das "j" in "Fuji" die erste "0" in "3400" berührt. Wenn jedoch der oben genannte Vertikalspreizfaktor angewendet wird, um die Ursprünge der verbundenen Komponenten "j" und "0" in der Vertikalrichtung zu verschieben, dann wird wie in Fig. 2(b) gezeigt ein ununterbrochener weißer Zwischenraum zwischen jedem Paar von vertikal benachbarten Linien erzeugt.
Aus einem Vergleich der vertikalen Verteilungsprofile der Begrenzungsrechtecke jeder Textzeile in Fig. 2(b) kann das obere oder unter Ende einer Zeile vertikal nicht von dem oberen oder unteren Ende der vorhergehenden oder folgenden Zeile unterschieden werden. In Teil (b) können jedoch das obere und untere Ende einer Zeile und das obere oder untere Ende von benachbarten Zeilen positiv unterschieden werden. Dabei ist es wichtig, zu beachten, daß das Spreizen zwar die vertikalen Positionen zwischen den Begrenzungsrechtecken von einer Zeile und den Begrenzungsrechtecken der vertikal benachbarten Zeilen verschiebt, die ursprünglichen Dimensionen der Begrenzungsrechtecke aber nicht verändert werden.
Nach dem vertikalen Spreizen des Textteils 104 bestimmt die Vertikalspreizeinrichtung 32, welche verbundenen Komponenten und Begrenzungsrechtecke zu jeder Textzeile gehören. Die Listen der Zeilen und der entsprechenden verbundenen Komponenten werden dann in dem Bildspeicher 26 und/oder dem Speicher 112 gespeichert.
Die Listen der Zeilen und der entsprechenden verbundenen Komponenten, die Liste der verbundenen Komponenten und der ursprünglichen Signalteile des Textteils 104 werden dann zu einer Vertikalprofileinrichtung 34 ausgegeben. Die Vertikalprofileinrichtung 34 bestimmt für den nicht gespreizten Teil 104 die obersten und untersten Positionen und die rechtesten und linkesten Positionen jeder Textzeile. Die Vertikalprofileinrichtung 34 erzeugt zuerst ein Vertikalverteilungsprofil der verbundenen Komponenten jeder Textzeile. Aus dem Vertikalverteilungsprofil können wie in Fig. 4 gezeigt die obersten und untersten Positionen einer Textzeile positiv bestimmt werden. Die Vertikalprofileinrichtung 34 bestimmt dann die obersten und untersten Positionen des Vertikalprofils für jede Textzeile. Der unterste Punkt der Textzeile ist wie in Fig. 4 gezeigt der unterste Punkt des Vertikalverteilungsprofils, während der oberste Punkt der Textzeile wie in Fig. 4 gezeigt der oberste Punkt des Vertikalprofils ist. Die Vertikalprofileinrichtung 34 erzeugt dann zwei zusätzliche Vertikalprofile für jede Textzeile: eines für nur für die untersten Positionen der verbundenen Komponenten der Zeile, und ein anderes für nur die obersten Positionen der verbundenen Komponenten der Zeile. Die Positionen der Basislinie und der x-Linie sind allgemein jeweils die vertikalen Positionen der Spitzen der Vertikalverteilungsprofile für die obersten und untersten Positionen. Es ist möglich, daß in einer Textzeile mit verbundenen Komponenten ohne Oberlängen und Unterlängen die oberste Position und die Position der x-Linie oder die unterste Position und die Position der Basislinie übereinstimmen. Weiterhin ist es in einer Textzeile mit einem hohen Prozentsatz von Buchstaben mit Oberlängen oder. Unterlängen eventuell nicht möglich, die Position der x-Linie korrekt zu bestimmen. Wenn alle Zeilen durch die Vertikalprofileinrichtung 34 verarbeitet wurden, werden die Listen für die untersten und obersten Positionen sowie für die Positionen der Basislinie und der x-Linie für jede Zeile an den Bildspeicher 26 ausgegeben. Die verbundenen Komponenten für eine Textzeile sind diejenigen Komponenten, die vollständig zwischen die obersten und untersten Positionen fallen. Daraus resultieren natürlich negative y-Ursprünge für viele verbundene Komponenten in einem abwärtspositiven Koordinatensystem.
Dann werden die Vielzahl von Signalteilen und die Listen der verbundenen Komponenten sowie der Begrenzungsrechtecke für jede Zeile des Textteils 104 an die Wortraummerkmal- Bestimmungseinrichtung 36 ausgegeben. Die Horizontalspreizeinrichtung 360 der Wortraum merkmal-Bestimmungseinrichtung 36 spreizt die einzelnen verbundenen Komponenten und die Begrenzungsrechtecke einer einzelnen Zeile horizontal, um Überlappungen oder Ligaturen von zwei oder mehr verbundenen Komponenten oder Begrenzungsrechtecken für zwei oder mehr unabhängige verbundene Komponenten zu entfernen.
Allgemein sind Zeichen innerhalb einer Textzeile durch verschiedene Größen von weißen Zwischenräumen getrennt, wobei ein weißer Zwischenraum als ein linearer, vertikaler weißer Pfad zwischen Zeichen in der aktuellen Zeile definiert ist. Wiederum sind asiatische Schrifttypen gewöhnlich einfach zu handhaben, so daß es allgemein nicht erforderlich ist, die Zeilen eines Dokuments in einer asiatischen Schrift horizontal zu spreizen, um sicherzustellen, daß derartige weiße Zwischenräume zwischen den Zeichen vorhanden sind. Im Gegensatz dazu sind bei proportional beabstandeten europäischen Schriften die Zeichen und Wörter gewöhnlich durch einen weißen Zwischenraum getrennt, dessen Größe und Verteilung innerhalb eines Wortes und zwischen Wörtern stark variieren kann. Der Zwischenraum hängt oft von der verwendeten Schrift ab, muß nicht genau vertikal sein, um durch das menschliche Auge erkannt zu werden, und kann absichtlich weggelassen werden. Aufgrund des geringen Aufwands des Spreizens ist es wiederum allgemein weder erforderlich noch vorteilhaft, den Schrifttyp des Textteils 104 zu bestimmen oder zu entscheiden, ob das Spreizen einer bestimmten Zeile erforderlich ist. Sollte der Aufwand für das Spreizen jedoch größer sein, kann wie weiter oben genannt natürlich eine derartige Information vorgesehen werden.
Paarunterschneidungen, die Überlappungen von Begrenzungsrechtecken verursachen, treten häufig auf, wie etwa in "uj" von "Fuji" oder in "Av" von "Avenue" in dem Probetext von Fig. 2. Weiterhin treten in einigen Schriften absichtliche Ligaturen oder Überlappungen von verbundenen Komponenten auf, wie etwa in "fi" von "confidence" in Fig. 2. In der bevorzugten Ausführungsform der vorliegenden Erfindung spreizt die Horizontalspreizeinrichtung 360 jede Zeile des Textteils horizontal, um Überlappungen zwischen benachbarten Begrenzungsrechtecken zu beseitigen. Dann wird jede horizontal gespreizte Zeile analysiert, um verbleibende Ligaturen in der Zeile zu analysieren. Nachdem die festgestellten Ligaturen identifiziert wurden, werden sie analysiert, um höchstens einen Teilungspunkt festzustellen. Wenn ein Teilungspunkt in der verbundenen Komponenten festgestellt wird, wird die Ligatur in zwei verbundene Komponenten geteilt. Nach dem Spreizen der festgestellten Ligaturen werden die verbundenen Komponenten der aktuellen Zeile erneut geprüft, um zu bestimmen, ob möglicherweise Ligaturen verbleiben.
Die Horizontalspreizeinrichtung 360 operiert ähnlich wie die Vertikalspreizeinrichtung 32, arbeitet aber auf den horizontalen und nicht auf den vertikalen Positionen des Begrenzungsrechtecks jeder Textzeile. Um jede Textzeile des Textteils 104 zu spreizen, verschiebt die Horizontalspreizeinrichtung 360 den Ursprung jedes Begrenzungsrechtecks der aktuellen Textzeile, um einen relativ großen weißen Zwischenraum zwischen jedem Paar von horizontal benachbarten verbundenen Komponenten zu bilden. Wenn Cx die ursprüngliche Position auf der x-Achse des Begrenzungsrechtecks ist und Cx' die endgültige Position auf der x-Achse des Begrenzungsrechtecks nach dem Spreizen ist,
Cx' = f(Cy + Cbu/2) - Cw/2 (2)
wobei Cw die Breite der aktuellen verbundenen Komponente ist und f() die Spreizfunktion ist. In der vorliegenden Ausführungsform ist f ein vorgewählter konstanter Spreizfaktor f im Bereich von 5 > f > 1. Dabei sollte f jedoch nicht so groß sein, daß die Trennung zwischen horizontal benachbarten Komponenten innerhalb eines Wortes fälschlicherweise als Zwischenraum zwischen Wörtern interpretiert wird. Dementsprechend ist f vorzugsweise ist gleich 1, 2.
Fig. 5 zeigt in Teil (a) die vertikal gespreizte Textprobe von Fig. 2(b) vor dem horizontalen Spreizen. Die Überlappungen zwischen den Begrenzungsrechtecken für die "u" und "i" in "Fuji" und "A" und "v" in "Avenue" sind deutlich, wie auch die nicht beabsichtigten Ligaturen "12" in "seized", von "in" und "rn" in "international" oder von "fi" in "confidence". Der horizontal gespreizte Textteil 104 ist in Fig. 5(b) gezeigt.
Während die unbeabsichtigten Überlappungen von Begrenzungsrechtecken einfach durch ein Spreizen entfernt werden, kann das horizontale Spreizen keine beabsichtigten oder unbeabsichtigten Ligaturen entfernen. Diese Ligaturen werden durch einzelne Begrenzungsrechtecke wiedergegeben, da sie als einzelne verbundene Komponenten identifiziert werden.
Um die Ligaturen zu trennen, bestimmt die Anschlagbreite-Bestimmungseinrichtung 364 (siehe Fig. 1) für jede Textzeile eine entsprechende Anschlagbreite Sw. Die durchschnittliche Anschlagbreite wird bestimmt, indem der modale Wert der Lauflängen in der Vielzahl der verbundenen Komponenten festgestellt wird, die mit einer bestimmten Textzeile assoziiert sind. Die Anschlagbreite-Bestimmungseinrichtung 364 umfaßt eine Breite-Verbundene-Komponenten-Feststellungseinrichtung 3640 zum Feststellen von verbundenen Komponenten, die breiter als eine vorbestimmte Breite sind, eine Kostenverteilungs-Erzeugungseinrichtung 3642 zum Erzeugen einer Kostenverteilung für jede breite verbundene Komponente, eine Kostenminima-Feststellungseinrichtung 3644 zu Feststellen von Minima innerhalb der Kostenverteilung und eine Verbunde-Komponenten-Teilungseinrichtung 3646 zum Teilen einer einzelnen verbundenen Komponente in zwei verbundene Komponenten an einem festgestellten Minimum.
Im Betrieb wird jede verbundene Komponente innerhalb einer Zeile mit einer Breite Cw, die mehr als dreimal so groß wie die repräsentative Anschlagbreite Sw ist, festgestellt und verarbeitet. Um eine verbundene Komponente mit einer Breite Cw, die wenigstens dreimal so groß wie die Anschlagbreite Sw ist, zu verarbeiten, wird jede Spalte dieser verbundenen Komponente mit jeder benachbarten Spalte UND-verknüpft und wird die Anzahl der "On"-Pixel der UND-verknüpften Spalten bestimmt, um eine Kostenverteilung zu erzeugen, die ein Pixel schmäler ist als die verbundene Komponente. Die Kostenverteilung wird dann analysiert, um Minima festzustellen. Für höchstens ein Minimum (vorzugsweise das linkeste Minimum, wenn 2 oder mehr Minima mit demselben Wert vorhanden sind), das einen Wert aufweist, der geringer als die repräsentative Anschlagbreite Sw ist, und mehr als 1,5 mal die Anschlagbreite Sw rechts von der linken Grenze und links von der rechten Grenze des entsprechenden Begrenzungsrechtecks lokalisiert ist, wird die verbundene Komponente in zwei verbundene Komponenten geteilt. Dieser Prozeß wird rekursiv auf jedes verbleibende Fragment angewendet, bis alle Fragmente erneut geprüft und bei Bedarf erneut geteilt wurden. Wenn wie in Fig. 5, Teil (b) gezeigt die Ligatur beabsichtigt ist, wie etwa bei "fi" in "confidence", dann wird häufig kein Minimum gefunden. In diesem Fall wird die Ligatur als ein einzelnes Zeichen behandelt.
Nachdem jede Zeile des Textteils 104 bestimmt wurde, bestimmt die Wortzwischenraum- Bestimmungseinrichtung 362 die Zeichen und Wortzwischenräume in jeder Textzeile des Textteils 104. Die Wortzwischenraum-Bestimmungseinrichtung 362 umfaßt eine Zeilenerstreckung-Bestimmungseinrichtung 3620 zum Bestimmen der linken und rechten Ränder jeder Zeile, eine Zwischenraumbreitenverteilung-Bestimmungseinrichtung 3622 zum Erzeugen einer Verteilung der bestimmten Zwischenraumbreiten und eine Zwischenraumbreitenverteilung-Analyseeinrichtung 3624 zum Analysieren der Zwischenraumbreitenverteilung. Die Zwischenraumbreitenverteilung-Analyseeinrichtung 3624 umfaßt eine Verteilungsspitzen-Feststellungseinrichtung 3626 zum Feststellen von Spitzen in der Zwischenraumbreitenverteilung und eine Verteilungsspitzen-Analyseeinrichtung 3628 zum Bestimmen, ob die festgestellten Spitzen Zwischenräume zwischen Wörtern oder innerhalb von Wörtern wiedergeben.
Im Betrieb wird der Anfang und das Ende von Zeilen als der Anfang und das Ende von Wörtern angenommen. Dann werden innerhalb einer Zeile die Zwischenräume innerhalb des horizontal gespreizten Textes zwischen verbundenen Komponenten festgestellt, und es wird eine Verteilungskurve der Breiten der Zwischenräume erzeugt. Die Breiten der Zwischenräume werden als die Distanz zwischen der rechtesten Kante einer links benachbarten verbundenen Komponente und der linkesten Kante einer rechts benachbarten Komponente gemessen. Allgemein ist die Verteilungskurve bimodal, wobei die Spitzen die schmalen Zwischenräume zwischen den Zeichen innerhalb von Wörtern und die breiten Zwischenräume zwischen Wörtern wiedergeben. Natürlich ist es möglich, daß eine oder beide Spitzen fehlen. Wenn die niedrigere Spitze, die einen Zwischenraum innerhalb von Wörtern wiedergibt, fehlt, dann kann der Text "eng gesetzt" sein. Die höchste Spitze der Verteilungskurve des nicht gespreizten Texts wird mit der Verteilungskurve des horizontal gespreizten Textteils verglichen. Wenn diese Spitze nicht mit einem Zwischenraum einer Zwischenzeichenzelle übereinstimmt, dann handelt es sich um einen Zwischenraum zwischen Wörtern. Wenn die höhere Spitze fehlt oder mit dem Zwischenraum zwischen Wörtern übereinstimmt, dann bedeutet dies, daß die Textzeile ein einziges Wort umfaßt.
Weil das Verfahren und die Vorrichtung der vorliegenden Erfindung auf einer statistischen Vorgehensweise basieren, sind sie sehr robust und können auch bei einem sehr schlecht gedruckten und/oder gescannten Dokument angewendet werden. Das heißt, daß es nicht erforderlich ist, daß das digitale Datensignal oder die aus dem digitalen Datensignal erzeugten verbundenen Komponenten perfekt jedes Zeichen des Dokuments wiedergeben. Die vorliegende Erfindung kann vielmehr auch dann angewendet werden, wenn gewöhnliche Scannfehler wie etwa das Teilen eines einzelnen verbundenen Komponentenzeichens in zwei oder mehr verbundene Komponenten oder das Verbinden von zwei oder mehr separaten verbundenen Komponentenzeichen zu einer einzelnen verbundenen Komponente auftreten.
Der horizontal gespreizte Text wird dann an die Zeichenzellen-Erzeugungseinrichtung 38 ausgegeben, um die Zeichenzellen innerhalb jeder Textzeile zu erzeugen. Für jeden Satz aus einer oder mehr vertikal miteinander ausgerichteten (d. h. horizontal überlappenden) verbundenen Komponenten, wird eine die verbundenen Komponenten umgebende Zeichenzelle durch die Zeichenzellen-Erzeugungseinrichtung 38 gebildet. Die Dimensionen jeder Zeichenzelle erstrecken sich von der obersten Position zu der untersten Position der entsprechenden Textzeile und von der linkesten Position der verbundenen Komponenten der Zeichenzelle zu der rechtesten Position der verbundenen Komponenten der Zeichenzelle, wie in Fig. 5(c) gezeigt.
Ein vereinfachtes Flußdiagramm des Betriebs des oben beschriebenen Schriftbestimmungssystems ist in Fig. 9 gezeigt. In Schritt S100 startet das System, und das Dokument wird in Schritt S110 gescannt, um das digitale Datensignal zu erzeugen. Das digitale Bilddatensignal wird dann gereinigt, indem in Schritt S120 gewünschte Vorverarbeitungsalgorithmen auf das digitale Bilddatensignal angewendet werden. In Schritt S130 werden die verbundenen Komponenten des digitalen Bilddatensignals identifiziert, und in Schritt S140 werden die Begrenzungsrechtecke für jede der bestimmten verbundenen Komponenten erzeugt.
Dann wird in Schritt S150 der Textteil vertikal gespreizt. In Schritt S160 werden die Textzeilen in dem gespreizten Text identifiziert. In Schritt 170 werden die Vertikalprofile jeder Zeile erzeugt und die obersten, untersten, linkesten und rechtesten Positionen sowie die Positionen der Basislinie und (wenn möglich) der x-Linie festgestellt. In Schritt S180 werden die verbundenen Komponenten und die Begrenzungsrechtecke für jede Zeile identifiziert.
Dann werden in Schritt S190 alle Zeilen des Textteils horizontal gespreizt. In Schritt S200 wird die modale Anschlagbreite für jede Zeile bestimmt, und in Schritt S210 werden mögliche Ligaturen in dem Textteil festgestellt. In Schritt S220 werden die festgestellten Ligaturen rekursiv zu den konstituierenden unabhängigen verbundenen Komponenten geteilt. In Schritt S230 werden die Zeichen- und Wortzwischenräume in jeder Zeile identifiziert. In Schritt S240 werden die Zeichenzellen jeder Zeile identifiziert und deren Dimensionen bestimmt. In Schritt S250 werden die Listen der Zeichenzellen, der entsprechenden Begrenzungsrechtecke und der verbundenen Komponenten ausgegeben. Dann stoppt der Prozeß in Schritt S260.

Claims

1. Automatisches Textmerkmalerkennungssystem zum Erkennen eines Textmerkmals eines ersten Textstücks (104) eines Bilds (102) eines Dokuments, mit:

einer Eingabeeinrichtung (24) zum Eingeben eines digitalen Datensignals, das das erste Textstück darstellt, wobei das digitale Datensignal eine Vielzahl von Signalabschnitten umfaßt, wobei jeder Signalabschnitt einem Pixel aus einer Vielzahl von Pixeln entspricht;

einer Komponentenerzeugungseinrichtung (28) zum Erzeugen einer Vielzahl von verbundenen Komponenten anhand der Vielzahl von Signalabschnitten;

einer Zeilenraummerkmalerkennungseinrichtung (36, 34, 32) zum Erkennen von Raummerkmalen jeder Zeile des ersten Textstücks, wobei jede Textzeile wenigstens eine der Vielzahl von verbundenen Komponenten umfaßt,

dadurch gekennzeichnet, daß die Raummerkmalerkennungseinrichtung eine Ausbreitungseinrichtung (32, 360) zum Erzeugen eines vertikal ausgebreiteten (Fig. 2(b) und 5(b)) Textstücks anhand des ersten Textstücks enthält, wobei wenigstens eine verbundene Komponente bewegt wird, um eine unnormal große Menge von Platz zwischen wenigstens zwei verbundenen Komponenten zu schaffen.

2. System nach Anspruch 1, das ferner eine Grenzrechteckerzeugungseinrichtung (30) zum Erzeugen einer Vielzahl von Grenzrechtecken (Fig. 3) umfaßt, wobei jedes Grenzrechteck eine entsprechende der Vielzahl von verbundenen Komponenten umgibt, wobei jede Ausbreitungseinrichtung ein ausgebreitetes Textstück durch Bewegen eines Ursprungs jedes Grenzrechtecks erzeugt, das einer bewegten verbundenen Komponente entspricht.

3. System nach Anspruch 1 oder 2, wobei die Zeilenraummerkmalerkennungseinrichtung (36, 34, 32) ferner umfaßt:

eine Vertikalprofileinrichtung (34) zum Erzeugen eines vertikalen Profils bezüglich des vertikal gespreizten Textstücks, wobei das Vertikalprofil die Dichteverteilung von schwarzen Punkten entlang der vertikalen Richtung darstellt.

4. System nach Anspruch 1, 2 oder 3, wobei die Zeilenraummerkmalerkennungseinrichtung (36, 34, 32) ferner eine Zeileninhaltserkennungseinrichtung zum Erkennen, welche der Vielzahl von verbundenen Komponenten jeder Zeile des ausgebreiteten Textstücks entsprechen, umfaßt.

5. System nach Anspruch 3 oder 4, der von Anspruch 3 abhängt, wobei die Vertikalprofileinrichtung (34) ferner eine Vertikalpositionserkennungseinrichtung (340) zum Erkennen einer obersten Position und einer untersten Position und wenigstens einer Grundlinienposition und einer x-Zeilenposition umfaßt, die auf den entsprechenden der Vielzahl von verbundenen Komponenten für jede Zeile des nicht ausgebreiteten Textstücks basieren.

6. System nach Anspruch 5, wobei die Vertikalpositionsbestimmungseinrichtung (340) ausgelegt ist, um die oberste und unterste Position jeder wenigstens einen Zeile basierend auf Übergängen von Null zu Nicht-Null-Werten unter Benutzung des Vertikalprofils, das jeder Zeile entspricht, zu bestimmen.

7. Verfahren zum automatischen Erkennen von Textmerkmalen eines ersten Textstücks (104) eines Bildes (102) eines Dokuments mit den Schritten:

Eingeben eines digitalen Datensignals, das das erste Textstück darstellt, wobei das digitale Datensignal eine Vielzahl von Signalabschnitten umfaßt, wobei jeder Signalabschnitt einem aus einer Vielzahl von Pixeln entspricht;

Erzeugen einer Vielzahl von verbundenen Komponenten anhand der Vielzahl von Signalabschnitten; und

Erkennen von räumlichen Merkmalen jeder Zeile des ersten Textstücks, wobei jede Textzeile wenigstens eine aus der Vielzahl von verbundenen Komponenten umfaßt, dadurch gekennzeichnet, daß der Erkennungsschritt das Erzeugen eines ausgebreiteten (Fig. 2(b)) Textstücks anhand des ersten Textstücks durch Bewegen wenigstens einer verbundenen Komponente umfaßt, um eine unnormal große Menge von Platz zwischen wenigstens zwei verbundenen Komponenten zu schaffen.

8. Verfahren zum automatischen Erkennen von Textmerkmalen nach Anspruch 7, das ferner das Erzeugen einer Vielzahl von Grenzrechtecken (Fig. 3) umfaßt, wobei jedes Grenzrechteck eine entsprechende aus der Vielzahl von verbundenen Komponenten umgibt, wobei das Erzeugen eines ausgebreiteten Textstücks durch. Bewegen eines Ursprungs jedes Grenzrechtecks ausgeführt wird, das einer bewegten verbundenen Komponente entspricht.

9. Verfahren nach Anspruch 7, das ferner die Schritte umfaßt:

Erzeugen eines Vertikalprofils des vertikal gespreizten Textstücks, wobei das Vertikalprofil die Dichteverteilung von schwarzen Punkten entlang der vertikalen Richtung darstellt.

10. Verfahren nach Anspruch 9, wobei der Erkennungsschritt den Schritt des Erkennens, welcher der Vielzahl von verbundenen Komponenten jeder Zeile des Textstücks entsprechen, umfaßt.

11. Verfahren nach Anspruch 9 oder 10, wobei der Schritt des Erzeugens eines Vertikalprofils den Schritt des Erkennens einer obersten Position und einer untersten Position und wenigstens einer Basislinienposition und einer x-Linienposition (Fig. 4), basierend auf den entsprechenden der Vielzahl von verbundenen Komponenten für jede Zeile für das Textstück umfaßt.