PatentDe  


Dokumentenidentifikation DE19533585C1 09.01.1997
Titel Verfahren zur Segmentierung von Zeichen
Anmelder Maaß, Peter, Prof. Dr., 14129 Berlin, DE
Erfinder Maaß, Peter, Prof. Dr., 14129 Berlin, DE
Vertreter Patentanwälte Gulde Hengelhaupt Ziebig, 10785 Berlin
DE-Anmeldedatum 01.09.1995
DE-Aktenzeichen 19533585
Veröffentlichungstag der Patenterteilung 09.01.1997
Veröffentlichungstag im Patentblatt 09.01.1997
IPC-Hauptklasse G06K 9/34
Zusammenfassung Die Erfindung beschreibt ein Verfahren zur Segmentierung von Zeichen, mit welchem Verklebungen innerhalb von Zeichen und/oder zwischen benachbarten Zeichen ganz oder teilweise aufgelöst werden können, indem dunkle Druckfarbenpixel mit einer hohen Temperatur und helle Papierpixel mit einer niedrigen Temperatur gleichgesetzt werden und die Ausbreitung der Wärmeverteilung als Kriterium für das Auslaufen der Druckfarbe rechentechnisch verarbeitet wird, wobei aus der vorhandenen Temperaturverteilung Rückschlüsse auf zuvor vorhandene Temperaturen gezogen werden und/oder Krater in Form von trichterförmigen Vertiefungen mit Methoden der Bildverarbeitung lokalisiert und gespeichert und nachfolgend die Konturen der Krater durch Abschmelzen verändert werden, indem der Boden der Krater und/oder die Wände der Krater erweitert werden.

Beschreibung[de]

Die Erfindung betrifft ein Verfahren zur Segmentierung von Zeichen und ist anwendbar insbesondere zur Ergänzung der OCR (Optical Character Recognition). Ein bevorzugtes Anwendungsgebiet der Erfindung ist die automatische Attributierung von Dokumenten in Archivierungssystemen.

Es ist bekannt, in Papierform vorliegende Texte, Bilder und Graphiken mittels sogenannter OCR-Programme über Scanner zu erfassen und im Speicher von Computern abzulegen.

Wesentliches Kriterium für die Anwendbarkeit in der täglichen Praxis ist die Erkennungsrate der OCR.

Im Betrieb oder bei der Errichtung von Betrieben entsteht eine Vielzahl technischer oder kaufmännischer Unterlagen, die innerhalb eines festgelegten Ordnungssystem registriert und abgelegt werden. Die Gesamtheit dieser Unterlagen enthält alle Daten und dient als Grundlage des Betriebes.

Eine wichtige Anforderung an die Dokumentation ist das rasche Auffinden der Dokumente. Dazu ist es notwendig, daß den Dokumenten bei der Einspeisung in das Dokumentensystem Attribute, wie etwa Kontonummer, Titel, Unterlagennummer oder ähnliches in einer geeigneten Systematik zugeordnet werden müssen. Da sich diese Attribute auf den Dokumenten befinden ist es von großem Vorteil, direkt beim Digitalisieren der Papierdokumente die entsprechenden Attribute automatisch herauszufiltern, zu bearbeiten, mit Hilfe eines Texterkennungsprogrammes zu deuten und in die Dokumentation zu integrieren.

Dieser Ablauf zur automatischen Ablage von Papierdokumenten in das Dokumentensystem wird automatische Attributierung genannt und wie folgt vollzogen:

Nach dem Digitalisieren/Scannen der Dokumente werden diese zunächst ausgerichtet. Dies bedeutet, daß durch Scannen oder Kopieren entstandene eventuelle Schieflagen korrigiert werden.

Da mehrere Formulare gleichen Formulartyps vorliegen, wird für jeden Formulartyp einmalig eine Vorlage mit allen notwendigen Informationen erstellt, die einem Formular gleichen Formulartyps automatisch zugeordnet wird. Erst dann können automatisch die entsprechenden Attribute aus dem Formular herausgeschnitten und dem Dokumentationssystem zugänglich gemacht werden.

Liegt ein Formular vor, für das noch keine Vorlage erstellt ist, wird dieses wie oben beschrieben ausgerichtet und eine weitere Vorlage erstellt.

Nun erfolgt der Erkennungsprozeß der Attribute mit dem Ziel einer sehr hohen Erkennungsrate. Die bisher bekannten Methoden der Bildverarbeitung führen zu Erkennungsraten, die für eine effektive, automatische Attributierung nicht ausreichend sind.

Die US 4,635,290 beschreibt ein Verfahren, welches nur eine Segmentierung von Zeichen für Nichtproportionalschriften, d. h. nur für Fonts mit konstanter Zeichenbreite ermöglicht.

Es fließen keinerlei Konturinfomationen zur Bestimmung der Segmentierungspositionen ein. Allein aus der Verteilungsfunktion (projection distribution) heraus - und nur unter Nutzung der Werte Null und größer Null - werden die Positionen (Trennstellen) zur Segmentierung ermittelt.

Vollständige Verlaufungen, d. h. wenn durch Verlaufen der Tinte umschlossene Flächen vollständig verloren gehen, wie z. B. bei den Zeichen &min;o&min;, &min;e&min; oder &min;8&min;, werden nicht betrachtet.

Die einfache Wertschrankenarithmetik kann besonders bei längeren Wörtern zu großen Abweichungen führen, da die Intervalle mit jeder Operation stark anwachsen. Auch sind die verwendeten Konstanten sehr vom Schriftfont abhängig, und sie müßten daher für jede zu segmentierende Zeichenkette bestimmt werden. Dies schränkt das Verfahren auf Zeichenketten mit einer entsprechenden Mindestlänge ein.

Nachteilig ist ebenfalls, daß keine Schriftaufwertung vorgenommen wird, z. B. wenn die spitzen Winkel im Zeichen &min;N&min; zu Rundungen verlaufen sind.

In der Veröffentlichung Proc. of the IEEE, Vol. 80, No. 7, July 1992, pp. 1079-1092 wird ein Verfahren beschrieben, mit welchem Bereiche auf Abbildungen wie z. B. Gebäude, Personen oder Gegenstände erkannt werden sollen, wobei eine Kombination aus Schwellwert- und Quadtree-Segmentierung verwendet wird.

Dieses Verfahren ist für die Segmentierung von Zeichen in einer Zeichenkette ungeeignet, insbesondere kann es nicht zur Trennung von zusammengelaufenen Zeichen (touching characters) verwendet werden.

Das Verfahren ist auf Grauwert- und Farbbilder und nicht auf Binärbilder ausgerichtet.

In der Veröffentlichung IEEE Trans. on PAMI, Vol. 16, No. 7, July 1994, pp. 689-700 wird ein Verfahren beschrieben, welches vor allem auf Handschriften spezialisiert ist und eine vereinfachte Schriftdickenanalyse zur Trennung von Zeichen benutzt. Es werden nur vertikale Verklebungen zwischen einzelnen Zeichen versucht aufzulösen, d. h. horizontale Verklebungen zwischen einzelnen Zeichen, z. B. zweier übereinander liegender Zeilen, und Verklebungen innerhalb von Zeichen, z. B. bei den Zeichen &min;i&min;, &min;a&min; oder &min;e&min;, werden nicht aufgelöst.

Vollständige Verlaufungen, d. h. wenn durch Verlaufen der Tinte umschlossene Flächen vollständig verloren gehen, wie z. B. bei den Zeichen &min;o&min;, &min;e&min; oder &min;8&min; werden nicht betrachtet.

Das Verfahren ist auch nicht für Proportionalschriften ausgelegt, da die Schriftbreite als Konstante einfließt und es können keine Zeichen getrennt werden, bei denen eine doppelte Verklebung, wie z. B. bei den Zeichen &min;88&min; möglich oder eine sehr dicke Verklebung, wie z. B. bei den Zeichen &min;HH&min; möglich, vorliegt.

Auch wird keine Schriftaufwertung vorgenommen, z. B. wenn die spitzen Winkel im Zeichen &min;N&min; zu Rundungen verlaufen sind.

Der Erfindung liegt daher die Aufgabe zugrunde, ein Verfahren zur Segmentierung von Zeichen zu schaffen, welches mit einfachen Mitteln realisierbar ist, die Fehlerursachen bei der OCR minimiert und eine effektive, automatische Attributierung ermöglicht.

Diese Aufgabe wird erfindungsgemäß gelöst durch die Merkmale im kennzeichnenden Teil des Anspruches 1 in Verbindung mit den Merkmalen im Oberbegriff.

Zweckmäßige Ausgestaltungen der Erfindung sind in den Unteransprüchen enthalten.

Ein besonderer Vorteil der Erfindung besteht darin, daß Verklebungen innerhalb von Zeichen und/oder zwischen benachbarten Zeichen als eine der häufigsten Fehlerursachen bei der optischen Zeichenerkennung ganz oder zumindest teilweise aufgelöst werden können, indem

  • - dunkle Druckfarbenpixel mit einer hohen Temperatur und helle Papierpixel mit einer niedrigen Temperatur gleichgesetzt werden und
  • - die Ausbreitung der Wärmeverteilung als Kriterium für das Auslaufen der Druckfarbe rechentechnisch verarbeitet wird, wobei
  • - aus der vorhandenen Temperaturverteilung Rückschlüsse auf zuvor vorhandene Temperaturen gezogen werden

    und/oder
  • - Krater in Form von trichterförmigen Vertiefungen bei den Verklebungen innerhalb von Zeichen und/oder zwischen benachbarten Zeichen mit Methoden der Bildverarbeitung lokalisiert und gespeichert und nachfolgend
  • - die Konturen der Krater durch Abschmelzen verändert werden, indem der Boden der Krater und/oder die Wände der Krater erweitert werden.


Die Erfindung soll nachstehend an Hand von Ausführungsbeispielen näher erläutert werden.

Es zeigen:

Fig. 1 ein Beispiel des Auslaufens der Druckfarbe in Abhängigkeit von der Zeit;

Fig. 2 ein Text/Zahlenbeispiel zum Abschmelzen von Kratern;

Fig. 3 ein weiteres Textbeispiel zum Abschmelzen von Kratern.

Die größten Probleme bei der Erkennung von Schrifttypen werden durch die auftretenden Verklebungen erzeugt. Diese entstehen dadurch, daß bei dem Druckvorgang die Drückfarbe ausläuft und hierdurch nahe beieinanderliegende Schriftelemente verbunden werden. Der Vorgang des Auslaufens wird nun rückwärts in der Zeit betrachtet, um damit die Verklebungen zu reduzieren.

Bei dieser Vorgehensweise findet die physikalische Analogie Anwendung, daß man ein schwarzes Pixel mit einer hohen und ein weißen Pixel mit einer niedrigen Temperatur identifiziert. Das Auslaufen der Druckfarbe entspricht dann der Ausbreitung der Wärmeverteilung.

Dies kann nun vorwärts und rückwärts in der Zeit betrachtet und aus einer gegebenen Temperaturverteilung auf die zuvor vorhandenen Temperaturen geschlossen werden.

Eine Simulation dieser Prozesse ist mittels der Wärmeleitungsgleichung

ut = c Δu

oder mittels geeigneter modifizierter Diffusionsgleichung, bei denen Gewichtsfaktoren in Abhängigkeit von der Größe der Gradienten z. B.

ut= exp (-|▿u|²/2σ) Δu

eingefügt werden, möglich. Bei einer Zeit t > 0 wird ein Auslaufen der Druckfarbe und bei einer Zeit t < 0 die Auflösung der Verklebungen simuliert.

Diese Gleichungen können durch Einfügen von Gewichtsfaktoren weiter modifiziert und der jeweiligen Anwendung angepaßt werden.

Wie aus Fig. 1 zu ersehen ist, läßt sich mittels der Wärmeleitungsgleichung die zeitliche Entwicklung des Auslaufens der Druckfarbe simulieren.

A zeigt das Auslaufmodell bei einer Zeit t > 0

B zeigt das Original

und

in C und D ist das Ergebnis der Reduktion bei

t = -1 ZE (= Zeiteinheit) und t = -2 ZE dargestellt.

Durch die zeitliche Rückentwicklung sind Verklebungen ganz oder zumindest teilweise gelöst.

Allerdings können Verklebungen, wie zu ersehen ist, nur dann vollständig gelöst werden, wenn gleichzeitig deutliche Veränderungen an den Buchstaben in Kauf genommen werden.

Eine weitere Erhöhung der Erkennungsrate durch Auflösung von Verklebungen, welche neben dem Auslaufen der Druckfarbe auch durch die Kontrasteinstellung und Interpolation durch den Scanner bedingt sein können, erfolgt durch die Erkennung und Bearbeitung von sogenannten Kratern.

Betrachtet man die Verklebungen genauer, so ist zu sehen, daß sie nicht gleichmäßig vorliegen, sondern verstärkt an spitzwinkligen Zeichenkonturen wie z. B. bei den Buchstaben "N" und "W" gemäß Fig. 3 und zwischen dicht benachbarten Schriftelementen innerhalb eines oder verschiedener Buchstaben wie z. B. beim "i" in Fig. 2 oder beim "H", "N", "90" und "-N" in Fig. 3.

Es fällt jedoch auf, daß fast immer eine trichterförmige Vertiefung bestehen bleibt. Dies wird als Krater bezeichnet. Zur Beseitigung der beispielsweise aus dem Verlaufen der Druckfarbe resultierenden Fehler muß man diese zurückverfolgen. Es ist zu beachten, daß an einigen Stellen Verklebungsdicken durchtrennt werden müssen, die sogar die Schriftdicke überschreiten, d. h. nimmt man ein Abschmelzen von der Kontur aus vor, so muß an manchen Stellen bis zur doppelten Schriftdicke tief und an anderen Stellen der Kontur nicht abgeschmolzen werden. Es ist also ein Vorgehen nötig, das starke und genau lokalisierte Eingriffe vornehmen kann.

Da die Krater sich stark in Form und Größe unterscheiden, ist eine variable Repräsentation der Krater notwendig. Dies kann erfolgen durch:

  • - Referenzpixel, Pixel des Kraters zur Lokalisierung des Kraters im Gesamtbild
  • - Höhe, senkrechte Ausdehnung vom Kraterboden bis zum oberen Kraterrand in Pixel
  • - Abstände, für jede Höhe des Kraters der horizontale Abstand des linken und rechten Kraterrandes vom Referenzpixel
  • - Konturinformationen, beispielsweise welches die steilere Seite des Kraters ist


Vom Referenzpixel ausgehend wird untersucht, ob sich dort ein Kraterboden befindet (geschlossener Boden und links und rechts eine Wand), dann wird Höhe für Höhe untersucht, ob links und rechts - im Rahmen von gesetzten Parametern - eine Kraterwand vorhanden ist.

Ist keine Kraterwand vorhanden oder eine maximal zu untersuchende Höhe erreicht, wird abgebrochen. Die Repräsentation eines Kraters wird gespeichert.

Vergleicht man die Krater untereinander, so erkennt man, daß je spitzer der Winkel der Kraterwände ist, um so tiefer am Kraterboden eingeschmolzen werden muß, um den Ausgangszustand herzustellen. Der Extremfall tritt bei eng parallel verlaufenden Schriftelementen, wie in der Zeichenfolge "HN", zwischen den Buchstaben, wie in Fig. 3 zu ersehen ist, auf.

Dementsprechend wird in Abhängigkeit der aufgenommenen Repräsentation der Krater (z. B. der Höhe) und einem der jeweiligen Schrift anzupassenden Parametersatz der Kraterboden eingeschmolzen. Anschließend werden die Wände des Kraters ausgeschmolzen. Beim Ein- wie auch Ausschmelzen findet die Kontur des Kraters Reachtung, indem beispielsweise an der steileren Kraterwandseite anders verfahren wird als an der gegenüberliegenden Seite. Die Schmelzprozesse werden durch folgende Gleichungen simuliert:

Kraterbedingung: |f*DaφK| > T,

Schmelzprozeß: f neu = (f-fχU(K))+TxφK&min;, mit φK&min;=A(K, fχW(K)) (DaφK).

Dabei bezeichnet f das Schriftbild, Da den Operator, der den Krater um den Faktor a vergrößert (a>1) beziehungsweise verkleinert (a<1) und φK die Kratermodellfunktion.

Die Kraterbedingung ist erfüllt, falls in der Schriftbildfunktion f ein Krater der Größe a und der Form φK gefunden wird (Pattern-matching). Die Bedingung ist bereits erfüllt, wenn die Kraterübereinstimmung größer als T ist.

Das neue Schriftbild fneu entsteht dadurch, daß der gefundene Krater im Schriftbild durch den angepaßten Krater K&min; ersetzt wird. Dabei ist der Anpassungsoperator a von dem Krater und der Umgebung U(K) im Schriftbild abhängig.

Da die meisten handelsüblichen OCR-Programme keine Möglichkeit der Rückkopplung bieten, d. h. sie geben keine prozentuale Wahrscheinlichkeit an, mit der sie die einzelnen Zeichen erkannt haben, ist es im allgemeinen nicht möglich, nur an Zeichen mit unzureichender Erkennungswahrscheinlichkeit Änderungen vorzunehmen, die anderen Zeichen jedoch unverändert zu lassen. Bei jedem Verfahren müssen daher nicht nur die Anzahl der aufgrund der Bearbeitung nun richtig erkannten Zeichen betrachtet werden, sondern auch die Anzahl der Zeichen, die durch nie ganz auszuschließende Nebenwirkung nun falsch erkannt werden. Das Verhältnis aus diesen beiden Zahlen gibt Auskunft über die Gesamtverbesserung der Erkennungsrate.


Anspruch[de]
  1. 1. Verfahren zur Segmentierung von Zeichen, wobei Papierdokumente durch Einscannen digitalisiert und nachfolgend gespeichert werden, dadurch gekennzeichnet, daß Verklebungen innerhalb von Zeichen und/oder zwischen benachbarten Zeichen ganz oder teilweise aufgelöst werden, indem
    1. - dunkle Druckfarbenpixel mit einer hohen Temperatur und helle Papierpixel mit einer niedrigen Temperatur gleichgesetzt werden und
    2. - die Ausbreitung der Wärmeverteilung als Kriterium für das Auslaufen der Druckfarbe rechentechnisch verarbeitet wird, wobei
    3. - aus der vorhandenen Temperaturverteilung Rückschlüsse auf zuvor vorhandene Temperaturen gezogen werden und/oder
    4. - Krater in Form von trichterförmigen Vertiefungen bei den Verklebungen innerhalb von Zeichen und/oder zwischen benachbarten Zeichen mit Methoden der Bildverarbeitung lokalisiert und gespeichert und nachfolgend
    5. - die Konturen der Krater durch Abschmelzen verändert werden, indem der Boden der Krater und/oder die Wände der Krater erweitert werden.
  2. 2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß mittels der Wärmeleitungsgleichung

    ut= c Δu

    oder mittels geeigneter modifizierter Diffusionsgleichung, bei denen Gewichtsfaktoren in Abhängigkeit von der Größe der Gradienten z. B.

    ut= exp (-|▿u|²/2σ) Δu

    eingefügt werden, wobei die Modifikation bewirkt, daß große Gradienten (= wesentliche Kanten) erhalten bleiben,

    für t > 0 ein Auslaufen der Druckfarbe und

    für t < 0 die Auflösung von Verklebungen simuliert

    wird.
  3. 3. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß als Parameter der Krater jeweils ein Referenzpixel, die Höhe in Pixel als senkrechte Ausdehnung vom Kraterboden bis zum oberen Kraterrand und für jede Höhe jeweils der horizontale Abstand des linken und rechten Kraterrandes vom Referenzpixel erfaßt werden.
  4. 4. Verfahren nach Anspruch 3, dadurch gekennzeichnet, daß zusätzlich Konturinformationen erfaßt werden.
  5. 5. Verfahren nach Anspruch 4, dadurch gekennzeichnet, daß die Konturinformationen die Steilheit der Kraterwände charakterisieren.
  6. 6. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß das Abschmelzen der Krater durch Einschmelzen des Kraterbodens und/oder Ausschmelzen der Kraterwände erfolgt, wobei die Schmelzprozesse durch folgende Gleichungen simuliert werden:

    Kraterbedingung: |f*DaφK|>T,

    Schmelzprozeß: fneu = (f-fxU(K))+TxφK&min;, mit φK&min;=A(K,fχU(K)) (DaφK),

    wobei

    f das ursprüngliche Schriftbild,

    fneu das neue Schriftbild,

    Da der Operator,

    φK die Kratermodellfunktion,

    K der Krater,

    K&min; der angepaßte Krater und U(K) die Umgebung ist.






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